# pandaman64/lean-regex architecture

> Architecture diagram of the GitHub repository pandaman64/lean-regex, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2025-03-30). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/pandaman64/lean-regex
- Repository: https://github.com/pandaman64/lean-regex

## Overview

##### 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.

## Diagram (Mermaid)

```mermaid
flowchart TD
    %% Implementation Layer
    subgraph "Implementation Layer"
        A1("Regex Pattern Input"):::impl
        A2("Regex Parser & AST"):::impl
        A3("NFA Compiler (Impl)"):::impl
        A4("PikeVM Engine (Impl)"):::impl
        A5("Auxiliary (Impl)"):::impl
        A6("Regex Core"):::impl
    end

    %% Formal Verification Layer
    subgraph "Formal Verification Layer"
        B1("Regex Correctness"):::verify
        B2("NFA Verification"):::verify
        B3("PikeVM Verification"):::verify
        B4("Auxiliary Verification"):::verify
    end

    %% Build & CI Infrastructure
    subgraph "Build & CI"
        C1("Build Infrastructure"):::ci
        C2("CI/CD Pipeline"):::ci
    end

    %% Implementation flow arrows
    A1 -->|"parsedVia"| A2
    A2 -->|"compiledTo"| A3
    A3 -->|"executedBy"| A4
    A1 ---|"supportedBy"| A5
    A4 -->|"integratedInto"| A6

    %% Verification arrows from implementation components to their corresponding verification modules
    A2 -->|"verifyParse"| B1
    A3 -->|"verifyNFA"| B2
    A4 -->|"verifyVM"| B3
    A5 -->|"verifyAux"| B4

    %% Merging flow into build and CI
    A6 -->|"buildTriggeredBy"| C1
    B1 -->|"verifiedBuild"| C1
    B2 -->|"verifiedBuild"| C1
    B3 -->|"verifiedBuild"| C1
    B4 -->|"verifiedBuild"| C1
    C1 -->|"CIExecution"| C2

    %% Click Events for Implementation Components
    click A6 "https://github.com/pandaman64/lean-regex/tree/main/regex/Regex"
    click A2 "https://github.com/pandaman64/lean-regex/tree/main/regex/Regex/Syntax"
    click A3 "https://github.com/pandaman64/lean-regex/tree/main/regex/Regex/NFA"
    click A4 "https://github.com/pandaman64/lean-regex/tree/main/regex/Regex/VM"
    click A5 "https://github.com/pandaman64/lean-regex/tree/main/regex/Regex/Data"

    %% Click Events for Verification Components
    click B1 "https://github.com/pandaman64/lean-regex/tree/main/correctness/RegexCorrectness"
    click B2 "https://github.com/pandaman64/lean-regex/tree/main/correctness/RegexCorrectness/NFA"
    click B3 "https://github.com/pandaman64/lean-regex/tree/main/correctness/RegexCorrectness/VM"
    click B4 "https://github.com/pandaman64/lean-regex/tree/main/correctness/RegexCorrectness/Data"

    %% Click Events for Build and CI (using representative files/directories)
    click C1 "https://github.com/pandaman64/lean-regex/blob/main/docbuild/README.md"
    click C2 "https://github.com/pandaman64/lean-regex/tree/main/.github/workflows"

    %% Styles
    classDef impl fill:#DDEEFF,stroke:#000,stroke-width:2px;
    classDef verify fill:#FFDDDD,stroke:#000,stroke-width:2px;
    classDef ci fill:#DDFFDD,stroke:#000,stroke-width:2px;
```
