PApabs3·Apr 27, 2021Submission
Redgrep – grep based on regex derivatives, matches in linear time
2 points · Open discussiongoogle
redgrep
C++2015–2026
google / redgrep · Archived
redgrep
♥ Janusz Brzozowski
7Distinct people
12Mentions
0Explicit recommenders
165GitHub stars
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 8–Nov 15 UTC · Direct repository links and separately labeled related project stories. Indexed through 11/15/2026, 4:00:59 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
| 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
5 sources> 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.
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.
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. CMost 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