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...

[andrewrk]

Here are two ways I want to investigate solving this problem, which if I understand correctly are distinct from both #8839 and #8846. They both rely on the new inline function semantics which are already implemented in self-hosted.

Idea 1: Canonicalize Types

/// This function is marked inline and its body is all comptime stuff except for
/// the call to format2 which will happen with modified `args` that has canonicalized
/// types to avoid runtime bloat.
inline fn format(comptime fmt: []const u8, args: anytype) void {
    var args2: FmtArgs(@TypeOf(args)) = undefined;
    inline for (@typeInfo(@TypeOf(args)).Struct.fields) |field| {
        @field(args2, field.name) = @field(args, field.name);
    }
    // Here we call the actual format logic, with similar types folded
    // into canonical ones, and comptime values converted to runtime values.
    return format2(fmt, &args2);
}

/// Returns a tuple with the same field types, except with some types replaced
/// with canonical types that are formatted the same way.
fn FmtArgs(T: type) type {
    var field_types: [@typeInfo(T).Struct.fields.len]type = undefined;
    inline for (@typeInfo(T).Struct.fields) |field, i| {
        field_types[i] = FmtField(field.field_type);
    }
    return @Tuple(field_types);
}

/// `[N]T`, `[:s]T`, `[]T`, `*[N]T` are converted to `[]const T`.
/// Smaller numeric types are converted to larger ones.
fn FmtField(T: type) type {
    return switch (@typeInfo(T)) {
        .Array => |array| []const array.child_type,
        .Pointer => |ptr| switch (ptr.size) {
            .Many => {
                if (ptr.sentinel != null) {
                    return []const ptr.child_type;
                }
                return T;
            },
            .One => switch (@typeInfo(ptr.child_type)) {
                .Array => |array| return []const array.child_type,
                else => T,
            },
            .Slice, .C => []const ptr.child_type,
        },
        .Int => |int| {
            switch (int.signedness) {
                .signed => {
                    if (int.bits <= 64) return i64;
                    if (int.bits <= 128) return i128;
                    if (int.bits <= 256) return i256;
                },
                .unsigned => {
                    if (int.bits <= 63) return i64;
                    if (int.bits <= 64) return u64;
                    if (int.bits <= 127) return i128;
                    if (int.bits <= 128) return u128;
                    if (int.bits <= 255) return i256;
                    if (int.bits <= 256) return u256;
                },
            }
            return T;
        },

        .ComptimeInt => i64,
        .ComptimeFloat => f64,

        .Float => |float| {
            if (float.bits <= 64) return f64;
            return f128;
        },

        else => T,
    };
}

/// This function is called with canonicalized arguments to "fold" many similar types
/// into the same one, and to convert comptime values into runtime values.
fn format2(comptime fmt: []const u8, args: anytype) void {
    // TODO: do the actual formatting
    _ = fmt;
    _ = args;
}

Idea 2: Comptime Check, Runtime Format

I think this is even better. Idea here is that there is an inline fn that does the format checking, and converts the args tuple into a tuple that can hold runtime values, and stuffs the args into that new tuple. Then it calls the function that does the actual formatting, with runtime-known arguments, meaning there is absolutely no generic function instantiations happening.

So with this strategy it would be equivalent to C printf, where you pay the cost (in terms of binary bloat) of formatted printing exactly once, but every successive call to formatted printing is free. Key difference, of course, being that the checking for formatted printing is still implemented outside the compiler, unlike C printf.

The one thing that we may consider doing is having a global way to opt-out (or in?) of some kinds of printing. For example, maybe there is a way to globally disable printing of f128 values since that could involve a bit of runtime bloat. Something like pub const enable_std_fmt_f128 = false; in the root source file. If any call to formatted printing then tried to print an f128, it would cause a compile error.

/// This function is marked inline and its body is all comptime stuff except for
/// the call to `formatRuntime` which is a non-generic function!
pub inline fn format(comptime fmt: []const u8, args: anytype) void {
    var args2: FmtArgs(@TypeOf(args)) = undefined;
    // Convert comptime stuff to runtime stuff.
    inline for (@typeInfo(@TypeOf(args)).Struct.fields) |field| {
        @field(args2, field.name) = @field(args, field.name);
    }
    // TODO: validate `fmt` string. maybe choose a different encoding?
    return formatRuntime(fmt, &args2);
}

/// Returns a tuple with the same field types, except with some types replaced
/// with canonical types that are formatted the same way.
fn FmtArgs(T: type) type {
    var field_types: [@typeInfo(T).Struct.fields.len]type = undefined;
    inline for (@typeInfo(T).Struct.fields) |field, i| {
        field_types[i] = switch (@typeInfo(field.field_type)) {
            .ComptimeInt => i64, // TODO pick the smallest runtime int that works
            .ComptimeFloat => f64, // TODO pick the smallest runtime float that works
            else => field.field_type, // No need to canonicalize for this strategy
        };
    }
    return @Tuple(field_types);
}

/// Note that both parameters here are runtime known. No generic function bloat!
fn formatRuntime(fmt: []const u8, args: *const anyopaque) void {
    for (fmt) |byte| {
        // TODO: using the fmt string, access `args`. It's safe because `format` has
        // already validated it!
        _ = byte;
        _ = args;
    }
}

---

Edit: forgot to mention, my actual proposal for solving this problem is to remove support for a format method. I think it is a design flaw.

[RetroDev256]

I no longer see this on master. Am I correctly testing this?

Here is my attempt to reproduce:

Here is where the issue was brought to my attention: (std.fmt, line 454)

[Vexu]

This and the other issue were probably fixed by the introduction of InternPool. The issues can be closed by adding a behavior test for them.

[rohlem]

@Vexu The behavior of the minimal repro has changed in status-quo, but imo the spec question of what should happen hasn't been answered. It's not clear whether x ++ "" is allowed to return a slice with result.ptr != x.ptr. (This might also depend on whether x gains a null-terminator from the operation.) I'd like it if at least one of the issues was kept open for further discussion.