(sigil regex)
(sigil regex) - Regular expressions with guaranteed linear-time matching
A regular expression engine written in Sigil. Patterns use the RE2 / Go regexp syntax, and matching runs on a Pike VM (a Thompson NFA simulation that carries capture positions per thread), so one match or search takes time proportional to the length of the input (times the size of the pattern) for every pattern. A hostile or careless pattern such as (a*)*b cannot make a match take exponential time, and compiling is bounded too.
regex-match-all, regex-replace-all and regex-split run one search per match. As in Go and RE2, each search may read ahead to the end of the text, so a pattern like a*b|a over a long run of as costs up to (number of matches x length); that is quadratic, never exponential.
Positions are character indexes, the same indexes substring and string-ref use, including on non-ASCII text.
(import (sigil regex))
(regex-match? "^[0-9a-f]{64}$" digest) ; whole-string test
(define version (regex "v(\\d+)\\.(\\d+)")) ; compile once
(let ((m (regex-search version "tag v12.4")))
(match-group m 1)) ; => "12"
(regex-replace-all "\\s+" "a b\tc" " ") ; => "a b c"
(regex-split "," "a,b,,c") ; => ("a" "b" "" "c")Every procedure that takes a regex also accepts a pattern string and compiles it through a small cache, so one-off script calls stay cheap.
Syntax
Literals and escapes (\n \t \r \f \v \a, \x7F, \x{10FFFF}, octal \0, \123, \ before any ASCII punctuation, \Q...\E), ., classes [...] with ranges, negation, \d \w \s \D \W \S and POSIX [[:alpha:]] names, anchors ^ $ \A \z \b \B, alternation |, groups (...), non-capturing (?:...), named (?P<name>...) and (?<name>...), quantifiers * + ? {m} {m,} {m,n} and their lazy forms (*? and so on), and flags (?i) (?m) (?s) (?U), also scoped as (?i:...) and cleared with (?-i).
\d, \w, \s and \b are ASCII, as in RE2 and Go. . matches any character except newline unless (?s) is set. Without (?m), ^ and $ match only at the start and end of the text. (?i) uses Unicode simple case folding from (sigil unicode case), the same orbits as Go and RE2 (k, K and KELVIN SIGN match each other), so it behaves the same on every backend.
Beyond backreferences and lookaround (below), these differ from Go on purpose: \p Unicode property classes are refused; groups may nest at most 100 deep (Go allows 1000); a compiled program is capped at 100,000 instructions (Go allows more); and in a replacement template a group name is ASCII letters, digits and _ (Go also reads non-ASCII letters into the name, which then names no group and inserts nothing).
Not supported
Backreferences (\1) and lookaround ((?=...), (?!...), (?<=...)) are rejected with a regex-error. They are what forces an engine to backtrack, and backtracking is what makes matching time exponential; RE2 and Go make the same trade.
Errors
A bad pattern raises an exception of kind regex-error whose message names the character position in the pattern. Test for it with regex-error? and read the position with regex-error-position.
Exports
regex-error?procedureTrue if OBJ is the exception raised for an invalid pattern.
(guard (e ((regex-error? e) (regex-error-position e)))
(regex "ab("))
; => 2regex-error-positionprocedureThe character position in the pattern where a regex-error was found.
compiled-regexprocedureConstruct a compiled-regex struct.
compiled-regex?procedureTest if a value is a compiled-regex struct.
compiled-regex-patternprocedureGet the pattern field of a compiled-regex struct.
compiled-regex-programprocedureGet the program field of a compiled-regex struct.
compiled-regex-group-countprocedureGet the group-count field of a compiled-regex struct.
compiled-regex-group-namesprocedureGet the group-names field of a compiled-regex struct.
regexprocedureCompile PATTERN into a regex.
Raises a regex-error naming the position of the problem when the pattern is invalid. Compile once and reuse the result when matching in a loop; every matching procedure also accepts a pattern string.
(define hex64 (regex "^[0-9a-f]{64}$"))
(regex-match? hex64 digest)regex?procedureTrue if OBJ is a compiled regex.
regex-patternprocedureThe pattern string a regex was compiled from.
regex-group-countprocedureThe number of capturing groups in a regex, not counting group 0.
regex-group-namesprocedureThe named groups of a regex as an alist of (name . index).
match-dataprocedureConstruct a match-data struct.
match-data?procedureTest if a value is a match-data struct.
match-data-textprocedureGet the text field of a match-data struct.
match-data-charsprocedureGet the chars field of a match-data struct.
match-data-capturesprocedureGet the captures field of a match-data struct.
match-data-group-namesprocedureGet the group-names field of a match-data struct.
match-groupvariableThe text matched by GROUP, or #f if that group did not take part.
GROUP is 0 (the whole match, the default), a group number, or a group name as a string or symbol. An unknown group raises an error. When several groups share a name, the first of them that took part is used.
(define m (regex-search "(?P<major>\\d+)\\.(\\d+)" "v1.22"))
(match-group m) ; => "1.22"
(match-group m 'major) ; => "1"
(match-group m 2) ; => "22"match-startvariableThe character index where GROUP (default 0) starts, or #f if unset.
match-endvariableThe character index just past the end of GROUP (default 0), or #f.
match-groupsprocedureThe text of groups 1 and up, as a list with #f for groups that did not take part in the match.
match-named-groupsprocedureThe named groups as an alist of (name . text).
regex-match?procedureTrue if RE matches the whole of TEXT.
(regex-match? "v[0-9]+" "v12") ; => #t
(regex-match? "v[0-9]+" "v12a") ; => #fregex-matchprocedureMatch RE against the whole of TEXT, returning match data or #f.
Like regex-match?, but the result carries the capture groups.
regex-searchvariableFind the leftmost match of RE in TEXT, returning match data or #f.
START (a keyword, default 0) is the character index to search from; anchors and \b still see the text before it.
Each call converts all of TEXT to characters first, so a loop that walks a long text with START costs the whole text per step. Use regex-match-all to visit every match.
(match-group (regex-search "[0-9]+" "abc 123 456")) ; => "123"regex-match-allprocedureEvery non-overlapping match of RE in TEXT, left to right.
An empty match directly after a previous match is skipped, as in Go.
(map match-group (regex-match-all "[0-9]+" "a1 b22 c333"))
; => ("1" "22" "333")regex-replaceprocedureReplace the first match of RE in TEXT.
REPLACEMENT is a template string or a procedure. In a template, $1 or ${1} inserts group 1, $name or ${name} inserts a named group, $0 the whole match, and $$ a literal $. A reference to a group that does not exist or did not match inserts nothing. Use the braces when a name is followed by a letter, digit or _: ${1}x, not $1x (which means the group named "1x"). A procedure receives the match data and returns the replacement string. When several groups share a name, $name inserts the first of them that took part.
(regex-replace "(\\w+)@(\\w+)" "me@host" "$2 at ${1}") ; => "host at me"
(regex-replace "\\d+" "a1b22" (lambda (m) "#")) ; => "a#b22"regex-replace-allprocedureReplace every match of RE in TEXT. REPLACEMENT is as for regex-replace.
(regex-replace-all "\\s+" "a b\tc" " ") ; => "a b c"regex-splitprocedureSplit TEXT around the matches of RE.
Follows Go's Split(s, -1): an empty TEXT gives (""), and separators at the start or end give empty strings there.
(regex-split "," "a,b,,c") ; => ("a" "b" "" "c")
(regex-split "\\s*;\\s*" "x ; y") ; => ("x" "y")regex-quoteprocedureEscape every regex metacharacter in TEXT, giving a pattern that matches TEXT literally.
(regex-quote "1.5*2") ; => "1\\.5\\*2"