]>
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}; |
9fa01778 | 9 | use crate::traits::select::IntercrateAmbiguityCause; |
5e7ed085 | 10 | use crate::traits::util::impl_subject_and_oblig; |
74b04a01 | 11 | use crate::traits::SkipLeakCheck; |
3c0e092e | 12 | use crate::traits::{ |
5099ac24 | 13 | self, FulfillmentContext, Normalized, Obligation, ObligationCause, PredicateObligation, |
064997fb | 14 | PredicateObligations, SelectionContext, TraitEngineExt, |
3c0e092e | 15 | }; |
064997fb | 16 | use rustc_data_structures::fx::FxIndexSet; |
5e7ed085 | 17 | use rustc_errors::Diagnostic; |
dfeec247 | 18 | use rustc_hir::def_id::{DefId, LOCAL_CRATE}; |
5e7ed085 FG |
19 | use rustc_infer::infer::{InferCtxt, TyCtxtInferExt}; |
20 | use rustc_infer::traits::{util, TraitEngine}; | |
5099ac24 | 21 | use rustc_middle::traits::specialization_graph::OverlapMode; |
923072b8 | 22 | use rustc_middle::ty::fast_reject::{DeepRejectCtxt, TreatParams}; |
ba9703b0 | 23 | use rustc_middle::ty::subst::Subst; |
064997fb FG |
24 | use rustc_middle::ty::visit::TypeVisitable; |
25 | use rustc_middle::ty::{self, ImplSubject, Ty, TyCtxt, TypeVisitor}; | |
dfeec247 XL |
26 | use rustc_span::symbol::sym; |
27 | use rustc_span::DUMMY_SP; | |
5e7ed085 | 28 | use std::fmt::Debug; |
ba9703b0 | 29 | use std::iter; |
064997fb | 30 | use std::ops::ControlFlow; |
1a4d82fc | 31 | |
ff7c6d11 XL |
32 | /// Whether we do the orphan check relative to this crate or |
33 | /// to some remote crate. | |
34 | #[derive(Copy, Clone, Debug)] | |
35 | enum InCrate { | |
36 | Local, | |
dfeec247 | 37 | Remote, |
ff7c6d11 XL |
38 | } |
39 | ||
40 | #[derive(Debug, Copy, Clone)] | |
41 | pub enum Conflict { | |
42 | Upstream, | |
74b04a01 | 43 | Downstream, |
ff7c6d11 | 44 | } |
c34b1796 | 45 | |
ea8adc8c XL |
46 | pub struct OverlapResult<'tcx> { |
47 | pub impl_header: ty::ImplHeader<'tcx>, | |
064997fb | 48 | pub intercrate_ambiguity_causes: FxIndexSet<IntercrateAmbiguityCause>, |
0731742a | 49 | |
9fa01778 | 50 | /// `true` if the overlap might've been permitted before the shift |
0731742a XL |
51 | /// to universes. |
52 | pub involves_placeholder: bool, | |
53 | } | |
54 | ||
5e7ed085 | 55 | pub fn add_placeholder_note(err: &mut Diagnostic) { |
74b04a01 | 56 | err.note( |
0731742a | 57 | "this behavior recently changed as a result of a bug fix; \ |
74b04a01 XL |
58 | see rust-lang/rust#56105 for details", |
59 | ); | |
ea8adc8c XL |
60 | } |
61 | ||
ff7c6d11 XL |
62 | /// If there are types that satisfy both impls, invokes `on_overlap` |
63 | /// with a suitably-freshened `ImplHeader` with those types | |
64 | /// substituted. Otherwise, invokes `no_overlap`. | |
5099ac24 | 65 | #[instrument(skip(tcx, skip_leak_check, on_overlap, no_overlap), level = "debug")] |
416331ca XL |
66 | pub fn overlapping_impls<F1, F2, R>( |
67 | tcx: TyCtxt<'_>, | |
ff7c6d11 XL |
68 | impl1_def_id: DefId, |
69 | impl2_def_id: DefId, | |
74b04a01 | 70 | skip_leak_check: SkipLeakCheck, |
5099ac24 | 71 | overlap_mode: OverlapMode, |
ff7c6d11 XL |
72 | on_overlap: F1, |
73 | no_overlap: F2, | |
74 | ) -> R | |
75 | where | |
76 | F1: FnOnce(OverlapResult<'_>) -> R, | |
77 | F2: FnOnce() -> R, | |
1a4d82fc | 78 | { |
6a06907d XL |
79 | // Before doing expensive operations like entering an inference context, do |
80 | // a quick check via fast_reject to tell if the impl headers could possibly | |
81 | // unify. | |
923072b8 | 82 | let drcx = DeepRejectCtxt { treat_obligation_params: TreatParams::AsInfer }; |
6a06907d XL |
83 | let impl1_ref = tcx.impl_trait_ref(impl1_def_id); |
84 | let impl2_ref = tcx.impl_trait_ref(impl2_def_id); | |
923072b8 FG |
85 | let may_overlap = match (impl1_ref, impl2_ref) { |
86 | (Some(a), Some(b)) => iter::zip(a.substs, b.substs) | |
87 | .all(|(arg1, arg2)| drcx.generic_args_may_unify(arg1, arg2)), | |
88 | (None, None) => { | |
89 | let self_ty1 = tcx.type_of(impl1_def_id); | |
90 | let self_ty2 = tcx.type_of(impl2_def_id); | |
91 | drcx.types_may_unify(self_ty1, self_ty2) | |
cdc7bbd5 | 92 | } |
923072b8 FG |
93 | _ => bug!("unexpected impls: {impl1_def_id:?} {impl2_def_id:?}"), |
94 | }; | |
95 | ||
96 | if !may_overlap { | |
6a06907d XL |
97 | // Some types involved are definitely different, so the impls couldn't possibly overlap. |
98 | debug!("overlapping_impls: fast_reject early-exit"); | |
99 | return no_overlap(); | |
100 | } | |
1a4d82fc | 101 | |
ff7c6d11 | 102 | let overlaps = tcx.infer_ctxt().enter(|infcx| { |
74b04a01 | 103 | let selcx = &mut SelectionContext::intercrate(&infcx); |
5099ac24 | 104 | overlap(selcx, skip_leak_check, impl1_def_id, impl2_def_id, overlap_mode).is_some() |
ff7c6d11 XL |
105 | }); |
106 | ||
107 | if !overlaps { | |
108 | return no_overlap(); | |
109 | } | |
110 | ||
111 | // In the case where we detect an error, run the check again, but | |
5e7ed085 | 112 | // this time tracking intercrate ambiguity causes for better |
ff7c6d11 XL |
113 | // diagnostics. (These take time and can lead to false errors.) |
114 | tcx.infer_ctxt().enter(|infcx| { | |
74b04a01 | 115 | let selcx = &mut SelectionContext::intercrate(&infcx); |
ff7c6d11 | 116 | selcx.enable_tracking_intercrate_ambiguity_causes(); |
5099ac24 FG |
117 | on_overlap( |
118 | overlap(selcx, skip_leak_check, impl1_def_id, impl2_def_id, overlap_mode).unwrap(), | |
119 | ) | |
ff7c6d11 | 120 | }) |
85aaf69f SL |
121 | } |
122 | ||
dc9dc135 XL |
123 | fn with_fresh_ty_vars<'cx, 'tcx>( |
124 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
125 | param_env: ty::ParamEnv<'tcx>, | |
126 | impl_def_id: DefId, | |
127 | ) -> ty::ImplHeader<'tcx> { | |
7cac9316 XL |
128 | let tcx = selcx.tcx(); |
129 | let impl_substs = selcx.infcx().fresh_substs_for_item(DUMMY_SP, impl_def_id); | |
130 | ||
131 | let header = ty::ImplHeader { | |
041b39d2 | 132 | impl_def_id, |
04454e1e FG |
133 | self_ty: tcx.bound_type_of(impl_def_id).subst(tcx, impl_substs), |
134 | trait_ref: tcx.bound_impl_trait_ref(impl_def_id).map(|i| i.subst(tcx, impl_substs)), | |
0bf4aa26 XL |
135 | predicates: tcx.predicates_of(impl_def_id).instantiate(tcx, impl_substs).predicates, |
136 | }; | |
7cac9316 XL |
137 | |
138 | let Normalized { value: mut header, obligations } = | |
fc512014 | 139 | traits::normalize(selcx, param_env, ObligationCause::dummy(), header); |
7cac9316 XL |
140 | |
141 | header.predicates.extend(obligations.into_iter().map(|o| o.predicate)); | |
142 | header | |
143 | } | |
144 | ||
9cc50fc6 | 145 | /// Can both impl `a` and impl `b` be satisfied by a common type (including |
9fa01778 | 146 | /// where-clauses)? If so, returns an `ImplHeader` that unifies the two impls. |
dc9dc135 XL |
147 | fn overlap<'cx, 'tcx>( |
148 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
74b04a01 | 149 | skip_leak_check: SkipLeakCheck, |
5099ac24 FG |
150 | impl1_def_id: DefId, |
151 | impl2_def_id: DefId, | |
152 | overlap_mode: OverlapMode, | |
0731742a | 153 | ) -> Option<OverlapResult<'tcx>> { |
5099ac24 FG |
154 | debug!( |
155 | "overlap(impl1_def_id={:?}, impl2_def_id={:?}, overlap_mode={:?})", | |
156 | impl1_def_id, impl2_def_id, overlap_mode | |
157 | ); | |
c34b1796 | 158 | |
74b04a01 | 159 | selcx.infcx().probe_maybe_skip_leak_check(skip_leak_check.is_yes(), |snapshot| { |
5e7ed085 | 160 | overlap_within_probe(selcx, impl1_def_id, impl2_def_id, overlap_mode, snapshot) |
74b04a01 | 161 | }) |
0731742a XL |
162 | } |
163 | ||
a2a8927a | 164 | fn overlap_within_probe<'cx, 'tcx>( |
dc9dc135 | 165 | selcx: &mut SelectionContext<'cx, 'tcx>, |
5099ac24 FG |
166 | impl1_def_id: DefId, |
167 | impl2_def_id: DefId, | |
168 | overlap_mode: OverlapMode, | |
0731742a XL |
169 | snapshot: &CombinedSnapshot<'_, 'tcx>, |
170 | ) -> Option<OverlapResult<'tcx>> { | |
5099ac24 | 171 | let infcx = selcx.infcx(); |
3c0e092e | 172 | |
5099ac24 FG |
173 | if overlap_mode.use_negative_impl() { |
174 | if negative_impl(selcx, impl1_def_id, impl2_def_id) | |
175 | || negative_impl(selcx, impl2_def_id, impl1_def_id) | |
176 | { | |
177 | return None; | |
178 | } | |
3c0e092e XL |
179 | } |
180 | ||
0bf4aa26 | 181 | // For the purposes of this check, we don't bring any placeholder |
7cac9316 XL |
182 | // types into scope; instead, we replace the generic types with |
183 | // fresh type variables, and hence we do our evaluations in an | |
184 | // empty environment. | |
0531ce1d | 185 | let param_env = ty::ParamEnv::empty(); |
7cac9316 | 186 | |
5099ac24 FG |
187 | let impl1_header = with_fresh_ty_vars(selcx, param_env, impl1_def_id); |
188 | let impl2_header = with_fresh_ty_vars(selcx, param_env, impl2_def_id); | |
c34b1796 | 189 | |
5099ac24 FG |
190 | let obligations = equate_impl_headers(selcx, &impl1_header, &impl2_header)?; |
191 | debug!("overlap: unification check succeeded"); | |
85aaf69f | 192 | |
5099ac24 FG |
193 | if overlap_mode.use_implicit_negative() { |
194 | if implicit_negative(selcx, param_env, &impl1_header, impl2_header, obligations) { | |
74b04a01 XL |
195 | return None; |
196 | } | |
5099ac24 | 197 | } |
85aaf69f | 198 | |
5e7ed085 FG |
199 | // We disable the leak when when creating the `snapshot` by using |
200 | // `infcx.probe_maybe_disable_leak_check`. | |
201 | if infcx.leak_check(true, snapshot).is_err() { | |
202 | debug!("overlap: leak check failed"); | |
203 | return None; | |
5099ac24 FG |
204 | } |
205 | ||
206 | let intercrate_ambiguity_causes = selcx.take_intercrate_ambiguity_causes(); | |
207 | debug!("overlap: intercrate_ambiguity_causes={:#?}", intercrate_ambiguity_causes); | |
208 | ||
209 | let involves_placeholder = | |
210 | matches!(selcx.infcx().region_constraints_added_in_snapshot(snapshot), Some(true)); | |
211 | ||
212 | let impl_header = selcx.infcx().resolve_vars_if_possible(impl1_header); | |
213 | Some(OverlapResult { impl_header, intercrate_ambiguity_causes, involves_placeholder }) | |
214 | } | |
215 | ||
216 | fn equate_impl_headers<'cx, 'tcx>( | |
217 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
218 | impl1_header: &ty::ImplHeader<'tcx>, | |
219 | impl2_header: &ty::ImplHeader<'tcx>, | |
220 | ) -> Option<PredicateObligations<'tcx>> { | |
221 | // Do `a` and `b` unify? If not, no overlap. | |
222 | debug!("equate_impl_headers(impl1_header={:?}, impl2_header={:?}", impl1_header, impl2_header); | |
223 | selcx | |
224 | .infcx() | |
225 | .at(&ObligationCause::dummy(), ty::ParamEnv::empty()) | |
226 | .eq_impl_headers(impl1_header, impl2_header) | |
227 | .map(|infer_ok| infer_ok.obligations) | |
228 | .ok() | |
229 | } | |
c34b1796 | 230 | |
5099ac24 FG |
231 | /// Given impl1 and impl2 check if both impls can be satisfied by a common type (including |
232 | /// where-clauses) If so, return false, otherwise return true, they are disjoint. | |
233 | fn implicit_negative<'cx, 'tcx>( | |
234 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
235 | param_env: ty::ParamEnv<'tcx>, | |
236 | impl1_header: &ty::ImplHeader<'tcx>, | |
237 | impl2_header: ty::ImplHeader<'tcx>, | |
238 | obligations: PredicateObligations<'tcx>, | |
239 | ) -> bool { | |
3c0e092e XL |
240 | // There's no overlap if obligations are unsatisfiable or if the obligation negated is |
241 | // satisfied. | |
242 | // | |
243 | // For example, given these two impl headers: | |
244 | // | |
245 | // `impl<'a> From<&'a str> for Box<dyn Error>` | |
246 | // `impl<E> From<E> for Box<dyn Error> where E: Error` | |
247 | // | |
248 | // So we have: | |
249 | // | |
250 | // `Box<dyn Error>: From<&'?a str>` | |
251 | // `Box<dyn Error>: From<?E>` | |
252 | // | |
253 | // After equating the two headers: | |
254 | // | |
255 | // `Box<dyn Error> = Box<dyn Error>` | |
256 | // So, `?E = &'?a str` and then given the where clause `&'?a str: Error`. | |
257 | // | |
258 | // If the obligation `&'?a str: Error` holds, it means that there's overlap. If that doesn't | |
259 | // hold we need to check if `&'?a str: !Error` holds, if doesn't hold there's overlap because | |
260 | // at some point an impl for `&'?a str: Error` could be added. | |
5099ac24 FG |
261 | debug!( |
262 | "implicit_negative(impl1_header={:?}, impl2_header={:?}, obligations={:?})", | |
263 | impl1_header, impl2_header, obligations | |
264 | ); | |
c34b1796 | 265 | let infcx = selcx.infcx(); |
5099ac24 | 266 | let opt_failing_obligation = impl1_header |
dfeec247 XL |
267 | .predicates |
268 | .iter() | |
fc512014 | 269 | .copied() |
5099ac24 | 270 | .chain(impl2_header.predicates) |
dfeec247 XL |
271 | .map(|p| infcx.resolve_vars_if_possible(p)) |
272 | .map(|p| Obligation { | |
273 | cause: ObligationCause::dummy(), | |
274 | param_env, | |
275 | recursion_depth: 0, | |
276 | predicate: p, | |
277 | }) | |
278 | .chain(obligations) | |
5099ac24 | 279 | .find(|o| !selcx.predicate_may_hold_fatal(o)); |
c34b1796 AL |
280 | |
281 | if let Some(failing_obligation) = opt_failing_obligation { | |
62682a34 | 282 | debug!("overlap: obligation unsatisfiable {:?}", failing_obligation); |
5099ac24 FG |
283 | true |
284 | } else { | |
285 | false | |
c34b1796 | 286 | } |
5099ac24 | 287 | } |
c34b1796 | 288 | |
5099ac24 FG |
289 | /// Given impl1 and impl2 check if both impls are never satisfied by a common type (including |
290 | /// where-clauses) If so, return true, they are disjoint and false otherwise. | |
291 | fn negative_impl<'cx, 'tcx>( | |
292 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
293 | impl1_def_id: DefId, | |
294 | impl2_def_id: DefId, | |
295 | ) -> bool { | |
296 | debug!("negative_impl(impl1_def_id={:?}, impl2_def_id={:?})", impl1_def_id, impl2_def_id); | |
297 | let tcx = selcx.infcx().tcx; | |
298 | ||
5099ac24 FG |
299 | // Create an infcx, taking the predicates of impl1 as assumptions: |
300 | tcx.infer_ctxt().enter(|infcx| { | |
5e7ed085 FG |
301 | // create a parameter environment corresponding to a (placeholder) instantiation of impl1 |
302 | let impl_env = tcx.param_env(impl1_def_id); | |
303 | let subject1 = match traits::fully_normalize( | |
5099ac24 FG |
304 | &infcx, |
305 | FulfillmentContext::new(), | |
306 | ObligationCause::dummy(), | |
5e7ed085 FG |
307 | impl_env, |
308 | tcx.impl_subject(impl1_def_id), | |
5099ac24 | 309 | ) { |
5e7ed085 FG |
310 | Ok(s) => s, |
311 | Err(err) => bug!("failed to fully normalize {:?}: {:?}", impl1_def_id, err), | |
5099ac24 FG |
312 | }; |
313 | ||
314 | // Attempt to prove that impl2 applies, given all of the above. | |
315 | let selcx = &mut SelectionContext::new(&infcx); | |
316 | let impl2_substs = infcx.fresh_substs_for_item(DUMMY_SP, impl2_def_id); | |
5e7ed085 FG |
317 | let (subject2, obligations) = |
318 | impl_subject_and_oblig(selcx, impl_env, impl2_def_id, impl2_substs); | |
5099ac24 | 319 | |
064997fb | 320 | !equate(&infcx, impl_env, subject1, subject2, obligations) |
5e7ed085 FG |
321 | }) |
322 | } | |
5099ac24 | 323 | |
5e7ed085 FG |
324 | fn equate<'cx, 'tcx>( |
325 | infcx: &InferCtxt<'cx, 'tcx>, | |
326 | impl_env: ty::ParamEnv<'tcx>, | |
5e7ed085 FG |
327 | subject1: ImplSubject<'tcx>, |
328 | subject2: ImplSubject<'tcx>, | |
329 | obligations: impl Iterator<Item = PredicateObligation<'tcx>>, | |
330 | ) -> bool { | |
331 | // do the impls unify? If not, not disjoint. | |
332 | let Ok(InferOk { obligations: more_obligations, .. }) = | |
333 | infcx.at(&ObligationCause::dummy(), impl_env).eq(subject1, subject2) | |
334 | else { | |
335 | debug!("explicit_disjoint: {:?} does not unify with {:?}", subject1, subject2); | |
336 | return true; | |
337 | }; | |
5099ac24 | 338 | |
5e7ed085 FG |
339 | let selcx = &mut SelectionContext::new(&infcx); |
340 | let opt_failing_obligation = obligations | |
341 | .into_iter() | |
342 | .chain(more_obligations) | |
064997fb | 343 | .find(|o| negative_impl_exists(selcx, impl_env, o)); |
5e7ed085 FG |
344 | |
345 | if let Some(failing_obligation) = opt_failing_obligation { | |
346 | debug!("overlap: obligation unsatisfiable {:?}", failing_obligation); | |
347 | false | |
348 | } else { | |
349 | true | |
350 | } | |
5099ac24 | 351 | } |
f035d41b | 352 | |
5e7ed085 FG |
353 | /// Try to prove that a negative impl exist for the given obligation and its super predicates. |
354 | #[instrument(level = "debug", skip(selcx))] | |
5099ac24 FG |
355 | fn negative_impl_exists<'cx, 'tcx>( |
356 | selcx: &SelectionContext<'cx, 'tcx>, | |
357 | param_env: ty::ParamEnv<'tcx>, | |
5099ac24 FG |
358 | o: &PredicateObligation<'tcx>, |
359 | ) -> bool { | |
360 | let infcx = &selcx.infcx().fork(); | |
5e7ed085 | 361 | |
064997fb | 362 | if resolve_negative_obligation(infcx, param_env, o) { |
5e7ed085 FG |
363 | return true; |
364 | } | |
365 | ||
366 | // Try to prove a negative obligation exists for super predicates | |
367 | for o in util::elaborate_predicates(infcx.tcx, iter::once(o.predicate)) { | |
064997fb | 368 | if resolve_negative_obligation(infcx, param_env, &o) { |
5e7ed085 FG |
369 | return true; |
370 | } | |
371 | } | |
372 | ||
373 | false | |
374 | } | |
375 | ||
376 | #[instrument(level = "debug", skip(infcx))] | |
377 | fn resolve_negative_obligation<'cx, 'tcx>( | |
378 | infcx: &InferCtxt<'cx, 'tcx>, | |
379 | param_env: ty::ParamEnv<'tcx>, | |
5e7ed085 FG |
380 | o: &PredicateObligation<'tcx>, |
381 | ) -> bool { | |
5099ac24 | 382 | let tcx = infcx.tcx; |
0731742a | 383 | |
5e7ed085 FG |
384 | let Some(o) = o.flip_polarity(tcx) else { |
385 | return false; | |
386 | }; | |
0731742a | 387 | |
064997fb | 388 | let mut fulfillment_cx = <dyn TraitEngine<'tcx>>::new(infcx.tcx); |
5e7ed085 FG |
389 | fulfillment_cx.register_predicate_obligation(infcx, o); |
390 | ||
391 | let errors = fulfillment_cx.select_all_or_error(infcx); | |
392 | ||
393 | if !errors.is_empty() { | |
394 | return false; | |
395 | } | |
396 | ||
064997fb FG |
397 | // FIXME -- also add "assumed to be well formed" types into the `outlives_env` |
398 | let outlives_env = OutlivesEnvironment::new(param_env); | |
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>, | |
407 | ) -> Option<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. | |
74b04a01 | 412 | return Some(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. | |
421 | return None; | |
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"); | |
ba9703b0 | 434 | None |
ff7c6d11 XL |
435 | } else { |
436 | debug!("trait_ref_is_knowable: nonlocal, nonfundamental, unowned"); | |
ba9703b0 | 437 | Some(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 | |
064997fb FG |
743 | // FIXME: Constants should participate in orphan checking. |
744 | fn visit_const(&mut self, _c: ty::Const<'tcx>) -> ControlFlow<Self::BreakTy> { | |
745 | ControlFlow::CONTINUE | |
1a4d82fc JJ |
746 | } |
747 | } |