pdf-odin-llm/path_test.odin

package pdf

import "core:math"
import "core:testing"

@(test)
test_path_rect_and_bounds :: proc(t: ^testing.T) {
    p := path_make()
    defer path_destroy(&p)

    path_rect(&p, 10, 20, 100, 50)
    testing.expect_value(t, len(p.verbs), 5)   // move, 3 lines, close
    testing.expect_value(t, len(p.points), 4)
    testing.expect_value(t, path_bounds(&p), Rect{10, 20, 110, 70})
    testing.expect_value(t, path_tight_bounds(&p), Rect{10, 20, 110, 70})
}

@(test)
test_path_drops_non_finite :: proc(t: ^testing.T) {
    p := path_make()
    defer path_destroy(&p)

    nan := math.nan_f64()
    path_move_to(&p, nan, 0)
    testing.expect_value(t, len(p.verbs), 0)
    path_move_to(&p, 0, math.INF_F64)
    testing.expect_value(t, len(p.verbs), 0)
    path_curve_to(&p, 0, 0, nan, 1, 2, 3)
    testing.expect_value(t, len(p.verbs), 0)

    path_move_to(&p, 1, 2)
    testing.expect_value(t, len(p.verbs), 1)
}

// "l" before any "m" starts a subpath rather than being dropped: content
// streams do this and viewers accept it.
@(test)
test_path_line_without_move :: proc(t: ^testing.T) {
    p := path_make()
    defer path_destroy(&p)

    path_line_to(&p, 5, 5)
    testing.expect_value(t, len(p.verbs), 1)
    testing.expect_value(t, p.verbs[0], Path_Verb.Move)
}

// A cubic that bulges outside its endpoints must widen the tight box, and the
// tight box must never be larger than the control hull.
@(test)
test_path_tight_bounds_curve :: proc(t: ^testing.T) {
    p := path_make()
    defer path_destroy(&p)

    path_move_to(&p, 0, 0)
    path_curve_to(&p, 0, 100, 100, 100, 100, 0)

    hull := path_bounds(&p)
    tight := path_tight_bounds(&p)

    testing.expect_value(t, hull, Rect{0, 0, 100, 100})
    // Peak of this symmetric curve is at t=0.5: y = 3/4 * 100 = 75.
    testing.expect(t, abs(tight.y1 - 75) < 1e-9, "curve peak should be 75")
    testing.expect_value(t, tight.x0, 0)
    testing.expect_value(t, tight.x1, 100)
    testing.expect_value(t, tight.y0, 0)
}

@(test)
test_path_transform :: proc(t: ^testing.T) {
    p := path_make()
    defer path_destroy(&p)

    path_rect(&p, 0, 0, 10, 10)
    path_transform(&p, matrix_mul(scale_matrix(2, 3), translate_matrix(5, 7)))
    testing.expect_value(t, path_bounds(&p), Rect{5, 7, 25, 37})
}

@(test)
test_flatten_line_is_exact :: proc(t: ^testing.T) {
    p := path_make()
    defer path_destroy(&p)
    fp := flat_path_make()
    defer flat_path_destroy(&fp)

    path_move_to(&p, 0, 0)
    path_line_to(&p, 10, 0)
    path_line_to(&p, 10, 10)
    path_close(&p)

    path_flatten(&fp, &p, MATRIX_IDENTITY)
    testing.expect_value(t, flat_path_count(&fp), 1)
    pts := flat_path_slice(&fp, 0)
    testing.expect_value(t, len(pts), 3)
    testing.expect_value(t, pts[0], Point{0, 0})
    testing.expect_value(t, pts[2], Point{10, 10})
    testing.expect(t, fp.subpaths[0].closed, "subpath should be closed")
}

// Flattening twice into one Flat_Path must produce two independent subpaths --
// the clip stack and tiling patterns both rely on it.
@(test)
test_flatten_accumulates :: proc(t: ^testing.T) {
    a := path_make(); defer path_destroy(&a)
    b := path_make(); defer path_destroy(&b)
    fp := flat_path_make(); defer flat_path_destroy(&fp)

    path_rect(&a, 0, 0, 10, 10)
    path_rect(&b, 100, 100, 10, 10)
    path_flatten(&fp, &a, MATRIX_IDENTITY)
    path_flatten(&fp, &b, MATRIX_IDENTITY)

    testing.expect_value(t, flat_path_count(&fp), 2)
    testing.expect_value(t, len(flat_path_slice(&fp, 0)), 4)
    testing.expect_value(t, len(flat_path_slice(&fp, 1)), 4)
    testing.expect_value(t, flat_path_slice(&fp, 1)[0], Point{100, 100})
}

// Every flattened point must lie within the flatness tolerance of the true
// curve, and the segment count must stay sane.
@(test)
test_flatten_curve_tolerance :: proc(t: ^testing.T) {
    p := path_make(); defer path_destroy(&p)
    fp := flat_path_make(); defer flat_path_destroy(&fp)

    path_move_to(&p, 0, 0)
    path_curve_to(&p, 0, 100, 100, 100, 100, 0)
    path_flatten(&fp, &p, MATRIX_IDENTITY)

    pts := flat_path_slice(&fp, 0)
    testing.expect(t, len(pts) > 4, "curve should subdivide")
    testing.expect(t, len(pts) < 400, "curve should not over-subdivide")
    testing.expect_value(t, pts[0], Point{0, 0})
    testing.expect_value(t, pts[len(pts) - 1], Point{100, 0})

    // Every sampled point of the true curve must lie close to the polyline.
    // Measure to the nearest *segment*, not the nearest vertex: with coarse
    // subdivision a sample halfway along a segment is far from both of its
    // endpoints while the polyline itself is still accurate.
    eval :: proc(t_: f64) -> Point {
        mt := 1 - t_
        x := 3 * mt * t_ * t_ * 100 + t_ * t_ * t_ * 100
        y := 3 * mt * mt * t_ * 100 + 3 * mt * t_ * t_ * 100
        return Point{x, y}
    }
    dist_to_segment :: proc(p, a, b: Point) -> f64 {
        vx := b.x - a.x
        vy := b.y - a.y
        len2 := vx * vx + vy * vy
        u := len2 == 0 ? 0 : ((p.x - a.x) * vx + (p.y - a.y) * vy) / len2
        u = clamp(u, 0, 1)
        dx := p.x - (a.x + u * vx)
        dy := p.y - (a.y + u * vy)
        return math.sqrt(dx * dx + dy * dy)
    }
    worst: f64 = 0
    for i in 0 ..= 200 {
        tv := f64(i) / 200
        want := eval(tv)
        best: f64 = 1e30
        for j in 0 ..< len(pts) - 1 {
            best = min(best, dist_to_segment(want, pts[j], pts[j + 1]))
        }
        worst = max(worst, best)
    }
    testing.expect(t, worst < 1.0, "flattened polyline should stay within a pixel of the curve")
}

// A degenerate curve (all control points equal) must terminate immediately.
@(test)
test_flatten_degenerate_terminates :: proc(t: ^testing.T) {
    p := path_make(); defer path_destroy(&p)
    fp := flat_path_make(); defer flat_path_destroy(&fp)

    path_move_to(&p, 5, 5)
    path_curve_to(&p, 5, 5, 5, 5, 5, 5)
    path_flatten(&fp, &p, MATRIX_IDENTITY)
    testing.expect(t, len(fp.points) < 8, "degenerate curve must not subdivide")
}

@(test)
test_flatten_empty_and_nil :: proc(t: ^testing.T) {
    fp := flat_path_make(); defer flat_path_destroy(&fp)
    p := path_make(); defer path_destroy(&p)

    path_flatten(&fp, &p, MATRIX_IDENTITY)
    testing.expect_value(t, flat_path_count(&fp), 0)
    testing.expect_value(t, len(flat_path_slice(&fp, 0)), 0)
    testing.expect_value(t, len(flat_path_slice(&fp, -1)), 0)
}

// A curve whose endpoints coincide encloses a loop. The chord is zero length,
// so the ordinary flatness test would declare it flat and throw the loop away.
@(test)
test_flatten_closed_loop_curve :: proc(t: ^testing.T) {
    p := path_make(); defer path_destroy(&p)
    fp := flat_path_make(); defer flat_path_destroy(&fp)

    path_move_to(&p, 0, 0)
    path_curve_to(&p, 100, 0, 100, 100, 0, 0)
    path_flatten(&fp, &p, MATRIX_IDENTITY)

    b := flat_path_bounds(&fp)
    testing.expect(t, rect_width(b) > 40, "loop must not collapse in x")
    testing.expect(t, rect_height(b) > 15, "loop must not collapse in y")
    testing.expect(t, len(fp.points) > 8, "loop must subdivide")
}

// A segment after `h` begins a new subpath AT the current point, which the
// close left at the start of the subpath it closed (ISO 32000-2, 8.5.2.1) --
// "even if the new segment begins at the endpoint reached by the h operation".
// Dropping that point loses the connecting segment entirely and leaves a
// one-point subpath, which a fill ignores and a stroke draws as a stray dot.
// The Line and Curve arms of path_flatten must agree about this.
@(test)
test_flatten_segment_after_close_keeps_current_point :: proc(t: ^testing.T) {
    // "m 0 0  l 10 0  h  l 20 0"
    line := path_make(); defer path_destroy(&line)
    path_move_to(&line, 0, 0)
    path_line_to(&line, 10, 0)
    path_close(&line)
    path_line_to(&line, 20, 0)

    lf := flat_path_make(); defer flat_path_destroy(&lf)
    path_flatten(&lf, &line, MATRIX_IDENTITY)
    testing.expect_value(t, flat_path_count(&lf), 2)
    second := flat_path_slice(&lf, 1)
    testing.expect_value(t, len(second), 2)
    testing.expect_value(t, second[0], Point{0, 0})
    testing.expect_value(t, second[1], Point{20, 0})

    // The same shape written with a curve has always behaved this way, and is
    // what the line case is being held to.
    curve := path_make(); defer path_destroy(&curve)
    path_move_to(&curve, 0, 0)
    path_line_to(&curve, 10, 0)
    path_close(&curve)
    path_curve_to(&curve, 20, 0, 20, 0, 20, 0)

    cf := flat_path_make(); defer flat_path_destroy(&cf)
    path_flatten(&cf, &curve, MATRIX_IDENTITY)
    testing.expect_value(t, flat_path_count(&cf), 2)
    testing.expect_value(t, flat_path_slice(&cf, 1)[0], Point{0, 0})
}

// ---------------------------------------------------------------------------
// Flattening what the clip can reach, and only that
// ---------------------------------------------------------------------------

// PF_BOMB is a cubic whose control points are ten trillion units away. It is
// not exotic: it is what an attacker writes, and what a producer emits when a
// transform has gone wrong. The flatness test never gives up on it, so it
// subdivides to MAX_FLATTEN_DEPTH and yields 65 537 points -- a megabyte of
// polyline for one `c`, none of which can be seen.
@(private = "file")
pf_bomb :: proc(p: ^Path, n: int) {
    path_move_to(p, 0, 0)
    for _ in 0 ..< n {
        path_curve_to(p, -4.98e13, 5.61e13, 7.23e13, 9.65e13, -7.82e13, 9.74e13)
    }
}

@(test)
test_path_flatten_culls_what_the_clip_cannot_reach :: proc(t: ^testing.T) {
    p := path_make()
    defer path_destroy(&p)
    pf_bomb(&p, 16)

    fp := flat_path_make()
    defer flat_path_destroy(&fp)
    path_flatten(&fp, &p, MATRIX_IDENTITY)
    // Sixteen of them exhaust the whole-flattening cap, which is the only
    // thing that stood between this and 16 MB.
    testing.expectf(t, len(fp.points) >= MAX_FLATTEN_POINTS,
        "the uncalled flattening should reach the cap, got %d points", len(fp.points))

    flat_path_clear(&fp)
    path_flatten(&fp, &p, MATRIX_IDENTITY, FLATNESS, Rect{-1, -1, 613, 793})
    testing.expectf(t, len(fp.points) <= 64,
        "a page-sized clip reaches none of it: %d points", len(fp.points))
}

// The substitution has to be invisible. A shape that crosses the clip is
// flattened with and without the cull and both are rasterised: the coverage
// inside the clip must agree to the byte, because the chord that replaces an
// unreachable curve lies in the same convex hull the curve did and cannot
// change the winding number of anything the clip covers.
@(private = "file")
Pf_Cov :: struct {
    w, h: int,
    buf:  []u8,
}

@(private = "file")
pf_span :: proc(user: rawptr, y: int, x0: int, coverage: []u8) {
    c := (^Pf_Cov)(user)
    if y < 0 || y >= c.h { return }
    for i in 0 ..< len(coverage) {
        x := x0 + i
        if x < 0 || x >= c.w { continue }
        c.buf[y * c.w + x] = coverage[i]
    }
}

@(private = "file")
pf_coverage :: proc(t: ^testing.T, p: ^Path, cull: Maybe(Rect), even_odd: bool) -> []u8 {
    W :: 120
    H :: 90
    fp := flat_path_make()
    defer flat_path_destroy(&fp)
    path_flatten(&fp, p, MATRIX_IDENTITY, FLATNESS, cull)
    cov := Pf_Cov{w = W, h = H, buf = make([]u8, W * H)}
    err := raster_fill(&fp, even_odd, Raster_Clip{0, 0, W, H}, pf_span, &cov)
    testing.expect_value(t, err, Error.None)
    return cov.buf
}

@(test)
test_path_flatten_cull_draws_the_same_picture :: proc(t: ^testing.T) {
    // Three curves that leave the clip and come back, one that never comes
    // near it, and one wholly inside: the culled and the full flattening have
    // to agree on every pixel.
    p := path_make()
    defer path_destroy(&p)
    path_move_to(&p, 20, 20)
    path_curve_to(&p, 1e6, -1e6, -1e6, 1e6, 100, 70)
    path_curve_to(&p, -4.98e13, 5.61e13, 7.23e13, 9.65e13, 60, 10)
    path_curve_to(&p, 5e5, 5e5, 6e5, 5e5, 90, 80)
    path_curve_to(&p, 30, 85, 25, 40, 20, 20)
    path_close(&p)

    for even_odd in ([2]bool{false, true}) {
        full := pf_coverage(t, &p, nil, even_odd)
        defer delete(full)
        culled := pf_coverage(t, &p, Rect{-1, -1, 121, 91}, even_odd)
        defer delete(culled)

        ink := 0
        diff := 0
        first := -1
        for i in 0 ..< len(full) {
            if full[i] != 0 { ink += 1 }
            if full[i] != culled[i] {
                diff += 1
                if first < 0 { first = i }
            }
        }
        testing.expect(t, ink > 1000, "the shape has to actually cover the clip")
        testing.expectf(t, diff == 0, "even_odd=%v: %d pixels differ, first at (%d,%d)",
            even_odd, diff, first % 120, first / 120)
    }
}