tiny.ui.tree

1pub const Error = error{CapacityOverflow};

1/// `Map` finds a node index by node id through open addressing with linear probing.2/// It stores node indices, not ids. `lookup` and `insert` read the id through the node array3/// passed to them, so every call must pass the array the map was filled from.4pub const Map = struct {5    /// `Map.slots` must have a power-of-two length, which `lookup` and `insert` assert.6    slots: []u32 = &.{},7    /// `Map.count` is the number of occupied slots.8    count: u32 = 0,910    /// `reset` empties every slot and sets `count` to 0.11    pub fn reset(self: *Map) void {12        @memset(self.slots, absent);13        self.count = 0;14    }1516    /// `lookup` returns the index of the node whose id equals `id`, or null.17    /// A map with no slots answers null. Each call probes at most `slots.len` slots.18    pub fn lookup(self: *const Map, nodes: []const Node, id: u64) ?u32 {19        if (self.slots.len == 0) return null;20        std.debug.assert(std.math.isPowerOfTwo(self.slots.len));21        const mask = self.slots.len - 1;22        var index = @as(usize, hash(id)) & mask;23        var probe: usize = 0;24        while (probe < self.slots.len) : (probe += 1) {25            const slot = self.slots[index];26            if (slot == absent) return null;27            std.debug.assert(slot - 1 < nodes.len);28            if (nodes[slot - 1].id == id) return slot - 1;29            index = (index + 1) & mask;30        }31        return null;32    }3334    /// `insert` adds node `index` under that node's id and returns true. When a node35    /// with the same id is already present, it returns false and leaves the map unchanged.36    /// It asserts that a free slot remains.37    pub fn insert(self: *Map, nodes: []const Node, index: u32) bool {38        std.debug.assert(self.slots.len > 0);39        std.debug.assert(std.math.isPowerOfTwo(self.slots.len));40        std.debug.assert(index < nodes.len);41        const id = nodes[index].id;42        if (self.lookup(nodes, id) != null) return false;43        std.debug.assert(self.count < self.slots.len);44        const mask = self.slots.len - 1;45        var slot = @as(usize, hash(id)) & mask;46        var probe: usize = 0;47        while (probe < self.slots.len) : (probe += 1) {48            if (self.slots[slot] == absent) {49                self.slots[slot] = index + 1;50                self.count += 1;51                return true;52            }53            slot = (slot + 1) & mask;54        }55        unreachable;56    }57};

1pub const Outcome = struct {2    /// `Outcome.bytes` is the length of the envelope written into the block. It is the publish3    /// buffer's length when no node carries the `retained` flag, and the full block size otherwise.4    bytes: u32 = 0,5    /// `Outcome.dirty` is the number of indices written to the beginning of `Scratch.place`,6    /// each naming a dirty node's position in the newly written preorder node array.7    dirty: u32 = 0,8};

1/// `Scratch` holds the work arrays for a splice, which writes a new preorder node array in the2/// order of the flat tree. While the splice emits nodes, `Scratch.place` maps publish indices to3/// written indices. After the emit and trailer phases, the splice reuses that slice for the4/// compact dirty index list, which `Store.dirty` returns as new preorder indices. After the5/// splice, `Scratch.dirty` holds one packed prior entry per written node: the low 31 bits name6/// the node's index in the previously retained tree, the high bit says its revision changed or7/// its id is new, and all low bits set means there was no retained node. The correspondence8/// describes only the immediately preceding retained tree, and remains valid until the next9/// publish modifies the scratch arrays.10pub const Scratch = struct {11    place: []u32,12    atom_remap: []u32,13    text_remap: []u32,14    dirty: []u32,15};

1/// `Accepted` is the result of an accepted publish.2pub const Accepted = struct {3    /// `Accepted.dirty` is the number of nodes `Store.dirty` lists.4    dirty: u32 = 0,5    /// `Accepted.unchanged` is true when that number is 0.6    unchanged: bool = false,7};

1/// `Report` is what `survey` returns for an accepted publish.2pub const Report = struct {3    /// `Report.view` is the bound publish.4    view: View,5    /// `Report.reuses_retained` is true when at least one node carries the `retained` flag.6    reuses_retained: bool = false,7    /// `Report.spliced` holds the counts described for `Spliced`.8    spliced: Spliced = .{},9};

1/// `Retained` describes the tree a publish is admitted against.2pub const Retained = struct {3    /// `Retained.view` is that tree.4    view: View = .{},5    /// `Retained.map` is its identity map.6    map: Map = .{},7    /// `Retained.revision` is its header revision.8    revision: u64 = 0,9    /// `Retained.present` is false when no tree is retained, which is the default.10    present: bool = false,11    assets: ?*const asset.Registry = null,12};

1/// `Spliced` counts what the splice adds beyond the publish's own tables when it2/// copies retained subtrees in.3/// `Spliced.nodes` and `Spliced.classes` are exact. The other counts are upper bounds,4/// because the survey counts absent atoms that the splice skips, shared atoms and texts5/// that the splice copies once, and the whole retained string table for every placeholder.6pub const Spliced = struct {7    nodes: u64 = 0,8    declarations: u64 = 0,9    classes: u64 = 0,10    texts: u64 = 0,11    runs: u64 = 0,12    atoms: u64 = 0,13    strings: u64 = 0,14};

1pub const BindError = error{2    BufferTooSmall,3    BufferLengthMismatch,4    MagicMismatch,5    AbiVersionMismatch,6    NodeSizeMismatch,7    SpanOutOfBounds,8    SpanMisaligned,9};

1/// `Children` iterates over the direct children of one node, in preorder.2pub const Children = struct {3    nodes: []const Node,4    /// `Children.last` is the index of the last descendant of the node whose children are walked.5    last: u32,6    /// `Children.cursor` is the index the next call examines.7    cursor: u32,89    /// `Children.next` returns the index of the next direct child, or null after the last one.10    /// Each call jumps over that child's whole subtree through its `subtree_count`,11    /// so a walk takes one step per child and never visits a grandchild.12    pub fn next(self: *Children) ?u32 {13        if (self.cursor > self.last) return null;14        const found = self.cursor;15        std.debug.assert(found < self.nodes.len);16        const span = self.nodes[found].subtree_count;17        std.debug.assert(found + span <= self.last);18        self.cursor = found + 1 + span;19        return found;20    }21};

1/// `arrays` lists the ten tables in the order they sit in a block.2pub const arrays = [_]Array{3    .{ .name = "nodes", .limit = "nodes", .bytes = @sizeOf(abi.Node), .alignment = 8 },4    .{ .name = "declarations", .limit = "declarations", .bytes = 16, .alignment = 4 },5    .{ .name = "classes", .limit = "classes", .bytes = 4, .alignment = 4 },6    .{ .name = "texts", .limit = "texts", .bytes = @sizeOf(abi.TextRecord), .alignment = 4 },7    .{ .name = "runs", .limit = "runs", .bytes = @sizeOf(abi.TextRun), .alignment = 4 },8    .{ .name = "relations", .limit = "relations", .bytes = @sizeOf(abi.Relation), .alignment = 4 },9    .{ .name = "atoms", .limit = "atoms", .bytes = @sizeOf(abi.Atom), .alignment = 4 },10    .{ .name = "strings", .limit = "string_bytes", .bytes = 1, .alignment = 1 },11    .{12        .name = "solved_roots",13        .limit = "solved_roots",14        .bytes = @sizeOf(abi.SolvedRoot),15        .alignment = 4,16    },17    .{18        .name = "solved_rects",19        .limit = "solved_rects",20        .bytes = @sizeOf(abi.Rect),21        .alignment = 4,22    },23};

1/// `slotCount` returns the smallest power of two at least twice `nodes`. It returns 02/// for zero nodes and when that power of two does not fit in 32 bits.3pub fn slotCount(nodes: u32) u32 {4    if (nodes == 0) return 0;5    const wanted = std.math.mul(u32, nodes, 2) catch return 0;6    return std.math.ceilPowerOfTwo(u32, wanted) catch 0;7}

1/// `absent` is 0, the value of an empty slot.2/// An occupied slot stores its node index plus 1.3pub const absent: u32 = 0;

1pub const prior_absent: u32 = 0x7fff_ffff;

1pub const prior_dirty: u32 = 0x8000_0000;

1/// `splice` is exported as `tree.graft`. It writes an accepted publish into `block` and leaves2/// `block_map` indexing the written nodes. It takes the `Report` that `admit` returned for that3/// publish and the same `Retained`. When no node carries the `retained` flag, it copies the4/// publish bytes whole and keeps the map `admit` filled, so `block_map` must be that map. It marks5/// dirty each node whose id the retained tree lacks or holds at another revision, and skips the6/// descendants of a node whose revision matches. Otherwise it rebuilds the tree. It copies the7/// publish tables, replaces each placeholder with the retained subtree of the same id, copies that8/// subtree's declarations, classes, atoms, texts, and runs with their indices remapped, and9/// rebuilds `block_map`. It marks dirty each other node whose id the retained tree lacks or holds10/// at another revision, and never a node of a retained subtree. It returns no error, because11/// `admit` already checked every bound.12pub fn splice(13    block: []align(8) u8,14    block_map: *Map,15    capacity: Capacity,16    report: Report,17    retained: Retained,18    scratch: Scratch,19) Outcome {20    if (!report.reuses_retained) return bulk(block, block_map, report.view, retained, scratch);21    var sink = Sink{22        .block = block,23        .capacity = capacity,24        .atom_remap = scratch.atom_remap,25        .text_remap = scratch.text_remap,26    };27    return rebuild(&sink, block_map, report.view, retained, scratch);28}

1/// `storage_alignment` is the byte alignment of a `Store`'s allocation and of every buffer2/// `Store.publish` accepts.3pub const storage_alignment: usize = 8;

1/// `Error` is every rejection that `survey` and `Store.publish` return.2/// It includes every `BindError`.3pub const Error = view_mod.BindError || error{4    PublishTooLarge,5    NodeLimitExceeded,6    DeclarationLimitExceeded,7    ClassLimitExceeded,8    TextLimitExceeded,9    RunLimitExceeded,10    RelationLimitExceeded,11    AtomLimitExceeded,12    StringLimitExceeded,13    SolvedRootLimitExceeded,14    SolvedRectLimitExceeded,15    SubtreeExtentOutOfBounds,16    ParentNotAncestor,17    RootParentMismatch,18    RootSubtreeIncomplete,19    DepthExceeded,20    DuplicateNodeId,21    StaleRetainedSubtree,22    RetainedSubtreeNotEmpty,23    AtomIndexOutOfBounds,24    AtomTextOutOfBounds,25    DeclarationIndexOutOfBounds,26    ClassIndexOutOfBounds,27    TextIndexOutOfBounds,28    RunIndexOutOfBounds,29    TextRunEmpty,30    TextRunsUnordered,31    TextRunsOverlap,32    TextRunOutOfBounds,33    TextRunSplitsScalar,34    TextRunPropertyNotAllowed,35    TextNotUtf8,36    RelationsUnsorted,37    RelationNodeOutOfBounds,38    SolvedRootNotSolved,39    SolvedRootNodeOutOfBounds,40    SolvedRootsUnordered,41    SolvedRectsOutOfBounds,42    SolvedNodeWithoutRoot,43    RetainedSolvedSubtree,44    StaleAsset,45};

1/// `survey` is exported as `tree.admit`. It checks one publish buffer against `limits` and2/// `retained` and returns a `Report` or the first rejection. It checks the buffer size, the header,3/// and the spans, then the table quotas. `survey` checks the declaration table for asset handles4/// after quota checks and before it resets scratch or walks nodes. It rejects a stale generation5/// with `error.StaleAsset`. It then walks the node table once, then loops over the6/// atoms, the relations, and the solved roots. When a node reuses a retained subtree, it last7/// checks the quotas again with those subtrees counted. `survey` reads the buffer and writes only8/// `scratch`. `survey` calls `scratch.reset()` only after the size check, `bind`, and9/// `surveyQuotas` have passed, and the node walk then inserts one node at a time. A rejection10/// can leave `scratch` untouched, partly filled, or wholly filled, and only an accepted publish11/// leaves every node of the publish in it.12/// `scratch` needs a power-of-two slot count at least as large as the publish's node count.13pub fn survey(14    bytes: []align(8) const u8,15    limits: Limits,16    retained: Retained,17    scratch: *Map,18) Error!Report {19    if (bytes.len > limitsBytes(limits)) return error.PublishTooLarge;20    const view = try view_mod.bind(bytes);21    try surveyQuotas(view, limits);22    try surveyAssets(view, retained.assets);23    scratch.reset();24    var report = Report{ .view = view };25    const solved_nodes = try surveyNodes(view, retained, scratch, &report);26    try surveyAtoms(view);27    try surveyRelations(view);28    try surveySolved(view, solved_nodes);29    if (report.reuses_retained) try surveyMerge(view, limits, report);30    return report;31}

1/// `bind` runs `readHeader`, checks each of the ten table spans, and returns a `View`.2/// It does not check the node tree, the indices inside records, or atom ranges. `admit` checks3/// those. The `View` accessors assert those bounds rather than return errors, so they belong on4/// a buffer `admit` accepted, such as the block `Store.retained` binds.5pub fn bind(bytes: []align(8) const u8) BindError!View {6    const header = try readHeader(bytes);7    return .{8        .bytes = bytes,9        .header = header,10        .nodes = try sliceOf(Node, bytes, header.nodes),11        .declarations = try sliceOf(Declaration, bytes, header.declarations),12        .classes = try sliceOf(u32, bytes, header.classes),13        .texts = try sliceOf(TextRecord, bytes, header.texts),14        .runs = try sliceOf(TextRun, bytes, header.runs),15        .relations = try sliceOf(Relation, bytes, header.relations),16        .atoms = try sliceOf(Atom, bytes, header.atoms),17        .strings = try sliceOf(u8, bytes, header.strings),18        .solved_roots = try sliceOf(SolvedRoot, bytes, header.solved_roots),19        .solved_rects = try sliceOf(Rect, bytes, header.solved_rects),20    };21}

1/// `readHeader` copies the 152 byte header out of the buffer and reads no table.2/// It checks, in order, that the buffer holds a whole header (`error.BufferTooSmall`), then3/// `magic` (`error.MagicMismatch`), `abi_version` (`error.AbiVersionMismatch`), `node_bytes`4/// (`error.NodeSizeMismatch`), and `buffer_bytes` (`error.BufferLengthMismatch`).5pub fn readHeader(bytes: []align(8) const u8) BindError!Header {6    if (bytes.len < abi.header_bytes) return error.BufferTooSmall;7    const header = std.mem.bytesToValue(Header, bytes[0..abi.header_bytes]);8    if (header.magic != abi.magic) return error.MagicMismatch;9    if (header.abi_version != abi.abi_version) return error.AbiVersionMismatch;10    if (header.node_bytes != @sizeOf(Node)) return error.NodeSizeMismatch;11    if (header.buffer_bytes != bytes.len) return error.BufferLengthMismatch;12    return header;13}

1/// `childCount` returns the number of direct children of node `index` by walking them.2pub fn childCount(nodes: []const Node, index: u32) u32 {3    var walk = children(nodes, index);4    var count: u32 = 0;5    while (walk.next()) |_| count += 1;6    return count;7}

1/// `children` returns the `Children` iterator for node `index`.2/// It asserts that `index` and that node's subtree lie inside `nodes`.3pub fn children(nodes: []const Node, index: u32) Children {4    std.debug.assert(index < nodes.len);5    const span = nodes[index].subtree_count;6    std.debug.assert(index + span < nodes.len);7    return .{ .nodes = nodes, .last = index + span, .cursor = index + 1 };8}

1/// `subtree` returns node `index` followed by all of its descendants,2/// as one slice of `subtree_count + 1` nodes.3pub fn subtree(nodes: []const Node, index: u32) []const Node {4    std.debug.assert(index < nodes.len);5    const span = nodes[index].subtree_count;6    std.debug.assert(index + span < nodes.len);7    return nodes[index .. index + span + 1];8}

1pub const tree = @import("tree/root.zig");

1//! Retained tree namespace whose `Store` retains one accepted tree in one of two envelope blocks.2//!3//! `admit` is the admission survey rejecting before any retained byte changes.4//! `bind` returns a `View` over the buffer whose accessors copy no table data.5//! `readHeader` copies only the 152 byte header.67const capacity = @import("capacity.zig");8const map = @import("map.zig");9const splice = @import("splice.zig");10const store = @import("store.zig");11const survey = @import("survey.zig");12const view = @import("view.zig");13const walk = @import("walk.zig");1415pub const Capacity = capacity.Capacity;16pub const Limits = capacity.Limits;17pub const CapacityError = capacity.Error;18pub const arrays = capacity.arrays;19pub const slotCount = capacity.slotCount;2021pub const Map = map.Map;22pub const map_absent = map.absent;2324pub const View = view.View;25pub const prior_dirty = splice.prior_dirty;26pub const prior_absent = splice.prior_absent;27pub const BindError = view.BindError;28pub const bind = view.bind;29pub const readHeader = view.readHeader;3031pub const Error = survey.Error;32pub const Report = survey.Report;33pub const Retained = survey.Retained;34pub const Spliced = survey.Spliced;35pub const admit = survey.survey;3637pub const Scratch = splice.Scratch;38pub const Outcome = splice.Outcome;39pub const graft = splice.splice;4041pub const Accepted = store.Accepted;42pub const Store = store.Store;43pub const storage_alignment = store.storage_alignment;4445pub const Children = walk.Children;46pub const children = walk.children;47pub const subtree = walk.subtree;48pub const childCount = walk.childCount;