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