PyRCC — Reverse C Compiler in Python

PyRCC transforms a restricted subset of C into forward and reverse (invertible) code. It generates both a forward variant (with history logging) and a reverse variant (history replay with inverted operations), producing self-contained C output.

The compiler uses Bennett's method: explicit value_log, branch_log, and loop_log stacks record the information lost during forward execution, enabling exact state restoration during reverse execution.

Architecture

C source → frontend.py (parse + lower) → IR → transform.py (fwd/rev) → codegen_c.py → C output

The pipeline is entirely in Python. The generated output is C code.

Supported Syntax

Paper-Aligned Core (--paper-core)

A minimal subset for research purposes:

• file-scope int globals with constant-expression initializers
• a single void step(void) entry function
• integer local variables and block-local declarations with alpha-renaming
• simple = assignments
• pure integer expressions (+, -, *)
• comparison conditions (==, !=, <, <=, >, >=)
• structured if / while
• forward/reverse transformation with explicit history logs

Prototype Extensions (default)

The full prototype additionally supports:

• Types: int, unsigned int, unsigned char, unsigned short, unsigned long, float, double, char, short, long scalars; fixed-size arrays (1D and multi-dimensional); 1D local scalar VLA with runtime length guards; struct with nested struct fields and arrays of struct
• Pointers: scalar, array-element, and struct-field aliasing; constant and non-literal-constant offsets; dynamic p = &a[i]; minimal int ** aliasing (pp = &p, **pp); -> / (*p).field
• Control flow: for, do-while, break, continue, same-block forward goto, cross-block goto from if bodies, minimal same-block backward goto loops
• Operators: compound assignments, ++/--, ternary ?:, comma, assignment expressions, short-circuit &&/||
• Functions: void/returning helpers, early return, direct self tail recursion, additive self recursion, minimal two-helper tail mutual recursion, loops inside recursive helpers
• I/O: print_int(), putchar(), puts()
• Optimizations: dead history elimination (consecutive writes, constant conditions, first-write), Shannon entropy analysis

Installation

python -m venv .venv
source .venv/bin/activate
pip install -e .

CLI

Generate C:

pyrcc input.c -o generated.c --runtime-dir out
pyrcc input.c -o generated.c --header-out generated.h --runtime-dir out

The generated C API exposes:

• <name>_init_state(State*) — initialize state
• <name>_forward(State*, RCCHistory*) — forward execution with history recording
• <name>_reverse(State*, RCCHistory*) — reverse execution restoring original state

Dump IR:

pyrcc input.c --dump-ir --dump-forward-ir --dump-reverse-ir

Analysis and verification:

pyrcc input.c --report
pyrcc input.c --verify --trials 20 --seed 0
pyrcc input.c --verify-codegen --trials 20 --seed 0
pyrcc input.c --compile-run --init x=3,y=1
pyrcc input.c --trace --init x=3,y=1

Dead history analysis and entropy:

pyrcc input.c --analyze-history
pyrcc input.c --entropy-report --trials 100
pyrcc input.c --optimize-history

Paper-core normalization:

python -m rcc.paper_normalize input.c -o normalized.c

Testing

make test

400 tests covering parsing, transformation, reversibility, generated C compilation, CLI behavior, dead history elimination, entropy analysis, and randomized differential checks between the Python semantics and generated C.

License

See LICENSE file.