aboutsummaryrefslogtreecommitdiff
path: root/src/graph.rs
diff options
context:
space:
mode:
authorJSDurand <mmemmew@gmail.com>2026-11-19 09:29:47 +0800
committerJSDurand <mmemmew@gmail.com>2026-11-19 09:29:47 +0800
commit5b9a806af13d38163156302097e405a7b145b6cc (patch)
treec079f3c4e027dc730892630f667b0e6401736043 /src/graph.rs
elel: notes engine (Rust) and Gnus-like Emacs frontendHEADmaster
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 <noreply@anthropic.com>
Diffstat (limited to 'src/graph.rs')
-rw-r--r--src/graph.rs187
1 files changed, 187 insertions, 0 deletions
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<Note>,
+}
+
+#[derive(Default, Serialize, Deserialize)]
+pub struct Manifest {
+ pub files: BTreeMap<String, FileEntry>,
+}
+
+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<Note>,
+ by_id: HashMap<String, usize>,
+ children: HashMap<String, Vec<usize>>,
+ backlinks: HashMap<String, Vec<usize>>,
+ pub duplicates: Vec<(String, Vec<usize>)>,
+}
+
+impl Graph {
+ pub fn build(m: &Manifest) -> Graph {
+ let notes: Vec<Note> = m.files.values().flat_map(|f| f.notes.clone()).collect();
+ let mut by_id: HashMap<String, usize> = HashMap::new();
+ let mut seen: HashMap<String, Vec<usize>> = 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<usize>)> =
+ seen.into_iter().filter(|(_, v)| v.len() > 1).collect();
+ duplicates.sort();
+ let mut children: HashMap<String, Vec<usize>> = HashMap::new();
+ let mut backlinks: HashMap<String, Vec<usize>> = 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<usize>>) -> 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<Rel>)> = 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
+ }
+}