diff options
| author | Can Celik <ogulcancelik@gmail.com> | 2026-09-10 21:51:57 +0300 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2026-09-10 21:51:57 +0300 |
| commit | 425c86179791cd32e2d4ce0ae7f269940b4b0663 (patch) | |
| tree | e52c4383a6d69216cbe2a32638bf90841d7e2189 /vendor/libghostty-vt/src/datastruct | |
| parent | 90e947a6e26e02f10ec7f1694c4eb5b78a86406b (diff) | |
chore: upgrade libghostty and preserve terminal behavior (#3906)
Diffstat (limited to 'vendor/libghostty-vt/src/datastruct')
| -rw-r--r-- | vendor/libghostty-vt/src/datastruct/array_list_collection.zig | 44 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/datastruct/blocking_queue.zig | 83 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/datastruct/circ_buf.zig | 67 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/datastruct/comparison.zig | 6 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/datastruct/limited_allocator.zig | 124 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/datastruct/lru.zig | 349 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/datastruct/main.zig | 6 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/datastruct/segmented_list.zig | 533 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/datastruct/segmented_pool.zig | 95 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/datastruct/split_tree.zig | 12 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/datastruct/untouched_pool.zig | 297 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/datastruct/wasm_page_pool.zig | 162 |
12 files changed, 1244 insertions, 534 deletions
diff --git a/vendor/libghostty-vt/src/datastruct/array_list_collection.zig b/vendor/libghostty-vt/src/datastruct/array_list_collection.zig deleted file mode 100644 index d3fbddb1..00000000 --- a/vendor/libghostty-vt/src/datastruct/array_list_collection.zig +++ /dev/null @@ -1,44 +0,0 @@ -const std = @import("std"); -const Allocator = std.mem.Allocator; - -/// A collection of ArrayLists with methods for bulk operations. -pub fn ArrayListCollection(comptime T: type) type { - return struct { - const Self = ArrayListCollection(T); - const ArrayListT = std.ArrayListUnmanaged(T); - - // An array containing the lists that belong to this collection. - lists: []ArrayListT, - - // The collection will be initialized with empty ArrayLists. - pub fn init( - alloc: Allocator, - list_count: usize, - initial_capacity: usize, - ) Allocator.Error!Self { - const self: Self = .{ - .lists = try alloc.alloc(ArrayListT, list_count), - }; - - for (self.lists) |*list| { - list.* = try .initCapacity(alloc, initial_capacity); - } - - return self; - } - - pub fn deinit(self: *Self, alloc: Allocator) void { - for (self.lists) |*list| { - list.deinit(alloc); - } - alloc.free(self.lists); - } - - /// Clear all lists in the collection, retaining capacity. - pub fn reset(self: *Self) void { - for (self.lists) |*list| { - list.clearRetainingCapacity(); - } - } - }; -} diff --git a/vendor/libghostty-vt/src/datastruct/blocking_queue.zig b/vendor/libghostty-vt/src/datastruct/blocking_queue.zig index 3185d98d..89ce57d8 100644 --- a/vendor/libghostty-vt/src/datastruct/blocking_queue.zig +++ b/vendor/libghostty-vt/src/datastruct/blocking_queue.zig @@ -3,6 +3,7 @@ const std = @import("std"); const Allocator = std.mem.Allocator; +const compat_thread = @import("../lib/compat/thread.zig"); /// Returns a blocking queue implementation for type T. /// @@ -62,12 +63,12 @@ pub fn BlockingQueue( len: Size = 0, /// The big mutex that must be held to read/write. - mutex: std.Thread.Mutex = .{}, + mutex: std.Io.Mutex = .init, /// A CV for being notified when the queue is no longer full. This is /// used for writing. Note we DON'T have a CV for waiting on the /// queue not being EMPTY because we use external notifiers for that. - cond_not_full: std.Thread.Condition = .{}, + cond_not_full: std.Io.Condition = .init, not_full_waiters: usize = 0, /// Allocate the blocking queue on the heap. @@ -80,8 +81,8 @@ pub fn BlockingQueue( .len = 0, .write = 0, .read = 0, - .mutex = .{}, - .cond_not_full = .{}, + .mutex = .init, + .cond_not_full = .init, .not_full_waiters = 0, }; @@ -98,9 +99,9 @@ pub fn BlockingQueue( /// Push a value to the queue. This returns the total size of the /// queue (unread items) after the push. A return value of zero /// means that the push failed. - pub fn push(self: *Self, value: T, timeout: Timeout) Size { - self.mutex.lock(); - defer self.mutex.unlock(); + pub fn push(self: *Self, io: std.Io, value: T, timeout: Timeout) Size { + self.mutex.lockUncancelable(io); + defer self.mutex.unlock(io); // The if (self.full()) { @@ -111,13 +112,23 @@ pub fn BlockingQueue( .forever => { self.not_full_waiters += 1; defer self.not_full_waiters -= 1; - self.cond_not_full.wait(&self.mutex); + self.cond_not_full.waitUncancelable(io, &self.mutex); }, .ns => |ns| { self.not_full_waiters += 1; defer self.not_full_waiters -= 1; - self.cond_not_full.timedWait(&self.mutex, ns) catch return 0; + compat_thread.waitTimeout( + &self.cond_not_full, + io, + &self.mutex, + .{ + .duration = .{ + .raw = .fromNanoseconds(ns), + .clock = .awake, + }, + }, + ) catch return 0; }, } @@ -136,9 +147,9 @@ pub fn BlockingQueue( } /// Pop a value from the queue without blocking. - pub fn pop(self: *Self) ?T { - self.mutex.lock(); - defer self.mutex.unlock(); + pub fn pop(self: *Self, io: std.Io) ?T { + self.mutex.lockUncancelable(io); + defer self.mutex.unlock(io); // If we're empty we have nothing if (self.len == 0) return null; @@ -151,7 +162,7 @@ pub fn BlockingQueue( self.len -= 1; // If we have consumers waiting on a full queue, notify. - if (self.not_full_waiters > 0) self.cond_not_full.signal(); + if (self.not_full_waiters > 0) self.cond_not_full.signal(io); return self.data[n]; } @@ -160,8 +171,8 @@ pub fn BlockingQueue( /// until `deinit` is called on the return value. This is used if /// you know you're going to "pop" and utilize all the values /// quickly to avoid many locks, bounds checks, and cv signals. - pub fn drain(self: *Self) DrainIterator { - self.mutex.lock(); + pub fn drain(self: *Self, io: std.Io) DrainIterator { + self.mutex.lockUncancelable(io); return .{ .queue = self }; } @@ -180,12 +191,12 @@ pub fn BlockingQueue( return self.queue.data[n]; } - pub fn deinit(self: *DrainIterator) void { + pub fn deinit(self: *DrainIterator, io: std.Io) void { // If we have consumers waiting on a full queue, notify. - if (self.queue.not_full_waiters > 0) self.queue.cond_not_full.signal(); + if (self.queue.not_full_waiters > 0) self.queue.cond_not_full.signal(io); // Unlock - self.queue.mutex.unlock(); + self.queue.mutex.unlock(io); } }; @@ -200,49 +211,51 @@ pub fn BlockingQueue( test "basic push and pop" { const testing = std.testing; const alloc = testing.allocator; + const io = testing.io; const Q = BlockingQueue(u64, 4); const q = try Q.create(alloc); defer q.destroy(alloc); // Should have no values - try testing.expect(q.pop() == null); + try testing.expect(q.pop(io) == null); // Push until we're full - try testing.expectEqual(@as(Q.Size, 1), q.push(1, .{ .instant = {} })); - try testing.expectEqual(@as(Q.Size, 2), q.push(2, .{ .instant = {} })); - try testing.expectEqual(@as(Q.Size, 3), q.push(3, .{ .instant = {} })); - try testing.expectEqual(@as(Q.Size, 4), q.push(4, .{ .instant = {} })); - try testing.expectEqual(@as(Q.Size, 0), q.push(5, .{ .instant = {} })); + try testing.expectEqual(@as(Q.Size, 1), q.push(io, 1, .{ .instant = {} })); + try testing.expectEqual(@as(Q.Size, 2), q.push(io, 2, .{ .instant = {} })); + try testing.expectEqual(@as(Q.Size, 3), q.push(io, 3, .{ .instant = {} })); + try testing.expectEqual(@as(Q.Size, 4), q.push(io, 4, .{ .instant = {} })); + try testing.expectEqual(@as(Q.Size, 0), q.push(io, 5, .{ .instant = {} })); // Pop! - try testing.expect(q.pop().? == 1); - try testing.expect(q.pop().? == 2); - try testing.expect(q.pop().? == 3); - try testing.expect(q.pop().? == 4); - try testing.expect(q.pop() == null); + try testing.expect(q.pop(io).? == 1); + try testing.expect(q.pop(io).? == 2); + try testing.expect(q.pop(io).? == 3); + try testing.expect(q.pop(io).? == 4); + try testing.expect(q.pop(io) == null); // Drain does nothing - var it = q.drain(); + var it = q.drain(io); try testing.expect(it.next() == null); - it.deinit(); + it.deinit(io); // Verify we can still push - try testing.expectEqual(@as(Q.Size, 1), q.push(1, .{ .instant = {} })); + try testing.expectEqual(@as(Q.Size, 1), q.push(io, 1, .{ .instant = {} })); } test "timed push" { const testing = std.testing; const alloc = testing.allocator; + const io = testing.io; const Q = BlockingQueue(u64, 1); const q = try Q.create(alloc); defer q.destroy(alloc); // Push - try testing.expectEqual(@as(Q.Size, 1), q.push(1, .{ .instant = {} })); - try testing.expectEqual(@as(Q.Size, 0), q.push(2, .{ .instant = {} })); + try testing.expectEqual(@as(Q.Size, 1), q.push(io, 1, .{ .instant = {} })); + try testing.expectEqual(@as(Q.Size, 0), q.push(io, 2, .{ .instant = {} })); // Timed push should fail - try testing.expectEqual(@as(Q.Size, 0), q.push(2, .{ .ns = 1000 })); + try testing.expectEqual(@as(Q.Size, 0), q.push(io, 2, .{ .ns = 1000 })); } diff --git a/vendor/libghostty-vt/src/datastruct/circ_buf.zig b/vendor/libghostty-vt/src/datastruct/circ_buf.zig index 3e373cb9..41a16832 100644 --- a/vendor/libghostty-vt/src/datastruct/circ_buf.zig +++ b/vendor/libghostty-vt/src/datastruct/circ_buf.zig @@ -167,18 +167,18 @@ pub fn CircBuf(comptime T: type, comptime default: T) type { const prev_len = self.len(); const prev_cap = self.storage.len; self.storage = try alloc.realloc(self.storage, size); + const retained_len = @min(prev_len, size); // If we grew, we need to set our new defaults. We can add it // at the end since we rotated to start. if (size > prev_cap) { @memset(self.storage[prev_cap..], default); - - // Fix up our head/tail - if (self.full) { - self.head = prev_len; - self.full = false; - } } + + // Fix up our head/tail for the new capacity. + self.head = if (retained_len == size) 0 else retained_len; + self.tail = 0; + self.full = retained_len == size; } /// Rotate the data so that it is zero-aligned. @@ -793,6 +793,61 @@ test "CircBuf resize shrink" { } } +test "CircBuf resize shrink partially full" { + const testing = std.testing; + const alloc = testing.allocator; + + const Buf = CircBuf(u8, 0); + var buf = try Buf.init(alloc, 5); + defer buf.deinit(alloc); + + try buf.append(1); + try buf.append(2); + try buf.append(3); + + try buf.resize(alloc, 2); + try testing.expect(buf.full); + try testing.expectEqual(@as(usize, 2), buf.len()); + try testing.expectEqual(@as(usize, 2), buf.capacity()); + + var it = buf.iterator(.forward); + try testing.expectEqual(@as(u8, 1), it.next().?.*); + try testing.expectEqual(@as(u8, 2), it.next().?.*); + try testing.expect(it.next() == null); + try testing.expectError(error.OutOfMemory, buf.append(4)); +} + +test "CircBuf resize shrink to length" { + const testing = std.testing; + const alloc = testing.allocator; + + const Buf = CircBuf(u8, 0); + var buf = try Buf.init(alloc, 5); + defer buf.deinit(alloc); + + try buf.append(1); + try buf.append(2); + try buf.resize(alloc, 2); + + try testing.expect(buf.full); + try testing.expectEqual(@as(usize, 2), buf.len()); + try testing.expectEqual(@as(usize, 2), buf.capacity()); +} + +test "CircBuf resize empty to zero" { + const testing = std.testing; + const alloc = testing.allocator; + + const Buf = CircBuf(u8, 0); + var buf = try Buf.init(alloc, 5); + defer buf.deinit(alloc); + + try buf.resize(alloc, 0); + try testing.expect(buf.full); + try testing.expectEqual(@as(usize, 0), buf.len()); + try testing.expectEqual(@as(usize, 0), buf.capacity()); +} + test "CircBuf append empty slice" { const testing = std.testing; const alloc = testing.allocator; diff --git a/vendor/libghostty-vt/src/datastruct/comparison.zig b/vendor/libghostty-vt/src/datastruct/comparison.zig index 6a862bb9..73f0a5bd 100644 --- a/vendor/libghostty-vt/src/datastruct/comparison.zig +++ b/vendor/libghostty-vt/src/datastruct/comparison.zig @@ -130,10 +130,12 @@ fn expectApproxEqualInner(comptime T: type, expected: T, actual: T) !void { }, .vector => |info| { var i: usize = 0; + const expected_array: [info.len]info.child = expected; + const actual_array: [info.len]info.child = actual; while (i < info.len) : (i += 1) { - expectApproxEqual(expected[i], actual[i]) catch { + expectApproxEqual(expected_array[i], actual_array[i]) catch { print("index {d} incorrect. expected approximately {any}, found {any}\n", .{ - i, expected[i], actual[i], + i, expected_array[i], actual_array[i], }); return error.TestExpectedApproxEqual; }; diff --git a/vendor/libghostty-vt/src/datastruct/limited_allocator.zig b/vendor/libghostty-vt/src/datastruct/limited_allocator.zig new file mode 100644 index 00000000..11c4fbea --- /dev/null +++ b/vendor/libghostty-vt/src/datastruct/limited_allocator.zig @@ -0,0 +1,124 @@ +const std = @import("std"); +const Allocator = std.mem.Allocator; + +/// An allocator that rejects any single allocation or resize larger than a +/// configured byte limit. The limit applies to each request independently, +/// not to the total amount of memory currently allocated. +pub const LimitedAllocator = struct { + child: Allocator, + limit: usize, + + /// Set after an allocation, resize, or remap is rejected for exceeding + /// the limit. This remains set until the caller clears it. + limit_exceeded: bool = false, + + pub fn init(child: Allocator, limit: usize) LimitedAllocator { + return .{ + .child = child, + .limit = limit, + }; + } + + pub fn allocator(self: *LimitedAllocator) Allocator { + return .{ + .ptr = self, + .vtable = &.{ + .alloc = alloc, + .resize = resize, + .remap = remap, + .free = free, + }, + }; + } + + fn check(self: *LimitedAllocator, size: usize) bool { + if (size <= self.limit) return true; + self.limit_exceeded = true; + return false; + } + + fn alloc( + ctx: *anyopaque, + len: usize, + alignment: std.mem.Alignment, + ret_addr: usize, + ) ?[*]u8 { + const self: *LimitedAllocator = @ptrCast(@alignCast(ctx)); + if (!self.check(len)) return null; + return self.child.rawAlloc(len, alignment, ret_addr); + } + + fn resize( + ctx: *anyopaque, + memory: []u8, + alignment: std.mem.Alignment, + new_len: usize, + ret_addr: usize, + ) bool { + const self: *LimitedAllocator = @ptrCast(@alignCast(ctx)); + if (!self.check(new_len)) return false; + return self.child.rawResize(memory, alignment, new_len, ret_addr); + } + + fn remap( + ctx: *anyopaque, + memory: []u8, + alignment: std.mem.Alignment, + new_len: usize, + ret_addr: usize, + ) ?[*]u8 { + const self: *LimitedAllocator = @ptrCast(@alignCast(ctx)); + if (!self.check(new_len)) return null; + return self.child.rawRemap(memory, alignment, new_len, ret_addr); + } + + fn free( + ctx: *anyopaque, + memory: []u8, + alignment: std.mem.Alignment, + ret_addr: usize, + ) void { + const self: *LimitedAllocator = @ptrCast(@alignCast(ctx)); + self.child.rawFree(memory, alignment, ret_addr); + } +}; + +test "LimitedAllocator allows allocations through the limit" { + const testing = std.testing; + + var limited: LimitedAllocator = .init(testing.allocator, 8); + const alloc = limited.allocator(); + const data = try alloc.alloc(u8, 8); + defer alloc.free(data); + + try testing.expect(!limited.limit_exceeded); +} + +test "LimitedAllocator rejects allocations before the child" { + const testing = std.testing; + + var failing = testing.FailingAllocator.init(testing.allocator, .{ + .fail_index = 0, + }); + var limited: LimitedAllocator = .init(failing.allocator(), 8); + + try testing.expectError(error.OutOfMemory, limited.allocator().alloc(u8, 9)); + try testing.expect(limited.limit_exceeded); + try testing.expect(!failing.has_induced_failure); +} + +test "LimitedAllocator rejects oversized resize and remap" { + const testing = std.testing; + + var limited: LimitedAllocator = .init(testing.allocator, 8); + const alloc = limited.allocator(); + const data = try alloc.alloc(u8, 8); + defer alloc.free(data); + + try testing.expect(!alloc.resize(data, 9)); + try testing.expect(limited.limit_exceeded); + + limited.limit_exceeded = false; + try testing.expect(alloc.remap(data, 9) == null); + try testing.expect(limited.limit_exceeded); +} diff --git a/vendor/libghostty-vt/src/datastruct/lru.zig b/vendor/libghostty-vt/src/datastruct/lru.zig deleted file mode 100644 index 83d2cf8e..00000000 --- a/vendor/libghostty-vt/src/datastruct/lru.zig +++ /dev/null @@ -1,349 +0,0 @@ -const std = @import("std"); -const assert = @import("../quirks.zig").inlineAssert; -const Allocator = std.mem.Allocator; - -/// Create a HashMap for a key type that can be automatically hashed. -/// If you want finer-grained control, use HashMap directly. -pub fn AutoHashMap(comptime K: type, comptime V: type) type { - return HashMap( - K, - V, - std.hash_map.AutoContext(K), - std.hash_map.default_max_load_percentage, - ); -} - -/// HashMap implementation that supports least-recently-used eviction. -/// -/// Beware of the Zig bug where a hashmap gets slower over time -/// (https://github.com/ziglang/zig/issues/17851). This LRU uses a hashmap -/// and evictions will cause this issue to appear. Callers should keep -/// track of eviction counts and periodically reinitialize the LRU to -/// avoid this issue. The LRU itself can't do this because it doesn't -/// know how to free values. -/// -/// Note: This is a really elementary CS101 version of an LRU right now. -/// This is done initially to get something working. Once we have it working, -/// we can benchmark and improve if this ends up being a source of slowness. -pub fn HashMap( - comptime K: type, - comptime V: type, - comptime Context: type, - comptime max_load_percentage: u64, -) type { - return struct { - const Self = @This(); - const Queue = std.DoublyLinkedList; - const Map = std.HashMapUnmanaged( - K, - *Entry, - Context, - max_load_percentage, - ); - - /// Map to maintain our entries. - map: Map, - - /// Queue to maintain LRU order. - queue: Queue, - - /// The capacity of our map. If this capacity is reached, cache - /// misses will begin evicting entries. - capacity: Map.Size, - - const Entry = struct { - data: KV, - node: Queue.Node, - - fn fromNode(node: *Queue.Node) *Entry { - return @fieldParentPtr("node", node); - } - }; - - pub const KV = struct { - key: K, - value: V, - }; - - /// The result of a getOrPut operation. - pub const GetOrPutResult = struct { - /// The entry that was retrieved. If found_existing is false, - /// then this is a pointer to allocated space to store a V. - /// If found_existing is true, the pointer value is valid, but - /// can be overwritten. - value_ptr: *V, - - /// Whether an existing value was found or not. - found_existing: bool, - - /// If another entry had to be evicted to make space for this - /// put operation, then this is the value that was evicted. - evicted: ?KV, - }; - - pub fn init(capacity: Map.Size) Self { - return .{ - .map = .{}, - .queue = .{}, - .capacity = capacity, - }; - } - - pub fn deinit(self: *Self, alloc: Allocator) void { - // Important: use our queue as a source of truth for dealloc - // because we might keep items in the queue around that aren't - // present in our LRU anymore to prevent future allocations. - var it = self.queue.first; - while (it) |node| { - it = node.next; - alloc.destroy(Entry.fromNode(node)); - } - - self.map.deinit(alloc); - self.* = undefined; - } - - /// Get or put a value for a key. See GetOrPutResult on how to check - /// if an existing value was found, if an existing value was evicted, - /// etc. - pub fn getOrPut(self: *Self, allocator: Allocator, key: K) Allocator.Error!GetOrPutResult { - if (@sizeOf(Context) != 0) - @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContext instead."); - return self.getOrPutContext(allocator, key, undefined); - } - - /// See getOrPut - pub fn getOrPutContext( - self: *Self, - alloc: Allocator, - key: K, - ctx: Context, - ) Allocator.Error!GetOrPutResult { - const map_gop = try self.map.getOrPutContext(alloc, key, ctx); - if (map_gop.found_existing) { - // Move to end to mark as most recently used - self.queue.remove(&map_gop.value_ptr.*.node); - self.queue.append(&map_gop.value_ptr.*.node); - - return GetOrPutResult{ - .found_existing = true, - .value_ptr = &map_gop.value_ptr.*.data.value, - .evicted = null, - }; - } - errdefer _ = self.map.remove(key); - - // We're evicting if our map insertion increased our capacity. - const evict = self.map.count() > self.capacity; - - // Get our entry. If we're not evicting then we allocate a new - // entry. If we are evicting then we avoid allocation by just - // reusing the entry we would've evicted. - const entry: *Entry = if (!evict) try alloc.create(Entry) else entry: { - // Our first node is the least recently used. - const least_used_node = self.queue.popFirst().?; - const least_used_entry: *Entry = .fromNode(least_used_node); - - // Remove the least used from the map - _ = self.map.remove(least_used_entry.data.key); - - break :entry least_used_entry; - }; - errdefer if (!evict) alloc.destroy(entry); - - // Store our entry in the map. - map_gop.value_ptr.* = entry; - - // Mark the entry as most recently used - self.queue.append(&entry.node); - - // Set our key - entry.data.key = key; - - return .{ - .found_existing = map_gop.found_existing, - .value_ptr = &entry.data.value, - .evicted = if (!evict) null else entry.data, - }; - } - - /// Get a value for a key. - pub fn get(self: *const Self, key: K) ?V { - if (@sizeOf(Context) != 0) { - @compileError("getContext must be used."); - } - return self.getContext(key, undefined); - } - - /// See get - pub fn getContext(self: *const Self, key: K, ctx: Context) ?V { - const node = self.map.getContext(key, ctx) orelse return null; - return node.data.value; - } - - /// Resize the LRU. If this shrinks the LRU then LRU items will be - /// deallocated. The deallocated items are returned in the slice. This - /// slice must be freed by the caller. - pub fn resize(self: *Self, alloc: Allocator, capacity: Map.Size) Allocator.Error!?[]V { - // Fastest - if (capacity >= self.capacity) { - self.capacity = capacity; - return null; - } - - // If we're shrinking but we're smaller than the new capacity, - // then we don't have to do anything. - if (self.map.count() <= capacity) { - self.capacity = capacity; - return null; - } - - // We're shrinking and we have more items than the new capacity - const delta = self.map.count() - capacity; - var evicted = try alloc.alloc(V, delta); - - var i: Map.Size = 0; - while (i < delta) : (i += 1) { - const node = self.queue.popFirst().?; - const entry: *Entry = .fromNode(node); - evicted[i] = entry.data.value; - self.queue.remove(node); - _ = self.map.remove(entry.data.key); - alloc.destroy(entry); - } - - self.capacity = capacity; - assert(self.map.count() == capacity); - - return evicted; - } - }; -} - -test "getOrPut" { - const testing = std.testing; - const alloc = testing.allocator; - - const Map = AutoHashMap(u32, u8); - var m = Map.init(2); - defer m.deinit(alloc); - - // Insert cap values, should be hits - { - const gop = try m.getOrPut(alloc, 1); - try testing.expect(!gop.found_existing); - try testing.expect(gop.evicted == null); - gop.value_ptr.* = 1; - } - { - const gop = try m.getOrPut(alloc, 2); - try testing.expect(!gop.found_existing); - try testing.expect(gop.evicted == null); - gop.value_ptr.* = 2; - } - - // 1 is LRU - try testing.expect((try m.getOrPut(alloc, 1)).found_existing); - try testing.expect((try m.getOrPut(alloc, 2)).found_existing); - - // Next should evict - { - const gop = try m.getOrPut(alloc, 3); - try testing.expect(!gop.found_existing); - try testing.expect(gop.evicted != null); - try testing.expect(gop.evicted.?.value == 1); - gop.value_ptr.* = 3; - } - - // Currently: 2 is LRU, let's make 3 LRU - try testing.expect((try m.getOrPut(alloc, 2)).found_existing); - - // Next should evict - { - const gop = try m.getOrPut(alloc, 4); - try testing.expect(!gop.found_existing); - try testing.expect(gop.evicted != null); - try testing.expect(gop.evicted.?.value == 3); - gop.value_ptr.* = 4; - } -} - -test "get" { - const testing = std.testing; - const alloc = testing.allocator; - - const Map = AutoHashMap(u32, u8); - var m = Map.init(2); - defer m.deinit(alloc); - - // Insert cap values, should be hits - { - const gop = try m.getOrPut(alloc, 1); - try testing.expect(!gop.found_existing); - try testing.expect(gop.evicted == null); - gop.value_ptr.* = 1; - } - - try testing.expect(m.get(1) != null); - try testing.expect(m.get(1).? == 1); - try testing.expect(m.get(2) == null); -} - -test "resize shrink without removal" { - const testing = std.testing; - const alloc = testing.allocator; - - const Map = AutoHashMap(u32, u8); - var m = Map.init(2); - defer m.deinit(alloc); - - // Insert cap values, LRU is 1 - { - const gop = try m.getOrPut(alloc, 1); - try testing.expect(!gop.found_existing); - try testing.expect(gop.evicted == null); - gop.value_ptr.* = 1; - } - - // Shrink - const evicted = try m.resize(alloc, 1); - try testing.expect(evicted == null); - { - const gop = try m.getOrPut(alloc, 1); - try testing.expect(gop.found_existing); - } -} - -test "resize shrink and remove" { - const testing = std.testing; - const alloc = testing.allocator; - - const Map = AutoHashMap(u32, u8); - var m = Map.init(2); - defer m.deinit(alloc); - - // Insert cap values, LRU is 1 - { - const gop = try m.getOrPut(alloc, 1); - try testing.expect(!gop.found_existing); - try testing.expect(gop.evicted == null); - gop.value_ptr.* = 1; - } - { - const gop = try m.getOrPut(alloc, 2); - try testing.expect(!gop.found_existing); - try testing.expect(gop.evicted == null); - gop.value_ptr.* = 2; - } - - // Shrink - const evicted = try m.resize(alloc, 1); - defer alloc.free(evicted.?); - try testing.expectEqual(@as(usize, 1), evicted.?.len); - { - const gop = try m.getOrPut(alloc, 1); - try testing.expect(!gop.found_existing); - try testing.expect(gop.evicted.?.value == 2); - gop.value_ptr.* = 1; - } -} diff --git a/vendor/libghostty-vt/src/datastruct/main.zig b/vendor/libghostty-vt/src/datastruct/main.zig index bfee2342..9fb0bae9 100644 --- a/vendor/libghostty-vt/src/datastruct/main.zig +++ b/vendor/libghostty-vt/src/datastruct/main.zig @@ -5,17 +5,17 @@ const blocking_queue = @import("blocking_queue.zig"); const cache_table = @import("cache_table.zig"); const circ_buf = @import("circ_buf.zig"); const intrusive_linked_list = @import("intrusive_linked_list.zig"); -const segmented_pool = @import("segmented_pool.zig"); const split_tree = @import("split_tree.zig"); -pub const lru = @import("lru.zig"); pub const BlockingQueue = blocking_queue.BlockingQueue; pub const CacheTable = cache_table.CacheTable; pub const CircBuf = circ_buf.CircBuf; pub const IntrusiveDoublyLinkedList = intrusive_linked_list.DoublyLinkedList; +pub const LimitedAllocator = @import("limited_allocator.zig").LimitedAllocator; pub const MessageData = @import("message_data.zig").MessageData; -pub const SegmentedPool = segmented_pool.SegmentedPool; pub const SplitTree = split_tree.SplitTree; +pub const UntouchedPool = @import("untouched_pool.zig").UntouchedPool; +pub const WasmPagePool = @import("wasm_page_pool.zig").WasmPagePool; test { @import("std").testing.refAllDecls(@This()); diff --git a/vendor/libghostty-vt/src/datastruct/segmented_list.zig b/vendor/libghostty-vt/src/datastruct/segmented_list.zig new file mode 100644 index 00000000..5c0601c5 --- /dev/null +++ b/vendor/libghostty-vt/src/datastruct/segmented_list.zig @@ -0,0 +1,533 @@ +//! Code taken from 0.15.2 `std.segmented_list` (MIT license). See +//! lib/compat/README.md for license and details. +const std = @import("std"); +const assert = @import("../quirks.zig").inlineAssert; +const testing = std.testing; +const mem = std.mem; +const Allocator = std.mem.Allocator; + +// Imagine that `fn at(self: *Self, index: usize) &T` is a customer asking for a box +// from a warehouse, based on a flat array, boxes ordered from 0 to N - 1. +// But the warehouse actually stores boxes in shelves of increasing powers of 2 sizes. +// So when the customer requests a box index, we have to translate it to shelf index +// and box index within that shelf. Illustration: +// +// customer indexes: +// shelf 0: 0 +// shelf 1: 1 2 +// shelf 2: 3 4 5 6 +// shelf 3: 7 8 9 10 11 12 13 14 +// shelf 4: 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 +// shelf 5: 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 +// ... +// +// warehouse indexes: +// shelf 0: 0 +// shelf 1: 0 1 +// shelf 2: 0 1 2 3 +// shelf 3: 0 1 2 3 4 5 6 7 +// shelf 4: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 +// shelf 5: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 +// ... +// +// With this arrangement, here are the equations to get the shelf index and +// box index based on customer box index: +// +// shelf_index = floor(log2(customer_index + 1)) +// shelf_count = ceil(log2(box_count + 1)) +// box_index = customer_index + 1 - 2 ** shelf +// shelf_size = 2 ** shelf_index +// +// Now we complicate it a little bit further by adding a preallocated shelf, which must be +// a power of 2: +// prealloc=4 +// +// customer indexes: +// prealloc: 0 1 2 3 +// shelf 0: 4 5 6 7 8 9 10 11 +// shelf 1: 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 +// shelf 2: 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 +// ... +// +// warehouse indexes: +// prealloc: 0 1 2 3 +// shelf 0: 0 1 2 3 4 5 6 7 +// shelf 1: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 +// shelf 2: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 +// ... +// +// Now the equations are: +// +// shelf_index = floor(log2(customer_index + prealloc)) - log2(prealloc) - 1 +// shelf_count = ceil(log2(box_count + prealloc)) - log2(prealloc) - 1 +// box_index = customer_index + prealloc - 2 ** (log2(prealloc) + 1 + shelf) +// shelf_size = prealloc * 2 ** (shelf_index + 1) + +/// This is a stack data structure where pointers to indexes have the same lifetime as the data structure +/// itself, unlike ArrayList where append() invalidates all existing element pointers. +/// The tradeoff is that elements are not guaranteed to be contiguous. For that, use ArrayList. +/// Note however that most elements are contiguous, making this data structure cache-friendly. +/// +/// Because it never has to copy elements from an old location to a new location, it does not require +/// its elements to be copyable, and it avoids wasting memory when backed by an ArenaAllocator. +/// Note that the append() and pop() convenience methods perform a copy, but you can instead use +/// addOne(), at(), setCapacity(), and shrinkCapacity() to avoid copying items. +/// +/// This data structure has O(1) append and O(1) pop. +/// +/// It supports preallocated elements, making it especially well suited when the expected maximum +/// size is small. `prealloc_item_count` must be 0, or a power of 2. +pub fn SegmentedList(comptime T: type, comptime prealloc_item_count: usize) type { + return struct { + const Self = @This(); + const ShelfIndex = std.math.Log2Int(usize); + + const prealloc_exp: ShelfIndex = blk: { + // we don't use the prealloc_exp constant when prealloc_item_count is 0 + // but lazy-init may still be triggered by other code so supply a value + if (prealloc_item_count == 0) { + break :blk 0; + } else { + assert(std.math.isPowerOfTwo(prealloc_item_count)); + const value = std.math.log2_int(usize, prealloc_item_count); + break :blk value; + } + }; + + prealloc_segment: [prealloc_item_count]T = undefined, + dynamic_segments: [][*]T = &[_][*]T{}, + len: usize = 0, + + pub const prealloc_count = prealloc_item_count; + + fn AtType(comptime SelfType: type) type { + if (@typeInfo(SelfType).pointer.is_const) { + return *const T; + } else { + return *T; + } + } + + pub fn deinit(self: *Self, allocator: Allocator) void { + self.freeShelves(allocator, @as(ShelfIndex, @intCast(self.dynamic_segments.len)), 0); + allocator.free(self.dynamic_segments); + self.* = undefined; + } + + pub fn at(self: anytype, i: usize) AtType(@TypeOf(self)) { + assert(i < self.len); + return self.uncheckedAt(i); + } + + pub fn count(self: Self) usize { + return self.len; + } + + pub fn append(self: *Self, allocator: Allocator, item: T) Allocator.Error!void { + const new_item_ptr = try self.addOne(allocator); + new_item_ptr.* = item; + } + + pub fn appendSlice(self: *Self, allocator: Allocator, items: []const T) Allocator.Error!void { + for (items) |item| { + try self.append(allocator, item); + } + } + + pub fn pop(self: *Self) ?T { + if (self.len == 0) return null; + + const index = self.len - 1; + const result = uncheckedAt(self, index).*; + self.len = index; + return result; + } + + pub fn addOne(self: *Self, allocator: Allocator) Allocator.Error!*T { + const new_length = self.len + 1; + try self.growCapacity(allocator, new_length); + const result = uncheckedAt(self, self.len); + self.len = new_length; + return result; + } + + /// Reduce length to `new_len`. + /// Invalidates pointers for the elements at index new_len and beyond. + pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void { + assert(new_len <= self.len); + self.len = new_len; + } + + /// Invalidates all element pointers. + pub fn clearRetainingCapacity(self: *Self) void { + self.len = 0; + } + + /// Invalidates all element pointers. + pub fn clearAndFree(self: *Self, allocator: Allocator) void { + self.setCapacity(allocator, 0) catch unreachable; + self.len = 0; + } + + /// Grows or shrinks capacity to match usage. + /// TODO update this and related methods to match the conventions set by ArrayList + pub fn setCapacity(self: *Self, allocator: Allocator, new_capacity: usize) Allocator.Error!void { + if (prealloc_item_count != 0) { + if (new_capacity <= @as(usize, 1) << (prealloc_exp + @as(ShelfIndex, @intCast(self.dynamic_segments.len)))) { + return self.shrinkCapacity(allocator, new_capacity); + } + } + return self.growCapacity(allocator, new_capacity); + } + + /// Only grows capacity, or retains current capacity. + pub fn growCapacity(self: *Self, allocator: Allocator, new_capacity: usize) Allocator.Error!void { + const new_cap_shelf_count = shelfCount(new_capacity); + const old_shelf_count = @as(ShelfIndex, @intCast(self.dynamic_segments.len)); + if (new_cap_shelf_count <= old_shelf_count) return; + + const new_dynamic_segments = try allocator.alloc([*]T, new_cap_shelf_count); + errdefer allocator.free(new_dynamic_segments); + + var i: ShelfIndex = 0; + while (i < old_shelf_count) : (i += 1) { + new_dynamic_segments[i] = self.dynamic_segments[i]; + } + errdefer while (i > old_shelf_count) : (i -= 1) { + allocator.free(new_dynamic_segments[i][0..shelfSize(i)]); + }; + while (i < new_cap_shelf_count) : (i += 1) { + new_dynamic_segments[i] = (try allocator.alloc(T, shelfSize(i))).ptr; + } + + allocator.free(self.dynamic_segments); + self.dynamic_segments = new_dynamic_segments; + } + + /// Only shrinks capacity or retains current capacity. + /// It may fail to reduce the capacity in which case the capacity will remain unchanged. + pub fn shrinkCapacity(self: *Self, allocator: Allocator, new_capacity: usize) void { + if (new_capacity <= prealloc_item_count) { + const len = @as(ShelfIndex, @intCast(self.dynamic_segments.len)); + self.freeShelves(allocator, len, 0); + allocator.free(self.dynamic_segments); + self.dynamic_segments = &[_][*]T{}; + return; + } + + const new_cap_shelf_count = shelfCount(new_capacity); + const old_shelf_count = @as(ShelfIndex, @intCast(self.dynamic_segments.len)); + assert(new_cap_shelf_count <= old_shelf_count); + if (new_cap_shelf_count == old_shelf_count) return; + + // freeShelves() must be called before resizing the dynamic + // segments, but we don't know if resizing the dynamic segments + // will work until we try it. So we must allocate a fresh memory + // buffer in order to reduce capacity. + const new_dynamic_segments = allocator.alloc([*]T, new_cap_shelf_count) catch return; + self.freeShelves(allocator, old_shelf_count, new_cap_shelf_count); + if (allocator.resize(self.dynamic_segments, new_cap_shelf_count)) { + // We didn't need the new memory allocation after all. + self.dynamic_segments = self.dynamic_segments[0..new_cap_shelf_count]; + allocator.free(new_dynamic_segments); + } else { + // Good thing we allocated that new memory slice. + @memcpy(new_dynamic_segments, self.dynamic_segments[0..new_cap_shelf_count]); + allocator.free(self.dynamic_segments); + self.dynamic_segments = new_dynamic_segments; + } + } + + pub fn shrink(self: *Self, new_len: usize) void { + assert(new_len <= self.len); + // TODO take advantage of the new realloc semantics + self.len = new_len; + } + + pub fn writeToSlice(self: *Self, dest: []T, start: usize) void { + const end = start + dest.len; + assert(end <= self.len); + + var i = start; + if (end <= prealloc_item_count) { + const src = self.prealloc_segment[i..end]; + @memcpy(dest[i - start ..][0..src.len], src); + return; + } else if (i < prealloc_item_count) { + const src = self.prealloc_segment[i..]; + @memcpy(dest[i - start ..][0..src.len], src); + i = prealloc_item_count; + } + + while (i < end) { + const shelf_index = shelfIndex(i); + const copy_start = boxIndex(i, shelf_index); + const copy_end = @min(shelfSize(shelf_index), copy_start + end - i); + const src = self.dynamic_segments[shelf_index][copy_start..copy_end]; + @memcpy(dest[i - start ..][0..src.len], src); + i += (copy_end - copy_start); + } + } + + pub fn uncheckedAt(self: anytype, index: usize) AtType(@TypeOf(self)) { + if (index < prealloc_item_count) { + return &self.prealloc_segment[index]; + } + const shelf_index = shelfIndex(index); + const box_index = boxIndex(index, shelf_index); + return &self.dynamic_segments[shelf_index][box_index]; + } + + fn shelfCount(box_count: usize) ShelfIndex { + if (prealloc_item_count == 0) { + return log2_int_ceil(usize, box_count + 1); + } + return log2_int_ceil(usize, box_count + prealloc_item_count) - prealloc_exp - 1; + } + + fn shelfSize(shelf_index: ShelfIndex) usize { + if (prealloc_item_count == 0) { + return @as(usize, 1) << shelf_index; + } + return @as(usize, 1) << (shelf_index + (prealloc_exp + 1)); + } + + fn shelfIndex(list_index: usize) ShelfIndex { + if (prealloc_item_count == 0) { + return std.math.log2_int(usize, list_index + 1); + } + return std.math.log2_int(usize, list_index + prealloc_item_count) - prealloc_exp - 1; + } + + fn boxIndex(list_index: usize, shelf_index: ShelfIndex) usize { + if (prealloc_item_count == 0) { + return (list_index + 1) - (@as(usize, 1) << shelf_index); + } + return list_index + prealloc_item_count - (@as(usize, 1) << ((prealloc_exp + 1) + shelf_index)); + } + + fn freeShelves(self: *Self, allocator: Allocator, from_count: ShelfIndex, to_count: ShelfIndex) void { + var i = from_count; + while (i != to_count) { + i -= 1; + allocator.free(self.dynamic_segments[i][0..shelfSize(i)]); + } + } + + pub const Iterator = BaseIterator(*Self, *T); + pub const ConstIterator = BaseIterator(*const Self, *const T); + fn BaseIterator(comptime SelfType: type, comptime ElementPtr: type) type { + return struct { + list: SelfType, + index: usize, + box_index: usize, + shelf_index: ShelfIndex, + shelf_size: usize, + + pub fn next(it: *@This()) ?ElementPtr { + if (it.index >= it.list.len) return null; + if (it.index < prealloc_item_count) { + const ptr = &it.list.prealloc_segment[it.index]; + it.index += 1; + if (it.index == prealloc_item_count) { + it.box_index = 0; + it.shelf_index = 0; + it.shelf_size = prealloc_item_count * 2; + } + return ptr; + } + + const ptr = &it.list.dynamic_segments[it.shelf_index][it.box_index]; + it.index += 1; + it.box_index += 1; + if (it.box_index == it.shelf_size) { + it.shelf_index += 1; + it.box_index = 0; + it.shelf_size *= 2; + } + return ptr; + } + + pub fn prev(it: *@This()) ?ElementPtr { + if (it.index == 0) return null; + + it.index -= 1; + if (it.index < prealloc_item_count) return &it.list.prealloc_segment[it.index]; + + if (it.box_index == 0) { + it.shelf_index -= 1; + it.shelf_size /= 2; + it.box_index = it.shelf_size - 1; + } else { + it.box_index -= 1; + } + + return &it.list.dynamic_segments[it.shelf_index][it.box_index]; + } + + pub fn peek(it: *@This()) ?ElementPtr { + if (it.index >= it.list.len) + return null; + if (it.index < prealloc_item_count) + return &it.list.prealloc_segment[it.index]; + + return &it.list.dynamic_segments[it.shelf_index][it.box_index]; + } + + pub fn set(it: *@This(), index: usize) void { + it.index = index; + if (index < prealloc_item_count) return; + it.shelf_index = shelfIndex(index); + it.box_index = boxIndex(index, it.shelf_index); + it.shelf_size = shelfSize(it.shelf_index); + } + }; + } + + pub fn iterator(self: *Self, start_index: usize) Iterator { + var it = Iterator{ + .list = self, + .index = undefined, + .shelf_index = undefined, + .box_index = undefined, + .shelf_size = undefined, + }; + it.set(start_index); + return it; + } + + pub fn constIterator(self: *const Self, start_index: usize) ConstIterator { + var it = ConstIterator{ + .list = self, + .index = undefined, + .shelf_index = undefined, + .box_index = undefined, + .shelf_size = undefined, + }; + it.set(start_index); + return it; + } + }; +} + +test "basic usage" { + try testSegmentedList(0); + try testSegmentedList(1); + try testSegmentedList(2); + try testSegmentedList(4); + try testSegmentedList(8); + try testSegmentedList(16); +} + +fn testSegmentedList(comptime prealloc: usize) !void { + var list = SegmentedList(i32, prealloc){}; + defer list.deinit(testing.allocator); + + { + var i: usize = 0; + while (i < 100) : (i += 1) { + try list.append(testing.allocator, @as(i32, @intCast(i + 1))); + try testing.expect(list.len == i + 1); + } + } + + { + var i: usize = 0; + while (i < 100) : (i += 1) { + try testing.expect(list.at(i).* == @as(i32, @intCast(i + 1))); + } + } + + { + var it = list.iterator(0); + var x: i32 = 0; + while (it.next()) |item| { + x += 1; + try testing.expect(item.* == x); + } + try testing.expect(x == 100); + while (it.prev()) |item| : (x -= 1) { + try testing.expect(item.* == x); + } + try testing.expect(x == 0); + } + + { + var it = list.constIterator(0); + var x: i32 = 0; + while (it.next()) |item| { + x += 1; + try testing.expect(item.* == x); + } + try testing.expect(x == 100); + while (it.prev()) |item| : (x -= 1) { + try testing.expect(item.* == x); + } + try testing.expect(x == 0); + } + + try testing.expect(list.pop().? == 100); + try testing.expect(list.len == 99); + + try list.appendSlice(testing.allocator, &[_]i32{ 1, 2, 3 }); + try testing.expect(list.len == 102); + try testing.expect(list.pop().? == 3); + try testing.expect(list.pop().? == 2); + try testing.expect(list.pop().? == 1); + try testing.expect(list.len == 99); + + try list.appendSlice(testing.allocator, &[_]i32{}); + try testing.expect(list.len == 99); + + { + var i: i32 = 99; + while (list.pop()) |item| : (i -= 1) { + try testing.expect(item == i); + list.shrinkCapacity(testing.allocator, list.len); + } + } + + { + var control: [100]i32 = undefined; + var dest: [100]i32 = undefined; + + var i: i32 = 0; + while (i < 100) : (i += 1) { + try list.append(testing.allocator, i + 1); + control[@as(usize, @intCast(i))] = i + 1; + } + + @memset(dest[0..], 0); + list.writeToSlice(dest[0..], 0); + try testing.expect(mem.eql(i32, control[0..], dest[0..])); + + @memset(dest[0..], 0); + list.writeToSlice(dest[50..], 50); + try testing.expect(mem.eql(i32, control[50..], dest[50..])); + } + + try list.setCapacity(testing.allocator, 0); +} + +test "clearRetainingCapacity" { + var list = SegmentedList(i32, 1){}; + defer list.deinit(testing.allocator); + + try list.appendSlice(testing.allocator, &[_]i32{ 4, 5 }); + list.clearRetainingCapacity(); + try list.append(testing.allocator, 6); + try testing.expect(list.at(0).* == 6); + try testing.expect(list.len == 1); + list.clearRetainingCapacity(); + try testing.expect(list.len == 0); +} + +/// TODO look into why this std.math function was changed in +/// fc9430f56798a53f9393a697f4ccd6bf9981b970. +fn log2_int_ceil(comptime T: type, x: T) std.math.Log2Int(T) { + assert(x != 0); + const log2_val = std.math.log2_int(T, x); + if (@as(T, 1) << log2_val == x) + return log2_val; + return log2_val + 1; +} diff --git a/vendor/libghostty-vt/src/datastruct/segmented_pool.zig b/vendor/libghostty-vt/src/datastruct/segmented_pool.zig deleted file mode 100644 index 328eb239..00000000 --- a/vendor/libghostty-vt/src/datastruct/segmented_pool.zig +++ /dev/null @@ -1,95 +0,0 @@ -const std = @import("std"); -const assert = @import("../quirks.zig").inlineAssert; -const Allocator = std.mem.Allocator; -const testing = std.testing; - -/// A data structure where you can get stable (never copied) pointers to -/// a type that automatically grows if necessary. The values can be "put back" -/// but are expected to be put back IN ORDER. -/// -/// This is implemented specifically for libuv write requests, since the -/// write requests must have a stable pointer and are guaranteed to be processed -/// in order for a single stream. -/// -/// This is NOT thread safe. -pub fn SegmentedPool(comptime T: type, comptime prealloc: usize) type { - return struct { - const Self = @This(); - - i: usize = 0, - available: usize = prealloc, - list: std.SegmentedList(T, prealloc) = .{ .len = prealloc }, - - pub fn deinit(self: *Self, alloc: Allocator) void { - self.list.deinit(alloc); - self.* = undefined; - } - - /// Get the next available value out of the list. This will not - /// grow the list. - pub fn get(self: *Self) !*T { - // Error to not have any - if (self.available == 0) return error.OutOfValues; - - // The index we grab is just i % len, so we wrap around to the front. - const i = @mod(self.i, self.list.len); - self.i +%= 1; // Wrapping addition to swe go back to 0 - self.available -= 1; - return self.list.at(i); - } - - /// Get the next available value out of the list and grow the list - /// if necessary. - pub fn getGrow(self: *Self, alloc: Allocator) !*T { - if (self.available == 0) try self.grow(alloc); - return try self.get(); - } - - fn grow(self: *Self, alloc: Allocator) !void { - try self.list.growCapacity(alloc, self.list.len * 2); - self.i = self.list.len; - self.available = self.list.len; - self.list.len *= 2; - } - - /// Put a value back. The value put back is expected to be the - /// in order of get. - pub fn put(self: *Self) void { - self.available += 1; - assert(self.available <= self.list.len); - } - }; -} - -test "SegmentedPool" { - var list: SegmentedPool(u8, 2) = .{}; - defer list.deinit(testing.allocator); - try testing.expectEqual(@as(usize, 2), list.available); - - // Get to capacity - const v1 = try list.get(); - const v2 = try list.get(); - try testing.expect(v1 != v2); - try testing.expectError(error.OutOfValues, list.get()); - - // Test writing for later - v1.* = 42; - - // Put a value back - list.put(); - const temp = try list.get(); - try testing.expect(v1 == temp); - try testing.expect(temp.* == 42); - try testing.expectError(error.OutOfValues, list.get()); - - // Grow - const v3 = try list.getGrow(testing.allocator); - try testing.expect(v1 != v3 and v2 != v3); - _ = try list.get(); - try testing.expectError(error.OutOfValues, list.get()); - - // Put a value back - list.put(); - try testing.expect(v1 == try list.get()); - try testing.expectError(error.OutOfValues, list.get()); -} diff --git a/vendor/libghostty-vt/src/datastruct/split_tree.zig b/vendor/libghostty-vt/src/datastruct/split_tree.zig index 1dc924ca..012f107f 100644 --- a/vendor/libghostty-vt/src/datastruct/split_tree.zig +++ b/vendor/libghostty-vt/src/datastruct/split_tree.zig @@ -183,6 +183,18 @@ pub fn SplitTree(comptime V: type) type { }; } + /// Find the handle within this tree that corresponds + /// to the given view. Uses pointer equality. + pub fn locate(self: *const Self, view: *const View) ?Node.Handle { + var it = self.iterator(); + while (it.next()) |entry| { + if (entry.view == view) { + return entry.handle; + } + } + return null; + } + /// An iterator over all the views in the tree. pub fn iterator( self: *const Self, diff --git a/vendor/libghostty-vt/src/datastruct/untouched_pool.zig b/vendor/libghostty-vt/src/datastruct/untouched_pool.zig new file mode 100644 index 00000000..a8ed4d31 --- /dev/null +++ b/vendor/libghostty-vt/src/datastruct/untouched_pool.zig @@ -0,0 +1,297 @@ +const std = @import("std"); +const assert = std.debug.assert; +const Allocator = std.mem.Allocator; +const Alignment = std.mem.Alignment; + +/// A fixed-size item pool whose bookkeeping never touches item memory. +/// +/// std.heap.MemoryPool keeps its free list inside the items intrusively, +/// meaning it has to touch allocated item memory. For memory that is +/// demand-paged, that write forces the OS to create a physical page +/// for nothing (to mark it free!). +/// +/// This pool keeps the free list in a separate array allocated from a +/// general-purpose allocator and allocates every item individually from +/// the item allocator with the requested alignment. The pool never reads +/// or writes an item until it is needed. +/// +/// Contracts: +/// +/// - The pool never zeroes. Callers that need zeroed items must use an +/// item allocator that returns zeroed memory and must zero (or +/// decommit) an item before destroy(). +/// - destroy() never allocates and never fails: create() reserves a +/// free-list slot for every live item before allocating a new one. +/// - The pool tracks free items only. Every item must be returned with +/// destroy() or release() before reset() or deinit(), or it leaks. +/// This is asserted in safe builds. +/// +/// The tradeoff is that this isn't as fast as std.heap.MemoryPool, its +/// not as cache friendly. But benchmarks show that the cost is minimal +/// and if the tradeoff of not touching the memory is important, then +/// this pays off. +pub fn UntouchedPool(comptime Item: type, comptime alignment: Alignment) type { + return struct { + const Self = @This(); + + pub const item_size = @sizeOf(Item); + pub const item_alignment: Alignment = alignment.max(.of(Item)); + pub const ItemPtr = *align(item_alignment.toByteUnits()) Item; + pub const ResetMode = std.heap.ArenaAllocator.ResetMode; + + /// The allocator items are allocated from. + allocator: Allocator, + + /// The general-purpose allocator for the free list. + gpa: Allocator, + + /// Free items. The most recently destroyed item is handed out first. + free: std.ArrayList(ItemPtr), + + /// Number of items currently allocated from the item allocator, + /// free or in use. `free.capacity >= live` always holds so that + /// destroy() never has to grow the free list. + live: usize, + + /// Create a pool with `preheat` items already allocated. + pub fn initCapacity( + gpa: Allocator, + item_alloc: Allocator, + preheat: usize, + ) Allocator.Error!Self { + var self: Self = .{ + .allocator = item_alloc, + .gpa = gpa, + .free = .empty, + .live = 0, + }; + errdefer self.deinit(); + + try self.free.ensureTotalCapacityPrecise(gpa, preheat); + for (0..preheat) |_| { + const item = try self.allocItem(); + self.free.appendAssumeCapacity(item); + } + + return self; + } + + /// Free all items and the free list. Every item must have been + /// returned with destroy() or release(). + pub fn deinit(self: *Self) void { + assert(self.live == self.free.items.len); + for (self.free.items) |item| self.allocator.free(bytes(item)); + self.free.deinit(self.gpa); + self.* = undefined; + } + + /// Free items so that the retained free items fit `mode`. Every + /// item must have been returned with destroy() or release(). + /// + /// This mirrors std.heap.MemoryPool.reset; it always succeeds + /// (returns true) because nothing is reallocated. + pub fn reset(self: *Self, mode: ResetMode) bool { + assert(self.live == self.free.items.len); + const retain_bytes: usize = switch (mode) { + .free_all => 0, + .retain_capacity => return true, + .retain_with_limit => |limit| limit, + }; + + const retain_items = retain_bytes / item_size; + while (self.free.items.len > retain_items) { + const item = self.free.pop().?; + self.allocator.free(bytes(item)); + self.live -= 1; + } + + return true; + } + + /// Get an item. This pops a free item without touching it or, + /// when none is free, allocates a new one from the item + /// allocator. + pub fn create(self: *Self) Allocator.Error!ItemPtr { + if (self.free.pop()) |item| return item; + + // Reserve the free-list slot for the new item before + // allocating it so that destroy() can never fail. + try self.free.ensureTotalCapacity(self.gpa, self.live + 1); + return try self.allocItem(); + } + + /// Return an item to the free list for reuse. The item is not + /// modified or zeroed so it is up to the caller. + pub fn destroy(self: *Self, item: ItemPtr) void { + assert(self.free.items.len < self.live); + self.free.appendAssumeCapacity(item); + } + + /// Return an item straight to the item allocator instead of the + /// free list. This is for teardown paths that would otherwise + /// have to zero an item only for it to be freed moments later. + pub fn release(self: *Self, item: ItemPtr) void { + assert(self.free.items.len < self.live); + self.allocator.free(bytes(item)); + self.live -= 1; + } + + fn allocItem(self: *Self) Allocator.Error!ItemPtr { + assert(self.free.capacity > self.live); + const memory = try self.allocator.alignedAlloc( + u8, + item_alignment, + item_size, + ); + self.live += 1; + return @ptrCast(memory.ptr); + } + + fn bytes(item: ItemPtr) []align(item_alignment.toByteUnits()) u8 { + return std.mem.asBytes(item); + } + }; +} + +/// Test item: one minimum OS page, page-aligned, like a terminal page. +const TestPool = UntouchedPool( + [std.heap.page_size_min]u8, + .fromByteUnits(std.heap.page_size_min), +); + +test "UntouchedPool: create, destroy, reuse" { + const testing = std.testing; + var pool: TestPool = try .initCapacity(testing.allocator, testing.allocator, 0); + defer pool.deinit(); + + const a = try pool.create(); + const b = try pool.create(); + const c = try pool.create(); + try testing.expect(a != b); + try testing.expect(a != c); + try testing.expect(b != c); + + // Freed items are recycled, most recent first. + pool.destroy(a); + pool.destroy(b); + try testing.expectEqual(b, try pool.create()); + try testing.expectEqual(a, try pool.create()); + + pool.destroy(a); + pool.destroy(b); + pool.destroy(c); +} + +test "UntouchedPool: create and destroy never touch items" { + const testing = std.testing; + const preheat = 4; + + // Back the item allocator with memory we can inspect. + const backing = try testing.allocator.alignedAlloc( + u8, + .fromByteUnits(std.heap.page_size_min), + preheat * TestPool.item_size, + ); + defer testing.allocator.free(backing); + var fba: std.heap.FixedBufferAllocator = .init(backing); + + var pool: TestPool = try .initCapacity( + testing.allocator, + fba.allocator(), + preheat, + ); + defer pool.deinit(); + try testing.expectEqual(preheat * TestPool.item_size, fba.end_index); + + // Lay the sentinel down after preheat: allocation itself may write + // (the Allocator interface fills fresh memory with undefined in + // safe builds, which valgrind also tracks). The sentinel must differ + // from Zig's 0xAA undefined pattern so that any write is visible. + const sentinel: u8 = 0x5A; + @memset(backing, sentinel); + + // Every preheated item comes out untouched and without allocating. + var items: [preheat]TestPool.ItemPtr = undefined; + for (&items) |*item| { + item.* = try pool.create(); + try testing.expectEqual(preheat * TestPool.item_size, fba.end_index); + try testing.expect(std.mem.allEqual(u8, item.*, sentinel)); + } + + // Destroying and re-creating doesn't touch them either. + for (items) |item| pool.destroy(item); + try testing.expect(std.mem.allEqual(u8, backing, sentinel)); + for (&items) |*item| { + item.* = try pool.create(); + try testing.expect(std.mem.allEqual(u8, item.*, sentinel)); + } + for (items) |item| pool.destroy(item); +} + +test "UntouchedPool: destroy never allocates from the general allocator" { + const testing = std.testing; + + // A general allocator that fails every allocation: after create has + // reserved the free-list slot, destroy must not need it. + var failing: std.testing.FailingAllocator = .init(testing.allocator, .{ + .fail_index = 0, + }); + + var pool: TestPool = try .initCapacity(testing.allocator, testing.allocator, 0); + defer pool.deinit(); + + // The pool grows the free list through its own gpa, so swap in the + // failing one only around destroy. + var items: [64]TestPool.ItemPtr = undefined; + for (&items) |*item| item.* = try pool.create(); + const gpa = pool.gpa; + pool.gpa = failing.allocator(); + for (items) |item| pool.destroy(item); + pool.gpa = gpa; + try testing.expectEqual(items.len, pool.free.items.len); +} + +test "UntouchedPool: reset retains at most the limit" { + const testing = std.testing; + var pool: TestPool = try .initCapacity(testing.allocator, testing.allocator, 4); + defer pool.deinit(); + + // Free everything above the limit + try testing.expect(pool.reset(.{ .retain_with_limit = 2 * TestPool.item_size })); + try testing.expectEqual(2, pool.free.items.len); + try testing.expectEqual(2, pool.live); + + // retain_capacity keeps everything + try testing.expect(pool.reset(.retain_capacity)); + try testing.expectEqual(2, pool.free.items.len); + + // Retained items are handed out without allocating; new items + // beyond them are allocated as needed. + const a = try pool.create(); + const b = try pool.create(); + try testing.expectEqual(2, pool.live); + const c = try pool.create(); + try testing.expectEqual(3, pool.live); + pool.destroy(a); + pool.destroy(b); + pool.destroy(c); + + try testing.expect(pool.reset(.free_all)); + try testing.expectEqual(0, pool.free.items.len); + try testing.expectEqual(0, pool.live); +} + +test "UntouchedPool: release frees immediately" { + const testing = std.testing; + var pool: TestPool = try .initCapacity(testing.allocator, testing.allocator, 1); + defer pool.deinit(); + + const a = try pool.create(); + const b = try pool.create(); + try testing.expectEqual(2, pool.live); + pool.release(a); + try testing.expectEqual(1, pool.live); + try testing.expectEqual(0, pool.free.items.len); + pool.destroy(b); + try testing.expectEqual(1, pool.free.items.len); +} diff --git a/vendor/libghostty-vt/src/datastruct/wasm_page_pool.zig b/vendor/libghostty-vt/src/datastruct/wasm_page_pool.zig new file mode 100644 index 00000000..0f73eec6 --- /dev/null +++ b/vendor/libghostty-vt/src/datastruct/wasm_page_pool.zig @@ -0,0 +1,162 @@ +const std = @import("std"); +const builtin = @import("builtin"); +const assert = std.debug.assert; +const Allocator = std.mem.Allocator; + +/// A memory pool of wasm-page-multiple-sized items backed directly by +/// wasm linear memory, for wasm targets only. +/// +/// This is necessary for two reasons: the std.heap.MemoryPool grows 1.5x +/// at each growth point. The backing allocator for that is usually a GPA +/// which is the BrkAllocator for wasm. This grows by power-of-two +/// big-allocation slots. If you pair these together you get a massive +/// permanent linear memory growth. Native (non-wasm) targets don't care +/// because unused virtual mappings are effectively free, but this isn't +/// exactly true for Wasm runtimes. +/// +/// This pool instead grows exactly @sizeOf(Item) bytes of fresh linear +/// memory per item with memory.grow (which also guarantees wasm-page +/// alignment and zeroing) and recycles freed items through a free list +/// that is container-level, i.e. shared by every pool of the same Item +/// type in the module instance. Every freed item is immediately +/// reusable by every pool, and each item costs exactly @sizeOf(Item) +/// reserved bytes, ever. +/// +/// The "shared by every pool of the same Item type" is really important: +/// the normal Ghostty memory pool is per-terminal. This one is per-module. +/// The Ghostty wasm modules are not multi-threaded so this doesn't require +/// any synchronization. But this means that all terminals share one pool +/// so memory doesn't balloon like crazy that way either. +/// +/// Requirements on Item: +/// +/// - @sizeOf(Item) must be a nonzero multiple of the wasm page size +/// (64KiB), since memory.grow allocates in whole pages. This is +/// also what makes the pool exact-fit: any other size would strand +/// the remainder of the last page. +/// - Natural alignment must be at most the wasm page size. +/// +/// Free-list items are dirty except that their first pointer-size bytes +/// hold the intrusive free-list node, exactly like the std MemoryPool. +/// Callers that need zeroed items must zero them (fresh items from +/// memory.grow are zero by the wasm spec; recycled items retain +/// whatever the caller left, so zero either on destroy or on create). +/// +/// The API mirrors the native page pool (datastruct.UntouchedPool: +/// initCapacity/deinit/reset/create/destroy plus the allocator field), +/// so PageList can swap them at comptime. +pub fn WasmPagePool(comptime Item: type) type { + return struct { + const Self = @This(); + + comptime { + if (builtin.target.cpu.arch.isWasm()) { + // The shared free list (and wasm's single linear + // memory) requires a single-threaded target. + assert(builtin.single_threaded); + // Items are whole wasm pages + assert(item_size > 0); + assert(item_size % std.heap.page_size_min == 0); + assert(@alignOf(Item) <= std.heap.page_size_min); + // Free items store the intrusive node in their bytes. + assert(item_size >= @sizeOf(std.SinglyLinkedList.Node)); + } + } + + /// The allocator this managed pool was initialized with, + /// carried for interface compatibility with the std managed + /// memory pools. Pool items never come from it (they come + /// from memory.grow), but callers may use it for related + /// allocations that don't fit the pool. + allocator: Allocator, + + pub const item_size = @sizeOf(Item); + pub const ItemPtr = *align(std.heap.page_size_min) Item; + + /// Freed items, shared by every pool of this Item type in the + /// module instance. + var free_list: std.SinglyLinkedList = .{}; + + pub fn initCapacity( + gpa: Allocator, + allocator: Allocator, + preheat: usize, + ) Allocator.Error!Self { + // The free list is intrusive so we never allocate from the + // general purpose allocator. + _ = gpa; + + // Preheating is intentionally a no-op: item creation is a + // cheap memory.grow or free-list pop. And we want to avoid + // the preallocation mem cost. + _ = preheat; + return .{ .allocator = allocator }; + } + + pub fn deinit(self: *Self) void { + // Items are global to the instance and outlive the pool so + // other pools can reuse them. Callers must destroy() any + // items they still hold before deinit or they leak. + self.* = undefined; + } + + pub fn reset( + self: *Self, + mode: std.heap.ArenaAllocator.ResetMode, + ) bool { + // There is nothing to trim: linear memory cannot shrink, + // so retaining every freed item for reuse is always the + // right policy on wasm. As with deinit, live items must be + // destroyed by the caller first. + _ = self; + _ = mode; + return true; + } + + pub fn create(self: *Self) Allocator.Error!ItemPtr { + _ = self; + + // If we have a free item, use it. + if (free_list.popFirst()) |node| return @ptrCast(@alignCast(node)); + + // Grow linear memory by exactly one item. + const pages = comptime item_size / std.heap.page_size_min; + const page_index = @wasmMemoryGrow(0, pages); + if (page_index == -1) return error.OutOfMemory; + return @ptrFromInt(@as(usize, @intCast(page_index)) * std.heap.page_size_min); + } + + pub fn destroy(self: *Self, ptr: ItemPtr) void { + _ = self; + const node: *std.SinglyLinkedList.Node = @ptrCast(ptr); + node.* = .{}; + free_list.prepend(node); + } + }; +} + +test WasmPagePool { + if (!comptime builtin.target.cpu.arch.isWasm()) return error.SkipZigTest; + + const testing = std.testing; + const Pool = WasmPagePool([64 * 1024]u8); + var pool: Pool = try .initCapacity(testing.allocator, testing.allocator, 0); + defer pool.deinit(); + + const a = try pool.create(); + const b = try pool.create(); + try testing.expect(a != b); + + // Freed items are recycled, most recent first. + pool.destroy(b); + try testing.expectEqual(b, try pool.create()); + + // The free list is shared across pools of the same Item type. + var pool2: Pool = try .initCapacity(testing.allocator, testing.allocator, 0); + defer pool2.deinit(); + pool.destroy(a); + try testing.expectEqual(a, try pool2.create()); + + pool.destroy(a); + pool.destroy(b); +} |
