package pdf

import "core:mem"
import "core:strings"

// The document outline (bookmarks), destinations and page labels.
//
// None of this draws anything: it is the navigation model a viewer needs
// around the page it is showing -- the tree down the side, where a bookmark
// jumps to, and the "iv" it puts in the page box instead of "4".
//
// A destination is the format's way of naming a position: a page, a view
// (`/XYZ`, `/Fit`, ...), and the coordinates that view takes. It can be
// written out in full, or named, in which case it is looked up in the
// catalog's `/Dests` dictionary (PDF 1.1) or its `/Names /Dests` name tree
// (PDF 1.2 and later). Both spellings are still produced.
//
// The outline is a doubly linked tree -- `/First` and `/Last` down, `/Next`
// and `/Prev` across, `/Parent` up -- and not an array, so a file that gets
// one link wrong hands the reader an infinite loop rather than a short tree.
// Every walk here is bounded three ways: a depth cap, a sibling cap, and a
// visited set of the dictionaries already placed in the tree. The last is what
// catches the common damage, a `/Next` chain that points back at itself.

// ---------------------------------------------------------------------------
// Limits
// ---------------------------------------------------------------------------

// Nesting the outline walk will follow. Real outlines are five or six deep;
// the format sets no limit and a hand-built file can nest until the stack ends.
@(private)
MAX_OUTLINE_DEPTH :: 32

// Items in one sibling chain, and in the whole tree. A file with more than a
// million bookmarks is not one anybody is going to navigate.
@(private)
MAX_OUTLINE_SIBLINGS :: 1 << 16
@(private)
MAX_OUTLINE_ITEMS :: 1 << 20

// Indirections followed while resolving a destination: a name into the /Dests
// dictionary, whose value is a dictionary, whose /D is the array. Three hops
// is the deepest the format defines; the fourth is there so a file that adds
// one more legitimate wrapper still works, and the bound is what stops a name
// that resolves to itself.
@(private)
MAX_DEST_HOPS :: 4

// Bytes of a /P prefix that reach the label, and repetitions of a letter in an
// alphabetic label. Both are file-controlled and both would otherwise let a
// tiny file ask for an enormous string.
@(private)
MAX_LABEL_PREFIX :: 512
@(private)
MAX_LABEL_LETTERS :: 64

// Largest value written as a Roman numeral. Above it the numeral would be a
// row of thousands with no information in it, so the number is written in
// decimal instead -- which is what a viewer showing "page 40000" wants anyway.
@(private)
MAX_LABEL_ROMAN :: 32767

// ---------------------------------------------------------------------------
// Destinations
// ---------------------------------------------------------------------------

// Dest_Kind is the view a destination asks for (ISO 32000-2, 12.3.2.2). The
// names mirror the format's: /XYZ, /FitH, /FitBV and the rest.
Dest_Kind :: enum u8 {
    XYZ = 0,   // left top zoom -- any of the three may be "unchanged"
    Fit,       // fit the whole page
    Fit_H,     // top: fit the width, with this at the top of the window
    Fit_V,     // left: fit the height
    Fit_R,     // left bottom right top: fit this rectangle
    Fit_B,     // fit the bounding box of the page's contents
    Fit_BH,    // top: fit the bounding box's width
    Fit_BV,    // left: fit the bounding box's height
}

// Destination is a resolved place in this document.
//
// `args` holds the view's numbers in the order the format writes them, and
// `has` says which of them the file actually gave: /XYZ's arguments are
// individually allowed to be null, meaning "leave that one as it is", and a
// zero is a legal coordinate, so the two cannot be told apart by value.
//
// The zero value is NOT a valid destination -- it names page 0. Use
// DESTINATION_NONE, whose page is -1, for "no destination".
Destination :: struct {
    page: int,       // page index, or -1 if the destination named no page here
    kind: Dest_Kind,
    args: [4]f64,
    has:  [4]bool,
}

DESTINATION_NONE :: Destination{page = -1}

// dest_kind_from_name maps a destination's view name.
@(private)
dest_kind_from_name :: proc(name: string) -> (kind: Dest_Kind, ok: bool) {
    switch name {
    case "XYZ":  return .XYZ, true
    case "Fit":  return .Fit, true
    case "FitH": return .Fit_H, true
    case "FitV": return .Fit_V, true
    case "FitR": return .Fit_R, true
    case "FitB": return .Fit_B, true
    case "FitBH": return .Fit_BH, true
    case "FitBV": return .Fit_BV, true
    }
    return .XYZ, false
}

// dest_arg_count is how many numbers follow the view name.
@(private)
dest_arg_count :: proc(kind: Dest_Kind) -> int {
    switch kind {
    case .XYZ:                       return 3
    case .Fit, .Fit_B:               return 0
    case .Fit_H, .Fit_V, .Fit_BH, .Fit_BV: return 1
    case .Fit_R:                     return 4
    }
    return 0
}

// dest_resolve turns any of the forms a destination is written in into a
// Destination.
//
// `obj` may be the destination array itself, a name or string that names one,
// a dictionary with a /D entry (which is both what the name tree stores and
// what a /GoTo action is), or a reference to any of those.
//
// `ok` is false only when nothing destination-shaped was found. A destination
// that is well formed but names a page this document does not have is still
// ok, with `page` -1: that is a broken link, not a broken file, and dropping
// the whole bookmark because its target was deleted loses its title too.
dest_resolve :: proc(doc: ^Document, obj: Object) -> (Destination, bool) {
    if doc == nil {
        return DESTINATION_NONE, false
    }
    o := resolve(doc, obj)
    for _ in 0 ..< MAX_DEST_HOPS {
        #partial switch v in o {
        case ^Array:
            return dest_from_array(doc, v)
        case Name:
            next, found := dest_by_name(doc, transmute([]byte)string(v))
            if !found {
                return DESTINATION_NONE, false
            }
            o = next
        case String:
            next, found := dest_by_name(doc, ([]byte)(v))
            if !found {
                return DESTINATION_NONE, false
            }
            o = next
        case ^Dict:
            // Both /Dests-tree values (<< /D [...] >>) and /GoTo actions
            // (<< /S /GoTo /D [...] >>) put the destination under /D. An
            // action of another kind -- /URI, /Launch -- has no destination in
            // this document, and its /D, if it has one, is not one either.
            if s := dict_name(doc, v, "S"); s != "" && s != "GoTo" {
                return DESTINATION_NONE, false
            }
            d := dict_get(doc, v, "D")
            if is_null(d) {
                return DESTINATION_NONE, false
            }
            o = d
        case:
            return DESTINATION_NONE, false
        }
    }
    return DESTINATION_NONE, false
}

// dest_by_name looks a named destination up in both places one can live.
@(private)
dest_by_name :: proc(doc: ^Document, key: []byte) -> (Object, bool) {
    if doc == nil || doc.catalog == nil {
        return nil, false
    }
    // PDF 1.1: a flat /Dests dictionary in the catalog, keyed by name.
    if dests := dict_dict(doc, doc.catalog, "Dests"); dests != nil {
        if v := dict_get(doc, dests, string(key)); !is_null(v) {
            return v, true
        }
    }
    // PDF 1.2 and later: the /Names /Dests name tree, keyed by string. The two
    // key spaces are distinct in the format and identical in practice, so a
    // name is looked up in the tree and a string in the dictionary as well --
    // producers do mix them, and the bytes are the same either way.
    if names := dict_dict(doc, doc.catalog, "Names"); names != nil {
        if tree := dict_dict(doc, names, "Dests"); tree != nil {
            if v := name_tree_lookup(doc, tree, key); !is_null(v) {
                return v, true
            }
        }
    }
    return nil, false
}

// dest_from_array reads the explicit form, [page /XYZ left top zoom]. An empty
// array names nothing at all and is the one array that is not a destination.
@(private)
dest_from_array :: proc(doc: ^Document, a: ^Array) -> (Destination, bool) {
    dest := DESTINATION_NONE
    if array_len(a) == 0 {
        return dest, false
    }

    // The page is a reference in a destination inside this document and an
    // integer index in one that names a page of another file (a /GoToR
    // action's /D). Files use the integer form locally too.
    first := array_get_raw(a, 0)
    if ref, is_ref := to_ref(first); is_ref {
        dest.page = page_index_of(doc, ref)
    } else if n, is_int := to_int(resolve(doc, first)); is_int {
        if n >= 0 && n < i64(page_count(doc)) {
            dest.page = int(n)
        }
    }

    // A missing or unknown view name leaves .XYZ with nothing set, which means
    // "this page, view unchanged" -- the least surprising thing to do with a
    // destination whose second element a producer got wrong.
    kind, known := dest_kind_from_name(array_name(doc, a, 1))
    if !known {
        return dest, true
    }
    dest.kind = kind

    for i in 0 ..< dest_arg_count(kind) {
        v, is_num := to_number(array_get(doc, a, 2 + i))
        // A null argument is the format's "leave this unchanged", and a
        // non-finite one is a producer bug with the same only sane reading.
        if !is_num || !is_finite(v) {
            continue
        }
        // "A zoom value of 0 has the same meaning as a null value"
        // (ISO 32000-2, 12.3.2.2, Table 151). Producers write it constantly --
        // it is what every /XYZ in the PDF specification itself carries -- and
        // a viewer that took it literally would zoom to nothing.
        if kind == .XYZ && i == 2 && v == 0 {
            continue
        }
        dest.args[i] = v
        dest.has[i] = true
    }
    return dest, true
}

// ---------------------------------------------------------------------------
// The outline
// ---------------------------------------------------------------------------

// Outline_Item is one bookmark.
//
// `page` is `dest.page` repeated, because a viewer building a table of
// contents wants the page and nothing else nine times out of ten.
Outline_Item :: struct {
    title:    string,   // decoded text, never nil, possibly empty
    page:     int,      // resolved page index, or -1
    dest:     Destination,
    open:     bool,     // /Count > 0: this item's children are shown expanded
    children: []Outline_Item,
}

// outline_load reads the document outline.
//
// The whole tree is returned, in the order the file links it. A document with
// no outline gives an empty slice and no error -- that is the common case, not
// a failure.
//
// The result is the caller's, allocated with `allocator`: the item slices and
// every title string. Free it with `outline_destroy`, passing the same
// allocator.
outline_load :: proc(doc: ^Document, allocator := context.allocator) -> ([]Outline_Item, Error) {
    if doc == nil {
        return nil, .Invalid_Argument
    }
    root := dict_dict(doc, doc.catalog, "Outlines")
    if root == nil {
        return nil, .None
    }

    // Keyed by dictionary address, which is stable: get_object caches by
    // object number, so the same reference always yields the same ^Dict. An
    // item reached twice is a damaged tree, and taking it once is what stops
    // both a /Next cycle and a /First that points back at an ancestor.
    visited := make(map[^Dict]bool, 64, context.allocator)
    defer delete(visited)
    visited[root] = true

    budget := MAX_OUTLINE_ITEMS
    items := outline_children(doc, root, 0, &visited, &budget, allocator)
    return items, .None
}

// outline_destroy frees what outline_load returned. `allocator` must be the
// one it was given.
outline_destroy :: proc(items: []Outline_Item, allocator := context.allocator) {
    for it in items {
        delete(it.title, allocator)
        outline_destroy(it.children, allocator)
    }
    if items != nil {
        delete(items, allocator)
    }
}

// outline_children walks one /First .. /Next chain.
@(private)
outline_children :: proc(
    doc: ^Document, parent: ^Dict, depth: int,
    visited: ^map[^Dict]bool, budget: ^int, allocator: mem.Allocator,
) -> []Outline_Item {
    if depth >= MAX_OUTLINE_DEPTH || budget^ <= 0 {
        if depth >= MAX_OUTLINE_DEPTH {
            add_repair(doc, .Recursion_Limit_Hit, 0)
        }
        return nil
    }

    // Gathered in scratch and copied out exactly, so the returned slice has no
    // spare capacity for the caller's `delete` to disagree about.
    list := make([dynamic]Outline_Item, 0, 8, context.allocator)
    defer delete(list)

    node := dict_dict(doc, parent, "First")
    for i := 0; node != nil && i < MAX_OUTLINE_SIBLINGS; i += 1 {
        if budget^ <= 0 {
            break
        }
        if visited[node] or_else false {
            // A /Next or /First that points at an item already in the tree.
            add_repair(doc, .Bad_Page_Object, 0)
            break
        }
        visited[node] = true
        budget^ -= 1

        append(&list, outline_item(doc, node, depth, visited, budget, allocator))
        node = dict_dict(doc, node, "Next")
    }

    if len(list) == 0 {
        return nil
    }
    out := make([]Outline_Item, len(list), allocator)
    copy(out, list[:])
    return out
}

// outline_item reads one node and, recursively, its children.
@(private)
outline_item :: proc(
    doc: ^Document, node: ^Dict, depth: int,
    visited: ^map[^Dict]bool, budget: ^int, allocator: mem.Allocator,
) -> (item: Outline_Item) {
    item.page = -1
    item.dest = DESTINATION_NONE

    // decode_text_string always allocates, so a missing or non-string /Title
    // still gives a string outline_destroy can free unconditionally.
    raw, _ := to_bytes(dict_get(doc, node, "Title"))
    item.title = decode_text_string(raw, allocator)

    // /Count is the number of visible descendants; its sign is what says
    // whether this item is open (ISO 32000-2, 12.3.3). Zero means no children,
    // for which "closed" is the only sensible answer.
    item.open = dict_int(doc, node, "Count", 0) > 0

    // /Dest first, then a /GoTo action's /D: a file may carry both, and /Dest
    // is the one the format says wins.
    target := dict_get(doc, node, "Dest")
    if is_null(target) {
        if a := dict_dict(doc, node, "A"); a != nil {
            target = a
        }
    }
    if !is_null(target) {
        if d, ok := dest_resolve(doc, target); ok {
            item.dest = d
        }
    }
    item.page = item.dest.page

    item.children = outline_children(doc, node, depth + 1, visited, budget, allocator)
    return item
}

// ---------------------------------------------------------------------------
// Page labels
// ---------------------------------------------------------------------------

// page_label is the label a viewer shows for page `index`: "iv" for the fourth
// page of a front matter numbered in lowercase Roman, "A-3" for a page in an
// appendix, "4" when the file says nothing.
//
// The catalog's /PageLabels number tree divides the document into ranges, each
// keyed by the index of its first page and each saying how that range is
// numbered: /S is the style (D, r, R, a, A), /P a prefix put in front of every
// label in the range, and /St the number the range starts at (ISO 32000-2,
// 12.4.2). A range with a /P and no /S labels every one of its pages with the
// prefix alone, which is legal and is how a cover page gets called "Cover".
//
// The result is always freshly allocated with `allocator` and owned by the
// caller, empty string included.
//
// Each call reads the tree: cheap, because a document has a handful of ranges
// and not one per page, but a caller labelling all 900 pages of a long
// document should keep the answers rather than ask again.
page_label :: proc(doc: ^Document, index: int, allocator := context.allocator) -> string {
    b := strings.builder_make(0, 16, allocator)
    if doc == nil || index < 0 {
        return strings.to_string(b)
    }

    entry, start, found := page_label_range(doc, index)
    if !found {
        // No /PageLabels, or none covering this page: the page's own position
        // is what every viewer falls back to.
        strings.write_int(&b, index + 1)
        return strings.to_string(b)
    }

    if raw := dict_bytes(doc, entry, "P"); len(raw) > 0 {
        prefix := decode_text_string(raw[:min(len(raw), MAX_LABEL_PREFIX)], context.allocator)
        defer delete(prefix, context.allocator)
        strings.write_string(&b, prefix)
    }

    style := dict_name(doc, entry, "S")
    if style == "" {
        return strings.to_string(b)
    }

    // /St is required to be at least 1. Clamped rather than rejected, and
    // clamped at the top as well so the arithmetic below cannot overflow.
    st := clamp(dict_int(doc, entry, "St", 1), 1, 1 << 31)
    n := st + i64(index) - start

    switch style {
    case "D":
        strings.write_i64(&b, n)
    case "r":
        label_write_roman(&b, n, false)
    case "R":
        label_write_roman(&b, n, true)
    case "a":
        label_write_alpha(&b, n, false)
    case "A":
        label_write_alpha(&b, n, true)
    }
    // An unknown style contributes nothing: the prefix is still a label, and
    // guessing decimal would put a number on a page the file did not number.
    return strings.to_string(b)
}

// page_label_range finds the /PageLabels entry covering `index`: the one whose
// key is the largest that is not greater than it.
@(private)
page_label_range :: proc(doc: ^Document, index: int) -> (entry: ^Dict, start: i64, found: bool) {
    root := dict_dict(doc, doc.catalog, "PageLabels")
    if root == nil {
        return nil, 0, false
    }

    keys, values := number_tree_collect(doc, root, context.allocator)
    defer delete(keys, context.allocator)
    defer delete(values, context.allocator)

    // Scanned rather than binary-searched: the /Nums arrays are required to be
    // in increasing order and damaged files are not, and a document has a
    // handful of ranges, not thousands.
    for k, i in keys {
        if k < 0 || k > i64(index) {
            continue
        }
        if found && k < start {
            continue
        }
        d, is_dict := to_dict(resolve(doc, values[i]))
        if !is_dict {
            continue
        }
        entry, start, found = d, k, true
    }
    return
}

// label_write_roman writes 1 as "i", 4 as "iv", 1990 as "mcmxc".
@(private)
label_write_roman :: proc(b: ^strings.Builder, n: i64, upper: bool) {
    if n <= 0 {
        return
    }
    if n > MAX_LABEL_ROMAN {
        strings.write_i64(b, n)
        return
    }
    values := [?]i64{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
    lower  := [?]string{"m", "cm", "d", "cd", "c", "xc", "l", "xl", "x", "ix", "v", "iv", "i"}
    upper_ := [?]string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
    rest := n
    for v, i in values {
        for rest >= v {
            strings.write_string(b, upper ? upper_[i] : lower[i])
            rest -= v
        }
    }
}

// label_write_alpha writes 1 as "a", 26 as "z", 27 as "aa", 53 as "aaa" -- the
// format's own scheme, which repeats the letter rather than carrying (12.4.2).
@(private)
label_write_alpha :: proc(b: ^strings.Builder, n: i64, upper: bool) {
    if n <= 0 {
        return
    }
    letter := byte((n - 1) % 26) + (upper ? 'A' : 'a')
    reps := int(min((n - 1) / 26 + 1, MAX_LABEL_LETTERS))
    for _ in 0 ..< reps {
        strings.write_byte(b, letter)
    }
}