1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
//! First-parent path history with conservative changed-path Bloom skipping.
use crate::{HistoryError, HistoryLimits, ObjectId, Objects, ReadLimits, TreeValue};
/// Failure to inspect first-parent history for a literal repository-relative path.
#[derive(Debug, thiserror::Error)]
#[non_exhaustive]
pub enum PathHistoryError {
/// The input is not a nonempty slash-separated relative path.
#[error("invalid history path")]
InvalidPath,
/// An explored history exceeds its bounds or contains a cycle.
#[error(transparent)]
History(#[from] HistoryError),
/// A fallback commit could not be read and parsed.
#[error(transparent)]
Commit(#[from] crate::ReadCommitError),
/// A tree on the selected path could not be read and parsed.
#[error(transparent)]
Tree(#[from] crate::ReadTreeError),
}
impl Objects {
/// Finds commits changing a literal path along the first-parent chain, newest first.
///
/// Compares entry identity and mode against the first parent, or an empty snapshot at a root
/// or declared shallow boundary. Includes additions and deletions. Directories compare their
/// subtree identities; pathspecs and rename following are not performed. An explicitly
/// attached graph can skip tree comparisons using Bloom negatives. Missing or uncertain
/// filters always require ordinary comparison. Uses default history and per-read bounds.
///
/// # Errors
///
/// Reports invalid paths, missing/corrupt commits or trees on the selected path, cycles and
/// exhausted bounds. Bloom-skipped trees and side-parent histories are not read or verified.
pub fn walk_path_first_parent(
&self,
root: ObjectId,
path: &[u8],
) -> Result<Vec<ObjectId>, PathHistoryError> {
self.walk_path_first_parent_with(root, path, HistoryLimits::default())
}
/// Finds first-parent path changes with explicit history and per-object read limits.
///
/// # Errors
///
/// Returns the same errors as [`Self::walk_path_first_parent`]. Commit bounds count visited
/// first-parent commits; parent bounds count followed first-parent edges. Each tree read uses
/// `limits.read`; memory includes returned IDs and the visited set, plus one decoded tree.
pub fn walk_path_first_parent_with(
&self,
root: ObjectId,
path: &[u8],
limits: HistoryLimits,
) -> Result<Vec<ObjectId>, PathHistoryError> {
if path.is_empty()
|| path
.split(|b| *b == b'/')
.any(|part| part.is_empty() || part == b"." || part == b".." || part.contains(&0))
{
return Err(PathHistoryError::InvalidPath);
}
let mut seen = crate::IdSet::default();
let mut remaining = limits.max_parents;
let mut next = Some(root);
let mut result = Vec::new();
while let Some(id) = next {
if seen.len() >= limits.max_commits {
return Err(HistoryError::Limit("commits").into());
}
if !seen.insert(id) {
return Err(HistoryError::Cycle.into());
}
let (tree, parent) = self.path_metadata(id, limits.read)?;
let parent = parent.filter(|_| !self.shallow_roots().contains(id));
if parent.is_some() {
remaining = remaining
.checked_sub(1)
.ok_or(HistoryError::Limit("parent occurrences"))?;
}
let negative = self
.commit_graph
.as_ref()
.and_then(|g| g.might_change_path(id, path))
== Some(false);
// A shallow boundary is compared with empty, not the indexed stored parent.
if !negative || self.shallow_roots().contains(id) {
let current = path_value(self, tree, path, limits.read)?;
let previous = if let Some(parent) = parent {
let (tree, _) = self.path_metadata(parent, limits.read)?;
path_value(self, tree, path, limits.read)?
} else {
None
};
if current != previous {
result.push(id);
}
}
next = parent;
}
Ok(result)
}
fn path_metadata(
&self,
id: ObjectId,
limits: ReadLimits,
) -> Result<(ObjectId, Option<ObjectId>), PathHistoryError> {
if let Some(record) = self.commit_graph.as_ref().and_then(|g| g.get(id)) {
return Ok((record.tree, record.parents.first().copied()));
}
let commit = self.read_commit_with(id, limits)?;
Ok((commit.tree(), commit.parents().first().copied()))
}
}
fn path_value(
objects: &Objects,
mut tree: ObjectId,
path: &[u8],
limits: ReadLimits,
) -> Result<Option<TreeValue>, PathHistoryError> {
let mut parts = path.split(|b| *b == b'/').peekable();
while let Some(part) = parts.next() {
let value = objects.read_tree_with(tree, limits)?;
let Some(entry) = value.entries().iter().find(|entry| entry.name == part) else {
return Ok(None);
};
if parts.peek().is_none() {
return Ok(Some(TreeValue {
id: entry.id,
mode: entry.mode,
}));
}
if entry.mode != crate::EntryMode::Tree {
return Ok(None);
}
tree = entry.id;
}
Ok(None)
}