lib/bumpalo/src/properties/bump.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const bumpalo = @import("bumpalo");
3 const hypothesis = @import("hypothesis");
4
5 const Allocator = std.mem.Allocator;
6 const Alignment = std.mem.Alignment;
7 const Bump = bumpalo.Bump;
8
9 const Range = struct {
10 start: usize,
11 end: usize,
12 };
13
14 const AllocatorRecord = struct {
15 slice: []u8,
16 fill: u8,
17
18 fn range(record: AllocatorRecord) Range {
19 return .{
20 .start = @intFromPtr(record.slice.ptr),
21 .end = @intFromPtr(record.slice.ptr) + record.slice.len,
22 };
23 }
24 };
25
26 pub fn settings() hypothesis.Settings {
27 return hypothesis.Settings.quick()
28 .withSeed(0xB0BA_10)
29 .withDatabase("zig-out/hypothesis-failures/bumpalo");
30 }
31
32 fn drawUsize(
33 conjecture: *hypothesis.ConjectureData,
34 min: usize,
35 max: usize,
36 shrink_towards: usize,
37 ) !usize {
38 return @intCast(try conjecture.drawInteger(
39 @intCast(min),
40 @intCast(max),
41 @intCast(shrink_towards),
42 ));
43 }
44
45 fn drawAlignment(conjecture: *hypothesis.ConjectureData) !Alignment {
46 const shift = try drawUsize(conjecture, 0, 8, 0);
47 return .fromByteUnits(@as(usize, 1) << @as(u6, @intCast(shift)));
48 }
49
50 fn expectDisjoint(ranges: []const Range) !void {
51 for (ranges, 0..) |left, index| {
52 for (ranges[index + 1 ..]) |right| {
53 try std.testing.expect(left.end <= right.start or right.end <= left.start);
54 }
55 }
56 }
57
58 fn expectContainedInAllocatedChunk(bump: *Bump, range: Range) !void {
59 var found = false;
60 var iter = bump.iterAllocatedChunks();
61 while (iter.next()) |chunk| {
62 const chunk_start = @intFromPtr(chunk.ptr);
63 const chunk_end = chunk_start + chunk.len;
64 if (chunk_start <= range.start and range.end <= chunk_end) {
65 found = true;
66 break;
67 }
68 }
69 try std.testing.expect(found);
70 }
71
72 pub const DirectAlignmentProperty = struct {
73 pub fn property(
74 conjecture: *hypothesis.ConjectureData,
75 property_allocator: Allocator,
76 ) !void {
77 var bump = Bump.init(property_allocator);
78 defer bump.deinit();
79
80 var ranges: std.ArrayList(Range) = .empty;
81 defer ranges.deinit(property_allocator);
82
83 const count = try drawUsize(conjecture, 1, 96, 12);
84 var index: usize = 0;
85 while (index < count) : (index += 1) {
86 const alignment = try drawAlignment(conjecture);
87 const len = try drawUsize(conjecture, 0, 256, 1);
88 const ptr = try bump.allocBytes(len, alignment);
89
90 try std.testing.expect(std.mem.isAligned(@intFromPtr(ptr), alignment.toByteUnits()));
91 if (len == 0) continue;
92
93 const range = Range{
94 .start = @intFromPtr(ptr),
95 .end = @intFromPtr(ptr) + len,
96 };
97 try ranges.append(property_allocator, range);
98 try expectContainedInAllocatedChunk(&bump, range);
99 }
100
101 try expectDisjoint(ranges.items);
102 try std.testing.expect(bump.queryCapacityIncludingMetadata() >= bump.queryCapacity());
103 }
104 };
105
106 pub const LimitResetProperty = struct {
107 pub fn property(
108 conjecture: *hypothesis.ConjectureData,
109 property_allocator: Allocator,
110 ) !void {
111 var bump = Bump.init(property_allocator);
112 defer bump.deinit();
113
114 const limit = try drawUsize(conjecture, 0, 8192, 4096);
115 bump.setBackingDataCapacityLimit(limit);
116 try std.testing.expectEqual(
117 @as(?usize, limit),
118 bump.backingDataCapacityLimit(),
119 );
120
121 const steps = try drawUsize(conjecture, 1, 80, 8);
122 var step: usize = 0;
123 while (step < steps) : (step += 1) {
124 const op = try drawUsize(conjecture, 0, 99, 0);
125 if (op < 60) {
126 const len = try drawUsize(conjecture, 0, 2048, 1);
127 if (bump.alloc(u8, len)) |slice| {
128 @memset(slice, @intCast(step & 0xff));
129 try std.testing.expect(bump.queryBackingDataCapacity() <= limit);
130 } else |err| {
131 try std.testing.expectEqual(error.OutOfMemory, err);
132 try std.testing.expect(bump.queryBackingDataCapacity() <= limit);
133 }
134 } else {
135 const reset_kind = try drawUsize(conjecture, 0, 3, 0);
136 const retained = switch (reset_kind) {
137 0 => bump.reset(.free_all),
138 1 => bump.reset(.retain_current),
139 2 => bump.reset(.retain_capacity),
140 else => bump.reset(.{
141 .retain_with_limit = try drawUsize(conjecture, 0, 8192, 1024),
142 }),
143 };
144 try std.testing.expect(retained);
145 try std.testing.expect(bump.queryBackingDataCapacity() <= limit);
146 }
147 }
148 }
149 };
150
151 pub const AllocatorStateProperty = struct {
152 pub fn property(
153 conjecture: *hypothesis.ConjectureData,
154 property_allocator: Allocator,
155 ) !void {
156 var bump = Bump.init(property_allocator);
157 defer bump.deinit();
158 const arena_allocator = bump.allocator();
159
160 var active: std.ArrayList(AllocatorRecord) = .empty;
161 defer active.deinit(property_allocator);
162
163 const steps = try drawUsize(conjecture, 1, 96, 16);
164 var step: usize = 0;
165 while (step < steps) : (step += 1) {
166 const op = try drawUsize(conjecture, 0, 99, 0);
167 if (op < 45 or active.items.len == 0) {
168 const len = try drawUsize(conjecture, 1, 192, 1);
169 const fill: u8 = @intCast(step & 0xff);
170 const slice = try arena_allocator.alloc(u8, len);
171 @memset(slice, fill);
172 try active.append(property_allocator, .{ .slice = slice, .fill = fill });
173 } else if (op < 75) {
174 const slot = try drawUsize(conjecture, 0, active.items.len - 1, 0);
175 var record = &active.items[slot];
176 const old_len = record.slice.len;
177 const new_len = try drawUsize(conjecture, 1, 256, 1);
178 const resized = try arena_allocator.realloc(record.slice, new_len);
179 const prefix_len = @min(old_len, new_len);
180 for (resized[0..prefix_len]) |byte| {
181 try std.testing.expectEqual(record.fill, byte);
182 }
183 @memset(resized, record.fill);
184 record.slice = resized;
185 } else if (op < 90) {
186 const slot = try drawUsize(conjecture, 0, active.items.len - 1, 0);
187 arena_allocator.free(active.items[slot].slice);
188 _ = active.swapRemove(slot);
189 } else {
190 const reset_kind = try drawUsize(conjecture, 0, 3, 1);
191 const did_reset = switch (reset_kind) {
192 0 => blk: {
193 bump.clearAndFree();
194 break :blk true;
195 },
196 1 => blk: {
197 bump.clearRetainingCurrent();
198 break :blk true;
199 },
200 2 => bump.clearRetainingCapacity(),
201 else => bump.clearRetainingCapacityLimit(try drawUsize(conjecture, 0, 4096, 512)),
202 };
203 try std.testing.expect(did_reset);
204 active.clearRetainingCapacity();
205 }
206
207 for (active.items, 0..) |record, left_index| {
208 const left = record.range();
209 for (record.slice) |byte| {
210 try std.testing.expectEqual(record.fill, byte);
211 }
212 for (active.items[left_index + 1 ..]) |other| {
213 const pair = [_]Range{ left, other.range() };
214 try expectDisjoint(&pair);
215 }
216 }
217 }
218 }
219 };
220
221 test "property: direct allocations are aligned disjoint and contained" {
222 try hypothesis.checkNamed(DirectAlignmentProperty, "bumpalo-alignment", settings());
223 }
224
225 test "property: allocator operations preserve prefixes and active ranges" {
226 try hypothesis.checkNamed(AllocatorStateProperty, "bumpalo-allocator-state", settings());
227 }
228
229 test "property: backing data capacity limits hold across resets" {
230 try hypothesis.checkNamed(LimitResetProperty, "bumpalo-limits-reset", settings());
231 }