1#![forbid(unsafe_code)]
2mod algo;
5mod block;
6mod inline;
7mod noise;
8mod unified;
9
10use std::cell::OnceCell;
11use std::collections::{HashMap, VecDeque};
12
13use serde::{Deserialize, Serialize};
14
15pub use block::{Block, BlockKind, normalize, split_blocks};
16pub use inline::{InlineOp, InlineSegment, inline_diff};
17pub use noise::NoiseCategory;
18pub use unified::{DiffLine, Hunk, LineKind, UnifiedDiff, unified_diff};
19
20pub fn align(a: &[u32], b: &[u32]) -> Vec<(usize, usize)> {
23 algo::diff(a, b)
24 .into_iter()
25 .filter_map(|e| match e {
26 Edit::Equal(i, j) => Some((i, j)),
27 _ => None,
28 })
29 .collect()
30}
31
32use algo::Edit;
33
34#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
35#[serde(rename_all = "camelCase")]
36pub enum ChangeType {
37 Added,
38 Removed,
39 Modified,
40 Moved,
41}
42
43#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
44#[serde(rename_all = "camelCase")]
45pub enum Significance {
46 Noise,
47 Substantive,
48}
49
50#[derive(Debug, Clone, Serialize, Deserialize)]
51#[serde(rename_all = "camelCase", default)]
52pub struct DiffOptions {
53 pub noise_categories: Vec<NoiseCategory>,
55 pub moved_is_noise: bool,
57 pub similarity_threshold: f64,
59}
60
61impl Default for DiffOptions {
62 fn default() -> Self {
63 Self {
64 noise_categories: vec![
65 NoiseCategory::Date,
66 NoiseCategory::RelativeTime,
67 NoiseCategory::Price,
68 NoiseCategory::Count,
69 NoiseCategory::Number,
70 ],
71 moved_is_noise: false,
72 similarity_threshold: 0.5,
73 }
74 }
75}
76
77#[derive(Debug, Clone, Serialize, Deserialize)]
78#[serde(rename_all = "camelCase")]
79pub struct BlockChange {
80 #[serde(rename = "type")]
81 pub change: ChangeType,
82 pub block_type: BlockKind,
83 pub significance: Significance,
84 #[serde(default, skip_serializing_if = "Vec::is_empty")]
85 pub noise_categories: Vec<NoiseCategory>,
86 #[serde(skip_serializing_if = "Option::is_none")]
87 pub old_index: Option<usize>,
88 #[serde(skip_serializing_if = "Option::is_none")]
89 pub new_index: Option<usize>,
90 #[serde(skip_serializing_if = "Option::is_none")]
91 pub old_text: Option<String>,
92 #[serde(skip_serializing_if = "Option::is_none")]
93 pub new_text: Option<String>,
94 #[serde(skip_serializing_if = "Option::is_none")]
95 pub old_hash: Option<String>,
96 #[serde(skip_serializing_if = "Option::is_none")]
97 pub new_hash: Option<String>,
98 #[serde(default, skip_serializing_if = "Vec::is_empty")]
99 pub inline: Vec<InlineSegment>,
100}
101
102#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize, Deserialize)]
103#[serde(rename_all = "camelCase")]
104pub struct DiffStats {
105 pub old_blocks: usize,
106 pub new_blocks: usize,
107 pub unchanged: usize,
108 pub added: usize,
109 pub removed: usize,
110 pub modified: usize,
111 pub moved: usize,
112 pub noise: usize,
113 pub substantive: usize,
114}
115
116#[derive(Debug, Clone, Serialize, Deserialize)]
117#[serde(rename_all = "camelCase")]
118pub struct DiffReport {
119 pub changed: bool,
120 pub substantive: bool,
121 pub blocks: Vec<BlockChange>,
122 pub stats: DiffStats,
123}
124
125fn hex(h: &[u8; 32]) -> String {
126 const D: &[u8; 16] = b"0123456789abcdef";
127 let mut s = String::with_capacity(64);
128 for b in h {
129 s.push(D[(b >> 4) as usize] as char);
130 s.push(D[(b & 15) as usize] as char);
131 }
132 s
133}
134
135fn signature(norm: &str) -> Vec<u64> {
137 use std::hash::{BuildHasher, BuildHasherDefault, DefaultHasher};
138 let hasher = BuildHasherDefault::<DefaultHasher>::default();
139 let mut v: Vec<u64> = inline::tokenize(norm)
140 .into_iter()
141 .filter(|t| !t.trim().is_empty())
142 .map(|t| hasher.hash_one(t))
143 .collect();
144 v.sort_unstable();
145 v
146}
147
148fn dice(a: &[u64], b: &[u64]) -> f64 {
149 if a.len() + b.len() == 0 {
150 return 1.0;
151 }
152 let (mut i, mut j, mut common) = (0, 0, 0usize);
153 while i < a.len() && j < b.len() {
154 match a[i].cmp(&b[j]) {
155 std::cmp::Ordering::Less => i += 1,
156 std::cmp::Ordering::Greater => j += 1,
157 std::cmp::Ordering::Equal => {
158 common += 1;
159 i += 1;
160 j += 1;
161 }
162 }
163 }
164 2.0 * common as f64 / (a.len() + b.len()) as f64
165}
166
167const PAIR_WINDOW: usize = 8;
168
169fn intern<'a>(bs: &'a [Block], ids: &mut HashMap<(BlockKind, &'a str), u32>) -> Vec<u32> {
170 bs.iter()
171 .map(|b| {
172 let n = ids.len() as u32;
173 *ids.entry((b.kind, b.norm.as_str())).or_insert(n)
174 })
175 .collect()
176}
177
178pub fn diff(old: &str, new: &str) -> DiffReport {
179 diff_with(old, new, &DiffOptions::default())
180}
181
182pub fn diff_with(old: &str, new: &str, opts: &DiffOptions) -> DiffReport {
183 let ob = split_blocks(old);
184 let nb = split_blocks(new);
185 let mut ids = HashMap::new();
186 let oi = intern(&ob, &mut ids);
187 let ni = intern(&nb, &mut ids);
188 let edits = algo::diff(&oi, &ni);
189
190 let mut stats = DiffStats {
191 old_blocks: ob.len(),
192 new_blocks: nb.len(),
193 ..Default::default()
194 };
195 let mut events: Vec<(usize, BlockChange)> = Vec::new();
196
197 let mut consumed = vec![false; edits.len()];
199 let mut deleted: HashMap<u32, VecDeque<(usize, usize)>> = HashMap::new();
200 for (p, e) in edits.iter().enumerate() {
201 if let Edit::Delete(i) = *e {
202 deleted.entry(oi[i]).or_default().push_back((p, i));
203 }
204 }
205 for (p, e) in edits.iter().enumerate() {
206 if let Edit::Insert(j) = *e
207 && let Some((dp, i)) = deleted.get_mut(&ni[j]).and_then(VecDeque::pop_front)
208 {
209 consumed[dp] = true;
210 consumed[p] = true;
211 events.push((
212 p,
213 BlockChange {
214 change: ChangeType::Moved,
215 block_type: nb[j].kind,
216 significance: if opts.moved_is_noise {
217 Significance::Noise
218 } else {
219 Significance::Substantive
220 },
221 noise_categories: vec![],
222 old_index: Some(i),
223 new_index: Some(j),
224 old_text: Some(ob[i].text.clone()),
225 new_text: Some(nb[j].text.clone()),
226 old_hash: Some(hex(&ob[i].hash())),
227 new_hash: Some(hex(&nb[j].hash())),
228 inline: vec![],
229 },
230 ));
231 }
232 }
233
234 let added = |p: usize, j: usize| {
235 (
236 p,
237 BlockChange {
238 change: ChangeType::Added,
239 block_type: nb[j].kind,
240 significance: Significance::Substantive,
241 noise_categories: vec![],
242 old_index: None,
243 new_index: Some(j),
244 old_text: None,
245 new_text: Some(nb[j].text.clone()),
246 old_hash: None,
247 new_hash: None,
248 inline: vec![],
249 },
250 )
251 };
252 let removed = |p: usize, i: usize| {
253 (
254 p,
255 BlockChange {
256 change: ChangeType::Removed,
257 block_type: ob[i].kind,
258 significance: Significance::Substantive,
259 noise_categories: vec![],
260 old_index: Some(i),
261 new_index: None,
262 old_text: Some(ob[i].text.clone()),
263 new_text: None,
264 old_hash: None,
265 new_hash: None,
266 inline: vec![],
267 },
268 )
269 };
270
271 let osig: Vec<OnceCell<Vec<u64>>> = (0..ob.len()).map(|_| OnceCell::new()).collect();
272 let nsig: Vec<OnceCell<Vec<u64>>> = (0..nb.len()).map(|_| OnceCell::new()).collect();
273 let mut dels: Vec<(usize, usize)> = Vec::new();
274 let mut inss: Vec<(usize, usize)> = Vec::new();
275 let flush = |dels: &mut Vec<(usize, usize)>,
276 inss: &mut Vec<(usize, usize)>,
277 events: &mut Vec<(usize, BlockChange)>| {
278 let mut j = 0;
279 for &(dp, i) in dels.iter() {
280 let hi = (j + PAIR_WINDOW).min(inss.len());
281 let mut best: Option<(usize, f64)> = None;
283 for k in j..hi {
284 if ob[i].kind != nb[inss[k].1].kind {
285 continue;
286 }
287 let so = osig[i].get_or_init(|| signature(&ob[i].norm));
288 let sn = nsig[inss[k].1].get_or_init(|| signature(&nb[inss[k].1].norm));
289 let sim = dice(so, sn);
290 if sim >= opts.similarity_threshold && best.is_none_or(|(_, s)| sim > s) {
291 best = Some((k, sim));
292 if sim >= 0.8 {
293 break;
294 }
295 }
296 }
297 match best {
298 Some((k, _)) => {
299 for &(ip, jj) in &inss[j..k] {
300 events.push(added(ip, jj));
301 }
302 let (ip, jj) = inss[k];
303 j = k + 1;
304 let (o, n) = (&ob[i], &nb[jj]);
305 let (significance, noise_categories) =
306 match noise::classify(&o.norm, &n.norm, &opts.noise_categories) {
307 Some(c) => (Significance::Noise, c),
308 None => (Significance::Substantive, vec![]),
309 };
310 events.push((
311 dp.min(ip),
312 BlockChange {
313 change: ChangeType::Modified,
314 block_type: n.kind,
315 significance,
316 noise_categories,
317 old_index: Some(i),
318 new_index: Some(jj),
319 old_text: Some(o.text.clone()),
320 new_text: Some(n.text.clone()),
321 old_hash: Some(hex(&o.hash())),
322 new_hash: Some(hex(&n.hash())),
323 inline: inline_diff(&o.norm, &n.norm),
324 },
325 ));
326 }
327 None => events.push(removed(dp, i)),
328 }
329 }
330 for &(ip, jj) in &inss[j..] {
331 events.push(added(ip, jj));
332 }
333 dels.clear();
334 inss.clear();
335 };
336
337 for (p, e) in edits.iter().enumerate() {
338 match *e {
339 Edit::Equal(..) => {
340 stats.unchanged += 1;
341 flush(&mut dels, &mut inss, &mut events);
342 }
343 _ if consumed[p] => {}
344 Edit::Delete(i) => dels.push((p, i)),
345 Edit::Insert(j) => inss.push((p, j)),
346 }
347 }
348 flush(&mut dels, &mut inss, &mut events);
349
350 events.sort_by_key(|e| e.0);
351 let blocks: Vec<BlockChange> = events.into_iter().map(|e| e.1).collect();
352 for b in &blocks {
353 match b.change {
354 ChangeType::Added => stats.added += 1,
355 ChangeType::Removed => stats.removed += 1,
356 ChangeType::Modified => stats.modified += 1,
357 ChangeType::Moved => stats.moved += 1,
358 }
359 match b.significance {
360 Significance::Noise => stats.noise += 1,
361 Significance::Substantive => stats.substantive += 1,
362 }
363 }
364 DiffReport {
365 changed: !blocks.is_empty(),
366 substantive: stats.substantive > 0,
367 blocks,
368 stats,
369 }
370}