tiny.hypothesis.conjecture

1const std = @import("std");2const Allocator = std.mem.Allocator;34pub const ChoiceKind = enum(u8) {5    integer,6    boolean,7    float,8    bytes,9};1011pub const ChoiceNode = struct {12    kind: ChoiceKind,13    value: u64,14    min: u64 = 0,15    max: u64 = std.math.maxInt(u64),16    shrink_towards: u64 = 0,17    was_forced: bool = false,18};1920pub const Span = struct {21    label: []const u8,22    start: usize,23    end: usize,24    depth: usize,25};2627pub const Status = enum {28    valid,29    invalid,30    interesting,31    overrun,32};3334pub const DrawError = error{35    Overrun,36    OutOfMemory,37};3839pub const default_max_input_bytes: usize = 1024 * 1024;4041pub const TargetError = error{42    DuplicateTargetLabel,43    NonFiniteTarget,44    OutOfMemory,45};4647pub const TargetObservation = struct {48    label: []const u8,49    value: f64,50};5152pub const ConjectureData = struct {53    choices: std.ArrayListUnmanaged(ChoiceNode) = .empty,54    spans: std.ArrayListUnmanaged(Span) = .empty,55    byte_blocks: std.ArrayListUnmanaged(u8) = .empty,56    targets: std.ArrayListUnmanaged(TargetObservation) = .empty,57    span_depth: usize = 0,58    status: Status = .valid,59    max_choices: usize = 4096,60    max_input_bytes: usize = default_max_input_bytes,6162    prng: std.Random.DefaultPrng,6364    replay_choices: ?[]const ChoiceNode = null,65    replay_byte_blocks: ?[]const u8 = null,66    replay_index: usize = 0,67    replay_byte_offset: usize = 0,6869    allocator: Allocator,7071    pub fn init(allocator: Allocator, seed: u64) ConjectureData {72        return .{73            .prng = std.Random.DefaultPrng.init(seed),74            .allocator = allocator,75        };76    }7778    pub fn initReplay(79        allocator: Allocator,80        replay_choices: []const ChoiceNode,81        replay_byte_blocks: ?[]const u8,82    ) ConjectureData {83        return .{84            .prng = std.Random.DefaultPrng.init(0),85            .replay_choices = replay_choices,86            .replay_byte_blocks = replay_byte_blocks,87            .allocator = allocator,88        };89    }9091    pub fn deinit(self: *ConjectureData) void {92        self.clearTargets();93        self.choices.deinit(self.allocator);94        self.spans.deinit(self.allocator);95        self.byte_blocks.deinit(self.allocator);96        self.targets.deinit(self.allocator);97    }9899    pub fn beginSpan(self: *ConjectureData, label: []const u8) !void {100        try self.spans.append(self.allocator, .{101            .label = label,102            .start = self.choices.items.len,103            .end = 0,104            .depth = self.span_depth,105        });106        self.span_depth += 1;107    }108109    pub fn endSpan(self: *ConjectureData) void {110        std.debug.assert(self.span_depth > 0);111        self.span_depth -= 1;112        var i = self.spans.items.len;113        while (i > 0) {114            i -= 1;115            if (self.spans.items[i].depth == self.span_depth and116                self.spans.items[i].end == 0)117            {118                self.spans.items[i].end = self.choices.items.len;119                return;120            }121        }122    }123124    pub fn drawInteger(125        self: *ConjectureData,126        min: u64,127        max: u64,128        shrink_towards: u64,129    ) DrawError!u64 {130        if (self.choices.items.len >= self.max_choices) {131            self.status = .overrun;132            return DrawError.Overrun;133        }134135        const value = if (self.replay_choices) |replay| blk: {136            if (self.replay_index >= replay.len) {137                self.status = .overrun;138                return DrawError.Overrun;139            }140            const node = replay[self.replay_index];141            self.replay_index += 1;142            break :blk node.value;143        } else blk: {144            if (min == max) break :blk min;145            const range = max -% min;146            break :blk min +% self.prng.random().intRangeAtMost(u64, 0, range);147        };148149        const clamped = @min(@max(value, min), max);150151        try self.choices.append(self.allocator, .{152            .kind = .integer,153            .value = clamped,154            .min = min,155            .max = max,156            .shrink_towards = shrink_towards,157        });158159        return clamped;160    }161162    pub fn drawBoolean(self: *ConjectureData) DrawError!bool {163        const value = try self.drawInteger(0, 1, 0);164        return value != 0;165    }166167    pub fn drawFloat(168        self: *ConjectureData,169        min: f64,170        max: f64,171    ) DrawError!f64 {172        if (self.choices.items.len >= self.max_choices) {173            self.status = .overrun;174            return DrawError.Overrun;175        }176177        const value = if (self.replay_choices) |replay| blk: {178            if (self.replay_index >= replay.len) {179                self.status = .overrun;180                return DrawError.Overrun;181            }182            const node = replay[self.replay_index];183            self.replay_index += 1;184            break :blk @as(f64, @bitCast(node.value));185        } else blk: {186            const r = self.prng.random();187            const unit: f64 = @as(f64, @floatFromInt(r.int(u52))) /188                @as(f64, @floatFromInt(@as(u52, std.math.maxInt(u52))));189            break :blk min + unit * (max - min);190        };191192        const clamped = @min(@max(value, min), max);193194        try self.choices.append(self.allocator, .{195            .kind = .float,196            .value = @bitCast(clamped),197            .min = @bitCast(min),198            .max = @bitCast(max),199            .shrink_towards = @bitCast(@as(f64, 0.0)),200        });201202        return clamped;203    }204205    pub fn drawBytes(206        self: *ConjectureData,207        min_size: usize,208        max_size: usize,209    ) DrawError![]const u8 {210        const len = try self.drawInteger(211            @intCast(min_size),212            @intCast(max_size),213            @intCast(min_size),214        );215216        const start = self.byte_blocks.items.len;217        const size: usize = @intCast(len);218        std.debug.assert(start <= self.max_input_bytes);219        if (size > self.max_input_bytes - start) {220            self.status = .overrun;221            return DrawError.Overrun;222        }223224        if (self.replay_byte_blocks) |replay_bytes| {225            if (self.replay_byte_offset + size > replay_bytes.len) {226                self.status = .overrun;227                return DrawError.Overrun;228            }229            try self.byte_blocks.appendSlice(230                self.allocator,231                replay_bytes[self.replay_byte_offset..][0..size],232            );233            self.replay_byte_offset += size;234        } else {235            try self.byte_blocks.ensureUnusedCapacity(self.allocator, size);236            for (0..size) |_| {237                self.byte_blocks.appendAssumeCapacity(238                    self.prng.random().int(u8),239                );240            }241        }242243        return self.byte_blocks.items[start..][0..size];244    }245246    pub fn forceInteger(self: *ConjectureData, value: u64) DrawError!void {247        if (self.choices.items.len >= self.max_choices) {248            self.status = .overrun;249            return DrawError.Overrun;250        }251        try self.choices.append(self.allocator, .{252            .kind = .integer,253            .value = value,254            .min = value,255            .max = value,256            .shrink_towards = value,257            .was_forced = true,258        });259    }260261    pub fn target(self: *ConjectureData, observation: anytype, label: []const u8) TargetError!void {262        const value = targetValue(@TypeOf(observation), observation);263        if (!std.math.isFinite(value)) return TargetError.NonFiniteTarget;264        for (self.targets.items) |existing| {265            if (std.mem.eql(u8, existing.label, label)) {266                return TargetError.DuplicateTargetLabel;267            }268        }269        const owned_label = try self.allocator.dupe(u8, label);270        errdefer self.allocator.free(owned_label);271        try self.targets.append(self.allocator, .{272            .label = owned_label,273            .value = value,274        });275    }276277    pub fn targetDefault(self: *ConjectureData, observation: anytype) TargetError!void {278        return self.target(observation, "");279    }280281    pub fn markInteresting(self: *ConjectureData) void {282        self.status = .interesting;283    }284285    pub fn markInvalid(self: *ConjectureData) void {286        self.status = .invalid;287    }288289    pub fn reset(self: *ConjectureData, seed: u64) void {290        self.clearTargets();291        self.choices.clearRetainingCapacity();292        self.spans.clearRetainingCapacity();293        self.byte_blocks.clearRetainingCapacity();294        self.span_depth = 0;295        self.status = .valid;296        self.prng = std.Random.DefaultPrng.init(seed);297        self.replay_choices = null;298        self.replay_byte_blocks = null;299        self.replay_index = 0;300        self.replay_byte_offset = 0;301    }302303    pub fn resetReplay(304        self: *ConjectureData,305        replay_choices: []const ChoiceNode,306        replay_byte_blocks: ?[]const u8,307    ) void {308        self.clearTargets();309        self.choices.clearRetainingCapacity();310        self.spans.clearRetainingCapacity();311        self.byte_blocks.clearRetainingCapacity();312        self.span_depth = 0;313        self.status = .valid;314        self.replay_choices = replay_choices;315        self.replay_byte_blocks = replay_byte_blocks;316        self.replay_index = 0;317        self.replay_byte_offset = 0;318    }319320    fn clearTargets(self: *ConjectureData) void {321        for (self.targets.items) |target_observation| {322            self.allocator.free(target_observation.label);323        }324        self.targets.clearRetainingCapacity();325    }326};327328pub fn target(data: *ConjectureData, observation: anytype, label: []const u8) TargetError!void {329    return data.target(observation, label);330}331332fn targetValue(comptime T: type, value: T) f64 {333    return switch (@typeInfo(T)) {334        .int, .comptime_int => @floatFromInt(value),335        .float, .comptime_float => @floatCast(value),336        else => @compileError("target observation must be an integer or float"),337    };338}339340test "drawInteger produces values in range" {341    const allocator = std.testing.allocator;342    var data = ConjectureData.init(allocator, 42);343    defer data.deinit();344345    for (0..100) |_| {346        const v = try data.drawInteger(10, 20, 10);347        try std.testing.expect(v >= 10 and v <= 20);348    }349}350351test "drawBoolean produces booleans" {352    const allocator = std.testing.allocator;353    var data = ConjectureData.init(allocator, 42);354    defer data.deinit();355356    var saw_true = false;357    var saw_false = false;358    for (0..100) |_| {359        const v = try data.drawBoolean();360        if (v) saw_true = true else saw_false = true;361    }362    try std.testing.expect(saw_true and saw_false);363}364365test "target records finite labeled observations" {366    const allocator = std.testing.allocator;367    var data = ConjectureData.init(allocator, 42);368    defer data.deinit();369370    try data.target(12, "size");371    try data.target(-3.5, "distance");372373    try std.testing.expectEqual(@as(usize, 2), data.targets.items.len);374    try std.testing.expectEqualStrings("size", data.targets.items[0].label);375    try std.testing.expectEqual(@as(f64, 12.0), data.targets.items[0].value);376    try std.testing.expectEqualStrings("distance", data.targets.items[1].label);377    try std.testing.expectEqual(@as(f64, -3.5), data.targets.items[1].value);378}379380test "target rejects duplicate labels and non-finite observations" {381    const allocator = std.testing.allocator;382    var data = ConjectureData.init(allocator, 42);383    defer data.deinit();384385    try data.target(1, "score");386    try std.testing.expectError(TargetError.DuplicateTargetLabel, data.target(2, "score"));387    try std.testing.expectError(TargetError.NonFiniteTarget, data.target(std.math.inf(f64), "inf"));388}389390test "replay reproduces values" {391    const allocator = std.testing.allocator;392393    var gen = ConjectureData.init(allocator, 123);394    defer gen.deinit();395    const v1 = try gen.drawInteger(0, 100, 0);396    const v2 = try gen.drawInteger(0, 100, 0);397    const v3 = try gen.drawBoolean();398399    var replay = ConjectureData.initReplay(allocator, gen.choices.items, null);400    defer replay.deinit();401    try std.testing.expectEqual(v1, try replay.drawInteger(0, 100, 0));402    try std.testing.expectEqual(v2, try replay.drawInteger(0, 100, 0));403    try std.testing.expectEqual(v3, try replay.drawBoolean());404}405406test "overrun on too many choices" {407    const allocator = std.testing.allocator;408    var data = ConjectureData.init(allocator, 42);409    defer data.deinit();410    data.max_choices = 5;411412    for (0..5) |_| {413        _ = try data.drawInteger(0, 10, 0);414    }415    try std.testing.expectError(DrawError.Overrun, data.drawInteger(0, 10, 0));416    try std.testing.expectEqual(.overrun, data.status);417}418419test "span tracking" {420    const allocator = std.testing.allocator;421    var data = ConjectureData.init(allocator, 42);422    defer data.deinit();423424    try data.beginSpan("outer");425    _ = try data.drawInteger(0, 10, 0);426    try data.beginSpan("inner");427    _ = try data.drawInteger(0, 10, 0);428    data.endSpan();429    _ = try data.drawInteger(0, 10, 0);430    data.endSpan();431432    try std.testing.expectEqual(2, data.spans.items.len);433    try std.testing.expectEqual(1, data.spans.items[1].start);434    try std.testing.expectEqual(2, data.spans.items[1].end);435    try std.testing.expectEqual(1, data.spans.items[1].depth);436    try std.testing.expectEqual(0, data.spans.items[0].start);437    try std.testing.expectEqual(3, data.spans.items[0].end);438    try std.testing.expectEqual(0, data.spans.items[0].depth);439}440441test "drawFloat produces values in range" {442    const allocator = std.testing.allocator;443    var data = ConjectureData.init(allocator, 42);444    defer data.deinit();445446    for (0..100) |_| {447        const v = try data.drawFloat(-1.0, 1.0);448        try std.testing.expect(v >= -1.0 and v <= 1.0);449    }450}451452test "drawBytes produces bytes in size range" {453    const allocator = std.testing.allocator;454    var data = ConjectureData.init(allocator, 42);455    defer data.deinit();456457    for (0..20) |_| {458        const bs = try data.drawBytes(2, 8);459        try std.testing.expect(bs.len >= 2 and bs.len <= 8);460    }461}462463test "drawBytes rejects cumulative max input plus one without growing bytes" {464    var data = ConjectureData.init(std.testing.allocator, 42);465    defer data.deinit();466    data.max_input_bytes = 4;467    _ = try data.drawBytes(2, 2);468    _ = try data.drawBytes(2, 2);469    const pointer = data.byte_blocks.items.ptr;470    try std.testing.expectError(DrawError.Overrun, data.drawBytes(1, 1));471    try std.testing.expectEqual(Status.overrun, data.status);472    try std.testing.expectEqual(@as(usize, 4), data.byte_blocks.items.len);473    try std.testing.expectEqual(pointer, data.byte_blocks.items.ptr);474}

1pub const conjecture = @import("conjecture.zig");