steeldb/

linter.rs

//! The **linter** — SteelDB's compile-time boundary between a probabilistic agent and the deterministic
//! engine (paper §2). Before any IKL query executes, every atom is validated against the corpus
//! Vocabulary Space `V` (the Bitmap Symbol Table). Unknown terms are rejected with a *"did you mean"*
//! nearest-term correction; wildcards are expanded to their real child terms; and unbalanced
//! parentheses are repaired. This is what turns a hallucinated URI into a caught compile error instead
//! of a silently wrong answer.
//!
//! Validation is deterministic and model-free: exact membership, prefix-glob coverage, and — for a miss
//! — an edit-distance suggestion scoped to the atom's own facet dimension.

use crate::tokenql::{parse, Node};
use std::collections::{HashMap, HashSet};

/// Status of a single atom against the vocabulary.
#[derive(Debug, Clone, PartialEq)]
pub enum AtomStatus {
    /// Exact term in the vocabulary.
    Known,
    /// A glob/prefix pattern that matches at least `n` real terms.
    Wildcard(usize),
    /// Not in the vocabulary — with nearest-term suggestions ("did you mean …").
    Unknown(Vec<String>),
}

#[derive(Debug, Clone)]
pub struct LintError {
    pub atom: String,
    pub message: String,
    pub suggestions: Vec<String>,
}

#[derive(Debug, Clone)]
pub struct LintReport {
    pub ok: bool,
    pub errors: Vec<LintError>,
    /// Set when the input had unbalanced parentheses that were auto-repaired.
    pub repaired: Option<String>,
}

/// The vocabulary index the linter validates against — the Bitmap Symbol Table's key set, organised by
/// facet dimension so suggestions stay in-dimension (a bad `geo/…` is corrected against real `geo/…`).
pub struct Linter {
    tokens: HashSet<String>,
    facets: HashSet<String>,
    by_facet: HashMap<String, Vec<String>>, // facet → leaf values
    /// Numeric fields are a **separate namespace** from facet tokens: in `(num range_km gt 500)` the
    /// `range_km` is a column in the numeric layer, not a `facet/value` membership. Validating it against
    /// the token vocabulary rejects every numeric predicate ever written.
    numeric: HashSet<String>,
}

/// Every head the linter treats as structure rather than vocabulary.
///
/// This list and the evaluator's match arms are the two halves of one contract, and they used to be able to
/// drift: a head whitelisted here with no arm in the evaluator passed linting and then evaluated to an empty
/// set, which is indistinguishable from "no rows matched". `s-path`, `source`, `target` and `constraint` all
/// sat in that state. A test in `tokenql` now asserts every entry is either evaluated or declared a sub-form.
pub const STRUCTURAL_HEADS: &[&str] = &[
    // top-level operators — each needs an evaluator arm
    "and", "or", "not", "num", "evidence", "combine-ds", "s-path",
    // sub-forms, only meaningful inside a parent head
    "stream", "mass", "source", "target", "constraint",
];

/// Heads that are only valid inside a parent form, so they need no evaluator arm of their own.
pub const SUB_FORMS: &[&str] = &["stream", "mass", "source", "target", "constraint"];

/// IKL keywords / structural atoms that are NOT vocabulary terms (operators, extended-IKL heads, and
/// `:keyword` argument markers). These are skipped during atom validation.
fn is_structural(a: &str) -> bool {
    STRUCTURAL_HEADS.contains(&a)
        || a.starts_with(':')
        || a.parse::<f64>().is_ok()
        || matches!(a, "ge" | "gt" | "le" | "lt" | "eq" | "ne" | "true" | "false")
}

fn facet_of(token: &str) -> &str {
    token.split('/').next().unwrap_or(token)
}
fn leaf_of(token: &str) -> &str {
    match token.find('/') {
        Some(i) => &token[i + 1..],
        None => token,
    }
}

/// Levenshtein edit distance (small strings; iterative two-row DP).
fn edit_distance(a: &str, b: &str) -> usize {
    let (a, b): (Vec<char>, Vec<char>) = (a.chars().collect(), b.chars().collect());
    let mut prev: Vec<usize> = (0..=b.len()).collect();
    let mut cur = vec![0usize; b.len() + 1];
    for i in 1..=a.len() {
        cur[0] = i;
        for j in 1..=b.len() {
            let cost = if a[i - 1] == b[j - 1] { 0 } else { 1 };
            cur[j] = (prev[j] + 1).min(cur[j - 1] + 1).min(prev[j - 1] + cost);
        }
        std::mem::swap(&mut prev, &mut cur);
    }
    prev[b.len()]
}

impl Linter {
    /// Build from the corpus's vocabulary (all `facet/value` tokens).
    pub fn from_tokens<I: IntoIterator<Item = String>>(tokens: I) -> Linter {
        let mut set = HashSet::new();
        let mut facets = HashSet::new();
        let mut by_facet: HashMap<String, Vec<String>> = HashMap::new();
        for t in tokens {
            facets.insert(facet_of(&t).to_string());
            by_facet.entry(facet_of(&t).to_string()).or_default().push(leaf_of(&t).to_string());
            set.insert(t);
        }
        Linter { tokens: set, facets, by_facet, numeric: HashSet::new() }
    }

    /// Declare the corpus's numeric fields so `(num <field> …)` predicates validate against the right
    /// namespace.
    pub fn with_numeric_fields<I: IntoIterator<Item = String>>(mut self, fields: I) -> Self {
        self.numeric = fields.into_iter().collect();
        self
    }

    pub fn numeric_fields(&self) -> Vec<String> {
        let mut v: Vec<String> = self.numeric.iter().cloned().collect();
        v.sort();
        v
    }

    /// Validate one atom: exact, wildcard-coverage, or unknown-with-suggestions.
    pub fn validate_atom(&self, atom: &str) -> AtomStatus {
        if atom.contains('*') {
            let prefix = &atom[..atom.find('*').unwrap()];
            let n = self.tokens.iter().filter(|t| t.starts_with(prefix)).count();
            if n > 0 {
                return AtomStatus::Wildcard(n);
            }
            // A wildcard that expands to nothing used to pass. `gene/*` linted clean while `gene/brca1`
            // refused, so asking for a category the corpus does not have returned an empty set that reads as
            // "no matches" — the exact confusion this linter exists to prevent. A wildcard is checked like any
            // other atom.
            return AtomStatus::Unknown(self.suggest(atom));
        }
        if self.tokens.contains(atom) {
            return AtomStatus::Known;
        }
        AtomStatus::Unknown(self.suggest(atom))
    }

    /// Is `facet` a dimension this corpus actually has?
    pub fn has_facet(&self, facet: &str) -> bool {
        self.facets.contains(facet)
    }

    /// The corpus's real facet names, sorted — what to show when a query names a dimension that does not
    /// exist here.
    pub fn facet_names(&self) -> Vec<String> {
        let mut v: Vec<String> = self.facets.iter().cloned().collect();
        v.sort();
        v
    }

    /// Nearest real terms to a miss, scoped to the atom's own facet. Returns empty when the facet itself
    /// is unknown — suggesting values from an unrelated dimension (`artifact/power_cube` →
    /// `state/negated`) is worse than saying the dimension doesn't exist, which `lint` reports instead.
    pub fn suggest(&self, atom: &str) -> Vec<String> {
        let facet = facet_of(atom);
        let leaf = leaf_of(atom);
        // only correct WITHIN a real facet; a bogus facet is a different error, reported by `lint`
        let real_facet = match self.facets.get(facet) {
            Some(f) => f.clone(),
            None => return Vec::new(),
        };
        let mut cands: Vec<(usize, &String)> =
            self.by_facet.get(&real_facet).map(|ls| ls.iter().map(|l| (edit_distance(l, leaf), l)).collect()).unwrap_or_default();
        cands.sort_by_key(|(d, _)| *d);
        cands.dedup_by(|a, b| a.1 == b.1);
        cands.into_iter().take(3).map(|(_, l)| format!("{real_facet}/{l}")).collect()
    }

    /// Lint a full IKL expression: repair unbalanced parens, then validate every vocabulary atom.
    pub fn lint(&self, ikl: &str) -> LintReport {
        let (expr, repaired) = balance_parens(ikl);
        let mut errors = Vec::new();
        self.walk(&parse(&expr), &mut errors);
        LintReport { ok: errors.is_empty(), errors, repaired }
    }

    fn walk(&self, node: &Node, errors: &mut Vec<LintError>) {
        match node {
            Node::Atom(a) => {
                if is_structural(a) {
                    return;
                }
                if let AtomStatus::Unknown(sug) = self.validate_atom(a) {
                    let facet = facet_of(a);
                    let msg = if !sug.is_empty() {
                        format!("term '{a}' not found; did you mean {}?", sug.join(", "))
                    } else if a.contains('/') && !self.has_facet(facet) {
                        format!("dimension '{facet}' is not in this corpus; facets are: {}", self.facet_names().join(", "))
                    } else {
                        format!("term '{a}' is not in the vocabulary")
                    };
                    errors.push(LintError { atom: a.clone(), message: msg, suggestions: sug });
                }
            }
            Node::List(items) => {
                // `(num <field> <op> <value>)`: the field belongs to the numeric layer, so it is checked
                // against that namespace and the op/value are structural — recursing as tokens would
                // reject every numeric predicate.
                if let Some(Node::Atom(head)) = items.first() {
                    if head == "num" {
                        if let Some(Node::Atom(field)) = items.get(1) {
                            if !self.numeric.is_empty() && !self.numeric.contains(field.as_str()) {
                                let mut sug: Vec<String> = self.numeric.iter().cloned().collect();
                                sug.sort_by_key(|f| edit_distance(f, field));
                                sug.truncate(3);
                                errors.push(LintError {
                                    atom: field.clone(),
                                    message: format!(
                                        "'{field}' is not a numeric field; numeric fields are: {}",
                                        self.numeric_fields().join(", ")
                                    ),
                                    suggestions: sug,
                                });
                            }
                        }
                        return; // op and value need no vocabulary check
                    }
                    // §6.1 evidential forms carry their own structure. Their keyword values — a stream id, a
                    // conflict threshold, a mass — are not vocabulary terms, and checking them as such
                    // rejected every well-formed fusion query ("term 'sensor' is not in the vocabulary").
                    if head == "combine-ds" {
                        for it in &items[1..] {
                            match it {
                                // :max-conflict and its number
                                Node::Atom(_) => {}
                                // (stream …) blocks
                                other => self.walk(other, errors),
                            }
                        }
                        return;
                    }
                    if head == "stream" {
                        // only :mass-assignments carries atoms; :id and its value do not
                        let mut i = 1;
                        while i < items.len() {
                            if matches!(&items[i], Node::Atom(k) if k == ":mass-assignments") {
                                if let Some(list) = items.get(i + 1) {
                                    self.walk(list, errors);
                                }
                                i += 2;
                                continue;
                            }
                            i += 1;
                        }
                        return;
                    }
                    if head == "mass" {
                        // (mass (<atom>+) <float>) — check the focal atoms, skip the number
                        if let Some(atoms) = items.get(1) {
                            self.walk(atoms, errors);
                        }
                        return;
                    }
                }
                // Skip the leading operator atom; recurse into the rest.
                let skip_first = matches!(items.first(), Some(Node::Atom(a)) if is_structural(a));
                for (i, it) in items.iter().enumerate() {
                    if i == 0 && skip_first {
                        continue;
                    }
                    self.walk(it, errors);
                }
            }
        }
    }
}

/// Repair unbalanced parentheses (a common LLM syntax drift): append missing `)` or trim extras.
/// Returns `(repaired_expr, Some(repaired) if changed)`.
pub fn balance_parens(expr: &str) -> (String, Option<String>) {
    let mut depth: i32 = 0;
    let mut out = String::with_capacity(expr.len());
    for c in expr.chars() {
        match c {
            '(' => {
                depth += 1;
                out.push(c);
            }
            ')' => {
                if depth > 0 {
                    depth -= 1;
                    out.push(c);
                } // drop unmatched ')'
            }
            _ => out.push(c),
        }
    }
    for _ in 0..depth {
        out.push(')'); // close unmatched '('
    }
    if out == expr {
        (out, None)
    } else {
        let r = out.clone();
        (out, Some(r))
    }
}

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

    fn linter() -> Linter {
        Linter::from_tokens(
            ["org/toyota", "org/honda", "artifact/battery_cell", "geo/apac", "powertrain/electric", "powertrain/diesel"]
                .into_iter()
                .map(String::from),
        )
    }

    #[test]
    fn exact_and_wildcard() {
        let l = linter();
        assert_eq!(l.validate_atom("org/toyota"), AtomStatus::Known);
        assert!(matches!(l.validate_atom("powertrain/*"), AtomStatus::Wildcard(n) if n == 2));
    }

    #[test]
    fn did_you_mean_scoped_to_facet() {
        let l = linter();
        // a near-miss leaf in a known facet → suggests the real term
        match l.validate_atom("artifact/battery_cel") {
            AtomStatus::Unknown(s) => assert_eq!(s, vec!["artifact/battery_cell".to_string()]),
            other => panic!("expected Unknown, got {other:?}"),
        }
        // hallucinated term
        match l.validate_atom("artifact/power_cube") {
            AtomStatus::Unknown(s) => assert!(s.iter().all(|x| x.starts_with("artifact/"))),
            other => panic!("expected Unknown, got {other:?}"),
        }
    }

    #[test]
    fn numeric_predicates_validate_against_the_numeric_namespace() {
        let l = linter().with_numeric_fields(["range_km".to_string(), "year".to_string()]);
        // a real numeric field must PASS (previously every numeric predicate was rejected)
        assert!(l.lint("(num range_km gt 500)").ok, "{:?}", l.lint("(num range_km gt 500)").errors);
        assert!(l.lint("(and powertrain/electric (num year ge 2020))").ok);
        // a bogus field is caught, and suggestions come from the numeric namespace — not from tokens
        let bad = l.lint("(num rnge_km gt 500)");
        assert!(!bad.ok);
        assert_eq!(bad.errors[0].suggestions[0], "range_km");
        assert!(bad.errors[0].message.contains("numeric field"), "{}", bad.errors[0].message);
        // with no declared numeric fields the predicate is accepted rather than falsely rejected
        assert!(linter().lint("(num anything gt 1)").ok);
    }

    #[test]
    fn unknown_dimension_reports_facets_not_bogus_suggestions() {
        let l = linter();
        // a value miss inside a REAL facet → in-facet suggestion
        let r = l.lint("artifact/battery_cel");
        assert!(!r.ok);
        assert_eq!(r.errors[0].suggestions[0], "artifact/battery_cell");
        // an unknown DIMENSION → no cross-facet guessing; list the real facets instead
        let r2 = l.lint("gene/brca1");
        assert!(!r2.ok);
        assert!(r2.errors[0].suggestions.is_empty(), "must not suggest values from another dimension");
        assert!(r2.errors[0].message.contains("dimension 'gene' is not in this corpus"), "{}", r2.errors[0].message);
        assert!(r2.errors[0].message.contains("artifact"), "should list real facets: {}", r2.errors[0].message);
    }

    #[test]
    fn lint_catches_bad_atom_and_repairs_parens() {
        let l = linter();
        let r = l.lint("(and org/toyota (not powertrain/diesel)"); // missing ')'
        assert!(r.repaired.is_some());
        assert!(r.ok, "all atoms valid: {:?}", r.errors);
        let bad = l.lint("(and org/tyota powertrain/electric)");
        assert!(!bad.ok);
        assert_eq!(bad.errors[0].suggestions[0], "org/toyota"); // nearest first
    }

    #[test]
    fn evidential_fusion_forms_lint_clean() {
        let l = Linter::from_tokens(
            ["artifact/battery_cell", "artifact/power_cube"].into_iter().map(String::from));

        // the bug: a stream id was type-checked as a vocabulary term, so every well-formed fusion query
        // was rejected with "term 'sensor' is not in the vocabulary"
        let q = "(combine-ds :max-conflict 0.20 \
                   (stream :id sensor :mass-assignments ((mass (artifact/battery_cell) 0.7) \
                                                         (mass (artifact/battery_cell artifact/power_cube) 0.3))))";
        let r = l.lint(q);
        assert!(r.ok, "should lint clean, got {:?}", r.errors.iter().map(|e| e.message.clone()).collect::<Vec<_>>());

        assert!(l.lint("(evidence artifact/battery_cell :min-bel 0.8 :max-pl 0.95)").ok);

        // a real unknown INSIDE a focal set must still be caught — the skip must not become a blind spot
        let bad = l.lint("(combine-ds :max-conflict 0.2 \
                            (stream :id s :mass-assignments ((mass (artifact/nonexistent) 1.0))))");
        assert!(!bad.ok, "an unknown focal atom must still be reported");
        assert!(bad.errors.iter().any(|e| e.atom.contains("nonexistent")), "{:?}", bad.errors);
    }

    #[test]
    fn a_wildcard_on_a_missing_category_is_refused() {
        // Shipped as 0.1.0 with this wrong: `gene/*` linted clean while `gene/brca1` refused, so asking for a
        // category the corpus lacks returned an empty set indistinguishable from "no matches".
        let l = Linter::from_tokens(["battle/defeated", "survey/elevation"].into_iter().map(String::from));

        assert!(l.lint("battle/*").ok, "a real category must still expand");
        assert!(l.lint("survey/*").ok);

        let bad = l.lint("gene/*");
        assert!(!bad.ok, "a wildcard cannot bypass the facet check");
        assert!(
            bad.errors[0].message.contains("battle") && bad.errors[0].message.contains("survey"),
            "and must name what does exist: {}",
            bad.errors[0].message
        );

        // nested, so the check cannot be skipped by burying it in an expression
        assert!(!l.lint("(and battle/* gene/*)").ok);
        assert!(!l.lint("(or (not gene/*) battle/*)").ok);
    }
}