La lib regex — Motor d'Expressions Regulars Thompson NFA en Temps Lineal $O(N \cdot M)$

19.1. Per què existeix la lib regex? (El problema real i la filosofia Ridgun)

«Per què necessito una lib regex escrita des de zero en Ridgun pur en lloc d'enllaçar una llibreria de C de tota la vida?»

Aquesta és la primera pregunta que es fa qualsevol enginyer de sistemes en arribar a regex. I la resposta resumeix tota la filosofia de ridgun-libs:

Siguem sincers: els motors d'expressions regulars amb backtracking han causat caigudes globals famoses (com a Cloudflare o StackOverflow) quan un patró com (a+)+b rep trenta a seguides i entra en temps exponencial $O(2^N)$.

La lib regex compila les teves expressions regulars (., *, +, ?, |, (), [a-z], [^...], ^, $, \d, \w, \s) a un autòmat finit no determinista de Thompson (NFA) i avança el conjunt d'estats pas a pas en temps estrictament lineal $O(N \cdot M)$, fent que els atacs ReDoS siguin matemàticament impossibles.

En un ecosistema tradicional, resoldre les tasques del domini REGEX implica arrossegar dependències externes en C, lluitar amb punters crus, conversions opaques de tipus, excepcions no verificades o pauses impredictibles del recol·lector de brossa. En Ridgun, la lib regex (src/main/ridgun/lib/regex.rg) aborda el problema amb quatre principis innegociables:

1. Declara import regex (o import regex as alias) a l'inici del fitxer: cada lib defineix el seu espai de noms module :: regex i en mode --strict les funcions multi-paraula s'invoquen sempre amb espais naturals.
2. Encadena les teves canonades d'esquerra a dreta amb ->: escriu entrada pas u -> pas dos -> resultat, fes servir màscares (+ _ _ +) per desestructurar seqüències i omet _ = en sentències seqüencials (o descarta amb -> ()).
3. Recursió de cua amb TCO (Tail-Call Optimization): tots els recorreguts interns de regex es compilen a bucles natius en espai de pila $O(1)$.
4. Memòria determinista (RMM1 / RMM2): cada estructura intermèdia s'allibera en l'instant exacte en què acaba la seva última lectura, sense Garbage Collector.

---

19.2. Artefactes natius, importació i catàleg complet de l'API de regex

A ridgun-libs, regex és una lib de primera classe situada a src/main/ridgun/lib/regex.rg (domini REGEX). En compilar amb stable bundle, s'empaqueta en tres formats natius:

Artefacte	Ruta	Propòsit
Bundle Ridgun	target/bundles/regex.rglib	Distribució i importació directa amb import regex
Fitxer compilat	target/regex.rgc	Artefacte intermedi verificat per ridgunc
Objecte compartit ELF64	target/libregex.so	Biblioteca dinàmica nativa sense dependències de C ni libc

Cada lib declara el seu propi espai de noms amb module :: regex: n'hi ha prou d'escriure import regex (o import regex as alias) a la capçalera i cridar les seves funcions amb espais naturals (la meva funcio x) i canonades -> (x la meva funcio -> resultat).

19.2.1. Resum de famílies funcionals de regex

Signatura / Funció / Tipus	Què fa i quan fer-la servir
regex match / regex is match	Coincidència de cadena completa i cerca de subcadena en temps lineal $O(N \cdot M)$
regex find / regex find all	Extreu la primera o totes les subcadenes coincidents sense solapament
regex replace / regex replace all	Reemplaça la primera o totes les coincidències de l'expressió regular
regex split / regex escape	Divideix text segons un delimitador regex i escapa metacaràcters

19.2.2. Catàleg exhaustiu de tipus i signatures a src/main/ridgun/lib/regex.rg

A continuació tens l'inventari complet de tipus algebraics (type), operadors (op ::) i signatures de funcions (fn ::) definits a src/main/ridgun/lib/regex.rg (4 tipus, 0 operadors i 70 funcions):

Tipus algebraics i registres (type) de regex:

type RegexMatch = matched: Bool, match_start: Int, match_end: Int, text: String
type ReNode = ReEmpty | ReChar Int | ReAny | ReClass Bool [Int] | ReShort Int | ReBol | ReEol | ReStar ReNode | RePlus ReNode | ReOpt ReNode | ReSeq ReNode ReNode | ReAlt ReNode ReNode
type ReParseRes = ReParseRes ReNode Int
type NfaInst = InstChar Int Int | InstAny Int | InstClass Bool [Int] Int | InstShort Int Int | InstBol Int | InstEol Int | InstSplit Int Int | InstJump Int | InstMatch

#	Funció / Signatura (fn ::)	Tipus de Retorn
1	fn :: re is digit Int	Bool
2	fn :: re is word Int	Bool
3	fn :: re is space Int	Bool
4	fn :: re match short Int Int	Bool
5	fn :: re in ranges Int [Int]	Bool
6	fn :: re escape char Int	ReNode
7	fn :: re class char String Int Int	(Int Int)
8	fn :: re fst int (Int Int)	Int
9	fn :: re snd int (Int Int)	Int
10	fn :: re parse class items String Int Int [Int]	([Int] Int)
11	fn :: re parse class item step String Int Int [Int]	([Int] Int)
12	fn :: re parse class range check String Int Int Int [Int]	([Int] Int)
13	fn :: re parse class range hi String Int Int Int [Int]	([Int] Int)
14	fn :: re fst ranges ([Int] Int)	[Int]
15	fn :: re snd pos ([Int] Int)	Int
16	fn :: re parse class String Int Int	ReParseRes
17	fn :: re finish class Bool ([Int] Int)	ReParseRes
18	fn :: re res node ReParseRes	ReNode
19	fn :: re res pos ReParseRes	Int
20	fn :: re parse group String Int Int	ReParseRes
21	fn :: re close group ReNode String Int Int	ReParseRes
22	fn :: re parse atom String Int Int	ReParseRes
23	fn :: re parse postfix ReNode String Int Int	ReParseRes
24	fn :: re parse factor String Int Int	ReParseRes
25	fn :: re is seq stop Int	Bool
26	fn :: re parse seq loop ReNode String Int Int	ReParseRes
27	fn :: re parse seq step ReNode String Int Int	ReParseRes
28	fn :: re parse seq String Int Int	ReParseRes
29	fn :: re parse seq first String Int Int	ReParseRes
30	fn :: re parse alt loop ReNode String Int Int	ReParseRes
31	fn :: re parse alt branch ReNode String Int Int	ReParseRes
32	fn :: re parse alt String Int Int	ReParseRes
33	fn :: nfa len [NfaInst]	Int
34	fn :: re compile seq ReNode ReNode Int	[NfaInst]
35	fn :: re compile opt ReNode Int	[NfaInst]
36	fn :: re compile star ReNode Int	[NfaInst]
37	fn :: re compile plus ReNode Int	[NfaInst]
38	fn :: re compile alt ReNode ReNode Int	[NfaInst]
39	fn :: re compile node ReNode Int	[NfaInst]
40	fn :: re compile String	[NfaInst]
41	fn :: nfa inst at [NfaInst] Int	NfaInst
42	fn :: nfa set has [Int] Int	Bool
43	fn :: nfa closure [NfaInst] [Int] Int Int [Int]	[Int]
44	fn :: nfa closure inst [NfaInst] Int [Int] Int Int [Int] NfaInst	[Int]
45	fn :: nfa step one NfaInst Int	[Int]
46	fn :: nfa step [NfaInst] [Int] Int	[Int]
47	fn :: nfa is match inst NfaInst	Bool
48	fn :: nfa has match [NfaInst] [Int]	Bool
49	fn :: nfa update last [NfaInst] [Int] Int Int	Int
50	fn :: nfa sim loop [NfaInst] String Int Int [Int] Int	Int
51	fn :: nfa sim step [NfaInst] String Int Int [Int] Int	Int
52	fn :: nfa longest from [NfaInst] String Int Int	Int
53	fn :: nfa full loop [NfaInst] String Int Int [Int]	Bool
54	fn :: nfa full step [NfaInst] String Int Int [Int]	Bool
55	fn :: regex match String String	Bool
56	fn :: nfa find from [NfaInst] String Int Int	RegexMatch
57	fn :: nfa find check [NfaInst] String Int Int Int	RegexMatch
58	fn :: regex find String String	RegexMatch
59	fn :: regex is match String String	Bool
60	fn :: nfa find all loop [NfaInst] String Int Int [RegexMatch]	[RegexMatch]
61	fn :: nfa find all step [NfaInst] String Int Int [RegexMatch] Int	[RegexMatch]
62	fn :: regex find all String String	[RegexMatch]
63	fn :: regex replace String String String	String
64	fn :: re apply replace RegexMatch String String	String
65	fn :: nfa replace all loop [NfaInst] String String Int Int String	String
66	fn :: nfa replace all step [NfaInst] String String Int Int String Int	String
67	fn :: regex replace all String String String	String
68	fn :: nfa split loop [NfaInst] String Int Int Int [String]	[String]
69	fn :: nfa split step [NfaInst] String Int Int Int [String] Int	[String]
70	fn :: regex split String String	[String]

---

19.3. Explorant regex a fons: Exemples pas a pas de cada funcionalitat

No n'hi ha prou de veure la taula de signatures: explorarem cadascuna de les funcionalitats de la lib regex mitjançant exemples progressius i executables en Ridgun. Començarem per les dues receptes tabulars d'ús quotidià i després recorrerem en detall tots els escenaris funcionals, transformacions i casos límit verificats a src/test/ridgun/test regex.rg.

19.3.1. Exemple 1: Flux principal en estil tabular amb regex

Observa com en Ridgun els signes = i els passos de transformació amb regex queden alineats com una taula neta, sense variables mutables innecessàries ni efectes laterals ocults:

import regex

fn :: extraer codigos postales String => [String]
      extraer codigos postales texto =
        regex find all "\d+" texto

19.3.2. Exemple 2: Composició segura i gestió de casos de vora

Tota funció de la lib regex està dissenyada per compondre's amb guardes booleanes | i amb la resta de les 32 libs de ridgun-libs:

import regex

fn :: censurar telefonos String => Bool String
      censurar telefonos comentario =
        regex is match "\d+-\d+" comentario -> tiene
        regex replace all "\d+-\d+" comentario "[TELEFONO]" -> limpio
        (tiene, limpio)

19.3.3. Exemple 3: Àncores (^, $), quantificadors (*, +, ?), alternança (|), grups (...), classes [a-z0-9] i dreceres (\d, \w, \s)

En aquest exemple pràctic explorem de manera exhaustiva com es comporta regex en aquest bloc funcional, incloent-hi entrades estàndard, combinacions de paràmetres i valors frontera:

fn :: test regex operators and classes => ()
      test regex operators and classes =
        assert true (regex match "" "") "AC1: empty pattern matches empty string"
        assert false (regex match "" "nonempty") "AC1: empty pattern rejects non-empty on full match"
        assert true (regex match 'a(b|c)+d?e*' "abcbdeee") "AC1: alternation group plus opt star"
        assert true (regex match 'a(b|c)+d?e*' "ac") "AC1: opt and star match zero occurrences"
        assert false (regex match 'a(b|c)+d?e*' "ade") "AC1: plus requires at least one"
        assert true (regex match '(foo|bar|baz)+' "barfoobazbar") "AC1: multi-branch alternation with plus"
        assert false (regex match '(foo|bar|baz)+' "barquxfoo") "AC1: multi-branch alternation rejects unknown"
        assert true (regex match '[a-zA-Z_][a-zA-Z0-9_]*' "_valid_Identifier_99") "AC1: identifier character class"
        assert false (regex match '[a-zA-Z_][a-zA-Z0-9_]*' "9invalid") "AC1: identifier rejects leading digit"
        assert true (regex match '[^0-9]+' "hello_world") "AC1: negated char class"
        assert false (regex match '[^0-9]+' "hello42") "AC1: negated char class rejects digits"
        assert true (regex match '\w+\s+\d+' "agent   007") "AC1: shorthand escapes \\w \\s \\d"
        assert true (regex match '\D+\S+' "abc_123") "AC1: negated shorthand escapes \\D \\S"
        assert true (regex match 'v\d+\.\d+\.\d+' "v0.9.16") "AC1: escaped dot literal"
        assert false (regex match 'v\d+\.\d+\.\d+' "v0X9Y16") "AC1: escaped dot rejects non-dot"
        assert true (regex is match '^hello' "hello world") "AC1: bol anchor matches start"
        assert false (regex is match '^world' "hello world") "AC1: bol anchor rejects middle"
        assert true (regex is match 'world$' "hello world") "AC1: eol anchor matches end"
        assert false (regex is match 'hello$' "hello world") "AC1: eol anchor rejects prefix"
        assert true (regex is match '^exact$' "exact") "AC1: anchored ^exact$ matches full string"
        assert false (regex is match '^exact$' "not exact") "AC1: anchored ^exact$ rejects extra chars"
        -- Russ Cox pathological backtracking benchmarks (exponential in backtracking engines, O(N*M) in Thompson NFA)
        assert false (regex match '(a+)+b' "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaac") "AC1: Thompson NFA immune to (a+)+b ReDoS"
        assert false (regex match '(a|aa)+b' "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaac") "AC1: Thompson NFA immune to (a|aa)+b ReDoS"
        assert true (regex match 'a?a?a?a?a?a?a?a?aaaaaaaa' "aaaaaaaa") "AC1: Russ Cox a?^n a^n vector"
        ()

19.3.4. Exemple 4: Extracció de coincidències (regex find, regex find all), reemplaçament (regex replace, regex replace all) i divisió (regex split)

En aquest exemple pràctic explorem de manera exhaustiva com es comporta regex en aquest bloc funcional, incloent-hi entrades estàndard, combinacions de paràmetres i valors frontera:

fn :: test regex find replace split => ()
      test regex find replace split =
        m1 = regex find '\d+' "item #42 and #99"
        assert true (matched m1) "AC2: find matched"
        assert int equals (match_start m1) 6 "AC2: find start"
        assert int equals (match_end m1) 8 "AC2: find end"
        assert str eq (text m1) "42" "AC2: find text"

        m_none = regex find '\d+' "no digits here"
        assert false (matched m_none) "AC2: find returns matched=False when absent"

        all_m = regex find all '[a-z]+=\d+' "id=10, port=8080, ttl=60"
        assert int equals (re match count all_m) 3 "AC2: find all key=val count"
        assert str eq (text (re match at all_m 0)) "id=10" "AC2: find all first match"
        assert str eq (text (re match at all_m 1)) "port=8080" "AC2: find all second match"
        assert str eq (text (re match at all_m 2)) "ttl=60" "AC2: find all third match"

        r1 = regex replace '\d+' "X" "v1.2.3"
        assert str eq r1 "vX.2.3" "AC3: replace first"
        r_no = regex replace '\d+' "X" "abc"
        assert str eq r_no "abc" "AC3: replace with no match returns original"
        r2 = regex replace all '\d+' "X" "v1.22.333"
        assert str eq r2 "vX.X.X" "AC3: replace all"

        parts = regex split '\s*[,;]\s*' "alpha, beta ;  gamma,delta"
        assert int equals (re str count parts) 4 "AC3: split count"
        assert str eq (re str at parts 0) "alpha" "AC3: split[0]"
        assert str eq (re str at parts 1) "beta" "AC3: split[1]"
        assert str eq (re str at parts 2) "gamma" "AC3: split[2]"
        assert str eq (re str at parts 3) "delta" "AC3: split[3]"
        ()

19.3.5. Exemple 5: Validador d'identificadors i anonimitzador de traces en temps lineal $O(N \cdot M)$ amb Thompson NFA (regex is match, regex replace all, regex split)

En aquest exemple pràctic explorem de manera exhaustiva com es comporta regex en aquest bloc funcional, incloent-hi entrades estàndard, combinacions de paràmetres i valors frontera:

import regex

fn :: limpiar traza y validar id (usuario_id : String) (linea_log : String) => (Bool, String, [String])
      limpiar traza y validar id usuario_id linea_log =
        id_valido = regex is match "^usr_[a-z0-9]+$" usuario_id
        sin_ips   = regex replace all "\d+\.\d+\.\d+\.\d+" linea_log "[IP-REDACTADA]"
        tokens    = regex split "\s+" sin_ips
        (id_valido, sin_ips, tokens)

---

19.4. Sota el capó: com està construïda regex en Ridgun pur (src/main/ridgun/lib/regex.rg)

Un dels majors avantatges de ridgun-libs és que no hi ha caixes negres en C. Pots obrir src/main/ridgun/lib/regex.rg i llegir exactament com està implementada cada operació fent servir pattern matching, arbres de guardes | / |. i recursió de cua (TCO). Vegem les peces clau de la seva implementació real:

19.4.1. Implementació interna: Character Class & Shorthand Helpers

Fixa't en com regex.rg estructura les signatures fn :: ... => ... primer i resol cada cas mitjançant equacions alineades i crides de cua:

module :: regex

fn :: re is digit Int => Bool
      re is digit c = c >= 48 and c <= 57

fn :: re is word Int => Bool
      re is word c = (c >= 48 and c <= 57) or (c >= 65 and c <= 90) or (c >= 97 and c <= 122) or c == 95

fn :: re is space Int => Bool
      re is space c = c == 32 or c == 9 or c == 10 or c == 13 or c == 11 or c == 12

fn :: re match short Int Int => Bool
      re match short 100 c = re is digit c
      re match short 68 c = not (re is digit c)
      re match short 119 c = re is word c
      re match short 87 c = not (re is word c)
      re match short 115 c = re is space c
      re match short 83 c = not (re is space c)
      re match short _ _ = False

fn :: re in ranges Int [Int] => Bool
      re in ranges _ [] = False
      re in ranges _ (_:[]) = False
      re in ranges c (lo:hi:rs) =
        | c >= lo and c <= hi = True
        | otherwise = re in ranges c rs

19.4.2. Implementació interna: Thompson NFA Compiler (ReNode -> [NfaInst])

Fixa't en com regex.rg estructura les signatures fn :: ... => ... primer i resol cada cas mitjançant equacions alineades i crides de cua:

fn :: nfa len [NfaInst] => Int
      nfa len [] = 0
      nfa len (_:rest) = 1 + (nfa len rest)

fn :: re compile seq ReNode ReNode Int => [NfaInst]
      re compile seq a b start_id =
        insts_a = re compile node a start_id
        mid_id = start_id + (nfa len insts_a)
        insts_b = re compile node b mid_id
        insts_a :: insts_b

fn :: re compile opt ReNode Int => [NfaInst]
      re compile opt a start_id =
        body = re compile node a (start_id + 1)
        end_id = start_id + 1 + (nfa len body)
        [InstSplit (start_id + 1) end_id] :: body

fn :: re compile star ReNode Int => [NfaInst]
      re compile star a start_id =
        body = re compile node a (start_id + 1)
        end_id = start_id + 2 + (nfa len body)
        ([InstSplit (start_id + 1) end_id] :: body) :: [InstJump start_id]

fn :: re compile plus ReNode Int => [NfaInst]
      re compile plus a start_id =
        body = re compile node a start_id
        split_id = start_id + (nfa len body)
        body :: [InstSplit start_id (split_id + 1)]

fn :: re compile alt ReNode ReNode Int => [NfaInst]
      re compile alt a b start_id =
        body_a = re compile node a (start_id + 1)
        jump_id = start_id + 1 + (nfa len body_a)
        start_b = jump_id + 1
        body_b = re compile node b start_b
        end_id = start_b + (nfa len body_b)
        (([InstSplit (start_id + 1) start_b] :: body_a) :: [InstJump end_id]) :: body_b

fn :: re compile node ReNode Int => [NfaInst]
      re compile node ReEmpty _ = []
      re compile node (ReChar c) start_id = [InstChar c (start_id + 1)]
      re compile node ReAny start_id = [InstAny (start_id + 1)]
      re compile node (ReClass neg rngs) start_id = [InstClass neg rngs (start_id + 1)]
      re compile node (ReShort k) start_id = [InstShort k (start_id + 1)]
      re compile node ReBol start_id = [InstBol (start_id + 1)]
      re compile node ReEol start_id = [InstEol (start_id + 1)]
      re compile node (ReOpt a) start_id = re compile opt a start_id
      re compile node (ReStar a) start_id = re compile star a start_id
      re compile node (RePlus a) start_id = re compile plus a start_id
      re compile node (ReSeq a b) start_id = re compile seq a b start_id
      re compile node (ReAlt a b) start_id = re compile alt a b start_id

fn :: re compile String => [NfaInst]
      re compile pat =
        re parse alt pat 0 (str len pat) -> parsed
        (re compile node (re res node parsed) 0) :: [InstMatch]

19.4.3. Implementació interna: Linear-Time Thompson NFA State-Set Simulation

Fixa't en com regex.rg estructura les signatures fn :: ... => ... primer i resol cada cas mitjançant equacions alineades i crides de cua:

fn :: nfa inst at [NfaInst] Int => NfaInst
      nfa inst at [] _ = InstMatch
      nfa inst at (i:_) 0 = i
      nfa inst at (_:rest) idx = nfa inst at rest (idx - 1)

fn :: nfa set has [Int] Int => Bool
      nfa set has [] _ = False
      nfa set has (x:xs) v =
        | x == v = True
        | otherwise = nfa set has xs v

fn :: nfa closure [NfaInst] [Int] Int Int [Int] => [Int]
      nfa closure _ [] _ _ visited = visited
      nfa closure prog (s:ss) pos len visited =
        | nfa set has visited s = nfa closure prog ss pos len visited
        | otherwise = nfa closure inst prog s ss pos len (visited :: [s]) (nfa inst at prog s)

fn :: nfa closure inst [NfaInst] Int [Int] Int Int [Int] NfaInst => [Int]
      nfa closure inst prog _ ss pos len vis (InstJump out) = nfa closure prog ([out] :: ss) pos len vis
      nfa closure inst prog _ ss pos len vis (InstSplit o1 o2) = nfa closure prog ([o1, o2] :: ss) pos len vis
      nfa closure inst prog _ ss pos len vis (InstBol out) =
        | pos == 0 = nfa closure prog ([out] :: ss) pos len vis
        | otherwise = nfa closure prog ss pos len vis
      nfa closure inst prog _ ss pos len vis (InstEol out) =
        | pos == len = nfa closure prog ([out] :: ss) pos len vis
        | otherwise = nfa closure prog ss pos len vis
      nfa closure inst prog _ ss pos len vis _ = nfa closure prog ss pos len vis

fn :: nfa step one NfaInst Int => [Int]
      nfa step one (InstChar expected out) c =
        | c == expected = [out]
        | otherwise = []
      nfa step one (InstAny out) c =
        | c != 10 = [out]
        | otherwise = []
      nfa step one (InstClass neg rngs out) c =
        | (re in ranges c rngs) != neg = [out]
        | otherwise = []
      nfa step one (InstShort kind out) c =
        | re match short kind c = [out]
        | otherwise = []
      nfa step one _ _ = []

fn :: nfa step [NfaInst] [Int] Int => [Int]
      nfa step _ [] _ = []
      nfa step prog (s:ss) c = (nfa step one (nfa inst at prog s) c) :: (nfa step prog ss c)

fn :: nfa is match inst NfaInst => Bool
      nfa is match inst InstMatch = True
      nfa is match inst _ = False

fn :: nfa has match [NfaInst] [Int] => Bool
      nfa has match _ [] = False
      nfa has match prog (s:ss) =
        | nfa is match inst (nfa inst at prog s) = True
        | otherwise = nfa has match prog ss

fn :: nfa update last [NfaInst] [Int] Int Int => Int
      nfa update last prog active cand cur =
        | nfa has match prog active = cand
        | otherwise = cur

fn :: nfa sim loop [NfaInst] String Int Int [Int] Int => Int
      nfa sim loop _ _ _ _ [] last_m = last_m
      nfa sim loop prog input pos len active last_m =
        | pos >= len = last_m
        | otherwise = nfa sim step prog input pos len active last_m

fn :: nfa sim step [NfaInst] String Int Int [Int] Int => Int
      nfa sim step prog input pos len active last_m =
        str char at input pos -> c
        nfa closure prog (nfa step prog active c) (pos + 1) len [] -> next_act
        nfa update last prog next_act (pos + 1) last_m -> next_last
        nfa sim loop prog input (pos + 1) len next_act next_last

fn :: nfa longest from [NfaInst] String Int Int => Int
      nfa longest from prog input pos len =
        nfa closure prog [0] pos len [] -> init_act
        nfa update last prog init_act pos (0 - 1) -> init_last
        nfa sim loop prog input pos len init_act init_last

fn :: nfa full loop [NfaInst] String Int Int [Int] => Bool
      nfa full loop _ _ _ _ [] = False
      nfa full loop prog input pos len active =
        | pos >= len = nfa has match prog active
        | otherwise = nfa full step prog input pos len active

fn :: nfa full step [NfaInst] String Int Int [Int] => Bool
      nfa full step prog input pos len active =
        str char at input pos -> c
        nfa closure prog (nfa step prog active c) (pos + 1) len [] -> next_act
        nfa full loop prog input (pos + 1) len next_act

19.4.4. Implementació interna: Public Regex API (API-REGEX-001)

Fixa't en com regex.rg estructura les signatures fn :: ... => ... primer i resol cada cas mitjançant equacions alineades i crides de cua:

fn :: regex match String String => Bool
      regex match pat input =
        pat re compile -> prog
        input str len -> len
        nfa closure prog [0] 0 len [] -> init_act
        nfa full loop prog input 0 len init_act

fn :: nfa find from [NfaInst] String Int Int => RegexMatch
      nfa find from prog input pos len =
        | pos > len = RegexMatch False (0 - 1) (0 - 1) ""
        | otherwise = nfa find check prog input pos len (nfa longest from prog input pos len)

fn :: nfa find check [NfaInst] String Int Int Int => RegexMatch
      nfa find check prog input pos len end_pos =
        | end_pos >= pos = RegexMatch True pos end_pos (str slice input pos end_pos)
        | otherwise = nfa find from prog input (pos + 1) len

fn :: regex find String String => RegexMatch
      regex find pat input =
        pat re compile -> prog
        nfa find from prog input 0 (str len input)

fn :: regex is match String String => Bool
      regex is match pat input = regex find pat input -> matched

fn :: nfa find all loop [NfaInst] String Int Int [RegexMatch] => [RegexMatch]
      nfa find all loop prog input pos len acc =
        | pos > len = acc
        | otherwise = nfa find all step prog input pos len acc (nfa longest from prog input pos len)

fn :: nfa find all step [NfaInst] String Int Int [RegexMatch] Int => [RegexMatch]
      nfa find all step prog input pos len acc end_pos =
        | end_pos > pos = nfa find all loop prog input end_pos len (acc :: [RegexMatch True pos end_pos (str slice input pos end_pos)])
        | end_pos == pos = nfa find all loop prog input (pos + 1) len (acc :: [RegexMatch True pos pos ""])
        | otherwise = nfa find all loop prog input (pos + 1) len acc

fn :: regex find all String String => [RegexMatch]
      regex find all pat input =
        pat re compile -> prog
        nfa find all loop prog input 0 (str len input) []

fn :: regex replace String String String => String
      regex replace pat repl input =
        regex find pat input -> m
        re apply replace m repl input

fn :: re apply replace RegexMatch String String => String
      re apply replace m repl input =
        | not (matched m) = input
        | otherwise = (str slice input 0 (match_start m)) + repl + (str slice input (match_end m) (str len input))

fn :: nfa replace all loop [NfaInst] String String Int Int String => String
      nfa replace all loop prog repl input pos len acc =
        | pos >= len = acc
        | otherwise = nfa replace all step prog repl input pos len acc (nfa longest from prog input pos len)

fn :: nfa replace all step [NfaInst] String String Int Int String Int => String
      nfa replace all step prog repl input pos len acc end_pos =
        | end_pos > pos = nfa replace all loop prog repl input end_pos len (acc + repl)
        | otherwise = nfa replace all loop prog repl input (pos + 1) len (acc + (str slice input pos (pos + 1)))

fn :: regex replace all String String String => String
      regex replace all pat repl input =
        pat re compile -> prog
        nfa replace all loop prog repl input 0 (str len input) ""

fn :: nfa split loop [NfaInst] String Int Int Int [String] => [String]
      nfa split loop prog input pos len last_s acc =
        | pos >= len = acc :: [str slice input last_s len]
        | otherwise = nfa split step prog input pos len last_s acc (nfa longest from prog input pos len)

fn :: nfa split step [NfaInst] String Int Int Int [String] Int => [String]
      nfa split step prog input pos len last_s acc end_pos =
        | end_pos > pos = nfa split loop prog input end_pos len end_pos (acc :: [str slice input last_s pos])
        | otherwise = nfa split loop prog input (pos + 1) len last_s acc

fn :: regex split String String => [String]
      regex split pat input =
        pat re compile -> prog
        nfa split loop prog input 0 (str len input) 0 []

---

19.5. Garanties algorísmiques, memòria RMM1/RMM2 i les 5 Regles d'Or de regex

• Garantia algorísmica i de seguretat: Simulació de conjunt d'estats NFA sense recursió descontrolada de pila i temps $O(N \cdot M)$ garantit fins i tot davant patrons patològics (a+)+b.
• Complexitat de pila $O(1)$ amb TCO: Tots els bucles recursius a src/main/ridgun/lib/regex.rg estan en posició de cua, de manera que ridgunc els compila a salts natius sense creixement de pila.
• Memòria determinista (RMM1/RMM2): Zero pauses de recol·lector de brossa; totes les estructures intermèdies s'alliberen de forma determinista en sortir de l'àmbit.
• Verificació contínua: Provada exhaustivament amb stable check i la suite automatitzada src/test/ridgun/test regex.rg.

Les 5 Regles d'Or en programar amb regex

1. Declara import regex a l'inici del fitxer i aprofita l'equivalència entre espais i guions baixos perquè el teu codi es llegeixi com a prosa.
2. Alinea les teves canonades de dades amb =: encadena les crides a regex en passos amb nom propi i deixa que stable format alineï les columnes.
3. Aprofita les funcions totals de regex a les teves guardes |: comprova els valors de retorn o desembolica els ADTs amb pattern matching en lloc d'assumir que l'entrada externa sempre és vàlida.
4. Evita copiar grans estructures si només necessites consultar un camp: recorda que en RMM2 els arguments d'entrada no incrementen ni decrementen comptadors (+0 / -0).
5. Combina regex amb test (import test): escriu sempre assercions amb assert equals o assert true per fixar els invariants del teu domini.

---

Al Capítol 20 passarem a explorar en profunditat la lib glob (La lib glob — Patrons de Comodins (*, ?, [a-z]) i Filtratge de Llistes).