Hello, everyone! My name is Tuấn-Anh.
I've been using Emacs for about 10 years.
Today, I'm going to talk about tree-sitter,
a new Emacs package that allows Emacs
to parse multiple programming languages in real-time.
So what is the problem statement?
In order to support programming functionalities
for a particular language,
a text editor needs to have some degree
of language understanding.
Traditionally, text editors have relied
very heavily on regular expressions for this.
Emacs is no different.
Most language major modes use regular expressions
for syntax-highlighting, code navigation,
folding, indexing, and so on.
Regular expressions are problematic for a couple of reasons.
They're slow and inaccurate.
They also make the code hard to read and write.
Sometimes it's because the regular expressions themselves are very hairy,
and sometimes because they are just not powerful enough.
Some helper code is usually needed
to parse more intricate language features.
That also illustrates the core problem with regular expressions,
in that they are not powerful enough to parse programming languages.
An example feature that regular expressions cannot handle very well
is string interpolation, which is a very common feature
in many modern programming languages.
It would be much nicer if Emacs somehow
had structural understanding of source code, like IDEs do.
There have been multiple efforts
to bring this kind of programming language understanding into Emacs.
There are language-specific parsers
written in Elisp
that can be thought of
as the next logical step of the glue code
on top of regular expressions,
moving from partial local pattern recognition
into a full-fledged parser.
The most prominent example of this approach
is probably the famous js2-mode.
However, this approach has several issues.
Parsing is computationally expensive,
and Emacs Lisp is not good at that kind of stuff.
Furthermore, maintenance is very troublesome.
In order to work on these parsers,
first, you have to know Elisp well enough,
and then you have to be comfortable with
writing a recursive descending parser,
while constantly keeping up with changes to the language itself,
which can be evolving very quickly,
like Javascript, for example.
Together, these constraints significantly reduce
the pool of potential maintainers.
The biggest issue, though, in my opinion,
is lack of the set of generic and reusable APIs.
This makes them very hard to use
for minor modes that want to deal with
cross-cutting concerns across multiple languages.
The other approach which has been
gaining a lot of momentum in recent years
is externalizing language understanding
to another process,
also known as language server protocol.
This second approach is actually a very interesting one.
By decoupling language understanding
from the editing facility itself,
the LSP servers can attract a lot more contributors,
which makes maintenance easier.
However, they also have several issues of their own.
Being a separate process,
they are usually more resource-intensive,
and depending on the language,
the LSP server itself can bring with it
a host of additional dependencies
external to Emacs, which may be messy to install and manage.
Furthermore, JSON over RPC has pretty high latency.
For one-off tasks like jumping to source
or on-demand completion, it's great.
But for things like code highlighting,
the latency is just too much.
I was using Rust and I was following the
community effort to improve its IDE support,
hoping to integrate some of that into Emacs itself.
Then I heard someone from the community mention tree-sitter,
and I decided to check it out.
Basically, tree-sitter is an incremental parsing library and a parser generator.
It was introduced by the Atom editor in 2018.
Besides Atom, it is also being integrated
into the NeoVim editor,
and Github is using it to power
their source code analysis
and navigation features.
It is written in C and can be compiled
for all major platforms.
It can even be compiled
to web assembly to run on the web.
That's how Github is using it on their website.
So why is tree-sitter an interesting solution to this problem?
There are multiple features that make it an attractive option.
It is designed to be fast.
By being incremental,
the initial parse of a typical big file
can take tens of milliseconds,
while subsequent incremental processes
are sub-millisecond.
It achieves this by using structural sharing,
meaning replacing only affected nodes
in the old tree when it needs to.
Also, unlike LSP, being in the same process,
it has much lower latency.
Secondly, it provides a uniform programming interface.
The same data structures and functions
work on parse trees of different languages.
Syntax nodes of different languages
differ only by their types
and their possible child nodes.
This is a big advantage over language-specific parsers.
Thirdly, it's written in self-contained embeddable C.
As I mentioned previously, it can even be compiled to webassembly.
This makes integrating it into various editors quite easy
without having to install any external dependencies.
One thing that is not mentioned here
is that being a parser generator,
its grammars are declarative.
Together with being editor-independent,
this makes the pool of potential contributors much larger.
So I was convinced that tree-sitter is a good fit for Emacs.
Last year, I started writing the bindings
using dynamic module support introduced in Emacs 25.
Dynamic module means there is platform-specific native code involved,
but since there are pre-compiled binaries
for the three major platforms,
it should work in most places.
Currently, the core functionalities are in a pretty good shape.
Syntax highlighting is working nicely.
The whole thing is split into three packages.
tree-sitter is the main package that other packages should depend on.
tree-sitter-langs is the language bundle
that includes support
for most common languages.
And finally, the core APIs are in the package tsc,
which stands for tree-sitter-core.
It is the implicit dependency of the
tree-sitter package.
The main package includes the minor mode tree-sitter-mode.
This provides the base for other major or minor modes to build on.
Using Emacs's change tracking hooks,
it enables incremental parsing
and provides a syntax tree that is always up to date
after any edits in a buffer.
There is also a basic debug mode
that shows the parse tree in another buffer.
Here is a quick demo.
Here I'm in an empty Python buffer
with tree-sitter enabled.
I'm going to turn on the debug mode to
see the parse tree.
Since the buffer is empty,
there is only one node in the syntax tree:
the top-level module node.
Let's try typing some code.
As you can see, as I type into the Python buffer,
the syntax tree updates in real time.
The other minor mode included in the main package
is tree-sitter-hl-mode.
It overrides font-lock mode
and provides its own set of phases
and customization options
It is query-driven.
That means instead of regular expressions,
it uses a Lisp-like query language
to map syntax nodes
to highlighting phrases.
I'm going to open a python file with small snippets
that showcase syntax highlighting.
So this is the default highlighting
provided by python-mode.
This is the highlighting enabled by tree-sitter.
As you can see, string interpolation
and decorators are highlighted correctly.
Function calls are also highlighted.
You can also note that property accessors
and property assignments are highlighted differently.
What I like the most about this is that
new bindings are consistently highlighted.
This included local variables,
function parameters, and property mutations.
Before going through the tree queries
and the syntax highlighting
customization options,
let's take a brief look at
the core data structures and functions
that tree-sitter provides.
So parsing is done with the help of
a generic parser object.
A single parser object can be used to
parse different languages
by sending different language objects to it.
The language objects themselves are
loaded from shared libraries.
Since tree-sitter-mmode already handles
the parsing part,
we will instead focus on the functions
that inspect nodes,
and in the resulting path tree,
we can ask tree-sitter what is
the syntax node at point.
This is an opaque object, so this is not very useful.
We can instead ask what is its type.
So its type is the symbol comparison operator.
In tree-sitter, there are two kinds of nodes,
anonymous nodes and named nodes.
Anonymous nodes correspond to simple grammar elements
like keywords, operators, punctuations, and so on.
Name nodes, on the other hand, are grammar elements
that are interesting enough on their own
to have a name, like an identifier,
an expression, or a function definition.
Name node types are symbols,
while anonymous node types are strings.
For example, if we are on this comparison operator,
the node type should be a string.
We can also get other information about the node.
For example: what is this text,
or where it is in the buffer,
or what is its parent.
There are many other APIs to query
our node's properties.
tree-sitter allows searching
for structural patterns within a parse tree.
It does so through a Lisp-like language.
This language supports matching by node types,
field names, and predicates.
It also allows capturing nodes for further processing.
Let's try to see some examples.
So in this very simple query,
we just try to highlight all the identifiers in the buffer.
This s side tells tree-sitter to capture a node.
In the context of the query builder,
it's not very important,
but in normal highlighting query,
this will determine
the face used to highlight the note.
Suppose we want to capture
all the function names,
instead of just any identifier.
You can improve the query like this.
This will highlight the whole definition.
But we only want to capture the function name,
which means the identifier here.
So we move the capture to after the identifier node.
If we want to capture the class names as well,
we just add another pattern.
Let's look at a more practical example.
Here we can see that single-quoted strings
and double-quoted strings are highlighted the same.
But in some places,
because of some coding conventions,
it may be desirable to highlight them differently.
For example, if the string is single-quoted,
we may want to highlight it as a constant.
Let's try to see whether we can
distinguish these two cases.
So here we get all the strings.
If we want to see if it's single quotes
or double quote strings,
we can try looking at the first character of the string--
I mean the first character of the node--
to check whether it's a single quote or a double quote.
So for that, we use tree-sitter's support for predicates.
In this case, we use a match predicate
to check whether the string-- whether the node starts
with a single quote.
And with this pattern,
we only capture the single-quotes strings.
Let's try to give it a different face.
So we copy the pattern,
and we add this pattern for Python only.
But we also want to give the capture a different name.
Let's say we want to highlight it as a keyword.
And now, if we refresh the buffer,
we see that single quote strings
are highlighted as keywords.
The highlighting patterns
can also be set for a single project
using directory-local variables.
For example, let's take a look at Emacs's source code.
So in Emacs's C source, there are a lot of uses
of these different macros
to define functions,
and you can see this is actually the function name,
but it's highlighted as the string.
So what we want is to somehow recognize this pattern
and highlight it.
Highlight this part
with the function face instead.
In order to do that,
we put a pattern in this project's directory-local settings file.
So we can put this button in the C mode section.
And now, if we enable tree-sitter,
you can see that this is highlighted
as a normal function definition.
So this is the function face like we wanted.
The pattern for this is actually pretty simple.
It's only this part.
So if it's a function call
where the name of the function is defun,
then we highlight the defun as a keyword,
and then the first string element,
we highlight it as a function name.
Since the language objects are actually native code,
they have to be compiled for each platform
that we want to support.
This will become a big obstacle for tree-sitter adoption.
Therefore, I've created a language bundle package, tree-sitter-langs,
that takes care of pre-compiling the grammars,
the most common grammars for all three major platforms.
It also takes care of distributing these binaries
and provides some highlighting queries
for some of the languages.
It should be noted that this package
should be treated as a temporary distribution mechanism only,
to help with bootstrapping tree-sitter adoption.
The plan is that eventually these files
should be provided by
the language major modes themselves.
But in order to do that, we need better tooling,
so we're not there yet.
Since the core already works reasonably well,
there are several areas that would benefit
from the community's contribution.
So tree-sitter's upstream language repositories
already contain highlighting queries on their own.
However, they are pretty basic,
and they may not fit well with existing Emacs conventions.
Therefore, the language bundle has its own set of highlighting queries.
This requires maintenance until language major modes adopt tree-sitter
and maintain the queries on their own.
The queries are actually quite easy to write,
as you've already seen.
You just need to be familiar with the language,
familiar enough to come up with sensible highlighting patterns.
And if you are a maintainer of a language major mode,
you may want to consider integrating tree-sitter into your mode,
initially maybe as an optional feature.
The integration is actually pretty straightforward,
especially for syntax highlighting.
Or alternatively,
you can also try writing a new major mode from scratch
that relies on tree-sitter
from the very beginning.
The code for such a major mode is quite simple.
For example, this is the proposed
wat-mode for web assembly.
The code is just one page of code, not a lot.
You can also try writing new minor modes
or writing integration packages.
For example, a lot of packages
may benefit from tree-sitter integration,
but no one has written the integration yet.
If you are interested in tree-sitter,
you can use these links to learn more about it.
I think that's it for me today.
I'm happy to answer any questions.