js/src/vm/PropMap.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "vm/PropMap-inl.h"
   8
   9 #include "gc/HashUtil.h"
  10 #include "js/GCVector.h"
  11 #include "js/Printer.h"  // js::GenericPrinter, js::Fprinter
  12 #include "vm/JSObject.h"
  13 #include "vm/JSONPrinter.h"  // JSONPrinter
  14
  15 #include "gc/GCContext-inl.h"
  16 #include "gc/Marking-inl.h"
  17 #include "vm/JSContext-inl.h"
  18 #include "vm/ObjectFlags-inl.h"
  19
  20 using namespace js;
  21
  22 void PropMap::addSizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf,
  23                                      size_t* children, size_t* tables) const {
  24   if (isShared() && asShared()->hasChildrenSet()) {
  25     auto* set = asShared()->treeDataRef().children.toChildrenSet();
  26     *children += set->shallowSizeOfIncludingThis(mallocSizeOf);
  27   }
  28   if (canHaveTable() && asLinked()->hasTable()) {
  29     *tables += asLinked()->data_.table->sizeOfIncludingThis(mallocSizeOf);
  30   }
  31 }
  32
  33 // static
  34 SharedPropMap* SharedPropMap::create(JSContext* cx, Handle<SharedPropMap*> prev,
  35                                      HandleId id, PropertyInfo prop) {
  36   // If the first property has a slot number <= MaxSlotNumber, all properties
  37   // added later will have a slot number <= CompactPropertyInfo::MaxSlotNumber
  38   // so we can use a CompactPropMap.
  39   static constexpr size_t MaxFirstSlot =
  40       CompactPropertyInfo::MaxSlotNumber - (PropMap::Capacity - 1);
  41
  42   if (!prev && prop.maybeSlot() <= MaxFirstSlot) {
  43     return cx->newCell<CompactPropMap>(id, prop);
  44   }
  45
  46   return cx->newCell<NormalPropMap>(prev, id, prop);
  47 }
  48
  49 // static
  50 SharedPropMap* SharedPropMap::createInitial(JSContext* cx, HandleId id,
  51                                             PropertyInfo prop) {
  52   // Lookup or create a shared map based on the first property.
  53
  54   using Lookup = InitialPropMapHasher::Lookup;
  55
  56   auto& table = cx->zone()->shapeZone().initialPropMaps;
  57
  58   auto p = MakeDependentAddPtr(cx, table, Lookup(id, prop));
  59   if (p) {
  60     return *p;
  61   }
  62
  63   SharedPropMap* result = create(cx, /* prev = */ nullptr, id, prop);
  64   if (!result) {
  65     return nullptr;
  66   }
  67
  68   Lookup lookup(id, prop);
  69   if (!p.add(cx, table, lookup, result)) {
  70     return nullptr;
  71   }
  72
  73   return result;
  74 }
  75
  76 // static
  77 SharedPropMap* SharedPropMap::clone(JSContext* cx, Handle<SharedPropMap*> map,
  78                                     uint32_t length) {
  79   MOZ_ASSERT(length > 0);
  80
  81   if (map->isCompact()) {
  82     Rooted<CompactPropMap*> prev(cx, map->asCompact());
  83     return cx->newCell<CompactPropMap>(prev, length);
  84   }
  85
  86   Rooted<NormalPropMap*> prev(cx, map->asNormal());
  87   return cx->newCell<NormalPropMap>(prev, length);
  88 }
  89
  90 // static
  91 DictionaryPropMap* SharedPropMap::toDictionaryMap(JSContext* cx,
  92                                                   Handle<SharedPropMap*> map,
  93                                                   uint32_t length) {
  94   // Starting at the last map, clone each shared map to a new dictionary map.
  95
  96   Rooted<DictionaryPropMap*> lastDictMap(cx);
  97   Rooted<DictionaryPropMap*> nextDictMap(cx);
  98
  99   Rooted<SharedPropMap*> sharedMap(cx, map);
 100   uint32_t sharedLength = length;
 101   while (true) {
 102     sharedMap->setHadDictionaryConversion();
 103
 104     DictionaryPropMap* dictMap;
 105     if (sharedMap->isCompact()) {
 106       Rooted<CompactPropMap*> prev(cx, sharedMap->asCompact());
 107       dictMap = cx->newCell<DictionaryPropMap>(prev, sharedLength);
 108     } else {
 109       Rooted<NormalPropMap*> prev(cx, sharedMap->asNormal());
 110       dictMap = cx->newCell<DictionaryPropMap>(prev, sharedLength);
 111     }
 112     if (!dictMap) {
 113       return nullptr;
 114     }
 115
 116     if (!lastDictMap) {
 117       lastDictMap = dictMap;
 118     }
 119
 120     if (nextDictMap) {
 121       nextDictMap->initPrevious(dictMap);
 122     }
 123     nextDictMap = dictMap;
 124
 125     if (!sharedMap->hasPrevious()) {
 126       break;
 127     }
 128     sharedMap = sharedMap->asNormal()->previous();
 129     sharedLength = PropMap::Capacity;
 130   }
 131
 132   return lastDictMap;
 133 }
 134
 135 static MOZ_ALWAYS_INLINE SharedPropMap* PropMapChildReadBarrier(
 136     SharedPropMap* parent, SharedPropMap* child) {
 137   JS::Zone* zone = child->zone();
 138   if (zone->needsIncrementalBarrier()) {
 139     // We need a read barrier for the map tree, since these are weak
 140     // pointers.
 141     ReadBarrier(child);
 142     return child;
 143   }
 144
 145   if (MOZ_UNLIKELY(zone->isGCSweeping() &&
 146                    IsAboutToBeFinalizedUnbarriered(child))) {
 147     // The map we've found is unreachable and due to be finalized, so
 148     // remove our weak reference to it and don't use it.
 149     MOZ_ASSERT(parent->isMarkedAny());
 150     parent->removeChild(zone->runtimeFromMainThread()->gcContext(), child);
 151     return nullptr;
 152   }
 153
 154   // We don't yield to the mutator when the zone is in this state so we don't
 155   // need to account for it here.
 156   MOZ_ASSERT(!zone->isGCCompacting());
 157
 158   return child;
 159 }
 160
 161 SharedPropMap* SharedPropMap::lookupChild(uint32_t length, HandleId id,
 162                                           PropertyInfo prop) {
 163   MOZ_ASSERT(length > 0);
 164
 165   SharedChildrenPtr children = treeDataRef().children;
 166   if (children.isNone()) {
 167     return nullptr;
 168   }
 169
 170   if (!hasChildrenSet()) {
 171     SharedPropMapAndIndex prevChild = children.toSingleChild();
 172     if (prevChild.index() == length - 1) {
 173       SharedPropMap* child = prevChild.map();
 174       uint32_t newPropIndex = indexOfNextProperty(length - 1);
 175       if (child->matchProperty(newPropIndex, id, prop)) {
 176         return PropMapChildReadBarrier(this, child);
 177       }
 178     }
 179     return nullptr;
 180   }
 181
 182   SharedChildrenSet* set = children.toChildrenSet();
 183   SharedChildrenHasher::Lookup lookup(id, prop, length - 1);
 184   if (auto p = set->lookup(lookup)) {
 185     MOZ_ASSERT(p->index() == length - 1);
 186     SharedPropMap* child = p->map();
 187     return PropMapChildReadBarrier(this, child);
 188   }
 189   return nullptr;
 190 }
 191
 192 bool SharedPropMap::addChild(JSContext* cx, SharedPropMapAndIndex child,
 193                              HandleId id, PropertyInfo prop) {
 194   SharedPropMap* childMap = child.map();
 195
 196 #ifdef DEBUG
 197   // If the parent map was full, the child map must have the parent as
 198   // |previous| map. Else, the parent and child have the same |previous| map.
 199   if (childMap->hasPrevious()) {
 200     if (child.index() == PropMap::Capacity - 1) {
 201       MOZ_ASSERT(childMap->asLinked()->previous() == this);
 202     } else {
 203       MOZ_ASSERT(childMap->asLinked()->previous() == asLinked()->previous());
 204     }
 205   } else {
 206     MOZ_ASSERT(!hasPrevious());
 207   }
 208 #endif
 209
 210   SharedChildrenPtr& childrenRef = treeDataRef().children;
 211
 212   if (childrenRef.isNone()) {
 213     childrenRef.setSingleChild(child);
 214     childMap->treeDataRef().setParent(this, child.index());
 215     return true;
 216   }
 217
 218   SharedChildrenHasher::Lookup lookup(id, prop, child.index());
 219
 220   if (hasChildrenSet()) {
 221     if (!childrenRef.toChildrenSet()->putNew(lookup, child)) {
 222       ReportOutOfMemory(cx);
 223       return false;
 224     }
 225   } else {
 226     auto hash = MakeUnique<SharedChildrenSet>();
 227     if (!hash || !hash->reserve(2)) {
 228       ReportOutOfMemory(cx);
 229       return false;
 230     }
 231     SharedPropMapAndIndex firstChild = childrenRef.toSingleChild();
 232     SharedPropMap* firstChildMap = firstChild.map();
 233     uint32_t firstChildIndex = indexOfNextProperty(firstChild.index());
 234     SharedChildrenHasher::Lookup lookupFirst(
 235         firstChildMap->getPropertyInfoWithKey(firstChildIndex),
 236         firstChild.index());
 237     hash->putNewInfallible(lookupFirst, firstChild);
 238     hash->putNewInfallible(lookup, child);
 239
 240     childrenRef.setChildrenSet(hash.release());
 241     setHasChildrenSet();
 242     AddCellMemory(this, sizeof(SharedChildrenSet), MemoryUse::PropMapChildren);
 243   }
 244
 245   childMap->treeDataRef().setParent(this, child.index());
 246   return true;
 247 }
 248
 249 // static
 250 bool SharedPropMap::addProperty(JSContext* cx, const JSClass* clasp,
 251                                 MutableHandle<SharedPropMap*> map,
 252                                 uint32_t* mapLength, HandleId id,
 253                                 PropertyFlags flags, ObjectFlags* objectFlags,
 254                                 uint32_t* slot) {
 255   MOZ_ASSERT(!flags.isCustomDataProperty());
 256
 257   *slot = SharedPropMap::slotSpan(clasp, map, *mapLength);
 258
 259   if (MOZ_UNLIKELY(*slot > SHAPE_MAXIMUM_SLOT)) {
 260     ReportAllocationOverflow(cx);
 261     return false;
 262   }
 263
 264   *objectFlags =
 265       GetObjectFlagsForNewProperty(clasp, *objectFlags, id, flags, cx);
 266
 267   PropertyInfo prop = PropertyInfo(flags, *slot);
 268   return addPropertyInternal(cx, map, mapLength, id, prop);
 269 }
 270
 271 // static
 272 bool SharedPropMap::addPropertyInReservedSlot(
 273     JSContext* cx, const JSClass* clasp, MutableHandle<SharedPropMap*> map,
 274     uint32_t* mapLength, HandleId id, PropertyFlags flags, uint32_t slot,
 275     ObjectFlags* objectFlags) {
 276   MOZ_ASSERT(!flags.isCustomDataProperty());
 277
 278   MOZ_ASSERT(slot < JSCLASS_RESERVED_SLOTS(clasp));
 279   MOZ_ASSERT_IF(map, map->lastUsedSlot(*mapLength) < slot);
 280
 281   *objectFlags =
 282       GetObjectFlagsForNewProperty(clasp, *objectFlags, id, flags, cx);
 283
 284   PropertyInfo prop = PropertyInfo(flags, slot);
 285   return addPropertyInternal(cx, map, mapLength, id, prop);
 286 }
 287
 288 // static
 289 bool SharedPropMap::addPropertyWithKnownSlot(JSContext* cx,
 290                                              const JSClass* clasp,
 291                                              MutableHandle<SharedPropMap*> map,
 292                                              uint32_t* mapLength, HandleId id,
 293                                              PropertyFlags flags, uint32_t slot,
 294                                              ObjectFlags* objectFlags) {
 295   MOZ_ASSERT(!flags.isCustomDataProperty());
 296
 297   if (MOZ_UNLIKELY(slot < JSCLASS_RESERVED_SLOTS(clasp))) {
 298     return addPropertyInReservedSlot(cx, clasp, map, mapLength, id, flags, slot,
 299                                      objectFlags);
 300   }
 301
 302   MOZ_ASSERT(slot == SharedPropMap::slotSpan(clasp, map, *mapLength));
 303   MOZ_RELEASE_ASSERT(slot <= SHAPE_MAXIMUM_SLOT);
 304
 305   *objectFlags =
 306       GetObjectFlagsForNewProperty(clasp, *objectFlags, id, flags, cx);
 307
 308   PropertyInfo prop = PropertyInfo(flags, slot);
 309   return addPropertyInternal(cx, map, mapLength, id, prop);
 310 }
 311
 312 // static
 313 bool SharedPropMap::addCustomDataProperty(JSContext* cx, const JSClass* clasp,
 314                                           MutableHandle<SharedPropMap*> map,
 315                                           uint32_t* mapLength, HandleId id,
 316                                           PropertyFlags flags,
 317                                           ObjectFlags* objectFlags) {
 318   MOZ_ASSERT(flags.isCustomDataProperty());
 319
 320   // Custom data properties don't have a slot. Copy the last property's slot
 321   // number to simplify the implementation of SharedPropMap::slotSpan.
 322   uint32_t slot = map ? map->lastUsedSlot(*mapLength) : SHAPE_INVALID_SLOT;
 323
 324   *objectFlags =
 325       GetObjectFlagsForNewProperty(clasp, *objectFlags, id, flags, cx);
 326
 327   PropertyInfo prop = PropertyInfo(flags, slot);
 328   return addPropertyInternal(cx, map, mapLength, id, prop);
 329 }
 330
 331 // static
 332 bool SharedPropMap::addPropertyInternal(JSContext* cx,
 333                                         MutableHandle<SharedPropMap*> map,
 334                                         uint32_t* mapLength, HandleId id,
 335                                         PropertyInfo prop) {
 336   if (!map) {
 337     // Adding the first property.
 338     MOZ_ASSERT(*mapLength == 0);
 339     map.set(SharedPropMap::createInitial(cx, id, prop));
 340     if (!map) {
 341       return false;
 342     }
 343     *mapLength = 1;
 344     return true;
 345   }
 346
 347   MOZ_ASSERT(*mapLength > 0);
 348
 349   if (*mapLength < PropMap::Capacity) {
 350     // Use the next map entry if possible.
 351     if (!map->hasKey(*mapLength)) {
 352       if (map->canHaveTable()) {
 353         JS::AutoCheckCannotGC nogc;
 354         if (PropMapTable* table = map->asLinked()->maybeTable(nogc)) {
 355           if (!table->add(cx, id, PropMapAndIndex(map, *mapLength))) {
 356             return false;
 357           }
 358         }
 359       }
 360       map->initProperty(*mapLength, id, prop);
 361       *mapLength += 1;
 362       return true;
 363     }
 364     if (map->matchProperty(*mapLength, id, prop)) {
 365       *mapLength += 1;
 366       return true;
 367     }
 368
 369     // The next entry can't be used so look up or create a child map. The child
 370     // map is a clone of this map up to mapLength, with the new property stored
 371     // as the next entry.
 372
 373     if (SharedPropMap* child = map->lookupChild(*mapLength, id, prop)) {
 374       map.set(child);
 375       *mapLength += 1;
 376       return true;
 377     }
 378
 379     SharedPropMap* child = SharedPropMap::clone(cx, map, *mapLength);
 380     if (!child) {
 381       return false;
 382     }
 383     child->initProperty(*mapLength, id, prop);
 384
 385     SharedPropMapAndIndex childEntry(child, *mapLength - 1);
 386     if (!map->addChild(cx, childEntry, id, prop)) {
 387       return false;
 388     }
 389
 390     map.set(child);
 391     *mapLength += 1;
 392     return true;
 393   }
 394
 395   // This map is full so look up or create a child map.
 396   MOZ_ASSERT(*mapLength == PropMap::Capacity);
 397
 398   if (SharedPropMap* child = map->lookupChild(*mapLength, id, prop)) {
 399     map.set(child);
 400     *mapLength = 1;
 401     return true;
 402   }
 403
 404   SharedPropMap* child = SharedPropMap::create(cx, map, id, prop);
 405   if (!child) {
 406     return false;
 407   }
 408
 409   SharedPropMapAndIndex childEntry(child, PropMap::Capacity - 1);
 410   if (!map->addChild(cx, childEntry, id, prop)) {
 411     return false;
 412   }
 413
 414   // As an optimization, pass the table to the new child map, unless adding the
 415   // property to it OOMs. Measurements indicate this gets rid of a large number
 416   // of PropMapTable allocations because we don't need to create a second table
 417   // when the parent map won't be used again as last map.
 418   if (map->canHaveTable()) {
 419     JS::AutoCheckCannotGC nogc;
 420     if (PropMapTable* table = map->asLinked()->maybeTable(nogc)) {
 421       // Trigger a pre-barrier on the parent map to appease the pre-barrier
 422       // verifier, because edges from the table are disappearing (even though
 423       // these edges are strictly redundant with the |previous| maps).
 424       gc::PreWriteBarrier(map.get());
 425       if (table->add(cx, id, PropMapAndIndex(child, 0))) {
 426         map->asLinked()->handOffTableTo(child->asLinked());
 427       } else {
 428         cx->recoverFromOutOfMemory();
 429       }
 430     }
 431   }
 432
 433   map.set(child);
 434   *mapLength = 1;
 435   return true;
 436 }
 437
 438 static PropertyFlags ComputeFlagsForSealOrFreeze(PropertyKey key,
 439                                                  PropertyFlags flags,
 440                                                  IntegrityLevel level) {
 441   // Private fields are not visible to SetIntegrityLevel.
 442   if (key.isSymbol() && key.toSymbol()->isPrivateName()) {
 443     return flags;
 444   }
 445
 446   // Make all properties non-configurable; if freezing, make data properties
 447   // read-only.
 448   flags.clearFlag(PropertyFlag::Configurable);
 449   if (level == IntegrityLevel::Frozen && flags.isDataDescriptor()) {
 450     flags.clearFlag(PropertyFlag::Writable);
 451   }
 452
 453   return flags;
 454 }
 455
 456 // static
 457 bool SharedPropMap::freezeOrSealProperties(JSContext* cx, IntegrityLevel level,
 458                                            const JSClass* clasp,
 459                                            MutableHandle<SharedPropMap*> map,
 460                                            uint32_t mapLength,
 461                                            ObjectFlags* objectFlags) {
 462   // Add all maps to a Vector so we can iterate over them in reverse order
 463   // (property definition order).
 464   JS::RootedVector<SharedPropMap*> maps(cx);
 465   {
 466     SharedPropMap* curMap = map;
 467     while (true) {
 468       if (!maps.append(curMap)) {
 469         return false;
 470       }
 471       if (!curMap->hasPrevious()) {
 472         break;
 473       }
 474       curMap = curMap->asNormal()->previous();
 475     }
 476   }
 477
 478   // Build a new SharedPropMap by adding each property with the changed
 479   // attributes.
 480   Rooted<SharedPropMap*> newMap(cx);
 481   uint32_t newMapLength = 0;
 482
 483   Rooted<PropertyKey> key(cx);
 484   Rooted<SharedPropMap*> curMap(cx);
 485
 486   for (size_t i = maps.length(); i > 0; i--) {
 487     curMap = maps[i - 1];
 488     uint32_t len = (i == 1) ? mapLength : PropMap::Capacity;
 489
 490     for (uint32_t j = 0; j < len; j++) {
 491       key = curMap->getKey(j);
 492       PropertyInfo prop = curMap->getPropertyInfo(j);
 493       PropertyFlags flags =
 494           ComputeFlagsForSealOrFreeze(key, prop.flags(), level);
 495
 496       if (prop.isCustomDataProperty()) {
 497         if (!addCustomDataProperty(cx, clasp, &newMap, &newMapLength, key,
 498                                    flags, objectFlags)) {
 499           return false;
 500         }
 501       } else {
 502         if (!addPropertyWithKnownSlot(cx, clasp, &newMap, &newMapLength, key,
 503                                       flags, prop.slot(), objectFlags)) {
 504           return false;
 505         }
 506       }
 507     }
 508   }
 509
 510   map.set(newMap);
 511   MOZ_ASSERT(newMapLength == mapLength);
 512   return true;
 513 }
 514
 515 void LinkedPropMap::handOffTableTo(LinkedPropMap* next) {
 516   MOZ_ASSERT(hasTable());
 517   MOZ_ASSERT(!next->hasTable());
 518
 519   next->data_.table = data_.table;
 520   data_.table = nullptr;
 521
 522   // Note: for tables currently only sizeof(PropMapTable) is tracked.
 523   RemoveCellMemory(this, sizeof(PropMapTable), MemoryUse::PropMapTable);
 524   AddCellMemory(next, sizeof(PropMapTable), MemoryUse::PropMapTable);
 525 }
 526
 527 void DictionaryPropMap::handOffLastMapStateTo(DictionaryPropMap* newLast) {
 528   // A dictionary object's last map contains the table, slot freeList, and
 529   // holeCount. These fields always have their initial values for non-last maps.
 530
 531   MOZ_ASSERT(this != newLast);
 532
 533   if (asLinked()->hasTable()) {
 534     asLinked()->handOffTableTo(newLast->asLinked());
 535   }
 536
 537   MOZ_ASSERT(newLast->freeList_ == SHAPE_INVALID_SLOT);
 538   newLast->freeList_ = freeList_;
 539   freeList_ = SHAPE_INVALID_SLOT;
 540
 541   MOZ_ASSERT(newLast->holeCount_ == 0);
 542   newLast->holeCount_ = holeCount_;
 543   holeCount_ = 0;
 544 }
 545
 546 // static
 547 bool DictionaryPropMap::addProperty(JSContext* cx, const JSClass* clasp,
 548                                     MutableHandle<DictionaryPropMap*> map,
 549                                     uint32_t* mapLength, HandleId id,
 550                                     PropertyFlags flags, uint32_t slot,
 551                                     ObjectFlags* objectFlags) {
 552   MOZ_ASSERT(map);
 553
 554   *objectFlags =
 555       GetObjectFlagsForNewProperty(clasp, *objectFlags, id, flags, cx);
 556   PropertyInfo prop = PropertyInfo(flags, slot);
 557
 558   if (*mapLength < PropMap::Capacity) {
 559     JS::AutoCheckCannotGC nogc;
 560     if (PropMapTable* table = map->asLinked()->maybeTable(nogc)) {
 561       if (!table->add(cx, id, PropMapAndIndex(map, *mapLength))) {
 562         return false;
 563       }
 564     }
 565     map->initProperty(*mapLength, id, prop);
 566     *mapLength += 1;
 567     return true;
 568   }
 569
 570   DictionaryPropMap* newMap = cx->newCell<DictionaryPropMap>(map, id, prop);
 571   if (!newMap) {
 572     return false;
 573   }
 574
 575   JS::AutoCheckCannotGC nogc;
 576   if (PropMapTable* table = map->asLinked()->maybeTable(nogc)) {
 577     if (!table->add(cx, id, PropMapAndIndex(newMap, 0))) {
 578       return false;
 579     }
 580   }
 581
 582   MOZ_ASSERT(newMap->previous() == map);
 583   map->handOffLastMapStateTo(newMap);
 584
 585   map.set(newMap);
 586   *mapLength = 1;
 587   return true;
 588 }
 589
 590 void DictionaryPropMap::changeProperty(JSContext* cx, const JSClass* clasp,
 591                                        uint32_t index, PropertyFlags flags,
 592                                        uint32_t slot,
 593                                        ObjectFlags* objectFlags) {
 594   MOZ_ASSERT(hasKey(index));
 595   *objectFlags = GetObjectFlagsForNewProperty(clasp, *objectFlags,
 596                                               getKey(index), flags, cx);
 597   linkedData_.propInfos[index] = PropertyInfo(flags, slot);
 598 }
 599
 600 void DictionaryPropMap::freezeOrSealProperties(JSContext* cx,
 601                                                IntegrityLevel level,
 602                                                const JSClass* clasp,
 603                                                uint32_t mapLength,
 604                                                ObjectFlags* objectFlags) {
 605   DictionaryPropMap* curMap = this;
 606   do {
 607     for (uint32_t i = 0; i < mapLength; i++) {
 608       if (!curMap->hasKey(i)) {
 609         continue;
 610       }
 611       PropertyKey key = curMap->getKey(i);
 612       PropertyFlags flags = curMap->getPropertyInfo(i).flags();
 613       flags = ComputeFlagsForSealOrFreeze(key, flags, level);
 614       curMap->changePropertyFlags(cx, clasp, i, flags, objectFlags);
 615     }
 616     curMap = curMap->previous();
 617     mapLength = PropMap::Capacity;
 618   } while (curMap);
 619 }
 620
 621 // static
 622 void DictionaryPropMap::skipTrailingHoles(MutableHandle<DictionaryPropMap*> map,
 623                                           uint32_t* mapLength) {
 624   // After removing a property, rewind map/mapLength so that the last property
 625   // is not a hole. This ensures accessing the last property of a map can always
 626   // be done without checking for holes.
 627
 628   while (true) {
 629     MOZ_ASSERT(*mapLength > 0);
 630     do {
 631       if (map->hasKey(*mapLength - 1)) {
 632         return;
 633       }
 634       map->decHoleCount();
 635       *mapLength -= 1;
 636     } while (*mapLength > 0);
 637
 638     if (!map->previous()) {
 639       // The dictionary map is empty, return the initial map with mapLength 0.
 640       MOZ_ASSERT(*mapLength == 0);
 641       MOZ_ASSERT(map->holeCount_ == 0);
 642       return;
 643     }
 644
 645     map->handOffLastMapStateTo(map->previous());
 646     map.set(map->previous());
 647     *mapLength = PropMap::Capacity;
 648   }
 649 }
 650
 651 // static
 652 void DictionaryPropMap::removeProperty(JSContext* cx,
 653                                        MutableHandle<DictionaryPropMap*> map,
 654                                        uint32_t* mapLength, PropMapTable* table,
 655                                        PropMapTable::Ptr& ptr) {
 656   MOZ_ASSERT(map);
 657   MOZ_ASSERT(*mapLength > 0);
 658
 659   JS::AutoCheckCannotGC nogc;
 660   MOZ_ASSERT(map->asLinked()->maybeTable(nogc) == table);
 661
 662   bool removingLast = (map == ptr->map() && *mapLength - 1 == ptr->index());
 663   ptr->map()->asDictionary()->clearProperty(ptr->index());
 664   map->incHoleCount();
 665   table->remove(ptr);
 666
 667   if (removingLast) {
 668     skipTrailingHoles(map, mapLength);
 669   }
 670   maybeCompact(cx, map, mapLength);
 671 }
 672
 673 // static
 674 void DictionaryPropMap::densifyElements(JSContext* cx,
 675                                         MutableHandle<DictionaryPropMap*> map,
 676                                         uint32_t* mapLength,
 677                                         NativeObject* obj) {
 678   MOZ_ASSERT(map);
 679   MOZ_ASSERT(*mapLength > 0);
 680
 681   JS::AutoCheckCannotGC nogc;
 682   PropMapTable* table = map->asLinked()->maybeTable(nogc);
 683
 684   DictionaryPropMap* currentMap = map;
 685   uint32_t currentLen = *mapLength;
 686   do {
 687     for (uint32_t i = 0; i < currentLen; i++) {
 688       PropertyKey key = currentMap->getKey(i);
 689       uint32_t index;
 690       if (!IdIsIndex(key, &index)) {
 691         continue;
 692       }
 693
 694       // The caller must have checked all sparse elements are plain data
 695       // properties.
 696       PropertyInfo prop = currentMap->getPropertyInfo(i);
 697       MOZ_ASSERT(prop.flags() == PropertyFlags::defaultDataPropFlags);
 698
 699       uint32_t slot = prop.slot();
 700       Value value = obj->getSlot(slot);
 701       obj->setDenseElement(index, value);
 702       obj->freeDictionarySlot(slot);
 703
 704       if (table) {
 705         PropMapTable::Ptr p = table->lookupRaw(key);
 706         MOZ_ASSERT(p);
 707         table->remove(p);
 708       }
 709
 710       currentMap->clearProperty(i);
 711       map->incHoleCount();
 712     }
 713     currentMap = currentMap->previous();
 714     currentLen = PropMap::Capacity;
 715   } while (currentMap);
 716
 717   skipTrailingHoles(map, mapLength);
 718   maybeCompact(cx, map, mapLength);
 719 }
 720
 721 void DictionaryPropMap::maybeCompact(JSContext* cx,
 722                                      MutableHandle<DictionaryPropMap*> map,
 723                                      uint32_t* mapLength) {
 724   // If there are no holes, there's nothing to compact.
 725   if (map->holeCount_ == 0) {
 726     return;
 727   }
 728
 729   JS::AutoCheckCannotGC nogc;
 730   PropMapTable* table = map->asLinked()->ensureTable(cx, nogc);
 731   if (!table) {
 732     // Compacting is optional so just return.
 733     cx->recoverFromOutOfMemory();
 734     return;
 735   }
 736
 737   // Heuristic: only compact if the number of holes >= the number of (non-hole)
 738   // entries.
 739   if (map->holeCount_ < table->entryCount()) {
 740     return;
 741   }
 742
 743   // Add all dictionary maps to a Vector so that we can iterate over them in
 744   // reverse order (property definition order). If appending to the Vector OOMs,
 745   // just return because compacting is optional.
 746   Vector<DictionaryPropMap*, 32, SystemAllocPolicy> maps;
 747   for (DictionaryPropMap* curMap = map; curMap; curMap = curMap->previous()) {
 748     if (!maps.append(curMap)) {
 749       return;
 750     }
 751   }
 752
 753   // Use two cursors: readMapCursor/readIndexCursor iterates over all properties
 754   // starting at the first one, to search for the next non-hole entry.
 755   // writeMapCursor/writeIndexCursor is used to write all non-hole keys.
 756   //
 757   // At the start of the loop, these cursors point to the next property slot to
 758   // read/write.
 759
 760   size_t readMapCursorVectorIndex = maps.length() - 1;
 761   DictionaryPropMap* readMapCursor = maps[readMapCursorVectorIndex];
 762   uint32_t readIndexCursor = 0;
 763
 764   size_t writeMapCursorVectorIndex = readMapCursorVectorIndex;
 765   DictionaryPropMap* writeMapCursor = readMapCursor;
 766   uint32_t writeIndexCursor = 0;
 767
 768   mozilla::DebugOnly<uint32_t> numHoles = 0;
 769
 770   while (true) {
 771     if (readMapCursor->hasKey(readIndexCursor)) {
 772       // Found a non-hole entry, copy it to its new position and update the
 773       // PropMapTable to point to this new entry. Only do this if the read and
 774       // write positions are different from each other.
 775       if (readMapCursor != writeMapCursor ||
 776           readIndexCursor != writeIndexCursor) {
 777         PropertyKey key = readMapCursor->getKey(readIndexCursor);
 778         auto p = table->lookupRaw(key);
 779         MOZ_ASSERT(p);
 780         MOZ_ASSERT(p->map() == readMapCursor);
 781         MOZ_ASSERT(p->index() == readIndexCursor);
 782
 783         writeMapCursor->setKey(writeIndexCursor, key);
 784         writeMapCursor->linkedData_.propInfos[writeIndexCursor] =
 785             readMapCursor->linkedData_.propInfos[readIndexCursor];
 786
 787         PropMapAndIndex newEntry(writeMapCursor, writeIndexCursor);
 788         table->replaceEntry(p, key, newEntry);
 789       }
 790       // Advance the write cursor.
 791       writeIndexCursor++;
 792       if (writeIndexCursor == PropMap::Capacity) {
 793         MOZ_ASSERT(writeMapCursorVectorIndex > 0);
 794         writeMapCursorVectorIndex--;
 795         writeMapCursor = maps[writeMapCursorVectorIndex];
 796         writeIndexCursor = 0;
 797       }
 798     } else {
 799       numHoles++;
 800     }
 801     // Advance the read cursor. If there are no more maps to read from, we're
 802     // done.
 803     readIndexCursor++;
 804     if (readIndexCursor == PropMap::Capacity) {
 805       if (readMapCursorVectorIndex == 0) {
 806         break;
 807       }
 808       readMapCursorVectorIndex--;
 809       readMapCursor = maps[readMapCursorVectorIndex];
 810       readIndexCursor = 0;
 811     }
 812   }
 813
 814   // Sanity check: the read cursor skipped holes between properties and holes
 815   // at the end of the last map (these are not included in holeCount_).
 816   MOZ_ASSERT(map->holeCount_ + (PropMap::Capacity - *mapLength) == numHoles);
 817
 818   // The write cursor points to the next available slot. If this is at the start
 819   // of a new map, use the previous map (which must be full) instead.
 820   if (writeIndexCursor == 0 && writeMapCursor->previous()) {
 821     writeMapCursor = writeMapCursor->previous();
 822     *mapLength = PropMap::Capacity;
 823   } else {
 824     *mapLength = writeIndexCursor;
 825   }
 826
 827   // Ensure the last map does not have any keys in [mapLength, Capacity).
 828   for (uint32_t i = *mapLength; i < PropMap::Capacity; i++) {
 829     writeMapCursor->clearProperty(i);
 830   }
 831
 832   if (writeMapCursor != map) {
 833     map->handOffLastMapStateTo(writeMapCursor);
 834     map.set(writeMapCursor);
 835   }
 836   map->holeCount_ = 0;
 837
 838   MOZ_ASSERT(*mapLength <= PropMap::Capacity);
 839   MOZ_ASSERT_IF(*mapLength == 0, !map->previous());
 840   MOZ_ASSERT_IF(!map->previous(), table->entryCount() == *mapLength);
 841 }
 842
 843 void SharedPropMap::fixupAfterMovingGC() {
 844   SharedChildrenPtr& childrenRef = treeDataRef().children;
 845   if (childrenRef.isNone()) {
 846     return;
 847   }
 848
 849   if (!hasChildrenSet()) {
 850     SharedPropMapAndIndex child = childrenRef.toSingleChild();
 851     if (gc::IsForwarded(child.map())) {
 852       child = SharedPropMapAndIndex(gc::Forwarded(child.map()), child.index());
 853       childrenRef.setSingleChild(child);
 854     }
 855     return;
 856   }
 857
 858   SharedChildrenSet* set = childrenRef.toChildrenSet();
 859   for (SharedChildrenSet::Enum e(*set); !e.empty(); e.popFront()) {
 860     SharedPropMapAndIndex child = e.front();
 861     if (IsForwarded(child.map())) {
 862       child = SharedPropMapAndIndex(Forwarded(child.map()), child.index());
 863       e.mutableFront() = child;
 864     }
 865   }
 866 }
 867
 868 void SharedPropMap::removeChild(JS::GCContext* gcx, SharedPropMap* child) {
 869   SharedPropMapAndIndex& parentRef = child->treeDataRef().parent;
 870   MOZ_ASSERT(parentRef.map() == this);
 871
 872   uint32_t index = parentRef.index();
 873   parentRef.setNone();
 874
 875   SharedChildrenPtr& childrenRef = treeDataRef().children;
 876   MOZ_ASSERT(!childrenRef.isNone());
 877
 878   if (!hasChildrenSet()) {
 879     MOZ_ASSERT(childrenRef.toSingleChild().map() == child);
 880     MOZ_ASSERT(childrenRef.toSingleChild().index() == index);
 881     childrenRef.setNone();
 882     return;
 883   }
 884
 885   SharedChildrenSet* set = childrenRef.toChildrenSet();
 886   {
 887     uint32_t nextIndex = SharedPropMap::indexOfNextProperty(index);
 888     SharedChildrenHasher::Lookup lookup(
 889         child->getPropertyInfoWithKey(nextIndex), index);
 890     auto p = set->lookup(lookup);
 891     MOZ_ASSERT(p, "Child must be in children set");
 892     set->remove(p);
 893   }
 894
 895   MOZ_ASSERT(set->count() >= 1);
 896
 897   if (set->count() == 1) {
 898     // Convert from set form back to single child form.
 899     SharedChildrenSet::Range r = set->all();
 900     SharedPropMapAndIndex remainingChild = r.front();
 901     childrenRef.setSingleChild(remainingChild);
 902     clearHasChildrenSet();
 903     gcx->delete_(this, set, MemoryUse::PropMapChildren);
 904   }
 905 }
 906
 907 void LinkedPropMap::purgeTable(JS::GCContext* gcx) {
 908   MOZ_ASSERT(hasTable());
 909   gcx->delete_(this, data_.table, MemoryUse::PropMapTable);
 910   data_.table = nullptr;
 911 }
 912
 913 uint32_t PropMap::approximateEntryCount() const {
 914   // Returns a number that's guaranteed to tbe >= the exact number of properties
 915   // in this map (including previous maps). This is used to reserve space in the
 916   // HashSet when allocating a table for this map.
 917
 918   const PropMap* map = this;
 919   uint32_t count = 0;
 920   JS::AutoCheckCannotGC nogc;
 921   while (true) {
 922     if (!map->hasPrevious()) {
 923       return count + PropMap::Capacity;
 924     }
 925     if (PropMapTable* table = map->asLinked()->maybeTable(nogc)) {
 926       return count + table->entryCount();
 927     }
 928     count += PropMap::Capacity;
 929     map = map->asLinked()->previous();
 930   }
 931 }
 932
 933 bool PropMapTable::init(JSContext* cx, LinkedPropMap* map) {
 934   if (!set_.reserve(map->approximateEntryCount())) {
 935     ReportOutOfMemory(cx);
 936     return false;
 937   }
 938
 939   PropMap* curMap = map;
 940   while (true) {
 941     for (uint32_t i = 0; i < PropMap::Capacity; i++) {
 942       if (curMap->hasKey(i)) {
 943         PropertyKey key = curMap->getKey(i);
 944         set_.putNewInfallible(key, PropMapAndIndex(curMap, i));
 945       }
 946     }
 947     if (!curMap->hasPrevious()) {
 948       break;
 949     }
 950     curMap = curMap->asLinked()->previous();
 951   }
 952
 953   return true;
 954 }
 955
 956 void PropMapTable::trace(JSTracer* trc) {
 957   purgeCache();
 958
 959   for (Set::Enum e(set_); !e.empty(); e.popFront()) {
 960     PropMap* map = e.front().map();
 961     TraceManuallyBarrieredEdge(trc, &map, "PropMapTable map");
 962     if (map != e.front().map()) {
 963       e.mutableFront() = PropMapAndIndex(map, e.front().index());
 964     }
 965   }
 966 }
 967
 968 #ifdef JSGC_HASH_TABLE_CHECKS
 969 void PropMapTable::checkAfterMovingGC() {
 970   for (Set::Enum e(set_); !e.empty(); e.popFront()) {
 971     PropMap* map = e.front().map();
 972     MOZ_ASSERT(map);
 973     CheckGCThingAfterMovingGC(map);
 974
 975     PropertyKey key = map->getKey(e.front().index());
 976     MOZ_RELEASE_ASSERT(!key.isVoid());
 977
 978     auto p = lookupRaw(key);
 979     MOZ_RELEASE_ASSERT(p.found() && *p == e.front());
 980   }
 981 }
 982 #endif
 983
 984 #ifdef DEBUG
 985 bool LinkedPropMap::canSkipMarkingTable() {
 986   if (!hasTable()) {
 987     return true;
 988   }
 989
 990   PropMapTable* table = data_.table;
 991   uint32_t count = 0;
 992
 993   PropMap* map = this;
 994   while (true) {
 995     for (uint32_t i = 0; i < Capacity; i++) {
 996       if (map->hasKey(i)) {
 997         PropertyKey key = map->getKey(i);
 998         PropMapTable::Ptr p = table->readonlyThreadsafeLookup(key);
 999         MOZ_ASSERT(*p == PropMapAndIndex(map, i));
1000         count++;
1001       }
1002     }
1003     if (!map->hasPrevious()) {
1004       break;
1005     }
1006     map = map->asLinked()->previous();
1007   }
1008
1009   return count == table->entryCount();
1010 }
1011 #endif
1012
1013 bool LinkedPropMap::createTable(JSContext* cx) {
1014   MOZ_ASSERT(canHaveTable());
1015   MOZ_ASSERT(!hasTable());
1016
1017   UniquePtr<PropMapTable> table = cx->make_unique<PropMapTable>();
1018   if (!table) {
1019     return false;
1020   }
1021
1022   if (!table->init(cx, this)) {
1023     return false;
1024   }
1025
1026   data_.table = table.release();
1027   // TODO: The contents of PropMapTable is not currently tracked, only the
1028   // object itself.
1029   AddCellMemory(this, sizeof(PropMapTable), MemoryUse::PropMapTable);
1030   return true;
1031 }
1032
1033 #if defined(DEBUG) || defined(JS_JITSPEW)
1034 void PropMap::dump() const {
1035   Fprinter out(stderr);
1036   dump(out);
1037 }
1038
1039 void PropMap::dump(js::GenericPrinter& out) const {
1040   js::JSONPrinter json(out);
1041   dump(json);
1042   out.put("\n");
1043 }
1044
1045 void PropMap::dump(js::JSONPrinter& json) const {
1046   json.beginObject();
1047   dumpFields(json);
1048   json.endObject();
1049 }
1050
1051 template <typename KnownF, typename UnknownF>
1052 void ForEachPropertyFlag(PropertyFlags flags, KnownF known, UnknownF unknown) {
1053   uint8_t raw = flags.toRaw();
1054   for (uint8_t i = 1; i; i = i << 1) {
1055     if (!(raw & i)) {
1056       continue;
1057     }
1058     switch (PropertyFlag(raw & i)) {
1059       case PropertyFlag::Configurable:
1060         known("Configurable");
1061         break;
1062       case PropertyFlag::Enumerable:
1063         known("Enumerable");
1064         break;
1065       case PropertyFlag::Writable:
1066         known("Writable");
1067         break;
1068       case PropertyFlag::AccessorProperty:
1069         known("AccessorProperty");
1070         break;
1071       case PropertyFlag::CustomDataProperty:
1072         known("UseWatchtowerTestingCallback");
1073         break;
1074       default:
1075         unknown(i);
1076         break;
1077     }
1078   }
1079 }
1080
1081 template <typename KnownF, typename UnknownF>
1082 /* static */
1083 void PropMap::forEachPropMapFlag(uintptr_t flags, KnownF known,
1084                                  UnknownF unknown) {
1085   for (uintptr_t i = 1 << gc::CellFlagBitsReservedForGC;
1086        i < 1 << PropMap::NumPreviousMapsShift; i = i << 1) {
1087     if (!(flags & i)) {
1088       continue;
1089     }
1090     switch (flags & i) {
1091       case PropMap::Flags::IsCompactFlag:
1092         known("IsCompactFlag");
1093         break;
1094       case PropMap::Flags::HasPrevFlag:
1095         known("HasPrevFlag");
1096         break;
1097       case PropMap::Flags::IsDictionaryFlag:
1098         known("IsDictionaryFlag");
1099         break;
1100       case PropMap::Flags::CanHaveTableFlag:
1101         known("CanHaveTableFlag");
1102         break;
1103       case PropMap::Flags::HasChildrenSetFlag:
1104         known("HasChildrenSetFlag");
1105         break;
1106       case PropMap::Flags::HadDictionaryConversionFlag:
1107         known("HadDictionaryConversionFlag");
1108         break;
1109       default:
1110         unknown(i);
1111         break;
1112     }
1113   }
1114 }
1115
1116 const char* PropMapTypeToString(const js::PropMap* map) {
1117   if (map->isLinked()) {
1118     return "js::LinkedPropMap";
1119   }
1120
1121   if (map->isShared()) {
1122     if (map->isCompact()) {
1123       return "js::CompactPropMap";
1124     }
1125     return "js::NormalPropMap";
1126   }
1127
1128   return "js::DictionaryPropMap";
1129 }
1130
1131 void PropMap::dumpFields(js::JSONPrinter& json) const {
1132   json.formatProperty("address", "(%s*)0x%p", PropMapTypeToString(this), this);
1133
1134   json.beginInlineListProperty("flags");
1135   forEachPropMapFlag(
1136       flags(), [&](const char* name) { json.value("%s", name); },
1137       [&](uint32_t value) { json.value("Unknown(%08x)", value); });
1138   json.endInlineList();
1139
1140   if (isLinked()) {
1141     asLinked()->dumpOwnFields(json);
1142   } else if (isShared()) {
1143     asShared()->dumpOwnFields(json);
1144   } else {
1145     asDictionary()->dumpOwnFields(json);
1146   }
1147
1148   json.beginObjectProperty("properties");
1149   for (uint32_t i = 0; i < Capacity; i++) {
1150     char name[64];
1151     SprintfLiteral(name, "%u", i);
1152
1153     if (!hasKey(i)) {
1154       json.nullProperty(name);
1155       return;
1156     }
1157
1158     json.beginObjectProperty(name);
1159     dumpFieldsAt(json, i);
1160     json.endObject();
1161   }
1162   json.endObject();
1163 }
1164
1165 void LinkedPropMap::dumpOwnFields(js::JSONPrinter& json) const {
1166   if (hasPrevious()) {
1167     json.formatProperty("previous", "(%s*)0x%p",
1168                         PropMapTypeToString(previous()), previous());
1169   }
1170
1171   if (canHaveTable()) {
1172     json.formatProperty("table", "(js::PropMapTable*)0x%p", data_.table);
1173   }
1174 }
1175
1176 void SharedPropMap::dumpOwnFields(js::JSONPrinter& json) const {
1177   SharedPropMapAndIndex parent = treeDataRef().parent;
1178   if (parent.isNone()) {
1179     json.nullProperty("parent");
1180   } else {
1181     json.formatProperty("parent", "(%s*)0x%p [%u]",
1182                         PropMapTypeToString(parent.map()), parent.map(),
1183                         parent.index());
1184   }
1185 }
1186
1187 void DictionaryPropMap::dumpOwnFields(js::JSONPrinter& json) const {
1188   json.property("freeList", freeList_);
1189   json.property("holeCount", holeCount_);
1190 }
1191
1192 void PropMap::dumpFieldsAt(js::JSONPrinter& json, uint32_t index) const {
1193   PropertyKey key = getKey(index);
1194   js::GenericPrinter& out = json.beginStringProperty("key");
1195   key.dumpStringContent(out);
1196   json.endStringProperty();
1197
1198   PropertyInfo prop = getPropertyInfo(index);
1199   json.beginInlineListProperty("flags");
1200   ForEachPropertyFlag(
1201       prop.flags(), [&](const char* name) { json.value("%s", name); },
1202       [&](uint8_t value) { json.value("Unknown(%02x)", value); });
1203   json.endInlineList();
1204
1205   if (prop.hasSlot()) {
1206     json.property("slot", prop.slot());
1207   }
1208 }
1209
1210 void PropMap::dumpDescriptorStringContentAt(js::GenericPrinter& out,
1211                                             uint32_t index) const {
1212   PropertyInfo prop = getPropertyInfo(index);
1213
1214   out.printf("map=(%s*)0x%p, index=%u", PropMapTypeToString(this), this, index);
1215
1216   if (prop.enumerable()) {
1217     out.put(", enumerable");
1218   }
1219   if (prop.configurable()) {
1220     out.put(", configurable");
1221   }
1222   if (prop.isDataDescriptor() && prop.writable()) {
1223     out.put(", writable");
1224   }
1225
1226   if (prop.isCustomDataProperty()) {
1227     out.printf(", <custom-data-prop>");
1228   }
1229
1230   if (prop.hasSlot()) {
1231     out.printf(", slot=%u", prop.slot());
1232   }
1233 }
1234
1235 JS::UniqueChars PropMap::getPropertyNameAt(uint32_t index) const {
1236   Sprinter sp;
1237   if (!sp.init()) {
1238     return nullptr;
1239   }
1240
1241   PropertyKey key = getKey(index);
1242   key.dumpPropertyName(sp);
1243
1244   return sp.release();
1245 }
1246 #endif  // defined(DEBUG) || defined(JS_JITSPEW)
1247
1248 #ifdef DEBUG
1249 void PropMap::checkConsistency(NativeObject* obj) const {
1250   const uint32_t mapLength = obj->shape()->propMapLength();
1251   MOZ_ASSERT(mapLength <= PropMap::Capacity);
1252
1253   JS::AutoCheckCannotGC nogc;
1254   if (isDictionary()) {
1255     // Check dictionary slot free list.
1256     for (uint32_t fslot = asDictionary()->freeList();
1257          fslot != SHAPE_INVALID_SLOT;
1258          fslot = obj->getSlot(fslot).toPrivateUint32()) {
1259       MOZ_ASSERT(fslot < obj->slotSpan());
1260     }
1261
1262     auto* table = asLinked()->maybeTable(nogc);
1263     const DictionaryPropMap* curMap = asDictionary();
1264     uint32_t numHoles = 0;
1265     do {
1266       // Some fields must only be set for the last dictionary map.
1267       if (curMap != this) {
1268         MOZ_ASSERT(!curMap->asLinked()->hasTable());
1269         MOZ_ASSERT(curMap->holeCount_ == 0);
1270         MOZ_ASSERT(curMap->freeList_ == SHAPE_INVALID_SLOT);
1271       }
1272
1273       for (uint32_t i = 0; i < PropMap::Capacity; i++) {
1274         if (!curMap->hasKey(i)) {
1275           if (curMap != this || i < mapLength) {
1276             numHoles++;
1277           }
1278           continue;
1279         }
1280
1281         // The last dictionary map must only have keys up to mapLength.
1282         MOZ_ASSERT_IF(curMap == this, i < mapLength);
1283
1284         PropertyInfo prop = curMap->getPropertyInfo(i);
1285         MOZ_ASSERT_IF(prop.hasSlot(), prop.slot() < obj->slotSpan());
1286
1287         // All properties must be in the table.
1288         if (table) {
1289           PropertyKey key = curMap->getKey(i);
1290           auto p = table->lookupRaw(key);
1291           MOZ_ASSERT(p->map() == curMap);
1292           MOZ_ASSERT(p->index() == i);
1293         }
1294       }
1295       curMap = curMap->previous();
1296     } while (curMap);
1297
1298     MOZ_ASSERT(asDictionary()->holeCount_ == numHoles);
1299     return;
1300   }
1301
1302   MOZ_ASSERT(mapLength > 0);
1303
1304   const SharedPropMap* curMap = asShared();
1305   auto* table =
1306       curMap->canHaveTable() ? curMap->asLinked()->maybeTable(nogc) : nullptr;
1307
1308   // Shared maps without a previous map never have a table.
1309   MOZ_ASSERT_IF(!curMap->hasPrevious(), !curMap->canHaveTable());
1310
1311   const SharedPropMap* nextMap = nullptr;
1312   mozilla::Maybe<uint32_t> nextSlot;
1313   while (true) {
1314     // Verify numPreviousMaps is set correctly.
1315     MOZ_ASSERT_IF(nextMap && nextMap->numPreviousMaps() != NumPreviousMapsMax,
1316                   curMap->numPreviousMaps() + 1 == nextMap->numPreviousMaps());
1317     MOZ_ASSERT(curMap->hasPrevious() == (curMap->numPreviousMaps() > 0));
1318
1319     // If a previous map also has a table, it must have fewer entries than the
1320     // last map's table.
1321     if (table && curMap != this && curMap->canHaveTable()) {
1322       if (auto* table2 = curMap->asLinked()->maybeTable(nogc)) {
1323         MOZ_ASSERT(table2->entryCount() < table->entryCount());
1324       }
1325     }
1326
1327     for (int32_t i = PropMap::Capacity - 1; i >= 0; i--) {
1328       uint32_t index = uint32_t(i);
1329
1330       // Only the last map can have holes, for entries following mapLength.
1331       if (!curMap->hasKey(index)) {
1332         MOZ_ASSERT(index > 0);
1333         MOZ_ASSERT(curMap == this);
1334         MOZ_ASSERT(index >= mapLength);
1335         continue;
1336       }
1337
1338       // Check slot numbers are within slot span and never decreasing.
1339       PropertyInfo prop = curMap->getPropertyInfo(i);
1340       if (prop.hasSlot()) {
1341         MOZ_ASSERT_IF((curMap != this || index < mapLength),
1342                       prop.slot() < obj->slotSpan());
1343         MOZ_ASSERT_IF(nextSlot.isSome(), *nextSlot >= prop.slot());
1344         nextSlot = mozilla::Some(prop.slot());
1345       }
1346
1347       // All properties must be in the table.
1348       if (table) {
1349         PropertyKey key = curMap->getKey(index);
1350         auto p = table->lookupRaw(key);
1351         MOZ_ASSERT(p->map() == curMap);
1352         MOZ_ASSERT(p->index() == index);
1353       }
1354     }
1355
1356     if (!curMap->hasPrevious()) {
1357       break;
1358     }
1359     nextMap = curMap;
1360     curMap = curMap->asLinked()->previous()->asShared();
1361   }
1362 }
1363 #endif  // DEBUG
1364
1365 JS::ubi::Node::Size JS::ubi::Concrete<PropMap>::size(
1366     mozilla::MallocSizeOf mallocSizeOf) const {
1367   Size size = js::gc::Arena::thingSize(get().asTenured().getAllocKind());
1368   size_t children = 0;
1369   size_t tables = 0;
1370   get().addSizeOfExcludingThis(mallocSizeOf, &children, &tables);
1371   return size + children + tables;
1372 }