]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | // Copyright 2014 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
c34b1796 | 11 | //! See `README.md` for high-level documentation |
1a4d82fc | 12 | |
54a0048b | 13 | use super::{SelectionContext, Obligation, ObligationCause}; |
1a4d82fc | 14 | |
9e0c209e | 15 | use hir::def_id::{DefId, LOCAL_CRATE}; |
54a0048b | 16 | use ty::{self, Ty, TyCtxt}; |
476ff2be SL |
17 | |
18 | use infer::{InferCtxt, InferOk}; | |
1a4d82fc | 19 | |
c34b1796 | 20 | #[derive(Copy, Clone)] |
9346a6ac | 21 | struct InferIsLocal(bool); |
c34b1796 | 22 | |
54a0048b SL |
23 | /// If there are types that satisfy both impls, returns a suitably-freshened |
24 | /// `ImplHeader` with those types substituted | |
a7813a04 XL |
25 | pub fn overlapping_impls<'cx, 'gcx, 'tcx>(infcx: &InferCtxt<'cx, 'gcx, 'tcx>, |
26 | impl1_def_id: DefId, | |
27 | impl2_def_id: DefId) | |
28 | -> Option<ty::ImplHeader<'tcx>> | |
1a4d82fc JJ |
29 | { |
30 | debug!("impl_can_satisfy(\ | |
62682a34 SL |
31 | impl1_def_id={:?}, \ |
32 | impl2_def_id={:?})", | |
33 | impl1_def_id, | |
34 | impl2_def_id); | |
1a4d82fc | 35 | |
c1a9b12d | 36 | let selcx = &mut SelectionContext::intercrate(infcx); |
9cc50fc6 | 37 | overlap(selcx, impl1_def_id, impl2_def_id) |
85aaf69f SL |
38 | } |
39 | ||
9cc50fc6 | 40 | /// Can both impl `a` and impl `b` be satisfied by a common type (including |
54a0048b | 41 | /// `where` clauses)? If so, returns an `ImplHeader` that unifies the two impls. |
a7813a04 XL |
42 | fn overlap<'cx, 'gcx, 'tcx>(selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>, |
43 | a_def_id: DefId, | |
44 | b_def_id: DefId) | |
45 | -> Option<ty::ImplHeader<'tcx>> | |
85aaf69f | 46 | { |
62682a34 SL |
47 | debug!("overlap(a_def_id={:?}, b_def_id={:?})", |
48 | a_def_id, | |
49 | b_def_id); | |
c34b1796 | 50 | |
54a0048b SL |
51 | let a_impl_header = ty::ImplHeader::with_fresh_ty_vars(selcx, a_def_id); |
52 | let b_impl_header = ty::ImplHeader::with_fresh_ty_vars(selcx, b_def_id); | |
c34b1796 | 53 | |
54a0048b SL |
54 | debug!("overlap: a_impl_header={:?}", a_impl_header); |
55 | debug!("overlap: b_impl_header={:?}", b_impl_header); | |
85aaf69f | 56 | |
92a42be0 | 57 | // Do `a` and `b` unify? If not, no overlap. |
476ff2be SL |
58 | match selcx.infcx().eq_impl_headers(true, |
59 | &ObligationCause::dummy(), | |
60 | &a_impl_header, | |
61 | &b_impl_header) { | |
c30ab7b3 SL |
62 | Ok(InferOk { obligations, .. }) => { |
63 | // FIXME(#32730) propagate obligations | |
64 | assert!(obligations.is_empty()); | |
65 | } | |
66 | Err(_) => return None | |
85aaf69f SL |
67 | } |
68 | ||
92a42be0 | 69 | debug!("overlap: unification check succeeded"); |
c34b1796 | 70 | |
85aaf69f | 71 | // Are any of the obligations unsatisfiable? If so, no overlap. |
c34b1796 AL |
72 | let infcx = selcx.infcx(); |
73 | let opt_failing_obligation = | |
54a0048b SL |
74 | a_impl_header.predicates |
75 | .iter() | |
76 | .chain(&b_impl_header.predicates) | |
77 | .map(|p| infcx.resolve_type_vars_if_possible(p)) | |
78 | .map(|p| Obligation { cause: ObligationCause::dummy(), | |
79 | recursion_depth: 0, | |
80 | predicate: p }) | |
c34b1796 AL |
81 | .find(|o| !selcx.evaluate_obligation(o)); |
82 | ||
83 | if let Some(failing_obligation) = opt_failing_obligation { | |
62682a34 | 84 | debug!("overlap: obligation unsatisfiable {:?}", failing_obligation); |
9cc50fc6 | 85 | return None |
c34b1796 AL |
86 | } |
87 | ||
54a0048b | 88 | Some(selcx.infcx().resolve_type_vars_if_possible(&a_impl_header)) |
c34b1796 AL |
89 | } |
90 | ||
a7813a04 XL |
91 | pub fn trait_ref_is_knowable<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>, |
92 | trait_ref: &ty::TraitRef<'tcx>) -> bool | |
c34b1796 | 93 | { |
62682a34 | 94 | debug!("trait_ref_is_knowable(trait_ref={:?})", trait_ref); |
c34b1796 AL |
95 | |
96 | // if the orphan rules pass, that means that no ancestor crate can | |
97 | // impl this, so it's up to us. | |
9346a6ac | 98 | if orphan_check_trait_ref(tcx, trait_ref, InferIsLocal(false)).is_ok() { |
c34b1796 AL |
99 | debug!("trait_ref_is_knowable: orphan check passed"); |
100 | return true; | |
101 | } | |
102 | ||
103 | // if the trait is not marked fundamental, then it's always possible that | |
104 | // an ancestor crate will impl this in the future, if they haven't | |
105 | // already | |
106 | if | |
e9174d1e | 107 | trait_ref.def_id.krate != LOCAL_CRATE && |
c1a9b12d | 108 | !tcx.has_attr(trait_ref.def_id, "fundamental") |
c34b1796 AL |
109 | { |
110 | debug!("trait_ref_is_knowable: trait is neither local nor fundamental"); | |
111 | return false; | |
112 | } | |
113 | ||
114 | // find out when some downstream (or cousin) crate could impl this | |
115 | // trait-ref, presuming that all the parameters were instantiated | |
116 | // with downstream types. If not, then it could only be | |
117 | // implemented by an upstream crate, which means that the impl | |
118 | // must be visible to us, and -- since the trait is fundamental | |
119 | // -- we can test. | |
9346a6ac | 120 | orphan_check_trait_ref(tcx, trait_ref, InferIsLocal(true)).is_err() |
85aaf69f SL |
121 | } |
122 | ||
1a4d82fc JJ |
123 | pub enum OrphanCheckErr<'tcx> { |
124 | NoLocalInputType, | |
125 | UncoveredTy(Ty<'tcx>), | |
126 | } | |
127 | ||
128 | /// Checks the coherence orphan rules. `impl_def_id` should be the | |
129 | /// def-id of a trait impl. To pass, either the trait must be local, or else | |
130 | /// two conditions must be satisfied: | |
131 | /// | |
132 | /// 1. All type parameters in `Self` must be "covered" by some local type constructor. | |
133 | /// 2. Some local type must appear in `Self`. | |
a7813a04 XL |
134 | pub fn orphan_check<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>, |
135 | impl_def_id: DefId) | |
136 | -> Result<(), OrphanCheckErr<'tcx>> | |
1a4d82fc | 137 | { |
62682a34 | 138 | debug!("orphan_check({:?})", impl_def_id); |
1a4d82fc JJ |
139 | |
140 | // We only except this routine to be invoked on implementations | |
141 | // of a trait, not inherent implementations. | |
c1a9b12d | 142 | let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap(); |
62682a34 | 143 | debug!("orphan_check: trait_ref={:?}", trait_ref); |
1a4d82fc JJ |
144 | |
145 | // If the *trait* is local to the crate, ok. | |
e9174d1e | 146 | if trait_ref.def_id.is_local() { |
62682a34 SL |
147 | debug!("trait {:?} is local to current crate", |
148 | trait_ref.def_id); | |
1a4d82fc JJ |
149 | return Ok(()); |
150 | } | |
151 | ||
9346a6ac | 152 | orphan_check_trait_ref(tcx, &trait_ref, InferIsLocal(false)) |
c34b1796 AL |
153 | } |
154 | ||
a7813a04 | 155 | fn orphan_check_trait_ref<'tcx>(tcx: TyCtxt, |
c34b1796 | 156 | trait_ref: &ty::TraitRef<'tcx>, |
9346a6ac | 157 | infer_is_local: InferIsLocal) |
c34b1796 AL |
158 | -> Result<(), OrphanCheckErr<'tcx>> |
159 | { | |
62682a34 SL |
160 | debug!("orphan_check_trait_ref(trait_ref={:?}, infer_is_local={})", |
161 | trait_ref, infer_is_local.0); | |
c34b1796 | 162 | |
85aaf69f SL |
163 | // First, create an ordered iterator over all the type parameters to the trait, with the self |
164 | // type appearing first. | |
85aaf69f SL |
165 | // Find the first input type that either references a type parameter OR |
166 | // some local type. | |
9e0c209e | 167 | for input_ty in trait_ref.input_types() { |
9346a6ac | 168 | if ty_is_local(tcx, input_ty, infer_is_local) { |
62682a34 | 169 | debug!("orphan_check_trait_ref: ty_is_local `{:?}`", input_ty); |
c34b1796 AL |
170 | |
171 | // First local input type. Check that there are no | |
172 | // uncovered type parameters. | |
9346a6ac | 173 | let uncovered_tys = uncovered_tys(tcx, input_ty, infer_is_local); |
c34b1796 AL |
174 | for uncovered_ty in uncovered_tys { |
175 | if let Some(param) = uncovered_ty.walk().find(|t| is_type_parameter(t)) { | |
62682a34 | 176 | debug!("orphan_check_trait_ref: uncovered type `{:?}`", param); |
c34b1796 AL |
177 | return Err(OrphanCheckErr::UncoveredTy(param)); |
178 | } | |
85aaf69f | 179 | } |
c34b1796 AL |
180 | |
181 | // OK, found local type, all prior types upheld invariant. | |
182 | return Ok(()); | |
85aaf69f | 183 | } |
c34b1796 AL |
184 | |
185 | // Otherwise, enforce invariant that there are no type | |
186 | // parameters reachable. | |
9346a6ac | 187 | if !infer_is_local.0 { |
c34b1796 | 188 | if let Some(param) = input_ty.walk().find(|t| is_type_parameter(t)) { |
62682a34 | 189 | debug!("orphan_check_trait_ref: uncovered type `{:?}`", param); |
c34b1796 AL |
190 | return Err(OrphanCheckErr::UncoveredTy(param)); |
191 | } | |
85aaf69f | 192 | } |
1a4d82fc JJ |
193 | } |
194 | ||
c34b1796 AL |
195 | // If we exit above loop, never found a local type. |
196 | debug!("orphan_check_trait_ref: no local type"); | |
197 | return Err(OrphanCheckErr::NoLocalInputType); | |
1a4d82fc JJ |
198 | } |
199 | ||
a7813a04 XL |
200 | fn uncovered_tys<'tcx>(tcx: TyCtxt, ty: Ty<'tcx>, infer_is_local: InferIsLocal) |
201 | -> Vec<Ty<'tcx>> { | |
9346a6ac | 202 | if ty_is_local_constructor(tcx, ty, infer_is_local) { |
c34b1796 AL |
203 | vec![] |
204 | } else if fundamental_ty(tcx, ty) { | |
205 | ty.walk_shallow() | |
62682a34 | 206 | .flat_map(|t| uncovered_tys(tcx, t, infer_is_local)) |
c34b1796 AL |
207 | .collect() |
208 | } else { | |
209 | vec![ty] | |
210 | } | |
211 | } | |
212 | ||
a7813a04 | 213 | fn is_type_parameter(ty: Ty) -> bool { |
c34b1796 AL |
214 | match ty.sty { |
215 | // FIXME(#20590) straighten story about projection types | |
62682a34 | 216 | ty::TyProjection(..) | ty::TyParam(..) => true, |
c34b1796 AL |
217 | _ => false, |
218 | } | |
219 | } | |
220 | ||
a7813a04 | 221 | fn ty_is_local(tcx: TyCtxt, ty: Ty, infer_is_local: InferIsLocal) -> bool { |
9346a6ac AL |
222 | ty_is_local_constructor(tcx, ty, infer_is_local) || |
223 | fundamental_ty(tcx, ty) && ty.walk_shallow().any(|t| ty_is_local(tcx, t, infer_is_local)) | |
c34b1796 AL |
224 | } |
225 | ||
a7813a04 | 226 | fn fundamental_ty(tcx: TyCtxt, ty: Ty) -> bool { |
c34b1796 | 227 | match ty.sty { |
476ff2be SL |
228 | ty::TyBox(..) | ty::TyRef(..) => true, |
229 | ty::TyAdt(def, _) => def.is_fundamental(), | |
230 | ty::TyDynamic(ref data, ..) => { | |
231 | data.principal().map_or(false, |p| tcx.has_attr(p.def_id(), "fundamental")) | |
232 | } | |
233 | _ => false | |
c34b1796 AL |
234 | } |
235 | } | |
236 | ||
a7813a04 | 237 | fn ty_is_local_constructor(tcx: TyCtxt, ty: Ty, infer_is_local: InferIsLocal)-> bool { |
62682a34 | 238 | debug!("ty_is_local_constructor({:?})", ty); |
1a4d82fc JJ |
239 | |
240 | match ty.sty { | |
62682a34 SL |
241 | ty::TyBool | |
242 | ty::TyChar | | |
243 | ty::TyInt(..) | | |
244 | ty::TyUint(..) | | |
245 | ty::TyFloat(..) | | |
92a42be0 | 246 | ty::TyStr | |
54a0048b SL |
247 | ty::TyFnDef(..) | |
248 | ty::TyFnPtr(_) | | |
62682a34 SL |
249 | ty::TyArray(..) | |
250 | ty::TySlice(..) | | |
251 | ty::TyRawPtr(..) | | |
252 | ty::TyRef(..) | | |
5bcae85e | 253 | ty::TyNever | |
62682a34 SL |
254 | ty::TyTuple(..) | |
255 | ty::TyParam(..) | | |
256 | ty::TyProjection(..) => { | |
1a4d82fc JJ |
257 | false |
258 | } | |
259 | ||
62682a34 | 260 | ty::TyInfer(..) => { |
9346a6ac | 261 | infer_is_local.0 |
c34b1796 AL |
262 | } |
263 | ||
9e0c209e | 264 | ty::TyAdt(def, _) => { |
e9174d1e | 265 | def.did.is_local() |
1a4d82fc JJ |
266 | } |
267 | ||
62682a34 | 268 | ty::TyBox(_) => { // Box<T> |
1a4d82fc | 269 | let krate = tcx.lang_items.owned_box().map(|d| d.krate); |
e9174d1e | 270 | krate == Some(LOCAL_CRATE) |
1a4d82fc JJ |
271 | } |
272 | ||
476ff2be SL |
273 | ty::TyDynamic(ref tt, ..) => { |
274 | tt.principal().map_or(false, |p| p.def_id().is_local()) | |
1a4d82fc JJ |
275 | } |
276 | ||
62682a34 | 277 | ty::TyError => { |
9cc50fc6 SL |
278 | true |
279 | } | |
280 | ||
5bcae85e | 281 | ty::TyClosure(..) | ty::TyAnon(..) => { |
54a0048b | 282 | bug!("ty_is_local invoked on unexpected type: {:?}", ty) |
1a4d82fc JJ |
283 | } |
284 | } | |
285 | } |