feature/tree-sitter c957832cbf 08/15: Remove treesit-traverse functions

[Yuan Fu]

branch: feature/tree-sitter
commit c957832cbf3e87e5a25f7c2bdb70abd959391d98
Author: Yuan Fu <casouri@gmail.com>
Commit: Yuan Fu <casouri@gmail.com>

    Remove treesit-traverse functions
    
    Remove before adding the replacements.
    
    * doc/lispref/parsing.texi (Retrieving Node): Remove relevant sections.
    * lisp/treesit.el (treesit-traverse-depth-first)
    (treesit--traverse-breadth-first-1)
    (treesit-traverse-breadth-first)
    (treesit-next-sibling-or-up)
    (treesit-traverse-forward)
    (treesit-search-forward)
    (treesit-search-beginning):
    (treesit-search-end): Remove functions.
    (treesit-defun-query): Remove variable.
    (treesit-beginning-of-defun)
    (treesit-end-of-defun): Remove functions.
    * test/src/treesit-tests.el: Remove comments.
---
 doc/lispref/parsing.texi   |  92 +---------------
 doc/lispref/positions.texi |  26 -----
 lisp/treesit.el            | 259 +--------------------------------------------
 test/src/treesit-tests.el  |   8 --
 4 files changed, 4 insertions(+), 381 deletions(-)

diff --git a/doc/lispref/parsing.texi b/doc/lispref/parsing.texi
index a83ad20281..0dbc70ce2d 100644
--- a/doc/lispref/parsing.texi
+++ b/doc/lispref/parsing.texi
@@ -580,34 +580,11 @@ for named child (@pxref{tree-sitter named node, named 
node}).
 
 @heading Searching for node
 
-@defun treesit-search-beginning query arg &optional lang up-only
-This function searches for the next node that @var{query} captures,
-starting at point.  Use the parser in current buffer that has
-@var{lang} as its language, if @var{lang} is nil, use the first parser
-in current buffer’s buffer list.
-
-This function stops at the @var{arg}'th match.  If @var{arg} is
-negative, search backward.  If the search succeeds, stop at the
-beginning of the matched node and return the node.  Return nil if
-search failed.
-
-By default, this function searches by traversing the parse tree depth
-first, starting from the node at point.  If @var{up-only} is non-nil,
-this function only go to siblings and parents, but never go down into
-children nodes.
+
 @end defun
 
-@defun treesit-search-end query arg &optional lang up-only
-This function is like @code{treesit-search-beginning}, but stops at
-the end of the matched node.
 @end defun
 
-@defun treesit-search-forward pos-fn arg query &optional lang up-only
-This function is like @code{treesit-search-beginning} and
-@code{treesit-search-end}, but instead of stopping at the beginning or
-end of the matched node, it determines where to stop by @var{pos-fn},
-where @var{pos-fn} is a function that takes a node and returns a
-position
 @end defun
 
 @heading More convenient functions
@@ -634,73 +611,6 @@ parent as the single argument).  I.e., this function 
returns the
 farthest parent that still satisfies @var{pred}.
 @end defun
 
-@cindex trees-sitter tree traversal
-@defun treesit-traverse-depth-first node pred &optional step depth
-Traverse the subtree of @var{node} depth-first. Traverse starting from
-@var{node} (i.e., @var{node} is passed to @var{pred}).  For each node
-traversed, we call @var{pred} with the node, and we stop and return
-the node if @var{pred} returns non-nil.  If no node satisfies
-@var{pred}, return nil.
-
-If @var{step} >= 0 or nil, go forward, if @var{step} < 0, go backward.
-(The quantity of @var{step} doesn't matter.)
-
-@var{depth} can be a positive integer or 0, meaning go @var{depth}
-levels deep, counting from @var{node}, or nil, meaning there is no
-limit.  For example, a value 0 means only traverse @var{node} itself,
-a value 1 means traverse @var{node} and its immediate children.
-@end defun
-
-@defun treesit-traverse-breadth-first node pred &optional step
-Traverse the subtree of @var{node} breadth-first.  Traverse starting
-from @var{node} (i.e., @var{node} is passed to @var{pred}).  For each
-node traversed, call @var{pred} with the node, stop and return the
-node if @var{pred} returns non-nil.  If no node satisfies @var{pred},
-return nil.
-
-If @var{step} >= 0 or nil, go forward, if @var{step} < 0, go backward.
-(The quantity of @var{step} doesn't matter.)
-@end defun
-
-@defun treesit-traverse-forward node pred &optional step depth
-Traverses the whole tree forward from NODE depth-first.  Traverse
-starting from @var{node} (i.e., @var{node} is passed to @var{pred}).
-For each node traversed, call @var{pred} with the node, stop and
-return the node if @var{pred} returns non-nil.  If no node satisfies
-@var{pred}, return nil.
-
-If @var{step} >= 0 or nil, go forward, if @var{step} < 0, go backward.
-(The quantity of @var{step} doesn't matter.)
-
-Traversing forward means that for a tree like the below where
-@var{node} is marked 1, traverse as numbered:
-
-@example
-@group
-                16
-                |
-       3--------4-----------8
-       |        |           |
-  o--o-+--1  5--+--6    9---+-----12
-  |  |    |        |    |         |
-  o  o    2        7  +-+-+    +--+--+
-                      |   |    |  |  |
-                      10  11   13 14 15
-@end group
-@end example
-
-@var{depth} can be a positive integer, 0, nil, or @code{'up}.  A
-positive integer or 0 means go @var{depth} deep counting from
-@var{node}.  A nil means no limit.  And a symbol @code{'up} means go
-upwards only: only traverse to sibling and parent, never go down to
-children.
-
-The difference between 0 and @code{'up} is subtle: in the above
-example, if given 0 as @var{depth}, node 1 3 4 5 6 8 9 12 16 are
-visited; if given @code{'up} as @var{depth}, only node 1 3 4 8 16 are
-visited.
-@end defun
-
 @node Accessing Node
 @section Accessing Node Information
 
diff --git a/doc/lispref/positions.texi b/doc/lispref/positions.texi
index 809ac207d2..7945232bf8 100644
--- a/doc/lispref/positions.texi
+++ b/doc/lispref/positions.texi
@@ -834,32 +834,6 @@ a defun.  The function @code{end-of-defun} calls this 
function instead
 of using its normal method.
 @end defvar
 
-When tree-sitter support is available (@pxref{Parsing Program
-Source}), Emacs can find the beginning and end of a function according
-to the syntax tree.
-
-@defvar treesit-defun-query
-Set this variable to a tree-sitter query that matches defun
-definitions, then @code{treesit-beginning-of-defun} and
-@code{treesit-end-of-defun} can find the beginning and end of a defun.
-
-Make sure to use a compiled query for this variable, otherwise
-@code{treesit-beginning-of-defun} and @code{treesit-end-of-defun} will
-be very slow.
-@end defvar
-
-@defun treesit-beginning-of-defun &optional arg
-This function finds the beginning of a defun according to
-@var{treesit-defun-query}.  This function is suitable for the value of
-@var{beginning-of-defun-function}.
-@end defun
-
-@defun treesit-end-of-defun &optional arg
-This function finds the end of a defun according to
-@var{treesit-defun-query}.  This function is suitable for the value of
-@var{end-of-defun-function}.
-@end defun
-
 @node Skipping Characters
 @subsection Skipping Characters
 @cindex skipping characters
diff --git a/lisp/treesit.el b/lisp/treesit.el
index 28a74657f9..2defd83dc6 100644
--- a/lisp/treesit.el
+++ b/lisp/treesit.el
@@ -203,130 +203,6 @@ one argument, the parent node."
 
 (defalias 'treesit-traverse-parent #'treesit-parent-until)
 
-(defun treesit-traverse-depth-first (node pred &optional step depth)
-  "Traverse the subtree of NODE depth-first.
-
-Traverse starting from NODE (i.e., NODE is passed to PRED).  For
-each node traversed, call PRED with the node, stop and return the
-node if PRED returns non-nil.  If STEP >= 0 or nil, go forward,
-if STEP < 0, go backward.  If no node satisfies PRED, return
-nil.
-
-DEPTH can be a positive integer or 0, meaning go DEPTH deep
-counting from NODE; or nil, meaning there is no limit."
-  (if (and (numberp depth) (<= depth 0))
-      nil
-    (if (funcall pred node)
-        node
-      (cl-loop for child in (if (or (null step) (>= step 0))
-                                (treesit-node-children node)
-                              (nreverse (treesit-node-children node)))
-               if (treesit-traverse-depth-first
-                   child pred step (if (numberp depth) (1- depth) depth))
-               return child))))
-
-(defun treesit--traverse-breadth-first-1 (pred step queue tail)
-  "The work horse for `treesit-traverse-breadth-first'.
-PRED and STEP are the same as in
-`treesit-traverse-breadth-first'.  This function simply runes BFS
-on QUEUE: pops an element from QUEUE, append children to QUEUE,
-process the element, and next iteration.  TAIL is the pointer to
-the last cons in QUEUE, used for appending elements."
-  (cl-loop while queue
-           if (funcall pred (car queue)) return (car queue)
-           else do
-           (let ((children (if (or (null step) (>= step 0))
-                               (treesit-node-children (car queue))
-                             (nreverse (treesit-node-children (car queue))))))
-             ;; Append children to the end.
-             (setcdr tail children)
-             (setq tail (last tail))
-             ;; Pop the head off.
-             (setq queue (cdr queue)))
-           finally return nil))
-
-(defun treesit-traverse-breadth-first (node pred &optional step)
-  "Traverse the subtree of NODE breadth-first.
-
-Traverse starting from NODE (i.e., NODE is passed to PRED).  For
-each node traversed, call PRED with the node, stop and return the
-node if PRED returns non-nil.  If STEP >= 0 or nil, go forward,
-if STEP < 0, go backward.  If no node satisfies PRED, return
-nil."
-  ;; Traverse with a queue.
-  (let* ((queue (list node))
-         (tail (last queue)))
-    (treesit--traverse-breadth-first-1 pred step queue tail)))
-
-(defun treesit-next-sibling-or-up (node step)
-  "Return the next sibling of NODE.
-
-If there is no next sibling of NODE but NODE has a parent, return
-the parent.  If there is no parent, return nil.  If STEP >= 0 or
-nil, return the next sibling, if STEP < 0, return the previous
-one.
-
-Return either ('sibling node) or ('parent node)."
-  ;; First deplete siblings.
-  (if-let ((sibling (if (or (null step) (>= step 0))
-                        (treesit-node-next-sibling node)
-                      (treesit-node-prev-sibling node))))
-      (list 'sibling sibling)
-    ;; When siblings depleted, go up one level.
-    (when (treesit-node-parent node)
-      (list 'parent (treesit-node-parent node)))))
-
-(defun treesit-traverse-forward (node pred &optional step depth)
-  "Traverse the whole tree forward from NODE depth-first.
-
-Traverse starting from NODE (i.e., NODE is passed to PRED).  For
-each node traversed, call PRED with the node, stop and return the
-node if PRED returns non-nil.  If STEP >= 0 or nil, go forward,
-if STEP < 0, go backward.  If no node satisfies PRED, return
-nil.
-
-Traversing forward depth-first means that for a tree like the
-below where NODE is marked 1, traverse as numbered:
-
-                16
-                |
-       3--------4-----------8
-       |        |           |
-  o--o-+--1  5--+--6    9---+-----12
-  |  |    |        |    |         |
-  o  o    2        7  +-+-+    +--+--+
-                      |   |    |  |  |
-                      10  11   13 14 15
-DEPTH can be a positive integer, 0, nil, or \\='up.  A positive
-integer or 0 means go DEPTH deep counting from NODE.  A nil means
-no limit.  And a symbol \\='up means go upwards only: only traverse
-sibling and parent, never go down to children.
-
-The difference between 0 and \\='up is subtle: in the above example,
-if given 0 as DEPTH, node 1 3 4 5 6 8 9 12 16 are visited; if
-given \\='up as DEPTH, only node 1 3 4 8 16 are visited."
-  ;; First try NODE's subtree, but only under these conditions: if
-  ;; DEPTH is a number, it has to be greater than 0, if it's a symbol,
-  ;; it cannot be 'up.
-  (or (and (if (numberp depth) (> depth 0) (not (eq depth 'up)))
-           (treesit-traverse-depth-first node pred step depth))
-      ;; If no match, try the next node: next sibling, or parent if no
-      ;; next sibling exists.
-      (catch 'match
-        (let ((next (list nil node)))
-          ;; If NEXT is parent, call PRED on it and keep going.  We
-          ;; can always go to parent, regardless the value of DEPTH.
-          (while (and (setq next (treesit-next-sibling-or-up
-                                  (cadr next) step))
-                      (eq (car next) 'parent))
-            (when (numberp depth) (cl-incf depth))
-            (when (funcall pred (cadr next))
-              (throw 'match (cadr next))))
-          (when next
-            ;; If NEXT is non-nil, it must be ('sibling node).
-            (treesit-traverse-forward
-             (cadr next) pred step depth))))))
-
 (defun treesit-node-children (node &optional named)
   "Return a list of NODE's children.
 If NAMED is non-nil, collect named child only."
@@ -846,138 +722,9 @@ indentation (target) is in green, current indentation is 
in red."
 
 ;;; Search
 
-;; TODO: It might be more performant if we implement this in C.
-(defun treesit-search-forward (pos-fn arg query &optional lang up-only)
-  "Search forward for nodes that matches QUERY from current point.
-
-QUERY has to capture the node to match.  LANG specifies the
-language in which we search for nodes.  If LANG is nil, use the
-first parser in (`treesit-parser-list').
-
-Move forward/backward ARG times, positive ARG means go forward,
-negative ARG means go backward.
-
-POS-FN can be either `treesit-node-start' or `treesit-node-end',
-or any function that takes a node and returns a position.
-
-If the search succeeds, stop at the position returned by POS-FN and
-return the matched node.  Return nil if search failed.
-
-We search by traversing the parse tree, visiting every node
-that's after (or before) the smallest node at point (retrieved by
-`treesit-node-at').  If UP-ONLY is non-nil, only go to sibling or
-parent in the tree, never go down into children when traversing
-the tree."
-  (cl-loop for idx from 1 to (abs arg)
-           for parser = (if lang
-                            (treesit-parser-create lang)
-                          (car (treesit-parser-list)))
-           for node =
-           (if-let ((starting-point (point))
-                    (node (treesit-node-at (point) parser t)))
-               (treesit-traverse-forward
-                node
-                (lambda (node)
-                  (and (not (eq (funcall pos-fn node)
-                                starting-point))
-                       (cl-loop
-                        for cap-node in
-                        (mapcar
-                         #'cdr
-                         (treesit-query-capture node query))
-                        if (and (treesit-node-eq cap-node node)
-                                (if (> arg 0)
-                                    ;; Make sure we moved forward.
-                                    (> (funcall pos-fn node)
-                                       starting-point)
-                                  ;; Make sure we moved backward.
-                                  (< (funcall pos-fn node)
-                                     starting-point)))
-                        return t)))
-                ;; The AND form converts non-nil/nil into t/nil.
-                arg (and up-only t)))
-           for pos = (funcall pos-fn node)
-           ;; If we can find a match, jump to it.
-           if pos do (goto-char pos)
-           else return nil
-           ;; Return t to indicate that search is successful.
-           finally return node))
-
-(defun treesit-search-beginning (query arg &optional lang up-only)
-  "Search forward for nodes that matches QUERY.
-
-Stops at the beginning of matched node.
-
-QUERY has to capture the node to match.  LANG specifies the
-language in which we search for nodes.  If LANG is nil, use the
-first parser in current buffer's parser list.
-
-Move forward/backward ARG times, positive ARG means go forward,
-negative ARG means go backward.
-
-If the search succeeds, return the matched node.  Return nil if
-search failed.
-
-We search by traversing the parse tree, visiting every node
-that's after (or before) the smallest node at point (retrieved by
-`treesit-node-at').  If UP-ONLY is non-nil, only go to sibling or
-parent in the tree, never go down into children when traversing
-the tree."
-  (treesit-search-forward #'treesit-node-start arg query lang
-                          up-only))
-
-(defun treesit-search-end (query arg &optional lang up-only)
-  "Search forward for nodes that matches QUERY.
-
-Stops at the end of matched node.
-
-QUERY has to capture the node to match.  LANG specifies the
-language in which we search for nodes.  If LANG is nil, use the
-first parser in (`treesit-parser-list').
-
-Move forward/backward ARG times, positive ARG means go forward,
-negative ARG means go backward.
-
-If the search succeeds, return the matched node.  Return nil if
-search failed.
-
-We search by traversing the parse tree, visiting every node
-that's after (or before) the smallest node at point (retrieved by
-`treesit-node-at').  If UP-ONLY is non-nil, only go to sibling or
-parent in the tree, never go down into children when traversing
-the tree."
-  (treesit-search-forward #'treesit-node-end arg query lang
-                          up-only))
-
-;;; Navigation
-
-(defvar-local treesit-defun-query nil
-  "A tree-sitter query that matches function/class definitions.
-Capture names don't matter.  This variable is used by navigation
-functions like `treesit-beginning-of-defun'.
-
-It is recommended to use a compiled query for this variable.  See
-`treesit-query-in' for what a query should look like.")
-
-(defun treesit-beginning-of-defun (&optional arg)
-  "Move backward to the beginning of a defun.
-
-With ARG, do it that many times.  Negative ARG means move forward
-to the ARGth following beginning of defun.  Defun is defined
-according to `treesit-defun-query'."
-  (unless treesit-defun-query
-    (error "Variable `treesit-defun-query' is unset"))
-  (treesit-search-beginning treesit-defun-query (- (or arg 1)) nil t))
-
-(defun treesit-end-of-defun (&optional arg)
-  "Move forward to the end of a defun.
-
-With ARG, do it that many times.  Negative ARG means move back to
-ARGth preceding end of defun.  Defun is defined according to
-`treesit-defun-query'."
-  (unless treesit-defun-query
-    (error "Variable `treesit-defun-query' is unset"))
-  (treesit-search-end treesit-defun-query (or arg 1) nil t))
+
+
+
 
 ;;; Debugging
 
diff --git a/test/src/treesit-tests.el b/test/src/treesit-tests.el
index aea417d47e..fbf99ff087 100644
--- a/test/src/treesit-tests.el
+++ b/test/src/treesit-tests.el
@@ -434,20 +434,12 @@ visible_end.)"
     ;; `treesit-parent-while'
     ;; `treesit-node-children'
     ;; `treesit-node-field-name'
-    ;; `treesit-next-sibling-or-up'
-    ;; `treesit-traverse-depth-first'
-    ;; `treesit-traverse-breadth-first'
-    ;; `treesit-traverse-forward-depth-first'
     ))
 
 ;; TODO
 ;; - Functions in treesit.el
 ;; - treesit-load-name-override-list
 ;; - treesit-search-forward
-;; - treesit-search-beginning
-;; - treesit-search-end
-;; - treesit-beginning-of-defun
-;; - treesit-end-of-defun
 
 (provide 'treesit-tests)
 ;;; treesit-tests.el ends here