src/pypdf/_page_labels.py
1"""
2Page labels are shown by PDF viewers as "the page number".
3
4A page has a numeric index, starting at 0. Additionally, the page
5has a label. In the most simple case:
6
7 label = index + 1
8
9However, the title page and the table of contents might have Roman numerals as
10page labels. This makes things more complicated.
11
12Example 1
13---------
14
15>>> reader.root_object["/PageLabels"]["/Nums"]
16[0, IndirectObject(18, 0, 139929798197504),
17 8, IndirectObject(19, 0, 139929798197504)]
18>>> reader.get_object(reader.root_object["/PageLabels"]["/Nums"][1])
19{'/S': '/r'}
20>>> reader.get_object(reader.root_object["/PageLabels"]["/Nums"][3])
21{'/S': '/D'}
22
23Example 2
24---------
25The following is a document with pages labeled
26i, ii, iii, iv, 1, 2, 3, A-8, A-9, ...
27
281 0 obj
29 << /Type /Catalog
30 /PageLabels << /Nums [
31 0 << /S /r >>
32 4 << /S /D >>
33 7 << /S /D
34 /P ( A- )
35 /St 8
36 >>
37 % A number tree containing
38 % three page label dictionaries
39 ]
40 >>
41 ...
42 >>
43endobj
44
45
46§12.4.2 PDF Specification 1.7 and 2.0
47=====================================
48
49Entries in a page label dictionary
50----------------------------------
51The /S key:
52D Decimal Arabic numerals
53R Uppercase Roman numerals
54r Lowercase Roman numerals
55A Uppercase letters (A to Z for the first 26 pages,
56 AA to ZZ for the next 26, and so on)
57a Lowercase letters (a to z for the first 26 pages,
58 aa to zz for the next 26, and so on)
59"""
60import math
61import string
62from bisect import bisect_left, bisect_right
63from collections.abc import Callable, Iterable
64from typing import Any, NamedTuple, cast
65
66from ._protocols import PdfCommonDocProtocol
67from ._utils import logger_warning
68from .generic import (
69 ArrayObject,
70 DictionaryObject,
71 NullObject,
72 NumberObject,
73 is_null_or_none,
74)
75
76# The largest number one can represent using the usual symbols
77# and subtractive notation without additional conventions.
78# Aligns with https://github.com/AA-Turner/roman-numerals/blob/master/python/roman_numerals/__init__.py
79MAXIMUM_ROMAN_NUMERAL = 3_999
80
81# Allow values of up to 512 * 26 = 13_312 for the `/A` and `/a`.
82# Please note that this limit is somehow arbitrary and some trade-off
83# between rather restrictive <= 256 output bytes per label and the possibly
84# unrealistic 1000 output bytes per label.
85MAXIMUM_PAGE_LABEL_LENGTH = 512
86
87
88def number2decimal_arabic_numeral(number: int) -> str:
89 # A page label is a page *number*, so reject the non-positive values the
90 # other styles already reject. Without this, a malformed /St or a /Nums
91 # range which does not start at the first page gives labels like "0".
92 if number <= 0:
93 raise ValueError("Expecting a positive number.")
94 return str(number)
95
96
97def number2uppercase_roman_numeral(num: int) -> str:
98 if num <= 0:
99 raise ValueError("Expecting a positive number.")
100 if num > MAXIMUM_ROMAN_NUMERAL:
101 raise ValueError("Number is out of range.")
102 roman = [
103 (1000, "M"),
104 (900, "CM"),
105 (500, "D"),
106 (400, "CD"),
107 (100, "C"),
108 (90, "XC"),
109 (50, "L"),
110 (40, "XL"),
111 (10, "X"),
112 (9, "IX"),
113 (5, "V"),
114 (4, "IV"),
115 (1, "I"),
116 ]
117
118 result = []
119 for value, symbol in roman:
120 count, num = divmod(num, value)
121 result.append(symbol * count)
122
123 return "".join(result)
124
125
126def number2lowercase_roman_numeral(number: int) -> str:
127 return number2uppercase_roman_numeral(number).lower()
128
129
130def number2uppercase_letter(number: int) -> str:
131 if number <= 0:
132 raise ValueError("Expecting a positive number.")
133 # A to Z, then the same letter repeated: AA to ZZ, AAA to ZZZ, and so on.
134 repetitions, position = divmod(number - 1, 26)
135 length = repetitions + 1
136 if length > MAXIMUM_PAGE_LABEL_LENGTH:
137 raise ValueError("Number is too large.")
138 return string.ascii_uppercase[position] * (repetitions + 1)
139
140
141def number2lowercase_letter(number: int) -> str:
142 return number2uppercase_letter(number).lower()
143
144
145_NUMBERING_STYLES: dict[str | None, Callable[[int], str]] = {
146 None: lambda _: "",
147 "/D": number2decimal_arabic_numeral,
148 "/R": number2uppercase_roman_numeral,
149 "/r": number2lowercase_roman_numeral,
150 "/A": number2uppercase_letter,
151 "/a": number2lowercase_letter,
152}
153
154
155def _get_label(value: Any, start_index: Any, index: int) -> str:
156 # if /Nums array is not following the specification or if /Nums is empty
157 if not isinstance(value, dict):
158 return str(index + 1) # Fallback
159 start = value.get("/St", 1)
160 prefix = cast(str, value.get("/P", ""))
161 mapping_function = _NUMBERING_STYLES.get(value.get("/S"))
162 if mapping_function is None:
163 # Unknown /S numbering style; fall back to the page position.
164 logger_warning(
165 "Ignoring unknown page label numbering style %(style)r in /Nums.",
166 source=__name__,
167 style=value.get("/S"),
168 )
169 return str(index + 1) # Fallback
170
171 try:
172 label = prefix + mapping_function(index - start_index + start)
173 if len(label) > MAXIMUM_PAGE_LABEL_LENGTH:
174 raise ValueError("Page label is too long.")
175 except (TypeError, ValueError) as exception:
176 # Malformed /St or /P value or too large value; fall back to the page position.
177 logger_warning(
178 "Ignoring malformed page label entry in /Nums (/St=%(start)r, /P=%(prefix)r): %(exception)s",
179 source=__name__,
180 start=start,
181 prefix=prefix,
182 exception=exception,
183 )
184 else:
185 return label
186
187 return str(index + 1) # Fallback
188
189
190def get_label_from_nums(dictionary_object: DictionaryObject, index: int) -> str:
191 # [Nums] shall be an array of the form
192 # [ key_1 value_1 key_2 value_2 ... key_n value_n ]
193 # where each key_i is an integer and the corresponding
194 # value_i shall be the object associated with that key.
195 # The keys shall be sorted in numerical order,
196 # analogously to the arrangement of keys in a name tree
197 # as described in 7.9.6, "Name Trees."
198 nums = dictionary_object["/Nums"]
199 if not isinstance(nums, ArrayObject):
200 logger_warning(
201 "Page label numbers are not an array: %(nums)s",
202 source=__name__,
203 nums=nums,
204 )
205 return str(index + 1) # Fallback
206 nums_length = len(nums)
207 i = 0
208 value = None
209 start_index = 0
210 while i < nums_length:
211 if i + 1 >= nums_length:
212 logger_warning(
213 "Ignoring last /Nums key without a value.", source=__name__
214 )
215 break
216 start_index = nums[i]
217 value = nums[i + 1].get_object()
218 if i + 2 == nums_length:
219 break
220 next_key = nums[i + 2]
221 if not isinstance(next_key, (int, float)):
222 logger_warning(
223 "Ignoring malformed page label key %(key)r in /Nums.",
224 source=__name__,
225 key=next_key,
226 )
227 return str(index + 1) # Fallback
228 if next_key > index:
229 break
230 i += 2
231 return _get_label(value, start_index, index)
232
233
234def index2label(reader: PdfCommonDocProtocol, index: int) -> str:
235 """
236 See 7.9.7 "Number Trees".
237
238 Args:
239 reader: The PdfReader
240 index: The index of the page
241
242 Returns:
243 The label of the page, e.g. "iv" or "4".
244
245 """
246 root = cast(DictionaryObject, reader.root_object)
247 if "/PageLabels" not in root:
248 return str(index + 1) # Fallback
249 number_tree = root["/PageLabels"].get_object()
250 if not isinstance(number_tree, DictionaryObject):
251 logger_warning(
252 "Page labels are not a dictionary: %(number_tree)s",
253 source=__name__,
254 number_tree=number_tree,
255 )
256 return str(index + 1) # Fallback
257 if "/Nums" in number_tree:
258 return get_label_from_nums(number_tree, index)
259 if "/Kids" in number_tree and not isinstance(number_tree["/Kids"], NullObject):
260 # number_tree = {'/Kids': [IndirectObject(7333, 0, 140132998195856), ...]}
261 # Limit maximum depth.
262 level = 0
263 while level < 100:
264 kids = number_tree["/Kids"].get_object()
265 if not isinstance(kids, ArrayObject):
266 logger_warning(
267 "Page label kids are not an array: %(kids)s",
268 source=__name__,
269 kids=kids,
270 )
271 break
272 # The keys are page indices where a labelling range starts, so a page
273 # between the /Limits of two kids belongs to the range started by the
274 # largest key before it, the last key of the preceding kid.
275 preceding_kid = None
276 for kid in kids:
277 # kid = {'/Limits': [0, 63], '/Nums': [0, {'/P': 'C1'}, ...]}
278 kid = kid.get_object()
279 if not isinstance(kid, DictionaryObject):
280 logger_warning(
281 "Ignoring kid which is not a dictionary in /PageLabels.",
282 source=__name__,
283 )
284 continue
285 limits = kid.get("/Limits", NullObject()).get_object()
286 if not isinstance(limits, list) or len(limits) < 2:
287 # Skip kids whose /Limits range is missing or malformed.
288 logger_warning(
289 "Ignoring kid with missing or malformed /Limits in /PageLabels.",
290 source=__name__,
291 )
292 continue
293 if limits[0] <= index <= limits[1]:
294 break
295 if limits[0] <= index:
296 preceding_kid = kid
297 else:
298 if preceding_kid is None:
299 # When no kid starts at or before the index, make sure to exit the
300 # `while` loop directly and continue with the fallback.
301 break
302 kid = preceding_kid
303 if not is_null_or_none(kid.get("/Kids", None)):
304 # Recursive definition.
305 level += 1
306 if level == 100: # pragma: no cover
307 raise NotImplementedError("Too deep nesting is not supported.")
308 number_tree = kid
309 # Continue at the next level with the next iteration of the `while` loop.
310 continue
311 return get_label_from_nums(kid, index)
312
313 logger_warning("Could not reliably determine page label for %(index)d.", source=__name__, index=index)
314 return str(index + 1) # Fallback if neither /Nums nor /Kids is in the number_tree
315
316
317def _get_labels_for_page_indexes(nums: ArrayObject, indexes: Iterable[int]) -> list[str]:
318 """
319 Labels for increasing page indexes, as ``get_label_from_nums`` would return them.
320
321 ``get_label_from_nums`` stops at the first pair whose next key is above the page index.
322 As that pair can only move forward when the page index grows, the array is read once
323 for all pages instead of from the start for every page, and each value is resolved
324 when its pair is first reached.
325 """
326 nums_length = len(nums)
327 labels = []
328 i = 0
329 resolved = -1
330 start_index: Any = 0
331 value: Any = None
332 for index in indexes:
333 is_key_malformed = False
334 while i < nums_length:
335 if i + 1 >= nums_length:
336 logger_warning("Ignoring last /Nums key without a value.", source=__name__)
337 break
338 if resolved != i:
339 start_index = nums[i]
340 value = nums[i + 1].get_object()
341 resolved = i
342 if i + 2 == nums_length:
343 break
344 next_key = nums[i + 2]
345 if not isinstance(next_key, (int, float)):
346 logger_warning(
347 "Ignoring malformed page label key %(key)r in /Nums.",
348 source=__name__,
349 key=next_key,
350 )
351 is_key_malformed = True
352 break
353 if next_key > index:
354 break
355 i += 2
356 labels.append(str(index + 1) if is_key_malformed else _get_label(value, start_index, index))
357 return labels
358
359
360def _get_page_range(limits: list[Any], page_count: int) -> tuple[int, int] | None:
361 """Get the first and last page index between the two ``/Limits`` values, if any."""
362 low, high = limits[0], limits[1]
363 if low >= page_count or high < 0:
364 return None
365 last_page = page_count - 1
366 first = 0 if low <= 0 else math.ceil(low)
367 last = last_page if high >= last_page else math.floor(high)
368 return (first, last) if first <= last else None
369
370
371class _FirstKidFinder:
372 """
373 Find the kid ``index2label`` picks for a page index: the first kid in order whose
374 ``/Limits`` contain it.
375
376 Like ``index2label``, kids are read in order and only as far as needed. The pages
377 covered by the kids read so far are kept as sorted ranges, so that each kid is read
378 once instead of once per page. A kid which cannot be read is returned as the
379 exception, which ``index2label`` raises for every page that reaches this kid.
380 """
381
382 def __init__(self, kids: ArrayObject, page_count: int) -> None:
383 self._kids = kids
384 self._kid_count = len(kids)
385 self._page_count = page_count
386 self._next_kid = 0
387 # Pages covered by any kid read so far, as merged ranges.
388 self._covered_starts: list[int] = []
389 self._covered_ends: list[int] = []
390 # Ranges of pages with the same first kid.
391 self._starts: list[int] = []
392 self._ends: list[int] = []
393 self._first_kids: list[DictionaryObject | Exception] = []
394 # Kids read so far with valid /Limits and their lower limits, in order.
395 self._read_kids: list[DictionaryObject] = []
396 self._read_lows: list[float] = []
397
398 def find(self, index: int) -> DictionaryObject | Exception | None:
399 while True:
400 position = bisect_right(self._starts, index) - 1
401 if position >= 0 and index <= self._ends[position]:
402 return self._first_kids[position]
403 if self._next_kid >= self._kid_count:
404 return None
405 kid_range = self._read_kid(self._kids[self._next_kid])
406 self._next_kid += 1
407 if kid_range is not None:
408 self._cover(*kid_range)
409
410 def find_preceding(self, index: int) -> DictionaryObject | None:
411 """
412 Find the kid ``index2label`` picks for a page index no kid contains: the last
413 kid in order whose ``/Limits`` start before it. Only valid once ``find`` has
414 returned ``None`` for the index, which means that all kids have been read.
415 """
416 position = bisect_right(self._read_lows, index) - 1
417 if position < 0:
418 return None
419 return self._read_kids[position]
420
421 def _read_kid(self, kid: Any) -> tuple[int, int, DictionaryObject | Exception] | None:
422 try:
423 kid = kid.get_object()
424 limits = kid.get("/Limits", NullObject()).get_object() if isinstance(kid, DictionaryObject) else None
425 except MemoryError: # pragma: no cover # TODO: BLE001
426 raise
427 except Exception as exception:
428 return 0, self._page_count - 1, exception
429 if not isinstance(kid, DictionaryObject):
430 logger_warning("Ignoring kid which is not a dictionary in /PageLabels.", source=__name__)
431 return None
432 if (
433 not isinstance(limits, list)
434 or len(limits) < 2
435 or not all(isinstance(limit, (int, float)) for limit in limits[:2])
436 ):
437 logger_warning("Ignoring kid with missing or malformed /Limits in /PageLabels.", source=__name__)
438 return None
439 self._read_kids.append(kid)
440 self._read_lows.append(limits[0])
441 page_range = _get_page_range(limits, self._page_count)
442 return None if page_range is None else (*page_range, kid)
443
444 def _cover(self, first: int, last: int, kid: DictionaryObject | Exception) -> None:
445 """Make ``kid`` the first kid of the pages from ``first`` to ``last`` which no earlier kid covers."""
446 start = bisect_left(self._covered_ends, first)
447 end = bisect_right(self._covered_starts, last)
448 gaps = []
449 position = first
450 for covered_start, covered_end in zip(self._covered_starts[start:end], self._covered_ends[start:end]):
451 if covered_start > position:
452 gaps.append((position, covered_start - 1))
453 position = max(position, covered_end + 1)
454 if position <= last:
455 gaps.append((position, last))
456 if start < end:
457 first = min(first, self._covered_starts[start])
458 last = max(last, self._covered_ends[end - 1])
459 self._covered_starts[start:end] = [first]
460 self._covered_ends[start:end] = [last]
461 for gap_start, gap_end in gaps:
462 position = bisect_left(self._starts, gap_start)
463 self._starts.insert(position, gap_start)
464 self._ends.insert(position, gap_end)
465 self._first_kids.insert(position, kid)
466
467
468class _TreeNode(NamedTuple):
469 """A node of a ``/Kids`` number tree with the page indexes reaching it."""
470
471 node: DictionaryObject
472 indexes: list[int]
473 level: int
474
475
476class _KidPages(NamedTuple):
477 """A kid with the page indexes it is picked for."""
478
479 kid: DictionaryObject
480 indexes: list[int]
481
482
483class _LeafPages(NamedTuple):
484 """A leaf with its ``/Nums`` array, if it is one, and the page indexes it labels."""
485
486 nums: ArrayObject | None
487 leaf: DictionaryObject
488 indexes: list[int]
489
490
491def _get_labels_from_kids(number_tree: DictionaryObject, page_count: int) -> list[str]:
492 """
493 Labels of the first ``page_count`` pages of a ``/Kids`` number tree, as ``index2label`` would return them.
494
495 Instead of walking the tree from the root for every page, each ``/Kids`` array is
496 indexed once and each ``/Nums`` array is read once for all of its pages. Warnings
497 about malformed kids are logged once per array instead of once per page.
498 """
499 # The finders keep their /Kids arrays, so the ids stay unique.
500 finders: dict[int, _FirstKidFinder] = {}
501 leaves: dict[int, _LeafPages] = {}
502 unmatched: list[int] = []
503 nodes = [_TreeNode(number_tree, list(range(page_count)), 0)]
504 while nodes:
505 node = nodes.pop()
506 kids = node.node["/Kids"].get_object()
507 if not isinstance(kids, ArrayObject):
508 logger_warning("Page label kids are not an array: %(kids)s", source=__name__, kids=kids)
509 unmatched.extend(node.indexes)
510 continue
511 if id(kids) not in finders:
512 finders[id(kids)] = _FirstKidFinder(kids, page_count)
513 finder = finders[id(kids)]
514 kid_pages: dict[int, _KidPages] = {}
515 for index in node.indexes:
516 kid = finder.find(index)
517 if isinstance(kid, Exception):
518 raise kid
519 if kid is None:
520 kid = finder.find_preceding(index)
521 if kid is None:
522 unmatched.append(index)
523 else:
524 kid_pages.setdefault(id(kid), _KidPages(kid, [])).indexes.append(index)
525 for kid, indexes in kid_pages.values():
526 if not is_null_or_none(kid.get("/Kids", None)):
527 # Same nesting limit as in index2label().
528 if node.level + 1 == 100: # pragma: no cover
529 raise NotImplementedError("Too deep nesting is not supported.")
530 nodes.append(_TreeNode(kid, indexes, node.level + 1))
531 continue
532 # Leaves sharing a /Nums array are read together.
533 nums = kid["/Nums"]
534 if isinstance(nums, ArrayObject):
535 leaves.setdefault(id(nums), _LeafPages(nums, kid, [])).indexes.extend(indexes)
536 else:
537 leaves.setdefault(id(kid), _LeafPages(None, kid, [])).indexes.extend(indexes)
538
539 labels = [""] * page_count
540 for leaf_nums, leaf, leaf_indexes in leaves.values():
541 leaf_indexes.sort()
542 leaf_labels = (
543 _get_labels_for_page_indexes(leaf_nums, leaf_indexes)
544 if leaf_nums is not None
545 else [get_label_from_nums(leaf, index) for index in leaf_indexes]
546 )
547 for index, label in zip(leaf_indexes, leaf_labels):
548 labels[index] = label
549 for index in sorted(unmatched):
550 logger_warning("Could not reliably determine page label for %(index)d.", source=__name__, index=index)
551 labels[index] = str(index + 1)
552 return labels
553
554
555def _index2labels_page_by_page(pdf: PdfCommonDocProtocol, page_count: int) -> list[str]:
556 return [index2label(pdf, index) for index in range(page_count)]
557
558
559def index2labels(pdf: PdfCommonDocProtocol, page_count: int) -> list[str]:
560 """
561 Labels of the first ``page_count`` pages, as ``index2label`` would return them.
562
563 Number trees are read once for all pages instead of from the start for every page.
564 """
565 if page_count <= 0:
566 return []
567 root = cast(DictionaryObject, pdf.root_object)
568 if "/PageLabels" not in root:
569 return _index2labels_page_by_page(pdf, page_count)
570 number_tree = root["/PageLabels"].get_object()
571 if not isinstance(number_tree, DictionaryObject):
572 return _index2labels_page_by_page(pdf, page_count)
573 if "/Nums" in number_tree:
574 nums = number_tree["/Nums"]
575 if not isinstance(nums, ArrayObject):
576 return [get_label_from_nums(number_tree, index) for index in range(page_count)]
577 return _get_labels_for_page_indexes(nums, range(page_count))
578 if "/Kids" in number_tree and not isinstance(number_tree["/Kids"], NullObject):
579 return _get_labels_from_kids(number_tree, page_count)
580 return _index2labels_page_by_page(pdf, page_count)
581
582
583def nums_insert(
584 key: NumberObject,
585 value: DictionaryObject,
586 nums: ArrayObject,
587) -> None:
588 """
589 Insert a key, value pair in a Nums array.
590
591 See 7.9.7 "Number Trees".
592
593 Args:
594 key: number key of the entry
595 value: value of the entry
596 nums: Nums array to modify
597
598 """
599 if len(nums) % 2 != 0:
600 raise ValueError("A nums like array must have an even number of elements")
601
602 i = len(nums)
603 while i != 0 and key <= nums[i - 2]:
604 i = i - 2
605
606 if i < len(nums) and key == nums[i]:
607 nums[i + 1] = value
608 else:
609 nums.insert(i, key)
610 nums.insert(i + 1, value)
611
612
613def nums_clear_range(
614 key: NumberObject,
615 page_index_to: int,
616 nums: ArrayObject,
617) -> None:
618 """
619 Remove all entries in a number tree in a range after an entry.
620
621 See 7.9.7 "Number Trees".
622
623 Args:
624 key: number key of the entry before the range
625 page_index_to: The page index of the upper limit of the range
626 nums: Nums array to modify
627
628 """
629 if len(nums) % 2 != 0:
630 raise ValueError("A nums like array must have an even number of elements")
631 if page_index_to < key:
632 raise ValueError("page_index_to must be greater or equal than key")
633
634 i = nums.index(key) + 2
635 while i < len(nums) and nums[i] <= page_index_to:
636 nums.pop(i)
637 nums.pop(i)
638
639
640def nums_next(
641 key: NumberObject,
642 nums: ArrayObject,
643) -> tuple[NumberObject | None, DictionaryObject | None]:
644 """
645 Return the (key, value) pair of the entry after the given one.
646
647 See 7.9.7 "Number Trees".
648
649 Args:
650 key: number key of the entry
651 nums: Nums array
652
653 """
654 if len(nums) % 2 != 0:
655 raise ValueError("A nums like array must have an even number of elements")
656
657 i = nums.index(key) + 2
658 if i < len(nums):
659 return nums[i], nums[i + 1]
660 return None, None