get_pixmap() never returns on a tagged PDF page with many MCIDs — pdf_lookup_mcid_in_mcids is a linear scan, making rendering O(n²) per page #5125

Description of the bug

Rendering a single tagged (Marked Content / PDF-UA style) page whose content carries ~5,400 marked-content ids never completes. page.get_pixmap() spins at 100% CPU indefinitely — I let it run for over 7 minutes with no result, and a truncated-size measurement extrapolates to roughly an hour for the real page.

The page itself is entirely unremarkable: A4 (595x841 pt), 2 subsetted Type1/CFF fonts, zero images, no shadings, no Do invocations, and only two ExtGStates (both /SMask /None, /BM /Normal). It has a /Group <</S/Transparency>>, but removing that changes nothing — it still hangs. It renders in 0.02 s the moment the structure tree is detached. The problem is not the page's graphics, it is the cost of resolving its marked-content ids.

A stack sample of the hung process points at the marked-content id lookup:

fz_new_display_list_from_page
  fz_run_page
    fz_run_page_contents
      pdf_run_page_contents
        pdf_run_page_contents_with_usage
          pdf_process_contents
            pdf_process_raw_contents            <- content stream interpreter
              +-- 2079 samples  (unsymbolised sibling in the same function)
              +-- 1975 samples  -> pdf_lookup_mcid_in_mcids   <- hot spot
                                    +-- 1758  (inside it)
                                    +--  127
                                    +--   39  pdf_array_get
                                    +--   32

pdf_array_get being called from inside pdf_lookup_mcid_in_mcids indicates the lookup walks the MCID array linearly. Since it runs once per BDC operator, a page with n marked-content ids costs O(n²).

Measured scaling confirms that. I took the real page and scaled it down consistently on every axis (content BDC count, the struct element's /K kids, the /ParentTree entry, and the /Pg back-references), so each variant is a faithful smaller version of the same page:

Two further observations that place the cost in content/structure interpretation rather than rasterisation:

• page.get_drawings() hangs identically on the same page.
• Document.save(..., clean=True) also hangs on it (the content sanitiser re-interprets the same operators).

Which item I

tagged_mcid_hang.pdf

keep makes no difference — keeping the first n ids versus the last n ids gives identical timings (0.84 vs 0.82 s at n=264, 4.87 vs 4.85 s at n=500, 27.67 vs 27.68 s at n=900). There is no single pathological entry; cost is purely a function of the count.

How to reproduce the bug

Attached: tagged_mcid_hang.pdf — 1 page, 718 KB, anonymised (boilerplate legal text only, no personal data, identifying metadata cleared; the producer/creator strings are kept deliberately to identify the generator).

import time
import pymupdf

doc = pymupdf.open("tagged_mcid_hang.pdf")

t = time.monotonic()
pm = doc[0].get_pixmap(dpi=200)          # never returns; 100% CPU
print(f"{time.monotonic() - t:.3f}s -> {pm.width}x{pm.height}")

Expected: completes in well under a second, like any other A4 text page of this complexity.

Actual: no result. Killed after 45 s here; observed spinning for 7+ minutes elsewhere, RSS flat at ~50 MB (so it is a CPU loop, not a memory problem or a deadlock).

Detaching the structure tree makes the same call return immediately, with byte-identical output to a correctly rendered variant:

catalog = doc.pdf_catalog()
for key in ("StructTreeRoot", "MarkInfo"):
    doc.xref_set_key(catalog, key, "null")

pm = doc[0].get_pixmap(dpi=200)          # 0.023 s -> 1653x2337

Verified on both versions, each run in a clean venv:

1.28.0 (MuPDF 1.29.0)  plain      : no result after 45s, SIGKILLed
1.28.0 (MuPDF 1.29.0)  workaround : get_pixmap returned in 0.023s -> 1653x2337
1.28.2 (MuPDF 1.28.2)  plain      : no result after 45s, SIGKILLed
1.28.2 (MuPDF 1.28.2)  workaround : get_pixmap returned in 0.024s -> 1653x2337

tagged_mcid_hang.pdf

PyMuPDF version

1.28.2

Operating system

Linux

Python version

3.14