Yes, my example was bad. Consider `\pL{100}` instead. :-)

With respect to expanding repetitions on literals, that already works today. e.g.,

$ rg '(foo){100}' /dev/null --debug
...
DEBUG:grep::literals: required literal found: "foofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoofoo"

The truly eagle-eyed would notice that there are actually only 83 instances of `foo` in this string. In fact, literal detection is actually quite a tricky task on arbitrary regular expressions, and one must be careful to bound the number of and size of literals you produce. For example, the regex `\w+` matches an ~infinite number of literals, but `\w` is really just a normal character class, and some character classes are good to include in your literal analysis.

The 83 comes from the fact that 83 times 3 = 249, which buts up against a hard-coded limit in the regex engine for literal detection: https://github.com/rust-lang/regex/blob/d894c631cb6c9a062c13...

In this case, the literal detector knows that the literal is a prefix. That means a prefix match must still be confirmed by entering the regex engine. If you pass a smaller literal, e.g., `(foo){4}`, then you'll see slightly different output:

DEBUG:grep::literals: literal prefixes detected: Literals { lits: [Complete(foofoofoofoo)], limit_size: 250, limit_class: 10 }

In this case, the regex compiler sees that a literal match corresponds to an overall match of the regex, and can therefore stay out of the regex engine entirely. The "completion" analysis doesn't stop at simple regexes either, for example, `(foo){2}|(ba[rz]){2}` yields:

DEBUG:grep::literals: literal prefixes detected: Literals { lits: [Complete(foofoo), Complete(barbar), Complete(bazbar), Complete(barbaz), Complete(bazbaz)], limit_size: 250, limit_class: 10 }

This is important, because this particular pattern will probably wind up using a special SIMD multi-pattern matcher. Failing that, it will use the "advanced" version of Aho-Corasick, which is a DFA that is computed ahead-of-time without extra failure transitions (as opposed to the more general lazy DFA used by the regex engine).

Literal detection is a big part of the secret sauce of ripgrep. Pretty much every single regex you feed to a tool like ripgrep will contain a literal somewhere, and this will greatly increase search speed when compared to tools that don't do literal extraction.

Of course, literal extraction has downsides. If your literal extractor picks out a prefix that is a very very common string in your haystack, then it would probably be better to just use the regex engine instead of ping-ponging back-and-forth between the prefix searcher and the regex engine. Of course, there are probably ways to detect and stop this ping-ponging, but I haven't invested much effort in that yet. Alas, the performance improvement in the common case (literals make things faster) seems to wind up being more beneficial for the general use case.

There is more in my blog post: http://blog.burntsushi.net/ripgrep/#literal-optimizations