lib/python/src/object/value.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! Every Python value the package handles is one tagged union: `None`, booleans and integers are
2 //! held in the value itself, a string is a slice of bytes held elsewhere, and lists, tuples,
3 //! dictionaries, ranges and the other objects are pointers to objects held elsewhere.
4 //!
5 //! The virtual machine copies values between its stack, its variables and its containers at every
6 //! step, so a value has to be small and cheap to copy. Python's rules for truth, equality and
7 //! hashing have to hold across all of the types.
8 //!
9 //! Python treats `True` and `False` as the integers 1 and 0 in arithmetic, equality and hashing, so
10 //! `True == 1` holds and a dictionary finds the key `1` under `True`. A dictionary has to keep
11 //! insertion order and find keys by hash, and only values that cannot change may be keys. Two lists
12 //! can hold the same items and still be different objects, so equality and identity are separate
13 //! questions.
14 //!
15 //! The values follow the rules of the [Python 3.14 language
16 //! reference](https://docs.python.org/3.14/reference/), and the file's tests check them: Python's
17 //! truth rules, its integer reading of booleans, its equality for strings, lists, tuples and
18 //! ranges, and equal hashes for equal keys.
19 //!
20 //! Python's integers grow without bound, and this package stores an integer in 128 signed bits, so
21 //! arithmetic that leaves that range fails with `IntegerOverflow`. A string is a borrowed slice of
22 //! UTF-8 bytes that points into the source text or into the heap. Length, iteration and slicing of
23 //! a string count codepoints. A function value is the position of its body in the top-level chunk,
24 //! and a builtin value is a tag that names one of nine builtin functions. A dictionary keeps its
25 //! entries in an array in insertion order and maps each key to its entry's position in a separate
26 //! hash table, so lookup goes by hash and iteration goes by insertion order. Removing a dictionary
27 //! entry shifts every later entry down one position and updates each later entry's position in the
28 //! hash table, so removal takes time linear in the number of later entries. `hash` uses Wyhash with
29 //! a fixed seed, so a value hashes the same in every run. `hash` reads a boolean as its integer, so
30 //! equal keys share a hash. Each iterator is a small record that points to what it walks and holds
31 //! a position, with a flag for walking from the end.
32 const std = @import("std");
33
34 /// One Python value, as a tagged union of thirteen kinds. The virtual machine reads and writes
35 /// values in every operation, and `Result.value` is one. `None`, booleans and integers live in the
36 /// value itself, a string is a slice of bytes held elsewhere, and every other kind points to an
37 /// object held elsewhere. The objects that the virtual machine makes live on its heap. Copying a
38 /// value copies the pointer, so both copies refer to the same object.
39 pub const Value = union(enum) {
40 /// Python's `None`, with no payload. `None` is false by Python's truth rules and equal only to
41 /// `None`.
42 none,
43 /// Python's `True` or `False`. A boolean counts as the integer 1 or 0 in arithmetic, equality,
44 /// ordering and hashing, so `True == 1` holds and a dictionary finds the key `1` under `True`.
45 /// A boolean is never the same object as an integer under `is`.
46 boolean: bool,
47 /// A Python integer, stored in 128 signed bits. Arithmetic that leaves that range fails with
48 /// `IntegerOverflow`.
49 integer: i128,
50 /// A Python string, as a slice of UTF-8 bytes that the value borrows. A string literal and its
51 /// slices with step 1 point into the source text, and a string the run built points into the
52 /// heap. Two strings are equal when their bytes are equal. Two strings are the same object
53 /// under `is` when they start at the same address and have the same length.
54 string: []const u8,
55 /// A Python function, as the position of its body in the function table of the top-level chunk.
56 /// The position names nothing once that chunk is freed.
57 function: usize,
58 /// One of the nine builtin functions, named by a `Builtin` tag.
59 builtin: Builtin,
60 /// A list or dictionary method bound to the object it was read from, as a pointer to a
61 /// `NativeMethod` on the heap.
62 method: *NativeMethod,
63 /// A pointer to a Python list. When the virtual machine made the list, the machine's heap owns
64 /// it.
65 list: *List,
66 /// A pointer to a Python tuple. When the virtual machine made the tuple, the machine's heap
67 /// owns it.
68 tuple: *Tuple,
69 /// A pointer to a Python dictionary. When the virtual machine made the dictionary, the
70 /// machine's heap owns it.
71 dict: *Dict,
72 /// A pointer to a view of a dictionary's keys, values or items.
73 view: *DictView,
74 /// A pointer to a Python range.
75 range: *Range,
76 /// A pointer to an iterator, whose position advances as it yields items.
77 iterator: *Iterator,
78
79 /// Returns whether the value is true by Python's truth rules, for `if`, `while`, `and`, `or`
80 /// and `not`. `None`, `False`, zero, and empty strings, lists, tuples, dictionaries, dictionary
81 /// views and ranges are false. A dictionary view is false when its dictionary is empty.
82 /// Functions, builtins, bound methods and iterators are always true.
83 pub fn truthy(self: Value) bool {
84 return switch (self) {
85 .none => false,
86 .boolean => |value| value,
87 .integer => |value| value != 0,
88 .string => |value| value.len != 0,
89 .function => true,
90 .builtin => true,
91 .method => true,
92 .list => |value| value.items.len != 0,
93 .tuple => |value| value.items.len != 0,
94 .dict => |value| value.entries.items.len != 0,
95 .view => |value| value.dict.entries.items.len != 0,
96 .range => |value| value.length != 0,
97 .iterator => true,
98 };
99 }
100
101 /// Returns the integer a value stands for: an integer's own value, 1 for `True`, 0 for `False`,
102 /// and `null` for every other kind. Arithmetic, indexing, `range`, `enumerate` and repetition
103 /// read their integer inputs through it.
104 pub fn integerLike(self: Value) ?i128 {
105 return switch (self) {
106 .integer => |value| value,
107 .boolean => |value| if (value) 1 else 0,
108 .none => null,
109 .string => null,
110 .function => null,
111 .builtin => null,
112 .method => null,
113 .list => null,
114 .tuple => null,
115 .dict => null,
116 .view => null,
117 .range => null,
118 .iterator => null,
119 };
120 }
121
122 /// Returns whether the value may be a dictionary key, so the virtual machine checks it before
123 /// every dictionary lookup and insertion. `None`, booleans, integers, strings, functions,
124 /// builtins, bound methods and ranges may be keys. A tuple may be a key when every item may.
125 /// Lists, dictionaries, dictionary views and iterators may never be keys. The check walks a
126 /// tuple item by item, so its cost grows with the tuple.
127 pub fn hashable(self: Value) bool {
128 return switch (self) {
129 .none, .boolean, .integer, .string, .function, .builtin, .method, .range => true,
130 .tuple => |value| sequenceHashable(value.items),
131 .list, .dict, .view, .iterator => false,
132 };
133 }
134
135 /// Returns whether two values are equal by Python's rules, for `==`, `!=`, membership tests and
136 /// dictionary lookups. Integers and booleans compare by their integer value. Strings compare
137 /// their bytes, and lists and tuples compare item by item. Two dictionaries are equal when they
138 /// hold equal values under the same keys, in any order. Two ranges are equal when they yield
139 /// the same elements. Keys views compare their dictionaries' keys, items views compare their
140 /// dictionaries, and a values view equals only itself. Two bound methods are equal when they
141 /// have the same method and the same receiver. Functions and builtins compare their positions
142 /// and tags, and iterators are equal only to themselves. Values of unrelated kinds are unequal,
143 /// and the comparison returns no error. Comparing a list with itself returns true before
144 /// comparing its items. Comparing a tuple with itself returns true before comparing its items.
145 /// A list containing itself therefore equals itself, including when it holds a tuple containing
146 /// that same list. Two distinct lists or dictionaries that each contain themselves recurse
147 /// until the native stack overflows when comparison reaches those self-references because
148 /// comparison has no depth bound.
149 pub fn eql(self: Value, other: Value) bool {
150 if (self.integerLike()) |left| {
151 if (other.integerLike()) |right| return left == right;
152 }
153 return switch (self) {
154 .none => other == .none,
155 .boolean => false,
156 .integer => false,
157 .string => |left| switch (other) {
158 .string => |right| std.mem.eql(u8, left, right),
159 else => false,
160 },
161 .function => |left| switch (other) {
162 .function => |right| left == right,
163 else => false,
164 },
165 .builtin => |left| switch (other) {
166 .builtin => |right| left == right,
167 else => false,
168 },
169 .method => |left| switch (other) {
170 .method => |right| nativeMethodsEqual(left, right),
171 else => false,
172 },
173 .list => |left| switch (other) {
174 .list => |right| listsEqual(left, right),
175 else => false,
176 },
177 .tuple => |left| switch (other) {
178 .tuple => |right| left == right or sequencesEqual(left.items, right.items),
179 else => false,
180 },
181 .dict => |left| switch (other) {
182 .dict => |right| dictsEqual(left, right),
183 else => false,
184 },
185 .view => |left| switch (other) {
186 .view => |right| dictViewsEqual(left, right),
187 else => false,
188 },
189 .range => |left| switch (other) {
190 .range => |right| rangesEqual(left, right),
191 else => false,
192 },
193 .iterator => |left| switch (other) {
194 .iterator => |right| left == right,
195 else => false,
196 },
197 };
198 }
199
200 /// Returns a 64-bit Wyhash of the value, with a fixed seed, so a value hashes the same in every
201 /// run. The dictionary's hash table hashes keys with it. Equal values hash equally: an integer
202 /// and the boolean with its value share a hash, and so do equal ranges and equal tuples. A
203 /// bound method hashes its method and its receiver's address. The function asserts that the
204 /// value is hashable, so the caller checks `hashable` first.
205 pub fn hash(self: Value) u64 {
206 std.debug.assert(self.hashable());
207 var hasher = std.hash.Wyhash.init(0x5059_5448_4f4e_5641);
208 hashInto(&hasher, self);
209 return hasher.final();
210 }
211 };
212
213 /// The builtin functions that the package provides, one tag each, named after the function: `dict`,
214 /// `enumerate`, `iter`, `len`, `list`, `next`, `range`, `reversed` and `tuple`. The virtual machine
215 /// pushes one when a name matches no local or global variable. Calling a builtin runs it inside the
216 /// virtual machine and pushes its result.
217 pub const Builtin = enum {
218 dict,
219 enumerate,
220 iter,
221 len,
222 list,
223 next,
224 range,
225 reversed,
226 tuple,
227 };
228
229 /// A list or dictionary method bound to the object it was read from, as a tagged union with one tag
230 /// per method. Reading a method of a list or dictionary makes one, and calling it runs the method.
231 /// Each tag's payload points to that object. Each tag is named after the object's type and the
232 /// method: `dict_clear`, `dict_copy`, `dict_get`, `dict_items`, `dict_keys`, `dict_pop`,
233 /// `dict_popitem`, `dict_setdefault`, `dict_update`, `dict_values`, `list_append`, `list_clear`,
234 /// `list_copy` and `list_pop`. Two bound methods are equal when their tags and objects match. Each
235 /// read makes a new bound method, so two reads give equal values that are different objects. A
236 /// bound method is hashable, so it can be a dictionary key.
237 pub const NativeMethod = union(enum) {
238 dict_clear: *Dict,
239 dict_copy: *Dict,
240 dict_get: *Dict,
241 dict_items: *Dict,
242 dict_keys: *Dict,
243 dict_pop: *Dict,
244 dict_popitem: *Dict,
245 dict_setdefault: *Dict,
246 dict_update: *Dict,
247 dict_values: *Dict,
248 list_append: *List,
249 list_clear: *List,
250 list_copy: *List,
251 list_pop: *List,
252 };
253
254 /// A Python list, as a Zig growable array of values. The virtual machine's lists are these, and the
255 /// package's property test and benchmark drive one directly. The array grows geometrically, so
256 /// filling it takes few allocations. After `clearRetainingCapacity`, refilling the array to its old
257 /// length allocates nothing and keeps the same storage. The virtual machine's `clear` method frees
258 /// the storage. When `pop` or `del` leaves fewer than half of the slots in use, the virtual machine
259 /// shrinks the storage to fit the items.
260 pub const List = std.ArrayListUnmanaged(Value);
261
262 /// A Python tuple, as a fixed slice of values. Tuple displays, `tuple()` and the pairs that
263 /// dictionaries and `enumerate` yield are these. The virtual machine never changes a tuple after
264 /// making it, so a tuple of hashable items can be a dictionary key.
265 pub const Tuple = struct {
266 /// The tuple's values, in order. When the virtual machine made the tuple, the machine's heap
267 /// owns this array.
268 items: []Value,
269 };
270
271 /// A Python dictionary that keeps insertion order: an array of key and value entries, in the order
272 /// the keys first arrived, and a hash table from each key to its entry's position. Dictionary
273 /// displays, `dict()` and `copy()` make these, and the package's property test and benchmark drive
274 /// one directly. An empty dictionary is `.{}`. Finding a key and replacing its value take expected
275 /// constant time and allocate nothing. Removing an entry shifts every later entry down one position
276 /// and updates each later entry's position in the hash table, so removal takes time linear in the
277 /// number of later entries. The hash table grows when it is more than 80 percent full. Every key
278 /// has to be hashable, and `put` asserts it.
279 pub const Dict = struct {
280 /// The key and value pairs in insertion order. Iteration, `popLast` and equality read this
281 /// array.
282 entries: std.ArrayListUnmanaged(DictEntry) = .empty,
283 /// A hash table from each key to its entry's position in `entries`. The table hashes keys with
284 /// `Value.hash` and compares them with `Value.eql`. The table's type is private to this file,
285 /// so callers reach it through the methods below.
286 index: DictIndex = .empty,
287
288 /// Frees the entries and the hash table with the given allocator and leaves the dictionary
289 /// undefined. The heap frees each dictionary it owns with it. The call frees nothing that the
290 /// keys and values point to.
291 pub fn deinit(self: *Dict, allocator: std.mem.Allocator) void {
292 self.index.deinit(allocator);
293 self.entries.deinit(allocator);
294 self.* = undefined;
295 }
296
297 /// Removes every entry and keeps the memory of both the entries and the hash table for reuse.
298 /// The virtual machine's `dict.clear` method empties a dictionary with it. The call allocates
299 /// nothing, so it cannot fail.
300 pub fn clearRetainingCapacity(self: *Dict) void {
301 self.entries.clearRetainingCapacity();
302 self.index.clearRetainingCapacity();
303 }
304
305 /// Reserves room for at least `capacity` entries in both the entry array and the hash table.
306 /// `createDict`, dictionary displays and the benchmark reserve room with it before inserting
307 /// many keys. The call returns `error.OutOfMemory` when an allocation fails. The call also
308 /// returns `error.OutOfMemory` when `capacity` exceeds the largest 32-bit unsigned integer,
309 /// because the hash table counts its entries in 32 bits.
310 pub fn ensureTotalCapacity(self: *Dict, allocator: std.mem.Allocator, capacity: usize) std.mem.Allocator.Error!void {
311 if (capacity > std.math.maxInt(u32)) return error.OutOfMemory;
312 try self.entries.ensureTotalCapacity(allocator, capacity);
313 try self.index.ensureTotalCapacity(allocator, @intCast(capacity));
314 }
315
316 /// Returns the position of the key's entry in `entries`, or null when the key is absent. Every
317 /// dictionary lookup, membership test and deletion in the virtual machine starts with it. The
318 /// key has to be hashable, because `Value.hash` asserts it.
319 pub fn indexOf(self: *const Dict, key: Value) ?usize {
320 return self.index.get(key);
321 }
322
323 /// When an equal key is present, replaces that entry's value, and the entry keeps its position
324 /// and its first key. Any other key goes with its value into a new entry at the end. Every
325 /// dictionary insertion in the virtual machine goes through it. Replacing a value allocates
326 /// nothing. The call asserts that the key is hashable. On `error.OutOfMemory`, both the entry
327 /// array and the hash table stay as they were.
328 pub fn put(self: *Dict, allocator: std.mem.Allocator, key: Value, entry_value: Value) std.mem.Allocator.Error!void {
329 std.debug.assert(key.hashable());
330 if (self.index.get(key)) |entry_index| {
331 self.entries.items[entry_index].value = entry_value;
332 return;
333 }
334 const entry_index = self.entries.items.len;
335 try self.entries.append(allocator, .{ .key = key, .value = entry_value });
336 errdefer self.entries.items.len -= 1;
337 try self.index.put(allocator, key, entry_index);
338 }
339
340 /// Removes the entry at the given position and returns its value. `del d[k]` and `d.pop(k)`
341 /// remove an entry with it. The call shifts every later entry down one place and updates each
342 /// later entry's position in the hash table. The call takes time linear in the number of
343 /// entries after the position. The position has to be in range. The call allocates nothing, so
344 /// it cannot fail.
345 pub fn removeAt(self: *Dict, entry_index: usize) Value {
346 const removed = self.entries.orderedRemove(entry_index);
347 std.debug.assert(self.index.remove(removed.key));
348 for (self.entries.items[entry_index..], entry_index..) |entry, index| {
349 self.index.getPtr(entry.key).?.* = index;
350 }
351 return removed.value;
352 }
353
354 /// Removes the most recently inserted entry and returns it, or returns null when the dictionary
355 /// is empty. `d.popitem()` removes the newest entry with it. The call leaves every other entry
356 /// at its position.
357 pub fn popLast(self: *Dict) ?DictEntry {
358 const entry = self.entries.pop() orelse return null;
359 std.debug.assert(self.index.remove(entry.key));
360 return entry;
361 }
362 };
363
364 /// One key and its value in a dictionary. A dictionary's entry array holds these, and `createDict`
365 /// takes a slice of them.
366 pub const DictEntry = struct {
367 /// The entry's key, which is hashable.
368 key: Value,
369 /// The value stored under the key.
370 value: Value,
371 };
372
373 /// The part of a dictionary a view shows, one tag each, named after the Python method that returns
374 /// the view: `keys`, `values` and `items`. A dictionary view carries one. An items view yields each
375 /// entry as a two-item tuple of key and value.
376 pub const DictViewKind = enum {
377 keys,
378 values,
379 items,
380 };
381
382 /// A live view of one dictionary. `keys()`, `values()` and `items()` return one. The view borrows
383 /// the dictionary and shows every later change to it. A view's length and truth value are those of
384 /// its dictionary. A keys view and an items view support membership and equality by content, and a
385 /// values view equals only itself.
386 pub const DictView = struct {
387 /// The dictionary that the view shows. The view borrows this dictionary.
388 dict: *Dict,
389 /// Which part of the dictionary the view shows.
390 kind: DictViewKind,
391 };
392
393 /// A Python range: the integers from `start` toward `stop` in steps of `step`, with the count of
394 /// elements stored. `range()` and range slices make one. Membership is computed from `start`,
395 /// `stop` and `step`, in constant time. Two ranges are equal when they yield the same elements,
396 /// whatever their stops.
397 pub const Range = struct {
398 /// The first element.
399 start: i128,
400 /// The bound the elements approach and never reach.
401 stop: i128,
402 /// The difference between neighboring elements. `range` and slicing reject a step of zero with
403 /// `ValueError`.
404 step: i128,
405 /// The number of elements, computed once by `range` or by a slice.
406 length: usize,
407 };
408
409 /// The state of one walk for `for` loops, `iter`, `next`, `enumerate`, `reversed`, and the
410 /// consuming builtins, as one tag per kind of source: a dictionary's keys, `enumerate`, a
411 /// dictionary view, a list, a tuple, a range, or a string. Each `next` call or loop step advances
412 /// the walk, so items it passed are gone for every holder of the iterator. Each kind borrows what
413 /// it walks, so a list or dictionary changed during the walk is read as it stands at each step. An
414 /// iterator has no hash, so it cannot be a dictionary key. An iterator equals only itself.
415 pub const Iterator = union(enum) {
416 /// Walks a dictionary's keys.
417 dict: DictIterator,
418 /// Pairs the items of another iterator with a counter.
419 enumerate: EnumerateIterator,
420 /// Walks a dictionary view.
421 view: DictViewIterator,
422 /// Walks a list.
423 list: ListIterator,
424 /// Walks a tuple.
425 tuple: TupleIterator,
426 /// Walks a range.
427 range: RangeIterator,
428 /// Walks a string by codepoint.
429 string: StringIterator,
430 };
431
432 /// The state of a walk over a list, from the first item or from the last, for `createListIterator`
433 /// and `createListReverseIterator`. The walk ends when its count of items taken reaches the list's
434 /// current length.
435 pub const ListIterator = struct {
436 /// The borrowed list that the walk reads.
437 list: *List,
438 /// How many items the walk has taken, starting at 0. A walk from the end reads the item that
439 /// many places before the last.
440 index: usize = 0,
441 /// True for a walk from the last item to the first, and false by default.
442 reverse: bool = false,
443 };
444
445 /// The state of a walk over a dictionary's keys, in insertion order or from the newest key back,
446 /// for `createDictIterator` and `createDictReverseIterator`. The walk checks nothing when the
447 /// dictionary changes under it, so a key added or removed mid-walk shifts what the walk yields.
448 pub const DictIterator = struct {
449 /// The borrowed dictionary that the walk reads.
450 dict: *Dict,
451 /// How many keys the walk has taken, starting at 0.
452 index: usize = 0,
453 /// True for a walk from the newest key to the oldest, and false by default.
454 reverse: bool = false,
455 };
456
457 /// The state of an `enumerate` walk for `createEnumerateIterator`: an inner iterator and the
458 /// counter value its next item gets. Each step makes a new two-item tuple on the heap.
459 pub const EnumerateIterator = struct {
460 /// The borrowed inner iterator, which each step advances by one item.
461 iterator: *Iterator,
462 /// The counter value for the next item. The counter starts at the `start` argument of
463 /// `enumerate`.
464 index: i128,
465 /// Set once the counter has reached the largest signed 128-bit integer. After that, one more
466 /// item from the inner iterator fails with `IntegerOverflow`, and an exhausted inner iterator
467 /// ends the walk.
468 overflowed: bool = false,
469 };
470
471 /// The state of a walk over a dictionary view, for `createDictViewIterator` and
472 /// `createDictViewReverseIterator`: its keys, its values, or its entries as key and value tuples. A
473 /// walk over an items view makes a new tuple on the heap for each entry.
474 pub const DictViewIterator = struct {
475 /// The borrowed view that the walk reads.
476 view: *DictView,
477 /// How many entries the walk has taken, starting at 0.
478 index: usize = 0,
479 /// True for a walk from the newest entry to the oldest, and false by default.
480 reverse: bool = false,
481 };
482
483 /// The state of a walk over a tuple, from the first item or from the last, for
484 /// `createTupleIterator` and `createTupleReverseIterator`.
485 pub const TupleIterator = struct {
486 /// The borrowed tuple that the walk reads.
487 tuple: *Tuple,
488 /// How many items the walk has taken, starting at 0.
489 index: usize = 0,
490 /// True for a walk from the last item to the first, and false by default.
491 reverse: bool = false,
492 };
493
494 /// The state of a walk over a range's elements, from its start or from its last element, for
495 /// `createRangeIterator` and `createRangeReverseIterator`. The walk fails with `IntegerOverflow`
496 /// when the next element leaves the signed 128-bit range.
497 pub const RangeIterator = struct {
498 /// The borrowed range that the walk reads.
499 range: *Range,
500 /// How many elements the walk has yielded, starting at 0. The walk ends when this count reaches
501 /// the range's length. A walk from the end computes each element from this count.
502 index: usize = 0,
503 /// The element that a forward walk yields next. A new iterator holds the range's start here. A
504 /// walk from the end leaves it unused.
505 next: i128,
506 /// True for a walk from the last element to the start, and false by default.
507 reverse: bool = false,
508 };
509
510 /// The state of a walk over a string's codepoints, from the first or from the last, for
511 /// `createStringIterator` and `createStringReverseIterator`. Each step yields one codepoint as a
512 /// string that points into the same bytes. The walk fails with `ValueError` when the bytes contain
513 /// invalid UTF-8. Each step checks bytes for valid UTF-8 again: a forward walk checks the rest of
514 /// the string, and a walk from the end checks all of it. A full walk therefore takes time quadratic
515 /// in the string's length.
516 pub const StringIterator = struct {
517 /// The borrowed bytes of the string that the walk reads.
518 value: []const u8,
519 /// The byte offset of the walk's position in the string. A forward walk starts this offset at 0
520 /// and moves it forward. A walk from the end starts this offset at the string's length and
521 /// moves it back.
522 index: usize = 0,
523 /// True for a walk from the last codepoint to the first, and false by default.
524 reverse: bool = false,
525 };
526
527 const ValueContext = struct {
528 pub fn hash(_: ValueContext, value: Value) u64 {
529 return value.hash();
530 }
531
532 pub fn eql(_: ValueContext, left: Value, right: Value) bool {
533 return left.eql(right);
534 }
535 };
536
537 const DictIndex = std.HashMapUnmanaged(Value, usize, ValueContext, 80);
538
539 fn hashInto(hasher: *std.hash.Wyhash, value: Value) void {
540 if (value.integerLike()) |integer| {
541 hashTag(hasher, 1);
542 hasher.update(std.mem.asBytes(&integer));
543 return;
544 }
545 switch (value) {
546 .none => hashTag(hasher, 0),
547 .boolean, .integer => unreachable,
548 .string => |string| {
549 hashTag(hasher, 2);
550 hasher.update(std.mem.asBytes(&string.len));
551 hasher.update(string);
552 },
553 .function => |function| {
554 hashTag(hasher, 3);
555 hasher.update(std.mem.asBytes(&function));
556 },
557 .builtin => |builtin| {
558 hashTag(hasher, 4);
559 const tag: u8 = @backingInt(builtin);
560 hasher.update(&.{tag});
561 },
562 .method => |method| {
563 hashTag(hasher, 5);
564 hashNativeMethod(hasher, method);
565 },
566 .tuple => |tuple| {
567 hashTag(hasher, 6);
568 hasher.update(std.mem.asBytes(&tuple.items.len));
569 for (tuple.items) |item| hashInto(hasher, item);
570 },
571 .range => |range| {
572 hashTag(hasher, 7);
573 hasher.update(std.mem.asBytes(&range.length));
574 if (range.length != 0) hasher.update(std.mem.asBytes(&range.start));
575 if (range.length > 1) hasher.update(std.mem.asBytes(&range.step));
576 },
577 .list, .dict, .view, .iterator => unreachable,
578 }
579 }
580
581 fn hashTag(hasher: *std.hash.Wyhash, tag: u8) void {
582 hasher.update(&.{tag});
583 }
584
585 fn hashNativeMethod(hasher: *std.hash.Wyhash, method: *const NativeMethod) void {
586 const tag: u8 = @backingInt(std.meta.activeTag(method.*));
587 hasher.update(&.{tag});
588 const owner = switch (method.*) {
589 .dict_clear => |dict| @intFromPtr(dict),
590 .dict_copy => |dict| @intFromPtr(dict),
591 .dict_get => |dict| @intFromPtr(dict),
592 .dict_items => |dict| @intFromPtr(dict),
593 .dict_keys => |dict| @intFromPtr(dict),
594 .dict_pop => |dict| @intFromPtr(dict),
595 .dict_popitem => |dict| @intFromPtr(dict),
596 .dict_setdefault => |dict| @intFromPtr(dict),
597 .dict_update => |dict| @intFromPtr(dict),
598 .dict_values => |dict| @intFromPtr(dict),
599 .list_append => |list| @intFromPtr(list),
600 .list_clear => |list| @intFromPtr(list),
601 .list_copy => |list| @intFromPtr(list),
602 .list_pop => |list| @intFromPtr(list),
603 };
604 hasher.update(std.mem.asBytes(&owner));
605 }
606
607 fn listsEqual(left: *const List, right: *const List) bool {
608 if (left == right) return true;
609 return sequencesEqual(left.items, right.items);
610 }
611
612 fn sequencesEqual(left: []const Value, right: []const Value) bool {
613 if (left.len != right.len) return false;
614 for (left, right) |a, b| {
615 if (!a.eql(b)) return false;
616 }
617 return true;
618 }
619
620 fn sequenceHashable(values: []const Value) bool {
621 for (values) |item| {
622 if (!item.hashable()) return false;
623 }
624 return true;
625 }
626
627 fn nativeMethodsEqual(left: *const NativeMethod, right: *const NativeMethod) bool {
628 return switch (left.*) {
629 .dict_clear => |dict| right.* == .dict_clear and right.dict_clear == dict,
630 .dict_copy => |dict| right.* == .dict_copy and right.dict_copy == dict,
631 .dict_get => |dict| right.* == .dict_get and right.dict_get == dict,
632 .dict_items => |dict| right.* == .dict_items and right.dict_items == dict,
633 .dict_keys => |dict| right.* == .dict_keys and right.dict_keys == dict,
634 .dict_pop => |dict| right.* == .dict_pop and right.dict_pop == dict,
635 .dict_popitem => |dict| right.* == .dict_popitem and right.dict_popitem == dict,
636 .dict_setdefault => |dict| right.* == .dict_setdefault and right.dict_setdefault == dict,
637 .dict_update => |dict| right.* == .dict_update and right.dict_update == dict,
638 .dict_values => |dict| right.* == .dict_values and right.dict_values == dict,
639 .list_append => |list| right.* == .list_append and right.list_append == list,
640 .list_clear => |list| right.* == .list_clear and right.list_clear == list,
641 .list_copy => |list| right.* == .list_copy and right.list_copy == list,
642 .list_pop => |list| right.* == .list_pop and right.list_pop == list,
643 };
644 }
645
646 fn dictsEqual(left: *const Dict, right: *const Dict) bool {
647 if (left == right) return true;
648 if (left.entries.items.len != right.entries.items.len) return false;
649 for (left.entries.items) |entry| {
650 const index = right.indexOf(entry.key) orelse return false;
651 if (!entry.value.eql(right.entries.items[index].value)) return false;
652 }
653 return true;
654 }
655
656 fn dictViewsEqual(left: *const DictView, right: *const DictView) bool {
657 if (left == right) return true;
658 if (left.kind != right.kind) return false;
659 return switch (left.kind) {
660 .keys => dictKeysEqual(left.dict, right.dict),
661 .items => dictsEqual(left.dict, right.dict),
662 .values => false,
663 };
664 }
665
666 fn dictKeysEqual(left: *const Dict, right: *const Dict) bool {
667 if (left.entries.items.len != right.entries.items.len) return false;
668 for (left.entries.items) |entry| {
669 if (right.indexOf(entry.key) == null) return false;
670 }
671 return true;
672 }
673
674 fn rangesEqual(left: *const Range, right: *const Range) bool {
675 if (left.length != right.length) return false;
676 if (left.length == 0) return true;
677 if (left.start != right.start) return false;
678 if (left.length == 1) return true;
679 return left.step == right.step;
680 }
681
682 test "boolean values behave as Python integers in arithmetic contexts" {
683 try std.testing.expectEqual(@as(?i128, 1), (Value{ .boolean = true }).integerLike());
684 try std.testing.expectEqual(@as(?i128, 0), (Value{ .boolean = false }).integerLike());
685 }
686
687 test "equality follows Python integer boolean behavior" {
688 try std.testing.expect((Value{ .boolean = true }).eql(.{ .integer = 1 }));
689 try std.testing.expect((Value{ .boolean = false }).eql(.{ .integer = 0 }));
690 try std.testing.expect((Value{ .none = {} }).eql(.none));
691 try std.testing.expect(!(Value{ .none = {} }).eql(.{ .integer = 0 }));
692 }
693
694 test "string values have Python truthiness and equality" {
695 try std.testing.expect(!(Value{ .string = "" }).truthy());
696 try std.testing.expect((Value{ .string = "x" }).truthy());
697 try std.testing.expect((Value{ .string = "alpha" }).eql(.{ .string = "alpha" }));
698 try std.testing.expect(!(Value{ .string = "alpha" }).eql(.{ .string = "beta" }));
699 }
700
701 test "list values have Python truthiness and equality" {
702 var left_items = [_]Value{ .{ .integer = 1 }, .{ .string = "x" } };
703 var right_items = [_]Value{ .{ .integer = 1 }, .{ .string = "x" } };
704 var different_items = [_]Value{.{ .integer = 1 }};
705 var empty: List = .empty;
706 var left = List{ .items = &left_items, .capacity = left_items.len };
707 var right = List{ .items = &right_items, .capacity = right_items.len };
708 var different = List{ .items = &different_items, .capacity = different_items.len };
709
710 try std.testing.expect(!(Value{ .list = &empty }).truthy());
711 try std.testing.expect((Value{ .list = &left }).truthy());
712 try std.testing.expect((Value{ .list = &left }).eql(.{ .list = &right }));
713 try std.testing.expect(!(Value{ .list = &left }).eql(.{ .list = &different }));
714 }
715
716 test "tuple values have Python truthiness and equality" {
717 var left_items = [_]Value{ .{ .integer = 1 }, .{ .string = "x" } };
718 var right_items = [_]Value{ .{ .integer = 1 }, .{ .string = "x" } };
719 var different_items = [_]Value{.{ .integer = 1 }};
720 var empty = Tuple{ .items = &.{} };
721 var left = Tuple{ .items = &left_items };
722 var right = Tuple{ .items = &right_items };
723 var different = Tuple{ .items = &different_items };
724
725 try std.testing.expect(!(Value{ .tuple = &empty }).truthy());
726 try std.testing.expect((Value{ .tuple = &left }).truthy());
727 try std.testing.expect((Value{ .tuple = &left }).eql(.{ .tuple = &right }));
728 try std.testing.expect(!(Value{ .tuple = &left }).eql(.{ .tuple = &different }));
729 }
730
731 test "range values have Python truthiness and equality" {
732 var empty = Range{ .start = 0, .stop = 0, .step = 1, .length = 0 };
733 var single = Range{ .start = 1, .stop = 2, .step = 1, .length = 1 };
734 var same_single = Range{ .start = 1, .stop = 20, .step = 3, .length = 1 };
735 var left = Range{ .start = 0, .stop = 3, .step = 2, .length = 2 };
736 var right = Range{ .start = 0, .stop = 4, .step = 2, .length = 2 };
737 var different = Range{ .start = 0, .stop = 5, .step = 2, .length = 3 };
738
739 try std.testing.expect(!(Value{ .range = &empty }).truthy());
740 try std.testing.expect((Value{ .range = &single }).truthy());
741 try std.testing.expect((Value{ .range = &single }).eql(.{ .range = &same_single }));
742 try std.testing.expect((Value{ .range = &left }).eql(.{ .range = &right }));
743 try std.testing.expect(!(Value{ .range = &left }).eql(.{ .range = &different }));
744 }
745
746 test "iterator values are truthy and compare by identity" {
747 var list: List = .empty;
748 var left = Iterator{ .list = .{ .list = &list } };
749 var right = Iterator{ .list = .{ .list = &list } };
750
751 try std.testing.expect((Value{ .iterator = &left }).truthy());
752 try std.testing.expect((Value{ .iterator = &left }).eql(.{ .iterator = &left }));
753 try std.testing.expect(!(Value{ .iterator = &left }).eql(.{ .iterator = &right }));
754 }
755
756 test "equal hashable values share hashes" {
757 var left_tuple_items = [_]Value{ .{ .boolean = true }, .{ .string = "tuple" } };
758 var right_tuple_items = [_]Value{ .{ .integer = 1 }, .{ .string = "tuple" } };
759 var left_tuple = Tuple{ .items = &left_tuple_items };
760 var right_tuple = Tuple{ .items = &right_tuple_items };
761 var left_empty_range = Range{ .start = 4, .stop = 4, .step = 1, .length = 0 };
762 var right_empty_range = Range{ .start = 90, .stop = -10, .step = -5, .length = 0 };
763 var left_list: List = .empty;
764 var left_method = NativeMethod{ .list_append = &left_list };
765 var right_method = NativeMethod{ .list_append = &left_list };
766
767 const pairs = [_][2]Value{
768 .{ .{ .boolean = true }, .{ .integer = 1 } },
769 .{ .{ .string = "same" }, .{ .string = "same" } },
770 .{ .{ .tuple = &left_tuple }, .{ .tuple = &right_tuple } },
771 .{ .{ .range = &left_empty_range }, .{ .range = &right_empty_range } },
772 .{ .{ .method = &left_method }, .{ .method = &right_method } },
773 };
774 for (pairs) |pair| {
775 try std.testing.expect(pair[0].eql(pair[1]));
776 try std.testing.expectEqual(pair[0].hash(), pair[1].hash());
777 }
778 }
779
780 test "list geometric storage supports allocation-free retained refill" {
781 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{});
782 var list: List = .empty;
783 defer list.deinit(failing.allocator());
784
785 for (0..4096) |index| try list.append(failing.allocator(), .{ .integer = @intCast(index) });
786 const capacity = list.capacity;
787 const pointer = list.items.ptr;
788 const growth_attempts = failing.alloc_index + failing.resize_index;
789 try std.testing.expect(capacity >= list.items.len);
790 try std.testing.expect(growth_attempts < 64);
791
792 list.clearRetainingCapacity();
793 failing.fail_index = failing.alloc_index;
794 failing.resize_fail_index = failing.resize_index;
795 for (0..4096) |index| try list.append(failing.allocator(), .{ .integer = @intCast(index) });
796
797 try std.testing.expect(!failing.has_induced_failure);
798 try std.testing.expectEqual(capacity, list.capacity);
799 try std.testing.expectEqual(pointer, list.items.ptr);
800 }
801
802 test "dictionary hashes equality while retaining insertion order" {
803 var dict: Dict = .{};
804 defer dict.deinit(std.testing.allocator);
805
806 try dict.put(std.testing.allocator, .{ .boolean = true }, .{ .string = "first" });
807 try dict.put(std.testing.allocator, .{ .integer = 2 }, .{ .string = "second" });
808 try dict.put(std.testing.allocator, .{ .integer = 1 }, .{ .string = "updated" });
809
810 try std.testing.expectEqual(@as(usize, 2), dict.entries.items.len);
811 try std.testing.expect(dict.entries.items[0].key == .boolean);
812 try std.testing.expectEqualStrings("updated", dict.entries.items[dict.indexOf(.{ .integer = 1 }).?].value.string);
813
814 _ = dict.removeAt(dict.indexOf(.{ .integer = 1 }).?);
815 try dict.put(std.testing.allocator, .{ .boolean = true }, .{ .string = "reinserted" });
816
817 try std.testing.expectEqual(@as(i128, 2), dict.entries.items[0].key.integer);
818 try std.testing.expect(dict.entries.items[1].key == .boolean);
819 try std.testing.expectEqual(@as(usize, 0), dict.indexOf(.{ .integer = 2 }).?);
820 try std.testing.expectEqual(@as(usize, 1), dict.indexOf(.{ .integer = 1 }).?);
821 }
822
823 test "dictionary insertion failure leaves both stores unchanged" {
824 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{});
825 var dict: Dict = .{};
826 defer dict.deinit(failing.allocator());
827 try dict.entries.ensureTotalCapacity(failing.allocator(), 1);
828
829 failing.fail_index = failing.alloc_index;
830 try std.testing.expectError(error.OutOfMemory, dict.put(failing.allocator(), .{ .integer = 7 }, .none));
831 try std.testing.expectEqual(@as(usize, 0), dict.entries.items.len);
832 try std.testing.expectEqual(@as(u32, 0), dict.index.count());
833
834 failing.fail_index = std.math.maxInt(usize);
835 try dict.put(failing.allocator(), .{ .integer = 7 }, .none);
836 try std.testing.expectEqual(@as(usize, 0), dict.indexOf(.{ .integer = 7 }).?);
837 }
838
839 test "dictionary existing updates allocate no working memory" {
840 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{});
841 var dict: Dict = .{};
842 defer dict.deinit(failing.allocator());
843 for (0..1024) |index| try dict.put(failing.allocator(), .{ .integer = @intCast(index) }, .none);
844
845 failing.fail_index = failing.alloc_index;
846 failing.resize_fail_index = failing.resize_index;
847 for (0..1024) |index| {
848 const key = Value{ .integer = @intCast(index) };
849 try dict.put(failing.allocator(), key, key);
850 try std.testing.expectEqual(index, dict.indexOf(key).?);
851 }
852
853 try std.testing.expect(!failing.has_induced_failure);
854 }