1use crate::diff::zero_oid;
8use crate::error::Result;
9use crate::objects::{parse_commit, parse_tree, tree_name_cmp, ObjectId, ObjectKind, TreeEntry};
10use crate::odb::Odb;
11
12#[must_use]
14pub fn combined_parent_status_char(s: CombinedParentStatus) -> char {
15 match s {
16 CombinedParentStatus::Added => 'A',
17 CombinedParentStatus::Modified => 'M',
18 CombinedParentStatus::Deleted => 'D',
19 CombinedParentStatus::Renamed => 'R',
20 }
21}
22
23#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
25#[non_exhaustive]
26pub struct CombinedRawLineFormatOptions {
27 pub combined_all_paths: bool,
29 pub quote_fully: bool,
31}
32
33#[must_use]
39pub fn format_combined_raw_line_all_paths(
40 p: &CombinedDiffPath,
41 abbrev_len: Option<usize>,
42 combined_all_paths: bool,
43 quote_fully: bool,
44) -> String {
45 format_combined_raw_line_all_paths_with_options(
46 p,
47 abbrev_len,
48 &CombinedRawLineFormatOptions {
49 combined_all_paths,
50 quote_fully,
51 },
52 )
53}
54
55#[must_use]
57pub fn format_combined_raw_line_all_paths_with_options(
58 p: &CombinedDiffPath,
59 abbrev_len: Option<usize>,
60 options: &CombinedRawLineFormatOptions,
61) -> String {
62 if !options.combined_all_paths {
63 return format_combined_raw_line(p, abbrev_len);
64 }
65 let quote_fully = options.quote_fully;
66 let mut line = combined_raw_meta(p, abbrev_len);
69 for side in &p.parents {
70 let name = side.rename_from.as_deref().unwrap_or(&p.path);
71 line.push('\t');
72 line.push_str(&crate::quote_path::quote_c_style(name, quote_fully));
73 }
74 line.push('\t');
75 line.push_str(&crate::quote_path::quote_c_style(&p.path, quote_fully));
76 line
77}
78
79impl CombinedRawLineFormatOptions {
80 #[must_use]
82 pub fn with_combined_all_paths(mut self, combined_all_paths: bool) -> Self {
83 self.combined_all_paths = combined_all_paths;
84 self
85 }
86
87 #[must_use]
89 pub fn with_quote_fully(mut self, quote_fully: bool) -> Self {
90 self.quote_fully = quote_fully;
91 self
92 }
93}
94
95#[must_use]
97pub fn format_combined_raw_line(p: &CombinedDiffPath, abbrev_len: Option<usize>) -> String {
98 format!("{}\t{}", combined_raw_meta(p, abbrev_len), p.path)
99}
100
101#[must_use]
103pub fn combined_raw_meta(p: &CombinedDiffPath, abbrev_len: Option<usize>) -> String {
104 let n = p.parents.len();
105 let mut colons = String::with_capacity(n);
106 for _ in 0..n {
107 colons.push(':');
108 }
109 let mut modes = String::new();
110 for side in &p.parents {
111 modes.push_str(&format!("{:06o} ", side.mode));
112 }
113 modes.push_str(&format!("{:06o}", p.merge_mode));
114 let mut oids = String::new();
115 for side in &p.parents {
116 let h = format!("{}", side.oid);
117 let disp = if let Some(len) = abbrev_len {
118 &h[..len.min(h.len())]
119 } else {
120 h.as_str()
121 };
122 oids.push(' ');
123 oids.push_str(disp);
124 }
125 let rh = format!("{}", p.merge_oid);
126 let rdisp = if let Some(len) = abbrev_len {
127 &rh[..len.min(rh.len())]
128 } else {
129 rh.as_str()
130 };
131 oids.push(' ');
132 oids.push_str(rdisp);
133 oids.push(' ');
134 let status: String = p
135 .parents
136 .iter()
137 .map(|s| combined_parent_status_char(s.status))
138 .collect();
139 format!("{colons}{modes}{oids}{status}")
140}
141
142#[derive(Debug, Clone, Copy, PartialEq, Eq)]
144pub enum CombinedParentStatus {
145 Added,
147 Modified,
149 Deleted,
151 Renamed,
154}
155
156#[derive(Debug, Clone)]
158pub struct CombinedDiffPath {
159 pub path: String,
161 pub merge_mode: u32,
163 pub merge_oid: ObjectId,
165 pub parents: Vec<CombinedParentSide>,
167}
168
169#[derive(Debug, Clone)]
171pub struct CombinedParentSide {
172 pub mode: u32,
174 pub oid: ObjectId,
176 pub status: CombinedParentStatus,
178 pub rename_from: Option<String>,
180}
181
182#[derive(Debug, Clone, Default)]
184pub struct CombinedTreeDiffOptions {
185 pub recursive: bool,
187 pub tree_in_recursive: bool,
189}
190
191fn is_tree_mode(mode: u32) -> bool {
192 (mode & 0o170000) == 0o040000
193}
194
195fn read_tree_entries(odb: &Odb, oid: Option<&ObjectId>) -> Result<Vec<TreeEntry>> {
196 let Some(oid) = oid else {
197 return Ok(Vec::new());
198 };
199 let obj = odb.read(oid)?;
200 if obj.kind != ObjectKind::Tree {
201 return Ok(Vec::new());
202 }
203 parse_tree(&obj.data)
204}
205
206fn tree_entry_pathcmp(a: Option<&TreeEntry>, b: Option<&TreeEntry>) -> std::cmp::Ordering {
207 match (a, b) {
208 (None, None) => std::cmp::Ordering::Equal,
209 (None, Some(_)) => std::cmp::Ordering::Greater,
210 (Some(_), None) => std::cmp::Ordering::Less,
211 (Some(e1), Some(e2)) => tree_name_cmp(
212 &e1.name,
213 is_tree_mode(e1.mode),
214 &e2.name,
215 is_tree_mode(e2.mode),
216 ),
217 }
218}
219
220fn combined_matches_find_object(path: &CombinedDiffPath, find: Option<&ObjectId>) -> bool {
221 let Some(target) = find else {
222 return true;
223 };
224 if path.merge_oid == *target {
225 return true;
226 }
227 path.parents.iter().any(|p| p.oid == *target)
228}
229
230fn emit_combined_path(
231 path: String,
232 merge_entry: Option<&TreeEntry>,
233 tp: &[Vec<TreeEntry>],
234 tp_idx: &[usize],
235 parent_neq: &[bool],
236 find_object: Option<&ObjectId>,
237 out: &mut Vec<CombinedDiffPath>,
238) {
239 let nparent = tp.len();
240 let mut parents = Vec::with_capacity(nparent);
241
242 if let Some(te) = merge_entry {
243 for i in 0..nparent {
244 let tpi_valid = !parent_neq[i];
245 let (mode_i, oid_i, status) = if tpi_valid {
246 let e = &tp[i][tp_idx[i]];
247 (e.mode, e.oid, CombinedParentStatus::Modified)
248 } else {
249 (0u32, zero_oid(), CombinedParentStatus::Added)
250 };
251 parents.push(CombinedParentSide {
252 mode: mode_i,
253 oid: oid_i,
254 status,
255 rename_from: None,
256 });
257 }
258 let p = CombinedDiffPath {
259 path,
260 merge_mode: te.mode,
261 merge_oid: te.oid,
262 parents,
263 };
264 if combined_matches_find_object(&p, find_object) {
265 out.push(p);
266 }
267 } else {
268 for i in 0..nparent {
269 let tpi_valid = !parent_neq[i];
270 let (mode_i, oid_i, status) = if tpi_valid {
271 let e = &tp[i][tp_idx[i]];
272 (e.mode, e.oid, CombinedParentStatus::Deleted)
273 } else {
274 (0u32, zero_oid(), CombinedParentStatus::Added)
275 };
276 parents.push(CombinedParentSide {
277 mode: mode_i,
278 oid: oid_i,
279 status,
280 rename_from: None,
281 });
282 }
283 let p = CombinedDiffPath {
284 path,
285 merge_mode: 0,
286 merge_oid: zero_oid(),
287 parents,
288 };
289 if combined_matches_find_object(&p, find_object) {
290 out.push(p);
291 }
292 }
293}
294
295fn should_recurse_dir(_path: &str, _opt: &CombinedTreeDiffOptions) -> bool {
296 true
299}
300
301fn ll_diff_tree_paths(
302 odb: &Odb,
303 out: &mut Vec<CombinedDiffPath>,
304 base_path: &str,
305 opt: &CombinedTreeDiffOptions,
306 merge_oid: Option<&ObjectId>,
307 parents_oid: &[Option<ObjectId>],
308 find_object: Option<&ObjectId>,
309) -> Result<()> {
310 let nparent = parents_oid.len();
311 let t_entries = read_tree_entries(odb, merge_oid)?;
312 let mut tp_entries: Vec<Vec<TreeEntry>> = Vec::with_capacity(nparent);
313 for po in parents_oid {
314 tp_entries.push(read_tree_entries(odb, po.as_ref())?);
315 }
316
317 let mut ti = 0usize;
318 let mut tp_idx = vec![0usize; nparent];
319
320 loop {
321 let t_cur = t_entries.get(ti);
322
323 if t_cur.is_none() && (0..nparent).all(|i| tp_idx[i] >= tp_entries[i].len()) {
324 break;
325 }
326
327 let mut imin = 0usize;
328 if nparent > 0 {
329 for i in 1..nparent {
330 let e_imin = tp_entries[imin].get(tp_idx[imin]);
331 let e_i = tp_entries[i].get(tp_idx[i]);
332 if tree_entry_pathcmp(e_i, e_imin) == std::cmp::Ordering::Less {
333 imin = i;
334 }
335 }
336 }
337
338 let mut parent_neq = vec![false; nparent];
339 for i in 0..nparent {
340 let e_imin = tp_entries[imin].get(tp_idx[imin]);
341 let e_i = tp_entries[i].get(tp_idx[i]);
342 parent_neq[i] = tree_entry_pathcmp(e_i, e_imin) != std::cmp::Ordering::Equal;
343 }
344 for ne in parent_neq.iter_mut().take(imin) {
345 *ne = true;
346 }
347
348 let p_min = tp_entries[imin].get(tp_idx[imin]);
349
350 let cmp = tree_entry_pathcmp(t_cur, p_min);
351
352 if cmp == std::cmp::Ordering::Equal {
353 if let Some(te) = t_cur {
354 let mut skip_emit = false;
360 for i in 0..nparent {
361 if parent_neq[i] {
363 continue;
364 }
365 if let Some(pe) = tp_entries[i].get(tp_idx[i]) {
366 if pe.oid == te.oid && pe.mode == te.mode {
367 skip_emit = true;
369 break;
370 }
371 }
372 }
373
374 if !skip_emit {
375 let name = std::str::from_utf8(&te.name).unwrap_or("");
376 let full_path = if base_path.is_empty() {
377 name.to_string()
378 } else {
379 format!("{base_path}/{name}")
380 };
381
382 let isdir = is_tree_mode(te.mode);
383 let mut do_emit = true;
384 if isdir && should_recurse_dir(&full_path, opt) {
385 do_emit = opt.tree_in_recursive;
386 }
387
388 if do_emit {
389 emit_combined_path(
390 full_path.clone(),
391 Some(te),
392 &tp_entries,
393 &tp_idx,
394 &parent_neq,
395 find_object,
396 out,
397 );
398 }
399
400 if isdir && should_recurse_dir(&full_path, opt) {
401 let merge_child = te.oid;
402 let mut child_parent_opts = vec![None; nparent];
403 for i in 0..nparent {
404 if parent_neq[i] {
405 continue;
406 }
407 if let Some(pe) = tp_entries[i].get(tp_idx[i]) {
408 if tree_name_cmp(
409 &pe.name,
410 is_tree_mode(pe.mode),
411 &te.name,
412 is_tree_mode(te.mode),
413 ) == std::cmp::Ordering::Equal
414 {
415 child_parent_opts[i] = Some(pe.oid);
416 }
417 }
418 }
419 ll_diff_tree_paths(
420 odb,
421 out,
422 &full_path,
423 opt,
424 Some(&merge_child),
425 &child_parent_opts,
426 find_object,
427 )?;
428 }
429 }
430 }
431
432 ti += 1;
433 for i in 0..nparent {
434 if !parent_neq[i] {
435 tp_idx[i] += 1;
436 }
437 }
438 } else if cmp == std::cmp::Ordering::Less {
439 let Some(te) = t_cur else {
440 ti += 1;
441 continue;
442 };
443 let name = std::str::from_utf8(&te.name).unwrap_or("");
444 let full_path = if base_path.is_empty() {
445 name.to_string()
446 } else {
447 format!("{base_path}/{name}")
448 };
449 let isdir = is_tree_mode(te.mode);
450 let mut do_emit = true;
451 if isdir && should_recurse_dir(&full_path, opt) {
452 do_emit = opt.tree_in_recursive;
453 }
454 if do_emit {
455 let all_parents_absent: Vec<bool> = vec![true; nparent];
456 emit_combined_path(
457 full_path.clone(),
458 Some(te),
459 &tp_entries,
460 &tp_idx,
461 &all_parents_absent,
462 find_object,
463 out,
464 );
465 }
466 if isdir && should_recurse_dir(&full_path, opt) {
467 let merge_child = te.oid;
468 let child_parent_opts = vec![None; nparent];
469 ll_diff_tree_paths(
470 odb,
471 out,
472 &full_path,
473 opt,
474 Some(&merge_child),
475 &child_parent_opts,
476 find_object,
477 )?;
478 }
479 ti += 1;
480 } else {
481 let skip_emit_tp = (0..nparent).any(|i| parent_neq[i]);
485 if !skip_emit_tp {
486 if let Some(pe) = p_min {
487 let name = std::str::from_utf8(&pe.name).unwrap_or("");
488 let full_path = if base_path.is_empty() {
489 name.to_string()
490 } else {
491 format!("{base_path}/{name}")
492 };
493 let isdir = is_tree_mode(pe.mode);
494 let mut do_emit = true;
495 if isdir && should_recurse_dir(&full_path, opt) {
496 do_emit = opt.tree_in_recursive;
497 }
498 if do_emit {
499 emit_combined_path(
500 full_path.clone(),
501 None,
502 &tp_entries,
503 &tp_idx,
504 &parent_neq,
505 find_object,
506 out,
507 );
508 }
509 if isdir && should_recurse_dir(&full_path, opt) {
510 let mut child_parent_opts = vec![None; nparent];
511 for i in 0..nparent {
512 if !parent_neq[i] {
513 if let Some(e) = tp_entries[i].get(tp_idx[i]) {
514 child_parent_opts[i] = Some(e.oid);
515 }
516 }
517 }
518 ll_diff_tree_paths(
519 odb,
520 out,
521 &full_path,
522 opt,
523 None,
524 &child_parent_opts,
525 find_object,
526 )?;
527 }
528 }
529 }
530 for i in 0..nparent {
531 if !parent_neq[i] {
532 tp_idx[i] += 1;
533 }
534 }
535 }
536 }
537
538 Ok(())
539}
540
541pub fn combined_diff_paths_filtered(
543 odb: &Odb,
544 commit_tree: &ObjectId,
545 parents: &[ObjectId],
546 walk: &CombinedTreeDiffOptions,
547 find_object: Option<&ObjectId>,
548) -> Result<Vec<CombinedDiffPath>> {
549 if parents.is_empty() {
550 return Ok(Vec::new());
551 }
552 let mut parent_trees = Vec::with_capacity(parents.len());
553 for p in parents {
554 let obj = odb.read(p)?;
555 if obj.kind != ObjectKind::Commit {
556 return Ok(Vec::new());
557 }
558 let c = parse_commit(&obj.data)?;
559 parent_trees.push(Some(c.tree));
560 }
561 let parent_opts: Vec<Option<ObjectId>> = parent_trees;
562 combined_diff_paths_trees(odb, commit_tree, &parent_opts, walk, find_object)
563}
564
565pub fn combined_diff_paths_trees(
567 odb: &Odb,
568 merge_tree: &ObjectId,
569 parent_trees: &[Option<ObjectId>],
570 walk: &CombinedTreeDiffOptions,
571 find_object: Option<&ObjectId>,
572) -> Result<Vec<CombinedDiffPath>> {
573 if parent_trees.is_empty() {
574 return Ok(Vec::new());
575 }
576 let mut out = Vec::new();
577 ll_diff_tree_paths(
578 odb,
579 &mut out,
580 "",
581 walk,
582 Some(merge_tree),
583 parent_trees,
584 find_object,
585 )?;
586 Ok(out)
587}