crates/ide_ssr/src/parsing.rs

   1 //! This file contains code for parsing SSR rules, which look something like `foo($a) ==>> bar($b)`.
   2 //! We first split everything before and after the separator `==>>`. Next, both the search pattern
   3 //! and the replacement template get tokenized by the Rust tokenizer. Tokens are then searched for
   4 //! placeholders, which start with `$`. For replacement templates, this is the final form. For
   5 //! search patterns, we go further and parse the pattern as each kind of thing that we can match.
   6 //! e.g. expressions, type references etc.
   7
   8 use crate::errors::bail;
   9 use crate::{SsrError, SsrPattern, SsrRule};
  10 use rustc_hash::{FxHashMap, FxHashSet};
  11 use std::{fmt::Display, str::FromStr};
  12 use syntax::{ast, AstNode, SmolStr, SyntaxKind, SyntaxNode, T};
  13
  14 #[derive(Debug)]
  15 pub(crate) struct ParsedRule {
  16     pub(crate) placeholders_by_stand_in: FxHashMap<SmolStr, Placeholder>,
  17     pub(crate) pattern: SyntaxNode,
  18     pub(crate) template: Option<SyntaxNode>,
  19 }
  20
  21 #[derive(Debug)]
  22 pub(crate) struct RawPattern {
  23     tokens: Vec<PatternElement>,
  24 }
  25
  26 // Part of a search or replace pattern.
  27 #[derive(Clone, Debug, PartialEq, Eq)]
  28 pub(crate) enum PatternElement {
  29     Token(Token),
  30     Placeholder(Placeholder),
  31 }
  32
  33 #[derive(Clone, Debug, PartialEq, Eq)]
  34 pub(crate) struct Placeholder {
  35     /// The name of this placeholder. e.g. for "$a", this would be "a"
  36     pub(crate) ident: Var,
  37     /// A unique name used in place of this placeholder when we parse the pattern as Rust code.
  38     stand_in_name: String,
  39     pub(crate) constraints: Vec<Constraint>,
  40 }
  41
  42 /// Represents a `$var` in an SSR query.
  43 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
  44 pub(crate) struct Var(pub(crate) String);
  45
  46 #[derive(Clone, Debug, PartialEq, Eq)]
  47 pub(crate) enum Constraint {
  48     Kind(NodeKind),
  49     Not(Box<Constraint>),
  50 }
  51
  52 #[derive(Clone, Debug, PartialEq, Eq)]
  53 pub(crate) enum NodeKind {
  54     Literal,
  55 }
  56
  57 #[derive(Debug, Clone, PartialEq, Eq)]
  58 pub(crate) struct Token {
  59     kind: SyntaxKind,
  60     pub(crate) text: SmolStr,
  61 }
  62
  63 impl ParsedRule {
  64     fn new(
  65         pattern: &RawPattern,
  66         template: Option<&RawPattern>,
  67     ) -> Result<Vec<ParsedRule>, SsrError> {
  68         let raw_pattern = pattern.as_rust_code();
  69         let raw_template = template.map(|t| t.as_rust_code());
  70         let raw_template = raw_template.as_deref();
  71         let mut builder = RuleBuilder {
  72             placeholders_by_stand_in: pattern.placeholders_by_stand_in(),
  73             rules: Vec::new(),
  74         };
  75
  76         let raw_template_stmt = raw_template.map(ast::Stmt::parse);
  77         if let raw_template_expr @ Some(Ok(_)) = raw_template.map(ast::Expr::parse) {
  78             builder.try_add(ast::Expr::parse(&raw_pattern), raw_template_expr);
  79         } else {
  80             builder.try_add(ast::Expr::parse(&raw_pattern), raw_template_stmt.clone());
  81         }
  82         builder.try_add(ast::Type::parse(&raw_pattern), raw_template.map(ast::Type::parse));
  83         builder.try_add(ast::Item::parse(&raw_pattern), raw_template.map(ast::Item::parse));
  84         builder.try_add(ast::Path::parse(&raw_pattern), raw_template.map(ast::Path::parse));
  85         builder.try_add(ast::Pat::parse(&raw_pattern), raw_template.map(ast::Pat::parse));
  86         builder.try_add(ast::Stmt::parse(&raw_pattern), raw_template_stmt);
  87         builder.build()
  88     }
  89 }
  90
  91 struct RuleBuilder {
  92     placeholders_by_stand_in: FxHashMap<SmolStr, Placeholder>,
  93     rules: Vec<ParsedRule>,
  94 }
  95
  96 impl RuleBuilder {
  97     fn try_add<T: AstNode, T2: AstNode>(
  98         &mut self,
  99         pattern: Result<T, ()>,
 100         template: Option<Result<T2, ()>>,
 101     ) {
 102         match (pattern, template) {
 103             (Ok(pattern), Some(Ok(template))) => self.rules.push(ParsedRule {
 104                 placeholders_by_stand_in: self.placeholders_by_stand_in.clone(),
 105                 pattern: pattern.syntax().clone(),
 106                 template: Some(template.syntax().clone()),
 107             }),
 108             (Ok(pattern), None) => self.rules.push(ParsedRule {
 109                 placeholders_by_stand_in: self.placeholders_by_stand_in.clone(),
 110                 pattern: pattern.syntax().clone(),
 111                 template: None,
 112             }),
 113             _ => {}
 114         }
 115     }
 116
 117     fn build(mut self) -> Result<Vec<ParsedRule>, SsrError> {
 118         if self.rules.is_empty() {
 119             bail!("Not a valid Rust expression, type, item, path or pattern");
 120         }
 121         // If any rules contain paths, then we reject any rules that don't contain paths. Allowing a
 122         // mix leads to strange semantics, since the path-based rules only match things where the
 123         // path refers to semantically the same thing, whereas the non-path-based rules could match
 124         // anything. Specifically, if we have a rule like `foo ==>> bar` we only want to match the
 125         // `foo` that is in the current scope, not any `foo`. However "foo" can be parsed as a
 126         // pattern (IDENT_PAT -> NAME -> IDENT). Allowing such a rule through would result in
 127         // renaming everything called `foo` to `bar`. It'd also be slow, since without a path, we'd
 128         // have to use the slow-scan search mechanism.
 129         if self.rules.iter().any(|rule| contains_path(&rule.pattern)) {
 130             let old_len = self.rules.len();
 131             self.rules.retain(|rule| contains_path(&rule.pattern));
 132             if self.rules.len() < old_len {
 133                 cov_mark::hit!(pattern_is_a_single_segment_path);
 134             }
 135         }
 136         Ok(self.rules)
 137     }
 138 }
 139
 140 /// Returns whether there are any paths in `node`.
 141 fn contains_path(node: &SyntaxNode) -> bool {
 142     node.kind() == SyntaxKind::PATH
 143         || node.descendants().any(|node| node.kind() == SyntaxKind::PATH)
 144 }
 145
 146 impl FromStr for SsrRule {
 147     type Err = SsrError;
 148
 149     fn from_str(query: &str) -> Result<SsrRule, SsrError> {
 150         let mut it = query.split("==>>");
 151         let pattern = it.next().expect("at least empty string").trim();
 152         let template = it
 153             .next()
 154             .ok_or_else(|| SsrError("Cannot find delimiter `==>>`".into()))?
 155             .trim()
 156             .to_string();
 157         if it.next().is_some() {
 158             return Err(SsrError("More than one delimiter found".into()));
 159         }
 160         let raw_pattern = pattern.parse()?;
 161         let raw_template = template.parse()?;
 162         let parsed_rules = ParsedRule::new(&raw_pattern, Some(&raw_template))?;
 163         let rule = SsrRule { pattern: raw_pattern, template: raw_template, parsed_rules };
 164         validate_rule(&rule)?;
 165         Ok(rule)
 166     }
 167 }
 168
 169 impl FromStr for RawPattern {
 170     type Err = SsrError;
 171
 172     fn from_str(pattern_str: &str) -> Result<RawPattern, SsrError> {
 173         Ok(RawPattern { tokens: parse_pattern(pattern_str)? })
 174     }
 175 }
 176
 177 impl RawPattern {
 178     /// Returns this search pattern as Rust source code that we can feed to the Rust parser.
 179     fn as_rust_code(&self) -> String {
 180         let mut res = String::new();
 181         for t in &self.tokens {
 182             res.push_str(match t {
 183                 PatternElement::Token(token) => token.text.as_str(),
 184                 PatternElement::Placeholder(placeholder) => placeholder.stand_in_name.as_str(),
 185             });
 186         }
 187         res
 188     }
 189
 190     pub(crate) fn placeholders_by_stand_in(&self) -> FxHashMap<SmolStr, Placeholder> {
 191         let mut res = FxHashMap::default();
 192         for t in &self.tokens {
 193             if let PatternElement::Placeholder(placeholder) = t {
 194                 res.insert(SmolStr::new(placeholder.stand_in_name.clone()), placeholder.clone());
 195             }
 196         }
 197         res
 198     }
 199 }
 200
 201 impl FromStr for SsrPattern {
 202     type Err = SsrError;
 203
 204     fn from_str(pattern_str: &str) -> Result<SsrPattern, SsrError> {
 205         let raw_pattern = pattern_str.parse()?;
 206         let parsed_rules = ParsedRule::new(&raw_pattern, None)?;
 207         Ok(SsrPattern { parsed_rules })
 208     }
 209 }
 210
 211 /// Returns `pattern_str`, parsed as a search or replace pattern. If `remove_whitespace` is true,
 212 /// then any whitespace tokens will be removed, which we do for the search pattern, but not for the
 213 /// replace pattern.
 214 fn parse_pattern(pattern_str: &str) -> Result<Vec<PatternElement>, SsrError> {
 215     let mut res = Vec::new();
 216     let mut placeholder_names = FxHashSet::default();
 217     let mut tokens = tokenize(pattern_str)?.into_iter();
 218     while let Some(token) = tokens.next() {
 219         if token.kind == T![$] {
 220             let placeholder = parse_placeholder(&mut tokens)?;
 221             if !placeholder_names.insert(placeholder.ident.clone()) {
 222                 bail!("Placeholder `{}` repeats more than once", placeholder.ident);
 223             }
 224             res.push(PatternElement::Placeholder(placeholder));
 225         } else {
 226             res.push(PatternElement::Token(token));
 227         }
 228     }
 229     Ok(res)
 230 }
 231
 232 /// Checks for errors in a rule. e.g. the replace pattern referencing placeholders that the search
 233 /// pattern didn't define.
 234 fn validate_rule(rule: &SsrRule) -> Result<(), SsrError> {
 235     let mut defined_placeholders = FxHashSet::default();
 236     for p in &rule.pattern.tokens {
 237         if let PatternElement::Placeholder(placeholder) = p {
 238             defined_placeholders.insert(&placeholder.ident);
 239         }
 240     }
 241     let mut undefined = Vec::new();
 242     for p in &rule.template.tokens {
 243         if let PatternElement::Placeholder(placeholder) = p {
 244             if !defined_placeholders.contains(&placeholder.ident) {
 245                 undefined.push(placeholder.ident.to_string());
 246             }
 247             if !placeholder.constraints.is_empty() {
 248                 bail!("Replacement placeholders cannot have constraints");
 249             }
 250         }
 251     }
 252     if !undefined.is_empty() {
 253         bail!("Replacement contains undefined placeholders: {}", undefined.join(", "));
 254     }
 255     Ok(())
 256 }
 257
 258 fn tokenize(source: &str) -> Result<Vec<Token>, SsrError> {
 259     let mut start = 0;
 260     let (raw_tokens, errors) = syntax::tokenize(source);
 261     if let Some(first_error) = errors.first() {
 262         bail!("Failed to parse pattern: {}", first_error);
 263     }
 264     let mut tokens: Vec<Token> = Vec::new();
 265     for raw_token in raw_tokens {
 266         let token_len = usize::from(raw_token.len);
 267         tokens.push(Token {
 268             kind: raw_token.kind,
 269             text: SmolStr::new(&source[start..start + token_len]),
 270         });
 271         start += token_len;
 272     }
 273     Ok(tokens)
 274 }
 275
 276 fn parse_placeholder(tokens: &mut std::vec::IntoIter<Token>) -> Result<Placeholder, SsrError> {
 277     let mut name = None;
 278     let mut constraints = Vec::new();
 279     if let Some(token) = tokens.next() {
 280         match token.kind {
 281             SyntaxKind::IDENT => {
 282                 name = Some(token.text);
 283             }
 284             T!['{'] => {
 285                 let token =
 286                     tokens.next().ok_or_else(|| SsrError::new("Unexpected end of placeholder"))?;
 287                 if token.kind == SyntaxKind::IDENT {
 288                     name = Some(token.text);
 289                 }
 290                 loop {
 291                     let token = tokens
 292                         .next()
 293                         .ok_or_else(|| SsrError::new("Placeholder is missing closing brace '}'"))?;
 294                     match token.kind {
 295                         T![:] => {
 296                             constraints.push(parse_constraint(tokens)?);
 297                         }
 298                         T!['}'] => break,
 299                         _ => bail!("Unexpected token while parsing placeholder: '{}'", token.text),
 300                     }
 301                 }
 302             }
 303             _ => {
 304                 bail!("Placeholders should either be $name or ${{name:constraints}}");
 305             }
 306         }
 307     }
 308     let name = name.ok_or_else(|| SsrError::new("Placeholder ($) with no name"))?;
 309     Ok(Placeholder::new(name, constraints))
 310 }
 311
 312 fn parse_constraint(tokens: &mut std::vec::IntoIter<Token>) -> Result<Constraint, SsrError> {
 313     let constraint_type = tokens
 314         .next()
 315         .ok_or_else(|| SsrError::new("Found end of placeholder while looking for a constraint"))?
 316         .text
 317         .to_string();
 318     match constraint_type.as_str() {
 319         "kind" => {
 320             expect_token(tokens, "(")?;
 321             let t = tokens.next().ok_or_else(|| {
 322                 SsrError::new("Unexpected end of constraint while looking for kind")
 323             })?;
 324             if t.kind != SyntaxKind::IDENT {
 325                 bail!("Expected ident, found {:?} while parsing kind constraint", t.kind);
 326             }
 327             expect_token(tokens, ")")?;
 328             Ok(Constraint::Kind(NodeKind::from(&t.text)?))
 329         }
 330         "not" => {
 331             expect_token(tokens, "(")?;
 332             let sub = parse_constraint(tokens)?;
 333             expect_token(tokens, ")")?;
 334             Ok(Constraint::Not(Box::new(sub)))
 335         }
 336         x => bail!("Unsupported constraint type '{}'", x),
 337     }
 338 }
 339
 340 fn expect_token(tokens: &mut std::vec::IntoIter<Token>, expected: &str) -> Result<(), SsrError> {
 341     if let Some(t) = tokens.next() {
 342         if t.text == expected {
 343             return Ok(());
 344         }
 345         bail!("Expected {} found {}", expected, t.text);
 346     }
 347     bail!("Expected {} found end of stream", expected);
 348 }
 349
 350 impl NodeKind {
 351     fn from(name: &SmolStr) -> Result<NodeKind, SsrError> {
 352         Ok(match name.as_str() {
 353             "literal" => NodeKind::Literal,
 354             _ => bail!("Unknown node kind '{}'", name),
 355         })
 356     }
 357 }
 358
 359 impl Placeholder {
 360     fn new(name: SmolStr, constraints: Vec<Constraint>) -> Self {
 361         Self {
 362             stand_in_name: format!("__placeholder_{}", name),
 363             constraints,
 364             ident: Var(name.to_string()),
 365         }
 366     }
 367 }
 368
 369 impl Display for Var {
 370     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
 371         write!(f, "${}", self.0)
 372     }
 373 }
 374
 375 #[cfg(test)]
 376 mod tests {
 377     use super::*;
 378
 379     #[test]
 380     fn parser_happy_case() {
 381         fn token(kind: SyntaxKind, text: &str) -> PatternElement {
 382             PatternElement::Token(Token { kind, text: SmolStr::new(text) })
 383         }
 384         fn placeholder(name: &str) -> PatternElement {
 385             PatternElement::Placeholder(Placeholder::new(SmolStr::new(name), Vec::new()))
 386         }
 387         let result: SsrRule = "foo($a, $b) ==>> bar($b, $a)".parse().unwrap();
 388         assert_eq!(
 389             result.pattern.tokens,
 390             vec![
 391                 token(SyntaxKind::IDENT, "foo"),
 392                 token(T!['('], "("),
 393                 placeholder("a"),
 394                 token(T![,], ","),
 395                 token(SyntaxKind::WHITESPACE, " "),
 396                 placeholder("b"),
 397                 token(T![')'], ")"),
 398             ]
 399         );
 400         assert_eq!(
 401             result.template.tokens,
 402             vec![
 403                 token(SyntaxKind::IDENT, "bar"),
 404                 token(T!['('], "("),
 405                 placeholder("b"),
 406                 token(T![,], ","),
 407                 token(SyntaxKind::WHITESPACE, " "),
 408                 placeholder("a"),
 409                 token(T![')'], ")"),
 410             ]
 411         );
 412     }
 413 }