fix(graph): use round-based topological sort in sortNodeIDsWithPriority#235
Conversation
✅ Deploy Preview for devsydev canceled.
|
|
Warning Rate limit exceeded
To continue reviewing without waiting, purchase usage credits in the billing tab. ⌛ How to resolve this issue?After the wait time has elapsed, a review can be triggered using the We recommend that you space out your commits to avoid hitting the rate limit. 🚦 How do rate limits work?CodeRabbit enforces hourly rate limits for each developer per organization. Our paid plans have higher rate limits than the trial, open-source and free plans. In all cases, we re-allow further reviews after a brief timeout. Please see our FAQ for further information. ℹ️ Review info⚙️ Run configurationConfiguration used: Organization UI Review profile: CHILL Plan: Pro Run ID: 📒 Files selected for processing (2)
Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out. Comment |
2b5d280 to
d35cf3e
Compare
The single-queue Kahn's algorithm processed one node at a time, which could interleave nodes from different topological levels. This aligns sortNodeIDsWithPriority with the round-based pattern already used by sortNodeIDs — collecting all zero-in-degree nodes per round, sorting within the round by priority, and emitting the full round before advancing.
Adds a test case where the old single-queue algorithm would produce a different (incorrect) ordering by promoting C ahead of B when A frees C mid-queue. The round-based approach correctly emits [A, B] in round 1 and [C] in round 2.
d35cf3e to
8c8018d
Compare
1 participant
Summary
Rewrites
sortNodeIDsWithPriority()to use the same round-based collection pattern assortNodeIDs(). The previous single-queue Kahn's algorithm processed one node at a time, which could emit nodes from later topological levels before all same-level siblings were emitted. The fix collects all zero-in-degree nodes per round, sorts them by priority within the round, and emits the entire round before advancing — matching the spec-required behavior for feature installation ordering.Spec Reference
The devcontainer Features specification describes how features must be installed in dependency order using a round-based topological sort. Specifically,
installsAfteris used to declare explicit ordering constraints between features, and compliant implementations must resolve these dependencies such that all features in a given topological level are processed before advancing to the next. This PR alignssortNodeIDsWithPriority()with that required round-based behavior.