addrkit/internal/domain/match/index.go

// Package match resolves a ParsedAddress against a canonical registry index.
//
// It is the deterministic heart of addrkit. It knows nothing about storage,
// HTTP or LLMs: it operates on an in-memory index built from []address.Entry
// and always answers from that data. A wrong house number is never invented —
// when the exact house unit is not present the result is "partial", and when
// several streets are plausible the result is "ambiguous".
package match

import (
	"sort"
	"unicode/utf8"

	"git.totmin.ru/en2zmax/addrkit/internal/domain/address"
)

// Candidate is one plausible match, returned alongside a non-"found" result so
// the caller (or an operator) can see what the resolver was choosing between.
type Candidate struct {
	Address   string  `json:"address"`
	City      string  `json:"city,omitempty"`
	District  string  `json:"district,omitempty"`
	House     string  `json:"house,omitempty"`
	Structure string  `json:"structure,omitempty"`
	Score     float64 `json:"score"`
}

// Result is the outcome of a resolution.
type Result struct {
	Status      address.Status `json:"status"`
	Address     string         `json:"address,omitempty"`
	City        string         `json:"city,omitempty"`
	District    string         `json:"district,omitempty"`
	Confidence  float64        `json:"confidence"`
	Candidates  []Candidate    `json:"candidates,omitempty"`
	DataVersion string         `json:"data_version,omitempty"`
}

// Options tunes matching behaviour.
type Options struct {
	// FuzzyThreshold is the minimum similarity (0..1) for a street to be
	// accepted as a typo-tolerant match. Below it the result is not_found.
	FuzzyThreshold float64
	// AmbiguityMargin: streets within this similarity of the best match make
	// the result ambiguous instead of silently picking one.
	AmbiguityMargin float64
	// MaxCandidates caps the candidates returned to the caller.
	MaxCandidates int
}

// DefaultOptions returns conservative defaults.
//
// The ambiguity margin is deliberately generous relative to the token scores:
// a one-edit match scores 0.95 and a two-edit match 0.90, so a 0.06 margin
// makes near-collisions (e.g. "Елоховская" vs "Волховская") ambiguous rather
// than silently picking the closer-but-wrong street.
func DefaultOptions() Options {
	return Options{
		FuzzyThreshold:  0.82,
		AmbiguityMargin: 0.06,
		MaxCandidates:   5,
	}
}

type streetRef struct {
	key     string
	cityKey string
	ordinal string
	nameKey string
}

// Index is an immutable, in-memory registry index. It is safe for concurrent
// reads once constructed.
type Index struct {
	version string
	opts    Options
	byKey   map[string][]address.Entry
	streets []streetRef
	cities  map[string]string // cityKey -> canonical display name
	size    int
}

// maxFuzzyNameRunes bounds the fuzzy scan. No real street name is longer than
// this; without the bound a single huge token would make every Levenshtein
// comparison walk a very long string and turn a request into a CPU sink.
const maxFuzzyNameRunes = 96

// NewIndex builds an index from canonical entries. Entries sharing a StreetKey
// are grouped; distinct streets are collected for typo-tolerant matching.
//
// Entries are sorted first, so candidate order is deterministic regardless of
// the order in which the storage adapter returned them.
func NewIndex(version string, entries []address.Entry, opts Options) *Index {
	sorted := append([]address.Entry(nil), entries...)
	sort.SliceStable(sorted, func(i, j int) bool { return entryLess(sorted[i], sorted[j]) })

	ix := &Index{
		version: version,
		opts:    opts,
		byKey:   make(map[string][]address.Entry, len(sorted)),
		cities:  make(map[string]string),
		size:    len(sorted),
	}
	seen := make(map[string]struct{}, len(sorted))
	for _, e := range sorted {
		ix.byKey[e.StreetKey] = append(ix.byKey[e.StreetKey], e)
		if e.CityKey != "" {
			if _, ok := ix.cities[e.CityKey]; !ok {
				ix.cities[e.CityKey] = e.City
			}
		}
		if _, ok := seen[e.StreetKey]; !ok {
			seen[e.StreetKey] = struct{}{}
			ix.streets = append(ix.streets, streetRef{
				key:     e.StreetKey,
				cityKey: e.CityKey,
				ordinal: e.Ordinal,
				nameKey: e.NameKey,
			})
		}
	}
	sort.Slice(ix.streets, func(i, j int) bool { return ix.streets[i].key < ix.streets[j].key })
	return ix
}

// entryLess defines the canonical order of registry rows. Address strings are
// the last meaningful tie-breaker; ID makes the order total even for duplicated
// rows.
func entryLess(a, b address.Entry) bool {
	switch {
	case a.CityKey != b.CityKey:
		return a.CityKey < b.CityKey
	case a.StreetKey != b.StreetKey:
		return a.StreetKey < b.StreetKey
	case a.House != b.House:
		return a.House < b.House
	case a.HouseFrac != b.HouseFrac:
		return a.HouseFrac < b.HouseFrac
	case a.HouseLetter != b.HouseLetter:
		return a.HouseLetter < b.HouseLetter
	case a.Building != b.Building:
		return a.Building < b.Building
	case a.BuildingFrac != b.BuildingFrac:
		return a.BuildingFrac < b.BuildingFrac
	case a.BuildingLetter != b.BuildingLetter:
		return a.BuildingLetter < b.BuildingLetter
	case a.Structure != b.Structure:
		return a.Structure < b.Structure
	case a.Address != b.Address:
		return a.Address < b.Address
	default:
		return a.ID < b.ID
	}
}

// Version returns the data version the index was built from.
func (ix *Index) Version() string { return ix.version }

// Size returns the number of indexed entries.
func (ix *Index) Size() int { return ix.size }

// Cities returns the distinct canonical city names present in the index, in
// deterministic order. A city-less index returns an empty slice.
func (ix *Index) Cities() []string {
	out := make([]string, 0, len(ix.cities))
	for _, name := range ix.cities {
		out = append(out, name)
	}
	sort.Strings(out)
	return out
}

// Resolve resolves a parsed address. It never returns an address that is not
// present in the index.
func (ix *Index) Resolve(p address.ParsedAddress) Result {
	res := Result{DataVersion: ix.version, City: p.City}

	entries := ix.byKey[p.StreetKey]
	similarity := 1.0

	if len(entries) == 0 {
		var ambiguousKeys []string
		entries, similarity, ambiguousKeys = ix.fuzzyStreets(p)
		if len(ambiguousKeys) > 0 {
			res.Status = address.StatusAmbiguous
			res.Confidence = similarity
			res.Candidates = ix.representatives(ambiguousKeys, similarity)
			return res
		}
	}
	if len(entries) == 0 {
		res.Status = address.StatusNotFound
		return res
	}
	if res.City == "" {
		// A city-less query may still match exactly one city; report it so the
		// caller does not have to re-derive the city from the candidates.
		res.City = commonCity(entries)
	}

	if !p.HasHouse {
		// Street is known but the caller did not supply a house: safe but
		// incomplete.
		res.Status = address.StatusPartial
		res.Confidence = clamp01(similarity * 0.8)
		res.Candidates = candidates(entries, similarity, ix.opts.MaxCandidates)
		return res
	}

	matched := matchHouseUnit(entries, p)
	switch len(matched) {
	case 1:
		res.Status = address.StatusFound
		res.Address = matched[0].Address
		res.City = matched[0].City
		res.District = matched[0].District
		res.Confidence = clamp01(similarity)
		return res
	case 0:
		// Street recognised, exact house unit absent, or several units share
		// the same number (ambiguous at the unit level).
		if sameHouseSeveral(entries, p) {
			res.Status = address.StatusAmbiguous
			res.Confidence = clamp01(similarity * 0.9)
			res.Candidates = candidates(matchHouseUnitAll(entries, p), similarity, ix.opts.MaxCandidates)
			return res
		}
		res.Status = address.StatusPartial
		res.Confidence = clamp01(similarity * 0.9)
		// Prefer houses that share the number/fraction/letter: they are the
		// plausible corrections (a different corpus or structure), while the
		// rest of the street is noise.
		related := matchHouseUnitAll(entries, p)
		if len(related) == 0 {
			related = entries
		}
		res.Candidates = candidates(related, similarity, ix.opts.MaxCandidates)
		return res
	default:
		res.Status = address.StatusAmbiguous
		res.Confidence = clamp01(similarity * 0.9)
		res.Candidates = candidates(matched, similarity, ix.opts.MaxCandidates)
		return res
	}
}

// fuzzyStreets finds streets similar to the query. It returns the entries of
// the best street when the match is unambiguous, or the list of competing
// street keys when several are within the ambiguity margin.
func (ix *Index) fuzzyStreets(p address.ParsedAddress) (entries []address.Entry, similarity float64, ambiguousKeys []string) {
	if p.NameKey == "" || utf8.RuneCountInString(p.NameKey) > maxFuzzyNameRunes {
		return nil, 0, nil
	}
	best := 0.0
	bestKey := ""
	for _, s := range ix.streets {
		// A query that names a city may only match streets in that city.
		if p.CityKey != "" && s.cityKey != p.CityKey {
			continue
		}
		// If the query carries an ordinal, the candidate's ordinal must match:
		// a user who says "1-й Северный" does not mean the plain "Северная".
		if !ordinalCompatible(p.Ordinal, s.ordinal) {
			continue
		}
		if sim := nameSimilarity(p.NameKey, s.nameKey); sim > best {
			best = sim
			bestKey = s.key
		}
	}
	if best < ix.opts.FuzzyThreshold {
		return nil, best, nil
	}

	for _, s := range ix.streets {
		if p.CityKey != "" && s.cityKey != p.CityKey {
			continue
		}
		if !ordinalCompatible(p.Ordinal, s.ordinal) {
			continue
		}
		if nameSimilarity(p.NameKey, s.nameKey) >= best-ix.opts.AmbiguityMargin {
			ambiguousKeys = append(ambiguousKeys, s.key)
		}
	}
	if len(ambiguousKeys) > 1 {
		return nil, best, ambiguousKeys
	}
	return ix.byKey[bestKey], best, nil
}

// ordinalCompatible reports whether a candidate street may compete with the
// query given the query's ordinal. When the query specifies an ordinal, only
// candidates with the same ordinal are allowed; otherwise any candidate is.
func ordinalCompatible(queryOrdinal, candidateOrdinal string) bool {
	if queryOrdinal == "" {
		return true
	}
	return queryOrdinal == candidateOrdinal
}

// representatives returns one candidate per competing street, which is far
// more useful to a user than five houses of a single street.
func (ix *Index) representatives(keys []string, score float64) []Candidate {
	sort.Strings(keys)
	out := make([]Candidate, 0, len(keys))
	for _, k := range keys {
		es := ix.byKey[k]
		if len(es) == 0 {
			continue
		}
		e := es[0]
		out = append(out, Candidate{
			Address:   e.Address,
			City:      e.City,
			District:  e.District,
			House:     e.House,
			Structure: e.Structure,
			Score:     clamp01(score),
		})
		if len(out) == ix.opts.MaxCandidates {
			break
		}
	}
	return out
}

// matchHouseUnit returns entries whose house unit equals p's, exactly.
func matchHouseUnit(entries []address.Entry, p address.ParsedAddress) []address.Entry {
	var out []address.Entry
	for _, e := range entries {
		if houseUnitEqual(e, p) {
			out = append(out, e)
		}
	}
	return out
}

// matchHouseUnitAll returns all entries for entries that share the same house
// number as p (used to surface ambiguity).
func matchHouseUnitAll(entries []address.Entry, p address.ParsedAddress) []address.Entry {
	var out []address.Entry
	for _, e := range entries {
		if e.House == p.House && e.HouseFrac == p.HouseFrac && e.HouseLetter == p.HouseLetter {
			out = append(out, e)
		}
	}
	return out
}

// sameHouseSeveral reports whether more than one entry matches the house
// number but with differing buildings/letters, i.e. the unit is ambiguous.
func sameHouseSeveral(entries []address.Entry, p address.ParsedAddress) bool {
	return len(matchHouseUnitAll(entries, p)) > 1
}

// houseUnitEqual compares the parts of a house unit. Unspecified (empty) parts
// must also be empty on the entry side, so "60/1" never matches "60/1 к148".
// The structure ("стр. 2") is part of the identity: a caller who explicitly
// asked for a different structure must not be handed another building.
func houseUnitEqual(e address.Entry, p address.ParsedAddress) bool {
	return e.House == p.House &&
		e.HouseFrac == p.HouseFrac &&
		e.HouseLetter == p.HouseLetter &&
		e.Building == p.Building &&
		e.BuildingFrac == p.BuildingFrac &&
		e.BuildingLetter == p.BuildingLetter &&
		e.Structure == p.Structure
}

func candidates(entries []address.Entry, score float64, limit int) []Candidate {
	if limit <= 0 || len(entries) == 0 {
		return nil
	}
	out := make([]Candidate, 0, len(entries))
	for _, e := range entries {
		out = append(out, Candidate{
			Address:   e.Address,
			City:      e.City,
			District:  e.District,
			House:     e.House,
			Structure: e.Structure,
			Score:     clamp01(score),
		})
		if len(out) == limit {
			break
		}
	}
	return out
}

func clamp01(v float64) float64 {
	if v < 0 {
		return 0
	}
	if v > 1 {
		return 1
	}
	return v
}

// commonCity returns the city shared by all entries, or "" when they span
// cities (or carry no city at all).
func commonCity(entries []address.Entry) string {
	key, name := "", ""
	for _, e := range entries {
		if e.CityKey == "" {
			continue
		}
		if key == "" {
			key, name = e.CityKey, e.City
			continue
		}
		if e.CityKey != key {
			return ""
		}
	}
	return name
}