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 }; 22 23 #[derive(Debug, Clone, PartialEq, Eq)] 24 pub enum ParamKind { 25 Type, 26 Const(Ty), 27 } 28 29 /// This is a builder for `Ty` or anything that needs a `Substitution`. 30 pub struct TyBuilder<D> { 31 /// The `data` field is used to keep track of what we're building (e.g. an 32 /// ADT, a `TraitRef`, ...). 33 data: D, 34 vec: SmallVec<[GenericArg; 2]>, 35 param_kinds: SmallVec<[ParamKind; 2]>, 36 parent_subst: Substitution, 37 } 38 39 impl<A> TyBuilder<A> { with_data<B>(self, data: B) -> TyBuilder<B>40 fn with_data<B>(self, data: B) -> TyBuilder<B> { 41 TyBuilder { 42 data, 43 vec: self.vec, 44 param_kinds: self.param_kinds, 45 parent_subst: self.parent_subst, 46 } 47 } 48 } 49 50 impl<D> TyBuilder<D> { new( data: D, param_kinds: SmallVec<[ParamKind; 2]>, parent_subst: Option<Substitution>, ) -> Self51 fn new( 52 data: D, 53 param_kinds: SmallVec<[ParamKind; 2]>, 54 parent_subst: Option<Substitution>, 55 ) -> Self { 56 let parent_subst = parent_subst.unwrap_or_else(|| Substitution::empty(Interner)); 57 Self { data, vec: SmallVec::with_capacity(param_kinds.len()), param_kinds, parent_subst } 58 } 59 new_empty(data: D) -> Self60 fn new_empty(data: D) -> Self { 61 TyBuilder::new(data, SmallVec::new(), None) 62 } 63 build_internal(self) -> (D, Substitution)64 fn build_internal(self) -> (D, Substitution) { 65 assert_eq!(self.vec.len(), self.param_kinds.len(), "{:?}", &self.param_kinds); 66 for (a, e) in self.vec.iter().zip(self.param_kinds.iter()) { 67 self.assert_match_kind(a, e); 68 } 69 let subst = Substitution::from_iter( 70 Interner, 71 self.vec.into_iter().chain(self.parent_subst.iter(Interner).cloned()), 72 ); 73 (self.data, subst) 74 } 75 push(mut self, arg: impl CastTo<GenericArg>) -> Self76 pub fn push(mut self, arg: impl CastTo<GenericArg>) -> Self { 77 assert!(self.remaining() > 0); 78 let arg = arg.cast(Interner); 79 let expected_kind = &self.param_kinds[self.vec.len()]; 80 81 let arg_kind = match arg.data(Interner) { 82 chalk_ir::GenericArgData::Ty(_) => ParamKind::Type, 83 chalk_ir::GenericArgData::Lifetime(_) => panic!("Got lifetime in TyBuilder::push"), 84 chalk_ir::GenericArgData::Const(c) => { 85 let c = c.data(Interner); 86 ParamKind::Const(c.ty.clone()) 87 } 88 }; 89 assert_eq!(*expected_kind, arg_kind); 90 91 self.vec.push(arg); 92 93 self 94 } 95 remaining(&self) -> usize96 pub fn remaining(&self) -> usize { 97 self.param_kinds.len() - self.vec.len() 98 } 99 fill_with_bound_vars(self, debruijn: DebruijnIndex, starting_from: usize) -> Self100 pub fn fill_with_bound_vars(self, debruijn: DebruijnIndex, starting_from: usize) -> Self { 101 // self.fill is inlined to make borrow checker happy 102 let mut this = self; 103 let other = &this.param_kinds[this.vec.len()..]; 104 let filler = (starting_from..).zip(other).map(|(idx, kind)| match kind { 105 ParamKind::Type => BoundVar::new(debruijn, idx).to_ty(Interner).cast(Interner), 106 ParamKind::Const(ty) => { 107 BoundVar::new(debruijn, idx).to_const(Interner, ty.clone()).cast(Interner) 108 } 109 }); 110 this.vec.extend(filler.take(this.remaining()).casted(Interner)); 111 assert_eq!(this.remaining(), 0); 112 this 113 } 114 fill_with_unknown(self) -> Self115 pub fn fill_with_unknown(self) -> Self { 116 // self.fill is inlined to make borrow checker happy 117 let mut this = self; 118 let filler = this.param_kinds[this.vec.len()..].iter().map(|x| match x { 119 ParamKind::Type => TyKind::Error.intern(Interner).cast(Interner), 120 ParamKind::Const(ty) => unknown_const_as_generic(ty.clone()), 121 }); 122 this.vec.extend(filler.casted(Interner)); 123 assert_eq!(this.remaining(), 0); 124 this 125 } 126 fill_with_inference_vars(self, table: &mut InferenceTable<'_>) -> Self127 pub(crate) fn fill_with_inference_vars(self, table: &mut InferenceTable<'_>) -> Self { 128 self.fill(|x| match x { 129 ParamKind::Type => table.new_type_var().cast(Interner), 130 ParamKind::Const(ty) => table.new_const_var(ty.clone()).cast(Interner), 131 }) 132 } 133 fill(mut self, filler: impl FnMut(&ParamKind) -> GenericArg) -> Self134 pub fn fill(mut self, filler: impl FnMut(&ParamKind) -> GenericArg) -> Self { 135 self.vec.extend(self.param_kinds[self.vec.len()..].iter().map(filler)); 136 assert_eq!(self.remaining(), 0); 137 self 138 } 139 assert_match_kind(&self, a: &chalk_ir::GenericArg<Interner>, e: &ParamKind)140 fn assert_match_kind(&self, a: &chalk_ir::GenericArg<Interner>, e: &ParamKind) { 141 match (a.data(Interner), e) { 142 (chalk_ir::GenericArgData::Ty(_), ParamKind::Type) 143 | (chalk_ir::GenericArgData::Const(_), ParamKind::Const(_)) => (), 144 _ => panic!("Mismatched kinds: {a:?}, {:?}, {:?}", self.vec, self.param_kinds), 145 } 146 } 147 } 148 149 impl TyBuilder<()> { unit() -> Ty150 pub fn unit() -> Ty { 151 TyKind::Tuple(0, Substitution::empty(Interner)).intern(Interner) 152 } 153 154 // FIXME: rustc's ty is dependent on the adt type, maybe we need to do that as well discr_ty() -> Ty155 pub fn discr_ty() -> Ty { 156 TyKind::Scalar(chalk_ir::Scalar::Int(chalk_ir::IntTy::I128)).intern(Interner) 157 } 158 bool() -> Ty159 pub fn bool() -> Ty { 160 TyKind::Scalar(chalk_ir::Scalar::Bool).intern(Interner) 161 } 162 usize() -> Ty163 pub fn usize() -> Ty { 164 TyKind::Scalar(chalk_ir::Scalar::Uint(chalk_ir::UintTy::Usize)).intern(Interner) 165 } 166 fn_ptr(sig: CallableSig) -> Ty167 pub fn fn_ptr(sig: CallableSig) -> Ty { 168 TyKind::Function(sig.to_fn_ptr()).intern(Interner) 169 } 170 builtin(builtin: BuiltinType) -> Ty171 pub fn builtin(builtin: BuiltinType) -> Ty { 172 match builtin { 173 BuiltinType::Char => TyKind::Scalar(Scalar::Char).intern(Interner), 174 BuiltinType::Bool => TyKind::Scalar(Scalar::Bool).intern(Interner), 175 BuiltinType::Str => TyKind::Str.intern(Interner), 176 BuiltinType::Int(t) => { 177 TyKind::Scalar(Scalar::Int(primitive::int_ty_from_builtin(t))).intern(Interner) 178 } 179 BuiltinType::Uint(t) => { 180 TyKind::Scalar(Scalar::Uint(primitive::uint_ty_from_builtin(t))).intern(Interner) 181 } 182 BuiltinType::Float(t) => { 183 TyKind::Scalar(Scalar::Float(primitive::float_ty_from_builtin(t))).intern(Interner) 184 } 185 } 186 } 187 slice(argument: Ty) -> Ty188 pub fn slice(argument: Ty) -> Ty { 189 TyKind::Slice(argument).intern(Interner) 190 } 191 placeholder_subst(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> Substitution192 pub fn placeholder_subst(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> Substitution { 193 let params = generics(db.upcast(), def.into()); 194 params.placeholder_subst(db) 195 } 196 unknown_subst(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> Substitution197 pub fn unknown_subst(db: &dyn HirDatabase, def: impl Into<GenericDefId>) -> Substitution { 198 let params = generics(db.upcast(), def.into()); 199 Substitution::from_iter( 200 Interner, 201 params.iter_id().map(|id| match id { 202 either::Either::Left(_) => TyKind::Error.intern(Interner).cast(Interner), 203 either::Either::Right(id) => { 204 unknown_const_as_generic(db.const_param_ty(id)).cast(Interner) 205 } 206 }), 207 ) 208 } 209 subst_for_def( db: &dyn HirDatabase, def: impl Into<GenericDefId>, parent_subst: Option<Substitution>, ) -> TyBuilder<()>210 pub fn subst_for_def( 211 db: &dyn HirDatabase, 212 def: impl Into<GenericDefId>, 213 parent_subst: Option<Substitution>, 214 ) -> TyBuilder<()> { 215 let generics = generics(db.upcast(), def.into()); 216 assert!(generics.parent_generics().is_some() == parent_subst.is_some()); 217 let params = generics 218 .iter_self() 219 .map(|(id, data)| match data { 220 TypeOrConstParamData::TypeParamData(_) => ParamKind::Type, 221 TypeOrConstParamData::ConstParamData(_) => { 222 ParamKind::Const(db.const_param_ty(ConstParamId::from_unchecked(id))) 223 } 224 }) 225 .collect(); 226 TyBuilder::new((), params, parent_subst) 227 } 228 229 /// Creates a `TyBuilder` to build `Substitution` for a generator defined in `parent`. 230 /// 231 /// A generator's substitution consists of: 232 /// - resume type of generator 233 /// - yield type of generator ([`Generator::Yield`](std::ops::Generator::Yield)) 234 /// - return type of generator ([`Generator::Return`](std::ops::Generator::Return)) 235 /// - generic parameters in scope on `parent` 236 /// in this order. 237 /// 238 /// This method prepopulates the builder with placeholder substitution of `parent`, so you 239 /// should only push exactly 3 `GenericArg`s before building. subst_for_generator(db: &dyn HirDatabase, parent: DefWithBodyId) -> TyBuilder<()>240 pub fn subst_for_generator(db: &dyn HirDatabase, parent: DefWithBodyId) -> TyBuilder<()> { 241 let parent_subst = 242 parent.as_generic_def_id().map(|p| generics(db.upcast(), p).placeholder_subst(db)); 243 // These represent resume type, yield type, and return type of generator. 244 let params = std::iter::repeat(ParamKind::Type).take(3).collect(); 245 TyBuilder::new((), params, parent_subst) 246 } 247 subst_for_closure( db: &dyn HirDatabase, parent: DefWithBodyId, sig_ty: Ty, ) -> Substitution248 pub fn subst_for_closure( 249 db: &dyn HirDatabase, 250 parent: DefWithBodyId, 251 sig_ty: Ty, 252 ) -> Substitution { 253 let sig_ty = sig_ty.cast(Interner); 254 let self_subst = iter::once(&sig_ty); 255 let Some(parent) = parent.as_generic_def_id() else { 256 return Substitution::from_iter(Interner, self_subst); 257 }; 258 Substitution::from_iter( 259 Interner, 260 self_subst 261 .chain(generics(db.upcast(), parent).placeholder_subst(db).iter(Interner)) 262 .cloned() 263 .collect::<Vec<_>>(), 264 ) 265 } 266 build(self) -> Substitution267 pub fn build(self) -> Substitution { 268 let ((), subst) = self.build_internal(); 269 subst 270 } 271 } 272 273 impl TyBuilder<hir_def::AdtId> { adt(db: &dyn HirDatabase, def: hir_def::AdtId) -> TyBuilder<hir_def::AdtId>274 pub fn adt(db: &dyn HirDatabase, def: hir_def::AdtId) -> TyBuilder<hir_def::AdtId> { 275 TyBuilder::subst_for_def(db, def, None).with_data(def) 276 } 277 fill_with_defaults( mut self, db: &dyn HirDatabase, mut fallback: impl FnMut() -> Ty, ) -> Self278 pub fn fill_with_defaults( 279 mut self, 280 db: &dyn HirDatabase, 281 mut fallback: impl FnMut() -> Ty, 282 ) -> Self { 283 // Note that we're building ADT, so we never have parent generic parameters. 284 let defaults = db.generic_defaults(self.data.into()); 285 let dummy_ty = TyKind::Error.intern(Interner).cast(Interner); 286 for default_ty in defaults.iter().skip(self.vec.len()) { 287 // NOTE(skip_binders): we only check if the arg type is error type. 288 if let Some(x) = default_ty.skip_binders().ty(Interner) { 289 if x.is_unknown() { 290 self.vec.push(fallback().cast(Interner)); 291 continue; 292 } 293 } 294 // Each default can only depend on the previous parameters. 295 // FIXME: we don't handle const generics here. 296 let subst_so_far = Substitution::from_iter( 297 Interner, 298 self.vec 299 .iter() 300 .cloned() 301 .chain(iter::repeat(dummy_ty.clone())) 302 .take(self.param_kinds.len()), 303 ); 304 self.vec.push(default_ty.clone().substitute(Interner, &subst_so_far).cast(Interner)); 305 } 306 self 307 } 308 build(self) -> Ty309 pub fn build(self) -> Ty { 310 let (adt, subst) = self.build_internal(); 311 TyKind::Adt(AdtId(adt), subst).intern(Interner) 312 } 313 } 314 315 pub struct Tuple(usize); 316 impl TyBuilder<Tuple> { tuple(size: usize) -> TyBuilder<Tuple>317 pub fn tuple(size: usize) -> TyBuilder<Tuple> { 318 TyBuilder::new(Tuple(size), iter::repeat(ParamKind::Type).take(size).collect(), None) 319 } 320 build(self) -> Ty321 pub fn build(self) -> Ty { 322 let (Tuple(size), subst) = self.build_internal(); 323 TyKind::Tuple(size, subst).intern(Interner) 324 } 325 tuple_with<I>(elements: I) -> Ty where I: IntoIterator<Item = Ty>, <I as IntoIterator>::IntoIter: ExactSizeIterator,326 pub fn tuple_with<I>(elements: I) -> Ty 327 where 328 I: IntoIterator<Item = Ty>, 329 <I as IntoIterator>::IntoIter: ExactSizeIterator, 330 { 331 let elements = elements.into_iter(); 332 let len = elements.len(); 333 let mut b = 334 TyBuilder::new(Tuple(len), iter::repeat(ParamKind::Type).take(len).collect(), None); 335 for e in elements { 336 b = b.push(e); 337 } 338 b.build() 339 } 340 } 341 342 impl TyBuilder<TraitId> { trait_ref(db: &dyn HirDatabase, def: TraitId) -> TyBuilder<TraitId>343 pub fn trait_ref(db: &dyn HirDatabase, def: TraitId) -> TyBuilder<TraitId> { 344 TyBuilder::subst_for_def(db, def, None).with_data(def) 345 } 346 build(self) -> TraitRef347 pub fn build(self) -> TraitRef { 348 let (trait_id, substitution) = self.build_internal(); 349 TraitRef { trait_id: to_chalk_trait_id(trait_id), substitution } 350 } 351 } 352 353 impl TyBuilder<TypeAliasId> { assoc_type_projection( db: &dyn HirDatabase, def: TypeAliasId, parent_subst: Option<Substitution>, ) -> TyBuilder<TypeAliasId>354 pub fn assoc_type_projection( 355 db: &dyn HirDatabase, 356 def: TypeAliasId, 357 parent_subst: Option<Substitution>, 358 ) -> TyBuilder<TypeAliasId> { 359 TyBuilder::subst_for_def(db, def, parent_subst).with_data(def) 360 } 361 build(self) -> ProjectionTy362 pub fn build(self) -> ProjectionTy { 363 let (type_alias, substitution) = self.build_internal(); 364 ProjectionTy { associated_ty_id: to_assoc_type_id(type_alias), substitution } 365 } 366 } 367 368 impl<T: HasInterner<Interner = Interner> + TypeFoldable<Interner>> TyBuilder<Binders<T>> { build(self) -> T369 pub fn build(self) -> T { 370 let (b, subst) = self.build_internal(); 371 b.substitute(Interner, &subst) 372 } 373 } 374 375 impl TyBuilder<Binders<Ty>> { def_ty( db: &dyn HirDatabase, def: TyDefId, parent_subst: Option<Substitution>, ) -> TyBuilder<Binders<Ty>>376 pub fn def_ty( 377 db: &dyn HirDatabase, 378 def: TyDefId, 379 parent_subst: Option<Substitution>, 380 ) -> TyBuilder<Binders<Ty>> { 381 let poly_ty = db.ty(def); 382 let id: GenericDefId = match def { 383 TyDefId::BuiltinType(_) => { 384 assert!(parent_subst.is_none()); 385 return TyBuilder::new_empty(poly_ty); 386 } 387 TyDefId::AdtId(id) => id.into(), 388 TyDefId::TypeAliasId(id) => id.into(), 389 }; 390 TyBuilder::subst_for_def(db, id, parent_subst).with_data(poly_ty) 391 } 392 impl_self_ty(db: &dyn HirDatabase, def: hir_def::ImplId) -> TyBuilder<Binders<Ty>>393 pub fn impl_self_ty(db: &dyn HirDatabase, def: hir_def::ImplId) -> TyBuilder<Binders<Ty>> { 394 TyBuilder::subst_for_def(db, def, None).with_data(db.impl_self_ty(def)) 395 } 396 } 397