frust-engine 0.6.2

//! Parallel strip generation: shape commands' strips generated by helper
//! threads behind the walk and merged back in painter order produce exactly
//! the frame the sequential walk produces.
//!
//! Every case runs two or more compilers side by side on the same frames: one
//! with a single worker (`set_parallel_workers(1)`, the per-compiler
//! counterpart of `FRUST_ENGINE_NO_PARALLEL`), which generates every strip on
//! the calling thread, and others with helpers and no spawn threshold, so even
//! a small scene is handed to them. Each frame they compile must be identical
//! — the same strips and alphas byte for byte, the same draws at the same
//! depths, the same paints, quads, punches and counters. Only
//! [`CompiledFrame::parallel_draws`] may differ, since it reports who did the
//! generating.
//!
//! Which commands a helper reaches before the walk does is a race, so a case
//! that needs the merge path exercised compiles until a frame reports helper
//! draws rather than assuming the first one will.

#![cfg(not(target_arch = "wasm32"))]

use std::sync::Arc;

use frust_engine::compile::{CompiledFrame, DEFAULT_PARALLEL_MIN_COST, DEFAULT_PARALLEL_WORKERS};
use frust_engine::{SceneCompiler, config};
use frust_scene::{DashPattern, FontHandle, Glyph, GlyphRun, Scene, SceneBuilder};
use kurbo::{Affine, BezPath, Circle, Point, Rect, Shape};
use peniko::color::DynamicColor;
use peniko::{
    Blob, Brush, Color, ColorStop, FontData, Gradient, ImageAlphaType, ImageData, ImageFormat,
};
use proptest::prelude::*;

/// Noto Sans, subsetted to Latin plus combining marks.
const LATIN_FONT: &[u8] = include_bytes!("../../../testing/fonts/NotoSans-Subset.ttf");

/// Glyph ids of `Hello` in [`LATIN_FONT`].
const HELLO: [u32; 5] = [5, 6, 7, 7, 8];

/// A phone-shaped host extent.
const SIZE: (u16, u16) = (360, 640);

/// How many frames a case compiles before it gives up waiting for a helper
/// to have generated anything.
const MERGE_ATTEMPTS: usize = 400;

fn latin_font() -> FontHandle {
    static FONT: std::sync::OnceLock<FontHandle> = std::sync::OnceLock::new();
    FONT.get_or_init(|| FontHandle::new(FontData::new(Blob::new(Arc::new(LATIN_FONT)), 0)))
        .clone()
}

fn label(size: f32, color: Color) -> GlyphRun {
    GlyphRun {
        font: latin_font(),
        font_size: size,
        brush: Brush::Solid(color),
        transform: Affine::IDENTITY,
        glyphs: HELLO
            .iter()
            .enumerate()
            .map(|(index, id)| Glyph {
                id: *id,
                x: index as f32 * size * 0.6,
                y: 0.0,
            })
            .collect(),
    }
}

fn gradient(center: Point, radius: f64, base: Color) -> Brush {
    Brush::Gradient(
        Gradient::new_radial(center, (0.95 * radius) as f32).with_stops([
            ColorStop {
                offset: 0.0,
                color: DynamicColor::from_alpha_color(base.with_alpha(0.7)),
            },
            ColorStop {
                offset: 1.0,
                color: DynamicColor::from_alpha_color(base.with_alpha(0.3)),
            },
        ]),
    )
}

/// The S1 shape: a full-screen background, then `count` moving circles, each
/// a gradient fill, a stroke and a label.
fn circles(step: u32, count: usize) -> Scene {
    let mut scene = Scene::new();
    let mut builder = SceneBuilder::new(&mut scene);
    builder.fill_rect(
        Rect::new(0.0, 0.0, f64::from(SIZE.0), f64::from(SIZE.1)),
        Brush::Solid(Color::from_rgba8(18, 18, 24, 255)),
    );
    let t = f64::from(step) * 0.05;
    for i in 0..count {
        let phase = i as f64 * 0.37;
        let radius = 12.0 + (i * 7 % 21) as f64;
        let center = Point::new(
            180.0 + 150.0 * (t + phase).sin() * ((i % 5) as f64 / 5.0 + 0.2),
            320.0 + 280.0 * (t * 0.7 + phase * 1.3).cos() * ((i % 7) as f64 / 7.0 + 0.2),
        );
        let base = Color::from_rgba8(
            (60 + i * 37 % 180) as u8,
            (90 + i * 53 % 150) as u8,
            (200 - i * 11 % 120) as u8,
            255,
        );
        let path = Circle::new(center, radius).to_path(0.1);
        builder.fill_path(path.clone(), gradient(center, radius, base));
        builder.stroke_path(path, 2.0, Brush::Solid(base.with_alpha(0.6)));
        if i % 3 == 0 {
            builder.push_transform(Affine::translate((center.x - 10.0, center.y)));
            builder.draw_glyph_run(label(12.0, Color::WHITE));
            builder.pop_transform();
        }
    }
    scene
}

fn image() -> ImageData {
    let mut pixels = Vec::with_capacity(16 * 16 * 4);
    for y in 0..16_u8 {
        for x in 0..16_u8 {
            pixels.extend_from_slice(&[x * 16, y * 16, 128, 255]);
        }
    }
    ImageData {
        data: Blob::new(Arc::new(pixels)),
        format: ImageFormat::Rgba8,
        alpha_type: ImageAlphaType::Alpha,
        width: 16,
        height: 16,
    }
}

fn star(center: Point, outer: f64) -> BezPath {
    let mut path = BezPath::new();
    for k in 0..10 {
        let angle = f64::from(k) * std::f64::consts::PI / 5.0;
        let r = if k % 2 == 0 { outer } else { outer * 0.45 };
        let point = Point::new(center.x + r * angle.cos(), center.y + r * angle.sin());
        if k == 0 {
            path.move_to(point);
        } else {
            path.line_to(point);
        }
    }
    path.close_path();
    path
}

/// Every shape command kind, inside and outside every bracket kind: scissor
/// clips, rounded (mask) clips, isolated layers, a scaled retained bracket, nesting,
/// an unbalanced pop, and a hole punch.
fn brackets(step: u32) -> Scene {
    let shift = f64::from(step % 13) * 0.75;
    let image = image();
    let mut scene = Scene::new();
    let mut builder = SceneBuilder::new(&mut scene);
    builder.fill_rect(
        Rect::new(0.0, 0.0, f64::from(SIZE.0), f64::from(SIZE.1)),
        Brush::Solid(Color::WHITE),
    );

    let shapes = |builder: &mut SceneBuilder<'_>, origin: Point| {
        let o = origin + (shift, shift * 0.5);
        builder.fill_rect(
            Rect::new(o.x + 0.3, o.y + 0.6, o.x + 40.7, o.y + 30.2),
            Brush::Solid(Color::from_rgb8(200, 30, 30)),
        );
        builder.fill_rounded_rect(
            Rect::new(o.x + 50.0, o.y, o.x + 110.0, o.y + 40.0),
            9.5,
            gradient(o + (80.0, 20.0), 30.0, Color::from_rgb8(30, 90, 200)),
        );
        builder.stroke_line(
            o + (0.0, 50.0),
            o + (120.0, 70.0),
            3.5,
            Brush::Solid(Color::BLACK),
        );
        builder.fill_path(
            star(o + (150.0, 30.0), 28.0),
            Brush::Solid(Color::from_rgb8(240, 180, 0)),
        );
        builder.stroke_path(
            star(o + (210.0, 30.0), 24.0),
            2.25,
            Brush::Solid(Color::from_rgb8(0, 120, 60)),
        );
        builder.stroke_path_dashed(
            Circle::new(o + (270.0, 30.0), 22.0).to_path(0.1),
            2.0,
            DashPattern {
                on: 6.0,
                off: 3.5,
                phase: shift,
            },
            Brush::Solid(Color::from_rgb8(90, 0, 140)),
        );
        builder.draw_image(&image, Rect::new(o.x, o.y + 80.0, o.x + 47.5, o.y + 120.25));
        builder.draw_image(
            &image,
            Rect::new(60.0, o.y.round() + 80.0, 92.0, o.y.round() + 112.0),
        );
        builder.draw_blurred_rounded_rect(
            Rect::new(o.x + 110.0, o.y + 80.0, o.x + 170.0, o.y + 120.0),
            8.0,
            4.0,
            Color::from_rgba8(0, 0, 0, 120),
        );
        builder.push_transform(Affine::translate((o.x + 190.0, o.y + 110.0)));
        builder.draw_glyph_run(label(14.0, Color::BLACK));
        builder.pop_transform();
    };

    shapes(&mut builder, Point::new(10.0, 10.0));

    builder.push_clip(Rect::new(0.0, 140.0, 300.0, 270.0));
    shapes(&mut builder, Point::new(-20.0, 150.0));
    builder.pop_clip();

    builder.push_clip_rounded(Rect::new(10.0, 280.0, 340.0, 420.0), 24.0);
    shapes(&mut builder, Point::new(5.0, 290.0));
    builder.push_clip(Rect::new(40.0, 300.0, 200.0, 400.0));
    shapes(&mut builder, Point::new(30.0, 310.0));
    builder.pop_clip();
    builder.pop_clip();

    builder.push_layer(Rect::new(0.0, 430.0, 360.0, 540.0), 0.5);
    shapes(&mut builder, Point::new(0.0, 435.0));
    builder.pop_layer();

    builder.push_transform(Affine::rotate_about(0.2, Point::new(180.0, 590.0)));
    builder.push_clip(Rect::new(20.0, 550.0, 340.0, 630.0));
    shapes(&mut builder, Point::new(15.0, 550.0));
    builder.pop_clip();
    builder.pop_transform();

    builder.push_retained(
        7,
        Rect::new(0.0, 0.0, 360.0, 300.0),
        0.8,
        1.0 + f64::from(step % 5) * 0.05,
    );
    shapes(&mut builder, Point::new(40.0, 40.0));
    builder.pop_retained();

    builder.clear_rect(Rect::new(300.0, 600.0, 350.0, 630.0));
    // Unbalanced: closes nothing.
    builder.pop_clip();
    shapes(&mut builder, Point::new(100.0, 560.0));
    scene
}

fn sequential() -> SceneCompiler {
    let mut compiler = SceneCompiler::new(SIZE.0, SIZE.1);
    compiler.set_parallel_workers(1);
    compiler
}

fn parallel(workers: usize) -> SceneCompiler {
    let mut compiler = SceneCompiler::new(SIZE.0, SIZE.1);
    compiler.set_parallel_workers(workers);
    compiler.set_parallel_min_cost(0);
    compiler
}

fn compile(compiler: &mut SceneCompiler, scene: &Scene, size: (u16, u16)) -> CompiledFrame {
    let frame = compiler
        .compile(scene, Affine::IDENTITY, size)
        .expect("an in-range scene compiles");
    compiler.acknowledge_glyph_clears();
    compiler.acknowledge_glyph_replay();
    compiler.acknowledge_image_plan();
    frame
}

/// The frame as text, with the two fields allowed to differ between arms
/// cleared: who generated the strips, and what the phases cost.
fn comparable(mut frame: CompiledFrame) -> (String, u32) {
    let helped = frame.parallel_draws;
    frame.parallel_draws = 0;
    frame.compile_spans = Default::default();
    (format!("{frame:?}"), helped)
}

/// A sequential compiler and parallel ones at several worker counts.
struct Arms {
    sequential: SceneCompiler,
    parallel: Vec<SceneCompiler>,
}

impl Arms {
    fn new() -> Self {
        Self {
            sequential: sequential(),
            parallel: [2, 3, 5].into_iter().map(parallel).collect(),
        }
    }

    /// Compile `scene` on every arm, require identical frames, and answer how
    /// many draws helpers generated across the parallel arms.
    fn frame(&mut self, label: &str, scene: &Scene, size: (u16, u16)) -> u32 {
        let (expected, helped) = comparable(compile(&mut self.sequential, scene, size));
        assert_eq!(helped, 0, "{label}: one worker never spawns a helper");
        let mut total = 0;
        for compiler in &mut self.parallel {
            let workers = compiler.parallel_workers();
            let (actual, helped) = comparable(compile(compiler, scene, size));
            assert!(
                actual == expected,
                "{label}: {workers} workers compiled a different frame"
            );
            total += helped;
        }
        total
    }
}

#[test]
fn moving_circles_compile_identically_with_helpers() {
    let mut arms = Arms::new();
    let mut helped = 0;
    for step in 0..40 {
        helped += arms.frame(&format!("frame {step}"), &circles(step, 120), SIZE);
    }
    let mut step = 40;
    while helped == 0 && step < 40 + MERGE_ATTEMPTS as u32 {
        helped += arms.frame(&format!("frame {step}"), &circles(step, 120), SIZE);
        step += 1;
    }
    assert!(helped > 0, "helpers generated some of the draws");
}

#[test]
fn every_bracket_kind_compiles_identically_with_helpers() {
    let mut arms = Arms::new();
    let mut helped = 0;
    for step in 0..30 {
        helped += arms.frame(&format!("frame {step}"), &brackets(step), SIZE);
    }
    let mut step = 30;
    while helped == 0 && step < 30 + MERGE_ATTEMPTS as u32 {
        helped += arms.frame(&format!("frame {step}"), &brackets(step), SIZE);
        step += 1;
    }
    assert!(helped > 0, "helpers generated some of the draws");
}

#[test]
fn a_frame_root_and_a_resize_reach_the_helpers() {
    let mut arms = Arms::new();
    let sizes = [SIZE, (200, 300), (1080, 2340), (33, 17), SIZE];
    for (index, size) in sizes.into_iter().enumerate() {
        for step in 0..4 {
            let scene = circles(step + index as u32 * 4, 80);
            let label = format!("size {size:?}, step {step}");
            arms.frame(&label, &scene, size);

            // A root transform the helpers compose exactly as the walk does.
            let root = Affine::translate((3.25, -7.5)) * Affine::scale(1.37);
            let (expected, _) = comparable(
                arms.sequential
                    .compile(&scene, root, size)
                    .expect("an in-range scene compiles"),
            );
            for compiler in &mut arms.parallel {
                let (actual, _) = comparable(
                    compiler
                        .compile(&scene, root, size)
                        .expect("an in-range scene compiles"),
                );
                assert!(actual == expected, "{label}: rooted frames differ");
            }
        }
    }
}

#[test]
fn a_refused_frame_leaves_the_pool_usable() {
    let mut arms = Arms::new();
    arms.frame("before", &circles(0, 60), SIZE);

    let mut invalid = circles(1, 60);
    SceneBuilder::new(&mut invalid).fill_rect(
        Rect::new(0.0, 0.0, f64::NAN, 4.0),
        Brush::Solid(Color::BLACK),
    );
    assert!(
        arms.sequential
            .compile(&invalid, Affine::IDENTITY, SIZE)
            .is_err()
    );
    for compiler in &mut arms.parallel {
        assert!(compiler.compile(&invalid, Affine::IDENTITY, SIZE).is_err());
    }

    for step in 2..6 {
        arms.frame(&format!("after {step}"), &circles(step, 60), SIZE);
    }
}

#[test]
fn one_worker_and_a_small_frame_never_use_a_helper() {
    let mut compiler = sequential();
    for step in 0..8 {
        let frame = compile(&mut compiler, &circles(step, 120), SIZE);
        assert_eq!(frame.parallel_draws, 0);
    }

    // Zero workers reads as the sequential walk.
    compiler.set_parallel_workers(0);
    assert_eq!(compiler.parallel_workers(), 1);

    // A single full-screen rectangle plans nothing, and a few small shapes
    // stay below the default spawn threshold.
    let mut compiler = SceneCompiler::new(SIZE.0, SIZE.1);
    compiler.set_parallel_workers(2);
    assert_eq!(
        compiler.parallel_min_cost(),
        config::parallel_min_cost().unwrap_or(DEFAULT_PARALLEL_MIN_COST)
    );
    compiler.set_parallel_min_cost(DEFAULT_PARALLEL_MIN_COST);
    let mut rect = Scene::new();
    SceneBuilder::new(&mut rect).fill_rect(
        Rect::new(0.0, 0.0, f64::from(SIZE.0), f64::from(SIZE.1)),
        Brush::Solid(Color::BLACK),
    );
    for _ in 0..8 {
        assert_eq!(compile(&mut compiler, &rect, SIZE).parallel_draws, 0);
        assert_eq!(
            compile(&mut compiler, &circles(0, 3), SIZE).parallel_draws,
            0
        );
    }
}

#[test]
fn the_default_worker_count_follows_the_kill_switch() {
    let compiler = SceneCompiler::new(SIZE.0, SIZE.1);
    let machine = std::thread::available_parallelism().map_or(1, usize::from);
    let expected = if config::parallel_walk_disabled() {
        1
    } else {
        config::parallel_workers()
            .unwrap_or(DEFAULT_PARALLEL_WORKERS)
            .min(machine)
            .max(1)
    };
    assert_eq!(compiler.parallel_workers(), expected);
}

/// One recorded operation of a random scene.
#[derive(Debug, Clone)]
enum Op {
    Rect(Rect, f64),
    Rounded(Rect, f64),
    Circle(Point, f64, Option<f64>),
    Line(Point, Point, f64),
    Clip(Rect, f64),
    Layer(Rect, f32),
    Pop,
    Transform(f64, f64, f64),
}

fn op() -> impl Strategy<Value = Op> {
    let coordinate = -40.0..400.0_f64;
    let point = (coordinate.clone(), coordinate.clone()).prop_map(|(x, y)| Point::new(x, y));
    let rect = (point.clone(), 0.0..220.0_f64, 0.0..220.0_f64)
        .prop_map(|(p, w, h)| Rect::new(p.x, p.y, p.x + w, p.y + h));
    let snapped = rect.clone().prop_map(|r| r.round());
    prop_oneof![
        (prop_oneof![rect.clone(), snapped.clone()], 0.0..1.0_f64)
            .prop_map(|(r, c)| Op::Rect(r, c)),
        (rect.clone(), 0.0..30.0_f64).prop_map(|(r, radius)| Op::Rounded(r, radius)),
        (
            point.clone(),
            0.5..90.0_f64,
            prop::option::of(0.25..6.0_f64)
        )
            .prop_map(|(p, r, stroke)| Op::Circle(p, r, stroke)),
        (point.clone(), point, 0.25..8.0_f64).prop_map(|(a, b, w)| Op::Line(a, b, w)),
        (prop_oneof![rect.clone(), snapped], 0.0..16.0_f64)
            .prop_map(|(r, radius)| Op::Clip(r, radius)),
        (rect, 0.1..1.0_f32).prop_map(|(r, alpha)| Op::Layer(r, alpha)),
        Just(Op::Pop),
        (-0.4..0.4_f64, 0.5..1.8_f64, -30.0..30.0_f64).prop_map(|(a, s, t)| Op::Transform(a, s, t)),
    ]
}

fn random_scene(ops: &[Op]) -> Scene {
    let mut scene = Scene::new();
    let mut builder = SceneBuilder::new(&mut scene);
    let mut open = Vec::new();
    for (index, op) in ops.iter().enumerate() {
        let color = Color::from_rgba8((index * 40 % 256) as u8, 90, 200, 200);
        match op {
            Op::Rect(rect, shade) => builder.fill_rect(
                *rect,
                gradient(
                    rect.center(),
                    rect.width().max(1.0),
                    color.with_alpha(*shade as f32),
                ),
            ),
            Op::Rounded(rect, radius) => {
                builder.fill_rounded_rect(*rect, *radius, Brush::Solid(color))
            }
            Op::Circle(center, radius, stroke) => {
                let path = Circle::new(*center, *radius).to_path(0.1);
                match stroke {
                    Some(width) => builder.stroke_path(path, *width, Brush::Solid(color)),
                    None => builder.fill_path(path, Brush::Solid(color)),
                }
            }
            Op::Line(a, b, width) => builder.stroke_line(*a, *b, *width, Brush::Solid(color)),
            Op::Clip(rect, radius) => {
                if *radius > 8.0 {
                    builder.push_clip_rounded(*rect, *radius);
                } else {
                    builder.push_clip(*rect);
                }
                open.push(false);
            }
            Op::Layer(rect, alpha) => {
                builder.push_layer(*rect, *alpha);
                open.push(true);
            }
            Op::Pop => match open.pop() {
                Some(true) => builder.pop_layer(),
                Some(false) => builder.pop_clip(),
                None => {}
            },
            Op::Transform(angle, scale, shift) => builder.push_transform(
                Affine::translate((*shift, -*shift))
                    * Affine::rotate_about(*angle, Point::new(180.0, 320.0))
                    * Affine::scale(*scale),
            ),
        }
    }
    scene
}

proptest! {
    #![proptest_config(ProptestConfig::with_cases(64))]

    /// Any mix of shapes, clips, layers and transforms compiles to the same
    /// frame with or without helpers.
    #[test]
    fn a_random_scene_compiles_identically_with_helpers(ops in prop::collection::vec(op(), 1..48)) {
        let scene = random_scene(&ops);
        let mut sequential = sequential();
        let mut helped = parallel(3);
        let (expected, _) = comparable(compile(&mut sequential, &scene, SIZE));
        let (actual, _) = comparable(compile(&mut helped, &scene, SIZE));
        prop_assert!(actual == expected, "the helpers changed the frame");
    }
}

/// Not a gate: the timings the pool's spawn threshold and worker count were
/// chosen from. Run with
/// `cargo test --release -p frust-engine --test parallel_walk -- --ignored --nocapture`.
#[test]
#[ignore = "timing report, not an assertion"]
fn timing_report() {
    use std::time::{Duration, Instant};

    fn median(mut samples: Vec<Duration>) -> Duration {
        samples.sort_unstable();
        samples[samples.len() / 2]
    }

    const RUNS: usize = 400;

    // What one scoped spawn costs the spawning thread, and what spawning,
    // running nothing and joining costs end to end.
    let mut call = Vec::with_capacity(RUNS);
    let mut round_trip = Vec::with_capacity(RUNS);
    for _ in 0..RUNS {
        let start = Instant::now();
        std::thread::scope(|scope| {
            let _ = std::thread::Builder::new().spawn_scoped(scope, || {});
            call.push(start.elapsed());
        });
        round_trip.push(start.elapsed());
    }
    println!(
        "scoped spawn: call {:?}, spawn+join {:?}",
        median(call),
        median(round_trip)
    );

    let phone = (1080, 2340);
    let mut rect = Scene::new();
    SceneBuilder::new(&mut rect).fill_rect(
        Rect::new(0.0, 0.0, 1080.0, 2340.0),
        Brush::Solid(Color::BLACK),
    );
    // A page of text and nothing else: what planning costs a frame that
    // offers a helper nothing.
    let mut text = Scene::new();
    {
        let mut builder = SceneBuilder::new(&mut text);
        builder.fill_rect(
            Rect::new(0.0, 0.0, 1080.0, 2340.0),
            Brush::Solid(Color::BLACK),
        );
        for line in 0..400 {
            builder.push_transform(Affine::translate((20.0, 20.0 + f64::from(line) * 5.5)));
            builder.draw_glyph_run(label(14.0, Color::WHITE));
            builder.pop_transform();
        }
    }
    for workers in [1, 2, 3] {
        let mut compiler = SceneCompiler::new(phone.0, phone.1);
        compiler.set_parallel_workers(workers);
        let page = median(
            (0..RUNS)
                .map(|_| {
                    let start = Instant::now();
                    let frame = compile(&mut compiler, &text, phone);
                    let elapsed = start.elapsed();
                    std::hint::black_box(frame);
                    elapsed
                })
                .collect(),
        );
        println!("workers {workers}: 400-run text page {page:?}");
        let single = median(
            (0..RUNS)
                .map(|_| {
                    let start = Instant::now();
                    let frame = compile(&mut compiler, &rect, phone);
                    let elapsed = start.elapsed();
                    std::hint::black_box(frame);
                    elapsed
                })
                .collect(),
        );
        let mut helped = 0;
        let s1 = median(
            (0..RUNS as u32)
                .map(|step| {
                    let scene = circles(step, 233);
                    let start = Instant::now();
                    let frame = compile(&mut compiler, &scene, SIZE);
                    let elapsed = start.elapsed();
                    helped += frame.parallel_draws;
                    std::hint::black_box(frame);
                    elapsed
                })
                .collect(),
        );
        println!(
            "workers {workers}: full-screen rect frame {single:?}, 233 circles {s1:?}, \
             helper draws {:.1}/frame",
            f64::from(helped) / RUNS as f64
        );
    }
}