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