[ tor-browser ].git.dasho

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