1use 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#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
24pub enum DiffSide {
25 Unstaged,
27 Staged,
29 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
43impl 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#[derive(Debug, Clone, PartialEq, Eq, Hash)]
56pub struct HunkId([u8; HUNK_ID_HEX_LEN / 2]);
57
58#[derive(Debug, Error, PartialEq, Eq)]
60#[non_exhaustive]
61pub enum HunkIdError {
62 #[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 #[must_use]
76 pub fn from_bytes(bytes: [u8; HUNK_ID_HEX_LEN / 2]) -> Self {
77 Self(bytes)
78 }
79
80 #[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#[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#[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#[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#[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}