Skip to main content

grit_lib/diff/
hunk_id.rs

1//! Stable identifiers for structured diff hunks (patch selection in later steps).
2//!
3//! Ids hash side, path, and hunk line bodies (not line numbers) so they stay stable
4//! when earlier hunks are staged and later hunks shift in the file.
5
6use std::collections::{HashMap, HashSet};
7use std::fmt;
8use std::str::FromStr;
9
10use thiserror::Error;
11
12use super::structured::{StructuredHunk, StructuredLine, StructuredLineKind};
13use crate::diff::structured::{
14    hash_hunk_body_from_unified_slice, hunk_body_digest_from_unified_slice,
15};
16use crate::diff::unified_hunk_header_counts;
17use crate::hash::ChecksumHasher;
18use crate::objects::HashAlgo;
19
20const HUNK_ID_HEX_LEN: usize = 12;
21
22/// Which tree/index/worktree sides a hunk was produced from.
23#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
24pub enum DiffSide {
25    /// Index compared to worktree (unstaged changes).
26    Unstaged,
27    /// `HEAD` tree compared to index (staged changes).
28    Staged,
29    /// Commit, tree, or other comparisons (ids are computed but not selectable yet).
30    Other,
31}
32
33impl DiffSide {
34    fn tag_byte(self) -> u8 {
35        match self {
36            Self::Unstaged => 0,
37            Self::Staged => 1,
38            Self::Other => 2,
39        }
40    }
41}
42
43/// Lowercase side name: `unstaged`, `staged` or `other`.
44impl fmt::Display for DiffSide {
45    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
46        f.write_str(match self {
47            Self::Unstaged => "unstaged",
48            Self::Staged => "staged",
49            Self::Other => "other",
50        })
51    }
52}
53
54/// Twelve lowercase hex characters identifying one structured hunk within a side and path.
55#[derive(Debug, Clone, PartialEq, Eq, Hash)]
56pub struct HunkId([u8; HUNK_ID_HEX_LEN / 2]);
57
58/// Parse or format failure for [`HunkId`].
59#[derive(Debug, Error, PartialEq, Eq)]
60#[non_exhaustive]
61pub enum HunkIdError {
62    /// Wrong length or non-hex character.
63    #[error("hunk id must be {HUNK_ID_HEX_LEN} lowercase hex characters")]
64    Invalid,
65}
66
67impl HunkId {
68    fn from_digest(digest: &[u8]) -> Self {
69        let mut raw = [0u8; HUNK_ID_HEX_LEN / 2];
70        raw.copy_from_slice(&digest[..HUNK_ID_HEX_LEN / 2]);
71        Self(raw)
72    }
73
74    /// Construct from exactly six raw digest bytes (used in tests).
75    #[must_use]
76    pub fn from_bytes(bytes: [u8; HUNK_ID_HEX_LEN / 2]) -> Self {
77        Self(bytes)
78    }
79
80    /// View as lowercase hex (twelve characters).
81    #[must_use]
82    pub fn as_str(&self) -> String {
83        self.to_string()
84    }
85}
86
87impl fmt::Display for HunkId {
88    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
89        for b in self.0 {
90            write!(f, "{b:02x}")?;
91        }
92        Ok(())
93    }
94}
95
96impl FromStr for HunkId {
97    type Err = HunkIdError;
98
99    fn from_str(s: &str) -> Result<Self, Self::Err> {
100        if s.len() != HUNK_ID_HEX_LEN
101            || !s
102                .bytes()
103                .all(|c| c.is_ascii_digit() || (b'a'..=b'f').contains(&c))
104        {
105            return Err(HunkIdError::Invalid);
106        }
107        let mut raw = [0u8; HUNK_ID_HEX_LEN / 2];
108        for (i, chunk) in s.as_bytes().chunks(2).enumerate() {
109            let hi = hex_nibble(chunk[0]).ok_or(HunkIdError::Invalid)?;
110            let lo = hex_nibble(chunk[1]).ok_or(HunkIdError::Invalid)?;
111            raw[i] = (hi << 4) | lo;
112        }
113        Ok(Self(raw))
114    }
115}
116
117fn hex_nibble(b: u8) -> Option<u8> {
118    match b {
119        b'0'..=b'9' => Some(b - b'0'),
120        b'a'..=b'f' => Some(b - b'a' + 10),
121        _ => None,
122    }
123}
124
125fn hash_hunk_id(
126    side: DiffSide,
127    path: &str,
128    hunk: &StructuredHunk,
129    duplicate_rank: Option<u32>,
130) -> HunkId {
131    let mut hasher = HashAlgo::Sha1.checksum_hasher();
132    hasher.update(&[side.tag_byte()]);
133    hasher.update(path.as_bytes());
134    hasher.update(&[0]);
135    hash_hunk_body(&mut hasher, hunk);
136    if let Some(rank) = duplicate_rank {
137        hasher.update(&rank.to_le_bytes());
138    }
139    let digest = hasher.finalize();
140    HunkId::from_digest(&digest)
141}
142
143#[derive(Eq, PartialEq, Ord, PartialOrd)]
144struct DuplicateSortKey {
145    old_start: usize,
146    new_start: usize,
147    is_peer: bool,
148    index: usize,
149}
150
151fn duplicate_ranks(hunks: &[StructuredHunk], peer_hunks: &[StructuredHunk]) -> Vec<Option<u32>> {
152    let own_digests: Vec<Vec<u8>> = hunks.iter().map(hunk_body_digest).collect();
153    let peer_digests: Vec<Vec<u8>> = peer_hunks.iter().map(hunk_body_digest).collect();
154    let body_counts = body_count_map_from_digests(&own_digests, &peer_digests);
155    own_digests
156        .iter()
157        .enumerate()
158        .map(|(i, body)| {
159            duplicate_rank_for_body(i, body, hunks, peer_hunks, body_counts.get(body).copied())
160        })
161        .collect()
162}
163
164fn duplicate_rank_for_body(
165    index: usize,
166    body: &[u8],
167    hunks: &[StructuredHunk],
168    peer_hunks: &[StructuredHunk],
169    body_count: Option<u32>,
170) -> Option<u32> {
171    if body_count.unwrap_or(0) <= 1 {
172        return None;
173    }
174    let mut keys: Vec<DuplicateSortKey> = Vec::new();
175    for (j, x) in hunks.iter().enumerate() {
176        if hunk_body_digest(x) == body {
177            keys.push(DuplicateSortKey {
178                old_start: x.old_start,
179                new_start: x.new_start,
180                is_peer: false,
181                index: j,
182            });
183        }
184    }
185    for (j, x) in peer_hunks.iter().enumerate() {
186        if hunk_body_digest(x) == body {
187            keys.push(DuplicateSortKey {
188                old_start: x.old_start,
189                new_start: x.new_start,
190                is_peer: true,
191                index: j,
192            });
193        }
194    }
195    keys.sort();
196    keys.iter()
197        .position(|k| !k.is_peer && k.index == index)
198        .map(|p| p as u32)
199}
200
201fn unified_slice_starts(slice: &str) -> (usize, usize) {
202    slice
203        .split('\n')
204        .next()
205        .and_then(unified_hunk_header_counts)
206        .map(|(o, _, n, _)| (o, n))
207        .unwrap_or((0, 0))
208}
209
210#[allow(clippy::too_many_arguments)]
211fn duplicate_ranks_unified_slices(
212    slices: &[&str],
213    before_count: usize,
214    after_count: usize,
215    before_ends_nl: bool,
216    after_ends_nl: bool,
217    peer_hunks: &[StructuredHunk],
218) -> Vec<Option<u32>> {
219    let bodies: Vec<Option<Vec<u8>>> = slices
220        .iter()
221        .map(|slice| {
222            hunk_body_digest_from_unified_slice(
223                slice,
224                before_count,
225                after_count,
226                before_ends_nl,
227                after_ends_nl,
228            )
229        })
230        .collect();
231    let mut body_counts: std::collections::HashMap<Vec<u8>, u32> = std::collections::HashMap::new();
232    for body in bodies.iter().flatten() {
233        *body_counts.entry(body.clone()).or_insert(0) += 1;
234    }
235    for h in peer_hunks {
236        let body = hunk_body_digest(h);
237        *body_counts.entry(body).or_insert(0) += 1;
238    }
239    bodies
240        .iter()
241        .enumerate()
242        .map(|(i, body)| {
243            let body = body.as_ref()?;
244            if body_counts.get(body).copied().unwrap_or(0) <= 1 {
245                return None;
246            }
247            let mut keys: Vec<DuplicateSortKey> = Vec::new();
248            for (j, other) in slices.iter().enumerate() {
249                let Some(other_body) = hunk_body_digest_from_unified_slice(
250                    other,
251                    before_count,
252                    after_count,
253                    before_ends_nl,
254                    after_ends_nl,
255                ) else {
256                    continue;
257                };
258                if &other_body != body {
259                    continue;
260                }
261                let (o, n) = unified_slice_starts(other);
262                keys.push(DuplicateSortKey {
263                    old_start: o,
264                    new_start: n,
265                    is_peer: false,
266                    index: j,
267                });
268            }
269            for (j, x) in peer_hunks.iter().enumerate() {
270                if hunk_body_digest(x) == *body {
271                    keys.push(DuplicateSortKey {
272                        old_start: peer_hunks[j].old_start,
273                        new_start: peer_hunks[j].new_start,
274                        is_peer: true,
275                        index: j,
276                    });
277                }
278            }
279            keys.sort();
280            keys.iter()
281                .position(|k| !k.is_peer && k.index == i)
282                .map(|p| p as u32)
283        })
284        .collect()
285}
286
287#[allow(clippy::too_many_arguments)]
288fn hash_hunk_id_from_unified_slice(
289    side: DiffSide,
290    path: &str,
291    slice: &str,
292    before_count: usize,
293    after_count: usize,
294    before_ends_nl: bool,
295    after_ends_nl: bool,
296    duplicate_rank: Option<u32>,
297) -> Option<HunkId> {
298    let mut hasher = HashAlgo::Sha1.checksum_hasher();
299    hasher.update(&[side.tag_byte()]);
300    hasher.update(path.as_bytes());
301    hasher.update(&[0]);
302    if !hash_hunk_body_from_unified_slice(
303        &mut hasher,
304        slice,
305        before_count,
306        after_count,
307        before_ends_nl,
308        after_ends_nl,
309    ) {
310        return None;
311    }
312    if let Some(rank) = duplicate_rank {
313        hasher.update(&rank.to_le_bytes());
314    }
315    let digest = hasher.finalize();
316    Some(HunkId::from_digest(&digest))
317}
318
319fn body_count_map_from_digests(own: &[Vec<u8>], peer: &[Vec<u8>]) -> HashMap<Vec<u8>, u32> {
320    let mut counts: HashMap<Vec<u8>, u32> = HashMap::new();
321    for body in own.iter().chain(peer.iter()) {
322        *counts.entry(body.clone()).or_insert(0) += 1;
323    }
324    counts
325}
326
327fn hash_hunk_body(hasher: &mut ChecksumHasher, hunk: &StructuredHunk) {
328    for line in &hunk.lines {
329        hash_line(hasher, line);
330    }
331}
332
333fn hash_line(hasher: &mut ChecksumHasher, line: &StructuredLine) {
334    let kind = match line.kind {
335        StructuredLineKind::Context => b' ',
336        StructuredLineKind::Add => b'+',
337        StructuredLineKind::Del => b'-',
338    };
339    hasher.update(&[kind]);
340    for seg in &line.segments {
341        hasher.update(seg.text.as_bytes());
342    }
343    hasher.update(&[if line.no_newline_at_eof { 1 } else { 0 }]);
344}
345
346fn hunk_body_digest(hunk: &StructuredHunk) -> Vec<u8> {
347    let mut hasher = HashAlgo::Sha1.checksum_hasher();
348    hash_hunk_body(&mut hasher, hunk);
349    hasher.finalize()
350}
351
352/// True when a diff entry's displayed or old path is listed in the primary change set.
353///
354/// Used to limit opposite-side peer loading to paths that can affect duplicate hunk ids.
355#[must_use]
356pub fn peer_scope_includes_path(
357    display_path: &str,
358    old_path: Option<&str>,
359    primary: &HashSet<&str>,
360) -> bool {
361    if primary.contains(display_path) {
362        return true;
363    }
364    if let Some(old) = old_path {
365        if old != display_path && primary.contains(old) {
366            return true;
367        }
368    }
369    false
370}
371
372/// Keep structured peer hunks only for paths present in the primary side.
373#[must_use]
374pub fn peer_hunks_by_primary_path(
375    primary: &HashSet<&str>,
376    peer_by_path: impl IntoIterator<Item = (String, Vec<StructuredHunk>)>,
377) -> HashMap<String, Vec<StructuredHunk>> {
378    peer_by_path
379        .into_iter()
380        .filter(|(path, _)| primary.contains(path.as_str()))
381        .collect()
382}
383
384/// Stable ids for `hunks` in file order (0-based index matches vector position).
385///
386/// `peer_hunks` are the hunks on the same path on the other side of the index (staged for an
387/// unstaged diff and the reverse); they take part in duplicate-body ranking so an id stays
388/// stable when an earlier identical hunk moves to the other side. Pass `&[]` when there are
389/// none.
390#[must_use]
391pub fn hunk_ids(
392    side: DiffSide,
393    path: &str,
394    hunks: &[StructuredHunk],
395    peer_hunks: &[StructuredHunk],
396) -> Vec<HunkId> {
397    let ranks = duplicate_ranks(hunks, peer_hunks);
398    hunks
399        .iter()
400        .zip(ranks)
401        .map(|(h, rank)| hash_hunk_id(side, path, h, rank))
402        .collect()
403}
404
405/// Stable ids for unified hunk slices (`@@` …) in the same order as [`super::core::imara_unified_hunk_slices`].
406#[must_use]
407#[allow(clippy::too_many_arguments)]
408pub(crate) fn hunk_ids_for_unified_slices(
409    side: DiffSide,
410    path: &str,
411    slices: &[&str],
412    before_count: usize,
413    after_count: usize,
414    before_ends_nl: bool,
415    after_ends_nl: bool,
416    peer_hunks: &[StructuredHunk],
417) -> Vec<HunkId> {
418    let ranks = duplicate_ranks_unified_slices(
419        slices,
420        before_count,
421        after_count,
422        before_ends_nl,
423        after_ends_nl,
424        peer_hunks,
425    );
426    slices
427        .iter()
428        .zip(ranks)
429        .filter_map(|(slice, rank)| {
430            hash_hunk_id_from_unified_slice(
431                side,
432                path,
433                slice,
434                before_count,
435                after_count,
436                before_ends_nl,
437                after_ends_nl,
438                rank,
439            )
440        })
441        .collect()
442}
443
444#[cfg(test)]
445mod tests {
446    use super::*;
447    use crate::diff::structured::{StructuredLineKind, StructuredSegment};
448
449    #[test]
450    fn diff_side_displays_lowercase_name() {
451        assert_eq!(DiffSide::Unstaged.to_string(), "unstaged");
452        assert_eq!(DiffSide::Staged.to_string(), "staged");
453        assert_eq!(DiffSide::Other.to_string(), "other");
454    }
455
456    fn line(kind: StructuredLineKind, text: &str) -> StructuredLine {
457        StructuredLine {
458            kind,
459            old: None,
460            new: None,
461            segments: vec![StructuredSegment {
462                text: text.to_owned(),
463                emphasis: false,
464            }],
465            no_newline_at_eof: false,
466        }
467    }
468
469    fn hunk(lines: Vec<StructuredLine>) -> StructuredHunk {
470        StructuredHunk {
471            old_start: 1,
472            new_start: 1,
473            old_lines: lines.len(),
474            new_lines: lines.len(),
475            context: None,
476            lines,
477        }
478    }
479
480    #[test]
481    fn hunk_id_stable_across_line_shift() {
482        let body = vec![
483            line(StructuredLineKind::Context, "ctx"),
484            line(StructuredLineKind::Add, "new"),
485        ];
486        let mut a = hunk(body.clone());
487        a.old_start = 10;
488        a.new_start = 10;
489        let mut b = hunk(body);
490        b.old_start = 20;
491        b.new_start = 22;
492        let ids_a = hunk_ids(DiffSide::Unstaged, "file.txt", &[a], &[]);
493        let ids_b = hunk_ids(DiffSide::Unstaged, "file.txt", &[b], &[]);
494        assert_eq!(ids_a, ids_b);
495    }
496
497    #[test]
498    fn hunk_id_changes_on_content_change() {
499        let a = hunk(vec![line(StructuredLineKind::Add, "one")]);
500        let b = hunk(vec![line(StructuredLineKind::Add, "two")]);
501        let ids_a = hunk_ids(DiffSide::Unstaged, "f", &[a], &[]);
502        let ids_b = hunk_ids(DiffSide::Unstaged, "f", &[b], &[]);
503        assert_ne!(ids_a[0], ids_b[0]);
504    }
505
506    #[test]
507    fn hunk_id_differs_by_side_and_path() {
508        let h = hunk(vec![line(StructuredLineKind::Add, "x")]);
509        let unstaged = hunk_ids(DiffSide::Unstaged, "a", &[h.clone()], &[]);
510        let staged = hunk_ids(DiffSide::Staged, "a", &[h.clone()], &[]);
511        let other_path = hunk_ids(DiffSide::Unstaged, "b", &[h], &[]);
512        assert_ne!(unstaged[0], staged[0]);
513        assert_ne!(unstaged[0], other_path[0]);
514    }
515
516    #[test]
517    fn hunk_id_duplicate_hunks_disambiguated() {
518        let body = vec![line(StructuredLineKind::Add, "dup")];
519        let mut a = hunk(body.clone());
520        a.old_start = 1;
521        a.new_start = 1;
522        let mut b = hunk(body);
523        b.old_start = 5;
524        b.new_start = 5;
525        let ids = hunk_ids(DiffSide::Staged, "x", &[a, b], &[]);
526        assert_ne!(ids[0], ids[1]);
527    }
528
529    #[test]
530    fn hunk_id_fromstr_rejects_uppercase() {
531        assert_eq!(HunkId::from_str("ABCDEF123456"), Err(HunkIdError::Invalid));
532    }
533
534    #[test]
535    fn hunk_id_stable_when_earlier_duplicate_on_peer_side() {
536        let body = vec![
537            line(StructuredLineKind::Context, "ctx"),
538            line(StructuredLineKind::Add, "same"),
539        ];
540        let mut first = hunk(body.clone());
541        first.old_start = 1;
542        first.new_start = 1;
543        let mut second = hunk(body);
544        second.old_start = 10;
545        second.new_start = 10;
546
547        let both = hunk_ids(
548            DiffSide::Unstaged,
549            "f",
550            &[first.clone(), second.clone()],
551            &[],
552        );
553        assert_ne!(both[0], both[1]);
554
555        let with_peer = hunk_ids(DiffSide::Unstaged, "f", &[second.clone()], &[first]);
556        assert_eq!(with_peer[0], both[1]);
557    }
558
559    #[test]
560    fn hunk_id_stable_when_insertion_coordinates_shift_after_staging() {
561        let body = vec![line(StructuredLineKind::Add, "insert")];
562        let mut first = hunk(body.clone());
563        first.old_start = 19;
564        first.new_start = 19;
565        let mut second = hunk(body);
566        second.old_start = 19;
567        second.new_start = 20;
568
569        let both = hunk_ids(
570            DiffSide::Unstaged,
571            "f",
572            &[first.clone(), second.clone()],
573            &[],
574        );
575        assert_ne!(both[0], both[1]);
576        let id_later = both[1].clone();
577
578        let mut shifted = second;
579        shifted.old_start = 20;
580        shifted.new_start = 20;
581
582        let after = hunk_ids(DiffSide::Unstaged, "f", &[shifted], &[first]);
583        assert_eq!(after[0], id_later);
584    }
585
586    #[test]
587    fn hunk_ids_unified_slices_match_structured_hunks() {
588        use crate::diff::imara_unified_hunk_slices;
589        use crate::diff::unified_hunk_body_for_diff_options;
590        use crate::diff::DiffOptions;
591
592        let old = "a\nb\nc\n";
593        let new = "a\nB\nc\nd\n";
594        let opts = DiffOptions::default();
595        let body = unified_hunk_body_for_diff_options(old, new, &opts);
596        let slices: Vec<&str> = imara_unified_hunk_slices(&body);
597        let before_count = 3;
598        let after_count = 4;
599        let from_slices = hunk_ids_for_unified_slices(
600            DiffSide::Unstaged,
601            "f.txt",
602            &slices,
603            before_count,
604            after_count,
605            true,
606            true,
607            &[],
608        );
609        let structured: Vec<StructuredHunk> = slices
610            .iter()
611            .filter_map(|slice| {
612                crate::diff::structured::structured_hunk_for_id_from_unified_slice(
613                    slice,
614                    before_count,
615                    after_count,
616                    true,
617                    true,
618                )
619            })
620            .collect();
621        let from_structured = hunk_ids(DiffSide::Unstaged, "f.txt", &structured, &[]);
622        assert_eq!(from_slices, from_structured);
623    }
624
625    #[test]
626    fn hunk_id_roundtrips_display_fromstr() {
627        let id = hunk_ids(
628            DiffSide::Other,
629            "p",
630            &[hunk(vec![line(StructuredLineKind::Del, "z")])],
631            &[],
632        )[0]
633        .clone();
634        let s = id.to_string();
635        assert_eq!(s.len(), HUNK_ID_HEX_LEN);
636        assert!(
637            s.bytes()
638                .all(|c| c.is_ascii_digit() || (b'a'..=b'f').contains(&c)),
639            "expected lowercase hex: {s}"
640        );
641        assert_eq!(HunkId::from_str(&s).expect("parse"), id);
642    }
643}