grit_lib/
write_tree.rs

1//! Build tree objects from index entries (`git write-tree` core logic).
2
3use std::collections::BTreeMap;
4
5use crate::error::Result;
6use crate::index::{
7    Index, IndexEntry, MODE_EXECUTABLE, MODE_GITLINK, MODE_REGULAR, MODE_SYMLINK, MODE_TREE,
8};
9use crate::objects::{serialize_tree, tree_entry_cmp, ObjectId, ObjectKind, TreeEntry};
10use crate::odb::Odb;
11
12/// Build and write tree object(s) from index entries and return the tree OID.
13///
14/// The `prefix` argument optionally limits the write to a subtree path.
15pub fn write_tree_from_index(odb: &Odb, index: &Index, prefix: &str) -> Result<ObjectId> {
16    // Ensure implicit empty blobs used by intent-to-add entries exist.
17    // These entries are skipped from tree construction below, but callers
18    // like commit/write-tree may still validate object presence and expect
19    // canonical empty-blob availability.
20    let _ = odb.write(ObjectKind::Blob, b"");
21
22    let prefix_bytes = prefix.as_bytes();
23    let mut entries: Vec<&IndexEntry> = index
24        .entries
25        .iter()
26        .filter(|entry| {
27            entry.stage() == 0 && !entry.intent_to_add() && entry.path.starts_with(prefix_bytes)
28        })
29        .collect();
30    entries.sort_by(|a, b| a.path.cmp(&b.path).then_with(|| a.stage().cmp(&b.stage())));
31    build_tree(odb, &entries, prefix_bytes)
32}
33
34fn build_tree(odb: &Odb, entries: &[&IndexEntry], dir_prefix: &[u8]) -> Result<ObjectId> {
35    let mut children: BTreeMap<Vec<u8>, ChildKind> = BTreeMap::new();
36
37    for entry in entries {
38        let path = &entry.path;
39        let rel = if dir_prefix.is_empty() {
40            path.as_slice()
41        } else {
42            path.strip_prefix(dir_prefix)
43                .and_then(|suffix| suffix.strip_prefix(b"/"))
44                .unwrap_or(path.as_slice())
45        };
46
47        if let Some(slash_pos) = rel.iter().position(|&byte| byte == b'/') {
48            let child_name = rel[..slash_pos].to_vec();
49            let sub_prefix = if dir_prefix.is_empty() {
50                child_name.clone()
51            } else {
52                let mut sub_prefix = dir_prefix.to_vec();
53                sub_prefix.push(b'/');
54                sub_prefix.extend_from_slice(&child_name);
55                sub_prefix
56            };
57            children
58                .entry(child_name)
59                .or_insert_with(|| ChildKind::Tree(sub_prefix, Vec::new()))
60                .push_entry(entry);
61        } else {
62            children
63                .entry(rel.to_vec())
64                .or_insert_with(|| ChildKind::Blob {
65                    mode: canonicalize_blob_mode(entry.mode),
66                    oid: entry.oid,
67                });
68        }
69    }
70
71    let mut tree_entries = Vec::with_capacity(children.len());
72    for (name, child) in children {
73        match child {
74            ChildKind::Blob { mode, oid } => tree_entries.push(TreeEntry { mode, name, oid }),
75            ChildKind::Tree(sub_prefix, sub_entries) => {
76                let sub_oid = build_tree(odb, &sub_entries, &sub_prefix)?;
77                tree_entries.push(TreeEntry {
78                    mode: MODE_TREE,
79                    name,
80                    oid: sub_oid,
81                });
82            }
83        }
84    }
85
86    tree_entries.sort_by(|a, b| {
87        let a_tree = a.mode == MODE_TREE;
88        let b_tree = b.mode == MODE_TREE;
89        tree_entry_cmp(&a.name, a_tree, &b.name, b_tree)
90    });
91
92    let data = serialize_tree(&tree_entries);
93    odb.write(ObjectKind::Tree, &data)
94}
95
96fn canonicalize_blob_mode(mode: u32) -> u32 {
97    match mode & 0o170000 {
98        0o120000 => MODE_SYMLINK,
99        0o160000 => MODE_GITLINK,
100        0o100000 => {
101            if mode & 0o111 != 0 {
102                MODE_EXECUTABLE
103            } else {
104                MODE_REGULAR
105            }
106        }
107        _ => MODE_REGULAR,
108    }
109}
110
111enum ChildKind<'a> {
112    Blob { mode: u32, oid: ObjectId },
113    Tree(Vec<u8>, Vec<&'a IndexEntry>),
114}
115
116impl<'a> ChildKind<'a> {
117    fn push_entry(&mut self, entry: &'a IndexEntry) {
118        if let Self::Tree(_, entries) = self {
119            entries.push(entry);
120        }
121    }
122}
123
124#[cfg(test)]
125mod tests {
126    #![allow(clippy::expect_used, clippy::unwrap_used)]
127
128    use super::*;
129    use crate::index::{IndexEntry, MODE_EXECUTABLE, MODE_REGULAR, MODE_SYMLINK, MODE_TREE};
130    use crate::objects::parse_tree;
131    use tempfile::TempDir;
132
133    fn entry(path: &str, mode: u32, oid: ObjectId) -> IndexEntry {
134        IndexEntry {
135            ctime_sec: 0,
136            ctime_nsec: 0,
137            mtime_sec: 0,
138            mtime_nsec: 0,
139            dev: 0,
140            ino: 0,
141            mode,
142            uid: 0,
143            gid: 0,
144            size: 0,
145            oid,
146            flags: path.len().min(0xFFF) as u16,
147            flags_extended: None,
148            path: path.as_bytes().to_vec(),
149        }
150    }
151
152    #[test]
153    fn writes_sorted_tree_with_canonical_modes() {
154        let temp_dir = TempDir::new().unwrap();
155        let odb = Odb::new(temp_dir.path());
156
157        let oid_a = odb.write(ObjectKind::Blob, b"a").unwrap();
158        let oid_exec = odb.write(ObjectKind::Blob, b"exec").unwrap();
159        let oid_link = odb.write(ObjectKind::Blob, b"target").unwrap();
160
161        let mut index = Index::new();
162        index.add_or_replace(entry("bin/run.sh", 0o100777, oid_exec));
163        index.add_or_replace(entry("link", 0o120777, oid_link));
164        index.add_or_replace(entry("a.txt", 0o100664, oid_a));
165
166        let root_oid = write_tree_from_index(&odb, &index, "").unwrap();
167        let root_tree_obj = odb.read(&root_oid).unwrap();
168        let root_entries = parse_tree(&root_tree_obj.data).unwrap();
169
170        assert_eq!(root_entries.len(), 3);
171        assert_eq!(root_entries[0].name, b"a.txt");
172        assert_eq!(root_entries[0].mode, MODE_REGULAR);
173        assert_eq!(root_entries[1].name, b"bin");
174        assert_eq!(root_entries[1].mode, MODE_TREE);
175        assert_eq!(root_entries[2].name, b"link");
176        assert_eq!(root_entries[2].mode, MODE_SYMLINK);
177
178        let bin_tree_obj = odb.read(&root_entries[1].oid).unwrap();
179        let bin_entries = parse_tree(&bin_tree_obj.data).unwrap();
180        assert_eq!(bin_entries.len(), 1);
181        assert_eq!(bin_entries[0].name, b"run.sh");
182        assert_eq!(bin_entries[0].mode, MODE_EXECUTABLE);
183    }
184}
grit_lib/write_tree.rs

grit_lib/
write_tree.rs
