Add improved tree-sitter navigation

This new set of functions (and tests) should eliminate
defun-navigation bugs and limitations we currently have.  This commit
doesn't change any existing bahavior: treesit-beginning/end-of-defun
and friends are unchanged.  The plan is to later switch gear and
replace the current functions with the new ones introduced in this
change.

This is a relatively big change, but I've setup a comprehensive test,
and it should fix current bugs, so I think it's ok to put it on the
release branch.

The gist of the new navigation is to use treesit--defuns-around to
find the previous sibling defun, next sibling defun, and the parent
defun, then use this information to move to previous/next
beginning/end of defun in treesit--navigate-defun.

I also added comprehensive testing that tests all four possible
operations (prev-beg, next-beg, prev-end, next-end) starting at all
possible positions (between two sibling defuns, inside a sibling
defun, etc).

* lisp/treesit.el (treesit-defun-type-regexp): Expand definition to
allow (REGEXP . FILTER).  Old functions don't support this, but it
should be fine since we are soon replacing them.

(treesit-defun-tactic)
(treesit-defun-skipper): New variables.

(treesit-default-defun-skipper)
(treesit--defuns-around)
(treesit--top-level-defun)
(treesit--navigate-defun): New functions.

* test/src/treesit-tests.el (treesit--ert-insert-and-parse-marker)
(treesit--ert-collect-positions)
(treesit--ert-test-defun-navigation): New helper functions.

(treesit--ert-defun-navigation-python-program)
(treesit--ert-defun-navigation-js-program)
(treesit--ert-defun-navigation-bash-program)
(treesit--ert-defun-navigation-nested-master): New variables.

(treesit-defun-navigation-nested-1)
(treesit-defun-navigation-nested-2)
(treesit-defun-navigation-nested-3)
(treesit-defun-navigation-top-level): New tests.

1 files changed, 282 insertions, 0 deletions

diff --git a/test/src/treesit-tests.el b/test/src/treesit-tests.el
index 188a9557928..eaf2df62104 100644
--- a/test/src/treesit-tests.el
+++ b/test/src/treesit-tests.el
@@ -607,6 +607,288 @@ visible_end.)"
     (insert "]")
     (should (treesit-node-check array-node 'outdated))))
 
+;;; Defun navigation
+;;
+;; I've setup a framework for easier testing of defun navigation.
+;;
+;; To use it for a particular langauge, first write a test program
+;; similar to `treesit--ert-defun-navigation-python-program', and
+;; insert markers.  Markers that marks BOLs are defined as follows:
+;;
+;; 100 Before 1st parent
+;; 101 Beg of 1st parent
+;; 102 End of 1st parent
+;; 103 Beg of 2nd parent
+;; 104 Beg of 1st method
+;; 105 End of 1st method
+;; 106 Beg of 2nd method
+;; 107 End of 2nd method
+;; 108 End of 2nd parent
+;; 109 Beg of 3rd parent
+;; 110 End of 3rd parent
+;; 999 Dummy markers
+;;
+;; Then add marker 0-9 following the definition given in
+;; `treesit--ert-defun-navigation-nested-master'.  Then you can use
+;; `treesit--ert-test-defun-navigation', pass the test program you
+;; just wrote, and the appropriate master:
+;;
+;; - `treesit--ert-defun-navigation-nested-master' for nested defun
+;; - `treesit--ert-defun-navigation-top-level-master' for top-level
+
+
+(defun treesit--ert-insert-and-parse-marker (opening closing text)
+  "Insert TEXT and parse the marker positions in it.
+
+TEXT should be a string in which contains position markings
+like (1).  OPENING and CLOSING are position marking's delimiters,
+for (1), OPENING and CLOSING should be \"(\" and \")\",
+respectively.
+
+This function inserts TEXT, parses and removes all the markings,
+and returns an alist of (NUMBER . POS), where number is each
+marking's number, and POS is each marking's position."
+  (declare (indent 2))
+  (let (result)
+    (insert text)
+    (goto-char (point-min))
+    (while (re-search-forward
+            (rx-to-string `(seq ,opening (group (+ digit)) ,closing))
+            nil t)
+      (let ((idx (string-to-number (match-string 1))))
+        (push (cons idx (match-beginning 0)) result)
+        (delete-region (match-beginning 0) (match-end 0))))
+    (nreverse result)))
+
+(defun treesit--ert-collect-positions (positions functions)
+  "Collect posifions after caling each function in FUNCTIONS.
+
+POSITIONS should be a list of buffer positions, FUNCTIONS should
+be a list of functions.  This function collects the return value
+of each function in FUNCTIONS starting at each position in
+POSITIONS.
+
+Return a list of (POS...) where each POS corresponds to a
+function in FUNCTIONS.  For example, if buffer content is
+\"123\", POSITIONS is (2 3), FUNCTIONS is (point-min point-max),
+the return value is ((1 3) (1 3))."
+  (cl-loop for pos in positions
+           collect (cl-loop for fn in functions
+                            collect (progn
+                                      (goto-char pos)
+                                      (funcall fn)))))
+
+(defun treesit--ert-test-defun-navigation
+    (init program master &optional opening closing)
+  "Run defun navigation tests on PROGRAM and MASTER.
+
+INIT is a setup function that runs right after this function
+creates a temporary buffer.  It should take no argument.
+
+PROGRAM is a program source in string, MASTER is a list of
+\(START PREV-BEG NEXT-END PREV-END NEXT-BEG), where START is the
+starting marker position, and the rest are marker positions the
+corresponding navigation should stop at (after running
+`treesit-defun-skipper').
+
+OPENING and CLOSING are the same as in
+`treesit--ert-insert-and-parse-marker', by default they are \"[\"
+and \"]\"."
+  (with-temp-buffer
+    (funcall init)
+    (let* ((opening (or opening "["))
+           (closing (or closing "]"))
+           ;; Insert program and parse marker positions.
+           (marker-alist (treesit--ert-insert-and-parse-marker
+                             opening closing program))
+           ;; Translate marker positions into buffer positions.
+           (decoded-master
+            (cl-loop for record in master
+                     collect
+                     (cl-loop for pos in record
+                              collect (alist-get pos marker-alist))))
+           ;; Collect positions each function returns.
+           (positions
+            (treesit--ert-collect-positions
+             ;; The first columnn of DECODED-MASTER.
+             (mapcar #'car decoded-master)
+             ;; Four functions: next-end, prev-beg, next-beg, prev-end.
+             (mapcar (lambda (conf)
+                       (lambda ()
+                         (if-let ((pos (funcall
+                                        #'treesit--navigate-defun
+                                        (point) (car conf) (cdr conf))))
+                             (save-excursion
+                               (goto-char pos)
+                               (funcall treesit-defun-skipper)
+                               (point)))))
+                     '((-1 . beg)
+                       (1 . end)
+                       (-1 . end)
+                       (1 . beg))))))
+      ;; Verify each position.
+      (cl-loop for record in decoded-master
+               for orig-record in master
+               for poss in positions
+               for name = (format "marker %d" (car orig-record))
+               do (should (equal (cons name (cdr record))
+                                 (cons name poss)))))))
+
+(defvar treesit--ert-defun-navigation-python-program
+  "[100]
+[101]class Class1():
+[999]    prop = 0
+[102]
+[103]class Class2():[0]
+[104]    [1]def method1():
+[999]        [2]return 0[3]
+[105]    [4]
+[106]    [5]def method2():
+[999]        [6]return 0[7]
+[107]    [8]
+[999]    prop = 0[9]
+[108]
+[109]class Class3():
+[999]    prop = 0[10]
+[110]
+"
+  "Python source for navigation test.")
+
+(defvar treesit--ert-defun-navigation-js-program
+  "[100]
+[101]class Class1 {
+[999]}
+[102]
+[103]class Class2 {[0]
+[104]  [1]method1() {
+[999]    [2]return 0;
+[999]  }[3]
+[105]  [4]
+[106]  [5]method2() {
+[999]    [6]return 0;
+[999]  }[7]
+[107][8]
+[999]}[9]
+[108]
+[109]class class3 {
+[999]}[10]
+[110]
+"
+  "Javascript source for navigation test.")
+
+(defvar treesit--ert-defun-navigation-bash-program
+  "[100]
+[101]parent1 () {
+[999]}
+[102]
+[103]parent2 () {[0]
+[104]    [1]sibling1 () {
+[999]        [2]echo hi
+[999]    }[3]
+[105]    [4]
+[106]    [5]sibling2 () {
+[999]        [6]echo hi
+[999]    }[7]
+[107][8]
+[999]}[9]
+[108]
+[109]parent3 () {
+[999]}
+[110]
+"
+  "Javascript source for navigation test.")
+
+(defvar treesit--ert-defun-navigation-nested-master
+  ;; START PREV-BEG NEXT-END PREV-END NEXT-BEG
+  '((0 103 105 102 106) ; Between Beg of parent & 1st sibling.
+    (1 103 105 102 106) ; Beg of 1st sibling.
+    (2 104 105 102 106) ; Inside 1st sibling.
+    (3 104 107 102 109) ; End of 1st sibling.
+    (4 104 107 102 109) ; Between 1st sibling & 2nd sibling.
+    (5 104 107 102 109) ; Beg of 2nd sibling.
+    (6 106 107 105 109) ; Inside 2nd sibling.
+    (7 106 108 105 109) ; End of 2nd sibling.
+    (8 106 108 105 109) ; Between 2nd sibling & end of parent.
+    (9 103 110 102 nil) ; End of parent.
+
+    (100 nil 102 nil 103) ; Before 1st parent.
+    (101 nil 102 nil 103) ; Beg of 1st parent.
+    (102 101 108 nil 109) ; Between 1st & 2nd parent.
+    (103 101 108 nil 109) ; Beg of 2nd parent.
+    (110 109 nil 108 nil) ; After 3rd parent.
+    )
+  "Master of nested navigation test.
+
+This basically says, e.g., \"start with point on marker 0, go to
+the prev-beg, now point should be at marker 103\", etc.")
+
+(defvar treesit--ert-defun-navigation-top-level-master
+  ;; START PREV-BEG NEXT-END NEXT-BEG PREV-END
+  '((0 103 108 102 109) ; Between Beg of parent & 1st sibling.
+    (1 103 108 102 109) ; Beg of 1st sibling.
+    (2 103 108 102 109) ; Inside 1st sibling.
+    (3 103 108 102 109) ; End of 1st sibling.
+    (4 103 108 102 109) ; Between 1st sibling & 2nd sibling.
+    (5 103 108 102 109) ; Beg of 2nd sibling.
+    (6 103 108 102 109) ; Inside 2nd sibling.
+    (7 103 108 102 109) ; End of 2nd sibling.
+    (8 103 108 102 109) ; Between 2nd sibling & end of parent.
+    (9 103 110 102 nil) ; End of parent.
+
+    ;; Top-level defuns should be identical to the nested test.
+    (100 nil 102 nil 103) ; Before 1st parent.
+    (101 nil 102 nil 103) ; Beg of 1st parent.
+    (102 101 108 nil 109) ; Between 1st & 2nd parent.
+    (103 101 108 nil 109) ; Beg of 2nd parent.
+    (110 109 nil 108 nil) ; After 3rd parent.
+    )
+  "Master of top-level navigation test.")
+
+(ert-deftest treesit-defun-navigation-nested-1 ()
+  "Test defun navigation."
+  (skip-unless (treesit-language-available-p 'python))
+  ;; Nested defun navigation
+  (let ((treesit-defun-tactic 'nested))
+    (require 'python)
+    (treesit--ert-test-defun-navigation
+     'python-ts-mode
+     treesit--ert-defun-navigation-python-program
+     treesit--ert-defun-navigation-nested-master)))
+
+(ert-deftest treesit-defun-navigation-nested-2 ()
+  "Test defun navigation using `js-ts-mode'."
+  (skip-unless (treesit-language-available-p 'javascript))
+  ;; Nested defun navigation
+  (let ((treesit-defun-tactic 'nested))
+    (require 'js)
+    (treesit--ert-test-defun-navigation
+     'js-ts-mode
+     treesit--ert-defun-navigation-js-program
+     treesit--ert-defun-navigation-nested-master)))
+
+(ert-deftest treesit-defun-navigation-nested-3 ()
+  "Test defun navigation using `bash-ts-mode'."
+  (skip-unless (treesit-language-available-p 'bash))
+  ;; Nested defun navigation
+  (let ((treesit-defun-tactic 'nested))
+    (treesit--ert-test-defun-navigation
+     (lambda ()
+       (treesit-parser-create 'bash)
+       (setq-local treesit-defun-type-regexp "function_definition"))
+     treesit--ert-defun-navigation-bash-program
+     treesit--ert-defun-navigation-nested-master)))
+
+(ert-deftest treesit-defun-navigation-top-level ()
+  "Test top-level only defun navigation."
+  (skip-unless (treesit-language-available-p 'python))
+  ;; Nested defun navigation
+  (let ((treesit-defun-tactic 'top-level))
+    (require 'python)
+    (treesit--ert-test-defun-navigation
+     'python-ts-mode
+     treesit--ert-defun-navigation-python-program
+     treesit--ert-defun-navigation-top-level-master)))
+
 ;; TODO
 ;; - Functions in treesit.el
 ;; - treesit-load-name-override-list