]>
Commit | Line | Data |
---|---|---|
923072b8 FG |
1 | use std::collections::hash_map::Entry; |
2 | ||
3 | use rustc_data_structures::fx::FxHashMap; | |
064997fb | 4 | use rustc_middle::ty::TypeVisitable; |
923072b8 FG |
5 | use rustc_middle::ty::{ |
6 | self, | |
7 | error::TypeError, | |
8 | relate::{self, Relate, RelateResult, TypeRelation}, | |
9 | Ty, TyCtxt, | |
10 | }; | |
11 | ||
12 | use crate::infer::region_constraints::VerifyIfEq; | |
13 | ||
14 | /// Given a "verify-if-eq" type test like: | |
15 | /// | |
16 | /// exists<'a...> { | |
17 | /// verify_if_eq(some_type, bound_region) | |
18 | /// } | |
19 | /// | |
20 | /// and the type `test_ty` that the type test is being tested against, | |
21 | /// returns: | |
22 | /// | |
23 | /// * `None` if `some_type` cannot be made equal to `test_ty`, | |
24 | /// no matter the values of the variables in `exists`. | |
25 | /// * `Some(r)` with a suitable bound (typically the value of `bound_region`, modulo | |
26 | /// any bound existential variables, which will be substituted) for the | |
27 | /// type under test. | |
28 | /// | |
29 | /// NB: This function uses a simplistic, syntactic version of type equality. | |
30 | /// In other words, it may spuriously return `None` even if the type-under-test | |
31 | /// is in fact equal to `some_type`. In practice, though, this is used on types | |
32 | /// that are either projections like `T::Item` or `T` and it works fine, but it | |
33 | /// could have trouble when complex types with higher-ranked binders and the | |
34 | /// like are used. This is a particular challenge since this function is invoked | |
35 | /// very late in inference and hence cannot make use of the normal inference | |
36 | /// machinery. | |
f2b60f7d | 37 | #[instrument(level = "debug", skip(tcx, param_env))] |
923072b8 FG |
38 | pub fn extract_verify_if_eq<'tcx>( |
39 | tcx: TyCtxt<'tcx>, | |
40 | param_env: ty::ParamEnv<'tcx>, | |
41 | verify_if_eq_b: &ty::Binder<'tcx, VerifyIfEq<'tcx>>, | |
42 | test_ty: Ty<'tcx>, | |
43 | ) -> Option<ty::Region<'tcx>> { | |
44 | assert!(!verify_if_eq_b.has_escaping_bound_vars()); | |
45 | let mut m = Match::new(tcx, param_env); | |
46 | let verify_if_eq = verify_if_eq_b.skip_binder(); | |
47 | m.relate(verify_if_eq.ty, test_ty).ok()?; | |
48 | ||
49 | if let ty::RegionKind::ReLateBound(depth, br) = verify_if_eq.bound.kind() { | |
50 | assert!(depth == ty::INNERMOST); | |
51 | match m.map.get(&br) { | |
52 | Some(&r) => Some(r), | |
53 | None => { | |
54 | // If there is no mapping, then this region is unconstrained. | |
55 | // In that case, we escalate to `'static`. | |
56 | Some(tcx.lifetimes.re_static) | |
57 | } | |
58 | } | |
59 | } else { | |
60 | // The region does not contain any bound variables, so we don't need | |
61 | // to do any substitution. | |
62 | // | |
63 | // Example: | |
64 | // | |
65 | // for<'a> <T as Foo<'a>>::Item: 'b | |
66 | // | |
67 | // In this case, we've now matched and found a value for | |
68 | // `'a`, but it doesn't affect the bound `'b`. | |
69 | Some(verify_if_eq.bound) | |
70 | } | |
71 | } | |
72 | ||
73 | /// True if a (potentially higher-ranked) outlives | |
f2b60f7d | 74 | #[instrument(level = "debug", skip(tcx, param_env))] |
923072b8 FG |
75 | pub(super) fn can_match_erased_ty<'tcx>( |
76 | tcx: TyCtxt<'tcx>, | |
77 | param_env: ty::ParamEnv<'tcx>, | |
78 | outlives_predicate: ty::Binder<'tcx, ty::TypeOutlivesPredicate<'tcx>>, | |
79 | erased_ty: Ty<'tcx>, | |
80 | ) -> bool { | |
81 | assert!(!outlives_predicate.has_escaping_bound_vars()); | |
82 | let erased_outlives_predicate = tcx.erase_regions(outlives_predicate); | |
83 | let outlives_ty = erased_outlives_predicate.skip_binder().0; | |
84 | if outlives_ty == erased_ty { | |
85 | // pointless micro-optimization | |
86 | true | |
87 | } else { | |
88 | Match::new(tcx, param_env).relate(outlives_ty, erased_ty).is_ok() | |
89 | } | |
90 | } | |
91 | ||
92 | struct Match<'tcx> { | |
93 | tcx: TyCtxt<'tcx>, | |
94 | param_env: ty::ParamEnv<'tcx>, | |
95 | pattern_depth: ty::DebruijnIndex, | |
96 | map: FxHashMap<ty::BoundRegion, ty::Region<'tcx>>, | |
97 | } | |
98 | ||
99 | impl<'tcx> Match<'tcx> { | |
100 | fn new(tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>) -> Match<'tcx> { | |
101 | Match { tcx, param_env, pattern_depth: ty::INNERMOST, map: FxHashMap::default() } | |
102 | } | |
103 | } | |
104 | ||
105 | impl<'tcx> Match<'tcx> { | |
106 | /// Creates the "Error" variant that signals "no match". | |
107 | fn no_match<T>(&self) -> RelateResult<'tcx, T> { | |
108 | Err(TypeError::Mismatch) | |
109 | } | |
110 | ||
111 | /// Binds the pattern variable `br` to `value`; returns an `Err` if the pattern | |
112 | /// is already bound to a different value. | |
f2b60f7d | 113 | #[instrument(level = "debug", skip(self))] |
923072b8 FG |
114 | fn bind( |
115 | &mut self, | |
116 | br: ty::BoundRegion, | |
117 | value: ty::Region<'tcx>, | |
118 | ) -> RelateResult<'tcx, ty::Region<'tcx>> { | |
119 | match self.map.entry(br) { | |
120 | Entry::Occupied(entry) => { | |
121 | if *entry.get() == value { | |
122 | Ok(value) | |
123 | } else { | |
124 | self.no_match() | |
125 | } | |
126 | } | |
127 | Entry::Vacant(entry) => { | |
128 | entry.insert(value); | |
129 | Ok(value) | |
130 | } | |
131 | } | |
132 | } | |
133 | } | |
134 | ||
135 | impl<'tcx> TypeRelation<'tcx> for Match<'tcx> { | |
136 | fn tag(&self) -> &'static str { | |
137 | "Match" | |
138 | } | |
487cf647 FG |
139 | |
140 | fn intercrate(&self) -> bool { | |
141 | false | |
142 | } | |
143 | ||
923072b8 FG |
144 | fn tcx(&self) -> TyCtxt<'tcx> { |
145 | self.tcx | |
146 | } | |
147 | fn param_env(&self) -> ty::ParamEnv<'tcx> { | |
148 | self.param_env | |
149 | } | |
150 | fn a_is_expected(&self) -> bool { | |
151 | true | |
152 | } // irrelevant | |
153 | ||
487cf647 FG |
154 | fn mark_ambiguous(&mut self) { |
155 | bug!() | |
156 | } | |
157 | ||
158 | #[instrument(level = "trace", skip(self))] | |
923072b8 FG |
159 | fn relate_with_variance<T: Relate<'tcx>>( |
160 | &mut self, | |
487cf647 | 161 | variance: ty::Variance, |
923072b8 FG |
162 | _: ty::VarianceDiagInfo<'tcx>, |
163 | a: T, | |
164 | b: T, | |
165 | ) -> RelateResult<'tcx, T> { | |
487cf647 FG |
166 | // Opaque types substs have lifetime parameters. |
167 | // We must not check them to be equal, as we never insert anything to make them so. | |
168 | if variance != ty::Bivariant { self.relate(a, b) } else { Ok(a) } | |
923072b8 FG |
169 | } |
170 | ||
171 | #[instrument(skip(self), level = "debug")] | |
172 | fn regions( | |
173 | &mut self, | |
174 | pattern: ty::Region<'tcx>, | |
175 | value: ty::Region<'tcx>, | |
176 | ) -> RelateResult<'tcx, ty::Region<'tcx>> { | |
177 | debug!("self.pattern_depth = {:?}", self.pattern_depth); | |
178 | if let ty::RegionKind::ReLateBound(depth, br) = pattern.kind() && depth == self.pattern_depth { | |
179 | self.bind(br, value) | |
180 | } else if pattern == value { | |
181 | Ok(pattern) | |
182 | } else { | |
183 | self.no_match() | |
184 | } | |
185 | } | |
186 | ||
187 | #[instrument(skip(self), level = "debug")] | |
188 | fn tys(&mut self, pattern: Ty<'tcx>, value: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> { | |
f2b60f7d FG |
189 | if let ty::Error(_) = pattern.kind() { |
190 | // Unlike normal `TypeRelation` rules, `ty::Error` does not equal any type. | |
191 | self.no_match() | |
192 | } else if pattern == value { | |
193 | Ok(pattern) | |
194 | } else { | |
195 | relate::super_relate_tys(self, pattern, value) | |
196 | } | |
923072b8 FG |
197 | } |
198 | ||
199 | #[instrument(skip(self), level = "debug")] | |
200 | fn consts( | |
201 | &mut self, | |
202 | pattern: ty::Const<'tcx>, | |
203 | value: ty::Const<'tcx>, | |
204 | ) -> RelateResult<'tcx, ty::Const<'tcx>> { | |
205 | debug!("{}.consts({:?}, {:?})", self.tag(), pattern, value); | |
206 | if pattern == value { | |
207 | Ok(pattern) | |
208 | } else { | |
209 | relate::super_relate_consts(self, pattern, value) | |
210 | } | |
211 | } | |
212 | ||
213 | fn binders<T>( | |
214 | &mut self, | |
215 | pattern: ty::Binder<'tcx, T>, | |
216 | value: ty::Binder<'tcx, T>, | |
217 | ) -> RelateResult<'tcx, ty::Binder<'tcx, T>> | |
218 | where | |
219 | T: Relate<'tcx>, | |
220 | { | |
221 | self.pattern_depth.shift_in(1); | |
222 | let result = Ok(pattern.rebind(self.relate(pattern.skip_binder(), value.skip_binder())?)); | |
223 | self.pattern_depth.shift_out(1); | |
224 | result | |
225 | } | |
226 | } |