steeldb/

emergent.rs

//! **Emergent ontology from prose** — discover facets from unlabelled natural language, with no model and
//! no planted hints.
//!
//! Field sensing (`vocabulary::candidate_fields`) reads `- **Field:** value` markers. That works, but those
//! markers are a schema someone already wrote into the document: sensing them is reading an answer key, not
//! discovering structure. Real corpora are prose, and on prose field sensing returns nothing at all.
//!
//! This module discovers the vocabulary the hard way:
//!
//! 1. **Salience** — score every term by TF-IDF across the corpus. A term in every document distinguishes
//!    nothing; a term in one document is noise. What survives is the vocabulary that carves the corpus up.
//! 2. **Co-occurrence** — represent each term by the set of documents it appears in, and measure terms by
//!    how much those sets overlap. Terms naming the same *kind* of thing occur in the same places.
//! 3. **Agglomeration** — merge the closest clusters until the requested number remain, so the taxonomy is
//!    built bottom-up out of the corpus rather than imposed on it.
//! 4. **Labelling** — name each cluster by its most distinctive term, again by TF-IDF.
//!
//! Every step is deterministic and dependency-free, which is what lets it run in the browser. An
//! embedding-based clusterer would be sharper, but it needs a tokenizer that cannot target wasm32 — and a
//! demo that cannot run the real thing is worth less than a slightly blunter one that can.

use std::collections::{HashMap, HashSet};

/// A discovered group of co-occurring terms — a candidate facet before the MECE gate has ruled on it.
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
pub struct TermCluster {
    /// most distinctive term in the cluster, used as the facet name
    pub label: String,
    /// members, most salient first
    pub terms: Vec<String>,
    /// fraction of the corpus in which at least one member appears
    pub coverage: f64,
    /// mean pairwise co-occurrence similarity — how tightly the group holds together
    pub cohesion: f64,
}

/// Terms that appear capitalised mid-sentence are proper nouns: names of individuals, not names of kinds.
///
/// They belong in a facet's MEMBERS (they are the instances it collects) but make poor LABELS — labelling
/// the battle cluster `gale` after a trainer's surname describes one competitor, not the category. A term is
/// treated as a common noun when the corpus writes it in lowercase at least sometimes.
pub fn common_nouns(docs: &[String]) -> HashSet<String> {
    let mut lower_seen: HashSet<String> = HashSet::new();
    for doc in docs {
        for raw in doc.split(|c: char| !c.is_alphanumeric() && c != '-' && c != '\'') {
            let t = raw.trim_matches('-');
            if t.len() < 3 {
                continue;
            }
            // first character lowercase in the source text
            if t.chars().next().map(|c| c.is_lowercase()).unwrap_or(false) {
                lower_seen.insert(t.to_lowercase());
            }
        }
    }
    lower_seen
}

fn tokenize(s: &str) -> Vec<String> {
    s.split(|c: char| !c.is_alphanumeric() && c != '-' && c != '\'')
        .map(|w| w.trim_matches('-').to_lowercase())
        .filter(|w| {
            w.len() >= 3
                && w.len() <= 28
                && w.chars().next().map(|c| c.is_alphabetic()).unwrap_or(false)
                // a bare number is a value, not a name for a kind of thing
                && !w.chars().all(|c| c.is_ascii_digit())
        })
        .collect()
}

const STOP: &[&str] = &[
    "the", "and", "for", "with", "was", "were", "this", "that", "from", "into", "are", "has", "had", "his",
    "her", "its", "not", "but", "all", "any", "may", "can", "will", "each", "than", "then", "during",
    "under", "over", "also", "which", "while", "their", "there", "been", "being", "who", "when", "what",
    "how", "why", "per", "via", "such", "more", "most", "less", "other", "some", "one", "two", "three",
    "against", "after", "before", "between", "both", "out", "off", "own", "same", "too", "very", "just",
    "him", "she", "they", "them", "these", "those", "have", "does", "did", "doing", "would", "could",
    "should", "must", "shall", "about", "above", "below", "again", "further", "once", "here", "only",
    "remains", "stands", "recorded", "reported", "held", "took", "made", "including", "included",
];

/// Select the candidate mentions to cluster — the members of the reified situations.
///
/// This step deliberately does **no TF-IDF**. TF-IDF measures how well a term distinguishes one group from
/// others, so it can only be applied once groups exist; using it to pick the input would be scoring terms
/// against a partition that has not been computed yet. Selection is therefore a plain document-frequency
/// window: a mention in nearly every situation separates nothing, and one appearing once cannot be a
/// dimension. TF-IDF enters later, in [`name_cluster`], where it replaces an LLM naming call.
fn salient_terms(docs: &[String], n_terms: usize) -> Vec<(String, HashSet<usize>)> {
    let mut incidence: HashMap<String, HashSet<usize>> = HashMap::new();
    let mut tf: HashMap<String, usize> = HashMap::new();
    for (i, doc) in docs.iter().enumerate() {
        for w in tokenize(doc) {
            if STOP.contains(&w.as_str()) || GENERIC.contains(&w.as_str()) || LOCATIVES.contains(&w.as_str()) {
                continue;
            }
            *tf.entry(w.clone()).or_default() += 1;
            incidence.entry(w).or_default().insert(i);
        }
    }

    let n = docs.len().max(1) as f64;
    let min_df = 2usize;
    let max_df = ((n * 0.85).ceil() as usize).max(min_df + 1);

    // rank only by how often the mention occurs, inside the frequency window; no relevance weighting here
    let mut scored: Vec<(String, f64)> = incidence
        .iter()
        .filter(|(_, docs_in)| docs_in.len() >= min_df && docs_in.len() <= max_df)
        .map(|(term, _)| (term.clone(), *tf.get(term).unwrap_or(&1) as f64))
        .collect();
    scored.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal).then(a.0.cmp(&b.0)));
    scored.truncate(n_terms);

    scored
        .into_iter()
        .map(|(term, _)| {
            let docs_in = incidence.remove(&term).unwrap_or_default();
            (term, docs_in)
        })
        .collect()
}

/// Latent motifs: themes a situation can join through terms that travel together, with no keyword in common.
///
/// This is the paper's sixth dimension. The reference implementation gets motifs from SPLADE activations, which
/// need a trained model; the paper permits optimal transport over the co-occurrence geometry as the alternative,
/// and that is what this does — the same solver as [`discover`], at a lower epsilon so each term commits to one
/// theme rather than hedging across all of them.
///
/// Returns `(name, member terms)`. A motif is named by its first member that is a corpus common noun, because a
/// theme should read as a kind of thing rather than as a proper name.
pub fn discover_motifs(docs: &[String], n_terms: usize, k: usize) -> Vec<(String, Vec<String>)> {
    let (terms, vecs) = term_vectors(docs, n_terms);
    if terms.len() < 2 || k == 0 {
        return Vec::new();
    }
    let (_protos, assign, _cost) = crate::text::ot::codebook(&vecs, k, MOTIF_EPS);
    let groups = assign.iter().copied().max().map_or(0, |m| m + 1);
    let mut members: Vec<Vec<String>> = vec![Vec::new(); groups];
    for (i, &a) in assign.iter().enumerate() {
        members[a].push(terms[i].clone());
    }
    let commons = common_nouns(docs);
    members
        .into_iter()
        .filter(|g| !g.is_empty())
        .filter_map(|g| {
            let name = g.iter().find(|t| commons.contains(*t)).or_else(|| g.first())?.clone();
            (!name.is_empty()).then_some((name, g))
        })
        .collect()
}

/// Entropy regularisation for motifs, below [`DISCOVER_EPS`] so a term commits to a single theme.
const MOTIF_EPS: f32 = 0.03;

/// Entropy regularisation for discovery, from the reference implementation's `--eps` default. Lower makes
/// each term commit to one facet; higher spreads it across several.
pub const DISCOVER_EPS: f32 = 0.05;

/// L2-normalised document-incidence vectors for the top salient terms, plus the terms themselves.
///
/// This is what lets optimal transport run with no embedding model. A term's "position" is simply the set of
/// documents it appears in, written as a vector of 0s and 1s and normalised — so cosine similarity between
/// two terms is exactly their co-occurrence. The Sinkhorn core takes a cost matrix and does not care where
/// the geometry came from, and this geometry needs no tokenizer, which is what makes it run in a browser.
pub fn term_vectors(docs: &[String], n_terms: usize) -> (Vec<String>, Vec<Vec<f32>>) {
    let picked = salient_terms(docs, n_terms);
    let n = docs.len().max(1);
    let mut names = Vec::with_capacity(picked.len());
    let mut vecs = Vec::with_capacity(picked.len());
    for (term, docs_in) in picked {
        let mut v = vec![0f32; n];
        for i in &docs_in {
            if *i < n {
                v[*i] = 1.0;
            }
        }
        let norm = v.iter().map(|x| x * x).sum::<f32>().sqrt() + 1e-9;
        vecs.push(v.into_iter().map(|x| x / norm).collect());
        names.push(term);
    }
    (names, vecs)
}

/// Quantities: a number followed by a unit, returned as `(start, end, canonical field)` byte ranges.
///
/// The paper treats quantities as their own dimension, and the reference pipeline routes them away from the
/// semantic codebook entirely — a measurement is not a kind of thing, it is a value with a scale. Extracting
/// them separately is also the only way a numeric range predicate has anything to range over: without this,
/// "1082 m" is three unremarkable characters and a unit nobody recorded.
pub fn quantity_spans(doc: &str) -> Vec<(usize, usize, String)> {
    const UNITS: &[(&str, &str)] = &[
        ("mm", "length_mm"), ("cm", "length_cm"), ("km", "length_km"), ("m", "length_m"),
        ("kg", "mass_kg"), ("g", "mass_g"), ("t", "mass_t"),
        ("°c", "temp_c"), ("°f", "temp_f"), ("c", "temp_c"),
        ("minutes", "minutes"), ("minute", "minutes"), ("min", "minutes"),
        ("hours", "hours"), ("hour", "hours"), ("seconds", "seconds"),
        ("mm/yr", "rainfall_mm"), ("%", "percent"),
    ];
    let b = doc.as_bytes();
    let mut out = Vec::new();
    let mut i = 0usize;
    while i < b.len() {
        // start of a number, not mid-word
        if b[i].is_ascii_digit() && (i == 0 || !(b[i - 1] as char).is_alphanumeric()) {
            // A leading minus belongs to the number. Dropping it turned "-7 °C" into 7 °C, so a sub-zero
            // reading indexed as above zero — a wrong answer, not a missing one. Only counts when the sign
            // directly precedes the digits and itself follows a boundary, so the hyphen in "11-minute" and
            // ranges like "5-10" are not mistaken for a sign.
            let mut start = i;
            if i > 0 && b[i - 1] == b'-' {
                let before_sign = i >= 2 && !(b[i - 2] as char).is_alphanumeric() && b[i - 2] != b'-';
                if i == 1 || before_sign {
                    start = i - 1;
                }
            }
            let mut j = i;
            while j < b.len() && (b[j].is_ascii_digit() || b[j] == b'.' || b[j] == b',') {
                j += 1;
            }
            let num_end = j;
            // optional separators (space, hyphen, non-breaking space) then the unit
            let mut k = j;
            while k < b.len() && (b[k] == b' ' || b[k] == b'-') {
                k += 1;
            }
            if k < b.len() && doc.is_char_boundary(k) {
                let rest = &doc[k..];
                let unit_len = rest
                    .char_indices()
                    .take_while(|(_, c)| c.is_alphabetic() || *c == '°' || *c == '%' || *c == '/')
                    .map(|(bi, c)| bi + c.len_utf8())
                    .last()
                    .unwrap_or(0);
                if unit_len > 0 {
                    let unit = rest[..unit_len].to_lowercase();
                    // longest unit match wins, so "km" is not read as "m"
                    let mut best: Option<(&str, usize)> = None;
                    for (u, field) in UNITS {
                        if unit == *u && best.map(|(_, l)| u.len() > l).unwrap_or(true) {
                            best = Some((field, u.len()));
                        }
                    }
                    if let Some((field, ulen)) = best {
                        let end = k + ulen;
                        if doc.is_char_boundary(start) && doc.is_char_boundary(end) {
                            out.push((start, end, field.to_string()));
                            i = end;
                            continue;
                        }
                    }
                }
            }
            i = num_end.max(i + 1);
            continue;
        }
        i += 1;
    }
    out
}

/// Whole-word containment test, for checking whether a document participates in a term group.
pub fn contains_term(hay: &str, needle: &str) -> bool {
    !word_spans(hay, needle).is_empty()
}

/// Relation verbs worth binding a role to. A curated list rather than a morphological guess: "-ed" also ends
/// plenty of adjectives ("distinctive", "detailed"), and a false relation is worse than a missing one because
/// it asserts a direction that was never stated.
const REL_VERBS: &[(&str, &str)] = &[
    ("defeated", "defeated"), ("beat", "defeated"), ("faced", "faced"), ("met", "faced"),
    ("documented", "documented"), ("recorded", "recorded"), ("measured", "measured"),
    ("observed", "observed"), ("found", "observed"), ("held", "held_at"), ("hosted", "held_at"),
    ("used", "used"), ("led", "used"), ("answered", "answered_with"), ("commanded", "commanded"),
    ("permitted", "permitted"), ("banned", "banned"), ("restricted", "restricted"),
    ("competed", "competed_in"), ("entered", "competed_in"), ("won", "won"), ("secured", "secured"),
    ("contributes", "contributes_to"), ("supplies", "supplies"), ("operates", "operates"),
];

/// One directional relation read out of a sentence.
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
pub struct Relation {
    /// canonical predicate name
    pub verb: String,
    /// the mention on the acting side
    pub actor: String,
    /// the mention on the receiving side
    pub target: String,
}

/// Extract directional relations from prose by pattern: mention, relation verb, mention.
///
/// This is deliberately not a model. The span tagger produces better relations, but it cannot run in a
/// browser, and leaving the dimension empty misrepresents the system more than a conservative extractor does.
///
/// Direction is the whole point. The mention on the left of the verb becomes the actor (`+`), the one on the
/// right the target (`-`). Storing them as separate tags is what makes a reversed relation
/// *unrepresentable* rather than merely wrong: there is no tag that means "supplied by" hiding inside
/// `rel/supplies/+`.
///
/// Only the nearest mention on each side is taken, and only within a single sentence, because a relation
/// inferred across a sentence boundary is a guess about coreference rather than something the text states.
pub fn relation_spans(doc: &str, mentions: &[String]) -> Vec<Relation> {
    let mut out: Vec<Relation> = Vec::new();
    for sentence in doc.split(['.', ';', '!', '?', '\n']) {
        if sentence.trim().is_empty() {
            continue;
        }
        // locate every mention in this sentence, longest first so a full name beats its prefix
        let mut found: Vec<(usize, usize, String)> = Vec::new();
        for m in mentions {
            for (s, e) in word_spans(sentence, m) {
                if !found.iter().any(|(fs, fe, _)| s >= *fs && e <= *fe) {
                    found.push((s, e, m.clone()));
                }
            }
        }
        // The corpus gazetteer only keeps mentions that RECUR, which is right for building vocabulary and
        // wrong for reading a relation: "Juan Tide defeated Cynthia Ward" states a fact about two people
        // whether or not either name appears twice. So names found in this sentence count too.
        for (s, e, name) in local_mentions(sentence) {
            if !found.iter().any(|(fs, fe, _)| s < *fe && e > *fs) {
                found.push((s, e, name));
            }
        }
        if found.len() < 2 {
            continue;
        }
        found.sort_by_key(|(s, _, _)| *s);

        for (raw, canon) in REL_VERBS {
            for (vs, ve) in word_spans(sentence, raw) {
                // nearest mention ending before the verb, and nearest starting after it
                let actor = found.iter().filter(|(_, e, _)| *e <= vs).next_back();
                let target = found.iter().find(|(s, _, _)| *s >= ve);
                if let (Some((_, _, a)), Some((_, _, t))) = (actor, target) {
                    if a != t {
                        out.push(Relation { verb: canon.to_string(), actor: a.clone(), target: t.clone() });
                    }
                }
            }
        }
    }
    out.dedup_by(|a, b| a.verb == b.verb && a.actor == b.actor && a.target == b.target);
    out
}

/// Capitalised runs inside a single sentence — mentions that need no corpus-wide support to be real.
///
/// Used for relation extraction, where a one-off name is still a participant. Deliberately not used to build
/// the vocabulary, because a mention seen once cannot define a retrieval dimension.
///
/// The first word of a sentence is skipped: its capital is grammar, not a name.
pub fn local_mentions(sentence: &str) -> Vec<(usize, usize, String)> {
    // Iterate CHARACTERS, not bytes. Casting a raw byte to char treats a UTF-8 continuation byte as a
    // Latin-1 character, so word boundaries land mid-character and slicing panics — "Pokémon" and "28 °C"
    // both trigger it.
    let is_word = |c: char| c.is_alphanumeric() || c == '\'' || c == '-';

    let mut words: Vec<(usize, usize, &str)> = Vec::new();
    let mut cur: Option<usize> = None;
    for (i, c) in sentence.char_indices() {
        if is_word(c) {
            if cur.is_none() {
                cur = Some(i);
            }
        } else if let Some(st) = cur.take() {
            words.push((st, i, &sentence[st..i]));
        }
    }
    if let Some(st) = cur {
        words.push((st, sentence.len(), &sentence[st..]));
    }

    // Runs are collected as word-index ranges first, so the sentence-opening word can be reconsidered once we
    // know how long its run turned out to be.
    let mut runs: Vec<(usize, usize)> = Vec::new();
    let mut run: Option<(usize, usize)> = None;
    let mut prev_end: Option<usize> = None;
    for (wi, (st, en, w)) in words.iter().enumerate() {
        let capped = w.chars().next().map(|c| c.is_uppercase()).unwrap_or(false) && w.chars().count() > 1;
        // Punctuation ends a run even between two capitals. Without this, "in Violet City, Johto, Juan Tide
        // defeated ..." reads as one seven-word name, and the relation gets an actor that is three separate
        // things joined by commas.
        let punctuated = prev_end
            .map(|pe| sentence[pe..*st].chars().any(|c| !c.is_whitespace()))
            .unwrap_or(false);
        if punctuated {
            if let Some(r) = run.take() {
                runs.push(r);
            }
        }
        if capped {
            run = Some(match run {
                Some((rs, _)) => (rs, wi),
                None => (wi, wi),
            });
        } else if let Some(r) = run.take() {
            runs.push(r);
        }
        prev_end = Some(*en);
    }
    if let Some(r) = run {
        runs.push(r);
    }

    // Determiners that open a sentence are capitalised by grammar. Previously the whole first word was skipped,
    // which cost "Morty Shade defeated Wallace Gale" its actor: "Morty" was dropped and the relation recorded
    // `shade`. A sentence-initial capital now joins its run, and only a leading determiner is removed — so
    // "Milotic is not permitted" still yields Milotic, which is genuinely the subject.
    const DETERMINERS: &[&str] = &[
        "the", "a", "an", "this", "that", "these", "those", "their", "its", "his", "her", "our", "your", "my",
        "it", "they", "we", "he", "she", "there", "then", "when", "where", "what", "which", "who",
    ];
    let mut out: Vec<(usize, usize, String)> = Vec::new();
    for (first, last) in runs {
        let mut first = first;
        if first == 0 && DETERMINERS.contains(&words[0].2.to_lowercase().as_str()) {
            // "The Indigo Invitational" is a name wearing an article; "The survey" is not a name at all
            first += 1;
        }
        if first > last {
            continue;
        }
        let (rs, re) = (words[first].0, words[last].1);
        out.push((rs, re, sentence[rs..re].to_string()));
    }
    out
}

/// Temporal loci: years and quarters, as `(start, end, bucket token)` byte ranges.
///
/// Dates are the one dimension that needs neither a model nor a gazetteer — a four-digit year is
/// unambiguous. They are bucketed rather than stored as exact instants, because the engine matches sets: a
/// query asks for `time/2026/q3`, not for an interval comparison. Bucketing is what turns a continuous axis
/// into something a bitmap can intersect.
pub fn temporal_spans(doc: &str) -> Vec<(usize, usize, String)> {
    let b = doc.as_bytes();
    let mut out: Vec<(usize, usize, String)> = Vec::new();

    // quarters: Q1..Q4, optionally followed by a year
    let mut i = 0usize;
    while i + 1 < b.len() {
        if (b[i] == b'Q' || b[i] == b'q') && b[i + 1].is_ascii_digit() {
            let q = (b[i + 1] - b'0') as u32;
            let starts_word = i == 0 || !(b[i - 1] as char).is_alphanumeric();
            if (1..=4).contains(&q) && starts_word {
                let end = i + 2;
                // look ahead for a year so the bucket can be fully qualified
                let tail = &doc[end..].trim_start();
                let year: Option<u32> = tail
                    .split(|c: char| !c.is_ascii_digit())
                    .next()
                    .filter(|t| t.len() == 4)
                    .and_then(|t| t.parse().ok())
                    .filter(|y| (1900..2200).contains(y));
                let token = match year {
                    Some(y) => format!("time/{y}/q{q}"),
                    None => format!("time/q{q}"),
                };
                if doc.is_char_boundary(i) && doc.is_char_boundary(end) {
                    out.push((i, end, token));
                }
                i = end;
                continue;
            }
        }
        i += 1;
    }

    // bare years
    let mut j = 0usize;
    while j + 3 < b.len() {
        if b[j].is_ascii_digit() {
            let before_ok = j == 0 || !(b[j - 1] as char).is_alphanumeric();
            let end = j + 4;
            let after_ok = end >= b.len() || !(b[end] as char).is_alphanumeric();
            if before_ok && after_ok && b[j..end].iter().all(|c| c.is_ascii_digit()) {
                if let Ok(y) = doc[j..end].parse::<u32>() {
                    if (1900..2200).contains(&y) && !out.iter().any(|(s, e, _)| j >= *s && end <= *e) {
                        out.push((j, end, format!("time/{y}")));
                    }
                }
                j = end;
                continue;
            }
        }
        j += 1;
    }
    out.sort_by_key(|(s, _, _)| *s);
    out
}

/// Mine multi-word proper-noun mentions — a **gazetteer** grown from the corpus itself.
///
/// Word-level matching shatters real entities: "Sootopolis City" becomes "Sootopolis" plus "City", and the
/// engine then believes it saw two unrelated things. A mention is a run of capitalised words, so the longest
/// run wins and the parts are never emitted separately.
///
/// A run is kept only if it appears at least `min_count` times across the corpus. That threshold is what
/// stops an ordinary sentence-initial word from being promoted to an entity: "The" starts many sentences but
/// never forms a repeated multi-word run with what follows.
pub fn mine_gazetteer(docs: &[String], min_count: usize) -> Vec<String> {
    let mut counts: HashMap<String, usize> = HashMap::new();
    for doc in docs {
        for sentence in doc.split(['.', '\n', ';', '!', '?']) {
            let words: Vec<&str> = sentence.split_whitespace().collect();
            let mut run: Vec<&str> = Vec::new();
            let mut first = true;
            for w in words {
                let clean = w.trim_matches(|c: char| !c.is_alphanumeric() && c != '\'' && c != '-');
                let cap = clean
                    .chars()
                    .next()
                    .map(|c| c.is_uppercase())
                    .unwrap_or(false)
                    && clean.len() > 1;
                // a sentence-initial capital carries no information, so it cannot start a run
                if cap && !(first && run.is_empty()) {
                    run.push(clean);
                } else {
                    if run.len() >= 2 {
                        *counts.entry(run.join(" ")).or_default() += 1;
                    }
                    run.clear();
                }
                first = false;
            }
            if run.len() >= 2 {
                *counts.entry(run.join(" ")).or_default() += 1;
            }
        }
    }
    let mut kept: Vec<String> =
        counts.into_iter().filter(|(_, n)| *n >= min_count).map(|(s, _)| s).collect();
    // longest first, so matching prefers the full mention over any prefix of it
    kept.sort_by(|a, b| b.len().cmp(&a.len()).then(a.cmp(b)));
    kept
}

/// Generic vocabulary that looks like a category but names no kind of thing. The reference pipeline routes
/// this class away from the codebook rather than clustering it.
/// Prepositions and locatives. These belong with `STOP`: a function word is not a kind of thing, so it can
/// neither name a category nor usefully join one, and one that occurs in most documents adds only noise to the
/// co-occurrence geometry. The list already held `during`, `under`, `over` and `between`; the omissions showed
/// up as a corpus whose discovered category was `near/*`.
pub const LOCATIVES: &[&str] = &[
    "near", "nearby", "across", "along", "around", "through", "throughout", "toward", "towards",
    "beside", "behind", "beyond", "upon", "onto", "inside", "outside", "amid", "among", "amongst",
    "beneath", "underneath", "alongside", "opposite", "past", "since", "until", "till", "unto",
];

pub const GENERIC: &[&str] = &[
    "within", "presence", "data", "contributes", "distribution", "environmental", "understanding",
    "preferences", "observation", "site", "location", "conditions", "period", "mean", "documented",
    "recorded", "measured", "reported", "described", "including", "various", "distinctive", "populations",
    "ecological", "information", "details", "features", "aspects", "elements", "factors", "values",
    "results", "analysis", "summary", "overview", "context", "purposes", "requirements",
];

/// Find every whole-word occurrence of `needle` in `hay`, as byte ranges.
///
/// Whole-word only: a substring match would highlight "it" inside "submitted".
pub fn word_spans(hay: &str, needle: &str) -> Vec<(usize, usize)> {
    let mut out = Vec::new();
    if needle.is_empty() {
        return out;
    }
    let lower = hay.to_lowercase();
    let pat = needle.to_lowercase();
    let bytes = lower.as_bytes();
    let mut from = 0usize;
    while let Some(rel) = lower[from..].find(&pat) {
        let s = from + rel;
        let e = s + pat.len();
        let before_ok = s == 0 || !(bytes[s - 1] as char).is_alphanumeric();
        let after_ok = e >= bytes.len() || !(bytes[e] as char).is_alphanumeric();
        // only keep it if the byte range is also a char boundary in the ORIGINAL string
        if before_ok && after_ok && hay.is_char_boundary(s) && hay.is_char_boundary(e) {
            out.push((s, e));
        }
        from = s + pat.len().max(1);
        if from >= lower.len() {
            break;
        }
    }
    out
}

/// The salience ranking on its own, for callers that want to show the intermediate step: `(term, score,
/// document frequency)`, most salient first.
pub fn salient(docs: &[String], n_terms: usize) -> Vec<(String, f64, usize)> {
    let picked = salient_terms(docs, n_terms);
    let n = docs.len().max(1) as f64;
    picked
        .into_iter()
        .map(|(term, docs_in)| {
            let d = docs_in.len();
            let idf = ((n + 1.0) / (d as f64 + 1.0)).ln() + 1.0;
            (term, idf, d)
        })
        .collect()
}

/// Name a cluster by the member term most exclusive to it — TF-IDF where a "document" is a CLUSTER.
///
/// This is the step that replaces an LLM naming call. The reference pipeline asked a model to invent a facet
/// name; here the corpus decides. A term scores highly when it is frequent inside this cluster and rare in
/// the other clusters, which is exactly what makes it a usable label for the group.
///
/// Running TF-IDF against the raw documents instead would answer a different question — "which words are
/// unusual in this corpus" — and can hand back a term that several clusters share.
///
/// Proper nouns are demoted: a facet names a KIND, and an always-capitalised term is an instance inside the
/// kind, not the name of it.
pub fn name_cluster(
    members: &[String],
    tf_in_cluster: &HashMap<String, usize>,
    clusters_containing: &HashMap<String, usize>,
    n_clusters: usize,
    cluster_size: usize,
    commons: &HashSet<String>,
    exclusivity: &HashMap<String, f64>,
) -> String {
    let n = n_clusters.max(1) as f64;
    let size = cluster_size.max(1) as f64;

    // A label has to be specific to its own group. `city` occurred in every battle document AND every survey
    // document ("Ecruteak City", "Sootopolis City"), so ranking by frequency alone named the battle category
    // `city/*` — a label that describes the corpus rather than the category, and the worst kind of wrong
    // because it reads as meaningful. Terms whose documents mostly sit in OTHER groups are therefore not
    // eligible to name this one. If that leaves nothing, every member is eligible again, since a group with no
    // specific term still needs a name.
    const MIN_EXCLUSIVITY: f64 = 0.8;
    let confined: Vec<String> = members
        .iter()
        .filter(|t| exclusivity.get(*t).copied().unwrap_or(1.0) >= MIN_EXCLUSIVITY)
        .cloned()
        .collect();
    let pool: &[String] = if confined.is_empty() { members } else { &confined };

    let mut scored: Vec<(String, f64)> = pool
        .iter()
        .map(|t| {
            let tf = *tf_in_cluster.get(t).unwrap_or(&1) as f64;
            let dfc = *clusters_containing.get(t).unwrap_or(&1) as f64;
            let idf = ((n + 1.0) / (dfc + 1.0)).ln() + 1.0;
            // A label must describe MOST of its group. Ranking by raw frequency first picked `city` for the
            // survey cluster: a frequent sub-part rather than the kind. Coverage of the cluster's own
            // situations leads, and exclusivity across clusters only breaks ties.
            let coverage = (tf / size).min(1.0);
            let common_bonus = if commons.contains(t) { 1.3 } else { 1.0 };
            (t.clone(), coverage * common_bonus + 0.12 * idf)
        })
        .collect();
    scored.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal).then(a.0.cmp(&b.0)));
    scored.first().map(|(t, _)| t.clone()).unwrap_or_default()
}

/// Cosine similarity of two document-incidence sets.
fn cosine(a: &HashSet<usize>, b: &HashSet<usize>) -> f64 {
    if a.is_empty() || b.is_empty() {
        return 0.0;
    }
    let inter = a.intersection(b).count() as f64;
    inter / ((a.len() as f64).sqrt() * (b.len() as f64).sqrt())
}

/// One node of the discovered taxonomy. Leaves are the clusters that survived the cut; internal nodes are
/// the merges that built them, so the shape is the corpus's own hierarchy rather than an imposed one.
#[derive(Debug, Clone, serde::Serialize, serde::Deserialize)]
pub struct TreeNode {
    /// cluster label for a leaf; empty for an internal merge node
    pub label: String,
    /// average-linkage similarity at which this merge happened (0 for leaves)
    pub height: f64,
    /// number of member terms beneath this node
    pub size: usize,
    pub children: Vec<TreeNode>,
}

/// Build the full dendrogram, continuing past the requested cut all the way to a single root.
///
/// The cut at `n_clusters` marks which nodes become facets; everything above it is the super-structure the
/// corpus implies. Returning the whole tree lets a viewer show both the accepted categories and how they
/// would have combined, which is the picture agglomerative clustering actually produces.
pub fn discover_hierarchy(docs: &[String], n_terms: usize, n_clusters: usize) -> Option<TreeNode> {
    let terms = salient_terms(docs, n_terms.clamp(2, 400));
    if terms.len() < 2 {
        return None;
    }
    let cut = n_clusters.clamp(1, terms.len());
    let commons = common_nouns(docs);

    // active[i] = (members, doc incidence, node)
    let mut active: Vec<(Vec<usize>, HashSet<usize>, TreeNode)> = terms
        .iter()
        .enumerate()
        .map(|(i, (t, d))| {
            (vec![i], d.clone(), TreeNode { label: t.clone(), height: 0.0, size: 1, children: Vec::new() })
        })
        .collect();

    let avg_linkage = |a: &[usize], b: &[usize]| -> f64 {
        let mut sum = 0.0;
        for x in a {
            for y in b {
                sum += cosine(&terms[*x].1, &terms[*y].1);
            }
        }
        sum / (a.len() * b.len()) as f64
    };

    // when the count reaches the cut, label the surviving groups — these are the facets
    let mut labelled = false;
    while active.len() > 1 {
        if active.len() == cut && !labelled {
            labelled = true;
            let n_c = active.len();
            let mut tf: HashMap<String, usize> = HashMap::new();
            let mut containing: HashMap<String, usize> = HashMap::new();
            for (members, docs_in, _) in &active {
                let mut seen = HashSet::new();
                for m in members {
                    let t = &terms[*m].0;
                    let c = docs_in.iter().filter_map(|i| docs.get(*i)).filter(|d| !word_spans(d, t).is_empty()).count();
                    *tf.entry(t.clone()).or_default() += c.max(1);
                    seen.insert(t.clone());
                }
                for t in seen {
                    *containing.entry(t).or_default() += 1;
                }
            }
            // the same specificity rule the flat discovery uses, computed before the mutable pass
            let excl: Vec<HashMap<String, f64>> = (0..active.len())
                .map(|ci| {
                    let others: HashSet<usize> = active
                        .iter()
                        .enumerate()
                        .filter(|(cj, _)| *cj != ci)
                        .flat_map(|(_, (_, docs_j, _))| docs_j.iter().copied())
                        .collect();
                    active[ci]
                        .0
                        .iter()
                        .map(|m| {
                            let (term, term_docs) = &terms[*m];
                            let own = term_docs.iter().filter(|d| !others.contains(d)).count() as f64;
                            (term.clone(), own / term_docs.len().max(1) as f64)
                        })
                        .collect()
                })
                .collect();
            for (ci, (members, docs_in, node)) in active.iter_mut().enumerate() {
                let names: Vec<String> = members.iter().map(|m| terms[*m].0.clone()).collect();
                node.label =
                    name_cluster(&names, &tf, &containing, n_c, docs_in.len(), &commons, &excl[ci]);
            }
        }

        let mut best: Option<(usize, usize, f64)> = None;
        for i in 0..active.len() {
            for j in (i + 1)..active.len() {
                let s = avg_linkage(&active[i].0, &active[j].0);
                if best.map(|(_, _, bs)| s > bs).unwrap_or(true) {
                    best = Some((i, j, s));
                }
            }
        }
        let Some((i, j, sim)) = best else { break };
        let (mj, dj, nj) = active.remove(j);
        let (_, _, ni) = &active[i];
        let merged = TreeNode {
            label: String::new(),
            height: sim,
            size: ni.size + nj.size,
            children: vec![active[i].2.clone(), nj],
        };
        active[i].0.extend(mj);
        active[i].1.extend(dj);
        active[i].2 = merged;
    }

    active.into_iter().next().map(|(_, _, n)| n)
}

/// Discover `n_clusters` candidate facets from prose.
///
/// `n_terms` caps how much vocabulary is considered; agglomeration is O(n_terms^3) in the worst case, so the
/// cap is what keeps this interactive in a browser.
pub fn discover(docs: &[String], n_terms: usize, n_clusters: usize) -> Vec<TermCluster> {
    let terms = salient_terms(docs, n_terms.clamp(2, 400));
    if terms.len() < 2 || n_clusters == 0 {
        return Vec::new();
    }

    // L2-normalised document-incidence vectors. A term's position is the set of documents it appears in, so
    // cosine between two terms is exactly their co-occurrence — the geometry the transport plan runs over, and
    // it needs no embedding model, which is what lets this run in a browser.
    let n_docs = docs.len().max(1);
    let vecs: Vec<Vec<f32>> = terms
        .iter()
        .map(|(_, docs_in)| {
            let mut v = vec![0f32; n_docs];
            for i in docs_in {
                if *i < n_docs {
                    v[*i] = 1.0;
                }
            }
            let norm = v.iter().map(|x| x * x).sum::<f32>().sqrt() + 1e-9;
            v.into_iter().map(|x| x / norm).collect()
        })
        .collect();

    // k-means++ prototypes, then entropy-regularised optimal transport onto them, then argmax over the plan.
    // This is the reference pipeline's `cluster()` (python/splade/spo_sinkhorn.py): eps 0.05, 200 Sinkhorn
    // iterations, 60 k-means iterations, cost `1 - cosine`, uniform marginals on both sides.
    //
    // It replaced average-linkage agglomerative clustering, which was never the paper's method. Linkage was
    // adopted here to stop one group chaining through weak similarities and swallowing the corpus, but the
    // uniform TARGET marginal rules that out structurally: no prototype can absorb more than its 1/k share of
    // the mass, so collapse is prevented by the solver rather than patched by a linkage floor.
    let (_protos, assign, _cost) = crate::text::ot::codebook(&vecs, n_clusters, DISCOVER_EPS);

    // group the terms by the target each was transported to; a prototype that won nothing is not a facet
    let k = assign.iter().copied().max().map_or(0, |m| m + 1);
    let mut clusters: Vec<(Vec<usize>, HashSet<usize>)> = vec![(Vec::new(), HashSet::new()); k];
    for (i, &a) in assign.iter().enumerate() {
        clusters[a].0.push(i);
        clusters[a].1.extend(terms[i].1.iter().copied());
    }
    clusters.retain(|(members, _)| !members.is_empty());

    let commons = common_nouns(docs);
    let n = docs.len().max(1) as f64;

    // Cluster-level statistics for naming: how often each term occurs inside its own cluster, and how many
    // clusters mention it at all. Both are needed before any cluster can be named, which is precisely why
    // naming cannot happen during selection.
    let n_clusters_final = clusters.len();
    let mut tf_in_cluster: HashMap<String, usize> = HashMap::new();
    let mut clusters_containing: HashMap<String, usize> = HashMap::new();
    for (members, docs_in) in &clusters {
        let mut seen: HashSet<String> = HashSet::new();
        for m in members {
            let term = &terms[*m].0;
            // occurrences of this member inside the cluster's own situations
            let count = docs_in
                .iter()
                .filter_map(|i| docs.get(*i))
                .filter(|d| word_spans(d, term).len() > 0)
                .count();
            *tf_in_cluster.entry(term.clone()).or_default() += count.max(1);
            seen.insert(term.clone());
        }
        for t in seen {
            *clusters_containing.entry(t).or_default() += 1;
        }
    }
    // For each cluster, how specific each member term is to it: the share of the term's own documents that no
    // OTHER cluster claims. Measuring against the cluster's own union would be vacuous, because that union is
    // built from its members' documents and every member would score 1.0.
    let exclusivity: Vec<HashMap<String, f64>> = (0..clusters.len())
        .map(|ci| {
            let others: HashSet<usize> = clusters
                .iter()
                .enumerate()
                .filter(|(cj, _)| *cj != ci)
                .flat_map(|(_, (_, docs_j))| docs_j.iter().copied())
                .collect();
            clusters[ci]
                .0
                .iter()
                .map(|m| {
                    let (term, term_docs) = &terms[*m];
                    let own = term_docs.iter().filter(|d| !others.contains(d)).count() as f64;
                    (term.clone(), own / term_docs.len().max(1) as f64)
                })
                .collect()
        })
        .collect();

    let mut out: Vec<TermCluster> = clusters
        .iter()
        .cloned()
        .enumerate()
        .map(|(ci, (members, docs_in))| {
            // members are already in salience order, since `terms` was sorted
            let mut member_terms: Vec<String> = members.iter().map(|m| terms[*m].0.clone()).collect();

            // cohesion: mean pairwise similarity among members
            let mut sum = 0.0;
            let mut pairs = 0usize;
            for a in 0..members.len() {
                for b in (a + 1)..members.len() {
                    sum += cosine(&terms[members[a]].1, &terms[members[b]].1);
                    pairs += 1;
                }
            }
            let cohesion = if pairs == 0 { 1.0 } else { sum / pairs as f64 };

            // label by the most distinctive term: the cluster's own documents against the whole corpus
            let label = name_cluster(
                &member_terms,
                &tf_in_cluster,
                &clusters_containing,
                n_clusters_final,
                docs_in.len(),
                &commons,
                &exclusivity[ci],
            );

            member_terms.retain(|t| *t != label);
            member_terms.insert(0, label.clone());

            TermCluster { label, terms: member_terms, coverage: docs_in.len() as f64 / n, cohesion }
        })
        .filter(|c| !c.label.is_empty() && c.terms.len() > 1)
        .collect();

    out.sort_by(|a, b| b.coverage.partial_cmp(&a.coverage).unwrap_or(std::cmp::Ordering::Equal));
    out
}

#[cfg(test)]
mod tests {
    use super::*;

    fn corpus() -> Vec<String> {
        // two clearly separate domains, stated only in prose — no field markers to read
        let battles = [
            "Morty Shade defeated Wallace Gale in a battle at the tournament venue",
            "Bea Strike defeated Falkner Gale in a battle at the tournament venue",
            "Iris Draco defeated Nessa Reef in a battle at the tournament venue",
            "Marnie Dusk defeated Juan Tide in a battle at the tournament venue",
        ];
        let surveys = [
            "The survey recorded elevation and rainfall across the habitat region",
            "The survey recorded elevation and temperature across the habitat region",
            "A survey measured rainfall and elevation within the habitat region",
            "A survey measured temperature and elevation within the habitat region",
        ];
        battles.iter().chain(surveys.iter()).map(|s| s.to_string()).collect()
    }

    #[test]
    fn discovers_the_two_domains_without_any_field_markers() {
        let docs = corpus();
        let clusters = discover(&docs, 60, 2);
        assert_eq!(clusters.len(), 2, "{clusters:#?}");

        let joined: Vec<String> = clusters.iter().map(|c| c.terms.join(" ")).collect();
        let battle_cluster = joined.iter().find(|t| t.contains("battle")).expect(&format!("{joined:?}"));
        let survey_cluster = joined.iter().find(|t| t.contains("survey")).expect(&format!("{joined:?}"));

        // the domains must not be mixed together
        assert!(!battle_cluster.contains("survey"), "battle cluster leaked survey terms: {battle_cluster}");
        assert!(!survey_cluster.contains("battle"), "survey cluster leaked battle terms: {survey_cluster}");
        assert!(survey_cluster.contains("elevation"), "{survey_cluster}");
    }

    #[test]
    fn labels_are_drawn_from_the_cluster_and_are_distinctive() {
        let docs = corpus();
        for c in discover(&docs, 60, 2) {
            assert!(c.terms.contains(&c.label), "label must be a member: {c:?}");
            assert_eq!(c.terms[0], c.label, "label should lead the member list");
            assert!(!STOP.contains(&c.label.as_str()), "label is a stopword: {c:?}");
            assert!(c.coverage > 0.0 && c.coverage <= 1.0, "{c:?}");
        }
    }

    #[test]
    fn prose_with_no_shared_vocabulary_yields_nothing_rather_than_noise() {
        // no term appears in two documents, so there is no co-occurrence to discover
        let docs: Vec<String> = ["alpha beta", "gamma delta", "epsilon zeta"].iter().map(|s| s.to_string()).collect();
        assert!(discover(&docs, 40, 3).is_empty());
    }

    #[test]
    fn is_deterministic() {
        let docs = corpus();
        let a = discover(&docs, 60, 3);
        let b = discover(&docs, 60, 3);
        assert_eq!(
            a.iter().map(|c| c.terms.join(",")).collect::<Vec<_>>(),
            b.iter().map(|c| c.terms.join(",")).collect::<Vec<_>>()
        );
    }

    #[test]
    fn quantities_are_extracted_with_their_units() {
        let doc = "recorded at an elevation of 1082 m. The mean temperature was 28 °C and it ran 7 minutes.";
        let q = quantity_spans(doc);
        let got: Vec<(&str, &str)> = q.iter().map(|(s, e, f)| (&doc[*s..*e], f.as_str())).collect();
        assert!(got.contains(&("1082 m", "length_m")), "{got:?}");
        assert!(got.contains(&("28 °C", "temp_c")), "{got:?}");
        assert!(got.contains(&("7 minutes", "minutes")), "{got:?}");
    }

    #[test]
    fn km_is_not_read_as_m() {
        let doc = "a range of 500 km across";
        let q = quantity_spans(doc);
        assert_eq!(q.len(), 1, "{q:?}");
        assert_eq!(q[0].2, "length_km");
        assert_eq!(&doc[q[0].0..q[0].1], "500 km");
    }

    #[test]
    fn gazetteer_keeps_whole_mentions_not_their_parts() {
        let docs: Vec<String> = [
            "A survey in Sootopolis City recorded Aggron near the crater",
            "Another survey in Sootopolis City found more Aggron there",
            "The Indigo Invitational was held in Sootopolis City again",
        ].iter().map(|s| s.to_string()).collect();
        let g = mine_gazetteer(&docs, 2);
        assert!(g.contains(&"Sootopolis City".to_string()), "{g:?}");
        // the parts must not be promoted on their own
        assert!(!g.contains(&"Sootopolis".to_string()), "{g:?}");
        assert!(!g.contains(&"City".to_string()), "{g:?}");
        // longest-first ordering so matching prefers the full mention
        assert!(g.iter().all(|x| x.split_whitespace().count() >= 2), "{g:?}");
    }

    #[test]
    fn sentence_initial_capitals_do_not_become_entities() {
        let docs: Vec<String> = [
            "The survey found nothing. The survey ended early",
            "The survey found nothing. The survey ended early",
        ].iter().map(|s| s.to_string()).collect();
        let g = mine_gazetteer(&docs, 2);
        assert!(!g.iter().any(|x| x.starts_with("The ")), "{g:?}");
    }

    #[test]
    fn generic_words_are_not_selected_as_vocabulary() {
        let docs: Vec<String> = (0..4)
            .map(|i| format!("survey {i} recorded data within the location and the distribution of species"))
            .collect();
        let picked: Vec<String> = salient(&docs, 40).into_iter().map(|(t, _, _)| t).collect();
        for g in ["data", "within", "location", "distribution"] {
            assert!(!picked.contains(&g.to_string()), "generic term leaked: {g} in {picked:?}");
        }
        assert!(picked.contains(&"survey".to_string()) || picked.contains(&"species".to_string()), "{picked:?}");
    }

    #[test]
    fn temporal_buckets_are_extracted_and_qualified() {
        let doc = "held in Q3 2026 at the venue, following the 2025 season";
        let t = temporal_spans(doc);
        let toks: Vec<&str> = t.iter().map(|(_, _, x)| x.as_str()).collect();
        assert!(toks.contains(&"time/2026/q3"), "{toks:?}");
        assert!(toks.contains(&"time/2025"), "{toks:?}");
        // spans must index the original text
        for (s, e, _) in &t {
            assert!(doc.get(*s..*e).is_some(), "bad span {s}..{e}");
        }
    }

    #[test]
    fn a_four_digit_number_that_is_not_a_year_is_ignored() {
        // an elevation, not a date
        let t = temporal_spans("an elevation of 2369 m");
        assert!(t.iter().all(|(_, _, x)| x != "time/2369"), "{t:?}");
    }

    #[test]
    fn relations_carry_direction_from_word_order() {
        let mentions: Vec<String> = ["Morty Shade", "Wallace Gale"].iter().map(|s| s.to_string()).collect();
        let r = relation_spans("Morty Shade defeated Wallace Gale at the venue", &mentions);
        assert_eq!(r.len(), 1, "{r:?}");
        assert_eq!(r[0].verb, "defeated");
        assert_eq!(r[0].actor, "Morty Shade");
        assert_eq!(r[0].target, "Wallace Gale");

        // reversing the sentence must reverse the roles, not merely relabel them
        let rev = relation_spans("Wallace Gale defeated Morty Shade at the venue", &mentions);
        assert_eq!(rev[0].actor, "Wallace Gale");
        assert_eq!(rev[0].target, "Morty Shade");
    }

    #[test]
    fn no_relation_is_invented_across_a_sentence_boundary() {
        let mentions: Vec<String> = ["Morty Shade", "Wallace Gale"].iter().map(|s| s.to_string()).collect();
        // the verb and the second mention are in different sentences
        let r = relation_spans("Morty Shade defeated someone. Wallace Gale watched", &mentions);
        assert!(r.is_empty(), "should not link across sentences: {r:?}");
    }

    #[test]
    fn a_single_mention_yields_no_relation() {
        let mentions: Vec<String> = vec!["Morty Shade".to_string()];
        assert!(relation_spans("Morty Shade defeated everyone", &mentions).is_empty());
    }

    #[test]
    fn a_one_off_name_can_still_be_a_relation_participant() {
        // neither name recurs, so neither is in the corpus gazetteer
        let r = relation_spans("At the tournament, Juan Tide defeated Cynthia Ward in a close battle", &[]);
        assert!(!r.is_empty(), "should read the relation from local names: {r:?}");
        let d = r.iter().find(|x| x.verb == "defeated").expect("a defeated relation");
        assert_eq!(d.actor, "Juan Tide");
        assert_eq!(d.target, "Cynthia Ward");
    }

    #[test]
    fn local_mentions_skip_the_sentence_initial_capital() {
        let m = local_mentions("Juan Tide defeated Cynthia Ward");
        let names: Vec<&str> = m.iter().map(|(_, _, n)| n.as_str()).collect();
        // "Juan" opens the sentence, so the run starts at "Tide"
        assert!(names.iter().any(|n| n.contains("Cynthia Ward")), "{names:?}");
        assert!(!names.iter().any(|n| n.starts_with("Juan Tide defeated")), "{names:?}");
    }

    #[test]
    fn local_mentions_survive_multibyte_text() {
        // é and ° are multi-byte; a byte-wise scan panicked here with a slice boundary error
        for text in [
            "A Pokémon named Aggron was recorded at 28 °C by Cynthia Ward",
            "Café Ecruteak hosted Juan Tide and Bea Strike",
            "28 °C — Sootopolis City",
        ] {
            let m = local_mentions(text);
            for (s, e, name) in &m {
                assert_eq!(&text[*s..*e], name, "offsets must slice cleanly");
            }
        }
    }

    #[test]
    fn relations_survive_multibyte_text() {
        let r = relation_spans("At the venue, Juan Tide defeated Cynthia Ward and a Pokémon at 28 °C", &[]);
        assert!(r.iter().any(|x| x.actor == "Juan Tide"), "{r:?}");
    }

    #[test]
    fn punctuation_breaks_a_capitalised_run() {
        // three separate names, not one seven-word name
        let m = local_mentions("held in Violet City, Johto, Juan Tide defeated Cynthia Ward");
        let names: Vec<&str> = m.iter().map(|(_, _, n)| n.as_str()).collect();
        assert!(names.contains(&"Violet City"), "{names:?}");
        assert!(names.contains(&"Juan Tide"), "{names:?}");
        assert!(!names.iter().any(|n| n.contains(',')), "a name must not span punctuation: {names:?}");

        let r = relation_spans("held in Violet City, Johto, Juan Tide defeated Cynthia Ward", &[]);
        let d = r.iter().find(|x| x.verb == "defeated").expect("a defeated relation");
        assert_eq!(d.actor, "Juan Tide", "nearest clean name, not a comma-joined run");
        assert_eq!(d.target, "Cynthia Ward");
    }

    #[test]
    fn a_negative_quantity_keeps_its_sign() {
        let doc = "the mean temperature was -7 °C that winter";
        let q = quantity_spans(doc);
        let (s, e, f) = q.first().expect("a quantity").clone();
        assert_eq!(f, "temp_c");
        assert_eq!(&doc[s..e], "-7 °C", "the sign is part of the number");
    }

    #[test]
    fn a_hyphen_between_words_is_not_a_minus_sign() {
        // "11-minute" is a compound, not negative eleven
        let doc = "an 11-minute battle";
        let q = quantity_spans(doc);
        let (s, e, _) = q.first().expect("a quantity").clone();
        assert_eq!(&doc[s..e], "11-minute".split('-').next().unwrap().to_owned() + "-minute");
        assert!(!doc[s..e].starts_with('-'), "must not read the compound hyphen as a sign: {:?}", &doc[s..e]);
    }

    #[test]
    fn a_range_hyphen_is_not_a_minus_sign() {
        let doc = "between 5-10 m of clearance";
        for (s, e, _) in quantity_spans(doc) {
            assert!(!doc[s..e].starts_with('-'), "range hyphen read as a sign: {:?}", &doc[s..e]);
        }
    }

    #[test]
    fn a_term_spanning_two_domains_cannot_name_either() {
        // "city" occurs in every battle document AND every survey document, so it is the most frequent term in
        // whichever group transport puts it in — and naming by frequency alone labelled the battle category
        // `city/*`. A label has to be specific to its own group, or it describes the corpus instead.
        let docs: Vec<String> = [
            "Morty Shade defeated Wallace Gale in a battle at Ecruteak City",
            "Bea Strike defeated Falkner Gale in a battle at Ecruteak City",
            "Iris Draco defeated Nessa Reef in a battle at Ecruteak City",
            "The survey recorded elevation across the habitat near Sootopolis City",
            "The survey recorded rainfall across the habitat near Sootopolis City",
            "A survey measured elevation within the habitat near Sootopolis City",
        ]
        .iter()
        .map(|s| s.to_string())
        .collect();

        let clusters = discover(&docs, 60, 2);
        assert!(!clusters.is_empty(), "the two domains should still be found");
        for c in &clusters {
            assert_ne!(c.label, "city", "a term common to both domains named one of them: {c:?}");
        }
        // it may still be a MEMBER — it genuinely co-occurs — it just cannot be the name
        assert!(clusters.iter().any(|c| c.terms.iter().any(|t| t == "city")), "{clusters:#?}");
    }

    #[test]
    fn discovery_transports_every_salient_term_to_some_facet() {
        // Sinkhorn assigns each term to exactly one target, so nothing salient is silently dropped — which is
        // what the agglomerative version did when a merge fell below its linkage floor.
        let docs = corpus();
        let clusters = discover(&docs, 60, 2);
        let placed: usize = clusters.iter().map(|c| c.terms.len()).sum();
        assert!(placed >= 6, "expected the salient terms to be placed, got {placed}: {clusters:#?}");
    }

    #[test]
    fn a_function_word_cannot_become_a_category() {
        // A corpus of these eight documents discovered `near/*`. A preposition is not a kind of thing, so it
        // can neither name a category nor usefully join one, and one that appears in most documents adds noise
        // to the co-occurrence geometry that the transport plan then has to spend mass on.
        let docs: Vec<String> = [
            "Morty Shade defeated Wallace Gale at Ecruteak City in 2025.",
            "Bea Strike defeated Iris Draco at Ecruteak City in 2025.",
            "Lance Wing defeated Karen Dusk at Ecruteak City in 2025.",
            "A survey recorded Aggron near Sootopolis City at 28 degrees.",
            "A survey recorded Salamence near Sootopolis City at 31 degrees.",
            "A survey recorded Metagross near Sootopolis City at 19 degrees.",
            "Milotic is not permitted in Series 1 play for the 2025 season.",
            "Registeel is not permitted in Series 1 play for the 2025 season.",
        ]
        .iter()
        .map(|s| s.to_string())
        .collect();

        for c in discover(&docs, 60, 4) {
            assert!(
                !LOCATIVES.contains(&c.label.as_str()) && !STOP.contains(&c.label.as_str()),
                "a function word named a category: {c:?}"
            );
            assert!(
                !c.terms.iter().any(|t| LOCATIVES.contains(&t.as_str())),
                "a function word was clustered as a signal word: {c:?}"
            );
        }
    }

    #[test]
    fn the_word_lists_do_not_overlap() {
        // Duplicated entries are harmless but mean one list is being maintained in two places.
        for w in LOCATIVES {
            assert!(!STOP.contains(w), "{w} is in both STOP and LOCATIVES");
            assert!(!GENERIC.contains(w), "{w} is in both GENERIC and LOCATIVES");
        }
    }
}