7 ms·
Rob Pike's simple C regex matcher in Go
- metadat 4y agoI wonder what the non-recursive redesign would look like, without using the simulate-recursion-via-callstack translation technique. I slept on it and the solution still isn't clear to me. As an aside: It'd be nice if the go unit tests logged an indication of whether or not the ./matchC exec tests ran.
- unixbane 4y agookay now post the standard academic version of elegant simple regex in algol, lisp, ml whatever and see how many upvotes it gets
- user5678 4y ago
- djbusby 4y agoOk. This was educational and fun. Thanks!
- jll29 4y agoI like the article that this post refers to about efficient implementation (https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html). It mentions a debate between J. Friedl and comp. sci. purists about whether NFAs and regular expressions should really be called what they are in the face of backreferences and other notation. Friedl suggests another name should be used, because de facto "NFAs" are no longer equivalent to DFAs. Since Xerox Research Europe's invention of xfst, the term "extended regular expression" is already taken for a specific superclass of expressions that describe regular relations. So I propose two alternatives, semi-regular expressions and super-regular expressions, for strings that look like regular expressions but that use non-regular extensions like backreferences that push the complexity beyond what can be done with NDAs/DFAs.
- kazinator 4y agoI cannot agree here. The term "regular expression" relates to "regular language". So instead of inventing new words haphazardly, we should look at what kind of language we are able to express with these non-regular expressions, what the name of that language is and then use that name for the expressions. Here is a starting point: where do regular languages sit in the Chomsky hierarchy: https://en.wikipedia.org/wiki/Regular_language#Location_in_the_Chomsky_hierarchy https://en.wikipedia.org/wiki/Regular_language#Location_in_t... Here, we see that there are also less inclusive languages included in regular: finite languages and star-free languages, for which the corresponding "finite expression" and "star-free expression" make sense. In the other direction, maybe some useful language kinds can be identified between "regular" and "context-free" in relation to the capabilities of certain kinds of expressions. However, "context-free expression" isn't a bad start. ("Cfex" [si:fex]?)
- Groxx 4y agoAlternatively: declare that "regex" has graduated into its own proper term (not a contraction) for whatever this evolving somewhat-too-capable-for-easy-classification tool is. It's certainly how it's used colloquially.
- amscanne 4y agoThe term “regex” is already used interchangeably for both classes. The Go regular expression library (which is widely used) does not support backreferences, and is guaranteed to run in linear time. It seems sillier to say “that’s not a regex” (since it definitely is a regular expression engine), than to say that the others are extended regular expressions or some other, more flexible thing (for better and worse).
- anitil 4y agoI've read that article so many times I knew what it was by seeing the link. The first few times it didn't make sense, and now it seems almost obvious - I can't remember what I was not understanding.
- deleted 4y ago[deleted]
- nsonha 4y agoI don't see anything "beautiful" here, it works and is performant but seems pretty average in term of readability
- abudabi123 4y agoEmacs has a DSL with the regex power and potential to make the reading experience better than poking toothpicks in your eyeball; experience and familiarity with the syntax sees beauty where others fail to?
- dev_snd 4y agoI never understood why incrementing a pointer while doing another operation, such as a comparison, is considered good style in C, TBQH. I think the go example is much more readable.
- rswail 4y agoBecause C was originally for PDP/DEC equipment and the instruction set had standard register access modes including both pre and post increment. So the (for example) strcmp "while (s++ == d++);" made sense as efficient code, because the pointer access and the post increment effectively compiled down to almost a single instruction. https://en.wikipedia.org/wiki/PDP-11_architecture#General_register_addressing_modes https://en.wikipedia.org/wiki/PDP-11_architecture#General_re...
- rurban 4y agoI also revived my old dynamic string matchers recently, which don't need any costly compilation step: https://github.com/rurban/tiny-matcher https://github.com/rurban/tiny-matcher (in-work) And with compilation https://github.com/rurban/tiny-regex-c https://github.com/rurban/tiny-regex-c (done)
- compsciphd 4y agoSo fun story (to me in retrospect). I had an interview at google years ago where I basically I was asked to come up with this on my own. In my opinion, a terrible interview Q (per Kernighan's blog, linked in original post, it took pike an hour or two alone in his office), and I bombed it. It was either my just before or just after lunch interview and it stuck with me for the rest of the day and I couldn't give my entire focus to the rest of the sessions. anyways, after it was done, I found kernighan's blog post and decided I should try to implement this in java as it will allow me to even get some practice with things like junit and more experience with object oriented programming as I had been living in the C world at that time). so I did, but I then found this regular expression page ( https://www.regular-expressions.info/ https://www.regular-expressions.info/) and learned many more things about "regular expressions" that i hadn't learned in school (because they aren't regular) and wondered if I could extend pike's simplicity to them in a relatively simple manner. So I did. which I created this https://github.com/sjpotter/regex https://github.com/sjpotter/regex. Not meant to be "performant" but meant to be educational to me and perhaps others. Then when I was learning go, I rewrote it in Go. I did things that are not "normal" go patterns (i.e. using panic and recover to make error handling cleaner (in my opinion, if an error path is simply if (err) { return err } all the way up, I personally think panics/recover at the top can be cleaner, but it seems most disagree), but it was educational on how to rewrite my java code to an object oriented style in Go and to explore the limitations of interfaces and how one might get around them (also perhaps in ways that go against what might be considered proper go programming) https://github.com/sjpotter/regex-go https://github.com/sjpotter/regex-go though now that I look at that repo, wondering if all the work was done elsewhere and then I just pushed a single commit there, might need to go back and look at it
- renewiltord 4y agoAbsolutely insane as an interview question. I know lots of top engineers who've built the fundamentals and driven companies to billions of dollars multiple times who would have failed to have completed this objective within an hour. I refuse to believe anyone could imagine it's possible. Either that or there's a whole bunch of hidden talent wasting away at Google - which sounds unlikely.
- tgv 4y agoIt's a left-shortest matching back-tracker. Not to be used in practice. I'm sure this implementation features in various text books.
- adrianmsmith 4y agoGood to see the term "regexp" (with a "p") in use. I always used to call it that, then at some point realized everyone was writing "regex", and wondered if I'd spelled the abbreviation wrong the whole time. I guess it's just a function of time, it used to be spelled with a "p" and now mostly isn't.
- lupire 4y agoRegexp has been dying for decades https://trends.google.com/trends/explore?date=all&geo=US&q=Regexp,Regex,regexpr https://trends.google.com/trends/explore?date=all&geo=US&q=R...
- smcl 4y agoI ended up learning it the same, possibly from the Camel Book? One thing I noticed when I wasn't coding alone in my bedroom and had to actually talk to other coders was that "regex" is more natural to say than "regexp", so that might explain why it became the preferred spelling.
- rob74 4y agoGuess that time favors shorter abbreviations. I prefer "rex" myself (at least as a variable name for a regex object).
- IshKebab 4y agoProbably because "regex" is much easier to say and looks much more like a real word than "regexp". Like "latex" or "codex". Nothing ends in "exp".
- kubb 4y agoIt's a a nicely written function... but it has the difficulty of a warmup interview question or a CS101 homework.
- keepquestioning 4y ago
- lupire 4y agoRegexps are usually in an Algorithms class. Good code looks deceptively simple.
- commandersaki 4y agoExcellent post. I remember reading the exegesis years ago but completely forgot about it. Really impressed how well the Go version turned out. Btw always love your writing Ben, it’s very engaging.
- hddqsb 4y ago> horrible run times on craftily-constructed regexes Here is a simple patch to make the runtime O(len(pattern) * len(text)) instead of exponential. It adds 5 lines and a new parameter. The idea is to memoize (cache) the results, specifically the failures (there is no need to cache the successes, because all the functions return immediately on success). // Match reports whether regexp matches anywhere in text. func Match(regexp, text string) bool { + seen := make(map[[2]int]bool) if regexp != "" && regexp[0] == '^' { - return matchHere(regexp[1:], text) + return matchHere(regexp[1:], text, seen) } for { - if matchHere(regexp, text) { + if matchHere(regexp, text, seen) { return true } if text == "" { return false } text = text[1:] } } // matchHere reports whether regexp matches at beginning of text. -func matchHere(regexp, text string) bool { +func matchHere(regexp, text string, seen map[[2]int]bool) bool { switch { case regexp == "": return true case regexp == "$": return text == "" case len(regexp) >= 2 && regexp[1] == '*': - return matchStar(regexp[0], regexp[2:], text) + return matchStar(regexp[0], regexp[2:], text, seen) case text != "" && (regexp[0] == '.' || regexp[0] == text[0]): - return matchHere(regexp[1:], text[1:]) + return matchHere(regexp[1:], text[1:], seen) } return false } // matchStar reports whether c*regexp matches at beginning of text. -func matchStar(c byte, regexp, text string) bool { +func matchStar(c byte, regexp, text string, seen map[[2]int]bool) bool { for { - if matchHere(regexp, text) { + if seen[[2]int{len(regexp), len(text)}] { + return false + } + if matchHere(regexp, text, seen) { return true } if text == "" || (text[0] != c && c != '.') { return false } + seen[[2]int{len(regexp), len(text)}] = true text = text[1:] } } Demo: https://go.dev/play/p/aD9vzXwTHGE https://go.dev/play/p/aD9vzXwTHGE
- antirez 4y agoApparently I reinvented almost the same code several years after Pike: https://github.com/redis/redis/blob/99ebbee2b260b3466672b4fa351cf1cb5e9b5fe9/src/util.c#L53 https://github.com/redis/redis/blob/99ebbee2b260b3466672b4fa...
- hddqsb 4y agoJust a heads up that this implementation has exponential time complexity on pathological patterns. Demo: https://tio.run/##tVddc6IwFH3nV0Q7WyXFIlrdUWr7uC/9B213BkIQKoKFUGs7/nY3EFA@Emi3LQ@Oudyce@69h3ygwRKhw@HM9ZEXWxhcR8TyXPPSuZFKNjeomkLXX5ZtiOw2ODFJqgqiIA4RngOHkE00V9WlS5zYvETBWg2x5UbZr@kFpjqbYdPEeGSOpkNzfDWdTn@PzCvbGE80ZGvInOCZObHxTI1CpMbE9S7R2d1kTONA8IcCDCKy8zDYGITg0AdrgyAnYQegKrk@AYxsavaw30eBHxGAHCMEMJujgMQvG9xhX5FA9hSdGQ7zZf8T13ToB8iIsCy9pxO3juvh/gkOnJ@fJsjg/YgebV1KKve8Hz4WXyaIoAd786PliA0q4DmA9ggWi2ROESd/MqeLC130iqINBuW3@9LItUuRaSxNroGFmMS0DZoOaH/SqieNqOXQ51akGKnSt5y/phT5akptbvHJe1boV9YrmTuvnfwJlVfJY5zmQmZhhmkYP@BHMkNsrPSKHm4reuBTEdLgYt4XMMutYNomCiOoS9IHBCUWE0UCC3BSeyrWvz29pjHq@EMKZoVe0MpzFKmJlFih/PDQK3x1yZdwswAj3uQW1s3MxQxYe5P1Qij@PFGtjrkH2KNt5yT22BMlUdGNGCpbF4Yt1RDlekIR1etTTGhfxpwFciDMk63tRlgWqi70xb5V8Bw1eCJQ6Ju40Sz4TQIs4pgjkhSRuuuSePljqVA0sRPLQYCyFzLN1tEGknl0EnjBFocsN7mVSOadVEDsiwqeSP4M9/yccEG/2TYRgoHQKSkBSgTGsqQiQ@A6rfRXPsp3YaxOe73/a6Fo4dXKLQ@cN6NPpSkXTzSLU6PSdydOXyMltVu@6ciTbEeSiF4n2xpr/UrtwuNR89b/tV19X9nf6X41bzrHiXavbygfzdE2PA8QJwziZSlPC9tG7JE6swalVxTeaVX4h6ot1Hejrjuf1PXHqPyIDDiN5DfwdOwW7ePspJRfnH72usHNh/1yThylWxbjLtWO9VKpE9Jeqt4Q@ddD0TWwrNQMl39vUai5MJSVDCczs5GsZIhHamvD9ft5AA43ugJ1DWhCBC2IoQ2X0IEufIIr6ME19GEAN/AZhjCCBMbwBW7hK9zBt64u8a@3KZ5hmghZFsa2vVw6jus@Pa1Wnrde@34QbDbPz2EYRYTE8cvLdvv6utu9vRkZ4oaCELvfTdOfg1/Rg99VSgU@FjUvJNXYLejucNQFc9D1g26S/eHwDw https://tio.run/##tVddc6IwFH3nV0Q7WyXFIlrdUWr7uC/9B213BkIQKo... pattern = "a*b*c*d*e*f*g*h*i*j*k*l*m*n*o*p*q*r*s*t*u*v*w*x*y*z" text = "aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyyzza" running time = 1.6s It should be relatively easy to fix this. Insight: If the pattern contains two or more wildcards (i.e. it has the form "<A>*<B>*<C>"), and you've found a match for "<A>*<B>", but you can't find a match for "*<C>", you can stop immediately without considering longer matches for the first wildcard. The reason is that a longer match for the first wildcard will mean you to start looking for "*<C>" later in the string, and that's strictly harder.
- ball_of_lint 4y agoThat might help, but I think it goes in the wrong direction - The proper way to implement a regex matcher if you are worried about performance against arbitrary patterns is to build a Finite State Machine. It's not as simple of code and involves knowing some computer science theory, but results in a matcher with better time complexity guarantees.
- mkovach 4y agoI love this bit of code. It saved my butt in '99 when I had to implement searches for potential "Y2K" coding issues. Some where, collecting dust in CVS repository, probably saved on tape is some storage bunker, is a modified version of this that searched millions of lines of code for various potential "double digit year" issues. And this also taught me an elegant way to implement recursion in C, that I shamelessly used in interviews to look way smarter than I actually am.
- returningfory2 4y ago> I ran benchmarks [...] matching the regex Ben.*H over 100 concatenated repeats of the King James Bible. Is there a concern with these kinds of micro-benchmarks, where you repeatedly do the same small operation (matching the same regex), that your results will be skewed by the branch predictor, CPU caches, etc.?
- tymscar 4y agoThat might be a concern but if you run the same benchmark , the same amount of times, on the same hardware, with the algorithms being the only difference, then you still get a proper comparison between them, even if the timings are useless outside said benchmark