io_v2_protocol.zig (12259B)
1 //! IO v2 wire decoding only. No v1 dispatch, facilities, scheduler or host effects. 2 //! Returned node IDs are borrowed: the caller must retain the action's root while 3 //! using them. Header decoding temporarily roots its input across reducer GC. 4 const std = @import("std"); 5 const Arena = @import("arena.zig").Arena; 6 const Node = @import("tree.zig").Node; 7 const reduce = @import("reduce.zig"); 8 9 pub const Core = enum(u4) { pure, bind, fail, scope, current_scope, spawn, join, discard, cancel, cancelled }; 10 pub const Name = struct { 11 bytes: [64]u8 = undefined, 12 len: u7 = 0, 13 pub fn slice(self: *const Name) []const u8 { 14 return self.bytes[0..self.len]; 15 } 16 }; 17 pub const Action = union(enum) { 18 core: struct { code: Core, payload: u32 }, 19 request: struct { group: Name, revision: u16, operation: Name, arguments: u32 }, 20 }; 21 pub const DecodeError = reduce.ReduceError || error{ 22 InvalidComputationShape, 23 UnknownComputationConstructor, 24 InvalidFacilityHeader, 25 }; 26 27 pub const Reader = struct { 28 arena: *Arena, 29 // Per-demand reducer fuel, not an aggregate request budget or deadline. 30 fuel: u64, 31 pub fn node(self: Reader, id: u32) reduce.ReduceError!Node { 32 // Copy, never hold an arena pointer across another reduction/allocation. 33 return self.arena.get(try reduce.reduce(id, self.arena, self.fuel)).*; 34 } 35 pub const Pair = struct { first: u32, second: u32 }; 36 pub fn pair(self: Reader, id: u32) reduce.ReduceError!?Pair { 37 return switch (try self.node(id)) { 38 .fork => |p| .{ .first = p.left, .second = p.right }, 39 else => null, 40 }; 41 } 42 pub fn nat(self: Reader, id: u32, bits: u7) reduce.ReduceError!?u64 { 43 std.debug.assert(bits <= 64); 44 var rest = id; 45 var value: u64 = 0; 46 var count: u7 = 0; 47 var last: u1 = 0; 48 while (true) { 49 const n = try self.node(rest); 50 if (n == .leaf) return if (count == 0 or last == 1) value else null; 51 if (count == bits or n != .fork) return null; 52 last = switch (try self.node(n.fork.left)) { 53 .leaf => 0, 54 .stem => |s| if (try self.node(s.child) == .leaf) 1 else return null, 55 else => return null, 56 }; 57 value |= @as(u64, last) << @as(u6, @intCast(count)); 58 count += 1; 59 rest = n.fork.right; 60 } 61 } 62 fn name(self: Reader, id: u32) reduce.ReduceError!?Name { 63 var out: Name = .{}; 64 var rest = id; 65 while (true) { 66 const n = try self.node(rest); 67 if (n == .leaf) return if (out.len == 0) null else out; 68 // At the limit observe the spine only, never an excess head/tail. 69 if (out.len == 64 or n != .fork) return null; 70 const c = try self.nat(n.fork.left, 7) orelse return null; 71 const letter = c >= 'a' and c <= 'z'; 72 if (!letter and (out.len == 0 or !((c >= '0' and c <= '9') or c == '-'))) return null; 73 out.bytes[out.len] = @intCast(c); 74 out.len += 1; 75 rest = n.fork.right; 76 } 77 } 78 }; 79 80 pub fn decode(arena: *Arena, action: u32, fuel: u64) DecodeError!Action { 81 const base = arena.roots.items.len; 82 defer arena.roots.shrinkRetainingCapacity(base); 83 try arena.roots.append(arena.allocator, action); 84 const r: Reader = .{ .arena = arena, .fuel = fuel }; 85 const outer = try r.pair(action) orelse return error.InvalidComputationShape; 86 const tag = try r.nat(outer.first, 8) orelse return error.UnknownComputationConstructor; 87 if (tag <= 9) return .{ .core = .{ .code = @enumFromInt(tag), .payload = outer.second } }; 88 if (tag != 10) return error.UnknownComputationConstructor; 89 const group = try r.pair(outer.second) orelse return error.InvalidFacilityHeader; 90 const revision = try r.pair(group.second) orelse return error.InvalidFacilityHeader; 91 const operation = try r.pair(revision.second) orelse return error.InvalidFacilityHeader; 92 const g = try r.name(group.first) orelse return error.InvalidFacilityHeader; 93 const v = try r.nat(revision.first, 16) orelse return error.InvalidFacilityHeader; 94 if (v == 0) return error.InvalidFacilityHeader; 95 const op = try r.name(operation.first) orelse return error.InvalidFacilityHeader; 96 return .{ .request = .{ .group = g, .revision = @intCast(v), .operation = op, .arguments = operation.second } }; 97 } 98 99 const testing = std.testing; 100 const codecs = @import("codecs.zig"); 101 fn pair(a: *Arena, left: u32, right: u32) !u32 { 102 return a.alloc(.{ .fork = .{ .left = left, .right = right } }); 103 } 104 fn request(a: *Arena, group: u32, revision: u32, operation: u32, arguments: u32) !u32 { 105 return pair(a, try codecs.ofNumber(a, 10), try pair(a, group, try pair(a, revision, try pair(a, operation, arguments)))); 106 } 107 fn poison(a: *Arena) !u32 { 108 const leaf = try a.alloc(.leaf); 109 const p = try a.alloc(.leaf); 110 a.get(p).* = .{ .app = .{ .func = p, .arg = leaf } }; 111 return p; 112 } 113 114 test "core catalogue and unknown tags never demand payloads" { 115 var a = Arena.init(testing.allocator); 116 defer a.deinit(); 117 const p = try poison(&a); 118 for (0..10) |tag| { 119 const act = try pair(&a, try codecs.ofNumber(&a, tag), p); 120 const decoded = try decode(&a, act, 0); 121 try testing.expectEqual(tag, @intFromEnum(decoded.core.code)); 122 try testing.expectEqual(p, decoded.core.payload); 123 } 124 for ([_]u64{ 11, 20, 255, 256 }) |tag| { 125 try testing.expectError(error.UnknownComputationConstructor, decode(&a, try pair(&a, try codecs.ofNumber(&a, tag), p), 0)); 126 } 127 try testing.expectError(error.InvalidComputationShape, decode(&a, try a.alloc(.leaf), 0)); 128 try testing.expectEqual(@as(usize, 0), a.roots.items.len); 129 try testing.expect(a.get(p).* == .app); 130 } 131 132 test "valid future headers retain arguments without demanding or resolving them" { 133 var a = Arena.init(testing.allocator); 134 defer a.deinit(); 135 const p = try poison(&a); 136 const act = try request(&a, try codecs.ofString(&a, "future-9"), try codecs.ofNumber(&a, 65535), try codecs.ofString(&a, "unknown"), p); 137 const decoded = (try decode(&a, act, 0)).request; 138 try testing.expectEqualStrings("future-9", decoded.group.slice()); 139 try testing.expectEqualStrings("unknown", decoded.operation.slice()); 140 try testing.expectEqual(@as(u16, 65535), decoded.revision); 141 try testing.expectEqual(p, decoded.arguments); 142 try testing.expect(a.get(p).* == .app); 143 } 144 145 test "strict canonical header numerals and identifier grammar" { 146 var a = Arena.init(testing.allocator); 147 defer a.deinit(); 148 const p = try poison(&a); 149 const leaf = try a.alloc(.leaf); 150 const zero = try pair(&a, leaf, leaf); // forbidden redundant zero bit 151 const good = try codecs.ofString(&a, "file"); 152 const one = try codecs.ofNumber(&a, 1); 153 try testing.expectError(error.UnknownComputationConstructor, decode(&a, try pair(&a, zero, p), 0)); 154 for ([_]u32{ leaf, zero, try codecs.ofNumber(&a, 65536) }) |revision| { 155 try testing.expectError(error.InvalidFacilityHeader, decode(&a, try request(&a, good, revision, good, p), 0)); 156 } 157 for ([_][]const u8{ "", "-file", "1file", "File", "a_b", "a b", "a\x7f", "a" ** 65 }) |name| { 158 const invalid = try codecs.ofString(&a, name); 159 try testing.expectError(error.InvalidFacilityHeader, decode(&a, try request(&a, invalid, one, good, p), 0)); 160 try testing.expectError(error.InvalidFacilityHeader, decode(&a, try request(&a, good, one, invalid, p), 0)); 161 } 162 const longest = try codecs.ofString(&a, "a" ** 64); 163 try testing.expectEqual(@as(u7, 64), (try decode(&a, try request(&a, longest, one, longest, p), 0)).request.group.len); 164 // Character 97 with a redundant high zero must not be accepted as ASCII a. 165 var character = zero; 166 for ([_]u1{ 1, 1, 0, 0, 0, 0, 1 }) |bit| { 167 character = try pair(&a, if (bit == 0) leaf else try a.alloc(.{ .stem = .{ .child = leaf } }), character); 168 } 169 const bad_name = try pair(&a, character, leaf); 170 try testing.expectError(error.InvalidFacilityHeader, decode(&a, try request(&a, bad_name, one, good, p), 0)); 171 } 172 173 test "oversize names do not demand excess head or tail and evaluation errors stay distinct" { 174 var a = Arena.init(testing.allocator); 175 defer a.deinit(); 176 const p = try poison(&a); 177 var name = try pair(&a, p, p); 178 const ch = try codecs.ofNumber(&a, 'a'); 179 for (0..64) |_| name = try pair(&a, ch, name); 180 const one = try codecs.ofNumber(&a, 1); 181 const good = try codecs.ofString(&a, "read"); 182 try testing.expectError(error.InvalidFacilityHeader, decode(&a, try request(&a, name, one, good, p), 0)); 183 try testing.expectError(error.FuelExhausted, decode(&a, try pair(&a, p, p), 0)); 184 try testing.expectEqual(@as(usize, 0), a.roots.items.len); 185 } 186 187 fn allocationProbe(allocator: std.mem.Allocator) !void { 188 var a = Arena.init(allocator); 189 defer a.deinit(); 190 const arg = try poison(&a); 191 const action = try request(&a, try codecs.ofString(&a, "file"), try codecs.ofNumber(&a, 1), try codecs.ofString(&a, "open-reader"), arg); 192 // An unrelated retained root must survive decoding and all failure unwinds. 193 const keep = try a.alloc(.leaf); 194 try a.roots.append(allocator, keep); 195 a.gc_enabled = true; 196 try a.setGcPolicy(1, 1); 197 const decoded = decode(&a, action, 0) catch |err| { 198 try testing.expectEqual(@as(usize, 1), a.roots.items.len); 199 return err; 200 }; 201 try testing.expect(a.collections > 0); 202 try testing.expectEqualStrings("open-reader", decoded.request.operation.slice()); 203 try testing.expect(a.get(decoded.request.arguments).* == .app); 204 try testing.expectEqualSlices(u32, &.{keep}, a.roots.items); 205 // Decoder roots do not turn into a hidden completion/history archive. 206 try a.collect(&.{}); 207 try testing.expectEqual(@as(usize, 1), a.last_live); 208 } 209 test "GC roots survive header demands and every allocator failure unwinds" { 210 try allocationProbe(testing.allocator); 211 try testing.checkAllAllocationFailures(testing.allocator, allocationProbe, .{}); 212 } 213 214 test "malformed facility framing is terminal without examining unrelated arguments" { 215 var a = Arena.init(testing.allocator); 216 defer a.deinit(); 217 const p = try poison(&a); 218 const leaf = try a.alloc(.leaf); 219 const ten = try codecs.ofNumber(&a, 10); 220 const group = try codecs.ofString(&a, "file"); 221 for ([_]u32{ leaf, try pair(&a, group, leaf), try pair(&a, group, try pair(&a, leaf, leaf)) }) |body| { 222 try testing.expectError(error.InvalidFacilityHeader, decode(&a, try pair(&a, ten, body), 0)); 223 } 224 // A bad header must not be confused with a valid unsupported operation. 225 const operation = try codecs.ofString(&a, "not-implemented"); 226 const one = try codecs.ofNumber(&a, 1); 227 const act = try request(&a, group, one, operation, p); 228 try testing.expectEqualStrings("not-implemented", (try decode(&a, act, 0)).request.operation.slice()); 229 try testing.expect(a.get(p).* == .app); 230 } 231 232 fn delayed(a: *Arena, value: u32, ignored: u32) !u32 { 233 return a.allocApp(try pair(a, try a.alloc(.leaf), value), ignored); 234 } 235 test "computed headers reduce under the caller budget and preserve borrowed roots through GC" { 236 var a = Arena.init(testing.allocator); 237 defer a.deinit(); 238 const p = try poison(&a); 239 const group = try delayed(&a, try codecs.ofString(&a, "file"), p); 240 const revision = try delayed(&a, try codecs.ofNumber(&a, 1), p); 241 const operation = try delayed(&a, try codecs.ofString(&a, "open-reader"), p); 242 const act = try delayed(&a, try request(&a, group, revision, operation, p), p); 243 try testing.expectError(error.FuelExhausted, decode(&a, act, 0)); 244 a.gc_enabled = true; 245 try a.setGcPolicy(1, 1); 246 const decoded = (try decode(&a, act, 1)).request; 247 try testing.expectEqualStrings("file", decoded.group.slice()); 248 try testing.expectEqualStrings("open-reader", decoded.operation.slice()); 249 try testing.expectEqual(p, decoded.arguments); 250 try testing.expect(a.get(p).* == .app); 251 try testing.expect(a.collections > 0); 252 try testing.expectEqual(@as(usize, 0), a.roots.items.len); 253 }