bernsteinbear.com
this repo has no description
1// Copyright (c) Facebook, Inc. and its affiliates. (http://www.facebook.com)
2#include "attributedict.h"
3
4#include "runtime.h"
5#include "thread.h"
6#include "type-builtins.h"
7
8namespace py {
9
10const word kInitialCapacity = 16;
11
12static NEVER_INLINE void attributeGrow(Thread* thread,
13 const AttributeDict& attrs) {
14 HandleScope scope(thread);
15 Tuple old_data(&scope, attrs.attributes());
16
17 // Count the number of filled buckets that are not tombstones.
18 word old_capacity = old_data.length();
19 word num_items = 0;
20 for (word idx = 0; idx < old_capacity; idx += kAttributeBucketNumWords) {
21 RawObject key = old_data.at(idx + kAttributeBucketKeyOffset);
22 if (key != kAttributeDictEmptyKey && key != kAttributeDictTombstoneKey) {
23 num_items++;
24 }
25 }
26
27 // Grow if more than half of the buckets are filled, otherwise maintain size
28 // and just clean out the tombstones.
29 word old_num_buckets = old_capacity >> 1;
30 word new_capacity = old_capacity;
31 if (num_items > (old_num_buckets >> 1)) {
32 // Grow if more than half of the buckets are filled, otherwise just clean
33 // out the tombstones.
34 new_capacity *= 2;
35 }
36
37 // Allocate new tuple and re-hash.
38 MutableTuple new_data(&scope,
39 thread->runtime()->newMutableTuple(new_capacity));
40 word num_buckets = new_capacity >> 1;
41 DCHECK(Utils::isPowerOfTwo(num_buckets), "must be power of two");
42 word new_remaining = (num_buckets * 2) / 3;
43 word mask = num_buckets - 1;
44 Object key(&scope, NoneType::object());
45 for (word old_idx = 0; old_idx < old_capacity;
46 old_idx += kAttributeBucketNumWords) {
47 key = old_data.at(old_idx + kAttributeBucketKeyOffset);
48 if (key == kAttributeDictEmptyKey || key == kAttributeDictTombstoneKey) {
49 continue;
50 }
51 DCHECK(key.isStr(), "key must be None, _Unbound or str");
52 word hash = internedStrHash(*key);
53 word bucket = hash & mask;
54 word num_probes = 0;
55 while (new_data.at(bucket * kAttributeBucketNumWords +
56 kAttributeBucketKeyOffset) != kAttributeDictEmptyKey) {
57 num_probes++;
58 bucket = (bucket + num_probes) & mask;
59 }
60 new_data.atPut(
61 bucket * kAttributeBucketNumWords + kAttributeBucketKeyOffset, *key);
62 new_data.atPut(
63 bucket * kAttributeBucketNumWords + kAttributeBucketValueOffset,
64 old_data.at(old_idx + kAttributeBucketValueOffset));
65 new_remaining--;
66 }
67 DCHECK(new_remaining > 0, "must have remaining buckets");
68 attrs.setAttributes(*new_data);
69 attrs.setAttributesRemaining(new_remaining);
70}
71
72void attributeDictInit(Thread* thread, const AttributeDict& attrs) {
73 attrs.setAttributes(thread->runtime()->newMutableTuple(kInitialCapacity));
74 word num_buckets = kInitialCapacity >> 1;
75 attrs.setAttributesRemaining((num_buckets * 2) / 3);
76}
77
78RawObject attributeKeys(Thread* thread, const AttributeDict& attrs) {
79 HandleScope scope(thread);
80 MutableTuple data(&scope, attrs.attributes());
81 Runtime* runtime = thread->runtime();
82 List keys(&scope, runtime->newList());
83 Object key(&scope, NoneType::object());
84 Object cell(&scope, NoneType::object());
85 for (word i = 0, length = data.length(); i < length;
86 i += kAttributeBucketNumWords) {
87 key = data.at(i + kAttributeBucketKeyOffset);
88 if (key == kAttributeDictEmptyKey || key == kAttributeDictTombstoneKey) {
89 continue;
90 }
91 DCHECK(key.isStr(), "key must be a str");
92 cell = data.at(i + kAttributeBucketValueOffset);
93 if (ValueCell::cast(*cell).isPlaceholder()) {
94 continue;
95 }
96 runtime->listAdd(thread, keys, key);
97 }
98 return *keys;
99}
100
101word attributeLen(Thread* thread, const AttributeDict& attrs) {
102 HandleScope scope(thread);
103 MutableTuple data(&scope, attrs.attributes());
104 Object key(&scope, NoneType::object());
105 Object cell(&scope, NoneType::object());
106 word count = 0;
107 for (word i = 0, length = data.length(); i < length;
108 i += kAttributeBucketNumWords) {
109 key = data.at(i + kAttributeBucketKeyOffset);
110 if (key == kAttributeDictEmptyKey || key == kAttributeDictTombstoneKey) {
111 continue;
112 }
113 DCHECK(key.isStr(), "key must be a str");
114 cell = data.at(i + kAttributeBucketValueOffset);
115 if (ValueCell::cast(*cell).isPlaceholder()) {
116 continue;
117 }
118 count++;
119 }
120 return count;
121}
122
123RawObject attributeName(Thread* thread, const Object& name_obj) {
124 if (name_obj.isSmallStr()) {
125 return *name_obj;
126 }
127 if (name_obj.isLargeStr()) {
128 return Runtime::internLargeStr(thread, name_obj);
129 }
130
131 Runtime* runtime = thread->runtime();
132 if (!runtime->isInstanceOfStr(*name_obj)) {
133 return thread->raiseWithFmt(LayoutId::kTypeError,
134 "attribute name must be string, not '%T'",
135 &name_obj);
136 }
137 HandleScope scope(thread);
138 Type type(&scope, runtime->typeOf(*name_obj));
139 if (typeLookupInMroById(thread, *type, ID(__eq__)) !=
140 runtime->strDunderEq() ||
141 typeLookupInMroById(thread, *type, ID(__hash__)) !=
142 runtime->strDunderHash()) {
143 UNIMPLEMENTED(
144 "str subclasses with __eq__ or __hash__ not supported as attribute "
145 "name");
146 }
147 Str name_str(&scope, strUnderlying(*name_obj));
148 return Runtime::internStr(thread, name_str);
149}
150
151RawObject attributeNameNoException(Thread* thread, const Object& name_obj) {
152 if (name_obj.isSmallStr()) {
153 return *name_obj;
154 }
155 if (name_obj.isLargeStr()) {
156 return Runtime::internLargeStr(thread, name_obj);
157 }
158
159 Runtime* runtime = thread->runtime();
160 if (!runtime->isInstanceOfStr(*name_obj)) {
161 return Error::error();
162 }
163 HandleScope scope(thread);
164 Type type(&scope, runtime->typeOf(*name_obj));
165 if (typeLookupInMroById(thread, *type, ID(__eq__)) !=
166 runtime->strDunderEq() ||
167 typeLookupInMroById(thread, *type, ID(__hash__)) !=
168 runtime->strDunderHash()) {
169 UNIMPLEMENTED(
170 "str subclasses with __eq__ or __hash__ not supported as attribute "
171 "name");
172 }
173 Str name_str(&scope, strUnderlying(*name_obj));
174 return Runtime::internStr(thread, name_str);
175}
176
177bool attributeFindForRemoval(const AttributeDict& attrs, const Object& name,
178 Object* value_cell_out, word* index_out) {
179 RawMutableTuple data = MutableTuple::cast(attrs.attributes());
180 word hash = internedStrHash(*name);
181 word mask = (data.length() - 1) >> 1;
182 for (word bucket = hash & mask, num_probes = 0;;
183 bucket = (bucket + ++num_probes) & mask) {
184 word index = bucket * kAttributeBucketNumWords;
185 RawObject key = data.at(index + kAttributeBucketKeyOffset);
186 if (key == *name) {
187 *value_cell_out = data.at(index + kAttributeBucketValueOffset);
188 *index_out = index;
189 return true;
190 }
191 if (key == kAttributeDictEmptyKey) {
192 return false;
193 }
194 // Remaining cases are either a key that does not match or tombstone.
195 }
196}
197
198void attributeRemove(const AttributeDict& attrs, word index) {
199 RawMutableTuple data = MutableTuple::cast(attrs.attributes());
200 data.atPut(index + kAttributeBucketKeyOffset, kAttributeDictTombstoneKey);
201 data.atPut(index + kAttributeBucketValueOffset, NoneType::object());
202}
203
204RawObject inline USED attributeValueCellAtPut(Thread* thread,
205 const AttributeDict& attrs,
206 const Object& name) {
207 HandleScope scope(thread);
208 MutableTuple data_obj(&scope, attrs.attributes());
209 RawMutableTuple data = *data_obj;
210 word hash = internedStrHash(*name);
211 word mask = (data.length() - 1) >> 1;
212 for (word bucket = hash & mask, num_probes = 0, last_tombstone = -1;;
213 bucket = (bucket + ++num_probes) & mask) {
214 word idx = bucket * kAttributeBucketNumWords;
215 RawObject key = data.at(idx + kAttributeBucketKeyOffset);
216 if (key == *name) {
217 return RawValueCell::cast(data.at(idx + kAttributeBucketValueOffset));
218 }
219 if (key == kAttributeDictEmptyKey) {
220 DCHECK(Runtime::isInternedStr(thread, name), "expected interned str");
221 RawValueCell cell = ValueCell::cast(thread->runtime()->newValueCell());
222 cell.makePlaceholder();
223 // newValueCell() may have triggered a GC; restore raw references.
224 data = *data_obj;
225 if (last_tombstone >= 0) {
226 // Overwrite an existing tombstone entry.
227 word last_tombstone_idx = last_tombstone * kAttributeBucketNumWords;
228 data.atPut(last_tombstone_idx + kAttributeBucketKeyOffset, *name);
229 data.atPut(last_tombstone_idx + kAttributeBucketValueOffset, cell);
230 } else {
231 // Use new bucket.
232 data.atPut(idx + kAttributeBucketKeyOffset, *name);
233 data.atPut(idx + kAttributeBucketValueOffset, cell);
234 word remaining = attrs.attributesRemaining() - 1;
235 attrs.setAttributesRemaining(remaining);
236 if (remaining == 0) {
237 ValueCell cell_obj(&scope, cell);
238 attributeGrow(thread, attrs);
239 return *cell_obj;
240 }
241 }
242 return cell;
243 }
244 if (key == kAttributeDictTombstoneKey) {
245 last_tombstone = bucket;
246 }
247 }
248}
249
250bool attributeValueCellAt(RawAttributeDict attrs, RawObject name,
251 RawObject* result_out) {
252 word hash = internedStrHash(name);
253 return attributeValueCellAtWithHash(attrs, name, hash, result_out);
254}
255
256RawObject attributeValues(Thread* thread, const AttributeDict& attrs) {
257 HandleScope scope(thread);
258 MutableTuple data(&scope, attrs.attributes());
259 Runtime* runtime = thread->runtime();
260 List values(&scope, runtime->newList());
261 Object key(&scope, NoneType::object());
262 Object value(&scope, NoneType::object());
263 for (word i = 0, length = data.length(); i < length;
264 i += kAttributeBucketNumWords) {
265 key = data.at(i + kAttributeBucketKeyOffset);
266 if (key == kAttributeDictEmptyKey || key == kAttributeDictTombstoneKey) {
267 continue;
268 }
269 DCHECK(key.isStr(), "key must be a str");
270 value = data.at(i + kAttributeBucketValueOffset);
271 if (ValueCell::cast(*value).isPlaceholder()) {
272 continue;
273 }
274 value = ValueCell::cast(*value).value();
275 runtime->listAdd(thread, values, value);
276 }
277 return *values;
278}
279
280} // namespace py