Structure.cpp 29.6 KB
Newer Older
weinig@apple.com's avatar
weinig@apple.com committed
1
/*
2
 * Copyright (C) 2008, 2009 Apple Inc. All rights reserved.
weinig@apple.com's avatar
weinig@apple.com committed
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 */

#include "config.h"
darin@apple.com's avatar
darin@apple.com committed
27
#include "Structure.h"
weinig@apple.com's avatar
weinig@apple.com committed
28

29
#include "Identifier.h"
ggaren@apple.com's avatar
ggaren@apple.com committed
30
#include "JSObject.h"
31 32
#include "JSPropertyNameIterator.h"
#include "Lookup.h"
aroben@apple.com's avatar
aroben@apple.com committed
33
#include "PropertyNameArray.h"
darin@apple.com's avatar
darin@apple.com committed
34
#include "StructureChain.h"
35
#include <wtf/RefCountedLeakCounter.h>
weinig@apple.com's avatar
weinig@apple.com committed
36 37
#include <wtf/RefPtr.h>

ap@webkit.org's avatar
ap@webkit.org committed
38 39 40 41
#if ENABLE(JSC_MULTIPLE_THREADS)
#include <wtf/Threading.h>
#endif

42
#define DUMP_STRUCTURE_ID_STATISTICS 0
43

44 45 46 47 48 49
#ifndef NDEBUG
#define DO_PROPERTYMAP_CONSTENCY_CHECK 0
#else
#define DO_PROPERTYMAP_CONSTENCY_CHECK 0
#endif

weinig@apple.com's avatar
weinig@apple.com committed
50
using namespace std;
51
using namespace WTF;
weinig@apple.com's avatar
weinig@apple.com committed
52

53
#if DUMP_PROPERTYMAP_STATS
weinig@apple.com's avatar
weinig@apple.com committed
54

55 56 57 58
int numProbes;
int numCollisions;
int numRehashes;
int numRemoves;
59

60
#endif
61

62
namespace JSC {
63

64
#if DUMP_STRUCTURE_ID_STATISTICS
ap@webkit.org's avatar
ap@webkit.org committed
65
static HashSet<Structure*>& liveStructureSet = *(new HashSet<Structure*>);
66
#endif
67

68
bool StructureTransitionTable::contains(StringImpl* rep, unsigned attributes) const
69
{
70 71 72
    if (isUsingSingleSlot()) {
        Structure* transition = singleTransition();
        return transition && transition->m_nameInPrevious == rep && transition->m_attributesInPrevious == attributes;
73
    }
74
    return map()->contains(make_pair(rep, attributes));
75 76
}

77
inline Structure* StructureTransitionTable::get(StringImpl* rep, unsigned attributes) const
78
{
79
    if (isUsingSingleSlot()) {
80
        Structure* transition = singleTransition();
81
        return (transition && transition->m_nameInPrevious == rep && transition->m_attributesInPrevious == attributes) ? transition : 0;
82
    }
83
    return map()->get(make_pair(rep, attributes));
84 85
}

86
inline void StructureTransitionTable::add(JSGlobalData& globalData, Structure* structure)
87
{
88 89 90 91 92
    if (isUsingSingleSlot()) {
        Structure* existingTransition = singleTransition();

        // This handles the first transition being added.
        if (!existingTransition) {
93
            setSingleTransition(globalData, structure);
94 95
            return;
        }
96 97 98 99

        // This handles the second transition being added
        // (or the first transition being despecified!)
        setMap(new TransitionMap());
100
        add(globalData, existingTransition);
101
    }
102 103

    // Add the structure to the map.
104 105 106 107 108

    // Newer versions of the STL have an std::make_pair function that takes rvalue references.
    // When either of the parameters are bitfields, the C++ compiler will try to bind them as lvalues, which is invalid. To work around this, use unary "+" to make the parameter an rvalue.
    // See https://bugs.webkit.org/show_bug.cgi?id=59261 for more details
    std::pair<TransitionMap::iterator, bool> result = map()->add(globalData, make_pair(structure->m_nameInPrevious, +structure->m_attributesInPrevious), structure);
109 110
    if (!result.second) {
        // There already is an entry! - we should only hit this when despecifying.
111
        ASSERT(result.first.get().second->m_specificValueInPrevious);
112
        ASSERT(!structure->m_specificValueInPrevious);
113
        map()->set(result.first, structure);
114 115 116
    }
}

darin@apple.com's avatar
darin@apple.com committed
117
void Structure::dumpStatistics()
118
{
119
#if DUMP_STRUCTURE_ID_STATISTICS
120
    unsigned numberLeaf = 0;
121
    unsigned numberUsingSingleSlot = 0;
122
    unsigned numberSingletons = 0;
123
    unsigned numberWithPropertyMaps = 0;
124
    unsigned totalPropertyMapsSize = 0;
125

darin@apple.com's avatar
darin@apple.com committed
126 127 128
    HashSet<Structure*>::const_iterator end = liveStructureSet.end();
    for (HashSet<Structure*>::const_iterator it = liveStructureSet.begin(); it != end; ++it) {
        Structure* structure = *it;
129 130 131

        switch (structure->m_transitionTable.size()) {
            case 0:
132
                ++numberLeaf;
133 134 135
               if (!structure->m_previous)
                    ++numberSingletons;
                break;
136

137 138 139
            case 1:
                ++numberUsingSingleSlot;
                break;
140
        }
141

darin@apple.com's avatar
darin@apple.com committed
142
        if (structure->m_propertyTable) {
143
            ++numberWithPropertyMaps;
144
            totalPropertyMapsSize += structure->m_propertyTable->sizeInMemory();
145
        }
146 147
    }

darin@apple.com's avatar
darin@apple.com committed
148 149 150 151 152
    printf("Number of live Structures: %d\n", liveStructureSet.size());
    printf("Number of Structures using the single item optimization for transition map: %d\n", numberUsingSingleSlot);
    printf("Number of Structures that are leaf nodes: %d\n", numberLeaf);
    printf("Number of Structures that singletons: %d\n", numberSingletons);
    printf("Number of Structures with PropertyMaps: %d\n", numberWithPropertyMaps);
153

darin@apple.com's avatar
darin@apple.com committed
154
    printf("Size of a single Structures: %d\n", static_cast<unsigned>(sizeof(Structure)));
155
    printf("Size of sum of all property maps: %d\n", totalPropertyMapsSize);
darin@apple.com's avatar
darin@apple.com committed
156
    printf("Size of average of all property maps: %f\n", static_cast<double>(totalPropertyMapsSize) / static_cast<double>(liveStructureSet.size()));
157
#else
darin@apple.com's avatar
darin@apple.com committed
158
    printf("Dumping Structure statistics is not enabled.\n");
159
#endif
160
}
161

162 163 164 165
Structure::Structure(JSGlobalData& globalData, JSValue prototype, const TypeInfo& typeInfo, unsigned anonymousSlotCount, const ClassInfo* classInfo)
    : JSCell(globalData, globalData.structureStructure.get())
    , m_typeInfo(typeInfo)
    , m_prototype(globalData, this, prototype)
166
    , m_classInfo(classInfo)
167
    , m_propertyStorageCapacity(typeInfo.isFinal() ? JSFinalObject_inlineStorageCapacity : JSNonFinalObject_inlineStorageCapacity)
168
    , m_offset(noOffset)
169
    , m_dictionaryKind(NoneDictionaryKind)
170
    , m_isPinnedPropertyTable(false)
171
    , m_hasGetterSetterProperties(false)
172
    , m_hasNonEnumerableProperties(false)
173
    , m_attributesInPrevious(0)
174
    , m_specificFunctionThrashCount(0)
175
    , m_anonymousSlotCount(anonymousSlotCount)
176
    , m_preventExtensions(false)
177
    , m_didTransition(false)
weinig@apple.com's avatar
weinig@apple.com committed
178
{
179
}
180

181
const ClassInfo Structure::s_info = { "Structure", 0, 0, 0 };
182

183
Structure::Structure(JSGlobalData& globalData)
184
    : JSCell(CreatingEarlyCell)
185
    , m_typeInfo(CompoundType, OverridesVisitChildren)
186 187 188 189 190 191 192 193 194 195 196 197
    , m_prototype(globalData, this, jsNull())
    , m_classInfo(&s_info)
    , m_propertyStorageCapacity(0)
    , m_offset(noOffset)
    , m_dictionaryKind(NoneDictionaryKind)
    , m_isPinnedPropertyTable(false)
    , m_hasGetterSetterProperties(false)
    , m_hasNonEnumerableProperties(false)
    , m_attributesInPrevious(0)
    , m_specificFunctionThrashCount(0)
    , m_anonymousSlotCount(0)
    , m_preventExtensions(false)
198
    , m_didTransition(false)
199
{
200 201
}

202 203 204 205
Structure::Structure(JSGlobalData& globalData, const Structure* previous)
    : JSCell(globalData, globalData.structureStructure.get())
    , m_typeInfo(previous->typeInfo())
    , m_prototype(globalData, this, previous->storedPrototype())
206 207 208 209 210 211 212 213 214 215
    , m_classInfo(previous->m_classInfo)
    , m_propertyStorageCapacity(previous->m_propertyStorageCapacity)
    , m_offset(noOffset)
    , m_dictionaryKind(NoneDictionaryKind)
    , m_isPinnedPropertyTable(false)
    , m_hasGetterSetterProperties(previous->m_hasGetterSetterProperties)
    , m_hasNonEnumerableProperties(previous->m_hasNonEnumerableProperties)
    , m_attributesInPrevious(0)
    , m_specificFunctionThrashCount(previous->m_specificFunctionThrashCount)
    , m_anonymousSlotCount(previous->anonymousSlotCount())
216
    , m_preventExtensions(previous->m_preventExtensions)
217
    , m_didTransition(true)
218 219 220
{
}

darin@apple.com's avatar
darin@apple.com committed
221
Structure::~Structure()
222
{
weinig@apple.com's avatar
weinig@apple.com committed
223 224
}

225
void Structure::materializePropertyMap(JSGlobalData& globalData)
226
{
jberlin@webkit.org's avatar
jberlin@webkit.org committed
227
    ASSERT(structure()->classInfo() == &s_info);
228 229
    ASSERT(!m_propertyTable);

darin@apple.com's avatar
darin@apple.com committed
230
    Vector<Structure*, 8> structures;
231 232
    structures.append(this);

darin@apple.com's avatar
darin@apple.com committed
233
    Structure* structure = this;
234

235
    // Search for the last Structure with a property table.
236 237 238 239 240
    while ((structure = structure->previousID())) {
        if (structure->m_isPinnedPropertyTable) {
            ASSERT(structure->m_propertyTable);
            ASSERT(!structure->m_previous);

241
            m_propertyTable = structure->m_propertyTable->copy(globalData, 0, m_offset + 1);
242 243 244 245 246 247 248
            break;
        }

        structures.append(structure);
    }

    if (!m_propertyTable)
249
        createPropertyMap(m_offset + 1);
250

251 252
    for (ptrdiff_t i = structures.size() - 2; i >= 0; --i) {
        structure = structures[i];
253
        PropertyMapEntry entry(globalData, this, structure->m_nameInPrevious.get(), m_anonymousSlotCount + structure->m_offset, structure->m_attributesInPrevious, structure->m_specificValueInPrevious.get());
254
        m_propertyTable->add(entry);
255 256 257
    }
}

darin@apple.com's avatar
darin@apple.com committed
258
void Structure::growPropertyStorageCapacity()
259
{
260 261
    if (isUsingInlineStorage())
        m_propertyStorageCapacity = JSObject::baseExternalStorageCapacity;
262 263
    else
        m_propertyStorageCapacity *= 2;
264 265
}

266
void Structure::despecifyDictionaryFunction(JSGlobalData& globalData, const Identifier& propertyName)
267
{
268
    StringImpl* rep = propertyName.impl();
269

270
    materializePropertyMapIfNecessary(globalData);
271

272
    ASSERT(isDictionary());
273 274
    ASSERT(m_propertyTable);

275 276
    PropertyMapEntry* entry = m_propertyTable->find(rep).first;
    ASSERT(entry);
277
    entry->specificValue.clear();
278 279
}

280
Structure* Structure::addPropertyTransitionToExistingStructure(Structure* structure, const Identifier& propertyName, unsigned attributes, JSCell* specificValue, size_t& offset)
weinig@apple.com's avatar
weinig@apple.com committed
281
{
282
    ASSERT(!structure->isDictionary());
darin@apple.com's avatar
darin@apple.com committed
283
    ASSERT(structure->typeInfo().type() == ObjectType);
weinig@apple.com's avatar
weinig@apple.com committed
284

285
    if (Structure* existingTransition = structure->m_transitionTable.get(propertyName.impl(), attributes)) {
286
        JSCell* specificValueInPrevious = existingTransition->m_specificValueInPrevious.get();
287 288
        if (specificValueInPrevious && specificValueInPrevious != specificValue)
            return 0;
289
        ASSERT(existingTransition->m_offset != noOffset);
290 291 292
        offset = existingTransition->m_offset + existingTransition->m_anonymousSlotCount;
        ASSERT(offset >= structure->m_anonymousSlotCount);
        ASSERT(structure->m_anonymousSlotCount == existingTransition->m_anonymousSlotCount);
293
        return existingTransition;
weinig@apple.com's avatar
weinig@apple.com committed
294
    }
weinig@apple.com's avatar
weinig@apple.com committed
295

296 297 298
    return 0;
}

299
Structure* Structure::addPropertyTransition(JSGlobalData& globalData, Structure* structure, const Identifier& propertyName, unsigned attributes, JSCell* specificValue, size_t& offset)
300
{
301 302 303 304 305 306 307 308 309 310
    // If we have a specific function, we may have got to this point if there is
    // already a transition with the correct property name and attributes, but
    // specialized to a different function.  In this case we just want to give up
    // and despecialize the transition.
    // In this case we clear the value of specificFunction which will result
    // in us adding a non-specific transition, and any subsequent lookup in
    // Structure::addPropertyTransitionToExistingStructure will just use that.
    if (specificValue && structure->m_transitionTable.contains(propertyName.impl(), attributes))
        specificValue = 0;

311
    ASSERT(!structure->isDictionary());
darin@apple.com's avatar
darin@apple.com committed
312
    ASSERT(structure->typeInfo().type() == ObjectType);
313
    ASSERT(!Structure::addPropertyTransitionToExistingStructure(structure, propertyName, attributes, specificValue, offset));
314 315 316
    
    if (structure->m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)
        specificValue = 0;
317

318
    if (structure->transitionCount() > s_maxTransitionLength) {
319
        Structure* transition = toCacheableDictionaryTransition(globalData, structure);
320
        ASSERT(structure != transition);
321
        offset = transition->putSpecificValue(globalData, propertyName, attributes, specificValue);
322 323
        ASSERT(offset >= structure->m_anonymousSlotCount);
        ASSERT(structure->m_anonymousSlotCount == transition->m_anonymousSlotCount);
324
        if (transition->propertyStorageSize() > transition->propertyStorageCapacity())
325
            transition->growPropertyStorageCapacity();
326
        return transition;
weinig@apple.com's avatar
weinig@apple.com committed
327
    }
weinig@apple.com's avatar
weinig@apple.com committed
328

329
    Structure* transition = create(globalData, structure);
330

331
    transition->m_cachedPrototypeChain.setMayBeNull(globalData, transition, structure->m_cachedPrototypeChain.get());
332
    transition->m_previous.set(globalData, transition, structure);
333
    transition->m_nameInPrevious = propertyName.impl();
weinig@apple.com's avatar
weinig@apple.com committed
334
    transition->m_attributesInPrevious = attributes;
335
    transition->m_specificValueInPrevious.setMayBeNull(globalData, transition, specificValue);
336

darin@apple.com's avatar
darin@apple.com committed
337 338
    if (structure->m_propertyTable) {
        if (structure->m_isPinnedPropertyTable)
339
            transition->m_propertyTable = structure->m_propertyTable->copy(globalData, transition, structure->m_propertyTable->size() + 1);
340 341
        else
            transition->m_propertyTable = structure->m_propertyTable.release();
342
    } else {
darin@apple.com's avatar
darin@apple.com committed
343
        if (structure->m_previous)
344
            transition->materializePropertyMap(globalData);
345
        else
346
            transition->createPropertyMap();
347 348
    }

349
    offset = transition->putSpecificValue(globalData, propertyName, attributes, specificValue);
350 351
    ASSERT(offset >= structure->m_anonymousSlotCount);
    ASSERT(structure->m_anonymousSlotCount == transition->m_anonymousSlotCount);
352
    if (transition->propertyStorageSize() > transition->propertyStorageCapacity())
353
        transition->growPropertyStorageCapacity();
weinig@apple.com's avatar
weinig@apple.com committed
354

355
    transition->m_offset = offset - structure->m_anonymousSlotCount;
356
    ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount());
357 358
    structure->m_transitionTable.add(globalData, transition);
    return transition;
weinig@apple.com's avatar
weinig@apple.com committed
359 360
}

361
Structure* Structure::removePropertyTransition(JSGlobalData& globalData, Structure* structure, const Identifier& propertyName, size_t& offset)
362
{
363
    ASSERT(!structure->isUncacheableDictionary());
364

365
    Structure* transition = toUncacheableDictionaryTransition(globalData, structure);
366 367

    offset = transition->remove(propertyName);
368 369
    ASSERT(offset >= structure->m_anonymousSlotCount);
    ASSERT(structure->m_anonymousSlotCount == transition->m_anonymousSlotCount);
370

371
    return transition;
372 373
}

374
Structure* Structure::changePrototypeTransition(JSGlobalData& globalData, Structure* structure, JSValue prototype)
375
{
376
    Structure* transition = create(globalData, structure);
377

378
    transition->m_prototype.set(globalData, transition, prototype);
379

380 381
    // Don't set m_offset, as one can not transition to this.

382
    structure->materializePropertyMapIfNecessary(globalData);
383
    transition->m_propertyTable = structure->copyPropertyTable(globalData, transition);
384
    transition->m_isPinnedPropertyTable = true;
385 386
    
    ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount());
387
    return transition;
388 389
}

390
Structure* Structure::despecifyFunctionTransition(JSGlobalData& globalData, Structure* structure, const Identifier& replaceFunction)
391
{
392
    ASSERT(structure->m_specificFunctionThrashCount < maxSpecificFunctionThrashCount);
393
    Structure* transition = create(globalData, structure);
394

395
    ++transition->m_specificFunctionThrashCount;
396 397 398

    // Don't set m_offset, as one can not transition to this.

399
    structure->materializePropertyMapIfNecessary(globalData);
400
    transition->m_propertyTable = structure->copyPropertyTable(globalData, transition);
401 402
    transition->m_isPinnedPropertyTable = true;

403
    if (transition->m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)
404
        transition->despecifyAllFunctions(globalData);
405
    else {
406
        bool removed = transition->despecifyFunction(globalData, replaceFunction);
407 408
        ASSERT_UNUSED(removed, removed);
    }
409 410
    
    ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount());
411
    return transition;
412 413
}

414
Structure* Structure::getterSetterTransition(JSGlobalData& globalData, Structure* structure)
415
{
416
    Structure* transition = create(globalData, structure);
417 418 419

    // Don't set m_offset, as one can not transition to this.

420
    structure->materializePropertyMapIfNecessary(globalData);
421
    transition->m_propertyTable = structure->copyPropertyTable(globalData, transition);
422
    transition->m_isPinnedPropertyTable = true;
423 424
    
    ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount());
425
    return transition;
426 427
}

428
Structure* Structure::toDictionaryTransition(JSGlobalData& globalData, Structure* structure, DictionaryKind kind)
weinig@apple.com's avatar
weinig@apple.com committed
429
{
430 431
    ASSERT(!structure->isUncacheableDictionary());
    
432
    Structure* transition = create(globalData, structure);
433

434
    structure->materializePropertyMapIfNecessary(globalData);
435
    transition->m_propertyTable = structure->copyPropertyTable(globalData, transition);
436
    transition->m_isPinnedPropertyTable = true;
437
    transition->m_dictionaryKind = kind;
438
    
439
    ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount());
440
    return transition;
oliver@apple.com's avatar
oliver@apple.com committed
441 442
}

443
Structure* Structure::toCacheableDictionaryTransition(JSGlobalData& globalData, Structure* structure)
444
{
445
    return toDictionaryTransition(globalData, structure, CachedDictionaryKind);
446 447
}

448
Structure* Structure::toUncacheableDictionaryTransition(JSGlobalData& globalData, Structure* structure)
449
{
450
    return toDictionaryTransition(globalData, structure, UncachedDictionaryKind);
451 452
}

453
// In future we may want to cache this transition.
454
Structure* Structure::sealTransition(JSGlobalData& globalData, Structure* structure)
455
{
456
    Structure* transition = preventExtensionsTransition(globalData, structure);
457 458 459 460 461 462 463

    if (transition->m_propertyTable) {
        PropertyTable::iterator end = transition->m_propertyTable->end();
        for (PropertyTable::iterator iter = transition->m_propertyTable->begin(); iter != end; ++iter)
            iter->attributes |= DontDelete;
    }

464
    return transition;
465 466 467
}

// In future we may want to cache this transition.
468
Structure* Structure::freezeTransition(JSGlobalData& globalData, Structure* structure)
469
{
470
    Structure* transition = preventExtensionsTransition(globalData, structure);
471 472 473 474 475 476 477

    if (transition->m_propertyTable) {
        PropertyTable::iterator end = transition->m_propertyTable->end();
        for (PropertyTable::iterator iter = transition->m_propertyTable->begin(); iter != end; ++iter)
            iter->attributes |= (DontDelete | ReadOnly);
    }

478
    return transition;
479 480 481
}

// In future we may want to cache this transition.
482
Structure* Structure::preventExtensionsTransition(JSGlobalData& globalData, Structure* structure)
483
{
484
    Structure* transition = create(globalData, structure);
485 486 487

    // Don't set m_offset, as one can not transition to this.

488
    structure->materializePropertyMapIfNecessary(globalData);
489
    transition->m_propertyTable = structure->copyPropertyTable(globalData, transition);
490 491 492 493
    transition->m_isPinnedPropertyTable = true;
    transition->m_preventExtensions = true;

    ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount());
494
    return transition;
495 496 497
}

// In future we may want to cache this property.
498
bool Structure::isSealed(JSGlobalData& globalData)
499 500 501 502
{
    if (isExtensible())
        return false;

503
    materializePropertyMapIfNecessary(globalData);
504 505 506 507 508 509 510 511 512 513 514 515
    if (!m_propertyTable)
        return true;

    PropertyTable::iterator end = m_propertyTable->end();
    for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter) {
        if ((iter->attributes & DontDelete) != DontDelete)
            return false;
    }
    return true;
}

// In future we may want to cache this property.
516
bool Structure::isFrozen(JSGlobalData& globalData)
517 518 519 520
{
    if (isExtensible())
        return false;

521
    materializePropertyMapIfNecessary(globalData);
522 523 524 525 526 527 528 529 530 531 532
    if (!m_propertyTable)
        return true;

    PropertyTable::iterator end = m_propertyTable->end();
    for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter) {
        if ((iter->attributes & (DontDelete | ReadOnly)) != (DontDelete | ReadOnly))
            return false;
    }
    return true;
}

533
Structure* Structure::flattenDictionaryStructure(JSGlobalData& globalData, JSObject* object)
ggaren@apple.com's avatar
ggaren@apple.com committed
534
{
535 536 537 538
    ASSERT(isDictionary());
    if (isUncacheableDictionary()) {
        ASSERT(m_propertyTable);

539
        unsigned anonymousSlotCount = m_anonymousSlotCount;
540 541 542 543 544 545 546
        size_t propertyCount = m_propertyTable->size();
        Vector<JSValue> values(propertyCount);

        unsigned i = 0;
        PropertyTable::iterator end = m_propertyTable->end();
        for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter, ++i) {
            values[i] = object->getDirectOffset(iter->offset);
547
            // Update property table to have the new property offsets
548
            iter->offset = anonymousSlotCount + i;
549 550 551 552
        }
        
        // Copy the original property values into their final locations
        for (unsigned i = 0; i < propertyCount; i++)
553
            object->putDirectOffset(globalData, anonymousSlotCount + i, values[i]);
554

555
        m_propertyTable->clearDeletedOffsets();
556
    }
weinig@apple.com's avatar
weinig@apple.com committed
557

558 559
    m_dictionaryKind = NoneDictionaryKind;
    return this;
weinig@apple.com's avatar
weinig@apple.com committed
560 561
}

562
size_t Structure::addPropertyWithoutTransition(JSGlobalData& globalData, const Identifier& propertyName, unsigned attributes, JSCell* specificValue)
563
{
564
    ASSERT(!m_enumerationCache);
565 566 567 568

    if (m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)
        specificValue = 0;

569
    materializePropertyMapIfNecessary(globalData);
570 571

    m_isPinnedPropertyTable = true;
572

573
    size_t offset = putSpecificValue(globalData, propertyName, attributes, specificValue);
574
    ASSERT(offset >= m_anonymousSlotCount);
575
    if (propertyStorageSize() > propertyStorageCapacity())
576
        growPropertyStorageCapacity();
577 578 579
    return offset;
}

580
size_t Structure::removePropertyWithoutTransition(JSGlobalData& globalData, const Identifier& propertyName)
581
{
582
    ASSERT(isUncacheableDictionary());
583
    ASSERT(!m_enumerationCache);
584

585
    materializePropertyMapIfNecessary(globalData);
586 587

    m_isPinnedPropertyTable = true;
588
    size_t offset = remove(propertyName);
589
    ASSERT(offset >= m_anonymousSlotCount);
590 591 592
    return offset;
}

593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613
#if DUMP_PROPERTYMAP_STATS

struct PropertyMapStatisticsExitLogger {
    ~PropertyMapStatisticsExitLogger();
};

static PropertyMapStatisticsExitLogger logger;

PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
{
    printf("\nJSC::PropertyMap statistics\n\n");
    printf("%d probes\n", numProbes);
    printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
    printf("%d rehashes\n", numRehashes);
    printf("%d removes\n", numRemoves);
}

#endif

#if !DO_PROPERTYMAP_CONSTENCY_CHECK

darin@apple.com's avatar
darin@apple.com committed
614
inline void Structure::checkConsistency()
615
{
616
}
617 618 619

#endif

620
PassOwnPtr<PropertyTable> Structure::copyPropertyTable(JSGlobalData& globalData, Structure* owner)
621
{
622
    return adoptPtr(m_propertyTable ? new PropertyTable(globalData, owner, *m_propertyTable) : 0);
623 624
}

625
size_t Structure::get(JSGlobalData& globalData, StringImpl* propertyName, unsigned& attributes, JSCell*& specificValue)
626
{
627
    materializePropertyMapIfNecessary(globalData);
628
    if (!m_propertyTable)
629
        return WTF::notFound;
630

631 632 633
    PropertyMapEntry* entry = m_propertyTable->find(propertyName).first;
    if (!entry)
        return WTF::notFound;
634

635
    attributes = entry->attributes;
636
    specificValue = entry->specificValue.get();
637 638
    ASSERT(entry->offset >= m_anonymousSlotCount);
    return entry->offset;
639 640
}

641
bool Structure::despecifyFunction(JSGlobalData& globalData, const Identifier& propertyName)
642
{
643
    materializePropertyMapIfNecessary(globalData);
644 645 646
    if (!m_propertyTable)
        return false;

647 648 649
    ASSERT(!propertyName.isNull());
    PropertyMapEntry* entry = m_propertyTable->find(propertyName.impl()).first;
    if (!entry)
650 651
        return false;

652
    ASSERT(entry->specificValue);
653
    entry->specificValue.clear();
654
    return true;
655 656
}

657
void Structure::despecifyAllFunctions(JSGlobalData& globalData)
658
{
659
    materializePropertyMapIfNecessary(globalData);
660 661
    if (!m_propertyTable)
        return;
662 663 664

    PropertyTable::iterator end = m_propertyTable->end();
    for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter)
665
        iter->specificValue.clear();
666 667
}

668
size_t Structure::putSpecificValue(JSGlobalData& globalData, const Identifier& propertyName, unsigned attributes, JSCell* specificValue)
669 670
{
    ASSERT(!propertyName.isNull());
671
    ASSERT(get(globalData, propertyName) == notFound);
672 673

    checkConsistency();
674 675 676
    if (attributes & DontEnum)
        m_hasNonEnumerableProperties = true;

677
    StringImpl* rep = propertyName.impl();
678 679

    if (!m_propertyTable)
680
        createPropertyMap();
681 682

    unsigned newOffset;
683 684 685 686 687

    if (m_propertyTable->hasDeletedOffset())
        newOffset = m_propertyTable->getDeletedOffset();
    else
        newOffset = m_propertyTable->size() + m_anonymousSlotCount;
688
    ASSERT(newOffset >= m_anonymousSlotCount);
689

690
    m_propertyTable->add(PropertyMapEntry(globalData, this, rep, newOffset, attributes, specificValue));
691 692 693 694 695

    checkConsistency();
    return newOffset;
}

darin@apple.com's avatar
darin@apple.com committed
696
size_t Structure::remove(const Identifier& propertyName)
697 698 699 700 701
{
    ASSERT(!propertyName.isNull());

    checkConsistency();

702
    StringImpl* rep = propertyName.impl();
703 704

    if (!m_propertyTable)
705
        return notFound;
706

707 708 709
    PropertyTable::find_iterator position = m_propertyTable->find(rep);
    if (!position.first)
        return notFound;
710

711
    size_t offset = position.first->offset;
712
    ASSERT(offset >= m_anonymousSlotCount);
713

714 715
    m_propertyTable->remove(position);
    m_propertyTable->addDeletedOffset(offset);
716 717 718 719 720

    checkConsistency();
    return offset;
}

721
void Structure::createPropertyMap(unsigned capacity)
722 723 724 725
{
    ASSERT(!m_propertyTable);

    checkConsistency();
726
    m_propertyTable = adoptPtr(new PropertyTable(capacity));
727 728 729
    checkConsistency();
}

730
void Structure::getPropertyNames(JSGlobalData& globalData, PropertyNameArray& propertyNames, EnumerationMode mode)
731
{