aboutsummaryrefslogtreecommitdiff
path: root/crates
diff options
context:
space:
mode:
Diffstat (limited to 'crates')
-rw-r--r--crates/ra_ssr/src/matching.rs155
1 files changed, 75 insertions, 80 deletions
diff --git a/crates/ra_ssr/src/matching.rs b/crates/ra_ssr/src/matching.rs
index ce53d46d2..50b29eab2 100644
--- a/crates/ra_ssr/src/matching.rs
+++ b/crates/ra_ssr/src/matching.rs
@@ -92,58 +92,52 @@ pub(crate) fn get_match(
92 sema: &Semantics<ra_ide_db::RootDatabase>, 92 sema: &Semantics<ra_ide_db::RootDatabase>,
93) -> Result<Match, MatchFailed> { 93) -> Result<Match, MatchFailed> {
94 record_match_fails_reasons_scope(debug_active, || { 94 record_match_fails_reasons_scope(debug_active, || {
95 MatchState::try_match(rule, code, restrict_range, sema) 95 Matcher::try_match(rule, code, restrict_range, sema)
96 }) 96 })
97} 97}
98 98
99/// Inputs to matching. This cannot be part of `MatchState`, since we mutate `MatchState` and in at 99/// Checks if our search pattern matches a particular node of the AST.
100/// least one case need to hold a borrow of a placeholder from the input pattern while calling a 100struct Matcher<'db, 'sema> {
101/// mutable `MatchState` method.
102struct MatchInputs<'pattern> {
103 ssr_pattern: &'pattern SsrPattern,
104}
105
106/// State used while attempting to match our search pattern against a particular node of the AST.
107struct MatchState<'db, 'sema> {
108 sema: &'sema Semantics<'db, ra_ide_db::RootDatabase>, 101 sema: &'sema Semantics<'db, ra_ide_db::RootDatabase>,
109 /// If any placeholders come from anywhere outside of this range, then the match will be 102 /// If any placeholders come from anywhere outside of this range, then the match will be
110 /// rejected. 103 /// rejected.
111 restrict_range: Option<FileRange>, 104 restrict_range: Option<FileRange>,
112 /// The match that we're building. We do two passes for a successful match. On the first pass, 105 rule: &'sema SsrRule,
113 /// this is None so that we can avoid doing things like storing copies of what placeholders 106}
114 /// matched to. If that pass succeeds, then we do a second pass where we collect those details. 107
115 /// This means that if we have a pattern like `$a.foo()` we won't do an insert into the 108/// Which phase of matching we're currently performing. We do two phases because most attempted
116 /// placeholders map for every single method call in the codebase. Instead we'll discard all the 109/// matches will fail and it means we can defer more expensive checks to the second phase.
117 /// method calls that aren't calls to `foo` on the first pass and only insert into the 110enum Phase<'a> {
118 /// placeholders map on the second pass. Likewise for ignored comments. 111 /// On the first phase, we perform cheap checks. No state is mutated and nothing is recorded.
119 match_out: Option<Match>, 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),
120} 116}
121 117
122impl<'db, 'sema> MatchState<'db, 'sema> { 118impl<'db, 'sema> Matcher<'db, 'sema> {
123 fn try_match( 119 fn try_match(
124 rule: &SsrRule, 120 rule: &'sema SsrRule,
125 code: &SyntaxNode, 121 code: &SyntaxNode,
126 restrict_range: &Option<FileRange>, 122 restrict_range: &Option<FileRange>,
127 sema: &'sema Semantics<'db, ra_ide_db::RootDatabase>, 123 sema: &'sema Semantics<'db, ra_ide_db::RootDatabase>,
128 ) -> Result<Match, MatchFailed> { 124 ) -> Result<Match, MatchFailed> {
129 let mut match_state = 125 let match_state = Matcher { sema, restrict_range: restrict_range.clone(), rule };
130 MatchState { sema, restrict_range: restrict_range.clone(), match_out: None };
131 let match_inputs = MatchInputs { ssr_pattern: &rule.pattern };
132 let pattern_tree = rule.pattern.tree_for_kind(code.kind())?; 126 let pattern_tree = rule.pattern.tree_for_kind(code.kind())?;
133 // First pass at matching, where we check that node types and idents match. 127 // First pass at matching, where we check that node types and idents match.
134 match_state.attempt_match_node(&match_inputs, &pattern_tree, code)?; 128 match_state.attempt_match_node(&mut Phase::First, &pattern_tree, code)?;
135 match_state.validate_range(&sema.original_range(code))?; 129 match_state.validate_range(&sema.original_range(code))?;
136 match_state.match_out = Some(Match { 130 let mut the_match = Match {
137 range: sema.original_range(code), 131 range: sema.original_range(code),
138 matched_node: code.clone(), 132 matched_node: code.clone(),
139 placeholder_values: FxHashMap::default(), 133 placeholder_values: FxHashMap::default(),
140 ignored_comments: Vec::new(), 134 ignored_comments: Vec::new(),
141 template: rule.template.clone(), 135 template: rule.template.clone(),
142 }); 136 };
143 // Second matching pass, where we record placeholder matches, ignored comments and maybe do 137 // Second matching pass, where we record placeholder matches, ignored comments and maybe do
144 // any other more expensive checks that we didn't want to do on the first pass. 138 // any other more expensive checks that we didn't want to do on the first pass.
145 match_state.attempt_match_node(&match_inputs, &pattern_tree, code)?; 139 match_state.attempt_match_node(&mut Phase::Second(&mut the_match), &pattern_tree, code)?;
146 Ok(match_state.match_out.unwrap()) 140 Ok(the_match)
147 } 141 }
148 142
149 /// Checks that `range` is within the permitted range if any. This is applicable when we're 143 /// Checks that `range` is within the permitted range if any. This is applicable when we're
@@ -161,27 +155,22 @@ impl<'db, 'sema> MatchState<'db, 'sema> {
161 } 155 }
162 156
163 fn attempt_match_node( 157 fn attempt_match_node(
164 &mut self, 158 &self,
165 match_inputs: &MatchInputs, 159 phase: &mut Phase,
166 pattern: &SyntaxNode, 160 pattern: &SyntaxNode,
167 code: &SyntaxNode, 161 code: &SyntaxNode,
168 ) -> Result<(), MatchFailed> { 162 ) -> Result<(), MatchFailed> {
169 // Handle placeholders. 163 // Handle placeholders.
170 if let Some(placeholder) = 164 if let Some(placeholder) = self.get_placeholder(&SyntaxElement::Node(pattern.clone())) {
171 match_inputs.get_placeholder(&SyntaxElement::Node(pattern.clone()))
172 {
173 for constraint in &placeholder.constraints { 165 for constraint in &placeholder.constraints {
174 self.check_constraint(constraint, code)?; 166 self.check_constraint(constraint, code)?;
175 } 167 }
176 if self.match_out.is_none() { 168 if let Phase::Second(matches_out) = phase {
177 return Ok(()); 169 let original_range = self.sema.original_range(code);
178 } 170 // We validated the range for the node when we started the match, so the placeholder
179 let original_range = self.sema.original_range(code); 171 // probably can't fail range validation, but just to be safe...
180 // We validated the range for the node when we started the match, so the placeholder 172 self.validate_range(&original_range)?;
181 // probably can't fail range validation, but just to be safe... 173 matches_out.placeholder_values.insert(
182 self.validate_range(&original_range)?;
183 if let Some(match_out) = &mut self.match_out {
184 match_out.placeholder_values.insert(
185 Var(placeholder.ident.to_string()), 174 Var(placeholder.ident.to_string()),
186 PlaceholderMatch::new(code, original_range), 175 PlaceholderMatch::new(code, original_range),
187 ); 176 );
@@ -190,41 +179,47 @@ impl<'db, 'sema> MatchState<'db, 'sema> {
190 } 179 }
191 // Non-placeholders. 180 // Non-placeholders.
192 if pattern.kind() != code.kind() { 181 if pattern.kind() != code.kind() {
193 fail_match!("Pattern had a {:?}, code had {:?}", pattern.kind(), code.kind()); 182 fail_match!(
183 "Pattern had a `{}` ({:?}), code had `{}` ({:?})",
184 pattern.text(),
185 pattern.kind(),
186 code.text(),
187 code.kind()
188 );
194 } 189 }
195 // Some kinds of nodes have special handling. For everything else, we fall back to default 190 // Some kinds of nodes have special handling. For everything else, we fall back to default
196 // matching. 191 // matching.
197 match code.kind() { 192 match code.kind() {
198 SyntaxKind::RECORD_FIELD_LIST => { 193 SyntaxKind::RECORD_FIELD_LIST => {
199 self.attempt_match_record_field_list(match_inputs, pattern, code) 194 self.attempt_match_record_field_list(phase, pattern, code)
200 } 195 }
201 SyntaxKind::TOKEN_TREE => self.attempt_match_token_tree(match_inputs, pattern, code), 196 SyntaxKind::TOKEN_TREE => self.attempt_match_token_tree(phase, pattern, code),
202 _ => self.attempt_match_node_children(match_inputs, pattern, code), 197 _ => self.attempt_match_node_children(phase, pattern, code),
203 } 198 }
204 } 199 }
205 200
206 fn attempt_match_node_children( 201 fn attempt_match_node_children(
207 &mut self, 202 &self,
208 match_inputs: &MatchInputs, 203 phase: &mut Phase,
209 pattern: &SyntaxNode, 204 pattern: &SyntaxNode,
210 code: &SyntaxNode, 205 code: &SyntaxNode,
211 ) -> Result<(), MatchFailed> { 206 ) -> Result<(), MatchFailed> {
212 self.attempt_match_sequences( 207 self.attempt_match_sequences(
213 match_inputs, 208 phase,
214 PatternIterator::new(pattern), 209 PatternIterator::new(pattern),
215 code.children_with_tokens(), 210 code.children_with_tokens(),
216 ) 211 )
217 } 212 }
218 213
219 fn attempt_match_sequences( 214 fn attempt_match_sequences(
220 &mut self, 215 &self,
221 match_inputs: &MatchInputs, 216 phase: &mut Phase,
222 pattern_it: PatternIterator, 217 pattern_it: PatternIterator,
223 mut code_it: SyntaxElementChildren, 218 mut code_it: SyntaxElementChildren,
224 ) -> Result<(), MatchFailed> { 219 ) -> Result<(), MatchFailed> {
225 let mut pattern_it = pattern_it.peekable(); 220 let mut pattern_it = pattern_it.peekable();
226 loop { 221 loop {
227 match self.next_non_trivial(&mut code_it) { 222 match phase.next_non_trivial(&mut code_it) {
228 None => { 223 None => {
229 if let Some(p) = pattern_it.next() { 224 if let Some(p) = pattern_it.next() {
230 fail_match!("Part of the pattern was unmatched: {:?}", p); 225 fail_match!("Part of the pattern was unmatched: {:?}", p);
@@ -232,11 +227,11 @@ impl<'db, 'sema> MatchState<'db, 'sema> {
232 return Ok(()); 227 return Ok(());
233 } 228 }
234 Some(SyntaxElement::Token(c)) => { 229 Some(SyntaxElement::Token(c)) => {
235 self.attempt_match_token(&mut pattern_it, &c)?; 230 self.attempt_match_token(phase, &mut pattern_it, &c)?;
236 } 231 }
237 Some(SyntaxElement::Node(c)) => match pattern_it.next() { 232 Some(SyntaxElement::Node(c)) => match pattern_it.next() {
238 Some(SyntaxElement::Node(p)) => { 233 Some(SyntaxElement::Node(p)) => {
239 self.attempt_match_node(match_inputs, &p, &c)?; 234 self.attempt_match_node(phase, &p, &c)?;
240 } 235 }
241 Some(p) => fail_match!("Pattern wanted '{}', code has {}", p, c.text()), 236 Some(p) => fail_match!("Pattern wanted '{}', code has {}", p, c.text()),
242 None => fail_match!("Pattern reached end, code has {}", c.text()), 237 None => fail_match!("Pattern reached end, code has {}", c.text()),
@@ -246,11 +241,12 @@ impl<'db, 'sema> MatchState<'db, 'sema> {
246 } 241 }
247 242
248 fn attempt_match_token( 243 fn attempt_match_token(
249 &mut self, 244 &self,
245 phase: &mut Phase,
250 pattern: &mut Peekable<PatternIterator>, 246 pattern: &mut Peekable<PatternIterator>,
251 code: &ra_syntax::SyntaxToken, 247 code: &ra_syntax::SyntaxToken,
252 ) -> Result<(), MatchFailed> { 248 ) -> Result<(), MatchFailed> {
253 self.record_ignored_comments(code); 249 phase.record_ignored_comments(code);
254 // Ignore whitespace and comments. 250 // Ignore whitespace and comments.
255 if code.kind().is_trivia() { 251 if code.kind().is_trivia() {
256 return Ok(()); 252 return Ok(());
@@ -317,8 +313,8 @@ impl<'db, 'sema> MatchState<'db, 'sema> {
317 /// We want to allow the records to match in any order, so we have special matching logic for 313 /// We want to allow the records to match in any order, so we have special matching logic for
318 /// them. 314 /// them.
319 fn attempt_match_record_field_list( 315 fn attempt_match_record_field_list(
320 &mut self, 316 &self,
321 match_inputs: &MatchInputs, 317 phase: &mut Phase,
322 pattern: &SyntaxNode, 318 pattern: &SyntaxNode,
323 code: &SyntaxNode, 319 code: &SyntaxNode,
324 ) -> Result<(), MatchFailed> { 320 ) -> Result<(), MatchFailed> {
@@ -334,11 +330,11 @@ impl<'db, 'sema> MatchState<'db, 'sema> {
334 for p in pattern.children_with_tokens() { 330 for p in pattern.children_with_tokens() {
335 if let SyntaxElement::Node(p) = p { 331 if let SyntaxElement::Node(p) = p {
336 if let Some(name_element) = p.first_child_or_token() { 332 if let Some(name_element) = p.first_child_or_token() {
337 if match_inputs.get_placeholder(&name_element).is_some() { 333 if self.get_placeholder(&name_element).is_some() {
338 // If the pattern is using placeholders for field names then order 334 // If the pattern is using placeholders for field names then order
339 // independence doesn't make sense. Fall back to regular ordered 335 // independence doesn't make sense. Fall back to regular ordered
340 // matching. 336 // matching.
341 return self.attempt_match_node_children(match_inputs, pattern, code); 337 return self.attempt_match_node_children(phase, pattern, code);
342 } 338 }
343 if let Some(ident) = only_ident(name_element) { 339 if let Some(ident) = only_ident(name_element) {
344 let code_record = fields_by_name.remove(ident.text()).ok_or_else(|| { 340 let code_record = fields_by_name.remove(ident.text()).ok_or_else(|| {
@@ -347,7 +343,7 @@ impl<'db, 'sema> MatchState<'db, 'sema> {
347 ident 343 ident
348 ) 344 )
349 })?; 345 })?;
350 self.attempt_match_node(match_inputs, &p, &code_record)?; 346 self.attempt_match_node(phase, &p, &code_record)?;
351 } 347 }
352 } 348 }
353 } 349 }
@@ -367,16 +363,15 @@ impl<'db, 'sema> MatchState<'db, 'sema> {
367 /// pattern matches the macro invocation. For matches within the macro call, we'll already have 363 /// pattern matches the macro invocation. For matches within the macro call, we'll already have
368 /// expanded the macro. 364 /// expanded the macro.
369 fn attempt_match_token_tree( 365 fn attempt_match_token_tree(
370 &mut self, 366 &self,
371 match_inputs: &MatchInputs, 367 phase: &mut Phase,
372 pattern: &SyntaxNode, 368 pattern: &SyntaxNode,
373 code: &ra_syntax::SyntaxNode, 369 code: &ra_syntax::SyntaxNode,
374 ) -> Result<(), MatchFailed> { 370 ) -> Result<(), MatchFailed> {
375 let mut pattern = PatternIterator::new(pattern).peekable(); 371 let mut pattern = PatternIterator::new(pattern).peekable();
376 let mut children = code.children_with_tokens(); 372 let mut children = code.children_with_tokens();
377 while let Some(child) = children.next() { 373 while let Some(child) = children.next() {
378 if let Some(placeholder) = pattern.peek().and_then(|p| match_inputs.get_placeholder(p)) 374 if let Some(placeholder) = pattern.peek().and_then(|p| self.get_placeholder(p)) {
379 {
380 pattern.next(); 375 pattern.next();
381 let next_pattern_token = pattern 376 let next_pattern_token = pattern
382 .peek() 377 .peek()
@@ -402,7 +397,7 @@ impl<'db, 'sema> MatchState<'db, 'sema> {
402 if Some(first_token.to_string()) == next_pattern_token { 397 if Some(first_token.to_string()) == next_pattern_token {
403 if let Some(SyntaxElement::Node(p)) = pattern.next() { 398 if let Some(SyntaxElement::Node(p)) = pattern.next() {
404 // We have a subtree that starts with the next token in our pattern. 399 // We have a subtree that starts with the next token in our pattern.
405 self.attempt_match_token_tree(match_inputs, &p, &n)?; 400 self.attempt_match_token_tree(phase, &p, &n)?;
406 break; 401 break;
407 } 402 }
408 } 403 }
@@ -411,7 +406,7 @@ impl<'db, 'sema> MatchState<'db, 'sema> {
411 }; 406 };
412 last_matched_token = next; 407 last_matched_token = next;
413 } 408 }
414 if let Some(match_out) = &mut self.match_out { 409 if let Phase::Second(match_out) = phase {
415 match_out.placeholder_values.insert( 410 match_out.placeholder_values.insert(
416 Var(placeholder.ident.to_string()), 411 Var(placeholder.ident.to_string()),
417 PlaceholderMatch::from_range(FileRange { 412 PlaceholderMatch::from_range(FileRange {
@@ -427,11 +422,11 @@ impl<'db, 'sema> MatchState<'db, 'sema> {
427 // Match literal (non-placeholder) tokens. 422 // Match literal (non-placeholder) tokens.
428 match child { 423 match child {
429 SyntaxElement::Token(token) => { 424 SyntaxElement::Token(token) => {
430 self.attempt_match_token(&mut pattern, &token)?; 425 self.attempt_match_token(phase, &mut pattern, &token)?;
431 } 426 }
432 SyntaxElement::Node(node) => match pattern.next() { 427 SyntaxElement::Node(node) => match pattern.next() {
433 Some(SyntaxElement::Node(p)) => { 428 Some(SyntaxElement::Node(p)) => {
434 self.attempt_match_token_tree(match_inputs, &p, &node)?; 429 self.attempt_match_token_tree(phase, &p, &node)?;
435 } 430 }
436 Some(SyntaxElement::Token(p)) => fail_match!( 431 Some(SyntaxElement::Token(p)) => fail_match!(
437 "Pattern has token '{}', code has subtree '{}'", 432 "Pattern has token '{}', code has subtree '{}'",
@@ -448,6 +443,13 @@ impl<'db, 'sema> MatchState<'db, 'sema> {
448 Ok(()) 443 Ok(())
449 } 444 }
450 445
446 fn get_placeholder(&self, element: &SyntaxElement) -> Option<&Placeholder> {
447 only_ident(element.clone())
448 .and_then(|ident| self.rule.pattern.placeholders_by_stand_in.get(ident.text()))
449 }
450}
451
452impl Phase<'_> {
451 fn next_non_trivial(&mut self, code_it: &mut SyntaxElementChildren) -> Option<SyntaxElement> { 453 fn next_non_trivial(&mut self, code_it: &mut SyntaxElementChildren) -> Option<SyntaxElement> {
452 loop { 454 loop {
453 let c = code_it.next(); 455 let c = code_it.next();
@@ -463,7 +465,7 @@ impl<'db, 'sema> MatchState<'db, 'sema> {
463 465
464 fn record_ignored_comments(&mut self, token: &SyntaxToken) { 466 fn record_ignored_comments(&mut self, token: &SyntaxToken) {
465 if token.kind() == SyntaxKind::COMMENT { 467 if token.kind() == SyntaxKind::COMMENT {
466 if let Some(match_out) = &mut self.match_out { 468 if let Phase::Second(match_out) = self {
467 if let Some(comment) = ast::Comment::cast(token.clone()) { 469 if let Some(comment) = ast::Comment::cast(token.clone()) {
468 match_out.ignored_comments.push(comment); 470 match_out.ignored_comments.push(comment);
469 } 471 }
@@ -472,13 +474,6 @@ impl<'db, 'sema> MatchState<'db, 'sema> {
472 } 474 }
473} 475}
474 476
475impl MatchInputs<'_> {
476 fn get_placeholder(&self, element: &SyntaxElement) -> Option<&Placeholder> {
477 only_ident(element.clone())
478 .and_then(|ident| self.ssr_pattern.placeholders_by_stand_in.get(ident.text()))
479 }
480}
481
482fn is_closing_token(kind: SyntaxKind) -> bool { 477fn is_closing_token(kind: SyntaxKind) -> bool {
483 kind == SyntaxKind::R_PAREN || kind == SyntaxKind::R_CURLY || kind == SyntaxKind::R_BRACK 478 kind == SyntaxKind::R_PAREN || kind == SyntaxKind::R_CURLY || kind == SyntaxKind::R_BRACK
484} 479}
@@ -596,12 +591,12 @@ impl PatternIterator {
596#[cfg(test)] 591#[cfg(test)]
597mod tests { 592mod tests {
598 use super::*; 593 use super::*;
599 use crate::MatchFinder; 594 use crate::{MatchFinder, SsrRule};
600 595
601 #[test] 596 #[test]
602 fn parse_match_replace() { 597 fn parse_match_replace() {
603 let rule: SsrRule = "foo($x) ==>> bar($x)".parse().unwrap(); 598 let rule: SsrRule = "foo($x) ==>> bar($x)".parse().unwrap();
604 let input = "fn main() { foo(1+2); }"; 599 let input = "fn foo() {} fn main() { foo(1+2); }";
605 600
606 use ra_db::fixture::WithFixture; 601 use ra_db::fixture::WithFixture;
607 let (db, file_id) = ra_ide_db::RootDatabase::with_single_file(input); 602 let (db, file_id) = ra_ide_db::RootDatabase::with_single_file(input);
@@ -623,6 +618,6 @@ mod tests {
623 let edit = crate::replacing::matches_to_edit(&matches, input); 618 let edit = crate::replacing::matches_to_edit(&matches, input);
624 let mut after = input.to_string(); 619 let mut after = input.to_string();
625 edit.apply(&mut after); 620 edit.apply(&mut after);
626 assert_eq!(after, "fn main() { bar(1+2); }"); 621 assert_eq!(after, "fn foo() {} fn main() { bar(1+2); }");
627 } 622 }
628} 623}