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