implement a DFA matcher

[BurntSushi]

One of the reasons why RE2/C++ is so fast is because it has two implementations of regex matching: a limited DFA matcher (no sub-capture support) and a full NFA simulation. This crate has the latter, but not the former.

Adding a DFA matcher should be an implementation detail and shouldn't require any public facing changes.

This is a pretty involved project. I hope to find time to do this some day, but if someone else wants to tackle it, I'd be happy to help mentor it. (Part of this will be figuring out how to handle the regex! macro. Do we replicate the DFA there too like we do the NFA?)

[WillEngler]

I'll do it!

@BurntSushi recommends that I look into an existing DFA engine by @carllerche.

I'll be starting by getting familiar with the code in this repo and RE2.

[carllerche]

Feel free to ping me on IRC or wherever if you want to talk about carllerche/automaton

[WillEngler]

Here's a summary of some research I've done and my intended next steps.

TL;DR

The algorithms that @carllerche uses in carllerche/automaton make a different time/space tradeoff than that made by RE2 and rust-lang/regex so far. For now, I recommend that we keep modeling rust-lang/regex after RE2 and use the same method of lazy DFA construction used in RE2 rather than incorporate Carl's work. However, using Carl's work to construct a DFA at compile time with the regex! macro could be a killer future enhancement.

A Comparison of rust-lang/regex, RE2, and carllerche/automaton

I consulted The Dragon Book and Russ Cox's blog series on implementing RE2 for background on algorithms for constructing and simulating automata. I'll refer to algorithms by numbers given to them in the Dragon Book for anyone who wants to take a closer look.

• RE2: Construct an NFA from a preprocessed regex using Thompson's construction (Dragon 3.3). Then, use the "Two Stacks" algorithm (Dragon 3.4) to simulate the NFA. It is also possible to use Two Stacks to simulate an equivalent DFA. Unlike backtracking NFA simulators, Two Stacks maintains a list of current NFA states and advances them in lockstep. Each list of NFA states is essentially one state of an equivalent DFA. By caching these lists, RE2 lazily constructs a DFA.
• rust-lang/regex: It uses the same approach as RE2, except it does not have lazy DFA construction built on top of Two Stacks. Right now, only NFA simulation is implemented.
• carllerche/automaton: Given an automaton, possibly an NFA, convert to a DFA using "subset construction" (Dragon 3.2). Then, walk the state graph to prune it. Finally, minimize the graph (using Dragon 3.6). Once you have a DFA, it is straightforward to simulate it in time proportional to the length of the target string.
• Tradeoffs: Let r be the length of a regex and x be the length of a target string. Constructing a DFA ahead of time (as Carl does) requires O(2^r) space. Lazy construction requires O(r) space (bearing in mind that we need to allocate a constant amount of space for the cache). Lazy DFA construction requires more computation than executing a pre-constructed DFA, but it is still O(x). So the algorithms that Carl has implemented take a fundamentally different approach than do the algorithms of RE2.

Next Steps

I say we keep modeling rust-lang/regex after RE2 and implement lazy DFA construction rather than ahead-of-time DFA construction. I see this as taking two big steps:

1. Implement DFA simulation.
2. Work out when to call on the DFA simulator and when to call on the NFA simulator depending on the question the client is asking (Is there a match? Where is the match? etc.).

Compilation of a regex into VM instructions would be unchanged.

However, the ahead-of-time approach could still be useful. Constructing a DFA at compile time with the regex! macro would be crazy cool. But I think that can wait 😄.

Questions

@carllerche: I know you and @BurntSushi were talking about folding in carllerche/automaton. Am I misunderstanding anything? Does this seem reasonable to you?

Also, many thanks to @BurntSushi for being so helpful to this Rust newbie.

[BurntSushi]

@WillEngler Sounds good to me! w.r.t. to regex!, that can be separately engineered, but its future is certainly exciting! :-)

(My new branch has some basic support for picking a matching engine on-the-fly, but the DFA is a bit more complicated since it can be beneficial to run the DFA first and then the NFA to find submatch boundaries. But this doesn't have to be in the first pass! A simple match-only DFA seems like a good initial goal to shoot for.)

[carllerche]

@WillEngler sounds accurate. My goal was to target the case of optimizing runtime at the expense of compile time with the assumption that it is easy to build the regex once at boot so trading off compile time vs. execution time is desirable.

[WillEngler]

Great! Then I'll get to work on a match-only DFA.

[WillEngler]

DFA Sitrep

I don't have anything to show for this week. If last week was about learning the theory of DFA construction, this week was about learning the implementation details. I traced and annotated Russ Cox's educational bounded-memory DFA implementation and his production implementation. I also followed @BurntSushi's major refactoring (#91) as I learned more about rustlang/regex's internals.

Expect to see some action in WillEngler/regex this week.

(Is this proper Github etiquette? I thought it would be helpful to give an update because I haven't shipped anything this week.)

[BurntSushi]

@WillEngler Updates are really good, particularly when you're still getting your bearing. If you share info with others, then you can benefit from their experience! In any case, sounds like you're on the right track. :D

[BurntSushi]

@WillEngler Oh, and please don't feel pressure to "ship" stuff!

[WillEngler]

@BurntSushi Thanks, I needed that 😄. I saw you contribute so many great additions so quickly in the refactor and I got a little intimidated. But as a beginner, it's unreasonable to expect myself to move that fast.

Onwards!