noverlay branch

noverlay branch

[Stefan Monnier]

I just updated the noverlay branch to the code in `master` (most of it
was mechanical except for the fact that since the last commit on that
branch we have gotten rid of Lisp_Misc and we moved to pdumper).

I'm getting ready to install this in `master`, so I'd encourage people
to try this code as much as possible to try and weed out the most
glaring problems before it hits master.  The code generally looks good,
but it touches some quite "core" code in the redisplay (with lots of
off-by-one opportunities) and in the memory management (with
opportunities for crashes and memory leaks).

For those who're not familiar with this branch, it changes the way
overlays are stored in a buffer: instead of keeping them in naïve
singly-linked lists, it keeps them in balanced binary trees, so as to
replace an O(N) complexity with O(log N). This way Emacs should not get
sluggish even with millions of overlays (of course, if a given buffer
position is covered by a million overlays, it'll still be sluggish when
operating around that position).


        Stefan

Re: noverlay branch

[Lars Ingebrigtsen]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> I just updated the noverlay branch to the code in `master`

Great!

I've tried using it for a couple minutes doing my normal setup (which
involves a bunch of stuff), and I don't see any anomalies, which is
promising.

But I'm getting these two test failures in buffer-tests.el:

2 unexpected results:
   FAILED  test-overlays-in-2
   FAILED  test-remove-overlays

Re: noverlay branch

[Stefan Monnier]

Lars Ingebrigtsen [2022-09-26 00:50:40] wrote:
> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> I just updated the noverlay branch to the code in `master`
>
> Great!
>
> I've tried using it for a couple minutes doing my normal setup (which
> involves a bunch of stuff), and I don't see any anomalies, which is
> promising.
>
> But I'm getting these two test failures in buffer-tests.el:
>
> 2 unexpected results:
>    FAILED  test-overlays-in-2
>    FAILED  test-remove-overlays

Yes, they're in my todo already :-)


        Stefan

Re: noverlay branch

[Ihor Radchenko]

[-- Attachment #1: Type: text/plain, Size: 976 bytes --]

On Mon, Sep 26, 2022 at 6:38 AM Stefan Monnier <monnier@iro.umontreal.ca>
wrote:

> I just updated the noverlay branch to the code in `master` (most of it
> was mechanical except for the fact that since the last commit on that
> branch we have gotten rid of Lisp_Misc and we moved to pdumper).
>
> Thanks! I have been waiting for this for years.


> I'm getting ready to install this in `master`, so I'd encourage people
> to try this code as much as possible to try and weed out the most
> glaring problems before it hits master.  The code generally looks good,
> but it touches some quite "core" code in the redisplay (with lots of
> off-by-one opportunities) and in the memory management (with
> opportunities for crashes and memory leaks).
>

I tried with my Emacs config and after some fiddling Emacs crashed during
helm search via helm-org-ql (a lot of regexp searching).
I was unable to trigger the crash using unoptimized build, so just giving a
heads-up.

Best,
Ihor

[-- Attachment #2: Type: text/html, Size: 1556 bytes --]

Re: noverlay branch

[Stefan Monnier]

> I tried with my Emacs config and after some fiddling Emacs crashed during
> helm search via helm-org-ql

If you can run it under GDB and provide a backtrace when you get such
a crash, that would be immensely helpful (especially if you can build
with `--enable-checking` and without too high an optimization level).

Even better of course is a reproducible recipe.

> (a lot of regexp searching).

The regexp search code is largely untouched, so it's probably not
directly connected (famous last word?).

> I was unable to trigger the crash using unoptimized build, so just giving a
> heads-up.

Oh, well, thanks anyway, it's still a useful data point.


        Stefan

Re: noverlay branch

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@gmail.com>
> Date: Mon, 26 Sep 2022 10:52:11 +0800
> Cc: emacs-devel <emacs-devel@gnu.org>
> 
> I tried with my Emacs config and after some fiddling Emacs crashed during helm search via helm-org-ql (a
> lot of regexp searching).
> I was unable to trigger the crash using unoptimized build, so just giving a heads-up.

A backtrace from an optimized build can also be of help.  It is
certainly better than nothing.

Thanks.

Re: noverlay branch

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> I tried with my Emacs config and after some fiddling Emacs crashed during helm search via helm-org-ql (a
>> lot of regexp searching).
>> I was unable to trigger the crash using unoptimized build, so just giving a heads-up.
>
> A backtrace from an optimized build can also be of help.  It is
> certainly better than nothing.

(the other attempt with unoptimized build was using
./configure --enable-checking='yes,glyphs' --enable-check-lisp-object-type CFLAGS='-O0 -g3' --without-native-compilation)

Backtrace after ./configure && make bootstrap

I
1. Opened bunch of Org files
2. Generated agenda view (agenda creates a bunch of markers)
3. Ran helm-org-ql in an Org buffer. The results never arrived and once
   I hit C-g to abort helm process, Emacs crashed.

Fatal error 6: Aborted
Backtrace:
/home/yantar92/Git/emacs/src/emacs(+0x19ec41)[0x5555556f2c41]
/home/yantar92/Git/emacs/src/emacs(+0x4ae2c)[0x55555559ee2c]
/home/yantar92/Git/emacs/src/emacs(+0x4b37f)[0x55555559f37f]
/home/yantar92/Git/emacs/src/emacs(+0x517fa)[0x5555555a57fa]
/home/yantar92/Git/emacs/src/emacs(+0x279cf2)[0x5555557cdcf2]
/home/yantar92/Git/emacs/src/emacs(+0x2031a4)[0x5555557571a4]
/home/yantar92/Git/emacs/src/emacs(+0x1c4819)[0x555555718819]
/home/yantar92/Git/emacs/src/emacs(+0x2511b7)[0x5555557a51b7]
/home/yantar92/Git/emacs/src/emacs(+0x20aae3)[0x55555575eae3]
/home/yantar92/Git/emacs/src/emacs(+0x208f41)[0x55555575cf41]
/home/yantar92/Git/emacs/src/emacs(+0x17d854)[0x5555556d1854]
/home/yantar92/Git/emacs/src/emacs(+0x2094bc)[0x55555575d4bc]
/home/yantar92/Git/emacs/src/emacs(+0x184213)[0x5555556d8213]
/home/yantar92/Git/emacs/src/emacs(+0x191825)[0x5555556e5825]
/home/yantar92/Git/emacs/src/emacs(+0x208ca7)[0x55555575cca7]
/home/yantar92/Git/emacs/src/emacs(+0x17c6b6)[0x5555556d06b6]
/home/yantar92/Git/emacs/src/emacs(+0x208c01)[0x55555575cc01]
/home/yantar92/Git/emacs/src/emacs(+0x17c601)[0x5555556d0601]
/home/yantar92/Git/emacs/src/emacs(+0x183a74)[0x5555556d7a74]
/home/yantar92/Git/emacs/src/emacs(+0x1b6efb)[0x55555570aefb]
/home/yantar92/Git/emacs/src/emacs(+0x20d58a)[0x55555576158a]
/home/yantar92/Git/emacs/src/emacs(+0x2511b7)[0x5555557a51b7]
/home/yantar92/Git/emacs/src/emacs(+0x20aae3)[0x55555575eae3]
/home/yantar92/Git/emacs/src/emacs(+0x20ad08)[0x55555575ed08]
/home/yantar92/Git/emacs/src/emacs(+0x2511b7)[0x5555557a51b7]
/home/yantar92/Git/emacs/src/emacs(+0x20aae3)[0x55555575eae3]
/home/yantar92/Git/emacs/src/emacs(+0x20ad08)[0x55555575ed08]
/home/yantar92/Git/emacs/src/emacs(+0x2511b7)[0x5555557a51b7]
/home/yantar92/Git/emacs/src/emacs(+0x20f897)[0x555555763897]
/home/yantar92/Git/emacs/src/emacs(+0x20e2f6)[0x5555557622f6]
/home/yantar92/Git/emacs/src/emacs(+0x20f465)[0x555555763465]
/home/yantar92/Git/emacs/src/emacs(+0x20aae3)[0x55555575eae3]
/home/yantar92/Git/emacs/src/emacs(+0x20644f)[0x55555575a44f]
/home/yantar92/Git/emacs/src/emacs(+0x20aae3)[0x55555575eae3]
/home/yantar92/Git/emacs/src/emacs(+0x20aeb8)[0x55555575eeb8]
/home/yantar92/Git/emacs/src/emacs(+0x207d67)[0x55555575bd67]
/home/yantar92/Git/emacs/src/emacs(+0x20e4cf)[0x5555557624cf]
/home/yantar92/Git/emacs/src/emacs(+0x2109c7)[0x5555557649c7]
/home/yantar92/Git/emacs/src/emacs(+0x20e4df)[0x5555557624df]
/home/yantar92/Git/emacs/src/emacs(+0x20e8ed)[0x5555557628ed]
/home/yantar92/Git/emacs/src/emacs(+0x20e3f2)[0x5555557623f2]
...

Thread 1 "emacs" received signal SIGABRT, Aborted.
0x00007ffff5172eac in ?? () from /lib64/libc.so.6

-- 
Ihor Radchenko,
Org mode contributor,
Learn more about Org mode at https://orgmode.org/.
Support Org development at https://liberapay.com/org-mode,
or support my work at https://liberapay.com/yantar92

Re: noverlay branch

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@gmail.com>
> Cc: monnier@iro.umontreal.ca,  emacs-devel@gnu.org
> Date: Mon, 26 Sep 2022 21:08:02 +0800
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > A backtrace from an optimized build can also be of help.  It is
> > certainly better than nothing.
> 
> (the other attempt with unoptimized build was using
> ./configure --enable-checking='yes,glyphs' --enable-check-lisp-object-type CFLAGS='-O0 -g3' --without-native-compilation)
> 
> Backtrace after ./configure && make bootstrap
> 
> I
> 1. Opened bunch of Org files
> 2. Generated agenda view (agenda creates a bunch of markers)
> 3. Ran helm-org-ql in an Org buffer. The results never arrived and once
>    I hit C-g to abort helm process, Emacs crashed.
> 
> Fatal error 6: Aborted
> Backtrace:
> /home/yantar92/Git/emacs/src/emacs(+0x19ec41)[0x5555556f2c41]
> /home/yantar92/Git/emacs/src/emacs(+0x4ae2c)[0x55555559ee2c]
> /home/yantar92/Git/emacs/src/emacs(+0x4b37f)[0x55555559f37f]
> /home/yantar92/Git/emacs/src/emacs(+0x517fa)[0x5555555a57fa]
> /home/yantar92/Git/emacs/src/emacs(+0x279cf2)[0x5555557cdcf2]
> /home/yantar92/Git/emacs/src/emacs(+0x2031a4)[0x5555557571a4]
> /home/yantar92/Git/emacs/src/emacs(+0x1c4819)[0x555555718819]
> /home/yantar92/Git/emacs/src/emacs(+0x2511b7)[0x5555557a51b7]
> /home/yantar92/Git/emacs/src/emacs(+0x20aae3)[0x55555575eae3]
> /home/yantar92/Git/emacs/src/emacs(+0x208f41)[0x55555575cf41]
> /home/yantar92/Git/emacs/src/emacs(+0x17d854)[0x5555556d1854]
> /home/yantar92/Git/emacs/src/emacs(+0x2094bc)[0x55555575d4bc]
> /home/yantar92/Git/emacs/src/emacs(+0x184213)[0x5555556d8213]
> /home/yantar92/Git/emacs/src/emacs(+0x191825)[0x5555556e5825]
> /home/yantar92/Git/emacs/src/emacs(+0x208ca7)[0x55555575cca7]
> /home/yantar92/Git/emacs/src/emacs(+0x17c6b6)[0x5555556d06b6]
> /home/yantar92/Git/emacs/src/emacs(+0x208c01)[0x55555575cc01]
> /home/yantar92/Git/emacs/src/emacs(+0x17c601)[0x5555556d0601]
> /home/yantar92/Git/emacs/src/emacs(+0x183a74)[0x5555556d7a74]
> /home/yantar92/Git/emacs/src/emacs(+0x1b6efb)[0x55555570aefb]
> /home/yantar92/Git/emacs/src/emacs(+0x20d58a)[0x55555576158a]
> /home/yantar92/Git/emacs/src/emacs(+0x2511b7)[0x5555557a51b7]
> /home/yantar92/Git/emacs/src/emacs(+0x20aae3)[0x55555575eae3]
> /home/yantar92/Git/emacs/src/emacs(+0x20ad08)[0x55555575ed08]
> /home/yantar92/Git/emacs/src/emacs(+0x2511b7)[0x5555557a51b7]
> /home/yantar92/Git/emacs/src/emacs(+0x20aae3)[0x55555575eae3]
> /home/yantar92/Git/emacs/src/emacs(+0x20ad08)[0x55555575ed08]
> /home/yantar92/Git/emacs/src/emacs(+0x2511b7)[0x5555557a51b7]
> /home/yantar92/Git/emacs/src/emacs(+0x20f897)[0x555555763897]
> /home/yantar92/Git/emacs/src/emacs(+0x20e2f6)[0x5555557622f6]
> /home/yantar92/Git/emacs/src/emacs(+0x20f465)[0x555555763465]
> /home/yantar92/Git/emacs/src/emacs(+0x20aae3)[0x55555575eae3]
> /home/yantar92/Git/emacs/src/emacs(+0x20644f)[0x55555575a44f]
> /home/yantar92/Git/emacs/src/emacs(+0x20aae3)[0x55555575eae3]
> /home/yantar92/Git/emacs/src/emacs(+0x20aeb8)[0x55555575eeb8]
> /home/yantar92/Git/emacs/src/emacs(+0x207d67)[0x55555575bd67]
> /home/yantar92/Git/emacs/src/emacs(+0x20e4cf)[0x5555557624cf]
> /home/yantar92/Git/emacs/src/emacs(+0x2109c7)[0x5555557649c7]
> /home/yantar92/Git/emacs/src/emacs(+0x20e4df)[0x5555557624df]
> /home/yantar92/Git/emacs/src/emacs(+0x20e8ed)[0x5555557628ed]
> /home/yantar92/Git/emacs/src/emacs(+0x20e3f2)[0x5555557623f2]

Thanks, but the above can only be interpreted on your machine.  So
either you can do this while running Emacs under GDB, and then post
the backtrace produced by GDB; or use the technique described in the
node "Crashing" of the Emacs user manual to convert the above
addresses to source file names and line numbers, and post the results
here.

FTR: Emacs didn't crash, it aborted (most probably due to an assertion
violation).

Re: noverlay branch

[Matt Armstrong]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> I just updated the noverlay branch to the code in `master` (most of it
> was mechanical except for the fact that since the last commit on that
> branch we have gotten rid of Lisp_Misc and we moved to pdumper).

This is pretty exciting!

I've been looking at the noverlay branch as well in some detail, but
only as a background task, over the past year.

I haven't considered the branch ready for merge because I saw some areas
where I think the implementation should improve.  But, working code is a
compelling thing.  If noverlay is ready to merge I'd suggest doing it.
Code can improve later, as and if needed.

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.

 2) Look at reducing the number of malloc'd overlay blocks in half by
    expressing the tree intrusively (the same way the overlay list is
    today).  I don't see a lot of value in itree.h/c abstracting away
    the interval logic from the overlay object itself.

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

And lower priority:

 4) The overlay `front-advance' and `rear-advance' booleans are
    conceptually part of the overlay's BEG and END positions, except
    that this is ignored everhwhere except insertion.  Upon insertion at
    any given POS the overlays are according to *both* their BEG or END
    positions and the *-advance booleans.  Yet, this is not used when
    ordering overlays in the tree.  Doing that may bring an opportunity
    to simplify code or make it more efficient.  (Side note: there *may*
    also be a way to encode the *-advance flags implicitly in the
    beg/end fields positions if a way can be found to "steal" the free
    bit in the currently signed ptrdiff_t fields, effectively causing
    the *-advance flags to count as this extra "half" position for the
    purpose of insertion).

 5) Look at using an augmented B-tree of overlays instead of a binary
    tree.  B-trees are quite often faster than binary trees (at least on
    hardware made over the past few decades), so there is that enticing
    proposition.  They're also typically not harder to implement,
    either, requiring no "rotations" nor convluted deletion logic.  An
    *augmented* B-tree may also allow for simplification of the relative
    vs. absolute offsets in the tree.  The noverlay branch currently
    handles this by treating the absolute offsets as cached values,
    "dirtying" them whenever any mutation occurs in the tree, and
    recomputing absolute offsets on demand.  If augmented in the right
    way a B-tree might be shallow enough in practice that recomputation
    on demand is always fast enough, so the the invalidation/caching
    approach (as well as the memory used to track it) can go away.
    (wild idea)

Re: noverlay branch

[Eli Zaretskii]

> From: Matt Armstrong <matt@rfc20.org>
> Date: Mon, 26 Sep 2022 22:12:44 -0700
> 
> Stefan Monnier <monnier@iro.umontreal.ca> writes:
> 
> > I just updated the noverlay branch to the code in `master` (most of it
> > was mechanical except for the fact that since the last commit on that
> > branch we have gotten rid of Lisp_Misc and we moved to pdumper).
> 
> This is pretty exciting!
> 
> I've been looking at the noverlay branch as well in some detail, but
> only as a background task, over the past year.
> 
> I haven't considered the branch ready for merge because I saw some areas
> where I think the implementation should improve.  But, working code is a
> compelling thing.  If noverlay is ready to merge I'd suggest doing it.
> Code can improve later, as and if needed.
> 
> 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.
> 
>  2) Look at reducing the number of malloc'd overlay blocks in half by
>     expressing the tree intrusively (the same way the overlay list is
>     today).  I don't see a lot of value in itree.h/c abstracting away
>     the interval logic from the overlay object itself.
> 
>  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).
> 
> And lower priority:
> 
>  4) The overlay `front-advance' and `rear-advance' booleans are
>     conceptually part of the overlay's BEG and END positions, except
>     that this is ignored everhwhere except insertion.  Upon insertion at
>     any given POS the overlays are according to *both* their BEG or END
>     positions and the *-advance booleans.  Yet, this is not used when
>     ordering overlays in the tree.  Doing that may bring an opportunity
>     to simplify code or make it more efficient.  (Side note: there *may*
>     also be a way to encode the *-advance flags implicitly in the
>     beg/end fields positions if a way can be found to "steal" the free
>     bit in the currently signed ptrdiff_t fields, effectively causing
>     the *-advance flags to count as this extra "half" position for the
>     purpose of insertion).
> 
>  5) Look at using an augmented B-tree of overlays instead of a binary
>     tree.  B-trees are quite often faster than binary trees (at least on
>     hardware made over the past few decades), so there is that enticing
>     proposition.  They're also typically not harder to implement,
>     either, requiring no "rotations" nor convluted deletion logic.  An
>     *augmented* B-tree may also allow for simplification of the relative
>     vs. absolute offsets in the tree.  The noverlay branch currently
>     handles this by treating the absolute offsets as cached values,
>     "dirtying" them whenever any mutation occurs in the tree, and
>     recomputing absolute offsets on demand.  If augmented in the right
>     way a B-tree might be shallow enough in practice that recomputation
>     on demand is always fast enough, so the the invalidation/caching
>     approach (as well as the memory used to track it) can go away.
>     (wild idea)

Thank you for your interest in this branch.

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.  Of the rest, item 1 sounds like the most important
one, but do you have ideas for how to achieve that?

Re: noverlay branch

[Gerd Möllmann]

Should we report bugs to bug-gnu-emacs?

And, should we fix things on the "noverlay" branch directly?  Or send 
patches?  It doesn't build on macOS, for instance, because that doesn't 
like the member named "nil" in struct interval.

Re: noverlay branch

[Eli Zaretskii]

> Date: Tue, 27 Sep 2022 10:39:22 +0200
> Cc: emacs-devel@gnu.org
> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> 
> Should we report bugs to bug-gnu-emacs?

Yes, please.  Just mention the branch.

> And, should we fix things on the "noverlay" branch directly?

Yes, please.

Thanks.

Re: noverlay branch

[Matt Armstrong]

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.

Re: noverlay branch

[Stefan Monnier]

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

Not only that.  It's an important end in itself.
Even if you don't know what the code does or why it does something,
writing it as a comment can be very useful (can help someone else, who
does understand the code, notice that it deserves an explanation).

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

I don't want to discourage you, but please do remember that we have
lived with a "ridiculously inefficient" implementation for the last 30
years or so, and that keeping two trees comes at a cost
(coding/maintenance cost + runtime cost + heapsize cost).


        Stefan

Re: noverlay branch

[Stefan Monnier]

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

I can explain the `visited` bit (and I added a comment about it in the
code).

What I'm less clear about is the use of the `null` sentinel node.
It seems that this node is sometimes modified (e.g. its color changed
from black to red or vice versa, and maybe also its `parent` field),
even though it's pointed to from lots of different nodes, so any help
documenting the way it works (or why the value in those fields doesn't
matter) would be welcome.


        Stefan

Re: noverlay branch

[Gerd Möllmann]

 > What I'm less clear about is the use of the `null` sentinel node.
 > It seems that this node is sometimes modified (e.g. its color changed
 > from black to red or vice versa, and maybe also its `parent` field),
 > even though it's pointed to from lots of different nodes, so any help
 > documenting the way it works (or why the value in those fields doesn't
 > matter) would be welcome.

Maybe I can say something because I used a similar trick in alloc.c. 
The gist of that was to make searching more elegant, and faster:

static struct mem_node *
mem_find (void *start)
{
   struct mem_node *p;

...

   /* Make the search always successful to speed up the loop below.  */
   mem_z.start = start;
   mem_z.end = (char *) start + 1;

   p = mem_root;
   while (start < p->start || start >= p->end)
     p = start < p->start ? p->left : p->right;
   return p;
}

If that's done for the same reason in itree.c, I don't know.  A hint 
that it is not, might be that each tree has a separated null node...

Re: noverlay branch

[Stefan Monnier]

> (the other attempt with unoptimized build was using
> ./configure --enable-checking='yes,glyphs' --enable-check-lisp-object-type
> CFLAGS='-O0 -g3' --without-native-compilation)
>
> Backtrace after ./configure && make bootstrap

While I don't know what your error may come from, we just fixed
a possible source of a "crash via abort", so there's a (slim) chance
that this is the bug you hit.

IOW you might like to try the new code on `feature/noverlay` to see if
it still suffers from your problem.


        Stefan

Re: noverlay branch

[Stefan Monnier]

>> What I'm less clear about is the use of the `null` sentinel node.
>> It seems that this node is sometimes modified (e.g. its color changed
>> from black to red or vice versa, and maybe also its `parent` field),
>> even though it's pointed to from lots of different nodes, so any help
>> documenting the way it works (or why the value in those fields doesn't
>> matter) would be welcome.
>
> Maybe I can say something because I used a similar trick in alloc.c.
> The gist of that was to make searching more elegant, and faster:
>
> static struct mem_node *
> mem_find (void *start)
> {
>   struct mem_node *p;
>
> ...
>
>   /* Make the search always successful to speed up the loop below.  */
>   mem_z.start = start;
>   mem_z.end = (char *) start + 1;
>
>   p = mem_root;
>   while (start < p->start || start >= p->end)
>     p = start < p->start ? p->left : p->right;
>   return p;
> }
>
> If that's done for the same reason in itree.c, I don't know.  A hint that it
> is not, might be that each tree has a separated null node...

OTOH there's a single mem tree, so in a sense you also have a separate
mem_nil node per tree :-)

I actually do understand the above use.  What I don't understand is code
such as:

    interval_tree_remove (struct interval_tree *tree, struct interval_node *node)
    {
      struct interval_node *broken = NULL;
      if (node->left == &tree->null || node->right == &tree->null)
        { ... }
      else
        {
          struct interval_node *min = interval_tree_subtree_min (tree, node->right);
          struct interval_node *min_right = min->right;
    
          if (!min->red)
            broken = min->right;
          if (min->parent == node)
            min_right->parent = min; /* set parent, if min_right = null */

where `min_right` on this last line can definitely be the null node (my
tests confirm it).
So what does it mean that we set the null nodes' `parent` field here?
How does it interact with other places where we use the `parent` field
(such as the last-but-one line where I confirmed that `min` can also be
the null node).
I don't see any place where we (re)set the null's `parent` field (other
than in `interval_tree_clear`)?  So it looks like this field is
"garbage" but not completely.


        Stefan

Re: noverlay branch

[Gerd Möllmann]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

W>> If that's done for the same reason in itree.c, I don't know.  A hint that it
>> is not, might be that each tree has a separated null node...
>
> OTOH there's a single mem tree, so in a sense you also have a separate
> mem_nil node per tree :-)

Hehe, true :-).

> I actually do understand the above use.  What I don't understand is code
> such as:
>
>     interval_tree_remove (struct interval_tree *tree, struct interval_node *node)
>     {
>       struct interval_node *broken = NULL;
>       if (node->left == &tree->null || node->right == &tree->null)
>         { ... }
>       else
>         {
>           struct interval_node *min = interval_tree_subtree_min (tree, node->right);
>           struct interval_node *min_right = min->right;
>     
>           if (!min->red)
>             broken = min->right;
>           if (min->parent == node)
>             min_right->parent = min; /* set parent, if min_right = null */
>
> where `min_right` on this last line can definitely be the null node (my
> tests confirm it).

Ok.

> So what does it mean that we set the null nodes' `parent` field here?
> How does it interact with other places where we use the `parent` field
> (such as the last-but-one line where I confirmed that `min` can also be
> the null node).

Yes, that's odd, but it should be harmless.  In general, walking the
tree should always stop at null, and not proceed with null itself.  So
null->parent shouldn't matter.

But it feels odd.  I don't remember other rb-tree implementations doing
that.  Maybe it's something special to Corman's implementation?
(Introduction to Algorithms was always quite expensive here, so I never
bought it).

Re: noverlay branch

[Matt Armstrong]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>>> What I'm less clear about is the use of the `null` sentinel node.
>>> It seems that this node is sometimes modified (e.g. its color changed
>>> from black to red or vice versa, and maybe also its `parent` field),
>>> even though it's pointed to from lots of different nodes, so any help
>>> documenting the way it works (or why the value in those fields doesn't
>>> matter) would be welcome.
>>
>> Maybe I can say something because I used a similar trick in alloc.c.
>> The gist of that was to make searching more elegant, and faster:
>>
>> static struct mem_node *
>> mem_find (void *start)
>> {
>>   struct mem_node *p;
>>
>> ...
>>
>>   /* Make the search always successful to speed up the loop below.  */
>>   mem_z.start = start;
>>   mem_z.end = (char *) start + 1;
>>
>>   p = mem_root;
>>   while (start < p->start || start >= p->end)
>>     p = start < p->start ? p->left : p->right;
>>   return p;
>> }
>>
>> If that's done for the same reason in itree.c, I don't know.  A hint that it
>> is not, might be that each tree has a separated null node...
>
> OTOH there's a single mem tree, so in a sense you also have a separate
> mem_nil node per tree :-)
>
> I actually do understand the above use.  What I don't understand is code
> such as:
>
>     interval_tree_remove (struct interval_tree *tree, struct interval_node *node)
>     {
>       struct interval_node *broken = NULL;
>       if (node->left == &tree->null || node->right == &tree->null)
>         { ... }
>       else
>         {
>           struct interval_node *min = interval_tree_subtree_min (tree, node->right);
>           struct interval_node *min_right = min->right;
>
>           if (!min->red)
>             broken = min->right;
>           if (min->parent == node)
>             min_right->parent = min; /* set parent, if min_right = null */
>
> where `min_right` on this last line can definitely be the null node (my
> tests confirm it).
> So what does it mean that we set the null nodes' `parent` field here?
> How does it interact with other places where we use the `parent` field
> (such as the last-but-one line where I confirmed that `min` can also be
> the null node).
> I don't see any place where we (re)set the null's `parent` field (other
> than in `interval_tree_clear`)?  So it looks like this field is
> "garbage" but not completely.

I see you removed some of the null->parent trick just today.  I like
that idea.  It is realtively easy to use actual NULL instead of a
sentinel NULL in tree algorithms, and I think on modern processors this
works out for the better.

Re: noverlay branch

[Gerd Möllmann]

On 22-10-06 6:47 , Matt Armstrong wrote:

> I see you removed some of the null->parent trick just today.  I like
> that idea.  It is realtively easy to use actual NULL instead of a
> sentinel NULL in tree algorithms, and I think on modern processors this
> works out for the better.

Clang libstd++ uses NULL, BTW, and I already wondered a little bit why.

Re: noverlay branch

[Stefan Monnier]

> I see you removed some of the null->parent trick just today.  I like
> that idea.  It is realtively easy to use actual NULL instead of a
> sentinel NULL in tree algorithms, and I think on modern processors this
> works out for the better.

The change I made only made it so the sentinel's fields are either
read-only or write-only, which means the sentinel is not used to
propagate information and is thus not a global state.

Whether using NULL is worse or better than using a sentinel, I don't
know, and I think the current code is fine in this respect.  If someone
wants to change it to use NULL, feel free, but it's not on my todo list.


        Stefan

Re: noverlay branch

[Matt Armstrong]

[-- Attachment #1: Type: text/plain, Size: 1392 bytes --]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> I just updated the noverlay branch to the code in `master` (most of it
> was mechanical except for the fact that since the last commit on that
> branch we have gotten rid of Lisp_Misc and we moved to pdumper).
>
> I'm getting ready to install this in `master`, so I'd encourage people
> to try this code as much as possible to try and weed out the most
> glaring problems before it hits master.  The code generally looks good,
> but it touches some quite "core" code in the redisplay (with lots of
> off-by-one opportunities) and in the memory management (with
> opportunities for crashes and memory leaks).
>
> For those who're not familiar with this branch, it changes the way
> overlays are stored in a buffer: instead of keeping them in naïve
> singly-linked lists, it keeps them in balanced binary trees, so as to
> replace an O(N) complexity with O(log N). This way Emacs should not get
> sluggish even with millions of overlays (of course, if a given buffer
> position is covered by a million overlays, it'll still be sluggish when
> operating around that position).
>
>
>         Stefan

Stefan, I don't have Emacs commit so I've attached comment improvement
patches here.  Lemme know if you'd prefer this occur on a bug.  These
commits are also on https://git.sr.ht/~matta/emacs/log/feature/noverlay


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-src-itree.h-include-lisp.h-for-Lisp_Object.patch --]
[-- Type: text/x-diff, Size: 951 bytes --]

From 6dff825a9943434cfccd64916c506ab10977acf8 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Thu, 6 Oct 2022 09:36:24 -0700
Subject: [PATCH 1/4] ; * src/itree.h: include "lisp.h" for Lisp_Object

---
 src/itree.c | 2 +-
 src/itree.h | 2 ++
 2 files changed, 3 insertions(+), 1 deletion(-)

diff --git a/src/itree.c b/src/itree.c
index ed31ef1156..a782410860 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -19,7 +19,7 @@ Copyright (C) 2017-2022  Free Software Foundation, Inc.
 
 #include <config.h>
 #include <math.h>
-#include "lisp.h"
+
 #include "itree.h"
 
 /*
diff --git a/src/itree.h b/src/itree.h
index 8f6bb667d6..9b79551f77 100644
--- a/src/itree.h
+++ b/src/itree.h
@@ -23,6 +23,8 @@ #define ITREE_H
 #include <stddef.h>
 #include <inttypes.h>
 
+#include "lisp.h"
+
 /* The tree and node structs are mainly here, so they can be allocated.
 
    NOTE: The only time where it is safe to modify node.begin and
-- 
2.35.1


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: 0002-src-itree.h-struct-interval_node-document-field-inva.patch --]
[-- Type: text/x-diff, Size: 3314 bytes --]

From 4048988f24c60104e6658b164a34df752f7b6167 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Thu, 6 Oct 2022 13:05:19 -0700
Subject: [PATCH 2/4] ; * src/itree.h (struct interval_node): document field
 invariants.

---
 src/itree.h | 58 ++++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 49 insertions(+), 9 deletions(-)

diff --git a/src/itree.h b/src/itree.h
index 9b79551f77..52219a8eef 100644
--- a/src/itree.h
+++ b/src/itree.h
@@ -25,22 +25,62 @@ #define ITREE_H
 
 #include "lisp.h"
 
-/* The tree and node structs are mainly here, so they can be allocated.
-
-   NOTE: The only time where it is safe to modify node.begin and
-   node.end directly, is while the node is not part of any tree.
-
-   NOTE: It is safe to read node.begin and node.end directly, if the
-   node came from a generator, because it validates the nodes it
-   returns as a side-effect.
-*/
+/* NOTE: the fields of the node and tree structs should for the most
+ * part be treated as opaque to the rest of Emacs.  Exceptions are
+ * noted in comments.  They are in the header file so they can be
+ * allocated.
+ */
 
 struct interval_node;
 struct interval_node
 {
+  /* The normal parent, left and right links found in binary trees.
+     See also `red`, below, which completes the Red-Black tree
+     representation.  */
   struct interval_node *parent;
   struct interval_node *left;
   struct interval_node *right;
+
+  /* The following five fields comprise the interval abstraction.
+
+     BEGIN, END are buffer positions.  BEGIN and END are the beginning
+     and end of this interval.  These form an inclusive, exlusive (or
+     closed, open) range of buffer positions [BEGIN..END).  When a
+     node is in a tree these fields are read only, written only by
+     itree functions.
+
+     The LIMIT, OFFSET and OTICK fields should be considered internal
+     to itree.c and used only by itree functions.
+
+     LIMIT is a buffer position, the maximum of END of this node and
+     its children.  See itree.c for its use.
+
+     OFFSET is in buffer position units, and will be non-zero only
+     when the node is dirty.
+
+     OTICK determines whether BEGIN, END, LIMIT and OFFSET are
+     considered dirty.  A node is clean when its OTICK is equal to the
+     OTICK of its tree (see struct interval_tree).  Otherwise, it is
+     dirty.
+
+     In a clean node, BEGIN, END and LIMIT are correct buffer
+     positions, and OFFSET is zero.  The parent of a clean node is
+     clean also clean, recursively.
+
+     In a dirty node, the node's OTICK won't equal its tree's OTICK,
+     and its OFFSET may be non-zero.  At all times the descendents of
+     a dirty node are also dirty.  BEGIN, END and LIMIT require
+     adjustment before use as buffer positions.
+
+     NOTE: BEGIN and END must not be modified while the node is part
+     of a tree.  Use interval_tree_insert_gap and
+     interval_tree_delete_gap instead.
+
+     NOTE: The interval generators ensure nodes are clean before
+     yielding them, so BEGIN and END may be safely used as buffer
+     positions then.
+  */
+
   ptrdiff_t begin;		/* The beginning of this interval. */
   ptrdiff_t end;		/* The end of the interval. */
   ptrdiff_t limit;		/* The maximum end in this subtree. */
-- 
2.35.1


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #4: 0003-src-itree.c-change-comments-for-clarity.patch --]
[-- Type: text/x-diff, Size: 2513 bytes --]

From 52470aa06f5f037358d957271101b8dbaa3f44e7 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Thu, 6 Oct 2022 13:12:54 -0700
Subject: [PATCH 3/4] ; * src/itree.c: change comments for clarity.

---
 src/itree.c | 18 +++++++++---------
 1 file changed, 9 insertions(+), 9 deletions(-)

diff --git a/src/itree.c b/src/itree.c
index a782410860..3098fe1cf4 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -24,7 +24,7 @@ Copyright (C) 2017-2022  Free Software Foundation, Inc.
 
 /*
    Intervals of the form [BEGIN, END), are stored as nodes inside a RB
-   tree, sorted by BEGIN .  The core operation of this tree (besides
+   tree, ordered by BEGIN.  The core operation of this tree (besides
    insert, remove, etc.) is finding all intervals intersecting with
    some given interval.  In order to perform this operation
    efficiently, every node stores a third value called LIMIT. (See
@@ -65,10 +65,10 @@ Copyright (C) 2017-2022  Free Software Foundation, Inc.
    ==== Adjusting intervals ====
 
    Since this data-structure will be used for overlays in an Emacs
-   buffer, a second core operation implements the ability to insert or
-   delete gaps in resp. from the tree.  This models the insertion
-   resp. deletion of text in a buffer and the effects it may have on
-   the positions of overlays.
+   buffer, a second core operation is the ability to insert and delete
+   gaps in the tree.  This models the insertion and deletion of text
+   in a buffer and the effects it may have on the positions of
+   overlays.
 
    Consider this: Something gets inserted at position P into a buffer
    and assume that all overlays occur strictly after P.  Ordinarily,
@@ -79,10 +79,10 @@ Copyright (C) 2017-2022  Free Software Foundation, Inc.
 
    The OFFSET of some some subtree, represented by its root, is the
    amount of shift that needs to be applied to its BEGIN, END and
-   LIMIT values, in order to get to the real values.  Coming back to
-   the example, all we would need to do in this case, is to increment
-   the OFFSET of the tree's root, without any traversal of the tree
-   itself.
+   LIMIT values, in order to get to the actual buffer positions.
+   Coming back to the example, all we would need to do in this case,
+   is to increment the OFFSET of the tree's root, without any
+   traversal of the tree itself.
 
    As a consequence, the real values of BEGIN, END and LIMIT of some
    NODE need to be computed by incrementing them by the sum of NODE's
-- 
2.35.1


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #5: 0004-Use-a-bool-instead-of-a-bitfield.patch --]
[-- Type: text/x-diff, Size: 744 bytes --]

From 53238b6c16f4dc3dec8d60205e88f5f79200d187 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Thu, 6 Oct 2022 13:18:46 -0700
Subject: [PATCH 4/4] Use a bool instead of a bitfield

* src/itree.c (struct interval_generator): use a bool instead of a
bitfield, since space is not an issue.
---
 src/itree.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/src/itree.c b/src/itree.c
index 3098fe1cf4..79e39d6e2a 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -145,7 +145,7 @@ null_is_sane (void)
   ptrdiff_t end;
   uintmax_t otick;              /* A copy of the tree's `otick`.  */
   enum interval_tree_order order;
-  bool_bf running : 1;
+  bool running;
   const char* file;
   int line;
 };
-- 
2.35.1

Re: noverlay branch

[Matt Armstrong]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

> On 22-10-06 6:47 , Matt Armstrong wrote:
>
>> I see you removed some of the null->parent trick just today.  I like
>> that idea.  It is realtively easy to use actual NULL instead of a
>> sentinel NULL in tree algorithms, and I think on modern processors this
>> works out for the better.
>
> Clang libstd++ uses NULL, BTW, and I already wondered a little bit why.

I believe GNU libstdc++ does not use sentinel nodes either.  I have yet
to see see sentinel nodes used in an optimized tree implementation.

I think in the context of this overlay work the performance difference
is not very significant, since the code is doing a lot of other stuff
while traversing the tree.

Re: noverlay branch

[Gerd Möllmann]

Matt Armstrong <matt@rfc20.org> writes:

>> Clang libstd++ uses NULL, BTW, and I already wondered a little bit why.
>
> I believe GNU libstdc++ does not use sentinel nodes either.  I have yet
> to see see sentinel nodes used in an optimized tree implementation.

I looked it up a few days ago, out of interest, and GCC's rb-tree uses
sentinels, in Git master at least.  Somewhere in this thread I posted
where to look in GCC's Git repo, I can't remember ATM.

(And I can't stop saying that it would be a big step forward for Emacs
to allow C++.  With std::multimap/std::multiset, we would have a
ready-made complete solution for the tree, tested by a gazillion of
users.  Just dreaming :-))

> I think in the context of this overlay work the performance difference
> is not very significant, since the code is doing a lot of other stuff
> while traversing the tree.

I agree.  I think NULL could be better in multi-threaded cases, as
Stefan alluded to.

Re: noverlay branch

[Stefan Monnier]

> to allow C++.  With std::multimap/std::multiset, we would have a
> ready-made complete solution for the tree, tested by a gazillion of
> users.  Just dreaming :-))

I'm not familiar with C++ libs: does this `multiset` lib offer something
similar to the lazy update of buffer positions that Andreas's code uses
(via the `offset` field together with the `interval_tree_inherit_offset`
function)?

>> I think in the context of this overlay work the performance difference
>> is not very significant, since the code is doing a lot of other stuff
>> while traversing the tree.
> I agree.  I think NULL could be better in multi-threaded cases, as
> Stefan alluded to.

The current code should be multi-thread safe (except for the global
iterator, of course), despite its use of a global sentinel node: there's
no need to synchronize anything when reading a read-only field or when
writing a write-only field.


        Stefan

Re: noverlay branch

[Gerd Möllmann]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> to allow C++.  With std::multimap/std::multiset, we would have a
>> ready-made complete solution for the tree, tested by a gazillion of
>> users.  Just dreaming :-))
>
> I'm not familiar with C++ libs: does this `multiset` lib offer something
> similar to the lazy update of buffer positions that Andreas's code uses
> (via the `offset` field together with the `interval_tree_inherit_offset`
> function)?

No, just the tree-part, or better said not the tree directly.  These
implement an abstraction of an ordered set, or multiset (containing an
element more than once), or map of (key, value) pairs, or multimap
(multiple (key, value) pairs with the same key.

Because of the complexities that the C++ standard guarantees, libstc++
uses rb-trees for the implmentation.  There are also unordered forms of
these concepts, using hash-tables under the hood.

https://cplusplus.com/reference/stl/

The rest would have to be built on top, using that.
std::multimap::iterator for example, would be an in-order iteration over
the key or (key, value) pairs.  C++ iterators are modelled after
pointers (++, --, *).

And there are a number of algorithms defined in C++ like lower_bound,
equal_range, upper_bound and so on that work on pointer-like iterators,
or real C pointers for that matter.

https://en.cppreference.com/w/cpp/algorithm

That's probably not a good explanation, sorry :-/.

Re: noverlay branch

[Stefan Monnier]

>>> to allow C++.  With std::multimap/std::multiset, we would have a
>>> ready-made complete solution for the tree, tested by a gazillion of
>>> users.  Just dreaming :-))
>>
>> I'm not familiar with C++ libs: does this `multiset` lib offer something
>> similar to the lazy update of buffer positions that Andreas's code uses
>> (via the `offset` field together with the `interval_tree_inherit_offset`
>> function)?
>
> No, just the tree-part, or better said not the tree directly.  These
> implement an abstraction of an ordered set, or multiset (containing an
> element more than once), or map of (key, value) pairs, or multimap
> (multiple (key, value) pairs with the same key.

Then I don't see how it would be a "ready-made complete solution"
because it doesn't seem easy to make such updates lazily "from the
outside".


        Stefan

Re: noverlay branch

[Stefan Monnier]

>>> I think in the context of this overlay work the performance difference
>>> is not very significant, since the code is doing a lot of other stuff
>>> while traversing the tree.
>> I agree.  I think NULL could be better in multi-threaded cases, as
>> Stefan alluded to.
>
> The current code should be multi-thread safe (except for the global
> iterator, of course), despite its use of a global sentinel node: there's
> no need to synchronize anything when reading a read-only field or when
> writing a write-only field.

But indeed, while it might be safe, its performance in a multi-threaded
situation (with multiple cores) might be affected, because of the
cache-line granularity and because the CPUs can't know that those writes
can be reordered (or even thrown away) since they will never be matched
by a corresponding read.


        Stefan

Re: noverlay branch

[Gerd Möllmann]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> Then I don't see how it would be a "ready-made complete solution"
> because it doesn't seem easy to make such updates lazily "from the
> outside".

I was anwering the context of the whole thread on the bug list, which
partly landed on emacs-devel.  Where "tree" meant what we talked about
implementing a successor function instead of a stateful stack that was
being used at the time, and so on, and so on.

Whatever.

Re: noverlay branch

[Matt Armstrong]

Gerd Möllmann <gerd.moellmann@gmail.com> writes:

> Matt Armstrong <matt@rfc20.org> writes:
>
>>> Clang libstd++ uses NULL, BTW, and I already wondered a little bit why.
>>
>> I believe GNU libstdc++ does not use sentinel nodes either.  I have yet
>> to see see sentinel nodes used in an optimized tree implementation.
>
> I looked it up a few days ago, out of interest, and GCC's rb-tree uses
> sentinels, in Git master at least.  Somewhere in this thread I posted
> where to look in GCC's Git repo, I can't remember ATM.

It uses a sentinel for the parent of the root node (a "header") but it
does not use a sentinel node for null at the leaves.  The easiest way to
see it is by looking at the code for GNU libstdc++ "minimum()" algorithm
on trees, which walks left ponters down to a leaf node:

https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=libstdc%2B%2B-v3/include/bits/stl_tree.h;h=a4de61417652a288e361a55fcc8bb7a9838c58a5;hb=HEAD#l112
    _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
    {
      while (__x->_M_left != 0) __x = __x->_M_left;
      return __x;
    }

For the header node, see
https://gcc.gnu.org/git?p=gcc.git;a=blob;f=libstdc%2B%2B-v3/include/bits/stl_tree.h;h=a4de61417652a288e361a55fcc8bb7a9838c58a5;hb=HEAD#l89

Re: noverlay branch

[Matt Armstrong]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> to allow C++.  With std::multimap/std::multiset, we would have a
>> ready-made complete solution for the tree, tested by a gazillion of
>> users.  Just dreaming :-))
>
> I'm not familiar with C++ libs: does this `multiset` lib offer something
> similar to the lazy update of buffer positions that Andreas's code uses
> (via the `offset` field together with the `interval_tree_inherit_offset`
> function)?

The ordered collections in the C++ standard library do not support
augmentation.  User code isn't allowed to see the left, right, parent
pointers, for example, nor are there "hooks" that allow running user
code as the tree is traversed or modified.  The "treeness" of the
collection is abstracted away entirely.

The kind of augmentation used by noverly is quite bespoke, and I think
it justifies a bespoke implementation.  It is "augmented" both bottom up
(the LIMIT field) and top down (the OFFSET field), and requires specific
handling of each.

There are enticing features in C++, but I don't think an off-the-shelf
solution to the overlay problem, suitable for use in Emacs
(e.g. licensing), is one of them.

I like C++ quite a lot, and have decades of using it professionally, but
I'd still be very cautious using it in Emacs.  For one, Emacs aims to
support all sorts of relatively obscure compilers on little used
platforms.  C++ tends to reduce what a program is portable to, though
admitedly it is much more portable in practice than most "modern"
programming languages.


>>> I think in the context of this overlay work the performance difference
>>> is not very significant, since the code is doing a lot of other stuff
>>> while traversing the tree.
>> I agree.  I think NULL could be better in multi-threaded cases, as
>> Stefan alluded to.
>
> The current code should be multi-thread safe (except for the global
> iterator, of course), despite its use of a global sentinel node: there's
> no need to synchronize anything when reading a read-only field or when
> writing a write-only field.

Pedantically, read-only fields do need synchronization with respect to
previous writers.  As for writing, you do need synchronization of writes
to avoid undefined behavior.  The memory model doesn't allow for
unsynchronized writes.

Anyway, neither is happening here.

If this global sentinel node is never modified then it isn't ever used,
so there can't be a synchronization problem!  It is just there to
generate a unique constant address that the tree code uses as a "null"
value without actually using NULL.  I think it is unusual and
unecessary, but it is thread safe.

Re: noverlay branch

[Matt Armstrong]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> I just updated the noverlay branch to the code in `master` (most of it
> was mechanical except for the fact that since the last commit on that
> branch we have gotten rid of Lisp_Misc and we moved to pdumper).
>
> I'm getting ready to install this in `master`, so I'd encourage people
> to try this code as much as possible to try and weed out the most
> glaring problems before it hits master.

Stefan (and others), where are we at with this?  Are there things that
must happen before a merge?

Is anybody able to use the noverlay branch for daily work?

I'm running the noverlay branch now and was observing an eassume
failure.  I recompiled without optimization and with Address Sanitizer
and ran Emacs under GDB, but haven't seen the crash since...  No crashes
so far, despite doing substantially the same things.  I am hoping it is
not an opt only bug.  If I isolate anything concrete I'll file a bug.

Re: noverlay branch

[Stefan Monnier]

Gerd Möllmann [2022-10-07 17:12:04] wrote:
> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> Then I don't see how it would be a "ready-made complete solution"
>> because it doesn't seem easy to make such updates lazily "from the
>> outside".
>
> I was anwering the context of the whole thread on the bug list, which
> partly landed on emacs-devel.  Where "tree" meant what we talked about
> implementing a successor function instead of a stateful stack that was
> being used at the time, and so on, and so on.

Ah, duh, sorry,


        Stefan

Re: noverlay branch

[Stefan Monnier]

Matt Armstrong [2022-10-07 09:51:32] wrote:
> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> I just updated the noverlay branch to the code in `master` (most of it
>> was mechanical except for the fact that since the last commit on that
>> branch we have gotten rid of Lisp_Misc and we moved to pdumper).
>>
>> I'm getting ready to install this in `master`, so I'd encourage people
>> to try this code as much as possible to try and weed out the most
>> glaring problems before it hits master.
>
> Stefan (and others), where are we at with this?  Are there things that
> must happen before a merge?

I'm mainly waiting to hear feedback (including my own) about "I use it
with no visible problem".

> Is anybody able to use the noverlay branch for daily work?

I do.

> I'm running the noverlay branch now and was observing an eassume
> failure.

Do you have the file&line number at least?

> I recompiled without optimization and with Address Sanitizer
> and ran Emacs under GDB, but haven't seen the crash since...

More important than that is the ENABLE_CHECKING (which you apparently
was using already anyway) and running under a debugger: even if
optimizations may throw GDB off a bit, it's usually good enough to make
progress on the bug (sometimes by adding more assertions or printfs to
make up (next time around) for the lack of info provided by GDB).


        Stefan

Re: noverlay branch

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@gmail.com>
> Cc: monnier@iro.umontreal.ca,  emacs-devel@gnu.org
> Date: Sat, 08 Oct 2022 10:36:28 +0800
> 
> There are a couple of glitches though:
> 1. hl-line-mode overlay sometimes disappear
> 2. notmuch search buffer hides text in wrong places (see the attached video)
> 
> Should I report these things as proper bugs or is it OK to discuss them
> within this thread?

Separate bug reports, please.  And please mention there that the bugs
pertain to the noverlay branch.  Thanks.

> Also, I did a small test comparing Org mode folding performance (using
> overlays) on master vs feature/noverlay branch using the methodology
> described in https://blog.tecosaur.com/tmio/2022-05-31-folding.html:
> 
> On large 20Mb Org file using built-in Org version:
> 
> master: Elapsed time: 142.940028s (1.428150s in 55 GCs)
> feature/noverlay: Elapsed time: 4.369854s (1.451378s in 74 GCs)
> 
> for comparison, the Org version from main yields:
> 
> Emacs master:
>  - main Org branch using text properties for folding: Elapsed time: 2.185786s (0.639190s in 4 GCs)
>  - main Org branch using overlays for folding: Elapsed time: 27.244284s (0.731581s in 5 GCs)
> 
> Emacs feature/noverlay:
>  - main Org branch using text properties for folding: Elapsed time: 1.586936s (0.476606s in 3 GCs)
>  - main Org branch using overlays for folding: Elapsed time: 2.039803s (0.724576s in 5 GCs)
> 
> The improvement is very significant.

Thanks, looks very encouraging.

> We also have tests for marker scaling. If the overlay tree
> implementation can be reused for markers, it would also be great.

Not in Emacs 29, I'm afraid.

Re: noverlay branch

[Matt Armstrong]

[-- Attachment #1: Type: text/plain, Size: 1541 bytes --]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> Matt Armstrong [2022-10-07 09:51:32] wrote:
>> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>>> I just updated the noverlay branch to the code in `master` (most of it
>>> was mechanical except for the fact that since the last commit on that
>>> branch we have gotten rid of Lisp_Misc and we moved to pdumper).
>>>
>>> I'm getting ready to install this in `master`, so I'd encourage people
>>> to try this code as much as possible to try and weed out the most
>>> glaring problems before it hits master.
>>
>> Stefan (and others), where are we at with this?  Are there things that
>> must happen before a merge?
>
> I'm mainly waiting to hear feedback (including my own) about "I use it
> with no visible problem".

I like that criteria.  :)

>> Is anybody able to use the noverlay branch for daily work?
>
> I do.
>
>> I'm running the noverlay branch now and was observing an eassume
>> failure.
>
> Do you have the file&line number at least?

Not the specific eassert because...reasons.  Long story short: I can
debug eassert failures now, but not then.

In any case, I do have a new test for tests/src/buffer-tests.el that
crashes feature/noverlay Emacs immediately, when ENABLE_CHECKING is on,
in a spot in itree.c having to do with offset inheritance.

Two patches, also on https://git.sr.ht/~matta/emacs/log/feature/noverlay
as before.  I'll work on fixing the crash next, but wanted to get the
test in because it takes an...interesting approach...that may require
discussion.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Comment-change-explain-inheriting-dirty-offsets.patch --]
[-- Type: text/x-diff, Size: 1510 bytes --]

From 87204feaa4f50744701481f3aa051483647cf9da Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Sat, 8 Oct 2022 09:15:26 -0700
Subject: [PATCH 1/2] Comment change: explain inheriting "dirty" offsets

; * src/itree.c (interval_generator_next): explain why the code
handles inheriting offsets from dirty nodes.
---
 src/itree.c | 14 +++++++++++---
 1 file changed, 11 insertions(+), 3 deletions(-)

diff --git a/src/itree.c b/src/itree.c
index de16af5b0c..1fc711b021 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -1086,9 +1086,17 @@ interval_tree_inherit_offset (uintmax_t otick, struct interval_node *node)
         node->right->offset += node->offset;
       node->offset = 0;
     }
-  /* FIXME: I wonder when/why this condition can be false, and more generally
-     why we'd want to propagate offsets that may not be fully up-to-date.  */
-  if (node->parent == ITREE_NULL || node->parent->otick == otick)
+  /* FIXME: I wonder when/why this condition can be false, and more
+     generally why we'd want to propagate offsets that may not be
+     fully up-to-date. --stef
+
+     Offsets can be inherited from dirty nodes (with out of date
+     otick) during insert and remove.  Offsets aren't inherited
+     downward from the root for these operations so rotations are
+     performed on potentially "dirty" nodes.  We could fix this by
+     always inheriting offsets downward from the root for every insert
+     and remove.  --matt
+  */
     node->otick = otick;
 }
 
-- 
2.35.1


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: 0002-test-src-buffer-tests.el-test-overlay-randomly-new-t.patch --]
[-- Type: text/x-diff, Size: 4982 bytes --]

From 89ed5cbee03cce6c621af6570d2c4411e7586f9d Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Sat, 8 Oct 2022 09:28:29 -0700
Subject: [PATCH 2/2] ; * test/src/buffer-tests.el (test-overlay-randomly): new
 test.

---
 test/src/buffer-tests.el | 92 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 92 insertions(+)

diff --git a/test/src/buffer-tests.el b/test/src/buffer-tests.el
index a12d15bc79..46e57289a1 100644
--- a/test/src/buffer-tests.el
+++ b/test/src/buffer-tests.el
@@ -1508,6 +1508,98 @@ test-overlay-multibyte-transition-2
         (ovshould nonempty-eob-end 4 5)
         (ovshould empty-eob        5 5)))))
 
+(ert-deftest test-overlay-randomly ()
+  "Exercise overlay code, but perform few assertions.
+
+This test works best when Emacs is configured with
+--enable-checking=yes.  This is a little bit like fuzz testing,
+except this test has no way to reduce to a minimal failng test
+case.  Regardless, by exercising many corner cases bugs can be
+found using Emacs' internal consistency assertions."
+  (let* (
+         ;; The size and slack for the test buffer size.
+         (buffer-size-target 1000)
+         (buffer-size-slack 200)
+
+         ;; Use up to 100 overlays.  We need not use more to observe
+         ;; reasonable variation in the overlay data structures.
+         (overlay-count-limit 100)
+
+         ;; This test maintains a vector of overlays.  Each iteration
+         ;; may append or erase one overlay.
+         (overlays (make-vector overlay-count-limit nil))
+         (overlay-count 0)
+
+         ;; The test is either slowly growing or shrinking the overlay
+         ;; count.  Deletions still occur while growing, and additions
+         ;; still occur while shrinking.  The GROWING variable only
+         ;; controls the relative probability of doing one or the
+         ;; other.
+         (growing t)
+
+         ;; Loop up to 100K times.
+         (iteration-count 0)
+         (iteration-target 100000))
+    (with-temp-buffer
+      (while (< (buffer-size) buffer-size-target)
+        (insert "Sed ut perspiciatis, unde omnis iste natus error sit voluptatem
+accusantium doloremque laudantium, totam rem aperiam eaque ipsa,
+quae ab illo inventore veritatis et quasi architecto beatae vitae
+dicta sunt, explicabo.  "))
+
+      (while (< iteration-count iteration-target)
+        (cl-incf iteration-count)
+
+        ;; Toggle GROWING if we've reached a size boundary.  The idea
+        ;; is to initially steadily increase the overlay count, then
+        ;; steadily decrease it, then repeat.
+        (when (and growing (= overlay-count overlay-count-limit))
+          (message "now shrinking")
+          (setq growing nil))
+        (when (and (not growing) (= overlay-count 0))
+          (message "now growing")
+          (setq growing t))
+
+        ;; Create or delete a random overlay according to a
+        ;; probability chosen by GROWING.
+        (let ((create-overlay (>= (random 100) (if growing 40 60))))
+          (cond
+           ;; Possibly create a new overlay in a random place in the
+           ;; buffer.  We have two easy choices.  We can choose the
+           ;; overlay BEGIN randomly, then choose its END among the
+           ;; valid remaining buffer posiitions.  Or we could choose
+           ;; the overlay width randomly, then choose a valid BEGIN.
+           ;; We take the former approach, because the overlay data
+           ;; structure is ordered primarily by BEGIN.
+           ((and create-overlay (< overlay-count overlay-count-limit))
+            (let* ((begin (random (buffer-size)))
+                   (end (+ begin (random (- (buffer-size) begin))))
+                   (ov (make-overlay begin end nil
+                                     (= 0 (random 2)) (= 0 (random 2)))))
+              (aset overlays overlay-count ov)
+              (cl-incf overlay-count)))
+           ((and (not create-overlay) (> overlay-count 0))
+
+            ;; Possibly delete a random overlay.
+            (let* ((last-index (1- overlay-count))
+                   (index (random overlay-count))
+                   (ov (aref overlays index)))
+              (when (< index last-index)
+                (aset overlays index (aref overlays last-index)))
+              (aset overlays last-index nil)
+              (cl-decf overlay-count)
+              (delete-overlay ov)))))
+
+        ;; Modify the buffer on occasion, which exercises the
+        ;; insert/remove gap logic in the overlay implementation.
+        (when (and (< (buffer-size) (+ buffer-size-target buffer-size-slack))
+                   (zerop (random 10)))
+          (goto-char (1+ (random (buffer-size))))
+          (insert (+ ?a (random 26))))
+        (when (and (> (buffer-size) (- buffer-size-target buffer-size-slack))
+                   (zerop (random 10)))
+          (goto-char (1+ (random (buffer-size))))
+          (delete-char 1))))))
 
 
 \f
-- 
2.35.1

Re: noverlay branch

[Matt Armstrong]

Ihor Radchenko <yantar92@gmail.com> writes:

> Update: I can no longer see crashes on the latest commit in the branch.
>
> I was able to use the branch with my config for while now, and it works
> mostly fine.
>
> There are a couple of glitches though:
> 1. hl-line-mode overlay sometimes disappear
> 2. notmuch search buffer hides text in wrong places (see the attached video)
>
> Should I report these things as proper bugs or is it OK to discuss them
> within this thread?

Hi Ihor, yes, your glitches (1) and (2) make sense to me, given some
fundamental bugs I have uncovered in noverlay branch.

In some not-yet-commited debug code I have against the noverlay branch I
am seeing binary tree invariants violated.  For example, overlay nodes
in a binary tree with BEGIN positions that are out of range for the
subtree they are in, potentially caused by them being offset
incorrectly.  The algorithms involved are quite fragile.  These bugs
would cause functions like overlays-at and overlays-in to potentially
miss overlays, as well as for BEGIN and/or END to be in incorrect
positions.  This would explain both scenarios you describe above.

Polishing off this new debug code and getting it commited, as well as
fixing the bugs, is what I'm working on.

Re: noverlay branch

[Matt Armstrong]

Eli Zaretskii <eliz@gnu.org> writes:

>> We also have tests for marker scaling. If the overlay tree
>> implementation can be reused for markers, it would also be great.
>
> Not in Emacs 29, I'm afraid.

Scalable markers will be *much* easier conceptually than overlays.  I
had this in mind for a post noverlay work.

Re: noverlay branch

[Matt Armstrong]

[-- Attachment #1: Type: text/plain, Size: 1684 bytes --]

Matt Armstrong <matt@rfc20.org> writes:

> From 87204feaa4f50744701481f3aa051483647cf9da Mon Sep 17 00:00:00 2001
> From: Matt Armstrong <matt@rfc20.org>
> Date: Sat, 8 Oct 2022 09:15:26 -0700
> Subject: [PATCH 1/2] Comment change: explain inheriting "dirty" offsets
>
> ; * src/itree.c (interval_generator_next): explain why the code
> handles inheriting offsets from dirty nodes.
> ---
>  src/itree.c | 14 +++++++++++---
>  1 file changed, 11 insertions(+), 3 deletions(-)
>
> diff --git a/src/itree.c b/src/itree.c
> index de16af5b0c..1fc711b021 100644
> --- a/src/itree.c
> +++ b/src/itree.c
> @@ -1086,9 +1086,17 @@ interval_tree_inherit_offset (uintmax_t otick, struct interval_node *node)
>          node->right->offset += node->offset;
>        node->offset = 0;
>      }
> -  /* FIXME: I wonder when/why this condition can be false, and more generally
> -     why we'd want to propagate offsets that may not be fully up-to-date.  */
> -  if (node->parent == ITREE_NULL || node->parent->otick == otick)
> +  /* FIXME: I wonder when/why this condition can be false, and more
> +     generally why we'd want to propagate offsets that may not be
> +     fully up-to-date. --stef
> +
> +     Offsets can be inherited from dirty nodes (with out of date
> +     otick) during insert and remove.  Offsets aren't inherited
> +     downward from the root for these operations so rotations are
> +     performed on potentially "dirty" nodes.  We could fix this by
> +     always inheriting offsets downward from the root for every insert
> +     and remove.  --matt
> +  */
>      node->otick = otick;
>  }

Correction to the above patch, where I inadvertently deleted a line of
code:


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Comment-change-explain-inheriting-dirty-offsets.patch --]
[-- Type: text/x-diff, Size: 1507 bytes --]

From 30f52202775155c1d301af3634d0122c3d7851f8 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Sat, 8 Oct 2022 09:15:26 -0700
Subject: [PATCH 1/3] Comment change: explain inheriting "dirty" offsets

; * src/itree.c (interval_generator_next): explain why the code
handles inheriting offsets from dirty nodes.
---
 src/itree.c | 13 +++++++++++--
 1 file changed, 11 insertions(+), 2 deletions(-)

diff --git a/src/itree.c b/src/itree.c
index de16af5b0c..05851007f5 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -1086,8 +1086,17 @@ interval_tree_inherit_offset (uintmax_t otick, struct interval_node *node)
         node->right->offset += node->offset;
       node->offset = 0;
     }
-  /* FIXME: I wonder when/why this condition can be false, and more generally
-     why we'd want to propagate offsets that may not be fully up-to-date.  */
+  /* FIXME: I wonder when/why this condition can be false, and more
+     generally why we'd want to propagate offsets that may not be
+     fully up-to-date. --stef
+
+     Offsets can be inherited from dirty nodes (with out of date
+     otick) during insert and remove.  Offsets aren't inherited
+     downward from the root for these operations so rotations are
+     performed on potentially "dirty" nodes.  We could fix this by
+     always inheriting offsets downward from the root for every insert
+     and remove.  --matt
+  */
   if (node->parent == ITREE_NULL || node->parent->otick == otick)
     node->otick = otick;
 }
-- 
2.35.1

Re: noverlay branch

[Stefan Monnier]

> Update: I can no longer see crashes on the latest commit in the branch.

Thanks for the update.

> There are a couple of glitches though:
> 1. hl-line-mode overlay sometimes disappear
> 2. notmuch search buffer hides text in wrong places (see the attached video)

Hmm... that's worrisome.

> Should I report these things as proper bugs or is it OK to discuss them
> within this thread?

As Eli said, bug-reports are best.  I don't read the bug-reports list,
so I'd appreciate if you can add me to the `X-Debbugs-Cc:` when you
report those bugs.

> Also, I did a small test comparing Org mode folding performance (using
> overlays) on master vs feature/noverlay branch using the methodology
> described in https://blog.tecosaur.com/tmio/2022-05-31-folding.html:

Very cool, thanks!

> We also have tests for marker scaling.  If the overlay tree
> implementation can be reused for markers, it would also be great.

That's definitely not on the current menu.  It's not out of the
question, but would require a fair bit more work and will come with
new tradeoffs.


        Stefan

Re: noverlay branch

[Stefan Monnier]

> In any case, I do have a new test for tests/src/buffer-tests.el that
> crashes feature/noverlay Emacs immediately, when ENABLE_CHECKING is on,
> in a spot in itree.c having to do with offset inheritance.

(Not?) great!

> Two patches, also on https://git.sr.ht/~matta/emacs/log/feature/noverlay
> as before.

Merged (along with another that you apparently pushed since).

> I'll work on fixing the crash next, but wanted to get the
> test in because it takes an...interesting approach...that may require
> discussion.

I'm fine with the random testing approach (I'd be happy to see something
like `propcheck` used in our testing rig).
Currently, our test suite is not really setup to test Emacs crashes
very well, so it's not ideal.  Still: better than nothing.

> @@ -1086,9 +1086,17 @@ interval_tree_inherit_offset (uintmax_t otick, struct interval_node *node)
>          node->right->offset += node->offset;
>        node->offset = 0;
>      }
> -  /* FIXME: I wonder when/why this condition can be false, and more generally
> -     why we'd want to propagate offsets that may not be fully up-to-date.  */
> -  if (node->parent == ITREE_NULL || node->parent->otick == otick)
> +  /* FIXME: I wonder when/why this condition can be false, and more
> +     generally why we'd want to propagate offsets that may not be
> +     fully up-to-date. --stef
> +
> +     Offsets can be inherited from dirty nodes (with out of date
> +     otick) during insert and remove.  Offsets aren't inherited
> +     downward from the root for these operations so rotations are
> +     performed on potentially "dirty" nodes.  We could fix this by
> +     always inheriting offsets downward from the root for every insert
> +     and remove.  --matt
> +  */
>      node->otick = otick;
>  }

Indeed, I saw later in the remove code that we do propagate offsets
without caring if they're up-to-date, and I think the logic behind that
is sound.  And indeed we can drop the test because the only property we
only ever care about for an `otick` is whether it's equal to
`tree->otick`, so if node->parent->otick != otick then performing the
assignment is equivalent to not performing it.


        Stefan

Re: noverlay branch

[Eli Zaretskii]

> From: Matt Armstrong <matt@rfc20.org>
> Cc: monnier@iro.umontreal.ca, emacs-devel@gnu.org
> Date: Sat, 08 Oct 2022 20:25:45 -0700
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> We also have tests for marker scaling. If the overlay tree
> >> implementation can be reused for markers, it would also be great.
> >
> > Not in Emacs 29, I'm afraid.
> 
> Scalable markers will be *much* easier conceptually than overlays.  I
> had this in mind for a post noverlay work.

I didn't say they were complicated.

Re: noverlay branch

[Stefan Monnier]

>>      node->otick = otick;
>
> Indeed, I saw later in the remove code that we do propagate offsets
> without caring if they're up-to-date, and I think the logic behind that
> is sound.  And indeed we can drop the test because the only property we
> only ever care about for an `otick` is whether it's equal to
> `tree->otick`, so if node->parent->otick != otick then performing the
> assignment is equivalent to not performing it.

The above isn't quite right:
I was thinking of `node->otick = parent->otick`.


        Stefan

Re: noverlay branch

[Stefan Monnier]

> In any case, I do have a new test for tests/src/buffer-tests.el that
> crashes feature/noverlay Emacs immediately, when ENABLE_CHECKING is on,
> in a spot in itree.c having to do with offset inheritance.

I tightened up a few things and the code now passes the tests without
crashing any more.


        Stefan

Re: noverlay branch

[Emanuel Berg]

Stefan Monnier wrote:

>> In any case, I do have a new test for
>> tests/src/buffer-tests.el that crashes feature/noverlay
>> Emacs immediately, when ENABLE_CHECKING is on, in a spot in
>> itree.c having to do with offset inheritance.
>
> I tightened up a few things and the code now passes the
> tests without crashing any more.

I know only of the byte-compiler and checkdoc

  https://dataswamp.org/~incal/emacs-init/ide/pack-style.el

If you have something more I want it please :)

If we talk Elisp in general ...

-- 
underground experts united
https://dataswamp.org/~incal

Re: noverlay branch

[Matt Armstrong]

[-- Attachment #1: Type: text/plain, Size: 1809 bytes --]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>>>      node->otick = otick;
>>
>> Indeed, I saw later in the remove code that we do propagate offsets
>> without caring if they're up-to-date, and I think the logic behind that
>> is sound.  And indeed we can drop the test because the only property we
>> only ever care about for an `otick` is whether it's equal to
>> `tree->otick`, so if node->parent->otick != otick then performing the
>> assignment is equivalent to not performing it.
>
> The above isn't quite right:
> I was thinking of `node->otick = parent->otick`.

Hey Stefan, yep, I'll have to check out the changes you made today.

I had a different idea of tightening the otree invariant to this:

 1) A node's otick must be greater than or equal to its children's.
 2) There is no tree->otick, just tree->root->otick.  That is what is
    incremented when offsets are added.
 3) All downward tree traversal propagates offsets and otick.

This strikes me as conceptually simpler.  E.g. since the invariant is
defined recursively it might allow for more local reasoning, clearer
assertions, less places where "offset math" is needed, etc.  But you've
lived in this code a bit longer than me.  What do you think?  I have a
commit halfway worked up so maybe I can show that if it works out...

Anyway, thanks for fixing my "thinko" bug in the check_tree code -- I
had the fix but should have sent it faster.  I didn't actually intend
for that to be commited yet (pushed it to sr.ht by accident), but maybe
it helped you chase down the bugs you fixed today?

I have two patches, mostly to add more checks to the invariant checking
in check_tree.  Tests on noverlay are passing again as of your commits
today, which is great!

On https://git.sr.ht/~matta/emacs/log/feature/noverlay but also below.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-test-src-buffer-tests.el-Remove-unecessary-message-c.patch --]
[-- Type: text/x-diff, Size: 958 bytes --]

From 246acbddbeb3e9a390fe78242259182af0c2cc18 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Sun, 9 Oct 2022 10:12:32 -0700
Subject: [PATCH 1/2] ; * test/src/buffer-tests.el: Remove unecessary `message'
 calls.

---
 test/src/buffer-tests.el | 2 --
 1 file changed, 2 deletions(-)

diff --git a/test/src/buffer-tests.el b/test/src/buffer-tests.el
index 01780a15cc..9bccbdf2e8 100644
--- a/test/src/buffer-tests.el
+++ b/test/src/buffer-tests.el
@@ -1554,10 +1554,8 @@ test-overlay-randomly
         ;; is to initially steadily increase the overlay count, then
         ;; steadily decrease it, then repeat.
         (when (and growing (= overlay-count overlay-count-limit))
-          (message "now shrinking")
           (setq growing nil))
         (when (and (not growing) (= overlay-count 0))
-          (message "now growing")
           (setq growing t))
 
         ;; Create or delete a random overlay according to a
-- 
2.35.1


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: 0002-Add-.-configure-enable-checking-overlays.patch --]
[-- Type: text/x-diff, Size: 9911 bytes --]

From 1d40c60265c34caaf9d8f5ad0c66322e7281902d Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Sun, 9 Oct 2022 19:42:14 -0700
Subject: [PATCH 2/2] Add ./configure --enable-checking=overlays

This enables expensive validation checks of overlay data structures.
Some are too expensive to turn on by default with
--enable-checking=all since they turn O(log N) algorithms into O(N)
algorithms.

* src/itree.c (ENABLE_OVERLAY_CHECKING): define to 0 if undefined.
(struct check_subtree_result): new struct.
(check_subtree): renamed from recurse_check_tree, modified to use
check_subtree_result and check more invariants.
(check_tree): use check_subtree_result.
* configure.ac: add support for ENABLE_OVERLAY_CHECKING.
---
 configure.ac |  11 +++-
 src/itree.c  | 164 +++++++++++++++++++++++++++++++++++++++++++--------
 2 files changed, 148 insertions(+), 27 deletions(-)

diff --git a/configure.ac b/configure.ac
index 8ba52a492b..42a55c7572 100644
--- a/configure.ac
+++ b/configure.ac
@@ -582,7 +582,7 @@ AC_DEFUN
 		 enable only specific categories of checks.
 		 Categories are: all,yes,no.
 		 Flags are: stringbytes, stringoverrun, stringfreelist,
-		 structs, glyphs])],
+		 structs, glyphs, overlays])],
 [ac_checking_flags="${enableval}"],[])
 IFS="${IFS= 	}"; ac_save_IFS="$IFS"; IFS="$IFS,"
 CHECK_STRUCTS=false
@@ -596,7 +596,8 @@ AC_DEFUN
 			ac_gc_check_stringbytes= ;
 	                ac_gc_check_string_overrun= ;
 	                ac_gc_check_string_free_list= ;
-			ac_glyphs_debug= ;;
+			ac_glyphs_debug= ;
+			ac_enable_overlay_checking= ;;
 	all)		ac_enable_checking=1 ;
 			CHECK_STRUCTS=true
 			ac_gc_check_stringbytes=1 ;
@@ -609,6 +610,7 @@ AC_DEFUN
 	stringfreelist) ac_gc_check_string_free_list=1 ;;
 	structs)	CHECK_STRUCTS=true ;;
 	glyphs)		ac_glyphs_debug=1 ;;
+	overlays)	ac_enable_overlay_checking=1 ;;
 	*)	AC_MSG_ERROR([unknown check category $check]) ;;
 	esac
 done
@@ -645,6 +647,11 @@ AC_DEFUN
   AC_DEFINE([GLYPH_DEBUG], [1],
 [Define this to enable glyphs debugging code.])
 fi
+if test x$ac_enable_overlay_checking != x ; then
+  AC_DEFINE([ENABLE_OVERLAY_CHECKING], [1],
+[Define this temporarily to hunt a bug.  If defined, expensive
+   invariant checking of the overlay data structures is enabled.])
+fi
 
 dnl The name of this option is unfortunate.  It predates, and has no
 dnl relation to, the "sampling-based elisp profiler" added in 24.3.
diff --git a/src/itree.c b/src/itree.c
index bbab70dac7..31a7e01090 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -144,6 +144,10 @@ Copyright (C) 2017-2022  Free Software Foundation, Inc.
 static struct interval_generator* interval_generator_create (struct interval_tree *);
 static void interval_tree_insert (struct interval_tree *, struct interval_node *);
 
+#ifndef ENABLE_OVERLAY_CHECKING
+#define ENABLE_OVERLAY_CHECKING 0
+#endif
+
 /* The sentinel node, the null node.  */
 struct interval_node itree_null;
 
@@ -205,14 +209,44 @@ itree_init (void)
   iter = interval_generator_create (NULL);
 }
 
-static ptrdiff_t
-recurse_check_tree (struct interval_node *node, uintmax_t tree_otick,
-                    ptrdiff_t offset, ptrdiff_t min_begin,
-                    ptrdiff_t max_begin, intmax_t *size)
+struct check_subtree_result
+{
+  /* Were all nodes visited?  */
+  bool complete;
+
+  /* Computed node count of the tree.  */
+  int size;
+
+  /* Computed limit of the tree (max END).  */
+  ptrdiff_t limit;
+
+  /* Computed black height of the tree (count of black nodes from the
+     bottom up to the root).  */
+  int black_height;
+};
+
+static struct check_subtree_result
+check_subtree (struct interval_node *node, uintmax_t tree_otick,
+               int max_depth, ptrdiff_t offset, ptrdiff_t min_begin,
+               ptrdiff_t max_begin)
 {
+  struct check_subtree_result result = { .complete = false,
+                                         .size = 0,
+                                         .limit = PTRDIFF_MIN,
+                                         .black_height = 0 };
   if (node == ITREE_NULL)
-    return PTRDIFF_MIN;
-  ++*size;
+    {
+      /* Every nil node of a Red-Black tree is black */
+      result.black_height = 1;
+      result.complete = true;
+      return result;
+    };
+
+  if (max_depth == 0)
+    {
+      result.complete = false;
+      return result;
+    }
 
   /* Validate structure.  */
   eassert (
@@ -221,12 +255,23 @@ recurse_check_tree (struct interval_node *node, uintmax_t tree_otick,
   eassert (node->left == ITREE_NULL || node->left->parent == node);
   eassert (node->right == ITREE_NULL || node->right->parent == node);
 
-  /* We don't check the RB invariants here (neither the absence of
-     red+red nor the equal-black-depth), so that we can use this check
-     even while the tree is temporarily breaking some of those invarints.  */
-  /* Red nodes cannot have red parents.  */
-  /* eassert (node->parent == ITREE_NULL
-              || !(node->red && node->parent->red)); */
+  /* We don't normally check the RB invariants here (neither the
+     absence of red+red nor the equal-black-depth), so that we can use
+     this check even while the tree is temporarily breaking some of
+     those invarints.  You can enable them if you want.  */
+  if (false)
+    {
+      /* If a node is red then both of its children are black.  Red
+         nodes cannot have red parents.  */
+      if (node->red)
+        {
+          eassert (node->left == ITREE_NULL
+                   || node->left->red == false);
+          eassert (node->right == ITREE_NULL
+                   || node->right->red == false);
+          eassert (node->parent == ITREE_NULL || !node->parent->red);
+        }
+    }
 
   eassert (node->offset == 0 || node->otick < tree_otick);
 
@@ -240,18 +285,44 @@ recurse_check_tree (struct interval_node *node, uintmax_t tree_otick,
   eassert (begin <= max_begin);
   eassert (end <= limit);
 
-  ptrdiff_t left_limit
-    = recurse_check_tree (node->left, tree_otick, offset, min_begin,
-                          begin, size);
-  ptrdiff_t right_limit
-    = recurse_check_tree (node->right, tree_otick, offset, begin,
-                          max_begin, size);
-  eassert (left_limit <= limit);
-  eassert (right_limit <= limit);
-  eassert (limit == max (end, max (left_limit, right_limit)));
-  return limit;
+  struct check_subtree_result left_result
+    = check_subtree (node->left, tree_otick, max_depth - 1, offset,
+                     min_begin, begin);
+  struct check_subtree_result right_result
+    = check_subtree (node->right, tree_otick, max_depth - 1, offset,
+                     begin, max_begin);
+
+  eassert (left_result.limit <= limit);
+  eassert (right_result.limit <= limit);
+
+  result.complete = left_result.complete && right_result.complete;
+  if (result.complete)
+    {
+      /* Every path from a node to a descendent leaf contains the same
+         number of black nodes.  Often said this way: all nodes have
+         the same "black height".  */
+      eassert (left_result.black_height == right_result.black_height);
+      result.black_height
+        = (node->red ? 0 : 1) + left_result.black_height;
+
+      result.size = 1 + left_result.size + right_result.size;
+      result.limit
+        = max (end, max (left_result.limit, right_result.limit));
+
+      eassert (limit == result.limit);
+    }
+
+  return result;
 }
 
+/* Validate invariants for TREE.
+
+   This runs in constant time when ENABLE_OVERLAY_CHECKING is 0
+   (i.e. Emacs is not configured with
+   "--enable_checking=yes,overlays").  In this mode it can't check all
+   the invariants.  When ENABLE_OVERLAY_CHECKING is 1 it checks the
+   entire tree and validates all invariants.
+*/
 static bool
 check_tree (struct interval_tree *tree)
 {
@@ -260,9 +331,52 @@ check_tree (struct interval_tree *tree)
   if (tree->root == ITREE_NULL)
     return true;
 
-  intmax_t size = 0;
-  recurse_check_tree (tree->root, tree->otick, 0,
-                      PTRDIFF_MIN, PTRDIFF_MAX, &size);
+  /* Establish an upper bound on the height of the tree.
+
+     A red-black tree with n nodes has height at least log2(n + 1) but
+     no more than 2 * log2(n + 1).  A red-black tree with height h has
+     at least pow(2, h / 2) - 1 nodes but no more than pow(2, h) - 1.
+
+     On 64 bit architectures a red black tree has at least 2 pointers,
+     8 bytes each.  A 64 bit architecture has a theoretical maximum of
+     2 ^ 64 addressable bytes.
+
+     Putting this together, the upper bound for the height of any
+     red-black tree on a 64 bit architecture is 120.
+
+        2 * log2((2 ^ 64 bytes) / (2 * 8) bytes + 1) => 120
+
+     In truth, the memory overhead for our tree nodes is more than two
+     pointers, but even if we say each has 1 KiB overhead the bound
+     only drops to 108, which is an unimportant difference here.
+  */
+  const int max_height = 120;
+
+  /*
+    When ENABLE_OVERLAY_CHECKING is true, check the invariants of the
+    entire tree.
+
+    Otherwise limit invariant checking to at most 257 nodes.  When so
+    limited some of the invariants cannot be asserted, but the
+    asymtotic run time of the tree algorithms is preserved, so it is
+    practical to enable them whenever ENABLE_CHECKING (without
+    ENABLE_OVERLAY_CHECKING) is defined.
+
+    Note: a tree of height 8 can have at most 2^8-1 or 257 nodes.
+  */
+  const int max_depth
+    = (ENABLE_OVERLAY_CHECKING || tree->size <= 257) ? max_height : 8;
+
+  struct interval_node *node = tree->root;
+  struct check_subtree_result result
+    = check_subtree (node, tree->otick, max_depth, node->offset,
+                     PTRDIFF_MIN, PTRDIFF_MAX);
+  if (ENABLE_OVERLAY_CHECKING)
+    eassert (result.complete);
+  if (result.complete)
+    eassert (result.size == tree->size);
+
+  /* The only way this function fails is eassert().  */
   return true;
 }
 
-- 
2.35.1

Re: noverlay branch

[Eli Zaretskii]

> From: Matt Armstrong <matt@rfc20.org>
> Cc: emacs-devel@gnu.org
> Date: Sun, 09 Oct 2022 19:57:43 -0700
> 
> Subject: [PATCH 2/2] Add ./configure --enable-checking=overlays
> 
> This enables expensive validation checks of overlay data structures.
> Some are too expensive to turn on by default with
> --enable-checking=all since they turn O(log N) algorithms into O(N)
> algorithms.
> 
> * src/itree.c (ENABLE_OVERLAY_CHECKING): define to 0 if undefined.
> (struct check_subtree_result): new struct.
> (check_subtree): renamed from recurse_check_tree, modified to use
> check_subtree_result and check more invariants.
> (check_tree): use check_subtree_result.
> * configure.ac: add support for ENABLE_OVERLAY_CHECKING.

Unless the checks are _very_ expensive, I'd prefer not to introduce
yet another "enable-checking" knob, and instead condition those just
by ENABLE_CHECKING.  This will allow these assertions to be active in
more builds, and will enhance our checking of their conditions.

Please also consider whether we need some checks to be invoked
manually, e.g. when something goes wrong in a session that might be
related to overlays.  E.g., a command that dumps the overlay tree(s)
to stderr could be perhaps useful in such cases.

Thanks.

Re: noverlay branch

[Stefan Monnier]

> I had a different idea of tightening the otree invariant to this:
>
>  1) A node's otick must be greater than or equal to its children's.

That's already checked in the current code, right?

>  2) There is no tree->otick, just tree->root->otick.  That is what is
>     incremented when offsets are added.

Sounds good.

>  3) All downward tree traversal propagates offsets and otick.

I think we already do that, but if there are places we missed, then yes,
of course.

Regarding `otick`, I can see 2 more options:
- Get rid of it completely: its sole purpose is to try and keep
  `overlay-start/end` O(1) in the usual case instead of O(log N), but
  I'm not convinced it's worth the cost of propagating `otick` everywhere
  all the time.
- A halfway point is to keep `otick` but update it more lazily,
  i.e. only update it when we do `overlay-start/end` (e.g. in
  `interval_tree_validate`).

> Anyway, thanks for fixing my "thinko" bug in the check_tree code -- I
> had the fix but should have sent it faster.  I didn't actually intend
> for that to be commited yet (pushed it to sr.ht by accident), but maybe
> it helped you chase down the bugs you fixed today?

Yes, pointed out the problem in the tree insertion code, yes.

> Subject: [PATCH 2/2] Add ./configure --enable-checking=overlays

I think this is going overboard.  I'd rather focus on providing good
"everyday checks" (i.e. cheap checks which help document our invariants,
controlled by the normal ENABLE_CHECKING) and leave the rest of the
debugging code under "manual" control rather than expose it as an
`--enable-checking=` option.

My assumption here is that once debugged, this overlay code will stay
untouched for the next many years (based on the past history of our
overlay code).

> +static struct check_subtree_result
> +check_subtree (struct interval_node *node, uintmax_t tree_otick,
> +               int max_depth, ptrdiff_t offset, ptrdiff_t min_begin,
> +               ptrdiff_t max_begin)

This max_depth also sounds to me like over-engineering.

> -  /* We don't check the RB invariants here (neither the absence of
> -     red+red nor the equal-black-depth), so that we can use this check
> -     even while the tree is temporarily breaking some of those invarints.  */
> -  /* Red nodes cannot have red parents.  */
> -  /* eassert (node->parent == ITREE_NULL
> -              || !(node->red && node->parent->red)); */
> +  /* We don't normally check the RB invariants here (neither the
> +     absence of red+red nor the equal-black-depth), so that we can use
> +     this check even while the tree is temporarily breaking some of
> +     those invarints.  You can enable them if you want.  */
> +  if (false)
> +    {
> +      /* If a node is red then both of its children are black.  Red
> +         nodes cannot have red parents.  */
> +      if (node->red)
> +        {
> +          eassert (node->left == ITREE_NULL
> +                   || node->left->red == false);
> +          eassert (node->right == ITREE_NULL
> +                   || node->right->red == false);
> +          eassert (node->parent == ITREE_NULL || !node->parent->red);
> +        }
> +    }

Since we'll be recursing into the children, the first two easserts seem
redundant with the third (IOW the new code just does the same as the old
code, only more verbosely and less efficiently :-( ).
What am I missing?

> +  result.complete = left_result.complete && right_result.complete;
> +  if (result.complete)

I think all calls to `check_tree` should be complete traversals.

Most of the invariants checked in it are already checked incrementally
via sprinkled assertions elsewhere, so it's only really useful when
debugging a concrete known issue where the "local" checks aren't
good enough.

We could also include a few "cheap" calls to `check_tree` via `eassert`
(i.e. calls which we know shouldn't be algorithmically too expensive
because we're already traversing the whole tree for some other reason,
e.g. when killing a buffer (e.g. to verify that, at the end of the day,
we still preversed the RB invariants :-) or maybe during GC).

> +    {
> +      /* Every path from a node to a descendent leaf contains the same
> +         number of black nodes.  Often said this way: all nodes have
> +         the same "black height".  */
> +      eassert (left_result.black_height == right_result.black_height);

IIUC this assertion should be conditionalized in the same way as the
red+red check, since this invariant can be temporarily false.


        Stefan

Re: noverlay branch

[Matt Armstrong]

Eli Zaretskii <eliz@gnu.org> writes:

> Unless the checks are _very_ expensive, I'd prefer not to introduce
> yet another "enable-checking" knob, and instead condition those just
> by ENABLE_CHECKING.

Ok, withdrawn.  I haven't experienced extreme slowness myself.  The
problem is theoretical at this point.

Because the checks validate the entire overlay tree before and after
primitive operations (insert, erase, etc.) they do have the potential to
be worse than the old overlay implementation running with checks on
(exponential performance, etc.).  I left the --enable_checking=overlays
diffs here sould we want them later:
https://git.sr.ht/~matta/emacs/log/my/shelve/enable-checking-overlays


> Please also consider whether we need some checks to be invoked
> manually, e.g. when something goes wrong in a session that might be
> related to overlays.  E.g., a command that dumps the overlay tree(s)
> to stderr could be perhaps useful in such cases.

I believe there is code for a new lisp function that returns a
representation of the tree.  I have never used it, and I'm not sure if
it is enabled.

Re: noverlay branch

[Matt Armstrong]

Emanuel Berg <incal@dataswamp.org> writes:

> Stefan Monnier wrote:
>
>>> In any case, I do have a new test for
>>> tests/src/buffer-tests.el that crashes feature/noverlay
>>> Emacs immediately, when ENABLE_CHECKING is on, in a spot in
>>> itree.c having to do with offset inheritance.
>>
>> I tightened up a few things and the code now passes the
>> tests without crashing any more.
>
> I know only of the byte-compiler and checkdoc
>
>   https://dataswamp.org/~incal/emacs-init/ide/pack-style.el
>
> If you have something more I want it please :)
>
> If we talk Elisp in general ...

Hi Emanuel, for what it is worth I could not figure out how your
response here pertains to this conversation.  Have you replied and
quoted the correct messages?

Re: noverlay branch

[Matt Armstrong]

[-- Attachment #1: Type: text/plain, Size: 827 bytes --]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> In any case, I do have a new test for tests/src/buffer-tests.el that
>> crashes feature/noverlay Emacs immediately, when ENABLE_CHECKING is on,
>> in a spot in itree.c having to do with offset inheritance.
>
> I tightened up a few things and the code now passes the tests without
> crashing any more.

Stefan, I now have four commits queued up on
https://git.sr.ht/~matta/emacs/log/feature/noverlay

These supercede my last message, and reflect the withdrawal of the diffs
that add a new "overlays" configure time flag, as requested by Eli.

We're still checking the entire tree unconditionally, but the code still
has the height limiting logic in case it is needed.  It also doubles as
a spot check of the fuction that computes the max height of the tree
given its size.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-test-src-buffer-tests.el-Remove-unecessary-message-c.patch --]
[-- Type: text/x-diff, Size: 958 bytes --]

From 246acbddbeb3e9a390fe78242259182af0c2cc18 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Sun, 9 Oct 2022 10:12:32 -0700
Subject: [PATCH 1/4] ; * test/src/buffer-tests.el: Remove unecessary `message'
 calls.

---
 test/src/buffer-tests.el | 2 --
 1 file changed, 2 deletions(-)

diff --git a/test/src/buffer-tests.el b/test/src/buffer-tests.el
index 01780a15cc..9bccbdf2e8 100644
--- a/test/src/buffer-tests.el
+++ b/test/src/buffer-tests.el
@@ -1554,10 +1554,8 @@ test-overlay-randomly
         ;; is to initially steadily increase the overlay count, then
         ;; steadily decrease it, then repeat.
         (when (and growing (= overlay-count overlay-count-limit))
-          (message "now shrinking")
           (setq growing nil))
         (when (and (not growing) (= overlay-count 0))
-          (message "now growing")
           (setq growing t))
 
         ;; Create or delete a random overlay according to a
-- 
2.35.1


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: 0002-Improve-check_subtree.patch --]
[-- Type: text/x-diff, Size: 6916 bytes --]

From 100faa45a3e64f82f0b16fccb511db2431815940 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Mon, 10 Oct 2022 08:48:41 -0700
Subject: [PATCH 2/4] Improve check_subtree

* src/itree.c (struct check_subtree_result): new struct returned by
check_subtree.
(check_subtree): new function, renamed from recurse_check_tree.  Add
new black height assertions.
(check_tree): assert that the tree has non-negative size, assert that
limiting to interval_tree_max_height(tree) levels is enough to
traverses the complete tree.
---
 src/itree.c | 136 ++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 111 insertions(+), 25 deletions(-)

diff --git a/src/itree.c b/src/itree.c
index bbab70dac7..60bc2b5c89 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -205,14 +205,44 @@ itree_init (void)
   iter = interval_generator_create (NULL);
 }
 
-static ptrdiff_t
-recurse_check_tree (struct interval_node *node, uintmax_t tree_otick,
-                    ptrdiff_t offset, ptrdiff_t min_begin,
-                    ptrdiff_t max_begin, intmax_t *size)
+struct check_subtree_result
 {
+  /* Were all nodes visited?  */
+  bool complete;
+
+  /* Computed node count of the tree.  */
+  int size;
+
+  /* Computed limit of the tree (max END).  */
+  ptrdiff_t limit;
+
+  /* Computed black height of the tree (count of black nodes from the
+     bottom up to the root).  */
+  int black_height;
+};
+
+static struct check_subtree_result
+check_subtree (struct interval_node *node, uintmax_t tree_otick,
+               int max_depth, ptrdiff_t offset, ptrdiff_t min_begin,
+               ptrdiff_t max_begin)
+{
+  struct check_subtree_result result = { .complete = false,
+                                         .size = 0,
+                                         .limit = PTRDIFF_MIN,
+                                         .black_height = 0 };
   if (node == ITREE_NULL)
-    return PTRDIFF_MIN;
-  ++*size;
+    {
+      /* Every nil node of a Red-Black tree is black */
+      result.black_height = 1;
+      result.complete = true;
+      return result;
+    };
+
+  if (max_depth == 0)
+    {
+      result.complete = false;
+      return result;
+    }
 
   /* Validate structure.  */
   eassert (
@@ -221,12 +251,23 @@ recurse_check_tree (struct interval_node *node, uintmax_t tree_otick,
   eassert (node->left == ITREE_NULL || node->left->parent == node);
   eassert (node->right == ITREE_NULL || node->right->parent == node);
 
-  /* We don't check the RB invariants here (neither the absence of
-     red+red nor the equal-black-depth), so that we can use this check
-     even while the tree is temporarily breaking some of those invarints.  */
-  /* Red nodes cannot have red parents.  */
-  /* eassert (node->parent == ITREE_NULL
-              || !(node->red && node->parent->red)); */
+  /* We don't normally check the RB invariants here (neither the
+     absence of red+red nor the equal-black-depth), so that we can use
+     this check even while the tree is temporarily breaking some of
+     those invarints.  You can enable them if you want.  */
+  if (false)
+    {
+      /* If a node is red then both of its children are black.  Red
+         nodes cannot have red parents.  */
+      if (node->red)
+        {
+          eassert (node->left == ITREE_NULL
+                   || node->left->red == false);
+          eassert (node->right == ITREE_NULL
+                   || node->right->red == false);
+          eassert (node->parent == ITREE_NULL || !node->parent->red);
+        }
+    }
 
   eassert (node->offset == 0 || node->otick < tree_otick);
 
@@ -240,29 +281,74 @@ recurse_check_tree (struct interval_node *node, uintmax_t tree_otick,
   eassert (begin <= max_begin);
   eassert (end <= limit);
 
-  ptrdiff_t left_limit
-    = recurse_check_tree (node->left, tree_otick, offset, min_begin,
-                          begin, size);
-  ptrdiff_t right_limit
-    = recurse_check_tree (node->right, tree_otick, offset, begin,
-                          max_begin, size);
-  eassert (left_limit <= limit);
-  eassert (right_limit <= limit);
-  eassert (limit == max (end, max (left_limit, right_limit)));
-  return limit;
+  struct check_subtree_result left_result
+    = check_subtree (node->left, tree_otick, max_depth - 1, offset,
+                     min_begin, begin);
+  struct check_subtree_result right_result
+    = check_subtree (node->right, tree_otick, max_depth - 1, offset,
+                     begin, max_begin);
+
+  eassert (left_result.limit <= limit);
+  eassert (right_result.limit <= limit);
+
+  result.complete = left_result.complete && right_result.complete;
+  if (result.complete)
+    {
+      /* Every path from a node to a descendent leaf contains the same
+         number of black nodes.  Often said this way: all nodes have
+         the same "black height".  */
+      eassert (left_result.black_height == right_result.black_height);
+      result.black_height
+        = (node->red ? 0 : 1) + left_result.black_height;
+
+      result.size = 1 + left_result.size + right_result.size;
+      result.limit
+        = max (end, max (left_result.limit, right_result.limit));
+
+      eassert (limit == result.limit);
+    }
+
+  return result;
 }
 
+/* Validate invariants for TREE.
+
+   This runs in constant time when ENABLE_OVERLAY_CHECKING is 0
+   (i.e. Emacs is not configured with
+   "--enable_checking=yes,overlays").  In this mode it can't check all
+   the invariants.  When ENABLE_OVERLAY_CHECKING is 1 it checks the
+   entire tree and validates all invariants.
+*/
 static bool
 check_tree (struct interval_tree *tree)
 {
   eassert (tree != NULL);
+  eassert (tree->size >= 0);
   eassert ((tree->size == 0) == (tree->root == ITREE_NULL));
   if (tree->root == ITREE_NULL)
     return true;
 
-  intmax_t size = 0;
-  recurse_check_tree (tree->root, tree->otick, 0,
-                      PTRDIFF_MIN, PTRDIFF_MAX, &size);
+  /* Limit the traversal depth to what 'interval_tree_max_height'
+     returns.  Later, verify that this is enough height to traverse
+     the complete tree.  */
+  const int max_height = interval_tree_max_height (tree);
+  eassert (max_height >= 0);
+  eassert (max_height <= 120);
+
+  /* NOTE: if this check is too expensive an easy fix is to reduce
+     max_height to for large trees, then relax the assertion on
+     result.complete.  Assertions in check_subtree will still be made
+     at the bottom of the tree (where they are probably most
+     interesting), but some will be skipped closer to the root.  */
+
+  struct interval_node *node = tree->root;
+  struct check_subtree_result result
+    = check_subtree (node, tree->otick, max_height, node->offset,
+                     PTRDIFF_MIN, PTRDIFF_MAX);
+  eassert (result.complete);
+  eassert (result.size == tree->size);
+
+  /* The only way this function fails is eassert().  */
   return true;
 }
 
-- 
2.35.1


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #4: 0003-Check-red-black-invariants-in-most-places.patch --]
[-- Type: text/x-diff, Size: 5270 bytes --]

From f2c25af5217e8ab7e8c00ab3e0084bce2bdf93e8 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Mon, 10 Oct 2022 09:07:42 -0700
Subject: [PATCH 3/4] Check red-black invariants in most places

Stefan recently disabled this but I happened to want it back soon
after.

* src/itree.c (check_subtree): new arg: allow_red_red
(check_tree_common): renamed from check_tree, pass allow_red_red
through.
(check_tree): new function, pass allow_red_red=false
(interval_tree_insert): check_tree -> check_tree_common with
allow_red_red=true.
---
 src/itree.c | 50 +++++++++++++++++++++++++-------------------------
 1 file changed, 25 insertions(+), 25 deletions(-)

diff --git a/src/itree.c b/src/itree.c
index 60bc2b5c89..9dfac57930 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -222,9 +222,9 @@ itree_init (void)
 };
 
 static struct check_subtree_result
-check_subtree (struct interval_node *node, uintmax_t tree_otick,
-               int max_depth, ptrdiff_t offset, ptrdiff_t min_begin,
-               ptrdiff_t max_begin)
+check_subtree (struct interval_node *node, bool allow_red_red,
+               uintmax_t tree_otick, int max_depth, ptrdiff_t offset,
+               ptrdiff_t min_begin, ptrdiff_t max_begin)
 {
   struct check_subtree_result result = { .complete = false,
                                          .size = 0,
@@ -251,22 +251,14 @@ check_subtree (struct interval_node *node, uintmax_t tree_otick,
   eassert (node->left == ITREE_NULL || node->left->parent == node);
   eassert (node->right == ITREE_NULL || node->right->parent == node);
 
-  /* We don't normally check the RB invariants here (neither the
-     absence of red+red nor the equal-black-depth), so that we can use
-     this check even while the tree is temporarily breaking some of
-     those invarints.  You can enable them if you want.  */
-  if (false)
+  if (!allow_red_red && node->red)
     {
       /* If a node is red then both of its children are black.  Red
          nodes cannot have red parents.  */
-      if (node->red)
-        {
-          eassert (node->left == ITREE_NULL
-                   || node->left->red == false);
-          eassert (node->right == ITREE_NULL
-                   || node->right->red == false);
-          eassert (node->parent == ITREE_NULL || !node->parent->red);
-        }
+      eassert (node->left == ITREE_NULL || node->left->red == false);
+      eassert (node->right == ITREE_NULL
+               || node->right->red == false);
+      eassert (node->parent == ITREE_NULL || !node->parent->red);
     }
 
   eassert (node->offset == 0 || node->otick < tree_otick);
@@ -282,11 +274,11 @@ check_subtree (struct interval_node *node, uintmax_t tree_otick,
   eassert (end <= limit);
 
   struct check_subtree_result left_result
-    = check_subtree (node->left, tree_otick, max_depth - 1, offset,
-                     min_begin, begin);
+    = check_subtree (node->left, allow_red_red, tree_otick,
+                     max_depth - 1, offset, min_begin, begin);
   struct check_subtree_result right_result
-    = check_subtree (node->right, tree_otick, max_depth - 1, offset,
-                     begin, max_begin);
+    = check_subtree (node->right, allow_red_red, tree_otick,
+                     max_depth - 1, offset, begin, max_begin);
 
   eassert (left_result.limit <= limit);
   eassert (right_result.limit <= limit);
@@ -311,7 +303,8 @@ check_subtree (struct interval_node *node, uintmax_t tree_otick,
   return result;
 }
 
-/* Validate invariants for TREE.
+/* Validate invariants for TREE.  If ALLOW_RED_RED, red nodes with red
+   children are considered valid.
 
    This runs in constant time when ENABLE_OVERLAY_CHECKING is 0
    (i.e. Emacs is not configured with
@@ -320,7 +313,7 @@ check_subtree (struct interval_node *node, uintmax_t tree_otick,
    entire tree and validates all invariants.
 */
 static bool
-check_tree (struct interval_tree *tree)
+check_tree_common (struct interval_tree *tree, bool allow_red_red)
 {
   eassert (tree != NULL);
   eassert (tree->size >= 0);
@@ -343,8 +336,8 @@ check_tree (struct interval_tree *tree)
 
   struct interval_node *node = tree->root;
   struct check_subtree_result result
-    = check_subtree (node, tree->otick, max_height, node->offset,
-                     PTRDIFF_MIN, PTRDIFF_MAX);
+    = check_subtree (node, allow_red_red, tree->otick, max_height,
+                     node->offset, PTRDIFF_MIN, PTRDIFF_MAX);
   eassert (result.complete);
   eassert (result.size == tree->size);
 
@@ -352,6 +345,13 @@ check_tree (struct interval_tree *tree)
   return true;
 }
 
+/* Syntactic sugar for check_tree(tree, false)  */
+static bool
+check_tree (struct interval_tree *tree)
+{
+  return check_tree_common (tree, /* allow_red_red= */ false);
+}
+
 /* +===================================================================================+
  * | Stack
  * +===================================================================================+ */
@@ -616,7 +616,7 @@ interval_tree_insert (struct interval_tree *tree, struct interval_node *node)
 
   /* Fix/update the tree */
   ++tree->size;
-  eassert (check_tree (tree));
+  eassert (check_tree_common (tree, /* allow_red_red= */ true));
   interval_tree_insert_fix (tree, node);
 }
 
-- 
2.35.1


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #5: 0004-Simplify-itree_null-initialization.patch --]
[-- Type: text/x-diff, Size: 3296 bytes --]

From a737c1b8298adf5586eede9bf4dca238b302439d Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Mon, 10 Oct 2022 08:32:56 -0700
Subject: [PATCH 4/4] Simplify itree_null initialization

* src/itree.c (null_is_sane): call eassert directly, check
REAR_ADVANCE, FRONT_ADVANCE.  Add FIXME that PARENT is still
read/write.
(itree_null): initialize statically
(itree_init): remove initialization code, call eassert(null_is_sane())
(check_tree_common): call eassert (null_is_sane())
---
 src/itree.c | 52 ++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 36 insertions(+), 16 deletions(-)

diff --git a/src/itree.c b/src/itree.c
index 9dfac57930..8d1dd00319 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -145,19 +145,42 @@ Copyright (C) 2017-2022  Free Software Foundation, Inc.
 static void interval_tree_insert (struct interval_tree *, struct interval_node *);
 
 /* The sentinel node, the null node.  */
-struct interval_node itree_null;
+struct interval_node itree_null = {
+  .parent = &itree_null,
+  .left = &itree_null,
+  .right = &itree_null,
+  .begin = PTRDIFF_MIN,
+  .end = PTRDIFF_MIN,
+  .limit = PTRDIFF_MIN, /* => max(x, null.limit) = x */
+  .offset = 0,
+  .otick = 0,
+  .red = false,
+  .rear_advance = false,
+  .front_advance = false,
+};
 
 static bool
 null_is_sane (void)
 {
-  /* The sentinel node has most of its fields read-only, except for `parent`,
-     `left`, `right` which are write only.  */
-  return itree_null.red == false
-         && itree_null.otick == 0
-         && itree_null.offset == 0
-         && itree_null.begin == PTRDIFF_MIN
-         && itree_null.end == PTRDIFF_MIN
-         && itree_null.limit == PTRDIFF_MIN;
+  /* The sentinel node has most of its fields read-only.
+
+     FIXME: PARENT is still read/write.  It is written to
+     ininterval_tree_transplant, and later read.  --matt
+  */
+  /* eassert (itree_null.parent == &itree_null); */
+  eassert (itree_null.left == &itree_null);
+  eassert (itree_null.right == &itree_null);
+  eassert (itree_null.begin == PTRDIFF_MIN);
+  eassert (itree_null.end == PTRDIFF_MIN);
+  eassert (itree_null.limit == PTRDIFF_MIN);
+  eassert (itree_null.offset == 0);
+  eassert (itree_null.otick == 0);
+  eassert (itree_null.red == false);
+  eassert (itree_null.rear_advance == false);
+  eassert (itree_null.front_advance == false);
+
+  /* if we get this far things must be good */
+  return true;
 }
 
 /* +------------------------------------------------------------------------------------+ */
@@ -195,13 +218,8 @@ null_is_sane (void)
 static void
 itree_init (void)
 {
-  struct interval_node *null = ITREE_NULL;
-  null->left = null->right = null->parent = null;
-  null->offset = null->otick = 0;
-  null->begin = PTRDIFF_MIN;
-  null->end = PTRDIFF_MIN;
-  null->limit = PTRDIFF_MIN;     /* => max(x, null.limit) = x */
-  null->red = false;
+  eassert (null_is_sane ());
+
   iter = interval_generator_create (NULL);
 }
 
@@ -315,6 +333,8 @@ check_subtree (struct interval_node *node, bool allow_red_red,
 static bool
 check_tree_common (struct interval_tree *tree, bool allow_red_red)
 {
+  eassert (null_is_sane ());
+
   eassert (tree != NULL);
   eassert (tree->size >= 0);
   eassert ((tree->size == 0) == (tree->root == ITREE_NULL));
-- 
2.35.1

Re: noverlay branch

[Matt Armstrong]

[-- Attachment #1: Type: text/plain, Size: 813 bytes --]

Matt Armstrong <matt@rfc20.org> writes:

> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>
>>> In any case, I do have a new test for tests/src/buffer-tests.el that
>>> crashes feature/noverlay Emacs immediately, when ENABLE_CHECKING is on,
>>> in a spot in itree.c having to do with offset inheritance.
>>
>> I tightened up a few things and the code now passes the tests without
>> crashing any more.
>
> Stefan, I now have four commits queued up on
> https://git.sr.ht/~matta/emacs/log/feature/noverlay

...now 5 commits on https://git.sr.ht/~matta/emacs/log/feature/noverlay

The latest makes all fields of the global itree_null sentinel node
read-only.  Because this property is only by convention, fragile, and
difficult to verify by reading code, I'm going to look at removing
itree_node entirely next.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0005-Stop-reading-and-writing-the-itree_null.parent-field.patch --]
[-- Type: text/x-diff, Size: 4086 bytes --]

From b4bdbbcd47530ed80d941bd4bd6d57538ee33ca5 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Mon, 10 Oct 2022 10:45:05 -0700
Subject: [PATCH 5/5] Stop reading and writing the itree_null.parent field
 entirely.

With this change all fields in the itree_null sentinel are read only.
This makes accessing itree_null thread safe in an obvious way.

Because it took two commits from two peole to get this right, I think
we can call this design fragile and difficult to reason about.
Another benefit of this commit is as preparation for removing sentinel
node completely, and just using NULL.

* src/itree.c (itree_null): Statically initialize itree_null.parent to
NULL.  It is never accessed.
(null_is_sane): Assert parent == NULL.
(interval_tree_remove_fix): Remove unecessary assignments to parent
from node->parent.  These were the last places itree_null.parent were
read.
(interval_tree_remove): Avoid an assignment to itree_null.parent
through min->right->parent.
(interval_tree_transplant): Avoid an assignment to itree_null.parent
through source->parent.
---
 src/itree.c | 20 +++++++-------------
 1 file changed, 7 insertions(+), 13 deletions(-)

diff --git a/src/itree.c b/src/itree.c
index 8d1dd00319..7b6a5039b3 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -146,7 +146,7 @@ Copyright (C) 2017-2022  Free Software Foundation, Inc.
 
 /* The sentinel node, the null node.  */
 struct interval_node itree_null = {
-  .parent = &itree_null,
+  .parent = NULL, /* never accessed */
   .left = &itree_null,
   .right = &itree_null,
   .begin = PTRDIFF_MIN,
@@ -162,12 +162,8 @@ Copyright (C) 2017-2022  Free Software Foundation, Inc.
 static bool
 null_is_sane (void)
 {
-  /* The sentinel node has most of its fields read-only.
-
-     FIXME: PARENT is still read/write.  It is written to
-     ininterval_tree_transplant, and later read.  --matt
-  */
-  /* eassert (itree_null.parent == &itree_null); */
+  /* All sentinel node fields are read-only.  */
+  eassert (itree_null.parent == NULL);
   eassert (itree_null.left == &itree_null);
   eassert (itree_null.right == &itree_null);
   eassert (itree_null.begin == PTRDIFF_MIN);
@@ -720,7 +716,6 @@ interval_tree_remove_fix (struct interval_tree *tree,
 	      other->red = false;
 	      parent->red = true;
 	      interval_tree_rotate_left (tree, parent);
-	      parent = node->parent;
 	      other = parent->right;
             }
 
@@ -739,7 +734,6 @@ interval_tree_remove_fix (struct interval_tree *tree,
 		  other->left->red = false;
 		  other->red = true;
 		  interval_tree_rotate_right (tree, other);
-		  parent = node->parent;
 		  other = parent->right;
                 }
 	      other->red = parent->red; /* 4.a */
@@ -759,7 +753,6 @@ interval_tree_remove_fix (struct interval_tree *tree,
 	      other->red = false;
 	      parent->red = true;
 	      interval_tree_rotate_right (tree, parent);
-	      parent = node->parent;
 	      other = parent->left;
             }
 
@@ -778,7 +771,6 @@ interval_tree_remove_fix (struct interval_tree *tree,
 		  other->right->red = false;
 		  other->red = true;
 		  interval_tree_rotate_left (tree, other);
-		  parent = node->parent;
 		  other = parent->left;
                 }
 
@@ -859,7 +851,8 @@ interval_tree_remove (struct interval_tree *tree, struct interval_node *node)
       interval_tree_transplant (tree, min, node);
       /* We set min->right->parent after `interval_tree_transplant` so
          that calls to `itree_total_offset` don't get stuck in an inf-loop.  */
-      min->right->parent = min;
+      if (min->right != ITREE_NULL)
+        min->right->parent = min;
       interval_tree_update_limit (min);
       /* This call "belongs" with the first `interval_tree_transplant`
          (of `min_right`, done earlier in the `if`) but we prefer to do it
@@ -1486,7 +1479,8 @@ interval_tree_transplant (struct interval_tree *tree, struct interval_node *sour
   else
     dest->parent->right = source;
 
-  source->parent = dest->parent;
+  if (source != ITREE_NULL)
+    source->parent = dest->parent;
 }
 
 \f
-- 
2.35.1

Re: noverlay branch

[Matt Armstrong]

[-- Attachment #1: Type: text/plain, Size: 6362 bytes --]

Stefan, I read only Eli's reply this morning.  Got to yours just now.


Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> I had a different idea of tightening the otree invariant to this:
>>
>>  1) A node's otick must be greater than or equal to its children's.
>
> That's already checked in the current code, right?

Not yet...until...just now.  See patches below.


>>  3) All downward tree traversal propagates offsets and otick.
>
> I think we already do that, but if there are places we missed, then yes,
> of course.

Yes, I think we do.  The wrinkle is that we don't always start
inheriting at the root, but otick is not updated in that case.


> Regarding `otick`, I can see 2 more options:
> - Get rid of it completely: its sole purpose is to try and keep
>   `overlay-start/end` O(1) in the usual case instead of O(log N), but
>   I'm not convinced it's worth the cost of propagating `otick` everywhere
>   all the time.
> - A halfway point is to keep `otick` but update it more lazily,
>   i.e. only update it when we do `overlay-start/end` (e.g. in
>   `interval_tree_validate`).

These ideas are simpler but similar in direction to my idea to use a
btree instead.  Then some of the "augmentation" could live in btree
arrays, which are a lot faster to traverse and modify in bulk.  (pie in
sky idea, maybe for Emacs 30 but more likely 40!).


>> Subject: [PATCH 2/2] Add ./configure --enable-checking=overlays
>
> I think this is going overboard.  I'd rather focus on providing good
> "everyday checks" (i.e. cheap checks which help document our invariants,
> controlled by the normal ENABLE_CHECKING) and leave the rest of the
> debugging code under "manual" control rather than expose it as an
> `--enable-checking=` option.

Yes, Eli said the same.  I've removed it.


> My assumption here is that once debugged, this overlay code will stay
> untouched for the next many years (based on the past history of our
> overlay code).

Yep, a great reason to have good ENABLE_CHECKING code.


>> +static struct check_subtree_result
>> +check_subtree (struct interval_node *node, uintmax_t tree_otick,
>> +               int max_depth, ptrdiff_t offset, ptrdiff_t min_begin,
>> +               ptrdiff_t max_begin)
>
> This max_depth also sounds to me like over-engineering.

I'd like to keep max_depth.

My reason for adding it is informed by experience on similar projects.
It is easier to understand an assertion that the tree is too deep than
it is to debug, say, stack overflow when there is a cycle in the link
structure of the tree.  It is easier to limit the height of checking if,
indeed, on some night I am diagnosing an unrelated bug but the perf cost
here is too much.  With max_depth in place I can easily manually hack up
a functon to verify checks only in a small subset of the tree
(e.g. around a rotation operation, etc.).  I've done and benefited from
this sort of thing in the past.

There is a small concrete benefit to it right now.  MAX_DEPTH is now
initialized from interval_tree_max_height(), which currently could wildy
under estimate the height and we wouldn't notice (because generator
stacks auto-grow).  Since we call that fucntion to make "big enough to
not need growing" stacks, it is nice to have test coverage for it.

I don't like over-engeneering, but I wouldn't call this engineering at
all.  It is just an arg and a bit of related code, with some utility,
and a tiny maintenance cost.  :-)


>> -  /* We don't check the RB invariants here (neither the absence of
>> -     red+red nor the equal-black-depth), so that we can use this check
>> -     even while the tree is temporarily breaking some of those invarints.  */
>> -  /* Red nodes cannot have red parents.  */
>> -  /* eassert (node->parent == ITREE_NULL
>> -              || !(node->red && node->parent->red)); */
>> +  /* We don't normally check the RB invariants here (neither the
>> +     absence of red+red nor the equal-black-depth), so that we can use
>> +     this check even while the tree is temporarily breaking some of
>> +     those invarints.  You can enable them if you want.  */
>> +  if (false)
>> +    {
>> +      /* If a node is red then both of its children are black.  Red
>> +         nodes cannot have red parents.  */
>> +      if (node->red)
>> +        {
>> +          eassert (node->left == ITREE_NULL
>> +                   || node->left->red == false);
>> +          eassert (node->right == ITREE_NULL
>> +                   || node->right->red == false);
>> +          eassert (node->parent == ITREE_NULL || !node->parent->red);
>> +        }
>> +    }
>
> Since we'll be recursing into the children, the first two easserts seem
> redundant with the third (IOW the new code just does the same as the old
> code, only more verbosely and less efficiently :-( ).
> What am I missing?

Good point, I reworked this for simplicity.


>> +  result.complete = left_result.complete && right_result.complete;
>> +  if (result.complete)
>
> I think all calls to `check_tree` should be complete traversals.
>
> Most of the invariants checked in it are already checked incrementally
> via sprinkled assertions elsewhere, so it's only really useful when
> debugging a concrete known issue where the "local" checks aren't good
> enough.

All `check_tree` calls are complete traversals.  If they aren't there is
a bug and an `eassert` will fire.


> We could also include a few "cheap" calls to `check_tree` via `eassert`
> (i.e. calls which we know shouldn't be algorithmically too expensive
> because we're already traversing the whole tree for some other reason,
> e.g. when killing a buffer (e.g. to verify that, at the end of the day,
> we still preversed the RB invariants :-) or maybe during GC).

...I'm not understanding something here.  All `check_tree` calls are in
`eassert` already.


>> +    {
>> +      /* Every path from a node to a descendent leaf contains the same
>> +         number of black nodes.  Often said this way: all nodes have
>> +         the same "black height".  */
>> +      eassert (left_result.black_height == right_result.black_height);
>
> IIUC this assertion should be conditionalized in the same way as the
> red+red check, since this invariant can be temporarily false.

Done, and now we have `check_tree_no_rb` for the one call site.

At https://git.sr.ht/~matta/emacs/log/feature/noverlay or below.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Improve-check_subtree.patch --]
[-- Type: text/x-diff, Size: 8205 bytes --]

From 67b9e89a5aa0052b1abdcd8971a0fa83f52e13a5 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Mon, 10 Oct 2022 08:48:41 -0700
Subject: [PATCH 1/4] Improve check_subtree

* src/itree.c (struct check_subtree_result): new struct returned by
check_subtree.
(check_subtree): new function, renamed from recurse_check_tree.  Add
new black height assertions.
(check_tree): assert that the tree has non-negative size, assert that
limiting to interval_tree_max_height(tree) levels is enough to
traverses the complete tree.
---
 src/itree.c | 156 ++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 126 insertions(+), 30 deletions(-)

diff --git a/src/itree.c b/src/itree.c
index bbab70dac7..aa8a5f7f3b 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -205,14 +205,44 @@ itree_init (void)
   iter = interval_generator_create (NULL);
 }
 
-static ptrdiff_t
-recurse_check_tree (struct interval_node *node, uintmax_t tree_otick,
-                    ptrdiff_t offset, ptrdiff_t min_begin,
-                    ptrdiff_t max_begin, intmax_t *size)
+struct check_subtree_result
+{
+  /* Were all nodes visited?  */
+  bool complete;
+
+  /* Computed node count of the tree.  */
+  int size;
+
+  /* Computed limit of the tree (max END).  */
+  ptrdiff_t limit;
+
+  /* Computed black height of the tree (count of black nodes from the
+     bottom up to the root).  */
+  int black_height;
+};
+
+static struct check_subtree_result
+check_subtree (struct interval_node *node, uintmax_t tree_otick,
+               int max_depth, ptrdiff_t offset, ptrdiff_t min_begin,
+               ptrdiff_t max_begin)
 {
+  struct check_subtree_result result = { .complete = false,
+                                         .size = 0,
+                                         .limit = PTRDIFF_MIN,
+                                         .black_height = 0 };
   if (node == ITREE_NULL)
-    return PTRDIFF_MIN;
-  ++*size;
+    {
+      /* Every nil node of a Red-Black tree is black */
+      result.black_height = 1;
+      result.complete = true;
+      return result;
+    };
+
+  if (max_depth == 0)
+    {
+      result.complete = false;
+      return result;
+    }
 
   /* Validate structure.  */
   eassert (
@@ -221,14 +251,35 @@ recurse_check_tree (struct interval_node *node, uintmax_t tree_otick,
   eassert (node->left == ITREE_NULL || node->left->parent == node);
   eassert (node->right == ITREE_NULL || node->right->parent == node);
 
-  /* We don't check the RB invariants here (neither the absence of
-     red+red nor the equal-black-depth), so that we can use this check
-     even while the tree is temporarily breaking some of those invarints.  */
-  /* Red nodes cannot have red parents.  */
-  /* eassert (node->parent == ITREE_NULL
-              || !(node->red && node->parent->red)); */
+  /* We don't normally check the RB invariants here (neither the
+     absence of red+red nor the equal-black-depth), so that we can use
+     this check even while the tree is temporarily breaking some of
+     those invarints.  You can enable them if you want.  */
+  if (false)
+    {
+      /* If a node is red then both of its children are black.  Red
+         nodes cannot have red parents.  */
+      if (node->red)
+        {
+          eassert (node->left == ITREE_NULL
+                   || node->left->red == false);
+          eassert (node->right == ITREE_NULL
+                   || node->right->red == false);
+          eassert (node->parent == ITREE_NULL || !node->parent->red);
+        }
+    }
 
-  eassert (node->offset == 0 || node->otick < tree_otick);
+  /* Validate otick.  A node's otick must be <= to the tree's otick
+     and <= to its parent's otick.
+
+     Note: we cannot assert that (NODE.otick == NODE.parent.otick)
+     implies (NODE.offset == 0) because interval_tree_inherit_offset()
+     doesn't always update otick.  It could, but it is not clear there
+     is a need.  */
+  eassert (node->otick <= tree_otick);
+  eassert (node->parent == ITREE_NULL
+           || node->otick <= node->parent->otick);
+  eassert (node->otick != tree_otick || node->offset == 0);
 
   offset += node->offset;
   ptrdiff_t begin = node->begin + offset;
@@ -240,29 +291,74 @@ recurse_check_tree (struct interval_node *node, uintmax_t tree_otick,
   eassert (begin <= max_begin);
   eassert (end <= limit);
 
-  ptrdiff_t left_limit
-    = recurse_check_tree (node->left, tree_otick, offset, min_begin,
-                          begin, size);
-  ptrdiff_t right_limit
-    = recurse_check_tree (node->right, tree_otick, offset, begin,
-                          max_begin, size);
-  eassert (left_limit <= limit);
-  eassert (right_limit <= limit);
-  eassert (limit == max (end, max (left_limit, right_limit)));
-  return limit;
+  struct check_subtree_result left_result
+    = check_subtree (node->left, tree_otick, max_depth - 1, offset,
+                     min_begin, begin);
+  struct check_subtree_result right_result
+    = check_subtree (node->right, tree_otick, max_depth - 1, offset,
+                     begin, max_begin);
+
+  eassert (left_result.limit <= limit);
+  eassert (right_result.limit <= limit);
+
+  result.complete = left_result.complete && right_result.complete;
+  if (result.complete)
+    {
+      /* Every path from a node to a descendent leaf contains the same
+         number of black nodes.  Often said this way: all nodes have
+         the same "black height".  */
+      eassert (left_result.black_height == right_result.black_height);
+      result.black_height
+        = (node->red ? 0 : 1) + left_result.black_height;
+
+      result.size = 1 + left_result.size + right_result.size;
+      result.limit
+        = max (end, max (left_result.limit, right_result.limit));
+
+      eassert (limit == result.limit);
+    }
+
+  return result;
 }
 
+/* Validate invariants for TREE.
+
+   This runs in constant time when ENABLE_OVERLAY_CHECKING is 0
+   (i.e. Emacs is not configured with
+   "--enable_checking=yes,overlays").  In this mode it can't check all
+   the invariants.  When ENABLE_OVERLAY_CHECKING is 1 it checks the
+   entire tree and validates all invariants.
+*/
 static bool
 check_tree (struct interval_tree *tree)
 {
   eassert (tree != NULL);
+  eassert (tree->size >= 0);
   eassert ((tree->size == 0) == (tree->root == ITREE_NULL));
   if (tree->root == ITREE_NULL)
     return true;
 
-  intmax_t size = 0;
-  recurse_check_tree (tree->root, tree->otick, 0,
-                      PTRDIFF_MIN, PTRDIFF_MAX, &size);
+  /* Limit the traversal depth to what 'interval_tree_max_height'
+     returns.  Later, verify that this is enough height to traverse
+     the complete tree.  */
+  const int max_height = interval_tree_max_height (tree);
+  eassert (max_height >= 0);
+  eassert (max_height <= 120);
+
+  /* NOTE: if this check is too expensive an easy fix is to reduce
+     max_height to for large trees, then relax the assertion on
+     result.complete.  Assertions in check_subtree will still be made
+     at the bottom of the tree (where they are probably most
+     interesting), but some will be skipped closer to the root.  */
+
+  struct interval_node *node = tree->root;
+  struct check_subtree_result result
+    = check_subtree (node, tree->otick, max_height, node->offset,
+                     PTRDIFF_MIN, PTRDIFF_MAX);
+  eassert (result.complete);
+  eassert (result.size == tree->size);
+
+  /* The only way this function fails is eassert().  */
   return true;
 }
 
@@ -1145,10 +1241,10 @@ interval_tree_inherit_offset (uintmax_t otick, struct interval_node *node)
     }
 
   /* Offsets can be inherited from dirty nodes (with out of date
-     otick) during insert and remove.  Offsets aren't inherited
-     downward from the root for these operations so rotations are
-     performed on potentially "dirty" nodes, where we only make sure
-     the *local* offsets are all zero.  */
+     otick) during removal, since we do not travel down from the root
+     in that case.  In this case rotations are performed on
+     potentially "dirty" nodes, where we only need to make sure the
+     *local* offsets are zero.  */
 
   if (node->offset)
     {
-- 
2.35.1


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: 0002-Check-red-black-invariants-in-most-places.patch --]
[-- Type: text/x-diff, Size: 6506 bytes --]

From 51a8e375ebea2e6e05eed623bddfb323b8e408f0 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Mon, 10 Oct 2022 09:07:42 -0700
Subject: [PATCH 2/4] Check red-black invariants in most places

Stefan recently disabled this but I happened to want it back soon
after.

* src/itree.c (check_subtree): new arg: allow_red_red
(check_tree_common): renamed from check_tree, pass allow_red_red
through.
(check_tree): new function, pass allow_red_red=false
(interval_tree_insert): check_tree -> check_tree_common with
allow_red_red=true.
---
 src/itree.c | 80 ++++++++++++++++++++++++++++++-----------------------
 1 file changed, 46 insertions(+), 34 deletions(-)

diff --git a/src/itree.c b/src/itree.c
index aa8a5f7f3b..7ac400398b 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -222,7 +222,8 @@ itree_init (void)
 };
 
 static struct check_subtree_result
-check_subtree (struct interval_node *node, uintmax_t tree_otick,
+check_subtree (struct interval_node *node,
+               bool check_red_black_invariants, uintmax_t tree_otick,
                int max_depth, ptrdiff_t offset, ptrdiff_t min_begin,
                ptrdiff_t max_begin)
 {
@@ -251,23 +252,9 @@ check_subtree (struct interval_node *node, uintmax_t tree_otick,
   eassert (node->left == ITREE_NULL || node->left->parent == node);
   eassert (node->right == ITREE_NULL || node->right->parent == node);
 
-  /* We don't normally check the RB invariants here (neither the
-     absence of red+red nor the equal-black-depth), so that we can use
-     this check even while the tree is temporarily breaking some of
-     those invarints.  You can enable them if you want.  */
-  if (false)
-    {
-      /* If a node is red then both of its children are black.  Red
-         nodes cannot have red parents.  */
-      if (node->red)
-        {
-          eassert (node->left == ITREE_NULL
-                   || node->left->red == false);
-          eassert (node->right == ITREE_NULL
-                   || node->right->red == false);
-          eassert (node->parent == ITREE_NULL || !node->parent->red);
-        }
-    }
+  /* No red nodes have red parents.  */
+  if (check_red_black_invariants && node->parent != ITREE_NULL)
+    eassert (!node->red || !node->parent->red);
 
   /* Validate otick.  A node's otick must be <= to the tree's otick
      and <= to its parent's otick.
@@ -292,11 +279,13 @@ check_subtree (struct interval_node *node, uintmax_t tree_otick,
   eassert (end <= limit);
 
   struct check_subtree_result left_result
-    = check_subtree (node->left, tree_otick, max_depth - 1, offset,
-                     min_begin, begin);
+    = check_subtree (node->left, check_red_black_invariants,
+                     tree_otick, max_depth - 1, offset, min_begin,
+                     begin);
   struct check_subtree_result right_result
-    = check_subtree (node->right, tree_otick, max_depth - 1, offset,
-                     begin, max_begin);
+    = check_subtree (node->right, check_red_black_invariants,
+                     tree_otick, max_depth - 1, offset, begin,
+                     max_begin);
 
   eassert (left_result.limit <= limit);
   eassert (right_result.limit <= limit);
@@ -304,24 +293,29 @@ check_subtree (struct interval_node *node, uintmax_t tree_otick,
   result.complete = left_result.complete && right_result.complete;
   if (result.complete)
     {
-      /* Every path from a node to a descendent leaf contains the same
-         number of black nodes.  Often said this way: all nodes have
-         the same "black height".  */
-      eassert (left_result.black_height == right_result.black_height);
-      result.black_height
-        = (node->red ? 0 : 1) + left_result.black_height;
-
       result.size = 1 + left_result.size + right_result.size;
       result.limit
         = max (end, max (left_result.limit, right_result.limit));
 
       eassert (limit == result.limit);
+
+      if (check_red_black_invariants)
+        {
+          /* Every path from a node to a descendent leaf contains the
+             same number of black nodes.  Often said this way: all
+             nodes have the same "black height".  */
+          eassert (left_result.black_height
+                   == right_result.black_height);
+          result.black_height
+            = (node->red ? 0 : 1) + left_result.black_height;
+        }
     }
 
   return result;
 }
 
-/* Validate invariants for TREE.
+/* Validate invariants for TREE.  If CHECK_RED_BLACK_INVARIANTS, red
+   nodes with red children are considered invalid.
 
    This runs in constant time when ENABLE_OVERLAY_CHECKING is 0
    (i.e. Emacs is not configured with
@@ -330,7 +324,8 @@ check_subtree (struct interval_node *node, uintmax_t tree_otick,
    entire tree and validates all invariants.
 */
 static bool
-check_tree (struct interval_tree *tree)
+check_tree_common (struct interval_tree *tree,
+                   bool check_red_black_invariants)
 {
   eassert (tree != NULL);
   eassert (tree->size >= 0);
@@ -353,8 +348,9 @@ check_tree (struct interval_tree *tree)
 
   struct interval_node *node = tree->root;
   struct check_subtree_result result
-    = check_subtree (node, tree->otick, max_height, node->offset,
-                     PTRDIFF_MIN, PTRDIFF_MAX);
+    = check_subtree (node, check_red_black_invariants, tree->otick,
+                     max_height, node->offset, PTRDIFF_MIN,
+                     PTRDIFF_MAX);
   eassert (result.complete);
   eassert (result.size == tree->size);
 
@@ -362,6 +358,22 @@ check_tree (struct interval_tree *tree)
   return true;
 }
 
+/* Check the tree with all invariant checks enabled.  */
+static bool
+check_tree (struct interval_tree *tree)
+{
+  return check_tree_common (tree, true);
+}
+
+/* Check the tree with all invariant checks enabled, except for the
+   red-black tree invariants.  Useful for asserting the other
+   invariants while inserting or removing.  */
+static bool
+check_tree_no_rb (struct interval_tree *tree)
+{
+  return check_tree_common (tree, false);
+}
+
 /* +===================================================================================+
  * | Stack
  * +===================================================================================+ */
@@ -626,7 +638,7 @@ interval_tree_insert (struct interval_tree *tree, struct interval_node *node)
 
   /* Fix/update the tree */
   ++tree->size;
-  eassert (check_tree (tree));
+  eassert (check_tree_no_rb (tree));
   interval_tree_insert_fix (tree, node);
 }
 
-- 
2.35.1


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #4: 0003-Simplify-itree_null-initialization.patch --]
[-- Type: text/x-diff, Size: 3296 bytes --]

From a154259bfacf7f1406794a952e80a8197b9a83fb Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Mon, 10 Oct 2022 08:32:56 -0700
Subject: [PATCH 3/4] Simplify itree_null initialization

* src/itree.c (null_is_sane): call eassert directly, check
REAR_ADVANCE, FRONT_ADVANCE.  Add FIXME that PARENT is still
read/write.
(itree_null): initialize statically
(itree_init): remove initialization code, call eassert(null_is_sane())
(check_tree_common): call eassert (null_is_sane())
---
 src/itree.c | 52 ++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 36 insertions(+), 16 deletions(-)

diff --git a/src/itree.c b/src/itree.c
index 7ac400398b..d9f9ec8cd6 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -145,19 +145,42 @@ Copyright (C) 2017-2022  Free Software Foundation, Inc.
 static void interval_tree_insert (struct interval_tree *, struct interval_node *);
 
 /* The sentinel node, the null node.  */
-struct interval_node itree_null;
+struct interval_node itree_null = {
+  .parent = &itree_null,
+  .left = &itree_null,
+  .right = &itree_null,
+  .begin = PTRDIFF_MIN,
+  .end = PTRDIFF_MIN,
+  .limit = PTRDIFF_MIN, /* => max(x, null.limit) = x */
+  .offset = 0,
+  .otick = 0,
+  .red = false,
+  .rear_advance = false,
+  .front_advance = false,
+};
 
 static bool
 null_is_sane (void)
 {
-  /* The sentinel node has most of its fields read-only, except for `parent`,
-     `left`, `right` which are write only.  */
-  return itree_null.red == false
-         && itree_null.otick == 0
-         && itree_null.offset == 0
-         && itree_null.begin == PTRDIFF_MIN
-         && itree_null.end == PTRDIFF_MIN
-         && itree_null.limit == PTRDIFF_MIN;
+  /* The sentinel node has most of its fields read-only.
+
+     FIXME: PARENT is still read/write.  It is written to
+     ininterval_tree_transplant, and later read.  --matt
+  */
+  /* eassert (itree_null.parent == &itree_null); */
+  eassert (itree_null.left == &itree_null);
+  eassert (itree_null.right == &itree_null);
+  eassert (itree_null.begin == PTRDIFF_MIN);
+  eassert (itree_null.end == PTRDIFF_MIN);
+  eassert (itree_null.limit == PTRDIFF_MIN);
+  eassert (itree_null.offset == 0);
+  eassert (itree_null.otick == 0);
+  eassert (itree_null.red == false);
+  eassert (itree_null.rear_advance == false);
+  eassert (itree_null.front_advance == false);
+
+  /* if we get this far things must be good */
+  return true;
 }
 
 /* +------------------------------------------------------------------------------------+ */
@@ -195,13 +218,8 @@ null_is_sane (void)
 static void
 itree_init (void)
 {
-  struct interval_node *null = ITREE_NULL;
-  null->left = null->right = null->parent = null;
-  null->offset = null->otick = 0;
-  null->begin = PTRDIFF_MIN;
-  null->end = PTRDIFF_MIN;
-  null->limit = PTRDIFF_MIN;     /* => max(x, null.limit) = x */
-  null->red = false;
+  eassert (null_is_sane ());
+
   iter = interval_generator_create (NULL);
 }
 
@@ -327,6 +345,8 @@ check_subtree (struct interval_node *node,
 check_tree_common (struct interval_tree *tree,
                    bool check_red_black_invariants)
 {
+  eassert (null_is_sane ());
+
   eassert (tree != NULL);
   eassert (tree->size >= 0);
   eassert ((tree->size == 0) == (tree->root == ITREE_NULL));
-- 
2.35.1


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #5: 0004-Stop-reading-and-writing-the-itree_null.parent-field.patch --]
[-- Type: text/x-diff, Size: 4086 bytes --]

From da0387f0fe79f577fae6d5453c758f600e1ae495 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Mon, 10 Oct 2022 10:45:05 -0700
Subject: [PATCH 4/4] Stop reading and writing the itree_null.parent field
 entirely.

With this change all fields in the itree_null sentinel are read only.
This makes accessing itree_null thread safe in an obvious way.

Because it took two commits from two peole to get this right, I think
we can call this design fragile and difficult to reason about.
Another benefit of this commit is as preparation for removing sentinel
node completely, and just using NULL.

* src/itree.c (itree_null): Statically initialize itree_null.parent to
NULL.  It is never accessed.
(null_is_sane): Assert parent == NULL.
(interval_tree_remove_fix): Remove unecessary assignments to parent
from node->parent.  These were the last places itree_null.parent were
read.
(interval_tree_remove): Avoid an assignment to itree_null.parent
through min->right->parent.
(interval_tree_transplant): Avoid an assignment to itree_null.parent
through source->parent.
---
 src/itree.c | 20 +++++++-------------
 1 file changed, 7 insertions(+), 13 deletions(-)

diff --git a/src/itree.c b/src/itree.c
index d9f9ec8cd6..9c5d8ce142 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -146,7 +146,7 @@ Copyright (C) 2017-2022  Free Software Foundation, Inc.
 
 /* The sentinel node, the null node.  */
 struct interval_node itree_null = {
-  .parent = &itree_null,
+  .parent = NULL, /* never accessed */
   .left = &itree_null,
   .right = &itree_null,
   .begin = PTRDIFF_MIN,
@@ -162,12 +162,8 @@ Copyright (C) 2017-2022  Free Software Foundation, Inc.
 static bool
 null_is_sane (void)
 {
-  /* The sentinel node has most of its fields read-only.
-
-     FIXME: PARENT is still read/write.  It is written to
-     ininterval_tree_transplant, and later read.  --matt
-  */
-  /* eassert (itree_null.parent == &itree_null); */
+  /* All sentinel node fields are read-only.  */
+  eassert (itree_null.parent == NULL);
   eassert (itree_null.left == &itree_null);
   eassert (itree_null.right == &itree_null);
   eassert (itree_null.begin == PTRDIFF_MIN);
@@ -742,7 +738,6 @@ interval_tree_remove_fix (struct interval_tree *tree,
 	      other->red = false;
 	      parent->red = true;
 	      interval_tree_rotate_left (tree, parent);
-	      parent = node->parent;
 	      other = parent->right;
             }
 
@@ -761,7 +756,6 @@ interval_tree_remove_fix (struct interval_tree *tree,
 		  other->left->red = false;
 		  other->red = true;
 		  interval_tree_rotate_right (tree, other);
-		  parent = node->parent;
 		  other = parent->right;
                 }
 	      other->red = parent->red; /* 4.a */
@@ -781,7 +775,6 @@ interval_tree_remove_fix (struct interval_tree *tree,
 	      other->red = false;
 	      parent->red = true;
 	      interval_tree_rotate_right (tree, parent);
-	      parent = node->parent;
 	      other = parent->left;
             }
 
@@ -800,7 +793,6 @@ interval_tree_remove_fix (struct interval_tree *tree,
 		  other->right->red = false;
 		  other->red = true;
 		  interval_tree_rotate_left (tree, other);
-		  parent = node->parent;
 		  other = parent->left;
                 }
 
@@ -881,7 +873,8 @@ interval_tree_remove (struct interval_tree *tree, struct interval_node *node)
       interval_tree_transplant (tree, min, node);
       /* We set min->right->parent after `interval_tree_transplant` so
          that calls to `itree_total_offset` don't get stuck in an inf-loop.  */
-      min->right->parent = min;
+      if (min->right != ITREE_NULL)
+        min->right->parent = min;
       interval_tree_update_limit (min);
       /* This call "belongs" with the first `interval_tree_transplant`
          (of `min_right`, done earlier in the `if`) but we prefer to do it
@@ -1508,7 +1501,8 @@ interval_tree_transplant (struct interval_tree *tree, struct interval_node *sour
   else
     dest->parent->right = source;
 
-  source->parent = dest->parent;
+  if (source != ITREE_NULL)
+    source->parent = dest->parent;
 }
 
 \f
-- 
2.35.1

Re: noverlay branch

[Stefan Monnier]

Matt Armstrong [2022-10-10 20:46:43] wrote:

> Stefan, I read only Eli's reply this morning.  Got to yours just now.
>
>
> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>
>>> I had a different idea of tightening the otree invariant to this:
>>>  1) A node's otick must be greater than or equal to its children's.
>> That's already checked in the current code, right?
> Not yet...until...just now.

??
In the code I have from feature/noverlay I see:

    eassert (node->parent == ITREE_NULL || node->parent->otick >= node->otick);

in `interval_tree_inherit_offset`.

>>>  3) All downward tree traversal propagates offsets and otick.
>> I think we already do that, but if there are places we missed, then yes,
>> of course.
> Yes, I think we do.  The wrinkle is that we don't always start
> inheriting at the root, but otick is not updated in that case.

I don't think propagating `otick` is very important during
tree traversals.

>> Regarding `otick`, I can see 2 more options:
>> - Get rid of it completely: its sole purpose is to try and keep
>>   `overlay-start/end` O(1) in the usual case instead of O(log N), but
>>   I'm not convinced it's worth the cost of propagating `otick` everywhere
>>   all the time.
>> - A halfway point is to keep `otick` but update it more lazily,
>>   i.e. only update it when we do `overlay-start/end` (e.g. in
>>   `interval_tree_validate`).
> These ideas are simpler but similar in direction to my idea to use a
> btree instead.

Sorry, I fail to see the connection to btrees.

>> This max_depth also sounds to me like over-engineering.
> I'd like to keep max_depth.

Sorry, not gonna happen.

> My reason for adding it is informed by experience on similar projects.
> It is easier to understand an assertion that the tree is too deep than
> it is to debug, say, stack overflow when there is a cycle in the link
> structure of the tree.

The purpose of ENABLE_CHECKING assertions is:
- avoid errors remaining undetected.
- document the code.

If it crashes with a stack overflow, it still detects the problem, so
`max_depth` is not necessary for that.

Your checking code is nice and detailed, but it's becoming so large that
it increases the maintenance burden.  I want to make it shorter&simpler.

> It is easier to limit the height of checking if, indeed, on some night
> I am diagnosing an unrelated bug but the perf cost here is too much.

Many people run their Emacs always with ENABLE_CHECKING, so the
performance impact should be minimized.  It's OK to check a node's local
invariants in those places where you visit the node anyway.  It's OK to
check the overall state of the tree in those places where the code will
visit all the nodes anyway, but it's not OK to visit significantly more
nodes just for the check than what the normal code would do, especially
if an error there could be detected sooner or later by cheaper
checks elsewhere.

> With max_depth in place I can easily manually hack up
> a functon to verify checks only in a small subset of the tree
> (e.g. around a rotation operation, etc.).  I've done and benefited from
> this sort of thing in the past.

Yes, it's very helpful *while working on the code*.  But it's easy to
sprinkle many more calls to `check_tree` as needed when you're debugging
an error caught by the cheap checks.  And when you do that you can
temporarily pay the price of full tree traversals.

> There is a small concrete benefit to it right now.  MAX_DEPTH is now
> initialized from interval_tree_max_height(), which currently could wildy
> under estimate the height and we wouldn't notice (because generator
> stacks auto-grow).  Since we call that fucntion to make "big enough to
> not need growing" stacks, it is nice to have test coverage for it.

[ FWIW, I'd like to get rid of the `tree->size` field, and thus rely on
  auto-growing more heavily.  ]

>>> +  result.complete = left_result.complete && right_result.complete;
>>> +  if (result.complete)
>> I think all calls to `check_tree` should be complete traversals.
>> Most of the invariants checked in it are already checked incrementally
>> via sprinkled assertions elsewhere, so it's only really useful when
>> debugging a concrete known issue where the "local" checks aren't good
>> enough.
> All `check_tree` calls are complete traversals.

Great, so we can remove the `result.complete` field.

>> We could also include a few "cheap" calls to `check_tree` via `eassert`
>> (i.e. calls which we know shouldn't be algorithmically too expensive
>> because we're already traversing the whole tree for some other reason,
>> e.g. when killing a buffer (e.g. to verify that, at the end of the day,
>> we still preversed the RB invariants :-) or maybe during GC).
> ...I'm not understanding something here.  All `check_tree` calls are in
> `eassert` already.

But some of them are currently at places where they're unacceptable
because they cost a lot more than the surrounding code.


        Stefan

Re: noverlay branch

[Stefan Monnier]

> ...now 5 commits on https://git.sr.ht/~matta/emacs/log/feature/noverlay

Merged, thanks,


        Stefan

Re: noverlay branch

[Matt Armstrong]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> Matt Armstrong [2022-10-10 20:46:43] wrote:
>
>> Not yet...until...just now.
>
> ??
> In the code I have from feature/noverlay I see:
>
>     eassert (node->parent == ITREE_NULL || node->parent->otick >= node->otick);
>
> in `interval_tree_inherit_offset`.

Oh, yeah.  I was talking only about the `check_tree` function.


>>>>  3) All downward tree traversal propagates offsets and otick.
>>> I think we already do that, but if there are places we missed, then yes,
>>> of course.
>> Yes, I think we do.  The wrinkle is that we don't always start
>> inheriting at the root, but otick is not updated in that case.
>
> I don't think propagating `otick` is very important during
> tree traversals.

I agree.  I can't think of a strong argument to do it.


>>> Regarding `otick`, I can see 2 more options:
>>> - Get rid of it completely: its sole purpose is to try and keep
>>>   `overlay-start/end` O(1) in the usual case instead of O(log N), but
>>>   I'm not convinced it's worth the cost of propagating `otick` everywhere
>>>   all the time.
>>> - A halfway point is to keep `otick` but update it more lazily,
>>>   i.e. only update it when we do `overlay-start/end` (e.g. in
>>>   `interval_tree_validate`).
>> These ideas are simpler but similar in direction to my idea to use a
>> btree instead.
>
> Sorry, I fail to see the connection to btrees.

Just a performance conjecture.  A b-tree is shallower, so your first
idea above is more attractive.


>>> This max_depth also sounds to me like over-engineering.
>> I'd like to keep max_depth.
>
> Sorry, not gonna happen.

[...]

> Yes, it's very helpful *while working on the code*.  But it's easy to
> sprinkle many more calls to `check_tree` as needed when you're debugging
> an error caught by the cheap checks.  And when you do that you can
> temporarily pay the price of full tree traversals.

[...]

> But some of them are currently at places where they're unacceptable
> because they cost a lot more than the surrounding code.

Great, thanks for those explanations.  I am now a little better
calibrated as far as the expected performance of ENABLE_CHECKING code.


> [ FWIW, I'd like to get rid of the `tree->size` field, and thus rely on
>   auto-growing more heavily.  ]

I rather like the size field.  It is one of the first things I look at
when assessing a crash, since it is nice to know whether a tree is small
or enormous.  But, yeah, little else really needs it.

I have a different idea about the stacks, though.  Idea: use fixed size
stacks, no auto-growing.  120 elements is all that is needed (the max
possible depth of a 3-pointer red-black tree on 64 bit architectures).
That is 1K memory overhead per traversal, which I think isn't an issue?
At least, this is a reasonable choice in other systems I've worked in.
Is it reasonable for Emacs?

Re: noverlay branch

[Stefan Monnier]

>>>> Regarding `otick`, I can see 2 more options:
>>>> - Get rid of it completely: its sole purpose is to try and keep
>>>>   `overlay-start/end` O(1) in the usual case instead of O(log N), but
>>>>   I'm not convinced it's worth the cost of propagating `otick` everywhere
>>>>   all the time.
>>>> - A halfway point is to keep `otick` but update it more lazily,
>>>>   i.e. only update it when we do `overlay-start/end` (e.g. in
>>>>   `interval_tree_validate`).
>>> These ideas are simpler but similar in direction to my idea to use a
>>> btree instead.
>> Sorry, I fail to see the connection to btrees.
> Just a performance conjecture.  A b-tree is shallower, so your first
> idea above is more attractive.

I still fail to see the connection: changes in `otick` need to be
propagated everywhere anyway, so the shape of the tree probably doesn't
make much difference.

[...time passe...]

Oh, I think you're talking specifically about the complete removal of
`otick` where a shallower tree would make that less costly.
Sorry.  I understand quickly, but only after a long explanation.

>> [ FWIW, I'd like to get rid of the `tree->size` field, and thus rely on
>>   auto-growing more heavily.  ]
> I rather like the size field.

I agree it has its benefit, which is why I haven't removed it yet:
I'm not sure.

> I have a different idea about the stacks, though.  Idea: use fixed size
> stacks, no auto-growing.  120 elements is all that is needed (the max
> possible depth of a 3-pointer red-black tree on 64 bit architectures).
> That is 1K memory overhead per traversal, which I think isn't an issue?
> At least, this is a reasonable choice in other systems I've worked in.
> Is it reasonable for Emacs?

Maybe you're right.  I think this decision is muddled by the (ab)use of
stacks as collections of nodes at a few places (where we use
`interval_stack_push`), where it's not limited to O(log N).


        Stefan

Re: noverlay branch

[Matt Armstrong]

[-- Attachment #1: Type: text/plain, Size: 1565 bytes --]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> Oh, I think you're talking specifically about the complete removal of
> `otick` where a shallower tree would make that less costly.
> Sorry.  I understand quickly, but only after a long explanation.

That and the basic tree operations (find, insert, remove, etc.).

You are right that there is enough essential updating going on in the
tree that perhaps the btree isn't a win.  I haven't thought about it
deeply.


>>> [ FWIW, I'd like to get rid of the `tree->size` field, and thus rely on
>>>   auto-growing more heavily.  ]
>> I rather like the size field.
>
> I agree it has its benefit, which is why I haven't removed it yet:
> I'm not sure.
>
>> I have a different idea about the stacks, though.  Idea: use fixed size
>> stacks, no auto-growing.  120 elements is all that is needed (the max
>> possible depth of a 3-pointer red-black tree on 64 bit architectures).
>> That is 1K memory overhead per traversal, which I think isn't an issue?
>> At least, this is a reasonable choice in other systems I've worked in.
>> Is it reasonable for Emacs?
>
> Maybe you're right.  I think this decision is muddled by the (ab)use of
> stacks as collections of nodes at a few places (where we use
> `interval_stack_push`), where it's not limited to O(log N).

Could most places use a fixed C array (maybe in a simple struct), with
fancy places still using the fancy thing?

Anyway, today 3 tiny patches.  Two improvements, one bug fix.  Also on
https://git.sr.ht/~matta/emacs/log/feature/noverlay.

And now patches...


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-.clang-format-Add-ITREE_FOREACH.patch --]
[-- Type: text/x-diff, Size: 714 bytes --]

From 034d50415858b18b032b116804bfefc1be421bb3 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Tue, 11 Oct 2022 11:41:47 -0700
Subject: [PATCH 1/3] ; * .clang-format: Add ITREE_FOREACH.

---
 .clang-format | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/.clang-format b/.clang-format
index 44200a3995..ac9f95c88a 100644
--- a/.clang-format
+++ b/.clang-format
@@ -6,7 +6,7 @@ BreakBeforeBinaryOperators: All
 BreakBeforeBraces: GNU
 ColumnLimit: 70
 ContinuationIndentWidth: 2
-ForEachMacros: [FOR_EACH_TAIL, FOR_EACH_TAIL_SAFE]
+ForEachMacros: [FOR_EACH_TAIL, FOR_EACH_TAIL_SAFE, ITREE_FOREACH]
 IncludeCategories:
   - Regex: '^<config\.h>$'
     Priority: -1
-- 
2.35.1


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: 0002-src-itree.c-check_tree-assert-that-the-tree-root-is-.patch --]
[-- Type: text/x-diff, Size: 718 bytes --]

From fda8723be640593a662d7ff9d4900b7f9e56423e Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Tue, 11 Oct 2022 20:32:08 -0700
Subject: [PATCH 2/3] ; * src/itree.c (check_tree): assert that the tree root
 is black

---
 src/itree.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/src/itree.c b/src/itree.c
index ef623d0850..deef0335cf 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -307,6 +307,7 @@ check_tree (struct interval_tree *tree,
   if (tree->root == ITREE_NULL)
     return true;
   eassert (tree->root->parent == ITREE_NULL);
+  eassert (!check_red_black_invariants || !tree->root->red);
 
   struct interval_node *node = tree->root;
   struct check_subtree_result result
-- 
2.35.1


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #4: 0003-src-itree.c-check_subtree-fix-logical-error-in-easse.patch --]
[-- Type: text/x-diff, Size: 852 bytes --]

From a98497429fcb1369bfe2af9d57820eb94ae380dc Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Tue, 11 Oct 2022 20:19:16 -0700
Subject: [PATCH 3/3] ; * src/itree.c (check_subtree): fix logical error in
 eassert

---
 src/itree.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/src/itree.c b/src/itree.c
index deef0335cf..cd6b0b35f8 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -277,7 +277,8 @@ check_subtree (struct interval_node *node,
   if (check_red_black_invariants)
     {
       eassert (left_result.black_height == right_result.black_height);
-      eassert (node->parent != ITREE_NULL || !node->red || !node->parent->red);
+      eassert (node->parent == ITREE_NULL || !node->red
+               || !node->parent->red);
     }
 
   result.size = 1 + left_result.size + right_result.size;
-- 
2.35.1

Re: noverlay branch

[Matt Armstrong]

[-- Attachment #1: Type: text/plain, Size: 552 bytes --]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> ...now 5 commits on https://git.sr.ht/~matta/emacs/log/feature/noverlay
>
> Merged, thanks,

Thanks Stefan, FWIW I don't see the merges on feature/noverlay yet.
Have you pushed?

Attached is what it looks like to remove itree_node entirely.  I like
the result, as I personally find sentinel nodes confusing and slightly
error prone.  I like my new implementation `interval_tree_remove` better
too.  Lemme know what you think.

It needs the 0003 patch also attached below or check_tree will crash.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0003-src-itree.c-check_subtree-fix-logical-error-in-easse.patch --]
[-- Type: text/x-diff, Size: 852 bytes --]

From a98497429fcb1369bfe2af9d57820eb94ae380dc Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Tue, 11 Oct 2022 20:19:16 -0700
Subject: [PATCH 3/4] ; * src/itree.c (check_subtree): fix logical error in
 eassert

---
 src/itree.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/src/itree.c b/src/itree.c
index deef0335cf..cd6b0b35f8 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -277,7 +277,8 @@ check_subtree (struct interval_node *node,
   if (check_red_black_invariants)
     {
       eassert (left_result.black_height == right_result.black_height);
-      eassert (node->parent != ITREE_NULL || !node->red || !node->parent->red);
+      eassert (node->parent == ITREE_NULL || !node->red
+               || !node->parent->red);
     }
 
   result.size = 1 + left_result.size + right_result.size;
-- 
2.35.1


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: 0004-Delete-the-itree_null-sentinel-node-use-NULL-everywh.patch --]
[-- Type: text/x-diff, Size: 19605 bytes --]

From 5ee0b50cf248b13bd3a702208f2b4ef87fdd7723 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Wed, 12 Oct 2022 10:06:03 -0700
Subject: [PATCH 4/4] Delete the itree_null sentinel node, use NULL everywhere.

This effort caught a few (already commited) places that were
dereferencing through ITREE_NULL in a confusing way.  It makes some
functions have to check for NULL in more places, but in my experinece
this is worth it from a code clarity point of view.

In doing this I rewrote `interval_tree_remove` completely.  There
there was one final bug in that function that I simply could not find
when I #define'd ITREE_NULL to NULL.  I couldn't easily understand
that function, so instead I rewrote it completely with a focus on code
clarity.  Bug went away.

I have left the ITREE_NULL #define in code, to reduce code review
noise.  It is easily removed later, mechanically.

* src/itree.h: #define ITREE_NULL to NULL and leave a FIXME.
* src/itree.c (itree_null): Delete the itree_null static variable.
(null_is_sane): Delete (and all callers).
(interval_tree_insert): Insert the first node as black straight away.
(itree_newlimit): Handle NULL children.
(interval_tree_remove_fix): ditto.
(interval_tree_insert_fix): ditto.
(interval_tree_remove): Rewrite for clarity.
(null_safe_is_red): New function.
(null_safe_is_black): New function.
(interval_tree_replace_child): Renamed from interval_tree_transplant.
(interval_tree_transplant): New function that something I think is
more like a full transplantation.  (names are hard)
---
 src/itree.c | 278 ++++++++++++++++++++++++++--------------------------
 src/itree.h |   5 +-
 2 files changed, 140 insertions(+), 143 deletions(-)

diff --git a/src/itree.c b/src/itree.c
index cd6b0b35f8..eacd4c6425 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -140,44 +140,17 @@ Copyright (C) 2017-2022  Free Software Foundation, Inc.
 static void interval_tree_rotate_left (struct interval_tree *, struct interval_node *);
 static void interval_tree_rotate_right (struct interval_tree *, struct interval_node *);
 static void interval_tree_insert_fix (struct interval_tree *, struct interval_node *);
-static void interval_tree_transplant (struct interval_tree *, struct interval_node *, struct interval_node *);
-static struct interval_generator* interval_generator_create (struct interval_tree *);
+static void interval_tree_replace_child (struct interval_tree *,
+					 struct interval_node *,
+					 struct interval_node *);
+static void interval_tree_transplant (struct interval_tree *tree,
+                                      struct interval_node *source,
+                                      struct interval_node *dest);
+static struct interval_generator *
+interval_generator_create (struct interval_tree *);
 static void interval_tree_insert (struct interval_tree *, struct interval_node *);
-
-/* The sentinel node, the null node.  */
-struct interval_node itree_null = {
-  .parent = NULL, /* never accessed */
-  .left = &itree_null,
-  .right = &itree_null,
-  .begin = PTRDIFF_MIN,
-  .end = PTRDIFF_MIN,
-  .limit = PTRDIFF_MIN, /* => max(x, null.limit) = x */
-  .offset = 0,
-  .otick = 0,
-  .red = false,
-  .rear_advance = false,
-  .front_advance = false,
-};
-
-static bool
-null_is_sane (void)
-{
-  /* All sentinel node fields are read-only.  */
-  eassert (itree_null.parent == NULL);
-  eassert (itree_null.left == &itree_null);
-  eassert (itree_null.right == &itree_null);
-  eassert (itree_null.begin == PTRDIFF_MIN);
-  eassert (itree_null.end == PTRDIFF_MIN);
-  eassert (itree_null.limit == PTRDIFF_MIN);
-  eassert (itree_null.offset == 0);
-  eassert (itree_null.otick == 0);
-  eassert (itree_null.red == false);
-  eassert (itree_null.rear_advance == false);
-  eassert (itree_null.front_advance == false);
-
-  /* if we get this far things must be good */
-  return true;
-}
+static bool null_safe_is_red (struct interval_node *node);
+static bool null_safe_is_black (struct interval_node *node);
 
 /* +------------------------------------------------------------------------------------+ */
 
@@ -214,8 +187,6 @@ null_is_sane (void)
 static void
 itree_init (void)
 {
-  eassert (null_is_sane ());
-
   iter = interval_generator_create (NULL);
 }
 
@@ -300,8 +271,6 @@ check_subtree (struct interval_node *node,
 check_tree (struct interval_tree *tree,
             bool check_red_black_invariants)
 {
-  eassert (null_is_sane ());
-
   eassert (tree != NULL);
   eassert (tree->size >= 0);
   eassert ((tree->size == 0) == (tree->root == ITREE_NULL));
@@ -550,7 +519,7 @@ interval_tree_insert (struct interval_tree *tree, struct interval_node *node)
   struct interval_node *child = tree->root;
   uintmax_t otick = tree->otick;
   /* It's the responsability of the caller to set `otick` on the node,
-     to "confirm" that the begin/end fields are uptodate.  */
+     to "confirm" that the begin/end fields are up to date.  */
   eassert (node->otick == otick);
 
   /* Find the insertion point, accumulate node's offset and update
@@ -578,7 +547,7 @@ interval_tree_insert (struct interval_tree *tree, struct interval_node *node)
   node->parent = parent;
   node->left = ITREE_NULL;
   node->right = ITREE_NULL;
-  node->red = true;
+  node->red = node != tree->root;
   node->offset = 0;
   node->limit = node->end;
   eassert (node->parent == ITREE_NULL || node->parent->otick >= node->otick);
@@ -621,8 +590,12 @@ itree_newlimit (struct interval_node *node)
 {
   eassert (node != ITREE_NULL);
   return max (node->end,
-              max (node->left->limit + node->left->offset,
-                   node->right->limit + node->right->offset));
+              max (node->left == ITREE_NULL
+                     ? PTRDIFF_MIN
+                     : node->left->limit + node->left->offset,
+                   node->right == ITREE_NULL
+                     ? PTRDIFF_MIN
+                     : node->right->limit + node->right->offset));
 }
 
 static bool
@@ -654,17 +627,20 @@ interval_tree_remove_fix (struct interval_tree *tree,
                           struct interval_node *node,
                           struct interval_node *parent)
 {
+  if (parent == ITREE_NULL)
+    eassert (node == tree->root);
+  else
   eassert (node == ITREE_NULL || node->parent == parent);
-  eassert (parent == ITREE_NULL
-           || node == parent->left || node == parent->right);
 
-  while (parent != ITREE_NULL && !node->red)
+  while (parent != ITREE_NULL && null_safe_is_black (node))
     {
+      eassert (node == parent->left || node == parent->right);
+
       if (node == parent->left)
 	{
 	  struct interval_node *other = parent->right;
 
-	  if (other->red) /* case 1.a */
+          if (null_safe_is_red (other)) /* case 1.a */
 	    {
 	      other->red = false;
 	      parent->red = true;
@@ -672,8 +648,8 @@ interval_tree_remove_fix (struct interval_tree *tree,
 	      other = parent->right;
             }
 
-	  if (!other->left->red /* 2.a */
-              && !other->right->red)
+          if (null_safe_is_black (other->left) /* 2.a */
+              && null_safe_is_black (other->right))
 	    {
 	      other->red = true;
 	      node = parent;
@@ -682,7 +658,7 @@ interval_tree_remove_fix (struct interval_tree *tree,
             }
 	  else
 	    {
-	      if (!other->right->red) /* 3.a */
+              if (null_safe_is_black (other->right)) /* 3.a */
 		{
 		  other->left->red = false;
 		  other->red = true;
@@ -701,7 +677,7 @@ interval_tree_remove_fix (struct interval_tree *tree,
 	{
 	  struct interval_node *other = parent->left;
 
-	  if (other->red) /* 1.b */
+          if (null_safe_is_red (other)) /* 1.b */
 	    {
 	      other->red = false;
 	      parent->red = true;
@@ -709,8 +685,8 @@ interval_tree_remove_fix (struct interval_tree *tree,
 	      other = parent->left;
             }
 
-	  if (!other->right->red /* 2.b */
-              && !other->left->red)
+          if (null_safe_is_black (other->right) /* 2.b */
+              && null_safe_is_black (other->left))
 	    {
 	      other->red = true;
 	      node = parent;
@@ -719,7 +695,7 @@ interval_tree_remove_fix (struct interval_tree *tree,
             }
 	  else
 	    {
-	      if (!other->left->red) /* 3.b */
+              if (null_safe_is_black (other->left)) /* 3.b */
 		{
 		  other->right->red = false;
 		  other->red = true;
@@ -737,6 +713,7 @@ interval_tree_remove_fix (struct interval_tree *tree,
         }
     }
 
+  if (node != ITREE_NULL)
   node->red = false;
 }
 
@@ -748,86 +725,70 @@ interval_tree_remove (struct interval_tree *tree, struct interval_node *node)
   eassert (interval_tree_contains (tree, node));
   eassert (check_tree (tree, true)); /* FIXME: Too expensive.  */
 
-  /* `broken`, if non-NULL, holds a node that's being moved up to where a black
-     node used to be, which may thus require further fixups in its parents
-     (done in `interval_tree_remove_fix`).  */
-  struct interval_node *broken = NULL;
-  /* `broken` may be null but `interval_tree_remove_fix` still
-     needs to know its "parent".
-     Cormen et al.'s Introduction to Algorithms uses a trick where
-     they rely on the null sentinel node's `parent` field to hold
-     the right value.  While this works, it breaks the rule that
-     the `parent` field is write-only making correctness much more tricky
-     and introducing a dependency on a global state (which is incompatible
-     with concurrency among other things), so instead we keep track of
-     `broken`'s parent manually.  */
-  struct interval_node *broken_parent = NULL;
-
+  /* Find `splice`, the leaf node to splice out of the tree.  When
+     `node` has at most one child this is `node` itself.  Otherwise,
+     it is the in order successor of `node`.  */
   interval_tree_inherit_offset (tree->otick, node);
-  if (node->left == ITREE_NULL || node->right == ITREE_NULL)
-    {
-      struct interval_node *subst
-	= node->right == ITREE_NULL ? node->left : node->right;
-      if (!node->red)
-        {
-          broken = subst;
-          broken_parent = node->parent; /* The future parent.  */
-        }
-      interval_tree_transplant (tree, subst, node);
-    }
-  else
+  struct interval_node *splice
+    = (node->left == ITREE_NULL || node->right == ITREE_NULL)
+        ? node
+        : interval_tree_subtree_min (tree->otick, node->right);
+
+  /* Find `subtree`, the only child of `splice` (may be NULL).  Note:
+     `subtree` will not be modified other than changing its parent to
+     `splice`.  */
+  eassert (splice->left == ITREE_NULL || splice->right == ITREE_NULL);
+  struct interval_node *subtree
+    = (splice->left != ITREE_NULL) ? splice->left : splice->right;
+
+  /* Save a pointer to the parent of where `subtree` will eventually
+     be in `subtree_parent`.  */
+  struct interval_node *subtree_parent
+    = (splice->parent != node) ? splice->parent : splice;
+
+  /* If `splice` is black removing it may violate Red-Black
+     invariants, so note this for later.  */
+
+  /* Replace `splice` with `subtree` under subtree's parent.  If
+     `splice` is black, this creates a red-red violation, so remember
+     this now as the field can be overwritten when splice is
+     transplanted below.  */
+  interval_tree_replace_child (tree, subtree, splice);
+  bool removed_black = !splice->red;
+
+  /* Replace `node` with `splice` in the tree and propagate limit
+     upwards, if necessary.  Note: Limit propagation can stabilize at
+     any point, so we must call from bottom to top for every node that
+     has a new child.  */
+  if (splice != node)
     {
-      struct interval_node *min
-        = interval_tree_subtree_min (tree->otick, node->right);
-      struct interval_node *min_right = min->right;
-      struct interval_node *min_parent = min->parent;
-
-      if (!min->red)
-        broken = min_right;
-      eassert (min != ITREE_NULL);
-      /* `min` should not have any offsets any more so we can move nodes
-         underneath it without risking changing their begin/end.  */
-      eassert (min->offset == 0);
-      if (min->parent == node)
-        broken_parent = min; /* The future parent.  */
-      else
-        {
-          interval_tree_transplant (tree, min_right, min);
-          broken_parent = min->parent; /* The parent.  */
-          min->right = node->right;
-        }
-      min->left = node->left;
-      min->left->parent = min;
-      min->red = node->red;
-      /* FIXME: At this point node->right->parent = min but node->right
-         is a parent of `min` so total_offsets gets stuck in an inf-loop!  */
-      interval_tree_transplant (tree, min, node);
-      /* We set min->right->parent after `interval_tree_transplant` so
-         that calls to `itree_total_offset` don't get stuck in an inf-loop.  */
-      if (min->right != ITREE_NULL)
-        min->right->parent = min;
-      interval_tree_update_limit (min);
-      /* This call "belongs" with the first `interval_tree_transplant`
-         (of `min_right`, done earlier in the `if`) but we prefer to do it
-         here ("late") because otherwise it would sometimes update part of
-         the tree with values that would be invalidated by the second
-         `interval_tree_transplant`.  */
-      interval_tree_propagate_limit (min_parent);
+      interval_tree_transplant (tree, splice, node);
+      interval_tree_propagate_limit (subtree_parent);
+      if (splice != subtree_parent)
+        interval_tree_propagate_limit (splice);
     }
-  interval_tree_propagate_limit (node->parent);
-  --tree->size;
+  interval_tree_propagate_limit (splice->parent);
 
-  if (broken)
-    {
-      eassert (check_tree (tree, false)); /* FIXME: Too expensive.  */
-      interval_tree_remove_fix (tree, broken, broken_parent);
-    }
+  --tree->size;
 
-  node->right = node->left = node->parent = NULL;
+  /* Fix any black height violation caused by removing a black
+     node.  */
+  if (removed_black)
+    interval_tree_remove_fix (tree, subtree, subtree_parent);
 
   eassert ((tree->size == 0) == (tree->root == ITREE_NULL));
   eassert (check_tree (tree, true)); /* FIXME: Too expensive.  */
 
+  /* Clear fields related to the tree for sanity while debugging.  */
+  node->red = false;
+  node->right = node->left = node->parent = NULL;
+  node->limit = 0;
+
+  /* Must be clean (all offsets applied).  Also, some callers rely on
+     node's otick being the tree's otick.  */
+  eassert (node->otick == tree->otick);
+  eassert (node->offset == 0);
+
   return node;
 }
 
@@ -861,7 +822,6 @@ interval_tree_iter_start (struct interval_tree *tree,
                           enum interval_tree_order order,
 			  const char* file, int line)
 {
-  eassert (null_is_sane ());
   /* struct interval_generator *iter = tree->iter; */
   if (iter->running)
     {
@@ -1172,6 +1132,18 @@ interval_generator_narrow (struct interval_generator *g,
  * | Internal Functions
  * +===================================================================================+ */
 
+static bool
+null_safe_is_red (struct interval_node *node)
+{
+  return node != ITREE_NULL && node->red;
+}
+
+static bool
+null_safe_is_black (struct interval_node *node)
+{
+  return node == ITREE_NULL || !node->red; /* NULL nodes are black */
+}
+
 /* Update NODE's limit attribute according to its children. */
 
 static void
@@ -1225,9 +1197,6 @@ interval_tree_inherit_offset (uintmax_t otick, struct interval_node *node)
 
 /* Update limit of NODE and its ancestors.  Stop when it becomes
    stable, i.e. new_limit = old_limit.
-
-   NODE may also be the null node, in which case its parent is
-   used. (This feature is due to the RB algorithm.)
 */
 
 static void
@@ -1332,7 +1301,9 @@ interval_tree_rotate_right (struct interval_tree *tree, struct interval_node *no
 static void
 interval_tree_insert_fix (struct interval_tree *tree, struct interval_node *node)
 {
-  while (node->parent->red)
+  eassert (tree->root->red == false);
+
+  while (null_safe_is_red (node->parent))
     {
       /* NODE is red and its parent is red.  This is a violation of
 	 red-black tree property #3.  */
@@ -1344,7 +1315,7 @@ interval_tree_insert_fix (struct interval_tree *tree, struct interval_node *node
 	     our "uncle".  */
 	  struct interval_node *uncle = node->parent->parent->right;
 
-	  if (uncle->red) /* case 1.a */
+          if (null_safe_is_red (uncle)) /* case 1.a */
 	    {
 	      /* Uncle and parent are red but should be black because
 		 NODE is red.  Change the colors accordingly and
@@ -1374,7 +1345,7 @@ interval_tree_insert_fix (struct interval_tree *tree, struct interval_node *node
 	  /* This is the symmetrical case of above.  */
 	  struct interval_node *uncle = node->parent->parent->left;
 
-	  if (uncle->red) /* case 1.b */
+          if (null_safe_is_red (uncle)) /* case 1.b */
 	    {
 	      node->parent->red = false;
 	      uncle->red = false;
@@ -1416,15 +1387,20 @@ itree_total_offset (struct interval_node *node)
   return offset;
 }
 
-/* Link node SOURCE in DEST's place.
-   It's the caller's responsability to refresh the `limit`s
-   of DEST->parents afterwards.  */
+/* Replace DEST with SOURCE as a child of DEST's parent.  Adjusts
+   *only* the parent linkage of SOURCE and either the parent's child
+   link the tree root.
+
+   Warning: DEST is left unmodified.  SOURCE's child links are
+   unchanged.  Caller is responsible for recalculation of `limit`.
+   Requires both nodes to be using the same effective `offset`.  */
 
 static void
-interval_tree_transplant (struct interval_tree *tree, struct interval_node *source,
-                          struct interval_node *dest)
+interval_tree_replace_child (struct interval_tree *tree,
+                             struct interval_node *source,
+                             struct interval_node *dest)
 {
-  eassert (tree && source && dest && dest != ITREE_NULL);
+  eassert (tree && dest != ITREE_NULL);
   eassert (source == ITREE_NULL
            || itree_total_offset (source) == itree_total_offset (dest));
 
@@ -1439,6 +1415,28 @@ interval_tree_transplant (struct interval_tree *tree, struct interval_node *sour
     source->parent = dest->parent;
 }
 
+/* Replace DEST with SOURCE in the tree.  Copies the following fields
+   from DEST to SOURCE: red, parent, left, right.  Also updates
+   parent, left and right in surrounding nodes to point to SOURCE.
+
+   Warning: DEST is left unmodified.  Caller is responsible for
+   recalculation of `limit`.  Requires both nodes to be using the same
+   effective `offset`. */
+static void
+interval_tree_transplant (struct interval_tree *tree,
+                          struct interval_node *source,
+                          struct interval_node *dest)
+{
+  interval_tree_replace_child (tree, source, dest);
+  source->left = dest->left;
+  if (source->left != ITREE_NULL)
+    source->left->parent = source;
+  source->right = dest->right;
+  if (source->right != ITREE_NULL)
+    source->right->parent = source;
+  source->red = dest->red;
+}
+
 \f
 /* +===================================================================================+
  * | Debugging
diff --git a/src/itree.h b/src/itree.h
index 5733ec1530..0e2e7d1f81 100644
--- a/src/itree.h
+++ b/src/itree.h
@@ -95,9 +95,8 @@ #define ITREE_H
   bool_bf front_advance : 1;    /* Same as for marker and overlays.  */
 };
 
-/* The sentinel node, the null node.  */
-extern struct interval_node itree_null;
-#define ITREE_NULL (&itree_null)
+/* FIXME: replace ITREE_NULL -> NULL everywhere  */
+#define ITREE_NULL NULL
 
 struct interval_tree
 {
-- 
2.35.1

Re: noverlay branch

[Stefan Monnier]

> --- a/src/itree.c
> +++ b/src/itree.c
> @@ -307,6 +307,7 @@ check_tree (struct interval_tree *tree,
>    if (tree->root == ITREE_NULL)
>      return true;
>    eassert (tree->root->parent == ITREE_NULL);
> +  eassert (!check_red_black_invariants || !tree->root->red);
>  
>    struct interval_node *node = tree->root;
>    struct check_subtree_result result

Does any part of the code care about that?  I can't see anything that
would break if this invariant is not satisfied (both in terms of
correct behavior and in terms of performance).  IOW it seems more like
an accident than something important would should check.

>      {
>        eassert (left_result.black_height == right_result.black_height);
> -      eassert (node->parent != ITREE_NULL || !node->red || !node->parent->red);
> +      eassert (node->parent == ITREE_NULL || !node->red
> +               || !node->parent->red);
>      }

Duh!  Thanks,


        Stefan

Re: noverlay branch

[Matt Armstrong]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> --- a/src/itree.c
>> +++ b/src/itree.c
>> @@ -307,6 +307,7 @@ check_tree (struct interval_tree *tree,
>>    if (tree->root == ITREE_NULL)
>>      return true;
>>    eassert (tree->root->parent == ITREE_NULL);
>> +  eassert (!check_red_black_invariants || !tree->root->red);
>>
>>    struct interval_node *node = tree->root;
>>    struct check_subtree_result result
>
> Does any part of the code care about that?  I can't see anything that
> would break if this invariant is not satisfied (both in terms of
> correct behavior and in terms of performance).  IOW it seems more like
> an accident than something important would should check.

That is a can of subtle worms.

As a practical matter, `interval_tree_insert_fix` asserts it, and that
was failing for me.  I wanted it to fail earlier.

TLDR: That the root be black isn't an essential proeprty of Red-Black
trees.  We could relax it, but that is uncommon practice and would
slightly complicate `interval_tree_insert_fix`.

Corman et. al. doesn't list it as one of the four "red-black
properties", but read on.

Harper, Sen and Tarjan's Rank Balanced Trees paper
(http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf) reformulates
Red-Black trees in terms of rank differences of a node and its parent.
In their formulation, there is an equivalence between Red-Black "color"
and the rank difference between a node and its parent.  Since the root
has no parent, they say the root has no color.  So I think you could
prove that the root's color doesn't matter -- it is inexpressible in an
equivalent formulation of the same class of trees.

But then you get to the implementation, where Corman et. al., subtly
placed deep in their description of their "RB-Insert" function (at least
in my old copy), says this:

  > We have made the important assumption that the root of the tree is
  > black -- a property we guarante in line 18 [...]

Why, because, in my copy, they do this:

  if p[x] = left[p[p[x]]]

which is ill defined if p[x] is a red root -- there is no p[p[x]].  They
want a guarantee that p[p[x]] exists.  They've already checked that p[x]
is red, so they just say root can't be red to save a check that p[x] is
not the root.

(Let me chime in here that I *dislike* it when textbook authors do this
kind of thing, especially in books aimed at undergrads.  They
prominently list four essential Red-Black tree properties, and promptly
write code that relies on additional invariants they toss in to make
their pseudo-code look nicer.  I actually remember looking at this
p[p[x]] and struggling to figure out how the four "red-black properties"
made that safe, then finding that little note burried at the end of a
paragraph in their voluminous text, and getting angry.  It is almost as
if they had no appreciation for their poor young readers minds being
completely full just understanding the very basics.  That was nearly
three decades ago!  A formative memory in the folly of being too
clever.)

Our code is the same in `interval_tree_inherit_offset`:

     if (node->parent == node->parent->parent->left)
	{

If node->parent is a red root that'll crash even with sentinel nodes
(after my change to give even them a truly NULL parent).

At long last, I think we could change this in `interval_tree_insert_fix`:

  while (null_safe_is_red (node->parent))
    {

to this:

  while (null_safe_is_red (node->parent) && node->parent != tree->root)
    {

...and then we could allow red roots.

I'm inclined to keep it the way it is, if only for reasons of inertia.
Most future maintainers coming to Red-Black tree code will have the
"Corman et. al." mindset.

Re: noverlay branch

[Stefan Monnier]

> Thanks Stefan, FWIW I don't see the merges on feature/noverlay yet.
> Have you pushed?

Hmm... I think so, yes.  `git log` tells me:

    commit 65a7b5a802a15daa6274403fef822ec3c9b95469 (HEAD -> noverlay, origin/feature/noverlay)
    Author: Matt Armstrong <matt@rfc20.org>
    Date:   Tue Oct 11 20:19:16 2022 -0700
    
        ; * src/itree.c (check_subtree): fix logical error in eassert
    
    commit fda8723be640593a662d7ff9d4900b7f9e56423e
    Author: Matt Armstrong <matt@rfc20.org>
    Date:   Tue Oct 11 20:32:08 2022 -0700
    
        ; * src/itree.c (check_tree): assert that the tree root is black
    
    commit 034d50415858b18b032b116804bfefc1be421bb3
    Author: Matt Armstrong <matt@rfc20.org>
    Date:   Tue Oct 11 11:41:47 2022 -0700
    
        ; * .clang-format: Add ITREE_FOREACH.
    
    commit 12836db6e4e09378d41301b3d4e1fcff58132d3a
    Author: Stefan Monnier <monnier@iro.umontreal.ca>
    Date:   Tue Oct 11 11:17:44 2022 -0400
    
        itree.c (check_tree): Simplify
        
        * src/itree.c (struct check_subtree_result): Remove `complete`.
        (check_subtree): Remove `max_depth` arg (and adjust callers).
        Use 0 as black-depth of empty tree.
        Remove redundant `node->parent` check (already performed by the caller).
        (check_tree): Replace with `check_tree_common` (update all callers).
        Check the root's `parent` field.
        (check_tree_no_rb): Delete function, inlined in its sole caller.
        (interval_tree_remove): Add call to `check_tree` (without RB checks)
        before `interval_tree_remove_fix`.  Move update of `size`
        field accordingly.
    
    commit da0387f0fe79f577fae6d5453c758f600e1ae495
    Author: Matt Armstrong <matt@rfc20.org>
    Date:   Mon Oct 10 10:45:05 2022 -0700
    
        Stop reading and writing the itree_null.parent field entirely.
        
        With this change all fields in the itree_null sentinel are read only.
        This makes accessing itree_null thread safe in an obvious way.
        
        Because it took two commits from two peole to get this right, I think
        we can call this design fragile and difficult to reason about.
        Another benefit of this commit is as preparation for removing sentinel
        node completely, and just using NULL.
        
        * src/itree.c (itree_null): Statically initialize itree_null.parent to
        NULL.  It is never accessed.
        (null_is_sane): Assert parent == NULL.
        (interval_tree_remove_fix): Remove unecessary assignments to parent
        from node->parent.  These were the last places itree_null.parent were
        read.
        (interval_tree_remove): Avoid an assignment to itree_null.parent
        through min->right->parent.
        (interval_tree_transplant): Avoid an assignment to itree_null.parent
        through source->parent.
    [...]


-- Stefan

Re: noverlay branch

[Stefan Monnier]

> As a practical matter, `interval_tree_insert_fix` asserts it, and that
> was failing for me.  I wanted it to fail earlier.

Ah, I see we depend on it in our implementation of insertion.  OK.
Then maybe it's best to keep this assertion in the insertion code
or at least add a node explaining why we require it.

> I'm inclined to keep it the way it is, if only for reasons of inertia.

I have no trouble with it, indeed.  It's just subtle enough to warrant
a comment.


        Stefan

Re: noverlay branch

[Ihor Radchenko]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> There are a couple of glitches though:
>> 1. hl-line-mode overlay sometimes disappear
>> 2. notmuch search buffer hides text in wrong places (see the attached video)
>
> Hmm... that's worrisome.
>
>> Should I report these things as proper bugs or is it OK to discuss them
>> within this thread?
>
> As Eli said, bug-reports are best.  I don't read the bug-reports list,
> so I'd appreciate if you can add me to the `X-Debbugs-Cc:` when you
> report those bugs.

Sorry, I forgot about X-Debbugs-Cc, but I did report the bugs:

1. bug#58478 Already fixed; unrelated to noverlay branch.
2. bug#58479

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

Re: noverlay branch

[Matt Armstrong]

[-- Attachment #1: Type: text/plain, Size: 501 bytes --]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> Thanks Stefan, FWIW I don't see the merges on feature/noverlay yet.
>> Have you pushed?
>
> Hmm... I think so, yes.  `git log` tells me:
>
>     commit 65a7b5a802a15daa6274403fef822ec3c9b95469 (HEAD -> noverlay, origin/feature/noverlay)
>     Author: Matt Armstrong <matt@rfc20.org>
>     Date:   Tue Oct 11 20:19:16 2022 -0700
>
>         ; * src/itree.c (check_subtree): fix logical error in eassert

Ah, but one patch was missed (the biggie):


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Delete-the-itree_null-sentinel-node-use-NULL-everywh.patch --]
[-- Type: text/x-diff, Size: 19601 bytes --]

From 82125d32c5170bcc6ecf480be1f8265524f0aa4e Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Wed, 12 Oct 2022 10:06:03 -0700
Subject: [PATCH] Delete the itree_null sentinel node, use NULL everywhere.

This effort caught a few (already commited) places that were
dereferencing through ITREE_NULL in a confusing way.  It makes some
functions have to check for NULL in more places, but in my experinece
this is worth it from a code clarity point of view.

In doing this I rewrote `interval_tree_remove` completely.  There
there was one final bug in that function that I simply could not find
when I #define'd ITREE_NULL to NULL.  I couldn't easily understand
that function, so instead I rewrote it completely with a focus on code
clarity.  Bug went away.

I have left the ITREE_NULL #define in code, to reduce code review
noise.  It is easily removed later, mechanically.

* src/itree.h: #define ITREE_NULL to NULL and leave a FIXME.
* src/itree.c (itree_null): Delete the itree_null static variable.
(null_is_sane): Delete (and all callers).
(interval_tree_insert): Insert the first node as black straight away.
(itree_newlimit): Handle NULL children.
(interval_tree_remove_fix): ditto.
(interval_tree_insert_fix): ditto.
(interval_tree_remove): Rewrite for clarity.
(null_safe_is_red): New function.
(null_safe_is_black): New function.
(interval_tree_replace_child): Renamed from interval_tree_transplant.
(interval_tree_transplant): New function that something I think is
more like a full transplantation.  (names are hard)
---
 src/itree.c | 278 ++++++++++++++++++++++++++--------------------------
 src/itree.h |   5 +-
 2 files changed, 140 insertions(+), 143 deletions(-)

diff --git a/src/itree.c b/src/itree.c
index 1728a8ab3a..6e2dfc6567 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -140,44 +140,17 @@ Copyright (C) 2017-2022  Free Software Foundation, Inc.
 static void interval_tree_rotate_left (struct interval_tree *, struct interval_node *);
 static void interval_tree_rotate_right (struct interval_tree *, struct interval_node *);
 static void interval_tree_insert_fix (struct interval_tree *, struct interval_node *);
-static void interval_tree_transplant (struct interval_tree *, struct interval_node *, struct interval_node *);
-static struct interval_generator* interval_generator_create (struct interval_tree *);
+static void interval_tree_replace_child (struct interval_tree *,
+					 struct interval_node *,
+					 struct interval_node *);
+static void interval_tree_transplant (struct interval_tree *tree,
+                                      struct interval_node *source,
+                                      struct interval_node *dest);
+static struct interval_generator *
+interval_generator_create (struct interval_tree *);
 static void interval_tree_insert (struct interval_tree *, struct interval_node *);
-
-/* The sentinel node, the null node.  */
-struct interval_node itree_null = {
-  .parent = NULL, /* never accessed */
-  .left = &itree_null,
-  .right = &itree_null,
-  .begin = PTRDIFF_MIN,
-  .end = PTRDIFF_MIN,
-  .limit = PTRDIFF_MIN, /* => max(x, null.limit) = x */
-  .offset = 0,
-  .otick = 0,
-  .red = false,
-  .rear_advance = false,
-  .front_advance = false,
-};
-
-static bool
-null_is_sane (void)
-{
-  /* All sentinel node fields are read-only.  */
-  eassert (itree_null.parent == NULL);
-  eassert (itree_null.left == &itree_null);
-  eassert (itree_null.right == &itree_null);
-  eassert (itree_null.begin == PTRDIFF_MIN);
-  eassert (itree_null.end == PTRDIFF_MIN);
-  eassert (itree_null.limit == PTRDIFF_MIN);
-  eassert (itree_null.offset == 0);
-  eassert (itree_null.otick == 0);
-  eassert (itree_null.red == false);
-  eassert (itree_null.rear_advance == false);
-  eassert (itree_null.front_advance == false);
-
-  /* if we get this far things must be good */
-  return true;
-}
+static bool null_safe_is_red (struct interval_node *node);
+static bool null_safe_is_black (struct interval_node *node);
 
 /* +------------------------------------------------------------------------------------+ */
 
@@ -214,8 +187,6 @@ null_is_sane (void)
 static void
 itree_init (void)
 {
-  eassert (null_is_sane ());
-
   iter = interval_generator_create (NULL);
 }
 
@@ -299,8 +270,6 @@ check_subtree (struct interval_node *node,
 check_tree (struct interval_tree *tree,
             bool check_red_black_invariants)
 {
-  eassert (null_is_sane ());
-
   eassert (tree != NULL);
   eassert (tree->size >= 0);
   eassert ((tree->size == 0) == (tree->root == ITREE_NULL));
@@ -549,7 +518,7 @@ interval_tree_insert (struct interval_tree *tree, struct interval_node *node)
   struct interval_node *child = tree->root;
   uintmax_t otick = tree->otick;
   /* It's the responsability of the caller to set `otick` on the node,
-     to "confirm" that the begin/end fields are uptodate.  */
+     to "confirm" that the begin/end fields are up to date.  */
   eassert (node->otick == otick);
 
   /* Find the insertion point, accumulate node's offset and update
@@ -577,7 +546,7 @@ interval_tree_insert (struct interval_tree *tree, struct interval_node *node)
   node->parent = parent;
   node->left = ITREE_NULL;
   node->right = ITREE_NULL;
-  node->red = true;
+  node->red = node != tree->root;
   node->offset = 0;
   node->limit = node->end;
   eassert (node->parent == ITREE_NULL || node->parent->otick >= node->otick);
@@ -620,8 +589,12 @@ itree_newlimit (struct interval_node *node)
 {
   eassert (node != ITREE_NULL);
   return max (node->end,
-              max (node->left->limit + node->left->offset,
-                   node->right->limit + node->right->offset));
+              max (node->left == ITREE_NULL
+                     ? PTRDIFF_MIN
+                     : node->left->limit + node->left->offset,
+                   node->right == ITREE_NULL
+                     ? PTRDIFF_MIN
+                     : node->right->limit + node->right->offset));
 }
 
 static bool
@@ -653,17 +626,20 @@ interval_tree_remove_fix (struct interval_tree *tree,
                           struct interval_node *node,
                           struct interval_node *parent)
 {
+  if (parent == ITREE_NULL)
+    eassert (node == tree->root);
+  else
   eassert (node == ITREE_NULL || node->parent == parent);
-  eassert (parent == ITREE_NULL
-           || node == parent->left || node == parent->right);
 
-  while (parent != ITREE_NULL && !node->red)
+  while (parent != ITREE_NULL && null_safe_is_black (node))
     {
+      eassert (node == parent->left || node == parent->right);
+
       if (node == parent->left)
 	{
 	  struct interval_node *other = parent->right;
 
-	  if (other->red) /* case 1.a */
+          if (null_safe_is_red (other)) /* case 1.a */
 	    {
 	      other->red = false;
 	      parent->red = true;
@@ -671,8 +647,8 @@ interval_tree_remove_fix (struct interval_tree *tree,
 	      other = parent->right;
             }
 
-	  if (!other->left->red /* 2.a */
-              && !other->right->red)
+          if (null_safe_is_black (other->left) /* 2.a */
+              && null_safe_is_black (other->right))
 	    {
 	      other->red = true;
 	      node = parent;
@@ -681,7 +657,7 @@ interval_tree_remove_fix (struct interval_tree *tree,
             }
 	  else
 	    {
-	      if (!other->right->red) /* 3.a */
+              if (null_safe_is_black (other->right)) /* 3.a */
 		{
 		  other->left->red = false;
 		  other->red = true;
@@ -700,7 +676,7 @@ interval_tree_remove_fix (struct interval_tree *tree,
 	{
 	  struct interval_node *other = parent->left;
 
-	  if (other->red) /* 1.b */
+          if (null_safe_is_red (other)) /* 1.b */
 	    {
 	      other->red = false;
 	      parent->red = true;
@@ -708,8 +684,8 @@ interval_tree_remove_fix (struct interval_tree *tree,
 	      other = parent->left;
             }
 
-	  if (!other->right->red /* 2.b */
-              && !other->left->red)
+          if (null_safe_is_black (other->right) /* 2.b */
+              && null_safe_is_black (other->left))
 	    {
 	      other->red = true;
 	      node = parent;
@@ -718,7 +694,7 @@ interval_tree_remove_fix (struct interval_tree *tree,
             }
 	  else
 	    {
-	      if (!other->left->red) /* 3.b */
+              if (null_safe_is_black (other->left)) /* 3.b */
 		{
 		  other->right->red = false;
 		  other->red = true;
@@ -736,6 +712,7 @@ interval_tree_remove_fix (struct interval_tree *tree,
         }
     }
 
+  if (node != ITREE_NULL)
   node->red = false;
 }
 
@@ -747,86 +724,70 @@ interval_tree_remove (struct interval_tree *tree, struct interval_node *node)
   eassert (interval_tree_contains (tree, node));
   eassert (check_tree (tree, true)); /* FIXME: Too expensive.  */
 
-  /* `broken`, if non-NULL, holds a node that's being moved up to where a black
-     node used to be, which may thus require further fixups in its parents
-     (done in `interval_tree_remove_fix`).  */
-  struct interval_node *broken = NULL;
-  /* `broken` may be null but `interval_tree_remove_fix` still
-     needs to know its "parent".
-     Cormen et al.'s Introduction to Algorithms uses a trick where
-     they rely on the null sentinel node's `parent` field to hold
-     the right value.  While this works, it breaks the rule that
-     the `parent` field is write-only making correctness much more tricky
-     and introducing a dependency on a global state (which is incompatible
-     with concurrency among other things), so instead we keep track of
-     `broken`'s parent manually.  */
-  struct interval_node *broken_parent = NULL;
-
+  /* Find `splice`, the leaf node to splice out of the tree.  When
+     `node` has at most one child this is `node` itself.  Otherwise,
+     it is the in order successor of `node`.  */
   interval_tree_inherit_offset (tree->otick, node);
-  if (node->left == ITREE_NULL || node->right == ITREE_NULL)
-    {
-      struct interval_node *subst
-	= node->right == ITREE_NULL ? node->left : node->right;
-      if (!node->red)
-        {
-          broken = subst;
-          broken_parent = node->parent; /* The future parent.  */
-        }
-      interval_tree_transplant (tree, subst, node);
-    }
-  else
+  struct interval_node *splice
+    = (node->left == ITREE_NULL || node->right == ITREE_NULL)
+        ? node
+        : interval_tree_subtree_min (tree->otick, node->right);
+
+  /* Find `subtree`, the only child of `splice` (may be NULL).  Note:
+     `subtree` will not be modified other than changing its parent to
+     `splice`.  */
+  eassert (splice->left == ITREE_NULL || splice->right == ITREE_NULL);
+  struct interval_node *subtree
+    = (splice->left != ITREE_NULL) ? splice->left : splice->right;
+
+  /* Save a pointer to the parent of where `subtree` will eventually
+     be in `subtree_parent`.  */
+  struct interval_node *subtree_parent
+    = (splice->parent != node) ? splice->parent : splice;
+
+  /* If `splice` is black removing it may violate Red-Black
+     invariants, so note this for later.  */
+
+  /* Replace `splice` with `subtree` under subtree's parent.  If
+     `splice` is black, this creates a red-red violation, so remember
+     this now as the field can be overwritten when splice is
+     transplanted below.  */
+  interval_tree_replace_child (tree, subtree, splice);
+  bool removed_black = !splice->red;
+
+  /* Replace `node` with `splice` in the tree and propagate limit
+     upwards, if necessary.  Note: Limit propagation can stabilize at
+     any point, so we must call from bottom to top for every node that
+     has a new child.  */
+  if (splice != node)
     {
-      struct interval_node *min
-        = interval_tree_subtree_min (tree->otick, node->right);
-      struct interval_node *min_right = min->right;
-      struct interval_node *min_parent = min->parent;
-
-      if (!min->red)
-        broken = min_right;
-      eassert (min != ITREE_NULL);
-      /* `min` should not have any offsets any more so we can move nodes
-         underneath it without risking changing their begin/end.  */
-      eassert (min->offset == 0);
-      if (min->parent == node)
-        broken_parent = min; /* The future parent.  */
-      else
-        {
-          interval_tree_transplant (tree, min_right, min);
-          broken_parent = min->parent; /* The parent.  */
-          min->right = node->right;
-        }
-      min->left = node->left;
-      min->left->parent = min;
-      min->red = node->red;
-      /* FIXME: At this point node->right->parent = min but node->right
-         is a parent of `min` so total_offsets gets stuck in an inf-loop!  */
-      interval_tree_transplant (tree, min, node);
-      /* We set min->right->parent after `interval_tree_transplant` so
-         that calls to `itree_total_offset` don't get stuck in an inf-loop.  */
-      if (min->right != ITREE_NULL)
-        min->right->parent = min;
-      interval_tree_update_limit (min);
-      /* This call "belongs" with the first `interval_tree_transplant`
-         (of `min_right`, done earlier in the `if`) but we prefer to do it
-         here ("late") because otherwise it would sometimes update part of
-         the tree with values that would be invalidated by the second
-         `interval_tree_transplant`.  */
-      interval_tree_propagate_limit (min_parent);
+      interval_tree_transplant (tree, splice, node);
+      interval_tree_propagate_limit (subtree_parent);
+      if (splice != subtree_parent)
+        interval_tree_propagate_limit (splice);
     }
-  interval_tree_propagate_limit (node->parent);
-  --tree->size;
+  interval_tree_propagate_limit (splice->parent);
 
-  if (broken)
-    {
-      eassert (check_tree (tree, false)); /* FIXME: Too expensive.  */
-      interval_tree_remove_fix (tree, broken, broken_parent);
-    }
+  --tree->size;
 
-  node->right = node->left = node->parent = NULL;
+  /* Fix any black height violation caused by removing a black
+     node.  */
+  if (removed_black)
+    interval_tree_remove_fix (tree, subtree, subtree_parent);
 
   eassert ((tree->size == 0) == (tree->root == ITREE_NULL));
   eassert (check_tree (tree, true)); /* FIXME: Too expensive.  */
 
+  /* Clear fields related to the tree for sanity while debugging.  */
+  node->red = false;
+  node->right = node->left = node->parent = NULL;
+  node->limit = 0;
+
+  /* Must be clean (all offsets applied).  Also, some callers rely on
+     node's otick being the tree's otick.  */
+  eassert (node->otick == tree->otick);
+  eassert (node->offset == 0);
+
   return node;
 }
 
@@ -860,7 +821,6 @@ interval_tree_iter_start (struct interval_tree *tree,
                           enum interval_tree_order order,
 			  const char* file, int line)
 {
-  eassert (null_is_sane ());
   /* struct interval_generator *iter = tree->iter; */
   if (iter->running)
     {
@@ -1171,6 +1131,18 @@ interval_generator_narrow (struct interval_generator *g,
  * | Internal Functions
  * +===================================================================================+ */
 
+static bool
+null_safe_is_red (struct interval_node *node)
+{
+  return node != ITREE_NULL && node->red;
+}
+
+static bool
+null_safe_is_black (struct interval_node *node)
+{
+  return node == ITREE_NULL || !node->red; /* NULL nodes are black */
+}
+
 /* Update NODE's limit attribute according to its children. */
 
 static void
@@ -1224,9 +1196,6 @@ interval_tree_inherit_offset (uintmax_t otick, struct interval_node *node)
 
 /* Update limit of NODE and its ancestors.  Stop when it becomes
    stable, i.e. new_limit = old_limit.
-
-   NODE may also be the null node, in which case its parent is
-   used. (This feature is due to the RB algorithm.)
 */
 
 static void
@@ -1331,7 +1300,9 @@ interval_tree_rotate_right (struct interval_tree *tree, struct interval_node *no
 static void
 interval_tree_insert_fix (struct interval_tree *tree, struct interval_node *node)
 {
-  while (node->parent->red)
+  eassert (tree->root->red == false);
+
+  while (null_safe_is_red (node->parent))
     {
       /* NODE is red and its parent is red.  This is a violation of
 	 red-black tree property #3.  */
@@ -1343,7 +1314,7 @@ interval_tree_insert_fix (struct interval_tree *tree, struct interval_node *node
 	     our "uncle".  */
 	  struct interval_node *uncle = node->parent->parent->right;
 
-	  if (uncle->red) /* case 1.a */
+          if (null_safe_is_red (uncle)) /* case 1.a */
 	    {
 	      /* Uncle and parent are red but should be black because
 		 NODE is red.  Change the colors accordingly and
@@ -1373,7 +1344,7 @@ interval_tree_insert_fix (struct interval_tree *tree, struct interval_node *node
 	  /* This is the symmetrical case of above.  */
 	  struct interval_node *uncle = node->parent->parent->left;
 
-	  if (uncle->red) /* case 1.b */
+          if (null_safe_is_red (uncle)) /* case 1.b */
 	    {
 	      node->parent->red = false;
 	      uncle->red = false;
@@ -1415,15 +1386,20 @@ itree_total_offset (struct interval_node *node)
   return offset;
 }
 
-/* Link node SOURCE in DEST's place.
-   It's the caller's responsability to refresh the `limit`s
-   of DEST->parents afterwards.  */
+/* Replace DEST with SOURCE as a child of DEST's parent.  Adjusts
+   *only* the parent linkage of SOURCE and either the parent's child
+   link the tree root.
+
+   Warning: DEST is left unmodified.  SOURCE's child links are
+   unchanged.  Caller is responsible for recalculation of `limit`.
+   Requires both nodes to be using the same effective `offset`.  */
 
 static void
-interval_tree_transplant (struct interval_tree *tree, struct interval_node *source,
-                          struct interval_node *dest)
+interval_tree_replace_child (struct interval_tree *tree,
+                             struct interval_node *source,
+                             struct interval_node *dest)
 {
-  eassert (tree && source && dest && dest != ITREE_NULL);
+  eassert (tree && dest != ITREE_NULL);
   eassert (source == ITREE_NULL
            || itree_total_offset (source) == itree_total_offset (dest));
 
@@ -1438,6 +1414,28 @@ interval_tree_transplant (struct interval_tree *tree, struct interval_node *sour
     source->parent = dest->parent;
 }
 
+/* Replace DEST with SOURCE in the tree.  Copies the following fields
+   from DEST to SOURCE: red, parent, left, right.  Also updates
+   parent, left and right in surrounding nodes to point to SOURCE.
+
+   Warning: DEST is left unmodified.  Caller is responsible for
+   recalculation of `limit`.  Requires both nodes to be using the same
+   effective `offset`. */
+static void
+interval_tree_transplant (struct interval_tree *tree,
+                          struct interval_node *source,
+                          struct interval_node *dest)
+{
+  interval_tree_replace_child (tree, source, dest);
+  source->left = dest->left;
+  if (source->left != ITREE_NULL)
+    source->left->parent = source;
+  source->right = dest->right;
+  if (source->right != ITREE_NULL)
+    source->right->parent = source;
+  source->red = dest->red;
+}
+
 \f
 /* +===================================================================================+
  * | Debugging
diff --git a/src/itree.h b/src/itree.h
index 5733ec1530..0e2e7d1f81 100644
--- a/src/itree.h
+++ b/src/itree.h
@@ -95,9 +95,8 @@ #define ITREE_H
   bool_bf front_advance : 1;    /* Same as for marker and overlays.  */
 };
 
-/* The sentinel node, the null node.  */
-extern struct interval_node itree_null;
-#define ITREE_NULL (&itree_null)
+/* FIXME: replace ITREE_NULL -> NULL everywhere  */
+#define ITREE_NULL NULL
 
 struct interval_tree
 {
-- 
2.35.1

Re: noverlay branch

[Matt Armstrong]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> I just updated the noverlay branch to the code in `master` (most of it
> was mechanical except for the fact that since the last commit on that
> branch we have gotten rid of Lisp_Misc and we moved to pdumper).

TLDR: things are looking pretty stable and good on the feature/noverlay
branch.  If anyone here tested it a month ago and found it lacking, give
it another whirl.

Stefan, unless I have a flash of insight I'm done with my differential
fuzz testing of the noverlay branch's ELisp functions that relate to
overlays.  I've sent you three patches (see bug#58703 and bug#58706) but
with those fixes my test harness now runs hundreds of thousands of
randomized operations against with no no difference detected between
Emacs master and the feature/noverlay branch.  Code at
https://git.sr.ht/~matta/emacs/tree/my/overfuzz/item/test/manual/noverlay/overfuzz.el,
though I haven't polished it up.

There are two calls to 'overlays_in' in buffer.c that I couldn't cover
from ELisp: 'disable_line_numbers_overlay_at_eob' and
'mouse_face_overlay_overlaps'.  They're both display related.

Trying to manually exercise 'disable_line_numbers_overlay_at_eob' I
couldn't find any ELisp that set `display-line-numbers-disable' on an
overlay, and only two that do it in a text property (vc/log-edit.el and
something in helm), so even if there were a bug here I'm not sure anyone
would discover it.

I haven't looked at mouse_face_overlay_overlaps, but as I move my mouse
around different things highlight as expected, and as I narrow the
buffer things behave the same on feature/noverlay as they do on master
(as far as I can tell).

Re: noverlay branch

[Stefan Kangas]

Matt Armstrong <matt@rfc20.org> writes:

> TLDR: things are looking pretty stable and good on the feature/noverlay
> branch.  If anyone here tested it a month ago and found it lacking, give
> it another whirl.

Would it be welcome to merge master into that feature branch?

BTW, I can see two warnings, with gcc 12.2.0:

In function ‘interval_tree_remove_fix’,
    inlined from ‘itree_remove’ at itree.c:1110:5:
itree.c:923:15: warning: potential null pointer dereference [-Wnull-dereference]
  923 |           if (null_safe_is_black (other->left) /* 2.a */
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
itree.c:960:15: warning: potential null pointer dereference [-Wnull-dereference]
  960 |           if (null_safe_is_black (other->right) /* 2.b */
      |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

I'm now running feature/noverlay here (with master merged locally), and
will report back if I run into any issues.

Re: noverlay branch

[Eli Zaretskii]

> From: Matt Armstrong <matt@rfc20.org>
> Date: Sat, 22 Oct 2022 21:49:09 -0700
> 
> There are two calls to 'overlays_in' in buffer.c that I couldn't cover
> from ELisp: 'disable_line_numbers_overlay_at_eob' and
> 'mouse_face_overlay_overlaps'.  They're both display related.
> 
> Trying to manually exercise 'disable_line_numbers_overlay_at_eob' I
> couldn't find any ELisp that set `display-line-numbers-disable' on an
> overlay, and only two that do it in a text property (vc/log-edit.el and
> something in helm), so even if there were a bug here I'm not sure anyone
> would discover it.

AFAIR, company-mode uses that overlay property.  Dmitry, am I right?

Re: noverlay branch

[Matt Armstrong]

Stefan Kangas <stefankangas@gmail.com> writes:

> Matt Armstrong <matt@rfc20.org> writes:
>
>> TLDR: things are looking pretty stable and good on the feature/noverlay
>> branch.  If anyone here tested it a month ago and found it lacking, give
>> it another whirl.
>
> Would it be welcome to merge master into that feature branch?

I'm leaving the merge decision up to Stefan and other committers.  I'm
happy to accept commit privs and help out with this, but I'm still
pretty green.

There are two things I think should be done before a merge:

1) Relax some of the 'echeck' calls in src/itree.c.  They are too
expensive and actually make --enable-checking builds much slower than
they are on 'master' when there are non-trivial numbers of overlays.
Stefan has added FIXME comments for most of these.

2) Run some benchmarks.  My preliminary results seem to show that Emacs
redisplay can be marginally slower when the overlay count is low (with
what we'd consider "acceptable numbers" of overlays today), but much
faster when things get out of hand.

3) Anything Stefan has in his head.  :)

> BTW, I can see two warnings, with gcc 12.2.0:
>
> In function ‘interval_tree_remove_fix’,
>     inlined from ‘itree_remove’ at itree.c:1110:5:
> itree.c:923:15: warning: potential null pointer dereference [-Wnull-dereference]
>   923 |           if (null_safe_is_black (other->left) /* 2.a */
>       |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> itree.c:960:15: warning: potential null pointer dereference [-Wnull-dereference]
>   960 |           if (null_safe_is_black (other->right) /* 2.b */
>       |               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Those warnings are false positives, though the invariant relies on
red-black in variants and is too complex for a compiler to realize.
Heck, I have to sit down and draw things out to re-prove it to myself
every time.  https://git.sr.ht/~matta/emacs/log/scratch/matta/for_stefan
has a patch for it (which uses 'eassume'), or we could just check for
NULL even though it should never happen.

> I'm now running feature/noverlay here (with master merged locally),
> and will report back if I run into any issues.

I'd welcome a merge from master on feature/noverlay.  I think it has
been one month.

Re: noverlay branch

[Dmitry Gutov]

Hi!

On 24.10.2022 15:51, Eli Zaretskii wrote:
>> From: Matt Armstrong<matt@rfc20.org>
>> Date: Sat, 22 Oct 2022 21:49:09 -0700
>>
>> There are two calls to 'overlays_in' in buffer.c that I couldn't cover
>> from ELisp: 'disable_line_numbers_overlay_at_eob' and
>> 'mouse_face_overlay_overlaps'.  They're both display related.
>>
>> Trying to manually exercise 'disable_line_numbers_overlay_at_eob' I
>> couldn't find any ELisp that set `display-line-numbers-disable' on an
>> overlay, and only two that do it in a text property (vc/log-edit.el and
>> something in helm), so even if there were a bug here I'm not sure anyone
>> would discover it.
> AFAIR, company-mode uses that overlay property.  Dmitry, am I right?

Doesn't look like it.

I vaguely remember discussing it, but it seems we have solved the 
corresponding problem some other way.