src/librustc_traits/lowering/mod.rs

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