1 | // Copyright (C) 2016 The Qt Company Ltd. |
2 | // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only |
3 | #include "qv4arraydata_p.h" |
4 | #include "qv4object_p.h" |
5 | #include "qv4functionobject_p.h" |
6 | #include <private/qv4mm_p.h> |
7 | #include "qv4runtime_p.h" |
8 | #include "qv4argumentsobject_p.h" |
9 | #include "qv4string_p.h" |
10 | #include "qv4jscall_p.h" |
11 | |
12 | using namespace QV4; |
13 | |
14 | DEFINE_MANAGED_VTABLE(ArrayData); |
15 | |
16 | const ArrayVTable SimpleArrayData::static_vtbl = |
17 | { |
18 | DEFINE_MANAGED_VTABLE_INT(SimpleArrayData, nullptr), |
19 | .type: Heap::ArrayData::Simple, |
20 | .reallocate: SimpleArrayData::reallocate, |
21 | .get: SimpleArrayData::get, |
22 | .put: SimpleArrayData::put, |
23 | .putArray: SimpleArrayData::putArray, |
24 | .del: SimpleArrayData::del, |
25 | .setAttribute: SimpleArrayData::setAttribute, |
26 | .push_front: SimpleArrayData::push_front, |
27 | .pop_front: SimpleArrayData::pop_front, |
28 | .truncate: SimpleArrayData::truncate, |
29 | .length: SimpleArrayData::length |
30 | }; |
31 | |
32 | const ArrayVTable SparseArrayData::static_vtbl = |
33 | { |
34 | DEFINE_MANAGED_VTABLE_INT(SparseArrayData, nullptr), |
35 | .type: Heap::ArrayData::Sparse, |
36 | .reallocate: SparseArrayData::reallocate, |
37 | .get: SparseArrayData::get, |
38 | .put: SparseArrayData::put, |
39 | .putArray: SparseArrayData::putArray, |
40 | .del: SparseArrayData::del, |
41 | .setAttribute: SparseArrayData::setAttribute, |
42 | .push_front: SparseArrayData::push_front, |
43 | .pop_front: SparseArrayData::pop_front, |
44 | .truncate: SparseArrayData::truncate, |
45 | .length: SparseArrayData::length |
46 | }; |
47 | |
48 | Q_STATIC_ASSERT(sizeof(Heap::ArrayData) == sizeof(Heap::SimpleArrayData)); |
49 | Q_STATIC_ASSERT(sizeof(Heap::ArrayData) == sizeof(Heap::SparseArrayData)); |
50 | |
51 | void Heap::ArrayData::markObjects(Heap::Base *base, MarkStack *stack) |
52 | { |
53 | ArrayData *a = static_cast<ArrayData *>(base); |
54 | a->values.mark(markStack: stack); |
55 | } |
56 | |
57 | |
58 | void ArrayData::realloc(Object *o, Type newType, uint requested, bool enforceAttributes) |
59 | { |
60 | Scope scope(o->engine()); |
61 | Scoped<ArrayData> d(scope, o->arrayData()); |
62 | |
63 | uint alloc = 8; |
64 | uint toCopy = 0; |
65 | uint offset = 0; |
66 | |
67 | if (d) { |
68 | bool hasAttrs = d->attrs(); |
69 | enforceAttributes |= hasAttrs; |
70 | |
71 | if (requested <= d->alloc() && newType == d->type() && hasAttrs == enforceAttributes) |
72 | return; |
73 | if (alloc < d->alloc()) |
74 | alloc = d->alloc(); |
75 | |
76 | if (d->type() < Heap::ArrayData::Sparse) { |
77 | offset = d->d()->offset; |
78 | toCopy = d->d()->values.size; |
79 | } else { |
80 | toCopy = d->alloc(); |
81 | } |
82 | if (d->type() > newType) |
83 | newType = d->type(); |
84 | } |
85 | |
86 | while (alloc < requested) |
87 | alloc *= 2; |
88 | size_t size = sizeof(Heap::ArrayData) + (alloc - 1)*sizeof(Value); |
89 | if (enforceAttributes) |
90 | size += alloc*sizeof(PropertyAttributes); |
91 | |
92 | Scoped<ArrayData> newData(scope); |
93 | if (newType < Heap::ArrayData::Sparse) { |
94 | Heap::SimpleArrayData *n = scope.engine->memoryManager->allocManaged<SimpleArrayData>(size); |
95 | n->init(); |
96 | n->offset = 0; |
97 | n->values.size = d ? d->d()->values.size : 0; |
98 | newData = n; |
99 | } else { |
100 | Heap::SparseArrayData *n = scope.engine->memoryManager->allocManaged<SparseArrayData>(size); |
101 | n->init(); |
102 | newData = n; |
103 | } |
104 | newData->setAlloc(alloc); |
105 | newData->setType(newType); |
106 | newData->setAttrs(enforceAttributes ? reinterpret_cast<PropertyAttributes *>(newData->d()->values.values + alloc) : nullptr); |
107 | o->setArrayData(newData); |
108 | |
109 | if (d) { |
110 | if (enforceAttributes) { |
111 | if (d->attrs()) |
112 | memcpy(dest: newData->attrs(), src: d->attrs(), n: sizeof(PropertyAttributes)*toCopy); |
113 | else |
114 | for (uint i = 0; i < toCopy; ++i) |
115 | newData->attrs()[i] = Attr_Data; |
116 | } |
117 | |
118 | if (toCopy > d->d()->values.alloc - offset) { |
119 | uint copyFromStart = toCopy - (d->d()->values.alloc - offset); |
120 | // no write barrier required here |
121 | memcpy(dest: newData->d()->values.values + toCopy - copyFromStart, src: d->d()->values.values, n: sizeof(Value)*copyFromStart); |
122 | toCopy -= copyFromStart; |
123 | } |
124 | // no write barrier required here |
125 | memcpy(dest: newData->d()->values.values, src: d->d()->values.values + offset, n: sizeof(Value)*toCopy); |
126 | } |
127 | |
128 | if (newType != Heap::ArrayData::Sparse) |
129 | return; |
130 | |
131 | Heap::SparseArrayData *sparse = static_cast<Heap::SparseArrayData *>(newData->d()); |
132 | |
133 | Value *lastFree; |
134 | if (d && d->type() == Heap::ArrayData::Sparse) { |
135 | Heap::SparseArrayData *old = static_cast<Heap::SparseArrayData *>(d->d()); |
136 | sparse->sparse = old->sparse; |
137 | old->sparse = nullptr; |
138 | lastFree = &sparse->sparse->freeList; |
139 | } else { |
140 | sparse->sparse = new SparseArray; |
141 | lastFree = &sparse->sparse->freeList; |
142 | *lastFree = Encode(0); |
143 | for (uint i = 0; i < toCopy; ++i) { |
144 | if (!sparse->values[i].isEmpty()) { |
145 | SparseArrayNode *n = sparse->sparse->insert(akey: i); |
146 | n->value = i; |
147 | } else { |
148 | *lastFree = Encode(i); |
149 | sparse->values.values[i].setEmpty(); |
150 | lastFree = &sparse->values.values[i]; |
151 | } |
152 | } |
153 | } |
154 | |
155 | if (toCopy < sparse->values.alloc) { |
156 | for (uint i = toCopy; i < sparse->values.alloc; ++i) { |
157 | *lastFree = Encode(i); |
158 | sparse->values.values[i].setEmpty(); |
159 | lastFree = &sparse->values.values[i]; |
160 | } |
161 | } |
162 | *lastFree = Encode(-1); |
163 | |
164 | Q_ASSERT(sparse->sparse->freeList.isInteger()); |
165 | // ### Could explicitly free the old data |
166 | } |
167 | |
168 | Heap::ArrayData *SimpleArrayData::reallocate(Object *o, uint n, bool enforceAttributes) |
169 | { |
170 | realloc(o, newType: Heap::ArrayData::Simple, requested: n, enforceAttributes); |
171 | return o->arrayData(); |
172 | } |
173 | |
174 | void ArrayData::ensureAttributes(Object *o) |
175 | { |
176 | if (o->arrayData() && o->arrayData()->attrs) |
177 | return; |
178 | |
179 | ArrayData::realloc(o, newType: Heap::ArrayData::Simple, requested: 0, enforceAttributes: true); |
180 | } |
181 | |
182 | ReturnedValue SimpleArrayData::get(const Heap::ArrayData *d, uint index) |
183 | { |
184 | const Heap::SimpleArrayData *dd = static_cast<const Heap::SimpleArrayData *>(d); |
185 | if (index >= dd->values.size) |
186 | return Value::emptyValue().asReturnedValue(); |
187 | return dd->data(index).asReturnedValue(); |
188 | } |
189 | |
190 | bool SimpleArrayData::put(Object *o, uint index, const Value &value) |
191 | { |
192 | Heap::SimpleArrayData *dd = o->d()->arrayData.cast<Heap::SimpleArrayData>(); |
193 | Q_ASSERT(index >= dd->values.size || !dd->attrs || !dd->attrs[index].isAccessor()); |
194 | // ### honour attributes |
195 | dd->setData(e: o->engine(), index, newVal: value); |
196 | if (index >= dd->values.size) { |
197 | if (dd->attrs) |
198 | dd->attrs[index] = Attr_Data; |
199 | dd->values.size = index + 1; |
200 | } |
201 | return true; |
202 | } |
203 | |
204 | bool SimpleArrayData::del(Object *o, uint index) |
205 | { |
206 | Heap::SimpleArrayData *dd = o->d()->arrayData.cast<Heap::SimpleArrayData>(); |
207 | if (index >= dd->values.size) |
208 | return true; |
209 | |
210 | if (!dd->attrs || dd->attrs[index].isConfigurable()) { |
211 | dd->setData(e: o->engine(), index, newVal: Value::emptyValue()); |
212 | if (dd->attrs) |
213 | dd->attrs[index] = Attr_Data; |
214 | return true; |
215 | } |
216 | if (dd->data(index).isEmpty()) |
217 | return true; |
218 | return false; |
219 | } |
220 | |
221 | void SimpleArrayData::setAttribute(Object *o, uint index, PropertyAttributes attrs) |
222 | { |
223 | o->arrayData()->attrs[index] = attrs; |
224 | } |
225 | |
226 | void SimpleArrayData::push_front(Object *o, const Value *values, uint n) |
227 | { |
228 | Heap::SimpleArrayData *dd = o->d()->arrayData.cast<Heap::SimpleArrayData>(); |
229 | Q_ASSERT(!dd->attrs); |
230 | if (dd->values.size + n > dd->values.alloc) { |
231 | realloc(o, newType: Heap::ArrayData::Simple, requested: dd->values.size + n, enforceAttributes: false); |
232 | Q_ASSERT(o->d()->arrayData->type == Heap::ArrayData::Simple); |
233 | dd = o->d()->arrayData.cast<Heap::SimpleArrayData>(); |
234 | } |
235 | if (n <= dd->offset) { |
236 | dd->offset -= n; // there is enough space left in front |
237 | } else { |
238 | // we need to wrap around, so: |
239 | dd->offset = dd->values.alloc - // start at the back, but subtract: |
240 | (n - dd->offset); // the number of items we can put in the free space at the start of the allocated array |
241 | } |
242 | dd->values.size += n; |
243 | for (uint i = 0; i < n; ++i) |
244 | dd->setData(e: o->engine(), index: i, newVal: values[i]); |
245 | } |
246 | |
247 | ReturnedValue SimpleArrayData::pop_front(Object *o) |
248 | { |
249 | Heap::SimpleArrayData *dd = o->d()->arrayData.cast<Heap::SimpleArrayData>(); |
250 | Q_ASSERT(!dd->attrs); |
251 | if (!dd->values.size) |
252 | return Encode::undefined(); |
253 | |
254 | ReturnedValue v = dd->data(index: 0).isEmpty() ? Encode::undefined() : dd->data(index: 0).asReturnedValue(); |
255 | dd->offset = (dd->offset + 1) % dd->values.alloc; |
256 | --dd->values.size; |
257 | return v; |
258 | } |
259 | |
260 | uint SimpleArrayData::truncate(Object *o, uint newLen) |
261 | { |
262 | Heap::SimpleArrayData *dd = o->d()->arrayData.cast<Heap::SimpleArrayData>(); |
263 | if (dd->values.size < newLen) |
264 | return newLen; |
265 | |
266 | if (!dd->attrs) { |
267 | dd->values.size = newLen; |
268 | return newLen; |
269 | } |
270 | |
271 | while (dd->values.size > newLen) { |
272 | if (!dd->data(index: dd->values.size - 1).isEmpty() && !dd->attrs[dd->values.size - 1].isConfigurable()) |
273 | return dd->values.size; |
274 | --dd->values.size; |
275 | } |
276 | return dd->values.size; |
277 | } |
278 | |
279 | uint SimpleArrayData::length(const Heap::ArrayData *d) |
280 | { |
281 | return d->values.size; |
282 | } |
283 | |
284 | bool SimpleArrayData::putArray(Object *o, uint index, const Value *values, uint n) |
285 | { |
286 | Heap::SimpleArrayData *dd = o->d()->arrayData.cast<Heap::SimpleArrayData>(); |
287 | if (index + n > dd->values.alloc) { |
288 | reallocate(o, n: index + n + 1, enforceAttributes: false); |
289 | dd = o->d()->arrayData.cast<Heap::SimpleArrayData>(); |
290 | } |
291 | QV4::ExecutionEngine *e = o->engine(); |
292 | for (uint i = dd->values.size; i < index; ++i) |
293 | dd->setData(e, index: i, newVal: Value::emptyValue()); |
294 | for (uint i = 0; i < n; ++i) |
295 | dd->setData(e, index: index + i, newVal: values[i]); |
296 | dd->values.size = qMax(a: dd->values.size, b: index + n); |
297 | return true; |
298 | } |
299 | |
300 | void SparseArrayData::free(Heap::ArrayData *d, uint idx) |
301 | { |
302 | Q_ASSERT(d && d->type == Heap::ArrayData::Sparse); |
303 | Value *v = d->values.values + idx; |
304 | if (d->attrs && d->attrs[idx].isAccessor()) { |
305 | // double slot, free both. Order is important, so we have a double slot for allocation again afterwards. |
306 | v[1] = d->sparse->freeList; |
307 | v[0] = Encode(idx + 1); |
308 | } else { |
309 | *v = d->sparse->freeList; |
310 | } |
311 | d->sparse->freeList = Encode(idx); |
312 | if (d->attrs) |
313 | d->attrs[idx].clear(); |
314 | } |
315 | |
316 | Heap::ArrayData *SparseArrayData::reallocate(Object *o, uint n, bool enforceAttributes) |
317 | { |
318 | realloc(o, newType: Heap::ArrayData::Sparse, requested: n, enforceAttributes); |
319 | return o->arrayData(); |
320 | } |
321 | |
322 | // double slots are required for accessor properties |
323 | uint SparseArrayData::allocate(Object *o, bool doubleSlot) |
324 | { |
325 | Q_ASSERT(o->d()->arrayData->type == Heap::ArrayData::Sparse); |
326 | Heap::SimpleArrayData *dd = o->d()->arrayData.cast<Heap::SimpleArrayData>(); |
327 | if (doubleSlot) { |
328 | Value *last = &dd->sparse->freeList; |
329 | while (1) { |
330 | if (last->int_32() == -1) { |
331 | reallocate(o, n: dd->values.alloc + 2, enforceAttributes: true); |
332 | dd = o->d()->arrayData.cast<Heap::SimpleArrayData>(); |
333 | last = &dd->sparse->freeList; |
334 | Q_ASSERT(last->int_32() != -1); |
335 | } |
336 | |
337 | Q_ASSERT(dd->values[static_cast<uint>(last->int_32())].int_32() != last->int_32()); |
338 | if (dd->values[static_cast<uint>(last->int_32())].int_32() == last->int_32() + 1) { |
339 | // found two slots in a row |
340 | uint idx = static_cast<uint>(last->int_32()); |
341 | *last = Encode(dd->values[static_cast<uint>(last->int_32()) + 1].int_32()); |
342 | dd->attrs[idx] = Attr_Accessor; |
343 | return idx; |
344 | } |
345 | last = &dd->values.values[last->int_32()]; |
346 | } |
347 | } else { |
348 | if (dd->sparse->freeList.int_32() == -1) { |
349 | reallocate(o, n: dd->values.alloc + 1, enforceAttributes: false); |
350 | dd = o->d()->arrayData.cast<Heap::SimpleArrayData>(); |
351 | } |
352 | Q_ASSERT(dd->sparse->freeList.int_32() != -1); |
353 | uint idx = static_cast<uint>(dd->sparse->freeList.int_32()); |
354 | dd->sparse->freeList = dd->values[idx]; |
355 | Q_ASSERT(dd->sparse->freeList.isInteger()); |
356 | if (dd->attrs) |
357 | dd->attrs[idx] = Attr_Data; |
358 | return idx; |
359 | } |
360 | } |
361 | |
362 | ReturnedValue SparseArrayData::get(const Heap::ArrayData *d, uint index) |
363 | { |
364 | const Heap::SparseArrayData *s = static_cast<const Heap::SparseArrayData *>(d); |
365 | index = s->mappedIndex(index); |
366 | if (index == UINT_MAX) |
367 | return Value::emptyValue().asReturnedValue(); |
368 | return s->values[index].asReturnedValue(); |
369 | } |
370 | |
371 | bool SparseArrayData::put(Object *o, uint index, const Value &value) |
372 | { |
373 | if (value.isEmpty()) |
374 | return true; |
375 | |
376 | Heap::SparseArrayData *s = o->d()->arrayData.cast<Heap::SparseArrayData>(); |
377 | SparseArrayNode *n = s->sparse->insert(akey: index); |
378 | Q_ASSERT(n->value == UINT_MAX || !s->attrs || !s->attrs[n->value].isAccessor()); |
379 | if (n->value == UINT_MAX) |
380 | n->value = allocate(o); |
381 | s = o->d()->arrayData.cast<Heap::SparseArrayData>(); |
382 | s->setArrayData(e: o->engine(), index: n->value, newVal: value); |
383 | if (s->attrs) |
384 | s->attrs[n->value] = Attr_Data; |
385 | return true; |
386 | } |
387 | |
388 | bool SparseArrayData::del(Object *o, uint index) |
389 | { |
390 | Heap::SparseArrayData *dd = o->d()->arrayData.cast<Heap::SparseArrayData>(); |
391 | |
392 | SparseArrayNode *n = dd->sparse->findNode(akey: index); |
393 | if (!n) |
394 | return true; |
395 | |
396 | uint pidx = n->value; |
397 | Q_ASSERT(!dd->values[pidx].isEmpty()); |
398 | |
399 | bool isAccessor = false; |
400 | if (dd->attrs) { |
401 | if (!dd->attrs[pidx].isConfigurable()) |
402 | return false; |
403 | |
404 | isAccessor = dd->attrs[pidx].isAccessor(); |
405 | dd->attrs[pidx] = Attr_Data; |
406 | } |
407 | |
408 | if (isAccessor) { |
409 | // free up both indices |
410 | dd->values.values[pidx + 1] = dd->sparse->freeList; |
411 | dd->values.values[pidx] = Encode(pidx + 1); |
412 | } else { |
413 | Q_ASSERT(dd->type == Heap::ArrayData::Sparse); |
414 | dd->values.values[pidx] = dd->sparse->freeList; |
415 | } |
416 | |
417 | dd->sparse->freeList = Encode(pidx); |
418 | dd->sparse->erase(n); |
419 | return true; |
420 | } |
421 | |
422 | void SparseArrayData::setAttribute(Object *o, uint index, PropertyAttributes attrs) |
423 | { |
424 | Heap::SparseArrayData *d = o->d()->arrayData.cast<Heap::SparseArrayData>(); |
425 | SparseArrayNode *n = d->sparse->insert(akey: index); |
426 | if (n->value == UINT_MAX) { |
427 | n->value = allocate(o, doubleSlot: attrs.isAccessor()); |
428 | d = o->d()->arrayData.cast<Heap::SparseArrayData>(); |
429 | } |
430 | else if (attrs.isAccessor() != d->attrs[n->value].isAccessor()) { |
431 | // need to convert the slot |
432 | free(d: o->arrayData(), idx: n->value); |
433 | n->value = allocate(o, doubleSlot: attrs.isAccessor()); |
434 | d = o->d()->arrayData.cast<Heap::SparseArrayData>(); |
435 | } |
436 | d->attrs[n->value] = attrs; |
437 | } |
438 | |
439 | void SparseArrayData::push_front(Object *o, const Value *values, uint n) |
440 | { |
441 | Heap::SparseArrayData *d = o->d()->arrayData.cast<Heap::SparseArrayData>(); |
442 | Q_ASSERT(!d->attrs); |
443 | for (int i = static_cast<int>(n) - 1; i >= 0; --i) { |
444 | uint idx = allocate(o); |
445 | d = o->d()->arrayData.cast<Heap::SparseArrayData>(); |
446 | d->setArrayData(e: o->engine(), index: idx, newVal: values[i]); |
447 | d->sparse->push_front(value: idx); |
448 | } |
449 | } |
450 | |
451 | ReturnedValue SparseArrayData::pop_front(Object *o) |
452 | { |
453 | Heap::SparseArrayData *d = o->d()->arrayData.cast<Heap::SparseArrayData>(); |
454 | Q_ASSERT(!d->attrs); |
455 | uint idx = d->sparse->pop_front(); |
456 | ReturnedValue v; |
457 | if (idx != UINT_MAX) { |
458 | v = d->values[idx].asReturnedValue(); |
459 | free(d: o->arrayData(), idx); |
460 | } else { |
461 | v = Encode::undefined(); |
462 | } |
463 | return v; |
464 | } |
465 | |
466 | uint SparseArrayData::truncate(Object *o, uint newLen) |
467 | { |
468 | Heap::SparseArrayData *d = o->d()->arrayData.cast<Heap::SparseArrayData>(); |
469 | SparseArrayNode *begin = d->sparse->lowerBound(akey: newLen); |
470 | if (begin != d->sparse->end()) { |
471 | SparseArrayNode *it = d->sparse->end()->previousNode(); |
472 | while (1) { |
473 | if (d->attrs) { |
474 | if (!d->attrs[it->value].isConfigurable()) { |
475 | newLen = it->key() + 1; |
476 | break; |
477 | } |
478 | } |
479 | free(d: o->arrayData(), idx: it->value); |
480 | bool brk = (it == begin); |
481 | SparseArrayNode *prev = it->previousNode(); |
482 | d->sparse->erase(n: it); |
483 | if (brk) |
484 | break; |
485 | it = prev; |
486 | } |
487 | } |
488 | return newLen; |
489 | } |
490 | |
491 | uint SparseArrayData::length(const Heap::ArrayData *d) |
492 | { |
493 | const Heap::SparseArrayData *dd = static_cast<const Heap::SparseArrayData *>(d); |
494 | if (!dd->sparse) |
495 | return 0; |
496 | SparseArrayNode *n = dd->sparse->end(); |
497 | n = n->previousNode(); |
498 | return n ? n->key() + 1 : 0; |
499 | } |
500 | |
501 | bool SparseArrayData::putArray(Object *o, uint index, const Value *values, uint n) |
502 | { |
503 | for (uint i = 0; i < n; ++i) |
504 | put(o, index: index + i, value: values[i]); |
505 | return true; |
506 | } |
507 | |
508 | |
509 | uint ArrayData::append(Object *obj, ArrayObject *otherObj, uint n) |
510 | { |
511 | Q_ASSERT(!obj->d()->arrayData || !obj->d()->arrayData->attrs); |
512 | |
513 | if (!n) |
514 | return obj->getLength(); |
515 | |
516 | Scope scope(obj->engine()); |
517 | Scoped<ArrayData> other(scope, otherObj->arrayData()); |
518 | |
519 | if (other && other->isSparse()) |
520 | obj->initSparseArray(); |
521 | else |
522 | obj->arrayCreate(); |
523 | |
524 | uint oldSize = obj->getLength(); |
525 | |
526 | if (!other || ArgumentsObject::isNonStrictArgumentsObject(m: otherObj)) { |
527 | ScopedValue v(scope); |
528 | for (uint i = 0; i < n; ++i) |
529 | obj->arraySet(index: oldSize + i, value: (v = otherObj->get(idx: i))); |
530 | } else if (other->isSparse()) { |
531 | Heap::SparseArrayData *os = static_cast<Heap::SparseArrayData *>(other->d()); |
532 | if (other->hasAttributes()) { |
533 | ScopedValue v(scope); |
534 | for (const SparseArrayNode *it = os->sparse->begin(); |
535 | it != os->sparse->end(); it = it->nextNode()) { |
536 | v = otherObj->getValue(v: os->values[it->value], attrs: other->d()->attrs[it->value]); |
537 | obj->arraySet(index: oldSize + it->key(), value: v); |
538 | } |
539 | } else { |
540 | for (const SparseArrayNode *it = other->d()->sparse->begin(); |
541 | it != os->sparse->end(); it = it->nextNode()) |
542 | obj->arraySet(index: oldSize + it->key(), value: os->values[it->value]); |
543 | } |
544 | } else { |
545 | Heap::SimpleArrayData *os = static_cast<Heap::SimpleArrayData *>(other->d()); |
546 | uint toCopy = n; |
547 | uint chunk = toCopy; |
548 | if (chunk > os->values.alloc - os->offset) |
549 | chunk = os->values.alloc - os->offset; |
550 | obj->arrayPut(index: oldSize, values: os->values.data() + os->offset, n: chunk); |
551 | toCopy -= chunk; |
552 | if (toCopy) |
553 | obj->arrayPut(index: oldSize + chunk, values: os->values.data(), n: toCopy); |
554 | } |
555 | |
556 | return oldSize + n; |
557 | } |
558 | |
559 | void ArrayData::insert(Object *o, uint index, const Value *v, bool isAccessor) |
560 | { |
561 | if (!isAccessor && o->d()->arrayData->type != Heap::ArrayData::Sparse) { |
562 | Heap::SimpleArrayData *d = o->d()->arrayData.cast<Heap::SimpleArrayData>(); |
563 | if (index < 0x1000 || index < d->values.size + (d->values.size >> 2)) { |
564 | if (index >= d->values.alloc) { |
565 | o->arrayReserve(n: index + 1); |
566 | d = o->d()->arrayData.cast<Heap::SimpleArrayData>(); |
567 | } |
568 | if (index >= d->values.size) { |
569 | // mark possible hole in the array |
570 | for (uint i = d->values.size; i < index; ++i) |
571 | d->setData(e: o->engine(), index: i, newVal: Value::emptyValue()); |
572 | d->values.size = index + 1; |
573 | } |
574 | d->setData(e: o->engine(), index, newVal: *v); |
575 | return; |
576 | } |
577 | } |
578 | |
579 | o->initSparseArray(); |
580 | Heap::SparseArrayData *s = o->d()->arrayData.cast<Heap::SparseArrayData>(); |
581 | SparseArrayNode *n = s->sparse->insert(akey: index); |
582 | if (n->value == UINT_MAX) |
583 | n->value = SparseArrayData::allocate(o, doubleSlot: isAccessor); |
584 | s = o->d()->arrayData.cast<Heap::SparseArrayData>(); |
585 | s->setArrayData(e: o->engine(), index: n->value, newVal: *v); |
586 | if (isAccessor) |
587 | s->setArrayData(e: o->engine(), index: n->value + Object::SetterOffset, newVal: v[Object::SetterOffset]); |
588 | } |
589 | |
590 | bool ArrayElementLessThan::operator()(Value v1, Value v2) const |
591 | { |
592 | Scope scope(m_engine); |
593 | |
594 | if (v1.isUndefined() || v1.isEmpty()) |
595 | return false; |
596 | if (v2.isUndefined() || v2.isEmpty()) |
597 | return true; |
598 | ScopedFunctionObject o(scope, m_comparefn); |
599 | if (o) { |
600 | Scope scope(o->engine()); |
601 | ScopedValue result(scope); |
602 | JSCallArguments jsCallData(scope, 2); |
603 | jsCallData.args[0] = v1; |
604 | jsCallData.args[1] = v2; |
605 | result = o->call(data: jsCallData); |
606 | if (scope.hasException()) |
607 | return false; |
608 | |
609 | return result->toNumber() < 0; |
610 | } |
611 | ScopedString p1s(scope, v1.toString(e: scope.engine)); |
612 | ScopedString p2s(scope, v2.toString(e: scope.engine)); |
613 | |
614 | if (!p1s) |
615 | return false; |
616 | if (!p2s) |
617 | return true; |
618 | |
619 | return p1s->toQString() < p2s->toQString(); |
620 | } |
621 | |
622 | void ArrayData::sort(ExecutionEngine *engine, Object *thisObject, const Value &comparefn, uint len) |
623 | { |
624 | if (!len) |
625 | return; |
626 | |
627 | Scope scope(engine); |
628 | Scoped<ArrayData> arrayData(scope, thisObject->arrayData()); |
629 | |
630 | if (!arrayData || !arrayData->length()) |
631 | return; |
632 | |
633 | if (!comparefn.isUndefined() && !comparefn.isFunctionObject()) { |
634 | engine->throwTypeError(); |
635 | return; |
636 | } |
637 | |
638 | // The spec says the sorting goes through a series of get,put and delete operations. |
639 | // this implies that the attributes don't get sorted around. |
640 | |
641 | if (arrayData->type() == Heap::ArrayData::Sparse) { |
642 | // since we sort anyway, we can simply iterate over the entries in the sparse |
643 | // array and append them one by one to a regular one. |
644 | Scoped<SparseArrayData> sparse(scope, static_cast<Heap::SparseArrayData *>(arrayData->d())); |
645 | |
646 | if (!sparse->sparse()->nEntries()) |
647 | return; |
648 | |
649 | thisObject->setArrayData(nullptr); |
650 | ArrayData::realloc(o: thisObject, newType: Heap::ArrayData::Simple, requested: sparse->sparse()->nEntries(), enforceAttributes: sparse->attrs() ? true : false); |
651 | Heap::SimpleArrayData *d = thisObject->d()->arrayData.cast<Heap::SimpleArrayData>(); |
652 | |
653 | SparseArrayNode *n = sparse->sparse()->begin(); |
654 | uint i = 0; |
655 | if (sparse->attrs()) { |
656 | while (n != sparse->sparse()->end()) { |
657 | if (n->value >= len) |
658 | break; |
659 | |
660 | PropertyAttributes a = sparse->attrs() ? sparse->attrs()[n->value] : Attr_Data; |
661 | d->setData(e: engine, index: i, newVal: Value::fromReturnedValue(val: thisObject->getValue(v: sparse->arrayData()[n->value], attrs: a))); |
662 | d->attrs[i] = a.isAccessor() ? Attr_Data : a; |
663 | |
664 | n = n->nextNode(); |
665 | ++i; |
666 | } |
667 | } else { |
668 | while (n != sparse->sparse()->end()) { |
669 | if (n->value >= len) |
670 | break; |
671 | d->setData(e: engine, index: i, newVal: sparse->arrayData()[n->value]); |
672 | n = n->nextNode(); |
673 | ++i; |
674 | } |
675 | } |
676 | d->values.size = i; |
677 | if (len > i) |
678 | len = i; |
679 | if (n != sparse->sparse()->end()) { |
680 | // have some entries outside the sort range that we need to ignore when sorting |
681 | thisObject->initSparseArray(); |
682 | while (n != sparse->sparse()->end()) { |
683 | PropertyAttributes a = sparse->attrs() ? sparse->attrs()[n->value] : Attr_Data; |
684 | thisObject->arraySet(index: n->value, p: reinterpret_cast<const Property *>(sparse->arrayData() + n->value), attributes: a); |
685 | |
686 | n = n->nextNode(); |
687 | } |
688 | |
689 | } |
690 | } else { |
691 | Heap::SimpleArrayData *d = thisObject->d()->arrayData.cast<Heap::SimpleArrayData>(); |
692 | if (len > d->values.size) |
693 | len = d->values.size; |
694 | |
695 | // sort empty values to the end |
696 | for (uint i = 0; i < len; i++) { |
697 | if (d->data(index: i).isEmpty()) { |
698 | while (--len > i) |
699 | if (!d->data(index: len).isEmpty()) |
700 | break; |
701 | Q_ASSERT(!d->attrs || !d->attrs[len].isAccessor()); |
702 | d->setData(e: engine, index: i, newVal: d->data(index: len)); |
703 | d->setData(e: engine, index: len, newVal: Value::emptyValue()); |
704 | } |
705 | } |
706 | |
707 | if (!len) |
708 | return; |
709 | } |
710 | |
711 | |
712 | ArrayElementLessThan lessThan(engine, comparefn); |
713 | |
714 | const auto thisArrayData = thisObject->arrayData(); |
715 | uint startIndex = thisArrayData->mappedIndex(index: 0); |
716 | uint endIndex = thisArrayData->mappedIndex(index: len - 1) + 1; |
717 | if (startIndex < endIndex) { |
718 | // Values are contiguous. Sort right away. |
719 | sortHelper( |
720 | start: thisArrayData->values.values + startIndex, |
721 | end: thisArrayData->values.values + endIndex, |
722 | lessThan); |
723 | } else { |
724 | // Values wrap around the end of the allocation. Close the gap to form a contiguous array. |
725 | // We're going to sort anyway. So we don't need to care about order. |
726 | |
727 | // ArrayElementLessThan sorts empty and undefined to the end of the array anyway, but we |
728 | // probably shouldn't rely on the unused slots to be actually undefined or empty. |
729 | |
730 | const uint gap = startIndex - endIndex; |
731 | const uint allocEnd = thisArrayData->values.alloc - 1; |
732 | for (uint i = 0; i < gap; ++i) { |
733 | const uint from = allocEnd - i; |
734 | const uint to = endIndex + i; |
735 | if (from < startIndex) |
736 | break; |
737 | |
738 | std::swap(a&: thisArrayData->values.values[from], b&: thisArrayData->values.values[to]); |
739 | } |
740 | |
741 | thisArrayData->offset = 0; |
742 | sortHelper(start: thisArrayData->values.values, end: thisArrayData->values.values + len, lessThan); |
743 | } |
744 | |
745 | #ifdef CHECK_SPARSE_ARRAYS |
746 | thisObject->initSparseArray(); |
747 | #endif |
748 | |
749 | } |
750 | |