crates/ide_ssr/src/matching.rs

   1 //! This module is responsible for matching a search pattern against a node in the AST. In the
   2 //! process of matching, placeholder values are recorded.
   3
   4 use crate::{
   5     parsing::{Constraint, NodeKind, Placeholder, Var},
   6     resolving::{ResolvedPattern, ResolvedRule, UfcsCallInfo},
   7     SsrMatches,
   8 };
   9 use hir::Semantics;
  10 use ide_db::base_db::FileRange;
  11 use rustc_hash::FxHashMap;
  12 use std::{cell::Cell, iter::Peekable};
  13 use syntax::{ast, SyntaxElement, SyntaxElementChildren, SyntaxKind, SyntaxNode, SyntaxToken};
  14 use syntax::{
  15     ast::{AstNode, AstToken},
  16     SmolStr,
  17 };
  18
  19 // Creates a match error. If we're currently attempting to match some code that we thought we were
  20 // going to match, as indicated by the --debug-snippet flag, then populate the reason field.
  21 macro_rules! match_error {
  22     ($e:expr) => {{
  23             MatchFailed {
  24                 reason: if recording_match_fail_reasons() {
  25                     Some(format!("{}", $e))
  26                 } else {
  27                     None
  28                 }
  29             }
  30     }};
  31     ($fmt:expr, $($arg:tt)+) => {{
  32         MatchFailed {
  33             reason: if recording_match_fail_reasons() {
  34                 Some(format!($fmt, $($arg)+))
  35             } else {
  36                 None
  37             }
  38         }
  39     }};
  40 }
  41
  42 // Fails the current match attempt, recording the supplied reason if we're recording match fail reasons.
  43 macro_rules! fail_match {
  44     ($($args:tt)*) => {return Err(match_error!($($args)*))};
  45 }
  46
  47 /// Information about a match that was found.
  48 #[derive(Debug)]
  49 pub struct Match {
  50     pub(crate) range: FileRange,
  51     pub(crate) matched_node: SyntaxNode,
  52     pub(crate) placeholder_values: FxHashMap<Var, PlaceholderMatch>,
  53     pub(crate) ignored_comments: Vec<ast::Comment>,
  54     pub(crate) rule_index: usize,
  55     /// The depth of matched_node.
  56     pub(crate) depth: usize,
  57     // Each path in the template rendered for the module in which the match was found.
  58     pub(crate) rendered_template_paths: FxHashMap<SyntaxNode, hir::ModPath>,
  59 }
  60
  61 /// Information about a placeholder bound in a match.
  62 #[derive(Debug)]
  63 pub(crate) struct PlaceholderMatch {
  64     pub(crate) range: FileRange,
  65     /// More matches, found within `node`.
  66     pub(crate) inner_matches: SsrMatches,
  67     /// How many times the code that the placeholder matched needed to be dereferenced. Will only be
  68     /// non-zero if the placeholder matched to the receiver of a method call.
  69     pub(crate) autoderef_count: usize,
  70     pub(crate) autoref_kind: ast::SelfParamKind,
  71 }
  72
  73 #[derive(Debug)]
  74 pub(crate) struct MatchFailureReason {
  75     pub(crate) reason: String,
  76 }
  77
  78 /// An "error" indicating that matching failed. Use the fail_match! macro to create and return this.
  79 #[derive(Clone)]
  80 pub(crate) struct MatchFailed {
  81     /// The reason why we failed to match. Only present when debug_active true in call to
  82     /// `get_match`.
  83     pub(crate) reason: Option<String>,
  84 }
  85
  86 /// Checks if `code` matches the search pattern found in `search_scope`, returning information about
  87 /// the match, if it does. Since we only do matching in this module and searching is done by the
  88 /// parent module, we don't populate nested matches.
  89 pub(crate) fn get_match(
  90     debug_active: bool,
  91     rule: &ResolvedRule,
  92     code: &SyntaxNode,
  93     restrict_range: &Option<FileRange>,
  94     sema: &Semantics<ide_db::RootDatabase>,
  95 ) -> Result<Match, MatchFailed> {
  96     record_match_fails_reasons_scope(debug_active, || {
  97         Matcher::try_match(rule, code, restrict_range, sema)
  98     })
  99 }
 100
 101 /// Checks if our search pattern matches a particular node of the AST.
 102 struct Matcher<'db, 'sema> {
 103     sema: &'sema Semantics<'db, ide_db::RootDatabase>,
 104     /// If any placeholders come from anywhere outside of this range, then the match will be
 105     /// rejected.
 106     restrict_range: Option<FileRange>,
 107     rule: &'sema ResolvedRule,
 108 }
 109
 110 /// Which phase of matching we're currently performing. We do two phases because most attempted
 111 /// matches will fail and it means we can defer more expensive checks to the second phase.
 112 enum Phase<'a> {
 113     /// On the first phase, we perform cheap checks. No state is mutated and nothing is recorded.
 114     First,
 115     /// On the second phase, we construct the `Match`. Things like what placeholders bind to is
 116     /// recorded.
 117     Second(&'a mut Match),
 118 }
 119
 120 impl<'db, 'sema> Matcher<'db, 'sema> {
 121     fn try_match(
 122         rule: &ResolvedRule,
 123         code: &SyntaxNode,
 124         restrict_range: &Option<FileRange>,
 125         sema: &'sema Semantics<'db, ide_db::RootDatabase>,
 126     ) -> Result<Match, MatchFailed> {
 127         let match_state = Matcher { sema, restrict_range: *restrict_range, rule };
 128         // First pass at matching, where we check that node types and idents match.
 129         match_state.attempt_match_node(&mut Phase::First, &rule.pattern.node, code)?;
 130         match_state.validate_range(&sema.original_range(code))?;
 131         let mut the_match = Match {
 132             range: sema.original_range(code),
 133             matched_node: code.clone(),
 134             placeholder_values: FxHashMap::default(),
 135             ignored_comments: Vec::new(),
 136             rule_index: rule.index,
 137             depth: 0,
 138             rendered_template_paths: FxHashMap::default(),
 139         };
 140         // Second matching pass, where we record placeholder matches, ignored comments and maybe do
 141         // any other more expensive checks that we didn't want to do on the first pass.
 142         match_state.attempt_match_node(
 143             &mut Phase::Second(&mut the_match),
 144             &rule.pattern.node,
 145             code,
 146         )?;
 147         the_match.depth = sema.ancestors_with_macros(the_match.matched_node.clone()).count();
 148         if let Some(template) = &rule.template {
 149             the_match.render_template_paths(template, sema)?;
 150         }
 151         Ok(the_match)
 152     }
 153
 154     /// Checks that `range` is within the permitted range if any. This is applicable when we're
 155     /// processing a macro expansion and we want to fail the match if we're working with a node that
 156     /// didn't originate from the token tree of the macro call.
 157     fn validate_range(&self, range: &FileRange) -> Result<(), MatchFailed> {
 158         if let Some(restrict_range) = &self.restrict_range {
 159             if restrict_range.file_id != range.file_id
 160                 || !restrict_range.range.contains_range(range.range)
 161             {
 162                 fail_match!("Node originated from a macro");
 163             }
 164         }
 165         Ok(())
 166     }
 167
 168     fn attempt_match_node(
 169         &self,
 170         phase: &mut Phase,
 171         pattern: &SyntaxNode,
 172         code: &SyntaxNode,
 173     ) -> Result<(), MatchFailed> {
 174         // Handle placeholders.
 175         if let Some(placeholder) = self.get_placeholder_for_node(pattern) {
 176             for constraint in &placeholder.constraints {
 177                 self.check_constraint(constraint, code)?;
 178             }
 179             if let Phase::Second(matches_out) = phase {
 180                 let original_range = self.sema.original_range(code);
 181                 // We validated the range for the node when we started the match, so the placeholder
 182                 // probably can't fail range validation, but just to be safe...
 183                 self.validate_range(&original_range)?;
 184                 matches_out.placeholder_values.insert(
 185                     placeholder.ident.clone(),
 186                     PlaceholderMatch::from_range(original_range),
 187                 );
 188             }
 189             return Ok(());
 190         }
 191         // We allow a UFCS call to match a method call, provided they resolve to the same function.
 192         if let Some(pattern_ufcs) = self.rule.pattern.ufcs_function_calls.get(pattern) {
 193             if let Some(code) = ast::MethodCallExpr::cast(code.clone()) {
 194                 return self.attempt_match_ufcs_to_method_call(phase, pattern_ufcs, &code);
 195             }
 196             if let Some(code) = ast::CallExpr::cast(code.clone()) {
 197                 return self.attempt_match_ufcs_to_ufcs(phase, pattern_ufcs, &code);
 198             }
 199         }
 200         if pattern.kind() != code.kind() {
 201             fail_match!(
 202                 "Pattern had `{}` ({:?}), code had `{}` ({:?})",
 203                 pattern.text(),
 204                 pattern.kind(),
 205                 code.text(),
 206                 code.kind()
 207             );
 208         }
 209         // Some kinds of nodes have special handling. For everything else, we fall back to default
 210         // matching.
 211         match code.kind() {
 212             SyntaxKind::RECORD_EXPR_FIELD_LIST => {
 213                 self.attempt_match_record_field_list(phase, pattern, code)
 214             }
 215             SyntaxKind::TOKEN_TREE => self.attempt_match_token_tree(phase, pattern, code),
 216             SyntaxKind::PATH => self.attempt_match_path(phase, pattern, code),
 217             _ => self.attempt_match_node_children(phase, pattern, code),
 218         }
 219     }
 220
 221     fn attempt_match_node_children(
 222         &self,
 223         phase: &mut Phase,
 224         pattern: &SyntaxNode,
 225         code: &SyntaxNode,
 226     ) -> Result<(), MatchFailed> {
 227         self.attempt_match_sequences(
 228             phase,
 229             PatternIterator::new(pattern),
 230             code.children_with_tokens(),
 231         )
 232     }
 233
 234     fn attempt_match_sequences(
 235         &self,
 236         phase: &mut Phase,
 237         pattern_it: PatternIterator,
 238         mut code_it: SyntaxElementChildren,
 239     ) -> Result<(), MatchFailed> {
 240         let mut pattern_it = pattern_it.peekable();
 241         loop {
 242             match phase.next_non_trivial(&mut code_it) {
 243                 None => {
 244                     if let Some(p) = pattern_it.next() {
 245                         fail_match!("Part of the pattern was unmatched: {:?}", p);
 246                     }
 247                     return Ok(());
 248                 }
 249                 Some(SyntaxElement::Token(c)) => {
 250                     self.attempt_match_token(phase, &mut pattern_it, &c)?;
 251                 }
 252                 Some(SyntaxElement::Node(c)) => match pattern_it.next() {
 253                     Some(SyntaxElement::Node(p)) => {
 254                         self.attempt_match_node(phase, &p, &c)?;
 255                     }
 256                     Some(p) => fail_match!("Pattern wanted '{}', code has {}", p, c.text()),
 257                     None => fail_match!("Pattern reached end, code has {}", c.text()),
 258                 },
 259             }
 260         }
 261     }
 262
 263     fn attempt_match_token(
 264         &self,
 265         phase: &mut Phase,
 266         pattern: &mut Peekable<PatternIterator>,
 267         code: &syntax::SyntaxToken,
 268     ) -> Result<(), MatchFailed> {
 269         phase.record_ignored_comments(code);
 270         // Ignore whitespace and comments.
 271         if code.kind().is_trivia() {
 272             return Ok(());
 273         }
 274         if let Some(SyntaxElement::Token(p)) = pattern.peek() {
 275             // If the code has a comma and the pattern is about to close something, then accept the
 276             // comma without advancing the pattern. i.e. ignore trailing commas.
 277             if code.kind() == SyntaxKind::COMMA && is_closing_token(p.kind()) {
 278                 return Ok(());
 279             }
 280             // Conversely, if the pattern has a comma and the code doesn't, skip that part of the
 281             // pattern and continue to match the code.
 282             if p.kind() == SyntaxKind::COMMA && is_closing_token(code.kind()) {
 283                 pattern.next();
 284             }
 285         }
 286         // Consume an element from the pattern and make sure it matches.
 287         match pattern.next() {
 288             Some(SyntaxElement::Token(p)) => {
 289                 if p.kind() != code.kind() || p.text() != code.text() {
 290                     fail_match!(
 291                         "Pattern wanted token '{}' ({:?}), but code had token '{}' ({:?})",
 292                         p.text(),
 293                         p.kind(),
 294                         code.text(),
 295                         code.kind()
 296                     )
 297                 }
 298             }
 299             Some(SyntaxElement::Node(p)) => {
 300                 // Not sure if this is actually reachable.
 301                 fail_match!(
 302                     "Pattern wanted {:?}, but code had token '{}' ({:?})",
 303                     p,
 304                     code.text(),
 305                     code.kind()
 306                 );
 307             }
 308             None => {
 309                 fail_match!("Pattern exhausted, while code remains: `{}`", code.text());
 310             }
 311         }
 312         Ok(())
 313     }
 314
 315     fn check_constraint(
 316         &self,
 317         constraint: &Constraint,
 318         code: &SyntaxNode,
 319     ) -> Result<(), MatchFailed> {
 320         match constraint {
 321             Constraint::Kind(kind) => {
 322                 kind.matches(code)?;
 323             }
 324             Constraint::Not(sub) => {
 325                 if self.check_constraint(&*sub, code).is_ok() {
 326                     fail_match!("Constraint {:?} failed for '{}'", constraint, code.text());
 327                 }
 328             }
 329         }
 330         Ok(())
 331     }
 332
 333     /// Paths are matched based on whether they refer to the same thing, even if they're written
 334     /// differently.
 335     fn attempt_match_path(
 336         &self,
 337         phase: &mut Phase,
 338         pattern: &SyntaxNode,
 339         code: &SyntaxNode,
 340     ) -> Result<(), MatchFailed> {
 341         if let Some(pattern_resolved) = self.rule.pattern.resolved_paths.get(pattern) {
 342             let pattern_path = ast::Path::cast(pattern.clone()).unwrap();
 343             let code_path = ast::Path::cast(code.clone()).unwrap();
 344             if let (Some(pattern_segment), Some(code_segment)) =
 345                 (pattern_path.segment(), code_path.segment())
 346             {
 347                 // Match everything within the segment except for the name-ref, which is handled
 348                 // separately via comparing what the path resolves to below.
 349                 self.attempt_match_opt(
 350                     phase,
 351                     pattern_segment.generic_arg_list(),
 352                     code_segment.generic_arg_list(),
 353                 )?;
 354                 self.attempt_match_opt(
 355                     phase,
 356                     pattern_segment.param_list(),
 357                     code_segment.param_list(),
 358                 )?;
 359             }
 360             if matches!(phase, Phase::Second(_)) {
 361                 let resolution = self
 362                     .sema
 363                     .resolve_path(&code_path)
 364                     .ok_or_else(|| match_error!("Failed to resolve path `{}`", code.text()))?;
 365                 if pattern_resolved.resolution != resolution {
 366                     fail_match!("Pattern had path `{}` code had `{}`", pattern.text(), code.text());
 367                 }
 368             }
 369         } else {
 370             return self.attempt_match_node_children(phase, pattern, code);
 371         }
 372         Ok(())
 373     }
 374
 375     fn attempt_match_opt<T: AstNode>(
 376         &self,
 377         phase: &mut Phase,
 378         pattern: Option<T>,
 379         code: Option<T>,
 380     ) -> Result<(), MatchFailed> {
 381         match (pattern, code) {
 382             (Some(p), Some(c)) => self.attempt_match_node(phase, p.syntax(), c.syntax()),
 383             (None, None) => Ok(()),
 384             (Some(p), None) => fail_match!("Pattern `{}` had nothing to match", p.syntax().text()),
 385             (None, Some(c)) => {
 386                 fail_match!("Nothing in pattern to match code `{}`", c.syntax().text())
 387             }
 388         }
 389     }
 390
 391     /// We want to allow the records to match in any order, so we have special matching logic for
 392     /// them.
 393     fn attempt_match_record_field_list(
 394         &self,
 395         phase: &mut Phase,
 396         pattern: &SyntaxNode,
 397         code: &SyntaxNode,
 398     ) -> Result<(), MatchFailed> {
 399         // Build a map keyed by field name.
 400         let mut fields_by_name: FxHashMap<SmolStr, SyntaxNode> = FxHashMap::default();
 401         for child in code.children() {
 402             if let Some(record) = ast::RecordExprField::cast(child.clone()) {
 403                 if let Some(name) = record.field_name() {
 404                     fields_by_name.insert(name.text().into(), child.clone());
 405                 }
 406             }
 407         }
 408         for p in pattern.children_with_tokens() {
 409             if let SyntaxElement::Node(p) = p {
 410                 if let Some(name_element) = p.first_child_or_token() {
 411                     if self.get_placeholder(&name_element).is_some() {
 412                         // If the pattern is using placeholders for field names then order
 413                         // independence doesn't make sense. Fall back to regular ordered
 414                         // matching.
 415                         return self.attempt_match_node_children(phase, pattern, code);
 416                     }
 417                     if let Some(ident) = only_ident(name_element) {
 418                         let code_record = fields_by_name.remove(ident.text()).ok_or_else(|| {
 419                             match_error!(
 420                                 "Placeholder has record field '{}', but code doesn't",
 421                                 ident
 422                             )
 423                         })?;
 424                         self.attempt_match_node(phase, &p, &code_record)?;
 425                     }
 426                 }
 427             }
 428         }
 429         if let Some(unmatched_fields) = fields_by_name.keys().next() {
 430             fail_match!(
 431                 "{} field(s) of a record literal failed to match, starting with {}",
 432                 fields_by_name.len(),
 433                 unmatched_fields
 434             );
 435         }
 436         Ok(())
 437     }
 438
 439     /// Outside of token trees, a placeholder can only match a single AST node, whereas in a token
 440     /// tree it can match a sequence of tokens. Note, that this code will only be used when the
 441     /// pattern matches the macro invocation. For matches within the macro call, we'll already have
 442     /// expanded the macro.
 443     fn attempt_match_token_tree(
 444         &self,
 445         phase: &mut Phase,
 446         pattern: &SyntaxNode,
 447         code: &syntax::SyntaxNode,
 448     ) -> Result<(), MatchFailed> {
 449         let mut pattern = PatternIterator::new(pattern).peekable();
 450         let mut children = code.children_with_tokens();
 451         while let Some(child) = children.next() {
 452             if let Some(placeholder) = pattern.peek().and_then(|p| self.get_placeholder(p)) {
 453                 pattern.next();
 454                 let next_pattern_token = pattern
 455                     .peek()
 456                     .and_then(|p| match p {
 457                         SyntaxElement::Token(t) => Some(t.clone()),
 458                         SyntaxElement::Node(n) => n.first_token(),
 459                     })
 460                     .map(|p| p.text().to_string());
 461                 let first_matched_token = child.clone();
 462                 let mut last_matched_token = child;
 463                 // Read code tokens util we reach one equal to the next token from our pattern
 464                 // or we reach the end of the token tree.
 465                 for next in &mut children {
 466                     match &next {
 467                         SyntaxElement::Token(t) => {
 468                             if Some(t.to_string()) == next_pattern_token {
 469                                 pattern.next();
 470                                 break;
 471                             }
 472                         }
 473                         SyntaxElement::Node(n) => {
 474                             if let Some(first_token) = n.first_token() {
 475                                 if Some(first_token.text()) == next_pattern_token.as_deref() {
 476                                     if let Some(SyntaxElement::Node(p)) = pattern.next() {
 477                                         // We have a subtree that starts with the next token in our pattern.
 478                                         self.attempt_match_token_tree(phase, &p, n)?;
 479                                         break;
 480                                     }
 481                                 }
 482                             }
 483                         }
 484                     };
 485                     last_matched_token = next;
 486                 }
 487                 if let Phase::Second(match_out) = phase {
 488                     match_out.placeholder_values.insert(
 489                         placeholder.ident.clone(),
 490                         PlaceholderMatch::from_range(FileRange {
 491                             file_id: self.sema.original_range(code).file_id,
 492                             range: first_matched_token
 493                                 .text_range()
 494                                 .cover(last_matched_token.text_range()),
 495                         }),
 496                     );
 497                 }
 498                 continue;
 499             }
 500             // Match literal (non-placeholder) tokens.
 501             match child {
 502                 SyntaxElement::Token(token) => {
 503                     self.attempt_match_token(phase, &mut pattern, &token)?;
 504                 }
 505                 SyntaxElement::Node(node) => match pattern.next() {
 506                     Some(SyntaxElement::Node(p)) => {
 507                         self.attempt_match_token_tree(phase, &p, &node)?;
 508                     }
 509                     Some(SyntaxElement::Token(p)) => fail_match!(
 510                         "Pattern has token '{}', code has subtree '{}'",
 511                         p.text(),
 512                         node.text()
 513                     ),
 514                     None => fail_match!("Pattern has nothing, code has '{}'", node.text()),
 515                 },
 516             }
 517         }
 518         if let Some(p) = pattern.next() {
 519             fail_match!("Reached end of token tree in code, but pattern still has {:?}", p);
 520         }
 521         Ok(())
 522     }
 523
 524     fn attempt_match_ufcs_to_method_call(
 525         &self,
 526         phase: &mut Phase,
 527         pattern_ufcs: &UfcsCallInfo,
 528         code: &ast::MethodCallExpr,
 529     ) -> Result<(), MatchFailed> {
 530         use ast::HasArgList;
 531         let code_resolved_function = self
 532             .sema
 533             .resolve_method_call(code)
 534             .ok_or_else(|| match_error!("Failed to resolve method call"))?;
 535         if pattern_ufcs.function != code_resolved_function {
 536             fail_match!("Method call resolved to a different function");
 537         }
 538         // Check arguments.
 539         let mut pattern_args = pattern_ufcs
 540             .call_expr
 541             .arg_list()
 542             .ok_or_else(|| match_error!("Pattern function call has no args"))?
 543             .args();
 544         // If the function we're calling takes a self parameter, then we store additional
 545         // information on the placeholder match about autoderef and autoref. This allows us to use
 546         // the placeholder in a context where autoderef and autoref don't apply.
 547         if code_resolved_function.self_param(self.sema.db).is_some() {
 548             if let (Some(pattern_type), Some(expr)) =
 549                 (&pattern_ufcs.qualifier_type, &code.receiver())
 550             {
 551                 let deref_count = self.check_expr_type(pattern_type, expr)?;
 552                 let pattern_receiver = pattern_args.next();
 553                 self.attempt_match_opt(phase, pattern_receiver.clone(), code.receiver())?;
 554                 if let Phase::Second(match_out) = phase {
 555                     if let Some(placeholder_value) = pattern_receiver
 556                         .and_then(|n| self.get_placeholder_for_node(n.syntax()))
 557                         .and_then(|placeholder| {
 558                             match_out.placeholder_values.get_mut(&placeholder.ident)
 559                         })
 560                     {
 561                         placeholder_value.autoderef_count = deref_count;
 562                         placeholder_value.autoref_kind = self
 563                             .sema
 564                             .resolve_method_call_as_callable(code)
 565                             .and_then(|callable| callable.receiver_param(self.sema.db))
 566                             .map(|self_param| self_param.kind())
 567                             .unwrap_or(ast::SelfParamKind::Owned);
 568                     }
 569                 }
 570             }
 571         } else {
 572             self.attempt_match_opt(phase, pattern_args.next(), code.receiver())?;
 573         }
 574         let mut code_args =
 575             code.arg_list().ok_or_else(|| match_error!("Code method call has no args"))?.args();
 576         loop {
 577             match (pattern_args.next(), code_args.next()) {
 578                 (None, None) => return Ok(()),
 579                 (p, c) => self.attempt_match_opt(phase, p, c)?,
 580             }
 581         }
 582     }
 583
 584     fn attempt_match_ufcs_to_ufcs(
 585         &self,
 586         phase: &mut Phase,
 587         pattern_ufcs: &UfcsCallInfo,
 588         code: &ast::CallExpr,
 589     ) -> Result<(), MatchFailed> {
 590         use ast::HasArgList;
 591         // Check that the first argument is the expected type.
 592         if let (Some(pattern_type), Some(expr)) = (
 593             &pattern_ufcs.qualifier_type,
 594             &code.arg_list().and_then(|code_args| code_args.args().next()),
 595         ) {
 596             self.check_expr_type(pattern_type, expr)?;
 597         }
 598         self.attempt_match_node_children(phase, pattern_ufcs.call_expr.syntax(), code.syntax())
 599     }
 600
 601     /// Verifies that `expr` matches `pattern_type`, possibly after dereferencing some number of
 602     /// times. Returns the number of times it needed to be dereferenced.
 603     fn check_expr_type(
 604         &self,
 605         pattern_type: &hir::Type,
 606         expr: &ast::Expr,
 607     ) -> Result<usize, MatchFailed> {
 608         use hir::HirDisplay;
 609         let code_type = self
 610             .sema
 611             .type_of_expr(expr)
 612             .ok_or_else(|| {
 613                 match_error!("Failed to get receiver type for `{}`", expr.syntax().text())
 614             })?
 615             .original;
 616         // Temporary needed to make the borrow checker happy.
 617         let res = code_type
 618             .autoderef(self.sema.db)
 619             .enumerate()
 620             .find(|(_, deref_code_type)| pattern_type == deref_code_type)
 621             .map(|(count, _)| count)
 622             .ok_or_else(|| {
 623                 match_error!(
 624                     "Pattern type `{}` didn't match code type `{}`",
 625                     pattern_type.display(self.sema.db),
 626                     code_type.display(self.sema.db)
 627                 )
 628             });
 629         res
 630     }
 631
 632     fn get_placeholder_for_node(&self, node: &SyntaxNode) -> Option<&Placeholder> {
 633         self.get_placeholder(&SyntaxElement::Node(node.clone()))
 634     }
 635
 636     fn get_placeholder(&self, element: &SyntaxElement) -> Option<&Placeholder> {
 637         only_ident(element.clone()).and_then(|ident| self.rule.get_placeholder(&ident))
 638     }
 639 }
 640
 641 impl Match {
 642     fn render_template_paths(
 643         &mut self,
 644         template: &ResolvedPattern,
 645         sema: &Semantics<ide_db::RootDatabase>,
 646     ) -> Result<(), MatchFailed> {
 647         let module = sema
 648             .scope(&self.matched_node)
 649             .module()
 650             .ok_or_else(|| match_error!("Matched node isn't in a module"))?;
 651         for (path, resolved_path) in &template.resolved_paths {
 652             if let hir::PathResolution::Def(module_def) = resolved_path.resolution {
 653                 let mod_path = module.find_use_path(sema.db, module_def).ok_or_else(|| {
 654                     match_error!("Failed to render template path `{}` at match location")
 655                 })?;
 656                 self.rendered_template_paths.insert(path.clone(), mod_path);
 657             }
 658         }
 659         Ok(())
 660     }
 661 }
 662
 663 impl Phase<'_> {
 664     fn next_non_trivial(&mut self, code_it: &mut SyntaxElementChildren) -> Option<SyntaxElement> {
 665         loop {
 666             let c = code_it.next();
 667             if let Some(SyntaxElement::Token(t)) = &c {
 668                 self.record_ignored_comments(t);
 669                 if t.kind().is_trivia() {
 670                     continue;
 671                 }
 672             }
 673             return c;
 674         }
 675     }
 676
 677     fn record_ignored_comments(&mut self, token: &SyntaxToken) {
 678         if token.kind() == SyntaxKind::COMMENT {
 679             if let Phase::Second(match_out) = self {
 680                 if let Some(comment) = ast::Comment::cast(token.clone()) {
 681                     match_out.ignored_comments.push(comment);
 682                 }
 683             }
 684         }
 685     }
 686 }
 687
 688 fn is_closing_token(kind: SyntaxKind) -> bool {
 689     kind == SyntaxKind::R_PAREN || kind == SyntaxKind::R_CURLY || kind == SyntaxKind::R_BRACK
 690 }
 691
 692 pub(crate) fn record_match_fails_reasons_scope<F, T>(debug_active: bool, f: F) -> T
 693 where
 694     F: Fn() -> T,
 695 {
 696     RECORDING_MATCH_FAIL_REASONS.with(|c| c.set(debug_active));
 697     let res = f();
 698     RECORDING_MATCH_FAIL_REASONS.with(|c| c.set(false));
 699     res
 700 }
 701
 702 // For performance reasons, we don't want to record the reason why every match fails, only the bit
 703 // of code that the user indicated they thought would match. We use a thread local to indicate when
 704 // we are trying to match that bit of code. This saves us having to pass a boolean into all the bits
 705 // of code that can make the decision to not match.
 706 thread_local! {
 707     pub static RECORDING_MATCH_FAIL_REASONS: Cell<bool> = Cell::new(false);
 708 }
 709
 710 fn recording_match_fail_reasons() -> bool {
 711     RECORDING_MATCH_FAIL_REASONS.with(|c| c.get())
 712 }
 713
 714 impl PlaceholderMatch {
 715     fn from_range(range: FileRange) -> Self {
 716         Self {
 717             range,
 718             inner_matches: SsrMatches::default(),
 719             autoderef_count: 0,
 720             autoref_kind: ast::SelfParamKind::Owned,
 721         }
 722     }
 723 }
 724
 725 impl NodeKind {
 726     fn matches(&self, node: &SyntaxNode) -> Result<(), MatchFailed> {
 727         let ok = match self {
 728             Self::Literal => {
 729                 cov_mark::hit!(literal_constraint);
 730                 ast::Literal::can_cast(node.kind())
 731             }
 732         };
 733         if !ok {
 734             fail_match!("Code '{}' isn't of kind {:?}", node.text(), self);
 735         }
 736         Ok(())
 737     }
 738 }
 739
 740 // If `node` contains nothing but an ident then return it, otherwise return None.
 741 fn only_ident(element: SyntaxElement) -> Option<SyntaxToken> {
 742     match element {
 743         SyntaxElement::Token(t) => {
 744             if t.kind() == SyntaxKind::IDENT {
 745                 return Some(t);
 746             }
 747         }
 748         SyntaxElement::Node(n) => {
 749             let mut children = n.children_with_tokens();
 750             if let (Some(only_child), None) = (children.next(), children.next()) {
 751                 return only_ident(only_child);
 752             }
 753         }
 754     }
 755     None
 756 }
 757
 758 struct PatternIterator {
 759     iter: SyntaxElementChildren,
 760 }
 761
 762 impl Iterator for PatternIterator {
 763     type Item = SyntaxElement;
 764
 765     fn next(&mut self) -> Option<SyntaxElement> {
 766         for element in &mut self.iter {
 767             if !element.kind().is_trivia() {
 768                 return Some(element);
 769             }
 770         }
 771         None
 772     }
 773 }
 774
 775 impl PatternIterator {
 776     fn new(parent: &SyntaxNode) -> Self {
 777         Self { iter: parent.children_with_tokens() }
 778     }
 779 }
 780
 781 #[cfg(test)]
 782 mod tests {
 783     use crate::{MatchFinder, SsrRule};
 784
 785     #[test]
 786     fn parse_match_replace() {
 787         let rule: SsrRule = "foo($x) ==>> bar($x)".parse().unwrap();
 788         let input = "fn foo() {} fn bar() {} fn main() { foo(1+2); }";
 789
 790         let (db, position, selections) = crate::tests::single_file(input);
 791         let mut match_finder = MatchFinder::in_context(&db, position, selections);
 792         match_finder.add_rule(rule).unwrap();
 793         let matches = match_finder.matches();
 794         assert_eq!(matches.matches.len(), 1);
 795         assert_eq!(matches.matches[0].matched_node.text(), "foo(1+2)");
 796         assert_eq!(matches.matches[0].placeholder_values.len(), 1);
 797
 798         let edits = match_finder.edits();
 799         assert_eq!(edits.len(), 1);
 800         let edit = &edits[&position.file_id];
 801         let mut after = input.to_string();
 802         edit.apply(&mut after);
 803         assert_eq!(after, "fn foo() {} fn bar() {} fn main() { bar(1+2); }");
 804     }
 805 }