search

mitchellh / libxev

libxev is a cross-platform, high-performance event loop that provides abstractions for non-blocking IO, timers, events, and more and works on Linux (io_uring or epoll), macOS (kqueue), and Wasm + WASI. Available as both a Zig and C API.
MIT License
2.07k stars 74 forks source link

Fix dangling next pointer in heap.zig #44

Closed ianic closed 1 year ago

ianic commented 1 year ago

I think that I found a bug in the heap.zig.

I have build a heap which looks like this: before_remove The next action was removing of element 88 (root). That resulted in heap: after_remove Element 92 is both next of 94 and child of 91 which is, I think, wrong. When B next is moved to the A next in the meld function B next pointer should be set to null. After the fix, resulting heap looks like: fixed

ianic commented 1 year ago

Here is full series of insert/removals to produce heap like in PR test case. Starting from empty heap and resulting in this: out

test "build failing heap structure" {
    const Elem = struct {
        const Self = @This();
        value: usize = 0,
        heap: IntrusiveField(Self) = .{},
    };
    const Heap = Intrusive(Elem, void, (struct {
        fn less(ctx: void, a: *Elem, b: *Elem) bool {
            _ = ctx;
            return a.value < b.value;
        }
    }).less);
    var h: Heap = .{ .context = {} };
    var v4296704944: Elem = .{ .value = 1 };
    h.insert(&v4296704944);
    var v4296706424: Elem = .{ .value = 2 };
    h.insert(&v4296706424);
    var v4296934320: Elem = .{ .value = 3 };
    h.insert(&v4296934320);
    var v4296935800: Elem = .{ .value = 4 };
    h.insert(&v4296935800);
    var v4296937280: Elem = .{ .value = 5 };
    h.insert(&v4296937280);
    var v4296938760: Elem = .{ .value = 6 };
    h.insert(&v4296938760);
    var v4296940240: Elem = .{ .value = 7 };
    h.insert(&v4296940240);
    var v4296999856: Elem = .{ .value = 8 };
    h.insert(&v4296999856);
    var v4297001336: Elem = .{ .value = 9 };
    h.insert(&v4297001336);
    var v4297002816: Elem = .{ .value = 10 };
    h.insert(&v4297002816);
    var v4297004296: Elem = .{ .value = 11 };
    h.insert(&v4297004296);
    var v4297005776: Elem = .{ .value = 12 };
    h.insert(&v4297005776);
    var v4297007256: Elem = .{ .value = 13 };
    h.insert(&v4297007256);
    var v4297008736: Elem = .{ .value = 14 };
    h.insert(&v4297008736);
    var v4297010216: Elem = .{ .value = 15 };
    h.insert(&v4297010216);
    var v4297011696: Elem = .{ .value = 16 };
    h.insert(&v4297011696);
    var v4297013176: Elem = .{ .value = 17 };
    h.insert(&v4297013176);
    var v4297014656: Elem = .{ .value = 18 };
    h.insert(&v4297014656);
    var v4298146736: Elem = .{ .value = 19 };
    h.insert(&v4298146736);
    var v4298148216: Elem = .{ .value = 20 };
    h.insert(&v4298148216);
    var v4298149696: Elem = .{ .value = 21 };
    h.insert(&v4298149696);
    var v4298151176: Elem = .{ .value = 22 };
    h.insert(&v4298151176);
    var v4298152656: Elem = .{ .value = 23 };
    h.insert(&v4298152656);
    var v4298154136: Elem = .{ .value = 24 };
    h.insert(&v4298154136);
    var v4298155616: Elem = .{ .value = 25 };
    h.insert(&v4298155616);
    var v4298157096: Elem = .{ .value = 26 };
    h.insert(&v4298157096);
    var v4298158576: Elem = .{ .value = 27 };
    h.insert(&v4298158576);
    var v4298160056: Elem = .{ .value = 28 };
    h.insert(&v4298160056);
    var v4298161536: Elem = .{ .value = 29 };
    h.insert(&v4298161536);
    var v4298163016: Elem = .{ .value = 30 };
    h.insert(&v4298163016);
    var v4298164496: Elem = .{ .value = 31 };
    h.insert(&v4298164496);
    var v4298165976: Elem = .{ .value = 32 };
    h.insert(&v4298165976);
    var v4298167456: Elem = .{ .value = 33 };
    h.insert(&v4298167456);
    var v4298168936: Elem = .{ .value = 34 };
    h.insert(&v4298168936);
    var v4298170416: Elem = .{ .value = 35 };
    h.insert(&v4298170416);
    var v4298171896: Elem = .{ .value = 36 };
    h.insert(&v4298171896);
    var v4298173376: Elem = .{ .value = 37 };
    h.insert(&v4298173376);
    var v4298174856: Elem = .{ .value = 38 };
    h.insert(&v4298174856);
    var v4298176336: Elem = .{ .value = 39 };
    h.insert(&v4298176336);
    var v4298177816: Elem = .{ .value = 40 };
    h.insert(&v4298177816);
    var v4298261424: Elem = .{ .value = 41 };
    h.insert(&v4298261424);
    var v4298262904: Elem = .{ .value = 42 };
    h.insert(&v4298262904);
    var v4298264384: Elem = .{ .value = 43 };
    h.insert(&v4298264384);
    var v4298265864: Elem = .{ .value = 44 };
    h.insert(&v4298265864);
    var v4298267344: Elem = .{ .value = 45 };
    h.insert(&v4298267344);
    var v4298268824: Elem = .{ .value = 46 };
    h.insert(&v4298268824);
    var v4298270304: Elem = .{ .value = 47 };
    h.insert(&v4298270304);
    var v4298271784: Elem = .{ .value = 48 };
    h.insert(&v4298271784);
    var v4298273264: Elem = .{ .value = 49 };
    h.insert(&v4298273264);
    var v4298274744: Elem = .{ .value = 50 };
    h.insert(&v4298274744);
    var v4298276224: Elem = .{ .value = 51 };
    h.insert(&v4298276224);
    var v4298277704: Elem = .{ .value = 52 };
    h.insert(&v4298277704);
    var v4298279184: Elem = .{ .value = 53 };
    h.insert(&v4298279184);
    var v4298280664: Elem = .{ .value = 54 };
    h.insert(&v4298280664);
    var v4298282144: Elem = .{ .value = 55 };
    h.insert(&v4298282144);
    var v4298283624: Elem = .{ .value = 56 };
    h.insert(&v4298283624);
    var v4298285104: Elem = .{ .value = 57 };
    h.insert(&v4298285104);
    var v4298286584: Elem = .{ .value = 58 };
    h.insert(&v4298286584);
    var v4298288064: Elem = .{ .value = 59 };
    h.insert(&v4298288064);
    var v4298289544: Elem = .{ .value = 60 };
    h.insert(&v4298289544);
    var v4298291024: Elem = .{ .value = 61 };
    h.insert(&v4298291024);
    var v4298292504: Elem = .{ .value = 62 };
    h.insert(&v4298292504);
    var v4298293984: Elem = .{ .value = 63 };
    h.insert(&v4298293984);
    var v4298295464: Elem = .{ .value = 64 };
    h.insert(&v4298295464);
    h.remove(&v4296704944);
    var v4298296944: Elem = .{ .value = 65 };
    h.insert(&v4298296944);
    var v4298298424: Elem = .{ .value = 66 };
    h.insert(&v4298298424);
    var v4298299904: Elem = .{ .value = 67 };
    h.insert(&v4298299904);
    h.remove(&v4296706424);
    var v4298301384: Elem = .{ .value = 68 };
    h.insert(&v4298301384);
    var v4298302864: Elem = .{ .value = 69 };
    h.insert(&v4298302864);
    var v4296704944_: Elem = .{ .value = 70 };
    h.insert(&v4296704944_);
    var v4298304344: Elem = .{ .value = 71 };
    h.insert(&v4298304344);
    var v4298305824: Elem = .{ .value = 72 };
    h.insert(&v4298305824);
    h.remove(&v4296934320);
    h.remove(&v4296935800);
    h.remove(&v4296937280);
    h.remove(&v4296938760);
    var v4296706424_: Elem = .{ .value = 73 };
    h.insert(&v4296706424_);
    var v4298307304: Elem = .{ .value = 74 };
    h.insert(&v4298307304);
    var v4298308784: Elem = .{ .value = 75 };
    h.insert(&v4298308784);
    h.remove(&v4296940240);
    h.remove(&v4296999856);
    var v4298310264: Elem = .{ .value = 76 };
    h.insert(&v4298310264);
    var v4298311744: Elem = .{ .value = 77 };
    h.insert(&v4298311744);
    h.remove(&v4297001336);
    var v4296938760_: Elem = .{ .value = 78 };
    h.insert(&v4296938760_);
    var v4296937280_: Elem = .{ .value = 79 };
    h.insert(&v4296937280_);
    var v4296935800_: Elem = .{ .value = 80 };
    h.insert(&v4296935800_);
    var v4296934320_: Elem = .{ .value = 81 };
    h.insert(&v4296934320_);
    h.remove(&v4297002816);
    h.remove(&v4297004296);
    h.remove(&v4297005776);
    var v4296999856_: Elem = .{ .value = 82 };
    h.insert(&v4296999856_);
    var v4296940240_: Elem = .{ .value = 83 };
    h.insert(&v4296940240_);
    h.remove(&v4297007256);
    var v4297001336_: Elem = .{ .value = 84 };
    h.insert(&v4297001336_);
    var v4298313224: Elem = .{ .value = 85 };
    h.insert(&v4298313224);
    var v4298314704: Elem = .{ .value = 86 };
    h.insert(&v4298314704);
    var v4298316184: Elem = .{ .value = 87 };
    h.insert(&v4298316184);
    h.remove(&v4297010216);
    h.remove(&v4297008736);
    h.remove(&v4297014656);
    h.remove(&v4297013176);
    h.remove(&v4297011696);
    h.remove(&v4298146736);
    h.remove(&v4298148216);
    h.remove(&v4298149696);
    var v4297005776_: Elem = .{ .value = 88 };
    h.insert(&v4297005776_);
    var v4297004296_: Elem = .{ .value = 89 };
    h.insert(&v4297004296_);
    var v4297002816_: Elem = .{ .value = 90 };
    h.insert(&v4297002816_);
    h.remove(&v4298151176);
    h.remove(&v4298152656);
    h.remove(&v4298154136);
    h.remove(&v4298155616);
    h.remove(&v4298157096);
    var v4297007256_: Elem = .{ .value = 91 };
    h.insert(&v4297007256_);
    var v4298317664: Elem = .{ .value = 92 };
    h.insert(&v4298317664);
    var v4298319144: Elem = .{ .value = 93 };
    h.insert(&v4298319144);
    h.remove(&v4298160056);
    h.remove(&v4298158576);
    h.remove(&v4298161536);
    h.remove(&v4298163016);
    h.remove(&v4298164496);
    h.remove(&v4298165976);
    var v4298149696_: Elem = .{ .value = 94 };
    h.insert(&v4298149696_);
    var v4298148216_: Elem = .{ .value = 95 };
    h.insert(&v4298148216_);
    var v4298146736_: Elem = .{ .value = 96 };
    h.insert(&v4298146736_);
    h.remove(&v4298168936);
    h.remove(&v4298170416);
    h.remove(&v4298167456);
    h.remove(&v4298171896);
    h.remove(&v4298173376);
    h.remove(&v4298174856);
    h.remove(&v4298176336);
    h.remove(&v4298177816);
    h.remove(&v4298261424);
    h.remove(&v4298262904);
    var v4298157096_: Elem = .{ .value = 97 };
    h.insert(&v4298157096_);
    var v4298155616_: Elem = .{ .value = 98 };
    h.insert(&v4298155616_);
    var v4298154136_: Elem = .{ .value = 99 };
    h.insert(&v4298154136_);
    var v4298152656_: Elem = .{ .value = 100 };
    h.insert(&v4298152656_);
    h.remove(&v4298264384);
    h.remove(&v4298265864);
    h.remove(&v4298267344);
    h.remove(&v4298268824);
    h.remove(&v4298270304);
    h.remove(&v4298271784);
    h.remove(&v4298273264);
    h.remove(&v4298274744);
    h.remove(&v4298276224);
    h.remove(&v4298277704);
    h.remove(&v4298279184);
    h.remove(&v4298280664);
    h.remove(&v4298282144);
    h.remove(&v4298283624);
    h.remove(&v4298285104);
    h.remove(&v4298286584);
    h.remove(&v4298288064);
    h.remove(&v4298289544);
    h.remove(&v4298291024);
    h.remove(&v4298292504);
    h.remove(&v4298293984);
    h.remove(&v4298295464);
    h.remove(&v4298298424);
    h.remove(&v4298296944);
    h.remove(&v4298299904);
    h.remove(&v4298301384);
    h.remove(&v4298302864);
    h.remove(&v4296704944_);
    h.remove(&v4298305824);
    h.remove(&v4298304344);
    h.remove(&v4296706424_);
    h.remove(&v4298307304);
    h.remove(&v4298308784);
    h.remove(&v4298310264);
    h.remove(&v4298311744);
    h.remove(&v4296937280_);
    h.remove(&v4296938760_);
    h.remove(&v4296935800_);
    h.remove(&v4296934320_);
    h.remove(&v4296999856_);
    h.remove(&v4296940240_);
    h.remove(&v4297001336_);
    h.remove(&v4298313224);
    h.remove(&v4298314704);
    h.remove(&v4298316184);
    h.remove(&v4297004296_);
    // h.remove(&v4297005776_); // remove of element 88
}
mitchellh commented 1 year ago

Thanks! I'm not surprised, this was not a very well vetted part of the source but I couldn't produce any failing tests. Your work looks promising. Is there any way to minimize the test further so we can have a reasonable reproduction? Your test in the PR is mostly manually playing with pointers and it'd be better to reproduce it using the published API. Your comment appears to do this but requires a lot of inserts/removals. That's fine if that's all we can get! But just wanted to check.

ianic commented 1 year ago

In the tests above I stopped when found invalid heap structure. If we continue with removals we will finish in the endless loop in combine_siblings line 157. That's was the situation I got while using libxev and the debugging lead to heap.zig.

This is long series with 4 more removals and call to deleteMin at the end which never finishes.

test "build failing heap structure" {
    const Elem = struct {
        const Self = @This();
        value: usize = 0,
        heap: IntrusiveField(Self) = .{},
    };
    const Heap = Intrusive(Elem, void, (struct {
        fn less(ctx: void, a: *Elem, b: *Elem) bool {
            _ = ctx;
            return a.value < b.value;
        }
    }).less);
    var h: Heap = .{ .context = {} };
    var v4296704944: Elem = .{ .value = 1 };
    h.insert(&v4296704944);
    var v4296706424: Elem = .{ .value = 2 };
    h.insert(&v4296706424);
    var v4296934320: Elem = .{ .value = 3 };
    h.insert(&v4296934320);
    var v4296935800: Elem = .{ .value = 4 };
    h.insert(&v4296935800);
    var v4296937280: Elem = .{ .value = 5 };
    h.insert(&v4296937280);
    var v4296938760: Elem = .{ .value = 6 };
    h.insert(&v4296938760);
    var v4296940240: Elem = .{ .value = 7 };
    h.insert(&v4296940240);
    var v4296999856: Elem = .{ .value = 8 };
    h.insert(&v4296999856);
    var v4297001336: Elem = .{ .value = 9 };
    h.insert(&v4297001336);
    var v4297002816: Elem = .{ .value = 10 };
    h.insert(&v4297002816);
    var v4297004296: Elem = .{ .value = 11 };
    h.insert(&v4297004296);
    var v4297005776: Elem = .{ .value = 12 };
    h.insert(&v4297005776);
    var v4297007256: Elem = .{ .value = 13 };
    h.insert(&v4297007256);
    var v4297008736: Elem = .{ .value = 14 };
    h.insert(&v4297008736);
    var v4297010216: Elem = .{ .value = 15 };
    h.insert(&v4297010216);
    var v4297011696: Elem = .{ .value = 16 };
    h.insert(&v4297011696);
    var v4297013176: Elem = .{ .value = 17 };
    h.insert(&v4297013176);
    var v4297014656: Elem = .{ .value = 18 };
    h.insert(&v4297014656);
    var v4298146736: Elem = .{ .value = 19 };
    h.insert(&v4298146736);
    var v4298148216: Elem = .{ .value = 20 };
    h.insert(&v4298148216);
    var v4298149696: Elem = .{ .value = 21 };
    h.insert(&v4298149696);
    var v4298151176: Elem = .{ .value = 22 };
    h.insert(&v4298151176);
    var v4298152656: Elem = .{ .value = 23 };
    h.insert(&v4298152656);
    var v4298154136: Elem = .{ .value = 24 };
    h.insert(&v4298154136);
    var v4298155616: Elem = .{ .value = 25 };
    h.insert(&v4298155616);
    var v4298157096: Elem = .{ .value = 26 };
    h.insert(&v4298157096);
    var v4298158576: Elem = .{ .value = 27 };
    h.insert(&v4298158576);
    var v4298160056: Elem = .{ .value = 28 };
    h.insert(&v4298160056);
    var v4298161536: Elem = .{ .value = 29 };
    h.insert(&v4298161536);
    var v4298163016: Elem = .{ .value = 30 };
    h.insert(&v4298163016);
    var v4298164496: Elem = .{ .value = 31 };
    h.insert(&v4298164496);
    var v4298165976: Elem = .{ .value = 32 };
    h.insert(&v4298165976);
    var v4298167456: Elem = .{ .value = 33 };
    h.insert(&v4298167456);
    var v4298168936: Elem = .{ .value = 34 };
    h.insert(&v4298168936);
    var v4298170416: Elem = .{ .value = 35 };
    h.insert(&v4298170416);
    var v4298171896: Elem = .{ .value = 36 };
    h.insert(&v4298171896);
    var v4298173376: Elem = .{ .value = 37 };
    h.insert(&v4298173376);
    var v4298174856: Elem = .{ .value = 38 };
    h.insert(&v4298174856);
    var v4298176336: Elem = .{ .value = 39 };
    h.insert(&v4298176336);
    var v4298177816: Elem = .{ .value = 40 };
    h.insert(&v4298177816);
    var v4298261424: Elem = .{ .value = 41 };
    h.insert(&v4298261424);
    var v4298262904: Elem = .{ .value = 42 };
    h.insert(&v4298262904);
    var v4298264384: Elem = .{ .value = 43 };
    h.insert(&v4298264384);
    var v4298265864: Elem = .{ .value = 44 };
    h.insert(&v4298265864);
    var v4298267344: Elem = .{ .value = 45 };
    h.insert(&v4298267344);
    var v4298268824: Elem = .{ .value = 46 };
    h.insert(&v4298268824);
    var v4298270304: Elem = .{ .value = 47 };
    h.insert(&v4298270304);
    var v4298271784: Elem = .{ .value = 48 };
    h.insert(&v4298271784);
    var v4298273264: Elem = .{ .value = 49 };
    h.insert(&v4298273264);
    var v4298274744: Elem = .{ .value = 50 };
    h.insert(&v4298274744);
    var v4298276224: Elem = .{ .value = 51 };
    h.insert(&v4298276224);
    var v4298277704: Elem = .{ .value = 52 };
    h.insert(&v4298277704);
    var v4298279184: Elem = .{ .value = 53 };
    h.insert(&v4298279184);
    var v4298280664: Elem = .{ .value = 54 };
    h.insert(&v4298280664);
    var v4298282144: Elem = .{ .value = 55 };
    h.insert(&v4298282144);
    var v4298283624: Elem = .{ .value = 56 };
    h.insert(&v4298283624);
    var v4298285104: Elem = .{ .value = 57 };
    h.insert(&v4298285104);
    var v4298286584: Elem = .{ .value = 58 };
    h.insert(&v4298286584);
    var v4298288064: Elem = .{ .value = 59 };
    h.insert(&v4298288064);
    var v4298289544: Elem = .{ .value = 60 };
    h.insert(&v4298289544);
    var v4298291024: Elem = .{ .value = 61 };
    h.insert(&v4298291024);
    var v4298292504: Elem = .{ .value = 62 };
    h.insert(&v4298292504);
    var v4298293984: Elem = .{ .value = 63 };
    h.insert(&v4298293984);
    var v4298295464: Elem = .{ .value = 64 };
    h.insert(&v4298295464);
    h.remove(&v4296704944);
    var v4298296944: Elem = .{ .value = 65 };
    h.insert(&v4298296944);
    var v4298298424: Elem = .{ .value = 66 };
    h.insert(&v4298298424);
    var v4298299904: Elem = .{ .value = 67 };
    h.insert(&v4298299904);
    h.remove(&v4296706424);
    var v4298301384: Elem = .{ .value = 68 };
    h.insert(&v4298301384);
    var v4298302864: Elem = .{ .value = 69 };
    h.insert(&v4298302864);
    var v4296704944_: Elem = .{ .value = 70 };
    h.insert(&v4296704944_);
    var v4298304344: Elem = .{ .value = 71 };
    h.insert(&v4298304344);
    var v4298305824: Elem = .{ .value = 72 };
    h.insert(&v4298305824);
    h.remove(&v4296934320);
    h.remove(&v4296935800);
    h.remove(&v4296937280);
    h.remove(&v4296938760);
    var v4296706424_: Elem = .{ .value = 73 };
    h.insert(&v4296706424_);
    var v4298307304: Elem = .{ .value = 74 };
    h.insert(&v4298307304);
    var v4298308784: Elem = .{ .value = 75 };
    h.insert(&v4298308784);
    h.remove(&v4296940240);
    h.remove(&v4296999856);
    var v4298310264: Elem = .{ .value = 76 };
    h.insert(&v4298310264);
    var v4298311744: Elem = .{ .value = 77 };
    h.insert(&v4298311744);
    h.remove(&v4297001336);
    var v4296938760_: Elem = .{ .value = 78 };
    h.insert(&v4296938760_);
    var v4296937280_: Elem = .{ .value = 79 };
    h.insert(&v4296937280_);
    var v4296935800_: Elem = .{ .value = 80 };
    h.insert(&v4296935800_);
    var v4296934320_: Elem = .{ .value = 81 };
    h.insert(&v4296934320_);
    h.remove(&v4297002816);
    h.remove(&v4297004296);
    h.remove(&v4297005776);
    var v4296999856_: Elem = .{ .value = 82 };
    h.insert(&v4296999856_);
    var v4296940240_: Elem = .{ .value = 83 };
    h.insert(&v4296940240_);
    h.remove(&v4297007256);
    var v4297001336_: Elem = .{ .value = 84 };
    h.insert(&v4297001336_);
    var v4298313224: Elem = .{ .value = 85 };
    h.insert(&v4298313224);
    var v4298314704: Elem = .{ .value = 86 };
    h.insert(&v4298314704);
    var v4298316184: Elem = .{ .value = 87 };
    h.insert(&v4298316184);
    h.remove(&v4297010216);
    h.remove(&v4297008736);
    h.remove(&v4297014656);
    h.remove(&v4297013176);
    h.remove(&v4297011696);
    h.remove(&v4298146736);
    h.remove(&v4298148216);
    h.remove(&v4298149696);
    var v4297005776_: Elem = .{ .value = 88 };
    h.insert(&v4297005776_);
    var v4297004296_: Elem = .{ .value = 89 };
    h.insert(&v4297004296_);
    var v4297002816_: Elem = .{ .value = 90 };
    h.insert(&v4297002816_);
    h.remove(&v4298151176);
    h.remove(&v4298152656);
    h.remove(&v4298154136);
    h.remove(&v4298155616);
    h.remove(&v4298157096);
    var v4297007256_: Elem = .{ .value = 91 };
    h.insert(&v4297007256_);
    var v4298317664: Elem = .{ .value = 92 };
    h.insert(&v4298317664);
    var v4298319144: Elem = .{ .value = 93 };
    h.insert(&v4298319144);
    h.remove(&v4298160056);
    h.remove(&v4298158576);
    h.remove(&v4298161536);
    h.remove(&v4298163016);
    h.remove(&v4298164496);
    h.remove(&v4298165976);
    var v4298149696_: Elem = .{ .value = 94 };
    h.insert(&v4298149696_);
    var v4298148216_: Elem = .{ .value = 95 };
    h.insert(&v4298148216_);
    var v4298146736_: Elem = .{ .value = 96 };
    h.insert(&v4298146736_);
    h.remove(&v4298168936);
    h.remove(&v4298170416);
    h.remove(&v4298167456);
    h.remove(&v4298171896);
    h.remove(&v4298173376);
    h.remove(&v4298174856);
    h.remove(&v4298176336);
    h.remove(&v4298177816);
    h.remove(&v4298261424);
    h.remove(&v4298262904);
    var v4298157096_: Elem = .{ .value = 97 };
    h.insert(&v4298157096_);
    var v4298155616_: Elem = .{ .value = 98 };
    h.insert(&v4298155616_);
    var v4298154136_: Elem = .{ .value = 99 };
    h.insert(&v4298154136_);
    var v4298152656_: Elem = .{ .value = 100 };
    h.insert(&v4298152656_);
    h.remove(&v4298264384);
    h.remove(&v4298265864);
    h.remove(&v4298267344);
    h.remove(&v4298268824);
    h.remove(&v4298270304);
    h.remove(&v4298271784);
    h.remove(&v4298273264);
    h.remove(&v4298274744);
    h.remove(&v4298276224);
    h.remove(&v4298277704);
    h.remove(&v4298279184);
    h.remove(&v4298280664);
    h.remove(&v4298282144);
    h.remove(&v4298283624);
    h.remove(&v4298285104);
    h.remove(&v4298286584);
    h.remove(&v4298288064);
    h.remove(&v4298289544);
    h.remove(&v4298291024);
    h.remove(&v4298292504);
    h.remove(&v4298293984);
    h.remove(&v4298295464);
    h.remove(&v4298298424);
    h.remove(&v4298296944);
    h.remove(&v4298299904);
    h.remove(&v4298301384);
    h.remove(&v4298302864);
    h.remove(&v4296704944_);
    h.remove(&v4298305824);
    h.remove(&v4298304344);
    h.remove(&v4296706424_);
    h.remove(&v4298307304);
    h.remove(&v4298308784);
    h.remove(&v4298310264);
    h.remove(&v4298311744);
    h.remove(&v4296937280_);
    h.remove(&v4296938760_);
    h.remove(&v4296935800_);
    h.remove(&v4296934320_);
    h.remove(&v4296999856_);
    h.remove(&v4296940240_);
    h.remove(&v4297001336_);
    h.remove(&v4298313224);
    h.remove(&v4298314704);
    h.remove(&v4298316184);
    h.remove(&v4297004296_);
    h.remove(&v4297005776_); // remove of element 88
    h.remove(&v4297002816_);
    h.remove(&v4298319144);
    h.remove(&v4298317664);
    try std.testing.expect(h.deleteMin() != null);
}

or when I clean that to just important part (playing with pointers, I agree) this also results in endless loop:

test "dangling next pointer" {
    const Elem = struct {
        const Self = @This();
        value: usize = 0,
        heap: IntrusiveField(Self) = .{},
    };

    const Heap = Intrusive(Elem, void, (struct {
        fn less(ctx: void, a: *Elem, b: *Elem) bool {
            _ = ctx;
            return a.value < b.value;
        }
    }).less);
    var h: Heap = .{ .context = {} };

    var e88: Elem = .{ .value = 88 };
    var e94: Elem = .{ .value = 94 };
    var e90: Elem = .{ .value = 90 };
    var e97: Elem = .{ .value = 97 };
    var e92: Elem = .{ .value = 92 };
    var e93: Elem = .{ .value = 93 };
    var e91: Elem = .{ .value = 91 };

    h.root = &e88;
    e88.heap.child = &e90;
    e90.heap.prev = &e88;
    e90.heap.next = &e94;
    e94.heap.prev = &e90;
    e94.heap.child = &e97;
    e97.heap.prev = &e94;
    e94.heap.next = &e92;
    e92.heap.prev = &e94;
    e92.heap.child = &e93;
    e93.heap.prev = &e92;
    e92.heap.next = &e91;
    e91.heap.prev = &e92;

    h.remove(&e88);
    h.remove(&e90);
    h.remove(&e93);
    h.remove(&e92);

    try std.testing.expect(h.deleteMin() != null);
}
penberg commented 1 year ago

@mitchellh FWIW, the change looks correct to me. The failing test case also sweetens the deal quite a bit...

ianic commented 1 year ago

I just pushed same fix in #56 but with much cleaner test. So I suggest that we close this and merge #56 instead.

mitchellh commented 1 year ago

Superseded by #56