lib/sql/src/properties/lattice.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const hypothesis = @import("hypothesis");
3 const sql = @import("sql");
4
5 const lattice = sql.lattice;
6
7 const max_entries = 24;
8 const max_operations = 48;
9
10 pub fn settings() hypothesis.Settings {
11 return hypothesis.Settings.quick()
12 .withSeed(0x1A77_1CE0)
13 .withDatabase("zig-out/hypothesis-failures/sql");
14 }
15
16 fn drawUsize(conjecture: *hypothesis.ConjectureData, min: usize, max: usize, shrink_towards: usize) !usize {
17 return @intCast(try conjecture.drawInteger(
18 @intCast(min),
19 @intCast(max),
20 @intCast(shrink_towards),
21 ));
22 }
23
24 fn drawKey(conjecture: *hypothesis.ConjectureData, buffer: *[4]u8) ![]const u8 {
25 const length = try drawUsize(conjecture, 1, buffer.len, 1);
26 for (buffer[0..length]) |*byte| {
27 byte.* = @intCast(try drawUsize(conjecture, 'a', 'd', 'a'));
28 }
29 return buffer[0..length];
30 }
31
32 pub const OrderProperty = struct {
33 pub fn property(conjecture: *hypothesis.ConjectureData, allocator: std.mem.Allocator) !void {
34 _ = allocator;
35 const count = try drawUsize(conjecture, 0, max_entries, 0);
36
37 var entries: [max_entries]lattice.State = undefined;
38 for (entries[0..count]) |*entry| {
39 var key_buffer: [4]u8 = undefined;
40 const entry_key = try drawKey(conjecture, &key_buffer);
41 const value = try conjecture.drawBytes(0, 16);
42 var hasher = lattice.EntryHasher.init(entry_key);
43 hasher.update(value);
44 entry.* = hasher.finish();
45 }
46
47 var forward = lattice.State.empty;
48 for (entries[0..count]) |*entry| forward.add(entry);
49
50 var reverse = lattice.State.empty;
51 var index = count;
52 while (index > 0) {
53 index -= 1;
54 reverse.add(&entries[index]);
55 }
56
57 try std.testing.expect(forward.eql(&reverse));
58 try std.testing.expect(std.mem.eql(
59 u8,
60 &forward.digest(count),
61 &reverse.digest(count),
62 ));
63 }
64 };
65
66 pub const InverseProperty = struct {
67 pub fn property(conjecture: *hypothesis.ConjectureData, allocator: std.mem.Allocator) !void {
68 _ = allocator;
69 const count = try drawUsize(conjecture, 0, max_entries, 0);
70
71 var entries: [max_entries]lattice.State = undefined;
72 for (entries[0..count]) |*entry| {
73 var key_buffer: [4]u8 = undefined;
74 const entry_key = try drawKey(conjecture, &key_buffer);
75 const value = try conjecture.drawBytes(0, 16);
76 entry.* = lattice.entryState(entry_key, value);
77 }
78
79 var state = lattice.State.empty;
80 for (entries[0..count]) |*entry| state.add(entry);
81
82 var order: [max_entries]usize = undefined;
83 for (order[0..count], 0..) |*slot, index| slot.* = index;
84 var remaining = count;
85 while (remaining > 0) {
86 const pick = try drawUsize(conjecture, 0, remaining - 1, 0);
87 state.subtract(&entries[order[pick]]);
88 order[pick] = order[remaining - 1];
89 remaining -= 1;
90 }
91
92 try std.testing.expect(state.isEmpty());
93 }
94 };
95
96 pub const ModelProperty = struct {
97 pub fn property(conjecture: *hypothesis.ConjectureData, allocator: std.mem.Allocator) !void {
98 var model = std.StringArrayHashMapUnmanaged([]const u8){};
99 defer {
100 for (model.keys()) |stored_key| allocator.free(stored_key);
101 for (model.values()) |stored_value| allocator.free(stored_value);
102 model.deinit(allocator);
103 }
104
105 var state = lattice.State.empty;
106 const operations = try drawUsize(conjecture, 0, max_operations, 0);
107
108 var index: usize = 0;
109 while (index < operations) : (index += 1) {
110 var key_buffer: [4]u8 = undefined;
111 const entry_key = try drawKey(conjecture, &key_buffer);
112 const remove = try drawUsize(conjecture, 0, 3, 0) == 0;
113
114 if (remove) {
115 if (model.fetchSwapRemove(entry_key)) |removed| {
116 const gone = lattice.entryState(removed.key, removed.value);
117 state.subtract(&gone);
118 allocator.free(removed.key);
119 allocator.free(removed.value);
120 }
121 continue;
122 }
123
124 const value = try conjecture.drawBytes(0, 16);
125 if (model.getEntry(entry_key)) |existing| {
126 const old = lattice.entryState(existing.key_ptr.*, existing.value_ptr.*);
127 state.subtract(&old);
128 allocator.free(existing.value_ptr.*);
129 existing.value_ptr.* = try allocator.dupe(u8, value);
130 } else {
131 const owned_key = try allocator.dupe(u8, entry_key);
132 errdefer allocator.free(owned_key);
133 const owned_value = try allocator.dupe(u8, value);
134 errdefer allocator.free(owned_value);
135 try model.put(allocator, owned_key, owned_value);
136 }
137 const fresh = lattice.entryState(entry_key, value);
138 state.add(&fresh);
139 }
140
141 var rebuilt = lattice.State.empty;
142 var iterator = model.iterator();
143 while (iterator.next()) |entry| {
144 const rebuilt_entry = lattice.entryState(entry.key_ptr.*, entry.value_ptr.*);
145 rebuilt.add(&rebuilt_entry);
146 }
147
148 try std.testing.expect(state.eql(&rebuilt));
149 try std.testing.expect(std.mem.eql(
150 u8,
151 &state.digest(model.count()),
152 &rebuilt.digest(model.count()),
153 ));
154 }
155 };
156
157 pub const CodecProperty = struct {
158 pub fn property(conjecture: *hypothesis.ConjectureData, allocator: std.mem.Allocator) !void {
159 _ = allocator;
160 var state = lattice.State.empty;
161 const count = try drawUsize(conjecture, 0, max_entries, 0);
162 var index: usize = 0;
163 while (index < count) : (index += 1) {
164 var key_buffer: [4]u8 = undefined;
165 const entry_key = try drawKey(conjecture, &key_buffer);
166 const value = try conjecture.drawBytes(0, 16);
167 const entry = lattice.entryState(entry_key, value);
168 state.add(&entry);
169 }
170
171 var encoded: [lattice.encoded_size]u8 = undefined;
172 state.encode(&encoded);
173 const decoded = lattice.State.decode(&encoded);
174 try std.testing.expect(state.eql(&decoded));
175 try std.testing.expect(std.mem.eql(
176 u8,
177 &state.digest(count),
178 &decoded.digest(count),
179 ));
180 }
181 };
182
183 pub const TreeProperty = struct {
184 pub fn property(conjecture: *hypothesis.ConjectureData, allocator: std.mem.Allocator) !void {
185 var tmp = std.testing.tmpDir(.{});
186 defer tmp.cleanup();
187
188 var database = try sql.FileDatabase.openForTesting(allocator, tmp.dir, .{
189 .paths = .{ .database = "lattice.db", .wal = "lattice.wal" },
190 .header = .{
191 .sequence = 601,
192 .salt = .{ .first = 0x1a77_1ce1, .second = 0x2b88_2df2 },
193 },
194 });
195 defer database.deinit();
196 try database.reserve(.{ .wal_frames = 120 });
197
198 var tree = try sql.Tree.open(&database, .{ .identity_page = 3 });
199
200 var model = std.StringArrayHashMapUnmanaged([]const u8){};
201 defer {
202 for (model.keys()) |stored_key| allocator.free(stored_key);
203 for (model.values()) |stored_value| allocator.free(stored_value);
204 model.deinit(allocator);
205 }
206
207 const operations = try drawUsize(conjecture, 0, max_operations, 0);
208 var index: usize = 0;
209 while (index < operations) : (index += 1) {
210 var key_buffer: [4]u8 = undefined;
211 const entry_key = try drawKey(conjecture, &key_buffer);
212 const action = try drawUsize(conjecture, 0, 4, 1);
213
214 if (action == 0) {
215 if (model.fetchSwapRemove(entry_key)) |removed| {
216 _ = try tree.delete(entry_key, .{ .durability = .buffered });
217 allocator.free(removed.key);
218 allocator.free(removed.value);
219 } else {
220 try std.testing.expectError(
221 error.KeyNotFound,
222 tree.delete(entry_key, .{ .durability = .buffered }),
223 );
224 }
225 continue;
226 }
227
228 const large = action == 4;
229 const value = if (large)
230 try conjecture.drawBytes(sql.page.overflow_capacity + 1, sql.page.overflow_capacity + 64)
231 else
232 try conjecture.drawBytes(0, 16);
233 _ = try tree.put(entry_key, value, .{ .durability = .buffered });
234 if (model.getEntry(entry_key)) |existing| {
235 allocator.free(existing.value_ptr.*);
236 existing.value_ptr.* = try allocator.dupe(u8, value);
237 } else {
238 const owned_key = try allocator.dupe(u8, entry_key);
239 errdefer allocator.free(owned_key);
240 const owned_value = try allocator.dupe(u8, value);
241 errdefer allocator.free(owned_value);
242 try model.put(allocator, owned_key, owned_value);
243 }
244 }
245
246 var rebuilt = lattice.State.empty;
247 var iterator = model.iterator();
248 while (iterator.next()) |entry| {
249 const rebuilt_entry = lattice.entryState(entry.key_ptr.*, entry.value_ptr.*);
250 rebuilt.add(&rebuilt_entry);
251 }
252
253 const info = try tree.identity();
254 try std.testing.expectEqual(@as(u64, model.count()), info.entries);
255 try std.testing.expect(info.state.eql(&rebuilt));
256 try std.testing.expect(std.mem.eql(
257 u8,
258 &tree.digestIdentity(&info),
259 &rebuilt.digest(model.count()),
260 ));
261 }
262 };
263
264 test "property: lattice state is order independent" {
265 if (!@import("sql_test_options").run_property_tests) return error.SkipZigTest;
266
267 try hypothesis.checkNamed(OrderProperty, "sql-lattice-order", settings());
268 }
269
270 test "property: lattice subtraction inverts addition in any order" {
271 if (!@import("sql_test_options").run_property_tests) return error.SkipZigTest;
272
273 try hypothesis.checkNamed(InverseProperty, "sql-lattice-inverse", settings());
274 }
275
276 test "property: lattice mutation trace matches rebuild from final entries" {
277 if (!@import("sql_test_options").run_property_tests) return error.SkipZigTest;
278
279 try hypothesis.checkNamed(ModelProperty, "sql-lattice-model", settings());
280 }
281
282 test "property: lattice encode decode round trips" {
283 if (!@import("sql_test_options").run_property_tests) return error.SkipZigTest;
284
285 try hypothesis.checkNamed(CodecProperty, "sql-lattice-codec", settings());
286 }
287
288 test "property: file tree identity matches rebuild from surviving entries" {
289 if (!@import("sql_test_options").run_property_tests) return error.SkipZigTest;
290
291 try hypothesis.checkNamed(TreeProperty, "sql-lattice-tree", settings());
292 }