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;
   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>, body: &mut Body<'tcx>) {
  35         let def_id = body.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)
  42             .iterate_to_fixpoint()
  43             .into_results_cursor(body);
  44
  45         TypeChecker { when: &self.when, 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     body: &'a Body<'tcx>,
 145     tcx: TyCtxt<'tcx>,
 146     param_env: ParamEnv<'tcx>,
 147     mir_phase: MirPhase,
 148     storage_liveness: ResultsCursor<'a, 'tcx, MaybeStorageLive>,
 149 }
 150
 151 impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
 152     fn fail(&self, location: Location, msg: impl AsRef<str>) {
 153         let span = self.body.source_info(location).span;
 154         // We use `delay_span_bug` as we might see broken MIR when other errors have already
 155         // occurred.
 156         self.tcx.sess.diagnostic().delay_span_bug(
 157             span,
 158             &format!(
 159                 "broken MIR in {:?} ({}) at {:?}:\n{}",
 160                 self.body.source.instance,
 161                 self.when,
 162                 location,
 163                 msg.as_ref()
 164             ),
 165         );
 166     }
 167
 168     fn check_edge(&self, location: Location, bb: BasicBlock, edge_kind: EdgeKind) {
 169         if let Some(bb) = self.body.basic_blocks().get(bb) {
 170             let src = self.body.basic_blocks().get(location.block).unwrap();
 171             match (src.is_cleanup, bb.is_cleanup, edge_kind) {
 172                 // Non-cleanup blocks can jump to non-cleanup blocks along non-unwind edges
 173                 (false, false, EdgeKind::Normal)
 174                 // Non-cleanup blocks can jump to cleanup blocks along unwind edges
 175                 | (false, true, EdgeKind::Unwind)
 176                 // Cleanup blocks can jump to cleanup blocks along non-unwind edges
 177                 | (true, true, EdgeKind::Normal) => {}
 178                 // All other jumps are invalid
 179                 _ => {
 180                     self.fail(
 181                         location,
 182                         format!(
 183                             "{:?} edge to {:?} violates unwind invariants (cleanup {:?} -> {:?})",
 184                             edge_kind,
 185                             bb,
 186                             src.is_cleanup,
 187                             bb.is_cleanup,
 188                         )
 189                     )
 190                 }
 191             }
 192         } else {
 193             self.fail(location, format!("encountered jump to invalid basic block {:?}", bb))
 194         }
 195     }
 196
 197     /// Check if src can be assigned into dest.
 198     /// This is not precise, it will accept some incorrect assignments.
 199     fn mir_assign_valid_types(&self, src: Ty<'tcx>, dest: Ty<'tcx>) -> bool {
 200         // Fast path before we normalize.
 201         if src == dest {
 202             // Equal types, all is good.
 203             return true;
 204         }
 205         // Normalize projections and things like that.
 206         // FIXME: We need to reveal_all, as some optimizations change types in ways
 207         // that require unfolding opaque types.
 208         let param_env = self.param_env.with_reveal_all_normalized(self.tcx);
 209         let src = self.tcx.normalize_erasing_regions(param_env, src);
 210         let dest = self.tcx.normalize_erasing_regions(param_env, dest);
 211
 212         // Type-changing assignments can happen when subtyping is used. While
 213         // all normal lifetimes are erased, higher-ranked types with their
 214         // late-bound lifetimes are still around and can lead to type
 215         // differences. So we compare ignoring lifetimes.
 216         equal_up_to_regions(self.tcx, param_env, src, dest)
 217     }
 218 }
 219
 220 impl<'a, 'tcx> Visitor<'tcx> for TypeChecker<'a, 'tcx> {
 221     fn visit_local(&mut self, local: &Local, context: PlaceContext, location: Location) {
 222         if context.is_use() {
 223             // Uses of locals must occur while the local's storage is allocated.
 224             self.storage_liveness.seek_after_primary_effect(location);
 225             let locals_with_storage = self.storage_liveness.get();
 226             if !locals_with_storage.contains(*local) {
 227                 self.fail(location, format!("use of local {:?}, which has no storage here", local));
 228             }
 229         }
 230     }
 231
 232     fn visit_var_debug_info(&mut self, _var_debug_info: &VarDebugInfo<'tcx>) {
 233         // Debuginfo can contain field projections, which count as a use of the base local. Skip
 234         // debuginfo so that we avoid the storage liveness assertion in that case.
 235     }
 236
 237     fn visit_operand(&mut self, operand: &Operand<'tcx>, location: Location) {
 238         // `Operand::Copy` is only supposed to be used with `Copy` types.
 239         if let Operand::Copy(place) = operand {
 240             let ty = place.ty(&self.body.local_decls, self.tcx).ty;
 241             let span = self.body.source_info(location).span;
 242
 243             if !ty.is_copy_modulo_regions(self.tcx.at(span), self.param_env) {
 244                 self.fail(location, format!("`Operand::Copy` with non-`Copy` type {}", ty));
 245             }
 246         }
 247
 248         self.super_operand(operand, location);
 249     }
 250
 251     fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) {
 252         match &statement.kind {
 253             StatementKind::Assign(box (dest, rvalue)) => {
 254                 // LHS and RHS of the assignment must have the same type.
 255                 let left_ty = dest.ty(&self.body.local_decls, self.tcx).ty;
 256                 let right_ty = rvalue.ty(&self.body.local_decls, self.tcx);
 257                 if !self.mir_assign_valid_types(right_ty, left_ty) {
 258                     self.fail(
 259                         location,
 260                         format!(
 261                             "encountered `{:?}` with incompatible types:\n\
 262                             left-hand side has type: {}\n\
 263                             right-hand side has type: {}",
 264                             statement.kind, left_ty, right_ty,
 265                         ),
 266                     );
 267                 }
 268                 match rvalue {
 269                     // The sides of an assignment must not alias. Currently this just checks whether the places
 270                     // are identical.
 271                     Rvalue::Use(Operand::Copy(src) | Operand::Move(src)) => {
 272                         if dest == src {
 273                             self.fail(
 274                                 location,
 275                                 "encountered `Assign` statement with overlapping memory",
 276                             );
 277                         }
 278                     }
 279                     // The deaggregator currently does not deaggreagate arrays.
 280                     // So for now, we ignore them here.
 281                     Rvalue::Aggregate(box AggregateKind::Array { .. }, _) => {}
 282                     // All other aggregates must be gone after some phases.
 283                     Rvalue::Aggregate(box kind, _) => {
 284                         if self.mir_phase > MirPhase::DropLowering
 285                             && !matches!(kind, AggregateKind::Generator(..))
 286                         {
 287                             // Generators persist until the state machine transformation, but all
 288                             // other aggregates must have been lowered.
 289                             self.fail(
 290                                 location,
 291                                 format!("{:?} have been lowered to field assignments", rvalue),
 292                             )
 293                         } else if self.mir_phase > MirPhase::GeneratorLowering {
 294                             // No more aggregates after drop and generator lowering.
 295                             self.fail(
 296                                 location,
 297                                 format!("{:?} have been lowered to field assignments", rvalue),
 298                             )
 299                         }
 300                     }
 301                     Rvalue::Ref(_, BorrowKind::Shallow, _) => {
 302                         if self.mir_phase > MirPhase::DropLowering {
 303                             self.fail(
 304                                 location,
 305                                 "`Assign` statement with a `Shallow` borrow should have been removed after drop lowering phase",
 306                             );
 307                         }
 308                     }
 309                     _ => {}
 310                 }
 311             }
 312             StatementKind::AscribeUserType(..) => {
 313                 if self.mir_phase > MirPhase::DropLowering {
 314                     self.fail(
 315                         location,
 316                         "`AscribeUserType` should have been removed after drop lowering phase",
 317                     );
 318                 }
 319             }
 320             StatementKind::FakeRead(..) => {
 321                 if self.mir_phase > MirPhase::DropLowering {
 322                     self.fail(
 323                         location,
 324                         "`FakeRead` should have been removed after drop lowering phase",
 325                     );
 326                 }
 327             }
 328             _ => {}
 329         }
 330     }
 331
 332     fn visit_terminator(&mut self, terminator: &Terminator<'tcx>, location: Location) {
 333         match &terminator.kind {
 334             TerminatorKind::Goto { target } => {
 335                 self.check_edge(location, *target, EdgeKind::Normal);
 336             }
 337             TerminatorKind::SwitchInt { targets, switch_ty, discr } => {
 338                 let ty = discr.ty(&self.body.local_decls, self.tcx);
 339                 if ty != *switch_ty {
 340                     self.fail(
 341                         location,
 342                         format!(
 343                             "encountered `SwitchInt` terminator with type mismatch: {:?} != {:?}",
 344                             ty, switch_ty,
 345                         ),
 346                     );
 347                 }
 348                 for (_, target) in targets.iter() {
 349                     self.check_edge(location, target, EdgeKind::Normal);
 350                 }
 351                 self.check_edge(location, targets.otherwise(), EdgeKind::Normal);
 352             }
 353             TerminatorKind::Drop { target, unwind, .. } => {
 354                 self.check_edge(location, *target, EdgeKind::Normal);
 355                 if let Some(unwind) = unwind {
 356                     self.check_edge(location, *unwind, EdgeKind::Unwind);
 357                 }
 358             }
 359             TerminatorKind::DropAndReplace { target, unwind, .. } => {
 360                 if self.mir_phase > MirPhase::DropLowering {
 361                     self.fail(
 362                         location,
 363                         "`DropAndReplace` is not permitted to exist after drop elaboration",
 364                     );
 365                 }
 366                 self.check_edge(location, *target, EdgeKind::Normal);
 367                 if let Some(unwind) = unwind {
 368                     self.check_edge(location, *unwind, EdgeKind::Unwind);
 369                 }
 370             }
 371             TerminatorKind::Call { func, destination, cleanup, .. } => {
 372                 let func_ty = func.ty(&self.body.local_decls, self.tcx);
 373                 match func_ty.kind() {
 374                     ty::FnPtr(..) | ty::FnDef(..) => {}
 375                     _ => self.fail(
 376                         location,
 377                         format!("encountered non-callable type {} in `Call` terminator", func_ty),
 378                     ),
 379                 }
 380                 if let Some((_, target)) = destination {
 381                     self.check_edge(location, *target, EdgeKind::Normal);
 382                 }
 383                 if let Some(cleanup) = cleanup {
 384                     self.check_edge(location, *cleanup, EdgeKind::Unwind);
 385                 }
 386             }
 387             TerminatorKind::Assert { cond, target, cleanup, .. } => {
 388                 let cond_ty = cond.ty(&self.body.local_decls, self.tcx);
 389                 if cond_ty != self.tcx.types.bool {
 390                     self.fail(
 391                         location,
 392                         format!(
 393                             "encountered non-boolean condition of type {} in `Assert` terminator",
 394                             cond_ty
 395                         ),
 396                     );
 397                 }
 398                 self.check_edge(location, *target, EdgeKind::Normal);
 399                 if let Some(cleanup) = cleanup {
 400                     self.check_edge(location, *cleanup, EdgeKind::Unwind);
 401                 }
 402             }
 403             TerminatorKind::Yield { resume, drop, .. } => {
 404                 if self.mir_phase > MirPhase::GeneratorLowering {
 405                     self.fail(location, "`Yield` should have been replaced by generator lowering");
 406                 }
 407                 self.check_edge(location, *resume, EdgeKind::Normal);
 408                 if let Some(drop) = drop {
 409                     self.check_edge(location, *drop, EdgeKind::Normal);
 410                 }
 411             }
 412             TerminatorKind::FalseEdge { real_target, imaginary_target } => {
 413                 self.check_edge(location, *real_target, EdgeKind::Normal);
 414                 self.check_edge(location, *imaginary_target, EdgeKind::Normal);
 415             }
 416             TerminatorKind::FalseUnwind { real_target, unwind } => {
 417                 self.check_edge(location, *real_target, EdgeKind::Normal);
 418                 if let Some(unwind) = unwind {
 419                     self.check_edge(location, *unwind, EdgeKind::Unwind);
 420                 }
 421             }
 422             TerminatorKind::InlineAsm { destination, .. } => {
 423                 if let Some(destination) = destination {
 424                     self.check_edge(location, *destination, EdgeKind::Normal);
 425                 }
 426             }
 427             // Nothing to validate for these.
 428             TerminatorKind::Resume
 429             | TerminatorKind::Abort
 430             | TerminatorKind::Return
 431             | TerminatorKind::Unreachable
 432             | TerminatorKind::GeneratorDrop => {}
 433         }
 434     }
 435 }