(I've tried splay-trees for text-properties, and the performance was not
noticeably different from the current mostly-balanced binary tree.
In particular it seems that either we don't get to see the O(1) behavior
because the locality is not as good as it seems, or the constant factor
makes up for the difference).
It *should* (in theory) be just fine for each undo-elt
to contain both string snapshot(s) and markers that
track the region effected. That's easy to code and in
turn it makes undo-elt-in-region very easy to code.
But that would significantly increase the size of the undo log, I expect
(maybe not algorithmically, but by a non-negligible factor).
It's too bad, because of we ignore the undo-in-region, we don't need
undo info for each modification, we could just grab a snapshot in
undo-boundary. That would be elegant (tho it's not like it matters:
changing the implementation of the undo data is trying to solve
a non-problem, really).