[elpa] externals/vundo ed0d7d42d8 38/58: Replace lists with vectors for the main vundo-m lists

[ELPA Syncer]

branch: externals/vundo
commit ed0d7d42d8e620d4439932defe2295a6dca9b19a
Author: Campbell Barton <ideasman42@gmail.com>
Commit: Yuan Fu <casouri@gmail.com>

    Replace lists with vectors for the main vundo-m lists
    
    Prefer vectors as they can perform direct lookups without having to
    iterate over all items.
    
    * test/vundo-test.el (vundo-test--mod-list, vundo-test--last-idx,
    vundo-test--2): Replace nth/car with aref.
    * vundo.el (vundo--mod-list-from): Replace list with vector.
    (vundo--update-mapping, vundo--build-tree, vundo--draw-tree,
    vundo--mod-list-trim, vundo--current-node, vundo--latest-buffer-state,
    vundo--move-to-node): Replace nth/car with aref.
---
 test/vundo-test.el | 14 +++++++-------
 vundo.el           | 53 ++++++++++++++++++++++++++++-------------------------
 2 files changed, 35 insertions(+), 32 deletions(-)

diff --git a/test/vundo-test.el b/test/vundo-test.el
index d45323c7e1..ef97ebc9fe 100644
--- a/test/vundo-test.el
+++ b/test/vundo-test.el
@@ -26,11 +26,11 @@
                    (list nil ul3 ul6 ul9)))
 
     (let ((ht6 (vundo--update-mapping ml6 nil 0)))
-      (should (eq (gethash ul3 ht6) (nth 1 ml6)))
-      (should (eq (gethash ul6 ht6) (nth 2 ml6)))
+      (should (eq (gethash ul3 ht6) (aref ml6 1)))
+      (should (eq (gethash ul6 ht6) (aref ml6 2)))
 
       (let ((ht9 (vundo--update-mapping ml9 ht6 3)))
-        (should (eq (gethash ul9 ht9) (nth 3 ml9))))
+        (should (eq (gethash ul9 ht9) (aref ml9 3))))
 
       (should (equal (mapcar #'vundo-m-idx ml9)
                      '(0 1 2 3))))))
@@ -65,7 +65,7 @@
 
 (defsubst vundo-test--last-idx ()
   "(vundo-m-idx (car (last vundo--prev-mod-list)))."
-  (vundo-m-idx (car (last vundo--prev-mod-list))))
+  (vundo-m-idx (aref vundo--prev-mod-list (1- (length vundo--prev-mod-list)))))
 
 (defmacro vundo-test--setup (&rest body)
   "Setup and evaluate BODY."
@@ -166,19 +166,19 @@ Sans ending newline."
      (vundo-forward 1)
      (vundo-next 1)
      (should (eq (vundo--get-node-at-point)
-                 (nth 51 vundo--prev-mod-list)))
+                 (aref vundo--prev-mod-list 51)))
 
      (dotimes (_ 20)
        (vundo-previous 1)
        (vundo-next 1))
      (should (eq (vundo--get-node-at-point)
-                 (nth 51 vundo--prev-mod-list)))
+                 (aref vundo--prev-mod-list 51)))
 
      (dotimes (_ 20)
        (vundo-forward 49)
        (vundo-backward 49))
      (should (eq (vundo--get-node-at-point)
-                 (nth 51 vundo--prev-mod-list))))))
+                 (aref vundo--prev-mod-list 51))))))
 
 (ert-deftest vundo-test--3 ()
   "This tests regional undos."
diff --git a/vundo.el b/vundo.el
index c50780dc4e..27c63dbe0f 100644
--- a/vundo.el
+++ b/vundo.el
@@ -39,7 +39,7 @@
 ;;
 ;; `vundo' calls `vundo--refresh-buffer' to setup the tree structure
 ;; and draw it in the buffer. We have two data structures:
-;; `vundo--prev-mod-list' which stores a list of `vundo-m'. This list
+;; `vundo--prev-mod-list' which stores a vector of `vundo-m'. This vector
 ;; is generated from `buffer-undo-list' by `vundo--mod-list-from'. We
 ;; also have a hash table `vundo--prev-mod-hash' generated by
 ;; `vundo--update-mapping', which maps undo-lists back to the
@@ -241,7 +241,7 @@ of UNDO-LIST is not nil."
 If N non-nil, only look at the first N entries in UNDO-LIST.
 If MOD-LIST non-nil, extend on MOD-LIST."
   (let ((uidx 0)
-        (mod-list (or mod-list (list (make-vundo-m))))
+        (mod-list (or mod-list (vector (make-vundo-m))))
         new-mlist)
     (while (and undo-list (or (null n) (< uidx n)))
       ;; Skip leading nils.
@@ -263,7 +263,8 @@ If MOD-LIST non-nil, extend on MOD-LIST."
         (while (car undo-list)
           (setq undo-list (cdr undo-list))
           (cl-incf uidx))))
-    (append mod-list new-mlist)))
+    ;; Convert to vector.
+    (vconcat mod-list new-mlist)))
 
 (defun vundo--update-mapping (mod-list &optional hash-table n)
   "Update each modification in MOD-LIST.
@@ -272,8 +273,8 @@ modification in HASH-TABLE. If N non-nil, start from the Nth
 modification in MOD-LIST. Return HASH-TABLE."
   (let ((hash-table (or hash-table
                         (make-hash-table :test #'eq :weakness t))))
-    (cl-loop for mod in (nthcdr (or n 0) mod-list)
-             for midx = (or n 0) then (1+ midx)
+    (cl-loop for midx from (or n 0) to (1- (length mod-list))
+             for mod = (aref mod-list midx)
              do (cl-assert (null (vundo-m-idx mod)))
              do (cl-assert (null (gethash (vundo-m-undo-list mod)
                                           hash-table)))
@@ -346,7 +347,7 @@ MOD-HASH maps undo-lists to modifications.
 If FROM non-nil, build from FORM-th modification in MOD-LIST."
   (cl-loop
    for m from (or from 0) to (1- (length mod-list))
-   for mod = (nth m mod-list)
+   for mod = (aref mod-list m)
    ;; If MOD is an undo, the buffer state it represents is equivalent
    ;; to a previous one.
    do (let ((prev-undo (undo--last-change-was-undo-p
@@ -363,7 +364,7 @@ If FROM non-nil, build from FORM-th modification in 
MOD-LIST."
            (let ((prev-m (gethash prev-undo mod-hash)))
              (vundo--eqv-merge-mod prev-m mod)))
           ;; This undo undoes to root, merge with the root node.
-          ('t (vundo--eqv-merge-mod (nth 0 mod-list) mod))
+          ('t (vundo--eqv-merge-mod (aref mod-list 0) mod))
           ;; This modification either is a region-undo, nil undo, or
           ;; not an undo. We treat them the same.
           ((or 'undo-in-region 'empty _)
@@ -371,7 +372,7 @@ If FROM non-nil, build from FORM-th modification in 
MOD-LIST."
            ;; we connect M-1 with M, where M-1 is the parent and M is
            ;; the child.
            (unless (eq m 0)
-             (let* ((m-1 (nth (1- m) mod-list))
+             (let* ((m-1 (aref mod-list (1- m)))
                     ;; TODO: may need to optimize.
                     (min-eqv-mod (car (vundo--eqv-list-of m-1))))
                (setf (vundo-m-parent mod) min-eqv-mod)
@@ -445,7 +446,7 @@ Translate according to ‘vundo-glyph-alist’."
 
 (defun vundo--draw-tree (mod-list)
   "Draw the tree in MOD-LIST in current buffer."
-  (let* ((root (nth 0 mod-list))
+  (let* ((root (aref mod-list 0))
          (node-queue (list root))
          (inhibit-read-only t))
     (erase-buffer)
@@ -567,14 +568,15 @@ WINDOW is the window that was/is displaying the vundo 
buffer."
 (defun vundo--mod-list-trim (mod-list n)
   "Remove MODS from MOD-LIST.
 Keep the first N modifications."
-  (dolist (mod (nthcdr (1+ n) mod-list))
-    (let ((parent (vundo-m-parent mod))
-          (eqv-list (vundo--eqv-list-of mod)))
-      (when parent
-        (setf (vundo-m-children parent)
-              (remove mod (vundo-m-children parent))))
-      (when eqv-list
-        (vundo--eqv-merge (remove mod eqv-list)))))
+  (cl-loop for midx from (1+ n) to (1- (length mod-list))
+           for mod = (aref mod-list midx)
+           do (let ((parent (vundo-m-parent mod))
+                    (eqv-list (vundo--eqv-list-of mod)))
+                (when parent
+                  (setf (vundo-m-children parent)
+                        (remove mod (vundo-m-children parent))))
+                (when eqv-list
+                  (vundo--eqv-merge (remove mod eqv-list)))))
   (seq-subseq mod-list 0 (1+ n)))
 
 (defun vundo--refresh-buffer
@@ -647,7 +649,7 @@ This function modifies ‘vundo--prev-mod-list’,
 
 (defun vundo--current-node (mod-list)
   "Return the currently highlighted node in MOD-LIST."
-  (car (vundo--eqv-list-of (car (last mod-list)))))
+  (car (vundo--eqv-list-of (aref mod-list (1- (length mod-list))))))
 
 (defun vundo--highlight-node (node)
   "Highlight NODE as current node."
@@ -798,8 +800,9 @@ If UNDO-LIST is nil, return nil."
 (defun vundo--latest-buffer-state (mod-list)
   "Return the node representing the latest buffer state.
 Basically, return the latest non-undo modification in MOD-LIST."
-  (let ((max-node (car mod-list)))
-    (cl-loop for mod in (cdr mod-list)
+  (let ((max-node (aref mod-list 0)))
+    (cl-loop for midx from 1 to (1- (length mod-list))
+             for mod = (aref mod-list midx)
              do (if (and (null (vundo-m-prev-eqv mod))
                          (> (vundo-m-idx mod)
                             (vundo-m-idx max-node)))
@@ -821,10 +824,10 @@ This function modifies the content of ORIG-BUFFER and its
              (dest-idx (car (last route)))
              ;; The complete undo-list that stops at SOURCE.
              (undo-list-at-source
-              (vundo-m-undo-list (nth source-idx mod-list)))
+              (vundo-m-undo-list (aref mod-list source-idx)))
              ;; The complete undo-list that stops at DEST.
              (undo-list-at-dest
-              (vundo-m-undo-list (nth dest-idx mod-list)))
+              (vundo-m-undo-list (aref mod-list dest-idx)))
              ;; We will undo these modifications.
              (planned-undo (vundo--list-subtract
                             undo-list-at-source undo-list-at-dest))
@@ -853,7 +856,7 @@ This function modifies the content of ORIG-BUFFER and its
                (cl-assert (not (and (consp buffer-undo-list)
                                     (null (car buffer-undo-list)))))
                (let ((undo-list-at-stop
-                      (vundo-m-undo-list (nth stop mod-list))))
+                      (vundo-m-undo-list (aref mod-list stop))))
                  (puthash buffer-undo-list (or undo-list-at-stop t)
                           undo-equiv-table))
                (push nil buffer-undo-list))))
@@ -879,9 +882,9 @@ This function modifies the content of ORIG-BUFFER and its
           (when vundo--message
             (message "%s -> %s Trim to: %s Steps: %s Undo-list len: %s"
                      (mapcar #'vundo-m-idx (vundo--eqv-list-of
-                                            (nth source-idx mod-list)))
+                                            (aref mod-list source-idx)))
                      (mapcar #'vundo-m-idx (vundo--eqv-list-of
-                                            (nth dest-idx mod-list)))
+                                            (aref mod-list dest-idx)))
                      trimmed
                      (length planned-undo)
                      (length buffer-undo-list)))