Regular Expression Engine for Mojo, any plans?

Do we have a regular expression engine implemented in Mojo?I haven't come across one yet, but it would be fantastic to have. Or is there a native solution planned for Mojo? If not, what could be our approach to developing one? I have no clue about the complexity involved in this task. Would we base it on some existing C engine or write it from scratch in Mojo. Thx

MMartin Dudek Do we have a regular expression engine implemented in Mojo?I haven't come across...

MM•5/16/24, 10:58 AM

The only one I know of is a very simple (60 loc) regex match implementaion in Mojo by sstadic (https://github.com/sstadick/ExtraMojo/blob/main/ExtraMojo/regex/simple_re.mojo). However I'm also very interested to know of any plans. To my understanding Rust has a fast regex library.

ModularBot•5/16/24, 10:58 AM

Congrats @MM, you just advanced to level 3!

bunny•5/16/24, 11:12 AM

Go's regex is known to be blazing fast, too. I recall reading that it beats Rust's (if barely) in some benchmarks. Last I looked into it (years ago; 5? 6? not sure), Go and Rust were the two fastest implementations in any major programming language.

Martin DudekOP•5/16/24, 1:49 PM

I use https://pypi.org/project/regex/ via Python integration right now which works fine but regex seems so essential that i really hope we will have something native at one point. for performance, and for elegance :mojo:

PyPI

regex

Alternative regular expression module, to replace re.

Heyitsmeguys•5/16/24, 4:16 PM

If we're talking about absolute performance, there's also hyperscan. It absolutely smashed the benchmarks. I don't know if we can write a portable regex library which is as fast as it, but one can dream. :mojo:

moosems_yeehaw•5/16/24, 4:44 PM

A quick google search found this

bunny•5/16/24, 4:45 PM

oh! I forgot about RE2. It was still unstable when I was doing that eval, years ago. Google does some amazing engineering.

Bbunny oh! I forgot about RE2. It was still unstable when I was doing that eval, years ...

moosems_yeehaw•5/16/24, 4:47 PM

When they want to do something right they seem to be good at it

moosems_yeehaw•5/16/24, 4:51 PM

Martin DudekOP•5/16/24, 4:55 PM

Thanks for finding these gems. But now the question remains, how can we do it right in Mojo?

bunny•5/16/24, 5:00 PM

moosems_yeehaw•5/16/24, 5:19 PM

I vote for lol

Ryulord•5/16/24, 5:29 PM

One thing to keep in mind when looking at those performance charts is that not all regex variants have the same expressive power. PCRE for example can describe any context-free language, not just regular languages. parsing/recognizing languages of different types on the chomsky hierarchy is well studied is CS and there's an inherent expressiveness/speed tradeoff to consider

benny•5/16/24, 9:35 PM

came here to also mention re2, i’ve looked into porting it but it’s a pretty large library, definitely an interesting issue

Bbenny came here to also mention re2, i’ve looked into porting it but it’s a pretty lar...

moosems_yeehaw•5/17/24, 12:51 AM

I took a look at the docs and it’s fairly complex to use though maybe I just need to take a better look at it

MM•5/17/24, 7:36 PM

While glimpsing through the re2 source code I found this link in a comment https://swtch.com/~rsc/regexp/. It has some bare bones examples in C that may provide a less intimidating starting point than the re2 library for someone toying with the idea of implementing regexes for Mojo.

MMM While glimpsing through the re2 source code I found this link in a comment https...

benny•5/18/24, 3:42 AM

I also recommend this video https://youtu.be/DDe-S3uef2w?si=NP6TqGm0PYFdg7zI, about halfway in it gives a great description of re2 (also a great vid in general)

YouTubeKevin Fang

Cloudflare Deploys Really Slow Code, Takes Down Entire Company

Cloudflare is back at it again with more regex and state machines.

Previously on Cloudflare: https://youtu.be/GEbn3nHyKnA

Sources:
https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/
https://blog.cloudflare.com/introducing-quicksilver-configuration-distribution-at-internet-scale/
https://swtch.com/~rsc/regexp/regexp1....

MM•5/18/24, 6:49 AM

A simd accelerated multiple substring matching algorithm called "Teddy". This is used in Rust's ripgrep. https://github.com/rust-lang/regex/blob/3de8c44f5357d5b582a80b7282480e38e8b7d50d/src/simd_accel/teddy128.rs

GitHub

regex/src/simd_accel/teddy128.rs at 3de8c44f5357d5b582a80b7282480e3...

An implementation of regular expressions for Rust. This implementation uses finite automata and guarantees linear time matching on all inputs. - rust-lang/regex

Bbenny I also recommend this video https://youtu.be/DDe-S3uef2w?si=NP6TqGm0PYFdg7zI, ab...

bunny•5/18/24, 3:40 PM

I finally watched that vid. Wow. That was awesome!

So, in "a former life," I worked somewhere that used a TON of regex. I recall that we had an engine that was "optimized for that time" (many years ago), but we also wrapped our regex-engine with a staging filter that would prevent certain regex formulas. For example, our system flat-out denied use of unlimited matching. I mean, you could get the rough equivalent of by doing or something. And -> . But the programmer would be intentionally building that numeric limit. In addition, IIRC, we also limited the upper end of matching on unlimited character sets () and also wide-ranging sets (, , etc); I do not recall the numeric limits. The real use case for and is really close to zero. Anytime you think "I should put an unlimited match here" you are really thinking "I should break the universe" and should probably approach the problem differently.

I don't remember all the safety-checks we had built into the staging filter. It was just too many years ago. But we essentially sanitized for any regex and kicked out errors and suggestions on how to get the same intended results without breaking everything.

---

Not editing anything above, but before hitting enter, I looked for something similar in open-source universe. This looks pretty cool: https://github.com/tjenkinson/redos-detector

Anyway, sorry for the diversion from discussing the underlying regex engine. Just wanted to share a tip for anybody working with regex in their current life, who might be at an org that is not willing to adopt something like RE2.

Martin DudekOP•5/18/24, 4:26 PM

i start getting worried we need to wait for a future life before somebody comes along who is actually willing to implement a regex engine for Mojo

it feels more and more like a pretty dry and quite complex task to dive into to be honest ...

bunny•5/18/24, 4:31 PM

It's super dry, super complex, and ....... we just gotta find somebody that enjoys a lot of pain.

Bbenny I also recommend this video https://youtu.be/DDe-S3uef2w?si=NP6TqGm0PYFdg7zI, ab...

moosems_yeehaw•5/18/24, 5:37 PM

The channel is great, by the way. I’d recommend watching their other videos

Darkmatter•5/20/24, 12:20 AM

I think that having a bifurcated version of regex the way Rust does would be a good idea. One which implements most of the things most people will ever need but has guaranteed linear time evaluation, and another which is a full PCRE implementation with all the dangers that entails. Call the safe one regex and the full one PCRE since that is correct from a computer science theory perspective, so that unaware people reach for the safe and faster implementation first.

DDarkmatter I think that having a bifurcated version of regex the way Rust does would be a g...

Ryulord•5/20/24, 2:54 AM

You could also possibly make a single library that just has multiple backends and uses whichever is most optimal for your pattern. Could even have an optional flag to just give you a compile time error if your pattern isn't compatible with the fast backend.

RRyulord You could also possibly make a single library that just has multiple backends an...

Darkmatter•5/20/24, 2:56 AM

That would probably require more compile time capabilities than Mojo currently has. If the compiler is willing to cooperate it would be great, but otherwise we are probably looking at needing Zig comptime/Rust proc macros to actually give compile time errors. Iirc the Rust regex crate doesn't give compile time errors in the name of allowing you to give it a string at runtime.

ModularBot•5/20/24, 2:56 AM

Congrats @Darkmatter, you just advanced to level 1!

Darkmatter•5/20/24, 2:58 AM

Also, automatically swapping to a backend with polynomial-in-input-size performance regressions is behavior I'm not sure I want to see in a library. It should be a manual switch.

DDarkmatter Also, automatically swapping to a backend with polynomial-in-input-size performa...

Ryulord•5/20/24, 3:02 AM

This could probably be solved by making the default mode be strict regex only and slower modes require explicit opt in. A little more verbose for "script-like" code though. As for compiling your pattern at comptime vs. runtime it should be as simple as vs but Mojo doesn't currently support calling functions that might raise at compile time. It seems like it should support that eventually though.

Darkmatter•5/20/24, 3:05 AM

What would the actual data layout of my_pattern look like in this case?

Darkmatter•5/20/24, 3:07 AM

I could see a potential path to turing completeness in the type system via Church encoding and lambda calculus, but that amounts to a torture test of the compiler.

Ryulord•5/20/24, 3:07 AM

Yeah, that's a bit tricky. Might have to be a variant type or a class

RRyulord Yeah, that's a bit tricky. Might have to be a variant type or a class

Darkmatter•5/20/24, 3:08 AM

aliases can't be recursive or co-recursive.

Darkmatter•5/20/24, 3:09 AM

Not sure if that's by design or a current implementation limitation.

Darkmatter•5/20/24, 3:09 AM

^ That errors out

Darkmatter•5/20/24, 3:10 AM

Remember that it has to be done 100% at compile time in order to construct a state machine you can then traverse at run-time in an O(n) manner.

Darkmatter•5/20/24, 3:13 AM

And the state machine will be required so that you can check for anything that is incompatible with linear-time evaluation.

Darkmatter•5/20/24, 3:14 AM

That's why I said this needed compiler support or more powerful compile-time capabilities.

DDarkmatter And the state machine will be required so that you can check for anything that i...

Ryulord•5/20/24, 3:14 AM

This isn't true is it? Can't we just check for presence of certain syntax?

RRyulord This isn't true is it? Can't we just check for presence of certain syntax?

Darkmatter•5/20/24, 3:15 AM

([a-zA-Z]+)*

Darkmatter•5/20/24, 3:15 AM

What part of that syntax can you ban?

Darkmatter•5/20/24, 3:15 AM

Because that's a Regex which allowed a Denial of Service attack in 2014.

Darkmatter•5/20/24, 3:16 AM

https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS

Regular expression Denial of Service - ReDoS on the main website for The OWASP Foundation. OWASP is a nonprofit foundation that works to improve the security of software.

DDarkmatter What would the actual data layout of my_pattern look like in this case?

Ryulord•5/20/24, 3:16 AM

And maybe have an optional type wrapping the data for each backend? then calling match would just check for the fastest non-None?

RRyulord And maybe have an optional type wrapping the data for each backend? then calling...

Darkmatter•5/20/24, 3:19 AM

I ended up giving up and doing this since nobody was answering my question about a JSON parser and I ran into the variant issue. This is VERY wasteful on space, and there's probably a magic type somewhere in the standard library that introduces indirection and lets you do recursive variants, but I can't find it.

Ryulord•5/20/24, 3:21 AM

Oh now I understand. I was confused about you mentioning recursion in Variant. The idea would be that my_pattern would have type

DDarkmatter ([a-zA-Z]+)*

Ryulord•5/20/24, 3:23 AM

and the issue here isn't syntax but the fact that the engine can do backtracking. You can change the semantics so this isn't quadratic

Darkmatter•5/20/24, 3:23 AM

I was thinking about the parse tree since I'm currently writing a JSON parser while we're talking.