src/librustc_traits/lowering/mod.rs

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