Change scopeType matchers to rely on tree-sitter style scheme queries

[Will-Sommers]

Background

Currently Cursorless uses a custom pattern definition DSL alongside a set of helper functions in nodeMatcher.ts to match various scope types, such as item within a list or argue within a function definition or function invocation.

The tree-sitter project also provides a DSL, written in Scheme which allows a user to query for patterns within syntax trees. Here's a link to the docs and an example usage in JS via the web-tree-sitter project. Each query then is allowed to assign a name to a node, such as @comment or @punctuation.bracket:

(comment) @comment

[
  "("
  ")"
  "["
  "]"
  "{"
  "}"
  "%w("
  "%i("
] @punctuation.bracket

The name can then be read or asserted against.

The thought is that moving towards this approach will be more expressive out of the box. Additionally, many other projects including Neovim and Helix rely on queries for syntax highlighting as well as indentation which might help to make the incremental work for adding a new language a little bit simpler, since there are already partial or full definitions to work from. In particular, Helix already uses these queries for their textobjects, which is a simplified version of Cursorless scope types. Here's an example of a set of textobject definitions; they exist for several other languages as well

The Work

• Create a queries directory with a subdirectory for each language, eg queries/python, etc
• Create a query file for a language that provides queries for some or all of these ScopeTypes, placing the file in queries/<language>/scopeTypes.scm
• Add the ability to load queries on a per-language basis
• Queries occur on the tree level (SyntaxNode.Tree.Language) and so are top down rather than bottom up as cursorless node matchers currently work.
• Should a query have successful matches, return the smallest range containing the input selection
• Note that for some of the auxiliary definitions listed below (eg @<scopeType>.searchScope) we first find a match, and then search within that range

The definitions

• Default query tag is just @<scopeType>, so eg @namedFunction
• In addition, we support a few other queries:
  • @<scopeType>.removalRange indicates a different range that should be used for removal
  • @<scopeType>.domain indicates that we should first expand to the smallest containing match for this tag and then search for a rooted instance of @<scopeType> within this region. The canonical example for this one is enabling take value from within the key in a map: we'd set @collectionItem.domain to be the containing pair
  • @<scopeType>.iterationScope indicates that when user says "every <scopeType>", we should first expand to the smallest instance of this tag, and then yield all top-level instances of @<scopeType> within this range. Here, top-level means not contained by any other match within the search range. Also, note that when finding the instances in the range, we should use @<scopeType>.domain if it exists. See below for an explanation
  • @<scopeType>.interior is used by excludeInterior and interiorOnly stages (see update inside / outside #254)

Migration notes

This will require a replacement of each of the language matcher files with a scopeTypes.scm definition. For this reason, we will want to support both paths while the migration occurs. We can keep doing continuous delivery during migration because every language other than C# is well tested.

Questions

• Do we want to change our term scopeType to textObject? That is the term used in both nvim tree-sitter, helix, and by redstart voice
• Better term for @<scopeType>.iterationScope?
  • @<scopeType>.parent?
• How to handle argument lists and collection items? I have a feeling we'll be repeating , stuff for removal ranges a lot. I wonder if we want to add Toml configuration for languages where we can indicate scopes that should be handled as comma-separated lists. Along this direction, it's worth thinking about the connection to Support generic comma-separated lists #357
• Do we want to support custom queries? Here's how neovim does it
• Do we still want to support the "every" in cases where a scope doesn't explicitly specify a @<scopeType>.domain? We do that today by just iterating the parent. Might be useful to keep this one as a fallback 🤷‍♂️

Challenging cases

Why we need to use @<scopeType>.domain when searching within @<scopeType>.iterationScope

Consider the following case:

{
   foo: {
      bar: "baz"
   }
}

If the user says "take every key fine", we want to just return foo, excluding the nested key bar. In this case key.iterationScope is object and key.domain is pair. If we just looked for instances of key within the object, we'd get the nested key as well. However, if we search for top-level pair objects we won't, as desired

Why @<scopeType> must be rooted within @<scopeType>.domain

We can actually use the same code example as above:

{
   foo: {|
      bar: "baz"
   }
}

If the user says "take key" with the cursor at the indicated position (after second opening bracket), we want to select foo. We first expand to the containing pair, as that is the definition of key.domain. Then we need to find the key. If we just look for top-level keys (ie not contained by other keys), we'll end up with both foo and bar. If we require that the key be rooted within the pair, that won't happen

Fwiw, we could possibly instead exclude any @<scopeType> matches which are contained within a lower @<scopeType>.domain

Resources

• Helix documentation
• Helix implementation
• Helix queries
• nvim-treesitter documentation
• nvim-treesitter implementation (might actually be in neovim itself)
• nvim-treesitter queries
• neovim documentation
• neovim implementation
  • https://github.com/neovim/neovim/blob/master/runtime/lua/vim/treesitter.lua
  • https://github.com/neovim/neovim/tree/master/runtime/lua/vim/treesitter
• neovim tests

Addenda:

• The query syntax also allows for the injection of information apart from the name of a node and using this DSL will likely be the approach used to support multi-language documents.
• Use tree-sitter queries for smart indentation #685

Attributions

👋 Big H/T 🎩 to @wenkokke for the original idea

[wenkokke]

@<scopeType>.removalRange indicates a different range that should be used for removal

Using things like .removalRange has as a disadvantage that we can only include a node in one such range.

[wenkokke]

@<scopeType>.searchScope indicates that we should first expand to the smallest containing match for this tag and then search for @<scopeType> within this region. The canonical example for this one is enabling take value from within the key in a map: we'd set @collectionItem.searchScope to be the containing pair

My proposal featured a simplified query language for delimiters, which we search upwards from the current token. It would be good to somehow merge these proposals, to have a concept like “all results for query Q2 within the node returned by Q1 containing the mark”.

[wenkokke]

@<scopeType>.iterationScope indicates that when user says "every ", we should first expand to the smallest instance of this tag, and then yield all top-level instances of @<scopeType> within this range.

I propose we do a slightly different thing, using the delimiter mechanism described above. If we run Q2 within the delimiting scope, then “every” simply means “all matches” and “ordinal” means the ordinal’th match. The default would be to again return the node which contains the mark.

[pokey]

@<scopeType>.removalRange indicates a different range that should be used for removal

Using things like .removalRange has as a disadvantage that we can only include a node in one such range.

Sorry not sure I follow. Can you elaborate on the problem?

[pokey]

query language for delimiters

Can you elaborate on what you mean by this? What kind of delimiters?

[wenkokke]

query language for delimiters

Can you elaborate on what you mean by this? What kind of delimiters?

For, e.g., function parameters in a definition in Haskell, I search upwards to the first function definition node, which will delimit the second query, a downwards search for parameters rooted at that definition.

I think this achieves something similar to @Will-Sommers suggestion of using an .iterationScope annotation, but theirs is cleaner, since it manages to use a single query and a single query language.

Theirs would search the entire document for all function definitions with parameters, then grab the one which contains the mark, and then (probably could) return a list of captures corresponding to the parameters, either taking every, the n’th, or by default the one containing the mark.

Would even, I just realised, open up the suggestion of saying things like “take next arg” to take the parameter one after the one which contains the cursor, and other such relative commands.

[pokey]

query language for delimiters

Can you elaborate on what you mean by this? What kind of delimiters?

For, e.g., function parameters in a definition in Haskell, I search upwards to the first function definition node, which will delimit the second query, a downwards search for parameters rooted at that definition.

I think this achieves something similar to @Will-Sommers suggestion of using an .iterationScope annotation, but theirs is cleaner, since it manages to use a single query and a single query language.

Theirs would search the entire document for all function definitions with parameters, then grab the one which contains the mark, and then (probably could) return a list of captures corresponding to the parameters, either taking every, the n’th, or by default the one containing the mark.

Would even, I just realised, open up the suggestion of saying things like “take next arg” to take the parameter one after the one which contains the cursor, and other such relative commands.

Ok I'm confused: are you suggesting that we just do what's described in the issue, or are you proposing that we change something?

[pokey]

@Will-Sommers maybe tomorrow let's go through the exercise of writing a language definition? I think we might be able to make some headway in an hour and it should help to make things more concrete

[wenkokke]

Ok I'm confused: are you suggesting that we just do what's described in the issue, or are you proposing that we change something?

I propose we use @Will-Sommers approach of marking — what I call — delimiters using a named capture, then select all matches where the delimiter is the smallest possible region containing the mark, and use my approach to assign captures to every/ordinal/default.

[pokey]

How is that different from what's described in the issue?

[pokey]

Fwiw here is @wenkokke's original proposal:

Cursorless NodeFinder.pdf

And looks like here she started putting together a draft implementation

[pokey]

Fwiw the reason that I was leaning away from rooted queries and towards top-level matches was so that we could support "take every key" both with nothing selected, which would expand to containing map, and with something selected, which would search within selection. If we use top-level matches, then we can handle both in the same way