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};
19 use rustc::mir::tcx::LvalueTy;
20 use rustc::mir::transform::{MirPass, MirSource, Pass};
21 use rustc::mir::visit::Visitor;
24 use syntax_pos::{Span, DUMMY_SP};
26 use rustc_data_structures::indexed_vec::Idx;
28 macro_rules! span_mirbug {
29 ($context:expr, $elem:expr, $($message:tt)*) => ({
30 $context.tcx().sess.span_warn(
32 &format!("broken MIR ({:?}): {}", $elem, format!($($message)*))
37 macro_rules! span_mirbug_and_err {
38 ($context:expr, $elem:expr, $($message:tt)*) => ({
40 $context.tcx().sess.span_warn(
42 &format!("broken MIR ({:?}): {:?}", $elem, format!($($message)*))
49 enum FieldAccessError {
50 OutOfRange { field_count: usize }
53 /// Verifies that MIR types are sane to not crash further checks.
55 /// The sanitize_XYZ methods here take an MIR object and compute its
56 /// type, calling `span_mirbug` and returning an error type if there
58 struct TypeVerifier<'a, 'b: 'a, 'gcx: 'b+'tcx, 'tcx: 'b> {
59 cx: &'a mut TypeChecker<'b, 'gcx, 'tcx>,
65 impl<'a, 'b, 'gcx, 'tcx> Visitor<'tcx> for TypeVerifier<'a, 'b, 'gcx, 'tcx> {
66 fn visit_span(&mut self, span: &Span) {
67 if *span != DUMMY_SP {
68 self.last_span = *span;
72 fn visit_lvalue(&mut self,
73 lvalue: &Lvalue<'tcx>,
74 _context: visit::LvalueContext,
76 self.sanitize_lvalue(lvalue, location);
79 fn visit_constant(&mut self, constant: &Constant<'tcx>, location: Location) {
80 self.super_constant(constant, location);
81 self.sanitize_type(constant, constant.ty);
84 fn visit_rvalue(&mut self, rvalue: &Rvalue<'tcx>, location: Location) {
85 self.super_rvalue(rvalue, location);
86 if let Some(ty) = rvalue.ty(self.mir, self.tcx()) {
87 self.sanitize_type(rvalue, ty);
91 fn visit_mir(&mut self, mir: &Mir<'tcx>) {
92 self.sanitize_type(&"return type", mir.return_ty);
93 for local_decl in &mir.local_decls {
94 self.sanitize_type(local_decl, local_decl.ty);
96 if self.errors_reported {
103 impl<'a, 'b, 'gcx, 'tcx> TypeVerifier<'a, 'b, 'gcx, 'tcx> {
104 fn new(cx: &'a mut TypeChecker<'b, 'gcx, 'tcx>, mir: &'a Mir<'tcx>) -> Self {
109 errors_reported: false
113 fn tcx(&self) -> TyCtxt<'a, 'gcx, 'tcx> {
117 fn sanitize_type(&mut self, parent: &fmt::Debug, ty: Ty<'tcx>) -> Ty<'tcx> {
118 if ty.needs_infer() || ty.has_escaping_regions() || ty.references_error() {
119 span_mirbug_and_err!(self, parent, "bad type {:?}", ty)
125 fn sanitize_lvalue(&mut self, lvalue: &Lvalue<'tcx>, location: Location) -> LvalueTy<'tcx> {
126 debug!("sanitize_lvalue: {:?}", lvalue);
128 Lvalue::Local(index) => LvalueTy::Ty { ty: self.mir.local_decls[index].ty },
129 Lvalue::Static(def_id) =>
130 LvalueTy::Ty { ty: self.tcx().item_type(def_id) },
131 Lvalue::Projection(ref proj) => {
132 let base_ty = self.sanitize_lvalue(&proj.base, location);
133 if let LvalueTy::Ty { ty } = base_ty {
134 if ty.references_error() {
135 assert!(self.errors_reported);
136 return LvalueTy::Ty { ty: self.tcx().types.err };
139 self.sanitize_projection(base_ty, &proj.elem, lvalue, location)
144 fn sanitize_projection(&mut self,
145 base: LvalueTy<'tcx>,
146 pi: &LvalueElem<'tcx>,
147 lvalue: &Lvalue<'tcx>,
150 debug!("sanitize_projection: {:?} {:?} {:?}", base, pi, lvalue);
151 let tcx = self.tcx();
152 let base_ty = base.to_ty(tcx);
153 let span = self.last_span;
155 ProjectionElem::Deref => {
156 let deref_ty = base_ty.builtin_deref(true, ty::LvaluePreference::NoPreference);
158 ty: deref_ty.map(|t| t.ty).unwrap_or_else(|| {
159 span_mirbug_and_err!(
160 self, lvalue, "deref of non-pointer {:?}", base_ty)
164 ProjectionElem::Index(ref i) => {
165 self.visit_operand(i, location);
166 let index_ty = i.ty(self.mir, tcx);
167 if index_ty != tcx.types.usize {
169 ty: span_mirbug_and_err!(self, i, "index by non-usize {:?}", i)
173 ty: base_ty.builtin_index().unwrap_or_else(|| {
174 span_mirbug_and_err!(
175 self, lvalue, "index of non-array {:?}", base_ty)
180 ProjectionElem::ConstantIndex { .. } => {
181 // consider verifying in-bounds
183 ty: base_ty.builtin_index().unwrap_or_else(|| {
184 span_mirbug_and_err!(
185 self, lvalue, "index of non-array {:?}", base_ty)
189 ProjectionElem::Subslice { from, to } => {
191 ty: match base_ty.sty {
192 ty::TyArray(inner, size) => {
193 let min_size = (from as usize) + (to as usize);
194 if let Some(rest_size) = size.checked_sub(min_size) {
195 tcx.mk_array(inner, rest_size)
197 span_mirbug_and_err!(
198 self, lvalue, "taking too-small slice of {:?}", base_ty)
201 ty::TySlice(..) => base_ty,
203 span_mirbug_and_err!(
204 self, lvalue, "slice of non-array {:?}", base_ty)
209 ProjectionElem::Downcast(adt_def1, index) =>
211 ty::TyAdt(adt_def, substs) if adt_def.is_enum() && adt_def == adt_def1 => {
212 if index >= adt_def.variants.len() {
214 ty: span_mirbug_and_err!(
217 "cast to variant #{:?} but enum only has {:?}",
219 adt_def.variants.len())
230 ty: span_mirbug_and_err!(
231 self, lvalue, "can't downcast {:?} as {:?}",
235 ProjectionElem::Field(field, fty) => {
236 let fty = self.sanitize_type(lvalue, fty);
237 match self.field_ty(lvalue, base, field) {
239 if let Err(terr) = self.cx.eq_types(span, ty, fty) {
241 self, lvalue, "bad field access ({:?}: {:?}): {:?}",
245 Err(FieldAccessError::OutOfRange { field_count }) => {
247 self, lvalue, "accessed field #{} but variant only has {}",
248 field.index(), field_count)
251 LvalueTy::Ty { ty: fty }
256 fn error(&mut self) -> Ty<'tcx> {
257 self.errors_reported = true;
261 fn field_ty(&mut self,
263 base_ty: LvalueTy<'tcx>,
265 -> Result<Ty<'tcx>, FieldAccessError>
267 let tcx = self.tcx();
269 let (variant, substs) = match base_ty {
270 LvalueTy::Downcast { adt_def, substs, variant_index } => {
271 (&adt_def.variants[variant_index], substs)
273 LvalueTy::Ty { ty } => match ty.sty {
274 ty::TyAdt(adt_def, substs) if adt_def.is_univariant() => {
275 (&adt_def.variants[0], substs)
277 ty::TyClosure(def_id, substs) => {
278 return match substs.upvar_tys(def_id, tcx).nth(field.index()) {
280 None => Err(FieldAccessError::OutOfRange {
281 field_count: substs.upvar_tys(def_id, tcx).count()
285 ty::TyTuple(tys, _) => {
286 return match tys.get(field.index()) {
288 None => Err(FieldAccessError::OutOfRange {
289 field_count: tys.len()
293 _ => return Ok(span_mirbug_and_err!(
294 self, parent, "can't project out of {:?}", base_ty))
298 if let Some(field) = variant.fields.get(field.index()) {
299 Ok(self.cx.normalize(&field.ty(tcx, substs)))
301 Err(FieldAccessError::OutOfRange { field_count: variant.fields.len() })
306 pub struct TypeChecker<'a, 'gcx: 'a+'tcx, 'tcx: 'a> {
307 infcx: &'a InferCtxt<'a, 'gcx, 'tcx>,
308 fulfillment_cx: traits::FulfillmentContext<'tcx>,
310 body_id: ast::NodeId,
313 impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> {
314 fn new(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>, body_id: ast::NodeId) -> Self {
317 fulfillment_cx: traits::FulfillmentContext::new(),
323 fn misc(&self, span: Span) -> traits::ObligationCause<'tcx> {
324 traits::ObligationCause::misc(span, self.body_id)
327 pub fn register_infer_ok_obligations<T>(&mut self, infer_ok: InferOk<'tcx, T>) -> T {
328 for obligation in infer_ok.obligations {
329 self.fulfillment_cx.register_predicate_obligation(self.infcx, obligation);
334 fn sub_types(&mut self, sup: Ty<'tcx>, sub: Ty<'tcx>)
335 -> infer::UnitResult<'tcx>
337 self.infcx.sub_types(false, &self.misc(self.last_span), sup, sub)
338 .map(|ok| self.register_infer_ok_obligations(ok))
341 fn eq_types(&mut self, span: Span, a: Ty<'tcx>, b: Ty<'tcx>)
342 -> infer::UnitResult<'tcx>
344 self.infcx.eq_types(false, &self.misc(span), a, b)
345 .map(|ok| self.register_infer_ok_obligations(ok))
348 fn tcx(&self) -> TyCtxt<'a, 'gcx, 'tcx> {
352 fn check_stmt(&mut self, mir: &Mir<'tcx>, stmt: &Statement<'tcx>) {
353 debug!("check_stmt: {:?}", stmt);
354 let tcx = self.tcx();
356 StatementKind::Assign(ref lv, ref rv) => {
357 let lv_ty = lv.ty(mir, tcx).to_ty(tcx);
358 let rv_ty = rv.ty(mir, tcx);
359 if let Some(rv_ty) = rv_ty {
360 if let Err(terr) = self.sub_types(rv_ty, lv_ty) {
361 span_mirbug!(self, stmt, "bad assignment ({:?} = {:?}): {:?}",
365 // FIXME: rvalue with undeterminable type - e.g. AggregateKind::Array branch that
368 StatementKind::SetDiscriminant{ ref lvalue, variant_index } => {
369 let lvalue_type = lvalue.ty(mir, tcx).to_ty(tcx);
370 let adt = match lvalue_type.sty {
371 TypeVariants::TyAdt(adt, _) if adt.is_enum() => adt,
373 span_bug!(stmt.source_info.span,
374 "bad set discriminant ({:?} = {:?}): lhs is not an enum",
379 if variant_index >= adt.variants.len() {
380 span_bug!(stmt.source_info.span,
381 "bad set discriminant ({:?} = {:?}): value of of range",
386 StatementKind::StorageLive(ref lv) |
387 StatementKind::StorageDead(ref lv) => {
389 Lvalue::Local(_) => {}
391 span_mirbug!(self, stmt, "bad lvalue: expected local");
395 StatementKind::InlineAsm { .. } |
396 StatementKind::Nop => {}
400 fn check_terminator(&mut self,
402 term: &Terminator<'tcx>) {
403 debug!("check_terminator: {:?}", term);
404 let tcx = self.tcx();
406 TerminatorKind::Goto { .. } |
407 TerminatorKind::Resume |
408 TerminatorKind::Return |
409 TerminatorKind::Unreachable |
410 TerminatorKind::Drop { .. } => {
411 // no checks needed for these
415 TerminatorKind::DropAndReplace {
420 let lv_ty = location.ty(mir, tcx).to_ty(tcx);
421 let rv_ty = value.ty(mir, tcx);
422 if let Err(terr) = self.sub_types(rv_ty, lv_ty) {
423 span_mirbug!(self, term, "bad DropAndReplace ({:?} = {:?}): {:?}",
427 TerminatorKind::SwitchInt { ref discr, switch_ty, .. } => {
428 let discr_ty = discr.ty(mir, tcx);
429 if let Err(terr) = self.sub_types(discr_ty, switch_ty) {
430 span_mirbug!(self, term, "bad SwitchInt ({:?} on {:?}): {:?}",
431 switch_ty, discr_ty, terr);
433 if !switch_ty.is_integral() && !switch_ty.is_char() &&
436 span_mirbug!(self, term, "bad SwitchInt discr ty {:?}",switch_ty);
438 // FIXME: check the values
440 TerminatorKind::Call { ref func, ref args, ref destination, .. } => {
441 let func_ty = func.ty(mir, tcx);
442 debug!("check_terminator: call, func_ty={:?}", func_ty);
443 let sig = match func_ty.sty {
444 ty::TyFnDef(.., sig) | ty::TyFnPtr(sig) => sig,
446 span_mirbug!(self, term, "call to non-function {:?}", func_ty);
450 let sig = tcx.erase_late_bound_regions(&sig);
451 let sig = self.normalize(&sig);
452 self.check_call_dest(mir, term, &sig, destination);
454 if self.is_box_free(func) {
455 self.check_box_free_inputs(mir, term, &sig, args);
457 self.check_call_inputs(mir, term, &sig, args);
460 TerminatorKind::Assert { ref cond, ref msg, .. } => {
461 let cond_ty = cond.ty(mir, tcx);
462 if cond_ty != tcx.types.bool {
463 span_mirbug!(self, term, "bad Assert ({:?}, not bool", cond_ty);
466 if let AssertMessage::BoundsCheck { ref len, ref index } = *msg {
467 if len.ty(mir, tcx) != tcx.types.usize {
468 span_mirbug!(self, len, "bounds-check length non-usize {:?}", len)
470 if index.ty(mir, tcx) != tcx.types.usize {
471 span_mirbug!(self, index, "bounds-check index non-usize {:?}", index)
478 fn check_call_dest(&mut self,
480 term: &Terminator<'tcx>,
481 sig: &ty::FnSig<'tcx>,
482 destination: &Option<(Lvalue<'tcx>, BasicBlock)>) {
483 let tcx = self.tcx();
485 Some((ref dest, _)) => {
486 let dest_ty = dest.ty(mir, tcx).to_ty(tcx);
487 if let Err(terr) = self.sub_types(sig.output(), dest_ty) {
488 span_mirbug!(self, term,
489 "call dest mismatch ({:?} <- {:?}): {:?}",
490 dest_ty, sig.output(), terr);
494 // FIXME(canndrew): This is_never should probably be an is_uninhabited
495 if !sig.output().is_never() {
496 span_mirbug!(self, term, "call to converging function {:?} w/o dest", sig);
502 fn check_call_inputs(&mut self,
504 term: &Terminator<'tcx>,
505 sig: &ty::FnSig<'tcx>,
506 args: &[Operand<'tcx>])
508 debug!("check_call_inputs({:?}, {:?})", sig, args);
509 if args.len() < sig.inputs().len() ||
510 (args.len() > sig.inputs().len() && !sig.variadic) {
511 span_mirbug!(self, term, "call to {:?} with wrong # of args", sig);
513 for (n, (fn_arg, op_arg)) in sig.inputs().iter().zip(args).enumerate() {
514 let op_arg_ty = op_arg.ty(mir, self.tcx());
515 if let Err(terr) = self.sub_types(op_arg_ty, fn_arg) {
516 span_mirbug!(self, term, "bad arg #{:?} ({:?} <- {:?}): {:?}",
517 n, fn_arg, op_arg_ty, terr);
522 fn is_box_free(&self, operand: &Operand<'tcx>) -> bool {
524 &Operand::Constant(Constant {
525 literal: Literal::Item { def_id, .. }, ..
527 Some(def_id) == self.tcx().lang_items.box_free_fn()
533 fn check_box_free_inputs(&mut self,
535 term: &Terminator<'tcx>,
536 sig: &ty::FnSig<'tcx>,
537 args: &[Operand<'tcx>])
539 debug!("check_box_free_inputs");
541 // box_free takes a Box as a pointer. Allow for that.
543 if sig.inputs().len() != 1 {
544 span_mirbug!(self, term, "box_free should take 1 argument");
548 let pointee_ty = match sig.inputs()[0].sty {
549 ty::TyRawPtr(mt) => mt.ty,
551 span_mirbug!(self, term, "box_free should take a raw ptr");
557 span_mirbug!(self, term, "box_free called with wrong # of args");
561 let ty = args[0].ty(mir, self.tcx());
562 let arg_ty = match ty.sty {
563 ty::TyRawPtr(mt) => mt.ty,
564 ty::TyAdt(def, _) if def.is_box() => ty.boxed_ty(),
566 span_mirbug!(self, term, "box_free called with bad arg ty");
571 if let Err(terr) = self.sub_types(arg_ty, pointee_ty) {
572 span_mirbug!(self, term, "bad box_free arg ({:?} <- {:?}): {:?}",
573 pointee_ty, arg_ty, terr);
577 fn check_iscleanup(&mut self, mir: &Mir<'tcx>, block: &BasicBlockData<'tcx>)
579 let is_cleanup = block.is_cleanup;
580 self.last_span = block.terminator().source_info.span;
581 match block.terminator().kind {
582 TerminatorKind::Goto { target } =>
583 self.assert_iscleanup(mir, block, target, is_cleanup),
584 TerminatorKind::SwitchInt { ref targets, .. } => {
585 for target in targets {
586 self.assert_iscleanup(mir, block, *target, is_cleanup);
589 TerminatorKind::Resume => {
591 span_mirbug!(self, block, "resume on non-cleanup block!")
594 TerminatorKind::Return => {
596 span_mirbug!(self, block, "return on cleanup block")
599 TerminatorKind::Unreachable => {}
600 TerminatorKind::Drop { target, unwind, .. } |
601 TerminatorKind::DropAndReplace { target, unwind, .. } |
602 TerminatorKind::Assert { target, cleanup: unwind, .. } => {
603 self.assert_iscleanup(mir, block, target, is_cleanup);
604 if let Some(unwind) = unwind {
606 span_mirbug!(self, block, "unwind on cleanup block")
608 self.assert_iscleanup(mir, block, unwind, true);
611 TerminatorKind::Call { ref destination, cleanup, .. } => {
612 if let &Some((_, target)) = destination {
613 self.assert_iscleanup(mir, block, target, is_cleanup);
615 if let Some(cleanup) = cleanup {
617 span_mirbug!(self, block, "cleanup on cleanup block")
619 self.assert_iscleanup(mir, block, cleanup, true);
625 fn assert_iscleanup(&mut self,
631 if mir[bb].is_cleanup != iscleanuppad {
632 span_mirbug!(self, ctxt, "cleanuppad mismatch: {:?} should be {:?}",
637 fn typeck_mir(&mut self, mir: &Mir<'tcx>) {
638 self.last_span = mir.span;
639 debug!("run_on_mir: {:?}", mir.span);
640 for block in mir.basic_blocks() {
641 for stmt in &block.statements {
642 if stmt.source_info.span != DUMMY_SP {
643 self.last_span = stmt.source_info.span;
645 self.check_stmt(mir, stmt);
648 self.check_terminator(mir, block.terminator());
649 self.check_iscleanup(mir, block);
654 fn normalize<T>(&mut self, value: &T) -> T
655 where T: fmt::Debug + TypeFoldable<'tcx>
657 let mut selcx = traits::SelectionContext::new(self.infcx);
658 let cause = traits::ObligationCause::misc(self.last_span, ast::CRATE_NODE_ID);
659 let traits::Normalized { value, obligations } =
660 traits::normalize(&mut selcx, cause, value);
662 debug!("normalize: value={:?} obligations={:?}",
666 let mut fulfill_cx = &mut self.fulfillment_cx;
667 for obligation in obligations {
668 fulfill_cx.register_predicate_obligation(self.infcx, obligation);
674 fn verify_obligations(&mut self, mir: &Mir<'tcx>) {
675 self.last_span = mir.span;
676 if let Err(e) = self.fulfillment_cx.select_all_or_error(self.infcx) {
677 span_mirbug!(self, "", "errors selecting obligation: {:?}",
683 pub struct TypeckMir;
686 pub fn new() -> Self {
691 impl<'tcx> MirPass<'tcx> for TypeckMir {
692 fn run_pass<'a>(&mut self, tcx: TyCtxt<'a, 'tcx, 'tcx>,
693 src: MirSource, mir: &mut Mir<'tcx>) {
694 debug!("run_pass: {}", tcx.node_path_str(src.item_id()));
696 if tcx.sess.err_count() > 0 {
697 // compiling a broken program can obviously result in a
698 // broken MIR, so try not to report duplicate errors.
701 let param_env = ty::ParameterEnvironment::for_item(tcx, src.item_id());
702 tcx.infer_ctxt(param_env, Reveal::UserFacing).enter(|infcx| {
703 let mut checker = TypeChecker::new(&infcx, src.item_id());
705 let mut verifier = TypeVerifier::new(&mut checker, mir);
706 verifier.visit_mir(mir);
707 if verifier.errors_reported {
708 // don't do further checks to avoid ICEs
712 checker.typeck_mir(mir);
713 checker.verify_obligations(mir);
718 impl Pass for TypeckMir {