hir_ty/mir/
monomorphization.rs

1//! Monomorphization of mir, which is used in mir interpreter and const eval.
2//!
3//! The job of monomorphization is:
4//! * Monomorphization. That is, replacing `Option<T>` with `Option<i32>` where `T:=i32` substitution
5//!   is provided
6//! * Normalizing types, for example replacing RPIT of other functions called in this body.
7//!
8//! So the monomorphization should be called even if the substitution is empty.
9
10use std::mem;
11
12use chalk_ir::{
13    ConstData, DebruijnIndex,
14    fold::{FallibleTypeFolder, TypeFoldable, TypeSuperFoldable},
15};
16use hir_def::DefWithBodyId;
17use triomphe::Arc;
18
19use crate::{
20    Const, Interner, ProjectionTy, Substitution, TraitEnvironment, Ty, TyKind,
21    consteval::{intern_const_scalar, unknown_const},
22    db::{HirDatabase, InternedClosure, InternedClosureId},
23    from_placeholder_idx,
24    generics::{Generics, generics},
25    infer::normalize,
26};
27
28use super::{MirBody, MirLowerError, Operand, OperandKind, Rvalue, StatementKind, TerminatorKind};
29
30macro_rules! not_supported {
31    ($it: expr) => {
32        return Err(MirLowerError::NotSupported(format!($it)))
33    };
34}
35
36struct Filler<'a> {
37    db: &'a dyn HirDatabase,
38    trait_env: Arc<TraitEnvironment>,
39    subst: &'a Substitution,
40    generics: Option<Generics>,
41    owner: DefWithBodyId,
42}
43impl FallibleTypeFolder<Interner> for Filler<'_> {
44    type Error = MirLowerError;
45
46    fn as_dyn(&mut self) -> &mut dyn FallibleTypeFolder<Interner, Error = Self::Error> {
47        self
48    }
49
50    fn interner(&self) -> Interner {
51        Interner
52    }
53
54    fn try_fold_ty(
55        &mut self,
56        ty: Ty,
57        outer_binder: DebruijnIndex,
58    ) -> std::result::Result<Ty, Self::Error> {
59        match ty.kind(Interner) {
60            TyKind::AssociatedType(id, subst) => {
61                // I don't know exactly if and why this is needed, but it looks like `normalize_ty` likes
62                // this kind of associated types.
63                Ok(TyKind::Alias(chalk_ir::AliasTy::Projection(ProjectionTy {
64                    associated_ty_id: *id,
65                    substitution: subst.clone().try_fold_with(self, outer_binder)?,
66                }))
67                .intern(Interner))
68            }
69            TyKind::OpaqueType(id, subst) => {
70                let impl_trait_id = self.db.lookup_intern_impl_trait_id((*id).into());
71                let subst = subst.clone().try_fold_with(self.as_dyn(), outer_binder)?;
72                match impl_trait_id {
73                    crate::ImplTraitId::ReturnTypeImplTrait(func, idx) => {
74                        let infer = self.db.infer(func.into());
75                        let filler = &mut Filler {
76                            db: self.db,
77                            owner: self.owner,
78                            trait_env: self.trait_env.clone(),
79                            subst: &subst,
80                            generics: Some(generics(self.db, func.into())),
81                        };
82                        filler.try_fold_ty(infer.type_of_rpit[idx].clone(), outer_binder)
83                    }
84                    crate::ImplTraitId::TypeAliasImplTrait(..) => {
85                        not_supported!("type alias impl trait");
86                    }
87                    crate::ImplTraitId::AsyncBlockTypeImplTrait(_, _) => {
88                        not_supported!("async block impl trait");
89                    }
90                }
91            }
92            _ => ty.try_super_fold_with(self.as_dyn(), outer_binder),
93        }
94    }
95
96    fn try_fold_free_placeholder_const(
97        &mut self,
98        _ty: chalk_ir::Ty<Interner>,
99        idx: chalk_ir::PlaceholderIndex,
100        _outer_binder: DebruijnIndex,
101    ) -> std::result::Result<chalk_ir::Const<Interner>, Self::Error> {
102        let it = from_placeholder_idx(self.db, idx).0;
103        let Some(idx) = self.generics.as_ref().and_then(|g| g.type_or_const_param_idx(it)) else {
104            not_supported!("missing idx in generics");
105        };
106        Ok(self
107            .subst
108            .as_slice(Interner)
109            .get(idx)
110            .and_then(|it| it.constant(Interner))
111            .ok_or_else(|| MirLowerError::GenericArgNotProvided(it, self.subst.clone()))?
112            .clone())
113    }
114
115    fn try_fold_free_placeholder_ty(
116        &mut self,
117        idx: chalk_ir::PlaceholderIndex,
118        _outer_binder: DebruijnIndex,
119    ) -> std::result::Result<Ty, Self::Error> {
120        let it = from_placeholder_idx(self.db, idx).0;
121        let Some(idx) = self.generics.as_ref().and_then(|g| g.type_or_const_param_idx(it)) else {
122            not_supported!("missing idx in generics");
123        };
124        Ok(self
125            .subst
126            .as_slice(Interner)
127            .get(idx)
128            .and_then(|it| it.ty(Interner))
129            .ok_or_else(|| MirLowerError::GenericArgNotProvided(it, self.subst.clone()))?
130            .clone())
131    }
132
133    fn try_fold_const(
134        &mut self,
135        constant: chalk_ir::Const<Interner>,
136        outer_binder: DebruijnIndex,
137    ) -> Result<chalk_ir::Const<Interner>, Self::Error> {
138        let next_ty = normalize(
139            self.db,
140            self.trait_env.clone(),
141            constant.data(Interner).ty.clone().try_fold_with(self, outer_binder)?,
142        );
143        ConstData { ty: next_ty, value: constant.data(Interner).value.clone() }
144            .intern(Interner)
145            .try_super_fold_with(self, outer_binder)
146    }
147}
148
149impl Filler<'_> {
150    fn fill_ty(&mut self, ty: &mut Ty) -> Result<(), MirLowerError> {
151        let tmp = mem::replace(ty, TyKind::Error.intern(Interner));
152        *ty = normalize(
153            self.db,
154            self.trait_env.clone(),
155            tmp.try_fold_with(self, DebruijnIndex::INNERMOST)?,
156        );
157        Ok(())
158    }
159
160    fn fill_const(&mut self, c: &mut Const) -> Result<(), MirLowerError> {
161        let tmp = mem::replace(c, unknown_const(c.data(Interner).ty.clone()));
162        *c = tmp.try_fold_with(self, DebruijnIndex::INNERMOST)?;
163        Ok(())
164    }
165
166    fn fill_subst(&mut self, ty: &mut Substitution) -> Result<(), MirLowerError> {
167        let tmp = mem::replace(ty, Substitution::empty(Interner));
168        *ty = tmp.try_fold_with(self, DebruijnIndex::INNERMOST)?;
169        Ok(())
170    }
171
172    fn fill_operand(&mut self, op: &mut Operand) -> Result<(), MirLowerError> {
173        match &mut op.kind {
174            OperandKind::Constant(c) => {
175                match &c.data(Interner).value {
176                    chalk_ir::ConstValue::BoundVar(b) => {
177                        let resolved = self
178                            .subst
179                            .as_slice(Interner)
180                            .get(b.index)
181                            .ok_or_else(|| {
182                                MirLowerError::GenericArgNotProvided(
183                                    self.generics
184                                        .as_ref()
185                                        .and_then(|it| it.iter().nth(b.index))
186                                        .and_then(|(id, _)| match id {
187                                            hir_def::GenericParamId::ConstParamId(id) => {
188                                                Some(hir_def::TypeOrConstParamId::from(id))
189                                            }
190                                            hir_def::GenericParamId::TypeParamId(id) => {
191                                                Some(hir_def::TypeOrConstParamId::from(id))
192                                            }
193                                            _ => None,
194                                        })
195                                        .unwrap(),
196                                    self.subst.clone(),
197                                )
198                            })?
199                            .assert_const_ref(Interner);
200                        *c = resolved.clone();
201                    }
202                    chalk_ir::ConstValue::InferenceVar(_)
203                    | chalk_ir::ConstValue::Placeholder(_) => {}
204                    chalk_ir::ConstValue::Concrete(cc) => match &cc.interned {
205                        crate::ConstScalar::UnevaluatedConst(const_id, subst) => {
206                            let mut subst = subst.clone();
207                            self.fill_subst(&mut subst)?;
208                            *c = intern_const_scalar(
209                                crate::ConstScalar::UnevaluatedConst(*const_id, subst),
210                                c.data(Interner).ty.clone(),
211                            );
212                        }
213                        crate::ConstScalar::Bytes(_, _) | crate::ConstScalar::Unknown => (),
214                    },
215                }
216                self.fill_const(c)?;
217            }
218            OperandKind::Copy(_) | OperandKind::Move(_) | OperandKind::Static(_) => (),
219        }
220        Ok(())
221    }
222
223    fn fill_body(&mut self, body: &mut MirBody) -> Result<(), MirLowerError> {
224        for (_, l) in body.locals.iter_mut() {
225            self.fill_ty(&mut l.ty)?;
226        }
227        for (_, bb) in body.basic_blocks.iter_mut() {
228            for statement in &mut bb.statements {
229                match &mut statement.kind {
230                    StatementKind::Assign(_, r) => match r {
231                        Rvalue::Aggregate(ak, ops) => {
232                            for op in &mut **ops {
233                                self.fill_operand(op)?;
234                            }
235                            match ak {
236                                super::AggregateKind::Array(ty)
237                                | super::AggregateKind::Tuple(ty)
238                                | super::AggregateKind::Closure(ty) => self.fill_ty(ty)?,
239                                super::AggregateKind::Adt(_, subst) => self.fill_subst(subst)?,
240                                super::AggregateKind::Union(_, _) => (),
241                            }
242                        }
243                        Rvalue::ShallowInitBox(_, ty) | Rvalue::ShallowInitBoxWithAlloc(ty) => {
244                            self.fill_ty(ty)?;
245                        }
246                        Rvalue::Use(op) => {
247                            self.fill_operand(op)?;
248                        }
249                        Rvalue::Repeat(op, len) => {
250                            self.fill_operand(op)?;
251                            self.fill_const(len)?;
252                        }
253                        Rvalue::Ref(_, _)
254                        | Rvalue::Len(_)
255                        | Rvalue::Cast(_, _, _)
256                        | Rvalue::CheckedBinaryOp(_, _, _)
257                        | Rvalue::UnaryOp(_, _)
258                        | Rvalue::Discriminant(_)
259                        | Rvalue::CopyForDeref(_) => (),
260                        Rvalue::ThreadLocalRef(n)
261                        | Rvalue::AddressOf(n)
262                        | Rvalue::BinaryOp(n)
263                        | Rvalue::NullaryOp(n) => match *n {},
264                    },
265                    StatementKind::Deinit(_)
266                    | StatementKind::FakeRead(_)
267                    | StatementKind::StorageLive(_)
268                    | StatementKind::StorageDead(_)
269                    | StatementKind::Nop => (),
270                }
271            }
272            if let Some(terminator) = &mut bb.terminator {
273                match &mut terminator.kind {
274                    TerminatorKind::Call { func, args, .. } => {
275                        self.fill_operand(func)?;
276                        for op in &mut **args {
277                            self.fill_operand(op)?;
278                        }
279                    }
280                    TerminatorKind::SwitchInt { discr, .. } => {
281                        self.fill_operand(discr)?;
282                    }
283                    TerminatorKind::Goto { .. }
284                    | TerminatorKind::UnwindResume
285                    | TerminatorKind::Abort
286                    | TerminatorKind::Return
287                    | TerminatorKind::Unreachable
288                    | TerminatorKind::Drop { .. }
289                    | TerminatorKind::DropAndReplace { .. }
290                    | TerminatorKind::Assert { .. }
291                    | TerminatorKind::Yield { .. }
292                    | TerminatorKind::CoroutineDrop
293                    | TerminatorKind::FalseEdge { .. }
294                    | TerminatorKind::FalseUnwind { .. } => (),
295                }
296            }
297        }
298        Ok(())
299    }
300}
301
302pub fn monomorphized_mir_body_query(
303    db: &dyn HirDatabase,
304    owner: DefWithBodyId,
305    subst: Substitution,
306    trait_env: Arc<crate::TraitEnvironment>,
307) -> Result<Arc<MirBody>, MirLowerError> {
308    let generics = owner.as_generic_def_id(db).map(|g_def| generics(db, g_def));
309    let filler = &mut Filler { db, subst: &subst, trait_env, generics, owner };
310    let body = db.mir_body(owner)?;
311    let mut body = (*body).clone();
312    filler.fill_body(&mut body)?;
313    Ok(Arc::new(body))
314}
315
316pub(crate) fn monomorphized_mir_body_cycle_result(
317    _db: &dyn HirDatabase,
318    _: DefWithBodyId,
319    _: Substitution,
320    _: Arc<crate::TraitEnvironment>,
321) -> Result<Arc<MirBody>, MirLowerError> {
322    Err(MirLowerError::Loop)
323}
324
325pub fn monomorphized_mir_body_for_closure_query(
326    db: &dyn HirDatabase,
327    closure: InternedClosureId,
328    subst: Substitution,
329    trait_env: Arc<crate::TraitEnvironment>,
330) -> Result<Arc<MirBody>, MirLowerError> {
331    let InternedClosure(owner, _) = db.lookup_intern_closure(closure);
332    let generics = owner.as_generic_def_id(db).map(|g_def| generics(db, g_def));
333    let filler = &mut Filler { db, subst: &subst, trait_env, generics, owner };
334    let body = db.mir_body_for_closure(closure)?;
335    let mut body = (*body).clone();
336    filler.fill_body(&mut body)?;
337    Ok(Arc::new(body))
338}
339
340// FIXME: remove this function. Monomorphization is a time consuming job and should always be a query.
341pub fn monomorphize_mir_body_bad(
342    db: &dyn HirDatabase,
343    mut body: MirBody,
344    subst: Substitution,
345    trait_env: Arc<crate::TraitEnvironment>,
346) -> Result<MirBody, MirLowerError> {
347    let owner = body.owner;
348    let generics = owner.as_generic_def_id(db).map(|g_def| generics(db, g_def));
349    let filler = &mut Filler { db, subst: &subst, trait_env, generics, owner };
350    filler.fill_body(&mut body)?;
351    Ok(body)
352}
hir_ty/mir/monomorphization.rs

hir_ty/mir/
monomorphization.rs
