const std = @import("std");

const builtin = @import("builtin");

const build_options = @import("terminal_options");

const Allocator = std.mem.Allocator;

const ArenaAllocator = std.heap.ArenaAllocator;

const assert = @import("../quirks.zig").inlineAssert;

const testing = std.testing;

const posix = std.posix;

const windows = std.os.windows;

const fastmem = @import("../fastmem.zig");

const color = @import("color.zig");

const hyperlink = @import("hyperlink.zig");

const kitty = @import("kitty.zig");

const stylepkg = @import("style.zig");

const Style = stylepkg.Style;

const StyleId = stylepkg.Id;

const StyleSet = stylepkg.Set;

const size = @import("size.zig");

const getOffset = size.getOffset;

const Offset = size.Offset;

const OffsetBuf = size.OffsetBuf;

const BitmapAllocator = @import("bitmap_allocator.zig").BitmapAllocator;

const hash_map = @import("hash_map.zig");

const AutoOffsetHashMap = hash_map.AutoOffsetHashMap;

const alignForward = std.mem.alignForward;

const alignBackward = std.mem.alignBackward;

const log = std.log.scoped(.page);

/// Page-aligned allocator used for terminal page backing memory. Pages

/// require page-aligned, zeroed memory obtained directly from the OS

/// (not the Zig allocator) because the allocation fast-path is

/// performance-critical and the OS guarantees zeroed pages.

const PageAlloc = switch (builtin.os.tag) {

.windows => AllocWindows,

else => AllocPosix,

};

/// Allocate page-aligned, zeroed backing memory using mmap with

/// MAP_PRIVATE | MAP_ANONYMOUS which guarantees zeroed pages.

const AllocPosix = struct {

pub fn alloc(n: usize) ![]align(std.heap.page_size_min) u8 {

return try posix.mmap(

null,

n,

posix.PROT.READ | posix.PROT.WRITE,

.{ .TYPE = .PRIVATE, .ANONYMOUS = true },

-1,

0,

);

}

pub fn free(mem: []align(std.heap.page_size_min) u8) void {

posix.munmap(mem);

}

};

/// Allocate page-aligned, zeroed backing memory using VirtualAlloc with

/// MEM_COMMIT | MEM_RESERVE which guarantees zeroed pages.

const AllocWindows = struct {

pub fn alloc(n: usize) error{OutOfMemory}![]align(std.heap.page_size_min) u8 {

const addr = windows.VirtualAlloc(

null,

n,

windows.MEM_COMMIT | windows.MEM_RESERVE,

windows.PAGE_READWRITE,

) catch return error.OutOfMemory;

return @as(

[*]align(std.heap.page_size_min) u8,

@ptrCast(@alignCast(addr)),

)[0..n];

}

pub fn free(mem: []align(std.heap.page_size_min) u8) void {

windows.VirtualFree(

@ptrCast(@alignCast(mem.ptr)),

0,

windows.MEM_RELEASE,

);

}

};

/// The allocator to use for multi-codepoint grapheme data. We use

/// a chunk size of 4 codepoints. It'd be best to set this empirically

/// but it is currently set based on vibes. My thinking around 4 codepoints

/// is that most skin-tone emoji are <= 4 codepoints, letter combiners

/// are usually <= 4 codepoints, and 4 codepoints is a nice power of two

/// for alignment.

const grapheme_chunk_len = 4;

const grapheme_chunk = grapheme_chunk_len * @sizeOf(u21);

const GraphemeAlloc = BitmapAllocator(grapheme_chunk);

const grapheme_count_default = GraphemeAlloc.bitmap_bit_size;

pub const grapheme_bytes_default = grapheme_count_default * grapheme_chunk;

const GraphemeMap = AutoOffsetHashMap(Offset(Cell), Offset(u21).Slice);

/// The allocator used for shared utf8-encoded strings within a page.

/// Note the chunk size below is the minimum size of a single allocation

/// and requires a single bit of metadata in our bitmap allocator. Therefore

/// it should be tuned carefully (too small and we waste metadata, too large

/// and we have fragmentation). We can probably use a better allocation

/// strategy in the future.

///

/// At the time of writing this, the strings table is only used for OSC8

/// IDs and URIs. IDs are usually short and URIs are usually longer. I chose

/// 32 bytes as a compromise between these two since it represents single

/// domain links quite well and is not too wasteful for short IDs. We can

/// continue to tune this as we see how it's used.

const string_chunk_len = 32;

const string_chunk = string_chunk_len * @sizeOf(u8);

const StringAlloc = BitmapAllocator(string_chunk);

const string_count_default = StringAlloc.bitmap_bit_size;

pub const string_bytes_default = string_count_default * string_chunk;

/// Default number of hyperlinks we support.

///

/// The cell multiplier is the number of cells per hyperlink entry that

/// we support. A hyperlink can be longer than this multiplier; the multiplier

/// just sets the total capacity to simplify adjustable size metrics.

const hyperlink_count_default = 4;

const hyperlink_bytes_default = hyperlink_count_default * @sizeOf(hyperlink.Set.Item);

const hyperlink_cell_multiplier = 16;

/// A page represents a specific section of terminal screen. The primary

/// idea of a page is that it is a fully self-contained unit that can be

/// serialized, copied, etc. as a convenient way to represent a section

/// of the screen.

///

/// This property is useful for renderers which want to copy just the pages

/// for the visible portion of the screen, or for infinite scrollback where

/// we may want to serialize and store pages that are sufficiently far

/// away from the current viewport.

///

/// Pages are always backed by a single contiguous block of memory that is

/// aligned on a page boundary. This makes it easy and fast to copy pages

/// around. Within the contiguous block of memory, the contents of a page are

/// thoughtfully laid out to optimize primarily for terminal IO (VT streams)

/// and to minimize memory usage.

pub const Page = struct {

comptime {

// The alignment of our members. We want to ensure that the page

// alignment is always divisible by this.

assert(std.heap.page_size_min % @max(

@alignOf(Row),

@alignOf(Cell),

StyleSet.base_align.toByteUnits(),

) == 0);

}

/// The backing memory for the page. A page is always made up of a

/// a single contiguous block of memory that is aligned on a page

/// boundary and is a multiple of the system page size.

memory: []align(std.heap.page_size_min) u8,

/// The array of rows in the page. The rows are always in row order

/// (i.e. index 0 is the top row, index 1 is the row below that, etc.)

rows: Offset(Row),

/// The array of cells in the page. The cells are NOT in row order,

/// but they are in column order. To determine the mapping of cells

/// to row, you must use the `rows` field. From the pointer to the

/// first column, all cells in that row are laid out in column order.

cells: Offset(Cell),

/// Set to true when an operation is performed that dirties all rows in

/// the page. See `Row.dirty` for more information on dirty tracking.

///

/// NOTE: A value of false does NOT indicate that

/// the page has no dirty rows in it, only

/// that no full-page-dirtying operations

/// have occurred since it was last cleared.

dirty: bool,

/// The string allocator for this page used for shared utf-8 encoded

/// strings. Liveness of strings and memory management is deferred to

/// the individual use case.

string_alloc: StringAlloc,

/// The multi-codepoint grapheme data for this page. This is where

/// any cell that has more than one codepoint will be stored. This is

/// relatively rare (typically only emoji) so this defaults to a very small

/// size and we force page realloc when it grows.

grapheme_alloc: GraphemeAlloc,

/// The mapping of cell to grapheme data. The exact mapping is the

/// cell offset to the grapheme data offset. Therefore, whenever a

/// cell is moved (i.e. `erase`) then the grapheme data must be updated.

/// Grapheme data is relatively rare so this is considered a slow

/// path.

grapheme_map: GraphemeMap,

/// The available set of styles in use on this page.

styles: StyleSet,

/// The structures used for tracking hyperlinks within the page.

/// The map maps cell offsets to hyperlink IDs and the IDs are in

/// the ref counted set. The strings within the hyperlink structures

/// are allocated in the string allocator.

hyperlink_map: hyperlink.Map,

hyperlink_set: hyperlink.Set,

/// The current dimensions of the page. The capacity may be larger

/// than this. This allows us to allocate a larger page than necessary

/// and also to resize a page smaller without reallocating.

size: Size,

/// The capacity of this page. This is the full size of the backing

/// memory and is fixed at page creation time.

capacity: Capacity,

/// If this is true then verifyIntegrity will do nothing. This is

/// only present with runtime safety enabled.

pause_integrity_checks: if (build_options.slow_runtime_safety) usize else void =

if (build_options.slow_runtime_safety) 0 else {},

/// Initialize a new page, allocating the required backing memory.

/// The size of the initialized page defaults to the full capacity.

///

/// The backing memory is always allocated using mmap directly.

/// You cannot use custom allocators with this structure because

/// it is critical to performance that we use mmap.

pub inline fn init(cap: Capacity) !Page {

const l = layout(cap);

// We allocate page-aligned zeroed memory directly to avoid Zig

// allocator overhead (small but meaningful for this path). Both

// mmap (POSIX) and VirtualAlloc (Windows) guarantee zeroed pages,

// which is a critical property for us.

assert(l.total_size % std.heap.page_size_min == 0);

const backing = try PageAlloc.alloc(l.total_size);

errdefer PageAlloc.free(backing);

const buf = OffsetBuf.init(backing);

return initBuf(buf, l);

}

/// Initialize a new page using the given backing memory.

/// It is up to the caller to not call deinit on these pages.

pub inline fn initBuf(buf: OffsetBuf, l: Layout) Page {

const cap = l.capacity;

const rows = buf.member(Row, l.rows_start);

const cells = buf.member(Cell, l.cells_start);

// We need to go through and initialize all the rows so that

// they point to a valid offset into the cells, since the rows

// zero-initialized aren't valid.

const cells_len = @as(usize, cap.cols) * @as(usize, cap.rows);

const cells_ptr = cells.ptr(buf)[0..cells_len];

for (rows.ptr(buf)[0..cap.rows], 0..) |*row, y| {

const start = y * cap.cols;

row.* = .{

.cells = getOffset(Cell, buf, &cells_ptr[start]),

};

}

return .{

.memory = @alignCast(buf.start()[0..l.total_size]),

.rows = rows,

.cells = cells,

.styles = StyleSet.init(

buf.add(l.styles_start),

l.styles_layout,

.{},

),

.string_alloc = .init(

buf.add(l.string_alloc_start),

l.string_alloc_layout,

),

.grapheme_alloc = .init(

buf.add(l.grapheme_alloc_start),

l.grapheme_alloc_layout,

),

.grapheme_map = .init(

buf.add(l.grapheme_map_start),

l.grapheme_map_layout,

),

.hyperlink_map = .init(

buf.add(l.hyperlink_map_start),

l.hyperlink_map_layout,

),

.hyperlink_set = .init(

buf.add(l.hyperlink_set_start),

l.hyperlink_set_layout,

.{},

),

.size = .{ .cols = cap.cols, .rows = cap.rows },

.capacity = cap,

.dirty = false,

};

}

/// Deinitialize the page, freeing any backing memory. Do NOT call

/// this if you allocated the backing memory yourself (i.e. you used

/// initBuf).

pub inline fn deinit(self: *Page) void {

PageAlloc.free(self.memory);

self.* = undefined;

}

/// Reinitialize the page with the same capacity.

pub inline fn reinit(self: *Page) void {

// We zero the page memory as u64 instead of u8 because

// we can and it's empirically quite a bit faster.

@memset(@as([*]u64, @ptrCast(self.memory))[0 .. self.memory.len / 8], 0);

self.* = initBuf(.init(self.memory), layout(self.capacity));

}

pub const IntegrityError = error{

ZeroRowCount,

ZeroColCount,

UnmarkedGraphemeRow,

MissingGraphemeData,

InvalidGraphemeCount,

UnmarkedGraphemeCell,

MissingStyle,

UnmarkedStyleRow,

MismatchedStyleRef,

InvalidStyleCount,

MissingHyperlinkData,

MismatchedHyperlinkRef,

UnmarkedHyperlinkCell,

UnmarkedHyperlinkRow,

InvalidSpacerTailLocation,

InvalidSpacerHeadLocation,

UnwrappedSpacerHead,

};

/// Temporarily pause integrity checks. This is useful when you are

/// doing a lot of operations that would trigger integrity check

/// violations but you know the page will end up in a consistent state.

pub inline fn pauseIntegrityChecks(self: *Page, v: bool) void {

if (build_options.slow_runtime_safety) {

if (v) {

self.pause_integrity_checks += 1;

} else {

self.pause_integrity_checks -= 1;

}

}

}

/// A helper that can be used to assert the integrity of the page

/// when runtime safety is enabled. This is a no-op when runtime

/// safety is disabled. This uses the libc allocator.

pub inline fn assertIntegrity(self: *const Page) void {

if (comptime build_options.slow_runtime_safety) {

var debug_allocator: std.heap.DebugAllocator(.{}) = .init;

defer _ = debug_allocator.deinit();

const alloc = debug_allocator.allocator();

self.verifyIntegrity(alloc) catch |err| {

log.err("page integrity violation, crashing. err={}", .{err});

@panic("page integrity violation");

};

}

}

/// Verifies the integrity of the page data. This is not fast,

/// but it is useful for assertions, deserialization, etc. The

/// allocator is only used for temporary allocations -- all memory

/// is freed before this function returns.

///

/// Integrity errors are also logged as warnings.

pub fn verifyIntegrity(self: *const Page, alloc_gpa: Allocator) !void {

// Some things that seem like we should check but do not:

//

// - We do not check that the style ref count is exact, only that

// it is at least what we see. We do this because some fast paths

// trim rows without clearing data.

// - We do not check that styles seen is exactly the same as the

// styles count in the page for the same reason as above.

// - We only check that we saw less graphemes than the total memory

// used for the same reason as styles above.

//

// We don't run integrity checks on Valgrind because its soooooo slow,

// Valgrind is our integrity checker, and we run these during unit

// tests (non-Valgrind) anyways so we're verifying anyways.

if (std.valgrind.runningOnValgrind() > 0) return;

if (build_options.slow_runtime_safety) {

if (self.pause_integrity_checks > 0) return;

}

if (self.size.rows == 0) {

log.warn("page integrity violation zero row count", .{});

return IntegrityError.ZeroRowCount;

}

if (self.size.cols == 0) {

log.warn("page integrity violation zero col count", .{});

return IntegrityError.ZeroColCount;

}

var arena = ArenaAllocator.init(alloc_gpa);

defer arena.deinit();

const alloc = arena.allocator();

var graphemes_seen: usize = 0;

var styles_seen = std.AutoHashMap(StyleId, usize).init(alloc);

defer styles_seen.deinit();

var hyperlinks_seen = std.AutoHashMap(hyperlink.Id, usize).init(alloc);

defer hyperlinks_seen.deinit();

const grapheme_count = self.graphemeCount();

const rows = self.rows.ptr(self.memory)[0..self.size.rows];

for (rows, 0..) |*row, y| {

const graphemes_start = graphemes_seen;

const cells = row.cells.ptr(self.memory)[0..self.size.cols];

for (cells, 0..) |*cell, x| {

if (cell.hasGrapheme()) {

// If a cell has grapheme data, it must be present in

// the grapheme map.

_ = self.lookupGrapheme(cell) orelse {

log.warn(

"page integrity violation y={} x={} grapheme data missing",

.{ y, x },

);

return IntegrityError.MissingGraphemeData;

};

graphemes_seen += 1;

} else if (grapheme_count > 0) {

// It should not have grapheme data if it isn't marked.

// The grapheme_count check above is just an optimization

// to speed up integrity checks.

if (self.lookupGrapheme(cell) != null) {

log.warn(

"page integrity violation y={} x={} cell not marked as grapheme",

.{ y, x },

);

return IntegrityError.UnmarkedGraphemeCell;

}

}

if (cell.style_id != stylepkg.default_id) {

// If a cell has a style, it must be present in the styles

// set. Accessing it with `get` asserts that.

_ = self.styles.get(

self.memory,

cell.style_id,

);

if (!row.styled) {

log.warn(

"page integrity violation y={} x={} row not marked as styled",

.{ y, x },

);

return IntegrityError.UnmarkedStyleRow;

}

const gop = try styles_seen.getOrPut(cell.style_id);

if (!gop.found_existing) gop.value_ptr.* = 0;

gop.value_ptr.* += 1;

}

if (cell.hyperlink) {

const id = self.lookupHyperlink(cell) orelse {

log.warn(

"page integrity violation y={} x={} hyperlink data missing",

.{ y, x },

);

return IntegrityError.MissingHyperlinkData;

};

if (!row.hyperlink) {

log.warn(

"page integrity violation y={} x={} row not marked as hyperlink",

.{ y, x },

);

return IntegrityError.UnmarkedHyperlinkRow;

}

const gop = try hyperlinks_seen.getOrPut(id);

if (!gop.found_existing) gop.value_ptr.* = 0;

gop.value_ptr.* += 1;

// Hyperlink ID should be valid. This just straight crashes

// if this fails due to assertions.

_ = self.hyperlink_set.get(self.memory, id);

} else {

// It should not have hyperlink data if it isn't marked

if (self.lookupHyperlink(cell) != null) {

log.warn(

"page integrity violation y={} x={} cell not marked as hyperlink",

.{ y, x },

);

return IntegrityError.UnmarkedHyperlinkCell;

}

}

switch (cell.wide) {

.narrow => {},

.wide => {},

.spacer_tail => {

// Spacer tails can't be at the start because they follow

// a wide char.

if (x == 0) {

log.warn(

"page integrity violation y={} x={} spacer tail at start",

.{ y, x },

);

return IntegrityError.InvalidSpacerTailLocation;

}

// Spacer tails must follow a wide char

const prev = cells[x - 1];

if (prev.wide != .wide) {

log.warn(

"page integrity violation y={} x={} spacer tail not following wide",

.{ y, x },

);

return IntegrityError.InvalidSpacerTailLocation;

}

},

.spacer_head => {

// Spacer heads must be at the end

if (x != self.size.cols - 1) {

log.warn(

"page integrity violation y={} x={} spacer head not at end",

.{ y, x },

);

return IntegrityError.InvalidSpacerHeadLocation;

}

// The row must be wrapped

if (!row.wrap) {

log.warn(

"page integrity violation y={} spacer head not wrapped",

.{y},

);

return IntegrityError.UnwrappedSpacerHead;

}

},

}

}

// Check row grapheme data

if (graphemes_seen > graphemes_start) {

// If a cell in a row has grapheme data, the row must

// be marked as having grapheme data.

if (!row.grapheme) {

log.warn(

"page integrity violation y={} grapheme data but row not marked",

.{y},

);

return IntegrityError.UnmarkedGraphemeRow;

}

}

}

// Our graphemes seen should exactly match the grapheme count

if (graphemes_seen > self.graphemeCount()) {

log.warn(

"page integrity violation grapheme count mismatch expected={} actual={}",

.{ graphemes_seen, self.graphemeCount() },

);

return IntegrityError.InvalidGraphemeCount;

}

// Verify all our styles have the correct ref count.

{

var it = styles_seen.iterator();

while (it.next()) |entry| {

const ref_count = self.styles.refCount(self.memory, entry.key_ptr.*);

if (ref_count < entry.value_ptr.*) {

log.warn(

"page integrity violation style ref count mismatch id={} expected={} actual={}",

.{ entry.key_ptr.*, entry.value_ptr.*, ref_count },

);

return IntegrityError.MismatchedStyleRef;

}

}

}

// Verify all our hyperlinks have the correct ref count.

{

var it = hyperlinks_seen.iterator();

while (it.next()) |entry| {

const ref_count = self.hyperlink_set.refCount(self.memory, entry.key_ptr.*);

if (ref_count < entry.value_ptr.*) {

log.warn(

"page integrity violation hyperlink ref count mismatch id={} expected={} actual={}",

.{ entry.key_ptr.*, entry.value_ptr.*, ref_count },

);

return IntegrityError.MismatchedHyperlinkRef;

}

}

}

// Verify there are no zombie styles, that is, styles in the

// set with ref counts > 0, which are not present in the page.

{

const styles_table = self.styles.table.ptr(self.memory)[0..self.styles.layout.table_cap];

const styles_items = self.styles.items.ptr(self.memory)[0..self.styles.layout.cap];

var zombies: usize = 0;

for (styles_table) |id| {

if (id == 0) continue;

const item = styles_items[id];

if (item.meta.ref == 0) continue;

const expected = styles_seen.get(id) orelse 0;

if (expected > 0) continue;

if (item.meta.ref > expected) {

zombies += 1;

}

}

// NOTE: This is currently disabled because @qwerasd says that

// certain fast paths can cause this but its okay.

// Just 1 zombie style might be the cursor style, so ignore it.

// if (zombies > 1) {

// log.warn(

// "page integrity violation zombie styles count={}",

// .{zombies},

// );

// return IntegrityError.ZombieStyles;

// }

}

}

/// Clone the contents of this page. This will allocate new memory

/// using the page allocator. If you want to manage memory manually,

/// use cloneBuf.

pub inline fn clone(self: *const Page) !Page {

const backing = try PageAlloc.alloc(self.memory.len);

errdefer PageAlloc.free(backing);

return self.cloneBuf(backing);

}

/// Clone the entire contents of this page.

///

/// The buffer must be at least the size of self.memory.

pub inline fn cloneBuf(self: *const Page, buf: []align(std.heap.page_size_min) u8) Page {

assert(buf.len >= self.memory.len);

// The entire concept behind a page is that everything is stored

// as offsets so we can do a simple linear copy of the backing

// memory and copy all the offsets and everything will work.

var result = self.*;

result.memory = buf[0..self.memory.len];

// This is a memcpy. We may want to investigate if there are

// faster ways to do this (i.e. copy-on-write tricks) but I suspect

// they'll be slower. I haven't experimented though.

// std.log.warn("copy bytes={}", .{self.memory.len});

fastmem.copy(u8, result.memory, self.memory);

return result;

}

pub const StyleSetError = error{

StyleSetOutOfMemory,

StyleSetNeedsRehash,

};

pub const HyperlinkError = error{

StringAllocOutOfMemory,

HyperlinkSetOutOfMemory,

HyperlinkSetNeedsRehash,

HyperlinkMapOutOfMemory,

};

pub const GraphemeError = error{

GraphemeMapOutOfMemory,

GraphemeAllocOutOfMemory,

};

pub const CloneFromError =

StyleSetError ||

HyperlinkError ||

GraphemeError;

/// Compute the exact capacity required to store a range of rows from

/// this page.

///

/// The returned capacity will have the same number of columns as this

/// page and the number of rows equal to the range given. The returned

/// capacity is by definition strictly less than or equal to this

/// page's capacity, so the layout is guaranteed to succeed.

///

/// Preconditions:

/// - Range must be at least 1 row

/// - Start and end must be valid for this page

pub fn exactRowCapacity(

self: *const Page,

y_start: usize,

y_end: usize,

) Capacity {

assert(y_start < y_end);

assert(y_end <= self.size.rows);

// Track unique IDs using a bitset. Both style IDs and hyperlink IDs

// are CellCountInt (u16), so we reuse this set for both to save

// stack memory (~8KB instead of ~16KB).

const CellCountSet = std.StaticBitSet(std.math.maxInt(size.CellCountInt) + 1);

comptime assert(size.StyleCountInt == size.CellCountInt);

comptime assert(size.HyperlinkCountInt == size.CellCountInt);

// Accumulators

var id_set: CellCountSet = .initEmpty();

var grapheme_bytes: usize = 0;

var string_bytes: usize = 0;

// First pass: count styles and grapheme bytes

const rows = self.rows.ptr(self.memory)[y_start..y_end];

for (rows) |*row| {

const cells = row.cells.ptr(self.memory)[0..self.size.cols];

for (cells) |*cell| {

if (cell.style_id != stylepkg.default_id) {

id_set.set(cell.style_id);

}

if (cell.hasGrapheme()) {

if (self.lookupGrapheme(cell)) |cps| {

grapheme_bytes += GraphemeAlloc.bytesRequired(u21, cps.len);

}

}

}

}

const styles_cap = StyleSet.capacityForCount(id_set.count());

// Second pass: count hyperlinks and string bytes

// We count both unique hyperlinks (for hyperlink_set) and total

// hyperlink cells (for hyperlink_map capacity).

id_set = .initEmpty();

var hyperlink_cells: usize = 0;

for (rows) |*row| {

const cells = row.cells.ptr(self.memory)[0..self.size.cols];

for (cells) |*cell| {

if (cell.hyperlink) {

hyperlink_cells += 1;

if (self.lookupHyperlink(cell)) |id| {

// Only count each unique hyperlink once for set sizing

if (!id_set.isSet(id)) {

id_set.set(id);

// Get the hyperlink entry to compute string bytes

const entry = self.hyperlink_set.get(self.memory, id);

string_bytes += StringAlloc.bytesRequired(u8, entry.uri.len);

switch (entry.id) {

.implicit => {},

.explicit => |slice| {

string_bytes += StringAlloc.bytesRequired(u8, slice.len);

},

}

}

}

}

}

}

// The hyperlink_map capacity in layout() is computed as:

// hyperlink_count * hyperlink_cell_multiplier (rounded to power of 2)

// We need enough hyperlink_bytes so that when layout() computes

// the map capacity, it can accommodate all hyperlink cells. This

// is unit tested.

const hyperlink_cap = cap: {

const hyperlink_count = id_set.count();

const hyperlink_set_cap = hyperlink.Set.capacityForCount(hyperlink_count);

const hyperlink_map_min = std.math.divCeil(

usize,

hyperlink_cells,

hyperlink_cell_multiplier,

) catch 0;

break :cap @max(hyperlink_set_cap, hyperlink_map_min);

};

// All the intCasts below are safe because we should have a

// capacity strictly less than or equal to this page's capacity.

return .{

.cols = self.size.cols,

.rows = @intCast(y_end - y_start),

.styles = @intCast(styles_cap),

.grapheme_bytes = @intCast(grapheme_bytes),

.hyperlink_bytes = @intCast(hyperlink_cap * @sizeOf(hyperlink.Set.Item)),

.string_bytes = @intCast(string_bytes),

};

}

/// Clone the contents of another page into this page. The capacities

/// can be different, but the size of the other page must fit into

/// this page.

///

/// The y_start and y_end parameters allow you to clone only a portion

/// of the other page. This is useful for splitting a page into two

/// or more pages.

///

/// The column count of this page will always be the same as this page.

/// If the other page has more columns, the extra columns will be

/// truncated. If the other page has fewer columns, the extra columns

/// will be zeroed.

pub inline fn cloneFrom(

self: *Page,

other: *const Page,

y_start: usize,

y_end: usize,

) CloneFromError!void {

assert(y_start <= y_end);

assert(y_end <= other.size.rows);

assert(y_end - y_start <= self.size.rows);

const other_rows = other.rows.ptr(other.memory)[y_start..y_end];

const rows = self.rows.ptr(self.memory)[0 .. y_end - y_start];

for (rows, other_rows) |*dst_row, *src_row| {

try self.cloneRowFrom(other, dst_row, src_row);

}

// We should remain consistent

self.assertIntegrity();

}

/// Clone a single row from another page into this page.

pub inline fn cloneRowFrom(

self: *Page,

other: *const Page,

dst_row: *Row,

src_row: *const Row,

) CloneFromError!void {

try self.clonePartialRowFrom(

other,

dst_row,

src_row,

0,

self.size.cols,

);

}

/// Clone a single row from another page into this page, supporting

/// partial copy. cloneRowFrom calls this.

pub fn clonePartialRowFrom(

self: *Page,

other: *const Page,

dst_row: *Row,

src_row: *const Row,

x_start: usize,

x_end_req: usize,

) CloneFromError!void {

// This whole operation breaks integrity until the end.

self.pauseIntegrityChecks(true);

defer {

self.pauseIntegrityChecks(false);

self.assertIntegrity();

}

const cell_len = @min(self.size.cols, other.size.cols);

const x_end = @min(x_end_req, cell_len);

assert(x_start <= x_end);

const other_cells = src_row.cells.ptr(other.memory)[x_start..x_end];

const cells = dst_row.cells.ptr(self.memory)[x_start..x_end];

// If our destination has styles or graphemes then we need to

// clear some state. This will free up the managed memory as well.

if (dst_row.managedMemory()) self.clearCells(dst_row, x_start, x_end);

// Copy all the row metadata but keep our cells offset

dst_row.* = copy: {

var copy = src_row.*;

// If we're not copying the full row then we want to preserve

// some original state from our dst row.

if ((x_end - x_start) < self.size.cols) {

copy.wrap = dst_row.wrap;

copy.wrap_continuation = dst_row.wrap_continuation;

copy.grapheme = dst_row.grapheme;

copy.hyperlink = dst_row.hyperlink;

copy.styled = dst_row.styled;

copy.dirty |= dst_row.dirty;

}

// Our cell offset remains the same

copy.cells = dst_row.cells;

break :copy copy;

};

// If we have no managed memory in the source, then we can just

// copy it directly.

if (!src_row.managedMemory()) {

// This is an integrity check: if the row claims it doesn't

// have managed memory then all cells must also not have

// managed memory.

if (build_options.slow_runtime_safety) {

for (other_cells) |cell| {

assert(!cell.hasGrapheme());

assert(!cell.hyperlink);

assert(cell.style_id == stylepkg.default_id);

}

}

fastmem.copy(Cell, cells, other_cells);

} else {

// We have managed memory, so we have to do a slower copy to

// get all of that right.

for (cells, other_cells) |*dst_cell, *src_cell| {

dst_cell.* = src_cell.*;

// Reset any managed memory markers on the cell so that we don't

// hit an integrity check if we have to return an error because

// the page can't fit the new memory.

dst_cell.hyperlink = false;

dst_cell.style_id = stylepkg.default_id;

if (dst_cell.content_tag == .codepoint_grapheme) {

dst_cell.content_tag = .codepoint;

}

if (src_cell.hasGrapheme()) {

// Copy the grapheme codepoints

const cps = other.lookupGrapheme(src_cell).?;

// Safe to use setGraphemes because we cleared all

// managed memory for our destination cell range.

try self.setGraphemes(dst_row, dst_cell, cps);

}

if (src_cell.hyperlink) hyperlink: {

const id = other.lookupHyperlink(src_cell).?;

// Fast-path: same page we can add with the same id.

if (other == self) {

self.hyperlink_set.use(self.memory, id);

try self.setHyperlink(dst_row, dst_cell, id);

break :hyperlink;

}

// Slow-path: get the hyperlink from the other page,

// add it, and migrate.

// If our page can't support an additional cell with

// a hyperlink then we have to return an error.

if (self.hyperlinkCount() >= self.hyperlinkCapacity()) {

// The hyperlink map capacity needs to be increased.

return error.HyperlinkMapOutOfMemory;

}

const other_link = other.hyperlink_set.get(other.memory, id);

const dst_id = dst_id: {

// First check if the link already exists in our page,

// and increment its refcount if so, since we're about

// to use it.

if (self.hyperlink_set.lookupContext(

self.memory,

other_link.*,

.{ .page = self, .src_page = @constCast(other) },

)) |i| {

self.hyperlink_set.use(self.memory, i);

break :dst_id i;

}

// If we don't have this link in our page yet then

// we need to clone it over and add it to our set.

// Clone the link.

const dst_link = other_link.dupe(other, self) catch |e| {

comptime assert(@TypeOf(e) == error{OutOfMemory});

// The string alloc capacity needs to be increased.

return error.StringAllocOutOfMemory;

};

// Add it, preferring to use the same ID as the other

// page, since this *probably* speeds up full-page

// clones.

//

// TODO(qwerasd): verify the assumption that `addWithId`

// is ever actually useful, I think it may not be.

break :dst_id self.hyperlink_set.addWithIdContext(

self.memory,

dst_link,

id,

.{ .page = self },

) catch |e| switch (e) {

// The hyperlink set capacity needs to be increased.

error.OutOfMemory => return error.HyperlinkSetOutOfMemory,

// The hyperlink set needs to be rehashed.

error.NeedsRehash => return error.HyperlinkSetNeedsRehash,

} orelse id;

};

try self.setHyperlink(dst_row, dst_cell, dst_id);

}

if (src_cell.style_id != stylepkg.default_id) style: {

dst_row.styled = true;

if (other == self) {

// If it's the same page we don't have to worry about

// copying the style, we can use the style ID directly.

dst_cell.style_id = src_cell.style_id;

self.styles.use(self.memory, dst_cell.style_id);

break :style;

}

// Slow path: Get the style from the other

// page and add it to this page's style set.

const other_style = other.styles.get(other.memory, src_cell.style_id);

dst_cell.style_id = self.styles.addWithId(

self.memory,