src/tools/rust-analyzer/crates/hir-ty/src/mir/lower/pattern_matching.rs

   1 //! MIR lowering for patterns
   2
   3 use hir_def::{hir::LiteralOrConst, resolver::HasResolver, AssocItemId};
   4
   5 use crate::BindingMode;
   6
   7 use super::*;
   8
   9 macro_rules! not_supported {
  10     ($x: expr) => {
  11         return Err(MirLowerError::NotSupported(format!($x)))
  12     };
  13 }
  14
  15 pub(super) enum AdtPatternShape<'a> {
  16     Tuple { args: &'a [PatId], ellipsis: Option<usize> },
  17     Record { args: &'a [RecordFieldPat] },
  18     Unit,
  19 }
  20
  21 /// We need to do pattern matching in two phases: One to check if the pattern matches, and one to fill the bindings
  22 /// of patterns. This is necessary to prevent double moves and similar problems. For example:
  23 /// ```ignore
  24 /// struct X;
  25 /// match (X, 3) {
  26 ///     (b, 2) | (b, 3) => {},
  27 ///     _ => {}
  28 /// }
  29 /// ```
  30 /// If we do everything in one pass, we will move `X` to the first `b`, then we see that the second field of tuple
  31 /// doesn't match and we should move the `X` to the second `b` (which here is the same thing, but doesn't need to be) and
  32 /// it might even doesn't match the second pattern and we may want to not move `X` at all.
  33 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
  34 enum MatchingMode {
  35     /// Check that if this pattern matches
  36     Check,
  37     /// Assume that this pattern matches, fill bindings
  38     Bind,
  39 }
  40
  41 impl MirLowerCtx<'_> {
  42     /// It gets a `current` unterminated block, appends some statements and possibly a terminator to it to check if
  43     /// the pattern matches and write bindings, and returns two unterminated blocks, one for the matched path (which
  44     /// can be the `current` block) and one for the mismatched path. If the input pattern is irrefutable, the
  45     /// mismatched path block is `None`.
  46     ///
  47     /// By default, it will create a new block for mismatched path. If you already have one, you can provide it with
  48     /// `current_else` argument to save an unnecessary jump. If `current_else` isn't `None`, the result mismatched path
  49     /// wouldn't be `None` as well. Note that this function will add jumps to the beginning of the `current_else` block,
  50     /// so it should be an empty block.
  51     pub(super) fn pattern_match(
  52         &mut self,
  53         current: BasicBlockId,
  54         current_else: Option<BasicBlockId>,
  55         cond_place: Place,
  56         pattern: PatId,
  57     ) -> Result<(BasicBlockId, Option<BasicBlockId>)> {
  58         let (current, current_else) = self.pattern_match_inner(
  59             current,
  60             current_else,
  61             cond_place.clone(),
  62             pattern,
  63             MatchingMode::Check,
  64         )?;
  65         let (current, current_else) = self.pattern_match_inner(
  66             current,
  67             current_else,
  68             cond_place,
  69             pattern,
  70             MatchingMode::Bind,
  71         )?;
  72         Ok((current, current_else))
  73     }
  74
  75     fn pattern_match_inner(
  76         &mut self,
  77         mut current: BasicBlockId,
  78         mut current_else: Option<BasicBlockId>,
  79         mut cond_place: Place,
  80         pattern: PatId,
  81         mode: MatchingMode,
  82     ) -> Result<(BasicBlockId, Option<BasicBlockId>)> {
  83         let cnt = self.infer.pat_adjustments.get(&pattern).map(|x| x.len()).unwrap_or_default();
  84         cond_place.projection = self.result.projection_store.intern(
  85             cond_place
  86                 .projection
  87                 .lookup(&self.result.projection_store)
  88                 .iter()
  89                 .cloned()
  90                 .chain((0..cnt).map(|_| ProjectionElem::Deref))
  91                 .collect::<Vec<_>>()
  92                 .into(),
  93         );
  94         Ok(match &self.body.pats[pattern] {
  95             Pat::Missing => return Err(MirLowerError::IncompletePattern),
  96             Pat::Wild => (current, current_else),
  97             Pat::Tuple { args, ellipsis } => {
  98                 let subst = match self.infer[pattern].kind(Interner) {
  99                     TyKind::Tuple(_, s) => s,
 100                     _ => {
 101                         return Err(MirLowerError::TypeError(
 102                             "non tuple type matched with tuple pattern",
 103                         ))
 104                     }
 105                 };
 106                 self.pattern_match_tuple_like(
 107                     current,
 108                     current_else,
 109                     args,
 110                     *ellipsis,
 111                     (0..subst.len(Interner)).map(|i| PlaceElem::TupleOrClosureField(i)),
 112                     &(&mut cond_place),
 113                     mode,
 114                 )?
 115             }
 116             Pat::Or(pats) => {
 117                 let then_target = self.new_basic_block();
 118                 let mut finished = false;
 119                 for pat in &**pats {
 120                     let (mut next, next_else) = self.pattern_match_inner(
 121                         current,
 122                         None,
 123                         (&mut cond_place).clone(),
 124                         *pat,
 125                         MatchingMode::Check,
 126                     )?;
 127                     if mode == MatchingMode::Bind {
 128                         (next, _) = self.pattern_match_inner(
 129                             next,
 130                             None,
 131                             (&mut cond_place).clone(),
 132                             *pat,
 133                             MatchingMode::Bind,
 134                         )?;
 135                     }
 136                     self.set_goto(next, then_target, pattern.into());
 137                     match next_else {
 138                         Some(t) => {
 139                             current = t;
 140                         }
 141                         None => {
 142                             finished = true;
 143                             break;
 144                         }
 145                     }
 146                 }
 147                 if !finished {
 148                     if mode == MatchingMode::Bind {
 149                         self.set_terminator(current, TerminatorKind::Unreachable, pattern.into());
 150                     } else {
 151                         let ce = *current_else.get_or_insert_with(|| self.new_basic_block());
 152                         self.set_goto(current, ce, pattern.into());
 153                     }
 154                 }
 155                 (then_target, current_else)
 156             }
 157             Pat::Record { args, .. } => {
 158                 let Some(variant) = self.infer.variant_resolution_for_pat(pattern) else {
 159                     not_supported!("unresolved variant for record");
 160                 };
 161                 self.pattern_matching_variant(
 162                     cond_place,
 163                     variant,
 164                     current,
 165                     pattern.into(),
 166                     current_else,
 167                     AdtPatternShape::Record { args: &*args },
 168                     mode,
 169                 )?
 170             }
 171             Pat::Range { start, end } => {
 172                 let mut add_check = |l: &LiteralOrConst, binop| -> Result<()> {
 173                     let lv =
 174                         self.lower_literal_or_const_to_operand(self.infer[pattern].clone(), l)?;
 175                     let else_target = *current_else.get_or_insert_with(|| self.new_basic_block());
 176                     let next = self.new_basic_block();
 177                     let discr: Place =
 178                         self.temp(TyBuilder::bool(), current, pattern.into())?.into();
 179                     self.push_assignment(
 180                         current,
 181                         discr.clone(),
 182                         Rvalue::CheckedBinaryOp(
 183                             binop,
 184                             lv,
 185                             Operand::Copy((&mut cond_place).clone()),
 186                         ),
 187                         pattern.into(),
 188                     );
 189                     let discr = Operand::Copy(discr);
 190                     self.set_terminator(
 191                         current,
 192                         TerminatorKind::SwitchInt {
 193                             discr,
 194                             targets: SwitchTargets::static_if(1, next, else_target),
 195                         },
 196                         pattern.into(),
 197                     );
 198                     current = next;
 199                     Ok(())
 200                 };
 201                 if mode == MatchingMode::Check {
 202                     if let Some(start) = start {
 203                         add_check(start, BinOp::Le)?;
 204                     }
 205                     if let Some(end) = end {
 206                         add_check(end, BinOp::Ge)?;
 207                     }
 208                 }
 209                 (current, current_else)
 210             }
 211             Pat::Slice { prefix, slice, suffix } => {
 212                 if mode == MatchingMode::Check {
 213                     // emit runtime length check for slice
 214                     if let TyKind::Slice(_) = self.infer[pattern].kind(Interner) {
 215                         let pattern_len = prefix.len() + suffix.len();
 216                         let place_len: Place =
 217                             self.temp(TyBuilder::usize(), current, pattern.into())?.into();
 218                         self.push_assignment(
 219                             current,
 220                             place_len.clone(),
 221                             Rvalue::Len((&mut cond_place).clone()),
 222                             pattern.into(),
 223                         );
 224                         let else_target =
 225                             *current_else.get_or_insert_with(|| self.new_basic_block());
 226                         let next = self.new_basic_block();
 227                         if slice.is_none() {
 228                             self.set_terminator(
 229                                 current,
 230                                 TerminatorKind::SwitchInt {
 231                                     discr: Operand::Copy(place_len),
 232                                     targets: SwitchTargets::static_if(
 233                                         pattern_len as u128,
 234                                         next,
 235                                         else_target,
 236                                     ),
 237                                 },
 238                                 pattern.into(),
 239                             );
 240                         } else {
 241                             let c = Operand::from_concrete_const(
 242                                 pattern_len.to_le_bytes().to_vec(),
 243                                 MemoryMap::default(),
 244                                 TyBuilder::usize(),
 245                             );
 246                             let discr: Place =
 247                                 self.temp(TyBuilder::bool(), current, pattern.into())?.into();
 248                             self.push_assignment(
 249                                 current,
 250                                 discr.clone(),
 251                                 Rvalue::CheckedBinaryOp(BinOp::Le, c, Operand::Copy(place_len)),
 252                                 pattern.into(),
 253                             );
 254                             let discr = Operand::Copy(discr);
 255                             self.set_terminator(
 256                                 current,
 257                                 TerminatorKind::SwitchInt {
 258                                     discr,
 259                                     targets: SwitchTargets::static_if(1, next, else_target),
 260                                 },
 261                                 pattern.into(),
 262                             );
 263                         }
 264                         current = next;
 265                     }
 266                 }
 267                 for (i, &pat) in prefix.iter().enumerate() {
 268                     let next_place = (&mut cond_place).project(
 269                         ProjectionElem::ConstantIndex { offset: i as u64, from_end: false },
 270                         &mut self.result.projection_store,
 271                     );
 272                     (current, current_else) =
 273                         self.pattern_match_inner(current, current_else, next_place, pat, mode)?;
 274                 }
 275                 if let Some(slice) = slice {
 276                     if mode == MatchingMode::Bind {
 277                         if let Pat::Bind { id, subpat: _ } = self.body[*slice] {
 278                             let next_place = (&mut cond_place).project(
 279                                 ProjectionElem::Subslice {
 280                                     from: prefix.len() as u64,
 281                                     to: suffix.len() as u64,
 282                                 },
 283                                 &mut self.result.projection_store,
 284                             );
 285                             (current, current_else) = self.pattern_match_binding(
 286                                 id,
 287                                 next_place,
 288                                 (*slice).into(),
 289                                 current,
 290                                 current_else,
 291                             )?;
 292                         }
 293                     }
 294                 }
 295                 for (i, &pat) in suffix.iter().enumerate() {
 296                     let next_place = (&mut cond_place).project(
 297                         ProjectionElem::ConstantIndex { offset: i as u64, from_end: true },
 298                         &mut self.result.projection_store,
 299                     );
 300                     (current, current_else) =
 301                         self.pattern_match_inner(current, current_else, next_place, pat, mode)?;
 302                 }
 303                 (current, current_else)
 304             }
 305             Pat::Path(p) => match self.infer.variant_resolution_for_pat(pattern) {
 306                 Some(variant) => self.pattern_matching_variant(
 307                     cond_place,
 308                     variant,
 309                     current,
 310                     pattern.into(),
 311                     current_else,
 312                     AdtPatternShape::Unit,
 313                     mode,
 314                 )?,
 315                 None => {
 316                     // The path is not a variant, so it is a const
 317                     if mode != MatchingMode::Check {
 318                         // A const don't bind anything. Only needs check.
 319                         return Ok((current, current_else));
 320                     }
 321                     let unresolved_name = || MirLowerError::unresolved_path(self.db, p);
 322                     let resolver = self.owner.resolver(self.db.upcast());
 323                     let pr = resolver
 324                         .resolve_path_in_value_ns(self.db.upcast(), p)
 325                         .ok_or_else(unresolved_name)?;
 326                     let (c, subst) = 'b: {
 327                         if let Some(x) = self.infer.assoc_resolutions_for_pat(pattern) {
 328                             if let AssocItemId::ConstId(c) = x.0 {
 329                                 break 'b (c, x.1);
 330                             }
 331                         }
 332                         if let ResolveValueResult::ValueNs(v, _) = pr {
 333                             if let ValueNs::ConstId(c) = v {
 334                                 break 'b (c, Substitution::empty(Interner));
 335                             }
 336                         }
 337                         not_supported!("path in pattern position that is not const or variant")
 338                     };
 339                     let tmp: Place =
 340                         self.temp(self.infer[pattern].clone(), current, pattern.into())?.into();
 341                     let span = pattern.into();
 342                     self.lower_const(
 343                         c.into(),
 344                         current,
 345                         tmp.clone(),
 346                         subst,
 347                         span,
 348                         self.infer[pattern].clone(),
 349                     )?;
 350                     let tmp2: Place = self.temp(TyBuilder::bool(), current, pattern.into())?.into();
 351                     self.push_assignment(
 352                         current,
 353                         tmp2.clone(),
 354                         Rvalue::CheckedBinaryOp(
 355                             BinOp::Eq,
 356                             Operand::Copy(tmp),
 357                             Operand::Copy(cond_place),
 358                         ),
 359                         span,
 360                     );
 361                     let next = self.new_basic_block();
 362                     let else_target = current_else.unwrap_or_else(|| self.new_basic_block());
 363                     self.set_terminator(
 364                         current,
 365                         TerminatorKind::SwitchInt {
 366                             discr: Operand::Copy(tmp2),
 367                             targets: SwitchTargets::static_if(1, next, else_target),
 368                         },
 369                         span,
 370                     );
 371                     (next, Some(else_target))
 372                 }
 373             },
 374             Pat::Lit(l) => match &self.body.exprs[*l] {
 375                 Expr::Literal(l) => {
 376                     if mode == MatchingMode::Check {
 377                         let c = self.lower_literal_to_operand(self.infer[pattern].clone(), l)?;
 378                         self.pattern_match_const(current_else, current, c, cond_place, pattern)?
 379                     } else {
 380                         (current, current_else)
 381                     }
 382                 }
 383                 _ => not_supported!("expression path literal"),
 384             },
 385             Pat::Bind { id, subpat } => {
 386                 if let Some(subpat) = subpat {
 387                     (current, current_else) = self.pattern_match_inner(
 388                         current,
 389                         current_else,
 390                         (&mut cond_place).clone(),
 391                         *subpat,
 392                         mode,
 393                     )?
 394                 }
 395                 if mode == MatchingMode::Bind {
 396                     self.pattern_match_binding(
 397                         *id,
 398                         cond_place,
 399                         pattern.into(),
 400                         current,
 401                         current_else,
 402                     )?
 403                 } else {
 404                     (current, current_else)
 405                 }
 406             }
 407             Pat::TupleStruct { path: _, args, ellipsis } => {
 408                 let Some(variant) = self.infer.variant_resolution_for_pat(pattern) else {
 409                     not_supported!("unresolved variant");
 410                 };
 411                 self.pattern_matching_variant(
 412                     cond_place,
 413                     variant,
 414                     current,
 415                     pattern.into(),
 416                     current_else,
 417                     AdtPatternShape::Tuple { args, ellipsis: *ellipsis },
 418                     mode,
 419                 )?
 420             }
 421             Pat::Ref { pat, mutability: _ } => {
 422                 let cond_place =
 423                     cond_place.project(ProjectionElem::Deref, &mut self.result.projection_store);
 424                 self.pattern_match_inner(current, current_else, cond_place, *pat, mode)?
 425             }
 426             Pat::Box { .. } => not_supported!("box pattern"),
 427             Pat::ConstBlock(_) => not_supported!("const block pattern"),
 428         })
 429     }
 430
 431     fn pattern_match_binding(
 432         &mut self,
 433         id: BindingId,
 434         cond_place: Place,
 435         span: MirSpan,
 436         current: BasicBlockId,
 437         current_else: Option<BasicBlockId>,
 438     ) -> Result<(BasicBlockId, Option<BasicBlockId>)> {
 439         let target_place = self.binding_local(id)?;
 440         let mode = self.infer.binding_modes[id];
 441         self.push_storage_live(id, current)?;
 442         self.push_assignment(
 443             current,
 444             target_place.into(),
 445             match mode {
 446                 BindingMode::Move => Operand::Copy(cond_place).into(),
 447                 BindingMode::Ref(Mutability::Not) => Rvalue::Ref(BorrowKind::Shared, cond_place),
 448                 BindingMode::Ref(Mutability::Mut) => {
 449                     Rvalue::Ref(BorrowKind::Mut { allow_two_phase_borrow: false }, cond_place)
 450                 }
 451             },
 452             span,
 453         );
 454         Ok((current, current_else))
 455     }
 456
 457     fn pattern_match_const(
 458         &mut self,
 459         current_else: Option<BasicBlockId>,
 460         current: BasicBlockId,
 461         c: Operand,
 462         cond_place: Place,
 463         pattern: Idx<Pat>,
 464     ) -> Result<(BasicBlockId, Option<BasicBlockId>)> {
 465         let then_target = self.new_basic_block();
 466         let else_target = current_else.unwrap_or_else(|| self.new_basic_block());
 467         let discr: Place = self.temp(TyBuilder::bool(), current, pattern.into())?.into();
 468         self.push_assignment(
 469             current,
 470             discr.clone(),
 471             Rvalue::CheckedBinaryOp(BinOp::Eq, c, Operand::Copy(cond_place)),
 472             pattern.into(),
 473         );
 474         let discr = Operand::Copy(discr);
 475         self.set_terminator(
 476             current,
 477             TerminatorKind::SwitchInt {
 478                 discr,
 479                 targets: SwitchTargets::static_if(1, then_target, else_target),
 480             },
 481             pattern.into(),
 482         );
 483         Ok((then_target, Some(else_target)))
 484     }
 485
 486     fn pattern_matching_variant(
 487         &mut self,
 488         cond_place: Place,
 489         variant: VariantId,
 490         mut current: BasicBlockId,
 491         span: MirSpan,
 492         mut current_else: Option<BasicBlockId>,
 493         shape: AdtPatternShape<'_>,
 494         mode: MatchingMode,
 495     ) -> Result<(BasicBlockId, Option<BasicBlockId>)> {
 496         Ok(match variant {
 497             VariantId::EnumVariantId(v) => {
 498                 if mode == MatchingMode::Check {
 499                     let e = self.const_eval_discriminant(v)? as u128;
 500                     let tmp = self.discr_temp_place(current);
 501                     self.push_assignment(
 502                         current,
 503                         tmp.clone(),
 504                         Rvalue::Discriminant(cond_place.clone()),
 505                         span,
 506                     );
 507                     let next = self.new_basic_block();
 508                     let else_target = current_else.get_or_insert_with(|| self.new_basic_block());
 509                     self.set_terminator(
 510                         current,
 511                         TerminatorKind::SwitchInt {
 512                             discr: Operand::Copy(tmp),
 513                             targets: SwitchTargets::static_if(e, next, *else_target),
 514                         },
 515                         span,
 516                     );
 517                     current = next;
 518                 }
 519                 let enum_data = self.db.enum_data(v.parent);
 520                 self.pattern_matching_variant_fields(
 521                     shape,
 522                     &enum_data.variants[v.local_id].variant_data,
 523                     variant,
 524                     current,
 525                     current_else,
 526                     &cond_place,
 527                     mode,
 528                 )?
 529             }
 530             VariantId::StructId(s) => {
 531                 let struct_data = self.db.struct_data(s);
 532                 self.pattern_matching_variant_fields(
 533                     shape,
 534                     &struct_data.variant_data,
 535                     variant,
 536                     current,
 537                     current_else,
 538                     &cond_place,
 539                     mode,
 540                 )?
 541             }
 542             VariantId::UnionId(_) => {
 543                 return Err(MirLowerError::TypeError("pattern matching on union"))
 544             }
 545         })
 546     }
 547
 548     fn pattern_matching_variant_fields(
 549         &mut self,
 550         shape: AdtPatternShape<'_>,
 551         variant_data: &VariantData,
 552         v: VariantId,
 553         current: BasicBlockId,
 554         current_else: Option<BasicBlockId>,
 555         cond_place: &Place,
 556         mode: MatchingMode,
 557     ) -> Result<(BasicBlockId, Option<BasicBlockId>)> {
 558         Ok(match shape {
 559             AdtPatternShape::Record { args } => {
 560                 let it = args
 561                     .iter()
 562                     .map(|x| {
 563                         let field_id =
 564                             variant_data.field(&x.name).ok_or(MirLowerError::UnresolvedField)?;
 565                         Ok((
 566                             PlaceElem::Field(FieldId { parent: v.into(), local_id: field_id }),
 567                             x.pat,
 568                         ))
 569                     })
 570                     .collect::<Result<Vec<_>>>()?;
 571                 self.pattern_match_adt(current, current_else, it.into_iter(), cond_place, mode)?
 572             }
 573             AdtPatternShape::Tuple { args, ellipsis } => {
 574                 let fields = variant_data
 575                     .fields()
 576                     .iter()
 577                     .map(|(x, _)| PlaceElem::Field(FieldId { parent: v.into(), local_id: x }));
 578                 self.pattern_match_tuple_like(
 579                     current,
 580                     current_else,
 581                     args,
 582                     ellipsis,
 583                     fields,
 584                     cond_place,
 585                     mode,
 586                 )?
 587             }
 588             AdtPatternShape::Unit => (current, current_else),
 589         })
 590     }
 591
 592     fn pattern_match_adt(
 593         &mut self,
 594         mut current: BasicBlockId,
 595         mut current_else: Option<BasicBlockId>,
 596         args: impl Iterator<Item = (PlaceElem, PatId)>,
 597         cond_place: &Place,
 598         mode: MatchingMode,
 599     ) -> Result<(BasicBlockId, Option<BasicBlockId>)> {
 600         for (proj, arg) in args {
 601             let cond_place = cond_place.project(proj, &mut self.result.projection_store);
 602             (current, current_else) =
 603                 self.pattern_match_inner(current, current_else, cond_place, arg, mode)?;
 604         }
 605         Ok((current, current_else))
 606     }
 607
 608     fn pattern_match_tuple_like(
 609         &mut self,
 610         current: BasicBlockId,
 611         current_else: Option<BasicBlockId>,
 612         args: &[PatId],
 613         ellipsis: Option<usize>,
 614         fields: impl DoubleEndedIterator<Item = PlaceElem> + Clone,
 615         cond_place: &Place,
 616         mode: MatchingMode,
 617     ) -> Result<(BasicBlockId, Option<BasicBlockId>)> {
 618         let (al, ar) = args.split_at(ellipsis.unwrap_or(args.len()));
 619         let it = al
 620             .iter()
 621             .zip(fields.clone())
 622             .chain(ar.iter().rev().zip(fields.rev()))
 623             .map(|(x, y)| (y, *x));
 624         self.pattern_match_adt(current, current_else, it, cond_place, mode)
 625     }
 626 }