Serenity: LibRegex: A regex engine for Serenity

[nooga]

While browsing the code, I've noticed that we don't have grep yet and also that RegExp would be a nice addition to the "maturing" LibJS runtime. In short, Serenity could use a regex engine of its own and I would like to dedicate this issue to figuring out how to make it happen.

In my mind, the engine should ideally have the following features and properties:

• [ ] Accept POSIX regex syntaxes (BRE and ERE),
• [ ] Accept JS regex syntax (eventually),
• [ ] Play nice with Unicode,
• [ ] Have a decent performance both for short strings and long streams,
• [ ] Be safe and easy to use in any Serenity application.

Given all this, my approach would be to structure the engine as follows:

Parser -[NFA]-> Compiler -[bytecode]-> VM

where:

1. Parser's job would be to construct a Nondeterministic Finite Automaton from the regex string,
2. Compiler's job would be to construct (and possibly minimize) a Deterministic Finite Automaton based on the NFA and generate a program for the VM,
3. VM's job would be to perform matching based on the supplied program.

This approach would allow us to:

• write parsers for different regex syntaxes independently,
• save on building ASTs for regexps,
• offload the heavy lifting to the generic compiler,
• cache compiled regexps for rapid reuse, possibly even across threads.

Using the VM for matching would offer decent performance while not requiring executable memory which would be a deal breaker for apps like the Browser.

I'm not sure how the API would look like yet but it should probably provide common regexp related functionality such as:

• [ ] compile and execute (+ convenience function to do that in one step),
• [ ] search & test
• [ ] match
• [ ] replace

I'm curious about your ideas and input. I'd like to establish some kind of loose consensus over this idea before I start laying down the code :^)

[linusg]

Related (previous attempt of adding regex capabilities to Serenity): https://github.com/SerenityOS/serenity/pull/1654

[nooga]

@linusg missed that one 😅

[devsh0]

Simulating a DFA would make back referencing extremely tricky. The engine will have to deal with a lot more states which leads to an NP-complete problem while matching? I believe LibJS needs to support back referencing @linusg?

[linusg]

I believe LibJS needs to support back referencing @linusg?

Yes:

Parentheses of the form ( Disjunction ) serve both to group the components of the Disjunction pattern together and to save the result of the match. The result can be used either in a backreference (\ followed by a nonzero decimal number), referenced in a replace String
[...]

as well as:

https://javascript.info/regexp-backreferences

[nooga]

@lnzero1dev are you working on this? I browsed through your #1654 - it seems like you've made some good progress but decided to start over.

[lnzero1dev]

Hi @nooga,

yes, still worked on that topic the last weeks, but hadn't that much time, so the rewrite is still not completed.
Though, I would like to share the code and maybe we can implement together.

So far the following of the lists above is implemented :

• [X] Accept POSIX regex syntaxes ERE

• [ ] Accept POSIX regex syntaxes BRE
  I implemeted a Parser interface that can be used to implement all types of parsers. Currently, only PosixExtended Parser is implemented. Next Step's would be to add PosixBasic Parser.

• [ ] Parser's job would be to construct a Nondeterministic Finite Automaton from the regex string,
  The Parser itself is not automaton bases yet. To be improved :^)

• [ ] Accept JS regex syntax (eventually)
  The JS Parser has to be added.

• [X] Play nice with Unicode
  I added some tests with utf-8 / utf-32 characters. Seems to work so far, but maybe also improvements possible.

• [ ] Have a decent performance both for short strings and long streams, --> Added a BenchmarkRegex.cpp file in the AK Test suite to measure performance agains standard library (on host machine though). Haven't run this after rewrite of code. So interesting how the perforamnce after the rewrite is =)

• [X] Be safe and easy to use in any Serenity application.
  A bit similar to the std::regex, I think. Currently, it looks like:

Pattern<PosixExtended> pattern("^.*$");
auto result = pattern.match("Well, hello friends!\nHello World!");
EXPECT(result.count == 1);
EXPECT(result.matches.at(0).view.starts_with("Well"));
EXPECT(result.matches.at(0).view.end() == "!");

Pattern<PosixExtended> pattern("^.*$", PosixFlags::Multiline | PosixFlags::StringCopyMatches);
auto result = pattern.match("Well, hello friends!\nHello World!");
EXPECT(result.count == 2);
EXPECT(result.matches.at(0).view, "Well, hello friends!"); // view points to internal copy of original string
EXPECT(result.matches.at(1).view, "Hello World!"); // view points to internal copy of original string

If you have any Ideas to make this even better, I'm more than happy to improve on that :-)

• [X] Compiler's job would be to construct (and possibly minimize) a Deterministic Finite Automaton based on the NFA and generate a program for the VM, --> I used the Trex VM as noted here

• [X] VM's job would be to perform matching based on the supplied program. --> I guess there is room for optimization :-)

• [ ] back referencing
  Not implemented, but should be possible.

• [X] I've noticed that we don't have grep --> I did a first shot but I havent adaptet it to the new implementation. But shouldn't be that complicated.

So I try to get the code running and upload it later on (or tomorrow, let's see how far I get).
Then you are more than welcome to dig into it, help, implement or whatever you want :-)
I'm really open as I'm not sure if the architecture of the implementation is quite right. :^)

[lnzero1dev]

Hi @nooga,

I just realized the performance dropped a lot in comparison to the first version. I think that is because of on demand OpCode creation. It might be easy to avoid that, but still there might be more to improve. So I think there is no way going further without using the great serenity OS profiler :^)

Can you have a look at the WIP pull request and give me a clue if it goes in the right direction in your opinion?

[nooga]

Hey @lnzero1dev. Just saw your PR. I'll try to go through it today to understand what's going on there and ping you with comments :)

I must say that your approach seems very good. Learned about Trex yesterday and it looks like a great choice - much better than the DFA I proposed.

[nooga]

@lnzero1dev The PR looks good to me but I'm not in a place to judge it :)

One slight issue is that you've put it all in AK. From IRC discussions it seems that AK is not a good place for regex and it should be a separate library living in Libraries/LibRegex or similar.

[lnzero1dev]

Hey @nooga,

fully agree. I think LibRegex seems to be a good name though. Living in Libraries/LibRegex would be a nice thing for me. One questions left for me is: when I put regex.h and POSIX regex functionality in LibC, there is basically a dependency from LibC to LibRegex. Today LibC uses AK, so that dependency already exists. If @awesomekling can live with another dependency or has another solution I didn't think of, that would be great :-)
At least, LibC needs to pull in the source files of LibRegex or link agains LibRegex or we the user has to link agains LibRegex on it's own, if POSIX regex from LibC should be used by the user.

I'm currently working some things out and move the files to the new directory. :-) Hopefully getting this ready soon :^)

For better juding, I think of providing some benchmarks restults for my host machine and different optimization levels with LibRegex and regex of stdlibc++.

[fwilhe2]

Hi, I was a bit surprised to find the userland has no "grep" command. I think even without regex, a grep command that only looks for fixed strings would be an improvement to the current situation, regex could later be added. Anyone disagrees?

[bugaevc]

There's fgrep

[fwilhe2]

There's fgrep

Thanks, I was not aware of that.

[danboid]

Apart from having a better grep (and many other good uses) this is required for the match function of expr which is needed so we can run configure scripts under Serenity.

[alimpfard]

Say, @lnzero1dev, would it be okay for me to pick up your PR and continue where you left it off?
it feels bad to let all that work go to waste :P

[lnzero1dev]

Hi Ali, sure, would be nice if it's not trash :) unfortunately I'm
currently not able to continue. My last thoughts were on looking how to
make it compatible with the JavaScript spec, as regex is also needed there.
In the current shape it's not that compatible and maybe it's ok to care
about the JavaScript later...
Feel free to take the code and work on it. 👍🏻
Regarding author in the files header I guess "developers of Serenity OS"
would be best, I think I put my name in there, so far, maybe you can change
that :)

Ali Mohammad Pur [e-mail] schrieb am Sa., 14. Nov. 2020,
19:08:

Say, @lnzero1dev https://github.com/lnzero1dev, would it be okay for me
to pick up your PR and continue where you left it off?
it feels bad to let all that work go to waste :P

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/SerenityOS/serenity/issues/2352#issuecomment-727244517,
or unsubscribe
https://github.com/notifications/unsubscribe-auth/ANXXVF3YQQONR4MG2UFJGULSP3BQNANCNFSM4NIRGBUA
.

[linusg]

Time to close this issue?! :^)

[nooga]

Thanks to @lnzero1dev and @alimpfard this issue is now resolved :)
Awesome work guys!