8 ms·

Regex engine internals as a library

396 points by kretaceous 3y ago

recov 3y ago
Burntsushi is a machine.
- agumonkey 3y ago
  lets him and borkdude meet
- kzrdude 3y ago
  Deterministic and finite such, or what?
  - sd9 3y ago
    Non-deterministic, deterministic, it matters not
jjice 3y ago
I've only given a quick read/skim, but this is extremely impressive. BurntSushi has a lot of create stuff out there, but the Rust regex crate is legendary. The fact that Rust has had such a performant and easy to use regular expression library for so long is a real treat to the community. This article as a whole is also a treasure. There's a fairly limited number of people who have written a ton about regular expressions, but they all do so extremely well. Russ Cox's article series (as mentioned in this one) is really great. I used it in college to write a regular expression engine one summer after I had started to fall in love with the perfect cross between theory and practice that regular expressions are. The changes for more in depth testing here are also very interesting, especially for a crate that I'm sure if critical so a lot of the ecosystem, and I appreciate the writeup on such a deep dive topic. Are regular expressions hard to read? Sometimes they can, especially if you haven't gone out of your way to take deep dives. Are they not perfect for a lot of parsing tasks? Sure, there are definitely things people shouldn't use regexs for that they do, like validating emails. At their core though, regular expressions are one of the most power dense tools we have in pretty much every language. The insane stuff you can get done (sometimes in a way that would be frowned upon) in so little time if just incredible. I'd love for there to be more content on regular expressions as well. Right now I'm only familiar with one book that really does a great job (at a practical level), and that's Mastering Regular Expressions by Jeffrey Friedl. On a theory level, a lot of compiler books will talk about them to varying degrees. The Dragon Book has some good content on regular expressions at an implementation level too. Does anyone have any other book recommendations for regular expressions? And if BurntSushi or any other regular expression engine contributors see this, I really appreciate the effort y'all put in to building such powerful software.
- chubot 3y ago
  What kind of content are you looking for? From a user POV, I think there is thankfully not much to learn about automata-based regexes like RE2 and rust/regex. The exception is if you're writing a performance-sensitive system entirely around regexes, like an intrusion detection system or search engine. A regex is a very small concept with a very large syntax :) It's "just" literals, alternation, repetition, and concatenation. So it's mostly being able to see through the syntax IMO. Nice animated diagrams in this recent post - https://news.ycombinator.com/item?id=35503089 https://news.ycombinator.com/item?id=35503089 (On the other hand, from the implementation POV, there is a wealth of material online, but you already know where to find that :) I still think someone should "cliff notes" the Cox RE2 articles, since the ideas are important but there is a lot of detail. There are also dozens of references in those articles for people to read; it was a comprehensive survey at the time.) --- BTW Friedl's book covers backtracking engines, which makes sense because PCRE, Perl itself, Python, Java, JavaScript, etc. all use that style But as far as I remember, most of the book is irrelevant for users of automata-based engines. It's a whole bunch of detail about optimizing backtracking, reordering your clauses, and lots of detail about engine-specific and even version-specific differences. Personally I just ignore all of that, and it doesn't cause me a problem. I use regexes all the time in every language, and stick to the features that an automata-based engine can handle. Once you go into the backtracking stuff, then you might want the Friedl book, and that's a huge waste of time IMO. It's way easier to do that kind of thing outside of a regex engine, with normal parsing techniques. And honestly once you go outside, you'll find you don't even need to backtrack. Perl-style regexes can be an astoundingly inefficient way to write a pattern recognition algorithm. --- Eggex is my attempt to separate the two kinds of things, since it's not obvious based on the syntax: https://www.oilshell.org/release/latest/doc/eggex.html https://www.oilshell.org/release/latest/doc/eggex.html It makes the syntax smaller, more familiar, and more composable. It's closer to the classic lex tool (e.g. GNU flex). It's funny that lex has a way better syntax for regular expressions for Perl, but it's used probably 10,000x less often because most people want an interpreter and not a compiler to C code. But lex has 90%-100% of what you need, and it's way simpler, with a nicer syntax. Literals are quoted so you don't have the literal/metachar confusion, and you can reuse patterns by name. The manual is worth skimming: https://westes.github.io/flex/manual/Simple-Examples.html#Simple-Examples https://westes.github.io/flex/manual/Simple-Examples.html#Si... I use re2c though, not flex, and its manual is also worth skimming: https://re2c.org/manual/manual_c.html https://re2c.org/manual/manual_c.html
ttul 3y ago
Story time. At ActiveState, my colleague and I - both fresh out of school - were tasked with building a regular expression debugger for the Komodo editor. We hired the legendary Perl guru Mark Jason Dominus to hack some hooks into Perl’s regex engine and then by exposing these hooks to the UI, we allowed users to watch the execution of their regexes step by step. These days, various web-based tools offer superior functionality. But in 2001, Komodo’s Rx Debugger was absolutely state of the art and so much fun to work on.
- mschaef 3y ago
  Any recommendations on specific web based tools for this?
  - imaginary_unit 3y ago
    not OP, but these are some I used in the past: https://www.debuggex.com/ https://www.debuggex.com/ https://regex101.com/ https://regex101.com/
- Twirrim 3y ago
  I've found myself in the past in a situation where I needed an offline regex debugger (dealing with air-gapped networks, so the folks that needed to use the tool literally couldn't get at any online site, nor would they be permitted to even think of putting what they were working with in to an online one, no matter how it's designed), and it seems almost all of the work has gone in to online tools. The offline tools are scarce and somewhat lacking in comparison to, say, https://regex101.com/ https://regex101.com/.
  - lesuorac 3y ago
    It seems like the site doesn't really need a server so people have made offline versions. So should be able to burn something like [1] to a disk. [1]: https://github.com/ibaaj/Regex101.com-offline-app/pull/1/files https://github.com/ibaaj/Regex101.com-offline-app/pull/1/fil...
  - aorth 3y ago
jakobnissen 3y ago
BioJulia has published Automa.jl, which is a pure-Julia regex engine that can insert arbitrary Julia code at compile time. Not to take away from Rusts regex which are far more advanced than Automa, but I just take issue with that library being the first time regex internals have been exposed as a library :)
- burntsushi 3y ago
  These sound like two different things. PCRE2, for example, has support for "callouts" which sound similar to what you're saying? https://www.pcre.org/current/doc/html/pcre2callout.html https://www.pcre.org/current/doc/html/pcre2callout.html --- Other things like ragel and re2c have done similar things. What I'm talking about in this blog is very different from that. This is about taking the internals of the regex library itself and turning them in a separately versioned library that others can compose. This makes somewhat less sense for a backtracker because most backtrackers just have one engine: the backtracker. But an automata based library usually has many different engines that can be composed in different ways. Still, backtrackers have things they could expose but don't in practice, such as a regex parser and an AST.
  - nsajko 3y ago
    You're both correct. In the context of Julia, where compilation and run time are arbitrarily interleaved, something like re2c can be a library and used at run time.
    - burntsushi 3y ago
      Just to be clear here, I mentioned re2c as an example of what my blog is not about. There is a category difference between "ask a regex engine to run arbitrary code" and "expose internals as a separately versioned library for others to compose as they want." They service different use cases.
LoganDark 3y ago
I was in the middle of writing some regex-automata code (using the early 0.2.0 release) when this post dropped. Welp, time to see if I'm going to have to start all over digging into some brand new internals~ (I haven't read the post yet because I have an important call in a few minutes, but it looks like a very interesting and also conveniently-timed blog post.) (Edit a few minutes later: looks like the answer might be yes, but since this is a polished release, I might be able to simplify my code massively. Wish me luck~) (Edit 2 about 10 minutes later: well that was pretty painless and the new Builder::patch method is a total upgrade. Awesome~) P.S. I'm still blocked from all your GitHub repositories and I think that's kind of unfair considering how widespread a lot of your crates are. I don't remember the original incident anymore. I believe the regex crate itself is under the rust-lang organization now, but there are still others I can't interact with.
- burntsushi 3y ago
  The regex-automata 0.2.0 docs did have a giant warning about this, and strongly recommended going with 0.1: https://docs.rs/regex-automata/0.2.0/regex_automata/ https://docs.rs/regex-automata/0.2.0/regex_automata/ > I'm still blocked from all your GitHub repositories and I think that's kind of unfair considering how widespread a lot of your crates are. I don't remember the original incident anymore. I don't either. I block a lot of people for a lot of reasons. I unblocked you.
  - LoganDark 3y ago
    > The regex-automata 0.2.0 docs did have a giant warning about this I didn't listen, and it paid off, because a bunch of the knowledge I learned on it is still perfectly applicable to 0.3.0; I already have the same NFA as before. :) Now my appointment got canceled so I get to read your blog post and play with the new version. Fun!
alpaca128 3y ago
I experimented with the regex-automata crate in the past and it's the only one I found which can be used for text editors because the direct access to the underlying DFA makes it compatible with any text data structure. The usual regex library APIs expect the input to be one contiguous string.
otterpro 3y ago
I use Ripgrep daily for searching anything in code or in text files, and I'm grateful every time I use it (on windows, linux, mac, vscode, vim, etc...). It's one of those software that has changed my life and how I work. Whenever I'm forced to use `grep`, it feels like I've travelled back in time when everything ran on a single core CPU and data were on slow spinning hard disk on PATA/IDE. Anyway, burntsushi definitely deserves honor amongst other great programmers.
- kzrdude 3y ago
  ripgrep comes out of a "lineage", before it there was ag and before that ack, that did similar things to provide a much better interface than just grep.
  - theonething 3y ago
    I'm still using ag and haven't tried ripgrep just because ag is already so fast for me. I should probably still try it sometime thought.
yazaddaruvala 3y ago
For a problem at work, I needed to create a RegexSet of over 10 MM really long regexes. No engine out of the box could handle it. Even Rust’s RegexSet wasn’t good enough by default. However, trying to use and read through regex-automata and regex-syntax (even in 2018) was such a very valuable and helpful learning resource. I ended up modeling the project at work off Lucene APIs, but it was all only after learning the basics from the regex crates. Best set of libs! Thanks sushi!
- burntsushi 3y ago
  Yeah 10 million regexes is huuuuge. Aho-Corasick can barely handle 10 million literals. Future work is definitely trying to make the regex engine scale better with more patterns. Currently, it will crap out well before 10 million regexes, and I'm not sure that goal is actually attainable. But it can certainly be better than what it is today. And of course, Hyperscan is really the gold standard here as far as multi-pattern searching goes. I'm not sure how well it will handle 10 million patterns though.
  - yazaddaruvala 3y ago
    Yeah basically built a competitor to Hyperscan without the proprietary Intel bits. Quick notes: to scale past X regexes in the set. 1. Don’t make a single RegexSet. Create multiple internally. 2. Ideally colocate similar partners together. 3. Use the immutability of a RegexSet to your advantage by generating an inverse index of “must match” portions of each regex. 4. When you get an input to match, first check the inverse index for a “may match set”, then only execute the internal automata that may possibly match on the input. The inverse index can be as complicated (FSTs, or all of Lucene) or simple (hash map ) as you’d like it to be. The better it can filter the regexes in the set the more performance and scale you end up with. And tune the sizes of the internal automata for your usecase for some Goldilocks size for extra perf.
    - burntsushi 3y ago
      Right. I'll also note that this strategy probably assumes something about the search task itself, and may not work for all possible search operations. Think about what happens when your haystack is GBs big for example.
BoppreH 3y ago
Can this be used for non-string lists? I always found it frustrating that we have this amazing machinery for searching and modifying lists of characters, but as soon as I have a list of numbers or dates it all goes out of the window. Let's say I have a list of login attempt dates, and I want all sequences of 5+ failed login attempts followed by a success. With a regex it's trivial, but I can't use that; I have to roll my own loop, flags, and temporary lists. Sure, I could convert my list to a string, process it, and (try to) convert it back, but the downsides are obvious. Even if the performance is not as good as string-based regex, why shouldn't we have regexes for arbitrary list types? --- Edit: I realized this is not the first time I had this idea, and found an old Python prototype: https://github.com/boppreh/listregex https://github.com/boppreh/listregex It's horribly slow, but as an API experiment I'm quite happy. It also gives some tools not available to regexes, like inverting and intersect patterns, and matched pairs.
- saagarjha 3y ago
  You're going to have to define some sort of API for matching on a sliding window of values. This isn't impossible, but most languages don't really have great interfaces for it.
  - BoppreH 3y ago
    Parser combinators[1] seem perfectly suited for this. # A sequence of 5 or more failed login attempts followed by a successful one. obj_regex.search(repeat(is_failed, min=5)+is_success, my_list) [1]: https://en.wikipedia.org/wiki/Parser_combinator https://en.wikipedia.org/wiki/Parser_combinator
- burntsushi 3y ago
  Nope. The regex library is tightly coupled with searching strings. That's an intentional design decision. Making a regex engine like this have a generic alphabet is a total non-starter. It's impractically difficult for me to do. Especially the API design and doing it in a way that doesn't impact the perf of the primary use case. The kind of regex engine you want, especially one where you don't care about perf, is not hard to build. You could take the `regex-lite` crate I published, for example, and code it up to be as generic as you want. In so doing, I expect you'll run into a number of interesting challenges. Anyway, it's not like these things don't exist. They do. People attempt to build them[1]. They just usually don't gain much traction because I suspect you're overstating their general utility. :-) [1]: https://docs.rs/automata/latest/automata/trait.Alphabet.html https://docs.rs/automata/latest/automata/trait.Alphabet.html
celeritascelery 3y ago
My biggest wish for rust regex was support for ARM SIMD. Currently the literal optimization is only vectorized on x86. It seems that the author doesn’t own an ARM machine, and therefore can’t test implementation and so doesn’t want to support it.
- burntsushi 3y ago
  I actually have an M2 mac mini in the mail from Apple for exactly this purpose. My time horizon is very long. It takes me a long time to do things these days. It has never been true that I don't want to support it. Merely that it is difficult to verify and test if I can't do it myself. There is also the problem that the port from x86 to arm is not straight-forward, due to both my own ignorance and what I believe are important missing vector operations such as movemask. This is discussed a bit more here (including the bit about movemask): https://github.com/BurntSushi/memchr/issues/76 https://github.com/BurntSushi/memchr/issues/76
  - celeritascelery 3y ago
    The current PR for ARM SIMD[1] uses a different instruction mix to achieve the same goals as movemask. I tested the PR and it has a significant speedup over the non-vectorized version. [1]https://github.com/BurntSushi/memchr/pull/114 https://github.com/BurntSushi/memchr/pull/114
    - burntsushi 3y ago
      Yup, thanks for the reminder. That's my starting point once my M2 arrives.
  - deleted 3y ago
    [deleted]
- deleted 3y ago
  [deleted]
- AceJohnny2 3y ago
  > It seems that the author doesn’t own an ARM machine, and therefore can’t test implementation and so doesn’t want to support it. Tangential (since he answered already), but in this era of cheap cloud instances, I'd be surprised if "not owning a <blank>" is any hindrance to support.
junon 3y ago
Thank you again, BurntSushi. This is marvelous work.
- burntsushi 3y ago
  <3
abbeyj 3y ago
burntsushi, the code example after "we can also increase it by decreasing the size of our regex by disabling Unicode mode:" seems to be the same as the previous code example. Copy-paste mistake?
- burntsushi 3y ago
  Yup, nice catch. I fixed it. The pattern should have a `(?-u)` at the beginning.

396 points by kretaceous 3y ago

recov 3y ago

Burntsushi is a machine.

agumonkey 3y ago
lets him and borkdude meet
kzrdude 3y ago
Deterministic and finite such, or what?
- sd9 3y ago
  Non-deterministic, deterministic, it matters not

jjice 3y ago

I've only given a quick read/skim, but this is extremely impressive. BurntSushi has a lot of create stuff out there, but the Rust regex crate is legendary. The fact that Rust has had such a performant and easy to use regular expression library for so long is a real treat to the community. This article as a whole is also a treasure. There's a fairly limited number of people who have written a ton about regular expressions, but they all do so extremely well. Russ Cox's article series (as mentioned in this one) is really great. I used it in college to write a regular expression engine one summer after I had started to fall in love with the perfect cross between theory and practice that regular expressions are. The changes for more in depth testing here are also very interesting, especially for a crate that I'm sure if critical so a lot of the ecosystem, and I appreciate the writeup on such a deep dive topic. Are regular expressions hard to read? Sometimes they can, especially if you haven't gone out of your way to take deep dives. Are they not perfect for a lot of parsing tasks? Sure, there are definitely things people shouldn't use regexs for that they do, like validating emails. At their core though, regular expressions are one of the most power dense tools we have in pretty much every language. The insane stuff you can get done (sometimes in a way that would be frowned upon) in so little time if just incredible. I'd love for there to be more content on regular expressions as well. Right now I'm only familiar with one book that really does a great job (at a practical level), and that's Mastering Regular Expressions by Jeffrey Friedl. On a theory level, a lot of compiler books will talk about them to varying degrees. The Dragon Book has some good content on regular expressions at an implementation level too. Does anyone have any other book recommendations for regular expressions? And if BurntSushi or any other regular expression engine contributors see this, I really appreciate the effort y'all put in to building such powerful software.

chubot 3y ago
What kind of content are you looking for? From a user POV, I think there is thankfully not much to learn about automata-based regexes like RE2 and rust/regex. The exception is if you're writing a performance-sensitive system entirely around regexes, like an intrusion detection system or search engine. A regex is a very small concept with a very large syntax :) It's "just" literals, alternation, repetition, and concatenation. So it's mostly being able to see through the syntax IMO. Nice animated diagrams in this recent post - https://news.ycombinator.com/item?id=35503089 https://news.ycombinator.com/item?id=35503089 (On the other hand, from the implementation POV, there is a wealth of material online, but you already know where to find that :) I still think someone should "cliff notes" the Cox RE2 articles, since the ideas are important but there is a lot of detail. There are also dozens of references in those articles for people to read; it was a comprehensive survey at the time.) --- BTW Friedl's book covers backtracking engines, which makes sense because PCRE, Perl itself, Python, Java, JavaScript, etc. all use that style But as far as I remember, most of the book is irrelevant for users of automata-based engines. It's a whole bunch of detail about optimizing backtracking, reordering your clauses, and lots of detail about engine-specific and even version-specific differences. Personally I just ignore all of that, and it doesn't cause me a problem. I use regexes all the time in every language, and stick to the features that an automata-based engine can handle. Once you go into the backtracking stuff, then you might want the Friedl book, and that's a huge waste of time IMO. It's way easier to do that kind of thing outside of a regex engine, with normal parsing techniques. And honestly once you go outside, you'll find you don't even need to backtrack. Perl-style regexes can be an astoundingly inefficient way to write a pattern recognition algorithm. --- Eggex is my attempt to separate the two kinds of things, since it's not obvious based on the syntax: https://www.oilshell.org/release/latest/doc/eggex.html https://www.oilshell.org/release/latest/doc/eggex.html It makes the syntax smaller, more familiar, and more composable. It's closer to the classic lex tool (e.g. GNU flex). It's funny that lex has a way better syntax for regular expressions for Perl, but it's used probably 10,000x less often because most people want an interpreter and not a compiler to C code. But lex has 90%-100% of what you need, and it's way simpler, with a nicer syntax. Literals are quoted so you don't have the literal/metachar confusion, and you can reuse patterns by name. The manual is worth skimming: https://westes.github.io/flex/manual/Simple-Examples.html#Simple-Examples https://westes.github.io/flex/manual/Simple-Examples.html#Si... I use re2c though, not flex, and its manual is also worth skimming: https://re2c.org/manual/manual_c.html https://re2c.org/manual/manual_c.html

ttul 3y ago

Story time. At ActiveState, my colleague and I - both fresh out of school - were tasked with building a regular expression debugger for the Komodo editor. We hired the legendary Perl guru Mark Jason Dominus to hack some hooks into Perl’s regex engine and then by exposing these hooks to the UI, we allowed users to watch the execution of their regexes step by step. These days, various web-based tools offer superior functionality. But in 2001, Komodo’s Rx Debugger was absolutely state of the art and so much fun to work on.

mschaef 3y ago
Any recommendations on specific web based tools for this?
- imaginary_unit 3y ago
  not OP, but these are some I used in the past: https://www.debuggex.com/ https://www.debuggex.com/ https://regex101.com/ https://regex101.com/
Twirrim 3y ago
I've found myself in the past in a situation where I needed an offline regex debugger (dealing with air-gapped networks, so the folks that needed to use the tool literally couldn't get at any online site, nor would they be permitted to even think of putting what they were working with in to an online one, no matter how it's designed), and it seems almost all of the work has gone in to online tools. The offline tools are scarce and somewhat lacking in comparison to, say, https://regex101.com/ https://regex101.com/.
- lesuorac 3y ago
  It seems like the site doesn't really need a server so people have made offline versions. So should be able to burn something like [1] to a disk. [1]: https://github.com/ibaaj/Regex101.com-offline-app/pull/1/files https://github.com/ibaaj/Regex101.com-offline-app/pull/1/fil...
- aorth 3y ago

jakobnissen 3y ago

BioJulia has published Automa.jl, which is a pure-Julia regex engine that can insert arbitrary Julia code at compile time. Not to take away from Rusts regex which are far more advanced than Automa, but I just take issue with that library being the first time regex internals have been exposed as a library :)

burntsushi 3y ago
These sound like two different things. PCRE2, for example, has support for "callouts" which sound similar to what you're saying? https://www.pcre.org/current/doc/html/pcre2callout.html https://www.pcre.org/current/doc/html/pcre2callout.html --- Other things like ragel and re2c have done similar things. What I'm talking about in this blog is very different from that. This is about taking the internals of the regex library itself and turning them in a separately versioned library that others can compose. This makes somewhat less sense for a backtracker because most backtrackers just have one engine: the backtracker. But an automata based library usually has many different engines that can be composed in different ways. Still, backtrackers have things they could expose but don't in practice, such as a regex parser and an AST.
- nsajko 3y ago
  You're both correct. In the context of Julia, where compilation and run time are arbitrarily interleaved, something like re2c can be a library and used at run time.
  - burntsushi 3y ago
    Just to be clear here, I mentioned re2c as an example of what my blog is not about. There is a category difference between "ask a regex engine to run arbitrary code" and "expose internals as a separately versioned library for others to compose as they want." They service different use cases.

LoganDark 3y ago

I was in the middle of writing some regex-automata code (using the early 0.2.0 release) when this post dropped. Welp, time to see if I'm going to have to start all over digging into some brand new internals~ (I haven't read the post yet because I have an important call in a few minutes, but it looks like a very interesting and also conveniently-timed blog post.) (Edit a few minutes later: looks like the answer might be yes, but since this is a polished release, I might be able to simplify my code massively. Wish me luck~) (Edit 2 about 10 minutes later: well that was pretty painless and the new Builder::patch method is a total upgrade. Awesome~) P.S. I'm still blocked from all your GitHub repositories and I think that's kind of unfair considering how widespread a lot of your crates are. I don't remember the original incident anymore. I believe the regex crate itself is under the rust-lang organization now, but there are still others I can't interact with.

burntsushi 3y ago
The regex-automata 0.2.0 docs did have a giant warning about this, and strongly recommended going with 0.1: https://docs.rs/regex-automata/0.2.0/regex_automata/ https://docs.rs/regex-automata/0.2.0/regex_automata/ > I'm still blocked from all your GitHub repositories and I think that's kind of unfair considering how widespread a lot of your crates are. I don't remember the original incident anymore. I don't either. I block a lot of people for a lot of reasons. I unblocked you.
- LoganDark 3y ago
  > The regex-automata 0.2.0 docs did have a giant warning about this I didn't listen, and it paid off, because a bunch of the knowledge I learned on it is still perfectly applicable to 0.3.0; I already have the same NFA as before. :) Now my appointment got canceled so I get to read your blog post and play with the new version. Fun!

alpaca128 3y ago

I experimented with the regex-automata crate in the past and it's the only one I found which can be used for text editors because the direct access to the underlying DFA makes it compatible with any text data structure. The usual regex library APIs expect the input to be one contiguous string.

otterpro 3y ago

I use Ripgrep daily for searching anything in code or in text files, and I'm grateful every time I use it (on windows, linux, mac, vscode, vim, etc...). It's one of those software that has changed my life and how I work. Whenever I'm forced to use `grep`, it feels like I've travelled back in time when everything ran on a single core CPU and data were on slow spinning hard disk on PATA/IDE. Anyway, burntsushi definitely deserves honor amongst other great programmers.

kzrdude 3y ago
ripgrep comes out of a "lineage", before it there was ag and before that ack, that did similar things to provide a much better interface than just grep.
- theonething 3y ago
  I'm still using ag and haven't tried ripgrep just because ag is already so fast for me. I should probably still try it sometime thought.

yazaddaruvala 3y ago

For a problem at work, I needed to create a RegexSet of over 10 MM really long regexes. No engine out of the box could handle it. Even Rust’s RegexSet wasn’t good enough by default. However, trying to use and read through regex-automata and regex-syntax (even in 2018) was such a very valuable and helpful learning resource. I ended up modeling the project at work off Lucene APIs, but it was all only after learning the basics from the regex crates. Best set of libs! Thanks sushi!

burntsushi 3y ago
Yeah 10 million regexes is huuuuge. Aho-Corasick can barely handle 10 million literals. Future work is definitely trying to make the regex engine scale better with more patterns. Currently, it will crap out well before 10 million regexes, and I'm not sure that goal is actually attainable. But it can certainly be better than what it is today. And of course, Hyperscan is really the gold standard here as far as multi-pattern searching goes. I'm not sure how well it will handle 10 million patterns though.
- yazaddaruvala 3y ago
  Yeah basically built a competitor to Hyperscan without the proprietary Intel bits. Quick notes: to scale past X regexes in the set. 1. Don’t make a single RegexSet. Create multiple internally. 2. Ideally colocate similar partners together. 3. Use the immutability of a RegexSet to your advantage by generating an inverse index of “must match” portions of each regex. 4. When you get an input to match, first check the inverse index for a “may match set”, then only execute the internal automata that may possibly match on the input. The inverse index can be as complicated (FSTs, or all of Lucene) or simple (hash map ) as you’d like it to be. The better it can filter the regexes in the set the more performance and scale you end up with. And tune the sizes of the internal automata for your usecase for some Goldilocks size for extra perf.
  - burntsushi 3y ago
    Right. I'll also note that this strategy probably assumes something about the search task itself, and may not work for all possible search operations. Think about what happens when your haystack is GBs big for example.

BoppreH 3y ago

Can this be used for non-string lists? I always found it frustrating that we have this amazing machinery for searching and modifying lists of characters, but as soon as I have a list of numbers or dates it all goes out of the window. Let's say I have a list of login attempt dates, and I want all sequences of 5+ failed login attempts followed by a success. With a regex it's trivial, but I can't use that; I have to roll my own loop, flags, and temporary lists. Sure, I could convert my list to a string, process it, and (try to) convert it back, but the downsides are obvious. Even if the performance is not as good as string-based regex, why shouldn't we have regexes for arbitrary list types? --- Edit: I realized this is not the first time I had this idea, and found an old Python prototype: https://github.com/boppreh/listregex https://github.com/boppreh/listregex It's horribly slow, but as an API experiment I'm quite happy. It also gives some tools not available to regexes, like inverting and intersect patterns, and matched pairs.

saagarjha 3y ago
You're going to have to define some sort of API for matching on a sliding window of values. This isn't impossible, but most languages don't really have great interfaces for it.
- BoppreH 3y ago
  Parser combinators[1] seem perfectly suited for this. # A sequence of 5 or more failed login attempts followed by a successful one. obj_regex.search(repeat(is_failed, min=5)+is_success, my_list) [1]: https://en.wikipedia.org/wiki/Parser_combinator https://en.wikipedia.org/wiki/Parser_combinator
burntsushi 3y ago
Nope. The regex library is tightly coupled with searching strings. That's an intentional design decision. Making a regex engine like this have a generic alphabet is a total non-starter. It's impractically difficult for me to do. Especially the API design and doing it in a way that doesn't impact the perf of the primary use case. The kind of regex engine you want, especially one where you don't care about perf, is not hard to build. You could take the `regex-lite` crate I published, for example, and code it up to be as generic as you want. In so doing, I expect you'll run into a number of interesting challenges. Anyway, it's not like these things don't exist. They do. People attempt to build them[1]. They just usually don't gain much traction because I suspect you're overstating their general utility. :-) [1]: https://docs.rs/automata/latest/automata/trait.Alphabet.html https://docs.rs/automata/latest/automata/trait.Alphabet.html

celeritascelery 3y ago

My biggest wish for rust regex was support for ARM SIMD. Currently the literal optimization is only vectorized on x86. It seems that the author doesn’t own an ARM machine, and therefore can’t test implementation and so doesn’t want to support it.

burntsushi 3y ago
I actually have an M2 mac mini in the mail from Apple for exactly this purpose. My time horizon is very long. It takes me a long time to do things these days. It has never been true that I don't want to support it. Merely that it is difficult to verify and test if I can't do it myself. There is also the problem that the port from x86 to arm is not straight-forward, due to both my own ignorance and what I believe are important missing vector operations such as movemask. This is discussed a bit more here (including the bit about movemask): https://github.com/BurntSushi/memchr/issues/76 https://github.com/BurntSushi/memchr/issues/76
- celeritascelery 3y ago
  The current PR for ARM SIMD[1] uses a different instruction mix to achieve the same goals as movemask. I tested the PR and it has a significant speedup over the non-vectorized version. [1]https://github.com/BurntSushi/memchr/pull/114 https://github.com/BurntSushi/memchr/pull/114
  - burntsushi 3y ago
    Yup, thanks for the reminder. That's my starting point once my M2 arrives.
- deleted 3y ago
  [deleted]
deleted 3y ago
[deleted]
AceJohnny2 3y ago
> It seems that the author doesn’t own an ARM machine, and therefore can’t test implementation and so doesn’t want to support it. Tangential (since he answered already), but in this era of cheap cloud instances, I'd be surprised if "not owning a <blank>" is any hindrance to support.

junon 3y ago

Thank you again, BurntSushi. This is marvelous work.

burntsushi 3y ago
<3

abbeyj 3y ago

burntsushi, the code example after "we can also increase it by decreasing the size of our regex by disabling Unicode mode:" seems to be the same as the previous code example. Copy-paste mistake?

burntsushi 3y ago
Yup, nice catch. I fixed it. The pattern should have a `(?-u)` at the beginning.