1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

use rustc_data_structures::vec_map::VecMap;
use rustc_infer::infer::InferCtxt;
use rustc_middle::ty::{self, OpaqueTypeKey, Ty, TyCtxt, TypeFoldable};
use rustc_span::Span;
use rustc_trait_selection::opaque_types::InferCtxtExt;

use super::RegionInferenceContext;

impl<'tcx> RegionInferenceContext<'tcx> {
    /// Resolve any opaque types that were encountered while borrow checking
    /// this item. This is then used to get the type in the `type_of` query.
    ///
    /// For example consider `fn f<'a>(x: &'a i32) -> impl Sized + 'a { x }`.
    /// This is lowered to give HIR something like
    ///
    /// type f<'a>::_Return<'_a> = impl Sized + '_a;
    /// fn f<'a>(x: &'a i32) -> f<'static>::_Return<'a> { x }
    ///
    /// When checking the return type record the type from the return and the
    /// type used in the return value. In this case they might be `_Return<'1>`
    /// and `&'2 i32` respectively.
    ///
    /// Once we to this method, we have completed region inference and want to
    /// call `infer_opaque_definition_from_instantiation` to get the inferred
    /// type of `_Return<'_a>`. `infer_opaque_definition_from_instantiation`
    /// compares lifetimes directly, so we need to map the inference variables
    /// back to concrete lifetimes: `'static`, `ReEarlyBound` or `ReFree`.
    ///
    /// First we map all the lifetimes in the concrete type to an equal
    /// universal region that occurs in the concrete type's substs, in this case
    /// this would result in `&'1 i32`. We only consider regions in the substs
    /// in case there is an equal region that does not. For example, this should
    /// be allowed:
    /// `fn f<'a: 'b, 'b: 'a>(x: *mut &'b i32) -> impl Sized + 'a { x }`
    ///
    /// Then we map the regions in both the type and the subst to their
    /// `external_name` giving `concrete_type = &'a i32`,
    /// `substs = ['static, 'a]`. This will then allow
    /// `infer_opaque_definition_from_instantiation` to determine that
    /// `_Return<'_a> = &'_a i32`.
    ///
    /// There's a slight complication around closures. Given
    /// `fn f<'a: 'a>() { || {} }` the closure's type is something like
    /// `f::<'a>::{{closure}}`. The region parameter from f is essentially
    /// ignored by type checking so ends up being inferred to an empty region.
    /// Calling `universal_upper_bound` for such a region gives `fr_fn_body`,
    /// which has no `external_name` in which case we use `'empty` as the
    /// region to pass to `infer_opaque_definition_from_instantiation`.
    #[instrument(skip(self, infcx))]
    pub(in crate::borrow_check) fn infer_opaque_types(
        &self,
        infcx: &InferCtxt<'_, 'tcx>,
        opaque_ty_decls: VecMap<OpaqueTypeKey<'tcx>, Ty<'tcx>>,
        span: Span,
    ) -> VecMap<OpaqueTypeKey<'tcx>, Ty<'tcx>> {
        opaque_ty_decls
            .into_iter()
            .map(|(opaque_type_key, concrete_type)| {
                let substs = opaque_type_key.substs;
                debug!(?concrete_type, ?substs);

                let mut subst_regions = vec![self.universal_regions.fr_static];
                let universal_substs =
                    infcx.tcx.fold_regions(substs, &mut false, |region, _| match *region {
                        ty::ReVar(vid) => {
                            subst_regions.push(vid);
                            self.definitions[vid].external_name.unwrap_or_else(|| {
                                infcx.tcx.sess.delay_span_bug(
                                    span,
                                    "opaque type with non-universal region substs",
                                );
                                infcx.tcx.lifetimes.re_static
                            })
                        }
                        // We don't fold regions in the predicates of opaque
                        // types to `ReVar`s. This means that in a case like
                        //
                        // fn f<'a: 'a>() -> impl Iterator<Item = impl Sized>
                        //
                        // The inner opaque type has `'static` in its substs.
                        ty::ReStatic => region,
                        _ => {
                            infcx.tcx.sess.delay_span_bug(
                                span,
                                &format!("unexpected concrete region in borrowck: {:?}", region),
                            );
                            region
                        }
                    });

                subst_regions.sort();
                subst_regions.dedup();

                let universal_concrete_type =
                    infcx.tcx.fold_regions(concrete_type, &mut false, |region, _| match *region {
                        ty::ReVar(vid) => subst_regions
                            .iter()
                            .find(|ur_vid| self.eval_equal(vid, **ur_vid))
                            .and_then(|ur_vid| self.definitions[*ur_vid].external_name)
                            .unwrap_or(infcx.tcx.lifetimes.re_root_empty),
                        ty::ReLateBound(..) => region,
                        _ => {
                            infcx.tcx.sess.delay_span_bug(
                                span,
                                &format!("unexpected concrete region in borrowck: {:?}", region),
                            );
                            region
                        }
                    });

                debug!(?universal_concrete_type, ?universal_substs);

                let opaque_type_key =
                    OpaqueTypeKey { def_id: opaque_type_key.def_id, substs: universal_substs };
                let remapped_type = infcx.infer_opaque_definition_from_instantiation(
                    opaque_type_key,
                    universal_concrete_type,
                    span,
                );
                (opaque_type_key, remapped_type)
            })
            .collect()
    }

    /// Map the regions in the type to named regions. This is similar to what
    /// `infer_opaque_types` does, but can infer any universal region, not only
    /// ones from the substs for the opaque type. It also doesn't double check
    /// that the regions produced are in fact equal to the named region they are
    /// replaced with. This is fine because this function is only to improve the
    /// region names in error messages.
    pub(in crate::borrow_check) fn name_regions<T>(&self, tcx: TyCtxt<'tcx>, ty: T) -> T
    where
        T: TypeFoldable<'tcx>,
    {
        tcx.fold_regions(ty, &mut false, |region, _| match *region {
            ty::ReVar(vid) => {
                // Find something that we can name
                let upper_bound = self.approx_universal_upper_bound(vid);
                self.definitions[upper_bound].external_name.unwrap_or(region)
            }
            _ => region,
        })
    }
}