FuzzSingleThreadedAllocator

const FuzzSingleThreadedAllocator = struct {
    gpa: mem.Allocator,
    smith: *std.testing.Smith,

    buf: []u8,
    fill: usize,
    allocs: std.MultiArrayList(AllocInfo),

    const AllocInfo = struct {
        ptr: [*]u8,
        len: usize,
        alignment: Alignment,
    };

    fn allocator(f: *FuzzSingleThreadedAllocator) mem.Allocator {
        @disableInstrumentation();
        return .{ .ptr = f, .vtable = &.{
            .alloc = FuzzSingleThreadedAllocator.alloc,
            .free = FuzzSingleThreadedAllocator.free,
            .resize = FuzzSingleThreadedAllocator.resize,
            .remap = FuzzSingleThreadedAllocator.remap,
        } };
    }

    fn alloc(ctx: *anyopaque, len: usize, alignment: Alignment, _: usize) ?[*]u8 {
        @disableInstrumentation();

        const f: *FuzzSingleThreadedAllocator = @ptrCast(@alignCast(ctx));
        f.allocs.ensureUnusedCapacity(f.gpa, 1) catch return null;

        const ptr = f.allocInner(len, alignment) orelse return null;
        f.allocs.appendAssumeCapacity(.{
            .ptr = ptr,
            .len = len,
            .alignment = alignment,
        });
        return ptr;
    }

    fn allocInner(f: *FuzzSingleThreadedAllocator, len: usize, alignment: Alignment) ?[*]u8 {
        @disableInstrumentation();

        const start_addr = alignment.forward(@intFromPtr(f.buf[f.fill..].ptr));
        const start = @as([*]u8, @ptrFromInt(start_addr)) - f.buf.ptr;
        if (start +| len > f.buf.len or f.smith.boolWeighted(31, 1)) return null;
        f.fill = start + len;
        return f.buf[start..][0..len].ptr;
    }

    fn allocIndex(f: *FuzzSingleThreadedAllocator, memory: []u8, alignment: Alignment) usize {
        @disableInstrumentation();

        const allocs_slice = f.allocs.slice();
        const i = mem.findScalar([*]u8, allocs_slice.items(.ptr), memory.ptr) orelse panic(
            "invalid SafeAllocator free of {f}",
            .{FormatMemory{ .memory = memory, .alignment = alignment }},
        );
        const expected_len = allocs_slice.items(.len)[i];
        const expected_align = allocs_slice.items(.alignment)[i];
        if (memory.len != expected_len or allocs_slice.items(.alignment)[i] != expected_align) {
            panic("SafeAllocator free {f} mismatches alloc {f}", .{
                FormatMemory{ .memory = memory, .alignment = alignment },
                FormatMemory{ .memory = memory.ptr[0..expected_len], .alignment = expected_align },
            });
        }
        return i;
    }

    fn free(ctx: *anyopaque, memory: []u8, alignment: Alignment, _: usize) void {
        @disableInstrumentation();

        const f: *FuzzSingleThreadedAllocator = @ptrCast(@alignCast(ctx));
        f.allocs.swapRemove(f.allocIndex(memory, alignment));
    }

    fn resize(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, _: usize) bool {
        @disableInstrumentation();

        const f: *FuzzSingleThreadedAllocator = @ptrCast(@alignCast(ctx));
        const i = f.allocIndex(memory, alignment);

        const start = memory.ptr - f.buf.ptr;
        const old_end = start + memory.len;
        const new_end = start +| new_len;
        if (new_end > f.buf.len or f.smith.value(bool)) {
            return false;
        }

        if (new_len <= memory.len) {
            // The fill is not decreased so memory is not reused.
        } else if (f.fill == old_end) {
            f.fill = new_end;
        } else {
            return false;
        }
        f.allocs.items(.len)[i] = new_len;
        return true;
    }

    fn remap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, _: usize) ?[*]u8 {
        @disableInstrumentation();

        const f: *FuzzSingleThreadedAllocator = @ptrCast(@alignCast(ctx));
        if (f.smith.value(bool)) {
            const resized = FuzzSingleThreadedAllocator.resize(
                ctx,
                memory,
                alignment,
                new_len,
                undefined,
            );
            return if (resized) memory.ptr else null;
        }

        const i = f.allocIndex(memory, alignment);
        if (f.smith.value(bool)) return null;

        const new_ptr = f.allocInner(new_len, alignment) orelse return null;
        const copy_len = @min(memory.len, new_len);
        @memcpy(new_ptr[0..copy_len], memory[0..copy_len]);

        f.allocs.set(i, .{
            .ptr = new_ptr,
            .len = new_len,
            .alignment = alignment,
        });
        return new_ptr;
    }
}