Subject: Re: bug#70077: An easier way to track buffer changes

From: Stefan Monnier <[email-masked]>
Date: Wed, 03 Apr 2024 08:45:59 -0400

> I am not 100% where the O(N^2) is coming from.

If you add N times 1 char to an (initially empty) string, the total cost
of constructing the resulting N-char string is O(N²).

> In any case, while I do see where the idea of over-expanding the region
> comes from, it is not ideal for my use-case in Org mode - it is often
> critical to know precise region where the change happened.

The reported changes are precise (modulo the fact that they are
combined): the over-expanded `track-changes--before-string`
is trimmed to the actual changes when it gets moved to a "state"
(that's done in `track-changes--clean-state`).

Also, note that in 99% of the cases, a command performs only a single
change (insertion or deletion), in which case there's no combining nor
over-expansion before the signal gets called.  Of course, approximation
may still happen if you decide not to act immediately when the signal
is sent.

        Stefan