Skip to content

[SortedCollections] Fix B-tree root reduction during element removal causing data loss#507

Merged
lorentey merged 1 commit intoapple:mainfrom
brianchang928:patch
Aug 18, 2025
Merged

[SortedCollections] Fix B-tree root reduction during element removal causing data loss#507
lorentey merged 1 commit intoapple:mainfrom
brianchang928:patch

Conversation

@brianchang928
Copy link
Copy Markdown
Contributor

@brianchang928 brianchang928 commented Aug 14, 2025

When removing elements from a B-tree, the root node could become empty while still having children. The previous code incorrectly just called drop() which deallocated all children, causing massive data loss during removal operations.

This fix implements proper root reduction by moving the single remaining child out of the empty root, then safely dropping the now-empty parent node and promoting the extracted child to become the new root.

This fixes test_modifySubscriptRemoval in SortedDictionaryTests, so we re-enable SortedDictionary tests which now all pass.

Checklist

  • I've read the Contribution Guidelines
  • My contributions are licensed under the Swift license.
  • I've followed the coding style of the rest of the project.
  • I've added tests covering all new code paths my change adds to the project (if appropriate).
  • I've added benchmarks covering new functionality (if appropriate).
  • I've verified that my change does not break any existing tests or introduce unexplained benchmark regressions.
  • I've updated the documentation if necessary.

When removing elements from a B-tree, the root node could become empty while still having children. The previous code incorrectly called drop() which deallocated all children, causing massive data loss during removal operations.

This fix implements proper root reduction by moving the single remaining child out of the empty root, then safely dropping the now-empty parent node and promoting the extracted child to become the new root.

This fixes `test_modifySubscriptRemoval` in `SortedDictionaryTests`, so we re-enable SortedDictionary tests which now all pass.
Copy link
Copy Markdown
Member

@lorentey lorentey left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thank you for resolving these!

@lorentey
Copy link
Copy Markdown
Member

@swift-ci test

@lorentey lorentey merged commit dc55a17 into apple:main Aug 18, 2025
25 checks passed
@brianchang928 brianchang928 deleted the patch branch August 18, 2025 04:37
@lorentey lorentey added this to the 1.3.0 milestone Sep 27, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants