[elpa] externals/undo-tree c638cbd 051/195: General code tidying and reorganisation.

[Stefan Monnier]

branch: externals/undo-tree
commit c638cbd3f5d18520f9644080209e8a531c2d2cdc
Author: Toby S. Cubitt <toby-undo-tree@dr-qubit.org>
Commit: Toby S. Cubitt <toby-undo-tree@dr-qubit.org>

    General code tidying and reorganisation.
---
 undo-tree.el | 477 +++++++++++++++++++++++++++++++----------------------------
 1 file changed, 249 insertions(+), 228 deletions(-)

diff --git a/undo-tree.el b/undo-tree.el
index 4cbe560..9d0f5b1 100644
--- a/undo-tree.el
+++ b/undo-tree.el
@@ -196,9 +196,9 @@
 ;;                                x  (second undo)
 ;;
 ;;
-;; Actually, since the buffer returns to a previous state after an undo, a
-;; better way to visualize it is to imagine the string of changes turning back
-;; on itself:
+;; Actually, since the buffer returns to a previous state after an undo,
+;; perhaps a better way to visualize it is to imagine the string of changes
+;; turning back on itself:
 ;;
 ;;        (initial buffer state)  o
 ;;                                |
@@ -251,7 +251,7 @@
 ;;
 ;; Now, what if you change your mind about those undos, and decide you did
 ;; like those other changes you'd made after all? With the standard undo/redo
-;; system, you're stuck. There's no way to recover them, because that branch
+;; system, you're lost. There's no way to recover them, because that branch
 ;; was discarded when you made the new edit.
 ;;
 ;; However, in Emacs' undo system, those old buffer states are still there in
@@ -298,11 +298,12 @@
 ;;                             |/
 ;;                             o
 ;;
-;; But if you're unlucky, you happen to have moved the point (say) after
-;; getting to the point labelled "got this far". In that case, you've "broken
-;; the undo chain". If you try to undo now, Emacs thinks you're trying to undo
-;; the undos! So to get back to the initial state you now have to rewind
-;; through *all* the changes, including the undos you just did:
+;; But if you're unlucky, and you happen to have moved the point (say) after
+;; getting to the point labelled "got this far", then you've "broken the undo
+;; chain". Hold on to something solid, because things are about to get
+;; hairy. If you try to undo now, Emacs thinks you're trying to undo the
+;; undos! So to get back to the initial state you now have to rewind through
+;; *all* the changes, including the undos you just did:
 ;;
 ;;      (trying to get   o                          x  (finally got there!)
 ;;       to this state)  |                          |
@@ -325,11 +326,12 @@
 ;;
 ;; In practice you can just hold down the undo key until you reach the buffer
 ;; state that you want. But whatever you do, don't move around in the buffer
-;; to check you've got back to where you want! Because you'll break the undo
-;; chain, and then you'll have to traverse the entire string of undos again to
-;; get back to the point at which you broke the chain. Undo in region and
-;; commands such as `undo-only' help to make using Emacs' undo a little
-;; easier, but nonetheless it remains confusing for many people.
+;; to *check* that you've got back to where you want! Because you'll break the
+;; undo chain, and then you'll have to traverse the entire string of undos
+;; again, just to get back to the point at which you broke the
+;; chain. Undo-in-region and commands such as `undo-only' help to make using
+;; Emacs' undo a little easier, but nonetheless it remains confusing for many
+;; people.
 ;;
 ;;
 ;; So what does `undo-tree-mode' do? Remember the diagram we drew to represent
@@ -401,9 +403,9 @@
 ;;                                |
 ;;                        (redo)  x
 ;;
-;; Now you're on the other branch, and if you undo and redo changes you'll
-;; stay on that branch, moving up and down through the buffer states located
-;; on that branch. Until you decide to switch branches again, of course.
+;; Now you're on the other branch, if you undo and redo changes you'll stay on
+;; that branch, moving up and down through the buffer states located on that
+;; branch. Until you decide to switch branches again, of course.
 ;;
 ;; Real undo trees might have multiple branches and sub-branches:
 ;;
@@ -422,8 +424,8 @@
 ;; will likely frazzle your brain circuits! But in `undo-tree-mode', you're
 ;; just moving around this undo history tree. Most of the time, you'll
 ;; probably only need to stay on the most recent branch, in which case it
-;; behaves like standard undo/redo, so is just as simple to understand. But if
-;; you ever need to recover a buffer state on a different branch, the
+;; behaves like standard undo/redo, and is just as simple to understand. But
+;; if you ever need to recover a buffer state on a different branch, the
 ;; possibility of switching between branches and accessing the full undo
 ;; history is still there.
 ;;
@@ -436,20 +438,20 @@
 ;; diagrams, because `undo-tree-mode' includes an undo-tree visualizer which
 ;; draws them for you! In fact, it draws even better diagrams: it highlights
 ;; the node representing the current buffer state, it highlights the current
-;; branch, and you can toggle the display of time-stamps for each buffer
-;; state. (There's one other tiny difference: the visualizer puts the most
-;; recent branch on the left rather than the right.)
+;; branch, and (by hitting "t") you can toggle the display of
+;; time-stamps. (There's one other tiny difference: the visualizer puts the
+;; most recent branch on the left rather than the right.)
 ;;
 ;; In the visualizer, the usual keys for moving up and down a buffer instead
 ;; move up and down the undo history tree (e.g. the up and down arrow keys, or
 ;; "C-n" and "C-p"). The state of the "parent" buffer (the buffer whose undo
 ;; history you are visualizing) is updated as you move around the undo tree in
 ;; the visualizer. If you reach a branch point in the visualizer, the usual
-;; keys for moving forward and backward in a buffer instead switch which
-;; branch to follow (e.g. the left and right arrow keys, or "C-f" and "C-b").
-;; Clicking with the mouse on any node in the visualizer will take you
-;; directly to that node, resetting the state of the parent buffer to the
-;; state represented by that node.
+;; keys for moving forward and backward in a buffer instead switch branch
+;; (e.g. the left and right arrow keys, or "C-f" and "C-b"). And clicking with
+;; the mouse on any node in the visualizer will take you directly to that
+;; node, resetting the state of the parent buffer to the state represented by
+;; that node.
 ;;
 ;; It can be useful to see how long ago the parent buffer was in the state
 ;; represented by a particular node in the visualizer. Hitting "t" in the
@@ -459,7 +461,7 @@
 ;; since you last undid any changes.)
 ;;
 ;; Finally, hitting "q" will quit the visualizer, leaving the parent buffer in
-;; whatever state you were last on.
+;; whatever state you ended at.
 ;;
 ;;
 ;;
@@ -499,6 +501,7 @@
 ;;   visualizer's parent buffer, or switch to the parent buffer if no window
 ;;   is displaying it
 ;; * fixed bug in `undo-tree-switch-branch'
+;; * general code tidying and reorganisation
 ;;
 ;; Version 0.1.6
 ;; * added `undo-tree-mode-lighter' customization option to allow the
@@ -506,14 +509,14 @@
 ;; * bug-fix in `undo-tree-discard-node'
 ;; * added `undo-tree-save-state-to-register' and
 ;;   `undo-tree-restore-state-from-register' commands and keybindings for
-;;   saving/restoring buffer states using registers
+;;   saving/restoring undo-tree states using registers
 ;;
 ;; Version 0.1.5
 ;; * modified `undo-tree-visualize' to mark the visualizer window as
-;;   soft-dedicated and changed `undo-tree-visualizer-quit' to use
-;;   `kill-buffer', so that visualizer window is deleted along with buffer if
-;;   visualizer buffer was displayed in a new window, but not if it was
-;;   displayed in an existing window.
+;;   soft-dedicated, and changed `undo-tree-visualizer-quit' to use
+;;   `kill-buffer', so that the visualizer window is deleted along with its
+;;   buffer if the visualizer buffer was displayed in a new window, but not if
+;;   it was displayed in an existing window.
 ;;
 ;; Version 0.1.4
 ;; * modified `undo-tree-undo' and `undo-tree-redo' to always replace
@@ -840,103 +843,9 @@ part of `buffer-undo-tree'."
     new))
 
 
-(defun undo-tree-compute-widths (undo-tree)
-  "Recursively compute widths for all UNDO-TREE's nodes."
-  (let ((stack (list (undo-tree-root undo-tree)))
-        res)
-    (while stack
-      ;; try to compute widths for node at top of stack
-      (if (undo-tree-node-p
-           (setq res (undo-tree-node-compute-widths (car stack))))
-          ;; if computation fails, it returns a node whose widths still need
-          ;; computing, which we push onto the stack
-          (push res stack)
-        ;; otherwise, store widths and remove it from stack
-        (setf (undo-tree-node-lwidth (car stack)) (aref res 0)
-              (undo-tree-node-cwidth (car stack)) (aref res 1)
-              (undo-tree-node-rwidth (car stack)) (aref res 2))
-        (pop stack)))))
-
-
-(defun undo-tree-node-compute-widths (node)
-  ;; Compute NODE's left-, centre-, and right-subtree widths. Returns widths
-  ;; (in a vector) if successful. Otherwise, returns a node whose widths need
-  ;; calculating before NODE's can be calculated.
-  (let ((num-children (length (undo-tree-node-next node)))
-        (lwidth 0) (cwidth 0) (rwidth 0)
-        p w)
-    (catch 'need-widths
-      (cond
-       ;; leaf nodes have 0 width
-       ((= 0 num-children)
-        (setf cwidth 1
-              (undo-tree-node-lwidth node) 0
-              (undo-tree-node-cwidth node) 1
-              (undo-tree-node-rwidth node) 0))
-
-       ;; odd number of children
-       ((= (mod num-children 2) 1)
-        (setq p (undo-tree-node-next node))
-        ;; compute left-width
-        (dotimes (i (/ num-children 2))
-          (if (undo-tree-node-lwidth (car p))
-              (incf lwidth (+ (undo-tree-node-lwidth (car p))
-                              (undo-tree-node-cwidth (car p))
-                              (undo-tree-node-rwidth (car p))))
-            ;; if child's widths haven't been computed, return that child
-            (throw 'need-widths (car p)))
-          (setq p (cdr p)))
-        (if (undo-tree-node-lwidth (car p))
-            (incf lwidth (undo-tree-node-lwidth (car p)))
-          (throw 'need-widths (car p)))
-        ;; centre-width is inherited from middle child
-        (setf cwidth (undo-tree-node-cwidth (car p)))
-        ;; compute right-width
-        (incf rwidth (undo-tree-node-rwidth (car p)))
-        (setq p (cdr p))
-        (dotimes (i (/ num-children 2))
-          (if (undo-tree-node-lwidth (car p))
-              (incf rwidth (+ (undo-tree-node-lwidth (car p))
-                              (undo-tree-node-cwidth (car p))
-                              (undo-tree-node-rwidth (car p))))
-            (throw 'need-widths (car p)))
-          (setq p (cdr p))))
-
-       ;; even number of children
-       (t
-        (setq p (undo-tree-node-next node))
-        ;; compute left-width
-        (dotimes (i (/ num-children 2))
-          (if (undo-tree-node-lwidth (car p))
-              (incf lwidth (+ (undo-tree-node-lwidth (car p))
-                              (undo-tree-node-cwidth (car p))
-                              (undo-tree-node-rwidth (car p))))
-            (throw 'need-widths (car p)))
-          (setq p (cdr p)))
-        ;; centre-width is 0 when number of children is even
-        (setq cwidth 0)
-        ;; compute right-width
-        (dotimes (i (/ num-children 2))
-          (if (undo-tree-node-lwidth (car p))
-              (incf rwidth (+ (undo-tree-node-lwidth (car p))
-                              (undo-tree-node-cwidth (car p))
-                              (undo-tree-node-rwidth (car p))))
-            (throw 'need-widths (car p)))
-          (setq p (cdr p)))))
-
-      ;; return left-, centre- and right-widths
-      (vector lwidth cwidth rwidth))))
-
-
-(defun undo-tree-clear-visualizer-data (undo-tree)
-  ;; Clear visualizer data from UNDO-TREE.
-  (let ((stack (list (undo-tree-root undo-tree)))
-        node)
-    (while stack
-      (setq node (pop stack))
-      (setf (undo-tree-node-visualizer node) nil)
-      (dolist (n (undo-tree-node-next node))
-        (push n stack)))))
+(defmacro undo-tree-num-branches ()
+  "Return number of branches at current undo tree node."
+  '(length (undo-tree-node-next (undo-tree-current buffer-undo-tree))))
 
 
 (defun undo-tree-position (node list)
@@ -952,10 +861,102 @@ Comparison is done with 'eq."
       nil)))
 
 
-(defmacro undo-tree-num-branches ()
-  ;; Return number of branches at current undo tree node.
-  '(length (undo-tree-node-next (undo-tree-current buffer-undo-tree))))
+(defvar *undo-tree-id-counter* 0)
+(defmacro undo-tree-generate-id ()
+  ;; Generate a new, unique id (uninterned symbol).
+  ;; The name is made by appending a number to "undo-tree-id".
+  ;; (Copied from CL package `gensym'.)
+  `(let ((num (prog1 *undo-tree-id-counter* (incf *undo-tree-id-counter*))))
+     (make-symbol (format "undo-tree-id%d" num))))
+
+
+
+
+;;; =====================================================================
+;;;         Utility functions for handling `buffer-undo-list'
+
+(defun undo-list-pop-changeset ()
+  ;; Pop changeset from `buffer-undo-list'.
+  ;; discard undo boundaries and marker adjustment entries at head of list
+  (while (or (null (car buffer-undo-list))
+            (and (consp (car buffer-undo-list))
+                 (markerp (caar buffer-undo-list))))
+    (setq buffer-undo-list (cdr buffer-undo-list)))
+  ;; pop elements up to next undo boundary
+  (unless (eq (car buffer-undo-list) 'undo-tree-canary)
+    (let* ((changeset (cons (pop buffer-undo-list) nil))
+           (p changeset))
+      (while (car buffer-undo-list)
+        (setcdr p (cons (pop buffer-undo-list) nil))
+       ;; discard marker adjustment entries (see Commentary, above)
+       (if (and (consp (cadr p)) (markerp (car (cadr p))))
+           (setcdr p nil)
+         (setq p (cdr p))))
+      changeset)))
+
+
+
+(defun undo-list-transfer-to-tree ()
+  ;; Transfer entries accumulated in `buffer-undo-list' to `buffer-undo-tree'.
 
+  ;; if `buffer-undo-tree' is empty, create initial undo-tree and make sure
+  ;; there's a canary at end of `buffer-undo-list'
+  (when (null buffer-undo-tree)
+    (setq buffer-undo-tree (make-undo-tree))
+    (let ((elt (last buffer-undo-list)))
+      (unless (eq (car elt) 'undo-tree-canary)
+       (setcdr elt '(nil undo-tree-canary)))))
+
+  ;; if `buffer-undo-list' is empty, add a canary
+  (if (null buffer-undo-list)
+      (setq buffer-undo-list '(nil undo-tree-canary))
+    (unless (eq (cadr buffer-undo-list) 'undo-tree-canary)
+      ;; create new node from first changeset in `buffer-undo-list', save old
+      ;; `buffer-undo-tree' current node, and make new node the current node
+      (let* ((node (make-undo-tree-node nil (undo-list-pop-changeset)))
+             (splice (undo-tree-current buffer-undo-tree))
+             (size (undo-list-byte-size (undo-tree-node-undo node))))
+        (setf (undo-tree-current buffer-undo-tree) node)
+        ;; grow tree fragment backwards using `buffer-undo-list' changesets
+        (while (and buffer-undo-list
+                    (not (eq (cadr buffer-undo-list) 'undo-tree-canary)))
+          (setq node
+                (undo-tree-grow-backwards node (undo-list-pop-changeset)))
+          (incf size (undo-list-byte-size (undo-tree-node-undo node))))
+        ;; if no undo history has been discarded from `buffer-undo-list' since
+        ;; last transfer, splice new tree fragment onto end of old
+        ;; `buffer-undo-tree' current node
+        (if (eq (cadr buffer-undo-list) 'undo-tree-canary)
+            (progn
+              (setf (undo-tree-node-previous node) splice)
+              (push node (undo-tree-node-next splice))
+              (setf (undo-tree-node-branch splice) 0)
+              (incf (undo-tree-size buffer-undo-tree) size))
+          ;; if undo history has been discarded, replace entire
+          ;; `buffer-undo-tree' with new tree fragment
+          (setq node (undo-tree-grow-backwards node nil))
+          (setf (undo-tree-root buffer-undo-tree) node)
+          (setq buffer-undo-list '(nil undo-tree-canary))
+          (setf (undo-tree-size buffer-undo-tree) size)))
+      ;; discard undo history if necessary
+      (undo-tree-discard-history))))
+
+
+(defun undo-list-byte-size (undo-list)
+  ;; Return size (in bytes) of UNDO-LIST
+  (let ((size 0) (p undo-list))
+    (while p
+      (incf size 8)  ; cons cells use up 8 bytes
+      (when (and (consp (car p)) (stringp (caar p)))
+        (incf size (string-bytes (caar p))))
+      (setq p (cdr p)))
+    size))
+
+
+
+
+;;; =====================================================================
+;;;                  History discarding functions
 
 (defun undo-tree-oldest-leaf (node)
   ;; Return oldest leaf node below NODE.
@@ -974,9 +975,6 @@ Comparison is done with 'eq."
 
   ;; don't discard current node
   (unless (eq node (undo-tree-current buffer-undo-tree))
-    (decf (undo-tree-size buffer-undo-tree)
-          (+ (undo-list-byte-size (undo-tree-node-undo node))
-             (undo-list-byte-size (undo-tree-node-redo node))))
 
     ;; discarding root node...
     (if (eq node (undo-tree-root buffer-undo-tree))
@@ -989,7 +987,12 @@ Comparison is done with 'eq."
          ((eq (car (undo-tree-node-next node))
               (undo-tree-current buffer-undo-tree))
          nil)
+        ;; discard root
          (t
+         ;; update undo-tree size
+         (decf (undo-tree-size buffer-undo-tree)
+               (+ (undo-list-byte-size (undo-tree-node-undo node))
+                  (undo-list-byte-size (undo-tree-node-redo node))))
           ;; make child of root into new root
           (setf node (setf (undo-tree-root buffer-undo-tree)
                            (car (undo-tree-node-next node)))
@@ -1007,12 +1010,16 @@ Comparison is done with 'eq."
       (let* ((parent (undo-tree-node-previous node))
              (current (nth (undo-tree-node-branch parent)
                            (undo-tree-node-next parent))))
+       ;; update undo-tree size
+       (decf (undo-tree-size buffer-undo-tree)
+             (+ (undo-list-byte-size (undo-tree-node-undo node))
+                (undo-list-byte-size (undo-tree-node-redo node))))
         (setf (undo-tree-node-next parent)
-              (delq node (undo-tree-node-next parent))
+                (delq node (undo-tree-node-next parent))
               (undo-tree-node-branch parent)
-              (undo-tree-position current (undo-tree-node-next parent)))
+                (undo-tree-position current (undo-tree-node-next parent)))
         ;; if parent has branches, or parent is current node, next node to
-        ;; discard is oldest lead, otherwise it's parent
+        ;; discard is oldest leaf, otherwise it's parent
         (if (or (eq parent (undo-tree-current buffer-undo-tree))
                 (and (undo-tree-node-next parent)
                      (or (not (eq parent (undo-tree-root buffer-undo-tree)))
@@ -1050,7 +1057,7 @@ set by `undo-limit', `undo-strong-limit' and 
`undo-outer-limit'."
 
       ;; if we're still over the `undo-outer-limit', discard entire history
       (when (> (undo-tree-size buffer-undo-tree) undo-outer-limit)
-        ;; query first `undo-ask-before-discard' is set
+        ;; query first if `undo-ask-before-discard' is set
         (if undo-ask-before-discard
             (when (yes-or-no-p
                    (format
@@ -1087,73 +1094,105 @@ which is defined in the `warnings' library.\n")
 
 
 ;;; =====================================================================
-;;;         Utility functions for handling `buffer-undo-list'
+;;;                 Visualizer-related functions
 
-(defun undo-list-pop-changeset ()
-  ;; Pop changeset from `buffer-undo-list'.
-  ;; discard undo boundaries and marker adjustment entries at head of list
-  (while (or (null (car buffer-undo-list))
-            (and (consp (car buffer-undo-list))
-                 (markerp (caar buffer-undo-list))))
-    (setq buffer-undo-list (cdr buffer-undo-list)))
-  ;; pop elements up to next undo boundary
-  (unless (eq (car buffer-undo-list) 'undo-tree-canary)
-    (let* ((changeset (cons (pop buffer-undo-list) nil))
-           (p changeset))
-      (while (car buffer-undo-list)
-        (setcdr p (cons (pop buffer-undo-list) nil))
-       ;; discard marker adjustment entries (see Commentary, above)
-       (if (and (consp (cadr p)) (markerp (car (cadr p))))
-           (setcdr p nil)
-         (setq p (cdr p))))
-      changeset)))
+(defun undo-tree-compute-widths (undo-tree)
+  "Recursively compute widths for all UNDO-TREE's nodes."
+  (let ((stack (list (undo-tree-root undo-tree)))
+        res)
+    (while stack
+      ;; try to compute widths for node at top of stack
+      (if (undo-tree-node-p
+           (setq res (undo-tree-node-compute-widths (car stack))))
+          ;; if computation fails, it returns a node whose widths still need
+          ;; computing, which we push onto the stack
+          (push res stack)
+        ;; otherwise, store widths and remove it from stack
+        (setf (undo-tree-node-lwidth (car stack)) (aref res 0)
+              (undo-tree-node-cwidth (car stack)) (aref res 1)
+              (undo-tree-node-rwidth (car stack)) (aref res 2))
+        (pop stack)))))
 
 
-(defun undo-list-transfer-to-tree ()
-  ;; Transfer entries accumulated in `buffer-undo-list' to `buffer-undo-tree'.
-  (if (null buffer-undo-list)
-      (setq buffer-undo-list '(nil undo-tree-canary))
-    (when (not (eq (cadr buffer-undo-list) 'undo-tree-canary))
-      ;; create new node from first changeset in `buffer-undo-list', save old
-      ;; `buffer-undo-tree' current node, and make new node the current node
-      (let* ((node (make-undo-tree-node nil (undo-list-pop-changeset)))
-             (splice (undo-tree-current buffer-undo-tree))
-             (size (undo-list-byte-size (undo-tree-node-undo node))))
-        (setf (undo-tree-current buffer-undo-tree) node)
-        ;; grow tree fragment backwards using `buffer-undo-list' changesets
-        (while (and buffer-undo-list
-                    (not (eq (cadr buffer-undo-list) 'undo-tree-canary)))
-          (setq node
-                (undo-tree-grow-backwards node (undo-list-pop-changeset)))
-          (incf size (undo-list-byte-size (undo-tree-node-undo node))))
-        ;; if no undo history has been discarded from `buffer-undo-list' since
-        ;; last transfer, splice new tree fragment onto end of old
-        ;; `buffer-undo-tree' current node
-        (if (eq (cadr buffer-undo-list) 'undo-tree-canary)
-            (progn
-              (setf (undo-tree-node-previous node) splice)
-              (push node (undo-tree-node-next splice))
-              (setf (undo-tree-node-branch splice) 0)
-              (incf (undo-tree-size buffer-undo-tree) size))
-          ;; if undo history has been discarded, replace entire
-          ;; `buffer-undo-tree' with new tree fragment
-          (setq node (undo-tree-grow-backwards node nil))
-          (setf (undo-tree-root buffer-undo-tree) node)
-          (setq buffer-undo-list '(nil undo-tree-canary))
-          (setf (undo-tree-size buffer-undo-tree) size)))
-      ;; discard undo history if necessary
-      (undo-tree-discard-history))))
+(defun undo-tree-node-compute-widths (node)
+  ;; Compute NODE's left-, centre-, and right-subtree widths. Returns widths
+  ;; (in a vector) if successful. Otherwise, returns a node whose widths need
+  ;; calculating before NODE's can be calculated.
+  (let ((num-children (length (undo-tree-node-next node)))
+        (lwidth 0) (cwidth 0) (rwidth 0)
+        p w)
+    (catch 'need-widths
+      (cond
+       ;; leaf nodes have 0 width
+       ((= 0 num-children)
+        (setf cwidth 1
+              (undo-tree-node-lwidth node) 0
+              (undo-tree-node-cwidth node) 1
+              (undo-tree-node-rwidth node) 0))
 
+       ;; odd number of children
+       ((= (mod num-children 2) 1)
+        (setq p (undo-tree-node-next node))
+        ;; compute left-width
+        (dotimes (i (/ num-children 2))
+          (if (undo-tree-node-lwidth (car p))
+              (incf lwidth (+ (undo-tree-node-lwidth (car p))
+                              (undo-tree-node-cwidth (car p))
+                              (undo-tree-node-rwidth (car p))))
+            ;; if child's widths haven't been computed, return that child
+            (throw 'need-widths (car p)))
+          (setq p (cdr p)))
+        (if (undo-tree-node-lwidth (car p))
+            (incf lwidth (undo-tree-node-lwidth (car p)))
+          (throw 'need-widths (car p)))
+        ;; centre-width is inherited from middle child
+        (setf cwidth (undo-tree-node-cwidth (car p)))
+        ;; compute right-width
+        (incf rwidth (undo-tree-node-rwidth (car p)))
+        (setq p (cdr p))
+        (dotimes (i (/ num-children 2))
+          (if (undo-tree-node-lwidth (car p))
+              (incf rwidth (+ (undo-tree-node-lwidth (car p))
+                              (undo-tree-node-cwidth (car p))
+                              (undo-tree-node-rwidth (car p))))
+            (throw 'need-widths (car p)))
+          (setq p (cdr p))))
 
-(defun undo-list-byte-size (undo-list)
-  ;; Return size (in bytes) of UNDO-LIST
-  (let ((size 0) (p undo-list))
-    (while p
-      (incf size 8)  ; cons cells use up 8 bytes
-      (when (and (consp (car p)) (stringp (caar p)))
-        (incf size (string-bytes (caar p))))
-      (setq p (cdr p)))
-    size))
+       ;; even number of children
+       (t
+        (setq p (undo-tree-node-next node))
+        ;; compute left-width
+        (dotimes (i (/ num-children 2))
+          (if (undo-tree-node-lwidth (car p))
+              (incf lwidth (+ (undo-tree-node-lwidth (car p))
+                              (undo-tree-node-cwidth (car p))
+                              (undo-tree-node-rwidth (car p))))
+            (throw 'need-widths (car p)))
+          (setq p (cdr p)))
+        ;; centre-width is 0 when number of children is even
+        (setq cwidth 0)
+        ;; compute right-width
+        (dotimes (i (/ num-children 2))
+          (if (undo-tree-node-lwidth (car p))
+              (incf rwidth (+ (undo-tree-node-lwidth (car p))
+                              (undo-tree-node-cwidth (car p))
+                              (undo-tree-node-rwidth (car p))))
+            (throw 'need-widths (car p)))
+          (setq p (cdr p)))))
+
+      ;; return left-, centre- and right-widths
+      (vector lwidth cwidth rwidth))))
+
+
+(defun undo-tree-clear-visualizer-data (undo-tree)
+  ;; Clear visualizer data from UNDO-TREE.
+  (let ((stack (list (undo-tree-root undo-tree)))
+        node)
+    (while stack
+      (setq node (pop stack))
+      (setf (undo-tree-node-visualizer node) nil)
+      (dolist (n (undo-tree-node-next node))
+        (push n stack)))))
 
 
 
@@ -1274,12 +1313,12 @@ Within the undo-tree visualizer, the following keys are 
available:
          ;; pop undo entries that `primitive-undo' has added to
          ;; `buffer-undo-list' and record them in current node's undo record,
          ;; replacing existing entry if one already exists
-        (when (undo-tree-node-undo current)
-         (decf (undo-tree-size buffer-undo-tree)
-               (undo-list-byte-size (undo-tree-node-undo current))))
-       (setf (undo-tree-node-undo current) (undo-list-pop-changeset))
-       (incf (undo-tree-size buffer-undo-tree)
-             (undo-list-byte-size (undo-tree-node-undo current))))))
+         (when (undo-tree-node-undo current)
+           (decf (undo-tree-size buffer-undo-tree)
+                 (undo-list-byte-size (undo-tree-node-undo current))))
+         (setf (undo-tree-node-undo current) (undo-list-pop-changeset))
+         (incf (undo-tree-size buffer-undo-tree)
+               (undo-list-byte-size (undo-tree-node-undo current))))))
 
     ;; inform user if at branch point
     (when (> (undo-tree-num-branches) 1) (message "Undo branch point!"))))
@@ -1292,11 +1331,7 @@ This will affect which branch to descend when *redoing* 
changes
 using `undo-tree-redo'."
   (interactive (list (or (and prefix-arg (prefix-numeric-value prefix-arg))
                          (and (not (eq buffer-undo-list t))
-                              (or buffer-undo-tree
-                                  (progn
-                                    (setq buffer-undo-tree (make-undo-tree))
-                                    (undo-list-transfer-to-tree)
-                                    t))
+                             (or (undo-list-transfer-to-tree) t)
                               (> (undo-tree-num-branches) 1)
                               (read-number
                                (format "Branch (0-%d): "
@@ -1307,12 +1342,7 @@ using `undo-tree-redo'."
   (when (<= (undo-tree-num-branches) 1) (error "Not at undo branch point"))
   (when (or (< branch 0) (> branch (1- (undo-tree-num-branches))))
     (error "Invalid branch number"))
-
-  ;; if `buffer-undo-tree' is empty, create initial undo-tree
-  (when (null buffer-undo-tree)
-    (setq buffer-undo-tree (make-undo-tree)))
-  ;; transfer entries accumulated in `buffer-undo-list' to
-  ;; `buffer-undo-tree'
+  ;; transfer entries accumulated in `buffer-undo-list' to `buffer-undo-tree'
   (undo-list-transfer-to-tree)
   ;; switch branch
   (setf (undo-tree-node-branch (undo-tree-current buffer-undo-tree))
@@ -1357,9 +1387,6 @@ Argument is a character, naming the register."
   (interactive "cUndo-tree state to register: ")
   ;; throw error if undo is disabled in buffer
   (when (eq buffer-undo-list t) (error "No undo information in this buffer"))
-  ;; if `buffer-undo-tree' is empty, create initial undo-tree
-  (when (null buffer-undo-tree)
-    (setq buffer-undo-tree (make-undo-tree)))
   ;; transfer entries accumulated in `buffer-undo-list' to `buffer-undo-tree'
   (undo-list-transfer-to-tree)
   ;; save current node to REGISTER
@@ -1380,9 +1407,6 @@ Argument is a character, naming the register."
       (error "No undo information in this buffer"))
      ((not (undo-tree-node-p node))
       (error "Register doesn't contain undo-tree state")))
-    ;; if `buffer-undo-tree' is empty, create initial undo-tree
-    (when (null buffer-undo-tree)
-      (setq buffer-undo-tree (make-undo-tree)))
     ;; transfer entries accumulated in `buffer-undo-list' to `buffer-undo-tree'
     (undo-list-transfer-to-tree)
     ;; restore buffer state corresponding to saved node
@@ -1399,9 +1423,6 @@ Argument is a character, naming the register."
   (interactive)
   ;; throw error if undo is disabled in buffer
   (when (eq buffer-undo-list t) (error "No undo information in this buffer"))
-  ;; if `buffer-undo-tree' is empty, create initial undo-tree
-  (when (null buffer-undo-tree)
-    (setq buffer-undo-tree (make-undo-tree)))
   ;; transfer entries accumulated in `buffer-undo-list' to `buffer-undo-tree'
   (undo-list-transfer-to-tree)
   ;; add hook to kill visualizer buffer if original buffer is changed