experimental HiFi tree diff algorithm for use with quick-fixes and refactoring commands in the IDE

[jurgenvinju]

This transforms a pair of parse Trees <original, rewritten> to a list[TextEdit]s. The resulting TextEdits are ready for use in VScode extensions via LSP features in util::LanguageServer and util::IDEServices.

The single pass parse tree recursion maps sub-tree and sub-list differences to textual differences in a special way. It lifts on the semantics of special parse tree non-terminals (literals, lexicals, separators) to ignore certain superfluous changes made in the rewritten tree. As a result the edited source text retains more of its original layout, including indentation and comments, as compared to yielding the rewritten parse tree to a string and replacing the entire file.

Especially with separated lists this algorithm does amazing work. Suppose you have a target pattern: <Element e>, <{Element ","}* newElems, <Element f> and newElems happens to be empty, then:

1. Rascal will remove the superfluous separators and layout around the empty list.
2. HifiTreeDiff will try and keep indentation and source code comments after the e and before the f even though these have been replaced by the concrete target pattern.
3. If the list is non-empty, also the layout before the new sublist and after the new sublist will be taken from the original list where possible.

The smaller diffs are not only good for high-fidelity in general, but also in particular smaller diffs are essential for providing interactive preview and undo features in the IDE. This PR enables language engineers to use parse tree rewriting rather than collecting the text edits themselves.

TODO's:

• [ ] write test, and fix initial issues triggered by the tests
• [ ] test the example in the documentation
• [ ] shorten the documentation
• [x] document the TextEdits module
• [x] short-circuit lexical identifiers (do not go deeper)
• [x] write indentation inheritance algorithm

[codecov[bot]]

Codecov Report

:x: Patch coverage is 80.00000% with 1 line in your changes missing coverage. Please review. :white_check_mark: Project coverage is 47%. Comparing base (2c284f1) to head (afbb402). :warning: Report is 85 commits behind head on main.

Files with missing lines	Patch %	Lines
src/org/rascalmpl/types/NonTerminalType.java	50%	0 Missing and 1 partial :warning:

Additional details and impacted files

@@           Coverage Diff           @@
##              main   #2031   +/-   ##
=======================================
  Coverage       47%     47%           
- Complexity    6492    6505   +13     
=======================================
  Files          780     780           
  Lines        64429   64434    +5     
  Branches      9594    9596    +2     
=======================================
+ Hits         30282   30311   +29     
+ Misses       31856   31834   -22     
+ Partials      2291    2289    -2     

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

:rocket: New features to boost your workflow:

• :snowflake: Test Analytics: Detect flaky tests, report on failures, and find test suite problems.
• :package: JS Bundle Analysis: Save yourself from yourself by tracking and limiting bundle sizes in JS merges.

[jurgenvinju]

@tvdstorm @DavyLandman I don't have the energy to finish this now, so I'm parking it here until I do. I wanted you to know it exists, because low-fidelity rewrites are a common issue we have to solve and because refactoring and quick-fixes in VScode are now under our fingertips.

[DavyLandman]

Cool stuff :+1:

[jurgenvinju]

The static checker chokes on the new code in ParseTree.rsc:

Error: [ERROR]   RunTests.onlyChangedModulesAreReChecked1: <18024,1205> » Throw /home/runner/actions-runner/_work/rascal/rascal/src/org/rascalmpl/compiler/lang/rascalcore/check/tests/StaticTestingUtils.rsc:168,26: "{error(\"Invalid type: expected node, ADT, or concrete syntax types, found `![]`\",|tmp:///rascal/src/org/rascalmpl/library/ParseTree.rsc|(47720,84,\<972,10\>,\<972,94\>),fixes=[])}"
Error: [ERROR]   RunTests.onlyTouchedModulesAreReChecked1: <15213,521> » Throw /home/runner/actions-runner/_work/rascal/rascal/src/org/rascalmpl/compiler/lang/rascalcore/check/tests/StaticTestingUtils.rsc:168,26: "{error(\"Invalid type: expected node, ADT, or concrete syntax types, found `![]`\",|tmp:///rascal/src/org/rascalmpl/library/ParseTree.rsc|(47720,84,\<972,10\>,\<972,94\>),fixes=[])}"

• [x] report the bug #2342
• [x] rewrite the code to work around it