Re: Overlays as an AA-tree

[Eli Zaretskii]

> From: Andreas Politz <address@hidden>
> Date: Fri, 03 Feb 2017 09:49:20 +0100
> 
> Hi, I'm interested in this problem as well.

Thanks for working on this.

> Overlays have begin B and end E positions each with a flag (front-advance
> resp. rear-advance).  These positions may change in one of 3 ways:
> 
> 1. move-overlay is called
> 2. Text of length L is inserted at position P.
>    Here the flags decide whether begin B resp. end E will move or not
>    in the literal border-cases P = B resp. P = E .
> 3. Text of length L is deleted beginning at position P.
> 
> Is this the correct model ?

Not sure what you are asking here.  You actually described the model
of modifying buffer text, which is only tangentially related to
overlays.

> Someone mentioned in a different thread,
> that occasionally we may have B > E.  How does this happen ?

I don't think it can happen, except during internal operations of
inserting and deleting buffer text.  The functions that handle these
changes in buffer text fix up B and E such that B >= E before they
return to the main loop, so Lisp will never see that.

But note that you could have B == E (so-called "empty" or
"zero-length" overlays).  In this case, front-advance and rear-advance
are applied to the same buffer position.

There are also overlays that evaporate.