src/librustc_traits/lowering/mod.rs

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