rto_graph/
sync.rs

1//! The incremental, content-addressed sync engine.
2//!
3//! `sync` brings a [`Store`] into agreement with the repository's `HEAD` tree.
4//! Extraction is the expensive part and is content-addressed by blob id, so only
5//! blobs whose content changed are re-extracted; the rest load from the
6//! [`ObjectCache`]. If the tree id is unchanged since the last sync, it is a
7//! no-op. The graph itself is reassembled from the (cached) per-blob fact sets
8//! and rebuilt in a single transaction — a deliberately simple DB-write model
9//! for this stage; incremental DB updates can come later.
10
11use std::collections::{BTreeMap, BTreeSet};
12
13use crate::cache::{CacheError, ObjectCache};
14use crate::extract::Extractor;
15use crate::git::{GitError, Repo};
16use crate::store::StoreError;
17use crate::{Edge, EdgeKind, FactSet, NodeKind, Store};
18
19/// Errors raised while syncing.
20#[derive(Debug, thiserror::Error)]
21pub enum SyncError {
22    /// A store operation failed.
23    #[error(transparent)]
24    Store(#[from] StoreError),
25    /// A cache operation failed.
26    #[error(transparent)]
27    Cache(#[from] CacheError),
28    /// A git operation failed.
29    #[error(transparent)]
30    Git(#[from] GitError),
31}
32
33/// A summary of the work a [`sync`] performed.
34#[derive(Debug, Clone, Default, serde::Serialize)]
35pub struct SyncReport {
36    /// Hex id of the synced `HEAD` tree.
37    pub tree: String,
38    /// Whether the tree was unchanged and nothing was done.
39    pub no_op: bool,
40    /// Total blobs in the tree.
41    pub blobs_total: usize,
42    /// Blobs that were extracted (cache misses).
43    pub blobs_extracted: usize,
44    /// Blobs served from the cache (cache hits).
45    pub blobs_cached: usize,
46    /// Nodes in the store after syncing.
47    pub nodes: u64,
48    /// Edges in the store after syncing.
49    pub edges: u64,
50}
51
52/// Sync `store` to the repository's `HEAD` tree, extracting changed blobs with
53/// `extractor` and caching results in `cache`.
54///
55/// # Errors
56/// Returns a [`SyncError`] if git access, extraction caching, or the store
57/// rebuild fails.
58pub fn sync(
59    store: &mut Store,
60    repo: &Repo,
61    cache: &ObjectCache,
62    extractor: &dyn Extractor,
63) -> Result<SyncReport, SyncError> {
64    let tree = repo.head_tree_id()?;
65
66    if store.sync_state()?.as_deref() == Some(tree.as_str()) {
67        return Ok(SyncReport {
68            no_op: true,
69            nodes: store.node_count()?,
70            edges: store.edge_count()?,
71            tree,
72            ..SyncReport::default()
73        });
74    }
75
76    let blobs = repo.walk_blobs()?;
77    let mut assembled = FactSet::new();
78    let mut extracted = 0usize;
79    let mut cached = 0usize;
80
81    for blob in &blobs {
82        // Extraction is a pure function of (path, blob bytes), not blob id
83        // alone: node keys are path-scoped (e.g. `file:<path>`), so the same
84        // blob content at two different paths yields different facts. Key the
85        // cache by (path, oid) so duplicate-content files (e.g. empty files,
86        // which git dedupes to one oid) never collide, while the same path+oid
87        // in another branch/worktree still hits.
88        let key = cache_key(&blob.path, &blob.oid);
89        let facts = if let Some(facts) = cache.get(&key)? {
90            cached += 1;
91            facts
92        } else {
93            let bytes = repo.read_blob(&blob.oid)?;
94            let facts = extractor.extract(&blob.path, &blob.oid, &bytes);
95            cache.put(&key, &facts)?;
96            extracted += 1;
97            facts
98        };
99        let FactSet { nodes, edges } = facts;
100        assembled.nodes.extend(nodes);
101        assembled.edges.extend(edges);
102    }
103
104    resolve_calls(&mut assembled);
105    store.rebuild(&assembled, &tree)?;
106
107    Ok(SyncReport {
108        no_op: false,
109        blobs_total: blobs.len(),
110        blobs_extracted: extracted,
111        blobs_cached: cached,
112        nodes: store.node_count()?,
113        edges: store.edge_count()?,
114        tree,
115    })
116}
117
118/// Resolve the per-function call records (`meta.calls`) accumulated during
119/// extraction into `calls` edges, now that every file's symbols are present.
120///
121/// A callee simple-name is linked only when it resolves to **exactly one**
122/// function in the whole tree; ambiguous names (multiple `fn foo`) and unknown
123/// names (external/std calls) are left unresolved rather than guessed. This runs
124/// at assembly time — not per blob — because a single blob cannot see the
125/// definitions in other files.
126fn resolve_calls(facts: &mut FactSet) {
127    // Simple function name → the keys of functions with that name.
128    let mut by_name: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
129    for n in &facts.nodes {
130        if n.kind == NodeKind::Fn {
131            by_name
132                .entry(n.name.as_str())
133                .or_default()
134                .push(n.key.as_str());
135        }
136    }
137
138    // Collect (caller, callee) pairs; BTreeSet dedupes and orders them.
139    let mut resolved: BTreeSet<(String, String)> = BTreeSet::new();
140    for n in &facts.nodes {
141        if n.kind != NodeKind::Fn {
142            continue;
143        }
144        let Some(calls) = n.meta.get("calls").and_then(|v| v.as_array()) else {
145            continue;
146        };
147        for callee in calls.iter().filter_map(|v| v.as_str()) {
148            if let Some(targets) = by_name.get(callee)
149                && targets.len() == 1
150            {
151                resolved.insert((n.key.clone(), targets[0].to_owned()));
152            }
153        }
154    }
155
156    for (src, dst) in resolved {
157        facts.edges.push(Edge::derived(src, dst, EdgeKind::Calls));
158    }
159}
160
161/// Content-addressed cache key for a blob at a given path: the blob oid (kept
162/// as the leading, well-distributed shard) suffixed with a stable 64-bit hash
163/// of the path. Sharing across branches/worktrees is preserved (same path+oid →
164/// same key) while duplicate content at distinct paths stays distinct.
165fn cache_key(path: &str, oid: &str) -> String {
166    format!("{oid}-{:016x}", fnv1a64(path.as_bytes()))
167}
168
169/// FNV-1a (64-bit). Dependency-free and deterministic; used only to derive
170/// cache filenames, so it needs no cryptographic properties.
171fn fnv1a64(bytes: &[u8]) -> u64 {
172    let mut hash: u64 = 0xcbf2_9ce4_8422_2325;
173    for &b in bytes {
174        hash ^= u64::from(b);
175        hash = hash.wrapping_mul(0x0000_0100_0000_01b3);
176    }
177    hash
178}
179
180#[cfg(test)]
181mod tests {
182    use super::{cache_key, resolve_calls};
183    use crate::{EdgeKind, FactSet, Node, NodeKind};
184
185    fn fn_node(key: &str, name: &str, calls: &[&str]) -> Node {
186        let mut n = Node::new(key, NodeKind::Fn, name);
187        if !calls.is_empty() {
188            n.meta = serde_json::json!({ "calls": calls });
189        }
190        n
191    }
192
193    #[test]
194    fn resolve_calls_links_unique_names_only() {
195        let mut fs = FactSet::new()
196            .with_node(fn_node(
197                "sym:rust:a.rs#caller",
198                "caller",
199                &["target", "dup", "missing"],
200            ))
201            .with_node(fn_node("sym:rust:a.rs#target", "target", &[]))
202            // Two functions named `dup` → ambiguous, must not be linked.
203            .with_node(fn_node("sym:rust:a.rs#dup", "dup", &[]))
204            .with_node(fn_node("sym:rust:b.rs#dup", "dup", &[]));
205
206        resolve_calls(&mut fs);
207
208        let calls: Vec<_> = fs
209            .edges
210            .iter()
211            .filter(|e| e.kind == EdgeKind::Calls)
212            .collect();
213        assert_eq!(
214            calls.len(),
215            1,
216            "only the unambiguous, known callee is linked"
217        );
218        assert_eq!(calls[0].src, "sym:rust:a.rs#caller");
219        assert_eq!(calls[0].dst, "sym:rust:a.rs#target");
220    }
221
222    #[test]
223    fn cache_key_separates_paths_but_is_stable() {
224        let oid = "abc123";
225        // Same path + oid is stable across calls.
226        assert_eq!(cache_key("src/a.rs", oid), cache_key("src/a.rs", oid));
227        // Same blob content (oid) at two different paths must not collide.
228        assert_ne!(cache_key("src/a.rs", oid), cache_key("src/b.rs", oid));
229        // Different content at the same path differs too.
230        assert_ne!(cache_key("src/a.rs", "aaa"), cache_key("src/a.rs", "bbb"));
231        // Key stays sharded on the oid so the cache's 2-char shard is well spread.
232        assert!(cache_key("src/a.rs", oid).starts_with("abc123-"));
233    }
234}
rto_graph/sync.rs

rto_graph/
sync.rs
