pdf-odin-llm/pagetree.odin

package pdf

import "core:math"

// ---------------------------------------------------------------------------
// Page tree -- ISO 32000-2, 7.7.3
//
// The catalog's /Pages is the root of a tree whose interior nodes (/Type
// /Pages) carry /Kids and whose leaves (/Type /Page) are the pages. Four
// attributes -- /Resources, /MediaBox, /CropBox and /Rotate -- are inherited
// from the nearest ancestor that supplies them (table 30).
//
// The tree is flattened once, at open, into `doc.pages`. Inheritance is
// resolved on the way *down*, by carrying the ancestors' values along the path
// and writing whichever ones the leaf lacks into the leaf's own dictionary.
// Doing it downwards rather than by following /Parent upwards from each page is
// what makes a wrong or cyclic /Parent chain harmless: the attributes come from
// the path actually taken to reach the page, which is the path the file's own
// structure defines. It also means every later reader of a page dictionary --
// the content interpreter, the annotation code -- sees a complete dictionary
// and never has to know inheritance exists.
// ---------------------------------------------------------------------------

// Page is one page of the document with its inherited attributes resolved.
//
// A Page borrows from the Document: `dict` and `resources` live in the
// Document's arena and become invalid when `close` is called. It is a value,
// cheap to copy, and holds no state of its own -- fetching the same index twice
// yields two equal Pages.
Page :: struct {
    doc:       ^Document,
    // Position in the flattened page list, 0-based.
    index:     int,
    // The page's object number, or {0,0} when /Kids held the page as a direct
    // dictionary rather than a reference.
    ref:       Ref,
    dict:      ^Dict,
    // /Resources after inheritance. nil for a page that names none anywhere in
    // its ancestry, which is legal and means "no resources"; the content
    // interpreter treats every name lookup in it as a miss.
    resources: ^Dict,
    // Always finite and non-empty: a page whose /MediaBox is missing, damaged
    // or degenerate gets DEFAULT_PAGE_RECT instead.
    media_box: Rect,
    // /CropBox intersected with /MediaBox, falling back to /MediaBox. This is
    // the rectangle a viewer displays.
    crop_box:  Rect,
    // Clockwise, normalised to one of 0, 90, 180, 270.
    rotate:    int,
    // /UserUnit: the size in points of one unit of page space, default 1. A
    // large-format drawing uses it to stay inside the format's 14400-point
    // limit, so ignoring it renders such a page at the wrong scale.
    user_unit: f64,
}

// ---------------------------------------------------------------------------
// Building the flattened list
// ---------------------------------------------------------------------------

// Inherited carries the four inheritable attributes down the walk as
// unresolved objects. They are copied verbatim -- a Ref stays a Ref -- so that
// writing one into a leaf costs nothing and shares rather than duplicates.
@(private)
Inherited :: struct {
    resources: Object,
    media_box: Object,
    crop_box:  Object,
    rotate:    Object,
}

// pagetree_build flattens the page tree into doc.pages and doc.page_refs.
//
// It returns .No_Pages only when both the tree walk and the fallback scan came
// up empty, because a document with no page objects anywhere in it is the one
// case where there is genuinely nothing to hand back.
@(private)
pagetree_build :: proc(doc: ^Document) -> Error {
    if doc == nil { return .Invalid_Argument }

    clear(&doc.pages)
    clear(&doc.page_refs)

    if root := dict_dict(doc, doc.catalog, "Pages"); root != nil {
        // Only interior nodes go in the visited set. A leaf cannot close a
        // cycle -- it has no kids to recurse through -- and files that
        // reference one page object from two places are relying on it
        // appearing twice, so marking leaves visited would silently drop
        // pages.
        // Deliberately *not* the Document arena: this is scratch for the walk,
        // and the arena is never reclaimed before `close`. Document-arena
        // memory is also never freed, so a set allocated there could not be
        // released here without breaking that rule.
        visited := make(map[u32]bool, 64, context.allocator)
        defer delete(visited)

        // Fuel bounds the total node visits, not just the depth. A tree can be
        // shallow, acyclic and still enormous if /Kids arrays are shared
        // between parents, which is how a small file expands into a very long
        // walk.
        fuel := MAX_PAGES
        root_ref, _ := dict_ref(doc.catalog, "Pages")
        pagetree_walk(doc, root, root_ref, Inherited{}, 0, &visited, &fuel)
    }

    // No catalog, an unusable /Pages, or a tree whose leaves were all
    // unreadable. Objects are still objects: look for pages directly.
    if len(doc.pages) == 0 {
        pagetree_scan(doc)
    }

    if len(doc.pages) == 0 {
        return .No_Pages
    }
    return .None
}

// pagetree_walk visits one node, appending any leaves beneath it.
@(private)
pagetree_walk :: proc(
    doc:       ^Document,
    node:      ^Dict,
    node_ref:  Ref,
    inherited: Inherited,
    depth:     int,
    visited:   ^map[u32]bool,
    fuel:      ^int,
) {
    if node == nil { return }
    if depth >= MAX_DEPTH {
        add_repair(doc, .Missing_Page_Node, 0, node_ref)
        return
    }
    if fuel^ <= 0 { return }
    fuel^ -= 1
    if len(doc.pages) >= MAX_PAGES { return }

    type := dict_type(doc, node)
    kids := dict_array(doc, node, "Kids")

    // /Type is checked before /Kids because a leaf that also carries a stray
    // /Kids -- a page edited by a tool that did not clean up after itself --
    // is a page, not an interior node.
    if type != "Page" && array_len(kids) > 0 {
        if node_ref.num != 0 {
            if visited[node_ref.num] or_else false {
                add_repair(doc, .Cyclic_Page_Tree, 0, node_ref)
                return
            }
            visited[node_ref.num] = true
        }

        down := pagetree_inherit(node, inherited)

        for i in 0 ..< array_len(kids) {
            if fuel^ <= 0 { break }
            raw := array_get_raw(kids, i)
            kid_ref, _ := to_ref(raw)
            kid, ok := to_dict(resolve(doc, raw))
            if !ok {
                add_repair(doc, .Missing_Page_Node, 0, kid_ref)
                continue
            }
            pagetree_walk(doc, kid, kid_ref, down, depth + 1, visited, fuel)
        }

        // Unmarked on the way out, so that a node legitimately reachable by two
        // different paths is walked for each of them. Only a node reachable
        // from *itself* is a cycle. This cannot be a `defer` at the point the
        // mark is set: that scope closes before the kids are walked.
        if node_ref.num != 0 {
            delete_key(visited, node_ref.num)
        }
        return
    }

    // An interior node with no kids contributes nothing. Anything else is a
    // leaf: /Type /Page, and also the untyped dictionaries that turn up in
    // /Kids from producers that omit it, which are pages by position.
    if type == "Pages" { return }

    pagetree_add_leaf(doc, node, node_ref, inherited)
}

// pagetree_inherit returns the inherited set as seen by this node's children:
// the parent's values, overridden by whichever ones this node supplies.
@(private)
pagetree_inherit :: proc(node: ^Dict, parent: Inherited) -> (out: Inherited) {
    out = parent
    if dict_has(node, "Resources") { out.resources = dict_get_raw(node, "Resources") }
    if dict_has(node, "MediaBox")  { out.media_box = dict_get_raw(node, "MediaBox") }
    if dict_has(node, "CropBox")   { out.crop_box  = dict_get_raw(node, "CropBox") }
    if dict_has(node, "Rotate")    { out.rotate    = dict_get_raw(node, "Rotate") }
    return
}

// pagetree_add_leaf records one page, first filling in the inheritable keys it
// does not define for itself.
@(private)
pagetree_add_leaf :: proc(doc: ^Document, leaf: ^Dict, ref: Ref, inherited: Inherited) {
    if len(doc.pages) >= MAX_PAGES { return }

    if !dict_has(leaf, "Resources") && inherited.resources != nil {
        dict_set(leaf, "Resources", inherited.resources)
    }
    if !dict_has(leaf, "MediaBox") && inherited.media_box != nil {
        dict_set(leaf, "MediaBox", inherited.media_box)
    }
    if !dict_has(leaf, "CropBox") && inherited.crop_box != nil {
        dict_set(leaf, "CropBox", inherited.crop_box)
    }
    if !dict_has(leaf, "Rotate") && inherited.rotate != nil {
        dict_set(leaf, "Rotate", inherited.rotate)
    }

    append(&doc.pages, leaf)
    append(&doc.page_refs, ref)
}

// pagetree_scan finds pages by looking at every object in the file, for
// documents whose catalog or page tree is unusable.
//
// The order is object number order, which is not document order. It is the only
// ordering available once the tree is gone, and it is right far more often than
// it is wrong: nearly every producer writes pages in order.
@(private)
pagetree_scan :: proc(doc: ^Document) {
    for num in 1 ..< len(doc.xref) {
        if len(doc.pages) >= MAX_PAGES { break }
        ref := Ref{u32(num), doc.xref[num].gen}
        d, ok := to_dict(get_object(doc, ref))
        if !ok { continue }
        // Without a tree to place them, only an explicit /Type /Page is
        // trustworthy: a resource dictionary or an annotation would otherwise
        // be swept up as a page.
        if dict_type(doc, d) != "Page" { continue }
        pagetree_inherit_upwards(doc, d)
        append(&doc.pages, d)
        append(&doc.page_refs, ref)
    }
    if len(doc.pages) > 0 {
        add_repair(doc, .Missing_Page_Node, 0, {})
    }
}

// pagetree_inherit_upwards resolves inheritance by following /Parent, for pages
// that were found by scanning and so have no known path from the root.
//
// The visited set is what makes this safe: a /Parent chain that loops back on
// itself is a real thing in damaged files, and is the whole reason the normal
// path walks downwards instead.
@(private)
pagetree_inherit_upwards :: proc(doc: ^Document, leaf: ^Dict) {
    visited: map[u32]bool
    defer delete(visited)

    node := leaf
    for _ in 0 ..< MAX_DEPTH {
        parent_ref, has_ref := dict_ref(node, "Parent")
        if has_ref {
            if visited[parent_ref.num] or_else false {
                add_repair(doc, .Cyclic_Page_Tree, 0, parent_ref)
                return
            }
            visited[parent_ref.num] = true
        }
        parent, ok := to_dict(dict_get(doc, node, "Parent"))
        if !ok || parent == leaf { return }

        if !dict_has(leaf, "Resources") && dict_has(parent, "Resources") {
            dict_set(leaf, "Resources", dict_get_raw(parent, "Resources"))
        }
        if !dict_has(leaf, "MediaBox") && dict_has(parent, "MediaBox") {
            dict_set(leaf, "MediaBox", dict_get_raw(parent, "MediaBox"))
        }
        if !dict_has(leaf, "CropBox") && dict_has(parent, "CropBox") {
            dict_set(leaf, "CropBox", dict_get_raw(parent, "CropBox"))
        }
        if !dict_has(leaf, "Rotate") && dict_has(parent, "Rotate") {
            dict_set(leaf, "Rotate", dict_get_raw(parent, "Rotate"))
        }
        node = parent
    }
}

// ---------------------------------------------------------------------------
// Public page access
// ---------------------------------------------------------------------------

// page_count is the number of pages the document has.
//
// This is the flattened count, not the catalog's /Count, which is a hint that
// damaged files get wrong and which this library never trusts.
page_count :: proc(doc: ^Document) -> int {
    if doc == nil { return 0 }
    return len(doc.pages)
}

// page_get returns page `index`, 0-based, with inherited attributes resolved
// and every geometric value guaranteed finite.
page_get :: proc(doc: ^Document, index: int) -> (page: Page, err: Error) {
    if doc == nil { return {}, .Invalid_Argument }
    if index < 0 || index >= len(doc.pages) { return {}, .Page_Out_Of_Range }

    d := doc.pages[index]
    page.doc   = doc
    page.index = index
    page.dict  = d
    if index < len(doc.page_refs) {
        page.ref = doc.page_refs[index]
    }
    page.resources = dict_dict(doc, d, "Resources")

    // A missing, unparsable or zero-area /MediaBox is common enough -- and
    // fatal enough to a renderer that divides by the page height -- that a
    // substitute is the only sane answer. Viewers all pick one; this one picks
    // A4, which is right more often than Letter outside North America and
    // wrong by a survivable margin either way.
    mb := dict_rect(doc, d, "MediaBox", RECT_EMPTY)
    if rect_is_empty(mb) || !rect_is_finite(mb) {
        mb = DEFAULT_PAGE_RECT
    }
    page.media_box = mb

    // /CropBox is required to lie inside /MediaBox; when it does not, the
    // intersection is what the format says to display (ISO 32000-2, 14.11.2).
    cb := dict_rect(doc, d, "CropBox", RECT_EMPTY)
    if rect_is_empty(cb) || !rect_is_finite(cb) {
        cb = mb
    } else {
        cb = rect_intersect(cb, mb)
        if rect_is_empty(cb) {
            cb = mb
        }
    }
    page.crop_box = cb

    page.rotate = page_normalize_rotate(dict_int(doc, d, "Rotate", 0))

    // /UserUnit is inheritable in no version of the format, so it is read from
    // the page alone. A non-positive or non-finite value means the producer
    // wrote nonsense; 1 is the default and the only safe substitute.
    page.user_unit = dict_num(doc, d, "UserUnit", 1)
    if !is_finite(page.user_unit) || page.user_unit <= 0 {
        page.user_unit = 1
    }

    return page, .None
}

// page_normalize_rotate folds /Rotate into 0, 90, 180 or 270.
//
// The format requires a multiple of 90 and files write 45, 360 and -90 anyway.
// Negatives are legal and mean anticlockwise; the rest are rounded down to the
// quarter turn below them, which is what viewers do.
@(private)
page_normalize_rotate :: proc(raw: i64) -> int {
    // Reduced in i64 first: /Rotate is file-controlled and can arrive as a
    // value whose magnitude would overflow a narrower type.
    r := raw % 360
    if r < 0 { r += 360 }
    return int(r / 90 * 90)
}

// page_index_of returns the position of a page object in the flattened list, or
// -1. Destinations and outline entries name a page by reference, and this is
// how they become a page number.
page_index_of :: proc(doc: ^Document, ref: Ref) -> int {
    if doc == nil || ref.num == 0 { return -1 }
    for r, i in doc.page_refs {
        if r.num == ref.num { return i }
    }
    return -1
}


// ---------------------------------------------------------------------------
// Page geometry and content
//
// These three are what a consumer of the library reaches for first: how big is
// the page, how big is the bitmap, and what does it draw. They are deliberately
// not methods on the Document -- a Page is a value, cheap to copy, and holds
// everything they need.
// ---------------------------------------------------------------------------

// page_bounds is the rectangle a viewer displays: the crop box, already
// intersected with the media box by page_get, and guaranteed finite and
// non-empty.
page_bounds :: proc(page: ^Page) -> Rect {
    if page == nil { return DEFAULT_PAGE_RECT }
    return page.crop_box
}

// page_size is the pixel size of the page at `scale`, with /Rotate applied, so
// a page rotated 90 degrees comes back landscape. /UserUnit is included:
// ignoring it renders a large-format drawing at the wrong size.
//
// The result is clamped to at least 1x1 -- a zero-sized bitmap is not something
// a caller can do anything useful with, and every path that produces one here
// comes from a damaged page.
page_size :: proc(page: ^Page, scale: f64 = 1) -> (width, height: int) {
    if page == nil { return 1, 1 }
    r := page_bounds(page)
    unit := page.user_unit
    if !is_finite(unit) || unit <= 0 { unit = 1 }
    s := scale * unit
    if !is_finite(s) || s <= 0 { s = 1 }

    w := rect_width(r) * s
    h := rect_height(r) * s
    if page.rotate == 90 || page.rotate == 270 {
        w, h = h, w
    }
    if !is_finite(w) || !is_finite(h) { return 1, 1 }

    // Round outward, not to nearest: a page 100.2 pixels wide needs 101
    // columns, or the last fraction of content falls off the right edge. The
    // epsilon keeps an exact 200.0 -- which floating-point scaling routinely
    // renders as 200.00000000000003 -- from claiming a 201st column.
    width  = max(1, int(math.ceil(w - 1e-9)))
    height = max(1, int(math.ceil(h - 1e-9)))
    return
}

// page_content concatenates the page's content streams into one buffer,
// allocated with `allocator` and owned by the caller.
//
// /Contents is one stream or an array of them, and the format explicitly allows
// a single operator -- even a single token -- to be split across the boundary
// between two of them (ISO 32000-2, 7.8.2). They are therefore joined with a
// newline between, never concatenated bare, or "1 0 0 1 50" + "50 cm" would
// lex as "501" and "cm". A stream that fails to decode contributes nothing and
// leaves the rest intact, because one broken stream should not blank the page.
page_content :: proc(page: ^Page, allocator := context.allocator) -> (data: []byte, err: Error) {
    if page == nil || page.doc == nil { return nil, .Invalid_Argument }
    doc := page.doc

    out := make([dynamic]byte, 0, 4096, allocator)
    contents := dict_get(doc, page.dict, "Contents")

    add :: proc(doc: ^Document, out: ^[dynamic]byte, s: ^Stream) {
        if s == nil { return }
        bytes, derr := stream_data(doc, s)
        if derr != .None || len(bytes) == 0 { return }
        if len(out) > 0 {
            append(out, byte('\n'))
        }
        append(out, ..bytes)
    }

    #partial switch v in contents {
    case ^Stream:
        add(doc, &out, v)
    case ^Array:
        // Cap the number of parts: /Contents is attacker-controlled, and an
        // array of a million references would otherwise be walked in full.
        n := min(array_len(v), MAX_CONTENT_PARTS)
        for i in 0 ..< n {
            s, ok := to_stream(array_get(doc, v, i))
            if ok {
                add(doc, &out, s)
            }
        }
    }

    return out[:], .None
}

// MAX_CONTENT_PARTS bounds the /Contents array. Real documents use one stream,
// or a handful when a producer emits one per layer; a thousand is already
// pathological.
MAX_CONTENT_PARTS :: 4096