Architecture

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

Stratégie : Rust + Python

Catnip utilise une architecture hybride :

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

• Classe principale Catnip (catnip/__init__.py)
• Context et gestion de l'environnement
• Interface 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 : Les composants bas niveau sont en Rust, l'ergonomie reste en Python.

Pourquoi PyO3

PyO3 permet d'écrire des extensions Python en Rust :

• Interopérabilité zero-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 de Compilation

Catnip transforme le code source en résultats exécutables via un pipeline à 4 étapes :

1. Parsing        → Parse tree (CST)
2. Transformation → IR (Intermediate Representation)
3. Semantic       → Op (Optimized AST)
4. Execution      → Result

1. Parsing : Tree-sitter

Le parser utilise Tree-sitter, un parser generator incrémental :

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)

Grammaire : catnip_rs/grammar/grammar.js définit la syntaxe complète

Avantage vs parser manuel : Tree-sitter encode la précédence des opérateurs dans la grammaire (prec.left(), prec.right()), pas besoin de la réimplémenter dans le transformer.

Références :

• Tree-sitter documentation
• Tree-sitter in Practice

2. Transformation : CST → IR

Le transformer (catnip_rs/src/parser/) convertit le parse tree en IR (Intermediate Representation) :

IR : Structure à base d'OpCode (entiers) pour identifier les opérations

• Sortie brute du parser, pas encore optimisée
• Utilise l'enum IROpCode (56 opcodes)
• Type IRPure (Rust) sans dépendance PyO3 pour pipeline standalone

Architecture unifiée :

• pure_transforms.rs : Source unique de vérité (72+ transformateurs en Rust pur)
• transforms.rs : Wrapper PyO3 ultra-léger qui délègue et convertit
• to_python.rs : Convertisseur IRPure → objets Python (IR, Ref, Pattern*)
• utils.rs : Helpers partagés (node_text, named_children, unescape_string, extract_operator)

Transformateurs couvrent tous les aspects du 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)
• Broadcasting et accès (chained, getattr, index, slice)

3. Semantic Analysis : IR → Op

L'analyse sémantique (catnip_rs/src/semantic/) transforme l'IR en Op exécutable :

Responsabilités :

• Résolution des identifiants
• Détection des tail calls (TCO)
• Application des pragmas
• Optimisations (6 passes)

Optimizations (optionnel, contrôlé par niveau 0-3) :

1. Constant folding - Évalue expressions constantes
2. Strength reduction - Remplace opérations coûteuses
3. Block flattening - Simplifie blocs imbriqués
4. Dead code elimination - Supprime code inaccessible
5. Common subexpression elimination - Réutilise calculs
6. Blunt code simplification - Simplifie patterns maladroits

Voir OPTIMIZATIONS.md pour détails sur les niveaux.

Op : Structure exécutable finale avec OpCode optimisé (56 opcodes)

4. Execution : Deux modes

Catnip supporte deux modes d'exécution :

VM Bytecode (défaut) :

• Compile Op → bytecode → VM stack-based
• NaN-boxing pour représentation compacte
• JIT Cranelift pour hot loops/functions
• Voir VM.md pour détails

AST Interpretation (fallback) :

• Interprète Op directement via Registry
• Dispatch O(1) en Rust
• Utilisé pour debug et tests

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 parse/semantic/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 HashMap flat en Rust au lieu d'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 HashMap contenant toutes les variables
• Tracking par frame pour savoir quoi nettoyer au pop
• Shadow stack pour gérer le masquage de variables

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 (catnip_rs/src/core/registry/) est le moteur d'exécution :

Responsabilités :

• Dispatcher les opcodes vers leurs implémentations
• Gérer la stack d'évaluation
• Exécuter les opérations (arithmetic, logical, control flow, etc.)

Dispatch : Direct pattern matching Rust (O(1))

• Compare l'opcode
• Appelle la fonction Rust appropriée
• Optimisé par le compilateur Rust (branch prediction)

Modules Registry : 12 fichiers spécialisés dans core/registry/ (arithmetic.rs, logical.rs, control_flow.rs, functions.rs, patterns.rs, etc.)

Tail Call Optimization (TCO)

Catnip utilise un trampoline pattern pour éliminer la croissance de stack :

Principe :

1. Fonction tail-recursive retourne TailCall(func, args) au lieu d'appeler
2. Trampoline loop détecte TailCall, rebind paramètres, continue
3. Un seul frame Python pour toute la récursion

Avantage : Récursion infinie possible (O(1) stack space)

Détection : Automatique par l'analyseur sémantique (appels en dernière position)

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

Où Trouver le Code

catnip/
├── __init__.py          # Classe Catnip, API principale
├── context.py           # Contexte d'exécution
├── nodes.py             # Nœuds AST (Ref, patterns, signaux)
├── semantic/            # Wrappers Python semantic Rust
├── transformer/         # Wrappers Python transformer Rust
└── vm/                  # Bridge Python VM Rust

catnip_rs/
├── grammar/grammar.js   # Grammaire Tree-sitter
└── src/
    ├── core/            # Scope, Op, Registry (Rust)
    ├── ir/              # IROpCode, IRPure, to_python (conversion)
    ├── parser/          # Transformateurs unifiés (pure_transforms.rs + wrapper PyO3)
    ├── semantic/        # Analyzer + 6 passes optimisation
    ├── vm/              # VM bytecode (compiler, frame, value)
    ├── jit/             # JIT Cranelift
    └── pragma/          # Directives compilation

Workflow de Développement

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

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

# Tests complets Python (~25s)
make test

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