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

spade_typeinference/
mir_type_lowering.rs
