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