RedfaA regex engine over the Unicode codespace, with the boolean operations (intersection, complement) alongside the usual ones, and DFA construction by Brzozowski derivative.
Regex is where a caller builds or parses a regex. Dfa turns a list of them into an automaton. Ast is the normal form the engine derives over, exposed for tests and benchmarks.
Single-domain. The hash-cons table behind Ast is global and unsynchronised, as are the memo fields on every node, so two domains calling into this library at once race — on the table, on the tag counter, and on the memos. Values are unsafe to share across domains too: two structurally equal nodes built on different domains may or may not end up as the same record, so Ast.equal between them is unreliable. Confine a program's use of redfa to one domain, or guard it with a lock of your own.
module Ast : sig ... endThe hash-consed regex the derivative engine works over. Smart constructors flatten nested Seq/Alt/Inter and sort Alt and Inter children by tag, dropping duplicates (associativity, commutativity, idempotence). Regexes differing only by those share a node, so equal is pointer equality, and deriving reaches a finite set of terms, which is what makes DFA construction terminate.
module Regex : sig ... endThe regex users write, keeping the shape they wrote it in. Plus, Opt and Neg_chars are constructors of their own, so a regex survives the round trip to source with its +, ? and [^...] intact.
module Dfa : sig ... endBuilt from a list of token regexes by item-set derivative construction. A state is a set of items, one per candidate token, each being the remainder of its regex still to match. Transitions are computed by deriving every item on one representative codepoint of each block of the items' joint approximate partition.