diff options
Diffstat (limited to 'src/qml/jsruntime/qv4arraydata.cpp')
| -rw-r--r-- | src/qml/jsruntime/qv4arraydata.cpp | 321 |
1 files changed, 208 insertions, 113 deletions
diff --git a/src/qml/jsruntime/qv4arraydata.cpp b/src/qml/jsruntime/qv4arraydata.cpp index 0ec36bd9db..09e9a7f28f 100644 --- a/src/qml/jsruntime/qv4arraydata.cpp +++ b/src/qml/jsruntime/qv4arraydata.cpp @@ -82,8 +82,8 @@ void ArrayData::getHeadRoom(ArrayData *d) Q_ASSERT(d); Q_ASSERT(!d->offset); d->offset = qMax(d->len >> 2, (uint)16); - Property *newArray = new Property[d->offset + d->alloc]; - memcpy(newArray + d->offset, d->data, d->len*sizeof(Property)); + SafeValue *newArray = new SafeValue[d->offset + d->alloc]; + memcpy(newArray + d->offset, d->data, d->len*sizeof(SafeValue)); delete [] d->data; d->data = newArray + d->offset; if (d->attrs) { @@ -102,9 +102,9 @@ void ArrayData::reserve(ArrayData *d, uint n) return; d->alloc = qMax(n, 2*d->alloc); - Property *newArrayData = new Property[d->alloc + d->offset]; + SafeValue *newArrayData = new SafeValue[d->alloc + d->offset]; if (d->data) { - memcpy(newArrayData + d->offset, d->data, sizeof(Property)*d->len); + memcpy(newArrayData + d->offset, d->data, sizeof(SafeValue)*d->len); delete [] (d->data - d->offset); } d->data = newArrayData + d->offset; @@ -144,14 +144,19 @@ ReturnedValue ArrayData::get(const ArrayData *d, uint index) { if (index >= d->len) return Primitive::emptyValue().asReturnedValue(); - return d->data[index].value.asReturnedValue(); + return d->data[index].asReturnedValue(); } bool ArrayData::put(ArrayData *d, uint index, ValueRef value) { - Q_ASSERT(!d->attrs || !d->attrs->isAccessor()); + Q_ASSERT(index >= d->len || !d->attrs || !d->attrs[index].isAccessor()); // ### honour attributes - d->data[index].value = value; + d->data[index] = value; + if (index >= d->len) { + if (d->attrs) + d->attrs[index] = Attr_Data; + d->len = index; + } return true; } @@ -161,12 +166,12 @@ bool ArrayData::del(ArrayData *d, uint index) return true; if (!d->attrs || d->attrs[index].isConfigurable()) { - d->data[index].value = Primitive::emptyValue(); + d->data[index] = Primitive::emptyValue(); if (d->attrs) d->attrs[index] = Attr_Data; return true; } - if (d->data[index].value.isEmpty()) + if (d->data[index].isEmpty()) return true; return false; } @@ -192,7 +197,7 @@ void ArrayData::push_front(ArrayData *d, SafeValue *values, uint n) --d->data; ++d->len; ++d->alloc; - d->data->value = values[i].asReturnedValue(); + *d->data = values[i].asReturnedValue(); } } @@ -203,7 +208,7 @@ ReturnedValue ArrayData::pop_front(ArrayData *d) if (!d->len) return Encode::undefined(); - ReturnedValue v = d->data[0].value.isEmpty() ? Encode::undefined() : d->data[0].value.asReturnedValue(); + ReturnedValue v = d->data[0].isEmpty() ? Encode::undefined() : d->data[0].asReturnedValue(); ++d->offset; ++d->data; --d->len; @@ -214,14 +219,14 @@ ReturnedValue ArrayData::pop_front(ArrayData *d) uint ArrayData::truncate(ArrayData *d, uint newLen) { if (d->attrs) { - Property *it = d->data + d->len; - const Property *begin = d->data + newLen; + SafeValue *it = d->data + d->len; + const SafeValue *begin = d->data + newLen; while (--it >= begin) { - if (!it->value.isEmpty() && !d->attrs[it - d->data].isConfigurable()) { + if (!it->isEmpty() && !d->attrs[it - d->data].isConfigurable()) { newLen = it - d->data + 1; break; } - it->value = Primitive::emptyValue(); + *it = Primitive::emptyValue(); } } d->len = newLen; @@ -233,9 +238,9 @@ bool ArrayData::putArray(ArrayData *d, uint index, SafeValue *values, uint n) if (index + n > d->alloc) reserve(d, index + n + 1); for (uint i = d->len; i < index; ++i) - d->data[i].value = Primitive::emptyValue(); + d->data[i] = Primitive::emptyValue(); for (uint i = 0; i < n; ++i) - d->data[index + i].value = values[i]; + d->data[index + i] = values[i]; d->len = qMax(d->len, index + n); return true; } @@ -244,8 +249,17 @@ void SparseArrayData::free(ArrayData *d, uint idx) { Q_ASSERT(d && d->type == ArrayData::Sparse); SparseArrayData *dd = static_cast<SparseArrayData *>(d); - Property &pd = dd->data[idx]; - pd.value.uint_32 = dd->freeList; + SafeValue *v = dd->data + idx; + if (dd->attrs && dd->attrs[idx].isAccessor()) { + // double slot, free both. Order is important, so we have a double slot for allocation again afterwards. + v[1].tag = Value::Empty_Type; + v[1].uint_32 = dd->freeList; + v[0].tag = Value::Empty_Type; + v[0].uint_32 = idx + 1; + } else { + v->tag = Value::Empty_Type; + v->uint_32 = dd->freeList; + } dd->freeList = idx; if (dd->attrs) dd->attrs[idx].clear(); @@ -266,12 +280,13 @@ void SparseArrayData::reserve(ArrayData *d, uint n) return; SparseArrayData *dd = static_cast<SparseArrayData *>(d); + uint oldAlloc = dd->alloc; // ### FIXME dd->len = dd->alloc; dd->alloc = qMax(n, 2*dd->alloc); - Property *newArrayData = new Property[dd->alloc]; + SafeValue *newArrayData = new SafeValue[dd->alloc]; if (dd->data) { - memcpy(newArrayData, dd->data, sizeof(Property)*dd->len); + memcpy(newArrayData, dd->data, sizeof(SafeValue)*dd->len); delete [] dd->data; } dd->data = newArrayData; @@ -281,21 +296,41 @@ void SparseArrayData::reserve(ArrayData *d, uint n) delete [] dd->attrs; dd->attrs = newAttrs; } - for (uint i = dd->freeList; i < dd->alloc; ++i) - dd->data[i].value = Primitive::fromInt32(i + 1); + for (uint i = oldAlloc; i < dd->alloc; ++i) + dd->data[i] = Primitive::fromInt32(i + 1); } -uint SparseArrayData::allocate(ArrayData *d) +// double slots are required for accessor properties +uint SparseArrayData::allocate(ArrayData *d, bool doubleSlot) { Q_ASSERT(d->type == ArrayData::Sparse); SparseArrayData *dd = static_cast<SparseArrayData *>(d); - uint idx = dd->freeList; - if (dd->alloc == dd->freeList) - reserve(d, d->alloc + 1); - dd->freeList = dd->data[dd->freeList].value.uint_32; - if (dd->attrs) - dd->attrs[idx].setType(PropertyAttributes::Data); - return idx; + if (doubleSlot) { + uint *last = &dd->freeList; + while (1) { + if (*last + 1 >= dd->alloc) { + reserve(d, d->alloc + 2); + last = &dd->freeList; + } + + if (dd->data[*last].uint_32 == (*last + 1)) { + // found two slots in a row + uint idx = *last; + *last = dd->data[*last + 1].uint_32; + d->attrs[idx] = Attr_Accessor; + return idx; + } + last = &dd->data[*last].uint_32; + } + } else { + if (dd->alloc == dd->freeList) + reserve(d, d->alloc + 2); + uint idx = dd->freeList; + dd->freeList = dd->data[idx].uint_32; + if (dd->attrs) + dd->attrs[idx] = Attr_Data; + return idx; + } } ReturnedValue SparseArrayData::get(const ArrayData *d, uint index) @@ -303,16 +338,21 @@ ReturnedValue SparseArrayData::get(const ArrayData *d, uint index) SparseArrayNode *n = static_cast<const SparseArrayData *>(d)->sparse->findNode(index); if (!n) return Primitive::emptyValue().asReturnedValue(); - return d->data[n->value].value.asReturnedValue(); + return d->data[n->value].asReturnedValue(); } bool SparseArrayData::put(ArrayData *d, uint index, ValueRef value) { - // ### honour attributes + if (value->isEmpty()) + return true; + SparseArrayNode *n = static_cast<SparseArrayData *>(d)->sparse->insert(index); + Q_ASSERT(n->value == UINT_MAX || !d->attrs || !d->attrs[n->value].isAccessor()); if (n->value == UINT_MAX) n->value = allocate(d); - d->data[n->value].value = value; + d->data[n->value] = value; + if (d->attrs) + d->attrs[n->value] = Attr_Data; return true; } @@ -324,22 +364,43 @@ bool SparseArrayData::del(ArrayData *d, uint index) return true; uint pidx = n->value; - Q_ASSERT(!dd->data[pidx].value.isEmpty()); + Q_ASSERT(!dd->data[pidx].isEmpty()); - if (!dd->attrs || dd->attrs[pidx].isConfigurable()) { - d->data[pidx].value.int_32 = static_cast<SparseArrayData *>(d)->freeList; - static_cast<SparseArrayData *>(d)->freeList = pidx; - static_cast<SparseArrayData *>(d)->sparse->erase(n); - return true; + bool isAccessor = false; + if (dd->attrs) { + if (!dd->attrs[pidx].isConfigurable()) + return false; + + isAccessor = dd->attrs[pidx].isAccessor(); + dd->attrs[pidx] = Attr_Data; } - return false; + + if (isAccessor) { + // free up both indices + d->data[pidx + 1].tag = Value::Undefined_Type; + d->data[pidx + 1].uint_32 = static_cast<SparseArrayData *>(d)->freeList; + d->data[pidx].tag = Value::Undefined_Type; + d->data[pidx].uint_32 = pidx + 1; + } else { + d->data[pidx].tag = Value::Undefined_Type; + d->data[pidx].uint_32 = static_cast<SparseArrayData *>(d)->freeList; + } + + static_cast<SparseArrayData *>(d)->freeList = pidx; + static_cast<SparseArrayData *>(d)->sparse->erase(n); + return true; } void SparseArrayData::setAttribute(ArrayData *d, uint index, PropertyAttributes attrs) { SparseArrayNode *n = static_cast<SparseArrayData *>(d)->sparse->insert(index); if (n->value == UINT_MAX) - n->value = allocate(d); + n->value = allocate(d, attrs.isAccessor()); + else if (attrs.isAccessor() != d->attrs[n->value].isAccessor()) { + // need to convert the slot + free(d, n->value); + n->value = allocate(d, attrs.isAccessor()); + } d->attrs[n->value] = attrs; } @@ -356,7 +417,7 @@ void SparseArrayData::push_front(ArrayData *d, SafeValue *values, uint n) Q_ASSERT(!d->attrs); for (int i = n - 1; i >= 0; --i) { uint idx = allocate(d); - d->data[idx].value = values[i]; + d->data[idx] = values[i]; static_cast<SparseArrayData *>(d)->sparse->push_front(idx); } } @@ -367,7 +428,7 @@ ReturnedValue SparseArrayData::pop_front(ArrayData *d) uint idx = static_cast<SparseArrayData *>(d)->sparse->pop_front(); ReturnedValue v; if (idx != UINT_MAX) { - v = d->data[idx].value.asReturnedValue(); + v = d->data[idx].asReturnedValue(); SparseArrayData::free(d, idx); } else { v = Encode::undefined(); @@ -381,16 +442,13 @@ uint SparseArrayData::truncate(ArrayData *d, uint newLen) if (begin != static_cast<SparseArrayData *>(d)->sparse->end()) { SparseArrayNode *it = static_cast<SparseArrayData *>(d)->sparse->end()->previousNode(); while (1) { - Property &pd = d->data[it->value]; if (d->attrs) { if (!d->attrs[it->value].isConfigurable()) { newLen = it->key() + 1; break; } } - pd.value.tag = Value::Empty_Type; - pd.value.int_32 = static_cast<SparseArrayData *>(d)->freeList; - static_cast<SparseArrayData *>(d)->freeList = it->value; + free(d, it->value); bool brk = (it == begin); SparseArrayNode *prev = it->previousNode(); static_cast<SparseArrayData *>(d)->sparse->erase(it); @@ -415,7 +473,7 @@ uint ArrayData::append(Object *o, const ArrayObject *otherObj, uint n) { ArrayData *d = o->arrayData; if (!n) - return d->len; + return o->getLength(); const ArrayData *other = otherObj->arrayData; @@ -424,39 +482,37 @@ uint ArrayData::append(Object *o, const ArrayObject *otherObj, uint n) d = o->arrayData; } - uint oldSize = d->len; + uint oldSize = o->getLength(); // ### copy attributes as well! if (d->type == ArrayData::Sparse) { if (other->isSparse()) { - for (const SparseArrayNode *it = static_cast<const SparseArrayData *>(other)->sparse->begin(); - it != static_cast<const SparseArrayData *>(other)->sparse->end(); it = it->nextNode()) - // ### accessor properties - o->arraySet(d->len + it->key(), other->data[it->value].value); - } else { - d->vtable->reserve(d, oldSize + n); - memcpy(d->data + oldSize, other->data, n*sizeof(Property)); - if (d->attrs) - std::fill(d->attrs + oldSize, d->attrs + oldSize + n, PropertyAttributes(Attr_Data)); - for (uint i = 0; i < n; ++i) { - SparseArrayNode *n = static_cast<SparseArrayData *>(d)->sparse->insert(d->len + i); - n->value = oldSize + i; + if (otherObj->hasAccessorProperty && other->hasAttributes()) { + for (const SparseArrayNode *it = static_cast<const SparseArrayData *>(other)->sparse->begin(); + it != static_cast<const SparseArrayData *>(other)->sparse->end(); it = it->nextNode()) + o->arraySet(oldSize + it->key(), *reinterpret_cast<Property *>(other->data + it->value), other->attrs[it->value]); + } else { + for (const SparseArrayNode *it = static_cast<const SparseArrayData *>(other)->sparse->begin(); + it != static_cast<const SparseArrayData *>(other)->sparse->end(); it = it->nextNode()) + o->arraySet(oldSize + it->key(), other->data[it->value]); } + } else { + d->put(oldSize, other->data, n); } } else if (other->length()) { d->vtable->reserve(d, oldSize + other->length()); if (oldSize > d->len) { for (uint i = d->len; i < oldSize; ++i) - d->data[i].value = Primitive::emptyValue(); + d->data[i] = Primitive::emptyValue(); } if (other->attrs) { for (uint i = 0; i < other->len; ++i) { bool exists; - d->data[oldSize + i].value = const_cast<ArrayObject *>(otherObj)->getIndexed(i, &exists); + d->data[oldSize + i] = const_cast<ArrayObject *>(otherObj)->getIndexed(i, &exists); d->len = oldSize + i + 1; o->arrayData->setAttributes(oldSize + i, Attr_Data); if (!exists) - d->data[oldSize + i].value = Primitive::emptyValue(); + d->data[oldSize + i] = Primitive::emptyValue(); } } else { d->len = oldSize + other->len; @@ -469,95 +525,134 @@ uint ArrayData::append(Object *o, const ArrayObject *otherObj, uint n) return oldSize + n; } -Property *ArrayData::insert(Object *o, uint index) +Property *ArrayData::insert(Object *o, uint index, bool isAccessor) { Property *pd; if (o->arrayData->type != ArrayData::Sparse && (index < 0x1000 || index < o->arrayData->len + (o->arrayData->len >> 2))) { + Q_ASSERT(!isAccessor); if (index >= o->arrayData->alloc) o->arrayReserve(index + 1); if (index >= o->arrayData->len) { // mark possible hole in the array for (uint i = o->arrayData->len; i < index; ++i) - o->arrayData->data[i].value = Primitive::emptyValue(); + o->arrayData->data[i] = Primitive::emptyValue(); o->arrayData->len = index + 1; } - pd = o->arrayData->data + index; + pd = reinterpret_cast<Property *>(o->arrayData->data + index); } else { o->initSparseArray(); SparseArrayNode *n = static_cast<SparseArrayData *>(o->arrayData)->sparse->insert(index); if (n->value == UINT_MAX) - n->value = SparseArrayData::allocate(o->arrayData); - pd = o->arrayData->data + n->value; + n->value = SparseArrayData::allocate(o->arrayData, isAccessor); + pd = reinterpret_cast<Property *>(o->arrayData->data + n->value); } return pd; } void ArrayData::markObjects(ExecutionEngine *e) { - if (type == ArrayData::Simple) { - for (uint i = 0; i < len; ++i) - data[i].value.mark(e); - return; - } else { - for (uint i = 0; i < len; ++i) { - const Property &pd = data[i]; - if (attrs && attrs[i].isAccessor()) { - if (pd.getter()) - pd.getter()->mark(e); - if (pd.setter()) - pd.setter()->mark(e); - } else { - pd.value.mark(e); - } - } - } - + for (uint i = 0; i < len; ++i) + data[i].mark(e); } void ArrayData::sort(ExecutionContext *context, ObjectRef thisObject, const ValueRef comparefn, uint len) { + if (!len) + return; + ArrayData *d = thisObject->arrayData; - if (!d || !d->len) + if (!d || (!d->len && d->type != ArrayData::Sparse)) return; - if (d->type == ArrayData::Sparse) { - context->throwUnimplemented(QStringLiteral("Object::sort unimplemented for sparse arrays")); + if (!(comparefn->isUndefined() || comparefn->asObject())) { + context->throwTypeError(); return; } - if (len > d->len) - len = d->len; - // The spec says the sorting goes through a series of get,put and delete operations. // this implies that the attributes don't get sorted around. - // behavior of accessor properties is implementation defined. We simply turn them all - // into data properties and then sort. This is in line with the sentence above. - if (d->attrs) { + + if (d->type == ArrayData::Sparse) { + // since we sort anyway, we can simply iterate over the entries in the sparse + // array and append them one by one to a regular one. + SparseArrayData *sparse = static_cast<SparseArrayData *>(d); + + if (!sparse->sparse->nEntries()) + return; + + thisObject->arrayData = new ArrayData; + d = thisObject->arrayData; + d->vtable->reserve(d, sparse->sparse->nEntries()); + + SparseArrayNode *n = sparse->sparse->begin(); + uint i = 0; + if (sparse->attrs) { + d->ensureAttributes(); + while (n != sparse->sparse->end()) { + if (n->value >= len) + break; + + PropertyAttributes a = sparse->attrs ? sparse->attrs[n->value] : Attr_Data; + d->data[i] = thisObject->getValue(reinterpret_cast<Property *>(sparse->data + n->value), a); + d->attrs[i] = a.isAccessor() ? Attr_Data : a; + + n = n->nextNode(); + ++i; + } + } else { + while (n != sparse->sparse->end()) { + if (n->value >= len) + break; + d->data[i] = sparse->data[n->value]; + n = n->nextNode(); + ++i; + } + } + d->len = i; + if (len > i) + len = i; + if (n != sparse->sparse->end()) { + // have some entries outside the sort range that we need to ignore when sorting + thisObject->initSparseArray(); + d = thisObject->arrayData; + while (n != sparse->sparse->end()) { + PropertyAttributes a = sparse->attrs ? sparse->attrs[n->value] : Attr_Data; + thisObject->arraySet(n->value, *reinterpret_cast<Property *>(sparse->data + n->value), a); + + n = n->nextNode(); + } + + } + + sparse->ArrayData::free(); + } else { + if (len > d->len) + len = d->len; + + // sort empty values to the end for (uint i = 0; i < len; i++) { - if (d->data[i].value.isEmpty()) { + if (d->data[i].isEmpty()) { while (--len > i) - if (!d->data[len].value.isEmpty()) + if (!d->data[len].isEmpty()) break; - d->data[i].value = thisObject->getValue(d->data + len, d->attrs ? d->attrs[len] : Attr_Data); - if (d->attrs) - d->attrs[i] = Attr_Data; - d->data[len].value = Primitive::emptyValue(); - } else if (d->attrs && d->attrs[i].isAccessor()) { - d->data[i].value = thisObject->getValue(d->data + i, d->attrs[i]); - d->attrs[i] = Attr_Data; + Q_ASSERT(!d->attrs || !d->attrs[len].isAccessor()); + d->data[i] = d->data[len]; + d->data[len] = Primitive::emptyValue(); } } - } - if (!(comparefn->isUndefined() || comparefn->asObject())) { - context->throwTypeError(); - return; + if (!len) + return; } + ArrayElementLessThan lessThan(context, thisObject, comparefn); - if (!len) - return; - Property *begin = d->data; + SafeValue *begin = d->data; std::sort(begin, begin + len, lessThan); + +#ifdef CHECK_SPARSE_ARRAYS + thisObject->initSparseArray(); +#endif + } |