onedrop_eval/

carry.rs

//! Carry-dependency analysis for per-point equation blocks.
//!
//! Custom-wave `per_point` blocks run sequentially across the wave's
//! samples and the convention is that each iteration sees the previous
//! iteration's `x`/`y`/`r`/`g`/`b`/`a` as input ("trail across samples").
//! In practice many presets don't actually depend on that carry — they
//! write `x = …; y = …; r = …;` from the per-sample inputs (`sample`,
//! `value1`, `value2`) and never read the previous values. In that case
//! the samples are independent and the engine is free to evaluate them
//! in parallel, which is a 4-8× win on dense waves.
//!
//! This module walks the compiled [`Node`]s once at preset-load time and
//! classifies each per_point block as either *safe-to-parallelize* or
//! *carry-dependent*. The check is conservative — a block is only marked
//! safe if:
//!
//! 1. No carry-tracked variable (`x`, `y`, `r`, `g`, `b`, `a`) is read
//!    before being written in the block sequence (a read inside an
//!    equation that also writes the var is treated as carry-needing
//!    unless an earlier equation already wrote it).
//! 2. No variable outside `{x, y, r, g, b, a, sample, value1, value2}`
//!    is written. Stray writes to `qN` / custom vars / per-frame vars
//!    leak state across samples.
//! 3. No stateful / side-effecting function is called (`rand`,
//!    `gmegabuf`, `megabuf`, `gmegabuf_set`, `megabuf_set`, `exec2`,
//!    `exec3`, `loop`, `while`). These either carry per-eval state
//!    (gmegabuf is thread-local; samples on different workers would
//!    see split state) or are sample-order dependent (`rand`).

use evalexpr::Node;
use std::collections::HashSet;

/// Variables that thread state across iterations of `eval_per_point`
/// (the caller seeds them from the previous sample's output).
pub const CARRY_VARS: &[&str] = &["x", "y", "r", "g", "b", "a"];

/// Per-sample input variables the caller re-seeds every iteration —
/// writes to these inside per_point are harmless because they get
/// overwritten before the next sample runs.
const INPUT_VARS: &[&str] = &["sample", "value1", "value2"];

/// Functions whose semantics depend on call order or thread-local state.
/// A per_point block calling any of these cannot be safely sample-parallelised.
const UNSAFE_FUNCTIONS: &[&str] = &[
    "rand",
    "gmegabuf",
    "megabuf",
    "gmegabuf_set",
    "megabuf_set",
    "exec2",
    "exec3",
    "loop",
    "while",
];

/// Classification of a per_point block for the parallel-samples pass.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PerPointParallelism {
    /// Samples can be evaluated independently — output of sample `S`
    /// does not feed into sample `S+1`.
    Safe,
    /// Sequential evaluation only — at least one of: carry-read on
    /// `{x,y,r,g,b,a}`, write outside the allowed output set, or call
    /// to a stateful function.
    Sequential,
}

impl PerPointParallelism {
    /// Returns `true` for [`PerPointParallelism::Safe`].
    #[inline]
    pub fn is_safe(self) -> bool {
        matches!(self, Self::Safe)
    }
}

/// Analyse a compiled per_point block. Walks each equation's operator
/// tree once and tracks a running set of "already-written" identifiers
/// to distinguish "first read = carry" from "first read after write =
/// uses fresh value".
pub fn analyse_per_point(per_point: &[Node]) -> PerPointParallelism {
    let mut already_written: HashSet<String> = HashSet::new();

    for node in per_point {
        // Functions first — a single occurrence of `rand` / `gmegabuf` /
        // … taints the whole block.
        for fname in node.iter_function_identifiers() {
            if UNSAFE_FUNCTIONS.contains(&fname) {
                return PerPointParallelism::Sequential;
            }
        }

        // Reads of a carry-tracked var that has NOT been written by an
        // earlier equation in the block mean sample S+1's value
        // depends on sample S's output.
        for ident in node.iter_read_variable_identifiers() {
            if CARRY_VARS.contains(&ident) && !already_written.contains(ident) {
                return PerPointParallelism::Sequential;
            }
        }

        // Writes outside the allowed output set propagate side effects
        // across samples (qN, custom vars, …). The shared per_point
        // outputs (`x`/`y`/`r`/`g`/`b`/`a`) and the re-seeded inputs
        // (`sample`/`value1`/`value2`) are fine.
        for ident in node.iter_write_variable_identifiers() {
            if !CARRY_VARS.contains(&ident) && !INPUT_VARS.contains(&ident) {
                return PerPointParallelism::Sequential;
            }
            already_written.insert(ident.to_string());
        }
    }

    PerPointParallelism::Safe
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::MilkEvaluator;

    fn compile(eqs: &[&str]) -> Vec<Node> {
        let mut eval = MilkEvaluator::new();
        let owned: Vec<String> = eqs.iter().map(|s| s.to_string()).collect();
        eval.compile_batch(&owned).unwrap()
    }

    #[test]
    fn pure_output_writes_are_safe() {
        let n = compile(&[
            "x = sample",
            "y = 0.5 - value1 * 0.5",
            "r = 1",
            "g = 0",
            "b = 0",
            "a = 1",
        ]);
        assert_eq!(analyse_per_point(&n), PerPointParallelism::Safe);
    }

    #[test]
    fn read_of_x_before_write_is_carry() {
        let n = compile(&["x = x + 0.001"]);
        assert_eq!(analyse_per_point(&n), PerPointParallelism::Sequential);
    }

    #[test]
    fn read_after_write_in_separate_equation_is_safe() {
        // eq1 writes x from sample; eq2 reads x but the first write
        // already happened in this iteration → no carry on x.
        let n = compile(&["x = sample", "y = x * 2"]);
        assert_eq!(analyse_per_point(&n), PerPointParallelism::Safe);
    }

    #[test]
    fn write_to_q_var_is_unsafe() {
        // q1 written by per_point would leak to next sample / next
        // wave's per_frame.
        let n = compile(&["q1 = sample", "x = sample"]);
        assert_eq!(analyse_per_point(&n), PerPointParallelism::Sequential);
    }

    #[test]
    fn write_to_custom_var_is_unsafe() {
        let n = compile(&["mycarry = sample", "x = mycarry"]);
        assert_eq!(analyse_per_point(&n), PerPointParallelism::Sequential);
    }

    #[test]
    fn rand_call_taints_block() {
        let n = compile(&["x = rand(100)/100"]);
        assert_eq!(analyse_per_point(&n), PerPointParallelism::Sequential);
    }

    #[test]
    fn gmegabuf_call_taints_block() {
        let n = compile(&["x = gmegabuf(0)"]);
        assert_eq!(analyse_per_point(&n), PerPointParallelism::Sequential);
    }

    #[test]
    fn empty_block_is_safe_but_vacuous() {
        // No equations → nothing reads carry → trivially safe (caller
        // handles empty case before invoking us anyway).
        assert_eq!(analyse_per_point(&[]), PerPointParallelism::Safe);
    }

    #[test]
    fn writing_to_sample_input_is_safe() {
        // sample/value1/value2 are re-seeded by the caller every
        // iteration; intra-iteration writes to them don't leak.
        let n = compile(&["sample = sample * 2", "x = sample"]);
        assert_eq!(analyse_per_point(&n), PerPointParallelism::Safe);
    }
}