tiny.python.object.value

1pub const value = @import("value.zig");

1//! Every Python value the package handles is one tagged union: `None`, booleans and integers are2//! 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 every6//! step, so a value has to be small and cheap to copy. Python's rules for truth, equality and7//! 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, so10//! `True == 1` holds and a dictionary finds the key `1` under `True`. A dictionary has to keep11//! insertion order and find keys by hash, and only values that cannot change may be keys. Two lists12//! can hold the same items and still be different objects, so equality and identity are separate13//! questions.14//!15//! The values follow the rules of the [Python 3.14 language16//! reference](https://docs.python.org/3.14/reference/), and the file's tests check them: Python's17//! truth rules, its integer reading of booleans, its equality for strings, lists, tuples and18//! 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, so21//! arithmetic that leaves that range fails with `IntegerOverflow`. A string is a borrowed slice of22//! UTF-8 bytes that points into the source text or into the heap. Length, iteration and slicing of23//! 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 its25//! entries in an array in insertion order and maps each key to its entry's position in a separate26//! hash table, so lookup goes by hash and iteration goes by insertion order. Removing a dictionary27//! entry shifts every later entry down one position and updates each later entry's position in the28//! hash table, so removal takes time linear in the number of later entries. `hash` uses Wyhash with29//! a fixed seed, so a value hashes the same in every run. `hash` reads a boolean as its integer, so30//! equal keys share a hash. Each iterator is a small record that points to what it walks and holds31//! a position, with a flag for walking from the end.32const std = @import("std");3334/// One Python value, as a tagged union of thirteen kinds. The virtual machine reads and writes35/// values in every operation, and `Result.value` is one. `None`, booleans and integers live in the36/// value itself, a string is a slice of bytes held elsewhere, and every other kind points to an37/// object held elsewhere. The objects that the virtual machine makes live on its heap. Copying a38/// value copies the pointer, so both copies refer to the same object.39pub const Value = union(enum) {40    /// Python's `None`, with no payload. `None` is false by Python's truth rules and equal only to41    /// `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 with48    /// `IntegerOverflow`.49    integer: i128,50    /// A Python string, as a slice of UTF-8 bytes that the value borrows. A string literal and its51    /// slices with step 1 point into the source text, and a string the run built points into the52    /// heap. Two strings are equal when their bytes are equal. Two strings are the same object53    /// 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 a61    /// `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 owns64    /// it.65    list: *List,66    /// A pointer to a Python tuple. When the virtual machine made the tuple, the machine's heap67    /// owns it.68    tuple: *Tuple,69    /// A pointer to a Python dictionary. When the virtual machine made the dictionary, the70    /// 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,7879    /// 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, dictionary81    /// 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    }100101    /// 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 repetition103    /// 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    }121122    /// Returns whether the value may be a dictionary key, so the virtual machine checks it before123    /// 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 a126    /// 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    }134135    /// Returns whether two values are equal by Python's rules, for `==`, `!=`, membership tests and136    /// dictionary lookups. Integers and booleans compare by their integer value. Strings compare137    /// their bytes, and lists and tuples compare item by item. Two dictionaries are equal when they138    /// hold equal values under the same keys, in any order. Two ranges are equal when they yield139    /// the same elements. Keys views compare their dictionaries' keys, items views compare their140    /// dictionaries, and a values view equals only itself. Two bound methods are equal when they141    /// have the same method and the same receiver. Functions and builtins compare their positions142    /// 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 before144    /// 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 containing146    /// that same list. Two distinct lists or dictionaries that each contain themselves recurse147    /// until the native stack overflows when comparison reaches those self-references because148    /// 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    }199200    /// Returns a 64-bit Wyhash of the value, with a fixed seed, so a value hashes the same in every201    /// run. The dictionary's hash table hashes keys with it. Equal values hash equally: an integer202    /// and the boolean with its value share a hash, and so do equal ranges and equal tuples. A203    /// bound method hashes its method and its receiver's address. The function asserts that the204    /// 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};212213/// 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 machine215/// pushes one when a name matches no local or global variable. Calling a builtin runs it inside the216/// virtual machine and pushes its result.217pub const Builtin = enum {218    dict,219    enumerate,220    iter,221    len,222    list,223    next,224    range,225    reversed,226    tuple,227};228229/// A list or dictionary method bound to the object it was read from, as a tagged union with one tag230/// 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 the232/// 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. Each235/// read makes a new bound method, so two reads give equal values that are different objects. A236/// bound method is hashable, so it can be a dictionary key.237pub 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};253254/// A Python list, as a Zig growable array of values. The virtual machine's lists are these, and the255/// package's property test and benchmark drive one directly. The array grows geometrically, so256/// filling it takes few allocations. After `clearRetainingCapacity`, refilling the array to its old257/// length allocates nothing and keeps the same storage. The virtual machine's `clear` method frees258/// the storage. When `pop` or `del` leaves fewer than half of the slots in use, the virtual machine259/// shrinks the storage to fit the items.260pub const List = std.ArrayListUnmanaged(Value);261262/// A Python tuple, as a fixed slice of values. Tuple displays, `tuple()` and the pairs that263/// dictionaries and `enumerate` yield are these. The virtual machine never changes a tuple after264/// making it, so a tuple of hashable items can be a dictionary key.265pub const Tuple = struct {266    /// The tuple's values, in order. When the virtual machine made the tuple, the machine's heap267    /// owns this array.268    items: []Value,269};270271/// A Python dictionary that keeps insertion order: an array of key and value entries, in the order272/// the keys first arrived, and a hash table from each key to its entry's position. Dictionary273/// displays, `dict()` and `copy()` make these, and the package's property test and benchmark drive274/// one directly. An empty dictionary is `.{}`. Finding a key and replacing its value take expected275/// constant time and allocate nothing. Removing an entry shifts every later entry down one position276/// and updates each later entry's position in the hash table, so removal takes time linear in the277/// number of later entries. The hash table grows when it is more than 80 percent full. Every key278/// has to be hashable, and `put` asserts it.279pub const Dict = struct {280    /// The key and value pairs in insertion order. Iteration, `popLast` and equality read this281    /// 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 with284    /// `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,287288    /// Frees the entries and the hash table with the given allocator and leaves the dictionary289    /// undefined. The heap frees each dictionary it owns with it. The call frees nothing that the290    /// 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    }296297    /// 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 allocates299    /// nothing, so it cannot fail.300    pub fn clearRetainingCapacity(self: *Dict) void {301        self.entries.clearRetainingCapacity();302        self.index.clearRetainingCapacity();303    }304305    /// 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 inserting307    /// many keys. The call returns `error.OutOfMemory` when an allocation fails. The call also308    /// 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    }315316    /// Returns the position of the key's entry in `entries`, or null when the key is absent. Every317    /// dictionary lookup, membership test and deletion in the virtual machine starts with it. The318    /// 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    }322323    /// When an equal key is present, replaces that entry's value, and the entry keeps its position324    /// and its first key. Any other key goes with its value into a new entry at the end. Every325    /// dictionary insertion in the virtual machine goes through it. Replacing a value allocates326    /// nothing. The call asserts that the key is hashable. On `error.OutOfMemory`, both the entry327    /// 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    }339340    /// 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 each342    /// later entry's position in the hash table. The call takes time linear in the number of343    /// entries after the position. The position has to be in range. The call allocates nothing, so344    /// 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    }353354    /// Removes the most recently inserted entry and returns it, or returns null when the dictionary355    /// is empty. `d.popitem()` removes the newest entry with it. The call leaves every other entry356    /// 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};363364/// One key and its value in a dictionary. A dictionary's entry array holds these, and `createDict`365/// takes a slice of them.366pub 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};372373/// The part of a dictionary a view shows, one tag each, named after the Python method that returns374/// the view: `keys`, `values` and `items`. A dictionary view carries one. An items view yields each375/// entry as a two-item tuple of key and value.376pub const DictViewKind = enum {377    keys,378    values,379    items,380};381382/// A live view of one dictionary. `keys()`, `values()` and `items()` return one. The view borrows383/// the dictionary and shows every later change to it. A view's length and truth value are those of384/// its dictionary. A keys view and an items view support membership and equality by content, and a385/// values view equals only itself.386pub 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};392393/// A Python range: the integers from `start` toward `stop` in steps of `step`, with the count of394/// 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.397pub 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 with403    /// `ValueError`.404    step: i128,405    /// The number of elements, computed once by `range` or by a slice.406    length: usize,407};408409/// The state of one walk for `for` loops, `iter`, `next`, `enumerate`, `reversed`, and the410/// consuming builtins, as one tag per kind of source: a dictionary's keys, `enumerate`, a411/// dictionary view, a list, a tuple, a range, or a string. Each `next` call or loop step advances412/// the walk, so items it passed are gone for every holder of the iterator. Each kind borrows what413/// it walks, so a list or dictionary changed during the walk is read as it stands at each step. An414/// iterator has no hash, so it cannot be a dictionary key. An iterator equals only itself.415pub 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};431432/// 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's434/// current length.435pub 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 that439    /// 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};444445/// 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 the447/// dictionary changes under it, so a key added or removed mid-walk shifts what the walk yields.448pub 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};456457/// The state of an `enumerate` walk for `createEnumerateIterator`: an inner iterator and the458/// counter value its next item gets. Each step makes a new two-item tuple on the heap.459pub 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 of463    /// `enumerate`.464    index: i128,465    /// Set once the counter has reached the largest signed 128-bit integer. After that, one more466    /// item from the inner iterator fails with `IntegerOverflow`, and an exhausted inner iterator467    /// ends the walk.468    overflowed: bool = false,469};470471/// The state of a walk over a dictionary view, for `createDictViewIterator` and472/// `createDictViewReverseIterator`: its keys, its values, or its entries as key and value tuples. A473/// walk over an items view makes a new tuple on the heap for each entry.474pub 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};482483/// The state of a walk over a tuple, from the first item or from the last, for484/// `createTupleIterator` and `createTupleReverseIterator`.485pub 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};493494/// The state of a walk over a range's elements, from its start or from its last element, for495/// `createRangeIterator` and `createRangeReverseIterator`. The walk fails with `IntegerOverflow`496/// when the next element leaves the signed 128-bit range.497pub 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 reaches501    /// 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. A504    /// 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};509510/// The state of a walk over a string's codepoints, from the first or from the last, for511/// `createStringIterator` and `createStringReverseIterator`. Each step yields one codepoint as a512/// string that points into the same bytes. The walk fails with `ValueError` when the bytes contain513/// invalid UTF-8. Each step checks bytes for valid UTF-8 again: a forward walk checks the rest of514/// the string, and a walk from the end checks all of it. A full walk therefore takes time quadratic515/// in the string's length.516pub 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 0520    /// and moves it forward. A walk from the end starts this offset at the string's length and521    /// 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};526527const ValueContext = struct {528    pub fn hash(_: ValueContext, value: Value) u64 {529        return value.hash();530    }531532    pub fn eql(_: ValueContext, left: Value, right: Value) bool {533        return left.eql(right);534    }535};536537const DictIndex = std.HashMapUnmanaged(Value, usize, ValueContext, 80);538539fn 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}580581fn hashTag(hasher: *std.hash.Wyhash, tag: u8) void {582    hasher.update(&.{tag});583}584585fn 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}606607fn listsEqual(left: *const List, right: *const List) bool {608    if (left == right) return true;609    return sequencesEqual(left.items, right.items);610}611612fn 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}619620fn sequenceHashable(values: []const Value) bool {621    for (values) |item| {622        if (!item.hashable()) return false;623    }624    return true;625}626627fn 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}645646fn 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}655656fn 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}665666fn 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}673674fn 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}681682test "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}686687test "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}693694test "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}700701test "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 };709710    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}715716test "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 };724725    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}730731test "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 };738739    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}745746test "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 } };750751    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}755756test "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 };766767    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}779780test "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());784785    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);791792    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) });796797    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}801802test "dictionary hashes equality while retaining insertion order" {803    var dict: Dict = .{};804    defer dict.deinit(std.testing.allocator);805806    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" });809810    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);813814    _ = dict.removeAt(dict.indexOf(.{ .integer = 1 }).?);815    try dict.put(std.testing.allocator, .{ .boolean = true }, .{ .string = "reinserted" });816817    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}822823test "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);828829    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());833834    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}838839test "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);844845    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    }852853    try std.testing.expect(!failing.has_induced_failure);854}