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
assessors
and property assignments are highlighted
differently
what I like the most about this is that
new bindings are consistently
highlighted
this included local variable
function parameters and property
mutations
before going through the three 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
pass different languages
by sending different language objects to
it
the language objects themselves are
loaded from shared libraries
since three seater mode 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
uh is it an opaque object so this is not
very useful
we can instead ask what is its type
so his type is the symbol comparison
operator
trees 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 grammar
elements that are interesting enough for
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 or
not
properties
tree sitter allows searching for
structural patterns within a parse tree
it does so through a list like language
this language supports by the 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 trisito 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
uh 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 quotes
strings and
double quotes screens 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 note
to check whether it's a single quote or
a double quote
yeah so for that we use the three
setters
support for predicate in this case
we use a match predicate
to check whether the string where the
note
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
pop item 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 variable
for example let's take a look at
ems source code
so in image 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
as highlight this part
with the function phase instead
in order to do that
we put a pattern in this project
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 the highlighted
uh
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
only this part so
if it's a function call where the name
of the function is different
then we highlight the different as a
keyword
and then the first string element we
highlighted
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
3-seater adoption
therefore I've created a language window
package 3-seater length
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 three-seaters
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 call already works reasonably
well
there are several areas that would
benefit from the community's
contribution
so three seaters upstream language
prepositories
already contain highlighting queries on
their own
however they are pretty basic and they
may not fit well with existing emax
conventions
therefore the language bundle has its
own set of highlighting queries
this requires maintenance until language
measurements adopt
three 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
what mode for web assembly
the code is just
like one page of code not
not a lot
you can also try writing new minor modes
or writing integration packages
for example a lot of package a lot of
packages
may benefit from tree sitter integration
but no one has written the integration
yet
if you are interested in 3-seater 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