spade_typeinference/
mir_type_lowering.rs

1use std::collections::HashMap;
2
3use hir::symbol_table::SymbolTable;
4use hir::{Parameter, TypeExpression, TypeSpec};
5use spade_common::id_tracker::ExprID;
6use spade_common::location_info::{Loc, WithLocation};
7use spade_common::name::NameID;
8use spade_diagnostics::Diagnostic;
9use spade_hir::{self as hir, ConstGenericWithId};
10use spade_hir::{TypeDeclaration, TypeList};
11use spade_types::{ConcreteType, KnownType, PrimitiveType};
12
13use crate::equation::{TypeVar, TypeVarID, TypedExpression};
14use crate::TypeState;
15
16pub trait HasConcreteType {
17    fn into_typed_expression(&self) -> Loc<TypedExpression>;
18}
19
20impl<T> HasConcreteType for &mut T
21where
22    T: HasConcreteType,
23{
24    fn into_typed_expression(&self) -> Loc<TypedExpression> {
25        (**self).into_typed_expression()
26    }
27}
28
29impl<T> HasConcreteType for &T
30where
31    T: HasConcreteType,
32{
33    fn into_typed_expression(&self) -> Loc<TypedExpression> {
34        (*self).into_typed_expression()
35    }
36}
37
38impl<T> HasConcreteType for Box<T>
39where
40    T: HasConcreteType,
41{
42    fn into_typed_expression(&self) -> Loc<TypedExpression> {
43        self.as_ref().into_typed_expression()
44    }
45}
46
47impl HasConcreteType for Loc<ExprID> {
48    fn into_typed_expression(&self) -> Loc<TypedExpression> {
49        TypedExpression::Id(self.inner).at_loc(self)
50    }
51}
52
53impl HasConcreteType for Loc<&ExprID> {
54    fn into_typed_expression(&self) -> Loc<TypedExpression> {
55        TypedExpression::Id(*self.inner).at_loc(self)
56    }
57}
58
59impl HasConcreteType for Loc<hir::Expression> {
60    fn into_typed_expression(&self) -> Loc<TypedExpression> {
61        TypedExpression::Id(self.id).at_loc(self)
62    }
63}
64
65impl HasConcreteType for Loc<hir::Pattern> {
66    fn into_typed_expression(&self) -> Loc<TypedExpression> {
67        TypedExpression::Id(self.id).at_loc(self)
68    }
69}
70impl HasConcreteType for Loc<ConstGenericWithId> {
71    fn into_typed_expression(&self) -> Loc<TypedExpression> {
72        TypedExpression::Id(self.id).at_loc(self)
73    }
74}
75
76impl HasConcreteType for Loc<NameID> {
77    fn into_typed_expression(&self) -> Loc<TypedExpression> {
78        TypedExpression::Name(self.inner.clone()).at_loc(self)
79    }
80}
81
82impl TypeState {
83    pub fn type_decl_to_concrete(
84        decl: &TypeDeclaration,
85        type_list: &TypeList,
86        params: Vec<ConcreteType>,
87        invert: bool,
88    ) -> ConcreteType {
89        // Mapping between generic name and type param
90
91        assert!(
92            params.len() == decl.generic_args.len(),
93            "Too few type decl params in {:?}\n\n    params: {:?}\n    decl: {:?}",
94            decl,
95            params,
96            decl.generic_args
97        );
98
99        let generic_subs = decl
100            .generic_args
101            .iter()
102            .zip(params.iter())
103            .map(|(lhs, rhs)| (lhs.name_id(), rhs))
104            .collect::<HashMap<_, _>>();
105
106        match &decl.kind {
107            hir::TypeDeclKind::Enum(e) => {
108                let options = e
109                    .options
110                    .iter()
111                    .map(|(name, args)| {
112                        let args = args
113                            .0
114                            .iter()
115                            .map(|arg| {
116                                (
117                                    arg.name.inner.clone(),
118                                    Self::type_spec_to_concrete(
119                                        &arg.ty.inner,
120                                        type_list,
121                                        &generic_subs,
122                                        false,
123                                    ),
124                                )
125                            })
126                            .collect();
127                        (name.inner.clone(), args)
128                    })
129                    .collect();
130                ConcreteType::Enum { options }
131            }
132            hir::TypeDeclKind::Struct(s) => {
133                let members = s
134                    .members
135                    .0
136                    .iter()
137                    .map(
138                        |Parameter {
139                             name: ident,
140                             ty: t,
141                             no_mangle: _,
142                             field_translator: _,
143                         }| {
144                            (
145                                ident.inner.clone(),
146                                Self::type_spec_to_concrete(t, type_list, &generic_subs, invert),
147                            )
148                        },
149                    )
150                    .collect();
151
152                let translators = s.members.0.iter().filter_map(
153                    |Parameter {
154                         name,
155                         field_translator,
156                         ..
157                     }| {
158                        field_translator
159                            .as_ref()
160                            .map(|t| (name.inner.clone(), t.clone()))
161                    },
162                );
163
164                ConcreteType::Struct {
165                    name: decl.name.inner.clone(),
166                    is_port: s.is_port,
167                    members,
168                    field_translators: translators.collect(),
169                }
170            }
171            hir::TypeDeclKind::Primitive(PrimitiveType::Clock) => {
172                let concrete_type = ConcreteType::Single {
173                    base: PrimitiveType::Clock,
174                    params,
175                };
176
177                if invert {
178                    ConcreteType::Backward(Box::new(concrete_type))
179                } else {
180                    concrete_type
181                }
182            }
183            hir::TypeDeclKind::Primitive(primitive) => ConcreteType::Single {
184                base: primitive.clone(),
185                params,
186            },
187        }
188    }
189
190    pub fn type_expr_to_concrete(
191        expr: &TypeExpression,
192        type_list: &TypeList,
193        generic_substitutions: &HashMap<NameID, &ConcreteType>,
194        invert: bool,
195    ) -> ConcreteType {
196        match &expr {
197            hir::TypeExpression::Integer(val) => ConcreteType::Integer(val.clone()),
198            hir::TypeExpression::String(val) => ConcreteType::String(val.clone()),
199            hir::TypeExpression::TypeSpec(inner) => {
200                Self::type_spec_to_concrete(inner, type_list, generic_substitutions, invert)
201            }
202            hir::TypeExpression::ConstGeneric(_) => {
203                unreachable!("Const generic in type_expr_to_concrete")
204            }
205        }
206    }
207
208    pub fn type_spec_to_concrete(
209        spec: &TypeSpec,
210        type_list: &TypeList,
211        generic_substitutions: &HashMap<NameID, &ConcreteType>,
212        invert: bool,
213    ) -> ConcreteType {
214        match spec {
215            TypeSpec::Declared(name, params) => {
216                let params = params
217                    .iter()
218                    .map(|p| {
219                        Self::type_expr_to_concrete(p, type_list, generic_substitutions, invert)
220                    })
221                    .collect();
222
223                let actual = type_list
224                    .get(name)
225                    .unwrap_or_else(|| panic!("Expected {:?} to be in type list", name));
226
227                Self::type_decl_to_concrete(actual, type_list, params, invert)
228            }
229            TypeSpec::Generic(name) => {
230                // Substitute the generic for the current substitution
231                (*generic_substitutions
232                    .get(name)
233                    .unwrap_or_else(|| panic!("Expected a substitution for {}", name)))
234                .clone()
235            }
236            TypeSpec::Tuple(t) => {
237                let inner = t
238                    .iter()
239                    .map(|v| {
240                        Self::type_spec_to_concrete(
241                            &v.inner,
242                            type_list,
243                            generic_substitutions,
244                            invert,
245                        )
246                    })
247                    .collect::<Vec<_>>();
248                ConcreteType::Tuple(inner)
249            }
250            TypeSpec::Array { inner, size } => {
251                let size_type = Box::new(Self::type_expr_to_concrete(
252                    size,
253                    type_list,
254                    generic_substitutions,
255                    invert,
256                ));
257
258                let size = if let ConcreteType::Integer(size) = size_type.as_ref() {
259                    size.clone()
260                } else {
261                    panic!("Array size must be an integer")
262                };
263
264                ConcreteType::Array {
265                    inner: Box::new(Self::type_spec_to_concrete(
266                        inner,
267                        type_list,
268                        generic_substitutions,
269                        invert,
270                    )),
271                    size,
272                }
273            }
274            TypeSpec::Wire(inner) => {
275                let inner = Box::new(Self::type_spec_to_concrete(
276                    inner,
277                    type_list,
278                    generic_substitutions,
279                    invert,
280                ));
281                if invert {
282                    ConcreteType::Backward(inner)
283                } else {
284                    ConcreteType::Wire(inner)
285                }
286            }
287            TypeSpec::Inverted(inner) => Self::type_spec_to_concrete(
288                inner,
289                type_list,
290                generic_substitutions,
291                // Recursive inversions uninvert, so if we're already inverted while
292                // reaching another inversion, go back to the normal direction
293                !invert,
294            ),
295            TypeSpec::TraitSelf(_) => panic!("Trying to concretize HIR TraitSelf type"),
296            TypeSpec::Wildcard(_) => panic!("Trying to concretize HIR Wildcard type"),
297        }
298    }
299
300    pub fn inner_ungenerify_type(
301        &self,
302        var: &TypeVarID,
303        symtab: &SymbolTable,
304        type_list: &TypeList,
305        invert: bool,
306    ) -> Option<ConcreteType> {
307        match var.resolve(self) {
308            TypeVar::Known(_, KnownType::Error, _) => Some(ConcreteType::Error),
309            TypeVar::Known(_, KnownType::Named(t), params) => {
310                let params = params
311                    .iter()
312                    .map(|v| self.inner_ungenerify_type(v, symtab, type_list, invert))
313                    .collect::<Option<Vec<_>>>()?;
314
315                type_list
316                    .get(t)
317                    .map(|t| Self::type_decl_to_concrete(&t.inner, type_list, params, invert))
318            }
319            TypeVar::Known(_, KnownType::Integer(val), params) => {
320                assert!(params.is_empty(), "integers cannot have type parameters");
321
322                Some(ConcreteType::Integer(val.clone()))
323            }
324            TypeVar::Known(_, KnownType::Bool(val), params) => {
325                assert!(
326                    params.is_empty(),
327                    "type level bools cannot have type parameters"
328                );
329
330                Some(ConcreteType::Bool(*val))
331            }
332            TypeVar::Known(_, KnownType::String(val), params) => {
333                assert!(
334                    params.is_empty(),
335                    "type level strings cannot have type parameters"
336                );
337
338                Some(ConcreteType::String(val.clone()))
339            }
340            TypeVar::Known(_, KnownType::Array, inner) => {
341                let value = self.inner_ungenerify_type(&inner[0], symtab, type_list, invert);
342                let size = self.ungenerify_type(&inner[1], symtab, type_list).map(|t| {
343                    if let ConcreteType::Integer(size) = t {
344                        size
345                    } else {
346                        panic!("Array size must be an integer")
347                    }
348                });
349
350                match (value, size) {
351                    (Some(value), Some(size)) => Some(ConcreteType::Array {
352                        inner: Box::new(value),
353                        size,
354                    }),
355                    _ => None,
356                }
357            }
358            TypeVar::Known(_, KnownType::Tuple, inner) => {
359                let inner = inner
360                    .iter()
361                    .map(|v| self.inner_ungenerify_type(v, symtab, type_list, invert))
362                    .collect::<Option<Vec<_>>>()?;
363                Some(ConcreteType::Tuple(inner))
364            }
365            TypeVar::Known(_, KnownType::Wire, inner) => {
366                if invert {
367                    self.inner_ungenerify_type(&inner[0], symtab, type_list, invert)
368                        .map(|t| ConcreteType::Backward(Box::new(t)))
369                } else {
370                    self.inner_ungenerify_type(&inner[0], symtab, type_list, invert)
371                        .map(|t| ConcreteType::Wire(Box::new(t)))
372                }
373            }
374            TypeVar::Known(_, KnownType::Inverted, inner) => {
375                self.inner_ungenerify_type(&inner[0], symtab, type_list, !invert)
376            }
377            TypeVar::Unknown(_, _, _, _) => None,
378        }
379    }
380
381    /// Converts the specified type to a concrete type, returning None
382    /// if it fails
383    pub fn ungenerify_type(
384        &self,
385        var: &TypeVarID,
386        symtab: &SymbolTable,
387        type_list: &TypeList,
388    ) -> Option<ConcreteType> {
389        self.inner_ungenerify_type(var, symtab, type_list, false)
390    }
391
392    /// Returns the type of the specified expression ID as a concrete type. If the type is not
393    /// known, or the type is Generic, panics
394    pub fn concrete_type_of_infallible(
395        &self,
396        id: ExprID,
397        symtab: &SymbolTable,
398        type_list: &TypeList,
399    ) -> ConcreteType {
400        self.concrete_type_of(id.nowhere(), symtab, type_list)
401            .expect("Expr had generic type")
402    }
403
404    /// Returns the concrete type of anything that might have a concrete type. Errors
405    /// if the type is not fully known.
406    pub fn concrete_type_of(
407        &self,
408        id: impl HasConcreteType,
409        symtab: &SymbolTable,
410        types: &TypeList,
411    ) -> Result<ConcreteType, Diagnostic> {
412        let id = id.into_typed_expression();
413        let t = self.type_of(&id.inner);
414
415        if let Some(t) = self.ungenerify_type(&t, symtab, types) {
416            Ok(t)
417        } else {
418            if std::env::var("SPADE_TRACE_TYPEINFERENCE").is_ok() {
419                println!("The incomplete type is {}", t.debug_resolve(self))
420            }
421            Err(
422                Diagnostic::error(id, "Type of expression is not fully known")
423                    .primary_label("The type of this expression is not fully known")
424                    .note(format!("Found incomplete type: {t}", t = t.display(self))),
425            )
426        }
427    }
428
429    /// Like `concrete_type_of` but reports an error message that mentions names
430    /// instead of an expression
431    pub fn concrete_type_of_name(
432        &self,
433        name: &Loc<NameID>,
434        symtab: &SymbolTable,
435        types: &TypeList,
436    ) -> Result<ConcreteType, Diagnostic> {
437        let t = self.type_of(&TypedExpression::Name(name.inner.clone()));
438
439        if let Some(t) = self.ungenerify_type(&t, symtab, types) {
440            Ok(t)
441        } else {
442            Err(
443                Diagnostic::error(name, format!("Type of {name} is not fully known"))
444                    .primary_label(format!("The type of {name} is not fully known"))
445                    .note(format!("Found incomplete type: {t}", t = t.display(self))),
446            )
447        }
448    }
449}
spade_typeinference/mir_type_lowering.rs

spade_typeinference/
mir_type_lowering.rs
