branch: externals/phpinspect
commit 0596bc52bf91104d7520a7d99991da0633369790
Author: Hugo Thunnissen <de...@hugot.nl>
Commit: Hugo Thunnissen <de...@hugot.nl>
Optimize splay tree and use it to store token's children
---
benchmarks/parse-file.el | 2 +-
benchmarks/splay-tree.el | 33 +++
phpinspect-bmap.el | 181 ++++-----------
phpinspect-eldoc.el | 44 ++--
phpinspect-meta.el | 130 +++++++++++
phpinspect-resolvecontext.el | 38 ++--
phpinspect-splayt.el | 517 ++++++++++++++++++++++++++-----------------
test/test-bmap.el | 3 +
test/test-splayt.el | 78 +++++--
9 files changed, 623 insertions(+), 403 deletions(-)
diff --git a/benchmarks/parse-file.el b/benchmarks/parse-file.el
index c2f05b2b25..604ba2e833 100644
--- a/benchmarks/parse-file.el
+++ b/benchmarks/parse-file.el
@@ -62,7 +62,7 @@
(garbage-collect)
- ;;(profiler-start 'cpu+mem)
+ ;;(profiler-start 'cpu)
(message "Incremental parse after 2 more edits:")
(phpinspect-with-parse-context (phpinspect-make-pctx :incremental t
:previous-bmap bmap-after :edtrack edtrack)
(benchmark 1 '(phpinspect-parse-current-buffer)))
diff --git a/benchmarks/splay-tree.el b/benchmarks/splay-tree.el
new file mode 100644
index 0000000000..261ddfe08a
--- /dev/null
+++ b/benchmarks/splay-tree.el
@@ -0,0 +1,33 @@
+
+
+(require 'phpinspect-splayt)
+
+(let ((here (file-name-directory (or load-file-name buffer-file-name)))
+ (tree (phpinspect-make-splayt)))
+ (message "Splay tree 10000 insertions:")
+ (garbage-collect)
+ (benchmark
+ 1 '(dotimes (i 10000)
+ (phpinspect-splayt-insert tree i 'value)))
+
+ (message "Splay tree 10000 lookups:")
+ (garbage-collect)
+ (benchmark
+ 1 '(dotimes (i 10000)
+ (phpinspect-splayt-find tree i))))
+
+
+(let (map)
+ (message "Hashtable 10000 insertions:")
+ (garbage-collect)
+ (benchmark
+ 1 '(progn
+ (setq map (make-hash-table :test #'eq :size 10000 :rehash-size 1.5))
+ (dotimes (i 10000)
+ (puthash i 'value map))))
+
+ (message "Hashtable 10000 lookups:")
+ (garbage-collect)
+ (benchmark
+ 1 '(dotimes (i 10000)
+ (gethash i map))))
diff --git a/phpinspect-bmap.el b/phpinspect-bmap.el
index 3519ac66a7..2b0221128f 100644
--- a/phpinspect-bmap.el
+++ b/phpinspect-bmap.el
@@ -24,6 +24,7 @@
;;; Code:
(require 'phpinspect-splayt)
+(require 'phpinspect-meta)
(cl-defstruct (phpinspect-bmap (:constructor phpinspect-make-bmap))
(starts (make-hash-table :test #'eql
@@ -71,77 +72,26 @@
(and (<= (phpinspect-region-start reg1) (phpinspect-region-start reg2))
(>= (phpinspect-region-end reg1) (phpinspect-region-end reg2))))
-(defsubst phpinspect-make-meta (parent start end whitespace-before token
&optional overlay right-siblings)
- (list 'meta parent start end whitespace-before token overlay right-siblings))
+(define-inline phpinspect-overlay-bmap (overlay)
+ (inline-quote (car (nthcdr 4 ,overlay))))
-(defsubst phpinspect-meta-parent (meta)
- (cadr meta))
+(define-inline phpinspect-overlay-delta (overlay)
+ (inline-quote (cadddr ,overlay)))
-(gv-define-setter phpinspect-meta-end (end meta) `(setcar (cdddr ,meta) ,end))
-(gv-define-setter phpinspect-meta-start (start meta) `(setcar (cddr ,meta)
,start))
-(gv-define-setter phpinspect-meta-overlay (overlay meta) `(setcar (nthcdr 6
,meta) ,overlay))
-(gv-define-setter phpinspect-meta-parent (parent meta) `(setcar (cdr ,meta)
,parent))
-(gv-define-setter phpinspect-meta-right-siblings (siblings meta) `(setcar
(nthcdr 7 ,meta) ,siblings))
+(define-inline phpinspect-overlay-start (overlay)
+ (inline-quote (cadr ,overlay)))
-(defsubst phpinspect-meta-right-siblings (meta)
- (car (nthcdr 7 meta)))
+(define-inline phpinspect-overlay-end (overlay)
+ (inline-quote (caddr ,overlay)))
-(defsubst phpinspect-meta-overlay (meta)
- (car (nthcdr 6 meta)))
+(define-inline phpinspect-overlay-token-meta (overlay)
+ (inline-quote (car (nthcdr 5 ,overlay))))
-(defsubst phpinspect-meta-token (meta)
- (car (nthcdr 5 meta)))
-
-(defsubst phpinspect-meta-end (meta)
- (cadddr meta))
-
-(defsubst phpinspect-meta-whitespace-before (meta)
- (car (cddddr meta)))
-
-(defsubst phpinspect-meta-width (meta)
- (- (phpinspect-meta-end meta) (phpinspect-meta-start meta)))
-
-(defun phpinspect-meta-sort-width (meta1 meta2)
- (< (phpinspect-meta-width meta1) (phpinspect-meta-width meta2)))
-
-(defsubst phpinspect-meta-start (meta)
- (caddr meta))
-
-(defsubst phpinspect-meta-overlaps-point (meta point)
- (and (> (phpinspect-meta-end meta) point)
- (<= (phpinspect-meta-start meta) point)))
-
-(defsubst phpinspect-meta-find-parent-matching-token (meta predicate)
- (if (funcall predicate (phpinspect-meta-token meta))
- meta
- (catch 'found
- (while (phpinspect-meta-parent meta)
- (setq meta (phpinspect-meta-parent meta))
- (when (funcall predicate (phpinspect-meta-token meta))
- (throw 'found meta))))))
-
-(gv-define-setter phpinspect-overlay-end (end overlay) `(setcar (cddr
,overlay) ,end))
-(gv-define-setter phpinspect-overlay-start (start overlay) `(setcar (cdr
,overlay) ,start))
-(gv-define-setter phpinspect-overlay-delta (delta overlay) `(setcar (cdddr
,overlay) ,delta))
-
-(defsubst phpinspect-overlay-bmap (overlay)
- (car (nthcdr 4 overlay)))
-
-(defsubst phpinspect-overlay-delta (overlay)
- (cadddr overlay))
-
-(defsubst phpinspect-overlay-start (overlay)
- (cadr overlay))
-
-(defsubst phpinspect-overlay-end (overlay)
- (caddr overlay))
-
-(defsubst phpinspect-overlay-token-meta (overlay)
- (car (nthcdr 5 overlay)))
-
-(defsubst phpinspect-overlay-overlaps-point (overlay point)
- (and (> (phpinspect-overlay-end overlay) point)
- (<= (phpinspect-overlay-start overlay) point)))
+(define-inline phpinspect-overlay-overlaps-point (overlay point)
+ (inline-letevals (overlay point)
+ (inline-quote
+ (and (> (phpinspect-overlay-end ,overlay) ,point)
+ (<= (phpinspect-overlay-start ,overlay) ,point)))))
(defmacro phpinspect-bmap-iterate-region (region place-and-bmap &rest body)
(declare (indent defun))
@@ -170,27 +120,13 @@
(_ignored (gensym))
(overlay-start (gensym))
(overlay-end (gensym)))
- `(let ((,bmap-stack (list ,(cadr place-and-bmap)))
- (,bmap))
- (while (setq ,bmap (pop ,bmap-stack))
- (if (phpinspect-overlay-p ,bmap)
- (let ((,overlay-start (phpinspect-overlay-start ,bmap))
- (,overlay-end (phpinspect-overlay-end ,bmap)))
- (maphash (lambda (,_ignored ,place)
- (setq ,place (phpinspect-overlay-wrap-meta ,bmap
,place))
- (when (and (<= ,overlay-start
- (phpinspect-meta-start ,place))
- (>= ,overlay-end
- (phpinspect-meta-end ,place)))
- (if (phpinspect-meta-overlay ,place)
- (push (phpinspect-meta-overlay ,place)
,bmap-stack)
- ,@body)))
- (phpinspect-bmap-meta (phpinspect-overlay-bmap
,bmap))))
- (maphash (lambda (,_ignored ,place)
- (if (phpinspect-meta-overlay ,place)
- (push (phpinspect-meta-overlay ,place) ,bmap-stack)
- ,@body))
- (phpinspect-bmap-meta ,bmap)))))))
+ `(let ((,bmap ,(cadr place-and-bmap)))
+ (maphash (lambda (,_ignored ,place)
+ ,@body
+ (when (phpinspect-meta-overlay ,place)
+ (phpinspect-splayt-traverse (,place
(phpinspect-meta-children ,place))
+ ,@body)))
+ (phpinspect-bmap-meta ,bmap)))))
(defsubst phpinspect-bmap-register (bmap start end token &optional
whitespace-before overlay)
(let* ((starts (phpinspect-bmap-starts bmap))
@@ -198,7 +134,7 @@
(meta (phpinspect-bmap-meta bmap))
(last-token-start (phpinspect-bmap-last-token-start bmap))
(existing-end (gethash end ends))
- (token-meta (phpinspect-make-meta nil start end whitespace-before
token overlay)))
+ (token-meta (or overlay (phpinspect-make-meta nil start end
whitespace-before token overlay))))
(unless whitespace-before
(setq whitespace-before ""))
@@ -219,22 +155,9 @@
(while (and (car stack) (>= (phpinspect-meta-start (car stack))
start))
(setq child (pop stack))
- (setf (phpinspect-meta-parent child) token-meta)
- (when (phpinspect-meta-overlay child)
- (setf (phpinspect-meta-parent
- (phpinspect-overlay-token-meta
- (phpinspect-meta-overlay child)))
- token-meta))
-
- (setf (phpinspect-meta-right-siblings child) right-siblings)
- (when (phpinspect-meta-overlay child)
- (setf (phpinspect-meta-right-siblings
- (phpinspect-overlay-token-meta
- (phpinspect-meta-overlay child)))
- right-siblings))
- (push (phpinspect-meta-token child) right-siblings))
-
- (setf (phpinspect-bmap-token-stack bmap) stack)))
+ (phpinspect-meta-set-parent child token-meta))
+
+ (setf (phpinspect-bmap-token-stack bmap) stack)))
(setf (phpinspect-bmap-last-token-start bmap) start)
(push token-meta (phpinspect-bmap-token-stack bmap))))
@@ -243,34 +166,9 @@
(and (listp overlay)
(eq 'overlay (car overlay))))
-(defsubst phpinspect-overlay-wrap-meta (overlay meta)
- (when meta
- (setq meta (cl-copy-list meta))
- (setf (phpinspect-meta-start meta)
- (+ (phpinspect-meta-start meta) (phpinspect-overlay-delta overlay)))
- (setf (phpinspect-meta-end meta)
- (+ (phpinspect-meta-end meta) (phpinspect-overlay-delta overlay)))
-
- (when (phpinspect-meta-overlay meta)
- (let ((meta-overlay (cl-copy-list (phpinspect-meta-overlay meta))))
- (setf (phpinspect-overlay-start meta-overlay)
- (+ (phpinspect-overlay-start meta-overlay)
- (phpinspect-overlay-delta overlay)))
- (setf (phpinspect-overlay-end meta-overlay)
- (+ (phpinspect-overlay-end meta-overlay)
- (phpinspect-overlay-delta overlay)))
- (setf (phpinspect-overlay-delta meta-overlay)
- (+ (phpinspect-overlay-delta meta-overlay)
- (phpinspect-overlay-delta overlay)))
- (setf (phpinspect-meta-overlay meta) meta-overlay)))
-
- meta))
-
(cl-defmethod phpinspect-bmap-token-starting-at ((overlay (head overlay))
point)
- (phpinspect-overlay-wrap-meta
- overlay
- (phpinspect-bmap-token-starting-at
- (phpinspect-overlay-bmap overlay) (- point (phpinspect-overlay-delta
overlay)))))
+ (phpinspect-bmap-token-starting-at
+ (phpinspect-overlay-bmap overlay) (- point (phpinspect-overlay-delta
overlay))))
(cl-defmethod phpinspect-bmap-token-starting-at ((bmap phpinspect-bmap) point)
(let ((overlay (phpinspect-bmap-overlay-at-point bmap point)))
@@ -279,9 +177,8 @@
(gethash point (phpinspect-bmap-starts bmap)))))
(cl-defmethod phpinspect-bmap-tokens-ending-at ((overlay (head overlay)) point)
- (mapcar (lambda (meta) (phpinspect-overlay-wrap-meta overlay meta))
- (phpinspect-bmap-tokens-ending-at
- (phpinspect-overlay-bmap overlay) (- point
(phpinspect-overlay-delta overlay)))))
+ (phpinspect-bmap-tokens-ending-at
+ (phpinspect-overlay-bmap overlay) (- point (phpinspect-overlay-delta
overlay))))
(cl-defmethod phpinspect-bmap-tokens-ending-at ((bmap phpinspect-bmap) point)
(let ((overlay (phpinspect-bmap-overlay-at-point bmap point)))
@@ -290,7 +187,7 @@
(gethash point (phpinspect-bmap-ends bmap)))))
(defsubst phpinspect-bmap-overlay-at-point (bmap point)
- (let ((overlay (phpinspect-splayt-find (phpinspect-bmap-overlays bmap) point
#'<= #'<= #'<=)))
+ (let ((overlay (phpinspect-splayt-find-smallest-after
(phpinspect-bmap-overlays bmap) point)))
(when (and overlay (phpinspect-overlay-overlaps-point overlay point))
overlay)))
@@ -307,11 +204,7 @@
(<= (phpinspect-meta-end meta) (phpinspect-overlay-end overlay))))
(cl-defmethod phpinspect-bmap-token-meta ((overlay (head overlay)) token)
- (let ((meta
- (phpinspect-overlay-wrap-meta
- overlay (phpinspect-bmap-token-meta (phpinspect-overlay-bmap
overlay) token))))
- (when (and meta (phpinspect-overlay-encloses-meta overlay meta))
- meta)))
+ (phpinspect-bmap-token-meta (phpinspect-overlay-bmap overlay) token))
(cl-defmethod phpinspect-bmap-token-meta ((bmap phpinspect-bmap) token)
(unless (phpinspect-probably-token-p token)
@@ -322,6 +215,9 @@
(catch 'found
(phpinspect-splayt-traverse (overlay (phpinspect-bmap-overlays bmap))
(when (setq found? (phpinspect-bmap-token-meta overlay token))
+ ;; Hit overlay's node to rebalance tree
+ (phpinspect-splayt-find
+ (phpinspect-bmap-overlays bmap) (phpinspect-overlay-end
overlay))
(throw 'found found?)))))))
(defsubst phpinspect-probably-token-p (token)
@@ -357,7 +253,10 @@ giving up. If not provided, this is 100."
(start (+ (phpinspect-meta-start token-meta) pos-delta))
(end (+ (phpinspect-meta-end token-meta) pos-delta))
(overlay `(overlay ,start ,end ,pos-delta ,bmap-overlay ,token-meta)))
- (phpinspect-bmap-register bmap start end (phpinspect-meta-token
token-meta) whitespace-before overlay)
+ (phpinspect-meta-detach-parent token-meta)
+ (phpinspect-meta-shift token-meta pos-delta)
+ (setf (phpinspect-meta-overlay token-meta) overlay)
+ (phpinspect-bmap-register bmap start end (phpinspect-meta-token
token-meta) whitespace-before token-meta)
(phpinspect-splayt-insert (phpinspect-bmap-overlays bmap)
(phpinspect-overlay-end overlay) overlay)))
(defun phpinspect-bmap-make-location-resolver (bmap)
diff --git a/phpinspect-eldoc.el b/phpinspect-eldoc.el
index 3e8ac35d26..ffdc5e8459 100644
--- a/phpinspect-eldoc.el
+++ b/phpinspect-eldoc.el
@@ -77,27 +77,28 @@ be implemented for return values of
`phpinspect-eld-strategy-execute'")
variable
method
result)
- (cond ((phpinspect-static-attrib-p attrib)
- (setq variable (phpinspect--class-get-variable class
attribute-name))
-
- (if (and variable
- (or (phpinspect--variable-static-p variable)
- (phpinspect--variable-const-p variable)))
- (setq result variable)
- (setq method (phpinspect--class-get-static-method
- class (phpinspect-intern-name attribute-name)))
- (when method
- (setq result (phpinspect-make-function-doc :fn method)))))
- ((phpinspect-object-attrib-p attrib)
- (setq variable (phpinspect--class-get-variable class
attribute-name))
-
- (if (and variable
- (phpinspect--variable-vanilla-p variable))
- (setq result variable)
- (setq method (phpinspect--class-get-method
- class (phpinspect-intern-name attribute-name)))
- (when method
- (setq result (phpinspect-make-function-doc :fn
method))))))))))
+ (when attribute-name
+ (cond ((phpinspect-static-attrib-p attrib)
+ (setq variable (phpinspect--class-get-variable class
attribute-name))
+
+ (if (and variable
+ (or (phpinspect--variable-static-p variable)
+ (phpinspect--variable-const-p variable)))
+ (setq result variable)
+ (setq method (phpinspect--class-get-static-method
+ class (phpinspect-intern-name
attribute-name)))
+ (when method
+ (setq result (phpinspect-make-function-doc :fn method)))))
+ ((phpinspect-object-attrib-p attrib)
+ (setq variable (phpinspect--class-get-variable class
attribute-name))
+
+ (if (and variable
+ (phpinspect--variable-vanilla-p variable))
+ (setq result variable)
+ (setq method (phpinspect--class-get-method
+ class (phpinspect-intern-name
attribute-name)))
+ (when method
+ (setq result (phpinspect-make-function-doc :fn
method)))))))))))
(cl-defstruct (phpinspect-eld-function-args (:constructor
phpinspect-make-eld-function-args))
@@ -127,6 +128,7 @@ be implemented for return values of
`phpinspect-eld-strategy-execute'")
match-result static arg-list arg-pos)
(phpinspect--log "Eldoc statement is: %s" statement)
+ (phpinspect--log "Enclosing token was: %s" enclosing-token)
(when enclosing-token
(cond
;; Method call
diff --git a/phpinspect-meta.el b/phpinspect-meta.el
new file mode 100644
index 0000000000..03ce5767b7
--- /dev/null
+++ b/phpinspect-meta.el
@@ -0,0 +1,130 @@
+;;; phpinspect-meta.el --- PHP parsing and completion package -*-
lexical-binding: t; -*-
+
+;; Copyright (C) 2021 Free Software Foundation, Inc
+
+;; Author: Hugo Thunnissen <de...@hugot.nl>
+;; Keywords: php, languages, tools, convenience
+;; Version: 0
+
+;; This program is free software; you can redistribute it and/or modify
+;; it under the terms of the GNU General Public License as published by
+;; the Free Software Foundation, either version 3 of the License, or
+;; (at your option) any later version.
+
+;; This program is distributed in the hope that it will be useful,
+;; but WITHOUT ANY WARRANTY; without even the implied warranty of
+;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+;; GNU General Public License for more details.
+
+;; You should have received a copy of the GNU General Public License
+;; along with this program. If not, see <https://www.gnu.org/licenses/>.
+
+;;; Commentary:
+
+;;; Code:
+
+(require 'phpinspect-splayt)
+
+(define-inline phpinspect-make-meta
+ (parent start end whitespace-before token &optional overlay children
parent-offset)
+ (inline-quote (list 'meta ,parent ,start ,end ,whitespace-before ,token
,overlay
+ ;;,children ,parent-offset)))
+ (or ,children (phpinspect-make-splayt)) ,parent-offset)))
+
+(define-inline phpinspect-meta-parent (meta)
+ (inline-quote (cadr ,meta)))
+
+(define-inline phpinspect-meta-children (meta)
+ (inline-quote (car (nthcdr 7 ,meta))))
+
+(define-inline phpinspect-meta-parent-offset (meta)
+ (inline-quote (car (nthcdr 8 ,meta))))
+
+(define-inline phpinspect-meta-overlay (meta)
+ (inline-quote (car (nthcdr 6 ,meta))))
+
+(define-inline phpinspect-meta-token (meta)
+ (inline-quote (car (nthcdr 5 ,meta))))
+
+(define-inline phpinspect-meta-absolute-end (meta)
+ (inline-quote (cadddr ,meta)))
+
+(define-inline phpinspect-meta-whitespace-before (meta)
+ (inline-quote (car (cddddr ,meta))))
+
+(defun phpinspect-meta-start (meta)
+ (if (phpinspect-meta-parent meta)
+ (+ (phpinspect-meta-start (phpinspect-meta-parent meta))
+ (phpinspect-meta-parent-offset meta))
+ (phpinspect-meta-absolute-start meta)))
+
+(defun phpinspect-meta-end (meta)
+ (+ (phpinspect-meta-start meta) (phpinspect-meta-width meta)))
+
+(defsubst phpinspect-meta-width (meta)
+ (- (phpinspect-meta-absolute-end meta) (phpinspect-meta-absolute-start
meta)))
+
+(defun phpinspect-meta-sort-width (meta1 meta2)
+ (< (phpinspect-meta-width meta1) (phpinspect-meta-width meta2)))
+
+(defun phpinspect-meta-sort-start (meta1 meta2)
+ (< (phpinspect-meta-start meta1) (phpinspect-meta-start meta2)))
+
+(define-inline phpinspect-meta-absolute-start (meta)
+ (inline-quote (caddr ,meta)))
+
+(defsubst phpinspect-meta-overlaps-point (meta point)
+ (and (> (phpinspect-meta-end meta) point)
+ (<= (phpinspect-meta-start meta) point)))
+
+(defun phpinspect-meta-find-parent-matching-token (meta predicate)
+ (if (funcall predicate (phpinspect-meta-token meta))
+ meta
+ (catch 'found
+ (while (phpinspect-meta-parent meta)
+ (setq meta (phpinspect-meta-parent meta))
+ (when (funcall predicate (phpinspect-meta-token meta))
+ (throw 'found meta))))))
+
+(define-inline phpinspect-meta-set-parent (meta parent)
+ (inline-letevals (meta parent)
+ (inline-quote
+ (progn
+ (when ,parent
+ (setf (phpinspect-meta-parent-offset ,meta)
+ (- (phpinspect-meta-start ,meta) (phpinspect-meta-start
,parent)))
+ (phpinspect-meta-add-child ,parent ,meta))
+ (setcar (cdr ,meta) ,parent)))))
+
+;; Note: using defsubst here causes a byte code overflow
+(defun phpinspect-meta-add-child (meta child)
+ (phpinspect-splayt-insert (phpinspect-meta-children meta)
(phpinspect-meta-parent-offset child) child))
+
+(define-inline phpinspect-meta-detach-parent (meta)
+ (inline-letevals (meta)
+ (inline-quote
+ (when (phpinspect-meta-parent ,meta)
+ ;; Update absolute start and end
+ (setf (phpinspect-meta-absolute-start ,meta) (phpinspect-meta-start
,meta))
+ (setf (phpinspect-meta-absolute-end ,meta) (phpinspect-meta-end ,meta))
+ (setf (phpinspect-meta-parent ,meta) nil)))))
+
+(defun phpinspect-meta-shift (meta delta)
+ (setf (phpinspect-meta-absolute-start meta) (+ (phpinspect-meta-start meta)
delta))
+ (setf (phpinspect-meta-absolute-end meta) (+ (phpinspect-meta-end meta)
delta)))
+
+(defun phpinspect-meta-right-siblings (meta)
+ (mapcar #'phpinspect-meta-token
+ (sort
+ (phpinspect-splayt-find-all-after
+ (phpinspect-meta-children (phpinspect-meta-parent meta))
(phpinspect-meta-parent-offset meta))
+ #'phpinspect-meta-sort-start)))
+
+
+(defun phpinspect-meta-string (meta)
+ (format "[start: %d, end: %d, token: %s]"
+ (phpinspect-meta-start meta) (phpinspect-meta-end meta)
(phpinspect-meta-token meta)))
+
+
+(provide 'phpinspect-meta)
+;;; phpinspect-meta.el ends here
diff --git a/phpinspect-resolvecontext.el b/phpinspect-resolvecontext.el
index 16dca768bc..fd66f68091 100644
--- a/phpinspect-resolvecontext.el
+++ b/phpinspect-resolvecontext.el
@@ -60,21 +60,24 @@
(string= "return" (cadr token))))
(defun phpinspect-find-statement-before-point (bmap meta point)
- (let ((children (reverse (cdr (phpinspect-meta-token meta)))))
- (let ((previous-siblings))
- (catch 'return
- (dolist (child children)
- (when (phpinspect-probably-token-p child)
- (setq child (phpinspect-bmap-token-meta bmap child))
- (when (< (phpinspect-meta-start child) point)
- (if (and (not previous-siblings) (phpinspect-blocklike-p
(phpinspect-meta-token child)))
- (progn
- (throw 'return (phpinspect-find-statement-before-point
bmap child point)))
- (when (or (phpinspect-return-p (phpinspect-meta-token child))
- (phpinspect-end-of-statement-p
(phpinspect-meta-token child)))
- (throw 'return previous-siblings))
- (push (phpinspect-meta-token child) previous-siblings)))))
- previous-siblings))))
+ (let ((children (reverse (cdr (phpinspect-meta-token meta))))
+ child-meta
+ previous-siblings)
+ (catch 'return
+ (dolist (child children)
+ (when (phpinspect-probably-token-p child)
+ (setq child-meta (phpinspect-bmap-token-meta bmap child))
+ (unless child-meta
+ (phpinspect--log "[ERROR] No metadata object found for token %s"
child))
+ (when (< (phpinspect-meta-start child-meta) point)
+ (if (and (not previous-siblings) (phpinspect-blocklike-p child))
+ (progn
+ (throw 'return (phpinspect-find-statement-before-point bmap
child-meta point)))
+ (when (or (phpinspect-return-p child)
+ (phpinspect-end-of-statement-p child))
+ (throw 'return previous-siblings))
+ (push child previous-siblings)))))
+ previous-siblings)))
(defun phpinspect--get-last-statement-in-token (token)
(setq token (cond ((phpinspect-function-p token)
@@ -102,7 +105,10 @@
(subject (phpinspect-bmap-last-token-before-point bmap point))
(subject-token)
(siblings))
- (phpinspect--log "Last token before point: %s" (phpinspect-meta-token
subject))
+ (phpinspect--log "Last token before point: %s, right siblings: %s, parent:
%s"
+ (phpinspect-meta-string subject)
+ (phpinspect-meta-right-siblings subject)
+ (phpinspect-meta-string (phpinspect-meta-parent subject)))
(let ((next-sibling (car (phpinspect-meta-right-siblings subject))))
;; When the right sibling of the last ending token overlaps point, this
is
diff --git a/phpinspect-splayt.el b/phpinspect-splayt.el
index fa96aa7f61..a6e7475212 100644
--- a/phpinspect-splayt.el
+++ b/phpinspect-splayt.el
@@ -27,192 +27,223 @@
;; Important functions:
;; - `phpinspect-splayt-insert'
;; - `phpinspect-splayt-find'
+;; - `phpinspect-splayt-find-smallest-after'
+;; - `phpinspect-splayt-find-all-after'
;; - `phpinspect-splayt-traverse'
+;;;
+;;
+;; DEVELOPING
+;;
+;; The main aim for this tree implementation is to be reasonably fast and
+;; comfortable to use for most of phpinspect's common operations. That means:
+;;
+;; - Fast insertion of sequential keys (for example when parsing a buffer from
left to right)
+;; - Consing as few bytes as possible by keeping the data structure simple, to
avoid GC pauses as much as possible
+;; - Fast repeated acces of "hot" regions (for example the edited region of a
buffer)
+;; - A straight forward public API to retrieve sets of nodes
+;;
+;; ** Inline Functions **
+;; There is a lot of use of `define-inline' in this file. Most of these inlines
+;; improve performance significantly. This is especially true for smaller
+;; inlined functions. It might be possible to change one or two of the larger
+;; functions to normal defuns without reintroducing a lot of ovehead. If you
+;; want to do this to make debugging the code a little easier, and you can
+;; backup that it doesn't impact performance all that much with some benchmarks
+;; (especially parse-file.el in the benchmarks folder), your PR will be
welcomed.
+;;
-;;; Code:
-
-(defsubst phpinspect-make-splayt-node (key value &optional left right)
- (cons (cons key value) (cons left right)))
-
-(defsubst phpinspect-splayt-node-left (node)
- (cadr node))
-
-(defsubst phpinspect-splayt-node-right (node)
- (cddr node))
-
-(defsubst phpinspect-splayt-node-key (node)
- (caar node))
-
-(defsubst phpinspect-splayt-node-value (node)
- (cdar node))
-
-(gv-define-setter phpinspect-splayt-node-left (left node) `(setcar (cdr ,node)
,left))
-(gv-define-setter phpinspect-splayt-node-right (right node) `(setcdr (cdr
,node) ,right))
-(gv-define-setter phpinspect-splayt-node-key (key node) `(setcar (car ,node)
,value))
-(gv-define-setter phpinspect-splayt-node-value (value node) `(setcdr (car
,node) ,value))
-
-(defsubst phpinspect-splayt-node-update-parent (node parent new-val)
- (if (eq node (phpinspect-splayt-node-left parent))
- (setf (phpinspect-splayt-node-left parent) new-val)
- (setf (phpinspect-splayt-node-right parent) new-val)))
-
-(defsubst phpinspect-make-splayt (&optional root-node)
- (cons root-node nil))
-
-(defsubst phpinspect-splayt-root-node (splayt)
- (car splayt))
-(gv-define-setter phpinspect-splayt-root-node (node splayt) `(setcar ,splayt
,node))
+;;; Code:
-(defsubst phpinspect-splayt-node-rotate-right (node &optional parent splayt)
- (let* ((left (phpinspect-splayt-node-left node))
- (left-right (phpinspect-splayt-node-right left)))
- (setf (phpinspect-splayt-node-right left) node)
- (setf (phpinspect-splayt-node-left node) left-right)
-
- (when (and splayt (eq node (phpinspect-splayt-root-node splayt)))
- (setf (phpinspect-splayt-root-node splayt) left))
+(define-inline phpinspect-make-splayt-node (key value &optional left right
parent temp-store)
+ (inline-quote (cons (cons ,key ,value) (list ,left ,right ,parent
,temp-store))))
+
+(define-inline phpinspect-splayt-node-left (node)
+ (inline-quote (cadr ,node)))
- (when parent
- (phpinspect-splayt-node-update-parent node parent left))))
+(define-inline phpinspect-splayt-node-right (node)
+ (inline-quote (caddr ,node)))
-(defsubst phpinspect-splayt-node-rotate-left (node &optional parent splayt)
- (let* ((right (phpinspect-splayt-node-right node))
- (right-left (phpinspect-splayt-node-left right)))
- (setf (phpinspect-splayt-node-left right) node)
- (setf (phpinspect-splayt-node-right node) right-left)
-
- (when (and splayt (eq node (phpinspect-splayt-root-node splayt)))
- (setf (phpinspect-splayt-root-node splayt) right))
-
- (when parent
- (phpinspect-splayt-node-update-parent node parent right))))
-
-(defsubst phpinspect-make-splayt-nav (splayt &optional current-node parents)
- (cons splayt (cons (or current-node (phpinspect-splayt-root-node splayt))
- parents)))
-
-(defsubst phpinspect-splayt-nav-splayt (nav)
- (car nav))
-
-(defsubst phpinspect-splayt-nav-current (nav)
- (cadr nav))
-
-(defsubst phpinspect-splayt-nav-parents (nav)
- (cddr nav))
-
-(gv-define-setter phpinspect-splayt-nav-current (node nav) `(setcar (cdr ,nav)
,node))
-(gv-define-setter phpinspect-splayt-nav-parents (parents nav) `(setcdr (cdr
,nav) ,parents))
-
-(defsubst phpinspect-splayt-nav-right (nav)
- (push (phpinspect-splayt-nav-current nav) (phpinspect-splayt-nav-parents
nav))
- (setf (phpinspect-splayt-nav-current nav)
- (phpinspect-splayt-node-right (phpinspect-splayt-nav-current nav))))
-
-(defsubst phpinspect-splayt-nav-left (nav)
- (push (phpinspect-splayt-nav-current nav) (phpinspect-splayt-nav-parents
nav))
- (setf (phpinspect-splayt-nav-current nav)
- (phpinspect-splayt-node-left (phpinspect-splayt-nav-current nav))))
-
-(defsubst phpinspect-splayt-nav-has-left-p (nav)
- (phpinspect-splayt-node-left (phpinspect-splayt-nav-current nav)))
-
-(defsubst phpinspect-splayt-nav-has-right-p (nav)
- (phpinspect-splayt-node-right (phpinspect-splayt-nav-current nav)))
-
-(defsubst phpinspect-splayt-nav-up (nav)
- (setf (phpinspect-splayt-nav-current nav)
- (pop (phpinspect-splayt-nav-parents nav))))
-
-(defsubst phpinspect-splayt-nav-current-value (nav)
- (phpinspect-splayt-node-value (phpinspect-splayt-nav-current nav)))
-
-(defsubst phpinspect-splayt-nav-current-key (nav)
- (phpinspect-splayt-node-key (phpinspect-splayt-nav-current nav)))
-
-(defsubst phpinspect-splayt-insert (splayt key value)
- (phpinspect-splayt-insert-node splayt (phpinspect-make-splayt-node key
value)))
-
-(defsubst phpinspect-splay (splayt node parents)
- (let (grandparent great-grandparent)
- (while parents
- (setq parent (pop parents))
- (setq grandparent (pop parents))
-
- (if grandparent
- (cond
- ;; Zig-Zig rotation
- ((and (eq parent (phpinspect-splayt-node-left grandparent))
- (eq node (phpinspect-splayt-node-left parent)))
- (phpinspect-splayt-node-rotate-right grandparent (car parents)
splayt)
- (phpinspect-splayt-node-rotate-right parent (car parents) splayt))
-
- ;; Zag-Zag rotation
- ((and (eq parent (phpinspect-splayt-node-right grandparent))
- (eq node (phpinspect-splayt-node-right parent)))
- (phpinspect-splayt-node-rotate-left grandparent (car parents)
splayt)
- (phpinspect-splayt-node-rotate-left parent (car parents) splayt))
-
- ;; Zig-Zag rotation
- ((and (eq parent (phpinspect-splayt-node-right grandparent))
- (eq node (phpinspect-splayt-node-left parent)))
- (phpinspect-splayt-node-rotate-right parent grandparent splayt)
- (phpinspect-splayt-node-rotate-left grandparent (car parents)
splayt))
-
- ;; Zag-Zig rotation
- ((and (eq parent (phpinspect-splayt-node-left grandparent))
- (eq node (phpinspect-splayt-node-right parent)))
- (phpinspect-splayt-node-rotate-left parent grandparent splayt)
- (phpinspect-splayt-node-rotate-right grandparent (car parents)
splayt))
- (t
- (error "Failed in determining rotation strategy")))
- ;; Else
- (if (eq node (phpinspect-splayt-node-left parent))
- (phpinspect-splayt-node-rotate-right parent (car parents) splayt)
- (phpinspect-splayt-node-rotate-left parent (car parents) splayt))))))
-
-(defsubst phpinspect-splayt-insert-node (splayt node)
- (if (not (phpinspect-splayt-root-node splayt))
- (setf (phpinspect-splayt-root-node splayt) node)
-
- ;; Else
- (let ((nav (phpinspect-make-splayt-nav splayt)))
- (catch 'break
- (while t
- (if (< (phpinspect-splayt-node-key node)
- (phpinspect-splayt-nav-current-key nav))
- (if (phpinspect-splayt-nav-has-left-p nav)
- (phpinspect-splayt-nav-left nav)
- (setf (phpinspect-splayt-node-left
(phpinspect-splayt-nav-current nav))
- node)
- (throw 'break nil))
-
- ;; Else
- (if (phpinspect-splayt-nav-has-right-p nav)
- (phpinspect-splayt-nav-right nav)
- (setf (phpinspect-splayt-node-right
(phpinspect-splayt-nav-current nav))
- node)
- (throw 'break nil))))))))
+(define-inline phpinspect-splayt-node-key (node)
+ (inline-quote (caar ,node)))
+
+(define-inline phpinspect-splayt-node-value (node)
+ (inline-quote (cdar ,node)))
+
+(define-inline phpinspect-splayt-node-parent (node)
+ (inline-quote (cadddr ,node)))
-(defmacro phpinspect-splayt-traverse (place-and-splayt &rest body)
- "Traverse splay tree in cadr of PLACE-AND-SPLAYT, executing BODY.
-
-The car of PLACE-AND-SPLAYT is assigned the value of each node.
-
-Traversal is breadth-first to take advantage of the splay trees
-main benefit: the most accessed interval of keys is likely to be
-near the top of the tee."
+(define-inline phpinspect-splayt-node-temp-store (node)
+ "Dedicated place to store data when necessary. Mostly used for
+rotations without instantiating a lexical environment with
+`let'. When only used once or twice in a function call, this
+apeared to be a little more performant than using `let'."
+ (inline-quote (car (cddddr ,node))))
+
+(define-inline phpinspect-splayt-node-update-parent (node parent new-val)
+ (inline-letevals (node parent new-val)
+ (inline-quote
+ (if (eq ,node (phpinspect-splayt-node-left ,parent))
+ (setf (phpinspect-splayt-node-left ,parent) ,new-val)
+ (setf (phpinspect-splayt-node-right ,parent) ,new-val)))))
+
+(define-inline phpinspect-make-splayt (&optional root-node)
+ (inline-quote
+ (cons ,root-node nil)))
+
+(define-inline phpinspect-splayt-root-node (splayt)
+ (inline-quote (car ,splayt)))
+
+(define-inline phpinspect-splayt-node-rotate-right (node &optional splayt)
+ (inline-letevals (node splayt)
+ (inline-quote
+ (progn
+ ;; Save right node of left child
+ (setf (phpinspect-splayt-node-temp-store ,node)
+ (phpinspect-splayt-node-right (phpinspect-splayt-node-left
,node)))
+
+ ;; Update node parent to reference left as child
+ (when (phpinspect-splayt-node-parent ,node)
+ (phpinspect-splayt-node-update-parent
+ ,node (phpinspect-splayt-node-parent ,node)
(phpinspect-splayt-node-left ,node)))
+
+ ;; Set left node new parent
+ (setf (phpinspect-splayt-node-parent (phpinspect-splayt-node-left
,node))
+ (phpinspect-splayt-node-parent ,node))
+
+ ;; Set left node as node's new parent
+ (setf (phpinspect-splayt-node-parent ,node)
+ (phpinspect-splayt-node-left ,node))
+
+ ;; Set node as left's right child
+ (setf (phpinspect-splayt-node-right (phpinspect-splayt-node-left
,node)) ,node)
+
+ ;; Set left's right child as node's left child
+ (setf (phpinspect-splayt-node-left ,node)
(phpinspect-splayt-node-temp-store ,node))
+
+ ;; Update new left child's parent
+ (when (phpinspect-splayt-node-left ,node)
+ (setf (phpinspect-splayt-node-parent (phpinspect-splayt-node-left
,node)) ,node))
+
+ ;; Update root node of tree when necessary
+ (when (and ,splayt (eq ,node (phpinspect-splayt-root-node ,splayt)))
+ (setf (phpinspect-splayt-root-node ,splayt)
(phpinspect-splayt-node-parent ,node)))))))
+
+(define-inline phpinspect-splayt-node-rotate-left (node &optional splayt)
+ (inline-letevals (node splayt)
+ (inline-quote
+ (progn
+ ;; Save left node of right child
+ (setf (phpinspect-splayt-node-temp-store ,node)
+ (phpinspect-splayt-node-left (phpinspect-splayt-node-right
,node)))
+
+ ;; Update node parent to reference right as child
+ (when (phpinspect-splayt-node-parent ,node)
+ (phpinspect-splayt-node-update-parent
+ ,node (phpinspect-splayt-node-parent ,node)
(phpinspect-splayt-node-right ,node)))
+
+ ;; Set right node new parent
+ (setf (phpinspect-splayt-node-parent (phpinspect-splayt-node-right
,node))
+ (phpinspect-splayt-node-parent ,node))
+
+ ;; Set right node as node's new parent
+ (setf (phpinspect-splayt-node-parent ,node)
+ (phpinspect-splayt-node-right ,node))
+
+ ;; Set node as right's left child
+ (setf (phpinspect-splayt-node-left (phpinspect-splayt-node-right
,node)) ,node)
+
+ ;; Set right's left child as node's right child
+ (setf (phpinspect-splayt-node-right ,node)
(phpinspect-splayt-node-temp-store ,node))
+
+ ;; Update new right child's parent
+ (when (phpinspect-splayt-node-right ,node)
+ (setf (phpinspect-splayt-node-parent (phpinspect-splayt-node-right
,node)) ,node))
+
+ ;; Update root node of tree when necessary
+ (when (and ,splayt (eq ,node (phpinspect-splayt-root-node ,splayt)))
+ (setf (phpinspect-splayt-root-node ,splayt)
(phpinspect-splayt-node-parent ,node)))))))
+
+(define-inline phpinspect-splayt-insert (splayt key value)
+ (inline-quote
+ (phpinspect-splayt-insert-node ,splayt (phpinspect-make-splayt-node ,key
,value))))
+
+(define-inline phpinspect-splayt-node-grandparent (node)
+ (inline-quote (phpinspect-splayt-node-parent (phpinspect-splayt-node-parent
,node))))
+
+(define-inline phpinspect-splay (splayt node)
+ (inline-letevals (splayt node)
+ (let ((parent (inline-quote (phpinspect-splayt-node-parent ,node)))
+ (grandparent (inline-quote (phpinspect-splayt-node-grandparent
,node))))
+ (inline-quote
+ (progn
+ (while ,parent
+ (if (phpinspect-splayt-node-grandparent ,node)
+ (cond
+ ;; Zig-Zig rotation
+ ((and (eq ,parent (phpinspect-splayt-node-left ,grandparent))
+ (eq ,node (phpinspect-splayt-node-left ,parent)))
+ (phpinspect-splayt-node-rotate-right ,grandparent ,splayt)
+ (phpinspect-splayt-node-rotate-right ,parent ,splayt))
+
+ ;; Zag-Zag rotation
+ ((and (eq (phpinspect-splayt-node-parent ,node)
+ (phpinspect-splayt-node-right
(phpinspect-splayt-node-grandparent ,node)))
+ (eq ,node (phpinspect-splayt-node-right
(phpinspect-splayt-node-parent ,node))))
+ (phpinspect-splayt-node-rotate-left ,grandparent ,splayt)
+ (phpinspect-splayt-node-rotate-left ,parent ,splayt))
+
+ ;; Zig-Zag rotation
+ ((and (eq ,parent (phpinspect-splayt-node-right ,grandparent))
+ (eq ,node (phpinspect-splayt-node-left ,parent)))
+ (phpinspect-splayt-node-rotate-right ,parent ,splayt)
+ (phpinspect-splayt-node-rotate-left ,parent ,splayt))
+
+ ;; Zag-Zig rotation
+ ((and (eq ,parent (phpinspect-splayt-node-left ,grandparent))
+ (eq ,node (phpinspect-splayt-node-right ,parent)))
+ (phpinspect-splayt-node-rotate-left ,parent ,splayt)
+ (phpinspect-splayt-node-rotate-right ,parent ,splayt))
+ (t
+ (error "Failed in determining rotation strategy.
(phpinspect-splayt-node-grandparent ,node): %s, parent: %s, ,node: %s")))
+
+ ;; Else
+ (if (eq ,node (phpinspect-splayt-node-left ,parent))
+ (phpinspect-splayt-node-rotate-right ,parent ,splayt)
+ (phpinspect-splayt-node-rotate-left ,parent ,splayt))))
+
+ ,node)))))
+
+(define-inline phpinspect-splayt-insert-node (splayt node)
+ (inline-letevals (splayt node (parent (inline-quote
(phpinspect-splayt-node-temp-store ,node))))
+ (inline-quote
+ (if (not (phpinspect-splayt-root-node ,splayt))
+ (setf (phpinspect-splayt-root-node ,splayt) ,node)
+ (progn
+ (setf ,parent (phpinspect-splayt-find-insertion-node ,splayt
(phpinspect-splayt-node-key ,node)))
+ (unless ,parent
+ (error "Error: failed to find parent node for %s" ,node))
+
+ (setf (phpinspect-splayt-node-parent ,node) ,parent)
+ (if (< (phpinspect-splayt-node-key ,parent)
(phpinspect-splayt-node-key ,node))
+ (setf (phpinspect-splayt-node-right ,parent) ,node)
+ (setf (phpinspect-splayt-node-left ,parent) ,node))
+
+ (phpinspect-splay ,splayt ,node))))))
+
+(defmacro phpinspect-splayt-node-traverse (place-and-node &rest body)
(declare (indent 1))
- (let ((place (car place-and-splayt))
+ (let ((place (car place-and-node))
(current-sym (gensym))
- (splayt-sym (gensym))
(stack-sym (gensym))
(queue-sym (gensym))
(reverse-sym (gensym))
+ (node-sym (gensym))
(size-sym (gensym)))
- `(let* ((,splayt-sym ,(cadr place-and-splayt))
+ `(let* ((,node-sym ,(cadr place-and-node))
;; Make place locally scoped variable if a symbol
- (,queue-sym (list (phpinspect-splayt-root-node ,splayt-sym)))
+ (,queue-sym (when ,node-sym
+ (list ,node-sym)))
(,reverse-sym t)
,size-sym
,stack-sym
@@ -231,10 +262,10 @@ near the top of the tee."
,@body)
(when (phpinspect-splayt-node-right ,current-sym)
- (setq ,queue-sym (nconc ,queue-sym (list
(phpinspect-splayt-node-right ,current-sym)))))
+ (push (phpinspect-splayt-node-right ,current-sym) ,queue-sym))
(when (phpinspect-splayt-node-left ,current-sym)
- (setq ,queue-sym (nconc ,queue-sym (list
(phpinspect-splayt-node-left ,current-sym)))))
+ (push (phpinspect-splayt-node-left ,current-sym) ,queue-sym))
(setq ,size-sym (- ,size-sym 1)))
@@ -244,38 +275,110 @@ near the top of the tee."
(setf ,place (phpinspect-splayt-node-value ,current-sym))
,@body))
- (setq ,reverse-sym (not ,reverse-sym))))))
-
-(defsubst phpinspect-splayt-find (splayt key &optional navigator matcher
continue-predicate)
- (unless navigator (setq navigator #'<))
- (unless matcher (setq matcher #'=))
-
- (let ((nav (phpinspect-make-splayt-nav splayt))
- current next)
- (when (phpinspect-splayt-nav-current nav)
- (catch 'found
- (while t
- (setq current (phpinspect-splayt-nav-current nav)
- next nil)
- (cond
- ((funcall navigator key (phpinspect-splayt-nav-current-key nav))
- (when (phpinspect-splayt-nav-has-left-p nav)
- (phpinspect-splayt-nav-left nav)
- (setq next (phpinspect-splayt-nav-current nav))))
- (t
- (when (phpinspect-splayt-nav-has-right-p nav)
- (phpinspect-splayt-nav-right nav)
- (setq next (phpinspect-splayt-nav-current nav)))))
-
- (if (funcall matcher key (phpinspect-splayt-node-key current))
- (when (or (not next)
- (not continue-predicate)
- (not (funcall continue-predicate key
(phpinspect-splayt-node-key next))))
- (phpinspect-splay
- splayt current
- (if next (cdr (phpinspect-splayt-nav-parents nav))
(phpinspect-splayt-nav-parents nav)))
- (throw 'found (phpinspect-splayt-node-value current)))
- (unless next
- (throw 'found nil))))))))
+ (setq ,reverse-sym (not ,reverse-sym)))
+
+ nil)))
+
+(defmacro phpinspect-splayt-traverse (place-and-splayt &rest body)
+ "Traverse splay tree in cadr of PLACE-AND-SPLAYT, executing BODY.
+
+The car of PLACE-AND-SPLAYT is assigned the value of each node.
+
+Traversal is breadth-first to take advantage of the splay trees
+main benefit: the most accessed interval of keys is likely to be
+near the top of the tee."
+ (declare (indent 1))
+ `(phpinspect-splayt-node-traverse
+ (,(car place-and-splayt) (phpinspect-splayt-root-node ,(cadr
place-and-splayt)))
+ ,@body))
+
+(define-inline phpinspect-splayt-find-node (splayt key)
+ (inline-letevals (splayt key)
+ (inline-quote
+ (let ((current (phpinspect-splayt-root-node ,splayt)))
+ (catch 'return
+ (while current
+ (if (= ,key (phpinspect-splayt-node-key current))
+ (progn
+ (phpinspect-splay ,splayt current)
+ (throw 'return current))
+ (if (< ,key (phpinspect-splayt-node-key current))
+ (setq current (phpinspect-splayt-node-left current))
+ (setq current (phpinspect-splayt-node-right current))))))))))
+
+(define-inline phpinspect-splayt-find-insertion-node (splayt key)
+ (inline-letevals (splayt key)
+ (inline-quote
+ (let ((current (phpinspect-splayt-root-node ,splayt)))
+ (catch 'return
+ (while current
+ (if (or (and (> (phpinspect-splayt-node-key current) ,key)
+ (not (phpinspect-splayt-node-left current)))
+ (and (<= (phpinspect-splayt-node-key current) ,key)
+ (not (phpinspect-splayt-node-right current))))
+ (throw 'return current)
+ (if (< ,key (phpinspect-splayt-node-key current))
+ (setq current (phpinspect-splayt-node-left current))
+ (setq current (phpinspect-splayt-node-right current))))))))))
+
+(define-inline phpinspect-splayt-find-smallest-node-after (splayt key)
+ (inline-letevals (splayt key)
+ (inline-quote
+ (let ((current (phpinspect-splayt-root-node ,splayt))
+ smallest)
+
+ (catch 'break
+ (while current
+ (if (>= ,key (phpinspect-splayt-node-key current))
+ (setf current (phpinspect-splayt-node-right current)
+ smallest current)
+ (throw 'break nil))))
+
+ (catch 'return
+ (while current
+ (when (= (+ ,key 1) (phpinspect-splayt-node-key current))
+ (throw 'return current))
+
+ (cond ((and (phpinspect-splayt-node-parent current)
+ (< ,key (phpinspect-splayt-node-key
(phpinspect-splayt-node-parent current)))
+ (eq (phpinspect-splayt-node-right
(phpinspect-splayt-node-parent current))
+ current))
+ (setf current (phpinspect-splayt-node-parent current)
+ smallest current))
+ ((phpinspect-splayt-node-left current)
+ (setf current (phpinspect-splayt-node-left current))
+ (when (< ,key (phpinspect-splayt-node-key current))
+ (setf smallest current)))
+ ((>= ,key (phpinspect-splayt-node-key current))
+ (if (phpinspect-splayt-node-right current)
+ (setf current (phpinspect-splayt-node-right current))
+ (throw 'return smallest)))
+ (t (throw 'return smallest)))))))))
+
+(defsubst phpinspect-splayt-find-all-after (splayt key)
+ "Find all values in SPLAYT with a key higher than KEY."
+ (let ((first (phpinspect-splayt-find-smallest-node-after splayt key))
+ all)
+ (while first
+ (push (phpinspect-splayt-node-value first) all)
+
+ (phpinspect-splayt-node-traverse (sibling (phpinspect-splayt-node-right
first))
+ (setq all (nconc all (list sibling))))
+
+ (if (and (phpinspect-splayt-node-parent first)
+ (eq first (phpinspect-splayt-node-left
(phpinspect-splayt-node-parent first))))
+ (setq first (phpinspect-splayt-node-parent first))
+ (setq first nil)))
+ all))
+
+(define-inline phpinspect-splayt-find-smallest-after (splayt key)
+ "Find value of node with smallest key that is higher than KEY in SPLAYT."
+ (inline-quote
+ (phpinspect-splayt-node-value
+ (phpinspect-splay
+ ,splayt (phpinspect-splayt-find-smallest-node-after ,splayt ,key)))))
+
+(defsubst phpinspect-splayt-find (splayt key)
+ (phpinspect-splayt-node-value (phpinspect-splayt-find-node splayt key)))
(provide 'phpinspect-splayt)
diff --git a/test/test-bmap.el b/test/test-bmap.el
index 700564a25b..613efaecfd 100644
--- a/test/test-bmap.el
+++ b/test/test-bmap.el
@@ -94,6 +94,9 @@
(phpinspect-bmap-overlay
bmap bmap2 (phpinspect-bmap-token-starting-at bmap2 200) 20)
+ (phpinspect-bmap-overlay
+ bmap bmap2 (phpinspect-bmap-token-starting-at bmap2 220) 20)
+
(setq result (phpinspect-bmap-tokens-overlapping bmap 240))
(should (equal '((:token6) (:token5)) (mapcar #'phpinspect-meta-token
result)))
diff --git a/test/test-splayt.el b/test/test-splayt.el
index c399f7c1c5..8bc9829136 100644
--- a/test/test-splayt.el
+++ b/test/test-splayt.el
@@ -27,24 +27,30 @@
(ert-deftest phpinspect-splayt-node-rotate ()
(let* ((one (phpinspect-make-splayt-node 1 "one"))
- (node (phpinspect-make-splayt-node
+ (four (phpinspect-make-splayt-node 4 "four"))
+ (three (phpinspect-make-splayt-node
3 "three"
one
- (phpinspect-make-splayt-node 4 "four"))))
- (phpinspect-splayt-node-rotate-right node)
- (should (equal (phpinspect-make-splayt-node
- 1 "one" nil
- (phpinspect-make-splayt-node
- 3 "three" nil (phpinspect-make-splayt-node 4 "four")))
- one))
-
- (phpinspect-splayt-node-rotate-left node one)
-
- (should (equal (phpinspect-make-splayt-node
- 1 "one" nil
- (phpinspect-make-splayt-node
- 4 "four" (phpinspect-make-splayt-node 3 "three")))
- one))))
+ four)))
+ (setf (phpinspect-splayt-node-parent four) three)
+ (setf (phpinspect-splayt-node-parent one) three)
+ (phpinspect-splayt-node-rotate-right three)
+
+ (should (eq one (phpinspect-splayt-node-parent three)))
+ (should (eq three (phpinspect-splayt-node-parent four)))
+ (should (eq three (phpinspect-splayt-node-right one)))
+ (should (eq four (phpinspect-splayt-node-right three)))
+ (should-not (phpinspect-splayt-node-left one))
+ (should-not (phpinspect-splayt-node-left four))
+ (should-not (phpinspect-splayt-node-left three))
+
+ (phpinspect-splayt-node-rotate-left one)
+
+ (should (eq one (phpinspect-splayt-node-left three)))
+ (should (eq three (phpinspect-splayt-node-parent four)))
+ (should (eq three (phpinspect-splayt-node-parent one)))
+ (should (eq four (phpinspect-splayt-node-right three)))
+ (should (eq one (phpinspect-splayt-node-left three)))))
(ert-deftest phpinspect-splayt ()
(let ((tree (phpinspect-make-splayt)))
@@ -63,7 +69,17 @@
(should (string= "nine" (phpinspect-splayt-find tree 9)))
(should (string= "four" (phpinspect-splayt-find tree 4)))
(should (string= "twelve" (phpinspect-splayt-find tree 12)))
- (should (string= "eleven" (phpinspect-splayt-find tree 11)))))
+ (should (string= "eleven" (phpinspect-splayt-find tree 11)))
+
+ (let ((expected (sort '("nine" "three" "eleven" "eight" "twelve" "four"
"one") #'string-lessp))
+ (result))
+
+ (phpinspect-splayt-traverse (item tree)
+ (push item result))
+
+ (setq result (sort result #'string-lessp))
+
+ (should (equal expected result)))))
(ert-deftest phpinspect-splayt-traverse ()
(let ((tree (phpinspect-make-splayt)))
@@ -84,3 +100,31 @@
(setq result (sort result #'string-lessp))
(should (equal expected result)))))
+
+(ert-deftest phpinspect-splayt-find-smallest-after ()
+ (let ((tree (phpinspect-make-splayt)))
+ (phpinspect-splayt-insert tree 9 "nine")
+ (phpinspect-splayt-insert tree 3 "three")
+ (phpinspect-splayt-insert tree 11 "eleven")
+ (phpinspect-splayt-insert tree 8 "eight")
+ (phpinspect-splayt-insert tree 12 "twelve")
+ (phpinspect-splayt-insert tree 4 "four")
+ (phpinspect-splayt-insert tree 1 "one")
+
+
+ (should (string= "nine" (phpinspect-splayt-find-smallest-after tree 8)))
+ (should (string= "three" (phpinspect-splayt-find-smallest-after tree 1)))))
+
+(ert-deftest phpinspect-splayt-find-all-after ()
+ (let ((tree (phpinspect-make-splayt)))
+ (phpinspect-splayt-insert tree 9 "nine")
+ (phpinspect-splayt-insert tree 3 "three")
+ (phpinspect-splayt-insert tree 11 "eleven")
+ (phpinspect-splayt-insert tree 8 "eight")
+ (phpinspect-splayt-insert tree 12 "twelve")
+ (phpinspect-splayt-insert tree 4 "four")
+ (phpinspect-splayt-insert tree 1 "one")
+
+
+ (should (equal (sort '("eight" "nine" "eleven" "twelve") #'string-lessp)
+ (sort (phpinspect-splayt-find-all-after tree 7)
#'string-lessp)))))
