use crate::ObjectRef;
use super::plan::LinearizationPlan;
use std::collections::{BTreeMap, BTreeSet};
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RenumberMap {
by_new_number: Vec<ObjectRef>,
by_original: BTreeMap<ObjectRef, ObjectRef>,
param_dict_slot: u32,
hint_stream_slot: u32,
}
const SENTINEL: ObjectRef = ObjectRef {
number: 0,
generation: 0,
};
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct ObjStmRelocation {
pub first_xref_slot: u32,
pub main_xref_slot: u32,
pub container_numbers: Vec<u32>,
}
impl ObjStmRelocation {
pub fn is_empty(&self) -> bool {
self.first_xref_slot == 0 && self.main_xref_slot == 0
}
}
impl RenumberMap {
pub fn from_plan(plan: &LinearizationPlan) -> Self {
assert!(
plan.parts_are_disjoint(),
"LinearizationPlan invariant violated: parts must be disjoint \
(Part 2 ∪ Part 3 ∪ Part 4 must contain each ObjectRef at most once)"
);
let total_parts = plan.part2_objects.len()
+ plan.part3_objects.len()
+ plan.part4_other_pages_private.len()
+ plan.part4_other_pages_shared.len()
+ plan.part4_rest.len();
let capacity = total_parts + 3;
let mut by_new_number: Vec<ObjectRef> = Vec::with_capacity(capacity);
let mut by_original: BTreeMap<ObjectRef, ObjectRef> = BTreeMap::new();
by_new_number.push(SENTINEL);
let push_real = |original: ObjectRef,
by_new_number: &mut Vec<ObjectRef>,
by_original: &mut BTreeMap<ObjectRef, ObjectRef>| {
let new_number = by_new_number.len() as u32;
let new_ref = ObjectRef::new(new_number, 0);
by_new_number.push(original);
assert!(
by_original.insert(original, new_ref).is_none(),
"duplicate original ObjectRef in LinearizationPlan: {original:?}"
);
};
let part4_rest_membership: BTreeSet<ObjectRef> = plan.part4_rest.iter().copied().collect();
let promote = |slot_owner: Option<ObjectRef>,
by_new_number: &mut Vec<ObjectRef>,
by_original: &mut BTreeMap<ObjectRef, ObjectRef>| {
if let Some(r) = slot_owner {
if part4_rest_membership.contains(&r) && !by_original.contains_key(&r) {
push_real(r, by_new_number, by_original);
}
}
};
for &original in &plan.part4_other_pages_private {
push_real(original, &mut by_new_number, &mut by_original);
}
for &original in &plan.part4_other_pages_shared {
push_real(original, &mut by_new_number, &mut by_original);
}
promote(plan.pages_tree_ref, &mut by_new_number, &mut by_original);
promote(plan.info_ref, &mut by_new_number, &mut by_original);
let param_dict_slot = by_new_number.len() as u32;
by_new_number.push(SENTINEL);
promote(plan.root_ref, &mut by_new_number, &mut by_original);
let hint_stream_slot = by_new_number.len() as u32;
by_new_number.push(SENTINEL);
for &original in &plan.part2_objects {
push_real(original, &mut by_new_number, &mut by_original);
}
for &original in &plan.part3_objects {
push_real(original, &mut by_new_number, &mut by_original);
}
for &original in &plan.part4_rest {
if by_original.contains_key(&original) {
continue;
}
push_real(original, &mut by_new_number, &mut by_original);
}
Self {
by_new_number,
by_original,
param_dict_slot,
hint_stream_slot,
}
}
pub fn new_for_original(&self, original: ObjectRef) -> Option<ObjectRef> {
self.by_original.get(&original).copied()
}
pub fn original_for_new(&self, new: ObjectRef) -> Option<ObjectRef> {
if new.generation != 0 {
return None;
}
let idx = new.number as usize;
if idx == 0 || idx >= self.by_new_number.len() {
return None;
}
let stored = self.by_new_number[idx];
if stored.number == 0 {
None
} else {
Some(stored)
}
}
pub fn param_dict_ref(&self) -> ObjectRef {
ObjectRef::new(self.param_dict_slot, 0)
}
pub fn hint_stream_slot(&self) -> u32 {
self.hint_stream_slot
}
pub fn len(&self) -> usize {
self.by_new_number.len() - 1
}
pub fn is_empty(&self) -> bool {
self.by_original.is_empty()
}
pub fn param_dict_slot_is_reserved(&self) -> bool {
matches!(
self.by_new_number.get(self.param_dict_slot as usize),
Some(r) if r.number == 0 && r.generation == 0
)
}
pub fn relocate_objstm_members(&mut self, batches: &[Vec<ObjectRef>]) -> ObjStmRelocation {
if batches.iter().all(|b| b.is_empty()) {
return ObjStmRelocation::default();
}
let member_set: BTreeSet<ObjectRef> =
batches.iter().flat_map(|b| b.iter().copied()).collect();
let old_param_slot = self.param_dict_slot;
let old_hint_slot = self.hint_stream_slot;
let mut new_by_new_number: Vec<ObjectRef> = Vec::with_capacity(self.by_new_number.len());
new_by_new_number.push(SENTINEL); let mut new_param_slot = 0u32;
let mut new_hint_slot = 0u32;
for (old_idx, &original) in self.by_new_number.iter().enumerate().skip(1) {
let old_idx = old_idx as u32;
if old_idx == old_param_slot {
new_param_slot = new_by_new_number.len() as u32;
new_by_new_number.push(SENTINEL);
continue;
}
if old_idx == old_hint_slot {
new_hint_slot = new_by_new_number.len() as u32;
new_by_new_number.push(SENTINEL);
continue;
}
if original.number == 0 {
new_by_new_number.push(SENTINEL);
continue;
}
if member_set.contains(&original) {
continue; }
new_by_new_number.push(original);
}
let first_xref_slot = new_by_new_number.len() as u32;
new_by_new_number.push(SENTINEL);
let main_xref_slot = new_by_new_number.len() as u32;
new_by_new_number.push(SENTINEL);
let mut container_numbers: Vec<u32> = Vec::with_capacity(batches.len());
for batch in batches {
if batch.is_empty() {
continue;
}
let container_num = new_by_new_number.len() as u32;
new_by_new_number.push(SENTINEL); container_numbers.push(container_num);
}
for batch in batches {
for &member in batch {
assert!(
self.by_original.contains_key(&member),
"relocate_objstm_members: member {member:?} not present in RenumberMap \
(planner / renumber inconsistency)"
);
new_by_new_number.push(member);
}
}
let mut new_by_original: BTreeMap<ObjectRef, ObjectRef> = BTreeMap::new();
for (idx, &original) in new_by_new_number.iter().enumerate().skip(1) {
if original.number == 0 {
continue;
}
let prev = new_by_original.insert(original, ObjectRef::new(idx as u32, 0));
assert!(
prev.is_none(),
"relocate_objstm_members: duplicate original {original:?} after relocation"
);
}
self.by_new_number = new_by_new_number;
self.by_original = new_by_original;
self.param_dict_slot = new_param_slot;
self.hint_stream_slot = new_hint_slot;
ObjStmRelocation {
first_xref_slot,
main_xref_slot,
container_numbers,
}
}
pub fn iter_in_layout_order(&self) -> impl Iterator<Item = (ObjectRef, ObjectRef)> + '_ {
self.by_new_number
.iter()
.enumerate()
.skip(1) .filter_map(|(new_number, &original)| {
if original.number == 0 {
None
} else {
Some((ObjectRef::new(new_number as u32, 0), original))
}
})
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::linearization::plan::{LinearizationPlan, PageHintEntry};
fn single_page_plan() -> LinearizationPlan {
LinearizationPlan {
part2_objects: vec![ObjectRef::new(3, 0), ObjectRef::new(2, 0)],
part4_rest: vec![ObjectRef::new(1, 0)],
total_object_count: 3,
root_ref: Some(ObjectRef::new(1, 0)),
page_hints: vec![PageHintEntry::placeholder(ObjectRef::new(3, 0))],
..Default::default()
}
}
fn two_page_plan() -> LinearizationPlan {
LinearizationPlan {
part2_objects: vec![ObjectRef::new(3, 0), ObjectRef::new(6, 0)],
part3_objects: vec![ObjectRef::new(5, 0), ObjectRef::new(8, 0)],
part4_other_pages_private: vec![ObjectRef::new(4, 0), ObjectRef::new(7, 0)],
part4_rest: vec![ObjectRef::new(1, 0), ObjectRef::new(2, 0)],
total_object_count: 8,
root_ref: Some(ObjectRef::new(1, 0)),
..Default::default()
}
}
#[test]
fn param_dict_ref_matches_param_dict_slot() {
let plan = single_page_plan();
let rn = RenumberMap::from_plan(&plan);
assert_eq!(rn.param_dict_ref(), ObjectRef::new(1, 0));
}
#[test]
fn single_page_slot_layout() {
let plan = single_page_plan();
let rn = RenumberMap::from_plan(&plan);
assert_eq!(rn.new_for_original(ObjectRef::new(1, 0)).unwrap().number, 2);
assert_eq!(rn.hint_stream_slot(), 3);
assert_eq!(rn.new_for_original(ObjectRef::new(3, 0)).unwrap().number, 4);
assert_eq!(rn.new_for_original(ObjectRef::new(2, 0)).unwrap().number, 5);
}
#[test]
fn two_page_part_ordering_correct() {
let plan = two_page_plan();
let rn = RenumberMap::from_plan(&plan);
assert_eq!(rn.new_for_original(ObjectRef::new(4, 0)).unwrap().number, 1);
assert_eq!(rn.new_for_original(ObjectRef::new(7, 0)).unwrap().number, 2);
assert_eq!(rn.param_dict_ref().number, 3);
assert_eq!(rn.new_for_original(ObjectRef::new(1, 0)).unwrap().number, 4);
assert_eq!(rn.hint_stream_slot(), 5);
assert_eq!(rn.new_for_original(ObjectRef::new(3, 0)).unwrap().number, 6);
assert_eq!(rn.new_for_original(ObjectRef::new(6, 0)).unwrap().number, 7);
assert_eq!(rn.new_for_original(ObjectRef::new(5, 0)).unwrap().number, 8);
assert_eq!(rn.new_for_original(ObjectRef::new(8, 0)).unwrap().number, 9);
assert_eq!(
rn.new_for_original(ObjectRef::new(2, 0)).unwrap().number,
10
);
}
#[test]
fn reverse_lookup_single_page() {
let plan = single_page_plan();
let rn = RenumberMap::from_plan(&plan);
assert_eq!(
rn.original_for_new(ObjectRef::new(2, 0)),
Some(ObjectRef::new(1, 0))
);
assert_eq!(
rn.original_for_new(ObjectRef::new(4, 0)),
Some(ObjectRef::new(3, 0))
);
assert_eq!(
rn.original_for_new(ObjectRef::new(5, 0)),
Some(ObjectRef::new(2, 0))
);
}
#[test]
fn sentinel_slots_return_none() {
let plan = single_page_plan();
let rn = RenumberMap::from_plan(&plan);
assert_eq!(rn.original_for_new(ObjectRef::new(0, 0)), None);
assert_eq!(
rn.original_for_new(ObjectRef::new(rn.param_dict_ref().number, 0)),
None
);
assert_eq!(
rn.original_for_new(ObjectRef::new(rn.hint_stream_slot(), 0)),
None
);
assert_eq!(rn.original_for_new(ObjectRef::new(99, 0)), None);
}
#[test]
fn uniqueness_no_duplicate_new_refs() {
let plan = two_page_plan();
let rn = RenumberMap::from_plan(&plan);
let mut seen_new: std::collections::BTreeSet<ObjectRef> = std::collections::BTreeSet::new();
for (new_ref, _orig) in rn.iter_in_layout_order() {
assert!(
seen_new.insert(new_ref),
"new ref {:?} appears more than once in layout order",
new_ref
);
}
}
#[test]
fn iter_layout_order_length_equals_plan_total() {
let plan = two_page_plan();
let total =
plan.part2_objects.len() + plan.part3_objects.len() + plan.part4_objects().len();
let rn = RenumberMap::from_plan(&plan);
let iter_len = rn.iter_in_layout_order().count();
assert_eq!(
iter_len, total,
"iter_in_layout_order must yield one entry per plan object"
);
}
#[test]
fn len_includes_param_dict_and_hint_reservations() {
let plan = two_page_plan();
let total =
plan.part2_objects.len() + plan.part3_objects.len() + plan.part4_objects().len();
let rn = RenumberMap::from_plan(&plan);
assert_eq!(
rn.len(),
total + 2,
"len() must be total objects + 2 for the param dict and hint stream slots"
);
}
#[test]
fn deterministic_from_same_plan() {
let plan = two_page_plan();
let rn1 = RenumberMap::from_plan(&plan);
let rn2 = RenumberMap::from_plan(&plan);
assert_eq!(rn1, rn2, "RenumberMap must be deterministic");
}
#[test]
fn iter_layout_order_is_ascending() {
let plan = two_page_plan();
let rn = RenumberMap::from_plan(&plan);
let new_numbers: Vec<u32> = rn.iter_in_layout_order().map(|(r, _)| r.number).collect();
let mut sorted = new_numbers.clone();
sorted.sort_unstable();
assert_eq!(
new_numbers, sorted,
"iter_in_layout_order must yield ascending new numbers"
);
}
#[test]
fn new_refs_have_generation_zero() {
let plan = two_page_plan();
let rn = RenumberMap::from_plan(&plan);
for (new_ref, _orig) in rn.iter_in_layout_order() {
assert_eq!(
new_ref.generation, 0,
"all new object refs must have generation 0"
);
}
}
#[test]
fn original_for_new_rejects_non_zero_generation() {
let plan = single_page_plan();
let rn = RenumberMap::from_plan(&plan);
assert_eq!(rn.original_for_new(ObjectRef::new(2, 1)), None);
assert_eq!(rn.original_for_new(ObjectRef::new(4, 99)), None);
assert_eq!(
rn.original_for_new(ObjectRef::new(4, 0)),
Some(ObjectRef::new(3, 0))
);
}
#[test]
fn param_dict_slot_is_reserved_after_from_plan() {
let plan = single_page_plan();
let rn = RenumberMap::from_plan(&plan);
assert!(rn.param_dict_slot_is_reserved());
}
#[test]
fn param_dict_slot_is_reserved_returns_false_when_overwritten() {
let plan = single_page_plan();
let mut rn = RenumberMap::from_plan(&plan);
let slot = rn.param_dict_ref().number as usize;
rn.by_new_number[slot] = ObjectRef::new(99, 0);
assert!(!rn.param_dict_slot_is_reserved());
}
#[test]
fn hint_stream_slot_points_to_unused_slot() {
let plan = two_page_plan();
let rn = RenumberMap::from_plan(&plan);
let h = rn.hint_stream_slot();
assert!(rn.original_for_new(ObjectRef::new(h, 0)).is_none());
assert_eq!(h, 5);
}
#[test]
fn qpdf_layout_pages_info_paramdict_catalog_hint_part2() {
let pages_ref = ObjectRef::new(8, 0);
let info_ref = ObjectRef::new(7, 0);
let catalog_ref = ObjectRef::new(6, 0);
let other_part4 = ObjectRef::new(9, 0);
let plan = LinearizationPlan {
part2_objects: vec![ObjectRef::new(2, 0)],
part4_rest: vec![catalog_ref, info_ref, pages_ref, other_part4],
total_object_count: 5,
root_ref: Some(catalog_ref),
pages_tree_ref: Some(pages_ref),
info_ref: Some(info_ref),
..Default::default()
};
let rn = RenumberMap::from_plan(&plan);
assert_eq!(rn.new_for_original(pages_ref).unwrap().number, 1);
assert_eq!(rn.new_for_original(info_ref).unwrap().number, 2);
assert_eq!(rn.param_dict_ref().number, 3);
assert_eq!(rn.new_for_original(catalog_ref).unwrap().number, 4);
assert_eq!(rn.hint_stream_slot(), 5);
assert_eq!(rn.new_for_original(ObjectRef::new(2, 0)).unwrap().number, 6);
assert_eq!(rn.new_for_original(other_part4).unwrap().number, 7);
}
#[test]
fn missing_promotion_refs_shift_param_and_hint_slots_earlier() {
let plan = single_page_plan(); let rn = RenumberMap::from_plan(&plan);
assert_eq!(rn.param_dict_ref().number, 1);
assert_eq!(rn.new_for_original(ObjectRef::new(1, 0)).unwrap().number, 2);
assert_eq!(rn.hint_stream_slot(), 3);
}
#[test]
fn promotion_skips_refs_not_in_part4_rest() {
let pages_ref = ObjectRef::new(10, 0);
let plan = LinearizationPlan {
part2_objects: vec![pages_ref, ObjectRef::new(2, 0)],
part4_rest: vec![ObjectRef::new(3, 0)],
total_object_count: 3,
pages_tree_ref: Some(pages_ref), ..Default::default()
};
let rn = RenumberMap::from_plan(&plan);
assert_eq!(rn.param_dict_ref().number, 1);
assert_eq!(rn.hint_stream_slot(), 2);
assert_eq!(rn.new_for_original(pages_ref).unwrap().number, 3);
assert_eq!(rn.new_for_original(ObjectRef::new(2, 0)).unwrap().number, 4);
assert_eq!(rn.new_for_original(ObjectRef::new(3, 0)).unwrap().number, 5);
}
#[test]
#[should_panic(expected = "parts must be disjoint")]
fn from_plan_panics_on_duplicate_in_part4_even_in_release() {
let dup = ObjectRef::new(5, 0);
let plan = LinearizationPlan {
part2_objects: vec![ObjectRef::new(2, 0)],
part4_other_pages_private: vec![dup],
part4_rest: vec![dup],
total_object_count: 3,
root_ref: Some(dup),
pages_tree_ref: Some(dup),
..Default::default()
};
let _ = RenumberMap::from_plan(&plan);
}
#[test]
fn relocate_orders_all_containers_before_all_members() {
let plan = two_page_plan();
let mut rn = RenumberMap::from_plan(&plan);
let batches = vec![
vec![ObjectRef::new(5, 0)],
vec![ObjectRef::new(4, 0), ObjectRef::new(7, 0)],
];
let relocation = rn.relocate_objstm_members(&batches);
assert_eq!(
relocation.container_numbers.len(),
2,
"two non-empty batches must yield two container numbers"
);
let c0 = relocation.container_numbers[0];
let c1 = relocation.container_numbers[1];
let members: Vec<u32> = batches
.iter()
.flatten()
.map(|&m| rn.new_for_original(m).unwrap().number)
.collect();
let max_container = c0.max(c1);
let min_member = *members.iter().min().unwrap();
assert!(
max_container < min_member,
"all containers ({c0}, {c1}) must precede all members ({members:?})"
);
assert_eq!(
c1,
c0 + 1,
"container slots must be contiguous, batch-ordered"
);
assert!(
relocation.main_xref_slot < c0,
"main xref slot ({}) must precede the container block ({c0})",
relocation.main_xref_slot
);
}
}