Re: How to add pseudo vector types

[Yuan Fu <casouri@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 2070 bytes --]

I wrote a simple interface between font-lock and tree-sitter, and it works pretty well: using tree-sitter for fontification, xdisp.c opens a lot faster, and scrolling through the buffer is also perceivably faster. My simple interface works like this: tree-sitter allow you to “pattern match” nodes in the parse tree with a DSL, and assign names to the matched nodes, e.g., given a pattern, you get back a list of (NAME . MATCHED-NODE). And if we use font-lock faces as names for those nodes, we get back a list of (FACE . MATCHED-NODE) from tree-sitter, and Emacs can simply look at the beginning and end of the node, and apply FACE to that range. For flexibility, FACE can also be a function, in which case the function is called with the node. This interface is basically what emacs-tree-sitter does (I don’t know if they allow a capture name to be a function, though.)

I have an example major-mode for C that uses tree-sitter for font-locking at the end of tree-sitter.el. 

Main functions to look at: tree-sitter-query-capture in tree_sitter.c, and tree-sitter-fontify-region-function in tree-sitter.el.

On the font-lock front, tree-sitter-fontify-region-function replaces font-lock-default-fontify-region, and tree-sitter-font-lock-settings replaces font-lock-defaults and font-lock-keywords. I should support font-lock-maximum-decoration but haven’t came up with a good way to do that. Maybe I should somehow reuse font-lock-defaults, and make it able to configure for tree-sitter font-locking? Apart from font-lock-maximum-decoration, what else should tree-sitter share with font-lock?

BTW, what is the best way to signal a lisp error from C? I tried xsignal2, signal_error, error and friends but they seem to crash Emacs. Maybe I wasn’t using them correctly.

IIUC if we want tree-sitter to use our malloc, we need to build it with Emacs, where should I put the source of tree-sitter?

What’s the different between make_string and make_pure_c_string? I’ve seen this “pure” thing else where, what does “pure” mean?

Yuan


[-- Attachment #2: ts.4.patch --]
[-- Type: application/octet-stream, Size: 36844 bytes --]

From d28e10e5905d244d92b71b74566c0bed80d5ed2b Mon Sep 17 00:00:00 2001
From: Yuan Fu <casouri@gmail.com>
Date: Sat, 24 Jul 2021 10:39:15 -0400
Subject: [PATCH] checkpoint 4

- Add font-locking
- Remove change-recording from replace_range_2, add to casify_region
---
 lisp/emacs-lisp/cl-preloaded.el |   2 +
 lisp/tree-sitter.el             | 276 ++++++++++++++++++++++++++
 src/casefiddle.c                |  12 ++
 src/insdel.c                    |  11 +-
 src/tree_sitter.c               | 332 +++++++++++++++++++++++++++++---
 src/tree_sitter.h               |   4 +-
 test/src/tree-sitter-tests.el   |  58 +++++-
 7 files changed, 655 insertions(+), 40 deletions(-)
 create mode 100644 lisp/tree-sitter.el

diff --git a/lisp/emacs-lisp/cl-preloaded.el b/lisp/emacs-lisp/cl-preloaded.el
index 7365e23186..2dccdff91a 100644
--- a/lisp/emacs-lisp/cl-preloaded.el
+++ b/lisp/emacs-lisp/cl-preloaded.el
@@ -68,6 +68,8 @@ cl--typeof-types
     (font-spec atom) (font-entity atom) (font-object atom)
     (vector array sequence atom)
     (user-ptr atom)
+    (tree-sitter-parser atom)
+    (tree-sitter-node atom)
     ;; Plus, really hand made:
     (null symbol list sequence atom))
   "Alist of supertypes.
diff --git a/lisp/tree-sitter.el b/lisp/tree-sitter.el
new file mode 100644
index 0000000000..a6ecb09386
--- /dev/null
+++ b/lisp/tree-sitter.el
@@ -0,0 +1,276 @@
+;;; tree-sitter.el --- tree-sitter utilities -*- lexical-binding: t -*-
+
+;; Copyright (C) 2021 Free Software Foundation, Inc.
+
+;; This file is part of GNU Emacs.
+
+;; GNU Emacs 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.
+
+;; GNU Emacs 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 GNU Emacs.  If not, see <https://www.gnu.org/licenses/>.
+
+;;; Commentary:
+
+;;; Code:
+
+;;; Node & parser accessors
+
+(defun tree-sitter-node-buffer (node)
+  "Return the buffer in where NODE belongs."
+  (tree-sitter-parser-buffer
+   (tree-sitter-node-parser node)))
+
+;;; Parser API supplement
+
+(defun tree-sitter-get-parser (name)
+  "Find the first parser with name NAME in `tree-sitter-parser-list'.
+Return nil if we can't find any."
+  (catch 'found
+    (dolist (parser tree-sitter-parser-list)
+      (when (equal name (tree-sitter-parser-name parser))
+        (throw 'found parser)))))
+
+(defun tree-sitter-get-parser-create (name language)
+  "Find the first parser with name NAME in `tree-sitter-parser-list'.
+If none exists, create one and return it.  LANGUAGE is passed to
+`tree-sitter-create-parser' when creating the parser."
+  (or (tree-sitter-get-parser name)
+      (tree-sitter-create-parser (current-buffer) language name)))
+
+;;; Node API supplement
+
+(defun tree-sitter-node-beginning (node)
+  "Return the start position of NODE."
+  (byte-to-position (tree-sitter-node-start-byte node)))
+
+(defun tree-sitter-node-end (node)
+  "Return the end position of NODE."
+  (byte-to-position (tree-sitter-node-end-byte node)))
+
+(defun tree-sitter-node-in-range (beg end &optional parser-name named)
+  "Return the smallest node covering BEG to END.
+Find node in current buffer.  Return nil if none find.  If NAMED
+non-nil, only look for named node.  NAMED defaults to nil.  By
+default, use the first parser in `tree-sitter-parser-list'; but
+if PARSER-NAME is non-nil, it specifies the name of the parser that
+should be used."
+  (when-let ((root (tree-sitter-parser-root-node
+                    (if parser-name
+                        (tree-sitter-get-parser parser-name)
+                      (car tree-sitter-parser-list)))))
+    (tree-sitter-node-descendant-for-byte-range
+     root (position-bytes beg) (position-bytes end) named)))
+
+(defun tree-sitter-filter-child (node pred &optional named)
+  "Return children of NODE that satisfies PRED.
+PRED is a function that takes one argument, the child node.  If
+NAMED non-nil, only search named node.  NAMED defaults to nil."
+  (let ((child (tree-sitter-node-child node 0 named))
+        result)
+    (while child
+      (when (funcall pred child)
+        (push child result))
+      (setq child (tree-sitter-node-next-sibling child named)))
+    result))
+
+(defun tree-sitter-node-content (node)
+  "Return the buffer content corresponding to NODE."
+  (with-current-buffer (tree-sitter-node-buffer node)
+    (buffer-substring-no-properties
+     (tree-sitter-node-beginning node)
+     (tree-sitter-node-end node))))
+
+;;; Font-lock
+
+(defvar-local tree-sitter-font-lock-settings nil
+  "A list of settings for tree-sitter-based font-locking.
+
+Each setting controls one parser (often of different language).
+A settings is a list of form (NAME LANGUAGE PATTERN).  NAME is
+the name given to the parser, by convention it is
+\"font-lock-<language>\", where <language> is the language that
+the parser uses.  LANGUAGE is the language object returned by
+tree-sitter language dynamic modules.
+
+PATTERN is a tree-sitter query pattern. (See manual for how to
+write query patterns.)  This pattern should capture nodes with
+either face names or function names.  If captured with a face
+name, the node's corresponding text in the buffer is fontified
+with that face; if captured with a function name, the function is
+called with three arguments, BEG END NODE, where BEG and END
+marks the span of the corresponding text, and NODE is the node
+itself.")
+
+(defun tree-sitter-fontify-region-function (beg end &optional verbose)
+  "Fontify the region between BEG and END.
+If VERBOSE is non-nil, print status messages.
+\(See `font-lock-fontify-region-function'.)"
+  (dolist (elm tree-sitter-font-lock-settings)
+    (let ((parser-name (car elm))
+          (language (nth 1 elm))
+          (match-pattern (nth 2 elm)))
+      (tree-sitter-get-parser-create parser-name language)
+      (when-let ((node (tree-sitter-node-in-range beg end parser-name)))
+        (let ((captures (tree-sitter-query-capture
+                         node match-pattern
+                         ;; specifying the range is important. More
+                         ;; often than not, NODE will be the root
+                         ;; node, and if we don't specify the range,
+                         ;; we are basically querying the whole file.
+                         (position-bytes beg) (position-bytes end))))
+          (with-silent-modifications
+            (while captures
+              (let* ((face (caar captures))
+                     (node (cdar captures))
+                     (beg (tree-sitter-node-beginning node))
+                     (end (tree-sitter-node-end node)))
+                (cond ((facep face)
+                       (put-text-property beg end 'face face))
+                      ((functionp face)
+                       (funcall face beg end node)))
+
+                (if verbose
+                    (message "Fontifying text from %d to %d with %s"
+                             beg end face)))
+              (setq captures (cdr captures))))
+          `(jit-lock-bounds ,(tree-sitter-node-beginning node)
+                            . ,(tree-sitter-node-end node)))))))
+
+
+(define-derived-mode json-mode js-mode "JSON"
+  "Major mode for JSON documents."
+  (setq-local font-lock-fontify-region-function
+              #'tree-sitter-fontify-region-function)
+  (setq-local tree-sitter-font-lock-settings
+              `(("font-lock-json"
+                 ,(tree-sitter-json)
+                 "(string) @font-lock-string-face
+(true) @font-lock-constant-face
+(false) @font-lock-constant-face
+(null) @font-lock-constant-face"))))
+
+(defun ts-c-fontify-system-lib (beg end _)
+  (put-text-property beg (1+ beg) 'face 'font-lock-preprocessor-face)
+  (put-text-property (1- end) end 'face 'font-lock-preprocessor-face)
+  (put-text-property (1+ beg) (1- end)
+                     'face 'font-lock-string-face))
+
+(define-derived-mode ts-c-mode prog-mode "TS C"
+  "C mode with tree-sitter support."
+  (setq-local font-lock-fontify-region-function
+              #'tree-sitter-fontify-region-function)
+  (setq-local tree-sitter-font-lock-settings
+              `(("font-lock-c"
+                 ,(tree-sitter-c)
+                 "(null) @font-lock-constant-face
+(true) @font-lock-constant-face
+(false) @font-lock-constant-face
+
+(comment) @font-lock-comment-face
+
+(system_lib_string) @ts-c-fontify-system-lib
+
+(unary_expression
+  operator: _ @font-lock-negation-char-face)
+
+(string_literal) @font-lock-string-face
+(char_literal) @font-lock-string-face
+
+
+
+(function_definition
+  declarator: (identifier) @font-lock-function-name-face)
+
+(declaration
+  declarator: (identifier) @font-lock-function-name-face)
+
+(function_declarator
+ declarator: (identifier) @font-lock-function-name-face)
+
+
+
+(init_declarator
+ declarator: (identifier) @font-lock-variable-name-face)
+
+(parameter_declaration
+ declarator: (identifier) @font-lock-variable-name-face)
+
+(preproc_def
+ name: (identifier) @font-lock-variable-name-face)
+
+(enumerator
+ name: (identifier) @font-lock-variable-name-face)
+
+(field_identifier) @font-lock-variable-name-face
+
+(parameter_list
+ (parameter_declaration
+  (identifier) @font-lock-variable-name-face))
+
+(pointer_declarator
+ declarator: (identifier) @font-lock-variable-name-face)
+
+(array_declarator
+ declarator: (identifier) @font-lock-variable-name-face)
+
+(preproc_function_def
+ name: (identifier) @font-lock-variable-name-face
+ parameters: (preproc_params
+              (identifier) @font-lock-variable-name-face))
+
+
+
+(type_identifier) @font-lock-type-face
+(primitive_type) @font-lock-type-face
+
+\"auto\" @font-lock-keyword-face
+\"break\" @font-lock-keyword-face
+\"case\" @font-lock-keyword-face
+\"const\" @font-lock-keyword-face
+\"continue\" @font-lock-keyword-face
+\"default\" @font-lock-keyword-face
+\"do\" @font-lock-keyword-face
+\"else\" @font-lock-keyword-face
+\"enum\" @font-lock-keyword-face
+\"extern\" @font-lock-keyword-face
+\"for\" @font-lock-keyword-face
+\"goto\" @font-lock-keyword-face
+\"if\" @font-lock-keyword-face
+\"register\" @font-lock-keyword-face
+\"return\" @font-lock-keyword-face
+\"sizeof\" @font-lock-keyword-face
+\"static\" @font-lock-keyword-face
+\"struct\" @font-lock-keyword-face
+\"switch\" @font-lock-keyword-face
+\"typedef\" @font-lock-keyword-face
+\"union\" @font-lock-keyword-face
+\"volatile\" @font-lock-keyword-face
+\"while\" @font-lock-keyword-face
+
+\"long\" @font-lock-type-face
+\"short\" @font-lock-type-face
+\"signed\" @font-lock-type-face
+\"unsigned\" @font-lock-type-face
+
+\"#include\" @font-lock-preprocessor-face
+\"#define\" @font-lock-preprocessor-face
+\"#ifdef\" @font-lock-preprocessor-face
+\"#ifndef\" @font-lock-preprocessor-face
+\"#endif\" @font-lock-preprocessor-face
+\"#else\" @font-lock-preprocessor-face
+\"#elif\" @font-lock-preprocessor-face"))))
+
+(add-to-list 'auto-mode-alist '("\\.json\\'" . json-mode))
+(add-to-list 'auto-mode-alist '("\\.tsc\\'" . ts-c-mode))
+
+(provide 'tree-sitter)
+
+;;; tree-sitter.el ends here
diff --git a/src/casefiddle.c b/src/casefiddle.c
index a7a2541490..42cd2fdd28 100644
--- a/src/casefiddle.c
+++ b/src/casefiddle.c
@@ -30,6 +30,10 @@ Copyright (C) 1985, 1994, 1997-1999, 2001-2021 Free Software Foundation,
 #include "composite.h"
 #include "keymap.h"
 
+#ifdef HAVE_TREE_SITTER
+#include "tree_sitter.h"
+#endif
+
 enum case_action {CASE_UP, CASE_DOWN, CASE_CAPITALIZE, CASE_CAPITALIZE_UP};
 
 /* State for casing individual characters.  */
@@ -495,6 +499,11 @@ casify_region (enum case_action flag, Lisp_Object b, Lisp_Object e)
   modify_text (start, end);
   prepare_casing_context (&ctx, flag, true);
 
+#ifdef HAVE_TREE_SITTER
+  ptrdiff_t start_byte = CHAR_TO_BYTE (start);
+  ptrdiff_t old_end_byte = CHAR_TO_BYTE (end);
+#endif
+
   ptrdiff_t orig_end = end;
   record_delete (start, make_buffer_string (start, end, true), false);
   if (NILP (BVAR (current_buffer, enable_multibyte_characters)))
@@ -513,6 +522,9 @@ casify_region (enum case_action flag, Lisp_Object b, Lisp_Object e)
     {
       signal_after_change (start, end - start - added, end - start);
       update_compositions (start, end, CHECK_ALL);
+#ifdef HAVE_TREE_SITTER
+      ts_record_change (start_byte, old_end_byte, CHAR_TO_BYTE (end));
+#endif
     }
 
   return orig_end + added;
diff --git a/src/insdel.c b/src/insdel.c
index b313c50cda..3dfc281b49 100644
--- a/src/insdel.c
+++ b/src/insdel.c
@@ -1592,7 +1592,11 @@ replace_range (ptrdiff_t from, ptrdiff_t to, Lisp_Object new,
    If MARKERS, relocate markers.
 
    Unlike most functions at this level, never call
-   prepare_to_modify_buffer and never call signal_after_change.  */
+   prepare_to_modify_buffer and never call signal_after_change.
+   Because this function is called in a loop, one character at a time.
+   The caller of 'replace_range_2' calls these hooks for the entire
+   region once.  Apart from signal_after_change, any caller of this
+   function should also call ts_record_change.  */
 
 void
 replace_range_2 (ptrdiff_t from, ptrdiff_t from_byte,
@@ -1705,11 +1709,6 @@ replace_range_2 (ptrdiff_t from, ptrdiff_t from_byte,
 
   modiff_incr (&MODIFF);
   CHARS_MODIFF = MODIFF;
-
-#ifdef HAVE_TREE_SITTER
-  ts_record_change (from_byte, to_byte, from_byte + insbytes);
-#endif
-
 }
 \f
 /* Delete characters in current buffer
diff --git a/src/tree_sitter.c b/src/tree_sitter.c
index a6a8912c84..e9f8ddc7e3 100644
--- a/src/tree_sitter.c
+++ b/src/tree_sitter.c
@@ -35,6 +35,8 @@ Copyright (C) 2021 Free Software Foundation, Inc.
 /* parser.h defines a macro ADVANCE that conflicts with alloc.c.  */
 #include <tree_sitter/parser.h>
 
+/*** Functions related to parser and node object.  */
+
 DEFUN ("tree-sitter-parser-p",
        Ftree_sitter_parser_p, Stree_sitter_parser_p, 1, 1, 0,
        doc: /* Return t if OBJECT is a tree-sitter parser.  */)
@@ -57,6 +59,8 @@ DEFUN ("tree-sitter-node-p",
     return Qnil;
 }
 
+/*** Parsing functions */
+
 /* Update each parser's tree after the user made an edit.  This
 function does not parse the buffer and only updates the tree. (So it
 should be very fast.)  */
@@ -77,7 +81,6 @@ ts_record_change (ptrdiff_t start_byte, ptrdiff_t old_end_byte,
       XTS_PARSER (lisp_parser)->need_reparse = true;
       parser_list = Fcdr (parser_list);
     }
-
 }
 
 /* Parse the buffer.  We don't parse until we have to. When we have
@@ -91,9 +94,19 @@ ts_ensure_parsed (Lisp_Object parser)
   TSTree *tree = XTS_PARSER(parser)->tree;
   TSInput input = XTS_PARSER (parser)->input;
   TSTree *new_tree = ts_parser_parse(ts_parser, tree, input);
+  /* This should be very rare: it only happens when 1) language is not
+     set (impossible in Emacs because the user has to supply a
+     language to create a parser), 2) parse canceled due to timeout
+     (impossible because we don't set a timeout), 3) parse canceled
+     due to cancellation flag (impossible because we don't set the
+     flag).  (See comments for ts_parser_parse in
+     tree_sitter/api.h.)  */
+  if (new_tree == NULL)
+    signal_error ("Parse failed", parser);
   ts_tree_delete (tree);
   XTS_PARSER (parser)->tree = new_tree;
   XTS_PARSER (parser)->need_reparse = false;
+  TSNode node = ts_tree_root_node (new_tree);
 }
 
 /* This is the read function provided to tree-sitter to read from a
@@ -103,9 +116,6 @@ ts_ensure_parsed (Lisp_Object parser)
 ts_read_buffer (void *buffer, uint32_t byte_index,
 		TSPoint position, uint32_t *bytes_read)
 {
-  if (!BUFFER_LIVE_P ((struct buffer *) buffer))
-    error ("BUFFER is not live");
-
   ptrdiff_t byte_pos = byte_index + 1;
 
   /* Read one character.  Tree-sitter wants us to set bytes_read to 0
@@ -114,8 +124,17 @@ ts_read_buffer (void *buffer, uint32_t byte_index,
      string.  */
   char *beg;
   int len;
+  /* This function could run from a user command, so it is better to
+     do nothing instead of raising an error. (It was a pain in the a**
+     to read mega-if-conditions in Emacs source, so I write the two
+     branches separately, hoping the compiler can merge them.)  */
+  if (!BUFFER_LIVE_P ((struct buffer *) buffer))
+    {
+      beg = "";
+      len = 0;
+    }
   // TODO BUF_ZV_BYTE?
-  if (byte_pos >= BUF_Z_BYTE ((struct buffer *) buffer))
+  else if (byte_pos >= BUF_Z_BYTE ((struct buffer *) buffer))
     {
       beg = "";
       len = 0;
@@ -123,19 +142,23 @@ ts_read_buffer (void *buffer, uint32_t byte_index,
   else
     {
       beg = (char *) BUF_BYTE_ADDRESS (buffer, byte_pos);
-      len = next_char_len(byte_pos);
+      len = BYTES_BY_CHAR_HEAD ((int) beg);
     }
   *bytes_read = (uint32_t) len;
 
   return beg;
 }
 
+/*** Creators and accessors for parser and node */
+
 /* Wrap the parser in a Lisp_Object to be used in the Lisp machine.  */
 Lisp_Object
-make_ts_parser (struct buffer *buffer, TSParser *parser, TSTree *tree)
+make_ts_parser (struct buffer *buffer, TSParser *parser,
+		TSTree *tree, Lisp_Object name)
 {
   struct Lisp_TS_Parser *lisp_parser
-    = ALLOCATE_PLAIN_PSEUDOVECTOR (struct Lisp_TS_Parser, PVEC_TS_PARSER);
+    = ALLOCATE_PSEUDOVECTOR (struct Lisp_TS_Parser, name, PVEC_TS_PARSER);
+  lisp_parser->name = name;
   lisp_parser->buffer = buffer;
   lisp_parser->parser = parser;
   lisp_parser->tree = tree;
@@ -156,17 +179,35 @@ make_ts_node (Lisp_Object parser, TSNode node)
   return make_lisp_ptr (lisp_node, Lisp_Vectorlike);
 }
 
+DEFUN ("tree-sitter-node-parser",
+       Ftree_sitter_node_parser, Stree_sitter_node_parser,
+       1, 1, 0,
+       doc: /* Return the parser to which NODE belongs.  */)
+  (Lisp_Object node)
+{
+  CHECK_TS_NODE (node);
+  return XTS_NODE (node)->parser;
+}
 
 DEFUN ("tree-sitter-create-parser",
        Ftree_sitter_create_parser, Stree_sitter_create_parser,
-       2, 2, 0,
+       2, 3, 0,
        doc: /* Create and return a parser in BUFFER for LANGUAGE.
+
 The parser is automatically added to BUFFER's
 `tree-sitter-parser-list'.  LANGUAGE should be the language provided
-by a tree-sitter language dynamic module.  */)
-  (Lisp_Object buffer, Lisp_Object language)
+by a tree-sitter language dynamic module.
+
+NAME (a string) is the name assigned to the parser, like the name for
+a process.  Unlike process names, not care is taken to make each
+parser's name unique.  By default, no name is assigned to the parser;
+the only consequence of that is you can't use
+`tree-sitter-get-parser' to find the parser by its name.  */)
+  (Lisp_Object buffer, Lisp_Object language, Lisp_Object name)
 {
   CHECK_BUFFER(buffer);
+  if (!NILP (name))
+    CHECK_STRING (name);
 
   /* LANGUAGE is a USER_PTR that contains the pointer to a TSLanguage
      struct.  */
@@ -175,9 +216,8 @@ DEFUN ("tree-sitter-create-parser",
   ts_parser_set_language (parser, lang);
 
   Lisp_Object lisp_parser
-    = make_ts_parser (XBUFFER(buffer), parser, NULL);
+    = make_ts_parser (XBUFFER(buffer), parser, NULL, name);
 
-  // FIXME: Is this the correct way to set a buffer-local variable?
   struct buffer *old_buffer = current_buffer;
   set_buffer_internal (XBUFFER (buffer));
 
@@ -188,6 +228,30 @@ DEFUN ("tree-sitter-create-parser",
   return lisp_parser;
 }
 
+DEFUN ("tree-sitter-parser-buffer",
+       Ftree_sitter_parser_buffer, Stree_sitter_parser_buffer,
+       1, 1, 0,
+       doc: /* Return the buffer of PARSER.  */)
+  (Lisp_Object parser)
+{
+  CHECK_TS_PARSER (parser);
+  Lisp_Object buf;
+  XSETBUFFER (buf, XTS_PARSER (parser)->buffer);
+  return buf;
+}
+
+DEFUN ("tree-sitter-parser-name",
+       Ftree_sitter_parser_name, Stree_sitter_parser_name,
+       1, 1, 0,
+       doc: /* Return parser's name.  */)
+  (Lisp_Object parser)
+{
+  CHECK_TS_PARSER (parser);
+  return XTS_PARSER (parser)->name;
+}
+
+/*** Parser API */
+
 DEFUN ("tree-sitter-parser-root-node",
        Ftree_sitter_parser_root_node, Stree_sitter_parser_root_node,
        1, 1, 0,
@@ -200,7 +264,8 @@ DEFUN ("tree-sitter-parser-root-node",
   return make_ts_node (parser, root_node);
 }
 
-DEFUN ("tree-sitter-parse", Ftree_sitter_parse, Stree_sitter_parse,
+DEFUN ("tree-sitter-parse-string",
+       Ftree_sitter_parse_string, Stree_sitter_parse_string,
        2, 2, 0,
        doc: /* Parse STRING and return the root node.
 LANGUAGE should be the language provided by a tree-sitter language
@@ -219,23 +284,20 @@ DEFUN ("tree-sitter-parse", Ftree_sitter_parse, Stree_sitter_parse,
 					 SSDATA (string),
 					 strlen (SSDATA (string)));
 
-  /* See comment for ts_parser_parse in tree_sitter/api.h
-     for possible reasons for a failure.  */
+  /* See comment in ts_ensure_parsed for possible reasons for a
+     failure.  */
   if (tree == NULL)
     signal_error ("Failed to parse STRING", string);
 
   TSNode root_node = ts_tree_root_node (tree);
 
-  Lisp_Object lisp_parser = make_ts_parser (NULL, parser, tree);
+  Lisp_Object lisp_parser = make_ts_parser (NULL, parser, tree, Qnil);
   Lisp_Object lisp_node = make_ts_node (lisp_parser, root_node);
 
   return lisp_node;
 }
 
-/* Below this point are uninteresting mechanical translations of
-   tree-sitter API.  */
-
-/* Node functions.  */
+/*** Node API  */
 
 DEFUN ("tree-sitter-node-type",
        Ftree_sitter_node_type, Stree_sitter_node_type, 1, 1, 0,
@@ -245,9 +307,31 @@ DEFUN ("tree-sitter-node-type",
   CHECK_TS_NODE (node);
   TSNode ts_node = XTS_NODE (node)->node;
   const char *type = ts_node_type(ts_node);
+  // TODO: Maybe return a string instead.
   return intern_c_string (type);
 }
 
+DEFUN ("tree-sitter-node-start-byte",
+       Ftree_sitter_node_start_byte, Stree_sitter_node_start_byte, 1, 1, 0,
+       doc: /* Return the NODE's start byte position.  */)
+  (Lisp_Object node)
+{
+  CHECK_TS_NODE (node);
+  TSNode ts_node = XTS_NODE (node)->node;
+  uint32_t start_byte = ts_node_start_byte(ts_node);
+  return make_fixnum(start_byte + 1);
+}
+
+DEFUN ("tree-sitter-node-end-byte",
+       Ftree_sitter_node_end_byte, Stree_sitter_node_end_byte, 1, 1, 0,
+       doc: /* Return the NODE's end byte position.  */)
+  (Lisp_Object node)
+{
+  CHECK_TS_NODE (node);
+  TSNode ts_node = XTS_NODE (node)->node;
+  uint32_t end_byte = ts_node_end_byte(ts_node);
+  return make_fixnum(end_byte + 1);
+}
 
 DEFUN ("tree-sitter-node-string",
        Ftree_sitter_node_string, Stree_sitter_node_string, 1, 1, 0,
@@ -303,9 +387,9 @@ DEFUN ("tree-sitter-node-check",
        Ftree_sitter_node_check, Stree_sitter_node_check, 2, 2, 0,
        doc: /* Return non-nil if NODE is in condition COND, nil otherwise.
 
-COND could be 'named, 'missing, 'extra, 'has-error.  Named nodes
-correspond to named rules in the grammar, whereas "anonymous" nodes
-correspond to string literals in the grammar.
+COND could be 'named, 'missing, 'extra, 'has-changes, 'has-error.
+Named nodes correspond to named rules in the grammar, whereas
+"anonymous" nodes correspond to string literals in the grammar.
 
 Missing nodes are inserted by the parser in order to recover from
 certain kinds of syntax errors, i.e., should be there but not there.
@@ -313,6 +397,9 @@ DEFUN ("tree-sitter-node-check",
 Extra nodes represent things like comments, which are not required the
 grammar, but can appear anywhere.
 
+A node "has changes" if the buffer changed since the node is
+created. (Don't forget the "s" at the end of 'has-changes.)
+
 A node "has error" if itself is a syntax error or contains any syntax
 errors.  */)
   (Lisp_Object node, Lisp_Object cond)
@@ -329,7 +416,10 @@ DEFUN ("tree-sitter-node-check",
     result = ts_node_is_extra (ts_node);
   else if (EQ (cond, Qhas_error))
     result = ts_node_has_error (ts_node);
+  else if (EQ (cond, Qhas_changes))
+    result = ts_node_has_changes (ts_node);
   else
+    // TODO: Is this a good error message?
     signal_error ("Expecting one of four symbols, see docstring", cond);
   return result ? Qt : Qnil;
 }
@@ -432,8 +522,177 @@ DEFUN ("tree-sitter-node-prev-sibling",
   return make_ts_node(XTS_NODE (node)->parser, sibling);
 }
 
+DEFUN ("tree-sitter-node-first-child-for-byte",
+       Ftree_sitter_node_first_child_for_byte,
+       Stree_sitter_node_first_child_for_byte, 2, 3, 0,
+       doc: /* Return the first child of NODE on POS.
+Specifically, return the first child that extends beyond POS.  POS is
+a byte position in the buffer counting from 1.  Return nil if there
+isn't any.  If NAMED is non-nil, look for named child only.  NAMED
+defaults to nil.  Note that this function returns an immediate child,
+not the smallest (grand)child.  */)
+  (Lisp_Object node, Lisp_Object pos, Lisp_Object named)
+{
+  CHECK_INTEGER (pos);
+
+  struct buffer *buf = (XTS_PARSER (XTS_NODE (node)->parser)->buffer);
+  ptrdiff_t byte_pos = XFIXNUM (pos);
+
+  if (byte_pos < BUF_BEGV_BYTE (buf) || byte_pos > BUF_ZV_BYTE (buf))
+    xsignal1 (Qargs_out_of_range, pos);
+
+  TSNode ts_node = XTS_NODE (node)->node;
+  TSNode child;
+  if (NILP (named))
+    child = ts_node_first_child_for_byte (ts_node, byte_pos - 1);
+  else
+    child = ts_node_first_named_child_for_byte (ts_node, byte_pos - 1);
+
+  if (ts_node_is_null(child))
+    return Qnil;
+
+  return make_ts_node(XTS_NODE (node)->parser, child);
+}
+
+DEFUN ("tree-sitter-node-descendant-for-byte-range",
+       Ftree_sitter_node_descendant_for_byte_range,
+       Stree_sitter_node_descendant_for_byte_range, 3, 4, 0,
+       doc: /* Return the smallest node that covers BEG to END.
+The returned node is a descendant of NODE.  POS is a byte position
+counting from 1.  Return nil if there isn't any.  If NAMED is non-nil,
+look for named child only.  NAMED defaults to nil.  */)
+  (Lisp_Object node, Lisp_Object beg, Lisp_Object end, Lisp_Object named)
+{
+  CHECK_INTEGER (beg);
+  CHECK_INTEGER (end);
+
+  struct buffer *buf = (XTS_PARSER (XTS_NODE (node)->parser)->buffer);
+  ptrdiff_t byte_beg = XFIXNUM (beg);
+  ptrdiff_t byte_end = XFIXNUM (end);
+
+  /* Checks for BUFFER_BEG <= BEG <= END <= BUFFER_END.  */
+  if (!(BUF_BEGV_BYTE (buf) <= byte_beg
+	&& byte_beg <= byte_end
+	&& byte_end <= BUF_ZV_BYTE (buf)))
+    xsignal2 (Qargs_out_of_range, beg, end);
+
+  TSNode ts_node = XTS_NODE (node)->node;
+  TSNode child;
+  if (NILP (named))
+    child = ts_node_descendant_for_byte_range
+      (ts_node, byte_beg - 1 , byte_end - 1);
+  else
+    child = ts_node_named_descendant_for_byte_range
+      (ts_node, byte_beg - 1, byte_end - 1);
+
+  if (ts_node_is_null(child))
+    return Qnil;
+
+  return make_ts_node(XTS_NODE (node)->parser, child);
+}
+
 /* Query functions */
 
+Lisp_Object ts_query_error_to_string (TSQueryError error)
+{
+  char *error_name;
+  switch (error)
+    {
+    case TSQueryErrorNone:
+      error_name = "none";
+      break;
+    case TSQueryErrorSyntax:
+      error_name = "syntax";
+      break;
+    case TSQueryErrorNodeType:
+      error_name = "node type";
+      break;
+    case TSQueryErrorField:
+      error_name = "field";
+      break;
+    case TSQueryErrorCapture:
+      error_name = "capture";
+      break;
+    case TSQueryErrorStructure:
+      error_name = "structure";
+      break;
+    }
+  return  make_pure_c_string (error_name, strlen(error_name));
+}
+
+DEFUN ("tree-sitter-query-capture",
+       Ftree_sitter_query_capture,
+       Stree_sitter_query_capture, 2, 4, 0,
+       doc: /* Query NODE with PATTERN.
+
+Returns a list of (CAPTURE_NAME . NODE).  CAPTURE_NAME is the name
+assigned to the node in PATTERN.  NODE is the captured node.
+
+PATTERN is a string containing one or more matching patterns.  See
+manual for further explanation for how to write a match pattern.
+
+BEG and END, if _both_ non-nil, specifies the range in which the query
+is executed.
+
+Return nil if the query failed.  */)
+  (Lisp_Object node, Lisp_Object pattern,
+   Lisp_Object beg, Lisp_Object end)
+{
+  CHECK_TS_NODE (node);
+  CHECK_STRING (pattern);
+
+  TSNode ts_node = XTS_NODE (node)->node;
+  Lisp_Object lisp_parser = XTS_NODE (node)->parser;
+  const TSLanguage *lang = ts_parser_language
+    (XTS_PARSER (lisp_parser)->parser);
+  char *source = SSDATA (pattern);
+
+  uint32_t error_offset;
+  uint32_t error_type;
+  TSQuery *query = ts_query_new (lang, source, strlen (source),
+				 &error_offset, &error_type);
+  TSQueryCursor *cursor = ts_query_cursor_new ();
+
+  if (query == NULL)
+    {
+      // FIXME: Signal an error?
+      return Qnil;
+    }
+  if (!NILP (beg) && !NILP (end))
+    {
+      EMACS_INT beg_byte = XFIXNUM (beg);
+      EMACS_INT end_byte = XFIXNUM (end);
+      ts_query_cursor_set_byte_range
+	(cursor, (uint32_t) beg_byte - 1, (uint32_t) end_byte - 1);
+    }
+
+  ts_query_cursor_exec (cursor, query, ts_node);
+  TSQueryMatch match;
+  TSQueryCapture capture;
+  Lisp_Object result = Qnil;
+  Lisp_Object entry;
+  Lisp_Object captured_node;
+  const char *capture_name;
+  uint32_t capture_name_len;
+  while (ts_query_cursor_next_match (cursor, &match))
+    {
+      const TSQueryCapture *captures = match.captures;
+      for (int idx=0; idx < match.capture_count; idx++)
+	{
+	  capture = captures[idx];
+	  captured_node = make_ts_node(lisp_parser, capture.node);
+	  capture_name = ts_query_capture_name_for_id
+	    (query, capture.index, &capture_name_len);
+	  entry = Fcons (intern_c_string (capture_name),
+			 captured_node);
+	  result = Fcons (entry, result);
+	}
+    }
+  ts_query_delete (query);
+  ts_query_cursor_delete (cursor);
+  return Freverse (result);
+}
+
 /* Initialize the tree-sitter routines.  */
 void
 syms_of_tree_sitter (void)
@@ -443,11 +702,18 @@ syms_of_tree_sitter (void)
   DEFSYM (Qnamed, "named");
   DEFSYM (Qmissing, "missing");
   DEFSYM (Qextra, "extra");
+  DEFSYM (Qhas_changes, "has-changes");
   DEFSYM (Qhas_error, "has-error");
 
+  DEFSYM (Qtree_sitter_query_error, "tree-sitter-query-error");
+  Fput (Qtree_sitter_query_error, Qerror_conditions,
+	pure_list (Qtree_sitter_query_error, Qerror));
+  Fput (Qtree_sitter_query_error, Qerror_message,
+	build_pure_c_string ("Error with query pattern"))
+
   DEFSYM (Qtree_sitter_parser_list, "tree-sitter-parser-list");
-  DEFVAR_LISP ("ts-parser-list", Vtree_sitter_parser_list,
-		     doc: /* A list of tree-sitter parsers.
+  DEFVAR_LISP ("tree-sitter-parser-list", Vtree_sitter_parser_list,
+	       doc: /* A list of tree-sitter parsers.
 // TODO: more doc.
 If you removed a parser from this list, do not put it back in.  */);
   Vtree_sitter_parser_list = Qnil;
@@ -455,11 +721,19 @@ syms_of_tree_sitter (void)
 
   defsubr (&Stree_sitter_parser_p);
   defsubr (&Stree_sitter_node_p);
+
+  defsubr (&Stree_sitter_node_parser);
+
   defsubr (&Stree_sitter_create_parser);
+  defsubr (&Stree_sitter_parser_buffer);
+  defsubr (&Stree_sitter_parser_name);
+
   defsubr (&Stree_sitter_parser_root_node);
-  defsubr (&Stree_sitter_parse);
+  defsubr (&Stree_sitter_parse_string);
 
   defsubr (&Stree_sitter_node_type);
+  defsubr (&Stree_sitter_node_start_byte);
+  defsubr (&Stree_sitter_node_end_byte);
   defsubr (&Stree_sitter_node_string);
   defsubr (&Stree_sitter_node_parent);
   defsubr (&Stree_sitter_node_child);
@@ -469,4 +743,8 @@ syms_of_tree_sitter (void)
   defsubr (&Stree_sitter_node_child_by_field_name);
   defsubr (&Stree_sitter_node_next_sibling);
   defsubr (&Stree_sitter_node_prev_sibling);
+  defsubr (&Stree_sitter_node_first_child_for_byte);
+  defsubr (&Stree_sitter_node_descendant_for_byte_range);
+
+  defsubr (&Stree_sitter_query_capture);
 }
diff --git a/src/tree_sitter.h b/src/tree_sitter.h
index a7e2a2d670..e9b4a71326 100644
--- a/src/tree_sitter.h
+++ b/src/tree_sitter.h
@@ -33,6 +33,7 @@ #define EMACS_TREE_SITTER_H
 struct Lisp_TS_Parser
 {
   union vectorlike_header header;
+  Lisp_Object name;
   struct buffer *buffer;
   TSParser *parser;
   TSTree *tree;
@@ -95,7 +96,8 @@ ts_record_change (ptrdiff_t start_byte, ptrdiff_t old_end_byte,
 		  ptrdiff_t new_end_byte);
 
 Lisp_Object
-make_ts_parser (struct buffer *buffer, TSParser *parser, TSTree *tree);
+make_ts_parser (struct buffer *buffer, TSParser *parser,
+		TSTree *tree, Lisp_Object name);
 
 Lisp_Object
 make_ts_node (Lisp_Object parser, TSNode node);
diff --git a/test/src/tree-sitter-tests.el b/test/src/tree-sitter-tests.el
index cb1c464d3a..c61ad678d2 100644
--- a/test/src/tree-sitter-tests.el
+++ b/test/src/tree-sitter-tests.el
@@ -21,6 +21,7 @@
 
 (require 'ert)
 (require 'tree-sitter-json)
+(require 'tree-sitter)
 
 (ert-deftest tree-sitter-basic-parsing ()
   "Test basic parsing routines."
@@ -52,12 +53,13 @@ tree-sitter-basic-parsing
 (ert-deftest tree-sitter-node-api ()
   "Tests for node API."
   (with-temp-buffer
-    (insert "[1,2,{\"name\": \"Bob\"},3]")
     (let (parser root-node doc-node object-node pair-node)
-      (setq parser (tree-sitter-create-parser
-                    (current-buffer) (tree-sitter-json)))
-      (setq root-node (tree-sitter-parser-root-node
-                       parser))
+      (progn
+        (insert "[1,2,{\"name\": \"Bob\"},3]")
+        (setq parser (tree-sitter-create-parser
+                      (current-buffer) (tree-sitter-json)))
+        (setq root-node (tree-sitter-parser-root-node
+                         parser)))
       ;; `tree-sitter-node-type'.
       (should (eq 'document (tree-sitter-node-type root-node)))
       ;; `tree-sitter-node-check'.
@@ -100,7 +102,51 @@ tree-sitter-node-api
       (should (equal "(\",\")"
                      (tree-sitter-node-string
                       (tree-sitter-node-prev-sibling object-node))))
-      )))
+      ;; `tree-sitter-node-first-child-for-byte'.
+      (should (equal "(number)"
+                     (tree-sitter-node-string
+                      (tree-sitter-node-first-child-for-byte
+                       doc-node 3 t))))
+      (should (equal "(\",\")"
+                     (tree-sitter-node-string
+                      (tree-sitter-node-first-child-for-byte
+                       doc-node 3))))
+      ;; `tree-sitter-node-descendant-for-byte-range'.
+      (should (equal "(\"{\")"
+                     (tree-sitter-node-string
+                      (tree-sitter-node-descendant-for-byte-range
+                       root-node 6 7))))
+      (should (equal "(object (pair key: (string (string_content)) value: (string (string_content))))"
+                     (tree-sitter-node-string
+                      (tree-sitter-node-descendant-for-byte-range
+                       root-node 6 7 t)))))))
+
+(ert-deftest tree-sitter-query-api ()
+  "Tests for query API."
+  (with-temp-buffer
+    (let (parser root-node pattern doc-node object-node pair-node)
+      (progn
+        (insert "[1,2,{\"name\": \"Bob\"},3]")
+        (setq parser (tree-sitter-create-parser
+                      (current-buffer) (tree-sitter-json)))
+        (setq root-node (tree-sitter-parser-root-node
+                         parser))
+        (setq pattern "(string) @string
+(pair key: (_) @keyword)
+(number) @number"))
+
+      (should
+       (equal
+        '((number . "1") (number . "2")
+          (keyword . "\"name\"")
+          (string . "\"name\"")
+          (string . "\"Bob\"")
+          (number . "3"))
+        (mapcar (lambda (entry)
+                  (cons (car entry)
+                        (tree-sitter-node-content
+                         (cdr entry))))
+                (tree-sitter-query-capture root-node pattern)))))))
 
 (provide 'tree-sitter-tests)
 ;;; tree-sitter-tests.el ends here
-- 
2.24.3 (Apple Git-128)