crates/hir-ty/src/chalk_db.rs

   1 //! The implementation of `RustIrDatabase` for Chalk, which provides information
   2 //! about the code that Chalk needs.
   3 use std::sync::Arc;
   4
   5 use cov_mark::hit;
   6 use syntax::SmolStr;
   7 use tracing::debug;
   8
   9 use chalk_ir::{cast::Cast, fold::shift::Shift, CanonicalVarKinds};
  10 use chalk_solve::rust_ir::{self, OpaqueTyDatumBound, WellKnownTrait};
  11
  12 use base_db::CrateId;
  13 use hir_def::{
  14     expr::Movability,
  15     lang_item::{lang_attr, LangItemTarget},
  16     AssocItemId, GenericDefId, HasModule, ItemContainerId, Lookup, ModuleId, TypeAliasId,
  17 };
  18 use hir_expand::name::name;
  19
  20 use crate::{
  21     db::HirDatabase,
  22     display::HirDisplay,
  23     from_assoc_type_id, from_chalk_trait_id, from_foreign_def_id, make_binders,
  24     make_single_type_binders,
  25     mapping::{from_chalk, ToChalk, TypeAliasAsValue},
  26     method_resolution::{TraitImpls, TyFingerprint, ALL_FLOAT_FPS, ALL_INT_FPS},
  27     to_assoc_type_id, to_chalk_trait_id,
  28     traits::ChalkContext,
  29     utils::generics,
  30     wrap_empty_binders, AliasEq, AliasTy, BoundVar, CallableDefId, DebruijnIndex, FnDefId,
  31     Interner, ProjectionTy, ProjectionTyExt, QuantifiedWhereClause, Substitution, TraitRef,
  32     TraitRefExt, Ty, TyBuilder, TyExt, TyKind, WhereClause,
  33 };
  34
  35 pub(crate) type AssociatedTyDatum = chalk_solve::rust_ir::AssociatedTyDatum<Interner>;
  36 pub(crate) type TraitDatum = chalk_solve::rust_ir::TraitDatum<Interner>;
  37 pub(crate) type StructDatum = chalk_solve::rust_ir::AdtDatum<Interner>;
  38 pub(crate) type ImplDatum = chalk_solve::rust_ir::ImplDatum<Interner>;
  39 pub(crate) type OpaqueTyDatum = chalk_solve::rust_ir::OpaqueTyDatum<Interner>;
  40
  41 pub(crate) type AssocTypeId = chalk_ir::AssocTypeId<Interner>;
  42 pub(crate) type TraitId = chalk_ir::TraitId<Interner>;
  43 pub(crate) type AdtId = chalk_ir::AdtId<Interner>;
  44 pub(crate) type ImplId = chalk_ir::ImplId<Interner>;
  45 pub(crate) type AssociatedTyValueId = chalk_solve::rust_ir::AssociatedTyValueId<Interner>;
  46 pub(crate) type AssociatedTyValue = chalk_solve::rust_ir::AssociatedTyValue<Interner>;
  47 pub(crate) type FnDefDatum = chalk_solve::rust_ir::FnDefDatum<Interner>;
  48 pub(crate) type Variances = chalk_ir::Variances<Interner>;
  49
  50 impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
  51     fn associated_ty_data(&self, id: AssocTypeId) -> Arc<AssociatedTyDatum> {
  52         self.db.associated_ty_data(id)
  53     }
  54     fn trait_datum(&self, trait_id: TraitId) -> Arc<TraitDatum> {
  55         self.db.trait_datum(self.krate, trait_id)
  56     }
  57     fn adt_datum(&self, struct_id: AdtId) -> Arc<StructDatum> {
  58         self.db.struct_datum(self.krate, struct_id)
  59     }
  60     fn adt_repr(&self, _struct_id: AdtId) -> Arc<rust_ir::AdtRepr<Interner>> {
  61         // FIXME: keep track of these
  62         Arc::new(rust_ir::AdtRepr { c: false, packed: false, int: None })
  63     }
  64     fn discriminant_type(&self, _ty: chalk_ir::Ty<Interner>) -> chalk_ir::Ty<Interner> {
  65         // FIXME: keep track of this
  66         chalk_ir::TyKind::Scalar(chalk_ir::Scalar::Uint(chalk_ir::UintTy::U32)).intern(Interner)
  67     }
  68     fn impl_datum(&self, impl_id: ImplId) -> Arc<ImplDatum> {
  69         self.db.impl_datum(self.krate, impl_id)
  70     }
  71
  72     fn fn_def_datum(
  73         &self,
  74         fn_def_id: chalk_ir::FnDefId<Interner>,
  75     ) -> Arc<rust_ir::FnDefDatum<Interner>> {
  76         self.db.fn_def_datum(self.krate, fn_def_id)
  77     }
  78
  79     fn impls_for_trait(
  80         &self,
  81         trait_id: TraitId,
  82         parameters: &[chalk_ir::GenericArg<Interner>],
  83         binders: &CanonicalVarKinds<Interner>,
  84     ) -> Vec<ImplId> {
  85         debug!("impls_for_trait {:?}", trait_id);
  86         let trait_: hir_def::TraitId = from_chalk_trait_id(trait_id);
  87
  88         let ty: Ty = parameters[0].assert_ty_ref(Interner).clone();
  89
  90         fn binder_kind(
  91             ty: &Ty,
  92             binders: &CanonicalVarKinds<Interner>,
  93         ) -> Option<chalk_ir::TyVariableKind> {
  94             if let TyKind::BoundVar(bv) = ty.kind(Interner) {
  95                 let binders = binders.as_slice(Interner);
  96                 if bv.debruijn == DebruijnIndex::INNERMOST {
  97                     if let chalk_ir::VariableKind::Ty(tk) = binders[bv.index].kind {
  98                         return Some(tk);
  99                     }
 100                 }
 101             }
 102             None
 103         }
 104
 105         let self_ty_fp = TyFingerprint::for_trait_impl(&ty);
 106         let fps: &[TyFingerprint] = match binder_kind(&ty, binders) {
 107             Some(chalk_ir::TyVariableKind::Integer) => &ALL_INT_FPS,
 108             Some(chalk_ir::TyVariableKind::Float) => &ALL_FLOAT_FPS,
 109             _ => self_ty_fp.as_ref().map(std::slice::from_ref).unwrap_or(&[]),
 110         };
 111
 112         fn local_impls(db: &dyn HirDatabase, module: ModuleId) -> Option<Arc<TraitImpls>> {
 113             let block = module.containing_block()?;
 114             hit!(block_local_impls);
 115             db.trait_impls_in_block(block)
 116         }
 117
 118         // Note: Since we're using impls_for_trait, only impls where the trait
 119         // can be resolved should ever reach Chalk. impl_datum relies on that
 120         // and will panic if the trait can't be resolved.
 121         let in_deps = self.db.trait_impls_in_deps(self.krate);
 122         let in_self = self.db.trait_impls_in_crate(self.krate);
 123         let trait_module = trait_.module(self.db.upcast());
 124         let type_module = match self_ty_fp {
 125             Some(TyFingerprint::Adt(adt_id)) => Some(adt_id.module(self.db.upcast())),
 126             Some(TyFingerprint::ForeignType(type_id)) => {
 127                 Some(from_foreign_def_id(type_id).module(self.db.upcast()))
 128             }
 129             Some(TyFingerprint::Dyn(trait_id)) => Some(trait_id.module(self.db.upcast())),
 130             _ => None,
 131         };
 132         let impl_maps = [
 133             Some(in_deps),
 134             Some(in_self),
 135             local_impls(self.db, trait_module),
 136             type_module.and_then(|m| local_impls(self.db, m)),
 137         ];
 138
 139         let id_to_chalk = |id: hir_def::ImplId| id.to_chalk(self.db);
 140
 141         let result: Vec<_> = if fps.is_empty() {
 142             debug!("Unrestricted search for {:?} impls...", trait_);
 143             impl_maps
 144                 .iter()
 145                 .filter_map(|o| o.as_ref())
 146                 .flat_map(|impls| impls.for_trait(trait_).map(id_to_chalk))
 147                 .collect()
 148         } else {
 149             impl_maps
 150                 .iter()
 151                 .filter_map(|o| o.as_ref())
 152                 .flat_map(|impls| {
 153                     fps.iter().flat_map(move |fp| {
 154                         impls.for_trait_and_self_ty(trait_, *fp).map(id_to_chalk)
 155                     })
 156                 })
 157                 .collect()
 158         };
 159
 160         debug!("impls_for_trait returned {} impls", result.len());
 161         result
 162     }
 163     fn impl_provided_for(&self, auto_trait_id: TraitId, kind: &chalk_ir::TyKind<Interner>) -> bool {
 164         debug!("impl_provided_for {:?}, {:?}", auto_trait_id, kind);
 165         false // FIXME
 166     }
 167     fn associated_ty_value(&self, id: AssociatedTyValueId) -> Arc<AssociatedTyValue> {
 168         self.db.associated_ty_value(self.krate, id)
 169     }
 170
 171     fn custom_clauses(&self) -> Vec<chalk_ir::ProgramClause<Interner>> {
 172         vec![]
 173     }
 174     fn local_impls_to_coherence_check(&self, _trait_id: TraitId) -> Vec<ImplId> {
 175         // We don't do coherence checking (yet)
 176         unimplemented!()
 177     }
 178     fn interner(&self) -> Interner {
 179         Interner
 180     }
 181     fn well_known_trait_id(
 182         &self,
 183         well_known_trait: rust_ir::WellKnownTrait,
 184     ) -> Option<chalk_ir::TraitId<Interner>> {
 185         let lang_attr = lang_attr_from_well_known_trait(well_known_trait);
 186         let trait_ = match self.db.lang_item(self.krate, lang_attr.into()) {
 187             Some(LangItemTarget::TraitId(trait_)) => trait_,
 188             _ => return None,
 189         };
 190         Some(to_chalk_trait_id(trait_))
 191     }
 192
 193     fn program_clauses_for_env(
 194         &self,
 195         environment: &chalk_ir::Environment<Interner>,
 196     ) -> chalk_ir::ProgramClauses<Interner> {
 197         self.db.program_clauses_for_chalk_env(self.krate, environment.clone())
 198     }
 199
 200     fn opaque_ty_data(&self, id: chalk_ir::OpaqueTyId<Interner>) -> Arc<OpaqueTyDatum> {
 201         let full_id = self.db.lookup_intern_impl_trait_id(id.into());
 202         let bound = match full_id {
 203             crate::ImplTraitId::ReturnTypeImplTrait(func, idx) => {
 204                 let datas = self
 205                     .db
 206                     .return_type_impl_traits(func)
 207                     .expect("impl trait id without impl traits");
 208                 let (datas, binders) = (*datas).as_ref().into_value_and_skipped_binders();
 209                 let data = &datas.impl_traits[idx as usize];
 210                 let bound = OpaqueTyDatumBound {
 211                     bounds: make_single_type_binders(data.bounds.skip_binders().to_vec()),
 212                     where_clauses: chalk_ir::Binders::empty(Interner, vec![]),
 213                 };
 214                 chalk_ir::Binders::new(binders, bound)
 215             }
 216             crate::ImplTraitId::AsyncBlockTypeImplTrait(..) => {
 217                 if let Some((future_trait, future_output)) = self
 218                     .db
 219                     .lang_item(self.krate, SmolStr::new_inline("future_trait"))
 220                     .and_then(|item| item.as_trait())
 221                     .and_then(|trait_| {
 222                         let alias =
 223                             self.db.trait_data(trait_).associated_type_by_name(&name![Output])?;
 224                         Some((trait_, alias))
 225                     })
 226                 {
 227                     // Making up Symbol’s value as variable is void: AsyncBlock<T>:
 228                     //
 229                     // |--------------------OpaqueTyDatum-------------------|
 230                     //        |-------------OpaqueTyDatumBound--------------|
 231                     // for<T> <Self> [Future<Self>, Future::Output<Self> = T]
 232                     //     ^1  ^0            ^0                    ^0      ^1
 233                     let impl_bound = WhereClause::Implemented(TraitRef {
 234                         trait_id: to_chalk_trait_id(future_trait),
 235                         // Self type as the first parameter.
 236                         substitution: Substitution::from1(
 237                             Interner,
 238                             TyKind::BoundVar(BoundVar {
 239                                 debruijn: DebruijnIndex::INNERMOST,
 240                                 index: 0,
 241                             })
 242                             .intern(Interner),
 243                         ),
 244                     });
 245                     let mut binder = vec![];
 246                     binder.push(crate::wrap_empty_binders(impl_bound));
 247                     let sized_trait = self
 248                         .db
 249                         .lang_item(self.krate, SmolStr::new_inline("sized"))
 250                         .and_then(|item| item.as_trait());
 251                     if let Some(sized_trait_) = sized_trait {
 252                         let sized_bound = WhereClause::Implemented(TraitRef {
 253                             trait_id: to_chalk_trait_id(sized_trait_),
 254                             // Self type as the first parameter.
 255                             substitution: Substitution::from1(
 256                                 Interner,
 257                                 TyKind::BoundVar(BoundVar {
 258                                     debruijn: DebruijnIndex::INNERMOST,
 259                                     index: 0,
 260                                 })
 261                                 .intern(Interner),
 262                             ),
 263                         });
 264                         binder.push(crate::wrap_empty_binders(sized_bound));
 265                     }
 266                     let proj_bound = WhereClause::AliasEq(AliasEq {
 267                         alias: AliasTy::Projection(ProjectionTy {
 268                             associated_ty_id: to_assoc_type_id(future_output),
 269                             // Self type as the first parameter.
 270                             substitution: Substitution::from1(
 271                                 Interner,
 272                                 TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0))
 273                                     .intern(Interner),
 274                             ),
 275                         }),
 276                         // The parameter of the opaque type.
 277                         ty: TyKind::BoundVar(BoundVar { debruijn: DebruijnIndex::ONE, index: 0 })
 278                             .intern(Interner),
 279                     });
 280                     binder.push(crate::wrap_empty_binders(proj_bound));
 281                     let bound = OpaqueTyDatumBound {
 282                         bounds: make_single_type_binders(binder),
 283                         where_clauses: chalk_ir::Binders::empty(Interner, vec![]),
 284                     };
 285                     // The opaque type has 1 parameter.
 286                     make_single_type_binders(bound)
 287                 } else {
 288                     // If failed to find Symbol’s value as variable is void: Future::Output, return empty bounds as fallback.
 289                     let bound = OpaqueTyDatumBound {
 290                         bounds: chalk_ir::Binders::empty(Interner, vec![]),
 291                         where_clauses: chalk_ir::Binders::empty(Interner, vec![]),
 292                     };
 293                     // The opaque type has 1 parameter.
 294                     make_single_type_binders(bound)
 295                 }
 296             }
 297         };
 298
 299         Arc::new(OpaqueTyDatum { opaque_ty_id: id, bound })
 300     }
 301
 302     fn hidden_opaque_type(&self, _id: chalk_ir::OpaqueTyId<Interner>) -> chalk_ir::Ty<Interner> {
 303         // FIXME: actually provide the hidden type; it is relevant for auto traits
 304         TyKind::Error.intern(Interner)
 305     }
 306
 307     fn is_object_safe(&self, _trait_id: chalk_ir::TraitId<Interner>) -> bool {
 308         // FIXME: implement actual object safety
 309         true
 310     }
 311
 312     fn closure_kind(
 313         &self,
 314         _closure_id: chalk_ir::ClosureId<Interner>,
 315         _substs: &chalk_ir::Substitution<Interner>,
 316     ) -> rust_ir::ClosureKind {
 317         // Fn is the closure kind that implements all three traits
 318         rust_ir::ClosureKind::Fn
 319     }
 320     fn closure_inputs_and_output(
 321         &self,
 322         _closure_id: chalk_ir::ClosureId<Interner>,
 323         substs: &chalk_ir::Substitution<Interner>,
 324     ) -> chalk_ir::Binders<rust_ir::FnDefInputsAndOutputDatum<Interner>> {
 325         let sig_ty = substs.at(Interner, 0).assert_ty_ref(Interner).clone();
 326         let sig = &sig_ty.callable_sig(self.db).expect("first closure param should be fn ptr");
 327         let io = rust_ir::FnDefInputsAndOutputDatum {
 328             argument_types: sig.params().to_vec(),
 329             return_type: sig.ret().clone(),
 330         };
 331         chalk_ir::Binders::empty(Interner, io.shifted_in(Interner))
 332     }
 333     fn closure_upvars(
 334         &self,
 335         _closure_id: chalk_ir::ClosureId<Interner>,
 336         _substs: &chalk_ir::Substitution<Interner>,
 337     ) -> chalk_ir::Binders<chalk_ir::Ty<Interner>> {
 338         let ty = TyBuilder::unit();
 339         chalk_ir::Binders::empty(Interner, ty)
 340     }
 341     fn closure_fn_substitution(
 342         &self,
 343         _closure_id: chalk_ir::ClosureId<Interner>,
 344         _substs: &chalk_ir::Substitution<Interner>,
 345     ) -> chalk_ir::Substitution<Interner> {
 346         Substitution::empty(Interner)
 347     }
 348
 349     fn trait_name(&self, trait_id: chalk_ir::TraitId<Interner>) -> String {
 350         let id = from_chalk_trait_id(trait_id);
 351         self.db.trait_data(id).name.to_string()
 352     }
 353     fn adt_name(&self, chalk_ir::AdtId(adt_id): AdtId) -> String {
 354         match adt_id {
 355             hir_def::AdtId::StructId(id) => self.db.struct_data(id).name.to_string(),
 356             hir_def::AdtId::EnumId(id) => self.db.enum_data(id).name.to_string(),
 357             hir_def::AdtId::UnionId(id) => self.db.union_data(id).name.to_string(),
 358         }
 359     }
 360     fn adt_size_align(&self, _id: chalk_ir::AdtId<Interner>) -> Arc<rust_ir::AdtSizeAlign> {
 361         // FIXME
 362         Arc::new(rust_ir::AdtSizeAlign::from_one_zst(false))
 363     }
 364     fn assoc_type_name(&self, assoc_ty_id: chalk_ir::AssocTypeId<Interner>) -> String {
 365         let id = self.db.associated_ty_data(assoc_ty_id).name;
 366         self.db.type_alias_data(id).name.to_string()
 367     }
 368     fn opaque_type_name(&self, opaque_ty_id: chalk_ir::OpaqueTyId<Interner>) -> String {
 369         format!("Opaque_{}", opaque_ty_id.0)
 370     }
 371     fn fn_def_name(&self, fn_def_id: chalk_ir::FnDefId<Interner>) -> String {
 372         format!("fn_{}", fn_def_id.0)
 373     }
 374     fn generator_datum(
 375         &self,
 376         id: chalk_ir::GeneratorId<Interner>,
 377     ) -> std::sync::Arc<chalk_solve::rust_ir::GeneratorDatum<Interner>> {
 378         let (parent, expr) = self.db.lookup_intern_generator(id.into());
 379
 380         // We fill substitution with unknown type, because we only need to know whether the generic
 381         // params are types or consts to build `Binders` and those being filled up are for
 382         // `resume_type`, `yield_type`, and `return_type` of the generator in question.
 383         let subst = TyBuilder::subst_for_generator(self.db, parent).fill_with_unknown().build();
 384
 385         let len = subst.len(Interner);
 386         let input_output = rust_ir::GeneratorInputOutputDatum {
 387             resume_type: TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, len - 3))
 388                 .intern(Interner),
 389             yield_type: TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, len - 2))
 390                 .intern(Interner),
 391             return_type: TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, len - 1))
 392                 .intern(Interner),
 393             // FIXME: calculate upvars
 394             upvars: vec![],
 395         };
 396
 397         let it = subst
 398             .iter(Interner)
 399             .map(|it| it.constant(Interner).map(|c| c.data(Interner).ty.clone()));
 400         let input_output = crate::make_type_and_const_binders(it, input_output);
 401
 402         let movability = match self.db.body(parent)[expr] {
 403             hir_def::expr::Expr::Closure {
 404                 closure_kind: hir_def::expr::ClosureKind::Generator(movability),
 405                 ..
 406             } => movability,
 407             _ => unreachable!("non generator expression interned as generator"),
 408         };
 409         let movability = match movability {
 410             Movability::Static => rust_ir::Movability::Static,
 411             Movability::Movable => rust_ir::Movability::Movable,
 412         };
 413
 414         Arc::new(rust_ir::GeneratorDatum { movability, input_output })
 415     }
 416     fn generator_witness_datum(
 417         &self,
 418         id: chalk_ir::GeneratorId<Interner>,
 419     ) -> std::sync::Arc<chalk_solve::rust_ir::GeneratorWitnessDatum<Interner>> {
 420         // FIXME: calculate inner types
 421         let inner_types =
 422             rust_ir::GeneratorWitnessExistential { types: wrap_empty_binders(vec![]) };
 423
 424         let (parent, _) = self.db.lookup_intern_generator(id.into());
 425         // See the comment in `generator_datum()` for unknown types.
 426         let subst = TyBuilder::subst_for_generator(self.db, parent).fill_with_unknown().build();
 427         let it = subst
 428             .iter(Interner)
 429             .map(|it| it.constant(Interner).map(|c| c.data(Interner).ty.clone()));
 430         let inner_types = crate::make_type_and_const_binders(it, inner_types);
 431
 432         Arc::new(rust_ir::GeneratorWitnessDatum { inner_types })
 433     }
 434
 435     fn unification_database(&self) -> &dyn chalk_ir::UnificationDatabase<Interner> {
 436         &self.db
 437     }
 438 }
 439
 440 impl<'a> chalk_ir::UnificationDatabase<Interner> for &'a dyn HirDatabase {
 441     fn fn_def_variance(
 442         &self,
 443         fn_def_id: chalk_ir::FnDefId<Interner>,
 444     ) -> chalk_ir::Variances<Interner> {
 445         HirDatabase::fn_def_variance(*self, fn_def_id)
 446     }
 447
 448     fn adt_variance(&self, adt_id: chalk_ir::AdtId<Interner>) -> chalk_ir::Variances<Interner> {
 449         HirDatabase::adt_variance(*self, adt_id)
 450     }
 451 }
 452
 453 pub(crate) fn program_clauses_for_chalk_env_query(
 454     db: &dyn HirDatabase,
 455     krate: CrateId,
 456     environment: chalk_ir::Environment<Interner>,
 457 ) -> chalk_ir::ProgramClauses<Interner> {
 458     chalk_solve::program_clauses_for_env(&ChalkContext { db, krate }, &environment)
 459 }
 460
 461 pub(crate) fn associated_ty_data_query(
 462     db: &dyn HirDatabase,
 463     id: AssocTypeId,
 464 ) -> Arc<AssociatedTyDatum> {
 465     debug!("associated_ty_data {:?}", id);
 466     let type_alias: TypeAliasId = from_assoc_type_id(id);
 467     let trait_ = match type_alias.lookup(db.upcast()).container {
 468         ItemContainerId::TraitId(t) => t,
 469         _ => panic!("associated type not in trait"),
 470     };
 471
 472     // Lower bounds -- we could/should maybe move this to a separate query in `lower`
 473     let type_alias_data = db.type_alias_data(type_alias);
 474     let generic_params = generics(db.upcast(), type_alias.into());
 475     // let bound_vars = generic_params.bound_vars_subst(DebruijnIndex::INNERMOST);
 476     let resolver = hir_def::resolver::HasResolver::resolver(type_alias, db.upcast());
 477     let ctx = crate::TyLoweringContext::new(db, &resolver)
 478         .with_type_param_mode(crate::lower::ParamLoweringMode::Variable);
 479     let pro_ty = TyBuilder::assoc_type_projection(db, type_alias)
 480         .fill_with_bound_vars(crate::DebruijnIndex::INNERMOST, 0)
 481         .build();
 482     let self_ty = TyKind::Alias(AliasTy::Projection(pro_ty)).intern(Interner);
 483     let mut bounds: Vec<_> = type_alias_data
 484         .bounds
 485         .iter()
 486         .flat_map(|bound| ctx.lower_type_bound(bound, self_ty.clone(), false))
 487         .filter_map(|pred| generic_predicate_to_inline_bound(db, &pred, &self_ty))
 488         .collect();
 489
 490     if !ctx.unsized_types.borrow().contains(&self_ty) {
 491         let sized_trait = db
 492             .lang_item(resolver.krate(), SmolStr::new_inline("sized"))
 493             .and_then(|lang_item| lang_item.as_trait().map(to_chalk_trait_id));
 494         let sized_bound = sized_trait.into_iter().map(|sized_trait| {
 495             let trait_bound =
 496                 rust_ir::TraitBound { trait_id: sized_trait, args_no_self: Default::default() };
 497             let inline_bound = rust_ir::InlineBound::TraitBound(trait_bound);
 498             chalk_ir::Binders::empty(Interner, inline_bound)
 499         });
 500         bounds.extend(sized_bound);
 501         bounds.shrink_to_fit();
 502     }
 503
 504     // FIXME: Re-enable where clauses on associated types when an upstream chalk bug is fixed.
 505     //        (rust-analyzer#9052)
 506     // let where_clauses = convert_where_clauses(db, type_alias.into(), &bound_vars);
 507     let bound_data = rust_ir::AssociatedTyDatumBound { bounds, where_clauses: vec![] };
 508     let datum = AssociatedTyDatum {
 509         trait_id: to_chalk_trait_id(trait_),
 510         id,
 511         name: type_alias,
 512         binders: make_binders(db, &generic_params, bound_data),
 513     };
 514     Arc::new(datum)
 515 }
 516
 517 pub(crate) fn trait_datum_query(
 518     db: &dyn HirDatabase,
 519     krate: CrateId,
 520     trait_id: TraitId,
 521 ) -> Arc<TraitDatum> {
 522     debug!("trait_datum {:?}", trait_id);
 523     let trait_ = from_chalk_trait_id(trait_id);
 524     let trait_data = db.trait_data(trait_);
 525     debug!("trait {:?} = {:?}", trait_id, trait_data.name);
 526     let generic_params = generics(db.upcast(), trait_.into());
 527     let bound_vars = generic_params.bound_vars_subst(db, DebruijnIndex::INNERMOST);
 528     let flags = rust_ir::TraitFlags {
 529         auto: trait_data.is_auto,
 530         upstream: trait_.lookup(db.upcast()).container.krate() != krate,
 531         non_enumerable: true,
 532         coinductive: false, // only relevant for Chalk testing
 533         // FIXME: set these flags correctly
 534         marker: false,
 535         fundamental: false,
 536     };
 537     let where_clauses = convert_where_clauses(db, trait_.into(), &bound_vars);
 538     let associated_ty_ids = trait_data.associated_types().map(to_assoc_type_id).collect();
 539     let trait_datum_bound = rust_ir::TraitDatumBound { where_clauses };
 540     let well_known =
 541         lang_attr(db.upcast(), trait_).and_then(|name| well_known_trait_from_lang_attr(&name));
 542     let trait_datum = TraitDatum {
 543         id: trait_id,
 544         binders: make_binders(db, &generic_params, trait_datum_bound),
 545         flags,
 546         associated_ty_ids,
 547         well_known,
 548     };
 549     Arc::new(trait_datum)
 550 }
 551
 552 fn well_known_trait_from_lang_attr(name: &str) -> Option<WellKnownTrait> {
 553     Some(match name {
 554         "clone" => WellKnownTrait::Clone,
 555         "coerce_unsized" => WellKnownTrait::CoerceUnsized,
 556         "copy" => WellKnownTrait::Copy,
 557         "discriminant_kind" => WellKnownTrait::DiscriminantKind,
 558         "dispatch_from_dyn" => WellKnownTrait::DispatchFromDyn,
 559         "drop" => WellKnownTrait::Drop,
 560         "fn" => WellKnownTrait::Fn,
 561         "fn_mut" => WellKnownTrait::FnMut,
 562         "fn_once" => WellKnownTrait::FnOnce,
 563         "generator" => WellKnownTrait::Generator,
 564         "sized" => WellKnownTrait::Sized,
 565         "unpin" => WellKnownTrait::Unpin,
 566         "unsize" => WellKnownTrait::Unsize,
 567         _ => return None,
 568     })
 569 }
 570
 571 fn lang_attr_from_well_known_trait(attr: WellKnownTrait) -> &'static str {
 572     match attr {
 573         WellKnownTrait::Clone => "clone",
 574         WellKnownTrait::CoerceUnsized => "coerce_unsized",
 575         WellKnownTrait::Copy => "copy",
 576         WellKnownTrait::DiscriminantKind => "discriminant_kind",
 577         WellKnownTrait::DispatchFromDyn => "dispatch_from_dyn",
 578         WellKnownTrait::Drop => "drop",
 579         WellKnownTrait::Fn => "fn",
 580         WellKnownTrait::FnMut => "fn_mut",
 581         WellKnownTrait::FnOnce => "fn_once",
 582         WellKnownTrait::Generator => "generator",
 583         WellKnownTrait::Sized => "sized",
 584         WellKnownTrait::Unpin => "unpin",
 585         WellKnownTrait::Unsize => "unsize",
 586     }
 587 }
 588
 589 pub(crate) fn struct_datum_query(
 590     db: &dyn HirDatabase,
 591     krate: CrateId,
 592     struct_id: AdtId,
 593 ) -> Arc<StructDatum> {
 594     debug!("struct_datum {:?}", struct_id);
 595     let chalk_ir::AdtId(adt_id) = struct_id;
 596     let generic_params = generics(db.upcast(), adt_id.into());
 597     let upstream = adt_id.module(db.upcast()).krate() != krate;
 598     let where_clauses = {
 599         let generic_params = generics(db.upcast(), adt_id.into());
 600         let bound_vars = generic_params.bound_vars_subst(db, DebruijnIndex::INNERMOST);
 601         convert_where_clauses(db, adt_id.into(), &bound_vars)
 602     };
 603     let flags = rust_ir::AdtFlags {
 604         upstream,
 605         // FIXME set fundamental and phantom_data flags correctly
 606         fundamental: false,
 607         phantom_data: false,
 608     };
 609     // FIXME provide enum variants properly (for auto traits)
 610     let variant = rust_ir::AdtVariantDatum {
 611         fields: Vec::new(), // FIXME add fields (only relevant for auto traits),
 612     };
 613     let struct_datum_bound = rust_ir::AdtDatumBound { variants: vec![variant], where_clauses };
 614     let struct_datum = StructDatum {
 615         // FIXME set ADT kind
 616         kind: rust_ir::AdtKind::Struct,
 617         id: struct_id,
 618         binders: make_binders(db, &generic_params, struct_datum_bound),
 619         flags,
 620     };
 621     Arc::new(struct_datum)
 622 }
 623
 624 pub(crate) fn impl_datum_query(
 625     db: &dyn HirDatabase,
 626     krate: CrateId,
 627     impl_id: ImplId,
 628 ) -> Arc<ImplDatum> {
 629     let _p = profile::span("impl_datum");
 630     debug!("impl_datum {:?}", impl_id);
 631     let impl_: hir_def::ImplId = from_chalk(db, impl_id);
 632     impl_def_datum(db, krate, impl_id, impl_)
 633 }
 634
 635 fn impl_def_datum(
 636     db: &dyn HirDatabase,
 637     krate: CrateId,
 638     chalk_id: ImplId,
 639     impl_id: hir_def::ImplId,
 640 ) -> Arc<ImplDatum> {
 641     let trait_ref = db
 642         .impl_trait(impl_id)
 643         // ImplIds for impls where the trait ref can't be resolved should never reach Chalk
 644         .expect("invalid impl passed to Chalk")
 645         .into_value_and_skipped_binders()
 646         .0;
 647     let impl_data = db.impl_data(impl_id);
 648
 649     let generic_params = generics(db.upcast(), impl_id.into());
 650     let bound_vars = generic_params.bound_vars_subst(db, DebruijnIndex::INNERMOST);
 651     let trait_ = trait_ref.hir_trait_id();
 652     let impl_type = if impl_id.lookup(db.upcast()).container.krate() == krate {
 653         rust_ir::ImplType::Local
 654     } else {
 655         rust_ir::ImplType::External
 656     };
 657     let where_clauses = convert_where_clauses(db, impl_id.into(), &bound_vars);
 658     let negative = impl_data.is_negative;
 659     debug!(
 660         "impl {:?}: {}{} where {:?}",
 661         chalk_id,
 662         if negative { "!" } else { "" },
 663         trait_ref.display(db),
 664         where_clauses
 665     );
 666
 667     let polarity = if negative { rust_ir::Polarity::Negative } else { rust_ir::Polarity::Positive };
 668
 669     let impl_datum_bound = rust_ir::ImplDatumBound { trait_ref, where_clauses };
 670     let trait_data = db.trait_data(trait_);
 671     let associated_ty_value_ids = impl_data
 672         .items
 673         .iter()
 674         .filter_map(|item| match item {
 675             AssocItemId::TypeAliasId(type_alias) => Some(*type_alias),
 676             _ => None,
 677         })
 678         .filter(|&type_alias| {
 679             // don't include associated types that don't exist in the trait
 680             let name = &db.type_alias_data(type_alias).name;
 681             trait_data.associated_type_by_name(name).is_some()
 682         })
 683         .map(|type_alias| TypeAliasAsValue(type_alias).to_chalk(db))
 684         .collect();
 685     debug!("impl_datum: {:?}", impl_datum_bound);
 686     let impl_datum = ImplDatum {
 687         binders: make_binders(db, &generic_params, impl_datum_bound),
 688         impl_type,
 689         polarity,
 690         associated_ty_value_ids,
 691     };
 692     Arc::new(impl_datum)
 693 }
 694
 695 pub(crate) fn associated_ty_value_query(
 696     db: &dyn HirDatabase,
 697     krate: CrateId,
 698     id: AssociatedTyValueId,
 699 ) -> Arc<AssociatedTyValue> {
 700     let type_alias: TypeAliasAsValue = from_chalk(db, id);
 701     type_alias_associated_ty_value(db, krate, type_alias.0)
 702 }
 703
 704 fn type_alias_associated_ty_value(
 705     db: &dyn HirDatabase,
 706     _krate: CrateId,
 707     type_alias: TypeAliasId,
 708 ) -> Arc<AssociatedTyValue> {
 709     let type_alias_data = db.type_alias_data(type_alias);
 710     let impl_id = match type_alias.lookup(db.upcast()).container {
 711         ItemContainerId::ImplId(it) => it,
 712         _ => panic!("assoc ty value should be in impl"),
 713     };
 714
 715     let trait_ref = db
 716         .impl_trait(impl_id)
 717         .expect("assoc ty value should not exist")
 718         .into_value_and_skipped_binders()
 719         .0; // we don't return any assoc ty values if the impl'd trait can't be resolved
 720
 721     let assoc_ty = db
 722         .trait_data(trait_ref.hir_trait_id())
 723         .associated_type_by_name(&type_alias_data.name)
 724         .expect("assoc ty value should not exist"); // validated when building the impl data as well
 725     let (ty, binders) = db.ty(type_alias.into()).into_value_and_skipped_binders();
 726     let value_bound = rust_ir::AssociatedTyValueBound { ty };
 727     let value = rust_ir::AssociatedTyValue {
 728         impl_id: impl_id.to_chalk(db),
 729         associated_ty_id: to_assoc_type_id(assoc_ty),
 730         value: chalk_ir::Binders::new(binders, value_bound),
 731     };
 732     Arc::new(value)
 733 }
 734
 735 pub(crate) fn fn_def_datum_query(
 736     db: &dyn HirDatabase,
 737     _krate: CrateId,
 738     fn_def_id: FnDefId,
 739 ) -> Arc<FnDefDatum> {
 740     let callable_def: CallableDefId = from_chalk(db, fn_def_id);
 741     let generic_params = generics(db.upcast(), callable_def.into());
 742     let (sig, binders) = db.callable_item_signature(callable_def).into_value_and_skipped_binders();
 743     let bound_vars = generic_params.bound_vars_subst(db, DebruijnIndex::INNERMOST);
 744     let where_clauses = convert_where_clauses(db, callable_def.into(), &bound_vars);
 745     let bound = rust_ir::FnDefDatumBound {
 746         // Note: Chalk doesn't actually use this information yet as far as I am aware, but we provide it anyway
 747         inputs_and_output: chalk_ir::Binders::empty(
 748             Interner,
 749             rust_ir::FnDefInputsAndOutputDatum {
 750                 argument_types: sig.params().to_vec(),
 751                 return_type: sig.ret().clone(),
 752             }
 753             .shifted_in(Interner),
 754         ),
 755         where_clauses,
 756     };
 757     let datum = FnDefDatum {
 758         id: fn_def_id,
 759         sig: chalk_ir::FnSig { abi: (), safety: chalk_ir::Safety::Safe, variadic: sig.is_varargs },
 760         binders: chalk_ir::Binders::new(binders, bound),
 761     };
 762     Arc::new(datum)
 763 }
 764
 765 pub(crate) fn fn_def_variance_query(db: &dyn HirDatabase, fn_def_id: FnDefId) -> Variances {
 766     let callable_def: CallableDefId = from_chalk(db, fn_def_id);
 767     let generic_params = generics(db.upcast(), callable_def.into());
 768     Variances::from_iter(
 769         Interner,
 770         std::iter::repeat(chalk_ir::Variance::Invariant).take(generic_params.len()),
 771     )
 772 }
 773
 774 pub(crate) fn adt_variance_query(
 775     db: &dyn HirDatabase,
 776     chalk_ir::AdtId(adt_id): AdtId,
 777 ) -> Variances {
 778     let generic_params = generics(db.upcast(), adt_id.into());
 779     Variances::from_iter(
 780         Interner,
 781         std::iter::repeat(chalk_ir::Variance::Invariant).take(generic_params.len()),
 782     )
 783 }
 784
 785 pub(super) fn convert_where_clauses(
 786     db: &dyn HirDatabase,
 787     def: GenericDefId,
 788     substs: &Substitution,
 789 ) -> Vec<chalk_ir::QuantifiedWhereClause<Interner>> {
 790     let generic_predicates = db.generic_predicates(def);
 791     let mut result = Vec::with_capacity(generic_predicates.len());
 792     for pred in generic_predicates.iter() {
 793         result.push(pred.clone().substitute(Interner, substs));
 794     }
 795     result
 796 }
 797
 798 pub(super) fn generic_predicate_to_inline_bound(
 799     db: &dyn HirDatabase,
 800     pred: &QuantifiedWhereClause,
 801     self_ty: &Ty,
 802 ) -> Option<chalk_ir::Binders<rust_ir::InlineBound<Interner>>> {
 803     // An InlineBound is like a GenericPredicate, except the self type is left out.
 804     // We don't have a special type for this, but Chalk does.
 805     let self_ty_shifted_in = self_ty.clone().shifted_in_from(Interner, DebruijnIndex::ONE);
 806     let (pred, binders) = pred.as_ref().into_value_and_skipped_binders();
 807     match pred {
 808         WhereClause::Implemented(trait_ref) => {
 809             if trait_ref.self_type_parameter(Interner) != self_ty_shifted_in {
 810                 // we can only convert predicates back to type bounds if they
 811                 // have the expected self type
 812                 return None;
 813             }
 814             let args_no_self = trait_ref.substitution.as_slice(Interner)[1..]
 815                 .iter()
 816                 .map(|ty| ty.clone().cast(Interner))
 817                 .collect();
 818             let trait_bound = rust_ir::TraitBound { trait_id: trait_ref.trait_id, args_no_self };
 819             Some(chalk_ir::Binders::new(binders, rust_ir::InlineBound::TraitBound(trait_bound)))
 820         }
 821         WhereClause::AliasEq(AliasEq { alias: AliasTy::Projection(projection_ty), ty }) => {
 822             if projection_ty.self_type_parameter(Interner) != self_ty_shifted_in {
 823                 return None;
 824             }
 825             let trait_ = projection_ty.trait_(db);
 826             let args_no_self = projection_ty.substitution.as_slice(Interner)[1..]
 827                 .iter()
 828                 .map(|ty| ty.clone().cast(Interner))
 829                 .collect();
 830             let alias_eq_bound = rust_ir::AliasEqBound {
 831                 value: ty.clone(),
 832                 trait_bound: rust_ir::TraitBound {
 833                     trait_id: to_chalk_trait_id(trait_),
 834                     args_no_self,
 835                 },
 836                 associated_ty_id: projection_ty.associated_ty_id,
 837                 parameters: Vec::new(), // FIXME we don't support generic associated types yet
 838             };
 839             Some(chalk_ir::Binders::new(
 840                 binders,
 841                 rust_ir::InlineBound::AliasEqBound(alias_eq_bound),
 842             ))
 843         }
 844         _ => None,
 845     }
 846 }