Most Markdown parsers use regex. Regex can backtrack. Backtracking can explode.
The regex problem
Many Markdown parsers lean on regex for tokenization and block detection. Regex engines use backtracking. Submit a carefully crafted string and the engine can backtrack exponentially. Processing time goes from milliseconds to minutes. That is ReDoS — Regular expression Denial of Service.
It is not theoretical. It has bitten production systems. For a parser that handles user-submitted content, it is a vulnerability.
O(n) and parallel parsing
Patitas does not use regex in the hot path. It uses a hand-written finite state machine. Single-character lookahead. No backtracking. Processing time is linear in input length, guaranteed.
Malicious Markdown is just slow Markdown — not a denial-of-service vector.
That also enables parallel parsing. On free-threaded Python, parse 1,000 documents with 8 threads and you get ~6.6x speedup. The lexer and parser are designed for it: immutable AST, ContextVar config, single-use instances. No shared mutable state.
Why Patitas exists
Patitas exists because the vertical stack needed a Markdown layer that:
- Is safe on untrusted input (no ReDoS)
- Scales across cores (parallel parsing)
- Integrates with Rosettes for O(n) syntax highlighting inside the parse step
Most parsers compromise one of those. Patitas does not. The tradeoff is that it is a smaller ecosystem. No plugin system like markdown-it. No decade of edge-case fixes like Python-Markdown.
When you should use markdown or mistletoe instead
Use markdown — You need a mature, well-tested parser with lots of extensions. You're not processing untrusted input. You don't care about parallel parsing.
Use mistletoe — You want a fast, CommonMark-compliant parser. You're okay with the GIL. You don't need the b-stack integration.
Use Patitas — You're building with Bengal or the b-stack. You need ReDoS-safe parsing. You want parallel parsing on free-threaded Python.
The vertical stack payoff
The payoff is not just "a safe parser." It is that Patitas owns the integration with Rosettes. Highlighting happens inside the parse step. No shelling out to Pygments. No regex-based lexers. O(n) all the way through.
That is what owning the vertical stack buys you. Each layer is designed knowing what the layers above and below need.