literal

func (*Extractor) ExtractInner ¶

func (e *Extractor) ExtractInner(re *syntax.Regexp) *Seq

ExtractInner extracts inner literals (not necessarily prefix/suffix). Useful for patterns like ".*foo.*" where foo must appear somewhere.

This is a simpler extraction that just looks for any required literals in the pattern, regardless of position.

Examples:

".*foo.*"           → ["foo"]
".*(hello|world).*" → ["hello", "world"]
"prefix.*middle.*suffix" → ["prefix", "middle", "suffix"] (first found)

Returns empty Seq if no inner literals can be extracted.

package main

import (
	"fmt"
	"regexp/syntax"

	"github.com/donge/coregex/literal"
)

func main() {
	// Pattern: .*error.*
	// Inner literal should be "error"
	re, _ := syntax.Parse(".*error.*", syntax.Perl)

	extractor := literal.New(literal.DefaultConfig())
	inner := extractor.ExtractInner(re)

	fmt.Printf("Found %d inner literal(s):\n", inner.Len())
	for i := 0; i < inner.Len(); i++ {
		lit := inner.Get(i)
		fmt.Printf("  - %q\n", string(lit.Bytes))
	}

}

Output:
Found 1 inner literal(s):
  - "error"

func (*Extractor) ExtractInnerForReverseSearch ¶

func (e *Extractor) ExtractInnerForReverseSearch(re *syntax.Regexp) *InnerLiteralInfo

ExtractInnerForReverseSearch extracts inner literals suitable for ReverseInner strategy. Returns nil if no suitable inner literal found (only prefix/suffix available).

"Inner" means:

• NOT at the very start (otherwise use prefix strategy)
• NOT at the very end (otherwise use suffix strategy)
• Has wildcards/repetitions both before AND after

This is specifically for patterns like:

• `ERROR.*connection.*timeout` → inner literal: "connection"
• `func.*Error.*return` → inner literal: "Error"
• `prefix.*middle.*suffix` → inner literal: "middle"

Algorithm:

1. Pattern must be OpConcat (concatenation of parts)
2. Find the first literal that is: a. NOT at position 0 (has content before) b. NOT at last position (has content after) c. Both before and after have wildcards (.*|.+|.?)
3. Prefer longer literals

Returns nil if:

• Not a concat pattern
• Only prefix or suffix literals available
• No wildcards before/after literals

Example:

// Pattern: `ERROR.*connection.*timeout`
re, _ := syntax.Parse(`ERROR.*connection.*timeout`, syntax.Perl)
extractor := literal.New(literal.DefaultConfig())
innerInfo := extractor.ExtractInnerForReverseSearch(re)
// innerInfo.Literals = ["connection"]
// innerInfo.InnerIdx = 2 (position in concat)

func (*Extractor) ExtractPrefixes ¶

func (e *Extractor) ExtractPrefixes(re *syntax.Regexp) *Seq

ExtractPrefixes extracts prefix literals from the regex. Returns literals that must appear at the start of any match.

Handles these syntax.Op types:

• OpLiteral: direct literal string → returns it
• OpConcat: take first sub-expression
• OpAlternate: union of all alternatives (e.g., (foo|bar) → ["foo", "bar"])
• OpCharClass: expand small classes (e.g., [abc] → ["a", "b", "c"])
• OpCapture: ignore capture group, extract from sub-expression
• OpStar/OpQuest/OpPlus: repetition makes prefix optional → return empty

Examples:

"hello"         → ["hello"]
"(foo|bar)"     → ["foo", "bar"]
"[abc]test"     → ["atest", "btest", "ctest"]
"hello.*world"  → ["hello"]
".*foo"         → [] (no prefix requirement)

Returns empty Seq if no prefix literals can be extracted.

package main

import (
	"fmt"
	"regexp/syntax"

	"github.com/donge/coregex/literal"
)

func main() {
	// Parse a simple pattern
	re, _ := syntax.Parse("hello", syntax.Perl)

	// Create extractor with default config
	extractor := literal.New(literal.DefaultConfig())

	// Extract prefixes
	prefixes := extractor.ExtractPrefixes(re)

	// Print results
	fmt.Printf("Found %d prefix(es):\n", prefixes.Len())
	for i := 0; i < prefixes.Len(); i++ {
		lit := prefixes.Get(i)
		fmt.Printf("  - %q\n", string(lit.Bytes))
	}

}

Output:
Found 1 prefix(es):
  - "hello"

package main

import (
	"fmt"
	"regexp/syntax"

	"github.com/donge/coregex/literal"
)

func main() {
	// Pattern with alternations (using distinct prefixes to avoid parser optimization)
	re, _ := syntax.Parse("(apple|banana|cherry)", syntax.Perl)

	extractor := literal.New(literal.DefaultConfig())
	prefixes := extractor.ExtractPrefixes(re)

	fmt.Printf("Found %d prefix(es):\n", prefixes.Len())
	for i := 0; i < prefixes.Len(); i++ {
		lit := prefixes.Get(i)
		fmt.Printf("  - %q\n", string(lit.Bytes))
	}

}

Output:
Found 3 prefix(es):
  - "apple"
  - "banana"
  - "cherry"

package main

import (
	"fmt"
	"regexp/syntax"

	"github.com/donge/coregex/literal"
)

func main() {
	// Small character class: [abc]
	re, _ := syntax.Parse("[abc]", syntax.Perl)

	extractor := literal.New(literal.DefaultConfig())
	prefixes := extractor.ExtractPrefixes(re)

	fmt.Printf("Found %d prefix(es):\n", prefixes.Len())
	for i := 0; i < prefixes.Len(); i++ {
		lit := prefixes.Get(i)
		fmt.Printf("  - %q\n", string(lit.Bytes))
	}

}

Output:
Found 3 prefix(es):
  - "a"
  - "b"
  - "c"

package main

import (
	"fmt"
	"regexp/syntax"

	"github.com/donge/coregex/literal"
)

func main() {
	// HTTP method regex (using methods with distinct first letters to avoid parser optimization)
	re, _ := syntax.Parse("(GET|HEAD|DELETE|OPTIONS)", syntax.Perl)

	extractor := literal.New(literal.DefaultConfig())
	prefixes := extractor.ExtractPrefixes(re)

	fmt.Printf("HTTP methods extracted: %d\n", prefixes.Len())
	fmt.Println("Can use these for prefilter optimization:")
	for i := 0; i < prefixes.Len(); i++ {
		lit := prefixes.Get(i)
		fmt.Printf("  - %q\n", string(lit.Bytes))
	}

}

Output:
HTTP methods extracted: 4
Can use these for prefilter optimization:
  - "GET"
  - "HEAD"
  - "DELETE"
  - "OPTIONS"

package main

import (
	"fmt"
	"regexp/syntax"

	"github.com/donge/coregex/literal"
)

func main() {
	// Pattern starts with wildcard: .*error
	re, _ := syntax.Parse(".*error", syntax.Perl)

	extractor := literal.New(literal.DefaultConfig())
	prefixes := extractor.ExtractPrefixes(re)

	if prefixes.IsEmpty() {
		fmt.Println("No prefix literals found (pattern starts with wildcard)")
	} else {
		fmt.Printf("Found %d prefix(es)\n", prefixes.Len())
	}

}

Output:
No prefix literals found (pattern starts with wildcard)

func (*Extractor) ExtractSuffixes ¶

func (e *Extractor) ExtractSuffixes(re *syntax.Regexp) *Seq

ExtractSuffixes extracts suffix literals from the regex. Returns literals that must appear at the end of any match.

Algorithm is similar to ExtractPrefixes but analyzes from the end.

Examples:

"world"         → ["world"]
"(foo|bar)"     → ["foo", "bar"]
"test[xyz]"     → ["testx", "testy", "testz"]
"hello.*world"  → ["world"]
"foo.*"         → [] (no suffix requirement)

Returns empty Seq if no suffix literals can be extracted.

package main

import (
	"fmt"
	"regexp/syntax"

	"github.com/donge/coregex/literal"
)

func main() {
	// Pattern: hello.*world
	// Suffix should be "world"
	re, _ := syntax.Parse("hello.*world", syntax.Perl)

	extractor := literal.New(literal.DefaultConfig())
	suffixes := extractor.ExtractSuffixes(re)

	fmt.Printf("Found %d suffix(es):\n", suffixes.Len())
	for i := 0; i < suffixes.Len(); i++ {
		lit := suffixes.Get(i)
		fmt.Printf("  - %q\n", string(lit.Bytes))
	}

}

Output:
Found 1 suffix(es):
  - "world"

func (Literal) Len ¶

func (l Literal) Len() int

Len returns the length of the literal in bytes.

Example:

lit := literal.NewLiteral([]byte("hello"), true)
fmt.Println(lit.Len()) // Output: 5

func (Literal) String ¶

func (l Literal) String() string

String returns a string representation of the literal for debugging purposes. Format: "literal{bytes, complete=true/false}"

Example:

lit := literal.NewLiteral([]byte("test"), true)
fmt.Println(lit.String()) // Output: literal{test, complete=true}

func (*Seq) AllComplete ¶

func (s *Seq) AllComplete() bool

AllComplete returns true if all literals in the sequence are complete. Complete literals represent full matches - no regex engine verification needed.

This is used to enable the "literal engine bypass" optimization: when all extracted literals are complete, we can skip DFA construction and use just the prefilter (Teddy/Memmem) for searching.

Example:

// For pattern "(foo|bar|baz)", literals are complete
literals := extractor.ExtractPrefixes(re)
if literals.AllComplete() {
    // Use prefilter directly, skip DFA
}

func (*Seq) Clone ¶

func (s *Seq) Clone() *Seq

Clone returns a deep copy of the sequence. All literals and their byte slices are duplicated.

Example:

original := literal.NewSeq(literal.NewLiteral([]byte("test"), true))
clone := original.Clone()
clone.Get(0).Bytes[0] = 'X' // Modifying clone doesn't affect original
fmt.Println(string(original.Get(0).Bytes)) // Output: test

package main

import (
	"fmt"

	"github.com/donge/coregex/literal"
)

func main() {
	original := literal.NewSeq(
		literal.NewLiteral([]byte("test"), true),
	)

	clone := original.Clone()

	// Modify clone
	clone.Minimize() // This won't affect original

	fmt.Printf("Original length: %d\n", original.Len())
	fmt.Printf("Clone length: %d\n", clone.Len())

}

Output:
Original length: 1
Clone length: 1

func (*Seq) CrossForward ¶

func (s *Seq) CrossForward(other *Seq)

CrossForward computes the cross-product of s with other, appending other's bytes to each literal in s. Only exact (Complete) literals in s are extended; inexact literals are kept as-is because they already represent truncated prefixes that cannot be meaningfully extended.

The result is Complete only if both the source literal and the other literal are Complete. This preserves the semantic that Complete means the literal captures the entire pattern up to this point.

If either s or other is empty, s is left unchanged.

Example:

s = ["ab", "cd"] (complete)
other = ["x", "y"] (complete)
s.CrossForward(other) → ["abx", "aby", "cdx", "cdy"]

func (*Seq) Dedup ¶

func (s *Seq) Dedup()

Dedup removes duplicate literals from the sequence, keeping the first occurrence. Two literals are considered duplicates if their byte content is identical, regardless of their Complete flag. When duplicates exist, the first occurrence is kept (which preserves the most accurate Complete status from earlier processing).

Example:

s = ["abc", "def", "abc", "ghi"]
s.Dedup() → ["abc", "def", "ghi"]

func (*Seq) Get ¶

func (s *Seq) Get(i int) Literal

Get returns the literal at the specified index. Panics if index is out of bounds.

Example:

seq := literal.NewSeq(
    literal.NewLiteral([]byte("first"), true),
    literal.NewLiteral([]byte("second"), true),
)
fmt.Println(string(seq.Get(0).Bytes)) // Output: first
fmt.Println(string(seq.Get(1).Bytes)) // Output: second

func (*Seq) IsEmpty ¶

func (s *Seq) IsEmpty() bool

IsEmpty returns true if the sequence has no literals.

Example:

empty := literal.NewSeq()
fmt.Println(empty.IsEmpty()) // Output: true

nonempty := literal.NewSeq(literal.NewLiteral([]byte("x"), true))
fmt.Println(nonempty.IsEmpty()) // Output: false

package main

import (
	"fmt"

	"github.com/donge/coregex/literal"
)

func main() {
	empty := literal.NewSeq()
	nonempty := literal.NewSeq(literal.NewLiteral([]byte("x"), true))

	fmt.Printf("Empty sequence: %v\n", empty.IsEmpty())
	fmt.Printf("Non-empty sequence: %v\n", nonempty.IsEmpty())

}

Output:
Empty sequence: true
Non-empty sequence: false

func (*Seq) IsFinite ¶

func (s *Seq) IsFinite() bool

IsFinite returns true if the sequence represents a finite language. A sequence is finite if it has at least one literal.

In regex theory, a finite language is one with a bounded number of strings. For our purposes, any non-empty literal set represents a finite language.

Example:

seq := literal.NewSeq(literal.NewLiteral([]byte("hello"), true))
fmt.Println(seq.IsFinite()) // Output: true

empty := literal.NewSeq()
fmt.Println(empty.IsFinite()) // Output: false

package main

import (
	"fmt"

	"github.com/donge/coregex/literal"
)

func main() {
	// A sequence with literals represents a finite language
	finite := literal.NewSeq(literal.NewLiteral([]byte("test"), true))

	// Empty sequence represents infinite/empty language
	empty := literal.NewSeq()

	fmt.Printf("Finite: %v\n", finite.IsFinite())
	fmt.Printf("Empty: %v\n", empty.IsFinite())

}

Output:
Finite: true
Empty: false

func (*Seq) IsPartialCoverage ¶

func (s *Seq) IsPartialCoverage() bool

IsPartialCoverage returns true if the literal set doesn't cover all alternation branches (due to overflow truncation). A partial-coverage prefilter cannot be used as a correctness gate in candidate loops — it would miss branches whose literals were not extracted. Rust avoids this by integrating prefilter as skip-ahead inside PikeVM, not as an external candidate loop.

func (*Seq) KeepFirstBytes ¶

func (s *Seq) KeepFirstBytes(n int)

KeepFirstBytes truncates all literals to at most n bytes. Truncated literals are marked as incomplete (Complete = false) since they no longer represent the full extracted sequence.

This is used for overflow handling when cross-product expansion exceeds limits: truncating to 4 bytes (Teddy fingerprint size) preserves prefilter effectiveness while bounding memory usage.

Example:

s = ["abcdef", "xy"] (complete)
s.KeepFirstBytes(4) → ["abcd" (incomplete), "xy" (complete)]

func (*Seq) Len ¶

func (s *Seq) Len() int

Len returns the number of literals in the sequence.

Example:

seq := literal.NewSeq(
    literal.NewLiteral([]byte("foo"), true),
    literal.NewLiteral([]byte("bar"), true),
)
fmt.Println(seq.Len()) // Output: 2

func (*Seq) LongestCommonPrefix ¶

func (s *Seq) LongestCommonPrefix() []byte

LongestCommonPrefix returns the longest common prefix of all literals in the sequence. If the sequence is empty or has no common prefix, returns an empty slice.

Algorithm:

1. If sequence is empty, return empty slice
2. Take first literal as candidate prefix
3. For each other literal: - Find common prefix with current candidate - Update candidate to this shorter prefix
4. Return final prefix

Time complexity: O(n * m) where n = number of literals, m = length of result prefix

Example:

seq := literal.NewSeq(
    literal.NewLiteral([]byte("hello"), true),
    literal.NewLiteral([]byte("help"), true),
    literal.NewLiteral([]byte("hero"), true),
)
prefix := seq.LongestCommonPrefix()
fmt.Println(string(prefix)) // Output: he

Example with no common prefix:

seq := literal.NewSeq(
    literal.NewLiteral([]byte("abc"), true),
    literal.NewLiteral([]byte("def"), true),
)
prefix := seq.LongestCommonPrefix()
fmt.Println(len(prefix)) // Output: 0

package main

import (
	"fmt"

	"github.com/donge/coregex/literal"
)

func main() {
	seq := literal.NewSeq(
		literal.NewLiteral([]byte("hello"), true),
		literal.NewLiteral([]byte("help"), true),
		literal.NewLiteral([]byte("hero"), true),
	)

	prefix := seq.LongestCommonPrefix()
	fmt.Printf("Common prefix: %s\n", prefix)

}

Output:
Common prefix: he

package main

import (
	"fmt"

	"github.com/donge/coregex/literal"
)

func main() {
	seq := literal.NewSeq(
		literal.NewLiteral([]byte("abc"), true),
		literal.NewLiteral([]byte("def"), true),
	)

	prefix := seq.LongestCommonPrefix()
	fmt.Printf("Common prefix length: %d\n", len(prefix))

}

Output:
Common prefix length: 0

func (*Seq) LongestCommonSuffix ¶

func (s *Seq) LongestCommonSuffix() []byte

LongestCommonSuffix returns the longest common suffix of all literals in the sequence. If the sequence is empty or has no common suffix, returns an empty slice.

Algorithm:

1. Reverse all literals
2. Find longest common prefix of reversed literals
3. Reverse the result

Time complexity: O(n * m) where n = number of literals, m = length of result suffix

Example:

seq := literal.NewSeq(
    literal.NewLiteral([]byte("cat"), true),
    literal.NewLiteral([]byte("bat"), true),
    literal.NewLiteral([]byte("rat"), true),
)
suffix := seq.LongestCommonSuffix()
fmt.Println(string(suffix)) // Output: at

Example with no common suffix:

seq := literal.NewSeq(
    literal.NewLiteral([]byte("abc"), true),
    literal.NewLiteral([]byte("def"), true),
)
suffix := seq.LongestCommonSuffix()
fmt.Println(len(suffix)) // Output: 0

package main

import (
	"fmt"

	"github.com/donge/coregex/literal"
)

func main() {
	seq := literal.NewSeq(
		literal.NewLiteral([]byte("cat"), true),
		literal.NewLiteral([]byte("bat"), true),
		literal.NewLiteral([]byte("rat"), true),
	)

	suffix := seq.LongestCommonSuffix()
	fmt.Printf("Common suffix: %s\n", suffix)

}

Output:
Common suffix: at

func (*Seq) Minimize ¶

func (s *Seq) Minimize()

Minimize removes redundant literals from the sequence.

For prefix matching, a literal L is redundant if there exists a shorter literal S that is a prefix of L. For example, in ["foo", "foobar"], "foo" makes "foobar" redundant because any string containing "foobar" also contains "foo".

Algorithm:

1. Sort literals by length (shortest first)
2. For each literal L: - Check if any shorter literal S is a prefix of L - If yes, L is redundant (skip it) - If no, keep L

Time complexity: O(n² * m) where n = number of literals, m = average literal length

Example:

seq := literal.NewSeq(
    literal.NewLiteral([]byte("foo"), true),
    literal.NewLiteral([]byte("foobar"), true),
)
seq.Minimize()
fmt.Println(seq.Len()) // Output: 1 (only "foo" remains)

Example with no redundancy:

seq := literal.NewSeq(
    literal.NewLiteral([]byte("hello"), true),
    literal.NewLiteral([]byte("world"), true),
)
seq.Minimize()
fmt.Println(seq.Len()) // Output: 2 (both remain)

package main

import (
	"fmt"

	"github.com/donge/coregex/literal"
)

func main() {
	// For prefix matching, "foo" covers "foobar"
	seq := literal.NewSeq(
		literal.NewLiteral([]byte("foo"), true),
		literal.NewLiteral([]byte("foobar"), true),
	)

	fmt.Printf("Before minimize: %d literals\n", seq.Len())
	seq.Minimize()
	fmt.Printf("After minimize: %d literals\n", seq.Len())
	fmt.Printf("Remaining: %s\n", seq.Get(0).Bytes)

}

Output:
Before minimize: 2 literals
After minimize: 1 literals
Remaining: foo

package main

import (
	"fmt"

	"github.com/donge/coregex/literal"
)

func main() {
	// "a" covers "ab" which covers "abc"
	seq := literal.NewSeq(
		literal.NewLiteral([]byte("abc"), true),
		literal.NewLiteral([]byte("ab"), true),
		literal.NewLiteral([]byte("a"), true),
	)

	seq.Minimize()
	fmt.Printf("Literals after minimize: %d\n", seq.Len())
	fmt.Printf("Shortest literal wins: %s\n", seq.Get(0).Bytes)

}

Output:
Literals after minimize: 1
Shortest literal wins: a