compiler/rustc_mir/src/transform/validate.rs

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