memfork_core/search.rs
1//! Exact brute-force cosine similarity search (DESIGN §4.2).
2//!
3//! There is no approximate index here on purpose: DESIGN §4.2 defers a
4//! branch-aware approximate index, which is still to do. Brute force over a
5//! branch head is exact,
6//! needs no index to keep in step with forks and merges, and — because the
7//! accumulation order is fixed and ties break on the key — returns byte-identical
8//! ordering on every platform.
9
10use std::sync::Arc;
11
12use crate::entry::Entry;
13use crate::store::Store;
14use crate::view::ReadView;
15
16/// One search result.
17#[derive(Debug, Clone)]
18pub struct SearchHit {
19 /// The matching key.
20 pub key: String,
21 /// Cosine similarity with the query, in `[-1, 1]`.
22 pub score: f32,
23 /// The matching entry.
24 pub entry: Arc<Entry>,
25}
26
27/// Cosine similarity of two equal-length vectors.
28///
29/// Returns 0 for a length mismatch or a zero-magnitude vector, so an entry can
30/// never knock a real match out of the top k by being undefined.
31pub fn cosine(a: &[f32], b: &[f32]) -> f32 {
32 if a.len() != b.len() || a.is_empty() {
33 return 0.0;
34 }
35 let mut dot = 0.0f32;
36 let mut na = 0.0f32;
37 let mut nb = 0.0f32;
38 // A fixed left-to-right accumulation: float addition is not associative,
39 // so the order is part of the contract: the same query must rank the
40 // same way on every machine, every time.
41 for i in 0..a.len() {
42 dot += a[i] * b[i];
43 na += a[i] * a[i];
44 nb += b[i] * b[i];
45 }
46 let denom = na.sqrt() * nb.sqrt();
47 if denom == 0.0 || !denom.is_finite() {
48 0.0
49 } else {
50 dot / denom
51 }
52}
53
54/// Top `k` entries of a view by cosine similarity, highest first.
55///
56/// Entries without an embedding are skipped. Ties break on the key, ascending,
57/// so the result is a total order and never depends on iteration order.
58pub fn search(view: &ReadView, query: &[f32], k: usize, prefix: Option<&str>) -> Vec<SearchHit> {
59 if k == 0 || query.is_empty() {
60 return Vec::new();
61 }
62 let root = &view.commit().root;
63 let mut hits: Vec<SearchHit> = match prefix {
64 Some(p) => collect(root.range_prefix(p), query),
65 None => collect(root.iter(), query),
66 };
67 hits.sort_by(|a, b| {
68 // `total_cmp` is a total order over every f32 including NaN, so the
69 // comparator can never be inconsistent.
70 b.score.total_cmp(&a.score).then_with(|| a.key.cmp(&b.key))
71 });
72 hits.truncate(k);
73 hits
74}
75
76fn collect<'a, I>(it: I, query: &[f32]) -> Vec<SearchHit>
77where
78 I: Iterator<Item = (&'a String, &'a Arc<Entry>)>,
79{
80 it.filter_map(|(key, entry)| {
81 let embedding = entry.embedding.as_deref()?;
82 Some(SearchHit {
83 key: key.clone(),
84 score: cosine(query, embedding),
85 entry: Arc::clone(entry),
86 })
87 })
88 .collect()
89}