hamelin_lib 0.10.13

use super::expression::{Expression, ExpressionKind};
use crate::{
    antlr::{
        hamelinparser::{IdentifierContextAll, IdentifierContextAttrs, SimpleIdentifierContextAll},
        interval,
    },
    antlr::{parse_identifier, parse_simple_identifier},
    err::TranslationError,
    tree::ast::context::{FromCst, ParseContext},
};
use antlr_rust::tree::ParseTree;
use derive_more::derive::{From, TryUnwrap};
use serde::{Deserialize, Serialize};
use std::{
    fmt::{Display, Formatter},
    hash::{Hash, Hasher},
    ops::{Add, RangeInclusive},
    rc::Rc,
    str::FromStr,
    sync::Arc,
};

use super::node::{Span, Spannable};

/// A pure AST identifier that is either simple or compound (no errors)
#[derive(Debug, Clone, PartialEq, From, TryUnwrap, Hash, Eq)]
pub enum Identifier {
    Simple(SimpleIdentifier),
    Compound(CompoundIdentifier),
}

/// A parsed identifier that may contain an error from CST conversion
#[derive(Debug, Clone, PartialEq, From, TryUnwrap, Hash, Eq)]
pub enum ParsedIdentifier {
    Valid(Identifier),
    Error(Arc<TranslationError>),
}

/// A parsed simple identifier that may contain an error from CST conversion
#[derive(Debug, Clone, PartialEq, From, TryUnwrap, Hash, Eq)]
pub enum ParsedSimpleIdentifier {
    Valid(SimpleIdentifier),
    Error(Arc<TranslationError>),
}

/// Iterator over all strict prefixes of a compound identifier.
/// For `x.y.z`, yields `x`, then `x.y`.
pub struct IdentifierPrefixes<'a> {
    parts: &'a [SimpleIdentifier],
    current_len: usize,
}

impl<'a> Iterator for IdentifierPrefixes<'a> {
    type Item = Identifier;

    fn next(&mut self) -> Option<Self::Item> {
        // Stop when we've yielded all strict prefixes (not including the full identifier)
        if self.current_len >= self.parts.len() {
            return None;
        }

        let prefix = if self.current_len == 1 {
            // Single part - return as Simple
            Identifier::Simple(self.parts[0].clone())
        } else {
            // Multiple parts - return as Compound
            Identifier::Compound(CompoundIdentifier {
                parts: self.parts[0..self.current_len].to_vec(),
            })
        };

        self.current_len += 1;
        Some(prefix)
    }
}

impl Spannable for Identifier {
    fn span(&self) -> Option<RangeInclusive<usize>> {
        match self {
            Identifier::Simple(s) => s.span(),
            Identifier::Compound(c) => c.span(),
        }
    }
}

impl Display for Identifier {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        match self {
            Identifier::Simple(s) => write!(f, "{}", s),
            Identifier::Compound(c) => write!(f, "{}", c),
        }
    }
}

impl Serialize for Identifier {
    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
        match self {
            Self::Simple(s) => serializer.serialize_str(&s.to_string()),
            Self::Compound(c) => serializer.serialize_str(&c.to_string()),
        }
    }
}

impl<'de> Deserialize<'de> for Identifier {
    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
        let s = String::deserialize(deserializer)?;
        if s.is_empty() {
            return Err(serde::de::Error::custom("empty identifier"));
        }
        Identifier::parse(&s).map_err(serde::de::Error::custom)
    }
}

impl FromCst<Rc<IdentifierContextAll<'static>>> for ParsedIdentifier {
    fn from_cst_with_context(
        cst: Rc<IdentifierContextAll<'static>>,
        ctx: &mut ParseContext,
    ) -> Self {
        // Parse all simple identifiers, short-circuit on first error
        let simple_idents: Vec<SimpleIdentifier> = match cst
            .simpleIdentifier_all()
            .into_iter()
            .map(|si| ParsedSimpleIdentifier::from_cst_with_context(si.as_ref(), ctx))
            .try_fold(Vec::new(), |mut acc, parsed| {
                parsed.valid().map(|si| {
                    acc.push(si);
                    acc
                })
            }) {
            Ok(idents) => idents,
            Err(e) => {
                ctx.add_error(e.clone());
                return e.into();
            }
        };

        // All parts are valid, build the identifier
        match simple_idents.as_slice() {
            [] => {
                let err = ctx.error("expected identifier").at(cst.as_ref()).emit();
                err.into()
            }
            [single] => Identifier::Simple(single.clone()).into(),
            [first, second, rest @ ..] => {
                CompoundIdentifier::new(first.clone(), second.clone(), rest.to_vec()).into()
            }
        }
    }
}

impl ParsedSimpleIdentifier {
    /// Extract a reference to the valid SimpleIdentifier or return the error
    pub fn valid_ref(&self) -> Result<&SimpleIdentifier, Arc<TranslationError>> {
        match self {
            ParsedSimpleIdentifier::Valid(si) => Ok(si),
            ParsedSimpleIdentifier::Error(err) => Err(err.clone()),
        }
    }

    /// Consume and extract the valid SimpleIdentifier or return the error
    pub fn valid(self) -> Result<SimpleIdentifier, Arc<TranslationError>> {
        match self {
            ParsedSimpleIdentifier::Valid(si) => Ok(si),
            ParsedSimpleIdentifier::Error(err) => Err(err),
        }
    }
}

impl ParsedIdentifier {
    /// Extract a reference to the valid Identifier or return the error
    pub fn valid_ref(&self) -> Result<&Identifier, Arc<TranslationError>> {
        match self {
            ParsedIdentifier::Valid(id) => Ok(id),
            ParsedIdentifier::Error(err) => Err(err.clone()),
        }
    }

    /// Consume and extract the valid Identifier or return the error
    pub fn valid(self) -> Result<Identifier, Arc<TranslationError>> {
        match self {
            ParsedIdentifier::Valid(id) => Ok(id),
            ParsedIdentifier::Error(err) => Err(err),
        }
    }
}

impl Display for ParsedIdentifier {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        self.valid_ref()
            .map(|id| write!(f, "{}", id))
            .unwrap_or_else(|_| write!(f, "<error>"))
    }
}

impl Spannable for ParsedIdentifier {
    fn span(&self) -> Option<RangeInclusive<usize>> {
        self.valid_ref().ok().and_then(|id| id.span())
    }
}

impl Display for ParsedSimpleIdentifier {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        self.valid_ref()
            .map(|id| write!(f, "{}", id))
            .unwrap_or_else(|_| write!(f, "<error>"))
    }
}

impl Spannable for ParsedSimpleIdentifier {
    fn span(&self) -> Option<RangeInclusive<usize>> {
        self.valid_ref().ok().and_then(|id| id.span())
    }
}

// Conversions from Identifier components to ParsedIdentifier
impl From<SimpleIdentifier> for ParsedIdentifier {
    fn from(si: SimpleIdentifier) -> Self {
        ParsedIdentifier::Valid(Identifier::Simple(si))
    }
}

impl From<CompoundIdentifier> for ParsedIdentifier {
    fn from(ci: CompoundIdentifier) -> Self {
        ParsedIdentifier::Valid(Identifier::Compound(ci))
    }
}

impl From<ParsedSimpleIdentifier> for ParsedIdentifier {
    fn from(value: ParsedSimpleIdentifier) -> Self {
        match value {
            ParsedSimpleIdentifier::Valid(si) => ParsedIdentifier::Valid(Identifier::Simple(si)),
            ParsedSimpleIdentifier::Error(err) => ParsedIdentifier::Error(err),
        }
    }
}

impl Identifier {
    pub fn parse(s: impl Into<String>) -> Result<Self, TranslationError> {
        let mut ctx = ParseContext::new();
        let cst = parse_identifier(s.into()).map_err(|errors| {
            errors
                .0
                .into_iter()
                .next()
                .unwrap_or_else(|| ctx.error("cannot parse identifier").emit().as_ref().clone())
        })?;
        match ParsedIdentifier::from_cst_with_context(cst, &mut ctx) {
            ParsedIdentifier::Valid(id) => Ok(id),
            ParsedIdentifier::Error(err) => Err((*err).clone()),
        }
    }

    /// Attempt to infer an identifier from an expression's AST structure.
    /// Returns None if the expression doesn't have an inferable identifier
    /// (caller should fall back to source text).
    ///
    /// This is used during CST→AST parsing to desugar bare expressions into
    /// assignments by inferring the field name from the expression structure.
    pub fn infer_from_expression(expr: &Expression) -> Option<ParsedIdentifier> {
        // First, check if we can strip off one wrapper operation
        let current = match &expr.kind {
            // Zero-arg function call: use the function name as identifier
            ExpressionKind::FunctionCall(func_call)
                if func_call.positional_args.is_empty() && func_call.named_args.is_empty() =>
            {
                return Some(match func_call.name.valid_ref() {
                    Ok(simple_id) => SimpleIdentifier::with_arc_name(simple_id.name.clone()).into(),
                    Err(err) => err.into(),
                });
            }
            // Timestamp truncation: unwrap to inner expression
            ExpressionKind::TsTrunc(tstrunc) => tstrunc.expression.as_ref(),
            // Cast: unwrap to inner expression
            ExpressionKind::Cast(cast) => cast.expression.as_ref(),
            // No wrapper to strip
            _ => expr,
        };

        // Collect field lookup chain by walking inward
        let mut fields = Vec::new();
        let mut inner = current;
        while let ExpressionKind::FieldLookup(field_lookup) = &inner.kind {
            fields.push(field_lookup.field_identifier.clone());
            inner = field_lookup.value.as_ref();
        }

        // Must be a field reference at the core
        match &inner.kind {
            ExpressionKind::FieldReference(col_ref) => {
                // Reverse fields since we collected them outside-in
                fields.reverse();
                match col_ref.field_name.valid_ref() {
                    Ok(field_name) => {
                        if fields.is_empty() {
                            // Just a field reference with no field lookup
                            Some(SimpleIdentifier::with_arc_name(field_name.name.clone()).into())
                        } else {
                            // Build compound identifier: base field + all lookups
                            let mut parts =
                                vec![SimpleIdentifier::with_arc_name(field_name.name.clone())];
                            for field in fields {
                                match field.valid() {
                                    Ok(simple_id) => parts.push(simple_id),
                                    Err(err) => return Some(err.into()),
                                }
                            }
                            Some(CompoundIdentifier { parts }.into())
                        }
                    }
                    Err(err) => Some(err.into()),
                }
            }
            _ => None, // Cannot infer - caller should use source text fallback
        }
    }

    /// Returns the first component of this identifier.
    pub fn first(&self) -> SimpleIdentifier {
        match self {
            Identifier::Simple(s) => s.first(),
            Identifier::Compound(c) => c.first(),
        }
    }

    /// Returns an iterator over all strict prefixes of this identifier.
    /// For example, `x.y.z` yields `x`, then `x.y`.
    /// Simple identifiers have no prefixes and return an empty iterator.
    pub fn prefixes(&self) -> IdentifierPrefixes<'_> {
        IdentifierPrefixes {
            parts: match self {
                Identifier::Compound(c) => &c.parts,
                _ => &[],
            },
            current_len: 1,
        }
    }

    /// Returns the rest of this identifier after removing the first component.
    /// Manually dispatches to the concrete type implementations.
    pub fn rest(&self) -> Option<Identifier> {
        match self {
            Identifier::Simple(s) => s.rest(),
            Identifier::Compound(c) => Some(c.rest()),
        }
    }

    /// Returns the last component of this identifier.
    pub fn last(&self) -> SimpleIdentifier {
        match self {
            Identifier::Simple(s) => s.last(),
            Identifier::Compound(c) => c.last(),
        }
    }

    /// Check if this identifier has the given prefix (without doing the stripping work).
    /// Returns true if `prefix` is a strict prefix of `self`.
    /// Returns false if they are equal or if prefix doesn't match.
    pub fn has_prefix(&self, prefix: &Identifier) -> bool {
        match self {
            Identifier::Simple(s) => s.has_prefix(prefix),
            Identifier::Compound(c) => c.has_prefix(prefix),
        }
    }

    /// Strip a prefix from this identifier, returning the suffix.
    /// Manually dispatches to the concrete type implementations.
    pub fn strip_prefix(&self, prefix: &Identifier) -> Option<Identifier> {
        match self {
            Identifier::Simple(s) => s.strip_prefix(prefix),
            Identifier::Compound(c) => c.strip_prefix(prefix),
        }
    }

    /// Returns a slice of SimpleIdentifier references for each segment of this identifier.
    /// For simple identifiers, returns a single-element slice.
    /// For compound identifiers, returns a slice of all parts.
    pub fn segments(&self) -> &[SimpleIdentifier] {
        match self {
            Identifier::Simple(s) => std::slice::from_ref(s),
            Identifier::Compound(c) => &c.parts,
        }
    }

    /// Build an identifier from a vec of segments.
    /// Returns `None` for empty, `Simple` for one, `Compound` for 2+.
    pub fn from_segments(segments: Vec<SimpleIdentifier>) -> Option<Identifier> {
        match segments.as_slice() {
            [] => None,
            [single] => Some(single.clone().into()),
            [first, second, rest @ ..] => {
                Some(CompoundIdentifier::new(first.clone(), second.clone(), rest.to_vec()).into())
            }
        }
    }

    /// Prepend a prefix identifier to this identifier, producing a compound identifier.
    pub fn prepend(self, prefix: Identifier) -> CompoundIdentifier {
        let mut parts = prefix.segments().to_vec();
        parts.extend(self.segments().iter().cloned());
        // We always have at least 2 parts (prefix has ≥1, self has ≥1)
        CompoundIdentifier { parts }
    }
}

/// A simple (unqualified) identifier
#[derive(Debug, Clone)]
pub struct SimpleIdentifier {
    pub span: Span,
    /// The identifier name, stored as Arc<str> for memory efficiency.
    /// When parsed with an interner, identical names share the same allocation.
    name: Arc<str>,
}

impl SimpleIdentifier {
    /// Create a new simple identifier without interning.
    ///
    /// This allocates a fresh `Arc<str>` for the name. For memory-efficient
    /// parsing with string deduplication, use `Pipeline::parse_with()` with
    /// an interner instead.
    pub fn new(name: impl Into<String>) -> Self {
        let s: String = name.into();
        Self {
            span: Span::NONE,
            name: Arc::from(s.as_str()),
        }
    }

    /// Create a simple identifier with a pre-existing `Arc<str>` name.
    ///
    /// This is used internally when we already have an interned or shared
    /// string and want to preserve the sharing.
    pub(crate) fn with_arc_name(name: Arc<str>) -> Self {
        Self {
            span: Span::NONE,
            name,
        }
    }

    /// Get the name as a string slice.
    pub fn as_str(&self) -> &str {
        &self.name
    }

    /// Get the name as a string slice.
    ///
    /// This is an ergonomic alias for `as_str()` that mirrors the field-access
    /// style of the old `pub name: String` field, easing the migration from
    /// `ident.name` to `ident.name()`.
    pub fn name(&self) -> &str {
        &self.name
    }

    /// Check if this identifier can be represented as an unquoted Hamelin identifier.
    ///
    /// Returns `true` if the name round-trips through the Hamelin parser without
    /// needing backtick quoting. This catches reserved words (like `select`, `let`)
    /// that the character-level check in `Display` would miss.
    pub fn is_clean(&self) -> bool {
        parse_simple_identifier(self.name.to_string()).is_ok()
    }
}

impl AsRef<str> for SimpleIdentifier {
    fn as_ref(&self) -> &str {
        &self.name
    }
}

impl PartialEq<str> for SimpleIdentifier {
    fn eq(&self, other: &str) -> bool {
        &*self.name == other
    }
}

impl PartialEq<&str> for SimpleIdentifier {
    fn eq(&self, other: &&str) -> bool {
        &*self.name == *other
    }
}

impl SimpleIdentifier {
    pub fn parse(s: impl Into<String>) -> Result<Self, TranslationError> {
        let mut ctx = ParseContext::new();
        match parse_simple_identifier(s.into()) {
            Ok(cst) => {
                match ParsedSimpleIdentifier::from_cst_with_context(cst.as_ref(), &mut ctx) {
                    ParsedSimpleIdentifier::Valid(identifier) => Ok(identifier),
                    ParsedSimpleIdentifier::Error(err) => Err((*err).clone()),
                }
            }
            Err(parse_errors) => {
                let err =
                    parse_errors.0.into_iter().next().unwrap_or_else(|| {
                        ctx.error("cant parse identifier").emit().as_ref().clone()
                    });
                Err(err)
            }
        }
    }
}

impl Spannable for SimpleIdentifier {
    fn span(&self) -> Option<RangeInclusive<usize>> {
        self.span.to_range()
    }
}

impl FromCst<&SimpleIdentifierContextAll<'static>> for ParsedSimpleIdentifier {
    fn from_cst_with_context(
        cst: &SimpleIdentifierContextAll<'static>,
        ctx: &mut ParseContext,
    ) -> Self {
        match cst {
            SimpleIdentifierContextAll::BackQuotedIdentifierContext(parser_ctx) => {
                let text = parser_ctx.get_text();
                match text.get(1..text.len() - 1) {
                    Some(inner) => {
                        let unescaped = inner.replace("``", "`");
                        SimpleIdentifier {
                            span: interval(parser_ctx).into(),
                            name: ctx.intern(&unescaped),
                        }
                        .into()
                    }
                    None => {
                        let err = ctx
                            .error("invalid backtick identifier")
                            .at(parser_ctx)
                            .emit();
                        err.into()
                    }
                }
            }
            SimpleIdentifierContextAll::UnquotedIdentifierContext(parser_ctx) => SimpleIdentifier {
                span: interval(parser_ctx).into(),
                name: ctx.intern(&parser_ctx.get_text()),
            }
            .into(),
            SimpleIdentifierContextAll::Error(parser_ctx) => {
                let err = ctx.error("parse_error").at(parser_ctx).emit();
                err.into()
            }
        }
    }
}

impl FromStr for Identifier {
    type Err = TranslationError;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        Self::parse(s)
    }
}

impl FromStr for SimpleIdentifier {
    type Err = TranslationError;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        Self::parse(s)
    }
}

impl From<&str> for SimpleIdentifier {
    fn from(s: &str) -> Self {
        SimpleIdentifier {
            span: Span::NONE,
            name: Arc::from(s),
        }
    }
}

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

impl Eq for SimpleIdentifier {}

impl Hash for SimpleIdentifier {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.name.hash(state);
    }
}

impl Display for SimpleIdentifier {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        if self.is_clean() {
            write!(f, "{}", self.name)
        } else {
            // Escape backticks by doubling them, then wrap in backticks
            let escaped = self.name.replace('`', "``");
            write!(f, "`{}`", escaped)
        }
    }
}

impl Serialize for SimpleIdentifier {
    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
        serializer.serialize_str(&self.to_string())
    }
}

impl<'de> Deserialize<'de> for SimpleIdentifier {
    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
        let s = String::deserialize(deserializer)?;
        SimpleIdentifier::parse(s).map_err(serde::de::Error::custom)
    }
}

impl SimpleIdentifier {
    /// Returns the simple identifier itself
    pub fn first(&self) -> SimpleIdentifier {
        self.clone()
    }

    /// Simple identifiers have no rest
    pub fn rest(&self) -> Option<Identifier> {
        None
    }

    /// Returns the simple identifier itself
    pub fn last(&self) -> SimpleIdentifier {
        self.clone()
    }

    /// Check if this simple identifier has the given prefix
    /// Always returns false since simple identifiers can't have prefixes
    pub fn has_prefix(&self, _prefix: &Identifier) -> bool {
        false
    }

    /// Strip prefix - returns None since simple identifiers can't have prefixes
    pub fn strip_prefix(&self, _prefix: &Identifier) -> Option<Identifier> {
        // Only returns None - either they're equal (not a child) or different (not a prefix)
        None
    }

    /// Prepend a prefix identifier so that this identifier becomes the rightmost segment.
    ///
    /// Equivalent to [`Identifier::prepend`] on `self.into()`, but reads naturally when
    /// building paths from the outer field inward (e.g. `items.prepend(data.into())` for
    /// `data.items`).
    pub fn prepend(self, prefix: Identifier) -> CompoundIdentifier {
        let id: Identifier = self.into();
        id.prepend(prefix)
    }
}

/// A compound (qualified) identifier like `table.column` or `schema.table.column`
#[derive(Debug, Clone, PartialEq, Hash, Eq)]
pub struct CompoundIdentifier {
    parts: Vec<SimpleIdentifier>,
}

impl CompoundIdentifier {
    pub fn new(
        first: SimpleIdentifier,
        second: SimpleIdentifier,
        rest: Vec<SimpleIdentifier>,
    ) -> Self {
        let mut parts = vec![first, second];
        parts.extend(rest);
        Self { parts }
    }

    /// Create a two-part compound identifier.
    pub fn from_two(first: impl Into<String>, second: impl Into<String>) -> Self {
        Self {
            parts: vec![SimpleIdentifier::new(first), SimpleIdentifier::new(second)],
        }
    }
}

impl Spannable for CompoundIdentifier {
    fn span(&self) -> Option<RangeInclusive<usize>> {
        // Combine spans of all parts
        let first_span = self.parts.first()?.span()?;
        let last_span = self.parts.last()?.span()?;
        Some(*first_span.start()..=*last_span.end())
    }
}

impl Display for CompoundIdentifier {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        // Join parts with dots
        for (i, part) in self.parts.iter().enumerate() {
            if i > 0 {
                write!(f, ".")?;
            }
            write!(f, "{}", part)?;
        }
        Ok(())
    }
}

impl CompoundIdentifier {
    /// Returns all parts as a slice.
    pub fn parts(&self) -> &[SimpleIdentifier] {
        &self.parts
    }

    /// Consumes self and returns the parts vec.
    pub fn into_parts(self) -> Vec<SimpleIdentifier> {
        self.parts
    }

    /// Returns the parts after the first as a slice.
    ///
    /// A CompoundIdentifier always has at least 2 parts, so this always has at least 1 element.
    pub fn rest_parts(&self) -> &[SimpleIdentifier] {
        &self.parts[1..]
    }

    /// Returns the first part as a simple identifier
    pub fn first(&self) -> SimpleIdentifier {
        // CompoundIdentifier always has at least 2 parts, so this is safe
        self.parts[0].clone()
    }

    /// Returns the remaining parts after the first.
    ///
    /// A CompoundIdentifier always has at least 2 parts, so rest always has at least 1 part.
    pub fn rest(&self) -> Identifier {
        match &self.parts[1..] {
            [single] => single.clone().into(),
            parts => CompoundIdentifier {
                parts: parts.to_vec(),
            }
            .into(),
        }
    }

    /// Returns the last part as a simple identifier
    pub fn last(&self) -> SimpleIdentifier {
        // CompoundIdentifier always has at least 2 parts, so this is safe
        self.parts[self.parts.len() - 1].clone()
    }

    /// Check if this compound identifier has the given prefix
    pub fn has_prefix(&self, prefix: &Identifier) -> bool {
        match prefix {
            Identifier::Simple(prefix_simple) => {
                // Prefix is simple - check if our first part matches and we have more parts
                self.parts.len() > 1 && self.parts[0] == *prefix_simple
            }
            Identifier::Compound(prefix_compound) => {
                // Prefix is compound - check if it matches the beginning of our parts
                let prefix_len = prefix_compound.parts().len();

                // We must have more parts than the prefix for it to be a true prefix
                if self.parts.len() <= prefix_len {
                    return false;
                }

                // Check if all prefix parts match
                for i in 0..prefix_len {
                    if self.parts[i] != prefix_compound.parts()[i] {
                        return false;
                    }
                }

                true
            }
        }
    }

    /// Strip a prefix from this compound identifier
    pub fn strip_prefix(&self, prefix: &Identifier) -> Option<Identifier> {
        let mut current: Identifier = self.clone().into();
        let mut prefix_current = prefix.clone();

        // Iteratively match first components
        loop {
            let c = current.first();
            let p = prefix_current.first();

            if c == p {
                // They match - check if prefix has more parts
                match prefix_current.rest() {
                    None => {
                        // Prefix exhausted - return the rest of current
                        return current.rest();
                    }
                    Some(prefix_rest) => {
                        // Prefix has more parts - advance both
                        match current.rest() {
                            None => return None, // Current exhausted, but prefix has more
                            Some(current_rest) => {
                                current = current_rest;
                                prefix_current = prefix_rest;
                            }
                        }
                    }
                }
            } else {
                // First components don't match
                return None;
            }
        }
    }
}

// ============================================================================
// Add trait implementation - combines identifiers into compound identifiers
// ============================================================================

impl Add for Identifier {
    type Output = Identifier;

    /// Combine two identifiers into a compound identifier.
    /// This is useful for building nested field paths like `prefix + field_name`.
    fn add(self, suffix: Identifier) -> Identifier {
        suffix.prepend(self).into()
    }
}

// ============================================================================
// Conversions from SQL identifiers to tree AST identifiers
// ============================================================================

use crate::sql::expression::identifier::{
    CompoundIdentifier as SqlCompoundIdentifier, Identifier as SqlIdentifier,
    SimpleIdentifier as SqlSimpleIdentifier,
};

impl From<SqlSimpleIdentifier> for SimpleIdentifier {
    fn from(sql_ident: SqlSimpleIdentifier) -> Self {
        SimpleIdentifier::new(sql_ident.name)
    }
}

impl From<SqlCompoundIdentifier> for CompoundIdentifier {
    fn from(sql_ident: SqlCompoundIdentifier) -> Self {
        CompoundIdentifier {
            parts: sql_ident.into_vec().into_iter().map(|p| p.into()).collect(),
        }
    }
}

impl From<SqlIdentifier> for Identifier {
    fn from(sql_ident: SqlIdentifier) -> Self {
        match sql_ident {
            SqlIdentifier::Simple(simple) => Identifier::Simple(simple.into()),
            SqlIdentifier::Compound(compound) => Identifier::Compound(compound.into()),
        }
    }
}

impl From<SqlSimpleIdentifier> for Identifier {
    fn from(sql_ident: SqlSimpleIdentifier) -> Self {
        Identifier::Simple(sql_ident.into())
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{tree::builder::*, types::STRING};
    // Helper function to convert Expression to Identifier using parse-time inference
    fn identifier_from_expr(expr: &Expression) -> Identifier {
        match Identifier::infer_from_expression(expr) {
            Some(ParsedIdentifier::Valid(identifier)) => identifier,
            Some(ParsedIdentifier::Error(e)) => panic!("expected valid identifier, got {:?}", e),
            None => panic!("could not infer identifier from expression"),
        }
    }

    #[test]
    fn test_simple_identifier_creation() {
        use crate::tree::builder::identifier::ident;
        let id: Identifier = ident("test").into();
        match id {
            Identifier::Simple(simple) => {
                assert!(simple == "test");
                assert!(simple.span.is_none());
            }
            _ => panic!("Expected simple identifier"),
        }
    }

    #[test]
    fn test_compound_identifier_creation() {
        use crate::tree::builder::identifier::ident;
        let id: Identifier = ident("schema").dot("table").into();
        match id {
            Identifier::Compound(compound) => {
                assert_eq!(compound.parts().len(), 2);
                assert!(compound.parts()[0] == "schema");
                assert!(compound.parts()[1] == "table");
            }
            _ => panic!("Expected compound identifier"),
        }
    }

    #[test]
    fn test_compound_identifier_with_three_parts() {
        use crate::tree::builder::identifier::ident;
        let id: Identifier = ident("catalog").dot("schema").dot("table").into();
        match id {
            Identifier::Compound(compound) => {
                assert_eq!(compound.parts().len(), 3);
                assert!(compound.parts()[0] == "catalog");
                assert!(compound.parts()[1] == "schema");
                assert!(compound.parts()[2] == "table");
            }
            _ => panic!("Expected compound identifier"),
        }
    }

    #[test]
    fn test_identifier_from_column_reference() {
        let expr = field_ref("foo").build();
        let ident = identifier_from_expr(&expr);
        match ident {
            Identifier::Simple(s) => assert!(s == "foo"),
            _ => panic!("Expected Simple identifier"),
        }
    }

    #[test]
    fn test_identifier_from_field_access_two_levels() {
        let expr = field(field_ref("foo"), "bar").build();
        let ident = identifier_from_expr(&expr);
        match ident {
            Identifier::Compound(c) => {
                assert_eq!(c.parts.len(), 2);
                assert!(c.parts()[0] == "foo");
                assert!(c.parts()[1] == "bar");
            }
            _ => panic!("Expected Compound identifier"),
        }
    }

    #[test]
    fn test_identifier_from_field_access_three_levels() {
        let expr = field(field(field_ref("foo"), "bar"), "baz").build();
        let ident = identifier_from_expr(&expr);
        match ident {
            Identifier::Compound(c) => {
                assert_eq!(c.parts.len(), 3);
                assert!(c.parts()[0] == "foo");
                assert!(c.parts()[1] == "bar");
                assert!(c.parts()[2] == "baz");
            }
            _ => panic!("Expected Compound identifier"),
        }
    }

    #[test]
    fn test_identifier_from_zero_arg_function() {
        let expr = call("now").build();
        let ident = identifier_from_expr(&expr);
        match ident {
            Identifier::Simple(s) => assert!(s == "now"),
            _ => panic!("Expected Simple identifier from zero-arg function"),
        }
    }

    #[test]
    fn test_identifier_from_cast() {
        let expr = cast(field_ref("foo"), STRING).build();
        let ident = identifier_from_expr(&expr);
        match ident {
            Identifier::Simple(s) => assert!(s == "foo"),
            _ => panic!("Expected Simple identifier from cast"),
        }
    }

    #[test]
    fn test_identifier_from_cast_with_field_access() {
        let expr = cast(field(field_ref("foo"), "bar"), STRING).build();
        let ident = identifier_from_expr(&expr);
        match ident {
            Identifier::Compound(c) => {
                assert_eq!(c.parts.len(), 2);
                assert!(c.parts()[0] == "foo");
                assert!(c.parts()[1] == "bar");
            }
            _ => panic!("Expected Compound identifier from cast of field access"),
        }
    }

    #[test]
    fn test_identifier_first() {
        use crate::tree::builder::identifier::ident;

        // Simple identifier
        let id: Identifier = ident("x").into();
        let first = id.first();
        assert!(first == "x");

        // Compound identifier
        let id: Identifier = ident("x").dot("y").into();
        let first = id.first();
        assert!(first == "x");
    }

    #[test]
    fn test_identifier_rest() {
        use crate::tree::builder::identifier::ident;

        // Simple identifier - no rest
        let id: Identifier = ident("x").into();
        assert_eq!(id.rest(), None);

        // Compound identifier with 2 parts
        let id: Identifier = ident("x").dot("y").into();
        match id.rest() {
            Some(Identifier::Simple(s)) => assert!(s == "y"),
            _ => panic!("Expected Simple identifier"),
        }

        // Compound identifier with 3 parts
        let id: Identifier = ident("x").dot("y").dot("z").into();
        match id.rest() {
            Some(Identifier::Compound(c)) => {
                assert_eq!(c.parts.len(), 2);
                assert!(c.parts()[0] == "y");
                assert!(c.parts()[1] == "z");
            }
            _ => panic!("Expected Compound identifier"),
        }
    }

    #[test]
    fn test_identifier_last() {
        use crate::tree::builder::identifier::ident;

        // Simple identifier
        let id: Identifier = ident("x").into();
        let last = id.last();
        assert!(last == "x");

        // Compound identifier
        let id: Identifier = ident("x").dot("y").into();
        let last = id.last();
        assert!(last == "y");

        // Compound identifier with 3 parts
        let id: Identifier = ident("x").dot("y").dot("z").into();
        let last = id.last();
        assert!(last == "z");
    }

    #[test]
    fn test_identifier_has_prefix() {
        use crate::tree::builder::identifier::ident;

        // x.y.z has prefix x.y
        let id: Identifier = ident("x").dot("y").dot("z").into();
        let prefix: Identifier = ident("x").dot("y").into();
        assert!(id.has_prefix(&prefix));

        // x.y has prefix x
        let id: Identifier = ident("x").dot("y").into();
        let prefix: Identifier = ident("x").into();
        assert!(id.has_prefix(&prefix));

        // x doesn't have prefix x (equal, not a child)
        let id: Identifier = ident("x").into();
        let prefix: Identifier = ident("x").into();
        assert!(!id.has_prefix(&prefix));

        // x doesn't have prefix y (not a prefix)
        let id: Identifier = ident("x").into();
        let prefix: Identifier = ident("y").into();
        assert!(!id.has_prefix(&prefix));

        // x doesn't have prefix x.y (prefix is longer)
        let id: Identifier = ident("x").into();
        let prefix: Identifier = ident("x").dot("y").into();
        assert!(!id.has_prefix(&prefix));

        // x.y.z has prefix x
        let id: Identifier = ident("x").dot("y").dot("z").into();
        let prefix: Identifier = ident("x").into();
        assert!(id.has_prefix(&prefix));

        // x.y doesn't have prefix x.z (different branch)
        let id: Identifier = ident("x").dot("y").into();
        let prefix: Identifier = ident("x").dot("z").into();
        assert!(!id.has_prefix(&prefix));
    }

    #[test]
    fn test_identifier_strip_prefix() {
        use crate::tree::builder::identifier::ident;

        // x.y.z with prefix x.y -> z
        let id: Identifier = ident("x").dot("y").dot("z").into();
        let prefix: Identifier = ident("x").dot("y").into();
        match id.strip_prefix(&prefix) {
            Some(Identifier::Simple(s)) => assert!(s == "z"),
            _ => panic!("Expected Some(Simple(z))"),
        }

        // x.y with prefix x -> y
        let id: Identifier = ident("x").dot("y").into();
        let prefix: Identifier = ident("x").into();
        match id.strip_prefix(&prefix) {
            Some(Identifier::Simple(s)) => assert!(s == "y"),
            _ => panic!("Expected Some(Simple(y))"),
        }

        // x with prefix x -> None (equal, not a child)
        let id: Identifier = ident("x").into();
        let prefix: Identifier = ident("x").into();
        assert_eq!(id.strip_prefix(&prefix), None);

        // x with prefix y -> None (not a prefix)
        let id: Identifier = ident("x").into();
        let prefix: Identifier = ident("y").into();
        assert_eq!(id.strip_prefix(&prefix), None);

        // x with prefix x.y -> None (prefix is longer)
        let id: Identifier = ident("x").into();
        let prefix: Identifier = ident("x").dot("y").into();
        assert_eq!(id.strip_prefix(&prefix), None);
    }

    #[test]
    fn test_identifier_add() {
        use crate::tree::builder::identifier::ident;

        // Simple + Simple -> Compound
        let prefix: Identifier = ident("x").into();
        let suffix: Identifier = ident("y").into();
        let result = prefix + suffix;
        match result {
            Identifier::Compound(c) => {
                assert_eq!(c.parts.len(), 2);
                assert!(c.parts()[0] == "x");
                assert!(c.parts()[1] == "y");
            }
            _ => panic!("Expected Compound identifier"),
        }

        // Simple + Compound -> Compound
        let prefix: Identifier = ident("x").into();
        let suffix: Identifier = ident("y").dot("z").into();
        let result = prefix + suffix;
        match result {
            Identifier::Compound(c) => {
                assert_eq!(c.parts.len(), 3);
                assert!(c.parts()[0] == "x");
                assert!(c.parts()[1] == "y");
                assert!(c.parts()[2] == "z");
            }
            _ => panic!("Expected Compound identifier"),
        }

        // Compound + Simple -> Compound
        let prefix: Identifier = ident("x").dot("y").into();
        let suffix: Identifier = ident("z").into();
        let result = prefix + suffix;
        match result {
            Identifier::Compound(c) => {
                assert_eq!(c.parts.len(), 3);
                assert!(c.parts()[0] == "x");
                assert!(c.parts()[1] == "y");
                assert!(c.parts()[2] == "z");
            }
            _ => panic!("Expected Compound identifier"),
        }

        // Compound + Compound -> Compound
        let prefix: Identifier = ident("x").dot("y").into();
        let suffix: Identifier = ident("z").dot("a").into();
        let result = prefix + suffix;
        match result {
            Identifier::Compound(c) => {
                assert_eq!(c.parts.len(), 4);
                assert!(c.parts()[0] == "x");
                assert!(c.parts()[1] == "y");
                assert!(c.parts()[2] == "z");
                assert!(c.parts()[3] == "a");
            }
            _ => panic!("Expected Compound identifier"),
        }
    }
}