grit_lib/
connectivity.rs

1//! Reachability checks for push / receive-pack connectivity verification.
2//!
3//! Approximates Git's `check_connected` / `rev-list --objects` walk for the cases
4//! exercised by the harness: full object closure from a tip, and "new objects only"
5//! when existing ref tips are treated as roots.
6
7use std::collections::{HashSet, VecDeque};
8
9use std::collections::HashMap;
10
11use crate::error::{Error, Result};
12use crate::objects::{parse_commit, parse_tag, parse_tree, Object, ObjectId, ObjectKind};
13use crate::refs;
14use crate::repo::Repository;
15
16/// Returns every commit reachable from all refs under `refs/` (not `HEAD` alone).
17///
18/// Git's connectivity check uses `--all` (refs), not `HEAD` resolution: a symbolic `HEAD`
19/// that points at `refs/heads/main` must not be treated as an extra root, or pushes that
20/// only advance `main` would be misclassified as already connected.
21fn commit_closure_from_all_refs(repo: &Repository) -> Result<HashSet<ObjectId>> {
22    let mut seeds = Vec::new();
23
24    for prefix in &[
25        "refs/heads/",
26        "refs/tags/",
27        "refs/remotes/",
28        "refs/bundles/",
29    ] {
30        if let Ok(entries) = refs::list_refs(&repo.git_dir, prefix) {
31            for (_, oid) in entries {
32                seeds.push(oid);
33            }
34        }
35    }
36
37    let mut seen = HashSet::new();
38    let mut queue: VecDeque<ObjectId> = VecDeque::new();
39
40    for oid in seeds {
41        let obj = match repo.odb.read(&oid) {
42            Ok(o) => o,
43            Err(_) => continue,
44        };
45        match obj.kind {
46            ObjectKind::Commit => {
47                if seen.insert(oid) {
48                    queue.push_back(oid);
49                }
50            }
51            ObjectKind::Tag => {
52                if let Some(target) = peel_tag_to_object(repo, &obj.data)? {
53                    if let Ok(tobj) = repo.odb.read(&target) {
54                        if tobj.kind == ObjectKind::Commit && seen.insert(target) {
55                            queue.push_back(target);
56                        }
57                    }
58                }
59            }
60            _ => {}
61        }
62    }
63
64    while let Some(c) = queue.pop_front() {
65        let obj = repo.odb.read(&c)?;
66        if obj.kind != ObjectKind::Commit {
67            continue;
68        }
69        let commit = parse_commit(&obj.data)?;
70        for p in commit.parents {
71            if seen.insert(p) {
72                queue.push_back(p);
73            }
74        }
75    }
76
77    Ok(seen)
78}
79
80/// Returns whether every bundle prerequisite commit is already reachable from existing refs.
81///
82/// Matches Git's `verify_bundle` connectivity check: prerequisite OIDs may exist loose in the ODB
83/// but must still lie in the commit closure of `refs/heads/`, `refs/tags/`, `refs/remotes/`, and
84/// `refs/bundles/` (so dangling objects do not satisfy prerequisites).
85pub fn bundle_prerequisites_connected_to_refs(
86    repo: &Repository,
87    prerequisites: &[ObjectId],
88) -> Result<bool> {
89    if prerequisites.is_empty() {
90        return Ok(true);
91    }
92    let closure = commit_closure_from_all_refs(repo)?;
93    Ok(prerequisites.iter().all(|p| closure.contains(p)))
94}
95
96fn peel_tag_to_object(repo: &Repository, tag_data: &[u8]) -> Result<Option<ObjectId>> {
97    let tag = parse_tag(tag_data)?;
98    let mut oid = tag.object;
99    loop {
100        let obj = repo.odb.read(&oid)?;
101        match obj.kind {
102            ObjectKind::Tag => {
103                let inner = parse_tag(&obj.data)?;
104                oid = inner.object;
105            }
106            _ => return Ok(Some(oid)),
107        }
108    }
109}
110
111fn tree_entry_is_tree(mode: u32) -> bool {
112    mode == 0o040000
113}
114
115fn tree_entry_is_blob(mode: u32) -> bool {
116    matches!(mode, 0o100644 | 0o100755 | 0o120000)
117}
118
119/// Walk commits starting from `roots`, optionally stopping parent traversal when a commit is in
120/// `parent_stop` (still enqueueing the edge from child: parent is treated as pre-existing).
121///
122/// Returns `Ok(false)` if any required object is missing from the ODB.
123fn walk_commit_graph_for_push(
124    repo: &Repository,
125    roots: &[ObjectId],
126    parent_stop: Option<&HashSet<ObjectId>>,
127) -> Result<bool> {
128    let mut seen_commits = HashSet::new();
129    let mut seen_trees = HashSet::new();
130    let mut seen_blobs = HashSet::new();
131    let mut commit_q: VecDeque<ObjectId> = VecDeque::new();
132    let mut tree_q: VecDeque<ObjectId> = VecDeque::new();
133
134    for &root in roots {
135        let tip_obj = match repo.odb.read(&root) {
136            Err(_) => return Ok(false),
137            Ok(o) => o,
138        };
139        if tip_obj.kind != ObjectKind::Commit {
140            return Err(Error::CorruptObject(format!(
141                "object {root} is not a commit"
142            )));
143        }
144        if seen_commits.insert(root) {
145            commit_q.push_back(root);
146        }
147    }
148
149    while let Some(c) = commit_q.pop_front() {
150        let obj = match repo.odb.read(&c) {
151            Err(_) => return Ok(false),
152            Ok(o) => o,
153        };
154        if obj.kind != ObjectKind::Commit {
155            return Err(Error::CorruptObject(format!("object {c} is not a commit")));
156        }
157        let commit = parse_commit(&obj.data)?;
158        for p in &commit.parents {
159            if parent_stop.is_some_and(|s| s.contains(p)) {
160                continue;
161            }
162            if seen_commits.insert(*p) {
163                commit_q.push_back(*p);
164            }
165        }
166        if seen_trees.insert(commit.tree) {
167            tree_q.push_back(commit.tree);
168        }
169    }
170
171    while let Some(t) = tree_q.pop_front() {
172        let obj = match repo.odb.read(&t) {
173            Err(_) => return Ok(false),
174            Ok(o) => o,
175        };
176        if obj.kind != ObjectKind::Tree {
177            return Err(Error::CorruptObject(format!("object {t} is not a tree")));
178        }
179        for entry in parse_tree(&obj.data)? {
180            if entry.mode == 0o160000 {
181                // Git submodule link: the pointed-to commit lives in another object store.
182            } else if tree_entry_is_tree(entry.mode) {
183                if seen_trees.insert(entry.oid) {
184                    tree_q.push_back(entry.oid);
185                }
186            } else if tree_entry_is_blob(entry.mode) {
187                if !seen_blobs.insert(entry.oid) {
188                    continue;
189                }
190                if repo.odb.read(&entry.oid).is_err() {
191                    return Ok(false);
192                }
193            }
194        }
195    }
196
197    Ok(true)
198}
199
200/// Verifies that every object reachable from `tip` exists in `repo.odb`.
201///
202/// # Errors
203///
204/// Returns [`Error::CorruptObject`] when `tip` is not a commit or tree data is invalid.
205pub fn push_tip_objects_exist(repo: &Repository, tip: ObjectId) -> Result<bool> {
206    walk_commit_graph_for_push(repo, &[tip], None)
207}
208
209/// Like [`push_tip_objects_exist`], but does not require parent commits listed in
210/// `parent_exceptions` to exist in the ODB (alternate `.have` semantics).
211pub fn push_tip_objects_exist_with_parent_exceptions(
212    repo: &Repository,
213    tip: ObjectId,
214    parent_exceptions: &HashSet<ObjectId>,
215) -> Result<bool> {
216    walk_commit_graph_for_push(repo, &[tip], Some(parent_exceptions))
217}
218
219fn read_object_for_push(
220    repo: &Repository,
221    pack_objects: Option<&HashMap<ObjectId, Object>>,
222    oid: &ObjectId,
223) -> Result<Object> {
224    if let Some(m) = pack_objects {
225        if let Some(o) = m.get(oid) {
226            return Ok(o.clone());
227        }
228    }
229    repo.odb.read(oid)
230}
231
232/// Objects reachable from `tip` that are not already reachable from existing refs (plus
233/// `extra_root_commits`) must exist in the ODB (or in `pack_objects` when verifying before
234/// unpacking a push pack).
235pub fn push_tip_connected_to_refs(
236    repo: &Repository,
237    tip: ObjectId,
238    extra_root_commits: &HashSet<ObjectId>,
239    pack_objects: Option<&HashMap<ObjectId, Object>>,
240) -> Result<bool> {
241    let mut existing = commit_closure_from_all_refs(repo)?;
242    existing.extend(extra_root_commits.iter().copied());
243
244    if existing.contains(&tip) {
245        return Ok(true);
246    }
247
248    let mut seen_commits = HashSet::new();
249    let mut seen_trees = HashSet::new();
250    let mut seen_blobs = HashSet::new();
251    let mut commit_q: VecDeque<ObjectId> = VecDeque::new();
252    let mut tree_q: VecDeque<ObjectId> = VecDeque::new();
253
254    seen_commits.insert(tip);
255    commit_q.push_back(tip);
256
257    while let Some(c) = commit_q.pop_front() {
258        let obj = match read_object_for_push(repo, pack_objects, &c) {
259            Err(_) => return Ok(false),
260            Ok(o) => o,
261        };
262        if obj.kind != ObjectKind::Commit {
263            return Err(Error::CorruptObject(format!("object {c} is not a commit")));
264        }
265        let commit = parse_commit(&obj.data)?;
266        for p in &commit.parents {
267            if existing.contains(p) {
268                continue;
269            }
270            if seen_commits.insert(*p) {
271                commit_q.push_back(*p);
272            }
273        }
274        if seen_trees.insert(commit.tree) {
275            tree_q.push_back(commit.tree);
276        }
277    }
278
279    while let Some(t) = tree_q.pop_front() {
280        let obj = match read_object_for_push(repo, pack_objects, &t) {
281            Err(_) => return Ok(false),
282            Ok(o) => o,
283        };
284        if obj.kind != ObjectKind::Tree {
285            return Err(Error::CorruptObject(format!("object {t} is not a tree")));
286        }
287        for entry in parse_tree(&obj.data)? {
288            if entry.mode == 0o160000 {
289                // Git submodule link: the pointed-to commit lives in another object store.
290            } else if tree_entry_is_tree(entry.mode) {
291                if seen_trees.insert(entry.oid) {
292                    tree_q.push_back(entry.oid);
293                }
294            } else if tree_entry_is_blob(entry.mode) {
295                if !seen_blobs.insert(entry.oid) {
296                    continue;
297                }
298                if read_object_for_push(repo, pack_objects, &entry.oid).is_err() {
299                    return Ok(false);
300                }
301            }
302        }
303    }
304
305    Ok(true)
306}
307
308/// If [`push_tip_connected_to_refs`] would fail, returns a missing object OID and a "context"
309/// commit OID for Git-compatible `Could not read` / `Failed to traverse parents` stderr.
310///
311/// `Ok(None)` means connected (same predicate as [`push_tip_connected_to_refs`] returning `Ok(true)`).
312pub fn diagnose_push_connectivity_failure(
313    repo: &Repository,
314    tip: ObjectId,
315    extra_root_commits: &HashSet<ObjectId>,
316    pack_objects: Option<&HashMap<ObjectId, Object>>,
317) -> Result<Option<(ObjectId, ObjectId)>> {
318    let mut existing = commit_closure_from_all_refs(repo)?;
319    existing.extend(extra_root_commits.iter().copied());
320
321    if existing.contains(&tip) {
322        return Ok(None);
323    }
324
325    let mut seen_commits = HashSet::new();
326    let mut seen_trees = HashSet::new();
327    let mut seen_blobs = HashSet::new();
328    let mut commit_q: VecDeque<ObjectId> = VecDeque::new();
329    let mut tree_q: VecDeque<ObjectId> = VecDeque::new();
330
331    seen_commits.insert(tip);
332    commit_q.push_back(tip);
333
334    while let Some(c) = commit_q.pop_front() {
335        let obj = match read_object_for_push(repo, pack_objects, &c) {
336            Err(_) => return Ok(Some((c, tip))),
337            Ok(o) => o,
338        };
339        if obj.kind != ObjectKind::Commit {
340            return Err(Error::CorruptObject(format!("object {c} is not a commit")));
341        }
342        let commit = parse_commit(&obj.data)?;
343        for p in &commit.parents {
344            if existing.contains(p) {
345                continue;
346            }
347            if read_object_for_push(repo, pack_objects, p).is_err() {
348                return Ok(Some((*p, c)));
349            }
350            if seen_commits.insert(*p) {
351                commit_q.push_back(*p);
352            }
353        }
354        if seen_trees.insert(commit.tree) {
355            tree_q.push_back(commit.tree);
356        }
357    }
358
359    while let Some(t) = tree_q.pop_front() {
360        let obj = match read_object_for_push(repo, pack_objects, &t) {
361            Err(_) => return Ok(Some((t, tip))),
362            Ok(o) => o,
363        };
364        if obj.kind != ObjectKind::Tree {
365            return Err(Error::CorruptObject(format!("object {t} is not a tree")));
366        }
367        for entry in parse_tree(&obj.data)? {
368            if entry.mode == 0o160000 {
369                continue;
370            } else if tree_entry_is_tree(entry.mode) {
371                if seen_trees.insert(entry.oid) {
372                    tree_q.push_back(entry.oid);
373                }
374            } else if tree_entry_is_blob(entry.mode) {
375                if !seen_blobs.insert(entry.oid) {
376                    continue;
377                }
378                if read_object_for_push(repo, pack_objects, &entry.oid).is_err() {
379                    return Ok(Some((entry.oid, tip)));
380                }
381            }
382        }
383    }
384
385    Ok(None)
386}
grit_lib/connectivity.rs

grit_lib/
connectivity.rs
