tig_core/
history.rs

1//! commit history の walk。
2//!
3//! `git log --date-order` と同じ規則で返す: parent はその子がすべて出力されるまで
4//! 出力せず (topology 制約)、その制約の下で committer date の新しいものから順に
5//! 選ぶ。committer date が単調な履歴では単純な date 順と一致するが、clock skew の
6//! ある履歴や、ancestor を指す ref が別の tip と並ぶ場合は topology 制約が効く。
7//!
8//! 実装は git と同様に 2 段階を踏む。最初の取り出しで到達可能な commit を全て
9//! 辿って「未出力の子の数」を数え、以後は子を出し切った commit だけを date 順の
10//! heap から取り出す (Kahn の topological sort の date 優先版)。到達した parent が
11//! store に無い場合 (shallow な入力や bundle の prerequisite) は、そこを履歴の
12//! 境界として黙って打ち切る。
13
14use alloc::collections::{BTreeMap, BinaryHeap};
15use alloc::vec::Vec;
16
17use crate::Odb;
18use crate::err::{Error, Result};
19use crate::object::{self, Kind};
20use crate::oid::Oid;
21
22/// walk が返す commit。body は所有権ごと返す (parse は `commit()` で行う)。
23pub struct WalkedCommit {
24    pub oid: Oid,
25    pub raw: Vec<u8>,
26}
27
28impl WalkedCommit {
29    /// body を解析して構造化された commit を返す。
30    pub fn commit(&self) -> Result<object::Commit<'_>> {
31        object::parse_commit(&self.raw)
32    }
33}
34
35/// 到達可能集合に載った commit の walk 用情報。
36struct Node {
37    time: i64,
38    parents: Vec<Oid>,
39    /// まだ出力されていない子の数。0 になった commit だけが出力候補になる。
40    pending_children: u32,
41}
42
43pub struct Walk<'a, O: Odb> {
44    odb: &'a O,
45    tips: Vec<Oid>,
46    prepared: bool,
47    nodes: BTreeMap<Oid, Node>,
48    /// 出力候補 (pending_children == 0) の (committer date, oid) max-heap。
49    /// date 同点は oid で決定的にする (git のような投入順ではない)。
50    ready: BinaryHeap<(i64, Oid)>,
51}
52
53impl<'a, O: Odb> Walk<'a, O> {
54    pub fn new(odb: &'a O) -> Self {
55        Self {
56            odb,
57            tips: Vec::new(),
58            prepared: false,
59            nodes: BTreeMap::new(),
60            ready: BinaryHeap::new(),
61        }
62    }
63
64    /// 開始点を追加する。annotated tag は commit まで剥がす。
65    /// 対象が store に無い場合はエラー。最初の取り出しの後は追加できない。
66    pub fn push(&mut self, oid: Oid) -> Result<()> {
67        debug_assert!(!self.prepared, "push after iteration start");
68        let mut oid = oid;
69        // tag が tag を指す入れ子に備えて有限回で打ち切る。
70        for _ in 0..16 {
71            let (kind, body) = self.odb.read(&oid).ok_or(Error::MissingBase)?;
72            match kind {
73                Kind::Commit => {
74                    object::parse_commit(&body)?;
75                    self.tips.push(oid);
76                    return Ok(());
77                }
78                Kind::Tag => {
79                    oid = object::parse_tag(&body)?.object;
80                }
81                _ => return Err(Error::Corrupt("start point is not a commit")),
82            }
83        }
84        Err(Error::Corrupt("tag nesting too deep"))
85    }
86
87    /// 到達可能な commit を全て辿り、pending_children と初期の出力候補を確定する。
88    fn prepare(&mut self) -> Result<()> {
89        self.prepared = true;
90        let mut stack: Vec<Oid> = self.tips.clone();
91        while let Some(oid) = stack.pop() {
92            if self.nodes.contains_key(&oid) {
93                continue;
94            }
95            // 存在しない・commit でない parent は境界として集合に載せない。
96            let Some((Kind::Commit, body)) = self.odb.read(&oid) else {
97                continue;
98            };
99            let commit = object::parse_commit(&body)?;
100            let parents = unique(&commit.parents);
101            for &parent in &parents {
102                stack.push(parent);
103            }
104            self.nodes.insert(
105                oid,
106                Node {
107                    time: commit.committer.time,
108                    parents,
109                    pending_children: 0,
110                },
111            );
112        }
113
114        // 子の数を数える。nodes に載っている commit 同士の辺だけが対象。
115        let edges: Vec<Oid> = self
116            .nodes
117            .values()
118            .flat_map(|n| n.parents.iter().copied())
119            .collect();
120        for parent in edges {
121            if let Some(node) = self.nodes.get_mut(&parent) {
122                node.pending_children += 1;
123            }
124        }
125
126        for (oid, node) in &self.nodes {
127            if node.pending_children == 0 {
128                self.ready.push((node.time, *oid));
129            }
130        }
131        Ok(())
132    }
133}
134
135/// 出現順を保ったまま重複を除く (merge が同じ parent を重複して持つ場合に備える)。
136fn unique(oids: &[Oid]) -> Vec<Oid> {
137    let mut out: Vec<Oid> = Vec::with_capacity(oids.len());
138    for &oid in oids {
139        if !out.contains(&oid) {
140            out.push(oid);
141        }
142    }
143    out
144}
145
146impl<O: Odb> Iterator for Walk<'_, O> {
147    type Item = Result<WalkedCommit>;
148
149    fn next(&mut self) -> Option<Self::Item> {
150        if !self.prepared
151            && let Err(e) = self.prepare()
152        {
153            return Some(Err(e));
154        }
155
156        let (_, oid) = self.ready.pop()?;
157        let parents = match self.nodes.get(&oid) {
158            Some(node) => node.parents.clone(),
159            None => return Some(Err(Error::Corrupt("walked oid without node"))),
160        };
161        for parent in parents {
162            if let Some(node) = self.nodes.get_mut(&parent) {
163                node.pending_children -= 1;
164                if node.pending_children == 0 {
165                    self.ready.push((node.time, parent));
166                }
167            }
168        }
169
170        match self.odb.read(&oid) {
171            // prepare で読めた commit だけを nodes に載せているため、通常は到達しない。
172            None => Some(Err(Error::MissingBase)),
173            Some((Kind::Commit, raw)) => Some(Ok(WalkedCommit { oid, raw })),
174            Some(_) => Some(Err(Error::Corrupt("walked object is not a commit"))),
175        }
176    }
177}
178
179#[cfg(test)]
180mod tests {
181    use super::*;
182    use crate::object::Kind;
183    use alloc::vec;
184
185    /// テスト用の単純な in-memory store。
186    struct MemOdb(Vec<(Oid, Kind, Vec<u8>)>);
187
188    impl Odb for MemOdb {
189        fn read(&self, oid: &Oid) -> Option<(Kind, Vec<u8>)> {
190            self.0
191                .iter()
192                .find(|(o, _, _)| o == oid)
193                .map(|(_, k, b)| (*k, b.clone()))
194        }
195    }
196
197    fn commit(store: &mut MemOdb, parents: &[Oid], time: i64) -> Oid {
198        let mut body = Vec::new();
199        body.extend_from_slice(b"tree e69de29bb2d1d6434b8b29ae775ad8c2e48c5391\n");
200        for p in parents {
201            body.extend_from_slice(format!("parent {p}\n").as_bytes());
202        }
203        body.extend_from_slice(format!("author A <a@e> {time} +0000\n").as_bytes());
204        body.extend_from_slice(format!("committer A <a@e> {time} +0000\n").as_bytes());
205        body.extend_from_slice(b"\nmsg\n");
206        let oid = crate::object::compute_oid(Kind::Commit, &body);
207        store.0.push((oid, Kind::Commit, body));
208        oid
209    }
210
211    fn walk_oids<O: Odb>(odb: &O, tips: &[Oid]) -> Vec<Oid> {
212        let mut walk = Walk::new(odb);
213        for &tip in tips {
214            walk.push(tip).unwrap();
215        }
216        walk.map(|c| c.unwrap().oid).collect()
217    }
218
219    #[test]
220    fn linear_history_newest_first() {
221        let mut store = MemOdb(vec![]);
222        let c1 = commit(&mut store, &[], 100);
223        let c2 = commit(&mut store, &[c1], 200);
224        let c3 = commit(&mut store, &[c2], 300);
225        assert_eq!(walk_oids(&store, &[c3]), vec![c3, c2, c1]);
226    }
227
228    #[test]
229    fn merge_interleaved_by_date() {
230        let mut store = MemOdb(vec![]);
231        let base = commit(&mut store, &[], 100);
232        let a = commit(&mut store, &[base], 300);
233        let b = commit(&mut store, &[base], 200);
234        let m = commit(&mut store, &[a, b], 400);
235        assert_eq!(walk_oids(&store, &[m]), vec![m, a, b, base]);
236    }
237
238    #[test]
239    fn missing_parent_is_boundary() {
240        let mut store = MemOdb(vec![]);
241        let absent = commit(&mut store, &[], 50);
242        store.0.clear();
243        let c = commit(&mut store, &[absent], 100);
244        assert_eq!(walk_oids(&store, &[c]), vec![c]);
245    }
246
247    #[test]
248    fn duplicate_start_points_dedupe() {
249        let mut store = MemOdb(vec![]);
250        let c1 = commit(&mut store, &[], 100);
251        let c2 = commit(&mut store, &[c1], 200);
252        assert_eq!(walk_oids(&store, &[c2, c2, c1]), vec![c2, c1]);
253    }
254
255    // ancestor を指す tip の committer date が descendant の tip より新しくても、
256    // 子を出し切るまで parent を出力しない (--date-order の topology 制約)。
257    #[test]
258    fn ancestor_tip_with_newer_date_waits_for_child() {
259        let mut store = MemOdb(vec![]);
260        let p = commit(&mut store, &[], 2000);
261        let c = commit(&mut store, &[p], 1000);
262        assert_eq!(walk_oids(&store, &[c, p]), vec![c, p]);
263    }
264
265    // 分岐内の clock skew。P(1000) の子 C(500) と D(800)、merge M(1200) の walk は
266    // M, D, C, P の順になる (P は date では D より新しいが、C を出すまで待つ)。
267    #[test]
268    fn skewed_diamond_respects_topology() {
269        let mut store = MemOdb(vec![]);
270        let p = commit(&mut store, &[], 1000);
271        let c = commit(&mut store, &[p], 500);
272        let d = commit(&mut store, &[p], 800);
273        let m = commit(&mut store, &[c, d], 1200);
274        assert_eq!(walk_oids(&store, &[m]), vec![m, d, c, p]);
275    }
276
277    // 同じ parent を重複して持つ merge でも二重に数えず、walk が完走すること。
278    #[test]
279    fn duplicate_parents_counted_once() {
280        let mut store = MemOdb(vec![]);
281        let p = commit(&mut store, &[], 100);
282        let m = commit(&mut store, &[p, p], 200);
283        assert_eq!(walk_oids(&store, &[m]), vec![m, p]);
284    }
285}
tig_core/history.rs

tig_core/
history.rs
