lib/ui/src/tree/view.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 const abi = @import("../abi/root.zig");
4 const walk = @import("walk.zig");
5 const map = @import("map.zig");
6
7 const Atom = abi.Atom;
8 const Declaration = abi.Declaration;
9 const Header = abi.Header;
10 const Node = abi.Node;
11 const Rect = abi.Rect;
12 const Relation = abi.Relation;
13 const SolvedRoot = abi.SolvedRoot;
14 const Span = abi.Span;
15 const TextRecord = abi.TextRecord;
16 const TextRun = abi.TextRun;
17
18 pub const BindError = error{
19 BufferTooSmall,
20 BufferLengthMismatch,
21 MagicMismatch,
22 AbiVersionMismatch,
23 NodeSizeMismatch,
24 SpanOutOfBounds,
25 SpanMisaligned,
26 };
27
28 /// `View` holds typed slices over one publish buffer. In a view from `bind`, every nonempty
29 /// table field is a slice into `bytes`, so the view owns no memory. The default `View` is empty.
30 pub const View = struct {
31 /// `View.bytes` is the whole buffer.
32 bytes: []align(8) const u8 = &.{},
33 /// `View.header` is a copy of its 152 byte header.
34 header: Header = .{},
35 nodes: []const Node = &.{},
36 /// `View.identity` points to the `Store`'s current id-to-index map. `View.prior` points to the
37 /// packed correspondence from the most recent publish. A `View` made by `bind` or by a caller
38 /// can omit identity and prior: their defaults are null and empty. The correspondence describes
39 /// only the immediately preceding retained tree, and remains valid until the next publish
40 /// modifies the scratch arrays.
41 identity: ?*const map.Map = null,
42 prior: []const u32 = &.{},
43 declarations: []const Declaration = &.{},
44 classes: []const u32 = &.{},
45 texts: []const TextRecord = &.{},
46 runs: []const TextRun = &.{},
47 relations: []const Relation = &.{},
48 atoms: []const Atom = &.{},
49 strings: []const u8 = &.{},
50 solved_roots: []const SolvedRoot = &.{},
51 solved_rects: []const Rect = &.{},
52
53 /// `View.text` returns the bytes of one atom from the string table. It returns an
54 /// empty slice for `atom_absent`.
55 pub fn text(self: View, atom: u32) []const u8 {
56 if (atom == abi.atom_absent) return &.{};
57 std.debug.assert(atom < self.atoms.len);
58 const record = self.atoms[atom];
59 std.debug.assert(record.offset + record.len <= self.strings.len);
60 return self.strings[record.offset..][0..record.len];
61 }
62
63 /// `View.declarationsOf` returns the declarations of node `node`, as a slice into
64 /// the buffer.
65 pub fn declarationsOf(self: View, node: u32) []const Declaration {
66 std.debug.assert(node < self.nodes.len);
67 const record = self.nodes[node];
68 const first = record.declaration_first;
69 std.debug.assert(first + record.declaration_count <= self.declarations.len);
70 return self.declarations[first..][0..record.declaration_count];
71 }
72
73 /// `View.classesOf` returns the class entries of node `node`.
74 pub fn classesOf(self: View, node: u32) []const u32 {
75 std.debug.assert(node < self.nodes.len);
76 const record = self.nodes[node];
77 std.debug.assert(record.class_first + record.class_count <= self.classes.len);
78 return self.classes[record.class_first..][0..record.class_count];
79 }
80
81 /// `View.textOf` returns a pointer to the text record of node `node`, or null
82 /// when the node has no text.
83 pub fn textOf(self: View, node: u32) ?*const TextRecord {
84 std.debug.assert(node < self.nodes.len);
85 const index = self.nodes[node].text;
86 if (index == abi.text_absent) return null;
87 std.debug.assert(index < self.texts.len);
88 return &self.texts[index];
89 }
90
91 /// `View.runsOf` returns the runs of one text record, as a slice into the buffer.
92 pub fn runsOf(self: View, record: *const TextRecord) []const TextRun {
93 std.debug.assert(record.run_first + record.run_count <= self.runs.len);
94 return self.runs[record.run_first..][0..record.run_count];
95 }
96
97 /// `View.children` returns an iterator over the direct children of node `node`.
98 pub fn children(self: View, node: u32) walk.Children {
99 return walk.children(self.nodes, node);
100 }
101
102 /// `View.subtree` returns node `node` followed by all of its descendants.
103 pub fn subtree(self: View, node: u32) []const Node {
104 return walk.subtree(self.nodes, node);
105 }
106
107 /// `View.solvedRectsOf` returns the `subtree_count + 1` rects of one solved root,
108 /// starting at its `rect_first`.
109 pub fn solvedRectsOf(self: View, root: SolvedRoot) []const Rect {
110 std.debug.assert(root.node < self.nodes.len);
111 const span = self.nodes[root.node].subtree_count + 1;
112 std.debug.assert(root.rect_first + span <= self.solved_rects.len);
113 return self.solved_rects[root.rect_first..][0..span];
114 }
115 };
116
117 /// `readHeader` copies the 152 byte header out of the buffer and reads no table.
118 /// It checks, in order, that the buffer holds a whole header (`error.BufferTooSmall`), then
119 /// `magic` (`error.MagicMismatch`), `abi_version` (`error.AbiVersionMismatch`), `node_bytes`
120 /// (`error.NodeSizeMismatch`), and `buffer_bytes` (`error.BufferLengthMismatch`).
121 pub fn readHeader(bytes: []align(8) const u8) BindError!Header {
122 if (bytes.len < abi.header_bytes) return error.BufferTooSmall;
123 const header = std.mem.bytesToValue(Header, bytes[0..abi.header_bytes]);
124 if (header.magic != abi.magic) return error.MagicMismatch;
125 if (header.abi_version != abi.abi_version) return error.AbiVersionMismatch;
126 if (header.node_bytes != @sizeOf(Node)) return error.NodeSizeMismatch;
127 if (header.buffer_bytes != bytes.len) return error.BufferLengthMismatch;
128 return header;
129 }
130
131 /// `bind` runs `readHeader`, checks each of the ten table spans, and returns a `View`.
132 /// It does not check the node tree, the indices inside records, or atom ranges. `admit` checks
133 /// those. The `View` accessors assert those bounds rather than return errors, so they belong on
134 /// a buffer `admit` accepted, such as the block `Store.retained` binds.
135 pub fn bind(bytes: []align(8) const u8) BindError!View {
136 const header = try readHeader(bytes);
137 return .{
138 .bytes = bytes,
139 .header = header,
140 .nodes = try sliceOf(Node, bytes, header.nodes),
141 .declarations = try sliceOf(Declaration, bytes, header.declarations),
142 .classes = try sliceOf(u32, bytes, header.classes),
143 .texts = try sliceOf(TextRecord, bytes, header.texts),
144 .runs = try sliceOf(TextRun, bytes, header.runs),
145 .relations = try sliceOf(Relation, bytes, header.relations),
146 .atoms = try sliceOf(Atom, bytes, header.atoms),
147 .strings = try sliceOf(u8, bytes, header.strings),
148 .solved_roots = try sliceOf(SolvedRoot, bytes, header.solved_roots),
149 .solved_rects = try sliceOf(Rect, bytes, header.solved_rects),
150 };
151 }
152
153 fn sliceOf(comptime T: type, bytes: []align(8) const u8, span: Span) BindError![]const T {
154 if (span.count == 0) return &.{};
155 if (span.offset < abi.header_bytes) return error.SpanOutOfBounds;
156 if (span.offset % @alignOf(T) != 0) return error.SpanMisaligned;
157 const total = std.math.mul(u32, span.count, @sizeOf(T)) catch
158 return error.SpanOutOfBounds;
159 const end = std.math.add(u32, span.offset, total) catch return error.SpanOutOfBounds;
160 if (end > bytes.len) return error.SpanOutOfBounds;
161 const base: [*]const T = @ptrCast(@alignCast(bytes.ptr + span.offset));
162 return base[0..span.count];
163 }
164
165 test "an empty view resolves the absent atom to an empty slice" {
166 const view = View{};
167 try std.testing.expectEqual(@as(usize, 0), view.text(abi.atom_absent).len);
168 try std.testing.expectEqual(@as(usize, 0), view.nodes.len);
169 }
170
171 test "a span whose element alignment the offset breaks is refused" {
172 var block: [256]u8 align(8) = @splat(0);
173 var header = Header{ .buffer_bytes = 256 };
174 header.nodes = .{ .offset = 156, .count = 1 };
175 @memcpy(block[0..abi.header_bytes], std.mem.asBytes(&header));
176 try std.testing.expectError(error.SpanMisaligned, bind(&block));
177 }
178
179 test "a span reaching past the buffer is refused" {
180 var block: [256]u8 align(8) = @splat(0);
181 var header = Header{ .buffer_bytes = 256 };
182 header.nodes = .{ .offset = 152, .count = 4 };
183 @memcpy(block[0..abi.header_bytes], std.mem.asBytes(&header));
184 try std.testing.expectError(error.SpanOutOfBounds, bind(&block));
185 }
186
187 test "a header whose magic, version, size, or length is wrong is refused" {
188 var block: [256]u8 align(8) = @splat(0);
189 var header = Header{ .buffer_bytes = 256 };
190 header.magic = 0;
191 @memcpy(block[0..abi.header_bytes], std.mem.asBytes(&header));
192 try std.testing.expectError(error.MagicMismatch, bind(&block));
193 header = .{ .buffer_bytes = 256, .abi_version = 2 };
194 @memcpy(block[0..abi.header_bytes], std.mem.asBytes(&header));
195 try std.testing.expectError(error.AbiVersionMismatch, bind(&block));
196 header = .{ .buffer_bytes = 256, .node_bytes = 63 };
197 @memcpy(block[0..abi.header_bytes], std.mem.asBytes(&header));
198 try std.testing.expectError(error.NodeSizeMismatch, bind(&block));
199 header = .{ .buffer_bytes = 255 };
200 @memcpy(block[0..abi.header_bytes], std.mem.asBytes(&header));
201 try std.testing.expectError(error.BufferLengthMismatch, bind(&block));
202 }
203
204 test "a buffer shorter than one header is refused before any field is read" {
205 var block: [8]u8 align(8) = @splat(0);
206 try std.testing.expectError(error.BufferTooSmall, bind(&block));
207 }