bernsteinbear.com
this repo has no description
1// Copyright (c) Facebook, Inc. and its affiliates. (http://www.facebook.com)
2#include "set-builtins.h"
3
4#include "builtins.h"
5#include "dict-builtins.h"
6#include "frame.h"
7#include "globals.h"
8#include "objects.h"
9#include "runtime.h"
10#include "thread.h"
11#include "type-builtins.h"
12
13namespace py {
14// Data tuple layout
15static const word kHashOffset = 0;
16static const word kValueOffset = kHashOffset + 1;
17static const word kNumPointers = kValueOffset + 1;
18
19static word getIndex(RawTuple data, word hash) {
20 DCHECK(SmallInt::isValid(hash), "hash out of range");
21 word nitems = data.length() / kNumPointers;
22 DCHECK(Utils::isPowerOfTwo(nitems), "%ld not a power of 2", nitems);
23 return (hash & (nitems - 1)) * kNumPointers;
24}
25
26static bool isEmpty(RawTuple data, word index) {
27 return data.at(index + kHashOffset).isNoneType();
28}
29
30static bool isFull(RawTuple data, word index) {
31 return data.at(index + kHashOffset).isSmallInt();
32}
33
34static bool isTombstone(RawTuple data, word index) {
35 return data.at(index + kHashOffset).isUnbound();
36}
37
38static word itemHash(RawTuple data, word index) {
39 return SmallInt::cast(data.at(index + kHashOffset)).value();
40}
41
42static RawObject itemValue(RawTuple data, word index) {
43 return data.at(index + kValueOffset);
44}
45
46static void itemAtPut(RawTuple data, word index, word hash, RawObject value) {
47 data.atPut(index + kHashOffset, SmallInt::fromWordTruncated(hash));
48 data.atPut(index + kValueOffset, value);
49}
50
51static void itemAtPutTombstone(RawTuple data, word index) {
52 data.atPut(index + kHashOffset, Unbound::object());
53 data.atPut(index + kValueOffset, NoneType::object());
54}
55
56static word nextItemIndex(RawTuple data, word* index) {
57 for (word i = *index; i < data.length(); i += kNumPointers) {
58 if (!isFull(data, i)) continue;
59 *index = i + kNumPointers;
60 return i;
61 }
62 return -1;
63}
64
65bool setNextItem(const SetBase& set, word* index, RawObject* value_out) {
66 RawTuple data = RawTuple::cast(set.data());
67 word next_item_index = nextItemIndex(data, index);
68 if (next_item_index < 0) {
69 return false;
70 }
71 *value_out = itemValue(data, next_item_index);
72 return true;
73}
74
75bool setNextItemHash(const SetBase& set, word* index, RawObject* value_out,
76 word* hash_out) {
77 DCHECK(hash_out != nullptr, "hash_out must not be null");
78 RawTuple data = RawTuple::cast(set.data());
79 word next_item_index = nextItemIndex(data, index);
80 if (next_item_index < 0) {
81 return false;
82 }
83 *value_out = itemValue(data, next_item_index);
84 *hash_out = itemHash(data, next_item_index);
85
86 return true;
87}
88
89static word entryMatches(Thread* thread, RawTuple data, word entry,
90 word hash_value, const Object& key) {
91 DCHECK(isFull(data, entry), "entry cannot be a tombstone");
92 if (itemHash(data, entry) == hash_value) {
93 RawObject start_key = itemValue(data, entry);
94 RawObject eq = Runtime::objectEquals(thread, start_key, *key);
95 if (eq == Bool::trueObj()) {
96 return entry;
97 }
98 if (eq.isErrorException()) {
99 UNIMPLEMENTED("exception in value comparison");
100 }
101 return -1;
102 }
103 return -1;
104}
105
106static const word kNumLinearProbes = 9;
107static const word kPerturbShift = 5;
108
109static word setLookup(Thread* thread, const Tuple& data, const Object& key,
110 word hash_value) {
111 word length = data.length();
112 if (length == 0) {
113 return -1;
114 }
115 uword perturb = static_cast<uword>(hash_value);
116 word mask = length - 1;
117 word i = hash_value & mask;
118 word entry = getIndex(*data, i);
119
120 if (isEmpty(*data, entry)) {
121 return -1;
122 }
123
124 for (;;) {
125 if (isFull(*data, entry)) {
126 word match = entryMatches(thread, *data, entry, hash_value, key);
127 if (match != -1) {
128 return match;
129 }
130 }
131 if (entry + kNumLinearProbes * kNumPointers <= mask) {
132 for (int j = 1; j <= kNumLinearProbes; j++) {
133 entry += kNumPointers;
134 if (isEmpty(*data, entry)) {
135 return -1;
136 }
137 if (!isTombstone(*data, entry)) {
138 word match = entryMatches(thread, *data, entry, hash_value, key);
139 if (match != -1) {
140 return match;
141 }
142 }
143 }
144 }
145 perturb >>= kPerturbShift;
146 i = (i * 5 + 1 + perturb) & mask;
147 entry = getIndex(*data, i);
148 if (isEmpty(*data, entry)) {
149 return -1;
150 }
151 }
152}
153
154static word setLookupForInsertion(Thread* thread, const Tuple& data,
155 const Object& key, word hash_value) {
156 word length = data.length();
157 if (length == 0) {
158 return -1;
159 }
160 uword perturb = static_cast<uword>(hash_value);
161 word mask = length - 1;
162 word i = hash_value & mask;
163 word entry = getIndex(*data, i);
164
165 if (isEmpty(*data, entry)) {
166 return entry;
167 }
168
169 for (word freeslot = -1;;) {
170 if (isFull(*data, entry)) {
171 word match = entryMatches(thread, *data, entry, hash_value, key);
172 if (match != -1) {
173 return match;
174 }
175 } else if (isTombstone(*data, entry)) {
176 freeslot = entry;
177 }
178 if (entry + kNumLinearProbes * kNumPointers <= mask) {
179 for (int j = 1; j <= kNumLinearProbes; j++) {
180 entry += kNumPointers;
181 if (isEmpty(*data, entry)) {
182 return entry;
183 }
184 if (!isTombstone(*data, entry)) {
185 word match = entryMatches(thread, *data, entry, hash_value, key);
186 if (match != -1) {
187 return match;
188 }
189 } else if (isTombstone(*data, entry)) {
190 freeslot = entry;
191 }
192 }
193 }
194 perturb >>= kPerturbShift;
195 i = (i * 5 + 1 + perturb) & mask;
196 entry = getIndex(*data, i);
197 if (isEmpty(*data, entry)) {
198 return (freeslot == -1) ? entry : freeslot;
199 }
200 }
201}
202
203static RawTuple setGrow(Thread* thread, const SetBase& set) {
204 HandleScope scope(thread);
205 Tuple data(&scope, set.data());
206 word new_length = data.length() * Runtime::kSetGrowthFactor;
207 if (new_length == 0) {
208 new_length = Runtime::kInitialSetCapacity * kNumPointers;
209 }
210 MutableTuple new_data(&scope, thread->runtime()->newMutableTuple(new_length));
211 new_data.fill(NoneType::object());
212 // Re-insert items
213 Object value(&scope, NoneType::object());
214 for (word i = 0, hash; setNextItemHash(set, &i, &value, &hash);) {
215 word index = setLookupForInsertion(thread, new_data, value, hash);
216 DCHECK(index != -1, "unexpected index %ld", index);
217 itemAtPut(*new_data, index, hash, *value);
218 }
219 set.setNumFilled(set.numItems());
220 return *new_data;
221}
222
223RawObject setAdd(Thread* thread, const SetBase& set, const Object& value,
224 word hash) {
225 HandleScope scope(thread);
226 Tuple data(&scope, set.data());
227 word index = setLookup(thread, data, value, hash);
228 if (index != -1) {
229 return itemValue(*data, index);
230 }
231
232 Tuple new_data(&scope, *data);
233 if (data.length() == 0 || 10 * set.numFilled() >= 3 * data.length()) {
234 new_data = setGrow(thread, set);
235 }
236 index = setLookupForInsertion(thread, new_data, value, hash);
237 DCHECK(index != -1, "unexpected index %ld", index);
238 set.setData(*new_data);
239 itemAtPut(*new_data, index, hash, *value);
240 set.setNumItems(set.numItems() + 1);
241 set.setNumFilled(set.numFilled() + 1);
242 return *value;
243}
244
245bool setIncludes(Thread* thread, const SetBase& set, const Object& key,
246 word hash) {
247 HandleScope scope(thread);
248 Tuple data(&scope, set.data());
249 return setLookup(thread, data, key, hash) != -1;
250}
251
252RawObject setIntersection(Thread* thread, const SetBase& set,
253 const Object& iterable) {
254 HandleScope scope(thread);
255 Runtime* runtime = thread->runtime();
256 SetBase dst(&scope, runtime->isInstanceOfSet(*set) ? runtime->newSet()
257 : runtime->newFrozenSet());
258 Object value(&scope, NoneType::object());
259 // Special case for sets
260 if (runtime->isInstanceOfSetBase(*iterable)) {
261 SetBase self(&scope, *set);
262 SetBase other(&scope, *iterable);
263 if (set.numItems() == 0 || other.numItems() == 0) {
264 return *dst;
265 }
266 // Iterate over the smaller set
267 if (set.numItems() > other.numItems()) {
268 self = *iterable;
269 other = *set;
270 }
271 Tuple other_data(&scope, other.data());
272 for (word i = 0, hash; setNextItemHash(self, &i, &value, &hash);) {
273 if (setLookup(thread, other_data, value, hash) != -1) {
274 setAdd(thread, dst, value, hash);
275 }
276 }
277 return *dst;
278 }
279 // Generic case
280 Object iter_method(&scope,
281 Interpreter::lookupMethod(thread, iterable, ID(__iter__)));
282 if (iter_method.isError()) {
283 return thread->raiseWithFmt(LayoutId::kTypeError, "object is not iterable");
284 }
285 Object iterator(&scope,
286 Interpreter::callMethod1(thread, iter_method, iterable));
287 if (iterator.isError()) {
288 return thread->raiseWithFmt(LayoutId::kTypeError, "object is not iterable");
289 }
290 Object next_method(&scope,
291 Interpreter::lookupMethod(thread, iterator, ID(__next__)));
292 if (next_method.isError()) {
293 return thread->raiseWithFmt(LayoutId::kTypeError,
294 "iter() returned a non-iterator");
295 }
296 if (set.numItems() == 0) {
297 return *dst;
298 }
299 Tuple data(&scope, set.data());
300 Object hash_obj(&scope, NoneType::object());
301 for (;;) {
302 value = Interpreter::callMethod1(thread, next_method, iterator);
303 if (value.isError()) {
304 if (thread->clearPendingStopIteration()) break;
305 return *value;
306 }
307 hash_obj = Interpreter::hash(thread, value);
308 if (hash_obj.isErrorException()) return *hash_obj;
309 word hash = SmallInt::cast(*hash_obj).value();
310 if (setLookup(thread, data, value, hash) != -1) {
311 setAdd(thread, dst, value, hash);
312 }
313 }
314 return *dst;
315}
316
317bool setRemove(Thread* thread, const Set& set, const Object& key, word hash) {
318 HandleScope scope(thread);
319 Tuple data(&scope, set.data());
320 word index = setLookup(thread, data, key, hash);
321 if (index != -1) {
322 itemAtPutTombstone(*data, index);
323 set.setNumItems(set.numItems() - 1);
324 return true;
325 }
326 return false;
327}
328
329RawObject setUpdate(Thread* thread, const SetBase& dst,
330 const Object& iterable) {
331 HandleScope scope(thread);
332 Object elt(&scope, NoneType::object());
333 Object hash_obj(&scope, NoneType::object());
334 // Special case for lists
335 if (iterable.isList()) {
336 List src(&scope, *iterable);
337 for (word i = 0; i < src.numItems(); i++) {
338 elt = src.at(i);
339 hash_obj = Interpreter::hash(thread, elt);
340 if (hash_obj.isErrorException()) return *hash_obj;
341 word hash = SmallInt::cast(*hash_obj).value();
342 setAdd(thread, dst, elt, hash);
343 }
344 return *dst;
345 }
346 // Special case for lists iterators
347 if (iterable.isListIterator()) {
348 ListIterator list_iter(&scope, *iterable);
349 List src(&scope, list_iter.iterable());
350 for (word i = 0; i < src.numItems(); i++) {
351 elt = src.at(i);
352 hash_obj = Interpreter::hash(thread, elt);
353 if (hash_obj.isErrorException()) return *hash_obj;
354 word hash = SmallInt::cast(*hash_obj).value();
355 setAdd(thread, dst, elt, hash);
356 }
357 }
358 // Special case for tuples
359 if (iterable.isTuple()) {
360 Tuple tuple(&scope, *iterable);
361 if (tuple.length() > 0) {
362 for (word i = 0; i < tuple.length(); i++) {
363 elt = tuple.at(i);
364 hash_obj = Interpreter::hash(thread, elt);
365 if (hash_obj.isErrorException()) return *hash_obj;
366 word hash = SmallInt::cast(*hash_obj).value();
367 setAdd(thread, dst, elt, hash);
368 }
369 }
370 return *dst;
371 }
372 // Special case for built-in set types
373 if (thread->runtime()->isInstanceOfSetBase(*iterable)) {
374 SetBase src(&scope, *iterable);
375 if (src.numItems() > 0) {
376 for (word i = 0, hash; setNextItemHash(src, &i, &elt, &hash);) {
377 // take hash from data to avoid recomputing it.
378 setAdd(thread, dst, elt, hash);
379 }
380 }
381 return *dst;
382 }
383 // Special case for dicts
384 if (iterable.isDict()) {
385 Dict dict(&scope, *iterable);
386 for (word i = 0, hash; dictNextKeyHash(dict, &i, &elt, &hash);) {
387 setAdd(thread, dst, elt, hash);
388 }
389 return *dst;
390 }
391 // Generic case
392 Object iter_method(&scope,
393 Interpreter::lookupMethod(thread, iterable, ID(__iter__)));
394 if (iter_method.isError()) {
395 return thread->raiseWithFmt(LayoutId::kTypeError,
396 "'%T' object is not iterable", &iterable);
397 }
398 Object iterator(&scope,
399 Interpreter::callMethod1(thread, iter_method, iterable));
400 if (iterator.isError()) {
401 return thread->raiseWithFmt(LayoutId::kTypeError,
402 "'%T' object is not iterable", &iterable);
403 }
404 Object next_method(&scope,
405 Interpreter::lookupMethod(thread, iterator, ID(__next__)));
406 if (next_method.isError()) {
407 return thread->raiseWithFmt(LayoutId::kTypeError,
408 "iter() returned a non-iterator");
409 }
410 for (;;) {
411 elt = Interpreter::callMethod1(thread, next_method, iterator);
412 if (elt.isError()) {
413 if (thread->clearPendingStopIteration()) break;
414 return *elt;
415 }
416 hash_obj = Interpreter::hash(thread, elt);
417 if (hash_obj.isErrorException()) return *hash_obj;
418 word hash = SmallInt::cast(*hash_obj).value();
419 setAdd(thread, dst, elt, hash);
420 }
421 return *dst;
422}
423
424RawSmallInt frozensetHash(Thread* thread, const Object& frozenset) {
425 HandleScope scope(thread);
426 FrozenSet set(&scope, *frozenset);
427 uword result = 0;
428 Object value(&scope, NoneType::object());
429 for (word i = 0, value_hash; setNextItemHash(set, &i, &value, &value_hash);) {
430 uword h = static_cast<uword>(value_hash);
431 result ^= ((h ^ uword{89869747}) ^ (h << 16)) * uword{3644798167};
432 }
433 result ^= static_cast<uword>(set.numItems() + 1) * uword{1927868237};
434
435 result ^= (result >> 11) ^ (result >> 25);
436 result = result * uword{69069} + uword{907133923};
437
438 // cpython replaces `-1` results with -2, because -1 is used as an
439 // "uninitialized hash" marker in some situations. We do not use the same
440 // marker, but do the same to match behavior.
441 if (result == static_cast<uword>(word{-1})) {
442 result--;
443 }
444 return SmallInt::fromWordTruncated(result);
445}
446
447static RawObject dunderLenImpl(Thread* thread, Arguments args, SymbolId id) {
448 HandleScope scope(thread);
449 Object self(&scope, args.get(0));
450 if (!thread->runtime()->isInstanceOfSetBase(*self)) {
451 return thread->raiseRequiresType(self, id);
452 }
453 SetBase set(&scope, *self);
454 return SmallInt::fromWord(set.numItems());
455}
456
457static RawObject dunderContainsImpl(Thread* thread, Arguments args,
458 SymbolId id) {
459 HandleScope scope(thread);
460 Object self(&scope, args.get(0));
461 if (!thread->runtime()->isInstanceOfSetBase(*self)) {
462 return thread->raiseRequiresType(self, id);
463 }
464 SetBase set(&scope, *self);
465 Object key(&scope, args.get(1));
466 Object hash_obj(&scope, Interpreter::hash(thread, key));
467 if (hash_obj.isErrorException()) return *hash_obj;
468 word hash = SmallInt::cast(*hash_obj).value();
469 return Bool::fromBool(setIncludes(thread, set, key, hash));
470}
471
472static RawObject dunderIterImpl(Thread* thread, Arguments args, SymbolId id) {
473 HandleScope scope(thread);
474 Object self(&scope, args.get(0));
475 if (!thread->runtime()->isInstanceOfSetBase(*self)) {
476 return thread->raiseRequiresType(self, id);
477 }
478 return thread->runtime()->newSetIterator(self);
479}
480
481static RawObject isdisjointImpl(Thread* thread, Arguments args, SymbolId id) {
482 HandleScope scope(thread);
483 Object self(&scope, args.get(0));
484 Object other(&scope, args.get(1));
485 Object value(&scope, NoneType::object());
486 if (!thread->runtime()->isInstanceOfSetBase(*self)) {
487 return thread->raiseRequiresType(self, id);
488 }
489 SetBase a(&scope, *self);
490 if (a.numItems() == 0) {
491 return Bool::trueObj();
492 }
493 if (thread->runtime()->isInstanceOfSetBase(*other)) {
494 SetBase b(&scope, *other);
495 if (b.numItems() == 0) {
496 return Bool::trueObj();
497 }
498 // Iterate over the smaller set
499 if (a.numItems() > b.numItems()) {
500 a = *other;
501 b = *self;
502 }
503 for (word i = 0, hash; setNextItemHash(a, &i, &value, &hash);) {
504 if (setIncludes(thread, b, value, hash)) {
505 return Bool::falseObj();
506 }
507 }
508 return Bool::trueObj();
509 }
510 // Generic iterator case
511 Object iter_method(&scope,
512 Interpreter::lookupMethod(thread, other, ID(__iter__)));
513 if (iter_method.isError()) {
514 return thread->raiseWithFmt(LayoutId::kTypeError, "object is not iterable");
515 }
516 Object iterator(&scope, Interpreter::callMethod1(thread, iter_method, other));
517 if (iterator.isError()) {
518 return thread->raiseWithFmt(LayoutId::kTypeError, "object is not iterable");
519 }
520 Object next_method(&scope,
521 Interpreter::lookupMethod(thread, iterator, ID(__next__)));
522 if (next_method.isError()) {
523 return thread->raiseWithFmt(LayoutId::kTypeError,
524 "iter() returned a non-iterator");
525 }
526 Object hash_obj(&scope, NoneType::object());
527 for (;;) {
528 value = Interpreter::callMethod1(thread, next_method, iterator);
529 if (value.isError()) {
530 if (thread->clearPendingStopIteration()) break;
531 return *value;
532 }
533 hash_obj = Interpreter::hash(thread, value);
534 if (hash_obj.isErrorException()) return *hash_obj;
535 word hash = SmallInt::cast(*hash_obj).value();
536 if (setIncludes(thread, a, value, hash)) {
537 return Bool::falseObj();
538 }
539 }
540 return Bool::trueObj();
541}
542
543static RawObject intersectionImpl(Thread* thread, Arguments args, SymbolId id) {
544 HandleScope scope(thread);
545 Object self(&scope, args.get(0));
546 if (!thread->runtime()->isInstanceOfSetBase(*self)) {
547 return thread->raiseRequiresType(self, id);
548 }
549 SetBase set(&scope, *self);
550 Object other(&scope, args.get(1));
551 return setIntersection(thread, set, other);
552}
553
554static RawObject dunderEqImpl(Thread* thread, Arguments args, SymbolId id) {
555 Runtime* runtime = thread->runtime();
556 HandleScope scope(thread);
557 Object self(&scope, args.get(0));
558 Object other(&scope, args.get(1));
559 if (!runtime->isInstanceOfSetBase(*self)) {
560 return thread->raiseRequiresType(self, id);
561 }
562 if (!runtime->isInstanceOfSetBase(*other)) {
563 return NotImplementedType::object();
564 }
565 SetBase set(&scope, *self);
566 SetBase other_set(&scope, *other);
567 return Bool::fromBool(setEquals(thread, set, other_set));
568}
569
570static RawObject dunderNeImpl(Thread* thread, Arguments args, SymbolId id) {
571 Runtime* runtime = thread->runtime();
572 HandleScope scope(thread);
573 Object self(&scope, args.get(0));
574 Object other(&scope, args.get(1));
575 if (!runtime->isInstanceOfSetBase(*self)) {
576 return thread->raiseRequiresType(self, id);
577 }
578 if (!runtime->isInstanceOfSetBase(*other)) {
579 return NotImplementedType::object();
580 }
581 SetBase set(&scope, *self);
582 SetBase other_set(&scope, *other);
583 return Bool::fromBool(!setEquals(thread, set, other_set));
584}
585
586static RawObject dunderLeImpl(Thread* thread, Arguments args, SymbolId id) {
587 Runtime* runtime = thread->runtime();
588 HandleScope scope(thread);
589 Object self(&scope, args.get(0));
590 Object other(&scope, args.get(1));
591 if (!runtime->isInstanceOfSetBase(*self)) {
592 return thread->raiseRequiresType(self, id);
593 }
594 if (!runtime->isInstanceOfSetBase(*other)) {
595 return NotImplementedType::object();
596 }
597 SetBase set(&scope, *self);
598 SetBase other_set(&scope, *other);
599 return Bool::fromBool(setIsSubset(thread, set, other_set));
600}
601
602static RawObject dunderLtImpl(Thread* thread, Arguments args, SymbolId id) {
603 Runtime* runtime = thread->runtime();
604 HandleScope scope(thread);
605 Object self(&scope, args.get(0));
606 Object other(&scope, args.get(1));
607 if (!runtime->isInstanceOfSetBase(*self)) {
608 return thread->raiseRequiresType(self, id);
609 }
610 if (!runtime->isInstanceOfSetBase(*other)) {
611 return NotImplementedType::object();
612 }
613 SetBase set(&scope, *self);
614 SetBase other_set(&scope, *other);
615 return Bool::fromBool(setIsProperSubset(thread, set, other_set));
616}
617
618static RawObject dunderGeImpl(Thread* thread, Arguments args, SymbolId id) {
619 Runtime* runtime = thread->runtime();
620 HandleScope scope(thread);
621 Object self(&scope, args.get(0));
622 Object other(&scope, args.get(1));
623 if (!runtime->isInstanceOfSetBase(*self)) {
624 return thread->raiseRequiresType(self, id);
625 }
626 if (!runtime->isInstanceOfSetBase(*other)) {
627 return NotImplementedType::object();
628 }
629 SetBase set(&scope, *self);
630 SetBase other_set(&scope, *other);
631 return Bool::fromBool(setIsSubset(thread, other_set, set));
632}
633
634static RawObject dunderGtImpl(Thread* thread, Arguments args, SymbolId id) {
635 Runtime* runtime = thread->runtime();
636 HandleScope scope(thread);
637 Object self(&scope, args.get(0));
638 Object other(&scope, args.get(1));
639 if (!runtime->isInstanceOfSetBase(*self)) {
640 return thread->raiseRequiresType(self, id);
641 }
642 if (!runtime->isInstanceOfSetBase(*other)) {
643 return NotImplementedType::object();
644 }
645 SetBase set(&scope, *self);
646 SetBase other_set(&scope, *other);
647 return Bool::fromBool(setIsProperSubset(thread, other_set, set));
648}
649
650static const BuiltinAttribute kFrozenSetAttributes[] = {
651 {ID(_frozenset__data), RawFrozenSet::kDataOffset, AttributeFlags::kHidden},
652 {ID(_frozenset__num_items), RawFrozenSet::kNumItemsOffset,
653 AttributeFlags::kHidden},
654 {ID(_frozenset__num_filled), RawFrozenSet::kNumFilledOffset,
655 AttributeFlags::kHidden},
656};
657
658RawObject METH(frozenset, __and__)(Thread* thread, Arguments args) {
659 HandleScope scope(thread);
660 Object self(&scope, args.get(0));
661 Object other(&scope, args.get(1));
662 Runtime* runtime = thread->runtime();
663 if (!runtime->isInstanceOfFrozenSet(*self)) {
664 return thread->raiseRequiresType(self, ID(frozenset));
665 }
666 if (!runtime->isInstanceOfSetBase(*other)) {
667 return NotImplementedType::object();
668 }
669 FrozenSet set(&scope, *self);
670 SetBase other_set(&scope, *other);
671 return setIntersection(thread, set, other_set);
672}
673
674RawObject METH(frozenset, __contains__)(Thread* thread, Arguments args) {
675 return dunderContainsImpl(thread, args, ID(frozenset));
676}
677
678RawObject METH(frozenset, __eq__)(Thread* thread, Arguments args) {
679 return dunderEqImpl(thread, args, ID(frozenset));
680}
681
682RawObject METH(frozenset, __ge__)(Thread* thread, Arguments args) {
683 return dunderGeImpl(thread, args, ID(frozenset));
684}
685
686RawObject METH(frozenset, __gt__)(Thread* thread, Arguments args) {
687 return dunderGtImpl(thread, args, ID(frozenset));
688}
689
690RawObject METH(frozenset, __hash__)(Thread* thread, Arguments args) {
691 HandleScope scope(thread);
692 Object self(&scope, args.get(0));
693 if (!thread->runtime()->isInstanceOfFrozenSet(*self)) {
694 return thread->raiseRequiresType(self, ID(frozenset));
695 }
696 FrozenSet set(&scope, *self);
697 return frozensetHash(thread, set);
698}
699
700RawObject METH(frozenset, __iter__)(Thread* thread, Arguments args) {
701 return dunderIterImpl(thread, args, ID(frozenset));
702}
703
704RawObject METH(frozenset, __le__)(Thread* thread, Arguments args) {
705 return dunderLeImpl(thread, args, ID(frozenset));
706}
707
708RawObject METH(frozenset, __len__)(Thread* thread, Arguments args) {
709 return dunderLenImpl(thread, args, ID(frozenset));
710}
711
712RawObject METH(frozenset, __lt__)(Thread* thread, Arguments args) {
713 return dunderLtImpl(thread, args, ID(frozenset));
714}
715
716RawObject METH(frozenset, __ne__)(Thread* thread, Arguments args) {
717 return dunderNeImpl(thread, args, ID(frozenset));
718}
719
720RawObject METH(frozenset, __new__)(Thread* thread, Arguments args) {
721 HandleScope scope(thread);
722 Object type_obj(&scope, args.get(0));
723 Runtime* runtime = thread->runtime();
724 if (!runtime->isInstanceOfType(*type_obj)) {
725 return thread->raiseRequiresType(type_obj, ID(type));
726 }
727 Type type(&scope, *type_obj);
728 if (type.builtinBase() != LayoutId::kFrozenSet) {
729 return thread->raiseWithFmt(LayoutId::kTypeError,
730 "not a subtype of frozenset");
731 }
732 if (args.get(1).isUnbound()) {
733 // Iterable not provided
734 if (type.isBuiltin() && type.builtinBase() == LayoutId::kFrozenSet) {
735 // Called with exact frozenset type, should return singleton
736 return runtime->emptyFrozenSet();
737 }
738 // Not called with exact frozenset type, should return new distinct
739 // frozenset
740 Layout layout(&scope, type.instanceLayout());
741 FrozenSet result(&scope, runtime->newInstance(layout));
742 result.setNumItems(0);
743 result.setNumFilled(0);
744 result.setData(runtime->emptyTuple());
745 return *result;
746 }
747 // Called with iterable, so iterate
748 Object iterable(&scope, args.get(1));
749 // frozenset(f) where f is a frozenset is idempotent
750 if (iterable.isFrozenSet()) {
751 return *iterable;
752 }
753 Object dunder_iter(&scope,
754 Interpreter::lookupMethod(thread, iterable, ID(__iter__)));
755 if (dunder_iter.isError()) {
756 return thread->raiseWithFmt(
757 LayoutId::kTypeError,
758 "frozenset.__new__ must be called with an iterable");
759 }
760 if (type.isBuiltin() && type.builtinBase() == LayoutId::kFrozenSet) {
761 // Called with exact frozenset type
762 FrozenSet result(&scope, runtime->newFrozenSet());
763 RawObject maybe_error = setUpdate(thread, result, iterable);
764 if (maybe_error.isError()) return maybe_error;
765 result = maybe_error;
766 if (result.numItems() == 0) {
767 return runtime->emptyFrozenSet();
768 }
769 return *result;
770 }
771 // Not called with exact frozenset type, should return new frozenset subclass
772 Layout layout(&scope, type.instanceLayout());
773 FrozenSet result(&scope, runtime->newInstance(layout));
774 result.setNumItems(0);
775 result.setNumFilled(0);
776 result.setData(runtime->emptyTuple());
777 return setUpdate(thread, result, iterable);
778}
779
780RawObject METH(frozenset, __or__)(Thread* thread, Arguments args) {
781 HandleScope scope(thread);
782 Object self_obj(&scope, args.get(0));
783 Object other(&scope, args.get(1));
784 Runtime* runtime = thread->runtime();
785 if (!runtime->isInstanceOfFrozenSet(*self_obj)) {
786 return thread->raiseRequiresType(self_obj, ID(frozenset));
787 }
788 if (!runtime->isInstanceOfSetBase(*other)) {
789 return NotImplementedType::object();
790 }
791 FrozenSet self(&scope, *self_obj);
792 if (*self == *other) {
793 // Make a shallow copy; we can alias the underlying immutable data
794 // structure
795 FrozenSet result(&scope, runtime->newFrozenSet());
796 result.setData(self.data());
797 result.setNumItems(self.numItems());
798 result.setNumFilled(self.numFilled());
799 return *result;
800 }
801 FrozenSet result(&scope, runtime->newFrozenSet());
802 Object maybe_error(&scope, setUpdate(thread, result, self));
803 if (maybe_error.isError()) return *maybe_error;
804 result = *maybe_error;
805 return setUpdate(thread, result, other);
806}
807
808RawObject METH(frozenset, copy)(Thread* thread, Arguments args) {
809 HandleScope scope(thread);
810 Object self(&scope, args.get(0));
811 if (!thread->runtime()->isInstanceOfFrozenSet(*self)) {
812 return thread->raiseRequiresType(self, ID(frozenset));
813 }
814 FrozenSet set(&scope, *self);
815 if (set.isFrozenSet()) {
816 return *set;
817 }
818 return setCopy(thread, set);
819}
820
821RawObject METH(frozenset, intersection)(Thread* thread, Arguments args) {
822 return intersectionImpl(thread, args, ID(frozenset));
823}
824
825RawObject METH(frozenset, isdisjoint)(Thread* thread, Arguments args) {
826 return isdisjointImpl(thread, args, ID(frozenset));
827}
828
829RawObject setCopy(Thread* thread, const SetBase& set) {
830 word num_items = set.numItems();
831 Runtime* runtime = thread->runtime();
832 if (num_items == 0) {
833 return runtime->isInstanceOfSet(*set) ? runtime->newSet()
834 : runtime->emptyFrozenSet();
835 }
836
837 HandleScope scope(thread);
838 SetBase new_set(&scope, runtime->isInstanceOfSet(*set)
839 ? runtime->newSet()
840 : runtime->newFrozenSet());
841 Tuple data(&scope, set.data());
842 MutableTuple new_data(&scope, runtime->newMutableTuple(data.length()));
843 new_data.fill(NoneType::object());
844 Object value(&scope, NoneType::object());
845 for (word i = 0, hash; setNextItemHash(set, &i, &value, &hash);) {
846 word dst_index = i - kNumPointers;
847 itemAtPut(*new_data, dst_index, hash, *value);
848 }
849 new_set.setData(*new_data);
850 new_set.setNumItems(set.numItems());
851 new_set.setNumFilled(set.numItems());
852 return *new_set;
853}
854
855bool setIsSubset(Thread* thread, const SetBase& set, const SetBase& other) {
856 HandleScope scope(thread);
857 Object value(&scope, NoneType::object());
858 for (word i = 0, hash; setNextItemHash(set, &i, &value, &hash);) {
859 if (!setIncludes(thread, other, value, hash)) {
860 return false;
861 }
862 }
863 return true;
864}
865
866bool setIsProperSubset(Thread* thread, const SetBase& set,
867 const SetBase& other) {
868 if (set.numItems() == other.numItems()) {
869 return false;
870 }
871 return setIsSubset(thread, set, other);
872}
873
874bool setEquals(Thread* thread, const SetBase& set, const SetBase& other) {
875 if (set.numItems() != other.numItems()) {
876 return false;
877 }
878 if (*set == *other) {
879 return true;
880 }
881 return setIsSubset(thread, set, other);
882}
883
884RawObject setPop(Thread* thread, const Set& set) {
885 HandleScope scope(thread);
886 Tuple data(&scope, set.data());
887 word num_items = set.numItems();
888 if (num_items != 0) {
889 Object value(&scope, NoneType::object());
890 for (word i = 0; setNextItem(set, &i, &value);) {
891 itemAtPutTombstone(*data, i - kNumPointers);
892 set.setNumItems(num_items - 1);
893 return *value;
894 }
895 }
896 // num_items == 0 or all items were found empty
897 return thread->raiseWithFmt(LayoutId::kKeyError, "pop from an empty set");
898}
899
900RawObject setIteratorNext(Thread* thread, const SetIterator& iter) {
901 word idx = iter.index();
902 HandleScope scope(thread);
903 SetBase underlying(&scope, iter.iterable());
904 Object value(&scope, NoneType::object());
905 // Find the next non empty item
906 if (!setNextItem(underlying, &idx, &value)) {
907 return Error::noMoreItems();
908 }
909 iter.setConsumedCount(iter.consumedCount() + 1);
910 iter.setIndex(idx);
911 return *value;
912}
913
914static const BuiltinAttribute kSetAttributes[] = {
915 {ID(_set__data), RawSet::kDataOffset, AttributeFlags::kHidden},
916 {ID(_set__num_items), RawSet::kNumItemsOffset, AttributeFlags::kHidden},
917 {ID(_set__num_filled), RawSet::kNumFilledOffset, AttributeFlags::kHidden},
918};
919
920RawObject METH(set, __and__)(Thread* thread, Arguments args) {
921 HandleScope scope(thread);
922 Object self(&scope, args.get(0));
923 Object other(&scope, args.get(1));
924 Runtime* runtime = thread->runtime();
925 if (!runtime->isInstanceOfSet(*self)) {
926 return thread->raiseRequiresType(self, ID(set));
927 }
928 if (!runtime->isInstanceOfSetBase(*other)) {
929 return NotImplementedType::object();
930 }
931 Set set(&scope, *self);
932 SetBase other_set(&scope, *other);
933 return setIntersection(thread, set, other_set);
934}
935
936RawObject METH(set, __contains__)(Thread* thread, Arguments args) {
937 return dunderContainsImpl(thread, args, ID(set));
938}
939
940RawObject METH(set, __eq__)(Thread* thread, Arguments args) {
941 return dunderEqImpl(thread, args, ID(set));
942}
943
944RawObject METH(set, __ge__)(Thread* thread, Arguments args) {
945 return dunderGeImpl(thread, args, ID(set));
946}
947
948RawObject METH(set, __gt__)(Thread* thread, Arguments args) {
949 return dunderGtImpl(thread, args, ID(set));
950}
951
952RawObject METH(set, __iand__)(Thread* thread, Arguments args) {
953 HandleScope scope(thread);
954 Object self(&scope, args.get(0));
955 Object other(&scope, args.get(1));
956 Runtime* runtime = thread->runtime();
957 if (!runtime->isInstanceOfSet(*self)) {
958 return thread->raiseRequiresType(self, ID(set));
959 }
960 if (!runtime->isInstanceOfSet(*other)) {
961 return NotImplementedType::object();
962 }
963 Set set(&scope, *self);
964 Object intersection(&scope, setIntersection(thread, set, other));
965 if (intersection.isError()) {
966 return *intersection;
967 }
968 RawSet intersection_set = Set::cast(*intersection);
969 set.setData(intersection_set.data());
970 set.setNumItems(intersection_set.numItems());
971 set.setNumFilled(intersection_set.numFilled());
972 return *set;
973}
974
975RawObject METH(set, __init__)(Thread* thread, Arguments args) {
976 Runtime* runtime = thread->runtime();
977 HandleScope scope(thread);
978 Object self(&scope, args.get(0));
979 if (!runtime->isInstanceOfSet(*self)) {
980 return thread->raiseRequiresType(self, ID(set));
981 }
982 Set set(&scope, *self);
983 Object iterable(&scope, args.get(1));
984 Object result(&scope, setUpdate(thread, set, iterable));
985 if (result.isError()) {
986 return *result;
987 }
988 return NoneType::object();
989}
990
991RawObject METH(set, __iter__)(Thread* thread, Arguments args) {
992 return dunderIterImpl(thread, args, ID(set));
993}
994
995RawObject METH(set, __le__)(Thread* thread, Arguments args) {
996 return dunderLeImpl(thread, args, ID(set));
997}
998
999RawObject METH(set, __len__)(Thread* thread, Arguments args) {
1000 return dunderLenImpl(thread, args, ID(set));
1001}
1002
1003RawObject METH(set, __lt__)(Thread* thread, Arguments args) {
1004 return dunderLtImpl(thread, args, ID(set));
1005}
1006
1007RawObject METH(set, __ne__)(Thread* thread, Arguments args) {
1008 return dunderNeImpl(thread, args, ID(set));
1009}
1010
1011RawObject METH(set, __new__)(Thread* thread, Arguments args) {
1012 HandleScope scope(thread);
1013 Runtime* runtime = thread->runtime();
1014 Object type_obj(&scope, args.get(0));
1015 if (!runtime->isInstanceOfType(*type_obj)) {
1016 return thread->raiseRequiresType(type_obj, ID(type));
1017 }
1018 Type type(&scope, *type_obj);
1019 if (type.builtinBase() != LayoutId::kSet) {
1020 return thread->raiseWithFmt(LayoutId::kTypeError, "not a subtype of set");
1021 }
1022 Layout layout(&scope, type.instanceLayout());
1023 Set result(&scope, runtime->newInstance(layout));
1024 result.setNumItems(0);
1025 result.setNumFilled(0);
1026 result.setData(runtime->emptyTuple());
1027 return *result;
1028}
1029
1030RawObject METH(set, add)(Thread* thread, Arguments args) {
1031 HandleScope scope(thread);
1032 Object self(&scope, args.get(0));
1033 Runtime* runtime = thread->runtime();
1034 if (!runtime->isInstanceOfSet(*self)) {
1035 return thread->raiseRequiresType(self, ID(set));
1036 }
1037 Set set(&scope, *self);
1038 Object value(&scope, args.get(1));
1039 Object hash_obj(&scope, Interpreter::hash(thread, value));
1040 if (hash_obj.isErrorException()) return *hash_obj;
1041 word hash = SmallInt::cast(*hash_obj).value();
1042
1043 Object result(&scope, setAdd(thread, set, value, hash));
1044 if (result.isError()) return *result;
1045 return NoneType::object();
1046}
1047
1048RawObject METH(set, clear)(Thread* thread, Arguments args) {
1049 HandleScope scope(thread);
1050 Object self(&scope, args.get(0));
1051 if (!thread->runtime()->isInstanceOfSet(*self)) {
1052 return thread->raiseRequiresType(self, ID(set));
1053 }
1054 Set set(&scope, *self);
1055 if (set.numItems() == 0) {
1056 return NoneType::object();
1057 }
1058 set.setNumItems(0);
1059 set.setNumFilled(0);
1060 MutableTuple data(&scope, set.data());
1061 data.fill(NoneType::object());
1062 return NoneType::object();
1063}
1064
1065RawObject METH(set, copy)(Thread* thread, Arguments args) {
1066 HandleScope scope(thread);
1067 Object self(&scope, args.get(0));
1068 if (!thread->runtime()->isInstanceOfSet(*self)) {
1069 return thread->raiseRequiresType(self, ID(set));
1070 }
1071 Set set(&scope, *self);
1072 return setCopy(thread, set);
1073}
1074
1075RawObject METH(set, discard)(Thread* thread, Arguments args) {
1076 HandleScope scope(thread);
1077 Object self_obj(&scope, args.get(0));
1078 Runtime* runtime = thread->runtime();
1079 if (!runtime->isInstanceOfSet(*self_obj)) {
1080 return thread->raiseRequiresType(self_obj, ID(set));
1081 }
1082 Set self(&scope, *self_obj);
1083 Object key(&scope, args.get(1));
1084 Object hash_obj(&scope, Interpreter::hash(thread, key));
1085 if (hash_obj.isErrorException()) return *hash_obj;
1086 word hash = SmallInt::cast(*hash_obj).value();
1087 setRemove(thread, self, key, hash);
1088 return NoneType::object();
1089}
1090
1091RawObject METH(set, intersection)(Thread* thread, Arguments args) {
1092 return intersectionImpl(thread, args, ID(set));
1093}
1094
1095RawObject METH(set, isdisjoint)(Thread* thread, Arguments args) {
1096 return isdisjointImpl(thread, args, ID(set));
1097}
1098
1099RawObject METH(set, pop)(Thread* thread, Arguments args) {
1100 HandleScope scope(thread);
1101 Object self(&scope, args.get(0));
1102 if (!thread->runtime()->isInstanceOfSet(*self)) {
1103 return thread->raiseRequiresType(self, ID(set));
1104 }
1105 Set set(&scope, args.get(0));
1106 return setPop(thread, set);
1107}
1108
1109RawObject METH(set, remove)(Thread* thread, Arguments args) {
1110 HandleScope scope(thread);
1111 Object self(&scope, args.get(0));
1112 Runtime* runtime = thread->runtime();
1113 if (!runtime->isInstanceOfSet(*self)) {
1114 return thread->raiseRequiresType(self, ID(set));
1115 }
1116 Set set(&scope, *self);
1117 Object key(&scope, args.get(1));
1118 Object hash_obj(&scope, Interpreter::hash(thread, key));
1119 if (hash_obj.isErrorException()) return *hash_obj;
1120 word hash = SmallInt::cast(*hash_obj).value();
1121 if (!setRemove(thread, set, key, hash)) {
1122 return thread->raise(LayoutId::kKeyError, *key);
1123 }
1124 return NoneType::object();
1125}
1126
1127RawObject METH(set, update)(Thread* thread, Arguments args) {
1128 HandleScope scope(thread);
1129 Runtime* runtime = thread->runtime();
1130 Object self_obj(&scope, args.get(0));
1131 if (!runtime->isInstanceOfSet(*self_obj)) {
1132 return thread->raiseRequiresType(self_obj, ID(set));
1133 }
1134 Set self(&scope, *self_obj);
1135 Object starargs_obj(&scope, args.get(1));
1136 if (!runtime->isInstanceOfTuple(*starargs_obj)) {
1137 return thread->raiseRequiresType(starargs_obj, ID(tuple));
1138 }
1139 Tuple starargs(&scope, tupleUnderlying(*starargs_obj));
1140 Object result(&scope, NoneType::object());
1141 for (word i = 0; i < starargs.length(); i++) {
1142 Object other(&scope, starargs.at(i));
1143 result = setUpdate(thread, self, other);
1144 if (result.isError()) {
1145 return *result;
1146 }
1147 }
1148 return NoneType::object();
1149}
1150
1151static const BuiltinAttribute kSetIteratorAttributes[] = {
1152 {ID(_set_iterator__iterable), RawSetIterator::kIterableOffset,
1153 AttributeFlags::kHidden},
1154 {ID(_set_iterator__index), RawSetIterator::kIndexOffset,
1155 AttributeFlags::kHidden},
1156 {ID(_set_iterator__consumed_count), RawSetIterator::kConsumedCountOffset,
1157 AttributeFlags::kHidden},
1158};
1159
1160RawObject METH(set_iterator, __iter__)(Thread* thread, Arguments args) {
1161 HandleScope scope(thread);
1162 Object self(&scope, args.get(0));
1163 if (!self.isSetIterator()) {
1164 return thread->raiseRequiresType(self, ID(set_iterator));
1165 }
1166 return *self;
1167}
1168
1169RawObject METH(set_iterator, __next__)(Thread* thread, Arguments args) {
1170 HandleScope scope(thread);
1171 Object self_obj(&scope, args.get(0));
1172 if (!self_obj.isSetIterator()) {
1173 return thread->raiseRequiresType(self_obj, ID(set_iterator));
1174 }
1175 SetIterator self(&scope, *self_obj);
1176 Object value(&scope, setIteratorNext(thread, self));
1177 if (value.isError()) {
1178 return thread->raise(LayoutId::kStopIteration, NoneType::object());
1179 }
1180 return *value;
1181}
1182
1183RawObject METH(set_iterator, __length_hint__)(Thread* thread, Arguments args) {
1184 HandleScope scope(thread);
1185 Object self(&scope, args.get(0));
1186 if (!self.isSetIterator()) {
1187 return thread->raiseRequiresType(self, ID(set_iterator));
1188 }
1189 SetIterator set_iterator(&scope, *self);
1190 Set set(&scope, set_iterator.iterable());
1191 return SmallInt::fromWord(set.numItems() - set_iterator.consumedCount());
1192}
1193
1194void initializeSetTypes(Thread* thread) {
1195 addBuiltinType(thread, ID(set), LayoutId::kSet,
1196 /*superclass_id=*/LayoutId::kObject, kSetAttributes,
1197 Set::kSize, /*basetype=*/true);
1198
1199 addBuiltinType(thread, ID(frozenset), LayoutId::kFrozenSet,
1200 /*superclass_id=*/LayoutId::kObject, kFrozenSetAttributes,
1201 FrozenSet::kSize, /*basetype=*/true);
1202
1203 addBuiltinType(thread, ID(set_iterator), LayoutId::kSetIterator,
1204 /*superclass_id=*/LayoutId::kObject, kSetIteratorAttributes,
1205 SetIterator::kSize, /*basetype=*/false);
1206}
1207
1208} // namespace py