8 ms·

Let's Build a Regex Engine (2019)

• tom_mellior 5y ago
  It hurts my eyes to see the author consistently misspell "automaton" as "automation".
  • a_gr 5y ago
    Oh my, fixed.
    • tom_mellior 5y ago
      Cool, thank you for the quick fix!
• sjrd 5y ago
  Not directly related, but recently I've built a regex engine that was a bit different: I implemented the semantics of Java's java.util.regex.Pattern on top of JavaScript's RegExp. This is for Scala.js' implementation of Pattern. [1] It turns out that they are wildly incompatible by default, so directly passing through the regular expressions to RegExp is incorrect in most cases. That was what we used to do before, though. Other compilers like GWT use the same technique. So I implemented a complete compiler from Java regular expressions to JavaScript regexes that preserves semantics. It supports virtually everything, and fails fast for the few things that are not supported (like grapheme clusters or canonical equivalence). Some things are very tricky to get right, like atomic groups or handling of surrogate pairs when the 'u' flag is not natively supported. The advantages of that strategy over reimplementing a complete engine (which is what TeaVM does) are a) code size and b) we get the performance of native RegExp's (which are JIT-compiled to native code, these days). [1] https://github.com/scala-js/scala-js/pull/4455 https://github.com/scala-js/scala-js/pull/4455
  • aarchi 5y ago
    Wow that's a phenomenal effort! It's surprisingly complex converting between regexp dialects.
  • bassdropvroom 5y ago
    This would be cool to extract out and use within regexr[0] [0] https://regexr.com/ https://regexr.com/
    • sjrd 5y ago
      I'd be happy to help, if someone wants to take the lead, and there is buy in from the maintainers of Regexr. I believe my contact is available in my profile. Otherwise, I'm really not hard to find on the internet. ;)
  • eevilspock 5y ago
    Not directly related to your not directly related: Are there any regexp syntax that works across main language platforms (e.g. JS, C, Rust, Ruby, Go) with identical semantics? Is there a subset of each language's native regexp syntax that is common across all of them? Or perhaps a third-party regexp library that has been implemented on each language? I've found one: Google's C++ RE2, which has wrappers for many languages.
    • sjrd 5y ago
      I'm not an expert in regexes in other platforms, but already if you want a common subset between Java and JS, you're limited to the following constructs: * Literal characters * Some escape sequences for literal characters: \t \r \n \xHH \uUUUU as well as the ones for the regex metacharacters such as \[ \( etc. * Groups, sequences and alternatives * Look-ahead (positive and negative) * Look-behind, if supported (ES 2018+) * Back-references to existing groups opened before the back-references, but you need to make sure that they're not syntactically followed by a digit, otherwise parsing is different between JS and Java * Greedy and lazy quantifiers * Custom character classes with [], without intersections or inner custom character classes That's assuming you have 'u' support in JS and that you use it (ECMAScript 2015), and that you don't use any other flag. (you can use the 'g' flag in JS or not; it affects the behavior of the methods, but not of the regex itself). If you don't have 'u' support, it's only the same if you restrict your regex and your input to ASCII characters. Some things that are unexpectedly NOT portable: * Most pre-defined character classes like \s and the like * CASE_INSENSITIVE/'i' and MULTILINE/'m' * \p{...} character classes * \b and \B (there's a bug in OpenJDK: https://bugs.openjdk.java.net/browse/JDK-8264160 https://bugs.openjdk.java.net/browse/JDK-8264160)
      • slimsag 5y ago
        Also: * Named groups are not supported everywhere. * Lookahead/lookbehind are not supported in Go and Rust (unless using fancy-regexp, from what I understand) Also beware that character classes like `[]` have differing Unicode support, some operate on ASCII, unicode codepoints, or on extended grapheme clusters.. so YMMV. As you start to expand to more languages, the common feature set is _far_ more limited.
  • Siira 5y ago
    Any PCRE to JS convertor you would know of?
    • sjrd 5y ago
      I'm afraid not. Otherwise I would have had some head start for this one. ;-)
  • SonOfLilit 5y ago
    I also wrote a regex-to-regex compiler, although in my case it was for a more human-centered regex DSL with a reasonable migration story. https://www.slideshare.net/AurSaraf/re3-modern-regex-syntax-with-a-focus-on-adoption https://www.slideshare.net/AurSaraf/re3-modern-regex-syntax-... https://github.com/sonoflilit/re2 https://github.com/sonoflilit/re2
• kccqzy 5y ago
  Russ Cox's articles on regex engine remain the gold standard: https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/ I remember having built my own regex engine (for educational purposes only) following his articles almost a decade ago. Great fun. Another fun thing you can do (and I have done) is that given a regex, construct strings that fully match the regex. It's not hard at all, but it's quite subtle if you want good results. For example given the regex "a+b+" the code can simply create strings like "ab", "aab", "aaab"... (with one "b" always), but it is slightly more challenging to have it output "aab", "abb", "aabb", etc, which involves forming the Cartesian product of infinite streams in a smart way.
  • glangdale 5y ago
    They really don't (remain the gold standard, that is). Don't get me wrong: I like RE2. However, it's 2-3 fairly standard ideas taped together in an idiosyncratic way that happens to work pretty well for Google and many other users. I will confess (having designed Hyperscan), that it's 200-300 ideas ranging from 'boring as heck' to 'wildly non-standard' taped together in a idiosyncratic way that happens to work pretty well for a different subset of users (mostly in much more heavyweight network IPS cases) I frankly think we're still waiting for a 'gold standard' in regular expression implementation. I daydream of a system that doesn't have the elephantine complexity of Hyperscan (and isn't inherently tied to x86) but still supports large scale regular expression matching and streaming. Ideally this system would also not have the weird "corners" of RE2 (dynamically constructing a DFA at run-time). Even nicer: native support for 'difficult' constructs like backtracking - by native I mean "one integrated algorithm" not "first one run approach, then run the other from scratch if the fast path matches".
    • chubot 5y ago
      I feel like this is like describing GCC or Clang as "a bunch of ideas taped together". That is more or less true but also fails to capture a pretty big achievement. Or same with v8 and SpiderMonkey. They have a bunch of different optimization techniques tuned for specific workloads. That is, regexes are a rich enough language now, with enough different use cases, that I think it will be true for any future implementation. --- I think the articles themselves are great, but they're also pretty dense, and I wish there was a version for regex users, not implementers. It seems like people still have a lot of problems with the backtracking regex vs. regular language distinction in practice.
• mleonhard 5y ago
  I recently built a regex library in safe Rust: https://crates.io/crates/safe-regex https://crates.io/crates/safe-regex Regex is a mini-language and my library compiles it to Rust. Writing it was surprisingly difficult. While working on one bug, I had a moment of doubt about my ability to solve it. I've had such experiences only a few times in my life. Luckily, I woke up the next morning with the solution in my mind. The work was satisfying. I also wrote a safe Rust async library, like a mini-tokio without all the scary bits: https://crates.io/crates/safina https://crates.io/crates/safina . And I started writing a safe Rust TLS 1.3 implementation and a safe Rust HTTP library. Working on a challenging side project can bring you satisfaction, knowledge, and confidence, even if you never finish the project.
  • ridiculous_fish 5y ago
    Can you say more about "my library compiles it to Rust?" Does your library run at compile time and emit Rust code? How did you implement capture groups without allocating? For example a capture group in a loop?
    • jiggawatts 5y ago
      I'm not the author, but it looks like he's using the same general approach as other similar libraries: Rust has a fairly advanced macro system that can be used to parse input strings at compile time and output hygienic Rust code. There are safe database libraries for example that check that the SQL query and the supplied parameters match.
    • mleonhard 5y ago
      safe-regex uses a Rust Procedural Macro [0] to convert expressions like `regex!(br"ab?c+")` into a Rust code block that defines a new type and returns an instance of it. The type implements a `Matcher` interface with a function that takes a byte array, executes the regular expression against it, and returns true/false and the capture groups. Examples of the generated code are in [1]. The generated function stores capture group info on the stack. It is not recursive. It makes one pass through the input, using an NFA algorithm. It is plain Rust code that starts instantly. This instant startup time makes `safe-regex` faster on small inputs than `regex` [3] which must compile or retrieve from cache at runtime. The `regex` library has highly optimized code which implements Aho-Corasick with SIMD instructions to find substrings and then matches the regex forward or backward from each substring match, while also tracking utf-8 glyph boundaries. It's amazing. On large inputs, it is 20-500 times faster than `safe-regex` in benchmarks. I expect that the simpler and shorter code from `safe-regex` puts less pressure on the processor instruction caches, improving performance of the rest of the program and other processes running on the machine. I believe Rust's benchmark library does not measure this. The Rust compiler optimizes the generated rust code. This means that `safe-regex` gets faster as the Rust compiler gets better. It also exercises the Rust compiler like few hand-written programs do. A previous version of `safe-regex` would compile expressions like 'a?a?a?a?a?' to Rust code that rustc could not compile in reasonable time. I let it compile for an hour once and it didn't finish. I think the rustc optimizer was traversing the potential execution paths with an inefficient algorithm. The workaround was to add extra useless intermediate function calls, so the optimizer would reach some internal limit earlier and give up, allowing the compiler to continue and complete. I saved the code that showed this problem [2]. A refactoring eliminated the problem entirely. The `regex!(br"ab?c+")` syntax is intuitive for Rust users. An invalid expression fails at compile time with a decent error message. The library does not allocate on the heap. The matcher object consumes a single byte when not matching. This is all very idiomatic. Macros are difficult to fuzz test because the Rust compiler must run for each test case. Writing tests by hand is tedious. I wrote a test helper that generates input strings. It uncovered some subtle bugs. [0] https://doc.rust-lang.org/reference/procedural-macros.html https://doc.rust-lang.org/reference/procedural-macros.html [1] https://gitlab.com/leonhard-llc/safe-regex-rs/-/blob/main/safe-regex/tests/machine.rs https://gitlab.com/leonhard-llc/safe-regex-rs/-/blob/main/sa... [2] https://gitlab.com/leonhard-llc/safe-regex-rs/-/tree/main/safe-regex/src/bin https://gitlab.com/leonhard-llc/safe-regex-rs/-/tree/main/sa... [3] https://crates.io/crates/regex https://crates.io/crates/regex
• ColinEberhardt 5y ago
  I have also recently built a regex engine. In my case it was for AssemblyScript (a new TypeScript-like language that compiles to WebAssembly). https://github.com/ColinEberhardt/assemblyscript-regex https://github.com/ColinEberhardt/assemblyscript-regex I was really impressed with just how many fantastic blog posts there were that introduced the key concepts, and also how easy it was to create my own regex engine. The bigger challenge was testing. I ended up using the PCRE test suite which I transformed into a suitable test suite for my engine: https://github.com/ColinEberhardt/assemblyscript-regex/tree/main/spec https://github.com/ColinEberhardt/assemblyscript-regex/tree/...
  • sjrd 5y ago
    I'm curious: what is the advantage of a custom engine over calling the JavaScript's `RegExp` via the interop layer of Wasm<->JS? I guess you'd have to convert the Wasm input string to a JS string, but is there any other issue?
• diveanon 5y ago
  Something that I have always wished for is a more human readable dsl for regex. I don't really mind developing regex, but revisiting a complex regex years later without docs is extremely painful.
  • coldtea 5y ago
    There are a few. E.g.: https://verbalexpressions.github.io/ https://verbalexpressions.github.io/
    • diveanon 5y ago
      nice link, thanks for sharing
  • fouc 5y ago
    I agree, I would think there should be a better DSL at the finite state machines/automaton/grammar level, but designed such that regular expressions could be implemented in trivially and in a readable manner.
  • slimsag 5y ago
    Perl's regex engine actually supports defining regex in human readable groups[0] which I think is pretty nice. In my regex engine[1], I'm adding support for a blended mix of plain regex syntax and EBNF-like definition syntax, so you can do something similar. [0] https://stackoverflow.com/a/1917982 https://stackoverflow.com/a/1917982 [1] https://github.com/hexops/zorex https://github.com/hexops/zorex
  • SonOfLilit 5y ago
    I have a (mostly abandoned, since I couldn't find an organization to cbe early adopter in the time I gave myself to work on it) side project with this aim. I spent a lot of time thinking about language design, from the perspective of enabling adoption of a new language when an existing one has so much network effect: https://www.slideshare.net/AurSaraf/re3-modern-regex-syntax-with-a-focus-on-adoption https://www.slideshare.net/AurSaraf/re3-modern-regex-syntax-... https://github.com/sonoflilit/re2 https://github.com/sonoflilit/re2
• 0xmarcin 5y ago
  So it be, I have also build a simplistic regex engine: - http://blog.marcinchwedczuk.pl/matching-regexes-using-backtracking http://blog.marcinchwedczuk.pl/matching-regexes-using-backtr... - https://github.com/marcin-chwedczuk/reng/blob/master/src/pl/marcinchwedczuk/reng/BacktrackingMatcher.java https://github.com/marcin-chwedczuk/reng/blob/master/src/pl/... I was learning about continuations in LISP and how you can use them to get rid of the call stack and implement pseudo-concurrency. After reading some articles I realised that the same approach can be used to implement a backtracking regex engine in just few lines of code. I was reading about LISP, but the code is in Java. Don't judge me.
• bregma 5y ago
  Fun with regex: if you're using the GCC C++ compiler and build you application with -D_GLIBCXX_DEBUG you can call the secret `std::regex::_M_dot(std::ostream&)` member function and it will generate a graphviz illustration of the regex state machine. This was fantastically useful for developing my own regex engine.