Zig NEWS

Discussion on: Using comptime to invert bijective functions on enums

Collapse
 
slavka profile image
slavka

I don't quite understand, is it necessary to use this switch + inline else construct? If so, why?

Collapse
 
rbino profile image
Riccardo Binetti • Edited

This bit me in my first implementation too so I'll expand how I got from there to the final code.

My first implementation was this:

pub fn beatenBy(self: Shape) Shape {
    const winner = blk: {
        inline for (@typeInfo(Shape).Enum.fields) |field| {
            const other_shape = @intToEnum(Shape, field.value);
            if (other_shape.beats() == self) {
                break :blk other_shape;
            }
        }
        unreachable;
    };
    return winner;
}
Enter fullscreen mode Exit fullscreen mode

This seems to work, but the problem is that it does its work at runtime. What happens is that inline for unrolls the for loop scanning through all Shapes at compile time, but the comparison happens as runtime, so the produced code (after comptime) should look something like this:

pub fn beatenBy(self: Shape) Shape {
    const winner = blk: {
      if (Shape.rock.beats() == self) break :blk .rock;
      if (Shape.paper.beats() == self) break :blk .paper;            
      if (Shape.scissors.beats() == self) break :blk .scissors;
      unreachable;
    };
    return winner;
}
Enter fullscreen mode Exit fullscreen mode

The problem with this is that it does not give the comptime guarantees I detailed above. Indeed if you try this with the Shapes and Colors example, it will compile without complaining even if the function is not bijective and only fail at runtime (hitting the unreachable above).

If we want the compile time guarantees, we need to add comptime before :blk, thus making that block evaluated at compile time. But if you try to do just that to the code above, the compiler will fail with:

src/main.zig:14:47: error: unable to resolve comptime value
            if (other_shape.beats() == self) {
            ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
Enter fullscreen mode Exit fullscreen mode

This is because we're trying to use self, which is a runtime value, in a comptime block. We want instead to handle all the possible values that self could have in the same place, and that's exactly what inline else is for.

If we expand the inline else part of comptime, the code in the original post looks something like this:

pub fn beatenBy(self: Shape) Shape {
    switch (self) {
        .rock => {
            const winner = comptime blk: {
                inline for (@typeInfo(Shape).Enum.fields) |field| {
                    const other_shape = @intToEnum(Shape, field.value);
                    if (other_shape.beats() == .rock) {
                        break :blk other_shape;
                    }
                }
                unreachable;
            };
            return winner;
        },
        .paper => {
            const winner = comptime blk: {
                inline for (@typeInfo(Shape).Enum.fields) |field| {
                    const other_shape = @intToEnum(Shape, field.value);
                    if (other_shape.beats() == .paper) {
                        break :blk other_shape;
                    }
                }
                unreachable;
            };
            return winner;
        },
        .scissors => {
            const winner = comptime blk: {
                inline for (@typeInfo(Shape).Enum.fields) |field| {
                    const other_shape = @intToEnum(Shape, field.value);
                    if (other_shape.beats() == .scissors) {
                        break :blk other_shape;
                    }
                }
                unreachable;
            };
            return winner;
        },
    }
}
Enter fullscreen mode Exit fullscreen mode

But since now all 3 values are comptime-known, comptime :blk can actually get executed at compile time and the final resulting code is:

pub fn beatenBy(self: Shape) Shape {
    switch (self) {
        .rock => {
            const winner = .paper;
            return winner;
        },
        .paper => {
            const winner = .scissors;
            return winner;
        },
        .scissors => {
            const winner = .rock;
            return winner;
        },
    }
}
Enter fullscreen mode Exit fullscreen mode

I hope this makes it clearer (I might consider integrating this in the original post).

Collapse
 
slavka profile image
slavka

Oh, I see, so the value between the | signs in the inline else construct is associated with the "current iteration over all possible enum values", which actually makes sense. Thanks!

I suppose the article could benefit from some version of this explanation, since it highlights a less obvious point about this feature of the language, especially if the reader hasn't had an opportunity to use it.

By the way, is the last snippet in your comment written by hand? If not, it would be cool to see how it was generated, otherwise it might be a good idea to include the generated machine code or something like that to verify that there's no actual work done at runtime.

Thread Thread
 
rbino profile image
Riccardo Binetti

It's written by hand to give the intuition of how that works, but if you look at the output of the code on GodBolt and search into the assembly, you can see that the beats functions is never called, and the beatenBy functions is translated to a number of comparisons, jumps and movs of constant (the winners calculated at compile time).