lib/python/src/object/heap.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
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's
3 //! values point at each other freely, and a list can hold itself. Every object has to be freed
4 //! 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, so
7 //! 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 at
10 //! once. Every object lives until the heap is freed, so a run's memory grows with each object it
11 //! 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, a
13 //! 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 stay
15 //! valid until `Result.deinit`.
16 const std = @import("std");
17 const value = @import("value.zig");
18
19 /// The allocator and, for each kind of object, one list holding every object the virtual machine
20 /// created. The virtual machine creates every object through a heap, and `execute` hands it to the
21 /// caller inside `Result`. A heap is made with `init` and freed with `deinit`, which frees every
22 /// object at once. Nothing is freed before `deinit`.
23 pub 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 source
35 /// 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 that
38 /// 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,
44
45 /// Returns an empty heap that allocates from the given allocator. `Vm.init` makes the machine's
46 /// heap with it, and `Vm.takeHeap` makes the empty heap it leaves behind. The call allocates
47 /// nothing, so it cannot fail.
48 pub fn init(allocator: std.mem.Allocator) Heap {
49 return .{ .allocator = allocator };
50 }
51
52 /// 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 points
54 /// 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 }
93
94 /// 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 are
97 /// shared. The call returns `error.OutOfMemory` when an allocation fails, after freeing what it
98 /// 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 }
108
109 /// Returns a tuple value that holds a copy of the given items. The virtual machine makes every
110 /// new tuple with it, for tuple displays, `tuple()`, joins, repeats, slices and the pairs that
111 /// dictionaries and `enumerate` yield. The heap owns the tuple and its array, which has exactly
112 /// 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 it
114 /// 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 }
124
125 /// Returns a dictionary value that holds the given entries in order. The virtual machine makes
126 /// every new dictionary with it, for displays, `dict()` and `copy()`. A repeated key keeps its
127 /// first position and takes the later value. The call reserves room for every entry before it
128 /// inserts the first. Every key has to be hashable, and the insertion asserts it. The call
129 /// returns `error.OutOfMemory` when an allocation fails or when there are more entries than a
130 /// 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 }
141
142 /// Returns a range value with the given start, stop, step and element count. `range()` and
143 /// range slices make each new range with it. The call stores the count as given without
144 /// checking it against the other three, so the caller computes it. The call returns
145 /// `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 }
158
159 /// Returns a string value that holds a copy of the given bytes. The virtual machine makes every
160 /// string it builds with it, for joins, repeats and slices with a step other than 1. The heap
161 /// owns the copy. The call returns `error.OutOfMemory` when an allocation fails, after freeing
162 /// 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 }
169
170 /// Returns an iterator that walks the list from its first item. `iter`, `for` loops and the
171 /// builtins that consume a list start their walk with it. The iterator borrows the list and
172 /// reads its length at each step, so items appended during the walk are visited. The call
173 /// 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 }
177
178 /// Returns an iterator that walks the list from its last item to its first. `reversed` starts
179 /// its walk of a list with it. The iterator borrows the list. The call returns
180 /// `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 }
184
185 /// Returns an iterator over the dictionary's keys, in insertion order. `iter`, `for` loops and
186 /// `list()` start their walk of a dictionary with it. The iterator borrows the dictionary. The
187 /// 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 }
191
192 /// 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. The
194 /// 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 }
198
199 /// Returns an iterator that pairs each item of the given iterator with a counter that starts at
200 /// `start`, as a two-item tuple. `enumerate` wraps the iterator of its argument with it. The
201 /// 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 }
209
210 /// Returns an iterator over a dictionary view, in insertion order: keys, values, or key and
211 /// value tuples, as the view's kind says. `iter`, `for` loops and the consuming builtins start
212 /// their walk of a dictionary view with it. The iterator borrows the view. The call returns
213 /// `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 }
217
218 /// 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. The
220 /// 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 }
224
225 /// Returns an iterator that walks the tuple from its first item. `iter`, `for` loops and the
226 /// consuming builtins start their walk of a tuple with it. The iterator borrows the tuple. The
227 /// 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 }
231
232 /// Returns an iterator that walks the tuple from its last item to its first. `reversed` starts
233 /// its walk of a tuple with it. The iterator borrows the tuple. The call returns
234 /// `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 }
238
239 /// Returns an iterator that yields the range's elements from its start. `iter`, `for` loops and
240 /// 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 }
248
249 /// 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 allocation
252 /// 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 }
260
261 /// 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 their
263 /// walk of a string with it. The iterator borrows the bytes. The call returns
264 /// `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 }
268
269 /// Returns an iterator that yields each codepoint of the string from the last to the first, as
270 /// strings pointing into the same bytes. `reversed` starts its walk of a string with it. The
271 /// iterator borrows the bytes and starts its position at their end. The call returns
272 /// `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 }
280
281 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 }
288
289 /// Returns a bound method value for the given method and its receiver, in a new object on the
290 /// heap. The virtual machine calls it on every method read of a list or dictionary. Each method
291 /// read makes a new object, so two reads give equal values that are different objects. The call
292 /// 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 }
300
301 /// 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 dictionary
303 /// and shows every later change to it. The call returns `error.OutOfMemory` when an allocation
304 /// 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 };
316
317 test "heap owns list objects" {
318 var heap = Heap.init(std.testing.allocator);
319 defer heap.deinit();
320
321 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 }
326
327 test "heap owns tuple objects" {
328 var heap = Heap.init(std.testing.allocator);
329 defer heap.deinit();
330
331 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 }
336
337 test "heap owns range objects" {
338 var heap = Heap.init(std.testing.allocator);
339 defer heap.deinit();
340
341 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 }
348
349 test "heap owns string objects" {
350 var heap = Heap.init(std.testing.allocator);
351 defer heap.deinit();
352
353 const first = try heap.createString("abc");
354 try std.testing.expect(first == .string);
355 try std.testing.expectEqualStrings("abc", first.string);
356 }
357
358 test "heap owns list iterators" {
359 var heap = Heap.init(std.testing.allocator);
360 defer heap.deinit();
361
362 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 }
370
371 test "heap owns native methods" {
372 var heap = Heap.init(std.testing.allocator);
373 defer heap.deinit();
374
375 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 }
381
382 test "heap owns dictionary views" {
383 var heap = Heap.init(std.testing.allocator);
384 defer heap.deinit();
385
386 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 }
392
393 test "heap owns dictionary view iterators" {
394 var heap = Heap.init(std.testing.allocator);
395 defer heap.deinit();
396
397 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 }
406
407 test "heap owns enumerate iterators" {
408 var heap = Heap.init(std.testing.allocator);
409 defer heap.deinit();
410
411 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 }
420
421 test "heap owns tuple iterators" {
422 var heap = Heap.init(std.testing.allocator);
423 defer heap.deinit();
424
425 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 }
433
434 test "heap owns range iterators" {
435 var heap = Heap.init(std.testing.allocator);
436 defer heap.deinit();
437
438 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 }
447
448 test "heap owns string iterators" {
449 var heap = Heap.init(std.testing.allocator);
450 defer heap.deinit();
451
452 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 }
459
460 test "heap owns reverse iterators" {
461 var heap = Heap.init(std.testing.allocator);
462 defer heap.deinit();
463
464 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);
468
469 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);
473
474 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);
478
479 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);
483
484 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);
488
489 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 }