Hello, I'm Danny McClanahan. This is EmacsConf 2024. And
this presentation is ostensibly about Emacs Regex
compilation. But it'll lead a lot more in future
directions. Thanks for coming on this journey with me.
This presentation is 50 slides, 50 footnotes, and that's
intended for it to be a resource later on for your perusal. We
are unfortunately not going to be able to go into all of it,
but I will try to be within 20 minutes so we can make it
throughout Q&A. This is the structure of the talk.
But enough about me. Who are you? And why are you here?
I'm Danny McClanahan.
My experience is a lot in build tools, especially in the
package managers. That started because I realized I was
wasting a lot of time. Then I didn't like that. I
started wasting a lot of time, trying to avoid wasting time.
Then I ended up... going so far around that I ended up
stopping other people from wasting their own time, in this
case, regarding failing builds. But this is a kind of
pattern that you'll see. I'm talking a lot about patterns in
this presentation. Parsing in text is another one of
those tendencies that I have. Why am I here? I've got a lot
of feelings about text. For the next 20 minutes, I'm
making it your problem.
First off, a huge shout out to Emacs Devel and the Emacs
community in general. I spent a lot of time learning about
what I'm about to talk about. I was definitely super
confused at first. Then when I became less confused and I
decided I was going to look at the regular expressions of the
Regex engine, I was like, oh, it's old C code. It's
Emacs. We can just use modern techniques. Turns out that's
wrong for kind of two reasons. One, because using modern
techniques or other engines don't necessarily do what
Emacs regex engine currently does. Then secondarily,
that's not actually as interesting as the other kind of
larger goals that emacs-devel discussed. Thank you, Eli
Zaretskii, so, so much, especially Pip Cet and everyone else
as well--I believe--Pip Cet, I hope I'm pronouncing that
correctly. Thank you so much. I'll be shouting you out
later as well. Then these larger goals ended up
overlapping a lot with my own research interests. And
that's very exciting. I'm hoping it's exciting for you
too. What is a regular expression? And when and how does
implementation match formal theory? So what does formal
theory mean? And we'll talk about that.
What is a regular expression? So I might ask you this
question, and you might give an answer. Then I might ask
someone else, and they might have an answer. Then I might
ask myself, and I might try to think of an answer. Our
answers would, you know, see, the thing is, they'd all be
correct, but they'd probably be slightly different, and
they'd be different in kind of important ways. I'm
using formal theory to kind of describe what unifies these
interpretations and what causes this sort of divergence,
both over time and then across code bases. I'm kind of
putting a flag in the ground here and saying formal theory is
actually a really, really negative influence, I think, but
it can be better. That's what I'm going to talk about in
this talk, in this presentation. We might ask, how did
this happen? and we might try to find a start state. We
might put that place at the theories of formal languages
that kind of arose, especially post Turing and post
Chomsky. Especially there was this really, really
interesting and powerful relationship with formal
languages between representation and computation. And
then on top of that, we have regex as this really powerful
union of theory and practice And then, like I mentioned,
this is kind of divergence that kind of occurs. This
divergence happens for a good reason. This happens because
people were adding implementations and people adding
features to implementations. While the people adding
these features were often academics, they were
industries, people that were hobbyists, they were
interested in building practical tools. This is a good
thing. This is still a good thing, even though it moves a
little bit away from formal theory. But we start seeing some
cracks developing, and we'll go into that in a second. We're
just going to kind of electric slide into the 1980s here, and
we're going to be confronted with two occurrences very
similarly. We might call it simultaneous discovery. In
1983, you have Michael Jackson demonstrating the
moonwalk. Three years later, we have backtracking
developed to stimulate EGREP-style regular expressions.
These would both be incredibly influential in their own
kind of branching paths. Here's where the gloves come
off. Formal theory, I claim, remains largely concerned
with incremental improvements to artificial benchmarks,
and much less with expanding models to cover actual user
needs. This isn't just about, oh, if you listened to
users, that you'd be a nicer person, you'd be a better
engineer. What I'm actually saying is that they're missing
out. When you don't listen to applications, you miss out on a
lot of fantastic opportunities for novel theory. So
this is, again, my complaint with formal theory as it
stands. But we're gonna do better. Before we get better,
we're gonna get, a little bit worse for a bit. We're going to
actually get a little bit worse is better. What I mean by
that is, by the 1990s, we start looking into these
non-backtracking engines. This is a bit of a reaction to
backtracking. The current ones include RE2,
hyperscan, and the rust regex library. These are all
great. I'll talk about them later as well. They make use
of these. They kind of call back to the earlier formal
theory. They have linear runtimes for well-specified
search tasks.
What happens if that doesn't fit your needs? We're going to
talk about that. We're going to table that for a second,
and we're going to focus more on Emacs, the subject of this
conference. What are regex used for? And in this
particular case, they're used for lots of things, with
practically, and I think they should be. But more
specifically, how do Emacs users use them? And I'm going to
focus in on this text as input and output. I'll be kind of
elaborating on this analogy as we continue. Why is text
powerful? Text as I/O. The reason text programming
languages and not just programming languages, but
languages themselves, the reason why they're successful
and why they propagate, I claim, is because text is both
input readable and output writable. What this means
is that if you receive something in text, you can read it, And
then you can also write it, you can modify it, and you can
produce a new version of it. You're on a kind of level
playing field. That's not always the case, though. You
recall that I've worked a lot with build systems and package
managers. There's a discussion that goes by the name of
software supply chain security. I think it's a massive
joke. The reason why is because people largely raise it
to explain why their for-profit company with their
for-profit product is going to solve the problem for you, as
opposed to the commons of open source. If you are unable to
modify or deploy your code without employing an opaque
external system, I think, then you have a hidden
dependency. you don't remove a dependency, you just, by,
for example, paying into a for-profit product or using a
closed-off supply chain, you end up just having a hidden
dependency, you end up just displacing that. This can
actually exert arbitrary control over your programming
output and potentially even your thoughts. This is really
important. I'm going to dive in a little bit deeper and I'm
going to overload the term locality here. I'm going to
say, if you cannot reproduce a system locally, it becomes an
opaque external system. I'm going to give examples
here, and these are going to be a bit of a hot take. First
off, GUI IDEs. I think we might, well, some of us might agree
with that here. I say development environments that only
allow you to use a graphical interface, do not expose
interaction with text, are explicitly trying to kind of
place you on a separate kind of plane where you're not an
equal contributor to the people who make the development
environment, make the development kind of frameworks
here. We'll go one further. Cloud services are precisely,
you know, they're useful for things that, you know, that
require large domain computation, but, you know, Twitter,
for example, didn't actually ever use any cloud services,
external ones, because it was really important for them to
actually own their own hardware, their own computation,
their own thinking. Cloud services are a way to ensure
that you're unable to reproduce a system without paying an
amount per month, an amount per day, an amount per second, an
amount per cycle to an external entity. I'm just going to
conclude this with, I'd say, the argumentum ad absurdum,
here, where large language models are all of these at once.
They are a cloud service, specifically, and this is what
makes them very evil, to make it so that, similar to GUI IDEs,
so that text itself loses that ability to be both readable
and writable. Instead, text is both unreadable, because
it's produced by a machine, and then also unwritable,
because you're subservient and subjugated to the machine,
to the large language model to produce the code in the first
place. You lose this input, output, readable, writable
behavior that I claim text has specifically. To
underline this, what is text? Text is local. Finally,
we're at the subject of this conference. Emacs, I have
double hearts with text. I start off the slide saying Emacs
is a text editor. I think that's a good start. Which
implements much of its own logic and user interface via
text. What this means is that, you know, I say without
trying, Emacs tries very hard, but without trying so hard,
Emacs, is imbued with all of the capabilities that text has
specifically. When you use text like Emacs does, and
particularly you then start offering mechanisms to query,
to transform, and to generally metaprogram text itself,
you don't just have the ability to edit code in new ways. And
this is something that I think is often lost, maybe not by
participants of this conference, you particularly start
being able to not only just edit code differently, but to
change the way that you think about code and actually to
expand your range of thought, the range of actions that you
can perform. You can actually start then editing at the
speed of thought. This is where especially Regex kind of
comes into play. Finally, we get to the subject of the
title of this talk. I'm about to disappoint a lot of
people. I claim for good reason. Unfortunately, it's a
very brief walkthrough, but I'm going to go over what the
current Emacs Redix engine is. This is going to give us
enough context for the next section on future directions.
Quickly, it's a backtracking engine over a multi-byte
code point. I'll define what that means. It's in
regex-emacs.c. It's invoked in two ways, which you'll see
is actually the same way, over a single contiguous string
input. This is a Lisp string that you pass in. or over the
two halves of the gap buffer. This is when you match
against a buffer text. We'll go into that a little bit
more, but this is one of the really actually interesting and
specific things about Emacs Regex Engine as it stands. So
very, very quickly, this is the data layout. This is just, if
you're interested, this is where the code lies. So
regex-emacs.h has re-pattern buffer, which is a struct
Actually, you know, I love, by the way, I love the Emacs C
source code. It's so nice to read. It made all this so, so
easy. I really appreciated it. In this particular case,
I'm just going to focus on re-pattern buffer actually has
the compiler. It's a C struct. It has every single thing
that is needed to execute the regular expression against a
string input or against a buffer input. This buffer,
It's not an Emacs buffer. It refers to just the instruction
table and the match loop. Again, this is very, very
brief, but I want to specifically focus on the first part. So
this is this inner matching loop, and there's a prologue,
and then there's a loop body, and there's an epilogue. And
the prologue is the really, really interesting part. I say
extract current and next char. What Emacs does here, it
doesn't just reach for the next byte. It actually will
perform lazily in some sense, this variable integer size
VAR decoding for multi-byte, and it'll actually then
decode the next one to four bytes. Up to 32 bits at once, and
then it'll actually go into the loop. We'll talk about the
implications of that later. Next, in the body of the loop, we
read the instruction from the instruction pointer, which
is, again, in that buffer field. Then we have this big
switch statement, which is actually, love a big switch
statement, super easy to read, super easy to understand
kind of what's occurring. Then that's the loop body. And
then at the end of it, we either increment the instruction
pointer if it was matching a single character or something
along those lines, or if it was a jump, we don't do that. A
jump, however, it's not referring to a jump in the sense of a
go-to, but a jump that's elsewhere within that table, that
buffer field. If you've included a capture, we write
that end position there. Of course, well, as you may
recall, the zeroth capture is, of course, the entire match
string. If the capture is zero, then we know we've
actually completed that match. That's really great.
I would love to receive Q&A about this as well. I've spent a
lot of time kind of learning and understanding it. But it's
really interesting that this can be described in a single
slide because it's really simple. That simplicity is
actually a really powerful thing. I'll mention that in
the next section. I say, is that all? And I apologize for
not doing so. But please, please ask questions in Q&A or
message me about this, because I think it's really, really,
again, interesting. Again, I find the code relatively
easy to read. Now, here's, I think this is actually the
point of the talk. The rest of it was, you know, I think just me
posturing. This is the really, really interesting part.
This is the ways that we can improve, well, not just we can
improve stuff in Emacs, but why those are the right things to
improve. Then also how that can be a model for even things
outside of Emacs. This is gonna be a lot of text. I'm not
gonna go through all of it. This is the one thing that I tried.
This is the thing that I thought would be a slam dunk, easy
solution. My initial thought process was, well, We tried
very hard to do an LRU cache here. It works. It's actually
very effective. However, though, we don't actually give
the user, the list programmer, the ability to then say, I
know that this regex is something that is going to be used
again. I made an artificial benchmark. I made an
artificial benchmark because I wanted to show there is one
very specific case that it does solve, but it's the same
issue with the artificial benchmarks. mentioned earlier.
It's very specifically crafted in order to show that this
particular solution would produce some speedup. What
this means is it just creates more than 20 regexps in a row. It
compiles them. Then, of course, because we just don't
pay the compile costs, because we don't go through that
cache eviction process, it ends up being faster. But this
isn't really mean very much, particularly the goal here,
you know, the goal would have been to show that the compile
cache is actually causing the performance issue in
comparison to pre-compiling it. That's not something
I've been able to show. Match over bytes, not cars. So
this is when I said at the beginning, oh, I came in and I think,
oh, we can just use modern regex engine techniques. This is
really what I meant. In particular, I mentioned in this
match loop here that there's this, prolog that does this
varring decoding. What this means is that every single
iteration of that loop is going to be interspersed with this
not being able to read a fixed number of bytes, but a variable
number of bytes just depending upon the Unicode character
or the Unicode code point or the multibyte code point. So
this ends up, again, being relatively difficult to
optimize because processors operate over bytes and not
over code points. Yes, we might consider a multi-byte CPU at
some point. But this is a really, really simple thing. It's
just generating automata that operate over bytes as
opposed to code points. This kind of goes into the much more
abstract one. There's a lot of text here, and we're not
going to go into it. But the really, really important point
that I'm specifically mentioning here is this explicit
control over linguistic complexity. That's the
abstract kind of point. I want to introduce the inputs and
the outputs. Basically, when you perform a search, or a
match, or a parse, those are different tasks. They'll
have different expected inputs and different desired
outputs. Right now, Emacs, the API for the regular
expression engine and for matching, It doesn't allow
specialization on this. Or rather, if we do specialize on
particular inputs, if we have a heuristic to check if a regex
is actually a literal string, that's not something that the
user actually has control over. For example, you can make
a mistake escaping something, and then you don't have a
literal, and then you accidentally have behavior that you
totally didn't expect. Not just correctness issues, but
also performance issues. I really like this one. I like
this a lot, because I didn't think of it at all. I think it's
better than in all of my ideas. This was proposed, at least
to me, by Pip Cet, and I really hope that I'm pronouncing your
name correctly. I'm sorry I didn't ask you beforehand,
emacs-devel. In particular, this was after a couple of
responses where I was trying to say, oh, I want to give the
list programmer, way back in here, I want to give the list
programmer the ability to control compilation in some
sense. you know, he mentioned, I think he is correct, you
know, there's no real introspection. That happens
because it's written in C. I was thinking, oh, if I turn
this into a list object that gives the list programmer the
power and the ability to do more with that, but it doesn't
actually because it's still in C. At first, I was
thinking, oh, we can make the C part more flexible. But
actually, especially if we want to do almost any of the
things we previously mentioned, I think basically that
this is... I think that if I'm not going to do it, somebody
else really should do it, and I think we should maybe even do
it together, because I think this is really, I think, how we
can start experimenting, and not just experimenting, but
because, as mentioned here, we have libgccjit, we have the
native compiler, we have the ability to opt, like,
specifically to generate specific code for this, so why not
implement the or a Redix engine itself in list, And this
gives us the ability to introspect it. That's one of the
things I mentioned at the beginning. But it actually gives
us the ability to then actually look at all the previous
implementations, to explicitly compile beforehand, to
match against bytes, to specialize and dispatch based upon
input and output. This is something that, you know, it's
super simple.
It's really smart. I'm really, really glad that Pip
mentioned this because it is, I think, the right way to solve
the rest of it. We're at the final section. I talked a
lot about, you know, kind of abstract, you know, thoughts.
I talked a little about, you know, specific solutions.
But I especially talked about, you know, what is Regex and
Emacs? And I don't know if I had a lot of specific examples of
it. I'm going to just describe kind of my, I guess,
motivation, my impetus. Then I think something that's
really something to chew on for the future. Do I have any
concrete examples? Yes. Well, you can decide if they're
concrete. Or am I just posturing? Also, yes. helm, rg. Helm,
Erg, it's literally just M-x grep, it uses ripgrep, which
is written by the same author of the Rust regex [??]. It
happens to be very, very fast. In particular, I use this tool
with ripgrep on the Twitter monorepo, and I was able to
search very, very large amounts of code that was on my local
machine using regular expressions. I think this is one
thing that I think is really, really important, because
when you want to scale, People say the word scaling and they
assume there's a specific kind of answer for that. I've
just found that text is not only flexible, it's actually
something that can be more performant than the alternative
and not only more performant, but more productive. It's
again, it's just M-x grep using ripgrep. There's a tool
deadgrep by Wilfred Hughes, which is also fantastic. I
think it's actually better than this, but this one's mine so
I can mess around with it. But this tool is kind of why,
especially I started looking into Emacs and looking into
changing the way that, or at least diving into how the
regular expression matching actually kind of works, both
in Emacs and then in ripgrep. We'll go to the next one.
This is something that does exist and continues to exist.
This is something that doesn't quite exist yet. I'm
calling it telepathy grams. It's, you know, it's the name,
and it's very, you know, it doesn't work, but it's a code
search tool that, in this case, precompiles the database to
execute NFAs against. I was thinking, how can I beat And
the first thing I thought is, well, as I have worked on build
tools, especially in monorepos, one of the things that the
pants build tool from Twitter does is it uses a file watcher
to ensure that instead of having to constantly read in the
entire contents of a file, which may be very, very large, it
only does so when the file has been changed. Finally, I
want to conclude on this note, which is just that the stuff I
didn't learn from emacs devel, I learned from Paul
Wankadia, Jr., who is the RE2 maintainer, and he taught me
quite a lot from 2023 to 2024. I'm thankful for the time
that I learned from you, so thank you, Paul. With that, we're
at point-max. Call me, beat me, if you want to reach me and or
hire me. These are places that you can reach me at. There are
probably others. Feel free to suggest other ways to contact
me. But for now, this is the end. Thank you so much for your
time. I really appreciate it.