js/src/jsscope.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   2  * vim: set ts=8 sw=4 et tw=78:
   3  *
   4  * ***** BEGIN LICENSE BLOCK *****
   5  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   6  *
   7  * The contents of this file are subject to the Mozilla Public License Version
   8  * 1.1 (the "License"); you may not use this file except in compliance with
   9  * the License. You may obtain a copy of the License at
  10  * http://www.mozilla.org/MPL/
  11  *
  12  * Software distributed under the License is distributed on an "AS IS" basis,
  13  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  14  * for the specific language governing rights and limitations under the
  15  * License.
  16  *
  17  * The Original Code is Mozilla Communicator client code, released
  18  * March 31, 1998.
  19  *
  20  * The Initial Developer of the Original Code is
  21  * Netscape Communications Corporation.
  22  * Portions created by the Initial Developer are Copyright (C) 1998
  23  * the Initial Developer. All Rights Reserved.
  24  *
  25  * Contributor(s):
  26  *
  27  * Alternatively, the contents of this file may be used under the terms of
  28  * either of the GNU General Public License Version 2 or later (the "GPL"),
  29  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  30  * in which case the provisions of the GPL or the LGPL are applicable instead
  31  * of those above. If you wish to allow use of your version of this file only
  32  * under the terms of either the GPL or the LGPL, and not to allow others to
  33  * use your version of this file under the terms of the MPL, indicate your
  34  * decision by deleting the provisions above and replace them with the notice
  35  * and other provisions required by the GPL or the LGPL. If you do not delete
  36  * the provisions above, a recipient may use your version of this file under
  37  * the terms of any one of the MPL, the GPL or the LGPL.
  38  *
  39  * ***** END LICENSE BLOCK ***** */
  40
  41 /*
  42  * JS symbol tables.
  43  */
  44 #include <new>
  45 #include <stdlib.h>
  46 #include <string.h>
  47 #include "jstypes.h"
  48 #include "jsstdint.h"
  49 #include "jsarena.h"
  50 #include "jsbit.h"
  51 #include "jsclist.h"
  52 #include "jsdhash.h"
  53 #include "jsutil.h"
  54 #include "jsapi.h"
  55 #include "jsatom.h"
  56 #include "jscntxt.h"
  57 #include "jsdbgapi.h"
  58 #include "jsfun.h"      /* for JS_ARGS_LENGTH_MAX */
  59 #include "jslock.h"
  60 #include "jsnum.h"
  61 #include "jsobj.h"
  62 #include "jsscope.h"
  63 #include "jsstr.h"
  64 #include "jstracer.h"
  65
  66 #include "jsdbgapiinlines.h"
  67 #include "jsobjinlines.h"
  68 #include "jsscopeinlines.h"
  69
  70 using namespace js;
  71 using namespace js::gc;
  72
  73 uint32
  74 js_GenerateShape(JSRuntime *rt)
  75 {
  76     uint32 shape;
  77
  78     shape = JS_ATOMIC_INCREMENT(&rt->shapeGen);
  79     JS_ASSERT(shape != 0);
  80     if (shape >= SHAPE_OVERFLOW_BIT) {
  81         /*
  82          * FIXME bug 440834: The shape id space has overflowed. Currently we
  83          * cope badly with this and schedule the GC on the every call. But
  84          * first we make sure that increments from other threads would not
  85          * have a chance to wrap around shapeGen to zero.
  86          */
  87         rt->shapeGen = SHAPE_OVERFLOW_BIT;
  88         shape = SHAPE_OVERFLOW_BIT;
  89
  90 #ifdef JS_THREADSAFE
  91         AutoLockGC lockIf(rt);
  92 #endif
  93         TriggerGC(rt);
  94     }
  95     return shape;
  96 }
  97
  98 uint32
  99 js_GenerateShape(JSContext *cx)
 100 {
 101     return js_GenerateShape(cx->runtime);
 102 }
 103
 104 bool
 105 JSObject::ensureClassReservedSlotsForEmptyObject(JSContext *cx)
 106 {
 107     JS_ASSERT(nativeEmpty());
 108
 109     /*
 110      * Subtle rule: objects that call JSObject::ensureInstanceReservedSlots
 111      * must either:
 112      *
 113      * (a) never escape anywhere an ad-hoc property could be set on them; or
 114      *
 115      * (b) protect their instance-reserved slots with shapes, at least a custom
 116      * empty shape with the right slotSpan member.
 117      *
 118      * Block objects are the only objects that fall into category (a). While
 119      * Call objects cannot escape, they can grow ad-hoc properties via eval
 120      * of a var declaration, or due to a function statement being evaluated,
 121      * but they have slots mapped by compiler-created shapes, and thus (b) no
 122      * problem predicting first ad-hoc property slot. Bound Function objects
 123      * have a custom empty shape.
 124      *
 125      * (Note that Block, Call, and bound Function objects are the only native
 126      * class objects that are allowed to call ensureInstanceReservedSlots.)
 127      */
 128     uint32 nfixed = JSSLOT_FREE(getClass());
 129     if (nfixed > numSlots() && !allocSlots(cx, nfixed))
 130         return false;
 131
 132     return true;
 133 }
 134
 135 #define PROPERTY_TABLE_NBYTES(n) ((n) * sizeof(Shape *))
 136
 137 #ifdef DEBUG
 138 JS_FRIEND_DATA(JSScopeStats) js_scope_stats = {0};
 139
 140 # define METER(x)       JS_ATOMIC_INCREMENT(&js_scope_stats.x)
 141 #else
 142 # define METER(x)       ((void) 0)
 143 #endif
 144
 145 bool
 146 PropertyTable::init(JSRuntime *rt, Shape *lastProp)
 147 {
 148     /*
 149      * Either we're creating a table for a large scope that was populated
 150      * via property cache hit logic under JSOP_INITPROP, JSOP_SETNAME, or
 151      * JSOP_SETPROP; or else calloc failed at least once already. In any
 152      * event, let's try to grow, overallocating to hold at least twice the
 153      * current population.
 154      */
 155     uint32 sizeLog2 = JS_CeilingLog2(2 * entryCount);
 156     if (sizeLog2 < MIN_SIZE_LOG2)
 157         sizeLog2 = MIN_SIZE_LOG2;
 158
 159     /*
 160      * Use rt->calloc for memory accounting and overpressure handling
 161      * without OOM reporting. See PropertyTable::change.
 162      */
 163     entries = (Shape **) rt->calloc(JS_BIT(sizeLog2) * sizeof(Shape *));
 164     if (!entries) {
 165         METER(tableAllocFails);
 166         return false;
 167     }
 168
 169     hashShift = JS_DHASH_BITS - sizeLog2;
 170     for (Shape::Range r = lastProp->all(); !r.empty(); r.popFront()) {
 171         const Shape &shape = r.front();
 172         METER(searches);
 173         METER(initSearches);
 174         Shape **spp = search(shape.id, true);
 175
 176         /*
 177          * Beware duplicate args and arg vs. var conflicts: the youngest shape
 178          * (nearest to lastProp) must win. See bug 600067.
 179          */
 180         if (!SHAPE_FETCH(spp))
 181             SHAPE_STORE_PRESERVING_COLLISION(spp, &shape);
 182     }
 183     return true;
 184 }
 185
 186 bool
 187 Shape::hashify(JSRuntime *rt)
 188 {
 189     JS_ASSERT(!hasTable());
 190     void* mem = rt->malloc(sizeof(PropertyTable));
 191     if (!mem)
 192         return false;
 193     setTable(new(mem) PropertyTable(entryCount()));
 194     return getTable()->init(rt, this);
 195 }
 196
 197 #ifdef DEBUG
 198 # include "jsprf.h"
 199 # define LIVE_SCOPE_METER(cx,expr) JS_LOCK_RUNTIME_VOID(cx->runtime,expr)
 200 #else
 201 # define LIVE_SCOPE_METER(cx,expr) /* nothing */
 202 #endif
 203
 204 static inline bool
 205 InitField(JSCompartment *comp, EmptyShape *JSCompartment:: *field, Class *clasp)
 206 {
 207     if (EmptyShape *emptyShape = EmptyShape::create(comp, clasp)) {
 208         comp->*field = emptyShape;
 209         return true;
 210     }
 211     return false;
 212 }
 213
 214 /* static */
 215 bool
 216 Shape::initEmptyShapes(JSCompartment *comp)
 217 {
 218     /*
 219      * NewArguments allocates dslots to have enough room for the argc of the
 220      * particular arguments object being created.
 221      * never mutated, it's safe to pretend to have all the slots possible.
 222      *
 223      * Note how the fast paths in jsinterp.cpp for JSOP_LENGTH and JSOP_GETELEM
 224      * bypass resolution of scope properties for length and element indices on
 225      * arguments objects. This helps ensure that any arguments object needing
 226      * its own mutable scope (with unique shape) is a rare event.
 227      */
 228     if (!InitField(comp, &JSCompartment::emptyArgumentsShape, &js_ArgumentsClass))
 229         return false;
 230
 231     if (!InitField(comp, &JSCompartment::emptyBlockShape, &js_BlockClass))
 232         return false;
 233
 234     /*
 235      * Initialize the shared scope for all empty Call objects so gets for args
 236      * and vars do not force the creation of a mutable scope for the particular
 237      * call object being accessed.
 238      */
 239     if (!InitField(comp, &JSCompartment::emptyCallShape, &js_CallClass))
 240         return false;
 241
 242     /* A DeclEnv object holds the name binding for a named function expression. */
 243     if (!InitField(comp, &JSCompartment::emptyDeclEnvShape, &js_DeclEnvClass))
 244         return false;
 245
 246     /* Non-escaping native enumerator objects share this empty scope. */
 247     if (!InitField(comp, &JSCompartment::emptyEnumeratorShape, &js_IteratorClass))
 248         return false;
 249
 250     /* Same drill for With objects. */
 251     if (!InitField(comp, &JSCompartment::emptyWithShape, &js_WithClass))
 252         return false;
 253
 254     return true;
 255 }
 256
 257 /* static */
 258 void
 259 Shape::finishEmptyShapes(JSCompartment *comp)
 260 {
 261     comp->emptyArgumentsShape = NULL;
 262     comp->emptyBlockShape = NULL;
 263     comp->emptyCallShape = NULL;
 264     comp->emptyDeclEnvShape = NULL;
 265     comp->emptyEnumeratorShape = NULL;
 266     comp->emptyWithShape = NULL;
 267 }
 268
 269 JS_STATIC_ASSERT(sizeof(JSHashNumber) == 4);
 270 JS_STATIC_ASSERT(sizeof(jsid) == JS_BYTES_PER_WORD);
 271
 272 #if JS_BYTES_PER_WORD == 4
 273 # define HASH_ID(id) ((JSHashNumber)(JSID_BITS(id)))
 274 #elif JS_BYTES_PER_WORD == 8
 275 # define HASH_ID(id) ((JSHashNumber)(JSID_BITS(id)) ^ (JSHashNumber)((JSID_BITS(id)) >> 32))
 276 #else
 277 # error "Unsupported configuration"
 278 #endif
 279
 280 /*
 281  * Double hashing needs the second hash code to be relatively prime to table
 282  * size, so we simply make hash2 odd.  The inputs to multiplicative hash are
 283  * the golden ratio, expressed as a fixed-point 32 bit fraction, and the id
 284  * itself.
 285  */
 286 #define HASH0(id)               (HASH_ID(id) * JS_GOLDEN_RATIO)
 287 #define HASH1(hash0,shift)      ((hash0) >> (shift))
 288 #define HASH2(hash0,log2,shift) ((((hash0) << (log2)) >> (shift)) | 1)
 289
 290 Shape **
 291 PropertyTable::search(jsid id, bool adding)
 292 {
 293     JSHashNumber hash0, hash1, hash2;
 294     int sizeLog2;
 295     Shape *stored, *shape, **spp, **firstRemoved;
 296     uint32 sizeMask;
 297
 298     JS_ASSERT(entries);
 299     JS_ASSERT(!JSID_IS_VOID(id));
 300
 301     /* Compute the primary hash address. */
 302     METER(hashes);
 303     hash0 = HASH0(id);
 304     hash1 = HASH1(hash0, hashShift);
 305     spp = entries + hash1;
 306
 307     /* Miss: return space for a new entry. */
 308     stored = *spp;
 309     if (SHAPE_IS_FREE(stored)) {
 310         METER(misses);
 311         METER(hashMisses);
 312         return spp;
 313     }
 314
 315     /* Hit: return entry. */
 316     shape = SHAPE_CLEAR_COLLISION(stored);
 317     if (shape && shape->id == id) {
 318         METER(hits);
 319         METER(hashHits);
 320         return spp;
 321     }
 322
 323     /* Collision: double hash. */
 324     sizeLog2 = JS_DHASH_BITS - hashShift;
 325     hash2 = HASH2(hash0, sizeLog2, hashShift);
 326     sizeMask = JS_BITMASK(sizeLog2);
 327
 328 #ifdef DEBUG
 329     jsuword collision_flag = SHAPE_COLLISION;
 330 #endif
 331
 332     /* Save the first removed entry pointer so we can recycle it if adding. */
 333     if (SHAPE_IS_REMOVED(stored)) {
 334         firstRemoved = spp;
 335     } else {
 336         firstRemoved = NULL;
 337         if (adding && !SHAPE_HAD_COLLISION(stored))
 338             SHAPE_FLAG_COLLISION(spp, shape);
 339 #ifdef DEBUG
 340         collision_flag &= jsuword(*spp) & SHAPE_COLLISION;
 341 #endif
 342     }
 343
 344     for (;;) {
 345         METER(steps);
 346         hash1 -= hash2;
 347         hash1 &= sizeMask;
 348         spp = entries + hash1;
 349
 350         stored = *spp;
 351         if (SHAPE_IS_FREE(stored)) {
 352             METER(misses);
 353             METER(stepMisses);
 354             return (adding && firstRemoved) ? firstRemoved : spp;
 355         }
 356
 357         shape = SHAPE_CLEAR_COLLISION(stored);
 358         if (shape && shape->id == id) {
 359             METER(hits);
 360             METER(stepHits);
 361             JS_ASSERT(collision_flag);
 362             return spp;
 363         }
 364
 365         if (SHAPE_IS_REMOVED(stored)) {
 366             if (!firstRemoved)
 367                 firstRemoved = spp;
 368         } else {
 369             if (adding && !SHAPE_HAD_COLLISION(stored))
 370                 SHAPE_FLAG_COLLISION(spp, shape);
 371 #ifdef DEBUG
 372             collision_flag &= jsuword(*spp) & SHAPE_COLLISION;
 373 #endif
 374         }
 375     }
 376
 377     /* NOTREACHED */
 378     return NULL;
 379 }
 380
 381 bool
 382 PropertyTable::change(int log2Delta, JSContext *cx)
 383 {
 384     int oldlog2, newlog2;
 385     uint32 oldsize, newsize, nbytes;
 386     Shape **newTable, **oldTable, **spp, **oldspp, *shape;
 387
 388     JS_ASSERT(entries);
 389
 390     /*
 391      * Grow, shrink, or compress by changing this->entries. Here, we prefer
 392      * cx->runtime->calloc to js_calloc, which on OOM waits for a background
 393      * thread to finish sweeping and retry, if appropriate. Avoid cx->calloc
 394      * so our caller can be in charge of whether to JS_ReportOutOfMemory.
 395      */
 396     oldlog2 = JS_DHASH_BITS - hashShift;
 397     newlog2 = oldlog2 + log2Delta;
 398     oldsize = JS_BIT(oldlog2);
 399     newsize = JS_BIT(newlog2);
 400     nbytes = PROPERTY_TABLE_NBYTES(newsize);
 401     newTable = (Shape **) cx->runtime->calloc(nbytes);
 402     if (!newTable) {
 403         METER(tableAllocFails);
 404         return false;
 405     }
 406
 407     /* Now that we have newTable allocated, update members. */
 408     hashShift = JS_DHASH_BITS - newlog2;
 409     removedCount = 0;
 410     oldTable = entries;
 411     entries = newTable;
 412
 413     /* Copy only live entries, leaving removed and free ones behind. */
 414     for (oldspp = oldTable; oldsize != 0; oldspp++) {
 415         shape = SHAPE_FETCH(oldspp);
 416         if (shape) {
 417             METER(searches);
 418             METER(changeSearches);
 419             spp = search(shape->id, true);
 420             JS_ASSERT(SHAPE_IS_FREE(*spp));
 421             *spp = shape;
 422         }
 423         oldsize--;
 424     }
 425
 426     /*
 427      * Finally, free the old entries storage. Note that cx->runtime->free just
 428      * calls js_free. Use js_free here to match PropertyTable::~PropertyTable,
 429      * which cannot have a cx or rt parameter.
 430      */
 431     js_free(oldTable);
 432     return true;
 433 }
 434
 435 bool
 436 PropertyTable::grow(JSContext *cx)
 437 {
 438     JS_ASSERT(needsToGrow());
 439
 440     uint32 size = capacity();
 441     int delta = removedCount < size >> 2;
 442     if (!delta)
 443         METER(compresses);
 444     else
 445         METER(grows);
 446
 447     if (!change(delta, cx) && entryCount + removedCount == size - 1) {
 448         JS_ReportOutOfMemory(cx);
 449         return false;
 450     }
 451     return true;
 452 }
 453
 454 Shape *
 455 Shape::getChild(JSContext *cx, const js::Shape &child, Shape **listp)
 456 {
 457     JS_ASSERT(!JSID_IS_VOID(child.id));
 458     JS_ASSERT(!child.inDictionary());
 459
 460     if (inDictionary()) {
 461         Shape *oldShape = *listp;
 462         PropertyTable *table = (oldShape && oldShape->hasTable()) ? oldShape->getTable() : NULL;
 463
 464         /*
 465          * Attempt to grow table if needed before extending *listp, rather than
 466          * risking OOM under table->grow after newDictionaryShape succeeds, and
 467          * then have to fix up *listp.
 468          */
 469         if (table && table->needsToGrow() && !table->grow(cx))
 470             return NULL;
 471
 472         if (newDictionaryShape(cx, child, listp)) {
 473             Shape *newShape = *listp;
 474
 475             JS_ASSERT(oldShape == newShape->parent);
 476             if (table) {
 477                 /* Add newShape to the property table. */
 478                 METER(searches);
 479                 Shape **spp = table->search(newShape->id, true);
 480
 481                 /*
 482                  * Beware duplicate formal parameters, allowed by ECMA-262 in
 483                  * non-strict mode. Otherwise we know that Bindings::add (our
 484                  * caller) won't pass an id already in the table to us. In the
 485                  * case of duplicate formals, the last one wins, so while we
 486                  * must not overcount entries, we must store newShape.
 487                  */
 488                 if (!SHAPE_FETCH(spp))
 489                     ++table->entryCount;
 490                 SHAPE_STORE_PRESERVING_COLLISION(spp, newShape);
 491
 492                 /* Hand the table off from oldShape to newShape. */
 493                 oldShape->setTable(NULL);
 494                 newShape->setTable(table);
 495             } else {
 496                 if (!newShape->hasTable())
 497                     newShape->hashify(cx->runtime);
 498             }
 499             return newShape;
 500         }
 501
 502         return NULL;
 503     }
 504
 505     if ((*listp)->entryCount() >= PropertyTree::MAX_HEIGHT) {
 506         Shape *dprop = Shape::newDictionaryList(cx, listp);
 507         if (!dprop)
 508             return NULL;
 509         return dprop->getChild(cx, child, listp);
 510     }
 511
 512     Shape *shape = JS_PROPERTY_TREE(cx).getChild(cx, this, child);
 513     if (shape) {
 514         JS_ASSERT(shape->parent == this);
 515         JS_ASSERT(this == *listp);
 516         *listp = shape;
 517     }
 518     return shape;
 519 }
 520
 521 /*
 522  * Get or create a property-tree or dictionary child property of parent, which
 523  * must be lastProp if inDictionaryMode(), else parent must be one of lastProp
 524  * or lastProp->parent.
 525  */
 526 Shape *
 527 JSObject::getChildProperty(JSContext *cx, Shape *parent, Shape &child)
 528 {
 529     JS_ASSERT(!JSID_IS_VOID(child.id));
 530     JS_ASSERT(!child.inDictionary());
 531
 532     /*
 533      * Aliases share another property's slot, passed in the |slot| parameter.
 534      * Shared properties have no slot. Unshared properties that do not alias
 535      * another property's slot allocate a slot here, but may lose it due to a
 536      * JS_ClearScope call.
 537      */
 538     if (!child.isAlias()) {
 539         if (child.attrs & JSPROP_SHARED) {
 540             child.slot = SHAPE_INVALID_SLOT;
 541         } else {
 542             /*
 543              * We may have set slot from a nearly-matching shape, above. If so,
 544              * we're overwriting that nearly-matching shape, so we can reuse
 545              * its slot -- we don't need to allocate a new one. Similarly, we
 546              * use a specific slot if provided by the caller.
 547              */
 548             if (child.slot == SHAPE_INVALID_SLOT && !allocSlot(cx, &child.slot))
 549                 return NULL;
 550         }
 551     }
 552
 553     Shape *shape;
 554
 555     if (inDictionaryMode()) {
 556         JS_ASSERT(parent == lastProp);
 557         if (parent->frozen()) {
 558             parent = Shape::newDictionaryList(cx, &lastProp);
 559             if (!parent)
 560                 return NULL;
 561             JS_ASSERT(!parent->frozen());
 562         }
 563         shape = Shape::newDictionaryShape(cx, child, &lastProp);
 564         if (!shape)
 565             return NULL;
 566     } else {
 567         shape = JS_PROPERTY_TREE(cx).getChild(cx, parent, child);
 568         if (!shape)
 569             return NULL;
 570         JS_ASSERT(shape->parent == parent);
 571         JS_ASSERT_IF(parent != lastProp, parent == lastProp->parent);
 572         setLastProperty(shape);
 573     }
 574
 575     updateFlags(shape);
 576     updateShape(cx);
 577     return shape;
 578 }
 579
 580 Shape *
 581 Shape::newDictionaryShape(JSContext *cx, const Shape &child, Shape **listp)
 582 {
 583     Shape *dprop = JS_PROPERTY_TREE(cx).newShape(cx);
 584     if (!dprop)
 585         return NULL;
 586
 587     new (dprop) Shape(child.id, child.rawGetter, child.rawSetter, child.slot, child.attrs,
 588                       (child.flags & ~FROZEN) | IN_DICTIONARY, child.shortid,
 589                       js_GenerateShape(cx), child.slotSpan);
 590
 591     dprop->listp = NULL;
 592     dprop->insertIntoDictionary(listp);
 593
 594     JS_COMPARTMENT_METER(cx->compartment->liveDictModeNodes++);
 595     return dprop;
 596 }
 597
 598 Shape *
 599 Shape::newDictionaryList(JSContext *cx, Shape **listp)
 600 {
 601     Shape *shape = *listp;
 602     Shape *list = shape;
 603
 604     Shape **childp = listp;
 605     *childp = NULL;
 606
 607     while (shape) {
 608         JS_ASSERT_IF(!shape->frozen(), !shape->inDictionary());
 609
 610         Shape *dprop = Shape::newDictionaryShape(cx, *shape, childp);
 611         if (!dprop) {
 612             METER(toDictFails);
 613             *listp = list;
 614             return NULL;
 615         }
 616
 617         JS_ASSERT(!dprop->hasTable());
 618         childp = &dprop->parent;
 619         shape = shape->parent;
 620     }
 621
 622     list = *listp;
 623     JS_ASSERT(list->inDictionary());
 624     list->hashify(cx->runtime);
 625     return list;
 626 }
 627
 628 bool
 629 JSObject::toDictionaryMode(JSContext *cx)
 630 {
 631     JS_ASSERT(!inDictionaryMode());
 632     if (!Shape::newDictionaryList(cx, &lastProp))
 633         return false;
 634
 635     clearOwnShape();
 636     return true;
 637 }
 638
 639 /*
 640  * Normalize stub getter and setter values for faster is-stub testing in the
 641  * SHAPE_CALL_[GS]ETTER macros.
 642  */
 643 static inline bool
 644 NormalizeGetterAndSetter(JSContext *cx, JSObject *obj,
 645                          jsid id, uintN attrs, uintN flags,
 646                          PropertyOp &getter,
 647                          StrictPropertyOp &setter)
 648 {
 649     if (setter == StrictPropertyStub) {
 650         JS_ASSERT(!(attrs & JSPROP_SETTER));
 651         setter = NULL;
 652     }
 653     if (flags & Shape::METHOD) {
 654         /* Here, getter is the method, a function object reference. */
 655         JS_ASSERT(getter);
 656         JS_ASSERT(!setter || setter == js_watch_set);
 657         JS_ASSERT(!(attrs & (JSPROP_GETTER | JSPROP_SETTER)));
 658     } else {
 659         if (getter == PropertyStub) {
 660             JS_ASSERT(!(attrs & JSPROP_GETTER));
 661             getter = NULL;
 662         }
 663     }
 664
 665     return true;
 666 }
 667
 668 #ifdef DEBUG
 669 # define CHECK_SHAPE_CONSISTENCY(obj) obj->checkShapeConsistency()
 670
 671 void
 672 JSObject::checkShapeConsistency()
 673 {
 674     static int throttle = -1;
 675     if (throttle < 0) {
 676         if (const char *var = getenv("JS_CHECK_SHAPE_THROTTLE"))
 677             throttle = atoi(var);
 678         if (throttle < 0)
 679             throttle = 0;
 680     }
 681     if (throttle == 0)
 682         return;
 683
 684     JS_ASSERT(isNative());
 685     if (hasOwnShape())
 686         JS_ASSERT(objShape != lastProp->shape);
 687     else
 688         JS_ASSERT(objShape == lastProp->shape);
 689
 690     Shape *shape = lastProp;
 691     Shape *prev = NULL;
 692
 693     if (inDictionaryMode()) {
 694         if (shape->hasTable()) {
 695             PropertyTable *table = shape->getTable();
 696             for (uint32 fslot = table->freelist; fslot != SHAPE_INVALID_SLOT;
 697                  fslot = getSlotRef(fslot).toPrivateUint32()) {
 698                 JS_ASSERT(fslot < shape->slotSpan);
 699             }
 700
 701             for (int n = throttle; --n >= 0 && shape->parent; shape = shape->parent) {
 702                 JS_ASSERT_IF(shape != lastProp, !shape->hasTable());
 703
 704                 Shape **spp = table->search(shape->id, false);
 705                 JS_ASSERT(SHAPE_FETCH(spp) == shape);
 706             }
 707         } else {
 708             shape = shape->parent;
 709             for (int n = throttle; --n >= 0 && shape; shape = shape->parent)
 710                 JS_ASSERT(!shape->hasTable());
 711         }
 712
 713         shape = lastProp;
 714         for (int n = throttle; --n >= 0 && shape; shape = shape->parent) {
 715             JS_ASSERT_IF(shape->slot != SHAPE_INVALID_SLOT, shape->slot < shape->slotSpan);
 716             if (!prev) {
 717                 JS_ASSERT(shape == lastProp);
 718                 JS_ASSERT(shape->listp == &lastProp);
 719             } else {
 720                 JS_ASSERT(shape->listp == &prev->parent);
 721                 JS_ASSERT(prev->slotSpan >= shape->slotSpan);
 722             }
 723             prev = shape;
 724         }
 725     } else {
 726         for (int n = throttle; --n >= 0 && shape->parent; shape = shape->parent) {
 727             if (shape->hasTable()) {
 728                 PropertyTable *table = shape->getTable();
 729                 JS_ASSERT(shape->parent);
 730                 for (Shape::Range r(shape); !r.empty(); r.popFront()) {
 731                     Shape **spp = table->search(r.front().id, false);
 732                     JS_ASSERT(SHAPE_FETCH(spp) == &r.front());
 733                 }
 734             }
 735             if (prev) {
 736                 JS_ASSERT(prev->slotSpan >= shape->slotSpan);
 737                 shape->kids.checkConsistency(prev);
 738             }
 739             prev = shape;
 740         }
 741     }
 742 }
 743 #else
 744 # define CHECK_SHAPE_CONSISTENCY(obj) ((void)0)
 745 #endif
 746
 747 const Shape *
 748 JSObject::addProperty(JSContext *cx, jsid id,
 749                       PropertyOp getter, StrictPropertyOp setter,
 750                       uint32 slot, uintN attrs,
 751                       uintN flags, intN shortid)
 752 {
 753     JS_ASSERT(!JSID_IS_VOID(id));
 754
 755     if (!isExtensible()) {
 756         reportNotExtensible(cx);
 757         return NULL;
 758     }
 759
 760     NormalizeGetterAndSetter(cx, this, id, attrs, flags, getter, setter);
 761
 762     /* Search for id with adding = true in order to claim its entry. */
 763     Shape **spp = nativeSearch(id, true);
 764     JS_ASSERT(!SHAPE_FETCH(spp));
 765     const Shape *shape = addPropertyInternal(cx, id, getter, setter, slot, attrs,
 766                                              flags, shortid, spp);
 767     if (!shape)
 768         return NULL;
 769
 770     /* Update any watchpoints referring to this property. */
 771     shape = js_UpdateWatchpointsForShape(cx, this, shape);
 772     if (!shape)
 773         METER(wrapWatchFails);
 774
 775     return shape;
 776 }
 777
 778 const Shape *
 779 JSObject::addPropertyInternal(JSContext *cx, jsid id,
 780                               PropertyOp getter, StrictPropertyOp setter,
 781                               uint32 slot, uintN attrs,
 782                               uintN flags, intN shortid,
 783                               Shape **spp)
 784 {
 785     JS_ASSERT_IF(inDictionaryMode(), !lastProp->frozen());
 786
 787     PropertyTable *table = NULL;
 788     if (!inDictionaryMode()) {
 789         if (lastProp->entryCount() >= PropertyTree::MAX_HEIGHT) {
 790             if (!toDictionaryMode(cx))
 791                 return NULL;
 792             spp = nativeSearch(id, true);
 793             table = lastProp->getTable();
 794         }
 795     } else if (lastProp->hasTable()) {
 796         table = lastProp->getTable();
 797         if (table->needsToGrow()) {
 798             if (!table->grow(cx))
 799                 return NULL;
 800
 801             METER(searches);
 802             METER(changeSearches);
 803             spp = table->search(id, true);
 804             JS_ASSERT(!SHAPE_FETCH(spp));
 805         }
 806     }
 807
 808     /* Find or create a property tree node labeled by our arguments. */
 809     const Shape *shape;
 810     {
 811         Shape child(id, getter, setter, slot, attrs, flags, shortid);
 812         shape = getChildProperty(cx, lastProp, child);
 813     }
 814
 815     if (shape) {
 816         JS_ASSERT(shape == lastProp);
 817
 818         if (table) {
 819             /* Store the tree node pointer in the table entry for id. */
 820             SHAPE_STORE_PRESERVING_COLLISION(spp, shape);
 821             ++table->entryCount;
 822
 823             /* Pass the table along to the new lastProp, namely shape. */
 824             JS_ASSERT(shape->parent->getTable() == table);
 825             shape->parent->setTable(NULL);
 826             shape->setTable(table);
 827         }
 828 #ifdef DEBUG
 829         LIVE_SCOPE_METER(cx, ++cx->runtime->liveObjectProps);
 830 #endif
 831         CHECK_SHAPE_CONSISTENCY(this);
 832         METER(adds);
 833         return shape;
 834     }
 835
 836     CHECK_SHAPE_CONSISTENCY(this);
 837     METER(addFails);
 838     return NULL;
 839 }
 840
 841 /*
 842  * Check and adjust the new attributes for the shape to make sure that our
 843  * slot access optimizations are sound. It is responsibility of the callers to
 844  * enforce all restrictions from ECMA-262 v5 8.12.9 [[DefineOwnProperty]].
 845  */
 846 inline bool
 847 CheckCanChangeAttrs(JSContext *cx, JSObject *obj, const Shape *shape, uintN *attrsp)
 848 {
 849     if (shape->configurable())
 850         return true;
 851
 852     /* A permanent property must stay permanent. */
 853     *attrsp |= JSPROP_PERMANENT;
 854
 855     /* Reject attempts to remove a slot from the permanent data property. */
 856     if (shape->isDataDescriptor() && shape->hasSlot() &&
 857         (*attrsp & (JSPROP_GETTER | JSPROP_SETTER | JSPROP_SHARED))) {
 858         obj->reportNotConfigurable(cx, shape->id);
 859         return false;
 860     }
 861
 862     return true;
 863 }
 864
 865 const Shape *
 866 JSObject::putProperty(JSContext *cx, jsid id,
 867                       PropertyOp getter, StrictPropertyOp setter,
 868                       uint32 slot, uintN attrs,
 869                       uintN flags, intN shortid)
 870 {
 871     JS_ASSERT(!JSID_IS_VOID(id));
 872
 873     /*
 874      * Horrid non-strict eval, debuggers, and |default xml namespace ...| may
 875      * extend Call objects.
 876      */
 877     if (lastProp->frozen()) {
 878         if (!Shape::newDictionaryList(cx, &lastProp))
 879             return NULL;
 880         JS_ASSERT(!lastProp->frozen());
 881     }
 882
 883     NormalizeGetterAndSetter(cx, this, id, attrs, flags, getter, setter);
 884
 885     /* Search for id in order to claim its entry if table has been allocated. */
 886     Shape **spp = nativeSearch(id, true);
 887     Shape *shape = SHAPE_FETCH(spp);
 888     if (!shape) {
 889         /*
 890          * You can't add properties to a non-extensible object, but you can change
 891          * attributes of properties in such objects.
 892          */
 893         if (!isExtensible()) {
 894             reportNotExtensible(cx);
 895             return NULL;
 896         }
 897
 898         const Shape *newShape =
 899             addPropertyInternal(cx, id, getter, setter, slot, attrs, flags, shortid, spp);
 900         if (!newShape)
 901             return NULL;
 902         newShape = js_UpdateWatchpointsForShape(cx, this, newShape);
 903         if (!newShape)
 904             METER(wrapWatchFails);
 905         return newShape;
 906     }
 907
 908     /* Property exists: search must have returned a valid *spp. */
 909     JS_ASSERT(!SHAPE_IS_REMOVED(*spp));
 910
 911     if (!CheckCanChangeAttrs(cx, this, shape, &attrs))
 912         return NULL;
 913
 914     /*
 915      * If the caller wants to allocate a slot, but doesn't care which slot,
 916      * copy the existing shape's slot into slot so we can match shape, if all
 917      * other members match.
 918      */
 919     bool hadSlot = !shape->isAlias() && shape->hasSlot();
 920     uint32 oldSlot = shape->slot;
 921     if (!(attrs & JSPROP_SHARED) && slot == SHAPE_INVALID_SLOT && hadSlot)
 922         slot = oldSlot;
 923
 924     /*
 925      * Now that we've possibly preserved slot, check whether all members match.
 926      * If so, this is a redundant "put" and we can return without more work.
 927      */
 928     if (shape->matchesParamsAfterId(getter, setter, slot, attrs, flags, shortid)) {
 929         METER(redundantPuts);
 930         return shape;
 931     }
 932
 933     /*
 934      * Overwriting a non-last property requires switching to dictionary mode.
 935      * The shape tree is shared immutable, and we can't removeProperty and then
 936      * addPropertyInternal because a failure under add would lose data.
 937      */
 938     if (shape != lastProp && !inDictionaryMode()) {
 939         if (!toDictionaryMode(cx))
 940             return NULL;
 941         spp = nativeSearch(shape->id);
 942         shape = SHAPE_FETCH(spp);
 943     }
 944
 945     /*
 946      * Now that we have passed the lastProp->frozen() check at the top of this
 947      * method, and the non-last-property conditioning just above, we are ready
 948      * to overwrite.
 949      *
 950      * Optimize the case of a non-frozen dictionary-mode object based on the
 951      * property that dictionaries exclusively own their mutable shape structs,
 952      * each of which has a unique shape number (not shared via a shape tree).
 953      *
 954      * This is more than an optimization: it is required to preserve for-in
 955      * enumeration order (see bug 601399).
 956      */
 957     if (inDictionaryMode()) {
 958         /* FIXME bug 593129 -- slot allocation and JSObject *this must move out of here! */
 959         if (slot == SHAPE_INVALID_SLOT && !(attrs & JSPROP_SHARED) && !(flags & Shape::ALIAS)) {
 960             if (!allocSlot(cx, &slot))
 961                 return NULL;
 962         }
 963
 964         shape->slot = slot;
 965         if (slot != SHAPE_INVALID_SLOT && slot >= shape->slotSpan) {
 966             shape->slotSpan = slot + 1;
 967
 968             for (Shape *temp = lastProp; temp != shape; temp = temp->parent) {
 969                 if (temp->slotSpan <= slot)
 970                     temp->slotSpan = slot + 1;
 971             }
 972         }
 973
 974         shape->rawGetter = getter;
 975         shape->rawSetter = setter;
 976         shape->attrs = uint8(attrs);
 977         shape->flags = flags | Shape::IN_DICTIONARY;
 978         shape->shortid = int16(shortid);
 979
 980         /*
 981          * We are done updating shape and lastProp. Now we may need to update
 982          * flags and we will need to update objShape, which is no longer "own".
 983          * In the last non-dictionary property case in the else clause just
 984          * below, getChildProperty handles this for us. First update flags.
 985          */
 986         updateFlags(shape);
 987
 988         /*
 989          * We have just mutated shape in place, but nothing caches it based on
 990          * shape->shape unless shape is lastProp and !hasOwnShape()). Therefore
 991          * we regenerate only lastProp->shape. We will clearOwnShape(), which
 992          * sets objShape to lastProp->shape.
 993          */
 994         lastProp->shape = js_GenerateShape(cx);
 995         clearOwnShape();
 996     } else {
 997         /*
 998          * Updating lastProp in a non-dictionary-mode object. Such objects
 999          * share their shapes via a tree rooted at a prototype emptyShape, or
1000          * perhaps a well-known compartment-wide singleton emptyShape.
1001          *
1002          * If any shape in the tree has a property hashtable, it is shared and
1003          * immutable too, therefore we must not update *spp.
1004          */
1005         JS_ASSERT(shape == lastProp);
1006         removeLastProperty();
1007
1008         /* Find or create a property tree node labeled by our arguments. */
1009         Shape child(id, getter, setter, slot, attrs, flags, shortid);
1010
1011         Shape *newShape = getChildProperty(cx, lastProp, child);
1012         if (!newShape) {
1013             setLastProperty(shape);
1014             CHECK_SHAPE_CONSISTENCY(this);
1015             METER(putFails);
1016             return NULL;
1017         }
1018
1019         shape = newShape;
1020     }
1021
1022     /*
1023      * Can't fail now, so free the previous incarnation's slot if the new shape
1024      * has no slot. But we do not need to free oldSlot (and must not, as trying
1025      * to will botch an assertion in JSObject::freeSlot) if the new lastProp
1026      * (shape here) has a slotSpan that does not cover it.
1027      */
1028     if (hadSlot && !shape->hasSlot()) {
1029         if (oldSlot < shape->slotSpan)
1030             freeSlot(cx, oldSlot);
1031 #ifdef DEBUG
1032         else
1033             getSlotRef(oldSlot).setUndefined();
1034 #endif
1035         JS_ATOMIC_INCREMENT(&cx->runtime->propertyRemovals);
1036     }
1037
1038     CHECK_SHAPE_CONSISTENCY(this);
1039     METER(puts);
1040
1041     const Shape *newShape = js_UpdateWatchpointsForShape(cx, this, shape);
1042     if (!newShape)
1043         METER(wrapWatchFails);
1044     return newShape;
1045 }
1046
1047 const Shape *
1048 JSObject::changeProperty(JSContext *cx, const Shape *shape, uintN attrs, uintN mask,
1049                          PropertyOp getter, StrictPropertyOp setter)
1050 {
1051     JS_ASSERT_IF(inDictionaryMode(), !lastProp->frozen());
1052     JS_ASSERT(!JSID_IS_VOID(shape->id));
1053     JS_ASSERT(nativeContains(*shape));
1054
1055     attrs |= shape->attrs & mask;
1056
1057     /* Allow only shared (slotless) => unshared (slotful) transition. */
1058     JS_ASSERT(!((attrs ^ shape->attrs) & JSPROP_SHARED) ||
1059               !(attrs & JSPROP_SHARED));
1060
1061     /* Don't allow method properties to be changed to have a getter. */
1062     JS_ASSERT_IF(getter != shape->rawGetter, !shape->isMethod());
1063
1064     if (getter == PropertyStub)
1065         getter = NULL;
1066     if (setter == StrictPropertyStub)
1067         setter = NULL;
1068
1069     if (!CheckCanChangeAttrs(cx, this, shape, &attrs))
1070         return NULL;
1071
1072     if (shape->attrs == attrs && shape->getter() == getter && shape->setter() == setter)
1073         return shape;
1074
1075     const Shape *newShape;
1076
1077     /*
1078      * Dictionary-mode objects exclusively own their mutable shape structs, so
1079      * we simply modify in place.
1080      */
1081     if (inDictionaryMode()) {
1082         /* FIXME bug 593129 -- slot allocation and JSObject *this must move out of here! */
1083         uint32 slot = shape->slot;
1084         if (slot == SHAPE_INVALID_SLOT && !(attrs & JSPROP_SHARED) && !(flags & Shape::ALIAS)) {
1085             if (!allocSlot(cx, &slot))
1086                 return NULL;
1087         }
1088
1089         Shape *mutableShape = const_cast<Shape *>(shape);
1090         mutableShape->slot = slot;
1091         if (slot != SHAPE_INVALID_SLOT && slot >= shape->slotSpan) {
1092             mutableShape->slotSpan = slot + 1;
1093
1094             for (Shape *temp = lastProp; temp != shape; temp = temp->parent) {
1095                 if (temp->slotSpan <= slot)
1096                     temp->slotSpan = slot + 1;
1097             }
1098         }
1099
1100         mutableShape->rawGetter = getter;
1101         mutableShape->rawSetter = setter;
1102         mutableShape->attrs = uint8(attrs);
1103
1104         updateFlags(shape);
1105
1106         /* See the corresponding code in putProperty. */
1107         lastProp->shape = js_GenerateShape(cx);
1108         clearOwnShape();
1109
1110         shape = js_UpdateWatchpointsForShape(cx, this, shape);
1111         if (!shape) {
1112             METER(wrapWatchFails);
1113             return NULL;
1114         }
1115         JS_ASSERT(shape == mutableShape);
1116         newShape = mutableShape;
1117     } else if (shape == lastProp) {
1118         Shape child(shape->id, getter, setter, shape->slot, attrs, shape->flags, shape->shortid);
1119
1120         newShape = getChildProperty(cx, shape->parent, child);
1121 #ifdef DEBUG
1122         if (newShape) {
1123             JS_ASSERT(newShape == lastProp);
1124             if (newShape->hasTable()) {
1125                 Shape **spp = nativeSearch(shape->id);
1126                 JS_ASSERT(SHAPE_FETCH(spp) == newShape);
1127             }
1128         }
1129 #endif
1130     } else {
1131         /*
1132          * Let JSObject::putProperty handle this |overwriting| case, including
1133          * the conservation of shape->slot (if it's valid). We must not call
1134          * removeProperty because it will free an allocated shape->slot, and
1135          * putProperty won't re-allocate it.
1136          */
1137         Shape child(shape->id, getter, setter, shape->slot, attrs, shape->flags, shape->shortid);
1138         newShape = putProperty(cx, child.id, child.rawGetter, child.rawSetter, child.slot,
1139                                child.attrs, child.flags, child.shortid);
1140 #ifdef DEBUG
1141         if (newShape)
1142             METER(changePuts);
1143 #endif
1144     }
1145
1146 #ifdef DEBUG
1147     CHECK_SHAPE_CONSISTENCY(this);
1148     if (newShape)
1149         METER(changes);
1150     else
1151         METER(changeFails);
1152 #endif
1153     return newShape;
1154 }
1155
1156 bool
1157 JSObject::removeProperty(JSContext *cx, jsid id)
1158 {
1159     Shape **spp = nativeSearch(id);
1160     Shape *shape = SHAPE_FETCH(spp);
1161     if (!shape) {
1162         METER(uselessRemoves);
1163         return true;
1164     }
1165
1166     /* First, if shape is unshared and not has a slot, free its slot number. */
1167     bool addedToFreelist = false;
1168     bool hadSlot = !shape->isAlias() && shape->hasSlot();
1169     if (hadSlot) {
1170         addedToFreelist = freeSlot(cx, shape->slot);
1171         JS_ATOMIC_INCREMENT(&cx->runtime->propertyRemovals);
1172     }
1173
1174
1175     /* If shape is not the last property added, switch to dictionary mode. */
1176     if (shape != lastProp && !inDictionaryMode()) {
1177         if (!toDictionaryMode(cx))
1178             return false;
1179         spp = nativeSearch(shape->id);
1180         shape = SHAPE_FETCH(spp);
1181     }
1182
1183     /*
1184      * A dictionary-mode object owns mutable, unique shapes on a non-circular
1185      * doubly linked list, optionally hashed by lastProp->table. So we can edit
1186      * the list and hash in place.
1187      */
1188     if (inDictionaryMode()) {
1189         PropertyTable *table = lastProp->hasTable() ? lastProp->getTable() : NULL;
1190
1191         if (SHAPE_HAD_COLLISION(*spp)) {
1192             JS_ASSERT(table);
1193             *spp = SHAPE_REMOVED;
1194             ++table->removedCount;
1195             --table->entryCount;
1196         } else {
1197             METER(removeFrees);
1198             if (table) {
1199                 *spp = NULL;
1200                 --table->entryCount;
1201
1202 #ifdef DEBUG
1203                 /*
1204                  * Check the consistency of the table but limit the number of
1205                  * checks not to alter significantly the complexity of the
1206                  * delete in debug builds, see bug 534493.
1207                  */
1208                 const Shape *aprop = lastProp;
1209                 for (int n = 50; --n >= 0 && aprop->parent; aprop = aprop->parent)
1210                     JS_ASSERT_IF(aprop != shape, nativeContains(*aprop));
1211 #endif
1212             }
1213         }
1214
1215         /*
1216          * Remove shape from its non-circular doubly linked list, setting this
1217          * object's OWN_SHAPE flag so the updateShape(cx) further below will
1218          * generate a fresh shape id for this object, distinct from the id of
1219          * any shape in the list. We need a fresh shape for all deletions, even
1220          * of lastProp. Otherwise, a shape number could replay and caches might
1221          * return get deleted DictionaryShapes! See bug 595365.
1222          */
1223         flags |= OWN_SHAPE;
1224
1225         Shape *oldLastProp = lastProp;
1226         shape->removeFromDictionary(this);
1227         if (table) {
1228             if (shape == oldLastProp) {
1229                 JS_ASSERT(shape->getTable() == table);
1230                 JS_ASSERT(shape->parent == lastProp);
1231                 JS_ASSERT(shape->slotSpan >= lastProp->slotSpan);
1232                 JS_ASSERT_IF(hadSlot, shape->slot + 1 <= shape->slotSpan);
1233
1234                 /*
1235                  * Maintain slot freelist consistency. The only constraint we
1236                  * have is that slot numbers on the freelist are less than
1237                  * lastProp->slotSpan. Thus, if the freelist is non-empty,
1238                  * then lastProp->slotSpan may not decrease.
1239                  */
1240                 if (table->freelist != SHAPE_INVALID_SLOT) {
1241                     lastProp->slotSpan = shape->slotSpan;
1242
1243                     /* Add the slot to the freelist if it wasn't added in freeSlot. */
1244                     if (hadSlot && !addedToFreelist) {
1245                         getSlotRef(shape->slot).setPrivateUint32(table->freelist);
1246                         table->freelist = shape->slot;
1247                     }
1248                 }
1249             }
1250
1251             /* Hand off table from old to new lastProp. */
1252             oldLastProp->setTable(NULL);
1253             lastProp->setTable(table);
1254         }
1255     } else {
1256         /*
1257          * Non-dictionary-mode property tables are shared immutables, so all we
1258          * need do is retract lastProp and we'll either get or else lazily make
1259          * via a later hashify the exact table for the new property lineage.
1260          */
1261         JS_ASSERT(shape == lastProp);
1262         removeLastProperty();
1263
1264         /*
1265          * Revert to fixed slots if this was the first dynamically allocated slot,
1266          * preserving invariant that objects with the same shape use the fixed
1267          * slots in the same way.
1268          */
1269         size_t fixed = numFixedSlots();
1270         if (shape->slot == fixed) {
1271             JS_ASSERT_IF(!lastProp->isEmptyShape() && lastProp->hasSlot(),
1272                          lastProp->slot == fixed - 1);
1273             revertToFixedSlots(cx);
1274         }
1275     }
1276     updateShape(cx);
1277
1278     /* On the way out, consider shrinking table if its load factor is <= .25. */
1279     if (lastProp->hasTable()) {
1280         PropertyTable *table = lastProp->getTable();
1281         uint32 size = table->capacity();
1282         if (size > PropertyTable::MIN_SIZE && table->entryCount <= size >> 2) {
1283             METER(shrinks);
1284             (void) table->change(-1, cx);
1285         }
1286     }
1287
1288     CHECK_SHAPE_CONSISTENCY(this);
1289     LIVE_SCOPE_METER(cx, --cx->runtime->liveObjectProps);
1290     METER(removes);
1291     return true;
1292 }
1293
1294 void
1295 JSObject::clear(JSContext *cx)
1296 {
1297     LIVE_SCOPE_METER(cx, cx->runtime->liveObjectProps -= propertyCount());
1298
1299     Shape *shape = lastProp;
1300     JS_ASSERT(inDictionaryMode() == shape->inDictionary());
1301
1302     while (shape->parent) {
1303         shape = shape->parent;
1304         JS_ASSERT(inDictionaryMode() == shape->inDictionary());
1305     }
1306     JS_ASSERT(shape->isEmptyShape());
1307
1308     if (inDictionaryMode())
1309         shape->listp = &lastProp;
1310
1311     /*
1312      * Revert to fixed slots if we have cleared below the first dynamically
1313      * allocated slot, preserving invariant that objects with the same shape
1314      * use the fixed slots in the same way.
1315      */
1316     if (hasSlotsArray() && JSSLOT_FREE(getClass()) <= numFixedSlots())
1317         revertToFixedSlots(cx);
1318
1319     /*
1320      * We have rewound to a uniquely-shaped empty scope, so we don't need an
1321      * override for this object's shape.
1322      */
1323     clearOwnShape();
1324     setMap(shape);
1325
1326     LeaveTraceIfGlobalObject(cx, this);
1327     JS_ATOMIC_INCREMENT(&cx->runtime->propertyRemovals);
1328     CHECK_SHAPE_CONSISTENCY(this);
1329 }
1330
1331 void
1332 JSObject::generateOwnShape(JSContext *cx)
1333 {
1334 #ifdef JS_TRACER
1335     JS_ASSERT_IF(!parent && JS_ON_TRACE(cx), JS_TRACE_MONITOR_ON_TRACE(cx)->bailExit);
1336     LeaveTraceIfGlobalObject(cx, this);
1337
1338     /*
1339      * If we are recording, here is where we forget already-guarded shapes.
1340      * Any subsequent property operation upon object on the trace currently
1341      * being recorded will re-guard (and re-memoize).
1342      */
1343     if (TraceRecorder *tr = TRACE_RECORDER(cx))
1344         tr->forgetGuardedShapesForObject(this);
1345 #endif
1346
1347     setOwnShape(js_GenerateShape(cx));
1348 }
1349
1350 void
1351 JSObject::deletingShapeChange(JSContext *cx, const Shape &shape)
1352 {
1353     JS_ASSERT(!JSID_IS_VOID(shape.id));
1354     generateOwnShape(cx);
1355 }
1356
1357 const Shape *
1358 JSObject::methodShapeChange(JSContext *cx, const Shape &shape)
1359 {
1360     const Shape *result = &shape;
1361
1362     JS_ASSERT(!JSID_IS_VOID(shape.id));
1363     if (shape.isMethod()) {
1364 #ifdef DEBUG
1365         const Value &prev = nativeGetSlot(shape.slot);
1366         JS_ASSERT(&shape.methodObject() == &prev.toObject());
1367         JS_ASSERT(canHaveMethodBarrier());
1368         JS_ASSERT(hasMethodBarrier());
1369         JS_ASSERT(!shape.rawSetter || shape.rawSetter == js_watch_set);
1370 #endif
1371
1372         /*
1373          * Pass null to make a stub getter, but pass along shape.rawSetter to
1374          * preserve watchpoints. Clear Shape::METHOD from flags as we are
1375          * despecializing from a method memoized in the property tree to a
1376          * plain old function-valued property.
1377          */
1378         result = putProperty(cx, shape.id, NULL, shape.rawSetter, shape.slot,
1379                              shape.attrs,
1380                              shape.getFlags() & ~Shape::METHOD,
1381                              shape.shortid);
1382         if (!result)
1383             return NULL;
1384     }
1385
1386     if (branded()) {
1387         uintN thrashCount = getMethodThrashCount();
1388         if (thrashCount < JSObject::METHOD_THRASH_COUNT_MAX) {
1389             ++thrashCount;
1390             setMethodThrashCount(thrashCount);
1391             if (thrashCount == JSObject::METHOD_THRASH_COUNT_MAX) {
1392                 unbrand(cx);
1393                 return result;
1394             }
1395         }
1396     }
1397
1398     generateOwnShape(cx);
1399     return result;
1400 }
1401
1402 bool
1403 JSObject::methodShapeChange(JSContext *cx, uint32 slot)
1404 {
1405     if (!hasMethodBarrier()) {
1406         generateOwnShape(cx);
1407     } else {
1408         for (Shape::Range r = lastProp->all(); !r.empty(); r.popFront()) {
1409             const Shape &shape = r.front();
1410             JS_ASSERT(!JSID_IS_VOID(shape.id));
1411             if (shape.slot == slot)
1412                 return methodShapeChange(cx, shape) != NULL;
1413         }
1414     }
1415     return true;
1416 }
1417
1418 void
1419 JSObject::protoShapeChange(JSContext *cx)
1420 {
1421     generateOwnShape(cx);
1422 }
1423
1424 void
1425 JSObject::shadowingShapeChange(JSContext *cx, const Shape &shape)
1426 {
1427     JS_ASSERT(!JSID_IS_VOID(shape.id));
1428     generateOwnShape(cx);
1429 }
1430
1431 bool
1432 JSObject::globalObjectOwnShapeChange(JSContext *cx)
1433 {
1434     generateOwnShape(cx);
1435     return !js_IsPropertyCacheDisabled(cx);
1436 }
1437
1438 #ifdef DEBUG
1439 static void
1440 PrintPropertyGetterOrSetter(JSTracer *trc, char *buf, size_t bufsize)
1441 {
1442     Shape *shape;
1443     jsid id;
1444     size_t n;
1445     const char *name;
1446
1447     JS_ASSERT(trc->debugPrinter == PrintPropertyGetterOrSetter);
1448     shape = (Shape *)trc->debugPrintArg;
1449     id = shape->id;
1450     JS_ASSERT(!JSID_IS_VOID(id));
1451     name = trc->debugPrintIndex ? js_setter_str : js_getter_str;
1452
1453     if (JSID_IS_ATOM(id)) {
1454         n = PutEscapedString(buf, bufsize, JSID_TO_ATOM(id), 0);
1455         if (n < bufsize)
1456             JS_snprintf(buf + n, bufsize - n, " %s", name);
1457     } else if (JSID_IS_INT(shape->id)) {
1458         JS_snprintf(buf, bufsize, "%d %s", JSID_TO_INT(id), name);
1459     } else {
1460         JS_snprintf(buf, bufsize, "<object> %s", name);
1461     }
1462 }
1463
1464 static void
1465 PrintPropertyMethod(JSTracer *trc, char *buf, size_t bufsize)
1466 {
1467     Shape *shape;
1468     jsid id;
1469     size_t n;
1470
1471     JS_ASSERT(trc->debugPrinter == PrintPropertyMethod);
1472     shape = (Shape *)trc->debugPrintArg;
1473     id = shape->id;
1474     JS_ASSERT(!JSID_IS_VOID(id));
1475
1476     JS_ASSERT(JSID_IS_ATOM(id));
1477     n = PutEscapedString(buf, bufsize, JSID_TO_ATOM(id), 0);
1478     if (n < bufsize)
1479         JS_snprintf(buf + n, bufsize - n, " method");
1480 }
1481 #endif
1482
1483 void
1484 Shape::trace(JSTracer *trc) const
1485 {
1486     if (IS_GC_MARKING_TRACER(trc))
1487         mark();
1488
1489     MarkId(trc, id, "id");
1490
1491     if (attrs & (JSPROP_GETTER | JSPROP_SETTER)) {
1492         if ((attrs & JSPROP_GETTER) && rawGetter) {
1493             JS_SET_TRACING_DETAILS(trc, PrintPropertyGetterOrSetter, this, 0);
1494             Mark(trc, getterObject());
1495         }
1496         if ((attrs & JSPROP_SETTER) && rawSetter) {
1497             JS_SET_TRACING_DETAILS(trc, PrintPropertyGetterOrSetter, this, 1);
1498             Mark(trc, setterObject());
1499         }
1500     }
1501
1502     if (isMethod()) {
1503         JS_SET_TRACING_DETAILS(trc, PrintPropertyMethod, this, 0);
1504         Mark(trc, &methodObject());
1505     }
1506 }