pdfrum_edit/content/
resource.rs

1//! Naming the resources a regenerated stream refers to (ISO 32000-1 §7.8.3).
2//!
3//! A content stream cannot hold a font, an image or a graphics-state
4//! dictionary; it holds a *name*, and the page's `/Resources` says what the
5//! name means. So regenerating a stream means allocating names, and the rules
6//! for that are load-bearing rather than cosmetic: the oracle's own regenerated
7//! page allocates the same names in the same order, and conformance compares
8//! the two.
9//!
10//! # `FX` plus one letter plus a number, restarting at one every time
11//!
12//! A name is `FX` + the category's first letter + a number: `FXF1` for a font,
13//! `FXX1` for an image *or* a form — both live in `/XObject` — and `FXE1` for
14//! a graphics state. The search restarts at 1 on **every** call and takes the
15//! first free slot, so it is not a counter: allocate three names and free the
16//! second, and the next allocation reuses the middle number.
17//!
18//! # Removed entries still reserve their names
19//!
20//! An entry the sweep removed is parked rather than dropped, because a later
21//! regeneration may need it back. A parked name is therefore *not* free — a
22//! fresh allocation skips it, or restoring the parked entry would collide with
23//! whatever took its name.
24//!
25//! # Only three categories exist here
26//!
27//! `/ExtGState`, `/Font` and `/XObject`. Colour spaces, patterns, shadings,
28//! `/Properties` and `/ProcSet` are neither created, swept, nor preserved —
29//! which is a real gap, and one we keep: a regenerated stream never refers to
30//! any of them, because the emitter never writes an operator that would.
31
32use std::collections::{BTreeMap, BTreeSet};
33
34use pdfrum_object::{Dict, Name, ObjRef, Object};
35
36/// The three resource categories a regenerated page maintains.
37///
38/// In the order the C++ sweeps them, which is the order removals are recorded
39/// in and therefore the order a re-run reallocates in.
40pub(crate) const CATEGORIES: [&str; 3] = ["ExtGState", "Font", "XObject"];
41
42/// The resource dictionaries of one page, while its streams are regenerated.
43///
44/// Holds the sub-dictionary per category plus the entries a previous sweep
45/// parked, so a name allocation can avoid both. A plain record: the four
46/// functions below are the operations.
47#[derive(Debug, Clone, Default)]
48pub struct ResourceTable {
49    /// The live entries, per category, in insertion order.
50    entries: BTreeMap<String, Dict>,
51    /// Entries a sweep removed, per category. They still reserve their names.
52    parked: BTreeMap<String, BTreeMap<Name, Object>>,
53}
54
55impl ResourceTable {
56    /// Read the three categories out of a page's `/Resources`.
57    ///
58    /// Every other key — colour spaces, patterns, `/ProcSet` — is left where
59    /// it is and carried through untouched.
60    #[must_use]
61    pub fn load(resources: &Dict, r: &impl pdfrum_object::Resolve) -> Self {
62        let mut entries = BTreeMap::new();
63        for category in CATEGORIES {
64            let key = Name::from(category);
65            if let Some(dict) = resources.dict(&key, r) {
66                entries.insert(category.to_owned(), dict);
67            }
68        }
69        Self {
70            entries,
71            parked: BTreeMap::new(),
72        }
73    }
74
75    /// The name `object` is known by in `category`, allocating one if it has
76    /// none yet.
77    ///
78    /// An object already in the category keeps the name it has — reusing an
79    /// existing `/F1` rather than minting `FXF1` beside it — which is what
80    /// keeps a page that regenerates twice from growing a resource dictionary
81    /// without bound.
82    pub fn realize(&mut self, category: &str, object: ObjRef) -> Name {
83        let dict = self.entries.entry(category.to_owned()).or_default();
84        for (name, held) in dict.iter() {
85            if held.as_ref_id() == Some(object) {
86                return name.clone();
87            }
88        }
89        let name = self.free_name(category);
90        let dict = self.entries.entry(category.to_owned()).or_default();
91        dict.push(name.clone(), Object::Ref(object));
92        name
93    }
94
95    /// The name `object` already has in `category`, without allocating one.
96    ///
97    /// What an object in a stream this run is *not* rewriting needs: the
98    /// stream refers to the resource by the name it already spells, so the
99    /// name has to be found rather than minted — and if there is none, there
100    /// is nothing to keep alive.
101    #[must_use]
102    pub fn name_of(&self, category: &str, object: ObjRef) -> Option<Name> {
103        self.entries
104            .get(category)?
105            .iter()
106            .find(|(_, held)| held.as_ref_id() == Some(object))
107            .map(|(name, _)| name.clone())
108    }
109
110    /// The name an equal direct dictionary already has in `category`, without
111    /// allocating one.
112    #[must_use]
113    pub fn name_of_dict(&self, category: &str, value: &Dict) -> Option<Name> {
114        self.entries
115            .get(category)?
116            .iter()
117            .find(|(_, held)| matches!(held, Object::Dict(d) if d == value))
118            .map(|(name, _)| name.clone())
119    }
120
121    /// Add a direct dictionary — an `/ExtGState` the emitter built rather than
122    /// found — under a fresh name, or return the name an equal one already has.
123    pub fn realize_dict(&mut self, category: &str, value: &Dict) -> Name {
124        let existing = self
125            .entries
126            .get(category)
127            .and_then(|dict| {
128                dict.iter().find(|(_, held)| match held {
129                    Object::Dict(d) => d == value,
130                    _ => false,
131                })
132            })
133            .map(|(name, _)| name.clone());
134        existing.unwrap_or_else(|| {
135            let name = self.free_name(category);
136            let dict = self.entries.entry(category.to_owned()).or_default();
137            dict.push(name.clone(), Object::Dict(value.clone()));
138            name
139        })
140    }
141
142    /// The first `FX*n` name free in `category`, counting from one.
143    ///
144    /// Free means absent from both the live entries and the parked ones — a
145    /// parked entry may be restored, and would then collide.
146    fn free_name(&self, category: &str) -> Name {
147        let letter = category.chars().next().unwrap_or('X');
148        let live = self.entries.get(category);
149        let parked = self.parked.get(category);
150        for id in 1u32.. {
151            let candidate = Name::from(format!("FX{letter}{id}").as_str());
152            let taken = live.is_some_and(|d| d.contains_key(&candidate))
153                || parked.is_some_and(|p| p.contains_key(&candidate));
154            if !taken {
155                return candidate;
156            }
157        }
158        // `1u32..` is unbounded, so the loop always returns; this satisfies
159        // the type checker without a panic.
160        Name::from("FXX1")
161    }
162
163    /// Drop every entry no object used, parking it in case a later
164    /// regeneration wants it back, and restore any parked entry that is wanted
165    /// now.
166    ///
167    /// `used` names, per category, exactly what the regenerated streams
168    /// referred to — every name [`Self::realize`] handed out and nothing else.
169    /// A name the caller allocated and then forgot to list is swept away, so
170    /// the caller records at the point of allocation.
171    pub fn sweep(&mut self, used: &BTreeMap<String, BTreeSet<Name>>) {
172        for category in CATEGORIES {
173            let wanted: BTreeSet<Name> =
174                used.get(category).into_iter().flatten().cloned().collect();
175
176            if let Some(dict) = self.entries.get_mut(category) {
177                let mut kept = Dict::new();
178                let parked = self.parked.entry(category.to_owned()).or_default();
179                for (name, value) in dict.iter() {
180                    if wanted.contains(name) {
181                        kept.push(name.clone(), value.clone());
182                    } else {
183                        parked.insert(name.clone(), value.clone());
184                    }
185                }
186                *dict = kept;
187            }
188
189            // Anything wanted that is parked comes back.
190            let restorable: Vec<(Name, Object)> = self
191                .parked
192                .get(category)
193                .into_iter()
194                .flatten()
195                .filter(|(name, _)| wanted.contains(*name))
196                .map(|(name, value)| (name.clone(), value.clone()))
197                .collect();
198            if restorable.is_empty() {
199                continue;
200            }
201            let dict = self.entries.entry(category.to_owned()).or_default();
202            let parked = self.parked.entry(category.to_owned()).or_default();
203            for (name, value) in restorable {
204                if !dict.contains_key(&name) {
205                    dict.push(name.clone(), value);
206                }
207                parked.remove(&name);
208            }
209        }
210    }
211
212    /// The `/Resources` dictionary this table describes, built onto `base` so
213    /// that categories the table does not maintain survive untouched.
214    #[must_use]
215    pub fn to_dict(&self, base: &Dict) -> Dict {
216        let mut out = Dict::new();
217        for (key, value) in base.iter() {
218            if CATEGORIES.iter().any(|c| key.as_bytes() == c.as_bytes()) {
219                continue;
220            }
221            out.push(key.clone(), value.clone());
222        }
223        for category in CATEGORIES {
224            let Some(dict) = self.entries.get(category) else {
225                continue;
226            };
227            // An empty category is dropped rather than written as `<< >>`:
228            // the sweep emptied it, and the key means nothing without entries.
229            if dict.is_empty() {
230                continue;
231            }
232            out.push(Name::from(category), Object::Dict(dict.clone()));
233        }
234        out
235    }
236}
237
238#[cfg(test)]
239mod tests {
240    use super::{CATEGORIES, ResourceTable};
241    use pdfrum_object::{Dict, Name, NoResolve, ObjRef, Object};
242    use std::collections::{BTreeMap, BTreeSet};
243
244    fn used(pairs: &[(&str, &[&str])]) -> BTreeMap<String, BTreeSet<Name>> {
245        pairs
246            .iter()
247            .map(|(category, names)| {
248                (
249                    (*category).to_owned(),
250                    names.iter().map(|n| Name::from(*n)).collect(),
251                )
252            })
253            .collect()
254    }
255
256    fn names_of(table: &ResourceTable, category: &str) -> Vec<String> {
257        let dict = table.to_dict(&Dict::new());
258        let Some(Object::Dict(sub)) = dict.raw(&Name::from(category)) else {
259            return Vec::new();
260        };
261        sub.keys()
262            .map(|k| String::from_utf8_lossy(k.as_bytes()).into_owned())
263            .collect()
264    }
265
266    // The three categories, and only those three.
267    #[test]
268    fn exactly_three_categories_are_maintained() {
269        assert_eq!(CATEGORIES, ["ExtGState", "Font", "XObject"]);
270    }
271
272    // `RealizeResource` (:513-552): `FX` + the category's first letter + a
273    // number counting from one.
274    #[test]
275    fn a_fresh_name_is_fx_plus_the_categorys_letter_plus_one() {
276        let mut table = ResourceTable::default();
277        assert_eq!(table.realize("Font", ObjRef::new(4, 0)), Name::from("FXF1"));
278        assert_eq!(
279            table.realize("XObject", ObjRef::new(5, 0)),
280            Name::from("FXX1")
281        );
282        assert_eq!(
283            table.realize("ExtGState", ObjRef::new(6, 0)),
284            Name::from("FXE1")
285        );
286    }
287
288    #[test]
289    fn successive_objects_take_successive_numbers() {
290        let mut table = ResourceTable::default();
291        let first = table.realize("XObject", ObjRef::new(1, 0));
292        let second = table.realize("XObject", ObjRef::new(2, 0));
293        assert_eq!(first, Name::from("FXX1"));
294        assert_eq!(second, Name::from("FXX2"));
295    }
296
297    // An object already named keeps its name rather than gaining a second.
298    #[test]
299    fn an_object_already_in_the_dictionary_keeps_its_name() {
300        let existing = Dict::from_pairs([(Name::from("F1"), Object::Ref(ObjRef::new(9, 0)))]);
301        let resources = Dict::from_pairs([(Name::from("Font"), Object::Dict(existing))]);
302        let mut table = ResourceTable::load(&resources, &NoResolve);
303        assert_eq!(table.realize("Font", ObjRef::new(9, 0)), Name::from("F1"));
304        assert_eq!(names_of(&table, "Font"), vec!["F1".to_owned()]);
305    }
306
307    // A name the dictionary already holds is skipped, whatever it names.
308    #[test]
309    fn an_occupied_name_is_skipped() {
310        let existing = Dict::from_pairs([(Name::from("FXF1"), Object::Int(0))]);
311        let resources = Dict::from_pairs([(Name::from("Font"), Object::Dict(existing))]);
312        let mut table = ResourceTable::load(&resources, &NoResolve);
313        assert_eq!(table.realize("Font", ObjRef::new(3, 0)), Name::from("FXF2"));
314    }
315
316    // `DoubleGenerating` (fpdf_edit_embeddertest.cpp:3638): the entry nothing
317    // uses is dropped, and the next allocation does **not** reuse its number,
318    // because the dropped entry is parked and still reserves it.
319    #[test]
320    fn a_swept_name_is_parked_and_still_reserved() {
321        let mut table = ResourceTable::default();
322        let first = table.realize("ExtGState", ObjRef::new(1, 0));
323        let second = table.realize("ExtGState", ObjRef::new(2, 0));
324        assert_eq!(
325            (first.clone(), second.clone()),
326            (Name::from("FXE1"), Name::from("FXE2"))
327        );
328
329        // Only the first is used; the second is swept away.
330        table.sweep(&used(&[("ExtGState", &["FXE1"])]));
331        assert_eq!(names_of(&table, "ExtGState"), vec!["FXE1".to_owned()]);
332
333        // The next allocation skips the parked FXE2.
334        let third = table.realize("ExtGState", ObjRef::new(3, 0));
335        assert_eq!(third, Name::from("FXE3"));
336    }
337
338    // The other half of the parking rule: an entry that is wanted again comes
339    // back rather than being minted afresh under a new name.
340    #[test]
341    fn a_parked_entry_wanted_again_is_restored() {
342        let existing = Dict::from_pairs([
343            (Name::from("A"), Object::Int(1)),
344            (Name::from("B"), Object::Int(2)),
345        ]);
346        let resources = Dict::from_pairs([(Name::from("Font"), Object::Dict(existing))]);
347        let mut table = ResourceTable::load(&resources, &NoResolve);
348
349        table.sweep(&used(&[("Font", &["A"])]));
350        assert_eq!(names_of(&table, "Font"), vec!["A".to_owned()]);
351
352        table.sweep(&used(&[("Font", &["A", "B"])]));
353        assert_eq!(
354            names_of(&table, "Font"),
355            vec!["A".to_owned(), "B".to_owned()]
356        );
357    }
358
359    // A category the sweep empties loses its key rather than becoming `<< >>`.
360    #[test]
361    fn an_emptied_category_loses_its_key() {
362        let existing = Dict::from_pairs([(Name::from("F1"), Object::Int(1))]);
363        let resources = Dict::from_pairs([(Name::from("Font"), Object::Dict(existing))]);
364        let mut table = ResourceTable::load(&resources, &NoResolve);
365        table.sweep(&BTreeMap::new());
366        let out = table.to_dict(&Dict::new());
367        assert!(!out.contains_key(&Name::from("Font")));
368    }
369
370    // Categories nobody maintains survive the round trip untouched — the sweep
371    // must not eat a page's colour spaces.
372    #[test]
373    fn an_unmaintained_category_is_carried_through() {
374        let base = Dict::from_pairs([
375            (Name::from("ColorSpace"), Object::Int(7)),
376            (Name::from("Font"), Object::Int(0)),
377        ]);
378        let table = ResourceTable::default();
379        let out = table.to_dict(&base);
380        assert_eq!(out.raw(&Name::from("ColorSpace")), Some(&Object::Int(7)));
381        // The maintained category is replaced by the table's own view, which
382        // here is empty.
383        assert!(!out.contains_key(&Name::from("Font")));
384    }
385
386    // Two objects wanting the same graphics state share one entry.
387    #[test]
388    fn an_equal_direct_dictionary_is_reused() {
389        let mut table = ResourceTable::default();
390        let gs = Dict::from_pairs([(Name::from("ca"), Object::Real(0.5))]);
391        let first = table.realize_dict("ExtGState", &gs);
392        let second = table.realize_dict("ExtGState", &gs);
393        assert_eq!(first, second);
394        assert_eq!(names_of(&table, "ExtGState"), vec!["FXE1".to_owned()]);
395    }
396
397    // The sweep is driven by the `used` set alone, so a name allocated and
398    // then not listed is swept — which is why the caller records each name at
399    // the point it allocates it rather than afterwards.
400    #[test]
401    fn a_name_the_caller_did_not_list_is_swept() {
402        let mut table = ResourceTable::default();
403        let _ = table.realize("XObject", ObjRef::new(1, 0));
404        table.sweep(&BTreeMap::new());
405        assert!(names_of(&table, "XObject").is_empty());
406    }
407}
pdfrum_edit/content/resource.rs

pdfrum_edit/content/
resource.rs
