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    out
135}
136
137/// Weighted term frequencies for one document.
138pub fn tf(parts: &[(&str, u16)]) -> (Vec<(String, u16)>, u32) {
139    let mut m: HashMap<String, u16> = HashMap::new();
140    let mut len = 0u32;
141    for (text, w) in parts {
142        // Cap very long bodies; the head carries the signal.
143        let text = if text.len() > 16 * 1024 {
144            &text[..mcp_kit::search::floor_char(text, 16 * 1024)]
145        } else {
146            text
147        };
148        for t in terms(text) {
149            let e = m.entry(t).or_insert(0);
150            *e = e.saturating_add(*w);
151            len += *w as u32;
152        }
153    }
154    let mut v: Vec<(String, u16)> = m.into_iter().collect();
155    v.sort();
156    (v, len.max(1))
157}
158
159#[derive(Default)]
160pub struct Bm25 {
161    postings: HashMap<String, Vec<(u32, u16)>>,
162    lens: Vec<u32>,
163    avg: f32,
164}
165
166pub struct Hit {
167    pub doc: u32,
168    pub score: f32,
169    /// Distinct query terms matched.
170    pub matched: usize,
171}
172
173impl Bm25 {
174    pub fn build<'a>(docs: impl Iterator<Item = (&'a [(String, u16)], u32)>) -> Bm25 {
175        let mut postings: HashMap<String, Vec<(u32, u16)>> = HashMap::new();
176        let mut lens = Vec::new();
177        let mut total = 0u64;
178        for (terms, len) in docs {
179            let id = lens.len() as u32;
180            lens.push(len);
181            total += len as u64;
182            for (t, f) in terms {
183                match postings.get_mut(t) {
184                    Some(v) => v.push((id, *f)),
185                    None => {
186                        postings.insert(t.clone(), vec![(id, *f)]);
187                    }
188                }
189            }
190        }
191        let avg = if lens.is_empty() { 1.0 } else { total as f32 / lens.len() as f32 };
192        Bm25 { postings, lens, avg }
193    }
194
195    pub fn len(&self) -> usize {
196        self.lens.len()
197    }
198
199    pub fn is_empty(&self) -> bool {
200        self.lens.is_empty()
201    }
202
203    /// Number of documents containing `term`.
204    pub fn df(&self, term: &str) -> usize {
205        self.postings.get(term).map_or(0, |p| p.len())
206    }
207
208    pub fn contains(&self, term: &str) -> bool {
209        self.postings.contains_key(term)
210    }
211
212    pub fn search(&self, qterms: &[String]) -> Vec<Hit> {
213        let weighted: Vec<(String, f32)> = qterms.iter().map(|t| (t.clone(), 1.0)).collect();
214        self.search_weighted(&weighted)
215    }
216
217    /// BM25 with per-term weights; coverage counts only full-weight terms.
218    pub fn search_weighted(&self, qterms: &[(String, f32)]) -> Vec<Hit> {
219        let n = self.lens.len() as f32;
220        let mut scores: HashMap<u32, (f32, usize)> = HashMap::new();
221        for (t, w) in qterms {
222            let Some(list) = self.postings.get(t) else { continue };
223            let df = list.len() as f32;
224            let idf = ((n - df + 0.5) / (df + 0.5) + 1.0).ln();
225            for &(d, tf) in list {
226                let tf = tf as f32;
227                let norm = tf * (K1 + 1.0) / (tf + K1 * (1.0 - B + B * self.lens[d as usize] as f32 / self.avg));
228                let e = scores.entry(d).or_insert((0.0, 0));
229                e.0 += idf * norm * w;
230                if *w >= 1.0 {
231                    e.1 += 1;
232                }
233            }
234        }
235        let q = qterms.iter().filter(|(_, w)| *w >= 1.0).count().max(1) as f32;
236        let mut hits: Vec<Hit> = scores
237            .into_iter()
238            .map(|(doc, (s, m))| Hit {
239                doc,
240                score: s * (0.4 + m as f32 / q),
241                matched: m,
242            })
243            .collect();
244        hits.sort_by(|a, b| b.score.partial_cmp(&a.score).unwrap_or(std::cmp::Ordering::Equal).then(a.doc.cmp(&b.doc)));
245        hits
246    }
247}
248
249#[cfg(test)]
250mod tests {
251    use super::*;
252    #[test]
253    fn stems_and_ranks() {
254        assert_eq!(stem("schemas"), "schema");
255        assert_eq!(stem("validating"), "validat");
256        assert_eq!(stem("validated"), "validat");
257        assert_eq!(stem("validate"), "validat");
258        assert_eq!(stem("parses"), stem("parse"));
259        assert_eq!(stem("class"), "class");
260        assert_eq!(stem("immutability"), stem("immutable"));
261        assert_eq!(stem("validation"), stem("validate"));
262        assert_eq!(stem("validations"), stem("validated"));
263        let a = tf(&[("object schema strict", 1)]);
264        let b = tf(&[("string schema", 1)]);
265        let idx = Bm25::build([(a.0.as_slice(), a.1), (b.0.as_slice(), b.1)].into_iter());
266        let hits = idx.search(&query_terms("how do I make strict object schemas"));
267        assert_eq!(hits[0].doc, 0);
268    }
269}