Dealing with recursion in a comptime function

Challenge
1

This is actually a problem I’ve just encountered in my code. I think it’s interesting enough to warrant a post here.

The isSupported function down below checks whether a data type is supported by my program. At the top part of the switch statement you can see the list of supported primitives. Composite types are handled near the bottom. They’re supported provided that they don’t contain (or point to) something unsupported.

fn isSupported(comptime T: type) bool {
    return switch (@typeInfo(T)) {
        .Type,
        .Bool,
        .Int,
        .ComptimeInt,
        .Float,
        .ComptimeFloat,
        .Void,
        .Null,
        .Undefined,
        .ErrorSet,
        .Enum,
        .Opaque,
        .Vector,
        .EnumLiteral,
        => true,
        .ErrorUnion => |eu| isSupported(eu.payload),
        inline .Array, .Optional, .Pointer => |ar| isSupported(ar.child),
        .Struct => |st| inline for (st.fields) |field| {
            if (!field.is_comptime and !isSupported(field.type)) {
                break false;
            }
        } else true,
        .Union => |un| inline for (un.fields) |field| {
            if (!isSupported(field.type)) {
                break false;
            }
        } else true,
        else => false,
    };
}

This code breaks when it encounters a struct that refers to itself indirectly through a pointer. I ran into the issue with the following example:

pub const File = struct {
    name: []const u8,
    data: []const u8,
};
pub const Directory = struct {
    name: []const u8,
    entries: []const DirectoryEntry,
};
pub const DirectoryEntry = union(enum) {
    file: File,
    dir: Directory,
};

isSupported would go into a infinite loop and die with an “evaluation exceeded 1000 backwards branches” error.

2 Likes
5

My try is the following, which seems to work at face value.

const EvalNode = struct {
    T: type,
    next: ?EvalNode,

    fn evaluating(comptime node: EvalNode, comptime T: type) bool {
        if (node.T == T) return true;
        if (node.next) |next| return next.evaluating(T);
        return false;
    }
};

fn isSupported(comptime T: type) bool {
    return isSupportedRec(T, null);
}

fn isSupportedRec(comptime T: type, comptime last_node: ?EvalNode) bool {
    const node: EvalNode = .{ .T = T, .next = last_node };
    return switch (@typeInfo(T)) {
        .Type,
        .Bool,
        .Int,
        .ComptimeInt,
        .Float,
        .ComptimeFloat,
        .Void,
        .Null,
        .Undefined,
        .ErrorSet,
        .Enum,
        .Opaque,
        .Vector,
        .EnumLiteral,
        => true,
        .ErrorUnion => |eu| if (node.evaluating(eu.payload)) true else isSupportedRec(eu.payload, node),
        inline .Array, .Optional, .Pointer => |ar| if (node.evaluating(ar.child)) true else isSupportedRec(ar.child, node),
        .Struct => |st| inline for (st.fields) |field| {
            if (!node.evaluating(field.type) and !field.is_comptime and !isSupportedRec(field.type, node)) {
                break false;
            }
        } else true,
        .Union => |un| inline for (un.fields) |field| {
            if (!node.evaluating(field.type) and !isSupportedRec(field.type, node)) {
                break false;
            }
        } else true,
        else => false,
    };
}

We could also do a linked list with ?*const Node, but this seemed clearner at comptime and I don’t know enough internals to evaluate if it saves anything.

I’ll be honest though, I can’t figure out a type that isn’t supported. So I had to edit the code to test failing cases.

1 Like
6

Here’s the solution I came up with:

fn isSupported(comptime T: type) bool {
    const recursively = struct {
        fn check(comptime CT: type, comptime checking_before: anytype) bool {
            inline for (checking_before) |BT| {
                if (CT == BT) {
                    return true;
                }
            }
            const checking_now = checking_before ++ .{CT};
            return switch (@typeInfo(CT)) {
                .Type,
                .Bool,
                .Int,
                .ComptimeInt,
                .Float,
                .ComptimeFloat,
                .Void,
                .Null,
                .Undefined,
                .ErrorSet,
                .Enum,
                .Opaque,
                .Vector,
                .EnumLiteral,
                => true,
                .ErrorUnion => |eu| check(eu.payload, checking_now),
                inline .Array, .Optional, .Pointer => |ar| check(ar.child, checking_now),
                .Struct => |st| inline for (st.fields) |field| {
                    if (!field.is_comptime and !check(field.type, checking_now)) {
                        break false;
                    }
                } else true,
                .Union => |un| inline for (un.fields) |field| {
                    if (!check(field.type, checking_now)) {
                        break false;
                    }
                } else true,
                else => false,
            };
        }
    };
    return recursively.check(T, .{});
}

This problem turned out not be much of a challenge. I had thought the fact that the function is comptime would make the issue more difficult to deal with. It actually made it easier, since we can ducktype at comptime :duck: :muscle:

6 Likes