bernsteinbear.com
this repo has no description
1// Copyright (c) Facebook, Inc. and its affiliates. (http://www.facebook.com)
2#include "list-builtins.h"
3
4#include "builtins.h"
5#include "frame.h"
6#include "globals.h"
7#include "int-builtins.h"
8#include "objects.h"
9#include "runtime.h"
10#include "slice-builtins.h"
11#include "thread.h"
12#include "tuple-builtins.h"
13#include "type-builtins.h"
14
15namespace py {
16
17void listExtend(Thread* thread, const List& dst, const Tuple& src,
18 word src_length) {
19 if (src_length == 0) {
20 return;
21 }
22
23 word old_length = dst.numItems();
24 word new_length = old_length + src_length;
25 thread->runtime()->listEnsureCapacity(thread, dst, new_length);
26 dst.setNumItems(new_length);
27 MutableTuple::cast(dst.items()).replaceFromWith(old_length, *src, src_length);
28}
29
30void listInsert(Thread* thread, const List& list, const Object& value,
31 word index) {
32 thread->runtime()->listAdd(thread, list, value);
33 word last_index = list.numItems() - 1;
34 if (index < 0) {
35 index = last_index + index;
36 }
37 index = Utils::maximum(word{0}, Utils::minimum(last_index, index));
38 // Shift elements over to the right
39 list.replaceFromWithStartAt(index + 1, *list, last_index - index, index);
40 list.atPut(index, *value);
41}
42
43RawObject listPop(Thread* thread, const List& list, word index) {
44 HandleScope scope(thread);
45 Object popped(&scope, list.at(index));
46 list.atPut(index, NoneType::object());
47 word last_index = list.numItems() - 1;
48 if (index < last_index) {
49 list.replaceFromWithStartAt(index, *list, last_index - index, index + 1);
50 }
51 list.setNumItems(last_index);
52 return *popped;
53}
54
55RawObject listReplicate(Thread* thread, const List& list, word ntimes) {
56 Runtime* runtime = thread->runtime();
57 word len = list.numItems();
58 word result_len = ntimes * len;
59 if (result_len == 0) {
60 return runtime->newList();
61 }
62 HandleScope scope(thread);
63 Tuple list_items(&scope, list.items());
64 MutableTuple items(&scope, runtime->newMutableTuple(result_len));
65 for (word i = 0; i < result_len; i += len) {
66 items.replaceFromWith(i, *list_items, len);
67 }
68 List result(&scope, runtime->newList());
69 result.setItems(*items);
70 result.setNumItems(result_len);
71 return *result;
72}
73
74void listReverse(Thread* thread, const List& list) {
75 if (list.numItems() == 0) {
76 return;
77 }
78 HandleScope scope(thread);
79 Object elt(&scope, NoneType::object());
80 for (word low = 0, high = list.numItems() - 1; low < high; ++low, --high) {
81 elt = list.at(low);
82 list.atPut(low, list.at(high));
83 list.atPut(high, *elt);
84 }
85}
86
87RawObject listSlice(Thread* thread, const List& list, word start, word stop,
88 word step) {
89 Runtime* runtime = thread->runtime();
90 word length = Slice::length(start, stop, step);
91 if (length == 0) {
92 return runtime->newList();
93 }
94
95 HandleScope scope(thread);
96 MutableTuple items(&scope, runtime->newMutableTuple(length));
97 Tuple src(&scope, list.items());
98 for (word i = 0, j = start; i < length; i++, j += step) {
99 items.atPut(i, src.at(j));
100 }
101 List result(&scope, runtime->newList());
102 result.setItems(*items);
103 result.setNumItems(length);
104 return *result;
105}
106
107// TODO(T63900795): Investigate this threshold on a realistic benchmark.
108static const int kListInsertionSortSize = 8;
109
110static RawObject objectLessThan(Thread* thread, const Object& left,
111 const Object& right,
112 const Object& compare_func) {
113 if (left.isSmallInt() && right.isSmallInt()) {
114 return Bool::fromBool(SmallInt::cast(*left).value() <
115 SmallInt::cast(*right).value());
116 }
117 if (left.isStr() && right.isStr()) {
118 return Bool::fromBool(Str::cast(*left).compare(Str::cast(*right)) < 0);
119 }
120 return Interpreter::call2(thread, compare_func, left, right);
121}
122
123static RawObject listInsertionSort(Thread* thread, const MutableTuple& data,
124 const Object& compare_func, word start,
125 word end) {
126 HandleScope scope(thread);
127 Object item_i(&scope, NoneType::object());
128 Object item_j(&scope, NoneType::object());
129 Object compare_result(&scope, NoneType::object());
130 for (word i = start + 1; i < end; i++) {
131 item_i = data.at(i);
132 word j = i - 1;
133 for (; j >= start; j--) {
134 item_j = data.at(j);
135 compare_result = objectLessThan(thread, item_i, item_j, compare_func);
136 if (compare_result.isError()) {
137 return *compare_result;
138 }
139 compare_result = Interpreter::isTrue(thread, *compare_result);
140 if (compare_result.isError()) {
141 return *compare_result;
142 }
143 if (!Bool::cast(*compare_result).value()) {
144 break;
145 }
146 data.atPut(j + 1, *item_j);
147 }
148 data.atPut(j + 1, *item_i);
149 }
150 return NoneType::object();
151}
152
153// Merge 2 sublists, input[left: right], input[right: end] into
154// output[left: end].
155static RawObject listMerge(Thread* thread, const MutableTuple& input,
156 const MutableTuple& output,
157 const Object& compare_func, word left, word right,
158 word end) {
159 HandleScope scope(thread);
160 Object item_i(&scope, NoneType::object());
161 Object item_j(&scope, NoneType::object());
162 Object compare_result(&scope, NoneType::object());
163 word i = left;
164 word j = right;
165 word k = left;
166 while (i < right && j < end) {
167 item_i = input.at(i);
168 item_j = input.at(j);
169 compare_result = objectLessThan(thread, item_j, item_i, compare_func);
170 if (compare_result.isError()) {
171 return *compare_result;
172 }
173 compare_result = Interpreter::isTrue(thread, *compare_result);
174 if (compare_result.isError()) {
175 return *compare_result;
176 }
177 if (*compare_result == Bool::trueObj()) {
178 output.atPut(k++, *item_j);
179 j++;
180 } else {
181 DCHECK(compare_result == Bool::falseObj(), "expected to be false");
182 output.atPut(k++, *item_i);
183 i++;
184 }
185 }
186 for (; i < right; i++) {
187 output.atPut(k++, input.at(i));
188 }
189 for (; j < end; j++) {
190 output.atPut(k++, input.at(j));
191 }
192 DCHECK(k == end, "sublists were not fully copied");
193 return NoneType::object();
194}
195
196RawObject listSort(Thread* thread, const List& list) {
197 return listSortWithCompareMethod(thread, list, ID(_lt));
198}
199
200// This uses an adaptation of merge sort. It sorts sublists of size
201// kListInsertionSortSize or less using insertion sort first. Afterwards, it is
202// using a bottom-up merge sort to increase the sublists' size by power of 2.
203// Also, this function allocates a temporary space to ease merging and swaps
204// `input` and `output` to avoid further allocation.
205// TODO(T39107329): Consider using Timsort for further optimization.
206RawObject listSortWithCompareMethod(Thread* thread, const List& list,
207 SymbolId compare_method) {
208 word num_items = list.numItems();
209 if (num_items == 0) {
210 return NoneType::object();
211 }
212 HandleScope scope(thread);
213 Runtime* runtime = thread->runtime();
214 Object compare_func(&scope, runtime->lookupNameInModule(thread, ID(_builtins),
215 compare_method));
216 if (compare_func.isError()) return *compare_func;
217 MutableTuple input(&scope, list.items());
218 Object compare_result(&scope, NoneType::object());
219 for (word left = 0; left < num_items; left += kListInsertionSortSize) {
220 word right = Utils::minimum(left + kListInsertionSortSize, num_items);
221 compare_result =
222 listInsertionSort(thread, input, compare_func, left, right);
223 if (compare_result.isError()) {
224 return *compare_result;
225 }
226 }
227 if (num_items <= kListInsertionSortSize) {
228 // The input list is small enough to be sorted by insertion sort.
229 return NoneType::object();
230 }
231 MutableTuple output(&scope, runtime->newMutableTuple(input.length()));
232 Object tmp(&scope, NoneType::object());
233 for (word width = kListInsertionSortSize; width < num_items; width *= 2) {
234 for (word left = 0; left < num_items; left += width * 2) {
235 word right = Utils::minimum(num_items, left + width);
236 word end = Utils::minimum(num_items, left + width * 2);
237 compare_result =
238 listMerge(thread, input, output, compare_func, left, right, end);
239 if (compare_result.isError()) {
240 return *compare_result;
241 }
242 }
243 tmp = *output;
244 output = *input;
245 input = MutableTuple::cast(*tmp);
246 }
247 list.setItems(*input);
248 return NoneType::object();
249}
250
251RawObject listIteratorNext(Thread* thread, const ListIterator& iter) {
252 HandleScope scope(thread);
253 word idx = iter.index();
254 List underlying(&scope, iter.iterable());
255 if (idx >= underlying.numItems()) {
256 return Error::outOfBounds();
257 }
258 RawObject item = underlying.at(idx);
259 iter.setIndex(idx + 1);
260 return item;
261}
262
263static const BuiltinAttribute kListAttributes[] = {
264 {ID(_list__items), RawList::kItemsOffset, AttributeFlags::kHidden},
265 {ID(_list__num_items), RawList::kNumItemsOffset, AttributeFlags::kHidden},
266};
267
268static const BuiltinAttribute kListIteratorAttributes[] = {
269 {ID(_list_iterator__iterable), RawListIterator::kIterableOffset,
270 AttributeFlags::kHidden},
271 {ID(_list_iterator__index), RawListIterator::kIndexOffset,
272 AttributeFlags::kHidden},
273};
274
275void initializeListTypes(Thread* thread) {
276 addBuiltinType(thread, ID(list), LayoutId::kList,
277 /*superclass_id=*/LayoutId::kObject, kListAttributes,
278 List::kSize, /*basetype=*/true);
279
280 addBuiltinType(thread, ID(list_iterator), LayoutId::kListIterator,
281 /*superclass_id=*/LayoutId::kObject, kListIteratorAttributes,
282 ListIterator::kSize, /*basetype=*/false);
283}
284
285RawObject METH(list, __new__)(Thread* thread, Arguments args) {
286 HandleScope scope(thread);
287 Object type_obj(&scope, args.get(0));
288 Runtime* runtime = thread->runtime();
289 if (!runtime->isInstanceOfType(*type_obj)) {
290 return thread->raiseWithFmt(LayoutId::kTypeError, "not a type object");
291 }
292 Type type(&scope, *type_obj);
293 if (type.builtinBase() != LayoutId::kList) {
294 return thread->raiseWithFmt(LayoutId::kTypeError, "not a subtype of list");
295 }
296 Layout layout(&scope, type.instanceLayout());
297 List result(&scope, runtime->newInstance(layout));
298 result.setNumItems(0);
299 result.setItems(runtime->emptyTuple());
300 return *result;
301}
302
303RawObject METH(list, __add__)(Thread* thread, Arguments args) {
304 HandleScope scope(thread);
305 Object self_obj(&scope, args.get(0));
306 Runtime* runtime = thread->runtime();
307 if (!runtime->isInstanceOfList(*self_obj)) {
308 return thread->raiseRequiresType(self_obj, ID(list));
309 }
310 Object other_obj(&scope, args.get(1));
311 if (!runtime->isInstanceOfList(*other_obj)) {
312 return thread->raiseWithFmt(LayoutId::kTypeError,
313 "can only concatenate list to list");
314 }
315 List self(&scope, *self_obj);
316 List other(&scope, *other_obj);
317 List new_list(&scope, runtime->newList());
318 word self_len = self.numItems();
319 word other_len = other.numItems();
320 runtime->listEnsureCapacity(thread, new_list, self_len + other_len);
321 Tuple self_items(&scope, self.items());
322 Tuple other_items(&scope, other.items());
323 listExtend(thread, new_list, self_items, self_len);
324 listExtend(thread, new_list, other_items, other_len);
325 return *new_list;
326}
327
328RawObject listContains(Thread* thread, const List& list, const Object& key) {
329 for (word i = 0, num_items = list.numItems(); i < num_items; ++i) {
330 RawObject result = Runtime::objectEquals(thread, *key, list.at(i));
331 if (result == Bool::trueObj()) {
332 return Bool::trueObj();
333 }
334 if (result.isErrorException()) return result;
335 }
336 return Bool::falseObj();
337}
338
339RawObject METH(list, __contains__)(Thread* thread, Arguments args) {
340 HandleScope scope(thread);
341 Object self_obj(&scope, args.get(0));
342 if (!thread->runtime()->isInstanceOfList(*self_obj)) {
343 return thread->raiseRequiresType(self_obj, ID(list));
344 }
345 List self(&scope, *self_obj);
346 Object key(&scope, args.get(1));
347 return listContains(thread, self, key);
348}
349
350RawObject METH(list, __eq__)(Thread* thread, Arguments args) {
351 HandleScope scope(thread);
352 Runtime* runtime = thread->runtime();
353 Object self_obj(&scope, args.get(0));
354 if (!runtime->isInstanceOfList(*self_obj)) {
355 return thread->raiseRequiresType(self_obj, ID(list));
356 }
357 Object other_obj(&scope, args.get(1));
358 if (!runtime->isInstanceOfList(*other_obj)) {
359 return NotImplementedType::object();
360 }
361 if (self_obj == other_obj) {
362 return Bool::trueObj();
363 }
364 List self(&scope, *self_obj);
365 List other(&scope, *other_obj);
366 word num_items = self.numItems();
367 if (num_items != other.numItems()) {
368 return Bool::falseObj();
369 }
370 Tuple self_items(&scope, self.items());
371 Tuple other_items(&scope, other.items());
372 for (word i = 0; i < num_items; i++) {
373 RawObject self_item = self_items.at(i);
374 RawObject other_item = other_items.at(i);
375 if (self_item != other_item) {
376 RawObject equals = Runtime::objectEquals(thread, self_item, other_item);
377 if (equals != Bool::trueObj()) {
378 return equals;
379 }
380 }
381 }
382 return Bool::trueObj();
383}
384
385RawObject METH(list, clear)(Thread* thread, Arguments args) {
386 HandleScope scope(thread);
387 Object self(&scope, args.get(0));
388 if (!thread->runtime()->isInstanceOfList(*self)) {
389 return thread->raiseRequiresType(self, ID(list));
390 }
391 List list(&scope, *self);
392 list.clearFrom(0);
393 return NoneType::object();
394}
395
396RawObject METH(list, __len__)(Thread* thread, Arguments args) {
397 HandleScope scope(thread);
398 Object self(&scope, args.get(0));
399 if (!thread->runtime()->isInstanceOfList(*self)) {
400 return thread->raiseRequiresType(self, ID(list));
401 }
402 List list(&scope, *self);
403 return SmallInt::fromWord(list.numItems());
404}
405
406RawObject METH(list, insert)(Thread* thread, Arguments args) {
407 HandleScope scope(thread);
408 Object self(&scope, args.get(0));
409 if (!thread->runtime()->isInstanceOfList(*self)) {
410 return thread->raiseRequiresType(self, ID(list));
411 }
412 List list(&scope, *self);
413 Object index_obj(&scope, args.get(1));
414 index_obj = intFromIndex(thread, index_obj);
415 if (index_obj.isError()) return *index_obj;
416 Int index_int(&scope, intUnderlying(*index_obj));
417 if (index_int.isLargeInt()) {
418 return thread->raiseWithFmt(LayoutId::kOverflowError,
419 "Python int too large to convert to C ssize_t");
420 }
421 word index = index_int.asWord();
422 Object value(&scope, args.get(2));
423 listInsert(thread, list, value, index);
424 return NoneType::object();
425}
426
427RawObject METH(list, __mul__)(Thread* thread, Arguments args) {
428 RawObject other = args.get(1);
429 HandleScope scope(thread);
430 Object self(&scope, args.get(0));
431 Runtime* runtime = thread->runtime();
432 if (!runtime->isInstanceOfList(*self)) {
433 return thread->raiseRequiresType(self, ID(list));
434 }
435 if (other.isSmallInt()) {
436 word ntimes = SmallInt::cast(other).value();
437 if (ntimes <= 0) return runtime->newList();
438 List list(&scope, *self);
439 return listReplicate(thread, list, ntimes);
440 }
441 return thread->raiseWithFmt(LayoutId::kTypeError,
442 "can't multiply list by non-int");
443}
444
445RawObject METH(list, pop)(Thread* thread, Arguments args) {
446 if (!args.get(1).isUnbound() && !args.get(1).isSmallInt()) {
447 return thread->raiseWithFmt(
448 LayoutId::kTypeError,
449 "index object cannot be interpreted as an integer");
450 }
451
452 HandleScope scope(thread);
453 Object self(&scope, args.get(0));
454 if (!thread->runtime()->isInstanceOfList(*self)) {
455 return thread->raiseRequiresType(self, ID(list));
456 }
457 List list(&scope, *self);
458 word length = list.numItems();
459 if (length == 0) {
460 return thread->raiseWithFmt(LayoutId::kIndexError, "pop from empty list");
461 }
462 word index = length - 1;
463 if (!args.get(1).isUnbound()) {
464 index = SmallInt::cast(args.get(1)).value();
465 if (index < 0) index += length;
466 }
467 if (index < 0 || index >= length) {
468 return thread->raiseWithFmt(LayoutId::kIndexError,
469 "pop index out of range");
470 }
471
472 return listPop(thread, list, index);
473}
474
475RawObject METH(list, remove)(Thread* thread, Arguments args) {
476 HandleScope scope(thread);
477 Object self_obj(&scope, args.get(0));
478 if (!thread->runtime()->isInstanceOfList(*self_obj)) {
479 return thread->raiseRequiresType(self_obj, ID(list));
480 }
481 Object value(&scope, args.get(1));
482 List self(&scope, *self_obj);
483 Object item(&scope, NoneType::object());
484 Object comp_result(&scope, NoneType::object());
485 Object found(&scope, NoneType::object());
486 for (word i = 0, num_items = self.numItems(); i < num_items; ++i) {
487 item = self.at(i);
488 if (*value == *item) {
489 listPop(thread, self, i);
490 return NoneType::object();
491 }
492 comp_result =
493 Interpreter::compareOperation(thread, CompareOp::EQ, item, value);
494 if (comp_result.isError()) return *comp_result;
495 found = Interpreter::isTrue(thread, *comp_result);
496 if (found.isError()) return *found;
497 if (found == Bool::trueObj()) {
498 listPop(thread, self, i);
499 return NoneType::object();
500 }
501 }
502 return thread->raiseWithFmt(LayoutId::kValueError,
503 "list.remove(x) x not in list");
504}
505
506RawObject METH(list, __imul__)(Thread* thread, Arguments args) {
507 RawObject other = args.get(1);
508 HandleScope scope(thread);
509 Object self(&scope, args.get(0));
510 Runtime* runtime = thread->runtime();
511 if (!runtime->isInstanceOfList(*self)) {
512 return thread->raiseRequiresType(self, ID(list));
513 }
514 Object count_index(&scope, args.get(1));
515 Object count_obj(&scope, intFromIndex(thread, count_index));
516 if (count_obj.isError()) return *count_obj;
517 word count = intUnderlying(*count_obj).asWordSaturated();
518 if (!SmallInt::isValid(count)) {
519 return thread->raiseWithFmt(LayoutId::kOverflowError,
520 "cannot fit '%T' into an index-sized integer",
521 &count_index);
522 }
523 word ntimes = SmallInt::cast(other).value();
524 if (ntimes == 1) {
525 return *self;
526 }
527 List list(&scope, *self);
528 if (ntimes <= 0) {
529 list.clearFrom(0);
530 return *list;
531 }
532 word new_length;
533 word len = list.numItems();
534 if (__builtin_mul_overflow(len, ntimes, &new_length) ||
535 !SmallInt::isValid(new_length)) {
536 return thread->raiseMemoryError();
537 }
538 if (new_length == len) {
539 return *list;
540 }
541 runtime->listEnsureCapacity(thread, list, new_length);
542 list.setNumItems(new_length);
543 for (word i = 0; i < ntimes; i++) {
544 list.replaceFromWith(i * len, *list, len);
545 }
546 return *list;
547}
548
549RawObject METH(list, __iter__)(Thread* thread, Arguments args) {
550 HandleScope scope(thread);
551 Object self(&scope, args.get(0));
552 if (!thread->runtime()->isInstanceOfList(*self)) {
553 return thread->raiseRequiresType(self, ID(list));
554 }
555 return thread->runtime()->newListIterator(self);
556}
557
558RawObject METH(list_iterator, __iter__)(Thread* thread, Arguments args) {
559 HandleScope scope(thread);
560 Object self(&scope, args.get(0));
561 if (!self.isListIterator()) {
562 return thread->raiseRequiresType(self, ID(list_iterator));
563 }
564 return *self;
565}
566
567RawObject METH(list_iterator, __next__)(Thread* thread, Arguments args) {
568 HandleScope scope(thread);
569 Object self_obj(&scope, args.get(0));
570 if (!self_obj.isListIterator()) {
571 return thread->raiseRequiresType(self_obj, ID(list_iterator));
572 }
573 ListIterator self(&scope, *self_obj);
574 Object value(&scope, listIteratorNext(thread, self));
575 if (value.isError()) {
576 return thread->raise(LayoutId::kStopIteration, NoneType::object());
577 }
578 return *value;
579}
580
581RawObject METH(list_iterator, __length_hint__)(Thread* thread, Arguments args) {
582 HandleScope scope(thread);
583 Object self(&scope, args.get(0));
584 if (!self.isListIterator()) {
585 return thread->raiseRequiresType(self, ID(list_iterator));
586 }
587 ListIterator list_iterator(&scope, *self);
588 List list(&scope, list_iterator.iterable());
589 return SmallInt::fromWord(list.numItems() - list_iterator.index());
590}
591
592} // namespace py