Skip to main content

grit_lib/
combined_tree_diff.rs

1//! Multi-parent combined tree diff (Git `diff_tree_paths` / `find_paths_multitree`).
2//!
3//! Implements the `D(T,P1...Pn)` walk from `tree-diff.c` for merge commits, producing
4//! per-path parent status letters used by `git diff-tree -c --name-status` and
5//! `--find-object` filtering (`combined_objfind` in `combine-diff.c`).
6
7use 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/// One character per parent for raw / name-status combined output (`A`/`M`/`D`).
13#[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/// Formatting switches for [`format_combined_raw_line_all_paths_with_options`].
24#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
25#[non_exhaustive]
26pub struct CombinedRawLineFormatOptions {
27    /// Emit every parent's source path before the merge path on rename sides.
28    pub combined_all_paths: bool,
29    /// C-quote path components with `quote_path::quote_c_style`.
30    pub quote_fully: bool,
31}
32
33/// Git raw combined line (`::::modes... oids... MM\tpath`).
34///
35/// When `combined_all_paths` is set and a parent side is a rename, the source name for every
36/// parent is emitted (tab-separated) before the merge-result path, each C-quoted when `quote_fully`
37/// is set.
38#[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/// Like [`format_combined_raw_line_all_paths`], with flags grouped in [`CombinedRawLineFormatOptions`].
56#[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    // Emit metadata (modes/oids/status) followed by one source name per parent and the merge path.
67    // We can't string-split the single-path line on `\t` because funny names contain tabs.
68    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    /// Sets [`combined_all_paths`](Self::combined_all_paths).
81    #[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    /// Sets [`quote_fully`](Self::quote_fully).
88    #[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/// Git raw combined line (`::::modes... oids... MM\tpath`).
96#[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/// Metadata portion of a combined raw line: `::::modes... oids... <status>` (no trailing tab/path).
102#[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/// Per-parent coarse status in a combined diff (`A` / `M` / `D`).
143#[derive(Debug, Clone, Copy, PartialEq, Eq)]
144pub enum CombinedParentStatus {
145    /// Parent lacks the path; merge tree added it.
146    Added,
147    /// Parent has the path at the same name as the merge result.
148    Modified,
149    /// Path removed from merge (only in parents that had it at the min name).
150    Deleted,
151    /// Path renamed relative to this parent (`-M`/`--combined-all-paths`); the source name is
152    /// carried on [`CombinedParentSide::rename_from`].
153    Renamed,
154}
155
156/// One path in a combined diff: merge result tree vs each parent tree.
157#[derive(Debug, Clone)]
158pub struct CombinedDiffPath {
159    /// Path relative to repository root.
160    pub path: String,
161    /// Mode and OID on the merge result side (`0` / zero OID when deleted from merge).
162    pub merge_mode: u32,
163    /// `merge_oid` field.
164    pub merge_oid: ObjectId,
165    /// One slot per parent commit (same order as `parents` passed to [`combined_diff_paths_filtered`]).
166    pub parents: Vec<CombinedParentSide>,
167}
168
169/// One parent's contribution at a combined-diff path.
170#[derive(Debug, Clone)]
171pub struct CombinedParentSide {
172    /// `mode` field.
173    pub mode: u32,
174    /// `oid` field.
175    pub oid: ObjectId,
176    /// `status` field.
177    pub status: CombinedParentStatus,
178    /// Source path when this parent saw the result as a rename (`-M`); `None` otherwise.
179    pub rename_from: Option<String>,
180}
181
182/// Options for the multitree walk.
183#[derive(Debug, Clone, Default)]
184pub struct CombinedTreeDiffOptions {
185    /// Recurse into sub-trees (`diff_options.flags.recursive`).
186    pub recursive: bool,
187    /// Emit tree directory lines when recursing (`tree_in_recursive`, e.g. `--find-object`).
188    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    // Git's `diff_tree_paths` / combined merge diff always recurses into subtrees
297    // (see `diff_tree_combined`: `diffopts.flags.recursive = 1`).
298    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                // Combined-diff intersection rule (git tree-diff.c ll_diff_tree_paths,
355                // cmp == 0 branch): skip the path when it is identical to *some* parent
356                // that has it at p[imin]. A path is only interesting for a combined diff
357                // if it differs from every parent. (find_copies_harder is not modelled
358                // here, matching the fast multitree path.)
359                let mut skip_emit = false;
360                for i in 0..nparent {
361                    // p[i] > p[imin]: path absent in this parent -> "+t" in D(T,Pi).
362                    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                            // diff(t, pi) == empty: result matches this parent -> skip.
368                            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            // git tree-diff.c (t > p[imin] branch): "-p[imin]" is only in D(T,Pi)
482            // when *every* parent has the path at p[imin] (deleted from all of them).
483            // Skip when any parent lacks it (parent_neq[i] set).
484            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
541/// Build combined-diff paths for a merge commit's tree against each parent's tree.
542pub 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
565/// Combined diff paths when `parents` are already tree OIDs (plumbing `git diff --cc` with N+1 trees).
566pub 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}