How does this project work?

[jcbhmr]

Hello @conartist6! 👋

Thanks for making this awesome project! I especially appreciate the way you publicly post on the GitHub Issue tracker with your current progress; 😆 I do the same thing and thought it was funny.

I got a playground example working, and it made me think... How the heck does this code actually work?

I tried to have a conversation with ChatGPT about it, but that didn't get me very far. https://sharegpt.com/c/nf0YXQn I also tried reading through the article that was linked in the README https://jasonhpriestley.com/regex and (I'll be honest) didn't completely understand it.

What I guess I'm asking is: how did you make this incredible magic machine? It seems to implement a custom regex parser. How did you do that? What happens to my /hello/g pattern when it goes into the Engine? How do you know when bytes are safe to discard from the stream (this is my big question)? Is there an architectural reason why exec() and execGlobal() are two separate functions (some parser quirk?)?

I'd be interested in learning more about how this project works. No particular purpose, I'm just curious. 🤓

Sidenote: How does this @iter-tools/regex package compare to something like https://oxism.com/works/stream-snitch/ ?

[conartist6]

Hahahaha I really enjoyed watching you fight with an AI and get nowhere. Thanks for sharing that!

I don't actually parse regex, I depend on an existing parser. The code you see here is just executing parsed patterns.

As to how the code works, think of it as evolving the pattern over time! If the pattern to match is ab and the first character of input is a then the pattern that needs to match against the rest of the stream is now b.

That's the easy part, but say the pattern is ab|a. ab and a are alternatives, and a is known as the worse alternative, as it must not match unless no better alternative match. To make that work you start by matching a and then the pattern is b|[match]. Then you can consume one more character from the input and either it is b and you've matched ab or it's anything else and you've matched a.

[conartist6]

I actually built a whole web playground that allows you to see the engine's state evolving as the input is conusmed, just as I described above. Unfortuantely it needs a bit of work to be usable again!

[jcbhmr]

There is the chance that legitimate match fragments could be discarded when the water mark is reached unless you specify a large enough buffer size for your needs.

Ahhh! I must have misread or misunderstood that part when I first read it. You're right that this answers my question. Still, this is a pretty important difference. It might be worth adding something like Wikipedia's "see also" or "external links" sections or even a "comparisons" section to the readme to highlight the differences.

See also

This project has a similar goal to stream-snitch, but is able to find matches of indefinite length without being limited by a 1kb buffer. If you're just looking for a bunch of URLs in a huge 100 MB HTTP stream, you can use stream-snitch just fine. If you're looking to find everything between <pre> and </pre> in a huge 100 MB HTML stream, you'll probably want this @iter-tools/regex so that you don't miss those long code blocks.

[jcbhmr]

That's the easy part, but say the pattern is ab|a. ab and a are alternatives, and a is known as the worse alternative, as it must not match unless no better alternative match. To make that work you start by matching a and then the pattern is b|[match]. Then you can consume one more character from the input and either it is b and you've matched ab or it's anything else and you've matched a.

So is it like magic? Do you constantly inch the regex forward?

const matchedPart = regex.exec(streamChunk);
if (matchedPart) {
  // '/abc/' => '/bc/'
  regex = new Regex(regex.toString().slice(1));
  allMatchedText += matchedPart[0];
}

Or is that what goes on in the Engine class?

I suppose I should provide some more context on why I'm interested in this library:

I want to make Java's Scanner class in JS for no particular reason; I just thought it'd be fun. Turns out that you use Java's Pattern class in Scanner#useDelimiter() which means you need to find a regex match in a stream like System.in

String input = "1 fish 2 fish red fish blue fish";
Scanner s = new Scanner(input).useDelimiter("\\s*fish\\s*");
System.out.println(s.nextInt());
System.out.println(s.nextInt());
System.out.println(s.next());
System.out.println(s.next());
s.close();

At least, that's how I understood it to be from the java se docs https://docs.oracle.com/en/java/javase/19/docs/api/java.base/java/util/Scanner.html and this stackoverflow post: https://stackoverflow.com/questions/15489570/java-scanner-with-regex-delimiter

So I started looking around online to see if there was a way to use the builtin progressive /re/.exec() state machine stuff to get it to work on a ReadableStream web stream or Node.js' Readable class.

Turns out, these isn't anything out there except this library. Congratulations on being one-of-a-kind! 🎉🥳

Anyways...

If I were to play around with this library in VS Code with the /hello/ demo that I used (https://runkit.com/embed/gk7b1v7e53df) where should I put debugger statements to inspect the Engine or whatever's state? Any particular interesting code files I should look at to better understand this project?

[conartist6]

Haha I know quite well that I'm one of a kind! I too wanted a proper abstraction for scanning streams and found that there was none, so I built this. And then I built a scanner on top of it, and a parser on top of that (all over in-progress over at https://github.com/js-cst-tokens/cst-tokens).

Check out this for a more narrative explanation of non-backtracking designs: https://swtch.com/~rsc/regexp/regexp1.html

[conartist6]

Let me see if I can spin up the playground for you.

[conartist6]

@jcbhmr I picked up the playground code and dusted it off. I had it working well at one point, but then the architecture changed some more and my focus shifted to other projects. At the moment what it needs is some d3.js work to render state the way the engine is currently storing it.

Would you be interested in helping with that work? My theory is that if I can help people understand how the code works (by just showing them how it works), then I can attract the maintenance attention needed to build some other features I've been neglecting -- most importantly unicode support.

[conartist6]

Also I actually didn't realize that the regex playground was still up. They sent me a million emails about how my vercel acct was going to be shut off, but I figured they'd take the site down at the same time. I guess not! Anyway that's the one, and it needs some love.

[jcbhmr]

Their parser code is um.... not so good. Where I factored out grammar coroutines, they smushed the parsing rules for every language into one file then applied for grant money.

🙄 of course they did... 🤦‍♂️ Anyways, I thought that was a cool idea. It definitely seemed more "natural" to represent a CST as a DOM tree vs a complex JSON struct in my brain 🧠 which is why I thought it looked interesting.

[conartist6]

I'm pretty sure I could support that as a serialization structure for my trees... It's super interesting. I've been thinking a lot about it!

[jcbhmr]

You know, that'd be a great way to do syntax highlighting! A rudimentary CST using XML/HTML that you can then style with CSS... I think PrismJS does something similar?

<style>
  srcml-var {
    color: red;
  }
  srcml-keyw {
    color: purple;
  }
  /* ... */
</style>
<pre><code data-proglang="js">
  <srcml-keyw>const</srcml-keyw>
  <srcml-var>hello</srcml-var>
  <srcml-op>=</srcml-op>
  <!-- ... -->
</code></pre>

[conartist6]

Both the JSON tree and the XML document can be equivalent -- they both represent trees of nodes. As long as the style rules can be applied to tree of nodes their application could be completely independent of the serialization format of the tree.