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    lang_items: HashMap<&'static str, Handle>,
61
62    // --- Queues for algorithms ---
63    pub(crate) unchecked: Vec<Handle>,
64    pub(crate) impls: Vec<Handle>,
65    pub(crate) uses: Vec<Handle>,
66}
67
68impl<'a> Table<'a> {
69    pub fn new() -> Self {
70        let mut kinds = IndexMap::new();
71        let mut parents = IndexMap::new();
72        let root = kinds.insert(NodeKind::Root);
73        assert_eq!(root, parents.insert(root));
74
75        Self {
76            root,
77            kinds,
78            parents,
79            children: HashMap::new(),
80            imports: HashMap::new(),
81            use_items: HashMap::new(),
82            bodies: HashMap::new(),
83            types: HashMap::new(),
84            spans: HashMap::new(),
85            metas: HashMap::new(),
86            sources: HashMap::new(),
87            impl_targets: HashMap::new(),
88            anon_types: HashMap::new(),
89            lang_items: HashMap::new(),
90            unchecked: Vec::new(),
91            impls: Vec::new(),
92            uses: Vec::new(),
93        }
94    }
95
96    pub fn entry(&self, handle: Handle) -> Entry<'_, 'a> {
97        handle.to_entry(self)
98    }
99
100    pub fn entry_mut(&mut self, handle: Handle) -> EntryMut<'_, 'a> {
101        handle.to_entry_mut(self)
102    }
103
104    pub fn new_entry(&mut self, parent: Handle, kind: NodeKind) -> Handle {
105        let entry = self.kinds.insert(kind);
106        assert_eq!(entry, self.parents.insert(parent));
107        entry
108    }
109
110    pub fn add_child(&mut self, parent: Handle, name: Sym, child: Handle) -> Option<Handle> {
111        self.children.entry(parent).or_default().insert(name, child)
112    }
113
114    pub fn add_import(&mut self, parent: Handle, name: Sym, import: Handle) -> Option<Handle> {
115        self.imports.entry(parent).or_default().insert(name, import)
116    }
117
118    pub fn mark_unchecked(&mut self, item: Handle) {
119        self.unchecked.push(item);
120    }
121
122    pub fn mark_use_item(&mut self, item: Handle) {
123        let parent = self.parents[item];
124        self.use_items.entry(parent).or_default().push(item);
125        self.uses.push(item);
126    }
127
128    pub fn mark_impl_item(&mut self, item: Handle) {
129        self.impls.push(item);
130    }
131
132    pub fn mark_lang_item(&mut self, name: &'static str, item: Handle) {
133        self.lang_items.insert(name, item);
134    }
135
136    pub fn get_lang_item(&self, name: &str) -> Handle {
137        match self.lang_items.get(name).copied() {
138            Some(handle) => handle,
139            None => todo!(),
140        }
141    }
142
143    pub fn handle_iter(&self) -> impl Iterator<Item = Handle> + use<> {
144        self.kinds.keys()
145    }
146
147    /// Returns handles to all nodes sequentially by [Entry]
148    pub fn debug_entry_iter(&self) -> impl Iterator<Item = Entry<'_, 'a>> {
149        self.kinds.keys().map(|key| key.to_entry(self))
150    }
151
152    /// Gets the [Handle] of an anonymous type with the provided [TypeKind].
153    /// If not already present, a new one is created.
154    pub(crate) fn anon_type(&mut self, kind: TypeKind) -> Handle {
155        if let Some(id) = self.anon_types.get(&kind) {
156            return *id;
157        }
158        let entry = self.new_entry(self.root, NodeKind::Type);
159        // Anonymous types require a bijective map (anon_types => Def => types)
160        self.types.insert(entry, kind.clone());
161        self.anon_types.insert(kind, entry);
162        entry
163    }
164
165    pub(crate) fn inferred_type(&mut self) -> Handle {
166        let handle = self.new_entry(self.root, NodeKind::Type);
167        self.types.insert(handle, TypeKind::Inferred);
168        handle
169    }
170
171    pub(crate) fn type_variable(&mut self) -> Handle {
172        let handle = self.new_entry(self.root, NodeKind::Type);
173        self.types.insert(handle, TypeKind::Variable);
174        handle
175    }
176
177    pub const fn root_entry(&self) -> Entry<'_, 'a> {
178        self.root.to_entry(self)
179    }
180
181    pub fn root_entry_mut(&mut self) -> crate::entry::EntryMut<'_, 'a> {
182        self.root.to_entry_mut(self)
183    }
184
185    // --- inherent properties ---
186
187    pub const fn root(&self) -> Handle {
188        self.root
189    }
190
191    pub fn kind(&self, node: Handle) -> Option<&NodeKind> {
192        self.kinds.get(node)
193    }
194
195    pub fn parent(&self, node: Handle) -> Option<&Handle> {
196        self.parents.get(node)
197    }
198
199    pub fn children(&self, node: Handle) -> Option<&HashMap<Sym, Handle>> {
200        self.children.get(&node)
201    }
202
203    pub fn imports(&self, node: Handle) -> Option<&HashMap<Sym, Handle>> {
204        self.imports.get(&node)
205    }
206
207    pub fn body(&self, node: Handle) -> Option<&'a Expr> {
208        self.bodies.get(&node).copied()
209    }
210
211    pub fn ty(&self, node: Handle) -> Option<&TypeKind> {
212        self.types.get(&node)
213    }
214
215    pub fn span(&self, node: Handle) -> Option<&Span> {
216        self.spans.get(&node)
217    }
218
219    pub fn meta(&self, node: Handle) -> Option<&'a [Meta]> {
220        self.metas.get(&node).copied()
221    }
222
223    pub fn source(&self, node: Handle) -> Option<&Source<'a>> {
224        self.sources.get(&node)
225    }
226
227    pub fn impl_target(&self, node: Handle) -> Option<Handle> {
228        self.impl_targets.get(&node).copied()
229    }
230
231    pub fn reparent(&mut self, node: Handle, parent: Handle) -> Handle {
232        self.parents.replace(node, parent)
233    }
234
235    pub fn set_body(&mut self, node: Handle, body: &'a Expr) -> Option<&'a Expr> {
236        self.mark_unchecked(node);
237        self.bodies.insert(node, body)
238    }
239
240    pub fn set_ty(&mut self, node: Handle, kind: TypeKind) -> Option<TypeKind> {
241        self.types.insert(node, kind)
242    }
243
244    pub fn set_span(&mut self, node: Handle, span: Span) -> Option<Span> {
245        self.spans.insert(node, span)
246    }
247
248    pub fn set_meta(&mut self, node: Handle, meta: &'a [Meta]) -> Option<&'a [Meta]> {
249        self.metas.insert(node, meta)
250    }
251
252    pub fn set_source(&mut self, node: Handle, source: Source<'a>) -> Option<Source<'a>> {
253        self.sources.insert(node, source)
254    }
255
256    pub fn set_impl_target(&mut self, node: Handle, target: Handle) -> Option<Handle> {
257        self.impl_targets.insert(node, target)
258    }
259
260    // --- derived properties ---
261
262    /// Gets a handle to the local `Self` type, if one exists
263    pub fn selfty(&self, node: Handle) -> Option<Handle> {
264        match self.kinds.get(node)? {
265            NodeKind::Root | NodeKind::Use => None,
266            NodeKind::Type => Some(node),
267            NodeKind::Impl => self.impl_target(node),
268            _ => self.selfty(*self.parent(node)?),
269        }
270    }
271
272    pub fn super_of(&self, node: Handle) -> Option<Handle> {
273        match self.kinds.get(node)? {
274            NodeKind::Root => None,
275            NodeKind::Module => self.parent(node).copied(),
276            _ => self.super_of(*self.parent(node)?),
277        }
278    }
279
280    pub fn name(&self, node: Handle) -> Option<Sym> {
281        self.source(node).and_then(|s| s.name())
282    }
283
284    pub fn is_transparent(&self, node: Handle) -> bool {
285        !matches!(
286            self.kind(node),
287            None | Some(NodeKind::Root | NodeKind::Module)
288        )
289    }
290
291    pub fn get_child(&self, node: Handle, name: &Sym) -> Option<Handle> {
292        self.children.get(&node).and_then(|c| c.get(name)).copied()
293    }
294
295    pub fn get_import(&self, node: Handle, name: &Sym) -> Option<Handle> {
296        self.imports.get(&node).and_then(|i| i.get(name)).copied()
297    }
298
299    pub fn get_by_sym(&self, node: Handle, name: &Sym) -> Option<Handle> {
300        self.get_child(node, name)
301            .or_else(|| self.get_import(node, name))
302            .or_else(|| {
303                self.is_transparent(node)
304                    .then(|| {
305                        self.parent(node)
306                            .and_then(|node| self.get_by_sym(*node, name))
307                    })
308                    .flatten()
309            })
310    }
311
312    /// Does path traversal relative to the provided `node`.
313    pub fn nav(&self, node: Handle, path: &[PathPart]) -> Option<Handle> {
314        match path {
315            [PathPart::SuperKw, rest @ ..] => self.nav(self.super_of(node)?, rest),
316            [PathPart::SelfTy, rest @ ..] => self.nav(self.selfty(node)?, rest),
317            [PathPart::Ident(name), rest @ ..] => self.nav(self.get_by_sym(node, name)?, rest),
318            [] => Some(node),
319        }
320    }
321}
322
323impl Default for Table<'_> {
324    fn default() -> Self {
325        Self::new()
326    }
327}
328
329#[derive(Clone, Copy, Debug)]
330pub enum NodeKind {
331    Root,
332    Module,
333    Type,
334    Const,
335    Static,
336    Function,
337    Temporary,
338    Let,
339    Scope,
340    Impl,
341    Use,
342}
343
344mod display {
345    use super::*;
346    use std::fmt;
347    impl fmt::Display for NodeKind {
348        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
349            match self {
350                NodeKind::Root => write!(f, "root"),
351                NodeKind::Module => write!(f, "mod"),
352                NodeKind::Type => write!(f, "type"),
353                NodeKind::Const => write!(f, "const"),
354                NodeKind::Static => write!(f, "static"),
355                NodeKind::Function => write!(f, "fn"),
356                NodeKind::Temporary => write!(f, "temp"),
357                NodeKind::Let => write!(f, "let"),
358                NodeKind::Scope => write!(f, "scope"),
359                NodeKind::Use => write!(f, "use"),
360                NodeKind::Impl => write!(f, "impl"),
361            }
362        }
363    }
364}
cl_typeck/table.rs

cl_typeck/
table.rs
