Skip to main content

nu_protocol/engine/
overlay.rs

1use crate::{DeclId, ModuleId, OverlayId, Span, TypeAliasId, VarId};
2use rustc_hash::FxBuildHasher;
3use std::{
4    collections::HashMap,
5    ops::Deref,
6    sync::atomic::{AtomicUsize, Ordering},
7};
8
9/// The longest name ever inserted into any [`DeclNameMap`] in this process.
10static LONGEST_DECL_NAME: AtomicUsize = AtomicUsize::new(0);
11
12/// An upper bound on the length of every declaration name: every name any [`DeclNameMap`] holds,
13/// in any engine state, is at most this long, so no lookup of a longer name can succeed.
14///
15/// `find_decl` searches only [`DeclNameMap`]s (declarations and predeclarations, in every scope
16/// and overlay), so the parser uses this to skip building command-name candidates that cannot
17/// match (see `find_longest_decl_with_prefix` in nu-parser). The bound is shared by every engine
18/// in the process and only grows, so a long name declared anywhere, even in a scope that is gone,
19/// makes it less tight; that only lets the parser build longer candidates, as it did without it.
20pub fn longest_decl_name() -> usize {
21    LONGEST_DECL_NAME.load(Ordering::Relaxed)
22}
23
24/// Name → id map for declarations that remembers the longest name it has ever held.
25///
26/// Command resolution tries the longest possible command name first and shortens it a word at a
27/// time (`find_longest_decl_with_prefix` in nu-parser), looking each candidate up in every map on
28/// the scope chain. It only builds candidates up to [`longest_decl_name`], the longest name in any
29/// map, but most maps hold much shorter names, such as a script's own definitions or a module's.
30/// Knowing the longest name it holds lets [`DeclNameMap::get`] reject a longer candidate before
31/// hashing it. The bound only grows (removals leave it alone), so it is always an upper bound on
32/// the keys present.
33///
34/// Reads go through `Deref` to the underlying `HashMap`; all mutation goes through the inherent
35/// methods so the bound stays valid.
36///
37/// The parser looks names up here for every command word it sees, so the map uses the Fx hash
38/// (a multiply per 8 bytes) rather than SipHash. Nothing depends on the order of its entries.
39/// Unlike SipHash, the Fx hash has no per-process key, so a file could declare names chosen to
40/// collide and make its own parse slow, in the LSP or `nu-check` as much as when it runs. That is
41/// accepted for the speed, as rustc does, since the names come from the code being parsed.
42#[derive(Debug, Clone, Default)]
43pub struct DeclNameMap {
44    map: HashMap<Vec<u8>, DeclId, FxBuildHasher>,
45    longest_name: usize,
46}
47
48impl DeclNameMap {
49    pub fn new() -> Self {
50        Self::default()
51    }
52
53    /// Look up a declaration by name; names longer than any key ever inserted are rejected
54    /// without hashing.
55    pub fn get(&self, name: &[u8]) -> Option<&DeclId> {
56        if name.len() > self.longest_name {
57            return None;
58        }
59        self.map.get(name)
60    }
61
62    pub fn insert(&mut self, name: Vec<u8>, decl_id: DeclId) -> Option<DeclId> {
63        self.longest_name = self.longest_name.max(name.len());
64        LONGEST_DECL_NAME.fetch_max(name.len(), Ordering::Relaxed);
65        self.map.insert(name, decl_id)
66    }
67
68    pub fn remove(&mut self, name: &[u8]) -> Option<DeclId> {
69        self.map.remove(name)
70    }
71
72    pub fn remove_entry(&mut self, name: &[u8]) -> Option<(Vec<u8>, DeclId)> {
73        self.map.remove_entry(name)
74    }
75}
76
77impl Deref for DeclNameMap {
78    type Target = HashMap<Vec<u8>, DeclId, FxBuildHasher>;
79
80    fn deref(&self) -> &Self::Target {
81        &self.map
82    }
83}
84
85impl<'a> IntoIterator for &'a DeclNameMap {
86    type Item = (&'a Vec<u8>, &'a DeclId);
87    type IntoIter = std::collections::hash_map::Iter<'a, Vec<u8>, DeclId>;
88
89    fn into_iter(self) -> Self::IntoIter {
90        self.map.iter()
91    }
92}
93
94impl IntoIterator for DeclNameMap {
95    type Item = (Vec<u8>, DeclId);
96    type IntoIter = std::collections::hash_map::IntoIter<Vec<u8>, DeclId>;
97
98    fn into_iter(self) -> Self::IntoIter {
99        self.map.into_iter()
100    }
101}
102
103impl Extend<(Vec<u8>, DeclId)> for DeclNameMap {
104    fn extend<I: IntoIterator<Item = (Vec<u8>, DeclId)>>(&mut self, iter: I) {
105        for (name, decl_id) in iter {
106            self.insert(name, decl_id);
107        }
108    }
109}
110
111impl FromIterator<(Vec<u8>, DeclId)> for DeclNameMap {
112    fn from_iter<I: IntoIterator<Item = (Vec<u8>, DeclId)>>(iter: I) -> Self {
113        let mut map = Self::default();
114        map.extend(iter);
115        map
116    }
117}
118
119pub static DEFAULT_OVERLAY_NAME: &str = "zero";
120
121/// Tells whether a decl is visible or not
122///
123/// Looked up for every declaration a name lookup finds (see [`VisibilityStack`]), so it uses the
124/// Fx hash like [`DeclNameMap`].
125#[derive(Debug, Clone)]
126pub struct Visibility {
127    decl_ids: HashMap<DeclId, bool, FxBuildHasher>,
128    /// Type aliases hidden with `hide`, or imported again after that, kept like `decl_ids`.
129    type_alias_ids: HashMap<TypeAliasId, bool, FxBuildHasher>,
130}
131
132/// The names an unscoped parse of a file bound in the scope frame it ran in: the commands,
133/// modules, variables and type aliases the file declared or imported there.
134///
135/// An unscoped parse (`source`, a script, a REPL entry) declares a file's names in the caller's
136/// scope frame. The parser's block cache keeps this record on the parsed
137/// [`Block`](crate::ast::Block). Reusing the block for a later parse of the same file declares
138/// nothing by itself, so the cache binds these names again wherever they are missing, such as
139/// after the scope of the first parse has ended (see
140/// [`StateWorkingSet::bind_names`](crate::engine::StateWorkingSet::bind_names)).
141#[derive(Debug, Clone, Default)]
142pub struct BoundNames {
143    pub decls: Vec<(Vec<u8>, DeclId)>,
144    pub modules: Vec<(Vec<u8>, ModuleId)>,
145    pub vars: Vec<(Vec<u8>, VarId)>,
146    pub type_aliases: Vec<(Vec<u8>, TypeAliasId)>,
147}
148
149/// Name bindings introduced while parsing a single block/closure scope.
150///
151/// Nested scopes discard their name maps on `exit_scope`; this snapshot is stored on the
152/// [`Block`](crate::ast::Block) so `scope` commands can report locals at runtime.
153///
154/// # Lifecycle
155///
156/// 1. **Parse**: [`StateWorkingSet::snapshot_scope_bindings`] copies decls/modules from the
157///    innermost scope frame into a `ScopeBindings` attached to the block, immediately before
158///    the matching `exit_scope`.
159/// 2. **Eval**: whole blocks push bindings on [`Stack::active_scope_bindings`] in
160///    `eval_ir_block`. Keyword bodies that are IR-inlined record
161///    [`ScopeRegion`](crate::ir::ScopeRegion)s on the parent [`IrBlock`](crate::ir::IrBlock);
162///    `scope` matches the current instruction index against those regions.
163#[derive(Debug, Clone, Default)]
164pub struct ScopeBindings {
165    pub decls: HashMap<Vec<u8>, DeclId>,
166    pub modules: HashMap<Vec<u8>, ModuleId>,
167    pub visibility: Visibility,
168}
169
170impl ScopeBindings {
171    pub fn is_empty(&self) -> bool {
172        self.decls.is_empty() && self.modules.is_empty() && self.visibility.decl_ids.is_empty()
173    }
174
175    /// Merge decls, modules, and visibility from an overlay frame (other wins on name clash).
176    pub fn extend_from_overlay(&mut self, overlay: &OverlayFrame) {
177        self.decls
178            .extend(overlay.decls.iter().map(|(k, v)| (k.clone(), *v)));
179        self.modules
180            .extend(overlay.modules.iter().map(|(k, v)| (k.clone(), *v)));
181        self.visibility.merge_with(overlay.visibility.clone());
182    }
183
184    /// Merge another bindings map on top of this one (other wins on name clash).
185    pub fn extend_from_bindings(&mut self, other: &ScopeBindings) {
186        self.decls
187            .extend(other.decls.iter().map(|(k, v)| (k.clone(), *v)));
188        self.modules
189            .extend(other.modules.iter().map(|(k, v)| (k.clone(), *v)));
190        self.visibility.merge_with(other.visibility.clone());
191    }
192}
193
194impl Visibility {
195    pub fn new() -> Self {
196        Visibility {
197            decl_ids: HashMap::default(),
198            type_alias_ids: HashMap::default(),
199        }
200    }
201
202    pub fn is_decl_id_visible(&self, decl_id: &DeclId) -> bool {
203        *self.decl_ids.get(decl_id).unwrap_or(&true) // by default it's visible
204    }
205
206    pub fn hide_decl_id(&mut self, decl_id: &DeclId) {
207        self.decl_ids.insert(*decl_id, false);
208    }
209
210    pub fn use_decl_id(&mut self, decl_id: &DeclId) {
211        self.decl_ids.insert(*decl_id, true);
212    }
213
214    pub fn is_type_alias_id_visible(&self, type_alias_id: &TypeAliasId) -> bool {
215        *self.type_alias_ids.get(type_alias_id).unwrap_or(&true) // by default it's visible
216    }
217
218    pub fn hide_type_alias_id(&mut self, type_alias_id: &TypeAliasId) {
219        self.type_alias_ids.insert(*type_alias_id, false);
220    }
221
222    pub fn use_type_alias_id(&mut self, type_alias_id: &TypeAliasId) {
223        self.type_alias_ids.insert(*type_alias_id, true);
224    }
225
226    /// Overwrite own values with the other
227    pub fn merge_with(&mut self, other: Visibility) {
228        self.decl_ids.extend(other.decl_ids);
229        self.type_alias_ids.extend(other.type_alias_ids);
230    }
231
232    /// Take new values from the other but keep own values
233    pub fn append(&mut self, other: &Visibility) {
234        for (decl_id, visible) in other.decl_ids.iter() {
235            if !self.decl_ids.contains_key(decl_id) {
236                self.decl_ids.insert(*decl_id, *visible);
237            }
238        }
239        for (type_alias_id, visible) in other.type_alias_ids.iter() {
240            self.type_alias_ids
241                .entry(*type_alias_id)
242                .or_insert(*visible);
243        }
244    }
245
246    /// Whether this hides a declaration or type alias that `before` didn't hide.
247    pub fn hides_more_than(&self, before: &Visibility) -> bool {
248        self.decl_ids
249            .iter()
250            .any(|(id, visible)| !visible && before.decl_ids.get(id) != Some(&false))
251            || self
252                .type_alias_ids
253                .iter()
254                .any(|(id, visible)| !visible && before.type_alias_ids.get(id) != Some(&false))
255    }
256}
257
258/// Decl visibility resolved across the overlay frames walked so far, innermost frame first.
259///
260/// Name lookups walk the active overlays from the innermost one outwards. A decl is visible
261/// unless one of the frames walked so far has an explicit entry hiding it, and the innermost
262/// frame with an entry for the decl wins. This borrows each frame's [`Visibility`] instead of
263/// merging the maps: merging copied every entry of every frame on every lookup, which made
264/// `find_decl` (called for every command word the parser sees) cost as much as the maps were
265/// large.
266#[derive(Debug, Default)]
267pub struct VisibilityStack<'a> {
268    /// The first frames pushed, in order. A lookup rarely walks more than a few frames that
269    /// hide declarations (once the standard library is loaded, the permanent overlay is one), so
270    /// they are kept here rather than in a `Vec`, which would allocate on every lookup.
271    inline: [Option<&'a Visibility>; 4],
272    /// The frames pushed after `inline` is full, in order.
273    spilled: Vec<&'a Visibility>,
274}
275
276impl<'a> VisibilityStack<'a> {
277    /// Add the visibility of the next (outer) frame. Frames pushed earlier take precedence.
278    ///
279    /// A frame that hides nothing can never answer a lookup, so it is not recorded; this keeps
280    /// the common lookup (no hidden declarations anywhere) free of allocation. A frame that only
281    /// hides type aliases is recorded too, so `find_decl` walks it without finding an answer
282    /// there; `hide` on a type alias is rare enough that this costs nothing in practice.
283    pub fn push(&mut self, visibility: &'a Visibility) {
284        if visibility.decl_ids.is_empty() && visibility.type_alias_ids.is_empty() {
285            return;
286        }
287        match self.inline.iter_mut().find(|layer| layer.is_none()) {
288            Some(layer) => *layer = Some(visibility),
289            None => self.spilled.push(visibility),
290        }
291    }
292
293    /// Whether `decl_id` is visible given the frames pushed so far.
294    pub fn is_decl_id_visible(&self, decl_id: &DeclId) -> bool {
295        self.inline
296            .iter()
297            .map_while(|layer| *layer)
298            .chain(self.spilled.iter().copied())
299            .find_map(|visibility| visibility.decl_ids.get(decl_id))
300            .copied()
301            .unwrap_or(true) // by default it's visible
302    }
303
304    /// Whether `type_alias_id` is visible given the frames pushed so far.
305    pub fn is_type_alias_id_visible(&self, type_alias_id: &TypeAliasId) -> bool {
306        self.inline
307            .iter()
308            .map_while(|layer| *layer)
309            .chain(self.spilled.iter().copied())
310            .find_map(|visibility| visibility.type_alias_ids.get(type_alias_id))
311            .copied()
312            .unwrap_or(true) // by default it's visible
313    }
314}
315
316#[derive(Debug, Clone)]
317pub struct ScopeFrame {
318    /// List of both active and inactive overlays in this ScopeFrame.
319    ///
320    /// The order does not have any meaning. Indexed locally (within this ScopeFrame) by
321    /// OverlayIds in active_overlays.
322    pub overlays: Vec<(Vec<u8>, OverlayFrame)>,
323
324    /// List of currently active overlays.
325    ///
326    /// Order is significant: The last item points at the last activated overlay.
327    pub active_overlays: Vec<OverlayId>,
328
329    /// Removed overlays from previous scope frames / permanent state
330    pub removed_overlays: Vec<Vec<u8>>,
331
332    /// temporary storage for predeclarations
333    pub predecls: DeclNameMap,
334
335    /// Where each `type` statement of the block being parsed is, by alias name; filled in with
336    /// the predeclarations and used only to tell a use before the definition from an unknown type.
337    pub type_predecls: HashMap<Vec<u8>, Vec<Span>>,
338
339    /// Variables that `unlet` hid while this frame was parsed (see
340    /// [`StateWorkingSet::hide_variable`](crate::engine::StateWorkingSet::hide_variable)). Only
341    /// the parser's frames use it: merging a delta removes the variables its top frame hid
342    /// from the overlays instead.
343    pub hidden_vars: Vec<VarId>,
344}
345
346impl ScopeFrame {
347    pub fn new() -> Self {
348        Self {
349            overlays: vec![],
350            active_overlays: vec![],
351            removed_overlays: vec![],
352            predecls: DeclNameMap::new(),
353            type_predecls: HashMap::new(),
354            hidden_vars: vec![],
355        }
356    }
357
358    pub fn with_empty_overlay(name: Vec<u8>, origin: ModuleId, prefixed: bool) -> Self {
359        Self {
360            overlays: vec![(name, OverlayFrame::from_origin(origin, prefixed))],
361            active_overlays: vec![OverlayId::new(0)],
362            removed_overlays: vec![],
363            predecls: DeclNameMap::new(),
364            type_predecls: HashMap::new(),
365            hidden_vars: vec![],
366        }
367    }
368
369    pub fn get_var(&self, var_name: &[u8]) -> Option<&VarId> {
370        for overlay_id in self.active_overlays.iter().rev() {
371            if let Some(var_id) = self
372                .overlays
373                .get(overlay_id.get())
374                .expect("internal error: missing overlay")
375                .1
376                .vars
377                .get(var_name)
378            {
379                return Some(var_id);
380            }
381        }
382
383        None
384    }
385
386    pub fn active_overlay_ids(&self, removed_overlays: &mut Vec<Vec<u8>>) -> Vec<OverlayId> {
387        for name in &self.removed_overlays {
388            if !removed_overlays.contains(name) {
389                removed_overlays.push(name.clone());
390            }
391        }
392
393        self.active_overlays
394            .iter()
395            .filter(|id| {
396                !removed_overlays
397                    .iter()
398                    .any(|name| name == self.get_overlay_name(**id))
399            })
400            .copied()
401            .collect()
402    }
403
404    pub fn active_overlays<'a, 'b>(
405        &'b self,
406        removed_overlays: &'a mut Vec<Vec<u8>>,
407    ) -> impl DoubleEndedIterator<Item = &'b OverlayFrame> + 'a
408    where
409        'b: 'a,
410    {
411        // Same filtering as `active_overlay_ids`, but iterated lazily: this runs for every scope
412        // frame on every declaration or variable lookup, so it must not allocate.
413        for name in &self.removed_overlays {
414            if !removed_overlays.contains(name) {
415                removed_overlays.push(name.clone());
416            }
417        }
418        let removed_overlays: &'a Vec<Vec<u8>> = removed_overlays;
419
420        self.active_overlays
421            .iter()
422            .filter(move |id| {
423                !removed_overlays
424                    .iter()
425                    .any(|name| name == self.get_overlay_name(**id))
426            })
427            .map(|id| self.get_overlay(*id))
428    }
429
430    pub fn active_overlay_names(&self, removed_overlays: &mut Vec<Vec<u8>>) -> Vec<&[u8]> {
431        self.active_overlay_ids(removed_overlays)
432            .iter()
433            .map(|id| self.get_overlay_name(*id))
434            .collect()
435    }
436
437    pub fn get_overlay_name(&self, overlay_id: OverlayId) -> &[u8] {
438        &self
439            .overlays
440            .get(overlay_id.get())
441            .expect("internal error: missing overlay")
442            .0
443    }
444
445    pub fn get_overlay(&self, overlay_id: OverlayId) -> &OverlayFrame {
446        &self
447            .overlays
448            .get(overlay_id.get())
449            .expect("internal error: missing overlay")
450            .1
451    }
452
453    pub fn get_overlay_mut(&mut self, overlay_id: OverlayId) -> &mut OverlayFrame {
454        &mut self
455            .overlays
456            .get_mut(overlay_id.get())
457            .expect("internal error: missing overlay")
458            .1
459    }
460
461    pub fn find_overlay(&self, name: &[u8]) -> Option<OverlayId> {
462        self.overlays
463            .iter()
464            .position(|(n, _)| n == name)
465            .map(OverlayId::new)
466    }
467
468    pub fn find_active_overlay(&self, name: &[u8]) -> Option<OverlayId> {
469        self.overlays
470            .iter()
471            .position(|(n, _)| n == name)
472            .map(OverlayId::new)
473            .filter(|id| self.active_overlays.contains(id))
474    }
475}
476
477#[derive(Debug, Clone)]
478pub struct OverlayFrame {
479    pub vars: HashMap<Vec<u8>, VarId>,
480    pub predecls: DeclNameMap, // temporary storage for predeclarations
481    pub decls: DeclNameMap,
482    pub modules: HashMap<Vec<u8>, ModuleId>,
483    pub type_aliases: HashMap<Vec<u8>, TypeAliasId>,
484    pub shadowed_vars: Vec<VarId>,
485    pub visibility: Visibility,
486    pub origin: ModuleId, // The original module the overlay was created from
487    pub prefixed: bool,   // Whether the overlay has definitions prefixed with its name
488}
489
490impl OverlayFrame {
491    pub fn from_origin(origin: ModuleId, prefixed: bool) -> Self {
492        Self {
493            vars: HashMap::new(),
494            predecls: DeclNameMap::new(),
495            decls: DeclNameMap::new(),
496            modules: HashMap::new(),
497            type_aliases: HashMap::new(),
498            shadowed_vars: Vec::new(),
499            visibility: Visibility::new(),
500            origin,
501            prefixed,
502        }
503    }
504
505    pub fn insert_decl(&mut self, name: Vec<u8>, decl_id: DeclId) -> Option<DeclId> {
506        self.decls.insert(name, decl_id)
507    }
508
509    pub fn insert_module(&mut self, name: Vec<u8>, module_id: ModuleId) -> Option<ModuleId> {
510        self.modules.insert(name, module_id)
511    }
512
513    pub fn insert_variable(&mut self, name: Vec<u8>, variable_id: VarId) -> Option<VarId> {
514        let res = self.vars.insert(name, variable_id);
515        if let Some(old_id) = res {
516            self.shadowed_vars.push(old_id);
517        }
518        res
519    }
520
521    pub fn get_decl(&self, name: &[u8]) -> Option<DeclId> {
522        self.decls.get(name).cloned()
523    }
524}
525
526impl Default for Visibility {
527    fn default() -> Self {
528        Self::new()
529    }
530}
531
532impl Default for ScopeFrame {
533    fn default() -> Self {
534        Self::new()
535    }
536}
537
538#[cfg(test)]
539mod visibility_stack_tests {
540    use super::*;
541
542    /// A frame that hides `hidden` and explicitly shows `shown`.
543    fn frame(hidden: &[usize], shown: &[usize]) -> Visibility {
544        let mut visibility = Visibility::new();
545        for id in hidden {
546            visibility.hide_decl_id(&DeclId::new(*id));
547        }
548        for id in shown {
549            visibility.use_decl_id(&DeclId::new(*id));
550        }
551        visibility
552    }
553
554    #[test]
555    fn innermost_frame_with_an_entry_wins_past_the_inline_frames() {
556        // Frame `i` hides decl `i` and shows decl `i + 1`; frames that hide nothing are skipped.
557        let frames: Vec<Visibility> = (0..7).map(|i| frame(&[i], &[i + 1])).collect();
558        let empty = Visibility::new();
559        let mut stack = VisibilityStack::default();
560        for visibility in &frames {
561            stack.push(&empty);
562            stack.push(visibility);
563        }
564        // Decl 0 is only hidden; every other decl is shown by the frame before the one hiding it.
565        assert!(!stack.is_decl_id_visible(&DeclId::new(0)));
566        for id in 1..8 {
567            assert!(stack.is_decl_id_visible(&DeclId::new(id)), "decl {id}");
568        }
569        // A decl no frame mentions is visible.
570        assert!(stack.is_decl_id_visible(&DeclId::new(100)));
571
572        // The same frames with the hiding order reversed: the innermost entry decides.
573        let mut stack = VisibilityStack::default();
574        for visibility in frames.iter().rev() {
575            stack.push(visibility);
576        }
577        assert!(!stack.is_decl_id_visible(&DeclId::new(6)));
578        assert!(stack.is_decl_id_visible(&DeclId::new(7)));
579        assert!(!stack.is_decl_id_visible(&DeclId::new(1)));
580    }
581}