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
12using namespace QV4;
13
14DEFINE_MANAGED_VTABLE(ArrayData);
15
16const 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
32const 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
48Q_STATIC_ASSERT(sizeof(Heap::ArrayData) == sizeof(Heap::SimpleArrayData));
49Q_STATIC_ASSERT(sizeof(Heap::ArrayData) == sizeof(Heap::SparseArrayData));
50
51void 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
58void 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
168Heap::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
174void 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
182ReturnedValue 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
190bool 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
204bool 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
221void SimpleArrayData::setAttribute(Object *o, uint index, PropertyAttributes attrs)
222{
223 o->arrayData()->attrs[index] = attrs;
224}
225
226void 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
247ReturnedValue 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
260uint 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
279uint SimpleArrayData::length(const Heap::ArrayData *d)
280{
281 return d->values.size;
282}
283
284bool 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
300void 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
316Heap::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
323uint 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
362ReturnedValue 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
371bool 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
388bool 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
422void 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
439void 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
451ReturnedValue 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
466uint 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
491uint 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
501bool 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
509uint 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
559void 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
590bool 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
622void 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

source code of qtdeclarative/src/qml/jsruntime/qv4arraydata.cpp