bug#16411: undo-only bugs

[Barry OReilly]

> (I thought we had already understood how to fix bug 2, BTW)

No, we both agreed about how to fix bug 1, which isn't too hard or
intrusive. I'm talking about bug 2 now. I appreciate you taking the
time to discuss it with me. You said about it:

> IIUC, you're talking of skipping (e.g. in a non-region undo) the
> undos that took place during undo-in-region, right? If so, I don't
> have an answer for how we could do that, in general.

If you require the solution use undo-equiv-table, then I would have to
also admit to not having an answer.

> why not skip all these elements in one swoop as we currently do with
> undo-equiv-table

Because it would not be correct. I constructed recipe 2 in order to
demonstrate the incorrectness.

> In which way would this help fixing bug 2

Recipe 2 used an undo-in-region to trick the current undo-only
behavior into finding the wrong element to undo. Under my proposed
solution, undo-in-region creates a change group of redo elements, each
with a reference to its undone-element. This allows undo-only to find
the correct element to undo per the algorithm I described.

Why is it correct? undo-only wishes to find the most recent non redo
element A which is currently in the buffer (ie the net effect is it's
not undone). If A is reachable through an odd number of hops across
undo-element references, then it is undone, if even it is not undone.
If there exist paths to A both even and odd in length, then something
strange has happened to the undo history. The effect of skipping undo
elements as I described it is to exclude the ones with odd length
paths. For example, consider:

  A1 undoes A2 undoes A3 undoes A4 undoes A5

A2 and A4 will find themselves in the undo-skip-set, the others won't.
undo-only correctly finds A5 as the element to undo.

  B1 undoes B2 undoes B3 undoes B4 undoes B5 undoes B6

B2, B4, B6 will be skipped, so undo-only will have to find some other
non B element to undo, as it should in this case.

> the step "Insert its undone-element in the undo-skip-set" means that
> we skip this "redo" element, which means that all the subsequent
> elements (until the matching undone-element) may have incorrect
> buffer positions.

I explained this: I would rework the pending-undo-list computation to
be lazier, perhaps creating a get-next-pending-undo function instead
of computing the entire pending-undo-list upfront. undo-only would use
this function to get the next copy of an element of buffer-undo-list,
with positions adjusted using an index of undo-delta sums.
get-next-pending-undo would be part of "Iterate over
pending-undo-list", which means we are adjusting positions whether the
element will be skipped or not.

This rework to use a new get-next-pending-undo can be a self contained
patch which would benefit undo in region's performance right away,
even if undo-only doesn't use it after just the first patch.

> But it's still dangerous and wasteful

By dangerous do you mean incorrect? By wasteful do you mean non
performant? Maybe the discussion will be less confusing if we focus on
correctness first, then move to performance? Could you describe what
part of my proposal is incorrect?