Ironing out `regex-lite`

[CosmicHorrorDev]

Just giving a more convenient place to iron out the details behind a potential regex-lite crate that aims to be light on compile time and binary size

I'll let @BurntSushi start things off since they're more qualified and have likely given this a great deal more thought

[BurntSushi]

Thank for filing this! So I want to be clear that I'm not convinced we should actually do this. And if we do, it's probably wise to wait to land it until after #656 is done. Although one could start work on it now. (Keeping in mind that I'm still not sold on the idea.)

The high level motivation here is that the regex crate generally prioritizes performance and correctness (especially with respect to Unicode and worst case behavior) above almost all else, and this usually comes at the cost of code complexity and compilation times. Compilation times and binary sizes have gotten bad enough that folks resist using regex. This was the main reason why I added a number of Cargo features that permit disabling all Unicode support and pretty much all performance optimizations. But this still isn't enough, in part because some parts of regex are just indivisible. For example, regex-syntax is made up of a parser that converts a &str pattern to an Ast, and then a whole separate translator that converts an Ast to an Hir. Most regex engines combine these into a single step. There's also a ton of infrastructure for supporting Unicode. Then there's the NFA compiler which is pretty big. And then there's all the search and prefilter logic. Some of this gets dropped when the corresponding features are dropped, but not all of it.

I don't really see how to fix that other than just splintering off and creating a totally new and separate "lite" version of regex. It could benefit being part of this project by declaring that its syntax is roughly equivalent (explained below) and passes the same test suite. It could also benefit by declaring that its API should be identical, and so folks could pretty easily switch between them. That is, regex-lite would be a mostly drop-in replacement for regex.

OK, so how do we actually simplify things? Here's what I think:

• We drop Unicode support completely. \b is ASCII aware. Case insensitivity is ASCII-only. [^\n] and . both match the same thing and that's every single individual byte except for \n. There is no \pL. Things like \w, \s and \d are ASCII-only.
• We generally retain the same syntax. Obviously it wouldn't have the Unicode things in the current syntax. I also think we should drop all character class set operations except for the obvious union operation. So for example, there is no [a-z&&[b-g]]. Generally, the set operations are most useful with Unicode. And they represent a fair bit of complexity in the parser.
• Ideally, any syntax that is supported in regex but not supported in regex-lite would return an error/panic (see below). That way, people don't accidentally assume the same regex does the same thing.
• Decide how to handle syntax that is the same but means different things. For example, if \w is ASCII-only in regex-lite and Unicode-aware in regex, then someone switching over to regex-lite might be surprised to find out that it no longer matches the same stuff. I think we kind of just have to document this. I'm not sure if there's an alternative.
• Decide how to handle the fact that not supporting Unicode means that things like \W and . can match any individual byte and thus split a codepoint. That in turn means that if it's searching a &str, it could report match offsets that split a codepoint and thus cause &string[s..e] to panic. That's non-ideal... We might need to fix that by supporting at least UTF-8, but this is going to be a little gnarly. (That is, maybe we need to make . match a full codepoint.)
• I wonder whether regex-lite should just panic if the pattern is invalid and not worry at all about error messages. I feel like this would make the parser substantially simpler. But it's kind of a bummer to do this to people. Perhaps a compromise is to just return a pub struct Error(&'static str) with a short message indicating what went wrong instead. So basically, none of the fancy error reporting with spans and all that that's in regex-syntax currently.
• We get rid of the division between Ast and Hir and just parse a &str into an Hir. (I suspect we still need an Hir or something like it before building a matching engine. But maybe not.)
• We don't do any literal optimizations.
• We always have one internal regex engine: the PikeVM.
• We support resolving capture groups.
• We don't support RegexSet.
• It should always have zero dependencies.
• In general, when making decisions about what to do, compile times and binary sizes are weighted heavily. Certainly much more than performance. Basically, performance is a total non-goal.

Those are my initial thoughts. regex-lite might be a smaller simpler regex, but this is still a big project I think!

[CosmicHorrorDev]

Thanks for the great write-up! I'm fine with either waiting for #656 or starting on things now (although I'm very excited for the refactor 🚀)

• Decide how to handle the fact that not supporting Unicode means that things like \W and . can match any individual byte and thus split a codepoint. That in turn means that if it's searching a &str, it could report match offsets that split a codepoint and thus cause &string[s..e] to panic. That's non-ideal... We might need to fix that by supporting at least UTF-8, but this is going to be a little gnarly. (That is, maybe we need to make . match a full codepoint.)

Having &string[s..e] panic would be less than ideal to say the least. I think it would definitely be worth supporting UTF-8 if that's what we wind up settling on, even if that adds in more complexity

• I wonder whether regex-lite should just panic if the pattern is invalid and not worry at all about error messages. I feel like this would make the parser substantially simpler. But it's kind of a bummer to do this to people. Perhaps a compromise is to just return a pub struct Error(&'static str) with a short message indicating what went wrong instead. So basically, none of the fancy error reporting with spans and all that that's in regex-syntax currently.

My preferred would be pub struct Error(&'static str). I think that just panicking would be too limiting here since that would drastically limit uses where a user may provide a regex that will filter a small number of entries (for instance criterion takes a regex just to filter benchmark names)

👍 to everything else

[BurntSushi]

I think you can get started whenever. I think the thing you shouldn't do is come up with a huge test suite. We'll be able to reuse the one that I have as part of #656. Obviously you can write tests as you build, but don't go out of your way to build something huge and comprehensive. Otherwise, I don't think #656 and this project would really intersect much, by design.

I think the UTF-8 issue is going to make this gnarly unfortunately. Ideally we would just use char everywhere, but arguably, regex-lite should support searching &[u8] just like regex does. And in order to do that, you kind of need to use u8. Perhaps there's a simple way to reconcile this. But I'm not sure.

[BurntSushi]

I've been thinking more about this, and I feel like it would be helpful to write down some core data types. It will help structure thought, discussion and work on this I think.

I think the two primary data types are an Hir and State, where State is a single state in an NFA. I'll start by writing down what my initial instinct for these two types are, and then explain the problems. For Hir:

enum Hir {
  Empty,
  Char(char),
  Class(Vec<(char, char)>),
  Repetition {
    min: u32,
    max: Option<u32>,
    greedy: bool,
    child: Box<Hir>,
  },
  Capture {
    index: u32,
    name: Option<Box<str>>,
    child: Box<Hir>,
  },
  Concat(Vec<Hir>),
  Alternation(Vec<Hir>),
}

And now for State:

enum State {
  Range {
    start: char,
    end: char,
  },
  Split {
    alt1: StateID,
    alt2: StateID,
  },
  Goto {
    target: StateID,
  },
  Fail,
  Match,
}

And that's pretty much it. The core matching loop would then proceed by decoding a single rune from the haystack and applying it to the NFA state graph above. This should all work fine for &str APIs because everything is guaranteed to be valid UTF-8.

The problem comes up with the &[u8] APIs. Ideally, we would want it to be possible for things like . to match through invalid UTF-8. So for example, compile(".").is_match(b"\xFF") should return true. Another thing that seems like something we should support is compile(r"\xFF").is_match(b"\xFF") should return true. The question is how to do this. In the status quo, we complicate the above representation by adding things like State::ByteRange { start: u8, end: u8 }. And then in order to compile such things, you usually need to build UTF-8 decoding into the automaton. Which kind of stinks.

I do wonder if we might be able to take Go's approach to this problem. Go's regexp engine doesn't support the compile(r"\xFF").is_match(b"\xFF") use case, but it does permit . to match through invalid UTF-8. Basically, it does this by using lossy UTF-8 decoding in its core matching loop. Any byte that is not valid UTF-8 gets treated as indistinguishable from U+FFFD. Thus, regexes like . and things like [^a] will match invalid UTF-8 because they match U+FFFD, but they also simultaneously will never split a codepoint.

This feels like an optimal place to land for me. It keeps the implementation very simple, makes searching &str sensible and permits quite a bit of flexibility with respect to searching on &[u8] as well.

Once difference from Go is that we should probably use "substitution of maximal subparts" as our lossy UTF-8 decoding strategy. So for example, a\xF0\x9F\x87z would decode as [a, U+FFFD, z], where as in Go, that would decode as [a, U+FFFD, U+FFFD, U+FFFD, z].

Please ask questions if any of this doesn't make sense!

[spencermountain]

hi friends-
this summer I spent some time learning about wasm filesizes, and was surprised by the import size of this crate, compared to some others:

I assume this is mostly 400kb of unicode data, but this was a deterrent for my browser-oriented rust project.

I don't know if it's possible, but wouldn't it be neat if the unicode could be progressively added, as a zero-cost abstraction?

Regex::new(r"foo") // ascii-only build
Regex::new(r"Björk") // larger build?

happy to get involved in any way - am way out of my comfort zone already.
thanks!

[SimonSapin]

Decide how to handle the fact that not supporting Unicode means that things like \W and . can match any individual byte and thus split a codepoint. That in turn means that if it's searching a &str, it could report match offsets that split a codepoint and thus cause &string[s..e] to panic. That's non-ideal... We might need to fix that by supporting at least UTF-8, but this is going to be a little gnarly. (That is, maybe we need to make . match a full codepoint.)

IMO . should match a single byte if matching against &[u8] input, or a single code point if matching against &str input. I’d expect the compilation time and code size impact of supporting UTF-8 to be much much less than that of supporting Unicode case-insensitivity, character classes, etc.

[BurntSushi]

IMO . should match a single byte if matching against &[u8] input, or a single code point if matching against &str input.

That is indeed the case for regex. Well, . always matches a codepoint. It is only (?-u:.) that matches a single byte. The latter is banned in regex::Regex but allowed in regex::bytes::Regex. Generally speaking, Unicode mode is orthogonal to searching &str and &[u8], although disabling Unicode is in practice the only way to match invalid UTF-8.

I’d expect the compilation time and code size impact of supporting UTF-8 to be much much less than that of supporting Unicode case-insensitivity, character classes, etc.

Yes of course. But if you're going to make . match any arbitrary byte for &[u8], then you basically run into a whole pile of worms, both in terms of API design and simplicity of implementation:

• It would be undesirable to make . unconditionally match a single byte when searching &[u8], because then it becomes impossible to use . to match an entire codepoint when searching &[u8]. Which is an entirely reasonable thing to do.
• If one permits . to match a single byte, then you probably also need to make [^a] match a single byte. And if [^a] matches a single byte, then what does [^β] match? Do you just ban non-ASCII completely? That seems like kind of a bummer. So then you start thinking, "well let's just add a Unicode mode..." And now you're circling the complexity drain.

Basically, as soon as you start talking about matching individual bytes, you wind up with an NFA state that instead looks like this:

enum State {
  RangeByte {
    start: u8,
    end: u8,
  },
  RangeChar {
    start: char,
    end: char,
  },
  Split {
    alt1: StateID,
    alt2: StateID,
  },
  Goto {
    target: StateID,
  },
  Fail,
  Match,
}

And now your regex engine needs to know how to deal with both and you need to write an abstraction over what is considered a "character." And mixing RangeByte and RangeChar into the same NFA turns out to make things rather difficult too.

Basically, I'm trying to simplify things here so that:

• &str and &[u8] searching are as similar as possible, if not identical. Otherwise you wind up needing to choose the type of your haystack based on the regex semantics you want, and this is just quite inconvenient.
• There is no "Unicode" mode. We adhere to the semantics of &str so that we never split a codepoint, and we let people type in Unicode literals and ranges, but that's it.
• There is no "allow invalid UTF-8" mode.
• Overall avoid needing to build UTF-8 automata.