Re: noverlay branch

[Matt Armstrong <matt@rfc20.org>]

Eli Zaretskii <eliz@gnu.org> writes:

[...]

>> I was planning to takle these problems before proposing a merge:
>>
>>  1) Improve the worst case run time of `previous-overlay-change' from
>>     O(n) to O(log N).  The noverlay branch uses an O(N) algorithm,
>>     though it is difficult to spot.  Since the point of using a tree is
>>     O(log N) algorithms, and O(n) algorithms can easily become
>>     exponential algorithms when composed in higher level loops (the
>>     problem overlays sees today), this strikes me as important.

[...]

>>  3) Improve quality of comments in the new code.  Personally, I find the
>>     algorithms quite subtle and quite a bit more complex than what you
>>     find on, say, https://en.wikipedia.org/wiki/Interval_tree or the
>>     Cormen et al. Introduction to Algorithms Book.  I think I pieced
>>     most of it together but it took a lot of effort.  At top of mind is
>>     looking at the interval_node.visited flag and figure out how that
>>     flag is used, then describe the algorithm in detail.  It isn't clear
>>     to me how that flag gets set/cleared.  Best case: doing so proves me
>>     wrong on point (1).

[...]

> We want to have this feature in Emacs 29, so, barring some grave bugs
> that will be uncovered soon enough, this branch will land on master
> soon.  You can work on the items you've mentioned either now or after
> the branch is merged.  Item 3 can be done immediately, and will be
> greatly appreciated, as comments that explain how the code works are
> always welcome.

I agree that this is a good plan.

A nice thing about the noverlay branch is that it touches every place in
Emacs that deals with overlay lists and, better, puts that behind an
API.  That is a good reason to merge noverlay now and, maybe, change
things later.


> Of the rest, item 1 sounds like the most important one, but do you
> have ideas for how to achieve that?

I think (3) -- improving the comments -- is a good starting point,
because I want to verify my claim that the *-overlay-change algorithms
are worst-case inefficient.

My idea is: store each overlay in two trees, one ordered by ascending
BEG and one ordered by descending END.  These are the similar to the
current "overlays before" and "overlays after" linked lists, except that
the "overlay center" is gone and replaced by O(log N) lookups.  (In fact
we could retain the idea of an "overlay center" by maintaining a
"finger" node in each tree...but I digress...)

From there an algorithm that is O(log N) in an obvious way falls out
trivially in the same way it does for the current overlay lists
approach.