perl_parser/incremental/

incremental_document.rs

//! High-performance incremental document parsing with subtree reuse
//!
//! This module provides incremental parsing with subtree reuse.  Single-edit
//! fast-path updates target <1ms; batch edits (`apply_edits`) always perform
//! a fresh parse for correctness validation, so batch latency scales with
//! document size rather than edit size.

use super::incremental_edit::{IncrementalEdit, IncrementalEditSet};
use perl_parser_core::{
    ast::{Node, NodeKind},
    error::ParseResult,
    parser::Parser,
};
use std::collections::{HashMap, VecDeque};
use std::sync::Arc;
use std::time::Instant;
use tracing::debug;

/// A document with incremental parsing and subtree reuse
#[derive(Debug, Clone)]
pub struct IncrementalDocument {
    /// Current parsed tree
    pub root: Arc<Node>,
    /// Source text
    pub source: String,
    /// Version number for tracking changes
    pub version: u64,
    /// Cache of reusable subtrees
    pub subtree_cache: SubtreeCache,
    /// Performance metrics
    pub metrics: ParseMetrics,
}

/// Cache for reusable subtrees
#[derive(Debug, Clone, Default)]
pub struct SubtreeCache {
    /// Maps content hash to subtree for content-based reuse
    pub by_content: HashMap<u64, Arc<Node>>,
    /// Maps byte range to subtree for position-based reuse
    pub by_range: HashMap<(usize, usize), Arc<Node>>,
    /// LRU queue for cache eviction
    pub lru: VecDeque<u64>,
    /// Critical symbols that should be preserved longer
    pub critical_symbols: HashMap<u64, SymbolPriority>,
    /// Maximum cache size
    pub max_size: usize,
}

/// Priority levels for symbols in cache eviction
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum SymbolPriority {
    Low = 0,
    Medium = 1,
    High = 2,
    Critical = 3,
}

/// Performance metrics for incremental parsing
#[derive(Debug, Clone, Default)]
pub struct ParseMetrics {
    pub last_parse_time_ms: f64,
    pub nodes_reused: usize,
    pub nodes_reparsed: usize,
    pub cache_hits: usize,
    pub cache_misses: usize,
}

impl IncrementalDocument {
    /// Create a new incremental document
    pub fn new(source: String) -> ParseResult<Self> {
        let start = Instant::now();
        let mut parser = Parser::new(&source);
        let root = parser.parse()?;

        let mut doc = IncrementalDocument {
            root: Arc::new(root),
            source,
            version: 0,
            subtree_cache: SubtreeCache::new(1000),
            metrics: ParseMetrics::default(),
        };

        doc.metrics.last_parse_time_ms = start.elapsed().as_secs_f64() * 1000.0;
        doc.cache_subtrees();

        Ok(doc)
    }

    /// Apply an edit and incrementally reparse
    pub fn apply_edit(&mut self, edit: IncrementalEdit) -> ParseResult<()> {
        let start = Instant::now();
        self.version += 1;

        // Reset metrics for this parse cycle
        self.metrics = ParseMetrics::default();

        // Apply the edit to the source
        let new_source = self.apply_edit_to_source(&edit);

        // Find affected subtrees
        let affected_range = (edit.start_byte, edit.old_end_byte);
        let reusable_subtrees = self.find_reusable_subtrees(affected_range, &edit);

        // Incrementally parse with subtree reuse
        let (new_root, used_fast_path) =
            self.incremental_parse(&new_source, &edit, reusable_subtrees)?;

        // Update state
        self.source = new_source;
        self.root = Arc::new(new_root);

        // Only rebuild the full subtree cache when the fast path was NOT used.
        // The fast path only mutates a single token node in-place, so the
        // existing cache entries (keyed by byte range) are mostly still valid,
        // whereas a full cache rebuild walks the entire tree and is O(n).
        if !used_fast_path {
            self.cache_subtrees();
        }

        self.metrics.last_parse_time_ms = start.elapsed().as_secs_f64() * 1000.0;

        Ok(())
    }

    /// Apply multiple edits in a batch
    pub fn apply_edits(&mut self, edits: &IncrementalEditSet) -> ParseResult<()> {
        let start = Instant::now();
        self.version += 1;

        // Reset metrics for this batch of edits
        self.metrics = ParseMetrics::default();

        let Some(sorted_edits) = edits.normalize_for_source(&self.source) else {
            return self.fallback_parse_batch(edits, start);
        };

        // Apply all edits to source in-place.
        // Reverse ordering keeps byte offsets stable while avoiding repeated
        // full-string allocations for each edit.
        let mut new_source = self.source.clone();
        for edit in &sorted_edits {
            if !self.apply_edit_in_place(&mut new_source, edit) {
                return self.fallback_parse_batch(edits, start);
            }
        }

        // Find all affected ranges
        let affected_ranges: Vec<_> =
            sorted_edits.iter().map(|e| (e.start_byte, e.old_end_byte)).collect();

        // Collect reusable subtrees outside affected ranges
        let reusable = self.find_reusable_for_ranges(&affected_ranges);

        // Parse with reuse when possible. When reuse was attempted, validate
        // the grafted tree against a fresh parse to catch divergence. When no
        // reuse candidates exist, skip the second parse entirely.
        let new_root = if !reusable.is_empty() {
            let reused_root = self.parse_with_reuse(&new_source, reusable)?;
            // parse_with_reuse already ran a full parse internally; run a second
            // one only to verify the graft produced a consistent tree.
            let mut parser = Parser::new(&new_source);
            let fresh_root = parser.parse()?;
            if Self::nodes_match(&reused_root, &fresh_root) {
                reused_root
            } else {
                debug!("Batch incremental reuse diverged from fresh parse; using fallback result");
                fresh_root
            }
        } else {
            let mut parser = Parser::new(&new_source);
            parser.parse()?
        };

        // Update state
        self.source = new_source;
        self.root = Arc::new(new_root);
        self.cache_subtrees();

        self.metrics.last_parse_time_ms = start.elapsed().as_secs_f64() * 1000.0;

        Ok(())
    }

    fn fallback_parse_batch(
        &mut self,
        edits: &IncrementalEditSet,
        start: Instant,
    ) -> ParseResult<()> {
        let new_source = edits.apply_to_string(&self.source);
        let mut parser = Parser::new(&new_source);
        let new_root = parser.parse()?;
        self.source = new_source;
        self.root = Arc::new(new_root);
        self.cache_subtrees();
        self.metrics.last_parse_time_ms = start.elapsed().as_secs_f64() * 1000.0;
        Ok(())
    }

    /// Apply edit to source string
    fn apply_edit_to_source(&self, edit: &IncrementalEdit) -> String {
        self.apply_edit_to_string(&self.source, edit)
    }

    fn apply_edit_to_string(&self, source: &str, edit: &IncrementalEdit) -> String {
        let Some((start, end)) = Self::map_edit_range(source, edit) else {
            debug!(
                "Invalid edit mapping: start={}, end={}, source_len={}",
                edit.start_byte,
                edit.old_end_byte,
                source.len()
            );
            return source.to_string();
        };

        let mut result = String::with_capacity(source.len() + edit.new_text.len());
        result.push_str(&source[..start]);
        result.push_str(&edit.new_text);
        result.push_str(&source[end..]);
        result
    }

    fn apply_edit_in_place(&self, source: &mut String, edit: &IncrementalEdit) -> bool {
        let Some((start, end)) = Self::map_edit_range(source, edit) else {
            debug!(
                "Invalid edit mapping: start={}, end={}, source_len={}",
                edit.start_byte,
                edit.old_end_byte,
                source.len()
            );
            return false;
        };

        source.replace_range(start..end, &edit.new_text);
        true
    }

    fn map_edit_range(source: &str, edit: &IncrementalEdit) -> Option<(usize, usize)> {
        if edit.start_byte > edit.old_end_byte {
            return None;
        }
        if edit.old_end_byte > source.len() {
            return None;
        }
        if !source.is_char_boundary(edit.start_byte) || !source.is_char_boundary(edit.old_end_byte)
        {
            return None;
        }
        Some((edit.start_byte, edit.old_end_byte))
    }

    fn nodes_match(left: &Node, right: &Node) -> bool {
        left == right
    }

    /// Find subtrees that can be reused (outside the edited range)
    fn find_reusable_subtrees(
        &mut self,
        affected_range: (usize, usize),
        edit: &IncrementalEdit,
    ) -> Vec<Arc<Node>> {
        let mut reusable = Vec::new();
        let delta = edit.byte_shift();

        // Collect subtrees before the edit (unchanged positions)
        for ((start, end), node) in &self.subtree_cache.by_range {
            if *end <= affected_range.0 {
                // Subtree entirely before edit - can reuse as-is
                reusable.push(node.clone());
                self.metrics.cache_hits += 1;
                self.metrics.nodes_reused += self.count_nodes(node);
            } else if *start >= affected_range.1 {
                // Subtree entirely after edit - needs position adjustment
                if let Some(adjusted) = self.adjust_node_position(node, delta) {
                    reusable.push(Arc::new(adjusted));
                    self.metrics.cache_hits += 1;
                    self.metrics.nodes_reused += self.count_nodes(node);
                }
            } else {
                self.metrics.cache_misses += 1;
            }
        }

        reusable
    }

    /// Find reusable subtrees for multiple affected ranges
    fn find_reusable_for_ranges(&mut self, ranges: &[(usize, usize)]) -> Vec<Arc<Node>> {
        let mut reusable = Vec::new();

        for ((start, end), node) in &self.subtree_cache.by_range {
            let affected = ranges.iter().any(|(r_start, r_end)| {
                // Check if this subtree overlaps with any affected range
                *start < *r_end && *end > *r_start
            });

            if !affected {
                reusable.push(node.clone());
                self.metrics.cache_hits += 1;
                self.metrics.nodes_reused += self.count_nodes(node);
            } else {
                self.metrics.cache_misses += 1;
            }
        }

        reusable
    }

    /// Incrementally parse with subtree reuse.
    ///
    /// Returns `(new_root, used_fast_path)` -- the boolean indicates whether
    /// the fast token-update path was used so the caller can skip a full
    /// cache rebuild.
    fn incremental_parse(
        &mut self,
        source: &str,
        edit: &IncrementalEdit,
        _reusable: Vec<Arc<Node>>,
    ) -> ParseResult<(Node, bool)> {
        // For small edits within a single token, try fast path
        if self.is_single_token_edit(edit) {
            if let Some(node) = self.fast_token_update(source, edit) {
                self.metrics.nodes_reparsed = 1;
                return Ok((node, true));
            }
        }

        // Otherwise use partial parsing with reuse
        let node = self.parse_with_reuse(source, _reusable)?;
        Ok((node, false))
    }

    /// Check if edit affects only a single token
    fn is_single_token_edit(&self, edit: &IncrementalEdit) -> bool {
        // Check if edit is small and contained within a single literal
        if edit.old_end_byte - edit.start_byte > 100 {
            return false; // Too large
        }

        // Find the containing node
        if let Some(node) = self.find_node_at_position(edit.start_byte) {
            matches!(
                node.kind,
                NodeKind::Number { .. } | NodeKind::String { .. } | NodeKind::Identifier { .. }
            )
        } else {
            false
        }
    }

    /// Fast path for single token updates
    fn fast_token_update(&self, source: &str, edit: &IncrementalEdit) -> Option<Node> {
        // Clone the tree and update just the affected token
        let mut new_root = (*self.root).clone();

        // Find and update the affected token
        if self.update_token_in_tree(&mut new_root, source, edit) { Some(new_root) } else { None }
    }

    /// Update a single token in the tree
    fn update_token_in_tree(&self, node: &mut Node, source: &str, edit: &IncrementalEdit) -> bool {
        // Check if this node contains the edit
        if node.location.start <= edit.start_byte && node.location.end >= edit.old_end_byte {
            match &mut node.kind {
                NodeKind::Number { .. } => {
                    // Re-parse just this number
                    let delta = edit.byte_shift();
                    let new_end = (node.location.end as isize + delta).max(0) as usize;

                    // Safely extract new text with bounds checking
                    if new_end <= source.len()
                        && source.is_char_boundary(node.location.start)
                        && source.is_char_boundary(new_end)
                    {
                        node.location.end = new_end;
                        let new_text = &source[node.location.start..node.location.end];
                        if let Ok(value) = new_text.parse::<f64>() {
                            node.kind = NodeKind::Number { value: value.to_string() };
                            return true;
                        }
                    }
                }
                NodeKind::String { value, .. } => {
                    // Update string content
                    let delta = edit.byte_shift();
                    let new_end = (node.location.end as isize + delta).max(0) as usize;

                    // Safely extract new string value with bounds checking
                    if new_end <= source.len()
                        && source.is_char_boundary(node.location.start)
                        && source.is_char_boundary(new_end)
                    {
                        node.location.end = new_end;
                        let new_text = &source[node.location.start..node.location.end];
                        *value = new_text.to_string();
                        return true;
                    }
                }
                NodeKind::Identifier { name } => {
                    // Update identifier
                    let delta = edit.byte_shift();
                    let new_end = (node.location.end as isize + delta).max(0) as usize;

                    // Safely extract identifier name with bounds checking
                    if new_end <= source.len()
                        && source.is_char_boundary(node.location.start)
                        && source.is_char_boundary(new_end)
                    {
                        node.location.end = new_end;
                        *name = source[node.location.start..node.location.end].to_string();
                        return true;
                    }
                }
                _ => {
                    // Recursively search children
                    return self.update_token_in_children(node, source, edit);
                }
            }
        }

        false
    }

    /// Update token in child nodes
    fn update_token_in_children(
        &self,
        node: &mut Node,
        source: &str,
        edit: &IncrementalEdit,
    ) -> bool {
        match &mut node.kind {
            NodeKind::Program { statements } | NodeKind::Block { statements } => {
                for stmt in statements {
                    if self.update_token_in_tree(stmt, source, edit) {
                        return true;
                    }
                }
            }
            NodeKind::Binary { left, right, .. }
            | NodeKind::Assignment { lhs: left, rhs: right, .. } => {
                if self.update_token_in_tree(left, source, edit) {
                    return true;
                }
                if self.update_token_in_tree(right, source, edit) {
                    return true;
                }
            }
            NodeKind::Subroutine { body, .. } => {
                if self.update_token_in_tree(body, source, edit) {
                    return true;
                }
            }
            NodeKind::ExpressionStatement { expression } => {
                if self.update_token_in_tree(expression, source, edit) {
                    return true;
                }
            }
            NodeKind::VariableDeclaration { variable, initializer, .. } => {
                if self.update_token_in_tree(variable, source, edit) {
                    return true;
                }
                if let Some(init) = initializer {
                    if self.update_token_in_tree(init, source, edit) {
                        return true;
                    }
                }
            }
            NodeKind::If { condition, then_branch, elsif_branches, else_branch } => {
                if self.update_token_in_tree(condition, source, edit) {
                    return true;
                }
                if self.update_token_in_tree(then_branch, source, edit) {
                    return true;
                }
                for (cond, branch) in elsif_branches {
                    if self.update_token_in_tree(cond, source, edit) {
                        return true;
                    }
                    if self.update_token_in_tree(branch, source, edit) {
                        return true;
                    }
                }
                if let Some(else_b) = else_branch {
                    if self.update_token_in_tree(else_b, source, edit) {
                        return true;
                    }
                }
            }
            NodeKind::While { condition, body, .. } => {
                if self.update_token_in_tree(condition, source, edit) {
                    return true;
                }
                if self.update_token_in_tree(body, source, edit) {
                    return true;
                }
            }
            NodeKind::FunctionCall { args, .. } => {
                for arg in args {
                    if self.update_token_in_tree(arg, source, edit) {
                        return true;
                    }
                }
            }
            NodeKind::Unary { operand, .. } => {
                if self.update_token_in_tree(operand, source, edit) {
                    return true;
                }
            }
            _ => {}
        }

        false
    }

    /// Parse with reusable subtrees
    fn parse_with_reuse(&mut self, source: &str, reusable: Vec<Arc<Node>>) -> ParseResult<Node> {
        // Start with a fresh parse of the new source
        let mut parser = Parser::new(source);
        let mut root = parser.parse()?;

        // Try to splice in any reusable subtrees by matching on byte ranges
        for node in reusable {
            self.insert_reusable(&mut root, &node);
        }

        // Update metrics based on reused nodes
        self.metrics.nodes_reparsed =
            self.count_nodes(&root).saturating_sub(self.metrics.nodes_reused);

        Ok(root)
    }

    /// Replace matching nodes in `target` with a reusable subtree
    fn insert_reusable(&self, target: &mut Node, reusable: &Arc<Node>) -> bool {
        if target.location.start == reusable.location.start
            && target.location.end == reusable.location.end
            && std::mem::discriminant(&target.kind) == std::mem::discriminant(&reusable.kind)
        {
            *target = (**reusable).clone();
            return true;
        }

        match &mut target.kind {
            NodeKind::Program { statements } | NodeKind::Block { statements } => {
                for stmt in statements {
                    if self.insert_reusable(stmt, reusable) {
                        return true;
                    }
                }
            }
            NodeKind::Binary { left, right, .. } => {
                if self.insert_reusable(left, reusable) {
                    return true;
                }
                if self.insert_reusable(right, reusable) {
                    return true;
                }
            }
            NodeKind::Subroutine { body, .. } => {
                if self.insert_reusable(body, reusable) {
                    return true;
                }
            }
            NodeKind::ExpressionStatement { expression } => {
                if self.insert_reusable(expression, reusable) {
                    return true;
                }
            }
            NodeKind::If { condition, then_branch, elsif_branches, else_branch } => {
                if self.insert_reusable(condition, reusable) {
                    return true;
                }
                if self.insert_reusable(then_branch, reusable) {
                    return true;
                }
                for (cond, branch) in elsif_branches {
                    if self.insert_reusable(cond, reusable) {
                        return true;
                    }
                    if self.insert_reusable(branch, reusable) {
                        return true;
                    }
                }
                if let Some(else_b) = else_branch {
                    if self.insert_reusable(else_b, reusable) {
                        return true;
                    }
                }
            }
            NodeKind::While { condition, body, .. } => {
                if self.insert_reusable(condition, reusable) {
                    return true;
                }
                if self.insert_reusable(body, reusable) {
                    return true;
                }
            }
            NodeKind::For { init, condition, update, body, .. } => {
                if let Some(i) = init {
                    if self.insert_reusable(i, reusable) {
                        return true;
                    }
                }
                if let Some(c) = condition {
                    if self.insert_reusable(c, reusable) {
                        return true;
                    }
                }
                if let Some(u) = update {
                    if self.insert_reusable(u, reusable) {
                        return true;
                    }
                }
                if self.insert_reusable(body, reusable) {
                    return true;
                }
            }
            NodeKind::VariableDeclaration { variable, initializer, .. } => {
                if self.insert_reusable(variable, reusable) {
                    return true;
                }
                if let Some(init) = initializer {
                    if self.insert_reusable(init, reusable) {
                        return true;
                    }
                }
            }
            NodeKind::Assignment { lhs, rhs, .. } => {
                if self.insert_reusable(lhs, reusable) {
                    return true;
                }
                if self.insert_reusable(rhs, reusable) {
                    return true;
                }
            }
            _ => {}
        }

        false
    }

    /// Adjust node positions after an edit
    ///
    /// Returns `None` if the adjustment would produce an invalid (negative) position,
    /// which can happen when a deletion shrinks the source and a node's original
    /// position is inside the deleted range.
    fn adjust_node_position(&self, node: &Node, delta: isize) -> Option<Node> {
        let mut adjusted = node.clone();

        // Checked conversion to prevent underflow when delta is negative
        let new_start = adjusted.location.start as isize + delta;
        let new_end = adjusted.location.end as isize + delta;
        if new_start < 0 || new_end < 0 {
            return None;
        }
        adjusted.location.start = new_start as usize;
        adjusted.location.end = new_end as usize;

        // Recursively adjust children
        match &mut adjusted.kind {
            NodeKind::Program { statements } | NodeKind::Block { statements } => {
                for stmt in statements {
                    *stmt = self.adjust_node_position(stmt, delta)?;
                }
            }
            NodeKind::Binary { left, right, .. } => {
                **left = self.adjust_node_position(left, delta)?;
                **right = self.adjust_node_position(right, delta)?;
            }
            NodeKind::Subroutine { body, .. } => {
                **body = self.adjust_node_position(body, delta)?;
            }
            NodeKind::ExpressionStatement { expression } => {
                **expression = self.adjust_node_position(expression, delta)?;
            }
            NodeKind::If { condition, then_branch, elsif_branches, else_branch } => {
                **condition = self.adjust_node_position(condition, delta)?;
                **then_branch = self.adjust_node_position(then_branch, delta)?;
                for (cond, branch) in elsif_branches {
                    **cond = self.adjust_node_position(cond, delta)?;
                    **branch = self.adjust_node_position(branch, delta)?;
                }
                if let Some(else_b) = else_branch {
                    **else_b = self.adjust_node_position(else_b, delta)?;
                }
            }
            NodeKind::While { condition, body, .. } => {
                **condition = self.adjust_node_position(condition, delta)?;
                **body = self.adjust_node_position(body, delta)?;
            }
            NodeKind::For { init, condition, update, body, .. } => {
                if let Some(i) = init {
                    **i = self.adjust_node_position(i, delta)?;
                }
                if let Some(c) = condition {
                    **c = self.adjust_node_position(c, delta)?;
                }
                if let Some(u) = update {
                    **u = self.adjust_node_position(u, delta)?;
                }
                **body = self.adjust_node_position(body, delta)?;
            }
            NodeKind::VariableDeclaration { variable, initializer, .. } => {
                **variable = self.adjust_node_position(variable, delta)?;
                if let Some(init) = initializer {
                    **init = self.adjust_node_position(init, delta)?;
                }
            }
            NodeKind::Assignment { lhs, rhs, .. } => {
                **lhs = self.adjust_node_position(lhs, delta)?;
                **rhs = self.adjust_node_position(rhs, delta)?;
            }
            _ => {}
        }

        Some(adjusted)
    }

    /// Find node at a specific byte position
    fn find_node_at_position(&self, pos: usize) -> Option<&Node> {
        self.find_in_node(&self.root, pos)
    }

    fn find_in_node<'a>(&self, node: &'a Node, pos: usize) -> Option<&'a Node> {
        if node.location.start <= pos && node.location.end > pos {
            // Check children for more specific match
            match &node.kind {
                NodeKind::Program { statements } | NodeKind::Block { statements } => {
                    for stmt in statements {
                        if let Some(found) = self.find_in_node(stmt, pos) {
                            return Some(found);
                        }
                    }
                }
                NodeKind::Binary { left, right, .. }
                | NodeKind::Assignment { lhs: left, rhs: right, .. } => {
                    if let Some(found) = self.find_in_node(left, pos) {
                        return Some(found);
                    }
                    if let Some(found) = self.find_in_node(right, pos) {
                        return Some(found);
                    }
                }
                NodeKind::Subroutine { body, .. } => {
                    if let Some(found) = self.find_in_node(body, pos) {
                        return Some(found);
                    }
                }
                NodeKind::ExpressionStatement { expression } => {
                    if let Some(found) = self.find_in_node(expression, pos) {
                        return Some(found);
                    }
                }
                NodeKind::VariableDeclaration { variable, initializer, .. } => {
                    if let Some(found) = self.find_in_node(variable, pos) {
                        return Some(found);
                    }
                    if let Some(init) = initializer {
                        if let Some(found) = self.find_in_node(init, pos) {
                            return Some(found);
                        }
                    }
                }
                NodeKind::If { condition, then_branch, elsif_branches, else_branch } => {
                    if let Some(found) = self.find_in_node(condition, pos) {
                        return Some(found);
                    }
                    if let Some(found) = self.find_in_node(then_branch, pos) {
                        return Some(found);
                    }
                    for (cond, branch) in elsif_branches {
                        if let Some(found) = self.find_in_node(cond, pos) {
                            return Some(found);
                        }
                        if let Some(found) = self.find_in_node(branch, pos) {
                            return Some(found);
                        }
                    }
                    if let Some(else_b) = else_branch {
                        if let Some(found) = self.find_in_node(else_b, pos) {
                            return Some(found);
                        }
                    }
                }
                NodeKind::While { condition, body, .. } => {
                    if let Some(found) = self.find_in_node(condition, pos) {
                        return Some(found);
                    }
                    if let Some(found) = self.find_in_node(body, pos) {
                        return Some(found);
                    }
                }
                NodeKind::FunctionCall { args, .. } => {
                    for arg in args {
                        if let Some(found) = self.find_in_node(arg, pos) {
                            return Some(found);
                        }
                    }
                }
                NodeKind::Unary { operand, .. } => {
                    if let Some(found) = self.find_in_node(operand, pos) {
                        return Some(found);
                    }
                }
                _ => {}
            }

            // No more specific child, return this node
            Some(node)
        } else {
            None
        }
    }

    /// Cache subtrees for reuse
    fn cache_subtrees(&mut self) {
        self.subtree_cache.clear();
        let root = self.root.clone();
        self.cache_node(&root);
    }

    fn cache_node(&mut self, node: &Node) {
        // Cache this subtree by range
        let range = (node.location.start, node.location.end);
        self.subtree_cache.by_range.insert(range, Arc::new(node.clone()));

        // Cache by content hash for common patterns
        let hash = self.hash_node(node);
        let priority = self.get_symbol_priority(node);

        self.subtree_cache.by_content.insert(hash, Arc::new(node.clone()));
        self.subtree_cache.critical_symbols.insert(hash, priority);
        self.subtree_cache.lru.push_back(hash);
        self.subtree_cache.evict_if_needed();

        // Recursively cache children
        match &node.kind {
            NodeKind::Program { statements } | NodeKind::Block { statements } => {
                for stmt in statements {
                    self.cache_node(stmt);
                }
            }
            NodeKind::Binary { left, right, .. } => {
                self.cache_node(left);
                self.cache_node(right);
            }
            NodeKind::Subroutine { body, .. } => {
                self.cache_node(body);
            }
            NodeKind::ExpressionStatement { expression } => {
                self.cache_node(expression);
            }
            NodeKind::If { condition, then_branch, elsif_branches, else_branch } => {
                self.cache_node(condition);
                self.cache_node(then_branch);
                for (cond, branch) in elsif_branches {
                    self.cache_node(cond);
                    self.cache_node(branch);
                }
                if let Some(else_b) = else_branch {
                    self.cache_node(else_b);
                }
            }
            NodeKind::While { condition, body, .. } => {
                self.cache_node(condition);
                self.cache_node(body);
            }
            NodeKind::For { init, condition, update, body, .. } => {
                if let Some(i) = init {
                    self.cache_node(i);
                }
                if let Some(c) = condition {
                    self.cache_node(c);
                }
                if let Some(u) = update {
                    self.cache_node(u);
                }
                self.cache_node(body);
            }
            NodeKind::Foreach { variable, list, body, continue_block } => {
                self.cache_node(variable);
                self.cache_node(list);
                self.cache_node(body);
                if let Some(cb) = continue_block {
                    self.cache_node(cb);
                }
            }
            NodeKind::VariableDeclaration { variable, initializer, .. } => {
                self.cache_node(variable);
                if let Some(init) = initializer {
                    self.cache_node(init);
                }
            }
            NodeKind::VariableListDeclaration { variables, initializer, .. } => {
                for var in variables {
                    self.cache_node(var);
                }
                if let Some(init) = initializer {
                    self.cache_node(init);
                }
            }
            NodeKind::Assignment { lhs, rhs, .. } => {
                self.cache_node(lhs);
                self.cache_node(rhs);
            }
            _ => {}
        }
    }

    /// Generate hash for a node (for content-based caching)
    fn hash_node(&self, node: &Node) -> u64 {
        use std::collections::hash_map::DefaultHasher;
        use std::hash::{Hash, Hasher};

        let mut hasher = DefaultHasher::new();

        // Hash node kind discriminant
        std::mem::discriminant(&node.kind).hash(&mut hasher);

        // Hash node content
        match &node.kind {
            NodeKind::Number { value } => value.hash(&mut hasher),
            NodeKind::String { value, .. } => value.hash(&mut hasher),
            NodeKind::Identifier { name } => name.hash(&mut hasher),
            _ => {}
        }

        hasher.finish()
    }

    /// Count nodes in a subtree
    fn count_nodes(&self, node: &Node) -> usize {
        let mut count = 1;

        match &node.kind {
            NodeKind::Program { statements } | NodeKind::Block { statements } => {
                for stmt in statements {
                    count += self.count_nodes(stmt);
                }
            }
            NodeKind::Binary { left, right, .. } => {
                count += self.count_nodes(left);
                count += self.count_nodes(right);
            }
            NodeKind::Subroutine { body, .. } => {
                count += self.count_nodes(body);
            }
            NodeKind::ExpressionStatement { expression } => {
                count += self.count_nodes(expression);
            }
            NodeKind::If { condition, then_branch, elsif_branches, else_branch } => {
                count += self.count_nodes(condition);
                count += self.count_nodes(then_branch);
                for (cond, branch) in elsif_branches {
                    count += self.count_nodes(cond);
                    count += self.count_nodes(branch);
                }
                if let Some(else_b) = else_branch {
                    count += self.count_nodes(else_b);
                }
            }
            NodeKind::While { condition, body, .. } => {
                count += self.count_nodes(condition);
                count += self.count_nodes(body);
            }
            NodeKind::For { init, condition, update, body, .. } => {
                if let Some(i) = init {
                    count += self.count_nodes(i);
                }
                if let Some(c) = condition {
                    count += self.count_nodes(c);
                }
                if let Some(u) = update {
                    count += self.count_nodes(u);
                }
                count += self.count_nodes(body);
            }
            NodeKind::Foreach { variable, list, body, continue_block } => {
                count += self.count_nodes(variable);
                count += self.count_nodes(list);
                count += self.count_nodes(body);
                if let Some(cb) = continue_block {
                    count += self.count_nodes(cb);
                }
            }
            NodeKind::VariableDeclaration { variable, initializer, .. } => {
                count += self.count_nodes(variable);
                if let Some(init) = initializer {
                    count += self.count_nodes(init);
                }
            }
            NodeKind::VariableListDeclaration { variables, initializer, .. } => {
                for var in variables {
                    count += self.count_nodes(var);
                }
                if let Some(init) = initializer {
                    count += self.count_nodes(init);
                }
            }
            NodeKind::Assignment { lhs, rhs, .. } => {
                count += self.count_nodes(lhs);
                count += self.count_nodes(rhs);
            }
            NodeKind::FunctionCall { args, .. } => {
                for arg in args {
                    count += self.count_nodes(arg);
                }
            }
            NodeKind::Unary { operand, .. } => {
                count += self.count_nodes(operand);
            }
            _ => {}
        }

        count
    }

    /// Determine the priority of a symbol for cache eviction
    fn get_symbol_priority(&self, node: &Node) -> SymbolPriority {
        match &node.kind {
            // Critical symbols needed for LSP features
            NodeKind::Package { .. } => SymbolPriority::Critical,
            NodeKind::Use { .. } | NodeKind::No { .. } => SymbolPriority::Critical,
            NodeKind::Subroutine { .. } => SymbolPriority::Critical,

            // High priority symbols for completion and navigation
            NodeKind::FunctionCall { .. } => SymbolPriority::High,
            NodeKind::Variable { .. } => SymbolPriority::High,
            NodeKind::VariableDeclaration { .. } => SymbolPriority::High,

            // Medium priority for structural elements
            NodeKind::Block { .. } => SymbolPriority::Medium,
            NodeKind::If { .. } | NodeKind::While { .. } | NodeKind::For { .. } => {
                SymbolPriority::Medium
            }
            NodeKind::Assignment { .. } => SymbolPriority::Medium,

            // Low priority for literals and simple expressions
            NodeKind::Number { .. } | NodeKind::String { .. } => SymbolPriority::Low,
            NodeKind::Binary { .. } | NodeKind::Unary { .. } => SymbolPriority::Low,

            // Default to medium for unknown types
            _ => SymbolPriority::Medium,
        }
    }

    /// Get current parse tree
    pub fn tree(&self) -> &Node {
        &self.root
    }

    /// Get current source text
    pub fn text(&self) -> &str {
        &self.source
    }

    /// Get performance metrics
    pub fn metrics(&self) -> &ParseMetrics {
        &self.metrics
    }

    /// Set maximum cache size
    pub fn set_cache_max_size(&mut self, max_size: usize) {
        self.subtree_cache.set_max_size(max_size);
    }
}

impl SubtreeCache {
    fn new(max_size: usize) -> Self {
        SubtreeCache {
            by_content: HashMap::new(),
            by_range: HashMap::new(),
            lru: VecDeque::new(),
            critical_symbols: HashMap::new(),
            max_size,
        }
    }

    fn clear(&mut self) {
        self.by_content.clear();
        self.by_range.clear();
        self.lru.clear();
        self.critical_symbols.clear();
    }

    fn evict_if_needed(&mut self) {
        while self.by_content.len() > self.max_size {
            if let Some(hash) = self.find_least_important_entry() {
                debug!(
                    "Evicting cache entry with hash {} (priority: {:?})",
                    hash,
                    self.critical_symbols.get(&hash).copied().unwrap_or(SymbolPriority::Low)
                );
                self.by_content.remove(&hash);
                self.critical_symbols.remove(&hash);
                // Remove from LRU queue
                self.lru.retain(|&h| h != hash);
            } else {
                // Fallback: remove oldest entry if no low priority entries found
                if let Some(hash) = self.lru.pop_front() {
                    debug!("Fallback eviction for hash {}", hash);
                    self.by_content.remove(&hash);
                    self.critical_symbols.remove(&hash);
                }
            }
        }
    }

    /// Find the least important cache entry for eviction.
    ///
    /// Uses a single pass over the LRU queue (O(n)) instead of sorting all
    /// candidates and doing O(n) position lookups per candidate (which was
    /// O(n^2) overall). LRU order inherently encodes age: earlier entries
    /// are older.
    fn find_least_important_entry(&self) -> Option<u64> {
        let mut best: Option<(u64, SymbolPriority)> = None;

        for &hash in &self.lru {
            let priority = self.critical_symbols.get(&hash).copied().unwrap_or(SymbolPriority::Low);

            match best {
                None => best = Some((hash, priority)),
                Some((_, best_priority)) => {
                    if priority < best_priority {
                        // Lower priority wins (should be evicted first)
                        best = Some((hash, priority));
                    }
                    // If same priority, keep the first (oldest) we found in LRU order
                }
            }
        }

        best.map(|(hash, _)| hash)
    }

    fn set_max_size(&mut self, max_size: usize) {
        self.max_size = max_size;
        self.evict_if_needed();
    }
}

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

    #[test]
    fn test_incremental_single_token_edit() -> ParseResult<()> {
        let source = r#"
            my $x = 42;
            my $y = 100;
            print $x + $y;
        "#;

        let mut doc = IncrementalDocument::new(source.to_string())?;

        // Change 42 to 43
        let pos =
            source.find("42").ok_or_else(|| perl_parser_core::error::ParseError::SyntaxError {
                message: "test source should contain '42'".to_string(),
                location: 0,
            })?;
        let edit = IncrementalEdit::new(pos + 1, pos + 2, "3".to_string());

        doc.apply_edit(edit)?;

        // Should have high reuse
        assert!(doc.metrics.nodes_reused > 0);
        assert!(doc.metrics.nodes_reparsed < 5);
        assert!(doc.metrics.last_parse_time_ms < 1.0);

        Ok(())
    }

    #[test]
    fn test_incremental_multiple_edits() -> ParseResult<()> {
        let source = r#"
            sub calculate {
                my $a = 10;
                my $b = 20;
                return $a + $b;
            }
        "#;

        let mut doc = IncrementalDocument::new(source.to_string())?;

        let mut edits = IncrementalEditSet::new();

        // Change 10 to 15
        let pos_10 =
            source.find("10").ok_or_else(|| perl_parser_core::error::ParseError::SyntaxError {
                message: "test source should contain '10'".to_string(),
                location: 0,
            })?;
        edits.add(IncrementalEdit::new(pos_10, pos_10 + 2, "15".to_string()));

        // Change 20 to 25
        let pos_20 =
            source.find("20").ok_or_else(|| perl_parser_core::error::ParseError::SyntaxError {
                message: "test source should contain '20'".to_string(),
                location: 0,
            })?;
        edits.add(IncrementalEdit::new(pos_20, pos_20 + 2, "25".to_string()));

        doc.apply_edits(&edits)?;

        // Cache should preserve critical symbols even during batch edits
        let critical_count = doc
            .subtree_cache
            .critical_symbols
            .values()
            .filter(|&p| *p == SymbolPriority::Critical)
            .count();
        assert!(critical_count > 0, "Should preserve critical symbols during batch edits");

        // Verify metrics
        // Assertions enabled for Issue #255 (Incremental parsing metrics).
        // threshold relaxed to 10.0ms for CI environment stability.
        assert!(doc.metrics.nodes_reused > 0, "Incremental parsing should reuse nodes");
        assert!(
            doc.metrics.last_parse_time_ms < 10.0,
            "Incremental parse time was {:.2}ms, which exceeds 10.0ms threshold",
            doc.metrics.last_parse_time_ms
        );

        Ok(())
    }

    #[test]
    fn test_cache_eviction() -> ParseResult<()> {
        let source = "my $x = 1;";
        let doc = IncrementalDocument::new(source.to_string())?;

        // Cache should have entries
        assert!(!doc.subtree_cache.by_range.is_empty());
        assert!(!doc.subtree_cache.by_content.is_empty());

        Ok(())
    }

    #[test]
    fn test_symbol_priority_classification() -> ParseResult<()> {
        let source = r#"
            package TestPkg;
            use strict;

            sub test_func {
                my $var = 42;
                if ($var > 0) {
                    return $var + 1;
                }
            }
        "#;
        let doc = IncrementalDocument::new(source.to_string())?;

        // Verify we have different priority levels in cache
        let priorities: std::collections::HashSet<_> =
            doc.subtree_cache.critical_symbols.values().cloned().collect();

        // Should have critical symbols (package, use, sub)
        assert!(
            priorities.contains(&SymbolPriority::Critical),
            "Should classify package/use/sub as critical"
        );
        // Should have high priority symbols (variables)
        assert!(
            priorities.contains(&SymbolPriority::High),
            "Should classify variables as high priority"
        );
        // Should have lower priority symbols (literals, operators)
        assert!(
            priorities.contains(&SymbolPriority::Low)
                || priorities.contains(&SymbolPriority::Medium),
            "Should have lower priority symbols"
        );

        Ok(())
    }

    #[test]
    fn test_cache_respects_max_size() -> ParseResult<()> {
        let source = "my $x = 1; my $y = 2; my $z = 3;";
        let mut doc = IncrementalDocument::new(source.to_string())?;

        // Ensure cache starts larger than 1 entry
        assert!(doc.subtree_cache.by_content.len() > 1);

        // Shrink cache and verify eviction
        doc.set_cache_max_size(1);
        assert!(doc.subtree_cache.by_content.len() <= 1);

        // Applying an edit should not grow the cache beyond max_size
        let pos =
            source.find('1').ok_or_else(|| perl_parser_core::error::ParseError::SyntaxError {
                message: "test source should contain '1'".to_string(),
                location: 0,
            })?;
        let edit = IncrementalEdit::new(pos, pos + 1, "10".to_string());
        doc.apply_edit(edit)?;
        assert!(doc.subtree_cache.by_content.len() <= 1);

        Ok(())
    }

    #[test]
    fn test_cache_priority_preservation() -> ParseResult<()> {
        let source = r#"
            package MyPackage;
            use strict;
            use warnings;

            sub process {
                my $x = 42;
                my $y = "hello";
                return $x + 1;
            }
        "#;
        let mut doc = IncrementalDocument::new(source.to_string())?;

        // Store initial cache state
        let initial_cache_size = doc.subtree_cache.by_content.len();
        assert!(initial_cache_size > 3, "Should have multiple cached nodes");

        // Set very small cache to force aggressive eviction
        doc.set_cache_max_size(3);
        assert!(doc.subtree_cache.by_content.len() <= 3);

        // Check that critical symbols are preserved
        let has_critical_symbols = doc
            .subtree_cache
            .critical_symbols
            .values()
            .cloned()
            .any(|p| p == SymbolPriority::Critical);
        assert!(has_critical_symbols, "Should preserve critical symbols like package/use/sub");

        // Apply edit and verify critical symbols remain
        let pos =
            source.find("42").ok_or_else(|| perl_parser_core::error::ParseError::SyntaxError {
                message: "test source should contain '42'".to_string(),
                location: 0,
            })?;
        let edit = IncrementalEdit::new(pos, pos + 2, "100".to_string());
        doc.apply_edit(edit)?;
        assert!(doc.subtree_cache.by_content.len() <= 3);

        // Still should have critical symbols after edit
        let has_critical_after_edit = doc
            .subtree_cache
            .critical_symbols
            .values()
            .cloned()
            .any(|p| p == SymbolPriority::Critical);
        assert!(has_critical_after_edit, "Should preserve critical symbols after edit");

        Ok(())
    }

    #[test]
    fn test_workspace_symbol_cache_preservation() -> ParseResult<()> {
        let source = r#"
            package TestModule;

            sub exported_function { }
            sub internal_helper { }

            my $global_var = "test";
        "#;
        let mut doc = IncrementalDocument::new(source.to_string())?;

        // Force small cache size
        doc.set_cache_max_size(2);

        // Verify package declaration is preserved (critical for workspace symbols)
        let package_preserved = doc
            .subtree_cache
            .by_content
            .values()
            .any(|node| matches!(node.kind, NodeKind::Package { .. }));
        assert!(package_preserved, "Package declaration should be preserved for workspace symbols");

        Ok(())
    }

    #[test]
    fn test_completion_metadata_preservation() -> ParseResult<()> {
        let source = r#"
            use Data::Dumper;
            use List::Util qw(first max);

            sub calculate {
                my ($input, $multiplier) = @_;
                return $input * $multiplier;
            }
        "#;
        let mut doc = IncrementalDocument::new(source.to_string())?;

        // Force cache eviction
        doc.set_cache_max_size(4);

        // Verify use statements are preserved (critical for completion)
        let use_statements_count = doc
            .subtree_cache
            .by_content
            .values()
            .filter(|node| matches!(node.kind, NodeKind::Use { .. }))
            .count();
        assert!(
            use_statements_count >= 1,
            "Use statements should be preserved for completion metadata"
        );

        // Verify function definitions are preserved
        let function_preserved = doc
            .subtree_cache
            .by_content
            .values()
            .any(|node| matches!(node.kind, NodeKind::Subroutine { .. }));
        assert!(function_preserved, "Function definitions should be preserved for completion");

        Ok(())
    }

    #[test]
    fn test_code_lens_reference_preservation() -> ParseResult<()> {
        let source = r#"
            package MyClass;

            sub new {
                my $class = shift;
                return bless {}, $class;
            }

            sub process_data {
                my ($self, $data) = @_;
                return $self->transform($data);
            }
        "#;
        let mut doc = IncrementalDocument::new(source.to_string())?;

        // Force aggressive cache eviction
        doc.set_cache_max_size(3);

        // Package and subroutines should be preserved for code lens reference counting
        let critical_nodes = doc
            .subtree_cache
            .by_content
            .values()
            .filter(|node| {
                matches!(node.kind, NodeKind::Package { .. } | NodeKind::Subroutine { .. })
            })
            .count();
        assert!(critical_nodes >= 2, "Should preserve package and key subroutines for code lens");

        Ok(())
    }
}