pdf-odin-llm/raster_test.odin

package pdf

import "core:math"
import "core:mem"
import "core:testing"
import "core:time"

// ---------------------------------------------------------------------------
// Span recorder
//
// Every test drives the rasteriser through this, so the ordering and bounds
// contract -- increasing y, increasing x within a row, no overlapping runs,
// nothing outside the clip -- is checked by every case rather than by one
// dedicated test that the others could quietly violate.
// ---------------------------------------------------------------------------

@(private)
Raster_Recorder :: struct {
    clip:      Raster_Clip,
    w, h:      int,
    grid:      []u8,
    n_spans:   int,
    total:     int,
    ordered:   bool,
    in_bounds: bool,
    disjoint:  bool,
    nonempty:  bool,
    nonzero:   bool,
    last_y:    int,
    last_end:  int,
}

@(private)
raster_rec_make :: proc(clip: Raster_Clip) -> Raster_Recorder {
    w := clip.x1 - clip.x0
    h := clip.y1 - clip.y0
    return Raster_Recorder{
        clip      = clip,
        w         = w,
        h         = h,
        grid      = make([]u8, max(w * h, 1)),
        ordered   = true,
        in_bounds = true,
        disjoint  = true,
        nonempty  = true,
        nonzero   = true,
        last_y    = min(int),
        last_end  = min(int),
    }
}

@(private)
raster_rec_destroy :: proc(rec: ^Raster_Recorder) {
    delete(rec.grid)
    rec.grid = nil
}

@(private)
raster_rec_at :: proc(rec: ^Raster_Recorder, x, y: int) -> u8 {
    ix := x - rec.clip.x0
    iy := y - rec.clip.y0
    if ix < 0 || iy < 0 || ix >= rec.w || iy >= rec.h { return 0 }
    return rec.grid[iy * rec.w + ix]
}

@(private)
raster_rec_span :: proc(user: rawptr, y: int, x0: int, coverage: []u8) {
    rec := (^Raster_Recorder)(user)
    rec.n_spans += 1

    if len(coverage) == 0 {
        rec.nonempty = false
        return
    }
    if y < rec.last_y || (y == rec.last_y && x0 < rec.last_end) {
        rec.ordered = false
    }
    rec.last_y = y
    rec.last_end = x0 + len(coverage)

    for c, i in coverage {
        x := x0 + i
        if c == 0 { rec.nonzero = false }
        rec.total += int(c)
        ix := x - rec.clip.x0
        iy := y - rec.clip.y0
        if ix < 0 || iy < 0 || ix >= rec.w || iy >= rec.h {
            rec.in_bounds = false
            continue
        }
        if rec.grid[iy * rec.w + ix] != 0 { rec.disjoint = false }
        rec.grid[iy * rec.w + ix] = c
    }
}

@(private)
raster_rec_check :: proc(t: ^testing.T, rec: ^Raster_Recorder, loc := #caller_location) {
    testing.expect(t, rec.ordered,   "spans must arrive in increasing y then x", loc = loc)
    testing.expect(t, rec.in_bounds, "spans must lie inside the clip", loc = loc)
    testing.expect(t, rec.disjoint,  "spans must not overlap", loc = loc)
    testing.expect(t, rec.nonempty,  "spans must not be empty", loc = loc)
    testing.expect(t, rec.nonzero,   "spans must hold no zero coverage", loc = loc)
}

// Raster_Counter is the recorder for cases whose clip is far too large to
// hold a grid for.
@(private)
Raster_Counter :: struct {
    spans: int,
    total: int,
}

@(private)
raster_count_span :: proc(user: rawptr, y: int, x0: int, coverage: []u8) {
    c := (^Raster_Counter)(user)
    c.spans += 1
    for v in coverage { c.total += int(v) }
}

@(private)
raster_test_add :: proc(fp: ^Flat_Path, closed: bool, pts: []Point) {
    start := len(fp.points)
    append(&fp.points, ..pts)
    append(&fp.subpaths, Flat_Subpath{start = start, count = len(pts), closed = closed})
}

// raster_test_run fills one polygon and returns the recorder, already checked
// for the structural invariants.
@(private)
raster_test_run :: proc(t: ^testing.T, pts: []Point, even_odd: bool, clip: Raster_Clip,
                        loc := #caller_location) -> Raster_Recorder {
    fp := flat_path_make()
    defer flat_path_destroy(&fp)
    raster_test_add(&fp, true, pts)

    rec := raster_rec_make(clip)
    err := raster_fill(&fp, even_odd, clip, raster_rec_span, &rec)
    testing.expect_value(t, err, Error.None, loc = loc)
    raster_rec_check(t, &rec, loc = loc)
    return rec
}

// ---------------------------------------------------------------------------
// Exactness
// ---------------------------------------------------------------------------

// A pixel-aligned square must come out with no fringe at all: every interior
// pixel fully on, every pixel outside it untouched. Anti-aliasing that leaks
// half a pixel of grey along a table rule is the single most visible way to
// get this wrong.
@(test)
test_raster_square_is_exact :: proc(t: ^testing.T) {
    pts := [][2]f64{{2, 3}, {12, 3}, {12, 13}, {2, 13}}
    rec := raster_test_run(t, pts[:], false, Raster_Clip{0, 0, 16, 16})
    defer raster_rec_destroy(&rec)

    bad := 0
    for y in 0 ..< 16 {
        for x in 0 ..< 16 {
            want: u8 = (x >= 2 && x < 12 && y >= 3 && y < 13) ? 255 : 0
            if raster_rec_at(&rec, x, y) != want { bad += 1 }
        }
    }
    testing.expect_value(t, bad, 0)
    // Ten full rows, one run each.
    testing.expect_value(t, rec.n_spans, 10)
    testing.expect_value(t, rec.total, 100 * 255)
}

// Half a pixel of coverage is half of 255. The tolerance is two levels, not
// because the maths is approximate -- it is exact -- but so the assertion is
// about the value and not about a rounding convention.
@(test)
test_raster_half_covered_pixel :: proc(t: ^testing.T) {
    pts := [][2]f64{{0, 0}, {0.5, 0}, {0.5, 1}, {0, 1}}
    rec := raster_test_run(t, pts[:], false, Raster_Clip{0, 0, 4, 4})
    defer raster_rec_destroy(&rec)

    got := int(raster_rec_at(&rec, 0, 0))
    testing.expectf(t, abs(got - 128) <= 2, "half-covered pixel gave %d, want 128", got)
    testing.expect_value(t, raster_rec_at(&rec, 1, 0), u8(0))
    testing.expect_value(t, raster_rec_at(&rec, 0, 1), u8(0))
}

// A rectangle on fractional boundaries has a closed-form coverage for every
// pixel it touches: the product of the overlaps in x and in y. Matching it to
// one level proves the coverage really is analytic in BOTH axes -- a
// sub-scanline sampler would quantise the y factor and fail this.
@(test)
test_raster_fractional_rect_is_analytic :: proc(t: ^testing.T) {
    RX0 :: 1.25
    RY0 :: 0.5
    RX1 :: 4.75
    RY1 :: 3.125

    pts := [][2]f64{{RX0, RY0}, {RX1, RY0}, {RX1, RY1}, {RX0, RY1}}
    rec := raster_test_run(t, pts[:], false, Raster_Clip{0, 0, 8, 8})
    defer raster_rec_destroy(&rec)

    worst := 0
    for y in 0 ..< 8 {
        for x in 0 ..< 8 {
            ox := max(0.0, min(f64(x + 1), RX1) - max(f64(x), RX0))
            oy := max(0.0, min(f64(y + 1), RY1) - max(f64(y), RY0))
            want := int(ox * oy * 255 + 0.5)
            got := int(raster_rec_at(&rec, x, y))
            worst = max(worst, abs(got - want))
        }
    }
    testing.expectf(t, worst <= 1, "worst analytic coverage error was %d levels", worst)
}

// Total coverage is the polygon's area. Shoelace gives the answer to compare
// against, and a fill that is a fraction of a pixel out anywhere -- a
// half-open range applied to the wrong side, a dropped last scanline -- misses
// it by far more than the quantisation slack.
@(test)
test_raster_triangle_area :: proc(t: ^testing.T) {
    pts := [][2]f64{{1.3, 1.7}, {9.1, 2.4}, {4.2, 8.6}}
    area := 0.5 * abs(
        pts[0].x * (pts[1].y - pts[2].y) +
        pts[1].x * (pts[2].y - pts[0].y) +
        pts[2].x * (pts[0].y - pts[1].y))

    for even_odd in ([2]bool{false, true}) {
        rec := raster_test_run(t, pts[:], even_odd, Raster_Clip{0, 0, 12, 12})
        defer raster_rec_destroy(&rec)
        got := f64(rec.total) / 255
        testing.expectf(t, abs(got - area) < 0.15,
            "triangle covered %f pixels, analytic area is %f (even_odd=%v)", got, area, even_odd)
    }
}

// ---------------------------------------------------------------------------
// Fill rules
// ---------------------------------------------------------------------------

// Two concentric squares, wound the same way and wound oppositely, under both
// rules. Three of the four cases punch a hole; only same-winding nonzero fills
// the middle. A rasteriser that ignores the fill rule, or that takes the
// absolute value of the winding before folding it, agrees in all four.
@(test)
test_raster_fill_rules_concentric :: proc(t: ^testing.T) {
    outer := [][2]f64{{0, 0}, {10, 0}, {10, 10}, {0, 10}}
    same  := [][2]f64{{3, 3}, {7, 3}, {7, 7}, {3, 7}}
    opp   := [][2]f64{{3, 3}, {3, 7}, {7, 7}, {7, 3}}

    Case :: struct { inner: [][2]f64, even_odd: bool, middle: u8 }
    cases := []Case{
        {same, false, 255},   // winding 2 -> filled
        {same, true,    0},   // winding 2 -> folded away
        {opp,  false,   0},   // winding 0 -> hole
        {opp,  true,    0},   // winding 0 -> hole
    }

    for c, i in cases {
        fp := flat_path_make()
        defer flat_path_destroy(&fp)
        raster_test_add(&fp, true, outer)
        raster_test_add(&fp, true, c.inner)

        rec := raster_rec_make(Raster_Clip{0, 0, 12, 12})
        defer raster_rec_destroy(&rec)
        testing.expect_value(t, raster_fill(&fp, c.even_odd, rec.clip, raster_rec_span, &rec), Error.None)
        raster_rec_check(t, &rec)

        testing.expectf(t, raster_rec_at(&rec, 5, 5) == c.middle,
            "case %d: middle pixel was %d, want %d", i, raster_rec_at(&rec, 5, 5), c.middle)
        // The ring between the squares is wound once either way, so it is
        // solid in every case; that is what makes the middle the only thing
        // the fill rule changes.
        testing.expectf(t, raster_rec_at(&rec, 1, 1) == 255,
            "case %d: ring pixel was %d, want 255", i, raster_rec_at(&rec, 1, 1))
    }
}

// The same square traced twice in the same direction winds to 2. Nonzero must
// clamp that to solid, not wrap it; even-odd must fold it to nothing.
@(test)
test_raster_double_wound_square :: proc(t: ^testing.T) {
    sq := [][2]f64{{1, 1}, {6, 1}, {6, 6}, {1, 6}}

    for even_odd in ([2]bool{false, true}) {
        fp := flat_path_make()
        defer flat_path_destroy(&fp)
        raster_test_add(&fp, true, sq)
        raster_test_add(&fp, true, sq)

        rec := raster_rec_make(Raster_Clip{0, 0, 8, 8})
        defer raster_rec_destroy(&rec)
        testing.expect_value(t, raster_fill(&fp, even_odd, rec.clip, raster_rec_span, &rec), Error.None)
        raster_rec_check(t, &rec)

        want := 25 * 255 if !even_odd else 0
        testing.expectf(t, rec.total == want,
            "double-wound square totalled %d, want %d (even_odd=%v)", rec.total, want, even_odd)
    }
}

// A self-intersecting figure of eight. The two lobes wind +1 and -1, so both
// rules fill both of them and the total is the sum of the two triangles --
// 25 + 25. A sign error in the winding, or a clamp applied before the fold,
// loses one lobe entirely.
@(test)
test_raster_figure_of_eight :: proc(t: ^testing.T) {
    pts := [][2]f64{{0, 0}, {10, 0}, {0, 10}, {10, 10}}

    for even_odd in ([2]bool{false, true}) {
        rec := raster_test_run(t, pts[:], even_odd, Raster_Clip{0, 0, 12, 12})
        defer raster_rec_destroy(&rec)
        got := f64(rec.total) / 255
        testing.expectf(t, abs(got - 50) < 0.5,
            "figure of eight covered %f pixels, want 50 (even_odd=%v)", got, even_odd)
        // The crossing is at (5,5); both lobes must be present.
        testing.expectf(t, raster_rec_at(&rec, 5, 1) == 255 && raster_rec_at(&rec, 5, 8) == 255,
            "both lobes must be solid (even_odd=%v)", even_odd)
    }
}

// ---------------------------------------------------------------------------
// Degenerate input
// ---------------------------------------------------------------------------

@(test)
test_raster_degenerate_paths :: proc(t: ^testing.T) {
    clip := Raster_Clip{0, 0, 8, 8}

    Case :: struct { name: string, pts: [][2]f64 }
    cases := []Case{
        {"empty",             {}},
        {"single point",      {{2, 2}}},
        {"two equal points",  {{2, 2}, {2, 2}}},
        {"horizontal",        {{1, 4}, {7, 4}}},
        {"three collinear",   {{1, 4}, {4, 4}, {7, 4}}},
        {"vertical",          {{4, 1}, {4, 7}}},
        {"zero-area square",  {{3, 3}, {3, 3}, {3, 3}, {3, 3}}},
    }

    for c in cases {
        fp := flat_path_make()
        defer flat_path_destroy(&fp)
        if len(c.pts) > 0 { raster_test_add(&fp, false, c.pts) }

        rec := raster_rec_make(clip)
        defer raster_rec_destroy(&rec)
        err := raster_fill(&fp, false, clip, raster_rec_span, &rec)
        testing.expectf(t, err == .None, "%s returned %v", c.name, err)
        testing.expectf(t, rec.n_spans == 0, "%s emitted %d spans", c.name, rec.n_spans)
    }
}

// A path outside the clip costs nothing and paints nothing, whichever side it
// is on.
@(test)
test_raster_outside_clip :: proc(t: ^testing.T) {
    clip := Raster_Clip{10, 10, 20, 20}
    offsets := [][2]f64{{-40, 0}, {40, 0}, {0, -40}, {0, 40}, {40, 40}}

    for off in offsets {
        pts := [][2]f64{
            {12 + off.x, 12 + off.y}, {18 + off.x, 12 + off.y},
            {18 + off.x, 18 + off.y}, {12 + off.x, 18 + off.y},
        }
        rec := raster_test_run(t, pts[:], false, clip)
        defer raster_rec_destroy(&rec)
        testing.expectf(t, rec.n_spans == 0, "offset %v emitted %d spans", off, rec.n_spans)
    }
}

// A shape larger than the clip is bounded by it exactly: the clip fills solid
// and nothing is reported outside. This is the case that decides whether the
// left-hand winding of a clipped-away edge survives -- drop it and the whole
// region comes out empty.
@(test)
test_raster_clips_oversized_shape :: proc(t: ^testing.T) {
    clip := Raster_Clip{10, 20, 40, 45}
    pts := [][2]f64{{-500, -500}, {500, -500}, {500, 500}, {-500, 500}}
    rec := raster_test_run(t, pts[:], false, clip)
    defer raster_rec_destroy(&rec)

    testing.expect_value(t, rec.n_spans, 25)
    testing.expect_value(t, rec.total, 30 * 25 * 255)
}

@(test)
test_raster_rejects_nil_span :: proc(t: ^testing.T) {
    fp := flat_path_make()
    defer flat_path_destroy(&fp)
    raster_test_add(&fp, true, [][2]f64{{0, 0}, {4, 0}, {4, 4}})
    testing.expect_value(t, raster_fill(&fp, false, Raster_Clip{0, 0, 8, 8}, nil, nil), Error.Invalid_Argument)
}

@(test)
test_raster_empty_clip :: proc(t: ^testing.T) {
    fp := flat_path_make()
    defer flat_path_destroy(&fp)
    raster_test_add(&fp, true, [][2]f64{{0, 0}, {4, 0}, {4, 4}})

    for clip in ([]Raster_Clip{{0, 0, 0, 8}, {0, 0, 8, 0}, {5, 0, 2, 8}, {0, 5, 8, 2}}) {
        rec := raster_rec_make(Raster_Clip{0, 0, 8, 8})
        defer raster_rec_destroy(&rec)
        testing.expect_value(t, raster_fill(&fp, false, clip, raster_rec_span, &rec), Error.None)
        testing.expect_value(t, rec.n_spans, 0)
    }
}

// An unclosed subpath fills as though it were closed: that is what `f` means,
// and a triangle drawn with two lines and no `h` is ordinary content.
@(test)
test_raster_closes_subpaths_implicitly :: proc(t: ^testing.T) {
    pts := [][2]f64{{1, 1}, {9, 1}, {9, 9}, {1, 9}}

    fp_open := flat_path_make()
    defer flat_path_destroy(&fp_open)
    raster_test_add(&fp_open, false, pts)

    fp_closed := flat_path_make()
    defer flat_path_destroy(&fp_closed)
    raster_test_add(&fp_closed, true, pts)

    a := raster_rec_make(Raster_Clip{0, 0, 12, 12})
    defer raster_rec_destroy(&a)
    b := raster_rec_make(Raster_Clip{0, 0, 12, 12})
    defer raster_rec_destroy(&b)

    testing.expect_value(t, raster_fill(&fp_open,   false, a.clip, raster_rec_span, &a), Error.None)
    testing.expect_value(t, raster_fill(&fp_closed, false, b.clip, raster_rec_span, &b), Error.None)

    testing.expect_value(t, a.total, 64 * 255)
    testing.expect_value(t, a.total, b.total)
    testing.expect_value(t, a.n_spans, b.n_spans)
}

// ---------------------------------------------------------------------------
// Robustness
// ---------------------------------------------------------------------------

// Coordinates like 1e9 are ordinary in content streams -- a "clip to
// everything" rectangle usually is one. The cost must follow the clip, not the
// path, so this is timed as well as checked: a rasteriser that iterates the
// path's scanlines instead of the clip's runs for hours here.
@(test)
test_raster_huge_coordinates_terminate :: proc(t: ^testing.T) {
    clip := Raster_Clip{0, 0, 100, 100}
    B :: 1e9

    Case :: struct { name: string, pts: [][2]f64, want_total: int }
    cases := []Case{
        {"covers clip",   {{-B, -B}, {B, -B}, {B, B}, {-B, B}}, 100 * 100 * 255},
        {"tall spike",    {{-B, -B}, {B, -B}, {0, B}},          100 * 100 * 255},
        {"far away",      {{B, B}, {B + 10, B}, {B + 10, B + 10}}, 0},
        {"one huge vertex", {{10, 10}, {B, 20}, {10, 30}},      -1},
    }

    for c in cases {
        start := time.now()
        rec := raster_test_run(t, c.pts, false, clip)
        defer raster_rec_destroy(&rec)
        ms := time.duration_milliseconds(time.since(start))

        testing.expectf(t, ms < 250, "%s took %f ms", c.name, ms)
        if c.want_total >= 0 {
            testing.expectf(t, rec.total == c.want_total,
                "%s totalled %d, want %d", c.name, rec.total, c.want_total)
        }
    }

}

// The mirror image of the case above: a small path inside an enormous clip.
// The cost has to follow the path there, so nothing may be allocated or
// iterated per row of the clip -- a million-row clip would otherwise mean a
// million-entry scanline table before a single pixel was touched.
@(test)
test_raster_small_path_in_huge_clip :: proc(t: ^testing.T) {
    fp := flat_path_make()
    defer flat_path_destroy(&fp)
    raster_test_add(&fp, true, [][2]f64{{500000, 400000}, {500010, 400000}, {500010, 400010}, {500000, 400010}})

    count := Raster_Counter{}
    start := time.now()
    err := raster_fill(&fp, false, Raster_Clip{0, 0, 1000000, 1000000}, raster_count_span, &count)
    ms := time.duration_milliseconds(time.since(start))

    testing.expect_value(t, err, Error.None)
    testing.expectf(t, ms < 250, "small path in a huge clip took %f ms", ms)
    testing.expect_value(t, count.spans, 10)
    testing.expect_value(t, count.total, 100 * 255)
}

// raster_test_measure fills through a tracking allocator and reports what the
// fill cost in allocations and in bytes.
@(private)
raster_test_measure :: proc(t: ^testing.T, fp: ^Flat_Path, clip: Raster_Clip,
                            loc := #caller_location) -> (calls: int, bytes: int) {
    track: mem.Tracking_Allocator
    mem.tracking_allocator_init(&track, context.allocator)
    defer mem.tracking_allocator_destroy(&track)

    count := Raster_Counter{}
    err := raster_fill(fp, false, clip, raster_count_span, &count, mem.tracking_allocator(&track))
    testing.expect_value(t, err, Error.None, loc = loc)
    testing.expectf(t, len(track.allocation_map) == 0,
        "raster_fill leaked %d allocations", len(track.allocation_map), loc = loc)
    return int(track.total_allocation_count), int(track.total_memory_allocated)
}

// Two things at once, both of them contract rather than taste.
//
// Nothing is allocated per scanline: a path 400 rows tall must cost the same
// number of allocations as one 4 rows tall.
//
// And the working set follows the path rather than the clip: the same small
// path against a clip a thousand times taller must not allocate a byte more,
// which is what stops a 300 dpi page from building a scanline table for rows
// no edge will ever reach.
@(test)
test_raster_allocation_is_bounded :: proc(t: ^testing.T) {
    short := flat_path_make()
    defer flat_path_destroy(&short)
    raster_test_add(&short, true, [][2]f64{{1, 1}, {5, 1}, {5, 5}, {1, 5}})

    tall := flat_path_make()
    defer flat_path_destroy(&tall)
    raster_test_add(&tall, true, [][2]f64{{1, 1}, {5, 1}, {5, 401}, {1, 401}})

    short_calls, short_bytes := raster_test_measure(t, &short, Raster_Clip{0, 0, 8, 8})
    tall_calls,  _           := raster_test_measure(t, &tall,  Raster_Clip{0, 0, 8, 512})
    huge_calls,  huge_bytes  := raster_test_measure(t, &short, Raster_Clip{0, 0, 8, 100000})

    testing.expectf(t, short_calls <= 8, "a fill took %d allocations", short_calls)
    testing.expectf(t, tall_calls == short_calls,
        "a path 100x taller took %d allocations against %d", tall_calls, short_calls)
    testing.expectf(t, huge_calls == short_calls && huge_bytes == short_bytes,
        "a clip 12000x taller cost %d allocations / %d bytes against %d / %d",
        huge_calls, huge_bytes, short_calls, short_bytes)
}

// path.odin filters non-finite coordinates on the way in, but a Flat_Path can
// also come from a transform that overflowed, so the rasteriser guards them
// itself rather than trusting its caller.
//
// The guard clamps rather than discards, and that distinction is the whole
// assertion here: dropping a segment because one end is infinite breaks the
// polygon open and loses everything the remaining edges were enclosing, while
// pulling that end back to the edge of the world keeps it closed and fills
// what the geometry meant. An infinite rectangle fills to the wall.
@(test)
test_raster_non_finite_coordinates :: proc(t: ^testing.T) {
    nan := math.nan_f64()
    inf := math.INF_F64
    clip := Raster_Clip{0, 0, 8, 8}

    open_right := raster_test_run(t, [][2]f64{{2, 2}, {inf, 2}, {inf, 6}, {2, 6}}, false, clip)
    defer raster_rec_destroy(&open_right)
    testing.expect_value(t, open_right.total, 6 * 4 * 255)

    open_left := raster_test_run(t, [][2]f64{{-inf, 2}, {6, 2}, {6, 6}, {-inf, 6}}, false, clip)
    defer raster_rec_destroy(&open_left)
    testing.expect_value(t, open_left.total, 6 * 4 * 255)

    // The rest have no defensible answer; the contract for them is only that
    // the rasteriser returns, stays inside the clip, and keeps its spans in
    // order -- all of which raster_test_run checks.
    paths := [][][2]f64{
        {{nan, 0}, {8, 0}, {8, 8}},
        {{0, nan}, {8, 0}, {8, 8}},
        {{inf, inf}, {-inf, inf}, {0, -inf}},
        {{nan, nan}, {nan, nan}, {nan, nan}},
        {{1, 1}, {7, nan}, {7, 7}, {nan, 7}},
    }
    for pts in paths {
        rec := raster_test_run(t, pts, false, clip)
        defer raster_rec_destroy(&rec)
        testing.expect(t, rec.total >= 0)
    }
}

// raster_test_tangle fills `n` points of a dense self-crossing scribble into
// `fp`, all of it inside a 64-pixel box.
@(private)
raster_test_tangle :: proc(fp: ^Flat_Path, n: int, ry: f64) {
    start := len(fp.points)
    for i in 0 ..< n {
        a := f64(i) * 0.31
        append(&fp.points, Point{32 + 30 * math.cos(a), 32 + ry * math.sin(a * 1.7)})
    }
    append(&fp.subpaths, Flat_Subpath{start = start, count = n, closed = true})
}

// A dense self-crossing scribble: thousands of edges live on every scanline at
// once and the winding runs deep, which is where an active-edge list that
// retires an edge one row early or late shows itself.
@(test)
test_raster_many_segments :: proc(t: ^testing.T) {
    fp := flat_path_make()
    defer flat_path_destroy(&fp)
    raster_test_tangle(&fp, 20000, 30)

    rec := raster_rec_make(Raster_Clip{0, 0, 64, 64})
    defer raster_rec_destroy(&rec)
    testing.expect_value(t, raster_fill(&fp, true, rec.clip, raster_rec_span, &rec), Error.None)
    raster_rec_check(t, &rec)
    testing.expect(t, rec.total > 0)
}

// Past MAX_RASTER_EDGES the edge table stops growing and the rest of the path
// is dropped. The shape that comes out is wrong -- that is the point of a cap
// -- but it still comes out, in order, inside the clip, without the table
// having grown to whatever a hostile content stream asked for. Uncapped, the
// same path allocates several hundred megabytes.
@(test)
test_raster_edge_cap :: proc(t: ^testing.T) {
    fp := flat_path_make()
    defer flat_path_destroy(&fp)
    // Kept to a couple of scanlines so the cap is what the test measures
    // rather than the time it takes to sweep a million tall edges.
    raster_test_tangle(&fp, MAX_RASTER_EDGES + (MAX_RASTER_EDGES / 2), 1)

    track: mem.Tracking_Allocator
    mem.tracking_allocator_init(&track, context.allocator)
    defer mem.tracking_allocator_destroy(&track)

    rec := raster_rec_make(Raster_Clip{0, 0, 64, 64})
    defer raster_rec_destroy(&rec)
    err := raster_fill(&fp, true, rec.clip, raster_rec_span, &rec, mem.tracking_allocator(&track))

    testing.expect_value(t, err, Error.None)
    raster_rec_check(t, &rec)
    testing.expect_value(t, len(track.allocation_map), 0)

    peak := int(track.peak_memory_allocated)
    testing.expectf(t, peak < 128 * 1024 * 1024,
        "the edge table peaked at %d bytes", peak)
}

// ---------------------------------------------------------------------------
// Clip windowing
// ---------------------------------------------------------------------------

// Coverage is a property of the path, not of the clip: narrowing the clip must
// reproduce the wider fill exactly over the window they share. This is what
// lets a device split a page into bands.
@(test)
test_raster_clip_window_matches :: proc(t: ^testing.T) {
    pts := [][2]f64{{1.4, 2.2}, {17.6, 4.1}, {14.2, 18.9}, {3.3, 15.5}}

    full := raster_test_run(t, pts[:], false, Raster_Clip{0, 0, 24, 24})
    defer raster_rec_destroy(&full)

    win := Raster_Clip{6, 7, 13, 16}
    part := raster_test_run(t, pts[:], false, win)
    defer raster_rec_destroy(&part)

    bad := 0
    for y in win.y0 ..< win.y1 {
        for x in win.x0 ..< win.x1 {
            if raster_rec_at(&full, x, y) != raster_rec_at(&part, x, y) { bad += 1 }
        }
    }
    testing.expect_value(t, bad, 0)
}

// ---------------------------------------------------------------------------
// Fuzz
// ---------------------------------------------------------------------------

@(private)
raster_test_rand :: proc(state: ^u64) -> u64 {
    // xorshift64*, so the corpus is the same on every machine and a failure
    // can be reproduced from the seed alone.
    x := state^
    x ~= x >> 12
    x ~= x << 25
    x ~= x >> 27
    state^ = x
    return x * 0x2545_f491_4f6c_dd1d
}

@(private)
raster_test_randf :: proc(state: ^u64, lo, hi: f64) -> f64 {
    u := f64(raster_test_rand(state) >> 11) / f64(u64(1) << 53)
    return lo + (hi - lo) * u
}

// raster_test_inside is a deliberately naive reference: cast a ray and count
// signed crossings. Slow, obviously correct, and shares no code with the
// rasteriser, which is the whole point of comparing against it.
@(private)
raster_test_inside :: proc(pts: [][2]f64, px, py: f64, even_odd: bool) -> bool {
    w := 0
    for i in 0 ..< len(pts) {
        a := pts[i]
        b := pts[(i + 1) % len(pts)]
        if (a.y <= py) == (b.y <= py) { continue }
        tx := a.x + (b.x - a.x) * (py - a.y) / (b.y - a.y)
        if tx <= px { continue }
        w += b.y > a.y ? 1 : -1
    }
    return even_odd ? (w & 1) != 0 : w != 0
}

// Random polygons, checked two ways: the structural contract on every span,
// and -- for every pixel the reference says is unambiguously inside or
// unambiguously outside at 12x12 samples -- that the coverage agrees. A
// half-pixel offset, an inverted fill rule or a lost winding all show up as an
// outside pixel that came back painted.
@(test)
test_raster_fuzz_polygons :: proc(t: ^testing.T) {
    SAMPLES :: 12
    clip := Raster_Clip{0, 0, 24, 24}
    seed: u64 = 0x9e37_79b9_7f4a_7c15

    for iter in 0 ..< 40 {
        n := 3 + int(raster_test_rand(&seed) % 8)
        pts := make([][2]f64, n)
        defer delete(pts)
        for &p in pts {
            p = Point{raster_test_randf(&seed, -8, 32), raster_test_randf(&seed, -8, 32)}
        }
        even_odd := (raster_test_rand(&seed) & 1) != 0

        rec := raster_test_run(t, pts, even_odd, clip)
        defer raster_rec_destroy(&rec)

        testing.expectf(t, rec.total <= 24 * 24 * 255,
            "iter %d: total coverage %d exceeds the clip", iter, rec.total)

        for y in 0 ..< 24 {
            for x in 0 ..< 24 {
                n_in := 0
                for sy in 0 ..< SAMPLES {
                    for sx in 0 ..< SAMPLES {
                        px := f64(x) + (f64(sx) + 0.5) / SAMPLES
                        py := f64(y) + (f64(sy) + 0.5) / SAMPLES
                        if raster_test_inside(pts, px, py, even_odd) { n_in += 1 }
                    }
                }
                got := int(raster_rec_at(&rec, x, y))
                if n_in == SAMPLES * SAMPLES {
                    testing.expectf(t, got >= 210,
                        "iter %d: pixel %d,%d is solidly inside but covered %d", iter, x, y, got)
                } else if n_in == 0 {
                    testing.expectf(t, got <= 45,
                        "iter %d: pixel %d,%d is solidly outside but covered %d", iter, x, y, got)
                }
            }
        }
    }
}

// The same corpus, with the clip offset away from the origin and the polygons
// straddling every wall, to exercise the guard cell and the left-hand winding
// substitution rather than the interior.
@(test)
test_raster_fuzz_straddling_clip :: proc(t: ^testing.T) {
    clip := Raster_Clip{7, 11, 23, 29}
    seed: u64 = 0xdead_beef_1234_5678

    for _ in 0 ..< 120 {
        n := 3 + int(raster_test_rand(&seed) % 6)
        pts := make([][2]f64, n)
        defer delete(pts)
        for &p in pts {
            p = Point{raster_test_randf(&seed, -200, 200), raster_test_randf(&seed, -200, 200)}
        }
        rec := raster_test_run(t, pts, (raster_test_rand(&seed) & 1) != 0, clip)
        defer raster_rec_destroy(&rec)
    }
}