lib/zen/src/diagram/limits.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

  1 const std = @import("std");
  2 
  3 const root = @import("root.zig");
  4 
  5 const spec = root.spec;
  6 
  7 pub const line_scratch_factor: u64 = 64;
  8 pub const line_scratch_slack: u64 = 4096;
  9 pub const list_growth_factor: u64 = 2;
 10 pub const fields_json_bytes_min: u64 = 8;
 11 pub const category_slot_bytes: u64 = 48;
 12 pub const mark_output_bytes: u64 = 4096;
 13 pub const axes_output_bytes: u64 = 16384;
 14 pub const svg_chrome_bytes: u64 = 4096;
 15 pub const escape_factor: u64 = 6;
 16 pub const region_slack_bytes: u64 = 4096;
 17 
 18 pub const Measure = struct {
 19     line_count: u64 = 0,
 20     max_line_bytes: u64 = 0,
 21     input_bytes: u64 = 0,
 22 };
 23 
 24 pub fn measure(jsonl: []const u8) Measure {
 25     var measured = Measure{};
 26     var lines = spec.LineIterator.init(jsonl);
 27     while (lines.next()) |line| {
 28         measured.line_count += 1;
 29         measured.max_line_bytes = @max(measured.max_line_bytes, line.len);
 30         measured.input_bytes += line.len;
 31     }
 32     return measured;
 33 }
 34 
 35 pub fn lineScratchBytes(max_line_bytes: u64) error{DiagramTooLarge}!u64 {
 36     const scaled = std.math.mul(u64, max_line_bytes, line_scratch_factor) catch return error.DiagramTooLarge;
 37     return std.math.add(u64, scaled, line_scratch_slack) catch return error.DiagramTooLarge;
 38 }
 39 
 40 pub const Limits = struct {
 41     input_bytes: u64 = 0,
 42     max_line_bytes: u64 = 0,
 43     record_count: u64 = 0,
 44     frame_records: u64 = 0,
 45     scale_records: u64 = 0,
 46     transform_records: u64 = 0,
 47     data_records: u64 = 0,
 48     data_line_bytes: u64 = 0,
 49     channel_records: u64 = 0,
 50     explicit_mark_records: u64 = 0,
 51     scratch_high_water: u64 = 0,
 52 
 53     pub fn marksUpper(self: Limits) error{DiagramTooLarge}!u64 {
 54         const fanout = std.math.mul(u64, self.channel_records, self.data_records) catch return error.DiagramTooLarge;
 55         return std.math.add(u64, self.explicit_mark_records, fanout) catch return error.DiagramTooLarge;
 56     }
 57 
 58     pub fn fanoutStringBytes(self: Limits) error{DiagramTooLarge}!u64 {
 59         return std.math.mul(u64, self.channel_records, self.data_line_bytes) catch return error.DiagramTooLarge;
 60     }
 61 };
 62 
 63 pub fn survey(line_scratch: []u8, jsonl: []const u8) !Limits {
 64     var limits = Limits{};
 65     var scratch = std.heap.FixedBufferAllocator.init(line_scratch);
 66     var lines = spec.LineIterator.init(jsonl);
 67     while (lines.next()) |line| {
 68         scratch.reset();
 69         var parsed = std.json.parseFromSlice(std.json.Value, scratch.allocator(), line, .{}) catch |err| switch (err) {
 70             error.OutOfMemory => return error.OutOfMemory,
 71             else => return error.InvalidJsonl,
 72         };
 73         defer parsed.deinit();
 74         limits.record_count += 1;
 75         limits.input_bytes += line.len;
 76         limits.max_line_bytes = @max(limits.max_line_bytes, line.len);
 77         switch (try spec.recordKindOf(parsed.value)) {
 78             .frame => limits.frame_records += 1,
 79             .scale => limits.scale_records += 1,
 80             .transform => limits.transform_records += 1,
 81             .data => {
 82                 limits.data_records += 1;
 83                 limits.data_line_bytes += line.len;
 84             },
 85             .mark => limits.channel_records += 1,
 86             .bar, .point, .rule, .text, .box, .edge => limits.explicit_mark_records += 1,
 87         }
 88         limits.scratch_high_water = @max(limits.scratch_high_water, scratch.end_index);
 89     }
 90     return limits;
 91 }
 92 
 93 pub const Capacity = struct {
 94     line_scratch_bytes: u64,
 95     document_bytes: u64,
 96     render_scratch_bytes: u64,
 97     output_bytes: u64,
 98 
 99     pub fn derive(limits: Limits) error{DiagramTooLarge}!Capacity {
100         const marks_upper = try limits.marksUpper();
101         const fanout_string_bytes = try limits.fanoutStringBytes();
102         const retained_string_bytes = try add(limits.input_bytes, fanout_string_bytes);
103 
104         const mark_slots = try mul(marks_upper, @sizeOf(spec.Mark) * list_growth_factor);
105         const data_slots = try mul(limits.data_records, @sizeOf(spec.DataRow) * list_growth_factor);
106         const transform_slots = try mul(limits.transform_records, @sizeOf(spec.Transform) * list_growth_factor);
107         const field_count = try add(limits.data_line_bytes / fields_json_bytes_min, limits.data_records);
108         const field_slots = try mul(field_count, @sizeOf(spec.Field) * list_growth_factor);
109         var document_bytes = try add(mark_slots, data_slots);
110         document_bytes = try add(document_bytes, transform_slots);
111         document_bytes = try add(document_bytes, field_slots);
112         document_bytes = try add(document_bytes, retained_string_bytes);
113         document_bytes = try add(document_bytes, region_slack_bytes);
114 
115         var render_scratch_bytes = try mul(marks_upper, category_slot_bytes);
116         render_scratch_bytes = try add(render_scratch_bytes, retained_string_bytes);
117         render_scratch_bytes = try add(render_scratch_bytes, limits.max_line_bytes);
118         render_scratch_bytes = try add(render_scratch_bytes, region_slack_bytes);
119 
120         var output_bytes = try mul(marks_upper, mark_output_bytes);
121         output_bytes = try add(output_bytes, try mul(retained_string_bytes, escape_factor));
122         output_bytes = try add(output_bytes, axes_output_bytes);
123         output_bytes = try add(output_bytes, svg_chrome_bytes);
124         output_bytes = try add(output_bytes, region_slack_bytes);
125 
126         return .{
127             .line_scratch_bytes = try lineScratchBytes(limits.max_line_bytes),
128             .document_bytes = document_bytes,
129             .render_scratch_bytes = render_scratch_bytes,
130             .output_bytes = output_bytes,
131         };
132     }
133 
134     pub fn totalBytes(self: Capacity) error{DiagramTooLarge}!u64 {
135         var total = try add(self.line_scratch_bytes, self.document_bytes);
136         total = try add(total, self.render_scratch_bytes);
137         return try add(total, self.output_bytes);
138     }
139 };
140 
141 fn add(a: u64, b: u64) error{DiagramTooLarge}!u64 {
142     return std.math.add(u64, a, b) catch error.DiagramTooLarge;
143 }
144 
145 fn mul(a: u64, b: u64) error{DiagramTooLarge}!u64 {
146     return std.math.mul(u64, a, b) catch error.DiagramTooLarge;
147 }
148 
149 test "measure reports lines and bytes over trimmed nonempty lines" {
150     const jsonl = "  {\"kind\":\"frame\"}  \n\n{\"kind\":\"point\",\"x\":1,\"y\":2}\n";
151     const measured = measure(jsonl);
152     try std.testing.expectEqual(@as(u64, 2), measured.line_count);
153     try std.testing.expectEqual(@as(u64, 16 + 28), measured.input_bytes);
154     try std.testing.expectEqual(@as(u64, 28), measured.max_line_bytes);
155 }
156 
157 test "survey counts records by kind and tracks scratch high water" {
158     const jsonl =
159         \\{"kind":"frame","title":"T"}
160         \\{"kind":"scale","axis":"x","type":"log"}
161         \\{"kind":"transform","op":"stack"}
162         \\{"kind":"data","name":"d","x":"a","y":1}
163         \\{"kind":"data","name":"d","x":"b","y":2}
164         \\{"kind":"mark","type":"bar","data":"d","x":"x","y":"y"}
165         \\{"kind":"bar","x":"a","y":1}
166         \\{"kind":"edge","x1":0,"y1":0,"x2":1,"y2":1}
167     ;
168     var scratch: [8192]u8 = undefined;
169     const limits = try survey(&scratch, jsonl);
170     try std.testing.expectEqual(@as(u64, 8), limits.record_count);
171     try std.testing.expectEqual(@as(u64, 1), limits.frame_records);
172     try std.testing.expectEqual(@as(u64, 1), limits.scale_records);
173     try std.testing.expectEqual(@as(u64, 1), limits.transform_records);
174     try std.testing.expectEqual(@as(u64, 2), limits.data_records);
175     try std.testing.expectEqual(@as(u64, 1), limits.channel_records);
176     try std.testing.expectEqual(@as(u64, 2), limits.explicit_mark_records);
177     try std.testing.expect(limits.scratch_high_water > 0);
178     try std.testing.expect(limits.scratch_high_water <= scratch.len);
179     try std.testing.expectEqual(@as(u64, 4), try limits.marksUpper());
180 }
181 
182 test "survey rejects malformed lines exactly as parse admission" {
183     var scratch: [8192]u8 = undefined;
184     try std.testing.expectError(error.InvalidJsonl, survey(&scratch, "not json"));
185     try std.testing.expectError(error.MissingKind, survey(&scratch, "{\"x\":1}"));
186     try std.testing.expectError(error.UnknownRecordKind, survey(&scratch, "{\"kind\":\"nope\"}"));
187     try std.testing.expectError(error.InvalidRecord, survey(&scratch, "[1,2]"));
188 }
189 
190 test "capacity derivation is monotone in survey terms and rejects overflow" {
191     var scratch: [8192]u8 = undefined;
192     const small = try survey(&scratch, "{\"kind\":\"point\",\"x\":1,\"y\":2}");
193     const capacity = try Capacity.derive(small);
194     try std.testing.expect(capacity.document_bytes >= small.input_bytes);
195     try std.testing.expect(capacity.output_bytes >= mark_output_bytes);
196     try std.testing.expect(try capacity.totalBytes() > 0);
197 
198     var overflowing = small;
199     overflowing.channel_records = std.math.maxInt(u64) / 2;
200     overflowing.data_records = std.math.maxInt(u64) / 2;
201     try std.testing.expectError(error.DiagramTooLarge, Capacity.derive(overflowing));
202 }