[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[elpa] externals/undotree 9b14800 018/195: Rewrote undotreecomputewi
From: 
Stefan Monnier 
Subject: 
[elpa] externals/undotree 9b14800 018/195: Rewrote undotreecomputewidths and undotreeclearvisualizerdata 
Date: 
Sat, 28 Nov 2020 13:41:12 0500 (EST) 
branch: externals/undotree
commit 9b14800378d9aa3ff6f76d90ed7983a87c2204d1
Author: tsc25 <tsc25@cantab.net>
Commit: tsc25 <tsc25@cantab.net>
Rewrote undotreecomputewidths and undotreeclearvisualizerdata
to use a stack rather than recursion, to avoid hitting recursion depth
limits
on large undo trees.
Locally increase maxlispevaldepth maxspecpdlsize when calling
undotreedrawsubtree, also to avoid hitting recursion depth limits on
large
undo trees.

undotree.el  178 ++++++++++++++++++++++++++++++++++++
1 file changed, 110 insertions(+), 68 deletions()
diff git a/undotree.el b/undotree.el
index 6e95df5..a15c28c 100644
 a/undotree.el
+++ b/undotree.el
@@ 550,6 +550,7 @@ in visualizer.")
root current)
+
(defstruct
(undotreenode
(:type vector) ; create unnamed struct
@@ 568,6 +569,11 @@ in visualizer.")
(:copier nil))
previous next undo redo timestamp branch visualizer)
+(defmacro undotreenodep (n)
+ (let ((len (length (makeundotreenode nil nil))))
+ `(and (vectorp ,n) (= (length ,n) ,len))))
+
+
(defstruct
(undotreevisualizerdata
@@ 656,80 +662,106 @@ part of `bufferundotree'."
(defun undotreecomputewidths (undotree)
"Recursively compute widths for all UNDOTREE's nodes."
 (undotreenodecomputewidths (undotreeroot undotree)))
+ (let ((stack (list (undotreeroot undotree)))
+ res)
+ (while stack
+ ;; try to compute widths for node at top of stack
+ (if (undotreenodep
+ (setq res (undotreenodecomputewidths (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 (undotreenodelwidth (car stack)) (aref res 0)
+ (undotreenodecwidth (car stack)) (aref res 1)
+ (undotreenoderwidth (car stack)) (aref res 2))
+ (pop stack)))))
(defun undotreenodecomputewidths (node)
 "Compute NODE's left and rightsubtree widths."
+ ;; Compute NODE's left, centre, and rightsubtree widths. Returns widths
+ ;; (in a vector) if successful. Otherwise, returns a node whose widths need
+ ;; calculating before NODE's can be calculated.
(let ((numchildren (length (undotreenodenext node)))
(lwidth 0) (cwidth 0) (rwidth 0)
p w)
 (cond
 ;; leaf nodes have 0 width
 ((= 0 numchildren)
 (setf cwidth 1
 (undotreenodelwidth node) 0
 (undotreenodecwidth node) 1
 (undotreenoderwidth node) 0))

 ;; odd number of children
 ((= (mod numchildren 2) 1)
 (setq p (undotreenodenext node))
 ;; compute leftwidth
 (dotimes (i (/ numchildren 2))
 (setq w (undotreenodecomputewidths (car p)))
 (setq lwidth (+ lwidth (aref w 0) (aref w 1) (aref w 2)))
 (setq p (cdr p)))
 (setq w (undotreenodecomputewidths (car p))
 lwidth (+ lwidth (aref w 0)))
 (setf (undotreenodelwidth node) lwidth)
 ;; centrewidth is inherited from middle child
 (setf cwidth (undotreenodecwidth (car p))
 (undotreenodecwidth node) cwidth)
 ;; compute rightwidth
 (setq rwidth (+ rwidth (aref w 2)))
 (setq p (cdr p))
 (dotimes (i (/ numchildren 2))
 (setq w (undotreenodecomputewidths (car p)))
 (setq rwidth (+ rwidth (aref w 0) (aref w 1) (aref w 2)))
 (setq p (cdr p)))
 (setf (undotreenoderwidth node) rwidth))

 ;; even number of children
 (t
 (setq p (undotreenodenext node))
 ;; compute leftwidth
 (dotimes (i (/ numchildren 2))
 (setq w (undotreenodecomputewidths (car p)))
 (setq lwidth (+ lwidth (aref w 0) (aref w 1) (aref w 2)))
 (setq p (cdr p)))
 (setf (undotreenodelwidth node) lwidth)
 ;; compute rightwidth
 (dotimes (i (/ numchildren 2))
 (setq w (undotreenodecomputewidths (car p)))
 (setq rwidth (+ rwidth (aref w 0) (aref w 1) (aref w 2)))
 (setq p (cdr p)))
 (setf (undotreenoderwidth node) rwidth)
 ;; centrewidth is 0 when number of children is even
 (setf cwidth 0
 (undotreenodecwidth node) 0)))

 ;; return left, centre and rightwidths
 (vector lwidth cwidth rwidth)))
+ (catch 'needwidths
+ (cond
+ ;; leaf nodes have 0 width
+ ((= 0 numchildren)
+ (setf cwidth 1
+ (undotreenodelwidth node) 0
+ (undotreenodecwidth node) 1
+ (undotreenoderwidth node) 0))
+
+ ;; odd number of children
+ ((= (mod numchildren 2) 1)
+ (setq p (undotreenodenext node))
+ ;; compute leftwidth
+ (dotimes (i (/ numchildren 2))
+ (if (undotreenodelwidth (car p))
+ (setq lwidth (+ lwidth
+ (undotreenodelwidth (car p))
+ (undotreenodecwidth (car p))
+ (undotreenoderwidth (car p))))
+ ;; if child's widths haven't been computed, return that child
+ (throw 'needwidths (car p)))
+ (setq p (cdr p)))
+ (if (undotreenodelwidth (car p))
+ (setq lwidth (+ lwidth (undotreenodelwidth (car p))))
+ (throw 'needwidths (car p)))
+ ;; centrewidth is inherited from middle child
+ (setf cwidth (undotreenodecwidth (car p)))
+ ;; compute rightwidth
+ (setq rwidth (+ rwidth (undotreenoderwidth (car p))))
+ (setq p (cdr p))
+ (dotimes (i (/ numchildren 2))
+ (if (undotreenodelwidth (car p))
+ (setq rwidth (+ rwidth
+ (undotreenodelwidth (car p))
+ (undotreenodecwidth (car p))
+ (undotreenoderwidth (car p))))
+ (throw 'needwidths (car p)))
+ (setq p (cdr p))))
+
+ ;; even number of children
+ (t
+ (setq p (undotreenodenext node))
+ ;; compute leftwidth
+ (dotimes (i (/ numchildren 2))
+ (if (undotreenodelwidth (car p))
+ (setq lwidth (+ lwidth
+ (undotreenodelwidth (car p))
+ (undotreenodecwidth (car p))
+ (undotreenoderwidth (car p))))
+ (throw 'needwidths (car p)))
+ (setq p (cdr p)))
+ ;; centrewidth is 0 when number of children is even
+ (setq cwidth 0)
+ ;; compute rightwidth
+ (dotimes (i (/ numchildren 2))
+ (if (undotreenodelwidth (car p))
+ (setq rwidth (+ rwidth
+ (undotreenodelwidth (car p))
+ (undotreenodecwidth (car p))
+ (undotreenoderwidth (car p))))
+ (throw 'needwidths (car p)))
+ (setq p (cdr p)))))
+
+ ;; return left, centre and rightwidths
+ (vector lwidth cwidth rwidth))))
(defun undotreeclearvisualizerdata (undotree)
;; Clear visualizer data from UNDOTREE.
 (undotreenodeclearvisualizerdata (undotreeroot undotree)))


(defun undotreenodeclearvisualizerdata (node)
 ;; Recursively clear visualizer data from NODE and descendents.
 (setf (undotreenodevisualizer node) nil)
 (dolist (n (undotreenodenext node))
 (undotreenodeclearvisualizerdata n)))

+ (let ((stack (list (undotreeroot undotree)))
+ node)
+ (while stack
+ (setq node (pop stack))
+ (setf (undotreenodevisualizer node) nil)
+ (dolist (n (undotreenodenext node))
+ (push n stack)))))
(defun undotreeposition (node list)
@@ 955,10 +987,14 @@ using `undotreeredo'."
(+ (undotreenodecharlwidth (undotreeroot undotree))
2))) ; left margin
;; draw undotree
 (let ((undotreeinsertface 'undotreevisualizerdefaultface))
+ (let ((undotreeinsertface 'undotreevisualizerdefaultface)
+ (maxlispevaldepth 1000000)
+ (maxspecpdlsize 1000000))
(saveexcursion (undotreedrawsubtree (undotreeroot undotree))))
;; highlight active branch
 (let ((undotreeinsertface 'undotreevisualizeractivebranchface))
+ (let ((undotreeinsertface 'undotreevisualizeractivebranchface)
+ (maxlispevaldepth 1000000)
+ (maxspecpdlsize 1000000))
(undotreedrawsubtree (undotreeroot undotree) 'active))
;; highlight current node
(gotochar (undotreenodemarker (undotreecurrent undotree)))
@@ 1182,7 +1218,9 @@ using `undotreeredo' or `undotreevisualizerredo'."
;; unhighlight old active branch below current node
(setq bufferreadonly nil)
(gotochar (undotreenodemarker (undotreecurrent bufferundotree)))
 (let ((undotreeinsertface 'undotreevisualizerdefaultface))
+ (let ((undotreeinsertface 'undotreevisualizerdefaultface)
+ (maxlispevaldepth 1000000)
+ (maxspecpdlsize 1000000))
(saveexcursion
(undotreedrawsubtree (undotreecurrent bufferundotree) 'active)))
;; increment branch
@@ 1194,7 +1232,9 @@ using `undotreeredo' or `undotreevisualizerredo'."
((<= (+ branch arg) 0) 0)
(t (+ branch arg))))
;; highlight new active branch below current node
 (let ((undotreeinsertface 'undotreevisualizeractivebranchface))
+ (let ((undotreeinsertface 'undotreevisualizeractivebranchface)
+ (maxlispevaldepth 1000000)
+ (maxspecpdlsize 1000000))
(saveexcursion
(undotreedrawsubtree (undotreecurrent bufferundotree) 'active)))
;; rehighlight current node
@@ 1230,7 +1270,9 @@ at POS."
(undotreeset node)
(setbuffer " *undotree*")
(setq bufferreadonly nil)
 (undotreedrawtree bufferundotree)
+ (let ((maxlispevaldepth 1000000)
+ (maxspecpdlsize 1000000))
+ (undotreedrawtree bufferundotree))
(setq bufferreadonly t))))
 [elpa] branch externals/undotree created (now bf2e9ba), Stefan Monnier, 2020/11/28
 [elpa] externals/undotree eae16c8 009/195: Implemented visualizer majormode and commands., Stefan Monnier, 2020/11/28
 [elpa] externals/undotree a46761a 022/195: Added "canary" to detect and deal with undo history being discarded, Stefan Monnier, 2020/11/28
 [elpa] externals/undotree 2fa1824 021/195: Implemented display of timestamps in visualizer., Stefan Monnier, 2020/11/28
 [elpa] externals/undotree 2c18d4a 010/195: Implemented active branch highlighting in visualizer., Stefan Monnier, 2020/11/28
 [elpa] externals/undotree 9b14800 018/195: Rewrote undotreecomputewidths and undotreeclearvisualizerdata,
Stefan Monnier <=
 [elpa] externals/undotree aa550da 025/195: Implemented undo history discarding so as to remain within memory usage limits, Stefan Monnier, 2020/11/28
 [elpa] externals/undotree ad38c6a 020/195: Reuse node markers in undotreedrawtree and undotreedrawsubtree,, Stefan Monnier, 2020/11/28
 [elpa] externals/undotree 486964c 014/195: Centre undotree in visualizer., Stefan Monnier, 2020/11/28
 [elpa] externals/undotree ff2fd6e 011/195: Implemented undotreemode minor mode., Stefan Monnier, 2020/11/28
 [elpa] externals/undotree 30dc485 013/195: Clear visualizer data when quitting visualizer., Stefan Monnier, 2020/11/28
 [elpa] externals/undotree e0b8308 015/195: Implemented commands to set buffer state to any given undotree node., Stefan Monnier, 2020/11/28
 [elpa] externals/undotree 0368f0f 006/195: Implemented undotree visualisation., Stefan Monnier, 2020/11/28
 [elpa] externals/undotree 711dd60 003/195: Implemented undotree data structure and undo command., Stefan Monnier, 2020/11/28
 [elpa] externals/undotree b15904c 023/195: Update timestamps when nodes are visited by undo/redo., Stefan Monnier, 2020/11/28
 [elpa] externals/undotree 21d3c89 004/195: Implemented redo command., Stefan Monnier, 2020/11/28