Skip to main content

pagesift_diff/
lib.rs

1#![forbid(unsafe_code)]
2//! 同一 URL 两份 Markdown 快照的块级差异对比,并区分噪声变化。
3
4mod 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
20/// 两个 id 序列的对齐(patience 取锚点、锚点间 Myers),返回相等位置对 `(i, j)`,按序递增。
21/// 给块级合并用:调用方把块映射成 id(相同内容同一个 id)。
22pub 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    /// 哪些类别的变化算噪声;不在其中的类别(如价格)按实质变化处理。
54    pub noise_categories: Vec<NoiseCategory>,
55    /// 纯移动是否算噪声。
56    pub moved_is_noise: bool,
57    /// 判定"同一块被修改"的词级相似度下限,0 到 1。
58    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
135/// 块的词集合签名:非空白词的哈希,已排序,用于 Dice 相似度。
136fn 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    // 先配对移动:同一哈希在别处被删除又被插入
198    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            // 顺序候选相似度够高就直接采用,省掉窗口内的其余比较
282            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}