1  /*
   2   * Copyright (C) 2008-2019 Apple Inc. All rights reserved.
   3   * Copyright (C) 2020 Alexey Shvayka <shvaikalesh@gmail.com>.
   4   *
   5   * Redistribution and use in source and binary forms, with or without
   6   * modification, are permitted provided that the following conditions
   7   * are met:
   8   * 1. Redistributions of source code must retain the above copyright
   9   *    notice, this list of conditions and the following disclaimer.
  10   * 2. Redistributions in binary form must reproduce the above copyright
  11   *    notice, this list of conditions and the following disclaimer in the
  12   *    documentation and/or other materials provided with the distribution.
  13   *
  14   * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  15   * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17   * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  18   * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  19   * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  20   * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  21   * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  22   * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  24   * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
  25   */
  26  
  27  #include "config.h"
  28  #include "Structure.h"
  29  
  30  #include "BuiltinNames.h"
  31  #include "DumpContext.h"
  32  #include "JSCInlines.h"
  33  #include "PropertyMapHashTable.h"
  34  #include "PropertyNameArray.h"
  35  #include <wtf/CommaPrinter.h>
  36  #include <wtf/NeverDestroyed.h>
  37  #include <wtf/RefPtr.h>
  38  
  39  #define DUMP_STRUCTURE_ID_STATISTICS 0
  40  
  41  namespace JSC {
  42  
  43  #if DUMP_STRUCTURE_ID_STATISTICS
  44  static HashSet<Structure*>& liveStructureSet = *(new HashSet<Structure*>);
  45  #endif
  46  
  47  class SingleSlotTransitionWeakOwner final : public WeakHandleOwner {
  48      void finalize(Handle<Unknown>, void* context) final
  49      {
  50          StructureTransitionTable* table = reinterpret_cast<StructureTransitionTable*>(context);
  51          ASSERT(table->isUsingSingleSlot());
  52          WeakSet::deallocate(table->weakImpl());
  53          table->m_data = StructureTransitionTable::UsingSingleSlotFlag;
  54      }
  55  };
  56  
  57  static SingleSlotTransitionWeakOwner& singleSlotTransitionWeakOwner()
  58  {
  59      static NeverDestroyed<SingleSlotTransitionWeakOwner> owner;
  60      return owner;
  61  }
  62  
  63  inline Structure* StructureTransitionTable::singleTransition() const
  64  {
  65      ASSERT(isUsingSingleSlot());
  66      if (WeakImpl* impl = this->weakImpl()) {
  67          if (impl->state() == WeakImpl::Live)
  68              return jsCast<Structure*>(impl->jsValue().asCell());
  69      }
  70      return nullptr;
  71  }
  72  
  73  inline void StructureTransitionTable::setSingleTransition(Structure* structure)
  74  {
  75      ASSERT(isUsingSingleSlot());
  76      if (WeakImpl* impl = this->weakImpl())
  77          WeakSet::deallocate(impl);
  78      WeakImpl* impl = WeakSet::allocate(structure, &singleSlotTransitionWeakOwner(), this);
  79      m_data = bitwise_cast<intptr_t>(impl) | UsingSingleSlotFlag;
  80  }
  81  
  82  bool StructureTransitionTable::contains(UniquedStringImpl* rep, unsigned attributes, TransitionKind transitionKind) const
  83  {
  84      if (isUsingSingleSlot()) {
  85          Structure* transition = singleTransition();
  86          return transition && transition->m_transitionPropertyName == rep && transition->transitionPropertyAttributes() == attributes && transition->transitionKind() == transitionKind;
  87      }
  88      return map()->get(StructureTransitionTable::Hash::Key(rep, attributes, transitionKind));
  89  }
  90  
  91  inline Structure* StructureTransitionTable::get(UniquedStringImpl* rep, unsigned attributes, TransitionKind transitionKind) const
  92  {
  93      if (isUsingSingleSlot()) {
  94          Structure* transition = singleTransition();
  95          return (transition && transition->m_transitionPropertyName == rep && transition->transitionPropertyAttributes() == attributes && transition->transitionKind() == transitionKind) ? transition : nullptr;
  96      }
  97      return map()->get(StructureTransitionTable::Hash::Key(rep, attributes, transitionKind));
  98  }
  99  
 100  void StructureTransitionTable::add(VM& vm, Structure* structure)
 101  {
 102      if (isUsingSingleSlot()) {
 103          Structure* existingTransition = singleTransition();
 104  
 105          // This handles the first transition being added.
 106          if (!existingTransition) {
 107              setSingleTransition(structure);
 108              return;
 109          }
 110  
 111          // This handles the second transition being added
 112          // (or the first transition being despecified!)
 113          setMap(new TransitionMap(vm));
 114          add(vm, existingTransition);
 115      }
 116  
 117      // Add the structure to the map.
 118      map()->set(StructureTransitionTable::Hash::Key(structure->m_transitionPropertyName.get(), structure->transitionPropertyAttributes(), structure->transitionKind()), structure);
 119  }
 120  
 121  void Structure::dumpStatistics()
 122  {
 123  #if DUMP_STRUCTURE_ID_STATISTICS
 124      unsigned numberLeaf = 0;
 125      unsigned numberUsingSingleSlot = 0;
 126      unsigned numberSingletons = 0;
 127      unsigned numberWithPropertyMaps = 0;
 128      unsigned totalPropertyMapsSize = 0;
 129  
 130      HashSet<Structure*>::const_iterator end = liveStructureSet.end();
 131      for (HashSet<Structure*>::const_iterator it = liveStructureSet.begin(); it != end; ++it) {
 132          Structure* structure = *it;
 133  
 134          switch (structure->m_transitionTable.size()) {
 135              case 0:
 136                  ++numberLeaf;
 137                  if (!structure->previousID())
 138                      ++numberSingletons;
 139                  break;
 140  
 141              case 1:
 142                  ++numberUsingSingleSlot;
 143                  break;
 144          }
 145  
 146          if (PropertyTable* table = structure->propertyTableOrNull()) {
 147              ++numberWithPropertyMaps;
 148              totalPropertyMapsSize += table->sizeInMemory();
 149          }
 150      }
 151  
 152      dataLogF("Number of live Structures: %d\n", liveStructureSet.size());
 153      dataLogF("Number of Structures using the single item optimization for transition map: %d\n", numberUsingSingleSlot);
 154      dataLogF("Number of Structures that are leaf nodes: %d\n", numberLeaf);
 155      dataLogF("Number of Structures that singletons: %d\n", numberSingletons);
 156      dataLogF("Number of Structures with PropertyMaps: %d\n", numberWithPropertyMaps);
 157  
 158      dataLogF("Size of a single Structures: %d\n", static_cast<unsigned>(sizeof(Structure)));
 159      dataLogF("Size of sum of all property maps: %d\n", totalPropertyMapsSize);
 160      dataLogF("Size of average of all property maps: %f\n", static_cast<double>(totalPropertyMapsSize) / static_cast<double>(liveStructureSet.size()));
 161  #else
 162      dataLogF("Dumping Structure statistics is not enabled.\n");
 163  #endif
 164  }
 165  
 166  #if ASSERT_ENABLED
 167  void Structure::validateFlags()
 168  {
 169      const MethodTable& methodTable = m_classInfo->methodTable;
 170  
 171      bool overridesGetCallData = methodTable.getCallData != JSCell::getCallData;
 172      RELEASE_ASSERT(overridesGetCallData == typeInfo().overridesGetCallData());
 173  
 174      bool overridesGetOwnPropertySlot =
 175          methodTable.getOwnPropertySlot != JSObject::getOwnPropertySlot
 176          && methodTable.getOwnPropertySlot != JSCell::getOwnPropertySlot;
 177      // We can strengthen this into an equivalence test if there are no classes
 178      // that specifies this flag without overriding getOwnPropertySlot.
 179      // FIXME: https://bugs.webkit.org/show_bug.cgi?id=212956
 180      if (overridesGetOwnPropertySlot)
 181          RELEASE_ASSERT(typeInfo().overridesGetOwnPropertySlot());
 182  
 183      bool overridesGetOwnPropertySlotByIndex =
 184          methodTable.getOwnPropertySlotByIndex != JSObject::getOwnPropertySlotByIndex
 185          && methodTable.getOwnPropertySlotByIndex != JSCell::getOwnPropertySlotByIndex;
 186      // We can strengthen this into an equivalence test if there are no classes
 187      // that specifies this flag without overriding getOwnPropertySlotByIndex.
 188      // FIXME: https://bugs.webkit.org/show_bug.cgi?id=212958
 189      if (overridesGetOwnPropertySlotByIndex)
 190          RELEASE_ASSERT(typeInfo().interceptsGetOwnPropertySlotByIndexEvenWhenLengthIsNotZero());
 191  
 192      bool overridesPutPropertySecurityCheck =
 193          methodTable.doPutPropertySecurityCheck != JSObject::doPutPropertySecurityCheck
 194          && methodTable.doPutPropertySecurityCheck != JSCell::doPutPropertySecurityCheck;
 195      RELEASE_ASSERT(overridesPutPropertySecurityCheck == typeInfo().hasPutPropertySecurityCheck());
 196  
 197      bool overridesGetOwnPropertyNames =
 198          methodTable.getOwnPropertyNames != JSObject::getOwnPropertyNames
 199          && methodTable.getOwnPropertyNames != JSCell::getOwnPropertyNames;
 200      RELEASE_ASSERT(overridesGetOwnPropertyNames == typeInfo().overridesGetOwnPropertyNames());
 201  
 202      bool overridesGetOwnSpecialPropertyNames =
 203          methodTable.getOwnSpecialPropertyNames != JSObject::getOwnSpecialPropertyNames
 204          && methodTable.getOwnSpecialPropertyNames != JSCell::getOwnSpecialPropertyNames;
 205      RELEASE_ASSERT(overridesGetOwnSpecialPropertyNames == typeInfo().overridesGetOwnSpecialPropertyNames());
 206  
 207      bool overridesGetPrototype =
 208          methodTable.getPrototype != static_cast<MethodTable::GetPrototypeFunctionPtr>(JSObject::getPrototype)
 209          && methodTable.getPrototype != JSCell::getPrototype;
 210      RELEASE_ASSERT(overridesGetPrototype == typeInfo().overridesGetPrototype());
 211  }
 212  #else
 213  inline void Structure::validateFlags() { }
 214  #endif
 215  
 216  Structure::Structure(VM& vm, JSGlobalObject* globalObject, JSValue prototype, const TypeInfo& typeInfo, const ClassInfo* classInfo, IndexingType indexingType, unsigned inlineCapacity)
 217      : JSCell(vm, vm.structureStructure.get())
 218      , m_blob(vm.heap.structureIDTable().allocateID(this), indexingType, typeInfo)
 219      , m_outOfLineTypeFlags(typeInfo.outOfLineTypeFlags())
 220      , m_inlineCapacity(inlineCapacity)
 221      , m_bitField(0)
 222      , m_globalObject(vm, this, globalObject, WriteBarrier<JSGlobalObject>::MayBeNull)
 223      , m_prototype(vm, this, prototype)
 224      , m_classInfo(classInfo)
 225      , m_transitionWatchpointSet(IsWatched)
 226      , m_propertyHash(0)
 227  {
 228      setDictionaryKind(NoneDictionaryKind);
 229      setIsPinnedPropertyTable(false);
 230      setHasGetterSetterProperties(classInfo->hasStaticSetterOrReadonlyProperties());
 231      setHasCustomGetterSetterProperties(false);
 232      setHasReadOnlyOrGetterSetterPropertiesExcludingProto(classInfo->hasStaticSetterOrReadonlyProperties());
 233      setHasUnderscoreProtoPropertyExcludingOriginalProto(false);
 234      setIsQuickPropertyAccessAllowedForEnumeration(true);
 235      setTransitionPropertyAttributes(0);
 236      setTransitionKind(TransitionKind::Unknown);
 237      setDidPreventExtensions(false);
 238      setDidTransition(false);
 239      setStaticPropertiesReified(false);
 240      setTransitionWatchpointIsLikelyToBeFired(false);
 241      setHasBeenDictionary(false);
 242      setProtectPropertyTableWhileTransitioning(false);
 243      setTransitionOffset(vm, invalidOffset);
 244      setMaxOffset(vm, invalidOffset);
 245   
 246      ASSERT(inlineCapacity <= JSFinalObject::maxInlineCapacity());
 247      ASSERT(static_cast<PropertyOffset>(inlineCapacity) < firstOutOfLineOffset);
 248      ASSERT(!hasRareData());
 249      ASSERT(hasReadOnlyOrGetterSetterPropertiesExcludingProto() == m_classInfo->hasStaticSetterOrReadonlyProperties());
 250      ASSERT(hasGetterSetterProperties() == m_classInfo->hasStaticSetterOrReadonlyProperties());
 251  
 252      validateFlags();
 253  }
 254  
 255  const ClassInfo Structure::s_info = { "Structure", nullptr, nullptr, nullptr, CREATE_METHOD_TABLE(Structure) };
 256  
 257  Structure::Structure(VM& vm)
 258      : JSCell(CreatingEarlyCell)
 259      , m_inlineCapacity(0)
 260      , m_bitField(0)
 261      , m_prototype(vm, this, jsNull())
 262      , m_classInfo(info())
 263      , m_transitionWatchpointSet(IsWatched)
 264      , m_propertyHash(0)
 265  {
 266      setDictionaryKind(NoneDictionaryKind);
 267      setIsPinnedPropertyTable(false);
 268      setHasGetterSetterProperties(m_classInfo->hasStaticSetterOrReadonlyProperties());
 269      setHasCustomGetterSetterProperties(false);
 270      setHasReadOnlyOrGetterSetterPropertiesExcludingProto(m_classInfo->hasStaticSetterOrReadonlyProperties());
 271      setHasUnderscoreProtoPropertyExcludingOriginalProto(false);
 272      setIsQuickPropertyAccessAllowedForEnumeration(true);
 273      setTransitionPropertyAttributes(0);
 274      setTransitionKind(TransitionKind::Unknown);
 275      setDidPreventExtensions(false);
 276      setDidTransition(false);
 277      setStaticPropertiesReified(false);
 278      setTransitionWatchpointIsLikelyToBeFired(false);
 279      setHasBeenDictionary(false);
 280      setProtectPropertyTableWhileTransitioning(false);
 281      setTransitionOffset(vm, invalidOffset);
 282      setMaxOffset(vm, invalidOffset);
 283   
 284      TypeInfo typeInfo = TypeInfo(CellType, StructureFlags);
 285      m_blob = StructureIDBlob(vm.heap.structureIDTable().allocateID(this), 0, typeInfo);
 286      m_outOfLineTypeFlags = typeInfo.outOfLineTypeFlags();
 287  
 288      ASSERT(hasReadOnlyOrGetterSetterPropertiesExcludingProto() || !m_classInfo->hasStaticSetterOrReadonlyProperties());
 289      ASSERT(hasGetterSetterProperties() || !m_classInfo->hasStaticSetterOrReadonlyProperties());
 290      ASSERT(!this->typeInfo().overridesGetCallData() || m_classInfo->methodTable.getCallData != &JSCell::getCallData);
 291  }
 292  
 293  Structure::Structure(VM& vm, Structure* previous, DeferredStructureTransitionWatchpointFire* deferred)
 294      : JSCell(vm, vm.structureStructure.get())
 295      , m_inlineCapacity(previous->m_inlineCapacity)
 296      , m_bitField(0)
 297      , m_prototype(vm, this, previous->m_prototype.get())
 298      , m_classInfo(previous->m_classInfo)
 299      , m_transitionWatchpointSet(IsWatched)
 300      , m_propertyHash(previous->m_propertyHash)
 301      , m_seenProperties(previous->m_seenProperties)
 302  {
 303      setDictionaryKind(previous->dictionaryKind());
 304      setIsPinnedPropertyTable(false);
 305      setHasBeenFlattenedBefore(previous->hasBeenFlattenedBefore());
 306      setHasGetterSetterProperties(previous->hasGetterSetterProperties());
 307      setHasCustomGetterSetterProperties(previous->hasCustomGetterSetterProperties());
 308      setHasReadOnlyOrGetterSetterPropertiesExcludingProto(previous->hasReadOnlyOrGetterSetterPropertiesExcludingProto());
 309      setHasUnderscoreProtoPropertyExcludingOriginalProto(previous->hasUnderscoreProtoPropertyExcludingOriginalProto());
 310      setIsQuickPropertyAccessAllowedForEnumeration(previous->isQuickPropertyAccessAllowedForEnumeration());
 311      setTransitionPropertyAttributes(0);
 312      setTransitionKind(TransitionKind::Unknown);
 313      setDidPreventExtensions(previous->didPreventExtensions());
 314      setDidTransition(true);
 315      setStaticPropertiesReified(previous->staticPropertiesReified());
 316      setHasBeenDictionary(previous->hasBeenDictionary());
 317      setProtectPropertyTableWhileTransitioning(false);
 318      setTransitionOffset(vm, invalidOffset);
 319      setMaxOffset(vm, invalidOffset);
 320   
 321      TypeInfo typeInfo = previous->typeInfo();
 322      m_blob = StructureIDBlob(vm.heap.structureIDTable().allocateID(this), previous->indexingModeIncludingHistory(), typeInfo);
 323      m_outOfLineTypeFlags = typeInfo.outOfLineTypeFlags();
 324  
 325      ASSERT(!previous->typeInfo().structureIsImmortal());
 326      setPreviousID(vm, previous);
 327  
 328      previous->didTransitionFromThisStructure(deferred);
 329      
 330      // Copy this bit now, in case previous was being watched.
 331      setTransitionWatchpointIsLikelyToBeFired(previous->transitionWatchpointIsLikelyToBeFired());
 332  
 333      if (previous->m_globalObject)
 334          m_globalObject.set(vm, this, previous->m_globalObject.get());
 335      ASSERT(hasReadOnlyOrGetterSetterPropertiesExcludingProto() || !m_classInfo->hasStaticSetterOrReadonlyProperties());
 336      ASSERT(hasGetterSetterProperties() || !m_classInfo->hasStaticSetterOrReadonlyProperties());
 337      ASSERT(!this->typeInfo().overridesGetCallData() || m_classInfo->methodTable.getCallData != &JSCell::getCallData);
 338  }
 339  
 340  Structure::~Structure()
 341  {
 342      if (typeInfo().structureIsImmortal())
 343          return;
 344      Heap::heap(this)->structureIDTable().deallocateID(this, m_blob.structureID());
 345  }
 346  
 347  void Structure::destroy(JSCell* cell)
 348  {
 349      static_cast<Structure*>(cell)->Structure::~Structure();
 350  }
 351  
 352  Structure* Structure::create(PolyProtoTag, VM& vm, JSGlobalObject* globalObject, JSObject* prototype, const TypeInfo& typeInfo, const ClassInfo* classInfo, IndexingType indexingType, unsigned inlineCapacity)
 353  {
 354      Structure* result = create(vm, globalObject, prototype, typeInfo, classInfo, indexingType, inlineCapacity);
 355  
 356      unsigned oldOutOfLineCapacity = result->outOfLineCapacity();
 357      result->addPropertyWithoutTransition(
 358          vm, vm.propertyNames->builtinNames().polyProtoName(), static_cast<unsigned>(PropertyAttribute::DontEnum),
 359          [&] (const GCSafeConcurrentJSLocker&, PropertyOffset offset, PropertyOffset newMaxOffset) {
 360              RELEASE_ASSERT(Structure::outOfLineCapacity(newMaxOffset) == oldOutOfLineCapacity);
 361              RELEASE_ASSERT(offset == knownPolyProtoOffset);
 362              RELEASE_ASSERT(isInlineOffset(knownPolyProtoOffset));
 363              result->m_prototype.setWithoutWriteBarrier(JSValue());
 364              result->setMaxOffset(vm, newMaxOffset);
 365          });
 366  
 367      return result;
 368  }
 369  
 370  bool Structure::isValidPrototype(JSValue prototype)
 371  {
 372      return prototype.isNull() || (prototype.isObject() && prototype.getObject()->mayBePrototype());
 373  }
 374  
 375  void Structure::findStructuresAndMapForMaterialization(Vector<Structure*, 8>& structures, Structure*& structure, PropertyTable*& table)
 376  {
 377      ASSERT(structures.isEmpty());
 378      table = nullptr;
 379  
 380      for (structure = this; structure; structure = structure->previousID()) {
 381          structure->m_lock.lock();
 382          
 383          table = structure->propertyTableOrNull();
 384          if (table) {
 385              // Leave the structure locked, so that the caller can do things to it atomically
 386              // before it loses its property table.
 387              return;
 388          }
 389          
 390          structures.append(structure);
 391          structure->m_lock.unlock();
 392      }
 393      
 394      ASSERT(!structure);
 395      ASSERT(!table);
 396  }
 397  
 398  PropertyTable* Structure::materializePropertyTable(VM& vm, bool setPropertyTable)
 399  {
 400      ASSERT(structure(vm)->classInfo() == info());
 401      ASSERT(!protectPropertyTableWhileTransitioning());
 402      
 403      DeferGC deferGC(vm.heap);
 404      
 405      Vector<Structure*, 8> structures;
 406      Structure* structure;
 407      PropertyTable* table;
 408      
 409      findStructuresAndMapForMaterialization(structures, structure, table);
 410      
 411      unsigned capacity = numberOfSlotsForMaxOffset(maxOffset(), m_inlineCapacity);
 412      if (table) {
 413          table = table->copy(vm, capacity);
 414          structure->m_lock.unlock();
 415      } else
 416          table = PropertyTable::create(vm, capacity);
 417      
 418      // Must hold the lock on this structure, since we will be modifying this structure's
 419      // property map. We don't want getConcurrently() to see the property map in a half-baked
 420      // state.
 421      GCSafeConcurrentJSLocker locker(m_lock, vm.heap);
 422      if (setPropertyTable)
 423          this->setPropertyTable(vm, table);
 424  
 425      for (size_t i = structures.size(); i--;) {
 426          structure = structures[i];
 427          if (!structure->m_transitionPropertyName)
 428              continue;
 429          switch (structure->transitionKind()) {
 430          case TransitionKind::PropertyAddition: {
 431              PropertyMapEntry entry(structure->m_transitionPropertyName.get(), structure->transitionOffset(), structure->transitionPropertyAttributes());
 432              auto nextOffset = table->nextOffset(structure->inlineCapacity());
 433              ASSERT_UNUSED(nextOffset, nextOffset == structure->transitionOffset());
 434              auto result = table->add(vm, entry);
 435              ASSERT_UNUSED(result, result.second);
 436              ASSERT_UNUSED(result, result.first.first->offset == nextOffset);
 437              break;
 438          }
 439          case TransitionKind::PropertyDeletion: {
 440              auto item = table->find(structure->m_transitionPropertyName.get());
 441              ASSERT(item.first);
 442              table->remove(vm, item);
 443              table->addDeletedOffset(structure->transitionOffset());
 444              break;
 445          }
 446          case TransitionKind::PropertyAttributeChange: {
 447              PropertyMapEntry* entry = table->get(structure->m_transitionPropertyName.get());
 448              entry->attributes = structure->transitionPropertyAttributes();
 449              ASSERT(entry->offset == structure->transitionOffset());
 450              break;
 451          }
 452          default:
 453              ASSERT_NOT_REACHED();
 454              break;
 455          }
 456      }
 457      
 458      checkOffsetConsistency(
 459          table,
 460          [&] () {
 461              dataLog("Detected in materializePropertyTable.\n");
 462              dataLog("Found structure = ", RawPointer(structure), "\n");
 463              dataLog("structures = ");
 464              CommaPrinter comma;
 465              for (Structure* structure : structures)
 466                  dataLog(comma, RawPointer(structure));
 467              dataLog("\n");
 468          });
 469      
 470      return table;
 471  }
 472  
 473  Structure* Structure::addPropertyTransitionToExistingStructureImpl(Structure* structure, UniquedStringImpl* uid, unsigned attributes, PropertyOffset& offset)
 474  {
 475      ASSERT(!structure->isDictionary());
 476      ASSERT(structure->isObject());
 477  
 478      offset = invalidOffset;
 479  
 480      if (structure->hasBeenDictionary())
 481          return nullptr;
 482  
 483      if (Structure* existingTransition = structure->m_transitionTable.get(uid, attributes, TransitionKind::PropertyAddition)) {
 484          validateOffset(existingTransition->transitionOffset(), existingTransition->inlineCapacity());
 485          offset = existingTransition->transitionOffset();
 486          return existingTransition;
 487      }
 488  
 489      return nullptr;
 490  }
 491  
 492  Structure* Structure::addPropertyTransitionToExistingStructure(Structure* structure, PropertyName propertyName, unsigned attributes, PropertyOffset& offset)
 493  {
 494      ASSERT(!isCompilationThread());
 495      return addPropertyTransitionToExistingStructureImpl(structure, propertyName.uid(), attributes, offset);
 496  }
 497  
 498  Structure* Structure::addPropertyTransitionToExistingStructureConcurrently(Structure* structure, UniquedStringImpl* uid, unsigned attributes, PropertyOffset& offset)
 499  {
 500      ConcurrentJSLocker locker(structure->m_lock);
 501      return addPropertyTransitionToExistingStructureImpl(structure, uid, attributes, offset);
 502  }
 503  
 504  bool Structure::holesMustForwardToPrototype(VM& vm, JSObject* base) const
 505  {
 506      ASSERT(base->structure(vm) == this);
 507  
 508      if (this->mayInterceptIndexedAccesses())
 509          return true;
 510  
 511      JSValue prototype = this->storedPrototype(base);
 512      if (!prototype.isObject())
 513          return false;
 514      JSObject* object = asObject(prototype);
 515  
 516      while (true) {
 517          Structure& structure = *object->structure(vm);
 518          if (hasIndexedProperties(object->indexingType()) || structure.mayInterceptIndexedAccesses())
 519              return true;
 520          prototype = structure.storedPrototype(object);
 521          if (!prototype.isObject())
 522              return false;
 523          object = asObject(prototype);
 524      }
 525  
 526      RELEASE_ASSERT_NOT_REACHED();
 527      return false;
 528  }
 529  
 530  Structure* Structure::addPropertyTransition(VM& vm, Structure* structure, PropertyName propertyName, unsigned attributes, PropertyOffset& offset)
 531  {
 532      Structure* newStructure = addPropertyTransitionToExistingStructure(structure, propertyName, attributes, offset);
 533      if (newStructure)
 534          return newStructure;
 535  
 536      return addNewPropertyTransition(
 537          vm, structure, propertyName, attributes, offset, PutPropertySlot::UnknownContext);
 538  }
 539  
 540  Structure* Structure::addNewPropertyTransition(VM& vm, Structure* structure, PropertyName propertyName, unsigned attributes, PropertyOffset& offset, PutPropertySlot::Context context, DeferredStructureTransitionWatchpointFire* deferred)
 541  {
 542      ASSERT(!structure->isDictionary());
 543      ASSERT(structure->isObject());
 544      ASSERT(!Structure::addPropertyTransitionToExistingStructure(structure, propertyName, attributes, offset));
 545      
 546      int maxTransitionLength;
 547      if (context == PutPropertySlot::PutById)
 548          maxTransitionLength = s_maxTransitionLengthForNonEvalPutById;
 549      else
 550          maxTransitionLength = s_maxTransitionLength;
 551      if (structure->transitionCountEstimate() > maxTransitionLength) {
 552          ASSERT(!isCopyOnWrite(structure->indexingMode()));
 553          Structure* transition = toCacheableDictionaryTransition(vm, structure, deferred);
 554          ASSERT(structure != transition);
 555          offset = transition->add(vm, propertyName, attributes);
 556          return transition;
 557      }
 558      
 559      Structure* transition = create(vm, structure, deferred);
 560  
 561      transition->m_cachedPrototypeChain.setMayBeNull(vm, transition, structure->m_cachedPrototypeChain.get());
 562      
 563      // While we are adding the property, rematerializing the property table is super weird: we already
 564      // have a m_transitionPropertyName and transitionPropertyAttributes but the m_transitionOffset is still wrong. If the
 565      // materialization algorithm runs, it'll build a property table that already has the property but
 566      // at a bogus offset. Rather than try to teach the materialization code how to create a table under
 567      // those conditions, we just tell the GC not to blow the table away during this period of time.
 568      // Holding the lock ensures that we either do this before the GC starts scanning the structure, in
 569      // which case the GC will not blow the table away, or we do it after the GC already ran in which
 570      // case all is well.  If it wasn't for the lock, the GC would have TOCTOU: if could read
 571      // protectPropertyTableWhileTransitioning before we set it to true, and then blow the table away after.
 572      {
 573          ConcurrentJSLocker locker(transition->m_lock);
 574          transition->setProtectPropertyTableWhileTransitioning(true);
 575      }
 576  
 577      transition->m_blob.setIndexingModeIncludingHistory(structure->indexingModeIncludingHistory() & ~CopyOnWrite);
 578      transition->m_transitionPropertyName = propertyName.uid();
 579      transition->setTransitionPropertyAttributes(attributes);
 580      transition->setTransitionKind(TransitionKind::PropertyAddition);
 581      transition->setPropertyTable(vm, structure->takePropertyTableOrCloneIfPinned(vm));
 582      transition->setMaxOffset(vm, structure->maxOffset());
 583  
 584      offset = transition->add(vm, propertyName, attributes);
 585      transition->setTransitionOffset(vm, offset);
 586  
 587      // Now that everything is fine with the new structure's bookkeeping, the GC is free to blow the
 588      // table away if it wants. We can now rebuild it fine.
 589      WTF::storeStoreFence();
 590      transition->setProtectPropertyTableWhileTransitioning(false);
 591  
 592      checkOffset(transition->transitionOffset(), transition->inlineCapacity());
 593      if (!structure->hasBeenDictionary()) {
 594          GCSafeConcurrentJSLocker locker(structure->m_lock, vm.heap);
 595          structure->m_transitionTable.add(vm, transition);
 596      }
 597      transition->checkOffsetConsistency();
 598      structure->checkOffsetConsistency();
 599      return transition;
 600  }
 601  
 602  Structure* Structure::removePropertyTransition(VM& vm, Structure* structure, PropertyName propertyName, PropertyOffset& offset, DeferredStructureTransitionWatchpointFire* deferred)
 603  {
 604      Structure* newStructure = removePropertyTransitionFromExistingStructure(structure, propertyName, offset);
 605      if (newStructure)
 606          return newStructure;
 607  
 608      return removeNewPropertyTransition(
 609          vm, structure, propertyName, offset, deferred);
 610  }
 611  
 612  Structure* Structure::removePropertyTransitionFromExistingStructureImpl(Structure* structure, PropertyName propertyName, unsigned attributes, PropertyOffset& offset)
 613  {
 614      ASSERT(!structure->isUncacheableDictionary());
 615      ASSERT(structure->isObject());
 616  
 617      offset = invalidOffset;
 618  
 619      if (structure->hasBeenDictionary())
 620          return nullptr;
 621  
 622      if (Structure* existingTransition = structure->m_transitionTable.get(propertyName.uid(), attributes, TransitionKind::PropertyDeletion)) {
 623          validateOffset(existingTransition->transitionOffset(), existingTransition->inlineCapacity());
 624          offset = existingTransition->transitionOffset();
 625          return existingTransition;
 626      }
 627  
 628      return nullptr;
 629  }
 630  
 631  Structure* Structure::removePropertyTransitionFromExistingStructure(Structure* structure, PropertyName propertyName, PropertyOffset& offset)
 632  {
 633      ASSERT(!isCompilationThread());
 634      unsigned attributes = 0;
 635      if (structure->getConcurrently(propertyName.uid(), attributes) == invalidOffset)
 636          return nullptr;
 637      return removePropertyTransitionFromExistingStructureImpl(structure, propertyName, attributes, offset);
 638  }
 639  
 640  Structure* Structure::removePropertyTransitionFromExistingStructureConcurrently(Structure* structure, PropertyName propertyName, PropertyOffset& offset)
 641  {
 642      unsigned attributes = 0;
 643      if (structure->getConcurrently(propertyName.uid(), attributes) == invalidOffset)
 644          return nullptr;
 645      ConcurrentJSLocker locker(structure->m_lock);
 646      return removePropertyTransitionFromExistingStructureImpl(structure, propertyName, attributes, offset);
 647  }
 648  
 649  Structure* Structure::removeNewPropertyTransition(VM& vm, Structure* structure, PropertyName propertyName, PropertyOffset& offset, DeferredStructureTransitionWatchpointFire* deferred)
 650  {
 651      ASSERT(!isCompilationThread());
 652      ASSERT(!structure->isUncacheableDictionary());
 653      ASSERT(structure->isObject());
 654      ASSERT(!Structure::removePropertyTransitionFromExistingStructure(structure, propertyName, offset));
 655      ASSERT(structure->getConcurrently(propertyName.uid()) != invalidOffset);
 656  
 657      if (structure->transitionCountHasOverflowed()) {
 658          ASSERT(!isCopyOnWrite(structure->indexingMode()));
 659          Structure* transition = toUncacheableDictionaryTransition(vm, structure, deferred);
 660          ASSERT(structure != transition);
 661          offset = transition->remove(vm, propertyName);
 662          return transition;
 663      }
 664  
 665      Structure* transition = create(vm, structure, deferred);
 666      transition->m_cachedPrototypeChain.setMayBeNull(vm, transition, structure->m_cachedPrototypeChain.get());
 667  
 668      // While we are deleting the property, we need to make sure the table is not cleared.
 669      {
 670          ConcurrentJSLocker locker(transition->m_lock);
 671          transition->setProtectPropertyTableWhileTransitioning(true);
 672      }
 673  
 674      transition->m_blob.setIndexingModeIncludingHistory(structure->indexingModeIncludingHistory() & ~CopyOnWrite);
 675      transition->m_transitionPropertyName = propertyName.uid();
 676      transition->setTransitionKind(TransitionKind::PropertyDeletion);
 677      transition->setPropertyTable(vm, structure->takePropertyTableOrCloneIfPinned(vm));
 678      transition->setMaxOffset(vm, structure->maxOffset());
 679  
 680      offset = transition->remove(vm, propertyName);
 681      ASSERT(offset != invalidOffset);
 682      transition->setTransitionOffset(vm, offset);
 683  
 684      // Now that everything is fine with the new structure's bookkeeping, the GC is free to blow the
 685      // table away if it wants. We can now rebuild it fine.
 686      WTF::storeStoreFence();
 687      transition->setProtectPropertyTableWhileTransitioning(false);
 688  
 689      checkOffset(transition->transitionOffset(), transition->inlineCapacity());
 690      if (!structure->hasBeenDictionary()) {
 691          GCSafeConcurrentJSLocker locker(structure->m_lock, vm.heap);
 692          structure->m_transitionTable.add(vm, transition);
 693      }
 694      transition->checkOffsetConsistency();
 695      structure->checkOffsetConsistency();
 696      return transition;
 697  }
 698  
 699  Structure* Structure::changePrototypeTransition(VM& vm, Structure* structure, JSValue prototype, DeferredStructureTransitionWatchpointFire& deferred)
 700  {
 701      ASSERT(isValidPrototype(prototype));
 702  
 703      DeferGC deferGC(vm.heap);
 704      Structure* transition = create(vm, structure, &deferred);
 705  
 706      transition->m_prototype.set(vm, transition, prototype);
 707  
 708      PropertyTable* table = structure->copyPropertyTableForPinning(vm);
 709      transition->pin(holdLock(transition->m_lock), vm, table);
 710      transition->setMaxOffset(vm, structure->maxOffset());
 711      
 712      transition->checkOffsetConsistency();
 713      return transition;
 714  }
 715  
 716  Structure* Structure::attributeChangeTransitionToExistingStructure(Structure* structure, PropertyName propertyName, unsigned attributes, PropertyOffset& offset)
 717  {
 718      ASSERT(structure->isObject());
 719  
 720      offset = invalidOffset;
 721  
 722      if (structure->hasBeenDictionary())
 723          return nullptr;
 724  
 725      if (Structure* existingTransition = structure->m_transitionTable.get(propertyName.uid(), attributes, TransitionKind::PropertyAttributeChange)) {
 726          validateOffset(existingTransition->transitionOffset(), existingTransition->inlineCapacity());
 727          offset = existingTransition->transitionOffset();
 728          return existingTransition;
 729      }
 730  
 731      return nullptr;
 732  }
 733  
 734  Structure* Structure::attributeChangeTransition(VM& vm, Structure* structure, PropertyName propertyName, unsigned attributes, DeferredStructureTransitionWatchpointFire* deferred)
 735  {
 736      if (structure->isUncacheableDictionary()) {
 737          structure->attributeChangeWithoutTransition(vm, propertyName, attributes, [](const GCSafeConcurrentJSLocker&, PropertyOffset, PropertyOffset) { });
 738          structure->checkOffsetConsistency();
 739          return structure;
 740      }
 741  
 742      ASSERT(!structure->isUncacheableDictionary());
 743      PropertyOffset offset = invalidOffset;
 744      if (Structure* existingTransition = attributeChangeTransitionToExistingStructure(structure, propertyName, attributes, offset)) {
 745          validateOffset(existingTransition->transitionOffset(), existingTransition->inlineCapacity());
 746          existingTransition->checkOffsetConsistency();
 747          return existingTransition;
 748      }
 749  
 750      if (structure->transitionCountHasOverflowed()) {
 751          ASSERT(!isCopyOnWrite(structure->indexingMode()));
 752          Structure* transition = toUncacheableDictionaryTransition(vm, structure, deferred);
 753          ASSERT(structure != transition);
 754          transition->attributeChange(vm, propertyName, attributes);
 755          return transition;
 756      }
 757  
 758      // Even if the current structure is dictionary, we should perform transition since this changes attributes of existing properties to keep
 759      // structure still cacheable.
 760      Structure* transition = create(vm, structure);
 761      transition->m_cachedPrototypeChain.setMayBeNull(vm, transition, structure->m_cachedPrototypeChain.get());
 762  
 763      {
 764          ConcurrentJSLocker locker(transition->m_lock);
 765          transition->setProtectPropertyTableWhileTransitioning(true);
 766      }
 767  
 768      transition->m_blob.setIndexingModeIncludingHistory(structure->indexingModeIncludingHistory() & ~CopyOnWrite);
 769      transition->m_transitionPropertyName = propertyName.uid();
 770      transition->setTransitionPropertyAttributes(attributes);
 771      transition->setTransitionKind(TransitionKind::PropertyAttributeChange);
 772      transition->setPropertyTable(vm, structure->takePropertyTableOrCloneIfPinned(vm));
 773      transition->setMaxOffset(vm, structure->maxOffset());
 774  
 775      offset = transition->attributeChange(vm, propertyName, attributes);
 776      transition->setTransitionOffset(vm, offset);
 777  
 778      // Now that everything is fine with the new structure's bookkeeping, the GC is free to blow the
 779      // table away if it wants. We can now rebuild it fine.
 780      WTF::storeStoreFence();
 781      transition->setProtectPropertyTableWhileTransitioning(false);
 782  
 783      checkOffset(transition->transitionOffset(), transition->inlineCapacity());
 784      if (!structure->hasBeenDictionary()) {
 785          GCSafeConcurrentJSLocker locker(structure->m_lock, vm.heap);
 786          structure->m_transitionTable.add(vm, transition);
 787      }
 788      transition->checkOffsetConsistency();
 789      structure->checkOffsetConsistency();
 790      return transition;
 791  }
 792  
 793  Structure* Structure::toDictionaryTransition(VM& vm, Structure* structure, DictionaryKind kind, DeferredStructureTransitionWatchpointFire* deferred)
 794  {
 795      ASSERT(!structure->isUncacheableDictionary());
 796      DeferGC deferGC(vm.heap);
 797      
 798      Structure* transition = create(vm, structure, deferred);
 799  
 800      PropertyTable* table = structure->copyPropertyTableForPinning(vm);
 801      transition->pin(holdLock(transition->m_lock), vm, table);
 802      transition->setMaxOffset(vm, structure->maxOffset());
 803      transition->setDictionaryKind(kind);
 804      transition->setHasBeenDictionary(true);
 805      
 806      transition->checkOffsetConsistency();
 807      return transition;
 808  }
 809  
 810  Structure* Structure::toCacheableDictionaryTransition(VM& vm, Structure* structure, DeferredStructureTransitionWatchpointFire* deferred)
 811  {
 812      return toDictionaryTransition(vm, structure, CachedDictionaryKind, deferred);
 813  }
 814  
 815  Structure* Structure::toUncacheableDictionaryTransition(VM& vm, Structure* structure, DeferredStructureTransitionWatchpointFire* deferred)
 816  {
 817      return toDictionaryTransition(vm, structure, UncachedDictionaryKind, deferred);
 818  }
 819  
 820  Structure* Structure::sealTransition(VM& vm, Structure* structure)
 821  {
 822      return nonPropertyTransition(vm, structure, TransitionKind::Seal);
 823  }
 824  
 825  Structure* Structure::freezeTransition(VM& vm, Structure* structure)
 826  {
 827      return nonPropertyTransition(vm, structure, TransitionKind::Freeze);
 828  }
 829  
 830  Structure* Structure::preventExtensionsTransition(VM& vm, Structure* structure)
 831  {
 832      return nonPropertyTransition(vm, structure, TransitionKind::PreventExtensions);
 833  }
 834  
 835  PropertyTable* Structure::takePropertyTableOrCloneIfPinned(VM& vm)
 836  {
 837      // This must always return a property table. It can't return null.
 838      PropertyTable* result = propertyTableOrNull();
 839      if (result) {
 840          if (isPinnedPropertyTable())
 841              return result->copy(vm, result->size() + 1);
 842          ConcurrentJSLocker locker(m_lock);
 843          setPropertyTable(vm, nullptr);
 844          return result;
 845      }
 846      bool setPropertyTable = false;
 847      return materializePropertyTable(vm, setPropertyTable);
 848  }
 849  
 850  Structure* Structure::nonPropertyTransitionSlow(VM& vm, Structure* structure, TransitionKind transitionKind)
 851  {
 852      IndexingType indexingModeIncludingHistory = newIndexingType(structure->indexingModeIncludingHistory(), transitionKind);
 853      
 854      if (!structure->isDictionary()) {
 855          if (Structure* existingTransition = structure->m_transitionTable.get(nullptr, 0, transitionKind)) {
 856              ASSERT(existingTransition->transitionKind() == transitionKind);
 857              ASSERT(existingTransition->indexingModeIncludingHistory() == indexingModeIncludingHistory);
 858              return existingTransition;
 859          }
 860      }
 861      
 862      DeferGC deferGC(vm.heap);
 863      
 864      Structure* transition = create(vm, structure);
 865      transition->setTransitionKind(transitionKind);
 866      transition->m_blob.setIndexingModeIncludingHistory(indexingModeIncludingHistory);
 867      
 868      if (preventsExtensions(transitionKind))
 869          transition->setDidPreventExtensions(true);
 870      
 871      if (setsDontDeleteOnAllProperties(transitionKind)
 872          || setsReadOnlyOnNonAccessorProperties(transitionKind)) {
 873          // We pin the property table on transitions that do wholesale editing of the property
 874          // table, since our logic for walking the property transition chain to rematerialize the
 875          // table doesn't know how to take into account such wholesale edits.
 876  
 877          PropertyTable* table = structure->copyPropertyTableForPinning(vm);
 878          transition->pinForCaching(holdLock(transition->m_lock), vm, table);
 879          transition->setMaxOffset(vm, structure->maxOffset());
 880          
 881          table = transition->propertyTableOrNull();
 882          RELEASE_ASSERT(table);
 883          for (auto& entry : *table) {
 884              if (setsDontDeleteOnAllProperties(transitionKind))
 885                  entry.attributes |= static_cast<unsigned>(PropertyAttribute::DontDelete);
 886              if (setsReadOnlyOnNonAccessorProperties(transitionKind) && !(entry.attributes & PropertyAttribute::Accessor))
 887                  entry.attributes |= static_cast<unsigned>(PropertyAttribute::ReadOnly);
 888          }
 889      } else {
 890          transition->setPropertyTable(vm, structure->takePropertyTableOrCloneIfPinned(vm));
 891          transition->setMaxOffset(vm, structure->maxOffset());
 892          checkOffset(transition->maxOffset(), transition->inlineCapacity());
 893      }
 894      
 895      if (setsReadOnlyOnNonAccessorProperties(transitionKind)
 896          && !transition->propertyTableOrNull()->isEmpty())
 897          transition->setHasReadOnlyOrGetterSetterPropertiesExcludingProto(true);
 898      
 899      if (structure->isDictionary()) {
 900          PropertyTable* table = transition->ensurePropertyTable(vm);
 901          transition->pin(holdLock(transition->m_lock), vm, table);
 902      } else {
 903          auto locker = holdLock(structure->m_lock);
 904          structure->m_transitionTable.add(vm, transition);
 905      }
 906  
 907      transition->checkOffsetConsistency();
 908      return transition;
 909  }
 910  
 911  // In future we may want to cache this property.
 912  bool Structure::isSealed(VM& vm)
 913  {
 914      if (isStructureExtensible())
 915          return false;
 916  
 917      PropertyTable* table = ensurePropertyTableIfNotEmpty(vm);
 918      if (!table)
 919          return true;
 920      
 921      PropertyTable::iterator end = table->end();
 922      for (PropertyTable::iterator iter = table->begin(); iter != end; ++iter) {
 923          if ((iter->attributes & PropertyAttribute::DontDelete) != static_cast<unsigned>(PropertyAttribute::DontDelete))
 924              return false;
 925      }
 926      return true;
 927  }
 928  
 929  // In future we may want to cache this property.
 930  bool Structure::isFrozen(VM& vm)
 931  {
 932      if (isStructureExtensible())
 933          return false;
 934  
 935      PropertyTable* table = ensurePropertyTableIfNotEmpty(vm);
 936      if (!table)
 937          return true;
 938      
 939      PropertyTable::iterator end = table->end();
 940      for (PropertyTable::iterator iter = table->begin(); iter != end; ++iter) {
 941          if (!(iter->attributes & PropertyAttribute::DontDelete))
 942              return false;
 943          if (!(iter->attributes & (PropertyAttribute::ReadOnly | PropertyAttribute::Accessor)))
 944              return false;
 945      }
 946      return true;
 947  }
 948  
 949  Structure* Structure::flattenDictionaryStructure(VM& vm, JSObject* object)
 950  {
 951      checkOffsetConsistency();
 952      ASSERT(isDictionary());
 953      ASSERT(object->structure(vm) == this);
 954      
 955      GCSafeConcurrentJSLocker locker(m_lock, vm.heap);
 956      
 957      object->setStructureIDDirectly(nuke(id()));
 958      WTF::storeStoreFence();
 959  
 960      size_t beforeOutOfLineCapacity = this->outOfLineCapacity();
 961      if (isUncacheableDictionary()) {
 962          PropertyTable* table = propertyTableOrNull();
 963          ASSERT(table);
 964  
 965          size_t propertyCount = table->size();
 966  
 967          // Holds our values compacted by insertion order.
 968          Vector<JSValue> values(propertyCount);
 969  
 970          // Copies out our values from their hashed locations, compacting property table offsets as we go.
 971          unsigned i = 0;
 972          PropertyTable::iterator end = table->end();
 973          auto offset = invalidOffset;
 974          for (PropertyTable::iterator iter = table->begin(); iter != end; ++iter, ++i) {
 975              values[i] = object->getDirect(iter->offset);
 976              offset = iter->offset = offsetForPropertyNumber(i, m_inlineCapacity);
 977          }
 978          setMaxOffset(vm, offset);
 979          ASSERT(transitionOffset() == invalidOffset);
 980          
 981          // Copies in our values to their compacted locations.
 982          for (unsigned i = 0; i < propertyCount; i++)
 983              object->putDirect(vm, offsetForPropertyNumber(i, m_inlineCapacity), values[i]);
 984  
 985          table->clearDeletedOffsets();
 986  
 987          // We need to zero our unused property space; otherwise the GC might see a
 988          // stale pointer when we add properties in the future.
 989          gcSafeZeroMemory(
 990              object->inlineStorageUnsafe() + inlineSize(),
 991              (inlineCapacity() - inlineSize()) * sizeof(EncodedJSValue));
 992  
 993          Butterfly* butterfly = object->butterfly();
 994          size_t preCapacity = butterfly->indexingHeader()->preCapacity(this);
 995          void* base = butterfly->base(preCapacity, beforeOutOfLineCapacity);
 996          void* startOfPropertyStorageSlots = reinterpret_cast<EncodedJSValue*>(base) + preCapacity;
 997          gcSafeZeroMemory(static_cast<JSValue*>(startOfPropertyStorageSlots), (beforeOutOfLineCapacity - outOfLineSize()) * sizeof(EncodedJSValue));
 998          checkOffsetConsistency();
 999      }
1000  
1001      setDictionaryKind(NoneDictionaryKind);
1002      setHasBeenFlattenedBefore(true);
1003  
1004      size_t afterOutOfLineCapacity = this->outOfLineCapacity();
1005  
1006      if (object->butterfly() && beforeOutOfLineCapacity != afterOutOfLineCapacity) {
1007          ASSERT(beforeOutOfLineCapacity > afterOutOfLineCapacity);
1008          // If the object had a Butterfly but after flattening/compacting we no longer have need of it,
1009          // we need to zero it out because the collector depends on the Structure to know the size for copying.
1010          if (!afterOutOfLineCapacity && !this->hasIndexingHeader(object))
1011              object->setButterfly(vm, nullptr);
1012          // If the object was down-sized to the point where the base of the Butterfly is no longer within the 
1013          // first CopiedBlock::blockSize bytes, we'll get the wrong answer if we try to mask the base back to 
1014          // the CopiedBlock header. To prevent this case we need to memmove the Butterfly down.
1015          else
1016              object->shiftButterflyAfterFlattening(locker, vm, this, afterOutOfLineCapacity);
1017      }
1018      
1019      WTF::storeStoreFence();
1020      object->setStructureIDDirectly(id());
1021  
1022      // We need to do a writebarrier here because the GC thread might be scanning the butterfly while
1023      // we are shuffling properties around. See: https://bugs.webkit.org/show_bug.cgi?id=166989
1024      vm.heap.writeBarrier(object);
1025  
1026      return this;
1027  }
1028  
1029  void Structure::pin(const AbstractLocker&, VM& vm, PropertyTable* table)
1030  {
1031      setIsPinnedPropertyTable(true);
1032      setPropertyTable(vm, table);
1033      clearPreviousID();
1034      m_transitionPropertyName = nullptr;
1035  }
1036  
1037  void Structure::pinForCaching(const AbstractLocker&, VM& vm, PropertyTable* table)
1038  {
1039      setIsPinnedPropertyTable(true);
1040      setPropertyTable(vm, table);
1041      m_transitionPropertyName = nullptr;
1042  }
1043  
1044  void Structure::allocateRareData(VM& vm)
1045  {
1046      ASSERT(!hasRareData());
1047      StructureRareData* rareData = StructureRareData::create(vm, previousID());
1048      WTF::storeStoreFence();
1049      m_previousOrRareData.set(vm, this, rareData);
1050      ASSERT(hasRareData());
1051  }
1052  
1053  WatchpointSet* Structure::ensurePropertyReplacementWatchpointSet(VM& vm, PropertyOffset offset)
1054  {
1055      ASSERT(!isUncacheableDictionary());
1056  
1057      // In some places it's convenient to call this with an invalid offset. So, we do the check here.
1058      if (!isValidOffset(offset))
1059          return nullptr;
1060      
1061      if (!hasRareData())
1062          allocateRareData(vm);
1063      ConcurrentJSLocker locker(m_lock);
1064      StructureRareData* rareData = this->rareData();
1065      if (!rareData->m_replacementWatchpointSets) {
1066          rareData->m_replacementWatchpointSets =
1067              makeUnique<StructureRareData::PropertyWatchpointMap>();
1068          WTF::storeStoreFence();
1069      }
1070      auto result = rareData->m_replacementWatchpointSets->add(offset, nullptr);
1071      if (result.isNewEntry)
1072          result.iterator->value = WatchpointSet::create(IsWatched);
1073      return result.iterator->value.get();
1074  }
1075  
1076  void Structure::startWatchingPropertyForReplacements(VM& vm, PropertyName propertyName)
1077  {
1078      ASSERT(!isUncacheableDictionary());
1079      
1080      startWatchingPropertyForReplacements(vm, get(vm, propertyName));
1081  }
1082  
1083  void Structure::didCachePropertyReplacement(VM& vm, PropertyOffset offset)
1084  {
1085      RELEASE_ASSERT(isValidOffset(offset));
1086      ensurePropertyReplacementWatchpointSet(vm, offset)->fireAll(vm, "Did cache property replacement");
1087  }
1088  
1089  void Structure::startWatchingInternalProperties(VM& vm)
1090  {
1091      if (!isUncacheableDictionary()) {
1092          startWatchingPropertyForReplacements(vm, vm.propertyNames->toString);
1093          startWatchingPropertyForReplacements(vm, vm.propertyNames->valueOf);
1094      }
1095      setDidWatchInternalProperties(true);
1096  }
1097  
1098  #if DUMP_PROPERTYMAP_STATS
1099  
1100  PropertyMapHashTableStats* propertyMapHashTableStats = 0;
1101  
1102  struct PropertyMapStatisticsExitLogger {
1103      PropertyMapStatisticsExitLogger();
1104      ~PropertyMapStatisticsExitLogger();
1105  };
1106  
1107  DEFINE_GLOBAL_FOR_LOGGING(PropertyMapStatisticsExitLogger, logger, );
1108  
1109  PropertyMapStatisticsExitLogger::PropertyMapStatisticsExitLogger()
1110  {
1111      propertyMapHashTableStats = adoptPtr(new PropertyMapHashTableStats()).leakPtr();
1112  }
1113  
1114  PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
1115  {
1116      unsigned finds = propertyMapHashTableStats->numFinds;
1117      unsigned collisions = propertyMapHashTableStats->numCollisions;
1118      dataLogF("\nJSC::PropertyMap statistics for process %d\n\n", getCurrentProcessID());
1119      dataLogF("%d finds\n", finds);
1120      dataLogF("%d collisions (%.1f%%)\n", collisions, 100.0 * collisions / finds);
1121      dataLogF("%d lookups\n", propertyMapHashTableStats->numLookups.load());
1122      dataLogF("%d lookup probings\n", propertyMapHashTableStats->numLookupProbing.load());
1123      dataLogF("%d adds\n", propertyMapHashTableStats->numAdds.load());
1124      dataLogF("%d removes\n", propertyMapHashTableStats->numRemoves.load());
1125      dataLogF("%d rehashes\n", propertyMapHashTableStats->numRehashes.load());
1126      dataLogF("%d reinserts\n", propertyMapHashTableStats->numReinserts.load());
1127  }
1128  
1129  #endif
1130  
1131  PropertyTable* Structure::copyPropertyTableForPinning(VM& vm)
1132  {
1133      if (PropertyTable* table = propertyTableOrNull())
1134          return PropertyTable::clone(vm, *table);
1135      bool setPropertyTable = false;
1136      return materializePropertyTable(vm, setPropertyTable);
1137  }
1138  
1139  PropertyOffset Structure::getConcurrently(UniquedStringImpl* uid, unsigned& attributes)
1140  {
1141      PropertyOffset result = invalidOffset;
1142      
1143      forEachPropertyConcurrently(
1144          [&] (const PropertyMapEntry& candidate) -> bool {
1145              if (candidate.key != uid)
1146                  return true;
1147              
1148              result = candidate.offset;
1149              attributes = candidate.attributes;
1150              return false;
1151          });
1152      
1153      return result;
1154  }
1155  
1156  Vector<PropertyMapEntry> Structure::getPropertiesConcurrently()
1157  {
1158      Vector<PropertyMapEntry> result;
1159  
1160      forEachPropertyConcurrently(
1161          [&] (const PropertyMapEntry& entry) -> bool {
1162              result.append(entry);
1163              return true;
1164          });
1165      
1166      return result;
1167  }
1168  
1169  PropertyOffset Structure::add(VM& vm, PropertyName propertyName, unsigned attributes)
1170  {
1171      return add<ShouldPin::No>(
1172          vm, propertyName, attributes,
1173          [this, &vm] (const GCSafeConcurrentJSLocker&, PropertyOffset, PropertyOffset newMaxOffset) {
1174              setMaxOffset(vm, newMaxOffset);
1175          });
1176  }
1177  
1178  PropertyOffset Structure::remove(VM& vm, PropertyName propertyName)
1179  {
1180      return remove<ShouldPin::No>(vm, propertyName, [this, &vm] (const GCSafeConcurrentJSLocker&, PropertyOffset, PropertyOffset newMaxOffset) {
1181          setMaxOffset(vm, newMaxOffset);
1182      });
1183  }
1184  
1185  PropertyOffset Structure::attributeChange(VM& vm, PropertyName propertyName, unsigned attributes)
1186  {
1187      return attributeChange<ShouldPin::No>(
1188          vm, propertyName, attributes,
1189          [this, &vm] (const GCSafeConcurrentJSLocker&, PropertyOffset, PropertyOffset newMaxOffset) {
1190              setMaxOffset(vm, newMaxOffset);
1191          });
1192  }
1193  
1194  void Structure::getPropertyNamesFromStructure(VM& vm, PropertyNameArray& propertyNames, DontEnumPropertiesMode mode)
1195  {
1196      PropertyTable* table = ensurePropertyTableIfNotEmpty(vm);
1197      if (!table)
1198          return;
1199      
1200      bool knownUnique = propertyNames.canAddKnownUniqueForStructure();
1201      bool foundSymbol = false;
1202  
1203      auto checkDontEnumAndAdd = [&](PropertyTable::iterator iter) {
1204          if (mode == DontEnumPropertiesMode::Include || !(iter->attributes & PropertyAttribute::DontEnum)) {
1205              if (knownUnique)
1206                  propertyNames.addUnchecked(iter->key);
1207              else
1208                  propertyNames.add(iter->key);
1209          }
1210      };
1211      
1212      PropertyTable::iterator end = table->end();
1213      for (PropertyTable::iterator iter = table->begin(); iter != end; ++iter) {
1214          ASSERT(!isQuickPropertyAccessAllowedForEnumeration() || !(iter->attributes & PropertyAttribute::DontEnum));
1215          ASSERT(!isQuickPropertyAccessAllowedForEnumeration() || !iter->key->isSymbol());
1216          if (iter->key->isSymbol()) {
1217              foundSymbol = true;
1218              if (propertyNames.propertyNameMode() != PropertyNameMode::Symbols)
1219                  continue;
1220          }
1221          checkDontEnumAndAdd(iter);
1222      }
1223  
1224      if (foundSymbol && propertyNames.propertyNameMode() == PropertyNameMode::StringsAndSymbols) {
1225          // To ensure the order defined in the spec, we append symbols at the last elements of keys.
1226          // https://tc39.es/ecma262/#sec-ordinaryownpropertykeys
1227          for (PropertyTable::iterator iter = table->begin(); iter != end; ++iter) {
1228              if (iter->key->isSymbol())
1229                  checkDontEnumAndAdd(iter);
1230          }
1231      }
1232  }
1233  
1234  void StructureFireDetail::dump(PrintStream& out) const
1235  {
1236      out.print("Structure transition from ", *m_structure);
1237  }
1238  
1239  DeferredStructureTransitionWatchpointFire::DeferredStructureTransitionWatchpointFire(VM& vm, Structure* structure)
1240      : DeferredWatchpointFire(vm)
1241      , m_structure(structure)
1242  {
1243  }
1244  
1245  DeferredStructureTransitionWatchpointFire::~DeferredStructureTransitionWatchpointFire()
1246  {
1247      fireAll();
1248  }
1249  
1250  void DeferredStructureTransitionWatchpointFire::dump(PrintStream& out) const
1251  {
1252      out.print("Structure transition from ", *m_structure);
1253  }
1254  
1255  void Structure::didTransitionFromThisStructure(DeferredStructureTransitionWatchpointFire* deferred) const
1256  {
1257      // If the structure is being watched, and this is the kind of structure that the DFG would
1258      // like to watch, then make sure to note for all future versions of this structure that it's
1259      // unwise to watch it.
1260      if (m_transitionWatchpointSet.isBeingWatched())
1261          const_cast<Structure*>(this)->setTransitionWatchpointIsLikelyToBeFired(true);
1262  
1263      if (deferred) {
1264          ASSERT(deferred->structure() == this);
1265          m_transitionWatchpointSet.fireAll(vm(), deferred);
1266      } else
1267          m_transitionWatchpointSet.fireAll(vm(), StructureFireDetail(this));
1268  }
1269  
1270  void Structure::visitChildren(JSCell* cell, SlotVisitor& visitor)
1271  {
1272      Structure* thisObject = jsCast<Structure*>(cell);
1273      ASSERT_GC_OBJECT_INHERITS(thisObject, info());
1274  
1275      Base::visitChildren(thisObject, visitor);
1276      
1277      ConcurrentJSLocker locker(thisObject->m_lock);
1278      
1279      visitor.append(thisObject->m_globalObject);
1280      if (!thisObject->isObject())
1281          thisObject->m_cachedPrototypeChain.clear();
1282      else {
1283          visitor.append(thisObject->m_prototype);
1284          visitor.append(thisObject->m_cachedPrototypeChain);
1285      }
1286      visitor.append(thisObject->m_previousOrRareData);
1287  
1288      if (thisObject->isPinnedPropertyTable() || thisObject->protectPropertyTableWhileTransitioning()) {
1289          // NOTE: This can interleave in pin(), in which case it may see a null property table.
1290          // That's fine, because then the barrier will fire and we will scan this again.
1291          visitor.append(thisObject->m_propertyTableUnsafe);
1292      } else if (visitor.isAnalyzingHeap())
1293          visitor.append(thisObject->m_propertyTableUnsafe);
1294      else if (thisObject->m_propertyTableUnsafe)
1295          thisObject->m_propertyTableUnsafe.clear();
1296  }
1297  
1298  bool Structure::isCheapDuringGC(VM& vm)
1299  {
1300      // FIXME: We could make this even safer by returning false if this structure's property table
1301      // has any large property names.
1302      // https://bugs.webkit.org/show_bug.cgi?id=157334
1303      
1304      return (!m_globalObject || vm.heap.isMarked(m_globalObject.get()))
1305          && (hasPolyProto() || !storedPrototypeObject() || vm.heap.isMarked(storedPrototypeObject()));
1306  }
1307  
1308  bool Structure::markIfCheap(SlotVisitor& visitor)
1309  {
1310      VM& vm = visitor.vm();
1311      if (!isCheapDuringGC(vm))
1312          return vm.heap.isMarked(this);
1313      
1314      visitor.appendUnbarriered(this);
1315      return true;
1316  }
1317  
1318  Ref<StructureShape> Structure::toStructureShape(JSValue value, bool& sawPolyProtoStructure)
1319  {
1320      Ref<StructureShape> baseShape = StructureShape::create();
1321      RefPtr<StructureShape> curShape = baseShape.ptr();
1322      Structure* curStructure = this;
1323      JSValue curValue = value;
1324      sawPolyProtoStructure = false;
1325      while (curStructure) {
1326          sawPolyProtoStructure |= curStructure->hasPolyProto();
1327          curStructure->forEachPropertyConcurrently(
1328              [&] (const PropertyMapEntry& entry) -> bool {
1329                  if (!PropertyName(entry.key).isPrivateName())
1330                      curShape->addProperty(*entry.key);
1331                  return true;
1332              });
1333  
1334          if (JSObject* curObject = curValue.getObject())
1335              curShape->setConstructorName(JSObject::calculatedClassName(curObject));
1336          else
1337              curShape->setConstructorName(curStructure->classInfo()->className);
1338  
1339          if (curStructure->isDictionary())
1340              curShape->enterDictionaryMode();
1341  
1342          curShape->markAsFinal();
1343  
1344          if (!curValue.isObject())
1345              break;
1346  
1347          JSObject* object = asObject(curValue);
1348          JSObject* prototypeObject = object->structure()->storedPrototypeObject(object);
1349          if (!prototypeObject)
1350              break;
1351  
1352          auto newShape = StructureShape::create();
1353          curShape->setProto(newShape.copyRef());
1354          curShape = WTFMove(newShape);
1355          curValue = prototypeObject;
1356          curStructure = prototypeObject->structure();
1357      }
1358      
1359      return baseShape;
1360  }
1361  
1362  void Structure::dump(PrintStream& out) const
1363  {
1364      out.print(RawPointer(this), ":[", RawPointer(reinterpret_cast<void*>(id())), ", ", classInfo()->className, ", {");
1365      
1366      CommaPrinter comma;
1367      
1368      const_cast<Structure*>(this)->forEachPropertyConcurrently(
1369          [&] (const PropertyMapEntry& entry) -> bool {
1370              out.print(comma, entry.key, ":", static_cast<int>(entry.offset));
1371              return true;
1372          });
1373      
1374      out.print("}, ", IndexingTypeDump(indexingMode()));
1375      
1376      if (hasPolyProto())
1377          out.print(", PolyProto offset:", knownPolyProtoOffset);
1378      else if (m_prototype.get().isCell())
1379          out.print(", Proto:", RawPointer(m_prototype.get().asCell()));
1380  
1381      switch (dictionaryKind()) {
1382      case NoneDictionaryKind:
1383          if (hasBeenDictionary())
1384              out.print(", Has been dictionary");
1385          break;
1386      case CachedDictionaryKind:
1387          out.print(", Dictionary");
1388          break;
1389      case UncachedDictionaryKind:
1390          out.print(", UncacheableDictionary");
1391          break;
1392      }
1393  
1394      if (transitionWatchpointSetIsStillValid())
1395          out.print(", Leaf");
1396      else if (transitionWatchpointIsLikelyToBeFired())
1397          out.print(", Shady leaf");
1398      
1399      if (transitionWatchpointSet().isBeingWatched())
1400          out.print(" (Watched)");
1401  
1402      out.print("]");
1403  }
1404  
1405  void Structure::dumpInContext(PrintStream& out, DumpContext* context) const
1406  {
1407      if (context)
1408          context->structures.dumpBrief(this, out);
1409      else
1410          dump(out);
1411  }
1412  
1413  void Structure::dumpBrief(PrintStream& out, const CString& string) const
1414  {
1415      out.print("%", string, ":", classInfo()->className);
1416      if (indexingType() & IndexingShapeMask)
1417          out.print(",", IndexingTypeDump(indexingType()));
1418  }
1419  
1420  void Structure::dumpContextHeader(PrintStream& out)
1421  {
1422      out.print("Structures:");
1423  }
1424  
1425  bool ClassInfo::hasStaticSetterOrReadonlyProperties() const
1426  {
1427      for (const ClassInfo* ci = this; ci; ci = ci->parentClass) {
1428          if (const HashTable* table = ci->staticPropHashTable) {
1429              if (table->hasSetterOrReadonlyProperties)
1430                  return true;
1431          }
1432      }
1433      return false;
1434  }
1435  
1436  void Structure::setCachedPropertyNameEnumerator(VM& vm, JSPropertyNameEnumerator* enumerator)
1437  {
1438      ASSERT(!isDictionary());
1439      if (!hasRareData())
1440          allocateRareData(vm);
1441      rareData()->setCachedPropertyNameEnumerator(vm, enumerator);
1442  }
1443  
1444  JSPropertyNameEnumerator* Structure::cachedPropertyNameEnumerator() const
1445  {
1446      if (!hasRareData())
1447          return nullptr;
1448      return rareData()->cachedPropertyNameEnumerator();
1449  }
1450  
1451  bool Structure::canCachePropertyNameEnumerator(VM& vm) const
1452  {
1453      if (!this->canCacheOwnPropertyNames())
1454          return false;
1455  
1456      StructureChain* structureChain = m_cachedPrototypeChain.get();
1457      ASSERT(structureChain);
1458      StructureID* currentStructureID = structureChain->head();
1459      while (true) {
1460          StructureID structureID = *currentStructureID;
1461          if (!structureID)
1462              return true;
1463          Structure* structure = vm.getStructure(structureID);
1464          if (!structure->canCacheOwnPropertyNames())
1465              return false;
1466          currentStructureID++;
1467      }
1468  
1469      ASSERT_NOT_REACHED();
1470      return true;
1471  }
1472      
1473  bool Structure::canAccessPropertiesQuicklyForEnumeration() const
1474  {
1475      if (!isQuickPropertyAccessAllowedForEnumeration())
1476          return false;
1477      if (hasGetterSetterProperties())
1478          return false;
1479      if (hasCustomGetterSetterProperties())
1480          return false;
1481      if (isUncacheableDictionary())
1482          return false;
1483      if (typeInfo().overridesGetOwnPropertyNames())
1484          return false;
1485      return true;
1486  }
1487  
1488  auto Structure::findPropertyHashEntry(PropertyName propertyName) const -> Optional<PropertyHashEntry>
1489  {
1490      for (const ClassInfo* info = classInfo(); info; info = info->parentClass) {
1491          if (const HashTable* propHashTable = info->staticPropHashTable) {
1492              if (const HashTableValue* entry = propHashTable->entry(propertyName))
1493                  return PropertyHashEntry { propHashTable, entry };
1494          }
1495      }
1496      return WTF::nullopt;
1497  }
1498  
1499  } // namespace JSC