Auto merge of #29241 - nikomatsakis:issue-28871, r=arielb1

Give preference to projections from where-clauses over those from trait definitions. This makes #28871 work again, though I think there's more to fix in this general area.

r? @arielb1 
cc @brson (fixes regression)

4 files changed, 114 insertions, 14 deletions

diff --git a/src/librustc/middle/region.rs b/src/librustc/middle/region.rs
index bdf01f941c4..1027bbf6703 100644
--- a/src/librustc/middle/region.rs
+++ b/src/librustc/middle/region.rs
@@ -24,6 +24,7 @@ use middle::ty::{self, Ty};
 
 use std::cell::RefCell;
 use std::collections::hash_map::Entry;
+use std::fmt;
 use std::mem;
 use syntax::codemap::{self, Span};
 use syntax::ast::{self, NodeId};
@@ -34,9 +35,25 @@ use rustc_front::hir::{Block, Item, FnDecl, Arm, Pat, Stmt, Expr, Local};
 use rustc_front::util::stmt_id;
 
 #[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash, RustcEncodable,
-           RustcDecodable, Debug, Copy)]
+           RustcDecodable, Copy)]
 pub struct CodeExtent(u32);
 
+impl fmt::Debug for CodeExtent {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        try!(write!(f, "CodeExtent({:?}", self.0));
+
+        try!(ty::tls::with_opt(|opt_tcx| {
+            if let Some(tcx) = opt_tcx {
+                let data = tcx.region_maps.code_extents.borrow()[self.0 as usize];
+                try!(write!(f, "/{:?}", data));
+            }
+            Ok(())
+        }));
+
+        write!(f, ")")
+    }
+}
+
 /// The root of everything. I should be using NonZero or profiling
 /// instead of this (probably).
 pub const ROOT_CODE_EXTENT : CodeExtent = CodeExtent(0);
diff --git a/src/librustc/middle/traits/project.rs b/src/librustc/middle/traits/project.rs
index a2c09f88ab3..bf90b3a02a8 100644
--- a/src/librustc/middle/traits/project.rs
+++ b/src/librustc/middle/traits/project.rs
@@ -54,9 +54,19 @@ pub struct MismatchedProjectionTypes<'tcx> {
 
 #[derive(PartialEq, Eq, Debug)]
 enum ProjectionTyCandidate<'tcx> {
+    // from a where-clause in the env or object type
     ParamEnv(ty::PolyProjectionPredicate<'tcx>),
+
+    // from the definition of `Trait` when you have something like <<A as Trait>::B as Trait2>::C
+    TraitDef(ty::PolyProjectionPredicate<'tcx>),
+
+    // defined in an impl
     Impl(VtableImplData<'tcx, PredicateObligation<'tcx>>),
+
+    // closure return type
     Closure(VtableClosureData<'tcx, PredicateObligation<'tcx>>),
+
+    // fn pointer return type
     FnPointer(Ty<'tcx>),
 }
 
@@ -491,7 +501,11 @@ fn project_type<'cx,'tcx>(
            candidates.vec.len(),
            candidates.ambiguous);
 
-    // We probably need some winnowing logic similar to select here.
+    // Inherent ambiguity that prevents us from even enumerating the
+    // candidates.
+    if candidates.ambiguous {
+        return Err(ProjectionTyError::TooManyCandidates);
+    }
 
     // Drop duplicates.
     //
@@ -512,10 +526,30 @@ fn project_type<'cx,'tcx>(
         }
     }
 
-    if candidates.ambiguous || candidates.vec.len() > 1 {
-        return Err(ProjectionTyError::TooManyCandidates);
+    // Prefer where-clauses. As in select, if there are multiple
+    // candidates, we prefer where-clause candidates over impls.  This
+    // may seem a bit surprising, since impls are the source of
+    // "truth" in some sense, but in fact some of the impls that SEEM
+    // applicable are not, because of nested obligations. Where
+    // clauses are the safer choice. See the comment on
+    // `select::SelectionCandidate` and #21974 for more details.
+    if candidates.vec.len() > 1 {
+        debug!("retaining param-env candidates only from {:?}", candidates.vec);
+        candidates.vec.retain(|c| match *c {
+            ProjectionTyCandidate::ParamEnv(..) => true,
+            ProjectionTyCandidate::Impl(..) |
+            ProjectionTyCandidate::Closure(..) |
+            ProjectionTyCandidate::TraitDef(..) |
+            ProjectionTyCandidate::FnPointer(..) => false,
+        });
+        debug!("resulting candidate set: {:?}", candidates.vec);
+        if candidates.vec.len() != 1 {
+            return Err(ProjectionTyError::TooManyCandidates);
+        }
     }
 
+    assert!(candidates.vec.len() <= 1);
+
     match candidates.vec.pop() {
         Some(candidate) => {
             let (ty, obligations) = confirm_candidate(selcx, obligation, candidate);
@@ -538,9 +572,14 @@ fn assemble_candidates_from_param_env<'cx,'tcx>(
     obligation_trait_ref: &ty::TraitRef<'tcx>,
     candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
 {
+    debug!("assemble_candidates_from_param_env(..)");
     let env_predicates = selcx.param_env().caller_bounds.iter().cloned();
-    assemble_candidates_from_predicates(selcx, obligation, obligation_trait_ref,
-                                        candidate_set, env_predicates);
+    assemble_candidates_from_predicates(selcx,
+                                        obligation,
+                                        obligation_trait_ref,
+                                        candidate_set,
+                                        ProjectionTyCandidate::ParamEnv,
+                                        env_predicates);
 }
 
 /// In the case of a nested projection like <<A as Foo>::FooT as Bar>::BarT, we may find
@@ -559,6 +598,8 @@ fn assemble_candidates_from_trait_def<'cx,'tcx>(
     obligation_trait_ref: &ty::TraitRef<'tcx>,
     candidate_set: &mut ProjectionTyCandidateSet<'tcx>)
 {
+    debug!("assemble_candidates_from_trait_def(..)");
+
     // Check whether the self-type is itself a projection.
     let trait_ref = match obligation_trait_ref.self_ty().sty {
         ty::TyProjection(ref data) => data.trait_ref.clone(),
@@ -575,8 +616,12 @@ fn assemble_candidates_from_trait_def<'cx,'tcx>(
     let trait_predicates = selcx.tcx().lookup_predicates(trait_ref.def_id);
     let bounds = trait_predicates.instantiate(selcx.tcx(), trait_ref.substs);
     let bounds = elaborate_predicates(selcx.tcx(), bounds.predicates.into_vec());
-    assemble_candidates_from_predicates(selcx, obligation, obligation_trait_ref,
-                                        candidate_set, bounds)
+    assemble_candidates_from_predicates(selcx,
+                                        obligation,
+                                        obligation_trait_ref,
+                                        candidate_set,
+                                        ProjectionTyCandidate::TraitDef,
+                                        bounds)
 }
 
 fn assemble_candidates_from_predicates<'cx,'tcx,I>(
@@ -584,6 +629,7 @@ fn assemble_candidates_from_predicates<'cx,'tcx,I>(
     obligation: &ProjectionTyObligation<'tcx>,
     obligation_trait_ref: &ty::TraitRef<'tcx>,
     candidate_set: &mut ProjectionTyCandidateSet<'tcx>,
+    ctor: fn(ty::PolyProjectionPredicate<'tcx>) -> ProjectionTyCandidate<'tcx>,
     env_predicates: I)
     where I: Iterator<Item=ty::Predicate<'tcx>>
 {
@@ -614,8 +660,7 @@ fn assemble_candidates_from_predicates<'cx,'tcx,I>(
                        data, is_match, same_name);
 
                 if is_match {
-                    candidate_set.vec.push(
-                        ProjectionTyCandidate::ParamEnv(data.clone()));
+                    candidate_set.vec.push(ctor(data.clone()));
                 }
             }
             _ => { }
@@ -647,8 +692,12 @@ fn assemble_candidates_from_object_type<'cx,'tcx>(
                                           .map(|p| p.to_predicate())
                                           .collect();
     let env_predicates = elaborate_predicates(selcx.tcx(), env_predicates);
-    assemble_candidates_from_predicates(selcx, obligation, obligation_trait_ref,
-                                        candidate_set, env_predicates)
+    assemble_candidates_from_predicates(selcx,
+                                        obligation,
+                                        obligation_trait_ref,
+                                        candidate_set,
+                                        ProjectionTyCandidate::ParamEnv,
+                                        env_predicates)
 }
 
 fn assemble_candidates_from_impls<'cx,'tcx>(
@@ -746,7 +795,8 @@ fn confirm_candidate<'cx,'tcx>(
            obligation);
 
     match candidate {
-        ProjectionTyCandidate::ParamEnv(poly_projection) => {
+        ProjectionTyCandidate::ParamEnv(poly_projection) |
+        ProjectionTyCandidate::TraitDef(poly_projection) => {
             confirm_param_env_candidate(selcx, obligation, poly_projection)
         }
 
diff --git a/src/librustc_driver/pretty.rs b/src/librustc_driver/pretty.rs
index 8407939bebc..a30c437197c 100644
--- a/src/librustc_driver/pretty.rs
+++ b/src/librustc_driver/pretty.rs
@@ -91,7 +91,7 @@ pub fn parse_pretty(sess: &Session,
         ("expanded,identified", _) => PpmSource(PpmExpandedIdentified),
         ("expanded,hygiene", _) => PpmSource(PpmExpandedHygiene),
         ("hir", true)       => PpmHir(PpmNormal),
-        ("hir,identified", true) => PpmHir(PpmExpandedIdentified),
+        ("hir,identified", true) => PpmHir(PpmIdentified),
         ("hir,typed", true)        => PpmHir(PpmTyped),
         ("flowgraph", true)    => PpmFlowGraph(PpFlowGraphMode::Default),
         ("flowgraph,unlabelled", true)    => PpmFlowGraph(PpFlowGraphMode::UnlabelledEdges),
diff --git a/src/test/run-pass/issue-28871.rs b/src/test/run-pass/issue-28871.rs
new file mode 100644
index 00000000000..92ba98f5062
--- /dev/null
+++ b/src/test/run-pass/issue-28871.rs
@@ -0,0 +1,33 @@
+// Copyright 2015 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.
+
+// Regression test for #28871. The problem is that rustc encountered
+// two ways to project, one from a where clause and one from the where
+// clauses on the trait definition. (In fact, in this case, the where
+// clauses originated from the trait definition as well.) The true
+// cause of the error is that the trait definition where clauses are
+// not being normalized, and hence the two sources are considered in
+// conflict, and not a duplicate. Hacky solution is to prefer where
+// clauses over the data found in the trait definition.
+
+trait T {
+    type T;
+}
+
+struct S;
+impl T for S {
+    type T = S;
+}
+
+trait T2 {
+    type T: Iterator<Item=<S as T>::T>;
+}
+
+fn main() { }