bernsteinbear.com
this repo has no description
1// Copyright (c) Facebook, Inc. and its affiliates. (http://www.facebook.com)
2#include "under-collections-module.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
17static const BuiltinAttribute kDequeAttributes[] = {
18 {ID(_deque__items), RawDeque::kItemsOffset, AttributeFlags::kHidden},
19 {ID(_deque__left), RawDeque::kLeftOffset, AttributeFlags::kHidden},
20 {ID(_deque__num_items), RawDeque::kNumItemsOffset, AttributeFlags::kHidden},
21 {ID(maxlen), RawDeque::kMaxlenOffset, AttributeFlags::kReadOnly},
22 {ID(_deque__state), RawDeque::kStateOffset, AttributeFlags::kHidden},
23};
24
25static const BuiltinAttribute kDequeIteratorAttributes[] = {
26 {ID(_deque_iterator__iterable), RawDequeIterator::kIterableOffset,
27 AttributeFlags::kHidden},
28 {ID(_deque_iterator__index), RawDequeIterator::kIndexOffset,
29 AttributeFlags::kHidden},
30 {ID(_deque_iterator__state), RawDequeIterator::kStateOffset,
31 AttributeFlags::kHidden},
32};
33
34static const BuiltinAttribute kDequeReverseIteratorAttributes[] = {
35 {ID(_deque_reverse_iterator__iterable),
36 RawDequeReverseIterator::kIterableOffset, AttributeFlags::kHidden},
37 {ID(_deque_reverse_iterator__index), RawDequeReverseIterator::kIndexOffset,
38 AttributeFlags::kHidden},
39 {ID(_deque_reverse_iterator__state), RawDequeReverseIterator::kStateOffset,
40 AttributeFlags::kHidden},
41};
42
43void initializeUnderCollectionsTypes(Thread* thread) {
44 addBuiltinType(thread, ID(deque), LayoutId::kDeque,
45 /*superclass_id=*/LayoutId::kObject, kDequeAttributes,
46 Deque::kSize, /*basetype=*/true);
47 addBuiltinType(thread, ID(_deque_iterator), LayoutId::kDequeIterator,
48 /*superclass_id=*/LayoutId::kObject, kDequeIteratorAttributes,
49 DequeIterator::kSize, /*basetype=*/false);
50 addBuiltinType(
51 thread, ID(_deque_reverse_iterator), LayoutId::kDequeReverseIterator,
52 /*superclass_id=*/LayoutId::kObject, kDequeReverseIteratorAttributes,
53 DequeReverseIterator::kSize, /*basetype=*/false);
54}
55
56static word dequeIndex(const Deque& deque, word index) {
57 word num_items = deque.numItems();
58 if (index >= num_items || index < -num_items) {
59 return -1;
60 }
61 if (index < 0) {
62 index += num_items;
63 }
64 word deque_index = deque.left() + index;
65 word capacity = deque.capacity();
66 if (deque_index >= capacity) {
67 deque_index -= capacity;
68 }
69 return deque_index;
70}
71
72RawObject FUNC(_collections, _deque_delitem)(Thread* thread, Arguments args) {
73 HandleScope scope(thread);
74 Object self_obj(&scope, args.get(0));
75 Runtime* runtime = thread->runtime();
76 if (!runtime->isInstanceOfDeque(*self_obj)) {
77 return thread->raiseRequiresType(self_obj, ID(deque));
78 }
79 Object key(&scope, args.get(1));
80 if (!runtime->isInstanceOfInt(*key)) {
81 return Unbound::object();
82 }
83
84 word index = intUnderlying(*key).asWordSaturated();
85 if (!SmallInt::isValid(index)) {
86 return thread->raiseWithFmt(LayoutId::kIndexError,
87 "cannot fit '%T' into an index-sized integer",
88 &key);
89 }
90 Deque deque(&scope, *self_obj);
91 word deque_index = dequeIndex(deque, index);
92 if (deque_index == -1) {
93 return thread->raiseWithFmt(LayoutId::kIndexError,
94 "deque index out of range");
95 }
96
97 MutableTuple items(&scope, deque.items());
98 word left = deque.left();
99 word num_items = deque.numItems();
100 if (deque_index < left) {
101 // shift (deque_index, right] one to the left
102 word right = left + num_items - items.length() - 1;
103 items.replaceFromWithStartAt(deque_index, *items, right - deque_index,
104 deque_index + 1);
105 items.atPut(right, NoneType::object());
106 } else {
107 // shift [left, deque_index) one to the right
108 items.replaceFromWithStartAt(left + 1, *items, deque_index - left, left);
109 items.atPut(left, NoneType::object());
110 word new_left = left + 1;
111 deque.setLeft(new_left < items.length() ? new_left : 0);
112 }
113 deque.setNumItems(num_items - 1);
114 return NoneType::object();
115}
116
117RawObject FUNC(_collections, _deque_getitem)(Thread* thread, Arguments args) {
118 HandleScope scope(thread);
119 Object self_obj(&scope, args.get(0));
120 Runtime* runtime = thread->runtime();
121 if (!runtime->isInstanceOfDeque(*self_obj)) {
122 return thread->raiseRequiresType(self_obj, ID(deque));
123 }
124 Object key(&scope, args.get(1));
125 if (!runtime->isInstanceOfInt(*key)) {
126 return Unbound::object();
127 }
128
129 word index = intUnderlying(*key).asWordSaturated();
130 if (!SmallInt::isValid(index)) {
131 return thread->raiseWithFmt(LayoutId::kIndexError,
132 "cannot fit '%T' into an index-sized integer",
133 &key);
134 }
135 Deque deque(&scope, *self_obj);
136 word deque_index = dequeIndex(deque, index);
137 if (deque_index == -1) {
138 return thread->raiseWithFmt(LayoutId::kIndexError,
139 "deque index out of range");
140 }
141 return deque.at(deque_index);
142}
143
144RawObject FUNC(_collections, _deque_set_maxlen)(Thread* thread,
145 Arguments args) {
146 HandleScope scope(thread);
147 Deque deque(&scope, args.get(0));
148 Object maxlen_obj(&scope, args.get(1));
149 if (maxlen_obj.isNoneType()) {
150 deque.setMaxlen(NoneType::object());
151 return NoneType::object();
152 }
153 if (!thread->runtime()->isInstanceOfInt(*maxlen_obj)) {
154 return thread->raiseWithFmt(LayoutId::kTypeError, "an integer is required");
155 }
156 word maxlen = intUnderlying(*maxlen_obj).asWordSaturated();
157 if (!SmallInt::isValid(maxlen)) {
158 return thread->raiseWithFmt(LayoutId::kOverflowError,
159 "Python int too large to convert to C ssize_t");
160 }
161 if (maxlen < 0) {
162 return thread->raiseWithFmt(LayoutId::kValueError,
163 "maxlen must be non-negative");
164 }
165 deque.setMaxlen(SmallInt::fromWord(maxlen));
166 return NoneType::object();
167}
168
169RawObject FUNC(_collections, _deque_setitem)(Thread* thread, Arguments args) {
170 HandleScope scope(thread);
171 Object self_obj(&scope, args.get(0));
172 Runtime* runtime = thread->runtime();
173 if (!runtime->isInstanceOfDeque(*self_obj)) {
174 return thread->raiseRequiresType(self_obj, ID(deque));
175 }
176 Object key(&scope, args.get(1));
177 if (!runtime->isInstanceOfInt(*key)) {
178 return Unbound::object();
179 }
180
181 word index = intUnderlying(*key).asWordSaturated();
182 if (!SmallInt::isValid(index)) {
183 return thread->raiseWithFmt(LayoutId::kIndexError,
184 "cannot fit '%T' into an index-sized integer",
185 &key);
186 }
187 Deque deque(&scope, *self_obj);
188 word deque_index = dequeIndex(deque, index);
189 if (deque_index == -1) {
190 return thread->raiseWithFmt(LayoutId::kIndexError,
191 "deque index out of range");
192 }
193 deque.atPut(deque_index, args.get(2));
194 return NoneType::object();
195}
196
197RawObject METH(_deque_iterator, __length_hint__)(Thread* thread,
198 Arguments args) {
199 HandleScope scope(thread);
200 Object self_obj(&scope, args.get(0));
201 if (!self_obj.isDequeIterator()) {
202 return thread->raiseRequiresType(self_obj, ID(_deque_iterator));
203 }
204 DequeIterator self(&scope, *self_obj);
205 Deque deque(&scope, self.iterable());
206 return SmallInt::fromWord(deque.numItems() - self.index());
207}
208
209RawObject METH(_deque_iterator, __new__)(Thread* thread, Arguments args) {
210 HandleScope scope(thread);
211 Object cls(&scope, args.get(0));
212 Runtime* runtime = thread->runtime();
213 if (!runtime->isInstanceOfType(*cls)) {
214 return thread->raiseRequiresType(cls, ID(type));
215 }
216 if (cls != runtime->typeAt(LayoutId::kDequeIterator)) {
217 Type type(&scope, *cls);
218 Str name(&scope, type.name());
219 return thread->raiseWithFmt(
220 LayoutId::kTypeError,
221 "_collections._deque_iterator.__new__(%S): "
222 "%S is not a subtype of _collections._deque_iterator",
223 &name, &name);
224 }
225
226 Object iterable(&scope, args.get(1));
227 if (!runtime->isInstanceOfDeque(*iterable)) {
228 return thread->raiseRequiresType(iterable, ID(deque));
229 }
230 Deque deque(&scope, *iterable);
231
232 Object index_obj(&scope, args.get(2));
233 index_obj = intFromIndex(thread, index_obj);
234 if (index_obj.isErrorException()) {
235 return *index_obj;
236 }
237 Int index_int(&scope, intUnderlying(*index_obj));
238 if (index_int.numDigits() > 1) {
239 return thread->raiseWithFmt(LayoutId::kOverflowError,
240 "Python int too large to convert to C ssize_t");
241 }
242 word index = index_int.asWord();
243 if (index < 0) {
244 index = 0;
245 } else {
246 word length = deque.numItems();
247 if (index > length) {
248 index = length;
249 }
250 }
251 return runtime->newDequeIterator(deque, index);
252}
253
254RawObject METH(_deque_iterator, __next__)(Thread* thread, Arguments args) {
255 HandleScope scope(thread);
256 Object self_obj(&scope, args.get(0));
257 if (!self_obj.isDequeIterator()) {
258 return thread->raiseRequiresType(self_obj, ID(_deque_iterator));
259 }
260
261 DequeIterator self(&scope, *self_obj);
262 Deque deque(&scope, self.iterable());
263 if (deque.state() != self.state()) {
264 return thread->raiseWithFmt(LayoutId::kRuntimeError,
265 "deque mutated during iteration");
266 }
267
268 word index = self.index();
269 word length = deque.numItems();
270 DCHECK_BOUND(index, length);
271 if (index == length) {
272 return thread->raiseStopIteration();
273 }
274
275 self.setIndex(index + 1);
276 index += deque.left();
277 word capacity = deque.capacity();
278 if (index < capacity) {
279 return deque.at(index);
280 }
281 return deque.at(index - capacity);
282}
283
284RawObject METH(_deque_iterator, __reduce__)(Thread* thread, Arguments args) {
285 HandleScope scope(thread);
286 Object self_obj(&scope, args.get(0));
287 if (!self_obj.isDequeIterator()) {
288 return thread->raiseRequiresType(self_obj, ID(_deque_iterator));
289 }
290 Runtime* runtime = thread->runtime();
291 DequeIterator self(&scope, *self_obj);
292 Object type(&scope, runtime->typeAt(LayoutId::kDequeIterator));
293 Object deque(&scope, self.iterable());
294 Object index(&scope, SmallInt::fromWord(self.index()));
295 Object tuple(&scope, runtime->newTupleWith2(deque, index));
296 return runtime->newTupleWith2(type, tuple);
297}
298
299RawObject METH(_deque_reverse_iterator, __length_hint__)(Thread* thread,
300 Arguments args) {
301 HandleScope scope(thread);
302 Object self_obj(&scope, args.get(0));
303 if (!self_obj.isDequeReverseIterator()) {
304 return thread->raiseRequiresType(self_obj, ID(_deque_reverse_iterator));
305 }
306 DequeReverseIterator self(&scope, *self_obj);
307 Deque deque(&scope, self.iterable());
308 return SmallInt::fromWord(deque.numItems() - self.index());
309}
310
311RawObject METH(_deque_reverse_iterator, __new__)(Thread* thread,
312 Arguments args) {
313 HandleScope scope(thread);
314 Object cls(&scope, args.get(0));
315 Runtime* runtime = thread->runtime();
316 if (!runtime->isInstanceOfType(*cls)) {
317 return thread->raiseRequiresType(cls, ID(type));
318 }
319 if (cls != runtime->typeAt(LayoutId::kDequeReverseIterator)) {
320 Type type(&scope, *cls);
321 Str name(&scope, type.name());
322 return thread->raiseWithFmt(
323 LayoutId::kTypeError,
324 "_collections._deque_reverse_iterator.__new__(%S): "
325 "%S is not a subtype of _collections._deque_reverse_iterator",
326 &name, &name);
327 }
328
329 Object iterable(&scope, args.get(1));
330 if (!runtime->isInstanceOfDeque(*iterable)) {
331 return thread->raiseRequiresType(iterable, ID(deque));
332 }
333 Deque deque(&scope, *iterable);
334
335 Object index_obj(&scope, args.get(2));
336 index_obj = intFromIndex(thread, index_obj);
337 if (index_obj.isErrorException()) {
338 return *index_obj;
339 }
340 Int index_int(&scope, intUnderlying(*index_obj));
341 if (index_int.numDigits() > 1) {
342 return thread->raiseWithFmt(LayoutId::kOverflowError,
343 "Python int too large to convert to C ssize_t");
344 }
345 word index = index_int.asWord();
346 if (index < 0) {
347 index = 0;
348 } else {
349 word length = deque.numItems();
350 if (index > length) {
351 index = length;
352 }
353 }
354 return runtime->newDequeReverseIterator(deque, index);
355}
356
357RawObject METH(_deque_reverse_iterator, __next__)(Thread* thread,
358 Arguments args) {
359 HandleScope scope(thread);
360 Object self_obj(&scope, args.get(0));
361 if (!self_obj.isDequeReverseIterator()) {
362 return thread->raiseRequiresType(self_obj, ID(_deque_reverse_iterator));
363 }
364
365 DequeReverseIterator self(&scope, *self_obj);
366 Deque deque(&scope, self.iterable());
367 if (deque.state() != self.state()) {
368 return thread->raiseWithFmt(LayoutId::kRuntimeError,
369 "deque mutated during iteration");
370 }
371
372 word index = self.index();
373 word length = deque.numItems();
374 DCHECK_BOUND(index, length);
375 if (index == length) {
376 return thread->raiseStopIteration();
377 }
378
379 index += 1;
380 self.setIndex(index);
381 index = deque.left() + deque.numItems() - index;
382 word capacity = deque.capacity();
383 if (index < capacity) {
384 return deque.at(index);
385 }
386 return deque.at(index - capacity);
387}
388
389RawObject METH(_deque_reverse_iterator, __reduce__)(Thread* thread,
390 Arguments args) {
391 HandleScope scope(thread);
392 Object self_obj(&scope, args.get(0));
393 if (!self_obj.isDequeIterator()) {
394 return thread->raiseRequiresType(self_obj, ID(_deque_iterator));
395 }
396 Runtime* runtime = thread->runtime();
397 DequeReverseIterator self(&scope, *self_obj);
398 Object type(&scope, runtime->typeAt(LayoutId::kDequeReverseIterator));
399 Object deque(&scope, self.iterable());
400 Object index(&scope, SmallInt::fromWord(self.index()));
401 Object tuple(&scope, runtime->newTupleWith2(deque, index));
402 return runtime->newTupleWith2(type, tuple);
403}
404
405static void dequeEnsureCapacity(Thread* thread, const Deque& deque,
406 word min_capacity) {
407 DCHECK_BOUND(min_capacity, SmallInt::kMaxValue);
408 word curr_capacity = deque.capacity();
409 if (min_capacity <= curr_capacity) return;
410 word new_capacity = Runtime::newCapacity(curr_capacity, min_capacity);
411 RawObject maxlen = deque.maxlen();
412 if (!maxlen.isNoneType()) {
413 new_capacity = Utils::minimum(new_capacity, SmallInt::cast(maxlen).value());
414 }
415
416 HandleScope scope(thread);
417 MutableTuple new_array(&scope,
418 thread->runtime()->newMutableTuple(new_capacity));
419 word num_items = deque.numItems();
420 if (num_items > 0) {
421 Tuple old_array(&scope, deque.items());
422 word left = deque.left();
423 word right = left + num_items;
424 if (right >= curr_capacity) {
425 right -= curr_capacity;
426 }
427 if (right <= left) {
428 word count = curr_capacity - left;
429 new_array.replaceFromWithStartAt(0, *old_array, count, left);
430 new_array.replaceFromWithStartAt(count, *old_array, right, 0);
431 } else {
432 new_array.replaceFromWithStartAt(0, *old_array, num_items, left);
433 }
434 }
435
436 deque.setItems(*new_array);
437 deque.setLeft(0);
438}
439
440static void dequeAppend(Thread* thread, const Deque& deque,
441 const Object& value) {
442 word num_items = deque.numItems();
443 if (deque.maxlen() == SmallInt::fromWord(num_items)) {
444 if (num_items == 0) return;
445 word left = deque.left();
446 word new_left = left + 1;
447 word capacity = deque.capacity();
448 if (new_left == capacity) {
449 new_left = 0;
450 }
451 deque.atPut(left, *value);
452 deque.setLeft(new_left);
453 return;
454 }
455 dequeEnsureCapacity(thread, deque, num_items + 1);
456 word left = deque.left();
457 word capacity = deque.capacity();
458 DCHECK(num_items < capacity, "deque should not be full");
459 // wrap right around to beginning of tuple if end reached
460 word right = left + num_items;
461 if (right >= capacity) {
462 right -= capacity;
463 }
464 deque.setNumItems(num_items + 1);
465 deque.atPut(right, *value);
466}
467
468static void dequeAppendLeft(Thread* thread, const Deque& deque,
469 const Object& value) {
470 word num_items = deque.numItems();
471 if (deque.maxlen() == SmallInt::fromWord(num_items)) {
472 if (num_items == 0) return;
473 word new_left = deque.left() - 1;
474 if (new_left < 0) {
475 new_left += deque.capacity();
476 }
477 deque.atPut(new_left, *value);
478 deque.setLeft(new_left);
479 return;
480 }
481 dequeEnsureCapacity(thread, deque, num_items + 1);
482 word new_left = deque.left();
483 new_left -= 1;
484 if (new_left < 0) {
485 new_left += deque.capacity();
486 }
487 deque.setNumItems(num_items + 1);
488 deque.atPut(new_left, *value);
489 deque.setLeft(new_left);
490}
491
492static RawObject dequePop(Thread* thread, const Deque& deque) {
493 HandleScope scope(thread);
494 word num_items = deque.numItems();
495 DCHECK(num_items != 0, "cannot pop from empty deque");
496 word new_length = num_items - 1;
497 word tail = deque.left() + new_length;
498 word capacity = deque.capacity();
499 if (tail >= capacity) {
500 tail -= capacity;
501 }
502 Object result(&scope, deque.at(tail));
503 deque.atPut(tail, NoneType::object());
504 deque.setNumItems(new_length);
505 return *result;
506}
507
508static RawObject dequePopLeft(Thread* thread, const Deque& deque) {
509 HandleScope scope(thread);
510 word num_items = deque.numItems();
511 DCHECK(num_items != 0, "cannot pop from empty deque");
512 word head = deque.left();
513 word new_head = head + 1;
514 word capacity = deque.capacity();
515 if (new_head >= capacity) {
516 new_head -= capacity;
517 }
518 Object result(&scope, deque.at(head));
519 deque.atPut(head, NoneType::object());
520 deque.setNumItems(num_items - 1);
521 deque.setLeft(new_head);
522 return *result;
523}
524
525bool METH(deque, __getitem___intrinsic)(Thread* thread) {
526 RawObject arg0 = thread->stackPeek(1);
527 if (!arg0.isDeque()) {
528 return false;
529 }
530
531 word index;
532 RawObject arg1 = thread->stackPeek(0);
533 if (arg1.isSmallInt()) {
534 index = SmallInt::cast(arg1).value();
535 if (index < 0) {
536 return false;
537 }
538 } else if (arg1.isBool()) {
539 index = Bool::cast(arg1).value();
540 } else {
541 return false;
542 }
543
544 RawDeque self = Deque::cast(arg0);
545 word num_items = self.numItems();
546 if (index >= num_items) {
547 return false;
548 }
549
550 word deque_index = self.left() + index;
551 word capacity = self.capacity();
552 if (deque_index >= capacity) {
553 deque_index -= capacity;
554 }
555
556 thread->stackDrop(2);
557 thread->stackSetTop(self.at(deque_index));
558 return true;
559}
560
561RawObject METH(deque, __iter__)(Thread* thread, Arguments args) {
562 HandleScope scope(thread);
563 Object self(&scope, args.get(0));
564 Runtime* runtime = thread->runtime();
565 if (!runtime->isInstanceOfDeque(*self)) {
566 return thread->raiseRequiresType(self, ID(deque));
567 }
568 Deque deque(&scope, *self);
569 return runtime->newDequeIterator(deque, 0);
570}
571
572RawObject METH(deque, __len__)(Thread* thread, Arguments args) {
573 HandleScope scope(thread);
574 Object self(&scope, args.get(0));
575 if (!thread->runtime()->isInstanceOfDeque(*self)) {
576 return thread->raiseRequiresType(self, ID(deque));
577 }
578 Deque deque(&scope, *self);
579 return SmallInt::fromWord(deque.numItems());
580}
581
582RawObject METH(deque, __new__)(Thread* thread, Arguments args) {
583 HandleScope scope(thread);
584 Object type_obj(&scope, args.get(0));
585 Runtime* runtime = thread->runtime();
586 if (!runtime->isInstanceOfType(*type_obj)) {
587 return thread->raiseWithFmt(LayoutId::kTypeError, "not a type object");
588 }
589 Type type(&scope, *type_obj);
590 if (type.builtinBase() != LayoutId::kDeque) {
591 return thread->raiseWithFmt(LayoutId::kTypeError, "not a subtype of deque");
592 }
593 Layout layout(&scope, type.instanceLayout());
594 Deque deque(&scope, runtime->newInstance(layout));
595 deque.setItems(SmallInt::fromWord(0));
596 deque.setLeft(0);
597 deque.setNumItems(0);
598 deque.setState(0);
599 return *deque;
600}
601
602RawObject METH(deque, __reversed__)(Thread* thread, Arguments args) {
603 HandleScope scope(thread);
604 Object self(&scope, args.get(0));
605 Runtime* runtime = thread->runtime();
606 if (!runtime->isInstanceOfDeque(*self)) {
607 return thread->raiseRequiresType(self, ID(deque));
608 }
609 Deque deque(&scope, *self);
610 return runtime->newDequeReverseIterator(deque, 0);
611}
612
613bool METH(deque, __setitem___intrinsic)(Thread* thread) {
614 RawObject arg0 = thread->stackPeek(2);
615 if (!arg0.isDeque()) {
616 return false;
617 }
618
619 word index;
620 RawObject arg1 = thread->stackPeek(1);
621 if (arg1.isSmallInt()) {
622 index = SmallInt::cast(arg1).value();
623 if (index < 0) {
624 return false;
625 }
626 } else if (arg1.isBool()) {
627 index = Bool::cast(arg1).value();
628 } else {
629 return false;
630 }
631
632 RawDeque self = Deque::cast(arg0);
633 word num_items = self.numItems();
634 if (index >= num_items) {
635 return false;
636 }
637
638 word deque_index = self.left() + index;
639 word capacity = self.capacity();
640 if (deque_index >= capacity) {
641 deque_index -= capacity;
642 }
643
644 self.atPut(deque_index, thread->stackPeek(0));
645 thread->stackDrop(3);
646 thread->stackSetTop(NoneType::object());
647 return true;
648}
649
650RawObject METH(deque, append)(Thread* thread, Arguments args) {
651 HandleScope scope(thread);
652 Object self(&scope, args.get(0));
653 Runtime* runtime = thread->runtime();
654 if (!runtime->isInstanceOfDeque(*self)) {
655 return thread->raiseRequiresType(self, ID(deque));
656 }
657 Deque deque(&scope, *self);
658 Object value(&scope, args.get(1));
659 dequeAppend(thread, deque, value);
660 deque.setState(deque.state() + 1);
661 return NoneType::object();
662}
663
664RawObject METH(deque, appendleft)(Thread* thread, Arguments args) {
665 HandleScope scope(thread);
666 Object self(&scope, args.get(0));
667 if (!thread->runtime()->isInstanceOfDeque(*self)) {
668 return thread->raiseRequiresType(self, ID(deque));
669 }
670 Deque deque(&scope, *self);
671 deque.setState(deque.state() + 1);
672 Object value(&scope, args.get(1));
673 dequeAppendLeft(thread, deque, value);
674 return NoneType::object();
675}
676
677RawObject METH(deque, clear)(Thread* thread, Arguments args) {
678 HandleScope scope(thread);
679 Object self(&scope, args.get(0));
680 if (!thread->runtime()->isInstanceOfDeque(*self)) {
681 return thread->raiseRequiresType(self, ID(deque));
682 }
683 Deque deque(&scope, *self);
684 deque.setState(deque.state() + 1);
685 deque.clear();
686 return NoneType::object();
687}
688
689RawObject METH(deque, pop)(Thread* thread, Arguments args) {
690 HandleScope scope(thread);
691 Object self(&scope, args.get(0));
692 if (!thread->runtime()->isInstanceOfDeque(*self)) {
693 return thread->raiseRequiresType(self, ID(deque));
694 }
695 Deque deque(&scope, *self);
696 if (deque.numItems() == 0) {
697 return thread->raiseWithFmt(LayoutId::kIndexError, "pop from empty deque");
698 }
699 deque.setState(deque.state() + 1);
700 return dequePop(thread, deque);
701}
702
703RawObject METH(deque, popleft)(Thread* thread, Arguments args) {
704 HandleScope scope(thread);
705 Object self(&scope, args.get(0));
706 if (!thread->runtime()->isInstanceOfDeque(*self)) {
707 return thread->raiseRequiresType(self, ID(deque));
708 }
709 Deque deque(&scope, *self);
710 if (deque.numItems() == 0) {
711 return thread->raiseWithFmt(LayoutId::kIndexError, "pop from empty deque");
712 }
713 deque.setState(deque.state() + 1);
714 return dequePopLeft(thread, deque);
715}
716
717RawObject METH(deque, reverse)(Thread* thread, Arguments args) {
718 HandleScope scope(thread);
719 Object self(&scope, args.get(0));
720 if (!thread->runtime()->isInstanceOfDeque(*self)) {
721 return thread->raiseRequiresType(self, ID(deque));
722 }
723
724 Deque deque(&scope, *self);
725 word length = deque.numItems();
726 if (length == 0) {
727 return NoneType::object();
728 }
729
730 MutableTuple items(&scope, deque.items());
731 word left = deque.left();
732 word capacity = items.length();
733 word right = left + length;
734
735 word prefix = right - capacity;
736 word suffix = capacity - left;
737 if (prefix > suffix) {
738 for (right = prefix - 1; left < capacity; left++, right--) {
739 items.swap(left, right);
740 }
741 left = 0;
742 } else if (prefix > 0) {
743 for (right = prefix - 1; right >= 0; left++, right--) {
744 items.swap(left, right);
745 }
746 right += capacity;
747 } else {
748 right--;
749 }
750
751 for (; left < right; left++, right--) {
752 items.swap(left, right);
753 }
754
755 return NoneType::object();
756}
757
758} // namespace py