Hoppa till innehållet
Ridgun
Svenska
EnglishEspañolPortuguêsSvenskaCatalàGalegoEuskaraItaliano

20 Boken om Ridgun

Lib:en glob — Jokerteckenmönster (*, ?, [a-z]) och Listfiltrering

20.1. Varför finns lib:en glob? (Det verkliga problemet och Ridguns filosofi)

”Varför behöver jag en glob-lib skriven från grunden i ren Ridgun i stället för att bara länka in ett gammalt C-bibliotek?”

Det är den första fråga varje systemingenjör ställer sig när man möter glob. Och svaret sammanfattar hela filosofin bakom ridgun-libs:

Låt oss vara ärliga: att dra igång en hel regex-motor bara för att kontrollera om ett filnamn matchar *.rg eller test_[0-9]*.rg är att skjuta mygg med kanon.

Lib:en glob implementerar exakt matchning av skal-jokertecken (*, ?, [a-z]-intervall, negerade [!0-9] / [^a-z]-klasser), skiftlägesokänslig matchning (glob match ci) och listfiltrering.

I ett traditionellt ekosystem innebär uppgifter inom domänen GLOB ofta att man drar in externa C-beroenden, brottas med råa pekare, ogenomskinliga typkonverteringar, okontrollerade undantag eller oförutsägbara skräpsamlarpauser. I Ridgun löser lib:en glob (src/main/ridgun/lib/glob.rg) problemet genom fyra kompromisslösa principer:

  1. Deklarera import glob (eller import glob as alias) överst i filen: varje lib definierar sin module :: glob-namnrymd och i --strict-läge anropas flerordsfunktioner alltid med naturliga mellanslag.
  2. Kedja dina datapipelines från vänster till höger med ->: skriv indata steg ett -> steg två -> resultat, använd (+ _ _ +)-sekvensmasker för att packa upp tupler och utelämna _ = vid sekventiella satser (eller kasta med -> ()).
  3. Svansrekursion med TCO (Tail-Call Optimization): alla interna genomlöpningar i glob kompileras till inbyggda hårdvaruloopar med $O(1)$ stackutrymme.
  4. Deterministiskt minne (RMM1 / RMM2): varje mellanliggande struktur frigörs i exakt det ögonblick dess sista läsning avslutas, helt utan Garbage Collector.

20.2. Inbyggda artefakter, import och komplett API-katalog för glob

I ridgun-libs är glob en förstklassig lib placerad i src/main/ridgun/lib/glob.rg (domän GLOB). När du bygger med stable bundle paketeras den i tre inbyggda format:

ArtefaktSökvägSyfte
Ridgun-bundletarget/bundles/glob.rglibPortabel distribution och direkt import med import glob
Kompilerat arkivtarget/glob.rgcTypkontrollerad mellanartefakt verifierad av ridgunc
Delat ELF64-objekttarget/libglob.soInbyggt dynamiskt bibliotek helt utan C- eller libc-beroenden

Varje lib deklarerar sin egen namnrymd med module :: glob: skriv bara import glob (eller import glob as alias) överst och anropa dess funktioner med naturliga mellanslag (min funktion x) och ->-pipelines (x min funktion -> resultat).

20.2.1. Översikt över funktionella familjer i glob

Signatur / Funktion / TypVad den gör och när den används
glob match / glob match ciSkiftlägeskänslig och skiftlägesokänslig glob-mönstermatchning
glob filter / glob any matchFiltrerar [String] till matchande element eller testar om något mönster i en lista matchar
glob has magicDetekterar om en sträng innehåller jokertecken (*, ?, [)

20.2.2. Komplett katalog över typer och signaturer i src/main/ridgun/lib/glob.rg

Nedan följer hela förteckningen över algebraiska datatyper (type), mixfix-operatorer (op ::) och funktionssignaturer (fn ::) som definieras i src/main/ridgun/lib/glob.rg (0 typer, 0 operatorer och 18 funktioner):

#Funktion / Signatur (fn ::)Returtyp
1fn :: gl lower char String Int IntString
2fn :: gl to lower loop String Int IntString
3fn :: gl to lower StringString
4fn :: gl find close bracket String Int IntInt
5fn :: gl match range String Int Int Int Int IntBool
6fn :: gl match class body String Int Int IntBool
7fn :: gl eval bracket char String Int Int Int IntBool
8fn :: gl eval bracket String Int Int IntBool
9fn :: gl skip stars String Int IntInt
10fn :: gl match star String Int Int String Int IntBool
11fn :: gl match star at String Int Int String Int IntBool
12fn :: gl match bracket step String Int Int String Int Int IntBool
13fn :: gl match step String Int Int String Int Int IntBool
14fn :: gl match loop String Int Int String Int IntBool
15fn :: glob match String StringBool
16fn :: glob match ci String StringBool
17fn :: glob filter String [String][String]
18fn :: glob any match [String] StringBool

20.3. Djupdykning i glob: Steg-för-steg-exempel för varje funktion

Det räcker inte med en signaturtabell: låt oss utforska varje funktionalitet i lib:en glob genom progressiva, körbara Ridgun-exempel. Vi börjar med två tabellbaserade vardagsrecept och går därefter igenom alla funktionella scenarier, transformationer och gränsfall som verifieras i src/test/ridgun/test glob.rg.

20.3.1. Exempel 1: Huvudflöde i tabellform med glob

Lägg märke till hur =-tecknen och transformationsstegen med glob linjeras som en ren tabell utan onödiga muterbara variabler eller dolda sidoeffekter:

import glob

fn :: seleccionar fuentes ridgun [String] => [String]
      seleccionar fuentes ridgun archivos =
        glob filter "test_[a-z]*.rg" archivos

20.3.2. Exempel 2: Säker komposition och hantering av gränsfall

Varje funktion i lib:en glob är utformad för att kombineras sömlöst med booleska vakter | och med övriga 32 libs i ridgun-libs:

import glob

fn :: es ruta excluida String => Bool
      es ruta excluida ruta =
        glob any match ["*.tmp", "*.bak", "target/*"] ruta

20.3.3. Exempel 3: Jokertecknen * och ?, exakt gränsmatchning och gränsfall med tomma mönster

I detta praktiska exempel undersöker vi grundligt hur glob beter sig inom detta funktionsområde, inklusive standardindata, parameterkombinationer och gränsvärden:

fn :: test glob wildcards and boundaries => ()
      test glob wildcards and boundaries =
        assert true (glob match "" "") "AC1: empty pattern matches empty string"
        assert false (glob match "" "a") "AC1: empty pattern rejects non-empty"
        assert true (glob match "*" "") "AC1: * matches empty string"
        assert true (glob match "***" "") "AC1: *** matches empty string"
        assert true (glob match "*" "anything.rg") "AC1: * matches full filename"
        assert true (glob match "*.rg" "socket.rg") "AC1: *.rg matches socket.rg"
        assert true (glob match "*.rg" ".rg") "AC1: *.rg matches leading dot .rg"
        assert false (glob match "*.rg" "README.md") "AC1: *.rg rejects README.md"
        assert false (glob match "*.rg" "socket.rg.bak") "AC1: *.rg rejects trailing suffix"
        assert true (glob match "test_?.rg" "test_a.rg") "AC1: ? matches single char"
        assert false (glob match "test_?.rg" "test_.rg") "AC1: ? rejects zero chars"
        assert false (glob match "test_?.rg" "test_ab.rg") "AC1: ? rejects two chars"
        assert true (glob match "???" "abc") "AC1: ??? matches 3 chars"
        assert false (glob match "???" "ab") "AC1: ??? rejects 2 chars"
        assert true (glob match "a*b*c" "abc") "AC1: multiple * matching zero chars"
        assert true (glob match "a*b*c" "axxxbyyyc") "AC1: multiple * matching substrings"
        assert true (glob match "a*b*c" "abbc") "AC1: backtracking * across repeated b"
        assert false (glob match "a*b*c" "axxxbyyy") "AC1: missing trailing literal after *"
        assert true (glob match "a***b" "axyzb") "AC1: collapsed *** matches"
        -- Pathological backtracking immunity via gl skip stars
        assert false (glob match "****************a" "bbbbbbbbbbbbbbbbbbbbbbbbbbbb") "AC1: collapsed stars avoid exponential backtracking"
        ()

20.3.4. Exempel 4: Teckenklasser [a-z], negerade intervall [!0-9] / [^0-9] och skiftlägesokänslig matchning (glob match ci)

I detta praktiska exempel undersöker vi grundligt hur glob beter sig inom detta funktionsområde, inklusive standardindata, parameterkombinationer och gränsvärden:

fn :: test glob classes and case insensitivity => ()
      test glob classes and case insensitivity =
        assert true (glob match "file_[0-9].txt" "file_0.txt") "AC2: [0-9] lower bound 0"
        assert true (glob match "file_[0-9].txt" "file_9.txt") "AC2: [0-9] upper bound 9"
        assert false (glob match "file_[0-9].txt" "file_a.txt") "AC2: [0-9] rejects alpha"
        assert true (glob match "id_[a-zA-Z0-9].rg" "id_Z.rg") "AC2: multi-range [a-zA-Z0-9] matches Z"
        assert true (glob match "id_[a-zA-Z0-9].rg" "id_5.rg") "AC2: multi-range [a-zA-Z0-9] matches 5"
        assert false (glob match "id_[a-zA-Z0-9].rg" "id__.rg") "AC2: multi-range [a-zA-Z0-9] rejects _"
        assert true (glob match "v[135].rg" "v3.rg") "AC2: discrete character set [135]"
        assert false (glob match "v[135].rg" "v2.rg") "AC2: discrete character set rejects 2"
        assert true (glob match "file_[!0-9].txt" "file_a.txt") "AC2: [!0-9] POSIX negated class"
        assert false (glob match "file_[!0-9].txt" "file_7.txt") "AC2: [!0-9] rejects digit"
        assert true (glob match "file_[^0-9].txt" "file_z.txt") "AC2: [^0-9] caret negated class"
        assert false (glob match "file_[^0-9].txt" "file_0.txt") "AC2: [^0-9] rejects digit"
        assert true (glob match "a[b" "a[b") "AC2: unclosed '[' matches literally"
        assert false (glob match "a[b" "axb") "AC2: unclosed '[' rejects non-bracket"

        -- Case-insensitive matching
        assert true (glob match ci "*.RG" "socket.rg") "AC2: glob_match_ci *.RG on lowercase"
        assert true (glob match ci "*.rg" "SOCKET.RG") "AC2: glob_match_ci *.rg on uppercase"
        assert true (glob match ci "src/**/Test_[A-Z]*.rg" "SRC/main/test_crypto.RG") "AC2: glob_match_ci mixed case"
        ()

20.3.5. Exempel 5: Batchfiltrering av sökvägslistor (glob filter) och matchning mot flera mönster (glob any match)

I detta praktiska exempel undersöker vi grundligt hur glob beter sig inom detta funktionsområde, inklusive standardindata, parameterkombinationer och gränsvärden:

fn :: test glob filter and any match => ()
      test glob filter and any match =
        files = ["socket.rg", "README.md", "test_socket.rg", "crypto.rg", "build.sh"]
        assert eq (glob filter "*.rg" files) ["socket.rg", "test_socket.rg", "crypto.rg"]
        assert eq (glob filter "test_*.rg" files) ["test_socket.rg"]
        assert eq (glob filter "*.nomatch" files) []
        assert eq (glob filter "*.rg" []) []
        assert true (glob any match ["*.md", "*.txt", "*.sh"] "README.md") "AC3: glob_any_match first pattern"
        assert true (glob any match ["*.md", "*.txt", "*.sh"] "build.sh") "AC3: glob_any_match last pattern"
        assert false (glob any match ["*.md", "*.txt"] "socket.rg") "AC3: glob_any_match no match"
        assert false (glob any match [] "socket.rg") "AC3: glob_any_match empty pattern list"
        ()

20.4. Under huven: hur glob är byggd i ren Ridgun (src/main/ridgun/lib/glob.rg)

En av de största fördelarna med ridgun-libs är att det inte finns några svarta lådor i C. Du kan öppna src/main/ridgun/lib/glob.rg och läsa exakt hur varje operation är implementerad med mönstermatchning, | / |.-vaktträd och svansrekursion (TCO). Låt oss titta på nyckeldelarna i den faktiska implementationen:

20.4.1. Intern implementation: Bracket Character Class [...] Matching

Se hur glob.rg deklarerar explicita fn :: ... => ...-kontrakt först och löser varje fall genom linjerade ekvationer och svansanrop:

module :: glob

fn :: gl find close bracket String Int Int => Int
      gl find close bracket pat idx plen =
        | idx >= plen                  = 0 - 1
        | (str char at pat idx) == 93  = idx
        | otherwise                    = gl find close bracket pat (idx + 1) plen

fn :: gl match range String Int Int Int Int Int => Bool
      gl match range pat idx end_idx tc lo hi =
        | tc >= lo and tc <= hi = True
        | otherwise             = gl match class body pat (idx + 3) end_idx tc

fn :: gl match class body String Int Int Int => Bool
      gl match class body pat idx end_idx tc =
        | idx >= end_idx = False
        | ((idx + 2) < end_idx) and ((str char at pat (idx + 1)) == 45) =
          gl match range pat idx end_idx tc (str char at pat idx) (str char at pat (idx + 2))
        | (str char at pat idx) == tc = True
        | otherwise                   = gl match class body pat (idx + 1) end_idx tc

fn :: gl eval bracket char String Int Int Int Int => Bool
      gl eval bracket char pat pstart close_idx tc c0 =
        | c0 == 33 or c0 == 94 = not (gl match class body pat (pstart + 1) close_idx tc)
        | otherwise            = gl match class body pat pstart close_idx tc

fn :: gl eval bracket String Int Int Int => Bool
      gl eval bracket pat pstart close_idx tc =
        gl eval bracket char pat pstart close_idx tc (str char at pat pstart)

20.4.2. Intern implementation: Wildcard (*, ?, [...]) Matcher

Se hur glob.rg deklarerar explicita fn :: ... => ...-kontrakt först och löser varje fall genom linjerade ekvationer och svansanrop:

fn :: gl skip stars String Int Int => Int
      gl skip stars pat pidx plen =
        | pidx >= plen                 = pidx
        | (str char at pat pidx) == 42 = gl skip stars pat (pidx + 1) plen
        | otherwise                    = pidx

fn :: gl match star String Int Int String Int Int => Bool
      gl match star pat pidx plen txt tidx tlen =
        | gl match loop pat pidx plen txt tidx tlen = True
        | tidx >= tlen                              = False
        | otherwise                                 = gl match star pat pidx plen txt (tidx + 1) tlen

fn :: gl match star at String Int Int String Int Int => Bool
      gl match star at pat next_p plen txt tidx tlen =
        | next_p >= plen = True
        | otherwise      = gl match star pat next_p plen txt tidx tlen

fn :: gl match bracket step String Int Int String Int Int Int => Bool
      gl match bracket step pat pidx plen txt tidx tlen close_idx =
        | close_idx < 0 =
          | (str char at txt tidx) == 91 = gl match loop pat (pidx + 1) plen txt (tidx + 1) tlen
          | otherwise                    = False |.
        | gl eval bracket pat (pidx + 1) close_idx (str char at txt tidx) =
          gl match loop pat (close_idx + 1) plen txt (tidx + 1) tlen
        | otherwise = False

fn :: gl match step String Int Int String Int Int Int => Bool
      gl match step pat pidx plen txt tidx tlen pc =
        | pc == 42                     = gl match star at pat (gl skip stars pat (pidx + 1) plen) plen txt tidx tlen
        | tidx >= tlen                 = False
        | pc == 63                     = gl match loop pat (pidx + 1) plen txt (tidx + 1) tlen
        | pc == 91                     = gl match bracket step pat pidx plen txt tidx tlen (gl find close bracket pat (pidx + 1) plen)
        | pc == (str char at txt tidx) = gl match loop pat (pidx + 1) plen txt (tidx + 1) tlen
        | otherwise                    = False

fn :: gl match loop String Int Int String Int Int => Bool
      gl match loop pat pidx plen txt tidx tlen =
        | pidx >= plen = tidx >= tlen
        | otherwise    = gl match step pat pidx plen txt tidx tlen (str char at pat pidx)

fn :: glob match String String => Bool
      glob match pat    txt    =  gl match loop pat 0 (str len pat) txt 0 (str len txt)

fn :: glob match ci String String => Bool
      glob match ci pat    txt    =
        pat gl to lower -> lpat
        txt gl to lower -> ltxt
        glob match lpat ltxt

fn :: glob filter String [String] => [String]
      glob filter _      []       =  []
      glob filter pat    (x:rest) =
        | glob match pat x = [x] :: (glob filter pat rest)
        | otherwise        = glob filter pat rest

fn :: glob any match [String] String => Bool
      glob any match []       _      =  False
      glob any match (p:rest) txt    =
        | glob match p txt = True
        | otherwise        = glob any match rest txt

20.5. Algoritmiska garantier, RMM1/RMM2-minne och de 5 Gyllene Reglerna för glob

  • Algoritmisk garanti och säkerhet: Automatisk sammanslagning av på varandra följande asterisker (*** $\rightarrow$ *) för att undvika onödig backtracking samt säker hantering av oavslutade [-klammrar.
  • $O(1)$ stackkomplexitet med TCO: Alla rekursiva loopar i src/main/ridgun/lib/glob.rg ligger i svansposition, så ridgunc kompilerar dem till inbyggda hopp utan stacktillväxt.
  • Deterministiskt minne (RMM1/RMM2): Noll skräpsamlarpauser; alla temporära strukturer frigörs deterministiskt när räckvidden lämnas.
  • Kontinuerlig verifiering: Statiskt kontrollerad med stable check och verifierad av den automatiserade testsviten src/test/ridgun/test glob.rg.

De 5 Gyllene Reglerna när du programmerar med glob

  1. Deklarera import glob överst i filen och utnyttja att mellanslag och understreck är utbytbara så att koden läses som naturlig prosa.
  2. Linjera dina datapipelines med =: kedja samman glob-anrop i namngivna mellansteg och låt stable format linjera kolumnerna.
  3. Utnyttja glob:s totala funktioner i dina |-vakter: kontrollera returvärden eller packa upp ADT:er med mönstermatchning i stället för att anta att extern indata alltid är giltig.
  4. Undvik att kopiera stora strukturer när du bara läser ett fält: kom ihåg att i RMM2 medför inargument noll referensräkningskostnad (+0 / -0).
  5. Kombinera glob med test (import test): lås alltid fast dina domäninvarianter med assert equals eller assert true.

I Kapitel 21 går vi vidare och utforskar lib:en diff på djupet (Lib:en diff — LCS-raddiff, Redigeringsavstånd, Unified Diff och Patchning).