meon — declarative flat-parsing engine (SoA, no AST)
I started this as a simple Markdown parser. Then I got curious about making it faster, and that curiosity turned into a bigger architectural question: instead of building a tree/AST, what if the parser output flat arrays — one Vec per element kind (headings, bold spans, links, etc.), all as zero-copy byte-offset spans into the source?
That idea grew into a small engine: you describe a grammar once via define_parser! and get a generated parser with no runtime dispatch. The Markdown parser became just one concrete grammar built on top of it. I later added a JSON grammar to prove the engine isn't Markdown-specific.
This project ended up as the basis of my coursework (3rd year, university), so it's had a fair amount of design iteration — but it's also grown past a toy project, and I'd like a critical outside look before I consider it more "done."
Repo structure (workspace, 4 crates):
meon — the core engine + define_parser! macro runtime
While undoubtly this is a cool technology I have hard time imagining how this can be used in practice. Abstract Syntax Tree is a tree for a reason. What useful work you can do with an array of all objects of a given kind in document, without knowing anything about a structure of said document? Even if traversing SoA is faster than disjointed tree, how do you compare additional cost of re-parsing to discover structure of your document during traversal?
Nesting isn't lost — it's just represented differently. Containment is an interval-inside-interval relationship: if span A's range fully contains span B's range, B is nested in A. Same information as a tree, different memory layout and different work for the CPU to extract it.
That's exactly what makes scaling smoother compared to AST builders — see the benchmarks linked in the README. If you actually need a tree, you can build one on top of these vectors with a straightforward algorithm — but only when you need it, not as a mandatory upfront cost for every consumer.
The O(1) per-type access without walking the whole tree is useful on its own for a lot of use cases — analytics being one obvious example, where you often want "give me all headings" or "give me all links" and nothing else.
Overall this layout sits a lot closer to the hardware than any tree-based representation.
I still have an AST, but it's stored in a flat buffer (a singled Vec<u8>), with each node being basically a header telling the size of the subtree. I also store only ranges into the source rather than strs. I know Symbolica has an identical approach.
Yours appears to generate a list of spans for highlighting, which I find to be very useful for markdown. When designing rich text rendering for cuicui (basically a UI framework), this is what I thought would be the best approach for performance. Have you considered what happens when the different types overlap (eg: a code section is bold, or bold+italic?) I feel like it could be useful for rendering to discriminate all types of combinations.
Good question. Overlaps aren't represented as the same span living in two vectors. Combinations that need to exist (bold+italic) are declared as their own explicit type with their own vector — bold_italics — routed by a count-based match arm in the grammar (1 => italics, 2 => bolds, 3 => bold_italics). For types that shouldn't compose with anything else (code spans), the grammar just makes them opaque: everything inside is treated as literal content, no inner triggers fire at all, so there's nothing to overlap with in the first place.
Two separate concerns in the DSL: which type a delimiter count maps to (the numeric match arm), and whether that type's content is parsed at all (parse_inside).
Could you explain how tree walking works in this paradigm? TBH it sounds like it could be quite expensive if all elements of multiple arrays would need to be cross-checked in order to establish that there is indeed a parent-child relationship between 2 nodes.
I can't speak for the details of their library, but this is essentially the same as for ECS: each individual list is in source order as well, so a "tree walk" becomes alternating which list you're progressing on, which you can pretty easily maintain with something like a priority queue of iterators: order by node start then by node end ascending will give you a post-order, or by node end descending will give a pre-order (if I got that right, at least!).
The main difficulty for more complex grammars like for a programming language is they can often end up with several levels with identical spans you would need to distinguish, but I expect most such cases that would be implicit in the kind (eg a type contains a type ref contains a path contains a name)
edit: I should also point out that many visitor passes are some version of "find all instances of X" which is of course trivial, or "find all instances of Y within each nearest containing X" which is a simplified version of the above approach.