mod.rs
1 //! Binding graph for tracking symbol bindings and environment variable references. 2 //! 3 //! The binding graph is the core data structure for tracking: 4 //! - Symbol declarations and their scopes 5 //! - Environment variable bindings and chains 6 //! - Usages of symbols and their property accesses 7 //! - Direct env var references 8 //! 9 //! This module is split into focused sub-modules: 10 //! - `core`: Arena storage and basic symbol/scope CRUD operations 11 //! - `indexing`: Interval trees and position-based lookups 12 //! - `resolution`: Chain resolution and origin tracking 13 //! - `env_var_index`: Environment variable indexing 14 //! - `operations`: Bulk operations and utilities 15 16 mod core; 17 mod env_var_index; 18 mod indexing; 19 mod operations; 20 mod resolution; 21 22 pub use env_var_index::{EnvVarLocation, EnvVarLocationKind}; 23 pub use operations::BindingGraphStats; 24 25 // Re-export for backwards compatibility 26 pub use crate::constants::{MAX_CHAIN_DEPTH, RANGE_SIZE_LINE_WEIGHT}; 27 28 use crate::types::{EnvReference, ResolvedEnv, Scope, ScopeId, Symbol, SymbolId, SymbolUsage}; 29 use compact_str::CompactString; 30 use intervaltree::IntervalTree; 31 use parking_lot::RwLock; 32 use rustc_hash::FxHashMap; 33 use smallvec::SmallVec; 34 use tower_lsp::lsp_types::Range; 35 36 /// Entry for building interval trees during analysis 37 #[derive(Debug, Clone)] 38 pub(crate) struct PendingRangeEntry<T: Clone> { 39 pub(crate) range: Range, 40 pub(crate) value: T, 41 } 42 43 /// The main binding graph structure. 44 /// 45 /// Tracks symbol declarations, scopes, usages, and environment variable references 46 /// for a single document. Uses interval trees for efficient position lookups and 47 /// maintains various indices for fast name-based and env var lookups. 48 #[derive(Debug)] 49 pub struct BindingGraph { 50 /// Arena storage for symbols 51 pub(crate) symbols: Vec<Symbol>, 52 53 /// Arena storage for scopes 54 pub(crate) scopes: Vec<Scope>, 55 56 /// Index for fast lookup of symbols by (name, scope) 57 pub(crate) name_index: FxHashMap<(CompactString, ScopeId), SmallVec<[SymbolId; 2]>>, 58 59 /// Index for fast lookup of all symbols by name only (ignoring scope) 60 pub(crate) name_only_index: FxHashMap<CompactString, SmallVec<[SymbolId; 4]>>, 61 62 /// Direct references to environment variables (e.g., `process.env.DATABASE_URL`) 63 pub(crate) direct_references: Vec<EnvReference>, 64 65 /// Usages of symbols (e.g., reading a variable that was bound to an env var) 66 pub(crate) usages: Vec<SymbolUsage>, 67 68 /// Pending entries for destructure range index (built into tree on rebuild) 69 pub(crate) pending_destructure_entries: Vec<PendingRangeEntry<SymbolId>>, 70 71 /// Pending entries for symbol range index (built into tree on rebuild) 72 pub(crate) pending_symbol_entries: Vec<PendingRangeEntry<SymbolId>>, 73 74 /// Pending entries for usage range index (built into tree on rebuild) 75 pub(crate) pending_usage_entries: Vec<PendingRangeEntry<usize>>, 76 77 /// Pending entries for scope range index (built into tree on rebuild) 78 /// Stores (scope_id, size) where size is used to find the most specific scope 79 pub(crate) pending_scope_entries: Vec<PendingRangeEntry<(ScopeId, u64)>>, 80 81 /// Interval tree for O(log n) destructure key lookup by position 82 pub(crate) destructure_range_tree: Option<IntervalTree<u64, SymbolId>>, 83 84 /// Interval tree for O(log n) symbol lookup by position 85 pub(crate) symbol_range_tree: Option<IntervalTree<u64, SymbolId>>, 86 87 /// Interval tree for O(log n) usage lookup by position 88 pub(crate) usage_range_tree: Option<IntervalTree<u64, usize>>, 89 90 /// Interval tree for O(log n) scope lookup by position 91 pub(crate) scope_range_tree: Option<IntervalTree<u64, (ScopeId, u64)>>, 92 93 /// Index for O(1) lookup of all usages of a given env var name 94 pub(crate) env_var_index: FxHashMap<CompactString, Vec<EnvVarLocation>>, 95 96 /// Cache for resolved env vars (symbol_id -> resolved result) 97 pub(crate) resolution_cache: FxHashMap<SymbolId, Option<ResolvedEnv>>, 98 99 /// Cache for scope lookups by position (line, character) -> ScopeId 100 pub(crate) scope_cache: RwLock<FxHashMap<(u32, u32), ScopeId>>, 101 102 /// Next symbol ID to assign 103 pub(crate) next_symbol_id: u32, 104 105 /// Next scope ID to assign 106 pub(crate) next_scope_id: u32, 107 } 108 109 impl Clone for BindingGraph { 110 fn clone(&self) -> Self { 111 Self { 112 symbols: self.symbols.clone(), 113 scopes: self.scopes.clone(), 114 name_index: self.name_index.clone(), 115 name_only_index: self.name_only_index.clone(), 116 direct_references: self.direct_references.clone(), 117 usages: self.usages.clone(), 118 pending_destructure_entries: self.pending_destructure_entries.clone(), 119 pending_symbol_entries: self.pending_symbol_entries.clone(), 120 pending_usage_entries: self.pending_usage_entries.clone(), 121 pending_scope_entries: self.pending_scope_entries.clone(), 122 destructure_range_tree: self.destructure_range_tree.clone(), 123 symbol_range_tree: self.symbol_range_tree.clone(), 124 usage_range_tree: self.usage_range_tree.clone(), 125 scope_range_tree: self.scope_range_tree.clone(), 126 env_var_index: self.env_var_index.clone(), 127 resolution_cache: self.resolution_cache.clone(), 128 // Create empty cache for clone - it will be repopulated on demand 129 scope_cache: RwLock::new(FxHashMap::default()), 130 next_symbol_id: self.next_symbol_id, 131 next_scope_id: self.next_scope_id, 132 } 133 } 134 } 135 136 impl Default for BindingGraph { 137 fn default() -> Self { 138 Self::new() 139 } 140 } 141 142 #[cfg(test)] 143 mod tests;