]>
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 | ||
11 | /*! | |
12 | ||
13 | typeck.rs, an introduction | |
14 | ||
15 | The type checker is responsible for: | |
16 | ||
17 | 1. Determining the type of each expression | |
18 | 2. Resolving methods and traits | |
19 | 3. Guaranteeing that most type rules are met ("most?", you say, "why most?" | |
20 | Well, dear reader, read on) | |
21 | ||
22 | The main entry point is `check_crate()`. Type checking operates in | |
23 | several major phases: | |
24 | ||
25 | 1. The collect phase first passes over all items and determines their | |
26 | type, without examining their "innards". | |
27 | ||
28 | 2. Variance inference then runs to compute the variance of each parameter | |
29 | ||
30 | 3. Coherence checks for overlapping or orphaned impls | |
31 | ||
32 | 4. Finally, the check phase then checks function bodies and so forth. | |
33 | Within the check phase, we check each function body one at a time | |
34 | (bodies of function expressions are checked as part of the | |
35 | containing function). Inference is used to supply types wherever | |
36 | they are unknown. The actual checking of a function itself has | |
37 | several phases (check, regionck, writeback), as discussed in the | |
38 | documentation for the `check` module. | |
39 | ||
40 | The type checker is defined into various submodules which are documented | |
41 | independently: | |
42 | ||
43 | - astconv: converts the AST representation of types | |
44 | into the `ty` representation | |
45 | ||
46 | - collect: computes the types of each top-level item and enters them into | |
476ff2be | 47 | the `tcx.types` table for later use |
1a4d82fc JJ |
48 | |
49 | - coherence: enforces coherence rules, builds some tables | |
50 | ||
51 | - variance: variance inference | |
52 | ||
abe05a73 XL |
53 | - outlives: outlives inference |
54 | ||
1a4d82fc JJ |
55 | - check: walks over function bodies and type checks them, inferring types for |
56 | local variables, type parameters, etc as necessary. | |
57 | ||
58 | - infer: finds the types to use for each type variable such that | |
59 | all subtyping and assignment constraints are met. In essence, the check | |
60 | module specifies the constraints, and the infer module solves them. | |
61 | ||
62 | # Note | |
63 | ||
64 | This API is completely unstable and subject to change. | |
65 | ||
66 | */ | |
9cc50fc6 | 67 | |
e9174d1e | 68 | #![doc(html_logo_url = "https://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png", |
62682a34 | 69 | html_favicon_url = "https://doc.rust-lang.org/favicon.ico", |
e9174d1e | 70 | html_root_url = "https://doc.rust-lang.org/nightly/")] |
1a4d82fc | 71 | |
85aaf69f SL |
72 | #![allow(non_camel_case_types)] |
73 | ||
74 | #![feature(box_patterns)] | |
1a4d82fc | 75 | #![feature(box_syntax)] |
2c00a5a8 | 76 | #![feature(crate_visibility_modifier)] |
ff7c6d11 | 77 | #![feature(from_ref)] |
0531ce1d | 78 | #![feature(exhaustive_patterns)] |
8faf50e0 | 79 | #![feature(iterator_find_map)] |
85aaf69f | 80 | #![feature(quote)] |
ff7c6d11 | 81 | #![feature(refcell_replace_swap)] |
1a4d82fc | 82 | #![feature(rustc_diagnostic_macros)] |
7cac9316 | 83 | #![feature(slice_patterns)] |
83c7162d | 84 | #![feature(slice_sort_by_cached_key)] |
0531ce1d | 85 | #![feature(never_type)] |
7cac9316 | 86 | |
94b46f34 XL |
87 | #![recursion_limit="256"] |
88 | ||
1a4d82fc JJ |
89 | #[macro_use] extern crate log; |
90 | #[macro_use] extern crate syntax; | |
3157f602 | 91 | extern crate syntax_pos; |
1a4d82fc JJ |
92 | |
93 | extern crate arena; | |
54a0048b | 94 | #[macro_use] extern crate rustc; |
e9174d1e | 95 | extern crate rustc_platform_intrinsics as intrinsics; |
476ff2be | 96 | extern crate rustc_data_structures; |
3157f602 | 97 | extern crate rustc_errors as errors; |
83c7162d | 98 | extern crate rustc_target; |
1a4d82fc | 99 | |
3b2f2976 XL |
100 | use rustc::hir; |
101 | use rustc::lint; | |
102 | use rustc::middle; | |
103 | use rustc::session; | |
104 | use rustc::util; | |
1a4d82fc | 105 | |
54a0048b | 106 | use hir::map as hir_map; |
476ff2be | 107 | use rustc::infer::InferOk; |
54a0048b | 108 | use rustc::ty::subst::Substs; |
476ff2be | 109 | use rustc::ty::{self, Ty, TyCtxt}; |
94b46f34 | 110 | use rustc::ty::query::Providers; |
8faf50e0 | 111 | use rustc::traits::{ObligationCause, ObligationCauseCode, TraitEngine, TraitEngineExt}; |
041b39d2 | 112 | use session::{CompileIncomplete, config}; |
1a4d82fc | 113 | use util::common::time; |
1a4d82fc | 114 | |
7453a54e | 115 | use syntax::ast; |
83c7162d | 116 | use rustc_target::spec::abi::Abi; |
3157f602 | 117 | use syntax_pos::Span; |
1a4d82fc | 118 | |
476ff2be | 119 | use std::iter; |
ff7c6d11 | 120 | |
85aaf69f SL |
121 | // NB: This module needs to be declared first so diagnostics are |
122 | // registered before they are used. | |
3b2f2976 | 123 | mod diagnostics; |
85aaf69f | 124 | |
2c00a5a8 | 125 | mod astconv; |
7cac9316 XL |
126 | mod check; |
127 | mod check_unused; | |
2c00a5a8 | 128 | mod coherence; |
7cac9316 | 129 | mod collect; |
85aaf69f | 130 | mod constrained_type_params; |
2c00a5a8 | 131 | mod structured_errors; |
476ff2be | 132 | mod impl_wf_check; |
2c00a5a8 | 133 | mod namespace; |
abe05a73 | 134 | mod outlives; |
7cac9316 | 135 | mod variance; |
1a4d82fc | 136 | |
c34b1796 | 137 | pub struct TypeAndSubsts<'tcx> { |
3b2f2976 XL |
138 | substs: &'tcx Substs<'tcx>, |
139 | ty: Ty<'tcx>, | |
1a4d82fc JJ |
140 | } |
141 | ||
a7813a04 | 142 | fn require_c_abi_if_variadic(tcx: TyCtxt, |
e9174d1e | 143 | decl: &hir::FnDecl, |
7453a54e | 144 | abi: Abi, |
c1a9b12d | 145 | span: Span) { |
7cac9316 | 146 | if decl.variadic && !(abi == Abi::C || abi == Abi::Cdecl) { |
5bcae85e | 147 | let mut err = struct_span_err!(tcx.sess, span, E0045, |
7cac9316 XL |
148 | "variadic function must have C or cdecl calling convention"); |
149 | err.span_label(span, "variadics require C or cdecl calling convention").emit(); | |
c1a9b12d SL |
150 | } |
151 | } | |
152 | ||
8bb4bdeb | 153 | fn require_same_types<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
476ff2be | 154 | cause: &ObligationCause<'tcx>, |
c30ab7b3 SL |
155 | expected: Ty<'tcx>, |
156 | actual: Ty<'tcx>) | |
a7813a04 | 157 | -> bool { |
041b39d2 | 158 | tcx.infer_ctxt().enter(|ref infcx| { |
0531ce1d XL |
159 | let param_env = ty::ParamEnv::empty(); |
160 | let mut fulfill_cx = TraitEngine::new(infcx.tcx); | |
7cac9316 | 161 | match infcx.at(&cause, param_env).eq(expected, actual) { |
c30ab7b3 | 162 | Ok(InferOk { obligations, .. }) => { |
cc61c64b | 163 | fulfill_cx.register_predicate_obligations(infcx, obligations); |
c30ab7b3 SL |
164 | } |
165 | Err(err) => { | |
32a655c1 | 166 | infcx.report_mismatched_types(cause, expected, actual, err).emit(); |
cc61c64b XL |
167 | return false; |
168 | } | |
169 | } | |
170 | ||
171 | match fulfill_cx.select_all_or_error(infcx) { | |
172 | Ok(()) => true, | |
173 | Err(errors) => { | |
0531ce1d | 174 | infcx.report_fulfillment_errors(&errors, None, false); |
c30ab7b3 SL |
175 | false |
176 | } | |
1a4d82fc | 177 | } |
a7813a04 | 178 | }) |
1a4d82fc JJ |
179 | } |
180 | ||
8bb4bdeb XL |
181 | fn check_main_fn_ty<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
182 | main_id: ast::NodeId, | |
183 | main_span: Span) { | |
32a655c1 | 184 | let main_def_id = tcx.hir.local_def_id(main_id); |
7cac9316 | 185 | let main_t = tcx.type_of(main_def_id); |
1a4d82fc | 186 | match main_t.sty { |
54a0048b | 187 | ty::TyFnDef(..) => { |
32a655c1 | 188 | match tcx.hir.find(main_id) { |
e9174d1e | 189 | Some(hir_map::NodeItem(it)) => { |
1a4d82fc | 190 | match it.node { |
8faf50e0 | 191 | hir::ItemKind::Fn(.., ref generics, _) => { |
94b46f34 | 192 | let mut error = false; |
ff7c6d11 | 193 | if !generics.params.is_empty() { |
8faf50e0 XL |
194 | let msg = "`main` function is not allowed to have generic \ |
195 | parameters".to_string(); | |
196 | let label = "`main` cannot have generic parameters".to_string(); | |
94b46f34 XL |
197 | struct_span_err!(tcx.sess, generics.span, E0131, "{}", msg) |
198 | .span_label(generics.span, label) | |
199 | .emit(); | |
200 | error = true; | |
201 | } | |
202 | if let Some(sp) = generics.where_clause.span() { | |
203 | struct_span_err!(tcx.sess, sp, E0646, | |
204 | "`main` function is not allowed to have a `where` clause") | |
205 | .span_label(sp, "`main` cannot have a `where` clause") | |
5bcae85e | 206 | .emit(); |
94b46f34 XL |
207 | error = true; |
208 | } | |
209 | if error { | |
5bcae85e SL |
210 | return; |
211 | } | |
1a4d82fc JJ |
212 | } |
213 | _ => () | |
214 | } | |
215 | } | |
216 | _ => () | |
217 | } | |
ff7c6d11 XL |
218 | |
219 | let actual = tcx.fn_sig(main_def_id); | |
0531ce1d | 220 | let expected_return_type = if tcx.lang_items().termination().is_some() { |
ff7c6d11 XL |
221 | // we take the return type of the given main function, the real check is done |
222 | // in `check_fn` | |
223 | actual.output().skip_binder() | |
224 | } else { | |
225 | // standard () main return type | |
226 | tcx.mk_nil() | |
227 | }; | |
228 | ||
83c7162d | 229 | let se_ty = tcx.mk_fn_ptr(ty::Binder::bind( |
041b39d2 | 230 | tcx.mk_fn_sig( |
8bb4bdeb | 231 | iter::empty(), |
ff7c6d11 | 232 | expected_return_type, |
8bb4bdeb XL |
233 | false, |
234 | hir::Unsafety::Normal, | |
235 | Abi::Rust | |
041b39d2 XL |
236 | ) |
237 | )); | |
1a4d82fc | 238 | |
5bcae85e | 239 | require_same_types( |
8bb4bdeb | 240 | tcx, |
476ff2be | 241 | &ObligationCause::new(main_span, main_id, ObligationCauseCode::MainFunctionType), |
c30ab7b3 | 242 | se_ty, |
ff7c6d11 | 243 | tcx.mk_fn_ptr(actual)); |
1a4d82fc JJ |
244 | } |
245 | _ => { | |
54a0048b SL |
246 | span_bug!(main_span, |
247 | "main has a non-function type: found `{}`", | |
248 | main_t); | |
1a4d82fc JJ |
249 | } |
250 | } | |
251 | } | |
252 | ||
8bb4bdeb XL |
253 | fn check_start_fn_ty<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
254 | start_id: ast::NodeId, | |
255 | start_span: Span) { | |
256 | let start_def_id = tcx.hir.local_def_id(start_id); | |
7cac9316 | 257 | let start_t = tcx.type_of(start_def_id); |
1a4d82fc | 258 | match start_t.sty { |
54a0048b | 259 | ty::TyFnDef(..) => { |
32a655c1 | 260 | match tcx.hir.find(start_id) { |
e9174d1e | 261 | Some(hir_map::NodeItem(it)) => { |
1a4d82fc | 262 | match it.node { |
8faf50e0 | 263 | hir::ItemKind::Fn(.., ref generics, _) => { |
94b46f34 XL |
264 | let mut error = false; |
265 | if !generics.params.is_empty() { | |
266 | struct_span_err!(tcx.sess, generics.span, E0132, | |
267 | "start function is not allowed to have type parameters") | |
268 | .span_label(generics.span, | |
269 | "start function cannot have type parameters") | |
270 | .emit(); | |
271 | error = true; | |
272 | } | |
273 | if let Some(sp) = generics.where_clause.span() { | |
274 | struct_span_err!(tcx.sess, sp, E0647, | |
275 | "start function is not allowed to have a `where` clause") | |
276 | .span_label(sp, "start function cannot have a `where` clause") | |
277 | .emit(); | |
278 | error = true; | |
279 | } | |
280 | if error { | |
281 | return; | |
282 | } | |
1a4d82fc JJ |
283 | } |
284 | _ => () | |
285 | } | |
286 | } | |
287 | _ => () | |
288 | } | |
289 | ||
83c7162d | 290 | let se_ty = tcx.mk_fn_ptr(ty::Binder::bind( |
041b39d2 | 291 | tcx.mk_fn_sig( |
476ff2be | 292 | [ |
c34b1796 | 293 | tcx.types.isize, |
c1a9b12d | 294 | tcx.mk_imm_ptr(tcx.mk_imm_ptr(tcx.types.u8)) |
476ff2be SL |
295 | ].iter().cloned(), |
296 | tcx.types.isize, | |
297 | false, | |
8bb4bdeb XL |
298 | hir::Unsafety::Normal, |
299 | Abi::Rust | |
041b39d2 XL |
300 | ) |
301 | )); | |
1a4d82fc | 302 | |
5bcae85e | 303 | require_same_types( |
8bb4bdeb | 304 | tcx, |
476ff2be | 305 | &ObligationCause::new(start_span, start_id, ObligationCauseCode::StartFunctionType), |
c30ab7b3 | 306 | se_ty, |
041b39d2 | 307 | tcx.mk_fn_ptr(tcx.fn_sig(start_def_id))); |
1a4d82fc JJ |
308 | } |
309 | _ => { | |
54a0048b SL |
310 | span_bug!(start_span, |
311 | "start has a non-function type: found `{}`", | |
312 | start_t); | |
1a4d82fc JJ |
313 | } |
314 | } | |
315 | } | |
316 | ||
8bb4bdeb | 317 | fn check_for_entry_fn<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) { |
83c7162d XL |
318 | if let Some((id, sp, entry_type)) = *tcx.sess.entry_fn.borrow() { |
319 | match entry_type { | |
320 | config::EntryMain => check_main_fn_ty(tcx, id, sp), | |
321 | config::EntryStart => check_start_fn_ty(tcx, id, sp), | |
3157f602 | 322 | } |
1a4d82fc JJ |
323 | } |
324 | } | |
325 | ||
8bb4bdeb XL |
326 | pub fn provide(providers: &mut Providers) { |
327 | collect::provide(providers); | |
328 | coherence::provide(providers); | |
329 | check::provide(providers); | |
7cac9316 | 330 | variance::provide(providers); |
abe05a73 | 331 | outlives::provide(providers); |
8bb4bdeb XL |
332 | } |
333 | ||
5bcae85e | 334 | pub fn check_crate<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) |
041b39d2 XL |
335 | -> Result<(), CompileIncomplete> |
336 | { | |
1a4d82fc JJ |
337 | // this ensures that later parts of type checking can assume that items |
338 | // have valid types and not error | |
54a0048b | 339 | tcx.sess.track_errors(|| { |
0531ce1d | 340 | time(tcx.sess, "type collecting", || |
8bb4bdeb | 341 | collect::collect_item_types(tcx)); |
9cc50fc6 | 342 | |
54a0048b | 343 | })?; |
1a4d82fc | 344 | |
abe05a73 | 345 | tcx.sess.track_errors(|| { |
0531ce1d | 346 | time(tcx.sess, "outlives testing", || |
abe05a73 XL |
347 | outlives::test::test_inferred_outlives(tcx)); |
348 | })?; | |
349 | ||
476ff2be | 350 | tcx.sess.track_errors(|| { |
0531ce1d | 351 | time(tcx.sess, "impl wf inference", || |
8bb4bdeb | 352 | impl_wf_check::impl_wf_check(tcx)); |
476ff2be SL |
353 | })?; |
354 | ||
54a0048b | 355 | tcx.sess.track_errors(|| { |
0531ce1d | 356 | time(tcx.sess, "coherence checking", || |
8bb4bdeb | 357 | coherence::check_coherence(tcx)); |
54a0048b | 358 | })?; |
1a4d82fc | 359 | |
7cac9316 | 360 | tcx.sess.track_errors(|| { |
0531ce1d | 361 | time(tcx.sess, "variance testing", || |
7cac9316 XL |
362 | variance::test::test_variance(tcx)); |
363 | })?; | |
364 | ||
0531ce1d | 365 | time(tcx.sess, "wf checking", || check::check_wf_new(tcx))?; |
1a4d82fc | 366 | |
0531ce1d | 367 | time(tcx.sess, "item-types checking", || check::check_item_types(tcx))?; |
e9174d1e | 368 | |
0531ce1d | 369 | time(tcx.sess, "item-bodies checking", || check::check_item_bodies(tcx))?; |
e9174d1e | 370 | |
a7813a04 | 371 | check_unused::check_crate(tcx); |
8bb4bdeb | 372 | check_for_entry_fn(tcx); |
7453a54e | 373 | |
041b39d2 | 374 | tcx.sess.compile_status() |
1a4d82fc | 375 | } |
d9579d0f | 376 | |
7cac9316 XL |
377 | /// A quasi-deprecated helper used in rustdoc and save-analysis to get |
378 | /// the type from a HIR node. | |
379 | pub fn hir_ty_to_ty<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, hir_ty: &hir::Ty) -> Ty<'tcx> { | |
380 | // In case there are any projections etc, find the "environment" | |
381 | // def-id that will be used to determine the traits/predicates in | |
382 | // scope. This is derived from the enclosing item-like thing. | |
383 | let env_node_id = tcx.hir.get_parent(hir_ty.id); | |
384 | let env_def_id = tcx.hir.local_def_id(env_node_id); | |
385 | let item_cx = self::collect::ItemCtxt::new(tcx, env_def_id); | |
ff7c6d11 XL |
386 | astconv::AstConv::ast_ty_to_ty(&item_cx, hir_ty) |
387 | } | |
388 | ||
389 | pub fn hir_trait_to_predicates<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, hir_trait: &hir::TraitRef) | |
390 | -> (ty::PolyTraitRef<'tcx>, Vec<ty::PolyProjectionPredicate<'tcx>>) { | |
391 | // In case there are any projections etc, find the "environment" | |
392 | // def-id that will be used to determine the traits/predicates in | |
393 | // scope. This is derived from the enclosing item-like thing. | |
394 | let env_node_id = tcx.hir.get_parent(hir_trait.ref_id); | |
395 | let env_def_id = tcx.hir.local_def_id(env_node_id); | |
396 | let item_cx = self::collect::ItemCtxt::new(tcx, env_def_id); | |
397 | let mut projections = Vec::new(); | |
398 | let principal = astconv::AstConv::instantiate_poly_trait_ref_inner( | |
399 | &item_cx, hir_trait, tcx.types.err, &mut projections, true | |
400 | ); | |
401 | (principal, projections) | |
7cac9316 XL |
402 | } |
403 | ||
d9579d0f | 404 | __build_diagnostic_array! { librustc_typeck, DIAGNOSTICS } |