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

grit_lib/diff/
hunk_id.rs
