Documentation ¶
Index ¶
- Constants
- func GetCommonSuffixBytesRef(a *Automaton) []byte
- func GetSingletonAutomaton(a *Automaton) ([]int, error)
- func IsEmptyAutomaton(a *Automaton) bool
- func IsFiniteAutomaton(a *Automaton) *atomic.Bool
- func IsTotalAutomaton(a *Automaton) bool
- func IsTotalAutomatonRange(a *Automaton, minAlphabet, maxAlphabet int) bool
- func Max[T int](a, b T) T
- func Min[T int](a, b T) T
- type Automaton
- func (r *Automaton) AddEpsilon(source, dest int)
- func (r *Automaton) AddTransition(source, dest, min, max int) error
- func (r *Automaton) AddTransitionLabel(source, dest, label int) error
- func (r *Automaton) Copy(other *Automaton)
- func (r *Automaton) CreateState() int
- func (r *Automaton) GetNextTransition(t *Transition)
- func (r *Automaton) GetNumStates() int
- func (r *Automaton) GetNumTransitions() int
- func (r *Automaton) GetNumTransitionsWithState(state int) int
- func (r *Automaton) GetStartPoints() []int
- func (r *Automaton) InitTransition(state int, t *Transition) int
- func (r *Automaton) IsAccept(state int) bool
- func (r *Automaton) IsDeterministic() bool
- func (r *Automaton) Next(transition *Transition, label int) int
- func (r *Automaton) SetAccept(state int, accept bool)
- func (r *Automaton) Step(state, label int) int
- type Builder
- func (r *Builder) AddTransition(source, dest, min, max int)
- func (r *Builder) AddTransitionLabel(source, dest, label int)
- func (r *Builder) CopyStates(other *Automaton)
- func (r *Builder) CreateState() int
- func (r *Builder) Finish() *Automaton
- func (r *Builder) IsAccept(state int) bool
- func (r *Builder) SetAccept(state int, accept bool)
- type ByteRunAutomaton
- type CompiledAutomaton
- type FrozenIntSet
- type IntSet
- type RunAutomaton
- type Transition
Constants ¶
const ( AUTOMATON_TYPE_NONE = iota // Automaton that accepts no strings. AUTOMATON_TYPE_ALL // Automaton that accepts all possible strings. AUTOMATON_TYPE_SINGLE // Automaton that accepts only a single fixed string. AUTOMATON_TYPE_NORMAL // Catch-all for any other automata. )
Variables ¶
This section is empty.
Functions ¶
func GetCommonSuffixBytesRef ¶
GetCommonSuffixBytesRef Returns the longest BytesRef that is a suffix of all accepted strings. Worst case complexity: quadratic with the number of states+transitions. Returns: common suffix, which can be an empty (length 0) BytesRef (never null)
func GetSingletonAutomaton ¶
func IsEmptyAutomaton ¶
IsEmptyAutomaton Returns true if the given automaton accepts no strings.
func IsFiniteAutomaton ¶
func IsTotalAutomaton ¶
IsTotalAutomaton Returns true if the given automaton accepts all strings. The automaton must be minimized.
func IsTotalAutomatonRange ¶
IsTotalAutomatonRange Returns true if the given automaton accepts all strings for the specified min/max range of the alphabet. The automaton must be minimized.
Types ¶
type Automaton ¶
type Automaton struct {
// contains filtered or unexported fields
}
Automaton Represents an automaton and all its states and transitions. States are integers and must be created using createState. Mark a state as an accept state using setAccept. Add transitions using addTransition. Each state must have all of its transitions added at once; if this is too restrictive then use Automaton.Builder instead. State 0 is always the initial state. Once a state is finished, either because you've starting adding transitions to another state or you call finishState, then that states transitions are sorted (first by min, then max, then dest) and reduced (transitions with adjacent labels going to the same dest are combined).
func DeterminizeAutomaton ¶
DeterminizeAutomaton Determinizes the given automaton. Worst case complexity: exponential in number of states. Params: workLimit – Maximum amount of "work" that the powerset construction will spend before throwing
TooComplexToDeterminizeException. Higher numbers allow this operation to consume more memory and CPU but allow more complex automatons. Use DEFAULT_DETERMINIZE_WORK_LIMIT as a decent default if you don't otherwise know what to specify.
Throws: TooComplexToDeterminizeException – if determinizing requires more than workLimit "effort"
func MakeAnyString ¶
func MakeAnyString() *Automaton
func NewAutomaton ¶
func NewAutomaton() *Automaton
func NewAutomatonV1 ¶
func RemoveDeadStates ¶
func (*Automaton) AddEpsilon ¶
AddEpsilon Add a [virtual] epsilon transition between source and dest. Dest state must already have all transitions added because this method simply copies those same transitions over to source.
func (*Automaton) AddTransition ¶
AddTransition Add a new transition with the specified source, dest, min, max.
func (*Automaton) AddTransitionLabel ¶
AddTransitionLabel Add a new transition with min = max = label.
func (*Automaton) Copy ¶
Copy Copies over all states/transitions from other. The states numbers are sequentially assigned (appended).
func (*Automaton) CreateState ¶
CreateState Create a new state.
func (*Automaton) GetNextTransition ¶
func (r *Automaton) GetNextTransition(t *Transition)
GetNextTransition Iterate to the next transition after the provided one
func (*Automaton) GetNumStates ¶
GetNumStates How many states this automaton has.
func (*Automaton) GetNumTransitions ¶
GetNumTransitions How many transitions this automaton has.
func (*Automaton) GetNumTransitionsWithState ¶
GetNumTransitionsWithState How many transitions this state has.
func (*Automaton) GetStartPoints ¶
Returns sorted array of all interval start points.
func (*Automaton) InitTransition ¶
func (r *Automaton) InitTransition(state int, t *Transition) int
InitTransition Initialize the provided Transition to iterate through all transitions leaving the specified state. You must call GetNextTransition to get each transition. Returns the number of transitions leaving this state.
func (*Automaton) IsDeterministic ¶
IsDeterministic Returns true if this automaton is deterministic (for ever state there is only one transition for each label).
func (*Automaton) Next ¶
func (r *Automaton) Next(transition *Transition, label int) int
Next Looks for the next transition that matches the provided label, assuming determinism. This method is similar to step(int, int) but is used more efficiently when iterating over multiple transitions from the same source state. It keeps the latest reached transition index in transition.transitionUpto so the next call to this method can continue from there instead of restarting from the first transition.
transition: The transition to start the lookup from (inclusive, using its Transition.source and Transition.transitionUpto). It is updated with the matched transition; or with Transition.dest = -1 if no match.
label: The codepoint to look up.
Returns: The destination state; or -1 if no matching outgoing transition.
type Builder ¶
type Builder struct {
// contains filtered or unexported fields
}
Builder Records new states and transitions and then finish creates the Automaton. Use this when you cannot create the Automaton directly because it's too restrictive to have to add all transitions leaving each state at once.
func NewBuilderV1 ¶
func NewNewBuilder ¶
func NewNewBuilder() *Builder
func (*Builder) AddTransition ¶
func (*Builder) AddTransitionLabel ¶
func (*Builder) CopyStates ¶
CopyStates Copies over all states from other.
func (*Builder) CreateState ¶
type ByteRunAutomaton ¶
type ByteRunAutomaton struct {
*RunAutomaton
}
ByteRunAutomaton Automaton representation for matching UTF-8 byte[].
func NewByteRunAutomaton ¶
func NewByteRunAutomaton(a *Automaton) *ByteRunAutomaton
func NewByteRunAutomatonV1 ¶
func NewByteRunAutomatonV1(a *Automaton, isBinary bool, determinizeWorkLimit int) *ByteRunAutomaton
func (*ByteRunAutomaton) Run ¶
func (r *ByteRunAutomaton) Run(s []byte) bool
Run Returns true if the given byte array is accepted by this automaton
type CompiledAutomaton ¶
type CompiledAutomaton struct {
// contains filtered or unexported fields
}
CompiledAutomaton Immutable class holding compiled details for a given Automaton. The Automaton is deterministic, must not have dead states but is not necessarily minimal.
func NewCompiledAutomaton ¶
func NewCompiledAutomaton(automaton *Automaton, finite *atomic.Bool, simplify bool, determinizeWorkLimit int, isBinary bool) *CompiledAutomaton
NewCompiledAutomaton Create this. If finite is null, we use Operations.isFinite to determine whether it is finite. If simplify is true, we run possibly expensive operations to determine if the automaton is one the cases in CompiledAutomaton.AUTOMATON_TYPE. If simplify requires determinizing the automaton then at most determinizeWorkLimit effort will be spent. Any more than that will cause a TooComplexToDeterminizeException.
func (*CompiledAutomaton) RunAutomaton ¶
func (r *CompiledAutomaton) RunAutomaton() *ByteRunAutomaton
func (*CompiledAutomaton) Term ¶
func (r *CompiledAutomaton) Term() []byte
func (*CompiledAutomaton) Type ¶
func (r *CompiledAutomaton) Type() int
type FrozenIntSet ¶
type FrozenIntSet struct {
// contains filtered or unexported fields
}
func NewFrozenIntSet ¶
func NewFrozenIntSet(values []int, state int, hashCode int64) *FrozenIntSet
func (*FrozenIntSet) GetArray ¶
func (f *FrozenIntSet) GetArray() []int
func (*FrozenIntSet) Hash ¶
func (f *FrozenIntSet) Hash() int64
func (*FrozenIntSet) Size ¶
func (f *FrozenIntSet) Size() int
type RunAutomaton ¶
type RunAutomaton struct {
// contains filtered or unexported fields
}
RunAutomaton Finite-state automaton with fast run operation. The initial state is always 0.
func NewRunAutomatonV1 ¶
func NewRunAutomatonV1(a *Automaton, alphabetSize, determinizeWorkLimit int) *RunAutomaton
func (*RunAutomaton) GetCharClass ¶
func (r *RunAutomaton) GetCharClass(c int) int
GetCharClass Gets character class of given codepoint
func (*RunAutomaton) GetSize ¶
func (r *RunAutomaton) GetSize() int
GetSize Returns number of states in automaton.
func (*RunAutomaton) IsAccept ¶
func (r *RunAutomaton) IsAccept(state int) bool
IsAccept Returns acceptance status for given state.
func (*RunAutomaton) Step ¶
func (r *RunAutomaton) Step(state int, c int) int
Step Returns the state obtained by reading the given char from the given state. Returns -1 if not obtaining any such state. (If the original Automaton had no dead states, -1 is returned here if and only if a dead state is entered in an equivalent automaton with a total transition function.)
type Transition ¶
type Transition struct { // Source state. Source int // Destination state. Dest int // Minimum accepted label (inclusive). Min int // Maximum accepted label (inclusive). Max int // Remembers where we are in the iteration; init to -1 to provoke exception if nextTransition is // called without first initTransition. TransitionUpto int }
Transition Holds one transition from an Automaton. This is typically used temporarily when iterating through transitions by invoking Automaton.initTransition and Automaton.getNextTransition.
func NewTransition ¶
func NewTransition() *Transition