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//! - [Spans][span]: Positional information from the source text. See [cl_structures::span].
21//! - [Metas](Meta): Metadata decorators. These may have an effect throughout the compiler.
22//! - [Sources](Source): Pointers back into the AST, for future analysis.
23//! - Impl Targets: Sparse mapping of `impl` nodes to their corresponding targets.
24//! - etc.
25//!
26//! [span]: struct@Span
27
28use crate::{
29    entry::{Entry, EntryMut},
30    handle::Handle,
31    source::Source,
32    type_kind::TypeKind,
33};
34use cl_ast::{Expr, Meta, PathPart, Sym};
35use cl_structures::{index_map::IndexMap, span::Span};
36use std::collections::HashMap;
37
38// TODO: Cycle detection external to this module
39
40/// The table is a monolithic data structure representing everything the type checker
41/// knows about a program.
42///
43/// See [module documentation](self).
44#[derive(Debug)]
45pub struct Table<'a> {
46    root: Handle,
47    /// This is the source of truth for handles
48    kinds: IndexMap<Handle, NodeKind>,
49    parents: IndexMap<Handle, Handle>,
50    pub(crate) children: HashMap<Handle, HashMap<Sym, Handle>>,
51    pub(crate) imports: HashMap<Handle, HashMap<Sym, Handle>>,
52    pub(crate) use_items: HashMap<Handle, Vec<Handle>>,
53    bodies: HashMap<Handle, &'a Expr>,
54    types: HashMap<Handle, TypeKind>,
55    spans: HashMap<Handle, Span>,
56    metas: HashMap<Handle, &'a [Meta]>,
57    sources: HashMap<Handle, Source<'a>>,
58    impl_targets: HashMap<Handle, Handle>,
59    anon_types: HashMap<TypeKind, Handle>,
60
61    // --- Queues for algorithms ---
62    pub(crate) impls: Vec<Handle>,
63    pub(crate) uses: Vec<Handle>,
64}
65
66impl<'a> Table<'a> {
67    pub fn new() -> Self {
68        let mut kinds = IndexMap::new();
69        let mut parents = IndexMap::new();
70        let root = kinds.insert(NodeKind::Root);
71        assert_eq!(root, parents.insert(root));
72
73        Self {
74            root,
75            kinds,
76            parents,
77            children: HashMap::new(),
78            imports: HashMap::new(),
79            use_items: HashMap::new(),
80            bodies: HashMap::new(),
81            types: HashMap::new(),
82            spans: HashMap::new(),
83            metas: HashMap::new(),
84            sources: HashMap::new(),
85            impl_targets: HashMap::new(),
86            anon_types: HashMap::new(),
87            impls: Vec::new(),
88            uses: Vec::new(),
89        }
90    }
91
92    pub fn entry(&self, handle: Handle) -> Entry<'_, 'a> {
93        handle.to_entry(self)
94    }
95
96    pub fn entry_mut(&mut self, handle: Handle) -> EntryMut<'_, 'a> {
97        handle.to_entry_mut(self)
98    }
99
100    pub fn new_entry(&mut self, parent: Handle, kind: NodeKind) -> Handle {
101        let entry = self.kinds.insert(kind);
102        assert_eq!(entry, self.parents.insert(parent));
103        entry
104    }
105
106    pub fn add_child(&mut self, parent: Handle, name: Sym, child: Handle) -> Option<Handle> {
107        self.children.entry(parent).or_default().insert(name, child)
108    }
109
110    pub fn add_import(&mut self, parent: Handle, name: Sym, import: Handle) -> Option<Handle> {
111        self.imports.entry(parent).or_default().insert(name, import)
112    }
113
114    pub fn mark_use_item(&mut self, item: Handle) {
115        let parent = self.parents[item];
116        self.use_items.entry(parent).or_default().push(item);
117        self.uses.push(item);
118    }
119
120    pub fn mark_impl_item(&mut self, item: Handle) {
121        self.impls.push(item);
122    }
123
124    pub fn handle_iter(&mut self) -> impl Iterator<Item = Handle> + use<> {
125        self.kinds.keys()
126    }
127
128    /// Returns handles to all nodes sequentially by [Entry]
129    pub fn debug_entry_iter(&self) -> impl Iterator<Item = Entry<'_, 'a>> {
130        self.kinds.keys().map(|key| key.to_entry(self))
131    }
132
133    /// Gets the [Handle] of an anonymous type with the provided [TypeKind].
134    /// If not already present, a new one is created.
135    pub(crate) fn anon_type(&mut self, kind: TypeKind) -> Handle {
136        if let Some(id) = self.anon_types.get(&kind) {
137            return *id;
138        }
139        let entry = self.new_entry(self.root, NodeKind::Type);
140        // Anonymous types require a bijective map (anon_types => Def => types)
141        self.types.insert(entry, kind.clone());
142        self.anon_types.insert(kind, entry);
143        entry
144    }
145
146    pub(crate) fn inferred_type(&mut self) -> Handle {
147        let handle = self.new_entry(self.root, NodeKind::Type);
148        self.types.insert(handle, TypeKind::Inferred);
149        handle
150    }
151
152    pub(crate) fn type_variable(&mut self) -> Handle {
153        let handle = self.new_entry(self.root, NodeKind::Type);
154        self.types.insert(handle, TypeKind::Variable);
155        handle
156    }
157
158    pub const fn root_entry(&self) -> Entry<'_, 'a> {
159        self.root.to_entry(self)
160    }
161
162    pub fn root_entry_mut(&mut self) -> crate::entry::EntryMut<'_, 'a> {
163        self.root.to_entry_mut(self)
164    }
165
166    // --- inherent properties ---
167
168    pub const fn root(&self) -> Handle {
169        self.root
170    }
171
172    pub fn kind(&self, node: Handle) -> Option<&NodeKind> {
173        self.kinds.get(node)
174    }
175
176    pub fn parent(&self, node: Handle) -> Option<&Handle> {
177        self.parents.get(node)
178    }
179
180    pub fn children(&self, node: Handle) -> Option<&HashMap<Sym, Handle>> {
181        self.children.get(&node)
182    }
183
184    pub fn imports(&self, node: Handle) -> Option<&HashMap<Sym, Handle>> {
185        self.imports.get(&node)
186    }
187
188    pub fn body(&self, node: Handle) -> Option<&'a Expr> {
189        self.bodies.get(&node).copied()
190    }
191
192    pub fn ty(&self, node: Handle) -> Option<&TypeKind> {
193        self.types.get(&node)
194    }
195
196    pub fn span(&self, node: Handle) -> Option<&Span> {
197        self.spans.get(&node)
198    }
199
200    pub fn meta(&self, node: Handle) -> Option<&'a [Meta]> {
201        self.metas.get(&node).copied()
202    }
203
204    pub fn source(&self, node: Handle) -> Option<&Source<'a>> {
205        self.sources.get(&node)
206    }
207
208    pub fn impl_target(&self, node: Handle) -> Option<Handle> {
209        self.impl_targets.get(&node).copied()
210    }
211
212    pub fn set_body(&mut self, node: Handle, body: &'a Expr) -> Option<&'a Expr> {
213        self.bodies.insert(node, body)
214    }
215
216    pub fn set_ty(&mut self, node: Handle, kind: TypeKind) -> Option<TypeKind> {
217        self.types.insert(node, kind)
218    }
219
220    pub fn set_span(&mut self, node: Handle, span: Span) -> Option<Span> {
221        self.spans.insert(node, span)
222    }
223
224    pub fn set_meta(&mut self, node: Handle, meta: &'a [Meta]) -> Option<&'a [Meta]> {
225        self.metas.insert(node, meta)
226    }
227
228    pub fn set_source(&mut self, node: Handle, source: Source<'a>) -> Option<Source<'a>> {
229        self.sources.insert(node, source)
230    }
231
232    pub fn set_impl_target(&mut self, node: Handle, target: Handle) -> Option<Handle> {
233        self.impl_targets.insert(node, target)
234    }
235
236    // --- derived properties ---
237
238    /// Gets a handle to the local `Self` type, if one exists
239    pub fn selfty(&self, node: Handle) -> Option<Handle> {
240        match self.kinds.get(node)? {
241            NodeKind::Root | NodeKind::Use => None,
242            NodeKind::Type => Some(node),
243            NodeKind::Impl => self.impl_target(node),
244            _ => self.selfty(*self.parent(node)?),
245        }
246    }
247
248    pub fn super_of(&self, node: Handle) -> Option<Handle> {
249        match self.kinds.get(node)? {
250            NodeKind::Root => None,
251            NodeKind::Module => self.parent(node).copied(),
252            _ => self.super_of(*self.parent(node)?),
253        }
254    }
255
256    pub fn name(&self, node: Handle) -> Option<Sym> {
257        self.source(node).and_then(|s| s.name())
258    }
259
260    pub fn is_transparent(&self, node: Handle) -> bool {
261        !matches!(
262            self.kind(node),
263            None | Some(NodeKind::Root | NodeKind::Module)
264        )
265    }
266
267    pub fn get_child(&self, node: Handle, name: &Sym) -> Option<Handle> {
268        self.children.get(&node).and_then(|c| c.get(name)).copied()
269    }
270
271    pub fn get_import(&self, node: Handle, name: &Sym) -> Option<Handle> {
272        self.imports.get(&node).and_then(|i| i.get(name)).copied()
273    }
274
275    pub fn get_by_sym(&self, node: Handle, name: &Sym) -> Option<Handle> {
276        self.get_child(node, name)
277            .or_else(|| self.get_import(node, name))
278            .or_else(|| {
279                self.is_transparent(node)
280                    .then(|| {
281                        self.parent(node)
282                            .and_then(|node| self.get_by_sym(*node, name))
283                    })
284                    .flatten()
285            })
286    }
287
288    /// Does path traversal relative to the provided `node`.
289    pub fn nav(&self, node: Handle, path: &[PathPart]) -> Option<Handle> {
290        match path {
291            [PathPart::SuperKw, rest @ ..] => self.nav(self.super_of(node)?, rest),
292            [PathPart::SelfTy, rest @ ..] => self.nav(self.selfty(node)?, rest),
293            [PathPart::Ident(name), rest @ ..] => self.nav(self.get_by_sym(node, name)?, rest),
294            [] => Some(node),
295        }
296    }
297}
298
299impl Default for Table<'_> {
300    fn default() -> Self {
301        Self::new()
302    }
303}
304
305#[derive(Clone, Copy, Debug)]
306pub enum NodeKind {
307    Root,
308    Module,
309    Type,
310    Const,
311    Static,
312    Function,
313    Temporary,
314    Local,
315    Impl,
316    Use,
317}
318
319mod display {
320    use super::*;
321    use std::fmt;
322    impl fmt::Display for NodeKind {
323        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
324            match self {
325                NodeKind::Root => write!(f, "root"),
326                NodeKind::Module => write!(f, "mod"),
327                NodeKind::Type => write!(f, "type"),
328                NodeKind::Const => write!(f, "const"),
329                NodeKind::Static => write!(f, "static"),
330                NodeKind::Function => write!(f, "fn"),
331                NodeKind::Temporary => write!(f, "temp"),
332                NodeKind::Local => write!(f, "local"),
333                NodeKind::Use => write!(f, "use"),
334                NodeKind::Impl => write!(f, "impl"),
335            }
336        }
337    }
338}
cl_typeck/table.rs

cl_typeck/
table.rs
