regexcore

nimony/lib/std/private/regexcore.nim

Regular expression engine core: parser, NFA construction, subset construction and DFA minimization. Derived from lexim.

This module is shared by two very different consumers:

std/regex compiles a pattern at runtime and walks the resulting DFA

as bytecode;

std/deps/regex, the plugin behind std/regex's lex construct, runs the

very same pipeline at compile time and emits the DFA as straight-line Nimony code.

Sharing the pipeline is the point: a pattern cannot mean one thing in a generated lexer and another at runtime, because there is only one implementation of what it means.

Nothing in here raises. A malformed pattern sets err on the context and parsing unwinds to an epsilon node; every entry point hands that message back so the runtime API can turn it into an exception and the plugin into a compile-time diagnostic, each at its own source location.

type RegexKind = enum
  reEps = (0, "reEps")
  reChar = (1, "reChar")
  reStr = (2, "reStr")
  reCClass = (3, "reCClass")
  reStar = (4, "reStar")
  rePlus = (5, "rePlus")
  reOpt = (6, "reOpt")
  reCat = (7, "reCat")
  reAlt = (8, "reAlt")
  reCapture = (9, "reCapture")
  reCaptureEnd = (10, "reCaptureEnd")
  reBackref = (11, "reBackref")
  reBegin = (12, "reBegin")
  reEnd = (13, "reEnd")
  reWordBoundary = (14, "reWordBoundary")
  reWordBoundaryNot = (15, "reWordBoundaryNot")

func dollar`.RegexKind(e: RegexKind): string
type RegexNode = ref RegexNode.Obj

type RegexNode.Obj = object
  kind: RegexKind
  a: ref RegexNode.Obj
  b: ref RegexNode.Obj
  c: char
  s: string
  cc: set[char]
  rule: int64

type RegexFlag = enum
  reExtended = (0, "reExtended")
  reNoBackrefs = (1, "reNoBackrefs")
  reNoCaptures = (2, "reNoCaptures")

func dollar`.RegexFlag(e: RegexFlag): string
const wordChars: set[char]
const whitespace: set[char]
const digits: set[char]
proc epsExpr(): ref RegexNode.Obj
proc charExpr(c: char): ref RegexNode.Obj
proc backrefExpr(x: int64): ref RegexNode.Obj
proc strExpr(str: string): ref RegexNode.Obj
proc cclassExpr(charset: set[char]): ref RegexNode.Obj
proc starExpr(r: ref RegexNode.Obj): ref RegexNode.Obj
proc plusExpr(r: ref RegexNode.Obj): ref RegexNode.Obj
proc optExpr(r: ref RegexNode.Obj): ref RegexNode.Obj
proc catExpr(a: ref RegexNode.Obj; b: ref RegexNode.Obj): ref RegexNode.Obj
proc altExpr(a: ref RegexNode.Obj; b: ref RegexNode.Obj): ref RegexNode.Obj
proc captureExpr(a: ref RegexNode.Obj): ref RegexNode.Obj
proc parseRegExpr(pattern: string; flags: set[RegexFlag]; err: var string): ref RegexNode.Obj
Parses pattern. On failure err describes what went wrong and the result is an epsilon node, so callers may keep walking the tree without a nil check as long as they test err before using the result.
proc containsInvalidCapture(r: ref RegexNode.Obj): bool
A DFA can only track a capture that every accepting path runs through, so (abc)|(xyz) is not expressible. Callers use this to say so up front instead of returning wrong capture bounds.

type Alphabet = object
  kind: RegexKind
  val: char

type Label = int32
a state number
type LabelSet = IntSet

type DfaEdge = object
  cond: Alphabet
  dest: int32

type NfaEdge = object
  cond: Alphabet
  dest: seq

type Dfa = object
  startState: int64
  stateCount: int64
  captures: int64
  backrefs: int64
  ruleCount: int64
  trans: seq
  toRules: seq

type Nfa = object
  captures: int64
  backrefs: int64
  stateCount: int64
  trans: seq
  toRules: seq

const alEpsilon: Alphabet
func allTransitions(a: Dfa; source: int64; dest: int64): tuple[seq, set[char]]
Splits the source -> dest edges into the assertions and markers (which have to be tested one by one) and the plain characters (which collapse into one set test). A single character is handed back as an Alphabet too, because x == 'a' beats x in {'a'} in the generated code.
iterator allDests(a: Dfa; source: int64): int64
Every state reachable from source, each yielded once and in state order.
func getRule(a: Dfa; s: int64): int64
proc rulesToDfa(patterns: openArray; flags: set[RegexFlag]; dfa: var Dfa; err: var string)
The whole pipeline: parse every pattern, tag it with its rule number, alternate them into one expression and run that through NFA → DFA → minimization. Rule numbers are 1-based and follow patterns' order, which is what makes "the earlier pattern wins a tie" the rule everywhere.
proc regexToDfa(pattern: string; flags: set[RegexFlag]; dfa: var Dfa; err: var string)
rulesToDfa for the single-pattern case, plus the capture check that only makes sense there.

type RegexOpcode = enum
  opcRet = (0, "opcRet")
  opcTestSet = (1, "opcTestSet")
  opcTestChar = (2, "opcTestChar")
  opcTJmp = (3, "opcTJmp")
  opcBegin = (4, "opcBegin")
  opcEnd = (5, "opcEnd")
  opcWordBound = (6, "opcWordBound")
  opcCaptureBegin = (7, "opcCaptureBegin")
  opcCaptureEnd = (8, "opcCaptureEnd")
  opcBackref = (9, "opcBackref")

func dollar`.RegexOpcode(e: RegexOpcode): string

type RegexInstr = object
  opc: RegexOpcode
  arg: int32

type Regex = object
  code: seq
  data: seq
  startAt: int64
  captures: int64
  capCode: seq
  capData: seq
  capStartAt: int64

type Capture = object
  first: int64
  last: int64

const CaptureOpen: int64
last while the group is still being matched
func emptyRegex(): Regex
func genBytecode(a: Dfa; res: var Regex)
Lowers a minimized DFA to the instruction stream exec walks.
proc compileRegex(pattern: string; flags: set[RegexFlag]; dest: var Regex; err: var string): bool
Pattern text to finished automaton. false with a message in err for a pattern this engine cannot express; dest then matches nothing.
func exec(r: Regex; s: string; caps: var seq; start: int64; endPos: var int64): int64
Matches r at start. Returns the rule that matched (0 for none), reports the position just past the match in endPos and fills caps with the capture bounds.
The match is decided by r.code; r.capCode, when present, runs afterwards purely for the bounds and is allowed to come up empty-handed without changing the answer.