aboutsummaryrefslogtreecommitdiff
path: root/crates/ra_ssr
diff options
context:
space:
mode:
authorDavid Lattimore <[email protected]>2020-07-03 04:09:14 +0100
committerDavid Lattimore <[email protected]>2020-07-03 23:56:58 +0100
commit69051d2f9dcf008124918ef34d2f11221a6a20f0 (patch)
treefb9527539d736ff98f690550bc769b68e5263811 /crates/ra_ssr
parent4a8679824b9ddf950e6754231755d5d065692c47 (diff)
SSR: Refactor matching code.
Mutable state is now stored in the enum Phase. MatchState, since it now has no mutable state is renamed Matcher. MatchInputs is merged into Matcher
Diffstat (limited to 'crates/ra_ssr')
-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}