1//! This module contains utilities and data structures for working with enums.
2
3const std = @import("std");
4const assert = std.debug.assert;
5const testing = std.testing;
6
7/// Increment this value when adding APIs that add single backwards branches.
8const eval_branch_quota_cushion = 10;
9
10pub fn fromInt(comptime E: type, integer: anytype) ?E {
11 const enum_info = @typeInfo(E).@"enum";
12 if (enum_info.mode == .nonexhaustive) {
13 if (std.math.cast(enum_info.tag_type, integer)) |tag| {
14 return @fromBackingInt(@intCast(tag));
15 }
16 return null;
17 }
18 // We don't directly iterate over the fields of E, as that
19 // would require an inline loop. Instead, we create an array of
20 // values that is comptime-know, but can be iterated at runtime
21 // without requiring an inline loop.
22 // This generates better machine code.
23 for (values(E)) |value| {
24 if (@backingInt(value) == integer) return value;
25 }
26 return null;
27}
28
29/// Returns a struct with a field matching each unique named enum element.
30/// If the enum is extern and has multiple names for the same value, only
31/// the first name is used. Each field is of type Data and has the provided
32/// default, which may be undefined.
33pub fn EnumFieldStruct(comptime E: type, comptime Data: type, comptime field_default: ?Data) type {
34 @setEvalBranchQuota(@typeInfo(E).@"enum".field_names.len + eval_branch_quota_cushion);
35 const default_ptr: ?*const anyopaque = if (field_default) |d| @ptrCast(&d) else null;
36 const field_names = @typeInfo(E).@"enum".field_names;
37 return @Struct(.auto, null, field_names, &@splat(Data), &@splat(.{ .default_value_ptr = default_ptr }));
38}
39
40/// Looks up the supplied field values in the given enum type.
41/// The result array is in the same order as the input.
42pub inline fn valuesFromFields(comptime E: type, comptime field_values: []const comptime_int) []const E {
43 comptime {
44 @setEvalBranchQuota(@typeInfo(E).@"enum".field_names.len + eval_branch_quota_cushion);
45 var result: [field_values.len]E = undefined;
46 for (&result, field_values) |*r, f_value| {
47 r.* = @fromBackingInt(@intCast(f_value));
48 }
49 const final = result;
50 return &final;
51 }
52}
53
54/// Returns the set of all named values in the given enum, in
55/// declaration order.
56pub inline fn values(comptime E: type) []const E {
57 return comptime valuesFromFields(E, @typeInfo(E).@"enum".field_values);
58}
59
60/// A safe alternative to @tagName() for non-exhaustive enums that doesn't
61/// panic when `e` has no tagged value.
62/// Returns the tag name for `e` or null if no tag exists.
63pub fn tagName(comptime E: type, e: E) ?[:0]const u8 {
64 const field_names = @typeInfo(E).@"enum".field_names;
65 const field_values = @typeInfo(E).@"enum".field_values;
66 @setEvalBranchQuota(field_names.len);
67 return inline for (field_names, field_values) |f_name, f_value| {
68 if (@backingInt(e) == f_value) break f_name;
69 } else null;
70}
71
72test tagName {
73 const E = enum(u8) { a, b, _ };
74 try testing.expect(tagName(E, .a) != null);
75 try testing.expectEqualStrings("a", tagName(E, .a).?);
76 try testing.expect(tagName(E, @as(E, @fromBackingInt(@intCast(42)))) == null);
77}
78
79/// Determines the length of a direct-mapped enum array, indexed by
80/// @intCast(usize, @intFromEnum(enum_value)).
81/// If the enum is non-exhaustive, the resulting length will only be enough
82/// to hold all explicit fields.
83/// If the enum contains any fields with values that cannot be represented
84/// by usize, a compile error is issued. The max_unused_slots parameter limits
85/// the total number of items which have no matching enum key (holes in the enum
86/// numbering). So for example, if an enum has values 1, 2, 5, and 6, max_unused_slots
87/// must be at least 3, to allow unused slots 0, 3, and 4.
88pub fn directEnumArrayLen(comptime E: type, comptime max_unused_slots: comptime_int) comptime_int {
89 var max_value: comptime_int = -1;
90 const max_usize: comptime_int = ~@as(usize, 0);
91 const info = @typeInfo(E).@"enum";
92 for (info.field_names, info.field_values) |f_name, f_value| {
93 if (f_value < 0) {
94 @compileError("Cannot create a direct enum array for " ++ @typeName(E) ++ ", field ." ++ f_name ++ " has a negative value.");
95 }
96 if (f_value > max_value) {
97 if (f_value > max_usize) {
98 @compileError("Cannot create a direct enum array for " ++ @typeName(E) ++ ", field ." ++ f_name ++ " is larger than the max value of usize.");
99 }
100 max_value = f_value;
101 }
102 }
103
104 const unused_slots = max_value + 1 - info.field_names.len;
105 if (unused_slots > max_unused_slots) {
106 const unused_str = std.fmt.comptimePrint("{d}", .{unused_slots});
107 const allowed_str = std.fmt.comptimePrint("{d}", .{max_unused_slots});
108 @compileError("Cannot create a direct enum array for " ++ @typeName(E) ++ ". It would have " ++ unused_str ++ " unused slots, but only " ++ allowed_str ++ " are allowed.");
109 }
110
111 return max_value + 1;
112}
113
114/// Initializes an array of Data which can be indexed by
115/// @intCast(usize, @intFromEnum(enum_value)).
116/// If the enum is non-exhaustive, the resulting array will only be large enough
117/// to hold all explicit fields.
118/// If the enum contains any fields with values that cannot be represented
119/// by usize, a compile error is issued. The max_unused_slots parameter limits
120/// the total number of items which have no matching enum key (holes in the enum
121/// numbering). So for example, if an enum has values 1, 2, 5, and 6, max_unused_slots
122/// must be at least 3, to allow unused slots 0, 3, and 4.
123/// The init_values parameter must be a struct with field names that match the enum values.
124/// If the enum has multiple fields with the same value, the name of the first one must
125/// be used.
126pub fn directEnumArray(
127 comptime E: type,
128 comptime Data: type,
129 comptime max_unused_slots: comptime_int,
130 init_values: EnumFieldStruct(E, Data, null),
131) [directEnumArrayLen(E, max_unused_slots)]Data {
132 return directEnumArrayDefault(E, Data, null, max_unused_slots, init_values);
133}
134
135test directEnumArray {
136 const E = enum(i4) { a = 4, b = 6, c = 2 };
137 var runtime_false: bool = false;
138 _ = &runtime_false;
139 const array = directEnumArray(E, bool, 4, .{
140 .a = true,
141 .b = runtime_false,
142 .c = true,
143 });
144
145 try testing.expectEqual([7]bool, @TypeOf(array));
146 try testing.expectEqual(true, array[4]);
147 try testing.expectEqual(false, array[6]);
148 try testing.expectEqual(true, array[2]);
149}
150
151/// Initializes an array of Data which can be indexed by
152/// @intCast(usize, @intFromEnum(enum_value)). The enum must be exhaustive.
153/// If the enum contains any fields with values that cannot be represented
154/// by usize, a compile error is issued. The max_unused_slots parameter limits
155/// the total number of items which have no matching enum key (holes in the enum
156/// numbering). So for example, if an enum has values 1, 2, 5, and 6, max_unused_slots
157/// must be at least 3, to allow unused slots 0, 3, and 4.
158/// The init_values parameter must be a struct with field names that match the enum values.
159/// If the enum has multiple fields with the same value, the name of the first one must
160/// be used.
161pub fn directEnumArrayDefault(
162 comptime E: type,
163 comptime Data: type,
164 comptime default: ?Data,
165 comptime max_unused_slots: comptime_int,
166 init_values: EnumFieldStruct(E, Data, default),
167) [directEnumArrayLen(E, max_unused_slots)]Data {
168 const len = comptime directEnumArrayLen(E, max_unused_slots);
169 var result: [len]Data = @splat(default orelse undefined);
170 inline for (@typeInfo(@TypeOf(init_values)).@"struct".field_names) |f_name| {
171 const enum_value = @field(E, f_name);
172 const index = @as(usize, @intCast(@backingInt(enum_value)));
173 result[index] = @field(init_values, f_name);
174 }
175 return result;
176}
177
178test directEnumArrayDefault {
179 const E = enum(i4) { a = 4, b = 6, c = 2 };
180 var runtime_false: bool = false;
181 _ = &runtime_false;
182 const array = directEnumArrayDefault(E, bool, false, 4, .{
183 .a = true,
184 .b = runtime_false,
185 });
186
187 try testing.expectEqual([7]bool, @TypeOf(array));
188 try testing.expectEqual(true, array[4]);
189 try testing.expectEqual(false, array[6]);
190 try testing.expectEqual(false, array[2]);
191}
192
193test "directEnumArrayDefault slice" {
194 const E = enum(i4) { a = 4, b = 6, c = 2 };
195 var runtime_b = "b";
196 _ = &runtime_b;
197 const array = directEnumArrayDefault(E, []const u8, "default", 4, .{
198 .a = "a",
199 .b = runtime_b,
200 });
201
202 try testing.expectEqual([7][]const u8, @TypeOf(array));
203 try testing.expectEqualSlices(u8, "a", array[4]);
204 try testing.expectEqualSlices(u8, "b", array[6]);
205 try testing.expectEqualSlices(u8, "default", array[2]);
206}
207
208test fromInt {
209 const E1 = enum {
210 A,
211 };
212 const E2 = enum {
213 A,
214 B,
215 };
216 const E3 = enum(i8) { A, _ };
217 const E4 = enum(u8) { A };
218
219 var zero: u8 = 0;
220 var one: u16 = 1;
221 _ = &zero;
222 _ = &one;
223 try testing.expect(fromInt(E1, zero).? == E1.A);
224 try testing.expect(fromInt(E2, one).? == E2.B);
225 try testing.expect(fromInt(E3, zero).? == E3.A);
226 try testing.expect(fromInt(E3, 127).? == @as(E3, @fromBackingInt(@intCast(127))));
227 try testing.expect(fromInt(E3, -128).? == @as(E3, @fromBackingInt(@intCast(-128))));
228 try testing.expectEqual(null, fromInt(E1, one));
229 try testing.expectEqual(null, fromInt(E3, 128));
230 try testing.expectEqual(null, fromInt(E3, -129));
231
232 // `fromInt` used to produce a compiler error instead of `null` if trying to convert an integer
233 // that wasn't out of range, but also wasn't a valid value.
234 try testing.expectEqual(null, fromInt(E4, 1));
235}
236
237/// A set of enum elements, backed by a bitfield. If the enum
238/// is exhaustive but not dense, a mapping will be constructed from enum values
239/// to dense indices. This type does no dynamic allocation and
240/// can be copied by value.
241pub fn EnumSet(comptime E: type) type {
242 return struct {
243 const Self = @This();
244
245 /// The indexing rules for converting between keys and indices.
246 pub const Indexer = EnumIndexer(E);
247 /// The element type for this set.
248 pub const Key = Indexer.Key;
249
250 const BitSet = std.bit_set.Static(Indexer.count);
251
252 /// The maximum number of items in this set.
253 pub const len = Indexer.count;
254
255 bits: BitSet = .empty,
256
257 /// Initializes the set using a struct of bools
258 pub fn init(init_values: EnumFieldStruct(E, bool, false)) Self {
259 @setEvalBranchQuota(2 * @typeInfo(E).@"enum".field_names.len);
260 var result: Self = .{};
261 if (@typeInfo(E).@"enum".mode == .exhaustive) {
262 inline for (0..Self.len) |i| {
263 const key = comptime Indexer.keyForIndex(i);
264 const tag = @tagName(key);
265 if (@field(init_values, tag)) {
266 result.bits.set(i);
267 }
268 }
269 } else {
270 inline for (@typeInfo(E).@"enum".field_names) |field_name| {
271 const key = @field(E, field_name);
272 if (@field(init_values, field_name)) {
273 const i = comptime Indexer.indexOf(key);
274 result.bits.set(i);
275 }
276 }
277 }
278 return result;
279 }
280
281 /// A set containing no keys.
282 pub const empty: Self = .{ .bits = .empty };
283
284 /// A set containing all possible keys.
285 pub const full: Self = .{ .bits = .full };
286
287 /// Returns a set containing multiple keys.
288 pub fn initMany(keys: []const Key) Self {
289 var set: Self = .empty;
290 for (keys) |key| set.insert(key);
291 return set;
292 }
293
294 /// Returns a set containing a single key.
295 pub fn initOne(key: Key) Self {
296 return initMany(&[_]Key{key});
297 }
298
299 /// Returns the number of keys in the set.
300 pub fn count(self: Self) usize {
301 return self.bits.count();
302 }
303
304 /// Checks if a key is in the set.
305 pub fn contains(self: Self, key: Key) bool {
306 return self.bits.isSet(Indexer.indexOf(key));
307 }
308
309 /// Puts a key in the set.
310 pub fn insert(self: *Self, key: Key) void {
311 self.bits.set(Indexer.indexOf(key));
312 }
313
314 /// Removes a key from the set.
315 pub fn remove(self: *Self, key: Key) void {
316 self.bits.unset(Indexer.indexOf(key));
317 }
318
319 /// Changes the presence of a key in the set to match the passed bool.
320 pub fn setPresent(self: *Self, key: Key, present: bool) void {
321 self.bits.setValue(Indexer.indexOf(key), present);
322 }
323
324 /// Toggles the presence of a key in the set. If the key is in
325 /// the set, removes it. Otherwise adds it.
326 pub fn toggle(self: *Self, key: Key) void {
327 self.bits.toggle(Indexer.indexOf(key));
328 }
329
330 /// Toggles the presence of all keys in the passed set.
331 pub fn toggleSet(self: *Self, other: Self) void {
332 self.bits.toggleSet(other.bits);
333 }
334
335 /// Toggles all possible keys in the set.
336 pub fn toggleAll(self: *Self) void {
337 self.bits.toggleAll();
338 }
339
340 /// Adds all keys in the passed set to this set.
341 pub fn setUnion(self: *Self, other: Self) void {
342 self.bits.setUnion(other.bits);
343 }
344
345 /// Removes all keys which are not in the passed set.
346 pub fn setIntersection(self: *Self, other: Self) void {
347 self.bits.setIntersection(other.bits);
348 }
349
350 /// Returns true iff both sets have the same keys.
351 pub fn eql(self: Self, other: Self) bool {
352 return self.bits.eql(other.bits);
353 }
354
355 /// Returns true iff all the keys in this set are
356 /// in the other set. The other set may have keys
357 /// not found in this set.
358 pub fn subsetOf(self: Self, other: Self) bool {
359 return self.bits.subsetOf(other.bits);
360 }
361
362 /// Returns true iff this set contains all the keys
363 /// in the other set. This set may have keys not
364 /// found in the other set.
365 pub fn supersetOf(self: Self, other: Self) bool {
366 return self.bits.supersetOf(other.bits);
367 }
368
369 /// Returns a set with all the keys not in this set.
370 pub fn complement(self: Self) Self {
371 return .{ .bits = self.bits.complement() };
372 }
373
374 /// Returns a set with keys that are in either this
375 /// set or the other set.
376 pub fn unionWith(self: Self, other: Self) Self {
377 return .{ .bits = self.bits.unionWith(other.bits) };
378 }
379
380 /// Returns a set with keys that are in both this
381 /// set and the other set.
382 pub fn intersectWith(self: Self, other: Self) Self {
383 return .{ .bits = self.bits.intersectWith(other.bits) };
384 }
385
386 /// Returns a set with keys that are in either this
387 /// set or the other set, but not both.
388 pub fn xorWith(self: Self, other: Self) Self {
389 return .{ .bits = self.bits.xorWith(other.bits) };
390 }
391
392 /// Returns a set with keys that are in this set
393 /// except for keys in the other set.
394 pub fn differenceWith(self: Self, other: Self) Self {
395 return .{ .bits = self.bits.differenceWith(other.bits) };
396 }
397
398 /// Returns an iterator over this set, which iterates in
399 /// index order. Modifications to the set during iteration
400 /// may or may not be observed by the iterator, but will
401 /// not invalidate it.
402 pub fn iterator(self: *const Self) Iterator {
403 return .{ .inner = self.bits.iterator(.{}) };
404 }
405
406 pub const Iterator = struct {
407 inner: BitSet.Iterator(.{}),
408
409 pub fn next(self: *Iterator) ?Key {
410 return if (self.inner.next()) |index|
411 Indexer.keyForIndex(index)
412 else
413 null;
414 }
415 };
416 };
417}
418
419/// A map keyed by an enum, backed by a bitfield and a dense array.
420/// If the enum is exhaustive but not dense, a mapping will be constructed from
421/// enum values to dense indices. This type does no dynamic
422/// allocation and can be copied by value.
423pub fn EnumMap(comptime E: type, comptime V: type) type {
424 return struct {
425 const Self = @This();
426
427 /// The index mapping for this map
428 pub const Indexer = EnumIndexer(E);
429 /// The key type used to index this map
430 pub const Key = Indexer.Key;
431 /// The value type stored in this map
432 pub const Value = V;
433 /// The number of possible keys in the map
434 pub const len = Indexer.count;
435
436 const BitSet = std.bit_set.Static(Indexer.count);
437
438 /// Bits determining whether items are in the map
439 bits: BitSet = .empty,
440 /// Values of items in the map. If the associated
441 /// bit is zero, the value is undefined.
442 values: [Indexer.count]Value = undefined,
443
444 /// Initializes the map using a sparse struct of optionals
445 pub fn init(init_values: EnumFieldStruct(E, ?Value, @as(?Value, null))) Self {
446 @setEvalBranchQuota(2 * @typeInfo(E).@"enum".field_names.len);
447 var result: Self = .{};
448 if (@typeInfo(E).@"enum".mode == .exhaustive) {
449 inline for (0..Self.len) |i| {
450 const key = comptime Indexer.keyForIndex(i);
451 const tag = @tagName(key);
452 if (@field(init_values, tag)) |*v| {
453 result.bits.set(i);
454 result.values[i] = v.*;
455 }
456 }
457 } else {
458 inline for (@typeInfo(E).@"enum".field_names) |field_name| {
459 const key = @field(E, field_name);
460 if (@field(init_values, field_name)) |*v| {
461 const i = comptime Indexer.indexOf(key);
462 result.bits.set(i);
463 result.values[i] = v.*;
464 }
465 }
466 }
467 return result;
468 }
469
470 /// Initializes a full mapping with all keys set to value.
471 /// Consider using EnumArray instead if the map will remain full.
472 pub fn initFull(value: Value) Self {
473 var result: Self = .{
474 .bits = .full,
475 .values = undefined,
476 };
477 @memset(&result.values, value);
478 return result;
479 }
480
481 /// Initializes a full mapping with supplied values.
482 /// Consider using EnumArray instead if the map will remain full.
483 pub fn initFullWith(init_values: EnumFieldStruct(E, Value, null)) Self {
484 return initFullWithDefault(null, init_values);
485 }
486
487 /// Initializes a full mapping with a provided default.
488 /// Consider using EnumArray instead if the map will remain full.
489 pub fn initFullWithDefault(comptime default: ?Value, init_values: EnumFieldStruct(E, Value, default)) Self {
490 @setEvalBranchQuota(2 * @typeInfo(E).@"enum".field_names.len);
491 var result: Self = .{
492 .bits = .full,
493 .values = undefined,
494 };
495 inline for (0..Self.len) |i| {
496 const key = comptime Indexer.keyForIndex(i);
497 const tag = @tagName(key);
498 result.values[i] = @field(init_values, tag);
499 }
500 return result;
501 }
502
503 /// The number of items in the map.
504 pub fn count(self: *const Self) usize {
505 return self.bits.count();
506 }
507
508 /// Checks if the map contains an item.
509 pub fn contains(self: *const Self, key: Key) bool {
510 return self.bits.isSet(Indexer.indexOf(key));
511 }
512
513 /// Gets the value associated with a key.
514 /// If the key is not in the map, returns null.
515 pub fn get(self: *const Self, key: Key) ?Value {
516 const index = Indexer.indexOf(key);
517 return if (self.bits.isSet(index)) self.values[index] else null;
518 }
519
520 /// Gets the value associated with a key, which must
521 /// exist in the map.
522 pub fn getAssertContains(self: *const Self, key: Key) Value {
523 const index = Indexer.indexOf(key);
524 assert(self.bits.isSet(index));
525 return self.values[index];
526 }
527
528 /// Gets the address of the value associated with a key.
529 /// If the key is not in the map, returns null.
530 pub fn getPtr(self: *Self, key: Key) ?*Value {
531 const index = Indexer.indexOf(key);
532 return if (self.bits.isSet(index)) &self.values[index] else null;
533 }
534
535 /// Gets the address of the const value associated with a key.
536 /// If the key is not in the map, returns null.
537 pub fn getPtrConst(self: *const Self, key: Key) ?*const Value {
538 const index = Indexer.indexOf(key);
539 return if (self.bits.isSet(index)) &self.values[index] else null;
540 }
541
542 /// Gets the address of the value associated with a key.
543 /// The key must be present in the map.
544 pub fn getPtrAssertContains(self: *Self, key: Key) *Value {
545 const index = Indexer.indexOf(key);
546 assert(self.bits.isSet(index));
547 return &self.values[index];
548 }
549
550 /// Gets the address of the const value associated with a key.
551 /// The key must be present in the map.
552 pub fn getPtrConstAssertContains(self: *const Self, key: Key) *const Value {
553 const index = Indexer.indexOf(key);
554 assert(self.bits.isSet(index));
555 return &self.values[index];
556 }
557
558 /// Adds the key to the map with the supplied value.
559 /// If the key is already in the map, overwrites the value.
560 pub fn put(self: *Self, key: Key, value: Value) void {
561 const index = Indexer.indexOf(key);
562 self.bits.set(index);
563 self.values[index] = value;
564 }
565
566 /// Adds the key to the map with an undefined value.
567 /// If the key is already in the map, the value becomes undefined.
568 /// A pointer to the value is returned, which should be
569 /// used to initialize the value.
570 pub fn putUninitialized(self: *Self, key: Key) *Value {
571 const index = Indexer.indexOf(key);
572 self.bits.set(index);
573 self.values[index] = undefined;
574 return &self.values[index];
575 }
576
577 /// Sets the value associated with the key in the map,
578 /// and returns the old value. If the key was not in
579 /// the map, returns null.
580 pub fn fetchPut(self: *Self, key: Key, value: Value) ?Value {
581 const index = Indexer.indexOf(key);
582 const result: ?Value = if (self.bits.isSet(index)) self.values[index] else null;
583 self.bits.set(index);
584 self.values[index] = value;
585 return result;
586 }
587
588 /// Removes a key from the map. If the key was not in the map,
589 /// does nothing.
590 pub fn remove(self: *Self, key: Key) void {
591 const index = Indexer.indexOf(key);
592 self.bits.unset(index);
593 self.values[index] = undefined;
594 }
595
596 /// Removes a key from the map, and returns the old value.
597 /// If the key was not in the map, returns null.
598 pub fn fetchRemove(self: *Self, key: Key) ?Value {
599 const index = Indexer.indexOf(key);
600 const result: ?Value = if (self.bits.isSet(index)) self.values[index] else null;
601 self.bits.unset(index);
602 self.values[index] = undefined;
603 return result;
604 }
605
606 /// Returns an iterator over the map, which visits items in index order.
607 /// Modifications to the underlying map may or may not be observed by
608 /// the iterator, but will not invalidate it.
609 pub fn iterator(self: *Self) Iterator {
610 return .{
611 .inner = self.bits.iterator(.{}),
612 .values = &self.values,
613 };
614 }
615
616 /// An entry in the map.
617 pub const Entry = struct {
618 /// The key associated with this entry.
619 /// Modifying this key will not change the map.
620 key: Key,
621
622 /// A pointer to the value in the map associated
623 /// with this key. Modifications through this
624 /// pointer will modify the underlying data.
625 value: *Value,
626 };
627
628 pub const Iterator = struct {
629 inner: BitSet.Iterator(.{}),
630 values: *[Indexer.count]Value,
631
632 pub fn next(self: *Iterator) ?Entry {
633 return if (self.inner.next()) |index|
634 Entry{
635 .key = Indexer.keyForIndex(index),
636 .value = &self.values[index],
637 }
638 else
639 null;
640 }
641 };
642 };
643}
644
645test EnumMap {
646 const Ball = enum { red, green, blue };
647
648 const some = EnumMap(Ball, u8).init(.{
649 .green = 0xff,
650 .blue = 0x80,
651 });
652 try testing.expectEqual(2, some.count());
653 try testing.expectEqual(null, some.get(.red));
654 try testing.expectEqual(0xff, some.get(.green));
655 try testing.expectEqual(0x80, some.get(.blue));
656}
657
658/// A multiset of enum elements up to a count of usize. Backed
659/// by an EnumArray. This type does no dynamic allocation and can
660/// be copied by value.
661pub fn EnumMultiset(comptime E: type) type {
662 return BoundedEnumMultiset(E, usize);
663}
664
665/// A multiset of enum elements up to CountSize. Backed by an
666/// EnumArray. This type does no dynamic allocation and can be
667/// copied by value.
668pub fn BoundedEnumMultiset(comptime E: type, comptime CountSize: type) type {
669 return struct {
670 const Self = @This();
671
672 counts: EnumArray(E, CountSize),
673
674 /// Initializes the multiset using a struct of counts.
675 pub fn init(init_counts: EnumFieldStruct(E, CountSize, 0)) Self {
676 @setEvalBranchQuota(2 * @typeInfo(E).@"enum".field_names.len);
677 var self = initWithCount(0);
678 const info = @typeInfo(E).@"enum";
679 inline for (info.field_names, info.field_values) |field_name, field_value| {
680 const c = @field(init_counts, field_name);
681 const key: E = @fromBackingInt(@intCast(field_value));
682 self.counts.set(key, c);
683 }
684 return self;
685 }
686
687 /// A multiset with a count of zero.
688 pub const empty: Self = .initWithCount(0);
689
690 /// Initializes the multiset with all keys at the
691 /// same count.
692 pub fn initWithCount(comptime c: CountSize) Self {
693 return .{
694 .counts = .initDefault(c, .{}),
695 };
696 }
697
698 /// Returns the total number of key counts in the multiset.
699 pub fn count(self: Self) usize {
700 var sum: usize = 0;
701 for (self.counts.values) |c| {
702 sum += c;
703 }
704 return sum;
705 }
706
707 /// Checks if at least one key in multiset.
708 pub fn contains(self: Self, key: E) bool {
709 return self.counts.get(key) > 0;
710 }
711
712 /// Removes all instance of a key from multiset. Same as
713 /// setCount(key, 0).
714 pub fn removeAll(self: *Self, key: E) void {
715 return self.counts.set(key, 0);
716 }
717
718 /// Increases the key count by given amount. Caller asserts
719 /// operation will not overflow.
720 pub fn addAssertSafe(self: *Self, key: E, c: CountSize) void {
721 self.counts.getPtr(key).* += c;
722 }
723
724 /// Increases the key count by given amount.
725 pub fn add(self: *Self, key: E, c: CountSize) error{Overflow}!void {
726 self.counts.set(key, try std.math.add(CountSize, self.counts.get(key), c));
727 }
728
729 /// Decreases the key count by given amount. If amount is
730 /// greater than the number of keys in multset, then key count
731 /// will be set to zero.
732 pub fn remove(self: *Self, key: E, c: CountSize) void {
733 self.counts.getPtr(key).* -= @min(self.getCount(key), c);
734 }
735
736 /// Returns the count for a key.
737 pub fn getCount(self: Self, key: E) CountSize {
738 return self.counts.get(key);
739 }
740
741 /// Set the count for a key.
742 pub fn setCount(self: *Self, key: E, c: CountSize) void {
743 self.counts.set(key, c);
744 }
745
746 /// Increases the all key counts by given multiset. Caller
747 /// asserts operation will not overflow any key.
748 pub fn addSetAssertSafe(self: *Self, other: Self) void {
749 inline for (@typeInfo(E).@"enum".field_values) |field_value| {
750 const key = @as(E, @fromBackingInt(@intCast(field_value)));
751 self.addAssertSafe(key, other.getCount(key));
752 }
753 }
754
755 /// Increases the all key counts by given multiset.
756 pub fn addSet(self: *Self, other: Self) error{Overflow}!void {
757 inline for (@typeInfo(E).@"enum".field_values) |field_value| {
758 const key = @as(E, @fromBackingInt(@intCast(field_value)));
759 try self.add(key, other.getCount(key));
760 }
761 }
762
763 /// Decreases the all key counts by given multiset. If
764 /// the given multiset has more key counts than this,
765 /// then that key will have a key count of zero.
766 pub fn removeSet(self: *Self, other: Self) void {
767 inline for (@typeInfo(E).@"enum".field_values) |field_value| {
768 const key = @as(E, @fromBackingInt(@intCast(field_value)));
769 self.remove(key, other.getCount(key));
770 }
771 }
772
773 /// Returns true iff all key counts are the same as
774 /// given multiset.
775 pub fn eql(self: Self, other: Self) bool {
776 inline for (@typeInfo(E).@"enum".field_values) |field_value| {
777 const key = @as(E, @fromBackingInt(@intCast(field_value)));
778 if (self.getCount(key) != other.getCount(key)) {
779 return false;
780 }
781 }
782 return true;
783 }
784
785 /// Returns true iff all key counts less than or
786 /// equal to the given multiset.
787 pub fn subsetOf(self: Self, other: Self) bool {
788 inline for (@typeInfo(E).@"enum".field_values) |field_value| {
789 const key = @as(E, @fromBackingInt(@intCast(field_value)));
790 if (self.getCount(key) > other.getCount(key)) {
791 return false;
792 }
793 }
794 return true;
795 }
796
797 /// Returns true iff all key counts greater than or
798 /// equal to the given multiset.
799 pub fn supersetOf(self: Self, other: Self) bool {
800 inline for (@typeInfo(E).@"enum".field_values) |field_value| {
801 const key = @as(E, @fromBackingInt(@intCast(field_value)));
802 if (self.getCount(key) < other.getCount(key)) {
803 return false;
804 }
805 }
806 return true;
807 }
808
809 /// Returns a multiset with the total key count of this
810 /// multiset and the other multiset. Caller asserts
811 /// operation will not overflow any key.
812 pub fn plusAssertSafe(self: Self, other: Self) Self {
813 var result = self;
814 result.addSetAssertSafe(other);
815 return result;
816 }
817
818 /// Returns a multiset with the total key count of this
819 /// multiset and the other multiset.
820 pub fn plus(self: Self, other: Self) error{Overflow}!Self {
821 var result = self;
822 try result.addSet(other);
823 return result;
824 }
825
826 /// Returns a multiset with the key count of this
827 /// multiset minus the corresponding key count in the
828 /// other multiset. If the other multiset contains
829 /// more key count than this set, that key will have
830 /// a count of zero.
831 pub fn minus(self: Self, other: Self) Self {
832 var result = self;
833 result.removeSet(other);
834 return result;
835 }
836
837 pub const Entry = EnumArray(E, CountSize).Entry;
838 pub const Iterator = EnumArray(E, CountSize).Iterator;
839
840 /// Returns an iterator over this multiset. Keys with zero
841 /// counts are included. Modifications to the set during
842 /// iteration may or may not be observed by the iterator,
843 /// but will not invalidate it.
844 pub fn iterator(self: *Self) Iterator {
845 return self.counts.iterator();
846 }
847 };
848}
849
850test EnumMultiset {
851 const Ball = enum { red, green, blue };
852
853 const empty = EnumMultiset(Ball).empty;
854 const r0_g1_b2 = EnumMultiset(Ball).init(.{
855 .red = 0,
856 .green = 1,
857 .blue = 2,
858 });
859 const ten_of_each = EnumMultiset(Ball).initWithCount(10);
860
861 try testing.expectEqual(empty.count(), 0);
862 try testing.expectEqual(r0_g1_b2.count(), 3);
863 try testing.expectEqual(ten_of_each.count(), 30);
864
865 try testing.expect(!empty.contains(.red));
866 try testing.expect(!empty.contains(.green));
867 try testing.expect(!empty.contains(.blue));
868
869 try testing.expect(!r0_g1_b2.contains(.red));
870 try testing.expect(r0_g1_b2.contains(.green));
871 try testing.expect(r0_g1_b2.contains(.blue));
872
873 try testing.expect(ten_of_each.contains(.red));
874 try testing.expect(ten_of_each.contains(.green));
875 try testing.expect(ten_of_each.contains(.blue));
876
877 {
878 var copy = ten_of_each;
879 copy.removeAll(.red);
880 try testing.expect(!copy.contains(.red));
881
882 // removeAll second time does nothing
883 copy.removeAll(.red);
884 try testing.expect(!copy.contains(.red));
885 }
886
887 {
888 var copy = ten_of_each;
889 copy.addAssertSafe(.red, 6);
890 try testing.expectEqual(copy.getCount(.red), 16);
891 }
892
893 {
894 var copy = ten_of_each;
895 try copy.add(.red, 6);
896 try testing.expectEqual(copy.getCount(.red), 16);
897
898 try testing.expectError(error.Overflow, copy.add(.red, std.math.maxInt(usize)));
899 }
900
901 {
902 var copy = ten_of_each;
903 copy.remove(.red, 4);
904 try testing.expectEqual(copy.getCount(.red), 6);
905
906 // subtracting more it contains does not underflow
907 copy.remove(.green, 14);
908 try testing.expectEqual(copy.getCount(.green), 0);
909 }
910
911 try testing.expectEqual(empty.getCount(.green), 0);
912 try testing.expectEqual(r0_g1_b2.getCount(.green), 1);
913 try testing.expectEqual(ten_of_each.getCount(.green), 10);
914
915 {
916 var copy = empty;
917 copy.setCount(.red, 6);
918 try testing.expectEqual(copy.getCount(.red), 6);
919 }
920
921 {
922 var copy = r0_g1_b2;
923 copy.addSetAssertSafe(ten_of_each);
924 try testing.expectEqual(copy.getCount(.red), 10);
925 try testing.expectEqual(copy.getCount(.green), 11);
926 try testing.expectEqual(copy.getCount(.blue), 12);
927 }
928
929 {
930 var copy = r0_g1_b2;
931 try copy.addSet(ten_of_each);
932 try testing.expectEqual(copy.getCount(.red), 10);
933 try testing.expectEqual(copy.getCount(.green), 11);
934 try testing.expectEqual(copy.getCount(.blue), 12);
935
936 const full = EnumMultiset(Ball).initWithCount(std.math.maxInt(usize));
937 try testing.expectError(error.Overflow, copy.addSet(full));
938 }
939
940 {
941 var copy = ten_of_each;
942 copy.removeSet(r0_g1_b2);
943 try testing.expectEqual(copy.getCount(.red), 10);
944 try testing.expectEqual(copy.getCount(.green), 9);
945 try testing.expectEqual(copy.getCount(.blue), 8);
946
947 copy.removeSet(ten_of_each);
948 try testing.expectEqual(copy.getCount(.red), 0);
949 try testing.expectEqual(copy.getCount(.green), 0);
950 try testing.expectEqual(copy.getCount(.blue), 0);
951 }
952
953 try testing.expect(empty.eql(empty));
954 try testing.expect(r0_g1_b2.eql(r0_g1_b2));
955 try testing.expect(ten_of_each.eql(ten_of_each));
956 try testing.expect(!empty.eql(r0_g1_b2));
957 try testing.expect(!r0_g1_b2.eql(ten_of_each));
958 try testing.expect(!ten_of_each.eql(empty));
959
960 try testing.expect(empty.subsetOf(empty));
961 try testing.expect(r0_g1_b2.subsetOf(r0_g1_b2));
962 try testing.expect(empty.subsetOf(r0_g1_b2));
963 try testing.expect(r0_g1_b2.subsetOf(ten_of_each));
964 try testing.expect(!ten_of_each.subsetOf(r0_g1_b2));
965 try testing.expect(!r0_g1_b2.subsetOf(empty));
966
967 try testing.expect(empty.supersetOf(empty));
968 try testing.expect(r0_g1_b2.supersetOf(r0_g1_b2));
969 try testing.expect(r0_g1_b2.supersetOf(empty));
970 try testing.expect(ten_of_each.supersetOf(r0_g1_b2));
971 try testing.expect(!r0_g1_b2.supersetOf(ten_of_each));
972 try testing.expect(!empty.supersetOf(r0_g1_b2));
973
974 {
975 // with multisets it could be the case where two
976 // multisets are neither subset nor superset of each
977 // other.
978
979 const r10 = EnumMultiset(Ball).init(.{
980 .red = 10,
981 });
982 const b10 = EnumMultiset(Ball).init(.{
983 .blue = 10,
984 });
985
986 try testing.expect(!r10.subsetOf(b10));
987 try testing.expect(!b10.subsetOf(r10));
988 try testing.expect(!r10.supersetOf(b10));
989 try testing.expect(!b10.supersetOf(r10));
990 }
991
992 {
993 const result = r0_g1_b2.plusAssertSafe(ten_of_each);
994 try testing.expectEqual(result.getCount(.red), 10);
995 try testing.expectEqual(result.getCount(.green), 11);
996 try testing.expectEqual(result.getCount(.blue), 12);
997 }
998
999 {
1000 const result = try r0_g1_b2.plus(ten_of_each);
1001 try testing.expectEqual(result.getCount(.red), 10);
1002 try testing.expectEqual(result.getCount(.green), 11);
1003 try testing.expectEqual(result.getCount(.blue), 12);
1004
1005 const full = EnumMultiset(Ball).initWithCount(std.math.maxInt(usize));
1006 try testing.expectError(error.Overflow, result.plus(full));
1007 }
1008
1009 {
1010 const result = ten_of_each.minus(r0_g1_b2);
1011 try testing.expectEqual(result.getCount(.red), 10);
1012 try testing.expectEqual(result.getCount(.green), 9);
1013 try testing.expectEqual(result.getCount(.blue), 8);
1014 }
1015
1016 {
1017 const result = ten_of_each.minus(r0_g1_b2).minus(ten_of_each);
1018 try testing.expectEqual(result.getCount(.red), 0);
1019 try testing.expectEqual(result.getCount(.green), 0);
1020 try testing.expectEqual(result.getCount(.blue), 0);
1021 }
1022
1023 {
1024 var copy = empty;
1025 var it = copy.iterator();
1026 var entry = it.next().?;
1027 try testing.expectEqual(entry.key, .red);
1028 try testing.expectEqual(entry.value.*, 0);
1029 entry = it.next().?;
1030 try testing.expectEqual(entry.key, .green);
1031 try testing.expectEqual(entry.value.*, 0);
1032 entry = it.next().?;
1033 try testing.expectEqual(entry.key, .blue);
1034 try testing.expectEqual(entry.value.*, 0);
1035 try testing.expectEqual(it.next(), null);
1036 }
1037
1038 {
1039 var copy = r0_g1_b2;
1040 var it = copy.iterator();
1041 var entry = it.next().?;
1042 try testing.expectEqual(entry.key, .red);
1043 try testing.expectEqual(entry.value.*, 0);
1044 entry = it.next().?;
1045 try testing.expectEqual(entry.key, .green);
1046 try testing.expectEqual(entry.value.*, 1);
1047 entry = it.next().?;
1048 try testing.expectEqual(entry.key, .blue);
1049 try testing.expectEqual(entry.value.*, 2);
1050 try testing.expectEqual(it.next(), null);
1051 }
1052}
1053
1054/// An array keyed by an enum, backed by a dense array.
1055/// If the enum is not dense, a mapping will be constructed from
1056/// enum values to dense indices. This type does no dynamic
1057/// allocation and can be copied by value.
1058pub fn EnumArray(comptime E: type, comptime V: type) type {
1059 return struct {
1060 const Self = @This();
1061
1062 /// The index mapping for this map
1063 pub const Indexer = EnumIndexer(E);
1064 /// The key type used to index this map
1065 pub const Key = Indexer.Key;
1066 /// The value type stored in this map
1067 pub const Value = V;
1068 /// The number of possible keys in the map
1069 pub const len = Indexer.count;
1070
1071 values: [Indexer.count]Value,
1072
1073 pub fn init(init_values: EnumFieldStruct(E, Value, null)) Self {
1074 return initDefault(null, init_values);
1075 }
1076
1077 /// Initializes values in the enum array, with the specified default.
1078 pub fn initDefault(comptime default: ?Value, init_values: EnumFieldStruct(E, Value, default)) Self {
1079 @setEvalBranchQuota(2 * @typeInfo(E).@"enum".field_names.len);
1080 var result: Self = .{ .values = undefined };
1081 inline for (0..Self.len) |i| {
1082 const key = comptime Indexer.keyForIndex(i);
1083 const tag = @tagName(key);
1084 result.values[i] = @field(init_values, tag);
1085 }
1086 return result;
1087 }
1088
1089 pub fn initUndefined() Self {
1090 return Self{ .values = undefined };
1091 }
1092
1093 pub fn initFill(v: Value) Self {
1094 var self: Self = undefined;
1095 @memset(&self.values, v);
1096 return self;
1097 }
1098
1099 /// Returns the value in the array associated with a key.
1100 pub fn get(self: Self, key: Key) Value {
1101 return self.values[Indexer.indexOf(key)];
1102 }
1103
1104 /// Returns a pointer to the slot in the array associated with a key.
1105 pub fn getPtr(self: *Self, key: Key) *Value {
1106 return &self.values[Indexer.indexOf(key)];
1107 }
1108
1109 /// Returns a const pointer to the slot in the array associated with a key.
1110 pub fn getPtrConst(self: *const Self, key: Key) *const Value {
1111 return &self.values[Indexer.indexOf(key)];
1112 }
1113
1114 /// Sets the value in the slot associated with a key.
1115 pub fn set(self: *Self, key: Key, value: Value) void {
1116 self.values[Indexer.indexOf(key)] = value;
1117 }
1118
1119 /// Iterates over the items in the array, in index order.
1120 pub fn iterator(self: *Self) Iterator {
1121 return .{
1122 .values = &self.values,
1123 };
1124 }
1125
1126 /// An entry in the array.
1127 pub const Entry = struct {
1128 /// The key associated with this entry.
1129 /// Modifying this key will not change the array.
1130 key: Key,
1131
1132 /// A pointer to the value in the array associated
1133 /// with this key. Modifications through this
1134 /// pointer will modify the underlying data.
1135 value: *Value,
1136 };
1137
1138 pub const Iterator = struct {
1139 index: usize = 0,
1140 values: *[Indexer.count]Value,
1141
1142 pub fn next(self: *Iterator) ?Entry {
1143 const index = self.index;
1144 if (index < Indexer.count) {
1145 self.index += 1;
1146 return Entry{
1147 .key = Indexer.keyForIndex(index),
1148 .value = &self.values[index],
1149 };
1150 }
1151 return null;
1152 }
1153 };
1154 };
1155}
1156
1157test "pure EnumSet fns" {
1158 const Suit = enum { spades, hearts, clubs, diamonds };
1159
1160 const empty = EnumSet(Suit).empty;
1161 const full = EnumSet(Suit).full;
1162 const black = EnumSet(Suit).initMany(&[_]Suit{ .spades, .clubs });
1163 const red = EnumSet(Suit).initMany(&[_]Suit{ .hearts, .diamonds });
1164
1165 try testing.expect(empty.eql(empty));
1166 try testing.expect(full.eql(full));
1167 try testing.expect(!empty.eql(full));
1168 try testing.expect(!full.eql(empty));
1169 try testing.expect(!empty.eql(black));
1170 try testing.expect(!full.eql(red));
1171 try testing.expect(!red.eql(empty));
1172 try testing.expect(!black.eql(full));
1173
1174 try testing.expect(empty.subsetOf(empty));
1175 try testing.expect(empty.subsetOf(full));
1176 try testing.expect(full.subsetOf(full));
1177 try testing.expect(!black.subsetOf(red));
1178 try testing.expect(!red.subsetOf(black));
1179
1180 try testing.expect(full.supersetOf(full));
1181 try testing.expect(full.supersetOf(empty));
1182 try testing.expect(empty.supersetOf(empty));
1183 try testing.expect(!black.supersetOf(red));
1184 try testing.expect(!red.supersetOf(black));
1185
1186 try testing.expect(empty.complement().eql(full));
1187 try testing.expect(full.complement().eql(empty));
1188 try testing.expect(black.complement().eql(red));
1189 try testing.expect(red.complement().eql(black));
1190
1191 try testing.expect(empty.unionWith(empty).eql(empty));
1192 try testing.expect(empty.unionWith(full).eql(full));
1193 try testing.expect(full.unionWith(full).eql(full));
1194 try testing.expect(full.unionWith(empty).eql(full));
1195 try testing.expect(black.unionWith(red).eql(full));
1196 try testing.expect(red.unionWith(black).eql(full));
1197
1198 try testing.expect(empty.intersectWith(empty).eql(empty));
1199 try testing.expect(empty.intersectWith(full).eql(empty));
1200 try testing.expect(full.intersectWith(full).eql(full));
1201 try testing.expect(full.intersectWith(empty).eql(empty));
1202 try testing.expect(black.intersectWith(red).eql(empty));
1203 try testing.expect(red.intersectWith(black).eql(empty));
1204
1205 try testing.expect(empty.xorWith(empty).eql(empty));
1206 try testing.expect(empty.xorWith(full).eql(full));
1207 try testing.expect(full.xorWith(full).eql(empty));
1208 try testing.expect(full.xorWith(empty).eql(full));
1209 try testing.expect(black.xorWith(red).eql(full));
1210 try testing.expect(red.xorWith(black).eql(full));
1211
1212 try testing.expect(empty.differenceWith(empty).eql(empty));
1213 try testing.expect(empty.differenceWith(full).eql(empty));
1214 try testing.expect(full.differenceWith(full).eql(empty));
1215 try testing.expect(full.differenceWith(empty).eql(full));
1216 try testing.expect(full.differenceWith(red).eql(black));
1217 try testing.expect(full.differenceWith(black).eql(red));
1218}
1219
1220test "EnumSet empty" {
1221 const E = enum {};
1222 const empty = EnumSet(E).empty;
1223 const full = EnumSet(E).full;
1224
1225 try std.testing.expect(empty.eql(full));
1226 try std.testing.expect(empty.complement().eql(full));
1227 try std.testing.expect(empty.complement().eql(full.complement()));
1228 try std.testing.expect(empty.eql(full.complement()));
1229}
1230
1231test "EnumSet const iterator" {
1232 const Direction = enum { up, down, left, right };
1233 const diag_move = init: {
1234 var move = EnumSet(Direction).empty;
1235 move.insert(.right);
1236 move.insert(.up);
1237 break :init move;
1238 };
1239
1240 var result = EnumSet(Direction).empty;
1241 var it = diag_move.iterator();
1242 while (it.next()) |dir| {
1243 result.insert(dir);
1244 }
1245
1246 try testing.expect(result.eql(diag_move));
1247}
1248
1249test "EnumSet non-exhaustive" {
1250 const BitIndices = enum(u4) {
1251 a = 0,
1252 b = 1,
1253 c = 4,
1254 _,
1255 };
1256 const BitField = EnumSet(BitIndices);
1257
1258 var flags = BitField.init(.{ .a = true, .b = true });
1259 flags.insert(.c);
1260 flags.remove(.a);
1261 try testing.expect(!flags.contains(.a));
1262 try testing.expect(flags.contains(.b));
1263 try testing.expect(flags.contains(.c));
1264}
1265
1266pub fn EnumIndexer(comptime E: type) type {
1267 // n log n for `std.mem.sortUnstable` call below.
1268 const fields_len = @typeInfo(E).@"enum".field_names.len;
1269 @setEvalBranchQuota(3 * fields_len * std.math.log2(@max(fields_len, 1)) + eval_branch_quota_cushion);
1270
1271 if (@typeInfo(E).@"enum".mode == .nonexhaustive) {
1272 const BackingInt = @typeInfo(E).@"enum".tag_type;
1273 if (@bitSizeOf(BackingInt) > @bitSizeOf(usize))
1274 @compileError("Cannot create an enum indexer for a given non-exhaustive enum, tag_type is larger than usize.");
1275
1276 return struct {
1277 pub const Key: type = E;
1278
1279 const backing_int_sign = @typeInfo(BackingInt).int.signedness;
1280 const min_value = std.math.minInt(BackingInt);
1281 const max_value = std.math.maxInt(BackingInt);
1282
1283 const RangeType = @Int(.unsigned, @bitSizeOf(BackingInt));
1284 pub const count: comptime_int = std.math.maxInt(RangeType) + 1;
1285
1286 pub fn indexOf(e: E) usize {
1287 if (backing_int_sign == .unsigned)
1288 return @backingInt(e);
1289
1290 return if (@backingInt(e) < 0)
1291 @intCast(@backingInt(e) - min_value)
1292 else
1293 @as(RangeType, -min_value) + @as(RangeType, @intCast(@backingInt(e)));
1294 }
1295 pub fn keyForIndex(i: usize) E {
1296 if (backing_int_sign == .unsigned)
1297 return @fromBackingInt(@intCast(i));
1298
1299 return @fromBackingInt(@intCast(@as(@Int(.signed, @bitSizeOf(RangeType) + 1), @intCast(i)) + min_value));
1300 }
1301 };
1302 }
1303
1304 if (fields_len == 0) {
1305 return struct {
1306 pub const Key = E;
1307 pub const count: comptime_int = 0;
1308 pub fn indexOf(e: E) usize {
1309 _ = e;
1310 unreachable;
1311 }
1312 pub fn keyForIndex(i: usize) E {
1313 _ = i;
1314 unreachable;
1315 }
1316 };
1317 }
1318
1319 var field_values = @typeInfo(E).@"enum".field_values[0..fields_len].*;
1320
1321 std.mem.sortUnstable(comptime_int, &field_values, {}, struct {
1322 fn lessThan(_: void, a: comptime_int, b: comptime_int) bool {
1323 return a < b;
1324 }
1325 }.lessThan);
1326
1327 const min = field_values[0];
1328 const max = field_values[fields_len - 1];
1329 if (max - min == field_values.len - 1) {
1330 return struct {
1331 pub const Key = E;
1332 pub const count: comptime_int = fields_len;
1333 pub fn indexOf(e: E) usize {
1334 return @as(usize, @intCast(@backingInt(e) - min));
1335 }
1336 pub fn keyForIndex(i: usize) E {
1337 // TODO fix addition semantics. This calculation
1338 // gives up some safety to avoid artificially limiting
1339 // the range of signed enum values to max_isize.
1340 const enum_value = if (min < 0) @as(isize, @bitCast(i)) +% min else i + min;
1341 return @as(E, @fromBackingInt(@intCast(@as(@typeInfo(E).@"enum".tag_type, @intCast(enum_value)))));
1342 }
1343 };
1344 }
1345
1346 const keys = valuesFromFields(E, &field_values);
1347
1348 return struct {
1349 pub const Key = E;
1350 pub const count: comptime_int = fields_len;
1351 pub fn indexOf(e: E) usize {
1352 for (keys, 0..) |k, i| {
1353 if (k == e) return i;
1354 }
1355 unreachable;
1356 }
1357 pub fn keyForIndex(i: usize) E {
1358 return keys[i];
1359 }
1360 };
1361}
1362
1363test "EnumIndexer non-exhaustive" {
1364 const backing_ints = [_]type{
1365 i1,
1366 i2,
1367 i3,
1368 i4,
1369 i8,
1370 i16,
1371 @Int(.signed, @bitSizeOf(isize) - 1),
1372 isize,
1373 u1,
1374 u2,
1375 u3,
1376 u4,
1377 u16,
1378 @Int(.unsigned, @bitSizeOf(usize) - 1),
1379 usize,
1380 };
1381 inline for (backing_ints) |BackingInt| {
1382 const E = enum(BackingInt) {
1383 number_zero_tag = 0,
1384 _,
1385 };
1386 const Indexer = EnumIndexer(E);
1387
1388 const min_tag: E = @fromBackingInt(@intCast(std.math.minInt(BackingInt)));
1389 const max_tag: E = @fromBackingInt(@intCast(std.math.maxInt(BackingInt)));
1390
1391 const RangedType = @Int(.unsigned, @bitSizeOf(BackingInt));
1392 const max_index: comptime_int = std.math.maxInt(RangedType);
1393 const number_zero_tag_index: usize = switch (@typeInfo(BackingInt).int.signedness) {
1394 .unsigned => 0,
1395 .signed => @divCeil(max_index, 2),
1396 };
1397
1398 try testing.expectEqual(E, Indexer.Key);
1399 try testing.expectEqual(max_index + 1, Indexer.count);
1400
1401 try testing.expectEqual(@as(usize, 0), Indexer.indexOf(min_tag));
1402 try testing.expectEqual(number_zero_tag_index, Indexer.indexOf(E.number_zero_tag));
1403 try testing.expectEqual(@as(usize, max_index), Indexer.indexOf(max_tag));
1404
1405 try testing.expectEqual(min_tag, Indexer.keyForIndex(0));
1406 try testing.expectEqual(E.number_zero_tag, Indexer.keyForIndex(number_zero_tag_index));
1407 try testing.expectEqual(max_tag, Indexer.keyForIndex(max_index));
1408 }
1409}
1410
1411test "EnumIndexer dense zeroed" {
1412 const E = enum(u2) { b = 1, a = 0, c = 2 };
1413 const Indexer = EnumIndexer(E);
1414 try testing.expectEqual(E, Indexer.Key);
1415 try testing.expectEqual(3, Indexer.count);
1416
1417 try testing.expectEqual(@as(usize, 0), Indexer.indexOf(.a));
1418 try testing.expectEqual(@as(usize, 1), Indexer.indexOf(.b));
1419 try testing.expectEqual(@as(usize, 2), Indexer.indexOf(.c));
1420
1421 try testing.expectEqual(E.a, Indexer.keyForIndex(0));
1422 try testing.expectEqual(E.b, Indexer.keyForIndex(1));
1423 try testing.expectEqual(E.c, Indexer.keyForIndex(2));
1424}
1425
1426test "EnumIndexer dense positive" {
1427 const E = enum(u4) { c = 6, a = 4, b = 5 };
1428 const Indexer = EnumIndexer(E);
1429 try testing.expectEqual(E, Indexer.Key);
1430 try testing.expectEqual(3, Indexer.count);
1431
1432 try testing.expectEqual(@as(usize, 0), Indexer.indexOf(.a));
1433 try testing.expectEqual(@as(usize, 1), Indexer.indexOf(.b));
1434 try testing.expectEqual(@as(usize, 2), Indexer.indexOf(.c));
1435
1436 try testing.expectEqual(E.a, Indexer.keyForIndex(0));
1437 try testing.expectEqual(E.b, Indexer.keyForIndex(1));
1438 try testing.expectEqual(E.c, Indexer.keyForIndex(2));
1439}
1440
1441test "EnumIndexer dense negative" {
1442 const E = enum(i4) { a = -6, c = -4, b = -5 };
1443 const Indexer = EnumIndexer(E);
1444 try testing.expectEqual(E, Indexer.Key);
1445 try testing.expectEqual(3, Indexer.count);
1446
1447 try testing.expectEqual(@as(usize, 0), Indexer.indexOf(.a));
1448 try testing.expectEqual(@as(usize, 1), Indexer.indexOf(.b));
1449 try testing.expectEqual(@as(usize, 2), Indexer.indexOf(.c));
1450
1451 try testing.expectEqual(E.a, Indexer.keyForIndex(0));
1452 try testing.expectEqual(E.b, Indexer.keyForIndex(1));
1453 try testing.expectEqual(E.c, Indexer.keyForIndex(2));
1454}
1455
1456test "EnumIndexer sparse" {
1457 const E = enum(i4) { a = -2, c = 6, b = 4 };
1458 const Indexer = EnumIndexer(E);
1459 try testing.expectEqual(E, Indexer.Key);
1460 try testing.expectEqual(3, Indexer.count);
1461
1462 try testing.expectEqual(@as(usize, 0), Indexer.indexOf(.a));
1463 try testing.expectEqual(@as(usize, 1), Indexer.indexOf(.b));
1464 try testing.expectEqual(@as(usize, 2), Indexer.indexOf(.c));
1465
1466 try testing.expectEqual(E.a, Indexer.keyForIndex(0));
1467 try testing.expectEqual(E.b, Indexer.keyForIndex(1));
1468 try testing.expectEqual(E.c, Indexer.keyForIndex(2));
1469}
1470
1471test "EnumIndexer empty" {
1472 const E = enum {};
1473 const Indexer = EnumIndexer(E);
1474 try testing.expectEqual(E, Indexer.Key);
1475 try testing.expectEqual(0, Indexer.count);
1476}
1477
1478test "EnumIndexer large dense unsorted" {
1479 @setEvalBranchQuota(500_000); // many `comptimePrint`s
1480 // Make an enum with 500 fields with values in *descending* order.
1481 const E = @Enum(u32, .exhaustive, names: {
1482 var names: [500][]const u8 = undefined;
1483 for (&names, 0..) |*name, i| name.* = std.fmt.comptimePrint("f{d}", .{i});
1484 break :names &names;
1485 }, vals: {
1486 var vals: [500]u32 = undefined;
1487 for (&vals, 0..) |*val, i| val.* = 500 - i;
1488 break :vals &vals;
1489 });
1490 const Indexer = EnumIndexer(E);
1491 try testing.expectEqual(E.f0, Indexer.keyForIndex(499));
1492 try testing.expectEqual(E.f499, Indexer.keyForIndex(0));
1493 try testing.expectEqual(499, Indexer.indexOf(.f0));
1494 try testing.expectEqual(0, Indexer.indexOf(.f499));
1495}
1496
1497test values {
1498 const E = enum {
1499 X,
1500 Y,
1501 Z,
1502 const A = 1;
1503 };
1504 try testing.expectEqualSlices(E, &.{ .X, .Y, .Z }, values(E));
1505}