lib/preserves/src/properties/packed.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const hypothesis = @import("hypothesis");
3 const preserves = @import("preserves");
4
5 const ConjectureData = hypothesis.ConjectureData;
6 const intToU64 = hypothesis.strategies.intToU64;
7 const u64ToInt = hypothesis.strategies.u64ToInt;
8 const PreservesValue = preserves.Value(preserves.NoEmbedded);
9 const packed_limits: preserves.packed_reader.Limits = .{
10 .max_depth = 64,
11 .max_nodes = 65_536,
12 .max_collection_items = 4096,
13 .max_retained_bytes = 16 * 1024 * 1024,
14 };
15
16 pub const Options = struct {
17 stress: bool = false,
18 max_bytes_len: usize = 8,
19 max_collection_len: usize = 4,
20 };
21
22 pub fn settings(seed: u64) hypothesis.Settings {
23 return hypothesis.Settings.quick()
24 .withSeed(seed)
25 .withDatabase("zig-out/hypothesis-failures/preserves");
26 }
27
28 pub fn drawValue(
29 data: *ConjectureData,
30 arena: std.mem.Allocator,
31 comptime depth: u32,
32 options: Options,
33 ) !PreservesValue {
34 if (depth == 0) return drawLeaf(data, arena, options);
35
36 const kind = try data.drawInteger(0, 5, 0);
37 return switch (kind) {
38 0 => drawLeaf(data, arena, options),
39 1 => drawSequence(data, arena, depth, options),
40 2 => drawDictionary(data, arena, depth, options),
41 3 => drawRecord(data, arena, depth, options),
42 4 => drawSet(data, arena, depth, options),
43 5 => drawLeaf(data, arena, options),
44 else => unreachable,
45 };
46 }
47
48 fn drawLeaf(
49 data: *ConjectureData,
50 arena: std.mem.Allocator,
51 options: Options,
52 ) !PreservesValue {
53 const max_kind: u64 = if (options.stress) 8 else 5;
54 const kind = try data.drawInteger(0, max_kind, 0);
55 return switch (kind) {
56 0 => PreservesValue.initBoolean(try data.drawBoolean()),
57 1 => if (options.stress)
58 try drawStressInteger(data)
59 else
60 try drawSmallInteger(data),
61 2 => if (options.stress)
62 try drawSmallInteger(data)
63 else
64 try drawString(data, arena, options, 0x20),
65 3 => if (options.stress)
66 try drawStressInteger(data)
67 else
68 try drawBytes(data, arena, options),
69 4 => if (options.stress)
70 try drawDouble(data)
71 else
72 try drawSymbol(data, arena, options),
73 5 => try drawDouble(data),
74 6 => try drawString(data, arena, options, 0x00),
75 7 => try drawBytes(data, arena, options),
76 8 => try drawSymbol(data, arena, options),
77 else => unreachable,
78 };
79 }
80
81 const double_bits = [_]u64{
82 @bitCast(@as(f64, 0.0)),
83 @bitCast(@as(f64, -0.0)),
84 @bitCast(@as(f64, 1.0)),
85 @bitCast(@as(f64, -1.5)),
86 @bitCast(@as(f64, 1e300)),
87 @bitCast(std.math.inf(f64)),
88 @bitCast(-std.math.inf(f64)),
89 @bitCast(std.math.nan(f64)),
90 0x7ff8_0000_0000_0001,
91 0x0000_0000_0000_0001,
92 };
93
94 fn drawDouble(data: *ConjectureData) !PreservesValue {
95 const pick = try data.drawInteger(0, double_bits.len - 1, 0);
96 return PreservesValue.initDouble(@bitCast(double_bits[@intCast(pick)]));
97 }
98
99 fn drawSymbol(
100 data: *ConjectureData,
101 arena: std.mem.Allocator,
102 options: Options,
103 ) !PreservesValue {
104 const len: usize = @intCast(try data.drawInteger(0, options.max_bytes_len, 1));
105 const buf = try arena.alloc(u8, len);
106 const alphabet = "abcdefghijklmnopqrstuvwxyz0123456789_'.";
107 for (buf) |*c| {
108 const index = try data.drawInteger(0, alphabet.len - 1, 0);
109 c.* = alphabet[@intCast(index)];
110 }
111 return .{ .symbol = buf };
112 }
113
114 fn drawRecord(
115 data: *ConjectureData,
116 arena: std.mem.Allocator,
117 comptime depth: u32,
118 options: Options,
119 ) !PreservesValue {
120 const label_ptr = try arena.create(PreservesValue);
121 label_ptr.* = if (try data.drawBoolean())
122 try drawSymbol(data, arena, options)
123 else
124 try drawLeaf(data, arena, options);
125
126 const len: usize = @intCast(try data.drawInteger(0, options.max_collection_len, 0));
127 const fields = try arena.alloc(PreservesValue, len);
128 for (fields) |*slot| {
129 slot.* = try drawValue(data, arena, depth - 1, options);
130 }
131 return .{ .record = .{ .label = label_ptr, .fields = fields } };
132 }
133
134 fn drawSet(
135 data: *ConjectureData,
136 arena: std.mem.Allocator,
137 comptime depth: u32,
138 options: Options,
139 ) !PreservesValue {
140 const target_len: usize = @intCast(try data.drawInteger(0, options.max_collection_len, 0));
141 var items: std.ArrayListUnmanaged(PreservesValue) = .empty;
142
143 const max_attempts: usize = target_len * 4 + 8;
144 var attempts: usize = 0;
145 while (items.items.len < target_len and attempts < max_attempts) : (attempts += 1) {
146 const candidate = try drawValue(data, arena, depth - 1, options);
147 var dup = false;
148 for (items.items) |existing| {
149 if (existing.eql(candidate)) {
150 dup = true;
151 break;
152 }
153 }
154 if (dup) continue;
155 try items.append(arena, candidate);
156 }
157
158 const sorted = try items.toOwnedSlice(arena);
159 const Cmp = struct {
160 fn lt(_: void, a: PreservesValue, b: PreservesValue) bool {
161 return a.compare(b) == .lt;
162 }
163 };
164 std.mem.sort(PreservesValue, sorted, {}, Cmp.lt);
165 return PreservesValue.initSet(sorted);
166 }
167
168 fn drawSmallInteger(data: *ConjectureData) !PreservesValue {
169 const n = try drawSigned(i64, data, -128, 127);
170 return PreservesValue.initI128(@as(i128, n));
171 }
172
173 fn drawStressInteger(data: *ConjectureData) !PreservesValue {
174 const kind = try data.drawInteger(0, 11, 0);
175 const n: i128 = switch (kind) {
176 0 => @as(i128, try drawSigned(i64, data, -128, 127)),
177 1 => 0,
178 2 => 1,
179 3 => -1,
180 4 => @as(i128, try drawSigned(i32, data, std.math.minInt(i32), std.math.maxInt(i32))),
181 5 => @as(i128, try drawSigned(i64, data, std.math.minInt(i64), std.math.maxInt(i64))),
182 6 => std.math.maxInt(i32),
183 7 => std.math.minInt(i32),
184 8 => @as(i128, std.math.maxInt(i32)) + 1,
185 9 => std.math.maxInt(i64),
186 10 => std.math.minInt(i64),
187 11 => @as(i128, 1) << 63,
188 else => unreachable,
189 };
190 return PreservesValue.initI128(n);
191 }
192
193 fn drawSigned(
194 comptime T: type,
195 data: *ConjectureData,
196 min: T,
197 max: T,
198 ) !T {
199 const raw = try data.drawInteger(
200 intToU64(T, min),
201 intToU64(T, max),
202 intToU64(T, if (min <= 0 and 0 <= max) 0 else min),
203 );
204 return u64ToInt(T, raw);
205 }
206
207 fn drawString(
208 data: *ConjectureData,
209 arena: std.mem.Allocator,
210 options: Options,
211 min_byte: u8,
212 ) !PreservesValue {
213 const len: usize = @intCast(try data.drawInteger(0, options.max_bytes_len, 0));
214 const buf = try arena.alloc(u8, len);
215 for (buf) |*c| {
216 c.* = @intCast(try data.drawInteger(min_byte, 0x7e, min_byte));
217 }
218 return .{ .string = buf };
219 }
220
221 fn drawBytes(
222 data: *ConjectureData,
223 arena: std.mem.Allocator,
224 options: Options,
225 ) !PreservesValue {
226 const bytes = try data.drawBytes(0, options.max_bytes_len);
227 const owned = try arena.dupe(u8, bytes);
228 return .{ .byte_string = owned };
229 }
230
231 fn drawSequence(
232 data: *ConjectureData,
233 arena: std.mem.Allocator,
234 comptime depth: u32,
235 options: Options,
236 ) !PreservesValue {
237 const len: usize = @intCast(try data.drawInteger(0, options.max_collection_len, 0));
238 const buf = try arena.alloc(PreservesValue, len);
239 for (buf) |*slot| {
240 slot.* = try drawValue(data, arena, depth - 1, options);
241 }
242 return PreservesValue.initSequence(buf);
243 }
244
245 fn drawDictionary(
246 data: *ConjectureData,
247 arena: std.mem.Allocator,
248 comptime depth: u32,
249 options: Options,
250 ) !PreservesValue {
251 const target_len: usize = @intCast(try data.drawInteger(0, options.max_collection_len, 0));
252 var entries: std.ArrayListUnmanaged(PreservesValue.DictionaryEntry) = .empty;
253
254 const max_attempts: usize = target_len * 4 + 8;
255 var filled: usize = 0;
256 var attempts: usize = 0;
257 while (filled < target_len and attempts < max_attempts) : (attempts += 1) {
258 const key = try drawLeaf(data, arena, options);
259 var dup = false;
260 for (entries.items) |existing| {
261 if (existing.key.eql(key)) {
262 dup = true;
263 break;
264 }
265 }
266 if (dup) continue;
267
268 const value = try drawValue(data, arena, depth - 1, options);
269 try entries.append(arena, .{ .key = key, .value = value });
270 filled += 1;
271 }
272
273 const sorted = try entries.toOwnedSlice(arena);
274 const Cmp = struct {
275 fn lt(_: void, a: PreservesValue.DictionaryEntry, b: PreservesValue.DictionaryEntry) bool {
276 return a.key.compare(b.key) == .lt;
277 }
278 };
279 std.mem.sort(PreservesValue.DictionaryEntry, sorted, {}, Cmp.lt);
280 return PreservesValue.initDictionary(sorted);
281 }
282
283 pub const RoundTripProperty = struct {
284 pub fn property(data: *hypothesis.ConjectureData, allocator: std.mem.Allocator) !void {
285 var arena_state = std.heap.ArenaAllocator.init(allocator);
286 defer arena_state.deinit();
287 const arena = arena_state.allocator();
288
289 const value = try drawValue(data, arena, 3, .{
290 .max_bytes_len = 8,
291 .max_collection_len = 4,
292 });
293
294 const encoded = try preserves.encodePacked(preserves.NoEmbedded, allocator, value);
295 defer allocator.free(encoded);
296
297 var decoded = try preserves.decodePacked(
298 preserves.NoEmbedded,
299 allocator,
300 encoded,
301 packed_limits,
302 );
303 defer decoded.deinit(allocator);
304
305 try std.testing.expect(value.eql(decoded));
306 }
307 };
308
309 pub const StressRoundTripProperty = struct {
310 pub fn property(data: *hypothesis.ConjectureData, allocator: std.mem.Allocator) !void {
311 var arena_state = std.heap.ArenaAllocator.init(allocator);
312 defer arena_state.deinit();
313 const arena = arena_state.allocator();
314
315 const value = try drawValue(data, arena, 3, .{
316 .stress = true,
317 .max_bytes_len = 16,
318 .max_collection_len = 4,
319 });
320
321 const encoded = try preserves.encodePacked(preserves.NoEmbedded, allocator, value);
322 defer allocator.free(encoded);
323
324 var decoded = try preserves.decodePacked(
325 preserves.NoEmbedded,
326 allocator,
327 encoded,
328 packed_limits,
329 );
330 defer decoded.deinit(allocator);
331
332 try std.testing.expect(value.eql(decoded));
333 }
334 };
335
336 pub const CanonicalRoundTripProperty = struct {
337 pub fn property(data: *hypothesis.ConjectureData, allocator: std.mem.Allocator) !void {
338 var arena_state = std.heap.ArenaAllocator.init(allocator);
339 defer arena_state.deinit();
340 const arena = arena_state.allocator();
341
342 const value = try drawValue(data, arena, 3, .{
343 .stress = true,
344 .max_bytes_len = 12,
345 .max_collection_len = 4,
346 });
347
348 const encoded = try preserves.encodePacked(preserves.NoEmbedded, allocator, value);
349 defer allocator.free(encoded);
350
351 var decoded = try preserves.decodePacked(
352 preserves.NoEmbedded,
353 allocator,
354 encoded,
355 packed_limits,
356 );
357 defer decoded.deinit(allocator);
358
359 const reencoded = try preserves.encodePacked(preserves.NoEmbedded, allocator, decoded);
360 defer allocator.free(reencoded);
361
362 try std.testing.expectEqualSlices(u8, encoded, reencoded);
363 }
364 };
365
366 test "prop: preserves packed encode/decode round-trip" {
367 try hypothesis.checkNamed(RoundTripProperty, "preserves-roundtrip", settings(42));
368 }
369
370 test "prop: preserves packed encode/decode stress round-trip" {
371 try hypothesis.checkNamed(StressRoundTripProperty, "preserves-stress", settings(43));
372 }
373
374 test "prop: preserves packed encoding is canonical after decode" {
375 try hypothesis.checkNamed(CanonicalRoundTripProperty, "preserves-canonical-after-decode", settings(47));
376 }