//! Core render graph implementation.
//!
//! The [`RenderGraph`] orchestrates render pass execution by:
//!
//! 1. Building a dependency graph from pass read/write declarations
//! 2. Topologically sorting passes for correct execution order
//! 3. Computing resource lifetimes for memory aliasing
//! 4. Determining optimal load/store operations
//! 5. Culling passes that don't contribute to final output

use super::error::{RenderGraphError, Result};
use super::pass::{
    BufferBuilder, ColorTextureBuilder, DepthTextureBuilder, ExecutePhase, GraphNode, PassBuilder,
    PassExecutionContext, PassNode, ResourcePool, ResourceTemplate, SlotValue, SubGraphInputSlot,
};
use super::resources::{
    RenderGraphBufferDescriptor, RenderGraphResources, RenderGraphTextureDescriptor, ResourceId,
    ResourceType,
};
use petgraph::graph::{DiGraph, NodeIndex};
use std::collections::{BinaryHeap, HashMap, HashSet};
use wgpu::{
    Buffer, BufferUsages, CommandBuffer, Device, StoreOp, Texture, TextureFormat, TextureUsages,
    TextureView,
};

pub struct RenderGraph<C = ()> {
    pub(super) graph: DiGraph<GraphNode<C>, ResourceId>,
    pub(super) pass_nodes: HashMap<String, NodeIndex>,
    pub(super) pass_resource_mappings: HashMap<String, HashMap<String, ResourceId>>,
    pub(super) sub_graphs: HashMap<String, RenderGraph<C>>,
    pub(super) sub_graph_inputs: HashMap<String, Vec<SubGraphInputSlot>>,
    pub(super) resources: RenderGraphResources,
    pub(super) execution_order: Vec<NodeIndex>,
    pub(super) store_ops: HashMap<ResourceId, StoreOp>,
    pub(super) clear_ops: std::collections::HashSet<(petgraph::graph::NodeIndex, ResourceId)>,
    pub(super) aliasing_info: Option<ResourceAliasingInfo>,
    pub(super) needs_recompile: bool,
    pub(super) needs_resource_reallocation: bool,
    pub(super) culled_passes: std::collections::HashSet<NodeIndex>,
    pub(super) resource_versions: HashMap<ResourceId, u64>,
    pub(super) texture_cache: Vec<TextureCacheEntry>,
    pub(super) texture_cache_clock: u64,
}

pub struct TextureCacheEntry {
    pub(super) descriptor: RenderGraphTextureDescriptor,
    pub(super) texture: Texture,
    pub(super) inserted_at: u64,
}

/// Number of `texture_cache_clock` ticks an unused cache entry survives
/// before it gets evicted on the next push. The clock advances once per
/// transient-pool reset, so an entry that has not been popped after
/// roughly this many resize cycles is presumed stale and dropped to
/// keep the cache bounded.
pub(super) const TEXTURE_CACHE_MAX_AGE: u64 = 120;

pub fn render_graph_new<C: 'static>() -> RenderGraph<C> {
    RenderGraph {
        graph: DiGraph::new(),
        pass_nodes: HashMap::new(),
        pass_resource_mappings: HashMap::new(),
        sub_graphs: HashMap::new(),
        sub_graph_inputs: HashMap::new(),
        resources: RenderGraphResources::new(),
        execution_order: Vec::new(),
        store_ops: HashMap::new(),
        clear_ops: std::collections::HashSet::new(),
        aliasing_info: None,
        needs_recompile: true,
        needs_resource_reallocation: false,
        culled_passes: std::collections::HashSet::new(),
        resource_versions: HashMap::new(),
        texture_cache: Vec::new(),
        texture_cache_clock: 0,
    }
}

pub fn render_graph_add_pass<C: 'static>(
    graph: &mut RenderGraph<C>,
    pass: Box<dyn PassNode<C>>,
    slot_mappings: &[(&str, ResourceId)],
) -> Result<NodeIndex> {
    let name = pass.name().to_string();
    let slot_names_reads = pass.reads();
    let slot_names_writes = pass.writes();
    let slot_names_reads_writes = pass.reads_writes();
    let slot_names_optional_reads = pass.optional_reads();

    let mappings: HashMap<String, ResourceId> = slot_mappings
        .iter()
        .map(|(slot, resource_id)| (slot.to_string(), *resource_id))
        .collect();

    let reads: Vec<ResourceId> = slot_names_reads
        .iter()
        .map(|slot| {
            mappings
                .get(*slot)
                .copied()
                .ok_or_else(|| RenderGraphError::SlotNotMapped {
                    pass: name.clone(),
                    slot: slot.to_string(),
                })
        })
        .collect::<Result<Vec<_>>>()?;

    let writes: Vec<ResourceId> = slot_names_writes
        .iter()
        .map(|slot| {
            mappings
                .get(*slot)
                .copied()
                .ok_or_else(|| RenderGraphError::SlotNotMapped {
                    pass: name.clone(),
                    slot: slot.to_string(),
                })
        })
        .collect::<Result<Vec<_>>>()?;

    let reads_writes: Vec<ResourceId> = slot_names_reads_writes
        .iter()
        .map(|slot| {
            mappings
                .get(*slot)
                .copied()
                .ok_or_else(|| RenderGraphError::SlotNotMapped {
                    pass: name.clone(),
                    slot: slot.to_string(),
                })
        })
        .collect::<Result<Vec<_>>>()?;

    let optional_reads: Vec<ResourceId> = slot_names_optional_reads
        .iter()
        .filter_map(|slot| mappings.get(*slot).copied())
        .collect();

    let graph_node = GraphNode {
        name: name.clone(),
        reads,
        writes,
        reads_writes,
        optional_reads,
        pass,
        enabled: true,
    };

    let index = graph.graph.add_node(graph_node);
    graph.pass_nodes.insert(name.clone(), index);
    graph.pass_resource_mappings.insert(name, mappings);
    graph.needs_recompile = true;
    Ok(index)
}

pub fn render_graph_add_sub_graph<C: 'static>(
    graph: &mut RenderGraph<C>,
    name: String,
    sub_graph: RenderGraph<C>,
    input_slots: Vec<SubGraphInputSlot>,
) {
    graph.sub_graphs.insert(name.clone(), sub_graph);
    graph.sub_graph_inputs.insert(name, input_slots);
}

pub fn render_graph_get_sub_graph<'a, C: 'static>(
    graph: &'a RenderGraph<C>,
    name: &str,
) -> Option<&'a RenderGraph<C>> {
    graph.sub_graphs.get(name)
}

pub fn render_graph_get_sub_graph_mut<'a, C: 'static>(
    graph: &'a mut RenderGraph<C>,
    name: &str,
) -> Option<&'a mut RenderGraph<C>> {
    graph.sub_graphs.get_mut(name)
}

pub fn render_graph_get_pass_mut<'a, C: 'static>(
    graph: &'a mut RenderGraph<C>,
    name: &str,
) -> Option<&'a mut (dyn PassNode<C> + 'static)> {
    let node_index = graph.pass_nodes.get(name)?;
    graph
        .graph
        .node_weight_mut(*node_index)
        .map(move |node| node.pass.as_mut())
}

pub fn render_graph_set_pass_enabled<C: 'static>(
    graph: &mut RenderGraph<C>,
    name: &str,
    enabled: bool,
) -> Result<()> {
    let node_index = *graph
        .pass_nodes
        .get(name)
        .ok_or_else(|| RenderGraphError::PassNotFound {
            pass: name.to_string(),
        })?;

    if let Some(node) = graph.graph.node_weight_mut(node_index) {
        node.enabled = enabled;
    }

    Ok(())
}

pub fn render_graph_add_dependency<C: 'static>(
    graph: &mut RenderGraph<C>,
    before: &str,
    after: &str,
) -> Result<()> {
    let before_index =
        *graph
            .pass_nodes
            .get(before)
            .ok_or_else(|| RenderGraphError::PassNotFound {
                pass: before.to_string(),
            })?;
    let after_index =
        *graph
            .pass_nodes
            .get(after)
            .ok_or_else(|| RenderGraphError::PassNotFound {
                pass: after.to_string(),
            })?;
    if before_index == after_index {
        return Ok(());
    }
    if !graph.graph.contains_edge(before_index, after_index) {
        graph
            .graph
            .add_edge(before_index, after_index, ResourceId::EXPLICIT_DEPENDENCY);
    }
    Ok(())
}

pub fn render_graph_save_pass_enabled_states<C: 'static>(
    graph: &RenderGraph<C>,
) -> HashMap<String, bool> {
    graph
        .pass_nodes
        .iter()
        .filter_map(|(name, node_index)| {
            graph
                .graph
                .node_weight(*node_index)
                .map(|node| (name.clone(), node.enabled))
        })
        .collect()
}

pub fn render_graph_restore_pass_enabled_states<C: 'static>(
    graph: &mut RenderGraph<C>,
    states: &HashMap<String, bool>,
) {
    for (name, enabled) in states {
        let _ = render_graph_set_pass_enabled(graph, name, *enabled);
    }
}

pub fn render_graph_add_color_texture<'a, C: 'static>(
    graph: &'a mut RenderGraph<C>,
    name: &str,
) -> ColorTextureBuilder<'a, C> {
    ColorTextureBuilder {
        graph,
        name: name.to_string(),
        descriptor: RenderGraphTextureDescriptor {
            format: TextureFormat::Rgba8UnormSrgb,
            width: 1,
            height: 1,
            usage: TextureUsages::RENDER_ATTACHMENT | TextureUsages::TEXTURE_BINDING,
            sample_count: 1,
            mip_level_count: 1,
            dimension: wgpu::TextureDimension::D2,
            depth_or_array_layers: 1,
        },
        clear_color: None,
        force_store: false,
        fixed_size: false,
    }
}

pub fn render_graph_add_depth_texture<'a, C: 'static>(
    graph: &'a mut RenderGraph<C>,
    name: &str,
) -> DepthTextureBuilder<'a, C> {
    DepthTextureBuilder {
        graph,
        name: name.to_string(),
        descriptor: RenderGraphTextureDescriptor {
            format: TextureFormat::Depth32Float,
            width: 1,
            height: 1,
            usage: TextureUsages::RENDER_ATTACHMENT | TextureUsages::TEXTURE_BINDING,
            sample_count: 1,
            mip_level_count: 1,
            dimension: wgpu::TextureDimension::D2,
            depth_or_array_layers: 1,
        },
        clear_depth: None,
        force_store: false,
        fixed_size: false,
    }
}

pub fn render_graph_add_buffer<'a, C: 'static>(
    graph: &'a mut RenderGraph<C>,
    name: &str,
) -> BufferBuilder<'a, C> {
    BufferBuilder {
        graph,
        name: name.to_string(),
        descriptor: RenderGraphBufferDescriptor {
            size: 256,
            usage: BufferUsages::STORAGE | BufferUsages::COPY_DST,
            mapped_at_creation: false,
        },
    }
}

pub fn render_graph_transient_color_from_template<C: 'static>(
    graph: &mut RenderGraph<C>,
    name: &str,
    template: &ResourceTemplate,
) -> ResourceId {
    graph.resources.register_transient_resource(
        name.to_string(),
        ResourceType::TransientColor {
            descriptor: RenderGraphTextureDescriptor {
                format: template.format,
                width: template.width,
                height: template.height,
                usage: template.usage,
                sample_count: template.sample_count,
                mip_level_count: template.mip_level_count,
                dimension: template.dimension,
                depth_or_array_layers: template.depth_or_array_layers,
            },
            clear_color: None,
            force_store: false,
        },
    )
}

pub fn render_graph_transient_color_from_template_with_clear<C: 'static>(
    graph: &mut RenderGraph<C>,
    name: &str,
    template: &ResourceTemplate,
    clear_color: wgpu::Color,
) -> ResourceId {
    graph.resources.register_transient_resource(
        name.to_string(),
        ResourceType::TransientColor {
            descriptor: RenderGraphTextureDescriptor {
                format: template.format,
                width: template.width,
                height: template.height,
                usage: template.usage,
                sample_count: template.sample_count,
                mip_level_count: template.mip_level_count,
                dimension: template.dimension,
                depth_or_array_layers: template.depth_or_array_layers,
            },
            clear_color: Some(clear_color),
            force_store: false,
        },
    )
}

pub fn render_graph_external_color<C: 'static>(
    graph: &mut RenderGraph<C>,
    name: &str,
) -> ResourceId {
    graph.resources.register_external_resource(
        name.to_string(),
        ResourceType::ExternalColor {
            clear_color: None,
            force_store: true,
        },
    )
}

pub fn render_graph_add_pass_with_slots<C: 'static>(
    graph: &mut RenderGraph<C>,
    pass: Box<dyn PassNode<C>>,
    slots: Vec<(&str, ResourceId)>,
) -> Result<NodeIndex> {
    render_graph_add_pass(graph, pass, &slots)
}

pub fn render_graph_pass<'a, C: 'static>(
    graph: &'a mut RenderGraph<C>,
    pass: Box<dyn PassNode<C>>,
) -> PassBuilder<'a, C> {
    PassBuilder {
        graph,
        pass: Some(pass),
        slots: Vec::new(),
    }
}

pub fn render_graph_resource_pool<'a, C: 'static>(
    graph: &'a mut RenderGraph<C>,
    template: &ResourceTemplate,
) -> ResourcePool<'a, C> {
    ResourcePool {
        graph,
        template: template.clone(),
    }
}

pub fn render_graph_set_external_texture<C: 'static>(
    graph: &mut RenderGraph<C>,
    id: ResourceId,
    texture: Option<Texture>,
    view: TextureView,
    width: u32,
    height: u32,
) {
    graph
        .resources
        .set_external_texture(id, texture, view, width, height);
}

pub fn render_graph_set_external_buffer<C: 'static>(
    graph: &mut RenderGraph<C>,
    id: ResourceId,
    buffer: Buffer,
) {
    graph.resources.set_external_buffer(id, buffer);
}

pub fn render_graph_get_texture<C: 'static>(
    graph: &RenderGraph<C>,
    id: ResourceId,
) -> Option<&Texture> {
    let aliasing_info = graph.aliasing_info.as_ref()?;
    let pool_index = aliasing_info.aliases.get(&id)?;
    let pool_slot = aliasing_info.pools.get(*pool_index)?;
    match &pool_slot.resource {
        Some(PooledResource::Texture { texture }) => Some(texture),
        _ => None,
    }
}

pub fn render_graph_get_texture_view<C: 'static>(
    graph: &RenderGraph<C>,
    id: ResourceId,
) -> Option<&TextureView> {
    graph.resources.get_texture_view(id)
}

fn render_graph_build_dependency_edges<C: 'static>(graph: &mut RenderGraph<C>) {
    let mut resource_writers: HashMap<ResourceId, NodeIndex> = HashMap::new();

    let node_indices: Vec<NodeIndex> = graph.graph.node_indices().collect();
    let mut edges_to_add: Vec<(NodeIndex, NodeIndex, ResourceId)> = Vec::new();

    for &node_index in &node_indices {
        let node = &graph.graph[node_index];
        let reads = node.reads.clone();
        let writes = node.writes.clone();
        let reads_writes = node.reads_writes.clone();
        let optional_reads = node.optional_reads.clone();

        for &read_resource in &reads {
            if let Some(&writer_index) = resource_writers.get(&read_resource)
                && !graph.graph.contains_edge(writer_index, node_index)
            {
                edges_to_add.push((writer_index, node_index, read_resource));
            }
        }

        for &read_resource in &optional_reads {
            if let Some(&writer_index) = resource_writers.get(&read_resource)
                && !graph.graph.contains_edge(writer_index, node_index)
            {
                edges_to_add.push((writer_index, node_index, read_resource));
            }
        }

        for &rw_resource in &reads_writes {
            if let Some(&writer_index) = resource_writers.get(&rw_resource)
                && !graph.graph.contains_edge(writer_index, node_index)
            {
                edges_to_add.push((writer_index, node_index, rw_resource));
            }
        }

        for &write_resource in &writes {
            resource_writers.insert(write_resource, node_index);
        }

        for &rw_resource in &reads_writes {
            resource_writers.insert(rw_resource, node_index);
        }
    }

    for (from, to, resource) in edges_to_add {
        graph.graph.add_edge(from, to, resource);
    }
}

fn render_graph_compute_resource_lifetimes<C: 'static>(
    graph: &RenderGraph<C>,
    execution_order: &[NodeIndex],
) -> Vec<ResourceLifetime> {
    let mut lifetimes: HashMap<ResourceId, ResourceLifetime> = HashMap::new();

    for (pass_index, &node_index) in execution_order.iter().enumerate() {
        let node = &graph.graph[node_index];

        for &resource_id in &node.writes {
            lifetimes.entry(resource_id).or_insert(ResourceLifetime {
                resource_id,
                first_use: pass_index,
                last_use: pass_index,
            });
        }

        for &resource_id in &node.reads {
            let lifetime = lifetimes.entry(resource_id).or_insert(ResourceLifetime {
                resource_id,
                first_use: pass_index,
                last_use: pass_index,
            });
            lifetime.last_use = pass_index;
        }

        for &resource_id in &node.reads_writes {
            let lifetime = lifetimes.entry(resource_id).or_insert(ResourceLifetime {
                resource_id,
                first_use: pass_index,
                last_use: pass_index,
            });
            lifetime.last_use = pass_index;
        }

        for &resource_id in &node.optional_reads {
            let lifetime = lifetimes.entry(resource_id).or_insert(ResourceLifetime {
                resource_id,
                first_use: pass_index,
                last_use: pass_index,
            });
            lifetime.last_use = pass_index;
        }
    }

    lifetimes
        .into_iter()
        .filter(|(id, _)| {
            if let Some(desc) = graph.resources.get_descriptor(*id) {
                !desc.is_external
            } else {
                false
            }
        })
        .map(|(_, lifetime)| lifetime)
        .collect()
}

fn can_alias_textures(
    desc1: &RenderGraphTextureDescriptor,
    desc2: &RenderGraphTextureDescriptor,
) -> bool {
    desc1.format == desc2.format
        && desc1.width == desc2.width
        && desc1.height == desc2.height
        && desc1.sample_count == desc2.sample_count
        && desc1.mip_level_count == desc2.mip_level_count
        && desc1.usage.contains(desc2.usage)
}

fn can_alias_buffers(
    desc1: &RenderGraphBufferDescriptor,
    desc2: &RenderGraphBufferDescriptor,
) -> bool {
    desc1.size >= desc2.size && desc1.usage == desc2.usage
}

fn render_graph_compute_resource_aliasing<C: 'static>(
    graph: &RenderGraph<C>,
    mut lifetimes: Vec<ResourceLifetime>,
) -> ResourceAliasingInfo {
    lifetimes.sort_by_key(|lt| lt.first_use);

    let mut aliasing_info = ResourceAliasingInfo {
        aliases: HashMap::new(),
        pools: Vec::new(),
    };

    let mut available_pools: BinaryHeap<PoolHeapEntry> = BinaryHeap::new();

    for lifetime in lifetimes {
        let descriptor = graph
            .resources
            .get_descriptor(lifetime.resource_id)
            .unwrap();

        let force_store = match &descriptor.resource_type {
            ResourceType::TransientColor { force_store, .. }
            | ResourceType::TransientDepth { force_store, .. } => *force_store,
            _ => false,
        };

        let mut reused_candidates = Vec::new();
        while let Some(entry) = available_pools.peek() {
            if entry.lifetime_end < lifetime.first_use {
                reused_candidates.push(available_pools.pop().unwrap());
            } else {
                break;
            }
        }

        let mut assigned_slot = None;
        if force_store {
            for candidate in reused_candidates {
                available_pools.push(candidate);
            }
            let slot_index = aliasing_info.pools.len();
            let descriptor_info = match &descriptor.resource_type {
                ResourceType::TransientColor {
                    descriptor: tex_desc,
                    ..
                }
                | ResourceType::TransientDepth {
                    descriptor: tex_desc,
                    ..
                } => PoolDescriptorInfo::Texture(tex_desc.clone()),
                ResourceType::TransientBuffer {
                    descriptor: buf_desc,
                } => PoolDescriptorInfo::Buffer(buf_desc.clone()),
                _ => continue,
            };
            aliasing_info.pools.push(PoolSlot {
                resource: None,
                descriptor_info: Some(descriptor_info),
                lifetime_end: lifetime.last_use,
            });
            aliasing_info
                .aliases
                .insert(lifetime.resource_id, slot_index);
            continue;
        }

        for candidate in reused_candidates.iter_mut() {
            let can_reuse = match (&candidate.descriptor_info, &descriptor.resource_type) {
                (
                    PoolDescriptorInfo::Texture(pool_desc),
                    ResourceType::TransientColor {
                        descriptor: res_desc,
                        ..
                    }
                    | ResourceType::TransientDepth {
                        descriptor: res_desc,
                        ..
                    },
                ) => can_alias_textures(pool_desc, res_desc),
                (
                    PoolDescriptorInfo::Buffer(pool_desc),
                    ResourceType::TransientBuffer {
                        descriptor: res_desc,
                    },
                ) => can_alias_buffers(pool_desc, res_desc),
                _ => false,
            };

            if can_reuse {
                let needs_new_resource =
                    match (&mut candidate.descriptor_info, &descriptor.resource_type) {
                        (
                            PoolDescriptorInfo::Texture(pool_desc),
                            ResourceType::TransientColor {
                                descriptor: res_desc,
                                ..
                            }
                            | ResourceType::TransientDepth {
                                descriptor: res_desc,
                                ..
                            },
                        ) if !pool_desc.usage.contains(res_desc.usage) => {
                            pool_desc.usage |= res_desc.usage;
                            true
                        }
                        (
                            PoolDescriptorInfo::Buffer(pool_desc),
                            ResourceType::TransientBuffer {
                                descriptor: res_desc,
                            },
                        ) if res_desc.size > pool_desc.size => {
                            *pool_desc = res_desc.clone();
                            true
                        }
                        _ => false,
                    };

                let pool_slot = &mut aliasing_info.pools[candidate.pool_index];
                pool_slot.lifetime_end = lifetime.last_use;
                pool_slot.descriptor_info = Some(candidate.descriptor_info.clone());

                if needs_new_resource {
                    pool_slot.resource = None;
                }

                candidate.lifetime_end = lifetime.last_use;
                assigned_slot = Some(candidate.pool_index);
                break;
            }
        }

        for candidate in reused_candidates {
            available_pools.push(candidate);
        }

        if assigned_slot.is_none() {
            let slot_index = aliasing_info.pools.len();

            let descriptor_info = match &descriptor.resource_type {
                ResourceType::TransientColor {
                    descriptor: tex_desc,
                    ..
                }
                | ResourceType::TransientDepth {
                    descriptor: tex_desc,
                    ..
                } => PoolDescriptorInfo::Texture(tex_desc.clone()),
                ResourceType::TransientBuffer {
                    descriptor: buf_desc,
                } => PoolDescriptorInfo::Buffer(buf_desc.clone()),
                _ => continue,
            };

            aliasing_info.pools.push(PoolSlot {
                resource: None,
                descriptor_info: Some(descriptor_info.clone()),
                lifetime_end: lifetime.last_use,
            });

            available_pools.push(PoolHeapEntry {
                pool_index: slot_index,
                lifetime_end: lifetime.last_use,
                descriptor_info,
            });

            assigned_slot = Some(slot_index);
        }

        aliasing_info
            .aliases
            .insert(lifetime.resource_id, assigned_slot.unwrap());
    }

    aliasing_info
}

fn render_graph_compute_store_ops<C: 'static>(
    graph: &RenderGraph<C>,
    execution_order: &[NodeIndex],
) -> HashMap<ResourceId, StoreOp> {
    let mut last_read: HashMap<ResourceId, usize> = HashMap::new();

    for (index, &node_index) in execution_order.iter().enumerate().rev() {
        let node = &graph.graph[node_index];

        for &resource_id in node
            .reads
            .iter()
            .chain(&node.reads_writes)
            .chain(&node.optional_reads)
        {
            last_read.entry(resource_id).or_insert(index);
        }
    }

    let mut store_ops = HashMap::new();

    for (index, &node_index) in execution_order.iter().enumerate() {
        let node = &graph.graph[node_index];

        for &resource_id in node.writes.iter().chain(&node.reads_writes) {
            let descriptor = graph.resources.get_descriptor(resource_id).unwrap();

            let force_store = match &descriptor.resource_type {
                ResourceType::ExternalColor { force_store, .. }
                | ResourceType::ExternalDepth { force_store, .. }
                | ResourceType::TransientColor { force_store, .. }
                | ResourceType::TransientDepth { force_store, .. } => *force_store,
                _ => false,
            };
            let has_later_read = last_read
                .get(&resource_id)
                .is_some_and(|&last| last > index);

            let store_op = if descriptor.is_external {
                match &descriptor.resource_type {
                    ResourceType::ExternalColor { .. } | ResourceType::ExternalDepth { .. } => {
                        if force_store || has_later_read {
                            StoreOp::Store
                        } else {
                            StoreOp::Discard
                        }
                    }
                    ResourceType::ExternalBuffer => StoreOp::Store,
                    _ => StoreOp::Store,
                }
            } else if force_store || has_later_read {
                StoreOp::Store
            } else {
                StoreOp::Discard
            };

            store_ops.entry(resource_id).or_insert(store_op);
        }
    }

    for &resource_id in graph.resources.descriptors.keys() {
        store_ops.entry(resource_id).or_insert_with(|| {
            let descriptor = graph.resources.get_descriptor(resource_id).unwrap();
            let force_store = match &descriptor.resource_type {
                ResourceType::ExternalColor { force_store, .. }
                | ResourceType::ExternalDepth { force_store, .. }
                | ResourceType::TransientColor { force_store, .. }
                | ResourceType::TransientDepth { force_store, .. } => *force_store,
                _ => false,
            };
            if descriptor.is_external {
                match &descriptor.resource_type {
                    ResourceType::ExternalColor { .. } | ResourceType::ExternalDepth { .. } => {
                        if force_store {
                            StoreOp::Store
                        } else {
                            StoreOp::Discard
                        }
                    }
                    _ => StoreOp::Store,
                }
            } else if force_store {
                StoreOp::Store
            } else {
                StoreOp::Discard
            }
        });
    }

    store_ops
}

fn render_graph_compute_clear_ops<C: 'static>(
    graph: &RenderGraph<C>,
    execution_order: &[NodeIndex],
) -> std::collections::HashSet<(NodeIndex, ResourceId)> {
    let mut clear_ops = std::collections::HashSet::new();
    let mut first_write: HashMap<ResourceId, NodeIndex> = HashMap::new();

    for &node_index in execution_order {
        let node = &graph.graph[node_index];

        for &resource_id in &node.writes {
            first_write.entry(resource_id).or_insert(node_index);
        }
        for &resource_id in &node.reads_writes {
            first_write.entry(resource_id).or_insert(node_index);
        }
    }

    for (&resource_id, &node_index) in &first_write {
        if let Some(descriptor) = graph.resources.get_descriptor(resource_id) {
            let has_clear = match &descriptor.resource_type {
                ResourceType::ExternalColor { clear_color, .. }
                | ResourceType::TransientColor { clear_color, .. } => clear_color.is_some(),
                ResourceType::ExternalDepth { clear_depth, .. }
                | ResourceType::TransientDepth { clear_depth, .. } => clear_depth.is_some(),
                _ => false,
            };

            if has_clear {
                clear_ops.insert((node_index, resource_id));
            }
        }
    }

    clear_ops
}

fn render_graph_compute_dead_passes<C: 'static>(
    graph: &RenderGraph<C>,
    execution_order: &[NodeIndex],
) -> HashSet<NodeIndex> {
    let mut required_resources: HashSet<ResourceId> = HashSet::new();
    let mut required_passes: HashSet<NodeIndex> = HashSet::new();

    for &resource_id in graph.resources.descriptors.keys() {
        let descriptor = graph.resources.get_descriptor(resource_id).unwrap();
        if descriptor.is_external {
            required_resources.insert(resource_id);
        }
    }

    for &node_index in execution_order.iter().rev() {
        let node = &graph.graph[node_index];

        let has_side_effects = node.writes.is_empty() && node.reads_writes.is_empty();

        let writes_required_resource = node.writes.iter().any(|r| required_resources.contains(r))
            || node
                .reads_writes
                .iter()
                .any(|r| required_resources.contains(r));

        if writes_required_resource || has_side_effects {
            required_passes.insert(node_index);
            required_resources.extend(&node.reads);
            required_resources.extend(&node.reads_writes);
            required_resources.extend(&node.optional_reads);
        }
    }

    let all_passes: HashSet<NodeIndex> = execution_order.iter().copied().collect();
    all_passes.difference(&required_passes).copied().collect()
}

pub fn render_graph_compile<C: 'static>(graph: &mut RenderGraph<C>) -> Result<()> {
    render_graph_build_dependency_edges(graph);

    graph.execution_order = petgraph::algo::toposort(&graph.graph, None).map_err(|cycle| {
        let pass = graph
            .graph
            .node_weight(cycle.node_id())
            .map(|node| node.name.clone())
            .unwrap_or_else(|| "<unknown>".to_string());
        RenderGraphError::CyclicDependency { pass }
    })?;

    graph.store_ops = render_graph_compute_store_ops(graph, &graph.execution_order.clone());
    graph.clear_ops = render_graph_compute_clear_ops(graph, &graph.execution_order.clone());

    let lifetimes = render_graph_compute_resource_lifetimes(graph, &graph.execution_order.clone());
    graph.aliasing_info = Some(render_graph_compute_resource_aliasing(graph, lifetimes));

    graph.culled_passes = render_graph_compute_dead_passes(graph, &graph.execution_order.clone());

    graph.needs_recompile = false;
    Ok(())
}

fn render_graph_recompile_if_needed<C: 'static>(graph: &mut RenderGraph<C>) -> Result<()> {
    if graph.needs_resource_reallocation {
        let lifetimes =
            render_graph_compute_resource_lifetimes(graph, &graph.execution_order.clone());
        graph.aliasing_info = Some(render_graph_compute_resource_aliasing(graph, lifetimes));
        graph.needs_resource_reallocation = false;
        return Ok(());
    }

    if !graph.needs_recompile {
        return Ok(());
    }

    let edge_indices: Vec<_> = graph.graph.edge_indices().collect();
    for edge_index in edge_indices {
        graph.graph.remove_edge(edge_index);
    }

    render_graph_build_dependency_edges(graph);

    graph.execution_order = petgraph::algo::toposort(&graph.graph, None).map_err(|cycle| {
        let pass = graph
            .graph
            .node_weight(cycle.node_id())
            .map(|node| node.name.clone())
            .unwrap_or_else(|| "<unknown>".to_string());
        RenderGraphError::CyclicDependency { pass }
    })?;

    graph.store_ops = render_graph_compute_store_ops(graph, &graph.execution_order.clone());
    graph.clear_ops = render_graph_compute_clear_ops(graph, &graph.execution_order.clone());

    let lifetimes = render_graph_compute_resource_lifetimes(graph, &graph.execution_order.clone());
    graph.aliasing_info = Some(render_graph_compute_resource_aliasing(graph, lifetimes));

    graph.culled_passes = render_graph_compute_dead_passes(graph, &graph.execution_order.clone());

    graph.needs_recompile = false;
    Ok(())
}

pub fn render_graph_execute<C: 'static>(
    graph: &mut RenderGraph<C>,
    device: &Device,
    queue: &wgpu::Queue,
    configs: &C,
) -> Result<Vec<CommandBuffer>> {
    render_graph_execute_with_phase(graph, device, queue, configs, ExecutePhase::Full)
}

pub fn render_graph_execute_with_phase<C: 'static>(
    graph: &mut RenderGraph<C>,
    device: &Device,
    queue: &wgpu::Queue,
    configs: &C,
    phase: ExecutePhase,
) -> Result<Vec<CommandBuffer>> {
    {
        let _span = tracing::info_span!("graph_recompile_if_needed").entered();
        render_graph_recompile_if_needed(graph)?;
    }

    if graph.aliasing_info.is_none() {
        let _span = tracing::info_span!("graph_compute_aliasing").entered();
        let lifetimes =
            render_graph_compute_resource_lifetimes(graph, &graph.execution_order.clone());
        graph.aliasing_info = Some(render_graph_compute_resource_aliasing(graph, lifetimes));
    }

    {
        let _span = tracing::info_span!("graph_allocate_transient").entered();
        if let Some(aliasing_info) = &mut graph.aliasing_info {
            let mut texture_cache = std::mem::take(&mut graph.texture_cache);
            graph.resources.allocate_transient_resources_with_aliasing(
                device,
                &graph.store_ops,
                aliasing_info,
                &mut texture_cache,
            );
            graph.texture_cache = texture_cache;
        }
    }

    {
        let _span = tracing::info_span!("graph_invalidate_bind_groups").entered();
        render_graph_invalidate_bind_groups_for_changed_resources(graph);
    }

    {
        let _span = tracing::info_span!("graph_prepare").entered();
        for &node_index in &graph.execution_order {
            if graph.culled_passes.contains(&node_index) {
                continue;
            }

            let node = &mut graph.graph[node_index];
            if !node.enabled {
                continue;
            }
            match phase {
                ExecutePhase::Full => {
                    if !node.pass.runs_in_full_phase() {
                        continue;
                    }
                }
                ExecutePhase::ComposeOnly => {
                    if !node.pass.runs_in_compose_only_phase() {
                        continue;
                    }
                }
            }
            let pass_name = node.name.clone();
            let _pass_span = tracing::info_span!("pass_prepare", name = %pass_name).entered();
            node.pass.prepare(device, queue, configs);
        }
    }

    let _span = tracing::info_span!("graph_execute").entered();
    render_graph_execute_serial(graph, device, queue, configs, phase)
}

fn render_graph_invalidate_bind_groups_for_changed_resources<C: 'static>(
    graph: &mut RenderGraph<C>,
) {
    let mut dirty_resources = HashSet::new();

    for &resource_id in graph.resources.descriptors.keys() {
        let current_version = graph.resources.get_version(resource_id);
        let stored_version = graph
            .resource_versions
            .get(&resource_id)
            .copied()
            .unwrap_or(0);

        if current_version != stored_version {
            dirty_resources.insert(resource_id);
            graph.resource_versions.insert(resource_id, current_version);
        }
    }

    if dirty_resources.is_empty() {
        return;
    }

    let mut passes_to_invalidate = HashSet::new();

    for &node_index in &graph.execution_order {
        let node = &graph.graph[node_index];

        for &resource_id in node
            .reads
            .iter()
            .chain(&node.writes)
            .chain(&node.reads_writes)
            .chain(&node.optional_reads)
        {
            if dirty_resources.contains(&resource_id) {
                passes_to_invalidate.insert(node_index);
                break;
            }
        }
    }

    for &node_index in &passes_to_invalidate {
        let node = &mut graph.graph[node_index];
        node.pass.invalidate_bind_groups();
    }
}

fn render_graph_execute_serial<C: 'static>(
    graph: &mut RenderGraph<C>,
    device: &Device,
    queue: &wgpu::Queue,
    configs: &C,
    phase: ExecutePhase,
) -> Result<Vec<CommandBuffer>> {
    let mut command_buffers = Vec::new();

    let execution_order = graph.execution_order.clone();
    for node_index in execution_order {
        if graph.culled_passes.contains(&node_index) {
            continue;
        }

        let is_enabled = graph.graph[node_index].enabled;
        match phase {
            ExecutePhase::Full => {
                if !graph.graph[node_index].pass.runs_in_full_phase() {
                    continue;
                }
            }
            ExecutePhase::ComposeOnly => {
                if !graph.graph[node_index].pass.runs_in_compose_only_phase() {
                    continue;
                }
            }
        }
        let pass_name = graph.graph[node_index].name.clone();
        let _pass_span = tracing::info_span!("pass_execute", name = %pass_name).entered();
        let encoder_label = format!("RenderGraph Pass: {}", pass_name);
        let mut encoder = device.create_command_encoder(&wgpu::CommandEncoderDescriptor {
            label: Some(&encoder_label),
        });
        let node = &mut graph.graph[node_index];

        let slot_mappings = graph
            .pass_resource_mappings
            .get(&node.name)
            .ok_or_else(|| RenderGraphError::ResourceNotFound {
                resource: format!("pass_{}_mappings", node.name),
                id: ResourceId(0),
            })?;

        let sub_graph_commands = {
            let context = PassExecutionContext {
                encoder: &mut encoder,
                resources: &graph.resources,
                device,
                queue,
                slot_mappings,
                configs,
                sub_graph_commands: Vec::new(),
                node_index,
                clear_ops: &graph.clear_ops,
                pass_enabled: is_enabled,
            };

            node.pass.execute(context)?
        };

        for command in sub_graph_commands {
            command_buffers.push(encoder.finish());

            let sub_graph = graph
                .sub_graphs
                .get_mut(&command.sub_graph_name)
                .ok_or_else(|| RenderGraphError::SubGraphNotFound {
                    sub_graph: command.sub_graph_name.clone(),
                })?;

            let input_slots = graph
                .sub_graph_inputs
                .get(&command.sub_graph_name)
                .cloned()
                .unwrap_or_default();

            for (index, slot_value) in command.inputs.iter().enumerate() {
                if let Some(input_slot) = input_slots.get(index) {
                    match slot_value {
                        SlotValue::TextureView {
                            texture,
                            view,
                            width,
                            height,
                        } => {
                            if let Some(resource_id) = sub_graph
                                .resources
                                .descriptors
                                .iter()
                                .find(|(_, desc)| desc.name == input_slot.name && desc.is_external)
                                .map(|(id, _)| *id)
                            {
                                let descriptor = sub_graph
                                    .resources
                                    .get_descriptor(resource_id)
                                    .ok_or_else(|| RenderGraphError::DescriptorNotFound {
                                        resource: input_slot.name.clone(),
                                        id: resource_id,
                                    })?;
                                match &descriptor.resource_type {
                                    ResourceType::ExternalColor { .. }
                                    | ResourceType::ExternalDepth { .. } => {
                                        sub_graph.resources.set_external_texture(
                                            resource_id,
                                            texture.cloned(),
                                            (*view).clone(),
                                            *width,
                                            *height,
                                        );
                                    }
                                    _ => {
                                        return Err(RenderGraphError::SubGraphInputTypeMismatch {
                                            input: input_slot.name.clone(),
                                            expected: "buffer".to_string(),
                                            received: "texture".to_string(),
                                        });
                                    }
                                }
                            }
                        }
                        SlotValue::Buffer(buffer) => {
                            if let Some(resource_id) = sub_graph
                                .resources
                                .descriptors
                                .iter()
                                .find(|(_, desc)| desc.name == input_slot.name && desc.is_external)
                                .map(|(id, _)| *id)
                            {
                                let descriptor = sub_graph
                                    .resources
                                    .get_descriptor(resource_id)
                                    .ok_or_else(|| RenderGraphError::DescriptorNotFound {
                                        resource: input_slot.name.clone(),
                                        id: resource_id,
                                    })?;
                                match &descriptor.resource_type {
                                    ResourceType::ExternalBuffer => {
                                        sub_graph
                                            .resources
                                            .set_external_buffer(resource_id, (*buffer).clone());
                                    }
                                    _ => {
                                        return Err(RenderGraphError::SubGraphInputTypeMismatch {
                                            input: input_slot.name.clone(),
                                            expected: "texture".to_string(),
                                            received: "buffer".to_string(),
                                        });
                                    }
                                }
                            }
                        }
                    }
                }
            }

            let sub_graph_buffers = render_graph_execute(sub_graph, device, queue, configs)?;
            command_buffers.extend(sub_graph_buffers);

            encoder = device.create_command_encoder(&wgpu::CommandEncoderDescriptor {
                label: Some(&encoder_label),
            });
        }

        command_buffers.push(encoder.finish());
    }

    Ok(command_buffers)
}

pub fn render_graph_resources_mut<C: 'static>(
    graph: &mut RenderGraph<C>,
) -> &mut RenderGraphResources {
    &mut graph.resources
}

pub fn render_graph_resize_transient_resource<C: 'static>(
    graph: &mut RenderGraph<C>,
    _device: &Device,
    id: ResourceId,
    width: u32,
    height: u32,
) -> Result<()> {
    let already_matches = graph
        .resources
        .descriptors
        .get(&id)
        .and_then(|descriptor| match &descriptor.resource_type {
            ResourceType::TransientColor {
                descriptor: tex_desc,
                ..
            }
            | ResourceType::TransientDepth {
                descriptor: tex_desc,
                ..
            } => Some(tex_desc.width == width && tex_desc.height == height),
            _ => None,
        })
        .unwrap_or(false);
    if already_matches {
        return Ok(());
    }

    graph
        .resources
        .update_transient_descriptor(id, width, height)?;

    drain_aliasing_pool_into_cache(graph);

    graph.aliasing_info = None;
    graph.resources.handles.retain(|id, _| {
        if let Some(descriptor) = graph.resources.descriptors.get(id) {
            descriptor.is_external
        } else {
            false
        }
    });
    graph.needs_resource_reallocation = true;
    Ok(())
}

fn drain_aliasing_pool_into_cache<C: 'static>(graph: &mut RenderGraph<C>) {
    graph.texture_cache_clock = graph.texture_cache_clock.wrapping_add(1);
    let now = graph.texture_cache_clock;

    if let Some(aliasing_info) = &mut graph.aliasing_info {
        for pool_slot in &mut aliasing_info.pools {
            if let Some(PooledResource::Texture { texture }) = pool_slot.resource.take()
                && let Some(PoolDescriptorInfo::Texture(desc)) = &pool_slot.descriptor_info
            {
                graph.texture_cache.push(TextureCacheEntry {
                    descriptor: desc.clone(),
                    texture,
                    inserted_at: now,
                });
            }
        }
    }

    graph
        .texture_cache
        .retain(|entry| now.saturating_sub(entry.inserted_at) <= TEXTURE_CACHE_MAX_AGE);
}

pub fn render_graph_resize_all_transient_proportional<C: 'static>(
    graph: &mut RenderGraph<C>,
    old_width: u32,
    old_height: u32,
    new_width: u32,
    new_height: u32,
) -> Result<()> {
    if old_width == 0 || old_height == 0 {
        return Ok(());
    }

    let resizes: Vec<(ResourceId, u32, u32)> = graph
        .resources
        .descriptors
        .iter()
        .filter_map(|(&id, descriptor)| {
            if descriptor.is_external || descriptor.fixed_size {
                return None;
            }
            let (current_width, current_height) = match &descriptor.resource_type {
                ResourceType::TransientColor {
                    descriptor: tex_desc,
                    ..
                }
                | ResourceType::TransientDepth {
                    descriptor: tex_desc,
                    ..
                } => (tex_desc.width, tex_desc.height),
                _ => return None,
            };

            let ratio_x = current_width as f64 / old_width as f64;
            let ratio_y = current_height as f64 / old_height as f64;

            if (ratio_x - ratio_y).abs() > 0.01 {
                return None;
            }

            let target_width = (new_width as f64 * ratio_x).round() as u32;
            let target_height = (new_height as f64 * ratio_y).round() as u32;

            Some((id, target_width.max(1), target_height.max(1)))
        })
        .collect();

    render_graph_resize_all_transient_textures(graph, &resizes)
}

pub fn render_graph_resize_all_transient_textures<C: 'static>(
    graph: &mut RenderGraph<C>,
    resizes: &[(ResourceId, u32, u32)],
) -> Result<()> {
    if resizes.is_empty() {
        return Ok(());
    }

    let mut actually_resized: Vec<(ResourceId, u32, u32)> = Vec::with_capacity(resizes.len());
    for &(id, width, height) in resizes {
        let needs_update = graph
            .resources
            .descriptors
            .get(&id)
            .map(|descriptor| match &descriptor.resource_type {
                ResourceType::TransientColor {
                    descriptor: tex_desc,
                    ..
                }
                | ResourceType::TransientDepth {
                    descriptor: tex_desc,
                    ..
                } => tex_desc.width != width || tex_desc.height != height,
                _ => true,
            })
            .unwrap_or(false);
        if needs_update {
            graph
                .resources
                .update_transient_descriptor(id, width, height)?;
            actually_resized.push((id, width, height));
        }
    }

    if actually_resized.is_empty() {
        return Ok(());
    }

    let resized_ids: std::collections::HashSet<ResourceId> =
        actually_resized.iter().map(|&(id, _, _)| id).collect();

    drain_aliasing_pool_into_cache(graph);

    graph
        .resources
        .handles
        .retain(|id, _| !resized_ids.contains(id));

    graph.aliasing_info = None;
    graph.needs_resource_reallocation = true;

    Ok(())
}

impl<C: 'static> Default for RenderGraph<C> {
    fn default() -> Self {
        render_graph_new()
    }
}

#[derive(Debug, Clone)]
struct ResourceLifetime {
    resource_id: ResourceId,
    first_use: usize,
    last_use: usize,
}

pub(super) enum PooledResource {
    Texture { texture: Texture },
    Buffer { buffer: Buffer },
}

#[derive(Clone)]
pub(super) enum PoolDescriptorInfo {
    Texture(RenderGraphTextureDescriptor),
    Buffer(RenderGraphBufferDescriptor),
}

pub struct PoolSlot {
    pub(super) resource: Option<PooledResource>,
    pub(super) descriptor_info: Option<PoolDescriptorInfo>,
    pub(super) lifetime_end: usize,
}

#[derive(Clone)]
struct PoolHeapEntry {
    pool_index: usize,
    lifetime_end: usize,
    descriptor_info: PoolDescriptorInfo,
}

impl PartialEq for PoolHeapEntry {
    fn eq(&self, other: &Self) -> bool {
        self.lifetime_end == other.lifetime_end
    }
}

impl Eq for PoolHeapEntry {}

impl PartialOrd for PoolHeapEntry {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for PoolHeapEntry {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.lifetime_end.cmp(&self.lifetime_end)
    }
}

pub struct ResourceAliasingInfo {
    pub aliases: HashMap<ResourceId, usize>,
    pub pools: Vec<PoolSlot>,
}
