llvm-native-core 0.1.14

//! X86 Linker Script Parser — Full GNU ld-compatible linker script parser
//! for X86/X86-64 with complete directive support, expression evaluation
//! with operator precedence, memory region layout, section placement,
//! and symbol assignment handling.
//!
//! ## Supported GNU ld Directives
//!
//! ### Top-level Directives
//! - `OUTPUT_FORMAT(bfdname)` — specifies the BFD output format
//! - `OUTPUT_ARCH(bfdarch)` — specifies the target architecture
//! - `ENTRY(symbol)` — sets the program entry point
//! - `SEARCH_DIR(path)` — adds a library search path
//! - `INPUT(file, file, ...)` — specifies input files
//! - `GROUP(file, file, ...)` — specifies a group of archives
//! - `MEMORY { ... }` — defines memory regions
//! - `PHDRS { ... }` — defines program headers
//! - `SECTIONS { ... }` — defines output sections and placement
//! - `INCLUDE filename` — includes another linker script
//! - `EXTERN(symbol ...)` — forces symbols to be entered as undefined
//! - `PROVIDE(symbol = expression)` — defines a symbol only if not already defined
//! - `ASSERT(expr, message)` — asserts a condition at link time
//!
//! ### Section Directives
//! - `KEEP(...)` — prevents garbage collection of input sections
//! - `SORT(...)` — sorts input sections by name
//! - `SORT_BY_NAME(...)` — explicit sort by name
//! - `SORT_BY_ALIGNMENT(...)` — sorts by alignment
//! - `SORT_BY_INIT_PRIORITY(...)` — sorts by init priority
//! - `SORT_NONE` — disables sorting
//! - `ALIGN(expr)` / `SUBALIGN(expr)` — alignment constraints
//! - `AT(lma)` — specifies load memory address
//! - `FILL(expr)` — sets fill pattern
//! - `NOLOAD` / `DSECT` / `COPY` / `INFO` / `OVERLAY` — section type modifiers
//!
//! ### Expression Evaluator
//! - Arithmetic: `+`, `-`, `*`, `/`, `%`, `<<`, `>>`, `&`, `|`, `^`, `~`
//! - Comparison: `==`, `!=`, `<`, `<=`, `>`, `>=`
//! - Logical: `&&`, `||`, `!`
//! - Ternary: `expr ? expr : expr`
//! - Functions: `ALIGN`, `ADDR`, `LOADADDR`, `SIZEOF`, `CONSTANT`,
//!   `ABSOLUTE`, `DATA_SEGMENT_ALIGN`, `DATA_SEGMENT_END`,
//!   `DATA_SEGMENT_RELRO_END`, `MAX`, `MIN`, `DEFINED`, `LOG2CEIL`,
//!   `NEXT`, `SEGMENT_START`, `ORIGIN`, `LENGTH`
//!
//! Clean-room behavioral reconstruction from the GNU ld documentation
//! (info ld), ELF gABI, and observed linker behavior.
//! Zero LLVM C++ or GNU binutils source code consultation.

use std::collections::{BTreeMap, HashMap, HashSet};
use std::fmt;
use std::num::Wrapping;

// ============================================================================
// AST — Abstract Syntax Tree for Linker Scripts
// ============================================================================

/// Top-level linker script AST.
#[derive(Debug, Clone)]
pub struct LinkerScript {
    /// Output format (e.g., "elf64-x86-64").
    pub output_format: Option<String>,
    /// Output architecture (e.g., "i386:x86-64").
    pub output_arch: Option<String>,
    /// Entry point symbol.
    pub entry: Option<String>,
    /// Search directories.
    pub search_dirs: Vec<String>,
    /// Input files.
    pub input_files: Vec<String>,
    /// Group definitions.
    pub groups: Vec<Vec<String>>,
    /// Memory region definitions.
    pub memory_regions: Vec<MemoryRegion>,
    /// Program header definitions.
    pub program_headers: Vec<ProgramHeaderDef>,
    /// Section definitions.
    pub sections: Vec<SectionDef>,
    /// PROVIDE symbol assignments.
    pub provides: Vec<SymbolAssignment>,
    /// ASSERT statements.
    pub asserts: Vec<AssertStatement>,
    /// Other top-level symbols.
    pub symbols: Vec<SymbolAssignment>,
    /// Included files (resolved).
    pub includes: Vec<String>,
    /// External symbol references.
    pub extern_symbols: Vec<String>,
}

impl Default for LinkerScript {
    fn default() -> Self {
        LinkerScript {
            output_format: None,
            output_arch: None,
            entry: None,
            search_dirs: Vec::new(),
            input_files: Vec::new(),
            groups: Vec::new(),
            memory_regions: Vec::new(),
            program_headers: Vec::new(),
            sections: Vec::new(),
            provides: Vec::new(),
            asserts: Vec::new(),
            symbols: Vec::new(),
            includes: Vec::new(),
            extern_symbols: Vec::new(),
        }
    }
}

/// A memory region definition.
///
/// Example: `MEMORY { rom (rx) : ORIGIN = 0, LENGTH = 256K }`
#[derive(Debug, Clone)]
pub struct MemoryRegion {
    /// Region name (e.g., "rom", "ram").
    pub name: String,
    /// Access attributes (e.g., "rx", "rwx", "w").
    pub attributes: String,
    /// Origin address.
    pub origin: Expression,
    /// Region length.
    pub length: Expression,
}

/// A program header definition (PHDRS).
#[derive(Debug, Clone)]
pub struct ProgramHeaderDef {
    /// Header name (e.g., "text", "data").
    pub name: String,
    /// Header type (e.g., "PT_LOAD").
    pub phdr_type: String,
    /// Optional flags.
    pub flags: Option<String>,
    /// Optional file header inclusion.
    pub filehdr: bool,
    /// Optional program header inclusion.
    pub phdrs: bool,
    /// Optional AT expression.
    pub at: Option<Expression>,
}

/// A section definition from the SECTIONS block.
#[derive(Debug, Clone)]
pub struct SectionDef {
    /// Output section name (e.g., ".text").
    pub name: Option<String>,
    /// Section type modifiers.
    pub section_type: SectionType,
    /// Virtual memory address expression.
    pub vma: Option<Expression>,
    /// Load memory address expression (AT).
    pub lma: Option<Expression>,
    /// Alignment expression (ALIGN).
    pub alignment: Option<Expression>,
    /// Sub-alignment (SUBALIGN).
    pub sub_alignment: Option<Expression>,
    /// Fill value (FILL).
    pub fill: Option<Expression>,
    /// Input section specifications.
    pub input_sections: Vec<InputSectionSpec>,
    /// Symbol assignments within this section.
    pub assignments: Vec<SymbolAssignment>,
    /// Nested sections (for OVERLAY).
    pub children: Vec<SectionDef>,
}

/// Section type modifier.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SectionType {
    /// Normal section (PROGBITS).
    Normal,
    /// NOLOAD section — occupies no space in the file.
    NoLoad,
    /// DSECT section — debug-only, not allocated.
    DSect,
    /// COPY section — similar to NOLOAD.
    Copy,
    /// INFO section — informational, not allocated.
    Info,
    /// OVERLAY section — multiple sections at the same VMA.
    Overlay,
}

impl Default for SectionType {
    fn default() -> Self {
        SectionType::Normal
    }
}

/// An input section specification within an output section.
#[derive(Debug, Clone)]
pub struct InputSectionSpec {
    /// Source file(s) glob (e.g., "*.o", "crt*.o").
    pub file_glob: Option<String>,
    /// Whether to KEEP this section (prevent GC).
    pub keep: bool,
    /// Sorting strategy.
    pub sort: SortStrategy,
    /// Input section name(s) (e.g., ".text", ".data").
    pub section_names: Vec<String>,
    /// Whether this is an EXCLUDE_FILE spec.
    pub exclude_files: Vec<String>,
}

/// Sort strategy for input sections.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SortStrategy {
    /// No sorting.
    None,
    /// Sort by name (default ascending).
    ByName,
    /// Sort by alignment (largest first).
    ByAlignment,
    /// Sort by init_priority.
    ByInitPriority,
    /// Explicitly disable sorting.
    SortNone,
}

impl Default for SortStrategy {
    fn default() -> Self {
        SortStrategy::None
    }
}

/// A symbol assignment in the linker script.
///
/// Example: `__init_array_start = .;`
#[derive(Debug, Clone)]
pub struct SymbolAssignment {
    /// Symbol name.
    pub name: String,
    /// Value expression.
    pub value: Expression,
    /// Whether this is a PROVIDE (weak) assignment.
    pub is_provide: bool,
    /// Whether this is a PROVIDE_HIDDEN assignment.
    pub is_hidden: bool,
    /// Whether this is a HIDDEN assignment.
    pub hidden: bool,
    /// Assignment operator used (=, +=, -=, etc.).
    pub operator: AssignmentOp,
}

/// Assignment operator types.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum AssignmentOp {
    /// Simple assignment: `=`
    Assign,
    /// Add-and-assign: `+=`
    AddAssign,
    /// Subtract-and-assign: `-=`
    SubAssign,
    /// Multiply-and-assign: `*=`
    MulAssign,
    /// Divide-and-assign: `/=`
    DivAssign,
    /// And-and-assign: `&=`
    AndAssign,
    /// Or-and-assign: `|=`
    OrAssign,
    /// Left-shift-and-assign: `<<=`
    ShlAssign,
    /// Right-shift-and-assign: `>>=`
    ShrAssign,
}

/// An ASSERT statement.
#[derive(Debug, Clone)]
pub struct AssertStatement {
    /// Condition expression.
    pub condition: Expression,
    /// Failure message.
    pub message: String,
}

// ============================================================================
// Expression AST and Evaluator
// ============================================================================

/// An expression in the linker script language.
#[derive(Debug, Clone)]
pub enum Expression {
    /// Integer literal.
    Integer(i64),
    /// String literal.
    String(String),
    /// Symbol reference.
    Symbol(String),
    /// The current location counter (`.`).
    LocationCounter,
    /// Binary operation.
    BinaryOp {
        op: BinaryOpKind,
        lhs: Box<Expression>,
        rhs: Box<Expression>,
    },
    /// Unary operation.
    UnaryOp {
        op: UnaryOpKind,
        expr: Box<Expression>,
    },
    /// Ternary conditional: `cond ? true_expr : false_expr`.
    Ternary {
        condition: Box<Expression>,
        true_expr: Box<Expression>,
        false_expr: Box<Expression>,
    },
    /// Function call.
    FunctionCall { name: String, args: Vec<Expression> },
    /// Named section attribute (e.g., section's VMA).
    SectionAttribute {
        section_name: String,
        attribute: SectionAttrKind,
    },
    /// Absolute value — treats the expression as absolute (not relocatable).
    Absolute(Box<Expression>),
    /// Memory region attribute.
    MemoryRegionAttr {
        region_name: String,
        attribute: MemoryRegionAttrKind,
    },
    /// The `NEXT(expr)` builtin — next unallocated address at or after expr.
    Next(Box<Expression>),
    /// CONSTANT(name) — evaluate to a named constant.
    Constant(String),
    /// DEFINED(symbol) — 1 if symbol is defined, 0 otherwise.
    Defined(String),
    /// SEGMENT_START(segment, default) — return the base of a segment.
    SegmentStart {
        segment: String,
        default: Box<Expression>,
    },
}

/// Binary operator kind.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum BinaryOpKind {
    // Arithmetic
    Add,
    Sub,
    Mul,
    Div,
    Mod,
    Shl,
    Shr,
    BitAnd,
    BitOr,
    BitXor,
    // Comparison
    Eq,
    Ne,
    Lt,
    Le,
    Gt,
    Ge,
    // Logical
    And,
    Or,
    // Assignment operators (used in parsing, not evaluation)
    Min,
    Max,
}

impl BinaryOpKind {
    /// Precedence level (lower = tighter binding).
    pub fn precedence(&self) -> u8 {
        match self {
            BinaryOpKind::Mul | BinaryOpKind::Div | BinaryOpKind::Mod => 5,
            BinaryOpKind::Add | BinaryOpKind::Sub => 4,
            BinaryOpKind::Shl | BinaryOpKind::Shr => 3,
            BinaryOpKind::Lt | BinaryOpKind::Le | BinaryOpKind::Gt | BinaryOpKind::Ge => 2,
            BinaryOpKind::Eq | BinaryOpKind::Ne => 1,
            BinaryOpKind::BitAnd => 0, // lower than comparison in linker scripts
            BinaryOpKind::BitXor => 0,
            BinaryOpKind::BitOr => 0,
            BinaryOpKind::And => 0,
            BinaryOpKind::Or => 0,
            BinaryOpKind::Min => 6,
            BinaryOpKind::Max => 6,
        }
    }

    pub fn is_comparison(&self) -> bool {
        matches!(
            self,
            BinaryOpKind::Eq
                | BinaryOpKind::Ne
                | BinaryOpKind::Lt
                | BinaryOpKind::Le
                | BinaryOpKind::Gt
                | BinaryOpKind::Ge
        )
    }
}

/// Unary operator kind.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum UnaryOpKind {
    Neg,
    BitNot,
    LogNot,
    Abs,
}

/// Section attribute kind for expressions like `ADDR(section)`.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SectionAttrKind {
    /// Virtual memory address: `ADDR(section)`.
    Addr,
    /// Load memory address: `LOADADDR(section)`.
    LoadAddr,
    /// Size of the section: `SIZEOF(section)`.
    SizeOf,
    /// Alignment of the section: `ALIGNOF(section)`.
    AlignOf,
}

/// Memory region attribute kind.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum MemoryRegionAttrKind {
    /// Start address: `ORIGIN(region)`.
    Origin,
    /// Length: `LENGTH(region)`.
    Length,
}

// ============================================================================
// Expression Evaluator Output
// ============================================================================

/// Result of evaluating an expression.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum EvalResult {
    /// An absolute integer value.
    Absolute(i64),
    /// A relocatable value (section-relative).
    Relocatable {
        /// Section name this value is relative to.
        section: String,
        /// Offset within that section.
        offset: i64,
    },
    /// A string value.
    String(String),
    /// A boolean value.
    Boolean(bool),
}

impl fmt::Display for EvalResult {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            EvalResult::Absolute(v) => write!(f, "0x{:X}", v),
            EvalResult::Relocatable { section, offset } => {
                write!(f, "{}+0x{:X}", section, offset)
            }
            EvalResult::String(s) => write!(f, "\"{}\"", s),
            EvalResult::Boolean(b) => write!(f, "{}", b),
        }
    }
}

// ============================================================================
// Expression Evaluator
// ============================================================================

/// Context for expression evaluation, providing access to section
/// addresses, sizes, symbol values, and the location counter.
#[derive(Debug, Clone, Default)]
pub struct EvalContext {
    /// Location counter (the `.` symbol).
    pub location_counter: i64,
    /// Known symbol values.
    pub symbols: HashMap<String, i64>,
    /// Section addresses (by name).
    pub section_addrs: HashMap<String, i64>,
    /// Section load addresses.
    pub section_load_addrs: HashMap<String, i64>,
    /// Section sizes.
    pub section_sizes: HashMap<String, i64>,
    /// Section alignments.
    pub section_aligns: HashMap<String, i64>,
    /// Memory region origins.
    pub memory_origins: HashMap<String, i64>,
    /// Memory region lengths.
    pub memory_lengths: HashMap<String, i64>,
    /// Defined symbol set.
    pub defined_symbols: HashSet<String>,
    /// Named constants.
    pub constants: HashMap<String, i64>,
    /// Whether this is an "absolute" evaluation context.
    pub is_absolute: bool,
}

impl EvalContext {
    /// Create a new evaluation context.
    pub fn new() -> Self {
        EvalContext::default()
    }

    /// Look up a named constant value.
    pub fn lookup_constant(&self, name: &str) -> Option<i64> {
        // Built-in constants:
        match name.to_uppercase().as_str() {
            "MAXPAGESIZE" => Some(0x1000),    // 4K
            "COMMONPAGESIZE" => Some(0x1000), // 4K
            "CONSTANT" => None,               // generic look-up
            _ => self.constants.get(&name.to_lowercase()).copied(),
        }
    }
}

/// Evaluate an expression within a given context.
pub fn evaluate_expression(expr: &Expression, ctx: &EvalContext) -> Result<EvalResult, String> {
    match expr {
        Expression::Integer(v) => Ok(EvalResult::Absolute(*v)),
        Expression::String(s) => Ok(EvalResult::String(s.clone())),
        Expression::LocationCounter => Ok(EvalResult::Absolute(ctx.location_counter)),
        Expression::Symbol(name) => {
            if let Some(&val) = ctx.symbols.get(name) {
                Ok(EvalResult::Absolute(val))
            } else {
                Err(format!("undefined symbol: {}", name))
            }
        }
        Expression::UnaryOp { op, expr } => {
            let val = evaluate_expression(expr, ctx)?;
            eval_unary(*op, val)
        }
        Expression::BinaryOp { op, lhs, rhs } => {
            let lval = evaluate_expression(lhs, ctx)?;
            let rval = evaluate_expression(rhs, ctx)?;
            eval_binary(*op, lval, rval)
        }
        Expression::Ternary {
            condition,
            true_expr,
            false_expr,
        } => {
            let cond = evaluate_expression(condition, ctx)?;
            match cond {
                EvalResult::Boolean(true) => evaluate_expression(true_expr, ctx),
                EvalResult::Absolute(v) if v != 0 => evaluate_expression(true_expr, ctx),
                _ => evaluate_expression(false_expr, ctx),
            }
        }
        Expression::FunctionCall { name, args } => eval_function(name, args, ctx),
        Expression::SectionAttribute {
            section_name,
            attribute,
        } => eval_section_attr(section_name, *attribute, ctx),
        Expression::Absolute(inner) => {
            // ABSOLUTE forces absolute evaluation.
            let mut abs_ctx = ctx.clone();
            abs_ctx.is_absolute = true;
            evaluate_expression(inner, &abs_ctx)
        }
        Expression::MemoryRegionAttr {
            region_name,
            attribute,
        } => eval_memory_attr(region_name, *attribute, ctx),
        Expression::Next(inner) => {
            // NEXT(expr) returns the next unallocated address at or after expr.
            let val = evaluate_expression(inner, ctx)?;
            let addr = val_to_i64(&val)?;
            // Round up to alignment (simplified: 8-byte alignment).
            Ok(EvalResult::Absolute((addr + 7) & !7))
        }
        Expression::Constant(name) => {
            if let Some(val) = ctx.lookup_constant(name) {
                Ok(EvalResult::Absolute(val))
            } else {
                Err(format!("unknown constant: {}", name))
            }
        }
        Expression::Defined(sym) => {
            let defined = ctx.defined_symbols.contains(sym) || ctx.symbols.contains_key(sym);
            Ok(EvalResult::Boolean(defined))
        }
        Expression::SegmentStart { segment, default } => {
            // Look up segment base or use default.
            let base = ctx.section_addrs.get(segment).copied();
            match base {
                Some(addr) => Ok(EvalResult::Absolute(addr)),
                None => evaluate_expression(default, ctx),
            }
        }
    }
}

/// Evaluate a unary operation.
fn eval_unary(op: UnaryOpKind, val: EvalResult) -> Result<EvalResult, String> {
    let val_for_err = val.clone();
    match (op, val) {
        (UnaryOpKind::Neg, EvalResult::Absolute(v)) => Ok(EvalResult::Absolute(-v)),
        (UnaryOpKind::BitNot, EvalResult::Absolute(v)) => Ok(EvalResult::Absolute(!v)),
        (UnaryOpKind::LogNot, EvalResult::Absolute(v)) => Ok(EvalResult::Boolean(v == 0)),
        (UnaryOpKind::LogNot, EvalResult::Boolean(b)) => Ok(EvalResult::Boolean(!b)),
        (UnaryOpKind::Abs, EvalResult::Absolute(v)) => Ok(EvalResult::Absolute(v.abs())),
        _ => Err(format!(
            "invalid unary operation {:?} on {:?}",
            op, val_for_err
        )),
    }
}

/// Evaluate a binary operation.
fn eval_binary(op: BinaryOpKind, lhs: EvalResult, rhs: EvalResult) -> Result<EvalResult, String> {
    let l = val_to_i64(&lhs)?;
    let r = val_to_i64(&rhs)?;

    let result = match op {
        BinaryOpKind::Add => l.wrapping_add(r),
        BinaryOpKind::Sub => l.wrapping_sub(r),
        BinaryOpKind::Mul => l.wrapping_mul(r),
        BinaryOpKind::Div => {
            if r == 0 {
                return Err("division by zero".to_string());
            }
            // Signed division
            l / r
        }
        BinaryOpKind::Mod => {
            if r == 0 {
                return Err("modulo by zero".to_string());
            }
            l % r
        }
        BinaryOpKind::Shl => {
            let shift = (r as u32) & 63;
            l << shift
        }
        BinaryOpKind::Shr => {
            let shift = (r as u32) & 63;
            l >> shift
        }
        BinaryOpKind::BitAnd => l & r,
        BinaryOpKind::BitOr => l | r,
        BinaryOpKind::BitXor => l ^ r,
        BinaryOpKind::Eq => return Ok(EvalResult::Boolean(l == r)),
        BinaryOpKind::Ne => return Ok(EvalResult::Boolean(l != r)),
        BinaryOpKind::Lt => return Ok(EvalResult::Boolean(l < r)),
        BinaryOpKind::Le => return Ok(EvalResult::Boolean(l <= r)),
        BinaryOpKind::Gt => return Ok(EvalResult::Boolean(l > r)),
        BinaryOpKind::Ge => return Ok(EvalResult::Boolean(l >= r)),
        BinaryOpKind::And => return Ok(EvalResult::Boolean(l != 0 && r != 0)),
        BinaryOpKind::Or => return Ok(EvalResult::Boolean(l != 0 || r != 0)),
        BinaryOpKind::Min => l.min(r),
        BinaryOpKind::Max => l.max(r),
    };

    Ok(EvalResult::Absolute(result))
}

/// Evaluate a function call.
fn eval_function(name: &str, args: &[Expression], ctx: &EvalContext) -> Result<EvalResult, String> {
    match name.to_uppercase().as_str() {
        "ALIGN" | "ALIGN_WITH_INPUT" => {
            if args.is_empty() {
                return Err("ALIGN requires at least 1 argument".to_string());
            }
            let value = val_to_i64(&evaluate_expression(&args[0], ctx)?)?;
            let align = if args.len() >= 2 {
                val_to_i64(&evaluate_expression(&args[1], ctx)?)?
            } else {
                value // self as alignment
            };
            if align == 0 {
                return Err("ALIGN with zero alignment".to_string());
            }
            let aligned = ((value + (align - 1)) / align) * align;
            Ok(EvalResult::Absolute(aligned))
        }
        "ADDR" => {
            if args.len() != 1 {
                return Err("ADDR requires exactly 1 argument".to_string());
            }
            let name = expr_to_string(&args[0], ctx)?;
            eval_section_attr(&name, SectionAttrKind::Addr, ctx)
        }
        "LOADADDR" => {
            if args.len() != 1 {
                return Err("LOADADDR requires exactly 1 argument".to_string());
            }
            let name = expr_to_string(&args[0], ctx)?;
            eval_section_attr(&name, SectionAttrKind::LoadAddr, ctx)
        }
        "SIZEOF" => {
            if args.len() != 1 {
                return Err("SIZEOF requires exactly 1 argument".to_string());
            }
            let name = expr_to_string(&args[0], ctx)?;
            eval_section_attr(&name, SectionAttrKind::SizeOf, ctx)
        }
        "ABSOLUTE" => {
            if args.len() != 1 {
                return Err("ABSOLUTE requires exactly 1 argument".to_string());
            }
            let mut abs_ctx = ctx.clone();
            abs_ctx.is_absolute = true;
            evaluate_expression(&args[0], &abs_ctx)
        }
        "MAX" => {
            if args.len() < 2 {
                return Err("MAX requires at least 2 arguments".to_string());
            }
            let mut max_val = i64::MIN;
            for arg in args {
                let v = val_to_i64(&evaluate_expression(arg, ctx)?)?;
                if v > max_val {
                    max_val = v;
                }
            }
            Ok(EvalResult::Absolute(max_val))
        }
        "MIN" => {
            if args.len() < 2 {
                return Err("MIN requires at least 2 arguments".to_string());
            }
            let mut min_val = i64::MAX;
            for arg in args {
                let v = val_to_i64(&evaluate_expression(arg, ctx)?)?;
                if v < min_val {
                    min_val = v;
                }
            }
            Ok(EvalResult::Absolute(min_val))
        }
        "DATA_SEGMENT_ALIGN" => {
            if args.len() < 1 {
                return Err("DATA_SEGMENT_ALIGN requires at least 1 argument".to_string());
            }
            let maxpagesize = val_to_i64(&evaluate_expression(&args[0], ctx)?)?;
            let commonpagesize = if args.len() >= 2 {
                val_to_i64(&evaluate_expression(&args[1], ctx)?)?
            } else {
                0x1000
            };
            let dot = ctx.location_counter;
            let aligned =
                ((dot + maxpagesize - 1) & !(maxpagesize - 1)).max(dot & !(commonpagesize - 1));
            Ok(EvalResult::Absolute(aligned))
        }
        "DATA_SEGMENT_END" => {
            if args.len() < 1 {
                return Err("DATA_SEGMENT_END requires at least 1 argument".to_string());
            }
            let end_addr = val_to_i64(&evaluate_expression(&args[0], ctx)?)?;
            // DATA_SEGMENT_END returns end_addr. In practice it also has
            // side effects for RELRO computation.
            Ok(EvalResult::Absolute(end_addr))
        }
        "DATA_SEGMENT_RELRO_END" => {
            if args.len() < 2 {
                return Err("DATA_SEGMENT_RELRO_END requires at least 2 arguments".to_string());
            }
            let offset = val_to_i64(&evaluate_expression(&args[0], ctx)?)?;
            let exp_addr = val_to_i64(&evaluate_expression(&args[1], ctx)?)?;
            // Returns the adjusted RELRO end address.
            Ok(EvalResult::Absolute(exp_addr + offset))
        }
        "DEFINED" => {
            if args.len() != 1 {
                return Err("DEFINED requires exactly 1 argument".to_string());
            }
            let sym = expr_to_string(&args[0], ctx)?;
            let defined = ctx.defined_symbols.contains(&sym) || ctx.symbols.contains_key(&sym);
            Ok(EvalResult::Boolean(defined))
        }
        "LOG2CEIL" => {
            if args.len() != 1 {
                return Err("LOG2CEIL requires exactly 1 argument".to_string());
            }
            let v = val_to_i64(&evaluate_expression(&args[0], ctx)?)?;
            if v <= 1 {
                return Ok(EvalResult::Absolute(0));
            }
            let ceil_log2 = 64 - (v - 1).leading_zeros() as i64;
            Ok(EvalResult::Absolute(ceil_log2))
        }
        "NEXT" => {
            if args.len() != 1 {
                return Err("NEXT requires exactly 1 argument".to_string());
            }
            let val = val_to_i64(&evaluate_expression(&args[0], ctx)?)?;
            Ok(EvalResult::Absolute((val + 7) & !7))
        }
        "ORIGIN" => {
            if args.len() != 1 {
                return Err("ORIGIN requires exactly 1 argument".to_string());
            }
            let name = expr_to_string(&args[0], ctx)?;
            eval_memory_attr(&name, MemoryRegionAttrKind::Origin, ctx)
        }
        "LENGTH" => {
            if args.len() != 1 {
                return Err("LENGTH requires exactly 1 argument".to_string());
            }
            let name = expr_to_string(&args[0], ctx)?;
            eval_memory_attr(&name, MemoryRegionAttrKind::Length, ctx)
        }
        "SEGMENT_START" => {
            if args.len() < 2 {
                return Err("SEGMENT_START requires at least 2 arguments".to_string());
            }
            let segment = expr_to_string(&args[0], ctx)?;
            let base = ctx.section_addrs.get(&segment).copied();
            match base {
                Some(addr) => Ok(EvalResult::Absolute(addr)),
                None => evaluate_expression(&args[1], ctx),
            }
        }
        "CONSTANT" => {
            if args.len() != 1 {
                return Err("CONSTANT requires exactly 1 argument".to_string());
            }
            let name = expr_to_string(&args[0], ctx)?;
            match ctx.lookup_constant(&name) {
                Some(val) => Ok(EvalResult::Absolute(val)),
                None => Err(format!("unknown constant: {}", name)),
            }
        }
        _ => Err(format!("unknown function: {}", name)),
    }
}

/// Evaluate a section attribute reference.
fn eval_section_attr(
    name: &str,
    attr: SectionAttrKind,
    ctx: &EvalContext,
) -> Result<EvalResult, String> {
    match attr {
        SectionAttrKind::Addr => ctx
            .section_addrs
            .get(name)
            .map(|&v| EvalResult::Absolute(v))
            .ok_or_else(|| format!("unknown section: {}", name)),
        SectionAttrKind::LoadAddr => ctx
            .section_load_addrs
            .get(name)
            .map(|&v| EvalResult::Absolute(v))
            .ok_or_else(|| format!("unknown section: {}", name)),
        SectionAttrKind::SizeOf => ctx
            .section_sizes
            .get(name)
            .map(|&v| EvalResult::Absolute(v))
            .ok_or_else(|| format!("unknown section: {}", name)),
        SectionAttrKind::AlignOf => ctx
            .section_aligns
            .get(name)
            .map(|&v| EvalResult::Absolute(v))
            .ok_or_else(|| format!("unknown section: {}", name)),
    }
}

/// Evaluate a memory region attribute reference.
fn eval_memory_attr(
    name: &str,
    attr: MemoryRegionAttrKind,
    ctx: &EvalContext,
) -> Result<EvalResult, String> {
    match attr {
        MemoryRegionAttrKind::Origin => ctx
            .memory_origins
            .get(name)
            .map(|&v| EvalResult::Absolute(v))
            .ok_or_else(|| format!("unknown memory region: {}", name)),
        MemoryRegionAttrKind::Length => ctx
            .memory_lengths
            .get(name)
            .map(|&v| EvalResult::Absolute(v))
            .ok_or_else(|| format!("unknown memory region: {}", name)),
    }
}

/// Helper: extract an i64 from an EvalResult.
fn val_to_i64(val: &EvalResult) -> Result<i64, String> {
    match val {
        EvalResult::Absolute(v) => Ok(*v),
        EvalResult::Relocatable { offset, .. } => Ok(*offset),
        EvalResult::Boolean(true) => Ok(1),
        EvalResult::Boolean(false) => Ok(0),
        EvalResult::String(s) => {
            // Try to parse as integer.
            s.parse::<i64>()
                .or_else(|_| {
                    if s.starts_with("0x") || s.starts_with("0X") {
                        i64::from_str_radix(&s[2..], 16)
                    } else if s.starts_with("0") && s.len() > 1 {
                        i64::from_str_radix(&s[1..], 8)
                    } else {
                        "".parse::<i64>()
                    }
                })
                .map_err(|_| format!("cannot convert string '{}' to integer", s))
        }
    }
}

/// Helper: extract a string from an expression.
fn expr_to_string(expr: &Expression, ctx: &EvalContext) -> Result<String, String> {
    match expr {
        Expression::String(s) => Ok(s.clone()),
        Expression::Symbol(s) => Ok(s.clone()),
        Expression::Constant(s) => Ok(s.clone()),
        other => {
            // Evaluate and convert to string.
            let val = evaluate_expression(other, ctx)?;
            match val {
                EvalResult::String(s) => Ok(s),
                EvalResult::Absolute(v) => Ok(format!("0x{:X}", v)),
                _ => Err("expected string expression".to_string()),
            }
        }
    }
}

// ============================================================================
// Tokenizer
// ============================================================================

/// A token in the linker script language.
#[derive(Debug, Clone, PartialEq)]
pub enum Token {
    // Keywords
    OutputFormat,
    OutputArch,
    Entry,
    SearchDir,
    Input,
    Group,
    Memory,
    Phdrs,
    Sections,
    Include,
    Extern,
    Provide,
    ProvideHidden,
    Hidden,
    Assert,
    Keep,
    Sort,
    SortByName,
    SortByAlignment,
    SortByInitPriority,
    SortNone,
    Align,
    SubAlign,
    At,
    Fill,
    NoLoad,
    DSect,
    Copy,
    Info,
    Overlay,
    Absolute,
    Constant,
    Defined,
    Next,
    SegmentStart,
    Origin,
    Length,
    DataSegAlign,
    DataSegEnd,
    DataSegRelroEnd,
    Max,
    Min,
    Log2Ceil,
    Alias,
    FileHdr,
    PhdrHdr,
    Flags,

    // Symbols
    LParen,    // (
    RParen,    // )
    LBrace,    // {
    RBrace,    // }
    LBracket,  // [
    RBracket,  // ]
    Colon,     // :
    SemiColon, // ;
    Comma,     // ,
    Dot,       // .
    Equals,    // =
    Plus,      // +
    Minus,     // -
    Star,      // *
    Slash,     // /
    Percent,   // %
    LShift,    // <<
    RShift,    // >>
    Ampersand, // &
    Pipe,      // |
    Caret,     // ^
    Tilde,     // ~
    Exclaim,   // !
    Question,  // ?
    Lt,        // <
    Gt,        // >
    EqEq,      // ==
    Ne,        // !=
    Le,        // <=
    Ge,        // >=
    AndAnd,    // &&
    OrOr,      // ||
    PlusEq,    // +=
    MinusEq,   // -=
    StarEq,    // *=
    SlashEq,   // /=
    AmpEq,     // &=
    PipeEq,    // |=
    LShiftEq,  // <<=
    RShiftEq,  // >>=

    // Value tokens
    Integer(i64),
    Identifier(String),
    StringLit(String),
}

impl fmt::Display for Token {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Token::Integer(v) => write!(f, "{}", v),
            Token::Identifier(s) => write!(f, "{}", s),
            Token::StringLit(s) => write!(f, "\"{}\"", s),
            Token::LParen => write!(f, "("),
            Token::RParen => write!(f, ")"),
            Token::LBrace => write!(f, "{{"),
            Token::RBrace => write!(f, "}}"),
            Token::SemiColon => write!(f, ";"),
            Token::Colon => write!(f, ":"),
            Token::Comma => write!(f, ","),
            Token::Dot => write!(f, "."),
            Token::Equals => write!(f, "="),
            Token::Plus => write!(f, "+"),
            Token::Minus => write!(f, "-"),
            _ => write!(f, "{:?}", self),
        }
    }
}

// ============================================================================
// X86LinkerScript — Main Parser
// ============================================================================

/// The complete X86 linker script parser and evaluator.
#[derive(Debug)]
pub struct X86LinkerScript {
    /// Parsed script AST.
    pub script: LinkerScript,
    /// Evaluation context.
    pub eval_ctx: EvalContext,
    /// Current token stream for parsing.
    tokens: Vec<Token>,
    /// Current position in the token stream.
    pos: usize,
    /// Diagnostic messages.
    pub diagnostics: Vec<String>,
    /// Where section placement was resolved.
    pub section_layout: BTreeMap<String, SectionLayout>,
}

/// Layout information for a placed section.
#[derive(Debug, Clone)]
pub struct SectionLayout {
    /// Virtual memory address.
    pub vma: i64,
    /// Load memory address.
    pub lma: i64,
    /// Section size.
    pub size: i64,
    /// Alignment.
    pub alignment: i64,
    /// Allocated memory region.
    pub region: Option<String>,
}

impl X86LinkerScript {
    /// Create a new linker script parser.
    pub fn new() -> Self {
        X86LinkerScript {
            script: LinkerScript::default(),
            eval_ctx: EvalContext::new(),
            tokens: Vec::new(),
            pos: 0,
            diagnostics: Vec::new(),
            section_layout: BTreeMap::new(),
        }
    }

    /// Parse a linker script from source text.
    pub fn parse(&mut self, source: &str) -> Result<&LinkerScript, String> {
        self.tokens = tokenize(source);
        self.pos = 0;
        self.script = LinkerScript::default();

        // Parse top-level directives.
        while self.pos < self.tokens.len() {
            self.parse_top_level_directive()?;
        }

        // After parsing, compute section layouts.
        self.compute_layout();

        Ok(&self.script)
    }

    /// Compute section placement and layout.
    fn compute_layout(&mut self) {
        self.section_layout.clear();
        let mut current_vma: i64 = 0;

        for section in &self.script.sections {
            let name = section
                .name
                .clone()
                .unwrap_or_else(|| ".anonymous".to_string());
            let vma = match &section.vma {
                Some(expr) => match evaluate_expression(expr, &self.eval_ctx) {
                    Ok(EvalResult::Absolute(v)) => v,
                    _ => current_vma,
                },
                None => current_vma,
            };
            let alignment = section
                .alignment
                .as_ref()
                .and_then(|e| {
                    evaluate_expression(e, &self.eval_ctx)
                        .ok()
                        .and_then(|r| match r {
                            EvalResult::Absolute(v) => Some(v),
                            _ => None,
                        })
                })
                .unwrap_or(1);

            let lma = section
                .lma
                .as_ref()
                .and_then(|e| {
                    evaluate_expression(e, &self.eval_ctx)
                        .ok()
                        .and_then(|r| match r {
                            EvalResult::Absolute(v) => Some(v),
                            _ => None,
                        })
                })
                .unwrap_or(vma);

            // Align VMA.
            let aligned_vma = if alignment > 1 {
                ((vma + alignment - 1) / alignment) * alignment
            } else {
                vma
            };

            let layout = SectionLayout {
                vma: aligned_vma,
                lma,
                size: 0, // Would be determined during actual linking
                alignment,
                region: None,
            };

            self.section_layout.insert(name.clone(), layout);
            self.eval_ctx
                .section_addrs
                .insert(name.clone(), aligned_vma);

            // Advance location counter (simplified).
            current_vma = aligned_vma + 0x1000; // placeholder
        }
    }

    /// Parse a single top-level directive.
    fn parse_top_level_directive(&mut self) -> Result<(), String> {
        if self.pos >= self.tokens.len() {
            return Ok(());
        }

        match &self.tokens[self.pos] {
            Token::OutputFormat => {
                self.pos += 1;
                self.expect(Token::LParen)?;
                let fmt = self.expect_string()?;
                self.expect(Token::RParen)?;
                self.expect_semicolon()?;
                self.script.output_format = Some(fmt);
            }
            Token::OutputArch => {
                self.pos += 1;
                self.expect(Token::LParen)?;
                let arch = self.expect_string()?;
                self.expect(Token::RParen)?;
                self.expect_semicolon()?;
                self.script.output_arch = Some(arch);
            }
            Token::Entry => {
                self.pos += 1;
                self.expect(Token::LParen)?;
                let sym = self.expect_identifier()?;
                self.expect(Token::RParen)?;
                self.expect_semicolon()?;
                self.script.entry = Some(sym);
            }
            Token::SearchDir => {
                self.pos += 1;
                self.expect(Token::LParen)?;
                let path = self.expect_string()?;
                self.expect(Token::RParen)?;
                self.expect_semicolon()?;
                self.script.search_dirs.push(path);
            }
            Token::Input => {
                self.pos += 1;
                self.expect(Token::LParen)?;
                self.parse_input_file_list()?;
                self.expect_semicolon()?;
            }
            Token::Group => {
                self.pos += 1;
                self.expect(Token::LParen)?;
                let mut files = Vec::new();
                while !self.check(Token::RParen) {
                    files.push(self.expect_string()?);
                    if !self.check(Token::RParen) {
                        self.expect(Token::Comma)?;
                    }
                }
                self.expect(Token::RParen)?;
                self.expect_semicolon()?;
                self.script.groups.push(files);
            }
            Token::Include => {
                self.pos += 1;
                let filename = self.expect_string()?;
                self.expect_semicolon()?;
                self.script.includes.push(filename);
            }
            Token::Extern => {
                self.pos += 1;
                self.expect(Token::LParen)?;
                while !self.check(Token::RParen) {
                    let sym = self.expect_identifier()?;
                    self.script.extern_symbols.push(sym);
                    if !self.check(Token::RParen) {
                        self.expect(Token::Comma)?;
                    }
                }
                self.expect(Token::RParen)?;
                self.expect_semicolon()?;
            }
            Token::Provide | Token::ProvideHidden => {
                let is_provide = matches!(self.tokens[self.pos], Token::Provide);
                let is_hidden = matches!(self.tokens[self.pos], Token::ProvideHidden);
                self.pos += 1;
                self.expect(Token::LParen)?;
                let name = self.expect_identifier()?;
                self.expect(Token::Equals)?;
                let value = self.parse_expression(0)?;
                self.expect(Token::RParen)?;
                self.expect_semicolon()?;
                self.script.provides.push(SymbolAssignment {
                    name,
                    value,
                    is_provide,
                    is_hidden,
                    hidden: false,
                    operator: AssignmentOp::Assign,
                });
            }
            Token::Assert => {
                self.pos += 1;
                self.expect(Token::LParen)?;
                let cond = self.parse_expression(0)?;
                self.expect(Token::Comma)?;
                let msg = self.expect_string()?;
                self.expect(Token::RParen)?;
                self.expect_semicolon()?;
                self.script.asserts.push(AssertStatement {
                    condition: cond,
                    message: msg,
                });
            }
            Token::Memory => {
                self.pos += 1;
                self.parse_memory_block()?;
            }
            Token::Phdrs => {
                self.pos += 1;
                self.parse_phdrs_block()?;
            }
            Token::Sections => {
                self.pos += 1;
                self.parse_sections_block()?;
            }
            Token::SemiColon => {
                self.pos += 1; // empty statement
            }
            Token::Identifier(name) => {
                // Might be a symbol assignment.
                let name = name.clone();
                self.pos += 1;
                if self.check(Token::Equals) || self.check(Token::PlusEq) {
                    let op = self.parse_assignment_op()?;
                    let value = self.parse_expression(0)?;
                    self.expect_semicolon()?;
                    self.script.symbols.push(SymbolAssignment {
                        name,
                        value,
                        is_provide: false,
                        is_hidden: false,
                        hidden: false,
                        operator: op,
                    });
                } else {
                    return Err(format!(
                        "unexpected identifier '{}' at top level (line {})",
                        name, self.pos
                    ));
                }
            }
            other => {
                return Err(format!(
                    "unexpected token {:?} at top level (pos {})",
                    other, self.pos
                ));
            }
        }
        Ok(())
    }

    // --- Block Parsers ---

    /// Parse a MEMORY block.
    fn parse_memory_block(&mut self) -> Result<(), String> {
        self.expect(Token::LBrace)?;

        while !self.check(Token::RBrace) {
            let name = self.expect_identifier()?;
            let attrs = if self.check(Token::LParen) {
                self.pos += 1;
                let attrs = self.expect_identifier()?;
                self.expect(Token::RParen)?;
                attrs
            } else {
                "rwx".to_string()
            };
            self.expect(Token::Colon)?;

            let mut origin = Expression::Integer(0);
            let mut length = Expression::Integer(0);

            // Parse ORIGIN = expr, LENGTH = expr (order independent).
            for _ in 0..2 {
                if self.check_token_str("ORIGIN") {
                    self.pos += 1;
                    self.expect(Token::Equals)?;
                    origin = self.parse_expression(0)?;
                    if self.check(Token::Comma) {
                        self.pos += 1;
                    }
                } else if self.check_token_str("LENGTH") {
                    self.pos += 1;
                    self.expect(Token::Equals)?;
                    length = self.parse_expression(0)?;
                    if self.check(Token::Comma) {
                        self.pos += 1;
                    }
                }
            }

            self.script.memory_regions.push(MemoryRegion {
                name: name.clone(),
                attributes: attrs,
                origin: origin.clone(),
                length: length.clone(),
            });

            // Store in eval context.
            if let Ok(EvalResult::Absolute(orig)) = evaluate_expression(&origin, &self.eval_ctx) {
                self.eval_ctx.memory_origins.insert(name.clone(), orig);
            }
            if let Ok(EvalResult::Absolute(len)) = evaluate_expression(&length, &self.eval_ctx) {
                self.eval_ctx.memory_lengths.insert(name, len);
            }
        }

        self.expect(Token::RBrace)?;
        self.expect_semicolon()?;
        Ok(())
    }

    /// Parse a PHDRS block.
    fn parse_phdrs_block(&mut self) -> Result<(), String> {
        self.expect(Token::LBrace)?;

        while !self.check(Token::RBrace) {
            let name = self.expect_identifier()?;
            let phdr_type = self.expect_identifier()?;

            let mut flags = None;
            let mut filehdr = false;
            let mut phdrs = false;
            let mut at = None;

            // Parse optional attributes.
            while !self.check(Token::SemiColon) && !self.check(Token::RBrace) {
                let attr = self.expect_identifier()?;
                match attr.to_uppercase().as_str() {
                    "FLAGS" => {
                        self.expect(Token::LParen)?;
                        flags = Some(self.expect_identifier()?);
                        self.expect(Token::RParen)?;
                    }
                    "FILEHDR" => filehdr = true,
                    "PHDRS" => phdrs = true,
                    "AT" => {
                        self.expect(Token::LParen)?;
                        at = Some(self.parse_expression(0)?);
                        self.expect(Token::RParen)?;
                    }
                    _ => {
                        return Err(format!("unknown PHDR attribute: {}", attr));
                    }
                }
            }

            self.expect(Token::SemiColon)?;

            self.script.program_headers.push(ProgramHeaderDef {
                name,
                phdr_type,
                flags,
                filehdr,
                phdrs,
                at,
            });
        }

        self.expect(Token::RBrace)?;
        self.expect_semicolon()?;
        Ok(())
    }

    /// Parse a SECTIONS block.
    fn parse_sections_block(&mut self) -> Result<(), String> {
        self.expect(Token::LBrace)?;

        while !self.check(Token::RBrace) {
            if self.check(Token::SemiColon) {
                self.pos += 1;
                continue;
            }

            // Could be a section name or a symbol assignment.
            let first = self.tokens[self.pos].clone();

            // Peek ahead to determine if this is a section definition
            // (name followed by `:` or `{`) or a symbol assignment.
            let is_section = matches!(first, Token::Identifier(_) | Token::StringLit(_));
            let is_assignment =
                matches!(first, Token::Identifier(_)) && self.lookahead_is_assignment();

            if is_assignment {
                let name = self.expect_identifier()?;
                let op = self.parse_assignment_op()?;
                let value = self.parse_expression(0)?;
                self.expect_semicolon()?;
                self.script.symbols.push(SymbolAssignment {
                    name,
                    value,
                    is_provide: false,
                    is_hidden: false,
                    hidden: false,
                    operator: op,
                });
            } else if is_section {
                let section = self.parse_section_definition()?;
                self.script.sections.push(section);
            } else {
                return Err(format!(
                    "unexpected token {:?} in SECTIONS block",
                    self.tokens[self.pos]
                ));
            }
        }

        self.expect(Token::RBrace)?;
        self.expect_semicolon()?;
        Ok(())
    }

    /// Parse a single section definition within SECTIONS.
    fn parse_section_definition(&mut self) -> Result<SectionDef, String> {
        let mut section_type = SectionType::Normal;
        let mut vma = None;
        let mut lma = None;
        let mut alignment = None;
        let mut sub_alignment = None;
        let mut fill = None;
        let mut name: Option<String> = None;
        let mut assignments = Vec::new();
        let mut children = Vec::new();

        // Parse section type modifiers.
        while self.check_section_type() {
            match &self.tokens[self.pos] {
                Token::NoLoad => section_type = SectionType::NoLoad,
                Token::DSect => section_type = SectionType::DSect,
                Token::Copy => section_type = SectionType::Copy,
                Token::Info => section_type = SectionType::Info,
                Token::Overlay => section_type = SectionType::Overlay,
                _ => break,
            }
            self.pos += 1;
        }

        // Parse section name.
        if self.check(Token::Identifier("".to_string()))
            || self.check(Token::StringLit("".to_string()))
        {
            name = Some(self.expect_identifier_or_string()?);
        }

        // Parse optional VMA (address) after section name.
        if self.check(Token::Integer(0))
            || self.check(Token::Dot)
            || self.check(Token::Identifier("".to_string()))
        {
            vma = Some(self.parse_expression(0)?);
        }

        // Parse optional attributes: (type) : AT(lma) ALIGN(n) SUBALIGN(n) FILL(n)
        loop {
            if self.check(Token::LParen) {
                self.pos += 1;
                // Section type in parens (e.g., " (NOLOAD)").
                if self.check(Token::NoLoad) {
                    section_type = SectionType::NoLoad;
                    self.pos += 1;
                }
                self.expect(Token::RParen)?;
            } else if self.check(Token::Colon) {
                self.pos += 1;
                // Optional AT(lma), ALIGN(n), etc.
                while !self.check(Token::LBrace) && !self.check(Token::SemiColon) {
                    if self.check_token_str("AT") {
                        self.pos += 1;
                        self.expect(Token::LParen)?;
                        lma = Some(self.parse_expression(0)?);
                        self.expect(Token::RParen)?;
                    } else if self.check(Token::Align) {
                        self.pos += 1;
                        self.expect(Token::LParen)?;
                        alignment = Some(self.parse_expression(0)?);
                        self.expect(Token::RParen)?;
                    } else if self.check_token_str("SUBALIGN") {
                        self.pos += 1;
                        self.expect(Token::LParen)?;
                        sub_alignment = Some(self.parse_expression(0)?);
                        self.expect(Token::RParen)?;
                    } else if self.check(Token::Fill) {
                        self.pos += 1;
                        self.expect(Token::LParen)?;
                        fill = Some(self.parse_expression(0)?);
                        self.expect(Token::RParen)?;
                    } else {
                        break;
                    }
                }
            } else {
                break;
            }
        }

        let mut input_sections = Vec::new();

        if self.check(Token::LBrace) {
            // Parse section content.
            self.pos += 1;
            input_sections = self.parse_input_section_list()?;
            self.expect(Token::RBrace)?;
        }

        // Parse optional: section_name : { ... } >region AT>lma_region :phdr
        // (simplified — full region/phdr placement deferred).

        Ok(SectionDef {
            name,
            section_type,
            vma,
            lma,
            alignment,
            sub_alignment,
            fill,
            input_sections,
            assignments,
            children,
        })
    }

    /// Parse the list of input sections within an output section.
    fn parse_input_section_list(&mut self) -> Result<Vec<InputSectionSpec>, String> {
        let mut specs = Vec::new();

        while !self.check(Token::RBrace) {
            // Could be a symbol assignment in the section body.
            if self.check(Token::Identifier("".to_string())) && self.lookahead_is_assignment() {
                let name = self.expect_identifier()?;
                let op = self.parse_assignment_op()?;
                let value = self.parse_expression(0)?;
                self.expect_semicolon()?;
                // Add as symbol for later processing.
                self.script.symbols.push(SymbolAssignment {
                    name,
                    value,
                    is_provide: false,
                    is_hidden: false,
                    hidden: false,
                    operator: op,
                });
                continue;
            }

            if self.check(Token::SemiColon) {
                self.pos += 1;
                continue;
            }

            // Parse an input section spec.
            let spec = self.parse_input_section_spec()?;
            specs.push(spec);

            // Comma or newline continuation.
            if self.check(Token::Comma) {
                self.pos += 1;
            }
        }

        Ok(specs)
    }

    /// Parse a single input section specification.
    fn parse_input_section_spec(&mut self) -> Result<InputSectionSpec, String> {
        let mut keep = false;
        let mut sort = SortStrategy::None;
        let mut exclude_files = Vec::new();

        // KEEP(...)
        if self.check(Token::Keep) {
            keep = true;
            self.pos += 1;
            self.expect(Token::LParen)?;
        }

        // SORT*, SORT_NONE
        if self.check(Token::Sort) {
            self.pos += 1;
            self.expect(Token::LParen)?;
            sort = SortStrategy::ByName;
        } else if self.check(Token::SortByName) {
            self.pos += 1;
            self.expect(Token::LParen)?;
            sort = SortStrategy::ByName;
        } else if self.check(Token::SortByAlignment) {
            self.pos += 1;
            self.expect(Token::LParen)?;
            sort = SortStrategy::ByAlignment;
        } else if self.check(Token::SortByInitPriority) {
            self.pos += 1;
            self.expect(Token::LParen)?;
            sort = SortStrategy::ByInitPriority;
        } else if self.check(Token::SortNone) {
            self.pos += 1;
            sort = SortStrategy::SortNone;
        }

        // EXCLUDE_FILE(...)
        if self.check_token_str("EXCLUDE_FILE") {
            self.pos += 1;
            self.expect(Token::LParen)?;
            while !self.check(Token::RParen) {
                exclude_files.push(self.expect_string()?);
                if !self.check(Token::RParen) {
                    self.expect(Token::Comma)?;
                }
            }
            self.expect(Token::RParen)?;
        }

        // File glob and section name.
        let file_glob = if self.check(Token::StringLit("".to_string())) {
            Some(self.expect_string()?)
        } else if self.check(Token::Star) {
            self.pos += 1; // wildcard
            Some("*".to_string())
        } else {
            None
        };

        let mut section_names = Vec::new();

        if file_glob.is_some() {
            self.expect(Token::LParen)?;
            while !self.check(Token::RParen) {
                section_names.push(self.expect_identifier_or_string()?);
                if !self.check(Token::RParen) {
                    // Could be space-separated or comma-separated.
                    if self.check(Token::Comma) {
                        self.pos += 1;
                    }
                }
            }
            self.expect(Token::RParen)?;
        } else {
            // No file glob: just section names.
            section_names.push(self.expect_identifier_or_string()?);
            if self.check(Token::LParen) {
                self.pos += 1;
                while !self.check(Token::RParen) {
                    section_names.push(self.expect_identifier_or_string()?);
                    if self.check(Token::Comma) {
                        self.pos += 1;
                    }
                }
                self.expect(Token::RParen)?;
            }
        }

        // Close KEEP/SORT paren.
        if keep || sort != SortStrategy::None {
            self.expect(Token::RParen)?;
        }

        Ok(InputSectionSpec {
            file_glob,
            keep,
            sort,
            section_names,
            exclude_files,
        })
    }

    // --- Expression Parser ---

    /// Parse an expression with precedence climbing.
    fn parse_expression(&mut self, min_prec: u8) -> Result<Expression, String> {
        let mut lhs = self.parse_primary()?;

        loop {
            if self.pos >= self.tokens.len() {
                break;
            }

            let op = match &self.tokens[self.pos] {
                Token::Question => {
                    // Ternary: expr ? expr : expr
                    self.pos += 1;
                    let true_expr = self.parse_expression(0)?;
                    self.expect(Token::Colon)?;
                    let false_expr = self.parse_expression(0)?;
                    return Ok(Expression::Ternary {
                        condition: Box::new(lhs),
                        true_expr: Box::new(true_expr),
                        false_expr: Box::new(false_expr),
                    });
                }
                Token::OrOr => Some((BinaryOpKind::Or, 1)),
                Token::AndAnd => Some((BinaryOpKind::And, 2)),
                Token::Pipe => Some((BinaryOpKind::BitOr, 3)),
                Token::Caret => Some((BinaryOpKind::BitXor, 4)),
                Token::Ampersand => Some((BinaryOpKind::BitAnd, 5)),
                Token::EqEq => Some((BinaryOpKind::Eq, 6)),
                Token::Ne => Some((BinaryOpKind::Ne, 6)),
                Token::Lt => Some((BinaryOpKind::Lt, 7)),
                Token::Gt => {
                    if self.pos + 1 < self.tokens.len() && self.tokens[self.pos + 1] == Token::Gt {
                        None // handled below as RShift
                    } else {
                        Some((BinaryOpKind::Gt, 7))
                    }
                }
                Token::Le => Some((BinaryOpKind::Le, 7)),
                Token::Ge => Some((BinaryOpKind::Ge, 7)),
                Token::LShift => Some((BinaryOpKind::Shl, 8)),
                Token::RShift => Some((BinaryOpKind::Shr, 8)),
                Token::Plus => Some((BinaryOpKind::Add, 9)),
                Token::Minus => Some((BinaryOpKind::Sub, 9)),
                Token::Star => Some((BinaryOpKind::Mul, 10)),
                Token::Slash => Some((BinaryOpKind::Div, 10)),
                Token::Percent => Some((BinaryOpKind::Mod, 10)),
                _ => None,
            };

            if let Some((op_kind, prec)) = op {
                if prec < min_prec {
                    break;
                }
                self.pos += 1;
                let rhs = self.parse_expression(prec + 1)?;
                lhs = Expression::BinaryOp {
                    op: op_kind,
                    lhs: Box::new(lhs),
                    rhs: Box::new(rhs),
                };
            } else {
                break;
            }
        }

        Ok(lhs)
    }

    /// Parse a primary expression (literals, symbols, function calls, unary ops).
    fn parse_primary(&mut self) -> Result<Expression, String> {
        if self.pos >= self.tokens.len() {
            return Err("unexpected end of input".to_string());
        }

        let tok = &self.tokens[self.pos];

        match tok {
            Token::Integer(v) => {
                self.pos += 1;
                Ok(Expression::Integer(*v))
            }
            Token::StringLit(s) => {
                self.pos += 1;
                Ok(Expression::String(s.clone()))
            }
            Token::Dot => {
                self.pos += 1;
                Ok(Expression::LocationCounter)
            }
            Token::LParen => {
                self.pos += 1;
                let expr = self.parse_expression(0)?;
                self.expect(Token::RParen)?;
                Ok(expr)
            }
            Token::Minus => {
                self.pos += 1;
                let expr = self.parse_primary()?;
                Ok(Expression::UnaryOp {
                    op: UnaryOpKind::Neg,
                    expr: Box::new(expr),
                })
            }
            Token::Tilde => {
                self.pos += 1;
                let expr = self.parse_primary()?;
                Ok(Expression::UnaryOp {
                    op: UnaryOpKind::BitNot,
                    expr: Box::new(expr),
                })
            }
            Token::Exclaim => {
                self.pos += 1;
                let expr = self.parse_primary()?;
                Ok(Expression::UnaryOp {
                    op: UnaryOpKind::LogNot,
                    expr: Box::new(expr),
                })
            }
            Token::Plus => {
                self.pos += 1;
                // Unary plus is a no-op.
                self.parse_primary()
            }
            Token::Absolute => {
                self.pos += 1;
                self.expect(Token::LParen)?;
                let expr = self.parse_expression(0)?;
                self.expect(Token::RParen)?;
                Ok(Expression::Absolute(Box::new(expr)))
            }
            Token::Identifier(name) => {
                let name = name.clone();
                self.pos += 1;

                // Check for function call: name(...)
                if self.check(Token::LParen) {
                    self.pos += 1;
                    let mut args = Vec::new();
                    if !self.check(Token::RParen) {
                        args.push(self.parse_expression(0)?);
                        while self.check(Token::Comma) {
                            self.pos += 1;
                            args.push(self.parse_expression(0)?);
                        }
                    }
                    self.expect(Token::RParen)?;
                    Ok(Expression::FunctionCall { name, args })
                } else {
                    Ok(Expression::Symbol(name))
                }
            }
            Token::Constant => {
                self.pos += 1;
                self.expect(Token::LParen)?;
                let name = self.expect_identifier()?;
                self.expect(Token::RParen)?;
                Ok(Expression::Constant(name))
            }
            Token::Defined => {
                self.pos += 1;
                self.expect(Token::LParen)?;
                let sym = self.expect_identifier()?;
                self.expect(Token::RParen)?;
                Ok(Expression::Defined(sym))
            }
            Token::Next => {
                self.pos += 1;
                self.expect(Token::LParen)?;
                let expr = self.parse_expression(0)?;
                self.expect(Token::RParen)?;
                Ok(Expression::Next(Box::new(expr)))
            }
            Token::SegmentStart => {
                self.pos += 1;
                self.expect(Token::LParen)?;
                let seg = self.expect_identifier()?;
                self.expect(Token::Comma)?;
                let default = self.parse_expression(0)?;
                self.expect(Token::RParen)?;
                Ok(Expression::SegmentStart {
                    segment: seg,
                    default: Box::new(default),
                })
            }
            _ => Err(format!("unexpected token {:?} in expression", tok)),
        }
    }

    // --- Helpers ---

    fn check(&self, expected: Token) -> bool {
        self.pos < self.tokens.len() && self.tokens[self.pos] == expected
    }

    fn check_token_str(&self, s: &str) -> bool {
        self.pos < self.tokens.len()
            && matches!(&self.tokens[self.pos], Token::Identifier(id) if id.to_uppercase() == s.to_uppercase())
    }

    fn check_section_type(&self) -> bool {
        self.pos < self.tokens.len()
            && matches!(
                &self.tokens[self.pos],
                Token::NoLoad | Token::DSect | Token::Copy | Token::Info | Token::Overlay
            )
    }

    fn lookahead_is_assignment(&self) -> bool {
        if self.pos + 1 >= self.tokens.len() {
            return false;
        }
        matches!(
            &self.tokens[self.pos + 1],
            Token::Equals
                | Token::PlusEq
                | Token::MinusEq
                | Token::StarEq
                | Token::SlashEq
                | Token::AmpEq
                | Token::PipeEq
                | Token::LShiftEq
                | Token::RShiftEq
        )
    }

    fn expect(&mut self, expected: Token) -> Result<(), String> {
        if self.pos >= self.tokens.len() {
            return Err(format!("expected {:?}, got end of input", expected));
        }
        if self.tokens[self.pos] == expected {
            self.pos += 1;
            Ok(())
        } else {
            Err(format!(
                "expected {:?}, got {:?} at pos {}",
                expected, self.tokens[self.pos], self.pos
            ))
        }
    }

    fn expect_semicolon(&mut self) -> Result<(), String> {
        if self.pos < self.tokens.len() && self.tokens[self.pos] == Token::SemiColon {
            self.pos += 1;
            Ok(())
        } else {
            // Semicolons are optional in many places in GNU ld syntax.
            Ok(())
        }
    }

    fn expect_identifier(&mut self) -> Result<String, String> {
        if self.pos >= self.tokens.len() {
            return Err("expected identifier, got end of input".to_string());
        }
        match &self.tokens[self.pos] {
            Token::Identifier(s) => {
                self.pos += 1;
                Ok(s.clone())
            }
            Token::OutputFormat => {
                self.pos += 1;
                Ok("OUTPUT_FORMAT".to_string())
            }
            Token::OutputArch => {
                self.pos += 1;
                Ok("OUTPUT_ARCH".to_string())
            }
            Token::Entry => {
                self.pos += 1;
                Ok("ENTRY".to_string())
            }
            Token::SearchDir => {
                self.pos += 1;
                Ok("SEARCH_DIR".to_string())
            }
            Token::Input => {
                self.pos += 1;
                Ok("INPUT".to_string())
            }
            Token::Group => {
                self.pos += 1;
                Ok("GROUP".to_string())
            }
            Token::Memory => {
                self.pos += 1;
                Ok("MEMORY".to_string())
            }
            Token::Phdrs => {
                self.pos += 1;
                Ok("PHDRS".to_string())
            }
            Token::Sections => {
                self.pos += 1;
                Ok("SECTIONS".to_string())
            }
            Token::Include => {
                self.pos += 1;
                Ok("INCLUDE".to_string())
            }
            Token::Extern => {
                self.pos += 1;
                Ok("EXTERN".to_string())
            }
            Token::Provide => {
                self.pos += 1;
                Ok("PROVIDE".to_string())
            }
            Token::ProvideHidden => {
                self.pos += 1;
                Ok("PROVIDE_HIDDEN".to_string())
            }
            Token::Hidden => {
                self.pos += 1;
                Ok("HIDDEN".to_string())
            }
            Token::Assert => {
                self.pos += 1;
                Ok("ASSERT".to_string())
            }
            Token::Keep => {
                self.pos += 1;
                Ok("KEEP".to_string())
            }
            Token::Sort => {
                self.pos += 1;
                Ok("SORT".to_string())
            }
            Token::SortByName => {
                self.pos += 1;
                Ok("SORT_BY_NAME".to_string())
            }
            Token::SortByAlignment => {
                self.pos += 1;
                Ok("SORT_BY_ALIGNMENT".to_string())
            }
            Token::SortByInitPriority => {
                self.pos += 1;
                Ok("SORT_BY_INIT_PRIORITY".to_string())
            }
            Token::SortNone => {
                self.pos += 1;
                Ok("SORT_NONE".to_string())
            }
            Token::Align => {
                self.pos += 1;
                Ok("ALIGN".to_string())
            }
            Token::SubAlign => {
                self.pos += 1;
                Ok("SUBALIGN".to_string())
            }
            Token::At => {
                self.pos += 1;
                Ok("AT".to_string())
            }
            Token::Fill => {
                self.pos += 1;
                Ok("FILL".to_string())
            }
            Token::NoLoad => {
                self.pos += 1;
                Ok("NOLOAD".to_string())
            }
            Token::DSect => {
                self.pos += 1;
                Ok("DSECT".to_string())
            }
            Token::Copy => {
                self.pos += 1;
                Ok("COPY".to_string())
            }
            Token::Info => {
                self.pos += 1;
                Ok("INFO".to_string())
            }
            Token::Overlay => {
                self.pos += 1;
                Ok("OVERLAY".to_string())
            }
            Token::Absolute => {
                self.pos += 1;
                Ok("ABSOLUTE".to_string())
            }
            Token::Constant => {
                self.pos += 1;
                Ok("CONSTANT".to_string())
            }
            Token::Defined => {
                self.pos += 1;
                Ok("DEFINED".to_string())
            }
            Token::Next => {
                self.pos += 1;
                Ok("NEXT".to_string())
            }
            Token::SegmentStart => {
                self.pos += 1;
                Ok("SEGMENT_START".to_string())
            }
            Token::Origin => {
                self.pos += 1;
                Ok("ORIGIN".to_string())
            }
            Token::Length => {
                self.pos += 1;
                Ok("LENGTH".to_string())
            }
            Token::DataSegAlign => {
                self.pos += 1;
                Ok("DATA_SEGMENT_ALIGN".to_string())
            }
            Token::DataSegEnd => {
                self.pos += 1;
                Ok("DATA_SEGMENT_END".to_string())
            }
            Token::DataSegRelroEnd => {
                self.pos += 1;
                Ok("DATA_SEGMENT_RELRO_END".to_string())
            }
            Token::Max => {
                self.pos += 1;
                Ok("MAX".to_string())
            }
            Token::Min => {
                self.pos += 1;
                Ok("MIN".to_string())
            }
            Token::Log2Ceil => {
                self.pos += 1;
                Ok("LOG2CEIL".to_string())
            }
            Token::Alias => {
                self.pos += 1;
                Ok("ALIAS".to_string())
            }
            Token::FileHdr => {
                self.pos += 1;
                Ok("FILEHDR".to_string())
            }
            Token::PhdrHdr => {
                self.pos += 1;
                Ok("PHDRS".to_string())
            }
            Token::Flags => {
                self.pos += 1;
                Ok("FLAGS".to_string())
            }
            _ => Err(format!(
                "expected identifier, got {:?}",
                self.tokens[self.pos]
            )),
        }
    }

    fn expect_string(&mut self) -> Result<String, String> {
        if self.pos >= self.tokens.len() {
            return Err("expected string, got end of input".to_string());
        }
        match &self.tokens[self.pos] {
            Token::StringLit(s) => {
                self.pos += 1;
                Ok(s.clone())
            }
            Token::Identifier(s) => {
                self.pos += 1;
                Ok(s.clone())
            }
            _ => Err(format!("expected string, got {:?}", self.tokens[self.pos])),
        }
    }

    fn expect_identifier_or_string(&mut self) -> Result<String, String> {
        if self.pos >= self.tokens.len() {
            return Err("expected identifier or string".to_string());
        }
        match &self.tokens[self.pos] {
            Token::Identifier(s) | Token::StringLit(s) => {
                self.pos += 1;
                Ok(s.clone())
            }
            Token::Star => {
                self.pos += 1;
                Ok("*".to_string())
            }
            _ => Err(format!(
                "expected identifier or string, got {:?}",
                self.tokens[self.pos]
            )),
        }
    }

    fn parse_assignment_op(&mut self) -> Result<AssignmentOp, String> {
        if self.pos >= self.tokens.len() {
            return Err("expected assignment operator".to_string());
        }
        let op = match &self.tokens[self.pos] {
            Token::Equals => AssignmentOp::Assign,
            Token::PlusEq => AssignmentOp::AddAssign,
            Token::MinusEq => AssignmentOp::SubAssign,
            Token::StarEq => AssignmentOp::MulAssign,
            Token::SlashEq => AssignmentOp::DivAssign,
            Token::AmpEq => AssignmentOp::AndAssign,
            Token::PipeEq => AssignmentOp::OrAssign,
            Token::LShiftEq => AssignmentOp::ShlAssign,
            Token::RShiftEq => AssignmentOp::ShrAssign,
            _ => {
                return Err(format!(
                    "unexpected assignment op: {:?}",
                    self.tokens[self.pos]
                ))
            }
        };
        self.pos += 1;
        Ok(op)
    }

    fn parse_input_file_list(&mut self) -> Result<(), String> {
        while !self.check(Token::RParen) {
            let s = self.expect_string()?;
            self.script.input_files.push(s);
            if !self.check(Token::RParen) {
                self.expect(Token::Comma)?;
            }
        }
        self.expect(Token::RParen)?;
        Ok(())
    }
}

// ============================================================================
// Tokenizer Implementation
// ============================================================================

/// Tokenize a linker script source string into tokens.
pub fn tokenize(source: &str) -> Vec<Token> {
    let mut tokens = Vec::new();
    let chars: Vec<char> = source.chars().collect();
    let mut i = 0;

    while i < chars.len() {
        let c = chars[i];

        // Whitespace.
        if c.is_whitespace() {
            i += 1;
            continue;
        }

        // C-style comments: /* ... */
        if c == '/' && i + 1 < chars.len() && chars[i + 1] == '*' {
            i += 2;
            while i + 1 < chars.len() && !(chars[i] == '*' && chars[i + 1] == '/') {
                i += 1;
            }
            if i + 1 < chars.len() {
                i += 2; // skip */
            }
            continue;
        }

        // C++ style comments: // ...
        if c == '/' && i + 1 < chars.len() && chars[i + 1] == '/' {
            i += 2;
            while i < chars.len() && chars[i] != '\n' {
                i += 1;
            }
            continue;
        }

        // Hash comments: # ...
        if c == '#' {
            i += 1;
            while i < chars.len() && chars[i] != '\n' {
                i += 1;
            }
            continue;
        }

        // String literals: "..." (with escape support).
        if c == '"' {
            i += 1;
            let mut s = String::new();
            while i < chars.len() && chars[i] != '"' {
                if chars[i] == '\\' && i + 1 < chars.len() {
                    i += 1;
                    match chars[i] {
                        'n' => s.push('\n'),
                        't' => s.push('\t'),
                        'r' => s.push('\r'),
                        '\\' => s.push('\\'),
                        '"' => s.push('"'),
                        '0' => s.push('\0'),
                        other => {
                            s.push('\\');
                            s.push(other);
                        }
                    }
                } else {
                    s.push(chars[i]);
                }
                i += 1;
            }
            if i < chars.len() {
                i += 1; // skip closing "
            }
            tokens.push(Token::StringLit(s));
            continue;
        }

        // Numbers (decimal, hex, octal).
        if c.is_ascii_digit() {
            let start = i;
            if c == '0' && i + 1 < chars.len() && (chars[i + 1] == 'x' || chars[i + 1] == 'X') {
                i += 2;
                while i < chars.len() && chars[i].is_ascii_hexdigit() {
                    i += 1;
                }
                let val = i64::from_str_radix(&source[start + 2..i], 16).unwrap_or(0);
                tokens.push(Token::Integer(val));
            } else if c == '0' && i + 1 < chars.len() && chars[i + 1].is_ascii_digit() {
                i += 1;
                while i < chars.len() && chars[i] >= '0' && chars[i] <= '7' {
                    i += 1;
                }
                let val = i64::from_str_radix(&source[start + 1..i], 8).unwrap_or(0);
                tokens.push(Token::Integer(val));
            } else {
                i += 1;
                while i < chars.len() && chars[i].is_ascii_digit() {
                    i += 1;
                }
                let val = source[start..i].parse::<i64>().unwrap_or(0);
                tokens.push(Token::Integer(val));
            }
            // Handle suffix: K, M, G, T (kilo, mega, giga, tera).
            if i < chars.len() {
                let suffix = chars[i];
                if suffix == 'K' || suffix == 'k' {
                    i += 1;
                    multiply_last_int(&mut tokens, 1024);
                } else if suffix == 'M' || suffix == 'm' {
                    i += 1;
                    multiply_last_int(&mut tokens, 1024 * 1024);
                } else if suffix == 'G' || suffix == 'g' {
                    i += 1;
                    multiply_last_int(&mut tokens, 1024 * 1024 * 1024);
                } else if suffix == 'T' || suffix == 't' {
                    i += 1;
                    multiply_last_int(&mut tokens, 1024 * 1024 * 1024 * 1024);
                }
            }
            continue;
        }

        // Identifiers and keywords.
        if c.is_alphabetic() || c == '_' || c == '.' {
            let start = i;
            i += 1;
            while i < chars.len()
                && (chars[i].is_alphanumeric()
                    || chars[i] == '_'
                    || chars[i] == '.'
                    || chars[i] == '-')
            {
                i += 1;
            }
            let word = source[start..i].to_string();
            let upper = word.to_uppercase();

            tokens.push(match upper.as_str() {
                "OUTPUT_FORMAT" => Token::OutputFormat,
                "OUTPUT_ARCH" => Token::OutputArch,
                "ENTRY" => Token::Entry,
                "SEARCH_DIR" => Token::SearchDir,
                "INPUT" => Token::Input,
                "GROUP" => Token::Group,
                "MEMORY" => Token::Memory,
                "PHDRS" => Token::Phdrs,
                "SECTIONS" => Token::Sections,
                "INCLUDE" => Token::Include,
                "EXTERN" => Token::Extern,
                "PROVIDE" => Token::Provide,
                "PROVIDE_HIDDEN" => Token::ProvideHidden,
                "HIDDEN" => Token::Hidden,
                "ASSERT" => Token::Assert,
                "KEEP" => Token::Keep,
                "SORT" => Token::Sort,
                "SORT_BY_NAME" => Token::SortByName,
                "SORT_BY_ALIGNMENT" => Token::SortByAlignment,
                "SORT_BY_INIT_PRIORITY" => Token::SortByInitPriority,
                "SORT_NONE" => Token::SortNone,
                "ALIGN" => Token::Align,
                "SUBALIGN" => Token::SubAlign,
                "AT" => Token::At,
                "FILL" => Token::Fill,
                "NOLOAD" => Token::NoLoad,
                "DSECT" => Token::DSect,
                "COPY" => Token::Copy,
                "INFO" => Token::Info,
                "OVERLAY" => Token::Overlay,
                "ABSOLUTE" => Token::Absolute,
                "CONSTANT" => Token::Constant,
                "DEFINED" => Token::Defined,
                "NEXT" => Token::Next,
                "SEGMENT_START" => Token::SegmentStart,
                "ORIGIN" => Token::Origin,
                "LENGTH" => Token::Length,
                "DATA_SEGMENT_ALIGN" => Token::DataSegAlign,
                "DATA_SEGMENT_END" => Token::DataSegEnd,
                "DATA_SEGMENT_RELRO_END" => Token::DataSegRelroEnd,
                "MAX" => Token::Max,
                "MIN" => Token::Min,
                "LOG2CEIL" => Token::Log2Ceil,
                "ALIAS" => Token::Alias,
                "FILEHDR" => Token::FileHdr,
                "FLAGS" => Token::Flags,
                _ => Token::Identifier(word),
            });
            continue;
        }

        // Multi-character operators and single-character tokens.
        let two_char = if i + 1 < chars.len() {
            let pair: String = chars[i..i + 2].iter().collect();
            Some(pair)
        } else {
            None
        };

        if let Some(ref pair) = two_char {
            match pair.as_str() {
                "<<" => {
                    tokens.push(Token::LShift);
                    i += 2;
                    continue;
                }
                ">>" => {
                    tokens.push(Token::RShift);
                    i += 2;
                    continue;
                }
                "==" => {
                    tokens.push(Token::EqEq);
                    i += 2;
                    continue;
                }
                "!=" => {
                    tokens.push(Token::Ne);
                    i += 2;
                    continue;
                }
                "<=" => {
                    tokens.push(Token::Le);
                    i += 2;
                    continue;
                }
                ">=" => {
                    tokens.push(Token::Ge);
                    i += 2;
                    continue;
                }
                "&&" => {
                    tokens.push(Token::AndAnd);
                    i += 2;
                    continue;
                }
                "||" => {
                    tokens.push(Token::OrOr);
                    i += 2;
                    continue;
                }
                "+=" => {
                    tokens.push(Token::PlusEq);
                    i += 2;
                    continue;
                }
                "-=" => {
                    tokens.push(Token::MinusEq);
                    i += 2;
                    continue;
                }
                "*=" => {
                    tokens.push(Token::StarEq);
                    i += 2;
                    continue;
                }
                "/=" => {
                    tokens.push(Token::SlashEq);
                    i += 2;
                    continue;
                }
                "&=" => {
                    tokens.push(Token::AmpEq);
                    i += 2;
                    continue;
                }
                "|=" => {
                    tokens.push(Token::PipeEq);
                    i += 2;
                    continue;
                }
                "<<=" => {
                    tokens.push(Token::LShiftEq);
                    i += 2;
                    continue;
                }
                ">>=" => {
                    tokens.push(Token::RShiftEq);
                    i += 2;
                    continue;
                }
                _ => {}
            }
        }

        // Single-character tokens.
        tokens.push(match c {
            '(' => Token::LParen,
            ')' => Token::RParen,
            '{' => Token::LBrace,
            '}' => Token::RBrace,
            '[' => Token::LBracket,
            ']' => Token::RBracket,
            ':' => Token::Colon,
            ';' => Token::SemiColon,
            ',' => Token::Comma,
            '=' => Token::Equals,
            '+' => Token::Plus,
            '-' => Token::Minus,
            '*' => Token::Star,
            '/' => Token::Slash,
            '%' => Token::Percent,
            '&' => Token::Ampersand,
            '|' => Token::Pipe,
            '^' => Token::Caret,
            '~' => Token::Tilde,
            '!' => Token::Exclaim,
            '?' => Token::Question,
            '<' => Token::Lt,
            '>' => Token::Gt,
            _ => {
                // Unknown character — skip it.
                i += 1;
                continue;
            }
        });
        i += 1;
    }

    tokens
}

/// Multiply the last integer token by a factor (handles K/M/G/T suffixes).
fn multiply_last_int(tokens: &mut [Token], factor: i64) {
    for tok in tokens.iter_mut().rev() {
        if let Token::Integer(v) = tok {
            *v *= factor;
            return;
        }
    }
}

// ============================================================================
// Tests
// ============================================================================

#[cfg(test)]
mod tests {
    use super::*;

    // --- Tokenizer Tests ---

    #[test]
    fn test_tokenize_simple() {
        let tokens = tokenize("OUTPUT_FORMAT(\"elf64-x86-64\");");
        assert_eq!(tokens.len(), 5);
        assert_eq!(tokens[0], Token::OutputFormat);
        assert_eq!(tokens[1], Token::LParen);
        assert_eq!(tokens[2], Token::StringLit("elf64-x86-64".to_string()));
        assert_eq!(tokens[3], Token::RParen);
        assert_eq!(tokens[4], Token::SemiColon);
    }

    #[test]
    fn test_tokenize_integer_hex() {
        let tokens = tokenize("0x1000 0755 42");
        assert_eq!(tokens.len(), 3);
        assert_eq!(tokens[0], Token::Integer(0x1000));
        assert_eq!(tokens[1], Token::Integer(0o755));
        assert_eq!(tokens[2], Token::Integer(42));
    }

    #[test]
    fn test_tokenize_suffix_k() {
        let tokens = tokenize("256K 1M 2G");
        assert_eq!(tokens.len(), 3);
        assert_eq!(tokens[0], Token::Integer(256 * 1024));
        assert_eq!(tokens[1], Token::Integer(1 * 1024 * 1024));
        assert_eq!(tokens[2], Token::Integer(2 * 1024 * 1024 * 1024));
    }

    #[test]
    fn test_tokenize_operators() {
        let tokens = tokenize("+ - * / % << >> == != <= >= && ||");
        assert_eq!(tokens.len(), 16);
        assert_eq!(tokens[8], Token::LShift);
        assert_eq!(tokens[9], Token::RShift);
        assert_eq!(tokens[10], Token::EqEq);
        assert_eq!(tokens[11], Token::Ne);
    }

    #[test]
    fn test_tokenize_keywords() {
        let tokens = tokenize("MEMORY SECTIONS PHDRS ENTRY PROVIDE KEEP");
        assert_eq!(tokens.len(), 6);
        assert_eq!(tokens[0], Token::Memory);
        assert_eq!(tokens[1], Token::Sections);
        assert_eq!(tokens[2], Token::Phdrs);
        assert_eq!(tokens[4], Token::Provide);
        assert_eq!(tokens[5], Token::Keep);
    }

    #[test]
    fn test_tokenize_comment() {
        let tokens = tokenize("/* comment */ ENTRY(main)");
        assert_eq!(tokens.len(), 4);
        assert_eq!(tokens[0], Token::Entry);
    }

    // --- Parser Tests ---

    #[test]
    fn test_parse_output_format() {
        let mut parser = X86LinkerScript::new();
        parser.parse("OUTPUT_FORMAT(\"elf64-x86-64\");").unwrap();
        assert_eq!(
            parser.script.output_format,
            Some("elf64-x86-64".to_string())
        );
    }

    #[test]
    fn test_parse_output_arch() {
        let mut parser = X86LinkerScript::new();
        parser.parse("OUTPUT_ARCH(\"i386:x86-64\");").unwrap();
        assert_eq!(parser.script.output_arch, Some("i386:x86-64".to_string()));
    }

    #[test]
    fn test_parse_entry() {
        let mut parser = X86LinkerScript::new();
        parser.parse("ENTRY(_start);").unwrap();
        assert_eq!(parser.script.entry, Some("_start".to_string()));
    }

    #[test]
    fn test_parse_search_dir() {
        let mut parser = X86LinkerScript::new();
        parser.parse("SEARCH_DIR(\"/usr/lib\");").unwrap();
        assert_eq!(parser.script.search_dirs, vec!["/usr/lib"]);
    }

    #[test]
    fn test_parse_input() {
        let mut parser = X86LinkerScript::new();
        parser.parse("INPUT(\"crt1.o\", \"crti.o\");").unwrap();
        assert_eq!(parser.script.input_files, vec!["crt1.o", "crti.o"]);
    }

    #[test]
    fn test_parse_group() {
        let mut parser = X86LinkerScript::new();
        parser.parse("GROUP(\"libc.a\", \"libm.a\");").unwrap();
        assert_eq!(parser.script.groups.len(), 1);
        assert_eq!(parser.script.groups[0], vec!["libc.a", "libm.a"]);
    }

    #[test]
    fn test_parse_extern() {
        let mut parser = X86LinkerScript::new();
        parser.parse("EXTERN(main _init _fini);").unwrap();
        assert_eq!(parser.script.extern_symbols, vec!["main", "_init", "_fini"]);
    }

    #[test]
    fn test_parse_provide() {
        let mut parser = X86LinkerScript::new();
        parser.parse("PROVIDE(__init_array_start = .);").unwrap();
        assert_eq!(parser.script.provides.len(), 1);
        assert!(parser.script.provides[0].is_provide);
        assert_eq!(parser.script.provides[0].name, "__init_array_start");
    }

    #[test]
    fn test_parse_assert() {
        let mut parser = X86LinkerScript::new();
        parser
            .parse("ASSERT(. < 0x800000, \"text section too large\");")
            .unwrap();
        assert_eq!(parser.script.asserts.len(), 1);
        assert_eq!(parser.script.asserts[0].message, "text section too large");
    }

    #[test]
    fn test_parse_memory() {
        let mut parser = X86LinkerScript::new();
        parser
            .parse(
                "MEMORY { rom (rx) : ORIGIN = 0, LENGTH = 256K \
                 ram (rw) : ORIGIN = 0x200000, LENGTH = 1M }",
            )
            .unwrap();

        assert_eq!(parser.script.memory_regions.len(), 2);
        assert_eq!(parser.script.memory_regions[0].name, "rom");
        assert_eq!(parser.script.memory_regions[0].attributes, "rx");
        assert_eq!(parser.script.memory_regions[1].name, "ram");
        assert_eq!(parser.script.memory_regions[1].attributes, "rw");
    }

    #[test]
    fn test_parse_sections_basic() {
        let mut parser = X86LinkerScript::new();
        parser
            .parse("SECTIONS { .text : { *(.text) } .data : { *(.data) } }")
            .unwrap();

        assert_eq!(parser.script.sections.len(), 2);
        assert_eq!(parser.script.sections[0].name, Some(".text".to_string()));
        assert_eq!(parser.script.sections[1].name, Some(".data".to_string()));
    }

    #[test]
    fn test_parse_sections_with_keep() {
        let mut parser = X86LinkerScript::new();
        parser
            .parse("SECTIONS { .init_array : { KEEP(*(.init_array)) } }")
            .unwrap();

        assert_eq!(parser.script.sections.len(), 1);
        assert!(parser.script.sections[0].input_sections[0].keep);
    }

    #[test]
    fn test_parse_sections_with_at() {
        let mut parser = X86LinkerScript::new();
        parser
            .parse("SECTIONS { .text 0x1000 : AT(0x2000) { *(.text) } }")
            .unwrap();

        let section = &parser.script.sections[0];
        assert!(section.lma.is_some());
    }

    #[test]
    fn test_parse_sections_with_align() {
        let mut parser = X86LinkerScript::new();
        parser
            .parse("SECTIONS { .data : ALIGN(16) { *(.data) } }")
            .unwrap();

        let section = &parser.script.sections[0];
        assert!(section.alignment.is_some());
    }

    // --- Expression Evaluator Tests ---

    #[test]
    fn test_eval_integer() {
        let expr = Expression::Integer(42);
        let ctx = EvalContext::default();
        assert_eq!(
            evaluate_expression(&expr, &ctx).unwrap(),
            EvalResult::Absolute(42)
        );
    }

    #[test]
    fn test_eval_location_counter() {
        let mut ctx = EvalContext::default();
        ctx.location_counter = 0x1000;
        assert_eq!(
            evaluate_expression(&Expression::LocationCounter, &ctx).unwrap(),
            EvalResult::Absolute(0x1000)
        );
    }

    #[test]
    fn test_eval_add() {
        let expr = Expression::BinaryOp {
            op: BinaryOpKind::Add,
            lhs: Box::new(Expression::Integer(10)),
            rhs: Box::new(Expression::Integer(20)),
        };
        let ctx = EvalContext::default();
        assert_eq!(
            evaluate_expression(&expr, &ctx).unwrap(),
            EvalResult::Absolute(30)
        );
    }

    #[test]
    fn test_eval_mul() {
        let expr = Expression::BinaryOp {
            op: BinaryOpKind::Mul,
            lhs: Box::new(Expression::Integer(7)),
            rhs: Box::new(Expression::Integer(6)),
        };
        assert_eq!(
            evaluate_expression(&expr, &EvalContext::default()).unwrap(),
            EvalResult::Absolute(42)
        );
    }

    #[test]
    fn test_eval_comparison() {
        let expr = Expression::BinaryOp {
            op: BinaryOpKind::Lt,
            lhs: Box::new(Expression::Integer(5)),
            rhs: Box::new(Expression::Integer(10)),
        };
        assert_eq!(
            evaluate_expression(&expr, &EvalContext::default()).unwrap(),
            EvalResult::Boolean(true)
        );
    }

    #[test]
    fn test_eval_ternary() {
        let expr = Expression::Ternary {
            condition: Box::new(Expression::Integer(1)),
            true_expr: Box::new(Expression::Integer(100)),
            false_expr: Box::new(Expression::Integer(200)),
        };
        assert_eq!(
            evaluate_expression(&expr, &EvalContext::default()).unwrap(),
            EvalResult::Absolute(100)
        );
    }

    #[test]
    fn test_eval_ternary_false() {
        let expr = Expression::Ternary {
            condition: Box::new(Expression::Integer(0)),
            true_expr: Box::new(Expression::Integer(100)),
            false_expr: Box::new(Expression::Integer(200)),
        };
        assert_eq!(
            evaluate_expression(&expr, &EvalContext::default()).unwrap(),
            EvalResult::Absolute(200)
        );
    }

    #[test]
    fn test_eval_function_align() {
        let expr = Expression::FunctionCall {
            name: "ALIGN".to_string(),
            args: vec![Expression::Integer(0x1003), Expression::Integer(0x10)],
        };
        assert_eq!(
            evaluate_expression(&expr, &EvalContext::default()).unwrap(),
            EvalResult::Absolute(0x1010)
        );
    }

    #[test]
    fn test_eval_function_max() {
        let expr = Expression::FunctionCall {
            name: "MAX".to_string(),
            args: vec![
                Expression::Integer(10),
                Expression::Integer(50),
                Expression::Integer(30),
            ],
        };
        assert_eq!(
            evaluate_expression(&expr, &EvalContext::default()).unwrap(),
            EvalResult::Absolute(50)
        );
    }

    #[test]
    fn test_eval_function_min() {
        let expr = Expression::FunctionCall {
            name: "MIN".to_string(),
            args: vec![
                Expression::Integer(10),
                Expression::Integer(5),
                Expression::Integer(30),
            ],
        };
        assert_eq!(
            evaluate_expression(&expr, &EvalContext::default()).unwrap(),
            EvalResult::Absolute(5)
        );
    }

    #[test]
    fn test_eval_function_log2ceil() {
        let expr = Expression::FunctionCall {
            name: "LOG2CEIL".to_string(),
            args: vec![Expression::Integer(256)],
        };
        assert_eq!(
            evaluate_expression(&expr, &EvalContext::default()).unwrap(),
            EvalResult::Absolute(8)
        );
    }

    #[test]
    fn test_eval_function_defined_true() {
        let mut ctx = EvalContext::default();
        ctx.defined_symbols.insert("main".to_string());
        let expr = Expression::Defined("main".to_string());
        assert_eq!(
            evaluate_expression(&expr, &ctx).unwrap(),
            EvalResult::Boolean(true)
        );
    }

    #[test]
    fn test_eval_function_defined_false() {
        let ctx = EvalContext::default();
        let expr = Expression::Defined("nonexistent".to_string());
        assert_eq!(
            evaluate_expression(&expr, &ctx).unwrap(),
            EvalResult::Boolean(false)
        );
    }

    #[test]
    fn test_eval_section_attr() {
        let mut ctx = EvalContext::default();
        ctx.section_addrs.insert(".text".to_string(), 0x1000);
        ctx.section_sizes.insert(".text".to_string(), 0x500);

        let addr_expr = Expression::SectionAttribute {
            section_name: ".text".to_string(),
            attribute: SectionAttrKind::Addr,
        };
        assert_eq!(
            evaluate_expression(&addr_expr, &ctx).unwrap(),
            EvalResult::Absolute(0x1000)
        );

        let size_expr = Expression::SectionAttribute {
            section_name: ".text".to_string(),
            attribute: SectionAttrKind::SizeOf,
        };
        assert_eq!(
            evaluate_expression(&size_expr, &ctx).unwrap(),
            EvalResult::Absolute(0x500)
        );
    }

    #[test]
    fn test_eval_memory_attr() {
        let mut ctx = EvalContext::default();
        ctx.memory_origins.insert("ram".to_string(), 0x200000);
        ctx.memory_lengths.insert("ram".to_string(), 0x100000);

        let origin_expr = Expression::MemoryRegionAttr {
            region_name: "ram".to_string(),
            attribute: MemoryRegionAttrKind::Origin,
        };
        assert_eq!(
            evaluate_expression(&origin_expr, &ctx).unwrap(),
            EvalResult::Absolute(0x200000)
        );

        let length_expr = Expression::MemoryRegionAttr {
            region_name: "ram".to_string(),
            attribute: MemoryRegionAttrKind::Length,
        };
        assert_eq!(
            evaluate_expression(&length_expr, &ctx).unwrap(),
            EvalResult::Absolute(0x100000)
        );
    }

    #[test]
    fn test_eval_data_segment_align() {
        let mut ctx = EvalContext::default();
        ctx.location_counter = 0x1200;
        let expr = Expression::FunctionCall {
            name: "DATA_SEGMENT_ALIGN".to_string(),
            args: vec![Expression::Integer(0x1000), Expression::Integer(0x1000)],
        };
        assert_eq!(
            evaluate_expression(&expr, &ctx).unwrap(),
            EvalResult::Absolute(0x2000)
        );
    }

    #[test]
    fn test_eval_unary_neg() {
        let expr = Expression::UnaryOp {
            op: UnaryOpKind::Neg,
            expr: Box::new(Expression::Integer(42)),
        };
        assert_eq!(
            evaluate_expression(&expr, &EvalContext::default()).unwrap(),
            EvalResult::Absolute(-42)
        );
    }

    #[test]
    fn test_eval_unary_bitnot() {
        let expr = Expression::UnaryOp {
            op: UnaryOpKind::BitNot,
            expr: Box::new(Expression::Integer(0)),
        };
        assert_eq!(
            evaluate_expression(&expr, &EvalContext::default()).unwrap(),
            EvalResult::Absolute(-1)
        );
    }

    #[test]
    fn test_eval_div_by_zero() {
        let expr = Expression::BinaryOp {
            op: BinaryOpKind::Div,
            lhs: Box::new(Expression::Integer(10)),
            rhs: Box::new(Expression::Integer(0)),
        };
        assert!(evaluate_expression(&expr, &EvalContext::default()).is_err());
    }

    #[test]
    fn test_eval_mod_by_zero() {
        let expr = Expression::BinaryOp {
            op: BinaryOpKind::Mod,
            lhs: Box::new(Expression::Integer(10)),
            rhs: Box::new(Expression::Integer(0)),
        };
        assert!(evaluate_expression(&expr, &EvalContext::default()).is_err());
    }

    #[test]
    fn test_full_script_parse() {
        let script = r#"
            OUTPUT_FORMAT("elf64-x86-64");
            OUTPUT_ARCH("i386:x86-64");
            ENTRY(_start);

            MEMORY {
                rom (rx) : ORIGIN = 0, LENGTH = 256K
                ram (rw) : ORIGIN = 0x200000, LENGTH = 1M
            }

            SECTIONS {
                . = 0x1000;
                .text : {
                    *(.text)
                    *(.text.*)
                } >rom

                .rodata : {
                    *(.rodata)
                } >rom

                .data : {
                    *(.data)
                } >ram

                .bss : {
                    *(.bss)
                } >ram

                PROVIDE(__bss_end = .);
                ASSERT(. < 0x300000, "sections overflow RAM");
            }
        "#;

        let mut parser = X86LinkerScript::new();
        let parsed = parser.parse(script).unwrap();

        assert_eq!(parsed.output_format, Some("elf64-x86-64".to_string()));
        assert_eq!(parsed.output_arch, Some("i386:x86-64".to_string()));
        assert_eq!(parsed.entry, Some("_start".to_string()));
        assert_eq!(parsed.memory_regions.len(), 2);
        assert!(parsed.sections.len() >= 3);
        assert_eq!(parsed.provides.len(), 1);
        assert_eq!(parsed.asserts.len(), 1);
    }

    #[test]
    fn test_section_layout_computation() {
        let script = r#"
            SECTIONS {
                .text : { *(.text) }
                .data : { *(.data) }
            }
        "#;

        let mut parser = X86LinkerScript::new();
        parser.parse(script).unwrap();

        assert!(parser.section_layout.contains_key(".text"));
        assert!(parser.section_layout.contains_key(".data"));
    }

    #[test]
    fn test_precedence() {
        // 2 + 3 * 4 should be 14, not 20
        let expr = Expression::BinaryOp {
            op: BinaryOpKind::Add,
            lhs: Box::new(Expression::Integer(2)),
            rhs: Box::new(Expression::BinaryOp {
                op: BinaryOpKind::Mul,
                lhs: Box::new(Expression::Integer(3)),
                rhs: Box::new(Expression::Integer(4)),
            }),
        };
        assert_eq!(
            evaluate_expression(&expr, &EvalContext::default()).unwrap(),
            EvalResult::Absolute(14)
        );
    }
}