Skip to main content

graphrt_rag/
memory.rs

1//! In-process vector store with a BM25 keyword index.
2//!
3//! Search is brute force: exact cosine similarity over every chunk of the
4//! requested datasets. That is fast enough for tens of thousands of chunks
5//! (one dot product per chunk, auto-vectorized) and keeps the store free of
6//! dependencies.
7//!
8//! Every dataset records the dimension of its vectors; upserting or searching
9//! with a different dimension is an error (re-ingest after changing the
10//! embedder), never a silent empty result.
11//!
12//! With the `fs` feature the store can persist to a single JSON file. Each
13//! change is written while the store's write lock is held, to a unique temporary
14//! file that is flushed to disk and then atomically renamed over the target, so
15//! concurrent writers in one process cannot interleave and a crash leaves either
16//! the old or the new file. Several *processes* writing the same file are not
17//! coordinated; use one writer per file. For bulk loads, turn off
18//! [`MemoryStore::set_autosave`] and call [`MemoryStore::flush`] at the end.
19
20use std::collections::{HashMap, HashSet};
21use std::sync::{Arc, RwLock};
22
23use futures::future::BoxFuture;
24
25use crate::error::RagError;
26use crate::filter::MetadataFilter;
27use crate::types::{
28    DocumentSummary, Hit, KeywordQuery, PER_CHUNK_KEYS, StoredChunk, VectorQuery, VectorStore, check_vector,
29    is_disabled,
30};
31
32/// BM25 parameters.
33const BM25_K1: f32 = 1.2;
34const BM25_B: f32 = 0.75;
35
36#[derive(Debug)]
37struct Entry {
38    chunk: StoredChunk,
39    norm: f32,
40    /// Term -> frequency in this chunk.
41    terms: HashMap<String, u32>,
42    length: u32,
43}
44
45#[derive(Debug, Default)]
46struct Dataset {
47    entries: Vec<Entry>,
48    /// Chunk id -> index in `entries`.
49    by_id: HashMap<String, usize>,
50    /// Document id -> chunk ids.
51    by_document: HashMap<String, HashSet<String>>,
52    /// Content hash -> number of chunks with it.
53    hashes: HashMap<String, u32>,
54    /// Term -> number of chunks containing it.
55    doc_freq: HashMap<String, u32>,
56    total_length: u64,
57    /// Dimension shared by every vector of the dataset.
58    dimension: Option<usize>,
59}
60
61impl Dataset {
62    fn insert(&mut self, chunk: StoredChunk) {
63        if let Some(&ix) = self.by_id.get(&chunk.id) {
64            self.remove_at(ix);
65        }
66        let terms = term_frequencies(&chunk.text);
67        let length = terms.values().sum();
68        for term in terms.keys() {
69            *self.doc_freq.entry(term.clone()).or_insert(0) += 1;
70        }
71        self.total_length += u64::from(length);
72        self.dimension = Some(chunk.vector.len());
73        *self.hashes.entry(chunk.content_hash.clone()).or_insert(0) += 1;
74        self.by_document.entry(chunk.document_id.clone()).or_default().insert(chunk.id.clone());
75        let norm = norm(&chunk.vector);
76        self.by_id.insert(chunk.id.clone(), self.entries.len());
77        self.entries.push(Entry { chunk, norm, terms, length });
78    }
79
80    /// Remove the entry at `ix` (swap-remove, fixing up the moved entry's index).
81    fn remove_at(&mut self, ix: usize) {
82        if ix >= self.entries.len() {
83            return;
84        }
85        let removed = self.entries.swap_remove(ix);
86        self.by_id.remove(&removed.chunk.id);
87        if let Some(ids) = self.by_document.get_mut(&removed.chunk.document_id) {
88            ids.remove(&removed.chunk.id);
89            if ids.is_empty() {
90                self.by_document.remove(&removed.chunk.document_id);
91            }
92        }
93        if let Some(count) = self.hashes.get_mut(&removed.chunk.content_hash) {
94            *count = count.saturating_sub(1);
95            if *count == 0 {
96                self.hashes.remove(&removed.chunk.content_hash);
97            }
98        }
99        for term in removed.terms.keys() {
100            if let Some(df) = self.doc_freq.get_mut(term) {
101                *df = df.saturating_sub(1);
102                if *df == 0 {
103                    self.doc_freq.remove(term);
104                }
105            }
106        }
107        self.total_length = self.total_length.saturating_sub(u64::from(removed.length));
108        if let Some(moved) = self.entries.get(ix) {
109            self.by_id.insert(moved.chunk.id.clone(), ix);
110        }
111        if self.entries.is_empty() {
112            self.dimension = None;
113        }
114    }
115
116    fn remove_id(&mut self, id: &str) -> bool {
117        match self.by_id.get(id).copied() {
118            Some(ix) => {
119                self.remove_at(ix);
120                true
121            }
122            None => false,
123        }
124    }
125
126    fn remove_document(&mut self, document_id: &str) -> usize {
127        let ids: Vec<String> =
128            self.by_document.get(document_id).map(|s| s.iter().cloned().collect()).unwrap_or_default();
129        ids.iter().filter(|id| self.remove_id(id)).count()
130    }
131
132    fn check_dimension(&self, dataset_id: &str, len: usize, what: &str) -> Result<(), RagError> {
133        match self.dimension {
134            Some(d) if d != len => Err(RagError::Input(format!(
135                "dataset `{dataset_id}` holds {d}-dimensional vectors but {what} is {len}-dimensional; \
136                 use the original embedder or re-ingest the dataset"
137            ))),
138            _ => Ok(()),
139        }
140    }
141}
142
143type Data = HashMap<String, Dataset>;
144
145/// In-memory [`VectorStore`] with cosine similarity and BM25 keyword search.
146#[derive(Debug, Default, Clone)]
147pub struct MemoryStore {
148    inner: Arc<RwLock<Data>>,
149    #[cfg(feature = "fs")]
150    file: Option<Arc<persistence::FileState>>,
151}
152
153impl MemoryStore {
154    pub fn new() -> Self {
155        Self::default()
156    }
157
158    /// Number of chunks across all datasets (0 if the store is unusable after a panic).
159    pub fn len(&self) -> usize {
160        self.read(|d| d.values().map(|ds| ds.entries.len()).sum()).unwrap_or(0)
161    }
162
163    pub fn is_empty(&self) -> bool {
164        self.len() == 0
165    }
166
167    /// All stored chunks (for export / inspection).
168    pub fn chunks(&self) -> Result<Vec<StoredChunk>, RagError> {
169        self.read(all_chunks)
170    }
171
172    fn read<T>(&self, f: impl FnOnce(&Data) -> T) -> Result<T, RagError> {
173        let guard = self.inner.read().map_err(|_| poisoned())?;
174        Ok(f(&guard))
175    }
176
177    /// Apply a change, then persist it (with the `fs` feature) while the write lock
178    /// is still held, so writes and file updates happen in the same order.
179    fn write<T>(&self, f: impl FnOnce(&mut Data) -> Result<T, RagError>) -> Result<T, RagError> {
180        let mut guard = self.inner.write().map_err(|_| poisoned())?;
181        let result = f(&mut guard)?;
182        self.persist_locked(&guard)?;
183        Ok(result)
184    }
185
186    /// Insert or replace chunks. The whole batch is validated first, so an error
187    /// leaves the store unchanged.
188    pub(crate) fn insert_all(&self, chunks: Vec<StoredChunk>) -> Result<(), RagError> {
189        self.write(|data| insert_batch(data, chunks))
190    }
191
192    /// Replace the whole content with `chunks` (validated first; unchanged on error).
193    #[cfg_attr(not(feature = "sqlite"), allow(dead_code))]
194    pub(crate) fn replace_all(&self, chunks: Vec<StoredChunk>) -> Result<(), RagError> {
195        self.write(|data| {
196            let mut fresh = Data::new();
197            insert_batch(&mut fresh, chunks)?;
198            *data = fresh;
199            Ok(())
200        })
201    }
202
203    pub(crate) fn remove_document(&self, dataset_id: &str, document_id: &str) -> Result<usize, RagError> {
204        self.write(|data| Ok(data.get_mut(dataset_id).map_or(0, |ds| ds.remove_document(document_id))))
205    }
206
207    pub(crate) fn remove_dataset(&self, dataset_id: &str) -> Result<usize, RagError> {
208        self.write(|data| Ok(data.remove(dataset_id).map_or(0, |ds| ds.entries.len())))
209    }
210
211    pub(crate) fn remove_chunks(&self, dataset_id: &str, ids: &[String]) -> Result<usize, RagError> {
212        self.write(|data| Ok(data.get_mut(dataset_id).map_or(0, |ds| ids.iter().filter(|id| ds.remove_id(id)).count())))
213    }
214
215    pub(crate) fn find_document_chunks(
216        &self,
217        dataset_id: &str,
218        document_id: &str,
219    ) -> Result<Vec<StoredChunk>, RagError> {
220        self.read(|data| {
221            let Some(ds) = data.get(dataset_id) else { return Vec::new() };
222            let Some(ids) = ds.by_document.get(document_id) else { return Vec::new() };
223            ids.iter()
224                .filter_map(|id| ds.by_id.get(id).and_then(|&ix| ds.entries.get(ix)))
225                .map(|e| e.chunk.clone())
226                .collect()
227        })
228    }
229
230    /// Exact cosine search over every chunk of the requested datasets.
231    pub(crate) fn vector_search(&self, query: &VectorQuery<'_>) -> Result<Vec<Hit>, RagError> {
232        check_vector(query.vector, "the query")?;
233        self.read(|data| {
234            let q_norm = norm(query.vector);
235            let mut scored: Vec<(f32, &Entry)> = Vec::new();
236            for (id, ds) in query.datasets.iter().filter_map(|id| data.get(id).map(|ds| (id, ds))) {
237                ds.check_dimension(id, query.vector.len(), "the query")?;
238                for entry in &ds.entries {
239                    if !passes(query.filter, &entry.chunk) {
240                        continue;
241                    }
242                    let denom = q_norm * entry.norm;
243                    let score = if denom > 0.0 { dot(query.vector, &entry.chunk.vector) / denom } else { 0.0 };
244                    scored.push((score, entry));
245                }
246            }
247            Ok(top_hits(scored, query.top_k))
248        })?
249    }
250
251    /// BM25 search with per-dataset statistics.
252    pub(crate) fn bm25_search(&self, query: &KeywordQuery<'_>) -> Result<Vec<Hit>, RagError> {
253        let terms: Vec<String> = tokenize(query.text);
254        self.read(|data| {
255            let mut scored: Vec<(f32, &Entry)> = Vec::new();
256            for ds in query.datasets.iter().filter_map(|id| data.get(id)) {
257                let n = ds.entries.len();
258                if n == 0 {
259                    continue;
260                }
261                #[allow(clippy::cast_precision_loss)]
262                let (n_f, avgdl) = (n as f32, (ds.total_length as f32 / n as f32).max(1.0));
263                for entry in &ds.entries {
264                    if !passes(query.filter, &entry.chunk) {
265                        continue;
266                    }
267                    let mut score = 0.0f32;
268                    #[allow(clippy::cast_precision_loss)]
269                    let dl = entry.length as f32;
270                    for term in &terms {
271                        let Some(&tf) = entry.terms.get(term) else { continue };
272                        #[allow(clippy::cast_precision_loss)]
273                        let df = ds.doc_freq.get(term).copied().unwrap_or(0) as f32;
274                        let idf = ((n_f - df + 0.5) / (df + 0.5) + 1.0).ln();
275                        #[allow(clippy::cast_precision_loss)]
276                        let tf = tf as f32;
277                        score += idf * (tf * (BM25_K1 + 1.0)) / (tf + BM25_K1 * (1.0 - BM25_B + BM25_B * dl / avgdl));
278                    }
279                    if score > 0.0 {
280                        scored.push((score, entry));
281                    }
282                }
283            }
284            top_hits(scored, query.top_k)
285        })
286    }
287
288    /// Documents of a dataset ordered by id, `limit` at most, after the `after` id.
289    pub(crate) fn document_summaries(
290        &self,
291        dataset_id: &str,
292        limit: usize,
293        after: Option<&str>,
294    ) -> Result<Vec<DocumentSummary>, RagError> {
295        self.read(|data| {
296            let Some(ds) = data.get(dataset_id) else { return Vec::new() };
297            let mut ids: Vec<&String> =
298                ds.by_document.keys().filter(|id| after.is_none_or(|after| id.as_str() > after)).collect();
299            ids.sort_unstable();
300            ids.into_iter().take(limit).map(|id| summarize(ds, id)).collect()
301        })
302    }
303
304    pub(crate) fn has_hash(&self, dataset_id: &str, content_hash: &str) -> Result<bool, RagError> {
305        self.read(|data| data.get(dataset_id).is_some_and(|ds| ds.hashes.contains_key(content_hash)))
306    }
307
308    #[cfg(not(feature = "fs"))]
309    fn persist_locked(&self, _data: &Data) -> Result<(), RagError> {
310        Ok(())
311    }
312}
313
314/// Summary of one document from its chunks (title and metadata from the first chunk).
315fn summarize(ds: &Dataset, document_id: &str) -> DocumentSummary {
316    let mut chunks: Vec<&StoredChunk> = ds
317        .by_document
318        .get(document_id)
319        .into_iter()
320        .flatten()
321        .filter_map(|id| ds.by_id.get(id).and_then(|&ix| ds.entries.get(ix)))
322        .map(|e| &e.chunk)
323        .collect();
324    chunks.sort_by_key(|c| c.metadata.get("chunk_index").and_then(serde_json::Value::as_u64).unwrap_or(u64::MAX));
325    let first = chunks.first();
326    let mut metadata = first.map(|c| c.metadata.clone()).unwrap_or_default();
327    for key in PER_CHUNK_KEYS {
328        metadata.remove(key);
329    }
330    DocumentSummary {
331        document_id: document_id.to_owned(),
332        title: first.map(|c| c.title.clone()).unwrap_or_default(),
333        chunks: chunks.len(),
334        characters: chunks.iter().map(|c| c.text.chars().count()).sum(),
335        enabled: !first.is_some_and(|c| is_disabled(&c.metadata)),
336        metadata,
337    }
338}
339
340/// Validate a batch (finite vectors, one dimension per dataset), then insert it.
341fn insert_batch(data: &mut Data, chunks: Vec<StoredChunk>) -> Result<(), RagError> {
342    let mut batch_dims: HashMap<&str, usize> = HashMap::new();
343    for chunk in &chunks {
344        check_vector(&chunk.vector, &format!("chunk `{}`", chunk.id))?;
345        let len = chunk.vector.len();
346        if let Some(ds) = data.get(&chunk.dataset_id) {
347            ds.check_dimension(&chunk.dataset_id, len, &format!("chunk `{}`", chunk.id))?;
348        }
349        match batch_dims.get(chunk.dataset_id.as_str()) {
350            Some(&d) if d != len => {
351                return Err(RagError::Input(format!(
352                    "chunks for dataset `{}` mix {d}- and {len}-dimensional vectors",
353                    chunk.dataset_id
354                )));
355            }
356            _ => {
357                batch_dims.insert(&chunk.dataset_id, len);
358            }
359        }
360    }
361    for chunk in chunks {
362        data.entry(chunk.dataset_id.clone()).or_default().insert(chunk);
363    }
364    Ok(())
365}
366
367fn poisoned() -> RagError {
368    RagError::Store("memory store lock poisoned by an earlier panic".into())
369}
370
371fn all_chunks(data: &Data) -> Vec<StoredChunk> {
372    data.values().flat_map(|ds| ds.entries.iter().map(|e| e.chunk.clone())).collect()
373}
374
375#[cfg(feature = "fs")]
376mod persistence {
377    use super::*;
378    use std::io::Write;
379    use std::path::{Path, PathBuf};
380    use std::sync::atomic::{AtomicBool, AtomicU64, Ordering};
381
382    #[derive(serde::Serialize, serde::Deserialize)]
383    struct FileFormat {
384        version: u32,
385        chunks: Vec<StoredChunk>,
386    }
387
388    /// Where and how the store persists itself.
389    #[derive(Debug)]
390    pub(super) struct FileState {
391        path: PathBuf,
392        autosave: AtomicBool,
393        /// Changes not yet written (autosave off, or a failed write).
394        dirty: AtomicBool,
395    }
396
397    static TEMP_COUNTER: AtomicU64 = AtomicU64::new(0);
398
399    impl MemoryStore {
400        /// Open a store backed by `path`: existing content is loaded, and every
401        /// change is written back (see the module docs for the guarantees).
402        pub fn open(path: impl Into<PathBuf>) -> Result<Self, RagError> {
403            let path = path.into();
404            let store = Self { inner: Arc::default(), file: None };
405            if path.exists() {
406                let text =
407                    std::fs::read_to_string(&path).map_err(|e| RagError::Io(format!("{}: {e}", path.display())))?;
408                let file: FileFormat =
409                    serde_json::from_str(&text).map_err(|e| RagError::Decode(format!("{}: {e}", path.display())))?;
410                if file.version != 1 {
411                    return Err(RagError::Decode(format!("unsupported store file version {}", file.version)));
412                }
413                store.insert_all(file.chunks)?;
414            }
415            let file = FileState { path, autosave: AtomicBool::new(true), dirty: AtomicBool::new(false) };
416            Ok(Self { file: Some(Arc::new(file)), ..store })
417        }
418
419        /// Write after every change (default `true`). With autosave off, changes stay
420        /// in memory until [`MemoryStore::flush`].
421        pub fn set_autosave(&self, autosave: bool) {
422            if let Some(file) = &self.file {
423                file.autosave.store(autosave, Ordering::SeqCst);
424            }
425        }
426
427        /// Write pending changes to the backing file (no-op for in-memory stores).
428        pub fn flush(&self) -> Result<(), RagError> {
429            let guard = self.inner.read().map_err(|_| poisoned())?;
430            match &self.file {
431                Some(file) if file.dirty.load(Ordering::SeqCst) => write_file(file, &guard),
432                _ => Ok(()),
433            }
434        }
435
436        /// Write the whole store to `path` (temp file + fsync + rename).
437        pub fn save_to(&self, path: &Path) -> Result<(), RagError> {
438            let guard = self.inner.read().map_err(|_| poisoned())?;
439            write_atomically(path, &all_chunks(&guard))
440        }
441
442        pub(super) fn persist_locked(&self, data: &Data) -> Result<(), RagError> {
443            let Some(file) = &self.file else { return Ok(()) };
444            file.dirty.store(true, Ordering::SeqCst);
445            if file.autosave.load(Ordering::SeqCst) { write_file(file, data) } else { Ok(()) }
446        }
447    }
448
449    fn write_file(file: &FileState, data: &Data) -> Result<(), RagError> {
450        write_atomically(&file.path, &all_chunks(data))?;
451        file.dirty.store(false, Ordering::SeqCst);
452        Ok(())
453    }
454
455    fn write_atomically(path: &Path, chunks: &[StoredChunk]) -> Result<(), RagError> {
456        #[derive(serde::Serialize)]
457        struct FileRef<'a> {
458            version: u32,
459            chunks: &'a [StoredChunk],
460        }
461        let text = serde_json::to_vec(&FileRef { version: 1, chunks })
462            .map_err(|e| RagError::Store(format!("cannot encode store: {e}")))?;
463        let n = TEMP_COUNTER.fetch_add(1, Ordering::SeqCst);
464        let name = path.file_name().map(|s| s.to_string_lossy().into_owned()).unwrap_or_else(|| "store".into());
465        let tmp = path.with_file_name(format!(".{name}.{}.{n}.tmp", std::process::id()));
466        let io = |p: &Path, e: std::io::Error| RagError::Io(format!("{}: {e}", p.display()));
467        let result = (|| {
468            let mut f = std::fs::File::create(&tmp).map_err(|e| io(&tmp, e))?;
469            f.write_all(&text).map_err(|e| io(&tmp, e))?;
470            f.sync_all().map_err(|e| io(&tmp, e))?;
471            std::fs::rename(&tmp, path).map_err(|e| io(path, e))?;
472            sync_parent_dir(path);
473            Ok(())
474        })();
475        if result.is_err() {
476            let _cleanup = std::fs::remove_file(&tmp);
477        }
478        result
479    }
480
481    /// Make the rename durable. Directories cannot be opened for syncing on every
482    /// platform; failure only weakens crash durability, so it is ignored.
483    fn sync_parent_dir(path: &Path) {
484        #[cfg(unix)]
485        if let Some(dir) = path.parent().filter(|p| !p.as_os_str().is_empty())
486            && let Ok(handle) = std::fs::File::open(dir)
487        {
488            let _best_effort = handle.sync_all();
489        }
490        #[cfg(not(unix))]
491        let _ = path;
492    }
493}
494
495impl VectorStore for MemoryStore {
496    fn upsert(&self, chunks: Vec<StoredChunk>) -> BoxFuture<'_, Result<(), RagError>> {
497        Box::pin(futures::future::ready(self.insert_all(chunks)))
498    }
499
500    fn delete_document<'a>(
501        &'a self,
502        dataset_id: &'a str,
503        document_id: &'a str,
504    ) -> BoxFuture<'a, Result<usize, RagError>> {
505        Box::pin(futures::future::ready(self.remove_document(dataset_id, document_id)))
506    }
507
508    fn delete_dataset<'a>(&'a self, dataset_id: &'a str) -> BoxFuture<'a, Result<usize, RagError>> {
509        Box::pin(futures::future::ready(self.remove_dataset(dataset_id)))
510    }
511
512    fn document_chunks<'a>(
513        &'a self,
514        dataset_id: &'a str,
515        document_id: &'a str,
516    ) -> BoxFuture<'a, Result<Vec<StoredChunk>, RagError>> {
517        Box::pin(futures::future::ready(self.find_document_chunks(dataset_id, document_id)))
518    }
519
520    fn delete_chunks<'a>(&'a self, dataset_id: &'a str, ids: &'a [String]) -> BoxFuture<'a, Result<usize, RagError>> {
521        Box::pin(futures::future::ready(self.remove_chunks(dataset_id, ids)))
522    }
523
524    fn list_documents<'a>(
525        &'a self,
526        dataset_id: &'a str,
527        limit: usize,
528        after: Option<&'a str>,
529    ) -> BoxFuture<'a, Result<Vec<DocumentSummary>, RagError>> {
530        Box::pin(futures::future::ready(self.document_summaries(dataset_id, limit, after)))
531    }
532
533    fn search<'a>(&'a self, query: VectorQuery<'a>) -> BoxFuture<'a, Result<Vec<Hit>, RagError>> {
534        Box::pin(futures::future::ready(self.vector_search(&query)))
535    }
536
537    fn supports_keyword(&self) -> bool {
538        true
539    }
540
541    fn keyword_search<'a>(&'a self, query: KeywordQuery<'a>) -> BoxFuture<'a, Result<Vec<Hit>, RagError>> {
542        Box::pin(futures::future::ready(self.bm25_search(&query)))
543    }
544
545    fn contains_hash<'a>(
546        &'a self,
547        dataset_id: &'a str,
548        content_hash: &'a str,
549    ) -> BoxFuture<'a, Result<bool, RagError>> {
550        Box::pin(futures::future::ready(self.has_hash(dataset_id, content_hash)))
551    }
552}
553
554fn passes(filter: Option<&MetadataFilter>, chunk: &StoredChunk) -> bool {
555    !is_disabled(&chunk.metadata) && filter.is_none_or(|f| f.matches(&chunk.metadata))
556}
557
558fn top_hits(mut scored: Vec<(f32, &Entry)>, top_k: usize) -> Vec<Hit> {
559    scored.retain(|(score, _)| score.is_finite());
560    scored.sort_by(|a, b| b.0.total_cmp(&a.0));
561    scored.into_iter().take(top_k).map(|(score, e)| Hit::from_chunk(&e.chunk, score)).collect()
562}
563
564/// Dot product written as 8 independent accumulators so the compiler can vectorize it.
565pub fn dot(a: &[f32], b: &[f32]) -> f32 {
566    let mut acc = [0.0f32; 8];
567    let chunks_a = a.chunks_exact(8);
568    let chunks_b = b.chunks_exact(8);
569    let (rest_a, rest_b) = (chunks_a.remainder(), chunks_b.remainder());
570    for (x, y) in chunks_a.zip(chunks_b) {
571        for ((slot, xi), yi) in acc.iter_mut().zip(x).zip(y) {
572            *slot += xi * yi;
573        }
574    }
575    let tail: f32 = rest_a.iter().zip(rest_b).map(|(x, y)| x * y).sum();
576    acc.iter().sum::<f32>() + tail
577}
578
579/// Euclidean norm.
580pub fn norm(v: &[f32]) -> f32 {
581    dot(v, v).sqrt()
582}
583
584/// Cosine similarity (0 when either vector is zero or lengths differ).
585pub fn cosine(a: &[f32], b: &[f32]) -> f32 {
586    if a.len() != b.len() {
587        return 0.0;
588    }
589    let denom = norm(a) * norm(b);
590    if denom > 0.0 { dot(a, b) / denom } else { 0.0 }
591}
592
593/// Lower-cased alphanumeric tokens. CJK characters become one token each so
594/// languages without spaces still get a usable keyword index.
595pub fn tokenize(text: &str) -> Vec<String> {
596    let mut tokens = Vec::new();
597    let mut current = String::new();
598    for c in text.chars() {
599        if is_cjk(c) {
600            if !current.is_empty() {
601                tokens.push(std::mem::take(&mut current));
602            }
603            tokens.push(c.to_string());
604        } else if c.is_alphanumeric() {
605            current.extend(c.to_lowercase());
606        } else if !current.is_empty() {
607            tokens.push(std::mem::take(&mut current));
608        }
609    }
610    if !current.is_empty() {
611        tokens.push(current);
612    }
613    tokens
614}
615
616fn is_cjk(c: char) -> bool {
617    matches!(u32::from(c), 0x3040..=0x30FF | 0x3400..=0x4DBF | 0x4E00..=0x9FFF | 0xAC00..=0xD7AF | 0xF900..=0xFAFF)
618}
619
620fn term_frequencies(text: &str) -> HashMap<String, u32> {
621    let mut map = HashMap::new();
622    for t in tokenize(text) {
623        *map.entry(t).or_insert(0) += 1;
624    }
625    map
626}
627
628#[cfg(test)]
629mod tests {
630    use super::*;
631
632    fn chunk(id: &str, ds: &str, text: &str, vector: Vec<f32>) -> StoredChunk {
633        StoredChunk {
634            id: id.into(),
635            dataset_id: ds.into(),
636            document_id: format!("doc-{id}"),
637            title: String::new(),
638            text: text.into(),
639            metadata: serde_json::Map::new(),
640            content_hash: crate::types::content_hash(ds, text),
641            vector,
642        }
643    }
644
645    fn block_on<F: std::future::Future>(f: F) -> F::Output {
646        futures::executor::block_on(f)
647    }
648
649    #[test]
650    fn cosine_ranking_and_dataset_scoping() {
651        let store = MemoryStore::new();
652        block_on(store.upsert(vec![
653            chunk("a", "d1", "a", vec![1.0, 0.0, 0.0]),
654            chunk("b", "d1", "b", vec![0.7, 0.7, 0.0]),
655            chunk("c", "d2", "c", vec![1.0, 0.0, 0.0]),
656        ]))
657        .unwrap();
658        let ds = vec!["d1".to_owned()];
659        let hits =
660            block_on(store.search(VectorQuery { datasets: &ds, vector: &[1.0, 0.1, 0.0], top_k: 5, filter: None }))
661                .unwrap();
662        assert_eq!(hits.iter().map(|h| h.id.as_str()).collect::<Vec<_>>(), vec!["a", "b"]);
663        assert!(hits[0].score > hits[1].score);
664    }
665
666    #[test]
667    fn bm25_prefers_rare_terms() {
668        let store = MemoryStore::new();
669        block_on(store.upsert(vec![
670            chunk("1", "d", "the cat sat on the mat", vec![1.0]),
671            chunk("2", "d", "the dog chased the cat", vec![1.0]),
672            chunk("3", "d", "quantum entanglement explained", vec![1.0]),
673        ]))
674        .unwrap();
675        let ds = vec!["d".to_owned()];
676        let hits = block_on(store.keyword_search(KeywordQuery { datasets: &ds, text: "dog", top_k: 5, filter: None }))
677            .unwrap();
678        assert_eq!(hits.len(), 1);
679        assert_eq!(hits[0].id, "2");
680        let hits =
681            block_on(store.keyword_search(KeywordQuery { datasets: &ds, text: "cat quantum", top_k: 5, filter: None }))
682                .unwrap();
683        assert_eq!(hits[0].id, "3", "rare term outweighs common one");
684    }
685
686    #[test]
687    fn upsert_replaces_and_delete_updates_index() {
688        let store = MemoryStore::new();
689        block_on(store.upsert(vec![chunk("x", "d", "apple banana", vec![1.0]), chunk("y", "d", "apple", vec![1.0])]))
690            .unwrap();
691        block_on(store.upsert(vec![chunk("x", "d", "cherry", vec![1.0])])).unwrap();
692        assert_eq!(store.len(), 2);
693        let ds = vec!["d".to_owned()];
694        let hits =
695            block_on(store.keyword_search(KeywordQuery { datasets: &ds, text: "banana", top_k: 5, filter: None }))
696                .unwrap();
697        assert!(hits.is_empty());
698        assert_eq!(block_on(store.delete_document("d", "doc-y")).unwrap(), 1);
699        assert_eq!(store.len(), 1);
700        assert_eq!(block_on(store.delete_dataset("d")).unwrap(), 1);
701        assert!(store.is_empty());
702    }
703
704    #[test]
705    fn dot_matches_naive() {
706        let a: Vec<f32> = (0..37).map(|i| i as f32 * 0.5).collect();
707        let b: Vec<f32> = (0..37).map(|i| (37 - i) as f32).collect();
708        let naive: f32 = a.iter().zip(&b).map(|(x, y)| x * y).sum();
709        assert!((dot(&a, &b) - naive).abs() < 1e-3);
710        assert!((cosine(&[1.0, 0.0], &[0.0, 1.0])).abs() < 1e-6);
711    }
712
713    #[test]
714    fn tokenizer_handles_cjk() {
715        assert_eq!(tokenize("Hello, World! 日本"), vec!["hello", "world", "日", "本"]);
716    }
717
718    #[cfg(feature = "fs")]
719    #[test]
720    fn persistence_roundtrip() {
721        let dir = std::env::temp_dir().join(format!("graphrt-rag-test-{}", std::process::id()));
722        std::fs::create_dir_all(&dir).unwrap();
723        let path = dir.join("kb.json");
724        let _ = std::fs::remove_file(&path);
725        {
726            let store = MemoryStore::open(&path).unwrap();
727            block_on(store.upsert(vec![chunk("a", "d", "persist me", vec![0.5, 0.5])])).unwrap();
728        }
729        let reopened = MemoryStore::open(&path).unwrap();
730        assert_eq!(reopened.len(), 1);
731        let ds = vec!["d".to_owned()];
732        let hits =
733            block_on(reopened.keyword_search(KeywordQuery { datasets: &ds, text: "persist", top_k: 1, filter: None }))
734                .unwrap();
735        assert_eq!(hits[0].content, "persist me");
736        block_on(reopened.delete_dataset("d")).unwrap();
737        assert!(MemoryStore::open(&path).unwrap().is_empty());
738        let _ = std::fs::remove_dir_all(&dir);
739    }
740}