# google/mangle architecture

> Architecture diagram of the GitHub repository google/mangle, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2026-10-01). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/google/mangle
- Repository: https://github.com/google/mangle

## Overview

Mangle is an embeddable Go implementation of an extended Datalog language. The main workflow is to parse source into rules and declarations, validate and analyze the program, then evaluate it against facts and expose query results. The engine supports recursive bottom-up evaluation, while temporal evaluation and interval-backed facts serve temporal rules. Built-in functions and aggregation extend rule execution; the library also offers interactive use, package structuring, and provenance explanations. Edges reflect README statements or source-index references; unsampled implementation details are not assumed.

Main entry points: [`parse/parse.go`](https://github.com/google/mangle/blob/main/parse/parse.go) (Source parser), [`ast/ast.go`](https://github.com/google/mangle/blob/main/ast/ast.go) (Rules and declarations), [`engine/seminaivebottomup.go`](https://github.com/google/mangle/blob/main/engine/seminaivebottomup.go) (Semi-naive engine), [`functional/functional.go`](https://github.com/google/mangle/blob/main/functional/functional.go) (Functions and reducers)

## Diagram (Mermaid)

```mermaid
flowchart TD

subgraph group_language["Language and analysis"]
  node_parser["Source parser<br/>[parse.go]"]
  node_ast["Rules and declarations<br/>[ast.go]"]
  node_packages["Package resolution<br/>[packages.go]"]
  node_validation["Program validation<br/>[validation.go]"]
  node_ruleanalysis["Rule analysis<br/>[rulecheck.go]"]
  node_bounds["Bound inference<br/>[boundscheck.go]"]
  node_symbols["Types and symbols<br/>[symbols.go]"]
end

subgraph group_runtime["Evaluation runtime"]
  node_engine["Semi-naive engine"]
  node_temporalengine["Temporal engine<br/>[temporal.go]"]
  node_functions["Functions and reducers<br/>[functional.go]"]
  node_builtins["Built-in predicates<br/>[builtin.go]"]
end

subgraph group_data["Facts and extensions"]
  node_factstore[("Fact store<br/>[factstore.go]")]
  node_columnstore[("Simplecolumn storage<br/>[simplecolumn.go]")]
  node_temporalstore[("Temporal fact store<br/>[temporal.go]")]
  node_provenance["Proof explanations<br/>[provenance.go]"]
  node_structadapters["Structured data adapters<br/>[json2struct.go]"]
end

subgraph group_interfaces["User interfaces"]
  node_interpreter["Interpreter<br/>[interpreter.go]"]
  node_mgwhy["Explanation command<br/>[main.go]"]
end

node_author(("Program author"))

node_author -->|"writes source"| node_parser
node_parser -->|"creates syntax"| node_ast
node_validation -->|"parses input"| node_parser
node_validation -->|"uses packages"| node_packages
node_validation -->|"checks symbols"| node_symbols
node_ruleanalysis -->|"checks rules"| node_ast
node_ruleanalysis -->|"uses types"| node_symbols
node_bounds -->|"infers bounds"| node_symbols
node_interpreter -->|"parses programs"| node_parser
node_interpreter -->|"evaluates rules"| node_engine
node_interpreter -->|"manages facts"| node_factstore
node_engine -->|"reads and writes"| node_factstore
node_engine -->|"evaluates functions"| node_functions
node_engine -->|"evaluates clauses"| node_ast
node_builtins -->|"evaluates calls"| node_functions
node_temporalengine -->|"stores intervals"| node_temporalstore
node_temporalengine -->|"uses functions"| node_functions
node_columnstore -->|"serializes facts"| node_ast
node_mgwhy -->|"loads program"| node_parser
node_mgwhy -->|"loads facts"| node_factstore
node_mgwhy -->|"requests proofs"| node_provenance
node_provenance -->|"checks facts"| node_factstore
node_structadapters -->|"converts structures"| node_ast
node_author -.->|"defines temporal rules"| node_temporalengine
node_author -.->|"uses aggregation"| node_functions

click node_parser "https://github.com/google/mangle/blob/main/parse/parse.go"
click node_ast "https://github.com/google/mangle/blob/main/ast/ast.go"
click node_packages "https://github.com/google/mangle/blob/main/packages/packages.go"
click node_validation "https://github.com/google/mangle/blob/main/analysis/validation.go"
click node_ruleanalysis "https://github.com/google/mangle/blob/main/analysis/rulecheck.go"
click node_bounds "https://github.com/google/mangle/blob/main/analysis/boundscheck.go"
click node_symbols "https://github.com/google/mangle/blob/main/symbols/symbols.go"
click node_interpreter "https://github.com/google/mangle/blob/main/interpreter/interpreter.go"
click node_engine "https://github.com/google/mangle/blob/main/engine/seminaivebottomup.go"
click node_temporalengine "https://github.com/google/mangle/blob/main/engine/temporal.go"
click node_functions "https://github.com/google/mangle/blob/main/functional/functional.go"
click node_builtins "https://github.com/google/mangle/blob/main/builtin/builtin.go"
click node_factstore "https://github.com/google/mangle/blob/main/factstore/factstore.go"
click node_columnstore "https://github.com/google/mangle/blob/main/factstore/simplecolumn.go"
click node_temporalstore "https://github.com/google/mangle/blob/main/factstore/temporal.go"
click node_provenance "https://github.com/google/mangle/blob/main/provenance/provenance.go"
click node_mgwhy "https://github.com/google/mangle/blob/main/cmd/mgwhy/main.go"
click node_structadapters "https://github.com/google/mangle/blob/main/json2struct/json2struct.go"

classDef toneNeutral fill:#f8fafc,stroke:#334155,stroke-width:1.5px,color:#0f172a
classDef toneBlue fill:#dbeafe,stroke:#2563eb,stroke-width:1.5px,color:#172554
classDef toneAmber fill:#fef3c7,stroke:#d97706,stroke-width:1.5px,color:#78350f
classDef toneMint fill:#dcfce7,stroke:#16a34a,stroke-width:1.5px,color:#14532d
classDef toneRose fill:#ffe4e6,stroke:#e11d48,stroke-width:1.5px,color:#881337
classDef toneIndigo fill:#e0e7ff,stroke:#4f46e5,stroke-width:1.5px,color:#312e81
classDef toneTeal fill:#ccfbf1,stroke:#0f766e,stroke-width:1.5px,color:#134e4a
class node_parser,node_ast,node_packages,node_validation,node_ruleanalysis,node_bounds,node_symbols toneBlue
class node_engine,node_temporalengine,node_functions,node_builtins toneAmber
class node_factstore,node_columnstore,node_temporalstore,node_provenance,node_structadapters toneMint
class node_interpreter,node_mgwhy toneRose
class node_author toneIndigo
```

## Components

### Language and analysis

- [Source parser](https://github.com/google/mangle/blob/main/parse/parse.go): `parse/parse.go`
- [Rules and declarations](https://github.com/google/mangle/blob/main/ast/ast.go): `ast/ast.go`
- [Package resolution](https://github.com/google/mangle/blob/main/packages/packages.go): `packages/packages.go`
- [Program validation](https://github.com/google/mangle/blob/main/analysis/validation.go): `analysis/validation.go`
- [Rule analysis](https://github.com/google/mangle/blob/main/analysis/rulecheck.go): `analysis/rulecheck.go`
- [Bound inference](https://github.com/google/mangle/blob/main/analysis/boundscheck.go): `analysis/boundscheck.go`
- [Types and symbols](https://github.com/google/mangle/blob/main/symbols/symbols.go): `symbols/symbols.go`

### Evaluation runtime

- [Semi-naive engine](https://github.com/google/mangle/blob/main/engine/seminaivebottomup.go): `engine/seminaivebottomup.go`
- [Temporal engine](https://github.com/google/mangle/blob/main/engine/temporal.go): `engine/temporal.go`
- [Functions and reducers](https://github.com/google/mangle/blob/main/functional/functional.go): `functional/functional.go`
- [Built-in predicates](https://github.com/google/mangle/blob/main/builtin/builtin.go): `builtin/builtin.go`

### Facts and extensions

- [Fact store](https://github.com/google/mangle/blob/main/factstore/factstore.go): `factstore/factstore.go`
- [Simplecolumn storage](https://github.com/google/mangle/blob/main/factstore/simplecolumn.go): `factstore/simplecolumn.go`
- [Temporal fact store](https://github.com/google/mangle/blob/main/factstore/temporal.go): `factstore/temporal.go`
- [Proof explanations](https://github.com/google/mangle/blob/main/provenance/provenance.go): `provenance/provenance.go`
- [Structured data adapters](https://github.com/google/mangle/blob/main/json2struct/json2struct.go): `json2struct/json2struct.go`

### User interfaces

- [Interpreter](https://github.com/google/mangle/blob/main/interpreter/interpreter.go): `interpreter/interpreter.go`
- [Explanation command](https://github.com/google/mangle/blob/main/cmd/mgwhy/main.go): `cmd/mgwhy/main.go`

### Other components

- **Program author**

## Connections

- Program author → Source parser: writes source (evidence: `README.md`)
- Source parser → Rules and declarations: creates syntax (evidence: `parse/parse.go`)
- Program validation → Source parser: parses input (evidence: `analysis/validation.go`)
- Program validation → Package resolution: uses packages (evidence: `analysis/validation.go`)
- Program validation → Types and symbols: checks symbols (evidence: `analysis/validation.go`)
- Rule analysis → Rules and declarations: checks rules (evidence: `analysis/rulecheck.go`)
- Rule analysis → Types and symbols: uses types (evidence: `analysis/rulecheck.go`)
- Bound inference → Types and symbols: infers bounds (evidence: `analysis/boundscheck.go`)
- Interpreter → Source parser: parses programs (evidence: `interpreter/interpreter.go`)
- Interpreter → Semi-naive engine: evaluates rules (evidence: `interpreter/interpreter.go`)
- Interpreter → Fact store: manages facts (evidence: `interpreter/interpreter.go`)
- Semi-naive engine → Fact store: reads and writes (evidence: `engine/seminaivebottomup.go`)
- Semi-naive engine → Functions and reducers: evaluates functions (evidence: `engine/seminaivebottomup.go`)
- Semi-naive engine → Rules and declarations: evaluates clauses (evidence: `engine/seminaivebottomup.go`)
- Built-in predicates → Functions and reducers: evaluates calls (evidence: `builtin/builtin.go`)
- Temporal engine → Temporal fact store: stores intervals (evidence: `engine/temporal.go`)
- Temporal engine → Functions and reducers: uses functions (evidence: `engine/temporal.go`)
- Simplecolumn storage → Rules and declarations: serializes facts (evidence: `factstore/simplecolumn.go`)
- Explanation command → Source parser: loads program (evidence: `cmd/mgwhy/main.go`)
- Explanation command → Fact store: loads facts (evidence: `cmd/mgwhy/main.go`)
- Explanation command → Proof explanations: requests proofs (evidence: `cmd/mgwhy/main.go`)
- Proof explanations → Fact store: checks facts (evidence: `provenance/provenance.go`)
- Structured data adapters → Rules and declarations: converts structures (evidence: `json2struct/json2struct.go`)
- Program author → Temporal engine: defines temporal rules (evidence: `README.md`)
- Program author → Functions and reducers: uses aggregation (evidence: `README.md`)
