src/tools/rust-analyzer/crates/hir-ty/src/builder.rs

   1 //! `TyBuilder`, a helper for building instances of `Ty` and related types.
   2
   3 use std::iter;
   4
   5 use chalk_ir::{
   6     cast::{Cast, CastTo, Caster},
   7     fold::TypeFoldable,
   8     interner::HasInterner,
   9     AdtId, DebruijnIndex, Scalar,
  10 };
  11 use hir_def::{
  12     builtin_type::BuiltinType, generics::TypeOrConstParamData, ConstParamId, DefWithBodyId,
  13     GenericDefId, TraitId, TypeAliasId,
  14 };
  15 use smallvec::SmallVec;
  16
  17 use crate::{
  18     consteval::unknown_const_as_generic, db::HirDatabase, infer::unify::InferenceTable, primitive,
  19     to_assoc_type_id, to_chalk_trait_id, utils::generics, Binders, BoundVar, CallableSig,
  20     GenericArg, Interner, ProjectionTy, Substitution, TraitRef, Ty, TyDefId, TyExt, TyKind,
  21     ValueTyDefId,
  22 };
  23
  24 #[derive(Debug, Clone, PartialEq, Eq)]
  25 pub enum ParamKind {
  26     Type,
  27     Const(Ty),
  28 }
  29
  30 /// This is a builder for `Ty` or anything that needs a `Substitution`.
  31 pub struct TyBuilder<D> {
  32     /// The `data` field is used to keep track of what we're building (e.g. an
  33     /// ADT, a `TraitRef`, ...).
  34     data: D,
  35     vec: SmallVec<[GenericArg; 2]>,
  36     param_kinds: SmallVec<[ParamKind; 2]>,
  37     parent_subst: Substitution,
  38 }
  39
  40 impl<A> TyBuilder<A> {
  41     fn with_data<B>(self, data: B) -> TyBuilder<B> {
  42         TyBuilder {
  43             data,
  44             vec: self.vec,
  45             param_kinds: self.param_kinds,
  46             parent_subst: self.parent_subst,
  47         }
  48     }
  49 }
  50
  51 impl<D> TyBuilder<D> {
  52     fn new(
  53         data: D,
  54         param_kinds: SmallVec<[ParamKind; 2]>,
  55         parent_subst: Option<Substitution>,
  56     ) -> Self {
  57         let parent_subst = parent_subst.unwrap_or_else(|| Substitution::empty(Interner));
  58         Self { data, vec: SmallVec::with_capacity(param_kinds.len()), param_kinds, parent_subst }
  59     }
  60
  61     fn new_empty(data: D) -> Self {
  62         TyBuilder::new(data, SmallVec::new(), None)
  63     }
  64
  65     fn build_internal(self) -> (D, Substitution) {
  66         assert_eq!(self.vec.len(), self.param_kinds.len());
  67         for (a, e) in self.vec.iter().zip(self.param_kinds.iter()) {
  68             self.assert_match_kind(a, e);
  69         }
  70         let subst = Substitution::from_iter(
  71             Interner,
  72             self.vec.into_iter().chain(self.parent_subst.iter(Interner).cloned()),
  73         );
  74         (self.data, subst)
  75     }
  76
  77     pub fn push(mut self, arg: impl CastTo<GenericArg>) -> Self {
  78         assert!(self.remaining() > 0);
  79         let arg = arg.cast(Interner);
  80         let expected_kind = &self.param_kinds[self.vec.len()];
  81
  82         let arg_kind = match arg.data(Interner) {
  83             chalk_ir::GenericArgData::Ty(_) => ParamKind::Type,
  84             chalk_ir::GenericArgData::Lifetime(_) => panic!("Got lifetime in TyBuilder::push"),
  85             chalk_ir::GenericArgData::Const(c) => {
  86                 let c = c.data(Interner);
  87                 ParamKind::Const(c.ty.clone())
  88             }
  89         };
  90         assert_eq!(*expected_kind, arg_kind);
  91
  92         self.vec.push(arg);
  93
  94         self
  95     }
  96
  97     pub fn remaining(&self) -> usize {
  98         self.param_kinds.len() - self.vec.len()
  99     }
 100
 101     pub fn fill_with_bound_vars(self, debruijn: DebruijnIndex, starting_from: usize) -> Self {
 102         // self.fill is inlined to make borrow checker happy
 103         let mut this = self;
 104         let other = &this.param_kinds[this.vec.len()..];
 105         let filler = (starting_from..).zip(other).map(|(idx, kind)| match kind {
 106             ParamKind::Type => BoundVar::new(debruijn, idx).to_ty(Interner).cast(Interner),
 107             ParamKind::Const(ty) => {
 108                 BoundVar::new(debruijn, idx).to_const(Interner, ty.clone()).cast(Interner)
 109             }
 110         });
 111         this.vec.extend(filler.take(this.remaining()).casted(Interner));
 112         assert_eq!(this.remaining(), 0);
 113         this
 114     }
 115
 116     pub fn fill_with_unknown(self) -> Self {
 117         // self.fill is inlined to make borrow checker happy
 118         let mut this = self;
 119         let filler = this.param_kinds[this.vec.len()..].iter().map(|x| match x {
 120             ParamKind::Type => TyKind::Error.intern(Interner).cast(Interner),
 121             ParamKind::Const(ty) => unknown_const_as_generic(ty.clone()),
 122         });
 123         this.vec.extend(filler.casted(Interner));
 124         assert_eq!(this.remaining(), 0);
 125         this
 126     }
 127
 128     pub(crate) fn fill_with_inference_vars(self, table: &mut InferenceTable<'_>) -> Self {
 129         self.fill(|x| match x {
 130             ParamKind::Type => table.new_type_var().cast(Interner),
 131             ParamKind::Const(ty) => table.new_const_var(ty.clone()).cast(Interner),
 132         })
 133     }
 134
 135     pub fn fill(mut self, filler: impl FnMut(&ParamKind) -> GenericArg) -> Self {
 136         self.vec.extend(self.param_kinds[self.vec.len()..].iter().map(filler));
 137         assert_eq!(self.remaining(), 0);
 138         self
 139     }
 140
 141     fn assert_match_kind(&self, a: &chalk_ir::GenericArg<Interner>, e: &ParamKind) {
 142         match (a.data(Interner), e) {
 143             (chalk_ir::GenericArgData::Ty(_), ParamKind::Type)
 144             | (chalk_ir::GenericArgData::Const(_), ParamKind::Const(_)) => (),
 145             _ => panic!("Mismatched kinds: {a:?}, {:?}, {:?}", self.vec, self.param_kinds),
 146         }
 147     }
 148 }
 149
 150 impl TyBuilder<()> {
 151     pub fn unit() -> Ty {
 152         TyKind::Tuple(0, Substitution::empty(Interner)).intern(Interner)
 153     }
 154
 155     pub fn usize() -> Ty {
 156         TyKind::Scalar(chalk_ir::Scalar::Uint(chalk_ir::UintTy::Usize)).intern(Interner)
 157     }
 158
 159     pub fn fn_ptr(sig: CallableSig) -> Ty {
 160         TyKind::Function(sig.to_fn_ptr()).intern(Interner)
 161     }
 162
 163     pub fn builtin(builtin: BuiltinType) -> Ty {
 164         match builtin {
 165             BuiltinType::Char => TyKind::Scalar(Scalar::Char).intern(Interner),
 166             BuiltinType::Bool => TyKind::Scalar(Scalar::Bool).intern(Interner),
 167             BuiltinType::Str => TyKind::Str.intern(Interner),
 168             BuiltinType::Int(t) => {
 169                 TyKind::Scalar(Scalar::Int(primitive::int_ty_from_builtin(t))).intern(Interner)
 170             }
 171             BuiltinType::Uint(t) => {
 172                 TyKind::Scalar(Scalar::Uint(primitive::uint_ty_from_builtin(t))).intern(Interner)
 173             }
 174             BuiltinType::Float(t) => {
 175                 TyKind::Scalar(Scalar::Float(primitive::float_ty_from_builtin(t))).intern(Interner)
 176             }
 177         }
 178     }
 179
 180     pub fn slice(argument: Ty) -> Ty {
 181         TyKind::Slice(argument).intern(Interner)
 182     }
 183
 184     pub fn placeholder_subst(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> Substitution {
 185         let params = generics(db.upcast(), def.into());
 186         params.placeholder_subst(db)
 187     }
 188
 189     pub fn subst_for_def(
 190         db: &dyn HirDatabase,
 191         def: impl Into<GenericDefId>,
 192         parent_subst: Option<Substitution>,
 193     ) -> TyBuilder<()> {
 194         let generics = generics(db.upcast(), def.into());
 195         assert!(generics.parent_generics().is_some() == parent_subst.is_some());
 196         let params = generics
 197             .iter_self()
 198             .map(|(id, data)| match data {
 199                 TypeOrConstParamData::TypeParamData(_) => ParamKind::Type,
 200                 TypeOrConstParamData::ConstParamData(_) => {
 201                     ParamKind::Const(db.const_param_ty(ConstParamId::from_unchecked(id)))
 202                 }
 203             })
 204             .collect();
 205         TyBuilder::new((), params, parent_subst)
 206     }
 207
 208     /// Creates a `TyBuilder` to build `Substitution` for a generator defined in `parent`.
 209     ///
 210     /// A generator's substitution consists of:
 211     /// - resume type of generator
 212     /// - yield type of generator ([`Generator::Yield`](std::ops::Generator::Yield))
 213     /// - return type of generator ([`Generator::Return`](std::ops::Generator::Return))
 214     /// - generic parameters in scope on `parent`
 215     /// in this order.
 216     ///
 217     /// This method prepopulates the builder with placeholder substitution of `parent`, so you
 218     /// should only push exactly 3 `GenericArg`s before building.
 219     pub fn subst_for_generator(db: &dyn HirDatabase, parent: DefWithBodyId) -> TyBuilder<()> {
 220         let parent_subst =
 221             parent.as_generic_def_id().map(|p| generics(db.upcast(), p).placeholder_subst(db));
 222         // These represent resume type, yield type, and return type of generator.
 223         let params = std::iter::repeat(ParamKind::Type).take(3).collect();
 224         TyBuilder::new((), params, parent_subst)
 225     }
 226
 227     pub fn build(self) -> Substitution {
 228         let ((), subst) = self.build_internal();
 229         subst
 230     }
 231 }
 232
 233 impl TyBuilder<hir_def::AdtId> {
 234     pub fn adt(db: &dyn HirDatabase, def: hir_def::AdtId) -> TyBuilder<hir_def::AdtId> {
 235         TyBuilder::subst_for_def(db, def, None).with_data(def)
 236     }
 237
 238     pub fn fill_with_defaults(
 239         mut self,
 240         db: &dyn HirDatabase,
 241         mut fallback: impl FnMut() -> Ty,
 242     ) -> Self {
 243         // Note that we're building ADT, so we never have parent generic parameters.
 244         let defaults = db.generic_defaults(self.data.into());
 245         let dummy_ty = TyKind::Error.intern(Interner).cast(Interner);
 246         for default_ty in defaults.iter().skip(self.vec.len()) {
 247             // NOTE(skip_binders): we only check if the arg type is error type.
 248             if let Some(x) = default_ty.skip_binders().ty(Interner) {
 249                 if x.is_unknown() {
 250                     self.vec.push(fallback().cast(Interner));
 251                     continue;
 252                 }
 253             }
 254             // Each default can only depend on the previous parameters.
 255             // FIXME: we don't handle const generics here.
 256             let subst_so_far = Substitution::from_iter(
 257                 Interner,
 258                 self.vec
 259                     .iter()
 260                     .cloned()
 261                     .chain(iter::repeat(dummy_ty.clone()))
 262                     .take(self.param_kinds.len()),
 263             );
 264             self.vec.push(default_ty.clone().substitute(Interner, &subst_so_far).cast(Interner));
 265         }
 266         self
 267     }
 268
 269     pub fn build(self) -> Ty {
 270         let (adt, subst) = self.build_internal();
 271         TyKind::Adt(AdtId(adt), subst).intern(Interner)
 272     }
 273 }
 274
 275 pub struct Tuple(usize);
 276 impl TyBuilder<Tuple> {
 277     pub fn tuple(size: usize) -> TyBuilder<Tuple> {
 278         TyBuilder::new(Tuple(size), iter::repeat(ParamKind::Type).take(size).collect(), None)
 279     }
 280
 281     pub fn build(self) -> Ty {
 282         let (Tuple(size), subst) = self.build_internal();
 283         TyKind::Tuple(size, subst).intern(Interner)
 284     }
 285 }
 286
 287 impl TyBuilder<TraitId> {
 288     pub fn trait_ref(db: &dyn HirDatabase, def: TraitId) -> TyBuilder<TraitId> {
 289         TyBuilder::subst_for_def(db, def, None).with_data(def)
 290     }
 291
 292     pub fn build(self) -> TraitRef {
 293         let (trait_id, substitution) = self.build_internal();
 294         TraitRef { trait_id: to_chalk_trait_id(trait_id), substitution }
 295     }
 296 }
 297
 298 impl TyBuilder<TypeAliasId> {
 299     pub fn assoc_type_projection(
 300         db: &dyn HirDatabase,
 301         def: TypeAliasId,
 302         parent_subst: Option<Substitution>,
 303     ) -> TyBuilder<TypeAliasId> {
 304         TyBuilder::subst_for_def(db, def, parent_subst).with_data(def)
 305     }
 306
 307     pub fn build(self) -> ProjectionTy {
 308         let (type_alias, substitution) = self.build_internal();
 309         ProjectionTy { associated_ty_id: to_assoc_type_id(type_alias), substitution }
 310     }
 311 }
 312
 313 impl<T: HasInterner<Interner = Interner> + TypeFoldable<Interner>> TyBuilder<Binders<T>> {
 314     pub fn build(self) -> T {
 315         let (b, subst) = self.build_internal();
 316         b.substitute(Interner, &subst)
 317     }
 318 }
 319
 320 impl TyBuilder<Binders<Ty>> {
 321     pub fn def_ty(
 322         db: &dyn HirDatabase,
 323         def: TyDefId,
 324         parent_subst: Option<Substitution>,
 325     ) -> TyBuilder<Binders<Ty>> {
 326         let poly_ty = db.ty(def);
 327         let id: GenericDefId = match def {
 328             TyDefId::BuiltinType(_) => {
 329                 assert!(parent_subst.is_none());
 330                 return TyBuilder::new_empty(poly_ty);
 331             }
 332             TyDefId::AdtId(id) => id.into(),
 333             TyDefId::TypeAliasId(id) => id.into(),
 334         };
 335         TyBuilder::subst_for_def(db, id, parent_subst).with_data(poly_ty)
 336     }
 337
 338     pub fn impl_self_ty(db: &dyn HirDatabase, def: hir_def::ImplId) -> TyBuilder<Binders<Ty>> {
 339         TyBuilder::subst_for_def(db, def, None).with_data(db.impl_self_ty(def))
 340     }
 341
 342     pub fn value_ty(
 343         db: &dyn HirDatabase,
 344         def: ValueTyDefId,
 345         parent_subst: Option<Substitution>,
 346     ) -> TyBuilder<Binders<Ty>> {
 347         let poly_value_ty = db.value_ty(def);
 348         let id = match def.to_generic_def_id() {
 349             Some(id) => id,
 350             None => {
 351                 // static items
 352                 assert!(parent_subst.is_none());
 353                 return TyBuilder::new_empty(poly_value_ty);
 354             }
 355         };
 356         TyBuilder::subst_for_def(db, id, parent_subst).with_data(poly_value_ty)
 357     }
 358 }