Support inferred error sets in recursion

This is a proposal based on the question raised in #763. (If #763 is considered the tracking issue or the final word, please feel free to close this one -- I didn't interpret any of the comments there as conclusive.)

Thanks @rjtobin for resurfacing the issue in IRC.

Summary

If a call graph is recursive, a return type with inferred error set may trigger this compile error:

cannot resolve inferred error set 'glarf': function 'kloyp' not fully analyzed yet

If all functions in that cycle use inferred error sets, the error is guaranteed to happen.

pub fn main() void {
    f1(false) catch {};
}

fn f1(x: bool) !void { // recurses
    return if (x) error.Bad else f1(x);
}

fn f2(x: bool) !void { // recurses
    return if (x) f2(x) else error.Bad;
}

If at least one of the functions in the cycle has an inferred error set, the error may happen. Given this error set:

const E = error{Bad};

Changing f1 to return E!void prevents the error. Leaving f1 alone and instead changing f2 to return E!void does not prevent the error. The outcome may be deterministic or it may be based on the color of the giant spaghetti monster's mood ring, I dunno.

Proposal

Guarantee that inferred error sets are allowed even in cyclic call graphs.

Alternatives

Explicitly state that recursion is incompatible with inferred error sets. "Wait!" I hear you cry, "the documentation already says exactly that". It sure does, but it is also acknowledges that this limitation may be removed in the future. We just need to decide (eventually) whether to add support or officially make it unsupported for the language specification (#75).

Note: Currently, I am neutral on this enhancement. It's not blocking me. This issue is just meant to track it and aggregate potential use cases.

This is implemented and working in self-hosted, only thing left to close the issue is ensure we have behavior test coverage.

Note that this works for plain recursion, but not mutual recursion:

fn f() !void {
    try g(false);
}

fn g(b: bool) !void {
    if (b) {
        try f();
    } else {
        return error.Foo;
    }
}

comptime {
    _ = f; // or g
}

thing.zig:7:14: error: unable to resolve inferred error set
        try f();
            ~^~

This is implemented and working in self-hosted, only thing left to close the issue is ensure we have behavior test coverage.

I started working on this.

I found exactly one test in test/behavior/error.zig: https://github.com/ziglang/zig/blob/3b465ebec59ee942b6c490ada2f81902ec047d7f/test/behavior/error.zig#L969

test "try used in recursive function with inferred error set" {
    if (builtin.zig_backend == .stage2_aarch64) return error.SkipZigTest; // TODO
    if (builtin.zig_backend == .stage2_arm) return error.SkipZigTest; // TODO
    if (builtin.zig_backend == .stage2_spirv64) return error.SkipZigTest;

    const Value = union(enum) {
        values: []const @This(),
        b,

        fn x(value: @This()) !void {
            switch (value.values[0]) {
                .values => return try x(value.values[0]),
                .b => return error.a,
            }
        }
    };
    const a = Value{
        .values = &[1]Value{
            .{
                .values = &[1]Value{.{ .b = {} }},
            },
        },
    };
    try expectError(error.a, Value.x(a));
}

And created the following tests with the following results:

// PASSES (this is pretty much identical to the existing one test)
test "recursive function with inferred error set containing try of itself" {
    const S = struct {
        fn recurseNTimes(n: u8) !void {
            if (n > 10) return error.TooMuchRecursing;
            if (n == 0) return error.DoneRecursing;
            try recurseNTimes(n - 1);
        }
    };
    try expectError(error.DoneRecursing, S.recurseNTimes(5));
    try expectError(error.TooMuchRecursing, S.recurseNTimes(11));
}

// FAILS (should this succeed?)
// ```
//  test/behavior/error.zig:1012:34: error: unable to resolve inferred error set
//        recurseNTimes(n - 1) catch |err| switch (err) {
// ```
test "recursive function explicitly returning errors from switch of itself" {
    const S = struct {
        fn recurseNTimes(n: u8) !void {
            if (n > 10) return error.TooMuchRecursing;
            if (n == 0) return error.DoneRecursing;
            recurseNTimes(n - 1) catch |err| switch (err) {
                error.TooMuchRecursing => unreachable,
                error.DoneRecursing => return error.ReallyDoneRecursing,
                error.ReallyDoneRecursing => return error.ReallyDoneRecursing,
            };
        }
    };
    try expectError(error.ReallyDoneRecursing, S.recurseNTimes(5));
    try expectError(error.TooMuchRecursing, S.recurseNTimes(11));
}

// FAILS (expected since mutual recusive functions are not supported as pointed out by mlugg)
// ```
// test/behavior/error.zig:1045:33: error: unable to resolve inferred error set
//            try recurseNTimesFnA(n - 1);
// ```
test "mutual recursive functions returning inferred error set" {
    const S = struct {
        fn recurseNTimesFnA(n: u8) !void {
            if (n > 10) return error.TooMuchRecursing;
            if (n == 0) return error.DoneRecursing;
            try recurseNTimesFnB(n - 1);
        }
        fn recurseNTimesFnB(n: u8) !void {
            if (n > 10) return error.TooMuchRecursing;
            if (n == 0) return error.DoneRecursing;
            try recurseNTimesFnA(n - 1);
        }
    };

    try expectError(error.DoneRecursing, S.recurseNTimesFnA(5));
    try expectError(error.DoneRecursing, S.recurseNTimesFnB(5));
    try expectError(error.TooMuchRecursing, S.recurseNTimesFnA(11));
    try expectError(error.TooMuchRecursing, S.recurseNTimesFnB(11));
}

Should I open a PR to add these tests?
Should the second test (with the switch case) succeed?

ziglang / zig