1use 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
15pub fn is_stop(w: &str) -> bool {
17 STOP.contains(&w)
18}
19
20pub 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
60pub fn terms(text: &str) -> Vec<String> {
62 crate::tokenize::tokenize(text).into_iter().map(|t| stem(&t)).collect()
63}
64
65pub 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
77const 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
122pub 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 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
148pub 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 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 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 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 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}