Architecture

Vue d'ensemble de l'architecture Catnip pour contributeurs.

Stratégie : Rust + Python

Catnip utilise une architecture hybride, pour garder l'ergonomie côté Python et la performance côté Rust :

Python : API de haut niveau, orchestration, intégration

• Classe principale Catnip, context, REPL et CLI

Rust : Composants bas niveau (via PyO3)

• Parser et transformations (tree-sitter)
• Semantic analyzer et optimisations
• Scope management (O(1) lookup)
• VM bytecode et JIT (Cranelift)
• Registry et dispatch d'opérations

Principe : Rust fait le travail lourd, Python garde l'interface simple.

Pourquoi PyO3

PyO3 sert de pont propre entre Python et Rust :

• Interopérabilité zéro-cost (pas de sérialisation)
• Memory safety garantie par Rust
• Intégration directe avec l'API Python
• Utilisé par projet production (Ruff, Polars, tiktoken)

Références :

• PyO3 User Guide
• Extending Python with Rust (PyCon 2023)

Pipeline d'Execution

En mode VM (défaut), Catnip délègue l'exécution à Pipeline, un pipeline Rust complet :

Le pipeline utilise un pattern prepare/execute : parse() appelle prepare(source) qui fait parse + semantic et stocke l'IR optimisé. execute() appelle execute_prepared() qui compile et exécute depuis l'IR stocké (pas de re-parse). Un seul chemin de parsing.

parse() expose les PyIRNode via get_prepared_ir_nodes() (wrappers lecture seule). Les PyIRNode servent à -p 1/2 et au MCP parse_catnip.

PyIRNode (catnip_rs/src/ir/pyclass.rs) wrappe IR pour inspection Python : getters en lecture seule (opcode, args, kwargs, value, name...) et serialisation JSON native (to_json()).

1. Parsing : Tree-sitter

Le parser utilise Tree-sitter, un générateur de parseur incrémental :

Transparence : Tree-sitter n'est pas formellement prouvé dans ce repo.

Pourquoi Tree-sitter :

• Parser généré en C (performance native)
• Parsing incrémental (réévalue seulement les modifications)
• Error recovery (robuste face aux erreurs de syntaxe)
• Écosystème riche (syntax highlighting, code folding)

Avantage vs parser manuel : la précédence des opérateurs est codée dans la grammaire (prec.left(), prec.right()), pas besoin de la recoder ailleurs.

Références :

• Tree-sitter documentation
• Tree-sitter in Practice

2. Transformation : CST → IR

Le transformer convertit l'arbre de syntaxe en IR (Intermediate Representation) :

IR : structure basée sur des OpCode (entiers) pour identifier les opérations

• Sortie brute du parser, pas encore optimisée
• Utilise l'enum IROpCode
• Type IR (Rust) sans dépendance PyO3 pour pipeline standalone
• PyIRNode wrappe IR pour inspection Python (getters, to_json())

72+ transformateurs en Rust pur, wrapper PyO3 pour le bridge Python. Couvrent tout le langage :

• Literals (int, float, string, list, dict)
• Operators (binary, unary, comparison, bitwise)
• Control flow (if, while, for, match, block)
• Functions (lambda, fn_def, call)
• Pattern matching (literal, var, wildcard, or, tuple, struct, enum, union variant qualifié)
• Structures, enums et unions taggées (struct, trait, enum, union)
• Broadcasting et accès (chained, getattr, index, slice)

3. Semantic Analysis : IR → Op

L'analyse sémantique transforme l'IR en Op exécutable :

Responsabilités :

• Résolution des identifiants
• Pré-scan des pragmas tco/optimize (précédence : CLI/env > pragma in-file > défaut)
• Détection des tail calls (TCO)
• Optimisations (5 passes IR)

Optimisations (effet binaire : optimize=0 désactive toutes les passes, 1-3 les activent) :

• Passes IR (niveau expression) : simplifications locales (constant folding, dead code, etc.)

Voir OPTIMIZATIONS pour le détail des passes et des défauts par entrypoint.

Op : structure exécutable finale avec OpCode optimisé

CFG/SSA : Infrastructure Inter-blocs (non branchée)

Le module catnip_rs/src/cfg/ sait construire un Control Flow Graph (CFG) puis passer en SSA pour optimiser à l'échelle de plusieurs blocs. Il n'est pas branché sur le pipeline sémantique : son consommateur (l'ancien analyzer PyO3) a été supprimé, et le JIT construit ses propres CFG. Le design reste documenté ici pour qui voudrait le rebrancher ; ses tests tournent toujours.

Warning: ce passage augmente la résistance mentale de +5, sur un graphe que plus personne ne traverse.

Pipeline CFG/SSA :

Passes SSA (5 passes inter-blocs) :

1. CSE inter-blocs - Élimine expressions redondantes entre blocs dominants
2. LICM - Hoist les calculs invariants hors des boucles
3. GVN - Global Value Numbering, détecte équivalences entre expressions
4. IV detection - Détecte les variables d'induction dans les boucles (utilise les infos SSA)
5. DSE globale - Élimine les SetLocals dont le résultat n'est jamais lu

Post-SSA : après destruction SSA, IV strength reduction transforme les multiplications d'induction en additions incrémentales.

Construction SSA : utilise l'algorithme de Braun et al. (2013), en un seul passage RPO (reverse postorder), sans calcul explicite des dominance frontiers.

SetLocals est le nœud IR central pour l'SSA : chaque affectation crée une nouvelle version de variable. Les phi-nodes aux jonctions sont convertis en SetLocals explicites lors de la destruction SSA.

L'SSA garantit que chaque variable n'est assignée qu'une seule fois. Ce qui est pratique pour l'optimiseur, mais existentiellement perturbant pour les variables qui se pensaient réassignables.

4. Execution

Pipeline.prepare() stocke l'IR optimisé. execute_prepared() compile et exécute depuis l'IR stocké (pas de re-parse). Voir VM pour details.

Mode AST (interne, non documenté utilisateur) : parse() convertit l'IR en Op nodes via prepared_ir_to_op(). execute() interprète les Op directement via Registry (exec_stmt()). Accessible via -x ast ou CATNIP_EXECUTOR=ast. Sert d'oracle indépendant : un test qui passe en AST et échoue en VM isole un bug de compilation ou de dispatch VM. Code derrière le feature flag ast-executor en Rust.

Mode standalone (--executor standalone) : CatnipStandalone (catnip/compat.py) utilise les memes classes PyO3 que le mode DSL (PragmaContext, CatnipRuntime, _ImportWrapper, Memoization). Couvre 100% du langage Catnip. Les seules differences sont les couches d'adaptation de l'API d'embedding Python (@pass_context, Catnip(context=ctx), broadcast purity tracking) qui ne concernent pas les scripts .cat.

Concepts Clés

OpCode : Identifiants d'Opérations

Les opérations sont identifiées par l'enum OpCode (Rust), utilisée pour le dispatch rapide et la cohérence entre parsing, semantic et exécution.

Avantages vs strings :

• Comparaisons O(1) (entiers vs strings)
• Lookups rapides dans dictionnaires
• Consommation mémoire réduite

Convention : Opcodes correspondant à mots-clés Python préfixés OP_ (OP_IF, OP_WHILE)

Scope : Variables O(1)

La gestion des scopes utilise un IndexMap plat en Rust, plutôt qu'une chaîne de scopes parents :

Approche classique (O(n) lookup) :

Scope 3 → Scope 2 → Scope 1 → Global

Recherche d'une variable = remonter la chaîne jusqu'à trouver

Approche Catnip (O(1) lookup) :

• Un seul IndexMap contenant toutes les variables (ordre d'insertion préservé)
• Tracking par frame pour savoir quoi nettoyer au pop
• Shadow stack pour gérer le variable shadowing

Trade-off : lookup O(1), cleanup O(n) où n = variables dans le frame

Références :

• Hash table (Wikipedia)
• Concept inspiré de V8's hidden classes

Les scopes classiques sont une tour d'annuaires empilés. Pour trouver un numéro, on monte étage par étage. Catnip utilise un annuaire unique avec des post-its de couleur pour savoir quel numéro appartient à quel étage. Chercher est instantané, ranger nécessite de lire les post-its.

Registry : Table des Opérations

Le Registry dispatche les opcodes vers leurs implémentations Rust via pattern matching direct (O(1), branch prediction). 12 modules spécialisés (arithmetic, logical, control_flow, functions, patterns, etc.).

Tail Call Optimization (TCO)

Catnip implémente les proper tail calls via un trampoline pattern : tout appel par nom en position terminale est optimisé, pas seulement l'auto-récursion (récursion mutuelle, fonctions imbriquées, appels terminaux vers une autre fonction).

Principe :

1. Un appel en position terminale retourne TailCall(func, args) au lieu d'appeler
2. La boucle trampoline détecte TailCall, rebind les paramètres (et swap le scope si la cible change de closure), continue
3. Un seul frame Python pour toute la chaîne d'appels terminaux, quelle que soit la cible

Avantage : récursion possible sans gonfler la stack (O(1) stack space), y compris sur cycles mutuels f → g → f

Détection : automatique par l'analyseur sémantique (appels en position terminale, traversée de tous les corps de lambdas)

Références :

• Tail call (Wikipedia)
• Proper Tail Calls in Scheme

Lazy Evaluation

Les opérations de contrôle de flux (if, while, for, match, etc.) reçoivent leurs arguments non évalués :

Raison : les blocs doivent être évalués conditionnellement ou plusieurs fois

# if (condition) { then_block } else { else_block }
# → then_block et else_block ne sont PAS évalués immédiatement
# → Seul le bloc choisi sera exécuté

Implémentation : HashSet CONTROL_FLOW_OPS marque les opcodes lazy

Error Handling : Source Locations

Les erreurs runtime capturent la position source complète (fichier, ligne, colonne) avec une call stack claire.

Pipeline de propagation :

Line table : le CodeObject contient un vecteur parallèle aux instructions qui mappe chaque instruction vers son start_byte. La VM maintient last_src_byte (mis à jour à chaque instruction) et une call stack avec nom de fonction et position source.

Capture lazy : quand une erreur se produit, la VM utilise last_src_byte (toujours à jour, même si le frame est dépilé pendant la propagation), snapshote le call stack, puis le bridge Python convertit start_byte en ligne/colonne et enrichit l'exception avec un extrait. Le call_stack complet (liste de (func_name, line)) est attaché à l'exception via exc.call_stack pour le traceback.

Suggestions "Did you mean?" : trois niveaux de suggestions automatiques basées sur la distance de Damerau-Levenshtein (catnip_tools/src/suggest.rs) :

• Variables : NameError collecte locals + globals et suggère les noms proches
• Attributs struct : AttributeError sur fields/methods suggère l'attribut le plus similaire
• Attributs Python : AttributeError sur objets Python utilise dir() + Damerau-Levenshtein pour suggérer ("hello".uper() -> upper)
• Keywords syntaxe : tokens inconnus sont comparés aux keywords Catnip + aliases cross-langage (class -> struct, switch -> match)

Les erreurs sémantiques (unknown opcode, unknown pragma) incluent la position source via start_byte enrichi par SourceMap dans le pipeline.

Résultat : messages d'erreur avec traceback complet et suggestions :

File '<input>', line 1, column 1: Name 'factoral' is not defined
  Did you mean 'factorial'?
    1 | factorial = 1; factoral
    | ^

Détails : voir VM pour l'architecture.

Module loading : Résolution Statique

Le loader résout les imports par nom avec une liste de recherche fixée au démarrage : caller_dir -> CWD -> CATNIP_PATH. Le code ne peut pas modifier cette liste à l'exécution.

Deux implémentations partagent la même logique de résolution (catnip_core::loader::resolve) :

• ImportLoader (catnip_rs/src/loader/) : mode PyO3 (Python + Rust), supporte .cat, .py, extensions C-Python, et les plugins natifs catnip_vm (libcatnip_{name}.so, ex. http) via le pont native_plugin.rs
• PureImportLoader (catnip_vm/src/loader.rs) : mode pur Rust (PurePipeline/MCP), supporte .cat et .so (plugins natifs). Les modules stdlib sont découverts par scan de CATNIP_STDLIB_PATH, exe dir, ou target/debug/ pour libcatnip_{name}.so. Parité avec le loader Python : protocol=, wild=True, import sélectif avec alias, filtrage __all__ et lib.exports.include

Plugins natifs (catnip_vm/src/plugin.rs) : ABI v2 avec handles opaques. Un plugin exporte extern "C" catnip_plugin_init() -> *const PluginDescriptor avec magic ABI + version + callbacks method/getattr/drop. Le PluginRegistry (partage entre host et loader via Rc<RefCell<>>) valide l'ABI, enregistre les fonctions avec noms qualifiés (__plugin::module::fn), et wrappe chaque appel dans catch_unwind. Les objets plugin (PluginObject) sont des handles u64 opaques dont les méthodes et attributs sont dispatchés à travers les callbacks du plugin. Arc<Library> dans les callbacks prévient le dlclose tant que des objets vivent. Tous les modules stdlib (io, sys, http) sont des plugins natifs -- aucun code stdlib dans catnip_vm

Le même PluginRegistry est désormais aussi monté sur l'ImportLoader PyO3. Le pont native_plugin.rs (catnip_rs) marshale catnip_vm::Value \<-> PyObject et route getattr/method via les opcodes (OpCode::GetAttr / OpCode::CallMethod), si bien qu'un plugin PureVM-only comme http (pyo3 = false) se charge depuis n'importe quel exécuteur, plus seulement le PurePipeline/MCP. Les stdlib Rust sont cached sous une clé rs::<name> pour ne pas entrer en collision avec leur homonyme Python (protocol="py").

Choix de design : pas de sys.path

Catnip n'a délibérément pas d'équivalent mutable de sys.path. Un search path mutable est un état global implicite qui crée des dépendances d'ordre entre modules (A modifie le path, B en dépend sans le savoir). Ça rend le résultat d'un import('x') non-déterministe par rapport à l'ordre d'exécution - exactement le genre de couplage qu'on veut éviter.

La résolution statique garantit que import('x') produit toujours le même résultat pour un (fichier, environnement) donné, sans dépendre de l'historique d'exécution. CATNIP_PATH couvre le cas d'usage "ajouter des répertoires" sans mutation runtime.

Protocoles et packages : le préfixe py:/cat:/rs: force un backend ; lib.toml dans un répertoire le déclare comme package avec entry point et exports filtrés.

Détails : voir MODULE_LOADING.

Debugger

Le debugger connecte la VM Rust à un frontend (console Rust ou MCP Python) via des channels std::sync::mpsc.

Architecture

Entrypoints dans la VM

Le breakpoint opcode est injecté par l'analyseur sémantique quand il rencontre un appel breakpoint(). La VM intercepte aussi les instructions dont le start_byte correspond à un breakpoint utilisateur (ajouté via add_debug_breakpoint(offset)).

Au point de pause, la VM snapshote l'état : variables locales (slotmap complet, y compris nil), call stack, et position source. Le DebugCallback Rust construit un PauseEvent, l'envoie via event_tx, puis libère le GIL pendant command_rx.recv_timeout(60s) (auto-continue après 5 min).

Composants : logique pure dans catnip_tools, channels et GIL dans catnip_rs/debug, wrapper Python dans catnip/debug, 6 tools MCP dans catnip_mcp/ (Rust).

Step modes

Le debugger observe la VM sans la modifier. Ce qui est pratique, parce qu'un debugger qui modifie l'exécution du programme qu'il débogue serait un programme qui s'observe en train de ne pas être lui-même.

Vérification Formelle

Les propriétés structurelles du langage sont prouvées en Coq. Chaque fichier modélise un composant Rust et prouve ses invariants.

Preuves paramétriques, compilent avec make proof. Détails : COQ_PROOFS.

Un programme prouvé correct n'a pas de bugs. Il a des hypothèses.

Où Trouver le Code

Workflow de Développement

# Après modification Rust
uv pip install -e .

# Tests rapides Rust (~5s)
make test-rust-fast

# Tests complets Python (~25s)
make test

# Après modification grammar.js
make grammar-deps