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};
15 use rustc::traits::{self, Reveal};
16 use rustc::ty::fold::TypeFoldable;
17 use rustc::ty::{self, Ty, TyCtxt, TypeVariants};
18 use rustc::mir::repr::*;
19 use rustc::mir::tcx::LvalueTy;
20 use rustc::mir::transform::{MirPass, MirSource, Pass};
21 use rustc::mir::visit::{self, Visitor};
23 use syntax_pos::{Span, DUMMY_SP};
25 use rustc_data_structures::indexed_vec::Idx;
27 macro_rules! span_mirbug {
28 ($context:expr, $elem:expr, $($message:tt)*) => ({
29 $context.tcx().sess.span_warn(
31 &format!("broken MIR ({:?}): {}", $elem, format!($($message)*))
36 macro_rules! span_mirbug_and_err {
37 ($context:expr, $elem:expr, $($message:tt)*) => ({
39 $context.tcx().sess.span_warn(
41 &format!("broken MIR ({:?}): {:?}", $elem, format!($($message)*))
48 enum FieldAccessError {
49 OutOfRange { field_count: usize }
52 /// Verifies that MIR types are sane to not crash further checks.
54 /// The sanitize_XYZ methods here take an MIR object and compute its
55 /// type, calling `span_mirbug` and returning an error type if there
57 struct TypeVerifier<'a, 'b: 'a, 'gcx: 'b+'tcx, 'tcx: 'b> {
58 cx: &'a mut TypeChecker<'b, 'gcx, 'tcx>,
64 impl<'a, 'b, 'gcx, 'tcx> Visitor<'tcx> for TypeVerifier<'a, 'b, 'gcx, 'tcx> {
65 fn visit_span(&mut self, span: &Span) {
66 if *span != DUMMY_SP {
67 self.last_span = *span;
71 fn visit_lvalue(&mut self, lvalue: &Lvalue<'tcx>, _context: visit::LvalueContext) {
72 self.sanitize_lvalue(lvalue);
75 fn visit_constant(&mut self, constant: &Constant<'tcx>) {
76 self.super_constant(constant);
77 self.sanitize_type(constant, constant.ty);
80 fn visit_rvalue(&mut self, rvalue: &Rvalue<'tcx>) {
81 self.super_rvalue(rvalue);
82 if let Some(ty) = rvalue.ty(self.mir, self.tcx()) {
83 self.sanitize_type(rvalue, ty);
87 fn visit_mir(&mut self, mir: &Mir<'tcx>) {
88 if let ty::FnConverging(t) = mir.return_ty {
89 self.sanitize_type(&"return type", t);
91 for var_decl in &mir.var_decls {
92 self.sanitize_type(var_decl, var_decl.ty);
94 for (n, arg_decl) in mir.arg_decls.iter().enumerate() {
95 self.sanitize_type(&(n, arg_decl), arg_decl.ty);
97 for (n, tmp_decl) in mir.temp_decls.iter().enumerate() {
98 self.sanitize_type(&(n, tmp_decl), tmp_decl.ty);
100 if self.errors_reported {
107 impl<'a, 'b, 'gcx, 'tcx> TypeVerifier<'a, 'b, 'gcx, 'tcx> {
108 fn new(cx: &'a mut TypeChecker<'b, 'gcx, 'tcx>, mir: &'a Mir<'tcx>) -> Self {
113 errors_reported: false
117 fn tcx(&self) -> TyCtxt<'a, 'gcx, 'tcx> {
121 fn sanitize_type(&mut self, parent: &fmt::Debug, ty: Ty<'tcx>) -> Ty<'tcx> {
122 if ty.needs_infer() || ty.has_escaping_regions() || ty.references_error() {
123 span_mirbug_and_err!(self, parent, "bad type {:?}", ty)
129 fn sanitize_lvalue(&mut self, lvalue: &Lvalue<'tcx>) -> LvalueTy<'tcx> {
130 debug!("sanitize_lvalue: {:?}", lvalue);
132 Lvalue::Var(index) => LvalueTy::Ty { ty: self.mir.var_decls[index].ty },
133 Lvalue::Temp(index) => LvalueTy::Ty { ty: self.mir.temp_decls[index].ty },
134 Lvalue::Arg(index) => LvalueTy::Ty { ty: self.mir.arg_decls[index].ty },
135 Lvalue::Static(def_id) =>
136 LvalueTy::Ty { ty: self.tcx().lookup_item_type(def_id).ty },
137 Lvalue::ReturnPointer => {
138 if let ty::FnConverging(return_ty) = self.mir.return_ty {
139 LvalueTy::Ty { ty: return_ty }
142 ty: span_mirbug_and_err!(
143 self, lvalue, "return in diverging function")
147 Lvalue::Projection(ref proj) => {
148 let base_ty = self.sanitize_lvalue(&proj.base);
149 if let LvalueTy::Ty { ty } = base_ty {
150 if ty.references_error() {
151 assert!(self.errors_reported);
152 return LvalueTy::Ty { ty: self.tcx().types.err };
155 self.sanitize_projection(base_ty, &proj.elem, lvalue)
160 fn sanitize_projection(&mut self,
161 base: LvalueTy<'tcx>,
162 pi: &LvalueElem<'tcx>,
163 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);
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::TyEnum(adt_def, substs) if 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::TyStruct(adt_def, substs) | ty::TyEnum(adt_def, substs)
290 if adt_def.is_univariant() => {
291 (&adt_def.variants[0], substs)
293 ty::TyTuple(tys) | ty::TyClosure(_, ty::ClosureSubsts {
296 return match tys.get(field.index()) {
298 None => Err(FieldAccessError::OutOfRange {
299 field_count: tys.len()
303 _ => return Ok(span_mirbug_and_err!(
304 self, parent, "can't project out of {:?}", base_ty))
308 if let Some(field) = variant.fields.get(field.index()) {
309 Ok(self.cx.normalize(&field.ty(tcx, substs)))
311 Err(FieldAccessError::OutOfRange { field_count: variant.fields.len() })
316 pub struct TypeChecker<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
317 infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
318 fulfillment_cx: traits::FulfillmentContext<'tcx>,
322 impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> {
323 fn new(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>) -> Self {
326 fulfillment_cx: traits::FulfillmentContext::new(),
331 fn sub_types(&self, span: Span, sup: Ty<'tcx>, sub: Ty<'tcx>)
332 -> infer::UnitResult<'tcx>
334 self.infcx.sub_types(false, infer::TypeOrigin::Misc(span), sup, sub)
335 // FIXME(#32730) propagate obligations
336 .map(|InferOk { obligations, .. }| assert!(obligations.is_empty()))
339 fn eq_types(&self, span: Span, a: Ty<'tcx>, b: Ty<'tcx>)
340 -> infer::UnitResult<'tcx>
342 self.infcx.eq_types(false, infer::TypeOrigin::Misc(span), a, b)
343 // FIXME(#32730) propagate obligations
344 .map(|InferOk { obligations, .. }| assert!(obligations.is_empty()))
347 fn tcx(&self) -> TyCtxt<'a, 'gcx, 'tcx> {
351 fn check_stmt(&mut self, mir: &Mir<'tcx>, stmt: &Statement<'tcx>) {
352 debug!("check_stmt: {:?}", stmt);
353 let tcx = self.tcx();
355 StatementKind::Assign(ref lv, ref rv) => {
356 let lv_ty = lv.ty(mir, tcx).to_ty(tcx);
357 let rv_ty = rv.ty(mir, tcx);
358 if let Some(rv_ty) = rv_ty {
359 if let Err(terr) = self.sub_types(self.last_span, rv_ty, lv_ty) {
360 span_mirbug!(self, stmt, "bad assignment ({:?} = {:?}): {:?}",
363 // FIXME: rvalue with undeterminable type - e.g. inline
367 StatementKind::SetDiscriminant{ ref lvalue, variant_index } => {
368 let lvalue_type = lvalue.ty(mir, tcx).to_ty(tcx);
369 let adt = match lvalue_type.sty {
370 TypeVariants::TyEnum(adt, _) => adt,
372 span_bug!(stmt.source_info.span,
373 "bad set discriminant ({:?} = {:?}): lhs is not an enum",
378 if variant_index >= adt.variants.len() {
379 span_bug!(stmt.source_info.span,
380 "bad set discriminant ({:?} = {:?}): value of of range",
388 fn check_terminator(&mut self,
390 term: &Terminator<'tcx>) {
391 debug!("check_terminator: {:?}", term);
392 let tcx = self.tcx();
394 TerminatorKind::Goto { .. } |
395 TerminatorKind::Resume |
396 TerminatorKind::Return |
397 TerminatorKind::Unreachable |
398 TerminatorKind::Drop { .. } => {
399 // no checks needed for these
403 TerminatorKind::DropAndReplace {
408 let lv_ty = location.ty(mir, tcx).to_ty(tcx);
409 let rv_ty = value.ty(mir, tcx);
410 if let Err(terr) = self.sub_types(self.last_span, rv_ty, lv_ty) {
411 span_mirbug!(self, term, "bad DropAndReplace ({:?} = {:?}): {:?}",
416 TerminatorKind::If { ref cond, .. } => {
417 let cond_ty = cond.ty(mir, tcx);
421 span_mirbug!(self, term, "bad If ({:?}, not bool", cond_ty);
425 TerminatorKind::SwitchInt { ref discr, switch_ty, .. } => {
426 let discr_ty = discr.ty(mir, tcx).to_ty(tcx);
427 if let Err(terr) = self.sub_types(self.last_span, discr_ty, switch_ty) {
428 span_mirbug!(self, term, "bad SwitchInt ({:?} on {:?}): {:?}",
429 switch_ty, discr_ty, terr);
431 if !switch_ty.is_integral() && !switch_ty.is_char() &&
434 span_mirbug!(self, term, "bad SwitchInt discr ty {:?}",switch_ty);
436 // FIXME: check the values
438 TerminatorKind::Switch { ref discr, adt_def, ref targets } => {
439 let discr_ty = discr.ty(mir, tcx).to_ty(tcx);
442 if def == adt_def && adt_def.variants.len() == targets.len()
445 span_mirbug!(self, term, "bad Switch ({:?} on {:?})",
450 TerminatorKind::Call { ref func, ref args, ref destination, .. } => {
451 let func_ty = func.ty(mir, tcx);
452 debug!("check_terminator: call, func_ty={:?}", func_ty);
453 let func_ty = match func_ty.sty {
454 ty::TyFnDef(_, _, func_ty) | ty::TyFnPtr(func_ty) => func_ty,
456 span_mirbug!(self, term, "call to non-function {:?}", func_ty);
460 let sig = tcx.erase_late_bound_regions(&func_ty.sig);
461 let sig = self.normalize(&sig);
462 self.check_call_dest(mir, term, &sig, destination);
464 if self.is_box_free(func) {
465 self.check_box_free_inputs(mir, term, &sig, args);
467 self.check_call_inputs(mir, term, &sig, args);
470 TerminatorKind::Assert { ref cond, ref msg, .. } => {
471 let cond_ty = cond.ty(mir, tcx);
472 if cond_ty != tcx.types.bool {
473 span_mirbug!(self, term, "bad Assert ({:?}, not bool", cond_ty);
476 if let AssertMessage::BoundsCheck { ref len, ref index } = *msg {
477 if len.ty(mir, tcx) != tcx.types.usize {
478 span_mirbug!(self, len, "bounds-check length non-usize {:?}", len)
480 if index.ty(mir, tcx) != tcx.types.usize {
481 span_mirbug!(self, index, "bounds-check index non-usize {:?}", index)
488 fn check_call_dest(&self,
490 term: &Terminator<'tcx>,
491 sig: &ty::FnSig<'tcx>,
492 destination: &Option<(Lvalue<'tcx>, BasicBlock)>) {
493 let tcx = self.tcx();
494 match (destination, sig.output) {
495 (&Some(..), ty::FnDiverging) => {
496 span_mirbug!(self, term, "call to diverging function {:?} with dest", sig);
498 (&Some((ref dest, _)), ty::FnConverging(ty)) => {
499 let dest_ty = dest.ty(mir, tcx).to_ty(tcx);
500 if let Err(terr) = self.sub_types(self.last_span, ty, dest_ty) {
501 span_mirbug!(self, term,
502 "call dest mismatch ({:?} <- {:?}): {:?}",
506 (&None, ty::FnDiverging) => {}
507 (&None, ty::FnConverging(..)) => {
508 span_mirbug!(self, term, "call to converging function {:?} w/o dest", sig);
513 fn check_call_inputs(&self,
515 term: &Terminator<'tcx>,
516 sig: &ty::FnSig<'tcx>,
517 args: &[Operand<'tcx>])
519 debug!("check_call_inputs({:?}, {:?})", sig, args);
520 if args.len() < sig.inputs.len() ||
521 (args.len() > sig.inputs.len() && !sig.variadic) {
522 span_mirbug!(self, term, "call to {:?} with wrong # of args", sig);
524 for (n, (fn_arg, op_arg)) in sig.inputs.iter().zip(args).enumerate() {
525 let op_arg_ty = op_arg.ty(mir, self.tcx());
526 if let Err(terr) = self.sub_types(self.last_span, op_arg_ty, fn_arg) {
527 span_mirbug!(self, term, "bad arg #{:?} ({:?} <- {:?}): {:?}",
528 n, fn_arg, op_arg_ty, terr);
533 fn is_box_free(&self, operand: &Operand<'tcx>) -> bool {
535 &Operand::Constant(Constant {
536 literal: Literal::Item { def_id, .. }, ..
538 Some(def_id) == self.tcx().lang_items.box_free_fn()
544 fn check_box_free_inputs(&self,
546 term: &Terminator<'tcx>,
547 sig: &ty::FnSig<'tcx>,
548 args: &[Operand<'tcx>])
550 debug!("check_box_free_inputs");
552 // box_free takes a Box as a pointer. Allow for that.
554 if sig.inputs.len() != 1 {
555 span_mirbug!(self, term, "box_free should take 1 argument");
559 let pointee_ty = match sig.inputs[0].sty {
560 ty::TyRawPtr(mt) => mt.ty,
562 span_mirbug!(self, term, "box_free should take a raw ptr");
568 span_mirbug!(self, term, "box_free called with wrong # of args");
572 let arg_ty = match args[0].ty(mir, self.tcx()).sty {
573 ty::TyRawPtr(mt) => mt.ty,
576 span_mirbug!(self, term, "box_free called with bad arg ty");
581 if let Err(terr) = self.sub_types(self.last_span, arg_ty, pointee_ty) {
582 span_mirbug!(self, term, "bad box_free arg ({:?} <- {:?}): {:?}",
583 pointee_ty, arg_ty, terr);
587 fn check_iscleanup(&mut self, mir: &Mir<'tcx>, block: &BasicBlockData<'tcx>)
589 let is_cleanup = block.is_cleanup;
590 self.last_span = block.terminator().source_info.span;
591 match block.terminator().kind {
592 TerminatorKind::Goto { target } =>
593 self.assert_iscleanup(mir, block, target, is_cleanup),
594 TerminatorKind::If { targets: (on_true, on_false), .. } => {
595 self.assert_iscleanup(mir, block, on_true, is_cleanup);
596 self.assert_iscleanup(mir, block, on_false, is_cleanup);
598 TerminatorKind::Switch { ref targets, .. } |
599 TerminatorKind::SwitchInt { ref targets, .. } => {
600 for target in targets {
601 self.assert_iscleanup(mir, block, *target, is_cleanup);
604 TerminatorKind::Resume => {
606 span_mirbug!(self, block, "resume on non-cleanup block!")
609 TerminatorKind::Return => {
611 span_mirbug!(self, block, "return on cleanup block")
614 TerminatorKind::Unreachable => {}
615 TerminatorKind::Drop { target, unwind, .. } |
616 TerminatorKind::DropAndReplace { target, unwind, .. } |
617 TerminatorKind::Assert { target, cleanup: unwind, .. } => {
618 self.assert_iscleanup(mir, block, target, is_cleanup);
619 if let Some(unwind) = unwind {
621 span_mirbug!(self, block, "unwind on cleanup block")
623 self.assert_iscleanup(mir, block, unwind, true);
626 TerminatorKind::Call { ref destination, cleanup, .. } => {
627 if let &Some((_, target)) = destination {
628 self.assert_iscleanup(mir, block, target, is_cleanup);
630 if let Some(cleanup) = cleanup {
632 span_mirbug!(self, block, "cleanup on cleanup block")
634 self.assert_iscleanup(mir, block, cleanup, true);
640 fn assert_iscleanup(&mut self,
646 if mir[bb].is_cleanup != iscleanuppad {
647 span_mirbug!(self, ctxt, "cleanuppad mismatch: {:?} should be {:?}",
652 fn typeck_mir(&mut self, mir: &Mir<'tcx>) {
653 self.last_span = mir.span;
654 debug!("run_on_mir: {:?}", mir.span);
655 for block in mir.basic_blocks() {
656 for stmt in &block.statements {
657 if stmt.source_info.span != DUMMY_SP {
658 self.last_span = stmt.source_info.span;
660 self.check_stmt(mir, stmt);
663 self.check_terminator(mir, block.terminator());
664 self.check_iscleanup(mir, block);
669 fn normalize<T>(&mut self, value: &T) -> T
670 where T: fmt::Debug + TypeFoldable<'tcx>
672 let mut selcx = traits::SelectionContext::new(self.infcx);
673 let cause = traits::ObligationCause::misc(self.last_span, 0);
674 let traits::Normalized { value, obligations } =
675 traits::normalize(&mut selcx, cause, value);
677 debug!("normalize: value={:?} obligations={:?}",
681 let mut fulfill_cx = &mut self.fulfillment_cx;
682 for obligation in obligations {
683 fulfill_cx.register_predicate_obligation(self.infcx, obligation);
689 fn verify_obligations(&mut self, mir: &Mir<'tcx>) {
690 self.last_span = mir.span;
691 if let Err(e) = self.fulfillment_cx.select_all_or_error(self.infcx) {
692 span_mirbug!(self, "", "errors selecting obligation: {:?}",
698 pub struct TypeckMir;
701 pub fn new() -> Self {
706 impl<'tcx> MirPass<'tcx> for TypeckMir {
707 fn run_pass<'a>(&mut self, tcx: TyCtxt<'a, 'tcx, 'tcx>,
708 src: MirSource, mir: &mut Mir<'tcx>) {
709 if tcx.sess.err_count() > 0 {
710 // compiling a broken program can obviously result in a
711 // broken MIR, so try not to report duplicate errors.
714 let param_env = ty::ParameterEnvironment::for_item(tcx, src.item_id());
715 tcx.infer_ctxt(None, Some(param_env), Reveal::NotSpecializable).enter(|infcx| {
716 let mut checker = TypeChecker::new(&infcx);
718 let mut verifier = TypeVerifier::new(&mut checker, mir);
719 verifier.visit_mir(mir);
720 if verifier.errors_reported {
721 // don't do further checks to avoid ICEs
725 checker.typeck_mir(mir);
726 checker.verify_obligations(mir);
731 impl Pass for TypeckMir {