tiny.python.object.heap

1//! The heap owns every object the virtual machine creates while it runs a program: lists, tuples,2//! dictionaries, ranges, copied strings, iterators, bound methods and dictionary views. A program's3//! values point at each other freely, and a list can hold itself. Every object has to be freed4//! exactly once, when the caller is done with the program's result.5//!6//! Values are copied between the stack, the variables and the containers with no bookkeeping, so7//! nothing records when an object stops being used.8//!9//! The heap keeps one list of pointers for each kind of object, and `deinit` frees every object at10//! once. Every object lives until the heap is freed, so a run's memory grows with each object it11//! creates, including the bound method made by each method read and the iterator made by each loop.12//! Each create function allocates the object and a slot in its list. When an allocation fails, a13//! create function frees what it allocated and leaves the heap as it was. The package's `execute`14//! moves the heap out of the virtual machine into its `Result`, so the values of the result stay15//! valid until `Result.deinit`.16const std = @import("std");17const value = @import("value.zig");1819/// The allocator and, for each kind of object, one list holding every object the virtual machine20/// created. The virtual machine creates every object through a heap, and `execute` hands it to the21/// caller inside `Result`. A heap is made with `init` and freed with `deinit`, which frees every22/// object at once. Nothing is freed before `deinit`.23pub const Heap = struct {24    /// The allocator given to `init`. Every object and every list of the heap comes from it.25    allocator: std.mem.Allocator,26    /// Every list the heap created, each with its item storage.27    lists: std.ArrayListUnmanaged(*value.List) = .empty,28    /// Every tuple the heap created, each with its array of items.29    tuples: std.ArrayListUnmanaged(*value.Tuple) = .empty,30    /// Every dictionary the heap created, each with its entries and its hash table.31    dicts: std.ArrayListUnmanaged(*value.Dict) = .empty,32    /// Every range the heap created.33    ranges: std.ArrayListUnmanaged(*value.Range) = .empty,34    /// The bytes of every string the heap copied. A string literal and its slices borrow the source35    /// text, so they have no entry here.36    strings: std.ArrayListUnmanaged([]u8) = .empty,37    /// Every iterator the heap created, one for each loop, `iter` call or consuming builtin that38    /// started a walk.39    iterators: std.ArrayListUnmanaged(*value.Iterator) = .empty,40    /// Every bound method the heap created, one for each method read.41    methods: std.ArrayListUnmanaged(*value.NativeMethod) = .empty,42    /// Every dictionary view the heap created.43    views: std.ArrayListUnmanaged(*value.DictView) = .empty,4445    /// Returns an empty heap that allocates from the given allocator. `Vm.init` makes the machine's46    /// heap with it, and `Vm.takeHeap` makes the empty heap it leaves behind. The call allocates47    /// nothing, so it cannot fail.48    pub fn init(allocator: std.mem.Allocator) Heap {49        return .{ .allocator = allocator };50    }5152    /// Frees every object with its storage, then the eight lists, and leaves the heap undefined.53    /// `Result.deinit` and `Vm.deinit` call it to free a run's objects. Every value that points54    /// into the heap is invalid afterwards.55    pub fn deinit(self: *Heap) void {56        for (self.iterators.items) |iterator| {57            self.allocator.destroy(iterator);58        }59        for (self.methods.items) |method| {60            self.allocator.destroy(method);61        }62        for (self.views.items) |view| {63            self.allocator.destroy(view);64        }65        for (self.lists.items) |list| {66            list.deinit(self.allocator);67            self.allocator.destroy(list);68        }69        for (self.tuples.items) |tuple| {70            self.allocator.free(tuple.items);71            self.allocator.destroy(tuple);72        }73        for (self.dicts.items) |dict| {74            dict.deinit(self.allocator);75            self.allocator.destroy(dict);76        }77        for (self.ranges.items) |range| {78            self.allocator.destroy(range);79        }80        for (self.strings.items) |string| {81            self.allocator.free(string);82        }83        self.lists.deinit(self.allocator);84        self.tuples.deinit(self.allocator);85        self.dicts.deinit(self.allocator);86        self.ranges.deinit(self.allocator);87        self.strings.deinit(self.allocator);88        self.iterators.deinit(self.allocator);89        self.methods.deinit(self.allocator);90        self.views.deinit(self.allocator);91        self.* = undefined;92    }9394    /// Returns a list value that holds a copy of the given items, in a new list that the heap owns.95    /// The virtual machine makes every new list with it, for list displays, `list()`, joins,96    /// repeats, slices and copies. The copy takes the item values, so the objects they point to are97    /// shared. The call returns `error.OutOfMemory` when an allocation fails, after freeing what it98    /// allocated.99    pub fn createList(self: *Heap, items: []const value.Value) std.mem.Allocator.Error!value.Value {100        const list = try self.allocator.create(value.List);101        errdefer self.allocator.destroy(list);102        list.* = .empty;103        errdefer list.deinit(self.allocator);104        try list.appendSlice(self.allocator, items);105        try self.lists.append(self.allocator, list);106        return .{ .list = list };107    }108109    /// Returns a tuple value that holds a copy of the given items. The virtual machine makes every110    /// new tuple with it, for tuple displays, `tuple()`, joins, repeats, slices and the pairs that111    /// dictionaries and `enumerate` yield. The heap owns the tuple and its array, which has exactly112    /// one slot per item. The copy takes the item values, so the objects they point to are shared.113    /// The call returns `error.OutOfMemory` when an allocation fails, after freeing what it114    /// allocated.115    pub fn createTuple(self: *Heap, items: []const value.Value) std.mem.Allocator.Error!value.Value {116        const owned_items = try self.allocator.dupe(value.Value, items);117        errdefer self.allocator.free(owned_items);118        const tuple = try self.allocator.create(value.Tuple);119        errdefer self.allocator.destroy(tuple);120        tuple.* = .{ .items = owned_items };121        try self.tuples.append(self.allocator, tuple);122        return .{ .tuple = tuple };123    }124125    /// Returns a dictionary value that holds the given entries in order. The virtual machine makes126    /// every new dictionary with it, for displays, `dict()` and `copy()`. A repeated key keeps its127    /// first position and takes the later value. The call reserves room for every entry before it128    /// inserts the first. Every key has to be hashable, and the insertion asserts it. The call129    /// returns `error.OutOfMemory` when an allocation fails or when there are more entries than a130    /// 32-bit count holds, after freeing what it allocated.131    pub fn createDict(self: *Heap, entries: []const value.DictEntry) std.mem.Allocator.Error!value.Value {132        const dict = try self.allocator.create(value.Dict);133        errdefer self.allocator.destroy(dict);134        dict.* = .{};135        errdefer dict.deinit(self.allocator);136        try dict.ensureTotalCapacity(self.allocator, entries.len);137        for (entries) |entry| try dict.put(self.allocator, entry.key, entry.value);138        try self.dicts.append(self.allocator, dict);139        return .{ .dict = dict };140    }141142    /// Returns a range value with the given start, stop, step and element count. `range()` and143    /// range slices make each new range with it. The call stores the count as given without144    /// checking it against the other three, so the caller computes it. The call returns145    /// `error.OutOfMemory` when an allocation fails, after freeing what it allocated.146    pub fn createRange(self: *Heap, start: i128, stop: i128, step: i128, length: usize) std.mem.Allocator.Error!value.Value {147        const range = try self.allocator.create(value.Range);148        errdefer self.allocator.destroy(range);149        range.* = .{150            .start = start,151            .stop = stop,152            .step = step,153            .length = length,154        };155        try self.ranges.append(self.allocator, range);156        return .{ .range = range };157    }158159    /// Returns a string value that holds a copy of the given bytes. The virtual machine makes every160    /// string it builds with it, for joins, repeats and slices with a step other than 1. The heap161    /// owns the copy. The call returns `error.OutOfMemory` when an allocation fails, after freeing162    /// what it allocated.163    pub fn createString(self: *Heap, bytes: []const u8) std.mem.Allocator.Error!value.Value {164        const owned = try self.allocator.dupe(u8, bytes);165        errdefer self.allocator.free(owned);166        try self.strings.append(self.allocator, owned);167        return .{ .string = owned };168    }169170    /// Returns an iterator that walks the list from its first item. `iter`, `for` loops and the171    /// builtins that consume a list start their walk with it. The iterator borrows the list and172    /// reads its length at each step, so items appended during the walk are visited. The call173    /// returns `error.OutOfMemory` when an allocation fails.174    pub fn createListIterator(self: *Heap, list: *value.List) std.mem.Allocator.Error!value.Value {175        return try self.createIterator(.{ .list = .{ .list = list } });176    }177178    /// Returns an iterator that walks the list from its last item to its first. `reversed` starts179    /// its walk of a list with it. The iterator borrows the list. The call returns180    /// `error.OutOfMemory` when an allocation fails.181    pub fn createListReverseIterator(self: *Heap, list: *value.List) std.mem.Allocator.Error!value.Value {182        return try self.createIterator(.{ .list = .{ .list = list, .reverse = true } });183    }184185    /// Returns an iterator over the dictionary's keys, in insertion order. `iter`, `for` loops and186    /// `list()` start their walk of a dictionary with it. The iterator borrows the dictionary. The187    /// call returns `error.OutOfMemory` when an allocation fails.188    pub fn createDictIterator(self: *Heap, dict: *value.Dict) std.mem.Allocator.Error!value.Value {189        return try self.createIterator(.{ .dict = .{ .dict = dict } });190    }191192    /// Returns an iterator over the dictionary's keys, from the last inserted to the first.193    /// `reversed` starts its walk of a dictionary with it. The iterator borrows the dictionary. The194    /// call returns `error.OutOfMemory` when an allocation fails.195    pub fn createDictReverseIterator(self: *Heap, dict: *value.Dict) std.mem.Allocator.Error!value.Value {196        return try self.createIterator(.{ .dict = .{ .dict = dict, .reverse = true } });197    }198199    /// Returns an iterator that pairs each item of the given iterator with a counter that starts at200    /// `start`, as a two-item tuple. `enumerate` wraps the iterator of its argument with it. The201    /// new iterator borrows the given one and advances it. The call returns `error.OutOfMemory`202    /// when an allocation fails.203    pub fn createEnumerateIterator(self: *Heap, iterator: *value.Iterator, start: i128) std.mem.Allocator.Error!value.Value {204        return try self.createIterator(.{ .enumerate = .{205            .iterator = iterator,206            .index = start,207        } });208    }209210    /// Returns an iterator over a dictionary view, in insertion order: keys, values, or key and211    /// value tuples, as the view's kind says. `iter`, `for` loops and the consuming builtins start212    /// their walk of a dictionary view with it. The iterator borrows the view. The call returns213    /// `error.OutOfMemory` when an allocation fails.214    pub fn createDictViewIterator(self: *Heap, view: *value.DictView) std.mem.Allocator.Error!value.Value {215        return try self.createIterator(.{ .view = .{ .view = view } });216    }217218    /// Returns an iterator over a dictionary view, from the last inserted entry to the first.219    /// `reversed` starts its walk of a dictionary view with it. The iterator borrows the view. The220    /// call returns `error.OutOfMemory` when an allocation fails.221    pub fn createDictViewReverseIterator(self: *Heap, view: *value.DictView) std.mem.Allocator.Error!value.Value {222        return try self.createIterator(.{ .view = .{ .view = view, .reverse = true } });223    }224225    /// Returns an iterator that walks the tuple from its first item. `iter`, `for` loops and the226    /// consuming builtins start their walk of a tuple with it. The iterator borrows the tuple. The227    /// call returns `error.OutOfMemory` when an allocation fails.228    pub fn createTupleIterator(self: *Heap, tuple: *value.Tuple) std.mem.Allocator.Error!value.Value {229        return try self.createIterator(.{ .tuple = .{ .tuple = tuple } });230    }231232    /// Returns an iterator that walks the tuple from its last item to its first. `reversed` starts233    /// its walk of a tuple with it. The iterator borrows the tuple. The call returns234    /// `error.OutOfMemory` when an allocation fails.235    pub fn createTupleReverseIterator(self: *Heap, tuple: *value.Tuple) std.mem.Allocator.Error!value.Value {236        return try self.createIterator(.{ .tuple = .{ .tuple = tuple, .reverse = true } });237    }238239    /// Returns an iterator that yields the range's elements from its start. `iter`, `for` loops and240    /// the consuming builtins start their walk of a range with it. The iterator borrows the range.241    /// The call returns `error.OutOfMemory` when an allocation fails.242    pub fn createRangeIterator(self: *Heap, range: *value.Range) std.mem.Allocator.Error!value.Value {243        return try self.createIterator(.{ .range = .{244            .range = range,245            .next = range.start,246        } });247    }248249    /// Returns an iterator that yields the range's elements from its last to its start. `reversed`250    /// starts its walk of a range with it. The iterator computes each element from its position.251    /// The iterator borrows the range. The call returns `error.OutOfMemory` when an allocation252    /// fails.253    pub fn createRangeReverseIterator(self: *Heap, range: *value.Range) std.mem.Allocator.Error!value.Value {254        return try self.createIterator(.{ .range = .{255            .range = range,256            .next = range.start,257            .reverse = true,258        } });259    }260261    /// Returns an iterator that yields each codepoint of the string as a string of its own,262    /// pointing into the same bytes. `iter`, `for` loops and the consuming builtins start their263    /// walk of a string with it. The iterator borrows the bytes. The call returns264    /// `error.OutOfMemory` when an allocation fails.265    pub fn createStringIterator(self: *Heap, string: []const u8) std.mem.Allocator.Error!value.Value {266        return try self.createIterator(.{ .string = .{ .value = string } });267    }268269    /// Returns an iterator that yields each codepoint of the string from the last to the first, as270    /// strings pointing into the same bytes. `reversed` starts its walk of a string with it. The271    /// iterator borrows the bytes and starts its position at their end. The call returns272    /// `error.OutOfMemory` when an allocation fails.273    pub fn createStringReverseIterator(self: *Heap, string: []const u8) std.mem.Allocator.Error!value.Value {274        return try self.createIterator(.{ .string = .{275            .value = string,276            .index = string.len,277            .reverse = true,278        } });279    }280281    fn createIterator(self: *Heap, value_iterator: value.Iterator) std.mem.Allocator.Error!value.Value {282        const iterator = try self.allocator.create(value.Iterator);283        errdefer self.allocator.destroy(iterator);284        iterator.* = value_iterator;285        try self.iterators.append(self.allocator, iterator);286        return .{ .iterator = iterator };287    }288289    /// Returns a bound method value for the given method and its receiver, in a new object on the290    /// heap. The virtual machine calls it on every method read of a list or dictionary. Each method291    /// read makes a new object, so two reads give equal values that are different objects. The call292    /// returns `error.OutOfMemory` when an allocation fails, after freeing what it allocated.293    pub fn createNativeMethod(self: *Heap, method_value: value.NativeMethod) std.mem.Allocator.Error!value.Value {294        const method = try self.allocator.create(value.NativeMethod);295        errdefer self.allocator.destroy(method);296        method.* = method_value;297        try self.methods.append(self.allocator, method);298        return .{ .method = method };299    }300301    /// Returns, for the given dictionary, a view of the given kind: keys, values or items.302    /// `keys()`, `values()` and `items()` make their views with it. The view borrows the dictionary303    /// and shows every later change to it. The call returns `error.OutOfMemory` when an allocation304    /// fails, after freeing what it allocated.305    pub fn createDictView(self: *Heap, dict: *value.Dict, kind: value.DictViewKind) std.mem.Allocator.Error!value.Value {306        const view = try self.allocator.create(value.DictView);307        errdefer self.allocator.destroy(view);308        view.* = .{309            .dict = dict,310            .kind = kind,311        };312        try self.views.append(self.allocator, view);313        return .{ .view = view };314    }315};316317test "heap owns list objects" {318    var heap = Heap.init(std.testing.allocator);319    defer heap.deinit();320321    const first = try heap.createList(&.{ .{ .integer = 1 }, .{ .integer = 2 } });322    try std.testing.expect(first == .list);323    try std.testing.expectEqual(@as(usize, 2), first.list.items.len);324    try std.testing.expectEqual(value.Value{ .integer = 2 }, first.list.items[1]);325}326327test "heap owns tuple objects" {328    var heap = Heap.init(std.testing.allocator);329    defer heap.deinit();330331    const first = try heap.createTuple(&.{ .{ .integer = 1 }, .{ .integer = 2 } });332    try std.testing.expect(first == .tuple);333    try std.testing.expectEqual(@as(usize, 2), first.tuple.items.len);334    try std.testing.expectEqual(value.Value{ .integer = 2 }, first.tuple.items[1]);335}336337test "heap owns range objects" {338    var heap = Heap.init(std.testing.allocator);339    defer heap.deinit();340341    const first = try heap.createRange(0, 5, 2, 3);342    try std.testing.expect(first == .range);343    try std.testing.expectEqual(@as(i128, 0), first.range.start);344    try std.testing.expectEqual(@as(i128, 5), first.range.stop);345    try std.testing.expectEqual(@as(i128, 2), first.range.step);346    try std.testing.expectEqual(@as(usize, 3), first.range.length);347}348349test "heap owns string objects" {350    var heap = Heap.init(std.testing.allocator);351    defer heap.deinit();352353    const first = try heap.createString("abc");354    try std.testing.expect(first == .string);355    try std.testing.expectEqualStrings("abc", first.string);356}357358test "heap owns list iterators" {359    var heap = Heap.init(std.testing.allocator);360    defer heap.deinit();361362    const list = try heap.createList(&.{.{ .integer = 1 }});363    const iterator = try heap.createListIterator(list.list);364    try std.testing.expect(iterator == .iterator);365    try std.testing.expect(iterator.iterator.* == .list);366    try std.testing.expectEqual(list.list, iterator.iterator.list.list);367    try std.testing.expectEqual(@as(usize, 0), iterator.iterator.list.index);368    try std.testing.expect(!iterator.iterator.list.reverse);369}370371test "heap owns native methods" {372    var heap = Heap.init(std.testing.allocator);373    defer heap.deinit();374375    const list = try heap.createList(&.{});376    const method = try heap.createNativeMethod(.{ .list_append = list.list });377    try std.testing.expect(method == .method);378    try std.testing.expect(method.method.* == .list_append);379    try std.testing.expect(method.method.list_append == list.list);380}381382test "heap owns dictionary views" {383    var heap = Heap.init(std.testing.allocator);384    defer heap.deinit();385386    const dict = try heap.createDict(&.{});387    const view = try heap.createDictView(dict.dict, .keys);388    try std.testing.expect(view == .view);389    try std.testing.expectEqual(dict.dict, view.view.dict);390    try std.testing.expectEqual(value.DictViewKind.keys, view.view.kind);391}392393test "heap owns dictionary view iterators" {394    var heap = Heap.init(std.testing.allocator);395    defer heap.deinit();396397    const dict = try heap.createDict(&.{});398    const view = try heap.createDictView(dict.dict, .items);399    const iterator = try heap.createDictViewIterator(view.view);400    try std.testing.expect(iterator == .iterator);401    try std.testing.expect(iterator.iterator.* == .view);402    try std.testing.expectEqual(view.view, iterator.iterator.view.view);403    try std.testing.expectEqual(@as(usize, 0), iterator.iterator.view.index);404    try std.testing.expect(!iterator.iterator.view.reverse);405}406407test "heap owns enumerate iterators" {408    var heap = Heap.init(std.testing.allocator);409    defer heap.deinit();410411    const list = try heap.createList(&.{.{ .integer = 1 }});412    const child = try heap.createListIterator(list.list);413    const iterator = try heap.createEnumerateIterator(child.iterator, 4);414    try std.testing.expect(iterator == .iterator);415    try std.testing.expect(iterator.iterator.* == .enumerate);416    try std.testing.expectEqual(child.iterator, iterator.iterator.enumerate.iterator);417    try std.testing.expectEqual(@as(i128, 4), iterator.iterator.enumerate.index);418    try std.testing.expect(!iterator.iterator.enumerate.overflowed);419}420421test "heap owns tuple iterators" {422    var heap = Heap.init(std.testing.allocator);423    defer heap.deinit();424425    const tuple = try heap.createTuple(&.{.{ .integer = 1 }});426    const iterator = try heap.createTupleIterator(tuple.tuple);427    try std.testing.expect(iterator == .iterator);428    try std.testing.expect(iterator.iterator.* == .tuple);429    try std.testing.expectEqual(tuple.tuple, iterator.iterator.tuple.tuple);430    try std.testing.expectEqual(@as(usize, 0), iterator.iterator.tuple.index);431    try std.testing.expect(!iterator.iterator.tuple.reverse);432}433434test "heap owns range iterators" {435    var heap = Heap.init(std.testing.allocator);436    defer heap.deinit();437438    const range = try heap.createRange(1, 5, 2, 2);439    const iterator = try heap.createRangeIterator(range.range);440    try std.testing.expect(iterator == .iterator);441    try std.testing.expect(iterator.iterator.* == .range);442    try std.testing.expectEqual(range.range, iterator.iterator.range.range);443    try std.testing.expectEqual(@as(usize, 0), iterator.iterator.range.index);444    try std.testing.expectEqual(@as(i128, 1), iterator.iterator.range.next);445    try std.testing.expect(!iterator.iterator.range.reverse);446}447448test "heap owns string iterators" {449    var heap = Heap.init(std.testing.allocator);450    defer heap.deinit();451452    const iterator = try heap.createStringIterator("abc");453    try std.testing.expect(iterator == .iterator);454    try std.testing.expect(iterator.iterator.* == .string);455    try std.testing.expectEqualStrings("abc", iterator.iterator.string.value);456    try std.testing.expectEqual(@as(usize, 0), iterator.iterator.string.index);457    try std.testing.expect(!iterator.iterator.string.reverse);458}459460test "heap owns reverse iterators" {461    var heap = Heap.init(std.testing.allocator);462    defer heap.deinit();463464    const list = try heap.createList(&.{.{ .integer = 1 }});465    const list_iterator = try heap.createListReverseIterator(list.list);466    try std.testing.expect(list_iterator.iterator.* == .list);467    try std.testing.expect(list_iterator.iterator.list.reverse);468469    const dict = try heap.createDict(&.{});470    const dict_iterator = try heap.createDictReverseIterator(dict.dict);471    try std.testing.expect(dict_iterator.iterator.* == .dict);472    try std.testing.expect(dict_iterator.iterator.dict.reverse);473474    const view = try heap.createDictView(dict.dict, .keys);475    const view_iterator = try heap.createDictViewReverseIterator(view.view);476    try std.testing.expect(view_iterator.iterator.* == .view);477    try std.testing.expect(view_iterator.iterator.view.reverse);478479    const tuple = try heap.createTuple(&.{.{ .integer = 1 }});480    const tuple_iterator = try heap.createTupleReverseIterator(tuple.tuple);481    try std.testing.expect(tuple_iterator.iterator.* == .tuple);482    try std.testing.expect(tuple_iterator.iterator.tuple.reverse);483484    const range = try heap.createRange(1, 5, 2, 2);485    const range_iterator = try heap.createRangeReverseIterator(range.range);486    try std.testing.expect(range_iterator.iterator.* == .range);487    try std.testing.expect(range_iterator.iterator.range.reverse);488489    const string_iterator = try heap.createStringReverseIterator("abc");490    try std.testing.expect(string_iterator.iterator.* == .string);491    try std.testing.expect(string_iterator.iterator.string.reverse);492    try std.testing.expectEqual(@as(usize, 3), string_iterator.iterator.string.index);493}

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