compiler/rustc_traits/src/chalk/db.rs

   1 //! Provides the `RustIrDatabase` implementation for `chalk-solve`
   2 //!
   3 //! The purpose of the `chalk_solve::RustIrDatabase` is to get data about
   4 //! specific types, such as bounds, where clauses, or fields. This file contains
   5 //! the minimal logic to assemble the types for `chalk-solve` by calling out to
   6 //! either the `TyCtxt` (for information about types) or
   7 //! `crate::chalk::lowering` (to lower rustc types into Chalk types).
   8
   9 use rustc_middle::traits::ChalkRustInterner as RustInterner;
  10 use rustc_middle::ty::{self, AssocKind, Ty, TyCtxt, TypeFoldable, TypeSuperFoldable};
  11 use rustc_middle::ty::{InternalSubsts, SubstsRef};
  12 use rustc_target::abi::{Integer, IntegerType};
  13
  14 use rustc_ast::ast;
  15
  16 use rustc_hir::def_id::DefId;
  17
  18 use rustc_span::symbol::sym;
  19
  20 use std::fmt;
  21 use std::sync::Arc;
  22
  23 use crate::chalk::lowering::LowerInto;
  24
  25 pub struct RustIrDatabase<'tcx> {
  26     pub(crate) interner: RustInterner<'tcx>,
  27 }
  28
  29 impl fmt::Debug for RustIrDatabase<'_> {
  30     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  31         write!(f, "RustIrDatabase")
  32     }
  33 }
  34
  35 impl<'tcx> RustIrDatabase<'tcx> {
  36     fn where_clauses_for(
  37         &self,
  38         def_id: DefId,
  39         bound_vars: SubstsRef<'tcx>,
  40     ) -> Vec<chalk_ir::QuantifiedWhereClause<RustInterner<'tcx>>> {
  41         self.interner
  42             .tcx
  43             .predicates_defined_on(def_id)
  44             .instantiate_own(self.interner.tcx, bound_vars)
  45             .filter_map(|(wc, _)| LowerInto::lower_into(wc, self.interner))
  46             .collect()
  47     }
  48
  49     fn bounds_for<T>(&self, def_id: DefId, bound_vars: SubstsRef<'tcx>) -> Vec<T>
  50     where
  51         ty::Predicate<'tcx>: LowerInto<'tcx, std::option::Option<T>>,
  52     {
  53         let bounds = self.interner.tcx.bound_explicit_item_bounds(def_id);
  54         bounds
  55             .0
  56             .iter()
  57             .map(|(bound, _)| bounds.rebind(*bound).subst(self.interner.tcx, &bound_vars))
  58             .filter_map(|bound| LowerInto::<Option<_>>::lower_into(bound, self.interner))
  59             .collect()
  60     }
  61 }
  62
  63 impl<'tcx> chalk_solve::RustIrDatabase<RustInterner<'tcx>> for RustIrDatabase<'tcx> {
  64     fn interner(&self) -> RustInterner<'tcx> {
  65         self.interner
  66     }
  67
  68     fn associated_ty_data(
  69         &self,
  70         assoc_type_id: chalk_ir::AssocTypeId<RustInterner<'tcx>>,
  71     ) -> Arc<chalk_solve::rust_ir::AssociatedTyDatum<RustInterner<'tcx>>> {
  72         let def_id = assoc_type_id.0;
  73         let assoc_item = self.interner.tcx.associated_item(def_id);
  74         let Some(trait_def_id) = assoc_item.trait_container(self.interner.tcx) else {
  75             unimplemented!("Not possible??");
  76         };
  77         match assoc_item.kind {
  78             AssocKind::Type => {}
  79             _ => unimplemented!("Not possible??"),
  80         }
  81         let bound_vars = bound_vars_for_item(self.interner.tcx, def_id);
  82         let binders = binders_for(self.interner, bound_vars);
  83
  84         let where_clauses = self.where_clauses_for(def_id, bound_vars);
  85         let bounds = self.bounds_for(def_id, bound_vars);
  86
  87         Arc::new(chalk_solve::rust_ir::AssociatedTyDatum {
  88             trait_id: chalk_ir::TraitId(trait_def_id),
  89             id: assoc_type_id,
  90             name: (),
  91             binders: chalk_ir::Binders::new(
  92                 binders,
  93                 chalk_solve::rust_ir::AssociatedTyDatumBound { bounds, where_clauses },
  94             ),
  95         })
  96     }
  97
  98     fn trait_datum(
  99         &self,
 100         trait_id: chalk_ir::TraitId<RustInterner<'tcx>>,
 101     ) -> Arc<chalk_solve::rust_ir::TraitDatum<RustInterner<'tcx>>> {
 102         use chalk_solve::rust_ir::WellKnownTrait::*;
 103
 104         let def_id = trait_id.0;
 105         let trait_def = self.interner.tcx.trait_def(def_id);
 106
 107         let bound_vars = bound_vars_for_item(self.interner.tcx, def_id);
 108         let binders = binders_for(self.interner, bound_vars);
 109
 110         let where_clauses = self.where_clauses_for(def_id, bound_vars);
 111
 112         let associated_ty_ids: Vec<_> = self
 113             .interner
 114             .tcx
 115             .associated_items(def_id)
 116             .in_definition_order()
 117             .filter(|i| i.kind == AssocKind::Type)
 118             .map(|i| chalk_ir::AssocTypeId(i.def_id))
 119             .collect();
 120
 121         let lang_items = self.interner.tcx.lang_items();
 122         let well_known = if lang_items.sized_trait() == Some(def_id) {
 123             Some(Sized)
 124         } else if lang_items.copy_trait() == Some(def_id) {
 125             Some(Copy)
 126         } else if lang_items.clone_trait() == Some(def_id) {
 127             Some(Clone)
 128         } else if lang_items.drop_trait() == Some(def_id) {
 129             Some(Drop)
 130         } else if lang_items.fn_trait() == Some(def_id) {
 131             Some(Fn)
 132         } else if lang_items.fn_once_trait() == Some(def_id) {
 133             Some(FnOnce)
 134         } else if lang_items.fn_mut_trait() == Some(def_id) {
 135             Some(FnMut)
 136         } else if lang_items.unsize_trait() == Some(def_id) {
 137             Some(Unsize)
 138         } else if lang_items.unpin_trait() == Some(def_id) {
 139             Some(Unpin)
 140         } else if lang_items.coerce_unsized_trait() == Some(def_id) {
 141             Some(CoerceUnsized)
 142         } else if lang_items.dispatch_from_dyn_trait() == Some(def_id) {
 143             Some(DispatchFromDyn)
 144         } else if lang_items.tuple_trait() == Some(def_id) {
 145             Some(Tuple)
 146         } else {
 147             None
 148         };
 149         Arc::new(chalk_solve::rust_ir::TraitDatum {
 150             id: trait_id,
 151             binders: chalk_ir::Binders::new(
 152                 binders,
 153                 chalk_solve::rust_ir::TraitDatumBound { where_clauses },
 154             ),
 155             flags: chalk_solve::rust_ir::TraitFlags {
 156                 auto: trait_def.has_auto_impl,
 157                 marker: trait_def.is_marker,
 158                 upstream: !def_id.is_local(),
 159                 fundamental: self.interner.tcx.has_attr(def_id, sym::fundamental),
 160                 non_enumerable: true,
 161                 coinductive: false,
 162             },
 163             associated_ty_ids,
 164             well_known,
 165         })
 166     }
 167
 168     fn adt_datum(
 169         &self,
 170         adt_id: chalk_ir::AdtId<RustInterner<'tcx>>,
 171     ) -> Arc<chalk_solve::rust_ir::AdtDatum<RustInterner<'tcx>>> {
 172         let adt_def = adt_id.0;
 173
 174         let bound_vars = bound_vars_for_item(self.interner.tcx, adt_def.did());
 175         let binders = binders_for(self.interner, bound_vars);
 176
 177         let where_clauses = self.where_clauses_for(adt_def.did(), bound_vars);
 178
 179         let variants: Vec<_> = adt_def
 180             .variants()
 181             .iter()
 182             .map(|variant| chalk_solve::rust_ir::AdtVariantDatum {
 183                 fields: variant
 184                     .fields
 185                     .iter()
 186                     .map(|field| field.ty(self.interner.tcx, bound_vars).lower_into(self.interner))
 187                     .collect(),
 188             })
 189             .collect();
 190         Arc::new(chalk_solve::rust_ir::AdtDatum {
 191             id: adt_id,
 192             binders: chalk_ir::Binders::new(
 193                 binders,
 194                 chalk_solve::rust_ir::AdtDatumBound { variants, where_clauses },
 195             ),
 196             flags: chalk_solve::rust_ir::AdtFlags {
 197                 upstream: !adt_def.did().is_local(),
 198                 fundamental: adt_def.is_fundamental(),
 199                 phantom_data: adt_def.is_phantom_data(),
 200             },
 201             kind: match adt_def.adt_kind() {
 202                 ty::AdtKind::Struct => chalk_solve::rust_ir::AdtKind::Struct,
 203                 ty::AdtKind::Union => chalk_solve::rust_ir::AdtKind::Union,
 204                 ty::AdtKind::Enum => chalk_solve::rust_ir::AdtKind::Enum,
 205             },
 206         })
 207     }
 208
 209     fn adt_repr(
 210         &self,
 211         adt_id: chalk_ir::AdtId<RustInterner<'tcx>>,
 212     ) -> Arc<chalk_solve::rust_ir::AdtRepr<RustInterner<'tcx>>> {
 213         let adt_def = adt_id.0;
 214         let int = |i| chalk_ir::TyKind::Scalar(chalk_ir::Scalar::Int(i)).intern(self.interner);
 215         let uint = |i| chalk_ir::TyKind::Scalar(chalk_ir::Scalar::Uint(i)).intern(self.interner);
 216         Arc::new(chalk_solve::rust_ir::AdtRepr {
 217             c: adt_def.repr().c(),
 218             packed: adt_def.repr().packed(),
 219             int: adt_def.repr().int.map(|i| match i {
 220                 IntegerType::Pointer(true) => int(chalk_ir::IntTy::Isize),
 221                 IntegerType::Pointer(false) => uint(chalk_ir::UintTy::Usize),
 222                 IntegerType::Fixed(i, true) => match i {
 223                     Integer::I8 => int(chalk_ir::IntTy::I8),
 224                     Integer::I16 => int(chalk_ir::IntTy::I16),
 225                     Integer::I32 => int(chalk_ir::IntTy::I32),
 226                     Integer::I64 => int(chalk_ir::IntTy::I64),
 227                     Integer::I128 => int(chalk_ir::IntTy::I128),
 228                 },
 229                 IntegerType::Fixed(i, false) => match i {
 230                     Integer::I8 => uint(chalk_ir::UintTy::U8),
 231                     Integer::I16 => uint(chalk_ir::UintTy::U16),
 232                     Integer::I32 => uint(chalk_ir::UintTy::U32),
 233                     Integer::I64 => uint(chalk_ir::UintTy::U64),
 234                     Integer::I128 => uint(chalk_ir::UintTy::U128),
 235                 },
 236             }),
 237         })
 238     }
 239
 240     fn adt_size_align(
 241         &self,
 242         adt_id: chalk_ir::AdtId<RustInterner<'tcx>>,
 243     ) -> Arc<chalk_solve::rust_ir::AdtSizeAlign> {
 244         let tcx = self.interner.tcx;
 245         let did = adt_id.0.did();
 246
 247         // Grab the ADT and the param we might need to calculate its layout
 248         let param_env = tcx.param_env(did);
 249         let adt_ty = tcx.type_of(did);
 250
 251         // The ADT is a 1-zst if it's a ZST and its alignment is 1.
 252         // Mark the ADT as _not_ a 1-zst if there was a layout error.
 253         let one_zst = if let Ok(layout) = tcx.layout_of(param_env.and(adt_ty)) {
 254             layout.is_zst() && layout.align.abi.bytes() == 1
 255         } else {
 256             false
 257         };
 258
 259         Arc::new(chalk_solve::rust_ir::AdtSizeAlign::from_one_zst(one_zst))
 260     }
 261
 262     fn fn_def_datum(
 263         &self,
 264         fn_def_id: chalk_ir::FnDefId<RustInterner<'tcx>>,
 265     ) -> Arc<chalk_solve::rust_ir::FnDefDatum<RustInterner<'tcx>>> {
 266         let def_id = fn_def_id.0;
 267         let bound_vars = bound_vars_for_item(self.interner.tcx, def_id);
 268         let binders = binders_for(self.interner, bound_vars);
 269
 270         let where_clauses = self.where_clauses_for(def_id, bound_vars);
 271
 272         let sig = self.interner.tcx.fn_sig(def_id);
 273         let (inputs_and_output, iobinders, _) = crate::chalk::lowering::collect_bound_vars(
 274             self.interner,
 275             self.interner.tcx,
 276             sig.map_bound(|s| s.inputs_and_output()).subst(self.interner.tcx, bound_vars),
 277         );
 278
 279         let argument_types = inputs_and_output[..inputs_and_output.len() - 1]
 280             .iter()
 281             .map(|t| sig.rebind(*t).subst(self.interner.tcx, &bound_vars).lower_into(self.interner))
 282             .collect();
 283
 284         let return_type = sig
 285             .rebind(inputs_and_output[inputs_and_output.len() - 1])
 286             .subst(self.interner.tcx, &bound_vars)
 287             .lower_into(self.interner);
 288
 289         let bound = chalk_solve::rust_ir::FnDefDatumBound {
 290             inputs_and_output: chalk_ir::Binders::new(
 291                 iobinders,
 292                 chalk_solve::rust_ir::FnDefInputsAndOutputDatum { argument_types, return_type },
 293             ),
 294             where_clauses,
 295         };
 296         Arc::new(chalk_solve::rust_ir::FnDefDatum {
 297             id: fn_def_id,
 298             sig: sig.0.lower_into(self.interner),
 299             binders: chalk_ir::Binders::new(binders, bound),
 300         })
 301     }
 302
 303     fn impl_datum(
 304         &self,
 305         impl_id: chalk_ir::ImplId<RustInterner<'tcx>>,
 306     ) -> Arc<chalk_solve::rust_ir::ImplDatum<RustInterner<'tcx>>> {
 307         let def_id = impl_id.0;
 308         let bound_vars = bound_vars_for_item(self.interner.tcx, def_id);
 309         let binders = binders_for(self.interner, bound_vars);
 310
 311         let trait_ref = self.interner.tcx.impl_trait_ref(def_id).expect("not an impl");
 312         let trait_ref = trait_ref.subst(self.interner.tcx, bound_vars);
 313
 314         let where_clauses = self.where_clauses_for(def_id, bound_vars);
 315
 316         let value = chalk_solve::rust_ir::ImplDatumBound {
 317             trait_ref: trait_ref.lower_into(self.interner),
 318             where_clauses,
 319         };
 320
 321         let associated_ty_value_ids: Vec<_> = self
 322             .interner
 323             .tcx
 324             .associated_items(def_id)
 325             .in_definition_order()
 326             .filter(|i| i.kind == AssocKind::Type)
 327             .map(|i| chalk_solve::rust_ir::AssociatedTyValueId(i.def_id))
 328             .collect();
 329
 330         Arc::new(chalk_solve::rust_ir::ImplDatum {
 331             polarity: self.interner.tcx.impl_polarity(def_id).lower_into(self.interner),
 332             binders: chalk_ir::Binders::new(binders, value),
 333             impl_type: chalk_solve::rust_ir::ImplType::Local,
 334             associated_ty_value_ids,
 335         })
 336     }
 337
 338     fn impls_for_trait(
 339         &self,
 340         trait_id: chalk_ir::TraitId<RustInterner<'tcx>>,
 341         parameters: &[chalk_ir::GenericArg<RustInterner<'tcx>>],
 342         _binders: &chalk_ir::CanonicalVarKinds<RustInterner<'tcx>>,
 343     ) -> Vec<chalk_ir::ImplId<RustInterner<'tcx>>> {
 344         let def_id = trait_id.0;
 345
 346         // FIXME(chalk): use TraitDef::for_each_relevant_impl, but that will
 347         // require us to be able to interconvert `Ty<'tcx>`, and we're
 348         // not there yet.
 349
 350         let all_impls = self.interner.tcx.all_impls(def_id);
 351         let matched_impls = all_impls.filter(|impl_def_id| {
 352             use chalk_ir::could_match::CouldMatch;
 353             let trait_ref = self.interner.tcx.impl_trait_ref(*impl_def_id).unwrap();
 354             let bound_vars = bound_vars_for_item(self.interner.tcx, *impl_def_id);
 355
 356             let self_ty = trait_ref.map_bound(|t| t.self_ty());
 357             let self_ty = self_ty.subst(self.interner.tcx, bound_vars);
 358             let lowered_ty = self_ty.lower_into(self.interner);
 359
 360             parameters[0].assert_ty_ref(self.interner).could_match(
 361                 self.interner,
 362                 self.unification_database(),
 363                 &lowered_ty,
 364             )
 365         });
 366
 367         let impls = matched_impls.map(chalk_ir::ImplId).collect();
 368         impls
 369     }
 370
 371     fn impl_provided_for(
 372         &self,
 373         auto_trait_id: chalk_ir::TraitId<RustInterner<'tcx>>,
 374         chalk_ty: &chalk_ir::TyKind<RustInterner<'tcx>>,
 375     ) -> bool {
 376         use chalk_ir::Scalar::*;
 377         use chalk_ir::TyKind::*;
 378
 379         let trait_def_id = auto_trait_id.0;
 380         let all_impls = self.interner.tcx.all_impls(trait_def_id);
 381         for impl_def_id in all_impls {
 382             let trait_ref = self.interner.tcx.impl_trait_ref(impl_def_id).unwrap().subst_identity();
 383             let self_ty = trait_ref.self_ty();
 384             let provides = match (self_ty.kind(), chalk_ty) {
 385                 (&ty::Adt(impl_adt_def, ..), Adt(id, ..)) => impl_adt_def.did() == id.0.did(),
 386                 (_, AssociatedType(_ty_id, ..)) => {
 387                     // FIXME(chalk): See https://github.com/rust-lang/rust/pull/77152#discussion_r494484774
 388                     false
 389                 }
 390                 (ty::Bool, Scalar(Bool)) => true,
 391                 (ty::Char, Scalar(Char)) => true,
 392                 (ty::Int(ty1), Scalar(Int(ty2))) => matches!(
 393                     (ty1, ty2),
 394                     (ty::IntTy::Isize, chalk_ir::IntTy::Isize)
 395                         | (ty::IntTy::I8, chalk_ir::IntTy::I8)
 396                         | (ty::IntTy::I16, chalk_ir::IntTy::I16)
 397                         | (ty::IntTy::I32, chalk_ir::IntTy::I32)
 398                         | (ty::IntTy::I64, chalk_ir::IntTy::I64)
 399                         | (ty::IntTy::I128, chalk_ir::IntTy::I128)
 400                 ),
 401                 (ty::Uint(ty1), Scalar(Uint(ty2))) => matches!(
 402                     (ty1, ty2),
 403                     (ty::UintTy::Usize, chalk_ir::UintTy::Usize)
 404                         | (ty::UintTy::U8, chalk_ir::UintTy::U8)
 405                         | (ty::UintTy::U16, chalk_ir::UintTy::U16)
 406                         | (ty::UintTy::U32, chalk_ir::UintTy::U32)
 407                         | (ty::UintTy::U64, chalk_ir::UintTy::U64)
 408                         | (ty::UintTy::U128, chalk_ir::UintTy::U128)
 409                 ),
 410                 (ty::Float(ty1), Scalar(Float(ty2))) => matches!(
 411                     (ty1, ty2),
 412                     (ty::FloatTy::F32, chalk_ir::FloatTy::F32)
 413                         | (ty::FloatTy::F64, chalk_ir::FloatTy::F64)
 414                 ),
 415                 (&ty::Tuple(substs), Tuple(len, _)) => substs.len() == *len,
 416                 (&ty::Array(..), Array(..)) => true,
 417                 (&ty::Slice(..), Slice(..)) => true,
 418                 (&ty::RawPtr(type_and_mut), Raw(mutability, _)) => {
 419                     match (type_and_mut.mutbl, mutability) {
 420                         (ast::Mutability::Mut, chalk_ir::Mutability::Mut) => true,
 421                         (ast::Mutability::Mut, chalk_ir::Mutability::Not) => false,
 422                         (ast::Mutability::Not, chalk_ir::Mutability::Mut) => false,
 423                         (ast::Mutability::Not, chalk_ir::Mutability::Not) => true,
 424                     }
 425                 }
 426                 (&ty::Ref(.., mutability1), Ref(mutability2, ..)) => {
 427                     match (mutability1, mutability2) {
 428                         (ast::Mutability::Mut, chalk_ir::Mutability::Mut) => true,
 429                         (ast::Mutability::Mut, chalk_ir::Mutability::Not) => false,
 430                         (ast::Mutability::Not, chalk_ir::Mutability::Mut) => false,
 431                         (ast::Mutability::Not, chalk_ir::Mutability::Not) => true,
 432                     }
 433                 }
 434                 (
 435                     &ty::Alias(ty::Opaque, ty::AliasTy { def_id, .. }),
 436                     OpaqueType(opaque_ty_id, ..),
 437                 ) => def_id == opaque_ty_id.0,
 438                 (&ty::FnDef(def_id, ..), FnDef(fn_def_id, ..)) => def_id == fn_def_id.0,
 439                 (&ty::Str, Str) => true,
 440                 (&ty::Never, Never) => true,
 441                 (&ty::Closure(def_id, ..), Closure(closure_id, _)) => def_id == closure_id.0,
 442                 (&ty::Foreign(def_id), Foreign(foreign_def_id)) => def_id == foreign_def_id.0,
 443                 (&ty::Error(..), Error) => false,
 444                 _ => false,
 445             };
 446             if provides {
 447                 return true;
 448             }
 449         }
 450         false
 451     }
 452
 453     fn associated_ty_value(
 454         &self,
 455         associated_ty_id: chalk_solve::rust_ir::AssociatedTyValueId<RustInterner<'tcx>>,
 456     ) -> Arc<chalk_solve::rust_ir::AssociatedTyValue<RustInterner<'tcx>>> {
 457         let def_id = associated_ty_id.0;
 458         let assoc_item = self.interner.tcx.associated_item(def_id);
 459         let impl_id = assoc_item.container_id(self.interner.tcx);
 460         match assoc_item.kind {
 461             AssocKind::Type => {}
 462             _ => unimplemented!("Not possible??"),
 463         }
 464
 465         let trait_item_id = assoc_item.trait_item_def_id.expect("assoc_ty with no trait version");
 466         let bound_vars = bound_vars_for_item(self.interner.tcx, def_id);
 467         let binders = binders_for(self.interner, bound_vars);
 468         let ty = self
 469             .interner
 470             .tcx
 471             .bound_type_of(def_id)
 472             .subst(self.interner.tcx, bound_vars)
 473             .lower_into(self.interner);
 474
 475         Arc::new(chalk_solve::rust_ir::AssociatedTyValue {
 476             impl_id: chalk_ir::ImplId(impl_id),
 477             associated_ty_id: chalk_ir::AssocTypeId(trait_item_id),
 478             value: chalk_ir::Binders::new(
 479                 binders,
 480                 chalk_solve::rust_ir::AssociatedTyValueBound { ty },
 481             ),
 482         })
 483     }
 484
 485     fn custom_clauses(&self) -> Vec<chalk_ir::ProgramClause<RustInterner<'tcx>>> {
 486         vec![]
 487     }
 488
 489     fn local_impls_to_coherence_check(
 490         &self,
 491         _trait_id: chalk_ir::TraitId<RustInterner<'tcx>>,
 492     ) -> Vec<chalk_ir::ImplId<RustInterner<'tcx>>> {
 493         unimplemented!()
 494     }
 495
 496     fn opaque_ty_data(
 497         &self,
 498         opaque_ty_id: chalk_ir::OpaqueTyId<RustInterner<'tcx>>,
 499     ) -> Arc<chalk_solve::rust_ir::OpaqueTyDatum<RustInterner<'tcx>>> {
 500         let bound_vars = ty::fold::shift_vars(
 501             self.interner.tcx,
 502             bound_vars_for_item(self.interner.tcx, opaque_ty_id.0),
 503             1,
 504         );
 505         let where_clauses = self.where_clauses_for(opaque_ty_id.0, bound_vars);
 506
 507         let identity_substs = InternalSubsts::identity_for_item(self.interner.tcx, opaque_ty_id.0);
 508
 509         let explicit_item_bounds = self.interner.tcx.bound_explicit_item_bounds(opaque_ty_id.0);
 510         let bounds =
 511             explicit_item_bounds
 512                 .0
 513                 .iter()
 514                 .map(|(bound, _)| {
 515                     explicit_item_bounds.rebind(*bound).subst(self.interner.tcx, &bound_vars)
 516                 })
 517                 .map(|bound| {
 518                     bound.fold_with(&mut ReplaceOpaqueTyFolder {
 519                         tcx: self.interner.tcx,
 520                         opaque_ty_id,
 521                         identity_substs,
 522                         binder_index: ty::INNERMOST,
 523                     })
 524                 })
 525                 .filter_map(|bound| {
 526                     LowerInto::<
 527                     Option<chalk_ir::QuantifiedWhereClause<RustInterner<'tcx>>>
 528                 >::lower_into(bound, self.interner)
 529                 })
 530                 .collect();
 531
 532         // Binder for the bound variable representing the concrete impl Trait type.
 533         let existential_binder = chalk_ir::VariableKinds::from1(
 534             self.interner,
 535             chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General),
 536         );
 537
 538         let value = chalk_solve::rust_ir::OpaqueTyDatumBound {
 539             bounds: chalk_ir::Binders::new(existential_binder.clone(), bounds),
 540             where_clauses: chalk_ir::Binders::new(existential_binder, where_clauses),
 541         };
 542
 543         let binders = binders_for(self.interner, bound_vars);
 544         Arc::new(chalk_solve::rust_ir::OpaqueTyDatum {
 545             opaque_ty_id,
 546             bound: chalk_ir::Binders::new(binders, value),
 547         })
 548     }
 549
 550     fn program_clauses_for_env(
 551         &self,
 552         environment: &chalk_ir::Environment<RustInterner<'tcx>>,
 553     ) -> chalk_ir::ProgramClauses<RustInterner<'tcx>> {
 554         chalk_solve::program_clauses_for_env(self, environment)
 555     }
 556
 557     fn well_known_trait_id(
 558         &self,
 559         well_known_trait: chalk_solve::rust_ir::WellKnownTrait,
 560     ) -> Option<chalk_ir::TraitId<RustInterner<'tcx>>> {
 561         use chalk_solve::rust_ir::WellKnownTrait::*;
 562         let lang_items = self.interner.tcx.lang_items();
 563         let def_id = match well_known_trait {
 564             Sized => lang_items.sized_trait(),
 565             Copy => lang_items.copy_trait(),
 566             Clone => lang_items.clone_trait(),
 567             Drop => lang_items.drop_trait(),
 568             Fn => lang_items.fn_trait(),
 569             FnMut => lang_items.fn_mut_trait(),
 570             FnOnce => lang_items.fn_once_trait(),
 571             Generator => lang_items.gen_trait(),
 572             Unsize => lang_items.unsize_trait(),
 573             Unpin => lang_items.unpin_trait(),
 574             CoerceUnsized => lang_items.coerce_unsized_trait(),
 575             DiscriminantKind => lang_items.discriminant_kind_trait(),
 576             DispatchFromDyn => lang_items.dispatch_from_dyn_trait(),
 577             Tuple => lang_items.tuple_trait(),
 578         };
 579         def_id.map(chalk_ir::TraitId)
 580     }
 581
 582     fn is_object_safe(&self, trait_id: chalk_ir::TraitId<RustInterner<'tcx>>) -> bool {
 583         self.interner.tcx.check_is_object_safe(trait_id.0)
 584     }
 585
 586     fn hidden_opaque_type(
 587         &self,
 588         _id: chalk_ir::OpaqueTyId<RustInterner<'tcx>>,
 589     ) -> chalk_ir::Ty<RustInterner<'tcx>> {
 590         // FIXME(chalk): actually get hidden ty
 591         self.interner
 592             .tcx
 593             .mk_ty(ty::Tuple(self.interner.tcx.intern_type_list(&[])))
 594             .lower_into(self.interner)
 595     }
 596
 597     fn closure_kind(
 598         &self,
 599         _closure_id: chalk_ir::ClosureId<RustInterner<'tcx>>,
 600         substs: &chalk_ir::Substitution<RustInterner<'tcx>>,
 601     ) -> chalk_solve::rust_ir::ClosureKind {
 602         let kind = &substs.as_slice(self.interner)[substs.len(self.interner) - 3];
 603         match kind.assert_ty_ref(self.interner).kind(self.interner) {
 604             chalk_ir::TyKind::Scalar(chalk_ir::Scalar::Int(int_ty)) => match int_ty {
 605                 chalk_ir::IntTy::I8 => chalk_solve::rust_ir::ClosureKind::Fn,
 606                 chalk_ir::IntTy::I16 => chalk_solve::rust_ir::ClosureKind::FnMut,
 607                 chalk_ir::IntTy::I32 => chalk_solve::rust_ir::ClosureKind::FnOnce,
 608                 _ => bug!("bad closure kind"),
 609             },
 610             _ => bug!("bad closure kind"),
 611         }
 612     }
 613
 614     fn closure_inputs_and_output(
 615         &self,
 616         _closure_id: chalk_ir::ClosureId<RustInterner<'tcx>>,
 617         substs: &chalk_ir::Substitution<RustInterner<'tcx>>,
 618     ) -> chalk_ir::Binders<chalk_solve::rust_ir::FnDefInputsAndOutputDatum<RustInterner<'tcx>>>
 619     {
 620         let sig = &substs.as_slice(self.interner)[substs.len(self.interner) - 2];
 621         match sig.assert_ty_ref(self.interner).kind(self.interner) {
 622             chalk_ir::TyKind::Function(f) => {
 623                 let substitution = f.substitution.0.as_slice(self.interner);
 624                 let return_type = substitution.last().unwrap().assert_ty_ref(self.interner).clone();
 625                 // Closure arguments are tupled
 626                 let argument_tuple = substitution[0].assert_ty_ref(self.interner);
 627                 let argument_types = match argument_tuple.kind(self.interner) {
 628                     chalk_ir::TyKind::Tuple(_len, substitution) => substitution
 629                         .iter(self.interner)
 630                         .map(|arg| arg.assert_ty_ref(self.interner))
 631                         .cloned()
 632                         .collect(),
 633                     _ => bug!("Expecting closure FnSig args to be tupled."),
 634                 };
 635
 636                 chalk_ir::Binders::new(
 637                     chalk_ir::VariableKinds::from_iter(
 638                         self.interner,
 639                         (0..f.num_binders).map(|_| chalk_ir::VariableKind::Lifetime),
 640                     ),
 641                     chalk_solve::rust_ir::FnDefInputsAndOutputDatum { argument_types, return_type },
 642                 )
 643             }
 644             _ => panic!("Invalid sig."),
 645         }
 646     }
 647
 648     fn closure_upvars(
 649         &self,
 650         _closure_id: chalk_ir::ClosureId<RustInterner<'tcx>>,
 651         substs: &chalk_ir::Substitution<RustInterner<'tcx>>,
 652     ) -> chalk_ir::Binders<chalk_ir::Ty<RustInterner<'tcx>>> {
 653         let inputs_and_output = self.closure_inputs_and_output(_closure_id, substs);
 654         let tuple = substs.as_slice(self.interner).last().unwrap().assert_ty_ref(self.interner);
 655         inputs_and_output.map_ref(|_| tuple.clone())
 656     }
 657
 658     fn closure_fn_substitution(
 659         &self,
 660         _closure_id: chalk_ir::ClosureId<RustInterner<'tcx>>,
 661         substs: &chalk_ir::Substitution<RustInterner<'tcx>>,
 662     ) -> chalk_ir::Substitution<RustInterner<'tcx>> {
 663         let substitution = &substs.as_slice(self.interner)[0..substs.len(self.interner) - 3];
 664         chalk_ir::Substitution::from_iter(self.interner, substitution)
 665     }
 666
 667     fn generator_datum(
 668         &self,
 669         _generator_id: chalk_ir::GeneratorId<RustInterner<'tcx>>,
 670     ) -> Arc<chalk_solve::rust_ir::GeneratorDatum<RustInterner<'tcx>>> {
 671         unimplemented!()
 672     }
 673
 674     fn generator_witness_datum(
 675         &self,
 676         _generator_id: chalk_ir::GeneratorId<RustInterner<'tcx>>,
 677     ) -> Arc<chalk_solve::rust_ir::GeneratorWitnessDatum<RustInterner<'tcx>>> {
 678         unimplemented!()
 679     }
 680
 681     fn unification_database(&self) -> &dyn chalk_ir::UnificationDatabase<RustInterner<'tcx>> {
 682         self
 683     }
 684
 685     fn discriminant_type(
 686         &self,
 687         _: chalk_ir::Ty<RustInterner<'tcx>>,
 688     ) -> chalk_ir::Ty<RustInterner<'tcx>> {
 689         unimplemented!()
 690     }
 691 }
 692
 693 impl<'tcx> chalk_ir::UnificationDatabase<RustInterner<'tcx>> for RustIrDatabase<'tcx> {
 694     fn fn_def_variance(
 695         &self,
 696         def_id: chalk_ir::FnDefId<RustInterner<'tcx>>,
 697     ) -> chalk_ir::Variances<RustInterner<'tcx>> {
 698         let variances = self.interner.tcx.variances_of(def_id.0);
 699         chalk_ir::Variances::from_iter(
 700             self.interner,
 701             variances.iter().map(|v| v.lower_into(self.interner)),
 702         )
 703     }
 704
 705     fn adt_variance(
 706         &self,
 707         adt_id: chalk_ir::AdtId<RustInterner<'tcx>>,
 708     ) -> chalk_ir::Variances<RustInterner<'tcx>> {
 709         let variances = self.interner.tcx.variances_of(adt_id.0.did());
 710         chalk_ir::Variances::from_iter(
 711             self.interner,
 712             variances.iter().map(|v| v.lower_into(self.interner)),
 713         )
 714     }
 715 }
 716
 717 /// Creates an `InternalSubsts` that maps each generic parameter to a higher-ranked
 718 /// var bound at index `0`. For types, we use a `BoundVar` index equal to
 719 /// the type parameter index. For regions, we use the `BoundRegionKind::BrNamed`
 720 /// variant (which has a `DefId`).
 721 fn bound_vars_for_item(tcx: TyCtxt<'_>, def_id: DefId) -> SubstsRef<'_> {
 722     InternalSubsts::for_item(tcx, def_id, |param, substs| match param.kind {
 723         ty::GenericParamDefKind::Type { .. } => tcx
 724             .mk_ty(ty::Bound(
 725                 ty::INNERMOST,
 726                 ty::BoundTy {
 727                     var: ty::BoundVar::from(param.index),
 728                     kind: ty::BoundTyKind::Param(param.name),
 729                 },
 730             ))
 731             .into(),
 732
 733         ty::GenericParamDefKind::Lifetime => {
 734             let br = ty::BoundRegion {
 735                 var: ty::BoundVar::from_usize(substs.len()),
 736                 kind: ty::BrAnon(substs.len() as u32, None),
 737             };
 738             tcx.mk_region(ty::ReLateBound(ty::INNERMOST, br)).into()
 739         }
 740
 741         ty::GenericParamDefKind::Const { .. } => tcx
 742             .mk_const(
 743                 ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from(param.index)),
 744                 tcx.type_of(param.def_id),
 745             )
 746             .into(),
 747     })
 748 }
 749
 750 fn binders_for<'tcx>(
 751     interner: RustInterner<'tcx>,
 752     bound_vars: SubstsRef<'tcx>,
 753 ) -> chalk_ir::VariableKinds<RustInterner<'tcx>> {
 754     chalk_ir::VariableKinds::from_iter(
 755         interner,
 756         bound_vars.iter().map(|arg| match arg.unpack() {
 757             ty::subst::GenericArgKind::Lifetime(_re) => chalk_ir::VariableKind::Lifetime,
 758             ty::subst::GenericArgKind::Type(_ty) => {
 759                 chalk_ir::VariableKind::Ty(chalk_ir::TyVariableKind::General)
 760             }
 761             ty::subst::GenericArgKind::Const(c) => {
 762                 chalk_ir::VariableKind::Const(c.ty().lower_into(interner))
 763             }
 764         }),
 765     )
 766 }
 767
 768 struct ReplaceOpaqueTyFolder<'tcx> {
 769     tcx: TyCtxt<'tcx>,
 770     opaque_ty_id: chalk_ir::OpaqueTyId<RustInterner<'tcx>>,
 771     identity_substs: SubstsRef<'tcx>,
 772     binder_index: ty::DebruijnIndex,
 773 }
 774
 775 impl<'tcx> ty::TypeFolder<'tcx> for ReplaceOpaqueTyFolder<'tcx> {
 776     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 777         self.tcx
 778     }
 779
 780     fn fold_binder<T: TypeFoldable<'tcx>>(
 781         &mut self,
 782         t: ty::Binder<'tcx, T>,
 783     ) -> ty::Binder<'tcx, T> {
 784         self.binder_index.shift_in(1);
 785         let t = t.super_fold_with(self);
 786         self.binder_index.shift_out(1);
 787         t
 788     }
 789
 790     fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> {
 791         if let ty::Alias(ty::Opaque, ty::AliasTy { def_id, substs, .. }) = *ty.kind() {
 792             if def_id == self.opaque_ty_id.0 && substs == self.identity_substs {
 793                 return self.tcx.mk_ty(ty::Bound(
 794                     self.binder_index,
 795                     ty::BoundTy::from(ty::BoundVar::from_u32(0)),
 796                 ));
 797             }
 798         }
 799         ty
 800     }
 801 }