Skip to content

scan.md

Latest commit

 

History

History
509 lines (412 loc) · 23.7 KB

scan.md

File metadata and controls

509 lines (412 loc) · 23.7 KB
Raw

Scan sub-package

The scan sub-package at github.com/axonops/fuzzymatch/scan is the turnkey collection-scan layer over the Scorer. It answers the question "which pairs in this collection are similar?" with a deterministic, suppression-aware, group-aware API. Lands in v1.0 (pre-release at the time of writing).

A scan.Config is a plain data struct passed by value; scan.Check is a pure function with no goroutines, channels, or mutexes — safe for concurrent invocation on disjoint inputs given a concurrent-safe *fuzzymatch.Scorer (Phase 8 guarantee). There are no global flags, no mutable internal state, and no init-time work.

The authoritative formal specification lives in docs/requirements.md §12. This document is the consumer-facing guide.

Quickstart

The one-line happy path is:

package main

import (
    "github.com/axonops/fuzzymatch"
    "github.com/axonops/fuzzymatch/scan"
)

func main() {
    s := fuzzymatch.DefaultScorer()
    items := []scan.Item{
        {Name: "user_id", Group: "login"},
        {Name: "userId", Group: "login"},
    }
    warnings, err := scan.Check(items, scan.DefaultConfig(s))
    if err != nil {
        // handle ErrInvalidItem / ErrInvalidConfig / ErrNilScorer
    }
    _ = warnings // process the deterministically-sorted slice
}

scan.DefaultConfig(s) cannot fail. It bakes the opinionated CrossGroupThresholdBoost = 0.05 and CompareIdenticalAcrossGroups = false defaults — see Threshold boost and Suppression composition below.

For tighter precision the recommended composition is Validate-then-Check. Validate is a pair-validation surface (Phase 8.5 Q4) — call it AFTER Check returns, on each emitted (NameA, NameB) pair, to surface per-pair input-quality diagnostics in O(|warnings|) rather than O(N) work upstream:

warnings, err := scan.Check(items, scan.DefaultConfig(s))
if err != nil {
    // handle ErrInvalidItem / ErrInvalidConfig / ErrNilScorer
}
for _, w := range warnings {
    if vs := fuzzymatch.Validate(w.NameA, w.NameB); len(vs) > 0 {
        // surface per-pair input-quality signals (mixed scripts,
        // non-ASCII edge cases, etc.) alongside the similarity warning
        _ = vs
    }
}

Alternatively, if your consumer needs per-item shape checks before scanning (e.g. very-large-input filters, non-ASCII detection on single names), validate each Item.Name against itself:

for i, it := range items {
    if it.Name == "" {
        continue // scan.Check will reject via D-03; skip the diag
    }
    if ws := fuzzymatch.Validate(it.Name, it.Name); len(ws) > 0 {
        // per-item shape diagnostics
        _ = i
        _ = ws
    }
}
warnings, err := scan.Check(items, scan.DefaultConfig(s))

Note: passing "" as the second argument to Validate always triggers WarnEmptyInput and is not a useful pre-flight idiom. Always pass two real strings.

See docs/best-practices.md for the broader Validate-then-Score idiom that applies to every layer.

Choosing a Config

A short decision guide for the three Config shapes:

  • Within-group only (most common). Use scan.DefaultConfig(s) unchanged. Compares items within each Group; cross-group is off. Suitable for the typical "find similar names within each schema / collection / namespace" use case.
  • Within + cross-group, reuse-tolerant. Use scan.DefaultConfig(s) and set cfg.CompareAcrossGroups = true. Adds the cross-group pass with the opinionated 0.05 boost. CompareIdenticalAcrossGroups stays false so legitimate reuse-across-groups (operators reusing user_id across schemas) doesn't drown signal.
  • Surface every identical cross-group name. Use scan.DefaultConfig(s) and set both cfg.CompareAcrossGroups = true and cfg.CompareIdenticalAcrossGroups = true. Now every byte-identical-post-normalise pair across groups appears in the output. Use sparingly; the volume scales with input size.

Custom CrossGroupThresholdBoost values are valid in [0.0, 1.0]; see Threshold boost for tuning notes.

Security and logging considerations

Item.Name, Item.Group, and (when emitted) Warning.NameA, Warning.NameB, Warning.GroupA, Warning.GroupB are verbatim echoes of the caller-supplied byte content. Consumers that pipe emitted warnings into logs propagate whatever bytes were in Item.Name/Item.Group — including any sensitive content the caller chose to put there. The library itself never logs these values; downstream loggers do.

If your Item corpus contains sensitive content (PII, schema field names you don't want in unsanitised log streams, etc.):

  • Carry sensitive context exclusively in Item.Tag (which the library never stringifies into error messages, panic messages, or diagnostic output — see the security note in scan.Item.Tag godoc).
  • Sanitise Warning.NameA/NameB/GroupA/GroupB at the logger boundary if those identifiers are themselves sensitive.

Validation error messages from scan.Check only contain integer indices (offending item positions in the input slice), never Item.Name or Item.Tag bytes. The in-line completeness assertion panic message similarly omits Tag content.

Public API

Function / Type / Constant Signature Description
Check func Check(items []Item, cfg Config) ([]Warning, error) Cross-comparison entry-point with within-group + opt-in cross-group passes, suppression composition, deterministic output.
DefaultConfig func DefaultConfig(s *fuzzymatch.Scorer) Config Opinionated Config: CrossGroupThresholdBoost = 0.05, CompareIdenticalAcrossGroups = false.
Item struct { Name, Group string; SilenceLint bool; Tag any } One named thing the scanner compares. Name is required (non-empty); Group scopes comparisons.
Kind type Kind int Pair-scope discriminator (within-group vs cross-group). SPEC OVERRIDE (Phase 9): renamed from WarningKind per 09-CONTEXT D-02.
KindWithinGroup, KindAcrossGroups const Kind = iota+1 The two Kind values. Iota+1 so the zero value is "unset".
Kind.String func (k Kind) String() string CamelCase form: "WithinGroup" / "AcrossGroups" — matching AlgoID.String() and WarnKind.String() (Phase 8.5 Q6b).
Warning struct { Kind; NameA, NameB; GroupA, GroupB; TagA, TagB any; Score; Scores map[fuzzymatch.AlgoID]float64 } One detected similar-name pair. Scores is typed-key per 09-CONTEXT D-01 (SPEC OVERRIDE).
Config struct { Scorer *fuzzymatch.Scorer; CompareAcrossGroups bool; CrossGroupThresholdBoost float64; CompareIdenticalAcrossGroups bool; SuppressedPairs [][2]string } Controls Check behaviour. Zero value: nil Scorer → ErrNilScorer. Zero CrossGroupThresholdBoost = 0.0 (no boost).
ErrNilScorer var error Config.Scorer was nil when Check was invoked.
ErrInvalidItem var error Empty Item.Name (D-03) or duplicate (Name, Group) (D-06); offending indices collected via errors.Join.
ErrInvalidConfig var error NaN/±Inf/out-of-range CrossGroupThresholdBoost (D-04) or empty entry in SuppressedPairs (D-05).
(*fuzzymatch.Scorer).NormalisationOptions func() (NormalisationOptions, bool) New Phase 9 accessor on *Scorer returning the Scorer's normalisation options. Used internally by scan to canonicalise SuppressedPairs.

Within-group vs cross-group passes

scan.Check runs two distinct passes:

  • Within-group pass. For every group (in sorted-key order), every i<j pair is evaluated via cfg.Scorer.Score and compared against the Scorer's threshold. Always on (default). Items with no Group share the empty-string group; the same iteration discipline applies.

  • Cross-group pass. Opt-in via cfg.CompareAcrossGroups = true. For every pair of distinct groups (gi < gj), every pair (i ∈ gi, j ∈ gj) is evaluated against the effective cross-group threshold:

    effectiveThreshold = min(1.0, scorer.Threshold() + cfg.CrossGroupThresholdBoost)

    The min(1.0, ...) clamp pins the effective threshold at 1.0 even when the arithmetic sum would exceed it (e.g. Threshold(0.85) + Boost(0.20) arithmetically yields 1.05; the clamp makes that 1.0, meaning only byte-identical-post-normalise pairs reach the threshold).

The cross-group pass is inherently noisier than the within-group pass — operators legitimately have schemas where similar names appear across distinct groups. The boost + identical-Name suppression (Rule 3) work together to keep the signal-to-noise ratio reasonable.

Suppression composition

Three rules compose via short-circuit OR — any rule firing suppresses the pair pre-emission. Order of evaluation is cheapest-first; the final emission set is identical regardless of order because OR composition is order-independent on its output.

Rule 1 — per-item SilenceLint

Item.SilenceLint = true suppresses every pair involving that Item. One-sided semantics: setting the flag on either side of a pair silences the pair.

items := []scan.Item{
    {Name: "user_id", Group: "login", SilenceLint: true},
    {Name: "userId",  Group: "login"},
}
warnings, _ := scan.Check(items, scan.DefaultConfig(s))
// len(warnings) == 0 — items[0]'s SilenceLint suppresses the pair.

Rule 2 — Config.SuppressedPairs canonical-pair lookup

A [][2]string of name pairs that should never produce a warning. Pairs are canonicalised once at Check entry via the Scorer's NormalisationOptions() (D-05) — consumers may pass raw forms regardless of case or separators when the Scorer's normalisation absorbs those.

cfg := scan.DefaultConfig(s)
cfg.SuppressedPairs = [][2]string{
    {"user_id", "userId"}, // canonicalised — case + separator drift absorbed
}
warnings, _ := scan.Check(items, cfg)

Self-pairs (a == b after normalisation) are silently retained — they are harmless because Check never emits a self-warning under D-06 (duplicate (Name, Group) is rejected at validation) and the i<j pair-iteration discipline. Caveat: a self-pair entry whose normalised form coincides with the canonical key of a DISTINCT-name candidate pair will also suppress that distinct pair. This is the inevitable consequence of canonical-pair semantics — flagged here so consumers building suppression lists programmatically know to expect it.

Rule 3 — cross-group identical-Name default

When cfg.CompareAcrossGroups == true and cfg.CompareIdenticalAcrossGroups == false (the DefaultConfig default), identical Names across different Groups are silently suppressed. Operators legitimately reuse the same name (e.g. user_id) across groups; surfacing every such pair would drown real similar-but-not-equal signals. Opt out by setting cfg.CompareIdenticalAcrossGroups = true.

The check uses normalised-name equality, so case/separator-only differences across groups are also silenced under the default normalisation pipeline.

Composition

The three rules compose via OR. The isSuppressed predicate is applied pre-emission on both the naive and token-bucket emission paths (so SCAN-02 bucket-vs-naive equivalence holds under suppression). Suppression is never applied post-emission; the emitted slice is precisely the unsuppressed set.

Threshold boost

The cross-group effective threshold is:

effectiveThreshold = min(1.0, scorer.Threshold() + cfg.CrossGroupThresholdBoost)

CrossGroupThresholdBoost is validated strictly at Check entry: NaN, ±Inf, < 0, or > 1 → ErrInvalidConfig (D-04). The zero-value is 0.0 (no boost); scan.DefaultConfig bakes the opinionated 0.05 default. The 0.05 value reflects production- calibration evidence that cross-group matches tend to be ~5 percentage points noisier than within-group matches.

Validation surface

Three subsections per locked decisions D-03 / D-04 / D-05 / D-06. All validation collects every offending index in a single pass and joins them via errors.Join, so callers can fix the whole batch in one round-trip rather than playing whack-a-mole.

D-03 — Empty Item.Name

ErrInvalidItem is returned with errors.Join across all offending indices. Discriminate via errors.Is:

warnings, err := scan.Check(items, cfg)
if errors.Is(err, scan.ErrInvalidItem) {
    // one or more items had empty Name or were duplicates;
    // walk the joined error to enumerate every offending index.
}

D-04 — Invalid Config.CrossGroupThresholdBoost

ErrInvalidConfig is returned when the boost is NaN, ±Inf, < 0, or > 1. Strict-range validation per the Phase 8.5 Q2 parameter contract (parameters vs comparison-data are validated differently — parameters fail fast, comparison data passes silently).

cfg := scan.DefaultConfig(s)
cfg.CrossGroupThresholdBoost = math.NaN()
_, err := scan.Check(items, cfg)
// errors.Is(err, scan.ErrInvalidConfig) == true

D-05 — Empty SuppressedPairs entry

ErrInvalidConfig is returned with errors.Join across all offending entry indices when one or both strings in a SuppressedPairs entry are empty. Self-pairs (a == b) are permitted (see Rule 2 caveat).

D-06 — Duplicate (Name, Group)

ErrInvalidItem is returned with errors.Join across all duplicate indices. The duplicate-detection invariant guarantees the deterministic sort key (Kind, NameA, NameB, GroupA, GroupB) is a strict total order on every valid input — eliminating the need for a post-sort tiebreaker.

Determinism

scan.Check guarantees byte-identical output across runs and platforms given identical input:

  • Lex canonicalisation. Before sorting, every Warning is canonicalised so NameA <= NameB under raw-byte lex compare; GroupA/GroupB and TagA/TagB swap in lockstep so the (Name, Group, Tag) triple still describes the same source Item.

  • Sort key. sort.SliceStable on the 5-tuple (Kind, NameA, NameB, GroupA, GroupB). Every field participates in the comparator, so the sort is a strict total order on valid input. D-06's duplicate-detection invariant guarantees no two Warnings can share the full 5-tuple key.

  • No map iteration on output paths. The groupIndices map is iterated only when building the sortedGroups []string slice (which is then sorted). Every downstream emission iterates the sorted slice. Per .claude/skills/determinism-standards.

  • In-line completeness assertion. After sorting, Check scans adjacent warnings linearly; any pair sharing the full 5-tuple sort key triggers a panic(fuzzymatch.ErrInternalInvariantViolated). The assertion is unreachable on valid input (D-06 rejects duplicate (Name, Group) at validation) — it exists as the documented invariant gate per the Phase 8.5 Gap 5 typed-panic convention. Consumers discriminate via errors.Is(recovered, fuzzymatch.ErrInternalInvariantViolated).

  • NaN/Inf/-0 never appear in output (DET-04). Property tests PropCheck_NoNaN + PropCheck_NoInf verify this on randomised input.

The cross-platform CI matrix (linux/amd64, linux/arm64, darwin/amd64, darwin/arm64, windows/amd64) verifies byte-identical output via the golden file at testdata/golden/scan-default.json. The make verify-determinism target runs the golden-file test on every platform.

Performance

scan.Check performance is dominated by the per-pair Scorer cost. The library applies two optimisations to amortise the dispatch overhead:

  • Tokenise-once. Item Names are normalised + tokenised once at Check entry (per Item, not per pair). The resulting token slice is reused by every per-pair Scorer call within the same Check invocation. Avoids the O(N²) re-tokenisation pattern that inflated v0.x performance roughly 3×.

  • Token-bucket pre-filter. For groups (within-group) or group-pair unions (cross-group) exceeding the internal bucketThreshold (50 items, empirically validated on darwin/arm64), candidate pairs are pre-filtered by shared tokens before the Scorer is consulted. Pairs sharing no token are eliminated without paying Scorer.Score. The PropCheck_BucketEquivalentToNaive property test (scan/props_test.go) proves the bucket path produces the identical warning set as the naive O(N²) reference on randomised input — SCAN-02 load-bearing gate.

PERF-05 budget: scan.Check completes in < 2 seconds for 10,000 items / 500 groups within-group on the reference hardware, verified by BenchmarkScanCheck_DefaultScorer_10k (Plan 09-04). The < 10% benchstat regression gate runs in CI on every PR; the committed bench.txt is the regression baseline.

Cross-group performance note (v0.x baseline): The cross-group pass at 10,000 items / 500 groups runs substantially slower than the within-group pass on the same input shape — the v0.x baseline is approximately 189 seconds on darwin/arm64 for the cross-group-enabled run, vs ~361 milliseconds within-only. Spec §12.6's "at most 2× within-only" claim is documented as a v0.x shortfall; the optimisation candidate (build a single global token bucket once at Check entry and apply per-pair group filters) is tracked in 09-CONTEXT.md "Deferred Ideas" for v1.x consideration. Consumers with large cross-group workloads at v0.x should expect multi-second wall-clock times and may need to chunk their input or restrict CompareAcrossGroups to selected group subsets.

Concurrency

scan.Config is a plain data struct passed by value to Check. *fuzzymatch.Scorer is concurrent-safe by construction (Phase 8 locked guarantee — immutable after NewScorer, no internal mutex or atomic state). scan.Check is a pure function with no goroutines, channels, or mutexes — safe for concurrent invocation on disjoint []Item slices given a shared *Scorer.

Consumers passing the same Config to multiple concurrent Check invocations must not mutate the SuppressedPairs slice between calls. The slice is read once at Check entry to build the canonical-pair map; subsequent mutations would race with that read.

The Warning.Scores map in each emitted Warning is freshly allocated by Scorer.ScoreAll — consumers may mutate it freely without affecting other Warning values or other Check invocations.

Errors

Three sentinels. All are typed error values exported from the package; discriminate via errors.Is, never by matching the error message string.

Sentinel When it fires
ErrNilScorer Config.Scorer was nil when Check was invoked. A nil Scorer has no algorithms, no threshold, and no normalisation options.
ErrInvalidItem Empty Item.Name (D-03) or duplicate (Name, Group) (D-06). errors.Join across all offending indices.
ErrInvalidConfig NaN/±Inf/out-of-range CrossGroupThresholdBoost (D-04) or empty entry in SuppressedPairs (D-05). errors.Join across all offending indices.

errors.Is walks Unwrap() []error (Go 1.20+), so the joined error still discriminates correctly:

warnings, err := scan.Check(items, cfg)
switch {
case errors.Is(err, scan.ErrNilScorer):
    // diagnostic
case errors.Is(err, scan.ErrInvalidItem):
    // walk the joined error to enumerate every offending index
case errors.Is(err, scan.ErrInvalidConfig):
    // either CrossGroupThresholdBoost or SuppressedPairs is invalid
case err != nil:
    // unexpected — file an issue
}

Each sentinel's godoc on pkg.go.dev follows the project's four-section template (What / Common causes / Resolution / Example) — consult that for full per-sentinel guidance beyond the one-line summaries above.

The library-bug panic surface (fuzzymatch.ErrInternalInvariantViolated, raised by the in-line sort-key completeness assertion) is documented in Determinism; consumers can errors.Is(recovered, fuzzymatch.ErrInternalInvariantViolated) to discriminate it from genuine errors. By construction (D-06 validation), this panic is unreachable on valid input.

Decision references

The implementation honours a set of locked design decisions documented internally (planning artefacts) that materially shape the public surface. The most consumer-visible ones (also surfaced as SPEC OVERRIDE notes inline above):

  • D-01. Warning.Scores is map[fuzzymatch.AlgoID]float64 (typed enum keys), NOT map[string]float64 as docs/requirements.md §12.1 originally specified. Extends Phase 8's ScoreAll override for the same compile-time-safety rationale.

  • D-02. The within/cross discriminator is Kind, NOT WarningKind as the spec originally named it. The package-scoped form scan.KindWithinGroup is unambiguous at the call site and avoids accidental symmetry with the root package's WarnKind (Phase 8.5 Q4 — a different domain).

  • D-04. The opinionated CrossGroupThresholdBoost = 0.05 default lives in scan.DefaultConfig, NOT as the zero-value of Config.CrossGroupThresholdBoost. Mirrors the Phase 8 DefaultScorer / DefaultScorerOptions pattern.

  • D-06. Check rejects duplicate (Name, Group) at validation time. Combined with the raw-byte lex canonicalisation of NameA/ NameB, this guarantees the 5-tuple sort key is a strict total order without a tiebreaker — eliminating the spec's earlier "lexicographically smaller (after normalisation)" tiebreaker wording, which is no longer needed.

  • D-07. The recommended composition is Validate-then-Check — see Quickstart and docs/best-practices.md.

See also