trigger unsized coercions keyed on Sized bounds

This PR causes unsized coercions to not be disabled by `$0: Unsize<dyn
Object>` coercion obligations when we have an `$0: Sized` obligation
somewhere.

Note that `X: Unsize<dyn Object>` obligations can't fail *as
obligations* if `X: Sized` holds, so this still maintains some version
of monotonicity (I think that an unsized coercion can't be converted to
no coercion by unifying type variables).

Fixes #49593 (unblocking never_type).

6 files changed, 197 insertions, 55 deletions

diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs
index b1a13354b7c..92e0a0a763d 100644
--- a/src/librustc/infer/mod.rs
+++ b/src/librustc/infer/mod.rs
@@ -1253,6 +1253,10 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         self.inlined_shallow_resolve(typ)
     }
 
+    pub fn root_var(&self, var: ty::TyVid) -> ty::TyVid {
+        self.type_variables.borrow_mut().root_var(var)
+    }
+
     pub fn resolve_type_vars_if_possible<T>(&self, value: &T) -> T
     where
         T: TypeFoldable<'tcx>,
diff --git a/src/librustc_typeck/check/closure.rs b/src/librustc_typeck/check/closure.rs
index be15503e479..8971e1aa058 100644
--- a/src/librustc_typeck/check/closure.rs
+++ b/src/librustc_typeck/check/closure.rs
@@ -20,7 +20,7 @@ use rustc::infer::LateBoundRegionConversionTime;
 use rustc::infer::type_variable::TypeVariableOrigin;
 use rustc::traits::Obligation;
 use rustc::traits::error_reporting::ArgKind;
-use rustc::ty::{self, ToPolyTraitRef, Ty, GenericParamDefKind};
+use rustc::ty::{self, Ty, GenericParamDefKind};
 use rustc::ty::fold::TypeFoldable;
 use rustc::ty::subst::Substs;
 use std::cmp;
@@ -222,6 +222,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         let fulfillment_cx = self.fulfillment_cx.borrow();
         // Here `expected_ty` is known to be a type inference variable.
 
+        let expected_vid = self.root_var(expected_vid);
         let expected_sig = fulfillment_cx
             .pending_obligations()
             .iter()
@@ -235,13 +236,14 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
                     // Given a Projection predicate, we can potentially infer
                     // the complete signature.
                     let trait_ref = proj_predicate.to_poly_trait_ref(self.tcx);
-                    self.self_type_matches_expected_vid(trait_ref, expected_vid)
-                        .and_then(|_| {
-                            self.deduce_sig_from_projection(
-                                Some(obligation.cause.span),
-                                proj_predicate
-                            )
-                        })
+                    Some(()).filter(|()| {
+                        self.self_type_matches_expected_vid(trait_ref, expected_vid)
+                    }).and_then(|()| {
+                        self.deduce_sig_from_projection(
+                            Some(obligation.cause.span),
+                            proj_predicate
+                        )
+                    })
                 } else {
                     None
                 }
@@ -252,34 +254,8 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         // infer the kind. This can occur if there is a trait-reference
         // like `F : Fn<A>`. Note that due to subtyping we could encounter
         // many viable options, so pick the most restrictive.
-        let expected_kind = fulfillment_cx
-            .pending_obligations()
-            .iter()
-            .filter_map(|obligation| {
-                let opt_trait_ref = match obligation.predicate {
-                    ty::Predicate::Projection(ref data) => Some(data.to_poly_trait_ref(self.tcx)),
-                    ty::Predicate::Trait(ref data) => Some(data.to_poly_trait_ref()),
-                    ty::Predicate::Subtype(..) => None,
-                    ty::Predicate::RegionOutlives(..) => None,
-                    ty::Predicate::TypeOutlives(..) => None,
-                    ty::Predicate::WellFormed(..) => None,
-                    ty::Predicate::ObjectSafe(..) => None,
-                    ty::Predicate::ConstEvaluatable(..) => None,
-
-                    // N.B., this predicate is created by breaking down a
-                    // `ClosureType: FnFoo()` predicate, where
-                    // `ClosureType` represents some `Closure`. It can't
-                    // possibly be referring to the current closure,
-                    // because we haven't produced the `Closure` for
-                    // this closure yet; this is exactly why the other
-                    // code is looking for a self type of a unresolved
-                    // inference variable.
-                    ty::Predicate::ClosureKind(..) => None,
-                };
-                opt_trait_ref
-                    .and_then(|tr| self.self_type_matches_expected_vid(tr, expected_vid))
-                    .and_then(|tr| self.tcx.lang_items().fn_trait_kind(tr.def_id()))
-            })
+        let expected_kind = self.obligations_for_self_ty(expected_vid)
+            .filter_map(|tr| self.tcx.lang_items().fn_trait_kind(tr.def_id()))
             .fold(None, |best, cur| {
                 Some(best.map_or(cur, |best| cmp::min(best, cur)))
             });
@@ -339,22 +315,6 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         Some(ExpectedSig { cause_span, sig })
     }
 
-    fn self_type_matches_expected_vid(
-        &self,
-        trait_ref: ty::PolyTraitRef<'tcx>,
-        expected_vid: ty::TyVid,
-    ) -> Option<ty::PolyTraitRef<'tcx>> {
-        let self_ty = self.shallow_resolve(trait_ref.self_ty());
-        debug!(
-            "self_type_matches_expected_vid(trait_ref={:?}, self_ty={:?})",
-            trait_ref, self_ty
-        );
-        match self_ty.sty {
-            ty::Infer(ty::TyVar(v)) if expected_vid == v => Some(trait_ref),
-            _ => None,
-        }
-    }
-
     fn sig_of_closure(
         &self,
         expr_def_id: DefId,
diff --git a/src/librustc_typeck/check/coercion.rs b/src/librustc_typeck/check/coercion.rs
index 8d844fe3a69..6832a6d2b56 100644
--- a/src/librustc_typeck/check/coercion.rs
+++ b/src/librustc_typeck/check/coercion.rs
@@ -579,7 +579,33 @@ impl<'f, 'gcx, 'tcx> Coerce<'f, 'gcx, 'tcx> {
             };
             match selcx.select(&obligation.with(trait_ref)) {
                 // Uncertain or unimplemented.
-                Ok(None) |
+                Ok(None) => {
+                    if trait_ref.def_id() == unsize_did {
+                        let trait_ref = self.resolve_type_vars_if_possible(&trait_ref);
+                        let self_ty = trait_ref.skip_binder().self_ty();
+                        let unsize_ty = trait_ref.skip_binder().input_types().nth(1).unwrap();
+                        debug!("coerce_unsized: ambiguous unsize case for {:?}", trait_ref);
+                        match (&self_ty.sty, &unsize_ty.sty) {
+                            (ty::Infer(ty::TyVar(v)),
+                             ty::Dynamic(..)) if self.type_var_is_sized(*v) => {
+                                debug!("coerce_unsized: have sized infer {:?}", v);
+                                coercion.obligations.push(obligation);
+                                // `$0: Unsize<dyn Trait>` where we know that `$0: Sized`, try going
+                                // for unsizing.
+                            }
+                            _ => {
+                                // Some other case for `$0: Unsize<Something>`. Note that we
+                                // hit this case even if `Something` is a sized type, so just
+                                // don't do the coercion.
+                                debug!("coerce_unsized: ambiguous unsize");
+                                return Err(TypeError::Mismatch);
+                            }
+                        }
+                    } else {
+                        debug!("coerce_unsized: early return - ambiguous");
+                        return Err(TypeError::Mismatch);
+                    }
+                }
                 Err(traits::Unimplemented) => {
                     debug!("coerce_unsized: early return - can't prove obligation");
                     return Err(TypeError::Mismatch);
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index 957c8d9f19f..e3770cee72f 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -113,8 +113,8 @@ use rustc::mir::interpret::{ConstValue, GlobalId};
 use rustc::ty::subst::{CanonicalUserSubsts, UnpackedKind, Subst, Substs,
                        UserSelfTy, UserSubsts};
 use rustc::traits::{self, ObligationCause, ObligationCauseCode, TraitEngine};
-use rustc::ty::{self, AdtKind, Ty, TyCtxt, GenericParamDefKind, Visibility, ToPredicate,
-                RegionKind};
+use rustc::ty::{self, AdtKind, Ty, TyCtxt, GenericParamDefKind, RegionKind, Visibility,
+                ToPolyTraitRef, ToPredicate};
 use rustc::ty::adjustment::{Adjust, Adjustment, AllowTwoPhase, AutoBorrow, AutoBorrowMutability};
 use rustc::ty::fold::TypeFoldable;
 use rustc::ty::query::Providers;
@@ -134,6 +134,7 @@ use std::collections::hash_map::Entry;
 use std::cmp;
 use std::fmt::Display;
 use std::iter;
+use std::vec;
 use std::mem::replace;
 use std::ops::{self, Deref};
 use std::slice;
@@ -2731,6 +2732,97 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         method.sig.output()
     }
 
+    fn self_type_matches_expected_vid(
+        &self,
+        trait_ref: ty::PolyTraitRef<'tcx>,
+        expected_vid: ty::TyVid,
+    ) -> bool {
+        let self_ty = self.shallow_resolve(trait_ref.self_ty());
+        debug!(
+            "self_type_matches_expected_vid(trait_ref={:?}, self_ty={:?}, expected_vid={:?})",
+            trait_ref, self_ty, expected_vid
+        );
+        match self_ty.sty {
+            ty::Infer(ty::TyVar(v)) => {
+                let root_vid = self.root_var(v);
+                debug!("self_type_matches_expected_vid - root_vid={:?}", root_vid);
+                if root_vid == expected_vid {
+                    true
+                } else {
+                    false
+                }
+            }
+            _ => false
+        }
+    }
+}
+
+/// FIXME: impl Trait why u give me lifetime errors?
+pub struct ObligationMapper<'a, 'gcx, 'tcx>(&'a FnCtxt<'a, 'gcx, 'tcx>, ty::TyVid);
+
+impl<'a, 'gcx, 'tcx> FnOnce<(traits::PredicateObligation<'tcx>,)>
+    for ObligationMapper<'a, 'gcx, 'tcx>
+{
+    type Output = Option<ty::PolyTraitRef<'tcx>>;
+
+    extern "rust-call" fn call_once(mut self, args: (traits::PredicateObligation<'tcx>,))
+                                    -> Self::Output {
+        self.call_mut(args)
+    }
+}
+
+impl<'a, 'gcx, 'tcx> FnMut<(traits::PredicateObligation<'tcx>,)>
+    for ObligationMapper<'a, 'gcx, 'tcx>
+{
+    extern "rust-call" fn call_mut(&mut self, args: (traits::PredicateObligation<'tcx>,))
+                                   -> Self::Output {
+        match args.0.predicate {
+            ty::Predicate::Projection(ref data) => Some(data.to_poly_trait_ref(self.0.tcx)),
+            ty::Predicate::Trait(ref data) => Some(data.to_poly_trait_ref()),
+            ty::Predicate::Subtype(..) => None,
+            ty::Predicate::RegionOutlives(..) => None,
+            ty::Predicate::TypeOutlives(..) => None,
+            ty::Predicate::WellFormed(..) => None,
+            ty::Predicate::ObjectSafe(..) => None,
+            ty::Predicate::ConstEvaluatable(..) => None,
+            // N.B., this predicate is created by breaking down a
+            // `ClosureType: FnFoo()` predicate, where
+            // `ClosureType` represents some `Closure`. It can't
+            // possibly be referring to the current closure,
+            // because we haven't produced the `Closure` for
+            // this closure yet; this is exactly why the other
+            // code is looking for a self type of a unresolved
+            // inference variable.
+            ty::Predicate::ClosureKind(..) => None,
+        }.filter(|tr| {
+            self.0.self_type_matches_expected_vid(*tr, self.1)
+        })
+    }
+}
+
+impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
+    fn obligations_for_self_ty<'b>(&'b self, self_ty: ty::TyVid)
+        -> iter::FilterMap<vec::IntoIter<traits::PredicateObligation<'tcx>>,
+                           ObligationMapper<'b, 'gcx, 'tcx>>
+    {
+        let ty_var_root = self.root_var(self_ty);
+        debug!("obligations_for_self_ty: self_ty={:?} ty_var_root={:?} pending_obligations={:?}",
+               self_ty, ty_var_root,
+               self.fulfillment_cx.borrow().pending_obligations());
+
+        self.fulfillment_cx
+            .borrow()
+            .pending_obligations()
+            .into_iter()
+            .filter_map(ObligationMapper(self, ty_var_root))
+    }
+
+    fn type_var_is_sized(&self, self_ty: ty::TyVid) -> bool {
+        self.obligations_for_self_ty(self_ty).any(|tr| {
+                Some(tr.def_id()) == self.tcx.lang_items().sized_trait()
+        })
+    }
+
     /// Generic function that factors out common logic from function calls,
     /// method calls and overloaded operators.
     fn check_argument_types(&self,
diff --git a/src/librustc_typeck/lib.rs b/src/librustc_typeck/lib.rs
index 8d6fb8b7f39..5ecf24c4a10 100644
--- a/src/librustc_typeck/lib.rs
+++ b/src/librustc_typeck/lib.rs
@@ -75,6 +75,7 @@ This API is completely unstable and subject to change.
 #![feature(box_syntax)]
 #![feature(crate_visibility_modifier)]
 #![feature(exhaustive_patterns)]
+#![feature(fn_traits)]
 #![feature(nll)]
 #![feature(quote)]
 #![feature(refcell_replace_swap)]
@@ -82,6 +83,7 @@ This API is completely unstable and subject to change.
 #![feature(slice_patterns)]
 #![feature(slice_sort_by_cached_key)]
 #![feature(never_type)]
+#![feature(unboxed_closures)]
 
 #![recursion_limit="256"]
 
diff --git a/src/test/ui/coercion/coerce-issue-49593-box-never.rs b/src/test/ui/coercion/coerce-issue-49593-box-never.rs
new file mode 100644
index 00000000000..7cdc6c8c4a4
--- /dev/null
+++ b/src/test/ui/coercion/coerce-issue-49593-box-never.rs
@@ -0,0 +1,58 @@
+// 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.
+
+// compile-pass
+
+#![feature(never_type)]
+#![allow(unreachable_code)]
+
+use std::error::Error;
+use std::char::ParseCharError; /* some Error */
+
+fn raw_ptr_box<T>(t: T) -> *mut T {
+    panic!()
+}
+
+fn foo(x: !) -> Box<Error> {
+    /* *mut $0 is coerced to *mut Error here */ Box::<_ /* ! */>::new(x)
+}
+
+fn foo_raw_ptr(x: !) -> *mut Error {
+    /* *mut $0 is coerced to *mut Error here */ raw_ptr_box::<_ /* ! */>(x)
+}
+
+fn no_coercion(d: *mut Error) -> *mut Error {
+    /* an unsize coercion won't compile here, and it is indeed not used
+       because there is nothing requiring the _ to be Sized */
+    d as *mut _
+}
+
+trait Xyz {}
+struct S;
+struct T;
+impl Xyz for S {}
+impl Xyz for T {}
+
+fn foo_no_never() {
+    let mut x /* : Box<S> */ = None;
+    let mut first_iter = false;
+    loop {
+        if !first_iter {
+            let y: Box<Xyz>
+                = /* Box<$0> is coerced to Box<Xyz> here */ Box::new(x.unwrap());
+        }
+
+        x = Some(S);
+        first_iter = true;
+    }
+}
+
+fn main() {
+}