use super::error::{RenderGraphError, Result};
use super::pass::{
    BufferBuilder, ColorTextureBuilder, DepthTextureBuilder, 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 = ()> {
    graph: DiGraph<GraphNode<C>, ResourceId>,
    pass_nodes: HashMap<String, NodeIndex>,
    pass_resource_mappings: HashMap<String, HashMap<String, ResourceId>>,
    sub_graphs: HashMap<String, RenderGraph<C>>,
    sub_graph_inputs: HashMap<String, Vec<SubGraphInputSlot>>,
    pub(super) resources: RenderGraphResources,
    execution_order: Vec<NodeIndex>,
    store_ops: HashMap<ResourceId, StoreOp>,
    clear_ops: std::collections::HashSet<(petgraph::graph::NodeIndex, ResourceId)>,
    aliasing_info: Option<ResourceAliasingInfo>,
    needs_recompile: bool,
    needs_resource_reallocation: bool,
    culled_passes: std::collections::HashSet<NodeIndex>,
    resource_versions: HashMap<ResourceId, u64>,
}

impl<C: 'static> RenderGraph<C> {
    pub fn new() -> Self {
        Self {
            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(),
        }
    }

    pub fn add_pass(
        &mut self,
        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 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 graph_node = GraphNode {
            name: name.clone(),
            reads,
            writes,
            reads_writes,
            pass,
            enabled: true,
        };

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

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

    pub fn get_sub_graph(&self, name: &str) -> Option<&RenderGraph<C>> {
        self.sub_graphs.get(name)
    }

    pub fn get_sub_graph_mut(&mut self, name: &str) -> Option<&mut RenderGraph<C>> {
        self.sub_graphs.get_mut(name)
    }

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

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

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

        Ok(())
    }

    pub fn add_color_texture(&mut self, name: &str) -> ColorTextureBuilder<'_, C> {
        ColorTextureBuilder {
            graph: self,
            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: true,
        }
    }

    pub fn add_depth_texture(&mut self, name: &str) -> DepthTextureBuilder<'_, C> {
        DepthTextureBuilder {
            graph: self,
            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: true,
        }
    }

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

    pub fn transient_color_from_template(
        &mut self,
        name: &str,
        template: &ResourceTemplate,
    ) -> ResourceId {
        self.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,
            },
        )
    }

    pub fn transient_color_from_template_with_clear(
        &mut self,
        name: &str,
        template: &ResourceTemplate,
        clear_color: wgpu::Color,
    ) -> ResourceId {
        self.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),
            },
        )
    }

    pub fn external_color(&mut self, name: &str) -> ResourceId {
        self.resources.register_external_resource(
            name.to_string(),
            ResourceType::ExternalColor {
                clear_color: None,
                force_store: true,
            },
        )
    }

    pub fn add_pass_with_slots(
        &mut self,
        pass: Box<dyn PassNode<C>>,
        slots: Vec<(&str, ResourceId)>,
    ) -> Result<NodeIndex> {
        self.add_pass(pass, &slots)
    }

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

    pub fn resource_pool(&mut self, template: &ResourceTemplate) -> ResourcePool<'_, C> {
        ResourcePool {
            graph: self,
            template: template.clone(),
        }
    }

    pub fn set_external_texture(
        &mut self,
        id: ResourceId,
        view: TextureView,
        width: u32,
        height: u32,
    ) {
        self.resources.set_external_texture(id, view, width, height);
    }

    pub fn set_external_buffer(&mut self, id: ResourceId, buffer: Buffer) {
        self.resources.set_external_buffer(id, buffer);
    }

    fn build_dependency_edges(&mut self) {
        let mut resource_writers: HashMap<ResourceId, NodeIndex> = HashMap::new();

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

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

            for &read_resource in &reads {
                if let Some(&writer_index) = resource_writers.get(&read_resource)
                    && !self.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)
                    && !self.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 {
            self.graph.add_edge(from, to, resource);
        }
    }

    fn compute_resource_lifetimes(&self, 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 = &self.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;
            }
        }

        lifetimes
            .into_iter()
            .filter(|(id, _)| {
                if let Some(desc) = self.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 compute_resource_aliasing(
        &self,
        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 = self.resources.get_descriptor(lifetime.resource_id).unwrap();

            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;

            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,
                            ..
                        },
                    ) => Self::can_alias_textures(pool_desc, res_desc),
                    (
                        PoolDescriptorInfo::Buffer(pool_desc),
                        ResourceType::TransientBuffer {
                            descriptor: res_desc,
                        },
                    ) => Self::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
                                } else {
                                    false
                                }
                            }
                            (
                                PoolDescriptorInfo::Buffer(pool_desc),
                                ResourceType::TransientBuffer {
                                    descriptor: res_desc,
                                },
                            ) => {
                                if res_desc.size > pool_desc.size {
                                    *pool_desc = res_desc.clone();
                                    true
                                } else {
                                    false
                                }
                            }
                            _ => 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 compute_store_ops(&self, 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 = &self.graph[node_index];

            for &resource_id in node.reads.iter().chain(&node.reads_writes) {
                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 = &self.graph[node_index];

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

                let store_op = if descriptor.is_external {
                    match &descriptor.resource_type {
                        ResourceType::ExternalColor { force_store, .. }
                        | ResourceType::ExternalDepth { force_store, .. } => {
                            if *force_store
                                || last_read
                                    .get(&resource_id)
                                    .is_some_and(|&last| last > index)
                            {
                                StoreOp::Store
                            } else {
                                StoreOp::Discard
                            }
                        }
                        ResourceType::ExternalBuffer => StoreOp::Store,
                        _ => StoreOp::Store,
                    }
                } else if last_read
                    .get(&resource_id)
                    .is_some_and(|&last| last > index)
                {
                    StoreOp::Store
                } else {
                    StoreOp::Discard
                };

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

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

        store_ops
    }

    fn compute_clear_ops(
        &self,
        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 = &self.graph[node_index];

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

        for (&resource_id, &node_index) in &first_write {
            if let Some(descriptor) = self.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 compute_dead_passes(&self, 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 self.resources.descriptors.keys() {
            let descriptor = self.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 = &self.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);
            }
        }

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

    pub fn compile(&mut self) -> Result<()> {
        self.build_dependency_edges();

        self.execution_order = petgraph::algo::toposort(&self.graph, None)
            .map_err(|_| RenderGraphError::CyclicDependency)?;

        self.store_ops = self.compute_store_ops(&self.execution_order);
        self.clear_ops = self.compute_clear_ops(&self.execution_order);

        let lifetimes = self.compute_resource_lifetimes(&self.execution_order);
        self.aliasing_info = Some(self.compute_resource_aliasing(lifetimes));

        self.culled_passes = self.compute_dead_passes(&self.execution_order);

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

    fn recompile_if_needed(&mut self) -> Result<()> {
        if self.needs_resource_reallocation {
            let lifetimes = self.compute_resource_lifetimes(&self.execution_order);
            self.aliasing_info = Some(self.compute_resource_aliasing(lifetimes));
            self.needs_resource_reallocation = false;
            return Ok(());
        }

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

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

        self.build_dependency_edges();

        self.execution_order = petgraph::algo::toposort(&self.graph, None)
            .map_err(|_| RenderGraphError::CyclicDependency)?;

        self.store_ops = self.compute_store_ops(&self.execution_order);
        self.clear_ops = self.compute_clear_ops(&self.execution_order);

        let lifetimes = self.compute_resource_lifetimes(&self.execution_order);
        self.aliasing_info = Some(self.compute_resource_aliasing(lifetimes));

        self.culled_passes = self.compute_dead_passes(&self.execution_order);

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

    pub fn execute(
        &mut self,
        device: &Device,
        queue: &wgpu::Queue,
        configs: &C,
    ) -> Result<Vec<CommandBuffer>> {
        self.recompile_if_needed()?;

        if self.aliasing_info.is_none() {
            let lifetimes = self.compute_resource_lifetimes(&self.execution_order);
            self.aliasing_info = Some(self.compute_resource_aliasing(lifetimes));
        }

        if let Some(aliasing_info) = &mut self.aliasing_info {
            self.resources.allocate_transient_resources_with_aliasing(
                device,
                &self.store_ops,
                aliasing_info,
            );
        }

        self.invalidate_bind_groups_for_changed_resources();

        for &node_index in &self.execution_order {
            if self.culled_passes.contains(&node_index) {
                continue;
            }

            let node = &mut self.graph[node_index];
            node.pass.prepare(device, queue, configs);
        }

        self.execute_serial(device, queue, configs)
    }

    fn invalidate_bind_groups_for_changed_resources(&mut self) {
        let mut dirty_resources = HashSet::new();

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

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

        if dirty_resources.is_empty() {
            return;
        }

        let mut passes_to_invalidate = HashSet::new();

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

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

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

    fn execute_serial(
        &mut self,
        device: &Device,
        queue: &wgpu::Queue,
        configs: &C,
    ) -> Result<Vec<CommandBuffer>> {
        let mut encoder = device.create_command_encoder(&wgpu::CommandEncoderDescriptor {
            label: Some("RenderGraph Serial Encoder"),
        });

        let mut command_buffers = Vec::new();

        for &node_index in &self.execution_order {
            if self.culled_passes.contains(&node_index) {
                continue;
            }

            let is_enabled = self.graph[node_index].enabled;
            let node = &mut self.graph[node_index];

            let slot_mappings = self.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: &self.resources,
                    device,
                    slot_mappings,
                    configs,
                    sub_graph_commands: Vec::new(),
                    node_index,
                    clear_ops: &self.clear_ops,
                    pass_enabled: is_enabled,
                };

                node.pass.execute(context)?
            };

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

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

                let input_slots = self
                    .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 {
                                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,
                                                (*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 = sub_graph.execute(device, queue, configs)?;
                command_buffers.extend(sub_graph_buffers);

                encoder = device.create_command_encoder(&wgpu::CommandEncoderDescriptor {
                    label: Some("RenderGraph Serial Encoder"),
                });
            }
        }

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

    pub fn resources_mut(&mut self) -> &mut RenderGraphResources {
        &mut self.resources
    }

    pub fn resize_transient_resource(
        &mut self,
        _device: &Device,
        id: ResourceId,
        width: u32,
        height: u32,
    ) -> Result<()> {
        self.resources
            .update_transient_descriptor(id, width, height)?;

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

impl<C: 'static> Default for RenderGraph<C> {
    fn default() -> Self {
        Self::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>,
}
