`StaticStringMap` evaluation branch quota too low

[zhylmzr]

Zig Version

0.13.0-dev.47+c231d9496

Steps to Reproduce and Observed Behavior

const std = @import("std");
const TypeToByteSizeLUT = std.StaticStringMap(u32).initComptime(.{
    .{ "bool", 0 },
    .{ "c_int", 0 },
    .{ "c_long", 0 },
    .{ "c_longdouble", 0 },
    .{ "t20", 0 },
    .{ "t19", 0 },
    .{ "t18", 0 },
    .{ "t17", 0 },
    .{ "t16", 0 },
    .{ "t15", 0 },
    .{ "t14", 0 },
    .{ "t13", 0 },
    .{ "t12", 0 },
    .{ "t11", 0 },
    .{ "t10", 0 },
    .{ "t9", 0 },
    .{ "t8", 0 },
    .{ "t7", 0 },
    .{ "t6", 0 },
    .{ "t5", 0 },
    .{ "t4", 0 },
    .{ "t3", 0 },
    .{ "t2", 0 },
    .{ "t1", 0 },
});

pub fn main() void {
    _ = TypeToByteSizeLUT.kvs;
}

The above example results in error: evaluation exceeded 1000 backwards branches, you can change any key name you want and it may or may not compile. Or you can change the order of t20 ~ t1 to t1 ~ t20 and it will compile.

Expected Behavior

Compile success.

[mlugg]

This behaviour is not a bug, and is documented in the language reference. In essence, comptime code evaluation "gives up" after a certain number of backwards control flow branches, since it is impossible to know whether comptime code will terminate. Use @setEvalBranchQuota to increase the limit:

const TypeToByteSizeLUT = lut: {
    @setEvalBranchQuota(2000); // example; increase further if this still fails
    break :lut std.StaticStringMap(u32).initComptime(.{
        .{ "bool", 0 },
        .{ "c_int", 0 },
        .{ "c_long", 0 },
        .{ "c_longdouble", 0 },
        .{ "t20", 0 },
        .{ "t19", 0 },
        .{ "t18", 0 },
        .{ "t17", 0 },
        .{ "t16", 0 },
        .{ "t15", 0 },
        .{ "t14", 0 },
        .{ "t13", 0 },
        .{ "t12", 0 },
        .{ "t11", 0 },
        .{ "t10", 0 },
        .{ "t9", 0 },
        .{ "t8", 0 },
        .{ "t7", 0 },
        .{ "t6", 0 },
        .{ "t5", 0 },
        .{ "t4", 0 },
        .{ "t3", 0 },
        .{ "t2", 0 },
        .{ "t1", 0 },
    });
};

[travisstaloch]

I'm wondering if this issue should be re-opened. The limit was previously hard coded at 1500 but I changed it in that PR to be dependent on kvs_list.len. The multiplier 30 was chosen arbitrarily by me to be just big enough to satisfy the test and benchmark requirements. So I'm surprised this fairly small kvs_list triggered the compile error since i tested with larger kvs_lists and included a test case with 1000 keys.

The error doesn't make sense to me. Could it be different because the map is declared at container level?

Let me know and I'll gladly submit a follow up PR to increase the limit. I was planning to follow up soon with some documentation changes anyway which were discussed at the end of that PR.

[zhylmzr]

Yes, i can fix it with @setEvalBranchQuota.

I was curious as to why changing the key name would result in different behavior, and by looking at the internal implementation I found that it used std.sort.pdqContext to sort the keys, which is unstable and has O(n*log(n)) time complexity in the worst case, which at this point could result in the total number of iterations at comptime exceeding 1,000 at this point.

This is an example of unstable sorting causing the comptime limit to be exceeded a limited number of times.

[Pyrolistical]

This isn't fixed for me. Need https://github.com/ziglang/zig/issues/19525#issuecomment-2119039817