Source code

Download source archive ↓

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