moore_common/
score.rs

1// Copyright (c) 2016-2021 Fabian Schuiki
2
3//! This module implements the scoreboard building blocks. Scoreboards are the
4//! driving mechanism behind moore. They keep track of the results of each
5//! compilation step for every node in the graph. Each node can be accessed in a
6//! type safe manner by its ID.
7
8use std;
9use std::collections::{BTreeMap, HashMap};
10use std::fmt::Debug;
11use std::hash::Hash;
12
13use crate::id::NodeId;
14
15/// A context which provides a language-agnostic scoreboard. This is used by
16/// the language-specific scoreboards to communicate with the global scoreboard.
17pub trait GenericContext {}
18
19/// The `NodeStorage` trait allows for references to nodes to be stored and
20/// retrieved via a unique node ID.
21///
22/// Once a node is created for example in an arena, a reference to it can be
23/// stored in a `NodeStorage` to associate it with an ID. If that ID is
24/// presented to the `NodeStorage` again, that same reference will be produced.
25/// Implementors of this trait are expected to implement it multiple times, once
26/// for each different ID/node type pair that they support. This then allows for
27/// nodes to be looked up in a type safe manner based on their ID.
28///
29/// The `NodeStorage` does not assume ownership over the nodes added to it.
30/// Therefore all nodes are references of at least the lifetime `'tn`.
31///
32/// # Example
33///
34/// ```
35/// use moore_common::score::NodeStorage;
36/// use std::collections::HashMap;
37///
38/// #[derive(PartialEq, Eq, Debug)]
39/// struct Foo;
40/// #[derive(PartialEq, Eq, Debug)]
41/// struct Bar;
42///
43/// #[derive(Clone, Copy, Hash, PartialEq, Eq, Debug)]
44/// struct FooId(usize);
45/// #[derive(Clone, Copy, Hash, PartialEq, Eq, Debug)]
46/// struct BarId(usize);
47///
48/// struct Table<'tn> {
49///     foos: HashMap<FooId, &'tn Foo>,
50///     bars: HashMap<BarId, &'tn Bar>,
51/// }
52///
53/// impl<'tn> NodeStorage<FooId> for Table<'tn> {
54///     type Node = &'tn Foo;
55///     fn get(&self, id: &FooId) -> Option<&&'tn Foo> { self.foos.get(id) }
56///     fn set(&mut self, id: FooId, node: &'tn Foo) -> Option<&'tn Foo> { self.foos.insert(id, node) }
57/// }
58///
59/// impl<'tn> NodeStorage<BarId> for Table<'tn> {
60///     type Node = &'tn Bar;
61///     fn get(&self, id: &BarId) -> Option<&&'tn Bar> { self.bars.get(id) }
62///     fn set(&mut self, id: BarId, node: &'tn Bar) -> Option<&'tn Bar> { self.bars.insert(id, node) }
63/// }
64///
65/// // Store node refs in table:
66/// let foo = Foo;
67/// let bar = Bar;
68/// let mut tbl = Table{ foos: HashMap::new(), bars: HashMap::new() };
69/// tbl.set(FooId(1), &foo);
70/// tbl.set(BarId(2), &bar);
71///
72/// // Retrieve node refs again:
73/// assert_eq!(tbl.get(&FooId(1)), Some(&&foo));
74/// assert_eq!(tbl.get(&BarId(2)), Some(&&bar));
75/// assert_eq!(tbl.get(&BarId(1)), None);
76/// assert_eq!(tbl.get(&FooId(2)), None);
77///
78/// // The following would produce a compiler error due to type mismatch:
79/// // let _: &Foo = *tbl.get(&BarId(1)).unwrap();
80/// // let _: &Bar = *tbl.get(&FooId(2)).unwrap();
81/// ```
82pub trait NodeStorage<I> {
83    /// The type of the node that is returned when presented with an ID of type
84    /// `I`.
85    type Node;
86
87    /// Obtains a reference to the node with the given ID.
88    ///
89    /// Returns `None` when no node with the given ID exists.
90    fn get(&self, id: &I) -> Option<&Self::Node>;
91
92    /// Store a reference to a node under the given ID.
93    ///
94    /// Later that reference can be retrieved again by presenting the same ID to
95    /// the `get` function. Returns the previously stored entry, if any.
96    fn set(&mut self, id: I, node: Self::Node) -> Option<Self::Node>;
97}
98
99// Implement the NodeStorage trait for HashMaps.
100impl<K, V> NodeStorage<K> for HashMap<K, V>
101where
102    K: Hash + Eq,
103{
104    type Node = V;
105
106    fn get(&self, id: &K) -> Option<&V> {
107        HashMap::get(self, id)
108    }
109
110    fn set(&mut self, id: K, node: V) -> Option<V> {
111        HashMap::insert(self, id, node)
112    }
113}
114
115// Implement the NodeStorage trait for BTreeMaps.
116impl<K, V> NodeStorage<K> for BTreeMap<K, V>
117where
118    K: Ord,
119{
120    type Node = V;
121
122    fn get(&self, id: &K) -> Option<&V> {
123        BTreeMap::get(self, id)
124    }
125
126    fn set(&mut self, id: K, node: V) -> Option<V> {
127        BTreeMap::insert(self, id, node)
128    }
129}
130
131/// The `NodeMaker` trait allows for nodes to be generated from an ID.
132///
133/// This is useful in conjunction with the `NodeStorage` and `Scoreboard`
134/// traits. If a value is requested that the scoreboard cannot find, this trait
135/// allows for the node to be generated. For example, if the AST for a node is
136/// requested but does not exist, this trait can be implemented in such a way
137/// that said AST is loaded. This allows for complex on-demand loading and
138/// compilation to be implemented.
139///
140/// The nodes are expected to be owned either by the caller or some arena.
141/// Therefore only a reference to the created node is returned.
142///
143/// # Example
144///
145/// ```
146/// use moore_common::score::{self, NodeMaker};
147///
148/// #[derive(PartialEq, Eq, Debug)]
149/// struct Foo;
150/// #[derive(PartialEq, Eq, Debug)]
151/// struct Bar;
152///
153/// struct FooId(usize);
154/// struct BarId(usize);
155///
156/// struct Table;
157///
158/// impl<'tn> NodeMaker<FooId, &'tn Foo> for Table {
159///     fn make(&self, id: FooId) -> score::Result<&'tn Foo> {
160///         static FOO: Foo = Foo;
161///         Ok(&FOO) // usually you would allocate this in an arena
162///     }
163/// }
164///
165/// impl<'tn> NodeMaker<BarId, &'tn Bar> for Table {
166///     fn make(&self, id: BarId) -> score::Result<&'tn Bar> {
167///         static BAR: Bar = Bar;
168///         Ok(&BAR) // usually you would allocate this in an arena
169///     }
170/// }
171///
172/// let tbl = Table;
173/// let foo = tbl.make(FooId(1)).unwrap();
174/// let bar = tbl.make(BarId(2)).unwrap();
175/// assert_eq!(foo, &Foo);
176/// assert_eq!(bar, &Bar);
177///
178/// // The following would produce a compiler error due to type mismatch:
179/// // assert_eq!(foo, &Bar);
180/// // assert_eq!(bar, &Foo);
181/// ```
182pub trait NodeMaker<I, N> {
183    /// Creates the node with the given ID.
184    ///
185    /// Returns `Err(())` upon failure. Note that the generated node has
186    /// lifetime `'tn` that outlives the `NodeMaker`. This is required to allow
187    /// for the `NodeMaker` to generate multiple nodes at the same time. The
188    /// generated nodes should be owned by an arena or the owner of the
189    /// `NodeMaker` itself.
190    fn make(&self, id: I) -> Result<N>;
191}
192
193/// The result of making a node. Errors that occur while making a node should be
194/// reported via a separate channel, e.g. diagnostics, which provide more
195/// information to the user.
196pub type Result<T> = std::result::Result<T, ()>;
197
198/// A reference to a node.
199///
200/// Newtypes around `NodeId` should implement this trait to offer functionality
201/// common to all node references.
202pub trait NodeRef: Copy + Eq + Ord + Hash + Debug + Into<NodeId> {
203    /// Allocate a new reference.
204    ///
205    /// Creates a new unique reference. Calls `NodeId::alloc()` under the hood.
206    fn alloc() -> Self {
207        Self::new(NodeId::alloc())
208    }
209
210    /// Create a new reference from an existing node ID.
211    fn new(id: NodeId) -> Self;
212}
213
214/// Create a new node reference.
215///
216/// This is merely a wrapper around `NodeId` to provide a type safe
217/// representation of a node.
218///
219/// # Example
220///
221/// ```
222/// #[macro_use]
223/// extern crate moore_common;
224///
225/// # fn main() {
226/// node_ref!(FooRef);
227/// node_ref!(BarRef);
228/// # }
229/// ```
230///
231/// This creates two structs `FooRef` and `BarRef` that both wrap around a
232/// `NodeId`.
233#[macro_export]
234macro_rules! node_ref {
235    ($name:ident) => {
236        #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
237        pub struct $name($crate::NodeId);
238
239        impl std::fmt::Debug for $name {
240            fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
241                write!(f, "{}({:?})", stringify!($name), self.0)
242            }
243        }
244
245        impl Into<$crate::NodeId> for $name {
246            fn into(self) -> $crate::NodeId {
247                self.0
248            }
249        }
250
251        impl $crate::score::NodeRef for $name {
252            fn new(id: $crate::NodeId) -> $name {
253                $name(id)
254            }
255        }
256    };
257}
258
259/// Create a new group of node references.
260///
261/// This is a simple enum that contains variants for each of the references.
262/// Implements `From` for the various references, and `Into<NodeId>`.
263#[macro_export]
264macro_rules! node_ref_group {
265    ($name:ident: $($var:ident($ty:ty),)+) => {
266        #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
267        pub enum $name {
268            $($var($ty),)*
269        }
270
271        impl std::fmt::Debug for $name {
272            fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
273                node_ref_group!(MATCHES *self, $($name::$var(id) => write!(f, "{}({:?})", stringify!($var), id)),*)
274            }
275        }
276
277        impl Into<$crate::NodeId> for $name {
278            fn into(self) -> $crate::NodeId {
279                node_ref_group!(MATCHES self, $($name::$var(id) => id.into()),*)
280            }
281        }
282
283        $(
284        impl From<$ty> for $name {
285            fn from(id: $ty) -> $name {
286                $name::$var(id)
287            }
288        }
289        )*
290    };
291
292    (MATCHES $value:expr, $($lhs:pat => $rhs:expr),+) => {
293        match $value {
294            $($lhs => $rhs),+
295        }
296    };
297}
298
299/// Create a new table that implements the `NodeStorage` trait.
300///
301/// The resulting table can then be used to store nodes in a type safe manner.
302///
303/// # Example
304///
305/// ```
306/// #[macro_use]
307/// extern crate moore_common;
308/// use moore_common::score::NodeStorage;
309/// # use std::collections::HashMap;
310///
311/// #[derive(PartialEq, Eq, Hash, Debug)]
312/// struct FooRef(usize);
313/// #[derive(PartialEq, Eq, Hash, Debug)]
314/// struct BarRef(usize);
315///
316/// #[derive(PartialEq, Eq, Debug)]
317/// struct Foo;
318/// #[derive(PartialEq, Eq, Debug)]
319/// struct Bar;
320///
321/// node_storage!(NodeTable<'tn>:
322///     foos: FooRef => &'tn Foo,
323///     bars: BarRef => &'tn Bar,
324/// );
325///
326/// # fn main() {
327/// let foo = &Foo;
328/// let bar = &Bar;
329///
330/// let mut tbl = NodeTable::new();
331/// tbl.set(FooRef(0), foo);
332/// tbl.set(BarRef(1), bar);
333///
334/// assert_eq!(tbl.get(&FooRef(0)), Some(&foo));
335/// assert_eq!(tbl.get(&BarRef(1)), Some(&bar));
336///
337/// // The following would produce a compiler error due to the type mismatch:
338/// // assert_eq!(tbl.get(&BarRef(0)), Some(&foo));
339/// // assert_eq!(tbl.get(&FooRef(1)), Some(&bar));
340/// # }
341/// ```
342#[macro_export]
343macro_rules! node_storage {
344    ($name:ident<$($lt:tt),+>: $($node_name:ident : $node_ref:ty => $node:ty,)+) => {
345        pub struct $name<$($lt),*> {
346            $($node_name: std::collections::HashMap<$node_ref, $node>,)*
347        }
348
349        node_storage!(STRUCT_IMPL $name; $($lt),*; $($node_name, $node_ref, $node;)*);
350    };
351
352    ($name:ident<$($lt:tt),+> where ($($wh:tt)+): $($node_name:ident : $node_ref:ty => $node:ty,)+) => {
353        pub struct $name<$($lt),*> where $($wh)* {
354            $($node_name: std::collections::HashMap<$node_ref, $node>,)*
355        }
356
357        node_storage!(STRUCT_IMPL $name; $($lt),*; $($node_name, $node_ref, $node;)*);
358    };
359
360    (STRUCT_IMPL $name:ident; $($lt:tt),+; $($node_name:ident, $node_ref:ty, $node:ty;)*) => {
361        impl<$($lt),*> $name<$($lt),*> {
362            /// Create a new empty table.
363            pub fn new() -> $name<$($lt),*> {
364                $name {
365                    $($node_name: std::collections::HashMap::new(),)*
366                }
367            }
368        }
369
370        node_storage!(TRAIT_IMPL $name; $($lt),*; $($node_name, $node_ref, $node;)*);
371    };
372
373    (TRAIT_IMPL $name:ident; $($lt:tt),+; $node_name:ident, $node_ref:ty, $node:ty; $($tail_name:ident, $tail_ref:ty, $tail:ty;)*) => {
374        impl<$($lt),*> $crate::score::NodeStorage<$node_ref> for $name<$($lt),*> {
375            type Node = $node;
376
377            fn get(&self, id: &$node_ref) -> Option<&$node> {
378                self.$node_name.get(id)
379            }
380
381            fn set(&mut self, id: $node_ref, node: $node) -> Option<$node> {
382                self.$node_name.insert(id, node)
383            }
384        }
385
386        node_storage!(TRAIT_IMPL $name; $($lt),*; $($tail_name, $tail_ref, $tail;)*);
387    };
388
389    (TRAIT_IMPL $name:ident; $($lt:tt),*;) => {}
390}
moore_common/score.rs

moore_common/
score.rs
