Distinguish between regional undo and undo to the beginning in undo-equiv-table

Distinguish between regional undo and undo to the beginning in undo-equiv-table

[Yuan Fu]

Currently if I undo to the beginning of the pending-undo-list, buffer-undo-list is mapped to t in undo-equiv-table. Meanwhile, if the undo is undo-in-region, the buffer-undo-list is also mapped to t in undo-equiv-table.

That means my package that constructs an undo tree from buffer-undo-list cannot distinguish the two and thus cannot work incorrectly. Is it ok to map one type of undo to something other than t? Maybe a symbol 'undo-in-region? Would that break anything? Or maybe we can create another hash table to mark undo-in-region undos.

I can explain how does my package use undo-equiv-table if needed.

Yuan

Re: Distinguish between regional undo and undo to the beginning in undo-equiv-table

[Stefan Monnier]

> That means my package that constructs an undo tree from buffer-undo-list
> cannot distinguish the two and thus cannot work incorrectly. Is it ok to map
> one type of undo to something other than t?

I think so, yes.  It might require a few tweaks in simple.el but nothing
major (if at all).


        Stefan

Re: Distinguish between regional undo and undo to the beginning in undo-equiv-table

[Yuan Fu]

[-- Attachment #1: Type: text/plain, Size: 707 bytes --]



> On Mar 2, 2021, at 6:50 PM, Stefan Monnier <monnier@iro.umontreal.ca> wrote:
> 
>> That means my package that constructs an undo tree from buffer-undo-list
>> cannot distinguish the two and thus cannot work incorrectly. Is it ok to map
>> one type of undo to something other than t?
> 
> I think so, yes.  It might require a few tweaks in simple.el but nothing
> major (if at all).
> 

Here is a patch, I mapped undo-in-region records to 'undo-in-region. I also fixed a bug in undo-make-selective-list: before this change, if you undo-in-region, break the undo chain, then undo-in-region again with undo-only, ulist would be set to t and it breaks at (setq undo-elt (car ulist)).

Yuan


[-- Attachment #2: undo-in-region.patch --]
[-- Type: application/octet-stream, Size: 2987 bytes --]

From 8c4d50409a7ad88eb85d51e79b04f3587cd36976 Mon Sep 17 00:00:00 2001
From: Yuan Fu <casouri@gmail.com>
Date: Wed, 3 Mar 2021 09:50:15 -0500
Subject: [PATCH] Map redo records for undo-in-region to 'undo-in-region

* lisp/simple.el (undo-equiv-table): Add explaination for
undo-in-region and undo to the beginning of undo list.
(undo): If equiv is 'undo-in-region or t, set to pending-undo-list to
t. If the redo is undo-in-region, map buffer-undo-list to
'undo-in-region instead of t.
(undo-make-selective-list): Only continue when ulist is not t or
undo-in-region.
---
 lisp/simple.el | 20 +++++++++++---------
 1 file changed, 11 insertions(+), 9 deletions(-)

diff --git a/lisp/simple.el b/lisp/simple.el
index f8050091d5..05bf4b8784 100644
--- a/lisp/simple.el
+++ b/lisp/simple.el
@@ -2824,8 +2824,9 @@ 'advertised-undo
 
 (defconst undo-equiv-table (make-hash-table :test 'eq :weakness t)
   "Table mapping redo records to the corresponding undo one.
-A redo record for undo-in-region maps to t.
-A redo record for ordinary undo maps to the following (earlier) undo.")
+A redo record for undo-in-region maps to 'undo-in-region.
+A redo record for ordinary undo maps to the following (earlier) undo.
+An undo record that undoes to the beginning of the undo list maps to t.")
 
 (defvar undo-in-region nil
   "Non-nil if `pending-undo-list' is not just a tail of `buffer-undo-list'.")
@@ -2901,7 +2902,7 @@ undo
 	;; undo-redo-undo-redo-... so skip to the very last equiv.
 	(while (let ((next (gethash equiv undo-equiv-table)))
 		 (if next (setq equiv next))))
-	(setq pending-undo-list equiv)))
+	(setq pending-undo-list (if (consp equiv) equiv t))))
     (undo-more
      (if (numberp arg)
 	 (prefix-numeric-value arg)
@@ -2917,11 +2918,12 @@ undo
       (while (eq (car list) nil)
 	(setq list (cdr list)))
       (puthash list
-               ;; Prevent identity mapping.  This can happen if
-               ;; consecutive nils are erroneously in undo list.
-               (if (or undo-in-region (eq list pending-undo-list))
-                   t
-                 pending-undo-list)
+               (cond
+                (undo-in-region 'undo-in-region)
+                ;; Prevent identity mapping.  This can happen if
+                ;; consecutive nils are erroneously in undo list.
+                ((eq list pending-undo-list) t)
+                (t pending-undo-list))
 	       undo-equiv-table))
     ;; Don't specify a position in the undo record for the undo command.
     ;; Instead, undoing this should move point to where the change is.
@@ -3234,7 +3236,7 @@ undo-make-selective-list
         undo-elt)
     (while ulist
       (when undo-no-redo
-        (while (gethash ulist undo-equiv-table)
+        (while (consp (gethash ulist undo-equiv-table))
           (setq ulist (gethash ulist undo-equiv-table))))
       (setq undo-elt (car ulist))
       (cond
-- 
2.24.3 (Apple Git-128)


[-- Attachment #3: Type: text/plain, Size: 2 bytes --]

Re: Distinguish between regional undo and undo to the beginning in undo-equiv-table

[Stefan Monnier]

> Here is a patch, I mapped undo-in-region records to 'undo-in-region. I also
> fixed a bug in undo-make-selective-list: before this change, if you
> undo-in-region, break the undo chain, then undo-in-region again with
> undo-only, ulist would be set to t and it breaks at (setq undo-elt (car
> ulist)).

Thanks a lot (especially for improving the docstring ;-).  In my
experience, this part of the code is quite delicate and I wouldn't be
surprised to find yet more bugs for other corner cases.  So I think it's
very important to document those corner cases with tests.  Any chance
you could add matching tests to test/lisp/simple-tests.el in your patch?


        Stefan


> Yuan
>
> From 8c4d50409a7ad88eb85d51e79b04f3587cd36976 Mon Sep 17 00:00:00 2001
> From: Yuan Fu <casouri@gmail.com>
> Date: Wed, 3 Mar 2021 09:50:15 -0500
> Subject: [PATCH] Map redo records for undo-in-region to 'undo-in-region
>
> * lisp/simple.el (undo-equiv-table): Add explaination for
> undo-in-region and undo to the beginning of undo list.
> (undo): If equiv is 'undo-in-region or t, set to pending-undo-list to
> t. If the redo is undo-in-region, map buffer-undo-list to
> 'undo-in-region instead of t.
> (undo-make-selective-list): Only continue when ulist is not t or
> undo-in-region.
> ---
>  lisp/simple.el | 20 +++++++++++---------
>  1 file changed, 11 insertions(+), 9 deletions(-)
>
> diff --git a/lisp/simple.el b/lisp/simple.el
> index f8050091d5..05bf4b8784 100644
> --- a/lisp/simple.el
> +++ b/lisp/simple.el
> @@ -2824,8 +2824,9 @@ 'advertised-undo
>  
>  (defconst undo-equiv-table (make-hash-table :test 'eq :weakness t)
>    "Table mapping redo records to the corresponding undo one.
> -A redo record for undo-in-region maps to t.
> -A redo record for ordinary undo maps to the following (earlier) undo.")
> +A redo record for undo-in-region maps to 'undo-in-region.
> +A redo record for ordinary undo maps to the following (earlier) undo.
> +An undo record that undoes to the beginning of the undo list maps to t.")
>  
>  (defvar undo-in-region nil
>    "Non-nil if `pending-undo-list' is not just a tail of `buffer-undo-list'.")
> @@ -2901,7 +2902,7 @@ undo
>  	;; undo-redo-undo-redo-... so skip to the very last equiv.
>  	(while (let ((next (gethash equiv undo-equiv-table)))
>  		 (if next (setq equiv next))))
> -	(setq pending-undo-list equiv)))
> +	(setq pending-undo-list (if (consp equiv) equiv t))))
>      (undo-more
>       (if (numberp arg)
>  	 (prefix-numeric-value arg)
> @@ -2917,11 +2918,12 @@ undo
>        (while (eq (car list) nil)
>  	(setq list (cdr list)))
>        (puthash list
> -               ;; Prevent identity mapping.  This can happen if
> -               ;; consecutive nils are erroneously in undo list.
> -               (if (or undo-in-region (eq list pending-undo-list))
> -                   t
> -                 pending-undo-list)
> +               (cond
> +                (undo-in-region 'undo-in-region)
> +                ;; Prevent identity mapping.  This can happen if
> +                ;; consecutive nils are erroneously in undo list.
> +                ((eq list pending-undo-list) t)
> +                (t pending-undo-list))
>  	       undo-equiv-table))
>      ;; Don't specify a position in the undo record for the undo command.
>      ;; Instead, undoing this should move point to where the change is.
> @@ -3234,7 +3236,7 @@ undo-make-selective-list
>          undo-elt)
>      (while ulist
>        (when undo-no-redo
> -        (while (gethash ulist undo-equiv-table)
> +        (while (consp (gethash ulist undo-equiv-table))
>            (setq ulist (gethash ulist undo-equiv-table))))
>        (setq undo-elt (car ulist))
>        (cond

Re: Distinguish between regional undo and undo to the beginning in undo-equiv-table

[Yuan Fu]

[-- Attachment #1: Type: text/plain, Size: 764 bytes --]

> 
> Thanks a lot (especially for improving the docstring ;-).  In my
> experience, this part of the code is quite delicate and I wouldn't be
> surprised to find yet more bugs for other corner cases.  So I think it's
> very important to document those corner cases with tests.  Any chance
> you could add matching tests to test/lisp/simple-tests.el in your patch?
> 

This patch applies on top of the first one. I added more docstrings since you seem to appreciate it. I came up with some simple test cases for ordinary mapping, t and ‘undo-in-region in the table. Do you have other corner cases in mind? I also added some simple test cases for undo in region. I couldn’t wrap my head around the original tests so I started a new one below.

Yuan


[-- Attachment #2: undo-in-region-2.patch --]
[-- Type: application/octet-stream, Size: 4848 bytes --]

From 72bbfd0e0d4c8a4175e44ccee49323323c018834 Mon Sep 17 00:00:00 2001
From: Yuan Fu <casouri@gmail.com>
Date: Wed, 3 Mar 2021 15:07:00 -0500
Subject: [PATCH] checkpoint

---
 lisp/simple.el            | 17 ++++++++-
 test/lisp/simple-tests.el | 75 ++++++++++++++++++++++++++++++++++++++-
 2 files changed, 90 insertions(+), 2 deletions(-)

diff --git a/lisp/simple.el b/lisp/simple.el
index 05bf4b8784..8265639305 100644
--- a/lisp/simple.el
+++ b/lisp/simple.el
@@ -2826,7 +2826,22 @@ undo-equiv-table
   "Table mapping redo records to the corresponding undo one.
 A redo record for undo-in-region maps to 'undo-in-region.
 A redo record for ordinary undo maps to the following (earlier) undo.
-An undo record that undoes to the beginning of the undo list maps to t.")
+An undo record that undoes to the beginning of the undo list maps to t.
+
+When you undo, the `pending-undo-list' shrinks and
+`buffer-undo-list' grows, and Emacs maps the tip of
+`buffer-undo-list' to the tip of `pending-undo-list' in this
+table.
+
+For example, consider this undo list where each node represents an
+undo record, if we undo from 4, `pending-undo-list' will be at 3,
+`buffer-undo-list' at 5, and 5 will map to 3.
+
+    |
+    3  5
+    | /
+    |/
+    4")
 
 (defvar undo-in-region nil
   "Non-nil if `pending-undo-list' is not just a tail of `buffer-undo-list'.")
diff --git a/test/lisp/simple-tests.el b/test/lisp/simple-tests.el
index f2ddc2e3fb..a4816951ce 100644
--- a/test/lisp/simple-tests.el
+++ b/test/lisp/simple-tests.el
@@ -465,8 +465,81 @@ simple-tests--undo
     (simple-tests--exec '(backward-char undo-redo undo-redo))
     (should (equal (buffer-string) "abc"))
     (simple-tests--exec '(backward-char undo-redo undo-redo))
+    (should (equal (buffer-string) "abcde")))
+  ;; Test undo/redo in region.
+  (with-temp-buffer
+    (buffer-enable-undo)
+    (dolist (x '("a" "b" "c" "d" "e"))
+      (insert x)
+      (undo-boundary))
     (should (equal (buffer-string) "abcde"))
-    ))
+    (simple-tests--exec '(move-beginning-of-line
+                          push-mark-command
+                          forward-char
+                          forward-char
+                          undo))
+    (should (equal (buffer-string) "acde"))
+    (simple-tests--exec '(undo-only))
+    (should (equal (buffer-string) "cde"))
+    (simple-tests--exec '(undo-redo))
+    (should (equal (buffer-string) "acde"))
+    (simple-tests--exec '(undo-redo))
+    (should (equal (buffer-string) "abcde"))))
+
+(defun simple-tests--sans-leading-nil (lst)
+  "Return LST sans the leading nils."
+  (while (and (consp lst) (null (car lst)))
+    (setq lst (cdr lst)))
+  lst)
+
+(ert-deftest simple-tests--undo-equiv-table ()
+  (with-temp-buffer
+    (buffer-enable-undo)
+    (let ((ul-hash-table (make-hash-table :test #'equal)))
+      (dolist (x '("a" "b" "c"))
+        (insert x)
+        (puthash x (simple-tests--sans-leading-nil buffer-undo-list)
+                 ul-hash-table)
+        (undo-boundary))
+      (should (equal (buffer-string) "abc"))
+
+      ;; Tests mappings in `undo-equiv-table'.
+      (simple-tests--exec '(undo))
+      (should (equal (buffer-string) "ab"))
+      (should (eq (gethash (simple-tests--sans-leading-nil
+                            buffer-undo-list)
+                           undo-equiv-table)
+                  (gethash "b" ul-hash-table)))
+
+      (simple-tests--exec '(backward-char undo))
+      (should (equal (buffer-string) "abc"))
+      (should (eq (gethash (simple-tests--sans-leading-nil
+                            buffer-undo-list)
+                           undo-equiv-table)
+                  (gethash "c" ul-hash-table)))
+
+      ;; Undo in region should map to 'undo-in-region.
+      (simple-tests--exec '(backward-char
+                            push-mark-command
+                            move-end-of-line
+                            undo))
+      (should (equal (buffer-string) "ab"))
+      (should (eq (gethash (simple-tests--sans-leading-nil
+                            buffer-undo-list)
+                           undo-equiv-table)
+                  'undo-in-region))
+
+      ;; The undo that undoes to the beginning should map to t.
+      (deactivate-mark 'force)
+      (simple-tests--exec '(backward-char
+                            undo undo undo
+                            undo undo undo))
+      (should (equal (buffer-string) ""))
+      (should (eq (gethash (simple-tests--sans-leading-nil
+                            buffer-undo-list)
+                           undo-equiv-table)
+                  t))
+      )))
 
 ;;; undo auto-boundary tests
 (ert-deftest undo-auto-boundary-timer ()
-- 
2.24.3 (Apple Git-128)

Re: Distinguish between regional undo and undo to the beginning in undo-equiv-table

[Stefan Monnier]

> This patch applies on top of the first one. I added more docstrings since
> you seem to appreciate it.

Great!

> I couldn’t wrap my head around the original tests so I started a new
> one below.

That's perfectly fine.

Earlier you wrote:
> if you undo-in-region, break the undo chain, then undo-in-region again
> with undo-only, ulist would be set to t and it breaks at (setq
> undo-elt (car ulist)).

I don't see which of the tests corresponds to this.
Is it this one:

> +    (should (equal (buffer-string) "abcde")))
> +  ;; Test undo/redo in region.
> +  (with-temp-buffer
> +    (buffer-enable-undo)
> +    (dolist (x '("a" "b" "c" "d" "e"))
> +      (insert x)
> +      (undo-boundary))
>      (should (equal (buffer-string) "abcde"))
> -    ))
> +    (simple-tests--exec '(move-beginning-of-line
> +                          push-mark-command
> +                          forward-char
> +                          forward-char
> +                          undo))
> +    (should (equal (buffer-string) "acde"))
> +    (simple-tests--exec '(undo-only))
> +    (should (equal (buffer-string) "cde"))
> +    (simple-tests--exec '(undo-redo))
> +    (should (equal (buffer-string) "acde"))
> +    (simple-tests--exec '(undo-redo))
> +    (should (equal (buffer-string) "abcde"))))

?

        Stefan

Re: Distinguish between regional undo and undo to the beginning in undo-equiv-table

[Yuan Fu]

[-- Attachment #1: Type: text/plain, Size: 1995 bytes --]



> On Mar 3, 2021, at 4:29 PM, Stefan Monnier <monnier@iro.umontreal.ca> wrote:
> 
>> This patch applies on top of the first one. I added more docstrings since
>> you seem to appreciate it.
> 
> Great!
> 
>> I couldn’t wrap my head around the original tests so I started a new
>> one below.
> 
> That's perfectly fine.
> 
> Earlier you wrote:
>> if you undo-in-region, break the undo chain, then undo-in-region again
>> with undo-only, ulist would be set to t and it breaks at (setq
>> undo-elt (car ulist)).
> 
> I don't see which of the tests corresponds to this.
> Is it this one:
> 
>> +    (should (equal (buffer-string) "abcde")))
>> +  ;; Test undo/redo in region.
>> +  (with-temp-buffer
>> +    (buffer-enable-undo)
>> +    (dolist (x '("a" "b" "c" "d" "e"))
>> +      (insert x)
>> +      (undo-boundary))
>>     (should (equal (buffer-string) "abcde"))
>> -    ))
>> +    (simple-tests--exec '(move-beginning-of-line
>> +                          push-mark-command
>> +                          forward-char
>> +                          forward-char
>> +                          undo))
>> +    (should (equal (buffer-string) "acde"))
>> +    (simple-tests--exec '(undo-only))
>> +    (should (equal (buffer-string) "cde"))
>> +    (simple-tests--exec '(undo-redo))
>> +    (should (equal (buffer-string) "acde"))
>> +    (simple-tests--exec '(undo-redo))
>> +    (should (equal (buffer-string) "abcde"))))
> 
> ?

Yes, that was supposed to be the one. Just to be sure I ran the test with the old version and it didn’t error. Oops! I fixed the test, now it errors on the old version and passes after applying my fix (in the first patch). The test first runs undo in region, then breaks the undo chain (my 2nd patch failed to do that), then runs undo in region again. I’m not sure how to write the comment for that test. Maybe I could write “test for commit xxx” but there is no commit number to refer to right now.

Yuan


[-- Attachment #2: undo-in-region-3.patch --]
[-- Type: application/octet-stream, Size: 1515 bytes --]

From 8c4df349dd2b6c214679d44712a5de99e8a04183 Mon Sep 17 00:00:00 2001
From: Yuan Fu <casouri@gmail.com>
Date: Wed, 3 Mar 2021 16:50:08 -0500
Subject: [PATCH] checkpoint

---
 test/lisp/simple-tests.el | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)

diff --git a/test/lisp/simple-tests.el b/test/lisp/simple-tests.el
index a4816951ce..eb1c0e53e2 100644
--- a/test/lisp/simple-tests.el
+++ b/test/lisp/simple-tests.el
@@ -479,12 +479,21 @@ simple-tests--undo
                           forward-char
                           undo))
     (should (equal (buffer-string) "acde"))
-    (simple-tests--exec '(undo-only))
-    (should (equal (buffer-string) "cde"))
+    (simple-tests--exec '(move-beginning-of-line
+                          push-mark-command
+                          forward-char
+                          forward-char
+                          undo-only))
+    (should (equal (buffer-string) "abcde"))
     (simple-tests--exec '(undo-redo))
     (should (equal (buffer-string) "acde"))
     (simple-tests--exec '(undo-redo))
-    (should (equal (buffer-string) "abcde"))))
+    (should (equal (buffer-string) "abcde"))
+    (deactivate-mark)
+    (simple-tests--exec '(move-beginning-of-line
+                          push-mark-command
+                          forward-char
+                          undo-only))))
 
 (defun simple-tests--sans-leading-nil (lst)
   "Return LST sans the leading nils."
-- 
2.24.3 (Apple Git-128)

Re: Distinguish between regional undo and undo to the beginning in undo-equiv-table

[Yuan Fu]

BTW, I can’t quite get what the comment at simple.el:2920 means:

(puthash list
               ;; Prevent identity mapping.  This can happen if
               ;; consecutive nils are erroneously in undo list.
               (if (or undo-in-region (eq list pending-undo-list))
                   t
                 pending-undo-list)
	       undo-equiv-table)

Is it that if there is (nil nil nil) on the top of buffer-undo-list, the middle one will be considered an undo record and will be passed to primitive-undo? In that case nothing is done and nothing is added to buffer-undo-list? Then should we add a mapping for the buffer-undo-list to t at that point? Or should we just do nothing?

Yuan

Re: Distinguish between regional undo and undo to the beginning in undo-equiv-table

[Stefan Monnier]

> Yes, that was supposed to be the one. Just to be sure I ran the test with
> the old version and it didn’t error. Oops! I fixed the test, now it errors
> on the old version and passes after applying my fix (in the first
> patch). The test first runs undo in region, then breaks the undo chain (my
> 2nd patch failed to do that), then runs undo in region again.

Perfect.

> I’m not sure how to write the comment for that test. Maybe I could
> write “test for commit xxx” but there is no commit number to refer to
> right now.

That would be fine.  Or just use some description of what the test does
like "check the case of interrupted+repeated undo-in-region".
Or just nothing at all and let the code speak for itself ;-)

> BTW, I can’t quite get what the comment at simple.el:2920 means:
>
> (puthash list
>                ;; Prevent identity mapping.  This can happen if
>                ;; consecutive nils are erroneously in undo list.
>                (if (or undo-in-region (eq list pending-undo-list))
>                    t
>                  pending-undo-list)
> 	       undo-equiv-table)

> Is it that if there is (nil nil nil) on the top of buffer-undo-list,
> the middle one will be considered an undo record and will be passed to
> primitive-undo?

I think so, yes.

> In that case nothing is done and nothing is added to buffer-undo-list?

Exactly.

> Then should we add a mapping for the buffer-undo-list to t at that
> point?  Or should we just do nothing?

Good question.  I think you have a better understanding of how the equiv
table should be filled than I do at this point, so I'd trust your judgment.


        Stefan

Re: Distinguish between regional undo and undo to the beginning in undo-equiv-table

[Yuan Fu]

[-- Attachment #1: Type: text/plain, Size: 624 bytes --]

> 
>> Then should we add a mapping for the buffer-undo-list to t at that
>> point?  Or should we just do nothing?
> 
> Good question.  I think you have a better understanding of how the equiv
> table should be filled than I do at this point, so I'd trust your judgment.

Ok, I looked into it in detail, undo-equiv-table is also used to check if the previous command is really an undo, alongside with checking last-command. So the undo record has to map to something, I decide to map it to ‘empty unless there is already a mapping for the record. Here is the (standalone) final draft. Please have a look.

Yuan


[-- Attachment #2: undo-in-region-3.patch --]
[-- Type: application/octet-stream, Size: 10501 bytes --]

From 7e197d19f257816aaf12f474bdae2eca36fbbc21 Mon Sep 17 00:00:00 2001
From: Yuan Fu <casouri@gmail.com>
Date: Wed, 3 Mar 2021 09:50:15 -0500
Subject: [PATCH] Map redo records for undo in region to 'undo-in-region

* lisp/simple.el (undo-equiv-table): Add explaination for
undo-in-region, undo to the beginning of undo list and null undo.
(undo): If equiv is 'undo-in-region, empty or t, set pending-undo-list
to t.  If the redo is undo-in-region, map buffer-undo-list to
'undo-in-region instead of t, if it is an identity mapping, map to
'empty.
(undo-make-selective-list): Only continue when ulist is a proper list.
* test/lisp/simple-tests.el (simple-tests--undo): Add test for
undo-only in region.
(simple-tests--sans-leading-nil): New helper function.
(simple-tests--undo-equiv-table): New test for 'undo-equiv-table'.
---
 lisp/simple.el            |  55 +++++++++++++++----
 test/lisp/simple-tests.el | 111 +++++++++++++++++++++++++++++++++++++-
 2 files changed, 155 insertions(+), 11 deletions(-)

diff --git a/lisp/simple.el b/lisp/simple.el
index f8050091d5..98fccf4ff2 100644
--- a/lisp/simple.el
+++ b/lisp/simple.el
@@ -2824,8 +2824,35 @@ 'advertised-undo
 
 (defconst undo-equiv-table (make-hash-table :test 'eq :weakness t)
   "Table mapping redo records to the corresponding undo one.
-A redo record for undo-in-region maps to t.
-A redo record for ordinary undo maps to the following (earlier) undo.")
+A redo record for an undo in region maps to 'undo-in-region.
+A redo record for ordinary undo maps to the following (earlier) undo.
+A redo record that undoes to the beginning of the undo list maps to t.
+In the rare case where there are (erroneously) consecutive nil's in
+`buffer-undo-list', `undo' maps the previous valid undo record to
+'empty, if the previous record is a redo record, `undo' doesn't change
+its mapping.
+
+To be clear, a redo record is just an undo record, the only difference
+is that it is created by an undo command (instead of an ordinary buffer
+edit).  Since a record used to undo ordinary change is called undo
+record, a record used to undo an undo is called redo record.
+
+`undo' uses this table to make sure the previous command is `undo'.
+`undo-redo' uses this table to set the correct `pending-undo-list'.
+
+When you undo, `pending-undo-list' shrinks and `buffer-undo-list'
+grows, and Emacs maps the tip of `buffer-undo-list' to the tip of
+`pending-undo-list' in this table.
+
+For example, consider this undo list where each node represents an
+undo record: if we undo from 4, `pending-undo-list' will be at 3,
+`buffer-undo-list' at 5, and 5 will map to 3.
+
+    |
+    3  5
+    | /
+    |/
+    4")
 
 (defvar undo-in-region nil
   "Non-nil if `pending-undo-list' is not just a tail of `buffer-undo-list'.")
@@ -2872,7 +2899,9 @@ undo
     ;; the next command should not be a "consecutive undo".
     ;; So set `this-command' to something other than `undo'.
     (setq this-command 'undo-start)
-
+    ;; Here we decide whether to break the undo chain.  If the
+    ;; previous command is `undo', we don't call `undo-start', i.e.,
+    ;; don't break the undo chain.
     (unless (and (eq last-command 'undo)
 		 (or (eq pending-undo-list t)
 		     ;; If something (a timer or filter?) changed the buffer
@@ -2901,7 +2930,7 @@ undo
 	;; undo-redo-undo-redo-... so skip to the very last equiv.
 	(while (let ((next (gethash equiv undo-equiv-table)))
 		 (if next (setq equiv next))))
-	(setq pending-undo-list equiv)))
+	(setq pending-undo-list (if (consp equiv) equiv t))))
     (undo-more
      (if (numberp arg)
 	 (prefix-numeric-value arg)
@@ -2917,11 +2946,17 @@ undo
       (while (eq (car list) nil)
 	(setq list (cdr list)))
       (puthash list
-               ;; Prevent identity mapping.  This can happen if
-               ;; consecutive nils are erroneously in undo list.
-               (if (or undo-in-region (eq list pending-undo-list))
-                   t
-                 pending-undo-list)
+               (cond
+                (undo-in-region 'undo-in-region)
+                ;; Prevent identity mapping.  This can happen if
+                ;; consecutive nils are erroneously in undo list.  It
+                ;; has to map to _something_ so that the next `undo'
+                ;; command recognizes that the previous command is
+                ;; `undo' and doesn't break the undo chain.
+                ((eq list pending-undo-list)
+                 (or (gethash list undo-equiv-table)
+                     'empty))
+                (t pending-undo-list))
 	       undo-equiv-table))
     ;; Don't specify a position in the undo record for the undo command.
     ;; Instead, undoing this should move point to where the change is.
@@ -3234,7 +3269,7 @@ undo-make-selective-list
         undo-elt)
     (while ulist
       (when undo-no-redo
-        (while (gethash ulist undo-equiv-table)
+        (while (consp (gethash ulist undo-equiv-table))
           (setq ulist (gethash ulist undo-equiv-table))))
       (setq undo-elt (car ulist))
       (cond
diff --git a/test/lisp/simple-tests.el b/test/lisp/simple-tests.el
index f2ddc2e3fb..1819775bda 100644
--- a/test/lisp/simple-tests.el
+++ b/test/lisp/simple-tests.el
@@ -465,8 +465,117 @@ simple-tests--undo
     (simple-tests--exec '(backward-char undo-redo undo-redo))
     (should (equal (buffer-string) "abc"))
     (simple-tests--exec '(backward-char undo-redo undo-redo))
+    (should (equal (buffer-string) "abcde")))
+  ;; Test undo/redo in region.
+  (with-temp-buffer
+    (buffer-enable-undo)
+    (dolist (x '("a" "b" "c" "d" "e"))
+      (insert x)
+      (undo-boundary))
+    (should (equal (buffer-string) "abcde"))
+    ;; The test does this: activate region, `undo', break the undo
+    ;; chain (by deactivating and reactivating the region), then
+    ;; `undo-only'.  There used to be a bug in
+    ;; `undo-make-selective-list' that makes `undo-only' error out in
+    ;; that case, which is fixed by in the same commit as this change.
+    (simple-tests--exec '(move-beginning-of-line
+                          push-mark-command
+                          forward-char
+                          forward-char
+                          undo))
+    (should (equal (buffer-string) "acde"))
+    (simple-tests--exec '(move-beginning-of-line
+                          push-mark-command
+                          forward-char
+                          forward-char
+                          undo-only))
     (should (equal (buffer-string) "abcde"))
-    ))
+    ;; Rest are simple redo in region tests.
+    (simple-tests--exec '(undo-redo))
+    (should (equal (buffer-string) "acde"))
+    (simple-tests--exec '(undo-redo))
+    (should (equal (buffer-string) "abcde"))))
+
+(defun simple-tests--sans-leading-nil (lst)
+  "Return LST sans the leading nils."
+  (while (and (consp lst) (null (car lst)))
+    (setq lst (cdr lst)))
+  lst)
+
+(ert-deftest simple-tests--undo-equiv-table ()
+  (with-temp-buffer
+    (buffer-enable-undo)
+    (let ((ul-hash-table (make-hash-table :test #'equal)))
+      (dolist (x '("a" "b" "c"))
+        (insert x)
+        (puthash x (simple-tests--sans-leading-nil buffer-undo-list)
+                 ul-hash-table)
+        (undo-boundary))
+      (should (equal (buffer-string) "abc"))
+      ;; Tests mappings in `undo-equiv-table'.
+      (simple-tests--exec '(undo))
+      (should (equal (buffer-string) "ab"))
+      (should (eq (gethash (simple-tests--sans-leading-nil
+                            buffer-undo-list)
+                           undo-equiv-table)
+                  (gethash "b" ul-hash-table)))
+      (simple-tests--exec '(backward-char undo))
+      (should (equal (buffer-string) "abc"))
+      (should (eq (gethash (simple-tests--sans-leading-nil
+                            buffer-undo-list)
+                           undo-equiv-table)
+                  (gethash "c" ul-hash-table)))
+      ;; Undo in region should map to 'undo-in-region.
+      (simple-tests--exec '(backward-char
+                            push-mark-command
+                            move-end-of-line
+                            undo))
+      (should (equal (buffer-string) "ab"))
+      (should (eq (gethash (simple-tests--sans-leading-nil
+                            buffer-undo-list)
+                           undo-equiv-table)
+                  'undo-in-region))
+      ;; The undo that undoes to the beginning should map to t.
+      (deactivate-mark 'force)
+      (simple-tests--exec '(backward-char
+                            undo undo undo
+                            undo undo undo))
+      (should (equal (buffer-string) ""))
+      (should (eq (gethash (simple-tests--sans-leading-nil
+                            buffer-undo-list)
+                           undo-equiv-table)
+                  t))
+      ;; Erroneous nil undo should map to 'empty.
+      (insert "a")
+      (undo-boundary)
+      (push nil buffer-undo-list)
+      (simple-tests--exec '(backward-char undo))
+      (should (equal (buffer-string) "a"))
+      (should (eq (gethash (simple-tests--sans-leading-nil
+                            buffer-undo-list)
+                           undo-equiv-table)
+                  'empty))
+      ;; But if the previous record is a redo record, its mapping
+      ;; shouldn't change.
+      (insert "e")
+      (undo-boundary)
+      (should (equal (buffer-string) "ea"))
+      (puthash "e" (simple-tests--sans-leading-nil buffer-undo-list)
+               ul-hash-table)
+      (insert "a")
+      (undo-boundary)
+      (simple-tests--exec '(backward-char undo))
+      (should (equal (buffer-string) "ea"))
+      (push nil buffer-undo-list)
+      (simple-tests--exec '(forward-char undo))
+      ;; Buffer content should change since we just undid a nil
+      ;; record.
+      (should (equal (buffer-string) "ea"))
+      ;; The previous redo record shouldn't map to empty.
+      (should (equal (gethash (simple-tests--sans-leading-nil
+                               buffer-undo-list)
+                              undo-equiv-table)
+                     (gethash "e" ul-hash-table))))))
 
 ;;; undo auto-boundary tests
 (ert-deftest undo-auto-boundary-timer ()
-- 
2.24.3 (Apple Git-128)

Re: Distinguish between regional undo and undo to the beginning in undo-equiv-table

[Stefan Monnier]

>>> Then should we add a mapping for the buffer-undo-list to t at that
>>> point?  Or should we just do nothing?
>> Good question.  I think you have a better understanding of how the equiv
>> table should be filled than I do at this point, so I'd trust your judgment.
> Ok, I looked into it in detail, undo-equiv-table is also used to check if
> the previous command is really an undo, alongside with checking
> last-command.

Indeed [ tho, this test is not 100% reliable, because the hash-table is
weak, so entries may disappear from it, leading to entries that used to
map to non-nil suddenly mapping to nil.  ]

> So the undo record has to map to something, I decide to map it to
> ‘empty unless there is already a mapping for the record.  Here is the
> (standalone) final draft. Please have a look.

Looks good, thanks.


        Stefan

Re: Distinguish between regional undo and undo to the beginning in undo-equiv-table

[Yuan Fu]

> On Mar 5, 2021, at 10:57 AM, Stefan Monnier <monnier@iro.umontreal.ca> wrote:
> 
>>>> Then should we add a mapping for the buffer-undo-list to t at that
>>>> point?  Or should we just do nothing?
>>> Good question.  I think you have a better understanding of how the equiv
>>> table should be filled than I do at this point, so I'd trust your judgment.
>> Ok, I looked into it in detail, undo-equiv-table is also used to check if
>> the previous command is really an undo, alongside with checking
>> last-command.
> 
> Indeed [ tho, this test is not 100% reliable, because the hash-table is
> weak, so entries may disappear from it, leading to entries that used to
> map to non-nil suddenly mapping to nil.  ]

I think that’s fine. If the entry disappeared, that means either the key or the value is no longer in the undo list, no?

Yuan

Re: Distinguish between regional undo and undo to the beginning in undo-equiv-table

[Stefan Monnier]

> I think that’s fine. If the entry disappeared, that means either the key or
> the value is no longer in the undo list, no?

Yes (in practice, it's usually the value which disappears first, since
the value is supposed to be "older" and these things normally disappear
as a result of undo-log truncation).


        Stefan

Re: Distinguish between regional undo and undo to the beginning in undo-equiv-table

[Yuan Fu]

I see the patch hasn’t merge yet. Is there anything needs to be done/tested?

Yuan

Re: Distinguish between regional undo and undo to the beginning in undo-equiv-table

[Stefan Monnier]

> I see the patch hasn’t merge yet. Is there anything needs to be done/tested?

Oh, no, I thought you could push yourself.
Sorry.  I'll get to it ASAP,


        Stefan

Re: Distinguish between regional undo and undo to the beginning in undo-equiv-table

[Yuan Fu]

> On Mar 11, 2021, at 12:54 PM, Stefan Monnier <monnier@iro.umontreal.ca> wrote:
> 
>> I see the patch hasn’t merge yet. Is there anything needs to be done/tested?
> 
> Oh, no, I thought you could push yourself.
> Sorry.  I'll get to it ASAP,
> 

No biggie, and thanks. :-)

Yuan

Re: Distinguish between regional undo and undo to the beginning in undo-equiv-table

[Stefan Monnier]

> Ok, I looked into it in detail, undo-equiv-table is also used to check if
> the previous command is really an undo, alongside with checking
> last-command. So the undo record has to map to something, I decide to map it
> to ‘empty unless there is already a mapping for the record. Here is the
> (standalone) final draft. Please have a look.
>
> Yuan
>
> [2. text/x-diff; undo-in-region-3.patch]...

Thanks, pushed to `master`.


        Stefan