Commit `82470d4f89`

Niles Salter <Validark@pm.me>

2023-06-21 05:05:12

[priority_dequeue] Fix out-of-bounds access

This makes it so `first_child_index` will not be accessed when it is equal to `self.len`. (i.e. `self.items[self.len]` will not happen) The access itself was "safe" (as in, `self.len < self.items.len`) because we were only calling `doSiftDown` in the case where there was a stale value at `self.items[self.len]`. However, it is still technically a bug, and can manifest by an unnecessary comparison of a value to a copy of itself.

master

1 parent ff58501

Changed files (1)

lib

std

priority_dequeue.zig

@@ -230,7 +230,7 @@ pub fn PriorityDequeue(comptime T: type, comptime Context: type, comptime compar
                 } else {
                     // The children or grandchildren are the last layer
                     const first_child_index = firstChildIndex(index);
-                    if (first_child_index > self.len) return;
+                    if (first_child_index >= self.len) return;
 
                     const best_descendent = self.bestDescendent(first_child_index, first_grandchild_index, target_order);
 
@@ -1002,3 +1002,25 @@ test "std.PriorityDequeue: add and remove" {
     try expectEqual(@as(usize, 2), queue.removeMax());
     try expectEqual(@as(usize, 1), queue.removeMin());
 }
+
+var all_cmps_unique = true;
+
+test "std.PriorityDeque: don't compare a value to a copy of itself" {
+    var depq = PriorityDequeue(u32, void, struct {
+        fn uniqueLessThan(_: void, a: u32, b: u32) Order {
+            all_cmps_unique = all_cmps_unique and (a != b);
+            return std.math.order(a, b);
+        }
+    }.uniqueLessThan).init(testing.allocator, {});
+    defer depq.deinit();
+
+    try depq.add(1);
+    try depq.add(2);
+    try depq.add(3);
+    try depq.add(4);
+    try depq.add(5);
+    try depq.add(6);
+
+    _ = depq.removeIndex(2);
+    try expectEqual(all_cmps_unique, true);
+}

Commit 82470d4f89

Commit `82470d4f89`