weavatrix_git/commit_graph/
mod.rs

1mod bloom;
2mod format;
3
4use std::{fs, path::Path};
5
6use crate::{GitError, HashKind, HistoryOptions, ObjectId, Result, error::invalid};
7use format::Layer;
8
9#[derive(Clone, Copy, Debug, PartialEq, Eq)]
10pub enum PathBloom {
11    DefinitelyNot,
12    Maybe,
13}
14
15pub(crate) struct CommitGraph {
16    hash: HashKind,
17    layers: Vec<Layer>,
18}
19
20pub(crate) struct GraphCommit {
21    pub(crate) id: ObjectId,
22    pub(crate) tree: ObjectId,
23    pub(crate) parents: Vec<ObjectId>,
24    pub(crate) time: i64,
25}
26
27impl CommitGraph {
28    pub(crate) fn open(common_dir: &Path, hash: HashKind) -> Result<Option<Self>> {
29        let info = common_dir.join("objects").join("info");
30        let monolithic = info.join("commit-graph");
31        if monolithic.is_file() {
32            let Some(layer) = Layer::open(&monolithic, hash, 0, &[], None)? else {
33                return Ok(None);
34            };
35            return Ok(Some(Self {
36                hash,
37                layers: vec![layer],
38            }));
39        }
40        let directory = info.join("commit-graphs");
41        let chain = match fs::read_to_string(directory.join("commit-graph-chain")) {
42            Ok(chain) => chain,
43            Err(error) if error.kind() == std::io::ErrorKind::NotFound => return Ok(None),
44            Err(error) => return Err(error.into()),
45        };
46        let ids = chain
47            .lines()
48            .filter(|line| !line.is_empty())
49            .map(|line| ObjectId::from_hex_for(line, hash))
50            .collect::<Result<Vec<_>>>()?;
51        if ids.is_empty() || ids.len() > 64 {
52            return Err(invalid("commit-graph chain length is invalid"));
53        }
54        let mut layers = Vec::with_capacity(ids.len());
55        let mut base_count = 0;
56        for (index, id) in ids.iter().enumerate() {
57            let path = directory.join(format!("graph-{}.graph", id.to_hex()));
58            let layer = Layer::open(&path, hash, base_count, &ids[..index], Some(*id))?
59                .ok_or_else(|| invalid("commit-graph chain hash kind mismatch"))?;
60            base_count = base_count
61                .checked_add(layer.count())
62                .ok_or_else(|| invalid("commit-graph chain count overflow"))?;
63            layers.push(layer);
64        }
65        Ok(Some(Self { hash, layers }))
66    }
67
68    pub(crate) fn find(&self, id: ObjectId) -> Result<Option<GraphCommit>> {
69        if id.kind() != self.hash {
70            return Ok(None);
71        }
72        for (layer_index, layer) in self.layers.iter().enumerate().rev() {
73            if let Some(position) = layer.find_position(id)? {
74                return self.entry(layer_index, position).map(Some);
75            }
76        }
77        Ok(None)
78    }
79
80    pub(crate) fn first_parent_ids(
81        &self,
82        start: ObjectId,
83        options: HistoryOptions,
84        traversal_limit: usize,
85    ) -> Result<Option<Vec<ObjectId>>> {
86        let Some(mut position) = self.global_position(start)? else {
87            return Ok(None);
88        };
89        let mut result = Vec::with_capacity(options.max_commits.min(1024));
90        let mut traversed = 0;
91        loop {
92            if result.len() == options.max_commits {
93                break;
94            }
95            if traversed == traversal_limit {
96                return Err(GitError::LimitExceeded {
97                    resource: "history traversal",
98                    limit: traversal_limit,
99                });
100            }
101            traversed += 1;
102            let (layer, local) = self.layer_at_global(position)?;
103            let raw = layer.raw_commit(local)?;
104            if options.since.is_none_or(|time| raw.time >= time)
105                && options.until.is_none_or(|time| raw.time <= time)
106            {
107                result.push(layer.id(local)?);
108            }
109            let Some(parent) = raw.parents.first() else {
110                break;
111            };
112            position = *parent;
113        }
114        Ok(Some(result))
115    }
116
117    pub(crate) const fn layer_count(&self) -> usize {
118        self.layers.len()
119    }
120
121    pub(crate) fn changed_path(&self, id: ObjectId, path: &[u8]) -> Result<Option<PathBloom>> {
122        if path.is_empty() || path.contains(&0) {
123            return Err(invalid("Bloom query path is empty or contains NUL"));
124        }
125        for layer in self.layers.iter().rev() {
126            if let Some(position) = layer.find_position(id)? {
127                return layer.changed_path(position, path);
128            }
129        }
130        Ok(None)
131    }
132
133    fn entry(&self, layer_index: usize, position: usize) -> Result<GraphCommit> {
134        let layer = &self.layers[layer_index];
135        let raw = layer.raw_commit(position)?;
136        let parents = raw
137            .parents
138            .into_iter()
139            .map(|position| self.id_at_global(position))
140            .collect::<Result<Vec<_>>>()?;
141        Ok(GraphCommit {
142            id: layer.id(position)?,
143            tree: raw.tree,
144            parents,
145            time: raw.time,
146        })
147    }
148
149    fn id_at_global(&self, position: usize) -> Result<ObjectId> {
150        let (layer, local) = self.layer_at_global(position)?;
151        layer.id(local)
152    }
153
154    fn global_position(&self, id: ObjectId) -> Result<Option<usize>> {
155        if id.kind() != self.hash {
156            return Ok(None);
157        }
158        for layer in self.layers.iter().rev() {
159            if let Some(position) = layer.find_position(id)? {
160                return Ok(Some(layer.base_count() + position));
161            }
162        }
163        Ok(None)
164    }
165
166    fn layer_at_global(&self, position: usize) -> Result<(&Layer, usize)> {
167        let layer = self
168            .layers
169            .iter()
170            .find(|layer| {
171                position >= layer.base_count()
172                    && position < layer.base_count().saturating_add(layer.count())
173            })
174            .ok_or_else(|| invalid("commit-graph parent is out of chain bounds"))?;
175        Ok((layer, position - layer.base_count()))
176    }
177}
weavatrix_git/commit_graph/mod.rs

weavatrix_git/commit_graph/
mod.rs
