src/librustc_traits/lowering/mod.rs

   1 mod environment;
   2
   3 use rustc::hir::map::definitions::DefPathData;
   4 use rustc::hir::map::Map;
   5 use rustc::traits::{
   6     Clause, Clauses, DomainGoal, FromEnv, GoalKind, PolyDomainGoal, ProgramClause,
   7     ProgramClauseCategory, WellFormed, WhereClause,
   8 };
   9 use rustc::ty::query::Providers;
  10 use rustc::ty::subst::{InternalSubsts, Subst};
  11 use rustc::ty::{self, List, TyCtxt};
  12 use rustc_hir as hir;
  13 use rustc_hir::def::DefKind;
  14 use rustc_hir::def_id::DefId;
  15 use rustc_hir::intravisit::{self, NestedVisitorMap, Visitor};
  16 use rustc_span::symbol::sym;
  17 use syntax::ast;
  18
  19 use std::iter;
  20
  21 crate fn provide(p: &mut Providers<'_>) {
  22     *p = Providers {
  23         program_clauses_for,
  24         program_clauses_for_env: environment::program_clauses_for_env,
  25         environment: environment::environment,
  26         ..*p
  27     };
  28 }
  29
  30 crate trait Lower<T> {
  31     /// Lower a rustc construct (e.g., `ty::TraitPredicate`) to a chalk-like type.
  32     fn lower(&self) -> T;
  33 }
  34
  35 impl<T, U> Lower<Vec<U>> for Vec<T>
  36 where
  37     T: Lower<U>,
  38 {
  39     fn lower(&self) -> Vec<U> {
  40         self.iter().map(|item| item.lower()).collect()
  41     }
  42 }
  43
  44 impl<'tcx> Lower<WhereClause<'tcx>> for ty::TraitPredicate<'tcx> {
  45     fn lower(&self) -> WhereClause<'tcx> {
  46         WhereClause::Implemented(*self)
  47     }
  48 }
  49
  50 impl<'tcx> Lower<WhereClause<'tcx>> for ty::ProjectionPredicate<'tcx> {
  51     fn lower(&self) -> WhereClause<'tcx> {
  52         WhereClause::ProjectionEq(*self)
  53     }
  54 }
  55
  56 impl<'tcx> Lower<WhereClause<'tcx>> for ty::RegionOutlivesPredicate<'tcx> {
  57     fn lower(&self) -> WhereClause<'tcx> {
  58         WhereClause::RegionOutlives(*self)
  59     }
  60 }
  61
  62 impl<'tcx> Lower<WhereClause<'tcx>> for ty::TypeOutlivesPredicate<'tcx> {
  63     fn lower(&self) -> WhereClause<'tcx> {
  64         WhereClause::TypeOutlives(*self)
  65     }
  66 }
  67
  68 impl<'tcx, T> Lower<DomainGoal<'tcx>> for T
  69 where
  70     T: Lower<WhereClause<'tcx>>,
  71 {
  72     fn lower(&self) -> DomainGoal<'tcx> {
  73         DomainGoal::Holds(self.lower())
  74     }
  75 }
  76
  77 /// `ty::Binder` is used for wrapping a rustc construction possibly containing generic
  78 /// lifetimes, e.g., `for<'a> T: Fn(&'a i32)`. Instead of representing higher-ranked things
  79 /// in that leaf-form (i.e., `Holds(Implemented(Binder<TraitPredicate>))` in the previous
  80 /// example), we model them with quantified domain goals, e.g., as for the previous example:
  81 /// `forall<'a> { T: Fn(&'a i32) }` which corresponds to something like
  82 /// `Binder<Holds(Implemented(TraitPredicate))>`.
  83 impl<'tcx, T> Lower<PolyDomainGoal<'tcx>> for ty::Binder<T>
  84 where
  85     T: Lower<DomainGoal<'tcx>> + ty::fold::TypeFoldable<'tcx>,
  86 {
  87     fn lower(&self) -> PolyDomainGoal<'tcx> {
  88         self.map_bound_ref(|p| p.lower())
  89     }
  90 }
  91
  92 impl<'tcx> Lower<PolyDomainGoal<'tcx>> for ty::Predicate<'tcx> {
  93     fn lower(&self) -> PolyDomainGoal<'tcx> {
  94         use rustc::ty::Predicate;
  95
  96         match self {
  97             Predicate::Trait(predicate, _) => predicate.lower(),
  98             Predicate::RegionOutlives(predicate) => predicate.lower(),
  99             Predicate::TypeOutlives(predicate) => predicate.lower(),
 100             Predicate::Projection(predicate) => predicate.lower(),
 101
 102             Predicate::WellFormed(..)
 103             | Predicate::ObjectSafe(..)
 104             | Predicate::ClosureKind(..)
 105             | Predicate::Subtype(..)
 106             | Predicate::ConstEvaluatable(..) => bug!("unexpected predicate {}", self),
 107         }
 108     }
 109 }
 110
 111 /// Used for implied bounds related rules (see rustc guide).
 112 trait IntoFromEnvGoal {
 113     /// Transforms an existing goal into a `FromEnv` goal.
 114     fn into_from_env_goal(self) -> Self;
 115 }
 116
 117 /// Used for well-formedness related rules (see rustc guide).
 118 trait IntoWellFormedGoal {
 119     /// Transforms an existing goal into a `WellFormed` goal.
 120     fn into_well_formed_goal(self) -> Self;
 121 }
 122
 123 impl<'tcx> IntoFromEnvGoal for DomainGoal<'tcx> {
 124     fn into_from_env_goal(self) -> DomainGoal<'tcx> {
 125         use self::WhereClause::*;
 126
 127         match self {
 128             DomainGoal::Holds(Implemented(trait_ref)) => {
 129                 DomainGoal::FromEnv(FromEnv::Trait(trait_ref))
 130             }
 131             other => other,
 132         }
 133     }
 134 }
 135
 136 impl<'tcx> IntoWellFormedGoal for DomainGoal<'tcx> {
 137     fn into_well_formed_goal(self) -> DomainGoal<'tcx> {
 138         use self::WhereClause::*;
 139
 140         match self {
 141             DomainGoal::Holds(Implemented(trait_ref)) => {
 142                 DomainGoal::WellFormed(WellFormed::Trait(trait_ref))
 143             }
 144             other => other,
 145         }
 146     }
 147 }
 148
 149 crate fn program_clauses_for(tcx: TyCtxt<'_>, def_id: DefId) -> Clauses<'_> {
 150     // FIXME(eddyb) this should only be using `def_kind`.
 151     match tcx.def_key(def_id).disambiguated_data.data {
 152         DefPathData::TypeNs(..) => match tcx.def_kind(def_id) {
 153             Some(DefKind::Trait) | Some(DefKind::TraitAlias) => {
 154                 program_clauses_for_trait(tcx, def_id)
 155             }
 156             // FIXME(eddyb) deduplicate this `associated_item` call with
 157             // `program_clauses_for_associated_type_{value,def}`.
 158             Some(DefKind::AssocTy) => match tcx.associated_item(def_id).container {
 159                 ty::AssocItemContainer::ImplContainer(_) => {
 160                     program_clauses_for_associated_type_value(tcx, def_id)
 161                 }
 162                 ty::AssocItemContainer::TraitContainer(_) => {
 163                     program_clauses_for_associated_type_def(tcx, def_id)
 164                 }
 165             },
 166             Some(DefKind::Struct)
 167             | Some(DefKind::Enum)
 168             | Some(DefKind::TyAlias)
 169             | Some(DefKind::Union)
 170             | Some(DefKind::OpaqueTy) => program_clauses_for_type_def(tcx, def_id),
 171             _ => List::empty(),
 172         },
 173         DefPathData::Impl => program_clauses_for_impl(tcx, def_id),
 174         _ => List::empty(),
 175     }
 176 }
 177
 178 fn program_clauses_for_trait(tcx: TyCtxt<'_>, def_id: DefId) -> Clauses<'_> {
 179     // `trait Trait<P1..Pn> where WC { .. } // P0 == Self`
 180
 181     // Rule Implemented-From-Env (see rustc guide)
 182     //
 183     // ```
 184     // forall<Self, P1..Pn> {
 185     //   Implemented(Self: Trait<P1..Pn>) :- FromEnv(Self: Trait<P1..Pn>)
 186     // }
 187     // ```
 188
 189     let bound_vars = InternalSubsts::bound_vars_for_item(tcx, def_id);
 190
 191     // `Self: Trait<P1..Pn>`
 192     let trait_pred = ty::TraitPredicate { trait_ref: ty::TraitRef { def_id, substs: bound_vars } };
 193
 194     // `Implemented(Self: Trait<P1..Pn>)`
 195     let impl_trait: DomainGoal<'_> = trait_pred.lower();
 196
 197     // `FromEnv(Self: Trait<P1..Pn>)`
 198     let from_env_goal = tcx.mk_goal(impl_trait.into_from_env_goal().into_goal());
 199     let hypotheses = tcx.intern_goals(&[from_env_goal]);
 200
 201     // `Implemented(Self: Trait<P1..Pn>) :- FromEnv(Self: Trait<P1..Pn>)`
 202     let implemented_from_env = ProgramClause {
 203         goal: impl_trait,
 204         hypotheses,
 205         category: ProgramClauseCategory::ImpliedBound,
 206     };
 207
 208     let implemented_from_env = Clause::ForAll(ty::Binder::bind(implemented_from_env));
 209
 210     let predicates = tcx.predicates_defined_on(def_id).predicates;
 211
 212     // Warning: these where clauses are not substituted for bound vars yet,
 213     // so that we don't need to adjust binders in the `FromEnv` rules below
 214     // (see the FIXME).
 215     let where_clauses = &predicates.iter().map(|(wc, _)| wc.lower()).collect::<Vec<_>>();
 216
 217     // Rule Implied-Bound-From-Trait
 218     //
 219     // For each where clause WC:
 220     // ```
 221     // forall<Self, P1..Pn> {
 222     //   FromEnv(WC) :- FromEnv(Self: Trait<P1..Pn)
 223     // }
 224     // ```
 225
 226     // `FromEnv(WC) :- FromEnv(Self: Trait<P1..Pn>)`, for each where clause WC
 227     let implied_bound_clauses = where_clauses
 228         .iter()
 229         .cloned()
 230         // `FromEnv(WC) :- FromEnv(Self: Trait<P1..Pn>)`
 231         .map(|wc| {
 232             // we move binders to the left
 233             wc.map_bound(|goal| ProgramClause {
 234                 // FIXME: As where clauses can only bind lifetimes for now, and that named
 235                 // bound regions have a def-id, it is safe to just inject `bound_vars` and
 236                 // `hypotheses` (which contain named vars bound at index `0`) into this
 237                 // binding level. This may change if we ever allow where clauses to bind
 238                 // types (e.g. for GATs things), because bound types only use a `BoundVar`
 239                 // index (no def-id).
 240                 goal: goal.subst(tcx, bound_vars).into_from_env_goal(),
 241                 hypotheses,
 242
 243                 category: ProgramClauseCategory::ImpliedBound,
 244             })
 245         })
 246         .map(Clause::ForAll);
 247
 248     // Rule WellFormed-TraitRef
 249     //
 250     // Here `WC` denotes the set of all where clauses:
 251     // ```
 252     // forall<Self, P1..Pn> {
 253     //   WellFormed(Self: Trait<P1..Pn>) :- Implemented(Self: Trait<P1..Pn>) && WellFormed(WC)
 254     // }
 255     // ```
 256
 257     // `WellFormed(WC)`
 258     let wf_conditions = where_clauses
 259         .into_iter()
 260         .map(|wc| wc.subst(tcx, bound_vars))
 261         .map(|wc| wc.map_bound(|goal| goal.into_well_formed_goal()));
 262
 263     // `WellFormed(Self: Trait<P1..Pn>) :- Implemented(Self: Trait<P1..Pn>) && WellFormed(WC)`
 264     let wf_clause = ProgramClause {
 265         goal: DomainGoal::WellFormed(WellFormed::Trait(trait_pred)),
 266         hypotheses: tcx.mk_goals(
 267             iter::once(tcx.mk_goal(GoalKind::DomainGoal(impl_trait))).chain(
 268                 wf_conditions.map(|wc| tcx.mk_goal(GoalKind::from_poly_domain_goal(wc, tcx))),
 269             ),
 270         ),
 271         category: ProgramClauseCategory::WellFormed,
 272     };
 273     let wf_clause = Clause::ForAll(ty::Binder::bind(wf_clause));
 274
 275     tcx.mk_clauses(
 276         iter::once(implemented_from_env).chain(implied_bound_clauses).chain(iter::once(wf_clause)),
 277     )
 278 }
 279
 280 fn program_clauses_for_impl(tcx: TyCtxt<'tcx>, def_id: DefId) -> Clauses<'tcx> {
 281     if let ty::ImplPolarity::Negative = tcx.impl_polarity(def_id) {
 282         return List::empty();
 283     }
 284
 285     // Rule Implemented-From-Impl (see rustc guide)
 286     //
 287     // `impl<P0..Pn> Trait<A1..An> for A0 where WC { .. }`
 288     //
 289     // ```
 290     // forall<P0..Pn> {
 291     //   Implemented(A0: Trait<A1..An>) :- WC
 292     // }
 293     // ```
 294
 295     let bound_vars = InternalSubsts::bound_vars_for_item(tcx, def_id);
 296
 297     let trait_ref = tcx.impl_trait_ref(def_id).expect("not an impl").subst(tcx, bound_vars);
 298
 299     // `Implemented(A0: Trait<A1..An>)`
 300     let trait_pred = ty::TraitPredicate { trait_ref }.lower();
 301
 302     // `WC`
 303     let predicates = tcx.predicates_of(def_id).predicates;
 304     let where_clauses =
 305         predicates.iter().map(|(wc, _)| wc.lower()).map(|wc| wc.subst(tcx, bound_vars));
 306
 307     // `Implemented(A0: Trait<A1..An>) :- WC`
 308     let clause = ProgramClause {
 309         goal: trait_pred,
 310         hypotheses: tcx.mk_goals(
 311             where_clauses.map(|wc| tcx.mk_goal(GoalKind::from_poly_domain_goal(wc, tcx))),
 312         ),
 313         category: ProgramClauseCategory::Other,
 314     };
 315     tcx.mk_clauses(iter::once(Clause::ForAll(ty::Binder::bind(clause))))
 316 }
 317
 318 pub fn program_clauses_for_type_def(tcx: TyCtxt<'_>, def_id: DefId) -> Clauses<'_> {
 319     // Rule WellFormed-Type
 320     //
 321     // `struct Ty<P1..Pn> where WC1, ..., WCm`
 322     //
 323     // ```
 324     // forall<P1..Pn> {
 325     //   WellFormed(Ty<...>) :- WellFormed(WC1), ..., WellFormed(WCm)`
 326     // }
 327     // ```
 328
 329     let bound_vars = InternalSubsts::bound_vars_for_item(tcx, def_id);
 330
 331     // `Ty<...>`
 332     let ty = tcx.type_of(def_id).subst(tcx, bound_vars);
 333
 334     // Warning: these where clauses are not substituted for bound vars yet,
 335     // so that we don't need to adjust binders in the `FromEnv` rules below
 336     // (see the FIXME).
 337     let where_clauses =
 338         tcx.predicates_of(def_id).predicates.iter().map(|(wc, _)| wc.lower()).collect::<Vec<_>>();
 339
 340     // `WellFormed(Ty<...>) :- WellFormed(WC1), ..., WellFormed(WCm)`
 341     let well_formed_clause = ProgramClause {
 342         goal: DomainGoal::WellFormed(WellFormed::Ty(ty)),
 343         hypotheses: tcx.mk_goals(
 344             where_clauses
 345                 .iter()
 346                 .map(|wc| wc.subst(tcx, bound_vars))
 347                 .map(|wc| wc.map_bound(|bound| bound.into_well_formed_goal()))
 348                 .map(|wc| tcx.mk_goal(GoalKind::from_poly_domain_goal(wc, tcx))),
 349         ),
 350         category: ProgramClauseCategory::WellFormed,
 351     };
 352     let well_formed_clause = Clause::ForAll(ty::Binder::bind(well_formed_clause));
 353
 354     // Rule Implied-Bound-From-Type
 355     //
 356     // For each where clause `WC`:
 357     // ```
 358     // forall<P1..Pn> {
 359     //   FromEnv(WC) :- FromEnv(Ty<...>)
 360     // }
 361     // ```
 362
 363     // `FromEnv(Ty<...>)`
 364     let from_env_goal = tcx.mk_goal(DomainGoal::FromEnv(FromEnv::Ty(ty)).into_goal());
 365     let hypotheses = tcx.intern_goals(&[from_env_goal]);
 366
 367     // For each where clause `WC`:
 368     let from_env_clauses = where_clauses
 369         .into_iter()
 370         // `FromEnv(WC) :- FromEnv(Ty<...>)`
 371         .map(|wc| {
 372             // move the binders to the left
 373             wc.map_bound(|goal| ProgramClause {
 374                 // FIXME: we inject `bound_vars` and `hypotheses` into this binding
 375                 // level, which may be incorrect in the future: see the FIXME in
 376                 // `program_clauses_for_trait`.
 377                 goal: goal.subst(tcx, bound_vars).into_from_env_goal(),
 378                 hypotheses,
 379
 380                 category: ProgramClauseCategory::ImpliedBound,
 381             })
 382         })
 383         .map(Clause::ForAll);
 384
 385     tcx.mk_clauses(iter::once(well_formed_clause).chain(from_env_clauses))
 386 }
 387
 388 pub fn program_clauses_for_associated_type_def(tcx: TyCtxt<'_>, item_id: DefId) -> Clauses<'_> {
 389     // Rule ProjectionEq-Placeholder
 390     //
 391     // ```
 392     // trait Trait<P1..Pn> {
 393     //     type AssocType<Pn+1..Pm>;
 394     // }
 395     // ```
 396     //
 397     // `ProjectionEq` can succeed by skolemizing, see "associated type"
 398     // chapter for more:
 399     // ```
 400     // forall<Self, P1..Pn, Pn+1..Pm> {
 401     //     ProjectionEq(
 402     //         <Self as Trait<P1..Pn>>::AssocType<Pn+1..Pm> =
 403     //         (Trait::AssocType)<Self, P1..Pn, Pn+1..Pm>
 404     //     )
 405     // }
 406     // ```
 407
 408     let item = tcx.associated_item(item_id);
 409     debug_assert_eq!(item.kind, ty::AssocKind::Type);
 410     let trait_id = match item.container {
 411         ty::AssocItemContainer::TraitContainer(trait_id) => trait_id,
 412         _ => bug!("not an trait container"),
 413     };
 414
 415     let trait_bound_vars = InternalSubsts::bound_vars_for_item(tcx, trait_id);
 416     let trait_ref = ty::TraitRef { def_id: trait_id, substs: trait_bound_vars };
 417
 418     let projection_ty = ty::ProjectionTy::from_ref_and_name(tcx, trait_ref, item.ident);
 419     let placeholder_ty = tcx.mk_ty(ty::UnnormalizedProjection(projection_ty));
 420     let projection_eq =
 421         WhereClause::ProjectionEq(ty::ProjectionPredicate { projection_ty, ty: placeholder_ty });
 422
 423     let projection_eq_clause = ProgramClause {
 424         goal: DomainGoal::Holds(projection_eq),
 425         hypotheses: ty::List::empty(),
 426         category: ProgramClauseCategory::Other,
 427     };
 428     let projection_eq_clause = Clause::ForAll(ty::Binder::bind(projection_eq_clause));
 429
 430     // Rule WellFormed-AssocTy
 431     // ```
 432     // forall<Self, P1..Pn, Pn+1..Pm> {
 433     //     WellFormed((Trait::AssocType)<Self, P1..Pn, Pn+1..Pm>)
 434     //         :- WellFormed(Self: Trait<P1..Pn>)
 435     // }
 436     // ```
 437
 438     let trait_predicate = ty::TraitPredicate { trait_ref };
 439     let hypothesis =
 440         tcx.mk_goal(DomainGoal::WellFormed(WellFormed::Trait(trait_predicate)).into_goal());
 441
 442     let wf_clause = ProgramClause {
 443         goal: DomainGoal::WellFormed(WellFormed::Ty(placeholder_ty)),
 444         hypotheses: tcx.mk_goals(iter::once(hypothesis)),
 445         category: ProgramClauseCategory::WellFormed,
 446     };
 447     let wf_clause = Clause::ForAll(ty::Binder::bind(wf_clause));
 448
 449     // Rule Implied-Trait-From-AssocTy
 450     // ```
 451     // forall<Self, P1..Pn, Pn+1..Pm> {
 452     //     FromEnv(Self: Trait<P1..Pn>)
 453     //         :- FromEnv((Trait::AssocType)<Self, P1..Pn, Pn+1..Pm>)
 454     // }
 455     // ```
 456
 457     let hypothesis = tcx.mk_goal(DomainGoal::FromEnv(FromEnv::Ty(placeholder_ty)).into_goal());
 458
 459     let from_env_clause = ProgramClause {
 460         goal: DomainGoal::FromEnv(FromEnv::Trait(trait_predicate)),
 461         hypotheses: tcx.mk_goals(iter::once(hypothesis)),
 462         category: ProgramClauseCategory::ImpliedBound,
 463     };
 464     let from_env_clause = Clause::ForAll(ty::Binder::bind(from_env_clause));
 465
 466     // Rule ProjectionEq-Normalize
 467     //
 468     // ProjectionEq can succeed by normalizing:
 469     // ```
 470     // forall<Self, P1..Pn, Pn+1..Pm, U> {
 471     //   ProjectionEq(<Self as Trait<P1..Pn>>::AssocType<Pn+1..Pm> = U) :-
 472     //       Normalize(<Self as Trait<P1..Pn>>::AssocType<Pn+1..Pm> -> U)
 473     // }
 474     // ```
 475
 476     let offset = tcx.generics_of(trait_id).params.iter().map(|p| p.index).max().unwrap_or(0);
 477     // Add a new type param after the existing ones (`U` in the comment above).
 478     let ty_var = ty::Bound(ty::INNERMOST, ty::BoundVar::from_u32(offset + 1).into());
 479
 480     // `ProjectionEq(<Self as Trait<P1..Pn>>::AssocType<Pn+1..Pm> = U)`
 481     let projection = ty::ProjectionPredicate { projection_ty, ty: tcx.mk_ty(ty_var) };
 482
 483     // `Normalize(<A0 as Trait<A1..An>>::AssocType<Pn+1..Pm> -> U)`
 484     let hypothesis = tcx.mk_goal(DomainGoal::Normalize(projection).into_goal());
 485
 486     //  ProjectionEq(<Self as Trait<P1..Pn>>::AssocType<Pn+1..Pm> = U) :-
 487     //      Normalize(<Self as Trait<P1..Pn>>::AssocType<Pn+1..Pm> -> U)
 488     let normalize_clause = ProgramClause {
 489         goal: DomainGoal::Holds(WhereClause::ProjectionEq(projection)),
 490         hypotheses: tcx.mk_goals(iter::once(hypothesis)),
 491         category: ProgramClauseCategory::Other,
 492     };
 493     let normalize_clause = Clause::ForAll(ty::Binder::bind(normalize_clause));
 494
 495     let clauses = iter::once(projection_eq_clause)
 496         .chain(iter::once(wf_clause))
 497         .chain(iter::once(from_env_clause))
 498         .chain(iter::once(normalize_clause));
 499
 500     tcx.mk_clauses(clauses)
 501 }
 502
 503 pub fn program_clauses_for_associated_type_value(tcx: TyCtxt<'_>, item_id: DefId) -> Clauses<'_> {
 504     // Rule Normalize-From-Impl (see rustc guide)
 505     //
 506     // ```
 507     // impl<P0..Pn> Trait<A1..An> for A0 {
 508     //     type AssocType<Pn+1..Pm> = T;
 509     // }
 510     // ```
 511     //
 512     // FIXME: For the moment, we don't account for where clauses written on the associated
 513     // ty definition (i.e., in the trait def, as in `type AssocType<T> where T: Sized`).
 514     // ```
 515     // forall<P0..Pm> {
 516     //   forall<Pn+1..Pm> {
 517     //     Normalize(<A0 as Trait<A1..An>>::AssocType<Pn+1..Pm> -> T) :-
 518     //       Implemented(A0: Trait<A1..An>)
 519     //   }
 520     // }
 521     // ```
 522
 523     let item = tcx.associated_item(item_id);
 524     debug_assert_eq!(item.kind, ty::AssocKind::Type);
 525     let impl_id = match item.container {
 526         ty::AssocItemContainer::ImplContainer(impl_id) => impl_id,
 527         _ => bug!("not an impl container"),
 528     };
 529
 530     let impl_bound_vars = InternalSubsts::bound_vars_for_item(tcx, impl_id);
 531
 532     // `A0 as Trait<A1..An>`
 533     let trait_ref = tcx.impl_trait_ref(impl_id).unwrap().subst(tcx, impl_bound_vars);
 534
 535     // `T`
 536     let ty = tcx.type_of(item_id);
 537
 538     // `Implemented(A0: Trait<A1..An>)`
 539     let trait_implemented: DomainGoal<'_> = ty::TraitPredicate { trait_ref }.lower();
 540
 541     // `<A0 as Trait<A1..An>>::AssocType<Pn+1..Pm>`
 542     let projection_ty = ty::ProjectionTy::from_ref_and_name(tcx, trait_ref, item.ident);
 543
 544     // `Normalize(<A0 as Trait<A1..An>>::AssocType<Pn+1..Pm> -> T)`
 545     let normalize_goal = DomainGoal::Normalize(ty::ProjectionPredicate { projection_ty, ty });
 546
 547     // `Normalize(... -> T) :- ...`
 548     let normalize_clause = ProgramClause {
 549         goal: normalize_goal,
 550         hypotheses: tcx.mk_goals(iter::once(tcx.mk_goal(GoalKind::DomainGoal(trait_implemented)))),
 551         category: ProgramClauseCategory::Other,
 552     };
 553     let normalize_clause = Clause::ForAll(ty::Binder::bind(normalize_clause));
 554
 555     tcx.mk_clauses(iter::once(normalize_clause))
 556 }
 557
 558 pub fn dump_program_clauses(tcx: TyCtxt<'_>) {
 559     if !tcx.features().rustc_attrs {
 560         return;
 561     }
 562
 563     let mut visitor = ClauseDumper { tcx };
 564     tcx.hir().krate().visit_all_item_likes(&mut visitor.as_deep_visitor());
 565 }
 566
 567 struct ClauseDumper<'tcx> {
 568     tcx: TyCtxt<'tcx>,
 569 }
 570
 571 impl ClauseDumper<'tcx> {
 572     fn process_attrs(&mut self, hir_id: hir::HirId, attrs: &[ast::Attribute]) {
 573         let def_id = self.tcx.hir().local_def_id(hir_id);
 574         for attr in attrs {
 575             let mut clauses = None;
 576
 577             if attr.check_name(sym::rustc_dump_program_clauses) {
 578                 clauses = Some(self.tcx.program_clauses_for(def_id));
 579             }
 580
 581             if attr.check_name(sym::rustc_dump_env_program_clauses) {
 582                 let environment = self.tcx.environment(def_id);
 583                 clauses = Some(self.tcx.program_clauses_for_env(environment));
 584             }
 585
 586             if let Some(clauses) = clauses {
 587                 let mut err = self.tcx.sess.struct_span_err(attr.span, "program clause dump");
 588
 589                 let mut strings: Vec<_> = clauses.iter().map(|clause| clause.to_string()).collect();
 590
 591                 strings.sort();
 592
 593                 for string in strings {
 594                     err.note(&string);
 595                 }
 596
 597                 err.emit();
 598             }
 599         }
 600     }
 601 }
 602
 603 impl Visitor<'tcx> for ClauseDumper<'tcx> {
 604     type Map = Map<'tcx>;
 605
 606     fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, Self::Map> {
 607         NestedVisitorMap::OnlyBodies(&self.tcx.hir())
 608     }
 609
 610     fn visit_item(&mut self, item: &'tcx hir::Item<'tcx>) {
 611         self.process_attrs(item.hir_id, &item.attrs);
 612         intravisit::walk_item(self, item);
 613     }
 614
 615     fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem<'tcx>) {
 616         self.process_attrs(trait_item.hir_id, &trait_item.attrs);
 617         intravisit::walk_trait_item(self, trait_item);
 618     }
 619
 620     fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem<'tcx>) {
 621         self.process_attrs(impl_item.hir_id, &impl_item.attrs);
 622         intravisit::walk_impl_item(self, impl_item);
 623     }
 624
 625     fn visit_struct_field(&mut self, s: &'tcx hir::StructField<'tcx>) {
 626         self.process_attrs(s.hir_id, &s.attrs);
 627         intravisit::walk_struct_field(self, s);
 628     }
 629 }