compiler/rustc_mir/src/transform/validate.rs

   1 //! Validates the MIR to ensure that invariants are upheld.
   2
   3 use crate::dataflow::impls::MaybeStorageLive;
   4 use crate::dataflow::{Analysis, ResultsCursor};
   5 use crate::util::storage::AlwaysLiveLocals;
   6
   7 use super::{MirPass, MirSource};
   8 use rustc_middle::mir::visit::{PlaceContext, Visitor};
   9 use rustc_middle::mir::{
  10     AggregateKind, BasicBlock, Body, BorrowKind, Local, Location, MirPhase, Operand, Rvalue,
  11     Statement, StatementKind, Terminator, TerminatorKind, VarDebugInfo,
  12 };
  13 use rustc_middle::ty::relate::{Relate, RelateResult, TypeRelation};
  14 use rustc_middle::ty::{self, ParamEnv, Ty, TyCtxt};
  15
  16 #[derive(Copy, Clone, Debug)]
  17 enum EdgeKind {
  18     Unwind,
  19     Normal,
  20 }
  21
  22 pub struct Validator {
  23     /// Describes at which point in the pipeline this validation is happening.
  24     pub when: String,
  25     /// The phase for which we are upholding the dialect. If the given phase forbids a specific
  26     /// element, this validator will now emit errors if that specific element is encountered.
  27     /// Note that phases that change the dialect cause all *following* phases to check the
  28     /// invariants of the new dialect. A phase that changes dialects never checks the new invariants
  29     /// itself.
  30     pub mir_phase: MirPhase,
  31 }
  32
  33 impl<'tcx> MirPass<'tcx> for Validator {
  34     fn run_pass(&self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut Body<'tcx>) {
  35         let def_id = source.def_id();
  36         let param_env = tcx.param_env(def_id);
  37         let mir_phase = self.mir_phase;
  38
  39         let always_live_locals = AlwaysLiveLocals::new(body);
  40         let storage_liveness = MaybeStorageLive::new(always_live_locals)
  41             .into_engine(tcx, body, def_id)
  42             .iterate_to_fixpoint()
  43             .into_results_cursor(body);
  44
  45         TypeChecker { when: &self.when, source, body, tcx, param_env, mir_phase, storage_liveness }
  46             .visit_body(body);
  47     }
  48 }
  49
  50 /// Returns whether the two types are equal up to lifetimes.
  51 /// All lifetimes, including higher-ranked ones, get ignored for this comparison.
  52 /// (This is unlike the `erasing_regions` methods, which keep higher-ranked lifetimes for soundness reasons.)
  53 ///
  54 /// The point of this function is to approximate "equal up to subtyping".  However,
  55 /// the approximation is incorrect as variance is ignored.
  56 pub fn equal_up_to_regions(
  57     tcx: TyCtxt<'tcx>,
  58     param_env: ParamEnv<'tcx>,
  59     src: Ty<'tcx>,
  60     dest: Ty<'tcx>,
  61 ) -> bool {
  62     // Fast path.
  63     if src == dest {
  64         return true;
  65     }
  66
  67     struct LifetimeIgnoreRelation<'tcx> {
  68         tcx: TyCtxt<'tcx>,
  69         param_env: ty::ParamEnv<'tcx>,
  70     }
  71
  72     impl TypeRelation<'tcx> for LifetimeIgnoreRelation<'tcx> {
  73         fn tcx(&self) -> TyCtxt<'tcx> {
  74             self.tcx
  75         }
  76
  77         fn param_env(&self) -> ty::ParamEnv<'tcx> {
  78             self.param_env
  79         }
  80
  81         fn tag(&self) -> &'static str {
  82             "librustc_mir::transform::validate"
  83         }
  84
  85         fn a_is_expected(&self) -> bool {
  86             true
  87         }
  88
  89         fn relate_with_variance<T: Relate<'tcx>>(
  90             &mut self,
  91             _: ty::Variance,
  92             a: T,
  93             b: T,
  94         ) -> RelateResult<'tcx, T> {
  95             // Ignore variance, require types to be exactly the same.
  96             self.relate(a, b)
  97         }
  98
  99         fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
 100             if a == b {
 101                 // Short-circuit.
 102                 return Ok(a);
 103             }
 104             ty::relate::super_relate_tys(self, a, b)
 105         }
 106
 107         fn regions(
 108             &mut self,
 109             a: ty::Region<'tcx>,
 110             _b: ty::Region<'tcx>,
 111         ) -> RelateResult<'tcx, ty::Region<'tcx>> {
 112             // Ignore regions.
 113             Ok(a)
 114         }
 115
 116         fn consts(
 117             &mut self,
 118             a: &'tcx ty::Const<'tcx>,
 119             b: &'tcx ty::Const<'tcx>,
 120         ) -> RelateResult<'tcx, &'tcx ty::Const<'tcx>> {
 121             ty::relate::super_relate_consts(self, a, b)
 122         }
 123
 124         fn binders<T>(
 125             &mut self,
 126             a: ty::Binder<T>,
 127             b: ty::Binder<T>,
 128         ) -> RelateResult<'tcx, ty::Binder<T>>
 129         where
 130             T: Relate<'tcx>,
 131         {
 132             self.relate(a.skip_binder(), b.skip_binder())?;
 133             Ok(a)
 134         }
 135     }
 136
 137     // Instantiate and run relation.
 138     let mut relator: LifetimeIgnoreRelation<'tcx> = LifetimeIgnoreRelation { tcx: tcx, param_env };
 139     relator.relate(src, dest).is_ok()
 140 }
 141
 142 struct TypeChecker<'a, 'tcx> {
 143     when: &'a str,
 144     source: MirSource<'tcx>,
 145     body: &'a Body<'tcx>,
 146     tcx: TyCtxt<'tcx>,
 147     param_env: ParamEnv<'tcx>,
 148     mir_phase: MirPhase,
 149     storage_liveness: ResultsCursor<'a, 'tcx, MaybeStorageLive>,
 150 }
 151
 152 impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
 153     fn fail(&self, location: Location, msg: impl AsRef<str>) {
 154         let span = self.body.source_info(location).span;
 155         // We use `delay_span_bug` as we might see broken MIR when other errors have already
 156         // occurred.
 157         self.tcx.sess.diagnostic().delay_span_bug(
 158             span,
 159             &format!(
 160                 "broken MIR in {:?} ({}) at {:?}:\n{}",
 161                 self.source.instance,
 162                 self.when,
 163                 location,
 164                 msg.as_ref()
 165             ),
 166         );
 167     }
 168
 169     fn check_edge(&self, location: Location, bb: BasicBlock, edge_kind: EdgeKind) {
 170         if let Some(bb) = self.body.basic_blocks().get(bb) {
 171             let src = self.body.basic_blocks().get(location.block).unwrap();
 172             match (src.is_cleanup, bb.is_cleanup, edge_kind) {
 173                 // Non-cleanup blocks can jump to non-cleanup blocks along non-unwind edges
 174                 (false, false, EdgeKind::Normal)
 175                 // Non-cleanup blocks can jump to cleanup blocks along unwind edges
 176                 | (false, true, EdgeKind::Unwind)
 177                 // Cleanup blocks can jump to cleanup blocks along non-unwind edges
 178                 | (true, true, EdgeKind::Normal) => {}
 179                 // All other jumps are invalid
 180                 _ => {
 181                     self.fail(
 182                         location,
 183                         format!(
 184                             "{:?} edge to {:?} violates unwind invariants (cleanup {:?} -> {:?})",
 185                             edge_kind,
 186                             bb,
 187                             src.is_cleanup,
 188                             bb.is_cleanup,
 189                         )
 190                     )
 191                 }
 192             }
 193         } else {
 194             self.fail(location, format!("encountered jump to invalid basic block {:?}", bb))
 195         }
 196     }
 197
 198     /// Check if src can be assigned into dest.
 199     /// This is not precise, it will accept some incorrect assignments.
 200     fn mir_assign_valid_types(&self, src: Ty<'tcx>, dest: Ty<'tcx>) -> bool {
 201         // Fast path before we normalize.
 202         if src == dest {
 203             // Equal types, all is good.
 204             return true;
 205         }
 206         // Normalize projections and things like that.
 207         // FIXME: We need to reveal_all, as some optimizations change types in ways
 208         // that require unfolding opaque types.
 209         let param_env = self.param_env.with_reveal_all_normalized(self.tcx);
 210         let src = self.tcx.normalize_erasing_regions(param_env, src);
 211         let dest = self.tcx.normalize_erasing_regions(param_env, dest);
 212
 213         // Type-changing assignments can happen when subtyping is used. While
 214         // all normal lifetimes are erased, higher-ranked types with their
 215         // late-bound lifetimes are still around and can lead to type
 216         // differences. So we compare ignoring lifetimes.
 217         equal_up_to_regions(self.tcx, param_env, src, dest)
 218     }
 219 }
 220
 221 impl<'a, 'tcx> Visitor<'tcx> for TypeChecker<'a, 'tcx> {
 222     fn visit_local(&mut self, local: &Local, context: PlaceContext, location: Location) {
 223         if context.is_use() {
 224             // Uses of locals must occur while the local's storage is allocated.
 225             self.storage_liveness.seek_after_primary_effect(location);
 226             let locals_with_storage = self.storage_liveness.get();
 227             if !locals_with_storage.contains(*local) {
 228                 self.fail(location, format!("use of local {:?}, which has no storage here", local));
 229             }
 230         }
 231     }
 232
 233     fn visit_var_debug_info(&mut self, _var_debug_info: &VarDebugInfo<'tcx>) {
 234         // Debuginfo can contain field projections, which count as a use of the base local. Skip
 235         // debuginfo so that we avoid the storage liveness assertion in that case.
 236     }
 237
 238     fn visit_operand(&mut self, operand: &Operand<'tcx>, location: Location) {
 239         // `Operand::Copy` is only supposed to be used with `Copy` types.
 240         if let Operand::Copy(place) = operand {
 241             let ty = place.ty(&self.body.local_decls, self.tcx).ty;
 242             let span = self.body.source_info(location).span;
 243
 244             if !ty.is_copy_modulo_regions(self.tcx.at(span), self.param_env) {
 245                 self.fail(location, format!("`Operand::Copy` with non-`Copy` type {}", ty));
 246             }
 247         }
 248
 249         self.super_operand(operand, location);
 250     }
 251
 252     fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) {
 253         match &statement.kind {
 254             StatementKind::Assign(box (dest, rvalue)) => {
 255                 // LHS and RHS of the assignment must have the same type.
 256                 let left_ty = dest.ty(&self.body.local_decls, self.tcx).ty;
 257                 let right_ty = rvalue.ty(&self.body.local_decls, self.tcx);
 258                 if !self.mir_assign_valid_types(right_ty, left_ty) {
 259                     self.fail(
 260                         location,
 261                         format!(
 262                             "encountered `{:?}` with incompatible types:\n\
 263                             left-hand side has type: {}\n\
 264                             right-hand side has type: {}",
 265                             statement.kind, left_ty, right_ty,
 266                         ),
 267                     );
 268                 }
 269                 match rvalue {
 270                     // The sides of an assignment must not alias. Currently this just checks whether the places
 271                     // are identical.
 272                     Rvalue::Use(Operand::Copy(src) | Operand::Move(src)) => {
 273                         if dest == src {
 274                             self.fail(
 275                                 location,
 276                                 "encountered `Assign` statement with overlapping memory",
 277                             );
 278                         }
 279                     }
 280                     // The deaggregator currently does not deaggreagate arrays.
 281                     // So for now, we ignore them here.
 282                     Rvalue::Aggregate(box AggregateKind::Array { .. }, _) => {}
 283                     // All other aggregates must be gone after some phases.
 284                     Rvalue::Aggregate(box kind, _) => {
 285                         if self.mir_phase > MirPhase::DropLowering
 286                             && !matches!(kind, AggregateKind::Generator(..))
 287                         {
 288                             // Generators persist until the state machine transformation, but all
 289                             // other aggregates must have been lowered.
 290                             self.fail(
 291                                 location,
 292                                 format!("{:?} have been lowered to field assignments", rvalue),
 293                             )
 294                         } else if self.mir_phase > MirPhase::GeneratorLowering {
 295                             // No more aggregates after drop and generator lowering.
 296                             self.fail(
 297                                 location,
 298                                 format!("{:?} have been lowered to field assignments", rvalue),
 299                             )
 300                         }
 301                     }
 302                     Rvalue::Ref(_, BorrowKind::Shallow, _) => {
 303                         if self.mir_phase > MirPhase::DropLowering {
 304                             self.fail(
 305                                 location,
 306                                 "`Assign` statement with a `Shallow` borrow should have been removed after drop lowering phase",
 307                             );
 308                         }
 309                     }
 310                     _ => {}
 311                 }
 312             }
 313             StatementKind::AscribeUserType(..) => {
 314                 if self.mir_phase > MirPhase::DropLowering {
 315                     self.fail(
 316                         location,
 317                         "`AscribeUserType` should have been removed after drop lowering phase",
 318                     );
 319                 }
 320             }
 321             StatementKind::FakeRead(..) => {
 322                 if self.mir_phase > MirPhase::DropLowering {
 323                     self.fail(
 324                         location,
 325                         "`FakeRead` should have been removed after drop lowering phase",
 326                     );
 327                 }
 328             }
 329             _ => {}
 330         }
 331     }
 332
 333     fn visit_terminator(&mut self, terminator: &Terminator<'tcx>, location: Location) {
 334         match &terminator.kind {
 335             TerminatorKind::Goto { target } => {
 336                 self.check_edge(location, *target, EdgeKind::Normal);
 337             }
 338             TerminatorKind::SwitchInt { targets, values, switch_ty, discr } => {
 339                 let ty = discr.ty(&self.body.local_decls, self.tcx);
 340                 if ty != *switch_ty {
 341                     self.fail(
 342                         location,
 343                         format!(
 344                             "encountered `SwitchInt` terminator with type mismatch: {:?} != {:?}",
 345                             ty, switch_ty,
 346                         ),
 347                     );
 348                 }
 349                 if targets.len() != values.len() + 1 {
 350                     self.fail(
 351                         location,
 352                         format!(
 353                             "encountered `SwitchInt` terminator with {} values, but {} targets (should be values+1)",
 354                             values.len(),
 355                             targets.len(),
 356                         ),
 357                     );
 358                 }
 359                 for target in targets {
 360                     self.check_edge(location, *target, EdgeKind::Normal);
 361                 }
 362             }
 363             TerminatorKind::Drop { target, unwind, .. } => {
 364                 self.check_edge(location, *target, EdgeKind::Normal);
 365                 if let Some(unwind) = unwind {
 366                     self.check_edge(location, *unwind, EdgeKind::Unwind);
 367                 }
 368             }
 369             TerminatorKind::DropAndReplace { target, unwind, .. } => {
 370                 if self.mir_phase > MirPhase::DropLowering {
 371                     self.fail(
 372                         location,
 373                         "`DropAndReplace` is not permitted to exist after drop elaboration",
 374                     );
 375                 }
 376                 self.check_edge(location, *target, EdgeKind::Normal);
 377                 if let Some(unwind) = unwind {
 378                     self.check_edge(location, *unwind, EdgeKind::Unwind);
 379                 }
 380             }
 381             TerminatorKind::Call { func, destination, cleanup, .. } => {
 382                 let func_ty = func.ty(&self.body.local_decls, self.tcx);
 383                 match func_ty.kind() {
 384                     ty::FnPtr(..) | ty::FnDef(..) => {}
 385                     _ => self.fail(
 386                         location,
 387                         format!("encountered non-callable type {} in `Call` terminator", func_ty),
 388                     ),
 389                 }
 390                 if let Some((_, target)) = destination {
 391                     self.check_edge(location, *target, EdgeKind::Normal);
 392                 }
 393                 if let Some(cleanup) = cleanup {
 394                     self.check_edge(location, *cleanup, EdgeKind::Unwind);
 395                 }
 396             }
 397             TerminatorKind::Assert { cond, target, cleanup, .. } => {
 398                 let cond_ty = cond.ty(&self.body.local_decls, self.tcx);
 399                 if cond_ty != self.tcx.types.bool {
 400                     self.fail(
 401                         location,
 402                         format!(
 403                             "encountered non-boolean condition of type {} in `Assert` terminator",
 404                             cond_ty
 405                         ),
 406                     );
 407                 }
 408                 self.check_edge(location, *target, EdgeKind::Normal);
 409                 if let Some(cleanup) = cleanup {
 410                     self.check_edge(location, *cleanup, EdgeKind::Unwind);
 411                 }
 412             }
 413             TerminatorKind::Yield { resume, drop, .. } => {
 414                 if self.mir_phase > MirPhase::GeneratorLowering {
 415                     self.fail(location, "`Yield` should have been replaced by generator lowering");
 416                 }
 417                 self.check_edge(location, *resume, EdgeKind::Normal);
 418                 if let Some(drop) = drop {
 419                     self.check_edge(location, *drop, EdgeKind::Normal);
 420                 }
 421             }
 422             TerminatorKind::FalseEdge { real_target, imaginary_target } => {
 423                 self.check_edge(location, *real_target, EdgeKind::Normal);
 424                 self.check_edge(location, *imaginary_target, EdgeKind::Normal);
 425             }
 426             TerminatorKind::FalseUnwind { real_target, unwind } => {
 427                 self.check_edge(location, *real_target, EdgeKind::Normal);
 428                 if let Some(unwind) = unwind {
 429                     self.check_edge(location, *unwind, EdgeKind::Unwind);
 430                 }
 431             }
 432             TerminatorKind::InlineAsm { destination, .. } => {
 433                 if let Some(destination) = destination {
 434                     self.check_edge(location, *destination, EdgeKind::Normal);
 435                 }
 436             }
 437             // Nothing to validate for these.
 438             TerminatorKind::Resume
 439             | TerminatorKind::Abort
 440             | TerminatorKind::Return
 441             | TerminatorKind::Unreachable
 442             | TerminatorKind::GeneratorDrop => {}
 443         }
 444     }
 445 }