trigram

Documentation

Overview

Package trigram is a pure-Go trigram postings index for substring and regex search over a document set — the tree + sibling-repo code-search seam (#3437, epic #3434). It borrows the two load-bearing ideas from Google Code Search (Russ Cox, "Regular Expression Matching with a Trigram Index"):

1. Index every distinct 3-rune shingle of each document, mapping trigram -> posting list of document ids. A literal can only occur in a document that contains ALL of the literal's trigrams, so the postings intersection is a cheap candidate pre-filter before the exact (and expensive) verify.
2. Probe with only the RAREST trigrams. The two lowest-frequency trigrams of a literal already cut the candidate set to near-nothing; intersecting more buys little. And if any trigram of the literal has an EMPTY posting list, the literal cannot exist anywhere — short-circuit to zero candidates without touching a single document.

The index is in-memory and built once from one goroutine, then queried; a repo is thousands of files, so a linear postings scan stays cheap and deterministic.

Index

• func Similarity(a, b string) float64
• type ComparisonArm
• type ComparisonResult
  • func CompareLocal() ComparisonResult
• type Index
  • func (ix *Index) Add(id, path, content string)
  • func (ix *Index) Candidates(literal string) []int
  • func (ix *Index) DocCount() int
  • func (ix *Index) Search(literal string) []Result
  • func (ix *Index) SearchRegexp(pattern string) ([]Result, error)
• type Result
• type Trigram

Functions

func Similarity

func Similarity(a, b string) float64

Similarity is the Sørensen–Dice coefficient over the DISTINCT trigram sets of a and b: 2·|A∩B| / (|A|+|B|), a 0..1 lexical closeness that REUSES the same 3-rune shingling the postings index is built on. It is the fuzzy ratio a near-miss or synonym lookup falls back to when exact substring matching finds nothing (the devindex Search* false-ABSENT fix, #3925), so it lives beside the index rather than being re-implemented by every caller.

It is case-sensitive (the index is too); callers that want case-folding lowercase both sides first. Two strings too short to shingle (<3 runes) share no trigrams, so they compare by exact equality — identical short strings score 1, otherwise 0. Two equal strings always score 1 (this also defines empty-vs-empty as identical).

Types

type ComparisonArm

type ComparisonArm struct {
	Name            string
	Kind            string
	Available       bool
	Correct         bool
	BuildLatency    time.Duration
	QueryLatency    time.Duration
	Queries         int
	ExactQueries    int
	FalsePositives  int
	FalseNegatives  int
	LocationErrors  int
	CPUSeconds      float64
	PeakRSSBytes    int64
	CorpusBytes     int64
	IndexBytes      int64
	NetworkBytes    int64
	StorageBytes    int64
	OperatorSeconds float64
	CostUSD         float64
	Note            string
}

type ComparisonResult

type ComparisonResult struct {
	Workload string
	Arms     []ComparisonArm
}

func CompareLocal

func CompareLocal() ComparisonResult

type Index

type Index struct {
	// contains filtered or unexported fields
}

Index maps each trigram to the sorted, de-duplicated list of document ids that contain it. The zero value is ready to use.

func (*Index) Add

func (ix *Index) Add(id, path, content string)

Add indexes a document under id (path is carried through to results). Re-adding an existing id is allowed; it appends a second doc, so callers that upsert should use distinct ids.

func (*Index) Candidates

func (ix *Index) Candidates(literal string) []int

Candidates returns the document ids that COULD contain literal, using the rarest-two-trigram probe. Guarantees:

• A literal with any trigram whose posting list is empty returns nil — it cannot exist in any document (the freq-0 short-circuit).
• A literal shorter than 3 runes cannot be indexed, so every document is a candidate (the caller must verify).
• Otherwise the result is a superset of the truly-matching documents (sound: never drops a real match), narrowed by intersecting the two rarest trigrams.

func (*Index) DocCount

func (ix *Index) DocCount() int

DocCount is the number of indexed documents.

func (*Index) Search

func (ix *Index) Search(literal string) []Result

Search returns the documents that contain literal as a substring, verified exactly after the trigram pre-filter. Results are ordered by document id.

func (*Index) SearchRegexp

func (ix *Index) SearchRegexp(pattern string) ([]Result, error)

SearchRegexp returns the documents matching pattern. It narrows candidates using the required literals extracted from the regex (an AND of substrings every match must contain), then verifies with the compiled regexp. When no required literal can be proven (alternation at top level, or a fully wildcard pattern), it falls back to brute force over every document — always sound, never a missed match.

type Result

type Result struct {
	ID    string
	Path  string
	Lines []int
}

Result is one matching document plus the 1-based line numbers where the query was found (populated by the verify pass).

type Trigram

type Trigram uint64

Trigram is three runes packed into a uint64 (21 bits each; Unicode's max code point 0x10FFFF fits in 21 bits, and 3*21 = 63 <= 64). Packing keeps the postings key a comparable scalar instead of a heap string.