first draft of `program_clauses_for_env`

This computes the transitive closure of traits that appear in the
environment and then appends their clauses. It needs some work, but
it's in the right direction.

10 files changed, 145 insertions, 18 deletions

diff --git a/src/librustc/dep_graph/dep_node.rs b/src/librustc/dep_graph/dep_node.rs
index b4f39439d5b..18bf54297af 100644
--- a/src/librustc/dep_graph/dep_node.rs
+++ b/src/librustc/dep_graph/dep_node.rs
@@ -655,6 +655,7 @@ define_dep_nodes!( <'tcx>
     [input] Features,
 
     [] ProgramClausesFor(DefId),
+    [] ProgramClausesForEnv(ParamEnv<'tcx>),
     [] WasmImportModuleMap(CrateNum),
     [] ForeignModules(CrateNum),
 
diff --git a/src/librustc/ty/maps/config.rs b/src/librustc/ty/maps/config.rs
index fea7de955e0..735fe06560f 100644
--- a/src/librustc/ty/maps/config.rs
+++ b/src/librustc/ty/maps/config.rs
@@ -717,6 +717,12 @@ impl<'tcx> QueryDescription<'tcx> for queries::program_clauses_for<'tcx> {
     }
 }
 
+impl<'tcx> QueryDescription<'tcx> for queries::program_clauses_for_env<'tcx> {
+    fn describe(_tcx: TyCtxt, _: ty::ParamEnv<'tcx>) -> String {
+        format!("generating chalk-style clauses for param env")
+    }
+}
+
 impl<'tcx> QueryDescription<'tcx> for queries::wasm_import_module_map<'tcx> {
     fn describe(_tcx: TyCtxt, _: CrateNum) -> String {
         format!("wasm import module map")
diff --git a/src/librustc/ty/maps/keys.rs b/src/librustc/ty/maps/keys.rs
index b8167ec9186..72f2cb49abc 100644
--- a/src/librustc/ty/maps/keys.rs
+++ b/src/librustc/ty/maps/keys.rs
@@ -154,6 +154,15 @@ impl<'tcx> Key for Ty<'tcx> {
     }
 }
 
+impl<'tcx> Key for ty::ParamEnv<'tcx> {
+    fn map_crate(&self) -> CrateNum {
+        LOCAL_CRATE
+    }
+    fn default_span(&self, _: TyCtxt) -> Span {
+        DUMMY_SP
+    }
+}
+
 impl<'tcx, T: Key> Key for ty::ParamEnvAnd<'tcx, T> {
     fn map_crate(&self) -> CrateNum {
         self.value.map_crate()
diff --git a/src/librustc/ty/maps/mod.rs b/src/librustc/ty/maps/mod.rs
index 0ab9f16dab4..368e9dc0fad 100644
--- a/src/librustc/ty/maps/mod.rs
+++ b/src/librustc/ty/maps/mod.rs
@@ -447,6 +447,10 @@ define_maps! { <'tcx>
 
     [] fn program_clauses_for: ProgramClausesFor(DefId) -> Lrc<&'tcx Slice<Clause<'tcx>>>,
 
+    [] fn program_clauses_for_env: ProgramClausesForEnv(
+        ty::ParamEnv<'tcx>
+    ) -> Lrc<&'tcx Slice<Clause<'tcx>>>,
+
     [] fn wasm_custom_sections: WasmCustomSections(CrateNum) -> Lrc<Vec<DefId>>,
     [] fn wasm_import_module_map: WasmImportModuleMap(CrateNum)
         -> Lrc<FxHashMap<DefId, String>>,
diff --git a/src/librustc/ty/maps/plumbing.rs b/src/librustc/ty/maps/plumbing.rs
index 8d6c7474a9f..70fbd17e6cb 100644
--- a/src/librustc/ty/maps/plumbing.rs
+++ b/src/librustc/ty/maps/plumbing.rs
@@ -978,6 +978,7 @@ pub fn force_from_dep_node<'a, 'gcx, 'lcx>(tcx: TyCtxt<'a, 'gcx, 'lcx>,
         DepKind::DropckOutlives |
         DepKind::SubstituteNormalizeAndTestPredicates |
         DepKind::InstanceDefSizeEstimate |
+        DepKind::ProgramClausesForEnv |
 
         // This one should never occur in this context
         DepKind::Null => {
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index c3d2d5675de..1524d4b9e7f 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -1138,6 +1138,11 @@ pub struct ProjectionPredicate<'tcx> {
 pub type PolyProjectionPredicate<'tcx> = Binder<ProjectionPredicate<'tcx>>;
 
 impl<'tcx> PolyProjectionPredicate<'tcx> {
+    /// Returns the def-id of the associated item being projected.
+    pub fn item_def_id(&self) -> DefId {
+        self.skip_binder().projection_ty.item_def_id
+    }
+
     pub fn to_poly_trait_ref(&self, tcx: TyCtxt) -> PolyTraitRef<'tcx> {
         // Note: unlike with TraitRef::to_poly_trait_ref(),
         // self.0.trait_ref is permitted to have escaping regions.
diff --git a/src/librustc_traits/lib.rs b/src/librustc_traits/lib.rs
index 8136f6857a5..90c870096e1 100644
--- a/src/librustc_traits/lib.rs
+++ b/src/librustc_traits/lib.rs
@@ -37,6 +37,7 @@ pub fn provide(p: &mut Providers) {
         normalize_ty_after_erasing_regions:
             normalize_erasing_regions::normalize_ty_after_erasing_regions,
         program_clauses_for: lowering::program_clauses_for,
+        program_clauses_for_env: lowering::program_clauses_for_env,
         ..*p
     };
 }
diff --git a/src/librustc_traits/lowering.rs b/src/librustc_traits/lowering.rs
index 942cf7a6571..25a3621fd00 100644
--- a/src/librustc_traits/lowering.rs
+++ b/src/librustc_traits/lowering.rs
@@ -10,11 +10,14 @@
 
 use rustc::hir::def_id::DefId;
 use rustc::hir::intravisit::{self, NestedVisitorMap, Visitor};
+use rustc::hir::map::definitions::DefPathData;
+use rustc::hir::{self, ImplPolarity};
 use rustc::traits::{Clause, DomainGoal, Goal, PolyDomainGoal, ProgramClause, WhereClauseAtom};
 use rustc::ty::subst::Substs;
 use rustc::ty::{self, Slice, TyCtxt};
+use rustc_data_structures::fx::FxHashSet;
 use rustc_data_structures::sync::Lrc;
-use syntax::ast;
+use std::mem;
 use syntax::ast;
 
 use std::iter;
@@ -120,24 +123,73 @@ crate fn program_clauses_for<'a, 'tcx>(
     tcx: TyCtxt<'a, 'tcx, 'tcx>,
     def_id: DefId,
 ) -> Lrc<&'tcx Slice<Clause<'tcx>>> {
-    let node_id = tcx.hir.as_local_node_id(def_id).unwrap();
-    let node = tcx.hir.find(node_id).unwrap();
-    match node {
-        hir::map::Node::NodeItem(item) => match item.node {
-            hir::ItemTrait(..) => program_clauses_for_trait(tcx, def_id),
-            hir::ItemImpl(..) => program_clauses_for_impl(tcx, def_id),
-            _ => Lrc::new(tcx.mk_clauses(iter::empty::<Clause>())),
-        },
-        hir::map::Node::NodeImplItem(item) => {
-            if let hir::ImplItemKind::Type(..) = item.node {
-                program_clauses_for_associated_type_value(tcx, def_id)
-            } else {
-                Lrc::new(tcx.mk_clauses(iter::empty::<Clause>()))
-            }
-        }
+    match tcx.def_key(def_id).disambiguated_data.data {
+        DefPathData::Trait(_) => program_clauses_for_trait(tcx, def_id),
+        DefPathData::Impl => program_clauses_for_impl(tcx, def_id),
+        DefPathData::AssocTypeInImpl(..) => program_clauses_for_associated_type_value(tcx, def_id),
+        _ => Lrc::new(Slice::empty()),
+    }
+}
+
+crate fn program_clauses_for_env<'a, 'tcx>(
+    tcx: TyCtxt<'a, 'tcx, 'tcx>,
+    param_env: ty::ParamEnv<'tcx>,
+) -> Lrc<&'tcx Slice<Clause<'tcx>>> {
+    debug!("program_clauses_for_env(param_env={:?})", param_env);
+
+    let mut last_round = FxHashSet();
+    last_round.extend(
+        param_env
+            .caller_bounds
+            .iter()
+            .flat_map(|&p| predicate_def_id(p)),
+    );
+
+    let mut closure = last_round.clone();
+    let mut next_round = FxHashSet();
+    while !last_round.is_empty() {
+        next_round.extend(
+            last_round
+                .drain()
+                .flat_map(|def_id| {
+                    tcx.predicates_of(def_id)
+                        .instantiate_identity(tcx)
+                        .predicates
+                })
+                .flat_map(|p| predicate_def_id(p))
+                .filter(|&def_id| closure.insert(def_id)),
+        );
+        mem::swap(&mut next_round, &mut last_round);
+    }
+
+    debug!("program_clauses_for_env: closure = {:#?}", closure);
 
-        // FIXME: other constructions e.g. traits, associated types...
-        _ => Lrc::new(tcx.mk_clauses(iter::empty::<Clause>())),
+    return Lrc::new(
+        tcx.mk_clauses(
+            closure
+                .into_iter()
+                .flat_map(|def_id| tcx.program_clauses_for(def_id).iter().cloned()),
+        ),
+    );
+
+    /// Given that `predicate` is in the environment, returns the
+    /// def-id of something (e.g., a trait, associated item, etc)
+    /// whose predicates can also be assumed to be true. We will
+    /// compute the transitive closure of such things.
+    fn predicate_def_id<'tcx>(predicate: ty::Predicate<'tcx>) -> Option<DefId> {
+        match predicate {
+            ty::Predicate::Trait(predicate) => Some(predicate.def_id()),
+
+            ty::Predicate::Projection(projection) => Some(projection.item_def_id()),
+
+            ty::Predicate::WellFormed(..)
+            | ty::Predicate::RegionOutlives(..)
+            | ty::Predicate::TypeOutlives(..)
+            | ty::Predicate::ObjectSafe(..)
+            | ty::Predicate::ClosureKind(..)
+            | ty::Predicate::Subtype(..)
+            | ty::Predicate::ConstEvaluatable(..) => None,
+        }
     }
 }
 
diff --git a/src/test/ui/chalkify/lower_env1.rs b/src/test/ui/chalkify/lower_env1.rs
new file mode 100644
index 00000000000..fc20ad0e08b
--- /dev/null
+++ b/src/test/ui/chalkify/lower_env1.rs
@@ -0,0 +1,24 @@
+// 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)]
+#![allow(dead_code)]
+
+trait Foo { }
+
+#[rustc_dump_program_clauses] //~ ERROR program clause dump
+trait Bar where Self: Foo { }
+
+#[rustc_dump_env_program_clauses] //~ ERROR program clause dump
+fn bar<T: Bar>() {
+}
+
+fn main() {
+}
diff --git a/src/test/ui/chalkify/lower_env1.stderr b/src/test/ui/chalkify/lower_env1.stderr
new file mode 100644
index 00000000000..aaf74f1095a
--- /dev/null
+++ b/src/test/ui/chalkify/lower_env1.stderr
@@ -0,0 +1,24 @@
+error: program clause dump
+  --> $DIR/lower_env1.rs:16:1
+   |
+LL | #[rustc_dump_program_clauses] //~ ERROR program clause dump
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+   |
+   = note: Implemented(Self: Bar) :- FromEnv(Self: Bar).
+   = note: FromEnv(Self: Bar) :- FromEnv(Self: Bar).
+   = note: FromEnv(Self: Foo) :- FromEnv(Self: Bar).
+
+error: program clause dump
+  --> $DIR/lower_env1.rs:19:1
+   |
+LL | #[rustc_dump_env_program_clauses] //~ ERROR program clause dump
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+   |
+   = note: Implemented(Self: std::marker::Sized) :- FromEnv(Self: std::marker::Sized).
+   = note: Implemented(Self: Bar) :- FromEnv(Self: Bar).
+   = note: FromEnv(Self: Bar) :- FromEnv(Self: Bar).
+   = note: FromEnv(Self: Foo) :- FromEnv(Self: Bar).
+   = note: Implemented(Self: Foo) :- FromEnv(Self: Foo).
+
+error: aborting due to 2 previous errors
+