Copying collection shouldn't require O(live bytes) memory overhead
[WebKit-https.git] / Source / JavaScriptCore / runtime / JSObject.cpp
1 /*
2  *  Copyright (C) 1999-2001 Harri Porten (porten@kde.org)
3  *  Copyright (C) 2001 Peter Kelly (pmk@post.com)
4  *  Copyright (C) 2003, 2004, 2005, 2006, 2008, 2009, 2012 Apple Inc. All rights reserved.
5  *  Copyright (C) 2007 Eric Seidel (eric@webkit.org)
6  *
7  *  This library is free software; you can redistribute it and/or
8  *  modify it under the terms of the GNU Library General Public
9  *  License as published by the Free Software Foundation; either
10  *  version 2 of the License, or (at your option) any later version.
11  *
12  *  This library is distributed in the hope that it will be useful,
13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15  *  Library General Public License for more details.
16  *
17  *  You should have received a copy of the GNU Library General Public License
18  *  along with this library; see the file COPYING.LIB.  If not, write to
19  *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
20  *  Boston, MA 02110-1301, USA.
21  *
22  */
23
24 #include "config.h"
25 #include "JSObject.h"
26
27 #include "ButterflyInlineMethods.h"
28 #include "CopiedSpaceInlineMethods.h"
29 #include "CopyVisitor.h"
30 #include "CopyVisitorInlineMethods.h"
31 #include "DatePrototype.h"
32 #include "ErrorConstructor.h"
33 #include "GetterSetter.h"
34 #include "IndexingHeaderInlineMethods.h"
35 #include "JSFunction.h"
36 #include "JSGlobalObject.h"
37 #include "Lookup.h"
38 #include "NativeErrorConstructor.h"
39 #include "Nodes.h"
40 #include "ObjectPrototype.h"
41 #include "Operations.h"
42 #include "PropertyDescriptor.h"
43 #include "PropertyNameArray.h"
44 #include "Reject.h"
45 #include "SlotVisitorInlineMethods.h"
46 #include <math.h>
47 #include <wtf/Assertions.h>
48
49 namespace JSC {
50
51 // We keep track of the size of the last array after it was grown. We use this
52 // as a simple heuristic for as the value to grow the next array from size 0.
53 // This value is capped by the constant FIRST_VECTOR_GROW defined in
54 // ArrayConventions.h.
55 static unsigned lastArraySize = 0;
56
57 JSCell* getCallableObjectSlow(JSCell* cell)
58 {
59     Structure* structure = cell->structure();
60     if (structure->typeInfo().type() == JSFunctionType)
61         return cell;
62     if (structure->classInfo()->isSubClassOf(&InternalFunction::s_info))
63         return cell;
64     return 0;
65 }
66
67 ASSERT_HAS_TRIVIAL_DESTRUCTOR(JSObject);
68 ASSERT_HAS_TRIVIAL_DESTRUCTOR(JSFinalObject);
69
70 const char* StrictModeReadonlyPropertyWriteError = "Attempted to assign to readonly property.";
71
72 const ClassInfo JSObject::s_info = { "Object", 0, 0, 0, CREATE_METHOD_TABLE(JSObject) };
73
74 const ClassInfo JSFinalObject::s_info = { "Object", &Base::s_info, 0, 0, CREATE_METHOD_TABLE(JSFinalObject) };
75
76 static inline void getClassPropertyNames(ExecState* exec, const ClassInfo* classInfo, PropertyNameArray& propertyNames, EnumerationMode mode, bool didReify)
77 {
78     // Add properties from the static hashtables of properties
79     for (; classInfo; classInfo = classInfo->parentClass) {
80         const HashTable* table = classInfo->propHashTable(exec);
81         if (!table)
82             continue;
83         table->initializeIfNeeded(exec);
84         ASSERT(table->table);
85
86         int hashSizeMask = table->compactSize - 1;
87         const HashEntry* entry = table->table;
88         for (int i = 0; i <= hashSizeMask; ++i, ++entry) {
89             if (entry->key() && (!(entry->attributes() & DontEnum) || (mode == IncludeDontEnumProperties)) && !((entry->attributes() & Function) && didReify))
90                 propertyNames.add(entry->key());
91         }
92     }
93 }
94
95 ALWAYS_INLINE void JSObject::copyButterfly(CopyVisitor& visitor, Butterfly* butterfly, size_t storageSize)
96 {
97     ASSERT(butterfly);
98     
99     Structure* structure = this->structure();
100     
101     size_t propertyCapacity = structure->outOfLineCapacity();
102     size_t preCapacity;
103     size_t indexingPayloadSizeInBytes;
104     bool hasIndexingHeader = JSC::hasIndexingHeader(structure->indexingType());
105     if (UNLIKELY(hasIndexingHeader)) {
106         preCapacity = butterfly->indexingHeader()->preCapacity(structure);
107         indexingPayloadSizeInBytes = butterfly->indexingHeader()->indexingPayloadSizeInBytes(structure);
108     } else {
109         preCapacity = 0;
110         indexingPayloadSizeInBytes = 0;
111     }
112     size_t capacityInBytes = Butterfly::totalSize(preCapacity, propertyCapacity, hasIndexingHeader, indexingPayloadSizeInBytes);
113     if (visitor.checkIfShouldCopy(butterfly->base(preCapacity, propertyCapacity), capacityInBytes)) {
114         Butterfly* newButterfly = Butterfly::createUninitializedDuringCollection(visitor, preCapacity, propertyCapacity, hasIndexingHeader, indexingPayloadSizeInBytes);
115         
116         // Copy the properties.
117         PropertyStorage currentTarget = newButterfly->propertyStorage();
118         PropertyStorage currentSource = butterfly->propertyStorage();
119         for (size_t count = storageSize; count--;)
120             (--currentTarget)->setWithoutWriteBarrier((--currentSource)->get());
121         
122         if (UNLIKELY(hasIndexingHeader)) {
123             *newButterfly->indexingHeader() = *butterfly->indexingHeader();
124             
125             // Copy the array if appropriate.
126             
127             WriteBarrier<Unknown>* currentTarget;
128             WriteBarrier<Unknown>* currentSource;
129             size_t count;
130             
131             switch (structure->indexingType()) {
132             case ALL_CONTIGUOUS_INDEXING_TYPES: {
133                 currentTarget = newButterfly->contiguous();
134                 currentSource = butterfly->contiguous();
135                 ASSERT(newButterfly->publicLength() <= newButterfly->vectorLength());
136                 count = newButterfly->vectorLength();
137                 break;
138             }
139                 
140             case ALL_ARRAY_STORAGE_INDEXING_TYPES: {
141                 newButterfly->arrayStorage()->copyHeaderFromDuringGC(*butterfly->arrayStorage());
142                 currentTarget = newButterfly->arrayStorage()->m_vector;
143                 currentSource = butterfly->arrayStorage()->m_vector;
144                 count = newButterfly->arrayStorage()->vectorLength();
145                 break;
146             }
147             default:
148                 CRASH();
149                 currentTarget = 0;
150                 currentSource = 0;
151                 count = 0;
152                 break;
153             }
154
155             while (count--)
156                 (currentTarget++)->setWithoutWriteBarrier((currentSource++)->get());
157         }
158         
159         m_butterfly = newButterfly;
160         visitor.didCopy(butterfly->base(preCapacity, propertyCapacity), capacityInBytes);
161     } 
162 }
163
164 ALWAYS_INLINE void JSObject::visitButterfly(SlotVisitor& visitor, Butterfly* butterfly, size_t storageSize)
165 {
166     ASSERT(butterfly);
167     
168     Structure* structure = this->structure();
169     
170     size_t propertyCapacity = structure->outOfLineCapacity();
171     size_t preCapacity;
172     size_t indexingPayloadSizeInBytes;
173     bool hasIndexingHeader = JSC::hasIndexingHeader(structure->indexingType());
174     if (UNLIKELY(hasIndexingHeader)) {
175         preCapacity = butterfly->indexingHeader()->preCapacity(structure);
176         indexingPayloadSizeInBytes = butterfly->indexingHeader()->indexingPayloadSizeInBytes(structure);
177     } else {
178         preCapacity = 0;
179         indexingPayloadSizeInBytes = 0;
180     }
181     size_t capacityInBytes = Butterfly::totalSize(preCapacity, propertyCapacity, hasIndexingHeader, indexingPayloadSizeInBytes);
182
183     // Mark the properties.
184     visitor.appendValues(butterfly->propertyStorage() - storageSize, storageSize);
185     visitor.copyLater(butterfly->base(preCapacity, propertyCapacity), capacityInBytes);
186     
187     // Mark the array if appropriate.
188     switch (structure->indexingType()) {
189     case ALL_CONTIGUOUS_INDEXING_TYPES:
190         visitor.appendValues(butterfly->contiguous(), butterfly->publicLength());
191         break;
192     case ALL_ARRAY_STORAGE_INDEXING_TYPES:
193         visitor.appendValues(butterfly->arrayStorage()->m_vector, butterfly->arrayStorage()->vectorLength());
194         if (butterfly->arrayStorage()->m_sparseMap)
195             visitor.append(&butterfly->arrayStorage()->m_sparseMap);
196         break;
197     default:
198         break;
199     }
200 }
201
202 void JSObject::visitChildren(JSCell* cell, SlotVisitor& visitor)
203 {
204     JSObject* thisObject = jsCast<JSObject*>(cell);
205     ASSERT_GC_OBJECT_INHERITS(thisObject, &s_info);
206 #if !ASSERT_DISABLED
207     bool wasCheckingForDefaultMarkViolation = visitor.m_isCheckingForDefaultMarkViolation;
208     visitor.m_isCheckingForDefaultMarkViolation = false;
209 #endif
210     
211     JSCell::visitChildren(thisObject, visitor);
212
213     Butterfly* butterfly = thisObject->butterfly();
214     if (butterfly)
215         thisObject->visitButterfly(visitor, butterfly, thisObject->structure()->outOfLineSize());
216
217 #if !ASSERT_DISABLED
218     visitor.m_isCheckingForDefaultMarkViolation = wasCheckingForDefaultMarkViolation;
219 #endif
220 }
221
222 void JSObject::copyBackingStore(JSCell* cell, CopyVisitor& visitor)
223 {
224     JSObject* thisObject = jsCast<JSObject*>(cell);
225     ASSERT_GC_OBJECT_INHERITS(thisObject, &s_info);
226     
227     Butterfly* butterfly = thisObject->butterfly();
228     if (butterfly)
229         thisObject->copyButterfly(visitor, butterfly, thisObject->structure()->outOfLineSize());
230 }
231
232 void JSFinalObject::visitChildren(JSCell* cell, SlotVisitor& visitor)
233 {
234     JSFinalObject* thisObject = jsCast<JSFinalObject*>(cell);
235     ASSERT_GC_OBJECT_INHERITS(thisObject, &s_info);
236 #if !ASSERT_DISABLED
237     bool wasCheckingForDefaultMarkViolation = visitor.m_isCheckingForDefaultMarkViolation;
238     visitor.m_isCheckingForDefaultMarkViolation = false;
239 #endif
240     
241     JSCell::visitChildren(thisObject, visitor);
242
243     Butterfly* butterfly = thisObject->butterfly();
244     if (butterfly)
245         thisObject->visitButterfly(visitor, butterfly, thisObject->structure()->outOfLineSize());
246
247     size_t storageSize = thisObject->structure()->inlineSize();
248     visitor.appendValues(thisObject->inlineStorage(), storageSize);
249
250 #if !ASSERT_DISABLED
251     visitor.m_isCheckingForDefaultMarkViolation = wasCheckingForDefaultMarkViolation;
252 #endif
253 }
254
255 String JSObject::className(const JSObject* object)
256 {
257     const ClassInfo* info = object->classInfo();
258     ASSERT(info);
259     return info->className;
260 }
261
262 bool JSObject::getOwnPropertySlotByIndex(JSCell* cell, ExecState* exec, unsigned i, PropertySlot& slot)
263 {
264     // NB. The fact that we're directly consulting our indexed storage implies that it is not
265     // legal for anyone to override getOwnPropertySlot() without also overriding
266     // getOwnPropertySlotByIndex().
267     
268     JSObject* thisObject = jsCast<JSObject*>(cell);
269     
270     if (i > MAX_ARRAY_INDEX)
271         return thisObject->methodTable()->getOwnPropertySlot(thisObject, exec, Identifier::from(exec, i), slot);
272     
273     switch (thisObject->structure()->indexingType()) {
274     case ALL_BLANK_INDEXING_TYPES:
275         break;
276         
277     case ALL_CONTIGUOUS_INDEXING_TYPES: {
278         Butterfly* butterfly = thisObject->m_butterfly;
279         if (i >= butterfly->vectorLength())
280             return false;
281         
282         JSValue value = butterfly->contiguous()[i].get();
283         if (value) {
284             slot.setValue(value);
285             return true;
286         }
287         
288         return false;
289     }
290         
291     case ALL_ARRAY_STORAGE_INDEXING_TYPES: {
292         ArrayStorage* storage = thisObject->m_butterfly->arrayStorage();
293         if (i >= storage->length())
294             return false;
295         
296         if (i < storage->vectorLength()) {
297             JSValue value = storage->m_vector[i].get();
298             if (value) {
299                 slot.setValue(value);
300                 return true;
301             }
302         } else if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
303             SparseArrayValueMap::iterator it = map->find(i);
304             if (it != map->notFound()) {
305                 it->value.get(slot);
306                 return true;
307             }
308         }
309         break;
310     }
311         
312     default:
313         ASSERT_NOT_REACHED();
314         break;
315     }
316     
317     return false;
318 }
319
320 // ECMA 8.6.2.2
321 void JSObject::put(JSCell* cell, ExecState* exec, PropertyName propertyName, JSValue value, PutPropertySlot& slot)
322 {
323     JSObject* thisObject = jsCast<JSObject*>(cell);
324     ASSERT(value);
325     ASSERT(!Heap::heap(value) || Heap::heap(value) == Heap::heap(thisObject));
326     JSGlobalData& globalData = exec->globalData();
327     
328     // Try indexed put first. This is required for correctness, since loads on property names that appear like
329     // valid indices will never look in the named property storage.
330     unsigned i = propertyName.asIndex();
331     if (i != PropertyName::NotAnIndex) {
332         putByIndex(thisObject, exec, i, value, slot.isStrictMode());
333         return;
334     }
335
336     // Check if there are any setters or getters in the prototype chain
337     JSValue prototype;
338     if (propertyName != exec->propertyNames().underscoreProto) {
339         for (JSObject* obj = thisObject; !obj->structure()->hasReadOnlyOrGetterSetterPropertiesExcludingProto(); obj = asObject(prototype)) {
340             prototype = obj->prototype();
341             if (prototype.isNull()) {
342                 if (!thisObject->putDirectInternal<PutModePut>(globalData, propertyName, value, 0, slot, getCallableObject(value)) && slot.isStrictMode())
343                     throwTypeError(exec, ASCIILiteral(StrictModeReadonlyPropertyWriteError));
344                 return;
345             }
346         }
347     }
348
349     for (JSObject* obj = thisObject; ; obj = asObject(prototype)) {
350         unsigned attributes;
351         JSCell* specificValue;
352         PropertyOffset offset = obj->structure()->get(globalData, propertyName, attributes, specificValue);
353         if (isValidOffset(offset)) {
354             if (attributes & ReadOnly) {
355                 if (slot.isStrictMode())
356                     throwError(exec, createTypeError(exec, ASCIILiteral(StrictModeReadonlyPropertyWriteError)));
357                 return;
358             }
359
360             JSValue gs = obj->getDirectOffset(offset);
361             if (gs.isGetterSetter()) {
362                 JSObject* setterFunc = asGetterSetter(gs)->setter();        
363                 if (!setterFunc) {
364                     if (slot.isStrictMode())
365                         throwError(exec, createTypeError(exec, ASCIILiteral("setting a property that has only a getter")));
366                     return;
367                 }
368                 
369                 CallData callData;
370                 CallType callType = setterFunc->methodTable()->getCallData(setterFunc, callData);
371                 MarkedArgumentBuffer args;
372                 args.append(value);
373
374                 // If this is WebCore's global object then we need to substitute the shell.
375                 call(exec, setterFunc, callType, callData, thisObject->methodTable()->toThisObject(thisObject, exec), args);
376                 return;
377             }
378
379             // If there's an existing property on the object or one of its 
380             // prototypes it should be replaced, so break here.
381             break;
382         }
383
384         prototype = obj->prototype();
385         if (prototype.isNull())
386             break;
387     }
388     
389     if (!thisObject->putDirectInternal<PutModePut>(globalData, propertyName, value, 0, slot, getCallableObject(value)) && slot.isStrictMode())
390         throwTypeError(exec, ASCIILiteral(StrictModeReadonlyPropertyWriteError));
391     return;
392 }
393
394 void JSObject::putByIndex(JSCell* cell, ExecState* exec, unsigned propertyName, JSValue value, bool shouldThrow)
395 {
396     JSObject* thisObject = jsCast<JSObject*>(cell);
397     
398     if (propertyName > MAX_ARRAY_INDEX) {
399         PutPropertySlot slot(shouldThrow);
400         thisObject->methodTable()->put(thisObject, exec, Identifier::from(exec, propertyName), value, slot);
401         return;
402     }
403     
404     switch (thisObject->structure()->indexingType()) {
405     case ALL_BLANK_INDEXING_TYPES:
406         break;
407         
408     case ALL_CONTIGUOUS_INDEXING_TYPES: {
409         Butterfly* butterfly = thisObject->m_butterfly;
410         if (propertyName >= butterfly->vectorLength())
411             break;
412         butterfly->contiguous()[propertyName].set(exec->globalData(), thisObject, value);
413         if (propertyName >= butterfly->publicLength())
414             butterfly->setPublicLength(propertyName + 1);
415         return;
416     }
417         
418     case NonArrayWithArrayStorage:
419     case ArrayWithArrayStorage: {
420         ArrayStorage* storage = thisObject->m_butterfly->arrayStorage();
421         
422         if (propertyName >= storage->vectorLength())
423             break;
424         
425         WriteBarrier<Unknown>& valueSlot = storage->m_vector[propertyName];
426         unsigned length = storage->length();
427         
428         // Update length & m_numValuesInVector as necessary.
429         if (propertyName >= length) {
430             length = propertyName + 1;
431             storage->setLength(length);
432             ++storage->m_numValuesInVector;
433         } else if (!valueSlot)
434             ++storage->m_numValuesInVector;
435         
436         valueSlot.set(exec->globalData(), thisObject, value);
437         return;
438     }
439         
440     case NonArrayWithSlowPutArrayStorage:
441     case ArrayWithSlowPutArrayStorage: {
442         ArrayStorage* storage = thisObject->m_butterfly->arrayStorage();
443         
444         if (propertyName >= storage->vectorLength())
445             break;
446         
447         WriteBarrier<Unknown>& valueSlot = storage->m_vector[propertyName];
448         unsigned length = storage->length();
449         
450         // Update length & m_numValuesInVector as necessary.
451         if (propertyName >= length) {
452             if (thisObject->attemptToInterceptPutByIndexOnHole(exec, propertyName, value, shouldThrow))
453                 return;
454             length = propertyName + 1;
455             storage->setLength(length);
456             ++storage->m_numValuesInVector;
457         } else if (!valueSlot) {
458             if (thisObject->attemptToInterceptPutByIndexOnHole(exec, propertyName, value, shouldThrow))
459                 return;
460             ++storage->m_numValuesInVector;
461         }
462         
463         valueSlot.set(exec->globalData(), thisObject, value);
464         return;
465     }
466         
467     default:
468         ASSERT_NOT_REACHED();
469     }
470     
471     thisObject->putByIndexBeyondVectorLength(exec, propertyName, value, shouldThrow);
472 }
473
474 ArrayStorage* JSObject::enterDictionaryIndexingModeWhenArrayStorageAlreadyExists(JSGlobalData& globalData, ArrayStorage* storage)
475 {
476     SparseArrayValueMap* map = storage->m_sparseMap.get();
477
478     if (!map)
479         map = allocateSparseIndexMap(globalData);
480
481     if (map->sparseMode())
482         return storage;
483
484     map->setSparseMode();
485
486     unsigned usedVectorLength = std::min(storage->length(), storage->vectorLength());
487     for (unsigned i = 0; i < usedVectorLength; ++i) {
488         JSValue value = storage->m_vector[i].get();
489         // This will always be a new entry in the map, so no need to check we can write,
490         // and attributes are default so no need to set them.
491         if (value)
492             map->add(this, i).iterator->value.set(globalData, this, value);
493     }
494
495     Butterfly* newButterfly = storage->butterfly()->resizeArray(globalData, structure(), 0, ArrayStorage::sizeFor(0));
496     if (!newButterfly)
497         CRASH();
498     
499     m_butterfly = newButterfly;
500     newButterfly->arrayStorage()->m_indexBias = 0;
501     newButterfly->arrayStorage()->setVectorLength(0);
502     newButterfly->arrayStorage()->m_sparseMap.set(globalData, this, map);
503     
504     return newButterfly->arrayStorage();
505 }
506
507 void JSObject::enterDictionaryIndexingMode(JSGlobalData& globalData)
508 {
509     switch (structure()->indexingType()) {
510     case ALL_CONTIGUOUS_INDEXING_TYPES:
511         // NOTE: this is horribly inefficient, as it will perform two conversions. We could optimize
512         // this case if we ever cared.
513         enterDictionaryIndexingModeWhenArrayStorageAlreadyExists(globalData, convertContiguousToArrayStorage(globalData));
514         break;
515     case ALL_ARRAY_STORAGE_INDEXING_TYPES:
516         enterDictionaryIndexingModeWhenArrayStorageAlreadyExists(globalData, m_butterfly->arrayStorage());
517         break;
518         
519     default:
520         break;
521     }
522 }
523
524 void JSObject::notifyPresenceOfIndexedAccessors(JSGlobalData& globalData)
525 {
526     if (mayInterceptIndexedAccesses())
527         return;
528     
529     setStructure(globalData, Structure::nonPropertyTransition(globalData, structure(), AddIndexedAccessors));
530     
531     if (!mayBeUsedAsPrototype(globalData))
532         return;
533     
534     globalObject()->haveABadTime(globalData);
535 }
536
537 WriteBarrier<Unknown>* JSObject::createInitialContiguous(JSGlobalData& globalData, unsigned length)
538 {
539     ASSERT(length < MAX_ARRAY_INDEX);
540     IndexingType oldType = structure()->indexingType();
541     ASSERT_UNUSED(oldType, !hasIndexedProperties(oldType));
542     ASSERT(!structure()->needsSlowPutIndexing());
543     ASSERT(!indexingShouldBeSparse());
544     unsigned vectorLength = std::max(length, BASE_VECTOR_LEN);
545     Butterfly* newButterfly = m_butterfly->growArrayRight(
546         globalData, structure(), structure()->outOfLineCapacity(), false, 0,
547         sizeof(EncodedJSValue) * vectorLength);
548     newButterfly->setPublicLength(length);
549     newButterfly->setVectorLength(vectorLength);
550     Structure* newStructure = Structure::nonPropertyTransition(globalData, structure(), AllocateContiguous);
551     setButterfly(globalData, newButterfly, newStructure);
552     return newButterfly->contiguous();
553 }
554
555 ArrayStorage* JSObject::createArrayStorage(JSGlobalData& globalData, unsigned length, unsigned vectorLength)
556 {
557     IndexingType oldType = structure()->indexingType();
558     ASSERT_UNUSED(oldType, !hasIndexedProperties(oldType));
559     Butterfly* newButterfly = m_butterfly->growArrayRight(
560         globalData, structure(), structure()->outOfLineCapacity(), false, 0,
561         ArrayStorage::sizeFor(vectorLength));
562     if (!newButterfly)
563         CRASH();
564     ArrayStorage* result = newButterfly->arrayStorage();
565     result->setLength(length);
566     result->setVectorLength(vectorLength);
567     result->m_sparseMap.clear();
568     result->m_numValuesInVector = 0;
569     result->m_indexBias = 0;
570     Structure* newStructure = Structure::nonPropertyTransition(globalData, structure(), structure()->suggestedArrayStorageTransition());
571     setButterfly(globalData, newButterfly, newStructure);
572     return result;
573 }
574
575 ArrayStorage* JSObject::createInitialArrayStorage(JSGlobalData& globalData)
576 {
577     return createArrayStorage(globalData, 0, BASE_VECTOR_LEN);
578 }
579
580 ArrayStorage* JSObject::convertContiguousToArrayStorage(JSGlobalData& globalData, NonPropertyTransition transition, unsigned neededLength)
581 {
582     ASSERT(hasContiguous(structure()->indexingType()));
583     
584     unsigned publicLength = m_butterfly->publicLength();
585     unsigned propertyCapacity = structure()->outOfLineCapacity();
586     unsigned propertySize = structure()->outOfLineSize();
587     
588     Butterfly* newButterfly = Butterfly::createUninitialized(
589         globalData, 0, propertyCapacity, true, ArrayStorage::sizeFor(neededLength));
590     
591     memcpy(
592         newButterfly->propertyStorage() - propertySize,
593         m_butterfly->propertyStorage() - propertySize,
594         propertySize * sizeof(EncodedJSValue));
595     
596     ArrayStorage* newStorage = newButterfly->arrayStorage();
597     newStorage->setVectorLength(neededLength);
598     newStorage->setLength(publicLength);
599     newStorage->m_sparseMap.clear();
600     newStorage->m_indexBias = 0;
601     newStorage->m_numValuesInVector = 0;
602     for (unsigned i = publicLength; i--;) {
603         JSValue v = m_butterfly->contiguous()[i].get();
604         if (!v)
605             continue;
606         newStorage->m_vector[i].setWithoutWriteBarrier(v);
607         newStorage->m_numValuesInVector++;
608     }
609     
610     Structure* newStructure = Structure::nonPropertyTransition(globalData, structure(), transition);
611     setButterfly(globalData, newButterfly, newStructure);
612     return newStorage;
613 }
614
615 ArrayStorage* JSObject::convertContiguousToArrayStorage(JSGlobalData& globalData, NonPropertyTransition transition)
616 {
617     return convertContiguousToArrayStorage(globalData, transition, m_butterfly->vectorLength());
618 }
619
620 ArrayStorage* JSObject::convertContiguousToArrayStorage(JSGlobalData& globalData)
621 {
622     return convertContiguousToArrayStorage(globalData, structure()->suggestedArrayStorageTransition());
623 }
624
625 WriteBarrier<Unknown>* JSObject::ensureContiguousSlow(JSGlobalData& globalData)
626 {
627     switch (structure()->indexingType()) {
628     case ALL_BLANK_INDEXING_TYPES:
629         if (UNLIKELY(indexingShouldBeSparse() || structure()->needsSlowPutIndexing()))
630             return 0;
631         return createInitialContiguous(globalData, 0);
632         
633     default:
634         ASSERT_NOT_REACHED();
635         return 0;
636     }
637 }
638
639 ArrayStorage* JSObject::ensureArrayStorageSlow(JSGlobalData& globalData)
640 {
641     switch (structure()->indexingType()) {
642     case ALL_CONTIGUOUS_INDEXING_TYPES:
643         ASSERT(!indexingShouldBeSparse());
644         ASSERT(!structure()->needsSlowPutIndexing());
645         return convertContiguousToArrayStorage(globalData);
646         
647     case ALL_BLANK_INDEXING_TYPES:
648         if (UNLIKELY(indexingShouldBeSparse()))
649             return ensureArrayStorageExistsAndEnterDictionaryIndexingMode(globalData);
650         return createInitialArrayStorage(globalData);
651         
652     default:
653         ASSERT_NOT_REACHED();
654         return 0;
655     }
656 }
657
658 Butterfly* JSObject::ensureIndexedStorageSlow(JSGlobalData& globalData)
659 {
660     switch (structure()->indexingType()) {
661     case ALL_BLANK_INDEXING_TYPES:
662         if (UNLIKELY(structure()->needsSlowPutIndexing()))
663             return createInitialArrayStorage(globalData)->butterfly();
664         if (UNLIKELY(indexingShouldBeSparse()))
665             return ensureArrayStorageExistsAndEnterDictionaryIndexingMode(globalData)->butterfly();
666         return Butterfly::fromContiguous(createInitialContiguous(globalData, 0));
667         
668     default:
669         ASSERT_NOT_REACHED();
670         return 0;
671     }
672 }
673
674 ArrayStorage* JSObject::ensureArrayStorageExistsAndEnterDictionaryIndexingMode(JSGlobalData& globalData)
675 {
676     switch (structure()->indexingType()) {
677     case ALL_CONTIGUOUS_INDEXING_TYPES:
678         // FIXME: This could be made way more efficient, if we cared.
679         return enterDictionaryIndexingModeWhenArrayStorageAlreadyExists(globalData, convertContiguousToArrayStorage(globalData));
680         
681     case ALL_ARRAY_STORAGE_INDEXING_TYPES:
682         return enterDictionaryIndexingModeWhenArrayStorageAlreadyExists(globalData, m_butterfly->arrayStorage());
683         
684     case ALL_BLANK_INDEXING_TYPES: {
685         createArrayStorage(globalData, 0, 0);
686         SparseArrayValueMap* map = allocateSparseIndexMap(globalData);
687         map->setSparseMode();
688         return arrayStorage();
689     }
690         
691     default:
692         ASSERT_NOT_REACHED();
693         return 0;
694     }
695 }
696
697 void JSObject::switchToSlowPutArrayStorage(JSGlobalData& globalData)
698 {
699     switch (structure()->indexingType()) {
700     case ALL_CONTIGUOUS_INDEXING_TYPES: {
701         convertContiguousToArrayStorage(globalData, AllocateSlowPutArrayStorage);
702         break;
703     }
704         
705     case NonArrayWithArrayStorage:
706     case ArrayWithArrayStorage: {
707         Structure* newStructure = Structure::nonPropertyTransition(globalData, structure(), SwitchToSlowPutArrayStorage);
708         setStructure(globalData, newStructure);
709         break;
710     }
711         
712     default:
713         ASSERT_NOT_REACHED();
714         break;
715     }
716 }
717
718 void JSObject::putDirectVirtual(JSObject* object, ExecState* exec, PropertyName propertyName, JSValue value, unsigned attributes)
719 {
720     ASSERT(!value.isGetterSetter() && !(attributes & Accessor));
721     PutPropertySlot slot;
722     object->putDirectInternal<PutModeDefineOwnProperty>(exec->globalData(), propertyName, value, attributes, slot, getCallableObject(value));
723 }
724
725 void JSObject::setPrototype(JSGlobalData& globalData, JSValue prototype)
726 {
727     ASSERT(prototype);
728     if (prototype.isObject())
729         asObject(prototype)->notifyUsedAsPrototype(globalData);
730     
731     Structure* newStructure = Structure::changePrototypeTransition(globalData, structure(), prototype);
732     setStructure(globalData, newStructure);
733     
734     if (!newStructure->anyObjectInChainMayInterceptIndexedAccesses())
735         return;
736     
737     if (mayBeUsedAsPrototype(globalData)) {
738         newStructure->globalObject()->haveABadTime(globalData);
739         return;
740     }
741     
742     if (!hasIndexingHeader(structure()->indexingType()))
743         return;
744     
745     if (shouldUseSlowPut(structure()->indexingType()))
746         return;
747     
748     switchToSlowPutArrayStorage(globalData);
749 }
750
751 bool JSObject::setPrototypeWithCycleCheck(JSGlobalData& globalData, JSValue prototype)
752 {
753     JSValue checkFor = this;
754     if (this->isGlobalObject())
755         checkFor = jsCast<JSGlobalObject*>(this)->globalExec()->thisValue();
756
757     JSValue nextPrototype = prototype;
758     while (nextPrototype && nextPrototype.isObject()) {
759         if (nextPrototype == checkFor)
760             return false;
761         nextPrototype = asObject(nextPrototype)->prototype();
762     }
763     setPrototype(globalData, prototype);
764     return true;
765 }
766
767 void JSObject::resetInheritorID(JSGlobalData& globalData)
768 {
769     PropertyOffset offset = structure()->get(globalData, globalData.m_inheritorIDKey);
770     if (!isValidOffset(offset))
771         return;
772     
773     putDirectOffset(globalData, offset, jsUndefined());
774 }
775
776 Structure* JSObject::inheritorID(JSGlobalData& globalData)
777 {
778     if (WriteBarrierBase<Unknown>* location = getDirectLocation(globalData, globalData.m_inheritorIDKey)) {
779         JSValue value = location->get();
780         if (value.isCell()) {
781             Structure* inheritorID = jsCast<Structure*>(value);
782             ASSERT(inheritorID->isEmpty());
783             return inheritorID;
784         }
785         ASSERT(value.isUndefined());
786     }
787     return createInheritorID(globalData);
788 }
789
790 bool JSObject::allowsAccessFrom(ExecState* exec)
791 {
792     JSGlobalObject* globalObject = this->globalObject();
793     return globalObject->globalObjectMethodTable()->allowsAccessFrom(globalObject, exec);
794 }
795
796 void JSObject::putDirectAccessor(ExecState* exec, PropertyName propertyName, JSValue value, unsigned attributes)
797 {
798     ASSERT(value.isGetterSetter() && (attributes & Accessor));
799
800     unsigned index = propertyName.asIndex();
801     if (index != PropertyName::NotAnIndex) {
802         putDirectIndex(exec, index, value, attributes, PutDirectIndexLikePutDirect);
803         return;
804     }
805
806     JSGlobalData& globalData = exec->globalData();
807
808     PutPropertySlot slot;
809     putDirectInternal<PutModeDefineOwnProperty>(globalData, propertyName, value, attributes, slot, getCallableObject(value));
810
811     // putDirect will change our Structure if we add a new property. For
812     // getters and setters, though, we also need to change our Structure
813     // if we override an existing non-getter or non-setter.
814     if (slot.type() != PutPropertySlot::NewProperty)
815         setStructure(globalData, Structure::attributeChangeTransition(globalData, structure(), propertyName, attributes));
816
817     if (attributes & ReadOnly)
818         structure()->setContainsReadOnlyProperties();
819
820     structure()->setHasGetterSetterProperties(propertyName == globalData.propertyNames->underscoreProto);
821 }
822
823 bool JSObject::hasProperty(ExecState* exec, PropertyName propertyName) const
824 {
825     PropertySlot slot;
826     return const_cast<JSObject*>(this)->getPropertySlot(exec, propertyName, slot);
827 }
828
829 bool JSObject::hasProperty(ExecState* exec, unsigned propertyName) const
830 {
831     PropertySlot slot;
832     return const_cast<JSObject*>(this)->getPropertySlot(exec, propertyName, slot);
833 }
834
835 // ECMA 8.6.2.5
836 bool JSObject::deleteProperty(JSCell* cell, ExecState* exec, PropertyName propertyName)
837 {
838     JSObject* thisObject = jsCast<JSObject*>(cell);
839     
840     unsigned i = propertyName.asIndex();
841     if (i != PropertyName::NotAnIndex)
842         return thisObject->methodTable()->deletePropertyByIndex(thisObject, exec, i);
843
844     if (!thisObject->staticFunctionsReified())
845         thisObject->reifyStaticFunctionsForDelete(exec);
846
847     unsigned attributes;
848     JSCell* specificValue;
849     if (isValidOffset(thisObject->structure()->get(exec->globalData(), propertyName, attributes, specificValue))) {
850         if (attributes & DontDelete && !exec->globalData().isInDefineOwnProperty())
851             return false;
852         thisObject->removeDirect(exec->globalData(), propertyName);
853         return true;
854     }
855
856     // Look in the static hashtable of properties
857     const HashEntry* entry = thisObject->findPropertyHashEntry(exec, propertyName);
858     if (entry && entry->attributes() & DontDelete && !exec->globalData().isInDefineOwnProperty())
859         return false; // this builtin property can't be deleted
860
861     // FIXME: Should the code here actually do some deletion?
862     return true;
863 }
864
865 bool JSObject::hasOwnProperty(ExecState* exec, PropertyName propertyName) const
866 {
867     PropertySlot slot;
868     return const_cast<JSObject*>(this)->methodTable()->getOwnPropertySlot(const_cast<JSObject*>(this), exec, propertyName, slot);
869 }
870
871 bool JSObject::deletePropertyByIndex(JSCell* cell, ExecState* exec, unsigned i)
872 {
873     JSObject* thisObject = jsCast<JSObject*>(cell);
874     
875     if (i > MAX_ARRAY_INDEX)
876         return thisObject->methodTable()->deleteProperty(thisObject, exec, Identifier::from(exec, i));
877     
878     switch (thisObject->structure()->indexingType()) {
879     case ALL_BLANK_INDEXING_TYPES:
880         return true;
881         
882     case ALL_CONTIGUOUS_INDEXING_TYPES: {
883         Butterfly* butterfly = thisObject->m_butterfly;
884         if (i >= butterfly->vectorLength())
885             return true;
886         butterfly->contiguous()[i].clear();
887         return true;
888     }
889         
890     case ALL_ARRAY_STORAGE_INDEXING_TYPES: {
891         ArrayStorage* storage = thisObject->m_butterfly->arrayStorage();
892         
893         if (i < storage->vectorLength()) {
894             WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
895             if (valueSlot) {
896                 valueSlot.clear();
897                 --storage->m_numValuesInVector;
898             }
899         } else if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
900             SparseArrayValueMap::iterator it = map->find(i);
901             if (it != map->notFound()) {
902                 if (it->value.attributes & DontDelete)
903                     return false;
904                 map->remove(it);
905             }
906         }
907         
908         return true;
909     }
910         
911     default:
912         ASSERT_NOT_REACHED();
913         return false;
914     }
915 }
916
917 static ALWAYS_INLINE JSValue callDefaultValueFunction(ExecState* exec, const JSObject* object, PropertyName propertyName)
918 {
919     JSValue function = object->get(exec, propertyName);
920     CallData callData;
921     CallType callType = getCallData(function, callData);
922     if (callType == CallTypeNone)
923         return exec->exception();
924
925     // Prevent "toString" and "valueOf" from observing execution if an exception
926     // is pending.
927     if (exec->hadException())
928         return exec->exception();
929
930     JSValue result = call(exec, function, callType, callData, const_cast<JSObject*>(object), exec->emptyList());
931     ASSERT(!result.isGetterSetter());
932     if (exec->hadException())
933         return exec->exception();
934     if (result.isObject())
935         return JSValue();
936     return result;
937 }
938
939 bool JSObject::getPrimitiveNumber(ExecState* exec, double& number, JSValue& result) const
940 {
941     result = methodTable()->defaultValue(this, exec, PreferNumber);
942     number = result.toNumber(exec);
943     return !result.isString();
944 }
945
946 // ECMA 8.6.2.6
947 JSValue JSObject::defaultValue(const JSObject* object, ExecState* exec, PreferredPrimitiveType hint)
948 {
949     // Must call toString first for Date objects.
950     if ((hint == PreferString) || (hint != PreferNumber && object->prototype() == exec->lexicalGlobalObject()->datePrototype())) {
951         JSValue value = callDefaultValueFunction(exec, object, exec->propertyNames().toString);
952         if (value)
953             return value;
954         value = callDefaultValueFunction(exec, object, exec->propertyNames().valueOf);
955         if (value)
956             return value;
957     } else {
958         JSValue value = callDefaultValueFunction(exec, object, exec->propertyNames().valueOf);
959         if (value)
960             return value;
961         value = callDefaultValueFunction(exec, object, exec->propertyNames().toString);
962         if (value)
963             return value;
964     }
965
966     ASSERT(!exec->hadException());
967
968     return throwError(exec, createTypeError(exec, ASCIILiteral("No default value")));
969 }
970
971 const HashEntry* JSObject::findPropertyHashEntry(ExecState* exec, PropertyName propertyName) const
972 {
973     for (const ClassInfo* info = classInfo(); info; info = info->parentClass) {
974         if (const HashTable* propHashTable = info->propHashTable(exec)) {
975             if (const HashEntry* entry = propHashTable->entry(exec, propertyName))
976                 return entry;
977         }
978     }
979     return 0;
980 }
981
982 bool JSObject::hasInstance(ExecState* exec, JSValue value)
983 {
984     TypeInfo info = structure()->typeInfo();
985     if (info.implementsDefaultHasInstance())
986         return defaultHasInstance(exec, value, get(exec, exec->propertyNames().prototype));
987     if (info.implementsHasInstance())
988         return methodTable()->customHasInstance(this, exec, value);
989     throwError(exec, createInvalidParamError(exec, "instanceof" , this));
990     return false;
991 }
992
993 bool JSObject::defaultHasInstance(ExecState* exec, JSValue value, JSValue proto)
994 {
995     if (!value.isObject())
996         return false;
997
998     if (!proto.isObject()) {
999         throwError(exec, createTypeError(exec, ASCIILiteral("instanceof called on an object with an invalid prototype property.")));
1000         return false;
1001     }
1002
1003     JSObject* object = asObject(value);
1004     while ((object = object->prototype().getObject())) {
1005         if (proto == object)
1006             return true;
1007     }
1008     return false;
1009 }
1010
1011 bool JSObject::propertyIsEnumerable(ExecState* exec, const Identifier& propertyName) const
1012 {
1013     PropertyDescriptor descriptor;
1014     if (!const_cast<JSObject*>(this)->methodTable()->getOwnPropertyDescriptor(const_cast<JSObject*>(this), exec, propertyName, descriptor))
1015         return false;
1016     return descriptor.enumerable();
1017 }
1018
1019 bool JSObject::getPropertySpecificValue(ExecState* exec, PropertyName propertyName, JSCell*& specificValue) const
1020 {
1021     unsigned attributes;
1022     if (isValidOffset(structure()->get(exec->globalData(), propertyName, attributes, specificValue)))
1023         return true;
1024
1025     // This could be a function within the static table? - should probably
1026     // also look in the hash?  This currently should not be a problem, since
1027     // we've currently always call 'get' first, which should have populated
1028     // the normal storage.
1029     return false;
1030 }
1031
1032 void JSObject::getPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
1033 {
1034     object->methodTable()->getOwnPropertyNames(object, exec, propertyNames, mode);
1035
1036     if (object->prototype().isNull())
1037         return;
1038
1039     JSObject* prototype = asObject(object->prototype());
1040     while(1) {
1041         if (prototype->structure()->typeInfo().overridesGetPropertyNames()) {
1042             prototype->methodTable()->getPropertyNames(prototype, exec, propertyNames, mode);
1043             break;
1044         }
1045         prototype->methodTable()->getOwnPropertyNames(prototype, exec, propertyNames, mode);
1046         JSValue nextProto = prototype->prototype();
1047         if (nextProto.isNull())
1048             break;
1049         prototype = asObject(nextProto);
1050     }
1051 }
1052
1053 void JSObject::getOwnPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
1054 {
1055     // Add numeric properties first. That appears to be the accepted convention.
1056     // FIXME: Filling PropertyNameArray with an identifier for every integer
1057     // is incredibly inefficient for large arrays. We need a different approach,
1058     // which almost certainly means a different structure for PropertyNameArray.
1059     switch (object->structure()->indexingType()) {
1060     case ALL_BLANK_INDEXING_TYPES:
1061         break;
1062         
1063     case ALL_CONTIGUOUS_INDEXING_TYPES: {
1064         Butterfly* butterfly = object->m_butterfly;
1065         unsigned usedLength = butterfly->publicLength();
1066         for (unsigned i = 0; i < usedLength; ++i) {
1067             if (!butterfly->contiguous()[i])
1068                 continue;
1069             propertyNames.add(Identifier::from(exec, i));
1070         }
1071         break;
1072     }
1073         
1074     case ALL_ARRAY_STORAGE_INDEXING_TYPES: {
1075         ArrayStorage* storage = object->m_butterfly->arrayStorage();
1076         
1077         unsigned usedVectorLength = std::min(storage->length(), storage->vectorLength());
1078         for (unsigned i = 0; i < usedVectorLength; ++i) {
1079             if (storage->m_vector[i])
1080                 propertyNames.add(Identifier::from(exec, i));
1081         }
1082         
1083         if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
1084             Vector<unsigned> keys;
1085             keys.reserveCapacity(map->size());
1086             
1087             SparseArrayValueMap::const_iterator end = map->end();
1088             for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
1089                 if (mode == IncludeDontEnumProperties || !(it->value.attributes & DontEnum))
1090                     keys.append(static_cast<unsigned>(it->key));
1091             }
1092             
1093             std::sort(keys.begin(), keys.end());
1094             for (unsigned i = 0; i < keys.size(); ++i)
1095                 propertyNames.add(Identifier::from(exec, keys[i]));
1096         }
1097         break;
1098     }
1099         
1100     default:
1101         ASSERT_NOT_REACHED();
1102     }
1103     
1104     object->methodTable()->getOwnNonIndexPropertyNames(object, exec, propertyNames, mode);
1105 }
1106
1107 void JSObject::getOwnNonIndexPropertyNames(JSObject* object, ExecState* exec, PropertyNameArray& propertyNames, EnumerationMode mode)
1108 {
1109     getClassPropertyNames(exec, object->classInfo(), propertyNames, mode, object->staticFunctionsReified());
1110     object->structure()->getPropertyNamesFromStructure(exec->globalData(), propertyNames, mode);
1111 }
1112
1113 double JSObject::toNumber(ExecState* exec) const
1114 {
1115     JSValue primitive = toPrimitive(exec, PreferNumber);
1116     if (exec->hadException()) // should be picked up soon in Nodes.cpp
1117         return 0.0;
1118     return primitive.toNumber(exec);
1119 }
1120
1121 JSString* JSObject::toString(ExecState* exec) const
1122 {
1123     JSValue primitive = toPrimitive(exec, PreferString);
1124     if (exec->hadException())
1125         return jsEmptyString(exec);
1126     return primitive.toString(exec);
1127 }
1128
1129 JSObject* JSObject::toThisObject(JSCell* cell, ExecState*)
1130 {
1131     return jsCast<JSObject*>(cell);
1132 }
1133
1134 void JSObject::seal(JSGlobalData& globalData)
1135 {
1136     if (isSealed(globalData))
1137         return;
1138     preventExtensions(globalData);
1139     setStructure(globalData, Structure::sealTransition(globalData, structure()));
1140 }
1141
1142 void JSObject::freeze(JSGlobalData& globalData)
1143 {
1144     if (isFrozen(globalData))
1145         return;
1146     preventExtensions(globalData);
1147     setStructure(globalData, Structure::freezeTransition(globalData, structure()));
1148 }
1149
1150 void JSObject::preventExtensions(JSGlobalData& globalData)
1151 {
1152     enterDictionaryIndexingMode(globalData);
1153     if (isExtensible())
1154         setStructure(globalData, Structure::preventExtensionsTransition(globalData, structure()));
1155 }
1156
1157 // This presently will flatten to an uncachable dictionary; this is suitable
1158 // for use in delete, we may want to do something different elsewhere.
1159 void JSObject::reifyStaticFunctionsForDelete(ExecState* exec)
1160 {
1161     ASSERT(!staticFunctionsReified());
1162     JSGlobalData& globalData = exec->globalData();
1163
1164     // If this object's ClassInfo has no static properties, then nothing to reify!
1165     // We can safely set the flag to avoid the expensive check again in the future.
1166     if (!classInfo()->hasStaticProperties()) {
1167         structure()->setStaticFunctionsReified();
1168         return;
1169     }
1170
1171     if (!structure()->isUncacheableDictionary())
1172         setStructure(globalData, Structure::toUncacheableDictionaryTransition(globalData, structure()));
1173
1174     for (const ClassInfo* info = classInfo(); info; info = info->parentClass) {
1175         const HashTable* hashTable = info->propHashTable(globalObject()->globalExec());
1176         if (!hashTable)
1177             continue;
1178         PropertySlot slot;
1179         for (HashTable::ConstIterator iter = hashTable->begin(globalData); iter != hashTable->end(globalData); ++iter) {
1180             if (iter->attributes() & Function)
1181                 setUpStaticFunctionSlot(globalObject()->globalExec(), *iter, this, Identifier(&globalData, iter->key()), slot);
1182         }
1183     }
1184
1185     structure()->setStaticFunctionsReified();
1186 }
1187
1188 bool JSObject::removeDirect(JSGlobalData& globalData, PropertyName propertyName)
1189 {
1190     if (!isValidOffset(structure()->get(globalData, propertyName)))
1191         return false;
1192
1193     PropertyOffset offset;
1194     if (structure()->isUncacheableDictionary()) {
1195         offset = structure()->removePropertyWithoutTransition(globalData, propertyName);
1196         if (offset == invalidOffset)
1197             return false;
1198         putUndefinedAtDirectOffset(offset);
1199         return true;
1200     }
1201
1202     setStructure(globalData, Structure::removePropertyTransition(globalData, structure(), propertyName, offset));
1203     if (offset == invalidOffset)
1204         return false;
1205     putUndefinedAtDirectOffset(offset);
1206     return true;
1207 }
1208
1209 NEVER_INLINE void JSObject::fillGetterPropertySlot(PropertySlot& slot, PropertyOffset offset)
1210 {
1211     if (JSObject* getterFunction = asGetterSetter(getDirectOffset(offset))->getter()) {
1212         if (!structure()->isDictionary())
1213             slot.setCacheableGetterSlot(this, getterFunction, offset);
1214         else
1215             slot.setGetterSlot(getterFunction);
1216     } else
1217         slot.setUndefined();
1218 }
1219
1220 void JSObject::notifyUsedAsPrototype(JSGlobalData& globalData)
1221 {
1222     PropertyOffset offset = structure()->get(globalData, globalData.m_inheritorIDKey);
1223     if (isValidOffset(offset))
1224         return;
1225     
1226     PutPropertySlot slot;
1227     putDirectInternal<PutModeDefineOwnProperty>(globalData, globalData.m_inheritorIDKey, jsUndefined(), DontEnum, slot, 0);
1228     
1229     // Note that this method makes the somewhat odd decision to not check if this
1230     // object currently has indexed accessors. We could do that check here, and if
1231     // indexed accessors were found, we could tell the global object to have a bad
1232     // time. But we avoid this, to allow the following to be always fast:
1233     //
1234     // 1) Create an object.
1235     // 2) Give it a setter or read-only property that happens to have a numeric name.
1236     // 3) Allocate objects that use this object as a prototype.
1237     //
1238     // This avoids anyone having a bad time. Even if the instance objects end up
1239     // having indexed storage, the creation of indexed storage leads to a prototype
1240     // chain walk that detects the presence of indexed setters and then does the
1241     // right thing. As a result, having a bad time only happens if you add an
1242     // indexed setter (or getter, or read-only field) to an object that is already
1243     // used as a prototype.
1244 }
1245
1246 Structure* JSObject::createInheritorID(JSGlobalData& globalData)
1247 {
1248     Structure* inheritorID = createEmptyObjectStructure(globalData, globalObject(), this);
1249     ASSERT(inheritorID->isEmpty());
1250
1251     PutPropertySlot slot;
1252     putDirectInternal<PutModeDefineOwnProperty>(globalData, globalData.m_inheritorIDKey, inheritorID, DontEnum, slot, 0);
1253     return inheritorID;
1254 }
1255
1256 void JSObject::putIndexedDescriptor(ExecState* exec, SparseArrayEntry* entryInMap, PropertyDescriptor& descriptor, PropertyDescriptor& oldDescriptor)
1257 {
1258     if (descriptor.isDataDescriptor()) {
1259         if (descriptor.value())
1260             entryInMap->set(exec->globalData(), this, descriptor.value());
1261         else if (oldDescriptor.isAccessorDescriptor())
1262             entryInMap->set(exec->globalData(), this, jsUndefined());
1263         entryInMap->attributes = descriptor.attributesOverridingCurrent(oldDescriptor) & ~Accessor;
1264         return;
1265     }
1266
1267     if (descriptor.isAccessorDescriptor()) {
1268         JSObject* getter = 0;
1269         if (descriptor.getterPresent())
1270             getter = descriptor.getterObject();
1271         else if (oldDescriptor.isAccessorDescriptor())
1272             getter = oldDescriptor.getterObject();
1273         JSObject* setter = 0;
1274         if (descriptor.setterPresent())
1275             setter = descriptor.setterObject();
1276         else if (oldDescriptor.isAccessorDescriptor())
1277             setter = oldDescriptor.setterObject();
1278
1279         GetterSetter* accessor = GetterSetter::create(exec);
1280         if (getter)
1281             accessor->setGetter(exec->globalData(), getter);
1282         if (setter)
1283             accessor->setSetter(exec->globalData(), setter);
1284
1285         entryInMap->set(exec->globalData(), this, accessor);
1286         entryInMap->attributes = descriptor.attributesOverridingCurrent(oldDescriptor) & ~ReadOnly;
1287         return;
1288     }
1289
1290     ASSERT(descriptor.isGenericDescriptor());
1291     entryInMap->attributes = descriptor.attributesOverridingCurrent(oldDescriptor);
1292 }
1293
1294 // Defined in ES5.1 8.12.9
1295 bool JSObject::defineOwnIndexedProperty(ExecState* exec, unsigned index, PropertyDescriptor& descriptor, bool throwException)
1296 {
1297     ASSERT(index <= MAX_ARRAY_INDEX);
1298     
1299     if (!inSparseIndexingMode()) {
1300         // Fast case: we're putting a regular property to a regular array
1301         // FIXME: this will pessimistically assume that if attributes are missing then they'll default to false
1302         // however if the property currently exists missing attributes will override from their current 'true'
1303         // state (i.e. defineOwnProperty could be used to set a value without needing to entering 'SparseMode').
1304         if (!descriptor.attributes()) {
1305             ASSERT(!descriptor.isAccessorDescriptor());
1306             return putDirectIndex(exec, index, descriptor.value(), 0, throwException ? PutDirectIndexShouldThrow : PutDirectIndexShouldNotThrow);
1307         }
1308         
1309         ensureArrayStorageExistsAndEnterDictionaryIndexingMode(exec->globalData());
1310     }
1311
1312     if (descriptor.attributes() & (ReadOnly | Accessor))
1313         notifyPresenceOfIndexedAccessors(exec->globalData());
1314
1315     SparseArrayValueMap* map = m_butterfly->arrayStorage()->m_sparseMap.get();
1316     ASSERT(map);
1317
1318     // 1. Let current be the result of calling the [[GetOwnProperty]] internal method of O with property name P.
1319     SparseArrayValueMap::AddResult result = map->add(this, index);
1320     SparseArrayEntry* entryInMap = &result.iterator->value;
1321
1322     // 2. Let extensible be the value of the [[Extensible]] internal property of O.
1323     // 3. If current is undefined and extensible is false, then Reject.
1324     // 4. If current is undefined and extensible is true, then
1325     if (result.isNewEntry) {
1326         if (!isExtensible()) {
1327             map->remove(result.iterator);
1328             return reject(exec, throwException, "Attempting to define property on object that is not extensible.");
1329         }
1330
1331         // 4.a. If IsGenericDescriptor(Desc) or IsDataDescriptor(Desc) is true, then create an own data property
1332         // named P of object O whose [[Value]], [[Writable]], [[Enumerable]] and [[Configurable]] attribute values
1333         // are described by Desc. If the value of an attribute field of Desc is absent, the attribute of the newly
1334         // created property is set to its default value.
1335         // 4.b. Else, Desc must be an accessor Property Descriptor so, create an own accessor property named P of
1336         // object O whose [[Get]], [[Set]], [[Enumerable]] and [[Configurable]] attribute values are described by
1337         // Desc. If the value of an attribute field of Desc is absent, the attribute of the newly created property
1338         // is set to its default value.
1339         // 4.c. Return true.
1340
1341         PropertyDescriptor defaults;
1342         entryInMap->setWithoutWriteBarrier(jsUndefined());
1343         entryInMap->attributes = DontDelete | DontEnum | ReadOnly;
1344         entryInMap->get(defaults);
1345
1346         putIndexedDescriptor(exec, entryInMap, descriptor, defaults);
1347         if (index >= m_butterfly->arrayStorage()->length())
1348             m_butterfly->arrayStorage()->setLength(index + 1);
1349         return true;
1350     }
1351
1352     // 5. Return true, if every field in Desc is absent.
1353     // 6. Return true, if every field in Desc also occurs in current and the value of every field in Desc is the same value as the corresponding field in current when compared using the SameValue algorithm (9.12).
1354     PropertyDescriptor current;
1355     entryInMap->get(current);
1356     if (descriptor.isEmpty() || descriptor.equalTo(exec, current))
1357         return true;
1358
1359     // 7. If the [[Configurable]] field of current is false then
1360     if (!current.configurable()) {
1361         // 7.a. Reject, if the [[Configurable]] field of Desc is true.
1362         if (descriptor.configurablePresent() && descriptor.configurable())
1363             return reject(exec, throwException, "Attempting to change configurable attribute of unconfigurable property.");
1364         // 7.b. Reject, if the [[Enumerable]] field of Desc is present and the [[Enumerable]] fields of current and Desc are the Boolean negation of each other.
1365         if (descriptor.enumerablePresent() && current.enumerable() != descriptor.enumerable())
1366             return reject(exec, throwException, "Attempting to change enumerable attribute of unconfigurable property.");
1367     }
1368
1369     // 8. If IsGenericDescriptor(Desc) is true, then no further validation is required.
1370     if (!descriptor.isGenericDescriptor()) {
1371         // 9. Else, if IsDataDescriptor(current) and IsDataDescriptor(Desc) have different results, then
1372         if (current.isDataDescriptor() != descriptor.isDataDescriptor()) {
1373             // 9.a. Reject, if the [[Configurable]] field of current is false.
1374             if (!current.configurable())
1375                 return reject(exec, throwException, "Attempting to change access mechanism for an unconfigurable property.");
1376             // 9.b. If IsDataDescriptor(current) is true, then convert the property named P of object O from a
1377             // data property to an accessor property. Preserve the existing values of the converted property's
1378             // [[Configurable]] and [[Enumerable]] attributes and set the rest of the property's attributes to
1379             // their default values.
1380             // 9.c. Else, convert the property named P of object O from an accessor property to a data property.
1381             // Preserve the existing values of the converted property's [[Configurable]] and [[Enumerable]]
1382             // attributes and set the rest of the property's attributes to their default values.
1383         } else if (current.isDataDescriptor() && descriptor.isDataDescriptor()) {
1384             // 10. Else, if IsDataDescriptor(current) and IsDataDescriptor(Desc) are both true, then
1385             // 10.a. If the [[Configurable]] field of current is false, then
1386             if (!current.configurable() && !current.writable()) {
1387                 // 10.a.i. Reject, if the [[Writable]] field of current is false and the [[Writable]] field of Desc is true.
1388                 if (descriptor.writable())
1389                     return reject(exec, throwException, "Attempting to change writable attribute of unconfigurable property.");
1390                 // 10.a.ii. If the [[Writable]] field of current is false, then
1391                 // 10.a.ii.1. Reject, if the [[Value]] field of Desc is present and SameValue(Desc.[[Value]], current.[[Value]]) is false.
1392                 if (descriptor.value() && !sameValue(exec, descriptor.value(), current.value()))
1393                     return reject(exec, throwException, "Attempting to change value of a readonly property.");
1394             }
1395             // 10.b. else, the [[Configurable]] field of current is true, so any change is acceptable.
1396         } else {
1397             ASSERT(current.isAccessorDescriptor() && current.getterPresent() && current.setterPresent());
1398             // 11. Else, IsAccessorDescriptor(current) and IsAccessorDescriptor(Desc) are both true so, if the [[Configurable]] field of current is false, then
1399             if (!current.configurable()) {
1400                 // 11.i. Reject, if the [[Set]] field of Desc is present and SameValue(Desc.[[Set]], current.[[Set]]) is false.
1401                 if (descriptor.setterPresent() && descriptor.setter() != current.setter())
1402                     return reject(exec, throwException, "Attempting to change the setter of an unconfigurable property.");
1403                 // 11.ii. Reject, if the [[Get]] field of Desc is present and SameValue(Desc.[[Get]], current.[[Get]]) is false.
1404                 if (descriptor.getterPresent() && descriptor.getter() != current.getter())
1405                     return reject(exec, throwException, "Attempting to change the getter of an unconfigurable property.");
1406             }
1407         }
1408     }
1409
1410     // 12. For each attribute field of Desc that is present, set the correspondingly named attribute of the property named P of object O to the value of the field.
1411     putIndexedDescriptor(exec, entryInMap, descriptor, current);
1412     // 13. Return true.
1413     return true;
1414 }
1415
1416 SparseArrayValueMap* JSObject::allocateSparseIndexMap(JSGlobalData& globalData)
1417 {
1418     SparseArrayValueMap* result = SparseArrayValueMap::create(globalData);
1419     arrayStorage()->m_sparseMap.set(globalData, this, result);
1420     return result;
1421 }
1422
1423 void JSObject::deallocateSparseIndexMap()
1424 {
1425     if (ArrayStorage* arrayStorage = arrayStorageOrNull())
1426         arrayStorage->m_sparseMap.clear();
1427 }
1428
1429 bool JSObject::attemptToInterceptPutByIndexOnHoleForPrototype(ExecState* exec, JSValue thisValue, unsigned i, JSValue value, bool shouldThrow)
1430 {
1431     for (JSObject* current = this; ;) {
1432         // This has the same behavior with respect to prototypes as JSObject::put(). It only
1433         // allows a prototype to intercept a put if (a) the prototype declares the property
1434         // we're after rather than intercepting it via an override of JSObject::put(), and
1435         // (b) that property is declared as ReadOnly or Accessor.
1436         
1437         ArrayStorage* storage = current->arrayStorageOrNull();
1438         if (storage && storage->m_sparseMap) {
1439             SparseArrayValueMap::iterator iter = storage->m_sparseMap->find(i);
1440             if (iter != storage->m_sparseMap->notFound() && (iter->value.attributes & (Accessor | ReadOnly))) {
1441                 iter->value.put(exec, thisValue, storage->m_sparseMap.get(), value, shouldThrow);
1442                 return true;
1443             }
1444         }
1445         
1446         JSValue prototypeValue = current->prototype();
1447         if (prototypeValue.isNull())
1448             return false;
1449         
1450         current = asObject(prototypeValue);
1451     }
1452 }
1453
1454 bool JSObject::attemptToInterceptPutByIndexOnHole(ExecState* exec, unsigned i, JSValue value, bool shouldThrow)
1455 {
1456     JSValue prototypeValue = prototype();
1457     if (prototypeValue.isNull())
1458         return false;
1459     
1460     return asObject(prototypeValue)->attemptToInterceptPutByIndexOnHoleForPrototype(exec, this, i, value, shouldThrow);
1461 }
1462
1463 void JSObject::putByIndexBeyondVectorLengthContiguousWithoutAttributes(ExecState* exec, unsigned i, JSValue value)
1464 {
1465     ASSERT(hasContiguous(structure()->indexingType()));
1466     ASSERT(!indexingShouldBeSparse());
1467     
1468     // For us to get here, the index is either greater than the public length, or greater than
1469     // or equal to the vector length.
1470     ASSERT(i >= m_butterfly->vectorLength());
1471     
1472     JSGlobalData& globalData = exec->globalData();
1473     
1474     if (i >= MAX_ARRAY_INDEX - 1
1475         || (i >= MIN_SPARSE_ARRAY_INDEX
1476             && !isDenseEnoughForVector(i, countElementsInContiguous(m_butterfly)))) {
1477         ASSERT(i <= MAX_ARRAY_INDEX);
1478         convertContiguousToArrayStorage(globalData, AllocateArrayStorage);
1479         SparseArrayValueMap* map = allocateSparseIndexMap(globalData);
1480         map->putEntry(exec, this, i, value, false);
1481         ASSERT(i >= arrayStorage()->length());
1482         arrayStorage()->setLength(i + 1);
1483         return;
1484     }
1485
1486     ensureContiguousLength(globalData, i + 1);
1487
1488     ASSERT(i < m_butterfly->vectorLength());
1489     m_butterfly->contiguous()[i].set(globalData, this, value);
1490 }
1491
1492 void JSObject::putByIndexBeyondVectorLengthWithArrayStorage(ExecState* exec, unsigned i, JSValue value, bool shouldThrow, ArrayStorage* storage)
1493 {
1494     JSGlobalData& globalData = exec->globalData();
1495
1496     // i should be a valid array index that is outside of the current vector.
1497     ASSERT(i <= MAX_ARRAY_INDEX);
1498     ASSERT(i >= storage->vectorLength());
1499     
1500     SparseArrayValueMap* map = storage->m_sparseMap.get();
1501     
1502     // First, handle cases where we don't currently have a sparse map.
1503     if (LIKELY(!map)) {
1504         // If the array is not extensible, we should have entered dictionary mode, and created the spare map.
1505         ASSERT(isExtensible());
1506     
1507         // Update m_length if necessary.
1508         if (i >= storage->length())
1509             storage->setLength(i + 1);
1510
1511         // Check that it is sensible to still be using a vector, and then try to grow the vector.
1512         if (LIKELY((isDenseEnoughForVector(i, storage->m_numValuesInVector)) && increaseVectorLength(globalData, i + 1))) {
1513             // success! - reread m_storage since it has likely been reallocated, and store to the vector.
1514             storage = arrayStorage();
1515             storage->m_vector[i].set(globalData, this, value);
1516             ++storage->m_numValuesInVector;
1517             return;
1518         }
1519         // We don't want to, or can't use a vector to hold this property - allocate a sparse map & add the value.
1520         map = allocateSparseIndexMap(exec->globalData());
1521         map->putEntry(exec, this, i, value, shouldThrow);
1522         return;
1523     }
1524
1525     // Update m_length if necessary.
1526     unsigned length = storage->length();
1527     if (i >= length) {
1528         // Prohibit growing the array if length is not writable.
1529         if (map->lengthIsReadOnly() || !isExtensible()) {
1530             if (shouldThrow)
1531                 throwTypeError(exec, StrictModeReadonlyPropertyWriteError);
1532             return;
1533         }
1534         length = i + 1;
1535         storage->setLength(length);
1536     }
1537
1538     // We are currently using a map - check whether we still want to be doing so.
1539     // We will continue  to use a sparse map if SparseMode is set, a vector would be too sparse, or if allocation fails.
1540     unsigned numValuesInArray = storage->m_numValuesInVector + map->size();
1541     if (map->sparseMode() || !isDenseEnoughForVector(length, numValuesInArray) || !increaseVectorLength(exec->globalData(), length)) {
1542         map->putEntry(exec, this, i, value, shouldThrow);
1543         return;
1544     }
1545
1546     // Reread m_storage after increaseVectorLength, update m_numValuesInVector.
1547     storage = arrayStorage();
1548     storage->m_numValuesInVector = numValuesInArray;
1549
1550     // Copy all values from the map into the vector, and delete the map.
1551     WriteBarrier<Unknown>* vector = storage->m_vector;
1552     SparseArrayValueMap::const_iterator end = map->end();
1553     for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
1554         vector[it->key].set(globalData, this, it->value.getNonSparseMode());
1555     deallocateSparseIndexMap();
1556
1557     // Store the new property into the vector.
1558     WriteBarrier<Unknown>& valueSlot = vector[i];
1559     if (!valueSlot)
1560         ++storage->m_numValuesInVector;
1561     valueSlot.set(globalData, this, value);
1562 }
1563
1564 void JSObject::putByIndexBeyondVectorLength(ExecState* exec, unsigned i, JSValue value, bool shouldThrow)
1565 {
1566     JSGlobalData& globalData = exec->globalData();
1567
1568     // i should be a valid array index that is outside of the current vector.
1569     ASSERT(i <= MAX_ARRAY_INDEX);
1570     
1571     switch (structure()->indexingType()) {
1572     case ALL_BLANK_INDEXING_TYPES: {
1573         if (indexingShouldBeSparse()) {
1574             putByIndexBeyondVectorLengthWithArrayStorage(
1575                 exec, i, value, shouldThrow,
1576                 ensureArrayStorageExistsAndEnterDictionaryIndexingMode(globalData));
1577             break;
1578         }
1579         if (i >= MIN_SPARSE_ARRAY_INDEX) {
1580             putByIndexBeyondVectorLengthWithArrayStorage(
1581                 exec, i, value, shouldThrow, createArrayStorage(globalData, 0, 0));
1582             break;
1583         }
1584         if (structure()->needsSlowPutIndexing()) {
1585             ArrayStorage* storage = createArrayStorage(globalData, i + 1, getNewVectorLength(0, 0, i + 1));
1586             storage->m_vector[i].set(globalData, this, value);
1587             storage->m_numValuesInVector++;
1588             break;
1589         }
1590             
1591         createInitialContiguous(globalData, i + 1)[i].set(globalData, this, value);
1592         break;
1593     }
1594         
1595     case ALL_CONTIGUOUS_INDEXING_TYPES: {
1596         putByIndexBeyondVectorLengthContiguousWithoutAttributes(exec, i, value);
1597         break;
1598     }
1599         
1600     case NonArrayWithSlowPutArrayStorage:
1601     case ArrayWithSlowPutArrayStorage: {
1602         // No own property present in the vector, but there might be in the sparse map!
1603         SparseArrayValueMap* map = arrayStorage()->m_sparseMap.get();
1604         if (!(map && map->contains(i)) && attemptToInterceptPutByIndexOnHole(exec, i, value, shouldThrow))
1605             return;
1606         // Otherwise, fall though.
1607     }
1608
1609     case NonArrayWithArrayStorage:
1610     case ArrayWithArrayStorage:
1611         putByIndexBeyondVectorLengthWithArrayStorage(exec, i, value, shouldThrow, arrayStorage());
1612         break;
1613         
1614     default:
1615         ASSERT_NOT_REACHED();
1616     }
1617 }
1618
1619 bool JSObject::putDirectIndexBeyondVectorLengthWithArrayStorage(ExecState* exec, unsigned i, JSValue value, unsigned attributes, PutDirectIndexMode mode, ArrayStorage* storage)
1620 {
1621     JSGlobalData& globalData = exec->globalData();
1622     
1623     // i should be a valid array index that is outside of the current vector.
1624     ASSERT(hasArrayStorage(structure()->indexingType()));
1625     ASSERT(arrayStorage() == storage);
1626     ASSERT(i >= storage->vectorLength() || attributes);
1627     ASSERT(i <= MAX_ARRAY_INDEX);
1628
1629     SparseArrayValueMap* map = storage->m_sparseMap.get();
1630
1631     // First, handle cases where we don't currently have a sparse map.
1632     if (LIKELY(!map)) {
1633         // If the array is not extensible, we should have entered dictionary mode, and created the spare map.
1634         ASSERT(isExtensible());
1635     
1636         // Update m_length if necessary.
1637         if (i >= storage->length())
1638             storage->setLength(i + 1);
1639
1640         // Check that it is sensible to still be using a vector, and then try to grow the vector.
1641         if (LIKELY(
1642                 !attributes
1643                 && (isDenseEnoughForVector(i, storage->m_numValuesInVector))
1644                 && increaseVectorLength(globalData, i + 1))) {
1645             // success! - reread m_storage since it has likely been reallocated, and store to the vector.
1646             storage = arrayStorage();
1647             storage->m_vector[i].set(globalData, this, value);
1648             ++storage->m_numValuesInVector;
1649             return true;
1650         }
1651         // We don't want to, or can't use a vector to hold this property - allocate a sparse map & add the value.
1652         map = allocateSparseIndexMap(exec->globalData());
1653         return map->putDirect(exec, this, i, value, attributes, mode);
1654     }
1655
1656     // Update m_length if necessary.
1657     unsigned length = storage->length();
1658     if (i >= length) {
1659         if (mode != PutDirectIndexLikePutDirect) {
1660             // Prohibit growing the array if length is not writable.
1661             if (map->lengthIsReadOnly())
1662                 return reject(exec, mode == PutDirectIndexShouldThrow, StrictModeReadonlyPropertyWriteError);
1663             if (!isExtensible())
1664                 return reject(exec, mode == PutDirectIndexShouldThrow, "Attempting to define property on object that is not extensible.");
1665         }
1666         length = i + 1;
1667         storage->setLength(length);
1668     }
1669
1670     // We are currently using a map - check whether we still want to be doing so.
1671     // We will continue  to use a sparse map if SparseMode is set, a vector would be too sparse, or if allocation fails.
1672     unsigned numValuesInArray = storage->m_numValuesInVector + map->size();
1673     if (map->sparseMode() || attributes || !isDenseEnoughForVector(length, numValuesInArray) || !increaseVectorLength(exec->globalData(), length))
1674         return map->putDirect(exec, this, i, value, attributes, mode);
1675
1676     // Reread m_storage after increaseVectorLength, update m_numValuesInVector.
1677     storage = arrayStorage();
1678     storage->m_numValuesInVector = numValuesInArray;
1679
1680     // Copy all values from the map into the vector, and delete the map.
1681     WriteBarrier<Unknown>* vector = storage->m_vector;
1682     SparseArrayValueMap::const_iterator end = map->end();
1683     for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it)
1684         vector[it->key].set(globalData, this, it->value.getNonSparseMode());
1685     deallocateSparseIndexMap();
1686
1687     // Store the new property into the vector.
1688     WriteBarrier<Unknown>& valueSlot = vector[i];
1689     if (!valueSlot)
1690         ++storage->m_numValuesInVector;
1691     valueSlot.set(globalData, this, value);
1692     return true;
1693 }
1694
1695 bool JSObject::putDirectIndexBeyondVectorLength(ExecState* exec, unsigned i, JSValue value, unsigned attributes, PutDirectIndexMode mode)
1696 {
1697     JSGlobalData& globalData = exec->globalData();
1698
1699     // i should be a valid array index that is outside of the current vector.
1700     ASSERT(i <= MAX_ARRAY_INDEX);
1701     
1702     if (attributes & (ReadOnly | Accessor))
1703         notifyPresenceOfIndexedAccessors(globalData);
1704     
1705     switch (structure()->indexingType()) {
1706     case ALL_BLANK_INDEXING_TYPES: {
1707         if (indexingShouldBeSparse() || attributes) {
1708             return putDirectIndexBeyondVectorLengthWithArrayStorage(
1709                 exec, i, value, attributes, mode,
1710                 ensureArrayStorageExistsAndEnterDictionaryIndexingMode(globalData));
1711         }
1712         if (i >= MIN_SPARSE_ARRAY_INDEX) {
1713             return putDirectIndexBeyondVectorLengthWithArrayStorage(
1714                 exec, i, value, attributes, mode, createArrayStorage(globalData, 0, 0));
1715         }
1716         if (structure()->needsSlowPutIndexing()) {
1717             ArrayStorage* storage = createArrayStorage(globalData, i + 1, getNewVectorLength(0, 0, i + 1));
1718             storage->m_vector[i].set(globalData, this, value);
1719             storage->m_numValuesInVector++;
1720             return true;
1721         }
1722         
1723         createInitialContiguous(globalData, i + 1)[i].set(globalData, this, value);
1724         return true;
1725     }
1726         
1727     case ALL_CONTIGUOUS_INDEXING_TYPES: {
1728         if (attributes & (ReadOnly | Accessor)) {
1729             return putDirectIndexBeyondVectorLengthWithArrayStorage(
1730                 exec, i, value, attributes, mode, convertContiguousToArrayStorage(globalData));
1731         }
1732         putByIndexBeyondVectorLengthContiguousWithoutAttributes(exec, i, value);
1733         return true;
1734     }
1735
1736     case ALL_ARRAY_STORAGE_INDEXING_TYPES:
1737         return putDirectIndexBeyondVectorLengthWithArrayStorage(exec, i, value, attributes, mode, arrayStorage());
1738         
1739     default:
1740         ASSERT_NOT_REACHED();
1741         return false;
1742     }
1743 }
1744
1745 ALWAYS_INLINE unsigned JSObject::getNewVectorLength(unsigned currentVectorLength, unsigned currentLength, unsigned desiredLength)
1746 {
1747     ASSERT(desiredLength <= MAX_STORAGE_VECTOR_LENGTH);
1748
1749     unsigned increasedLength;
1750     unsigned maxInitLength = std::min(currentLength, 100000U);
1751
1752     if (desiredLength < maxInitLength)
1753         increasedLength = maxInitLength;
1754     else if (!currentVectorLength)
1755         increasedLength = std::max(desiredLength, lastArraySize);
1756     else {
1757         increasedLength = timesThreePlusOneDividedByTwo(desiredLength);
1758     }
1759
1760     ASSERT(increasedLength >= desiredLength);
1761
1762     lastArraySize = std::min(increasedLength, FIRST_VECTOR_GROW);
1763
1764     return std::min(increasedLength, MAX_STORAGE_VECTOR_LENGTH);
1765 }
1766
1767 ALWAYS_INLINE unsigned JSObject::getNewVectorLength(unsigned desiredLength)
1768 {
1769     unsigned vectorLength;
1770     unsigned length;
1771     
1772     switch (structure()->indexingType()) {
1773     case ALL_BLANK_INDEXING_TYPES:
1774         vectorLength = 0;
1775         length = 0;
1776         break;
1777     case ALL_CONTIGUOUS_INDEXING_TYPES:
1778     case ALL_ARRAY_STORAGE_INDEXING_TYPES:
1779         vectorLength = m_butterfly->vectorLength();
1780         length = m_butterfly->publicLength();
1781         break;
1782     default:
1783         CRASH();
1784         return 0;
1785     }
1786     return getNewVectorLength(vectorLength, length, desiredLength);
1787 }
1788
1789 unsigned JSObject::countElementsInContiguous(Butterfly* butterfly)
1790 {
1791     unsigned numValues = 0;
1792     for (unsigned i = butterfly->publicLength(); i--;) {
1793         if (butterfly->contiguous()[i])
1794             numValues++;
1795     }
1796     return numValues;
1797 }
1798
1799 bool JSObject::increaseVectorLength(JSGlobalData& globalData, unsigned newLength)
1800 {
1801     // This function leaves the array in an internally inconsistent state, because it does not move any values from sparse value map
1802     // to the vector. Callers have to account for that, because they can do it more efficiently.
1803     if (newLength > MAX_STORAGE_VECTOR_LENGTH)
1804         return false;
1805
1806     ArrayStorage* storage = arrayStorage();
1807     
1808     if (newLength >= MIN_SPARSE_ARRAY_INDEX
1809         && !isDenseEnoughForVector(newLength, storage->m_numValuesInVector))
1810         return false;
1811
1812     unsigned indexBias = storage->m_indexBias;
1813     unsigned vectorLength = storage->vectorLength();
1814     ASSERT(newLength > vectorLength);
1815     unsigned newVectorLength = getNewVectorLength(newLength);
1816
1817     // Fast case - there is no precapacity. In these cases a realloc makes sense.
1818     if (LIKELY(!indexBias)) {
1819         Butterfly* newButterfly = storage->butterfly()->growArrayRight(globalData, structure(), structure()->outOfLineCapacity(), true, ArrayStorage::sizeFor(vectorLength), ArrayStorage::sizeFor(newVectorLength));
1820         if (!newButterfly)
1821             return false;
1822         m_butterfly = newButterfly;
1823         newButterfly->arrayStorage()->setVectorLength(newVectorLength);
1824         return true;
1825     }
1826     
1827     // Remove some, but not all of the precapacity. Atomic decay, & capped to not overflow array length.
1828     unsigned newIndexBias = std::min(indexBias >> 1, MAX_STORAGE_VECTOR_LENGTH - newVectorLength);
1829     Butterfly* newButterfly = storage->butterfly()->resizeArray(
1830         globalData,
1831         structure()->outOfLineCapacity(), true, ArrayStorage::sizeFor(vectorLength),
1832         newIndexBias, true, ArrayStorage::sizeFor(newVectorLength));
1833     if (!newButterfly)
1834         return false;
1835     
1836     m_butterfly = newButterfly;
1837     newButterfly->arrayStorage()->setVectorLength(newVectorLength);
1838     newButterfly->arrayStorage()->m_indexBias = newIndexBias;
1839     return true;
1840 }
1841
1842 void JSObject::ensureContiguousLengthSlow(JSGlobalData& globalData, unsigned length)
1843 {
1844     ASSERT(length < MAX_ARRAY_INDEX);
1845     ASSERT(hasContiguous(structure()->indexingType()));
1846     ASSERT(length > m_butterfly->vectorLength());
1847     
1848     unsigned newVectorLength = std::min(
1849         length << 1,
1850         MAX_STORAGE_VECTOR_LENGTH);
1851     m_butterfly = m_butterfly->growArrayRight(
1852         globalData, structure(), structure()->outOfLineCapacity(), true,
1853         m_butterfly->vectorLength() * sizeof(EncodedJSValue),
1854         newVectorLength * sizeof(EncodedJSValue));
1855     m_butterfly->setVectorLength(newVectorLength);
1856 }
1857
1858 Butterfly* JSObject::growOutOfLineStorage(JSGlobalData& globalData, size_t oldSize, size_t newSize)
1859 {
1860     ASSERT(newSize > oldSize);
1861
1862     // It's important that this function not rely on structure(), for the property
1863     // capacity, since we might have already mutated the structure in-place.
1864     
1865     return m_butterfly->growPropertyStorage(globalData, structure(), oldSize, newSize);
1866 }
1867
1868 bool JSObject::getOwnPropertyDescriptor(JSObject* object, ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor)
1869 {
1870     unsigned attributes = 0;
1871     JSCell* cell = 0;
1872     PropertyOffset offset = object->structure()->get(exec->globalData(), propertyName, attributes, cell);
1873     if (isValidOffset(offset)) {
1874         descriptor.setDescriptor(object->getDirectOffset(offset), attributes);
1875         return true;
1876     }
1877     
1878     unsigned i = propertyName.asIndex();
1879     if (i == PropertyName::NotAnIndex)
1880         return false;
1881     
1882     switch (object->structure()->indexingType()) {
1883     case ALL_BLANK_INDEXING_TYPES:
1884         return false;
1885         
1886     case ALL_CONTIGUOUS_INDEXING_TYPES: {
1887         Butterfly* butterfly = object->m_butterfly;
1888         if (i >= butterfly->vectorLength())
1889             return false;
1890         JSValue value = butterfly->contiguous()[i].get();
1891         if (!value)
1892             return false;
1893         descriptor.setDescriptor(value, 0);
1894         return true;
1895     }
1896         
1897     case ALL_ARRAY_STORAGE_INDEXING_TYPES: {
1898         ArrayStorage* storage = object->m_butterfly->arrayStorage();
1899         if (i >= storage->length())
1900             return false;
1901         if (i < storage->vectorLength()) {
1902             WriteBarrier<Unknown>& value = storage->m_vector[i];
1903             if (!value)
1904                 return false;
1905             descriptor.setDescriptor(value.get(), 0);
1906             return true;
1907         }
1908         if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
1909             SparseArrayValueMap::iterator it = map->find(i);
1910             if (it == map->notFound())
1911                 return false;
1912             it->value.get(descriptor);
1913             return true;
1914         }
1915         return false;
1916     }
1917         
1918     default:
1919         ASSERT_NOT_REACHED();
1920         return false;
1921     }
1922 }
1923
1924 bool JSObject::getPropertyDescriptor(ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor)
1925 {
1926     JSObject* object = this;
1927     while (true) {
1928         if (object->methodTable()->getOwnPropertyDescriptor(object, exec, propertyName, descriptor))
1929             return true;
1930         JSValue prototype = object->prototype();
1931         if (!prototype.isObject())
1932             return false;
1933         object = asObject(prototype);
1934     }
1935 }
1936
1937 static bool putDescriptor(ExecState* exec, JSObject* target, PropertyName propertyName, PropertyDescriptor& descriptor, unsigned attributes, const PropertyDescriptor& oldDescriptor)
1938 {
1939     if (descriptor.isGenericDescriptor() || descriptor.isDataDescriptor()) {
1940         if (descriptor.isGenericDescriptor() && oldDescriptor.isAccessorDescriptor()) {
1941             GetterSetter* accessor = GetterSetter::create(exec);
1942             if (oldDescriptor.getterPresent())
1943                 accessor->setGetter(exec->globalData(), oldDescriptor.getterObject());
1944             if (oldDescriptor.setterPresent())
1945                 accessor->setSetter(exec->globalData(), oldDescriptor.setterObject());
1946             target->putDirectAccessor(exec, propertyName, accessor, attributes | Accessor);
1947             return true;
1948         }
1949         JSValue newValue = jsUndefined();
1950         if (descriptor.value())
1951             newValue = descriptor.value();
1952         else if (oldDescriptor.value())
1953             newValue = oldDescriptor.value();
1954         target->putDirect(exec->globalData(), propertyName, newValue, attributes & ~Accessor);
1955         if (attributes & ReadOnly)
1956             target->structure()->setContainsReadOnlyProperties();
1957         return true;
1958     }
1959     attributes &= ~ReadOnly;
1960     GetterSetter* accessor = GetterSetter::create(exec);
1961
1962     if (descriptor.getterPresent())
1963         accessor->setGetter(exec->globalData(), descriptor.getterObject());
1964     else if (oldDescriptor.getterPresent())
1965         accessor->setGetter(exec->globalData(), oldDescriptor.getterObject());
1966     if (descriptor.setterPresent())
1967         accessor->setSetter(exec->globalData(), descriptor.setterObject());
1968     else if (oldDescriptor.setterPresent())
1969         accessor->setSetter(exec->globalData(), oldDescriptor.setterObject());
1970
1971     target->putDirectAccessor(exec, propertyName, accessor, attributes | Accessor);
1972     return true;
1973 }
1974
1975 void JSObject::putDirectMayBeIndex(ExecState* exec, PropertyName propertyName, JSValue value)
1976 {
1977     unsigned asIndex = propertyName.asIndex();
1978     if (asIndex == PropertyName::NotAnIndex)
1979         putDirect(exec->globalData(), propertyName, value);
1980     else
1981         putDirectIndex(exec, asIndex, value);
1982 }
1983
1984 class DefineOwnPropertyScope {
1985 public:
1986     DefineOwnPropertyScope(ExecState* exec)
1987         : m_globalData(exec->globalData())
1988     {
1989         m_globalData.setInDefineOwnProperty(true);
1990     }
1991
1992     ~DefineOwnPropertyScope()
1993     {
1994         m_globalData.setInDefineOwnProperty(false);
1995     }
1996
1997 private:
1998     JSGlobalData& m_globalData;
1999 };
2000
2001 bool JSObject::defineOwnNonIndexProperty(ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor, bool throwException)
2002 {
2003     // Track on the globaldata that we're in define property.
2004     // Currently DefineOwnProperty uses delete to remove properties when they are being replaced
2005     // (particularly when changing attributes), however delete won't allow non-configurable (i.e.
2006     // DontDelete) properties to be deleted. For now, we can use this flag to make this work.
2007     DefineOwnPropertyScope scope(exec);
2008     
2009     // If we have a new property we can just put it on normally
2010     PropertyDescriptor current;
2011     if (!methodTable()->getOwnPropertyDescriptor(this, exec, propertyName, current)) {
2012         // unless extensions are prevented!
2013         if (!isExtensible()) {
2014             if (throwException)
2015                 throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to define property on object that is not extensible.")));
2016             return false;
2017         }
2018         PropertyDescriptor oldDescriptor;
2019         oldDescriptor.setValue(jsUndefined());
2020         return putDescriptor(exec, this, propertyName, descriptor, descriptor.attributes(), oldDescriptor);
2021     }
2022
2023     if (descriptor.isEmpty())
2024         return true;
2025
2026     if (current.equalTo(exec, descriptor))
2027         return true;
2028
2029     // Filter out invalid changes
2030     if (!current.configurable()) {
2031         if (descriptor.configurable()) {
2032             if (throwException)
2033                 throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to configurable attribute of unconfigurable property.")));
2034             return false;
2035         }
2036         if (descriptor.enumerablePresent() && descriptor.enumerable() != current.enumerable()) {
2037             if (throwException)
2038                 throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to change enumerable attribute of unconfigurable property.")));
2039             return false;
2040         }
2041     }
2042
2043     // A generic descriptor is simply changing the attributes of an existing property
2044     if (descriptor.isGenericDescriptor()) {
2045         if (!current.attributesEqual(descriptor)) {
2046             methodTable()->deleteProperty(this, exec, propertyName);
2047             return putDescriptor(exec, this, propertyName, descriptor, descriptor.attributesOverridingCurrent(current), current);
2048         }
2049         return true;
2050     }
2051
2052     // Changing between a normal property or an accessor property
2053     if (descriptor.isDataDescriptor() != current.isDataDescriptor()) {
2054         if (!current.configurable()) {
2055             if (throwException)
2056                 throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to change access mechanism for an unconfigurable property.")));
2057             return false;
2058         }
2059         methodTable()->deleteProperty(this, exec, propertyName);
2060         return putDescriptor(exec, this, propertyName, descriptor, descriptor.attributesOverridingCurrent(current), current);
2061     }
2062
2063     // Changing the value and attributes of an existing property
2064     if (descriptor.isDataDescriptor()) {
2065         if (!current.configurable()) {
2066             if (!current.writable() && descriptor.writable()) {
2067                 if (throwException)
2068                     throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to change writable attribute of unconfigurable property.")));
2069                 return false;
2070             }
2071             if (!current.writable()) {
2072                 if (descriptor.value() && !sameValue(exec, current.value(), descriptor.value())) {
2073                     if (throwException)
2074                         throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to change value of a readonly property.")));
2075                     return false;
2076                 }
2077             }
2078         }
2079         if (current.attributesEqual(descriptor) && !descriptor.value())
2080             return true;
2081         methodTable()->deleteProperty(this, exec, propertyName);
2082         return putDescriptor(exec, this, propertyName, descriptor, descriptor.attributesOverridingCurrent(current), current);
2083     }
2084
2085     // Changing the accessor functions of an existing accessor property
2086     ASSERT(descriptor.isAccessorDescriptor());
2087     if (!current.configurable()) {
2088         if (descriptor.setterPresent() && !(current.setterPresent() && JSValue::strictEqual(exec, current.setter(), descriptor.setter()))) {
2089             if (throwException)
2090                 throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to change the setter of an unconfigurable property.")));
2091             return false;
2092         }
2093         if (descriptor.getterPresent() && !(current.getterPresent() && JSValue::strictEqual(exec, current.getter(), descriptor.getter()))) {
2094             if (throwException)
2095                 throwError(exec, createTypeError(exec, ASCIILiteral("Attempting to change the getter of an unconfigurable property.")));
2096             return false;
2097         }
2098     }
2099     JSValue accessor = getDirect(exec->globalData(), propertyName);
2100     if (!accessor)
2101         return false;
2102     GetterSetter* getterSetter = asGetterSetter(accessor);
2103     if (descriptor.setterPresent())
2104         getterSetter->setSetter(exec->globalData(), descriptor.setterObject());
2105     if (descriptor.getterPresent())
2106         getterSetter->setGetter(exec->globalData(), descriptor.getterObject());
2107     if (current.attributesEqual(descriptor))
2108         return true;
2109     methodTable()->deleteProperty(this, exec, propertyName);
2110     unsigned attrs = descriptor.attributesOverridingCurrent(current);
2111     putDirectAccessor(exec, propertyName, getterSetter, attrs | Accessor);
2112     return true;
2113 }
2114
2115 bool JSObject::defineOwnProperty(JSObject* object, ExecState* exec, PropertyName propertyName, PropertyDescriptor& descriptor, bool throwException)
2116 {
2117     // If it's an array index, then use the indexed property storage.
2118     unsigned index = propertyName.asIndex();
2119     if (index != PropertyName::NotAnIndex) {
2120         // c. Let succeeded be the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing P, Desc, and false as arguments.
2121         // d. Reject if succeeded is false.
2122         // e. If index >= oldLen
2123         // e.i. Set oldLenDesc.[[Value]] to index + 1.
2124         // e.ii. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", oldLenDesc, and false as arguments. This call will always return true.
2125         // f. Return true.
2126         return object->defineOwnIndexedProperty(exec, index, descriptor, throwException);
2127     }
2128     
2129     return object->defineOwnNonIndexProperty(exec, propertyName, descriptor, throwException);
2130 }
2131
2132 bool JSObject::getOwnPropertySlotSlow(ExecState* exec, PropertyName propertyName, PropertySlot& slot)
2133 {
2134     unsigned i = propertyName.asIndex();
2135     if (i != PropertyName::NotAnIndex)
2136         return getOwnPropertySlotByIndex(this, exec, i, slot);
2137     return false;
2138 }
2139
2140 JSObject* throwTypeError(ExecState* exec, const String& message)
2141 {
2142     return throwError(exec, createTypeError(exec, message));
2143 }
2144
2145 } // namespace JSC