Add MVP for chalkification

12 files changed, 519 insertions, 0 deletions

diff --git a/src/librustc/dep_graph/dep_node.rs b/src/librustc/dep_graph/dep_node.rs
index 8d7fef90b75..744e3a5eaab 100644
--- a/src/librustc/dep_graph/dep_node.rs
+++ b/src/librustc/dep_graph/dep_node.rs
@@ -648,6 +648,8 @@ define_dep_nodes!( <'tcx>
     [] GetSymbolExportLevel(DefId),
 
     [input] Features,
+
+    [] ProgramClausesFor(DefId),
 );
 
 trait DepNodeParams<'a, 'gcx: 'tcx + 'a, 'tcx: 'a> : fmt::Debug {
diff --git a/src/librustc/ich/impls_ty.rs b/src/librustc/ich/impls_ty.rs
index 4eb4f0edafe..868ce831d13 100644
--- a/src/librustc/ich/impls_ty.rs
+++ b/src/librustc/ich/impls_ty.rs
@@ -1286,3 +1286,86 @@ impl_stable_hash_for!(struct infer::canonical::QueryRegionConstraints<'tcx> {
 impl_stable_hash_for!(enum infer::canonical::Certainty {
     Proven, Ambiguous
 });
+
+impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for traits::WhereClauseAtom<'tcx> {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a>,
+                                          hasher: &mut StableHasher<W>) {
+        use traits::WhereClauseAtom::*;
+
+        mem::discriminant(self).hash_stable(hcx, hasher);
+        match *self {
+            Implemented(ref trait_ref) => trait_ref.hash_stable(hcx, hasher),
+            ProjectionEq(ref projection) => projection.hash_stable(hcx, hasher),
+        }
+    }
+}
+
+impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for traits::DomainGoal<'tcx> {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a>,
+                                          hasher: &mut StableHasher<W>) {
+        use traits::DomainGoal::*;
+
+        mem::discriminant(self).hash_stable(hcx, hasher);
+        match *self {
+            Holds(ref where_clause) |
+            WellFormed(ref where_clause) |
+            FromEnv(ref where_clause) => where_clause.hash_stable(hcx, hasher),
+
+            WellFormedTy(ref ty) => ty.hash_stable(hcx, hasher),
+            FromEnvTy(ref ty) => ty.hash_stable(hcx, hasher),
+            RegionOutlives(ref predicate) => predicate.hash_stable(hcx, hasher),
+            TypeOutlives(ref predicate) => predicate.hash_stable(hcx, hasher),
+        }
+    }
+}
+
+impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for traits::LeafGoal<'tcx> {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a>,
+                                          hasher: &mut StableHasher<W>) {
+        use traits::LeafGoal::*;
+
+        mem::discriminant(self).hash_stable(hcx, hasher);
+        match *self {
+            DomainGoal(ref domain_goal) => domain_goal.hash_stable(hcx, hasher),
+        }
+    }
+}
+
+impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for traits::Goal<'tcx> {
+    fn hash_stable<W: StableHasherResult>(&self,
+                                          hcx: &mut StableHashingContext<'a>,
+                                          hasher: &mut StableHasher<W>) {
+        use traits::Goal::*;
+
+        mem::discriminant(self).hash_stable(hcx, hasher);
+        match *self {
+            Implies(ref hypotheses, ref goal) => {
+                hypotheses.hash_stable(hcx, hasher);
+                goal.hash_stable(hcx, hasher);
+            },
+            And(ref goal1, ref goal2) => {
+                goal1.hash_stable(hcx, hasher);
+                goal2.hash_stable(hcx, hasher);
+            }
+            Not(ref goal) => goal.hash_stable(hcx, hasher),
+            Leaf(ref leaf_goal) => leaf_goal.hash_stable(hcx, hasher),
+            Quantified(quantifier, ref goal) => {
+                quantifier.hash_stable(hcx, hasher);
+                goal.hash_stable(hcx, hasher);
+            },
+        }
+    }
+}
+
+impl_stable_hash_for!(enum traits::QuantifierKind {
+    Universal,
+    Existential
+});
+
+impl_stable_hash_for!(struct traits::ProgramClause<'tcx> {
+    consequence,
+    conditions
+});
diff --git a/src/librustc/traits/lowering.rs b/src/librustc/traits/lowering.rs
new file mode 100644
index 00000000000..4f7e66628d4
--- /dev/null
+++ b/src/librustc/traits/lowering.rs
@@ -0,0 +1,147 @@
+// Copyright 2018 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use hir::{self, ImplPolarity};
+use hir::def_id::DefId;
+use hir::intravisit::{self, NestedVisitorMap, Visitor};
+use ty::{self, PolyTraitPredicate, TraitPredicate, PolyProjectionPredicate, TyCtxt, Predicate};
+use super::{DomainGoal, ProgramClause, WhereClauseAtom};
+use rustc_data_structures::sync::Lrc;
+use syntax::ast;
+
+trait Lower<T> {
+    fn lower(&self) -> T;
+}
+
+impl<T, U> Lower<Vec<U>> for Vec<T> where T: Lower<U> {
+    fn lower(&self) -> Vec<U> {
+        self.iter().map(|item| item.lower()).collect()
+    }
+}
+
+impl<'tcx> Lower<WhereClauseAtom<'tcx>> for PolyTraitPredicate<'tcx> {
+    fn lower(&self) -> WhereClauseAtom<'tcx> {
+        WhereClauseAtom::Implemented(*self)
+    }
+}
+
+impl<'tcx> Lower<WhereClauseAtom<'tcx>> for PolyProjectionPredicate<'tcx> {
+    fn lower(&self) -> WhereClauseAtom<'tcx> {
+        WhereClauseAtom::ProjectionEq(*self)
+    }
+}
+
+impl<'tcx, T> Lower<DomainGoal<'tcx>> for T where T: Lower<WhereClauseAtom<'tcx>> {
+    fn lower(&self) -> DomainGoal<'tcx> {
+        DomainGoal::Holds(self.lower())
+    }
+}
+
+impl<'tcx> Lower<DomainGoal<'tcx>> for Predicate<'tcx> {
+    fn lower(&self) -> DomainGoal<'tcx> {
+        use self::Predicate::*;
+
+        match *self {
+            Trait(predicate) => predicate.lower(),
+            RegionOutlives(predicate) => DomainGoal::RegionOutlives(predicate),
+            TypeOutlives(predicate) => DomainGoal::TypeOutlives(predicate),
+            Projection(predicate) => predicate.lower(),
+            WellFormed(ty) => DomainGoal::WellFormedTy(ty),
+            ObjectSafe(..) |
+            ClosureKind(..) |
+            Subtype(..) |
+            ConstEvaluatable(..) => unimplemented!(),
+
+        }
+    }
+}
+
+pub fn program_clauses_for<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId)
+    -> Lrc<Vec<ProgramClause<'tcx>>>
+{
+    let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
+    let item = tcx.hir.expect_item(node_id);
+    match item.node {
+        hir::ItemImpl(..) => program_clauses_for_impl(tcx, def_id),
+        _ => Lrc::new(vec![]),
+    }
+}
+
+fn program_clauses_for_impl<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, def_id: DefId)
+    -> Lrc<Vec<ProgramClause<'tcx>>>
+{
+    if let ImplPolarity::Negative = tcx.impl_polarity(def_id) {
+        return Lrc::new(vec![]);
+    }
+
+    let trait_ref = tcx.impl_trait_ref(def_id).unwrap();
+    let trait_ref = ty::Binder(TraitPredicate { trait_ref }).lower();
+    let where_clauses = tcx.predicates_of(def_id).predicates.lower();
+
+    let clause = ProgramClause {
+        consequence: trait_ref,
+        conditions: where_clauses.into_iter().map(|wc| wc.into()).collect(),
+    };
+
+    Lrc::new(vec![clause])
+}
+
+pub fn dump_program_clauses<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) {
+    if !tcx.features().rustc_attrs {
+        return;
+    }
+
+    let mut visitor = ClauseDumper { tcx };
+    tcx.hir.krate().visit_all_item_likes(&mut visitor.as_deep_visitor());
+}
+
+struct ClauseDumper<'a, 'tcx: 'a> {
+    tcx: TyCtxt<'a, 'tcx, 'tcx>,
+}
+
+impl <'a, 'tcx> ClauseDumper<'a, 'tcx > {
+    fn process_attrs(&mut self, node_id: ast::NodeId, attrs: &[ast::Attribute]) {
+        let def_id = self.tcx.hir.local_def_id(node_id);
+        for attr in attrs {
+            if attr.check_name("rustc_dump_program_clauses") {
+                let clauses = self.tcx.program_clauses_for(def_id);
+                for clause in &*clauses {
+                    self.tcx.sess.struct_span_err(attr.span, &format!("{}", clause)).emit();
+                }
+            }
+        }
+    }
+}
+
+impl<'a, 'tcx> Visitor<'tcx> for ClauseDumper<'a, 'tcx> {
+    fn nested_visit_map<'this>(&'this mut self) -> NestedVisitorMap<'this, 'tcx> {
+        NestedVisitorMap::OnlyBodies(&self.tcx.hir)
+    }
+
+    fn visit_item(&mut self, item: &'tcx hir::Item) {
+        self.process_attrs(item.id, &item.attrs);
+        intravisit::walk_item(self, item);
+    }
+
+    fn visit_trait_item(&mut self, trait_item: &'tcx hir::TraitItem) {
+        self.process_attrs(trait_item.id, &trait_item.attrs);
+        intravisit::walk_trait_item(self, trait_item);
+    }
+
+    fn visit_impl_item(&mut self, impl_item: &'tcx hir::ImplItem) {
+        self.process_attrs(impl_item.id, &impl_item.attrs);
+        intravisit::walk_impl_item(self, impl_item);
+    }
+
+    fn visit_struct_field(&mut self, s: &'tcx hir::StructField) {
+        self.process_attrs(s.id, &s.attrs);
+        intravisit::walk_struct_field(self, s);
+    }
+}
diff --git a/src/librustc/traits/mod.rs b/src/librustc/traits/mod.rs
index a2a5aa246cf..8b2f96ce875 100644
--- a/src/librustc/traits/mod.rs
+++ b/src/librustc/traits/mod.rs
@@ -29,6 +29,7 @@ use infer::{InferCtxt};
 
 use rustc_data_structures::sync::Lrc;
 use std::rc::Rc;
+use std::convert::From;
 use syntax::ast;
 use syntax_pos::{Span, DUMMY_SP};
 
@@ -62,6 +63,7 @@ mod specialize;
 mod structural_impls;
 pub mod trans;
 mod util;
+mod lowering;
 
 pub mod query;
 
@@ -244,6 +246,59 @@ pub type Obligations<'tcx, O> = Vec<Obligation<'tcx, O>>;
 pub type PredicateObligations<'tcx> = Vec<PredicateObligation<'tcx>>;
 pub type TraitObligations<'tcx> = Vec<TraitObligation<'tcx>>;
 
+#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
+pub enum WhereClauseAtom<'tcx> {
+    Implemented(ty::PolyTraitPredicate<'tcx>),
+    ProjectionEq(ty::PolyProjectionPredicate<'tcx>),
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
+pub enum DomainGoal<'tcx> {
+    Holds(WhereClauseAtom<'tcx>),
+    WellFormed(WhereClauseAtom<'tcx>),
+    FromEnv(WhereClauseAtom<'tcx>),
+    WellFormedTy(Ty<'tcx>),
+    FromEnvTy(Ty<'tcx>),
+    RegionOutlives(ty::PolyRegionOutlivesPredicate<'tcx>),
+    TypeOutlives(ty::PolyTypeOutlivesPredicate<'tcx>),
+}
+
+#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
+pub enum LeafGoal<'tcx> {
+    DomainGoal(DomainGoal<'tcx>),
+}
+
+#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
+pub enum QuantifierKind {
+    Universal,
+    Existential,
+}
+
+#[derive(Clone, PartialEq, Eq, Hash, Debug)]
+pub enum Goal<'tcx> {
+    Implies(Vec<DomainGoal<'tcx>>, Box<Goal<'tcx>>),
+    And(Box<Goal<'tcx>>, Box<Goal<'tcx>>),
+    Not(Box<Goal<'tcx>>),
+    Leaf(LeafGoal<'tcx>),
+    Quantified(QuantifierKind, Box<ty::Binder<Goal<'tcx>>>)
+}
+
+impl<'tcx> From<DomainGoal<'tcx>> for Goal<'tcx> {
+    fn from(domain_goal: DomainGoal<'tcx>) -> Self {
+        Goal::Leaf(LeafGoal::DomainGoal(domain_goal))
+    }
+}
+
+#[derive(Clone, PartialEq, Eq, Hash, Debug)]
+pub struct ProgramClause<'tcx> {
+    pub consequence: DomainGoal<'tcx>,
+    pub conditions: Vec<Goal<'tcx>>,
+}
+
+pub fn dump_program_clauses<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) {
+    lowering::dump_program_clauses(tcx)
+}
+
 pub type Selection<'tcx> = Vtable<'tcx, PredicateObligation<'tcx>>;
 
 #[derive(Clone,Debug)]
@@ -915,6 +970,7 @@ pub fn provide(providers: &mut ty::maps::Providers) {
         specialization_graph_of: specialize::specialization_graph_provider,
         specializes: specialize::specializes,
         trans_fulfill_obligation: trans::trans_fulfill_obligation,
+        program_clauses_for: lowering::program_clauses_for,
         vtable_methods,
         substitute_normalize_and_test_predicates,
         ..*providers
diff --git a/src/librustc/traits/structural_impls.rs b/src/librustc/traits/structural_impls.rs
index a2d98a456f4..62881013c4c 100644
--- a/src/librustc/traits/structural_impls.rs
+++ b/src/librustc/traits/structural_impls.rs
@@ -425,3 +425,186 @@ BraceStructTypeFoldableImpl! {
         obligations
     } where T: TypeFoldable<'tcx>
 }
+
+impl<'tcx> fmt::Display for traits::WhereClauseAtom<'tcx> {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        use traits::WhereClauseAtom::*;
+        match *self {
+            Implemented(ref trait_ref) => write!(fmt, "Implemented({})", trait_ref),
+            ProjectionEq(ref projection) => write!(fmt, "ProjectionEq({})", projection),
+        }
+    }
+}
+
+impl<'tcx> fmt::Display for traits::DomainGoal<'tcx> {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        use traits::DomainGoal::*;
+        use traits::WhereClauseAtom::*;
+        match *self {
+            Holds(wc) => write!(fmt, "{}", wc),
+            WellFormed(Implemented(ref trait_ref)) => write!(fmt, "WellFormed({})", trait_ref),
+            WellFormed(ProjectionEq(ref projection)) => write!(fmt, "WellFormed({})", projection),
+            FromEnv(Implemented(ref trait_ref)) => write!(fmt, "FromEnv({})", trait_ref),
+            FromEnv(ProjectionEq(ref projection)) => write!(fmt, "FromEnv({})", projection),
+            WellFormedTy(ref ty) => write!(fmt, "WellFormed({})", ty),
+            FromEnvTy(ref ty) => write!(fmt, "FromEnv({})", ty),
+            RegionOutlives(ref predicate) => write!(fmt, "RegionOutlives({})", predicate),
+            TypeOutlives(ref predicate) => write!(fmt, "TypeOutlives({})", predicate),
+        }
+    }
+}
+
+impl fmt::Display for traits::QuantifierKind {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        use traits::QuantifierKind::*;
+        match *self {
+            Universal => write!(fmt, "forall"),
+            Existential => write!(fmt, "exists"),
+        }
+    }
+}
+
+impl<'tcx> fmt::Display for traits::LeafGoal<'tcx> {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        use traits::LeafGoal::*;
+        match *self {
+            DomainGoal(ref domain_goal) => write!(fmt, "{}", domain_goal),
+        }
+    }
+}
+
+impl<'tcx> fmt::Display for traits::Goal<'tcx> {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        use traits::Goal::*;
+        match *self {
+            Implies(ref hypotheses, ref goal) => {
+                write!(fmt, "if (")?;
+                for (index, hyp) in hypotheses.iter().enumerate() {
+                    if index > 0 {
+                        write!(fmt, ", ")?;
+                    }
+                    write!(fmt, "{}", hyp)?;
+                }
+                write!(fmt, ") {{ {} }}", goal)
+            }
+            And(ref goal1, ref goal2) => write!(fmt, "({}, {})", goal1, goal2),
+            Not(ref goal) => write!(fmt, "not {{ {} }}", goal),
+            Leaf(ref goal) => write!(fmt, "{}", goal),
+            Quantified(qkind, ref goal) => {
+                // FIXME: appropriate binder names
+                write!(fmt, "{}<> {{ {} }}", qkind, goal.skip_binder())
+            }
+        }
+    }
+}
+
+impl<'tcx> fmt::Display for traits::ProgramClause<'tcx> {
+    fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+        write!(fmt, "{}", self.consequence)?;
+        if self.conditions.is_empty() {
+            write!(fmt, ".")?;
+        } else {
+            write!(fmt, " :- ")?;
+            for (index, condition) in self.conditions.iter().enumerate() {
+                if index > 0 {
+                    write!(fmt, ", ")?;
+                }
+                write!(fmt, "{}", condition)?;
+            }
+        }
+        Ok(())
+    }
+}
+
+impl<'tcx> TypeFoldable<'tcx> for traits::WhereClauseAtom<'tcx> {
+    fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
+        use traits::WhereClauseAtom::*;
+        match *self {
+            Implemented(ref trait_ref) => Implemented(trait_ref.fold_with(folder)),
+            ProjectionEq(ref projection) => ProjectionEq(projection.fold_with(folder)),
+        }
+    }
+
+    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
+        use traits::WhereClauseAtom::*;
+        match *self {
+            Implemented(ref trait_ref) => trait_ref.visit_with(visitor),
+            ProjectionEq(ref projection) => projection.visit_with(visitor),
+        }
+    }
+}
+
+impl<'tcx> TypeFoldable<'tcx> for traits::DomainGoal<'tcx> {
+    fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
+        use traits::DomainGoal::*;
+        match *self {
+            Holds(ref wc) => Holds(wc.fold_with(folder)),
+            WellFormed(ref wc) => WellFormed(wc.fold_with(folder)),
+            FromEnv(ref wc) => FromEnv(wc.fold_with(folder)),
+            WellFormedTy(ref ty) => WellFormedTy(ty.fold_with(folder)),
+            FromEnvTy(ref ty) => FromEnvTy(ty.fold_with(folder)),
+            RegionOutlives(ref predicate) => RegionOutlives(predicate.fold_with(folder)),
+            TypeOutlives(ref predicate) => TypeOutlives(predicate.fold_with(folder)),
+        }
+    }
+
+    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
+        use traits::DomainGoal::*;
+        match *self {
+            Holds(ref wc) |
+            WellFormed(ref wc) |
+            FromEnv(ref wc) => wc.visit_with(visitor),
+            WellFormedTy(ref ty) |
+            FromEnvTy(ref ty) => ty.visit_with(visitor),
+            RegionOutlives(ref predicate) => predicate.visit_with(visitor),
+            TypeOutlives(ref predicate) => predicate.visit_with(visitor),
+        }
+    }
+}
+
+impl<'tcx> TypeFoldable<'tcx> for traits::LeafGoal<'tcx> {
+    fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
+        use traits::LeafGoal::*;
+        match *self {
+            DomainGoal(ref domain_goal) => DomainGoal(domain_goal.fold_with(folder)),
+        }
+    }
+
+    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
+        use traits::LeafGoal::*;
+        match *self {
+            DomainGoal(ref domain_goal) => domain_goal.visit_with(visitor),
+        }
+    }
+}
+
+impl<'tcx> TypeFoldable<'tcx> for traits::Goal<'tcx> {
+    fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
+        use traits::Goal::*;
+        match *self {
+            Implies(ref hypotheses, ref goal) => {
+                Implies(
+                    hypotheses.iter().map(|hyp| hyp.fold_with(folder)).collect(),
+                    goal.fold_with(folder)
+                )
+            },
+            And(ref goal1, ref goal2) => And(goal1.fold_with(folder), goal2.fold_with(folder)),
+            Not(ref goal) => Not(goal.fold_with(folder)),
+            Leaf(ref leaf_goal) => Leaf(leaf_goal.fold_with(folder)),
+            Quantified(qkind, ref goal) => Quantified(qkind, goal.fold_with(folder)),
+        }
+    }
+
+    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
+        use traits::Goal::*;
+        match *self {
+            Implies(ref hypotheses, ref goal) => {
+                hypotheses.iter().any(|hyp| hyp.visit_with(visitor)) || goal.visit_with(visitor)
+            }
+            And(ref goal1, ref goal2) => goal1.visit_with(visitor) || goal2.visit_with(visitor),
+            Not(ref goal) => goal.visit_with(visitor),
+            Leaf(ref leaf_goal) => leaf_goal.visit_with(visitor),
+            Quantified(_, ref goal) => goal.visit_with(visitor),
+        }
+    }
+}
diff --git a/src/librustc/ty/maps/config.rs b/src/librustc/ty/maps/config.rs
index dbfe7770bbd..abda7a2cd09 100644
--- a/src/librustc/ty/maps/config.rs
+++ b/src/librustc/ty/maps/config.rs
@@ -681,6 +681,12 @@ impl<'tcx> QueryDescription<'tcx> for queries::generics_of<'tcx> {
     }
 }
 
+impl<'tcx> QueryDescription<'tcx> for queries::program_clauses_for<'tcx> {
+    fn describe(_tcx: TyCtxt, _: DefId) -> String {
+        format!("generating chalk-style clauses")
+    }
+}
+
 macro_rules! impl_disk_cacheable_query(
     ($query_name:ident, |$key:tt| $cond:expr) => {
         impl<'tcx> QueryDescription<'tcx> for queries::$query_name<'tcx> {
diff --git a/src/librustc/ty/maps/mod.rs b/src/librustc/ty/maps/mod.rs
index 7d726d2e3cd..087c7d6d44d 100644
--- a/src/librustc/ty/maps/mod.rs
+++ b/src/librustc/ty/maps/mod.rs
@@ -38,6 +38,7 @@ use traits::query::{CanonicalProjectionGoal, CanonicalTyGoal, NoSolution};
 use traits::query::dropck_outlives::{DtorckConstraint, DropckOutlivesResult};
 use traits::query::normalize::NormalizationResult;
 use traits::specialization_graph;
+use traits::ProgramClause;
 use ty::{self, CrateInherentImpls, ParamEnvAnd, Ty, TyCtxt};
 use ty::steal::Steal;
 use ty::subst::Substs;
@@ -417,6 +418,8 @@ define_maps! { <'tcx>
         -> usize,
 
     [] fn features_query: features_node(CrateNum) -> Lrc<feature_gate::Features>,
+
+    [] fn program_clauses_for: ProgramClausesFor(DefId) -> Lrc<Vec<ProgramClause<'tcx>>>,
 }
 
 //////////////////////////////////////////////////////////////////////
diff --git a/src/librustc/ty/maps/plumbing.rs b/src/librustc/ty/maps/plumbing.rs
index bc7186f781a..dd65d4b4190 100644
--- a/src/librustc/ty/maps/plumbing.rs
+++ b/src/librustc/ty/maps/plumbing.rs
@@ -935,6 +935,8 @@ pub fn force_from_dep_node<'a, 'gcx, 'lcx>(tcx: TyCtxt<'a, 'gcx, 'lcx>,
 
         DepKind::GetSymbolExportLevel => { force!(symbol_export_level, def_id!()); }
         DepKind::Features => { force!(features_query, LOCAL_CRATE); }
+
+        DepKind::ProgramClausesFor => { force!(program_clauses_for, def_id!()); }
     }
 
     true
diff --git a/src/librustc_driver/driver.rs b/src/librustc_driver/driver.rs
index 542f818c381..69257e3e113 100644
--- a/src/librustc_driver/driver.rs
+++ b/src/librustc_driver/driver.rs
@@ -1089,6 +1089,8 @@ pub fn phase_3_run_analysis_passes<'tcx, F, R>(trans: &TransCrate,
 
         time(sess, "lint checking", || lint::check_crate(tcx));
 
+        time(time_passes, "dumping chalk-like clauses", || traits::dump_program_clauses(tcx));
+
         return Ok(f(tcx, analysis, rx, tcx.sess.compile_status()));
     })
 }
diff --git a/src/libsyntax/feature_gate.rs b/src/libsyntax/feature_gate.rs
index ec9a15d9f2b..ea2d907331a 100644
--- a/src/libsyntax/feature_gate.rs
+++ b/src/libsyntax/feature_gate.rs
@@ -831,6 +831,13 @@ pub const BUILTIN_ATTRIBUTES: &'static [(&'static str, AttributeType, AttributeG
                                                           across crates and will never be stable",
                                                           cfg_fn!(rustc_attrs))),
 
+    ("rustc_dump_program_clauses", Whitelisted, Gated(Stability::Unstable,
+                                                     "rustc_attrs",
+                                                     "the `#[rustc_dump_program_clauses]` \
+                                                      attribute is just used for rustc unit \
+                                                      tests and will never be stable",
+                                                     cfg_fn!(rustc_attrs))),
+
     // RFC #2094
     ("nll", Whitelisted, Gated(Stability::Unstable,
                                "nll",
diff --git a/src/test/ui/chalkify/lower_impl.rs b/src/test/ui/chalkify/lower_impl.rs
new file mode 100644
index 00000000000..2083ada6d2d
--- /dev/null
+++ b/src/test/ui/chalkify/lower_impl.rs
@@ -0,0 +1,20 @@
+// Copyright 2018 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![feature(rustc_attrs)]
+
+trait Foo { }
+
+#[rustc_dump_program_clauses] //~ ERROR Implemented(T: Foo) :-
+impl<T: 'static> Foo for T where T: Iterator<Item = i32> { }
+
+fn main() {
+    println!("hello");
+}
diff --git a/src/test/ui/chalkify/lower_impl.stderr b/src/test/ui/chalkify/lower_impl.stderr
new file mode 100644
index 00000000000..8645e4506ef
--- /dev/null
+++ b/src/test/ui/chalkify/lower_impl.stderr
@@ -0,0 +1,8 @@
+error: Implemented(T: Foo) :- ProjectionEq(<T as std::iter::Iterator>::Item == i32), TypeOutlives(T : 'static), Implemented(T: std::iter::Iterator), Implemented(T: std::marker::Sized)
+  --> $DIR/lower_impl.rs:15:1
+   |
+LL | #[rustc_dump_program_clauses] //~ ERROR Implemented(T: Foo) :-
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: aborting due to previous error
+