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