steeldb/

index.rs

//! InfonIndex — the sparse incidence store: one posting set per infon token = the situations where
//! it holds. Generic over the `Postings` backend so the same query path runs on either the HashSet
//! baseline or roaring. `atom` resolves a token or a glob pattern to the UNION of matching postings,
//! matching the TS `atom` / `fnmatch` semantics.

use crate::bitmap::Postings;
use crate::tokenql::TokenStore;
use std::collections::HashMap;

pub struct InfonIndex<B: Postings> {
    symbol_table: HashMap<String, B>,
    universe: B,
    n: u32,
    /// numeric columnar layer: field → (sid, value), sid-ascending — powers `(num field op value)`.
    numbers: HashMap<String, Vec<(u32, f64)>>,
    /// **Infon polarity** layer (paper §1.2, §4): the paper's infon `⟨⟨R, a₁…aₙ; i⟩⟩` carries a polarity
    /// `i`; we widen `i` from `{0,1}` to four discrete belief levels `{-1, -0.5, +0.5, +1}`
    /// (strong-against / weak-against / weak-for / strong-for) so Dempster-Shafer `Bel`/`Pl` can be
    /// aggregated as a weighted POPCNT over bitmaps rather than a power-set walk:
    ///   sign(sid): in `polarity_neg` ⇒ `i < 0`; magnitude(sid): in `polarity_weak` ⇒ `|i| = 0.5` else `1.0`.
    ///   default (present in the symbol table, in neither set) = `i = +1`.
    polarity_neg: HashMap<String, B>,
    polarity_weak: HashMap<String, B>,
}

impl<B: Postings> InfonIndex<B> {
    /// Build from `token -> ascending sids`. Callers accumulate sids in id order during a scan.
    pub fn from_postings(raw: HashMap<String, Vec<u32>>, n: u32) -> Self {
        let mut symbol_table = HashMap::with_capacity(raw.len());
        for (tok, ids) in raw {
            symbol_table.insert(tok, B::from_sorted(&ids));
        }
        let universe = B::from_sorted(&(0..n).collect::<Vec<_>>());
        InfonIndex { symbol_table, universe, n, numbers: HashMap::new(), polarity_neg: HashMap::new(), polarity_weak: HashMap::new() }
    }

    /// Record a token membership at `sid` with a Dempster-Shafer polarity level ∈ {-1, -0.5, +0.5, +1}
    /// (paper §4). `+1` strong-for, `+0.5` weak-for, `-0.5` weak-against, `-1` strong-against. Presence is
    /// always asserted; sign/magnitude are stored in the `neg`/`weak` auxiliary sets.
    pub fn add_infon_polar(&mut self, sid: u32, token: &str, level: f32) {
        self.symbol_table.entry(token.to_string()).or_insert_with(B::empty).insert(sid);
        if level < 0.0 {
            self.polarity_neg.entry(token.to_string()).or_insert_with(B::empty).insert(sid);
        }
        if level.abs() < 0.75 {
            self.polarity_weak.entry(token.to_string()).or_insert_with(B::empty).insert(sid);
        }
    }

    /// SIMD belief aggregation (paper §4.1): net signed mass of `token` over `scope`, computed as a
    /// weighted POPCNT over roaring sets — `+1·|strong-for| +0.5·|weak-for| −0.5·|weak-against|
    /// −1·|strong-against|`, all within `scope ∩ post(token)`.
    pub fn signed_mass(&self, token: &str, scope: &B) -> f64 {
        let Some(post) = self.symbol_table.get(token) else { return 0.0 };
        let base = post.and(scope);
        let neg = self.polarity_neg.get(token).map(|n| base.and(n)).unwrap_or_else(B::empty);
        let weak = self.polarity_weak.get(token).map(|w| base.and(w)).unwrap_or_else(B::empty);
        let pos = base.and_not(&neg); // positive-sign members
        let pos_weak = pos.and(&weak);
        let neg_weak = neg.and(&weak);
        let pos_strong = pos.len() - pos_weak.len();
        let neg_strong = neg.len() - neg_weak.len();
        pos_strong as f64 + 0.5 * pos_weak.len() as f64 - 0.5 * neg_weak.len() as f64 - neg_strong as f64
    }

    /// Situations where `token` holds with per-situation belief ≥ `min_bel`, using the discrete level
    /// map (+1→1.0 strong-for, +0.5→0.5 weak-for, present→>0). Powers IKL `(evidence … :min-bel b)`.
    pub fn evidence_set(&self, token: &str, min_bel: f64) -> B {
        let Some(post) = self.symbol_table.get(token) else { return B::empty() };
        let neg = self.polarity_neg.get(token);
        let pos = match neg {
            Some(n) => post.and_not(n), // positive-sign members
            None => post.clone(),
        };
        if min_bel >= 0.75 {
            // strong-for only: positive AND not weak
            match self.polarity_weak.get(token) {
                Some(w) => pos.and_not(w),
                None => pos,
            }
        } else if min_bel >= 0.25 {
            pos // strong or weak for
        } else {
            post.clone() // any presence
        }
    }

    /// Dempster-Shafer belief interval `[Bel, Pl]` for `token` over `scope` (paper §4.1): `Bel` = fraction
    /// of scope with strong-for evidence (lower certainty bound); `Pl` = fraction not strongly refuted
    /// (upper bound `1 − Bel(¬A)`). Returns `(bel, pl)` in `[0,1]`.
    pub fn belief_interval(&self, token: &str, scope: &B) -> (f64, f64) {
        let n = scope.len();
        if n == 0 {
            return (0.0, 0.0);
        }
        let Some(post) = self.symbol_table.get(token) else { return (0.0, 1.0) };
        let base = post.and(scope);
        let neg = self.polarity_neg.get(token).map(|x| base.and(x)).unwrap_or_else(B::empty);
        let weak = self.polarity_weak.get(token).map(|x| base.and(x)).unwrap_or_else(B::empty);
        let pos = base.and_not(&neg);
        let strong_for = pos.len() - pos.and(&weak).len();
        let strong_against = neg.len() - neg.and(&weak).len();
        let bel = strong_for as f64 / n as f64;
        let pl = 1.0 - (strong_against as f64 / n as f64);
        (bel, pl)
    }

    /// Record a numeric field value for a situation (columnar numeric layer).
    pub fn add_number(&mut self, sid: u32, field: &str, value: f64) {
        self.numbers.entry(field.to_string()).or_default().push((sid, value));
    }

    /// Numeric fields present (for schema/agent discovery).
    pub fn numeric_fields(&self) -> impl Iterator<Item = &String> {
        self.numbers.keys()
    }

    /// Append one situation's tokens as a new sid (incremental / realtime ingest). Tokens should be
    /// de-duplicated by the caller. Returns the new sid.
    pub fn add(&mut self, tokens: &[String]) -> u32 {
        let sid = self.n;
        for t in tokens {
            self.symbol_table.entry(t.clone()).or_insert_with(B::empty).insert(sid);
        }
        self.universe.insert(sid);
        self.n += 1;
        sid
    }

    pub fn vocab_size(&self) -> usize {
        self.symbol_table.len()
    }
    pub fn tokens(&self) -> impl Iterator<Item = &String> {
        self.symbol_table.keys()
    }
    /// The posting set for an exact token (clone; empty if absent). Unlike `atom`, no glob handling —
    /// the analytics programs address concrete tokens they discovered from the vocabulary.
    pub fn post(&self, token: &str) -> B {
        self.symbol_table.get(token).cloned().unwrap_or_else(B::empty)
    }
    pub fn post_len(&self, token: &str) -> usize {
        self.symbol_table.get(token).map(|b| b.len()).unwrap_or(0)
    }
    /// Every token under a facet (first path segment), unsorted and untruncated — the analytics
    /// programs partition/rank over the full facet, not just the top-N `tokens_in_facet` returns.
    pub fn facet_members(&self, facet: &str) -> Vec<&String> {
        self.symbol_table.keys().filter(|t| t.split('/').next() == Some(facet)).collect()
    }
    /// The most frequent tokens under a facet, with posting sizes — so an agent can learn the
    /// queryable vocabulary of a facet before composing IKL.
    pub fn tokens_in_facet(&self, facet: &str, limit: usize) -> Vec<(String, usize)> {
        let mut v: Vec<(String, usize)> = self
            .symbol_table
            .iter()
            .filter(|(t, _)| t.split('/').next() == Some(facet))
            .map(|(t, b)| (t.clone(), b.len()))
            .collect();
        v.sort_by(|a, b| b.1.cmp(&a.1).then(a.0.cmp(&b.0)));
        v.truncate(limit);
        v
    }
    /// Every `(tag, postings)` pair in the symbol table — the incidence matrix, row by row.
    pub fn postings(&self) -> impl Iterator<Item = (&String, &B)> {
        self.symbol_table.iter()
    }
    pub fn situations(&self) -> u32 {
        self.n
    }

    /// Total native bytes across all postings (memory proxy for the chosen backend).
    pub fn postings_native_bytes(&self) -> usize {
        self.symbol_table.values().map(|b| b.native_bytes()).sum()
    }
    /// Total portable delta-gap bytes (same for every backend — the on-disk posting size).
    pub fn postings_deltagap_bytes(&self) -> usize {
        self.symbol_table.values().map(|b| b.serialize_deltagap().len()).sum()
    }
}

/// glob match with `*` (any run) and `?` (one char) — enough for the token wildcard atoms.
fn glob_match(pat: &str, s: &str) -> bool {
    // classic two-pointer wildcard matcher with backtracking on `*`
    let (p, t) = (pat.as_bytes(), s.as_bytes());
    let (mut pi, mut ti) = (0usize, 0usize);
    let (mut star, mut mark) = (usize::MAX, 0usize);
    while ti < t.len() {
        if pi < p.len() && (p[pi] == b'?' || p[pi] == t[ti]) {
            pi += 1;
            ti += 1;
        } else if pi < p.len() && p[pi] == b'*' {
            star = pi;
            mark = ti;
            pi += 1;
        } else if star != usize::MAX {
            pi = star + 1;
            mark += 1;
            ti = mark;
        } else {
            return false;
        }
    }
    while pi < p.len() && p[pi] == b'*' {
        pi += 1;
    }
    pi == p.len()
}

fn is_glob(pat: &str) -> bool {
    pat.contains('*') || pat.contains('?')
}

impl<B: Postings> InfonIndex<B> {
    /// Tokens on an s-path from `a` to `b`: a chain where consecutive tokens share at least `s` situations
    /// (paper §3.3). Returns `None` when either endpoint is unknown or no such chain exists.
    ///
    /// Raising `s` is what suppresses semantic drift — at `s = 1` a single shared situation links two tokens,
    /// which lets a walk wander somewhere unrelated to where it began.
    ///
    /// Breadth-first, so the chain found is the shortest. Neighbour discovery scans the symbol table, which is
    /// linear per expansion; the paper's answer to that cost is to filter the scope first, and the
    /// `(constraint …)` clause in the query form is how a caller does it.
    pub fn s_path_tokens(&self, a: &str, b: &str, s: usize) -> Option<Vec<String>> {
        let s = s.max(1);
        if !self.symbol_table.contains_key(a) || !self.symbol_table.contains_key(b) {
            return None;
        }
        if a == b {
            return Some(vec![a.to_string()]);
        }
        let mut prev: std::collections::HashMap<&str, Option<&str>> = std::collections::HashMap::new();
        prev.insert(a, None);
        let mut queue = std::collections::VecDeque::from([a]);
        while let Some(cur) = queue.pop_front() {
            let cur_post = match self.symbol_table.get(cur) {
                Some(p) => p,
                None => continue,
            };
            for (tok, post) in &self.symbol_table {
                if tok.as_str() == cur || prev.contains_key(tok.as_str()) {
                    continue;
                }
                if cur_post.and(post).len() < s {
                    continue;
                }
                prev.insert(tok.as_str(), Some(cur));
                if tok.as_str() == b {
                    // walk the parent chain back to the source
                    let mut chain = vec![b.to_string()];
                    let mut node = b;
                    while let Some(Some(p)) = prev.get(node) {
                        chain.push((*p).to_string());
                        node = p;
                    }
                    chain.reverse();
                    return Some(chain);
                }
                queue.push_back(tok.as_str());
            }
        }
        None
    }
}

impl<B: Postings> TokenStore<B> for InfonIndex<B> {
    fn atom(&self, pattern: &str) -> B {
        if is_glob(pattern) {
            let mut acc = B::empty();
            for (tok, post) in &self.symbol_table {
                if glob_match(pattern, tok) {
                    acc.or_inplace(post);
                }
            }
            acc
        } else {
            self.symbol_table.get(pattern).cloned().unwrap_or_else(B::empty)
        }
    }
    fn universe(&self) -> B {
        self.universe.clone()
    }
    /// The `evidence` atom of §6.1, backed by the polarity layer: situations where this token holds with
    /// per-situation belief at or above the threshold. The trait default is plain membership, which would
    /// ignore polarity entirely and quietly include refuted situations.
    fn evidence(&self, token: &str, min_bel: f64) -> B {
        self.evidence_set(token, min_bel)
    }
    /// The situations an s-path passes through: the union of the postings of the tokens on the chain, so the
    /// result composes with the rest of the set algebra.
    fn s_path(&self, a: &str, b: &str, s: usize) -> Option<B> {
        // Some(empty) and None mean different things and must not be collapsed: this index HAS a topological
        // layer, so "no chain connects these at this threshold" is an answer (empty), whereas None is reserved
        // for a store that cannot evaluate s-paths at all.
        let Some(chain) = self.s_path_tokens(a, b, s) else { return Some(B::empty()) };
        let mut out = B::empty();
        for tok in &chain {
            if let Some(post) = self.symbol_table.get(tok) {
                out.or_inplace(post);
            }
        }
        Some(out)
    }
    fn numeric(&self, field: &str, op: &str, value: f64) -> B {
        match self.numbers.get(field) {
            Some(vals) => {
                let sids: Vec<u32> = vals.iter().filter(|(_, v)| crate::units::cmp_op(*v, op, value)).map(|(sid, _)| *sid).collect();
                // a situation may record a field once; sids stay ascending from the ingest scan
                B::from_sorted(&sids)
            }
            None => B::empty(),
        }
    }
}