2556698dd3
Principe RS-7 : « dès qu'on build un truc, plus personne n'a à le rebuild —
la seule chose à faire est l'optimisation. » (nexus/RepoVerse)
- bion-vc : horloges vectorielles + MvReg fork-visible (LA spec
xion-relativiste-v0 enfin codée — CRDT testé par permutations)
- bion-triplet : l'Adressage Génératif (gen_hash BLAKE3, coords, résidu ;
résidu vide quand déjà-su ; align décidable au bit)
- bion-tsoinlog: journal append-only rejouable (CRC32 maison, crash-recovery)
- bion-kv : magasin clé-valeur bitcask (compaction atomique, tombstones)
- bion-regex : moteur Thompson NFA linéaire (jamais exponentiel — Russ Cox)
- bion-git : mini-git content-addressed (SHA-1 maison + vecteurs officiels,
branches divergentes = le fork visible)
129 tests verts, clippy 0 warning, doc française = chaque bion est un cours.
Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>
127 lines
5.8 KiB
Markdown
127 lines
5.8 KiB
Markdown
# bion-regex 🔤
|
||
|
||
Moteur d'expressions régulières **from scratch, std-only, zéro dépendance,
|
||
zéro unsafe** — LE classique *build-your-own-regex*, version **NFA de
|
||
Thompson** simulé par ensembles d'états. La brique regex du xerboxion :
|
||
construite une fois, plus jamais rebâtie, seulement optimisée (principe RS-7).
|
||
|
||
Référence fondatrice : Russ Cox, **« Regular Expression Matching Can Be
|
||
Simple And Fast »** — <https://swtch.com/~rsc/regexp/regexp1.html>. À lire
|
||
avec le code sous les yeux : ce crate en est une implémentation Rust fidèle
|
||
et commentée. Voir aussi la section *build-your-own-x* correspondante :
|
||
<https://github.com/codecrafters-io/build-your-own-x#build-your-own-regex-engine>.
|
||
|
||
## Quoi
|
||
|
||
Pipeline en trois étapes, un fichier par étape :
|
||
|
||
```
|
||
motif ──parse──▶ AST ──compile──▶ NFA ──simulation──▶ oui/non + position
|
||
src/parser.rs src/nfa.rs src/nfa.rs (ensembles d'états)
|
||
```
|
||
|
||
- `Regex::new(pattern) -> Result<Regex, Error>` — compile une fois pour toutes
|
||
- `is_match(text) -> bool` — le motif apparaît-il quelque part ?
|
||
- `find(text) -> Option<(usize, usize)>` — première occurrence,
|
||
*leftmost-longest*, offsets en **octets** (`&text[start..end]` = le match)
|
||
- Erreurs de syntaxe **localisées** (position en caractères) et en français
|
||
|
||
Langage supporté : littéraux Unicode · `.` (tout sauf `\n`) · `*` `+` `?` ·
|
||
`|` · groupes `(…)` (priorité seulement, pas de capture — choix assumé pour
|
||
garder l'API minuscule) · classes `[a-z]`, `[^…]`, `]`/`-` littéraux aux
|
||
positions classiques · `\d \D \w \W \s \S` · `\n \t \r` · métacaractères
|
||
échappés (`\.` `\(` …) · ancres `^` `$`.
|
||
|
||
## Pourquoi Thompson (et pas du backtracking)
|
||
|
||
C'est **le** point pédagogique du crate. Un moteur à backtracking (Perl,
|
||
PCRE, `re` de Python…) essaie les alternatives une par une et revient en
|
||
arrière : sur `a*a*a*…a*b` face à `aaaa…a` (sans `b`), il doit explorer
|
||
~2ⁿ découpages avant d'avouer l'échec — 30 `a` suffisent à le figer des
|
||
secondes, 40 des heures. C'est la racine des CVE « ReDoS ».
|
||
|
||
L'approche Thompson (1968), ressuscitée par l'article de Russ Cox :
|
||
|
||
1. **Compilation** : chaque nœud de l'AST devient un fragment de NFA d'au
|
||
plus UN état (`Char`, `Split`, assertions). Le NFA fait O(m) états pour
|
||
un motif de m caractères — jamais plus.
|
||
2. **Simulation par ensembles d'états** : on lit le texte UNE fois ; à chaque
|
||
caractère on maintient *l'ensemble de tous les états où le NFA pourrait
|
||
être* (≤ n états, dédupliqués). C'est la déterminisation « à la volée »,
|
||
sans matérialiser le DFA.
|
||
|
||
Résultat : **O(texte × motif) garanti, pour tout motif, tout texte**. Le
|
||
motif pathologique ci-dessus répond en microsecondes — c'est testé,
|
||
chronomètre à l'appui (`pathologique_a_star_reste_instantane`).
|
||
|
||
Les ancres `^`/`$` sont des états-assertions évalués pendant la fermeture
|
||
epsilon (elles ne consomment rien), donc elles marchent aussi au milieu
|
||
d'une alternance (`^début|fin$`).
|
||
|
||
## Exemple
|
||
|
||
```rust
|
||
use bion_regex::Regex;
|
||
|
||
let re = Regex::new(r"^\w+@\w+\.[a-z]+$").unwrap();
|
||
assert!(re.is_match("rs7@xerion.ch"));
|
||
|
||
let re = Regex::new(r"\d+").unwrap();
|
||
let texte = "il y a 285 bions";
|
||
let (s, e) = re.find(texte).unwrap();
|
||
assert_eq!(&texte[s..e], "285");
|
||
|
||
// Le piège qui tue un backtracker — instantané ici :
|
||
let patho = Regex::new(&format!("{}b", "a*".repeat(30))).unwrap();
|
||
assert!(!patho.is_match(&"a".repeat(30)));
|
||
```
|
||
|
||
## Le bug classique (vécu, puis testé)
|
||
|
||
Première version : la fermeture epsilon marquait les états `Split` comme
|
||
« vus » mais ne les démarquait pas entre deux caractères → les boucles
|
||
(`a+`, `(ab)*`) n'étaient traversables qu'**une seule fois** (`ab+c`
|
||
matchait `abc` mais pas `abbc`). Le fix : l'ensemble d'états garde la liste
|
||
de TOUS les états marqués (pas seulement les stables) pour tout démarquer au
|
||
`clear`. Si tu réimplémentes ce moteur, tu feras ce bug — le test
|
||
`plus_exige_au_moins_un` t'attend.
|
||
|
||
## Complément, pas doublon
|
||
|
||
Le core (`~/xerboxion-rt`) n'a aucun moteur de motifs ; les ploxions font du
|
||
`match exact only` (cf. tsoin engine / `config/ploxions.php`). `bion-regex`
|
||
est la brique qui manque : filtrage de tsoins, routes, validation d'entrées —
|
||
embarquable partout (std-only, compile en WASM sans rien changer).
|
||
|
||
## Comment l'optimiser (l'invitation au fork)
|
||
|
||
Le moteur est volontairement la version *simple et juste*. Pistes, par ordre
|
||
de rendement (toutes dans les articles suivants de Russ Cox,
|
||
[regexp2](https://swtch.com/~rsc/regexp/regexp2.html) et
|
||
[regexp3](https://swtch.com/~rsc/regexp/regexp3.html)) :
|
||
|
||
1. **`find` en un seul passage** — aujourd'hui `find` relance une simulation
|
||
ancrée par position de départ (O(n²·m) au pire). La VM de Pike attache la
|
||
position de départ à chaque « thread » : leftmost-longest en O(n·m).
|
||
2. **Captures** — même VM de Pike : chaque thread porte ses positions de
|
||
sous-groupes. C'est l'étape qui transforme `(…)` en vraies captures.
|
||
3. **Cache DFA à la RE2** — mémoïser les ensembles d'états rencontrés :
|
||
chaque caractère devient UN lookup de table (c'est ce que fait `grep`).
|
||
4. **Octets plutôt que chars** — compiler les classes Unicode en automate
|
||
sur les octets UTF-8 : plus de décodage à l'exécution.
|
||
5. **Littéraux préfixes** — `memchr` sur le premier octet obligatoire avant
|
||
de lancer le NFA (l'optimisation qui rend `ripgrep` rapide).
|
||
|
||
L'API (`new` / `is_match` / `find` / `pattern`) ne bouge pas : optimiser =
|
||
remplacer l'intérieur, jamais casser l'extérieur.
|
||
|
||
## Tests
|
||
|
||
```
|
||
cargo test -p bion-regex # 34 tests : 12 unitaires + 20 intégration + 2 doc
|
||
```
|
||
|
||
Couvre : les pièges pathologiques (chronométrés), boucles vides imbriquées
|
||
`((a*)*)*`, classes négatives, `]`/`-` littéraux, ancres en alternance,
|
||
matchs vides, offsets Unicode, et huit erreurs de syntaxe localisées.
|