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