1 // Copyright 2016 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.
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.
11 //! This pass type-checks the MIR to ensure it is not broken.
12 #![allow(unreachable_code)]
14 use rustc::infer::{self, InferCtxt, InferOk};
16 use rustc::ty::fold::TypeFoldable;
17 use rustc::ty::{self, Ty, TyCtxt, TypeVariants};
18 use rustc::middle::const_val::ConstVal;
20 use rustc::mir::tcx::LvalueTy;
21 use rustc::mir::transform::{MirPass, MirSource};
22 use rustc::mir::visit::Visitor;
25 use syntax_pos::{Span, DUMMY_SP};
27 use rustc_data_structures::fx::FxHashSet;
28 use rustc_data_structures::indexed_vec::Idx;
30 fn mirbug(tcx: TyCtxt, span: Span, msg: &str) {
31 tcx.sess.diagnostic().span_bug(span, msg);
34 macro_rules! span_mirbug {
35 ($context:expr, $elem:expr, $($message:tt)*) => ({
36 mirbug($context.tcx(), $context.last_span,
37 &format!("broken MIR ({:?}): {}", $elem, format!($($message)*)))
41 macro_rules! span_mirbug_and_err {
42 ($context:expr, $elem:expr, $($message:tt)*) => ({
44 span_mirbug!($context, $elem, $($message)*);
50 enum FieldAccessError {
51 OutOfRange { field_count: usize }
54 /// Verifies that MIR types are sane to not crash further checks.
56 /// The sanitize_XYZ methods here take an MIR object and compute its
57 /// type, calling `span_mirbug` and returning an error type if there
59 struct TypeVerifier<'a, 'b: 'a, 'gcx: 'b+'tcx, 'tcx: 'b> {
60 cx: &'a mut TypeChecker<'b, 'gcx, 'tcx>,
66 impl<'a, 'b, 'gcx, 'tcx> Visitor<'tcx> for TypeVerifier<'a, 'b, 'gcx, 'tcx> {
67 fn visit_span(&mut self, span: &Span) {
68 if *span != DUMMY_SP {
69 self.last_span = *span;
73 fn visit_lvalue(&mut self,
74 lvalue: &Lvalue<'tcx>,
75 _context: visit::LvalueContext,
77 self.sanitize_lvalue(lvalue, location);
80 fn visit_constant(&mut self, constant: &Constant<'tcx>, location: Location) {
81 self.super_constant(constant, location);
82 self.sanitize_type(constant, constant.ty);
85 fn visit_rvalue(&mut self, rvalue: &Rvalue<'tcx>, location: Location) {
86 self.super_rvalue(rvalue, location);
87 let rval_ty = rvalue.ty(self.mir, self.tcx());
88 self.sanitize_type(rvalue, rval_ty);
91 fn visit_local_decl(&mut self, local_decl: &LocalDecl<'tcx>) {
92 self.super_local_decl(local_decl);
93 self.sanitize_type(local_decl, local_decl.ty);
96 fn visit_mir(&mut self, mir: &Mir<'tcx>) {
97 self.sanitize_type(&"return type", mir.return_ty);
98 for local_decl in &mir.local_decls {
99 self.sanitize_type(local_decl, local_decl.ty);
101 if self.errors_reported {
108 impl<'a, 'b, 'gcx, 'tcx> TypeVerifier<'a, 'b, 'gcx, 'tcx> {
109 fn new(cx: &'a mut TypeChecker<'b, 'gcx, 'tcx>, mir: &'a Mir<'tcx>) -> Self {
114 errors_reported: false
118 fn tcx(&self) -> TyCtxt<'a, 'gcx, 'tcx> {
122 fn sanitize_type(&mut self, parent: &fmt::Debug, ty: Ty<'tcx>) -> Ty<'tcx> {
123 if ty.needs_infer() || ty.has_escaping_regions() || ty.references_error() {
124 span_mirbug_and_err!(self, parent, "bad type {:?}", ty)
130 fn sanitize_lvalue(&mut self, lvalue: &Lvalue<'tcx>, location: Location) -> LvalueTy<'tcx> {
131 debug!("sanitize_lvalue: {:?}", lvalue);
133 Lvalue::Local(index) => LvalueTy::Ty { ty: self.mir.local_decls[index].ty },
134 Lvalue::Static(box Static { def_id, ty: sty }) => {
135 let sty = self.sanitize_type(lvalue, sty);
136 let ty = self.tcx().type_of(def_id);
137 let ty = self.cx.normalize(&ty);
138 if let Err(terr) = self.cx.eq_types(self.last_span, ty, sty) {
140 self, lvalue, "bad static type ({:?}: {:?}): {:?}",
143 LvalueTy::Ty { ty: sty }
146 Lvalue::Projection(ref proj) => {
147 let base_ty = self.sanitize_lvalue(&proj.base, location);
148 if let LvalueTy::Ty { ty } = base_ty {
149 if ty.references_error() {
150 assert!(self.errors_reported);
151 return LvalueTy::Ty { ty: self.tcx().types.err };
154 self.sanitize_projection(base_ty, &proj.elem, lvalue, location)
159 fn sanitize_projection(&mut self,
160 base: LvalueTy<'tcx>,
161 pi: &LvalueElem<'tcx>,
162 lvalue: &Lvalue<'tcx>,
165 debug!("sanitize_projection: {:?} {:?} {:?}", base, pi, lvalue);
166 let tcx = self.tcx();
167 let base_ty = base.to_ty(tcx);
168 let span = self.last_span;
170 ProjectionElem::Deref => {
171 let deref_ty = base_ty.builtin_deref(true, ty::LvaluePreference::NoPreference);
173 ty: deref_ty.map(|t| t.ty).unwrap_or_else(|| {
174 span_mirbug_and_err!(
175 self, lvalue, "deref of non-pointer {:?}", base_ty)
179 ProjectionElem::Index(ref i) => {
180 self.visit_operand(i, location);
181 let index_ty = i.ty(self.mir, tcx);
182 if index_ty != tcx.types.usize {
184 ty: span_mirbug_and_err!(self, i, "index by non-usize {:?}", i)
188 ty: base_ty.builtin_index().unwrap_or_else(|| {
189 span_mirbug_and_err!(
190 self, lvalue, "index of non-array {:?}", base_ty)
195 ProjectionElem::ConstantIndex { .. } => {
196 // consider verifying in-bounds
198 ty: base_ty.builtin_index().unwrap_or_else(|| {
199 span_mirbug_and_err!(
200 self, lvalue, "index of non-array {:?}", base_ty)
204 ProjectionElem::Subslice { from, to } => {
206 ty: match base_ty.sty {
207 ty::TyArray(inner, size) => {
208 let min_size = (from as usize) + (to as usize);
209 if let Some(rest_size) = size.checked_sub(min_size) {
210 tcx.mk_array(inner, rest_size)
212 span_mirbug_and_err!(
213 self, lvalue, "taking too-small slice of {:?}", base_ty)
216 ty::TySlice(..) => base_ty,
218 span_mirbug_and_err!(
219 self, lvalue, "slice of non-array {:?}", base_ty)
224 ProjectionElem::Downcast(adt_def1, index) =>
226 ty::TyAdt(adt_def, substs) if adt_def.is_enum() && adt_def == adt_def1 => {
227 if index >= adt_def.variants.len() {
229 ty: span_mirbug_and_err!(
232 "cast to variant #{:?} but enum only has {:?}",
234 adt_def.variants.len())
245 ty: span_mirbug_and_err!(
246 self, lvalue, "can't downcast {:?} as {:?}",
250 ProjectionElem::Field(field, fty) => {
251 let fty = self.sanitize_type(lvalue, fty);
252 match self.field_ty(lvalue, base, field) {
254 if let Err(terr) = self.cx.eq_types(span, ty, fty) {
256 self, lvalue, "bad field access ({:?}: {:?}): {:?}",
260 Err(FieldAccessError::OutOfRange { field_count }) => {
262 self, lvalue, "accessed field #{} but variant only has {}",
263 field.index(), field_count)
266 LvalueTy::Ty { ty: fty }
271 fn error(&mut self) -> Ty<'tcx> {
272 self.errors_reported = true;
276 fn field_ty(&mut self,
278 base_ty: LvalueTy<'tcx>,
280 -> Result<Ty<'tcx>, FieldAccessError>
282 let tcx = self.tcx();
284 let (variant, substs) = match base_ty {
285 LvalueTy::Downcast { adt_def, substs, variant_index } => {
286 (&adt_def.variants[variant_index], substs)
288 LvalueTy::Ty { ty } => match ty.sty {
289 ty::TyAdt(adt_def, substs) if adt_def.is_univariant() => {
290 (&adt_def.variants[0], substs)
292 ty::TyClosure(def_id, substs) => {
293 return match substs.upvar_tys(def_id, tcx).nth(field.index()) {
295 None => Err(FieldAccessError::OutOfRange {
296 field_count: substs.upvar_tys(def_id, tcx).count()
300 ty::TyTuple(tys, _) => {
301 return match tys.get(field.index()) {
303 None => Err(FieldAccessError::OutOfRange {
304 field_count: tys.len()
308 _ => return Ok(span_mirbug_and_err!(
309 self, parent, "can't project out of {:?}", base_ty))
313 if let Some(field) = variant.fields.get(field.index()) {
314 Ok(self.cx.normalize(&field.ty(tcx, substs)))
316 Err(FieldAccessError::OutOfRange { field_count: variant.fields.len() })
321 pub struct TypeChecker<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
322 infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
323 param_env: ty::ParamEnv<'gcx>,
324 fulfillment_cx: traits::FulfillmentContext<'tcx>,
326 body_id: ast::NodeId,
327 reported_errors: FxHashSet<(Ty<'tcx>, Span)>,
330 impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> {
331 fn new(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
332 body_id: ast::NodeId,
333 param_env: ty::ParamEnv<'gcx>)
337 fulfillment_cx: traits::FulfillmentContext::new(),
341 reported_errors: FxHashSet(),
345 fn misc(&self, span: Span) -> traits::ObligationCause<'tcx> {
346 traits::ObligationCause::misc(span, self.body_id)
349 pub fn register_infer_ok_obligations<T>(&mut self, infer_ok: InferOk<'tcx, T>) -> T {
350 for obligation in infer_ok.obligations {
351 self.fulfillment_cx.register_predicate_obligation(self.infcx, obligation);
356 fn sub_types(&mut self, sub: Ty<'tcx>, sup: Ty<'tcx>)
357 -> infer::UnitResult<'tcx>
359 self.infcx.at(&self.misc(self.last_span), self.param_env)
361 .map(|ok| self.register_infer_ok_obligations(ok))
364 fn eq_types(&mut self, span: Span, a: Ty<'tcx>, b: Ty<'tcx>)
365 -> infer::UnitResult<'tcx>
367 self.infcx.at(&self.misc(span), self.param_env)
369 .map(|ok| self.register_infer_ok_obligations(ok))
372 fn tcx(&self) -> TyCtxt<'a, 'gcx, 'tcx> {
376 fn check_stmt(&mut self, mir: &Mir<'tcx>, stmt: &Statement<'tcx>) {
377 debug!("check_stmt: {:?}", stmt);
378 let tcx = self.tcx();
380 StatementKind::Assign(ref lv, ref rv) => {
381 let lv_ty = lv.ty(mir, tcx).to_ty(tcx);
382 let rv_ty = rv.ty(mir, tcx);
383 if let Err(terr) = self.sub_types(rv_ty, lv_ty) {
384 span_mirbug!(self, stmt, "bad assignment ({:?} = {:?}): {:?}",
388 StatementKind::SetDiscriminant{ ref lvalue, variant_index } => {
389 let lvalue_type = lvalue.ty(mir, tcx).to_ty(tcx);
390 let adt = match lvalue_type.sty {
391 TypeVariants::TyAdt(adt, _) if adt.is_enum() => adt,
393 span_bug!(stmt.source_info.span,
394 "bad set discriminant ({:?} = {:?}): lhs is not an enum",
399 if variant_index >= adt.variants.len() {
400 span_bug!(stmt.source_info.span,
401 "bad set discriminant ({:?} = {:?}): value of of range",
406 StatementKind::StorageLive(ref lv) |
407 StatementKind::StorageDead(ref lv) => {
409 Lvalue::Local(_) => {}
411 span_mirbug!(self, stmt, "bad lvalue: expected local");
415 StatementKind::InlineAsm { .. } |
416 StatementKind::EndRegion(_) |
417 StatementKind::Validate(..) |
418 StatementKind::Nop => {}
422 fn check_terminator(&mut self,
424 term: &Terminator<'tcx>) {
425 debug!("check_terminator: {:?}", term);
426 let tcx = self.tcx();
428 TerminatorKind::Goto { .. } |
429 TerminatorKind::Resume |
430 TerminatorKind::Return |
431 TerminatorKind::Unreachable |
432 TerminatorKind::Drop { .. } => {
433 // no checks needed for these
437 TerminatorKind::DropAndReplace {
442 let lv_ty = location.ty(mir, tcx).to_ty(tcx);
443 let rv_ty = value.ty(mir, tcx);
444 if let Err(terr) = self.sub_types(rv_ty, lv_ty) {
445 span_mirbug!(self, term, "bad DropAndReplace ({:?} = {:?}): {:?}",
449 TerminatorKind::SwitchInt { ref discr, switch_ty, .. } => {
450 let discr_ty = discr.ty(mir, tcx);
451 if let Err(terr) = self.sub_types(discr_ty, switch_ty) {
452 span_mirbug!(self, term, "bad SwitchInt ({:?} on {:?}): {:?}",
453 switch_ty, discr_ty, terr);
455 if !switch_ty.is_integral() && !switch_ty.is_char() &&
458 span_mirbug!(self, term, "bad SwitchInt discr ty {:?}",switch_ty);
460 // FIXME: check the values
462 TerminatorKind::Call { ref func, ref args, ref destination, .. } => {
463 let func_ty = func.ty(mir, tcx);
464 debug!("check_terminator: call, func_ty={:?}", func_ty);
465 let sig = match func_ty.sty {
466 ty::TyFnDef(..) | ty::TyFnPtr(_) => func_ty.fn_sig(tcx),
468 span_mirbug!(self, term, "call to non-function {:?}", func_ty);
472 let sig = tcx.erase_late_bound_regions(&sig);
473 let sig = self.normalize(&sig);
474 self.check_call_dest(mir, term, &sig, destination);
476 if self.is_box_free(func) {
477 self.check_box_free_inputs(mir, term, &sig, args);
479 self.check_call_inputs(mir, term, &sig, args);
482 TerminatorKind::Assert { ref cond, ref msg, .. } => {
483 let cond_ty = cond.ty(mir, tcx);
484 if cond_ty != tcx.types.bool {
485 span_mirbug!(self, term, "bad Assert ({:?}, not bool", cond_ty);
488 if let AssertMessage::BoundsCheck { ref len, ref index } = *msg {
489 if len.ty(mir, tcx) != tcx.types.usize {
490 span_mirbug!(self, len, "bounds-check length non-usize {:?}", len)
492 if index.ty(mir, tcx) != tcx.types.usize {
493 span_mirbug!(self, index, "bounds-check index non-usize {:?}", index)
500 fn check_call_dest(&mut self,
502 term: &Terminator<'tcx>,
503 sig: &ty::FnSig<'tcx>,
504 destination: &Option<(Lvalue<'tcx>, BasicBlock)>) {
505 let tcx = self.tcx();
507 Some((ref dest, _)) => {
508 let dest_ty = dest.ty(mir, tcx).to_ty(tcx);
509 if let Err(terr) = self.sub_types(sig.output(), dest_ty) {
510 span_mirbug!(self, term,
511 "call dest mismatch ({:?} <- {:?}): {:?}",
512 dest_ty, sig.output(), terr);
516 // FIXME(canndrew): This is_never should probably be an is_uninhabited
517 if !sig.output().is_never() {
518 span_mirbug!(self, term, "call to converging function {:?} w/o dest", sig);
524 fn check_call_inputs(&mut self,
526 term: &Terminator<'tcx>,
527 sig: &ty::FnSig<'tcx>,
528 args: &[Operand<'tcx>])
530 debug!("check_call_inputs({:?}, {:?})", sig, args);
531 if args.len() < sig.inputs().len() ||
532 (args.len() > sig.inputs().len() && !sig.variadic) {
533 span_mirbug!(self, term, "call to {:?} with wrong # of args", sig);
535 for (n, (fn_arg, op_arg)) in sig.inputs().iter().zip(args).enumerate() {
536 let op_arg_ty = op_arg.ty(mir, self.tcx());
537 if let Err(terr) = self.sub_types(op_arg_ty, fn_arg) {
538 span_mirbug!(self, term, "bad arg #{:?} ({:?} <- {:?}): {:?}",
539 n, fn_arg, op_arg_ty, terr);
544 fn is_box_free(&self, operand: &Operand<'tcx>) -> bool {
546 &Operand::Constant(box Constant {
547 literal: Literal::Value {
548 value: ConstVal::Function(def_id, _), ..
551 Some(def_id) == self.tcx().lang_items.box_free_fn()
557 fn check_box_free_inputs(&mut self,
559 term: &Terminator<'tcx>,
560 sig: &ty::FnSig<'tcx>,
561 args: &[Operand<'tcx>])
563 debug!("check_box_free_inputs");
565 // box_free takes a Box as a pointer. Allow for that.
567 if sig.inputs().len() != 1 {
568 span_mirbug!(self, term, "box_free should take 1 argument");
572 let pointee_ty = match sig.inputs()[0].sty {
573 ty::TyRawPtr(mt) => mt.ty,
575 span_mirbug!(self, term, "box_free should take a raw ptr");
581 span_mirbug!(self, term, "box_free called with wrong # of args");
585 let ty = args[0].ty(mir, self.tcx());
586 let arg_ty = match ty.sty {
587 ty::TyRawPtr(mt) => mt.ty,
588 ty::TyAdt(def, _) if def.is_box() => ty.boxed_ty(),
590 span_mirbug!(self, term, "box_free called with bad arg ty");
595 if let Err(terr) = self.sub_types(arg_ty, pointee_ty) {
596 span_mirbug!(self, term, "bad box_free arg ({:?} <- {:?}): {:?}",
597 pointee_ty, arg_ty, terr);
601 fn check_iscleanup(&mut self, mir: &Mir<'tcx>, block: &BasicBlockData<'tcx>)
603 let is_cleanup = block.is_cleanup;
604 self.last_span = block.terminator().source_info.span;
605 match block.terminator().kind {
606 TerminatorKind::Goto { target } =>
607 self.assert_iscleanup(mir, block, target, is_cleanup),
608 TerminatorKind::SwitchInt { ref targets, .. } => {
609 for target in targets {
610 self.assert_iscleanup(mir, block, *target, is_cleanup);
613 TerminatorKind::Resume => {
615 span_mirbug!(self, block, "resume on non-cleanup block!")
618 TerminatorKind::Return => {
620 span_mirbug!(self, block, "return on cleanup block")
623 TerminatorKind::Unreachable => {}
624 TerminatorKind::Drop { target, unwind, .. } |
625 TerminatorKind::DropAndReplace { target, unwind, .. } |
626 TerminatorKind::Assert { target, cleanup: unwind, .. } => {
627 self.assert_iscleanup(mir, block, target, is_cleanup);
628 if let Some(unwind) = unwind {
630 span_mirbug!(self, block, "unwind on cleanup block")
632 self.assert_iscleanup(mir, block, unwind, true);
635 TerminatorKind::Call { ref destination, cleanup, .. } => {
636 if let &Some((_, target)) = destination {
637 self.assert_iscleanup(mir, block, target, is_cleanup);
639 if let Some(cleanup) = cleanup {
641 span_mirbug!(self, block, "cleanup on cleanup block")
643 self.assert_iscleanup(mir, block, cleanup, true);
649 fn assert_iscleanup(&mut self,
655 if mir[bb].is_cleanup != iscleanuppad {
656 span_mirbug!(self, ctxt, "cleanuppad mismatch: {:?} should be {:?}",
661 fn check_local(&mut self, mir: &Mir<'gcx>, local: Local, local_decl: &LocalDecl<'gcx>) {
662 match mir.local_kind(local) {
663 LocalKind::ReturnPointer | LocalKind::Arg => {
664 // return values of normal functions are required to be
665 // sized by typeck, but return values of ADT constructors are
666 // not because we don't include a `Self: Sized` bounds on them.
668 // Unbound parts of arguments were never required to be Sized
669 // - maybe we should make that a warning.
672 LocalKind::Var | LocalKind::Temp => {}
675 let span = local_decl.source_info.span;
676 let ty = local_decl.ty;
677 if !ty.is_sized(self.tcx().global_tcx(), self.param_env, span) {
678 // in current MIR construction, all non-control-flow rvalue
679 // expressions evaluate through `as_temp` or `into` a return
680 // slot or local, so to find all unsized rvalues it is enough
681 // to check all temps, return slots and locals.
682 if let None = self.reported_errors.replace((ty, span)) {
683 span_err!(self.tcx().sess, span, E0161,
684 "cannot move a value of type {0}: the size of {0} \
685 cannot be statically determined", ty);
690 fn typeck_mir(&mut self, mir: &Mir<'gcx>) {
691 self.last_span = mir.span;
692 debug!("run_on_mir: {:?}", mir.span);
694 for (local, local_decl) in mir.local_decls.iter_enumerated() {
695 self.check_local(mir, local, local_decl);
698 for block in mir.basic_blocks() {
699 for stmt in &block.statements {
700 if stmt.source_info.span != DUMMY_SP {
701 self.last_span = stmt.source_info.span;
703 self.check_stmt(mir, stmt);
706 self.check_terminator(mir, block.terminator());
707 self.check_iscleanup(mir, block);
712 fn normalize<T>(&mut self, value: &T) -> T
713 where T: fmt::Debug + TypeFoldable<'tcx>
715 let mut selcx = traits::SelectionContext::new(self.infcx);
716 let cause = traits::ObligationCause::misc(self.last_span, ast::CRATE_NODE_ID);
717 let traits::Normalized { value, obligations } =
718 traits::normalize(&mut selcx, self.param_env, cause, value);
720 debug!("normalize: value={:?} obligations={:?}",
724 let fulfill_cx = &mut self.fulfillment_cx;
725 for obligation in obligations {
726 fulfill_cx.register_predicate_obligation(self.infcx, obligation);
732 fn verify_obligations(&mut self, mir: &Mir<'tcx>) {
733 self.last_span = mir.span;
734 if let Err(e) = self.fulfillment_cx.select_all_or_error(self.infcx) {
735 span_mirbug!(self, "", "errors selecting obligation: {:?}",
741 pub struct TypeckMir;
743 impl MirPass for TypeckMir {
744 fn run_pass<'a, 'tcx>(&self,
745 tcx: TyCtxt<'a, 'tcx, 'tcx>,
747 mir: &mut Mir<'tcx>) {
748 let item_id = src.item_id();
749 let def_id = tcx.hir.local_def_id(item_id);
750 debug!("run_pass: {:?}", def_id);
752 if tcx.sess.err_count() > 0 {
753 // compiling a broken program can obviously result in a
754 // broken MIR, so try not to report duplicate errors.
757 let param_env = tcx.param_env(def_id);
758 tcx.infer_ctxt().enter(|infcx| {
759 let mut checker = TypeChecker::new(&infcx, item_id, param_env);
761 let mut verifier = TypeVerifier::new(&mut checker, mir);
762 verifier.visit_mir(mir);
763 if verifier.errors_reported {
764 // don't do further checks to avoid ICEs
768 checker.typeck_mir(mir);
769 checker.verify_obligations(mir);