sparse_strips/vello_common/src/render_graph.rs - external/github.com/linebender/vello - Git at Google

 // Copyright 2025 the Vello Authors
 // SPDX-License-Identifier: Apache-2.0 OR MIT

 //! Render graph for multi-pass rendering with filter effects.
 //!
 //! This module provides a directed acyclic graph (DAG) representation of the rendering pipeline,
 //! enabling efficient multi-pass rendering when layers have filter effects applied.
 //!
 //! # Overview
 //!
 //! The render graph tracks dependencies between rendering operations (nodes) and ensures they
 //! execute in the correct order. Each node represents either:
 //! - The root (backdrop) layer that forms the base for compositing
 //! - A filtered layer that renders geometry, applies effects, and blends the result
 //!
 //! # Key Features
 //!
 //! - **Incremental execution order**: The graph builds its execution order as layers are popped
 //!   during scene encoding, avoiding the need for a full topological sort at render time.
 //! - **Data dependencies**: Edges represent dependencies where one layer's output is consumed
 //!   as input to another operation (e.g., a filter reading from a previous layer's buffer).
 //! - **Efficient traversal**: The pre-computed execution order allows O(1) iteration over nodes
 //!   in dependency order, with children always processed before their parents.
 //!
 //! # Usage Pattern
 //!
 //! 1. During scene encoding, nodes are added via [`RenderGraph::add_node`] as layers are created
 //! 2. When layers with dependencies are popped, edges are added via [`RenderGraph::add_edge`]
 //! 3. As each layer completes, it's recorded in execution order via [`RenderGraph::record_node_for_execution`]
 //! 4. At render time, iterate nodes in order using [`RenderGraph::execution_order`]
 //!
 //! # Example Structure
 //!
 //! ```text
 //! RootLayer (id=0) ← backdrop
 //!     │
 //!     └─→ FilterLayer (id=1, blur filter)
 //!             │
 //!             └─→ FilterLayer (id=2, drop shadow filter)
 //!
 //! Execution order: [2, 1, 0] (deepest children first, then parents)
 //! ```
 //!
 //! In this example, `FilterLayer 2` (drop shadow) is the most deeply nested child, so it
 //! executes first. Then `FilterLayer 1` (blur) executes and can reference `FilterLayer 2`'s output
 //! if needed. Finally, the `RootLayer` composites all filtered results into the final image.
 //!
 //! # Future Improvements
 //!
 //! TODO: Consider using `render_graph` for `FilterGraph` execution for filters. The render graph
 //! infrastructure could potentially be extended to handle the internal DAG structure within
 //! individual filter effects, not just layer-to-layer dependencies.

 use crate::coarse::WideTilesBbox;
 use crate::filter_effects::Filter;
 use crate::kurbo::Affine;
 use alloc::vec;
 use alloc::vec::Vec;
 use hashbrown::HashMap;

 /// A render graph containing nodes and edges representing the rendering pipeline.
 ///
 /// This graph tracks layers with filter effects and their dependencies, enabling
 /// multi-pass rendering where filter outputs can be used as inputs to subsequent operations.
 #[derive(Debug, Clone)]
 pub struct RenderGraph {
     /// All render operations (layers) in the graph.
     pub nodes: Vec<RenderNode>,
     /// Dependencies between nodes, defining execution order.
     pub edges: Vec<RenderEdge>,
     /// Counter for generating unique node IDs.
     next_node_id: NodeId,
     /// Pre-computed execution order collected during `pop_layer` calls.
     /// This is built incrementally as layers are popped (children before parents),
     /// avoiding the need for topological sort at render time.
     node_execution_order: Vec<NodeId>,
     /// The root layer node ID, tracked separately since it's never popped.
     /// This is appended to the execution order when iterating.
     root_node: Option<NodeId>,
     /// Flag indicating whether the graph contains any filter layers.
     /// Set to true when a `FilterLayer` node is added.
     has_filters: bool,
 }

 /// The type of dependency between nodes.
 #[derive(Debug, Clone)]
 pub enum DependencyKind {
     /// Sequential execution: the `from` node must execute before the `to` node.
     ///
     /// The `to` node consumes output from the `from` node via the specified layer.
     /// For example, a parent filter reads from a child layer buffer produced by a previous operation.
     Sequential {
         /// The layer that connects the two nodes, whose output flows from `from` to `to`.
         layer_id: LayerId,
     },
 }

 impl Default for RenderGraph {
     fn default() -> Self {
         Self::new()
     }
 }

 impl RenderGraph {
     /// Creates a new empty render graph.
     ///
     /// The graph starts with no nodes or edges. Nodes are added via [`add_node`](Self::add_node)
     /// as layers are created during scene encoding.
     pub fn new() -> Self {
         Self {
             nodes: Vec::new(),
             edges: Vec::new(),
             next_node_id: 0,
             node_execution_order: Vec::new(),
             root_node: None,
             has_filters: false,
         }
     }

     /// Clears the render graph state while preserving allocated capacity.
     ///
     /// This resets the graph to an empty state (equivalent to [`new`](Self::new))
     /// but reuses the existing memory allocations, avoiding the need to reallocate
     /// when building a new scene.
     ///
     /// After calling `clear()`, the graph will have no nodes or edges, and counters
     /// will be reset to their initial state.
     pub fn clear(&mut self) {
         self.nodes.clear();
         self.edges.clear();
         self.next_node_id = 0;
         self.node_execution_order.clear();
         self.root_node = None;
         self.has_filters = false;
     }

     /// Add a node to the graph and return its ID.
     ///
     /// This is called during scene encoding when a new layer is created. The returned ID
     /// should be stored with the layer to establish edges later when dependencies are known.
     pub fn add_node(&mut self, kind: RenderNodeKind) -> NodeId {
         let id = self.next_node_id;
         self.next_node_id += 1;

         // Track root node separately since it's never popped and executes last
         if matches!(kind, RenderNodeKind::RootLayer { .. }) {
             self.root_node = Some(id);
         }

         // Track if we have any filters to avoid scanning nodes later
         if matches!(kind, RenderNodeKind::FilterLayer { .. }) {
             self.has_filters = true;
         }

         self.nodes.push(RenderNode { id, kind });
         id
     }

     /// Add an edge between two nodes, establishing a dependency relationship.
     ///
     /// This is called when a layer with dependencies is popped during scene encoding.
     /// The edge ensures that `from` node executes before `to` node, typically because
     /// `to` needs to read data produced by `from` (e.g., a filter reading from a layer buffer).
     pub fn add_edge(&mut self, from: NodeId, to: NodeId, kind: DependencyKind) {
         self.edges.push(RenderEdge { from, to, kind });
     }

     /// Record a node as ready for execution in topological order.
     ///
     /// This is called from `pop_layer` to incrementally build the execution order
     /// as layers are popped. Since layers are popped in a depth-first manner (children
     /// before parents), this naturally builds the correct dependency order without
     /// requiring a separate topological sort at render time.
     ///
     /// # Example
     ///
     /// For nested layers A → B → C (where C is the deepest child):
     /// - C is popped first → recorded first
     /// - B is popped second → recorded second
     /// - A is popped last → recorded last
     ///
     /// This gives execution order [C, B, A], which respects dependencies.
     pub fn record_node_for_execution(&mut self, node_id: NodeId) {
         self.node_execution_order.push(node_id);
     }

     /// Check if the graph contains any filter passes.
     ///
     /// Returns `true` if any layers have filter effects that need processing.
     /// This is useful for determining whether to use the multi-pass rendering
     /// pipeline (with filter support) or a simpler single-pass approach.
     ///
     /// This is set when filter nodes are added.
     pub fn has_filters(&self) -> bool {
         self.has_filters
     }

     /// Get an iterator over nodes in execution order.
     ///
     /// Returns filter layers followed by the root layer, in the order they should be executed.
     /// This order is built incrementally during `pop_layer` calls (children before parents),
     /// avoiding the need for topological sort at render time. Returns an iterator to avoid allocation.
     pub fn execution_order(&self) -> impl Iterator<Item = NodeId> + '_ {
         self.node_execution_order
             .iter()
             .copied()
             .chain(self.root_node)
     }

     /// Topologically sort nodes based on their dependencies using Kahn's algorithm.
     ///
     /// Returns nodes in execution order, ensuring all dependencies are satisfied before
     /// each node is processed. This implements a standard topological sort with cycle detection.
     ///
     /// # Performance
     ///
     /// This is primarily used for validation and debugging. For normal rendering,
     /// prefer [`execution_order`](Self::execution_order) which is pre-computed during
     /// scene encoding and avoids the O(V+E) sorting overhead.
     ///
     /// # Panics
     ///
     /// Panics if the graph contains a cycle, which should never happen in a valid render graph.
     #[allow(
         dead_code,
         reason = "we don't use currently topological sort but will in the future"
     )]
     pub fn topological_sort(&self) -> Vec<NodeId> {
         // Track how many incoming edges each node has (dependencies it's waiting for)
         let mut in_degree = vec![0; self.nodes.len()];

         // Map each node to its dependents (nodes that depend on it)
         let mut adj_list: HashMap<NodeId, Vec<NodeId>> = HashMap::new();

         // Build adjacency list and count incoming edges for each node
         for edge in &self.edges {
             adj_list.entry(edge.from).or_default().push(edge.to);
             in_degree[edge.to] += 1;
         }

         // Start with nodes that have no dependencies (in-degree = 0)
         // These are safe to execute immediately
         let mut queue: Vec<NodeId> = (0..self.nodes.len())
             .filter(|&i| in_degree[i] == 0)
             .collect();

         let mut result = Vec::new();

         // Process nodes in dependency order (Kahn's algorithm)
         while let Some(node_id) = queue.pop() {
             result.push(node_id);

             // For each node that depends on this one, mark this dependency as satisfied
             if let Some(neighbors) = adj_list.get(&node_id) {
                 for &neighbor in neighbors {
                     in_degree[neighbor] -= 1;
                     // If all dependencies are now satisfied, this node is ready to execute
                     if in_degree[neighbor] == 0 {
                         queue.push(neighbor);
                     }
                 }
             }
         }

         // If we didn't process all nodes, there's a cycle (which should never happen)
         assert_eq!(
             result.len(),
             self.nodes.len(),
             "Cycle detected in render graph"
         );
         result
     }
 }

 /// A node in the render graph representing a single render operation.
 #[derive(Debug, Clone)]
 pub struct RenderNode {
     /// Unique identifier for this node.
     pub id: NodeId,
     /// The type of render operation this node performs.
     pub kind: RenderNodeKind,
 }

 /// An edge representing a dependency between two nodes.
 #[derive(Debug, Clone)]
 pub struct RenderEdge {
     /// The source node that must complete first.
     pub from: NodeId,
     /// The destination node that depends on the source.
     pub to: NodeId,
     /// The type of dependency relationship.
     pub kind: DependencyKind,
 }

 /// The type of operation a render node performs.
 ///
 /// Each variant represents a different kind of rendering pass in the pipeline.
 /// Nodes are executed in dependency order to ensure correct compositing and filtering.
 #[derive(Debug, Clone)]
 pub enum RenderNodeKind {
     /// The root (backdrop) layer that serves as the base for compositing.
     ///
     /// This layer is always present and is rendered last, after all filter layers have
     /// been processed. It contains all non-filtered geometry and serves as the final
     /// compositing target.
     RootLayer {
         /// ID of the root layer.
         layer_id: LayerId,
         /// Bounding box in wide tile coordinates covered by this layer.
         wtile_bbox: WideTilesBbox,
     },
     /// A layer with filter effects applied.
     ///
     /// This combines multiple passes: render geometry → apply filter → blend result.
     /// Layers are added to the render graph only if they have filters. The filter
     /// output may be consumed by other filter layers or composited into the root layer.
     FilterLayer {
         /// ID of this filtered layer.
         layer_id: LayerId,
         /// The filter effect to apply.
         filter: Filter,
         /// Bounding box in wide tile coordinates containing geometry for this layer.
         wtile_bbox: WideTilesBbox,
         /// Transform that was active when the layer was created.
         /// Used to scale filter parameters based on the current scale/zoom level.
         transform: Affine,
     },
 }

 /// Unique identifier for a layer in the rendering system.
 ///
 /// Layer IDs are assigned by the encoding system and used to track layer buffers
 /// across multiple render passes. A layer may or may not have a corresponding node
 /// in the render graph (only layers with filters create graph nodes).
 pub type LayerId = u32;

 /// Unique identifier for a node in the render graph.
 ///
 /// Node IDs are assigned sequentially as nodes are added during scene encoding.
 /// They are used to reference nodes when adding edges and during execution order traversal.
 pub type NodeId = usize;

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

     #[test]
     fn new_creates_empty_graph() {
         let graph = RenderGraph::new();
         assert_eq!(graph.nodes.len(), 0);
         assert_eq!(graph.edges.len(), 0);
         assert!(!graph.has_filters());
         assert!(graph.root_node.is_none());
     }

     #[test]
     fn clear_resets_to_empty_state() {
         let mut graph = RenderGraph::new();
         graph.add_node(RenderNodeKind::RootLayer {
             layer_id: 0,
             wtile_bbox: dummy_bbox(),
         });
         graph.add_node(RenderNodeKind::FilterLayer {
             layer_id: 1,
             filter: dummy_filter(),
             wtile_bbox: dummy_bbox(),
             transform: Affine::IDENTITY,
         });
         graph.record_node_for_execution(1);

         graph.clear();

         assert_eq!(graph.nodes.len(), 0);
         assert_eq!(graph.edges.len(), 0);
         assert_eq!(graph.next_node_id, 0);
         assert!(graph.root_node.is_none());
         assert!(!graph.has_filters());
         assert_eq!(graph.execution_order().count(), 0);
     }

     #[test]
     fn clear_preserves_capacity() {
         let mut graph = RenderGraph::new();
         let from = graph.add_node(RenderNodeKind::RootLayer {
             layer_id: 0,
             wtile_bbox: dummy_bbox(),
         });
         let to = graph.add_node(RenderNodeKind::RootLayer {
             layer_id: 1,
             wtile_bbox: dummy_bbox(),
         });
         graph.add_edge(from, to, DependencyKind::Sequential { layer_id: 1 });

         let nodes_capacity = graph.nodes.capacity();
         let edges_capacity = graph.edges.capacity();

         graph.clear();

         assert!(graph.nodes.capacity() >= nodes_capacity);
         assert!(graph.edges.capacity() >= edges_capacity);
     }

     #[test]
     fn add_node_returns_sequential_ids() {
         let mut graph = RenderGraph::new();
         let id0 = graph.add_node(RenderNodeKind::RootLayer {
             layer_id: 0,
             wtile_bbox: dummy_bbox(),
         });
         let id1 = graph.add_node(RenderNodeKind::FilterLayer {
             layer_id: 1,
             filter: dummy_filter(),
             wtile_bbox: dummy_bbox(),
             transform: Affine::IDENTITY,
         });

         assert_eq!(id0, 0);
         assert_eq!(id1, 1);
     }

     #[test]
     fn add_node_tracks_root() {
         let mut graph = RenderGraph::new();
         let root_id = graph.add_node(RenderNodeKind::RootLayer {
             layer_id: 0,
             wtile_bbox: dummy_bbox(),
         });

         assert_eq!(graph.root_node, Some(root_id));
     }

     #[test]
     fn add_node_filter_sets_has_filters() {
         let mut graph = RenderGraph::new();

         graph.add_node(RenderNodeKind::FilterLayer {
             layer_id: 1,
             filter: dummy_filter(),
             wtile_bbox: dummy_bbox(),
             transform: Affine::IDENTITY,
         });

         assert!(graph.has_filters());
     }

     #[test]
     fn add_node_root_does_not_set_has_filters() {
         let mut graph = RenderGraph::new();

         graph.add_node(RenderNodeKind::RootLayer {
             layer_id: 0,
             wtile_bbox: dummy_bbox(),
         });

         assert!(!graph.has_filters());
     }

     #[test]
     fn add_edge_creates_dependency() {
         let mut graph = RenderGraph::new();
         let from = graph.add_node(RenderNodeKind::FilterLayer {
             layer_id: 1,
             filter: dummy_filter(),
             wtile_bbox: dummy_bbox(),
             transform: Affine::IDENTITY,
         });
         let to = graph.add_node(RenderNodeKind::RootLayer {
             layer_id: 0,
             wtile_bbox: dummy_bbox(),
         });

         graph.add_edge(from, to, DependencyKind::Sequential { layer_id: 1 });

         assert_eq!(graph.edges.len(), 1);
         assert_eq!(graph.edges[0].from, from);
         assert_eq!(graph.edges[0].to, to);
     }

     #[test]
     fn add_edge_multiple_from_same_node() {
         let mut graph = RenderGraph::new();
         let from = graph.add_node(RenderNodeKind::FilterLayer {
             layer_id: 1,
             filter: dummy_filter(),
             wtile_bbox: dummy_bbox(),
             transform: Affine::IDENTITY,
         });
         let to1 = graph.add_node(RenderNodeKind::FilterLayer {
             layer_id: 2,
             filter: dummy_filter(),
             wtile_bbox: dummy_bbox(),
             transform: Affine::IDENTITY,
         });
         let to2 = graph.add_node(RenderNodeKind::RootLayer {
             layer_id: 0,
             wtile_bbox: dummy_bbox(),
         });

         graph.add_edge(from, to1, DependencyKind::Sequential { layer_id: 1 });
         graph.add_edge(from, to2, DependencyKind::Sequential { layer_id: 1 });

         assert_eq!(graph.edges.len(), 2);
     }

     #[test]
     fn execution_order_includes_recorded_nodes() {
         let mut graph = RenderGraph::new();
         let filter = graph.add_node(RenderNodeKind::FilterLayer {
             layer_id: 1,
             filter: dummy_filter(),
             wtile_bbox: dummy_bbox(),
             transform: Affine::IDENTITY,
         });

         graph.record_node_for_execution(filter);

         let order: Vec<_> = graph.execution_order().collect();
         assert_eq!(order, vec![filter]);
     }

     #[test]
     fn execution_order_includes_only_root_when_present() {
         let mut graph = RenderGraph::new();
         let root = graph.add_node(RenderNodeKind::RootLayer {
             layer_id: 0,
             wtile_bbox: dummy_bbox(),
         });

         let order: Vec<_> = graph.execution_order().collect();
         assert_eq!(order, vec![root]);
     }

     #[test]
     fn execution_order_root_comes_last() {
         let mut graph = RenderGraph::new();
         let filter1 = graph.add_node(RenderNodeKind::FilterLayer {
             layer_id: 1,
             filter: dummy_filter(),
             wtile_bbox: dummy_bbox(),
             transform: Affine::IDENTITY,
         });
         let filter2 = graph.add_node(RenderNodeKind::FilterLayer {
             layer_id: 2,
             filter: dummy_filter(),
             wtile_bbox: dummy_bbox(),
             transform: Affine::IDENTITY,
         });
         let root = graph.add_node(RenderNodeKind::RootLayer {
             layer_id: 0,
             wtile_bbox: dummy_bbox(),
         });

         graph.record_node_for_execution(filter2);
         graph.record_node_for_execution(filter1);

         let order: Vec<_> = graph.execution_order().collect();
         assert_eq!(order, vec![filter2, filter1, root]);
     }

     #[test]
     fn topological_sort_diamond_dependency() {
         let mut graph = RenderGraph::new();
         let bottom = graph.add_node(RenderNodeKind::FilterLayer {
             layer_id: 3,
             filter: dummy_filter(),
             wtile_bbox: dummy_bbox(),
             transform: Affine::IDENTITY,
         });
         let left = graph.add_node(RenderNodeKind::FilterLayer {
             layer_id: 1,
             filter: dummy_filter(),
             wtile_bbox: dummy_bbox(),
             transform: Affine::IDENTITY,
         });
         let right = graph.add_node(RenderNodeKind::FilterLayer {
             layer_id: 2,
             filter: dummy_filter(),
             wtile_bbox: dummy_bbox(),
             transform: Affine::IDENTITY,
         });
         let top = graph.add_node(RenderNodeKind::RootLayer {
             layer_id: 0,
             wtile_bbox: dummy_bbox(),
         });

         // Diamond: bottom -> left -> top, bottom -> right -> top
         graph.add_edge(bottom, left, DependencyKind::Sequential { layer_id: 3 });
         graph.add_edge(bottom, right, DependencyKind::Sequential { layer_id: 3 });
         graph.add_edge(left, top, DependencyKind::Sequential { layer_id: 1 });
         graph.add_edge(right, top, DependencyKind::Sequential { layer_id: 2 });

         let sorted = graph.topological_sort();
         assert_eq!(sorted, vec![bottom, right, left, top]);
     }

     fn dummy_filter() -> Filter {
         Filter::from_primitive(crate::filter_effects::FilterPrimitive::Flood {
             color: AlphaColor::from_rgba8(0, 0, 0, 255),
         })
     }

     fn dummy_bbox() -> WideTilesBbox {
         WideTilesBbox::new([0, 0, 0, 0])
     }
 }
	// Copyright 2025 the Vello Authors
	// SPDX-License-Identifier: Apache-2.0 OR MIT

	//! Render graph for multi-pass rendering with filter effects.
	//!
	//! This module provides a directed acyclic graph (DAG) representation of the rendering pipeline,
	//! enabling efficient multi-pass rendering when layers have filter effects applied.
	//!
	//! # Overview
	//!
	//! The render graph tracks dependencies between rendering operations (nodes) and ensures they
	//! execute in the correct order. Each node represents either:
	//! - The root (backdrop) layer that forms the base for compositing
	//! - A filtered layer that renders geometry, applies effects, and blends the result
	//!
	//! # Key Features
	//!
	//! - Incremental execution order: The graph builds its execution order as layers are popped
	//! during scene encoding, avoiding the need for a full topological sort at render time.
	//! - Data dependencies: Edges represent dependencies where one layer's output is consumed
	//! as input to another operation (e.g., a filter reading from a previous layer's buffer).
	//! - Efficient traversal: The pre-computed execution order allows O(1) iteration over nodes
	//! in dependency order, with children always processed before their parents.
	//!
	//! # Usage Pattern
	//!
	//! 1. During scene encoding, nodes are added via [`RenderGraph::add_node`] as layers are created
	//! 2. When layers with dependencies are popped, edges are added via [`RenderGraph::add_edge`]
	//! 3. As each layer completes, it's recorded in execution order via [`RenderGraph::record_node_for_execution`]
	//! 4. At render time, iterate nodes in order using [`RenderGraph::execution_order`]
	//!
	//! # Example Structure
	//!
	//! ```text
	//! RootLayer (id=0) ← backdrop
	//! │
	//! └─→ FilterLayer (id=1, blur filter)
	//! │
	//! └─→ FilterLayer (id=2, drop shadow filter)
	//!
	//! Execution order: [2, 1, 0] (deepest children first, then parents)
	//! ```
	//!
	//! In this example, `FilterLayer 2` (drop shadow) is the most deeply nested child, so it
	//! executes first. Then `FilterLayer 1` (blur) executes and can reference `FilterLayer 2`'s output
	//! if needed. Finally, the `RootLayer` composites all filtered results into the final image.
	//!
	//! # Future Improvements
	//!
	//! TODO: Consider using `render_graph` for `FilterGraph` execution for filters. The render graph
	//! infrastructure could potentially be extended to handle the internal DAG structure within
	//! individual filter effects, not just layer-to-layer dependencies.

	use crate::coarse::WideTilesBbox;
	use crate::filter_effects::Filter;
	use crate::kurbo::Affine;
	use alloc::vec;
	use alloc::vec::Vec;
	use hashbrown::HashMap;

	/// A render graph containing nodes and edges representing the rendering pipeline.
	///
	/// This graph tracks layers with filter effects and their dependencies, enabling
	/// multi-pass rendering where filter outputs can be used as inputs to subsequent operations.
	#[derive(Debug, Clone)]
	pub struct RenderGraph {
	/// All render operations (layers) in the graph.
	pub nodes: Vec<RenderNode>,
	/// Dependencies between nodes, defining execution order.
	pub edges: Vec<RenderEdge>,
	/// Counter for generating unique node IDs.
	next_node_id: NodeId,
	/// Pre-computed execution order collected during `pop_layer` calls.
	/// This is built incrementally as layers are popped (children before parents),
	/// avoiding the need for topological sort at render time.
	node_execution_order: Vec<NodeId>,
	/// The root layer node ID, tracked separately since it's never popped.
	/// This is appended to the execution order when iterating.
	root_node: Option<NodeId>,
	/// Flag indicating whether the graph contains any filter layers.
	/// Set to true when a `FilterLayer` node is added.
	has_filters: bool,
	}

	/// The type of dependency between nodes.
	#[derive(Debug, Clone)]
	pub enum DependencyKind {
	/// Sequential execution: the `from` node must execute before the `to` node.
	///
	/// The `to` node consumes output from the `from` node via the specified layer.
	/// For example, a parent filter reads from a child layer buffer produced by a previous operation.
	Sequential {
	/// The layer that connects the two nodes, whose output flows from `from` to `to`.
	layer_id: LayerId,
	},
	}

	impl Default for RenderGraph {
	fn default() -> Self {
	Self::new()
	}
	}

	impl RenderGraph {
	/// Creates a new empty render graph.
	///
	/// The graph starts with no nodes or edges. Nodes are added via [`add_node`](Self::add_node)
	/// as layers are created during scene encoding.
	pub fn new() -> Self {
	Self {
	nodes: Vec::new(),
	edges: Vec::new(),
	next_node_id: 0,
	node_execution_order: Vec::new(),
	root_node: None,
	has_filters: false,
	}
	}

	/// Clears the render graph state while preserving allocated capacity.
	///
	/// This resets the graph to an empty state (equivalent to [`new`](Self::new))
	/// but reuses the existing memory allocations, avoiding the need to reallocate
	/// when building a new scene.
	///
	/// After calling `clear()`, the graph will have no nodes or edges, and counters
	/// will be reset to their initial state.
	pub fn clear(&mut self) {
	self.nodes.clear();
	self.edges.clear();
	self.next_node_id = 0;
	self.node_execution_order.clear();
	self.root_node = None;
	self.has_filters = false;
	}

	/// Add a node to the graph and return its ID.
	///
	/// This is called during scene encoding when a new layer is created. The returned ID
	/// should be stored with the layer to establish edges later when dependencies are known.
	pub fn add_node(&mut self, kind: RenderNodeKind) -> NodeId {
	let id = self.next_node_id;
	self.next_node_id += 1;

	// Track root node separately since it's never popped and executes last
	if matches!(kind, RenderNodeKind::RootLayer { .. }) {
	self.root_node = Some(id);
	}

	// Track if we have any filters to avoid scanning nodes later
	if matches!(kind, RenderNodeKind::FilterLayer { .. }) {
	self.has_filters = true;
	}

	self.nodes.push(RenderNode { id, kind });
	id
	}

	/// Add an edge between two nodes, establishing a dependency relationship.
	///
	/// This is called when a layer with dependencies is popped during scene encoding.
	/// The edge ensures that `from` node executes before `to` node, typically because
	/// `to` needs to read data produced by `from` (e.g., a filter reading from a layer buffer).
	pub fn add_edge(&mut self, from: NodeId, to: NodeId, kind: DependencyKind) {
	self.edges.push(RenderEdge { from, to, kind });
	}

	/// Record a node as ready for execution in topological order.
	///
	/// This is called from `pop_layer` to incrementally build the execution order
	/// as layers are popped. Since layers are popped in a depth-first manner (children
	/// before parents), this naturally builds the correct dependency order without
	/// requiring a separate topological sort at render time.
	///
	/// # Example
	///
	/// For nested layers A → B → C (where C is the deepest child):
	/// - C is popped first → recorded first
	/// - B is popped second → recorded second
	/// - A is popped last → recorded last
	///
	/// This gives execution order [C, B, A], which respects dependencies.
	pub fn record_node_for_execution(&mut self, node_id: NodeId) {
	self.node_execution_order.push(node_id);
	}

	/// Check if the graph contains any filter passes.
	///
	/// Returns `true` if any layers have filter effects that need processing.
	/// This is useful for determining whether to use the multi-pass rendering
	/// pipeline (with filter support) or a simpler single-pass approach.
	///
	/// This is set when filter nodes are added.
	pub fn has_filters(&self) -> bool {
	self.has_filters
	}

	/// Get an iterator over nodes in execution order.
	///
	/// Returns filter layers followed by the root layer, in the order they should be executed.
	/// This order is built incrementally during `pop_layer` calls (children before parents),
	/// avoiding the need for topological sort at render time. Returns an iterator to avoid allocation.
	pub fn execution_order(&self) -> impl Iterator<Item = NodeId> + '_ {
	self.node_execution_order
	.iter()
	.copied()
	.chain(self.root_node)
	}

	/// Topologically sort nodes based on their dependencies using Kahn's algorithm.
	///
	/// Returns nodes in execution order, ensuring all dependencies are satisfied before
	/// each node is processed. This implements a standard topological sort with cycle detection.
	///
	/// # Performance
	///
	/// This is primarily used for validation and debugging. For normal rendering,
	/// prefer [`execution_order`](Self::execution_order) which is pre-computed during
	/// scene encoding and avoids the O(V+E) sorting overhead.
	///
	/// # Panics
	///
	/// Panics if the graph contains a cycle, which should never happen in a valid render graph.
	#[allow(
	dead_code,
	reason = "we don't use currently topological sort but will in the future"
	)]
	pub fn topological_sort(&self) -> Vec<NodeId> {
	// Track how many incoming edges each node has (dependencies it's waiting for)
	let mut in_degree = vec![0; self.nodes.len()];

	// Map each node to its dependents (nodes that depend on it)
	let mut adj_list: HashMap<NodeId, Vec<NodeId>> = HashMap::new();

	// Build adjacency list and count incoming edges for each node
	for edge in &self.edges {
	adj_list.entry(edge.from).or_default().push(edge.to);
	in_degree[edge.to] += 1;
	}

	// Start with nodes that have no dependencies (in-degree = 0)
	// These are safe to execute immediately
	let mut queue: Vec<NodeId> = (0..self.nodes.len())
	.filter(\|&i\| in_degree[i] == 0)
	.collect();

	let mut result = Vec::new();

	// Process nodes in dependency order (Kahn's algorithm)
	while let Some(node_id) = queue.pop() {
	result.push(node_id);

	// For each node that depends on this one, mark this dependency as satisfied
	if let Some(neighbors) = adj_list.get(&node_id) {
	for &neighbor in neighbors {
	in_degree[neighbor] -= 1;
	// If all dependencies are now satisfied, this node is ready to execute
	if in_degree[neighbor] == 0 {
	queue.push(neighbor);
	}
	}
	}
	}

	// If we didn't process all nodes, there's a cycle (which should never happen)
	assert_eq!(
	result.len(),
	self.nodes.len(),
	"Cycle detected in render graph"
	);
	result
	}
	}

	/// A node in the render graph representing a single render operation.
	#[derive(Debug, Clone)]
	pub struct RenderNode {
	/// Unique identifier for this node.
	pub id: NodeId,
	/// The type of render operation this node performs.
	pub kind: RenderNodeKind,
	}

	/// An edge representing a dependency between two nodes.
	#[derive(Debug, Clone)]
	pub struct RenderEdge {
	/// The source node that must complete first.
	pub from: NodeId,
	/// The destination node that depends on the source.
	pub to: NodeId,
	/// The type of dependency relationship.
	pub kind: DependencyKind,
	}

	/// The type of operation a render node performs.
	///
	/// Each variant represents a different kind of rendering pass in the pipeline.
	/// Nodes are executed in dependency order to ensure correct compositing and filtering.
	#[derive(Debug, Clone)]
	pub enum RenderNodeKind {
	/// The root (backdrop) layer that serves as the base for compositing.
	///
	/// This layer is always present and is rendered last, after all filter layers have
	/// been processed. It contains all non-filtered geometry and serves as the final
	/// compositing target.
	RootLayer {
	/// ID of the root layer.
	layer_id: LayerId,
	/// Bounding box in wide tile coordinates covered by this layer.
	wtile_bbox: WideTilesBbox,
	},
	/// A layer with filter effects applied.
	///
	/// This combines multiple passes: render geometry → apply filter → blend result.
	/// Layers are added to the render graph only if they have filters. The filter
	/// output may be consumed by other filter layers or composited into the root layer.
	FilterLayer {
	/// ID of this filtered layer.
	layer_id: LayerId,
	/// The filter effect to apply.
	filter: Filter,
	/// Bounding box in wide tile coordinates containing geometry for this layer.
	wtile_bbox: WideTilesBbox,
	/// Transform that was active when the layer was created.
	/// Used to scale filter parameters based on the current scale/zoom level.
	transform: Affine,
	},
	}

	/// Unique identifier for a layer in the rendering system.
	///
	/// Layer IDs are assigned by the encoding system and used to track layer buffers
	/// across multiple render passes. A layer may or may not have a corresponding node
	/// in the render graph (only layers with filters create graph nodes).
	pub type LayerId = u32;

	/// Unique identifier for a node in the render graph.
	///
	/// Node IDs are assigned sequentially as nodes are added during scene encoding.
	/// They are used to reference nodes when adding edges and during execution order traversal.
	pub type NodeId = usize;

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

	#[test]
	fn new_creates_empty_graph() {
	let graph = RenderGraph::new();
	assert_eq!(graph.nodes.len(), 0);
	assert_eq!(graph.edges.len(), 0);
	assert!(!graph.has_filters());
	assert!(graph.root_node.is_none());
	}

	#[test]
	fn clear_resets_to_empty_state() {
	let mut graph = RenderGraph::new();
	graph.add_node(RenderNodeKind::RootLayer {
	layer_id: 0,
	wtile_bbox: dummy_bbox(),
	});
	graph.add_node(RenderNodeKind::FilterLayer {
	layer_id: 1,
	filter: dummy_filter(),
	wtile_bbox: dummy_bbox(),
	transform: Affine::IDENTITY,
	});
	graph.record_node_for_execution(1);

	graph.clear();

	assert_eq!(graph.nodes.len(), 0);
	assert_eq!(graph.edges.len(), 0);
	assert_eq!(graph.next_node_id, 0);
	assert!(graph.root_node.is_none());
	assert!(!graph.has_filters());
	assert_eq!(graph.execution_order().count(), 0);
	}

	#[test]
	fn clear_preserves_capacity() {
	let mut graph = RenderGraph::new();
	let from = graph.add_node(RenderNodeKind::RootLayer {
	layer_id: 0,
	wtile_bbox: dummy_bbox(),
	});
	let to = graph.add_node(RenderNodeKind::RootLayer {
	layer_id: 1,
	wtile_bbox: dummy_bbox(),
	});
	graph.add_edge(from, to, DependencyKind::Sequential { layer_id: 1 });

	let nodes_capacity = graph.nodes.capacity();
	let edges_capacity = graph.edges.capacity();

	graph.clear();

	assert!(graph.nodes.capacity() >= nodes_capacity);
	assert!(graph.edges.capacity() >= edges_capacity);
	}

	#[test]
	fn add_node_returns_sequential_ids() {
	let mut graph = RenderGraph::new();
	let id0 = graph.add_node(RenderNodeKind::RootLayer {
	layer_id: 0,
	wtile_bbox: dummy_bbox(),
	});
	let id1 = graph.add_node(RenderNodeKind::FilterLayer {
	layer_id: 1,
	filter: dummy_filter(),
	wtile_bbox: dummy_bbox(),
	transform: Affine::IDENTITY,
	});

	assert_eq!(id0, 0);
	assert_eq!(id1, 1);
	}

	#[test]
	fn add_node_tracks_root() {
	let mut graph = RenderGraph::new();
	let root_id = graph.add_node(RenderNodeKind::RootLayer {
	layer_id: 0,
	wtile_bbox: dummy_bbox(),
	});

	assert_eq!(graph.root_node, Some(root_id));
	}

	#[test]
	fn add_node_filter_sets_has_filters() {
	let mut graph = RenderGraph::new();

	graph.add_node(RenderNodeKind::FilterLayer {
	layer_id: 1,
	filter: dummy_filter(),
	wtile_bbox: dummy_bbox(),
	transform: Affine::IDENTITY,
	});

	assert!(graph.has_filters());
	}

	#[test]
	fn add_node_root_does_not_set_has_filters() {
	let mut graph = RenderGraph::new();

	graph.add_node(RenderNodeKind::RootLayer {
	layer_id: 0,
	wtile_bbox: dummy_bbox(),
	});

	assert!(!graph.has_filters());
	}

	#[test]
	fn add_edge_creates_dependency() {
	let mut graph = RenderGraph::new();
	let from = graph.add_node(RenderNodeKind::FilterLayer {
	layer_id: 1,
	filter: dummy_filter(),
	wtile_bbox: dummy_bbox(),
	transform: Affine::IDENTITY,
	});
	let to = graph.add_node(RenderNodeKind::RootLayer {
	layer_id: 0,
	wtile_bbox: dummy_bbox(),
	});

	graph.add_edge(from, to, DependencyKind::Sequential { layer_id: 1 });

	assert_eq!(graph.edges.len(), 1);
	assert_eq!(graph.edges[0].from, from);
	assert_eq!(graph.edges[0].to, to);
	}

	#[test]
	fn add_edge_multiple_from_same_node() {
	let mut graph = RenderGraph::new();
	let from = graph.add_node(RenderNodeKind::FilterLayer {
	layer_id: 1,
	filter: dummy_filter(),
	wtile_bbox: dummy_bbox(),
	transform: Affine::IDENTITY,
	});
	let to1 = graph.add_node(RenderNodeKind::FilterLayer {
	layer_id: 2,
	filter: dummy_filter(),
	wtile_bbox: dummy_bbox(),
	transform: Affine::IDENTITY,
	});
	let to2 = graph.add_node(RenderNodeKind::RootLayer {
	layer_id: 0,
	wtile_bbox: dummy_bbox(),
	});

	graph.add_edge(from, to1, DependencyKind::Sequential { layer_id: 1 });
	graph.add_edge(from, to2, DependencyKind::Sequential { layer_id: 1 });

	assert_eq!(graph.edges.len(), 2);
	}

	#[test]
	fn execution_order_includes_recorded_nodes() {
	let mut graph = RenderGraph::new();
	let filter = graph.add_node(RenderNodeKind::FilterLayer {
	layer_id: 1,
	filter: dummy_filter(),
	wtile_bbox: dummy_bbox(),
	transform: Affine::IDENTITY,
	});

	graph.record_node_for_execution(filter);

	let order: Vec<_> = graph.execution_order().collect();
	assert_eq!(order, vec![filter]);
	}

	#[test]
	fn execution_order_includes_only_root_when_present() {
	let mut graph = RenderGraph::new();
	let root = graph.add_node(RenderNodeKind::RootLayer {
	layer_id: 0,
	wtile_bbox: dummy_bbox(),
	});

	let order: Vec<_> = graph.execution_order().collect();
	assert_eq!(order, vec![root]);
	}

	#[test]
	fn execution_order_root_comes_last() {
	let mut graph = RenderGraph::new();
	let filter1 = graph.add_node(RenderNodeKind::FilterLayer {
	layer_id: 1,
	filter: dummy_filter(),
	wtile_bbox: dummy_bbox(),
	transform: Affine::IDENTITY,
	});
	let filter2 = graph.add_node(RenderNodeKind::FilterLayer {
	layer_id: 2,
	filter: dummy_filter(),
	wtile_bbox: dummy_bbox(),
	transform: Affine::IDENTITY,
	});
	let root = graph.add_node(RenderNodeKind::RootLayer {
	layer_id: 0,
	wtile_bbox: dummy_bbox(),
	});

	graph.record_node_for_execution(filter2);
	graph.record_node_for_execution(filter1);

	let order: Vec<_> = graph.execution_order().collect();
	assert_eq!(order, vec![filter2, filter1, root]);
	}

	#[test]
	fn topological_sort_diamond_dependency() {
	let mut graph = RenderGraph::new();
	let bottom = graph.add_node(RenderNodeKind::FilterLayer {
	layer_id: 3,
	filter: dummy_filter(),
	wtile_bbox: dummy_bbox(),
	transform: Affine::IDENTITY,
	});
	let left = graph.add_node(RenderNodeKind::FilterLayer {
	layer_id: 1,
	filter: dummy_filter(),
	wtile_bbox: dummy_bbox(),
	transform: Affine::IDENTITY,
	});
	let right = graph.add_node(RenderNodeKind::FilterLayer {
	layer_id: 2,
	filter: dummy_filter(),
	wtile_bbox: dummy_bbox(),
	transform: Affine::IDENTITY,
	});
	let top = graph.add_node(RenderNodeKind::RootLayer {
	layer_id: 0,
	wtile_bbox: dummy_bbox(),
	});

	// Diamond: bottom -> left -> top, bottom -> right -> top
	graph.add_edge(bottom, left, DependencyKind::Sequential { layer_id: 3 });
	graph.add_edge(bottom, right, DependencyKind::Sequential { layer_id: 3 });
	graph.add_edge(left, top, DependencyKind::Sequential { layer_id: 1 });
	graph.add_edge(right, top, DependencyKind::Sequential { layer_id: 2 });

	let sorted = graph.topological_sort();
	assert_eq!(sorted, vec![bottom, right, left, top]);
	}

	fn dummy_filter() -> Filter {
	Filter::from_primitive(crate::filter_effects::FilterPrimitive::Flood {
	color: AlphaColor::from_rgba8(0, 0, 0, 255),
	})
	}

	fn dummy_bbox() -> WideTilesBbox {
	WideTilesBbox::new([0, 0, 0, 0])
	}
	}