lib/sql/src/properties/page.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

  1 const std = @import("std");
  2 const hypothesis = @import("hypothesis");
  3 const sql = @import("sql");
  4 
  5 const Leaf = sql.LeafPage;
  6 
  7 const key_count = 10;
  8 const value_max = 400;
  9 
 10 pub fn settings() hypothesis.Settings {
 11     return hypothesis.Settings.quick()
 12         .withSeed(0x71DB_2026)
 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 keyByte(index: usize) u8 {
 25     return @intCast(index);
 26 }
 27 
 28 /// A model value, stored as its length and the byte that fills it.
 29 const Value = struct {
 30     len: usize,
 31     byte: u8,
 32 
 33     fn bytes(self: Value, buffer: *[value_max]u8) []const u8 {
 34         @memset(buffer[0..self.len], self.byte);
 35         return buffer[0..self.len];
 36     }
 37 };
 38 
 39 /// Checks the leaf against the model, and that its cells leave exactly the
 40 /// free bytes of a leaf built from its entries in order.
 41 fn expectLeaf(leaf: *const Leaf, values: [key_count]?Value) !void {
 42     var index: usize = 0;
 43     while (index < key_count) : (index += 1) {
 44         const key_bytes = [_]u8{keyByte(index)};
 45         const actual = leaf.get(&key_bytes);
 46         if (values[index]) |expected| {
 47             var buffer: [value_max]u8 = undefined;
 48             try std.testing.expect(actual != null);
 49             try std.testing.expectEqualSlices(u8, expected.bytes(&buffer), actual.?);
 50         } else {
 51             try std.testing.expect(actual == null);
 52         }
 53     }
 54 
 55     var rebuilt_bytes: [sql.page.size]u8 = undefined;
 56     var rebuilt = Leaf.init(&rebuilt_bytes, 1);
 57     var range = try leaf.range(null, null);
 58     var previous: ?u8 = null;
 59     while (range.next()) |entry| {
 60         try std.testing.expect(entry.key.len == 1);
 61         const key_value = entry.key[0];
 62         if (previous) |prev| try std.testing.expect(prev < key_value);
 63         previous = key_value;
 64         try std.testing.expect(values[key_value] != null);
 65         try rebuilt.put(entry.key, entry.value);
 66     }
 67     try std.testing.expectEqual(rebuilt.freeBytes(), leaf.freeBytes());
 68 }
 69 
 70 pub const LeafProperty = struct {
 71     pub fn property(conjecture: *hypothesis.ConjectureData, _: std.mem.Allocator) !void {
 72         var bytes: [sql.page.size]u8 = undefined;
 73         var leaf = Leaf.init(&bytes, 1);
 74         var model = @as([key_count]?Value, @splat(null));
 75 
 76         const steps = try drawUsize(conjecture, 1, 120, 20);
 77         var step: usize = 0;
 78         while (step < steps) : (step += 1) {
 79             const op = try drawUsize(conjecture, 0, 99, 0);
 80             const slot = try drawUsize(conjecture, 0, key_count - 1, 0);
 81             const key_bytes = [_]u8{keyByte(slot)};
 82             if (op < 60) {
 83                 const value: Value = .{
 84                     .len = try drawUsize(conjecture, 1, value_max, 1),
 85                     .byte = @intCast(try drawUsize(conjecture, 0, 255, 0)),
 86                 };
 87                 var buffer: [value_max]u8 = undefined;
 88                 const before = bytes;
 89                 if (leaf.put(&key_bytes, value.bytes(&buffer))) {
 90                     model[slot] = value;
 91                 } else |err| switch (err) {
 92                     error.PageFull => try std.testing.expectEqualSlices(u8, &before, &bytes),
 93                     else => return err,
 94                 }
 95             } else if (op < 80) {
 96                 const result = leaf.delete(&key_bytes);
 97                 if (model[slot]) |_| {
 98                     try result;
 99                     model[slot] = null;
100                 } else {
101                     try std.testing.expectError(error.KeyNotFound, result);
102                 }
103             } else {
104                 const loaded = try Leaf.load(&bytes);
105                 try expectLeaf(&loaded, model);
106             }
107 
108             const loaded = try Leaf.load(&bytes);
109             try expectLeaf(&loaded, model);
110         }
111     }
112 };
113 
114 test "property: slotted leaf page matches the bounded model" {
115     if (!@import("sql_test_options").run_property_tests) return error.SkipZigTest;
116 
117     try hypothesis.checkNamed(LeafProperty, "sql-leaf-page", settings());
118 }