zig comptime memoization broken with comptime slices

[marler8997]

The following code will cause the compiler to go into an infinite function instantiation loop when compiling with zig build-exe bug.zig:

const std = @import("std");

fn comptimeFun(comptime s: []const u8) void {
    @compileLog("comptimeFun with ", s);
    // note: this next line causes the issue
    comptimeFun(s ++ "");
    // note: if we replace the line above with `comptimeFun(s)` then the infinite loop goes away
    // note: the issue also manifests with: comptimeFun(s ++ "something")[0..s.len]);
}

pub fn main() void {
    comptimeFun("foo");
}

The problem here is that when Zig checks whether comptimeFun("foo") has already been instantiated, it's not seeing that slices with the same contents are equivalent. So even though comptimeFun is always called with the same comptime string "foo", it doesn't see them as equivalent so it just keeps instantiating them forever.

[mikdusan]

hmm narrowed to something to do with array operators?

redux.zig

fn comptimeFun(comptime s: []const u8) void {
    @compileLog("comptimeFun with ", s);
}

export fn foo() void {
    comptimeFun( ("foo" ++ "something")[0..3] );
    comptimeFun( ("foo" ++ "something")[0..3] );
    comptimeFun( ("foo" ** 2)[0..3] );
    comptimeFun( ("foo" ** 2)[0..3] );

    comptimeFun( "foosomething"[0..3] ); // these 2 use same fn instance
    comptimeFun( "foosomething"[0..3] ); // ^^
}

zig build-obj redux.zig

| *"comptimeFun with ", []const u8{102,111,111}
| *"comptimeFun with ", []const u8{102,111,111}
| *"comptimeFun with ", []const u8{102,111,111}
| *"comptimeFun with ", []const u8{102,111,111}
| *"comptimeFun with ", "foo"

[LemonBoy]

it's not seeing that slices with the same contents are equivalent

Why would it? You're creating brand new slices with different comptime pointers (++ and ** allocate a brand new object) and same length, that's why it keeps recursing.

[mikdusan]

True. While the content of the slice may compare equal, and slice.len is equal, slice.ptr has changed.

[ifreund]

I've hit a similar issue with the memoization before without any ++ or ** involved. Unable to isolate a test case though:

./river/Root.zig:103:59: error: expected type
'.wayland.wayland_server_core.list.Head(.wlroots.types.output_layout.Output,"link").Iterator(.wayland.wayland_server_core.Direction.forward)', found
'.wayland.wayland_server_core.list.Head(.wlroots.types.output_layout.Output,"link").Iterator(.wayland.wayland_server_core.Direction.forward)'

    return .{ .inner = self.output_layout.outputs.iterator(dir) };
                                                          ^
./river/InputManager.zig:153:54: note: called from here
    var output_it = self.server.root.outputLayoutIter(.forward);
                                                     ^
./river/InputManager.zig:144:8: note: called from here
) void {
       ^
./zig-cache/zig-wayland/wayland_server_core.zig:413:24: note: .wayland.wayland_server_core.list.Head(.wlroots.types.output_layout.Output,"link").Iterator(.wayland.wayland_server_core.Direction.forward) declared here
                return struct {
                       ^
./zig-cache/zig-wayland/wayland_server_core.zig:413:24: note: .wayland.wayland_server_core.list.Head(.wlroots.types.output_layout.Output,"link").Iterator(.wayland.wayland_server_core.Direction.forward) declared here
                return struct {
                       ^

code on this branch: https://github.com/ifreund/river/tree/output-refactor

[marler8997]

@LemonBoy they actually have the same pointer as well. Check it out:

fn comptimeFun(comptime s: []const u8) void {
    @compileLog("s is ", s, " and s.ptr is ", s.ptr);
}

pub fn main() void {
    comptimeFun("foo");
    comptimeFun("foo" ++ "");
}

$ zig build-exe bug.zig
| *"s is ", []const u8{102,111,111}, *" and s.ptr is ", *102
| *"s is ", []const u8{102,111,111}, *" and s.ptr is ", *102

This will instantiate competimeFun twice (you'll see 2 compileLogs), however, if you remove the ++ "" from the second call, it will only be instantiated once.

fn comptimeFun(comptime s: []const u8) void {
    @compileLog("s is ", s, " and s.ptr is ", s.ptr);
}

pub fn main() void {
    comptimeFun("foo");
    comptimeFun("foo");
}

$ zig build-exe bug.zig
| *"s is ", "foo", *" and s.ptr is ", *102

[marler8997]

Even if the strings did not have the same pointer (which it looks like they do in at least some cases), it's problematic to instantiate different functions with strings that have the same content but different comptime pointers. For example, this would mean that if you did want to guarantee that a comptime string doesn't cause a new instantiation of a function, then passing string literals directly to comptime strings would be a code hazard:

pub fn foo(comptime s: []const u8) void {
    //...
}


foo("hello"); // this is now a code hazard

// now every time you pass a comptime string to a function, you'll want to define a const string literal like this
// so that every instance is referencing the exact same string
const hello = "hello"; // defined somewhere common
foo(hello);

This also means that if you want to allow memorization to work with dynamic strings built at comptime, you're going to have to implement you're own memoization:

foo("a" ++ "b"); // code hazard

const ab = comptime_string_memoizer.get("a" ++ "b");
foo(ab);

For a real-world example, I can't use "any" string literals in fmt.zig. It causes the compiler to enter an infinite recursion of function instantiations. So instead, I have to create a constant const ANY = "any" (see https://github.com/ziglang/zig/pull/7676/files#diff-b2dd3e0e31147e6adc31a9099c0967f22e1c5fa2f6bdd7a65b00528e9bab976fR398)

One way zig can solve this is by making sure that all comptime strings with the same content get resolved to the same string (with the same pointer). The other way is to base string comparison for the purposes of memoization on content, however, this would also mean that Zig should now allow the ptr field to be used in code working with comptime strings.

[LemonBoy]

they actually have the same pointer as well.

No, they're not.
Watch this:

fn comptimeFun(comptime s: []const u8) void {
    @compileLog(s.ptr);
}

pub fn main() void {
    comptimeFun("foo");  // prints "*102"
    comptimeFun("fee"); // prints "*102"
}

What you're seeing is a * followed by the first item in the string rendered as an integer.

[zigazeljko]

Regardless of memoization, shouldn't this fail because of comptime branch quota?

[SpexGuy]

This is a design flaw. Memoization behavior may not ever traverse pointers (or it might, for now we haven't decided how it should behave), but the compiler should not be able to have an infinite loop. This isn't caught by the eval branch quota because function instantiation creates a new context with a new quota, so the limit is never reached. Going to mark this as a bug and tag it "use case", to make sure it is visible to searches for design meeting topics.

[SpexGuy]

We discussed this in a design meeting. First, we need a way to prevent this loop:

1. Add a global instantiation limit, which is configured in a similar way to builtin.panic (can be overridden in the root file).
2. Any time a generic function is instantiated, the instantiation count for that function is incremented.
3. If the instantiation count for any function exceeds the limit, a compile error is issued.

This turns the compiler crash into a compile error, but it also seems like this memoization should succeed when possible. We'll do so as follows:

1. Comptime constants are always deduplicated. If you inspect the address of "foo", it is guaranteed to be the same as the address of a different "foo" elsewhere in the program. "foo" ++ "" == "foo" will always be true under this rule. However only whole regions are deduplicated. "foo" == "foobar"[0..3] will always be false. But "foobar"[0..3] == "foobar"[0..3] will always be true.
2. When a comptime var memory region becomes const, it is deduplicated. This happens when the var goes out of scope, and also if the address of a var is closed over. Which is what happens when a function is instantiated with a slice parameter.
3. Comptime parameters which are slices over const regions are memoized according to the deduplicated memory region they reference, in addition to their offset and length.

So as an example,

fn foo(comptime str: []const u8) void {
    const buf = str[0..str.len].*;
    foo(&buf); // if str is a whole memory region, this is equal to it.
}
export fn bar() {
    comptime var var_string = "string".*;
    foo(var_string[3..]); // var_string becomes immutable here
    foo("ing");
    foo("string");
}

Produces the following set of constants and instantiations (in an impromptu IR pseudocode):

%1 = "string\0"
%2 = addressof %1 + 0 // &"string\0"
%3 = addressof %1 + 3 // &"string\0" + 3
%4 = []u8 { %3, 3 }   // "string\0"[3..6]
%5 = "ing\0"
%6 = addressof %5 + 0 // &"ing\0"
%7 = []u8 { %6, 3 }   // "ing\0"[0..3]
%8 = []u8 { %1, 6 }   // "string\0"[0..6]
%9 = foo(%7):         // foo("ing\0"[0..3])
    call %9           //   call foo("ing\0"[0..3]) runtime recursion
%10 = foo(%4):        // foo("string\0"[3..6]):
    call %9           //   call foo("ing\0"[0..3]) recursive instantiation
%11 = foo(%8):        // foo("string\0"[0..6]):
    call %11          //   call foo("string\0"[0..6]) runtime recursion
%12 = export bar():   // bar():
    call %10          //   call foo("string\0"[3..6])
    call %9           //   call foo("ing\0"[0..3])
    call %11          //   call foo("string\0"[0..6])

[marler8997]

I feel like de-duplicating string constants fixes this issue for some cases but not for others.

In most cases, I think when people write a function that accepts comptime s: []const u8, the semantics they mean are they want to instantiate only 1 instance for every string whose contents are the same. So the following should instantiate the same instance:

foo("any");
foo("{any}"[1..4]);

I believe it was @ifreund who pointed out Zig can do this today, like this:

fn foo(comptime s: anytype) void {
    fooImpl(s.len, s.*);
}
fn fooImpl(comptime size: usize, comptime s: [size]u8) void {
}

Maybe this is good enough? I'm not sure though. What would people say if we used this method on all the comptime s: []const u8 in std? I believe this pattern better represents developer's intentions in the majority of cases, but having to create a wrapper function like this is discouraging. It's possible we could come up with a proposal to make this mechanism easier to use. I believe it's worth considering because it would make it "easier to write correct code". Otherwise, some may continue to use comptime s: []const u8 even if it's not semantically correct because it's just easier.

P.S. I actually can't think of a case where the current semantics of comptime s: []const u8 would be the "correct code" matching the developer's intention...