1use 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#[derive(Debug, Clone, PartialEq, Eq)]
14pub struct Planned {
15 pub path: Vec<u8>,
16 pub mode: u32,
18 pub oid: ObjectId,
19 pub mtime: gix_index::entry::stat::Time,
21 pub size: u64,
23}
24
25#[derive(Debug, Default)]
27pub struct Verified {
28 pub paths: Vec<Planned>,
30 pub racy: Vec<Planned>,
32 pub considered: usize,
34}
35
36#[derive(Debug, Default)]
38pub struct Plan {
39 pub directories: Vec<Vec<u8>>,
41 pub directories_created: Vec<Vec<u8>>,
45 pub files: Vec<Planned>,
47 pub materialised: Vec<Planned>,
49}
50
51pub fn colliding_paths(
67 target: &Listing,
68 source_paths: &[Vec<u8>],
69) -> (HashSet<Vec<u8>>, Vec<Vec<u8>>) {
70 let mut by_folded: HashMap<Vec<u8>, HashSet<Vec<u8>>> = HashMap::new();
75 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 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
116pub 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
161pub 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
235fn 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
265fn 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
284fn 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#[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
338pub 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 #[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}