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

use rustc_middle::ty::{
    self, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitableExt, TypeVisitor,
};

use std::ops::ControlFlow;

use crate::infer::outlives::test_type_match;
use crate::infer::region_constraints::VerifyIfEq;

/// Visits free regions in the type that are relevant for liveness computation.
/// These regions are passed to `OP`.
///
/// Specifically, we visit all of the regions of types recursively, except if
/// the type is an alias, we look at the outlives bounds in the param-env
/// and alias's item bounds. If there is a unique outlives bound, then visit
/// that instead. If there is not a unique but there is a `'static` outlives
/// bound, then don't visit anything. Otherwise, walk through the opaque's
/// regions structurally.
pub struct FreeRegionsVisitor<'tcx, OP: FnMut(ty::Region<'tcx>)> {
    pub tcx: TyCtxt<'tcx>,
    pub param_env: ty::ParamEnv<'tcx>,
    pub op: OP,
}

impl<'tcx, OP> TypeVisitor<TyCtxt<'tcx>> for FreeRegionsVisitor<'tcx, OP>
where
    OP: FnMut(ty::Region<'tcx>),
{
    fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(
        &mut self,
        t: &ty::Binder<'tcx, T>,
    ) -> ControlFlow<Self::BreakTy> {
        t.super_visit_with(self);
        ControlFlow::Continue(())
    }

    fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> {
        match *r {
            // ignore bound regions, keep visiting
            ty::ReBound(_, _) => ControlFlow::Continue(()),
            _ => {
                (self.op)(r);
                ControlFlow::Continue(())
            }
        }
    }

    fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> {
        // We're only interested in types involving regions
        if !ty.flags().intersects(ty::TypeFlags::HAS_FREE_REGIONS) {
            return ControlFlow::Continue(());
        }

        // FIXME: Don't consider alias bounds on types that have escaping bound
        // vars. See #117455.
        if ty.has_escaping_bound_vars() {
            return ty.super_visit_with(self);
        }

        match ty.kind() {
            // We can prove that an alias is live two ways:
            // 1. All the components are live.
            //
            // 2. There is a known outlives bound or where-clause, and that
            //    region is live.
            //
            // We search through the item bounds and where clauses for
            // either `'static` or a unique outlives region, and if one is
            // found, we just need to prove that that region is still live.
            // If one is not found, then we continue to walk through the alias.
            ty::Alias(kind, ty::AliasTy { def_id, args, .. }) => {
                let tcx = self.tcx;
                let param_env = self.param_env;
                let outlives_bounds: Vec<_> = tcx
                    .item_bounds(def_id)
                    .iter_instantiated(tcx, args)
                    .chain(param_env.caller_bounds())
                    .filter_map(|clause| {
                        let outlives = clause.as_type_outlives_clause()?;
                        if let Some(outlives) = outlives.no_bound_vars()
                            && outlives.0 == ty
                        {
                            Some(outlives.1)
                        } else {
                            test_type_match::extract_verify_if_eq(
                                tcx,
                                &outlives.map_bound(|ty::OutlivesPredicate(ty, bound)| {
                                    VerifyIfEq { ty, bound }
                                }),
                                ty,
                            )
                        }
                    })
                    .collect();
                // If we find `'static`, then we know the alias doesn't capture *any* regions.
                // Otherwise, all of the outlives regions should be equal -- if they're not,
                // we don't really know how to proceed, so we continue recursing through the
                // alias.
                if outlives_bounds.contains(&tcx.lifetimes.re_static) {
                    // no
                } else if let Some(r) = outlives_bounds.first()
                    && outlives_bounds[1..].iter().all(|other_r| other_r == r)
                {
                    assert!(r.type_flags().intersects(ty::TypeFlags::HAS_FREE_REGIONS));
                    r.visit_with(self)?;
                } else {
                    // Skip lifetime parameters that are not captures.
                    let variances = match kind {
                        ty::Opaque => Some(self.tcx.variances_of(*def_id)),
                        _ => None,
                    };

                    for (idx, s) in args.iter().enumerate() {
                        if variances.map(|variances| variances[idx])
                            != Some(ty::Variance::Bivariant)
                        {
                            s.visit_with(self)?;
                        }
                    }
                }
            }

            _ => {
                ty.super_visit_with(self)?;
            }
        }

        ControlFlow::Continue(())
    }
}