bug#16377: Undo Tree regression: (error "Unrecognized entry in undo list undo-tree-canary")

bug#16377: Undo Tree regression: (error "Unrecognized entry in undo list undo-tree-canary")

[Barry OReilly]

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

Don't know yet if the code change belongs in Undo Tree or Emacs but
the recipe is:

  • Start Emacs in scratch buffer with global-undo-tree-mode enabled
  • Go to BOB and insert "xxx"
  • Select first line
  • undo-tree-undo in region
  • undo-tree-redo in region
  • undo-tree-visualize
  • Navigate down (redo)*
  • Navigate up (undo)

Upon the navigate up, this error occurs:

  Debugger entered--Lisp error: (error "Unrecognized entry in undo list
undo-tree-canary")
     signal(error ("Unrecognized entry in undo list undo-tree-canary"))
     error("Unrecognized entry in undo list %S" undo-tree-canary)
     primitive-undo(1 (undo-tree-canary))
     undo-tree-undo-1(1)
     undo-tree-visualize-undo(1)
     call-interactively(undo-tree-visualize-undo nil nil)
     command-execute(undo-tree-visualize-undo)

* Sometimes the navigate down hangs with backtrace:

  Debugger entered--Lisp error: (quit)
     undo-tree-copy-list((nil))
     undo-tree-redo-1(1)
     undo-tree-visualize-redo(1)
     call-interactively(undo-tree-visualize-redo nil nil)
     command-execute(undo-tree-visualize-redo)

Don't know if it's related or not.

This recipe does not cause a problem with Emacs 24.3.

The following commit is suspicious:

commit 0c180ea96c022923ef18a255d0492bdb5ad04e02
Author: Aaron S. Hawley <aaron.s.hawley@gmail.com>
Date:   Tue Jan 8 14:13:31 2013 -0500

    * lisp/simple.el (primitive-undo): Move from undo.c.
    * src/undo.c (Fprimitive_undo): Move to simple.el.
    (syms_of_undo): Remove declaration for Sprimitive_undo.
    * test/automated/undo-tests.el: New file.

The commit moved primitive-undo from C to Elisp. In the process, it
added an else condition not present in the C code:

+             (t (error "Unrecognized entry in undo list %S" next)))))

The consequence of this bug is that when using Undo Tree, recent undo
history can become completely inaccessible.

I should note that if I don't undo in region, Undo Tree has never run
into any problems with the Emacs on trunk.

[-- Attachment #2: Type: text/html, Size: 2342 bytes --]

bug#16377: Undo Tree regression: (error "Unrecognized entry in undo list undo-tree-canary")

[Toby Cubitt]

Hi Barry,

Thanks for the bug report and recipe.

On Mon, Jan 06, 2014 at 07:32:45PM -0500, Barry OReilly wrote:
> Don't know yet if the code change belongs in Undo Tree or Emacs but
> the recipe is:
> 
>   • Start Emacs in scratch buffer with global-undo-tree-mode enabled
>   • Go to BOB and insert "xxx"
>   • Select first line
>   • undo-tree-undo in region
>   • undo-tree-redo in region
>   • undo-tree-visualize
>   • Navigate down (redo)*
>   • Navigate up (undo)
> 
> Upon the navigate up, this error occurs:
> 
>   Debugger entered--Lisp error: (error "Unrecognized entry in undo list
> undo-tree-canary")
>      signal(error ("Unrecognized entry in undo list undo-tree-canary"))
>      error("Unrecognized entry in undo list %S" undo-tree-canary)
>      primitive-undo(1 (undo-tree-canary))
>      undo-tree-undo-1(1)
>      undo-tree-visualize-undo(1)
>      call-interactively(undo-tree-visualize-undo nil nil)
>      command-execute(undo-tree-visualize-undo)

I also can't reproduce this in current stable Emacs. (Which is odd, as my
first guess from the backtrace would have been that this is a bug in the
relatively untested undo-tree undo-in-region code, and nothing to do with
Emacs.)

> * Sometimes the navigate down hangs with backtrace:
> 
>   Debugger entered--Lisp error: (quit)
>      undo-tree-copy-list((nil))
>      undo-tree-redo-1(1)
>      undo-tree-visualize-redo(1)
>      call-interactively(undo-tree-visualize-redo nil nil)
>      command-execute(undo-tree-visualize-redo)
> 
> Don't know if it's related or not.
> 
> This recipe does not cause a problem with Emacs 24.3.

Confirmed.

> The following commit is suspicious:
> 
> commit 0c180ea96c022923ef18a255d0492bdb5ad04e02
> Author: Aaron S. Hawley <aaron.s.hawley@gmail.com>
> Date:   Tue Jan 8 14:13:31 2013 -0500
> 
>     * lisp/simple.el (primitive-undo): Move from undo.c.
>     * src/undo.c (Fprimitive_undo): Move to simple.el.
>     (syms_of_undo): Remove declaration for Sprimitive_undo.
>     * test/automated/undo-tests.el: New file.
> 
> The commit moved primitive-undo from C to Elisp. In the process, it
> added an else condition not present in the C code:
>
> +             (t (error "Unrecognized entry in undo list %S" next)))))

OK, who messed with `primitive-undo' without making absolutely sure the
elisp implementation was strictly identical to the aeons-old c
implementation, and can I shoot them please? ;-)

Seriously, from the backtrace, the error does seem to be thrown by the
new test. Whether that's an Emacs regression, or just that the new test
is catching an existing bug in undo-tree, is harder to tell.

I'll play around with it in a fresh vcs Emacs when I have some time. In
the meantime, since this *is* a regression of sorts(*), can you bisect to
confirm this is the commit that broke things?

(*) I'd hope that a key requirement of moving `primitive-undo' to elisp
is surely that it not introduce changes in behaviour.

> The consequence of this bug is that when using Undo Tree, recent undo
> history can become completely inaccessible.
> 
> I should note that if I don't undo in region, Undo Tree has never run
> into any problems with the Emacs on trunk.

Have you hit other reproducible undo-in-region bugs on trunk? If so,
please report them! The undo-tree undo-in-region code is fiendishly
complex, hard to test, and under-tested.

Best,
Toby

PS: Sorry if I've broken threading on bug-gnu-emacs and generated a new
bug number. I have delivery disabled currently as I don't have time to
follow it. But it seems worth copying my reply there.
-- 
Dr T. S. Cubitt
Royal Society University Research Fellow
and Fellow of Churchill College, Cambridge
Centre for Quantum Information
DAMTP, University of Cambridge

email: tsc25@cantab.net
web:   www.dr-qubit.org

bug#16377: Undo Tree regression: (error "Unrecognized entry in undo list undo-tree-canary")

[Toby Cubitt]

On Mon, Jan 06, 2014 at 07:32:45PM -0500, Barry OReilly wrote:
> Don't know yet if the code change belongs in Undo Tree or Emacs but
> the recipe is:
> 
>   • Start Emacs in scratch buffer with global-undo-tree-mode enabled
>   • Go to BOB and insert "xxx"
>   • Select first line
>   • undo-tree-undo in region
>   • undo-tree-redo in region
>   • undo-tree-visualize
>   • Navigate down (redo)*
>   • Navigate up (undo)
> 
> Upon the navigate up, this error occurs:
> 
>   Debugger entered--Lisp error: (error "Unrecognized entry in undo list
> undo-tree-canary")
>      signal(error ("Unrecognized entry in undo list undo-tree-canary"))
>      error("Unrecognized entry in undo list %S" undo-tree-canary)
>      primitive-undo(1 (undo-tree-canary))
>      undo-tree-undo-1(1)
>      undo-tree-visualize-undo(1)
>      call-interactively(undo-tree-visualize-undo nil nil)
>      command-execute(undo-tree-visualize-undo)
>
> * Sometimes the navigate down hangs with backtrace:
>
>   Debugger entered--Lisp error: (quit)
>      undo-tree-copy-list((nil))
>      undo-tree-redo-1(1)
>      undo-tree-visualize-redo(1)
>      call-interactively(undo-tree-visualize-redo nil nil)
>      command-execute(undo-tree-visualize-redo)

OK, I can reproduce this. Here's a precise recipe:

1.  emacs -Q
2.  M-x load-file ~/undo-tree.elc
3.  M-x global-undo-tree-mode
4.  M-<
5.  type "xxx"
6.  C-a, C-SPC, C-e
7.  C-/
8.  C-g
9.  C-a, C-SPC, C-e
10. C-?
11. C-g
12.  C-x u
13. <down>
14. <up>

For me, this causes Emacs to hang in an infinite loop. I managed to
trigger the "Unrecognized entry" error once, but now I can't reproduce
it.

(Unfortunately, because of the way Emacs' undo system works, tiny changes
to the precise sequence of commands can affect how it behaves - even
apparently benign things like moving the point. I've never encountered so
many Heisenbugs as when coding undo-tree :-/

This looks like an undo-tree bug to me. The "Unrecognised entry" error
suggests the undo-tree-canary symbol has somehow ended up in a
`buffer-undo-tree' entry. That should never happen.

However, I don't understand why this should depend on which Emacs version
one runs.

I'll keep investigating. If you can rediscover the precise sequence of
steps required to trigger the error instead of the hang, please send them
to me!

Best,
Toby

-- 
Dr T. S. Cubitt
Royal Society University Research Fellow
and Fellow of Churchill College, Cambridge
Centre for Quantum Information
DAMTP, University of Cambridge

email: tsc25@cantab.net
web:   www.dr-qubit.org

bug#16377: Undo Tree regression: (error "Unrecognized entry in undo list undo-tree-canary")

[Barry OReilly]

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

> The "Unrecognised entry" error suggests the undo-tree-canary symbol
> has somehow ended up in a `buffer-undo-tree' entry.

You mean "buffer-undo-list" not "buffer-undo-tree" right?

I checked Emacs 24.3 and as I suspected it's quite easy to make
undo-tree-canary appear in the buffer-undo-list. What changed is the
error checking in core Emacs. If you expected that undo-tree-canary
would never be there between commands, that has not been so for some
time.

Could you tell me more about the purpose of undo-tree-canary?

[-- Attachment #2: Type: text/html, Size: 634 bytes --]

bug#16377: Undo Tree regression: (error "Unrecognized entry in undo list undo-tree-canary")

[Barry OReilly]

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

> * Sometimes the navigate down hangs with backtrace:
>
>   Debugger entered--Lisp error: (quit)
>      undo-tree-copy-list((nil))
>      undo-tree-redo-1(1)
>      undo-tree-visualize-redo(1)
>      call-interactively(undo-tree-visualize-redo nil nil)
>      command-execute(undo-tree-visualize-redo)

In a reproduction of this, at the start of undo-tree-copy-list,
undo-list is:

  (nil (undo-tree-id3 . -2))

Then in this while loop:

  (while (null copy)
    (setq copy
          (undo-tree-restore-GC-elts-from-pool (pop undo-list))))

undo-tree-restore-GC-elts-from-pool returns nil for both elements, so
the while loop never ends. Perhaps you want instead (ignore-whitespace
diff):

--- a/emacs/lisp/undo-tree.el    Fri Jan 17 19:18:15 2014 -0500
+++ b/emacs/lisp/undo-tree.el    Tue Jan 21 22:17:50 2014 -0500
@@ -1690,13 +1690,13 @@
 (defun undo-tree-copy-list (undo-list)
   ;; Return a deep copy of first changeset in `undo-list'. Object id's are
   ;; replaced by corresponding objects from `buffer-undo-tree' object-pool.
-  (when undo-list
     (let (copy p)
       ;; if first element contains an object id, replace it with object
from
       ;; pool, discarding element entirely if it's been GC'd
-      (while (null copy)
+    (while (and undo-list (null copy))
     (setq copy
           (undo-tree-restore-GC-elts-from-pool (pop undo-list))))
+    (when copy
       (setq copy (list copy)
         p copy)
       ;; copy remaining elements, replacing object id's with objects from

[-- Attachment #2: Type: text/html, Size: 1751 bytes --]

bug#16377: Undo Tree regression: (error "Unrecognized entry in undo list undo-tree-canary")

[Barry OReilly]

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

On Wed, Jan 22, 2014 at 9:17 AM, Toby Cubitt <
toby-dated-1391609828.ede38b@dr-qubit.org> wrote:

> On Tue, Jan 21, 2014 at 07:05:38PM -0500, Barry OReilly wrote:
> > > The "Unrecognised entry" error suggests the undo-tree-canary symbol
> > > has somehow ended up in a `buffer-undo-tree' entry.
> >
> > You mean "buffer-undo-list" not "buffer-undo-tree" right?
>
> No, I mean `buffer-undo-tree'. The canary should never end up there. In
> undo-tree-mode, primitive-undo only ever gets called on an entry copied
> from buffer-undo-tree. Hence my statement, above.
>
> > I checked Emacs 24.3 and as I suspected it's quite easy to make
> > undo-tree-canary appear in the buffer-undo-list.
>
> It's *supposed* to be in buffer-undo-list. It's not supposed to ever be
> in buffer-undo-tree. (And maybe it isn't, I'm just guessing from the
> error message here. I haven't had time to investigate yet.)
>
> > What changed is the error checking in core Emacs. If you expected that
> > undo-tree-canary would never be there between commands, that has not
> > been so for some time.
>
> I didn't expect that.
>
> > Could you tell me more about the purpose of undo-tree-canary?
>
> It lets undo-tree-mode detect when Emacs has discarded undo history from
> buffer-undo-list "behind undo-tree-mode's back". If the canary has
> vanished when undo-tree-mode looks at buffer-undo-list, Emacs must have
> purged some undo history.
>
> The new error checking in primitive-undo shouldn't affect undo-tree-mode
> in any way. I still strongly suspect this is a bug in the very delicate
> and relatively untested undo-in-region code, and the change to
> primitive-undo is a red herring.
>
>
In undo-tree-redo-1:

  (setf (undo-tree-node-undo current)
        (undo-list-pop-changeset 'discard-pos))

In undo-list-pop-changeset:

  (if (eq (car buffer-undo-list) 'undo-tree-canary)
      (push nil buffer-undo-list)
    [...])

The push call returns (nil 'undo-tree-canary). This is how it gets
into the buffer-undo-tree in my reproduction.

I'll close the Emacs bug since we're fairly sure at this point it's an
undo-tree bug.

[-- Attachment #2: Type: text/html, Size: 2749 bytes --]

bug#16377: Undo Tree regression: (error "Unrecognized entry in undo list undo-tree-canary")

[Toby Cubitt]

On Wed, Jan 22, 2014 at 10:26:05AM -0500, Barry OReilly wrote:
> On Wed, Jan 22, 2014 at 9:17 AM, Toby Cubitt <
> toby-dated-1391609828.ede38b@dr-qubit.org> wrote:
> 
> > On Tue, Jan 21, 2014 at 07:05:38PM -0500, Barry OReilly wrote:
> > > > The "Unrecognised entry" error suggests the undo-tree-canary symbol
> > > > has somehow ended up in a `buffer-undo-tree' entry.
> > >
> > > You mean "buffer-undo-list" not "buffer-undo-tree" right?
> >
> > No, I mean `buffer-undo-tree'. The canary should never end up there. In
> > undo-tree-mode, primitive-undo only ever gets called on an entry copied
> > from buffer-undo-tree. Hence my statement, above.
> >
> > > I checked Emacs 24.3 and as I suspected it's quite easy to make
> > > undo-tree-canary appear in the buffer-undo-list.
> >
> > It's *supposed* to be in buffer-undo-list. It's not supposed to ever be
> > in buffer-undo-tree. (And maybe it isn't, I'm just guessing from the
> > error message here. I haven't had time to investigate yet.)
> >
> > > What changed is the error checking in core Emacs. If you expected that
> > > undo-tree-canary would never be there between commands, that has not
> > > been so for some time.
> >
> > I didn't expect that.
> >
> > > Could you tell me more about the purpose of undo-tree-canary?
> >
> > It lets undo-tree-mode detect when Emacs has discarded undo history from
> > buffer-undo-list "behind undo-tree-mode's back". If the canary has
> > vanished when undo-tree-mode looks at buffer-undo-list, Emacs must have
> > purged some undo history.
> >
> > The new error checking in primitive-undo shouldn't affect undo-tree-mode
> > in any way. I still strongly suspect this is a bug in the very delicate
> > and relatively untested undo-in-region code, and the change to
> > primitive-undo is a red herring.
> >
> >
> In undo-tree-redo-1:
> 
>   (setf (undo-tree-node-undo current)
>         (undo-list-pop-changeset 'discard-pos))
> 
> In undo-list-pop-changeset:
> 
>   (if (eq (car buffer-undo-list) 'undo-tree-canary)
>       (push nil buffer-undo-list)
>     [...])
> 
> The push call returns (nil 'undo-tree-canary). This is how it gets
> into the buffer-undo-tree in my reproduction.

I think this is still a symptom, not the ultimate cause of the bug
(though I should probably guard against this better). `undo-tree-redo-1'
has previously called `primitive-undo', so you would expect
`buffer-undo-list' to contain at least one undo changeset (the one added
by `primitive-undo') when `undo-list-pop-changeset' is called.

Are there circumstances in which `primitive-undo' doesn't add to
`buffer-undo-list'?

Anyway, I need to step through the code and figure out what's going
on. Which I'll do as soon as I have a block of free time to set aside for
elisp debugging.

> I'll close the Emacs bug since we're fairly sure at this point it's an
> undo-tree bug.

Yup, fine by me. I think what's happened is that the new error checking
in `primitive-undo' simply caught this undo-tree bug (so it's doing its
job!)

Toby
-- 
Dr T. S. Cubitt
Royal Society University Research Fellow
and Fellow of Churchill College, Cambridge
Centre for Quantum Information
DAMTP, University of Cambridge

email: tsc25@cantab.net
web:   www.dr-qubit.org

bug#16523: Undo Tree regression: (error "Unrecognized entry in undo list undo-tree-canary")

[Toby Cubitt]

On Tue, Jan 21, 2014 at 10:23:37PM -0500, Barry OReilly wrote:
> > * Sometimes the navigate down hangs with backtrace:
> >
> >   Debugger entered--Lisp error: (quit)
> >      undo-tree-copy-list((nil))
> >      undo-tree-redo-1(1)
> >      undo-tree-visualize-redo(1)
> >      call-interactively(undo-tree-visualize-redo nil nil)
> >      command-execute(undo-tree-visualize-redo)
> 
> In a reproduction of this, at the start of undo-tree-copy-list,
> undo-list is:
> 
>   (nil (undo-tree-id3 . -2))
> 
> Then in this while loop:
> 
>   (while (null copy)
>     (setq copy
>           (undo-tree-restore-GC-elts-from-pool (pop undo-list))))
> 
> undo-tree-restore-GC-elts-from-pool returns nil for both elements, so
> the while loop never ends. Perhaps you want instead (ignore-whitespace
> diff):

Could well be. Thanks a lot for the patch!

I need to step through the minimal example and remember what this code is
supposed to be doing, and then either apply your patch or figure out what
the correct fix is (to this, and the other undo-list-pop-changeset issue
you pointed out, which at the moment seem to be separate issues).

Cheers,
Toby


> --- a/emacs/lisp/undo-tree.el    Fri Jan 17 19:18:15 2014 -0500
> +++ b/emacs/lisp/undo-tree.el    Tue Jan 21 22:17:50 2014 -0500
> @@ -1690,13 +1690,13 @@
>  (defun undo-tree-copy-list (undo-list)
>    ;; Return a deep copy of first changeset in `undo-list'. Object id's are
>    ;; replaced by corresponding objects from `buffer-undo-tree' object-pool.
> -  (when undo-list
>      (let (copy p)
>        ;; if first element contains an object id, replace it with object
> from
>        ;; pool, discarding element entirely if it's been GC'd
> -      (while (null copy)
> +    (while (and undo-list (null copy))
>      (setq copy
>            (undo-tree-restore-GC-elts-from-pool (pop undo-list))))
> +    (when copy
>        (setq copy (list copy)
>          p copy)
>        ;; copy remaining elements, replacing object id's with objects from

-- 
Dr T. S. Cubitt
Royal Society University Research Fellow
and Fellow of Churchill College, Cambridge
Centre for Quantum Information
DAMTP, University of Cambridge

email: tsc25@cantab.net
web:   www.dr-qubit.org

bug#16377: Undo Tree regression: (error "Unrecognized entry in undo list undo-tree-canary")

[Stefan Monnier]

> Are there circumstances in which `primitive-undo' doesn't add to
> `buffer-undo-list'?

Of course: if there are no changes until the next undo boundary, then
primitive-undo just doesn't do anything other than pop that
undo boundary.
And primitive-undo doesn't add any boundary, so it can end up with no
change at all to buffer-undo-list.


        Stefan

bug#16377: Undo Tree regression: (error "Unrecognized entry in undo list undo-tree-canary")

[Toby Cubitt]

On Wed, Jan 22, 2014 at 01:56:12PM -0500, Stefan Monnier wrote:
> > Are there circumstances in which `primitive-undo' doesn't add to
> > `buffer-undo-list'?
> 
> Of course: if there are no changes until the next undo boundary, then
> primitive-undo just doesn't do anything other than pop that
> undo boundary.
> And primitive-undo doesn't add any boundary, so it can end up with no
> change at all to buffer-undo-list.

Makes sense.

This shouldn't happen in undo-tree, since normally it should only call
`primitive-undo' on a non-empty undo changeset...except it's just
possible that undo-tree's undo-in-region could add empty changesets to
buffer-undo-tree under some circumstances. Which might explain why this
error is triggered by undo-in-region, but not in normal undo-tree usage.

I'll investigate when I have time. In any case, it seems clear to me that
it's an existing undo-tree bug that's been brought to light by the new
error checking, rather than breakage from the new `primitive-undo'
implementation. So the ball's in my court.

Toby
-- 
Dr T. S. Cubitt
Royal Society University Research Fellow
and Fellow of Churchill College, Cambridge
Centre for Quantum Information
DAMTP, University of Cambridge

email: tsc25@cantab.net
web:   www.dr-qubit.org

bug#16377: Undo Tree regression: (error "Unrecognized entry in undo list undo-tree-canary")

[Keith David Bershatsky]

I have been working on a fork of undo-tree.el, and am interested in resolving this particular bug.  I saw a recent post on reddit/emacs asking for help on this issue, and thought I would take this opportunity to chime-in.  I am presently using the following modified version of primitive-undo in my forked version for 2 reasons.  First, is to just throw a message instead of an error if bug 16377 shows its head.  Second, I like to have the window-point update in the target window while I am doing a change in the undo-tree visualization buffer.

I have no idea whether bypassing the error about 16377 is a bad thing, so I thought I'd share my function and let the experts decide how best to handle the bug.  I also wanted to remind the powers that be that this bug still affects people in today's day and age.  Another user on reddit added a comment stating he/she also had the same problem.  I have seen this bug as well when playing with undo/redo in region.

Thanks.

(defun undo-tree--primitive-undo (n list)
"Undo N records from the front of the list LIST.
Return what remains of the list."
  (let ((arg n)
        ;; In a writable buffer, enable undoing read-only text that is
        ;; so because of text properties.
        (inhibit-read-only t)
        ;; Don't let `intangible' properties interfere with undo.
        (inhibit-point-motion-hooks t)
        ;; We use oldlist only to check for EQ.  ++kfs
        (oldlist buffer-undo-list)
        (did-apply nil)
        (next nil)
        (window-of-current-buffer (get-buffer-window (current-buffer)))
        (selected-window (selected-window)))
    (while (> arg 0)
      (while (setq next (pop list))     ;Exit inner loop at undo boundary.
        ;; Handle an integer by setting point to that value.
        (pcase next
          ((pred integerp)
            (goto-char next)
              (unless (eq window-of-current-buffer selected-window)
                (set-window-point window-of-current-buffer next)))
          ;; Element (t . TIME) records previous modtime.
          ;; Preserve any flag of NONEXISTENT_MODTIME_NSECS or
          ;; UNKNOWN_MODTIME_NSECS.
          (`(t . ,time)
           ;; If this records an obsolete save
           ;; (not matching the actual disk file)
           ;; then don't mark unmodified.
            (when (or (equal time (visited-file-modtime))
                      (and (consp time)
                           (equal (list (car time) (cdr time)) (visited-file-modtime))))
              (when (fboundp 'unlock-buffer)
                (unlock-buffer))
              (set-buffer-modified-p nil)))
          ;; Element (nil PROP VAL BEG . END) is property change.
          (`(nil . ,(or `(,prop ,val ,beg . ,end) pcase--dontcare))
            (when (or (> (point-min) beg) (< (point-max) end))
              (let ((debug-on-quit nil)
                    (msg (concat
                           "undo-tree--primative-undo (1 of 4):"
                           "  "
                           "Changes to be undone are outside visible portion of buffer.")))
                (signal 'quit `(,msg))))
           (put-text-property beg end prop val))
          ;; Element (BEG . END) means range was inserted.
          (`(,(and beg (pred integerp)) . ,(and end (pred integerp)))
           ;; (and `(,beg . ,end) `(,(pred integerp) . ,(pred integerp)))
           ;; Ideally: `(,(pred integerp beg) . ,(pred integerp end))
            (when (or (> (point-min) beg) (< (point-max) end))
              (let ((debug-on-quit nil)
                    (msg (concat
                           "undo-tree--primative-undo (2 of 4):"
                           "  "
                           "Changes to be undone are outside visible portion of buffer.")))
                (signal 'quit `(,msg))))
           ;; Set point first thing, so that undoing this undo
           ;; does not send point back to where it is now.
           (goto-char beg)
           (delete-region beg end)
           (unless (eq window-of-current-buffer selected-window)
             (set-window-point window-of-current-buffer beg)))
          ;; Element (apply FUN . ARGS) means call FUN to undo.
          (`(apply . ,fun-args)
           (let ((currbuff (current-buffer)))
             (if (integerp (car fun-args))
                 ;; Long format: (apply DELTA START END FUN . ARGS).
                 (pcase-let* ((`(,delta ,start ,end ,fun . ,args) fun-args)
                              (start-mark (copy-marker start nil))
                              (end-mark (copy-marker end t)))
                    (when (or (> (point-min) start) (< (point-max) end))
              (let ((debug-on-quit nil)
                    (msg (concat
                           "undo-tree--primative-undo (3 of 4):"
                           "  "
                           "Changes to be undone are outside visible portion of buffer.")))
                (signal 'quit `(,msg))))
                   (apply fun args) ;; Use `save-current-buffer'?
                   ;; Check that the function did what the entry
                   ;; said it would do.
                   (unless (and (= start start-mark)
                                (= (+ delta end) end-mark))
                     (error "Changes to be undone by function different than announced"))
                   (set-marker start-mark nil)
                   (set-marker end-mark nil))
               (apply fun-args))
             (unless (eq currbuff (current-buffer))
               (error "Undo function switched buffer"))
             (setq did-apply t)))
          ;; Element (STRING . POS) means STRING was deleted.
          (`(,(and string (pred stringp)) . ,(and pos (pred integerp)))
           (when (let ((apos (abs pos)))
                    (or (< apos (point-min)) (> apos (point-max))))
              (let ((debug-on-quit nil)
                    (msg (concat
                           "undo-tree--primative-undo (4 of 4):"
                           "  "
                           "Changes to be undone are outside visible portion of buffer.")))
                (signal 'quit `(,msg))))
           (let (valid-marker-adjustments)
             ;; Check that marker adjustments which were recorded
             ;; with the (STRING . POS) record are still valid, ie
             ;; the markers haven't moved.  We check their validity
             ;; before reinserting the string so as we don't need to
             ;; mind marker insertion-type.
             (while (and (markerp (car-safe (car list)))
                         (integerp (cdr-safe (car list))))
               (let* ((marker-adj (pop list))
                      (m (car marker-adj)))
                 (and (eq (marker-buffer m) (current-buffer))
                      (= pos m)
                      (push marker-adj valid-marker-adjustments))))
             ;; Insert string and adjust point
             (if (< pos 0)
                 (progn
                   (goto-char (- pos))
                   (insert string))
               (goto-char pos)
               (insert string)
               (goto-char pos))
             (unless (eq window-of-current-buffer selected-window)
               (set-window-point window-of-current-buffer pos))
             ;; Adjust the valid marker adjustments
             (dolist (adj valid-marker-adjustments)
               (set-marker (car adj)
                           (- (car adj) (cdr adj))))))
          ;; (MARKER . OFFSET) means a marker MARKER was adjusted by OFFSET.
          (`(,(and marker (pred markerp)) . ,(and offset (pred integerp)))
            (let ((msg
                    (concat
                      "undo-tree--primitive-undo:  "
                      (format "Encountered %S entry in undo list with no matching (TEXT . POS) entry"
                              next))))
              (message msg))
           ;; Even though these elements are not expected in the undo
           ;; list, adjust them to be conservative for the 24.4
           ;; release.  (Bug#16818)
           (when (marker-buffer marker)
             (set-marker marker
                         (- marker offset)
                         (marker-buffer marker))))
          (_
            (if (eq next 'undo-tree-canary)
              (message "undo-tree--primitive-undo:  catch-all found `%s'." next)
              (error "Unrecognized entry in undo list %S" next)))))
      (setq arg (1- arg)))
    ;; Make sure an apply entry produces at least one undo entry,
    ;; so the test in `undo' for continuing an undo series
    ;; will work right.
    (if (and did-apply
             (eq oldlist buffer-undo-list))
        (setq buffer-undo-list
              (cons (list 'apply 'cdr nil) buffer-undo-list))))
  list)

bug#16377: Undo Tree regression: (error "Unrecognized entry in undo list undo-tree-canary")

[Keith David Bershatsky]

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

Thank you, Stefan, for taking another look at #16377.

The attached `patch.diff` relates to the modified version of `primitive-undo` that I am using in-house.  It applies to the latest version of the master branch (downloaded today 07/05/2017) bearing commit 7a0170de20fe1225d3eeac099d1e61a0c0410bf3.  It looks like the revision for bug#25599 was applied by the Emacs team sometime after I made my revised version -- I've never tried using that revised section of code.

Keith

;;;;;;;;;;;;;;;;;;;;;;; PREVIOUS MESSAGE ;;;;;;;;;;;;;;;;;;;;;;

DATE:  [07-05-2017 21:06:50] <06 Jul 2017 00:06:50 -0400>
FROM:  Stefan Monnier <monnier@IRO.UMontreal.CA>
> 
> > I am presently using the following modified version of primitive-undo in my
> [...]
> 
> Please send it as a patch, so we get to see what you've changed,
> I don't know about you, but I personally do not remember the current
> code of primitive-undo by heart.
> 
> 
>         Stefan

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


[-- Attachment #2: patch.diff --]
[-- Type: application/diff, Size: 7984 bytes --]

bug#16377: Undo Tree regression: (error "Unrecognized entry in undo list undo-tree-canary")

[Stefan Monnier]

> +        (window-of-current-buffer (get-buffer-window (current-buffer)))
> +        (selected-window (selected-window)))
[...]
> +              (unless (eq window-of-current-buffer selected-window)

Better check (eq (window-buffer) (current-buffer)), since these two
functions are mere accessors, whereas get-buffer-window is a funny
function which returns *one of* the buffer's windows (or nil) and is
hence both more costly (it has a loop inside) and less reliable.

> -           (when (or (> (point-min) beg) (< (point-max) end))
> -             (error "Changes to be undone are outside visible portion of buffer"))
> +            (when (or (> (point-min) beg) (< (point-max) end))
> +              (let ((debug-on-quit nil)
> +                    (msg (concat
> +                           "undo-tree--primitive-undo (1 of 4):"
> +                           "  "
> +                           "Changes to be undone are outside visible portion of buffer.")))
> +                (signal 'quit `(,msg))))

Not sure what is the benefit of signaling `quit` rather than `error`.
Can you expand on that?

> -               ;; Insert might have invalidated some of the markers
> -               ;; via modification hooks.  Update only the currently
> -               ;; valid ones (bug#25599).
> -               (if (marker-buffer (car adj))
> -                   (set-marker (car adj)
> -                               (- (car adj) (cdr adj)))))))
> +               (set-marker (car adj)
> +                           (- (car adj) (cdr adj))))))

IIUC, this is an unintended change in your code, right?

>            ;; (MARKER . OFFSET) means a marker MARKER was adjusted by OFFSET.
>            (`(,(and marker (pred markerp)) . ,(and offset (pred integerp)))
> -           (warn "Encountered %S entry in undo list with no matching (TEXT . POS) entry"
> -                 next)
> +            (let ((msg
> +                    (concat
> +                      "undo-tree--primitive-undo:  "
> +                      (format "Encountered %S entry in undo list with no matching (TEXT . POS) entry"
> +                              next))))
> +              (message msg))

What is this change meant to do?

> +          (_
> +            (if (eq next 'undo-tree-canary)
> +              (message "undo-tree--primitive-undo:  catch-all found `%s'." next)
> +              (error "Unrecognized entry in undo list %S" next)))))

This might make sense to work around the problem, but is clearly not an
actual fix.  IIUC Tony said it looked like a bug in undo-tree.
Has there been any progress on finding/fixing the bug there?
What is this "canary" meant to do?  If it shouldn't signal an error
here, maybe rather than the constant `undo-tree-canary`, undo-tree
should use another constant value, i.e. one that is a valid (and
harmless) undo entry.


        Stefan

bug#16377: Undo Tree regression: (error "Unrecognized entry in undo list undo-tree-canary")

[Keith David Bershatsky]

Thank you for the helpful critique to substitute `window-buffer` for `get-window-buffer`.

I like to keep `debug-on-error` always set to `t`, and known situations I generally limit to showing me just a message in the echo area with the name of the function that generated it.  That's why I've been using the `quit` signal instead of popping open a `*Backrace*` buffer for familiar situations.

The code that the Emacs team implemented in response to bug#25599 is probably fine.  I just hadn't seen that before today, and my code predates its implementation.

Substituting the `warn` pop-up buffer for a plain old `message` was just a matter of personal preference.  Nothing substantive there was intended.

The existence and discussion surrounding `undo-tree.el` predates my usage of that library, but from what I can tell, at some point in the past `primitive-undo' was "improved" to start checking for errors and this resulted in bug #16377.  From an untrained layman's way of thinking, I am "guessing" that if undo-tree worked fine before `primitive-undo` was modified to throw an error, then perhaps it is not "a problem" with undo-tree except to the extent that undo-tree may need to "evolve" to play nice with the current version of `primitive-undo`.  Based on that "optional evolution theory", I created the workaround to just throw an informative message instead of an error.  However, I do not know if that approach could lead to problems.

I've spent quite a bit of time studying certain sections of the undo-tree.el library, but there are sections of the code that are still "Greek to me".  My understanding of the `undo-tree-canary` symbol inside the `buffer-undo-list` is that it is a way for undo-tree to check if it has interacted with the `buffer-undo-list`.  If the canary is not there, then handle the situation differently.  If the canary is there, then process the `buffer-undo-list` until reaching the canary.  It could be any arbitrary symbol so long as it remains at the tail end of the `buffer-undo-list` with a `nil` before it while undo-tree is being used in the buffer.  There is only one situation I am aware of where the `undo-tree-canary` disappears, and it happens sometimes with garbage collection (bug #27214).  Whate
 ver symbol is used, it needs to remain in the `buffer-undo-list` until `undo-tree-mode` is deactivated.  I suppose the design could have been different, but Dr. Cubitt probably had several additiona
 l reasons for using a constant symbol such as the `undo-tree-canary`.

Bug #16377 might very well be resolvable by tweaking/fixing undo-tree.el; however, the undo/redo in region code is still a few light years beyond my present abilities.

Keith

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

> > +          (_
> > +            (if (eq next 'undo-tree-canary)
> > +              (message "undo-tree--primitive-undo:  catch-all found `%s'." next)
> > +              (error "Unrecognized entry in undo list %S" next)))))
> 
> This might make sense to work around the problem, but is clearly not an
> actual fix.  IIUC Tony said it looked like a bug in undo-tree.
> Has there been any progress on finding/fixing the bug there?
> What is this "canary" meant to do?  If it shouldn't signal an error
> here, maybe rather than the constant `undo-tree-canary`, undo-tree
> should use another constant value, i.e. one that is a valid (and
> harmless) undo entry.
> 
> 
>         Stefan

bug#16377: Undo Tree regression: (error "Unrecognized entry in undo list undo-tree-canary")

[Toby Cubitt]

On Wed, Jul 05, 2017 at 11:25:10PM -0700, Keith David Bershatsky wrote:
> The existence and discussion surrounding `undo-tree.el` predates my
> usage of that library, but from what I can tell, at some point in the
> past `primitive-undo' was "improved" to start checking for errors and
> this resulted in bug #16377.

No, the new error checking just helpfully revealed an existing bug in
undo-tree's undo-in-region support (which frankly has always been flaky,
as it's extraordinarily difficult to reliably reproduce undo
bugs). There's even an `undo-tree-enable-undo-in-region' toggle to
disable undo-in-region support, for exactly this reason. Probably I
should make it default to "off" for now.

I'm way behind on dealing with undo-tree bug reports whilst busy with
"real life". #16377 is a very helpful bug report, which I can now
reproduce much more reliably with current Emacs version than I could when
it was originally reported. I hope to have time for a mammoth undo-tree
maintenance session later this summer. If that works out, I'll look into
it then.

> From an untrained layman's way of thinking, I am "guessing" that if
> undo-tree worked fine before `primitive-undo` was modified to throw an
> error, then perhaps it is not "a problem" with undo-tree except to the
> extent that undo-tree may need to "evolve" to play nice with the
> current version of `primitive-undo`.

The undo-tree-canary symbol should never end up in the list passed by
undo-tree to `primitive-undo', so it shouldn't matter whether it throws
an error. `primitive-undo' throwing an error on garbage, as in current
Emacs, makes complete sense from my perspective.

> Based on that "optional evolution theory", I created the workaround to
> just throw an informative message instead of an error.  However, I do
> not know if that approach could lead to problems.

I deliberately didn't touch `primitive-undo' in undo-tree. It was a c
primitive when I wrote undo-tree, and overriding primitives is not a good
idea.

Even now, I wouldn't recommend overriding it without rewriting undo-tree
so it completely rips out and replaces the Emacs undo system. (If that's
even possible -- it didn't used to be because too much was done in c.) As
currently implemented, undo-tree sits on top of the standard Emacs undo
system and overrides as little as possible.

I certainly wouldn't disable the error reporting, since that just masks
the bug, it doesn't fix it.

> I've spent quite a bit of time studying certain sections of the
>  undo-tree.el library, but there are sections of the code that are
>  still "Greek to me".  My understanding of the `undo-tree-canary`
>  symbol inside the `buffer-undo-list` is that it is a way for undo-tree
>  to check if it has interacted with the `buffer-undo-list`.

The *only* purpose of the undo-tree-canary is to detect when Emacs has
discarded undo history from buffer-undo-list before undo-tree got to look
at it. In that situation, the entire contents of buffer-undo-tree gets
discarded (because it only contains undo history that's being discarded),
and gets rebuilt afresh from the new contents of buffer-undo-list.

> There is only one situation I am aware of where the `undo-tree-canary`
> disappears, and it happens sometimes with garbage collection (bug
> #27214).  Whatever symbol is used, it needs to remain in the
> `buffer-undo-list` until `undo-tree-mode` is deactivated.

No, it's fine for it to be removed from buffer-undo-list, as long as this
only happens when the whole undo history is being discarded.

> I suppose the design could have been different, but Dr. Cubitt probably
> had several additiona l reasons for using a constant symbol such as the
> `undo-tree-canary`.

Anything that's an invalid undo entry would do the job. A symbol with the
package prefix is the obvious choice.

> Bug #16377 might very well be resolvable by tweaking/fixing
> undo-tree.el; however, the undo/redo in region code is still a few
> light years beyond my present abilities.

Unfortunately, it's also always been a few light years beyond my ability
to debug :-/

Best,
Toby
-- 
Dr T. S. Cubitt
Royal Society University Research Fellow
Quantum Information Theory
Department of Computer Science
University College London

email: tsc25@cantab.net
web:   www.dr-qubit.org

bug#16377: Undo Tree regression: (error "Unrecognized entry in undo list undo-tree-canary")

[Toby Cubitt]

On Thu, Jul 06, 2017 at 10:02:56AM +0100, Toby Cubitt wrote:
> I'm way behind on dealing with undo-tree bug reports whilst busy with
> "real life". #16377 is a very helpful bug report, which I can now
> reproduce much more reliably with current Emacs version than I could when
> it was originally reported. I hope to have time for a mammoth undo-tree
> maintenance session later this summer. If that works out, I'll look into
> it then.

Scratch that. I can't reproduce #16377 in Emacs 25.2.1, undo-tree git
head, except by calling undo-tree-undo/redo commands via M-x in buffers
where undo-tree-mode is disabled.

Calling undo-tree commands with undo-tree-mode disabled is entirely
expected to mess up buffer-undo-list. I've added checks in git to all the
undo-tree interactive commands to throw a user-error if they're called
when undo-tree is not enabled, to guard against this.

But that has nothing to do with the original bug, which appears to
already be fixed in git.

Toby
-- 
Dr T. S. Cubitt
Royal Society University Research Fellow
Quantum Information Theory
Department of Computer Science
University College London

email: tsc25@cantab.net
web:   www.dr-qubit.org