Overlays as an AA-tree

[Joakim Jalap]

Hello Emacs devel

I've been working on an item from /etc/TODO on and off for a while now,
but now I have hit a bit of a roadblock.

What I've been looking at is replacing the current implementation of
buffer overlays with a self balanced tree. I chose an AA-tree as that
seemed simple enough for me to grasp :). First I tried using the tree
from intervals.c, but that seemed to be very tightly bound to the
implementation of text properties, so I gave up on that idea.

I got a bit on the way; I managed to get the tree structure in place and
to make it work for some very simple cases. I wrote some simple ert tests
for this. The idea was to be able to compile in three ways: just as
before, with just the new overlay implementation and with both
implementations and a whole lot of easserts. But alas, it turned out to
be too hard for me. There's quite a bit of fiddly code regarding
overlays and ripping it out and replacing it seems to be more than I can
chew. So the status right now is that nothing works... If you define
BOTH_OVERLAYS it will compile but fail an eassert at startup, if you
define NEW_OVERLAYS it doesn't even compile, since there's some stuff I
haven't replaced properly.

Anyway, I basically have two questions for you experts:
1) Is it worth continuing down this path?
2) If so, what's the best way to go about something like this? Replacing
the whole thing at once seems very hard, but I don't really know how to
go about replacing it little by little.

I'm attaching the diff. It is an unholy mess of ifdefs, but the meat of
it is in overlays.[ch] and buffer.c. It is a pretty big diff, and it's
based on master from a few months ago, so I'm not even sure it applies,
but I'd be grateful if somebody could have a quick look at it and try to
see if there's anything worth keeping there. If there's any interest I
could try rebasing it.

(I also just noted there's a heckload of trailing whitespace, I should
really append my init.el for that....)

Very grateful for all help!

-- Joakim

overlays-aa-tree.diff
Description: Overlays as AA-tree