Can you show me the research that states how to add things like complement and intersection to general purpose regex libraries?
Most regex engines are backtracking based, and in that context, adding complement/intersection seems pretty intractable to me.
For the small subset of regex engines that are based on finite state machines, it's pretty much intractable there too outside of niche regex engines.
In fact, the research[1] suggests that adding things like complement/intersection is quite difficult:
> In particular, we show that when constructing a regular expression defining the complement of a given regular expression, a double exponential size increase cannot be avoided. Similarly, when constructing a regular expression defining the intersection of a fixed and an arbitrary number of regular expressions, an exponential and double exponential size increase, respectively, cannot be avoided.
And indeed, as another commenter pointed out, "minimal DFA" is effectively irrelevant for any general purpose regex engine. Not only do you not have the the budget to build a DFA, but you certainly don't have the budget to minimize that DFA.
With respect to reversal, RE2 and Rust's regex crate both do that. But mostly as an internal strategy for finding the start-of-match when using a lazy DFA. It's otherwise a somewhat niche feature more generally.
With respect to JITs, plenty of regex engines out there do that. PCRE comes to mind. So does V8.
As a general purpose regex engine author, we aren't "stuck" in the 80s/90s. There are just some fundamental trade offs at play here that make your ideas difficult to support. It's not like we haven't thought about it. Moreover, for things like complement and intersection specifically, actually reasoning about them in regex syntax is pretty tricky! I'm not sure if you've tried it or not. (There are some niche regex engines that implement it, like redgrep.)
>Most regex engines are backtracking based, and in that context, adding complement/intersection seems pretty intractable to me.
Most regex engines, using backtracking, already have it in the form of lookarounds. The performance penalty of such a strategy is often quite significant. Lookarounds are hard to automatically convert into intersection and complement, but if such primitives were exposed to the programmer, they could often reimplement their regexes in terms of them. It might occasionally lead to an unacceptable performance cost, but there would be many cases where it would be a desirable tradeoff.
Sorry, don't have time for that right now, but look into regular expression derivatives and similar stuff.
> Most regex engines are backtracking based, and in that context, adding complement/intersection seems pretty intractable to me.
Yeah, I wasn't really considering irregular "regexp", they don't make much sense in theory, so of course that extending them wouldn't make much sense either. Thing is, extending true regular expressions with operators like complement and concepts like weights seems like it could make the "theoretically pure" regexps more powerful *in practice* than irregular regexps (with backreferences, etc. Certainly more understandable.
> For the small subset of regex engines that are based on finite state machines, it's pretty much intractable there too outside of niche regex engines.
Don't think so. There are many examples, but mostly implemented in "functional" programming languages.
> In fact, the research[1] suggests that adding things like complement/intersection is quite difficult:
> > ...
You misunderstood the abstract. It's not saying that its difficult to translate extended RE (RE with these additional operators) to finite automata, it's just saying that translating extended RE to traditional RE can cause a huge blowup (something I already hinted at in the comment above). So this is a pro, not a con.
> And indeed, as another commenter pointed out, "minimal DFA" is effectively irrelevant for any general purpose regex engine. Not only do you not have the the budget to build a DFA, but you certainly don't have the budget to minimize that DFA.
It's possible to produce NFA directly from extended RE, see "Antimirov derivatives" for a start. The original Antimirov derivatives don't support complementation and similar, but there are extensions that do. Search for something like "partial derivatives regular expression complement", or "derived term automata complement".
> niche regex engines that implement it, like redgrep
Thanks for the pointer.
Obviously, I have. There's a reason why there isn't a single general purpose regex engine that uses regex derivatives. They build full DFAs and full DFAs take worst case exponential time and space.
> Don't think so. There are many examples, but mostly implemented in "functional" programming languages.
Oh I think so. Feel free to link to some examples of general purpose regex engines that implement these things.
> You misunderstood the abstract. It's not saying that its difficult to translate extended RE (RE with these additional operators) to finite automata, it's just saying that translating extended RE to traditional RE can cause a huge blowup (something I already hinted at in the comment above). So this is a pro, not a con.
No, I'm not misunderstanding anything. The bottom line is that if you have an NFA with N states and you take its complement (how do you do that without first converting it to a DFA?), then you could wind up with an NFA containing a number of states exponential in N.
What's happening here is that you aren't quite appreciating what it means to engineer a general purpose regex engine.
All of these things you're talking about are all doable and implementable in niche regex engine libraries that serve a particular purpose. And it's all been done before. What I'm talking about here are general purpose regex engines, where you can't afford quadratic time during regex compilation (which is why Thompson's construction is so popular), nevermind exponential time.
And all of this is rooted in me taking objection to your characterization of regex engines being "stuck" in the 80s/90s. I'm trying to explain to you why that's not the case.
In theory, practice and theory are the same. In practice, they're totally different.
> It's possible to produce NFA directly from extended RE, see "Antimirov derivatives" for a start.
I know. I'm not talking about what's "possible." I'm talking about what's feasible from engineering perspective. As far as I know, building such an NFA takes O(n^2) time, which is a hard sell in a general purpose regex engine.
> The bottom line is that if you have an NFA with N states and you take its complement (how do you do that without first converting it to a DFA?), then you could wind up with an NFA containing a number of states exponential in N.
Are you sure that a less naive approach doesn't exist? Genuinely asking, I'm not an expert. I don't quite remember the contents, but I know there are some papers with extensions to Antimirov derivatives (see updated upthread comment) that support taking the complement of an expression.
I don't think so. There's a reason why exactly zero popular regex engines build full DFAs. (Sometimes small DFAs are built in cases where you know they'll be very small or enforce a tight bound, but even then, the DFA is typically used as a prefilter rather than a regex engine unto itself.)
There are plenty of regex engines that do build full DFAs, but they're either relegated to the work of research or niche areas. re2c, for example, is an excellent regex engine that translates regex syntax into DFA source code. It thus has procedures for compilation and execution, but it is not what I would call a "general purpose" regex engine.
As another example, if I were to make Rust's regex crate use quadratic (or far worse, exponential) compilation, I'm pretty sure I'd have many upset users. (Now, I could use quadratic or even exponential compilation in cases where I'm sure that the absolute wall clock time won't be disagreeable, but I think it's safe to exclude such things for the purposes of this discussion.)
Even for DFAs that don't take exponential time, Unicode means that DFAs get obscenely big. \pL, for example, is 279 states and uses 143K of memory. And it takes around 8ms to compile on my machine. 1ms is already pushing it.
> Are you sure that a less naive approach doesn't exist?
Pretty sure. I'm not an expert in the theory either. I'm just aware of most of it. And I'm totally unaware of anyone who has overcome the practical engineering challenges of things like complement and intersection.
Vcsn link: https://www.lrde.epita.fr/wiki/Vcsn
I don't know, maybe just don't make grand pronouncements about regex engines if you aren't actually familiar with how they're implemented and the engineering tradeoffs in play?
It's like how character class set notation has a 'negation' feature. e.g., '[a-z]' matches a-z, but '[^a-z]' matches anything except for 'a-z'. So you might say, "why bother with adding negation when you can just check if the original char class would fail?" The answer is that without negation embedded in the regex itself, you miss out on composition.
This is another reason why features like complement and intersection aren't particularly popular. They are weird to reason about. Another reason is that many of their use cases can be achieved through other means. For example, my example above could conceivably be done by iterating over all words (using word segmentation, for example) and just checking whether each matches 'foo' or not. It could also likely be accomplished through the use of negative look-around, commonly found in backtracking regex engines and not finite automata based regex engines.
> who has implemented an excellent ...
This is an appeal to authority.
> being exceedingly generous to your point of view
Now you're just insulting me!?
> you being the opposite of generous
Consider that I couldn't have known upfront that burntsushi is acquainted to any degree with RE derivatives and similar concepts. His regexp engine is not based on them AFAIK. So I pointed to those for a start. Later in the discussion, including in the same comment, I pointed to other sources, too. So I think it's not fair to call me ungenerous.
The whole "general-purpose regex engine" thing was moving the goalposts in the first place and not very relevant to this whole discussion anyway. EDIT: I'm not saying that these distinctions don't matter at all, rather what I want to say is that it doesn't make sense to implicitly call upon a subjective and arbitrary standard.
I don't think it's so much "what you said" or even "who you said it to" but "how you said it". Most of us are coming to this thread specifically because we _don't_ already have specialized knowledge in this area, and we were hoping to learn something. It's totally reasonable not to have time to explain something this complicated, but it comes across as a bit disingenuous when followed by many additional comments in the thread continuing to debate in what looks to be close to real time. I think in this case, people are downvoting more for a breach of "decorum" than for anything else; you might very well be correct in your assertions about regexes, but it's impossible for any non-experts to tell, so we end up seeing (fairly or not) picture of someone who is more interesting in spending time arguing that they're right than actually demonstrating it.
Not so much for disagreeing. More for engaging a lower-effort way (than the person you were talking to) and appearing to assume that burntsushi was coming from a place of ignorance.
> The whole "general-purpose regex engine" thing was moving the goalposts in the first place and not very relevant to this whole discussion anyway. EDIT: I'm not saying that these distinctions don't matter at all, rather what I want to say is that it doesn't make sense to implicitly call upon a subjective and arbitrary standard.
"general-purpose regex engine" is a direct response to "most regexp libraries are stuck in the 80s/90s". It's about why the regex libraries most people use (the general-purpose ones) haven't adopted the ideas that you're advocating. Seems on-point to me; on HN most readers will be mainly familiar with the general-purpose libraries, so they'll be thinking in terms of those.
I understand how you might think this. However, please consider that the statement you were responding to is establishing a bonafide - a reason why burntsushi's words might be worth consideration.
Sometimes an appeal to authority is not wrong.
In my experience, the more I study a topic, the smarter other folks appear.
Yes, this is exactly why extending RE is necessary.
(this would have been an edit, but I'm out of the window)
My lib’s show HN which addresses most of his concerns, royally got 5 votes.
Given that Rulex was obviously a success, I didn’t feel like my comment would take from them.
Also, the discrepancy between the upvotes on that comment and the lack of uptick for compose-regexp felt interesting to point out
Although not JIT in that it needs the regex specified at compile time, both Rust and C++ (using the compile time reflex library) can generate the code to evaluate the regex at compile time.
The reflex library is interesting, but more like a C++ template hack. Its codegen is impressive, but it's missing (last time I checked) a lot of the classical optimizations that a regex engine typically has. Like a literal prefilter scan.
As an aside, my impression is that Rust developers are using macros less now than they were even a couple of years ago. It seemed a few years ago, a lot of people coming to Rust were impressed by the power of macros (especially procedural) and used them in a lot of libraries. It seems now, people are realizing the costs of macros to tooling and understandability, and are using them more judiciously.
It should be noted that none of them build out complete DFAs in the general case. Building a DFA is worst case exponential time and space, and they can in practice be expensive even when not hitting the worst case.
Instead, they use different techniques. RE2 and the regex crate, for example, use a hybrid NFA/DFA that does subset construction at search time. Outside of pathological cases, it provides the speed of a DFA without needing to build the whole thing up front.
Hyperscan is also built on finite automata. GNU grep uses finite automata in many cases too.
PCRE is the pinnacle of deceptive advertising. It is emphatically not Perl-Compatible.
Source: I used to write Perl for a living, and I have battle scars from (¹) above.
To me, it was inconceivable that you could release a major language and not only not have regular expressions built into the language like Perl, but not even have it in the standard library. Crazy.
Rust has a different target problem space, a different standard library philosophy, a package management system, and exists in a world where adding external dependencies is trivial.
Java didn’t have any of those excuses.
The Rust regex crate is also DFA based and safe for untrusted inputs.
In fact for both .NET v5 and v7, they specifically did work to improve the performance of regexes. For example there is a new non-backtracking option. https://devblogs.microsoft.com/dotnet/regular-expression-imp...
You're very wrong, backreferences in general can't be translated to finite automata (NFA is short for nondeterministic finite automaton). See these comments:
> resistant to catastrophic backtracking despite features which normally translate to nfa
I interpret this as you equating NFA with backtracking engines, which would be incorrect. Is my interpretation wrong?
Stephen has put incredible work into having an alternative implementation in .net 7.
For anyone interested in regex engine inner workings and optimizations, including SIMD, the blog post is fantastic.
The design philosophy behind RE2 for those unfamiliar with the library: https://github.com/google/re2/wiki/WhyRE2
OK, but the painful syntax is the biggest problem for regular expressions!
I actually had complement in it as a 5th construct, but when the submission came closer and the examiners found some errors in my logic (my fault for not writing good enough unit tests!), I took complement out again when cleaning the project up.
In any case, I built your program with 'stack install' but got this when I tried to use it with Unicode:
$ hgrep-exe '^\pL{42}$' OpenSubtitles2018.raw.sample.en
hgrep-exe: Maybe.fromJust: Nothing
$ echo 'β' > /tmp/beta
$ echo 'b' /tmp/b
$ hgrep-exe '\w' /tmp/beta
$ hgrep-exe '\w' /tmp/b
$
$ hgrep-exe '[a-z]' /tmp/b
$ hgrep-exe 'b' /tmp/b
b
I don't know. I'm not sure how to do a Unicode stress test with your tool.
Not that this was just an university project that is far from polished, and certainly not fast!
* I don't think it supports '\w' - is that part of the ERE? (otherwise I will lower my claim in the project description)
* Repetition works like this: {1,3}, did not add the syntactic sugar
---------
My setup:
me:~/hgrep-smallcore$ echo 'awd え bbb c' > test
me:~/hgrep-smallcore$ /home/me/.local/bin/hgrep-exe 'f' test
me:~/hgrep-smallcore$ /home/me/.local/bin/hgrep-exe 'b{1,3}' test
awd え bbb c
me:~/hgrep-smallcore$ /home/me/.local/bin/hgrep-exe 'え' test
awd え bbb c
But upon looking at the POSIX ERE spec, yes, it looks like technically things like \w, \d and \s are not in it. But most ERE implementations, including both BSD grep and GNU grep, support constructs like \w. (Yet another reason to cast a suspicious eye on folks who obsess about portability. Portability means following a spec, not using whatever your tool lets you do. And most tools let you do far more than what's in the spec because the spec---especially one like POSIX---is usually divorced from the reality of what's useful.)
I understand your tool is a university project. The main point I'm trying to drive home here is that there are folks in this thread that seem to not be keen on acknowledging engineering challenges and are instead only looking at the theory. Unicode, for example, is an enormous engineering challenge. It's not difficult because getting it correct is difficult, it's difficult because making it correct and fast is not straight-forward. As you show, using a naive representation (sparse transitions, hash sets for states) will give you correctness without much complexity. But that's not usually what we mean when we talking about supporting Unicode in general purpose regex engines. Because "general purpose" means folks expect it to be minimally fast.
> It's not difficult because getting it correct is difficult, it's difficult because making it correct and fast is not straight-forward.
It seems to me that you take my project as a proxy for whether regex derivations are a feasible way to deal with unicode-ready regexes that also support complements and so on. That was not my intention, I was merely attempting to show an easy implementation of regex derivations that can deal with unicode and can be extended to support complements. With this project and the paper I linked, it seems to me that answering whether this particular kind of constructing regex DFAs is a possible way to achieve what you are looking for or not should be rather straightforward.
(To my last knowledge, a regex complement is not easy to add in the presence of extra features like backtracing and lookahead.)
Yes, you're correct. It just isn't that interesting because it will fall over in any kind of real practical usage. :-) Full disclosure, I'm the author of ripgrep, so I have some particularly relevant experience in the specific domain of making regexes work well for the masses. (It also forms my bias with what I care about.)
Like I said, I wasn't necessarily trying to pick on you. There are others in this thread that are seemingly ignoring the engineering challenges, and only looking at the theory. Then using that as a basis to proclaim that regex engines are "stuck" in the 80s/90s.
Consider my perspective here: if someone pipes up and says, "yeah hey it is actually easy to add those kinds of features to regex engines." Well, then, it's important to include the caveats with that. That's what I see as my role in this thread. Otherwise, it looks like general purpose regex engines are crippled for no apparent reason.
All good, thank you for sharing your POV! I find both theory and the practical engineering feats quite interesting, and actually understood the original question as a theoretical question, not a question about general-purpose regex engine. Quite possibly that this is even how the asking person was intending it, in hindsight.
Last thing on topic (talking now about having complement and unicode in a usable regex engine): My personal, gut-feeling-based hunch is that by adding all these features not strictly related to regular languages, we kind of evolved our regex enginges and expectations towards them into a corner of the design space that works well, but might not work well when one adds complement. It feels like a constructivist world without negation and stuff on top that works, and reverse-engineering what works with negation and what not will likely be hard work. As a theory-ish kind of person (without much insight into regexes or formal grammars), I wish there would be some kind of insight into what are the atoms of a regex and which atoms can be combined witch which other atoms - I would bet that fancyFeatures and unicode+complement would have a high algorithmic complexity already in theory.
Any final tipps on the repo I linked to not disappoint users expectations? :)
The incentive structure of academia that leads to software like that, though, is also a big reason why I left. The theory is super important (that's why I work on a regex engine that only provides support for regular languages), but I also think the engineering aspect is just as important. And academia, or at least the corner I was in, just did not care about the engineering side of things at all. This in turn leads to publishing results that are hard to reproduce, because if you don't share code that is at least somewhat robust, it's going to be very costly for someone else to build on your work.
Anyway, sorry about the side rant haha. But all good.
> The incentive structure of academia that leads to software like that, though, is also a big reason why I left. The theory is super important (that's why I work on a regex engine that only provides support for regular languages), but I also think the engineering aspect is just as important. And academia, or at least the corner I was in, just did not care about the engineering side of things at all. This in turn leads to publishing results that are hard to reproduce, because if you don't share code that is at least somewhat robust, it's going to be very costly for someone else to build on your work.
Totally get it. This also baffles me - papers in computer science that are hard to reproduce? Yes I know, publish or perish and all that BS. But I don't want to accept this: I mean I get it for psychology obviously, and then also material sciences and so on, but for compsci?... Next to proofs, programs are probably one of the most reproducible things that nature has given given us.
Good for me and many others that you cho(o)se to spend your time on building tools :)
The unwashed ones?
The relevant standard is UTS #18, it subsumes POSIX afaict. Do you think the same as me about it, namely that following and implementing it is essential?
To redirect to UTS#18, I don't think UTS#18 subsumes POSIX. UTS#18 doesn't support [[=a=]] for example AFAIK. And UTS#18 more generally doesn't require locale support. UTS#18 Level 3 was actually removed from the spec, which is where "custom tailored" logic for specific locales used to live. On top of that, POSIX also specifies BREs which UTS#18 doesn't touch. So while there is overlap between POSIX and UTS#18, POSIX is not a strict subset of UTS#18. If you're speaking "conceptually" and less precisely, you can maybe say POSIX is subsumed by UTS#18 though. I don't really think about it that way though personally. They serve two different use cases that are still relevant today.
I think UTS#18 is a tortured document, but yes, the regex crate supports pretty much all of UTS#18 Level 1: https://github.com/rust-lang/regex/blob/master/UNICODE.md
Going beyond Level 1 is difficult.
I suppose you could use a programming environment that forbids partial functions, but I'm unclear on how productive that is.
> And a language without purity as a concept like Rust has achieved frankly a more tight feeling of safety and great flexibility despite having a more simple typesystem.
Haskell has 'fromJust' and Rust has 'unwrap'. They're both exactly equivalent and result in similarly poor failure modes. (Well, 'unwrap' usually at least gives you a line number.)
When someone who truly believed in that Haskell could be a proper modern programming tool and invested their hard work and frankly their genius into it, they Haskell leadership responded with skepticism and inaction. I bet if you gave Snoyman full dictatorship over a new Haskell prelude, it would be the best general purpose programming language by a mile for the next decade at least. Instead Haskell will remain as backwards as its ISO 8859-1 String type.
I used to use Haskell too and I stopped using it for $reasons. Nothing to do with the prelude or its string type though. More about the nature of the language and paradigm itself.
This function and others are in the prelude, but one can use other preludes that don't have these escape hatches.
This does not undermine the huge benefits that people get from having IO checked by the typesystem. Just as having tyepcasting in a language does not undermine the benefits of types in that language.
If it is not practical matters that are the concern here, there are more than enough languages that only allow total functions and offer other sweet stuff. Haskell's main purpose was to be a lazy-by-default-language, and that people can actually write practical stuff in it is a nice side-effect.
EDIT: If malicious inputs are something to be worried about, I think a good way to do this would be to check for exceedingly costly blowups of various kinds during/after translation to a finite automaton (so before automaton execution). This would enable having complemented expressions when safe (in lots of cases, at least).
For example, most regexp languages basically only have the traditional three operators of alternation, concatenation and closure/iteration. It's not necessary to stop there: the regular languages are closed under various other useful operators. Many of these operators don't even significantly increase the size of the minimal DFA.
For example, the complement (as in set/language complement) and reversal/mirror image would be some basic additions that seem like they should be necessary nowadays. Using them can make the regular expression much shorter, nicer and more understandable. For the complement, this should come at no cost for the minimal DFA size.
Some other viable operators are: intersection, set difference, merge (AKA shuffle), infiltration (also sometimes known as shuffle), interleaving.
Some other possibilites for regexp that could be put to good use more are:
* weighted regular expressions: these enable more power in a very elegant way, the idea is that programmers don't want just recognizers, so why limit regexps or finite automata to just that.
* JIT. It should be possible to compile regexps with libgccjit or with llvm.