starfree

Documentation

Overview

Package starfree provides validation and FM-index search for star-free regular expressions.

Star-free languages

A language is star-free if it can be expressed by a regular expression that uses only:

• Literal characters (a, b, …)
• Concatenation (ab)
• Union / alternation (a|b)
• Complement (¬a) [handled by the aperiodicity equivalence]
• Optional (a?) — syntactic sugar for a|ε
• Bounded repetition (a{n,m}) — finite union of concatenations

and that does NOT use:

• Kleene star (a*) — unbounded zero-or-more
• One-or-more (a+) — unbounded one-or-more
• Unbounded repetition (a{n,}) — equivalent to Kleene star

Star-free languages are exactly the aperiodic regular languages (those recognised by counter-free automata).

Search

Search translates the star-free pattern into a set of SA intervals on the FM-index using a recursive backward-search strategy: sub-expressions are evaluated right-to-left, accumulating a (potentially merged) list of non-overlapping intervals in the suffix array.

Index

• func Check(pattern string) error
• type Interval
  • func (iv Interval) Size() int
• type SearchResult
  • func Search(idx *fmindex.Index, pattern string, limit int) (*SearchResult, error)
  • func (sr *SearchResult) Positions(idx *fmindex.Index) []int
• type UnsupportedError
  • func (e *UnsupportedError) Error() string
• type ViolationError
  • func (e *ViolationError) Error() string

Functions

func Check

func Check(pattern string) error

Check returns nil when pattern is a valid star-free regular expression. It returns a *ViolationError if the pattern contains Kleene star, one-or-more, or an unbounded repetition; a *UnsupportedError for constructs that cannot be represented by backward search (such as position anchors); or a wrapped *syntax.Error for invalid syntax.

Types

type Interval

type Interval struct {
	Lo, Hi int
}

Interval is a half-open SA range [Lo, Hi).

func (Interval) Size

func (iv Interval) Size() int

Size returns the number of matches represented by this interval.

type SearchResult

type SearchResult struct {
	// Intervals contains the (merged, sorted) SA intervals matching the pattern.
	// All positions in these intervals are valid match start positions.
	Intervals []Interval
	// TotalCount is the total number of matches before any limit was applied.
	TotalCount int
	// Truncated is true when TotalCount > the requested limit.
	Truncated bool
}

SearchResult holds the outcome of a search.

func Search

func Search(idx *fmindex.Index, pattern string, limit int) (*SearchResult, error)

Search executes a star-free regex search on the FM-index.

pattern must be a valid star-free regular expression (see Check). limit controls the maximum number of match positions returned; ≤0 means no limit.

Returns a *ViolationError if pattern violates star-free constraints, a *UnsupportedError for unsupported regex constructs, or a wrapped *syntax.Error for invalid syntax.

func (*SearchResult) Positions

func (sr *SearchResult) Positions(idx *fmindex.Index) []int

Positions returns the text positions for all intervals in the result using the provided index.

type UnsupportedError

type UnsupportedError struct {
	Op      string // human-readable name of the unsupported operator
	SubExpr string // string form of the offending sub-expression
}

UnsupportedError describes a regex construct that is valid syntax but not supported by this FM-index based matcher.

func (*UnsupportedError) Error

func (e *UnsupportedError) Error() string

type ViolationError

type ViolationError struct {
	Op      string // human-readable name of the offending operator
	SubExpr string // string form of the offending sub-expression
}

ViolationError describes a star-free constraint violation within a pattern.

func (*ViolationError) Error

func (e *ViolationError) Error() string