introduce an "in" constraint instead of error

4 files changed, 133 insertions, 49 deletions

diff --git a/src/librustc/infer/canonical/query_response.rs b/src/librustc/infer/canonical/query_response.rs
index 3e92fed005c..f0ea61cf9b4 100644
--- a/src/librustc/infer/canonical/query_response.rs
+++ b/src/librustc/infer/canonical/query_response.rs
@@ -654,11 +654,15 @@ pub fn make_query_outlives<'tcx>(
         constraints,
         verifys,
         givens,
+        in_constraints,
     } = region_constraints;
 
     assert!(verifys.is_empty());
     assert!(givens.is_empty());
 
+    // FIXME(ndm) -- we have to think about what to do here, perhaps
+    assert!(in_constraints.is_empty());
+
     let outlives: Vec<_> = constraints
         .into_iter()
         .map(|(k, _)| match *k {
diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs
index eca1ada8518..d4386b321e3 100644
--- a/src/librustc/infer/mod.rs
+++ b/src/librustc/infer/mod.rs
@@ -30,6 +30,7 @@ use rustc_data_structures::unify as ut;
 use std::cell::{Cell, Ref, RefCell, RefMut};
 use std::collections::BTreeMap;
 use std::fmt;
+use std::rc::Rc;
 use syntax::ast;
 use syntax_pos::symbol::InternedString;
 use syntax_pos::Span;
@@ -904,6 +905,19 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
             .make_subregion(origin, a, b);
     }
 
+    /// Require that the region `r` be equal to one of the regions in
+    /// the set `regions`.
+    pub fn in_constraint(
+        &self,
+        origin: SubregionOrigin<'tcx>,
+        region: ty::Region<'tcx>,
+        in_regions: &Rc<Vec<ty::Region<'tcx>>>,
+    ) {
+        debug!("sub_regions({:?} <: {:?})", region, in_regions);
+        self.borrow_region_constraints()
+            .in_constraint(origin, region, in_regions);
+    }
+
     pub fn subtype_predicate(
         &self,
         cause: &ObligationCause<'tcx>,
diff --git a/src/librustc/infer/opaque_types/mod.rs b/src/librustc/infer/opaque_types/mod.rs
index 47dfa3ea508..3072c398df3 100644
--- a/src/librustc/infer/opaque_types/mod.rs
+++ b/src/librustc/infer/opaque_types/mod.rs
@@ -9,6 +9,8 @@ use crate::ty::subst::{InternalSubsts, Kind, SubstsRef, UnpackedKind};
 use crate::ty::{self, GenericParamDefKind, Ty, TyCtxt};
 use crate::util::nodemap::DefIdMap;
 use rustc_data_structures::fx::FxHashMap;
+use std::rc::Rc;
+use syntax::source_map::Span;
 
 pub type OpaqueTypeMap<'tcx> = DefIdMap<OpaqueTypeDecl<'tcx>>;
 
@@ -212,13 +214,13 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
     ///
     /// # The Solution
     ///
-    /// We make use of the constraint that we *do* have in the `<=`
-    /// relation. To do that, we find the "minimum" of all the
-    /// arguments that appear in the substs: that is, some region
-    /// which is less than all the others. In the case of `Foo1<'a>`,
-    /// that would be `'a` (it's the only choice, after all). Then we
-    /// apply that as a least bound to the variables (e.g., `'a <=
-    /// '0`).
+    /// We generally prefer to make us our `<=` constraints, since
+    /// they integrate best into the region solve. To do that, we find
+    /// the "minimum" of all the arguments that appear in the substs:
+    /// that is, some region which is less than all the others. In the
+    /// case of `Foo1<'a>`, that would be `'a` (it's the only choice,
+    /// after all). Then we apply that as a least bound to the
+    /// variables (e.g., `'a <= '0`).
     ///
     /// In some cases, there is no minimum. Consider this example:
     ///
@@ -226,8 +228,32 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
     /// fn baz<'a, 'b>() -> impl Trait<'a, 'b> { ... }
     /// ```
     ///
-    /// Here we would report an error, because `'a` and `'b` have no
-    /// relation to one another.
+    /// Here we would report a more complex "in constraint", like `'r
+    /// in ['a, 'b, 'static]` (where `'r` is some regon appearing in
+    /// the hidden type).
+    ///
+    /// # Constrain regions, not the hidden concrete type
+    ///
+    /// Note that generating constraints on each region `Rc` is *not*
+    /// the same as generating an outlives constraint on `Tc` iself.
+    /// For example, if we had a function like this:
+    ///
+    /// ```rust
+    /// fn foo<'a, T>(x: &'a u32, y: T) -> impl Foo<'a> {
+    ///   (x, y)
+    /// }
+    ///
+    /// // Equivalent to:
+    /// existential type FooReturn<'a, T>: Foo<'a>;
+    /// fn foo<'a, T>(..) -> FooReturn<'a, T> { .. }
+    /// ```
+    ///
+    /// then the hidden type `Tc` would be `(&'0 u32, T)` (where `'0`
+    /// is an inference variable). If we generated a constraint that
+    /// `Tc: 'a`, then this would incorrectly require that `T: 'a` --
+    /// but this is not necessary, because the existential type we
+    /// create will be allowed to reference `T`. So instead we just
+    /// generate a constraint that `'0: 'a`.
     ///
     /// # The `free_region_relations` parameter
     ///
@@ -270,6 +296,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
         }
     }
 
+    /// See `constrain_opaque_types` for docs
     pub fn constrain_opaque_type<FRR: FreeRegionRelations<'tcx>>(
         &self,
         def_id: DefId,
@@ -323,6 +350,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
                 GenericParamDefKind::Lifetime => {}
                 _ => continue,
             }
+
             // Get the value supplied for this region from the substs.
             let subst_arg = opaque_defn.substs.region_at(param.index as usize);
 
@@ -339,45 +367,19 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
                         least_region = Some(subst_arg);
                     } else {
                         // There are two regions (`lr` and
-                        // `subst_arg`) which are not relatable. We can't
-                        // find a best choice.
-                        let context_name = match opaque_defn.origin {
-                            hir::ExistTyOrigin::ExistentialType => "existential type",
-                            hir::ExistTyOrigin::ReturnImplTrait => "impl Trait",
-                            hir::ExistTyOrigin::AsyncFn => "async fn",
-                        };
-                        let msg = format!("ambiguous lifetime bound in `{}`", context_name);
-                        let mut err = self.tcx.sess.struct_span_err(span, &msg);
-
-                        let lr_name = lr.to_string();
-                        let subst_arg_name = subst_arg.to_string();
-                        let label_owned;
-                        let label = match (&*lr_name, &*subst_arg_name) {
-                            ("'_", "'_") => "the elided lifetimes here do not outlive one another",
-                            _ => {
-                                label_owned = format!(
-                                    "neither `{}` nor `{}` outlives the other",
-                                    lr_name, subst_arg_name,
-                                );
-                                &label_owned
-                            }
-                        };
-                        err.span_label(span, label);
-
-                        if let hir::ExistTyOrigin::AsyncFn = opaque_defn.origin {
-                            err.note(
-                                "multiple unrelated lifetimes are not allowed in \
-                                 `async fn`.",
-                            );
-                            err.note(
-                                "if you're using argument-position elided lifetimes, consider \
-                                 switching to a single named lifetime.",
-                            );
-                        }
-                        err.emit();
-
-                        least_region = Some(self.tcx.mk_region(ty::ReEmpty));
-                        break;
+                        // `subst_arg`) which are not relatable. We
+                        // can't find a best choice. Therefore,
+                        // instead of creating a single bound like
+                        // `'r: 'a` (which is our preferred choice),
+                        // we will create a "in bound" like `'r in
+                        // ['a, 'b, 'c]`, where `'a..'c` are the
+                        // regions that appear in the impl trait.
+                        return self.generate_in_constraint(
+                            span,
+                            concrete_ty,
+                            abstract_type_generics,
+                            opaque_defn,
+                        );
                     }
                 }
             }
@@ -392,6 +394,37 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> {
         });
     }
 
+    /// As a fallback, we sometimes generate an "in constraint". For
+    /// case like `impl Foo<'a, 'b>`, where `'a` and `'b` cannot be
+    /// related, we would generate a constraint `'r in ['a, 'b,
+    /// 'static]` for each region `'r` that appears in the hidden type
+    /// (i.e., it must be equal to `'a`, `'b`, or `'static`).
+    fn generate_in_constraint(
+        &self,
+        span: Span,
+        concrete_ty: Ty<'tcx>,
+        abstract_type_generics: &ty::Generics,
+        opaque_defn: &OpaqueTypeDecl<'tcx>,
+    ) {
+        let in_regions: Rc<Vec<ty::Region<'tcx>>> = Rc::new(
+            abstract_type_generics
+                .params
+                .iter()
+                .filter(|param| match param.kind {
+                    GenericParamDefKind::Lifetime => true,
+                    GenericParamDefKind::Type { .. } | GenericParamDefKind::Const => false,
+                })
+                .map(|param| opaque_defn.substs.region_at(param.index as usize))
+                .chain(std::iter::once(self.tcx.lifetimes.re_static))
+                .collect(),
+        );
+
+        concrete_ty.visit_with(&mut ConstrainOpaqueTypeRegionVisitor {
+            tcx: self.tcx,
+            op: |r| self.in_constraint(infer::CallReturn(span), r, &in_regions),
+        });
+    }
+
     /// Given the fully resolved, instantiated type for an opaque
     /// type, i.e., the value of an inference variable like C1 or C2
     /// (*), computes the "definition type" for an abstract type
diff --git a/src/librustc/infer/region_constraints/mod.rs b/src/librustc/infer/region_constraints/mod.rs
index f2235fe8d6d..14572c050b0 100644
--- a/src/librustc/infer/region_constraints/mod.rs
+++ b/src/librustc/infer/region_constraints/mod.rs
@@ -17,6 +17,7 @@ use crate::ty::{Region, RegionVid};
 use std::collections::BTreeMap;
 use std::{cmp, fmt, mem};
 use std::ops::Range;
+use std::rc::Rc;
 
 mod leak_check;
 
@@ -78,6 +79,11 @@ pub struct RegionConstraintData<'tcx> {
     /// be a region variable (or neither, as it happens).
     pub constraints: BTreeMap<Constraint<'tcx>, SubregionOrigin<'tcx>>,
 
+    /// Constraints of the form `R0 in [R1, ..., Rn]`, meaning that
+    /// `R0` must be equal to one of the regions `R1..Rn`. These occur
+    /// with `impl Trait` quite frequently.
+    pub in_constraints: Vec<InConstraint<'tcx>>,
+
     /// A "verify" is something that we need to verify after inference
     /// is done, but which does not directly affect inference in any
     /// way.
@@ -137,6 +143,14 @@ impl Constraint<'_> {
     }
 }
 
+/// Requires that `region` must be equal to one of the regions in `in_regions`.
+#[derive(Debug, Clone)]
+pub struct InConstraint<'tcx> {
+    pub origin: SubregionOrigin<'tcx>,
+    pub region: Region<'tcx>,
+    pub in_regions: Rc<Vec<Region<'tcx>>>,
+}
+
 /// `VerifyGenericBound(T, _, R, RS)`: the parameter type `T` (or
 /// associated type) must outlive the region `R`. `T` is known to
 /// outlive `RS`. Therefore, verify that `R <= RS[i]` for some
@@ -643,6 +657,24 @@ impl<'tcx> RegionConstraintCollector<'tcx> {
         }
     }
 
+    pub fn in_constraint(
+        &mut self,
+        origin: SubregionOrigin<'tcx>,
+        region: ty::Region<'tcx>,
+        in_regions: &Rc<Vec<ty::Region<'tcx>>>,
+    ) {
+        debug!("in_constraint({:?} in {:#?})", region, in_regions);
+
+        if in_regions.iter().any(|&r| r == region) {
+            return;
+        }
+
+        self.data.in_constraints.push(InConstraint {
+            origin, region, in_regions: in_regions.clone()
+        });
+
+    }
+
     pub fn make_subregion(
         &mut self,
         origin: SubregionOrigin<'tcx>,
@@ -906,9 +938,10 @@ impl<'tcx> RegionConstraintData<'tcx> {
     pub fn is_empty(&self) -> bool {
         let RegionConstraintData {
             constraints,
+            in_constraints,
             verifys,
             givens,
         } = self;
-        constraints.is_empty() && verifys.is_empty() && givens.is_empty()
+        constraints.is_empty() && in_constraints.is_empty() && verifys.is_empty() && givens.is_empty()
     }
 }