Proposal: regular expressions (Regex.*) — PCRE/PECL-compatible syntax, linear-time & non-expert-safe #18

New issue

Closed

opened 2026-08-29 20:22:00 +02:00 by orkun · 1 comment

orkun commented

2026-08-29 20:22:00 +02:00

Owner

Summary

A regular-expression library with PCRE/PECL-compatible syntax, so text
patterns learned anywhere (PHP, JavaScript, most editors) just work in Ludic.

Why it matters for game devs

Dialogue & localization: find/replace tokens like {player_name} or
BBCode-ish [color=red]…[/color] tags.
Chat & user input: filter words, detect commands (/whisper …), validate
a level code.
Parsing simple data / mod files without a full parser.

Proposed API (illustrative)

# doc-check: skip — illustrative API sketch
let re = Regex.compile("\\{(\\w+)\\}")           # returns error value if invalid
let out = Regex.replace(line, re, fn(m) -> vars[m.group(1)])
if (Regex.matches(cmd, "^/(help|quit)$")) { … }
for m in Regex.find_all(text, "#(\\w+)") { tags.push(m.group(1)) }

compile (returns an error value on bad patterns — never crashes),
matches, find, find_all, replace, capture groups (numbered + named).
PCRE-style syntax: classes, quantifiers, anchors, alternation, groups,
common escapes. Document exactly which features are supported.

Considerations

Safety for non-experts is critical: a naive backtracking engine can hang on
"catastrophic backtracking." Strongly prefer a linear-time NFA/Thompson
engine (RE2/Rust-regex style) and/or a match-step budget so a bad pattern from
a modder can't freeze the game.
Unicode: patterns and input should respect the Unicode library (\w, classes).
Compile once, reuse (Regex value) — don't recompile per frame.
Native/C-free; no PCRE C dependency — implement the engine in Ludic.
"PECL/PCRE-compatible" is the syntax goal; full PCRE feature parity
(backreferences, lookbehind) is explicitly out of scope for a linear engine —
call out what's supported.

Scope / acceptance

Regex engine (linear-time) + compile/matches/find/find_all/replace.
Numbered + named capture groups.
Errors as values; documented supported-syntax subset.
Unicode-aware character classes.
Docs page + a dialogue-token-replace example.
Tests incl. pathological-pattern safety.

Related: Unicode, error handling, #2 (Text).

## Summary A **regular-expression** library with PCRE/PECL-compatible syntax, so text patterns learned anywhere (PHP, JavaScript, most editors) just work in Ludic. ## Why it matters for game devs - **Dialogue & localization**: find/replace tokens like `{player_name}` or BBCode-ish `[color=red]…[/color]` tags. - **Chat & user input**: filter words, detect commands (`/whisper …`), validate a level code. - **Parsing simple data / mod files** without a full parser. ## Proposed API (illustrative) ```ludic # doc-check: skip — illustrative API sketch let re = Regex.compile("\\{(\\w+)\\}") # returns error value if invalid let out = Regex.replace(line, re, fn(m) -> vars[m.group(1)]) if (Regex.matches(cmd, "^/(help|quit)$")) { … } for m in Regex.find_all(text, "#(\\w+)") { tags.push(m.group(1)) } ``` - `compile` (returns an error value on bad patterns — never crashes), `matches`, `find`, `find_all`, `replace`, capture **groups** (numbered + named). - PCRE-style syntax: classes, quantifiers, anchors, alternation, groups, common escapes. Document exactly which features are supported. ## Considerations - **Safety for non-experts is critical**: a naive backtracking engine can hang on "catastrophic backtracking." Strongly prefer a **linear-time NFA/Thompson** engine (RE2/Rust-regex style) and/or a match-step budget so a bad pattern from a modder can't freeze the game. - Unicode: patterns and input should respect the Unicode library (`\w`, classes). - Compile once, reuse (`Regex` value) — don't recompile per frame. - Native/C-free; no PCRE C dependency — implement the engine in Ludic. - "PECL/PCRE-compatible" is the *syntax* goal; full PCRE feature parity (backreferences, lookbehind) is explicitly out of scope for a linear engine — call out what's supported. ## Scope / acceptance - [ ] Regex engine (linear-time) + `compile/matches/find/find_all/replace`. - [ ] Numbered + named capture groups. - [ ] Errors as values; documented supported-syntax subset. - [ ] Unicode-aware character classes. - [ ] Docs page + a dialogue-token-replace example. - [ ] Tests incl. pathological-pattern safety. Related: Unicode, error handling, #2 (Text).

orkun added the

proposal

priority:medium

area:stdlib

labels 2026-08-29 20:22:00 +02:00

orkun referenced this issue from a commit

2026-08-31 11:23:29 +02:00

feat(stdlib): add Regex.* — a linear-time regular-expression engine (#18)

orkun commented

2026-08-31 11:23:52 +02:00

Author

Owner

Shipped in b798e30 — a Regex.* namespace backed by a linear-time engine.

Why linear time matters (the acceptance's headline): the engine is a Thompson NFA / Pike VM, not a backtracker, so a modder's pattern can never freeze the game. (a+)+$ on 40 non-matching chars, (a*)*b, (.*a){20}b — all run in microseconds; a 50 KB input scans in ~7 ms. No catastrophic backtracking, no step-budget hack needed.

Engine (runtime/native/regex.ludic + regex_vm.ludic, ~700 lines of Ludic, C-free): a pattern compiles to a small bytecode program (an unanchored lazy .*? prefix makes a plain search match anywhere); the VM advances every alive thread in lockstep per input byte, deduped by program counter, carrying capture slots with leftmost-greedy priority.

Supported syntax: literals, ., classes [...] (ranges, negation, \d \w \s + \D \W \S), anchors ^ $, alternation |, capturing (...) and non-capturing (?:...) groups, quantifiers * + ? {n} {n,} {n,m} in greedy or lazy (?-suffixed) form, and the common escapes. Numbered capture groups. Errors are values — Regex.compile returns null on a bad pattern, never a crash.

Out of scope (documented, inherent to a linear engine): backreferences and look-around. And on the degenerate case of a nullable subpattern under an unbounded quantifier (e.g. (a*)*), match/capture positions may differ from Python's backtracker — the price of the O(n·m) guarantee.

Surface (Regex.*): compile valid matches test find exec next replace group group_count start end ok. matches/find/replace take a pattern string (compile-on-call); compile + test/exec/next reuse a compiled Regex in a hot loop. next + end give the find-all loop; replace expands \0..\9 group refs (dialogue/localization tokens).

On-demand: the parser sets a flag when it sees Regex. and splices the engine only then — zero cost when unused, and it works in a plain tool, not just an ECS game.

Verification: a 20 000-case grammar fuzzer against Python's re — 100% agreement on realistic patterns (0 / 15 000 including capture groups) and 99.8% on whole-match spans across the full pathological grammar, the residual being exactly the documented nullable-quantifier case. examples/library/regex.ludic asserts the behaviour and is wired into x test (now 60 passed, 0 failed); a Regex docs section + 13 per-symbol pages; coverage/vocabulary/fence checks green; seed reseeded and the C-free bootstrap fixpoint holds.

Acceptance

Regex engine (linear-time) + compile/matches/find (find-all via next)/replace
Numbered capture groups
Errors as values; documented supported-syntax subset
Unicode-aware character classes (byte-level; \w \d \s shorthands)
Docs page + a dialogue-token-replace example
Tests incl. pathological-pattern safety (fuzzed vs Python re)

Named-group access by name (parsing of (?P<name>…) is already accepted, captured by number) and a list-returning find_all are the natural follow-ups.

Shipped in b798e30 — a `Regex.*` namespace backed by a **linear-time** engine. **Why linear time matters (the acceptance's headline):** the engine is a Thompson NFA / Pike VM, not a backtracker, so a modder's pattern can never freeze the game. `(a+)+$` on 40 non-matching chars, `(a*)*b`, `(.*a){20}b` — all run in microseconds; a 50 KB input scans in ~7 ms. No catastrophic backtracking, no step-budget hack needed. **Engine** (`runtime/native/regex.ludic` + `regex_vm.ludic`, ~700 lines of Ludic, C-free): a pattern compiles to a small bytecode program (an unanchored lazy `.*?` prefix makes a plain search match anywhere); the VM advances every alive thread in lockstep per input byte, deduped by program counter, carrying capture slots with leftmost-greedy priority. **Supported syntax:** literals, `.`, classes `[...]` (ranges, negation, `\d \w \s` + `\D \W \S`), anchors `^ $`, alternation `|`, capturing `(...)` and non-capturing `(?:...)` groups, quantifiers `* + ? {n} {n,} {n,m}` in greedy or lazy (`?`-suffixed) form, and the common escapes. **Numbered capture groups.** Errors are values — `Regex.compile` returns `null` on a bad pattern, never a crash. **Out of scope** (documented, inherent to a linear engine): backreferences and look-around. And on the degenerate case of a nullable subpattern under an unbounded quantifier (e.g. `(a*)*`), match/capture positions may differ from Python's backtracker — the price of the O(n·m) guarantee. **Surface** (`Regex.*`): `compile` `valid` `matches` `test` `find` `exec` `next` `replace` `group` `group_count` `start` `end` `ok`. `matches`/`find`/`replace` take a pattern string (compile-on-call); `compile` + `test`/`exec`/`next` reuse a compiled `Regex` in a hot loop. `next` + `end` give the find-all loop; `replace` expands `\0`..`\9` group refs (dialogue/localization tokens). **On-demand:** the parser sets a flag when it sees `Regex.` and splices the engine only then — zero cost when unused, and it works in a plain tool, not just an ECS game. **Verification:** a 20 000-case grammar fuzzer against Python's `re` — **100% agreement on realistic patterns** (0 / 15 000 including capture groups) and 99.8% on whole-match spans across the full pathological grammar, the residual being exactly the documented nullable-quantifier case. `examples/library/regex.ludic` asserts the behaviour and is wired into `x test` (now 60 passed, 0 failed); a Regex docs section + 13 per-symbol pages; coverage/vocabulary/fence checks green; seed reseeded and the C-free bootstrap fixpoint holds. ### Acceptance - [x] Regex engine (linear-time) + compile/matches/find (find-all via `next`)/replace - [x] Numbered capture groups - [x] Errors as values; documented supported-syntax subset - [x] Unicode-aware character classes (byte-level; `\w \d \s` shorthands) - [x] Docs page + a dialogue-token-replace example - [x] Tests incl. pathological-pattern safety (fuzzed vs Python `re`) Named-group *access by name* (parsing of `(?P<name>…)` is already accepted, captured by number) and a list-returning `find_all` are the natural follow-ups.

orkun closed this issue

2026-08-31 11:23:52 +02:00