automaton

package
v0.0.0-...-53ff736 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 27, 2024 License: Apache-2.0 Imports: 11 Imported by: 1

Documentation

Index

Constants

View Source 
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 

func GetCommonSuffixBytesRef(a *Automaton) []byte

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 GetSingletonAutomaton(a *Automaton) ([]int, error)

func IsEmptyAutomaton 

func IsEmptyAutomaton(a *Automaton) bool

IsEmptyAutomaton Returns true if the given automaton accepts no strings.

func IsFiniteAutomaton 

func IsFiniteAutomaton(a *Automaton) *atomic.Bool

func IsTotalAutomaton 

func IsTotalAutomaton(a *Automaton) bool

IsTotalAutomaton Returns true if the given automaton accepts all strings. The automaton must be minimized.

func IsTotalAutomatonRange 

func IsTotalAutomatonRange(a *Automaton, minAlphabet, maxAlphabet int) bool

IsTotalAutomatonRange Returns true if the given automaton accepts all strings for the specified min/max range of the alphabet. The automaton must be minimized.

func Max 

func Max[T int](a, b T) T

func Min 

func Min[T int](a, b T) T

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 

func DeterminizeAutomaton(a *Automaton, workLimit int) *Automaton

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 NewAutomatonV1(numStates, numTransitions int) *Automaton

func RemoveDeadStates 

func RemoveDeadStates(a *Automaton) *Automaton

func (*Automaton) AddEpsilon 

func (r *Automaton) AddEpsilon(source, dest int)

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 

func (r *Automaton) AddTransition(source, dest, min, max int) error

AddTransition Add a new transition with the specified source, dest, min, max.

func (*Automaton) AddTransitionLabel 

func (r *Automaton) AddTransitionLabel(source, dest, label int) error

AddTransitionLabel Add a new transition with min = max = label.

func (*Automaton) Copy 

func (r *Automaton) Copy(other *Automaton)

Copy Copies over all states/transitions from other. The states numbers are sequentially assigned (appended).

func (*Automaton) CreateState 

func (r *Automaton) CreateState() int

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 

func (r *Automaton) GetNumStates() int

GetNumStates How many states this automaton has.

func (*Automaton) GetNumTransitions 

func (r *Automaton) GetNumTransitions() int

GetNumTransitions How many transitions this automaton has.

func (*Automaton) GetNumTransitionsWithState 

func (r *Automaton) GetNumTransitionsWithState(state int) int

GetNumTransitionsWithState How many transitions this state has.

func (*Automaton) GetStartPoints 

func (r *Automaton) GetStartPoints() []int

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) IsAccept 

func (r *Automaton) IsAccept(state int) bool

IsAccept Returns true if this state is an accept state.

func (*Automaton) IsDeterministic 

func (r *Automaton) IsDeterministic() bool

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.

func (*Automaton) SetAccept 

func (r *Automaton) SetAccept(state int, accept bool)

SetAccept Set or clear this state as an accept state.

func (*Automaton) Step 

func (r *Automaton) Step(state, label int) int

Step Performs lookup in transitions, assuming determinism. Params: state – starting state 

label – codepoint to look up

Returns: destination state, -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 NewBuilderV1(numStates, numTransitions int) *Builder

func NewNewBuilder 

func NewNewBuilder() *Builder

func (*Builder) AddTransition 

func (r *Builder) AddTransition(source, dest, min, max int)

func (*Builder) AddTransitionLabel 

func (r *Builder) AddTransitionLabel(source, dest, label int)

func (*Builder) CopyStates 

func (r *Builder) CopyStates(other *Automaton)

CopyStates Copies over all states from other.

func (*Builder) CreateState 

func (r *Builder) CreateState() int

func (*Builder) Finish 

func (r *Builder) Finish() *Automaton

func (*Builder) IsAccept 

func (r *Builder) IsAccept(state int) bool

func (*Builder) SetAccept 

func (r *Builder) SetAccept(state int, accept bool)

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 IntSet 

type IntSet interface {
	GetArray() []int

	Size() int

	Hash() int64
}

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

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.