red-dragon

KO | EN

gitlite — search

#python #typescript #go #android #rust #linux #docker #cli #kubernetes #awesome-list #vue #pytorch #openai #open-source

(★ 12)

Multi-language code execution through a simple IR and deterministic VM with LLM repair / patching

red-dragon 최신버젼 다운로드

최종 버전 다운로드 (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# RedDragon

![CI](https://github.com/avishek-sen-gupta/red-dragon/actions/workflows/ci.yml/badge.svg) [![Technical Presentation](https://img.shields.io/badge/Technical-slides-blue)](https://raw.githubusercontent.com/avishek-sen-gupta/red-dragon/main/presentation/technical-presentation.html) [![Overview Presentation](https://img.shields.io/badge/Overview-slides-green)](https://raw.githubusercontent.com/avishek-sen-gupta/red-dragon/main/presentation/overview-presentation.html) [![License: MIT](https://img.shields.io/badge/License-MIT-green)](https://raw.githubusercontent.com/avishek-sen-gupta/red-dragon/main/LICENSE.md)

**RedDragon** is an experimental toolkit for **"executing" frequently-incomplete code** — the kind found in legacy code, decompiled binaries, partial extracts, and codebases with missing dependencies. It explores three ideas:

1. **Deterministic language frontends with LLM-assisted repair** — tree-sitter frontends (15 languages) and a ProLeap bridge (COBOL) handle well-formed source deterministically. When tree-sitter hits malformed syntax, an optional **LLM repair loop** fixes only the broken fragments and re-parses, maximising deterministic coverage for real-world incomplete code. All paths produce the same universal [37-opcode IR](docs/ir-reference.md).
2. **Full LLM frontends for unsupported languages** — for languages without a tree-sitter frontend, an LLM lowers source to IR entirely — supporting any language without new parser code. A chunked variant splits large files into per-function chunks via tree-sitter, lowering each independently. Both produce the same [37-opcode IR](docs/ir-reference.md).
3. **A VM that integrates LLMs to produce plausible state changes** when execution hits missing dependencies, unresolved imports, or unknown externals — keeping execution moving through incomplete programs instead of halting at the first unknown.

**Scale:** 37-opcode universal IR · 15 tree-sitter frontends + COBOL (114 enumerated features) + LLM · 14,500+ tests

When source is complete and all dependencies are present, the entire pipeline (parse → lower → execute) is **deterministic with 0 LLM calls**. LLMs are only invoked at the boundaries where information is genuinely missing.

**Note that "execution" is a tricky concept, when dealing with these many languages.** It is important to cover the big-ticket features of the supported languages, but this project makes no claims to cover all features of every language exhaustively, because that would imply (potentially) writing full-fledged compiler frontends for every language. I have taken some liberties in terms of how some of the language features are implemented at a global / language level, and I hope that this will not detract from the inherent usefulness of this toolkit.

Concretely, RedDragon does the following:

- **Parses and lowers** source in 15 languages via tree-sitter (with optional LLM-assisted repair), COBOL via ProLeap bridge, or **any language** via full LLM-based lowering — each frontend owns its parsing internally; callers only provide `source: bytes`
- **Produces** a universal flattened three-address code [IR (37 opcodes)](docs/ir-reference.md) with structured source location traceability
- **Extracts and infers types** — see [Type system](#type-system) below
- **Builds** control flow graphs from IR instructions
- **Analyses** data flow via iterative reaching definitions, def-use chains, and variable dependency graphs. An **interprocedural analysis** module (`interpreter/interprocedural/`) extends this with call graph construction (CHA for virtual dispatch), per-function summaries (1-CFA context-sensitive), depth-1 field-sensitive heap flow tracking, whole-program propagation via SCC fixpoint (Kosaraju's algorithm for strongly connected components, iterative summary stabilization within each SCC, formal-to-actual argument substitution at call sites), query interfaces for impact analysis, taint tracking, and program slicing, and an `analyze_interprocedural(cfg, registry)` entry point that orchestrates the full pipeline
- **Supports multi-file projects** — given an entry file, recursively discovers imports (all 15 languages + COBOL), resolves local dependencies, compiles each module independently, and links them into a single merged IR stream that the VM and analysis infrastructure consume unmodified — see [Multi-file project support](#multi-file-project-support) below
- **Executes** programs via a deterministic VM with **write-time type coercion** and a configurable **LLM plausible-value resolver** for unresolved calls — see [VM features](#vm-features) below

### Type system

Three-phase pipeline — **extraction**, **inference**, **coercion** — with all types represented as `TypeExpr` algebraic data types (no string roundtrips). See the full [Type System Design Document](docs/type-system.md) for details.

| Phase | What it does |
|-------|-------------|
| **Frontend extraction** | 13 statically-typed frontends extract type annotations during lowering |
| **Static inference** | `infer_types()` propagates types to fixpoint across 15 opcodes — self/this typing, generics, union widening, overload resolution, interface hierarchies, 60+ builtin return types |
| **Runtime coercion** | Immutable `TypeEnvironment` drives write-time coercion via pluggable `TypeConversionRules` |

**TypeExpr ADT:** `ScalarType`, `ParameterizedType`, `UnionType`, `FunctionType`, `TypeVar`, `UnknownType`

**Storage model:** All VM storage uses domain-typed keys (`Register`, `VarName`, `FieldName`, `Address`) and stores `TypedValue` exclusively. The heap uses accessor methods with a `NO_HEAP_OBJECT` null-object sentinel. `_resolve_reg()` preserves parameterized type information (e.g. `pointer(scalar("Dog"))`) through the full pipeline.

**Dataflow:** All 37 IR instruction classes implement a `StorageIdentifier` protocol with `reads()`/`writes()` methods.

**Scoping:** 9 block-scoped frontends use LLVM-style name mangling for shadowed variables in nested blocks, loops, and catch clauses. Function-scoped languages (Python, JavaScript `var`, Ruby, etc.) bypass this.

### VM features

The VM executes programs deterministically, tracking data flow through incomplete programs with missing imports or unknown externals entirely **without LLM calls**.

| Feature | Summary |
|---------|---------|
| **Write-time type coercion** | Register values coerced to statically-inferred types at write time (e.g. Float→Int for array indices) |
| **Class inheritance** | 10 OOP frontends extract parent chains; executor walks inheritance hierarchy on method miss; multi-level dispatch, overrides, overload accumulation |
| **Static method dispatch** | `Class.method(args)` dispatches directly via ClassRef across Java, C#, C++, PHP, Ruby |
| **Overload resolution** | Composable `OverloadResolver`: arity distance + type compatibility scoring with `TypeGraph.is_subtype_expr()` for inheritance-aware dispatch |
| **Field initializers** | Instance field initializers prepended to constructor bodies (matching javac/Roslyn/kotlinc); synthetic constructors for classes without explicit ones |
| **Implicit this** | Java, C#, C++ — bare field reads/writes in methods rewritten to `LOAD_FIELD this`/`STORE_FIELD this` when identifier matches a declared class field |
| **Property accessors** | Kotlin/Pascal custom getters/setters lowered as synthetic methods; navigation expressions intercepted; common infrastructure reusable across frontends |
| **Default parameters** | Shared `__resolve_default__` IR helper; wired for 10 frontends (Python, JS, TS, Ruby, C#, C++, Kotlin, Scala, PHP, Pascal) |
| **Symbol extraction** | All 15 frontends run pre-lowering symbol extraction building `SymbolTable` of classes, fields, methods, inheritance; used for field resolution, type seeding, constructor generation |
| **Pattern matching** | 13-type Pattern ADT; 7 language consumers (Python, C#, Java, Rust, Ruby, Kotlin, Scala); compiles to existing IR primitives; guards supported |
| **Builtins** | `len`, `range`, `print`, `str`, `slice`, etc. Method builtins (`length`/`size`/`Length`, `subList`, `substring`, `toString`) via `METHOD_TABLE`. All return `BuiltinResult` — no direct heap mutation |
| **Byte-addressed memory** | `ALLOC_REGION`/`WRITE_REGION`/`LOAD_REGION` for COBOL-style REDEFINES overlays |
| **Named continuations** | `SET_CONTINUATION`/`RESUME_CONTINUATION` for COBOL PERFORM return semantics |
| **Closures** | Shared mutable environments (capture-by-reference); mutations persist across calls and are visible to sibling closures |
| **LLM resolver** | Optionally replaces symbolic placeholders with concrete values for unresolved function/method calls |

<details>
<summary>VM feature implementation details (click to expand)</summary>

- **Class inheritance and method resolution** — the registry pre-linearizes parent chains via BFS, and the executor walks the parent chain on method miss. Method overload accumulation preserves multiple methods with the same name as `list[str]`. C++ `Util::square(5)` is lowered by a dedicated `lower_cpp_call` pass. Ruby singleton methods (`def self.method`) are registered under the bare method name. C++ static methods skip implicit `this` emission.
- **Overload resolution** — `ArityThenTypeStrategy` ranks candidates by arity distance then type compatibility score (exact=2, coercion/subtype=1, neutral=0, mismatch=-1). `DefaultTypeCompatibility` uses `TypeGraph.is_subtype_expr()` for inheritance-aware dispatch (e.g. `foo(Dog)` beats `foo(Animal)` when passing a `Dog`), with `_COMPATIBLE_PAIRS` handling primitive coercion (Int↔Float, Bool→Int) separately from subtyping.
- **Field initializer lowering** — matches how real compilers handle them: javac, Roslyn, kotlinc, scalac. Classes without explicit constructors get a synthetic `__init__` (or `__construct` for PHP). Lua table-based OOP uses a different mechanism: dotted function declarations emit `STORE_FIELD`, dotted calls emit `LOAD_FIELD` + `CALL_UNKNOWN` (ADR-104).
- **Implicit-this field store** — in constructors, bare `x = v` assignments where `x` is a declared class field are rewritten to `LOAD_VAR this` + `STORE_FIELD` at lowering time. **Implicit-this field reads** — `resolve_field` walks the class hierarchy; `_method_declared_names` tracks local variables to avoid shadowing. `reset_method_scope()` called at method entry.
- **Property accessor interception** — Kotlin: `get() = field + 1` lowered as `__get_<prop>__` with `field` resolved to raw `LOAD_FIELD`/`STORE_FIELD`. Pascal: `property Name: string read FName write SetName` supports field-targeted and method-targeted accessors. Common infrastructure in `common/property_accessors.py`.
- **Symbol extraction** — OOP languages extract class fields, methods, inheritance chains. Struct-based languages (Go, C, Rust) extract struct fields and functions. Go methods attached to receiver struct. Pascal classes extract from `declSection > declField`. COBOL uses `from_data_layout`. `resolve_field` returns `NULL_FIELD` sentinel (not `None`).
- **Pattern matching** — 13 types: Literal, Wildcard, Capture, Sequence (with Star), Mapping, Class (positional via `__match_args__`), Or, As, Value, Deref, Relational, And, Negated. CPython linear chain model with two-pass test-before-bind. Seven consumers: Python, C#, Java, Rust, Ruby, Kotlin, Scala. Decomposes into `BINOP ==`, `CALL_FUNCTION isinstance/len`, `LOAD_INDEX`, `LOAD_FIELD`, `STORE_VAR`, `BRANCH_IF`.

</details>

The execution engine is split into focused modules under `interpreter/vm/`: `vm_types.py` (state model with domain-typed keys), `vm.py` (`apply_update`, operators, register resolution), `executor.py` (37 opcode handlers dispatched by instruction type), `builtins.py` (built-in function table), `unresolved_call.py` (symbolic/LLM call resolution), and `field_fallback.py` (field access chain). Supporting modules: `cfg_types.py`, `run_types.py`, `registry.py`, and `cobol/` (COBOL type system, EBCDIC tables, IR encoder/decoder builders). All 37 IR opcodes are defined as frozen dataclasses in `interpreter/instructions.py`, with domain-typed fields (`Register`, `CodeLabel`, `VarName`, `FieldName`, `FuncName`, `BinopKind`/`UnopKind`) and `reads()`/`writes()` methods for dataflow analysis.

## How it works

```mermaid
flowchart TD
 SRC[Source Code] --> DET["tree-sitter 15 languages"]
 SRC --> COBOL["ProLeap Bridge COBOL"]
 SRC --> LLM["LLM Frontend any language"]
 SRC --> CHUNK["Chunked LLM chunk → LLM × N → renumber → reassemble"]

DET --> REPAIR["AST Repair (optional) LLM fixes ERROR/MISSING nodes"]
 REPAIR --> IR[Flattened TAC IR]
 DET -->|no errors| IR
 COBOL --> IR
 LLM --> IR
 CHUNK --> IR

IR --> CFG[Control Flow Graph]
 CFG --> DF["Dataflow Analysis reaching defs · def-use chains · dependency graphs"]
 CFG --> VM[Deterministic VM Execution]
 VM -->|symbolic values only| ORACLE[LLM Oracle]
```

For programs with concrete inputs and no external dependencies, the entire execution is **deterministic with 0 LLM calls**.

### Pipeline visualisation

![Pipeline Visualisation](https://raw.githubusercontent.com/avishek-sen-gupta/red-dragon/main/docs/pipeline-viz.gif)

### Built-in pipeline visualizer

An interactive TUI for stepping through the full pipeline (source → AST → IR → CFG → execution) is included in `viz/`:

```bash
# Single-language mode
uv run python -m viz viz/examples/pointer_demo.c -l c
uv run python -m viz viz/examples/factorial.py -l python

# Compare mode — side-by-side across languages
uv run python -m viz compare c:viz/examples/pointer_demo.c rust:viz/examples/pointer_demo.rs

# Lowering trace — interactive exploration of how frontend lowers AST to IR
uv run python -m viz lower viz/examples/factorial.py -l python

# Coverage matrix — cross-language frontend handler availability
uv run python -m viz coverage
uv run python -m viz coverage -l python,javascript,rust

# Multi-file project — compile directory, browse import graph, debug across modules
uv run python -m viz project tests/fixtures/projects/python_basic -l python
uv run python -m viz project /path/to/java/project -l java -s 500
```

Six synchronized panels: **Source** (span-highlighted), **AST** (collapsible tree, toggle `a`), **IR** (grouped by CFG block), **VM State** (heap/stack/registers with diff highlighting), **CFG** (box-drawing graph, toggle `g`), and **Step** (delta summary). Arrow keys step forward/backward, space toggles auto-play, `d` toggles **Dataflow mode** (replaces AST/VM/CFG with call-graph summaries and whole-program dependency graph, cross-highlights source and IR on function selection), `q` quits.

The **project mode** (`viz project`) compiles an entire directory via `compile_directory()` and presents a two-phase experience. **Phase 1** (Project Overview) shows a box-drawing import DAG and an entry-point picker grouped by module. Select a function or top-level execution to proceed. **Phase 2** (Execution) reuses all standard panels with **module-aware source switching**: as execution crosses module boundaries, the Source and AST panels automatically swap to the active module's content, and the Source title updates to show the current file path. Press `p` to return to the project overview.

The pipeline result also includes **interprocedural analysis** (call graph, function summaries, and whole-program dependency graph) when the source contains function definitions. The **Dataflow Summary** panel (`viz/panels/dataflow_summary_panel.py`) renders this as a collapsible tree: each function shows its callers, callees, and merged data-flow summaries across call contexts. The **Dataflow Graph** panel (`viz/panels/dataflow_graph_panel.py`) renders interprocedural data flow as a collapsible call-chain tree. Top-level call sites are discovered via `find_top_level_call_sites`, then `build_call_chain` recursively constructs a per-parameter flow tree for each callee: each parameter's data flows to return endpoints, field writes, or through inner call sites (with argument mapping) into recursive subtrees, with cycle detection via immutable visited sets. The tree widget replaces the previous flat edge list, making multi-level call chains navigable. The legacy `annotate_endpoint` and `render_graph_lines` functions remain available for programmatic use.

The **lowering trace** mode shows four panels: source with highlighted spans, a collapsible tree of handler invocations (which handler processed which AST node), handler details (emitted IR, dispatch type, module), and the full IR output. Click any node in the trace tree to see its handler, emitted instructions, and source location.

The **coverage matrix** mode displays a cross-language grid showing which AST node types each frontend handles, distinguishing language-specific handlers (`✓`) from shared/common handlers (`✓*`). Supports filtering by node type name.

### MCP Server

RedDragon exposes its compilation pipeline, VM execution, and interprocedural dataflow analysis as an [MCP (Model Context Protocol)](https://modelcontextprotocol.io) server, allowing LLMs to analyze and execute programs across all 15 supported languages.

**10 analysis tools:**
- `analyze_program(source, language)` — full pipeline analysis: functions, call graph, flow counts
- `get_function_summary(source, language, function_name)` — param→return/field flows for one function
- `get_call_chain(source, language, function_name?)` — nested call-chain tree showing data flow through calls
- `list_opcodes()` — all 37 IR opcodes with descriptions, categories, typed fields, and semantic notes
- `load_program(source, language, max_steps?)` — load and execute a program, record step-by-step trace
- `step(count?)` — advance through execution trace, get instructions and state deltas
- `run_to_end()` — skip to final state with all variable values
- `get_state()` — current VM state: call stack, variables, registers, heap
- `get_ir(function_name?)` — IR instructions, optionally filtered to one function

**Multi-file project tool:**
- `load_project(entry_file, language)` — discover imports from entry file, compile all modules, link, and analyze. Returns module count, import graph, functions, classes, and unresolved imports

**3 resources:** `reddragon://source`, `reddragon://ir`, `reddragon://cfg`

**Run:** `uv run python -m mcp_server`

**Configure in Claude Code** (`.claude/settings.json`):
```json
{
  "mcpServers": {
    "red-dragon": {
      "command": "uv",
      "args": ["run", "python", "-m", "mcp_server"],
      "cwd": "/path/to/red-dragon"
    }
  }
}
```

## Setup

### Prerequisites

- **Python >= 3.10**
- **uv**
- **JDK 17+** (COBOL frontend only)
- **Maven** (COBOL frontend only)

### Full build (including COBOL)

```bash
git clone --recurse-submodules https://github.com/avishek-sen-gupta/red-dragon.git
cd red-dragon

# 1. Python dependencies
uv sync

# 2. ProLeap COBOL bridge (requires JDK 17+ and Maven)
cd proleap-bridge && ./build.sh && cd ..
# Produces: proleap-bridge/target/proleap-bridge-0.1.0-shaded.jar

# 3. Verify
uv run python -m pytest tests/unit/ -x -q       # unit tests (no external deps)
uv run python -m pytest tests/integration/ -x -q # integration tests (needs ProLeap JAR)
```

### Minimal build (without COBOL)

```bash
git clone https://github.com/avishek-sen-gupta/red-dragon.git
cd red-dragon
uv sync
uv run python -m pytest tests/unit/ -x -q
```

All 15 tree-sitter frontends and the LLM frontends work without JDK/Maven. COBOL integration tests skip gracefully when the ProLeap JAR is not present.

### ProLeap bridge standalone usage

```bash
cat myprogram.cbl | java -jar proleap-bridge/target/proleap-bridge-0.1.0-shaded.jar
java -jar proleap-bridge/target/proleap-bridge-0.1.0-shaded.jar myprogram.cbl
java -jar proleap-bridge/target/proleap-bridge-0.1.0-shaded.jar -format TANDEM myprogram.cbl
```

### LLM API keys (optional)

Only needed for `--frontend llm` or when execution encounters symbolic values:

```bash
export ANTHROPIC_API_KEY=sk-...          # for Claude (default)
export OPENAI_API_KEY=sk-...             # for OpenAI
export HUGGING_FACE_API_TOKEN=hf_...     # for HuggingFace Inference Endpoints
# Ollama requires no API key (runs locally at localhost:11434)
```

## Usage

```bash
uv run python interpreter.py myfile.py -v            # run on a file
uv run python interpreter.py myfile.py --ir-only      # inspect IR only
uv run python interpreter.py myfile.py --cfg-only     # inspect CFG only
uv run python interpreter.py example.js -l javascript  # non-Python source
uv run python interpreter.py myfile.py -f llm -v       # LLM frontend
uv run python interpreter.py myfile.py -f chunked_llm  # chunked LLM frontend
uv run python interpreter.py example.cob -l cobol         # COBOL via ProLeap bridge
export PROLEAP_BRIDGE_JAR=/path/to/bridge.jar                 # optional: custom bridge JAR path
uv run python interpreter.py myfile.py --mermaid        # output CFG as Mermaid flowchart
uv run python interpreter.py myfile.py --mermaid --function foo  # CFG for a single function
```

| Flag | Description |
|------|-------------|
| `-v` | Print IR, CFG, and step-by-step execution |
| `-l` | Source language (default: `python`) |
| `-b` | LLM backend: `claude`, `openai`, `ollama`, `huggingface` (default: `claude`) |
| `-n` | Maximum interpretation steps (default: 100) |
| `-f` | Frontend: `deterministic`, `llm`, `chunked_llm`, `cobol` (default: `deterministic`) |
| `--ir-only` | Print the IR and exit |
| `--cfg-only` | Print the CFG and exit |
| `--mermaid` | Output CFG as a Mermaid flowchart diagram and exit |
| `--function` | Extract CFG for a single function (use with `--mermaid` or `--cfg-only`) |

### Programmatic API

All CLI pipelines are available as composable functions — no argparse required.

#### Deterministic (no LLM calls)

```python
from interpreter import lower_source, lower_and_infer, dump_ir, build_cfg_from_source, dump_cfg, dump_mermaid, extract_function_source, ir_stats, run
from interpreter.constants import Language

source = """
def factorial(n):
 if n <= 1:
 return n
 return n * factorial(n - 1)
result = factorial(6)
"""

# Parse and lower to IR via tree-sitter (0 LLM calls)
instructions = lower_source(source, language=Language.PYTHON)
instructions = lower_source(source, language="javascript")  # strings still accepted

# Get IR as text
ir_text = dump_ir(source, language=Language.PYTHON)

# Build a CFG (optionally scoped to a single function)
cfg = build_cfg_from_source(source, function_name="factorial")

# Get CFG or Mermaid text
cfg_text = dump_cfg(source)
mermaid = dump_mermaid(source, function_name="factorial")

# Extract raw source text of a named function (recursive — finds methods and nested functions)
fn_source = extract_function_source(source, "factorial", language=Language.PYTHON)

# Lower + type inference in one call (propagates frontend type seeds)
instructions, env = lower_and_infer(source, language=Language.PYTHON)
print(env.var_types)         # {"result": "Int", ...}
print(env.get_func_signature("factorial"))  # FunctionSignature(params=(...), return_type="Int")

# Get opcode frequency counts
stats = ir_stats(source, language=Language.PYTHON)  # e.g. {"CONST": 3, "STORE_VAR": 2, ...}

# Full pipeline: parse → lower → CFG → execute (deterministic, 0 LLM calls)
vm = run(source, language=Language.PYTHON, verbose=True)
frame = vm.call_stack[0]
print(frame.local_vars["result"])  # 720
```

#### With LLM calls

```python
from interpreter import lower_source, run
from interpreter.constants import Language
from interpreter import constants
from interpreter.run_types import UnresolvedCallStrategy

# LLM frontend: the LLM acts as a compiler frontend, lowering source to IR
# Works for any language, even those without a tree-sitter frontend
instructions = lower_source(
    "x = math.sqrt(16)\ny = x + 1\n",
    language=Language.PYTHON,
    frontend_type=constants.FRONTEND_LLM,       # or "chunked_llm" for large files
    backend="claude",                            # or "openai", "ollama", "huggingface"
)

# LLM resolver: deterministic frontend + LLM resolves external/missing dependencies
# math.sqrt and math.floor are external — the LLM provides plausible concrete values
vm = run(
    "import math\nx = math.sqrt(16)\ny = math.floor(7.8)\n",
    language=Language.PYTHON,
    unresolved_call_strategy=UnresolvedCallStrategy.LLM,
    backend="claude",
)
frame = vm.call_stack[0]
print(frame.local_vars["x"])  # 4.0 (resolved by LLM)
print(frame.local_vars["y"])  # 7   (resolved by LLM)

# LLM frontend for an unsupported language (no tree-sitter frontend needed)
from interpreter.llm_client import get_llm_client
from interpreter.llm_frontend import LLMFrontend
from interpreter.constants import LLMProvider
from interpreter.cfg import build_cfg
from interpreter.registry import build_registry
from interpreter import execute_cfg, VMConfig

haskell_source = "factorial 0 = 1\nfactorial n = n * factorial (n - 1)\nx = factorial 5\n"
llm_client = get_llm_client(provider=LLMProvider.CLAUDE)  # or "claude" (StrEnum)
frontend = LLMFrontend(llm_client=llm_client, language="haskell")
instructions = frontend.lower(haskell_source.encode("utf-8"))

cfg = build_cfg(instructions)
registry = build_registry(instructions, cfg)
vm, stats = execute_cfg(cfg, cfg.entry, registry, VMConfig(max_steps=200))
```

#### Standalone VM execution

`execute_cfg` runs a pre-built CFG without re-running the full parse → lower → build pipeline — useful for programmatic use where you build/customize the CFG and registry independently:

```python
from interpreter import lower_source, execute_cfg, VMConfig
from interpreter.constants import Language
from interpreter.cfg import build_cfg
from interpreter.registry import build_registry

instructions = lower_source(source, language=Language.PYTHON)
cfg = build_cfg(instructions)
registry = build_registry(instructions, cfg)

vm, stats = execute_cfg(cfg, "entry", registry, VMConfig(max_steps=200))
# stats.steps, stats.llm_calls, stats.final_heap_objects, ...
```

| Function | Returns | Purpose |
|---|---|---|
| `lower_source(source, language, frontend_type, backend)` | `list[InstructionBase]` | Parse + lower source to IR (37 per-opcode frozen dataclasses) |
| `lower_and_infer(source, language, frontend_type, backend)` | `(list[InstructionBase], TypeEnvironment)` | Lower + type inference with frontend type seeds |
| `dump_ir(source, language, frontend_type, backend)` | `str` | IR text output |
| `build_cfg_from_source(source, language, frontend_type, backend, function_name)` | `CFG` | Parse → lower → optionally slice → build CFG |
| `dump_cfg(source, language, frontend_type, backend, function_name)` | `str` | CFG text output |
| `dump_mermaid(source, language, frontend_type, backend, function_name)` | `str` | Mermaid flowchart output |
| `ir_stats(source, language, frontend_type, backend)` | `dict[str, int]` | Opcode frequency counts |
| `extract_function_source(source, function_name, language)` | `str` | Raw source text of a named function (recursive AST walk) |
| `execute_cfg(cfg, entry_point, registry, config)` | `(VMState, ExecutionStats)` | Execute a pre-built CFG from a given entry point |
| `execute_traced(source, language, function_name, entry_point, frontend_type, backend, max_steps)` | `ExecutionTrace` | Parse → lower → CFG → execute with per-step VMState snapshots for replay |
| `analyze_project(entry_file, language, project_root?)` | `InterproceduralResult` | Multi-file: discover → compile → link → interprocedural analysis |
| `run_project(entry_file, language, project_root?, max_steps?, verbose?)` | `VMState` | Multi-file: discover → compile → link → execute |

Functions compose hierarchically: `dump_ir` calls `lower_source`; `dump_cfg` and `dump_mermaid` call `build_cfg_from_source`, which calls `lower_source`. Full execution is available via `interpreter.run()`, via `execute_cfg()` for standalone VM execution with a pre-built CFG, or via `execute_traced()` for step-by-step replay with VMState snapshots at each instruction.

### Multi-file project support

RedDragon can analyze and execute real-world multi-file codebases. Given an entry file, it recursively discovers imports, resolves them to local files, compiles each module independently, links them into a single merged program, and runs execution or interprocedural analysis — all with the same deterministic pipeline.

**Supported across all 15 deterministic frontends + COBOL** — Python, JavaScript, TypeScript, Java, Go, Rust, C, C++, C#, Kotlin, Scala, Ruby, PHP, Lua, Pascal, COBOL.

```python
from interpreter.api import analyze_project, run_project
from interpreter.constants import Language

# Multi-file interprocedural analysis
result = analyze_project("src/main.py", Language.PYTHON)
# result.call_graph — cross-module call graph
# result.summaries — per-function dataflow summaries
# result.whole_program_graph — whole-program dependency graph

# Multi-file execution
vm = run_project("src/main.py", Language.PYTHON, max_steps=500)
frame = vm.call_stack[0]
print(frame.local_vars["result"])  # concrete value from cross-module execution
```

The pipeline:

```
Entry file (main.py)
    │ extract_imports()  — tree-sitter or regex (COBOL)
    ▼
Dependency graph (BFS + topological sort)
    │ [Java] pre-scan → NamespaceTree → JavaNamespaceResolver
    │ compile_module()  — existing lower() pipeline per file
    ▼
list[ModuleUnit]
    │ link_modules()  — strip entry labels, namespace, rebase, drop import stubs
    ▼                    concatenate deps-first → single IR stream
LinkedProgram
    │
    ├──► execute_cfg()             (no VM changes)
    └──► analyze_interprocedural() (no analysis changes)
```

- **Import extraction** uses tree-sitter ASTs (not regex) for each language's import syntax
- **Resolution** is per-language: Python's `import X` / `from X import Y`, JS/TS `import`/`require`, Java package paths, C/C++ `#include`, Rust `use`/`mod`, Go grouped imports, etc.
- **Linking** strips per-module entry labels, namespaces all IR labels and registers, drops resolved import stubs, and concatenates everything — dependencies first, entry module last — producing a single IR stream indistinguishable from single-file compilation
- **System imports** (stdlib, npm packages, maven artifacts) are automatically skipped — only local project files are compiled
- **Cyclic imports** are detected and reported with the full cycle path
- **Namespace resolution** (Java) — fully-qualified references like `java.util.Arrays.fill(arr, 0)` are resolved at compile time via a `NamespaceTree` that maps package paths to types. The pre-scan phase extracts package + class names from all source files, builds a tree from project classes + stdlib stubs, and an injectable `JavaNamespaceResolver` intercepts `lower_field_access` to emit `LoadVar(short_name)` instead of cascading `LOAD_VAR "java"` → `LOAD_FIELD "util"` → `LOAD_FIELD "Arrays"` chains. This resolves to the same `ClassRef` dispatch path used by unqualified references

## Supported languages

15 deterministic tree-sitter frontends (0 LLM calls):

Python, JavaScript, TypeScript, Java, Ruby, Go, PHP, C#, C, C++, Rust, Kotlin, Scala, Lua, Pascal

Control flow constructs (if/else, while, for, for-of/foreach, switch, break/continue, try/catch/finally, do-while) are lowered into real LABEL+BRANCH IR rather than `SYMBOLIC` placeholders. For-each style loops (for-of, for-in, range-for, enhanced-for) use DECL_VAR/LOAD_VAR for the loop index counter so that SSA-immutable registers correctly advance each iteration. Built-in functions `len()` and `keys()` produce concrete results from heap objects, and Lua `ipairs()`/`pairs()` wrappers are stripped at lowering time, ensuring all for-each loops terminate correctly. Spread/splat arguments (`*args` in Python/Ruby/Kotlin, `...arr` in JS, `...$arr` in PHP) are represented as `SpreadArguments` operands in the IR — the VM unpacks heap arrays into individual call arguments at execution time (ADR-109). Methods stored as heap object fields (Lua table OOP, JS/Python dynamic properties) are resolved by `CALL_METHOD` automatically (ADR-110).

<details>
<summary>Language-specific features (click to expand)</summary>

| Language | Supported constructs |
|----------|---------------------|
| **Python** | list/dict/set comprehensions (including nested), generator expressions, with statements, decorators, lambdas, yield/await, assert, import/from-import, walrus operator (`:=`), match statements with structural pattern matching (3.10+ — literal, wildcard, capture, sequence, mapping, class, or, as patterns + guards, star/splat patterns `[first, *rest]` including star-at-start, star-at-end, star-in-middle, and nested star patterns, value patterns via dotted constant lookup `case Color.RED:` and multi-level `case HTTP.Status.OK:`), delete, slicing, f-string interpolation, list/dict/splat patterns, ellipsis (`...`), splat/spread (`*args`, `**kwargs` in expressions), expression lists, dotted names |
| **JS/TS** | destructuring (including rest patterns `[a, ...rest]` and `{a, ...rest}`), for-of/for-in loops, switch, do-while, new expressions, template string substitutions, regex literals, spread/sequence/yield/await expressions, function expressions, class static blocks, labeled statements, abstract classes (TS), import/export statements, public field definitions (TS), class field definitions (`#private = 0`), export clauses (`export { a, b }`), with statements, abstract method signatures (TS), namespaces/internal modules (TS) |
| **Ruby** | symbols, ranges, regex, lambdas, string/symbol arrays (`%w`/`%i`), case/when, case/in structural pattern matching via Pattern ADT (`parse_ruby_pattern` — literal int/str/float, wildcard `_`, capture, `alternative_pattern` → OrPattern, `array_pattern` → SequencePattern with `*rest` StarPattern, `hash_pattern` → MappingPattern with keyword shorthand `{name:}`, `as_pattern` `X => binding`, `constant` → ClassPattern, `Point[x, y]` class pattern with positional sub-patterns, unary negative literals `-1`), modules, global/class variables, heredocs, if/unless/while/until modifiers, ternary operator, unary operators, `self`, singleton classes/methods, element reference (array indexing), string interpolation (`"Hello #{expr}"`), heredoc interpolation (`<<~HEREDOC\nHello #{expr}\nHEREDOC`), hash key symbols, `super`, `yield`, delimited symbols (`:"dynamic"`), `retry`, class instantiation (`Counter.new()`), instance variable field semantics (`@var` → `LOAD_FIELD`/`STORE_FIELD`), `initialize` → `__init__` constructor mapping, scope resolution (`Module::Class`), rescue modifier (`expr rescue fallback`), array slicing (`arr[1..3]` inclusive, `arr[1...3]` exclusive, `arr[start, length]` positional) |
| **PHP** | switch, do-while, match expressions, arrow functions, scoped calls (`Class::method`), namespaces, interfaces, traits, enums, static variables, goto/labels, anonymous functions (closures), null-safe access (`?->`), null-safe method calls (`?->method()`), class constant access, property declarations, yield, heredoc/nowdoc, string interpolation (`"Hello $name"` / `"Hello {$expr}"` / heredoc interpolation), relative scope (`self::`/`static::`), dynamic variable names (`$$x`), global declarations, include/require_once expressions, variadic unpacking (`...$arr`), `print` intrinsic, `clone` expressions (shallow heap copy), `const` declarations, error suppression (`@expr`), `exit`/`die`, `declare`, `unset`, `list()` destructuring (`list($a, $b) = $arr`), `strlen` builtin, anonymous classes (`new class { ... }`) |
| **Java** | records, instanceof with type patterns and record patterns (Java 16+: `o instanceof String s` binding, `o instanceof Point(int x, int y)` record destructuring), method references (`Type::method`), lambdas, class literals (`Type.class`), do-while, assert, labeled statements, synchronized blocks, static initializers, explicit constructor invocations (`super()`/`this()`), annotation type declarations, scoped identifiers (`java.lang.System`), switch expressions (Java 14+, including expression_statement, throw in arms, `yield` in block arms, and pattern matching with type patterns, guards (`when` clauses), and wildcard `_`), hex floating point literals (`0x1.0p10`) |
| **C#** | await, yield, switch expressions (C# 8) with pattern matching (constant, declaration/var, recursive/property, or, list, parenthesized, relational `> 5`, and `> 0 and < 10`, negated `not 0` patterns), lock, using statements, checked/fixed blocks, events, typeof, is-check, property declarations, lambdas, null-conditional access (`?.`), local functions, tuples, is-pattern expressions, declaration patterns, array initializer expressions, string interpolation (`$"Hello {expr}"` — format specifiers and alignment clauses are discarded as presentation-only), record declarations, verbatim strings (`@"..."`), constant patterns, delegate declarations, implicit object creation (`new()`), LINQ query expressions (`from...where...select`), throw expressions (`x ?? throw new ...`), goto/labeled statements, `default` expressions, `sizeof` expressions, `checked`/`unchecked` expressions, `out`/`ref`/`in` parameter modifiers with pass-by-reference semantics (callee writes propagate to caller via ADDRESS_OF/Pointer infrastructure), anonymous object creation (`new { Name = "foo", Age = 42 }`) |
| **C** | pointer dereference/address-of, function pointers (`int (*fp)(int,int) = &add; (*fp)(3,5)`) including function-pointer return types (`int (*get_op(int))(int,int)`), struct pointers with arrow operator (`p->x`, pass-by-pointer, linked structures), sizeof, compound literals, struct/union/enum definitions, initializer lists (positional and designated), struct-aware initializer lists (`struct Node n = {3, 0}` and `{.value = 3}` emit `NEW_OBJECT` + `STORE_FIELD`), goto/labels, typedef, char literals, function-like macros (`#define MAX(a, b) ...`), `extern "C"` linkage specifications |
| **C++** | lambda expressions (closures), field initializer lists, delete expressions, enum class, array subscript expressions, C++20 concepts, constructor field storage (VM-injected `this`), C++17 structured bindings (`auto [a, b] = expr;`) |
| **Kotlin** | do-while, object declarations (singletons), companion objects, enum classes, not-null assertion (`!!`), is-check, type tests (`is Type` in `when`), type aliases, elvis operator (`?:`) with short-circuit throw, infix expressions, indexing expressions, type casts (`as`), conjunction/disjunction expressions, hex literals, character literals, string interpolation (`"$name"` / `"${expr}"`), multi-variable destructuring (`val (a, b) = pair`), range expressions (`1..10`), anonymous object literals (`object : Type { ... }`), anonymous function expressions (`fun(x: Int): Int { ... }`), `when` as statement and expression (subject-form uses Pattern ADT via `parse_kotlin_pattern`; subjectless form evaluates boolean conditions directly), labels (`outer@`), unsigned literals (`42u`, `42UL`), callable references (`::functionName`), spread expressions (`*array`), wildcard imports (`import foo.*`), `subList`/`substring` method builtins, primary constructor `val` params (`class Node(val x: Int)`) |
| **Go** | defer, go, switch/type-switch/select, channel send/receive (including `select` receive statements), slices, type assertions, func literals, labeled statements, const declarations, goto, multi-name var declarations (`var a, b = 1, 2`), var blocks (`var (...)`), type conversions (`int(x)`, `[]byte(s)`), generic types (`Foo[int]`), rune literals (`'a'`), blank identifier (`_`), fallthrough (no-op), `make()` desugaring (`make(map[K]V)` → NEW_OBJECT, `make([]T, n)` → NEW_ARRAY) |
| **Rust** | closures (`\|x\| expr`), traits, enums, const/static/type items, try (`?`), await, async blocks, mod/unsafe blocks, type casts (`as`), scoped identifiers (`HashMap::new`), tuple destructuring (`let (a, b) = expr`), struct destructuring (`let Point { x, y } = p`), range expressions and slicing (`arr[0..10]`, `arr[0..=n]`), structural pattern matching via Pattern ADT (literal, wildcard, capture, or-pattern `1 \| 2 => ...`, tuple struct `Some(v)`, struct `Point { x, y }`, guard clauses `n if n > 0 => ...`, scoped identifiers), generic/turbofish syntax (`parse::<i32>()`), `if let`/`while let` conditions, trait function signatures (`fn area(&self) -> f64;`), unit expression (`()`), raw string literals (`r"..."`, `r#"..."#`), negative literals in match patterns (`-1 => ...`), Box auto-deref (`Box::new(x).field` and `Box::new(x).method()` delegate through `__method_missing__` / `__boxed__` chain including `Box<Box<T>>` multi-level), impl method implicit return (`self.field` at end of method body is the return value — expression-oriented semantics) |
| **Scala** | for-comprehensions, traits, case classes, lazy vals, do-while, type definitions, `new` expressions with argument passing, throw expressions, string interpolation (`s"$name"` / `s"${expr}"`), tuple destructuring (`val (a, b) = expr`), operator identifiers, structural pattern matching via Pattern ADT (literal, wildcard, capture, alternative `1 \| 2`, case class `Circle(r)`, typed `i: Int`, tuple `(a, b)`, guard `if condition`, stable identifiers `pkg.Foo`), abstract function declarations, infix patterns (`head :: tail`), case blocks, generic/parameterized calls (`foo[Int](x)`), postfix expressions (`list sorted`), stable type identifiers (`pkg.Class`), export declarations (Scala 3), array indexing (`arr(i)` read/write via apply semantics), primary constructor `val` params (`class Node(val x: Int)`), Scala 3 simple enums (`enum Color { case Red, Green, Blue }`) |
| **Lua** | anonymous functions, varargs, goto/labels, method calls (`obj:method()`), dotted function declarations (`function T.f()` emits STORE_FIELD), dotted function calls (`T.f()` emits LOAD_FIELD + CALL_UNKNOWN) |
| **Pascal** | nested functions, field access, array indexing, unary operators, case-of, repeat-until, set literals, const/type/uses declarations, parenthesized expressions, try/except/finally, exception handlers (`on E: Exception do`), raise, ranges (`4..10`), with statements, inherited calls, for-in loops, goto/labels, class declarations, property declarations (`property Name: string read FName write SetName;` with field/method accessor support) |

</details>

## Example: CFG

```python
def classify(x):
    if x > 0:
        label = "positive"
    else:
        label = "negative"
    return label
```

```mermaid
flowchart TD
 entry(["entry LOAD x · CONST 0 · BINOP > BRANCH_IF"])
 if_true["if_true CONST &quot;positive&quot; STORE_VAR label"]
 if_false["if_false CONST &quot;negative&quot; STORE_VAR label"]
 merge(["merge LOAD_VAR label RETURN"])

entry -- T --> if_true
    entry -- F --> if_false
    if_true --> merge
    if_false --> merge
```

Function bodies appear as subgraphs with dashed call edges (`-.->|"call"|`) connecting `CALL_FUNCTION` sites to function entry blocks. Blocks with more than 6 instructions are collapsed to show the first 4 lines, an `... (N more)` placeholder, and the terminator — keeping CFG diagrams readable without hiding critical branch/return instructions. All 15 frontends produce the same CFG shape for equivalent logic.

## Example: deterministic execution (0 LLM calls)

```python
def factorial(n):
 if n <= 1:
 return 1
 else:
 return n * factorial(n - 1)

result = factorial(5)
```

```
[step 4] call factorial(5) → dispatch to func_factorial_0
[step 53] binop 1 <= 1 = True ← base case
[step 56] return 1 ← unwind begins
[step 57] 2 * 1 = 2 → 3 * 2 = 6 → 4 * 6 = 24 → 5 * 24 = 120
[step 65] store_var result 120

Final state: result = 120  (67 steps, 0 LLM calls)
```

The VM also handles — all deterministically:

- **Classes & Arrays** — heap allocation via `Pointer(base, offset)` with parameterized types (`Pointer[ClassName]`, `Pointer[ElementType]`), method dispatch with overload resolution (arity + type + subtype-aware scoring via TypeGraph), field access
- **Closures** — shared mutable environments (capture-by-reference); mutations persist across calls and are visible to sibling closures
- **Byte-addressed memory regions** — `ALLOC_REGION`/`WRITE_REGION`/`LOAD_REGION` for COBOL-style REDEFINES overlays
- **Named continuations** — `SET_CONTINUATION`/`RESUME_CONTINUATION` for COBOL PERFORM return semantics
- **Data layout preservation** — COBOL field names, offsets, lengths, and type metadata attached to `VMState.data_layout` after execution
- **Builtins** — `len`, `range`, `print`, `int`, `str`, `slice`, `arrayOf`/`listOf`, byte-manipulation primitives, etc. Method builtins (`subList`, `substring`, `slice`, `length`/`size`/`Length`, `toString`) dispatch through `METHOD_TABLE` for cross-language collection and string operations. All builtins return a `BuiltinResult(value, new_objects, heap_writes)` (defined in `vm_types.py`) instead of raw values — no builtin directly mutates `vm.heap`. Heap mutations are expressed as data in the result and applied uniformly via `StateUpdate`, keeping builtins pure and side-effect-free.

The execution engine is split into focused modules under `interpreter/vm/`: `vm_types.py`, `vm.py`, `executor.py` (37 opcode handlers), `builtins.py`, `unresolved_call.py`, and `field_fallback.py`. Supporting modules: `cfg_types.py`, `run_types.py`, `registry.py`, and `cobol/` (COBOL type system, EBCDIC tables, IR encoder/decoder builders).

## Handling incomplete programs

When the interpreter encounters incomplete information (missing imports, unknown externals), it creates symbolic placeholder values rather than erroring:

- `process(items)` where `process` is unresolved → `sym_N [process(sym_M)]`
- `obj.method(arg)` on a symbolic object → `sym_N [sym_M.method(arg)]`
- `obj.field` on a symbolic object → `sym_N` (deduplicated across repeated accesses)
- `sym_0 + 1` → `sym_N [sym_0 + 1]` (symbolic arithmetic with constraints)
- `branch_if sym_0` → takes true branch, records path condition

This means data flow through programs with missing dependencies is traced entirely deterministically with **0 LLM calls**.

### Configurable unresolved call resolution

When the VM encounters a call to an unresolved function (e.g., `math.sqrt(16)`), the default behavior creates symbolic values that propagate through subsequent computation. The `UnresolvedCallStrategy` enum controls this:

- **`SYMBOLIC`** (default) — creates symbolic placeholders: `math.sqrt(16) → sym_N`, subsequent `sym_N + 1 → sym_M` (precision death)
- **`LLM`** — makes a lightweight LLM call to get a plausible concrete value: `math.sqrt(16) → 4.0`, subsequent `4.0 + 1 = 5.0` (precision preserved), with support for side effects via `heap_writes`/`var_writes`

```python
from interpreter.run import run
from interpreter.run_types import UnresolvedCallStrategy

vm = run(source, language="python", unresolved_call_strategy=UnresolvedCallStrategy.LLM)
```

## Dataflow analysis

Iterative intraprocedural analysis on the CFG: **reaching definitions**, **def-use chains**, and **variable dependency graphs** (both direct and transitive closure). Covers all value-producing opcodes including byte-addressed memory region operations (`ALLOC_REGION`, `LOAD_REGION`, `WRITE_REGION`), ensuring complete dataflow tracking for COBOL programs.

### Example: dependency graph

```python
a = 1
b = 2
c = a + b
d = a * b
e = c + d
f = e - a

def square(x):
    return x * x

g = square(c)
h = g + f
total = h + e + b
```

Diamond dependencies (`c` and `d` both depend on `a` and `b`), function calls (`g = square(c)`), and multi-operand expressions (`total = h + e + b`). The direct dependency graph ([docs/graph.md](docs/graph.md)):

```mermaid
flowchart BT
    a["a"]
    b["b"]
    c["c"]
    d["d"]
    e["e"]
    f["f"]
    g["g"]
    h["h"]
    total["total"]
    a --> c
    b --> c
    a --> d
    b --> d
    c --> e
    d --> e
    a --> f
    e --> f
    c --> g
    f --> h
    g --> h
    b --> total
    e --> total
    h --> total
```

`total` directly depends on `h`, `e`, and `b`. The transitive closure adds `a`, `c`, `d`, `f`, and `g`. See [`scripts/demo_dataflow.py`](scripts/demo_dataflow.py) for the full pipeline (lowering → CFG → reaching definitions → dependency graph → Mermaid visualisation).

## LLM frontend

The LLM frontend (`--frontend llm`) sends source to an LLM constrained by a formal [IR schema](docs/ir-reference.md) — the LLM acts as a **compiler frontend**, not a reasoning engine. The prompt provides 24 opcode schemas used by the LLM path (including `DECL_VAR`, `CALL_CTOR`, `TRY_PUSH`, and `TRY_POP`), concrete patterns for functions/classes/control flow, a worked example for function definitions, and a worked example for array initialization (showing that each value and index needs a dedicated CONST register). An explicit rule warns against confusing register names with stored values. On malformed JSON, the call is retried up to 3 times.

The **chunked LLM frontend** (`--frontend chunked_llm`) handles large files by decomposing them into per-function/class chunks via tree-sitter, lowering each independently, then renumbering registers/labels and reassembling. Failed chunks produce `SYMBOLIC` placeholders.

All providers are accessed through [LiteLLM](https://github.com/BerriAI/litellm), a unified completion interface that routes to provider-specific APIs internally.

| Provider | Flag | Notes |
|----------|------|-------|
| Claude | `-b claude` | Requires `ANTHROPIC_API_KEY` |
| OpenAI | `-b openai` | Requires `OPENAI_API_KEY` |
| HuggingFace | `-b huggingface` | Inference Endpoints, requires `HUGGING_FACE_API_TOKEN` |
| Ollama | `-b ollama` | Local, no API key needed |

Demo scripts exercising the LLM integration:

```bash
uv run python scripts/demo_llm_e2e.py             # LLM frontend + LLM resolver (Python)
uv run python scripts/demo_unsupported_language_haskell.py  # LLM frontend for Haskell (no tree-sitter)
uv run python scripts/run_chunked_demo.py           # chunked LLM frontend
uv run python scripts/demo_ast_repair.py            # LLM-assisted AST repair for malformed source
```

## LLM-assisted AST repair

When tree-sitter parses malformed source, it produces ERROR/MISSING nodes that fall through to `SYMBOLIC "unsupported:ERROR"`. The **AST repair** feature uses an LLM to fix broken syntax before deterministic lowering, maximising deterministic IR coverage for real-world incomplete code.

```python
from interpreter.frontend import get_frontend
from interpreter.llm.llm_client import get_llm_client

repair_llm = get_llm_client(provider="claude")
frontend = get_frontend("python", repair_client=repair_llm)
ir = frontend.lower(malformed_source)
```

The repair is:
- **Optional** — enabled only when `repair_client` is provided to `get_frontend()`
- **Centralised** — wraps any deterministic frontend via decorator; all 15 languages get it for free
- **Retry-capable** — configurable max attempts (`RepairConfig(max_retries=3)`)
- **Safe** — if all retries fail, falls back to the original source (ERROR nodes become SYMBOLIC as before)

## Testing

```bash
uv run pytest tests/ -v          # all tests (parallel by default via pytest-xdist)
uv run pytest tests/unit/ -v     # unit tests only
uv run pytest tests/integration/ -v  # integration tests only
uv run pytest tests/ -n 0 -v     # disable parallel execution
```

Tests are organised into `tests/unit/` (pure logic, no I/O) and `tests/integration/` (LLM calls, databases, external repos). Unit tests use dependency injection (no real LLM calls).

Current suite size: **14,533 collected tests** (`uv run python -m pytest tests/ --co -q`).

**Coverage areas:**

- **Language frontends** — all 15 tree-sitter frontends, LLM frontend, chunked LLM frontend
- **CFG and dataflow** — CFG building, reaching definitions, def-use chains, dependency graphs
- **Cross-language semantics** — closures (mutation persistence, accumulator semantics, nested-function and lambda forms), classes with method dispatch and overload resolution (12 languages), field access, exception handling, destructuring, variable scoping
- **Multi-file projects** — import extraction (all 15 languages + COBOL), import resolution, topological sort, cycle detection, module compilation, linking (label namespacing, register rebasing, import stub dropping), namespace resolution (Java qualified references via `NamespaceTree`), multi-file VM execution for every language, API and MCP integration
- **Frontend type extraction** — 13 statically-typed frontends verified to populate `TypeEnvironmentBuilder` with register types, variable types, function return types, parameter types, and this/self class typing from source-level annotations
- **Static type inference** — type propagation through 15 opcode chains, builtin return types, RETURN backfill, UNOP refinement, class method/field tracking, region tagging, CALL_UNKNOWN resolution, array element tracking, function signatures across 13 languages; comprehensive cross-language integration tests covering BINOP (int+int, int+float, comparison→Bool), UNOP (not/!→Bool, Lua #→Int), return backfill, typed param seeding, field tracking, CALL_METHOD return types, and NEW_OBJECT typing across all 15 languages
- **VM execution** — deterministic execution, write-time type coercion, factory routing
- **Composable API** — `lower_source`, `lower_and_infer`, `dump_ir`, `build_cfg_from_source`, etc.

### Rosetta cross-language suite

The **Rosetta suite** (`tests/unit/rosetta/`) implements 28 cross-language test sets and verifies they produce clean, structurally consistent IR:

- **10 algorithms** — all 15 languages: factorial (recursive + iterative), fibonacci, gcd, bubble sort, binary search, ackermann, is_prime, fizzbuzz, interprocedural
- **10 semantic patterns** — all 15 languages: higher-order, method chaining, string concat, nested loops, linked list, boolean logic, bitwise, unary operators, ternary, array accumulate
- **closures** — all 15 languages
- **closures-lambda** — 5 languages with lambda/arrow syntax (Python, JS, TS, Kotlin, Scala)
- **classes** — all 15 languages
- **exceptions** — all 15 languages
- **variable scoping** — all 15 languages
- **destructuring** — 6 languages (Python, JS, TS, Rust, Scala, Kotlin) in variable declarations; for-loop destructuring in JS/TS (`for (const [k, v] of arr)`), Kotlin (`for ((a, b) in pairs)`), and C++ (`for (auto [a, b] : pairs)`); C++ declaration-level structured bindings (`auto [a, b] = expr;`)
- **nested functions** — 12 languages (Python, JS, TS, Rust, Lua, Ruby, Go, Kotlin, Scala, PHP, C#, Pascal)
- **pattern matching** — 6 languages (Python, C#, Rust, Scala, Kotlin, Ruby) all classifying a number through `match`/`switch`/`case/in` and asserting `result == "small"`

Each problem tests:

- Entry label presence and minimum instruction count
- Zero unsupported `SYMBOLIC` nodes
- Required opcode presence and operator spot-checks
- Aggregate cross-language variance

**VM execution verification** runs algorithms, closures, classes, exceptions, destructuring, nested functions, and variable scoping through the VM with zero LLM calls, asserting correct computed results:

| Test | Expected |
|------|----------|
| factorial | 120 |
| fib(10) | 55 |
| gcd(48, 18) | 6 |
| sorting | sorted arrays |
| interprocedural double_add(3, 4) | 14 |
| closure make_adder(10)(5) | 15 |
| counter | 3 |
| try-body | -1 |
| destructured a+b | 15 |
| nested outer(3) | 11 |
| callee(99) with caller's x=42 | 198, x preserved |
| ack(2, 3) | 9 |
| isqrt(49) binary search | 7 |
| higher-order apply(double, 5) | 10 |
| pattern matching dispatch(2) | 20 |
| linked list sum_list(3) | 6 |
| string concat | "hello world" |
| ternary abs(-5) | 5 |
| boolean (a AND NOT b) OR false | True |
| bitwise (12 & 10) ^ 5 | 13 |
| unary -(-7) | 7 |
| array accumulate sum([1..5]) | 15 |
| method chaining counter.inc().inc().get() | 2 |
| nested loops count pairs(1..4) | 6 |

**Inner function scoping** is verified for 9 languages (Python, JavaScript, TypeScript, Rust, Go, Kotlin, Scala, C#, Pascal) — inner functions are inaccessible outside the enclosing scope (the VM produces a symbolic value instead of a concrete result).

**Python comprehension scoping** follows Python 3 semantics — loop variables in list, dict, set comprehensions and generator expressions are scoped to the comprehension body using `enter_block_scope`/`exit_block_scope` with name mangling, preventing leakage to the enclosing scope.

**Pointer aliasing** uses a KLEE-inspired promote-on-address-of model for C and Rust. The `ADDRESS_OF` opcode promotes primitive variables to heap-backed storage when their address is taken (`&x`), enabling `*ptr = 99` to correctly update the original variable. Supports nested pointers (`int **pp = &ptr`), pointer arithmetic (`ptr + n`, `ptr - ptr`), pointer comparison (`<`, `>`, `<=`, `>=`, `==`, `!=`), struct pointers (`ptr->field`), and array pointer decay. Dereference reads (`*ptr`) emit `LOAD_INDIRECT ptr` and dereference writes (`*ptr = val`) emit `STORE_INDIRECT ptr, val` as dedicated opcodes for pointer resolution through the executor.

All frontends emit **canonical Python-form literals** (`"None"`, `"True"`, `"False"`) — language-native forms (`nil`, `null`, `undefined`, `NULL`, `true`, `false`) are canonicalized at lowering time.

### Equivalence suite

The **equivalence suite** (`tests/unit/equivalence/`) verifies that all 15 frontends produce **structurally identical IR** for the same algorithm. Function bodies are extracted, LABEL pseudo-instructions stripped, and raw opcode sequences compared across all languages. Currently covers recursive and iterative factorial. Iterative factorial achieves 14-language equivalence (Pascal excluded — its implicit return uses `LOAD_VAR Result` instead of `CONST None`, verified separately); recursive factorial has 4 frontends (kotlin, pascal, rust, scala) with minor redundant instructions pending cleanup.

### Exercism integration suite

The **Exercism suite** (`tests/unit/exercism/`) pulls canonical test data from [Exercism's problem-specifications](https://github.com/exercism/problem-specifications) and runs solutions in all 15 languages. Each exercise is parametrized across all canonical test cases.

<details>
<summary>Exercism exercise breakdown (click to expand)</summary>

| Exercise | Constructs tested | Cases | Execution |
|----------|-------------------|-------|-----------|
| **leap** | modulo, boolean logic, short-circuit eval | 9 | 270 |
| **collatz-conjecture** | while loop, conditional, integer division | 4 | 120 |
| **difference-of-squares** | while loop, accumulator, function composition | 9 | 270 |
| **two-fer** | string concatenation, string literals | 3 | 90 |
| **hamming** | string indexing, character comparison, while loop | 5 | 150 |
| **reverse-string** | backward iteration, string building | 5 | 150 |
| **rna-transcription** | multi-branch if, char mapping | 6 | 180 |
| **perfect-numbers** | divisor loop, three-way return | 9 | 270 |
| **triangle** | nested ifs, validity guards, float sides | 21 | 630 |
| **space-age** | float division, string-to-number mapping | 8 | 240 |
| **grains** | exponentiation, large integers (2^63) | 8 | 240 |
| **isogram** | nested while loops, case-insensitive comparison | 14 | 420 |
| **nth-prime** | nested loops, trial division, primality testing | 3 | 90 |
| **resistor-color** | string-to-integer mapping, string equality | 3 | 90 |
| **pangram** | nested loops, letter search, toLowerChar helper | 11 | 330 |
| **bob** | string classification, multi-branch return | 22 | 616 |
| **luhn** | charToDigit helper, right-to-left traversal, modulo | 22 | 660 |
| **acronym** | toUpperChar helper, word boundary detection | 9 | 252 |
| **Total** | | **171** | **5,068** |

</details>

## Code quality

Static analysis tools run in CI as a report-only job (non-blocking). To run locally:

```bash
uv run radon cc interpreter/ -s -n C       # cyclomatic complexity (grade C and above)
uv run radon mi interpreter/ -s -n B        # maintainability index (grade B and below)
uv run pylint interpreter/ --exit-zero      # linting (report only)
uv run lint-imports                         # architectural import contracts
uv run pydeps interpreter --no-show -T png  # dependency graph (requires graphviz)
```

| Tool | Purpose |
|------|---------|
| [radon](https://radon.readthedocs.io/) | Cyclomatic complexity and maintainability index |
| [pylint](https://pylint.readthedocs.io/) | Static linting (configured in `.pylintrc`) |
| [import-linter](https://import-linter.readthedocs.io/) | Architectural boundary contracts (configured in `.importlinter`) |
| [pydeps](https://github.com/thebjorn/pydeps) | Module dependency visualization |

Import-linter enforces five architectural contracts:

| Contract | Rule |
|----------|------|
| `vm-no-frontend` | VM, handlers, and run layer must not import frontends |
| `ir-is-leaf` | IR module must not import any other interpreter module |
| `project-no-vm-internals` | Project module must not import VM or handler internals |
| `frontend-independence` | Language frontends must not import each other |
| `cobol-isolation` | COBOL module may only be imported by the frontend factory |

## Documentation

- **[IR Reference](docs/ir-reference.md)** — Complete specification of the 37-opcode instruction set: value producers, consumers, control flow, region operations, continuations, pointer operations, and the SYMBOLIC fallback
- **[VM Design Document](docs/notes-on-vm-design.md)** — Comprehensive technical deep-dive into the VM architecture: IR design, CFG construction, state model, execution engine, call dispatch, best-effort execution, closures, LLM fallback, dataflow analysis, and end-to-end worked examples with code references
- **[Frontend Design Document](docs/notes-on-frontend-design.md)** — Frontend subsystem overview: three frontend strategies (deterministic, LLM, chunked LLM), Frontend ABC contract, tree-sitter parser layer, LLM frontend with prompt engineering, chunked LLM frontend with register renumbering, factory routing, and end-to-end worked example
- **[Per-Language Frontend Design](docs/frontend-design/)** — Exhaustive per-language documentation of all 15 deterministic frontends and the COBOL frontend: BaseFrontend context-mode architecture, GrammarConstants, TreeSitterEmitContext, common lowerers, dispatch tables, language-specific lowering methods, and worked examples for each language
- **[COBOL Frontend Design](docs/frontend-design/cobol.md)** — ProLeap bridge architecture, PIC-driven encoding, 20-statement coverage matrix, PERFORM continuation semantics, SEARCH/STRING/INSPECT lowering patterns; 112-feature enumeration via `CobolFeature` enum (test-gated)
- **[Linker & Multi-File Design](docs/linker-design.md)** — Multi-file project pipeline: import discovery, resolution, per-module compilation, linking (namespace, rebase, merge), worked example, and per-language import extraction reference
- **[Type System Design Document](docs/type-system.md)** — Type system architecture: TypeGraph DAG with subtype/LUB queries, frontend type extraction and seeding, fixpoint inference algorithm with per-opcode dispatch, TypeConversionRules for operator coercion and assignment narrowing/widening, write-time coercion in the VM, and end-to-end worked examples with Mermaid diagrams
- **[Dataflow Design Document](docs/notes-on-dataflow-design.md)** — Dataflow analysis architecture: reaching definitions via GEN/KILL worklist fixpoint, def-use chain extraction, variable dependency graph construction with transitive closure, integration with IR/CFG, worked examples, and complexity analysis
- **[Architectural Decision Records](docs/architectural-design-decisions.md)** — Chronological log of key architectural decisions: IR design, deterministic VM, best-effort execution, closure semantics, LLM frontend strategy, dataflow analysis, modular package structure, and more

## Limitations

This is an experimental project. Key limitations to be aware of:

- **No standard library implementations.** Language standard libraries are not implemented. The VM provides a small set of builtins (string operations, basic I/O, arithmetic) but calls to standard library functions (e.g., `Collections.sort()` in Java, `itertools` in Python) will produce symbolic values or fall back to the LLM oracle.
- **Language feature coverage is evolving.** Frontend support for each language is tested through [Exercism](#exercism-integration-suite) and [Rosetta](#rosetta-cross-language-suite) cross-language suites, but not every language construct is covered. Edge cases in complex features (e.g., advanced pattern matching, generator expressions, async/await) may lower incorrectly or produce `SYMBOLIC` nodes. See the [Frontend Lowering Gap Analysis](docs/frontend-lowering-gaps.md) for detailed status — 956 features tracked across 16 languages, with 758 covered (79%).
- **LLM frontends are non-deterministic.** The LLM and chunked-LLM frontends produce valid IR in most cases, but outputs can vary between runs and may occasionally generate structurally incorrect IR despite schema constraints and retries.
- **No concurrency or I/O modelling.** The VM is single-threaded and does not model file I/O, network calls, or concurrency primitives. Programs relying on these will hit symbolic boundaries.
- **COBOL frontend requires external tooling.** The ProLeap bridge needs JDK 17+ and a separately-built JAR. It is not included in the default Poetry install.

red-dragon

red-dragon 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

red-dragon

red-dragon 최신버젼 다운로드

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

Download README