swiftlang / swiftlang/swift-syntax

Incremental parsing loses lookahead ranges when reusing syntax nodes

Open
#3,397 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Swift
Stars
3.7k
Forks
553
Avg merge
5d 13h
Merged PRs (30d)
16

Description

### Description

While I was learning about how incremental parsing works together with Codex, I noticed that lookahead ranges were not preserved when registering a reused node for future reuse. I then had Codex write a unit test (see below) which reproduces this issue. Even though Codex wrote the unit test I have manually looked at it and verified that it actually reproduce a real bug.

Given this source:
```swift
foo() {}
label: switch x {
default: break
}
bar() {}
```
While parsing the code block item that contains `foo() {}`, the parser looks ahead to determine that `label:` does not begin a labeled trailing closure. This fact is then included in the node's recorded lookahead range.

When doing an unrelated edit (like replacing `bar` with `baz`) the code block item for `foo` is reused. However, when that reused node is registered for (potential) reuse in the next incremental parse, however, its original lookahead range is not preserved.

If a subsequent edit replaces
```swift
switch x {
default: break
}
```
with
```swift
{}
```
`label: {}` becomes a valid labeled trailing closure for the `foo` function call. The code block item should thus be reparsed. But because the lookahead range was not preserved, the edit does not intersect the range of the code block item, and it is incorrectly reused. As a result, incremental parsing produces a different syntax tree from the final source from scratch.

If the same replacement is performed immediately after the initial parse, the node is correctly invalidated because the original lookahead range still intersects the edit.

### Steps to Reproduce

Unit test to reproduce this issue:
```swift
public func testLookaheadRangeDoesNotShrinkWhenNodeIsReused() {
func replacing(_ oldText: String, with newText: String, in source: String) -> (String, SourceEdit) {
let range = source.range(of: oldText)!
let lowerBound = source.utf8.distance(
from: source.utf8.startIndex,
to: range.lowerBound.samePosition(in: source.utf8)!
)
let upperBound = source.utf8.distance(
from: source.utf8.startIndex,
to: range.upperBound.samePosition(in: source.utf8)!
)
var editedSource = source
editedSource.replaceSubrange(range, with: newText)
return (
editedSource,
SourceEdit(
range: AbsolutePosition(utf8Offset: lowerBound)..

Contributor guide

Open the contributing guide

Research direction

Start with the supplied testLookaheadRangeDoesNotShrinkWhenNodeIsReused reproducer and run the incremental parsing tests. Trace how reused nodes are registered for the next parse and how their recorded lookahead ranges are carried forward. Done means the test passes and incremental parsing produces the same tree as parsing the final source from scratch.

Written by the indexing model from the issue text.

Assessment

Tech stack
swift
Domain
compilers
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
68/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.