SyntaxToken.GetNextToken is very slow for long Child/Token lists - which causes SyntaxNormalizer to be slow as well
#72,861 opened on Apr 3, 2024
Repository metrics
- Stars
- (20,414 stars)
- PR merge metrics
- (Avg merge 6d 17h) (256 merged PRs in 30d)
Description
Version Used:
Steps to Reproduce: Parse the following code with a long array initializer - and Normalize whitespace.
Expected Behavior: It should terminate in a reasonable time.
Actual Behavior: Computes like forever
The performance hit seems to be caused mainly by SyntaxNavigator.GetNextToken which is called by SyntaxNormalizer.GetNextRelevantToken. To skip the previous tokens it simply iterates over all childs and tokens until it finds itself. For small token lists this is fine - but for long lists this algorithm is very bad. Couldn't we do for example something like binary search based on the token positon / span?
In addition: To iterate over the nodes it calls SyntaxNode.ChildNodesAndTokens() - which needs to compute the count all the time.
Close to that function is ChildThatContainsPosition() which seems to be very much faster - perhaps we could use that function ...