RefCountedSet.addWithId over-counts living items when the requested id is dead and the value already exists

[alleneubank]

Hi! I'm an outside contributor who has been fuzzing the terminal core in a local build, and I think I found a small accounting bug in RefCountedSet. I don't have a vouch to open issues or PRs yet, so I'm filing it here first. I have a fix with a unit test ready and would be glad to open a PR if a maintainer agrees it's a real bug.

Summary

RefCountedSet.addWithIdContext increments living even when the requested (dead) id resolves to a value that is already live under a different id. Each such call adds a phantom living item, so count() drifts above the number of entries with a non-zero ref count.

Where

src/terminal/ref_counted_set.zig, the dead-slot branch of addWithIdContext (current main, lines ~326-334):

if (items[id].meta.ref == 0) {
    // ...
    self.deleteItem(base, id, ctx);

    const added_id = self.upsert(base, value, id, ctx);

    items[added_id].meta.ref += 1;

    self.living += 1;   // <-- also runs when upsert returned an existing live item

    return if (added_id == id) null else added_id;
}

upsert returns the existing entry when lookupContext finds the value already live, and only inserts otherwise. The living increment doesn't distinguish the two cases.

How the state arises

Dead slots are reaped lazily (by the trim loop in add or when an insert probe walks over them), and lookup skips dead slots. So after a style is released from a page and later re-added, the set can hold a dead slot for style S at id X and a live S at id Y. addWithId(S, X) — used when cloning rows between pages to try to keep the source id — then takes the dead branch, upsert returns Y, and living is bumped for an item that already existed.

This is reachable from plain terminal output, no resize needed. Probing the branch with a panic in a debug build, the fuzz case's path was:

Terminal.linefeed -> index -> scrollUp -> deleteLines
  -> Screen.clonePartialRowGrowCapacity -> Page.clonePartialRowFrom
  -> styles.addWithId

i.e. a linefeed at the bottom of a scroll region whose incoming row lives on a different page than its destination.

Impact

Nothing crashes on main as far as I can tell; it's silent over-counting. count() feeds the style capacity projection in PageList (adjustCapacity, the .styles => page.styles.count() branch) and the living < 0.9 * cap check in add() that picks NeedsRehash vs OutOfMemory, so affected pages over-provision style capacity and report the set full earlier than necessary. It also shows up as a wrong number in the inspector's page view. I noticed it because a local encoder cross-checked count() against the live entries and saw count() == 5 with only 2 live entries.

Reproduction (unit test)

test "addWithId dead id for an existing value keeps living count accurate" {
    const alloc = testing.allocator;
    const TestSet = RefCountedSet(
        u32,
        u16,
        u16,
        struct {
            pub fn hash(_: *const @This(), value: u32) u64 {
                return std.hash.int(value);
            }

            pub fn eql(_: *const @This(), a: u32, b: u32) bool {
                return a == b;
            }
        },
    );

    const layout: TestSet.Layout = .init(8);
    const buf = try alloc.alignedAlloc(u8, TestSet.base_align, layout.total_size);
    defer alloc.free(buf);

    var set: TestSet = .init(.init(buf), layout, .{});
    const kept = try set.add(buf, 11);
    const dead = try set.add(buf, 22);
    set.release(buf, dead);
    try testing.expectEqual(@as(usize, 1), set.count());

    const resolved = try set.addWithId(buf, 11, dead);
    try testing.expectEqual(kept, resolved.?);
    try testing.expectEqual(@as(u16, 2), set.refCount(buf, kept));
    try testing.expectEqual(@as(usize, 1), set.count()); // fails on main: expected 1, found 2

    var it = set.iterator(buf);
    var live: usize = 0;
    while (it.next()) |_| live += 1;
    try testing.expectEqual(set.count(), live);
}

On current main this fails with expected 1, found 2.

Proposed fix

A fresh insert leaves the item at ref == 1; an existing item ends at >= 2:

items[added_id].meta.ref += 1;

// upsert resolves to an existing live item when the
// value is already present; only a fresh insert
// (ref went 0 -> 1) adds a living item.
if (items[added_id].meta.ref == 1) self.living += 1;

With that change the test passes and the fuzz input that surfaced this no longer trips the cross-check. Commit with the fix and test on top of current main: alleneubank@651f3a6

An alternative, if you'd rather not lean on the ref == 1 check, would be to make the dead-slot branch mirror addContext (lookup first and return the existing id, otherwise reap + insert + living += 1), which would also let upsert go away since this is its only caller. I kept the one-line version to keep the diff minimal, but I'm happy to do it either way.

Thanks for Ghostty!

Sent with Claude Code Fable

[mitchellh]

Thanks #14081