src/librustc_mir/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         BasicBlock, Body, Location, Operand, Rvalue, Statement, StatementKind, Terminator,
   8         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 }
  27
  28 impl<'tcx> MirPass<'tcx> for Validator {
  29     fn run_pass(&self, tcx: TyCtxt<'tcx>, source: MirSource<'tcx>, body: &mut Body<'tcx>) {
  30         let param_env = tcx.param_env(source.def_id());
  31         TypeChecker { when: &self.when, source, body, tcx, param_env }.visit_body(body);
  32     }
  33 }
  34
  35 /// Returns whether the two types are equal up to lifetimes.
  36 /// All lifetimes, including higher-ranked ones, get ignored for this comparison.
  37 /// (This is unlike the `erasing_regions` methods, which keep higher-ranked lifetimes for soundness reasons.)
  38 ///
  39 /// The point of this function is to approximate "equal up to subtyping".  However,
  40 /// the approximation is incorrect as variance is ignored.
  41 pub fn equal_up_to_regions(
  42     tcx: TyCtxt<'tcx>,
  43     param_env: ParamEnv<'tcx>,
  44     src: Ty<'tcx>,
  45     dest: Ty<'tcx>,
  46 ) -> bool {
  47     // Fast path.
  48     if src == dest {
  49         return true;
  50     }
  51
  52     struct LifetimeIgnoreRelation<'tcx> {
  53         tcx: TyCtxt<'tcx>,
  54         param_env: ty::ParamEnv<'tcx>,
  55     }
  56
  57     impl TypeRelation<'tcx> for LifetimeIgnoreRelation<'tcx> {
  58         fn tcx(&self) -> TyCtxt<'tcx> {
  59             self.tcx
  60         }
  61
  62         fn param_env(&self) -> ty::ParamEnv<'tcx> {
  63             self.param_env
  64         }
  65
  66         fn tag(&self) -> &'static str {
  67             "librustc_mir::transform::validate"
  68         }
  69
  70         fn a_is_expected(&self) -> bool {
  71             true
  72         }
  73
  74         fn relate_with_variance<T: Relate<'tcx>>(
  75             &mut self,
  76             _: ty::Variance,
  77             a: T,
  78             b: T,
  79         ) -> RelateResult<'tcx, T> {
  80             // Ignore variance, require types to be exactly the same.
  81             self.relate(a, b)
  82         }
  83
  84         fn tys(&mut self, a: Ty<'tcx>, b: Ty<'tcx>) -> RelateResult<'tcx, Ty<'tcx>> {
  85             if a == b {
  86                 // Short-circuit.
  87                 return Ok(a);
  88             }
  89             ty::relate::super_relate_tys(self, a, b)
  90         }
  91
  92         fn regions(
  93             &mut self,
  94             a: ty::Region<'tcx>,
  95             _b: ty::Region<'tcx>,
  96         ) -> RelateResult<'tcx, ty::Region<'tcx>> {
  97             // Ignore regions.
  98             Ok(a)
  99         }
 100
 101         fn consts(
 102             &mut self,
 103             a: &'tcx ty::Const<'tcx>,
 104             b: &'tcx ty::Const<'tcx>,
 105         ) -> RelateResult<'tcx, &'tcx ty::Const<'tcx>> {
 106             ty::relate::super_relate_consts(self, a, b)
 107         }
 108
 109         fn binders<T>(
 110             &mut self,
 111             a: ty::Binder<T>,
 112             b: ty::Binder<T>,
 113         ) -> RelateResult<'tcx, ty::Binder<T>>
 114         where
 115             T: Relate<'tcx>,
 116         {
 117             self.relate(a.skip_binder(), b.skip_binder())?;
 118             Ok(a)
 119         }
 120     }
 121
 122     // Instantiate and run relation.
 123     let mut relator: LifetimeIgnoreRelation<'tcx> = LifetimeIgnoreRelation { tcx: tcx, param_env };
 124     relator.relate(src, dest).is_ok()
 125 }
 126
 127 struct TypeChecker<'a, 'tcx> {
 128     when: &'a str,
 129     source: MirSource<'tcx>,
 130     body: &'a Body<'tcx>,
 131     tcx: TyCtxt<'tcx>,
 132     param_env: ParamEnv<'tcx>,
 133 }
 134
 135 impl<'a, 'tcx> TypeChecker<'a, 'tcx> {
 136     fn fail(&self, location: Location, msg: impl AsRef<str>) {
 137         let span = self.body.source_info(location).span;
 138         // We use `delay_span_bug` as we might see broken MIR when other errors have already
 139         // occurred.
 140         self.tcx.sess.diagnostic().delay_span_bug(
 141             span,
 142             &format!(
 143                 "broken MIR in {:?} ({}) at {:?}:\n{}",
 144                 self.source.instance,
 145                 self.when,
 146                 location,
 147                 msg.as_ref()
 148             ),
 149         );
 150     }
 151
 152     fn check_edge(&self, location: Location, bb: BasicBlock, edge_kind: EdgeKind) {
 153         if let Some(bb) = self.body.basic_blocks().get(bb) {
 154             let src = self.body.basic_blocks().get(location.block).unwrap();
 155             match (src.is_cleanup, bb.is_cleanup, edge_kind) {
 156                 // Non-cleanup blocks can jump to non-cleanup blocks along non-unwind edges
 157                 (false, false, EdgeKind::Normal)
 158                 // Non-cleanup blocks can jump to cleanup blocks along unwind edges
 159                 | (false, true, EdgeKind::Unwind)
 160                 // Cleanup blocks can jump to cleanup blocks along non-unwind edges
 161                 | (true, true, EdgeKind::Normal) => {}
 162                 // All other jumps are invalid
 163                 _ => {
 164                     self.fail(
 165                         location,
 166                         format!(
 167                             "{:?} edge to {:?} violates unwind invariants (cleanup {:?} -> {:?})",
 168                             edge_kind,
 169                             bb,
 170                             src.is_cleanup,
 171                             bb.is_cleanup,
 172                         )
 173                     )
 174                 }
 175             }
 176         } else {
 177             self.fail(location, format!("encountered jump to invalid basic block {:?}", bb))
 178         }
 179     }
 180
 181     /// Check if src can be assigned into dest.
 182     /// This is not precise, it will accept some incorrect assignments.
 183     fn mir_assign_valid_types(&self, src: Ty<'tcx>, dest: Ty<'tcx>) -> bool {
 184         // Fast path before we normalize.
 185         if src == dest {
 186             // Equal types, all is good.
 187             return true;
 188         }
 189         // Normalize projections and things like that.
 190         // FIXME: We need to reveal_all, as some optimizations change types in ways
 191         // that require unfolding opaque types.
 192         let param_env = self.param_env.with_reveal_all_normalized(self.tcx);
 193         let src = self.tcx.normalize_erasing_regions(param_env, src);
 194         let dest = self.tcx.normalize_erasing_regions(param_env, dest);
 195
 196         // Type-changing assignments can happen when subtyping is used. While
 197         // all normal lifetimes are erased, higher-ranked types with their
 198         // late-bound lifetimes are still around and can lead to type
 199         // differences. So we compare ignoring lifetimes.
 200         equal_up_to_regions(self.tcx, param_env, src, dest)
 201     }
 202 }
 203
 204 impl<'a, 'tcx> Visitor<'tcx> for TypeChecker<'a, 'tcx> {
 205     fn visit_operand(&mut self, operand: &Operand<'tcx>, location: Location) {
 206         // `Operand::Copy` is only supposed to be used with `Copy` types.
 207         if let Operand::Copy(place) = operand {
 208             let ty = place.ty(&self.body.local_decls, self.tcx).ty;
 209             let span = self.body.source_info(location).span;
 210
 211             if !ty.is_copy_modulo_regions(self.tcx.at(span), self.param_env) {
 212                 self.fail(location, format!("`Operand::Copy` with non-`Copy` type {}", ty));
 213             }
 214         }
 215
 216         self.super_operand(operand, location);
 217     }
 218
 219     fn visit_statement(&mut self, statement: &Statement<'tcx>, location: Location) {
 220         match &statement.kind {
 221             StatementKind::Assign(box (dest, rvalue)) => {
 222                 // LHS and RHS of the assignment must have the same type.
 223                 let left_ty = dest.ty(&self.body.local_decls, self.tcx).ty;
 224                 let right_ty = rvalue.ty(&self.body.local_decls, self.tcx);
 225                 if !self.mir_assign_valid_types(right_ty, left_ty) {
 226                     self.fail(
 227                         location,
 228                         format!(
 229                             "encountered `Assign` statement with incompatible types:\n\
 230                             left-hand side has type: {}\n\
 231                             right-hand side has type: {}",
 232                             left_ty, right_ty,
 233                         ),
 234                     );
 235                 }
 236                 // The sides of an assignment must not alias. Currently this just checks whether the places
 237                 // are identical.
 238                 match rvalue {
 239                     Rvalue::Use(Operand::Copy(src) | Operand::Move(src)) => {
 240                         if dest == src {
 241                             self.fail(
 242                                 location,
 243                                 "encountered `Assign` statement with overlapping memory",
 244                             );
 245                         }
 246                     }
 247                     _ => {}
 248                 }
 249             }
 250             _ => {}
 251         }
 252     }
 253
 254     fn visit_terminator(&mut self, terminator: &Terminator<'tcx>, location: Location) {
 255         match &terminator.kind {
 256             TerminatorKind::Goto { target } => {
 257                 self.check_edge(location, *target, EdgeKind::Normal);
 258             }
 259             TerminatorKind::SwitchInt { targets, values, switch_ty, discr } => {
 260                 let ty = discr.ty(&self.body.local_decls, self.tcx);
 261                 if ty != *switch_ty {
 262                     self.fail(
 263                         location,
 264                         format!(
 265                             "encountered `SwitchInt` terminator with type mismatch: {:?} != {:?}",
 266                             ty, switch_ty,
 267                         ),
 268                     );
 269                 }
 270                 if targets.len() != values.len() + 1 {
 271                     self.fail(
 272                         location,
 273                         format!(
 274                             "encountered `SwitchInt` terminator with {} values, but {} targets (should be values+1)",
 275                             values.len(),
 276                             targets.len(),
 277                         ),
 278                     );
 279                 }
 280                 for target in targets {
 281                     self.check_edge(location, *target, EdgeKind::Normal);
 282                 }
 283             }
 284             TerminatorKind::Drop { target, unwind, .. } => {
 285                 self.check_edge(location, *target, EdgeKind::Normal);
 286                 if let Some(unwind) = unwind {
 287                     self.check_edge(location, *unwind, EdgeKind::Unwind);
 288                 }
 289             }
 290             TerminatorKind::DropAndReplace { target, unwind, .. } => {
 291                 self.check_edge(location, *target, EdgeKind::Normal);
 292                 if let Some(unwind) = unwind {
 293                     self.check_edge(location, *unwind, EdgeKind::Unwind);
 294                 }
 295             }
 296             TerminatorKind::Call { func, destination, cleanup, .. } => {
 297                 let func_ty = func.ty(&self.body.local_decls, self.tcx);
 298                 match func_ty.kind {
 299                     ty::FnPtr(..) | ty::FnDef(..) => {}
 300                     _ => self.fail(
 301                         location,
 302                         format!("encountered non-callable type {} in `Call` terminator", func_ty),
 303                     ),
 304                 }
 305                 if let Some((_, target)) = destination {
 306                     self.check_edge(location, *target, EdgeKind::Normal);
 307                 }
 308                 if let Some(cleanup) = cleanup {
 309                     self.check_edge(location, *cleanup, EdgeKind::Unwind);
 310                 }
 311             }
 312             TerminatorKind::Assert { cond, target, cleanup, .. } => {
 313                 let cond_ty = cond.ty(&self.body.local_decls, self.tcx);
 314                 if cond_ty != self.tcx.types.bool {
 315                     self.fail(
 316                         location,
 317                         format!(
 318                             "encountered non-boolean condition of type {} in `Assert` terminator",
 319                             cond_ty
 320                         ),
 321                     );
 322                 }
 323                 self.check_edge(location, *target, EdgeKind::Normal);
 324                 if let Some(cleanup) = cleanup {
 325                     self.check_edge(location, *cleanup, EdgeKind::Unwind);
 326                 }
 327             }
 328             TerminatorKind::Yield { resume, drop, .. } => {
 329                 self.check_edge(location, *resume, EdgeKind::Normal);
 330                 if let Some(drop) = drop {
 331                     self.check_edge(location, *drop, EdgeKind::Normal);
 332                 }
 333             }
 334             TerminatorKind::FalseEdge { real_target, imaginary_target } => {
 335                 self.check_edge(location, *real_target, EdgeKind::Normal);
 336                 self.check_edge(location, *imaginary_target, EdgeKind::Normal);
 337             }
 338             TerminatorKind::FalseUnwind { real_target, unwind } => {
 339                 self.check_edge(location, *real_target, EdgeKind::Normal);
 340                 if let Some(unwind) = unwind {
 341                     self.check_edge(location, *unwind, EdgeKind::Unwind);
 342                 }
 343             }
 344             TerminatorKind::InlineAsm { destination, .. } => {
 345                 if let Some(destination) = destination {
 346                     self.check_edge(location, *destination, EdgeKind::Normal);
 347                 }
 348             }
 349             // Nothing to validate for these.
 350             TerminatorKind::Resume
 351             | TerminatorKind::Abort
 352             | TerminatorKind::Return
 353             | TerminatorKind::Unreachable
 354             | TerminatorKind::GeneratorDrop => {}
 355         }
 356     }
 357 }