tig_core/
checkout.rs

1//! tree の展開 (checkout)。
2//!
3//! filesystem は持たず、tree を辿って path / 種別 / 内容を callback で渡す。
4//! ファイルへの書き出しや権限の設定は frontend (CLI 等) の責務とする。
5//! 再帰は使わず、明示的な stack で辿る。
6
7use alloc::vec::Vec;
8
9use crate::Odb;
10use crate::err::{Error, Result};
11use crate::object::{Kind, TreeIter};
12use crate::oid::Oid;
13
14/// entry の種別。git の mode から導出する。
15#[derive(Debug, Clone, Copy, PartialEq, Eq)]
16pub enum EntryKind {
17    File,
18    Executable,
19    /// content はリンク先の path。
20    Symlink,
21    /// submodule。content は指し先 commit の oid (20 byte 生値) で、blob は存在しない。
22    Gitlink,
23}
24
25/// `walk` の callback。引数は (path, 種別, 内容)。
26pub type Visit<'a> = dyn FnMut(&[u8], EntryKind, &[u8]) -> Result<()> + 'a;
27
28/// tree 直下から再帰的に entry を列挙し、`visit(path, kind, content)` を呼ぶ。
29/// path は '/' 区切り (先頭に '/' なし)。列挙順は tree の格納順 (名前順)。
30pub fn walk<O: Odb>(odb: &O, tree: Oid, visit: &mut Visit<'_>) -> Result<()> {
31    let root = read_tree(odb, &tree)?;
32    // (path prefix, tree body, body 内の現在位置)
33    let mut stack: Vec<(Vec<u8>, Vec<u8>, usize)> = alloc::vec![(Vec::new(), root, 0)];
34
35    loop {
36        // 現在の tree から次の entry を読み、必要な値を所有権ごと取り出してから
37        // stack を更新する (借用を跨がないため)。
38        let Some((prefix, body, pos)) = stack.last() else {
39            return Ok(());
40        };
41        let Some(entry) = TreeIter::new(&body[*pos..]).next() else {
42            stack.pop();
43            continue;
44        };
45        let entry = entry?;
46        // 細工された tree による path traversal を拒否する。'\0' は tree の
47        // 区切り文字のため name には現れない。
48        if entry.name.is_empty()
49            || entry.name == b"."
50            || entry.name == b".."
51            || entry.name.contains(&b'/')
52        {
53            return Err(Error::Corrupt("tree entry name"));
54        }
55        // entry の占有長: mode + SP + name + NUL + oid(20)。
56        let consumed = entry.mode.len() + 1 + entry.name.len() + 1 + 20;
57
58        let mut path = prefix.clone();
59        if !path.is_empty() {
60            path.push(b'/');
61        }
62        path.extend_from_slice(entry.name);
63        let (mode, oid) = (entry.mode.to_vec(), entry.oid);
64
65        let top = stack.last_mut().expect("stack is non-empty");
66        top.2 += consumed;
67
68        match mode.as_slice() {
69            b"40000" | b"040000" => {
70                if stack.len() >= 256 {
71                    return Err(Error::Corrupt("tree nesting too deep"));
72                }
73                let child = read_tree(odb, &oid)?;
74                stack.push((path, child, 0));
75            }
76            b"160000" => visit(&path, EntryKind::Gitlink, oid.as_bytes())?,
77            _ => {
78                let kind = match mode.as_slice() {
79                    b"100644" | b"100664" => EntryKind::File,
80                    b"100755" => EntryKind::Executable,
81                    b"120000" => EntryKind::Symlink,
82                    _ => return Err(Error::Corrupt("tree entry mode")),
83                };
84                let Some((Kind::Blob, content)) = odb.read(&oid) else {
85                    return Err(Error::MissingBase);
86                };
87                visit(&path, kind, &content)?;
88            }
89        }
90    }
91}
92
93fn read_tree<O: Odb>(odb: &O, oid: &Oid) -> Result<Vec<u8>> {
94    match odb.read(oid) {
95        Some((Kind::Tree, body)) => Ok(body),
96        Some(_) => Err(Error::Corrupt("not a tree")),
97        None => Err(Error::MissingBase),
98    }
99}
100
101#[cfg(test)]
102mod tests {
103    use super::*;
104    use crate::object::compute_oid;
105    use alloc::vec;
106
107    struct MemOdb(Vec<(Oid, Kind, Vec<u8>)>);
108
109    impl MemOdb {
110        fn put(&mut self, kind: Kind, body: Vec<u8>) -> Oid {
111            let oid = compute_oid(kind, &body);
112            self.0.push((oid, kind, body));
113            oid
114        }
115    }
116
117    impl Odb for MemOdb {
118        fn read(&self, oid: &Oid) -> Option<(Kind, Vec<u8>)> {
119            self.0
120                .iter()
121                .find(|(o, _, _)| o == oid)
122                .map(|(_, k, b)| (*k, b.clone()))
123        }
124    }
125
126    fn tree_body(entries: &[(&[u8], &[u8], Oid)]) -> Vec<u8> {
127        let mut body = Vec::new();
128        for (mode, name, oid) in entries {
129            body.extend_from_slice(mode);
130            body.push(b' ');
131            body.extend_from_slice(name);
132            body.push(0);
133            body.extend_from_slice(oid.as_bytes());
134        }
135        body
136    }
137
138    #[test]
139    fn walks_nested_trees_in_order() {
140        let mut odb = MemOdb(vec![]);
141        let blob_a = odb.put(Kind::Blob, b"A".to_vec());
142        let blob_b = odb.put(Kind::Blob, b"B".to_vec());
143        let sub = odb.put(Kind::Tree, tree_body(&[(b"100755", b"run.sh", blob_b)]));
144        let root = odb.put(
145            Kind::Tree,
146            tree_body(&[(b"100644", b"a.txt", blob_a), (b"40000", b"dir", sub)]),
147        );
148
149        let mut seen: Vec<(Vec<u8>, EntryKind, Vec<u8>)> = Vec::new();
150        walk(&odb, root, &mut |path, kind, content| {
151            seen.push((path.to_vec(), kind, content.to_vec()));
152            Ok(())
153        })
154        .unwrap();
155
156        assert_eq!(
157            seen,
158            vec![
159                (b"a.txt".to_vec(), EntryKind::File, b"A".to_vec()),
160                (b"dir/run.sh".to_vec(), EntryKind::Executable, b"B".to_vec()),
161            ]
162        );
163    }
164
165    // 細工された tree の traversal 系の name を拒否する。
166    #[test]
167    fn malicious_names_rejected() {
168        for name in [&b".."[..], b".", b"", b"a/b"] {
169            let mut odb = MemOdb(vec![]);
170            let blob = odb.put(Kind::Blob, b"x".to_vec());
171            let root = odb.put(Kind::Tree, tree_body(&[(b"100644", name, blob)]));
172            assert_eq!(
173                walk(&odb, root, &mut |_, _, _| Ok(())).unwrap_err(),
174                Error::Corrupt("tree entry name"),
175                "name={name:?}"
176            );
177        }
178    }
179
180    #[test]
181    fn missing_blob_is_error() {
182        let mut odb = MemOdb(vec![]);
183        let ghost = compute_oid(Kind::Blob, b"ghost");
184        let root = odb.put(Kind::Tree, tree_body(&[(b"100644", b"x", ghost)]));
185        assert_eq!(
186            walk(&odb, root, &mut |_, _, _| Ok(())).unwrap_err(),
187            Error::MissingBase
188        );
189    }
190}
tig_core/checkout.rs

tig_core/
checkout.rs
