// Package fact recognises the facts §8.8's box is allowed to show.
//
// One table drives all of it: a kind names the words that ask for it AND
// the validator that admits it. Those two must not drift apart — a
// lexicon that primes `iban` next to a validator that no longer accepts
// one is a box that never appears and nothing that says why — so they are
// two columns of one declaration and live in one file. That is also why
// the lexicon is here rather than in query, which has its own single
// decision to make and says so.
//
// Nothing here touches a database, a template or an app. The spec's §8.8
// is a long argument about authorization and ordering, and none of it is
// in this package: by the time Scan is called the passage has already
// passed §4.1. What is here is the part that can be wrong on its own —
// whether a string is really an IBAN, and what the document called it.
//
// **Three of the five kinds are checksums and two are not**, and the
// difference is stated rather than smoothed over. An eircode's routing
// key is a closed set, an IBAN has a mod-97 check, an Irish VAT number
// has a check letter derived from its own digits: those can be wrong, and
// a wrong one is refused. A phone number and an email address have no
// such property, and their bounds are structural. See phoneValid for the
// rule that keeps the weakest of them honest.
package fact

import (
	"regexp"
	"sort"
	"strings"
	"unicode"
	"unicode/utf8"
)

// Kind is one recognisable fact type.
type Kind string

const (
	Eircode Kind = "eircode"
	Phone   Kind = "phone"
	IBAN    Kind = "iban"
	VAT     Kind = "vat"
	Email   Kind = "email"
	// Address is a postal address, and it is the first MODEL kind: no
	// recogniser produces one, because an address has no checksum, no
	// grammar and no length to validate against. §8.9 sends it to a
	// model; this package only lets a query ask for it.
	Address Kind = "address"
)

// modelKinds is §8.9's allowlist: the kinds that may be sent to a model.
//
// **An allowlist, and never "whatever has no recogniser".** Draft 1 of
// §8.9 phrased eligibility as "where the deterministic layer produced
// nothing", which invites asking a model for a phone number whenever the
// box happens to be empty — and §8.8's box is empty for five different
// reasons, from zero candidates to a collision. Eligibility is a
// property of the kind. TestNoModelKindHasARecogniser holds the two sets
// apart, so adding a recogniser for Address later forces a decision
// rather than quietly sending a validated kind to a model.
var modelKinds = map[Kind]bool{Address: true}

// ModelKind reports whether k may be sent to a model under §8.9.
func ModelKind(k Kind) bool { return modelKinds[k] }

// order is the order kinds are returned and rendered in, so that a
// two-kind query produces the same two boxes in the same places every
// time. A map's range order would not, and §8.8's gate asserts order.
var order = []Kind{Eircode, Phone, IBAN, VAT, Email, Address}

// Found is one validated fact, located in a passage.
type Found struct {
	Kind Kind
	// Span is the document's own bytes, and the only thing rendered.
	// Taken as a slice of the input rather than rebuilt from parts, so
	// that "byte-identical to the document" is a property of this type
	// and not a discipline somebody has to keep. §8.7's rule one noun
	// over: a second formatter is the same bug class as a second
	// calculator.
	Span string
	// Canonical is match-only. It keys candidate identity so that
	// "01 547 7854" and "+353 (0)1 547 7854" are one number rather than
	// two, and it is what the validator ran on. It is NEVER rendered and
	// is never an operand — see the package doc and §8.8 for why that
	// distinction is what keeps this inside §8.7 and decision 10.
	Canonical string
	// Label is what the document called this value. Never composed.
	// When NoBox is set it holds the over-long label, which is never
	// rendered: it is kept so §8.8's narrowing can tell whether the
	// reader's words are in it.
	Label string
	// Own reports that Label is the document's own words for this value —
	// the sentence-anchored run ending in a separator (§8.8 rule 2) —
	// rather than the heading trail or title it falls back to. Only an
	// own label can match the reader's words (§8.8, narrowing).
	Own bool
	// NoBox means this kind renders nothing at all, because a value
	// carried a document-authored label too long to show. Substituting
	// the heading trail would replace the document's words with vaguer
	// ones — "the number you must never give to customers…" becoming
	// "Contacts" — and dropping just this candidate would turn a
	// two-candidate ambiguity into a confident single answer. Both are
	// worse than silence. §8.8.
	NoBox bool
}

// ---------------------------------------------------------------------
// The lexicon: which words ask for which kind.
// ---------------------------------------------------------------------

// phrase is one entry of the lexicon, as a token sequence.
type phrase struct {
	toks []string
	kind Kind
}

// lexicon maps what a person types to a kind. Longest phrases are tried
// first, which is the whole reason "email address" can mean Email while
// "address" alone means nothing: postal and email addresses are
// ambiguous and only one of them has anything resembling a validator.
//
// **This is query.openers' trade made in the opposite direction.** That
// list is deliberately stingy, because a wrong Enter-prime navigates away
// from a page somebody was reading. This one can afford to be generous,
// and the reason is the validator rather than a shared instinct: "mobile
// app" primes Phone, finds no phone number, and renders nothing. A
// generous lexicon costs a box that does not appear.
var lexicon = []phrase{
	// Three tokens, and it must come first: "e-mail address" splits to
	// e / mail / address, and without this the two-token "e mail" took
	// the first two and left "address" to prime the POSTAL kind — an
	// email query sending passages to a model. Found by review.
	{[]string{"e", "mail", "address"}, Email},
	{[]string{"email", "address"}, Email},
	{[]string{"postal", "address"}, Address},
	{[]string{"phone", "number"}, Phone},
	{[]string{"bank", "details"}, IBAN},
	{[]string{"post", "code"}, Eircode},
	{[]string{"vat", "number"}, VAT},
	{[]string{"e", "mail"}, Email},
	{[]string{"eircode"}, Eircode},
	{[]string{"postcode"}, Eircode},
	{[]string{"telephone"}, Phone},
	{[]string{"phone"}, Phone},
	{[]string{"mobile"}, Phone},
	{[]string{"tel"}, Phone},
	{[]string{"iban"}, IBAN},
	{[]string{"vat"}, VAT},
	{[]string{"email"}, Email},
	// Bare "address" is POSTAL. It used to prime nothing, because it is
	// ambiguous with email and only email had a validator; decision 15's
	// amendment makes postal a model kind, and "email address" is matched
	// as a phrase before this single word is ever tried.
	{[]string{"address"}, Address},
}

// Wanted returns the kinds a query names, in `order`. Empty means no box.
//
// Deliberately absent: "number", which is generic and counts only in
// combination, and would prime on ordinary queries that are not asking
// for a fact. ("address" used to be absent too; it is now the postal
// model kind — see the lexicon.)
func Wanted(q string) []Kind {
	toks := tokens(q)
	want := map[Kind]bool{}
	for i := 0; i < len(toks); i++ {
		for _, p := range lexicon {
			if len(p.toks) > len(toks)-i {
				continue
			}
			if matchAt(toks, i, p.toks) {
				want[p.kind] = true
				i += len(p.toks) - 1
				break
			}
		}
	}
	var out []Kind
	for _, k := range order {
		if want[k] {
			out = append(out, k)
		}
	}
	return out
}

// generic are words that name no kind and qualify nothing: "number" is
// how every kind is asked for.
var generic = map[string]bool{"number": true, "numbers": true, "no": true, "nr": true}

// stopwords are the question and function words a query carries around
// its qualifiers. **Stated as incomplete**, like the abbreviation list:
// a word missing from here becomes a qualifier that no label contains,
// narrowing matches nothing, and the kind is ruled exactly as it would
// have been without narrowing. That is the safe direction. This must not
// grow into a parser.
var stopwords = map[string]bool{}

func init() {
	for _, w := range strings.Fields(`
		what whats which who whose where when why how
		is are was were be been am do does did has have had can could
		will would should shall may might must
		a an the this that these those there here
		i me my mine we us our ours you your yours he him his she her hers
		it its they them their theirs
		of for to at in on by with from about as into onto and or but not
		please tell give find show get need want know let see look
		any some one all`) {
		stopwords[w] = true
	}
}

// Qualifiers returns the words in a query that are neither how a kind is
// asked for nor how a question is asked — "office" in "what is the office
// phone number?". §8.8 narrows a kind to the candidates whose own label
// contains every one of them. In query order, without repeats.
func Qualifiers(q string) []string {
	lex := map[string]bool{}
	for _, p := range lexicon {
		for _, t := range p.toks {
			lex[t] = true
		}
	}
	var out []string
	seen := map[string]bool{}
	for _, t := range tokens(q) {
		if utf8.RuneCountInString(t) < 2 || lex[t] || generic[t] || stopwords[t] || seen[t] {
			continue
		}
		seen[t] = true
		out = append(out, t)
	}
	return out
}

// LabelMatches reports whether label contains every qualifier as a whole
// token. Tokens, not substrings, so "office" does not match "offices" or
// "backoffice". No stemming: a missed match leaves the kind ruled as it
// would have been anyway.
func LabelMatches(label string, qualifiers []string) bool {
	if len(qualifiers) == 0 {
		return false
	}
	have := map[string]bool{}
	for _, t := range tokens(label) {
		have[t] = true
	}
	for _, q := range qualifiers {
		if !have[q] {
			return false
		}
	}
	return true
}

func matchAt(toks []string, i int, want []string) bool {
	for j, w := range want {
		if toks[i+j] != w {
			return false
		}
	}
	return true
}

// tokens lowercases and splits on anything that is not a letter or
// digit, so "e-mail" becomes ["e","mail"] and punctuation is inert. The
// same shape as index.MatchQuery's term split, and for the same reason: a
// search box is not a query language.
func tokens(s string) []string {
	return strings.FieldsFunc(strings.ToLower(s), func(r rune) bool {
		return !unicode.IsLetter(r) && !unicode.IsDigit(r)
	})
}

// ---------------------------------------------------------------------
// The recognisers.
// ---------------------------------------------------------------------

// sep is every character that may separate the groups of a fact, and it
// includes U+00A0.
//
// Go's \s does NOT match a non-breaking space, and Word and Notion both
// paste them. chunk.Split does not normalise interior whitespace, so the
// bytes reach the sealed row exactly as pasted — which means a recogniser
// written with \s finds nothing at all in text pasted from either, and
// the failure is a box that silently never appears.
const sep = ` \x{00A0}`

// phoneGroups builds the digit-group half of the phone pattern for one
// separator style.
//
// **Loose, and the group count is the validator's job — not this
// pattern's.** Bounding it here truncated real numbers instead of
// refusing them, which is far worse than either: capped at five digits a
// group, "Mobile: +353 87 1234567" was boxed as "+353 87 12345" — the
// commonest international spelling of an Irish mobile, rendered as a
// different number, cited, above the results. Capped at three groups,
// "+49 30 12 34 56 78" was boxed as "+49 30 12 34 56". Both pass every
// other check because what is left is a well-formed number; they are
// §8.7's "cites correctly while being wrong", produced by the pattern
// that was supposed to prevent it.
//
// So the groups are generous and phoneValid refuses by count. A refusal
// shows nothing; a truncation shows a wrong number.
//
// **And at least one, which is what makes the three styles alternate.**
// Written {0,3} the first branch matched zero groups and won, because
// Go's regexp prefers the earliest alternative that matches AT ALL —
// so "01-547-7854" came back as the two-digit span "01" and was refused,
// with the dash branch never tried. A branch that cannot match zero
// groups fails, and the next one gets its turn.
func phoneGroups(sepClass string) string {
	return `(?:` + sepClass + `[0-9]{2,7}){1,6}`
}

type recogniser struct {
	kind  Kind
	re    *regexp.Regexp
	canon func(string) string
	valid func(span, canonical string) bool
}

// The regexes are deliberately LOOSE and the validators do the work.
// That is §8.8's "validation is not pattern-spotting" made structural: it
// is what stops the next person tightening a regex until it is a
// validator nobody can see, and it is why every reject below fails on an
// arithmetic property rather than on a character class.
var recognisers = []recogniser{
	{
		kind: Eircode,
		// The routing key's first letter is a closed set and the unique
		// identifier's alphabet excludes the letters that misread. A
		// pattern written [A-Z][0-9][0-9] gets Dublin 6W wrong and lets
		// B12 3456 through; both are fixtures.
		//
		// **Case-SENSITIVE, and it was written (?i) first.** The review
		// found what that costs: the identifier alphabet is most of the
		// consonants, so lowercase English after a road number or a form
		// code matches it. "Take the N11 then exit at Bray" boxed
		// "N11 then"; "Form P45 then P60" boxed "P45 then". A query for
		// an eircode then gets a cited fact that is an English word —
		// §8.7's "cites correctly while being wrong", from a character
		// class. Eircodes are written uppercase, and a lowercase one
		// going unrecognised is the safe direction.
		re:    regexp.MustCompile(`\b[ACDEFHKNPRTVWXY][0-9][0-9W][` + sep + `]?[0-9ACDEFHKNPRTVWXY]{4}\b`),
		canon: func(s string) string { return strings.ToUpper(stripSep(s)) },
		valid: func(_, _ string) bool { return true }, // the pattern IS the closed set
	},
	{
		kind: Phone,
		// Built out of digit GROUPS rather than one character class, and
		// that is the difference between working and not.
		//
		// A class — [0-9 ().-]{6,24} — is greedy across a LIST: given
		// "Phone: 01 547 7854 - 01 598 1234" it swallows both numbers as
		// one span of eighteen digits, which then fails validation, so
		// the page shows nothing where it should show two. Requiring a
		// SINGLE separator between groups stops the match at the " - ",
		// and the second number then matches on its own. Found by the
		// fixture, not by reading the pattern.
		//
		// The prefix is "+CC", optionally followed by the "(0)" that
		// means "the trunk digit you omit from abroad", or a bare
		// leading 0. Anchoring there is what keeps account numbers,
		// company numbers and DUNS numbers out before any validation
		// runs at all.
		//
		// **One separator style throughout, and phoneValid's 9-or-10
		// bound is why it has to be.** That bound was written to keep
		// dates out, and a mixed-separator pattern walked straight past
		// it: "The deadline is 01-02-2024 10:30" matched
		// "01-02-2024 10" — ten digits, valid, boxed. A person writing a
		// phone number uses one separator for all of it. RE2 has no
		// backreferences, so the three styles are three alternatives.
		re: regexp.MustCompile(`(?:\+[0-9]{1,3}[` + sep + `]*(?:\(0\))?|\b0)[` + sep + `]*` +
			`[0-9]{1,9}(?:` + phoneGroups(`[`+sep+`]`) + `|` + phoneGroups(`-`) + `|` + phoneGroups(`\.`) + `)?` +
			// An extension is part of the span, because §8.8 says the span
			// is what the document wrote, and a number whose extension has
			// been dropped is a number that does not reach the person.
			//
			// **An extension OR a word boundary, never "optionally
			// neither".** Written `(?:…)?` the match could stop in the
			// middle of a run of digits, which is the other half of how
			// "+353 87 1234567" became "+353 87 12345". Requiring one or
			// the other means a partial number is not a match at all.
			`(?:(?i:[` + sep + `]*(?:ext|extension|x)\.?[` + sep + `]*[0-9]{1,6})|\b)`),
		canon: phoneCanon,
		valid: phoneValid,
	},
	{
		kind: IBAN,
		// Two spellings, because a document writes an IBAN either solid
		// or in groups of four.
		//
		// **The grouped alternative was {2,4}-sized groups and that made
		// the kind inert on its commonest shape.** A trailing 2-4 letter
		// word was swallowed into the last group, the canonical form came
		// out the wrong length, and validation refused the whole thing:
		// "Our IBAN is IE29 AIBK 9311 5212 3456 78 and our BIC is …"
		// found nothing at all. Only a full stop immediately after the
		// number worked. Groups of exactly four with one short tail stop
		// at the space before "and", because "and" is not four
		// characters — and case-sensitivity means it would not match
		// even if it were.
		//
		// **The tail is digits only**, because an uppercase 1-3 character
		// token is exactly what follows an IBAN in practice: "BE68 5390
		// 0754 7034 BIC: GEBABEBB" found nothing while the tail admitted
		// letters, and every country whose length is a multiple of four
		// (BE, ES, AT, PL, SE, LU) has no real tail for it to sit in.
		re:    regexp.MustCompile(`\b[A-Z]{2}[0-9]{2}(?:[A-Z0-9]{11,30}|(?:[` + sep + `][A-Z0-9]{4}){2,7}(?:[` + sep + `][0-9]{1,3})?)\b`),
		canon: func(s string) string { return strings.ToUpper(stripSep(s)) },
		valid: func(_, c string) bool { return ibanValid(c) },
	},
	{
		kind:  VAT,
		re:    regexp.MustCompile(`(?i)\bIE[0-9]{7}[A-Z]{1,2}\b`),
		canon: func(s string) string { return strings.ToUpper(stripSep(s)) },
		valid: func(_, c string) bool { return vatValid(c) },
	},
	{
		kind: Email,
		// The weakest kind here, and §8.8 says so rather than hiding it:
		// local@domain is closer to pattern-spotting than to validation.
		// On a corpus carrying forwarded mail every signature qualifies,
		// the cap is passed, and the box is inert for this kind — which
		// is the cap working, and fails towards silence rather than
		// towards a wrong address.
		re:    regexp.MustCompile(`\b[A-Za-z0-9._%+\-]+@[A-Za-z0-9.\-]+\.[A-Za-z]{2,}\b`),
		canon: strings.ToLower,
		valid: func(_, _ string) bool { return true },
	},
}

// stripSep removes every separator a document might group a fact with,
// including U+00A0. Used only to build a Canonical; a Span is never
// passed through it, which is gate 36's whole subject.
func stripSep(s string) string {
	return strings.Map(func(r rune) rune {
		switch r {
		case ' ', ' ', '-', '.', '(', ')', '\t':
			return -1
		}
		return r
	}, s)
}

// phoneCanon folds a written number onto E.164 so that "01 547 7854" and
// "+353 (0)1 547 7854" are ONE candidate rather than two.
//
// The "(0)" is dropped only after an international prefix, which is what
// that notation means: it is the trunk digit you dial domestically and
// omit from abroad. Keeping it would make the two spellings above
// different canonical values and put the same number in the box twice.
//
// Never rendered. §8.8 rules explicitly that a canonical form which is
// neither displayed nor an operand is not §8.7's forbidden second parser.
func phoneCanon(s string) string {
	if base, ext := splitExt(s); ext != "" {
		// An extension is part of the number somebody has to ring, so two
		// entries differing only by extension are two candidates and not a
		// duplicate. Appended AFTER the base is folded, so the base still
		// dedupes across spellings.
		return phoneCanon(base) + "x" + onlyDigits(ext)
	}
	intl := strings.HasPrefix(s, "+")
	if intl {
		s = strings.Replace(s, "(0)", "", 1)
	}
	var d strings.Builder
	for _, r := range s {
		if r >= '0' && r <= '9' {
			d.WriteRune(r)
		}
	}
	digits := d.String()
	switch {
	case intl:
		return "+" + digits
	case strings.HasPrefix(digits, "0"):
		// A national number, which on this corpus means Ireland. Folded
		// onto +353 so it dedupes against the international spelling.
		return "+353" + digits[1:]
	default:
		return digits
	}
}

// phoneValid is the structural rule that keeps the one checksum-less
// numeric kind honest: **a bare run of digits is never a phone number.**
//
// A phone number has no check digit, so unlike an IBAN or a VAT number
// there is nothing arithmetic to refuse a wrong one with. What is left is
// how documents actually write phone numbers: with a country code, or in
// groups. Without this rule index/rank_test.go's own corpus produces a
// false positive on its first line — "DUNS/D-U-N-S number is 985632364"
// is nine digits and a plausible Irish mobile.
//
// **The cost is stated rather than discovered:** a document that writes
// 0871234567 with no separators at all is not boxed. That is the
// direction a refusal should fail in.
func phoneValid(span, _ string) bool {
	// Validated on the BASE number. An extension carries its own
	// digits and would otherwise push an ordinary number past E.164's
	// fifteen — refusing it for carrying more information, not less.
	base, _ := splitExt(span)
	if !strings.HasPrefix(base, "+") && !strings.ContainsAny(base, "  ().-") {
		return false
	}
	// **Refused by group count, never truncated.** A phone number is at
	// most four separator-delimited runs, or five once a country code is
	// counted: "01 547 7854" is three, "+353 87 1234567" is three.
	// "Numbers drawn: 01 05 12 23 34" is five, and "+49 30 12 34 56 78"
	// is six — both refused here rather than cut down to something that
	// would validate. Germany and France genuinely do write more groups
	// than this; refusing their numbers is the cost, and it is the right
	// way round, because the alternative is showing most of one.
	groups := digitRuns(base)
	max := 4
	if strings.HasPrefix(base, "+") {
		max = 5
	}
	if groups > max {
		return false
	}
	digits := strings.TrimPrefix(phoneCanon(base), "+")
	if strings.HasPrefix(base, "+") {
		// E.164 caps at fifteen. The floor here is TEN rather than the
		// eight E.164 technically permits, and that is a deliberate
		// narrowing: a country code plus a national number reaches ten
		// for every country anybody in this corpus dials, while eight
		// admits "+10 000 000" out of the sentence "Growth of
		// +10 000 000 users". Refusing a genuinely short international
		// number is the safe direction; boxing a growth figure is not.
		return len(digits) >= 10 && len(digits) <= 15
	}
	// A national number, canonicalised to +353 above, so the national
	// form was 0 plus what follows. Irish numbers are 9 or 10 digits
	// including the trunk 0 — 01 xxx xxxx, 021 xxx xxxx, 08x xxx xxxx.
	//
	// Nine-or-ten rather than "eight or more" is load-bearing: a date
	// written 01-02-2024 leads with a 0, carries separators, and is eight
	// digits. Widening this bound puts dates in the box.
	n := len(digits) - len("353") + 1
	return n == 9 || n == 10
}

// digitRuns counts the separator-delimited runs of digits in a span.
func digitRuns(s string) int {
	n, in := 0, false
	for i := 0; i < len(s); i++ {
		if s[i] >= '0' && s[i] <= '9' {
			if !in {
				n++
				in = true
			}
			continue
		}
		in = false
	}
	return n
}

// extRe finds a trailing extension, so canon and valid can treat the base
// number and the extension separately while the SPAN keeps both.
var extRe = regexp.MustCompile(`(?i)[` + sep + `]*(?:ext|extension|x)\.?[` + sep + `]*[0-9]{1,6}$`)

func splitExt(s string) (base, ext string) {
	if m := extRe.FindStringIndex(s); m != nil {
		return s[:m[0]], s[m[0]:]
	}
	return s, ""
}

func onlyDigits(s string) string {
	var b strings.Builder
	for _, r := range s {
		if r >= '0' && r <= '9' {
			b.WriteRune(r)
		}
	}
	return b.String()
}

// ibanAlphabet holds the lengths IBANs have, by country. An unknown
// country is refused rather than guessed: mod-97 alone admits roughly one
// random string in ninety-seven, and the length is what makes the check
// worth having.
var ibanLength = map[string]int{
	"IE": 22, "GB": 22, "DE": 22, "FR": 27, "ES": 24, "NL": 18,
	"IT": 27, "BE": 16, "PT": 25, "AT": 20, "PL": 28, "SE": 24,
	"DK": 18, "FI": 18, "NO": 15, "CH": 21, "LU": 20, "GR": 27,
}

// ibanValid is ISO 13616's mod-97 check: move the first four characters
// to the end, map letters to two-digit numbers, and the whole thing
// modulo 97 must be 1.
//
// Verified before it was written, against IE29AIBK93115212345678,
// GB82WEST12345698765432 and DE89370400440532013000, and against the
// first of those with one digit changed. A checksum is the one thing in
// this package that can be checked against the world rather than against
// a fixture somebody here wrote, so it was.
func ibanValid(s string) bool {
	if len(s) < 15 || len(s) > 34 {
		return false
	}
	want, known := ibanLength[s[:2]]
	if !known || len(s) != want {
		return false
	}
	rem := 0
	for _, c := range s[4:] + s[:4] {
		switch {
		case c >= '0' && c <= '9':
			rem = (rem*10 + int(c-'0')) % 97
		case c >= 'A' && c <= 'Z':
			rem = (rem*100 + int(c-'A') + 10) % 97
		default:
			return false
		}
	}
	return rem == 1
}

// vatCheckAlphabet is Revenue's check-letter table, indexed by the
// weighted sum modulo 23. W is zero.
const vatCheckAlphabet = "WABCDEFGHIJKLMNOPQRSTUV"

// vatValid checks an Irish VAT number's check letter.
//
// Modern format only — seven digits, a check letter, optionally a second
// letter. **The old style, with a letter or + or * in second position, is
// refused deliberately.** A refused VAT number is a box that does not
// appear; an admitted wrong one is a fact on the page, and between those
// two the choice is not close.
//
// Verified against IE6388047V and IE3628739L, and against the invented
// IE1234567X, which it refuses. index/rank_test.go's own IE3384527RH
// passes, which is what makes that fixture usable as a corpus here.
func vatValid(s string) bool {
	s = strings.TrimPrefix(s, "IE")
	if len(s) != 8 && len(s) != 9 {
		return false
	}
	sum := 0
	for i := 0; i < 7; i++ {
		if s[i] < '0' || s[i] > '9' {
			return false
		}
		sum += int(s[i]-'0') * (8 - i)
	}
	if len(s) == 9 {
		j := strings.IndexByte(vatCheckAlphabet, s[8])
		if j < 0 {
			return false
		}
		sum += j * 9
	}
	return s[7] == vatCheckAlphabet[sum%23]
}

// ---------------------------------------------------------------------
// The label.
// ---------------------------------------------------------------------

// MaxLabel is how long a document-authored label may be, in characters.
//
// **A guess.** What is not a guess is that it has to clear the motivating
// fixture in index/rank_test.go, whose longer label — "We also have the
// following unused phone numbers" — is 47.
const MaxLabel = 60

// abbreviations are the full stops that do not end a sentence.
//
// **Stated as incomplete, because that is the honest form.** Draft 2 of
// §8.8 claimed the sentence split "fails in the safe direction"; it does
// not. A boundary placed too LATE yields a shorter run that passes every
// other test and produces a label the document never wrote — "Dr. Smith's
// direct line:" becoming "Smith's direct line". That is the composing
// failure this whole function exists to prevent, arriving through the
// function itself, so the list is what holds it and the list is short.
//
// It must not grow into a sentence tokeniser. Where it is wrong it is
// wrong in the composing direction, and knowing that is the difference
// between a limit and a surprise.
var abbreviations = map[string]bool{
	"dr.": true, "mr.": true, "mrs.": true, "ms.": true, "st.": true,
	"no.": true, "ext.": true, "ltd.": true, "co.": true,
}

// separators are what a document puts between a label and its value.
//
// The en dash is here because Word and Notion autocorrect a hyphen
// between spaces into one, so "Office – 01 547 7854" is what a document
// actually contains rather than what its author typed.
func isSeparator(r rune) bool {
	switch r {
	case ':', '—', '–', '-', '=', '\t':
		return true
	}
	return false
}

// maxLookback bounds how far sentenceStart walks.
//
// Without it this is linear in the LINE, and chunk.Split bounds a chunk
// by words rather than bytes — so a 2 MiB upload with no whitespace is
// one word, one paragraph, one chunk, and one line. Measured before this
// bound: 0.49s at 100 KB, 1.94s at 200 KB, 48.5s at 1 MB, which at the
// upload cap is minutes of search latency bought by one person's file.
//
// **It changes an outcome in one case, and draft 2's claim that it
// changes none was wrong.** Four hundred bytes is always more than
// MaxLabel runes UNLESS most of them are whitespace, which TrimSpace
// then removes: five hundred characters, four hundred and fifty spaces,
// then "Phone: 01 547 7854" yields the document's own label where the
// uncapped walk yielded none. That is the better answer and it is the
// direction this file prefers everywhere else, so the bound stays — but
// stated, because "changes no outcome" is the kind of claim that stops
// anybody checking.
const maxLookback = 400

// sentenceStart walks back from at to the start of the enclosing sentence
// or line, bounded by maxLookback.
func sentenceStart(text string, at int) int {
	floor := at - maxLookback
	if floor < 0 {
		floor = 0
	}
	for i := at - 1; i > floor; i-- {
		if text[i] == '\n' {
			return i + 1
		}
		if text[i] != ' ' || (text[i-1] != '.' && text[i-1] != '!' && text[i-1] != '?') {
			continue
		}
		// A full stop followed by a space. Whether it ends a sentence
		// depends on the word it is attached to.
		w := i
		for w > floor {
			r, size := utf8.DecodeLastRuneInString(text[floor:w])
			if size == 0 || isWordBreak(r) {
				break
			}
			w -= size
		}
		if isAbbreviation(text[w:i]) {
			continue
		}
		return i + 1
	}
	return floor
}

// isWordBreak ends the backward word walk. **NBSP counts**, and it did
// not at first: Word and Notion glue "Contact\u00a0Dr." into one token,
// which then matched no abbreviation, so the boundary was taken and the
// label came back as "Smith's direct line" — the composing failure the
// abbreviation list exists to prevent, arriving through a space nobody
// can see.
func isWordBreak(r rune) bool {
	return r == ' ' || r == '\n' || r == '\t' || r == '\u00a0'
}

// isAbbreviation reports whether a token ending in "." is one that does
// not end a sentence.
//
// The fixed list, plus **any single letter**, which covers the initials
// the list cannot enumerate: "J. Smith's line:" yielded "Smith's line"
// before this, and there is no list of every initial.
func isAbbreviation(tok string) bool {
	if abbreviations[strings.ToLower(tok)] {
		return true
	}
	// Decoded as RUNES, not bytes. `len(tok) == 2 && rune(tok[0])` read a
	// raw byte as a code point, so "Planta 2\u00ba. Tel\u00e9fono:" saw
	// 0xBA as the letter "\u00ba" and swallowed the sentence boundary,
	// while "\u00c9. Dupont's line:" was still cut to "Dupont's line" —
	// wrong in both directions at once, and the second is the composing
	// direction §8.8 calls the unsafe one.
	r, size := utf8.DecodeRuneInString(tok)
	return size > 0 && len(tok) == size+1 && tok[size] == '.' && unicode.IsLetter(r)
}

// listMarker is one leading list marker: a bullet, a number, a to-do box
// after either, or a quote. memoria's own Notion renderer writes these
// (notion/markdown.go), and rule 1 anchors the run at the start of the
// line, so without this the label carried memoria's syntax: "- Office".
var listMarker = regexp.MustCompile(`^[ \t\x{00A0}]*(?:(?:[-*+•]|[0-9]{1,3}[.)])[ \x{00A0}]+(?:\[[ xX]\][ \x{00A0}]+)?|>[ \x{00A0}]+)`)

// labelOf applies §8.8's label rules. It returns the label, whether the
// document wrote it (rule 2) rather than it being the fallback (rule 5),
// and whether the kind renders no box because that label is too long
// (rule 4) — in which case the label is returned too, for matching only.
//
// The order of the rules is the whole of it, and each one is here because
// a fixture broke without it — see gate 37, which carries one per case.
func labelOf(text string, start int, spans [][2]int, heading, title string) (string, bool, bool) {
	b := sentenceStart(text, start)
	// **An earlier recognised span inside the run is not part of the
	// label.** Without this, "Phone: 01 547 7854 - 01 598 1234" labels
	// the SECOND number with the first one's value — a box whose left
	// column is another phone number.
	//
	// A binary search over spans sorted by start, not a scan of all of
	// them: scanning made this quadratic in the facts a chunk holds, and
	// a chunk can hold tens of thousands of them.
	if e := lastSpanEndBefore(spans, start); e > b {
		b = e
	}
	run := strings.TrimRight(text[b:start], "  ")
	// A leading list marker is markup. The pattern needs a space after
	// the marker and run is already trimmed on the right, so whatever it
	// matches has something after it: a bare bullet — "- +353 1 547
	// 7854" — trims to "-", does not match, and rule 3 still sends it to
	// the trail. (A guard for "nothing follows" was written and removed:
	// no input could reach it.)
	if m := listMarker.FindStringIndex(run); m != nil {
		run = run[m[1]:]
	}
	if r, size := utf8.DecodeLastRuneInString(run); size > 0 && isSeparator(r) {
		lbl := strings.TrimSpace(run[:len(run)-size])
		switch {
		case lbl == "":
			// A markdown bullet: chunk.Split keeps lines verbatim, so
			// "- +353 1 547 7854" gives a run of "-", which ends in a
			// separator and names nothing. Falling through keeps a plain
			// contact list boxable; returning "" would make two bullets
			// collide and suppress it.
		case utf8.RuneCountInString(lbl) > MaxLabel:
			return lbl, true, true
		default:
			return lbl, true, false
		}
	}
	if heading != "" {
		return heading, false, false
	}
	return title, false, false
}

// lastSpanEndBefore returns the end of the latest span finishing at or
// before at. spans must be sorted by END — see the sort in Scan.
func lastSpanEndBefore(spans [][2]int, at int) int {
	lo, hi, out := 0, len(spans)-1, 0
	for lo <= hi {
		mid := (lo + hi) / 2
		if spans[mid][1] <= at {
			if spans[mid][1] > out {
				out = spans[mid][1]
			}
			lo = mid + 1
		} else {
			hi = mid - 1
		}
	}
	return out
}

// ---------------------------------------------------------------------
// Scan.
// ---------------------------------------------------------------------

// Scan returns every validated fact of the wanted kinds in text.
//
// heading and title are the label fallbacks, in that order, and title is
// the last one on purpose: an upload with no headings at all is the
// common pasted-file shape, and falling through to an empty label there
// is the case every fixture carrying a heading would hide.
//
// **This runs over a passage that has already passed §4.1.** Nothing in
// this package knows about authorization, and that is the point: by
// construction there is no way to reach it with a passage the reader may
// not see, because the caller has only the ruled results to hand it.
func Scan(text, heading, title string, want []Kind) []Found {
	wanted := map[Kind]bool{}
	for _, k := range want {
		wanted[k] = true
	}

	// Every span of EVERY kind is located first, and every label is
	// derived afterwards. Two separate reasons, both found by review:
	//
	//   - labelOf needs to know about the spans to its left, and cannot
	//     if it is called as they are found.
	//   - **the spans it needs are of every kind, not just the wanted
	//     ones.** Locating only what was asked for made a fact's label
	//     depend on which kinds the query named: "Email paul@tito.io or
	//     phone: 01 547 7854" asked for `phone` alone came back labelled
	//     "Email paul@tito.io or phone", one fact's value inside
	//     another's label — which is exactly what the earlier-span rule
	//     exists to stop, reappearing because the rule could not see the
	//     span.
	type hit struct {
		kind      Kind
		at        [2]int
		span      string
		canonical string
	}
	var hits []hit
	var spans [][2]int
	for _, r := range recognisers {
		for _, m := range r.re.FindAllStringIndex(text, -1) {
			span := text[m[0]:m[1]]
			c := r.canon(span)
			if !r.valid(span, c) {
				continue
			}
			spans = append(spans, [2]int{m[0], m[1]})
			if wanted[r.kind] {
				hits = append(hits, hit{r.kind, [2]int{m[0], m[1]}, span, c})
			}
		}
	}
	// Sorted by END, not by start, because lastSpanEndBefore searches on
	// the end and spans NEST: a phone number inside an email address, or
	// inside an IBAN, is a real pair. Sorted by start the predicate is
	// non-monotonic and the binary search can miss the enclosing span,
	// which puts a recognised value back inside another fact's label.
	sort.Slice(spans, func(i, j int) bool { return spans[i][1] < spans[j][1] })
	sort.SliceStable(hits, func(i, j int) bool { return hits[i].at[0] < hits[j].at[0] })

	// **Deduped BEFORE labels are derived, not after.** A label costs a
	// backward walk, and a chunk repeating one value ten thousand times
	// needs exactly one. The caller dedupes across passages on the same
	// key and keeps the first, so doing it here keeps the same
	// occurrence and changes no outcome.
	seen := map[Kind]map[string]bool{}
	var out []Found
	for _, k := range order {
		if !wanted[k] {
			continue
		}
		for _, h := range hits {
			if h.kind != k {
				continue
			}
			if seen[k] == nil {
				seen[k] = map[string]bool{}
			}
			if seen[k][h.canonical] {
				continue
			}
			seen[k][h.canonical] = true
			lbl, own, noBox := labelOf(text, h.at[0], spans, heading, title)
			out = append(out, Found{
				Kind:      h.kind,
				Span:      h.span,
				Canonical: h.canonical,
				Label:     lbl,
				Own:       own,
				NoBox:     noBox,
			})
		}
	}
	return out
}

// Kinds returns the render order, so a caller applying §8.8's per-kind
// rules produces the same boxes in the same places on every request.
func Kinds() []Kind { return append([]Kind(nil), order...) }

// ---------------------------------------------------------------------
// What §8.9's model half borrows from this layer.
//
// Exported so the model half uses THIS code rather than a copy of it: a
// second implementation of the label rules is how a model row would come
// to be labelled differently from a validated row sitting beside it,
// with nothing to say which rule was which.
// ---------------------------------------------------------------------

// RecognisedSpans returns the byte range of every validated fact of every
// kind in text, sorted by end.
//
// §8.9 refuses a model's span that lies inside one of these — a street
// name inside an email address is not an address — and needs the ranges
// of ALL kinds for the same reason Scan does: the answer must not depend
// on which kinds the query happened to name.
func RecognisedSpans(text string) [][2]int {
	var spans [][2]int
	for _, r := range recognisers {
		for _, m := range r.re.FindAllStringIndex(text, -1) {
			span := text[m[0]:m[1]]
			if r.valid(span, r.canon(span)) {
				spans = append(spans, [2]int{m[0], m[1]})
			}
		}
	}
	sort.Slice(spans, func(i, j int) bool { return spans[i][1] < spans[j][1] })
	return spans
}

// LabelAtSpans applies §8.8's five label rules to a value at byte offset
// start. It returns the label, and whether the kind must render no box
// because the document labelled the value too long to show — in which
// case the label is the over-long one, exactly as Scan reports it, and
// must not be rendered.
//
// spans are the passage's RecognisedSpans, computed once by the caller.
// **There is deliberately no variant that computes them itself.** One
// existed — LabelAt — and a review showed that swapping it in for this
// function passed the whole suite while recomputing every recogniser per
// label: 6.8 seconds for a legal-sized model response. Removing it makes
// that mistake a compile error instead of a timing regression nothing
// could see.
func LabelAtSpans(text string, start int, spans [][2]int, heading, title string) (string, bool) {
	l, _, noBox := labelOf(text, start, spans, heading, title)
	return l, noBox
}

// WordBounded reports whether text[start:end] begins and ends on a word
// boundary — neither neighbour is a letter or a digit.
//
// §8.9 requires it of a model's span, because an exact byte match inside
// a longer word ("Street" found in "Streetside") reproduces source bytes
// and names nothing.
func WordBounded(text string, start, end int) bool {
	if start < 0 || end > len(text) || start >= end {
		return false
	}
	if start > 0 {
		if r, _ := utf8.DecodeLastRuneInString(text[:start]); isWordRune(r) {
			return false
		}
	}
	if end < len(text) {
		if r, _ := utf8.DecodeRuneInString(text[end:]); isWordRune(r) {
			return false
		}
	}
	return true
}

func isWordRune(r rune) bool { return unicode.IsLetter(r) || unicode.IsDigit(r) }