stage2: comptime function with the same args is memoized

 * Introduce `memoized_calls` to `Module` which stores all the comptime
   function calls that are cached. It is keyed on the `*Fn` and the
   comptime arguments, but it does not yet properly detect comptime function
   pointers and avoid memoizing in this case. So it will have false
   positives for when a comptime function call mutates data through a
   pointer parameter.
 * Sema: Add a new helper function: `resolveConstMaybeUndefVal`
 * Value: add `enumToInt` method and use it in `zirEnumToInt`. It is
   also used by the hashing function.
 * Value: fix representation of optionals to match error unions.
   Previously it would not handle nested optionals correctly. Now it
   matches the memory layout of error unions and supports nested
   optionals properly. This required changes in all the backends for
   generating optional constants.
 * TypedValue gains `eql` and `hash` methods.
 * Value: Implement hashing for floats, optionals, and enums.
   Additionally, the zig type tag is added to the hash, where it was not
   previously, so that values of differing types will get different
   hashes.

1 files changed, 98 insertions, 9 deletions

diff --git a/src/value.zig b/src/value.zig
index 7b3056bfcf..5ac9f142c4 100644
--- a/src/value.zig
+++ b/src/value.zig
@@ -133,12 +133,21 @@ pub const Value = extern union {
         /// When the type is error union:
         /// * If the tag is `.@"error"`, the error union is an error.
         /// * If the tag is `.eu_payload`, the error union is a payload.
-        /// * A nested error such as `((anyerror!T1)!T2)` in which the the outer error union
+        /// * A nested error such as `anyerror!(anyerror!T)` in which the the outer error union
         ///   is non-error, but the inner error union is an error, is represented as
         ///   a tag of `.eu_payload`, with a sub-tag of `.@"error"`.
         eu_payload,
         /// A pointer to the payload of an error union, based on a pointer to an error union.
         eu_payload_ptr,
+        /// When the type is optional:
+        /// * If the tag is `.null_value`, the optional is null.
+        /// * If the tag is `.opt_payload`, the optional is a payload.
+        /// * A nested optional such as `??T` in which the the outer optional
+        ///   is non-null, but the inner optional is null, is represented as
+        ///   a tag of `.opt_payload`, with a sub-tag of `.null_value`.
+        opt_payload,
+        /// A pointer to the payload of an optional, based on a pointer to an optional.
+        opt_payload_ptr,
         /// An instance of a struct.
         @"struct",
         /// An instance of a union.
@@ -238,6 +247,8 @@ pub const Value = extern union {
                 .repeated,
                 .eu_payload,
                 .eu_payload_ptr,
+                .opt_payload,
+                .opt_payload_ptr,
                 => Payload.SubValue,
 
                 .bytes,
@@ -459,7 +470,12 @@ pub const Value = extern union {
                 return Value{ .ptr_otherwise = &new_payload.base };
             },
             .bytes => return self.copyPayloadShallow(allocator, Payload.Bytes),
-            .repeated, .eu_payload, .eu_payload_ptr => {
+            .repeated,
+            .eu_payload,
+            .eu_payload_ptr,
+            .opt_payload,
+            .opt_payload_ptr,
+            => {
                 const payload = self.cast(Payload.SubValue).?;
                 const new_payload = try allocator.create(Payload.SubValue);
                 new_payload.* = .{
@@ -656,12 +672,20 @@ pub const Value = extern union {
                 try out_stream.writeAll("(eu_payload) ");
                 val = val.castTag(.eu_payload).?.data;
             },
+            .opt_payload => {
+                try out_stream.writeAll("(opt_payload) ");
+                val = val.castTag(.opt_payload).?.data;
+            },
             .inferred_alloc => return out_stream.writeAll("(inferred allocation value)"),
             .inferred_alloc_comptime => return out_stream.writeAll("(inferred comptime allocation value)"),
             .eu_payload_ptr => {
                 try out_stream.writeAll("(eu_payload_ptr)");
                 val = val.castTag(.eu_payload_ptr).?.data;
             },
+            .opt_payload_ptr => {
+                try out_stream.writeAll("(opt_payload_ptr)");
+                val = val.castTag(.opt_payload_ptr).?.data;
+            },
         };
     }
 
@@ -776,6 +800,38 @@ pub const Value = extern union {
         }
     }
 
+    pub fn enumToInt(val: Value, ty: Type, buffer: *Payload.U64) Value {
+        if (val.castTag(.enum_field_index)) |enum_field_payload| {
+            const field_index = enum_field_payload.data;
+            switch (ty.tag()) {
+                .enum_full, .enum_nonexhaustive => {
+                    const enum_full = ty.cast(Type.Payload.EnumFull).?.data;
+                    if (enum_full.values.count() != 0) {
+                        return enum_full.values.keys()[field_index];
+                    } else {
+                        // Field index and integer values are the same.
+                        buffer.* = .{
+                            .base = .{ .tag = .int_u64 },
+                            .data = field_index,
+                        };
+                        return Value.initPayload(&buffer.base);
+                    }
+                },
+                .enum_simple => {
+                    // Field index and integer values are the same.
+                    buffer.* = .{
+                        .base = .{ .tag = .int_u64 },
+                        .data = field_index,
+                    };
+                    return Value.initPayload(&buffer.base);
+                },
+                else => unreachable,
+            }
+        }
+        // Assume it is already an integer and return it directly.
+        return val;
+    }
+
     /// Asserts the value is an integer.
     pub fn toBigInt(self: Value, space: *BigIntSpace) BigIntConst {
         switch (self.tag()) {
@@ -1132,7 +1188,10 @@ pub const Value = extern union {
     }
 
     pub fn hash(val: Value, ty: Type, hasher: *std.hash.Wyhash) void {
-        switch (ty.zigTypeTag()) {
+        const zig_ty_tag = ty.zigTypeTag();
+        std.hash.autoHash(hasher, zig_ty_tag);
+
+        switch (zig_ty_tag) {
             .BoundFn => unreachable, // TODO remove this from the language
 
             .Void,
@@ -1157,7 +1216,10 @@ pub const Value = extern union {
                 }
             },
             .Float, .ComptimeFloat => {
-                @panic("TODO implement hashing float values");
+                // TODO double check the lang spec. should we to bitwise hashing here,
+                // or a hash that normalizes the float value?
+                const float = val.toFloat(f128);
+                std.hash.autoHash(hasher, @bitCast(u128, float));
             },
             .Pointer => {
                 @panic("TODO implement hashing pointer values");
@@ -1169,7 +1231,15 @@ pub const Value = extern union {
                 @panic("TODO implement hashing struct values");
             },
             .Optional => {
-                @panic("TODO implement hashing optional values");
+                if (val.castTag(.opt_payload)) |payload| {
+                    std.hash.autoHash(hasher, true); // non-null
+                    const sub_val = payload.data;
+                    var buffer: Type.Payload.ElemType = undefined;
+                    const sub_ty = ty.optionalChild(&buffer);
+                    sub_val.hash(sub_ty, hasher);
+                } else {
+                    std.hash.autoHash(hasher, false); // non-null
+                }
             },
             .ErrorUnion => {
                 @panic("TODO implement hashing error union values");
@@ -1178,7 +1248,16 @@ pub const Value = extern union {
                 @panic("TODO implement hashing error set values");
             },
             .Enum => {
-                @panic("TODO implement hashing enum values");
+                var enum_space: Payload.U64 = undefined;
+                const int_val = val.enumToInt(ty, &enum_space);
+
+                var space: BigIntSpace = undefined;
+                const big = int_val.toBigInt(&space);
+
+                std.hash.autoHash(hasher, big.positive);
+                for (big.limbs) |limb| {
+                    std.hash.autoHash(hasher, limb);
+                }
             },
             .Union => {
                 @panic("TODO implement hashing union values");
@@ -1257,6 +1336,11 @@ pub const Value = extern union {
                 const err_union_val = (try err_union_ptr.pointerDeref(allocator)) orelse return null;
                 break :blk err_union_val.castTag(.eu_payload).?.data;
             },
+            .opt_payload_ptr => blk: {
+                const opt_ptr = self.castTag(.opt_payload_ptr).?.data;
+                const opt_val = (try opt_ptr.pointerDeref(allocator)) orelse return null;
+                break :blk opt_val.castTag(.opt_payload).?.data;
+            },
 
             .zero,
             .one,
@@ -1354,13 +1438,14 @@ pub const Value = extern union {
     /// Valid for all types. Asserts the value is not undefined and not unreachable.
     pub fn isNull(self: Value) bool {
         return switch (self.tag()) {
+            .null_value => true,
+            .opt_payload => false,
+
             .undef => unreachable,
             .unreachable_value => unreachable,
             .inferred_alloc => unreachable,
             .inferred_alloc_comptime => unreachable,
-            .null_value => true,
-
-            else => false,
+            else => unreachable,
         };
     }
 
@@ -1390,6 +1475,10 @@ pub const Value = extern union {
         return switch (val.tag()) {
             .eu_payload => true,
             else => false,
+
+            .undef => unreachable,
+            .inferred_alloc => unreachable,
+            .inferred_alloc_comptime => unreachable,
         };
     }