fix(generate): use topological sort for subtype map#4280
fix(generate): use topological sort for subtype map#4280WillLillis merged 1 commit intotree-sitter:masterfrom
Conversation
|
rebase so @amaanq can take a look? |
|
@WillLillis Can you say something about the performance (esp. memory) impact? Also, why isn't the parser generate test being run on this PR? Is this because the crates refactor moved the (Maybe we could run the build workflow generally -- it's relatively quick -- and just gate the generate workflow behind |
|
Testing with some complex grammars (systemverilog, nim) shows no measurable impact on Linux and a ~1% increase on macOS, which is negligible. So this looks good to go. |
|
Backport failed for Please cherry-pick the changes locally and resolve any conflicts. git fetch origin release-0.25
git worktree add -d .worktree/backport-4280-to-release-0.25 origin/release-0.25
cd .worktree/backport-4280-to-release-0.25
git switch --create backport-4280-to-release-0.25
git cherry-pick -x d2e06bf130a479ba90f2657fd67f129e5a9ad69f |
Detailed explanation of the problem in #4277. In short, we need to impose a total ordering when supplying a custom comparator to any of the sort functions in Rust's stdlib, or use a topological sort instead.
I checked our other usages of
sort_byin the project and they appear to already impose a total ordering.tree-sitter generatemay cause a panic in standard library's sort function #4277