Proposal to improve the ergonomics and precision of type inference in generic functions

[zzyxyzz]

Problem

Generic functions, as currently supported in Zig have the form

fn eql(x: anytype, y: @TypeOf(x)) bool {
    return x == y;
}

This works well enough in general, but also has some problems and limitations:

1. Aesthetics

Besides the controversial keyword (#5893), the @TypeOf pattern is a bit of a hack, even though everybody is used to it by now. It somewhat obscures the fact that eql takes two arguments of the same type. It also leads to unnecessary verbosity in some cases:

fn foo(x: anytype, y: @TypeOf(x)) Container(@TypeOf(x)) {
    const T = @TypeOf(x);
    ...
}

2. Type signatures

The type of a simple function like same(x: i32, y: i32) bool {...}, is fn(i32, i32) bool. For the generic function eql, the intended type is something like fn<T>(T,T) bool. But the actual type inferred by the compiler seems to be fn(anytype,anytype) anytype. In my limited testing, I found that the compiler essentially considers all generic and parametric functions to have the same type. Only the number of arguments is checked. E.g., the following code compiles:

const eq: fn(anytype, f32) i32 = eql; // should have failed
assert(eq(1, 1));

It seems that the type check automatically simplifies to const eq: any_generic_function = eql;, which then succeeds. Maybe this is a limitation of the compiler that can be fixed independently, but then only in part. For example, the fact that both arguments of eql should have the same type is simply not expressible in the current system, since parameter names are not part of the type: fn(anytype, @TypeOf(?)) bool.

This state of affairs reduces the precision of type checks, and also discards valuable information that could be used by documentation generators, mataprogrammed interfaces and error messages.

3. Order dependence

Another minor nit is that generic functions constrain the order of function parameters in some cases. This, for example, is not possible:

fn find(haystack: ArrayList(@TypeOf(needle)), needle: anytype) usize {...} // error

The arguments need to be the other way round, although logically they can be in any order. This is an arbitrary, albeit minor, limitation.

Proposed solution

Change the fn(x: anytype) syntax to fn(x: infer T), which infers the type of x and binds it to T. Example:

// before:
fn eql(x: anytype, y: @TypeOf(x)) bool {...}
// after:
fn eql(x: infer T, y: T) bool {...}

// before:
fn find(needle: anytype, haystack: ArrayList(@TypeOf(needle))) usize {...}
// after:
fn find(needle: infer T, haystack: ArrayList(T)) usize {...}

This makes the intent much clearer, IMO. More importantly, the naming of inferred types allows us to talk about the types of generic functions with much greater precision:

// before:
eql: fn(anytype, anytype) anytype
// after:
eql: fn(infer T, T) bool

// before:
find: fn(anytype, anytype) anytype
// after:
find: fn(infer T, ArrayList(T)) usize

This forms the bare bones of the proposal, but there are additional possibilities that could be easily layered on top of it:

// Make type name optional:
fn wrapper(x: infer _) void { other_generic_function(x, 0); }

// Unrestrict order of inferred parameters:
fn find(haystack: ArrayList(T), needle: infer T) usize {...}
// Note: T can still only be inferred once, and only at a particular location, but it
// can be referred to before that. The procedure would be to resolve all infers first,
// and then use them in a second pass to finalize the types of the remaining arguments.

// Structural pattern matching on simple types:
fn foo(bar: ?*infer T, baz: []const T) bool {...}

// However, note that structural inference across custom types is not possible
// and will probably never be possible, because type constructors in Zig can be
// arbitrarily complex. 
fn convert(x: ArrayList(infer T)) HashSet(T) {...} // No can do. Use this instead:
fn convert(comptime T: type, x: ArrayList(T)) HashSet(T) {...}

Peer type resolution

Another straight-forward possibility is to allow peer type resolution, as suggested by @mlugg in this comment. Peer type resolution is enabled by using an infer with the same label more than once:

fn max(x: infer T, y: infer T) T {
    return if (x > y) x else y;
}

This allows us to call max(@as(u8, 5), @as(u16, 3)) and get a u16 as a result. If the function were instead declared as fn max(x: infer T, y: T) T { ... }, then a call with different argument types would be an error.

Nearly the same thing could be achieved by declaring fn max(x: infer _, y: infer _) @TypeOf(x, y) { ... }, but this is less nice syntactically. It may also lead to over-instantiation in some cases: max(u8, u16), max(u16, u8) and max(u16, u16) would produce separate instances. This can be avoided if the peer type resolution happens at the argument level and is not deferred to the return type calculation.

Similar proposals

This proposal is an improved (I hope) version of something suggested by @YohananDiamond here: #5893 (comment). Towards the end of the comment, the following is proposed:

fn max(generic a: T, b: T) T {
    return if (a > b) a else b;
}

In the same comment it is pointed out that this makes it somewhat unclear that T is being declared here. The present proposal addresses this shortcoming and generally makes it clear what and where exactly is inferred. It also leads to a more natural representation of the type of a generic function, but is otherwise only a minor reshuffling of keywords.

Edit: There's also the proposal #6997, which provides a partial solution to the type signature imprecision problem.

Summary

Advantages over status quo:

• Preserve more type information for docgen, metaprogramming and error messages
• Reduce visual noise and unintuitive keyword naming
• Express intent more clearly

Optionally also:

• Remove constraints on order of arguments
• Allow structural pattern matching without std.meta in simple cases

It should also be mentioned that inference remains simple and fully deterministic and does not open the door to template metaprogamming or some such.

[jedisct1]

This is a nice proposal, and indeed, having to systematically use @TypeOf() for this use case is a little bit cumbersome.

There wouldn't be a clear difference between anytype and infer, though. The only difference is that with infer, the type has a name, while with anytype, it doesn't.

So, I'm wondering if, instead of introducing a new keyword, we couldn't have anytype (perhaps renamed to infer if this improves clarity) require a name, which could be _ to discard it.

[ghost]

There wouldn't be a clear difference between anytype and infer, though. The only difference is that with infer, the type has a name, while with anytype, it doesn't.

So, I'm wondering if, instead of introducing a new keyword, we couldn't have anytype (perhaps renamed to infer if this improves clarity) require a name, which could be _ to discard it.

That's actually how I intended it. With this change anytype would no longer be allowed in function declarations. In principle, it's not even necessary to rename the keyword, as you say. The proposal could be changed to fn(x: anytype T, ...), but I thought if we are already changing syntax, then we can also change the keyword to something more appropriate.

[zigazeljko]

There wouldn't be a clear difference between anytype and infer, though. The only difference is that with infer, the type has a name, while with anytype, it doesn't.

There would be a difference. Since infer could be used inside a more complex type, it would allow pattern matching and creating type constraints.

[marler8997]

// However, note that structural inference across custom types is not possible // and will probably never be possible, because type constructors in Zig can be // arbitrarily complex and impure.

Oh it's definitely possible. All you need is a way to reverse the operation from a custom type to its input parameters. The compiler could maintain this mapping internally. Note this would only work for "custom types" though. This wouldn't work with non-custom types and would probably be mostly useless for them anyway:

fn foo(x: IgnoreTGiveMeU32(infer T)) void { }

fn IgnoreTGiveMeU32(comptime T: type) type { return u32; }

It's impossible to do this in the general case, unless all your functions are bijective mappings. Whether it's desirable is another question which I would have to ponder on. Some things to think about.

[SpexGuy]

This doesn't work for most actual cases though, because things like std.ArrayList are just wrappers for more complex types like std.ArrayListAligned. Determining whether a function like std.ArrayList could return a given type for some input is undecidable in the general case.

[marler8997]

Yes the general case meaning all functions is undecidable, but it's very much possible for bijective functions. In the case of std.ArrayList, it's a very simple bijective function, so this "actual case" is quite simple if you use the table I mentioned. Let's say we have an ArrayList(u32). In this case, the compiler's "inverse table" would look like this:

ArrayList
    (u32) -> ArrayListAligned(u32, null)
    (Foo) -> ArrayListAligned(Foo, null)

So when the compiler tries to pattern match ArrayList(infer T), and receives an instance of ArrayListAligned(u32, null) (aka ArrayList(u32)), all it needs to do is look in the ArrayList table for an output type that matches ArrayListAligned(u32, null), and assign the infer T to the corresponding input parameter u32.

This only breaks down when we have non-bijective functions. For example:

fn IgnoreTGiveMeU32(comptime T: type) type { return u32; }

In this case our inverse table looks like this:

IgnoreTGiveMeU32
    (u32) -> u32
    (Foo) -> u32

So now when we try to pattern match IgnoreTGiveMeU32(infer T) with an instance of u32, we will find multiple entries that match the output type u32, which means we cannot determine the input parameter and thus the problem becomes "undecidable" as you say.

The concept of bijective functions is well-understood, and that is the exact criteria that would determine whether or not a function could support infer T.

P.S. I think that determining whether a function is actually bijective is very difficult. Determining whether the subset of input of all instantiations is bijective is very easy. Relying on these imperfect tables to determine whether a function is bijective would cause cascading errors when a conflict is instantiated. I'm not sure of an easy way to solve this, so the compiler would only know when this is violated when a conflict happens to be instantiated.

[ghost]

@marler8997 You're making a good point about the reverse lookup table. To ask the question "given a particular instance of ArrayList, what type T was used to construct it?", we need to have already constructed said instance, meaning that the mapping T -> ArrayList(T) must already be in the cache, and performing the reverse operation is possible. So for custom types that play nice inference is a lot easier than I thought.

Non-bijective functions would be a problem, of course. Especially in libraries, where unambiguous inference needs to be ensured for all possible child types, and not only instances currently used in the project. There are also other failure modes that should not occur in good code, but are still possible in principle, like ArrayList(T) doing something funny on April 1.

So, if we had an annotation for well-behaved type constructors (callconv(.InvertibleTypeConstructor)?), then structural pattern matching on custom types would become feasible, and maybe not even difficult. But without it, trying to infer things would be a rather adventurous undertaking.

[ikskuh]

@zzyxyzz i don't think all of this is worth the benefit in the end, especially as ArrayList(T) aliases with ArrayListAligned(T, null) already and a lot of comptime functions just configure other types. Or you have functions like this:

pub fn BitBuffer(comptime size: usize) type {
    return [(size + 7)/8]u8;
}

where BitBuffer(1) and BitBuffer(8) are the same type

[ghost]

@MasterQ32 Just to be clear, pattern matching on custom types is not part of the proposal. I think it's an intriguing possibility to keep in mind, especially now that a workable implementation idea has been suggested. But whether it can really be made to work and at what cost, and whether we want it in the first place, has to be decided separately.

As it stands, the most ambitious variant of this proposal only allows pattern matching against built-in types, such as pointers, optionals and slices, which should not pose any problems.

BTW, BitBuffer is a nice example of a non-invertible type constructor, thanks for that. I also forgot about type aliases. They would further compound the difficulties with general type inference.

[marler8997]

@MasterQ32 yes your example BitBuffer is a non-bijective function so it's not reversible. We could create a bijective function that wraps it like this:

pub fn BitBufferBijective(comptime size: usize) type {
    std.debug.assert(size % 8 == 0); // Blocks inputs in order to create a 1 to 1 mapping
    return BitBuffer(size);
}

This example doesn't really apply to this infer T proposal because BitBuffer takes a usize instead of a type, so there's no type to infer, but the same concept applies to functions that do accept types as input parameters. This mechanism of defining wrapper functions to make type functions bijective could be used to extract the input types from any type function.

pub fn Foo(comptime T: type) type {
    // black box, that is not bijective, this Foo is a stand-in for any type funciton.
}

pub fn bar(x: Foo(infer T) void {...}
// compile error: cannot use 'infer T' with 'Foo' because it is not bijective, the input types x and y both map to z

pub fn FooBijective(comptime T: type) type {
    std.debug.assert( limitInputsToRemoveConflicts(T) );
    return Foo(T);
}

pub fn bar(x: FooBijective(infer T) void {...}
// now it will work, T will become whatever type was passed to the caller's Foo(T) instance

I thought alot about this stuff years ago when I was thinking about how D implemented pattern matching and what the challenges and potential solutions were with it. I determined it is feasible and actually not too difficult to implement and I'd be happy to help come up with a design if we want to go this route. And to re-iterate, I'm not advocating that we do implement it, just sharing exactly what a solution would look so we can make informed decisions.

[windows-h8r]

On a comment on #5893, I suggested an alternative. If we add support for default parameters, and make default parameters go first, we can do something like this:

const std = @import("std");

fn square(comptime T: type = any, n: T) T {
    return n * n;
}

fn main() void {
    const x: u32 = 5;
    std.debug.print(
         "{} = {}\n",
         square(u32, x),
         square(x)
    );
}

[SpexGuy]

The reverse lookup table doesn't work, because the outer function may never have been called.

fn foo(x: std.ArrayList(infer T)) { }
test {
  const T = std.ArrayListAligned(u32, null);
  var v: T = undefined;
  // assert(T == std.ArrayList(u32))
  foo(v);
}

std.ArrayList has never run in the above example, but the type being passed to foo is indeed a valid possible return value for it.

[marler8997]

@SpexGuy Shoot you're right. I can't think of a way to get around this without having a way to generally reverse code evaluation.

[ghost]

Shoot you're right. I can't think of a way to get around this without having a way to generally reverse code evaluation.

There are some ways. E.g. the compiler could automatically expand trivial type constructors like ArrayList, or we could make the system operate in What You Write Is What You Get fashion and simply refuse to match ArrayList(T) against ArrayListAligned(T, null). The non-injectivity issue is also both fairly rare and can be caught automatically in most cases (you have to check, recursively, that none of the return paths discards the input type). So I still think general inference could be made to work in almost all non-pathological cases. But if someone were to argue that this creates complexity way beyond what is acceptable in Zig, I wouldn't disagree :smile:.

[zigazeljko]

There is a simpler and more powerful way that does not depend on memoization or other type constructor shenanigans.

Given a parameter declaration such as haystack: ArrayList(infer T), the compiler expands the type constructor into the actual type, in this case haystack: struct { items: []infer T, capacity: usize, allocator: *Allocator }. Treating that as an equation, we get const T = @typeInfo(@TypeOf(haystack.items)).Pointer.child;.

For example, the function fn find(haystack: ArrayList(infer T), needle: T) usize {...} would behave like this:

fn find(haystack: anytype, needle: anytype) usize {
    const T = @typeInfo(@TypeOf(haystack.items)).Pointer.child;
    return findImpl(T, haystack, needle);
}

fn findImpl(comptime T: type, haystack: ArrayList(T), needle: T) usize {...}

This method also allows infer T to be used more that once per function declaration.

For example, the declaration fn max(a: infer T, b: infer T) T would mean this:

fn max(a: anytype, b: anytype) anytype {
    const T = @TypeOf(a, b);
    return maxImpl(T, a, b);
}

fn maxImpl(comptime T: type, a: T, b: T) T {...}

Furthermore, this method allows using anonymous initializers for generic parameters:

fn Vec3(comptime T: type) type {
    return struct { x: T, y: T, z: T };
}

comptime {
    const a: f32 = 2;
    _ = length(.{ .x = a, .y = 3, .z = 6 });
}

fn length(v: Vec3(infer T)) T {
    // T == f32
    // @TypeOf(v) == Vec3(f32)
    return @sqrt(v.x * v.x + v.y * v.y + v.z * v.z);
}

[ghost]

@zigazeljko, I couldn't quite parse what you are suggesting. Would the following rephrasing correctly describe your idea?

All type constructors must eventually produce a concrete type, often a struct of some kind. E.g., ArrayList(i32) expands into

struct {
    items: []i32,
    capacity: usize,
    allocator: *Allocator,
    // 300 lines of methods and other decls omitted
}

If we perform the expansion with infer T as a placeholder type, we would get

struct {
    items: []infer T,
    capacity: usize,
    allocator: *Allocator,
    // ...
}

Matching the two structs against each other, we can now correctly infer that T == i32.

If that is the idea, then the problem is that not all type constructors do simple template expansion. E.g. consider the following type:

fn StackArray(comptime T: type) type {
    const maxSize = 1024;
    const size = @sizeOf(T);
    if (size > maxSize) @compileError("Too big!");
    return struct {
        items: [maxSize/size]T,
    };
}

StackArray(i32) will expand into struct { items: [256]i32; }, but StackArray(infer T) cannot expand past the point of @sizeOf(infer T), since the size is unknown at that time. Thus, StackArray(i32) cannot be matched against StackArray(infer T) by direct comparison, although memoization would work in this case.

But please correct me if I misunderstood something.

[ghost]

@windows-h8r I must say I'm not too thrilled with the idea of optional parameters in the leading position. If we go in that direction, it may be cleaner to introduce a formal split between comptime and runtime parameters and put them in separate lists:

fn square|comptime T: type = any|(n: T) T {
    return n * n;
}
//...
square|i32|(5); // explicit
square(@as(i32,5)); // inferred

In any case, it seems to me that our proposals solve different problems, despite some overlap. Yours allows the same generic function to be used with an explicit type parameter or with an inferred one, whichever is more convenient. This sort of reminds me of #7835. A key part of my proposal, however, is the ability to talk about the types of generic functions, which seems more difficult with what you are suggesting. What would the type of fn square(comptime T: type = any, n: T) T {...} be?

[windows-h8r]

@zzyxyzz

What would the type of fn square(comptime T: type = any, n: T) T {...} be?

That's a good question. I guess we could make the parameter names part of the function type, like

fn (comptime T: type, n: T) T

This also simplifies the grammar, and complements #1717, since banning this...

const x = fn (type, anytype) anytype; // error: missing parameter names

...also bans this...

const x = fn (type, anytype) anytype { // error: missing parameter names
    // ....
};

...where a valid function would be...

const square = fn (comptime T: type = any, n: T) T {
    return n * n;
};

[windows-h8r]

fn square|comptime T: type = any|(n: T) T {
  return n * n;
}
//...
square|i32|(5); // explicit
square(@as(i32,5)); // inferred

The problem with using the |...| syntax is that it would be ambiguous. For example, how would a|b|(c) be parsed?

[marler8997]

Treating that as an equation, we get const T = @typeInfo(@TypeOf(haystack.items)).Pointer.child

@zigazeljko that's the problem right there. How do you take any type constructor function and find its "equation". This is equivalent to "reversing a function" which is very difficult as far as I can tall, and also "undecidable" in many cases (when functions are not bijective).

[ghost]

I guess we could make the parameter names part of the function type

That would certainly solve the type representation problem. We could say that the type of a function is simply the header, as written, with equality defined up to parameter names, so that fn(foo: i32) void == fn(bar: i32) void. The main thing I don't like about this is that most functions aren't generic, but would also need to carry around (unnecessarily) their parameter names in their type.

[zigazeljko]

@zzyxyzz Yes, you got the basic idea, but there is one important detail. In your second example, the compiler would do best-effort expansion (i.e. expand what it can, and mark other things as unknown), which would produce this:

struct {
    items: [unknown]infer T,
}

This expansion is enough to get a type candidate for T, in this case @typeinfo(@typeof(x.items)).Array.child, which is then plugged back into StackArray(T) to do the actual type checking and coercion.

@marler8997 Okay, "equation" may not be the correct term here, but my approach is still doable as outlined below.

1. Given a type constructor, the compiler does a best-effort expansion. This results in a type template containing infer placeholders and unknown parts.
2. For each infer T, the compiler generates a typeInfo-style path that extracts T. This is always possible, since we are dealing with one infer at a time.
3. The compiler merges all of the extracted types from step 2 using peer type resolution. This produces a type candidate for T.

This approach fails only if:

• the resulting type does not contain infer.
• the control flow diverges and the resulting types have no common parts containing infer.

In particular, if the resulting type is a struct, you can make this approach always work by including a zero-sized member like _phantom: [0]T (the same trick as PhantomData<T> in Rust).

[ghost]

So you're essentially suggesting to solve the inference problem the hard way, using a specialized backtracking engine: Given a concrete type C that should match MyType(infer T), you walk the entire branch space of MyType, while culling any return path that provably does not result in a type, does not use the input type, or is structurally incompatible with the target type C. When a compatible T is found, MyType(T) is re-computed. If the result is identical to C, we're done, otherwise we backtrack and continue the search. If the search terminates without producing viable candidates, an error is reported.

Since most type constructors don't do anything fancy and usually confine themselves to filling in templates and doing straight-forward error checking, this procedure should be acceptably fast in practice. On the other hand, it will fail if the resulting type is constructed with @Type or is selected by enumeration. In addition, excessive branching in the constructor will easily exhaust the branch quota.

I concede that this approach would probably be more effective in practice than memoization. But given the complexity of the required inference engine, and the fact that this still represents a best-effort solution, I still think that the cost-benefit ratio is unfavorable.

[marler8997]

Taking a type constructor and evaluating it with a generic unknown type would be extremely limiting. Any time the type is used in a branch such as an if or switch, the compiler would have to punt and turn that expression into an "unknown" type as you said. And any subsequent code affected by that type would also have to be "unknown". It's possible this limitation is good enough and we could make some of our types conform to it for the sake of supporting infer T on them.

[ghost]

More use-cases:

Most of the functions in std.math and std.mem` could drop their explicit type parameters:

mem.copy(i32, dest, source); // old
mem.copy(dest, source); // new

math.shl(i64, x, 5);
math.shl(x, 5);

I think this has been discussed before, but is probably held back by the usual problems of duck-typing. With this proposal, the change could be made without making the implementations more complex or losing precision in type signatures and error messages:

pub fn copy(comptime T: type, dest: []T, source: []const T) void; // old
pub fn copy(dest: []infer T, source: []const T) void; // new

[marler8997]

I thought I should also share my other idea to implement this for completeness. It requires work from the developer but it can support all possible cases. The idea is to allow developers to provide their own custom type constructor inverse functions.

Consider a mechanism that associates a type with a user-defined inverse function. We can imagine a builtin that does this such as:

// Takes a type T that resulted from a type constructor and it's inverse, namely, a function that
// will derive the type constructor inputs from the resulting type.
//
// When a compiler sees that a type constructor returns an inversible type, it will associate
// the inverse function with that type constructor which would allow that type constructor
// to be used with `infer T`.
@Inversible(comptime T: type, comptime inverse: fn(comptime T: type, comptime param: comptime_int) type

For example, imagine we start with a simple type constructor like this:

fn Pair(comptime A: type, comptime B: type) type {
    return struct { a: A, b: B };
};

Now let's redefine it to make it inversible:

fn Pair(comptime A: type, comptime B: type) type {
    return @Inversible(struct { a: A, b: B }, pair_inverse);
};

fn pair_inverse(comptime T: type, comptime param: comptime_int) type {
    return switch (param) {
        0 => @typeInfo(T).Struct.fields[0].field_type,
        1 => @typeInfo(T).Struct.fields[1].field_type,
        else => unreachable,
    };
}

So if you had a function like this:

fn foo(p: Pair(infer A, infer B)) void {
    // ...
}

If the function was called with an instance of Pair(u8, i32), then it would evaluate the inverse function twice and get:

inverse(Pair(u8, i32), 0) -> u8
inverse(Pair(u8, i32), 1) -> i32

The compiler would also verify internally that the inverse function is correct by taking the result of the inverse function and re-evaluating the type constructor to ensure it evaluates to the same type that was given. This would mean that any error in the inverse function that would have an affect on the program would automatically become a compile error. This also prevents the inverse function from working with different types. For example, say we had passed a different type:

const T = struct { x: i32, y: i64, z: u8};
foo(T { .x = 0, .y = 0, .z = 0});

// inverse(T, 0) -> i32
// inverse(T, 1) -> i64

The inverse function would appear to work in this case, but once it evaluated Pair(i32, i64) it would see that this the given type T is not equivalent to a Pair. Also note that this mechanism would still work for functions that only exist to set default parameters, like ArrayList. If foo accepted ArrayListAligned(infer T, infer align), then passing an ArrayList would still work as expected. Note however that foo would not be able to define a parameter with ArrayList(infer T) unless ArrayList itself also provided it's own inverse function.

This solution is a tradeoff between having the ability to support infer T in all possible cases at the cost of extra code to help the compiler for each type constructor. If we decided to support infer, then I'd like to understand what the compiler could do without a feature like this which I believe is a matter of understanding how easy it is to reverse evaluate zig code. Reversing code isn't something I've heard much about but I can easily come up with impossible cases and cases that seem difficult, For the cases that are possible, I believe it would be more difficult than implementing a normal evaluation engine, but maybe it's not as hard as it seems? I bet this is an area that's been explored so if anyone knows let me know.

[InKryption]

@marler8997 I actually quite like that idea; it gives the power and responsibility of type inference to the designer of the type. I actually have done something similar in a private personal project:

pub fn main() !void {
    takesMyGenericType(RealInstance0{});
    takesMyGenericType(RealInstance1{});
    // takesMyGenericType(FakeInstance0{}); // triggers compiler error
}

pub fn takesMyGenericType(my_generic_type: anytype) void {
    const T = @TypeOf(my_generic_type);
    comptime if (!verifyMyGenericType(T)) @compileError("'" ++ @typeName(T) ++ "' is not an instance of MyGenericType.");
    
    _ = my_generic_type;
}

const RealInstance0 = MyGenericType(i32, 4);
const FakeInstance0 = struct {
    const MetaInfo = struct {
        const params = .{ i32, 4 };
    };
};

const RealInstance1 = MyGenericType(u32, 6);
const FakeInstance1 = struct {
    const MetaInfo = struct {
        const params = .{ u32, 6 };
    };
};

pub fn verifyMyGenericType(comptime T: type) bool {
    if (!meta.trait.isContainer(T)) return false;
    if (!@hasDecl(T, "MetaInfo")) return false;
    if (!@hasDecl(T.MetaInfo, "params")) return false;
    if (!meta.trait.isTuple(@TypeOf(T.MetaInfo.params))) return false;
    if (@TypeOf(T.MetaInfo.params.@"0") != type) return false;
    if (@TypeOf(T.MetaInfo.params.@"1") != usize) return false;
    
    const Expected = @call(.{}, MyGenericType, T.MetaInfo.params);
    if (T != Expected) return false;
    if (T.MetaInfo != Expected.MetaInfo) return false;
    return true;
}

pub fn MyGenericType(comptime param1: type, comptime param2: usize) type {
    return struct {
        const MetaInfo = struct {
            const params = .{ param1, param2 };
        };
    };
}

Not an exact equivalence, but regardless I imagine functionality like this being built-in to the compiler would make this code quite a bit more ergonomic.

[ghost]

@marler8997, I think you're trying to solve a problem that you've solved already :sunglasses:.

Your previous suggestion with memoization already covers this case. Actually, it's even simpler than that: Because of how Zig's struct naming works, Pair(u8, i32) is already memoized as the @typeName of the struct, and matching it against Pair(infer A, infer B) given an instance is trivial.

There is also an easy 90% solution to the alias and injectivity problems: Instead of just assigning a single struct name, we also collect a list of known aliases in the course of comptime execution. For example, when we use ArrayList(i32) somewhere, this produces a type with the name ArrayListAligned(i32, null) and the known alias of ArrayList(i32), and both can be easily matched by infer. This will also lazily catch non-invertible situations, e.g. when a type has the known aliases of Foo(u8) and Foo(u16).

The only corner case that remains to be solved is the issue raised by @SpexGuy: if a function signature requires ArrayList(infer T), but the code explicitly constructs it as ArrayListAligned(i32, null) and we have never used ArrayList(i32) anywhere else in the project, then we have a problem. This situation should be rare, but is annoying nonetheless. Maybe this case can be bridged by an explicit "type inverse" like you suggest, I'm not sure. Or we could simply leave it as a known problem, with a known workaround of adding a const dummy: ArrayList(i32) = undefined somewhere.

[agathazeren]

Zig Zen says:

• Edge cases matter.

I think that the big problem with the function reversing solutions is that there are edge cases where it cannot be reversed, that are non-obvious, likely to produce errors far from the source of the problem, and are fixed with workarounds such as const dummy: ArrayList(i32) = undefined whose reason for working is non-obvious, especially for users not familiar with compiler implementation (much less this compiler's implementation). The reverseable function/alias solution, in general will solve almost all of the usecases, but only solve them 90% of the time.

With this in mind, here's a proposal for a slightly different direction on this problem, that covers 90% of the use cases consistently.

The main idea is to have the type expressions in function parameters have access to the actual type of the argument. So:

fn find(haystack: ArrayList(@TypeOf(haystack).Element), needle: @TypeOf(haystack).Element) usize {}
fn eql(lhs: anytype, rhs: @TypeOf(lhs)) void {}

The function argument typechecking alogorithm would then be, loosely.

1. Get the types of the expressions being passed as arguments, as args
2. For each parameter param of the function: 2.1. Evaluate the type expression of the corresponding parameter, with args, yeilding a type Param 2.2. Apply peer type resolution to attempt to resolve the type of the argument passed in to Param 2.3 Peer type resolution does not succeed, then error.
3. Evaluate the type expression for the return type

This is a much simpler solution in terms of compiler implementation, and in language complexity, and solves most of the problems of expressiveness.

The one main issue, however, is the verbosity. I think there is a solution though, which is to provide a way to bind a type expression to a name. There are many ways to spell this out, and I don't know which is the best one, but here a few ways I have thought of:

fn find(let T = @TypeOf(haystack).Element, haystack: ArrayList(T), needle: T) usize {}
fn find(haystack: |Haystack| ArrayList(Haystack.Element), needle: Haystack.Element) usize {}
fn find(haystack: ArrayList(@TypeOf(haystack).Element) : List, needle: List.Element) usize {}
fn find(haystack: ArrayList(@TypeOf(haystack).Element : T)), needle: T) usize {}
fn find(haystack: ArrayList(let T = @TypeOf(Haystack).Element), needle: T) usize {}

My personal favorite notation is the second, though it has the drawback of Haystack being visible in all parameters' type expressions, while only appearing to be visible in one.

[ghost]

@agathazeren, Your idea looks very much like #6615, which I believe would have permitted the haystack: ArrayList(@TypeOf(haystack).Element) syntax. From a technical point of view this is quite clever, although aesthetically I dislike both the verbosity and the self-referential nature of the notation.

You are also assuming that the type parameter is directly extractable via .Element. That's sort of cheating, since the original problem was to infer the type parameters without making assumptions about the structure of the type. Your solution requires that the generic type exposes its parameters and that the user knows how to access them. It's also difficult to come up with a standard naming convention, because the names will depend on the nature of the container. E.g., a list might have a sole type parameter .Element, but a hash map might call its two parameters .Key and .Value and in a vector they might be .T and .Dim. One could try to put all type parameters in a tuple with a standard name, but then we get type signatures like this:

container: HashMap(@TypeOf(container).TypeParams[0], @TypeOf(container).TypeParams[1])

which is a far cry from

container: HashMap(infer K, infer V)

And even then, type aliases may reshuffle or omit some of the parameters, so you still have to read the documentation...

I'm probably sounding more negative that I should be. This is a viable and consistent solution to the inference problem, I just personally think that the tradeoffs required here are worse than in the memoization-based approach.