cl_typeck/
table.rs

1//! The [Table] is a monolithic data structure representing everything the type checker
2//! knows about a program.
3//!
4//! Individual nodes in the table can be queried using the [Entry] API ([Table::entry])
5//! or modified using the [EntryMut] API ([Table::entry_mut]).
6//!
7//! # Contents of a "node"
8//! Always present:
9//! - [NodeKind]: Determines how this node will be treated during the [stages](crate::stage) of
10//!   compilation
11//! - [Parent node](Handle): Arranges this node in the hierarchical graph structure
12//!
13//! Populated as needed:
14//! - Children: An associative array of [names](Sym) to child nodes in the graph. Child nodes are
15//!   arranged in a *strict* tree structure, with no back edges
16//! - Imports: An associative array of [names](Sym) to other nodes in the graph. Not all import
17//!   nodes are back edges, but all back edges *must be* import nodes.
18//! - [Types](TypeKind): Contains type information populated through type checking and inference.
19//!   Nodes with unpopulated types may be considered type variables in the future.
20//! - [Meta](Expr): Metadata decorators. These may have an effect throughout the compiler.
21//! - Impl Targets: Sparse mapping of `impl` nodes to their corresponding targets.
22//! - etc.
23
24use crate::{
25    entry::{Entry, EntryMut},
26    handle::Handle,
27    type_kind::TypeKind,
28};
29use cl_ast::{
30    Expr,
31    types::{Path, Symbol as Sym},
32};
33use cl_structures::{index_map::IndexMap, intern::interned::Interned};
34use std::collections::{BTreeMap, HashMap};
35
36pub type Map<K, V> = BTreeMap<K, V>;
37pub type SymMap<V> = BTreeMap<Sym, V>;
38
39/// The table is a monolithic data structure representing everything the type checker
40/// knows about a program.
41///
42/// See [module documentation](self).
43#[derive(Debug)]
44pub struct Table {
45    root: Handle,
46    /// This is the source of truth for handles
47    kinds: IndexMap<Handle, NodeKind>,
48    parents: IndexMap<Handle, Handle>,
49    pub(crate) children: Map<Handle, SymMap<Handle>>,
50    pub(crate) lazy_imports: Map<Handle, SymMap<Path>>,
51    pub(crate) glob_imports: Map<Handle, Vec<Path>>,
52    pub(crate) names: Map<Handle, Sym>,
53    pub(crate) types: Map<Handle, TypeKind>,
54    pub(crate) metas: Map<Handle, Vec<Expr>>,
55    pub(crate) impls: Map<Handle, Vec<Handle>>,
56    pub(crate) impl_targets: Map<Handle, Handle>,
57    pub(crate) anon_types: HashMap<TypeKind, Handle>,
58    pub(crate) lang_items: Map<&'static str, Handle>,
59
60    // --- Queues for algorithms ---
61    pub(crate) unchecked_handles: Vec<Handle>,
62    pub(crate) pending_impls: Vec<Handle>,
63}
64
65impl Table {
66    pub fn new() -> Self {
67        let mut kinds = IndexMap::new();
68        let mut parents = IndexMap::new();
69        let root = kinds.insert(NodeKind::Root);
70        assert_eq!(root, parents.insert(root));
71
72        Self {
73            root,
74            kinds,
75            parents,
76            children: Map::new(),
77            lazy_imports: Map::new(),
78            glob_imports: Map::new(),
79            names: Map::new(),
80            types: Map::new(),
81            metas: Map::new(),
82            impls: Map::new(),
83            impl_targets: Map::new(),
84            anon_types: HashMap::new(),
85            lang_items: Map::new(),
86            unchecked_handles: Vec::new(),
87            pending_impls: Vec::new(),
88        }
89    }
90
91    /// Gets the [Entry] for a [Handle] in the [Table]
92    pub fn entry(&self, handle: Handle) -> Entry<'_> {
93        handle.to_entry(self)
94    }
95
96    /// Gets the [EntryMut] for a [Handle] in the [Table]
97    pub fn entry_mut(&mut self, handle: Handle) -> EntryMut<'_> {
98        handle.to_entry_mut(self)
99    }
100
101    /// Creates a new entry in the table, and returns its [Handle]
102    pub fn new_entry(&mut self, parent: Handle, kind: NodeKind) -> Handle {
103        let entry = self.kinds.insert(kind);
104        assert_eq!(entry, self.parents.insert(parent));
105        entry
106    }
107
108    /// Adds an existing [Handle] as the child of another (parent) [Handle]
109    pub fn add_child(&mut self, parent: Handle, name: Sym, child: Handle) -> Option<Handle> {
110        self.children.entry(parent).or_default().insert(name, child)
111    }
112
113    /// Marks this item as not having been typechecked
114    pub fn mark_unchecked(&mut self, item: Handle) {
115        self.unchecked_handles.push(item);
116    }
117
118    /// Marks this item as an `impl` which hasn't been linked.
119    pub fn mark_impl_item(&mut self, item: Handle) {
120        let parent = self.parent(item).copied().unwrap_or(item);
121        self.impls.entry(parent).or_default().push(item);
122        self.pending_impls.push(item);
123    }
124
125    /// Marks this item as a "lang item", to be [retrieved later](Table::get_lang_item)
126    pub fn mark_lang_item(&mut self, name: &'static str, item: Handle) {
127        self.lang_items.insert(name, item);
128    }
129
130    /// Gets a previously [marked](Table::get_lang_item) lang-item from the table.
131    pub fn get_lang_item(&self, name: &str) -> Handle {
132        match self.lang_items.get(name).copied() {
133            Some(handle) => handle,
134            None => todo!(),
135        }
136    }
137
138    /// Gets an [Iterator] over [Handles](Handle) in the Table
139    pub fn handle_iter(&self) -> impl Iterator<Item = Handle> + use<> {
140        self.kinds.keys()
141    }
142
143    /// Returns handles to all nodes sequentially by [Entry]
144    pub fn debug_entry_iter(&self) -> impl Iterator<Item = Entry<'_>> {
145        self.kinds.keys().map(|key| key.to_entry(self))
146    }
147
148    /// Gets the [Handle] of an anonymous type with the provided [TypeKind].
149    /// If not already present, a new one is created.
150    pub(crate) fn anon_type(&mut self, kind: TypeKind) -> Handle {
151        if let Some(id) = self.anon_types.get(&kind) {
152            return *id;
153        }
154        let entry = self.new_entry(self.root, NodeKind::Type);
155        // Anonymous types require a bijective map (anon_types => Def => types)
156        self.types.insert(entry, kind.clone());
157        self.anon_types.insert(kind, entry);
158        entry
159    }
160
161    /// Gets a [Handle] to a new [NodeKind::Type] with [TypeKind::Inferred]
162    pub(crate) fn inferred_type(&mut self) -> Handle {
163        let handle = self.new_entry(self.root, NodeKind::Type);
164        self.types.insert(handle, TypeKind::Inferred);
165        handle
166    }
167
168    /// Gets a [Handle] to a new [NodeKind::Type] with [TypeKind::Variable]
169    pub(crate) fn type_variable(&mut self) -> Handle {
170        let handle = self.new_entry(self.root, NodeKind::Type);
171        self.types.insert(handle, TypeKind::Variable);
172        handle
173    }
174
175    /// Gets the root [Entry] in the table
176    pub const fn root_entry(&self) -> Entry<'_> {
177        self.root.to_entry(self)
178    }
179
180    /// Gets the root [EntryMut] in the table
181    pub fn root_entry_mut(&mut self) -> crate::entry::EntryMut<'_> {
182        self.root.to_entry_mut(self)
183    }
184
185    // --- inherent properties ---
186
187    /// Gets the root [Handle] in the table.
188    pub const fn root(&self) -> Handle {
189        self.root
190    }
191
192    /// Gets the [NodeKind] of the given [Handle]
193    pub fn kind(&self, node: Handle) -> Option<&NodeKind> {
194        self.kinds.get(node)
195    }
196
197    /// Gets the parent [Handle] of the given [Handle]
198    pub fn parent(&self, node: Handle) -> Option<&Handle> {
199        self.parents.get(node)
200    }
201
202    /// Gets the child map of the given [Handle]
203    pub fn children(&self, node: Handle) -> Option<&SymMap<Handle>> {
204        self.children.get(&node)
205    }
206
207    /// Gets the lazy import map of the given [Handle]
208    pub fn lazy_imports(&self, node: Handle) -> Option<&SymMap<Path>> {
209        self.lazy_imports.get(&node)
210    }
211
212    /// Gets the glob-import set of the given [Handle]
213    pub fn glob_imports(&self, node: Handle) -> Option<&[Path]> {
214        self.glob_imports.get(&node).map(Vec::as_slice)
215    }
216
217    /// Gets the [TypeKind] of the given [Handle]
218    pub fn ty(&self, node: Handle) -> Option<&TypeKind> {
219        self.types.get(&node)
220    }
221
222    /// Gets the [meta-expressions](Expr) of the given [Handle]
223    pub fn meta(&self, node: Handle) -> Option<&[Expr]> {
224        self.metas.get(&node).map(Vec::as_slice)
225    }
226
227    /// Gets the `impl` target of the given [Handle], if there is one
228    pub fn impl_target(&self, node: Handle) -> Option<Handle> {
229        self.impl_targets.get(&node).copied()
230    }
231
232    /// Replaces the parent [Handle] of the given node, returning the old one
233    pub fn reparent(&mut self, node: Handle, parent: Handle) -> Handle {
234        self.parents.replace(node, parent)
235    }
236
237    /// Adds a lazy-import to the entry at the `node` [Handle]
238    pub fn add_import(&mut self, node: Handle, name: Sym, path: Path) {
239        self.lazy_imports
240            .entry(node)
241            .or_default()
242            .insert(name, path);
243    }
244
245    /// Adds a glob-import at the given node
246    pub fn add_glob(&mut self, node: Handle, path: Path) {
247        self.glob_imports.entry(node).or_default().push(path);
248    }
249
250    /// Sets the preferred name of the given node
251    pub fn set_name(&mut self, node: Handle, name: Sym) -> Option<Sym> {
252        self.names.insert(node, name)
253    }
254
255    /// Sets the [TypeKind] of the given node
256    pub fn set_ty(&mut self, node: Handle, kind: TypeKind) -> Option<TypeKind> {
257        self.types.insert(node, kind)
258    }
259
260    /// Sets the [meta-expressions](Expr) of the given node, returning the old expressions
261    pub fn set_meta(&mut self, node: Handle, meta: Vec<Expr>) {
262        self.metas.entry(node).or_default().extend(meta);
263    }
264
265    pub fn add_meta(&mut self, node: Handle, meta: Expr) {
266        self.metas.entry(node).or_default().push(meta);
267    }
268
269    /// Sets the `impl` target of the given node
270    pub fn set_impl_target(&mut self, node: Handle, target: Handle) -> Option<Handle> {
271        self.impl_targets.insert(node, target)
272    }
273
274    // --- derived properties ---
275
276    /// Gets a handle to the local `Self` type, if one exists
277    pub fn selfty(&self, node: Handle) -> Option<Handle> {
278        match self.kinds.get(node)? {
279            NodeKind::Root | NodeKind::Use => None,
280            NodeKind::Type => Some(node),
281            NodeKind::Impl => self.impl_target(node),
282            _ => self.selfty(*self.parent(node)?),
283        }
284    }
285
286    /// Gets the local parent *module*
287    pub fn super_of(&self, node: Handle) -> Option<Handle> {
288        match self.kinds.get(node)? {
289            NodeKind::Root => None,
290            NodeKind::Module => self.parent(node).copied(),
291            _ => self.super_of(*self.parent(node)?),
292        }
293    }
294
295    /// Gets the name of this node
296    pub fn name(&self, node: Handle) -> Option<Sym> {
297        self.names.get(&node).copied()
298    }
299
300    /// Returns `true` when name resolution is allowed to defer to the parent of this node
301    pub fn is_transparent(&self, node: Handle) -> bool {
302        !matches!(
303            self.kind(node),
304            None | Some(NodeKind::Root | NodeKind::Module)
305        )
306    }
307
308    /// Gets the child of this `node` with the given `name`
309    pub fn get_child(&self, node: Handle, name: &Sym) -> Option<Handle> {
310        self.children.get(&node).and_then(|c| c.get(name)).copied()
311    }
312
313    /// Searches the import hierarchy for a particular name
314    pub fn get_import(&self, node: Handle, name: &Sym) -> Option<Handle> {
315        if let Some(path) = self.lazy_imports(node).and_then(|t| t.get(name)) {
316            return self.nav(node, &path.parts);
317        }
318        self.glob_imports(node)
319            .into_iter()
320            .flatten()
321            .rev()
322            .flat_map(|path| self.nav(node, &path.parts))
323            .find_map(|node| self.get_by_sym(node, name))
324    }
325
326    pub fn get_by_sym(&self, node: Handle, name: &Sym) -> Option<Handle> {
327        self.get_child(node, name)
328            .or_else(|| {
329                self.is_transparent(node)
330                    .then(|| {
331                        self.parent(node)
332                            .and_then(|node| self.get_by_sym(*node, name))
333                    })
334                    .flatten()
335            })
336            .or_else(|| self.get_import(node, name))
337    }
338
339    /// Does path traversal relative to the provided `node`.
340    pub fn nav(&self, node: Handle, path: &[Sym]) -> Option<Handle> {
341        // println!(
342        //     "Navigating to {}::{:?}",
343        //     self.name(node).unwrap_or_default(),
344        //     path
345        // );
346        match path {
347            [Interned("", ..), rest @ ..] => self.nav(self.root, rest),
348            [Interned("super", ..), rest @ ..] => self.nav(self.super_of(node)?, rest),
349            [Interned("Self", ..), rest @ ..] => self.nav(self.selfty(node)?, rest),
350            [name, rest @ ..] => self.nav(self.get_by_sym(node, name)?, rest),
351            [] => Some(node),
352        }
353    }
354}
355
356impl Default for Table {
357    fn default() -> Self {
358        Self::new()
359    }
360}
361
362#[derive(Clone, Copy, Debug)]
363pub enum NodeKind {
364    Root,
365    Module,
366    Type,
367    Const,
368    Static,
369    Function,
370    Temporary,
371    Let,
372    Scope,
373    Impl,
374    Use,
375}
376
377mod display {
378    use super::*;
379    use std::fmt;
380    impl fmt::Display for NodeKind {
381        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
382            match self {
383                NodeKind::Root => write!(f, "root"),
384                NodeKind::Module => write!(f, "mod"),
385                NodeKind::Type => write!(f, "type"),
386                NodeKind::Const => write!(f, "const"),
387                NodeKind::Static => write!(f, "static"),
388                NodeKind::Function => write!(f, "fn"),
389                NodeKind::Temporary => write!(f, "temp"),
390                NodeKind::Let => write!(f, "let"),
391                NodeKind::Scope => write!(f, "scope"),
392                NodeKind::Use => write!(f, "use"),
393                NodeKind::Impl => write!(f, "impl"),
394            }
395        }
396    }
397}
cl_typeck/table.rs

cl_typeck/
table.rs
