gix_imara_diff/postprocess.rs
1// Modified for gitoxide from the upstream imara-diff crate.
2// Upstream source: git cat-file -p 32d1e45d3df061e6ccba6db7fdce92db29e345d8:src/postprocess.rs
3
4use crate::intern::{InternedInput, Token};
5use crate::slider_heuristic::SliderHeuristic;
6use crate::util::{find_hunk_end, find_hunk_start};
7use crate::{Diff, Hunk};
8
9impl Diff {
10 /// Postprocesses the diff using explicit token sequences and a custom heuristic.
11 ///
12 /// This is a lower-level method that works directly with token sequences rather than
13 /// an `InternedInput`. Use [`postprocess_with_heuristic`](Self::postprocess_with_heuristic)
14 /// for a more convenient API.
15 ///
16 /// # Parameters
17 ///
18 /// * `before` - The token sequence from the first file, before changes
19 /// * `after` - The token sequence from the second file, after changes
20 /// * `heuristic` - The slider heuristic to use for positioning hunks
21 pub fn postprocess_with(&mut self, before: &[Token], after: &[Token], mut heuristic: impl SliderHeuristic) {
22 // Compact removals first so ambiguous additions align with them, as in Git.
23 Postprocessor {
24 added: &mut self.removed,
25 removed: &mut self.added,
26 tokens: before,
27 hunk: Hunk {
28 before: 0..0,
29 after: 0..0,
30 },
31 heuristic: &mut heuristic,
32 }
33 .run();
34 Postprocessor {
35 added: &mut self.added,
36 removed: &mut self.removed,
37 tokens: after,
38 hunk: Hunk {
39 before: 0..0,
40 after: 0..0,
41 },
42 heuristic: &mut heuristic,
43 }
44 .run()
45 }
46
47 /// Postprocesses the diff using an `InternedInput` and a custom heuristic.
48 ///
49 /// This is a convenience wrapper around [`postprocess_with`](Self::postprocess_with)
50 /// that extracts the token sequences from the input automatically.
51 ///
52 /// # Parameters
53 ///
54 /// * `input` - The interned input containing the token sequences
55 /// * `heuristic` - The slider heuristic to use for positioning hunks
56 pub fn postprocess_with_heuristic<T>(&mut self, input: &InternedInput<T>, heuristic: impl SliderHeuristic) {
57 self.postprocess_with(&input.before, &input.after, heuristic);
58 }
59}
60
61/// Internal state for postprocessing a diff to improve readability.
62struct Postprocessor<'a, H> {
63 /// The mutable array tracking which tokens were added.
64 added: &'a mut [bool],
65 /// The immutable array tracking which tokens were removed.
66 removed: &'a [bool],
67 /// The token sequence being processed.
68 tokens: &'a [Token],
69 /// The current hunk being processed in the iteration.
70 hunk: Hunk,
71 /// The heuristic used to determine optimal hunk positions.
72 heuristic: &'a mut H,
73}
74
75impl<H: SliderHeuristic> Postprocessor<'_, H> {
76 fn run(mut self) {
77 loop {
78 // find a hunk
79 if !self.hunk.next_hunk(self.removed, self.added) {
80 break;
81 }
82
83 let mut earliest_end;
84 let mut is_modification;
85 loop {
86 // move hunk up as far as possible to possibly merge it with other hunks
87 // and discover if there are other possible positions
88 while self.slide_up() {}
89 earliest_end = self.hunk.after.end;
90 is_modification = self.hunk.before.start != self.hunk.before.end;
91
92 let hunk_size_unexpanded = self.hunk.after.len();
93 // move hunk down as far as possible (and merge with other hunks it if
94 // possible) sliding down is often the most preferred position
95 while self.slide_down() {
96 is_modification |= self.hunk.before.start != self.hunk.before.end;
97 }
98 // if this hunk was merged with another hunk while sliding down we might
99 // be able to slide up more otherwise we are done
100 if hunk_size_unexpanded == self.hunk.after.len() {
101 break;
102 }
103 }
104
105 if self.hunk.after.end == earliest_end {
106 continue;
107 }
108 if is_modification {
109 // hunk can be moved and there is a removed hunk in the same region
110 // move the hunk so it align with the other hunk to produce a single
111 // MODIFIED hunk instead of two separate ADDED/REMOVED hunks
112 while self.hunk.before.start == self.hunk.before.end {
113 let success = self.slide_up();
114 debug_assert!(success);
115 }
116 } else {
117 let slider_end = self
118 .heuristic
119 .best_slider_end(self.tokens, self.hunk.after.clone(), earliest_end);
120 for _ in slider_end..self.hunk.after.end {
121 let success = self.slide_up();
122 debug_assert!(success);
123 }
124 }
125 }
126 }
127
128 /// Slides a hunk down by one token/line, potentially merging it with a subsequent hunk.
129 fn slide_down(&mut self) -> bool {
130 let Some(&next_token) = self.tokens.get(self.hunk.after.end as usize) else {
131 return false;
132 };
133 if self.tokens[self.hunk.after.start as usize] != next_token {
134 return false;
135 }
136 self.added[self.hunk.after.start as usize] = false;
137 self.added[self.hunk.after.end as usize] = true;
138 self.hunk.after.start += 1;
139 self.hunk.after.end = find_hunk_end(self.added, self.hunk.after.end);
140 // move the end of the remove range one down to keep the unchanged lines aligned
141 self.hunk.before.start = self.hunk.before.end + 1;
142 self.hunk.before.end = find_hunk_end(self.removed, self.hunk.before.start);
143 true
144 }
145
146 /// Slides a hunk up by one token/line, potentially merging it with a previous hunk.
147 fn slide_up(&mut self) -> bool {
148 if self.hunk.after.start == 0 {
149 return false;
150 }
151 if self.tokens[self.hunk.after.start as usize - 1] != self.tokens[self.hunk.after.end as usize - 1] {
152 return false;
153 }
154 self.added[self.hunk.after.start as usize - 1] = true;
155 self.added[self.hunk.after.end as usize - 1] = false;
156 self.hunk.after.end -= 1;
157 self.hunk.after.start = find_hunk_start(self.added, self.hunk.after.start - 1);
158 // move the start of the remove range one up to keep the unchanged lines aligned
159 self.hunk.before.end = self.hunk.before.start - 1;
160 self.hunk.before.start = find_hunk_start(self.removed, self.hunk.before.start - 1);
161 true
162 }
163}