Generating unique id at comptime

[chung-leong]

The following is some code I’ve been playing around with. The key function is
getUniqueId, which returns a unique id for any given type:

const std = @import("std");

const Error = error{failure_is_success};

fn fail(comptime _: type) !void {
    return Error.failure_is_success;
}

fn getUniqueNumber(comptime T: type) usize {
    fail(T) catch {
        if (@errorReturnTrace()) |trace| {
            return trace.instruction_addresses[0];
        }
    };
    unreachable;
}

const base_opaque = opaque {};

fn getUniqueId(comptime T: type) usize {
    const base = getUniqueNumber(base_opaque);
    return getUniqueNumber(T) - base;
}

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

pub fn main() void {
    const types = .{
        u32,
        i32,
        []u8,
        [*:0]u8,
        Point(f32),
        Point(f64),
        @TypeOf(.{ .evil_turtles = "on the loose", .stage = 1 }),
        @TypeOf(.{ .evil_turtles = "on the loose", .stage = 2 }),
        @TypeOf(Point),
        opaque {},
        opaque {},
    };
    inline for (1..3) |round| {
        std.debug.print("Round {d}:\n", .{round});
        inline for (types) |T| {
            const id = getUniqueId(T);
            std.debug.print("{s} => {d}\n", .{ @typeName(T), id });
        }
        std.debug.print("\n", .{});
    }
}

Round 1:
u32 => 16
i32 => 352
[]u8 => 688
[*:0]u8 => 1024
opaque.Point(f32) => 1360
opaque.Point(f64) => 1696
struct{comptime evil_turtles: *const [12:0]u8 = "on the loose", comptime stage: comptime_int = 1} => 2032
struct{comptime evil_turtles: *const [12:0]u8 = "on the loose", comptime stage: comptime_int = 2} => 2368
fn (comptime type) type => 2704
opaque.main__opaque_3394 => 3040
opaque.main__opaque_3395 => 3376

Round 2:
u32 => 16
i32 => 352
[]u8 => 688
[*:0]u8 => 1024
opaque.Point(f32) => 1360
opaque.Point(f64) => 1696
struct{comptime evil_turtles: *const [12:0]u8 = "on the loose", comptime stage: comptime_int = 1} => 2032
struct{comptime evil_turtles: *const [12:0]u8 = "on the loose", comptime stage: comptime_int = 2} => 2368
fn (comptime type) type => 2704
opaque.main__opaque_3394 => 3040
opaque.main__opaque_3395 => 3376

Totally hackish but seems to work. Got any idea on how to accomplish the same thing in a cleaner manner?

[chung-leong]

Since I started this thread, I guess I’m obliged in some way to detail the eventual solution I came up with. So the basic challenge is assigning a unique integer id to a type (for identifying the type outside of Zig). What I did is create a comptime struct that collects information about all the types that my program will encounter:

const TypeDataCollector = struct {
    types: ComptimeList(TypeData),
    functions: ComptimeList(type),
    next_slot: usize = 0,

TypeData is a struct that holds info about a type, including the integer id in question (which I call “slot”):

const TypeData = struct {
    Type: type,
    slot: ?usize = null,
    attrs: TypeAttributes = .{},
};

Plus some important info about the type:

const TypeAttributes = packed struct {
    is_supported: bool = false,
    is_comptime_only: bool = false,
    has_pointer: bool = false,
    known: bool = false,
};

ComptimeList is basically a variable-length array in comptime:

fn ComptimeList(comptime T: type) type {
    return struct {
        entries: []T,
        len: comptime_int,

        fn init(comptime capacity: comptime_int) @This() {
            comptime var entries: [capacity]T = undefined;
            return .{ .entries = &entries, .len = 0 };
        }

        fn concat(comptime self: @This(), comptime value: T) @This() {
            if (self.len < self.entries.len) {
                self.entries[self.len] = value;
                return .{ .entries = self.entries, .len = self.len + 1 };
            } else {
                // need new array
                const capacity = if (self.entries.len > 0) 2 * self.entries.len else 1;
                comptime var entries: [capacity]T = undefined;
                inline for (self.entries, 0..) |entry, index| {
                    entries[index] = entry;
                }
                entries[self.len] = value;
                return .{ .entries = &entries, .len = self.len + 1 };
            }
        }

        fn slice(comptime self: @This()) []T {
            return self.entries[0..self.len];
        }
    };
}

It’s a comptime structure that grows in size as needed. Thanks to it I don’t need to worry about how many types I’m dealing with. It’s used in the following manner:

    fn add(comptime self: *@This(), comptime T: type) void {
        if (self.indexOf(T)) |index| {
            return;
        }
        self.types = self.types.concat(.{ .Type = T });
        switch (@typeInfo(T)) {
           // add child types here
        }
    }

Since TypeDataCollector contains fields with pointers to comptime var, it’s a comptime-only structure. It can only be employed in code that runs only in comptime. You cannot pass it to a function that accepts both comptime and runtime arguments.

In order to actually make use of the info collected by TypeDataCollector, I need a separate struct type:

fn TypeDatabase(comptime len: comptime_int) type {
    return struct {
        entries: [len]TypeData,

        fn get(comptime self: @This(), comptime T: type) TypeData {
            for (self.entries) |entry| {
                if (entry.Type == T) {
                    return entry;
                }
            } else {
                @compileError("No type data for " ++ @typeName(T));
            }
        }
    };
}

TypeDatabase does not have pointers so it’s usable in contexts requiring comptime-known values. Here’s the function in TypeDataCollector that creates an instance of it:

    fn createDatabase(comptime self: *const @This()) TypeDatabase(self.types.len) {
        comptime var tdb: TypeDatabase(self.types.len) = undefined;
        inline for (self.types.slice(), 0..) |td, index| {
            tdb.entries[index] = td;
        }
        return tdb;
    }

Basically, we’re making the data we’ve collected thus far constant from this point on (in comptime). We can therefore pass this struct to functions expecting comptime known variables.