Hacker News Reader

Hyperscan may be idiosyncratic but is quite an accomplishment, and by all accounts the fastest there is, kudos!

Do you know of any resources describing how to handle 'difficult' constructs in DFAs? Capture groups, zero-width assertions, and high-trip-count loops are examples: these are all straightforward in pcre-style backtracking, but require novel techniques in DFAs. Some of these techniques are research papers (tagged DFAs), some are yet-to-be-written papers (re2 drives the loop "one ahead" for zero-width assertions), some are open questions. What's the path forward here?

These difficult constructs are a brace of unpleasant questions, all quite distinct. Laurikari has some good work on capturing; we also did capturing in Hyperscan in an unreleased branch during the closed-source days (idea: run a trace of states from the NFA backward, then follow the trace forward, emulating what a backtracker would do).

Zero-width assertions are painful for automata-based approaches, especially forwards asserts. Backward asserts are easy in an bit-parallel NFA although I'm not aware of anyone actually doing that (you just need to have special "AND" states rather than the usual relation of being OR'd on if any of your predecessors are on). Even streaming would be doable.

As a rule, forward asserts are ugly and are "as easy to do as determinizing the two patterns together from that point on" - which can be trivial, or it can be a horrible world-smashing explosion.

High trip count loops were a lot of work in Hyperscan. We special-cased out the single-character width ones to properly handle /foo.{1500}bar/ and the like, but of course even Unicode can screw this up; something as trivial as /foo.{100,200}bar/ with anything but "dot means any single byte" - e.g. UTF-8, or even a 2-byte code unit of any size - much harder.

Wrapping a fully general regular expression inside a large bounded repeat is a nightmare. I have some ideas kicking around for how to do this that I've toyed with for years.

As might be apparent, I'm thinking of returning to the general regular expression fray (probably with a new project), so I've been thinking a lot about this stuff.

I feel like this is like describing GCC or Clang as "a bunch of ideas taped together". That is more or less true but also fails to capture a pretty big achievement.

Or same with v8 and SpiderMonkey. They have a bunch of different optimization techniques tuned for specific workloads.

That is, regexes are a rich enough language now, with enough different use cases, that I think it will be true for any future implementation.

---

I think the articles themselves are great, but they're also pretty dense, and I wish there was a version for regex users, not implementers. It seems like people still have a lot of problems with the backtracking regex vs. regular language distinction in practice.

GCC and Clang have phases that communicate synergistically. If I'm working on instruction scheduling, I can get the benefits of an upstream pass that did code motion. Conversely, if I'm working on a backend for x86, I can both share benefit of the front-end generic optimizations with an ARM backend [ edit: and not be concerned about what's going on in the other backend as well ]

By contrast, both Hyperscan and RE2 have a tendency to just throw different, well understood techniques at the problem of matching regular expressions, without necessarily getting much decomposition of the problem. Hyperscan goes further but at great expense and complexity - and many of the decisions we made are very "one size fits all".

One of the consequences of this is that the regex vs regular language distinction you speak of tends to pop up aggressively and annoyingly, even when there are perfectly good possibilities for a solution that integrates automata and back-tracking based matching. RE2 handles this by taping back-tracking to a automata-based approach, and Hyperscan doesn't solve this at all (unless you count Chimera, which tapes libpcre to Hyperscan).

Users probably shouldn't have to know about the underlying engine, but the other problem of the idiosyncratic nature of all of our 'taping' jobs is that each system has weird corners that users can wind up suddenly finding out about (and often can't really control). My dream library would allow users to indicate which tradeoffs they want (potentially telling them to "go away" when they ask for the impossible or unimplemented; e.g. "I want fully general backreferences, streaming and fixed-sized stream state").

Hm decomposing the problem and integrating automata and backtracking sound interesting. Although I'll say you can't claim that the RE2 articles aren't the gold standard if you haven't worked on or published this yet! :) (as code or prose)

Many things may have changed since they were written, but as far as I can tell they haven't been demonstrated in a friendly way, i.e. with the short example code in those articles.

> I frankly think we're still waiting for a 'gold standard' in regular expression implementation.

Is it the implementations, or is it regexes themselves? I was under the impression that SNOBOL/SPITBOL/REBOL was the gold standard... But I guess you're saying that given some (posix?) regex syntax, implementations can/should be improved? (while eg REBOL/Red-lang goes more towards "a more pragmatic regular language for pattern recognition", I guess ?)

> REBOL/Red-lang goes more towards "a more pragmatic regular language for pattern recognition"

Rebol and Red use embedded PEG parsers, which, by definition, support context-free, and not just regular, languages.

I'm fascinated by PEG parsers, but I don't know whether they can be implemented in a way that's remotely as performant as even mediocre regular expression implementations, much less tuned SIMD extravaganzas.

That would be a stretch goal for me: build a regular expression / automata library that's sufficiently modular to keep some components and drop in more expressive constructs (not necessarily PEGs, but maybe pushdown automata).

Not, sure - but I just came across this in the Nim standard library:

http://nim-lang.github.io/Nim/pegs.html

> Simple PEG (Parsing expression grammar) matching. Uses no memorization, but uses superoperators and symbol inlining to improve performance. Note: Matching performance is hopefully competitive with optimized regular expression engines.

I've written a lot of things that are "hopefully competitive" with something else, but generally benchmarking is the ideal. :-) Hard to benchmark PEG vs regex fairly. Not dismissing it out of hand, as I've had many years to observe the weak spots of regex at quite a short distance.

Proper regular expressions don't need backtracking.