bug#77942: 31.0.50; replace-region-contents gets stuck

[Gerd Möllmann]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Gerd Möllmann <gerd.moellmann@gmail.com>
>> Cc: monnier@iro.umontreal.ca,  eggert@cs.ucla.edu,  77942@debbugs.gnu.org
>> Date: Tue, 22 Apr 2025 13:42:15 +0200
>> 
>> Eli Zaretskii <eliz@gnu.org> writes:
>> 
>> >> Cc: Paul Eggert <eggert@cs.ucla.edu>, 77942@debbugs.gnu.org
>> >> From: Gerd Möllmann <gerd.moellmann@gmail.com>
>> >> Date: Tue, 22 Apr 2025 05:48:14 +0200
>> >> 
>> >> But honestly, what the heck? Does someone know what this diffing is
>> >> about in the first place?
>> >
>> > It's about leaving the unchanged portions of text intact, including
>> > their properties, overlays, markers, etc.  I believe the doc string
>> > says that much.
>> 
>> What I meant is why perform an O(ND) diff for that purpose. That's not
>> at all obvious.
>
> AFAIU, it's because the Diff algorithm makes the minimum number of
> changes.
>
>> (And it would be nice if the doc string talked about
>> that O(ND) a bit to warn users.)
>
> It does:
>
>   Because this function can be very slow if there is a large number of
>   differences between the two buffers, there are two optional arguments
>   mitigating this issue.

I find that pretty vague. If it said something about the O(ND), one
could figure out that that can be morally equivalent to O(N^2) which I
would find a fair warning.

But whatever. Funny function that one.