tierkreis_core/namespace.rs
1//! Defines the [Signature] of a runtime as the mapping from tree-structured
2//! [FunctionName]s to polymorphically-typed [FunctionDeclaration]s each available at
3//! different [Location]s.
4use crate::graph::TypeScheme;
5use crate::symbol::{FunctionName, Label, Location, LocationName, Name, Prefix};
6use itertools::join;
7use std::collections::hash_map::Entry;
8use std::collections::{HashMap, HashSet};
9use thiserror::Error;
10
11/// Information about a function: its polymorphic [TypeScheme], user-readable
12/// description, and port ordering (for debug/display purposes, not used by
13/// the typechecker).
14#[derive(Debug, Clone, PartialEq, Eq)]
15pub struct FunctionDeclaration {
16 /// Polymorphic type scheme describing all possible input/output types
17 pub type_scheme: TypeScheme,
18 /// User-readable documentation
19 pub description: String,
20 /// Order in which to display input ports
21 pub input_order: Vec<Label>,
22 /// Order in which to display output ports
23 pub output_order: Vec<Label>,
24}
25
26/// Tree-structured mapping (sharing common prefixes) from [FunctionName]s
27/// (to some kind of values, typically [FunctionDeclaration] or [NamespaceItem]).
28#[derive(Debug, Clone)]
29pub struct Namespace<T> {
30 /// Items at this level of the name hierarchy
31 pub functions: HashMap<Name, T>,
32 /// Mappings for subtrees of the name hierarchy
33 pub subspaces: HashMap<Prefix, Namespace<T>>,
34}
35
36/// Error when trying to merge two namespaces with different values for the same
37/// [FunctionName].
38#[derive(Debug, Error, Clone)]
39#[error("Conflicting declarations for {}, in namespace {}", .0.name, join(.0.prefixes.iter(), "::"))]
40pub struct ConflictingDeclaration(FunctionName);
41
42impl ConflictingDeclaration {
43 pub(crate) fn extend(mut self, ns: Prefix) -> Self {
44 self.0.prefixes.insert(0, ns);
45 self
46 }
47}
48
49impl<T> Namespace<T> {
50 /// Creates a new, empty, instance.
51 pub fn new() -> Self {
52 Namespace {
53 functions: HashMap::new(),
54 subspaces: HashMap::new(),
55 }
56 }
57
58 /// `true` if there are no functions in the namespace, including in any
59 /// [subspace](Namespace::subspaces); otherwise `false`.
60 pub fn is_empty(&self) -> bool {
61 self.functions.is_empty() && self.subspaces.values().all(|x| x.is_empty())
62 }
63
64 /// Consumes and transforms the namespace by applying a function to every value.
65 /// (Keys are preserved.)
66 pub fn map<S, F>(self, f: F) -> Namespace<S>
67 where
68 F: (Fn(T) -> S) + Clone,
69 {
70 let functions = self.functions.into_iter().map(|(k, v)| (k, f(v))).collect();
71
72 let subspaces = self
73 .subspaces
74 .into_iter()
75 .map(|(k, v)| (k, v.map(f.clone())))
76 .collect();
77
78 Namespace {
79 functions,
80 subspaces,
81 }
82 }
83
84 /// Applies a function to the values in the namespace (keeping the same keys).
85 /// The function takes the values by reference and the [Namespace] is not consumed.
86 pub fn map_ref<S, F>(&self, f: F) -> Namespace<S>
87 where
88 F: (Fn(&T) -> S) + Clone,
89 {
90 let functions = self.functions.iter().map(|(k, v)| (*k, f(v))).collect();
91
92 let subspaces = self
93 .subspaces
94 .iter()
95 .map(|(k, v)| (*k, v.map_ref(f.clone())))
96 .collect();
97
98 Namespace {
99 functions,
100 subspaces,
101 }
102 }
103
104 /// Merge a namespace into another namespace.
105 ///
106 /// `merge_funcs` combines two values (which had the same name), returning either
107 /// `Some` of a new RHS value, or `None` to cause `merge_namespace` to return a
108 /// [ConflictingDeclaration] error.
109 pub fn merge_namespace<F>(
110 &mut self,
111 other: Namespace<T>,
112 merge_funcs: F,
113 ) -> Result<(), ConflictingDeclaration>
114 where
115 F: (Fn(T, T) -> Option<T>) + Clone,
116 {
117 for (name, func) in other.functions {
118 match self.functions.entry(name) {
119 Entry::Occupied(x) => {
120 match merge_funcs(x.remove(), func) {
121 Some(y) => self.functions.insert(name, y),
122 None => {
123 return Err(ConflictingDeclaration(FunctionName {
124 name,
125 prefixes: vec![],
126 }))
127 }
128 };
129 }
130 Entry::Vacant(x) => {
131 x.insert(func);
132 }
133 }
134 }
135
136 for (name, ns) in other.subspaces {
137 match self.subspaces.entry(name) {
138 Entry::Occupied(mut x) => {
139 x.get_mut()
140 .merge_namespace(ns, merge_funcs.clone())
141 .map_err(|e| e.extend(name))?;
142 }
143 Entry::Vacant(x) => {
144 x.insert(ns);
145 }
146 }
147 }
148 Ok(())
149 }
150
151 /// Recursively insert a function into a namespace
152 pub fn insert_into_namespace(&mut self, name: FunctionName, item: T) {
153 let mut ns = self;
154 for space in name.prefixes.iter() {
155 ns = ns.subspaces.entry(*space).or_default();
156 }
157 ns.functions.insert(name.name, item);
158 }
159
160 /// Gets an iterator over the RHS of all mappings, i.e. without any [FunctionName]s
161 pub fn values(&self) -> Box<dyn Iterator<Item = &T> + '_> {
162 let subs = self.subspaces.values().flat_map(|ss| ss.values());
163 Box::new(self.functions.values().chain(subs))
164 }
165
166 /// Looks up a [FunctionName] starting at this point in the name hierarchy
167 pub fn get(&self, name: &FunctionName) -> Option<&T> {
168 let mut namespace = self;
169 for ns in name.prefixes.iter() {
170 namespace = namespace.subspaces.get(ns)?;
171 }
172 namespace.functions.get(&name.name)
173 }
174
175 /// Returns `true` if the namespace is a subset of another namespace `other`
176 pub fn is_subset(&self, other: &Namespace<T>) -> bool
177 where
178 T: PartialEq,
179 {
180 self.functions
181 .iter()
182 .all(|(k, v)| other.functions.get(k) == Some(v))
183 && self
184 .subspaces
185 .iter()
186 .all(|(k, v)| match other.subspaces.get(k) {
187 None => false,
188 Some(v2) => v.is_subset(v2),
189 })
190 }
191}
192
193impl<T> Default for Namespace<T> {
194 fn default() -> Self {
195 Self::new()
196 }
197}
198
199/// A [FunctionDeclaration] with a set of [Location]s at which
200/// the function is supported.
201#[derive(Debug, Clone, PartialEq, Eq)]
202pub struct NamespaceItem {
203 /// Declaration of the function, including typescheme; identical at all locations
204 pub decl: FunctionDeclaration,
205 /// The locations (aka scopes) at which the function is supported
206 pub locations: Vec<Location>,
207}
208
209/// The signature of a runtime is the functions and locations which it knows about.
210#[derive(Debug, Clone, Default)]
211pub struct Signature {
212 /// Every function and location the runtime can run
213 pub root: Namespace<NamespaceItem>,
214 /// Named aliases for polymorphic types.
215 pub aliases: HashMap<String, TypeScheme>,
216 /// All the locations the runtime knows about.
217 /// Must be disjoint from those of any other signature with which
218 /// this one is [merged](Signature::merge_signature).
219 pub scopes: HashSet<Location>,
220}
221
222/// Errors when trying to merge two Signatures - see [Signature::merge_signature]
223#[derive(Error, Debug)]
224pub enum SignatureError {
225 /// The two signatures had different declarations for the same [FunctionName]
226 #[error(transparent)]
227 ConflictingDecl(#[from] ConflictingDeclaration),
228 /// Both [Signature]s had the same [Location] in their [scopes](Signature::scopes)
229 #[error("Scope at location {0} defined twice")]
230 ScopeClash(Location),
231}
232
233impl Signature {
234 /// Transforms this instance by nesting everything inside a [LocationName].
235 /// For example, calling `in_location(loc)` on a [Signature] which declares
236 /// a function "x" in a location "foo", returns a Signature declaring x in "loc::foo".
237 pub fn in_location(mut self, loc: LocationName) -> Self {
238 self.root = self.root.map(|x| NamespaceItem {
239 decl: x.decl,
240 locations: x.locations.into_iter().map(|x| x.prepend(loc)).collect(),
241 });
242 self.scopes = self.scopes.into_iter().map(|x| x.prepend(loc)).collect();
243 self
244 }
245
246 /// Merges another signature into this, producing a new signature whose
247 /// [scopes](Signature::scopes) and whose set of `(FunctionName, Location)` pairs
248 /// are the union of the two input signatures.
249 // ALAN this could be "disjoint union" if we knew a Signature's NamespaceItems were only supported in its own scopes.
250 ///
251 /// # Errors
252 ///
253 /// * If the two sets of [scopes](Signature::scopes) are not disjoint;
254 /// * If the same function(name) is declared by both [Signature]s but with different [FunctionDeclaration]s.
255 pub fn merge_signature(&mut self, other: Signature) -> Result<(), SignatureError> {
256 self.root.merge_namespace(other.root, |a, b| {
257 if a.decl != b.decl {
258 None
259 } else {
260 let mut locations = a.locations;
261 locations.extend(b.locations.into_iter());
262 Some(NamespaceItem {
263 decl: a.decl,
264 locations,
265 })
266 }
267 })?;
268
269 for x in other.scopes {
270 if !self.scopes.insert(x.clone()) {
271 return Err(SignatureError::ScopeClash(x));
272 }
273 }
274
275 for (name, type_) in other.aliases {
276 if self.aliases.contains_key(&name) {
277 continue;
278 }
279
280 self.aliases.insert(name, type_);
281 }
282
283 Ok(())
284 }
285
286 /// Returns `true` if the signature is a subset of another signature `other`
287 pub fn is_subset(&self, other: &Signature) -> bool {
288 self.root.is_subset(&other.root) && self.scopes.is_subset(&other.scopes)
289 }
290
291 /// Gets names and typeschemes (only) of all the functions declared
292 /// in this signature. (That is, throws away all [Location] information,
293 /// as well as fields of [FunctionDeclaration] other than
294 /// [FunctionDeclaration::type_scheme].)
295 pub fn type_schemes(self) -> Namespace<TypeScheme> {
296 self.root.map(|x| x.decl.type_scheme)
297 }
298}