]>
Commit | Line | Data |
---|---|---|
ba9703b0 XL |
1 | //! See Rustc Dev Guide chapters on [trait-resolution] and [trait-specialization] for more info on |
2 | //! how this works. | |
0531ce1d | 3 | //! |
ba9703b0 XL |
4 | //! [trait-resolution]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html |
5 | //! [trait-specialization]: https://rustc-dev-guide.rust-lang.org/traits/specialization.html | |
1a4d82fc | 6 | |
5099ac24 | 7 | use crate::infer::outlives::env::OutlivesEnvironment; |
923072b8 | 8 | use crate::infer::{CombinedSnapshot, InferOk}; |
f2b60f7d | 9 | use crate::traits::outlives_bounds::InferCtxtExt as _; |
9fa01778 | 10 | use crate::traits::select::IntercrateAmbiguityCause; |
5e7ed085 | 11 | use crate::traits::util::impl_subject_and_oblig; |
74b04a01 | 12 | use crate::traits::SkipLeakCheck; |
3c0e092e | 13 | use crate::traits::{ |
487cf647 FG |
14 | self, Obligation, ObligationCause, ObligationCtxt, PredicateObligation, PredicateObligations, |
15 | SelectionContext, | |
3c0e092e | 16 | }; |
064997fb | 17 | use rustc_data_structures::fx::FxIndexSet; |
5e7ed085 | 18 | use rustc_errors::Diagnostic; |
f2b60f7d FG |
19 | use rustc_hir::def_id::{DefId, CRATE_DEF_ID, LOCAL_CRATE}; |
20 | use rustc_hir::CRATE_HIR_ID; | |
487cf647 | 21 | use rustc_infer::infer::{DefiningAnchor, InferCtxt, TyCtxtInferExt}; |
f2b60f7d | 22 | use rustc_infer::traits::util; |
5099ac24 | 23 | use rustc_middle::traits::specialization_graph::OverlapMode; |
923072b8 | 24 | use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams}; |
064997fb FG |
25 | use rustc_middle::ty::visit::TypeVisitable; |
26 | use rustc_middle::ty::{self, ImplSubject, Ty, TyCtxt, TypeVisitor}; | |
dfeec247 XL |
27 | use rustc_span::symbol::sym; |
28 | use rustc_span::DUMMY_SP; | |
5e7ed085 | 29 | use std::fmt::Debug; |
ba9703b0 | 30 | use std::iter; |
064997fb | 31 | use std::ops::ControlFlow; |
1a4d82fc | 32 | |
487cf647 FG |
33 | use super::NormalizeExt; |
34 | ||
ff7c6d11 XL |
35 | /// Whether we do the orphan check relative to this crate or |
36 | /// to some remote crate. | |
37 | #[derive(Copy, Clone, Debug)] | |
38 | enum InCrate { | |
39 | Local, | |
dfeec247 | 40 | Remote, |
ff7c6d11 XL |
41 | } |
42 | ||
43 | #[derive(Debug, Copy, Clone)] | |
44 | pub enum Conflict { | |
45 | Upstream, | |
74b04a01 | 46 | Downstream, |
ff7c6d11 | 47 | } |
c34b1796 | 48 | |
ea8adc8c XL |
49 | pub struct OverlapResult<'tcx> { |
50 | pub impl_header: ty::ImplHeader<'tcx>, | |
064997fb | 51 | pub intercrate_ambiguity_causes: FxIndexSet<IntercrateAmbiguityCause>, |
0731742a | 52 | |
9fa01778 | 53 | /// `true` if the overlap might've been permitted before the shift |
0731742a XL |
54 | /// to universes. |
55 | pub involves_placeholder: bool, | |
56 | } | |
57 | ||
5e7ed085 | 58 | pub fn add_placeholder_note(err: &mut Diagnostic) { |
74b04a01 | 59 | err.note( |
0731742a | 60 | "this behavior recently changed as a result of a bug fix; \ |
74b04a01 XL |
61 | see rust-lang/rust#56105 for details", |
62 | ); | |
ea8adc8c XL |
63 | } |
64 | ||
2b03887a | 65 | /// If there are types that satisfy both impls, returns `Some` |
ff7c6d11 | 66 | /// with a suitably-freshened `ImplHeader` with those types |
2b03887a FG |
67 | /// substituted. Otherwise, returns `None`. |
68 | #[instrument(skip(tcx, skip_leak_check), level = "debug")] | |
487cf647 FG |
69 | pub fn overlapping_impls<'tcx>( |
70 | tcx: TyCtxt<'tcx>, | |
ff7c6d11 XL |
71 | impl1_def_id: DefId, |
72 | impl2_def_id: DefId, | |
74b04a01 | 73 | skip_leak_check: SkipLeakCheck, |
5099ac24 | 74 | overlap_mode: OverlapMode, |
487cf647 | 75 | ) -> Option<OverlapResult<'tcx>> { |
6a06907d XL |
76 | // Before doing expensive operations like entering an inference context, do |
77 | // a quick check via fast_reject to tell if the impl headers could possibly | |
78 | // unify. | |
923072b8 | 79 | let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::AsInfer }; |
6a06907d XL |
80 | let impl1_ref = tcx.impl_trait_ref(impl1_def_id); |
81 | let impl2_ref = tcx.impl_trait_ref(impl2_def_id); | |
923072b8 FG |
82 | let may_overlap = match (impl1_ref, impl2_ref) { |
83 | (Some(a), Some(b)) => iter::zip(a.substs, b.substs) | |
84 | .all(|(arg1, arg2)| drcx.generic_args_may_unify(arg1, arg2)), | |
85 | (None, None) => { | |
86 | let self_ty1 = tcx.type_of(impl1_def_id); | |
87 | let self_ty2 = tcx.type_of(impl2_def_id); | |
88 | drcx.types_may_unify(self_ty1, self_ty2) | |
cdc7bbd5 | 89 | } |
923072b8 FG |
90 | _ => bug!("unexpected impls: {impl1_def_id:?} {impl2_def_id:?}"), |
91 | }; | |
92 | ||
93 | if !may_overlap { | |
6a06907d XL |
94 | // Some types involved are definitely different, so the impls couldn't possibly overlap. |
95 | debug!("overlapping_impls: fast_reject early-exit"); | |
2b03887a | 96 | return None; |
6a06907d | 97 | } |
1a4d82fc | 98 | |
487cf647 FG |
99 | let infcx = |
100 | tcx.infer_ctxt().with_opaque_type_inference(DefiningAnchor::Bubble).intercrate().build(); | |
101 | let selcx = &mut SelectionContext::new(&infcx); | |
2b03887a FG |
102 | let overlaps = |
103 | overlap(selcx, skip_leak_check, impl1_def_id, impl2_def_id, overlap_mode).is_some(); | |
ff7c6d11 | 104 | if !overlaps { |
2b03887a | 105 | return None; |
ff7c6d11 XL |
106 | } |
107 | ||
108 | // In the case where we detect an error, run the check again, but | |
5e7ed085 | 109 | // this time tracking intercrate ambiguity causes for better |
ff7c6d11 | 110 | // diagnostics. (These take time and can lead to false errors.) |
487cf647 FG |
111 | let infcx = |
112 | tcx.infer_ctxt().with_opaque_type_inference(DefiningAnchor::Bubble).intercrate().build(); | |
113 | let selcx = &mut SelectionContext::new(&infcx); | |
2b03887a FG |
114 | selcx.enable_tracking_intercrate_ambiguity_causes(); |
115 | Some(overlap(selcx, skip_leak_check, impl1_def_id, impl2_def_id, overlap_mode).unwrap()) | |
85aaf69f SL |
116 | } |
117 | ||
dc9dc135 XL |
118 | fn with_fresh_ty_vars<'cx, 'tcx>( |
119 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
120 | param_env: ty::ParamEnv<'tcx>, | |
121 | impl_def_id: DefId, | |
122 | ) -> ty::ImplHeader<'tcx> { | |
7cac9316 | 123 | let tcx = selcx.tcx(); |
487cf647 | 124 | let impl_substs = selcx.infcx.fresh_substs_for_item(DUMMY_SP, impl_def_id); |
7cac9316 XL |
125 | |
126 | let header = ty::ImplHeader { | |
041b39d2 | 127 | impl_def_id, |
04454e1e FG |
128 | self_ty: tcx.bound_type_of(impl_def_id).subst(tcx, impl_substs), |
129 | trait_ref: tcx.bound_impl_trait_ref(impl_def_id).map(|i| i.subst(tcx, impl_substs)), | |
0bf4aa26 XL |
130 | predicates: tcx.predicates_of(impl_def_id).instantiate(tcx, impl_substs).predicates, |
131 | }; | |
7cac9316 | 132 | |
487cf647 FG |
133 | let InferOk { value: mut header, obligations } = |
134 | selcx.infcx.at(&ObligationCause::dummy(), param_env).normalize(header); | |
7cac9316 XL |
135 | |
136 | header.predicates.extend(obligations.into_iter().map(|o| o.predicate)); | |
137 | header | |
138 | } | |
139 | ||
9cc50fc6 | 140 | /// Can both impl `a` and impl `b` be satisfied by a common type (including |
9fa01778 | 141 | /// where-clauses)? If so, returns an `ImplHeader` that unifies the two impls. |
dc9dc135 XL |
142 | fn overlap<'cx, 'tcx>( |
143 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
74b04a01 | 144 | skip_leak_check: SkipLeakCheck, |
5099ac24 FG |
145 | impl1_def_id: DefId, |
146 | impl2_def_id: DefId, | |
147 | overlap_mode: OverlapMode, | |
0731742a | 148 | ) -> Option<OverlapResult<'tcx>> { |
5099ac24 FG |
149 | debug!( |
150 | "overlap(impl1_def_id={:?}, impl2_def_id={:?}, overlap_mode={:?})", | |
151 | impl1_def_id, impl2_def_id, overlap_mode | |
152 | ); | |
c34b1796 | 153 | |
487cf647 | 154 | selcx.infcx.probe_maybe_skip_leak_check(skip_leak_check.is_yes(), |snapshot| { |
5e7ed085 | 155 | overlap_within_probe(selcx, impl1_def_id, impl2_def_id, overlap_mode, snapshot) |
74b04a01 | 156 | }) |
0731742a XL |
157 | } |
158 | ||
a2a8927a | 159 | fn overlap_within_probe<'cx, 'tcx>( |
dc9dc135 | 160 | selcx: &mut SelectionContext<'cx, 'tcx>, |
5099ac24 FG |
161 | impl1_def_id: DefId, |
162 | impl2_def_id: DefId, | |
163 | overlap_mode: OverlapMode, | |
2b03887a | 164 | snapshot: &CombinedSnapshot<'tcx>, |
0731742a | 165 | ) -> Option<OverlapResult<'tcx>> { |
487cf647 | 166 | let infcx = selcx.infcx; |
3c0e092e | 167 | |
5099ac24 | 168 | if overlap_mode.use_negative_impl() { |
487cf647 FG |
169 | if negative_impl(infcx.tcx, impl1_def_id, impl2_def_id) |
170 | || negative_impl(infcx.tcx, impl2_def_id, impl1_def_id) | |
5099ac24 FG |
171 | { |
172 | return None; | |
173 | } | |
3c0e092e XL |
174 | } |
175 | ||
0bf4aa26 | 176 | // For the purposes of this check, we don't bring any placeholder |
7cac9316 XL |
177 | // types into scope; instead, we replace the generic types with |
178 | // fresh type variables, and hence we do our evaluations in an | |
179 | // empty environment. | |
0531ce1d | 180 | let param_env = ty::ParamEnv::empty(); |
7cac9316 | 181 | |
5099ac24 FG |
182 | let impl1_header = with_fresh_ty_vars(selcx, param_env, impl1_def_id); |
183 | let impl2_header = with_fresh_ty_vars(selcx, param_env, impl2_def_id); | |
c34b1796 | 184 | |
5099ac24 FG |
185 | let obligations = equate_impl_headers(selcx, &impl1_header, &impl2_header)?; |
186 | debug!("overlap: unification check succeeded"); | |
85aaf69f | 187 | |
5099ac24 FG |
188 | if overlap_mode.use_implicit_negative() { |
189 | if implicit_negative(selcx, param_env, &impl1_header, impl2_header, obligations) { | |
74b04a01 XL |
190 | return None; |
191 | } | |
5099ac24 | 192 | } |
85aaf69f | 193 | |
2b03887a | 194 | // We disable the leak when creating the `snapshot` by using |
5e7ed085 FG |
195 | // `infcx.probe_maybe_disable_leak_check`. |
196 | if infcx.leak_check(true, snapshot).is_err() { | |
197 | debug!("overlap: leak check failed"); | |
198 | return None; | |
5099ac24 FG |
199 | } |
200 | ||
201 | let intercrate_ambiguity_causes = selcx.take_intercrate_ambiguity_causes(); | |
202 | debug!("overlap: intercrate_ambiguity_causes={:#?}", intercrate_ambiguity_causes); | |
203 | ||
204 | let involves_placeholder = | |
487cf647 | 205 | matches!(selcx.infcx.region_constraints_added_in_snapshot(snapshot), Some(true)); |
5099ac24 | 206 | |
487cf647 | 207 | let impl_header = selcx.infcx.resolve_vars_if_possible(impl1_header); |
5099ac24 FG |
208 | Some(OverlapResult { impl_header, intercrate_ambiguity_causes, involves_placeholder }) |
209 | } | |
210 | ||
211 | fn equate_impl_headers<'cx, 'tcx>( | |
212 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
213 | impl1_header: &ty::ImplHeader<'tcx>, | |
214 | impl2_header: &ty::ImplHeader<'tcx>, | |
215 | ) -> Option<PredicateObligations<'tcx>> { | |
216 | // Do `a` and `b` unify? If not, no overlap. | |
217 | debug!("equate_impl_headers(impl1_header={:?}, impl2_header={:?}", impl1_header, impl2_header); | |
218 | selcx | |
487cf647 | 219 | .infcx |
5099ac24 FG |
220 | .at(&ObligationCause::dummy(), ty::ParamEnv::empty()) |
221 | .eq_impl_headers(impl1_header, impl2_header) | |
222 | .map(|infer_ok| infer_ok.obligations) | |
223 | .ok() | |
224 | } | |
c34b1796 | 225 | |
5099ac24 FG |
226 | /// Given impl1 and impl2 check if both impls can be satisfied by a common type (including |
227 | /// where-clauses) If so, return false, otherwise return true, they are disjoint. | |
228 | fn implicit_negative<'cx, 'tcx>( | |
229 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
230 | param_env: ty::ParamEnv<'tcx>, | |
231 | impl1_header: &ty::ImplHeader<'tcx>, | |
232 | impl2_header: ty::ImplHeader<'tcx>, | |
233 | obligations: PredicateObligations<'tcx>, | |
234 | ) -> bool { | |
3c0e092e XL |
235 | // There's no overlap if obligations are unsatisfiable or if the obligation negated is |
236 | // satisfied. | |
237 | // | |
238 | // For example, given these two impl headers: | |
239 | // | |
240 | // `impl<'a> From<&'a str> for Box<dyn Error>` | |
241 | // `impl<E> From<E> for Box<dyn Error> where E: Error` | |
242 | // | |
243 | // So we have: | |
244 | // | |
245 | // `Box<dyn Error>: From<&'?a str>` | |
246 | // `Box<dyn Error>: From<?E>` | |
247 | // | |
248 | // After equating the two headers: | |
249 | // | |
250 | // `Box<dyn Error> = Box<dyn Error>` | |
251 | // So, `?E = &'?a str` and then given the where clause `&'?a str: Error`. | |
252 | // | |
253 | // If the obligation `&'?a str: Error` holds, it means that there's overlap. If that doesn't | |
254 | // hold we need to check if `&'?a str: !Error` holds, if doesn't hold there's overlap because | |
255 | // at some point an impl for `&'?a str: Error` could be added. | |
5099ac24 FG |
256 | debug!( |
257 | "implicit_negative(impl1_header={:?}, impl2_header={:?}, obligations={:?})", | |
258 | impl1_header, impl2_header, obligations | |
259 | ); | |
487cf647 | 260 | let infcx = selcx.infcx; |
5099ac24 | 261 | let opt_failing_obligation = impl1_header |
dfeec247 XL |
262 | .predicates |
263 | .iter() | |
fc512014 | 264 | .copied() |
5099ac24 | 265 | .chain(impl2_header.predicates) |
dfeec247 XL |
266 | .map(|p| infcx.resolve_vars_if_possible(p)) |
267 | .map(|p| Obligation { | |
268 | cause: ObligationCause::dummy(), | |
269 | param_env, | |
270 | recursion_depth: 0, | |
271 | predicate: p, | |
272 | }) | |
273 | .chain(obligations) | |
5099ac24 | 274 | .find(|o| !selcx.predicate_may_hold_fatal(o)); |
c34b1796 AL |
275 | |
276 | if let Some(failing_obligation) = opt_failing_obligation { | |
62682a34 | 277 | debug!("overlap: obligation unsatisfiable {:?}", failing_obligation); |
5099ac24 FG |
278 | true |
279 | } else { | |
280 | false | |
c34b1796 | 281 | } |
5099ac24 | 282 | } |
c34b1796 | 283 | |
5099ac24 FG |
284 | /// Given impl1 and impl2 check if both impls are never satisfied by a common type (including |
285 | /// where-clauses) If so, return true, they are disjoint and false otherwise. | |
487cf647 | 286 | fn negative_impl<'tcx>(tcx: TyCtxt<'tcx>, impl1_def_id: DefId, impl2_def_id: DefId) -> bool { |
5099ac24 | 287 | debug!("negative_impl(impl1_def_id={:?}, impl2_def_id={:?})", impl1_def_id, impl2_def_id); |
5099ac24 | 288 | |
5099ac24 | 289 | // Create an infcx, taking the predicates of impl1 as assumptions: |
2b03887a FG |
290 | let infcx = tcx.infer_ctxt().build(); |
291 | // create a parameter environment corresponding to a (placeholder) instantiation of impl1 | |
292 | let impl_env = tcx.param_env(impl1_def_id); | |
293 | let subject1 = match traits::fully_normalize( | |
294 | &infcx, | |
295 | ObligationCause::dummy(), | |
296 | impl_env, | |
297 | tcx.impl_subject(impl1_def_id), | |
298 | ) { | |
299 | Ok(s) => s, | |
300 | Err(err) => { | |
301 | tcx.sess.delay_span_bug( | |
302 | tcx.def_span(impl1_def_id), | |
303 | format!("failed to fully normalize {:?}: {:?}", impl1_def_id, err), | |
304 | ); | |
305 | return false; | |
306 | } | |
307 | }; | |
308 | ||
309 | // Attempt to prove that impl2 applies, given all of the above. | |
310 | let selcx = &mut SelectionContext::new(&infcx); | |
311 | let impl2_substs = infcx.fresh_substs_for_item(DUMMY_SP, impl2_def_id); | |
312 | let (subject2, obligations) = | |
313 | impl_subject_and_oblig(selcx, impl_env, impl2_def_id, impl2_substs); | |
314 | ||
315 | !equate(&infcx, impl_env, subject1, subject2, obligations, impl1_def_id) | |
5e7ed085 | 316 | } |
5099ac24 | 317 | |
2b03887a FG |
318 | fn equate<'tcx>( |
319 | infcx: &InferCtxt<'tcx>, | |
5e7ed085 | 320 | impl_env: ty::ParamEnv<'tcx>, |
5e7ed085 FG |
321 | subject1: ImplSubject<'tcx>, |
322 | subject2: ImplSubject<'tcx>, | |
323 | obligations: impl Iterator<Item = PredicateObligation<'tcx>>, | |
f2b60f7d | 324 | body_def_id: DefId, |
5e7ed085 FG |
325 | ) -> bool { |
326 | // do the impls unify? If not, not disjoint. | |
327 | let Ok(InferOk { obligations: more_obligations, .. }) = | |
328 | infcx.at(&ObligationCause::dummy(), impl_env).eq(subject1, subject2) | |
329 | else { | |
330 | debug!("explicit_disjoint: {:?} does not unify with {:?}", subject1, subject2); | |
331 | return true; | |
332 | }; | |
5099ac24 | 333 | |
5e7ed085 FG |
334 | let opt_failing_obligation = obligations |
335 | .into_iter() | |
336 | .chain(more_obligations) | |
487cf647 | 337 | .find(|o| negative_impl_exists(infcx, o, body_def_id)); |
5e7ed085 FG |
338 | |
339 | if let Some(failing_obligation) = opt_failing_obligation { | |
340 | debug!("overlap: obligation unsatisfiable {:?}", failing_obligation); | |
341 | false | |
342 | } else { | |
343 | true | |
344 | } | |
5099ac24 | 345 | } |
f035d41b | 346 | |
5e7ed085 | 347 | /// Try to prove that a negative impl exist for the given obligation and its super predicates. |
487cf647 FG |
348 | #[instrument(level = "debug", skip(infcx))] |
349 | fn negative_impl_exists<'tcx>( | |
350 | infcx: &InferCtxt<'tcx>, | |
5099ac24 | 351 | o: &PredicateObligation<'tcx>, |
f2b60f7d | 352 | body_def_id: DefId, |
5099ac24 | 353 | ) -> bool { |
487cf647 | 354 | if resolve_negative_obligation(infcx.fork(), o, body_def_id) { |
5e7ed085 FG |
355 | return true; |
356 | } | |
357 | ||
358 | // Try to prove a negative obligation exists for super predicates | |
487cf647 FG |
359 | for o in util::elaborate_predicates(infcx.tcx, iter::once(o.predicate)) { |
360 | if resolve_negative_obligation(infcx.fork(), &o, body_def_id) { | |
5e7ed085 FG |
361 | return true; |
362 | } | |
363 | } | |
364 | ||
365 | false | |
366 | } | |
367 | ||
368 | #[instrument(level = "debug", skip(infcx))] | |
2b03887a FG |
369 | fn resolve_negative_obligation<'tcx>( |
370 | infcx: InferCtxt<'tcx>, | |
5e7ed085 | 371 | o: &PredicateObligation<'tcx>, |
f2b60f7d | 372 | body_def_id: DefId, |
5e7ed085 | 373 | ) -> bool { |
5099ac24 | 374 | let tcx = infcx.tcx; |
0731742a | 375 | |
5e7ed085 FG |
376 | let Some(o) = o.flip_polarity(tcx) else { |
377 | return false; | |
378 | }; | |
0731742a | 379 | |
f2b60f7d FG |
380 | let param_env = o.param_env; |
381 | if !super::fully_solve_obligation(&infcx, o).is_empty() { | |
5e7ed085 FG |
382 | return false; |
383 | } | |
384 | ||
f2b60f7d FG |
385 | let (body_id, body_def_id) = if let Some(body_def_id) = body_def_id.as_local() { |
386 | (tcx.hir().local_def_id_to_hir_id(body_def_id), body_def_id) | |
387 | } else { | |
388 | (CRATE_HIR_ID, CRATE_DEF_ID) | |
389 | }; | |
390 | ||
391 | let ocx = ObligationCtxt::new(&infcx); | |
392 | let wf_tys = ocx.assumed_wf_types(param_env, DUMMY_SP, body_def_id); | |
393 | let outlives_env = OutlivesEnvironment::with_bounds( | |
394 | param_env, | |
395 | Some(&infcx), | |
396 | infcx.implied_bounds_tys(param_env, body_id, wf_tys), | |
397 | ); | |
398 | ||
064997fb | 399 | infcx.process_registered_region_obligations(outlives_env.region_bound_pairs(), param_env); |
5e7ed085 | 400 | |
064997fb | 401 | infcx.resolve_regions(&outlives_env).is_empty() |
c34b1796 AL |
402 | } |
403 | ||
dc9dc135 XL |
404 | pub fn trait_ref_is_knowable<'tcx>( |
405 | tcx: TyCtxt<'tcx>, | |
406 | trait_ref: ty::TraitRef<'tcx>, | |
f2b60f7d | 407 | ) -> Result<(), Conflict> { |
62682a34 | 408 | debug!("trait_ref_is_knowable(trait_ref={:?})", trait_ref); |
ff7c6d11 XL |
409 | if orphan_check_trait_ref(tcx, trait_ref, InCrate::Remote).is_ok() { |
410 | // A downstream or cousin crate is allowed to implement some | |
411 | // substitution of this trait-ref. | |
f2b60f7d | 412 | return Err(Conflict::Downstream); |
c34b1796 AL |
413 | } |
414 | ||
ff7c6d11 XL |
415 | if trait_ref_is_local_or_fundamental(tcx, trait_ref) { |
416 | // This is a local or fundamental trait, so future-compatibility | |
417 | // is no concern. We know that downstream/cousin crates are not | |
418 | // allowed to implement a substitution of this trait ref, which | |
419 | // means impls could only come from dependencies of this crate, | |
420 | // which we already know about. | |
f2b60f7d | 421 | return Ok(()); |
c34b1796 AL |
422 | } |
423 | ||
ff7c6d11 XL |
424 | // This is a remote non-fundamental trait, so if another crate |
425 | // can be the "final owner" of a substitution of this trait-ref, | |
426 | // they are allowed to implement it future-compatibly. | |
427 | // | |
428 | // However, if we are a final owner, then nobody else can be, | |
429 | // and if we are an intermediate owner, then we don't care | |
430 | // about future-compatibility, which means that we're OK if | |
431 | // we are an owner. | |
432 | if orphan_check_trait_ref(tcx, trait_ref, InCrate::Local).is_ok() { | |
433 | debug!("trait_ref_is_knowable: orphan check passed"); | |
f2b60f7d | 434 | Ok(()) |
ff7c6d11 XL |
435 | } else { |
436 | debug!("trait_ref_is_knowable: nonlocal, nonfundamental, unowned"); | |
f2b60f7d | 437 | Err(Conflict::Upstream) |
ff7c6d11 | 438 | } |
85aaf69f SL |
439 | } |
440 | ||
dc9dc135 XL |
441 | pub fn trait_ref_is_local_or_fundamental<'tcx>( |
442 | tcx: TyCtxt<'tcx>, | |
443 | trait_ref: ty::TraitRef<'tcx>, | |
444 | ) -> bool { | |
48663c56 | 445 | trait_ref.def_id.krate == LOCAL_CRATE || tcx.has_attr(trait_ref.def_id, sym::fundamental) |
ea8adc8c XL |
446 | } |
447 | ||
1a4d82fc | 448 | pub enum OrphanCheckErr<'tcx> { |
e74abb32 | 449 | NonLocalInputType(Vec<(Ty<'tcx>, bool /* Is this the first input type? */)>), |
60c5eb7d | 450 | UncoveredTy(Ty<'tcx>, Option<Ty<'tcx>>), |
1a4d82fc JJ |
451 | } |
452 | ||
453 | /// Checks the coherence orphan rules. `impl_def_id` should be the | |
9fa01778 | 454 | /// `DefId` of a trait impl. To pass, either the trait must be local, or else |
1a4d82fc JJ |
455 | /// two conditions must be satisfied: |
456 | /// | |
457 | /// 1. All type parameters in `Self` must be "covered" by some local type constructor. | |
458 | /// 2. Some local type must appear in `Self`. | |
dfeec247 | 459 | pub fn orphan_check(tcx: TyCtxt<'_>, impl_def_id: DefId) -> Result<(), OrphanCheckErr<'_>> { |
62682a34 | 460 | debug!("orphan_check({:?})", impl_def_id); |
1a4d82fc JJ |
461 | |
462 | // We only except this routine to be invoked on implementations | |
463 | // of a trait, not inherent implementations. | |
c1a9b12d | 464 | let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); |
62682a34 | 465 | debug!("orphan_check: trait_ref={:?}", trait_ref); |
1a4d82fc JJ |
466 | |
467 | // If the *trait* is local to the crate, ok. | |
e9174d1e | 468 | if trait_ref.def_id.is_local() { |
dfeec247 | 469 | debug!("trait {:?} is local to current crate", trait_ref.def_id); |
1a4d82fc JJ |
470 | return Ok(()); |
471 | } | |
472 | ||
ff7c6d11 | 473 | orphan_check_trait_ref(tcx, trait_ref, InCrate::Local) |
c34b1796 AL |
474 | } |
475 | ||
9fa01778 | 476 | /// Checks whether a trait-ref is potentially implementable by a crate. |
ff7c6d11 XL |
477 | /// |
478 | /// The current rule is that a trait-ref orphan checks in a crate C: | |
479 | /// | |
480 | /// 1. Order the parameters in the trait-ref in subst order - Self first, | |
0731742a | 481 | /// others linearly (e.g., `<U as Foo<V, W>>` is U < V < W). |
ff7c6d11 XL |
482 | /// 2. Of these type parameters, there is at least one type parameter |
483 | /// in which, walking the type as a tree, you can reach a type local | |
484 | /// to C where all types in-between are fundamental types. Call the | |
485 | /// first such parameter the "local key parameter". | |
0731742a | 486 | /// - e.g., `Box<LocalType>` is OK, because you can visit LocalType |
ff7c6d11 XL |
487 | /// going through `Box`, which is fundamental. |
488 | /// - similarly, `FundamentalPair<Vec<()>, Box<LocalType>>` is OK for | |
489 | /// the same reason. | |
490 | /// - but (knowing that `Vec<T>` is non-fundamental, and assuming it's | |
491 | /// not local), `Vec<LocalType>` is bad, because `Vec<->` is between | |
492 | /// the local type and the type parameter. | |
3dfed10e XL |
493 | /// 3. Before this local type, no generic type parameter of the impl must |
494 | /// be reachable through fundamental types. | |
495 | /// - e.g. `impl<T> Trait<LocalType> for Vec<T>` is fine, as `Vec` is not fundamental. | |
923072b8 | 496 | /// - while `impl<T> Trait<LocalType> for Box<T>` results in an error, as `T` is |
3dfed10e | 497 | /// reachable through the fundamental type `Box`. |
ff7c6d11 XL |
498 | /// 4. Every type in the local key parameter not known in C, going |
499 | /// through the parameter's type tree, must appear only as a subtree of | |
500 | /// a type local to C, with only fundamental types between the type | |
501 | /// local to C and the local key parameter. | |
0731742a | 502 | /// - e.g., `Vec<LocalType<T>>>` (or equivalently `Box<Vec<LocalType<T>>>`) |
ff7c6d11 XL |
503 | /// is bad, because the only local type with `T` as a subtree is |
504 | /// `LocalType<T>`, and `Vec<->` is between it and the type parameter. | |
505 | /// - similarly, `FundamentalPair<LocalType<T>, T>` is bad, because | |
0531ce1d | 506 | /// the second occurrence of `T` is not a subtree of *any* local type. |
ff7c6d11 XL |
507 | /// - however, `LocalType<Vec<T>>` is OK, because `T` is a subtree of |
508 | /// `LocalType<Vec<T>>`, which is local and has no types between it and | |
509 | /// the type parameter. | |
510 | /// | |
511 | /// The orphan rules actually serve several different purposes: | |
512 | /// | |
0731742a | 513 | /// 1. They enable link-safety - i.e., 2 mutually-unknowing crates (where |
ff7c6d11 XL |
514 | /// every type local to one crate is unknown in the other) can't implement |
515 | /// the same trait-ref. This follows because it can be seen that no such | |
516 | /// type can orphan-check in 2 such crates. | |
517 | /// | |
518 | /// To check that a local impl follows the orphan rules, we check it in | |
519 | /// InCrate::Local mode, using type parameters for the "generic" types. | |
520 | /// | |
521 | /// 2. They ground negative reasoning for coherence. If a user wants to | |
522 | /// write both a conditional blanket impl and a specific impl, we need to | |
523 | /// make sure they do not overlap. For example, if we write | |
04454e1e | 524 | /// ```ignore (illustrative) |
ff7c6d11 XL |
525 | /// impl<T> IntoIterator for Vec<T> |
526 | /// impl<T: Iterator> IntoIterator for T | |
527 | /// ``` | |
528 | /// We need to be able to prove that `Vec<$0>: !Iterator` for every type $0. | |
529 | /// We can observe that this holds in the current crate, but we need to make | |
530 | /// sure this will also hold in all unknown crates (both "independent" crates, | |
531 | /// which we need for link-safety, and also child crates, because we don't want | |
532 | /// child crates to get error for impl conflicts in a *dependency*). | |
533 | /// | |
534 | /// For that, we only allow negative reasoning if, for every assignment to the | |
535 | /// inference variables, every unknown crate would get an orphan error if they | |
536 | /// try to implement this trait-ref. To check for this, we use InCrate::Remote | |
537 | /// mode. That is sound because we already know all the impls from known crates. | |
538 | /// | |
f9f354fc | 539 | /// 3. For non-`#[fundamental]` traits, they guarantee that parent crates can |
ff7c6d11 XL |
540 | /// add "non-blanket" impls without breaking negative reasoning in dependent |
541 | /// crates. This is the "rebalancing coherence" (RFC 1023) restriction. | |
542 | /// | |
543 | /// For that, we only a allow crate to perform negative reasoning on | |
f9f354fc | 544 | /// non-local-non-`#[fundamental]` only if there's a local key parameter as per (2). |
ff7c6d11 XL |
545 | /// |
546 | /// Because we never perform negative reasoning generically (coherence does | |
547 | /// not involve type parameters), this can be interpreted as doing the full | |
548 | /// orphan check (using InCrate::Local mode), substituting non-local known | |
549 | /// types for all inference variables. | |
550 | /// | |
551 | /// This allows for crates to future-compatibly add impls as long as they | |
552 | /// can't apply to types with a key parameter in a child crate - applying | |
553 | /// the rules, this basically means that every type parameter in the impl | |
554 | /// must appear behind a non-fundamental type (because this is not a | |
555 | /// type-system requirement, crate owners might also go for "semantic | |
556 | /// future-compatibility" involving things such as sealed traits, but | |
557 | /// the above requirement is sufficient, and is necessary in "open world" | |
558 | /// cases). | |
559 | /// | |
560 | /// Note that this function is never called for types that have both type | |
561 | /// parameters and inference variables. | |
dc9dc135 | 562 | fn orphan_check_trait_ref<'tcx>( |
e74abb32 | 563 | tcx: TyCtxt<'tcx>, |
dc9dc135 XL |
564 | trait_ref: ty::TraitRef<'tcx>, |
565 | in_crate: InCrate, | |
566 | ) -> Result<(), OrphanCheckErr<'tcx>> { | |
dfeec247 | 567 | debug!("orphan_check_trait_ref(trait_ref={:?}, in_crate={:?})", trait_ref, in_crate); |
ff7c6d11 | 568 | |
5099ac24 | 569 | if trait_ref.needs_infer() && trait_ref.needs_subst() { |
dfeec247 XL |
570 | bug!( |
571 | "can't orphan check a trait ref with both params and inference variables {:?}", | |
572 | trait_ref | |
573 | ); | |
ff7c6d11 | 574 | } |
c34b1796 | 575 | |
064997fb FG |
576 | let mut checker = OrphanChecker::new(tcx, in_crate); |
577 | match trait_ref.visit_with(&mut checker) { | |
578 | ControlFlow::Continue(()) => Err(OrphanCheckErr::NonLocalInputType(checker.non_local_tys)), | |
579 | ControlFlow::Break(OrphanCheckEarlyExit::ParamTy(ty)) => { | |
580 | // Does there exist some local type after the `ParamTy`. | |
581 | checker.search_first_local_ty = true; | |
582 | if let Some(OrphanCheckEarlyExit::LocalTy(local_ty)) = | |
583 | trait_ref.visit_with(&mut checker).break_value() | |
584 | { | |
585 | Err(OrphanCheckErr::UncoveredTy(ty, Some(local_ty))) | |
586 | } else { | |
587 | Err(OrphanCheckErr::UncoveredTy(ty, None)) | |
ba9703b0 | 588 | } |
e74abb32 | 589 | } |
064997fb | 590 | ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(_)) => Ok(()), |
60c5eb7d | 591 | } |
c34b1796 AL |
592 | } |
593 | ||
064997fb | 594 | struct OrphanChecker<'tcx> { |
a2a8927a | 595 | tcx: TyCtxt<'tcx>, |
a2a8927a | 596 | in_crate: InCrate, |
064997fb FG |
597 | in_self_ty: bool, |
598 | /// Ignore orphan check failures and exclusively search for the first | |
599 | /// local type. | |
600 | search_first_local_ty: bool, | |
601 | non_local_tys: Vec<(Ty<'tcx>, bool)>, | |
602 | } | |
603 | ||
604 | impl<'tcx> OrphanChecker<'tcx> { | |
605 | fn new(tcx: TyCtxt<'tcx>, in_crate: InCrate) -> Self { | |
606 | OrphanChecker { | |
607 | tcx, | |
608 | in_crate, | |
609 | in_self_ty: true, | |
610 | search_first_local_ty: false, | |
611 | non_local_tys: Vec::new(), | |
dfeec247 | 612 | } |
e74abb32 | 613 | } |
c34b1796 | 614 | |
064997fb FG |
615 | fn found_non_local_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<OrphanCheckEarlyExit<'tcx>> { |
616 | self.non_local_tys.push((t, self.in_self_ty)); | |
617 | ControlFlow::CONTINUE | |
618 | } | |
ba9703b0 | 619 | |
064997fb FG |
620 | fn found_param_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<OrphanCheckEarlyExit<'tcx>> { |
621 | if self.search_first_local_ty { | |
622 | ControlFlow::CONTINUE | |
623 | } else { | |
624 | ControlFlow::Break(OrphanCheckEarlyExit::ParamTy(t)) | |
ba9703b0 | 625 | } |
064997fb | 626 | } |
ba9703b0 | 627 | |
064997fb FG |
628 | fn def_id_is_local(&mut self, def_id: DefId) -> bool { |
629 | match self.in_crate { | |
630 | InCrate::Local => def_id.is_local(), | |
631 | InCrate::Remote => false, | |
632 | } | |
633 | } | |
c34b1796 AL |
634 | } |
635 | ||
064997fb FG |
636 | enum OrphanCheckEarlyExit<'tcx> { |
637 | ParamTy(Ty<'tcx>), | |
638 | LocalTy(Ty<'tcx>), | |
ff7c6d11 XL |
639 | } |
640 | ||
064997fb FG |
641 | impl<'tcx> TypeVisitor<'tcx> for OrphanChecker<'tcx> { |
642 | type BreakTy = OrphanCheckEarlyExit<'tcx>; | |
643 | fn visit_region(&mut self, _r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> { | |
644 | ControlFlow::CONTINUE | |
645 | } | |
abe05a73 | 646 | |
064997fb FG |
647 | fn visit_ty(&mut self, ty: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { |
648 | let result = match *ty.kind() { | |
649 | ty::Bool | |
650 | | ty::Char | |
651 | | ty::Int(..) | |
652 | | ty::Uint(..) | |
653 | | ty::Float(..) | |
654 | | ty::Str | |
655 | | ty::FnDef(..) | |
656 | | ty::FnPtr(_) | |
657 | | ty::Array(..) | |
658 | | ty::Slice(..) | |
659 | | ty::RawPtr(..) | |
660 | | ty::Never | |
661 | | ty::Tuple(..) | |
662 | | ty::Projection(..) => self.found_non_local_ty(ty), | |
663 | ||
664 | ty::Param(..) => self.found_param_ty(ty), | |
665 | ||
666 | ty::Placeholder(..) | ty::Bound(..) | ty::Infer(..) => match self.in_crate { | |
667 | InCrate::Local => self.found_non_local_ty(ty), | |
668 | // The inference variable might be unified with a local | |
669 | // type in that remote crate. | |
670 | InCrate::Remote => ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)), | |
671 | }, | |
672 | ||
673 | // For fundamental types, we just look inside of them. | |
674 | ty::Ref(_, ty, _) => ty.visit_with(self), | |
675 | ty::Adt(def, substs) => { | |
676 | if self.def_id_is_local(def.did()) { | |
677 | ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)) | |
678 | } else if def.is_fundamental() { | |
679 | substs.visit_with(self) | |
680 | } else { | |
681 | self.found_non_local_ty(ty) | |
682 | } | |
0731742a | 683 | } |
064997fb FG |
684 | ty::Foreign(def_id) => { |
685 | if self.def_id_is_local(def_id) { | |
686 | ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)) | |
687 | } else { | |
688 | self.found_non_local_ty(ty) | |
689 | } | |
690 | } | |
691 | ty::Dynamic(tt, ..) => { | |
692 | let principal = tt.principal().map(|p| p.def_id()); | |
693 | if principal.map_or(false, |p| self.def_id_is_local(p)) { | |
694 | ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)) | |
695 | } else { | |
696 | self.found_non_local_ty(ty) | |
697 | } | |
698 | } | |
699 | ty::Error(_) => ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)), | |
700 | ty::Closure(..) | ty::Generator(..) | ty::GeneratorWitness(..) => { | |
701 | self.tcx.sess.delay_span_bug( | |
702 | DUMMY_SP, | |
703 | format!("ty_is_local invoked on closure or generator: {:?}", ty), | |
704 | ); | |
705 | ControlFlow::Break(OrphanCheckEarlyExit::LocalTy(ty)) | |
706 | } | |
707 | ty::Opaque(..) => { | |
708 | // This merits some explanation. | |
709 | // Normally, opaque types are not involved when performing | |
710 | // coherence checking, since it is illegal to directly | |
711 | // implement a trait on an opaque type. However, we might | |
712 | // end up looking at an opaque type during coherence checking | |
713 | // if an opaque type gets used within another type (e.g. as | |
714 | // the type of a field) when checking for auto trait or `Sized` | |
715 | // impls. This requires us to decide whether or not an opaque | |
716 | // type should be considered 'local' or not. | |
717 | // | |
718 | // We choose to treat all opaque types as non-local, even | |
719 | // those that appear within the same crate. This seems | |
720 | // somewhat surprising at first, but makes sense when | |
721 | // you consider that opaque types are supposed to hide | |
722 | // the underlying type *within the same crate*. When an | |
723 | // opaque type is used from outside the module | |
724 | // where it is declared, it should be impossible to observe | |
725 | // anything about it other than the traits that it implements. | |
726 | // | |
727 | // The alternative would be to look at the underlying type | |
728 | // to determine whether or not the opaque type itself should | |
729 | // be considered local. However, this could make it a breaking change | |
730 | // to switch the underlying ('defining') type from a local type | |
731 | // to a remote type. This would violate the rule that opaque | |
732 | // types should be completely opaque apart from the traits | |
733 | // that they implement, so we don't use this behavior. | |
734 | self.found_non_local_ty(ty) | |
735 | } | |
736 | }; | |
737 | // A bit of a hack, the `OrphanChecker` is only used to visit a `TraitRef`, so | |
738 | // the first type we visit is always the self type. | |
739 | self.in_self_ty = false; | |
740 | result | |
741 | } | |
1a4d82fc | 742 | |
f2b60f7d FG |
743 | /// All possible values for a constant parameter already exist |
744 | /// in the crate defining the trait, so they are always non-local[^1]. | |
745 | /// | |
746 | /// Because there's no way to have an impl where the first local | |
747 | /// generic argument is a constant, we also don't have to fail | |
748 | /// the orphan check when encountering a parameter or a generic constant. | |
749 | /// | |
750 | /// This means that we can completely ignore constants during the orphan check. | |
751 | /// | |
752 | /// See `src/test/ui/coherence/const-generics-orphan-check-ok.rs` for examples. | |
753 | /// | |
754 | /// [^1]: This might not hold for function pointers or trait objects in the future. | |
755 | /// As these should be quite rare as const arguments and especially rare as impl | |
756 | /// parameters, allowing uncovered const parameters in impls seems more useful | |
757 | /// than allowing `impl<T> Trait<local_fn_ptr, T> for i32` to compile. | |
064997fb FG |
758 | fn visit_const(&mut self, _c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> { |
759 | ControlFlow::CONTINUE | |
1a4d82fc JJ |
760 | } |
761 | } |