Current section
Files
Jump to
Current section
Files
zig/opentui/rope.zig
const std = @import("std");
const Allocator = std.mem.Allocator;
/// This is a persistent/immutable rope - operations create new nodes without
/// freeing old ones. Use an ArenaAllocator to avoid manual memory management:
///
/// var arena = std.heap.ArenaAllocator.init(allocator);
/// defer arena.deinit();
/// var rope = try Rope(T).init(arena.allocator());
///
/// TODO: Needs a startTransaction and endTransaction to track changes
/// -> used to trigger a change event _after_ a batch of changes is complete (group as operation)
/// -> used to group history operations (undo/redo), so not everything is a single history entry
///
pub fn Rope(comptime T: type) type {
return struct {
const Self = @This();
pub const max_imbalance = 7;
pub const Config = struct {
max_undo_depth: ?usize = null, // null = unlimited
};
const marker_enabled = @typeInfo(T) == .@"union" and @hasDecl(T, "MarkerTypes");
const MarkerTagCount = if (marker_enabled) T.MarkerTypes.len else 0;
const boundary_enabled = @hasDecl(T, "BoundaryAction");
pub const BoundaryAction = if (boundary_enabled) T.BoundaryAction else struct {
delete_left: bool = false,
delete_right: bool = false,
insert_between: []const T = &[_]T{},
};
pub const MarkerPosition = struct {
leaf_index: u32,
global_weight: u32,
};
pub const MarkerCache = if (marker_enabled) struct {
// Flat arrays of positions for each marker type
positions: std.AutoHashMap(std.meta.Tag(T), std.ArrayListUnmanaged(MarkerPosition)),
version: u64, // Rope version when cache was built
allocator: Allocator,
pub fn init(allocator: Allocator) MarkerCache {
return .{
.positions = std.AutoHashMap(std.meta.Tag(T), std.ArrayListUnmanaged(MarkerPosition)).init(allocator),
.version = std.math.maxInt(u64), // Sentinel: cache is invalid until first rebuild
.allocator = allocator,
};
}
pub fn deinit(self: *MarkerCache) void {
var iter = self.positions.valueIterator();
while (iter.next()) |list| {
list.deinit(self.allocator);
}
self.positions.deinit();
}
fn clear(self: *MarkerCache) void {
var iter = self.positions.valueIterator();
while (iter.next()) |list| {
list.clearRetainingCapacity();
}
}
} else struct {
pub fn init(_: Allocator) @This() {
return .{};
}
pub fn deinit(_: *@This()) void {}
fn clear(_: *@This()) void {}
};
pub const Metrics = struct {
count: u32 = 0,
depth: u32 = 1,
custom: if (@hasDecl(T, "Metrics")) T.Metrics else void = if (@hasDecl(T, "Metrics")) .{} else {},
marker_counts: if (marker_enabled) [MarkerTagCount]u32 else void = if (marker_enabled) [_]u32{0} ** MarkerTagCount else {},
pub fn add(self: *Metrics, other: Metrics) void {
self.count += other.count;
self.depth = @max(self.depth, other.depth);
if (@hasDecl(T, "Metrics")) {
if (@hasDecl(T.Metrics, "add")) {
self.custom.add(other.custom);
}
}
if (marker_enabled) {
inline for (&self.marker_counts, 0..) |*dst, i| {
dst.* += other.marker_counts[i];
}
}
}
pub fn weight(self: *const Metrics) u32 {
if (@hasDecl(T, "Metrics")) {
if (@hasDecl(T.Metrics, "weight")) {
return self.custom.weight();
}
}
return self.count;
}
};
pub const Branch = struct {
left: *const Node,
right: *const Node,
left_metrics: Metrics,
total_metrics: Metrics,
fn is_balanced(self: *const Branch) bool {
const left_weight = self.left.metrics().weight();
const right_weight = self.right.metrics().weight();
const total_weight = left_weight + right_weight;
if (total_weight == 0) return true;
const max_side = (total_weight * 3) / 4;
return left_weight <= max_side and right_weight <= max_side;
}
};
pub const Leaf = struct {
data: T,
is_sentinel: bool = false,
fn metrics(self: *const Leaf) Metrics {
var m = Metrics{
.count = if (self.is_sentinel) 0 else 1,
.depth = 1,
};
if (@hasDecl(T, "Metrics")) {
if (@hasDecl(T, "measure")) {
m.custom = self.data.measure();
}
}
if (!self.is_sentinel and marker_enabled) {
const tag = std.meta.activeTag(self.data);
inline for (T.MarkerTypes, 0..) |mt, i| {
if (tag == mt) {
m.marker_counts[i] = 1;
break;
}
}
}
return m;
}
};
pub const Node = union(enum) {
branch: Branch,
leaf: Leaf,
pub fn metrics(self: *const Node) Metrics {
return switch (self.*) {
.branch => |*b| b.total_metrics,
.leaf => |*l| l.metrics(),
};
}
pub fn depth(self: *const Node) u32 {
return self.metrics().depth;
}
pub fn count(self: *const Node) u32 {
return self.metrics().count;
}
pub fn is_balanced(self: *const Node) bool {
return switch (self.*) {
.branch => |*b| b.is_balanced(),
.leaf => true,
};
}
pub fn is_empty(self: *const Node) bool {
return switch (self.*) {
.branch => |*b| b.left.is_empty() and b.right.is_empty(),
.leaf => |*l| {
if (@hasDecl(T, "is_empty")) {
return l.data.is_empty();
}
return false;
},
};
}
pub fn is_sentinel(self: *const Node, empty_leaf: *const Node) bool {
return self == empty_leaf;
}
pub fn new_branch(allocator: Allocator, left: *const Node, right: *const Node) !*const Node {
const node = try allocator.create(Node);
errdefer allocator.destroy(node);
const left_metrics = left.metrics();
var total_metrics = Metrics{};
total_metrics.add(left_metrics);
total_metrics.add(right.metrics());
total_metrics.depth += 1;
node.* = .{ .branch = .{
.left = left,
.right = right,
.left_metrics = left_metrics,
.total_metrics = total_metrics,
} };
return node;
}
pub fn new_leaf(allocator: Allocator, data: T) !*const Node {
const node = try allocator.create(Node);
errdefer allocator.destroy(node);
node.* = .{ .leaf = .{ .data = data } };
return node;
}
pub fn get(self: *const Node, index: u32) ?*const T {
return switch (self.*) {
.branch => |*b| {
const left_count = b.left_metrics.count;
if (index < left_count) {
return b.left.get(index);
}
return b.right.get(index - left_count);
},
.leaf => |*l| if (index == 0) &l.data else null,
};
}
pub const WalkerFn = *const fn (ctx: *anyopaque, data: *const T, index: u32) WalkerResult;
pub const WalkerResult = struct {
keep_walking: bool = true,
err: ?anyerror = null,
};
pub fn walk(self: *const Node, ctx: *anyopaque, f: WalkerFn, current_index: *u32) WalkerResult {
return switch (self.*) {
.branch => |*b| {
const left_result = b.left.walk(ctx, f, current_index);
if (!left_result.keep_walking or left_result.err != null) {
return left_result;
}
return b.right.walk(ctx, f, current_index);
},
.leaf => |*l| {
const result = f(ctx, &l.data, current_index.*);
current_index.* += 1;
return result;
},
};
}
pub fn walk_from(self: *const Node, start_index: u32, ctx: *anyopaque, f: WalkerFn) WalkerResult {
var current_index: u32 = start_index;
return self.walk_from_internal(start_index, ctx, f, ¤t_index);
}
fn walk_from_internal(self: *const Node, start_index: u32, ctx: *anyopaque, f: WalkerFn, current_index: *u32) WalkerResult {
return switch (self.*) {
.branch => |*b| {
const left_count = b.left_metrics.count;
if (start_index >= left_count) {
return b.right.walk_from_internal(start_index - left_count, ctx, f, current_index);
}
const left_result = b.left.walk_from_internal(start_index, ctx, f, current_index);
if (!left_result.keep_walking or left_result.err != null) {
return left_result;
}
return b.right.walk(ctx, f, current_index);
},
.leaf => |*l| {
if (start_index == 0) {
const result = f(ctx, &l.data, current_index.*);
current_index.* += 1;
return result;
}
return .{};
},
};
}
fn collect(self: *const Node, list: *std.ArrayListUnmanaged(*const Node), allocator: Allocator) !void {
switch (self.*) {
.branch => |*b| {
try b.left.collect(list, allocator);
try b.right.collect(list, allocator);
},
.leaf => try list.append(allocator, self),
}
}
fn merge_leaves(leaves: []*const Node, allocator: Allocator) error{OutOfMemory}!*const Node {
const len = leaves.len;
if (len == 0) return error.OutOfMemory; // Should not happen
if (len == 1) return leaves[0];
if (len == 2) return try Node.new_branch(allocator, leaves[0], leaves[1]);
const mid = len / 2;
return try Node.new_branch(
allocator,
try merge_leaves(leaves[0..mid], allocator),
try merge_leaves(leaves[mid..], allocator),
);
}
pub fn rebalance(self: *const Node, allocator: Allocator, tmp_allocator: Allocator) !*const Node {
if (self.is_balanced()) return self;
var leaves: std.ArrayListUnmanaged(*const Node) = .{};
defer leaves.deinit(tmp_allocator);
try leaves.ensureTotalCapacity(tmp_allocator, self.count());
try self.collect(&leaves, tmp_allocator);
return try merge_leaves(leaves.items, allocator);
}
/// Structural split at index - returns (left, right) without flattening
pub fn split_at(node: *const Node, index: u32, allocator: Allocator, empty_leaf: *const Node) error{OutOfMemory}!struct { left: *const Node, right: *const Node } {
return switch (node.*) {
.leaf => {
if (index == 0) {
return .{ .left = empty_leaf, .right = node };
} else {
return .{ .left = node, .right = empty_leaf };
}
},
.branch => |*b| {
const left_count = b.left_metrics.count;
if (index < left_count) {
const result = try split_at(b.left, index, allocator, empty_leaf);
const new_right = try join_balanced(result.right, b.right, allocator);
return .{ .left = result.left, .right = new_right };
} else if (index > left_count) {
const result = try split_at(b.right, index - left_count, allocator, empty_leaf);
const new_left = try join_balanced(b.left, result.left, allocator);
return .{ .left = new_left, .right = result.right };
} else {
return .{ .left = b.left, .right = b.right };
}
},
};
}
pub fn join_balanced(left: *const Node, right: *const Node, allocator: Allocator) error{OutOfMemory}!*const Node {
const left_count = left.metrics().count;
const right_count = right.metrics().count;
if (left_count == 0) return right;
if (right_count == 0) return left;
const left_weight = left.metrics().weight();
const right_weight = right.metrics().weight();
const total_weight = left_weight + right_weight;
if (total_weight > 0) {
const max_side = (total_weight * 3) / 4;
if (left_weight <= max_side and right_weight <= max_side) {
return try new_branch(allocator, left, right);
}
}
if (left_weight > right_weight * 3) {
return switch (left.*) {
.leaf => try new_branch(allocator, left, right),
.branch => |*b| {
const new_right = try join_balanced(b.right, right, allocator);
return try new_branch(allocator, b.left, new_right);
},
};
}
return switch (right.*) {
.leaf => try new_branch(allocator, left, right),
.branch => |*b| {
const new_left = try join_balanced(left, b.left, allocator);
return try new_branch(allocator, new_left, b.right);
},
};
}
pub const LeafSplitResult = struct { left: T, right: T };
pub const LeafSplitFn = struct {
ctx: ?*anyopaque = null,
splitFn: *const fn (ctx: ?*anyopaque, allocator: Allocator, leaf: *const T, weight_in_leaf: u32) error{ OutOfBounds, OutOfMemory }!LeafSplitResult,
pub fn call(self: *const @This(), allocator: Allocator, leaf: *const T, weight: u32) error{ OutOfBounds, OutOfMemory }!LeafSplitResult {
return self.splitFn(self.ctx, allocator, leaf, weight);
}
};
pub fn split_at_weight(
node: *const Node,
target_weight: u32,
allocator: Allocator,
empty_leaf: *const Node,
split_leaf_fn: *const LeafSplitFn,
) error{ OutOfMemory, OutOfBounds }!struct { left: *const Node, right: *const Node } {
return switch (node.*) {
.leaf => |*l| {
const leaf_weight = node.metrics().weight();
if (target_weight == 0) {
return .{ .left = empty_leaf, .right = node };
} else if (target_weight >= leaf_weight) {
return .{ .left = node, .right = empty_leaf };
}
const split_result = try split_leaf_fn.call(allocator, &l.data, target_weight);
const left_node = try new_leaf(allocator, split_result.left);
const right_node = try new_leaf(allocator, split_result.right);
return .{ .left = left_node, .right = right_node };
},
.branch => |*b| {
const left_weight = b.left_metrics.weight();
if (target_weight < left_weight) {
const result = try split_at_weight(b.left, target_weight, allocator, empty_leaf, split_leaf_fn);
const new_right = try join_balanced(result.right, b.right, allocator);
return .{ .left = result.left, .right = new_right };
} else if (target_weight > left_weight) {
const result = try split_at_weight(b.right, target_weight - left_weight, allocator, empty_leaf, split_leaf_fn);
const new_left = try join_balanced(b.left, result.left, allocator);
return .{ .left = new_left, .right = result.right };
} else {
return .{ .left = b.left, .right = b.right };
}
},
};
}
};
pub const UndoNode = struct {
root: *const Node,
next: ?*UndoNode = null,
branches: ?*UndoBranch = null,
meta: []const u8,
};
pub const UndoBranch = struct {
redo: *UndoNode,
next: ?*UndoBranch,
};
root: *const Node,
allocator: Allocator,
empty_leaf: *const Node,
undo_history: ?*UndoNode = null,
redo_history: ?*UndoNode = null,
curr_history: ?*UndoNode = null,
config: Config = .{},
undo_depth: usize = 0,
version: u64 = 0,
marker_cache: MarkerCache,
pub fn init(allocator: Allocator) error{OutOfMemory}!Self {
return initWithConfig(allocator, .{});
}
pub fn initWithConfig(allocator: Allocator, config: Config) error{OutOfMemory}!Self {
const empty_data = if (@hasDecl(T, "empty"))
T.empty()
else
std.mem.zeroes(T);
const node = try allocator.create(Node);
node.* = .{ .leaf = .{ .data = empty_data, .is_sentinel = true } };
var self = Self{
.root = node,
.allocator = allocator,
.empty_leaf = node,
.config = config,
.marker_cache = MarkerCache.init(allocator),
};
try self.applyEndsInvariant();
return self;
}
pub fn from_item(allocator: Allocator, data: T) !Self {
return from_itemWithConfig(allocator, data, .{});
}
pub fn from_itemWithConfig(allocator: Allocator, data: T, config: Config) !Self {
const root = try Node.new_leaf(allocator, data);
const empty_data = if (@hasDecl(T, "empty"))
T.empty()
else
std.mem.zeroes(T);
const empty_node = try allocator.create(Node);
empty_node.* = .{ .leaf = .{ .data = empty_data, .is_sentinel = true } };
return .{
.root = root,
.allocator = allocator,
.empty_leaf = empty_node,
.config = config,
.marker_cache = MarkerCache.init(allocator),
};
}
pub fn from_slice(allocator: Allocator, items: []const T) !Self {
return from_sliceWithConfig(allocator, items, .{});
}
pub fn from_sliceWithConfig(allocator: Allocator, items: []const T, config: Config) !Self {
if (items.len == 0) {
return try initWithConfig(allocator, config);
}
var leaves: std.ArrayListUnmanaged(*const Node) = .{};
defer leaves.deinit(allocator);
try leaves.ensureTotalCapacity(allocator, items.len);
for (items) |item| {
const leaf = try Node.new_leaf(allocator, item);
try leaves.append(allocator, leaf);
}
const root = try Node.merge_leaves(leaves.items, allocator);
const empty_data = if (@hasDecl(T, "empty"))
T.empty()
else
std.mem.zeroes(T);
const empty_node = try allocator.create(Node);
empty_node.* = .{ .leaf = .{ .data = empty_data, .is_sentinel = true } };
return .{
.root = root,
.allocator = allocator,
.empty_leaf = empty_node,
.config = config,
.marker_cache = MarkerCache.init(allocator),
};
}
pub fn count(self: *const Self) u32 {
return self.root.count();
}
pub fn get(self: *const Self, index: u32) ?*const T {
return self.root.get(index);
}
pub fn walk(self: *const Self, ctx: *anyopaque, f: Node.WalkerFn) !void {
var index: u32 = 0;
const result = self.walkNode(self.root, ctx, f, &index);
if (result.err) |e| return e;
}
fn walkNode(self: *const Self, node: *const Node, ctx: *anyopaque, f: Node.WalkerFn, current_index: *u32) Node.WalkerResult {
return switch (node.*) {
.branch => |*b| {
const left_result = self.walkNode(b.left, ctx, f, current_index);
if (!left_result.keep_walking or left_result.err != null) {
return left_result;
}
return self.walkNode(b.right, ctx, f, current_index);
},
.leaf => |*l| {
if (node.count() == 0) {
return .{};
}
const result = f(ctx, &l.data, current_index.*);
current_index.* += 1;
return result;
},
};
}
pub fn walk_from(self: *const Self, start_index: u32, ctx: *anyopaque, f: Node.WalkerFn) !void {
var current_index: u32 = 0;
const result = self.walkFromNode(self.root, start_index, ctx, f, ¤t_index);
if (result.err) |e| return e;
}
fn walkFromNode(self: *const Self, node: *const Node, start_index: u32, ctx: *anyopaque, f: Node.WalkerFn, current_index: *u32) Node.WalkerResult {
return switch (node.*) {
.branch => |*b| {
const left_count = b.left_metrics.count;
if (start_index >= left_count) {
return self.walkFromNode(b.right, start_index - left_count, ctx, f, current_index);
}
const left_result = self.walkFromNode(b.left, start_index, ctx, f, current_index);
if (!left_result.keep_walking or left_result.err != null) {
return left_result;
}
return self.walkNode(b.right, ctx, f, current_index);
},
.leaf => |*l| {
if (node.count() == 0) {
return .{};
}
if (start_index == 0) {
const result = f(ctx, &l.data, current_index.*);
current_index.* += 1;
return result;
}
return .{};
},
};
}
pub fn rebalance(self: *Self, tmp_allocator: Allocator) !void {
self.root = try self.root.rebalance(self.allocator, tmp_allocator);
}
pub fn insert(self: *Self, index: u32, data: T) !void {
try self.insert_slice(index, &[_]T{data});
}
pub fn delete(self: *Self, index: u32) !void {
try self.delete_range(index, index + 1);
}
pub fn replace(self: *Self, index: u32, data: T) !void {
if (index >= self.count()) return;
try self.delete_range(index, index + 1);
try self.insert_slice(index, &[_]T{data});
}
pub fn append(self: *Self, data: T) !void {
try self.insert(self.count(), data);
}
pub fn prepend(self: *Self, data: T) !void {
try self.insert(0, data);
}
pub fn concat(self: *Self, other: *const Self) !void {
self.root = try self.joinWithBoundary(self.root, other.root);
self.version += 1;
}
pub fn split(self: *Self, index: u32) !Self {
const result = try Node.split_at(self.root, index, self.allocator, self.empty_leaf);
self.root = result.left;
self.version += 1;
return Self{
.root = result.right,
.allocator = self.allocator,
.empty_leaf = self.empty_leaf,
.undo_history = null,
.redo_history = null,
.curr_history = null,
.marker_cache = MarkerCache.init(self.allocator),
};
}
pub fn slice(self: *const Self, start: u32, end: u32, allocator: Allocator) ![]T {
if (start >= end) return &[_]T{};
const SliceContext = struct {
items: std.ArrayListUnmanaged(T),
allocator: Allocator,
start: u32,
end: u32,
current_index: u32 = 0,
fn walker(ctx: *anyopaque, data: *const T, idx: u32) Node.WalkerResult {
_ = idx;
const context = @as(*@This(), @ptrCast(@alignCast(ctx)));
if (context.current_index >= context.start and context.current_index < context.end) {
context.items.append(context.allocator, data.*) catch |e| return .{ .err = e };
}
context.current_index += 1;
if (context.current_index >= context.end) {
return .{ .keep_walking = false };
}
return .{};
}
};
var context = SliceContext{
.items = .{},
.allocator = allocator,
.start = start,
.end = end,
};
errdefer context.items.deinit(allocator);
try self.walk(&context, SliceContext.walker);
return context.items.toOwnedSlice(allocator);
}
pub fn delete_range(self: *Self, start: u32, end: u32) !void {
if (start >= end) return;
const first_split = try Node.split_at(self.root, start, self.allocator, self.empty_leaf);
const second_split = try Node.split_at(first_split.right, end - start, self.allocator, self.empty_leaf);
self.root = try self.joinWithBoundary(first_split.left, second_split.right);
self.version += 1;
try self.applyEndsInvariant();
}
pub fn insert_slice(self: *Self, index: u32, items: []const T) !void {
if (items.len == 0) return;
const insert_rope = try Self.from_slice(self.allocator, items);
const split_result = try Node.split_at(self.root, index, self.allocator, self.empty_leaf);
const left_joined = try self.joinWithBoundary(split_result.left, insert_rope.root);
self.root = try self.joinWithBoundary(left_joined, split_result.right);
self.version += 1;
try self.applyEndsInvariant();
}
pub fn to_array(self: *const Self, allocator: Allocator) ![]T {
const ToArrayContext = struct {
items: std.ArrayListUnmanaged(T),
allocator: Allocator,
fn walker(ctx: *anyopaque, data: *const T, idx: u32) Node.WalkerResult {
_ = idx;
const context = @as(*@This(), @ptrCast(@alignCast(ctx)));
context.items.append(context.allocator, data.*) catch |e| return .{ .err = e };
return .{};
}
};
var context = ToArrayContext{
.items = .{},
.allocator = allocator,
};
errdefer context.items.deinit(allocator);
try self.walk(&context, ToArrayContext.walker);
return context.items.toOwnedSlice(allocator);
}
pub fn toText(self: *const Self, allocator: Allocator) ![]u8 {
var buffer: std.ArrayListUnmanaged(u8) = .{};
errdefer buffer.deinit(allocator);
try buffer.appendSlice(allocator, "[root");
try nodeToText(self.root, &buffer, allocator);
try buffer.append(allocator, ']');
return buffer.toOwnedSlice(allocator);
}
fn nodeToText(node: *const Node, buffer: *std.ArrayListUnmanaged(u8), allocator: Allocator) !void {
switch (node.*) {
.branch => |*b| {
try buffer.appendSlice(allocator, "[branch");
try nodeToText(b.left, buffer, allocator);
try nodeToText(b.right, buffer, allocator);
try buffer.append(allocator, ']');
},
.leaf => |*l| {
if (l.is_sentinel) {
try buffer.appendSlice(allocator, "[empty]");
return;
}
if (@typeInfo(T) == .@"union") {
const tag = std.meta.activeTag(l.data);
const tag_name = @tagName(tag);
try buffer.append(allocator, '[');
try buffer.appendSlice(allocator, tag_name);
if (@hasDecl(T, "Metrics")) {
const metrics = l.metrics();
try buffer.append(allocator, ':');
try buffer.writer(allocator).print("w{d}", .{metrics.weight()});
if (@hasDecl(T.Metrics, "total_width")) {
try buffer.writer(allocator).print(",tw{d}", .{metrics.custom.total_width});
}
if (@hasDecl(T.Metrics, "total_bytes")) {
try buffer.writer(allocator).print(",b{d}", .{metrics.custom.total_bytes});
}
}
try buffer.append(allocator, ']');
} else {
try buffer.appendSlice(allocator, "[leaf");
if (@hasDecl(T, "Metrics")) {
const metrics = l.metrics();
try buffer.append(allocator, ':');
try buffer.writer(allocator).print("w{d}", .{metrics.weight()});
}
try buffer.append(allocator, ']');
}
},
}
}
pub fn totalWeight(self: *const Self) u32 {
return self.root.metrics().weight();
}
pub fn splitByWeight(self: *Self, weight: u32, split_leaf_fn: *const Node.LeafSplitFn) !Self {
const result = try Node.split_at_weight(self.root, weight, self.allocator, self.empty_leaf, split_leaf_fn);
self.root = result.left;
self.version += 1;
return Self{
.root = result.right,
.allocator = self.allocator,
.empty_leaf = self.empty_leaf,
.undo_history = null,
.redo_history = null,
.curr_history = null,
.marker_cache = MarkerCache.init(self.allocator),
};
}
fn getLastLeaf(self: *const Self) ?*const T {
if (self.count() == 0) return null;
return self.get(self.count() - 1);
}
fn getFirstLeaf(self: *const Self) ?*const T {
if (self.count() == 0) return null;
return self.get(0);
}
fn getFirstLeafIn(node: *const Node) ?*const T {
return switch (node.*) {
.branch => |*b| getFirstLeafIn(b.left),
.leaf => |*l| if (node.count() == 0) null else &l.data,
};
}
fn getLastLeafIn(node: *const Node) ?*const T {
return switch (node.*) {
.branch => |*b| getLastLeafIn(b.right),
.leaf => |*l| if (node.count() == 0) null else &l.data,
};
}
fn dropFirst(node: *const Node, allocator: Allocator, empty_leaf: *const Node) error{OutOfMemory}!*const Node {
if (node.count() == 0) return node;
const split_result = try Node.split_at(node, 1, allocator, empty_leaf);
return split_result.right;
}
fn dropLast(node: *const Node, allocator: Allocator, empty_leaf: *const Node) error{OutOfMemory}!*const Node {
const cnt = node.count();
if (cnt == 0) return node;
const split_result = try Node.split_at(node, cnt - 1, allocator, empty_leaf);
return split_result.left;
}
fn joinWithBoundary(self: *Self, left: *const Node, right: *const Node) error{OutOfMemory}!*const Node {
if (!boundary_enabled or !@hasDecl(T, "rewriteBoundary")) {
return try Node.join_balanced(left, right, self.allocator);
}
const l_last = getLastLeafIn(left);
const r_first = getFirstLeafIn(right);
if (@hasDecl(T, "canMerge") and @hasDecl(T, "merge")) {
if (l_last != null and r_first != null) {
if (T.canMerge(l_last.?, r_first.?)) {
const merged = T.merge(self.allocator, l_last.?, r_first.?);
const merged_leaf = try Node.new_leaf(self.allocator, merged);
const L = try dropLast(left, self.allocator, self.empty_leaf);
const R = try dropFirst(right, self.allocator, self.empty_leaf);
const left_with_merged = try Node.join_balanced(L, merged_leaf, self.allocator);
return try Node.join_balanced(left_with_merged, R, self.allocator);
}
}
}
const action = try T.rewriteBoundary(self.allocator, l_last, r_first);
var L = left;
var R = right;
if (action.delete_left) {
L = try dropLast(L, self.allocator, self.empty_leaf);
}
if (action.delete_right) {
R = try dropFirst(R, self.allocator, self.empty_leaf);
}
if (action.insert_between.len > 0) {
const insert_rope = try Self.from_slice(self.allocator, action.insert_between);
const left_with_insert = try Node.join_balanced(L, insert_rope.root, self.allocator);
return try Node.join_balanced(left_with_insert, R, self.allocator);
}
return try Node.join_balanced(L, R, self.allocator);
}
fn applyEndsInvariant(self: *Self) !void {
if (!boundary_enabled or !@hasDecl(T, "rewriteEnds")) return;
const first = self.getFirstLeaf();
const last = self.getLastLeaf();
const action = try T.rewriteEnds(self.allocator, first, last);
// Handle deletion operations first
if (action.delete_left and self.count() > 0) {
const split_result = try Node.split_at(self.root, 1, self.allocator, self.empty_leaf);
self.root = split_result.right;
}
if (action.delete_right and self.count() > 0) {
const cnt = self.count();
const split_result = try Node.split_at(self.root, cnt - 1, self.allocator, self.empty_leaf);
self.root = split_result.left;
}
// Handle insertion
if (action.insert_between.len > 0) {
var leaves: std.ArrayListUnmanaged(*const Node) = .{};
defer leaves.deinit(self.allocator);
try leaves.ensureTotalCapacity(self.allocator, action.insert_between.len);
for (action.insert_between) |item| {
const leaf = try Node.new_leaf(self.allocator, item);
try leaves.append(self.allocator, leaf);
}
const insert_root = try Node.merge_leaves(leaves.items, self.allocator);
self.root = try Node.join_balanced(insert_root, self.root, self.allocator);
}
}
pub fn deleteRangeByWeight(self: *Self, start: u32, end: u32, split_leaf_fn: *const Node.LeafSplitFn) !void {
if (start >= end) return;
const first_split = try Node.split_at_weight(self.root, start, self.allocator, self.empty_leaf, split_leaf_fn);
const second_split = try Node.split_at_weight(first_split.right, end - start, self.allocator, self.empty_leaf, split_leaf_fn);
self.root = try self.joinWithBoundary(first_split.left, second_split.right);
self.version += 1;
try self.applyEndsInvariant();
}
pub fn insertSliceByWeight(self: *Self, weight: u32, items: []const T, split_leaf_fn: *const Node.LeafSplitFn) !void {
if (items.len == 0) return;
const insert_rope = try Self.from_slice(self.allocator, items);
const split_result = try Node.split_at_weight(self.root, weight, self.allocator, self.empty_leaf, split_leaf_fn);
const left_joined = try self.joinWithBoundary(split_result.left, insert_rope.root);
self.root = try self.joinWithBoundary(left_joined, split_result.right);
self.version += 1;
try self.applyEndsInvariant();
}
pub const WeightFindResult = struct { leaf: *const T, start_weight: u32 };
pub fn findByWeight(self: *const Self, weight: u32) ?WeightFindResult {
return self.findByWeightInNode(self.root, weight, 0);
}
fn findByWeightInNode(self: *const Self, node: *const Node, target_weight: u32, current_weight: u32) ?WeightFindResult {
return switch (node.*) {
.branch => |*b| {
const left_weight = b.left_metrics.weight();
if (target_weight < current_weight + left_weight) {
return self.findByWeightInNode(b.left, target_weight, current_weight);
}
return self.findByWeightInNode(b.right, target_weight, current_weight + left_weight);
},
.leaf => |*l| {
const leaf_weight = node.metrics().weight();
if (target_weight < current_weight + leaf_weight) {
return .{ .leaf = &l.data, .start_weight = current_weight };
}
return null;
},
};
}
/// Undo/Redo operations
pub fn store_undo(self: *Self, meta: []const u8) !void {
const undo_node = try self.create_undo_node(self.root, meta);
self.push_undo(undo_node);
self.curr_history = null;
try self.push_redo_branch();
}
fn create_undo_node(self: *const Self, root: *const Node, meta_: []const u8) !*UndoNode {
const undo_node = try self.allocator.create(UndoNode);
const meta = try self.allocator.dupe(u8, meta_);
undo_node.* = UndoNode{
.root = root,
.meta = meta,
};
return undo_node;
}
fn push_undo(self: *Self, undo_node: *UndoNode) void {
const next = self.undo_history;
self.undo_history = undo_node;
undo_node.next = next;
self.undo_depth += 1;
// Trim history if we exceed max_undo_depth
if (self.config.max_undo_depth) |max_depth| {
if (self.undo_depth > max_depth) {
self.trimUndoHistory(max_depth);
}
}
}
fn trimUndoHistory(self: *Self, max_depth: usize) void {
var current = self.undo_history;
var depth_count: usize = 0;
var prev: ?*UndoNode = null;
while (current) |node| {
depth_count += 1;
if (depth_count >= max_depth) {
// Cut off the rest of the history
if (prev) |p| {
p.next = null;
}
self.undo_depth = max_depth;
return;
}
prev = node;
current = node.next;
}
}
fn push_redo(self: *Self, undo_node: *UndoNode) void {
const next = self.redo_history;
self.redo_history = undo_node;
undo_node.next = next;
}
fn push_redo_branch(self: *Self) !void {
const r = self.redo_history orelse return;
const u = self.undo_history orelse return;
const next = u.branches;
const b = try self.allocator.create(UndoBranch);
b.* = .{
.redo = r,
.next = next,
};
u.branches = b;
self.redo_history = null;
}
pub fn undo(self: *Self, meta: []const u8) ![]const u8 {
const r = self.curr_history orelse try self.create_undo_node(self.root, meta);
const h = self.undo_history orelse return error.Stop;
self.undo_history = h.next;
self.curr_history = h;
self.root = h.root;
self.version += 1;
self.push_redo(r);
if (self.undo_depth > 0) self.undo_depth -= 1;
return h.meta;
}
pub fn redo(self: *Self) ![]const u8 {
const u = self.curr_history orelse return error.Stop;
const h = self.redo_history orelse return error.Stop;
if (u.root != self.root) return error.Stop;
self.redo_history = h.next;
self.curr_history = h;
self.root = h.root;
self.version += 1;
self.push_undo(u);
return h.meta;
}
pub fn can_undo(self: *const Self) bool {
return self.undo_history != null;
}
pub fn can_redo(self: *const Self) bool {
return self.redo_history != null and self.curr_history != null;
}
pub fn clear_history(self: *Self) void {
self.undo_history = null;
self.redo_history = null;
self.curr_history = null;
self.undo_depth = 0;
}
pub fn clear(self: *Self) void {
self.root = self.empty_leaf;
self.version += 1;
self.applyEndsInvariant() catch {};
}
/// Replace the rope content with new items, using same structure as from_slice
/// This is useful for repeated setText operations without creating a new rope instance
pub fn setSegments(self: *Self, items: []const T) !void {
if (items.len == 0) {
self.root = self.empty_leaf;
self.version += 1;
try self.applyEndsInvariant();
return;
}
var leaves: std.ArrayListUnmanaged(*const Node) = .{};
defer leaves.deinit(self.allocator);
try leaves.ensureTotalCapacity(self.allocator, items.len);
for (items) |item| {
const leaf = try Node.new_leaf(self.allocator, item);
try leaves.append(self.allocator, leaf);
}
self.root = try Node.merge_leaves(leaves.items, self.allocator);
self.version += 1;
}
fn rebuildMarkerCache(self: *Self) !void {
if (!marker_enabled) return;
self.marker_cache.clear();
const RebuildContext = struct {
cache: *MarkerCache,
current_leaf: u32 = 0,
current_weight: u32 = 0,
fn walker(ctx: *anyopaque, data: *const T, idx: u32) Node.WalkerResult {
_ = idx;
const context = @as(*@This(), @ptrCast(@alignCast(ctx)));
const tag = std.meta.activeTag(data.*);
var is_marker = false;
inline for (T.MarkerTypes) |mt| {
if (tag == mt) {
is_marker = true;
break;
}
}
const leaf_weight = if (@hasDecl(T, "Metrics")) blk: {
if (@hasDecl(T, "measure")) {
const metrics = data.measure();
break :blk if (@hasDecl(T.Metrics, "weight")) metrics.weight() else 1;
}
break :blk 1;
} else 1;
if (is_marker) {
const gop = context.cache.positions.getOrPut(tag) catch |e| {
return .{ .keep_walking = false, .err = e };
};
if (!gop.found_existing) {
gop.value_ptr.* = .{};
}
gop.value_ptr.append(context.cache.allocator, .{
.leaf_index = context.current_leaf,
.global_weight = context.current_weight,
}) catch |e| {
return .{ .keep_walking = false, .err = e };
};
}
context.current_leaf += 1;
context.current_weight += leaf_weight;
return .{};
}
};
var ctx = RebuildContext{ .cache = &self.marker_cache };
try self.walk(&ctx, RebuildContext.walker);
self.marker_cache.version = self.version;
}
pub fn markerCount(self: *Self, tag: std.meta.Tag(T)) u32 {
if (!marker_enabled) return 0;
if (self.marker_cache.version != self.version) {
self.rebuildMarkerCache() catch return 0;
}
const list = self.marker_cache.positions.get(tag) orelse return 0;
return @intCast(list.items.len);
}
pub fn getMarker(self: *Self, tag: std.meta.Tag(T), occurrence: u32) ?MarkerPosition {
if (!marker_enabled) return null;
if (self.marker_cache.version != self.version) {
self.rebuildMarkerCache() catch return null;
}
const list = self.marker_cache.positions.get(tag) orelse return null;
if (occurrence >= list.items.len) return null;
return list.items[occurrence];
}
};
}