Code guarded by `if (!<expression>)` incorrectly not executed under specific conditions

[iamfraggle]

Zig Version

0.9.0

Steps to Reproduce

zig init-exe Set src/main.zig to the code below zig build test

const std = @import("std");

const Board = struct {
    grid: [5][5]u8,
    marked: [5][5]bool = .{
        .{false}**5,
        .{false}**5,
        .{false}**5,
        .{false}**5,
        .{false}**5
    },
    complete: bool = false,

    pub fn construct(reader: anytype) ?Board {
        var buf: [15]u8 = undefined;
        var out: Board = undefined;
        _ = reader.readUntilDelimiterOrEof(&buf, '\n') catch return null;

        var i: u8 = 0;
        while (i < 5) : (i += 1) {
            var line = (reader.readUntilDelimiterOrEof(&buf, '\n') catch return null) orelse return null;

            var b: u8 = 0;
            var j: u8 = 0;
            while (j < 5) : ({j += 1; b += 3;}) {
                var slice = if (line[b] == ' ') line[b+1..b+2] else line[b+0..b+2];
                out.grid[i][j] = std.fmt.parseUnsigned(u8, slice, 10) catch return null;
            }
        }

        return out;
    }

    pub fn mark(self: *Board, call: u8) bool {
        if (self.complete) return false;

        for (self.grid) |row, y| {
            for (row) |val, x| {
                if (val == call) {
                    self.marked[y][x] = true;

                    var it: u8 = 0;
                    while (it < 5 and self.marked[y][it]) : (it += 1) {}
                    if (it == 5) {
                        self.complete = true;
                        return true;
                    }

                    it = 0;
                    while (it < 5 and self.marked[it][x]) : (it += 1) {}
                    if (it == 5) {
                        self.complete = true;
                        return true;
                    }
                    return false;
                }
            }
        }

        return false;
    }

    pub fn score(self: Board, call: u8) u32 {
        var unmarked: u32 = 0;
        for (self.grid) |row, y| {
            for (row) |cell, x| {
//                var include = !self.marked[y][x];       // To fix, uncomment
//                if (include) unmarked += cell;          // these lines
                if (!self.marked[y][x]) unmarked += cell; // and comment this one
            }
        }

        return unmarked * call;
    }
};

test "example test" {
    const boardtext = 
        \\
        \\22 13 17 11  0
        \\ 8  2 23  4 24
        \\21  9 14 16  7
        \\ 6 10  3 18  5
        \\ 1 12 20 15 19
        \\
        \\ 3 15  0  2 22
        \\ 9 18 13 17  5
        \\19  8  7 25 23
        \\20 11 10 24  4
        \\14 21 16 12  6
        \\
        \\14 21 17 24  4
        \\10 16 15  9 19
        \\18  8 23 26 20
        \\22 11 13  6  5
        \\ 2  0 12  3  7
        \\
    ;

    var reader = std.io.fixedBufferStream(boardtext).reader();

    var boards = [3]Board{
        Board.construct(reader).?,
        Board.construct(reader).?,
        Board.construct(reader).?,
    };

    const calls = [_]u8 {7,4,9,5,11,17,23,2,0,14,21,24,10,16,13,6,15,25,12,22,18,20,8,19,3,26,1};

    for (calls) |call| {
        for (boards) |*board| {
            if (board.mark(call)) {
                var result = board.score(call);
                try std.testing.expectEqual(result, 4512);
                return;
            }
        }
    }
}

Expected Behavior

Test [0/1] test "example test"... 1/1 test "example test"... OK

Actual Behavior

Test [0/1] test "example test"... 1/1 test "example test"... expected 0, found 4512

Any code guarded by the offending if (!<expression) does not get executed. Note that only if (!<expression) is affected if (<expression>) in the same scenario works correctly.

[iamfraggle]

Just thought to try the following which also fails:

var include = self.marked[y][x];
if (!include) unmarked += cell;

[iamfraggle]

I appear to have omitted a comment I intended to put in the code. The issue only triggers if Board has been created via Board.construct(). Instantiating Board manually bypasses the problem.

[squeek502]

There seems to be something strange going on, but I believe you're invoking undefined behavior.

In Board.construct you are doing:

var out: Board = undefined;

which can skip setting the default values for the marked and complete fields (the entire struct just gets initialized with 'undefined' memory). In Debug mode, this doesn't seem to happen (they appear to be set to false if you print them), but if you run the code in ReleaseFast and add std.debug.print("{}\n", .{out}); after the var out: Board = undefined line you get a mishmash of random values.

I think what might be happening is that there is some Debug-specific optimizations that are happening because the compiler knows that marked is undefined, and somehow the if (!self.marked[y][x]) is triggering that.

It's possible to verify this by running with Valgrind:

zig test 10479.zig -femit-bin 10479 --test-no-exec
valgrind ./10479 zig

...
==4113839== Conditional jump or move depends on uninitialised value(s)
==4113839==    at 0x208CFD: Board.mark (10479.zig:32)
==4113839==    by 0x207E0A: test "example test" (10479.zig:109)
==4113839==    by 0x231DE7: std.special.main (test_runner.zig:77)
==4113839==    by 0x22A44C: std.start.callMain (start.zig:543)
==4113839==    by 0x20ACEE: std.start.initEventLoopAndCallMain (start.zig:495)
==4113839==    by 0x20ACEE: std.start.callMainWithArgs (start.zig:445)
==4113839==    by 0x209626: std.start.posixCallMainAndExit (start.zig:409)
==4113839==    by 0x209432: _start (start.zig:322)
==4113839==    by 0x1: ???
==4113839==    by 0x1FFEFFFFD6: ???
==4113839==    by 0x1FFEFFFFDE: ???
...

(and the same error triggered by lines 40, 47, and 66)

The fix for your code would be to do:

var out: Board = .{ .grid = undefined };

thereby only setting the grid field to undefined, and allowing the rest of the fields to use their defaults.

---

Not sure about what (if anything?) should be done on the compiler's end.

EDIT: This seems to be the relevant proposal: https://github.com/ziglang/zig/issues/211

[iamfraggle]

Thanks for the explanation!