djvu_rs/
semantic_diff.rs

1//! Semantic comparison of two DjVu documents (#696).
2//!
3//! Unlike a byte diff, this compares what the documents *mean*: page
4//! properties, extracted text, annotations, metadata, bookmarks, and the
5//! component graph. Each plane reports `Match` or `Diverge` with a bounded
6//! list of human-readable details; encoding differences that decode to the
7//! same content compare as equal.
8
9use crate::component_graph::ComponentGraph;
10use crate::djvu_document::{DjVuBookmark, DjVuDocument, DocError};
11use crate::metadata::DjVuMetadata;
12use crate::text::{TextZone, TextZoneKind};
13
14/// Per-plane comparison status.
15#[derive(Debug, Clone, Copy, PartialEq, Eq)]
16pub enum PlaneStatus {
17    /// The plane is semantically identical in both documents.
18    Match,
19    /// The plane differs; see the accompanying details.
20    Diverge,
21}
22
23/// One compared plane and its outcome.
24#[derive(Debug, Clone)]
25pub struct PlaneDiff {
26    /// Stable plane name: `pages`, `text`, `annotations`, `metadata`,
27    /// `bookmarks`, or `component_graph`.
28    pub plane: &'static str,
29    /// Whether the plane matched.
30    pub status: PlaneStatus,
31    /// Bounded human-readable divergence details (empty when matching).
32    pub details: Vec<String>,
33}
34
35/// The result of a semantic comparison.
36#[derive(Debug, Clone)]
37pub struct SemanticDiff {
38    /// One entry per evaluated plane, in canonical plane order.
39    pub planes: Vec<PlaneDiff>,
40}
41
42impl SemanticDiff {
43    /// Whether every evaluated plane matched.
44    pub fn is_identical(&self) -> bool {
45        self.planes
46            .iter()
47            .all(|plane| plane.status == PlaneStatus::Match)
48    }
49}
50
51/// All plane names, in canonical evaluation/report order.
52pub const PLANES: [&str; 6] = [
53    "pages",
54    "text",
55    "annotations",
56    "metadata",
57    "bookmarks",
58    "component_graph",
59];
60
61/// Cap on per-plane detail lines so a pathological pair cannot flood output.
62const MAX_DETAILS: usize = 8;
63
64/// Compare two documents semantically.
65///
66/// `planes` filters which planes are evaluated (`None` = all). Unknown plane
67/// names are ignored. Parse failures of either input are hard errors — a
68/// document that cannot be opened cannot be compared; use `djvu validate` for
69/// damaged files.
70pub fn semantic_diff(
71    a: &[u8],
72    b: &[u8],
73    planes: Option<&[String]>,
74) -> Result<SemanticDiff, DocError> {
75    let doc_a = DjVuDocument::parse(a)?;
76    let doc_b = DjVuDocument::parse(b)?;
77
78    let wanted =
79        |name: &str| -> bool { planes.is_none_or(|list| list.iter().any(|plane| plane == name)) };
80
81    let mut result = SemanticDiff { planes: Vec::new() };
82    if wanted("pages") {
83        result.planes.push(diff_pages(&doc_a, &doc_b)?);
84    }
85    if wanted("text") {
86        result.planes.push(diff_text(&doc_a, &doc_b)?);
87    }
88    if wanted("annotations") {
89        result.planes.push(diff_annotations(&doc_a, &doc_b)?);
90    }
91    if wanted("metadata") {
92        result.planes.push(diff_metadata(&doc_a, &doc_b)?);
93    }
94    if wanted("bookmarks") {
95        result.planes.push(diff_bookmarks(&doc_a, &doc_b));
96    }
97    if wanted("component_graph") {
98        result.planes.push(diff_component_graph(a, b));
99    }
100    Ok(result)
101}
102
103fn plane(plane: &'static str, details: Vec<String>) -> PlaneDiff {
104    let status = if details.is_empty() {
105        PlaneStatus::Match
106    } else {
107        PlaneStatus::Diverge
108    };
109    let mut details = details;
110    if details.len() > MAX_DETAILS {
111        let hidden = details.len() - MAX_DETAILS;
112        details.truncate(MAX_DETAILS);
113        details.push(format!("... and {hidden} more"));
114    }
115    PlaneDiff {
116        plane,
117        status,
118        details,
119    }
120}
121
122/// Collapse whitespace so layout-only differences compare equal.
123fn text_signature(value: &str) -> String {
124    value.split_whitespace().collect::<Vec<_>>().join(" ")
125}
126
127/// A short, single-line excerpt for divergence messages.
128fn excerpt(value: &str) -> String {
129    const MAX: usize = 48;
130    let mut out: String = value.chars().take(MAX).collect();
131    if value.chars().count() > MAX {
132        out.push('…');
133    }
134    out
135}
136
137fn diff_pages(a: &DjVuDocument, b: &DjVuDocument) -> Result<PlaneDiff, DocError> {
138    let mut details = Vec::new();
139    if a.page_count() != b.page_count() {
140        details.push(format!(
141            "page count differs: {} vs {}",
142            a.page_count(),
143            b.page_count()
144        ));
145    }
146    for index in 0..a.page_count().min(b.page_count()) {
147        let pa = a.page(index)?;
148        let pb = b.page(index)?;
149        let props_a = (pa.width(), pa.height(), pa.dpi());
150        let props_b = (pb.width(), pb.height(), pb.dpi());
151        if props_a != props_b {
152            details.push(format!(
153                "page {}: {}x{} @ {} dpi vs {}x{} @ {} dpi",
154                index + 1,
155                props_a.0,
156                props_a.1,
157                props_a.2,
158                props_b.0,
159                props_b.1,
160                props_b.2,
161            ));
162        }
163    }
164    Ok(plane("pages", details))
165}
166
167fn diff_text(a: &DjVuDocument, b: &DjVuDocument) -> Result<PlaneDiff, DocError> {
168    let mut details = Vec::new();
169    if a.page_count() != b.page_count() {
170        details.push(format!(
171            "page count differs: {} vs {}",
172            a.page_count(),
173            b.page_count()
174        ));
175    }
176    for index in 0..a.page_count().min(b.page_count()) {
177        let text_a = a.page(index)?.text()?.map(|t| text_signature(&t));
178        let text_b = b.page(index)?.text()?.map(|t| text_signature(&t));
179        if text_a != text_b {
180            details.push(format!(
181                "page {}: \"{}\" vs \"{}\"",
182                index + 1,
183                excerpt(text_a.as_deref().unwrap_or("<no text layer>")),
184                excerpt(text_b.as_deref().unwrap_or("<no text layer>")),
185            ));
186        }
187    }
188    Ok(plane("text", details))
189}
190
191fn diff_annotations(a: &DjVuDocument, b: &DjVuDocument) -> Result<PlaneDiff, DocError> {
192    let mut details = Vec::new();
193    if a.page_count() != b.page_count() {
194        details.push(format!(
195            "page count differs: {} vs {}",
196            a.page_count(),
197            b.page_count()
198        ));
199    }
200    for index in 0..a.page_count().min(b.page_count()) {
201        // Debug formatting is a stable within-process signature: both sides
202        // are rendered by the same code in the same binary.
203        let sig_a = a.page(index)?.annotations()?.map(|v| format!("{v:?}"));
204        let sig_b = b.page(index)?.annotations()?.map(|v| format!("{v:?}"));
205        if sig_a != sig_b {
206            details.push(format!(
207                "page {}: annotations differ ({} vs {})",
208                index + 1,
209                sig_a.map_or("absent".to_string(), |s| excerpt(&s)),
210                sig_b.map_or("absent".to_string(), |s| excerpt(&s)),
211            ));
212        }
213    }
214    Ok(plane("annotations", details))
215}
216
217fn metadata_signature(meta: &DjVuMetadata) -> String {
218    let mut pairs = Vec::new();
219    let mut push = |key: &str, value: &Option<String>| {
220        if let Some(value) = value {
221            pairs.push(format!("{key}={}", text_signature(value)));
222        }
223    };
224    push("title", &meta.title);
225    push("author", &meta.author);
226    push("subject", &meta.subject);
227    push("publisher", &meta.publisher);
228    push("year", &meta.year);
229    push("keywords", &meta.keywords);
230    let mut extra: Vec<String> = meta
231        .extra
232        .iter()
233        .map(|(key, value)| format!("{}={}", key.to_ascii_lowercase(), text_signature(value)))
234        .collect();
235    pairs.append(&mut extra);
236    pairs.sort();
237    pairs.join("\n")
238}
239
240fn diff_metadata(a: &DjVuDocument, b: &DjVuDocument) -> Result<PlaneDiff, DocError> {
241    let sig_a = a.metadata()?.as_ref().map(metadata_signature);
242    let sig_b = b.metadata()?.as_ref().map(metadata_signature);
243    let mut details = Vec::new();
244    if sig_a != sig_b {
245        details.push(format!(
246            "metadata differs: {} vs {}",
247            sig_a.map_or("absent".to_string(), |s| excerpt(&s.replace('\n', "; "))),
248            sig_b.map_or("absent".to_string(), |s| excerpt(&s.replace('\n', "; "))),
249        ));
250    }
251    Ok(plane("metadata", details))
252}
253
254fn bookmark_signature(bookmarks: &[DjVuBookmark], out: &mut String, depth: usize) {
255    for bookmark in bookmarks {
256        out.push_str(&format!(
257            "{}{}|{}\n",
258            "  ".repeat(depth),
259            text_signature(&bookmark.title),
260            text_signature(&bookmark.url),
261        ));
262        bookmark_signature(&bookmark.children, out, depth + 1);
263    }
264}
265
266fn diff_bookmarks(a: &DjVuDocument, b: &DjVuDocument) -> PlaneDiff {
267    let sig = |doc: &DjVuDocument| {
268        let mut out = String::new();
269        bookmark_signature(doc.bookmarks(), &mut out, 0);
270        out
271    };
272    let sig_a = sig(a);
273    let sig_b = sig(b);
274    let mut details = Vec::new();
275    if sig_a != sig_b {
276        // Report the first differing line for orientation.
277        let first = sig_a
278            .lines()
279            .zip(sig_b.lines())
280            .find(|(la, lb)| la != lb)
281            .map(|(la, lb)| format!("first differing entry: \"{la}\" vs \"{lb}\""))
282            .unwrap_or_else(|| {
283                format!(
284                    "bookmark count differs: {} vs {} entries",
285                    sig_a.lines().count(),
286                    sig_b.lines().count()
287                )
288            });
289        details.push(first);
290    }
291    plane("bookmarks", details)
292}
293
294fn zone_kind_name(kind: &TextZoneKind) -> &'static str {
295    match kind {
296        TextZoneKind::Page => "page",
297        TextZoneKind::Column => "column",
298        TextZoneKind::Region => "region",
299        TextZoneKind::Para => "para",
300        TextZoneKind::Line => "line",
301        TextZoneKind::Word => "word",
302        TextZoneKind::Character => "char",
303    }
304}
305
306// Currently unused by the plane set (text compares plain text), but kept
307// private-ready for a hierarchy plane; referenced by tests.
308#[allow(dead_code)]
309fn zone_signature(zone: &TextZone, out: &mut String, depth: usize) {
310    out.push_str(&format!(
311        "{}{}:{}\n",
312        "  ".repeat(depth),
313        zone_kind_name(&zone.kind),
314        text_signature(&zone.text),
315    ));
316    for child in &zone.children {
317        zone_signature(child, out, depth + 1);
318    }
319}
320
321fn diff_component_graph(a: &[u8], b: &[u8]) -> PlaneDiff {
322    let graph_a = ComponentGraph::parse(a).ok();
323    let graph_b = ComponentGraph::parse(b).ok();
324    let mut details = Vec::new();
325    match (&graph_a, &graph_b) {
326        (None, None) => {} // both single-page / non-bundled: trivially equal
327        (Some(_), None) => {
328            details.push("only the first document has a bundled component graph".to_string());
329        }
330        (None, Some(_)) => {
331            details.push("only the second document has a bundled component graph".to_string());
332        }
333        (Some(ga), Some(gb)) => {
334            // DIRM sequence (order-sensitive): ids and kinds in directory order.
335            let seq = |graph: &ComponentGraph| {
336                graph
337                    .nodes()
338                    .iter()
339                    .map(|node| format!("{}:{:?}", node.id, node.kind))
340                    .collect::<Vec<_>>()
341            };
342            let seq_a = seq(ga);
343            let seq_b = seq(gb);
344            if seq_a != seq_b {
345                details.push(format!(
346                    "DIRM sequence differs: [{}] vs [{}]",
347                    excerpt(&seq_a.join(", ")),
348                    excerpt(&seq_b.join(", ")),
349                ));
350            }
351            // INCL edge sets (order-insensitive): source -> target pairs.
352            let edges = |graph: &ComponentGraph| {
353                let mut edges: Vec<String> = graph
354                    .nodes()
355                    .iter()
356                    .flat_map(|node| {
357                        node.includes
358                            .iter()
359                            .map(|&target| format!("{}->{}", node.id, graph.nodes()[target].id))
360                    })
361                    .collect();
362                edges.sort();
363                edges
364            };
365            let edges_a = edges(ga);
366            let edges_b = edges(gb);
367            if edges_a != edges_b {
368                for edge in edges_a.iter().filter(|edge| !edges_b.contains(edge)) {
369                    details.push(format!("INCL edge only in first: {edge}"));
370                }
371                for edge in edges_b.iter().filter(|edge| !edges_a.contains(edge)) {
372                    details.push(format!("INCL edge only in second: {edge}"));
373                }
374            }
375        }
376    }
377    plane("component_graph", details)
378}
379
380#[cfg(test)]
381mod tests {
382    use super::*;
383
384    fn fixture(name: &str) -> Vec<u8> {
385        let path = std::path::Path::new(env!("CARGO_MANIFEST_DIR"))
386            .join("tests")
387            .join("fixtures")
388            .join(name);
389        std::fs::read(path).expect("fixture exists")
390    }
391
392    #[test]
393    fn identical_documents_match_on_every_plane() {
394        let bytes = fixture("DjVu3Spec_bundled.djvu");
395        let diff = semantic_diff(&bytes, &bytes, None).expect("diff");
396        assert!(diff.is_identical(), "planes: {:?}", diff.planes);
397        assert_eq!(diff.planes.len(), PLANES.len());
398    }
399
400    #[test]
401    fn different_documents_diverge() {
402        let a = fixture("DjVu3Spec_bundled.djvu");
403        let b = std::fs::read(
404            std::path::Path::new(env!("CARGO_MANIFEST_DIR"))
405                .join("tests")
406                .join("corpus")
407                .join("cable_1973_100133.djvu"),
408        )
409        .expect("corpus fixture");
410        let diff = semantic_diff(&a, &b, None).expect("diff");
411        assert!(!diff.is_identical());
412        // Page counts differ, so at minimum the pages plane diverges.
413        let pages = diff
414            .planes
415            .iter()
416            .find(|plane| plane.plane == "pages")
417            .expect("pages plane present");
418        assert_eq!(pages.status, PlaneStatus::Diverge);
419    }
420
421    #[test]
422    fn plane_filter_limits_evaluation() {
423        let bytes = fixture("DjVu3Spec_bundled.djvu");
424        let planes = vec!["text".to_string()];
425        let diff = semantic_diff(&bytes, &bytes, Some(&planes)).expect("diff");
426        assert_eq!(diff.planes.len(), 1);
427        assert_eq!(diff.planes[0].plane, "text");
428    }
429
430    #[test]
431    fn metadata_only_edit_diverges_only_expected_planes() {
432        use crate::editor::{DocumentEditor, EditOperation, EditRequest};
433        use crate::metadata::DjVuMetadata;
434
435        let original = fixture("DjVu3Spec_bundled.djvu");
436        let edited = DocumentEditor::apply(
437            &original,
438            &EditRequest::new(vec![EditOperation::SetDocumentMetadata {
439                metadata: DjVuMetadata {
440                    title: Some("Edited title".to_string()),
441                    ..Default::default()
442                },
443            }]),
444        )
445        .expect("edit applies");
446
447        let diff = semantic_diff(&original, &edited, None).expect("diff");
448        for plane in &diff.planes {
449            match plane.plane {
450                "metadata" => assert_eq!(plane.status, PlaneStatus::Diverge),
451                // Metadata lives in a document-level chunk; every other
452                // semantic plane must be unaffected by the edit.
453                _ => assert_eq!(
454                    plane.status,
455                    PlaneStatus::Match,
456                    "unexpected divergence in {}: {:?}",
457                    plane.plane,
458                    plane.details
459                ),
460            }
461        }
462    }
463
464    #[test]
465    fn details_are_bounded() {
466        let details: Vec<String> = (0..40).map(|i| format!("detail {i}")).collect();
467        let plane = plane("pages", details);
468        assert!(plane.details.len() <= MAX_DETAILS + 1);
469        assert!(plane.details.last().unwrap().contains("more"));
470    }
471}
djvu_rs/semantic_diff.rs

djvu_rs/
semantic_diff.rs
