You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Most of BTree's merge methods have subtle bugs in their common subtree detection logic, which can sometimes lead to corrupt results and/or assertions when duplicate keys cross the boundaries of a common subtree.
It is not easy to reproduce this bug using public API, but the following test manages to do it:
func test_Intersection_withModifiedSelf(){vartree=BTree<Int,Int>(order:5)
for i in 0..<10{
for j in 0..<2{
tree.insert((i, j))}}
for i in 0..<10{varother= tree
other.withCursor(atOffset:2* i){ cursor in
cursor.remove(2)}
other.assertValid()lettest= tree.intersection(other)XCTAssertEqual(test.map{ $0.0}, other.map{ $0.0})}}
Merge methods (i.e., set operations) sometimes did not correctly handle duplicate keys at the boundaries of common subtrees.
This is extremely hard to reproduce using conventional means.
Affected methods:
- BTree.distinctUnion
- BTree.subtracting
- BTree.bagSubtracting
- BTree.symmetricDifference
- BTree.bagSymmetricDifference
- BTree.intersection
- BTree.bagIntersection
- BTreeMerger.copyCommonElementsFromSecond
- BTreeMerger.copyMatchingNumberOfCommonElementsFromSecond
- BTreeMerger.skipCommonElements
- BTreeMerger.skipMatchingNumberOfCommonElements
This fixes issue #20.
Sometimes BTree merges considered an entire subtree shared even after they have already processed a non-empty prefix of it. As a result, the prefix tree would be inserted twice into the result, breaking the ordering invariant. This happened when the shared subtree was a suffix tree of one of the input trees. Affected BTree methods: distinctUnion, intersection, and bagIntersection.
When a merging method detected a shared subtree S, and exactly one of the input trees had at least one element immediately following S with the same key as S.last!.key, these extra elements would not be counted as having matching keys across the two input trees. Affected BTree methods: distinctUnion, subtracting, symmetricDifference and intersection.
Most of BTree's merge methods have subtle bugs in their common subtree detection logic, which can sometimes lead to corrupt results and/or assertions when duplicate keys cross the boundaries of a common subtree.
It is not easy to reproduce this bug using public API, but the following test manages to do it:
Results on current master branch:
Note how the returned results are often not even sorted correctly.
The bug affects
distinctUnion
,subtracting
,symmetricDifference
,intersection
, and the new bag variants, but notunion
.The text was updated successfully, but these errors were encountered: