crates/ra_hir_ty/src/traits/chalk.rs

   1 //! Conversion code from/to Chalk.
   2 use std::{fmt, sync::Arc};
   3
   4 use log::debug;
   5
   6 use chalk_ir::{
   7     cast::Cast, fold::shift::Shift, interner::HasInterner, GenericArg, Goal, GoalData,
   8     PlaceholderIndex, Scalar, TypeName, UniverseIndex,
   9 };
  10
  11 use hir_def::{
  12     lang_item::{lang_attr, LangItemTarget},
  13     type_ref::Mutability,
  14     AssocContainerId, AssocItemId, GenericDefId, HasModule, Lookup, TypeAliasId,
  15 };
  16 use ra_db::{
  17     salsa::{InternId, InternKey},
  18     CrateId,
  19 };
  20
  21 use super::{builtin, AssocTyValue, Canonical, ChalkContext, Impl, Obligation};
  22 use crate::{
  23     db::HirDatabase,
  24     display::HirDisplay,
  25     method_resolution::TyFingerprint,
  26     primitive::{FloatBitness, FloatTy, IntBitness, IntTy, Signedness, Uncertain},
  27     utils::generics,
  28     ApplicationTy, DebruijnIndex, GenericPredicate, ProjectionTy, Substs, TraitRef, Ty, TypeCtor,
  29 };
  30 use chalk_rust_ir::WellKnownTrait;
  31
  32 pub(super) mod tls;
  33
  34 #[derive(Debug, Copy, Clone, Hash, PartialOrd, Ord, PartialEq, Eq)]
  35 pub struct Interner;
  36
  37 impl chalk_ir::interner::Interner for Interner {
  38     type InternedType = Box<chalk_ir::TyData<Self>>; // FIXME use Arc?
  39     type InternedLifetime = chalk_ir::LifetimeData<Self>;
  40     type InternedConst = Arc<chalk_ir::ConstData<Self>>;
  41     type InternedConcreteConst = ();
  42     type InternedGenericArg = chalk_ir::GenericArgData<Self>;
  43     type InternedGoal = Arc<GoalData<Self>>;
  44     type InternedGoals = Vec<Goal<Self>>;
  45     type InternedSubstitution = Vec<GenericArg<Self>>;
  46     type InternedProgramClause = chalk_ir::ProgramClauseData<Self>;
  47     type InternedProgramClauses = Arc<[chalk_ir::ProgramClause<Self>]>;
  48     type InternedQuantifiedWhereClauses = Vec<chalk_ir::QuantifiedWhereClause<Self>>;
  49     type InternedVariableKinds = Vec<chalk_ir::VariableKind<Self>>;
  50     type InternedCanonicalVarKinds = Vec<chalk_ir::CanonicalVarKind<Self>>;
  51     type DefId = InternId;
  52     type InternedAdtId = InternId;
  53     type Identifier = TypeAliasId;
  54
  55     fn debug_adt_id(type_kind_id: StructId, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> {
  56         tls::with_current_program(|prog| Some(prog?.debug_struct_id(type_kind_id, fmt)))
  57     }
  58
  59     fn debug_trait_id(type_kind_id: TraitId, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> {
  60         tls::with_current_program(|prog| Some(prog?.debug_trait_id(type_kind_id, fmt)))
  61     }
  62
  63     fn debug_assoc_type_id(id: AssocTypeId, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> {
  64         tls::with_current_program(|prog| Some(prog?.debug_assoc_type_id(id, fmt)))
  65     }
  66
  67     fn debug_alias(
  68         alias: &chalk_ir::AliasTy<Interner>,
  69         fmt: &mut fmt::Formatter<'_>,
  70     ) -> Option<fmt::Result> {
  71         tls::with_current_program(|prog| Some(prog?.debug_alias(alias, fmt)))
  72     }
  73
  74     fn debug_projection_ty(
  75         proj: &chalk_ir::ProjectionTy<Interner>,
  76         fmt: &mut fmt::Formatter<'_>,
  77     ) -> Option<fmt::Result> {
  78         tls::with_current_program(|prog| Some(prog?.debug_projection_ty(proj, fmt)))
  79     }
  80
  81     fn debug_opaque_ty(
  82         opaque_ty: &chalk_ir::OpaqueTy<Interner>,
  83         fmt: &mut fmt::Formatter<'_>,
  84     ) -> Option<fmt::Result> {
  85         tls::with_current_program(|prog| Some(prog?.debug_opaque_ty(opaque_ty, fmt)))
  86     }
  87
  88     fn debug_opaque_ty_id(
  89         opaque_ty_id: chalk_ir::OpaqueTyId<Self>,
  90         fmt: &mut fmt::Formatter<'_>,
  91     ) -> Option<fmt::Result> {
  92         tls::with_current_program(|prog| Some(prog?.debug_opaque_ty_id(opaque_ty_id, fmt)))
  93     }
  94
  95     fn debug_ty(ty: &chalk_ir::Ty<Interner>, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> {
  96         tls::with_current_program(|prog| Some(prog?.debug_ty(ty, fmt)))
  97     }
  98
  99     fn debug_lifetime(
 100         lifetime: &chalk_ir::Lifetime<Interner>,
 101         fmt: &mut fmt::Formatter<'_>,
 102     ) -> Option<fmt::Result> {
 103         tls::with_current_program(|prog| Some(prog?.debug_lifetime(lifetime, fmt)))
 104     }
 105
 106     fn debug_generic_arg(
 107         parameter: &GenericArg<Interner>,
 108         fmt: &mut fmt::Formatter<'_>,
 109     ) -> Option<fmt::Result> {
 110         tls::with_current_program(|prog| Some(prog?.debug_generic_arg(parameter, fmt)))
 111     }
 112
 113     fn debug_goal(goal: &Goal<Interner>, fmt: &mut fmt::Formatter<'_>) -> Option<fmt::Result> {
 114         tls::with_current_program(|prog| Some(prog?.debug_goal(goal, fmt)))
 115     }
 116
 117     fn debug_goals(
 118         goals: &chalk_ir::Goals<Interner>,
 119         fmt: &mut fmt::Formatter<'_>,
 120     ) -> Option<fmt::Result> {
 121         tls::with_current_program(|prog| Some(prog?.debug_goals(goals, fmt)))
 122     }
 123
 124     fn debug_program_clause_implication(
 125         pci: &chalk_ir::ProgramClauseImplication<Interner>,
 126         fmt: &mut fmt::Formatter<'_>,
 127     ) -> Option<fmt::Result> {
 128         tls::with_current_program(|prog| Some(prog?.debug_program_clause_implication(pci, fmt)))
 129     }
 130
 131     fn debug_application_ty(
 132         application_ty: &chalk_ir::ApplicationTy<Interner>,
 133         fmt: &mut fmt::Formatter<'_>,
 134     ) -> Option<fmt::Result> {
 135         tls::with_current_program(|prog| Some(prog?.debug_application_ty(application_ty, fmt)))
 136     }
 137
 138     fn debug_substitution(
 139         substitution: &chalk_ir::Substitution<Interner>,
 140         fmt: &mut fmt::Formatter<'_>,
 141     ) -> Option<fmt::Result> {
 142         tls::with_current_program(|prog| Some(prog?.debug_substitution(substitution, fmt)))
 143     }
 144
 145     fn debug_separator_trait_ref(
 146         separator_trait_ref: &chalk_ir::SeparatorTraitRef<Interner>,
 147         fmt: &mut fmt::Formatter<'_>,
 148     ) -> Option<fmt::Result> {
 149         tls::with_current_program(|prog| {
 150             Some(prog?.debug_separator_trait_ref(separator_trait_ref, fmt))
 151         })
 152     }
 153
 154     fn intern_ty(&self, ty: chalk_ir::TyData<Self>) -> Box<chalk_ir::TyData<Self>> {
 155         Box::new(ty)
 156     }
 157
 158     fn ty_data<'a>(&self, ty: &'a Box<chalk_ir::TyData<Self>>) -> &'a chalk_ir::TyData<Self> {
 159         ty
 160     }
 161
 162     fn intern_lifetime(
 163         &self,
 164         lifetime: chalk_ir::LifetimeData<Self>,
 165     ) -> chalk_ir::LifetimeData<Self> {
 166         lifetime
 167     }
 168
 169     fn lifetime_data<'a>(
 170         &self,
 171         lifetime: &'a chalk_ir::LifetimeData<Self>,
 172     ) -> &'a chalk_ir::LifetimeData<Self> {
 173         lifetime
 174     }
 175
 176     fn intern_const(&self, constant: chalk_ir::ConstData<Self>) -> Arc<chalk_ir::ConstData<Self>> {
 177         Arc::new(constant)
 178     }
 179
 180     fn const_data<'a>(
 181         &self,
 182         constant: &'a Arc<chalk_ir::ConstData<Self>>,
 183     ) -> &'a chalk_ir::ConstData<Self> {
 184         constant
 185     }
 186
 187     fn const_eq(&self, _ty: &Box<chalk_ir::TyData<Self>>, _c1: &(), _c2: &()) -> bool {
 188         true
 189     }
 190
 191     fn intern_generic_arg(
 192         &self,
 193         parameter: chalk_ir::GenericArgData<Self>,
 194     ) -> chalk_ir::GenericArgData<Self> {
 195         parameter
 196     }
 197
 198     fn generic_arg_data<'a>(
 199         &self,
 200         parameter: &'a chalk_ir::GenericArgData<Self>,
 201     ) -> &'a chalk_ir::GenericArgData<Self> {
 202         parameter
 203     }
 204
 205     fn intern_goal(&self, goal: GoalData<Self>) -> Arc<GoalData<Self>> {
 206         Arc::new(goal)
 207     }
 208
 209     fn intern_goals<E>(
 210         &self,
 211         data: impl IntoIterator<Item = Result<Goal<Self>, E>>,
 212     ) -> Result<Self::InternedGoals, E> {
 213         data.into_iter().collect()
 214     }
 215
 216     fn goal_data<'a>(&self, goal: &'a Arc<GoalData<Self>>) -> &'a GoalData<Self> {
 217         goal
 218     }
 219
 220     fn goals_data<'a>(&self, goals: &'a Vec<Goal<Interner>>) -> &'a [Goal<Interner>] {
 221         goals
 222     }
 223
 224     fn intern_substitution<E>(
 225         &self,
 226         data: impl IntoIterator<Item = Result<GenericArg<Self>, E>>,
 227     ) -> Result<Vec<GenericArg<Self>>, E> {
 228         data.into_iter().collect()
 229     }
 230
 231     fn substitution_data<'a>(
 232         &self,
 233         substitution: &'a Vec<GenericArg<Self>>,
 234     ) -> &'a [GenericArg<Self>] {
 235         substitution
 236     }
 237
 238     fn intern_program_clause(
 239         &self,
 240         data: chalk_ir::ProgramClauseData<Self>,
 241     ) -> chalk_ir::ProgramClauseData<Self> {
 242         data
 243     }
 244
 245     fn program_clause_data<'a>(
 246         &self,
 247         clause: &'a chalk_ir::ProgramClauseData<Self>,
 248     ) -> &'a chalk_ir::ProgramClauseData<Self> {
 249         clause
 250     }
 251
 252     fn intern_program_clauses<E>(
 253         &self,
 254         data: impl IntoIterator<Item = Result<chalk_ir::ProgramClause<Self>, E>>,
 255     ) -> Result<Arc<[chalk_ir::ProgramClause<Self>]>, E> {
 256         data.into_iter().collect()
 257     }
 258
 259     fn program_clauses_data<'a>(
 260         &self,
 261         clauses: &'a Arc<[chalk_ir::ProgramClause<Self>]>,
 262     ) -> &'a [chalk_ir::ProgramClause<Self>] {
 263         &clauses
 264     }
 265
 266     fn intern_quantified_where_clauses<E>(
 267         &self,
 268         data: impl IntoIterator<Item = Result<chalk_ir::QuantifiedWhereClause<Self>, E>>,
 269     ) -> Result<Self::InternedQuantifiedWhereClauses, E> {
 270         data.into_iter().collect()
 271     }
 272
 273     fn quantified_where_clauses_data<'a>(
 274         &self,
 275         clauses: &'a Self::InternedQuantifiedWhereClauses,
 276     ) -> &'a [chalk_ir::QuantifiedWhereClause<Self>] {
 277         clauses
 278     }
 279
 280     fn intern_generic_arg_kinds<E>(
 281         &self,
 282         data: impl IntoIterator<Item = Result<chalk_ir::VariableKind<Self>, E>>,
 283     ) -> Result<Self::InternedVariableKinds, E> {
 284         data.into_iter().collect()
 285     }
 286
 287     fn variable_kinds_data<'a>(
 288         &self,
 289         parameter_kinds: &'a Self::InternedVariableKinds,
 290     ) -> &'a [chalk_ir::VariableKind<Self>] {
 291         &parameter_kinds
 292     }
 293
 294     fn intern_canonical_var_kinds<E>(
 295         &self,
 296         data: impl IntoIterator<Item = Result<chalk_ir::CanonicalVarKind<Self>, E>>,
 297     ) -> Result<Self::InternedCanonicalVarKinds, E> {
 298         data.into_iter().collect()
 299     }
 300
 301     fn canonical_var_kinds_data<'a>(
 302         &self,
 303         canonical_var_kinds: &'a Self::InternedCanonicalVarKinds,
 304     ) -> &'a [chalk_ir::CanonicalVarKind<Self>] {
 305         &canonical_var_kinds
 306     }
 307 }
 308
 309 impl chalk_ir::interner::HasInterner for Interner {
 310     type Interner = Self;
 311 }
 312
 313 pub type AssocTypeId = chalk_ir::AssocTypeId<Interner>;
 314 pub type AssociatedTyDatum = chalk_rust_ir::AssociatedTyDatum<Interner>;
 315 pub type TraitId = chalk_ir::TraitId<Interner>;
 316 pub type TraitDatum = chalk_rust_ir::TraitDatum<Interner>;
 317 pub type StructId = chalk_ir::AdtId<Interner>;
 318 pub type StructDatum = chalk_rust_ir::AdtDatum<Interner>;
 319 pub type ImplId = chalk_ir::ImplId<Interner>;
 320 pub type ImplDatum = chalk_rust_ir::ImplDatum<Interner>;
 321 pub type AssociatedTyValueId = chalk_rust_ir::AssociatedTyValueId<Interner>;
 322 pub type AssociatedTyValue = chalk_rust_ir::AssociatedTyValue<Interner>;
 323
 324 pub(super) trait ToChalk {
 325     type Chalk;
 326     fn to_chalk(self, db: &dyn HirDatabase) -> Self::Chalk;
 327     fn from_chalk(db: &dyn HirDatabase, chalk: Self::Chalk) -> Self;
 328 }
 329
 330 pub(super) fn from_chalk<T, ChalkT>(db: &dyn HirDatabase, chalk: ChalkT) -> T
 331 where
 332     T: ToChalk<Chalk = ChalkT>,
 333 {
 334     T::from_chalk(db, chalk)
 335 }
 336
 337 impl ToChalk for Ty {
 338     type Chalk = chalk_ir::Ty<Interner>;
 339     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Ty<Interner> {
 340         match self {
 341             Ty::Apply(apply_ty) => {
 342                 if let TypeCtor::Ref(m) = apply_ty.ctor {
 343                     return ref_to_chalk(db, m, apply_ty.parameters);
 344                 }
 345                 let name = apply_ty.ctor.to_chalk(db);
 346                 let substitution = apply_ty.parameters.to_chalk(db);
 347                 chalk_ir::ApplicationTy { name, substitution }.cast(&Interner).intern(&Interner)
 348             }
 349             Ty::Projection(proj_ty) => {
 350                 let associated_ty_id = proj_ty.associated_ty.to_chalk(db);
 351                 let substitution = proj_ty.parameters.to_chalk(db);
 352                 chalk_ir::AliasTy::Projection(chalk_ir::ProjectionTy {
 353                     associated_ty_id,
 354                     substitution,
 355                 })
 356                 .cast(&Interner)
 357                 .intern(&Interner)
 358             }
 359             Ty::Placeholder(id) => {
 360                 let interned_id = db.intern_type_param_id(id);
 361                 PlaceholderIndex {
 362                     ui: UniverseIndex::ROOT,
 363                     idx: interned_id.as_intern_id().as_usize(),
 364                 }
 365                 .to_ty::<Interner>(&Interner)
 366             }
 367             Ty::Bound(idx) => chalk_ir::TyData::BoundVar(idx).intern(&Interner),
 368             Ty::Infer(_infer_ty) => panic!("uncanonicalized infer ty"),
 369             Ty::Dyn(predicates) => {
 370                 let where_clauses = chalk_ir::QuantifiedWhereClauses::from(
 371                     &Interner,
 372                     predicates.iter().filter(|p| !p.is_error()).cloned().map(|p| p.to_chalk(db)),
 373                 );
 374                 let bounded_ty = chalk_ir::DynTy { bounds: make_binders(where_clauses, 1) };
 375                 chalk_ir::TyData::Dyn(bounded_ty).intern(&Interner)
 376             }
 377             Ty::Opaque(_) | Ty::Unknown => {
 378                 let substitution = chalk_ir::Substitution::empty(&Interner);
 379                 let name = TypeName::Error;
 380                 chalk_ir::ApplicationTy { name, substitution }.cast(&Interner).intern(&Interner)
 381             }
 382         }
 383     }
 384     fn from_chalk(db: &dyn HirDatabase, chalk: chalk_ir::Ty<Interner>) -> Self {
 385         match chalk.data(&Interner).clone() {
 386             chalk_ir::TyData::Apply(apply_ty) => match apply_ty.name {
 387                 TypeName::Error => Ty::Unknown,
 388                 TypeName::Ref(m) => ref_from_chalk(db, m, apply_ty.substitution),
 389                 _ => {
 390                     let ctor = from_chalk(db, apply_ty.name);
 391                     let parameters = from_chalk(db, apply_ty.substitution);
 392                     Ty::Apply(ApplicationTy { ctor, parameters })
 393                 }
 394             },
 395             chalk_ir::TyData::Placeholder(idx) => {
 396                 assert_eq!(idx.ui, UniverseIndex::ROOT);
 397                 let interned_id = crate::db::GlobalTypeParamId::from_intern_id(
 398                     crate::salsa::InternId::from(idx.idx),
 399                 );
 400                 Ty::Placeholder(db.lookup_intern_type_param_id(interned_id))
 401             }
 402             chalk_ir::TyData::Alias(chalk_ir::AliasTy::Projection(proj)) => {
 403                 let associated_ty = from_chalk(db, proj.associated_ty_id);
 404                 let parameters = from_chalk(db, proj.substitution);
 405                 Ty::Projection(ProjectionTy { associated_ty, parameters })
 406             }
 407             chalk_ir::TyData::Alias(chalk_ir::AliasTy::Opaque(_)) => unimplemented!(),
 408             chalk_ir::TyData::Function(_) => unimplemented!(),
 409             chalk_ir::TyData::BoundVar(idx) => Ty::Bound(idx),
 410             chalk_ir::TyData::InferenceVar(_iv) => Ty::Unknown,
 411             chalk_ir::TyData::Dyn(where_clauses) => {
 412                 assert_eq!(where_clauses.bounds.binders.len(&Interner), 1);
 413                 let predicates = where_clauses
 414                     .bounds
 415                     .skip_binders()
 416                     .iter(&Interner)
 417                     .map(|c| from_chalk(db, c.clone()))
 418                     .collect();
 419                 Ty::Dyn(predicates)
 420             }
 421         }
 422     }
 423 }
 424
 425 const LIFETIME_PLACEHOLDER: PlaceholderIndex =
 426     PlaceholderIndex { ui: UniverseIndex::ROOT, idx: usize::MAX };
 427
 428 /// We currently don't model lifetimes, but Chalk does. So, we have to insert a
 429 /// fake lifetime here, because Chalks built-in logic may expect it to be there.
 430 fn ref_to_chalk(
 431     db: &dyn HirDatabase,
 432     mutability: Mutability,
 433     subst: Substs,
 434 ) -> chalk_ir::Ty<Interner> {
 435     let arg = subst[0].clone().to_chalk(db);
 436     let lifetime = LIFETIME_PLACEHOLDER.to_lifetime(&Interner);
 437     chalk_ir::ApplicationTy {
 438         name: TypeName::Ref(mutability.to_chalk(db)),
 439         substitution: chalk_ir::Substitution::from(
 440             &Interner,
 441             vec![lifetime.cast(&Interner), arg.cast(&Interner)],
 442         ),
 443     }
 444     .intern(&Interner)
 445 }
 446
 447 /// Here we remove the lifetime from the type we got from Chalk.
 448 fn ref_from_chalk(
 449     db: &dyn HirDatabase,
 450     mutability: chalk_ir::Mutability,
 451     subst: chalk_ir::Substitution<Interner>,
 452 ) -> Ty {
 453     let tys = subst
 454         .iter(&Interner)
 455         .filter_map(|p| Some(from_chalk(db, p.ty(&Interner)?.clone())))
 456         .collect();
 457     Ty::apply(TypeCtor::Ref(from_chalk(db, mutability)), Substs(tys))
 458 }
 459
 460 impl ToChalk for Substs {
 461     type Chalk = chalk_ir::Substitution<Interner>;
 462
 463     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Substitution<Interner> {
 464         chalk_ir::Substitution::from(&Interner, self.iter().map(|ty| ty.clone().to_chalk(db)))
 465     }
 466
 467     fn from_chalk(db: &dyn HirDatabase, parameters: chalk_ir::Substitution<Interner>) -> Substs {
 468         let tys = parameters
 469             .iter(&Interner)
 470             .map(|p| match p.ty(&Interner) {
 471                 Some(ty) => from_chalk(db, ty.clone()),
 472                 None => unimplemented!(),
 473             })
 474             .collect();
 475         Substs(tys)
 476     }
 477 }
 478
 479 impl ToChalk for TraitRef {
 480     type Chalk = chalk_ir::TraitRef<Interner>;
 481
 482     fn to_chalk(self: TraitRef, db: &dyn HirDatabase) -> chalk_ir::TraitRef<Interner> {
 483         let trait_id = self.trait_.to_chalk(db);
 484         let substitution = self.substs.to_chalk(db);
 485         chalk_ir::TraitRef { trait_id, substitution }
 486     }
 487
 488     fn from_chalk(db: &dyn HirDatabase, trait_ref: chalk_ir::TraitRef<Interner>) -> Self {
 489         let trait_ = from_chalk(db, trait_ref.trait_id);
 490         let substs = from_chalk(db, trait_ref.substitution);
 491         TraitRef { trait_, substs }
 492     }
 493 }
 494
 495 impl ToChalk for hir_def::TraitId {
 496     type Chalk = TraitId;
 497
 498     fn to_chalk(self, _db: &dyn HirDatabase) -> TraitId {
 499         chalk_ir::TraitId(self.as_intern_id())
 500     }
 501
 502     fn from_chalk(_db: &dyn HirDatabase, trait_id: TraitId) -> hir_def::TraitId {
 503         InternKey::from_intern_id(trait_id.0)
 504     }
 505 }
 506
 507 impl ToChalk for TypeCtor {
 508     type Chalk = TypeName<Interner>;
 509
 510     fn to_chalk(self, db: &dyn HirDatabase) -> TypeName<Interner> {
 511         match self {
 512             TypeCtor::AssociatedType(type_alias) => {
 513                 let type_id = type_alias.to_chalk(db);
 514                 TypeName::AssociatedType(type_id)
 515             }
 516
 517             TypeCtor::Bool => TypeName::Scalar(Scalar::Bool),
 518             TypeCtor::Char => TypeName::Scalar(Scalar::Char),
 519             TypeCtor::Int(Uncertain::Known(int_ty)) => TypeName::Scalar(int_ty_to_chalk(int_ty)),
 520             TypeCtor::Float(Uncertain::Known(FloatTy { bitness: FloatBitness::X32 })) => {
 521                 TypeName::Scalar(Scalar::Float(chalk_ir::FloatTy::F32))
 522             }
 523             TypeCtor::Float(Uncertain::Known(FloatTy { bitness: FloatBitness::X64 })) => {
 524                 TypeName::Scalar(Scalar::Float(chalk_ir::FloatTy::F64))
 525             }
 526
 527             TypeCtor::Tuple { cardinality } => TypeName::Tuple(cardinality.into()),
 528             TypeCtor::RawPtr(mutability) => TypeName::Raw(mutability.to_chalk(db)),
 529             TypeCtor::Slice => TypeName::Slice,
 530             TypeCtor::Ref(mutability) => TypeName::Ref(mutability.to_chalk(db)),
 531             TypeCtor::Str => TypeName::Str,
 532
 533             TypeCtor::Int(Uncertain::Unknown)
 534             | TypeCtor::Float(Uncertain::Unknown)
 535             | TypeCtor::Adt(_)
 536             | TypeCtor::Array
 537             | TypeCtor::FnDef(_)
 538             | TypeCtor::FnPtr { .. }
 539             | TypeCtor::Never
 540             | TypeCtor::Closure { .. } => {
 541                 // other TypeCtors get interned and turned into a chalk StructId
 542                 let struct_id = db.intern_type_ctor(self).into();
 543                 TypeName::Adt(struct_id)
 544             }
 545         }
 546     }
 547
 548     fn from_chalk(db: &dyn HirDatabase, type_name: TypeName<Interner>) -> TypeCtor {
 549         match type_name {
 550             TypeName::Adt(struct_id) => db.lookup_intern_type_ctor(struct_id.into()),
 551             TypeName::AssociatedType(type_id) => TypeCtor::AssociatedType(from_chalk(db, type_id)),
 552             TypeName::OpaqueType(_) => unreachable!(),
 553
 554             TypeName::Scalar(Scalar::Bool) => TypeCtor::Bool,
 555             TypeName::Scalar(Scalar::Char) => TypeCtor::Char,
 556             TypeName::Scalar(Scalar::Int(int_ty)) => TypeCtor::Int(Uncertain::Known(IntTy {
 557                 signedness: Signedness::Signed,
 558                 bitness: bitness_from_chalk_int(int_ty),
 559             })),
 560             TypeName::Scalar(Scalar::Uint(uint_ty)) => TypeCtor::Int(Uncertain::Known(IntTy {
 561                 signedness: Signedness::Unsigned,
 562                 bitness: bitness_from_chalk_uint(uint_ty),
 563             })),
 564             TypeName::Scalar(Scalar::Float(chalk_ir::FloatTy::F32)) => {
 565                 TypeCtor::Float(Uncertain::Known(FloatTy { bitness: FloatBitness::X32 }))
 566             }
 567             TypeName::Scalar(Scalar::Float(chalk_ir::FloatTy::F64)) => {
 568                 TypeCtor::Float(Uncertain::Known(FloatTy { bitness: FloatBitness::X64 }))
 569             }
 570             TypeName::Tuple(cardinality) => TypeCtor::Tuple { cardinality: cardinality as u16 },
 571             TypeName::Raw(mutability) => TypeCtor::RawPtr(from_chalk(db, mutability)),
 572             TypeName::Slice => TypeCtor::Slice,
 573             TypeName::Ref(mutability) => TypeCtor::Ref(from_chalk(db, mutability)),
 574             TypeName::Str => TypeCtor::Str,
 575
 576             TypeName::FnDef(_) => unreachable!(),
 577
 578             TypeName::Error => {
 579                 // this should not be reached, since we don't represent TypeName::Error with TypeCtor
 580                 unreachable!()
 581             }
 582         }
 583     }
 584 }
 585
 586 fn bitness_from_chalk_uint(uint_ty: chalk_ir::UintTy) -> IntBitness {
 587     use chalk_ir::UintTy;
 588
 589     match uint_ty {
 590         UintTy::Usize => IntBitness::Xsize,
 591         UintTy::U8 => IntBitness::X8,
 592         UintTy::U16 => IntBitness::X16,
 593         UintTy::U32 => IntBitness::X32,
 594         UintTy::U64 => IntBitness::X64,
 595         UintTy::U128 => IntBitness::X128,
 596     }
 597 }
 598
 599 fn bitness_from_chalk_int(int_ty: chalk_ir::IntTy) -> IntBitness {
 600     use chalk_ir::IntTy;
 601
 602     match int_ty {
 603         IntTy::Isize => IntBitness::Xsize,
 604         IntTy::I8 => IntBitness::X8,
 605         IntTy::I16 => IntBitness::X16,
 606         IntTy::I32 => IntBitness::X32,
 607         IntTy::I64 => IntBitness::X64,
 608         IntTy::I128 => IntBitness::X128,
 609     }
 610 }
 611
 612 fn int_ty_to_chalk(int_ty: IntTy) -> Scalar {
 613     use chalk_ir::{IntTy, UintTy};
 614
 615     match int_ty.signedness {
 616         Signedness::Signed => Scalar::Int(match int_ty.bitness {
 617             IntBitness::Xsize => IntTy::Isize,
 618             IntBitness::X8 => IntTy::I8,
 619             IntBitness::X16 => IntTy::I16,
 620             IntBitness::X32 => IntTy::I32,
 621             IntBitness::X64 => IntTy::I64,
 622             IntBitness::X128 => IntTy::I128,
 623         }),
 624         Signedness::Unsigned => Scalar::Uint(match int_ty.bitness {
 625             IntBitness::Xsize => UintTy::Usize,
 626             IntBitness::X8 => UintTy::U8,
 627             IntBitness::X16 => UintTy::U16,
 628             IntBitness::X32 => UintTy::U32,
 629             IntBitness::X64 => UintTy::U64,
 630             IntBitness::X128 => UintTy::U128,
 631         }),
 632     }
 633 }
 634
 635 impl ToChalk for Mutability {
 636     type Chalk = chalk_ir::Mutability;
 637     fn to_chalk(self, _db: &dyn HirDatabase) -> Self::Chalk {
 638         match self {
 639             Mutability::Shared => chalk_ir::Mutability::Not,
 640             Mutability::Mut => chalk_ir::Mutability::Mut,
 641         }
 642     }
 643     fn from_chalk(_db: &dyn HirDatabase, chalk: Self::Chalk) -> Self {
 644         match chalk {
 645             chalk_ir::Mutability::Mut => Mutability::Mut,
 646             chalk_ir::Mutability::Not => Mutability::Shared,
 647         }
 648     }
 649 }
 650
 651 impl ToChalk for Impl {
 652     type Chalk = ImplId;
 653
 654     fn to_chalk(self, db: &dyn HirDatabase) -> ImplId {
 655         db.intern_chalk_impl(self).into()
 656     }
 657
 658     fn from_chalk(db: &dyn HirDatabase, impl_id: ImplId) -> Impl {
 659         db.lookup_intern_chalk_impl(impl_id.into())
 660     }
 661 }
 662
 663 impl ToChalk for TypeAliasId {
 664     type Chalk = AssocTypeId;
 665
 666     fn to_chalk(self, _db: &dyn HirDatabase) -> AssocTypeId {
 667         chalk_ir::AssocTypeId(self.as_intern_id())
 668     }
 669
 670     fn from_chalk(_db: &dyn HirDatabase, type_alias_id: AssocTypeId) -> TypeAliasId {
 671         InternKey::from_intern_id(type_alias_id.0)
 672     }
 673 }
 674
 675 impl ToChalk for AssocTyValue {
 676     type Chalk = AssociatedTyValueId;
 677
 678     fn to_chalk(self, db: &dyn HirDatabase) -> AssociatedTyValueId {
 679         db.intern_assoc_ty_value(self).into()
 680     }
 681
 682     fn from_chalk(db: &dyn HirDatabase, assoc_ty_value_id: AssociatedTyValueId) -> AssocTyValue {
 683         db.lookup_intern_assoc_ty_value(assoc_ty_value_id.into())
 684     }
 685 }
 686
 687 impl ToChalk for GenericPredicate {
 688     type Chalk = chalk_ir::QuantifiedWhereClause<Interner>;
 689
 690     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::QuantifiedWhereClause<Interner> {
 691         match self {
 692             GenericPredicate::Implemented(trait_ref) => {
 693                 let chalk_trait_ref = trait_ref.to_chalk(db);
 694                 let chalk_trait_ref = chalk_trait_ref.shifted_in(&Interner);
 695                 make_binders(chalk_ir::WhereClause::Implemented(chalk_trait_ref), 0)
 696             }
 697             GenericPredicate::Projection(projection_pred) => {
 698                 let ty = projection_pred.ty.to_chalk(db).shifted_in(&Interner);
 699                 let projection = projection_pred.projection_ty.to_chalk(db).shifted_in(&Interner);
 700                 let alias = chalk_ir::AliasTy::Projection(projection);
 701                 make_binders(chalk_ir::WhereClause::AliasEq(chalk_ir::AliasEq { alias, ty }), 0)
 702             }
 703             GenericPredicate::Error => panic!("tried passing GenericPredicate::Error to Chalk"),
 704         }
 705     }
 706
 707     fn from_chalk(
 708         db: &dyn HirDatabase,
 709         where_clause: chalk_ir::QuantifiedWhereClause<Interner>,
 710     ) -> GenericPredicate {
 711         // we don't produce any where clauses with binders and can't currently deal with them
 712         match where_clause
 713             .skip_binders()
 714             .shifted_out(&Interner)
 715             .expect("unexpected bound vars in where clause")
 716         {
 717             chalk_ir::WhereClause::Implemented(tr) => {
 718                 GenericPredicate::Implemented(from_chalk(db, tr))
 719             }
 720             chalk_ir::WhereClause::AliasEq(projection_eq) => {
 721                 let projection_ty = from_chalk(
 722                     db,
 723                     match projection_eq.alias {
 724                         chalk_ir::AliasTy::Projection(p) => p,
 725                         _ => unimplemented!(),
 726                     },
 727                 );
 728                 let ty = from_chalk(db, projection_eq.ty);
 729                 GenericPredicate::Projection(super::ProjectionPredicate { projection_ty, ty })
 730             }
 731         }
 732     }
 733 }
 734
 735 impl ToChalk for ProjectionTy {
 736     type Chalk = chalk_ir::ProjectionTy<Interner>;
 737
 738     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::ProjectionTy<Interner> {
 739         chalk_ir::ProjectionTy {
 740             associated_ty_id: self.associated_ty.to_chalk(db),
 741             substitution: self.parameters.to_chalk(db),
 742         }
 743     }
 744
 745     fn from_chalk(
 746         db: &dyn HirDatabase,
 747         projection_ty: chalk_ir::ProjectionTy<Interner>,
 748     ) -> ProjectionTy {
 749         ProjectionTy {
 750             associated_ty: from_chalk(db, projection_ty.associated_ty_id),
 751             parameters: from_chalk(db, projection_ty.substitution),
 752         }
 753     }
 754 }
 755
 756 impl ToChalk for super::ProjectionPredicate {
 757     type Chalk = chalk_ir::AliasEq<Interner>;
 758
 759     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::AliasEq<Interner> {
 760         chalk_ir::AliasEq {
 761             alias: chalk_ir::AliasTy::Projection(self.projection_ty.to_chalk(db)),
 762             ty: self.ty.to_chalk(db),
 763         }
 764     }
 765
 766     fn from_chalk(_db: &dyn HirDatabase, _normalize: chalk_ir::AliasEq<Interner>) -> Self {
 767         unimplemented!()
 768     }
 769 }
 770
 771 impl ToChalk for Obligation {
 772     type Chalk = chalk_ir::DomainGoal<Interner>;
 773
 774     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::DomainGoal<Interner> {
 775         match self {
 776             Obligation::Trait(tr) => tr.to_chalk(db).cast(&Interner),
 777             Obligation::Projection(pr) => pr.to_chalk(db).cast(&Interner),
 778         }
 779     }
 780
 781     fn from_chalk(_db: &dyn HirDatabase, _goal: chalk_ir::DomainGoal<Interner>) -> Self {
 782         unimplemented!()
 783     }
 784 }
 785
 786 impl<T> ToChalk for Canonical<T>
 787 where
 788     T: ToChalk,
 789     T::Chalk: HasInterner<Interner = Interner>,
 790 {
 791     type Chalk = chalk_ir::Canonical<T::Chalk>;
 792
 793     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Canonical<T::Chalk> {
 794         let parameter = chalk_ir::CanonicalVarKind::new(
 795             chalk_ir::VariableKind::Ty,
 796             chalk_ir::UniverseIndex::ROOT,
 797         );
 798         let value = self.value.to_chalk(db);
 799         chalk_ir::Canonical {
 800             value,
 801             binders: chalk_ir::CanonicalVarKinds::from(&Interner, vec![parameter; self.num_vars]),
 802         }
 803     }
 804
 805     fn from_chalk(db: &dyn HirDatabase, canonical: chalk_ir::Canonical<T::Chalk>) -> Canonical<T> {
 806         Canonical {
 807             num_vars: canonical.binders.len(&Interner),
 808             value: from_chalk(db, canonical.value),
 809         }
 810     }
 811 }
 812
 813 impl ToChalk for Arc<super::TraitEnvironment> {
 814     type Chalk = chalk_ir::Environment<Interner>;
 815
 816     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Environment<Interner> {
 817         let mut clauses = Vec::new();
 818         for pred in &self.predicates {
 819             if pred.is_error() {
 820                 // for env, we just ignore errors
 821                 continue;
 822             }
 823             let program_clause: chalk_ir::ProgramClause<Interner> =
 824                 pred.clone().to_chalk(db).cast(&Interner);
 825             clauses.push(program_clause.into_from_env_clause(&Interner));
 826         }
 827         chalk_ir::Environment::new(&Interner).add_clauses(&Interner, clauses)
 828     }
 829
 830     fn from_chalk(
 831         _db: &dyn HirDatabase,
 832         _env: chalk_ir::Environment<Interner>,
 833     ) -> Arc<super::TraitEnvironment> {
 834         unimplemented!()
 835     }
 836 }
 837
 838 impl<T: ToChalk> ToChalk for super::InEnvironment<T>
 839 where
 840     T::Chalk: chalk_ir::interner::HasInterner<Interner = Interner>,
 841 {
 842     type Chalk = chalk_ir::InEnvironment<T::Chalk>;
 843
 844     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::InEnvironment<T::Chalk> {
 845         chalk_ir::InEnvironment {
 846             environment: self.environment.to_chalk(db),
 847             goal: self.value.to_chalk(db),
 848         }
 849     }
 850
 851     fn from_chalk(
 852         db: &dyn HirDatabase,
 853         in_env: chalk_ir::InEnvironment<T::Chalk>,
 854     ) -> super::InEnvironment<T> {
 855         super::InEnvironment {
 856             environment: from_chalk(db, in_env.environment),
 857             value: from_chalk(db, in_env.goal),
 858         }
 859     }
 860 }
 861
 862 impl ToChalk for builtin::BuiltinImplData {
 863     type Chalk = ImplDatum;
 864
 865     fn to_chalk(self, db: &dyn HirDatabase) -> ImplDatum {
 866         let impl_type = chalk_rust_ir::ImplType::External;
 867         let where_clauses = self.where_clauses.into_iter().map(|w| w.to_chalk(db)).collect();
 868
 869         let impl_datum_bound =
 870             chalk_rust_ir::ImplDatumBound { trait_ref: self.trait_ref.to_chalk(db), where_clauses };
 871         let associated_ty_value_ids =
 872             self.assoc_ty_values.into_iter().map(|v| v.to_chalk(db)).collect();
 873         chalk_rust_ir::ImplDatum {
 874             binders: make_binders(impl_datum_bound, self.num_vars),
 875             impl_type,
 876             polarity: chalk_rust_ir::Polarity::Positive,
 877             associated_ty_value_ids,
 878         }
 879     }
 880
 881     fn from_chalk(_db: &dyn HirDatabase, _data: ImplDatum) -> Self {
 882         unimplemented!()
 883     }
 884 }
 885
 886 impl ToChalk for builtin::BuiltinImplAssocTyValueData {
 887     type Chalk = AssociatedTyValue;
 888
 889     fn to_chalk(self, db: &dyn HirDatabase) -> AssociatedTyValue {
 890         let ty = self.value.to_chalk(db);
 891         let value_bound = chalk_rust_ir::AssociatedTyValueBound { ty };
 892
 893         chalk_rust_ir::AssociatedTyValue {
 894             associated_ty_id: self.assoc_ty_id.to_chalk(db),
 895             impl_id: self.impl_.to_chalk(db),
 896             value: make_binders(value_bound, self.num_vars),
 897         }
 898     }
 899
 900     fn from_chalk(
 901         _db: &dyn HirDatabase,
 902         _data: AssociatedTyValue,
 903     ) -> builtin::BuiltinImplAssocTyValueData {
 904         unimplemented!()
 905     }
 906 }
 907
 908 fn make_binders<T>(value: T, num_vars: usize) -> chalk_ir::Binders<T>
 909 where
 910     T: HasInterner<Interner = Interner>,
 911 {
 912     chalk_ir::Binders::new(
 913         chalk_ir::VariableKinds::from(
 914             &Interner,
 915             std::iter::repeat(chalk_ir::VariableKind::Ty).take(num_vars),
 916         ),
 917         value,
 918     )
 919 }
 920
 921 fn convert_where_clauses(
 922     db: &dyn HirDatabase,
 923     def: GenericDefId,
 924     substs: &Substs,
 925 ) -> Vec<chalk_ir::QuantifiedWhereClause<Interner>> {
 926     let generic_predicates = db.generic_predicates(def);
 927     let mut result = Vec::with_capacity(generic_predicates.len());
 928     for pred in generic_predicates.iter() {
 929         if pred.value.is_error() {
 930             // skip errored predicates completely
 931             continue;
 932         }
 933         result.push(pred.clone().subst(substs).to_chalk(db));
 934     }
 935     result
 936 }
 937
 938 fn generic_predicate_to_inline_bound(
 939     db: &dyn HirDatabase,
 940     pred: &GenericPredicate,
 941     self_ty: &Ty,
 942 ) -> Option<chalk_rust_ir::InlineBound<Interner>> {
 943     // An InlineBound is like a GenericPredicate, except the self type is left out.
 944     // We don't have a special type for this, but Chalk does.
 945     match pred {
 946         GenericPredicate::Implemented(trait_ref) => {
 947             if &trait_ref.substs[0] != self_ty {
 948                 // we can only convert predicates back to type bounds if they
 949                 // have the expected self type
 950                 return None;
 951             }
 952             let args_no_self = trait_ref.substs[1..]
 953                 .iter()
 954                 .map(|ty| ty.clone().to_chalk(db).cast(&Interner))
 955                 .collect();
 956             let trait_bound =
 957                 chalk_rust_ir::TraitBound { trait_id: trait_ref.trait_.to_chalk(db), args_no_self };
 958             Some(chalk_rust_ir::InlineBound::TraitBound(trait_bound))
 959         }
 960         GenericPredicate::Projection(proj) => {
 961             if &proj.projection_ty.parameters[0] != self_ty {
 962                 return None;
 963             }
 964             let trait_ = match proj.projection_ty.associated_ty.lookup(db.upcast()).container {
 965                 AssocContainerId::TraitId(t) => t,
 966                 _ => panic!("associated type not in trait"),
 967             };
 968             let args_no_self = proj.projection_ty.parameters[1..]
 969                 .iter()
 970                 .map(|ty| ty.clone().to_chalk(db).cast(&Interner))
 971                 .collect();
 972             let alias_eq_bound = chalk_rust_ir::AliasEqBound {
 973                 value: proj.ty.clone().to_chalk(db),
 974                 trait_bound: chalk_rust_ir::TraitBound {
 975                     trait_id: trait_.to_chalk(db),
 976                     args_no_self,
 977                 },
 978                 associated_ty_id: proj.projection_ty.associated_ty.to_chalk(db),
 979                 parameters: Vec::new(), // FIXME we don't support generic associated types yet
 980             };
 981             Some(chalk_rust_ir::InlineBound::AliasEqBound(alias_eq_bound))
 982         }
 983         GenericPredicate::Error => None,
 984     }
 985 }
 986
 987 impl<'a> chalk_solve::RustIrDatabase<Interner> for ChalkContext<'a> {
 988     fn associated_ty_data(&self, id: AssocTypeId) -> Arc<AssociatedTyDatum> {
 989         self.db.associated_ty_data(id)
 990     }
 991     fn trait_datum(&self, trait_id: TraitId) -> Arc<TraitDatum> {
 992         self.db.trait_datum(self.krate, trait_id)
 993     }
 994     fn adt_datum(&self, struct_id: StructId) -> Arc<StructDatum> {
 995         self.db.struct_datum(self.krate, struct_id)
 996     }
 997     fn impl_datum(&self, impl_id: ImplId) -> Arc<ImplDatum> {
 998         self.db.impl_datum(self.krate, impl_id)
 999     }
1000
1001     fn fn_def_datum(
1002         &self,
1003         _fn_def_id: chalk_ir::FnDefId<Interner>,
1004     ) -> Arc<chalk_rust_ir::FnDefDatum<Interner>> {
1005         // We don't yet provide any FnDefs to Chalk
1006         unimplemented!()
1007     }
1008
1009     fn impls_for_trait(
1010         &self,
1011         trait_id: TraitId,
1012         parameters: &[GenericArg<Interner>],
1013     ) -> Vec<ImplId> {
1014         debug!("impls_for_trait {:?}", trait_id);
1015         let trait_: hir_def::TraitId = from_chalk(self.db, trait_id);
1016
1017         let ty: Ty = from_chalk(self.db, parameters[0].assert_ty_ref(&Interner).clone());
1018
1019         let self_ty_fp = TyFingerprint::for_impl(&ty);
1020
1021         // Note: Since we're using impls_for_trait, only impls where the trait
1022         // can be resolved should ever reach Chalk. `impl_datum` relies on that
1023         // and will panic if the trait can't be resolved.
1024         let mut result: Vec<_> = self
1025             .db
1026             .impls_for_trait(self.krate, trait_, self_ty_fp)
1027             .iter()
1028             .copied()
1029             .map(Impl::ImplDef)
1030             .map(|impl_| impl_.to_chalk(self.db))
1031             .collect();
1032
1033         let arg: Option<Ty> =
1034             parameters.get(1).map(|p| from_chalk(self.db, p.assert_ty_ref(&Interner).clone()));
1035
1036         builtin::get_builtin_impls(self.db, self.krate, &ty, &arg, trait_, |i| {
1037             result.push(i.to_chalk(self.db))
1038         });
1039
1040         debug!("impls_for_trait returned {} impls", result.len());
1041         result
1042     }
1043     fn impl_provided_for(&self, auto_trait_id: TraitId, struct_id: StructId) -> bool {
1044         debug!("impl_provided_for {:?}, {:?}", auto_trait_id, struct_id);
1045         false // FIXME
1046     }
1047     fn associated_ty_value(&self, id: AssociatedTyValueId) -> Arc<AssociatedTyValue> {
1048         self.db.associated_ty_value(self.krate, id)
1049     }
1050     fn custom_clauses(&self) -> Vec<chalk_ir::ProgramClause<Interner>> {
1051         vec![]
1052     }
1053     fn local_impls_to_coherence_check(&self, _trait_id: TraitId) -> Vec<ImplId> {
1054         // We don't do coherence checking (yet)
1055         unimplemented!()
1056     }
1057     fn interner(&self) -> &Interner {
1058         &Interner
1059     }
1060     fn well_known_trait_id(
1061         &self,
1062         well_known_trait: chalk_rust_ir::WellKnownTrait,
1063     ) -> Option<chalk_ir::TraitId<Interner>> {
1064         let lang_attr = lang_attr_from_well_known_trait(well_known_trait);
1065         let lang_items = self.db.crate_lang_items(self.krate);
1066         let trait_ = match lang_items.target(lang_attr) {
1067             Some(LangItemTarget::TraitId(trait_)) => trait_,
1068             _ => return None,
1069         };
1070         Some(trait_.to_chalk(self.db))
1071     }
1072
1073     fn program_clauses_for_env(
1074         &self,
1075         environment: &chalk_ir::Environment<Interner>,
1076     ) -> chalk_ir::ProgramClauses<Interner> {
1077         self.db.program_clauses_for_chalk_env(self.krate, environment.clone())
1078     }
1079
1080     fn opaque_ty_data(
1081         &self,
1082         _id: chalk_ir::OpaqueTyId<Interner>,
1083     ) -> Arc<chalk_rust_ir::OpaqueTyDatum<Interner>> {
1084         unimplemented!()
1085     }
1086
1087     fn force_impl_for(
1088         &self,
1089         _well_known: chalk_rust_ir::WellKnownTrait,
1090         _ty: &chalk_ir::TyData<Interner>,
1091     ) -> Option<bool> {
1092         // this method is mostly for rustc
1093         None
1094     }
1095
1096     fn is_object_safe(&self, _trait_id: chalk_ir::TraitId<Interner>) -> bool {
1097         // FIXME: implement actual object safety
1098         true
1099     }
1100 }
1101
1102 pub(crate) fn program_clauses_for_chalk_env_query(
1103     db: &dyn HirDatabase,
1104     krate: CrateId,
1105     environment: chalk_ir::Environment<Interner>,
1106 ) -> chalk_ir::ProgramClauses<Interner> {
1107     chalk_solve::program_clauses_for_env(&ChalkContext { db, krate }, &environment)
1108 }
1109
1110 pub(crate) fn associated_ty_data_query(
1111     db: &dyn HirDatabase,
1112     id: AssocTypeId,
1113 ) -> Arc<AssociatedTyDatum> {
1114     debug!("associated_ty_data {:?}", id);
1115     let type_alias: TypeAliasId = from_chalk(db, id);
1116     let trait_ = match type_alias.lookup(db.upcast()).container {
1117         AssocContainerId::TraitId(t) => t,
1118         _ => panic!("associated type not in trait"),
1119     };
1120
1121     // Lower bounds -- we could/should maybe move this to a separate query in `lower`
1122     let type_alias_data = db.type_alias_data(type_alias);
1123     let generic_params = generics(db.upcast(), type_alias.into());
1124     let bound_vars = Substs::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
1125     let resolver = hir_def::resolver::HasResolver::resolver(type_alias, db.upcast());
1126     let ctx = crate::TyLoweringContext::new(db, &resolver)
1127         .with_type_param_mode(crate::lower::TypeParamLoweringMode::Variable);
1128     let self_ty = Ty::Bound(crate::BoundVar::new(crate::DebruijnIndex::INNERMOST, 0));
1129     let bounds = type_alias_data
1130         .bounds
1131         .iter()
1132         .flat_map(|bound| GenericPredicate::from_type_bound(&ctx, bound, self_ty.clone()))
1133         .filter_map(|pred| generic_predicate_to_inline_bound(db, &pred, &self_ty))
1134         .map(|bound| make_binders(bound.shifted_in(&Interner), 0))
1135         .collect();
1136
1137     let where_clauses = convert_where_clauses(db, type_alias.into(), &bound_vars);
1138     let bound_data = chalk_rust_ir::AssociatedTyDatumBound { bounds, where_clauses };
1139     let datum = AssociatedTyDatum {
1140         trait_id: trait_.to_chalk(db),
1141         id,
1142         name: type_alias,
1143         binders: make_binders(bound_data, generic_params.len()),
1144     };
1145     Arc::new(datum)
1146 }
1147
1148 pub(crate) fn trait_datum_query(
1149     db: &dyn HirDatabase,
1150     krate: CrateId,
1151     trait_id: TraitId,
1152 ) -> Arc<TraitDatum> {
1153     debug!("trait_datum {:?}", trait_id);
1154     let trait_: hir_def::TraitId = from_chalk(db, trait_id);
1155     let trait_data = db.trait_data(trait_);
1156     debug!("trait {:?} = {:?}", trait_id, trait_data.name);
1157     let generic_params = generics(db.upcast(), trait_.into());
1158     let bound_vars = Substs::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
1159     let flags = chalk_rust_ir::TraitFlags {
1160         auto: trait_data.auto,
1161         upstream: trait_.lookup(db.upcast()).container.module(db.upcast()).krate != krate,
1162         non_enumerable: true,
1163         coinductive: false, // only relevant for Chalk testing
1164         // FIXME set these flags correctly
1165         marker: false,
1166         fundamental: false,
1167     };
1168     let where_clauses = convert_where_clauses(db, trait_.into(), &bound_vars);
1169     let associated_ty_ids =
1170         trait_data.associated_types().map(|type_alias| type_alias.to_chalk(db)).collect();
1171     let trait_datum_bound = chalk_rust_ir::TraitDatumBound { where_clauses };
1172     let well_known =
1173         lang_attr(db.upcast(), trait_).and_then(|name| well_known_trait_from_lang_attr(&name));
1174     let trait_datum = TraitDatum {
1175         id: trait_id,
1176         binders: make_binders(trait_datum_bound, bound_vars.len()),
1177         flags,
1178         associated_ty_ids,
1179         well_known,
1180     };
1181     Arc::new(trait_datum)
1182 }
1183
1184 fn well_known_trait_from_lang_attr(name: &str) -> Option<WellKnownTrait> {
1185     Some(match name {
1186         "sized" => WellKnownTrait::SizedTrait,
1187         "copy" => WellKnownTrait::CopyTrait,
1188         "clone" => WellKnownTrait::CloneTrait,
1189         "drop" => WellKnownTrait::DropTrait,
1190         _ => return None,
1191     })
1192 }
1193
1194 fn lang_attr_from_well_known_trait(attr: WellKnownTrait) -> &'static str {
1195     match attr {
1196         WellKnownTrait::SizedTrait => "sized",
1197         WellKnownTrait::CopyTrait => "copy",
1198         WellKnownTrait::CloneTrait => "clone",
1199         WellKnownTrait::DropTrait => "drop",
1200     }
1201 }
1202
1203 pub(crate) fn struct_datum_query(
1204     db: &dyn HirDatabase,
1205     krate: CrateId,
1206     struct_id: StructId,
1207 ) -> Arc<StructDatum> {
1208     debug!("struct_datum {:?}", struct_id);
1209     let type_ctor: TypeCtor = from_chalk(db, TypeName::Adt(struct_id));
1210     debug!("struct {:?} = {:?}", struct_id, type_ctor);
1211     let num_params = type_ctor.num_ty_params(db);
1212     let upstream = type_ctor.krate(db) != Some(krate);
1213     let where_clauses = type_ctor
1214         .as_generic_def()
1215         .map(|generic_def| {
1216             let generic_params = generics(db.upcast(), generic_def);
1217             let bound_vars = Substs::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
1218             convert_where_clauses(db, generic_def, &bound_vars)
1219         })
1220         .unwrap_or_else(Vec::new);
1221     let flags = chalk_rust_ir::AdtFlags {
1222         upstream,
1223         // FIXME set fundamental flag correctly
1224         fundamental: false,
1225     };
1226     let struct_datum_bound = chalk_rust_ir::AdtDatumBound {
1227         fields: Vec::new(), // FIXME add fields (only relevant for auto traits)
1228         where_clauses,
1229     };
1230     let struct_datum =
1231         StructDatum { id: struct_id, binders: make_binders(struct_datum_bound, num_params), flags };
1232     Arc::new(struct_datum)
1233 }
1234
1235 pub(crate) fn impl_datum_query(
1236     db: &dyn HirDatabase,
1237     krate: CrateId,
1238     impl_id: ImplId,
1239 ) -> Arc<ImplDatum> {
1240     let _p = ra_prof::profile("impl_datum");
1241     debug!("impl_datum {:?}", impl_id);
1242     let impl_: Impl = from_chalk(db, impl_id);
1243     match impl_ {
1244         Impl::ImplDef(impl_def) => impl_def_datum(db, krate, impl_id, impl_def),
1245         _ => Arc::new(builtin::impl_datum(db, krate, impl_).to_chalk(db)),
1246     }
1247 }
1248
1249 fn impl_def_datum(
1250     db: &dyn HirDatabase,
1251     krate: CrateId,
1252     chalk_id: ImplId,
1253     impl_id: hir_def::ImplId,
1254 ) -> Arc<ImplDatum> {
1255     let trait_ref = db
1256         .impl_trait(impl_id)
1257         // ImplIds for impls where the trait ref can't be resolved should never reach Chalk
1258         .expect("invalid impl passed to Chalk")
1259         .value;
1260     let impl_data = db.impl_data(impl_id);
1261
1262     let generic_params = generics(db.upcast(), impl_id.into());
1263     let bound_vars = Substs::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
1264     let trait_ = trait_ref.trait_;
1265     let impl_type = if impl_id.lookup(db.upcast()).container.module(db.upcast()).krate == krate {
1266         chalk_rust_ir::ImplType::Local
1267     } else {
1268         chalk_rust_ir::ImplType::External
1269     };
1270     let where_clauses = convert_where_clauses(db, impl_id.into(), &bound_vars);
1271     let negative = impl_data.is_negative;
1272     debug!(
1273         "impl {:?}: {}{} where {:?}",
1274         chalk_id,
1275         if negative { "!" } else { "" },
1276         trait_ref.display(db),
1277         where_clauses
1278     );
1279     let trait_ref = trait_ref.to_chalk(db);
1280
1281     let polarity = if negative {
1282         chalk_rust_ir::Polarity::Negative
1283     } else {
1284         chalk_rust_ir::Polarity::Positive
1285     };
1286
1287     let impl_datum_bound = chalk_rust_ir::ImplDatumBound { trait_ref, where_clauses };
1288     let trait_data = db.trait_data(trait_);
1289     let associated_ty_value_ids = impl_data
1290         .items
1291         .iter()
1292         .filter_map(|item| match item {
1293             AssocItemId::TypeAliasId(type_alias) => Some(*type_alias),
1294             _ => None,
1295         })
1296         .filter(|&type_alias| {
1297             // don't include associated types that don't exist in the trait
1298             let name = &db.type_alias_data(type_alias).name;
1299             trait_data.associated_type_by_name(name).is_some()
1300         })
1301         .map(|type_alias| AssocTyValue::TypeAlias(type_alias).to_chalk(db))
1302         .collect();
1303     debug!("impl_datum: {:?}", impl_datum_bound);
1304     let impl_datum = ImplDatum {
1305         binders: make_binders(impl_datum_bound, bound_vars.len()),
1306         impl_type,
1307         polarity,
1308         associated_ty_value_ids,
1309     };
1310     Arc::new(impl_datum)
1311 }
1312
1313 pub(crate) fn associated_ty_value_query(
1314     db: &dyn HirDatabase,
1315     krate: CrateId,
1316     id: AssociatedTyValueId,
1317 ) -> Arc<AssociatedTyValue> {
1318     let data: AssocTyValue = from_chalk(db, id);
1319     match data {
1320         AssocTyValue::TypeAlias(type_alias) => {
1321             type_alias_associated_ty_value(db, krate, type_alias)
1322         }
1323         _ => Arc::new(builtin::associated_ty_value(db, krate, data).to_chalk(db)),
1324     }
1325 }
1326
1327 fn type_alias_associated_ty_value(
1328     db: &dyn HirDatabase,
1329     _krate: CrateId,
1330     type_alias: TypeAliasId,
1331 ) -> Arc<AssociatedTyValue> {
1332     let type_alias_data = db.type_alias_data(type_alias);
1333     let impl_id = match type_alias.lookup(db.upcast()).container {
1334         AssocContainerId::ImplId(it) => it,
1335         _ => panic!("assoc ty value should be in impl"),
1336     };
1337
1338     let trait_ref = db.impl_trait(impl_id).expect("assoc ty value should not exist").value; // we don't return any assoc ty values if the impl'd trait can't be resolved
1339
1340     let assoc_ty = db
1341         .trait_data(trait_ref.trait_)
1342         .associated_type_by_name(&type_alias_data.name)
1343         .expect("assoc ty value should not exist"); // validated when building the impl data as well
1344     let ty = db.ty(type_alias.into());
1345     let value_bound = chalk_rust_ir::AssociatedTyValueBound { ty: ty.value.to_chalk(db) };
1346     let value = chalk_rust_ir::AssociatedTyValue {
1347         impl_id: Impl::ImplDef(impl_id).to_chalk(db),
1348         associated_ty_id: assoc_ty.to_chalk(db),
1349         value: make_binders(value_bound, ty.num_binders),
1350     };
1351     Arc::new(value)
1352 }
1353
1354 impl From<StructId> for crate::TypeCtorId {
1355     fn from(struct_id: StructId) -> Self {
1356         InternKey::from_intern_id(struct_id.0)
1357     }
1358 }
1359
1360 impl From<crate::TypeCtorId> for StructId {
1361     fn from(type_ctor_id: crate::TypeCtorId) -> Self {
1362         chalk_ir::AdtId(type_ctor_id.as_intern_id())
1363     }
1364 }
1365
1366 impl From<ImplId> for crate::traits::GlobalImplId {
1367     fn from(impl_id: ImplId) -> Self {
1368         InternKey::from_intern_id(impl_id.0)
1369     }
1370 }
1371
1372 impl From<crate::traits::GlobalImplId> for ImplId {
1373     fn from(impl_id: crate::traits::GlobalImplId) -> Self {
1374         chalk_ir::ImplId(impl_id.as_intern_id())
1375     }
1376 }
1377
1378 impl From<chalk_rust_ir::AssociatedTyValueId<Interner>> for crate::traits::AssocTyValueId {
1379     fn from(id: chalk_rust_ir::AssociatedTyValueId<Interner>) -> Self {
1380         Self::from_intern_id(id.0)
1381     }
1382 }
1383
1384 impl From<crate::traits::AssocTyValueId> for chalk_rust_ir::AssociatedTyValueId<Interner> {
1385     fn from(assoc_ty_value_id: crate::traits::AssocTyValueId) -> Self {
1386         chalk_rust_ir::AssociatedTyValueId(assoc_ty_value_id.as_intern_id())
1387     }
1388 }