3 ms·
Ragel was designed to do #1 and #2 to make network scanners easy to implement. It technically doesn't do #4 because it only generates DFAs[1] And it does #5 bec
by wahern 8y ago
Ragel was designed to do #1 and #2 to make network scanners easy to implement. It technically doesn't do #4 because it only generates DFAs[1] And it does #5 because it doesn't have any concept of strings, per se, just sequences of integers. (The pre-defined named patterns assume ASCII encoding but you don't need to use those.)
Saving state (#2) is trivial because the state of the DFA is a single integer, `cs`. Ragel scans input through a very simple interface--in C it uses just three pointers, `p`, `pe`, and `eof`, that are expected to be in scope and valid when its generated code block is resumed. (It pauses when p == pe but p != eof, allowing you to yield and resume when you have more data, and only halts when p == eof. Can you also explicitly exit at any point while keeping state consistent.) You can save and restore these however you want, and you can even change their names or how the generated code dereferences them (e.g. so they're dereferenced directly through your state structure).
[1] It only does DFAs but you can support more complex matchers by employing specialized constructs for tracking state transitions (allowing you to capture match positions), conditional matching (using user code to dynamically test if a character matches), direct branching to another DFA (fgoto), and recursion (fcall, fret). The latter (recursion) also requires that the user save and restore a stack of `cs` values.
- mehrdadn 8y agoCool! Yeah, someone else mentioned Ragel too. I'll have to check it out and see if it's also lazy (to prevent exponential blow-up for the DFA).
- wahern 8y agoUnfortunately[1] it's not lazy. The DFAs are static. And you can get blow ups. I've used Ragel for many different projects. The only time that became an issue was for a project that involved transforming ~10,000 PCREs to Ragelable syntax and into a giant union. A handful[2], when placed into a union, would trigger (directly or indirectly) DFAs that were either too large or simply took too long to compile.[3] We developed heuristics to split them up, so we had one giant union and a few dozen smaller ones. Later the Ragel author implemented a cost function that allowed us to do that more consistently and efficiently. Normally if you encounter undesirable blow ups you can use Ragel constructs to split your machines and dynamically jump between them. I've also worked with RE2 and consulted on a project using re2c. Those projects run into trouble with DFA complexity much, much, much earlier than Ragel. For example, re2c took days to compile a union that Ragel compiled in seconds, and while the generated code was large it wasn't even noticeable in terms of performance. (And by not noticeable I mean that the run time wasn't noticeably different from other Ragel-using projects. In terms of performance there's simply no comparison between Ragel and re2c, or Ragel and RE2 for that matter.) [1] On the plus side, if you compile the machine into a dynamically linked library the generated code and data will be shared across processes and with the file system buffer cache. Even multi-gigabyte machines don't necessarily result in as much memory pressure as you'd think because most of the states won't be visited and so won't need to be resident. Sometimes you make a little change to a machine and it doubles or triples in size; I had to learn to leave it be and move on because ultimately it was usually inconsequential and my time was better spent elsewhere rather than obsessing over what intuitively seemed inefficient and costly. [2] EDIT: This originally said 5%, but now I remember that 5% was the number of PCREs that contained problematic constructs that, in order to emulate, required special treatment. (In other words, 95% readily transformed to equivalent DFAs) The ones that truly blew up the DFA into something unusable were quite rare. And none were so large that they couldn't be compiled to their own, single machine. [3] Part of that was our use of `when` conditionals, which we used heavily to translate zero-width assertions (e.g. "\B"). Because of how they work they can easily inflate the machine size when part of a union.
- mehrdadn 8y agoInteresting, thanks for the info! :-)