src/tools/rust-analyzer/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 input_output = rust_ir::GeneratorInputOutputDatum {
 386             resume_type: TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 0))
 387                 .intern(Interner),
 388             yield_type: TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 1))
 389                 .intern(Interner),
 390             return_type: TyKind::BoundVar(BoundVar::new(DebruijnIndex::INNERMOST, 2))
 391                 .intern(Interner),
 392             // FIXME: calculate upvars
 393             upvars: vec![],
 394         };
 395
 396         let it = subst
 397             .iter(Interner)
 398             .map(|it| it.constant(Interner).map(|c| c.data(Interner).ty.clone()));
 399         let input_output = crate::make_type_and_const_binders(it, input_output);
 400
 401         let movability = match self.db.body(parent)[expr] {
 402             hir_def::expr::Expr::Closure {
 403                 closure_kind: hir_def::expr::ClosureKind::Generator(movability),
 404                 ..
 405             } => movability,
 406             _ => unreachable!("non generator expression interned as generator"),
 407         };
 408         let movability = match movability {
 409             Movability::Static => rust_ir::Movability::Static,
 410             Movability::Movable => rust_ir::Movability::Movable,
 411         };
 412
 413         Arc::new(rust_ir::GeneratorDatum { movability, input_output })
 414     }
 415     fn generator_witness_datum(
 416         &self,
 417         id: chalk_ir::GeneratorId<Interner>,
 418     ) -> std::sync::Arc<chalk_solve::rust_ir::GeneratorWitnessDatum<Interner>> {
 419         // FIXME: calculate inner types
 420         let inner_types =
 421             rust_ir::GeneratorWitnessExistential { types: wrap_empty_binders(vec![]) };
 422
 423         let (parent, _) = self.db.lookup_intern_generator(id.into());
 424         // See the comment in `generator_datum()` for unknown types.
 425         let subst = TyBuilder::subst_for_generator(self.db, parent).fill_with_unknown().build();
 426         let it = subst
 427             .iter(Interner)
 428             .map(|it| it.constant(Interner).map(|c| c.data(Interner).ty.clone()));
 429         let inner_types = crate::make_type_and_const_binders(it, inner_types);
 430
 431         Arc::new(rust_ir::GeneratorWitnessDatum { inner_types })
 432     }
 433
 434     fn unification_database(&self) -> &dyn chalk_ir::UnificationDatabase<Interner> {
 435         &self.db
 436     }
 437 }
 438
 439 impl<'a> chalk_ir::UnificationDatabase<Interner> for &'a dyn HirDatabase {
 440     fn fn_def_variance(
 441         &self,
 442         fn_def_id: chalk_ir::FnDefId<Interner>,
 443     ) -> chalk_ir::Variances<Interner> {
 444         HirDatabase::fn_def_variance(*self, fn_def_id)
 445     }
 446
 447     fn adt_variance(&self, adt_id: chalk_ir::AdtId<Interner>) -> chalk_ir::Variances<Interner> {
 448         HirDatabase::adt_variance(*self, adt_id)
 449     }
 450 }
 451
 452 pub(crate) fn program_clauses_for_chalk_env_query(
 453     db: &dyn HirDatabase,
 454     krate: CrateId,
 455     environment: chalk_ir::Environment<Interner>,
 456 ) -> chalk_ir::ProgramClauses<Interner> {
 457     chalk_solve::program_clauses_for_env(&ChalkContext { db, krate }, &environment)
 458 }
 459
 460 pub(crate) fn associated_ty_data_query(
 461     db: &dyn HirDatabase,
 462     id: AssocTypeId,
 463 ) -> Arc<AssociatedTyDatum> {
 464     debug!("associated_ty_data {:?}", id);
 465     let type_alias: TypeAliasId = from_assoc_type_id(id);
 466     let trait_ = match type_alias.lookup(db.upcast()).container {
 467         ItemContainerId::TraitId(t) => t,
 468         _ => panic!("associated type not in trait"),
 469     };
 470
 471     // Lower bounds -- we could/should maybe move this to a separate query in `lower`
 472     let type_alias_data = db.type_alias_data(type_alias);
 473     let generic_params = generics(db.upcast(), type_alias.into());
 474     // let bound_vars = generic_params.bound_vars_subst(DebruijnIndex::INNERMOST);
 475     let resolver = hir_def::resolver::HasResolver::resolver(type_alias, db.upcast());
 476     let ctx = crate::TyLoweringContext::new(db, &resolver)
 477         .with_type_param_mode(crate::lower::ParamLoweringMode::Variable);
 478
 479     let trait_subst = TyBuilder::subst_for_def(db, trait_, None)
 480         .fill_with_bound_vars(crate::DebruijnIndex::INNERMOST, generic_params.len_self())
 481         .build();
 482     let pro_ty = TyBuilder::assoc_type_projection(db, type_alias, Some(trait_subst))
 483         .fill_with_bound_vars(crate::DebruijnIndex::INNERMOST, 0)
 484         .build();
 485     let self_ty = TyKind::Alias(AliasTy::Projection(pro_ty)).intern(Interner);
 486
 487     let mut bounds: Vec<_> = type_alias_data
 488         .bounds
 489         .iter()
 490         .flat_map(|bound| ctx.lower_type_bound(bound, self_ty.clone(), false))
 491         .filter_map(|pred| generic_predicate_to_inline_bound(db, &pred, &self_ty))
 492         .collect();
 493
 494     if !ctx.unsized_types.borrow().contains(&self_ty) {
 495         let sized_trait = db
 496             .lang_item(resolver.krate(), SmolStr::new_inline("sized"))
 497             .and_then(|lang_item| lang_item.as_trait().map(to_chalk_trait_id));
 498         let sized_bound = sized_trait.into_iter().map(|sized_trait| {
 499             let trait_bound =
 500                 rust_ir::TraitBound { trait_id: sized_trait, args_no_self: Default::default() };
 501             let inline_bound = rust_ir::InlineBound::TraitBound(trait_bound);
 502             chalk_ir::Binders::empty(Interner, inline_bound)
 503         });
 504         bounds.extend(sized_bound);
 505         bounds.shrink_to_fit();
 506     }
 507
 508     // FIXME: Re-enable where clauses on associated types when an upstream chalk bug is fixed.
 509     //        (rust-analyzer#9052)
 510     // let where_clauses = convert_where_clauses(db, type_alias.into(), &bound_vars);
 511     let bound_data = rust_ir::AssociatedTyDatumBound { bounds, where_clauses: vec![] };
 512     let datum = AssociatedTyDatum {
 513         trait_id: to_chalk_trait_id(trait_),
 514         id,
 515         name: type_alias,
 516         binders: make_binders(db, &generic_params, bound_data),
 517     };
 518     Arc::new(datum)
 519 }
 520
 521 pub(crate) fn trait_datum_query(
 522     db: &dyn HirDatabase,
 523     krate: CrateId,
 524     trait_id: TraitId,
 525 ) -> Arc<TraitDatum> {
 526     debug!("trait_datum {:?}", trait_id);
 527     let trait_ = from_chalk_trait_id(trait_id);
 528     let trait_data = db.trait_data(trait_);
 529     debug!("trait {:?} = {:?}", trait_id, trait_data.name);
 530     let generic_params = generics(db.upcast(), trait_.into());
 531     let bound_vars = generic_params.bound_vars_subst(db, DebruijnIndex::INNERMOST);
 532     let flags = rust_ir::TraitFlags {
 533         auto: trait_data.is_auto,
 534         upstream: trait_.lookup(db.upcast()).container.krate() != krate,
 535         non_enumerable: true,
 536         coinductive: false, // only relevant for Chalk testing
 537         // FIXME: set these flags correctly
 538         marker: false,
 539         fundamental: false,
 540     };
 541     let where_clauses = convert_where_clauses(db, trait_.into(), &bound_vars);
 542     let associated_ty_ids = trait_data.associated_types().map(to_assoc_type_id).collect();
 543     let trait_datum_bound = rust_ir::TraitDatumBound { where_clauses };
 544     let well_known =
 545         lang_attr(db.upcast(), trait_).and_then(|name| well_known_trait_from_lang_attr(&name));
 546     let trait_datum = TraitDatum {
 547         id: trait_id,
 548         binders: make_binders(db, &generic_params, trait_datum_bound),
 549         flags,
 550         associated_ty_ids,
 551         well_known,
 552     };
 553     Arc::new(trait_datum)
 554 }
 555
 556 fn well_known_trait_from_lang_attr(name: &str) -> Option<WellKnownTrait> {
 557     Some(match name {
 558         "clone" => WellKnownTrait::Clone,
 559         "coerce_unsized" => WellKnownTrait::CoerceUnsized,
 560         "copy" => WellKnownTrait::Copy,
 561         "discriminant_kind" => WellKnownTrait::DiscriminantKind,
 562         "dispatch_from_dyn" => WellKnownTrait::DispatchFromDyn,
 563         "drop" => WellKnownTrait::Drop,
 564         "fn" => WellKnownTrait::Fn,
 565         "fn_mut" => WellKnownTrait::FnMut,
 566         "fn_once" => WellKnownTrait::FnOnce,
 567         "generator" => WellKnownTrait::Generator,
 568         "sized" => WellKnownTrait::Sized,
 569         "unpin" => WellKnownTrait::Unpin,
 570         "unsize" => WellKnownTrait::Unsize,
 571         "tuple_trait" => WellKnownTrait::Tuple,
 572         _ => return None,
 573     })
 574 }
 575
 576 fn lang_attr_from_well_known_trait(attr: WellKnownTrait) -> &'static str {
 577     match attr {
 578         WellKnownTrait::Clone => "clone",
 579         WellKnownTrait::CoerceUnsized => "coerce_unsized",
 580         WellKnownTrait::Copy => "copy",
 581         WellKnownTrait::DiscriminantKind => "discriminant_kind",
 582         WellKnownTrait::DispatchFromDyn => "dispatch_from_dyn",
 583         WellKnownTrait::Drop => "drop",
 584         WellKnownTrait::Fn => "fn",
 585         WellKnownTrait::FnMut => "fn_mut",
 586         WellKnownTrait::FnOnce => "fn_once",
 587         WellKnownTrait::Generator => "generator",
 588         WellKnownTrait::Sized => "sized",
 589         WellKnownTrait::Tuple => "tuple_trait",
 590         WellKnownTrait::Unpin => "unpin",
 591         WellKnownTrait::Unsize => "unsize",
 592     }
 593 }
 594
 595 pub(crate) fn struct_datum_query(
 596     db: &dyn HirDatabase,
 597     krate: CrateId,
 598     struct_id: AdtId,
 599 ) -> Arc<StructDatum> {
 600     debug!("struct_datum {:?}", struct_id);
 601     let chalk_ir::AdtId(adt_id) = struct_id;
 602     let generic_params = generics(db.upcast(), adt_id.into());
 603     let upstream = adt_id.module(db.upcast()).krate() != krate;
 604     let where_clauses = {
 605         let generic_params = generics(db.upcast(), adt_id.into());
 606         let bound_vars = generic_params.bound_vars_subst(db, DebruijnIndex::INNERMOST);
 607         convert_where_clauses(db, adt_id.into(), &bound_vars)
 608     };
 609     let flags = rust_ir::AdtFlags {
 610         upstream,
 611         // FIXME set fundamental and phantom_data flags correctly
 612         fundamental: false,
 613         phantom_data: false,
 614     };
 615     // FIXME provide enum variants properly (for auto traits)
 616     let variant = rust_ir::AdtVariantDatum {
 617         fields: Vec::new(), // FIXME add fields (only relevant for auto traits),
 618     };
 619     let struct_datum_bound = rust_ir::AdtDatumBound { variants: vec![variant], where_clauses };
 620     let struct_datum = StructDatum {
 621         // FIXME set ADT kind
 622         kind: rust_ir::AdtKind::Struct,
 623         id: struct_id,
 624         binders: make_binders(db, &generic_params, struct_datum_bound),
 625         flags,
 626     };
 627     Arc::new(struct_datum)
 628 }
 629
 630 pub(crate) fn impl_datum_query(
 631     db: &dyn HirDatabase,
 632     krate: CrateId,
 633     impl_id: ImplId,
 634 ) -> Arc<ImplDatum> {
 635     let _p = profile::span("impl_datum");
 636     debug!("impl_datum {:?}", impl_id);
 637     let impl_: hir_def::ImplId = from_chalk(db, impl_id);
 638     impl_def_datum(db, krate, impl_id, impl_)
 639 }
 640
 641 fn impl_def_datum(
 642     db: &dyn HirDatabase,
 643     krate: CrateId,
 644     chalk_id: ImplId,
 645     impl_id: hir_def::ImplId,
 646 ) -> Arc<ImplDatum> {
 647     let trait_ref = db
 648         .impl_trait(impl_id)
 649         // ImplIds for impls where the trait ref can't be resolved should never reach Chalk
 650         .expect("invalid impl passed to Chalk")
 651         .into_value_and_skipped_binders()
 652         .0;
 653     let impl_data = db.impl_data(impl_id);
 654
 655     let generic_params = generics(db.upcast(), impl_id.into());
 656     let bound_vars = generic_params.bound_vars_subst(db, DebruijnIndex::INNERMOST);
 657     let trait_ = trait_ref.hir_trait_id();
 658     let impl_type = if impl_id.lookup(db.upcast()).container.krate() == krate {
 659         rust_ir::ImplType::Local
 660     } else {
 661         rust_ir::ImplType::External
 662     };
 663     let where_clauses = convert_where_clauses(db, impl_id.into(), &bound_vars);
 664     let negative = impl_data.is_negative;
 665     debug!(
 666         "impl {:?}: {}{} where {:?}",
 667         chalk_id,
 668         if negative { "!" } else { "" },
 669         trait_ref.display(db),
 670         where_clauses
 671     );
 672
 673     let polarity = if negative { rust_ir::Polarity::Negative } else { rust_ir::Polarity::Positive };
 674
 675     let impl_datum_bound = rust_ir::ImplDatumBound { trait_ref, where_clauses };
 676     let trait_data = db.trait_data(trait_);
 677     let associated_ty_value_ids = impl_data
 678         .items
 679         .iter()
 680         .filter_map(|item| match item {
 681             AssocItemId::TypeAliasId(type_alias) => Some(*type_alias),
 682             _ => None,
 683         })
 684         .filter(|&type_alias| {
 685             // don't include associated types that don't exist in the trait
 686             let name = &db.type_alias_data(type_alias).name;
 687             trait_data.associated_type_by_name(name).is_some()
 688         })
 689         .map(|type_alias| TypeAliasAsValue(type_alias).to_chalk(db))
 690         .collect();
 691     debug!("impl_datum: {:?}", impl_datum_bound);
 692     let impl_datum = ImplDatum {
 693         binders: make_binders(db, &generic_params, impl_datum_bound),
 694         impl_type,
 695         polarity,
 696         associated_ty_value_ids,
 697     };
 698     Arc::new(impl_datum)
 699 }
 700
 701 pub(crate) fn associated_ty_value_query(
 702     db: &dyn HirDatabase,
 703     krate: CrateId,
 704     id: AssociatedTyValueId,
 705 ) -> Arc<AssociatedTyValue> {
 706     let type_alias: TypeAliasAsValue = from_chalk(db, id);
 707     type_alias_associated_ty_value(db, krate, type_alias.0)
 708 }
 709
 710 fn type_alias_associated_ty_value(
 711     db: &dyn HirDatabase,
 712     _krate: CrateId,
 713     type_alias: TypeAliasId,
 714 ) -> Arc<AssociatedTyValue> {
 715     let type_alias_data = db.type_alias_data(type_alias);
 716     let impl_id = match type_alias.lookup(db.upcast()).container {
 717         ItemContainerId::ImplId(it) => it,
 718         _ => panic!("assoc ty value should be in impl"),
 719     };
 720
 721     let trait_ref = db
 722         .impl_trait(impl_id)
 723         .expect("assoc ty value should not exist")
 724         .into_value_and_skipped_binders()
 725         .0; // we don't return any assoc ty values if the impl'd trait can't be resolved
 726
 727     let assoc_ty = db
 728         .trait_data(trait_ref.hir_trait_id())
 729         .associated_type_by_name(&type_alias_data.name)
 730         .expect("assoc ty value should not exist"); // validated when building the impl data as well
 731     let (ty, binders) = db.ty(type_alias.into()).into_value_and_skipped_binders();
 732     let value_bound = rust_ir::AssociatedTyValueBound { ty };
 733     let value = rust_ir::AssociatedTyValue {
 734         impl_id: impl_id.to_chalk(db),
 735         associated_ty_id: to_assoc_type_id(assoc_ty),
 736         value: chalk_ir::Binders::new(binders, value_bound),
 737     };
 738     Arc::new(value)
 739 }
 740
 741 pub(crate) fn fn_def_datum_query(
 742     db: &dyn HirDatabase,
 743     _krate: CrateId,
 744     fn_def_id: FnDefId,
 745 ) -> Arc<FnDefDatum> {
 746     let callable_def: CallableDefId = from_chalk(db, fn_def_id);
 747     let generic_params = generics(db.upcast(), callable_def.into());
 748     let (sig, binders) = db.callable_item_signature(callable_def).into_value_and_skipped_binders();
 749     let bound_vars = generic_params.bound_vars_subst(db, DebruijnIndex::INNERMOST);
 750     let where_clauses = convert_where_clauses(db, callable_def.into(), &bound_vars);
 751     let bound = rust_ir::FnDefDatumBound {
 752         // Note: Chalk doesn't actually use this information yet as far as I am aware, but we provide it anyway
 753         inputs_and_output: chalk_ir::Binders::empty(
 754             Interner,
 755             rust_ir::FnDefInputsAndOutputDatum {
 756                 argument_types: sig.params().to_vec(),
 757                 return_type: sig.ret().clone(),
 758             }
 759             .shifted_in(Interner),
 760         ),
 761         where_clauses,
 762     };
 763     let datum = FnDefDatum {
 764         id: fn_def_id,
 765         sig: chalk_ir::FnSig { abi: (), safety: chalk_ir::Safety::Safe, variadic: sig.is_varargs },
 766         binders: chalk_ir::Binders::new(binders, bound),
 767     };
 768     Arc::new(datum)
 769 }
 770
 771 pub(crate) fn fn_def_variance_query(db: &dyn HirDatabase, fn_def_id: FnDefId) -> Variances {
 772     let callable_def: CallableDefId = from_chalk(db, fn_def_id);
 773     let generic_params = generics(db.upcast(), callable_def.into());
 774     Variances::from_iter(
 775         Interner,
 776         std::iter::repeat(chalk_ir::Variance::Invariant).take(generic_params.len()),
 777     )
 778 }
 779
 780 pub(crate) fn adt_variance_query(
 781     db: &dyn HirDatabase,
 782     chalk_ir::AdtId(adt_id): AdtId,
 783 ) -> Variances {
 784     let generic_params = generics(db.upcast(), adt_id.into());
 785     Variances::from_iter(
 786         Interner,
 787         std::iter::repeat(chalk_ir::Variance::Invariant).take(generic_params.len()),
 788     )
 789 }
 790
 791 pub(super) fn convert_where_clauses(
 792     db: &dyn HirDatabase,
 793     def: GenericDefId,
 794     substs: &Substitution,
 795 ) -> Vec<chalk_ir::QuantifiedWhereClause<Interner>> {
 796     let generic_predicates = db.generic_predicates(def);
 797     let mut result = Vec::with_capacity(generic_predicates.len());
 798     for pred in generic_predicates.iter() {
 799         result.push(pred.clone().substitute(Interner, substs));
 800     }
 801     result
 802 }
 803
 804 pub(super) fn generic_predicate_to_inline_bound(
 805     db: &dyn HirDatabase,
 806     pred: &QuantifiedWhereClause,
 807     self_ty: &Ty,
 808 ) -> Option<chalk_ir::Binders<rust_ir::InlineBound<Interner>>> {
 809     // An InlineBound is like a GenericPredicate, except the self type is left out.
 810     // We don't have a special type for this, but Chalk does.
 811     let self_ty_shifted_in = self_ty.clone().shifted_in_from(Interner, DebruijnIndex::ONE);
 812     let (pred, binders) = pred.as_ref().into_value_and_skipped_binders();
 813     match pred {
 814         WhereClause::Implemented(trait_ref) => {
 815             if trait_ref.self_type_parameter(Interner) != self_ty_shifted_in {
 816                 // we can only convert predicates back to type bounds if they
 817                 // have the expected self type
 818                 return None;
 819             }
 820             let args_no_self = trait_ref.substitution.as_slice(Interner)[1..]
 821                 .iter()
 822                 .map(|ty| ty.clone().cast(Interner))
 823                 .collect();
 824             let trait_bound = rust_ir::TraitBound { trait_id: trait_ref.trait_id, args_no_self };
 825             Some(chalk_ir::Binders::new(binders, rust_ir::InlineBound::TraitBound(trait_bound)))
 826         }
 827         WhereClause::AliasEq(AliasEq { alias: AliasTy::Projection(projection_ty), ty }) => {
 828             let trait_ = projection_ty.trait_(db);
 829             if projection_ty.self_type_parameter(db) != self_ty_shifted_in {
 830                 return None;
 831             }
 832             let args_no_self = projection_ty.substitution.as_slice(Interner)[1..]
 833                 .iter()
 834                 .map(|ty| ty.clone().cast(Interner))
 835                 .collect();
 836             let alias_eq_bound = rust_ir::AliasEqBound {
 837                 value: ty.clone(),
 838                 trait_bound: rust_ir::TraitBound {
 839                     trait_id: to_chalk_trait_id(trait_),
 840                     args_no_self,
 841                 },
 842                 associated_ty_id: projection_ty.associated_ty_id,
 843                 parameters: Vec::new(), // FIXME we don't support generic associated types yet
 844             };
 845             Some(chalk_ir::Binders::new(
 846                 binders,
 847                 rust_ir::InlineBound::AliasEqBound(alias_eq_bound),
 848             ))
 849         }
 850         _ => None,
 851     }
 852 }