aboutsummaryrefslogtreecommitdiff
path: root/src/vec.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/vec.rs')
-rw-r--r--src/vec.rs651
1 files changed, 651 insertions, 0 deletions
diff --git a/src/vec.rs b/src/vec.rs
new file mode 100644
index 0000000..2c30ab5
--- /dev/null
+++ b/src/vec.rs
@@ -0,0 +1,651 @@
+//! The semantic side: embeddings from Ollama, a small vector store, and
+//! the ranking on top of it.
+//!
+//! One vector per chunk of a note (see `chunk.rs`). The store keeps two
+//! files next to each other: the vectors as f16 for exact scores, and one
+//! sign bit per dimension for a fast first pass by Hamming distance when
+//! there are very many chunks. Everything here can be rebuilt from the
+//! note files, so it lives in the index directory.
+
+use crate::chunk;
+use crate::graph::Graph;
+use crate::note::Note;
+use anyhow::{Context, Result, anyhow, bail};
+use half::f16;
+use serde::{Deserialize, Serialize};
+use std::collections::{HashMap, HashSet};
+use std::path::{Path, PathBuf};
+use std::time::Duration;
+
+pub const DEFAULT_MODEL: &str = "qwen3-embedding:0.6b";
+const BATCH: usize = 16;
+/// Above this many chunks, a Hamming pass narrows the candidates first.
+const EXACT_LIMIT: usize = 2000;
+
+// ---------------------------------------------------------------- Ollama
+
+pub struct Ollama {
+ url: String,
+ pub model: String,
+}
+
+/// Why a call to Ollama failed: it is not running, or it is something else.
+#[derive(Debug)]
+pub struct Unreachable(pub String);
+
+impl std::fmt::Display for Unreachable {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ write!(f, "{}", self.0)
+ }
+}
+
+impl std::error::Error for Unreachable {}
+
+impl Ollama {
+ pub fn from_env() -> Ollama {
+ Ollama {
+ url: std::env::var("ELEL_OLLAMA").unwrap_or_else(|_| "http://localhost:11434".into()),
+ model: std::env::var("ELEL_MODEL").unwrap_or_else(|_| DEFAULT_MODEL.into()),
+ }
+ }
+
+ /// Embed texts, already formatted for the model. The vectors are
+ /// normalized to length 1.
+ pub fn embed(&self, inputs: &[String]) -> Result<Vec<Vec<f32>>> {
+ let agent = ureq::AgentBuilder::new()
+ .timeout_connect(Duration::from_secs(3))
+ .timeout(Duration::from_secs(300))
+ .build();
+ let resp = agent
+ .post(&format!("{}/api/embed", self.url.trim_end_matches('/')))
+ .send_json(serde_json::json!({
+ "model": self.model,
+ "input": inputs,
+ "truncate": true,
+ }));
+ let v: serde_json::Value = match resp {
+ Ok(r) => r.into_json()?,
+ Err(ureq::Error::Status(404, _)) => bail!(
+ "model {} is not available in Ollama; run `ollama pull {}`",
+ self.model,
+ self.model
+ ),
+ Err(ureq::Error::Status(code, r)) => {
+ let body = r.into_string().unwrap_or_default();
+ bail!("Ollama answered {}: {}", code, body)
+ }
+ Err(e @ ureq::Error::Transport(_)) => {
+ return Err(anyhow::Error::new(Unreachable(format!(
+ "cannot reach Ollama at {} ({})",
+ self.url, e
+ ))));
+ }
+ };
+ let arr = v["embeddings"]
+ .as_array()
+ .ok_or_else(|| anyhow!("Ollama gave no embeddings: {}", v))?;
+ let mut out = Vec::new();
+ for e in arr {
+ let mut x: Vec<f32> = e
+ .as_array()
+ .ok_or_else(|| anyhow!("bad embedding"))?
+ .iter()
+ .map(|n| n.as_f64().unwrap_or(0.0) as f32)
+ .collect();
+ normalize(&mut x);
+ out.push(x);
+ }
+ if out.len() != inputs.len() {
+ bail!("asked for {} embeddings, got {}", inputs.len(), out.len());
+ }
+ Ok(out)
+ }
+
+ /// A note chunk, as the model wants a document.
+ pub fn doc_text(&self, text: &str) -> String {
+ if self.model.starts_with("embeddinggemma") {
+ format!("title: none | text: {}", text)
+ } else if self.model.starts_with("nomic-embed") {
+ format!("search_document: {}", text)
+ } else {
+ text.to_string()
+ }
+ }
+
+ /// A search text, as the model wants a query.
+ pub fn query_text(&self, text: &str) -> String {
+ if self.model.starts_with("qwen3-embedding") {
+ format!(
+ "Instruct: Given a search query, retrieve the notes that are about it\nQuery: {}",
+ text
+ )
+ } else if self.model.starts_with("embeddinggemma") {
+ format!("task: search result | query: {}", text)
+ } else if self.model.starts_with("nomic-embed") {
+ format!("search_query: {}", text)
+ } else {
+ text.to_string()
+ }
+ }
+
+ pub fn embed_query(&self, text: &str) -> Result<Vec<f32>> {
+ Ok(self.embed(&[self.query_text(text)])?.remove(0))
+ }
+}
+
+// ------------------------------------------------------------ vector math
+
+pub fn normalize(v: &mut [f32]) {
+ let n = v.iter().map(|x| x * x).sum::<f32>().sqrt();
+ if n > 0.0 {
+ for x in v.iter_mut() {
+ *x /= n;
+ }
+ }
+}
+
+pub fn dot(a: &[f32], b: &[f32]) -> f32 {
+ a.iter().zip(b).map(|(x, y)| x * y).sum()
+}
+
+/// The sign bits of a vector, packed eight to a byte.
+pub fn to_bits(v: &[f32]) -> Vec<u8> {
+ let mut out = vec![0u8; v.len().div_ceil(8)];
+ for (i, x) in v.iter().enumerate() {
+ if *x > 0.0 {
+ out[i / 8] |= 1 << (i % 8);
+ }
+ }
+ out
+}
+
+pub fn hamming(a: &[u8], b: &[u8]) -> u32 {
+ a.iter().zip(b).map(|(x, y)| (x ^ y).count_ones()).sum()
+}
+
+/// The normalized mean of some vectors.
+pub fn mean(vs: &[&[f32]]) -> Option<Vec<f32>> {
+ let first = vs.first()?;
+ let mut m = vec![0.0f32; first.len()];
+ for v in vs {
+ for (a, b) in m.iter_mut().zip(*v) {
+ *a += b;
+ }
+ }
+ normalize(&mut m);
+ Some(m)
+}
+
+/// The merged vector of some liked and some disliked vectors:
+/// `normalize(mean(pos) - 0.5 * mean(neg))`.
+pub fn rocchio(pos: &[Vec<f32>], neg: &[Vec<f32>]) -> Option<Vec<f32>> {
+ let p: Vec<&[f32]> = pos.iter().map(|v| v.as_slice()).collect();
+ let mut q = mean(&p)?;
+ let n: Vec<&[f32]> = neg.iter().map(|v| v.as_slice()).collect();
+ if let Some(nm) = mean(&n) {
+ for (a, b) in q.iter_mut().zip(&nm) {
+ *a -= 0.5 * b;
+ }
+ normalize(&mut q);
+ }
+ Some(q)
+}
+
+/// Reciprocal rank fusion of ranked lists of IDs: `sum 1/(60 + rank)`.
+pub fn rrf(lists: &[Vec<String>]) -> Vec<(String, f32)> {
+ let mut score: HashMap<&str, f32> = HashMap::new();
+ for l in lists {
+ for (r, id) in l.iter().enumerate() {
+ *score.entry(id).or_default() += 1.0 / (60.0 + r as f32 + 1.0);
+ }
+ }
+ let mut v: Vec<(String, f32)> = score.into_iter().map(|(k, s)| (k.to_string(), s)).collect();
+ v.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap().then(a.0.cmp(&b.0)));
+ v
+}
+
+// ------------------------------------------------------------------ store
+
+#[derive(Clone, Serialize, Deserialize)]
+pub struct Row {
+ pub id: String,
+ /// `Note.hash` when the vector was made.
+ pub hash: String,
+ /// Index of the chunk in the note.
+ pub chunk: usize,
+ /// 0-based line in the body where the chunk starts.
+ pub line: usize,
+}
+
+#[derive(Default, Serialize, Deserialize)]
+struct Meta {
+ model: String,
+ dim: usize,
+ rows: Vec<Row>,
+}
+
+#[derive(Default)]
+pub struct Store {
+ pub model: String,
+ pub dim: usize,
+ pub rows: Vec<Row>,
+ vecs: Vec<f32>,
+ bits: Vec<u8>,
+}
+
+/// A hit of the vector ranking.
+pub struct VecHit {
+ pub id: String,
+ pub score: f32,
+ /// The best chunk, when ranked by chunk.
+ pub row: Option<Row>,
+}
+
+pub fn dir(index: &Path) -> PathBuf {
+ index.join("vec")
+}
+
+impl Store {
+ pub fn load(index: &Path) -> Store {
+ let d = dir(index);
+ let meta: Meta = std::fs::read_to_string(d.join("meta.json"))
+ .ok()
+ .and_then(|s| serde_json::from_str(&s).ok())
+ .unwrap_or_default();
+ let raw = std::fs::read(d.join("f16.bin")).unwrap_or_default();
+ let want = meta.rows.len() * meta.dim * 2;
+ if meta.rows.is_empty() || raw.len() != want {
+ return Store::default();
+ }
+ let vecs: Vec<f32> = raw
+ .chunks_exact(2)
+ .map(|b| f16::from_le_bytes([b[0], b[1]]).to_f32())
+ .collect();
+ let bits = std::fs::read(d.join("bits.bin")).unwrap_or_default();
+ Store {
+ model: meta.model,
+ dim: meta.dim,
+ rows: meta.rows,
+ vecs,
+ bits,
+ }
+ }
+
+ pub fn is_empty(&self) -> bool {
+ self.rows.is_empty()
+ }
+
+ pub fn save(&self, index: &Path) -> Result<()> {
+ let d = dir(index);
+ std::fs::create_dir_all(&d)?;
+ let write = |name: &str, bytes: &[u8]| -> Result<()> {
+ let tmp = d.join(format!("{}.tmp", name));
+ std::fs::write(&tmp, bytes)?;
+ std::fs::rename(&tmp, d.join(name))?;
+ Ok(())
+ };
+ let mut f = Vec::with_capacity(self.vecs.len() * 2);
+ for x in &self.vecs {
+ f.extend_from_slice(&f16::from_f32(*x).to_le_bytes());
+ }
+ // The bit file must be consistent with the (rounded) f16 file.
+ write("f16.bin", &f)?;
+ write("bits.bin", &self.bits)?;
+ let meta = Meta {
+ model: self.model.clone(),
+ dim: self.dim,
+ rows: self.rows.clone(),
+ };
+ write("meta.json", &serde_json::to_vec(&meta)?)
+ }
+
+ fn vec_of(&self, i: usize) -> &[f32] {
+ &self.vecs[i * self.dim..(i + 1) * self.dim]
+ }
+
+ fn bits_of(&self, i: usize) -> &[u8] {
+ let w = self.dim.div_ceil(8);
+ &self.bits[i * w..(i + 1) * w]
+ }
+
+ /// Keep the rows for which `keep` is true.
+ pub fn retain(&mut self, keep: impl Fn(&Row) -> bool) {
+ let w = self.dim.div_ceil(8);
+ let mut rows = Vec::new();
+ let mut vecs = Vec::new();
+ let mut bits = Vec::new();
+ for (i, r) in self.rows.iter().enumerate() {
+ if keep(r) {
+ rows.push(r.clone());
+ vecs.extend_from_slice(self.vec_of(i));
+ bits.extend_from_slice(&self.bits[i * w..(i + 1) * w]);
+ }
+ }
+ self.rows = rows;
+ self.vecs = vecs;
+ self.bits = bits;
+ }
+
+ pub fn push(&mut self, row: Row, v: &[f32]) {
+ if self.rows.is_empty() {
+ self.dim = v.len();
+ }
+ self.bits.extend_from_slice(&to_bits(v));
+ self.vecs.extend_from_slice(v);
+ self.rows.push(row);
+ }
+
+ #[cfg(test)]
+ pub fn has(&self, id: &str, hash: &str) -> bool {
+ self.rows.iter().any(|r| r.id == id && r.hash == hash)
+ }
+
+ /// The vector of a whole note: the mean of its chunks.
+ pub fn note_vec(&self, id: &str) -> Option<Vec<f32>> {
+ let vs: Vec<&[f32]> = self
+ .rows
+ .iter()
+ .enumerate()
+ .filter(|(_, r)| r.id == id)
+ .map(|(i, _)| self.vec_of(i))
+ .collect();
+ mean(&vs)
+ }
+
+ /// All note vectors at once.
+ pub fn note_vecs(&self) -> HashMap<String, Vec<f32>> {
+ let mut groups: HashMap<&str, Vec<&[f32]>> = HashMap::new();
+ for (i, r) in self.rows.iter().enumerate() {
+ groups.entry(&r.id).or_default().push(self.vec_of(i));
+ }
+ groups
+ .into_iter()
+ .filter_map(|(id, vs)| mean(&vs).map(|m| (id.to_string(), m)))
+ .collect()
+ }
+
+ /// Rank the notes for the query vector `q`. With `by_chunk` a note
+ /// scores as its best chunk (for text queries); otherwise as the mean
+ /// of its chunks (for "like this note"). `allow` filters by ID.
+ pub fn rank(&self, q: &[f32], by_chunk: bool, allow: &dyn Fn(&str) -> bool) -> Vec<VecHit> {
+ let mut out: Vec<VecHit> = Vec::new();
+ if self.is_empty() || q.len() != self.dim {
+ return out;
+ }
+ if by_chunk {
+ let mut cand: Vec<usize> = (0..self.rows.len())
+ .filter(|&i| allow(&self.rows[i].id))
+ .collect();
+ if cand.len() > EXACT_LIMIT {
+ let qb = to_bits(q);
+ cand.sort_by_key(|&i| hamming(&qb, self.bits_of(i)));
+ cand.truncate(EXACT_LIMIT);
+ }
+ let mut best: HashMap<&str, (f32, usize)> = HashMap::new();
+ for i in cand {
+ let s = dot(q, self.vec_of(i));
+ let e = best.entry(&self.rows[i].id).or_insert((f32::MIN, i));
+ if s > e.0 {
+ *e = (s, i);
+ }
+ }
+ for (id, (s, i)) in best {
+ out.push(VecHit {
+ id: id.to_string(),
+ score: s,
+ row: Some(self.rows[i].clone()),
+ });
+ }
+ } else {
+ for (id, v) in self.note_vecs() {
+ if allow(&id) {
+ out.push(VecHit {
+ score: dot(q, &v),
+ id,
+ row: None,
+ });
+ }
+ }
+ }
+ out.sort_by(|a, b| b.score.partial_cmp(&a.score).unwrap().then(a.id.cmp(&b.id)));
+ out
+ }
+
+ /// Rank the tags for a note vector. The anchor of a tag is the mean
+ /// of the vectors of the other notes that carry it; tags with fewer
+ /// than two such notes are skipped.
+ pub fn tag_scores(&self, g: &Graph, id: &str, v: &[f32]) -> Vec<(String, usize, f32, bool)> {
+ let vecs = self.note_vecs();
+ let mut by_tag: HashMap<&str, Vec<&[f32]>> = HashMap::new();
+ let mut count: HashMap<&str, usize> = HashMap::new();
+ let mut has: HashSet<&str> = HashSet::new();
+ for n in g.notes.iter().filter(|n| n.id.is_some()) {
+ let nid = n.id.as_deref().unwrap();
+ for t in &n.tags {
+ *count.entry(t).or_default() += 1;
+ if nid == id {
+ has.insert(t);
+ } else if let Some(x) = vecs.get(nid) {
+ by_tag.entry(t).or_default().push(x);
+ }
+ }
+ }
+ let mut out = Vec::new();
+ for (t, vs) in by_tag {
+ if vs.len() < 2 {
+ continue;
+ }
+ if let Some(a) = mean(&vs) {
+ out.push((t.to_string(), count[t], dot(v, &a), has.contains(t)));
+ }
+ }
+ out.sort_by(|a, b| b.2.partial_cmp(&a.2).unwrap().then(a.0.cmp(&b.0)));
+ out
+ }
+}
+
+// ------------------------------------------------------------------ sync
+
+/// The text of the chunks of a note, formatted for the model.
+pub fn note_chunks(n: &Note) -> Vec<chunk::Chunk> {
+ chunk::chunks(&n.title, &n.tags, n.summary.as_deref(), &n.body)
+}
+
+pub struct SyncReport {
+ pub embedded: usize,
+ pub pending: usize,
+ pub error: Option<String>,
+}
+
+/// Bring the store up to date with the graph. Notes without a vector are
+/// embedded; vectors of notes that changed or vanished are dropped.
+/// If Ollama fails, the notes done so far are kept and the rest stay
+/// pending for the next run.
+pub fn sync(index: &Path, g: &Graph, ollama: &Ollama) -> Result<SyncReport> {
+ let mut store = Store::load(index);
+ if store.model != ollama.model {
+ store = Store::default();
+ }
+ let current: HashMap<&str, &str> = g
+ .notes
+ .iter()
+ .filter_map(|n| n.id.as_deref().map(|i| (i, n.hash.as_str())))
+ .collect();
+ store.retain(|r| current.get(r.id.as_str()) == Some(&r.hash.as_str()));
+ store.model = ollama.model.clone();
+ let have: HashSet<String> = store.rows.iter().map(|r| r.id.clone()).collect();
+ let mut seen: HashSet<&str> = HashSet::new();
+ let todo: Vec<&Note> = g
+ .notes
+ .iter()
+ .filter(|n| match n.id.as_deref() {
+ Some(i) => !have.contains(i) && seen.insert(i),
+ None => false,
+ })
+ .collect();
+ let total = todo.len();
+ let mut embedded = 0;
+ let mut error = None;
+ let mut parsed: HashMap<String, Vec<Note>> = HashMap::new();
+ // Work in groups of notes, so a failure never leaves half a note.
+ let mut group: Vec<(&Note, Vec<chunk::Chunk>)> = Vec::new();
+ let mut size = 0;
+ let flush = |group: &mut Vec<(&Note, Vec<chunk::Chunk>)>,
+ store: &mut Store|
+ -> Result<usize> {
+ if group.is_empty() {
+ return Ok(0);
+ }
+ let texts: Vec<String> = group
+ .iter()
+ .flat_map(|(_, cs)| cs.iter().map(|c| ollama.doc_text(&c.text)))
+ .collect();
+ let mut vs = Vec::new();
+ for b in texts.chunks(BATCH) {
+ let t0 = std::time::Instant::now();
+ vs.extend(ollama.embed(b)?);
+ if std::env::var_os("ELEL_DEBUG").is_some() {
+ eprintln!(
+ "embed batch of {}: {} chars, max {}, {:.1}s",
+ b.len(),
+ b.iter().map(|x| x.len()).sum::<usize>(),
+ b.iter().map(|x| x.len()).max().unwrap_or(0),
+ t0.elapsed().as_secs_f32()
+ );
+ }
+ }
+ let mut k = 0;
+ let mut notes = 0;
+ for (n, cs) in group.iter() {
+ for (ci, c) in cs.iter().enumerate() {
+ store.push(
+ Row {
+ id: n.id.clone().unwrap(),
+ hash: n.hash.clone(),
+ chunk: ci,
+ line: c.line,
+ },
+ &vs[k],
+ );
+ k += 1;
+ }
+ notes += 1;
+ }
+ group.clear();
+ Ok(notes)
+ };
+ 'work: for n in todo {
+ // The body is not in the manifest: read it from the file again.
+ let notes = match parsed.get(&n.path) {
+ Some(v) => v,
+ None => {
+ let content = match std::fs::read_to_string(&n.path) {
+ Ok(c) => c,
+ Err(_) => continue,
+ };
+ let v = crate::adapter::parse_file(Path::new(&n.path), &content).unwrap_or_default();
+ parsed.entry(n.path.clone()).or_insert(v)
+ }
+ };
+ let fresh = match notes.iter().find(|x| x.id == n.id && x.hash == n.hash) {
+ Some(f) => f,
+ None => continue,
+ };
+ let cs = note_chunks(fresh);
+ size += cs.len();
+ group.push((n, cs));
+ if size >= BATCH {
+ match flush(&mut group, &mut store) {
+ Ok(k) => embedded += k,
+ Err(e) => {
+ error = Some(e.to_string());
+ break 'work;
+ }
+ }
+ size = 0;
+ }
+ }
+ if error.is_none() {
+ match flush(&mut group, &mut store) {
+ Ok(k) => embedded += k,
+ Err(e) => error = Some(e.to_string()),
+ }
+ }
+ store.save(index).context("cannot save the vectors")?;
+ Ok(SyncReport {
+ embedded,
+ pending: total - embedded,
+ error,
+ })
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+
+ fn unit(v: &[f32]) -> Vec<f32> {
+ let mut x = v.to_vec();
+ normalize(&mut x);
+ x
+ }
+
+ #[test]
+ fn bits_and_hamming() {
+ let a = to_bits(&[1.0, -1.0, 1.0, 1.0, -1.0, -1.0, -1.0, -1.0, 1.0]);
+ assert_eq!(a, vec![0b0000_1101, 0b0000_0001]);
+ let b = to_bits(&[1.0, 1.0, 1.0, 1.0, -1.0, -1.0, -1.0, -1.0, -1.0]);
+ assert_eq!(hamming(&a, &b), 2);
+ }
+
+ #[test]
+ fn f16_round_trip_keeps_the_order() {
+ let dir = std::env::temp_dir().join(format!("elel-vec-{}", std::process::id()));
+ let mut s = Store::default();
+ s.model = "m".into();
+ let row = |id: &str| Row { id: id.into(), hash: "h".into(), chunk: 0, line: 0 };
+ s.push(row("a"), &unit(&[1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]));
+ s.push(row("b"), &unit(&[1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]));
+ s.push(row("c"), &unit(&[0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0]));
+ s.save(&dir).unwrap();
+ let t = Store::load(&dir);
+ std::fs::remove_dir_all(&dir).ok();
+ assert_eq!(t.rows.len(), 3);
+ let q = unit(&[1.0, 0.2, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]);
+ let r = t.rank(&q, true, &|_| true);
+ assert_eq!(r.iter().map(|h| h.id.as_str()).collect::<Vec<_>>(), vec!["a", "b", "c"]);
+ let r = t.rank(&q, false, &|id| id != "a");
+ assert_eq!(r[0].id, "b");
+ }
+
+ #[test]
+ fn rocchio_moves_away_from_the_negative() {
+ let pos = vec![unit(&[1.0, 1.0, 0.0])];
+ let neg = vec![unit(&[0.0, 1.0, 0.0])];
+ let q = rocchio(&pos, &neg).unwrap();
+ assert!(q[0] > q[1], "{:?}", q);
+ let plain = rocchio(&pos, &[]).unwrap();
+ assert!((plain[0] - plain[1]).abs() < 1e-6);
+ assert!(rocchio(&[], &neg).is_none());
+ }
+
+ #[test]
+ fn rrf_prefers_notes_high_in_both_lists() {
+ let l1 = vec!["a".to_string(), "b".into(), "c".into()];
+ let l2 = vec!["b".to_string(), "c".into(), "d".into()];
+ let r = rrf(&[l1, l2]);
+ assert_eq!(r[0].0, "b");
+ assert_eq!(r.len(), 4);
+ }
+
+ #[test]
+ fn retain_drops_stale_rows() {
+ let mut s = Store::default();
+ let row = |id: &str, h: &str| Row { id: id.into(), hash: h.into(), chunk: 0, line: 0 };
+ s.push(row("a", "1"), &unit(&[1.0, 0.0]));
+ s.push(row("b", "1"), &unit(&[0.0, 1.0]));
+ s.retain(|r| r.id == "a" && r.hash == "1");
+ assert_eq!(s.rows.len(), 1);
+ assert!(s.has("a", "1") && !s.has("b", "1"));
+ assert_eq!(s.vec_of(0), &[1.0, 0.0]);
+ }
+}