Endless loop in Semantic Analysis [x/y]

[ikskuh]

When compiling the following code, the compiler will run into an endless loop trying to analyze whatever it is to analyze:

const std = @import("std");

const Value = union(enum) {
    array: Array,
    item: i32,

    /// Checks if two values are equal.
    pub fn format(value: @This(), comptime fmt: []const u8, options: std.fmt.FormatOptions, context: var, comptime Errors: type, comptime output: fn (@TypeOf(context), []const u8) Errors!void) Errors!void {
        return switch (value) {
            .item => |i| std.fmt.format(context, Errors, output, "{d}", .{i}),
            .array => |array| {
                for (array) |item| {
                    try std.fmt.format(context, Errors, output, " {}", .{item}); // <= @0 will analyze forever
                    // try format(item, fmt, options, context, Errors, output); // <= @1 works
                }
                // try arrayFormat(array, context, Errors, output); // @2 works as well
            },
        };
    }

    fn arrayFormat(array: Array, context: var, comptime Errors: type, comptime output: fn (@TypeOf(context), []const u8) Errors!void) Errors!void {
        for (array) |item| {
            try std.fmt.format(context, Errors, output, " {}", .{item}); // <= @2 works as well
        }
    }
};

const Array = []const Value;

test "will analyze forever" {
    const v: Value = Value{ .item = 1 };
    std.debug.warn("{}\n", .{v}); // this will call `format` on our struct
}

This code will run into an endless loop of semantic analysis when using variant @0:

[felix@denkplatte-v2 bugreports]$ zig test recursion-error.zig 
Semantic Analysis [3552/5909] ^C

It will run when using variant @1 (using direct recursion) or variant @2 (calling a function that will call the formatter)

Zig version: 0.5.0+330e30aec

[joachimschmidt557]

I don't know if it's related, but compiling https://github.com/andrewrk/tetris with zig build play also results in an infinite loop at compile time.

[joachimschmidt557]

It seems like the issue during compilation of https://github.com/andrewrk/tetris is not related to this.

[oatberry]

I am able to trigger this bug with this recursive .format() function: https://gist.github.com/oatberry/fc89cba8e3bdbeaf9e474949f838cc7a

[lemon32767]

As of zig 0.6.0+006b780d4, this bug is still present.
Here's another test case:

const std = @import("std");
const E = enum { Leaf, Branch };
const R = union(E) {
    Leaf: i32,
    Branch: struct { left: *const R, right: *const R },

    pub fn format(self: R, comptime fmt: []const u8, options: std.fmt.FormatOptions, writer: anytype) !void {
        return switch (self) {
            .Leaf => |n| std.fmt.format(writer, "Leaf({})", .{n}),
            .Branch => |b| std.fmt.format(writer, "Branch({}, {})", .{ b.left, b.right }),
        };
    }
};

test "∞" {
    const r: *const R = undefined; //runtime value here doesn't matter,
    std.debug.print("{}\n", .{r}); //infinite analysis loop
}

A possible work-around is to replace the recursive algorithm with an iterative one, like so:

const std = @import("std");
const E = enum { Leaf, Branch };
const R = union(E) {
    Leaf: i32,
    Branch: struct { left: *const R, right: *const R },

    pub fn format(self: R, comptime fmt: []const u8, options: std.fmt.FormatOptions, writer: anytype) !void {
        var pool: [500]u8 = undefined;
        var allocator = &std.heap.FixedBufferAllocator.init(&pool).allocator;

        const FE = enum { r, s };
        const F = union(FE) {
            r: *const R, //actual value
            s: []const u8, //some string to print
        };
        var stack = std.ArrayList(F).init(allocator);
        var val: F = .{ .r = &self };

        while (true) {
            switch (val) {
                .r => |r| switch (r.*) {
                    .Leaf => |n| {
                        try std.fmt.format(writer, "Leaf({})", .{n});
                    },
                    .Branch => |*b| {
                        try std.fmt.format(writer, "Branch(", .{});
                        //pushed in reverse order to how they'll be printed
                        stack.append(.{ .s = ")" }) catch unreachable;
                        stack.append(.{ .r = b.right }) catch unreachable;
                        stack.append(.{ .s = ", " }) catch unreachable;
                        stack.append(.{ .r = b.left }) catch unreachable;
                    },
                },
                .s => |s| try std.fmt.format(writer, "{}", .{s}),
            }

            if (stack.items.len == 0) break;
            val = stack.pop();
        }
    }
};

test "✓" {
    const r = &R{
        .Branch = .{
            .left = &R{
                .Branch = .{
                    .left = &R{ .Leaf = 3 },
                    .right = &R{
                        .Branch = .{
                            .left = &R{ .Leaf = 0 },
                            .right = &R{ .Leaf = 9 },
                        },
                    },
                },
            },
            .right = &R{
                .Branch = .{
                    .left = &R{ .Leaf = -1 },
                    .right = &R{ .Leaf = 99 },
                },
            },
        },
    };
    //output: Branch(Branch(Leaf(3), Branch(Leaf(0), Leaf(9))), Branch(Leaf(-1), Leaf(99)))
    std.debug.print("{}\n", .{r});
}

Though this gets quite unwieldy.