bug#25592: Feature request: sorting overlays

[Clément Pit--Claudel]

On 2017-02-04 03:13, Eli Zaretskii wrote:
>> Cc: 25592@debbugs.gnu.org From: Clément Pit--Claudel
>> <clement.pitclaudel@live.com> Date: Fri, 3 Feb 2017 16:51:24 -0500
>> 
>>>> No: I'm iterating over all overlays, and applying them one by
>>>> one.
>>> 
>>> Why not do it as I suggest?  Then your problems with sorting will
>>> be solved as a nice side-effect.
>> 
>> I'm worried about the cost and the additional implementation
>> complexity.  My current algorithm is very simple: iterate over
>> overlays, applying their properties to the ranges they cover.  In
>> contrast, scanning over overlays introduces additional complexity
>> (I need to keep track of which overlays I have already applied and
>> move around the buffer), and additional costs (next-overlay-change
>> seems to do quite a bit of work).
> 
> Why would you need to keep track of overlays, if you always process 
> each one just once?

To avoid applying the same overlay twice. But I think I understand your 
suggestion better now, and you meant that I would apply each overlay's 
properties not to the entire overlay's range (overlay-start .. overlay-end), 
but instead just to the current range (as determined by next-overlay-change).  
Correct?
 
> As for costs, next-overlay-change (or one of its variants) is used
> by the display engine in its inner loops (see 
> compute_display_string_pos), so it should be fast enough for your 
> needs, I think.

I see, thanks.  I'll consider this option, then!

>> None of this is a show stopper (in fact, I don't even know for sure
>> that the slowdown would be significant, and I do know that I don't
>> expect to have that many overlays anyway :), but it'd be nice to be
>> able to use the "simpler" solution.
> 
> But the "simpler" solution has a problem, whereby the order of the 
> overlays might depend on buffer position for which you evaluate the 
> order, because overlays could begin at the same position, but end at 
> different ones, or vice versa.  IOW, the overlaps between portions
> of the buffer text "covered" by different overlays could be partial.
> How do you handle this situation in your algorithm?  The correct
> solution would require having different values of the corresponding
> text property for different locations, according to the
> highest-priority overlay at each location.  Am I missing something?

I think I'm probably the one missing something :) I'm not sure I understand the 
problem.  Here's my current algorithm:

(defun esh--filter-plist (plist props)
  "Remove PROPS from PLIST."
  (let ((filtered nil))
    (esh--doplist (prop val plist)
      (unless (memq prop props)
        (push prop filtered)
        (push val filtered)))
    (nreverse filtered)))

(defun esh--number-or-0 (x)
  "Return X if X is a number, 0 otherwise."
  (if (numberp x) x 0))

(defun esh--augment-overlay (ov)
  "Return a list of three values: the priorities of overlay OV, and OV."
  (let ((pr (overlay-get ov 'priority)))
    (if (consp pr)
        (list (esh--number-or-0 (car pr)) (esh--number-or-0 (cdr pr)) ov)
      (list (esh--number-or-0 pr) 0 ov))))

(defun esh--augmented-overlay-< (ov1 ov2)
  "Compare two lists OV1 OV2 produced by `esh--augment-overlay'."
  (or (< (car ov1) (car ov2))
      (and (= (car ov1) (car ov2))
           (< (cadr ov1) (cadr ov2)))))

(defun esh--buffer-overlays (buf)
  "Collects overlays of BUF, in order of increasing priority."
  (let* ((ovs (with-current-buffer buf (overlays-in (point-min) (point-max))))
         (augmented (mapcar #'esh--augment-overlay ovs))
         (sorted (sort augmented #'esh--augmented-overlay-<)))
    (mapcar #'cl-caddr sorted)))

(defconst esh--overlay-specific-props
  '(after-string before-string evaporate isearch-open-invisible
                 isearch-open-invisible-temporary priority window)
  "Properties that only apply to overlays.")

(defun esh--commit-overlays (buf)
  "Copy overlays of BUF into current buffer's text properties."
  (let ((pt-min-diff (- (with-current-buffer buf (point-min)) (point-min))))
    (dolist (ov (esh--buffer-overlays buf))
      (let* ((start (max (point-min) (- (overlay-start ov) pt-min-diff)))
             (end (min (point-max) (- (overlay-end ov) pt-min-diff)))
             (ov-props (overlay-properties ov))
             (cat-props (let ((symbol (plist-get ov-props 'category)))
                          (and symbol (symbol-plist symbol))))
             (face (let ((mem (plist-member ov-props 'face)))
                     (if mem (cadr mem) (plist-get cat-props 'face))))
             (props (esh--filter-plist (append cat-props ov-props)
                                    (cons 'face esh--overlay-specific-props))))
        (when face
          (font-lock-prepend-text-property start end 'face face))
        (add-text-properties start end props)))))

I can trim the code to remove bits that are not directly relevant, if you want.

>>>>> How did you implement in Lisp the "last resort" of
>>>>> comparison, which compares addresses of the C structs?
>>>> 
>>>> I didn't :)
>>> 
>>> So it isn't really a solution ;-)
>> 
>> It's not a full reimplementation, but it's enough of a solution for
>> me :) The docs say “If SORTED is non-‘nil’, the list is in
>> decreasing order of priority”, and that's what my implementation
>> does.
> 
> Then there will be use cases where your solution will give a wrong 
> value to the text property that replaces the overlays.

Snap.  Do you have a concrete example?  I imagine this would happen if two 
overlays are added to the same range of text, with no explicit priority?

Thanks for your comments!
Clément.

signature.asc
Description: OpenPGP digital signature