Skip to main content

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}