perl_semantic_analyzer/analysis/

declaration.rs

//! Declaration Provider for LSP
//!
//! Provides go-to-declaration functionality for finding where symbols are declared.
//! Supports LocationLink for enhanced client experience.

use crate::ast::{Node, NodeKind};
use crate::workspace_index::{SymKind, SymbolKey};
use rustc_hash::FxHashMap;
use std::sync::Arc;

/// Parent-map from child node to parent node, stored as raw pointers.
///
/// # Safety Invariant
///
/// Every `*const Node` in this map (both keys and values) must be a pointer
/// obtained by casting a shared reference (`&Node`) that was derived from the
/// **same** `Arc<Node>` tree that was passed to [`DeclarationProvider::build_parent_map`].
/// The pointed-to nodes must remain alive for the entire duration of any code
/// that inspects the map.
///
/// Raw pointers are used as **hash keys only** for O(1) identity-based lookup.
/// They are **never** dereferenced directly through this map.  Safe references
/// are recovered via the companion `node_lookup` map
/// (`FxHashMap<*const Node, &Node>`) that re-derives `&Node` from the live
/// `Arc<Node>` tree at call time.
///
/// # Ownership and Lifetime
///
/// The `Arc<Node>` that backs the tree must outlive every `&ParentMap` borrow.
/// In the LSP server this is guaranteed because both the `Arc<Node>` and the
/// `ParentMap` are stored together in `DocumentState`, guarded by a
/// `parking_lot::Mutex`.
///
/// # Thread Safety
///
/// `*const Node` is `!Send + !Sync`.  Consequently `ParentMap` is `!Send +
/// !Sync` and must remain on the thread that owns the `Arc<Node>` tree.
/// LSP request handlers satisfy this requirement because they process each
/// request synchronously within a single thread context.
pub type ParentMap = FxHashMap<*const Node, *const Node>;

/// Provider for finding declarations in Perl source code.
///
/// This provider implements LSP go-to-declaration functionality with enhanced
/// workspace navigation support. Maintains ≤1ms response time for symbol lookup
/// operations through optimized AST traversal and parent mapping.
///
/// # Performance Characteristics
/// - Declaration resolution: <500μs for typical Perl files
/// - Memory usage: O(n) where n is AST node count
/// - Parent map validation: Debug-only with cycle detection
///
/// # LSP Workflow Integration
/// Parse → Index → Navigate → Complete → Analyze pipeline integration:
/// 1. Parse: AST generation from Perl source
/// 2. Index: Symbol table construction with qualified name resolution
/// 3. Navigate: Declaration provider for go-to-definition requests
/// 4. Complete: Symbol context for completion providers
/// 5. Analyze: Cross-reference analysis for workspace refactoring
pub struct DeclarationProvider<'a> {
    /// The parsed AST for the current document
    pub ast: Arc<Node>,
    content: String,
    document_uri: String,
    parent_map: Option<&'a ParentMap>,
    doc_version: i32,
}

/// Represents a location link from origin to target
#[derive(Debug, Clone)]
pub struct LocationLink {
    /// The range of the symbol being targeted at the origin
    pub origin_selection_range: (usize, usize),
    /// The target URI
    pub target_uri: String,
    /// The full range of the target declaration
    pub target_range: (usize, usize),
    /// The range to select in the target (e.g., just the name)
    pub target_selection_range: (usize, usize),
}

impl<'a> DeclarationProvider<'a> {
    /// Creates a new declaration provider for the given AST and document.
    ///
    /// # Arguments
    /// * `ast` - The parsed AST tree for declaration lookup
    /// * `content` - The source code content for text extraction
    /// * `document_uri` - The URI of the document being analyzed
    ///
    /// # Performance
    /// - Initialization: <10μs for typical Perl files
    /// - Memory overhead: Minimal, shares AST reference
    ///
    /// # Examples
    /// ```rust,ignore
    /// use perl_parser::declaration::DeclarationProvider;
    /// use perl_parser::ast::Node;
    /// use std::sync::Arc;
    ///
    /// let ast = Arc::new(Node::new_root());
    /// let provider = DeclarationProvider::new(
    ///     ast,
    ///     "package MyPackage; sub example { }".to_string(),
    ///     "file:///path/to/file.pl".to_string()
    /// );
    /// ```
    pub fn new(ast: Arc<Node>, content: String, document_uri: String) -> Self {
        Self {
            ast,
            content,
            document_uri,
            parent_map: None,
            doc_version: 0, // Default to version 0 for simple use cases
        }
    }

    /// Configures the provider with a pre-built parent map for enhanced traversal.
    ///
    /// The parent map enables efficient upward AST traversal for scope resolution
    /// and context analysis. Debug builds include comprehensive validation.
    ///
    /// # Arguments
    /// * `parent_map` - Mapping from child nodes to their parents
    ///
    /// # Performance
    /// - Parent lookup: O(1) hash table access
    /// - Validation overhead: Debug-only, ~100μs for large files
    ///
    /// # Panics
    /// In debug builds, panics if:
    /// - Parent map is empty for non-trivial AST
    /// - Root node has a parent (cycle detection)
    /// - Cycles detected in parent relationships
    ///
    /// # Examples
    /// ```rust,ignore
    /// use perl_parser::declaration::{DeclarationProvider, ParentMap};
    /// use perl_parser::ast::Node;
    /// use std::sync::Arc;
    ///
    /// let ast = Arc::new(Node::new_root());
    /// let mut parent_map = ParentMap::default();
    /// DeclarationProvider::build_parent_map(&ast, &mut parent_map, None);
    ///
    /// let provider = DeclarationProvider::new(
    ///     ast, "content".to_string(), "uri".to_string()
    /// ).with_parent_map(&parent_map);
    /// ```
    pub fn with_parent_map(mut self, parent_map: &'a ParentMap) -> Self {
        #[cfg(debug_assertions)]
        {
            // If the AST has more than the root node, an empty map is suspicious.
            // (Root has no parent, so a truly trivial AST may legitimately produce 0.)
            debug_assert!(
                !parent_map.is_empty(),
                "DeclarationProvider: empty ParentMap (did you forget to rebuild after AST refresh?)"
            );

            // Root sanity check - root must have no parent
            let root_ptr = &*self.ast as *const _;
            debug_assert!(
                !parent_map.contains_key(&root_ptr),
                "Root node must have no parent in the parent map"
            );

            // Cycle detection - ensure no node is its own ancestor
            Self::debug_assert_no_cycles(parent_map);
        }
        self.parent_map = Some(parent_map);
        self
    }

    /// Sets the document version for staleness detection.
    ///
    /// Version tracking ensures the provider operates on current data
    /// and prevents usage after document updates in LSP workflows.
    ///
    /// # Arguments
    /// * `version` - Document version number from LSP client
    ///
    /// # Performance
    /// - Version check: <1μs per operation
    /// - Debug validation: Additional consistency checks
    ///
    /// # Examples
    /// ```rust,ignore
    /// use perl_parser::declaration::DeclarationProvider;
    /// use perl_parser::ast::Node;
    /// use std::sync::Arc;
    ///
    /// let provider = DeclarationProvider::new(
    ///     Arc::new(Node::new_root()),
    ///     "content".to_string(),
    ///     "uri".to_string()
    /// ).with_doc_version(42);
    /// ```
    pub fn with_doc_version(mut self, version: i32) -> Self {
        self.doc_version = version;
        self
    }

    /// Returns `true` if this provider is still fresh (version matches).
    ///
    /// In both debug and release builds: logs a warning and returns `false` on mismatch so
    /// callers can return `None` early instead of operating on a stale AST snapshot.
    #[inline]
    #[track_caller]
    fn is_fresh(&self, current_version: i32) -> bool {
        if self.doc_version != current_version {
            tracing::warn!(
                provider_version = self.doc_version,
                current_version,
                "DeclarationProvider used after AST refresh — returning empty result"
            );
            return false;
        }
        true
    }

    /// Debug-only cycle detection for parent map
    #[cfg(debug_assertions)]
    fn debug_assert_no_cycles(parent_map: &ParentMap) {
        // For each node in the map, climb up to ensure we don't hit a cycle
        let cap = parent_map.len() + 1; // Max depth before assuming cycle

        for (&child, _) in parent_map.iter() {
            let mut current = child;
            let mut depth = 0;

            while depth < cap {
                if let Some(&parent) = parent_map.get(&current) {
                    current = parent;
                    depth += 1;
                } else {
                    // Reached a node with no parent (root), no cycle
                    break;
                }
            }

            // If we exhausted the cap, we have a cycle
            if depth >= cap {
                eprintln!(
                    "Cycle detected in ParentMap - node is its own ancestor (depth limit {})",
                    cap
                );
                break;
            }
        }
    }

    /// Build a parent map for efficient scope walking
    /// Builds a parent map for efficient upward AST traversal.
    ///
    /// Recursively traverses the AST to construct a mapping from each node
    /// to its parent, enabling O(1) parent lookups for scope resolution.
    ///
    /// # Arguments
    /// * `node` - Current node to process
    /// * `map` - Mutable parent map to populate
    /// * `parent` - Parent of the current node (None for root)
    ///
    /// # Performance
    /// - Time complexity: O(n) where n is node count
    /// - Space complexity: O(n) for parent pointers
    /// - Typical build time: <100μs for 1000-node AST
    ///
    /// # Safety
    /// Uses raw pointers for performance. Safe as long as AST nodes
    /// remain valid during provider lifetime.
    ///
    /// # Examples
    /// ```rust,ignore
    /// use perl_parser::declaration::{DeclarationProvider, ParentMap};
    /// use perl_parser::ast::Node;
    ///
    /// let ast = Node::new_root();
    /// let mut parent_map = ParentMap::default();
    /// DeclarationProvider::build_parent_map(&ast, &mut parent_map, None);
    /// ```
    pub fn build_parent_map(node: &Node, map: &mut ParentMap, parent: Option<*const Node>) {
        if let Some(p) = parent {
            // SAFETY invariant for the ParentMap:
            //
            // 1. `node` is a shared reference (`&Node`) obtained from a live `Arc<Node>`.
            //    Casting it to `*const Node` produces a pointer that is valid for the
            //    lifetime of that `Arc`.
            //
            // 2. `p` (the parent pointer) was obtained by the same cast in the previous
            //    recursive frame, so it satisfies the same validity guarantee.
            //
            // 3. Neither pointer is **ever** dereferenced through this map.  The map stores
            //    raw pointers purely as identity keys.  Callers that need to follow a parent
            //    pointer back to a `&Node` must go through `build_node_lookup_map`, which
            //    re-derives safe references from the same live `Arc<Node>` tree.
            //
            // 4. The caller (LSP runtime) is responsible for ensuring the `Arc<Node>` tree
            //    remains alive for at least as long as any `&ParentMap` borrow.  In the LSP
            //    server both the `Arc` and the `ParentMap` live inside `DocumentState`,
            //    guarded by the same `parking_lot::Mutex`.
            //
            // 5. No interior mutability is introduced: `node` is not modified during
            //    traversal.  The `ParentMap` itself is an exclusive (`&mut`) borrow during
            //    construction and transitions to a shared borrow (`&`) afterwards.
            map.insert(node as *const _, p);
        }

        for child in Self::get_children_static(node) {
            // SAFETY: `child` is a child reference of `node`, both living in the same
            // `Arc<Node>` allocation.  The same invariant from above applies.
            Self::build_parent_map(child, map, Some(node as *const _));
        }
    }

    /// Find the declaration of the symbol at the given position
    pub fn find_declaration(
        &self,
        offset: usize,
        current_version: i32,
    ) -> Option<Vec<LocationLink>> {
        // Guard against stale provider usage after AST refresh (both debug and release)
        if !self.is_fresh(current_version) {
            return None;
        }

        // Find the node at the cursor position
        let node = self.find_node_at_offset(&self.ast, offset)?;

        // Check what kind of node we're on
        match &node.kind {
            NodeKind::Variable { name, .. } => self.find_variable_declaration(node, name),
            NodeKind::FunctionCall { name, .. } => self.find_subroutine_declaration(node, name),
            NodeKind::MethodCall { method, object, .. } => {
                self.find_method_declaration(node, method, object)
            }
            NodeKind::IndirectCall { method, object, .. } => {
                // Handle indirect calls (e.g., "move $obj 10, 20" or "new Class")
                self.find_method_declaration(node, method, object)
            }
            NodeKind::Identifier { name } => self.find_identifier_declaration(node, name),
            _ => None,
        }
    }

    /// Find variable declaration using scope-aware lookup
    fn find_variable_declaration(&self, usage: &Node, var_name: &str) -> Option<Vec<LocationLink>> {
        // Walk upwards through scopes to find the nearest declaration
        // SAFETY: `usage` is a shared reference into the `Arc<Node>` AST tree held by
        // `DeclarationProvider<'a>`. The raw pointer is used only as a HashMap key for O(1)
        // parent lookup and is never dereferenced directly; lookups go through `build_node_lookup_map`
        // which re-derives safe `&Node` references from the same Arc tree.
        let mut current_ptr: *const Node = usage as *const _;

        // Build temporary parent map if not provided (for testing)
        let temp_parent_map;
        let parent_map = if let Some(pm) = self.parent_map {
            pm
        } else {
            temp_parent_map = {
                let mut map = FxHashMap::default();
                Self::build_parent_map(&self.ast, &mut map, None);
                map
            };
            &temp_parent_map
        };
        let node_lookup = self.build_node_lookup_map();

        while let Some(&parent_ptr) = parent_map.get(&current_ptr) {
            let Some(parent) = node_lookup.get(&parent_ptr).copied() else {
                break;
            };

            // Check siblings before this node in the current scope
            for child in self.get_children(parent) {
                // Stop when we reach or pass the usage node
                if child.location.start >= usage.location.start {
                    break;
                }

                // Check if this is a variable declaration matching our name
                if let NodeKind::VariableDeclaration { variable, .. } = &child.kind {
                    if let NodeKind::Variable { name, .. } = &variable.kind {
                        if name == var_name {
                            return Some(vec![LocationLink {
                                origin_selection_range: (usage.location.start, usage.location.end),
                                target_uri: self.document_uri.clone(),
                                target_range: (child.location.start, child.location.end),
                                target_selection_range: (
                                    variable.location.start,
                                    variable.location.end,
                                ),
                            }]);
                        }
                    }
                }

                // Also check variable list declarations
                if let NodeKind::VariableListDeclaration { variables, .. } = &child.kind {
                    for var in variables {
                        if let NodeKind::Variable { name, .. } = &var.kind {
                            if name == var_name {
                                return Some(vec![LocationLink {
                                    origin_selection_range: (
                                        usage.location.start,
                                        usage.location.end,
                                    ),
                                    target_uri: self.document_uri.clone(),
                                    target_range: (child.location.start, child.location.end),
                                    target_selection_range: (var.location.start, var.location.end),
                                }]);
                            }
                        }
                    }
                }
            }

            current_ptr = parent_ptr;
        }

        None
    }

    /// Find subroutine declaration
    fn find_subroutine_declaration(
        &self,
        node: &Node,
        func_name: &str,
    ) -> Option<Vec<LocationLink>> {
        // Check if the function name is package-qualified (contains ::)
        let (target_package, target_name) = if let Some(pos) = func_name.rfind("::") {
            // Split into package and function name
            let package = &func_name[..pos];
            let name = &func_name[pos + 2..];
            (Some(package), name)
        } else {
            // No package qualifier, use current package context
            (self.find_current_package(node), func_name)
        };

        // Search for subroutines with the target name
        let mut declarations = Vec::new();
        self.collect_subroutine_declarations(&self.ast, target_name, &mut declarations);

        // If we have a target package, find subs in that specific package
        if let Some(pkg_name) = target_package {
            if let Some(decl) =
                declarations.iter().find(|d| self.find_current_package(d) == Some(pkg_name))
            {
                return Some(vec![self.create_location_link(
                    node,
                    decl,
                    self.get_subroutine_name_range(decl),
                )]);
            }
        }

        // Otherwise return the first match
        if let Some(decl) = declarations.first() {
            return Some(vec![self.create_location_link(
                node,
                decl,
                self.get_subroutine_name_range(decl),
            )]);
        }

        None
    }

    /// Find method declaration with package resolution
    fn find_method_declaration(
        &self,
        node: &Node,
        method_name: &str,
        object: &Node,
    ) -> Option<Vec<LocationLink>> {
        // Try to determine the package from the object
        let package_name = match &object.kind {
            NodeKind::Identifier { name } if name.chars().next()?.is_uppercase() => {
                // Likely a package name (e.g., Foo->method)
                Some(name.as_str())
            }
            _ => None,
        };

        if let Some(pkg) = package_name {
            // Look for the method in the specific package
            let mut declarations = Vec::new();
            self.collect_subroutine_declarations(&self.ast, method_name, &mut declarations);

            if let Some(decl) =
                declarations.iter().find(|d| self.find_current_package(d) == Some(pkg))
            {
                return Some(vec![self.create_location_link(
                    node,
                    decl,
                    self.get_subroutine_name_range(decl),
                )]);
            }
        }

        // Fall back to any subroutine with this name
        self.find_subroutine_declaration(node, method_name)
    }

    /// Find declaration for an identifier
    fn find_identifier_declaration(&self, node: &Node, name: &str) -> Option<Vec<LocationLink>> {
        // Try to find as subroutine first
        if let Some(links) = self.find_subroutine_declaration(node, name) {
            return Some(links);
        }

        // Try to find as package
        let packages = self.find_package_declarations(&self.ast, name);
        if let Some(pkg) = packages.first() {
            return Some(vec![self.create_location_link(
                node,
                pkg,
                self.get_package_name_range(pkg),
            )]);
        }

        // Try to find as constant (supporting multiple forms)
        let constants = self.find_constant_declarations(&self.ast, name);
        if let Some(const_decl) = constants.first() {
            return Some(vec![self.create_location_link(
                node,
                const_decl,
                self.get_constant_name_range_for(const_decl, name),
            )]);
        }

        None
    }

    /// Find the current package context for a node
    fn find_current_package<'b>(&'b self, node: &Node) -> Option<&'b str> {
        // SAFETY: `node` is a shared reference into the `Arc<Node>` AST tree held
        // by `DeclarationProvider<'a>`.  The raw pointer is used only as a hash key
        // to query the `parent_map`; it is never dereferenced.  Safe `&Node`
        // references are recovered through `node_lookup`, which re-derives them
        // from the same live `Arc<Node>` tree.
        let mut current_ptr: *const Node = node as *const _;

        // Build temporary parent map if not provided (for testing)
        let temp_parent_map;
        let parent_map = if let Some(pm) = self.parent_map {
            pm
        } else {
            temp_parent_map = {
                let mut map = FxHashMap::default();
                Self::build_parent_map(&self.ast, &mut map, None);
                map
            };
            &temp_parent_map
        };
        let node_lookup = self.build_node_lookup_map();

        while let Some(&parent_ptr) = parent_map.get(&current_ptr) {
            let Some(parent) = node_lookup.get(&parent_ptr).copied() else {
                break;
            };

            // Check siblings before this node for package declarations
            for child in self.get_children(parent) {
                if child.location.start >= node.location.start {
                    break;
                }

                if let NodeKind::Package { name, .. } = &child.kind {
                    return Some(name.as_str());
                }
            }

            current_ptr = parent_ptr;
        }

        None
    }

    /// Create a location link
    fn create_location_link(
        &self,
        origin: &Node,
        target: &Node,
        name_range: (usize, usize),
    ) -> LocationLink {
        LocationLink {
            origin_selection_range: (origin.location.start, origin.location.end),
            target_uri: self.document_uri.clone(),
            target_range: (target.location.start, target.location.end),
            target_selection_range: name_range,
        }
    }

    // Helper methods

    fn find_node_at_offset<'b>(&'b self, node: &'b Node, offset: usize) -> Option<&'b Node> {
        if offset >= node.location.start && offset <= node.location.end {
            // Check children first for more specific match
            for child in self.get_children(node) {
                if let Some(found) = self.find_node_at_offset(child, offset) {
                    return Some(found);
                }
            }
            return Some(node);
        }
        None
    }

    fn collect_subroutine_declarations<'b>(
        &'b self,
        node: &'b Node,
        sub_name: &str,
        subs: &mut Vec<&'b Node>,
    ) {
        if let NodeKind::Subroutine { name, .. } = &node.kind {
            if let Some(name_str) = name {
                if name_str == sub_name {
                    subs.push(node);
                }
            }
        }

        for child in self.get_children(node) {
            self.collect_subroutine_declarations(child, sub_name, subs);
        }
    }

    fn find_package_declarations<'b>(&'b self, node: &'b Node, pkg_name: &str) -> Vec<&'b Node> {
        let mut packages = Vec::new();
        self.collect_package_declarations(node, pkg_name, &mut packages);
        packages
    }

    fn collect_package_declarations<'b>(
        &'b self,
        node: &'b Node,
        pkg_name: &str,
        packages: &mut Vec<&'b Node>,
    ) {
        if let NodeKind::Package { name, .. } = &node.kind {
            if name == pkg_name {
                packages.push(node);
            }
        }

        for child in self.get_children(node) {
            self.collect_package_declarations(child, pkg_name, packages);
        }
    }

    fn find_constant_declarations<'b>(&'b self, node: &'b Node, const_name: &str) -> Vec<&'b Node> {
        let mut constants = Vec::new();
        self.collect_constant_declarations(node, const_name, &mut constants);
        constants
    }

    /// Strip leading -options from constant args
    fn strip_constant_options<'b>(&self, args: &'b [String]) -> &'b [String] {
        let mut i = 0;
        while i < args.len() && args[i].starts_with('-') {
            i += 1;
        }
        // Also skip a comma if present after options
        if i < args.len() && args[i] == "," {
            i += 1;
        }
        &args[i..]
    }

    fn collect_constant_declarations<'b>(
        &'b self,
        node: &'b Node,
        const_name: &str,
        constants: &mut Vec<&'b Node>,
    ) {
        if let NodeKind::Use { module, args, .. } = &node.kind {
            if module == "constant" {
                // Strip leading options like -strict, -nonstrict, -force
                let stripped_args = self.strip_constant_options(args);

                // Form 1: FOO => ...
                if stripped_args.first().map(|s| s.as_str()) == Some(const_name) {
                    constants.push(node);
                    // keep scanning siblings too (there can be multiple `use constant`)
                }

                // Flattened args text once (cheap)
                let args_text = stripped_args.join(" ");

                // Form 2: { FOO => 1, BAR => 2 }
                if self.contains_name_in_hash(&args_text, const_name) {
                    constants.push(node);
                }

                // Form 3: qw(FOO BAR) / qw/FOO BAR/
                if self.contains_name_in_qw(&args_text, const_name) {
                    constants.push(node);
                }
            }
        }

        for child in self.get_children(node) {
            self.collect_constant_declarations(child, const_name, constants);
        }
    }

    /// Check if a byte is part of an ASCII identifier
    #[inline]
    fn is_ident_ascii(b: u8) -> bool {
        matches!(b, b'0'..=b'9' | b'A'..=b'Z' | b'a'..=b'z' | b'_')
    }

    /// Iterate over all qw windows in the string
    /// Handles both paired delimiters ((), [], {}, <>) and symmetric delimiters (|, !, #, etc.)
    fn for_each_qw_window<F>(&self, s: &str, mut f: F) -> bool
    where
        F: FnMut(usize, usize) -> bool,
    {
        let b = s.as_bytes();
        let mut i = 0;
        while i + 1 < b.len() {
            // find literal "qw"
            if b[i] == b'q' && b[i + 1] == b'w' {
                let mut j = i + 2;

                // allow whitespace between qw and delimiter
                while j < b.len() && (b[j] as char).is_ascii_whitespace() {
                    j += 1;
                }
                if j >= b.len() {
                    break;
                }

                let open = b[j] as char;

                // "qwerty" guard: next non-ws must be a NON-word delimiter
                // (i.e., not [A-Za-z0-9_])
                if open.is_ascii_alphanumeric() || open == '_' {
                    i += 1;
                    continue;
                }

                // choose closing delimiter
                let close = match open {
                    '(' => ')',
                    '[' => ']',
                    '{' => '}',
                    '<' => '>',
                    _ => open, // symmetric delimiter (|, !, #, /, ~, ...)
                };

                // advance past opener and collect until closer
                j += 1;
                let start = j;
                while j < b.len() && (b[j] as char) != close {
                    j += 1;
                }
                if j <= b.len() {
                    // Found the closing delimiter
                    if f(start, j) {
                        return true;
                    }
                    // continue scanning after the closer
                    i = j + 1;
                    continue;
                } else {
                    // unclosed; stop scanning
                    break;
                }
            }

            i += 1;
        }
        false
    }

    /// Iterate over all {...} pairs in the string
    fn for_each_brace_window<F>(&self, s: &str, mut f: F) -> bool
    where
        F: FnMut(usize, usize) -> bool,
    {
        let b = s.as_bytes();
        let mut i = 0;
        while i < b.len() {
            if b[i] == b'{' {
                let start = i + 1;
                let mut nesting = 1;
                let mut j = i + 1;
                while j < b.len() {
                    match b[j] {
                        b'{' => nesting += 1,
                        b'}' => {
                            nesting -= 1;
                            if nesting == 0 {
                                break;
                            }
                        }
                        _ => {}
                    }
                    j += 1;
                }

                if nesting == 0 {
                    // Found matching closing brace at j
                    if f(start, j) {
                        return true;
                    }
                    i = j + 1;
                    continue;
                }
            }
            i += 1;
        }
        false
    }

    fn contains_name_in_hash(&self, s: &str, name: &str) -> bool {
        // for { FOO => 1, BAR => 2 } form - check all {...} pairs
        self.for_each_brace_window(s, |start, end| {
            // only scan that slice
            self.find_word(&s[start..end], name).is_some()
        })
    }

    fn contains_name_in_qw(&self, s: &str, name: &str) -> bool {
        // looks for qw(...) / qw[...] / qw/.../ etc. with word boundaries
        self.for_each_qw_window(s, |start, end| {
            // tokens are whitespace separated
            s[start..end].split_whitespace().any(|tok| tok == name)
        })
    }

    fn find_word(&self, hay: &str, needle: &str) -> Option<(usize, usize)> {
        if needle.is_empty() {
            return None;
        }
        let mut find_from = 0;
        while let Some(hit) = hay[find_from..].find(needle) {
            let start = find_from + hit;
            let end = start + needle.len();
            let left_ok = start == 0 || !Self::is_ident_ascii(hay.as_bytes()[start - 1]);
            let right_ok = end == hay.len()
                || !Self::is_ident_ascii(*hay.as_bytes().get(end).unwrap_or(&b' '));
            if left_ok && right_ok {
                return Some((start, end));
            }
            find_from = end;
        }
        None
    }

    fn first_all_caps_word(&self, s: &str) -> Option<(usize, usize)> {
        // very small scanner: find FOO-ish
        let bytes = s.as_bytes();
        let mut i = 0;
        while i < bytes.len() {
            while i < bytes.len() && !Self::is_ident_ascii(bytes[i]) {
                i += 1;
            }
            let start = i;
            while i < bytes.len() && Self::is_ident_ascii(bytes[i]) {
                i += 1;
            }
            if start < i {
                let w = &s[start..i];
                if w.chars().all(|c| c.is_ascii_uppercase() || c.is_ascii_digit() || c == '_') {
                    return Some((start, i));
                }
            }
        }
        None
    }

    fn get_subroutine_name_range(&self, decl: &Node) -> (usize, usize) {
        if let NodeKind::Subroutine { name_span: Some(loc), .. } = &decl.kind {
            (loc.start, loc.end)
        } else {
            (decl.location.start, decl.location.end)
        }
    }

    fn get_package_name_range(&self, decl: &Node) -> (usize, usize) {
        if let NodeKind::Package { name_span, .. } = &decl.kind {
            (name_span.start, name_span.end)
        } else {
            (decl.location.start, decl.location.end)
        }
    }

    fn get_constant_name_range(&self, decl: &Node) -> (usize, usize) {
        let text = self.get_node_text(decl);

        // Prefer an exact span if we can find the first occurrence with word boundaries
        if let NodeKind::Use { args, .. } = &decl.kind {
            let best_guess = args.first().map(|s| s.as_str()).unwrap_or("");
            if let Some((lo, hi)) = self.find_word(&text, best_guess) {
                let abs_lo = decl.location.start + lo;
                let abs_hi = decl.location.start + hi;
                return (abs_lo, abs_hi);
            }
        }

        // Try any constant-looking all-caps token in the decl
        if let Some((lo, hi)) = self.first_all_caps_word(&text) {
            return (decl.location.start + lo, decl.location.start + hi);
        }

        // Fallback to whole range
        (decl.location.start, decl.location.end)
    }

    fn get_constant_name_range_for(&self, decl: &Node, name: &str) -> (usize, usize) {
        let text = self.get_node_text(decl);

        // Fast path: try to find the exact word
        if let Some((lo, hi)) = self.find_word(&text, name) {
            return (decl.location.start + lo, decl.location.start + hi);
        }

        // Try inside all qw(...) windows
        let mut found_range = None;
        self.for_each_qw_window(&text, |start, end| {
            // Find the exact token position within this qw window
            if let Some((lo, hi)) = self.find_word(&text[start..end], name) {
                found_range =
                    Some((decl.location.start + start + lo, decl.location.start + start + hi));
                true // Stop searching
            } else {
                false // Continue to next window
            }
        });
        if let Some(range) = found_range {
            return range;
        }

        // Try inside all { ... } blocks (hash form)
        self.for_each_brace_window(&text, |start, end| {
            if let Some((lo, hi)) = self.find_word(&text[start..end], name) {
                found_range =
                    Some((decl.location.start + start + lo, decl.location.start + start + hi));
                true // Stop searching
            } else {
                false // Continue to next window
            }
        });
        if let Some(range) = found_range {
            return range;
        }

        // Final fallback to heuristics
        self.get_constant_name_range(decl)
    }

    fn get_children<'b>(&self, node: &'b Node) -> Vec<&'b Node> {
        Self::get_children_static(node)
    }

    /// Build a lookup map from raw node pointers back to safe references.
    ///
    /// This map is the bridge that makes `ParentMap` safe to use: callers
    /// obtain a `*const Node` from the parent map and look it up here to
    /// recover a properly-lifetime-bounded `&Node`.  The raw pointer is
    /// used purely as an identity key — it is never dereferenced directly.
    fn build_node_lookup_map(&self) -> FxHashMap<*const Node, &Node> {
        let mut map = FxHashMap::default();
        Self::build_node_lookup(self.ast.as_ref(), &mut map);
        map
    }

    fn build_node_lookup<'b>(node: &'b Node, map: &mut FxHashMap<*const Node, &'b Node>) {
        // SAFETY: `node` is a shared reference whose lifetime `'b` is tied to
        // `self.ast` (`Arc<Node>`).  We store the address as a raw-pointer key
        // alongside the same reference as the value.  The value is the safe
        // side of this pair — it is the only route through which the pointer
        // is ever turned back into usable data.
        map.insert(node as *const Node, node);
        for child in Self::get_children_static(node) {
            Self::build_node_lookup(child, map);
        }
    }

    fn get_children_static(node: &Node) -> Vec<&Node> {
        match &node.kind {
            NodeKind::Program { statements } => statements.iter().collect(),
            NodeKind::Block { statements } => statements.iter().collect(),
            NodeKind::If { condition, then_branch, else_branch, .. } => {
                let mut children = vec![condition.as_ref(), then_branch.as_ref()];
                if let Some(else_b) = else_branch {
                    children.push(else_b.as_ref());
                }
                children
            }
            NodeKind::Binary { left, right, .. } => vec![left.as_ref(), right.as_ref()],
            NodeKind::Unary { operand, .. } => vec![operand.as_ref()],
            NodeKind::VariableDeclaration { variable, initializer, .. } => {
                let mut children = vec![variable.as_ref()];
                if let Some(init) = initializer {
                    children.push(init.as_ref());
                }
                children
            }
            NodeKind::Subroutine { signature, body, .. } => {
                let mut children = vec![body.as_ref()];
                if let Some(sig) = signature {
                    children.push(sig.as_ref());
                }
                children
            }
            NodeKind::FunctionCall { args, .. } => args.iter().collect(),
            NodeKind::MethodCall { object, args, .. } => {
                let mut children = vec![object.as_ref()];
                children.extend(args.iter());
                children
            }
            NodeKind::IndirectCall { object, args, .. } => {
                let mut children = vec![object.as_ref()];
                children.extend(args.iter());
                children
            }
            NodeKind::While { condition, body, .. } => {
                vec![condition.as_ref(), body.as_ref()]
            }
            NodeKind::For { init, condition, update, body, .. } => {
                let mut children = Vec::new();
                if let Some(i) = init {
                    children.push(i.as_ref());
                }
                if let Some(c) = condition {
                    children.push(c.as_ref());
                }
                if let Some(u) = update {
                    children.push(u.as_ref());
                }
                children.push(body.as_ref());
                children
            }
            NodeKind::Foreach { variable, list, body, .. } => {
                vec![variable.as_ref(), list.as_ref(), body.as_ref()]
            }
            NodeKind::ExpressionStatement { expression } => vec![expression.as_ref()],
            _ => vec![],
        }
    }

    /// Extracts the source code text for a given AST node.
    ///
    /// Returns the substring of the document content corresponding to
    /// the node's location range. Used for symbol name extraction and
    /// text-based analysis.
    ///
    /// # Arguments
    /// * `node` - AST node to extract text from
    ///
    /// # Performance
    /// - Time complexity: O(m) where m is node text length
    /// - Memory: Creates owned string copy
    /// - Typical latency: <10μs for identifier names
    ///
    /// # Examples
    /// ```rust,ignore
    /// use perl_parser::declaration::DeclarationProvider;
    /// use perl_parser::ast::Node;
    /// use std::sync::Arc;
    ///
    /// let provider = DeclarationProvider::new(
    ///     Arc::new(Node::new_root()),
    ///     "sub example { }".to_string(),
    ///     "uri".to_string()
    /// );
    /// // let text = provider.get_node_text(&some_node);
    /// ```
    pub fn get_node_text(&self, node: &Node) -> String {
        self.content[node.location.start..node.location.end].to_string()
    }
}

/// Extracts a symbol key from the AST node at the given cursor position.
///
/// Analyzes the AST at a specific byte offset to identify the symbol under
/// the cursor for LSP operations. Supports function calls, variable references,
/// and package-qualified symbols with full Perl syntax coverage.
///
/// # Arguments
/// * `ast` - Root AST node to search within
/// * `offset` - Byte offset in the source document
/// * `current_pkg` - Current package context for symbol resolution
///
/// # Returns
/// * `Some(SymbolKey)` - Symbol found at position with package qualification
/// * `None` - No symbol at the given position
///
/// # Performance
/// - Search time: O(log n) average case with spatial indexing
/// - Worst case: O(n) for unbalanced AST traversal
/// - Typical latency: <50μs for LSP responsiveness
///
/// # Perl Parsing Context
/// Handles complex Perl symbol patterns:
/// - Package-qualified calls: `Package::function`
/// - Bare function calls: `function` (resolved in current package)
/// - Variable references: `$var`, `@array`, `%hash`
/// - Method calls: `$obj->method`
///
/// # Examples
/// ```rust,ignore
/// use perl_parser::declaration::symbol_at_cursor;
/// use perl_parser::ast::Node;
///
/// let ast = Node::new_root();
/// let symbol = symbol_at_cursor(&ast, 42, "MyPackage");
/// if let Some(sym) = symbol {
///     println!("Found symbol: {:?}", sym);
/// }
/// ```
pub fn symbol_at_cursor(ast: &Node, offset: usize, current_pkg: &str) -> Option<SymbolKey> {
    fn collect_node_path_at_offset<'a>(
        node: &'a Node,
        offset: usize,
        path: &mut Vec<&'a Node>,
    ) -> bool {
        if offset < node.location.start || offset > node.location.end {
            return false;
        }

        path.push(node);

        for child in get_node_children(node) {
            if collect_node_path_at_offset(child, offset, path) {
                return true;
            }
        }

        true
    }

    fn find_symbol_node_at_offset(ast: &Node, offset: usize) -> Option<&Node> {
        let mut path = Vec::new();
        if !collect_node_path_at_offset(ast, offset, &mut path) {
            return None;
        }

        path.iter()
            .rev()
            .copied()
            .find(|node| {
                matches!(
                    node.kind,
                    NodeKind::Variable { .. }
                        | NodeKind::FunctionCall { .. }
                        | NodeKind::Subroutine { .. }
                        | NodeKind::MethodCall { .. }
                        | NodeKind::Use { .. }
                )
            })
            .or_else(|| path.last().copied())
    }

    fn node_variable_name(node: &Node) -> Option<&str> {
        if let NodeKind::Variable { name, .. } = &node.kind { Some(name.as_str()) } else { None }
    }

    fn looks_like_package_name(name: &str) -> bool {
        name.contains("::") || name.chars().next().is_some_and(|ch| ch.is_ascii_uppercase())
    }

    fn infer_receiver_package(
        object: &Node,
        current_pkg: &str,
        receiver_packages: &std::collections::HashMap<String, String>,
    ) -> Option<String> {
        if let NodeKind::Identifier { name } = &object.kind {
            return Some(name.clone());
        }

        if let Some(name) = node_variable_name(object) {
            if let Some(package_name) = receiver_packages.get(name) {
                return Some(package_name.clone());
            }

            if matches!(name, "self" | "this" | "class") {
                return Some(current_pkg.to_string());
            }

            if looks_like_package_name(name) {
                return Some(name.to_string());
            }
        }

        None
    }

    fn infer_constructor_package(
        rhs: &Node,
        current_pkg: &str,
        receiver_packages: &std::collections::HashMap<String, String>,
    ) -> Option<String> {
        match &rhs.kind {
            NodeKind::MethodCall { method, object, .. } if method == "new" => {
                infer_receiver_package(object, current_pkg, receiver_packages)
            }
            NodeKind::FunctionCall { name, .. } => {
                name.rsplit_once("::").map(|(package_name, _)| package_name.to_string())
            }
            _ => None,
        }
    }

    fn record_receiver_assignment(
        node: &Node,
        offset: usize,
        current_pkg: &str,
        receiver_packages: &mut std::collections::HashMap<String, String>,
    ) {
        if node.location.start > offset {
            return;
        }

        if node.location.end <= offset {
            match &node.kind {
                NodeKind::VariableDeclaration { variable, initializer, .. } => {
                    if let (Some(variable_name), Some(initializer)) =
                        (node_variable_name(variable), initializer.as_ref())
                    {
                        if let Some(package_name) =
                            infer_constructor_package(initializer, current_pkg, receiver_packages)
                        {
                            receiver_packages.insert(variable_name.to_string(), package_name);
                        }
                    }
                }
                NodeKind::Assignment { lhs, rhs, .. } => {
                    if let Some(variable_name) = node_variable_name(lhs) {
                        if let Some(package_name) =
                            infer_constructor_package(rhs, current_pkg, receiver_packages)
                        {
                            receiver_packages.insert(variable_name.to_string(), package_name);
                        }
                    }
                }
                _ => {}
            }
        }

        for child in get_node_children(node) {
            if child.location.start <= offset {
                record_receiver_assignment(child, offset, current_pkg, receiver_packages);
            }
        }
    }

    let node = find_symbol_node_at_offset(ast, offset)?;
    match &node.kind {
        NodeKind::Variable { sigil, name } => {
            // Variable already has sigil separated
            let sigil_char = sigil.chars().next();
            Some(SymbolKey {
                pkg: current_pkg.into(),
                name: name.clone().into(),
                sigil: sigil_char,
                kind: SymKind::Var,
            })
        }
        NodeKind::FunctionCall { name, .. } => {
            let (pkg, bare) = if let Some(idx) = name.rfind("::") {
                (&name[..idx], &name[idx + 2..])
            } else {
                (current_pkg, name.as_str())
            };
            Some(SymbolKey { pkg: pkg.into(), name: bare.into(), sigil: None, kind: SymKind::Sub })
        }
        NodeKind::Subroutine { name: Some(name), .. } => {
            let (pkg, bare) = if let Some(idx) = name.rfind("::") {
                (&name[..idx], &name[idx + 2..])
            } else {
                (current_pkg, name.as_str())
            };
            Some(SymbolKey { pkg: pkg.into(), name: bare.into(), sigil: None, kind: SymKind::Sub })
        }
        NodeKind::MethodCall { object, method, .. } => {
            let mut receiver_packages = std::collections::HashMap::new();
            record_receiver_assignment(ast, offset, current_pkg, &mut receiver_packages);
            let pkg = infer_receiver_package(object, current_pkg, &receiver_packages)
                .unwrap_or_else(|| current_pkg.to_string());
            Some(SymbolKey {
                pkg: pkg.into(),
                name: method.clone().into(),
                sigil: None,
                kind: SymKind::Sub,
            })
        }
        NodeKind::Use { module, .. } => {
            // When cursor is on a `use Module::Name` statement, resolve to the package
            Some(SymbolKey {
                pkg: module.clone().into(),
                name: module.clone().into(),
                sigil: None,
                kind: SymKind::Pack,
            })
        }
        _ => None,
    }
}

/// Determines the current package context at the given offset.
///
/// Scans the AST backwards from the offset to find the most recent
/// package declaration, providing proper context for symbol resolution
/// in Perl's package-based namespace system.
///
/// # Arguments
/// * `ast` - Root AST node to search within
/// * `offset` - Byte offset in the source document
///
/// # Returns
/// Package name as string slice, defaults to "main" if no package found
///
/// # Performance
/// - Search time: O(n) worst case, O(log n) typical
/// - Memory: Returns borrowed string slice (zero-copy)
/// - Caching: Results suitable for per-request caching
///
/// # Perl Parsing Context
/// Perl package semantics:
/// - `package Foo;` declarations change current namespace
/// - Scope continues until next package declaration or EOF
/// - Default package is "main" when no explicit declaration
/// - Package names follow Perl identifier rules (`::`-separated)
///
/// # Examples
/// ```rust,ignore
/// use perl_parser::declaration::current_package_at;
/// use perl_parser::ast::Node;
///
/// let ast = Node::new_root();
/// let pkg = current_package_at(&ast, 100);
/// println!("Current package: {}", pkg);
/// ```
pub fn current_package_at(ast: &Node, offset: usize) -> &str {
    // Find the nearest package declaration before the offset
    fn scan<'a>(node: &'a Node, offset: usize, last: &mut Option<&'a str>) {
        if let NodeKind::Package { name, .. } = &node.kind {
            if node.location.start <= offset {
                *last = Some(name.as_str());
            }
        }
        for child in get_node_children(node) {
            if child.location.start <= offset {
                scan(child, offset, last);
            }
        }
    }

    let mut last_pkg: Option<&str> = None;
    scan(ast, offset, &mut last_pkg);
    last_pkg.unwrap_or("main")
}

/// Finds the most specific AST node containing the given byte offset.
///
/// Performs recursive descent through the AST to locate the deepest node
/// that encompasses the specified position. Essential for cursor-based
/// LSP operations like go-to-definition and hover.
///
/// # Arguments
/// * `node` - AST node to search within (typically root)
/// * `offset` - Byte offset in the source document
///
/// # Returns
/// * `Some(&Node)` - Deepest node containing the offset
/// * `None` - Offset is outside the node's range
///
/// # Performance
/// - Search time: O(log n) average, O(n) worst case
/// - Memory: Zero allocations, returns borrowed reference
/// - Spatial locality: Optimized for sequential offset queries
///
/// # LSP Integration
/// Core primitive for:
/// - Hover information: Find node for symbol details
/// - Go-to-definition: Identify symbol under cursor
/// - Completion: Determine context for suggestions
/// - Diagnostics: Map error positions to AST nodes
///
/// # Examples
/// ```rust,ignore
/// use perl_parser::declaration::find_node_at_offset;
/// use perl_parser::ast::Node;
///
/// let ast = Node::new_root();
/// if let Some(node) = find_node_at_offset(&ast, 42) {
///     println!("Found node: {:?}", node.kind);
/// }
/// ```
pub fn find_node_at_offset(node: &Node, offset: usize) -> Option<&Node> {
    if offset < node.location.start || offset > node.location.end {
        return None;
    }

    // Check children first for more specific match
    let children = get_node_children(node);
    for child in children {
        if let Some(found) = find_node_at_offset(child, offset) {
            return Some(found);
        }
    }

    // If no child contains the offset, return this node
    Some(node)
}

/// Returns direct child nodes for a given AST node.
///
/// Provides generic access to child nodes across different node types,
/// essential for AST traversal algorithms and recursive analysis patterns.
///
/// # Arguments
/// * `node` - AST node to extract children from
///
/// # Returns
/// Vector of borrowed child node references
///
/// # Performance
/// - Time complexity: O(k) where k is child count
/// - Memory: Allocates vector for child references
/// - Typical latency: <5μs for common node types
///
/// # Examples
/// ```rust,ignore
/// use perl_parser::declaration::get_node_children;
/// use perl_parser::ast::Node;
///
/// let node = Node::new_root();
/// let children = get_node_children(&node);
/// println!("Node has {} children", children.len());
/// ```
pub fn get_node_children(node: &Node) -> Vec<&Node> {
    // Delegate to the AST node's own comprehensive children() method,
    // which handles all node kinds including Block, Package, MethodCall, etc.
    node.children()
}