google

redgrep

C++2015–2026

google / redgrep · Archived

redgrep

♥ Janusz Brzozowski

Explore on GitHub Read Hacker News discussions

7Distinct people

12Mentions

0Explicit recommenders

165GitHub stars

REPOSITORY AT A GLANCE

What to know before exploring

What it is

♥ Janusz Brzozowski

GitHub

Where it is used

No documented product use has been verified yet.

What people are saying

No recommendation phrase was found in the indexed comments.

No classified warning is attached to this page. Read the discussions before treating silence as approval.

Also in these discussions

google/re2 · linked in 2 of the same discussions

Mentioned in the same Hacker News threads. That is not proof they are substitutes.

This week on Hacker News

Nov 7–Nov 14 UTC · Direct repository links and separately labeled related project stories. Indexed through 11/14/2026, 12:54:37 PM UTC.

No direct repository links were found in the indexed HN discussions over the past seven days. Older discussions are available below.

Mentions over time

HN mentions by year12 dated mentions

Observed mentions: 2015-10-21 01:44:39 UTC to 2026-03-24 11:17:04 UTC.

* An incomplete calendar period is marked with an outlined bar. Its count is not directly comparable with a full period.

Counts come from the repository’s dated source evidence. Index cutoff: 2026-11-02 08:16:59 UTC.

View mention counts and date ranges

UTC ranges include their start and exclude their end. Select a period to filter the source evidence.
Period	Start (UTC)	End (exclusive, UTC)	Mentions	Submissions	Comments
2015	2015-01-01 00:00:00 UTC	2016-01-01 00:00:00 UTC	1	0	1
2016	2016-01-01 00:00:00 UTC	2017-01-01 00:00:00 UTC	0	0	0
2017	2017-01-01 00:00:00 UTC	2018-01-01 00:00:00 UTC	1	0	1
2018	2018-01-01 00:00:00 UTC	2019-01-01 00:00:00 UTC	0	0	0
2019	2019-01-01 00:00:00 UTC	2020-01-01 00:00:00 UTC	1	0	1
2020	2020-01-01 00:00:00 UTC	2021-01-01 00:00:00 UTC	0	0	0
2021	2021-01-01 00:00:00 UTC	2022-01-01 00:00:00 UTC	5	1	4
2022	2022-01-01 00:00:00 UTC	2023-01-01 00:00:00 UTC	0	0	0
2023	2023-01-01 00:00:00 UTC	2024-01-01 00:00:00 UTC	2	0	2
2024	2024-01-01 00:00:00 UTC	2025-01-01 00:00:00 UTC	0	0	0
2025	2025-01-01 00:00:00 UTC	2026-01-01 00:00:00 UTC	1	0	1
2026 (partial)	2026-01-01 00:00:00 UTC	2027-01-01 00:00:00 UTC	1	0	1

What Hacker News says

12 sources

davidgrenier·Mar 24, 2026

I wonder how gracefully redgrep handles this. This tool hasn't been talked about since the year of its release. If I recall correctly, it doesn't handle some obstruse regexes the way conventional tools do however. https://github.com/google/redgrep

In Finding all regex matches has always been O(n²)

eru·Dec 23, 2025

See https://en.wikipedia.org/wiki/Regular_language#Closure_prope... The complement of a regular language is a regular language, and for any given regular language we can check whether a string is a member of that language in O(length of the string) time. Yes, depending on how you represent your regular language, the complement operator might not work play nicely with that representation. But eg it's fairly trivial for finite state machines or when matching via Brzozowski derivatives. See https://en.wikipedia.org/wiki/Brzozowski_derivative See also https://github.com/google/redgrep Regular languages have a bunch of closure properties. In practice, intersection and complement are really useful. So you can say things like: [regular_expression_for_matching_email_addresses] & ![my_list_of_naughty_words] Exercise for the reader: expand the e

Read the rest

xpression above to allow the town of 'Scunthorpe'.

In Chomsky and the Two Cultures of Statistical Learning (2011)

burntsushi·Sep 9, 2023

> If it's actually a _regular_ expression, by definition re2 will support it. Hmmm, kinda sorta. Regular languages are closed under complement and intersection, but RE2 doesn't support them. They are difficult to implement efficiently, particularly with respect to building the regex. There are some issues on the RE2 issue tracker about this. Of course, you could say that you could always rewrite a regex using complement or intersection to an equivalent regex that doesn't use those operations. While true, such a feat is usually quite tricky. So treat this comment as adding more clarity as opposed to me trying to correct you perhaps. :-) Complement and intersection are not implemented in any "general purpose" regex engine that I know of. You tend to find them in more specialty projects like redgrep[1] or in libraries specifically devoted to

Read the rest

the construction and manipulation of DFAs. (RE2 doesn't have such a thing, only a lazy DFA, because full DFAs are too expensive to build in the "general purpose" context.) [1]: https://github.com/google/redgrep

In Debugging catastrophic backtracking for regular expressions in Python

c0nstantine·Mar 7, 2023

I don't think Rust regex engine relies on this technique. I guess the main point is when you construct the DFA directly you still have the possibility of the exponential explosion of the number of states. That's why modern engines balance between NFA/DFA and lazy DFA. Though there is an implementation that relies only on Brzozowski derivatives: https://github.com/google/redgrep

In Show HN: Regex Derivatives (Brzozowski Derivatives)

pabs3·Apr 27, 2021Submission

Redgrep – grep based on regex derivatives, matches in linear time

2 points · Open discussion

burntsushi·Mar 14, 2021

> About large character classes: how are those harder than in approaches? If you build any FSM you have to deal with those, don't you? I mean specifically in the context of derivatives. IIRC, the formulation used in Turon's paper wasn't amenable to large classes. Yes, interval sets work great: https://github.com/rust-lang/regex/blob/master/regex-syntax/... This is why I asked if a production grade regex engine based on derivatives exists. Because I want to see how the engineering is actually done. > What do you want your capture groups to do? Do you eg just want to return pointers to where you captured them (if any)? Look at any production grade regex engine. It will implement captures. It should do what they do. > I have an inkling that something inspired by https://en.wikipedia.org/wiki/Viterbi_algorithm might work. Nothing about Viterb

Read the rest

i is fast, in my experience implementing it in the past. :-) > https://github.com/google/redgrep/blob/main/parser.yy mentions something about capture, but not sure if that has anything to do with capture groups. It looks like it does, and in particular see: https://github.com/google/redgrep/blob/6b9d5b02753c4ece17e2f... But that's only for parsing the regex itself. I don't see any match APIs that utilize them. I wouldn't expect to either, because you can't implement capturing inside a DFA. (You need a tagged DFA, which is a strictly more powerful thing. But in that case, the DFA size explodes. See the re2c project and their associated papers.) If I'm remembering correctly, I think the problem with derivatives is that they jump straight to a DFA. You can't do that in a production regex engine because a DFA's worst case size is exponential in the size of the regex.

In Speed of Rust vs. C

eru·Mar 14, 2021

I've made some attempts, but nothing production grade. About large character classes: how are those harder than in approaches? If you build any FSM you have to deal with those, don't you? One way to handle them that works well when the characters in your classes are mostly next to each other unicode, is to express your state transition function as an 'interval map' What I mean is that eg a hash table or an array lets you build representations of mathematical functions that map points to values. You want something that can model a step function. You can either roll your own, or write something around a sorted-map data structure. Eg in C++ you'd base the whole thing around https://en.cppreference.com/w/cpp/container/map/upper_bound (or https://hackage.haskell.org/package/containers-0.4.0.0/docs/... in Haskell.) The keys in your sorted map

Read the rest

are the 'edges' of your characters classes (eg where they start and end). Does that make sense? Or am I misunderstanding the problem? > I personally always get stuck at how to handle things like captures [...] Let me think about that one for a while. Some Googling suggests https://github.com/elfsternberg/barre but they don't seem to support intersection, complement or stripping prefixes. What do you want your capture groups to do? Do you eg just want to return pointers to where you captured them (if any)? I have an inkling that something inspired by https://en.wikipedia.org/wiki/Viterbi_algorithm might work. https://github.com/google/redgrep/blob/main/parser.yy mentions something about capture, but not sure if that has anything to do with capture groups.

In Speed of Rust vs. C

eru·Mar 14, 2021

It couldn't figure it out from looking through ripgrep's website: does ripgrep support intersection and complement of expressions? Like eg https://github.com/google/redgrep does. Regular languages are closed under those operations after all.

In Speed of Rust vs. C

burntsushi·Jan 1, 2021

Most popular regex engines use backtracking and support non-regular features. They aren't based on automata, so implementing AND is perhaps not as theoretically straight-forward in that context. There are some popular finite automata based engines though. RE2 comes to mind. In theory, things like AND and complement could be implemented, but in practice, they blow up the size of the state machine.[1, 2] The current maintainer of RE2 did build a tool that permits intersection and complement though.[3] [1] - https://dl.acm.org/doi/10.1145/2071368.2071372 [2] - https://github.com/google/re2/issues/156#issuecomment-354068... [3] - https://github.com/google/redgrep

In State machines are wonderful tools

chubot·Jun 30, 2019

RE2 was used in Google Code Search in an adversarial context, and it handles the DFA issue by simply putting an 8MB limit on the DFA for a regex: https://github.com/google/re2/blob/master/re2/re2.h#L601 I learned a few months ago that Rust's regex crate, which is based heavily on RE2, does the same thing. There is perhaps something worth exploring there, but after reading the Cox articles, I can see that there are so many issues that come up in regex implementation, and this seems to be one of the smaller ones. I don't think the "regex as untrusted data" use case is very common. That is, there are probably 10,000 programs that use regexes for every one that accepts regexes from users. ----- Although, one thing I've wanted to explore is Regex derivatives. Supposedly that technique constructs an optimal DFA directly. You don't have to ma

Read the rest

ke an NFA, convert it to a DFA, and then optimize the DFA. Cox describes it as a "win-win" here (in contrast to parsing with derivatives, which is asymptotically worse than traditional parsing algorithms) https://research.swtch.com/yaccalive There a bunch of non-production implementations floating around like https://github.com/google/redgrep https://github.com/MichaelPaddon/epsilon (This technique was revived by the 2009 paper cited) ----- Regarding the blog post, I have some material here. I gave about 10% of this as a 5-minute talk, and realized it's about 2 hours worth of material. https://www.oilshell.org/share/05-31-pres.html I still think the table toward the end is a good summary and perhaps worth publishing with some more context / explanation. ---- One interesting test of whether the message from Cox's articles got through is what style of regex engine newer languages are using. I just noticed Julia uses PCRE, which is unfortunate IMO. I like RE2 -- it has a nice API, great performance, and a lot of features. https://docs.julialang.org/en/v1/manual/strings/index.html#R... Swift also has Perl-style regexes, but maybe they inherited it from Objective C: https://developer.apple.com/documentation/foundation/nsregul... So basically Rust is the only newer language that appears to have gotten the message. The Oil shell will of course use "regular languages" rather than regexes, but that's natural because shell never had Perl-style regexes. One thing I think Cox didn't explore enough is that most libc's appear to be using the "fast" good method, because they don't need Perl constructs. I guess that would be a good follow-up article. To test GNU libc and musl libc on those pathological cases. I looked at their code a few years ago and they looked "right" (I've forgotten the details), but I don't think I ever did the test.

In Regular Expression Matching Can Be Simple and Fast (2007)

eru·Jul 6, 2017

There's also redgrep (https://github.com/google/redgrep) that supports intersection and complements of regular expressions. I am toying the idea of writing a little game where player A thinks of a regular expression, and player B tries to guess. If B guesses right, they win. If B guesses wrong, A has to provide a false positive and a false negative (if they exist), and B gets to guess again. Can you think of ways to automate the roles of A and/or B?

In Regex Puzzle

jonstewart·Oct 21, 2015

- With a PCRE/RE2-like NFA implementation, where you have green threads representing the states in the automata, you can just store the start of match in the thread. You do have to be careful then about not killing some threads off. If HyperScan is a DFA, though, then SoM is indeed hard. - Redgrep is a cool project by Paul Wankadia that uses LLVM to JIT regexp automata into machine code. https://github.com/google/redgrep. The two things that are tough about JITting for very large automata, though, are breaking the code up into functions (a compiler can't deal with one gigantor block), and all that entails, and the fact that a machine code representation of a large automaton might be many times bigger than a more traditional representation, so what you gain in decode time you lose on L3 cache hits. - I don't grok what you mean about predic

Read the rest

ting the future wrt/ lazy/greedy quantification. With lazy quantification, you can stop producing matches once you've gotten the first match (or once you've moved past the quantification iff the subsequent subpattern and the quantification subpattern are disjoint). Looking for "<html>.+</html>" in a large stream is very bad, whereas looking for "<html>.+?</html>" is almost certainly what's desired. - Capturing in a streaming mode just doesn't seem worth it. - Large spans of bounded repetition are indeed the devil. It should be possible to replace states with a counter, but I think it requires dynamic mallocs (though I haven't worked on it yet).

In Hyperscan, a high-performance multiple regex matching library