bug#25592: Feature request: sorting overlays

[Eli Zaretskii <eliz@gnu.org>]

> 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?

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.

> 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?

> >>> 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.