use super::{HandleMap, HandleSet, ModuleMap};
use crate::arena::{Arena, Handle};

pub struct ExpressionTracer<'tracer> {
    pub constants: &'tracer Arena<crate::Constant>,

    /// The arena in which we are currently tracing expressions.
    pub expressions: &'tracer Arena<crate::Expression>,

    /// The used map for `types`.
    pub types_used: &'tracer mut HandleSet<crate::Type>,

    /// The used map for `constants`.
    pub constants_used: &'tracer mut HandleSet<crate::Constant>,

    /// The used set for `arena`.
    ///
    /// This points to whatever arena holds the expressions we are
    /// currently tracing: either a function's expression arena, or
    /// the module's constant expression arena.
    pub expressions_used: &'tracer mut HandleSet<crate::Expression>,

    /// The used set for the module's `global_expressions` arena.
    ///
    /// If `None`, we are already tracing the constant expressions,
    /// and `expressions_used` already refers to their handle set.
    pub global_expressions_used: Option<&'tracer mut HandleSet<crate::Expression>>,
}

impl<'tracer> ExpressionTracer<'tracer> {
    /// Propagate usage through `self.expressions`, starting with `self.expressions_used`.
    ///
    /// Treat `self.expressions_used` as the initial set of "known
    /// live" expressions, and follow through to identify all
    /// transitively used expressions.
    ///
    /// Mark types, constants, and constant expressions used directly
    /// by `self.expressions` as used. Items used indirectly are not
    /// marked.
    ///
    /// [fe]: crate::Function::expressions
    /// [ce]: crate::Module::global_expressions
    pub fn trace_expressions(&mut self) {
        log::trace!(
            "entering trace_expression of {}",
            if self.global_expressions_used.is_some() {
                "function expressions"
            } else {
                "const expressions"
            }
        );

        // We don't need recursion or a work list. Because an
        // expression may only refer to other expressions that precede
        // it in the arena, it suffices to make a single pass over the
        // arena from back to front, marking the referents of used
        // expressions as used themselves.
        for (handle, expr) in self.expressions.iter().rev() {
            // If this expression isn't used, it doesn't matter what it uses.
            if !self.expressions_used.contains(handle) {
                continue;
            }

            log::trace!("tracing new expression {:?}", expr);

            use crate::Expression as Ex;
            match *expr {
                // Expressions that do not contain handles that need to be traced.
                Ex::Literal(_)
                | Ex::FunctionArgument(_)
                | Ex::GlobalVariable(_)
                | Ex::LocalVariable(_)
                | Ex::CallResult(_)
                | Ex::SubgroupBallotResult
                | Ex::RayQueryProceedResult => {}

                Ex::Constant(handle) => {
                    self.constants_used.insert(handle);
                    // Constants and expressions are mutually recursive, which
                    // complicates our nice one-pass algorithm. However, since
                    // constants don't refer to each other, we can get around
                    // this by looking *through* each constant and marking its
                    // initializer as used. Since `expr` refers to the constant,
                    // and the constant refers to the initializer, it must
                    // precede `expr` in the arena.
                    let init = self.constants[handle].init;
                    match self.global_expressions_used {
                        Some(ref mut used) => used.insert(init),
                        None => self.expressions_used.insert(init),
                    };
                }
                Ex::Override(_) => {
                    // All overrides are considered used by definition. We mark
                    // their types and initialization expressions as used in
                    // `compact::compact`, so we have no more work to do here.
                }
                Ex::ZeroValue(ty) => {
                    self.types_used.insert(ty);
                }
                Ex::Compose { ty, ref components } => {
                    self.types_used.insert(ty);
                    self.expressions_used
                        .insert_iter(components.iter().cloned());
                }
                Ex::Access { base, index } => self.expressions_used.insert_iter([base, index]),
                Ex::AccessIndex { base, index: _ } => {
                    self.expressions_used.insert(base);
                }
                Ex::Splat { size: _, value } => {
                    self.expressions_used.insert(value);
                }
                Ex::Swizzle {
                    size: _,
                    vector,
                    pattern: _,
                } => {
                    self.expressions_used.insert(vector);
                }
                Ex::Load { pointer } => {
                    self.expressions_used.insert(pointer);
                }
                Ex::ImageSample {
                    image,
                    sampler,
                    gather: _,
                    coordinate,
                    array_index,
                    offset,
                    ref level,
                    depth_ref,
                } => {
                    self.expressions_used
                        .insert_iter([image, sampler, coordinate]);
                    self.expressions_used.insert_iter(array_index);
                    match self.global_expressions_used {
                        Some(ref mut used) => used.insert_iter(offset),
                        None => self.expressions_used.insert_iter(offset),
                    }
                    use crate::SampleLevel as Sl;
                    match *level {
                        Sl::Auto | Sl::Zero => {}
                        Sl::Exact(expr) | Sl::Bias(expr) => {
                            self.expressions_used.insert(expr);
                        }
                        Sl::Gradient { x, y } => self.expressions_used.insert_iter([x, y]),
                    }
                    self.expressions_used.insert_iter(depth_ref);
                }
                Ex::ImageLoad {
                    image,
                    coordinate,
                    array_index,
                    sample,
                    level,
                } => {
                    self.expressions_used.insert(image);
                    self.expressions_used.insert(coordinate);
                    self.expressions_used.insert_iter(array_index);
                    self.expressions_used.insert_iter(sample);
                    self.expressions_used.insert_iter(level);
                }
                Ex::ImageQuery { image, ref query } => {
                    self.expressions_used.insert(image);
                    use crate::ImageQuery as Iq;
                    match *query {
                        Iq::Size { level } => self.expressions_used.insert_iter(level),
                        Iq::NumLevels | Iq::NumLayers | Iq::NumSamples => {}
                    }
                }
                Ex::Unary { op: _, expr } => {
                    self.expressions_used.insert(expr);
                }
                Ex::Binary { op: _, left, right } => {
                    self.expressions_used.insert_iter([left, right]);
                }
                Ex::Select {
                    condition,
                    accept,
                    reject,
                } => self
                    .expressions_used
                    .insert_iter([condition, accept, reject]),
                Ex::Derivative {
                    axis: _,
                    ctrl: _,
                    expr,
                } => {
                    self.expressions_used.insert(expr);
                }
                Ex::Relational { fun: _, argument } => {
                    self.expressions_used.insert(argument);
                }
                Ex::Math {
                    fun: _,
                    arg,
                    arg1,
                    arg2,
                    arg3,
                } => {
                    self.expressions_used.insert(arg);
                    self.expressions_used.insert_iter(arg1);
                    self.expressions_used.insert_iter(arg2);
                    self.expressions_used.insert_iter(arg3);
                }
                Ex::As {
                    expr,
                    kind: _,
                    convert: _,
                } => {
                    self.expressions_used.insert(expr);
                }
                Ex::ArrayLength(expr) => {
                    self.expressions_used.insert(expr);
                }
                Ex::AtomicResult { ty, comparison: _ }
                | Ex::WorkGroupUniformLoadResult { ty }
                | Ex::SubgroupOperationResult { ty } => {
                    self.types_used.insert(ty);
                }
                Ex::RayQueryGetIntersection {
                    query,
                    committed: _,
                } => {
                    self.expressions_used.insert(query);
                }
            }
        }
    }
}

impl ModuleMap {
    /// Fix up all handles in `expr`.
    ///
    /// Use the expression handle remappings in `operand_map`, and all
    /// other mappings from `self`.
    pub fn adjust_expression(
        &self,
        expr: &mut crate::Expression,
        operand_map: &HandleMap<crate::Expression>,
    ) {
        let adjust = |expr: &mut Handle<crate::Expression>| {
            operand_map.adjust(expr);
        };

        use crate::Expression as Ex;
        match *expr {
            // Expressions that do not contain handles that need to be adjusted.
            Ex::Literal(_)
            | Ex::FunctionArgument(_)
            | Ex::GlobalVariable(_)
            | Ex::LocalVariable(_)
            | Ex::CallResult(_)
            | Ex::SubgroupBallotResult
            | Ex::RayQueryProceedResult => {}

            // All overrides are retained, so their handles never change.
            Ex::Override(_) => {}

            // Expressions that contain handles that need to be adjusted.
            Ex::Constant(ref mut constant) => self.constants.adjust(constant),
            Ex::ZeroValue(ref mut ty) => self.types.adjust(ty),
            Ex::Compose {
                ref mut ty,
                ref mut components,
            } => {
                self.types.adjust(ty);
                for component in components {
                    adjust(component);
                }
            }
            Ex::Access {
                ref mut base,
                ref mut index,
            } => {
                adjust(base);
                adjust(index);
            }
            Ex::AccessIndex {
                ref mut base,
                index: _,
            } => adjust(base),
            Ex::Splat {
                size: _,
                ref mut value,
            } => adjust(value),
            Ex::Swizzle {
                size: _,
                ref mut vector,
                pattern: _,
            } => adjust(vector),
            Ex::Load { ref mut pointer } => adjust(pointer),
            Ex::ImageSample {
                ref mut image,
                ref mut sampler,
                gather: _,
                ref mut coordinate,
                ref mut array_index,
                ref mut offset,
                ref mut level,
                ref mut depth_ref,
            } => {
                adjust(image);
                adjust(sampler);
                adjust(coordinate);
                operand_map.adjust_option(array_index);
                if let Some(ref mut offset) = *offset {
                    self.global_expressions.adjust(offset);
                }
                self.adjust_sample_level(level, operand_map);
                operand_map.adjust_option(depth_ref);
            }
            Ex::ImageLoad {
                ref mut image,
                ref mut coordinate,
                ref mut array_index,
                ref mut sample,
                ref mut level,
            } => {
                adjust(image);
                adjust(coordinate);
                operand_map.adjust_option(array_index);
                operand_map.adjust_option(sample);
                operand_map.adjust_option(level);
            }
            Ex::ImageQuery {
                ref mut image,
                ref mut query,
            } => {
                adjust(image);
                self.adjust_image_query(query, operand_map);
            }
            Ex::Unary {
                op: _,
                ref mut expr,
            } => adjust(expr),
            Ex::Binary {
                op: _,
                ref mut left,
                ref mut right,
            } => {
                adjust(left);
                adjust(right);
            }
            Ex::Select {
                ref mut condition,
                ref mut accept,
                ref mut reject,
            } => {
                adjust(condition);
                adjust(accept);
                adjust(reject);
            }
            Ex::Derivative {
                axis: _,
                ctrl: _,
                ref mut expr,
            } => adjust(expr),
            Ex::Relational {
                fun: _,
                ref mut argument,
            } => adjust(argument),
            Ex::Math {
                fun: _,
                ref mut arg,
                ref mut arg1,
                ref mut arg2,
                ref mut arg3,
            } => {
                adjust(arg);
                operand_map.adjust_option(arg1);
                operand_map.adjust_option(arg2);
                operand_map.adjust_option(arg3);
            }
            Ex::As {
                ref mut expr,
                kind: _,
                convert: _,
            } => adjust(expr),
            Ex::AtomicResult {
                ref mut ty,
                comparison: _,
            } => self.types.adjust(ty),
            Ex::WorkGroupUniformLoadResult { ref mut ty } => self.types.adjust(ty),
            Ex::SubgroupOperationResult { ref mut ty } => self.types.adjust(ty),
            Ex::ArrayLength(ref mut expr) => adjust(expr),
            Ex::RayQueryGetIntersection {
                ref mut query,
                committed: _,
            } => adjust(query),
        }
    }

    fn adjust_sample_level(
        &self,
        level: &mut crate::SampleLevel,
        operand_map: &HandleMap<crate::Expression>,
    ) {
        let adjust = |expr: &mut Handle<crate::Expression>| operand_map.adjust(expr);

        use crate::SampleLevel as Sl;
        match *level {
            Sl::Auto | Sl::Zero => {}
            Sl::Exact(ref mut expr) => adjust(expr),
            Sl::Bias(ref mut expr) => adjust(expr),
            Sl::Gradient {
                ref mut x,
                ref mut y,
            } => {
                adjust(x);
                adjust(y);
            }
        }
    }

    fn adjust_image_query(
        &self,
        query: &mut crate::ImageQuery,
        operand_map: &HandleMap<crate::Expression>,
    ) {
        use crate::ImageQuery as Iq;

        match *query {
            Iq::Size { ref mut level } => operand_map.adjust_option(level),
            Iq::NumLevels | Iq::NumLayers | Iq::NumSamples => {}
        }
    }
}