alpha2_render/

graph.rs

use std::fmt;
use std::sync::atomic::{AtomicU32, Ordering};

use crate::graph_cache::{
    composite_cache_key, effect_cache_key_with_resources, transient_source_key,
};
use crate::{
    BlendMode, Color, EffectId, EffectParams, EffectResources, EffectRuntime, LayerTransform,
    RenderError, RenderSize, SourceView,
};

/// Stable handle to a node within one render graph.
#[derive(Copy, Clone, Debug, Eq, Hash, PartialEq)]
pub struct RenderNodeId {
    pub(crate) graph: u32,
    pub(crate) index: usize,
}

impl RenderNodeId {
    /// Returns the node's insertion-order index.
    #[must_use]
    pub const fn index(self) -> usize {
        self.index
    }
}

/// Public category of a render graph node.
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub enum RenderNodeKind {
    /// Externally owned input texture.
    Source,
    /// Registered one-input effect.
    Effect,
    /// Registered two-input transition.
    Transition,
    /// Registered zero-input generator.
    Generator,
    /// Ordered layer composition.
    Composite,
}

/// One owned layer reference in a graph composition node.
#[derive(Copy, Clone, Debug)]
pub struct GraphLayer {
    /// Node whose result is sampled as this layer.
    pub source: RenderNodeId,
    /// Layer transform and opacity.
    pub visual: LayerTransform,
    /// Artistic blend operation.
    pub blend_mode: BlendMode,
}

/// An insertion-ordered, acyclic render program.
#[derive(Debug)]
pub struct RenderGraph<'a> {
    pub(crate) id: u32,
    pub(crate) size: RenderSize,
    pub(crate) nodes: Vec<RenderNode<'a>>,
    pub(crate) cache_keys: Vec<RenderCacheKey>,
    /// Whether each node's key is complete: no source under it lacks a
    /// stable key.
    pub(crate) stable: Vec<bool>,
    /// Each node's cache intent; `None` for a node that is not a candidate.
    pub(crate) intents: Vec<Option<crate::CacheIntent>>,
    pub(crate) output: Option<RenderNodeId>,
    /// The space this graph's composites blend in; `None` takes the
    /// renderer's.
    pub(crate) blend_space: Option<crate::BlendSpace>,
}

static NEXT_GRAPH_ID: AtomicU32 = AtomicU32::new(1);

#[derive(Debug)]
pub(crate) enum RenderNode<'a> {
    Source(&'a wgpu::TextureView),
    Effect {
        effect: EffectId,
        source: RenderNodeId,
        params: EffectParams<'a>,
        resources: EffectResources,
        runtime: EffectRuntime,
    },
    Transition {
        effect: EffectId,
        from: RenderNodeId,
        to: RenderNodeId,
        params: EffectParams<'a>,
        resources: EffectResources,
        runtime: EffectRuntime,
    },
    Generator {
        effect: EffectId,
        params: EffectParams<'a>,
        resources: EffectResources,
        runtime: EffectRuntime,
    },
    Composite {
        layers: Vec<GraphLayer>,
        background: Option<Color>,
    },
}

/// Deterministic 128-bit key for a source or rendered graph result.
#[derive(Copy, Clone, Debug, Eq, Hash, PartialEq)]
pub struct RenderCacheKey(pub(crate) u128);

impl RenderCacheKey {
    /// Creates a stable source key supplied by a decode or asset cache.
    #[must_use]
    pub const fn source(value: u64) -> Self {
        Self(value as u128)
    }

    /// Creates a key from all 128 bits, as [`Self::value`] gives them back. A
    /// key a caller derives for something other than a decoded source sets
    /// high bits, so it never equals a [`Self::source`] key.
    #[must_use]
    pub const fn from_value(value: u128) -> Self {
        Self(value)
    }

    /// Returns the stable 128-bit representation.
    #[must_use]
    pub const fn value(self) -> u128 {
        self.0
    }
}

/// Structural or execution failure in a render graph.
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
#[non_exhaustive]
pub enum GraphError {
    /// A node references an ID not already present in the graph.
    InvalidDependency,
    /// No final output node was selected.
    MissingOutput,
    /// An external source cannot be returned as an owned render result.
    SourceOutput,
    /// A registered shader kind does not match its graph node.
    EffectKindMismatch,
    /// A rendering operation failed.
    Render(RenderError),
}

impl fmt::Display for GraphError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::InvalidDependency => {
                formatter.write_str("render graph dependency must name an earlier node")
            }
            Self::MissingOutput => formatter.write_str("render graph has no selected output"),
            Self::SourceOutput => {
                formatter.write_str("render graph output must be a rendered node")
            }
            Self::EffectKindMismatch => {
                formatter.write_str("registered effect kind does not match its graph node")
            }
            Self::Render(error) => write!(formatter, "render graph execution failed: {error}"),
        }
    }
}

impl std::error::Error for GraphError {
    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
        match self {
            Self::Render(error) => Some(error),
            _ => None,
        }
    }
}

impl From<RenderError> for GraphError {
    fn from(error: RenderError) -> Self {
        Self::Render(error)
    }
}

impl GraphError {
    /// Collapses a graph failure into the renderer's error type, reporting
    /// every structural fault as [`RenderError::InvalidGraph`].
    #[must_use]
    pub const fn into_render_error(self) -> RenderError {
        match self {
            Self::Render(error) => error,
            Self::InvalidDependency
            | Self::MissingOutput
            | Self::SourceOutput
            | Self::EffectKindMismatch => RenderError::InvalidGraph,
        }
    }
}

impl<'a> RenderGraph<'a> {
    /// Creates an empty graph whose rendered nodes share one output size.
    #[must_use]
    pub fn new(size: RenderSize) -> Self {
        Self {
            id: NEXT_GRAPH_ID.fetch_add(1, Ordering::Relaxed),
            size,
            nodes: Vec::new(),
            cache_keys: Vec::new(),
            stable: Vec::new(),
            intents: Vec::new(),
            output: None,
            blend_space: None,
        }
    }

    /// Blends this graph's composites in `space` rather than in the
    /// renderer's default space. A timeline frame takes it from its project,
    /// so preview and export blend alike whatever renderer draws them.
    pub fn set_blend_space(&mut self, space: crate::BlendSpace) {
        self.blend_space = Some(space);
    }

    /// Adds an externally owned source texture.
    pub fn add_source(&mut self, texture: SourceView<'a>) -> RenderNodeId {
        let key = transient_source_key(self.id, self.nodes.len());
        self.push(RenderNode::Source(texture.wgpu_view()), key, false)
    }

    /// Adds an externally owned texture with a cross-frame stable cache key.
    ///
    /// The key is the caller's promise that the texture's pixels depend on
    /// nothing it leaves out: the source's content, the frame, and how it was
    /// decoded and converted. Results drawn from it can then be cached.
    pub fn add_source_with_key(
        &mut self,
        texture: SourceView<'a>,
        key: RenderCacheKey,
    ) -> RenderNodeId {
        self.push(RenderNode::Source(texture.wgpu_view()), key, true)
    }

    /// Adds a registered one-input effect node.
    ///
    /// # Errors
    /// Returns [`GraphError::InvalidDependency`] unless `source` is earlier.
    pub fn add_effect(
        &mut self,
        effect: EffectId,
        source: RenderNodeId,
        params: EffectParams<'a>,
        runtime: EffectRuntime,
    ) -> Result<RenderNodeId, GraphError> {
        self.add_effect_with_resources(effect, source, params, EffectResources::new(), runtime)
    }

    /// Adds a registered one-input effect node with external resources.
    ///
    /// The built-in Gaussian blur and glow are added as the internal passes
    /// that draw them, and the returned node is the last of those.
    ///
    /// # Errors
    /// Returns [`GraphError::InvalidDependency`] unless `source` is earlier;
    /// for a built-in drawn as passes, also [`RenderError::InvalidEffectParams`]
    /// when its parameters are not ones it declares or are out of range.
    pub fn add_effect_with_resources(
        &mut self,
        effect: EffectId,
        source: RenderNodeId,
        params: EffectParams<'a>,
        resources: EffectResources,
        runtime: EffectRuntime,
    ) -> Result<RenderNodeId, GraphError> {
        self.validate_dependency(source)?;
        // Some built-ins are drawn as several internal passes; they bind no resources.
        if let Some(expanded) = self.add_expanded_effect(&effect, source, &params, runtime) {
            if resources.iter().next().is_some() {
                return Err(RenderError::InvalidEffectParams.into());
            }
            return expanded;
        }
        let key = effect_cache_key_with_resources(
            b"effect",
            self.size,
            &effect,
            &[self.cache_keys[source.index]],
            &params,
            &resources,
            runtime,
        );
        let stable = self.stable[source.index];
        Ok(self.push(
            RenderNode::Effect {
                effect,
                source,
                params,
                resources,
                runtime,
            },
            key,
            stable,
        ))
    }

    /// Adds a registered generator node: a picture drawn from its
    /// parameters alone, at the graph's size.
    pub fn add_generator(
        &mut self,
        effect: EffectId,
        params: EffectParams<'a>,
        runtime: EffectRuntime,
    ) -> RenderNodeId {
        self.add_generator_with_resources(effect, params, EffectResources::new(), runtime)
    }

    /// Adds a registered generator node that samples external resources,
    /// bound by the names its definition declares, as an effect's are.
    pub fn add_generator_with_resources(
        &mut self,
        effect: EffectId,
        params: EffectParams<'a>,
        resources: EffectResources,
        runtime: EffectRuntime,
    ) -> RenderNodeId {
        let key = effect_cache_key_with_resources(
            b"generator",
            self.size,
            &effect,
            &[],
            &params,
            &resources,
            runtime,
        );
        self.push(
            RenderNode::Generator {
                effect,
                params,
                resources,
                runtime,
            },
            key,
            true,
        )
    }

    /// Adds a registered two-input transition node.
    ///
    /// # Errors
    /// Returns [`GraphError::InvalidDependency`] unless both inputs are earlier.
    pub fn add_transition(
        &mut self,
        effect: EffectId,
        from: RenderNodeId,
        to: RenderNodeId,
        params: EffectParams<'a>,
        runtime: EffectRuntime,
    ) -> Result<RenderNodeId, GraphError> {
        self.add_transition_with_resources(
            effect,
            from,
            to,
            params,
            EffectResources::new(),
            runtime,
        )
    }

    /// Adds a registered two-input transition node with external resources.
    ///
    /// # Errors
    /// Returns [`GraphError::InvalidDependency`] unless both inputs are earlier.
    pub fn add_transition_with_resources(
        &mut self,
        effect: EffectId,
        from: RenderNodeId,
        to: RenderNodeId,
        params: EffectParams<'a>,
        resources: EffectResources,
        runtime: EffectRuntime,
    ) -> Result<RenderNodeId, GraphError> {
        self.validate_dependency(from)?;
        self.validate_dependency(to)?;
        let key = effect_cache_key_with_resources(
            b"transition",
            self.size,
            &effect,
            &[self.cache_keys[from.index], self.cache_keys[to.index]],
            &params,
            &resources,
            runtime,
        );
        let stable = self.stable[from.index] && self.stable[to.index];
        Ok(self.push(
            RenderNode::Transition {
                effect,
                from,
                to,
                params,
                resources,
                runtime,
            },
            key,
            stable,
        ))
    }

    /// Adds an ordered layer-composition node over a transparent target.
    ///
    /// # Errors
    /// Returns [`GraphError::InvalidDependency`] for a missing layer source.
    pub fn add_composite(&mut self, layers: Vec<GraphLayer>) -> Result<RenderNodeId, GraphError> {
        self.push_composite(layers, None)
    }

    /// Adds an ordered layer-composition node over a solid background.
    ///
    /// `background` is the bottom layer: the first layer blends against it as
    /// against any lower layer. Like [`crate::Renderer::render_solid`]'s
    /// color, it is a premultiplied, sRGB-encoded storage value.
    ///
    /// # Errors
    /// Returns [`GraphError::InvalidDependency`] for a missing layer source,
    /// or [`RenderError::InvalidColor`] for a background out of range or not
    /// premultiplied.
    pub fn add_composite_over(
        &mut self,
        layers: Vec<GraphLayer>,
        background: Color,
    ) -> Result<RenderNodeId, GraphError> {
        if !background.is_valid() {
            return Err(GraphError::Render(RenderError::InvalidColor));
        }
        self.push_composite(layers, Some(background))
    }

    fn push_composite(
        &mut self,
        layers: Vec<GraphLayer>,
        background: Option<Color>,
    ) -> Result<RenderNodeId, GraphError> {
        for layer in &layers {
            self.validate_dependency(layer.source)?;
        }
        let key = composite_cache_key(self.size, &layers, background, &self.cache_keys);
        let stable = layers.iter().all(|layer| self.stable[layer.source.index]);
        Ok(self.push(RenderNode::Composite { layers, background }, key, stable))
    }

    /// Selects the graph result.
    ///
    /// # Errors
    /// Returns [`GraphError::InvalidDependency`] for an unknown node.
    pub fn set_output(&mut self, output: RenderNodeId) -> Result<(), GraphError> {
        self.validate_dependency(output)?;
        self.output = Some(output);
        Ok(())
    }

    /// Returns the number of nodes in insertion order.
    #[must_use]
    pub fn node_count(&self) -> usize {
        self.nodes.len()
    }

    /// Returns the public category of a node.
    #[must_use]
    pub fn node_kind(&self, id: RenderNodeId) -> Option<RenderNodeKind> {
        if id.graph == self.id {
            self.nodes.get(id.index).map(RenderNode::kind)
        } else {
            None
        }
    }

    /// Names `node` a cache candidate: its result is looked up before it is
    /// drawn and kept after, as `intent` says, when its key is complete.
    /// [`crate::CacheIntent::Bypass`] instead keeps it, everything it is drawn
    /// from, and everything drawn from it out of the cache.
    ///
    /// # Errors
    /// Returns [`GraphError::InvalidDependency`] for an unknown node.
    pub fn set_cache_intent(
        &mut self,
        node: RenderNodeId,
        intent: crate::CacheIntent,
    ) -> Result<(), GraphError> {
        self.validate_dependency(node)?;
        self.intents[node.index] = Some(intent);
        Ok(())
    }

    /// Whether `node`'s result can be cached, and if not, why.
    ///
    /// # Errors
    /// Returns [`GraphError::InvalidDependency`] for an unknown node.
    pub fn cache_eligibility(
        &self,
        node: RenderNodeId,
    ) -> Result<crate::CacheEligibility, GraphError> {
        self.validate_dependency(node)?;
        Ok(self.eligibility()[node.index])
    }

    /// Every node's eligibility. A bypass reaches down to what a node is
    /// drawn from and up to what is drawn from it; a transient source only up.
    pub(crate) fn eligibility(&self) -> Vec<crate::CacheEligibility> {
        let count = self.nodes.len();
        let mut bypassed: Vec<bool> = self
            .intents
            .iter()
            .map(|intent| *intent == Some(crate::CacheIntent::Bypass))
            .collect();
        // Up: nodes are in dependency order, so inputs come first.
        for index in 0..count {
            if self.nodes[index]
                .dependencies()
                .iter()
                .any(|input| bypassed[input.index])
            {
                bypassed[index] = true;
            }
        }
        // Down: from each explicitly bypassed node to its inputs.
        let mut down: Vec<bool> = self
            .intents
            .iter()
            .map(|intent| *intent == Some(crate::CacheIntent::Bypass))
            .collect();
        for index in (0..count).rev() {
            if down[index] {
                for input in self.nodes[index].dependencies() {
                    down[input.index] = true;
                }
            }
        }
        (0..count)
            .map(|index| {
                if bypassed[index] || down[index] {
                    crate::CacheEligibility::Bypassed
                } else if self.stable[index] {
                    crate::CacheEligibility::Eligible
                } else {
                    crate::CacheEligibility::TransientSource
                }
            })
            .collect()
    }

    fn push(
        &mut self,
        node: RenderNode<'a>,
        cache_key: RenderCacheKey,
        stable: bool,
    ) -> RenderNodeId {
        let id = RenderNodeId {
            graph: self.id,
            index: self.nodes.len(),
        };
        self.nodes.push(node);
        self.cache_keys.push(cache_key);
        self.stable.push(stable);
        self.intents.push(None);
        id
    }

    fn validate_dependency(&self, dependency: RenderNodeId) -> Result<(), GraphError> {
        if dependency.graph == self.id && dependency.index < self.nodes.len() {
            Ok(())
        } else {
            Err(GraphError::InvalidDependency)
        }
    }
}

impl RenderNodeKind {
    /// The label a pass of this kind is timed under (see
    /// [`crate::PassTiming::label`]).
    pub(crate) const fn pass_label(self) -> &'static str {
        match self {
            Self::Source => "source",
            Self::Effect => "effect",
            Self::Transition => "transition",
            Self::Generator => "generator",
            Self::Composite => "composite",
        }
    }
}

impl RenderNode<'_> {
    pub(crate) const fn kind(&self) -> RenderNodeKind {
        match self {
            Self::Source(_) => RenderNodeKind::Source,
            Self::Effect { .. } => RenderNodeKind::Effect,
            Self::Transition { .. } => RenderNodeKind::Transition,
            Self::Generator { .. } => RenderNodeKind::Generator,
            Self::Composite { .. } => RenderNodeKind::Composite,
        }
    }

    pub(crate) fn dependencies(&self) -> Vec<RenderNodeId> {
        match self {
            Self::Source(_) | Self::Generator { .. } => Vec::new(),
            Self::Effect { source, .. } => vec![*source],
            Self::Transition { from, to, .. } => vec![*from, *to],
            Self::Composite { layers, .. } => layers.iter().map(|layer| layer.source).collect(),
        }
    }
}

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

    #[test]
    fn every_node_and_setting_refuses_a_node_of_another_graph_or_one_not_yet_added() {
        // A node id carries its graph, so a dependency check that compared only indices
        // would wire one graph's node into another; every method taking a node refuses it.
        let size = RenderSize::new(16, 9).expect("non-zero size");
        let effect = EffectId::new("test.effect".into(), 1);
        let mut other = RenderGraph::new(size);
        let foreign = other.add_generator(
            effect.clone(),
            EffectParams::new(),
            EffectRuntime::default(),
        );
        let mut graph = RenderGraph::new(size);
        let own = graph.add_generator(
            effect.clone(),
            EffectParams::new(),
            EffectRuntime::default(),
        );
        // The same index as a node of this graph, but another graph's.
        assert_eq!(foreign.index, own.index);
        let unknown = RenderNodeId {
            graph: graph.id,
            index: 1,
        };
        let layer = |source| GraphLayer {
            source,
            visual: crate::LayerTransform {
                position: [0.5, 0.5],
                anchor: [0.5, 0.5],
                scale: [1.0, 1.0],
                rotation_degrees: 0.0,
                opacity: 1.0,
            },
            blend_mode: crate::BlendMode::Normal,
        };
        for bad in [foreign, unknown] {
            let invalid = Err(GraphError::InvalidDependency);
            assert_eq!(
                graph.add_effect(
                    effect.clone(),
                    bad,
                    EffectParams::new(),
                    EffectRuntime::default()
                ),
                invalid
            );
            assert_eq!(
                graph.add_transition(
                    effect.clone(),
                    own,
                    bad,
                    EffectParams::new(),
                    EffectRuntime::default()
                ),
                invalid
            );
            assert_eq!(
                graph.add_transition(
                    effect.clone(),
                    bad,
                    own,
                    EffectParams::new(),
                    EffectRuntime::default()
                ),
                invalid
            );
            assert_eq!(graph.add_composite(vec![layer(own), layer(bad)]), invalid);
            assert_eq!(
                graph.add_composite_over(vec![layer(bad)], Color::BLACK),
                invalid
            );
            assert_eq!(graph.set_output(bad), Err(GraphError::InvalidDependency));
            assert_eq!(
                graph.set_cache_intent(bad, crate::CacheIntent::Pin),
                Err(GraphError::InvalidDependency)
            );
            assert_eq!(
                graph.cache_eligibility(bad),
                Err(GraphError::InvalidDependency)
            );
            assert_eq!(graph.node_kind(bad), None);
        }
        assert_eq!(graph.node_count(), 1);
        assert_eq!(graph.node_kind(own), Some(RenderNodeKind::Generator));
        // An out-of-range background is refused before its layers are looked at.
        assert_eq!(
            graph.add_composite_over(vec![layer(foreign)], Color::rgba(1.5, 0.0, 0.0, 1.0)),
            Err(GraphError::Render(RenderError::InvalidColor))
        );
        assert_eq!(graph.node_count(), 1);
    }

    #[test]
    fn a_graph_compiles_only_once_an_output_is_chosen() {
        let size = RenderSize::new(16, 9).expect("non-zero size");
        let mut graph = RenderGraph::new(size);
        let output = graph.add_composite(Vec::new()).expect("empty clear node");
        assert_eq!(graph.compile().err(), Some(GraphError::MissingOutput));
        assert_eq!(
            GraphError::MissingOutput.into_render_error(),
            RenderError::InvalidGraph
        );
        graph.set_output(output).expect("known output");
        assert_eq!(
            graph.compile().expect("compiles").execution_order(),
            [output]
        );
    }

    #[test]
    fn quality_compilation_exposes_centered_temporal_schedule() {
        let size = RenderSize::new(16, 9).expect("non-zero size");
        let mut graph = RenderGraph::new(size);
        let output = graph.add_composite(Vec::new()).expect("empty clear node");
        graph.set_output(output).expect("known output");
        let plan = graph
            .compile_with_quality(crate::RenderQualityControls {
                max_filter_samples: 12,
                motion_blur_subframes: 4,
            })
            .expect("compiled");
        assert_eq!(plan.temporal_offsets(), [-0.375, -0.125, 0.125, 0.375]);
        assert_eq!(plan.filter_sample_limit(output), None);
    }
}