From 5b9a806af13d38163156302097e405a7b145b6cc Mon Sep 17 00:00:00 2001 From: JSDurand Date: Thu, 19 Nov 2026 09:29:47 +0800 Subject: elel: notes engine (Rust) and Gnus-like Emacs frontend Tantivy full text index, link graph, inline query filters, Ollama embeddings with paragraph chunks, and an Elisp summary/article UI. Co-Authored-By: Claude Sonnet 5.5 --- src/graph.rs | 187 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 187 insertions(+) create mode 100644 src/graph.rs (limited to 'src/graph.rs') diff --git a/src/graph.rs b/src/graph.rs new file mode 100644 index 0000000..460bdec --- /dev/null +++ b/src/graph.rs @@ -0,0 +1,187 @@ +//! The manifest (what was indexed) and the graph built from it. +//! +//! The manifest is a small JSON file. The graph is rebuilt in memory +//! on every call; with thousands of notes this takes microseconds. + +use crate::note::Note; +use anyhow::Result; +use serde::{Deserialize, Serialize}; +use std::collections::{BTreeMap, HashMap, HashSet, VecDeque}; +use std::path::Path; + +#[derive(Serialize, Deserialize)] +pub struct FileEntry { + pub hash: String, + pub notes: Vec, +} + +#[derive(Default, Serialize, Deserialize)] +pub struct Manifest { + pub files: BTreeMap, +} + +impl Manifest { + pub fn load(path: &Path) -> Manifest { + std::fs::read_to_string(path) + .ok() + .and_then(|s| serde_json::from_str(&s).ok()) + .unwrap_or_default() + } + + /// Write through a temporary file so a crash cannot leave half a file. + pub fn save(&self, path: &Path) -> Result<()> { + let tmp = path.with_extension("json.tmp"); + std::fs::write(&tmp, serde_json::to_vec(self)?)?; + std::fs::rename(&tmp, path)?; + Ok(()) + } +} + +/// How a note is reached from the note we started at. +#[derive(Clone, Copy, PartialEq, Eq, Debug)] +pub enum Rel { + Parent, + Child, + Link, + Backlink, +} + +impl Rel { + pub fn name(self) -> &'static str { + match self { + Rel::Parent => "parent", + Rel::Child => "child", + Rel::Link => "link", + Rel::Backlink => "backlink", + } + } +} + +pub struct Graph { + pub notes: Vec, + by_id: HashMap, + children: HashMap>, + backlinks: HashMap>, + pub duplicates: Vec<(String, Vec)>, +} + +impl Graph { + pub fn build(m: &Manifest) -> Graph { + let notes: Vec = m.files.values().flat_map(|f| f.notes.clone()).collect(); + let mut by_id: HashMap = HashMap::new(); + let mut seen: HashMap> = HashMap::new(); + for (i, n) in notes.iter().enumerate() { + if let Some(id) = &n.id { + seen.entry(id.clone()).or_default().push(i); + by_id.entry(id.clone()).or_insert(i); + } + } + let mut duplicates: Vec<(String, Vec)> = + seen.into_iter().filter(|(_, v)| v.len() > 1).collect(); + duplicates.sort(); + let mut children: HashMap> = HashMap::new(); + let mut backlinks: HashMap> = HashMap::new(); + for (i, n) in notes.iter().enumerate() { + if n.id.is_none() { + continue; + } + if let Some(p) = &n.parent { + children.entry(p.clone()).or_default().push(i); + } + for l in &n.links { + backlinks.entry(l.dst.clone()).or_default().push(i); + } + } + Graph { + notes, + by_id, + children, + backlinks, + duplicates, + } + } + + pub fn get(&self, id: &str) -> Option<&Note> { + self.by_id.get(id).map(|&i| &self.notes[i]) + } + + pub fn parent_of(&self, id: &str) -> Option<&Note> { + self.get(id) + .and_then(|n| n.parent.as_deref()) + .and_then(|p| self.get(p)) + } + + pub fn children_of(&self, id: &str) -> Vec<&Note> { + self.idx(self.children.get(id)) + } + + pub fn backlinks_of(&self, id: &str) -> Vec<&Note> { + self.idx(self.backlinks.get(id)) + } + + pub fn outlinks_of(&self, id: &str) -> Vec<&Note> { + match self.get(id) { + Some(n) => n.links.iter().filter_map(|l| self.get(&l.dst)).collect(), + None => Vec::new(), + } + } + + fn idx(&self, v: Option<&Vec>) -> Vec<&Note> { + match v { + Some(v) => v.iter().map(|&i| &self.notes[i]).collect(), + None => Vec::new(), + } + } + + /// Does the note have a link or a backlink or a parent or a child? + pub fn is_connected(&self, n: &Note) -> bool { + let id = match &n.id { + Some(id) => id, + None => return false, + }; + n.parent.is_some() + || !n.links.is_empty() + || self.children.contains_key(id) + || self.backlinks.contains_key(id) + } + + /// Breadth-first search over all relations, ignoring direction. + /// Returns (note, distance, relation at the first step). + pub fn reach(&self, id: &str, hops: usize) -> Vec<(&Note, usize, Rel)> { + let mut out = Vec::new(); + let mut seen: HashSet<&str> = HashSet::new(); + seen.insert(id); + let mut queue: VecDeque<(&str, usize, Option)> = VecDeque::new(); + queue.push_back((id, 0, None)); + while let Some((cur, d, first)) = queue.pop_front() { + if d == hops { + continue; + } + let mut next: Vec<(&Note, Rel)> = Vec::new(); + if let Some(p) = self.parent_of(cur) { + next.push((p, Rel::Parent)); + } + for c in self.children_of(cur) { + next.push((c, Rel::Child)); + } + for l in self.outlinks_of(cur) { + next.push((l, Rel::Link)); + } + for b in self.backlinks_of(cur) { + next.push((b, Rel::Backlink)); + } + for (n, rel) in next { + let nid = match n.id.as_deref() { + Some(x) => x, + None => continue, + }; + if seen.insert(nid) { + let r = first.unwrap_or(rel); + out.push((n, d + 1, r)); + queue.push_back((nid, d + 1, Some(r))); + } + } + } + out + } +} -- cgit v1.2.3-18-g5258