bug#52798: 27.2; `undo' causes `buffer-undo-list' to grow exponentially

bug#52798: 27.2; `undo' causes `buffer-undo-list' to grow exponentially

[Vladimir Panteleev]

Consider this Emacs Lisp script:

---
(eval-when-compile
  (require 'cl-lib))

(with-current-buffer (get-buffer-create "undo-test")
  ;; First, insert 50 characters.
  ;; Place an undo boundary after every insertion.
  (cl-loop repeat 50 do
       (insert "x")
       (undo-boundary))

  ;; Then, undo 50 times.
  ;; It doesn't matter if we use undo or undo-only.
  ;; We will only get into about 12 undos,
  ;; before the new exponentially-growing entries erase the old history.
  (cl-loop repeat 50 do
       (undo-only)
       (message "Length is now: %S" (length buffer-undo-list))))
---

When executed with `emacs --script test.el', I see the following output:

---
Undo
Length is now: 102
Undo
Length is now: 104
Undo
Length is now: 108
Undo
Length is now: 116
Undo
Length is now: 132
Undo
Length is now: 164
Undo
Length is now: 228
Undo
Length is now: 356
Undo
Length is now: 612
Undo
Length is now: 1124
Undo
Length is now: 2148
Undo
Length is now: 4196
Undo
Length is now: 8292
No further undo information
---

As far as I can see, the undo (and undo-only) command causes
buffer-undo-list to grow exponentially. This causes information about
previous entries to eventually be displaced.

N.B.: I noticed that upping gc-cons-threshold lets it do more undos, but
it does not prevent the exponential growth issue.

I think this is a bug by itself, but it's worth mentioning that this
script is a reduced version of a different problem I'm seeing with the
"No further undo information" message; the bug described here may or may
not be the root cause of that bug.

In GNU Emacs 27.2 (build 1, x86_64-pc-linux-gnu, GTK+ Version 3.24.27,
cairo version 1.17.4)
 of 2021-03-26 built on juergen
Windowing system distributor 'The X.Org Foundation', version 11.0.12101002
System Description: Arch Linux

Configured using:
 'configure --prefix=/usr --sysconfdir=/etc --libexecdir=/usr/lib
 --localstatedir=/var --with-x-toolkit=gtk3 --with-xft --with-wide-int
 --with-modules --with-cairo --with-harfbuzz 'CFLAGS=-march=x86-64
 -mtune=generic -O2 -pipe -fno-plt' CPPFLAGS=-D_FORTIFY_SOURCE=2
 LDFLAGS=-Wl,-O1,--sort-common,--as-needed,-z,relro,-z,now'

Configured features:
XPM JPEG TIFF GIF PNG RSVG CAIRO SOUND GPM DBUS GSETTINGS GLIB NOTIFY
INOTIFY ACL GNUTLS LIBXML2 FREETYPE HARFBUZZ M17N_FLT LIBOTF ZLIB
TOOLKIT_SCROLL_BARS GTK3 X11 XDBE XIM MODULES THREADS LIBSYSTEMD JSON
PDUMPER LCMS2 GMP

Important settings:
  value of $LC_TIME: en_DK.UTF-8
  value of $LANG: en_US.UTF-8
  locale-coding-system: utf-8-unix

bug#52798: 27.2; `undo' causes `buffer-undo-list' to grow exponentially

[Lars Ingebrigtsen]

Vladimir Panteleev <vladimir.panteleev.md@gmail.com> writes:

> As far as I can see, the undo (and undo-only) command causes
> buffer-undo-list to grow exponentially. This causes information about
> previous entries to eventually be displaced.

I can reproduce this in Emacs 29, too.  Perhaps Stefan has some
comments; added to the CCs.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#52798: 27.2; `undo' causes `buffer-undo-list' to grow exponentially

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Lars Ingebrigtsen [2021-12-29 17:29:26] wrote:
> Vladimir Panteleev <vladimir.panteleev.md@gmail.com> writes:
>> As far as I can see, the undo (and undo-only) command causes
>> buffer-undo-list to grow exponentially. This causes information about
>> previous entries to eventually be displaced.
> I can reproduce this in Emacs 29, too.

Yes, it's a known problem (tho it should be much less of a problem with
`undo-only`, IIRC).

> Perhaps Stefan has some comments; added to the CCs.

I'm sure we can do better.  The info about which parts can be skipped
should be available in `undo-equiv-table` but someone needs to sit down
and think about how and when we can use it.


        Stefan