How pandaman64/lean-regex works
Main components
• Verified Regex Engine Core – This is the part that implements regular expression parsing, compilation, and matching. It is primarily found in the “regex” directory.
• Formal Correctness and Verification – The “correctness” directory contains Lean proofs and supporting code that formally verifies the semantics and behavior of the regex and PikeVM implementations.
• Regex Parsing and Syntax – Within “regex/Regex/Syntax” you have the AST and parser modules that take a regex pattern and convert it into an internal representation.
• NFA Compilation – Both in “regex/Regex/NFA” (and similarly in “correctness/RegexCorrectness/NFA”) you have files that compile the regex into a non-deterministic finite automaton.
• PikeVM (Virtual Machine) – The PikeVM is implemented in “regex/Regex/VM” and its structure also includes detailed submodules such as “Basic” and “Strategy” for executing regex matching.
• Auxiliary Components – There are additional utilities for handling strings, sparse sets, list operations, and other helper functions spread across both the “regex” and “correctness” modules.
• Build and CI Infrastructure – The presence of Lake build files (lakefile.toml, lean-toolchain) and GitHub workflows indicates integration and continuous integration processes running tests and builds.
Relationships and interactions
• The process starts from a regex pattern (input). The Syntax/Parser modules convert this into an AST representation.
• The AST is then compiled into an NFA using the NFA Compilation components.
• The generated NFA is executed by the PikeVM-based engine found in the VM modules.
• In parallel, formal correctness modules (inside “correctness”) mirror this pipeline to provide proofs and verification of each stage:
• They verify the semantics of regex constructs.
• Prove the correctness of both the NFA operation and the VM behavior.
• The testing and benchmarking scripts (in directories like “regex/tests” and “regex/scripts”) are used to validate both performance and correctness.
• The build/infrastructure (docbuild, .github/workflows, etc.) ties everything together so that on each commit or PR, the verification and compilation steps are automatically executed.
Important architectural patterns
• Modular Design – The project is clearly modular with separation of concerns: one module for the core implementation (“regex”) and another for verification proofs (“correctness”).
• Layered Architecture – The flow from parsing to compilation, execution, and verification represents a layered approach where each stage depends on the previous one.
• Dual-path Implementation – Both the execution logic and its formal verification exist side-by-side. This ensures that for every computational mechanism there is a corresponding correctness model.
Technologies/frameworks
• Lean Theorem Prover – The entire project is built in Lean, leveraging its capabilities for formal verification.
• Lake Build Tool – Used for build configuration, as seen in the lakefile.toml and lean-toolchain.
• GitHub Actions – As indicated by files in the “.github/workflows” directory for CI/CD.