Skip to main content

git_sprout/
plan.rs

1// ABOUTME: Turns two tree listings and the source index into the set of paths to clone.
2// ABOUTME: Nothing enters the plan that has not passed every check in `verify`.
3
4use std::collections::{BTreeMap, HashMap, HashSet};
5use std::path::{Path, PathBuf};
6
7use gix_hash::ObjectId;
8
9use crate::tree::{directory_of, Listing};
10use crate::verify::{self, Verdict};
11
12/// A path the plan intends to materialise by cloning.
13#[derive(Debug, Clone, PartialEq, Eq)]
14pub struct Planned {
15    pub path: Vec<u8>,
16    /// The mode from the tree. Never the mode the source file happens to carry.
17    pub mode: u32,
18    pub oid: ObjectId,
19    /// The source file's modification time, as the source index records it.
20    pub mtime: gix_index::entry::stat::Time,
21    /// The source file's size on disk, which for a symlink is the length of its target.
22    pub size: u64,
23}
24
25/// What the verification pass concluded about the target tree.
26#[derive(Debug, Default)]
27pub struct Verified {
28    /// Paths whose source file may stand in for a checkout.
29    pub paths: Vec<Planned>,
30    /// Paths whose stat data fell in the racily-clean window, for git to settle.
31    pub racy: Vec<Planned>,
32    /// How many blobs the target tree holds in total.
33    pub considered: usize,
34}
35
36/// The work to do, once the racy paths have been settled and directories chosen.
37#[derive(Debug, Default)]
38pub struct Plan {
39    /// Subtrees to clone in a single call, topmost only, in tree order.
40    pub directories: Vec<Vec<u8>>,
41    /// Every directory those clones put on disk, roots included. A clone copies the
42    /// source's permissions, so each of these needs the ones a checkout would have given
43    /// it.
44    pub directories_created: Vec<Vec<u8>>,
45    /// Paths to clone one at a time, because no chosen directory covers them.
46    pub files: Vec<Planned>,
47    /// Every path the plan materialises, including those inside a cloned directory.
48    pub materialised: Vec<Planned>,
49}
50
51/// The paths and subtrees a filesystem that folds case cannot keep apart.
52///
53/// Where two tracked paths differ only by case, only one file can exist, and real
54/// `git worktree add` settles which by checking every entry out in index order: the last
55/// one written unlinks and recreates the shared file, so it decides both the name on disk
56/// and the content, and the other path is reported modified. Cloning even one member wins
57/// a collision git would have lost, which spec §3.5.1 forbids, and inverts the dirty set.
58/// So a whole group goes to git, which settles it exactly as it always would.
59///
60/// The fold is ASCII, which is what git's own case-insensitive comparisons use. A
61/// filesystem that also folds beyond ASCII, as APFS does, can still collide on paths this
62/// leaves in the plan; the clone of the second one fails and demotes the run, which is
63/// slow rather than wrong.
64///
65/// On a case-sensitive filesystem this costs a handful of paths and changes nothing else.
66pub fn colliding_paths(
67    target: &Listing,
68    source_paths: &[Vec<u8>],
69) -> (HashSet<Vec<u8>>, Vec<Vec<u8>>) {
70    // Keyed on the folded name, holding the distinct spellings seen under it. A set
71    // rather than a list because the same path arrives from both the target tree and
72    // the source index, and counting one path twice would make every path in the
73    // repository look like a collision with itself.
74    let mut by_folded: HashMap<Vec<u8>, HashSet<Vec<u8>>> = HashMap::new();
75    // Folded over the source's paths as well as the target's, because the hazard lives
76    // in the source's filesystem rather than in either tree. Where two paths differ only
77    // by case the operating system keeps one file for both names, and the bytes behind
78    // the surviving name may belong to either member. A pair that exists at the source's
79    // HEAD but not in the target — a detached checkout, a tag, any commit where one
80    // member was added or removed — is invisible to the target alone, and the surviving
81    // path then looks like an ordinary clonable file whose content is somebody else's.
82    //
83    // Widening costs a handful of clones that would have been safe. The alternative
84    // costs a worktree that differs from git's.
85    let named = target
86        .blobs
87        .keys()
88        .chain(target.trees.keys())
89        .chain(target.gitlinks.iter())
90        .chain(source_paths.iter());
91    for path in named {
92        by_folded
93            .entry(path.to_ascii_lowercase())
94            .or_default()
95            .insert(path.clone());
96    }
97
98    let mut paths = HashSet::new();
99    let mut prefixes = Vec::new();
100    for (_, group) in by_folded.into_iter().filter(|(_, group)| group.len() > 1) {
101        for path in group {
102            // A source-only path is not in the plan to begin with; naming it here would
103            // be harmless but misleading. What matters is that its *target* twin is.
104            if target.trees.contains_key(&path) {
105                let mut prefix = path.clone();
106                prefix.push(b'/');
107                prefixes.push(prefix);
108            }
109            paths.insert(path);
110        }
111    }
112    prefixes.sort();
113    (paths, prefixes)
114}
115
116/// Applies every check that does not depend on git re-reading a file's content.
117pub fn verify_paths(
118    target: &Listing,
119    source_index: &gix_index::File,
120    source_root: &Path,
121    poisoned: &[Vec<u8>],
122    excluded: &HashSet<Vec<u8>>,
123) -> Verified {
124    let mut verified = Verified {
125        considered: target.blobs.len(),
126        ..Verified::default()
127    };
128    let timestamp = source_index.timestamp();
129
130    for (path, blob) in &target.blobs {
131        if excluded.contains(path) || verify::is_poisoned(path, poisoned) {
132            continue;
133        }
134        let Some(entry) = source_index.entry_by_path(path.as_slice().into()) else {
135            continue;
136        };
137        if !verify::entry_can_stand_in(blob, entry) {
138            continue;
139        }
140        let Ok(metadata) =
141            gix_index::fs::Metadata::from_path_no_follow(&source_root.join(as_path(path)))
142        else {
143            continue;
144        };
145        let planned = Planned {
146            path: path.clone(),
147            mode: blob.mode,
148            oid: blob.oid,
149            mtime: entry.stat.mtime,
150            size: metadata.len(),
151        };
152        match verify::stat_verdict(entry, &metadata, timestamp) {
153            Verdict::Clone => verified.paths.push(planned),
154            Verdict::AskGit => verified.racy.push(planned),
155            Verdict::Reject => {}
156        }
157    }
158    verified
159}
160
161/// Chooses the subtrees worth cloning in one call and splits the rest into single files.
162///
163/// A subtree qualifies only when both sides record the same tree oid, every blob under it
164/// is verified, and the source directory holds exactly the tracked entries and nothing
165/// else. That last condition is what keeps untracked and ignored files out of the new
166/// worktree: a directory clone copies whatever is on disk, so anything on disk that the
167/// tree does not name disqualifies the whole subtree.
168pub fn assemble(
169    target: &Listing,
170    source: &Listing,
171    source_root: &Path,
172    destination: &Path,
173    verified: Vec<Planned>,
174    clone_directories: bool,
175) -> Plan {
176    let mut plan = Plan {
177        materialised: verified,
178        ..Plan::default()
179    };
180    let verified_paths: HashSet<&[u8]> = plan
181        .materialised
182        .iter()
183        .map(|planned| planned.path.as_slice())
184        .collect();
185
186    if clone_directories {
187        let children = children_by_directory(target);
188        let mut covered: Vec<Vec<u8>> = Vec::new();
189        for (path, oid) in &target.trees {
190            if covered.iter().any(|prefix| path.starts_with(prefix)) {
191                continue;
192            }
193            if source.trees.get(path) != Some(oid) {
194                continue;
195            }
196            if !subtree_is_fully_verified(target, path, &verified_paths) {
197                continue;
198            }
199            if destination.join(as_path(path)).exists() {
200                continue;
201            }
202            if !source_holds_only(source_root, path, &children) {
203                continue;
204            }
205            let mut prefix = path.clone();
206            prefix.push(b'/');
207            plan.directories_created.push(path.clone());
208            plan.directories_created.extend(
209                target
210                    .trees
211                    .range(prefix.clone()..)
212                    .take_while(|(under, _)| under.starts_with(&prefix))
213                    .map(|(under, _)| under.clone()),
214            );
215            covered.push(prefix);
216            plan.directories.push(path.clone());
217        }
218        plan.files = plan
219            .materialised
220            .iter()
221            .filter(|planned| {
222                !covered
223                    .iter()
224                    .any(|prefix| planned.path.starts_with(prefix))
225            })
226            .cloned()
227            .collect();
228    } else {
229        plan.files = plan.materialised.clone();
230    }
231
232    plan
233}
234
235/// Every blob under `directory` is verified, there is at least one, and no submodule sits
236/// inside it.
237fn subtree_is_fully_verified(
238    target: &Listing,
239    directory: &[u8],
240    verified: &HashSet<&[u8]>,
241) -> bool {
242    let mut prefix = directory.to_vec();
243    prefix.push(b'/');
244    let mut blobs = 0usize;
245    for (path, _) in target.blobs.range(prefix.clone()..) {
246        if !path.starts_with(&prefix) {
247            break;
248        }
249        if !verified.contains(path.as_slice()) {
250            return false;
251        }
252        blobs += 1;
253    }
254    if blobs == 0 {
255        return false;
256    }
257    if let Some(path) = target.gitlinks.range(prefix.clone()..).next() {
258        if path.starts_with(&prefix) {
259            return false;
260        }
261    }
262    true
263}
264
265/// The immediate children of every directory in the tree, keyed by the directory path.
266fn children_by_directory(listing: &Listing) -> HashMap<Vec<u8>, HashSet<Vec<u8>>> {
267    let mut children: HashMap<Vec<u8>, HashSet<Vec<u8>>> = HashMap::new();
268    let paths = listing
269        .blobs
270        .keys()
271        .chain(listing.trees.keys())
272        .chain(listing.gitlinks.iter());
273    for path in paths {
274        let directory = directory_of(path);
275        let name = path[directory.len()..].to_vec();
276        children
277            .entry(directory.strip_suffix(b"/").unwrap_or(directory).to_vec())
278            .or_default()
279            .insert(name);
280    }
281    children
282}
283
284/// Whether the source directory holds exactly the tracked entries, at every depth.
285fn source_holds_only(
286    source_root: &Path,
287    directory: &[u8],
288    children: &HashMap<Vec<u8>, HashSet<Vec<u8>>>,
289) -> bool {
290    let Some(expected) = children.get(directory) else {
291        return false;
292    };
293    let Ok(entries) = std::fs::read_dir(source_root.join(as_path(directory))) else {
294        return false;
295    };
296    let mut seen: HashSet<Vec<u8>> = HashSet::new();
297    for entry in entries {
298        let Ok(entry) = entry else { return false };
299        seen.insert(file_name_bytes(&entry.file_name()));
300    }
301    if &seen != expected {
302        return false;
303    }
304    for name in expected {
305        let mut child = directory.to_vec();
306        child.push(b'/');
307        child.extend_from_slice(name);
308        if children.contains_key(&child) && !source_holds_only(source_root, &child, children) {
309            return false;
310        }
311    }
312    true
313}
314
315#[cfg(unix)]
316fn file_name_bytes(name: &std::ffi::OsStr) -> Vec<u8> {
317    use std::os::unix::ffi::OsStrExt;
318    name.as_bytes().to_vec()
319}
320
321#[cfg(not(unix))]
322fn file_name_bytes(name: &std::ffi::OsStr) -> Vec<u8> {
323    name.to_string_lossy().into_owned().into_bytes()
324}
325
326/// Turns a repository-relative git path into a filesystem path.
327#[cfg(unix)]
328pub fn as_path(path: &[u8]) -> PathBuf {
329    use std::os::unix::ffi::OsStrExt;
330    PathBuf::from(std::ffi::OsStr::from_bytes(path))
331}
332
333#[cfg(not(unix))]
334pub fn as_path(path: &[u8]) -> PathBuf {
335    PathBuf::from(String::from_utf8_lossy(path).into_owned())
336}
337
338/// The `.gitattributes` blobs the source index records, split into the ones its stat cache
339/// vouches for and the ones only git can settle by re-reading the file.
340pub fn source_attribute_files(
341    source_index: &gix_index::File,
342    source_root: &Path,
343) -> (BTreeMap<Vec<u8>, ObjectId>, Vec<Vec<u8>>) {
344    let mut files = BTreeMap::new();
345    let mut suspect = Vec::new();
346    let timestamp = source_index.timestamp();
347    for entry in source_index.entries() {
348        let path = entry.path(source_index).to_vec();
349        if !crate::tree::is_attributes_file(&path) {
350            continue;
351        }
352        let verdict =
353            gix_index::fs::Metadata::from_path_no_follow(&source_root.join(as_path(&path)))
354                .map(|metadata| verify::stat_verdict(entry, &metadata, timestamp))
355                .unwrap_or(Verdict::Reject);
356        files.insert(path.clone(), entry.id);
357        if verdict != Verdict::Clone {
358            suspect.push(path);
359        }
360    }
361    (files, suspect)
362}
363
364#[cfg(test)]
365mod tests {
366    use super::*;
367    use crate::tree::Blob;
368
369    fn oid(byte: u8) -> ObjectId {
370        ObjectId::from_hex(format!("{:02x}", byte).repeat(20).as_bytes()).unwrap()
371    }
372
373    fn listing(blobs: &[(&str, u8)], trees: &[(&str, u8)], gitlinks: &[&str]) -> Listing {
374        Listing {
375            blobs: blobs
376                .iter()
377                .map(|(path, byte)| {
378                    (
379                        path.as_bytes().to_vec(),
380                        Blob {
381                            mode: 0o100644,
382                            oid: oid(*byte),
383                        },
384                    )
385                })
386                .collect(),
387            trees: trees
388                .iter()
389                .map(|(path, byte)| (path.as_bytes().to_vec(), oid(*byte)))
390                .collect(),
391            gitlinks: gitlinks
392                .iter()
393                .map(|path| path.as_bytes().to_vec())
394                .collect(),
395        }
396    }
397
398    /// A pair that exists in the source but not in the target is still a collision:
399    /// the source's filesystem keeps one file for both names, so the survivor's bytes
400    /// may belong to either member. Regression for a divergence seen only under
401    /// `--detach` and a tag, where the target resolves to a commit the pair straddles.
402    #[test]
403    fn a_pair_only_the_source_has_still_disqualifies_the_target_twin() {
404        let listing = listing(&[("net/xt_mark.h", 0)], &[], &[]);
405        let (bare, _) = colliding_paths(&listing, &[]);
406        assert!(
407            bare.is_empty(),
408            "the target alone names no pair, so nothing collides"
409        );
410
411        let source = vec![b"net/xt_mark.h".to_vec(), b"net/XT_MARK.h".to_vec()];
412        let (widened, _) = colliding_paths(&listing, &source);
413        assert!(
414            widened.contains(b"net/xt_mark.h".as_slice()),
415            "the target's member of a pair the source holds must be dropped from the plan"
416        );
417    }
418
419    #[test]
420    fn maps_every_directory_to_its_own_children() {
421        let listing = listing(
422            &[("src/a.txt", 1), ("src/deep/b.txt", 2), ("top.txt", 3)],
423            &[("src", 4), ("src/deep", 5)],
424            &[],
425        );
426        let children = children_by_directory(&listing);
427        assert_eq!(
428            children[b"".as_slice()],
429            HashSet::from([b"src".to_vec(), b"top.txt".to_vec()])
430        );
431        assert_eq!(
432            children[b"src".as_slice()],
433            HashSet::from([b"a.txt".to_vec(), b"deep".to_vec()])
434        );
435    }
436
437    #[test]
438    fn a_subtree_needs_every_blob_verified() {
439        let listing = listing(&[("src/a.txt", 1), ("src/b.txt", 2)], &[("src", 4)], &[]);
440        let all = HashSet::from([b"src/a.txt".as_slice(), b"src/b.txt".as_slice()]);
441        assert!(subtree_is_fully_verified(&listing, b"src", &all));
442        let partial = HashSet::from([b"src/a.txt".as_slice()]);
443        assert!(!subtree_is_fully_verified(&listing, b"src", &partial));
444    }
445
446    #[test]
447    fn a_subtree_with_a_submodule_is_never_cloned_whole() {
448        let listing = listing(&[("src/a.txt", 1)], &[("src", 4)], &["src/vendor"]);
449        let all = HashSet::from([b"src/a.txt".as_slice()]);
450        assert!(!subtree_is_fully_verified(&listing, b"src", &all));
451    }
452
453    #[test]
454    fn an_empty_subtree_is_not_worth_cloning() {
455        let listing = listing(&[], &[("src", 4)], &[]);
456        assert!(!subtree_is_fully_verified(
457            &listing,
458            b"src",
459            &HashSet::new()
460        ));
461    }
462
463    #[test]
464    fn paths_that_differ_only_by_case_all_go_to_git() {
465        let listing = listing(
466            &[
467                ("net/xt_MARK.c", 1),
468                ("net/xt_mark.c", 2),
469                ("net/other.c", 3),
470            ],
471            &[("net", 4)],
472            &[],
473        );
474        let (paths, prefixes) = colliding_paths(&listing, &[]);
475        assert!(paths.contains(b"net/xt_MARK.c".as_slice()));
476        assert!(paths.contains(b"net/xt_mark.c".as_slice()));
477        assert!(!paths.contains(b"net/other.c".as_slice()));
478        assert!(prefixes.is_empty());
479    }
480
481    #[test]
482    fn directories_that_differ_only_by_case_take_their_subtrees_with_them() {
483        let listing = listing(
484            &[("Net/a.c", 1), ("net/b.c", 2)],
485            &[("Net", 3), ("net", 4)],
486            &[],
487        );
488        let (paths, prefixes) = colliding_paths(&listing, &[]);
489        assert!(paths.contains(b"Net".as_slice()));
490        assert_eq!(prefixes, vec![b"Net/".to_vec(), b"net/".to_vec()]);
491    }
492
493    #[test]
494    fn a_tree_and_a_blob_that_fold_together_both_go_to_git() {
495        let listing = listing(&[("Doc", 1), ("doc/a.c", 2)], &[("doc", 3)], &[]);
496        let (paths, prefixes) = colliding_paths(&listing, &[]);
497        assert!(paths.contains(b"Doc".as_slice()));
498        assert!(paths.contains(b"doc".as_slice()));
499        assert_eq!(prefixes, vec![b"doc/".to_vec()]);
500    }
501
502    #[test]
503    fn an_untracked_file_disqualifies_the_directory_clone() {
504        let scratch = std::env::temp_dir().join("git-sprout-plan-test");
505        let _ = std::fs::remove_dir_all(&scratch);
506        std::fs::create_dir_all(scratch.join("src")).unwrap();
507        std::fs::write(scratch.join("src/a.txt"), "a").unwrap();
508        let listing = listing(&[("src/a.txt", 1)], &[("src", 4)], &[]);
509        let children = children_by_directory(&listing);
510        assert!(source_holds_only(&scratch, b"src", &children));
511
512        std::fs::write(scratch.join("src/untracked.log"), "x").unwrap();
513        assert!(!source_holds_only(&scratch, b"src", &children));
514        let _ = std::fs::remove_dir_all(&scratch);
515    }
516}