flpdf 0.1.9

A pure-Rust PDF toolkit modeled on qpdf — read, rewrite, linearize, and inspect PDFs.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
//! Article-thread bead `/P` reference drop after page extraction.
//!
//! After [`crate::page_tree_rebuild::rebuild_page_tree`] has rebuilt the page
//! tree for a subset extraction, this module walks the article-thread beads
//! (ISO 32000-2 §12.4.3) and updates each bead's `/P` (the page the bead
//! belongs to) to match qpdf's `--pages` behaviour:
//!
//! - A bead whose `/P` points at a **surviving** page keeps the entry, remapped
//!   to the page's new [`ObjectRef`] when the rebuild changed it.
//! - A bead whose `/P` points at a **removed** page has the `/P` key
//!   **dropped**. The bead itself — and its `/N`/`/V` ring links, `/T`, and
//!   `/R` — is retained; the now-unreferenced page is garbage-collected by the
//!   subsequent subset sweep ([`crate::subset_prune`]) and is absent from the
//!   output.
//!
//! This is the structural-reference *drop* family, alongside the structure-tree
//! `/Pg` handling ([`crate::struct_tree_pg`]): the reference is removed rather
//! than replaced with `null` (the opposite of the outline / named-destination /
//! annotation null-out family in [`crate::outline_dest_remap`]).
//!
//! # Reaching the beads
//!
//! qpdf reaches a bead ring through **either** entry point, so this pass seeds
//! its walk from both:
//!
//! - the catalog `/Threads` article list (`/Threads` → thread `/F` → ring), and
//! - each surviving page's `/B` bead array.
//!
//! A removed page kept alive only through a sibling bead reachable via a
//! surviving page's `/B` (with no usable `/Threads`) must still have that
//! bead's `/P` dropped, or the prune cannot collect the page. Indirection is
//! normalized through an internal reference-chain resolver at every
//! link (`/Threads`, the thread entry, `/F`, `/N`, `/V`, `/B`, and `/P`), so a
//! reference-to-reference chain, a direct (inline) thread dictionary, or a
//! chained `/P` is handled the same way the page extraction path
//! ([`crate::page_extract`]) handles them. The walk is bounded by a visited set
//! keyed on the terminal bead ref (a thread's beads form a cycle).
//!
//! # qpdf 11.9.0 observed behaviour (truth source `/usr/bin/qpdf`)
//!
//! For `qpdf in.pdf --pages in.pdf 1,3 -- out.pdf` over a document whose page 2
//! is referenced only by an article bead's `/P`, qpdf drops that bead's `/P`
//! and the removed page is absent from the output (not emitted as `null`). The
//! bead stays in the thread ring with its `/N`/`/V`/`/T`/`/R` intact. Even when
//! every bead of a thread targets a removed page, qpdf keeps the thread and all
//! its beads (each with `/P` dropped) — it never removes the thread itself. The
//! same drop applies when the ring is reachable only through a surviving page's
//! `/B` array rather than the catalog `/Threads`.
//!
//! qpdf drops the bead's `/P` even when the removed page is *also* referenced by
//! a surviving outline item or named destination: there the page object is kept
//! as `null` (the destination still points at it), but the bead's `/P` is still
//! dropped.
//!
//! ## Surviving page under a duplicate selection
//!
//! For `qpdf in.pdf --pages in.pdf 1,1,3 -- out.pdf` (page 1 selected twice,
//! page 2 dropped) over the same article-thread document, qpdf emits two page
//! dictionaries for page 1 but does **not** duplicate the bead: both page
//! copies' `/B` arrays reference the **same** single bead object, and that
//! bead's `/P` points at the **first** of the two page copies. The dropped
//! page's bead loses its `/P` as above. So a duplicated page's bead `/P`
//! resolves to the first occurrence of that page.
//!
//! This module's surviving-page rule matches that observation: it remaps a
//! bead's `/P` to `ref_map[old]`'s first new occurrence. Note that
//! [`crate::page_tree_rebuild::rebuild_page_tree`] keeps the **first**
//! occurrence of a surviving page under its original [`ObjectRef`] (only the
//! 2nd+ duplicate copies get fresh numbers), so for every surviving page the
//! first new ref equals the original ref and the remap is an identity — the
//! explicit "remap to a different ref" branch is a defensive invariant that a
//! single-document rebuild never triggers. (This pass operates on a single
//! document; cross-document merge — which could renumber a first occurrence —
//! is out of scope here.)

use crate::page_tree_rebuild::RebuildResult;
use crate::ref_chain::resolve_ref_chain;
use crate::{Dictionary, Object, ObjectRef, Pdf, Result};
use std::collections::{BTreeMap, BTreeSet};
use std::io::{Read, Seek};

/// Drop dangling article-thread bead `/P` references after a page-tree rebuild
/// (qpdf `--pages` parity).
///
/// `result` is the [`RebuildResult`] returned by
/// [`crate::page_tree_rebuild::rebuild_page_tree`]. Its `ref_map` encodes the
/// old → new page reference mapping: a page absent from the map was removed; a
/// page present maps to `ref_map[old][0]` (first new occurrence).
///
/// The walk is seeded from both the catalog `/Threads` article list and every
/// surviving page's `/B` bead array, then follows the ring through `/N` and
/// `/V` (bounded by a visited set, since a thread's beads form a cycle). Each
/// bead's `/P` is remapped when its target page survived and removed when its
/// target page was dropped, so that a removed page referenced by nothing else
/// is garbage-collected by the subsequent subset sweep
/// ([`crate::subset_prune::prune_after_subset`]). Reference-to-reference chains
/// at every link are normalized through an internal reference-chain resolver
/// before each step is inspected. The function mutates `pdf`
/// in place (same convention as `rebuild_page_tree`) and succeeds silently when
/// the document has no article beads.
///
/// # Errors
///
/// Any error propagated from [`Pdf::resolve`] / [`Pdf::resolve_borrowed`] while
/// resolving the catalog, the `/Threads` array, the threads, the surviving
/// pages, or the beads.
pub fn drop_thread_bead_dangling_p<R: Read + Seek>(
    pdf: &mut Pdf<R>,
    result: &RebuildResult,
) -> Result<()> {
    let surviving: BTreeMap<ObjectRef, ObjectRef> = result
        .ref_map
        .iter()
        .filter_map(|(&old, new_refs)| new_refs.first().map(|&new| (old, new)))
        .collect();

    // Seed the bead walk from every entry point qpdf reaches a ring through:
    // the catalog /Threads article list and each surviving page's /B array.
    let mut queue: Vec<ObjectRef> = Vec::new();
    seed_from_threads(pdf, &mut queue)?;
    seed_from_surviving_pages(pdf, result, &mut queue)?;

    // Walk the ring(s). resolve_ref_chain normalizes /N//V/F indirection so the
    // visited key and the write-back target are the terminal bead ref (never an
    // intermediate reference holder).
    let mut visited: BTreeSet<ObjectRef> = BTreeSet::new();
    while let Some(start_ref) = queue.pop() {
        let (concrete, terminal) = resolve_ref_chain(pdf, &Object::Reference(start_ref))?;
        let bead_ref = terminal.unwrap_or(start_ref);
        if !visited.insert(bead_ref) {
            continue;
        }
        let Some(mut bead) = concrete.into_dict() else {
            continue;
        };
        // Enqueue ring neighbours before any mutation; they are chain-resolved
        // when popped.
        for key in ["N", "V"] {
            if let Some(Object::Reference(r)) = bead.get(key) {
                queue.push(*r);
            }
        }
        if remap_or_drop_bead_p(pdf, &mut bead, &surviving)? {
            pdf.set_object(bead_ref, Object::Dictionary(bead));
        }
    }
    Ok(())
}

/// Push every catalog-`/Threads` thread's first bead (`/F`) onto `queue`.
///
/// `/Threads` (an array of thread dictionaries) may be stored as an indirect
/// reference; each entry may be an indirect reference to a thread dictionary or
/// a direct (inline) one. Returns silently when there is no catalog or no
/// `/Threads`.
fn seed_from_threads<R: Read + Seek>(pdf: &mut Pdf<R>, queue: &mut Vec<ObjectRef>) -> Result<()> {
    let Some(catalog_ref) = pdf.root_ref() else {
        return Ok(()); // No catalog.
    };
    let threads_val = {
        let catalog_obj = pdf.resolve_borrowed(catalog_ref)?;
        let Some(catalog) = catalog_obj.as_dict() else {
            return Ok(());
        };
        // Shared borrow of the catalog: clone the (small) /Threads value out.
        catalog.get("Threads").cloned()
    };
    let Some(threads_val) = threads_val else {
        return Ok(()); // No article threads.
    };
    // /Threads may be an indirect (possibly multi-hop) reference to the array.
    let (threads_concrete, _) = resolve_ref_chain(pdf, &threads_val)?;
    let Object::Array(threads) = threads_concrete else {
        return Ok(());
    };
    for thread in &threads {
        if let Some(first_bead) = thread_first_bead(pdf, thread)? {
            queue.push(first_bead);
        }
    }
    Ok(())
}

/// Resolve a `/Threads` entry to its thread dictionary and return the terminal
/// ref of its `/F` (first bead), if any.
///
/// The entry may be an indirect reference (chain) to a thread dictionary or a
/// direct (inline) dictionary; `/F` may itself be a reference chain.
fn thread_first_bead<R: Read + Seek>(
    pdf: &mut Pdf<R>,
    thread: &Object,
) -> Result<Option<ObjectRef>> {
    let (concrete, _) = resolve_ref_chain(pdf, thread)?;
    let Some(dict) = concrete.as_dict() else {
        return Ok(None);
    };
    let Some(f_val) = dict.get("F") else {
        return Ok(None);
    };
    let (_, terminal) = resolve_ref_chain(pdf, f_val)?;
    Ok(terminal)
}

/// Push the beads listed in each surviving page's `/B` array onto `queue`.
///
/// The surviving pages are `result.new_kids` (deduplicated, since a duplicated
/// selection lists a page more than once). `/B` may be an indirect reference to
/// the array. Beads on removed pages are still reached from here through the
/// ring's `/N`/`/V` links during the walk.
fn seed_from_surviving_pages<R: Read + Seek>(
    pdf: &mut Pdf<R>,
    result: &RebuildResult,
    queue: &mut Vec<ObjectRef>,
) -> Result<()> {
    let mut seen_pages: BTreeSet<ObjectRef> = BTreeSet::new();
    for &page_ref in &result.new_kids {
        if !seen_pages.insert(page_ref) {
            continue;
        }
        let b_val = {
            let page_obj = pdf.resolve_borrowed(page_ref)?;
            page_obj.as_dict().and_then(|p| p.get("B")).cloned()
        };
        let Some(b_val) = b_val else {
            continue;
        };
        let (b_concrete, _) = resolve_ref_chain(pdf, &b_val)?;
        if let Object::Array(beads) = b_concrete {
            for bead in &beads {
                if let Some(r) = bead.as_ref_id() {
                    queue.push(r);
                }
            }
        }
    }
    Ok(())
}

/// Remap-or-drop a bead's `/P`. Returns `true` when `bead` was modified (so the
/// caller writes it back).
///
/// `/P` is by spec an indirect reference to the page the bead belongs to,
/// possibly through a reference chain. The chain is resolved to its terminal
/// page ref; a `/P` that resolves to a live non-page object (a non-reference,
/// or a non-page target) is malformed and left unchanged. A `/P` resolving to
/// `null` *is* treated as a removed page and dropped (a removed page kept alive
/// by a surviving outline / named destination is nulled in place by the earlier
/// null-out pass). A surviving target is remapped to its new ref when the
/// rebuild changed it; a removed target has the key dropped so the page is
/// garbage-collected.
fn remap_or_drop_bead_p<R: Read + Seek>(
    pdf: &mut Pdf<R>,
    bead: &mut Dictionary,
    surviving: &BTreeMap<ObjectRef, ObjectRef>,
) -> Result<bool> {
    let Some(p_val) = bead.get("P").cloned() else {
        return Ok(false);
    };
    let (p_concrete, p_terminal) = resolve_ref_chain(pdf, &p_val)?;
    let Some(page_ref) = p_terminal else {
        return Ok(false); // Non-reference /P: malformed, left unchanged.
    };
    // A removed page that a surviving outline / named destination still
    // references is replaced with `null` *in place* by the earlier null-out pass
    // ([`crate::outline_dest_remap`], Step 4) before this pass (Step 6) runs, so
    // its /P resolves to `null` here rather than to a /Type /Page dict. That is
    // still a removed page and its /P must be dropped (qpdf parity). Only the
    // null-out pass nulls objects before this pass runs — the other extraction
    // passes drop keys, not objects — so a `null` terminal here unambiguously
    // means a removed page.
    if !is_page_dict(&p_concrete) && !matches!(p_concrete, Object::Null) {
        return Ok(false); // /P does not resolve to a page (or null): left unchanged.
    }
    match surviving.get(&page_ref) {
        Some(&new) if new != page_ref => {
            bead.insert("P", Object::Reference(new));
            Ok(true)
        }
        Some(_) => Ok(false), // Surviving under the same ref: nothing to change.
        None => {
            bead.remove("P");
            Ok(true)
        }
    }
}

/// `true` when `obj` is a `<< /Type /Page ... >>` dictionary.
fn is_page_dict(obj: &Object) -> bool {
    obj.as_dict()
        .and_then(|d| d.get("Type"))
        .is_some_and(|t| matches!(t, Object::Name(n) if n == b"Page"))
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::Pdf;
    use std::collections::BTreeMap;
    use std::io::Cursor;

    /// Serialize `objs` (object number → body) into a classic-xref PDF with
    /// `/Root 1 0 R`.
    fn build_pdf(objs: &BTreeMap<u32, String>) -> Vec<u8> {
        build_pdf_inner(objs, true)
    }

    /// Like [`build_pdf`] but writes a trailer with no `/Root` when
    /// `with_root` is false (so `root_ref()` is `None`).
    fn build_pdf_inner(objs: &BTreeMap<u32, String>, with_root: bool) -> Vec<u8> {
        let mut raw: Vec<u8> = b"%PDF-1.5\n".to_vec();
        let mut offs: BTreeMap<u32, usize> = BTreeMap::new();
        for (n, body) in objs {
            offs.insert(*n, raw.len());
            raw.extend_from_slice(format!("{n} 0 obj\n{body}\nendobj\n").as_bytes());
        }
        let max_num = *objs.keys().max().unwrap();
        let xref_pos = raw.len();
        raw.extend_from_slice(format!("xref\n0 {}\n0000000000 65535 f \n", max_num + 1).as_bytes());
        for i in 1..=max_num {
            if let Some(&off) = offs.get(&i) {
                raw.extend_from_slice(format!("{off:010} 00000 n \n").as_bytes());
            } else {
                raw.extend_from_slice(b"0000000000 65535 f \n");
            }
        }
        let root = if with_root { " /Root 1 0 R" } else { "" };
        raw.extend_from_slice(
            format!(
                "trailer\n<< /Size {}{root} >>\nstartxref\n{xref_pos}\n%%EOF\n",
                max_num + 1
            )
            .as_bytes(),
        );
        raw
    }

    /// Base skeleton: catalog (1) with `/Threads [10 0 R]`, pages root (2),
    /// three pages (3, 4, 5) each carrying a `/B` bead array, a thread (10)
    /// whose `/F` is bead 11, and a 3-bead ring 11→12→13 (via `/N`) where bead
    /// 11 is on page 3, bead 12 on page 4, bead 13 on page 5.
    fn base_objs() -> BTreeMap<u32, String> {
        let mut objs: BTreeMap<u32, String> = BTreeMap::new();
        objs.insert(
            1,
            "<< /Type /Catalog /Pages 2 0 R /Threads [10 0 R] >>".into(),
        );
        objs.insert(
            2,
            "<< /Type /Pages /Kids [3 0 R 4 0 R 5 0 R] /Count 3 >>".into(),
        );
        objs.insert(
            3,
            "<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792] /B [11 0 R] >>".into(),
        );
        objs.insert(
            4,
            "<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792] /B [12 0 R] >>".into(),
        );
        objs.insert(
            5,
            "<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792] /B [13 0 R] >>".into(),
        );
        objs.insert(10, "<< /Type /Thread /F 11 0 R >>".into());
        objs.insert(
            11,
            "<< /Type /Bead /T 10 0 R /N 12 0 R /V 13 0 R /P 3 0 R /R [0 0 100 100] >>".into(),
        );
        objs.insert(
            12,
            "<< /Type /Bead /T 10 0 R /N 13 0 R /V 11 0 R /P 4 0 R /R [0 0 100 100] >>".into(),
        );
        objs.insert(
            13,
            "<< /Type /Bead /T 10 0 R /N 11 0 R /V 12 0 R /P 5 0 R /R [0 0 100 100] >>".into(),
        );
        objs
    }

    /// [`base_objs`] with the pages' `/B` arrays removed, so the only way to
    /// reach the bead ring is through the catalog `/Threads`. Used to isolate
    /// the `/Threads`-seeding branches from the `/B`-seeding fallback.
    fn base_objs_no_b() -> BTreeMap<u32, String> {
        let mut objs = base_objs();
        for n in 3..=5 {
            objs.insert(
                n,
                "<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792] >>".into(),
            );
        }
        objs
    }

    fn open(objs: &BTreeMap<u32, String>) -> Pdf<Cursor<Vec<u8>>> {
        Pdf::open(Cursor::new(build_pdf(objs))).expect("open fixture")
    }

    /// A `RebuildResult` keeping pages 3 and 5 under their original refs
    /// (page 4 removed).
    fn keep_3_and_5() -> RebuildResult {
        let mut ref_map: BTreeMap<ObjectRef, Vec<ObjectRef>> = BTreeMap::new();
        ref_map.insert(ObjectRef::new(3, 0), vec![ObjectRef::new(3, 0)]);
        ref_map.insert(ObjectRef::new(5, 0), vec![ObjectRef::new(5, 0)]);
        RebuildResult {
            new_kids: vec![ObjectRef::new(3, 0), ObjectRef::new(5, 0)],
            ref_map,
            ..Default::default()
        }
    }

    fn bead_dict(pdf: &mut Pdf<Cursor<Vec<u8>>>, num: u32) -> Dictionary {
        pdf.resolve(ObjectRef::new(num, 0))
            .expect("resolve bead")
            .into_dict()
            .expect("bead object is a dictionary")
    }

    #[test]
    fn removed_bead_p_dropped_and_bead_kept() {
        // Keep pages 3 and 5; page 4 removed. Bead 12 (on page 4) loses /P; the
        // bead itself and its ring links stay. Beads 11/13 keep their /P.
        let mut pdf = open(&base_objs());
        drop_thread_bead_dangling_p(&mut pdf, &keep_3_and_5()).expect("bead /P drop");

        let bead12 = bead_dict(&mut pdf, 12);
        let p12 = bead12.get("P");
        assert!(
            p12.is_none(),
            "bead 12 /P (removed page) must be dropped, got {p12:?}"
        );
        // Ring links, thread back-pointer, and rectangle are retained.
        let n12 = bead12.get("N");
        assert!(
            matches!(n12, Some(Object::Reference(r)) if r.number == 13),
            "bead 12 /N must be kept, got {n12:?}"
        );
        let v12 = bead12.get("V");
        assert!(
            matches!(v12, Some(Object::Reference(r)) if r.number == 11),
            "bead 12 /V must be kept, got {v12:?}"
        );
        assert!(bead12.get("T").is_some(), "bead 12 /T must be kept");
        assert!(bead12.get("R").is_some(), "bead 12 /R must be kept");

        // Beads on surviving pages keep their /P.
        let bead11 = bead_dict(&mut pdf, 11);
        let p11 = bead11.get("P");
        assert!(
            matches!(p11, Some(Object::Reference(r)) if r.number == 3),
            "bead 11 /P (surviving page 3) must be kept, got {p11:?}"
        );
        let bead13 = bead_dict(&mut pdf, 13);
        let p13 = bead13.get("P");
        assert!(
            matches!(p13, Some(Object::Reference(r)) if r.number == 5),
            "bead 13 /P (surviving page 5) must be kept, got {p13:?}"
        );
    }

    #[test]
    fn surviving_bead_p_remapped_to_new_ref() {
        // Defensive invariant: when a surviving page's first new ref differs
        // from its original (ref_map[old][0] != old), a bead /P pointing at it
        // must be REMAPPED to that new ref, not dropped. A single-document
        // `rebuild_page_tree` never produces this (it keeps the first occurrence
        // under the original ref, page_tree_rebuild.rs), so this fixture builds
        // the RebuildResult by hand to exercise the otherwise-unreachable remap
        // arm and pin the qpdf first-occurrence rule for a future cross-doc path.
        let mut pdf = open(&base_objs());
        let mut ref_map: BTreeMap<ObjectRef, Vec<ObjectRef>> = BTreeMap::new();
        ref_map.insert(ObjectRef::new(3, 0), vec![ObjectRef::new(7, 0)]);
        ref_map.insert(ObjectRef::new(5, 0), vec![ObjectRef::new(5, 0)]);
        let result = RebuildResult {
            new_kids: vec![ObjectRef::new(7, 0), ObjectRef::new(5, 0)],
            ref_map,
            ..Default::default()
        };

        drop_thread_bead_dangling_p(&mut pdf, &result).expect("bead /P remap");

        let bead11 = bead_dict(&mut pdf, 11);
        let p11 = bead11.get("P");
        assert!(
            matches!(p11, Some(Object::Reference(r)) if r.number == 7),
            "bead 11 /P (surviving page under new ref) must be remapped, got {p11:?}"
        );
        // The surviving page under its original ref is left unchanged.
        let bead13 = bead_dict(&mut pdf, 13);
        let p13 = bead13.get("P");
        assert!(
            matches!(p13, Some(Object::Reference(r)) if r.number == 5),
            "bead 13 /P (surviving page, identity) must be kept, got {p13:?}"
        );
    }

    #[test]
    fn duplicate_selection_keeps_bead_p_at_first_occurrence() {
        // The realistic shape a duplicate selection actually produces: page 3 is
        // selected twice, so `rebuild_page_tree` keeps the first occurrence under
        // its original ref and allocates a fresh ref (7 0 R) for the second copy,
        // giving ref_map[3] = [3, 7]. qpdf 11.9.0 points the (single, shared)
        // bead's /P at the FIRST occurrence, and `ref_map[old][0] == old` here, so
        // bead 11's /P must stay at page 3 — the identity arm, never the remap.
        let mut pdf = open(&base_objs());
        let mut ref_map: BTreeMap<ObjectRef, Vec<ObjectRef>> = BTreeMap::new();
        ref_map.insert(
            ObjectRef::new(3, 0),
            vec![ObjectRef::new(3, 0), ObjectRef::new(7, 0)],
        );
        ref_map.insert(ObjectRef::new(5, 0), vec![ObjectRef::new(5, 0)]);
        let result = RebuildResult {
            // Selection order 3,3,5: first copy keeps ref 3, duplicate is 7.
            new_kids: vec![
                ObjectRef::new(3, 0),
                ObjectRef::new(7, 0),
                ObjectRef::new(5, 0),
            ],
            ref_map,
            ..Default::default()
        };

        drop_thread_bead_dangling_p(&mut pdf, &result).expect("duplicate-page bead /P");

        // Bead 11 (on the duplicated page 3) keeps its /P at the first occurrence
        // (ref 3), not the duplicate ref 7 and not dropped — matching qpdf.
        let p11 = bead_dict(&mut pdf, 11).get("P").cloned();
        assert!(
            matches!(p11, Some(Object::Reference(r)) if r.number == 3),
            "a duplicated page's bead /P must stay at the first occurrence (page 3), got {p11:?}"
        );
        // Bead 12 (on the removed page 4) still loses its /P.
        assert!(
            bead_dict(&mut pdf, 12).get("P").is_none(),
            "the removed-page bead /P must still be dropped under a duplicate selection"
        );
    }

    /// Skeleton like [`base_objs`] but with a fourth, bead-less page (6) so a
    /// selection can keep a page while every bead targets a removed page.
    fn objs_with_beadless_page() -> BTreeMap<u32, String> {
        let mut objs = base_objs();
        objs.insert(
            2,
            "<< /Type /Pages /Kids [3 0 R 4 0 R 5 0 R 6 0 R] /Count 4 >>".into(),
        );
        objs.insert(
            6,
            "<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792] >>".into(),
        );
        objs
    }

    #[test]
    fn all_beads_dangling_keeps_thread_and_ring_and_terminates() {
        // Keep only the bead-less page 6, so every bead (on pages 3/4/5) targets
        // a removed page. qpdf keeps the thread and every bead, dropping each
        // bead's /P. The cyclic ring (11→12→13→11) must terminate via `visited`.
        let mut pdf = open(&objs_with_beadless_page());
        let mut ref_map: BTreeMap<ObjectRef, Vec<ObjectRef>> = BTreeMap::new();
        ref_map.insert(ObjectRef::new(6, 0), vec![ObjectRef::new(6, 0)]);
        let result = RebuildResult {
            new_kids: vec![ObjectRef::new(6, 0)],
            ref_map,
            ..Default::default()
        };

        drop_thread_bead_dangling_p(&mut pdf, &result).expect("all-dangling drop");

        for num in [11, 12, 13] {
            let bead = bead_dict(&mut pdf, num);
            let p = bead.get("P");
            assert!(
                p.is_none(),
                "bead {num} /P must be dropped (all dangling), got {p:?}"
            );
            // Ring links survive so the thread stays traversable.
            assert!(bead.get("N").is_some(), "bead {num} /N must be kept");
            assert!(bead.get("V").is_some(), "bead {num} /V must be kept");
        }
        // The thread itself is retained with its /F first-bead pointer.
        let thread = bead_dict(&mut pdf, 10);
        let f = thread.get("F");
        assert!(
            matches!(f, Some(Object::Reference(r)) if r.number == 11),
            "thread /F must be kept, got {f:?}"
        );
    }

    #[test]
    fn seeds_from_surviving_page_b_without_threads() {
        // No catalog /Threads, but the kept pages' /B arrays reach the ring. The
        // removed-page bead must still lose its /P (qpdf 11.9.0 parity), or the
        // removed page would stay reachable via the kept page's /B ring.
        let mut objs = base_objs();
        objs.insert(1, "<< /Type /Catalog /Pages 2 0 R >>".into());
        let mut pdf = open(&objs);

        drop_thread_bead_dangling_p(&mut pdf, &keep_3_and_5()).expect("/B seeding");

        let p12 = bead_dict(&mut pdf, 12).get("P").cloned();
        assert!(
            p12.is_none(),
            "bead reached only via a surviving page's /B must have its dangling /P dropped, got {p12:?}"
        );
        // A surviving bead reached the same way keeps its /P.
        let p11 = bead_dict(&mut pdf, 11).get("P").cloned();
        assert!(
            matches!(p11, Some(Object::Reference(r)) if r.number == 3),
            "surviving bead /P reached via /B must be kept, got {p11:?}"
        );
    }

    #[test]
    fn direct_thread_dict_in_threads_is_processed() {
        // /Threads holds a DIRECT (inline) thread dictionary, and the pages have
        // no /B, so the only entry point is the direct dict. Its ring's
        // removed-page bead must still lose its /P.
        let mut objs = base_objs_no_b();
        objs.insert(
            1,
            "<< /Type /Catalog /Pages 2 0 R /Threads [ << /Type /Thread /F 11 0 R >> ] >>".into(),
        );
        objs.remove(&10); // the inline thread replaces the indirect one
        let mut pdf = open(&objs);

        drop_thread_bead_dangling_p(&mut pdf, &keep_3_and_5()).expect("direct thread dict");

        let p12 = bead_dict(&mut pdf, 12).get("P").cloned();
        assert!(
            p12.is_none(),
            "a direct (inline) thread dictionary's dangling bead /P must be dropped, got {p12:?}"
        );
    }

    #[test]
    fn bead_p_reference_chain_is_resolved() {
        // Bead 12's /P is a reference-to-reference chain to the removed page 4;
        // bead 11's /P is a chain to the surviving page 3. The chain must be
        // resolved before classifying: 12 dropped, 11 kept.
        let mut objs = base_objs_no_b();
        objs.insert(
            11,
            "<< /Type /Bead /T 10 0 R /N 12 0 R /V 13 0 R /P 21 0 R /R [0 0 100 100] >>".into(),
        );
        objs.insert(
            12,
            "<< /Type /Bead /T 10 0 R /N 13 0 R /V 11 0 R /P 20 0 R /R [0 0 100 100] >>".into(),
        );
        objs.insert(20, "4 0 R".into()); // chain → removed page 4
        objs.insert(21, "3 0 R".into()); // chain → surviving page 3
        let mut pdf = open(&objs);

        drop_thread_bead_dangling_p(&mut pdf, &keep_3_and_5()).expect("/P chain");

        let p12 = bead_dict(&mut pdf, 12).get("P").cloned();
        assert!(
            p12.is_none(),
            "a chained /P to a removed page must be dropped, got {p12:?}"
        );
        let p11 = bead_dict(&mut pdf, 11).get("P").cloned();
        assert!(
            matches!(p11, Some(Object::Reference(r)) if r.number == 21),
            "a chained /P to a surviving page must be kept verbatim, got {p11:?}"
        );
    }

    #[test]
    fn ring_neighbour_reference_chain_is_followed() {
        // Bead 11's /N points at object 22, whose value is the real bead 12
        // reference (a ref-to-ref ring link). With no /B fallback the removed
        // bead 12 is reachable only through this chained /N; it must still be
        // processed.
        let mut objs = base_objs_no_b();
        objs.insert(
            11,
            "<< /Type /Bead /T 10 0 R /N 22 0 R /V 13 0 R /P 3 0 R /R [0 0 100 100] >>".into(),
        );
        objs.insert(22, "12 0 R".into());
        let mut pdf = open(&objs);

        drop_thread_bead_dangling_p(&mut pdf, &keep_3_and_5()).expect("/N chain");

        let p12 = bead_dict(&mut pdf, 12).get("P").cloned();
        assert!(
            p12.is_none(),
            "a bead reached only through a chained /N must have its dangling /P dropped, got {p12:?}"
        );
    }

    #[test]
    fn threads_multi_hop_reference_chain_is_resolved() {
        // /Threads → 14 → 15 → [10 0 R] (two-hop chain). No /B fallback, so the
        // removed-page bead is reachable only by resolving the chain.
        let mut objs = base_objs_no_b();
        objs.insert(
            1,
            "<< /Type /Catalog /Pages 2 0 R /Threads 14 0 R >>".into(),
        );
        objs.insert(14, "15 0 R".into());
        objs.insert(15, "[10 0 R]".into());
        let mut pdf = open(&objs);

        drop_thread_bead_dangling_p(&mut pdf, &keep_3_and_5()).expect("multi-hop /Threads");

        let p12 = bead_dict(&mut pdf, 12).get("P").cloned();
        assert!(
            p12.is_none(),
            "a thread reached through a multi-hop /Threads chain must be walked, got {p12:?}"
        );
    }

    #[test]
    fn non_dict_thread_entry_and_thread_without_f_skipped() {
        // /Threads holds a direct non-dictionary entry (42 — skipped), the real
        // thread 10, and a second thread 15 with no /F (skipped). No /B, so only
        // thread 10 reaches the ring.
        let mut objs = base_objs_no_b();
        objs.insert(
            1,
            "<< /Type /Catalog /Pages 2 0 R /Threads [42 10 0 R 15 0 R] >>".into(),
        );
        objs.insert(15, "<< /Type /Thread >>".into());
        let mut pdf = open(&objs);

        drop_thread_bead_dangling_p(&mut pdf, &keep_3_and_5()).expect("mixed /Threads");

        let p12 = bead_dict(&mut pdf, 12).get("P").cloned();
        assert!(
            p12.is_none(),
            "the real thread's dangling bead /P must still be dropped, got {p12:?}"
        );
    }

    #[test]
    fn thread_f_non_reference_is_skipped() {
        // Thread 10's /F is a non-reference (integer): no first bead, skipped.
        // No /B, so nothing reaches the ring and beads are untouched.
        let mut objs = base_objs_no_b();
        objs.insert(10, "<< /Type /Thread /F 0 >>".into());
        let mut pdf = open(&objs);

        drop_thread_bead_dangling_p(&mut pdf, &keep_3_and_5()).expect("non-ref /F");

        assert!(
            bead_dict(&mut pdf, 12).get("P").is_some(),
            "a thread whose /F is not a reference yields no first bead"
        );
    }

    #[test]
    fn non_array_threads_with_no_b_is_a_noop() {
        // A malformed /Threads (not an array, not a ref to one) and no /B: no
        // entry point, so beads are untouched.
        let mut objs = base_objs_no_b();
        objs.insert(1, "<< /Type /Catalog /Pages 2 0 R /Threads 42 >>".into());
        let mut pdf = open(&objs);
        drop_thread_bead_dangling_p(&mut pdf, &keep_3_and_5()).expect("noop");
        assert!(
            bead_dict(&mut pdf, 12).get("P").is_some(),
            "a non-array /Threads with no /B must leave beads untouched"
        );
    }

    #[test]
    fn no_threads_no_b_is_a_noop() {
        // No /Threads and no /B: nothing is seeded, so beads are untouched.
        let mut objs = base_objs_no_b();
        objs.insert(1, "<< /Type /Catalog /Pages 2 0 R >>".into());
        let mut pdf = open(&objs);
        drop_thread_bead_dangling_p(&mut pdf, &keep_3_and_5()).expect("noop");
        assert!(
            bead_dict(&mut pdf, 12).get("P").is_some(),
            "with neither /Threads nor /B, beads are untouched"
        );
    }

    #[test]
    fn surviving_page_b_non_array_is_skipped() {
        // A surviving page's /B is not an array (malformed) and there is no
        // /Threads: nothing is seeded.
        let mut objs = base_objs();
        objs.insert(1, "<< /Type /Catalog /Pages 2 0 R >>".into());
        objs.insert(
            3,
            "<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792] /B 99 >>".into(),
        );
        objs.insert(
            5,
            "<< /Type /Page /Parent 2 0 R /MediaBox [0 0 612 792] /B 99 >>".into(),
        );
        let mut pdf = open(&objs);
        drop_thread_bead_dangling_p(&mut pdf, &keep_3_and_5()).expect("noop");
        assert!(
            bead_dict(&mut pdf, 12).get("P").is_some(),
            "a non-array /B must be ignored"
        );
    }

    #[test]
    fn malformed_non_ref_p_left_unchanged() {
        // A bead whose /P is not an indirect reference (malformed) is left as-is.
        let mut objs = base_objs();
        objs.insert(
            12,
            "<< /Type /Bead /T 10 0 R /N 13 0 R /V 11 0 R /P 999 /R [0 0 100 100] >>".into(),
        );
        let mut pdf = open(&objs);

        drop_thread_bead_dangling_p(&mut pdf, &keep_3_and_5()).expect("malformed /P");

        let p12 = bead_dict(&mut pdf, 12).get("P").cloned();
        assert!(
            matches!(p12, Some(Object::Integer(999))),
            "a non-reference /P must be left unchanged, got {p12:?}"
        );
    }

    #[test]
    fn p_resolving_to_non_page_left_unchanged() {
        // Bead 12's /P points at a non-page object (not in `surviving`, but not
        // a page either): it must be left unchanged, not dropped.
        let mut objs = base_objs();
        objs.insert(
            12,
            "<< /Type /Bead /T 10 0 R /N 13 0 R /V 11 0 R /P 30 0 R /R [0 0 100 100] >>".into(),
        );
        objs.insert(30, "<< /Type /Whatever >>".into());
        let mut pdf = open(&objs);

        drop_thread_bead_dangling_p(&mut pdf, &keep_3_and_5()).expect("non-page /P");

        let p12 = bead_dict(&mut pdf, 12).get("P").cloned();
        assert!(
            matches!(p12, Some(Object::Reference(r)) if r.number == 30),
            "a /P resolving to a non-page object must be left unchanged, got {p12:?}"
        );
    }

    #[test]
    fn bead_p_to_nulled_removed_page_still_dropped() {
        // A removed page that a surviving outline / named destination still
        // references is replaced with `null` IN PLACE by the earlier null-out
        // pass (crate::outline_dest_remap, pipeline Step 4) BEFORE this pass
        // (Step 6) runs. The bead's /P then resolves to Object::Null rather than
        // a /Type /Page dict — but it is still a removed page, and qpdf drops the
        // bead's /P. Object 4 is `null` and is not in `surviving`, so /P must be
        // dropped (matching qpdf; requiring /Type /Page here would wrongly keep
        // the dangling /P). Mirrors objr_obj_annot_p's
        // `p_to_nulled_removed_page_still_dropped`.
        let mut objs = base_objs();
        objs.insert(4, "null".into());
        let mut pdf = open(&objs);

        drop_thread_bead_dangling_p(&mut pdf, &keep_3_and_5()).expect("nulled-page /P drop");

        let p12 = bead_dict(&mut pdf, 12).get("P").cloned();
        assert!(
            p12.is_none(),
            "a bead /P to a removed page nulled by the dest null-out pass must still be dropped, got {p12:?}"
        );
        // Beads on surviving pages are unaffected.
        let p11 = bead_dict(&mut pdf, 11).get("P").cloned();
        assert!(
            matches!(p11, Some(Object::Reference(r)) if r.number == 3),
            "surviving-page bead /P must be kept, got {p11:?}"
        );
    }

    #[test]
    fn bead_without_p_is_left_unchanged() {
        // A bead that carries no /P at all is walked (for its ring links) but
        // needs no change.
        let mut objs = base_objs();
        objs.insert(
            12,
            "<< /Type /Bead /T 10 0 R /N 13 0 R /V 11 0 R /R [0 0 100 100] >>".into(),
        );
        let mut pdf = open(&objs);

        drop_thread_bead_dangling_p(&mut pdf, &keep_3_and_5()).expect("bead without /P");

        let bead12 = bead_dict(&mut pdf, 12);
        assert!(bead12.get("P").is_none(), "bead 12 still has no /P");
        // The rest of the ring is still processed (bead 11 kept, 13 kept).
        assert!(
            bead_dict(&mut pdf, 11).get("P").is_some(),
            "the rest of the ring is still walked"
        );
    }

    #[test]
    fn non_dict_bead_in_ring_skipped() {
        // A /N neighbour that resolves to a non-dictionary is skipped without
        // error; the rest of the ring is still processed. No /B, so the chained
        // entry is the thread /F.
        let mut objs = base_objs_no_b();
        objs.insert(
            11,
            "<< /Type /Bead /T 10 0 R /N 16 0 R /V 13 0 R /P 3 0 R /R [0 0 100 100] >>".into(),
        );
        objs.insert(16, "42".into());
        // Thread /F points at bead 12 directly so the removed-page bead is still
        // reached even though the 11→16 link is broken.
        objs.insert(10, "<< /Type /Thread /F 12 0 R >>".into());
        let mut pdf = open(&objs);

        drop_thread_bead_dangling_p(&mut pdf, &keep_3_and_5()).expect("non-dict neighbour");

        assert!(
            bead_dict(&mut pdf, 12).get("P").is_none(),
            "bead 12 dangling /P must be dropped despite a non-dict ring neighbour"
        );
    }

    #[test]
    fn non_dict_catalog_still_seeds_from_b() {
        // /Root resolves to a non-dictionary: the /Threads walk bails out, but
        // the /B seeding (independent of the catalog) still drops the dangling
        // bead /P.
        let mut objs = base_objs();
        objs.insert(1, "42".into());
        let mut pdf = open(&objs);
        drop_thread_bead_dangling_p(&mut pdf, &keep_3_and_5()).expect("non-dict catalog");
        assert!(
            bead_dict(&mut pdf, 12).get("P").is_none(),
            "a non-dictionary catalog still permits /B-seeded bead /P drop"
        );
    }

    #[test]
    fn no_root_still_seeds_from_b() {
        // A trailer without /Root: root_ref() is None, so the /Threads walk
        // bails out, but /B seeding (driven by the rebuild result, not the
        // catalog) still drops the dangling bead /P.
        let mut objs = base_objs();
        objs.remove(&1); // drop the catalog
        let raw = build_pdf_inner(&objs, false);
        let mut pdf = Pdf::open(Cursor::new(raw)).expect("open no-root fixture");
        assert!(pdf.root_ref().is_none(), "fixture must have no /Root");

        drop_thread_bead_dangling_p(&mut pdf, &keep_3_and_5()).expect("no-root /B seeding");

        assert!(
            bead_dict(&mut pdf, 12).get("P").is_none(),
            "a missing catalog still permits /B-seeded bead /P drop"
        );
    }

    #[test]
    fn non_dict_surviving_page_is_skipped() {
        // A surviving page ref that resolves to a non-dictionary (malformed
        // selection) is skipped during /B seeding without error.
        let mut objs = base_objs();
        objs.insert(1, "<< /Type /Catalog /Pages 2 0 R >>".into());
        objs.insert(3, "42".into()); // surviving "page" is not a dict
        let mut pdf = open(&objs);

        // new_kids lists page 3 (now a non-dict) and page 5; only 5 has a /B.
        drop_thread_bead_dangling_p(&mut pdf, &keep_3_and_5()).expect("non-dict surviving page");

        // Page 5's /B still reaches the ring and drops bead 12's dangling /P.
        assert!(
            bead_dict(&mut pdf, 12).get("P").is_none(),
            "a non-dict surviving page is skipped but the others are still walked"
        );
    }

    #[test]
    fn duplicate_surviving_page_ref_in_new_kids_is_deduped() {
        // new_kids lists the same surviving page ref twice; the /B-seeding dedup
        // must visit each page once. (No /Threads, so /B is the only entry.)
        let mut objs = base_objs();
        objs.insert(1, "<< /Type /Catalog /Pages 2 0 R >>".into());
        let mut pdf = open(&objs);
        let mut ref_map: BTreeMap<ObjectRef, Vec<ObjectRef>> = BTreeMap::new();
        ref_map.insert(ObjectRef::new(3, 0), vec![ObjectRef::new(3, 0)]);
        ref_map.insert(ObjectRef::new(5, 0), vec![ObjectRef::new(5, 0)]);
        let result = RebuildResult {
            new_kids: vec![
                ObjectRef::new(3, 0),
                ObjectRef::new(3, 0),
                ObjectRef::new(5, 0),
            ],
            ref_map,
            ..Default::default()
        };

        drop_thread_bead_dangling_p(&mut pdf, &result).expect("dedup");

        assert!(
            bead_dict(&mut pdf, 12).get("P").is_none(),
            "a duplicated page ref in new_kids must not break /B seeding"
        );
    }
}