use std::rc::Rc;

use ordermap::OrderMap;
use thiserror::Error;
use vecmap::map::{Entry, VecMap};

use crate::{
    tree::ast::identifier::{Identifier, SimpleIdentifier},
    tree::typed_ast::expression::TypedExpression,
    types::{struct_type::Struct, Type},
};

/// A type environment for the TypedAST that stores flattened type bindings
/// and tracks lineage of computed fields.
///
/// Unlike the old Environment which was designed for SQL translation,
/// TypeEnvironment is specifically designed for type checking with:
/// - Flattened storage (x.y.z: int instead of nested structs)
/// - Expression lineage tracking (knowing HOW each field was computed)
/// - Proper parent chaining for lexical scoping
/// - Tombstones for efficient DROP operations
/// - Trie-based storage: O(segments) lookup instead of O(n) linear scan
#[derive(Debug, Clone, Default)]
pub struct TypeEnvironment {
    /// Parent environment(s) - can be single (for LET) or merged (for FROM/JOIN)
    base: Option<TypeEnvironmentParent>,

    /// Trie root for local bindings in this scope
    /// Each path through the trie represents a dotted identifier (e.g., x.y.z)
    trie: TrieNode,
}

/// A trie node for storing bindings by identifier segments.
/// A node is either a Terminal (has a binding) or Intermediate (has children).
/// This invariant is enforced by the type system.
#[derive(Debug, Clone)]
enum TrieNode {
    /// A terminal node with a binding (Present or Tombstone)
    Terminal(Binding),
    /// An intermediate node with children (no binding at this path)
    /// VecMap is used instead of OrderMap because trie nodes typically have few children
    /// (field names at each level), making linear search faster than hash-based lookup.
    Intermediate(VecMap<SimpleIdentifier, TrieNode>),
}

impl Default for TrieNode {
    fn default() -> Self {
        TrieNode::Intermediate(VecMap::new())
    }
}

/// Represents how environments chain together
/// Keeping as an enum to support multiple parent styles (potentially those which merge?)
#[derive(Debug, Clone)]
pub enum TypeEnvironmentParent {
    /// Single parent (used by LET commands, or FROM single table)
    Single(Rc<TypeEnvironment>),
}

/// Represents the lineage (source/origin) of a field in the type environment
#[derive(Debug, Clone)]
pub enum Lineage {
    /// Computed from an expression - chase ColumnReferences inside for deeper lineage
    Computed(Rc<TypedExpression>),
    /// Base field from catalog/CTE
    Base(Rc<Type>),
}

impl Lineage {
    /// Get the type from this lineage
    pub fn get_type(&self) -> Rc<Type> {
        match self {
            Lineage::Computed(expr) => expr.resolved_type.clone(),
            Lineage::Base(typ) => typ.clone(),
        }
    }
}

/// A binding in the type environment
#[derive(Debug, Clone)]
pub enum Binding {
    /// A present binding with its lineage
    Present(Lineage),
    /// A tombstone marking this identifier as dropped
    Tombstone,
}

impl Binding {
    /// Get the type of this binding, if it has one (tombstones return None)
    pub fn get_type(&self) -> Option<Rc<Type>> {
        match self {
            Binding::Present(lineage) => Some(lineage.get_type()),
            Binding::Tombstone => None,
        }
    }

    /// Get the lineage for this binding
    pub fn get_lineage(&self) -> Option<&Lineage> {
        match self {
            Binding::Present(lineage) => Some(lineage),
            Binding::Tombstone => None,
        }
    }
}

/// Errors that can occur when working with TypeEnvironment
#[derive(Debug, Error)]
pub enum TypeEnvironmentError {
    #[error("Field name conflict: identifier '{ident}' is already defined")]
    FieldNameConflict { ident: String },

    #[error("Cannot access field of non-struct type: '{identifier}' has type {actual_type}")]
    FieldAccessOnNonStruct {
        identifier: String,
        actual_type: Type,
    },
}

impl TrieNode {
    /// Get children if this is an Intermediate node, None if Terminal
    fn children(&self) -> Option<&VecMap<SimpleIdentifier, TrieNode>> {
        match self {
            TrieNode::Terminal(_) => None,
            TrieNode::Intermediate(children) => Some(children),
        }
    }

    /// Get child at key (works for both Terminal and Intermediate)
    fn get_child(&self, key: &SimpleIdentifier) -> Option<&TrieNode> {
        self.children().and_then(|c| c.get(key))
    }

    /// Insert a binding at the given identifier (creating intermediate nodes as needed)
    /// Returns Err if the path conflicts with existing bindings.
    /// The bool indicates whether a binding already existed at the exact path (true)
    /// vs a structural conflict like path-through-terminal or has-children (false).
    fn insert(&mut self, id: &Identifier, binding: Binding) -> Result<(), bool> {
        let segments = id.segments();
        let mut current = self;

        // Navigate to the parent of the final segment, creating intermediate nodes as needed
        for segment in &segments[..segments.len() - 1] {
            let children = match current {
                TrieNode::Intermediate(children) => children,
                TrieNode::Terminal(_) => return Err(false),
            };
            current = children
                .entry(segment.clone())
                .or_insert_with(|| TrieNode::Intermediate(VecMap::new()));
        }

        // Insert at the final segment
        let last_segment = &segments[segments.len() - 1];
        let children = match current {
            TrieNode::Intermediate(children) => children,
            TrieNode::Terminal(_) => return Err(false),
        };
        match children.entry(last_segment.clone()) {
            Entry::Occupied(entry) => match entry.get() {
                TrieNode::Terminal(_) => Err(true), // Already exists
                TrieNode::Intermediate(grandchildren) if !grandchildren.is_empty() => Err(false),
                TrieNode::Intermediate(_) => {
                    *entry.into_mut() = TrieNode::Terminal(binding);
                    Ok(())
                }
            },
            Entry::Vacant(entry) => {
                entry.insert(TrieNode::Terminal(binding));
                Ok(())
            }
        }
    }
}

impl TypeEnvironment {
    /// Create empty environment with no base
    pub fn default() -> Self {
        Self {
            base: None,
            trie: TrieNode::default(),
        }
    }

    /// Create new environment with a single base
    pub fn new(parent: Rc<TypeEnvironment>) -> Self {
        Self {
            base: Some(TypeEnvironmentParent::Single(parent)),
            trie: TrieNode::default(),
        }
    }

    /// Look up the type of an identifier
    ///
    /// Returns None if:
    /// - The identifier doesn't exist
    /// - The identifier is tombstoned
    /// - Any prefix of the identifier is tombstoned
    ///
    /// If the identifier is not found directly, attempts to reconstruct a struct type
    /// from all bindings that have the identifier as a prefix (e.g., looking up "x.y"
    /// when "x.y.z" and "x.y.a" exist will return a struct {z, a}).
    pub fn lookup(&self, id: &Identifier) -> Option<Rc<Type>> {
        let segments = id.segments();

        // Phase 1: Build initial candidates from first segment
        let mut candidates = self.build_initial_candidates(&segments[0]);
        if candidates.is_empty() {
            return None;
        }

        // Phase 2: Advance through ALL remaining segments
        for segment in &segments[1..] {
            candidates = Self::advance_candidates(candidates, segment);
        }

        // Phase 3: Examine candidates and return type (no lineage reconstruction)
        Self::final_lookup_type(candidates)
    }

    /// Check if any parent prefix has a direct struct-typed binding.
    ///
    /// This is used to determine if compound identifier assignments need desugaring.
    /// A "non-clean" parent means we must reconstruct the entire struct.
    ///
    /// Returns:
    /// - `Ok(Some((prefix, struct)))` if a prefix has a DIRECT struct binding (needs desugaring)
    /// - `Ok(None)` if all prefixes are clean (can bind directly)
    /// - `Err(...)` if a prefix has a non-struct binding (can't access fields)
    ///
    /// IMPORTANT: This function only considers DIRECT bindings, not reconstructed structs.
    /// If `x.a` and `x.b` exist but `x` has no direct binding, this returns Ok(None).
    pub fn lookup_struct(
        &self,
        id: &Identifier,
    ) -> Result<Option<(Identifier, Struct)>, TypeEnvironmentError> {
        // Check each strict prefix of the identifier for a direct binding
        for prefix in id.prefixes() {
            // Look up the prefix - but we only care about DIRECT bindings, not reconstructed
            let segments = prefix.segments();

            // Phase 1: Build candidates for the first segment
            let mut candidates = self.build_initial_candidates(&segments[0]);
            if candidates.is_empty() {
                continue;
            }

            // Phase 2: Advance through ALL remaining segments
            for segment in &segments[1..] {
                candidates = Self::advance_candidates(candidates, segment);
                if candidates.is_empty() {
                    break;
                }
            }

            if candidates.is_empty() {
                continue;
            }

            // Phase 3: Check candidates for a DIRECT terminal binding
            for candidate in &candidates {
                match candidate {
                    TrieNode::Terminal(Binding::Present(lineage)) => {
                        let typ = lineage.get_type();
                        match typ.as_ref() {
                            Type::Struct(s) => {
                                return Ok(Some((prefix, s.clone())));
                            }
                            other => {
                                return Err(TypeEnvironmentError::FieldAccessOnNonStruct {
                                    identifier: prefix.to_string(),
                                    actual_type: other.clone(),
                                });
                            }
                        }
                    }
                    TrieNode::Terminal(Binding::Tombstone) => break,
                    TrieNode::Intermediate(children) if !children.is_empty() => {
                        // Intermediate WITH children - shadows older candidates
                        // No direct binding at this prefix, move to next prefix
                        break;
                    }
                    TrieNode::Intermediate(_) => {
                        // Intermediate WITHOUT children - skip, check older
                    }
                }
            }
        }

        // No prefix has a direct binding
        Ok(None)
    }

    /// Look up the lineage of an identifier
    ///
    /// Returns one-level-deep lineage - caller can chase recursively by inspecting
    /// ColumnReferences in Computed expressions.
    ///
    /// Returns empty vec if:
    /// - The identifier doesn't exist
    /// - The identifier is tombstoned
    /// - Any prefix is tombstoned
    ///
    /// For exact matches:
    /// - Returns all lineages for this binding (may be multiple in merged environments)
    ///
    /// For reconstructed structs (prefix lookup):
    /// - Returns vec of all child bindings with their full identifiers (not stripped)
    ///
    /// For merged environments:
    /// - Can return multiple entries with the same identifier from different sources
    pub fn lineage(&self, id: &Identifier) -> Vec<(Identifier, Lineage)> {
        let segments = id.segments();

        // Phase 1: Build initial candidates from first segment
        let mut candidates = self.build_initial_candidates(&segments[0]);
        if candidates.is_empty() {
            return vec![];
        }

        // Phase 2: Advance through ALL remaining segments
        for segment in &segments[1..] {
            candidates = Self::advance_candidates(candidates, segment);
        }

        // Phase 3: Examine candidates and return lineage
        Self::final_lookup_lineage(id, candidates)
    }

    /// Phase 1: Build initial candidates by chasing parent chain
    /// Returns trie nodes for the first segment, ordered youngest-to-oldest
    fn build_initial_candidates(&self, first_segment: &SimpleIdentifier) -> Vec<&TrieNode> {
        let mut candidates = vec![];
        let mut env: Option<&TypeEnvironment> = Some(self);

        while let Some(e) = env {
            if let Some(node) = e.trie.get_child(first_segment) {
                match node {
                    TrieNode::Terminal(_) => {
                        // Terminal - add it and STOP chasing parents (shadows all older)
                        candidates.push(node);
                        break;
                    }
                    TrieNode::Intermediate(_) => {
                        // Intermediate - add and continue to parent
                        candidates.push(node);
                    }
                }
            }
            env = match &e.base {
                Some(TypeEnvironmentParent::Single(parent)) => Some(parent.as_ref()),
                None => None,
            };
        }

        candidates
    }

    /// Phase 2: Advance candidates through a segment
    /// Keeps both Terminal and Intermediate nodes. Terminal nodes shadow older candidates.
    /// If a Terminal is carried forward and we try to advance again, get_child returns None
    /// and it will be dropped naturally.
    fn advance_candidates<'a>(
        candidates: Vec<&'a TrieNode>,
        segment: &SimpleIdentifier,
    ) -> Vec<&'a TrieNode> {
        let mut next_candidates = vec![];

        for candidate in candidates {
            if let Some(child) = candidate.get_child(segment) {
                match child {
                    TrieNode::Terminal(_) => {
                        // Terminal - valid result, shadows older candidates
                        next_candidates.push(child);
                        break;
                    }
                    TrieNode::Intermediate(_) => {
                        // Intermediate - keep following
                        next_candidates.push(child);
                    }
                }
            }
            // else: no child at this segment - candidate is dropped
        }

        next_candidates
    }

    /// Phase 3: Final lookup returning just the type (optimized path for lookup()).
    /// Candidates already point directly to the target nodes.
    fn final_lookup_type(candidates: Vec<&TrieNode>) -> Option<Rc<Type>> {
        let mut merge_candidates = vec![];

        for candidate in candidates {
            match candidate {
                TrieNode::Terminal(Binding::Present(lineage)) => {
                    if !merge_candidates.is_empty() {
                        break;
                    }
                    // Direct hit - no struct reconstruction needed
                    return Some(lineage.get_type());
                }
                TrieNode::Terminal(Binding::Tombstone) => {
                    if !merge_candidates.is_empty() {
                        break;
                    }
                    return None;
                }
                TrieNode::Intermediate(children) if !children.is_empty() => {
                    merge_candidates.push(candidate);
                }
                TrieNode::Intermediate(_) => {}
            }
        }

        if merge_candidates.is_empty() {
            None
        } else {
            // Struct reconstruction path - need to merge children
            let (struct_type, _) = Self::merge_children_to_struct(None, &merge_candidates);
            match &struct_type {
                Type::Struct(s) if s.fields.is_empty() => None,
                _ => Some(Rc::new(struct_type)),
            }
        }
    }

    /// Phase 3: Final lookup returning lineage (for lineage() method).
    /// Candidates already point directly to the target nodes.
    fn final_lookup_lineage(
        id: &Identifier,
        candidates: Vec<&TrieNode>,
    ) -> Vec<(Identifier, Lineage)> {
        let mut merge_candidates = vec![];

        for candidate in candidates {
            match candidate {
                TrieNode::Terminal(Binding::Present(lineage)) => {
                    if !merge_candidates.is_empty() {
                        break;
                    }
                    // Direct hit - single lineage entry
                    return vec![(id.clone(), lineage.clone())];
                }
                TrieNode::Terminal(Binding::Tombstone) => {
                    if !merge_candidates.is_empty() {
                        break;
                    }
                    return vec![];
                }
                TrieNode::Intermediate(children) if !children.is_empty() => {
                    merge_candidates.push(candidate);
                }
                TrieNode::Intermediate(_) => {}
            }
        }

        if merge_candidates.is_empty() {
            vec![]
        } else {
            // Struct reconstruction path - collect all child lineages
            let (_, lineages) = Self::merge_children_to_struct(Some(id), &merge_candidates);
            lineages
        }
    }

    /// Merge children from multiple candidates into a struct type, optionally collecting lineage.
    ///
    /// When `prefix` is Some, lineage is collected for each field. When None, lineage
    /// collection is skipped (optimization for lookup() which only needs the type).
    ///
    /// Candidates are processed youngest-to-oldest; earlier fields shadow later ones.
    /// This properly handles merging across multiple candidates at each level:
    /// if env1 has `x.a` and env2 has `x.b`, looking up `x` will merge both.
    fn merge_children_to_struct(
        prefix: Option<&Identifier>,
        candidates: &[&TrieNode],
    ) -> (Type, Vec<(Identifier, Lineage)>) {
        let mut fields: OrderMap<crate::sql::expression::identifier::SimpleIdentifier, Type> =
            OrderMap::new();
        let mut lineages: Vec<(Identifier, Lineage)> = vec![];

        // Collect all children from all candidates, grouped by field name
        // OrderMap preserves insertion order: youngest candidate's fields first
        let mut field_nodes: OrderMap<SimpleIdentifier, Vec<&TrieNode>> = OrderMap::new();

        for candidate in candidates {
            let Some(children) = candidate.children() else {
                continue;
            };
            for (key, child) in children {
                field_nodes.entry(key.clone()).or_default().push(child);
            }
        }

        // Process each field (youngest-to-oldest within each field's node list)
        for (key, nodes) in field_nodes {
            let sql_key = crate::sql::expression::identifier::SimpleIdentifier::new(key.as_str());
            let child_prefix = prefix.map(|p| p.clone() + key.clone().into());

            // First node determines the behavior (youngest shadows older)
            match nodes[0] {
                TrieNode::Terminal(Binding::Present(lineage)) => {
                    fields.insert(sql_key, lineage.get_type().as_ref().clone());
                    if let Some(child_id) = child_prefix {
                        lineages.push((child_id, lineage.clone()));
                    }
                }
                TrieNode::Terminal(Binding::Tombstone) => {
                    // Tombstone shadows all older - field is dropped
                }
                TrieNode::Intermediate(_) => {
                    // Collect all Intermediate nodes until we hit a Terminal (which shadows)
                    let intermediate_nodes: Vec<&TrieNode> = nodes
                        .iter()
                        .take_while(|n| matches!(n, TrieNode::Intermediate(_)))
                        .filter(|n| !n.children().map_or(true, |c| c.is_empty()))
                        .copied()
                        .collect();

                    if intermediate_nodes.is_empty() {
                        continue;
                    }

                    // Recursively merge all intermediate nodes at this level
                    let (nested_type, nested_lineages) =
                        Self::merge_children_to_struct(child_prefix.as_ref(), &intermediate_nodes);

                    // Skip empty structs (all children tombstoned)
                    if let Type::Struct(s) = &nested_type {
                        if s.fields.is_empty() {
                            continue;
                        }
                    }
                    fields.insert(sql_key, nested_type);
                    lineages.extend(nested_lineages);
                }
            }
        }

        (Type::Struct(Struct::new(fields)), lineages)
    }

    /// Add a computed binding (consuming self), checking for conflicts
    pub fn with_computed(
        mut self,
        id: Identifier,
        expr: Rc<TypedExpression>,
    ) -> Result<Self, TypeEnvironmentError> {
        self.bind_computed(id, expr)?;
        Ok(self)
    }

    /// Link this TypeEnvironment to a single parent
    pub fn with_single_parent(mut self, parent: Rc<TypeEnvironment>) -> Self {
        self.base = Some(TypeEnvironmentParent::Single(parent));
        self
    }

    /// Add a base type binding (consuming self), checking for conflicts
    pub fn with_base(mut self, id: Identifier, typ: Type) -> Result<Self, TypeEnvironmentError> {
        self.bind_base(id, typ)?;
        Ok(self)
    }

    /// Add a computed binding (mutating), checking for conflicts
    pub fn bind_computed(
        &mut self,
        id: Identifier,
        expr: Rc<TypedExpression>,
    ) -> Result<(), TypeEnvironmentError> {
        self.trie
            .insert(&id, Binding::Present(Lineage::Computed(expr)))
            .map_err(|_| TypeEnvironmentError::FieldNameConflict {
                ident: id.to_string(),
            })
    }

    /// Add a base type binding (mutating), checking for conflicts
    pub fn bind_base(&mut self, id: Identifier, typ: Type) -> Result<(), TypeEnvironmentError> {
        self.trie
            .insert(&id, Binding::Present(Lineage::Base(Rc::new(typ))))
            .map_err(|_| TypeEnvironmentError::FieldNameConflict {
                ident: id.to_string(),
            })
    }

    /// Drop a binding (adds a tombstone)
    ///
    /// Returns an error if any binding (Present or Tombstone) already exists at this path,
    /// or if there's a structural conflict (children exist or path goes through a terminal).
    pub fn drop(&mut self, id: &Identifier) -> Result<(), TypeEnvironmentError> {
        self.trie.insert(id, Binding::Tombstone).map_err(|_| {
            TypeEnvironmentError::FieldNameConflict {
                ident: id.to_string(),
            }
        })
    }

    /// Drop a binding (adds a tombstone), consuming self
    pub fn without(mut self, id: Identifier) -> Result<Self, TypeEnvironmentError> {
        self.drop(&id)?;
        Ok(self)
    }

    /// Convert to a single Struct type (constructs nested Struct from flattened bindings)
    /// Traverses the entire parent chain and reconstructs nested structures from compound identifiers.
    ///
    /// Field ordering:
    /// - Youngest environment's fields come first, then parent's, etc.
    /// - Within each environment, fields appear in insertion order
    /// - Tombstones shadow older bindings (field is excluded)
    /// - If a child env has a binding under `x`, it claims `x`'s position (shadows parent's position)
    pub fn flatten(&self) -> Struct {
        // Collect root trie nodes from each environment (youngest to oldest)
        let mut candidates: Vec<&TrieNode> = vec![];
        let mut env: Option<&TypeEnvironment> = Some(self);

        while let Some(e) = env {
            candidates.push(&e.trie);
            env = match &e.base {
                Some(TypeEnvironmentParent::Single(parent)) => Some(parent.as_ref()),
                None => None,
            };
        }

        // Merge all candidates into a single struct
        Self::merge_candidates_to_struct(&candidates)
    }

    /// Merge trie node candidates into a Struct (without tracking lineage).
    /// Used by flatten() where we only need the type, not lineage info.
    ///
    /// Field ordering: youngest environment's fields first, then older environments.
    /// A field is "owned" by the youngest environment that contributes actual content
    /// (not just tombstones or empty intermediates).
    fn merge_candidates_to_struct(candidates: &[&TrieNode]) -> Struct {
        let mut fields: OrderMap<crate::sql::expression::identifier::SimpleIdentifier, Type> =
            OrderMap::new();

        // Collect all children from all candidates, grouped by field name
        // We use a Vec of (key, nodes) to control ordering later
        let mut field_nodes: OrderMap<SimpleIdentifier, Vec<&TrieNode>> = OrderMap::new();

        for candidate in candidates {
            let Some(children) = candidate.children() else {
                continue;
            };
            for (key, child) in children {
                field_nodes.entry(key.clone()).or_default().push(child);
            }
        }

        // Determine field ordering by collecting names with Present bindings from each candidate.
        // This mirrors the original flatten() logic: youngest env's fields first, then older.
        // Tombstones shadow but don't claim position.
        let mut names_per_candidate: Vec<Vec<SimpleIdentifier>> = vec![];
        for candidate in candidates {
            let mut names = vec![];
            let Some(children) = candidate.children() else {
                names_per_candidate.push(names);
                continue;
            };
            for (key, child) in children {
                if Self::node_has_present_binding(child) {
                    names.push(key.clone());
                }
            }
            names_per_candidate.push(names);
        }

        // Build field_order: iterate youngest to oldest, skip already-seen
        let mut field_order: Vec<SimpleIdentifier> = vec![];
        let mut seen: OrderMap<SimpleIdentifier, bool> = OrderMap::new();

        for names in &names_per_candidate {
            for key in names {
                if seen.contains_key(key) {
                    continue;
                }
                seen.insert(key.clone(), true);
                field_order.push(key.clone());
            }
        }

        // Process fields in the determined order
        for key in field_order {
            let nodes = &field_nodes[&key];
            let sql_key = crate::sql::expression::identifier::SimpleIdentifier::new(key.as_str());

            match nodes[0] {
                TrieNode::Terminal(Binding::Present(lineage)) => {
                    fields.insert(sql_key, lineage.get_type().as_ref().clone());
                }
                TrieNode::Terminal(Binding::Tombstone) => {
                    // Tombstone shadows all - field is dropped
                }
                TrieNode::Intermediate(_) => {
                    let intermediate_nodes: Vec<&TrieNode> = nodes
                        .iter()
                        .take_while(|n| matches!(n, TrieNode::Intermediate(_)))
                        .filter(|n| !n.children().map_or(true, |c| c.is_empty()))
                        .copied()
                        .collect();

                    if intermediate_nodes.is_empty() {
                        continue;
                    }

                    let nested = Self::merge_candidates_to_struct(&intermediate_nodes);
                    if nested.fields.is_empty() {
                        continue;
                    }
                    fields.insert(sql_key, nested.into());
                }
            }
        }

        Struct::new(fields)
    }

    /// Check if a node has any Present binding (directly or in descendants)
    fn node_has_present_binding(node: &TrieNode) -> bool {
        match node {
            TrieNode::Terminal(Binding::Present(_)) => true,
            TrieNode::Terminal(Binding::Tombstone) => false,
            TrieNode::Intermediate(children) => {
                children.values().any(Self::node_has_present_binding)
            }
        }
    }
}

impl From<Struct> for TypeEnvironment {
    /// Create a TypeEnvironment from a Struct by flattening all nested fields into the trie.
    /// All bindings are created as `Lineage::Base` since they come from schema, not expressions.
    fn from(s: Struct) -> Self {
        let mut env = TypeEnvironment::default();
        for (sql_id, typ) in s.iter_flattened() {
            // Convert SQL identifier to AST identifier
            let ast_id: Identifier = sql_id.into();
            // Struct fields are guaranteed unique by construction, so insert should never fail.
            // If it does, it indicates a bug in Struct's iter_flattened().
            let result = env.trie.insert(
                &ast_id,
                Binding::Present(Lineage::Base(Rc::new(typ.clone()))),
            );
            debug_assert!(
                result.is_ok(),
                "Struct::iter_flattened() produced duplicate path: {}",
                ast_id
            );
        }
        env
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::tree::builder::identifier::ident;
    use crate::types::{BOOLEAN, INT, STRING};
    use rstest::rstest;

    #[rstest]
    #[case::cannot_rebind_different_types(
        // Try to bind x twice with different types
        vec![(ident("x").into(), INT), (ident("x").into(), STRING)],
        false,
        None,
        None,
    )]
    #[case::cannot_rebind_same_type(
        // Try to bind x twice with same type - should also fail
        vec![(ident("x").into(), INT), (ident("x").into(), INT)],
        false,
        None,
        None,
    )]
    #[case::cannot_bind_prefix_after_child(
        // Bind x.y.z first, then try to bind x.y (a prefix)
        vec![
            (ident("x").dot("y").dot("z").into(), INT),
            (ident("x").dot("y").into(), INT),
        ],
        false,
        None,
        None,
    )]
    #[case::cannot_bind_child_after_prefix(
        // Bind x.y first, then try to bind x.y.z (a child)
        vec![
            (ident("x").dot("y").into(), INT),
            (ident("x").dot("y").dot("z").into(), INT),
        ],
        false,
        None,
        None,
    )]
    #[case::cannot_bind_simple_prefix_after_compound(
        // Bind x.y first, then try to bind x (simple prefix)
        vec![(ident("x").dot("y").into(), INT), (ident("x").into(), INT)],
        false,
        None,
        None,
    )]
    #[case::cannot_bind_compound_after_simple(
        // Bind x first, then try to bind x.y (child)
        vec![(ident("x").into(), INT), (ident("x").dot("y").into(), INT)],
        false,
        None,
        None,
    )]
    #[case::can_bind_unrelated_compound_identifiers(
        // Multiple bindings with no prefix relationships
        vec![
            (ident("x").dot("y").into(), INT),
            (ident("x").dot("z").into(), INT),
            (ident("a").dot("b").into(), INT),
        ],
        true,
        // Expected flatten: {x: {y: int, z: int}, a: {b: int}}
        Some(Struct::default()
            .with_str("x", Struct::default()
                .with_str("y", INT)
                .with_str("z", INT)
                .into())
            .with_str("a", Struct::default()
                .with_str("b", INT)
                .into())),
        // Lookups
        Some(vec![
            (ident("x").dot("y").into(), Some(INT)),
            (ident("x").dot("z").into(), Some(INT)),
            (ident("a").dot("b").into(), Some(INT)),
            (ident("x").into(), Some(Type::Struct(Struct::default()
                .with_str("y", INT)
                .with_str("z", INT)))),
            (ident("a").into(), Some(Type::Struct(Struct::default()
                .with_str("b", INT)))),
        ]),
    )]
    fn test_local_binding_conflicts(
        #[case] bindings: Vec<(Identifier, Type)>,
        #[case] should_succeed: bool,
        #[case] expected_flatten: Option<Struct>,
        #[case] expected_lookups: Option<Vec<(Identifier, Option<Type>)>>,
    ) {
        let mut env = TypeEnvironment::default();
        let mut results = Vec::new();

        for (id, typ) in bindings {
            results.push(env.bind_base(id, typ));
        }

        if should_succeed {
            assert!(
                results.iter().all(|r| r.is_ok()),
                "Expected all bindings to succeed"
            );

            // Verify flatten output
            if let Some(expected) = expected_flatten {
                assert_eq!(env.flatten(), expected, "Flatten output mismatch");
            }

            // Verify lookups
            if let Some(lookups) = expected_lookups {
                for (lookup_id, expected_type) in lookups {
                    let result = env.lookup(&lookup_id);
                    assert_eq!(
                        result.as_ref().map(|t| t.as_ref()),
                        expected_type.as_ref(),
                        "Lookup mismatch for {:?}",
                        lookup_id
                    );
                }
            }
        } else {
            assert!(
                results.last().unwrap().is_err(),
                "Expected last binding to fail"
            );
        }
    }

    #[rstest]
    #[case::simple_single_environment(
        // Stack: single level with simple identifiers
        vec![
            TypeEnvironment::default()
                .with_base(ident("x").into(), INT).unwrap()
                .with_base(ident("y").into(), STRING).unwrap(),
        ],
        // Expected flatten: {x: int, y: string}
        Struct::default()
            .with_str("x", INT)
            .with_str("y", STRING),
        // Lookups: test both fields exist and one doesn't
        vec![
            (ident("x").into(), Some(INT)),
            (ident("y").into(), Some(STRING)),
            (ident("nonexistent").into(), None),
        ]
    )]
    #[case::base_chain_adds_fields(
        // Stack: base + extended
        vec![
            TypeEnvironment::default()
                .with_base(ident("x").into(), INT).unwrap(),
            TypeEnvironment::default()
                .with_base(ident("y").into(), STRING).unwrap()
                .with_base(ident("z").into(), INT).unwrap(),
        ],
        // Expected: {y: string, z: int, x: int} (top-level first, then base)
        Struct::default()
            .with_str("y", STRING)
            .with_str("z", INT)
            .with_str("x", INT),
        // Lookups: test all three leaf fields and one not found
        vec![
            (ident("x").into(), Some(INT)),
            (ident("y").into(), Some(STRING)),
            (ident("z").into(), Some(INT)),
            (ident("nonexistent").into(), None),
        ]
    )]
    #[case::base_chain_reconstructs_struct(
        // Stack: base has x.y, extended adds x.z and a
        vec![
            TypeEnvironment::default()
                .with_base(ident("x").dot("y").into(), INT).unwrap(),
            TypeEnvironment::default()
                .with_base(ident("x").dot("z").into(), STRING).unwrap()
                .with_base(ident("a").into(), INT).unwrap(),
        ],
        // Expected: {x: {z: string, y: int}, a: int}
        // Note: order is top-level (z) then base (y)
        Struct::default()
            .with_str("x", Struct::default()
                .with_str("z", STRING)
                .with_str("y", INT)
                .into())
            .with_str("a", INT),
        // Lookups: test leaves (x.y, x.z, a), intermediate struct (x), and not found
        vec![
            (ident("x").dot("y").into(), Some(INT)),
            (ident("x").dot("z").into(), Some(STRING)),
            (ident("x").into(), Some(Type::Struct(Struct::default()
                .with_str("z", STRING)
                .with_str("y", INT)))),
            (ident("a").into(), Some(INT)),
            (ident("b").into(), None),
        ]
    )]
    #[case::with_tombstone(
        // Stack: base has x, y, z; extended drops y and adds a
        vec![
            TypeEnvironment::default()
                .with_base(ident("x").into(), INT).unwrap()
                .with_base(ident("y").into(), STRING).unwrap()
                .with_base(ident("z").into(), INT).unwrap(),
            TypeEnvironment::default()
                .without(ident("y").into()).unwrap()
                .with_base(ident("a").into(), INT).unwrap(),
        ],
        // Expected: {a: int, x: int, z: int} (top-level a, then base x, z; y is tombstoned)
        Struct::default()
            .with_str("a", INT)
            .with_str("x", INT)
            .with_str("z", INT),
        // Lookups: test existing fields (x, z, a), tombstoned field (y returns None), not found
        vec![
            (ident("x").into(), Some(INT)),
            (ident("z").into(), Some(INT)),
            (ident("a").into(), Some(INT)),
            (ident("y").into(), None),  // tombstoned
            (ident("nonexistent").into(), None),
        ]
    )]
    #[case::tombstone_struct_prefix(
        // Stack: base has x.y.z, x.y.a, x.b, w; extended drops x.y and adds c
        vec![
            TypeEnvironment::default()
                .with_base(ident("x").dot("y").dot("z").into(), INT).unwrap()
                .with_base(ident("x").dot("y").dot("a").into(), STRING).unwrap()
                .with_base(ident("x").dot("b").into(), INT).unwrap()
                .with_base(ident("w").into(), INT).unwrap(),
            TypeEnvironment::default()
                .without(ident("x").dot("y").into()).unwrap()
                .with_base(ident("c").into(), INT).unwrap(),
        ],
        // Expected: {c: int, x: {b: int}, w: int} (top-level c first, then base x, w; x.y.z and x.y.a are tombstoned)
        Struct::default()
            .with_str("c", INT)
            .with_str("x", Struct::default().with_str("b", INT).into())
            .with_str("w", INT),
        // Lookups: test existing leaves (c, w, x.b), intermediate struct (x), tombstoned prefix (x.y, x.y.z, x.y.a)
        vec![
            (ident("c").into(), Some(INT)),
            (ident("w").into(), Some(INT)),
            (ident("x").dot("b").into(), Some(INT)),
            (ident("x").into(), Some(Type::Struct(Struct::default().with_str("b", INT)))),
            (ident("x").dot("y").into(), None),  // tombstoned prefix
            (ident("x").dot("y").dot("z").into(), None),  // tombstoned child
            (ident("x").dot("y").dot("a").into(), None),  // tombstoned child
        ]
    )]
    #[case::three_level_chain(
        // Stack: three levels building up x.{a,b,c} and y, z, w
        vec![
            TypeEnvironment::default()
                .with_base(ident("x").dot("a").into(), INT).unwrap()
                .with_base(ident("y").into(), STRING).unwrap(),
            TypeEnvironment::default()
                .with_base(ident("x").dot("b").into(), INT).unwrap()
                .with_base(ident("z").into(), INT).unwrap(),
            TypeEnvironment::default()
                .with_base(ident("x").dot("c").into(), STRING).unwrap()
                .with_base(ident("w").into(), INT).unwrap(),
        ],
        // Expected: {x: {c: string, b: int, a: int}, w: int, z: int, y: string}
        // Note: fields in top-to-bottom order - level 3 (x.c, w), level 2 (x.b, z), level 1 (x.a, y)
        Struct::default()
            .with_str("x", Struct::default()
                .with_str("c", STRING)
                .with_str("b", INT)
                .with_str("a", INT)
                .into())
            .with_str("w", INT)
            .with_str("z", INT)
            .with_str("y", STRING),
        // Lookups: test all leaves (x.a, x.b, x.c, w, z, y), intermediate struct (x), not found
        vec![
            (ident("x").dot("a").into(), Some(INT)),
            (ident("x").dot("b").into(), Some(INT)),
            (ident("x").dot("c").into(), Some(STRING)),
            (ident("x").into(), Some(Type::Struct(Struct::default()
                .with_str("c", STRING)
                .with_str("b", INT)
                .with_str("a", INT)))),
            (ident("w").into(), Some(INT)),
            (ident("z").into(), Some(INT)),
            (ident("y").into(), Some(STRING)),
            (ident("nonexistent").into(), None),
        ]
    )]
    #[case::shadowing(
        // Stack: base has x: int, y: string; extended shadows x with string
        vec![
            TypeEnvironment::default()
                .with_base(ident("x").into(), INT).unwrap()
                .with_base(ident("y").into(), STRING).unwrap(),
            TypeEnvironment::default()
                .with_base(ident("x").into(), STRING).unwrap(),
        ],
        // Expected: {x: string, y: string} (x is shadowed)
        Struct::default()
            .with_str("x", STRING)
            .with_str("y", STRING),
        // Lookups: test shadowed x returns string (not int), y unchanged, not found
        vec![
            (ident("x").into(), Some(STRING)),  // shadowed value
            (ident("y").into(), Some(STRING)),
            (ident("z").into(), None),
        ]
    )]
    #[case::prefix_shadowing(
        // Base has x.y.z, x.y.a, x.b; extended adds x.y (shadows x.y.z and x.y.a)
        vec![
            TypeEnvironment::default()
                .with_base(ident("x").dot("y").dot("z").into(), INT).unwrap()
                .with_base(ident("x").dot("y").dot("a").into(), INT).unwrap()
                .with_base(ident("x").dot("b").into(), INT).unwrap(),
            TypeEnvironment::default()
                .with_base(ident("x").dot("y").into(), INT).unwrap(),
        ],
        // Expected: {x: {y: int, b: int}} (x.y shadows x.y.z and x.y.a)
        Struct::default()
            .with_str("x", Struct::default()
                .with_str("y", INT)
                .with_str("b", INT)
                .into()),
        // Lookups: test shadowing x.y (now int), shadowed children (x.y.z, x.y.a return None), x.b still visible, intermediate struct x
        vec![
            (ident("x").dot("y").into(), Some(INT)),  // shadowed to int
            (ident("x").dot("b").into(), Some(INT)),
            (ident("x").into(), Some(Type::Struct(Struct::default()
                .with_str("y", INT)
                .with_str("b", INT)))),
            (ident("x").dot("y").dot("z").into(), None),  // shadowed
            (ident("x").dot("y").dot("a").into(), None),  // shadowed
        ]
    )]
    #[case::three_level_middle_tombstone_complete(
        // env1 has x.y.z, env2 tombstones x.y, env3 adds a
        vec![
            TypeEnvironment::default()
                .with_base(ident("x").dot("y").dot("z").into(), INT).unwrap(),
            TypeEnvironment::default()
                .without(ident("x").dot("y").into()).unwrap(),
            TypeEnvironment::default()
                .with_base(ident("a").into(), INT).unwrap(),
        ],
        // Expected: {a: int} (entire x branch gone due to middle tombstone)
        Struct::default()
            .with_str("a", INT),
        // Lookups: test existing a, tombstoned paths (x.y.z, x.y, x), not found
        vec![
            (ident("a").into(), Some(INT)),
            (ident("x").dot("y").dot("z").into(), None),  // tombstoned
            (ident("x").dot("y").into(), None),  // tombstoned
            (ident("x").into(), None),  // entire x branch gone
            (ident("nonexistent").into(), None),
        ]
    )]
    #[case::three_level_middle_tombstone_partial(
        // env1 has x.y.z, x.a.b; env2 tombstones x.y; env3 adds c
        vec![
            TypeEnvironment::default()
                .with_base(ident("x").dot("y").dot("z").into(), INT).unwrap()
                .with_base(ident("x").dot("a").dot("b").into(), INT).unwrap(),
            TypeEnvironment::default()
                .without(ident("x").dot("y").into()).unwrap(),
            TypeEnvironment::default()
                .with_base(ident("c").into(), INT).unwrap(),
        ],
        // Expected: {c: int, x: {a: {b: int}}} (only y branch removed, a branch remains)
        Struct::default()
            .with_str("c", INT)
            .with_str("x", Struct::default()
                .with_str("a", Struct::default()
                    .with_str("b", INT)
                    .into())
                .into()),
        // Lookups: test existing leaves (c, x.a.b), intermediate structs (x, x.a), tombstoned branch (x.y, x.y.z)
        vec![
            (ident("c").into(), Some(INT)),
            (ident("x").dot("a").dot("b").into(), Some(INT)),
            (ident("x").dot("a").into(), Some(Type::Struct(Struct::default()
                .with_str("b", INT)))),
            (ident("x").into(), Some(Type::Struct(Struct::default()
                .with_str("a", Struct::default()
                    .with_str("b", INT)
                    .into())))),
            (ident("x").dot("y").into(), None),  // tombstoned
            (ident("x").dot("y").dot("z").into(), None),  // tombstoned
        ]
    )]
    #[case::deep_nesting_four_levels(
        // env1 has x.y.z.a (4 levels), env2 tombstones x.y, env3 adds b
        vec![
            TypeEnvironment::default()
                .with_base(ident("x").dot("y").dot("z").dot("a").into(), INT).unwrap(),
            TypeEnvironment::default()
                .without(ident("x").dot("y").into()).unwrap(),
            TypeEnvironment::default()
                .with_base(ident("b").into(), INT).unwrap(),
        ],
        // Expected: {b: int} (x.y.z.a filtered by middle tombstone at x.y)
        Struct::default()
            .with_str("b", INT),
        // Lookups: test existing b, tombstoned deep path (x.y.z.a, x.y.z, x.y, x)
        vec![
            (ident("b").into(), Some(INT)),
            (ident("x").dot("y").dot("z").dot("a").into(), None),  // tombstoned
            (ident("x").dot("y").dot("z").into(), None),  // tombstoned
            (ident("x").dot("y").into(), None),  // tombstoned
            (ident("x").into(), None),  // entire x branch gone
        ]
    )]
    #[case::four_level_chain_mixed_ops(
        // Four-level environment chain with mixed operations
        // env1: x.a, y.b
        // env2: x.c, z
        // env3: tombstone y.b
        // env4: x.d, w
        vec![
            TypeEnvironment::default()
                .with_base(ident("x").dot("a").into(), INT).unwrap()
                .with_base(ident("y").dot("b").into(), STRING).unwrap(),
            TypeEnvironment::default()
                .with_base(ident("x").dot("c").into(), INT).unwrap()
                .with_base(ident("z").into(), INT).unwrap(),
            TypeEnvironment::default()
                .without(ident("y").dot("b").into()).unwrap(),
            TypeEnvironment::default()
                .with_base(ident("x").dot("d").into(), INT).unwrap()
                .with_base(ident("w").into(), STRING).unwrap(),
        ],
        // Expected: {x: {d: int, c: int, a: int}, w: string, z: int}
        // Note: y.b is tombstoned, x fields accumulate across levels, order is top-to-bottom
        Struct::default()
            .with_str("x", Struct::default()
                .with_str("d", INT)
                .with_str("c", INT)
                .with_str("a", INT)
                .into())
            .with_str("w", STRING)
            .with_str("z", INT),
        // Lookups: test all leaves (x.a, x.c, x.d, z, w), intermediate struct x, tombstoned y.b, not found y
        vec![
            (ident("x").dot("a").into(), Some(INT)),
            (ident("x").dot("c").into(), Some(INT)),
            (ident("x").dot("d").into(), Some(INT)),
            (ident("x").into(), Some(Type::Struct(Struct::default()
                .with_str("d", INT)
                .with_str("c", INT)
                .with_str("a", INT)))),
            (ident("z").into(), Some(INT)),
            (ident("w").into(), Some(STRING)),
            (ident("y").dot("b").into(), None),  // tombstoned
            (ident("y").into(), None),  // entire y branch gone
        ]
    )]
    #[case::multiple_tombstones_different_levels(
        // Multiple tombstones at different levels
        // env1: x.y.z, x.a.b, w
        // env2: tombstone x.y
        // env3: adds m
        // env4: tombstone x.a
        vec![
            TypeEnvironment::default()
                .with_base(ident("x").dot("y").dot("z").into(), INT).unwrap()
                .with_base(ident("x").dot("a").dot("b").into(), INT).unwrap()
                .with_base(ident("w").into(), STRING).unwrap(),
            TypeEnvironment::default()
                .without(ident("x").dot("y").into()).unwrap(),
            TypeEnvironment::default()
                .with_base(ident("m").into(), INT).unwrap(),
            TypeEnvironment::default()
                .without(ident("x").dot("a").into()).unwrap(),
        ],
        // Expected: {m: int, w: string} (both x.y and x.a tombstoned, so entire x branch gone)
        Struct::default()
            .with_str("m", INT)
            .with_str("w", STRING),
        // Lookups: test existing (m, w), multiple tombstoned paths (x.y.z, x.y, x.a.b, x.a, x)
        vec![
            (ident("m").into(), Some(INT)),
            (ident("w").into(), Some(STRING)),
            (ident("x").dot("y").dot("z").into(), None),  // tombstoned
            (ident("x").dot("y").into(), None),  // tombstoned
            (ident("x").dot("a").dot("b").into(), None),  // tombstoned
            (ident("x").dot("a").into(), None),  // tombstoned
            (ident("x").into(), None),  // entire x branch gone
        ]
    )]
    #[case::tombstone_then_reshadow(
        // Tombstone then re-add (tombstone + shadowing combined)
        // env1: x.y.z
        // env2: tombstone x.y
        // env3: re-adds x.y (shadows the tombstone and x.y.z)
        vec![
            TypeEnvironment::default()
                .with_base(ident("x").dot("y").dot("z").into(), INT).unwrap(),
            TypeEnvironment::default()
                .without(ident("x").dot("y").into()).unwrap(),
            TypeEnvironment::default()
                .with_base(ident("x").dot("y").into(), STRING).unwrap(),
        ],
        // Expected: {x: {y: string}} (x.y re-added at top level, shadows tombstone and original x.y.z)
        Struct::default()
            .with_str("x", Struct::default()
                .with_str("y", STRING)
                .into()),
        // Lookups: test re-added x.y (now string), intermediate struct x, shadowed original x.y.z
        vec![
            (ident("x").dot("y").into(), Some(STRING)),  // re-added as string
            (ident("x").into(), Some(Type::Struct(Struct::default()
                .with_str("y", STRING)))),
            (ident("x").dot("y").dot("z").into(), None),  // shadowed by x.y
        ]
    )]
    #[case::very_deep_nesting_six_levels(
        // Very deep nesting (6 levels) with partial tombstone
        // env1: x.y.z.a.b.c (6 levels)
        // env2: tombstone x.y.z
        // env3: adds d
        vec![
            TypeEnvironment::default()
                .with_base(
                    ident("x").dot("y").dot("z").dot("a").dot("b").dot("c").into(),
                    INT
                ).unwrap(),
            TypeEnvironment::default()
                .without(ident("x").dot("y").dot("z").into()).unwrap(),
            TypeEnvironment::default()
                .with_base(ident("d").into(), STRING).unwrap(),
        ],
        // Expected: {d: string} (entire x.y.z.a.b.c filtered by tombstone at x.y.z)
        Struct::default()
            .with_str("d", STRING),
        // Lookups: test existing d, tombstoned very deep path and all intermediate levels
        vec![
            (ident("d").into(), Some(STRING)),
            (ident("x").dot("y").dot("z").dot("a").dot("b").dot("c").into(), None),  // tombstoned
            (ident("x").dot("y").dot("z").dot("a").dot("b").into(), None),  // tombstoned
            (ident("x").dot("y").dot("z").dot("a").into(), None),  // tombstoned
            (ident("x").dot("y").dot("z").into(), None),  // tombstoned
            (ident("x").dot("y").into(), None),  // tombstoned
            (ident("x").into(), None),  // entire x branch gone
        ]
    )]
    fn test_env_bindings(
        #[case] stack: Vec<TypeEnvironment>,
        #[case] expected_flatten: Struct,
        #[case] expected_lookups: Vec<(Identifier, Option<Type>)>,
    ) {
        let env = stack
            .into_iter()
            .reduce(|l, r| r.with_single_parent(Rc::new(l)))
            .unwrap();

        // Check flatten output
        let flatten_result = env.flatten();
        assert_eq!(flatten_result, expected_flatten, "Flatten output mismatch");

        // Check lookup for various paths
        for (lookup_id, expected_type) in expected_lookups {
            let result = env.lookup(&lookup_id);
            assert_eq!(
                result.as_ref().map(|t| t.as_ref()),
                expected_type.as_ref(),
                "Lookup mismatch for {:?}",
                lookup_id
            );
        }
    }

    #[rstest]
    // Simple identifier - no prefixes to check
    #[case::simple_identifier(
        TypeEnvironment::default(),
        ident("x").into(),
        Ok(None)
    )]
    // Compound where parent is from struct literal (no direct binding)
    #[case::struct_literal_parent_clean(
        TypeEnvironment::default()
            .with_base(ident("x").dot("a").into(), INT).unwrap()
            .with_base(ident("x").dot("b").into(), STRING).unwrap(),
        ident("x").dot("c").into(),
        Ok(None)
    )]
    // Compound where parent has direct struct binding
    #[case::non_splittable_parent_has_struct(
        TypeEnvironment::default()
            .with_base(ident("x").into(), Type::Struct(
                Struct::default()
                    .with_str("a", INT)
                    .with_str("b", STRING)
            )).unwrap(),
        ident("x").dot("c").into(),
        Ok(Some((
            ident("x").into(),
            Struct::default()
                .with_str("a", INT)
                .with_str("b", STRING)
        )))
    )]
    // Nested: x.y.z where x.y has struct binding
    #[case::nested_parent_has_struct(
        TypeEnvironment::default()
            .with_base(ident("x").dot("y").into(), Type::Struct(
                Struct::default().with_str("a", INT)
            )).unwrap(),
        ident("x").dot("y").dot("z").into(),
        Ok(Some((
            ident("x").dot("y").into(),
            Struct::default().with_str("a", INT)
        )))
    )]
    // Error case: parent has non-struct binding
    #[case::parent_is_non_struct_error(
        TypeEnvironment::default()
            .with_base(ident("x").into(), INT).unwrap(),
        ident("x").dot("y").into(),
        Err(())  // Just check that it errors
    )]
    // After desugaring: parent has children (passthrough shadows parent's direct binding)
    // No explicit tombstone needed - the children create a passthrough that shadows
    #[case::desugared_parent_with_children(
        {
            let base = TypeEnvironment::default()
                .with_base(ident("x").into(), Type::Struct(
                    Struct::default()
                        .with_str("a", INT)
                        .with_str("b", STRING)
                )).unwrap();
            let mut child = TypeEnvironment::new(Rc::new(base));
            // Don't need to drop x - binding children creates passthrough that shadows
            child.bind_base(ident("x").dot("a").into(), INT).unwrap();
            child.bind_base(ident("x").dot("b").into(), STRING).unwrap();
            child.bind_base(ident("x").dot("c").into(), INT).unwrap();
            child
        },
        ident("x").dot("d").into(),
        Ok(None)  // x is passthrough (has children), so it's clean
    )]
    fn test_lookup_struct(
        #[case] env: TypeEnvironment,
        #[case] id: Identifier,
        #[case] expected: Result<Option<(Identifier, Struct)>, ()>,
    ) {
        let result = env.lookup_struct(&id);

        match expected {
            Ok(expected_val) => {
                assert!(result.is_ok(), "Expected Ok, got Err: {:?}", result);
                assert_eq!(result.unwrap(), expected_val);
            }
            Err(_) => {
                assert!(result.is_err(), "Expected Err, got Ok: {:?}", result);
            }
        }
    }

    #[test]
    fn test_conflict_error_when_binding_prefix_after_children() {
        // Test that binding a prefix after children exist fails
        let mut env = TypeEnvironment::default();

        // Bind x.y: int and x.z: string
        env.bind_base(ident("x").dot("y").into(), INT).unwrap();
        env.bind_base(ident("x").dot("z").into(), STRING).unwrap();

        // Try to bind x: bool (should conflict - x already has children)
        let result = env.bind_base(ident("x").into(), BOOLEAN);

        assert!(result.is_err(), "Expected conflict error");
        let err = result.unwrap_err();

        // Verify it's a FieldNameConflict
        match err {
            TypeEnvironmentError::FieldNameConflict { ident } => {
                assert_eq!(ident, "x");
            }
            other => panic!("Expected FieldNameConflict, got: {:?}", other),
        }
    }

    #[test]
    fn test_cannot_drop_present_binding_in_same_env() {
        // Bind x: int, then try to drop x in the same environment
        let mut env = TypeEnvironment::default();
        env.bind_base(ident("x").into(), INT).unwrap();

        // Dropping x should fail - can't drop a Present binding in the same env
        let result = env.drop(&ident("x").into());

        assert!(
            result.is_err(),
            "Expected error when dropping Present binding"
        );
        match result.unwrap_err() {
            TypeEnvironmentError::FieldNameConflict { ident } => {
                assert_eq!(ident, "x");
            }
            other => panic!("Expected FieldNameConflict, got: {:?}", other),
        }
    }

    #[test]
    fn test_cannot_drop_same_identifier_twice() {
        // Drop x, then try to drop x again in the same environment
        let mut env = TypeEnvironment::default();
        env.drop(&ident("x").into()).unwrap();

        // Dropping x again should fail - duplicate tombstone
        let result = env.drop(&ident("x").into());

        assert!(
            result.is_err(),
            "Expected error when dropping same identifier twice"
        );
        match result.unwrap_err() {
            TypeEnvironmentError::FieldNameConflict { ident } => {
                assert_eq!(ident, "x");
            }
            other => panic!("Expected FieldNameConflict, got: {:?}", other),
        }
    }
}
