package pdf

import "core:math"

// Patterns (ISO 32000-2, 8.7.3 and 8.7.4).
//
// PATTERN SPACE IS ANCHORED TO THE PAGE, NOT TO THE FILL
//
// A pattern's /Matrix maps pattern space to the DEFAULT coordinate space of
// the page -- or of the form XObject, Type 3 glyph or annotation appearance
// stream -- in which the pattern is a resource (8.7.3.1). It does NOT compose
// with the CTM that happens to be in force when the fill runs. So the mapping
// every procedure in this file builds is
//
//     pattern space --(/Matrix)--> default space --(base CTM)--> device
//
// and `ctm` throughout this file means that base CTM: the one the interpreter
// started the content stream with, saved before the first `cm`, never
// `gs.ctm`.
//
// Two fills with the same pattern under different CTMs must therefore land on
// exactly the same lattice. A patterned rectangle drawn twice -- once plainly,
// once inside `q 2 0 0 2 30 40 cm ... Q` -- shows the same hatch, at the same
// phase, in the same place, and only the shape being filled moves. Composing
// with the live CTM instead is the classic pattern bug: the texture slides
// with whatever transform preceded the fill. It looks plausible in isolation
// and is obvious the moment two shapes with different CTMs share an edge, or
// the moment the page is rendered at a second zoom level.
//
// One consequence is worth stating because the interpreter has to act on it: a
// form XObject re-anchors pattern space. A pattern named from a form's
// /Resources is anchored to the form's default space -- the CTM at the moment
// the form was invoked, including the form's own /Matrix -- so entering a form
// means saving a new base CTM, and leaving it means restoring the old one.
// The same goes for a Type 3 glyph and an annotation appearance stream.
//
// WHAT THE INTERPRETER STILL HAS TO DO
//
// `pattern_tiles` says where to replay a tiling cell, not how. For each matrix
// it returns, the interpreter sets the CTM to that matrix, clips to the
// pattern's /BBox (a rotated pattern makes that a path, not a scissor
// rectangle), and runs `content` against `resources`. For an uncoloured
// pattern -- `pattern_needs_color` -- every colour operator inside the cell is
// ignored and the whole cell paints in the colour supplied with the pattern
// name. Recursion into a pattern that fills with a pattern is the
// interpreter's to bound.

Pattern_Kind :: enum u8 {
    Tiling  = 1,
    Shading = 2,
}

Paint_Type :: enum u8 {
    Coloured   = 1,   // the cell supplies its own colour
    Uncoloured = 2,   // the cell is a stencil painted in the caller's colour
}

Tiling_Type :: enum u8 {
    Constant_Spacing            = 1,
    No_Distortion               = 2,
    Faster_Constant_Spacing     = 3,
}

Pattern :: struct {
    kind: Pattern_Kind,
    // Pattern space to the default space of the page or form the pattern is
    // used in -- NOT to the CTM in force when it is painted (8.7.3.1). Getting
    // this wrong makes patterns slide around under a transformed fill.
    mtx:  Matrix,

    // Tiling.
    paint_type:  Paint_Type,
    tiling_type: Tiling_Type,
    bbox:        Rect,
    xstep:       f64,
    ystep:       f64,
    resources:   ^Dict,
    content:     ^Stream,

    // Shading.
    shading:  ^Shading,
    ext_gstate: ^Dict,

    // The Document this was read from. A lattice can only be found to be
    // pathological once the area to cover is known, which is inside
    // `pattern_tiles`, and the repair that records it has to be attached to
    // something.
    doc: ^Document,
    // Set once the tile cap has been reported for this pattern. A page that
    // fills with the same hostile pattern five hundred times should cost one
    // repair, not five hundred crowding every other one out of doc.repairs.
    cap_reported: bool,
}

// ---------------------------------------------------------------------------
// Limits
//
// Each of these bounds a number that came out of a file, on a path any file
// can reach: `/Pattern cs /P1 scn ... f` is three operators.
// ---------------------------------------------------------------------------

// Cells one call may ask the interpreter to replay. A full page at 300 dpi is
// 2550 x 3300 device pixels, so even a 16-pixel cell covering all of it is
// about 33 000 -- this is twice that, and everything past it is a file whose
// /XStep is small enough to make one fill cost a million content streams.
@(private)
MAX_PATTERN_TILES :: 1 << 16

// How many lattice steps a cell may span before the step is treated as
// degenerate rather than as overlapping cells. Cells that overlap are a real
// design -- a brick bond with a bleed, a hatch drawn with a fat pen -- so a
// generous factor is allowed before the step is snapped back to the cell size.
@(private)
MAX_TILE_OVERLAP :: 64.0

// Bound on a lattice index before it is narrowed to an int. The quotients that
// produce the index range are computed from file-derived numbers and can be
// 1e300; converting that to an int is undefined, so the range is clamped in
// f64 first. 2^24 is exact in f64 and is already 16 million cells along one
// axis, far past what the tile cap will let through.
@(private)
MAX_TILE_INDEX :: 1 << 24

// ---------------------------------------------------------------------------
// Loading
// ---------------------------------------------------------------------------

// pattern_load builds the pattern `obj` describes: a stream for a tiling
// pattern (/PatternType 1), whose dictionary carries the pattern entries and
// whose bytes are the cell's content, or a dictionary for a shading pattern
// (/PatternType 2).
//
// `res` is the /Resources dictionary the pattern was named from. It resolves a
// colour space named by a bare name inside a shading pattern's /Shading, and
// it stands in for a tiling pattern that omits its own /Resources.
//
// The result is owned by the Document and must not be freed. Nothing is
// cached: like a shading, a pattern is built once per `scn` that names it, and
// the content stream it points at is decoded by `stream_data`, which caches.
pattern_load :: proc(doc: ^Document, obj: Object, res: ^Dict) -> (^Pattern, Error) {
    if doc == nil {
        return nil, .Invalid_Argument
    }
    o := resolve(doc, obj)
    d, has_dict := to_dict(o)
    if !has_dict {
        return nil, .Bad_Pattern
    }
    stm, is_stream := to_stream(o)

    kind := dict_int(doc, d, "PatternType", 0)
    if kind != 1 && kind != 2 {
        // /PatternType is required, but a file that leaves it out still says
        // plainly which kind it meant: only a tiling pattern is a stream, and
        // only a shading pattern has a /Shading.
        switch {
        case dict_has(d, "Shading"): kind = 2
        case is_stream:              kind = 1
        case:                        return nil, .Bad_Pattern
        }
        add_repair(doc, .Bad_Resource, 0)
    }

    p := Pattern{doc = doc}
    // `object_to_matrix` is the finiteness boundary for a matrix out of a
    // file, so a /Matrix that is short, non-numeric or infinite arrives here
    // as the identity -- which is the format's own default and the only
    // sensible guess.
    p.mtx = dict_matrix(doc, d, "Matrix")

    if kind == 2 {
        p.kind = .Shading
        sh, sh_err := shading_load(doc, dict_get(doc, d, "Shading"), res)
        // A shading pattern is nothing but its shading; with no shading to
        // paint there is no degraded version of it to hand back.
        if sh_err != .None || sh == nil {
            return nil, .Bad_Pattern
        }
        p.shading = sh
        // /ExtGState is applied by the caller: it belongs to the graphics
        // state the shading paints under, not to the shading itself, and it
        // can carry a soft mask that only the interpreter can build.
        p.ext_gstate = dict_dict(doc, d, "ExtGState")
        return pattern_intern(doc, p), .None
    }

    p.kind = .Tiling
    if !is_stream {
        // The cell's content is the stream's own bytes. A tiling pattern
        // written as a bare dictionary has no content at all, and an empty
        // cell tiled across a fill is indistinguishable from not filling.
        return nil, .Bad_Pattern
    }
    p.content = stm

    bbox, bbox_ok := object_to_rect(doc, dict_get(doc, d, "BBox"))
    // Both corners are finite by the time `object_to_rect` returns, but their
    // difference need not be: a /BBox of [-1e308 -1e308 1e308 1e308] has an
    // infinite width, and a step of infinity multiplied by a lattice index of
    // zero is a NaN in the middle of a cell matrix. Nothing below the Device
    // line may see one, and a cell the size of the number line is not a cell.
    bw := rect_width(bbox)
    bh := rect_height(bbox)
    if !bbox_ok || rect_is_empty(bbox) || !is_finite(bw) || !is_finite(bh) {
        // 8.7.3.1: the cell is clipped to /BBox, so a missing or degenerate
        // one clips every cell away to nothing.
        return nil, .Bad_Pattern
    }
    p.bbox  = bbox
    // After this the steps are finite and strictly positive, which is the
    // invariant `pattern_bounds` and `pattern_tiles` are written against.
    p.xstep = pattern_step(doc, dict_num(doc, d, "XStep"), bw)
    p.ystep = pattern_step(doc, dict_num(doc, d, "YStep"), bh)

    // Both are required entries, and an out-of-range value is a broken file
    // rather than a new feature; the defaults are what a viewer shows.
    p.paint_type  = dict_int(doc, d, "PaintType", 1) == 2 ? .Uncoloured : .Coloured
    switch dict_int(doc, d, "TilingType", 1) {
    case 2:  p.tiling_type = .No_Distortion
    case 3:  p.tiling_type = .Faster_Constant_Spacing
    case:    p.tiling_type = .Constant_Spacing
    }

    p.resources = dict_dict(doc, d, "Resources")
    if p.resources == nil {
        // /Resources is required (8.7.3.3), but a cell that only draws
        // rectangles needs nothing out of it, so its absence is not on its own
        // a defect worth recording. Falling back to the resources of the
        // stream that named the pattern is what every viewer does, and it is
        // the only other dictionary in scope; a name that still does not
        // resolve is reported by the interpreter that looks it up.
        p.resources = res
    }
    return pattern_intern(doc, p), .None
}

// pattern_intern copies a finished pattern into the Document arena. Patterns
// are built on the stack first so that a file that fails half way through
// validation costs no arena at all -- an arena is never reclaimed before
// `close`, and a page can name a broken pattern in every one of its fills.
@(private)
pattern_intern :: proc(doc: ^Document, p: Pattern) -> ^Pattern {
    out := new(Pattern, doc.allocator)
    out^ = p
    return out
}

// pattern_step normalises /XStep or /YStep against the size of the cell.
//
// Only the magnitude spaces the lattice, so a negative step is read as its
// absolute value rather than rejected. Zero is forbidden by the format and
// occurs anyway; it would stack every cell of an infinite row at one place, so
// it falls back to the cell size, which is what the step means when cells
// abut.
//
// A step far smaller than the cell is the same denial of service written
// differently: at a thousandth of the cell width every device pixel is covered
// by a thousand cells, and one fill costs a thousand times what it looks like.
// Overlapping cells are a legitimate design, so an overlap of up to
// MAX_TILE_OVERLAP-fold is honoured before the step is snapped to the cell.
@(private)
pattern_step :: proc(doc: ^Document, step, cell: f64) -> f64 {
    s := abs(step)
    if !is_finite(s) || s <= 0 || s * MAX_TILE_OVERLAP < cell {
        add_repair(doc, .Bad_Resource, 0)
        return cell
    }
    return s
}

// ---------------------------------------------------------------------------
// The one composition every caller needs
// ---------------------------------------------------------------------------

// pattern_matrix maps the pattern's own space to device space.
//
// `ctm` is the DEFAULT-space CTM of the page or form the pattern is a resource
// of, not the CTM of the fill being painted -- see the note at the top of this
// file. This is the only place the two are composed, so an interpreter that
// routes everything through here cannot get 8.7.3.1 wrong in one operator and
// right in another.
@(private)
pattern_matrix :: proc(p: ^Pattern, ctm: Matrix) -> Matrix {
    if p == nil {
        return ctm
    }
    return matrix_mul(p.mtx, ctm)
}

// pattern_needs_color reports whether the caller must supply the colour: an
// uncoloured tiling pattern (/PaintType 2) is a stencil, and every colour
// operator inside its cell is ignored in favour of the components given
// alongside the pattern name in `scn` (8.7.3.1). Those components live in the
// underlying colour space of the /Pattern space, which is what
// `Colorspace.under` holds.
@(private)
pattern_needs_color :: proc(p: ^Pattern) -> bool {
    return p != nil && p.kind == .Tiling && p.paint_type == .Uncoloured
}

// ---------------------------------------------------------------------------
// Bounds
// ---------------------------------------------------------------------------

// pattern_bounds is the device-space region the pattern can paint under the
// default-space `ctm`.
//
// A tiling pattern repeats over the whole plane, so the honest answer is
// RECT_INFINITE, the identity for `rect_intersect`: a caller that intersects
// it with the clip gets the clip. A shading pattern is bounded exactly when
// its shading is -- an un-extended radial one is, an axial one is not.
//
// A transform that collapses the plane to a line or a point paints nothing at
// all, and that is RECT_EMPTY rather than RECT_INFINITE, because the two are
// opposite identities and a caller intersecting with the wrong one would fill
// the whole clip with a pattern that has no area.
pattern_bounds :: proc(p: ^Pattern, ctm: Matrix) -> Rect {
    if p == nil || !matrix_is_finite(ctm) {
        return RECT_EMPTY
    }
    m := pattern_matrix(p, ctm)
    if !matrix_is_finite(m) {
        return RECT_EMPTY
    }
    if _, ok := matrix_invert(m); !ok {
        return RECT_EMPTY
    }

    switch p.kind {
    case .Shading:
        // `shading_bounds` answers RECT_EMPTY for a nil shading, which is the
        // right answer and is not worth a second guard here.
        return shading_bounds(p.shading, m)
    case .Tiling:
        // The lattice is infinite in both directions: /XStep and /YStep are
        // finite and non-zero after loading, so there is always another cell.
        return RECT_INFINITE
    }
    return RECT_EMPTY
}

// ---------------------------------------------------------------------------
// Tiling
// ---------------------------------------------------------------------------

// pattern_tiles returns the matrices at which the interpreter must replay a
// tiling pattern's content stream to cover `area`.
//
// Each matrix maps the cell's own space -- the space /BBox is written in -- to
// device space, and already carries the pattern matrix and `ctm`, so the
// interpreter sets the CTM to it, clips to /BBox, and runs the content. Cell
// (i, j) of the lattice is the cell translated by (i * /XStep, j * /YStep) in
// pattern space, so the returned matrices differ only in that translation and
// share the pattern's rotation and scale exactly; the cells cannot drift apart
// at the far end of a long fill.
//
//   area   the device-space region to cover, normally the fill's bounding box
//          intersected with the clip. It must be finite: RECT_INFINITE, an
//          empty rectangle and a NaN one all mean nothing to draw, because
//          "cover an unbounded area with a repeating cell" has no answer.
//   ctm    the DEFAULT-space CTM of the page or form -- see the top of this
//          file. It is emphatically not the CTM of the fill.
//
// An empty slice means nothing to draw, which is also what a shading pattern
// always gets: it paints in one pass rather than as cells. The result is
// allocated with `allocator` and belongs to the caller.
//
// A cell whose /BBox merely touches the edge of `area` is included. It is
// clipped away to a hairline at worst, and being inclusive is what keeps the
// common case -- a lattice exactly aligned with the area, where the quotients
// land on integers -- from dropping a whole row to a rounding error.
pattern_tiles :: proc(p: ^Pattern, area: Rect, ctm: Matrix,
                      allocator := context.allocator) -> []Matrix {
    if p == nil || p.kind != .Tiling || p.content == nil {
        return nil
    }
    // RECT_INFINITE has to be caught by identity, not by is_finite: its
    // corners are 1e30, which is a perfectly finite number, and
    // `transform_rect` passes it through unchanged.
    if area == RECT_INFINITE || !rect_is_finite(area) || rect_is_empty(area) {
        return nil
    }
    if !matrix_is_finite(ctm) || p.xstep <= 0 || p.ystep <= 0 {
        return nil
    }

    m := pattern_matrix(p, ctm)
    if !matrix_is_finite(m) {
        return nil
    }
    inv, invertible := matrix_invert(m)
    if !invertible {
        // A singular pattern matrix collapses every cell to zero area.
        return nil
    }

    // The lattice is regular in pattern space and only there, so the area is
    // taken back into pattern space and the indices are read off directly. For
    // a rotated or skewed pattern the pulled-back rectangle is the bounding
    // box of a rotated one, so a few cells in the corners fall outside the
    // area and are clipped away; that costs a little work and never misses a
    // cell, which is the right way round.
    pa := transform_rect(inv, area)
    if !rect_is_finite(pa) {
        return nil
    }

    // Cell (i, j) spans [bbox.x0 + i*xs, bbox.x1 + i*xs] across, so it meets
    // the area when bbox.x0 + i*xs <= pa.x1 and bbox.x1 + i*xs >= pa.x0.
    i0, i1, ok_x := tile_range(pa.x0, pa.x1, p.bbox.x0, p.bbox.x1, p.xstep)
    j0, j1, ok_y := tile_range(pa.y0, pa.y1, p.bbox.y0, p.bbox.y1, p.ystep)
    if !ok_x || !ok_y {
        return nil
    }

    nx := i1 - i0 + 1
    ny := j1 - j0 + 1
    if nx <= 0 || ny <= 0 {
        return nil
    }
    // In f64 because the product of two clamped index counts overflows no f64
    // but would need care in an int.
    total := f64(nx) * f64(ny)
    n := nx * ny
    if total > f64(MAX_PATTERN_TILES) {
        // Painting fewer cells than were asked for leaves part of the fill
        // bare, which is the least bad of the three options: the whole fill
        // dropped, a lattice respaced to fit (which would show gaps at the
        // wrong pitch and look like a rendering bug rather than a damaged
        // file), or an unbounded amount of work. Row-major truncation keeps
        // the painted part contiguous.
        n = MAX_PATTERN_TILES
        if !p.cap_reported {
            p.cap_reported = true
            add_repair(p.doc, .Bad_Resource, 0)
        }
    }

    out, alloc_err := make([]Matrix, n, allocator)
    if alloc_err != nil {
        return nil
    }
    k := 0
    rows: for j := j0; j <= j1; j += 1 {
        ty := f64(j) * p.ystep
        for i := i0; i <= i1; i += 1 {
            if k >= n {
                break rows
            }
            out[k] = matrix_mul(translate_matrix(f64(i) * p.xstep, ty), m)
            k += 1
        }
    }
    return out
}

// tile_range is the inclusive range of lattice indices whose cell meets
// [lo, hi], for a cell spanning [c0, c1] and a step of `step`.
//
// The quotients are formed from numbers that came out of a file and can be
// enormous, so they are clamped while they are still f64: `int(1e300)` is
// undefined, and the clamp is what makes the tile cap the only thing standing
// between a hostile file and an allocation.
@(private)
tile_range :: proc(lo, hi, c0, c1, step: f64) -> (from, to: int, ok: bool) {
    if step <= 0 || !is_finite(step) {
        return 0, 0, false
    }
    a := math.ceil((lo - c1) / step)
    b := math.floor((hi - c0) / step)
    if !is_finite(a) || !is_finite(b) {
        return 0, 0, false
    }
    a = clamp(a, -MAX_TILE_INDEX, MAX_TILE_INDEX)
    b = clamp(b, -MAX_TILE_INDEX, MAX_TILE_INDEX)
    if b < a {
        return 0, 0, false
    }
    return int(a), int(b), true
}

// ---------------------------------------------------------------------------
// Painting a shading pattern
// ---------------------------------------------------------------------------

// pattern_paint_shading composites a shading pattern's shading onto `bmp`
// through `clip`, which the caller has already narrowed to the shape being
// filled.
//
// This exists so that the pattern matrix is composed in exactly one place:
// everything else about the call is `shading_paint`'s, including that `bmp` is
// premultiplied and that `mask` is an optional soft mask aligned with it in
// device pixels.
//
// `ctm` is the default-space CTM, not the fill's. The pattern's /ExtGState is
// the caller's to apply -- `alpha`, `mode` and `mask` are where its effect
// arrives here.
@(private)
pattern_paint_shading :: proc(doc: ^Document, p: ^Pattern, bmp: ^Bitmap, ctm: Matrix,
                              clip: Raster_Clip, alpha: f64, mode: Blend_Mode,
                              mask: ^Bitmap) -> Error {
    if p == nil || p.kind != .Shading || p.shading == nil {
        return .Invalid_Argument
    }
    return shading_paint(doc, p.shading, bmp, pattern_matrix(p, ctm), clip, alpha, mode, mask)
}