spade_hir/
symbol_table.rs

Help
1use std::collections::HashMap;
2
3use colored::Colorize;
4use itertools::Itertools;
5use serde::{Deserialize, Serialize};
6use tap::prelude::*;
7use tracing::trace;
8
9use spade_common::id_tracker::NameIdTracker;
10use spade_common::location_info::{Loc, WithLocation};
11use spade_common::name::{Identifier, NameID, Path};
12use spade_diagnostics::diagnostic::Diagnostic;
13use spade_types::meta_types::MetaType;
14
15use crate::{
16    FunctionKind, ParameterList, TraitSpec, TypeExpression, TypeParam, TypeSpec, UnitHead, UnitKind,
17};
18
19#[derive(Debug, Clone, PartialEq)]
20pub enum LookupError {
21    NoSuchSymbol(Loc<Path>),
22    NotAThing(Loc<Path>),
23    NotATypeSymbol(Loc<Path>, Thing),
24    NotAVariable(Loc<Path>, Thing),
25    NotAUnit(Loc<Path>, Thing),
26    NotAnEnumVariant(Loc<Path>, Thing),
27    NotAPatternableType(Loc<Path>, Thing),
28    NotAStruct(Loc<Path>, Thing),
29    NotAValue(Loc<Path>, Thing),
30    NotAComptimeValue(Loc<Path>, Thing),
31    NotATrait(Loc<Path>, Thing),
32    IsAType(Loc<Path>),
33    BarrierError(Diagnostic),
34}
35
36impl From<LookupError> for Diagnostic {
37    fn from(lookup_error: LookupError) -> Diagnostic {
38        match &lookup_error {
39            LookupError::NoSuchSymbol(path) => {
40                Diagnostic::error(path, format!("Use of undeclared name {path}"))
41                    .primary_label("Undeclared name")
42            }
43            LookupError::NotAThing(path) => {
44                Diagnostic::error(path, format!("Use of {path} before it was decleared"))
45                    .primary_label("Undeclared name")
46            }
47            LookupError::IsAType(path) => {
48                Diagnostic::error(path, format!("Unexpected type {path}"))
49                    .primary_label("Unexpected type")
50            }
51            LookupError::BarrierError(diag) => diag.clone(),
52            LookupError::NotATypeSymbol(path, got)
53            | LookupError::NotAVariable(path, got)
54            | LookupError::NotAUnit(path, got)
55            | LookupError::NotAnEnumVariant(path, got)
56            | LookupError::NotAPatternableType(path, got)
57            | LookupError::NotAStruct(path, got)
58            | LookupError::NotAValue(path, got)
59            | LookupError::NotATrait(path, got)
60            | LookupError::NotAComptimeValue(path, got) => {
61                let expected = match lookup_error {
62                    LookupError::NotATypeSymbol(_, _) => "a type",
63                    LookupError::NotAVariable(_, _) => "a variable",
64                    LookupError::NotAUnit(_, _) => "a unit",
65                    LookupError::NotAnEnumVariant(_, _) => "an enum variant",
66                    LookupError::NotAPatternableType(_, _) => "a patternable type",
67                    LookupError::NotAStruct(_, _) => "a struct",
68                    LookupError::NotAValue(_, _) => "a value",
69                    LookupError::NotAComptimeValue(_, _) => "a compile time value",
70                    LookupError::NotATrait(_, _) => "a trait",
71                    LookupError::NoSuchSymbol(_)
72                    | LookupError::IsAType(_)
73                    | LookupError::BarrierError(_)
74                    | LookupError::NotAThing(_) => unreachable!(),
75                };
76
77                // an entity can be instantiated, ...
78                let hint = match lookup_error {
79                    LookupError::NotAComptimeValue(_, _) => {
80                        Some("compile time values can be defined with $config <name> = value")
81                    }
82                    _ => None,
83                };
84                let mut diagnostic =
85                    Diagnostic::error(path, format!("Expected {path} to be {expected}"))
86                        .primary_label(format!("Expected {expected}"))
87                        .secondary_label(got.loc(), format!("{path} is a {}", got.kind_string()));
88
89                if let Some(hint) = hint {
90                    diagnostic.add_help(hint);
91                }
92
93                match lookup_error {
94                    LookupError::NotAValue(path, Thing::EnumVariant(v)) => diagnostic
95                        .span_suggest_insert_after(
96                            "Consider specifying the arguments to the variant",
97                            path,
98                            format!(
99                                "({})",
100                                v.inner
101                                    .params
102                                    .0
103                                    .iter()
104                                    .map(|a| format!("/* {} */", a.name))
105                                    .join(", ")
106                            ),
107                        ),
108                    LookupError::NotAValue(path, Thing::Struct(v)) => diagnostic
109                        .span_suggest_insert_after(
110                            "Consider specifying the struct parameters",
111                            path,
112                            format!(
113                                "({})",
114                                v.inner
115                                    .params
116                                    .0
117                                    .iter()
118                                    .map(|a| format!("/*{}*/", a.name))
119                                    .join(", ")
120                            ),
121                        ),
122                    _ => diagnostic,
123                }
124            }
125        }
126    }
127}
128
129#[derive(Debug, Clone, PartialEq)]
130pub enum UniqueNameError {
131    MultipleDefinitions { new: Loc<Path>, prev: Loc<()> },
132}
133
134#[derive(PartialEq, Debug, Clone, Serialize, Deserialize)]
135pub struct EnumVariant {
136    pub name: Loc<Identifier>,
137    pub output_type: Loc<TypeSpec>,
138    pub option: usize,
139    pub params: Loc<ParameterList>,
140    pub type_params: Vec<Loc<TypeParam>>,
141    pub documentation: String,
142}
143impl WithLocation for EnumVariant {}
144
145impl EnumVariant {
146    pub fn as_unit_head(&self) -> UnitHead {
147        UnitHead {
148            name: self.name.clone(),
149            inputs: self.params.clone(),
150            output_type: Some(self.output_type.clone()),
151            unit_type_params: self.type_params.clone(),
152            scope_type_params: self.type_params.clone(),
153            unit_kind: UnitKind::Function(FunctionKind::Enum).at_loc(&self.name),
154            where_clauses: vec![],
155            documentation: String::new(),
156        }
157    }
158}
159
160#[derive(PartialEq, Debug, Clone, Serialize, Deserialize)]
161pub struct StructCallable {
162    pub name: Loc<Identifier>,
163    pub self_type: Loc<TypeSpec>,
164    pub params: Loc<ParameterList>,
165    pub type_params: Vec<Loc<TypeParam>>,
166}
167impl WithLocation for StructCallable {}
168impl StructCallable {
169    pub fn as_unit_head(&self) -> UnitHead {
170        UnitHead {
171            name: self.name.clone(),
172            inputs: self.params.clone(),
173            output_type: Some(self.self_type.clone()),
174            unit_type_params: self.type_params.clone(),
175            scope_type_params: vec![],
176            unit_kind: UnitKind::Function(FunctionKind::Struct).at_loc(&self.name),
177            where_clauses: vec![],
178            documentation: String::new(),
179        }
180    }
181}
182
183/// Any named thing in the language which is not a type. Structs are here for instantiation
184/// under the same NameID as the type
185#[derive(PartialEq, Debug, Clone, Serialize, Deserialize)]
186pub enum Thing {
187    /// Definition of a named type
188    Struct(Loc<StructCallable>),
189    EnumVariant(Loc<EnumVariant>),
190    Unit(Loc<UnitHead>),
191    Variable(Loc<Identifier>),
192    Alias {
193        path: Loc<Path>,
194        in_namespace: Path,
195    },
196    PipelineStage(Loc<Identifier>),
197    Module(Loc<Identifier>),
198    /// Actual trait definition is present in the item list. This is only a marker
199    /// for there being a trait with the item name.
200    Trait(Loc<Identifier>),
201}
202
203impl Thing {
204    pub fn kind_string(&self) -> &'static str {
205        match self {
206            Thing::Struct(_) => "struct",
207            Thing::Unit(_) => "unit",
208            Thing::Variable(_) => "variable",
209            Thing::EnumVariant(_) => "enum variant",
210            Thing::Alias { .. } => "alias",
211            Thing::PipelineStage(_) => "pipeline stage",
212            Thing::Trait(_) => "trait",
213            Thing::Module(_) => "module",
214        }
215    }
216
217    /// The Loc of the entire Thing.
218    pub fn loc(&self) -> Loc<()> {
219        match self {
220            Thing::Struct(i) => i.loc(),
221            Thing::Variable(i) => i.loc(),
222            Thing::Unit(i) => i.loc(),
223            Thing::EnumVariant(i) => i.loc(),
224            Thing::Alias {
225                path,
226                in_namespace: _,
227            } => path.loc(),
228            Thing::PipelineStage(i) => i.loc(),
229            Thing::Trait(loc) => loc.loc(),
230            Thing::Module(loc) => loc.loc(),
231        }
232    }
233
234    /// The Loc where the name of the thing is defined.
235    pub fn name_loc(&self) -> Loc<()> {
236        match self {
237            Thing::Struct(s) => s.name.loc(),
238            Thing::EnumVariant(v) => v.name.loc(),
239            Thing::Unit(f) => f.name.loc(),
240            Thing::Variable(v) => v.loc(),
241            Thing::Alias {
242                path,
243                in_namespace: _,
244            } => path.loc(),
245            Thing::PipelineStage(_) => todo!(),
246            Thing::Trait(loc) => loc.loc(),
247            Thing::Module(loc) => loc.loc(),
248        }
249    }
250}
251
252#[derive(PartialEq, Debug, Clone)]
253pub enum PatternableKind {
254    Struct,
255    Enum,
256}
257#[derive(PartialEq, Debug, Clone)]
258pub struct Patternable {
259    pub kind: PatternableKind,
260    pub params: Loc<ParameterList>,
261}
262impl WithLocation for Patternable {}
263
264#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
265pub enum GenericArg {
266    TypeName {
267        name: Identifier,
268        traits: Vec<Loc<TraitSpec>>,
269    },
270    TypeWithMeta {
271        name: Identifier,
272        meta: MetaType,
273    },
274}
275
276impl GenericArg {
277    pub fn uint(name: Identifier) -> Self {
278        GenericArg::TypeWithMeta {
279            name,
280            meta: MetaType::Uint,
281        }
282    }
283}
284impl WithLocation for GenericArg {}
285
286#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
287pub enum TypeDeclKind {
288    Struct { is_port: bool },
289    Enum,
290    Primitive { is_port: bool },
291}
292
293impl TypeDeclKind {
294    pub fn normal_struct() -> Self {
295        TypeDeclKind::Struct { is_port: false }
296    }
297    pub fn struct_port() -> Self {
298        TypeDeclKind::Struct { is_port: true }
299    }
300
301    pub fn name(&self) -> String {
302        match self {
303            TypeDeclKind::Struct { is_port } => {
304                format!("struct{}", if *is_port { " port" } else { "" })
305            }
306            TypeDeclKind::Enum => "enum".to_string(),
307            TypeDeclKind::Primitive { .. } => "primitive".to_string(),
308        }
309    }
310}
311
312/// A previously declared type symbol
313#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
314pub enum TypeSymbol {
315    /// A fixed type that has been declared, like a typedef, enum or struct with the
316    /// specified generic arguments
317    Declared(Vec<Loc<GenericArg>>, TypeDeclKind),
318    /// A generic type present in the current scope
319    GenericArg {
320        traits: Vec<Loc<TraitSpec>>,
321    },
322    GenericMeta(MetaType),
323    /// A type alias. This is lowered during initial AST lowering, so subsequent compilation
324    /// stages can bail on finding this
325    Alias(Loc<TypeExpression>),
326}
327impl WithLocation for TypeSymbol {}
328
329/// The declaration/definition status of a variable
330#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
331pub enum DeclarationState {
332    /// This variable has been defined by a `decl` statement
333    Undefined(NameID),
334    /// There is a pipeline reference to this variable, but no definition or declaration (yet)
335    Undecleared(NameID),
336    /// This variable has been defined (and assigned) with a let binding.
337    /// All variables must be in the declared state before the end of the scope
338    Defined(Loc<()>),
339}
340impl WithLocation for DeclarationState {}
341
342pub type ScopeBarrier =
343    dyn Fn(&Loc<Path>, &Loc<NameID>, &Thing) -> Result<(), Diagnostic> + Send + Sync;
344
345#[derive(Serialize, Deserialize)]
346pub struct Scope {
347    vars: HashMap<Path, NameID>,
348    #[serde(skip)]
349    lookup_barrier: Option<Box<ScopeBarrier>>,
350}
351impl std::fmt::Debug for Scope {
352    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
353        let Self {
354            vars,
355            lookup_barrier: _,
356        } = self;
357        write!(f, "Scope({vars:?})")
358    }
359}
360
361/// A table of the symbols known to the program in the current scope. Names
362/// are mapped to IDs which are then mapped to the actual things
363///
364/// Modules are managed by a special variable in the symtab. All names in the
365/// symtab are absolute paths, that is `X` in `mod A{mod B {fn X}}` will only be
366/// stored as `A::B::X`. All variables inside X will also have the full path
367/// appended to them. This should however be invisible to the user.
368#[derive(Debug, Serialize, Deserialize)]
369pub struct SymbolTable {
370    /// Each outer vec is a scope, inner vecs are symbols in that scope
371    pub symbols: Vec<Scope>,
372    pub declarations: Vec<HashMap<Loc<Identifier>, DeclarationState>>,
373    id_tracker: NameIdTracker,
374    pub types: HashMap<NameID, Loc<TypeSymbol>>,
375    pub things: HashMap<NameID, Thing>,
376    /// The namespace which we are currently in. When looking up and adding symbols, this namespace
377    /// is added to the start of the path, thus ensuring all paths are absolute. If a path is not
378    /// found that path is also looked up in the global namespace
379    namespace: Path,
380    /// The namespace which `lib` refers to currently.
381    base_namespace: Path,
382}
383
384impl Default for SymbolTable {
385    fn default() -> Self {
386        Self::new()
387    }
388}
389
390impl SymbolTable {
391    pub fn new() -> Self {
392        Self {
393            symbols: vec![Scope {
394                vars: HashMap::new(),
395                lookup_barrier: None,
396            }],
397            declarations: vec![HashMap::new()],
398            id_tracker: NameIdTracker::new(),
399            types: HashMap::new(),
400            things: HashMap::new(),
401            namespace: Path(vec![]),
402            base_namespace: Path(vec![]),
403        }
404    }
405    #[tracing::instrument(skip_all)]
406    pub fn new_scope(&mut self) {
407        self.symbols.push(Scope {
408            vars: HashMap::new(),
409            lookup_barrier: None,
410        });
411        self.declarations.push(HashMap::new());
412    }
413
414    pub fn new_scope_with_barrier(&mut self, barrier: Box<ScopeBarrier>) {
415        self.symbols.push(Scope {
416            vars: HashMap::new(),
417            lookup_barrier: Some(barrier),
418        });
419        self.declarations.push(HashMap::new());
420    }
421
422    #[tracing::instrument(skip_all)]
423    pub fn close_scope(&mut self) {
424        self.symbols.pop();
425        self.declarations.pop();
426    }
427
428    pub fn current_scope(&self) -> usize {
429        self.symbols.len() - 1
430    }
431
432    /// Push an identifier onto the current namespace
433    #[tracing::instrument(skip_all, fields(%new_ident))]
434    pub fn push_namespace(&mut self, new_ident: Loc<Identifier>) {
435        self.namespace = self.namespace.push_ident(new_ident.clone());
436    }
437
438    #[tracing::instrument(skip_all)]
439    pub fn pop_namespace(&mut self) {
440        self.namespace = self.namespace.pop();
441    }
442
443    pub fn current_namespace(&self) -> &Path {
444        &self.namespace
445    }
446
447    pub fn set_base_namespace(&mut self, base_namespace: Path) {
448        self.base_namespace = base_namespace
449    }
450
451    /// Adds a thing to the scope at `current_scope - offset`. Panics if there is no such scope
452    pub fn add_thing_with_id_at_offset(
453        &mut self,
454        offset: usize,
455        id: u64,
456        name: Path,
457        item: Thing,
458    ) -> NameID {
459        let full_name = self.namespace.join(name);
460
461        let name_id = NameID(id, full_name.clone());
462        if self.things.contains_key(&name_id) {
463            panic!("Duplicate nameID inserted, {}", id);
464        }
465        self.things.insert(name_id.clone(), item);
466
467        if offset > self.symbols.len() {
468            panic!("Not enough scopes to add symbol at offset {}", offset);
469        }
470
471        let index = self.symbols.len() - 1 - offset;
472        self.symbols[index].vars.insert(full_name, name_id.clone());
473
474        name_id
475    }
476
477    /// Add a thing to the symtab with the specified NameID. The NameID must already be in
478    /// the symtab when calling this function
479    pub fn add_thing_with_name_id(&mut self, name_id: NameID, item: Thing) {
480        self.things.insert(name_id, item);
481    }
482
483    pub fn add_thing_with_id(&mut self, id: u64, name: Path, item: Thing) -> NameID {
484        self.add_thing_with_id_at_offset(0, id, name, item)
485    }
486
487    #[tracing::instrument(skip_all, fields(?name))]
488    pub fn add_unique_thing(&mut self, name: Loc<Path>, item: Thing) -> Result<NameID, Diagnostic> {
489        self.ensure_is_unique(&name)?;
490        Ok(self.add_thing(name.inner, item))
491    }
492
493    pub fn add_thing(&mut self, name: Path, item: Thing) -> NameID {
494        let id = self.id_tracker.next();
495        self.add_thing_with_id(id, name, item)
496    }
497
498    pub fn re_add_type(&mut self, name: Loc<Identifier>, name_id: NameID) {
499        assert!(self.types.contains_key(&name_id));
500        self.symbols
501            .last_mut()
502            .unwrap()
503            .vars
504            .insert(self.namespace.join(Path::ident(name)), name_id);
505    }
506
507    pub fn add_type_with_id(&mut self, id: u64, name: Path, t: Loc<TypeSymbol>) -> NameID {
508        let full_name = self.namespace.join(name);
509        let name_id = NameID(id, full_name.clone());
510        if self.types.contains_key(&name_id) {
511            panic!("Duplicate nameID for types, {}", id)
512        }
513        self.types.insert(name_id.clone(), t);
514        self.symbols
515            .last_mut()
516            .unwrap()
517            .vars
518            .insert(full_name, name_id.clone());
519        name_id
520    }
521
522    pub fn add_type(&mut self, name: Path, t: Loc<TypeSymbol>) -> NameID {
523        let id = self.id_tracker.next();
524        self.add_type_with_id(id, name, t)
525    }
526
527    pub fn add_traits_to_generic(
528        &mut self,
529        name_id: &NameID,
530        traits: Vec<Loc<TraitSpec>>,
531    ) -> Result<(), Diagnostic> {
532        assert!(self.types.contains_key(&name_id));
533        match &mut self.types.get_mut(name_id).unwrap().inner {
534            TypeSymbol::GenericArg { traits: existing } => {
535                existing.extend(traits);
536                Ok(())
537            }
538            _ => Err(Diagnostic::bug(
539                self.type_symbol_by_id(name_id).loc(),
540                "Attempted to add trait bounds to a non-generic type",
541            )),
542        }
543    }
544
545    pub fn add_unique_type(
546        &mut self,
547        name: Loc<Path>,
548        t: Loc<TypeSymbol>,
549    ) -> Result<NameID, Diagnostic> {
550        self.ensure_is_unique(&name)?;
551
552        Ok(self.add_type(name.inner, t))
553    }
554
555    #[tracing::instrument(skip_all, fields(?name, ?target))]
556    pub fn add_alias(&mut self, name: Loc<Path>, target: Loc<Path>) -> Result<NameID, Diagnostic> {
557        self.ensure_is_unique(&name)?;
558        let absolute_path = if let Some(lib_relative) = target.inner.lib_relative() {
559            self.base_namespace.join(lib_relative)
560        } else {
561            target.inner.clone()
562        };
563        let path = absolute_path.between(name.file_id, &name, &target);
564        Ok(self.add_thing(
565            name.inner,
566            Thing::Alias {
567                path,
568                in_namespace: self.current_namespace().clone(),
569            },
570        ))
571    }
572
573    /// Adds a thing to the scope at `current_scope - offset`. Panics if there is no such scope
574    pub fn add_thing_at_offset(&mut self, offset: usize, name: Path, item: Thing) -> NameID {
575        let id = self.id_tracker.next();
576        self.add_thing_with_id_at_offset(offset, id, name, item)
577    }
578
579    pub fn freeze(self) -> FrozenSymtab {
580        let id_tracker = self.id_tracker.make_clone();
581        FrozenSymtab {
582            inner: self,
583            id_tracker,
584        }
585    }
586
587    pub fn add_local_variable(&mut self, name: Loc<Identifier>) -> NameID {
588        let path = Path(vec![name.clone()]);
589        self.add_thing(path, Thing::Variable(name))
590    }
591    pub fn add_local_variable_at_offset(&mut self, offset: usize, name: Loc<Identifier>) -> NameID {
592        let path = Path(vec![name.clone()]);
593        self.add_thing_at_offset(offset, path, Thing::Variable(name))
594    }
595
596    pub fn add_declaration(&mut self, ident: Loc<Identifier>) -> Result<NameID, Diagnostic> {
597        let declared_more_than_once = |new, old| {
598            Diagnostic::error(new, "Variable declared more than once")
599                .primary_label("This variable has been declared more than once")
600                .secondary_label(old, "Previously declared here")
601        };
602        // Check if a variable with this name already exists
603        if let Some(id) = self.try_lookup_id(&Path(vec![ident.clone()]).at_loc(&ident), &[]) {
604            if let Some(Thing::Variable(prev)) = self.things.get(&id) {
605                return Err(declared_more_than_once(ident, prev));
606            }
607        }
608
609        if let Some((old, _)) = self.declarations.last().unwrap().get_key_value(&ident) {
610            Err(declared_more_than_once(ident, old))
611        } else {
612            let name_id = self.add_local_variable(ident.clone());
613            self.declarations
614                .last_mut()
615                .unwrap()
616                .insert(ident, DeclarationState::Undefined(name_id.clone()));
617            Ok(name_id)
618        }
619    }
620
621    pub fn add_undecleared_at_offset(&mut self, offset: usize, name: Loc<Identifier>) -> NameID {
622        let path = Path(vec![name.clone()]);
623
624        let name_id = NameID(self.id_tracker.next(), path.clone());
625        let full_name = self.namespace.join(path);
626
627        let index = self.symbols.len() - 1 - offset;
628        if index > self.symbols.len() {
629            panic!("Not enough scopes to add symbol at offset {}", offset);
630        }
631        self.symbols[index].vars.insert(full_name, name_id.clone());
632        self.declarations[index].insert(name, DeclarationState::Undecleared(name_id.clone()));
633
634        name_id
635    }
636
637    pub fn get_declaration(&mut self, ident: &Loc<Identifier>) -> Option<Loc<DeclarationState>> {
638        self.declarations
639            .last()
640            .unwrap()
641            .get_key_value(ident)
642            .map(|(k, v)| v.clone().at_loc(k))
643    }
644
645    pub fn mark_declaration_defined(&mut self, ident: Loc<Identifier>, definition_point: Loc<()>) {
646        *self
647            .declarations
648            .last_mut()
649            .unwrap()
650            .get_mut(&ident)
651            .unwrap() = DeclarationState::Defined(definition_point)
652    }
653
654    pub fn get_undefined_declarations(&self) -> Vec<(Loc<Identifier>, DeclarationState)> {
655        self.declarations
656            .last()
657            .unwrap()
658            .iter()
659            .filter_map(|(ident, state)| match state {
660                DeclarationState::Undefined(_) => Some((ident.clone(), state.clone())),
661                DeclarationState::Undecleared(_) => Some((ident.clone(), state.clone())),
662                DeclarationState::Defined(_) => None,
663            })
664            .collect()
665    }
666}
667macro_rules! thing_accessors {
668    (
669        $(
670            $by_id_name:ident,
671            $lookup_name:ident,
672            $result:path,
673            $err:ident $(,)?
674            {$($thing:pat => $conversion:expr),*$(,)?}
675        ),*
676    ) => {
677        $(
678            /// Look up an item and panic if the item is not in the symtab or if it is the wrong
679            /// type
680            pub fn $by_id_name(&self, id: &NameID) -> Loc<$result> {
681                match self.things.get(&id) {
682                    $(
683                        Some($thing) => {$conversion}
684                    )*,
685                    Some(other) => panic!("attempted to look up {} but it was {:?}", stringify!($result), other),
686                    None => panic!("No thing entry found for {:?}", id)
687                }
688            }
689
690            /// Look up an item, with errors if the item is not currently in scope, or is not
691            /// convertible to the return type.
692            #[tracing::instrument(level = "trace", skip_all, fields(%name.inner, %name.span, %name.file_id))]
693            pub fn $lookup_name(&self, name: &Loc<Path>) -> Result<(NameID, Loc<$result>), LookupError> {
694                let id = self.lookup_final_id(name, &[]).tap(|id| trace!(?id))?;
695
696                match self.things.get(&id).tap(|thing| trace!(?thing)) {
697                    $(
698                        Some($thing) => {Ok((id, $conversion))}
699                    )*,
700                    Some(other) => Err(LookupError::$err(name.clone(), other.clone())),
701                    None => {
702                        match self.types.get(&id) {
703                            Some(_) => Err(LookupError::IsAType(name.clone())),
704                            None => Err(LookupError::NotAThing(name.clone()))
705                        }
706                    }
707                }
708            }
709        )*
710    }
711}
712
713impl SymbolTable {
714    // Define accessors for accessing items. *_by_id looks up things under the
715    // assumption that the name is in the symtab, and that it is the specified type.
716    // If this is not true, it panics.
717    //
718    // lookup_* looks up items by path, and returns the NameID and item if successful.
719    // If the path is not in scope, or the item is not the right kind, returns an error.
720    thing_accessors! {
721        unit_by_id, lookup_unit, UnitHead, NotAUnit {
722            Thing::Unit(head) => head.clone(),
723            Thing::EnumVariant(variant) => variant.as_unit_head().at_loc(variant),
724            Thing::Struct(s) => s.as_unit_head().at_loc(s),
725        },
726        enum_variant_by_id, lookup_enum_variant, EnumVariant, NotAnEnumVariant {
727            Thing::EnumVariant(variant) => variant.clone()
728        },
729        patternable_type_by_id, lookup_patternable_type, Patternable, NotAPatternableType {
730            Thing::EnumVariant(variant) => Patternable{
731                kind: PatternableKind::Enum,
732                params: variant.params.clone()
733            }.at_loc(variant),
734            Thing::Struct(variant) => Patternable {
735                kind: PatternableKind::Struct,
736                params: variant.params.clone()
737            }.at_loc(variant),
738        },
739        struct_by_id, lookup_struct, StructCallable, NotAStruct {
740            Thing::Struct(s) => s.clone()
741        },
742        trait_by_id, lookup_trait, Identifier, NotATrait {
743            Thing::Trait(t) => t.clone()
744        }
745    }
746
747    pub fn type_symbol_by_id(&self, id: &NameID) -> Loc<TypeSymbol> {
748        match self.types.get(id) {
749            Some(inner) => inner.clone(),
750            None => panic!("No thing entry found for {:?}", id),
751        }
752    }
753
754    pub fn try_type_symbol_by_id(&self, id: &NameID) -> Option<&Loc<TypeSymbol>> {
755        self.types.get(id)
756    }
757
758    pub fn thing_by_id(&self, id: &NameID) -> Option<&Thing> {
759        self.things.get(id)
760    }
761
762    pub fn lookup_type_symbol(
763        &self,
764        name: &Loc<Path>,
765    ) -> Result<(NameID, Loc<TypeSymbol>), LookupError> {
766        let id = self.lookup_final_id(name, &[])?;
767
768        match self.types.get(&id) {
769            Some(tsym) => Ok((id, tsym.clone())),
770            None => match self.things.get(&id) {
771                Some(thing) => Err(LookupError::NotATypeSymbol(name.clone(), thing.clone())),
772                None => panic!("{:?} was in symtab but is neither a type nor a thing", id),
773            },
774        }
775    }
776
777    pub fn has_symbol(&self, name: Path) -> bool {
778        match self.lookup_id(&name.nowhere(), &[]) {
779            Ok(_) => true,
780            Err(LookupError::NoSuchSymbol(_)) => false,
781            Err(LookupError::BarrierError(_)) => unreachable!(),
782            Err(LookupError::NotATypeSymbol(_, _)) => unreachable!(),
783            Err(LookupError::NotAVariable(_, _)) => unreachable!(),
784            Err(LookupError::NotAUnit(_, _)) => unreachable!(),
785            Err(LookupError::NotAPatternableType(_, _)) => unreachable!(),
786            Err(LookupError::NotAnEnumVariant(_, _)) => unreachable!(),
787            Err(LookupError::NotAStruct(_, _)) => unreachable!(),
788            Err(LookupError::NotAValue(_, _)) => unreachable!(),
789            Err(LookupError::NotAComptimeValue(_, _)) => unreachable!(),
790            Err(LookupError::NotATrait(_, _)) => unreachable!(),
791            Err(LookupError::IsAType(_)) => unreachable!(),
792            Err(LookupError::NotAThing(_)) => unreachable!(),
793        }
794    }
795
796    /// Look up the previous definition of `name` returning a "Multiple items with the same name" error if
797    /// such definition already exists. Only an absolute path in the root name space is checked
798    /// as this is intended to be used for item definitions
799    pub fn ensure_is_unique(&self, name: &Loc<Path>) -> Result<(), Diagnostic> {
800        let full_path = self.current_namespace().join(name.inner.clone());
801
802        let prev = self
803            .symbols
804            .first()
805            .unwrap()
806            .vars
807            .get(&full_path)
808            .and_then(|id| {
809                self.things
810                    .get(id)
811                    .map(|thing| thing.name_loc())
812                    .or_else(|| self.types.get(id).map(|t| t.loc()))
813            });
814
815        match prev {
816            Some(prev) => Err(Diagnostic::error(name, "Multiple items with the same name")
817                .primary_label(format!("{} is defined multiple times", name))
818                .secondary_label(prev, "Previous definition here")),
819            None => Ok(()),
820        }
821    }
822
823    pub fn lookup_variable(&self, name: &Loc<Path>) -> Result<NameID, LookupError> {
824        let id = self.lookup_final_id(name, &[])?;
825
826        match self.things.get(&id) {
827            Some(Thing::Variable(_)) => Ok(id),
828            Some(other) => Err(LookupError::NotAVariable(name.clone(), other.clone())),
829            None => match self.types.get(&id) {
830                Some(_) => Err(LookupError::IsAType(name.clone())),
831                None => Err(LookupError::NotAThing(name.clone())),
832            },
833        }
834    }
835
836    /// Look up `name`. If it is defined and a variable, return that name. If it is defined
837    /// but not a variable, return an error. If it is undefined, return None
838    ///
839    /// Intended for use if undefined variables should be declared
840    pub fn try_lookup_variable(&self, name: &Loc<Path>) -> Result<Option<NameID>, LookupError> {
841        let id = self.try_lookup_final_id(name, &[]);
842        match id {
843            Some(id) => match self.things.get(&id) {
844                Some(Thing::Variable(_)) => Ok(Some(id)),
845                Some(other) => Err(LookupError::NotAVariable(name.clone(), other.clone())),
846                None => match self.types.get(&id) {
847                    Some(_) => Err(LookupError::IsAType(name.clone())),
848                    None => Ok(None),
849                },
850            },
851            None => Ok(None),
852        }
853    }
854
855    pub fn try_lookup_final_id(&self, name: &Loc<Path>, forbidden: &[NameID]) -> Option<NameID> {
856        match self.lookup_final_id(name, forbidden) {
857            Ok(id) => Some(id),
858            Err(LookupError::NoSuchSymbol(_)) => None,
859            Err(_) => unreachable!(),
860        }
861    }
862
863    /// Returns the name ID of the provided path if that path exists and resolving
864    /// all aliases along the way.
865    pub fn lookup_final_id(
866        &self,
867        name: &Loc<Path>,
868        forbidden: &[NameID],
869    ) -> Result<NameID, LookupError> {
870        let mut forbidden = forbidden.to_vec();
871        let mut namespace = &self.namespace;
872        let mut name = name.clone();
873
874        loop {
875            let id = self.lookup_id_in_namespace(&name, &forbidden, namespace)?;
876            match self.things.get(&id) {
877                Some(Thing::Alias {
878                    path: alias,
879                    in_namespace,
880                }) => {
881                    forbidden.push(id);
882                    name = alias.clone();
883                    namespace = in_namespace;
884                }
885                _ => return Ok(id),
886            }
887        }
888    }
889
890    pub fn try_lookup_id(&self, name: &Loc<Path>, forbidden: &[NameID]) -> Option<NameID> {
891        match self.lookup_id(name, forbidden) {
892            Ok(id) => Some(id),
893            Err(LookupError::NoSuchSymbol(_)) => None,
894            Err(_) => unreachable!(),
895        }
896    }
897
898    /// Resolves a given relative path to the next thing.
899    ///
900    /// That thing might also be an alias.
901    /// When you want to also resolve aliases, look at [`Self::try_lookup_final_id`] instead.
902    ///
903    /// ## Warning
904    /// For `use A;` where the path is only one segment wide, it will return itself.
905    /// This might end in an infinite lookup. Forbid already looked up nameids or use [`Self::try_lookup_final_id`] instead.
906    #[tracing::instrument(level = "trace", skip(self))]
907    #[inline]
908    pub fn lookup_id(&self, name: &Loc<Path>, forbidden: &[NameID]) -> Result<NameID, LookupError> {
909        self.lookup_id_in_namespace(name, forbidden, &self.namespace)
910    }
911
912    #[tracing::instrument(level = "trace", skip(self))]
913    fn lookup_id_in_namespace(
914        &self,
915        name: &Loc<Path>,
916        forbidden: &[NameID],
917        namespace: &Path,
918    ) -> Result<NameID, LookupError> {
919        // The behaviour depends on whether or not the path is a library relative path (starting
920        // with `lib`) or not. If it is, an absolute lookup of the path obtained by
921        // substituting `lib` for the current `base_path` should be performed.
922        //
923        // If not, three lookups should be performed
924        //  - The path in the root namespace
925        //  - The path in the current namespace
926        //  - The path in other use statements. For example, with
927        //      ```
928        //      use a::b;
929        //
930        //      b::c();
931        //      ```
932        //      A lookup for `b` is performed which returns an alias (a::b). From that, another
933        //      lookup for a::b::c is performed.
934        let absolute_path = if let Some(lib_relative) = name.lib_relative() {
935            self.base_namespace.join(lib_relative).at_loc(name)
936        } else {
937            let local_path = namespace.join(name.inner.clone());
938            let mut barriers: Vec<&Box<ScopeBarrier>> = vec![];
939            for tab in self.symbols.iter().rev() {
940                if let Some(id) = tab.vars.get(&local_path) {
941                    if forbidden.iter().contains(id) {
942                        continue;
943                    }
944                    for barrier in barriers {
945                        self.things
946                            .get(id)
947                            .map(|thing| {
948                                (barrier)(name, &id.clone().at_loc(&thing.name_loc()), thing)
949                                    .map_err(LookupError::BarrierError)
950                            })
951                            .unwrap_or(Ok(()))?;
952                    }
953                    return Ok(id.clone());
954                }
955                if let Some(barrier) = &tab.lookup_barrier {
956                    barriers.push(barrier);
957                }
958            }
959
960            if name.inner.0.len() > 1 {
961                let base_name = name.inner.0.first().unwrap();
962
963                let alias_id =
964                    self.lookup_id(&Path(vec![base_name.clone()]).at_loc(base_name), forbidden)?;
965
966                // Extend forbidden slice with newly used alias
967                let mut forbidden = forbidden.to_vec();
968                forbidden.push(alias_id.clone());
969
970                match self.things.get(&alias_id) {
971                    Some(Thing::Alias {
972                        path: alias_path,
973                        in_namespace,
974                    }) => {
975                        let alias_result =
976                            self.lookup_id_in_namespace(alias_path, &forbidden, in_namespace)?;
977
978                        // Pop the aliased bit of the path
979                        let rest_path = Path(name.inner.0[1..].into());
980
981                        alias_result.1.join(rest_path).at_loc(name)
982                    }
983                    _ => name.clone(),
984                }
985            } else {
986                name.clone()
987            }
988        };
989
990        // Then look up things in the absolute namespace. This is only needed at the
991        // top scope as that's where all top level will be defined
992        if let Some(id) = self.symbols.first().unwrap().vars.get(&absolute_path) {
993            if !forbidden.contains(id) {
994                return Ok(id.clone());
995            }
996        }
997
998        // ERROR: Symbol couldn't be found
999        // Look recursively which path segment can not be found
1000        // This is a check that there are at least 2 path segments and we also grab one.
1001        if let [_first, .., tail] = absolute_path.0.as_slice() {
1002            let prelude = &absolute_path.0[..absolute_path.0.len() - 1];
1003            let _ = self.lookup_id_in_namespace(
1004                &Path(prelude.to_vec()).nowhere(),
1005                forbidden,
1006                namespace,
1007            )?;
1008            Err(LookupError::NoSuchSymbol(
1009                absolute_path.inner.clone().at_loc(tail),
1010            ))
1011        } else {
1012            Err(LookupError::NoSuchSymbol(name.clone()))
1013        }
1014    }
1015
1016    pub fn print_symbols(&self) {
1017        println!("=============================================================");
1018        println!("                      Symtab dump");
1019        println!("=============================================================");
1020        println!("Current namespace is `{}`", self.namespace);
1021        println!("Current base_namespace is `{}`", self.base_namespace);
1022        for (level, scope) in self.symbols.iter().enumerate() {
1023            let indent = (1..level + 1).map(|_| "\t").collect::<Vec<_>>().join("");
1024            println!(">>> new_scope",);
1025
1026            for (path, name) in &scope.vars {
1027                println!(
1028                    "{indent}{path} => {name}",
1029                    path = format!("{path}").cyan(),
1030                    name = format!("{name:?}").yellow()
1031                );
1032            }
1033        }
1034
1035        println!("Things:");
1036        for (name, thing) in &self.things {
1037            print!("{}: ", format!("{name:?}").purple());
1038            match thing {
1039                Thing::Struct(_) => println!("struct"),
1040                Thing::EnumVariant(_) => println!("enum variant"),
1041                Thing::Unit(_) => println!("unit"),
1042                Thing::Variable(_) => println!("variable"),
1043                Thing::Alias { path, in_namespace } => {
1044                    println!("{}", format!("alias => {path} in {in_namespace}").green())
1045                }
1046                Thing::PipelineStage(stage) => println!("'{stage}"),
1047                Thing::Trait(name) => println!("trait {}", name),
1048                Thing::Module(name) => println!("mod {name}"),
1049            }
1050        }
1051
1052        println!("Types:");
1053        for name in self.types.keys() {
1054            print!("{}: ", format!("{name:?}").purple());
1055            println!("type");
1056        }
1057    }
1058}
1059
1060/// A symbol table that cannot have any new symbols added to it. The ID tracker can be used to
1061/// generate new names for for intermediate variables during codegen.
1062///
1063/// Mutable references to `SymbolTable` are never given out, ensuring that nothing can be added to
1064/// the symtab, thus avoiding collisions with things added using the Id tracker.
1065#[derive(Serialize, Deserialize)]
1066pub struct FrozenSymtab {
1067    inner: SymbolTable,
1068    pub id_tracker: NameIdTracker,
1069}
1070
1071impl FrozenSymtab {
1072    pub fn symtab(&self) -> &SymbolTable {
1073        &self.inner
1074    }
1075
1076    pub fn new_name(&mut self, description: Path) -> NameID {
1077        NameID(self.id_tracker.next(), description)
1078    }
1079
1080    /// Unfreeze the symtab, removing access to the underlying id_tracker and
1081    /// giving ownership of the symtab again
1082    pub fn unfreeze(self) -> SymbolTable {
1083        // Ensure that we will not generate any conflicting IDs by re combining
1084        // this with the new ID trakcer by ensuring that the new ID tracker is further
1085        // along than the symtabs
1086        SymbolTable {
1087            id_tracker: self.id_tracker,
1088            ..self.inner
1089        }
1090    }
1091}
spade_hir/symbol_table.rs

spade_hir/
symbol_table.rs
