const std = @import("std");
const tree = @import("piece_tree.zig");
const md = @import("markdown.zig");
const inline_markdown = @import("inline_markdown.zig");

pub const Position = struct {
    id: u32 = 0,
    offset: u32 = 0,
};

pub const Selection = struct {
    anchor: Position = .{},
    focus: Position = .{},
};

pub const Block = struct {
    id: u32,
    kind: u32,
    root: tree.Root,
    prefix: tree.Root = null,
    suffix: tree.Root = null,
    cache: ?[]u8 = null,
    depth: u32 = 0,
    ordinal: u32 = 0,
    separator: u8 = 1,
};

fn tree_contains_lf(root: tree.Root) bool {
    for (0..tree.length(root)) |i| {
        if (tree.byte_at(root, i) == '\n') {
            return true;
        }
    }
    return false;
}

fn release_block(allocator: std.mem.Allocator, b: Block) void {
    tree.release(allocator, b.root);
    tree.release(allocator, b.prefix);
    tree.release(allocator, b.suffix);
}

const Snapshot = struct {
    blocks: []Block = &.{},
    selection: Selection = .{},
};

const limit = 100;

pub const Editor = struct {
    allocator: std.mem.Allocator,
    state: Snapshot = .{},
    past: [limit]Snapshot = @splat(.{}),
    future: [limit]Snapshot = @splat(.{}),
    past_len: usize = 0,
    future_len: usize = 0,
    next_id: u64 = 1,
    revision: u32 = 0,
    markdown: ?[]u8 = null,
    changed_ids: []u32 = &.{},
    shape: bool = false,

    fn destroy(self: *Editor, s: Snapshot) void {
        for (s.blocks) |b| {
            release_block(self.allocator, b);
            if (b.cache) |c| {
                self.allocator.free(c);
            }
        }
        self.allocator.free(s.blocks);
    }

    fn clear(self: *Editor, history: *[limit]Snapshot, len: *usize) void {
        for (history[0..len.*]) |s| {
            self.destroy(s);
        }
        len.* = 0;
    }

    fn push(self: *Editor, history: *[limit]Snapshot, len: *usize, s: Snapshot) void {
        if (len.* == limit) {
            self.destroy(history[0]);
            std.mem.copyForwards(Snapshot, history[0 .. limit - 1], history[1..]);
            len.* -= 1;
        }
        history[len.*] = s;
        len.* += 1;
    }

    fn invalidate(self: *Editor) void {
        if (self.markdown) |m| {
            self.allocator.free(m);
        }
        self.markdown = null;
        // Render caches are not retained by history.
        for (self.state.blocks) |*b| {
            if (b.cache) |c| {
                self.allocator.free(c);
            }
            b.cache = null;
        }
    }

    pub fn deinit(self: *Editor) void {
        self.invalidate();
        self.destroy(self.state);
        self.clear(&self.past, &self.past_len);
        self.clear(&self.future, &self.future_len);
        self.allocator.free(self.changed_ids);
        self.state = .{};
        self.changed_ids = &.{};
    }

    pub fn init(self: *Editor) bool {
        if (self.next_id > std.math.maxInt(u32)) {
            return false;
        }

        const blocks = self.allocator.alloc(Block, 1) catch return false;
        const ids = self.allocator.alloc(u32, 1) catch {
            self.allocator.free(blocks);
            return false;
        };

        const id: u32 = @intCast(self.next_id);
        blocks[0] = .{
            .id = id,
            .kind = 0,
            .root = null,
        };
        ids[0] = id;
        self.deinit();
        self.next_id += 1;
        self.state = .{
            .blocks = blocks,
            .selection = .{
                .anchor = .{
                    .id = id,
                },
                .focus = .{
                    .id = id,
                },
            },
        };
        self.changed_ids = ids;
        self.shape = true;
        self.revision +%= 1;
        return true;
    }

    /// Input must already be LF-normalized. Import is one undoable transaction.
    pub fn import_markdown(self: *Editor, source: []const u8) bool {
        if (!std.unicode.utf8ValidateSlice(source) or std.mem.indexOfScalar(u8, source, '\r') != null or source.len > std.math.maxInt(u32)) {
            return false;
        }
        var counter: md.Blocks = .{
            .source = source,
        };
        var count: usize = 0;
        while (counter.next() != null) {
            count += 1;
        }
        if (count > std.math.maxInt(u32) or self.next_id + count > @as(u64, std.math.maxInt(u32)) + 1) {
            return false;
        }

        const blocks = self.allocator.alloc(Block, count) catch return false;
        var filled: usize = 0;
        var committed = false;
        defer {
            if (!committed) {
                for (blocks[0..filled]) |b| {
                    release_block(self.allocator, b);
                }
                self.allocator.free(blocks);
            }
        }

        const ids = self.allocator.alloc(u32, count) catch return false;
        defer {
            if (!committed) {
                self.allocator.free(ids);
            }
        }
        var parser: md.Blocks = .{
            .source = source,
        };
        while (parser.next()) |parsed| {
            const id: u32 = @intCast(self.next_id + filled);
            blocks[filled] = .{
                .id = id,
                .kind = parsed.kind,
                .depth = parsed.depth,
                .ordinal = parsed.ordinal,
                .root = null,
            };
            ids[filled] = id;
            filled += 1;
            const block = &blocks[filled - 1];
            block.root = tree.from_bytes(self.allocator, parsed.text) catch return false;
            block.prefix = tree.from_bytes(self.allocator, parsed.prefix) catch return false;
            block.suffix = tree.from_bytes(self.allocator, parsed.suffix) catch return false;
        }

        const caret: Position = .{
            .id = ids[0],
        };
        self.commit(.{
            .blocks = blocks,
            .selection = .{
                .anchor = caret,
                .focus = caret,
            },
        }, ids, true);
        self.next_id += count;
        committed = true;
        return true;
    }

    fn index_of(self: *Editor, id: u32) ?usize {
        for (self.state.blocks, 0..) |b, i| {
            if (b.id == id) {
                return i;
            }
        }
        return null;
    }

    fn valid_position(self: *Editor, p: Position) bool {
        const i = self.index_of(p.id) orelse return false;
        const root = self.state.blocks[i].root;
        const len = tree.length(root);
        return p.offset <= len and (p.offset == len or tree.byte_at(root, p.offset) & 0xc0 != 0x80);
    }

    pub fn set_selection(self: *Editor, selection: Selection) bool {
        if (!self.valid_position(selection.anchor) or !self.valid_position(selection.focus)) {
            return false;
        }
        self.state.selection = selection;
        return true;
    }

    /// Resolve only ambiguous projected positions. Exact source selections and
    /// edit ranges deliberately do not call this: after-close is meaningful.
    pub fn inline_resolve(self: *Editor, index: usize, offset: u32, bias: i32) ?u32 {
        if (index >= self.state.blocks.len or !self.valid_position(.{
            .id = self.state.blocks[index].id,
            .offset = offset,
        })) {
            return null;
        }
        const text = self.block_text(index) orelse return null;
        const runs = inline_markdown.parse(self.allocator, text, self.state.blocks[index].kind == md.code) catch return null;
        defer self.allocator.free(runs);

        return inline_markdown.resolve(runs, offset, bias);
    }

    /// Same-block projected replacement. The adapter supplies grapheme-aligned
    /// source endpoints; keep the first selected span's formatting and remove
    /// later wrappers emptied by the edit. History
    /// captures the original selection, including its exact delimiter side.
    pub fn inline_replace(self: *Editor, index: usize, anchor: u32, focus: u32, text: []const u8) bool {
        if (index >= self.state.blocks.len) {
            return false;
        }
        const id = self.state.blocks[index].id;
        const low = @min(anchor, focus);
        const high = @max(anchor, focus);
        if (!self.valid_position(.{ .id = id, .offset = low }) or
            !self.valid_position(.{ .id = id, .offset = high }))
        {
            return false;
        }
        if (low == high) {
            return self.replace_range(.{
                .anchor = .{ .id = id, .offset = low },
                .focus = .{ .id = id, .offset = high },
            }, text);
        }
        const source = self.block_text(index) orelse return false;
        var spans: std.ArrayList(inline_markdown.Span) = .empty;
        defer spans.deinit(self.allocator);
        const runs = inline_markdown.parse_with_spans(self.allocator, source, self.state.blocks[index].kind == md.code, &spans) catch return false;
        defer self.allocator.free(runs);
        return self.inline_replace_prepared(id, source, runs, spans.items, low, high, text);
    }

    fn inline_replace_prepared(self: *Editor, id: u32, source: []const u8, runs: []const inline_markdown.Run, spans: []const inline_markdown.Span, low: u32, high: u32, text: []const u8) bool {
        const Interval = struct {
            start: u32,
            end: u32,

            fn less_than(_: void, a: @This(), b: @This()) bool {
                return a.start < b.start;
            }
        };

        var removed: std.ArrayList(Interval) = .empty;
        defer removed.deinit(self.allocator);
        for (runs) |run| {
            const start = @max(low, run.start);
            const end = @min(high, run.end);
            if (start < end) {
                removed.append(self.allocator, .{ .start = start, .end = end }) catch return false;
            }
        }
        if (removed.items.len == 0) {
            return false;
        }
        const first_visible = removed.items[0].start;
        for (spans) |span| {
            // Replacement inherits every wrapper containing its first visible
            // byte, even when all original content in that wrapper is removed.
            if (text.len > 0 and span.content_start <= first_visible and first_visible < span.content_end) {
                continue;
            }
            if (span.content_end <= low or span.content_start >= high) {
                continue;
            }
            const fully_covered = span.content_start >= low and span.content_end <= high;
            var has_content = fully_covered;
            var emptied = true;
            for (if (fully_covered) runs[0..0] else runs) |run| {
                const start = @max(span.content_start, run.start);
                const end = @min(span.content_end, run.end);
                if (start < end) {
                    has_content = true;
                    if (start < low or end > high) {
                        emptied = false;
                        break;
                    }
                }
            }
            if (has_content and emptied) {
                removed.append(self.allocator, .{ .start = span.start, .end = span.content_start }) catch return false;
                removed.append(self.allocator, .{ .start = span.content_end, .end = span.end }) catch return false;
            }
        }
        std.mem.sort(Interval, removed.items, {}, Interval.less_than);
        const begin = removed.items[0].start;
        var cursor = begin;
        var replacement: std.ArrayList(u8) = .empty;
        defer replacement.deinit(self.allocator);
        replacement.appendSlice(self.allocator, text) catch return false;
        const single_line = std.mem.indexOfScalar(u8, text, '\n') == null;
        for (removed.items) |interval| {
            if (interval.start > cursor) {
                replacement.appendSlice(self.allocator, source[cursor..interval.start]) catch return false;
            }
            cursor = @max(cursor, interval.end);
        }
        const result = self.replace_range(.{
            .anchor = .{ .id = id, .offset = begin },
            .focus = .{ .id = id, .offset = cursor },
        }, replacement.items);
        if (result and single_line) {
            // Retained syntax follows the inserted text, not the caret.
            const caret: Position = .{ .id = id, .offset = begin + @as(u32, @intCast(text.len)) };
            self.state.selection = .{ .anchor = caret, .focus = caret };
        }
        return result;
    }

    fn clone_block(b: Block) Block {
        return .{
            .id = b.id,
            .kind = b.kind,
            .depth = b.depth,
            .ordinal = b.ordinal,
            .separator = b.separator,
            .root = tree.retain(b.root),
            .prefix = tree.retain(b.prefix),
            .suffix = tree.retain(b.suffix),
        };
    }

    fn commit(self: *Editor, next: Snapshot, ids: []u32, shape: bool) void {
        self.invalidate();
        self.push(&self.past, &self.past_len, self.state);
        self.clear(&self.future, &self.future_len);
        self.state = next;
        self.allocator.free(self.changed_ids);
        self.changed_ids = ids;
        self.shape = shape;
        self.revision +%= 1;
    }

    /// Backspace removes a preceding atomic rule or empty heading formatting.
    /// Null indicates failure; false leaves ordinary text deletion to the caller.
    pub fn backspace_boundary(self: *Editor) ?bool {
        const selection = self.state.selection;
        if (selection.anchor.id != selection.focus.id or selection.anchor.offset != selection.focus.offset or selection.focus.offset != 0) {
            return false;
        }
        const index = self.index_of(selection.focus.id) orelse return null;
        const block = self.state.blocks[index];
        if (block.kind == md.paragraph and index > 0 and self.state.blocks[index - 1].kind == md.rule) {
            const blocks = self.allocator.alloc(Block, self.state.blocks.len - 1) catch return null;
            const ids = self.allocator.alloc(u32, 1) catch {
                self.allocator.free(blocks);
                return null;
            };
            var output: usize = 0;
            for (self.state.blocks, 0..) |b, i| {
                if (i == index - 1) {
                    continue;
                }
                blocks[output] = clone_block(b);
                if (i == index) {
                    blocks[output].separator = self.state.blocks[index - 1].separator;
                }
                output += 1;
            }
            ids[0] = block.id;
            self.commit(.{ .blocks = blocks, .selection = selection }, ids, true);
            return true;
        }
        if (block.kind < 1 or block.kind > 6 or tree.length(block.root) != 0) {
            return false;
        }
        if (!self.set_kind(index, 0)) {
            return null;
        }
        return true;
    }

    pub fn set_kind(self: *Editor, index: usize, kind: u32) bool {
        if (index >= self.state.blocks.len or kind > 6) {
            return false;
        }
        if (self.state.blocks[index].kind > 6 or (kind != 0 and tree_contains_lf(self.state.blocks[index].root))) {
            return false;
        }

        if (self.state.blocks[index].kind == kind) {
            return true;
        }

        const blocks = self.allocator.alloc(Block, self.state.blocks.len) catch return false;
        const ids = self.allocator.alloc(u32, 1) catch {
            self.allocator.free(blocks);
            return false;
        };
        for (self.state.blocks, blocks) |b, *out| {
            out.* = clone_block(b);
        }
        if (blocks[index].kind != kind) {
            tree.release(self.allocator, blocks[index].prefix);
            tree.release(self.allocator, blocks[index].suffix);
            blocks[index].prefix = null;
            blocks[index].suffix = null;
        }
        blocks[index].kind = kind;
        ids[0] = blocks[index].id;
        const shape = self.state.blocks[index].kind != kind;
        self.commit(.{
            .blocks = blocks,
            .selection = self.state.selection,
        }, ids, shape);
        return true;
    }

    /// Byte ranges must be scalar-aligned. Grapheme deletion is a renderer concern:
    /// use Intl.Segmenter to compute the range, then call replace_range.
    /// CR is rejected; callers normalize CRLF/CR to LF.
    pub fn replace_selection(self: *Editor, text: []const u8) bool {
        return self.replace_range(self.state.selection, text);
    }

    /// Apply an independent edit range without replacing the pre-edit selection
    /// saved in history. The successful edit collapses the caret after insertion.
    pub fn replace_range(self: *Editor, range: Selection, text: []const u8) bool {
        return self.replace_range_with_intent(range, text, false);
    }

    /// Ordinary typing may convert heading markers and fences, or exit code.
    pub fn type_text(self: *Editor, text: []const u8, range: Selection) bool {
        return self.replace_range_with_intent(range, text, true);
    }

    fn replace_range_with_intent(self: *Editor, range: Selection, text: []const u8, typing: bool) bool {
        if (!self.valid_position(range.anchor) or !self.valid_position(range.focus)) {
            return false;
        }
        if (!std.unicode.utf8ValidateSlice(text) or std.mem.indexOfScalar(u8, text, '\r') != null) {
            return false;
        }
        var first = range.anchor;
        var last = range.focus;
        var start = self.index_of(first.id) orelse return false;
        var end = self.index_of(last.id) orelse return false;
        if (start > end or (start == end and first.offset > last.offset)) {
            std.mem.swap(Position, &first, &last);
            std.mem.swap(usize, &start, &end);
        }

        const original = self.state.blocks[start];
        if (typing and start == end and first.offset == last.offset and
            first.offset == tree.length(original.root) and std.mem.eql(u8, text, "\n"))
        {
            if (original.kind == md.paragraph and !tree_contains_lf(original.root)) {
                const opener = self.allocator.alloc(u8, tree.length(original.root)) catch return false;
                defer self.allocator.free(opener);
                tree.copy(original.root, opener);

                var scanner: md.Scanner = .{};
                _ = scanner.next(opener);
                if (scanner.marker != 0) {
                    var indent: usize = 0;
                    while (opener[indent] == ' ') : (indent += 1) {}
                    return self.fence_enter(start, opener[indent..][0..scanner.width]);
                }
            } else if (original.kind == md.code and first.offset > 0 and
                tree.byte_at(original.root, first.offset - 1) == '\n')
            {
                return self.fence_enter(start, null);
            }
        }

        // Paragraph Enter acts on visible block edges, not on the exact side
        // of a hidden delimiter. Keep explicit replacements (soft breaks) exact.
        if (typing and start == end and first.offset == last.offset and
            original.kind != md.code and std.mem.eql(u8, text, "\n"))
        {
            const source = self.allocator.alloc(u8, tree.length(original.root)) catch return false;
            defer self.allocator.free(source);
            tree.copy(original.root, source);

            const runs = inline_markdown.parse(self.allocator, source, false) catch return false;
            defer self.allocator.free(runs);

            var visible_start: usize = source.len;
            var visible_end: usize = 0;
            for (runs) |run| {
                if (run.start == run.end) {
                    continue;
                }
                visible_start = @min(visible_start, run.start);
                visible_end = @max(visible_end, run.end);
            }
            if (visible_start < visible_end) {
                if (first.offset <= visible_start) {
                    first.offset = 0;
                } else if (first.offset >= visible_end) {
                    first.offset = @intCast(source.len);
                }
                last.offset = first.offset;
            }
        }

        const item = original.kind == md.quote or original.kind == md.unordered or original.kind == md.ordered;
        const whole_delete = text.len == 0 and first.offset == 0 and last.offset == tree.length(self.state.blocks[end].root);
        const heading = original.kind >= 1 and original.kind <= 6;
        const exit_item = start == end and (item or heading) and tree.length(original.root) == 0 and std.mem.eql(u8, text, "\n");
        const clear_kind = exit_item or original.kind == md.rule or (whole_delete and start != end);
        const insertion = if (exit_item) "" else text;
        if (start != end and !whole_delete) {
            for (self.state.blocks[start .. end + 1]) |b| {
                if (b.kind > 6) {
                    return false;
                }
            }
        }

        const is_code = start == end and self.state.blocks[start].kind == md.code;
        var lines: usize = 1;
        for (insertion) |c| {
            if (c == '\n' and !is_code) {
                lines += 1;
            }
        }
        if (self.next_id + lines - 1 > @as(u64, std.math.maxInt(u32)) + 1) {
            return false;
        }

        const count = std.math.add(usize, self.state.blocks.len - (end - start), lines - 1) catch return false;
        if (count > std.math.maxInt(u32)) {
            return false;
        }

        const blocks = self.allocator.alloc(Block, count) catch return false;
        var filled: usize = 0;
        var committed = false;
        defer {
            if (!committed) {
                for (blocks[0..filled]) |b| {
                    release_block(self.allocator, b);
                }
                self.allocator.free(blocks);
            }
        }
        return self.replace_prepared(
            insertion,
            first,
            last,
            start,
            end,
            lines,
            blocks,
            &filled,
            &committed,
            clear_kind,
            typing,
        );
    }

    // Prepare all owned data before committing either structural Enter operation.
    fn fence_enter(self: *Editor, index: usize, closing: ?[]const u8) bool {
        const exiting = closing == null;
        if (exiting and (self.next_id > std.math.maxInt(u32) or self.state.blocks.len == std.math.maxInt(u32))) {
            return false;
        }
        const original = self.state.blocks[index];
        const root = if (exiting)
            tree.slice(self.allocator, original.root, 0, tree.length(original.root) - 1) catch return false
        else
            null;
        defer tree.release(self.allocator, root);

        const newline = if (!exiting) tree.from_bytes(self.allocator, "\n") catch return false else null;
        defer tree.release(self.allocator, newline);
        const prefix = if (!exiting) tree.concat(self.allocator, original.root, newline) catch return false else tree.retain(original.prefix);
        defer tree.release(self.allocator, prefix);
        const suffix = if (closing) |bytes| tree.from_bytes(self.allocator, bytes) catch return false else tree.retain(original.suffix);
        defer tree.release(self.allocator, suffix);

        const blocks = self.allocator.alloc(Block, self.state.blocks.len + @as(usize, if (exiting) 1 else 0)) catch return false;
        var filled: usize = 0;
        var committed = false;
        defer {
            if (!committed) {
                for (blocks[0..filled]) |b| {
                    release_block(self.allocator, b);
                }
                self.allocator.free(blocks);
            }
        }
        const ids = self.allocator.alloc(u32, if (exiting) 2 else 1) catch return false;
        defer {
            if (!committed) {
                self.allocator.free(ids);
            }
        }

        var caret = Position{ .id = original.id, .offset = 0 };
        for (self.state.blocks, 0..) |b, i| {
            blocks[filled] = clone_block(b);
            filled += 1;
            if (i != index) {
                continue;
            }

            const out = &blocks[filled - 1];
            tree.release(self.allocator, out.root);
            tree.release(self.allocator, out.prefix);
            tree.release(self.allocator, out.suffix);
            out.root = tree.retain(root);
            out.prefix = tree.retain(prefix);
            out.suffix = tree.retain(suffix);
            out.kind = md.code;
            ids[0] = out.id;

            if (exiting) {
                caret.id = @intCast(self.next_id);
                blocks[filled] = .{ .id = caret.id, .kind = md.paragraph, .root = null, .separator = 2 };
                filled += 1;
                ids[1] = caret.id;
            }
        }
        self.commit(.{
            .blocks = blocks,
            .selection = .{ .anchor = caret, .focus = caret },
        }, ids, true);
        if (exiting) {
            self.next_id += 1;
        }
        committed = true;
        return true;
    }

    fn replace_prepared(
        self: *Editor,
        text: []const u8,
        first: Position,
        last: Position,
        start: usize,
        end: usize,
        lines: usize,
        blocks: []Block,
        filled: *usize,
        committed: *bool,
        clear_kind: bool,
        typing: bool,
    ) bool {
        const original_block = self.state.blocks[start];
        var rule_enter = false;
        if (typing and start == end and first.offset == last.offset and
            original_block.kind == md.paragraph and first.offset == tree.length(original_block.root) and
            std.mem.eql(u8, text, "\n") and !tree_contains_lf(original_block.root))
        {
            const source = self.allocator.alloc(u8, tree.length(original_block.root)) catch return false;
            defer self.allocator.free(source);
            tree.copy(original_block.root, source);
            rule_enter = md.is_rule(source);
        }
        var heading_kind: u32 = 0;
        if (typing and start == end and first.offset == last.offset and
            original_block.kind == 0 and first.offset >= 1 and first.offset <= 6 and
            std.mem.eql(u8, text, " ") and !tree_contains_lf(original_block.root))
        {
            heading_kind = first.offset;
            for (0..first.offset) |i| {
                if (tree.byte_at(original_block.root, i) != '#') {
                    heading_kind = 0;
                    break;
                }
            }
        }
        const insertion = if (heading_kind != 0) "" else text;

        const ids = self.allocator.alloc(u32, lines) catch return false;
        defer {
            if (!committed.*) {
                self.allocator.free(ids);
            }
        }

        const input = tree.from_bytes(self.allocator, insertion) catch return false;
        defer {
            tree.release(self.allocator, input);
        }
        for (self.state.blocks[0..start]) |b| {
            blocks[filled.*] = clone_block(b);
            filled.* += 1;
        }
        var segments = std.mem.splitScalar(u8, insertion, '\n');
        var offset: usize = 0;
        var line: usize = 0;
        var caret: Position = undefined;
        while (if (lines == 1) (if (line == 0) @as(?[]const u8, insertion) else null) else segments.next()) |segment| : (line += 1) {
            var root = tree.slice(self.allocator, input, offset, segment.len) catch return false;
            defer {
                tree.release(self.allocator, root);
            }
            if (line == 0 and heading_kind == 0) {
                const prefix = tree.slice(self.allocator, self.state.blocks[start].root, 0, first.offset) catch return false;
                defer {
                    tree.release(self.allocator, prefix);
                }

                const joined = tree.concat(self.allocator, prefix, root) catch return false;
                tree.release(self.allocator, root);
                root = joined;
            }

            const id: u32 = if (line == 0) first.id else @intCast(self.next_id + line - 1);
            if (line == lines - 1) {
                if (tree.length(root) > std.math.maxInt(u32)) {
                    return false;
                }
                caret = .{
                    .id = id,
                    .offset = @intCast(tree.length(root)),
                };

                const source = self.state.blocks[end].root;
                const suffix = tree.slice(self.allocator, source, last.offset, tree.length(source) - last.offset) catch return false;
                defer {
                    tree.release(self.allocator, suffix);
                }

                const joined = tree.concat(self.allocator, root, suffix) catch return false;
                tree.release(self.allocator, root);
                root = joined;
            }
            if (tree.length(root) > std.math.maxInt(u32)) {
                return false;
            }
            if (!clear_kind and self.state.blocks[start].kind == md.code) {
                const bytes = self.allocator.alloc(u8, tree.length(root)) catch return false;
                defer {
                    self.allocator.free(bytes);
                }
                tree.copy(root, bytes);
                var scan: md.Scanner = .{};
                const opener = self.allocator.alloc(u8, tree.length(self.state.blocks[start].prefix)) catch return false;
                defer {
                    self.allocator.free(opener);
                }
                tree.copy(self.state.blocks[start].prefix, opener);
                _ = scan.next(std.mem.trimEnd(u8, opener, "\n"));
                var content = std.mem.splitScalar(u8, bytes, '\n');
                while (content.next()) |content_line| {
                    _ = scan.next(content_line);
                    if (scan.marker == 0) {
                        return false;
                    }
                }
            }

            const original = self.state.blocks[start];
            const continuation = original.kind == md.quote or original.kind == md.unordered or original.kind == md.ordered;
            const keep = !clear_kind and heading_kind == 0 and (line == 0 or continuation);
            var marker: tree.Root = if (keep) tree.retain(original.prefix) else null;
            defer {
                tree.release(self.allocator, marker);
            }
            var ordinal: u32 = if (keep) original.ordinal else 0;
            if (keep and line > 0 and original.kind == md.ordered) {
                const next = std.math.add(usize, original.ordinal, line) catch return false;
                if (next > 999999999) {
                    return false;
                }
                ordinal = @intCast(next);
                const bytes = self.allocator.alloc(u8, tree.length(original.prefix)) catch return false;
                defer {
                    self.allocator.free(bytes);
                }
                tree.copy(original.prefix, bytes);
                var digit: usize = 0;
                while (digit < bytes.len and bytes[digit] == ' ') : (digit += 1) {}
                var delimiter = digit;
                while (delimiter < bytes.len and std.ascii.isDigit(bytes[delimiter])) : (delimiter += 1) {}
                const generated = std.fmt.allocPrint(self.allocator, "{s}{d}{s}", .{
                    bytes[0..digit],
                    ordinal,
                    bytes[delimiter..],
                }) catch return false;
                defer {
                    self.allocator.free(generated);
                }

                const replacement = tree.from_bytes(self.allocator, generated) catch return false;
                tree.release(self.allocator, marker);
                marker = replacement;
            }
            blocks[filled.*] = .{
                .id = id,

                .kind = if (heading_kind != 0) heading_kind else if (keep) original.kind else 0,

                .depth = if (keep) original.depth else 0,

                .ordinal = ordinal,

                .separator = if (line == 0) original.separator else if (continuation) 1 else 2,

                .root = tree.retain(root),

                .prefix = tree.retain(marker),

                .suffix = if (keep and line == 0) tree.retain(original.suffix) else null,
            };
            if (rule_enter and line == 0) {
                const converted = &blocks[filled.*];
                tree.release(self.allocator, converted.prefix);
                converted.prefix = converted.root;
                converted.root = null;
                converted.kind = md.rule;
            }
            filled.* += 1;
            ids[line] = id;
            offset += segment.len + 1;
        }
        for (self.state.blocks[end + 1 ..]) |b| {
            blocks[filled.*] = clone_block(b);
            filled.* += 1;
        }
        self.commit(.{
            .blocks = blocks,
            .selection = .{
                .anchor = caret,
                .focus = caret,
            },
        }, ids, lines != 1 or start != end or clear_kind or heading_kind != 0);
        self.next_id += lines - 1;
        committed.* = true;
        return true;
    }

    fn travel(self: *Editor, source: *[limit]Snapshot, source_len: *usize, dest: *[limit]Snapshot, dest_len: *usize) bool {
        if (source_len.* == 0) {
            return false;
        }

        const next = source[source_len.* - 1];
        const ids = self.allocator.alloc(u32, next.blocks.len) catch return false;
        for (next.blocks, ids) |b, *id| {
            id.* = b.id;
        }
        var shape = next.blocks.len != self.state.blocks.len;
        if (!shape) {
            for (next.blocks, self.state.blocks) |a, b| {
                if (a.id != b.id or a.kind != b.kind) {
                    shape = true;
                    break;
                }
            }
        }
        self.invalidate();
        self.push(dest, dest_len, self.state);
        source_len.* -= 1;
        self.state = next;
        self.allocator.free(self.changed_ids);
        self.changed_ids = ids;
        self.shape = shape;
        self.revision +%= 1;
        return true;
    }

    pub fn undo(self: *Editor) bool {
        return self.travel(&self.past, &self.past_len, &self.future, &self.future_len);
    }

    pub fn redo(self: *Editor) bool {
        return self.travel(&self.future, &self.future_len, &self.past, &self.past_len);
    }

    pub fn block_text(self: *Editor, index: usize) ?[]const u8 {
        if (index >= self.state.blocks.len) {
            return null;
        }

        const b = &self.state.blocks[index];
        if (b.cache) |c| {
            return c;
        }

        const c = self.allocator.alloc(u8, tree.length(b.root)) catch return null;
        tree.copy(b.root, c);
        b.cache = c;
        return c;
    }

    /// Exact normalized source, retaining imported delimiters and blank lines.
    pub fn source_text(self: *Editor) ?[]const u8 {
        return self.serialize();
    }

    fn needs_heading_space(b: Block) bool {
        const n = tree.length(b.prefix);
        return b.kind >= 1 and b.kind <= 6 and tree.length(b.root) != 0 and n != 0 and tree.byte_at(b.prefix, n - 1) == '#';
    }

    fn needs_code_newline(b: Block) bool {
        return b.kind == md.code and tree.length(b.root) != 0 and tree.length(b.suffix) != 0 and tree.byte_at(b.suffix, 0) != '\n';
    }

    pub fn serialize(self: *Editor) ?[]const u8 {
        if (self.markdown) |m| {
            return m;
        }
        var len: usize = 0;
        for (self.state.blocks, 0..) |b, i| {
            len = std.math.add(usize, len, tree.length(b.root)) catch return null;
            if (needs_code_newline(b)) {
                len = std.math.add(usize, len, 1) catch return null;
            }
            if (needs_heading_space(b)) {
                len = std.math.add(usize, len, 1) catch return null;
            }
            len = std.math.add(usize, len, tree.length(b.prefix) + tree.length(b.suffix) + @as(usize, if (b.kind >= 1 and b.kind <= 6 and b.prefix == null) b.kind + 1 else 0) + @as(usize, if (i == 0) 0 else b.separator)) catch return null;
        }

        const out = self.allocator.alloc(u8, len) catch return null;
        var pos: usize = 0;
        for (self.state.blocks, 0..) |b, i| {
            if (i != 0) {
                @memset(out[pos..][0..b.separator], '\n');
                pos += b.separator;
            }
            if (b.prefix != null) {
                const n = tree.length(b.prefix);
                tree.copy(b.prefix, out[pos..][0..n]);
                pos += n;
            } else if (b.kind >= 1 and b.kind <= 6) {
                @memset(out[pos..][0..b.kind], '#');
                pos += b.kind;
                out[pos] = ' ';
                pos += 1;
            }
            if (needs_heading_space(b)) {
                out[pos] = ' ';
                pos += 1;
            }

            const n = tree.length(b.root);
            tree.copy(b.root, out[pos..][0..n]);
            pos += n;
            if (needs_code_newline(b)) {
                out[pos] = '\n';
                pos += 1;
            }

            const suffix_len = tree.length(b.suffix);
            tree.copy(b.suffix, out[pos..][0..suffix_len]);
            pos += suffix_len;
        }
        self.markdown = out;
        return out;
    }
};

test "source preserves literal lines and terminal newline choices" {
    var editor: Editor = .{
        .allocator = std.testing.allocator,
    };
    defer {
        editor.deinit();
    }
    for ([_][]const u8{ "", "\n\n", "plain", "plain\n", "#", "#   ", "# ###", "###### title ######", "*literal*\n    # code\n#hashtag" }) |source| {
        try std.testing.expect(editor.import_markdown(source));
        try std.testing.expectEqualStrings(source, editor.source_text().?);
    }
    try std.testing.expect(editor.import_markdown("#"));
    try std.testing.expect(editor.replace_selection("title"));
    try std.testing.expectEqualStrings("# title", editor.source_text().?);
    try std.testing.expect(editor.set_kind(0, 2));
    try std.testing.expectEqualStrings("## title", editor.source_text().?);
    try std.testing.expect(editor.set_kind(0, 0));
    try std.testing.expectEqualStrings("title", editor.source_text().?);
}

test "headings-only import source edits and undo redo" {
    var editor: Editor = .{
        .allocator = std.testing.allocator,
    };
    defer {
        editor.deinit();
    }
    try std.testing.expect(editor.init());
    const old_id = editor.state.blocks[0].id;
    const source = "  ## \tTitle  ### \t\n```\n# literal\n```\nplain *literal*\n";
    try std.testing.expect(editor.import_markdown(source));
    const id = editor.state.blocks[0].id;
    try std.testing.expect(id != old_id);
    try std.testing.expectEqual(@as(usize, 4), editor.state.blocks.len);
    try std.testing.expectEqual(@as(u32, 2), editor.state.blocks[0].kind);
    try std.testing.expectEqual(@as(u32, 0), editor.state.blocks[2].kind);
    try std.testing.expectEqualStrings("Title", editor.block_text(0).?);
    try std.testing.expectEqualStrings(source, editor.source_text().?);
    try std.testing.expectEqual(id, editor.state.selection.focus.id);
    try std.testing.expectEqual(@as(u32, 0), editor.state.selection.focus.offset);
    try std.testing.expect(editor.replace_selection("New "));
    try std.testing.expectEqualStrings("  ## \tNew Title  ### \t\n```\n# literal\n```\nplain *literal*\n", editor.source_text().?);
    try std.testing.expect(editor.undo());
    try std.testing.expectEqualStrings(source, editor.source_text().?);
    try std.testing.expect(editor.undo());
    try std.testing.expectEqual(old_id, editor.state.blocks[0].id);
    try std.testing.expectEqualStrings("", editor.source_text().?);
    try std.testing.expect(editor.redo());
    try std.testing.expectEqual(id, editor.state.blocks[0].id);
    try std.testing.expectEqualStrings(source, editor.source_text().?);
    const revision = editor.revision;
    try std.testing.expect(!editor.import_markdown("bad\r\n"));
    try std.testing.expect(!editor.import_markdown("\xff"));
    try std.testing.expectEqual(revision, editor.revision);
    try std.testing.expect(editor.redo());
    try std.testing.expect(editor.import_markdown(""));
    try std.testing.expectEqual(@as(usize, 1), editor.state.blocks.len);
    try std.testing.expectEqualStrings("", editor.source_text().?);
}

fn import_allocation_failure(allocator: std.mem.Allocator) !void {
    var editor: Editor = .{
        .allocator = allocator,
    };
    defer {
        editor.deinit();
    }
    if (!editor.init()) {
        return error.OutOfMemory;
    }
    if (!editor.replace_selection("before")) {
        return error.OutOfMemory;
    }
    if (!editor.undo()) {
        return error.OutOfMemory;
    }

    const revision = editor.revision;
    const next_id = editor.next_id;
    const selection = editor.state.selection;
    if (!editor.import_markdown("## title ##\nparagraph\ncontinued\n\n> quote\n> continued\n- item\n  2. nested\n~~~\n# code\n~~~\n")) {
        try std.testing.expectEqual(revision, editor.revision);
        try std.testing.expectEqual(next_id, editor.next_id);
        try std.testing.expectEqualDeep(selection, editor.state.selection);
        try std.testing.expectEqual(@as(usize, 1), editor.future_len);
        try std.testing.expectEqual(@as(usize, 1), editor.state.blocks.len);
        try std.testing.expectEqual(@as(usize, 0), tree.length(editor.state.blocks[0].root));
        return error.OutOfMemory;
    }
    try std.testing.expectEqual(@as(usize, 0), editor.future_len);
}

test "import allocation rollback" {
    try std.testing.checkAllAllocationFailures(std.testing.allocator, import_allocation_failure, .{});
}

test "M4 blocks metadata and exact source" {
    var e: Editor = .{
        .allocator = std.testing.allocator,
    };
    defer {
        e.deinit();
    }

    const source = "alpha\nbeta\n\n> one\n> two\n\n- item\n  03) nested\n\n```zig\nx\ny\n```\n";
    try std.testing.expect(e.import_markdown(source));
    try std.testing.expectEqualStrings(source, e.source_text().?);
    try std.testing.expectEqualStrings("alpha\nbeta", e.block_text(0).?);
    try std.testing.expectEqual(@as(u32, 7), e.state.blocks[2].kind);
    try std.testing.expectEqual(@as(u32, 1), e.state.blocks[2].depth);
    try std.testing.expectEqual(@as(u32, 9), e.state.blocks[5].kind);
    try std.testing.expectEqual(@as(u32, 10), e.state.blocks[6].kind);
    try std.testing.expectEqual(@as(u32, 1), e.state.blocks[6].depth);
    try std.testing.expectEqual(@as(u32, 3), e.state.blocks[6].ordinal);
    try std.testing.expectEqualStrings("x\ny", e.block_text(8).?);
    const id = e.state.blocks[8].id;
    try std.testing.expect(e.replace_range(.{
        .anchor = .{
            .id = id,
            .offset = 1,
        },
        .focus = .{
            .id = id,
            .offset = 1,
        },
    }, "\nnew"));
    try std.testing.expectEqualStrings("x\nnew\ny", e.block_text(8).?);
    try std.testing.expectEqual(@as(usize, 10), e.state.blocks.len);
    try std.testing.expect(e.undo());
    try std.testing.expectEqualStrings(source, e.source_text().?);
    try std.testing.expect(e.redo());
    try std.testing.expect(!e.replace_range(.{
        .anchor = .{
            .id = id,
        },
        .focus = .{
            .id = id,
        },
    }, "```\n"));
}

test "paragraph Enter and empty fence edits serialize safely" {
    var e: Editor = .{
        .allocator = std.testing.allocator,
    };
    defer {
        e.deinit();
    }
    try std.testing.expect(e.import_markdown("ab\ncd"));
    const id = e.state.blocks[0].id;
    try std.testing.expect(e.replace_range(.{
        .anchor = .{
            .id = id,
            .offset = 1,
        },
        .focus = .{
            .id = id,
            .offset = 1,
        },
    }, "\n"));
    try std.testing.expectEqualStrings("a\n\nb\ncd", e.source_text().?);
    try std.testing.expect(e.undo());
    try std.testing.expectEqualStrings("ab\ncd", e.source_text().?);
    try std.testing.expect(e.import_markdown("```\n```"));
    try std.testing.expectEqualStrings("", e.block_text(0).?);
    try std.testing.expect(e.replace_selection("hello\nworld"));
    try std.testing.expectEqualStrings("```\nhello\nworld\n```", e.source_text().?);
}

fn block_edit_allocation_failure(allocator: std.mem.Allocator) !void {
    var e: Editor = .{
        .allocator = allocator,
    };
    defer {
        e.deinit();
    }
    if (!e.import_markdown("~~~zig\nabc\n~~~\n\nend")) {
        return error.OutOfMemory;
    }

    const revision = e.revision;
    const next_id = e.next_id;
    const selection = e.state.selection;
    if (!e.replace_selection("line\n")) {
        try std.testing.expectEqual(revision, e.revision);
        try std.testing.expectEqual(next_id, e.next_id);
        try std.testing.expectEqualDeep(selection, e.state.selection);
        try std.testing.expectEqual(@as(usize, 3), tree.length(e.state.blocks[0].root));
        return error.OutOfMemory;
    }
    if (!e.undo()) {
        return error.OutOfMemory;
    }
    if (!e.redo()) {
        return error.OutOfMemory;
    }
}

test "structured edits allocation rollback" {
    try std.testing.checkAllAllocationFailures(std.testing.allocator, block_edit_allocation_failure, .{});
}

test "quote lines expose plain text and continue markers" {
    var e: Editor = .{
        .allocator = std.testing.allocator,
    };
    defer {
        e.deinit();
    }

    const source = "  > > alpha\n> beta\n>";
    try std.testing.expect(e.import_markdown(source));
    try std.testing.expectEqual(@as(usize, 3), e.state.blocks.len);
    try std.testing.expectEqualStrings("alpha", e.block_text(0).?);
    try std.testing.expectEqualStrings("beta", e.block_text(1).?);
    try std.testing.expectEqualStrings(source, e.source_text().?);
    try std.testing.expect(e.replace_selection("new\n"));
    try std.testing.expectEqualStrings("  > > new\n  > > alpha\n> beta\n>", e.source_text().?);
    try std.testing.expectEqual(@as(u32, 2), e.state.blocks[1].depth);
    try std.testing.expectEqual(@as(u32, 0), e.state.selection.focus.offset);
    try std.testing.expect(e.undo());
    try std.testing.expectEqualStrings(source, e.source_text().?);
    try std.testing.expect(e.redo());
}

test "list continuation numbering delimiter and empty Enter exit" {
    var e: Editor = .{
        .allocator = std.testing.allocator,
    };
    defer {
        e.deinit();
    }
    for ([_][]const u8{ "  009) ab", "  + ab", "> ab" }, [_][]const u8{ "  009) a\n  10) b", "  + a\n  + b", "> a\n> b" }) |source, expected| {
        try std.testing.expect(e.import_markdown(source));
        const id = e.state.blocks[0].id;
        try std.testing.expect(e.replace_range(.{
            .anchor = .{
                .id = id,
                .offset = 1,
            },
            .focus = .{
                .id = id,
                .offset = 1,
            },
        }, "\n"));
        try std.testing.expectEqualStrings(expected, e.source_text().?);
        try std.testing.expectEqual(e.state.blocks[0].kind, e.state.blocks[1].kind);
        try std.testing.expectEqual(e.state.blocks[0].depth, e.state.blocks[1].depth);
        if (e.state.blocks[1].kind == md.ordered) {
            try std.testing.expectEqual(@as(u32, 10), e.state.blocks[1].ordinal);
        }
    }
    for ([_][]const u8{ "> ", "  - ", "2. " }) |source| {
        try std.testing.expect(e.import_markdown(source));
        try std.testing.expect(e.replace_selection("\n"));
        try std.testing.expectEqual(@as(usize, 1), e.state.blocks.len);
        try std.testing.expectEqual(@as(u32, 0), e.state.blocks[0].kind);
        try std.testing.expectEqualStrings("", e.source_text().?);
        try std.testing.expect(e.undo());
        try std.testing.expectEqualStrings(source, e.source_text().?);
        try std.testing.expect(e.redo());
        try std.testing.expectEqualStrings("", e.source_text().?);
    }
}

test "whole structured range delete but partial cross edits reject" {
    var e: Editor = .{
        .allocator = std.testing.allocator,
    };
    defer {
        e.deinit();
    }

    const source = "> quote\n- item\n```\ncode\n```";
    try std.testing.expect(e.import_markdown(source));
    const first = e.state.blocks[0].id;
    const last = e.state.blocks[2].id;
    try std.testing.expect(!e.replace_range(.{
        .anchor = .{
            .id = first,
            .offset = 1,
        },
        .focus = .{
            .id = last,
            .offset = 4,
        },
    }, ""));
    try std.testing.expect(e.replace_range(.{
        .anchor = .{
            .id = first,
        },
        .focus = .{
            .id = last,
            .offset = 4,
        },
    }, ""));
    try std.testing.expectEqualStrings("", e.source_text().?);
    try std.testing.expectEqual(@as(u32, 0), e.state.blocks[0].kind);
    try std.testing.expect(e.undo());
    try std.testing.expectEqualStrings(source, e.source_text().?);
}

fn list_edit_allocation_failure(allocator: std.mem.Allocator) !void {
    var e: Editor = .{
        .allocator = allocator,
    };
    defer {
        e.deinit();
    }
    if (!e.import_markdown("  009) abc")) {
        return error.OutOfMemory;
    }

    const revision = e.revision;
    const next_id = e.next_id;
    if (!e.replace_selection("a\nb\nc")) {
        try std.testing.expectEqual(revision, e.revision);
        try std.testing.expectEqual(next_id, e.next_id);
        try std.testing.expectEqual(@as(usize, 1), e.state.blocks.len);
        try std.testing.expectEqual(@as(u32, 9), e.state.blocks[0].ordinal);
        return error.OutOfMemory;
    }
}

test "ordered continuation allocation rollback" {
    try std.testing.checkAllAllocationFailures(std.testing.allocator, list_edit_allocation_failure, .{});
}

test "empty backtick and tilde fences preserve closing line through edits" {
    var e: Editor = .{
        .allocator = std.testing.allocator,
    };
    defer {
        e.deinit();
    }
    for ([_][]const u8{ "```", "~~~" }) |marker| {
        const source = try std.fmt.allocPrint(std.testing.allocator, "{s}\n{s}", .{
            marker,
            marker,
        });
        defer {
            std.testing.allocator.free(source);
        }
        for ([_][]const u8{ "hello", "\n", "hello\n", "\nhello", "hello\nworld" }) |content| {
            try std.testing.expect(e.import_markdown(source));
            try std.testing.expectEqualStrings("", e.block_text(0).?);
            try std.testing.expectEqualStrings(source, e.source_text().?);
            const id = e.state.blocks[0].id;
            try std.testing.expect(e.replace_selection(content));
            const expected = try std.fmt.allocPrint(std.testing.allocator, "{s}\n{s}\n{s}", .{
                marker,
                content,
                marker,
            });
            defer {
                std.testing.allocator.free(expected);
            }
            try std.testing.expectEqualStrings(expected, e.source_text().?);
            try std.testing.expectEqualStrings(content, e.block_text(0).?);
            try std.testing.expectEqual(@as(usize, 1), e.state.blocks.len);
            try std.testing.expectEqual(@as(u32, @intCast(content.len)), e.state.selection.focus.offset);
            try std.testing.expect(e.undo());
            try std.testing.expectEqualStrings(source, e.source_text().?);
            try std.testing.expect(e.redo());
            try std.testing.expectEqualStrings(expected, e.source_text().?);
            try std.testing.expect(e.replace_range(.{
                .anchor = .{
                    .id = id,
                },
                .focus = .{
                    .id = id,
                    .offset = @intCast(content.len),
                },
            }, ""));
            try std.testing.expectEqualStrings(source, e.source_text().?);
            try std.testing.expect(e.import_markdown(expected));
            try std.testing.expectEqualStrings(content, e.block_text(0).?);
            try std.testing.expectEqualStrings(expected, e.source_text().?);
        }
    }
}

test "whitespace-only lines separate paragraphs without losing source" {
    var e: Editor = .{
        .allocator = std.testing.allocator,
    };
    defer {
        e.deinit();
    }

    const source = "alpha\nbeta\n \t \n\t\ngamma\ndelta\n  ";
    try std.testing.expect(e.import_markdown(source));
    try std.testing.expectEqual(@as(usize, 5), e.state.blocks.len);
    for ([_][]const u8{ "alpha\nbeta", " \t ", "\t", "gamma\ndelta", "  " }, 0..) |text, i| {
        try std.testing.expectEqualStrings(text, e.block_text(i).?);
    }
    try std.testing.expectEqualStrings(source, e.source_text().?);
    try std.testing.expect(e.replace_selection("new "));
    try std.testing.expectEqualStrings("new alpha\nbeta\n \t \n\t\ngamma\ndelta\n  ", e.source_text().?);
    try std.testing.expect(e.undo());
    try std.testing.expectEqualStrings(source, e.source_text().?);
}