Skip to content

RegExp.RegExpSearch

Defined in regexp@1.1.5

Running the automaton over the input: the scanner that walks sets of threads, and the walk that carries the threads one at a time. This is an internal module of RegExp.

Values

namespace RegExp.RegExpSearch::DFA

find

Type: Std::Array Std::U8 -> Std::I64 -> RegExp.RegExpSearch::DFA -> (Std::Option RegExp.RegExpNFA::Groups, RegExp.RegExpSearch::DFA)

The leftmost match beginning at or after a position, taking the longest of those that begin at the same place, together with the scanner as the search left it.

Positions holding a byte no match can begin with are passed over without the automaton being walked at all, which is what makes a search over text a pattern rarely meets cost little more than reading the text.

Parameters
  • bytes - The bytes to read.
  • from - The position at or after which the match has to begin.
  • dfa - The scanner.

make

Type: RegExp.RegExpNFA::NFA -> RegExp.RegExpSearch::DFA

A scanner that has walked nothing yet.

Parameters
  • nfa - The automaton to walk.

namespace RegExp.RegExpSearch::NFA

Type: Std::Array Std::U8 -> Std::I64 -> RegExp.RegExpNFA::NFA -> Std::Option RegExp.RegExpNFA::Groups

Runs the automaton over the bytes and reports the leftmost match beginning at or after a position, taking the longest of those that begin at the same place.

Parameters
  • bytes - The bytes to read.
  • from - The position at or after which the match has to begin.
  • nfa - The automaton to run.

search_all

Type: Std::Array Std::U8 -> RegExp.RegExpNFA::NFA -> Std::Array RegExp.RegExpNFA::Groups

Every match the automaton finds, taken left to right, none of them overlapping another.

Parameters
  • bytes - The bytes to read.
  • nfa - The automaton to run.

namespace RegExp.RegExpSearch::Walk

make

Type: RegExp.RegExpNFA::NFA -> RegExp.RegExpSearch::Walk

A walk carrying no thread.

Parameters
  • nfa - The automaton to walk.

Types and aliases

namespace RegExp.RegExpSearch

DFA

Defined as: type DFA = box struct { ...fields... }

The scanner: the automaton walked over sets of threads, so that reading a byte costs one table lookup. Where the text below says "the scanner" it means a DFA, and "the automaton" an NFA.

A state is a set of threads. Reading a byte carries every thread whose node admits it to the node that node leads to, and the threads reachable from there without reading anything join them; what comes out is again a state. States and the transitions between them are worked out as the input calls for them and kept, so that a byte read again in the same state costs one lookup.

A thread is width numbers: the node it stands at, then the rounds it has counted for each special quantifier. A state holds its threads ordered by node, so that two sets holding the same threads are one state.

The scanner reports where a match begins and ends and nothing else. The groups a match captured are read off afterwards by the automaton, over the stretch the match covers.

field nfa

Type: RegExp.RegExpNFA::NFA

field width

Type: Std::I64

field threads

Type: Std::Array Std::I64

field bounds

Type: Std::Array Std::I64

field ordered

Type: Std::Array Std::I64

field transitions

Type: Std::Array Std::I64

field accepts

Type: Std::Array Std::Bool

field accepts_at_end

Type: Std::Array Std::I64

field untaken

Type: Std::Array Std::I64

1 where it does, 0 where it does not, -1 until asked

field interior

Type: Std::I64

field first_bytes

Type: Std::Array Std::U64

field absorbing

Type: Std::Array Std::U8

field full

Type: Std::Bool

2 where it does not, 0 where it has not been worked out

Walk

Defined as: type Walk = box struct { ...fields... }

The threads an automaton is walked with, and what each of them has captured.

A thread stands at a node, has captured a beginning and an end for each group, and has counted rounds for each special quantifier. All three are numbers, and the threads share three arrays of them, so that carrying a thread forward writes numbers and allocates nothing. Gathering what one thread holds into a value of its own would put an array behind every thread and have it copied once per node the thread reaches.

Thread t stands at nodes.@(t), has captured the slot_width numbers of slots beginning at t * slot_width - a beginning and an end to a group, the whole match first - and has counted the count_width numbers of counts beginning at t * count_width.

field slot_width

Type: Std::I64

field count_width

Type: Std::I64

field nodes

Type: Std::Array Std::I64

field slots

Type: Std::Array Std::I64

field counts

Type: Std::Array Std::I64

field pending

Type: Std::Array Std::I64

The threads whose empty-string transitions are still to be followed, taken from the end.

field at_step

Type: Std::Array Std::I64

Per node, the step at which a thread took it, so that nothing has to be cleared between positions.

field counts_at_step

Type: Std::Array (Std::Array Std::I64)

Per node, the rounds counted by the threads that took it at that step, since two threads standing at one node having counted differently do not have the same future.

field step

Type: Std::I64

How many bytes the walk has read, which tells the marks left at one position from those left at another.

Traits and aliases

Trait implementations