crates/syntax/src/parsing/reparsing.rs

   1 //! Implementation of incremental re-parsing.
   2 //!
   3 //! We use two simple strategies for this:
   4 //!   - if the edit modifies only a single token (like changing an identifier's
   5 //!     letter), we replace only this token.
   6 //!   - otherwise, we search for the nearest `{}` block which contains the edit
   7 //!     and try to parse only this block.
   8
   9 use parser::Reparser;
  10 use text_edit::Indel;
  11
  12 use crate::{
  13     parsing::{
  14         lexer::{lex_single_syntax_kind, tokenize, Token},
  15         text_tree_sink::TextTreeSink,
  16         to_parser_tokens,
  17     },
  18     syntax_node::{GreenNode, GreenToken, NodeOrToken, SyntaxElement, SyntaxNode},
  19     SyntaxError,
  20     SyntaxKind::*,
  21     TextRange, TextSize, T,
  22 };
  23
  24 pub(crate) fn incremental_reparse(
  25     node: &SyntaxNode,
  26     edit: &Indel,
  27     errors: Vec<SyntaxError>,
  28 ) -> Option<(GreenNode, Vec<SyntaxError>, TextRange)> {
  29     if let Some((green, new_errors, old_range)) = reparse_token(node, edit) {
  30         return Some((green, merge_errors(errors, new_errors, old_range, edit), old_range));
  31     }
  32
  33     if let Some((green, new_errors, old_range)) = reparse_block(node, edit) {
  34         return Some((green, merge_errors(errors, new_errors, old_range, edit), old_range));
  35     }
  36     None
  37 }
  38
  39 fn reparse_token(
  40     root: &SyntaxNode,
  41     edit: &Indel,
  42 ) -> Option<(GreenNode, Vec<SyntaxError>, TextRange)> {
  43     let prev_token = root.covering_element(edit.delete).as_token()?.clone();
  44     let prev_token_kind = prev_token.kind();
  45     match prev_token_kind {
  46         WHITESPACE | COMMENT | IDENT | STRING => {
  47             if prev_token_kind == WHITESPACE || prev_token_kind == COMMENT {
  48                 // removing a new line may extends previous token
  49                 let deleted_range = edit.delete - prev_token.text_range().start();
  50                 if prev_token.text()[deleted_range].contains('\n') {
  51                     return None;
  52                 }
  53             }
  54
  55             let mut new_text = get_text_after_edit(prev_token.clone().into(), edit);
  56             let (new_token_kind, new_err) = lex_single_syntax_kind(&new_text)?;
  57
  58             if new_token_kind != prev_token_kind
  59                 || (new_token_kind == IDENT && is_contextual_kw(&new_text))
  60             {
  61                 return None;
  62             }
  63
  64             // Check that edited token is not a part of the bigger token.
  65             // E.g. if for source code `bruh"str"` the user removed `ruh`, then
  66             // `b` no longer remains an identifier, but becomes a part of byte string literal
  67             if let Some(next_char) = root.text().char_at(prev_token.text_range().end()) {
  68                 new_text.push(next_char);
  69                 let token_with_next_char = lex_single_syntax_kind(&new_text);
  70                 if let Some((_kind, _error)) = token_with_next_char {
  71                     return None;
  72                 }
  73                 new_text.pop();
  74             }
  75
  76             let new_token = GreenToken::new(rowan::SyntaxKind(prev_token_kind.into()), &new_text);
  77             Some((
  78                 prev_token.replace_with(new_token),
  79                 new_err.into_iter().collect(),
  80                 prev_token.text_range(),
  81             ))
  82         }
  83         _ => None,
  84     }
  85 }
  86
  87 fn reparse_block(
  88     root: &SyntaxNode,
  89     edit: &Indel,
  90 ) -> Option<(GreenNode, Vec<SyntaxError>, TextRange)> {
  91     let (node, reparser) = find_reparsable_node(root, edit.delete)?;
  92     let text = get_text_after_edit(node.clone().into(), edit);
  93
  94     let (lexer_tokens, new_lexer_errors) = tokenize(&text);
  95     if !is_balanced(&lexer_tokens) {
  96         return None;
  97     }
  98     let parser_tokens = to_parser_tokens(&text, &lexer_tokens);
  99
 100     let mut tree_sink = TextTreeSink::new(&text, &lexer_tokens);
 101     reparser.parse(&parser_tokens, &mut tree_sink);
 102
 103     let (green, mut new_parser_errors) = tree_sink.finish();
 104     new_parser_errors.extend(new_lexer_errors);
 105
 106     Some((node.replace_with(green), new_parser_errors, node.text_range()))
 107 }
 108
 109 fn get_text_after_edit(element: SyntaxElement, edit: &Indel) -> String {
 110     let edit = Indel::replace(edit.delete - element.text_range().start(), edit.insert.clone());
 111
 112     let mut text = match element {
 113         NodeOrToken::Token(token) => token.text().to_string(),
 114         NodeOrToken::Node(node) => node.text().to_string(),
 115     };
 116     edit.apply(&mut text);
 117     text
 118 }
 119
 120 fn is_contextual_kw(text: &str) -> bool {
 121     matches!(text, "auto" | "default" | "union")
 122 }
 123
 124 fn find_reparsable_node(node: &SyntaxNode, range: TextRange) -> Option<(SyntaxNode, Reparser)> {
 125     let node = node.covering_element(range);
 126
 127     node.ancestors().find_map(|node| {
 128         let first_child = node.first_child_or_token().map(|it| it.kind());
 129         let parent = node.parent().map(|it| it.kind());
 130         Reparser::for_node(node.kind(), first_child, parent).map(|r| (node, r))
 131     })
 132 }
 133
 134 fn is_balanced(tokens: &[Token]) -> bool {
 135     if tokens.is_empty()
 136         || tokens.first().unwrap().kind != T!['{']
 137         || tokens.last().unwrap().kind != T!['}']
 138     {
 139         return false;
 140     }
 141     let mut balance = 0usize;
 142     for t in &tokens[1..tokens.len() - 1] {
 143         match t.kind {
 144             T!['{'] => balance += 1,
 145             T!['}'] => {
 146                 balance = match balance.checked_sub(1) {
 147                     Some(b) => b,
 148                     None => return false,
 149                 }
 150             }
 151             _ => (),
 152         }
 153     }
 154     balance == 0
 155 }
 156
 157 fn merge_errors(
 158     old_errors: Vec<SyntaxError>,
 159     new_errors: Vec<SyntaxError>,
 160     range_before_reparse: TextRange,
 161     edit: &Indel,
 162 ) -> Vec<SyntaxError> {
 163     let mut res = Vec::new();
 164
 165     for old_err in old_errors {
 166         let old_err_range = old_err.range();
 167         if old_err_range.end() <= range_before_reparse.start() {
 168             res.push(old_err);
 169         } else if old_err_range.start() >= range_before_reparse.end() {
 170             let inserted_len = TextSize::of(&edit.insert);
 171             res.push(old_err.with_range((old_err_range + inserted_len) - edit.delete.len()));
 172             // Note: extra parens are intentional to prevent uint underflow, HWAB (here was a bug)
 173         }
 174     }
 175     res.extend(new_errors.into_iter().map(|new_err| {
 176         // fighting borrow checker with a variable ;)
 177         let offseted_range = new_err.range() + range_before_reparse.start();
 178         new_err.with_range(offseted_range)
 179     }));
 180     res
 181 }
 182
 183 #[cfg(test)]
 184 mod tests {
 185     use test_utils::{assert_eq_text, extract_range};
 186
 187     use super::*;
 188     use crate::{AstNode, Parse, SourceFile};
 189
 190     fn do_check(before: &str, replace_with: &str, reparsed_len: u32) {
 191         let (range, before) = extract_range(before);
 192         let edit = Indel::replace(range, replace_with.to_owned());
 193         let after = {
 194             let mut after = before.clone();
 195             edit.apply(&mut after);
 196             after
 197         };
 198
 199         let fully_reparsed = SourceFile::parse(&after);
 200         let incrementally_reparsed: Parse<SourceFile> = {
 201             let before = SourceFile::parse(&before);
 202             let (green, new_errors, range) =
 203                 incremental_reparse(before.tree().syntax(), &edit, before.errors.to_vec()).unwrap();
 204             assert_eq!(range.len(), reparsed_len.into(), "reparsed fragment has wrong length");
 205             Parse::new(green, new_errors)
 206         };
 207
 208         assert_eq_text!(
 209             &format!("{:#?}", fully_reparsed.tree().syntax()),
 210             &format!("{:#?}", incrementally_reparsed.tree().syntax()),
 211         );
 212         assert_eq!(fully_reparsed.errors(), incrementally_reparsed.errors());
 213     }
 214
 215     #[test] // FIXME: some test here actually test token reparsing
 216     fn reparse_block_tests() {
 217         do_check(
 218             r"
 219 fn foo() {
 220     let x = foo + $0bar$0
 221 }
 222 ",
 223             "baz",
 224             3,
 225         );
 226         do_check(
 227             r"
 228 fn foo() {
 229     let x = foo$0 + bar$0
 230 }
 231 ",
 232             "baz",
 233             25,
 234         );
 235         do_check(
 236             r"
 237 struct Foo {
 238     f: foo$0$0
 239 }
 240 ",
 241             ",\n    g: (),",
 242             14,
 243         );
 244         do_check(
 245             r"
 246 fn foo {
 247     let;
 248     1 + 1;
 249     $092$0;
 250 }
 251 ",
 252             "62",
 253             31, // FIXME: reparse only int literal here
 254         );
 255         do_check(
 256             r"
 257 mod foo {
 258     fn $0$0
 259 }
 260 ",
 261             "bar",
 262             11,
 263         );
 264
 265         do_check(
 266             r"
 267 trait Foo {
 268     type $0Foo$0;
 269 }
 270 ",
 271             "Output",
 272             3,
 273         );
 274         do_check(
 275             r"
 276 impl IntoIterator<Item=i32> for Foo {
 277     f$0$0
 278 }
 279 ",
 280             "n next(",
 281             9,
 282         );
 283         do_check(r"use a::b::{foo,$0,bar$0};", "baz", 10);
 284         do_check(
 285             r"
 286 pub enum A {
 287     Foo$0$0
 288 }
 289 ",
 290             "\nBar;\n",
 291             11,
 292         );
 293         do_check(
 294             r"
 295 foo!{a, b$0$0 d}
 296 ",
 297             ", c[3]",
 298             8,
 299         );
 300         do_check(
 301             r"
 302 fn foo() {
 303     vec![$0$0]
 304 }
 305 ",
 306             "123",
 307             14,
 308         );
 309         do_check(
 310             r"
 311 extern {
 312     fn$0;$0
 313 }
 314 ",
 315             " exit(code: c_int)",
 316             11,
 317         );
 318     }
 319
 320     #[test]
 321     fn reparse_token_tests() {
 322         do_check(
 323             r"$0$0
 324 fn foo() -> i32 { 1 }
 325 ",
 326             "\n\n\n   \n",
 327             1,
 328         );
 329         do_check(
 330             r"
 331 fn foo() -> $0$0 {}
 332 ",
 333             "  \n",
 334             2,
 335         );
 336         do_check(
 337             r"
 338 fn $0foo$0() -> i32 { 1 }
 339 ",
 340             "bar",
 341             3,
 342         );
 343         do_check(
 344             r"
 345 fn foo$0$0foo() {  }
 346 ",
 347             "bar",
 348             6,
 349         );
 350         do_check(
 351             r"
 352 fn foo /* $0$0 */ () {}
 353 ",
 354             "some comment",
 355             6,
 356         );
 357         do_check(
 358             r"
 359 fn baz $0$0 () {}
 360 ",
 361             "    \t\t\n\n",
 362             2,
 363         );
 364         do_check(
 365             r"
 366 fn baz $0$0 () {}
 367 ",
 368             "    \t\t\n\n",
 369             2,
 370         );
 371         do_check(
 372             r"
 373 /// foo $0$0omment
 374 mod { }
 375 ",
 376             "c",
 377             14,
 378         );
 379         do_check(
 380             r#"
 381 fn -> &str { "Hello$0$0" }
 382 "#,
 383             ", world",
 384             7,
 385         );
 386         do_check(
 387             r#"
 388 fn -> &str { // "Hello$0$0"
 389 "#,
 390             ", world",
 391             10,
 392         );
 393         do_check(
 394             r##"
 395 fn -> &str { r#"Hello$0$0"#
 396 "##,
 397             ", world",
 398             10,
 399         );
 400         do_check(
 401             r"
 402 #[derive($0Copy$0)]
 403 enum Foo {
 404
 405 }
 406 ",
 407             "Clone",
 408             4,
 409         );
 410     }
 411
 412     #[test]
 413     fn reparse_str_token_with_error_unchanged() {
 414         do_check(r#""$0Unclosed$0 string literal"#, "Still unclosed", 24);
 415     }
 416
 417     #[test]
 418     fn reparse_str_token_with_error_fixed() {
 419         do_check(r#""unterinated$0$0"#, "\"", 12);
 420     }
 421
 422     #[test]
 423     fn reparse_block_with_error_in_middle_unchanged() {
 424         do_check(
 425             r#"fn main() {
 426                 if {}
 427                 32 + 4$0$0
 428                 return
 429                 if {}
 430             }"#,
 431             "23",
 432             105,
 433         )
 434     }
 435
 436     #[test]
 437     fn reparse_block_with_error_in_middle_fixed() {
 438         do_check(
 439             r#"fn main() {
 440                 if {}
 441                 32 + 4$0$0
 442                 return
 443                 if {}
 444             }"#,
 445             ";",
 446             105,
 447         )
 448     }
 449 }