facett-core 0.1.19

//! **GFX_V2 item 7 — OIT is genuinely ORDER-INDEPENDENT** (needs `--features wgpu`).
//!
//! The point of order-independent transparency is the name. So the load-bearing
//! assertion here renders **the same overlapping translucent geometry in six different
//! submission orders** and requires the resulting pixels to be *byte-identical*. A
//! depth-sorted alpha blend cannot pass that, and neither can an OIT whose per-pixel
//! comparator is only a partial order.
//!
//! **But cross-order identity ALONE is a hollow guard**, and it is hollow in the exact
//! way this track keeps finding: a resolve that returned a constant colour — or one
//! whose linked list never received a single fragment — would be perfectly identical
//! across all six orders and prove nothing. That is the identity-value trap. So every
//! order-independence assertion here is paired with three that a dead pass fails:
//!
//! 1. **An independent CPU oracle of the composite** at named pixels. The expected
//!    colour is folded on the host from the *sorted* fragment set, in `f32`, and
//!    compared to the device's byte. A pass that skipped a layer, sorted the wrong way,
//!    or premultiplied twice lands on a different byte.
//! 2. **The device's own fragment counter** (`OitPass::fragment_count`) — the bump
//!    allocator the shader `atomicAdd`ed, read back out of GPU memory. It must equal
//!    the covered-area sum, so "no fragment ever reached a list" is not mistakable for
//!    "the frame is stable".
//! 3. **Region distinctness** — the 1-, 2- and 3-layer zones must all differ from each
//!    other and from the background, so a constant frame fails.
//!
//! It also proves the two properties the order-independence *rests* on, separately,
//! because each is a place where a plausible implementation silently becomes
//! order-dependent:
//!
//! * **Ties.** Coplanar quads at *equal depth* with different colours are the case a
//!   depth-only comparator gets wrong. The shader breaks ties on the packed colour;
//!   `equal_depth_layers_are_still_order_independent` submits them both ways round.
//! * **Overflow.** Past `OIT_MAX_LAYERS` fragments on one pixel, keeping "the first N
//!   seen" would be submission-order dependent. `overflow_selects_the_nearest_layers`
//!   stacks 24 layers on one pixel and requires identity across orders anyway.
//!
//! Run: `cargo test -p facett-core --features wgpu --test gpu_oit -- --nocapture`
#![cfg(feature = "wgpu")]

use facett_core::render::gpu::oit::{OitBatch, OitPass, OIT_MAX_LAYERS};
use facett_core::render::gpu::{preferred_backends, read_texture_region, request_best_adapter};
use egui::{pos2, Rect};

/// The component every row and every SKIP in this file is filed under.
const GATE_COMPONENT: &str = "facett-core";
/// What a skipped arm of this file would have proven, so a SKIPPED matrix row is
/// readable without opening the test.
const GATE_DETAIL: &str = "order-independent transparency on a real device — identical pixels under every submission order";

const TARGET_FORMAT: wgpu::TextureFormat = wgpu::TextureFormat::Rgba8Unorm;
const W: u32 = 96;
const H: u32 = 96;

/// A real device via the **sanctioned** selector — same helper shape as
/// `tests/gpu_picking.rs`, for the same reason (`request_adapter(&Default::default())`
/// asks for `LowPower` and picks the wrong GPU on a hybrid box).
///
/// Returns the adapter too, because this lane needs a downlevel capability
/// (`FRAGMENT_WRITABLE_STORAGE`) and a caller must be able to say so out loud rather
/// than fail inside pipeline creation.
fn device() -> Option<(wgpu::Adapter, wgpu::Device, wgpu::Queue)> {
    let instance = wgpu::Instance::new(wgpu::InstanceDescriptor {
        backends: preferred_backends(),
        flags: wgpu::InstanceFlags::from_build_config().with_env(),
        backend_options: wgpu::BackendOptions::from_env_or_default(),
        memory_budget_thresholds: wgpu::MemoryBudgetThresholds::default(),
        display: None,
    });
    let adapter = request_best_adapter(&instance, preferred_backends())?;
    // ATTRIBUTION, not decoration. A graceful `None` skip is exactly how a GPU test
    // file goes green having run no shader, so print the device that answered — and
    // print whether it can run this lane at all.
    let info = adapter.get_info();
    eprintln!(
        "[gpu_oit] device: {} ({:?}, {:?}) fragment_writable_storage={}",
        info.name,
        info.backend,
        info.device_type,
        OitPass::supported(&adapter)
    );
    let (device, queue) = pollster::block_on(adapter.request_device(&wgpu::DeviceDescriptor {
        label: Some("gpu_oit_test"),
        required_features: wgpu::Features::empty(),
        required_limits: wgpu::Limits::downlevel_defaults(),
        ..Default::default()
    }))
    .ok()?;
    Some((adapter, device, queue))
}

fn target(device: &wgpu::Device) -> (wgpu::Texture, wgpu::TextureView) {
    let tex = device.create_texture(&wgpu::TextureDescriptor {
        label: Some("gpu_oit_target"),
        size: wgpu::Extent3d { width: W, height: H, depth_or_array_layers: 1 },
        mip_level_count: 1,
        sample_count: facett_core::render::gpu::NO_MSAA_SAMPLES,
        dimension: wgpu::TextureDimension::D2,
        format: TARGET_FORMAT,
        usage: wgpu::TextureUsages::RENDER_ATTACHMENT | wgpu::TextureUsages::COPY_SRC,
        view_formats: &[],
    });
    let view = tex.create_view(&Default::default());
    (tex, view)
}

/// Render `batch` through the OIT lane and return `(rgba bytes, device fragment count)`.
fn render(
    device: &wgpu::Device,
    queue: &wgpu::Queue,
    batch: &OitBatch,
    background: [f32; 4],
    layers: u32,
) -> (Vec<u8>, u32) {
    let (tex, view) = target(device);
    let mut pass = OitPass::new(device, TARGET_FORMAT);
    pass.ensure(device, W, H, layers);
    pass.set_frame(queue, background);
    pass.upload(device, queue, batch);

    let mut enc = device.create_command_encoder(&wgpu::CommandEncoderDescriptor {
        label: Some("gpu_oit_enc"),
    });
    let submitted = pass.record(&mut enc, &view);
    queue.submit(Some(enc.finish()));
    assert_eq!(submitted, batch.len() as u32, "the pass submitted the whole batch");

    let bytes = read_texture_region(device, queue, &tex, 4, 0, 0, W, H);
    let frags = pass.fragment_count(device, queue);
    (bytes, frags)
}

fn px(bytes: &[u8], x: u32, y: u32) -> [u8; 4] {
    let o = ((y * W + x) * 4) as usize;
    [bytes[o], bytes[o + 1], bytes[o + 2], bytes[o + 3]]
}

/// **The independent oracle.** Fold `src OVER dst` back-to-front over `bg`, in `f32`,
/// from the fragment set sorted by the SAME total order the shader uses (depth, then
/// packed colour). Re-derived on the host on purpose: if it shared code with the shader
/// it could not catch the shader being wrong.
fn oracle(bg: [f32; 4], mut frags: Vec<(f32, [f32; 4])>) -> [u8; 4] {
    // Quantise exactly as `pack4x8unorm` does, then compare on the same total order —
    // otherwise the oracle's tie-break and the device's could differ.
    let packed = |c: [f32; 4]| -> u32 {
        let b = |v: f32| (v.clamp(0.0, 1.0) * 255.0).round() as u32;
        b(c[0]) | (b(c[1]) << 8) | (b(c[2]) << 16) | (b(c[3]) << 24)
    };
    frags.sort_by(|a, b| {
        // Farthest first.
        b.0.partial_cmp(&a.0)
            .unwrap()
            .then(packed(b.1).cmp(&packed(a.1)))
    });
    let unpack = |c: [f32; 4]| -> [f32; 4] {
        let p = packed(c);
        [
            (p & 0xFF) as f32 / 255.0,
            ((p >> 8) & 0xFF) as f32 / 255.0,
            ((p >> 16) & 0xFF) as f32 / 255.0,
            ((p >> 24) & 0xFF) as f32 / 255.0,
        ]
    };
    let mut rgb = [bg[0], bg[1], bg[2]];
    let mut a = bg[3];
    for (_, c) in &frags {
        let s = unpack(*c);
        for k in 0..3 {
            rgb[k] = s[k] * s[3] + rgb[k] * (1.0 - s[3]);
        }
        a = s[3] + a * (1.0 - s[3]);
    }
    let q = |v: f32| (v.clamp(0.0, 1.0) * 255.0).round() as u8;
    [q(rgb[0]), q(rgb[1]), q(rgb[2]), q(a)]
}

/// Colours on exact `k/255` steps, so `pack4x8unorm` is lossless and the oracle's
/// arithmetic is the device's arithmetic rather than an approximation of it.
const RED: [f32; 4] = [204.0 / 255.0, 0.0, 0.0, 128.0 / 255.0];
const GREEN: [f32; 4] = [0.0, 204.0 / 255.0, 0.0, 128.0 / 255.0];
const BLUE: [f32; 4] = [0.0, 0.0, 204.0 / 255.0, 128.0 / 255.0];
const BG: [f32; 4] = [16.0 / 255.0, 16.0 / 255.0, 16.0 / 255.0, 1.0];

/// Three half-transparent quads in a staircase, so the frame has a 1-layer, a 2-layer
/// and a 3-layer zone. Depths are chosen so **painter order is NOT depth order** — the
/// nearest quad is submitted first — which is what makes a naive "blend as submitted"
/// implementation produce a different picture.
///
/// Returns the batch plus the probe points and their expected fragment sets.
#[allow(clippy::type_complexity)]
fn staircase() -> (OitBatch, Vec<(&'static str, u32, u32, Vec<(f32, [f32; 4])>)>) {
    let mut b = OitBatch::new();
    // BLUE is NEAREST (depth 1) but pushed FIRST; RED is farthest (depth 3) but last.
    b.push_quad(Rect::from_min_max(pos2(8.0, 8.0), pos2(56.0, 56.0)), BLUE, 1.0);
    b.push_quad(Rect::from_min_max(pos2(24.0, 24.0), pos2(72.0, 72.0)), GREEN, 2.0);
    b.push_quad(Rect::from_min_max(pos2(40.0, 40.0), pos2(88.0, 88.0)), RED, 3.0);

    let probes = vec![
        ("background", 4u32, 4u32, vec![]),
        ("blue only", 12, 12, vec![(1.0, BLUE)]),
        ("blue+green", 30, 30, vec![(1.0, BLUE), (2.0, GREEN)]),
        ("all three", 48, 48, vec![(1.0, BLUE), (2.0, GREEN), (3.0, RED)]),
        ("green+red", 64, 64, vec![(2.0, GREEN), (3.0, RED)]),
        ("red only", 80, 80, vec![(3.0, RED)]),
    ];
    (b, probes)
}

/// The six submission orders. Every permutation of 3 quads = 6 triangle orders, so this
/// is *exhaustive* over quad orderings rather than a sample.
fn quad_orders() -> Vec<(&'static str, Vec<usize>)> {
    let tris = |q: [usize; 3]| -> Vec<usize> { q.iter().flat_map(|&i| [i * 2, i * 2 + 1]).collect() };
    vec![
        ("0,1,2 (as built)", tris([0, 1, 2])),
        ("0,2,1", tris([0, 2, 1])),
        ("1,0,2", tris([1, 0, 2])),
        ("1,2,0", tris([1, 2, 0])),
        ("2,0,1", tris([2, 0, 1])),
        ("2,1,0 (reversed)", tris([2, 1, 0])),
    ]
}

#[test]
fn oit_pixels_are_identical_across_every_submission_order_and_match_the_oracle() {
    let Some((adapter, device, queue)) = device() else {
        facett_core::testmatrix::gpu_skip(GATE_COMPONENT, "oit_pixels_are_identical_across_every_submission_order_and_match_the_oracle", "no WebGPU-class adapter", GATE_DETAIL);
        return;
    };
    if !OitPass::supported(&adapter) {
        facett_core::testmatrix::gpu_skip(GATE_COMPONENT, "oit_pixels_are_identical_across_every_submission_order_and_match_the_oracle", "adapter lacks FRAGMENT_WRITABLE_STORAGE", GATE_DETAIL);
        return;
    }
    let (base, probes) = staircase();

    let mut frames: Vec<(&str, Vec<u8>, u32)> = Vec::new();
    for (name, order) in quad_orders() {
        let permuted = base.permuted(&order);
        assert_eq!(permuted.len(), base.len(), "{name}: the permutation is the same scene");
        let (bytes, frags) = render(&device, &queue, &permuted, BG, 8);
        frames.push((name, bytes, frags));
    }

    // ── (2) NON-VACUITY FIRST: the device really rasterised fragments. ──
    // 3 quads of 48×48 px = 3 · 2304 = 6912 covered fragments. The gather emits one
    // node per covered fragment, so the bump allocator must land exactly there. A
    // resolve that returns a constant, or a gather that never ran, gives 0.
    let expect_frags = 3 * 48 * 48;
    for (name, _, frags) in &frames {
        assert_eq!(
            *frags, expect_frags,
            "{name}: the DEVICE's fragment counter must be {expect_frags} — a stable frame with 0 \
             fragments proves nothing"
        );
    }
    eprintln!("[gpu_oit] device fragment count per frame: {expect_frags} (all 6 orders)");

    // ── (1) THE ORACLE: the composite is CORRECT, not merely stable. ──
    let reference = &frames[0].1;
    for (label, x, y, frags) in &probes {
        let got = px(reference, *x, *y);
        let want = oracle(BG, frags.clone());
        eprintln!("[gpu_oit] probe {label:>12} at ({x},{y}): got {got:?} want {want:?}");
        assert_eq!(
            got, want,
            "probe '{label}' at ({x},{y}): the device composite must equal the independent CPU \
             oracle of the sorted fragment set"
        );
    }

    // ── (3) DISTINCTNESS: a constant frame fails. ──
    let seen: Vec<[u8; 4]> = probes.iter().map(|(_, x, y, _)| px(reference, *x, *y)).collect();
    for i in 0..seen.len() {
        for j in (i + 1)..seen.len() {
            assert_ne!(
                seen[i], seen[j],
                "probes '{}' and '{}' must differ — every zone the same colour is a dead resolve",
                probes[i].0, probes[j].0
            );
        }
    }

    // ── THE HEADLINE: byte-identical across all six submission orders. ──
    for (name, bytes, _) in &frames[1..] {
        assert_eq!(
            bytes.len(),
            reference.len(),
            "{name}: same frame size"
        );
        let differing = bytes
            .chunks(4)
            .zip(reference.chunks(4))
            .filter(|(a, b)| a != b)
            .count();
        assert_eq!(
            differing, 0,
            "submission order '{name}' changed {differing} pixels — OIT is not order-independent"
        );
    }
    eprintln!(
        "[gpu_oit] 6/6 submission orders byte-identical over {}×{} px",
        W, H
    );

    // And the painter-order control: submitting nearest-first vs farthest-first are two
    // of the six orders above, so the picture we just froze is NOT simply "the last
    // quad wins". Prove that by checking the 3-layer probe is not any single quad over
    // the background.
    let three = px(reference, 48, 48);
    for (c, nm) in [(BLUE, "blue"), (GREEN, "green"), (RED, "red")] {
        assert_ne!(
            three,
            oracle(BG, vec![(1.0, c)]),
            "the 3-layer probe must not equal {nm} alone over the background"
        );
    }
}

#[test]
fn equal_depth_layers_are_still_order_independent() {
    let Some((adapter, device, queue)) = device() else {
        facett_core::testmatrix::gpu_skip(GATE_COMPONENT, "equal_depth_layers_are_still_order_independent", "no WebGPU-class adapter", GATE_DETAIL);
        return;
    };
    if !OitPass::supported(&adapter) {
        facett_core::testmatrix::gpu_skip(GATE_COMPONENT, "equal_depth_layers_are_still_order_independent", "adapter lacks FRAGMENT_WRITABLE_STORAGE", GATE_DETAIL);
        return;
    }
    // Two COPLANAR quads: same depth, different colours, fully overlapping. This is the
    // case a depth-only comparator resolves in list order, i.e. in submission order.
    let mut a = OitBatch::new();
    let r = Rect::from_min_max(pos2(16.0, 16.0), pos2(80.0, 80.0));
    a.push_quad(r, RED, 5.0);
    a.push_quad(r, GREEN, 5.0);

    let (fwd, f1) = render(&device, &queue, &a, BG, 8);
    let (rev, f2) = render(&device, &queue, &a.permuted(&[2, 3, 0, 1]), BG, 8);

    let expect = 2 * 64 * 64;
    assert_eq!(f1, expect, "forward: the device counted every covered fragment");
    assert_eq!(f2, expect, "reversed: same");

    let centre_f = px(&fwd, 48, 48);
    let centre_r = px(&rev, 48, 48);
    eprintln!("[gpu_oit] equal-depth centre: forward {centre_f:?} reversed {centre_r:?}");
    // Non-vacuity: both layers really contributed, so the pixel is neither quad alone.
    assert_ne!(centre_f, oracle(BG, vec![(5.0, RED)]), "not red alone");
    assert_ne!(centre_f, oracle(BG, vec![(5.0, GREEN)]), "not green alone");
    assert_ne!(centre_f, [16, 16, 16, 255], "not the background");
    assert_eq!(
        fwd, rev,
        "two COPLANAR translucent quads must composite identically either way round — \
         this is the tie the colour tie-break in the comparator exists for"
    );
}

#[test]
fn overflow_selects_the_nearest_layers_and_stays_order_independent() {
    let Some((adapter, device, queue)) = device() else {
        facett_core::testmatrix::gpu_skip(GATE_COMPONENT, "overflow_selects_the_nearest_layers_and_stays_order_independent", "no WebGPU-class adapter", GATE_DETAIL);
        return;
    };
    if !OitPass::supported(&adapter) {
        facett_core::testmatrix::gpu_skip(GATE_COMPONENT, "overflow_selects_the_nearest_layers_and_stays_order_independent", "adapter lacks FRAGMENT_WRITABLE_STORAGE", GATE_DETAIL);
        return;
    }
    // 24 stacked layers over one region — more than OIT_MAX_LAYERS (16), so the resolve
    // MUST overflow. Keeping "the first 16 seen" would depend on submission order.
    let n: u32 = 24;
    assert!(n > OIT_MAX_LAYERS, "the point is to exceed the register array");
    let mut b = OitBatch::new();
    let r = Rect::from_min_max(pos2(24.0, 24.0), pos2(72.0, 72.0));
    for i in 0..n {
        // Distinct depth AND distinct colour per layer.
        let v = (40 + i * 8) as f32 / 255.0;
        b.push_quad(r, [v, v * 0.5, 1.0 - v, 40.0 / 255.0], 1.0 + i as f32);
    }
    let tris = b.tri_count();
    // Node storage per pixel must exceed the stack, otherwise the ALLOCATOR drops the
    // tail and we would be testing that instead of the resolve's selection policy.
    let (fwd, f1) = render(&device, &queue, &b, BG, 32);
    let rev_order: Vec<usize> = (0..tris).rev().collect();
    let (rev, f2) = render(&device, &queue, &b.permuted(&rev_order), BG, 32);

    let expect = n * 48 * 48;
    assert_eq!(f1, expect, "every one of the {n} layers reached a list");
    assert_eq!(f2, expect, "…in the reversed order too");

    let c = px(&fwd, 48, 48);
    eprintln!("[gpu_oit] overflow centre ({n} layers, cap {OIT_MAX_LAYERS}): {c:?}");
    assert_ne!(c, [16, 16, 16, 255], "the overflowed pixel is not the background");
    assert_eq!(
        fwd, rev,
        "with {n} layers on one pixel and room for {OIT_MAX_LAYERS}, the surviving set must be \
         chosen by the total order (the NEAREST ones), not by arrival — otherwise overflow \
         reintroduces order dependence exactly where a small test never looks"
    );

    // And overflow is not silently equivalent to no overflow: the same stack truncated
    // to OIT_MAX_LAYERS nearest layers is what we should see, which differs from the
    // full 24-layer composite. Prove the cap actually bites.
    let mut near_only = OitBatch::new();
    for i in 0..OIT_MAX_LAYERS {
        let v = (40 + i * 8) as f32 / 255.0;
        near_only.push_quad(r, [v, v * 0.5, 1.0 - v, 40.0 / 255.0], 1.0 + i as f32);
    }
    let (capped, _) = render(&device, &queue, &near_only, BG, 32);
    assert_eq!(
        px(&capped, 48, 48),
        c,
        "the 24-layer pixel must equal the 16-NEAREST-layer pixel — that is what 'selects the \
         nearest' means, and it is how we know the cap bit rather than the tail being dropped"
    );
}