Skip to main content

lockdocs_core/
bm25.rs

1//! BM25 over entries (adapted from repomap's engine), with a light English
2//! stemmer and query stopwords so questions in plain language rank well.
3
4use std::collections::HashMap;
5
6const K1: f32 = 1.2;
7const B: f32 = 0.75;
8
9const STOP: &[&str] = &[
10    "a", "an", "and", "are", "as", "at", "be", "by", "can", "do", "does", "for", "from", "get", "how", "i", "if", "in", "is", "it", "me", "my", "of", "on",
11    "or", "should", "that", "the", "this", "to", "using", "what", "when", "where", "which", "with", "you", "your", "we", "our", "way", "want", "need", "there",
12    "their", "into", "vs", "versus", "about", "example", "show",
13];
14
15/// A stopword (lowercase)?
16pub fn is_stop(w: &str) -> bool {
17    STOP.contains(&w)
18}
19
20/// Conservative suffix stripping: plural, -ing, -ed, final -e, and the
21/// noun forms -ation / -ability that pair with -ate / -able
22/// (validation ~ validate, immutability ~ immutable).
23pub fn stem(t: &str) -> String {
24    let mut s = stem0(t);
25    let n = s.len();
26    if s.is_ascii() && n > 8 && (s.ends_with("ability") || s.ends_with("ibility")) {
27        s.replace_range(n - 5.., "l");
28    } else if s.is_ascii() && n > 7 && s.ends_with("ation") {
29        s.truncate(n - 3);
30    }
31    if s.len() > 4 && s.ends_with('e') && s.is_ascii() {
32        s.pop();
33    }
34    s
35}
36
37fn stem0(t: &str) -> String {
38    let n = t.len();
39    if n <= 3 || !t.is_ascii() {
40        return t.to_string();
41    }
42    if n > 5 && t.ends_with("ies") {
43        return format!("{}y", &t[..n - 3]);
44    }
45    if n > 4 && (t.ends_with("sses") || t.ends_with("shes") || t.ends_with("ches") || t.ends_with("xes")) {
46        return t[..n - 2].to_string();
47    }
48    if t.ends_with('s') && !t.ends_with("ss") && !t.ends_with("us") && !t.ends_with("is") {
49        return t[..n - 1].to_string();
50    }
51    if n > 6 && t.ends_with("ing") {
52        return t[..n - 3].to_string();
53    }
54    if n > 5 && t.ends_with("ed") && !t.ends_with("eed") {
55        return t[..n - 2].to_string();
56    }
57    t.to_string()
58}
59
60/// Index-side terms for a text.
61pub fn terms(text: &str) -> Vec<String> {
62    crate::tokenize::tokenize(text).into_iter().map(|t| stem(&t)).collect()
63}
64
65/// Query-side terms: stopwords dropped, deduplicated.
66pub fn query_terms(q: &str) -> Vec<String> {
67    let mut v: Vec<String> = crate::tokenize::tokenize(q)
68        .into_iter()
69        .filter(|t| !STOP.contains(&t.as_str()))
70        .map(|t| stem(&t))
71        .collect();
72    v.sort();
73    v.dedup();
74    v
75}
76
77/// Programming synonyms: docs and questions often use different words for
78/// the same thing ("convert to dict" vs `model_dump`). Stemmed forms.
79const SYNONYMS: &[(&str, &[&str])] = &[
80    ("dict", &["dictionary", "dump", "mapping"]),
81    ("dictionary", &["dict"]),
82    ("convert", &["dump", "serializ", "transform", "cast"]),
83    ("serializ", &["dump", "json", "encod"]),
84    ("deserializ", &["pars", "load", "decod", "validat"]),
85    ("pars", &["validat", "decod", "load"]),
86    ("validat", &["pars", "check"]),
87    ("remov", &["delet", "drop"]),
88    ("delet", &["remov", "drop"]),
89    ("creat", &["new", "build", "mak", "init"]),
90    ("async", &["await", "promis", "futur"]),
91    ("error", &["except", "err", "fail"]),
92    ("except", &["error"]),
93    ("config", &["setting", "option", "configur"]),
94    ("setting", &["config"]),
95    ("option", &["config", "param"]),
96    ("fetch", &["request", "get"]),
97    ("request", &["fetch"]),
98    ("redirect", &["navigat"]),
99    ("navigat", &["redirect", "router"]),
100    ("spawn", &["task"]),
101    ("finish", &["complet", "done"]),
102    ("complet", &["finish", "done"]),
103    ("first", &["race", "select"]),
104    ("route", &["router", "path"]),
105    ("middleware", &["layer"]),
106    ("layer", &["middleware"]),
107    ("state", &["extension"]),
108    ("parameter", &["param", "arg", "argument"]),
109    ("param", &["parameter"]),
110    ("argument", &["arg", "param"]),
111    ("arg", &["argument"]),
112    ("javascript", &["js"]),
113    ("js", &["javascript"]),
114    ("typescript", &["ts"]),
115    ("ts", &["typescript"]),
116    ("databas", &["db"]),
117    ("db", &["databas"]),
118    ("unknown", &["extra", "strict"]),
119    ("extra", &["unknown"]),
120];
121
122/// Query terms plus weighted synonyms not already present.
123pub fn expand(terms: &[String]) -> Vec<(String, f32)> {
124    let mut out: Vec<(String, f32)> = terms.iter().map(|t| (t.clone(), 1.0)).collect();
125    for t in terms {
126        if let Some((_, syns)) = SYNONYMS.iter().find(|(k, _)| k == t) {
127            for s in *syns {
128                if !out.iter().any(|(x, _)| x == s) {
129                    out.push((s.to_string(), 0.35));
130                }
131            }
132        }
133    }
134    // Rejecting extra input is strict validation. In this explicit context
135    // "strict" carries the question's intent, rather than the weak association
136    // of "unknown" alone (which also describes unknown types and errors).
137    let has = |words: &[&str]| terms.iter().any(|t| words.contains(&t.as_str()));
138    if has(&["reject", "forbid", "disallow"]) && has(&["unknown", "extra", "unrecogniz"]) && has(&["key", "field", "property", "properti"]) {
139        if let Some((_, weight)) = out.iter_mut().find(|(t, _)| t == "strict") {
140            *weight = 1.0;
141        } else {
142            out.push(("strict".into(), 1.0));
143        }
144    }
145    out
146}
147
148/// Weighted term frequencies for one document.
149pub fn tf(parts: &[(&str, u16)]) -> (Vec<(String, u16)>, u32) {
150    let mut m: HashMap<String, u16> = HashMap::new();
151    let mut len = 0u32;
152    for (text, w) in parts {
153        // Cap very long bodies; the head carries the signal.
154        let text = if text.len() > 16 * 1024 {
155            &text[..mcp_kit::search::floor_char(text, 16 * 1024)]
156        } else {
157            text
158        };
159        for t in terms(text) {
160            let e = m.entry(t).or_insert(0);
161            *e = e.saturating_add(*w);
162            len += *w as u32;
163        }
164    }
165    let mut v: Vec<(String, u16)> = m.into_iter().collect();
166    v.sort();
167    (v, len.max(1))
168}
169
170#[derive(Default)]
171pub struct Bm25 {
172    postings: HashMap<String, Vec<(u32, u16)>>,
173    lens: Vec<u32>,
174    avg: f32,
175}
176
177pub struct Hit {
178    pub doc: u32,
179    pub score: f32,
180    /// Distinct query terms matched.
181    pub matched: usize,
182}
183
184impl Bm25 {
185    pub fn build<'a>(docs: impl Iterator<Item = (&'a [(String, u16)], u32)>) -> Bm25 {
186        let mut postings: HashMap<String, Vec<(u32, u16)>> = HashMap::new();
187        let mut lens = Vec::new();
188        let mut total = 0u64;
189        for (terms, len) in docs {
190            let id = lens.len() as u32;
191            lens.push(len);
192            total += len as u64;
193            for (t, f) in terms {
194                match postings.get_mut(t) {
195                    Some(v) => v.push((id, *f)),
196                    None => {
197                        postings.insert(t.clone(), vec![(id, *f)]);
198                    }
199                }
200            }
201        }
202        let avg = if lens.is_empty() { 1.0 } else { total as f32 / lens.len() as f32 };
203        Bm25 { postings, lens, avg }
204    }
205
206    pub fn len(&self) -> usize {
207        self.lens.len()
208    }
209
210    pub fn is_empty(&self) -> bool {
211        self.lens.is_empty()
212    }
213
214    /// Number of documents containing `term`.
215    pub fn df(&self, term: &str) -> usize {
216        self.postings.get(term).map_or(0, |p| p.len())
217    }
218
219    pub fn contains(&self, term: &str) -> bool {
220        self.postings.contains_key(term)
221    }
222
223    pub fn search(&self, qterms: &[String]) -> Vec<Hit> {
224        let weighted: Vec<(String, f32)> = qterms.iter().map(|t| (t.clone(), 1.0)).collect();
225        self.search_weighted(&weighted)
226    }
227
228    /// BM25 with per-term weights; coverage counts only full-weight terms.
229    pub fn search_weighted(&self, qterms: &[(String, f32)]) -> Vec<Hit> {
230        let n = self.lens.len() as f32;
231        let mut scores: HashMap<u32, (f32, usize)> = HashMap::new();
232        for (t, w) in qterms {
233            let Some(list) = self.postings.get(t) else { continue };
234            let df = list.len() as f32;
235            let idf = ((n - df + 0.5) / (df + 0.5) + 1.0).ln();
236            for &(d, tf) in list {
237                let tf = tf as f32;
238                let norm = tf * (K1 + 1.0) / (tf + K1 * (1.0 - B + B * self.lens[d as usize] as f32 / self.avg));
239                let e = scores.entry(d).or_insert((0.0, 0));
240                e.0 += idf * norm * w;
241                if *w >= 1.0 {
242                    e.1 += 1;
243                }
244            }
245        }
246        let q = qterms.iter().filter(|(_, w)| *w >= 1.0).count().max(1) as f32;
247        let mut hits: Vec<Hit> = scores
248            .into_iter()
249            .map(|(doc, (s, m))| Hit {
250                doc,
251                score: s * (0.4 + m as f32 / q),
252                matched: m,
253            })
254            .collect();
255        hits.sort_by(|a, b| b.score.partial_cmp(&a.score).unwrap_or(std::cmp::Ordering::Equal).then(a.doc.cmp(&b.doc)));
256        hits
257    }
258}
259
260#[cfg(test)]
261mod tests {
262    use super::*;
263    #[test]
264    fn rejecting_extra_input_finds_strict_validation_without_rewriting_unknown_types() {
265        let entries = [tf(&[("strictObject", 8)]), tf(&[("unknown key", 1)])];
266        let index = Bm25::build(entries.iter().map(|(terms, len)| (terms.as_slice(), *len)));
267        for q in ["reject unknown keys", "forbid extra fields", "disallow unknown properties"] {
268            let hits = index.search_weighted(&expand(&query_terms(q)));
269            assert!(hits.iter().any(|h| h.doc == 0), "{q}");
270        }
271        let hits = index.search_weighted(&expand(&query_terms("unknown key type")));
272        assert_eq!(hits[0].doc, 1);
273    }
274    #[test]
275    fn stems_and_ranks() {
276        assert_eq!(stem("schemas"), "schema");
277        assert_eq!(stem("validating"), "validat");
278        assert_eq!(stem("validated"), "validat");
279        assert_eq!(stem("validate"), "validat");
280        assert_eq!(stem("parses"), stem("parse"));
281        assert_eq!(stem("class"), "class");
282        assert_eq!(stem("immutability"), stem("immutable"));
283        assert_eq!(stem("validation"), stem("validate"));
284        assert_eq!(stem("validations"), stem("validated"));
285        let a = tf(&[("object schema strict", 1)]);
286        let b = tf(&[("string schema", 1)]);
287        let idx = Bm25::build([(a.0.as_slice(), a.1), (b.0.as_slice(), b.1)].into_iter());
288        let hits = idx.search(&query_terms("how do I make strict object schemas"));
289        assert_eq!(hits[0].doc, 0);
290    }
291}