/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

/* JavaScript iterators. */

#include "vm/Iteration.h"

#include "mozilla/ArrayUtils.h"
#include "mozilla/Likely.h"
#include "mozilla/Maybe.h"
#include "mozilla/MemoryReporting.h"
#include "mozilla/PodOperations.h"

#include <algorithm>
#include <new>

#include "jsapi.h"
#include "jstypes.h"

#include "builtin/Array.h"
#include "builtin/MapObject.h"
#include "builtin/SelfHostingDefines.h"
#include "ds/Sort.h"
#include "gc/GC.h"
#include "gc/GCContext.h"
#include "js/ForOfIterator.h"         // JS::ForOfIterator
#include "js/friend/ErrorMessages.h"  // js::GetErrorMessage, JSMSG_*
#include "js/PropertySpec.h"
#include "util/DifferentialTesting.h"
#include "util/Poison.h"
#include "vm/GlobalObject.h"
#include "vm/Interpreter.h"
#include "vm/JSContext.h"
#include "vm/JSObject.h"
#include "vm/NativeObject.h"  // js::PlainObject
#include "vm/Shape.h"
#include "vm/StringType.h"
#include "vm/TypedArrayObject.h"
#include "vm/Watchtower.h"

#include "gc/StoreBuffer-inl.h"
#include "vm/NativeObject-inl.h"
#include "vm/PlainObject-inl.h"  // js::PlainObject::createWithTemplate
#include "vm/Shape-inl.h"        // js::GetPropertyAttributes

using namespace js;

using mozilla::ArrayEqual;
using mozilla::Maybe;
using mozilla::PodCopy;

using RootedPropertyIteratorObject = Rooted<PropertyIteratorObject*>;

static const gc::AllocKind ITERATOR_FINALIZE_KIND =
    gc::AllocKind::OBJECT2_BACKGROUND;

// Beware!  This function may have to trace incompletely-initialized
// |NativeIterator| allocations if the |IdToString| in that constructor recurs
// into this code.
void NativeIterator::trace(JSTracer* trc) {
  TraceEdge(trc, &objectBeingIterated_, "objectBeingIterated_");
  TraceEdge(trc, &iterObj_, "iterObj_");
  TraceEdge(trc, &objShape_, "objShape_");

  // The limits below are correct at every instant of |NativeIterator|
  // initialization, with the end-pointer incremented as each new shape is
  // created, so they're safe to use here.
  std::for_each(protoShapesBegin(allocatedPropertyCount()), protoShapesEnd(),
                [trc](GCPtr<Shape*>& shape) {
                  TraceEdge(trc, &shape, "iterator_proto_shape");
                });

  std::for_each(propertiesBegin(), propertiesEnd(),
                [trc](IteratorProperty& prop) { prop.traceString(trc); });
}

void IteratorProperty::traceString(JSTracer* trc) {
  // Properties begin life non-null and never *become* null.
  // Trace the underlying string while preserving the deleted bit.
  JSLinearString* str = asString();
  TraceManuallyBarrieredEdge(trc, &str, "iterator-property-string");
  raw_ = uintptr_t(str) | (deleted() ? DeletedBit : 0);
}

using PropertyKeySet = GCHashSet<PropertyKey, DefaultHasher<PropertyKey>>;

class PropertyEnumerator {
  RootedObject obj_;
  MutableHandleIdVector props_;
  PropertyIndexVector* indices_;

  uint32_t flags_;
  Rooted<PropertyKeySet> visited_;

  uint32_t ownPropertyCount_ = 0;

  bool enumeratingProtoChain_ = false;
  bool forObjectKeys_ = false;

  enum class IndicesState {
    // Every property that has been enumerated so far can be represented as a
    // PropertyIndex, but we are not currently producing a list of indices. If
    // the state is Valid when we are done enumerating, then the resulting
    // iterator can be marked with NativeIterator::Flags::IndicesSupported.
    Valid,

    // Every property that has been enumerated so far can be represented as a
    // PropertyIndex, and |indices_| points to a PropertyIndexVector containing
    // those indices. This is used when we want to create a NativeIterator with
    // valid indices.
    Allocating,

    // It is not possible to represent every property of the object being
    // enumerated as a PropertyIndex. For example, enumerated properties on the
    // prototype chain are unsupported. We can transition to this state from
    // either of the other two.
    Unsupported
  };
  IndicesState indicesState_;

 public:
  PropertyEnumerator(JSContext* cx, JSObject* obj, uint32_t flags,
                     MutableHandleIdVector props,
                     PropertyIndexVector* indices = nullptr)
      : obj_(cx, obj),
        props_(props),
        indices_(indices),
        flags_(flags),
        visited_(cx, PropertyKeySet(cx)),
        indicesState_(indices ? IndicesState::Allocating
                              : IndicesState::Valid) {}

  bool snapshot(JSContext* cx);

  void markIndicesUnsupported() { indicesState_ = IndicesState::Unsupported; }
  bool supportsIndices() const {
    return indicesState_ != IndicesState::Unsupported;
  }
  bool allocatingIndices() const {
    return indicesState_ == IndicesState::Allocating;
  }
  uint32_t ownPropertyCount() const { return ownPropertyCount_; }

  void setForObjectKeys(bool value) { forObjectKeys_ = value; }

 private:
  template <bool CheckForDuplicates>
  bool enumerate(JSContext* cx, jsid id, bool enumerable,
                 PropertyIndex index = PropertyIndex::Invalid());

  bool enumerateExtraProperties(JSContext* cx);

  template <bool CheckForDuplicates>
  bool enumerateNativeProperties(JSContext* cx);

  bool enumerateNativeProperties(JSContext* cx, bool checkForDuplicates) {
    if (checkForDuplicates) {
      return enumerateNativeProperties<true>(cx);
    }
    return enumerateNativeProperties<false>(cx);
  }

  template <bool CheckForDuplicates>
  bool enumerateProxyProperties(JSContext* cx);

  void reversePropsAndIndicesAfter(size_t initialLength) {
    // We iterate through prop maps in descending order of property creation,
    // but we need our return value to be in ascending order. If we are tracking
    // property indices, make sure to keep them in sync.
    MOZ_ASSERT(props_.begin() + initialLength <= props_.end());
    MOZ_ASSERT_IF(allocatingIndices(), props_.length() == indices_->length());

    std::reverse(props_.begin() + initialLength, props_.end());
    if (allocatingIndices()) {
      std::reverse(indices_->begin() + initialLength, indices_->end());
    }
  }
};

template <bool CheckForDuplicates>
bool PropertyEnumerator::enumerate(JSContext* cx, jsid id, bool enumerable,
                                   PropertyIndex index) {
  if (CheckForDuplicates) {
    // If we've already seen this, we definitely won't add it.
    PropertyKeySet::AddPtr p = visited_.lookupForAdd(id);
    if (MOZ_UNLIKELY(!!p)) {
      return true;
    }

    // It's not necessary to add properties to the hash set at the end of
    // the prototype chain, but custom enumeration behaviors might return
    // duplicated properties, so always add in such cases.
    if (obj_->is<ProxyObject>() || obj_->staticPrototype() ||
        obj_->getClass()->getNewEnumerate()) {
      if (!visited_.add(p, id)) {
        return false;
      }
    }
  }

  if (!enumerable && !(flags_ & JSITER_HIDDEN)) {
    return true;
  }

  // Symbol-keyed properties and nonenumerable properties are skipped unless
  // the caller specifically asks for them. A caller can also filter out
  // non-symbols by asking for JSITER_SYMBOLSONLY. PrivateName symbols are
  // skipped unless JSITER_PRIVATE is passed.
  if (id.isSymbol()) {
    if (!(flags_ & JSITER_SYMBOLS)) {
      return true;
    }
    if (!(flags_ & JSITER_PRIVATE) && id.isPrivateName()) {
      return true;
    }
  } else {
    if ((flags_ & JSITER_SYMBOLSONLY)) {
      return true;
    }
  }

  MOZ_ASSERT_IF(allocatingIndices(), indices_->length() == props_.length());
  if (!props_.append(id)) {
    return false;
  }

  if (!supportsIndices()) {
    return true;
  }
  if (index.kind() == PropertyIndex::Kind::Invalid || enumeratingProtoChain_) {
    markIndicesUnsupported();
    return true;
  }

  if (allocatingIndices() && !indices_->append(index)) {
    return false;
  }

  return true;
}

bool PropertyEnumerator::enumerateExtraProperties(JSContext* cx) {
  MOZ_ASSERT(obj_->getClass()->getNewEnumerate());

  RootedIdVector properties(cx);
  bool enumerableOnly = !(flags_ & JSITER_HIDDEN);
  if (!obj_->getClass()->getNewEnumerate()(cx, obj_, &properties,
                                           enumerableOnly)) {
    return false;
  }

  RootedId id(cx);
  for (size_t n = 0; n < properties.length(); n++) {
    id = properties[n];

    // The enumerate hook does not indicate whether the properties
    // it returns are enumerable or not. Since we already passed
    // `enumerableOnly` to the hook to filter out non-enumerable
    // properties, it doesn't really matter what we pass here.
    bool enumerable = true;
    if (!enumerate<true>(cx, id, enumerable)) {
      return false;
    }
  }

  return true;
}

static bool SortComparatorIntegerIds(jsid a, jsid b, bool* lessOrEqualp) {
  uint32_t indexA, indexB;
  MOZ_ALWAYS_TRUE(IdIsIndex(a, &indexA));
  MOZ_ALWAYS_TRUE(IdIsIndex(b, &indexB));
  *lessOrEqualp = (indexA <= indexB);
  return true;
}

template <bool CheckForDuplicates>
bool PropertyEnumerator::enumerateNativeProperties(JSContext* cx) {
  Handle<NativeObject*> pobj = obj_.as<NativeObject>();

  if (Watchtower::watchesPropertyValueChange(pobj)) {
    markIndicesUnsupported();
  }

  // We don't need to iterate over the shape's properties if we're only
  // interested in enumerable properties and the object is known to have no
  // enumerable properties.
  //
  // Don't optimize if CheckForDuplicates is true, because non-enumerable
  // properties still have to participate in duplicate-property checking.
  const bool iterShapeProperties = CheckForDuplicates ||
                                   (flags_ & JSITER_HIDDEN) ||
                                   pobj->hasEnumerableProperty();

  bool enumerateSymbols;
  if (flags_ & JSITER_SYMBOLSONLY) {
    if (!iterShapeProperties) {
      return true;
    }
    enumerateSymbols = true;
  } else {
    // Collect any dense elements from this object.
    size_t firstElemIndex = props_.length();
    size_t initlen = pobj->getDenseInitializedLength();
    const Value* elements = pobj->getDenseElements();
    bool elementsAreFrozen = pobj->denseElementsAreFrozen();
    bool hasHoles = false;
    for (uint32_t i = 0; i < initlen; ++i) {
      if (elements[i].isMagic(JS_ELEMENTS_HOLE)) {
        hasHoles = true;
      } else {
        PropertyIndex index = elementsAreFrozen ? PropertyIndex::Invalid()
                                                : PropertyIndex::ForElement(i);
        // Dense arrays never get so large that i would not fit into an
        // integer id.
        if (!enumerate<CheckForDuplicates>(cx, PropertyKey::Int(i),
                                           /* enumerable = */ true, index)) {
          return false;
        }
      }
    }

    // Collect any typed array or shared typed array elements from this
    // object.
    if (pobj->is<TypedArrayObject>()) {
      size_t len = pobj->as<TypedArrayObject>().length().valueOr(0);

      // Fail early if the typed array is enormous, because this will be very
      // slow and will likely report OOM. This also means we don't need to
      // handle indices greater than PropertyKey::IntMax in the loop below.
      static_assert(PropertyKey::IntMax == INT32_MAX);
      if (len > INT32_MAX) {
        ReportOutOfMemory(cx);
        return false;
      }

      for (uint32_t i = 0; i < len; i++) {
        if (!enumerate<CheckForDuplicates>(cx, PropertyKey::Int(i),
                                           /* enumerable = */ true)) {
          return false;
        }
      }
    }

    // The code below enumerates shape properties (including sparse elements) so
    // if we can ignore those we're done.
    if (!iterShapeProperties) {
      return true;
    }

    // Collect any sparse elements from this object.
    bool isIndexed = pobj->isIndexed();
    if (isIndexed) {
      // If the dense elements didn't have holes, we don't need to include
      // them in the sort.
      if (!hasHoles) {
        firstElemIndex = props_.length();
      }

      for (ShapePropertyIter<NoGC> iter(pobj->shape()); !iter.done(); iter++) {
        jsid id = iter->key();
        uint32_t dummy;
        if (IdIsIndex(id, &dummy)) {
          if (!enumerate<CheckForDuplicates>(cx, id, iter->enumerable())) {
            return false;
          }
        }
      }

      MOZ_ASSERT(firstElemIndex <= props_.length());

      jsid* ids = props_.begin() + firstElemIndex;
      size_t n = props_.length() - firstElemIndex;

      RootedIdVector tmp(cx);
      if (!tmp.resize(n)) {
        return false;
      }
      PodCopy(tmp.begin(), ids, n);

      if (!MergeSort(ids, n, tmp.begin(), SortComparatorIntegerIds)) {
        return false;
      }
    }

    size_t initialLength = props_.length();

    /* Collect all unique property names from this object's shape. */
    bool symbolsFound = false;
    for (ShapePropertyIter<NoGC> iter(pobj->shape()); !iter.done(); iter++) {
      jsid id = iter->key();

      if (id.isSymbol()) {
        symbolsFound = true;
        continue;
      }

      uint32_t dummy;
      if (isIndexed && IdIsIndex(id, &dummy)) {
        continue;
      }

      PropertyIndex index = iter->isDataProperty() && iter->writable()
                                ? PropertyIndex::ForSlot(pobj, iter->slot())
                                : PropertyIndex::Invalid();
      if (!enumerate<CheckForDuplicates>(cx, id, iter->enumerable(), index)) {
        return false;
      }
    }
    reversePropsAndIndicesAfter(initialLength);

    enumerateSymbols = symbolsFound && (flags_ & JSITER_SYMBOLS);
  }

  if (enumerateSymbols) {
    MOZ_ASSERT(iterShapeProperties);
    MOZ_ASSERT(!allocatingIndices());

    // Do a second pass to collect symbols. The spec requires that all symbols
    // appear after all strings in [[OwnPropertyKeys]] for ordinary objects:
    // https://tc39.es/ecma262/#sec-ordinaryownpropertykeys
    size_t initialLength = props_.length();
    for (ShapePropertyIter<NoGC> iter(pobj->shape()); !iter.done(); iter++) {
      jsid id = iter->key();
      if (id.isSymbol()) {
        if (!enumerate<CheckForDuplicates>(cx, id, iter->enumerable())) {
          return false;
        }
      }
    }
    reversePropsAndIndicesAfter(initialLength);
  }

  return true;
}

template <bool CheckForDuplicates>
bool PropertyEnumerator::enumerateProxyProperties(JSContext* cx) {
  MOZ_ASSERT(obj_->is<ProxyObject>());

  RootedIdVector proxyProps(cx);

  if (flags_ & JSITER_HIDDEN || flags_ & JSITER_SYMBOLS) {
    // This gets all property keys, both strings and symbols. The call to
    // enumerate in the loop below will filter out unwanted keys, per the
    // flags.
    if (!Proxy::ownPropertyKeys(cx, obj_, &proxyProps)) {
      return false;
    }

    Rooted<mozilla::Maybe<PropertyDescriptor>> desc(cx);
    for (size_t n = 0, len = proxyProps.length(); n < len; n++) {
      bool enumerable = false;

      // We need to filter, if the caller just wants enumerable symbols.
      if (!(flags_ & JSITER_HIDDEN)) {
        if (!Proxy::getOwnPropertyDescriptor(cx, obj_, proxyProps[n], &desc)) {
          return false;
        }
        enumerable = desc.isSome() && desc->enumerable();
      }

      if (!enumerate<CheckForDuplicates>(cx, proxyProps[n], enumerable)) {
        return false;
      }
    }

    return true;
  }

  // Returns enumerable property names (no symbols).
  if (!Proxy::getOwnEnumerablePropertyKeys(cx, obj_, &proxyProps)) {
    return false;
  }

  for (size_t n = 0, len = proxyProps.length(); n < len; n++) {
    if (!enumerate<CheckForDuplicates>(cx, proxyProps[n], true)) {
      return false;
    }
  }

  return true;
}

#ifdef DEBUG

struct SortComparatorIds {
  JSContext* const cx;

  explicit SortComparatorIds(JSContext* cx) : cx(cx) {}

  bool operator()(jsid aArg, jsid bArg, bool* lessOrEqualp) {
    RootedId a(cx, aArg);
    RootedId b(cx, bArg);

    // Pick an arbitrary order on jsids that is as stable as possible
    // across executions.
    if (a == b) {
      *lessOrEqualp = true;
      return true;
    }

    enum class KeyType { Void, Int, String, Symbol };

    auto keyType = [](PropertyKey key) {
      if (key.isString()) {
        return KeyType::String;
      }
      if (key.isInt()) {
        return KeyType::Int;
      }
      if (key.isSymbol()) {
        return KeyType::Symbol;
      }
      MOZ_ASSERT(key.isVoid());
      return KeyType::Void;
    };

    if (keyType(a) != keyType(b)) {
      *lessOrEqualp = (keyType(a) <= keyType(b));
      return true;
    }

    if (a.isInt()) {
      *lessOrEqualp = (a.toInt() <= b.toInt());
      return true;
    }

    RootedString astr(cx), bstr(cx);
    if (a.isSymbol()) {
      MOZ_ASSERT(b.isSymbol());
      JS::SymbolCode ca = a.toSymbol()->code();
      JS::SymbolCode cb = b.toSymbol()->code();
      if (ca != cb) {
        *lessOrEqualp = uint32_t(ca) <= uint32_t(cb);
        return true;
      }
      MOZ_ASSERT(ca == JS::SymbolCode::PrivateNameSymbol ||
                 ca == JS::SymbolCode::InSymbolRegistry ||
                 ca == JS::SymbolCode::UniqueSymbol);
      astr = a.toSymbol()->description();
      bstr = b.toSymbol()->description();
      if (!astr || !bstr) {
        *lessOrEqualp = !astr;
        return true;
      }

      // Fall through to string comparison on the descriptions. The sort
      // order is nondeterministic if two different unique symbols have
      // the same description.
    } else {
      astr = IdToString(cx, a);
      if (!astr) {
        return false;
      }
      bstr = IdToString(cx, b);
      if (!bstr) {
        return false;
      }
    }

    int32_t result;
    if (!CompareStrings(cx, astr, bstr, &result)) {
      return false;
    }

    *lessOrEqualp = (result <= 0);
    return true;
  }
};

#endif /* DEBUG */

static void AssertNoEnumerableProperties(NativeObject* obj) {
#ifdef DEBUG
  // Verify the object has no enumerable properties if the HasEnumerable
  // ObjectFlag is not set.

  MOZ_ASSERT(!obj->hasEnumerableProperty());

  static constexpr size_t MaxPropsToCheck = 5;

  size_t count = 0;
  for (ShapePropertyIter<NoGC> iter(obj->shape()); !iter.done(); iter++) {
    MOZ_ASSERT(!iter->enumerable());
    if (++count > MaxPropsToCheck) {
      break;
    }
  }
#endif  // DEBUG
}

static bool ProtoMayHaveEnumerableProperties(JSObject* obj) {
  if (!obj->is<NativeObject>()) {
    return true;
  }

  JSObject* proto = obj->as<NativeObject>().staticPrototype();
  while (proto) {
    if (!proto->is<NativeObject>()) {
      return true;
    }
    NativeObject* nproto = &proto->as<NativeObject>();
    if (nproto->hasEnumerableProperty() ||
        nproto->getDenseInitializedLength() > 0 ||
        ClassCanHaveExtraEnumeratedProperties(nproto->getClass())) {
      return true;
    }
    AssertNoEnumerableProperties(nproto);
    proto = nproto->staticPrototype();
  }

  return false;
}

bool PropertyEnumerator::snapshot(JSContext* cx) {
  if (forObjectKeys_) {
    flags_ |= JSITER_OWNONLY;
  }

  // If we're only interested in enumerable properties and the proto chain has
  // no enumerable properties (the common case), we can optimize this to ignore
  // the proto chain. This also lets us take advantage of the no-duplicate-check
  // optimization below.
  if (!(flags_ & JSITER_HIDDEN) && !(flags_ & JSITER_OWNONLY) &&
      !ProtoMayHaveEnumerableProperties(obj_)) {
    flags_ |= JSITER_OWNONLY;
  }

  // Don't check for duplicates if we're only interested in own properties.
  // This does the right thing for most objects: native objects don't have
  // duplicate property ids and we allow the [[OwnPropertyKeys]] proxy trap to
  // return duplicates.
  //
  // The only special case is when the object has a newEnumerate hook: it
  // can return duplicate properties and we have to filter them. This is
  // handled below.
  bool checkForDuplicates = !(flags_ & JSITER_OWNONLY);

  do {
    if (obj_->getClass()->getNewEnumerate()) {
      markIndicesUnsupported();

      if (!enumerateExtraProperties(cx)) {
        return false;
      }

      if (obj_->is<NativeObject>()) {
        if (!enumerateNativeProperties(cx, /*checkForDuplicates*/ true)) {
          return false;
        }
      }

    } else if (obj_->is<NativeObject>()) {
      // Give the object a chance to resolve all lazy properties
      if (JSEnumerateOp enumerateOp = obj_->getClass()->getEnumerate()) {
        markIndicesUnsupported();
        if (!enumerateOp(cx, obj_.as<NativeObject>())) {
          return false;
        }
      }
      if (!enumerateNativeProperties(cx, checkForDuplicates)) {
        return false;
      }
    } else if (obj_->is<ProxyObject>()) {
      markIndicesUnsupported();
      if (checkForDuplicates) {
        if (!enumerateProxyProperties<true>(cx)) {
          return false;
        }
      } else {
        if (!enumerateProxyProperties<false>(cx)) {
          return false;
        }
      }
    } else {
      MOZ_CRASH("non-native objects must have an enumerate op");
    }

    if (!enumeratingProtoChain_) {
      ownPropertyCount_ = props_.length();
    }

    if (flags_ & JSITER_OWNONLY) {
      break;
    }

    if (!GetPrototype(cx, obj_, &obj_)) {
      return false;
    }
    enumeratingProtoChain_ = true;

    // The [[Prototype]] chain might be cyclic.
    if (!CheckForInterrupt(cx)) {
      return false;
    }
  } while (obj_ != nullptr);

#ifdef DEBUG
  if (js::SupportDifferentialTesting() && !supportsIndices() &&
      !forObjectKeys_) {
    /*
     * In some cases the enumeration order for an object depends on the
     * execution mode (interpreter vs. JIT), especially for native objects
     * with a class enumerate hook (where resolving a property changes the
     * resulting enumeration order). These aren't really bugs, but the
     * differences can change the generated output and confuse correctness
     * fuzzers, so we sort the ids if such a fuzzer is running.
     *
     * We don't do this in the general case because (a) doing so is slow,
     * and (b) it also breaks the web, which expects enumeration order to
     * follow the order in which properties are added, in certain cases.
     * Since ECMA does not specify an enumeration order for objects, both
     * behaviors are technically correct to do.
     */

    jsid* ids = props_.begin();
    size_t n = props_.length();

    RootedIdVector tmp(cx);
    if (!tmp.resize(n)) {
      return false;
    }
    PodCopy(tmp.begin(), ids, n);

    if (!MergeSort(ids, n, tmp.begin(), SortComparatorIds(cx))) {
      return false;
    }
  }
#endif

  return true;
}

JS_PUBLIC_API bool js::GetPropertyKeys(JSContext* cx, HandleObject obj,
                                       unsigned flags,
                                       MutableHandleIdVector props) {
  uint32_t validFlags =
      flags & (JSITER_OWNONLY | JSITER_HIDDEN | JSITER_SYMBOLS |
               JSITER_SYMBOLSONLY | JSITER_PRIVATE);

  PropertyEnumerator enumerator(cx, obj, validFlags, props);
  return enumerator.snapshot(cx);
}

static inline void RegisterEnumerator(JSContext* cx, NativeIterator* ni,
                                      HandleObject obj) {
  ni->initObjectBeingIterated(*obj);

  // Register non-escaping native enumerators (for-in) with the current
  // context.
  ni->link(cx->compartment()->enumeratorsAddr());

  MOZ_ASSERT(!ni->isActive());
  ni->markActive();
}

static PropertyIteratorObject* NewPropertyIteratorObject(JSContext* cx) {
  const JSClass* clasp = &PropertyIteratorObject::class_;
  Rooted<SharedShape*> shape(
      cx,
      SharedShape::getInitialShape(cx, clasp, cx->realm(), TaggedProto(nullptr),
                                   ITERATOR_FINALIZE_KIND));
  if (!shape) {
    return nullptr;
  }

  auto* res = NativeObject::create<PropertyIteratorObject>(
      cx, ITERATOR_FINALIZE_KIND, GetInitialHeap(GenericObject, clasp), shape);
  if (!res) {
    return nullptr;
  }

  // CodeGenerator::visitIteratorStartO assumes the iterator object is not
  // inside the nursery when deciding whether a barrier is necessary.
  MOZ_ASSERT(!js::gc::IsInsideNursery(res));
  return res;
}

static inline size_t NumTrailingBytes(size_t propertyCount,
                                      size_t protoShapeCount, bool hasIndices) {
  static_assert(alignof(IteratorProperty) <= alignof(NativeIterator));
  static_assert(alignof(GCPtr<Shape*>) <= alignof(IteratorProperty));
  static_assert(alignof(PropertyIndex) <= alignof(GCPtr<Shape*>));
  size_t result = propertyCount * sizeof(IteratorProperty) +
                  protoShapeCount * sizeof(GCPtr<Shape*>);
  if (hasIndices) {
    result += propertyCount * sizeof(PropertyIndex);
    if constexpr (sizeof(PropertyIndex) != alignof(GCPtr<Shape*>)) {
      result = AlignBytes(result, alignof(GCPtr<Shape*>));
    }
  }
  return result;
}

static inline size_t AllocationSize(size_t propertyCount,
                                    size_t protoShapeCount, bool hasIndices) {
  return sizeof(NativeIterator) +
         NumTrailingBytes(propertyCount, protoShapeCount, hasIndices);
}

static PropertyIteratorObject* CreatePropertyIterator(
    JSContext* cx, Handle<JSObject*> objBeingIterated, HandleIdVector props,
    bool supportsIndices, PropertyIndexVector* indices,
    uint32_t cacheableProtoChainLength, uint32_t ownPropertyCount,
    bool forObjectKeys) {
  MOZ_ASSERT_IF(indices, supportsIndices);
  if (props.length() >= NativeIterator::PropCountLimit) {
    ReportAllocationOverflow(cx);
    return nullptr;
  }

  bool hasIndices = !!indices;

  // If the iterator is cacheable, we store the shape of each object
  // along the proto chain in the iterator. If the iterator is not
  // cacheable, but has indices, then we store one shape (the shape of
  // the object being iterated.)
  uint32_t numShapes = cacheableProtoChainLength;
  if (numShapes == 0 && hasIndices) {
    numShapes = 1;
  }
  if (numShapes > NativeIterator::ShapeCountLimit) {
    ReportAllocationOverflow(cx);
    return nullptr;
  }
  uint32_t numProtoShapes = numShapes > 0 ? numShapes - 1 : 0;

  Rooted<PropertyIteratorObject*> propIter(cx, NewPropertyIteratorObject(cx));
  if (!propIter) {
    return nullptr;
  }

  void* mem = cx->pod_malloc_with_extra<NativeIterator, uint8_t>(
      NumTrailingBytes(props.length(), numProtoShapes, hasIndices));
  if (!mem) {
    return nullptr;
  }

  // This also registers |ni| with |propIter|.
  bool hadError = false;
  new (mem) NativeIterator(cx, propIter, objBeingIterated, props,
                           supportsIndices, indices, numShapes,
                           ownPropertyCount, forObjectKeys, &hadError);
  if (hadError) {
    return nullptr;
  }

  return propIter;
}

static HashNumber HashIteratorShape(Shape* shape) {
  return DefaultHasher<Shape*>::hash(shape);
}

/**
 * Initialize a fresh NativeIterator.
 *
 * This definition is a bit tricky: some parts of initializing are fallible, so
 * as we initialize, we must carefully keep this in GC-safe state (see
 * NativeIterator::trace).
 */
NativeIterator::NativeIterator(JSContext* cx,
                               Handle<PropertyIteratorObject*> propIter,
                               Handle<JSObject*> objBeingIterated,
                               HandleIdVector props, bool supportsIndices,
                               PropertyIndexVector* indices, uint32_t numShapes,
                               uint32_t ownPropertyCount, bool forObjectKeys,
                               bool* hadError)
    : objectBeingIterated_(nullptr),
      iterObj_(propIter),
      objShape_(numShapes > 0 ? objBeingIterated->shape() : nullptr),
      // This holds the allocated property count until we're done with
      // initialization
      propertyCursor_(props.length()),
      ownPropertyCount_(ownPropertyCount),
      shapesHash_(0) {
  // If there are shapes, the object and all objects on its prototype chain must
  // be native objects. See CanCompareIterableObjectToCache.
  MOZ_ASSERT_IF(numShapes > 0,
                objBeingIterated && objBeingIterated->is<NativeObject>());

  MOZ_ASSERT(!*hadError);

  bool hasActualIndices = !!indices;
  MOZ_ASSERT_IF(hasActualIndices, indices->length() == props.length());

  if (hasActualIndices) {
    flags_ |= Flags::IndicesAllocated;
  } else if (supportsIndices) {
    flags_ |= Flags::IndicesSupported;
  }

  if (forObjectKeys) {
    flags_ |= Flags::OwnPropertiesOnly;
  }

  // NOTE: This must be done first thing: The caller can't free `this` on error
  //       because it has GCPtr fields whose barriers have already fired; the
  //       store buffer has pointers to them. Only the GC can free `this` (via
  //       PropertyIteratorObject::finalize).
  propIter->initNativeIterator(this);

  // The GC asserts on finalization that `this->allocationSize()` matches the
  // `nbytes` passed to `AddCellMemory`. So once these lines run, we must make
  // `this->allocationSize()` correct. That means infallibly initializing the
  // shapes, and ensuring that indicesState_.allocated() is true if we've
  // allocated space for indices. It's OK for the constructor to fail after
  // that.
  size_t nbytes = AllocationSize(
      props.length(), numShapes > 0 ? numShapes - 1 : 0, hasActualIndices);
  AddCellMemory(propIter, nbytes, MemoryUse::NativeIterator);

  if (numShapes > 0) {
    // Construct shapes into the shapes array.  Also compute the shapesHash,
    // which incorporates Shape* addresses that could have changed during a GC
    // triggered in (among other places) |IdToString| above.
    JSObject* pobj = objBeingIterated;
    HashNumber shapesHash = 0;
    for (uint32_t i = 0; i < numShapes; i++) {
      MOZ_ASSERT(pobj->is<NativeObject>());
      Shape* shape = pobj->shape();
      if (i > 0) {
        new (protoShapesEnd()) GCPtr<Shape*>(shape);
        protoShapeCount_++;
      }
      shapesHash = mozilla::AddToHash(shapesHash, HashIteratorShape(shape));
      pobj = pobj->staticPrototype();
    }
    shapesHash_ = shapesHash;

    // There are two cases in which we need to store shapes. If this
    // iterator is cacheable, we store the shapes for the entire proto
    // chain so we can check that the cached iterator is still valid
    // (see MacroAssembler::maybeLoadIteratorFromShape). If this iterator
    // has indices, then even if it isn't cacheable we need to store the
    // shape of the iterated object itself (see IteratorHasIndicesAndBranch).
    // In the former case, assert that we're storing the entire proto chain.
    MOZ_ASSERT_IF(numShapes > 1, pobj == nullptr);
    MOZ_ASSERT(uintptr_t(protoShapesEnd()) == uintptr_t(this) + nbytes);
  }

  // Allocate any strings in the nursery until the first minor GC. After this
  // point they will end up getting tenured anyway because they are reachable
  // from |propIter| which will be tenured.
  AutoSelectGCHeap gcHeap(cx);

  bool maybeNeedGC = !gc::IsInsideNursery(propIter);
  uint64_t gcNumber = cx->runtime()->gc.gcNumber();
  size_t numProps = props.length();
  for (size_t i = 0; i < numProps; i++) {
    JSLinearString* str = IdToString(cx, props[i], gcHeap);
    if (!str) {
      *hadError = true;
      return;
    }
    uint64_t newGcNumber = cx->runtime()->gc.gcNumber();
    if (newGcNumber != gcNumber) {
      gcNumber = newGcNumber;
      maybeNeedGC = true;
    }
    // We write to our IteratorProperty children only here and in
    // PropertyIteratorObject::trace. Here we do not need a pre-barrier
    // because we are not overwriting a previous value.
    new (propertiesEnd()) IteratorProperty(str);
    propertyCount_++;
    if (maybeNeedGC && gc::IsInsideNursery(str)) {
      maybeNeedGC = false;
      cx->runtime()->gc.storeBuffer().putWholeCell(propIter);
    }
  }

  if (hasActualIndices) {
    PropertyIndex* cursor = indicesBegin();
    for (size_t i = 0; i < numProps; i++) {
      *cursor++ = (*indices)[i];
    }
    flags_ |= Flags::IndicesAvailable;
  }

  propertyCursor_ = 0;
  flags_ |= Flags::Initialized;

  MOZ_ASSERT(!*hadError);
}

inline size_t NativeIterator::allocationSize() const {
  return AllocationSize(allocatedPropertyCount(), protoShapeCount_,
                        indicesAllocated());
}

/* static */
bool IteratorHashPolicy::match(PropertyIteratorObject* obj,
                               const Lookup& lookup) {
  NativeIterator* ni = obj->getNativeIterator();
  if (ni->shapesHash() != lookup.shapesHash ||
      ni->protoShapeCount() != lookup.numProtoShapes ||
      ni->objShape() != lookup.objShape) {
    return false;
  }

  return ArrayEqual(reinterpret_cast<Shape**>(ni->protoShapesBegin()),
                    lookup.protoShapes, ni->protoShapeCount());
}

static inline bool CanCompareIterableObjectToCache(JSObject* obj) {
  if (obj->is<NativeObject>()) {
    return obj->as<NativeObject>().getDenseInitializedLength() == 0;
  }
  return false;
}

static bool CanStoreInIteratorCache(JSObject* obj) {
  do {
    MOZ_ASSERT(obj->as<NativeObject>().getDenseInitializedLength() == 0);

    // Typed arrays have indexed properties not captured by the Shape guard.
    // Enumerate hooks may add extra properties.
    if (MOZ_UNLIKELY(ClassCanHaveExtraEnumeratedProperties(obj->getClass()))) {
      return false;
    }

    obj = obj->staticPrototype();
  } while (obj);

  return true;
}

static MOZ_ALWAYS_INLINE PropertyIteratorObject* LookupInShapeIteratorCache(
    JSContext* cx, JSObject* obj, uint32_t* cacheableProtoChainLength,
    bool exclusive) {
  if (!obj->shape()->cache().isIterator() ||
      !CanCompareIterableObjectToCache(obj)) {
    return nullptr;
  }
  PropertyIteratorObject* iterobj = obj->shape()->cache().toIterator();
  NativeIterator* ni = iterobj->getNativeIterator();
  MOZ_ASSERT(ni->objShape() == obj->shape());
  if (exclusive && !ni->isReusable()) {
    return nullptr;
  }

  // Verify shapes of proto chain.
  JSObject* pobj = obj;
  for (GCPtr<Shape*>* s = ni->protoShapesBegin(); s != ni->protoShapesEnd();
       s++) {
    Shape* shape = *s;
    pobj = pobj->staticPrototype();
    if (pobj->shape() != shape) {
      return nullptr;
    }
    if (!CanCompareIterableObjectToCache(pobj)) {
      return nullptr;
    }
  }
  MOZ_ASSERT(CanStoreInIteratorCache(obj));
  *cacheableProtoChainLength = ni->objShape() ? ni->protoShapeCount() + 1 : 0;
  return iterobj;
}

static MOZ_ALWAYS_INLINE PropertyIteratorObject* LookupInIteratorCache(
    JSContext* cx, JSObject* obj, uint32_t* cacheableProtoChainLength,
    bool exclusive) {
  MOZ_ASSERT(*cacheableProtoChainLength == 0);

  if (PropertyIteratorObject* shapeCached = LookupInShapeIteratorCache(
          cx, obj, cacheableProtoChainLength, exclusive)) {
    return shapeCached;
  }

  Vector<Shape*, 8> shapes(cx);
  HashNumber shapesHash = 0;
  JSObject* pobj = obj;
  do {
    if (!CanCompareIterableObjectToCache(pobj)) {
      return nullptr;
    }

    MOZ_ASSERT(pobj->is<NativeObject>());
    Shape* shape = pobj->shape();
    shapesHash = mozilla::AddToHash(shapesHash, HashIteratorShape(shape));

    if (MOZ_UNLIKELY(!shapes.append(shape))) {
      cx->recoverFromOutOfMemory();
      return nullptr;
    }

    pobj = pobj->staticPrototype();
  } while (pobj);

  MOZ_ASSERT(!shapes.empty());
  *cacheableProtoChainLength = shapes.length();

  IteratorHashPolicy::Lookup lookup(shapes[0], shapes.begin() + 1,
                                    shapes.length() - 1, shapesHash);
  auto p = ObjectRealm::get(obj).iteratorCache.lookup(lookup);
  if (!p) {
    return nullptr;
  }

  PropertyIteratorObject* iterobj = *p;
  MOZ_ASSERT(iterobj->compartment() == cx->compartment());

  NativeIterator* ni = iterobj->getNativeIterator();
  if (exclusive && !ni->isReusable()) {
    return nullptr;
  }

  return iterobj;
}

[[nodiscard]] static bool StoreInIteratorCache(
    JSContext* cx, JSObject* obj, PropertyIteratorObject* iterobj) {
  MOZ_ASSERT(CanStoreInIteratorCache(obj));

  NativeIterator* ni = iterobj->getNativeIterator();
  MOZ_ASSERT(ni->objShape());

  obj->shape()->maybeCacheIterator(cx, iterobj);

  IteratorHashPolicy::Lookup lookup(
      ni->objShape(), reinterpret_cast<Shape**>(ni->protoShapesBegin()),
      ni->protoShapeCount(), ni->shapesHash());

  ObjectRealm::IteratorCache& cache = ObjectRealm::get(obj).iteratorCache;
  bool ok;
  auto p = cache.lookupForAdd(lookup);
  if (MOZ_LIKELY(!p)) {
    ok = cache.add(p, iterobj);
  } else {
    // If we weren't able to use an existing cached iterator, just
    // replace it.
    cache.remove(p);
    ok = cache.relookupOrAdd(p, lookup, iterobj);
  }
  if (!ok) {
    ReportOutOfMemory(cx);
    return false;
  }

  return true;
}

bool js::EnumerateProperties(JSContext* cx, HandleObject obj,
                             MutableHandleIdVector props) {
  MOZ_ASSERT(props.empty());

  if (MOZ_UNLIKELY(obj->is<ProxyObject>())) {
    return Proxy::enumerate(cx, obj, props);
  }

  uint32_t flags = 0;
  PropertyEnumerator enumerator(cx, obj, flags, props);
  return enumerator.snapshot(cx);
}

#ifdef DEBUG
static bool IndicesAreValid(NativeObject* obj, NativeIterator* ni) {
  MOZ_ASSERT(ni->indicesAvailable());
  size_t numDenseElements = obj->getDenseInitializedLength();
  size_t numFixedSlots = obj->numFixedSlots();
  const Value* elements = obj->getDenseElements();

  IteratorProperty* keys = ni->propertiesBegin();
  PropertyIndex* indices = ni->indicesBegin();

  for (uint32_t i = 0; i < ni->numKeys(); i++) {
    PropertyIndex index = indices[i];
    switch (index.kind()) {
      case PropertyIndex::Kind::Element:
        // Verify that the dense element exists and is not a hole.
        if (index.index() >= numDenseElements ||
            elements[index.index()].isMagic(JS_ELEMENTS_HOLE)) {
          return false;
        }
        break;
      case PropertyIndex::Kind::FixedSlot: {
        // Verify that the slot exists and is an enumerable data property with
        // the expected key.
        Maybe<PropertyInfo> prop =
            obj->lookupPure(AtomToId(&keys[i].asString()->asAtom()));
        if (!prop.isSome() || !prop->hasSlot() || !prop->enumerable() ||
            !prop->isDataProperty() || prop->slot() != index.index()) {
          return false;
        }
        break;
      }
      case PropertyIndex::Kind::DynamicSlot: {
        // Verify that the slot exists and is an enumerable data property with
        // the expected key.
        Maybe<PropertyInfo> prop =
            obj->lookupPure(AtomToId(&keys[i].asString()->asAtom()));
        if (!prop.isSome() || !prop->hasSlot() || !prop->enumerable() ||
            !prop->isDataProperty() ||
            prop->slot() - numFixedSlots != index.index()) {
          return false;
        }
        break;
      }
      case PropertyIndex::Kind::Invalid:
        return false;
    }
  }
  return true;
}
#endif

static PropertyIteratorObject* GetIteratorImpl(JSContext* cx, HandleObject obj,
                                               bool wantIndices,
                                               bool forObjectKeys) {
  MOZ_ASSERT(!obj->is<PropertyIteratorObject>());
  MOZ_ASSERT(cx->compartment() == obj->compartment(),
             "We may end up allocating shapes in the wrong zone!");

  uint32_t cacheableProtoChainLength = 0;
  if (PropertyIteratorObject* iterobj = LookupInIteratorCache(
          cx, obj, &cacheableProtoChainLength, !forObjectKeys)) {
    NativeIterator* ni = iterobj->getNativeIterator();
    bool recreateWithIndices = wantIndices && ni->indicesSupported();
    bool recreateWithProtoProperties =
        !forObjectKeys && ni->ownPropertiesOnly();
    if (!recreateWithIndices && !recreateWithProtoProperties) {
      MOZ_ASSERT_IF(wantIndices && ni->indicesAvailable(),
                    IndicesAreValid(&obj->as<NativeObject>(), ni));
      if (!forObjectKeys) {
        RegisterEnumerator(cx, ni, obj);
      }
      return iterobj;
    }
    // We don't want to get in a pattern where an Object.keys + indices
    // use case clobbers us because it wants indices, and then we clobber
    // it because we want prototype keys. This prevents that.
    if (!recreateWithIndices && ni->indicesAvailable()) {
      wantIndices = true;
    }
  }

  if (cacheableProtoChainLength > 0 && !CanStoreInIteratorCache(obj)) {
    cacheableProtoChainLength = 0;
  }
  if (cacheableProtoChainLength > NativeIterator::ShapeCountLimit) {
    cacheableProtoChainLength = 0;
  }

  RootedIdVector keys(cx);
  PropertyIndexVector indices(cx);
  bool supportsIndices = false;
  uint32_t ownPropertyCount = 0;

  if (MOZ_UNLIKELY(obj->is<ProxyObject>())) {
    if (!Proxy::enumerate(cx, obj, &keys)) {
      return nullptr;
    }
  } else {
    PropertyEnumerator enumerator(cx, obj, /*flags*/ 0, &keys, &indices);
    enumerator.setForObjectKeys(forObjectKeys);
    if (!enumerator.snapshot(cx)) {
      return nullptr;
    }
    supportsIndices = enumerator.supportsIndices();
    ownPropertyCount = enumerator.ownPropertyCount();
    MOZ_ASSERT_IF(wantIndices && supportsIndices,
                  keys.length() == indices.length());
  }

  // If the object has dense elements, mark the dense elements as
  // maybe-in-iteration. However if this is for Object.keys, we're not able to
  // do the appropriate invalidations on deletion etc. anyway. Accordingly,
  // we're forced to just disable the indices optimization for this iterator
  // entirely.
  //
  // The iterator is a snapshot so if indexed properties are added after this
  // point we don't need to do anything. However, the object might have sparse
  // elements now that can be densified later. To account for this, we set the
  // maybe-in-iteration flag also in NativeObject::maybeDensifySparseElements.
  //
  // In debug builds, AssertDenseElementsNotIterated is used to check the flag
  // is set correctly.
  if (obj->is<NativeObject>() &&
      obj->as<NativeObject>().getDenseInitializedLength() > 0) {
    if (forObjectKeys) {
      supportsIndices = false;
    } else {
      obj->as<NativeObject>().markDenseElementsMaybeInIteration();
    }
  }

  PropertyIndexVector* indicesPtr =
      wantIndices && supportsIndices ? &indices : nullptr;
  PropertyIteratorObject* iterobj = CreatePropertyIterator(
      cx, obj, keys, supportsIndices, indicesPtr, cacheableProtoChainLength,
      ownPropertyCount, forObjectKeys);
  if (!iterobj) {
    return nullptr;
  }
  if (!forObjectKeys) {
    RegisterEnumerator(cx, iterobj->getNativeIterator(), obj);
  }

  cx->check(iterobj);
  MOZ_ASSERT_IF(
      wantIndices && supportsIndices,
      IndicesAreValid(&obj->as<NativeObject>(), iterobj->getNativeIterator()));

#ifdef DEBUG
  if (obj->is<NativeObject>()) {
    if (PrototypeMayHaveIndexedProperties(&obj->as<NativeObject>())) {
      iterobj->getNativeIterator()->setMaybeHasIndexedPropertiesFromProto();
    }
  }
#endif

  // Cache the iterator object.
  if (cacheableProtoChainLength > 0) {
    if (!StoreInIteratorCache(cx, obj, iterobj)) {
      return nullptr;
    }
  }

  return iterobj;
}

PropertyIteratorObject* js::GetIterator(JSContext* cx, HandleObject obj) {
  return GetIteratorImpl(cx, obj, false, false);
}

PropertyIteratorObject* js::GetIteratorWithIndices(JSContext* cx,
                                                   HandleObject obj) {
  return GetIteratorImpl(cx, obj, true, false);
}

PropertyIteratorObject* js::GetIteratorForObjectKeys(JSContext* cx,
                                                     HandleObject obj) {
  return GetIteratorImpl(cx, obj, false, true);
}

PropertyIteratorObject* js::GetIteratorWithIndicesForObjectKeys(
    JSContext* cx, HandleObject obj) {
  return GetIteratorImpl(cx, obj, true, true);
}

PropertyIteratorObject* js::LookupInIteratorCache(JSContext* cx,
                                                  HandleObject obj) {
  uint32_t dummy = 0;
  return LookupInIteratorCache(cx, obj, &dummy, true);
}

PropertyIteratorObject* js::LookupInShapeIteratorCache(JSContext* cx,
                                                       HandleObject obj) {
  uint32_t dummy = 0;
  return LookupInShapeIteratorCache(cx, obj, &dummy, true);
}

// ES 2017 draft 7.4.7.
PlainObject* js::CreateIterResultObject(JSContext* cx, HandleValue value,
                                        bool done) {
  // Step 1 (implicit).

  // Step 2.
  Rooted<PlainObject*> templateObject(
      cx, GlobalObject::getOrCreateIterResultTemplateObject(cx));
  if (!templateObject) {
    return nullptr;
  }

  PlainObject* resultObj = PlainObject::createWithTemplate(cx, templateObject);
  if (!resultObj) {
    return nullptr;
  }

  // Step 3.
  resultObj->setSlot(GlobalObject::IterResultObjectValueSlot, value);

  // Step 4.
  resultObj->setSlot(GlobalObject::IterResultObjectDoneSlot,
                     done ? TrueHandleValue : FalseHandleValue);

  // Step 5.
  return resultObj;
}

PlainObject* GlobalObject::getOrCreateIterResultTemplateObject(JSContext* cx) {
  GCPtr<PlainObject*>& obj = cx->global()->data().iterResultTemplate;
  if (obj) {
    return obj;
  }

  PlainObject* templateObj = createIterResultTemplateObject(cx);
  obj.init(templateObj);
  return obj;
}

/* static */
PlainObject* GlobalObject::createIterResultTemplateObject(JSContext* cx) {
  // Create template plain object
  Rooted<PlainObject*> templateObject(
      cx, NewPlainObject(cx, {.newKind = TenuredObject}));
  if (!templateObject) {
    return nullptr;
  }

  // Set dummy `value` property
  if (!NativeDefineDataProperty(cx, templateObject, cx->names().value,
                                UndefinedHandleValue, JSPROP_ENUMERATE)) {
    return nullptr;
  }

  // Set dummy `done` property
  if (!NativeDefineDataProperty(cx, templateObject, cx->names().done,
                                TrueHandleValue, JSPROP_ENUMERATE)) {
    return nullptr;
  }

#ifdef DEBUG
  // Make sure that the properties are in the right slots.
  ShapePropertyIter<NoGC> iter(templateObject->shape());
  MOZ_ASSERT(iter->slot() == GlobalObject::IterResultObjectDoneSlot &&
             iter->key() == NameToId(cx->names().done));
  iter++;
  MOZ_ASSERT(iter->slot() == GlobalObject::IterResultObjectValueSlot &&
             iter->key() == NameToId(cx->names().value));
#endif

  return templateObject;
}

/*** Iterator objects *******************************************************/

size_t PropertyIteratorObject::sizeOfMisc(
    mozilla::MallocSizeOf mallocSizeOf) const {
  return mallocSizeOf(getNativeIterator());
}

void PropertyIteratorObject::trace(JSTracer* trc, JSObject* obj) {
  if (NativeIterator* ni =
          obj->as<PropertyIteratorObject>().getNativeIterator()) {
    ni->trace(trc);
  }
}

void PropertyIteratorObject::finalize(JS::GCContext* gcx, JSObject* obj) {
  if (NativeIterator* ni =
          obj->as<PropertyIteratorObject>().getNativeIterator()) {
    gcx->free_(obj, ni, ni->allocationSize(), MemoryUse::NativeIterator);
  }
}

const JSClassOps PropertyIteratorObject::classOps_ = {
    .finalize = finalize,
    .trace = trace,
};

const JSClass PropertyIteratorObject::class_ = {
    "Iterator",
    JSCLASS_HAS_RESERVED_SLOTS(SlotCount) | JSCLASS_BACKGROUND_FINALIZE,
    &PropertyIteratorObject::classOps_,
};

static const JSClass ArrayIteratorPrototypeClass = {
    "Array Iterator",
    0,
};

enum {
  ArrayIteratorSlotIteratedObject,
  ArrayIteratorSlotNextIndex,
  ArrayIteratorSlotItemKind,
  ArrayIteratorSlotCount
};
// Slot numbers must match constants used in self-hosted code.
static_assert(ArrayIteratorSlotIteratedObject == ITERATOR_SLOT_TARGET);
static_assert(ArrayIteratorSlotNextIndex == ITERATOR_SLOT_NEXT_INDEX);
static_assert(ArrayIteratorSlotItemKind == ARRAY_ITERATOR_SLOT_ITEM_KIND);

const JSClass ArrayIteratorObject::class_ = {
    "Array Iterator",
    JSCLASS_HAS_RESERVED_SLOTS(ArrayIteratorSlotCount),
};

ArrayIteratorObject* js::NewArrayIteratorTemplate(JSContext* cx) {
  RootedObject proto(
      cx, GlobalObject::getOrCreateArrayIteratorPrototype(cx, cx->global()));
  if (!proto) {
    return nullptr;
  }

  return NewObjectWithGivenProto<ArrayIteratorObject>(
      cx, proto, {.newKind = TenuredObject});
}

ArrayIteratorObject* js::NewArrayIterator(JSContext* cx) {
  RootedObject proto(
      cx, GlobalObject::getOrCreateArrayIteratorPrototype(cx, cx->global()));
  if (!proto) {
    return nullptr;
  }

  return NewObjectWithGivenProto<ArrayIteratorObject>(cx, proto);
}

static const JSFunctionSpec array_iterator_methods[] = {
    JS_SELF_HOSTED_FN("next", "ArrayIteratorNext", 0, 0),
    JS_FS_END,
};

static const JSClass StringIteratorPrototypeClass = {
    "String Iterator",
    0,
};

enum {
  StringIteratorSlotIteratedObject,
  StringIteratorSlotNextIndex,
  StringIteratorSlotCount
};
// Slot numbers must match constants used in self-hosted code.
static_assert(StringIteratorSlotIteratedObject == ITERATOR_SLOT_TARGET);
static_assert(StringIteratorSlotNextIndex == ITERATOR_SLOT_NEXT_INDEX);

const JSClass StringIteratorObject::class_ = {
    "String Iterator",
    JSCLASS_HAS_RESERVED_SLOTS(StringIteratorSlotCount),
};

static const JSFunctionSpec string_iterator_methods[] = {
    JS_SELF_HOSTED_FN("next", "StringIteratorNext", 0, 0),
    JS_FS_END,
};

StringIteratorObject* js::NewStringIteratorTemplate(JSContext* cx) {
  RootedObject proto(
      cx, GlobalObject::getOrCreateStringIteratorPrototype(cx, cx->global()));
  if (!proto) {
    return nullptr;
  }

  return NewObjectWithGivenProto<StringIteratorObject>(
      cx, proto, {.newKind = TenuredObject});
}

StringIteratorObject* js::NewStringIterator(JSContext* cx) {
  RootedObject proto(
      cx, GlobalObject::getOrCreateStringIteratorPrototype(cx, cx->global()));
  if (!proto) {
    return nullptr;
  }

  return NewObjectWithGivenProto<StringIteratorObject>(cx, proto);
}

static const JSClass RegExpStringIteratorPrototypeClass = {
    "RegExp String Iterator",
    0,
};

enum {
  // The regular expression used for iteration. May hold the original RegExp
  // object when it is reused instead of a new RegExp object.
  RegExpStringIteratorSlotRegExp,

  // The String value being iterated upon.
  RegExpStringIteratorSlotString,

  // The source string of the original RegExp object. Used to validate we can
  // reuse the original RegExp object for matching.
  RegExpStringIteratorSlotSource,

  // The flags of the original RegExp object.
  RegExpStringIteratorSlotFlags,

  // When non-negative, this slot holds the current lastIndex position when
  // reusing the original RegExp object for matching. When set to |-1|, the
  // iterator has finished. When set to any other negative value, the
  // iterator is not yet exhausted and we're not on the fast path and we're
  // not reusing the input RegExp object.
  RegExpStringIteratorSlotLastIndex,

  RegExpStringIteratorSlotCount
};

static_assert(RegExpStringIteratorSlotRegExp ==
                  REGEXP_STRING_ITERATOR_REGEXP_SLOT,
              "RegExpStringIteratorSlotRegExp must match self-hosting define "
              "for regexp slot.");
static_assert(RegExpStringIteratorSlotString ==
                  REGEXP_STRING_ITERATOR_STRING_SLOT,
              "RegExpStringIteratorSlotString must match self-hosting define "
              "for string slot.");
static_assert(RegExpStringIteratorSlotSource ==
                  REGEXP_STRING_ITERATOR_SOURCE_SLOT,
              "RegExpStringIteratorSlotString must match self-hosting define "
              "for source slot.");
static_assert(RegExpStringIteratorSlotFlags ==
                  REGEXP_STRING_ITERATOR_FLAGS_SLOT,
              "RegExpStringIteratorSlotFlags must match self-hosting define "
              "for flags slot.");
static_assert(RegExpStringIteratorSlotLastIndex ==
                  REGEXP_STRING_ITERATOR_LASTINDEX_SLOT,
              "RegExpStringIteratorSlotLastIndex must match self-hosting "
              "define for lastIndex slot.");

const JSClass RegExpStringIteratorObject::class_ = {
    "RegExp String Iterator",
    JSCLASS_HAS_RESERVED_SLOTS(RegExpStringIteratorSlotCount),
};

static const JSFunctionSpec regexp_string_iterator_methods[] = {
    JS_SELF_HOSTED_FN("next", "RegExpStringIteratorNext", 0, 0),

    JS_FS_END,
};

RegExpStringIteratorObject* js::NewRegExpStringIteratorTemplate(JSContext* cx) {
  RootedObject proto(cx, GlobalObject::getOrCreateRegExpStringIteratorPrototype(
                             cx, cx->global()));
  if (!proto) {
    return nullptr;
  }

  return NewObjectWithGivenProto<RegExpStringIteratorObject>(
      cx, proto, {.newKind = TenuredObject});
}

RegExpStringIteratorObject* js::NewRegExpStringIterator(JSContext* cx) {
  RootedObject proto(cx, GlobalObject::getOrCreateRegExpStringIteratorPrototype(
                             cx, cx->global()));
  if (!proto) {
    return nullptr;
  }

  return NewObjectWithGivenProto<RegExpStringIteratorObject>(cx, proto);
}

#ifdef NIGHTLY_BUILD
static const JSClass IteratorRangePrototypeClass = {
    "Numeric Range Iterator",
    0,
};

enum {
  IteratorRangeSlotStart,
  IteratorRangeSlotEnd,
  IteratorRangeSlotStep,
  IteratorRangeSlotInclusiveEnd,
  IteratorRangeSlotZero,
  IteratorRangeSlotOne,
  IteratorRangeSlotCurrentCount,
  IteratorRangeSlotCount
};

// slot numbers must match constants used in self-hosted code
static_assert(IteratorRangeSlotStart == ITERATOR_RANGE_SLOT_START);
static_assert(IteratorRangeSlotEnd == ITERATOR_RANGE_SLOT_END);
static_assert(IteratorRangeSlotStep == ITERATOR_RANGE_SLOT_STEP);
static_assert(IteratorRangeSlotInclusiveEnd ==
              ITERATOR_RANGE_SLOT_INCLUSIVE_END);
static_assert(IteratorRangeSlotZero == ITERATOR_RANGE_SLOT_ZERO);
static_assert(IteratorRangeSlotOne == ITERATOR_RANGE_SLOT_ONE);
static_assert(IteratorRangeSlotCurrentCount ==
              ITERATOR_RANGE_SLOT_CURRENT_COUNT);

static const JSFunctionSpec iterator_range_methods[] = {
    JS_SELF_HOSTED_FN("next", "IteratorRangeNext", 0, 0),
    JS_FS_END,
};

IteratorRangeObject* js::NewIteratorRange(JSContext* cx) {
  RootedObject proto(
      cx, GlobalObject::getOrCreateIteratorRangePrototype(cx, cx->global()));
  if (!proto) {
    return nullptr;
  }

  return NewObjectWithGivenProto<IteratorRangeObject>(cx, proto);
}
#endif

// static
PropertyIteratorObject* GlobalObject::getOrCreateEmptyIterator(JSContext* cx) {
  if (!cx->global()->data().emptyIterator) {
    RootedIdVector props(cx);  // Empty
    PropertyIteratorObject* iter =
        CreatePropertyIterator(cx, nullptr, props, false, nullptr, 0, 0, false);
    if (!iter) {
      return nullptr;
    }
    iter->getNativeIterator()->markEmptyIteratorSingleton();
    cx->global()->data().emptyIterator.init(iter);
  }
  return cx->global()->data().emptyIterator;
}

PropertyIteratorObject* js::ValueToIterator(JSContext* cx, HandleValue vp) {
  RootedObject obj(cx);
  if (vp.isObject()) {
    /* Common case. */
    obj = &vp.toObject();
  } else if (vp.isNullOrUndefined()) {
    /*
     * Enumerating over null and undefined gives an empty enumerator, so
     * that |for (var p in <null or undefined>) <loop>;| never executes
     * <loop>, per ES5 12.6.4.
     */
    return GlobalObject::getOrCreateEmptyIterator(cx);
  } else {
    obj = ToObject(cx, vp);
    if (!obj) {
      return nullptr;
    }
  }

  return GetIterator(cx, obj);
}

void js::CloseIterator(JSObject* obj) {
  if (!obj->is<PropertyIteratorObject>()) {
    return;
  }

  // Remove iterator from the active list, which is a stack. The shared iterator
  // used for for-in with null/undefined is immutable and unlinked.

  NativeIterator* ni = obj->as<PropertyIteratorObject>().getNativeIterator();
  if (ni->isEmptyIteratorSingleton()) {
    return;
  }

  ni->unlink();

  MOZ_ASSERT(ni->isActive());
  ni->markInactive();

  ni->clearObjectBeingIterated();

  // Reset the enumerator; it may still be in the cached iterators for
  // this thread and can be reused.
  ni->resetPropertyCursorForReuse();
}

bool js::IteratorCloseForException(JSContext* cx, HandleObject obj) {
  MOZ_ASSERT(cx->isExceptionPending());

  // Closing an iterator is implemented as an exception.
  bool isClosingGenerator = cx->isClosingGenerator();

  // Save the current exception state. This implicitly clears any pending
  // exception, so it needs to happen after calling |cx->isClosingGenerator()|.
  // The destructor restores the saved exception state, unless there's a new
  // pending exception.
  JS::AutoSaveExceptionState savedExc(cx);

  // CloseIterOperation when called with |CompletionKind::Throw| clears any
  // pending exception, so the previously stored exception in |savedExc| is
  // correctly restored.
  // When called with |CompletionKind::Return|, pending exceptions aren't
  // cleared, so the "generator closing" exception state in |savedExc| is only
  // restored if there isn't a new pending exception.
  auto completionKind =
      isClosingGenerator ? CompletionKind::Return : CompletionKind::Throw;
  return CloseIterOperation(cx, obj, completionKind);
}

void js::UnwindIteratorForUncatchableException(JSObject* obj) {
  if (obj->is<PropertyIteratorObject>()) {
    NativeIterator* ni = obj->as<PropertyIteratorObject>().getNativeIterator();
    if (ni->isEmptyIteratorSingleton()) {
      return;
    }
    ni->unlink();
  }
}

static bool SuppressDeletedProperty(JSContext* cx, NativeIterator* ni,
                                    HandleObject obj,
                                    Handle<JSLinearString*> str) {
  if (ni->objectBeingIterated() != obj) {
    return true;
  }

  ni->disableIndices();

  // Optimization for the following common case:
  //
  //    for (var p in o) {
  //        delete o[p];
  //    }
  //
  // Note that usually both strings will be atoms so we only check for pointer
  // equality here.
  if (ni->previousPropertyWas(str)) {
    return true;
  }

  // Check whether id is still to come.
  IteratorProperty* cursor = ni->nextProperty();
  for (; cursor < ni->propertiesEnd(); ++cursor) {
    JSLinearString* idStr = cursor->asString();
    // Common case: both strings are atoms.
    if (idStr->isAtom() && str->isAtom()) {
      if (idStr != str) {
        continue;
      }
    } else {
      if (!EqualStrings(idStr, str)) {
        continue;
      }
    }

    // Check whether another property along the prototype chain became
    // visible as a result of this deletion.
    //
    // Use pure lookups to avoid re-entrancy: proxy traps can run arbitrary JS
    // that may close iterators and modify the iterator list we're currently
    // traversing in SuppressDeletedPropertyHelper. If pure lookup is not
    // possible (e.g. the object is a proxy with a dynamic prototype, or the
    // object has a resolve hook that might resolve this property), we
    // conservatively suppress the property.
    //
    // Note that the spec does not precisely define the observable behavior of
    // property deletion during for-in.
    // See https://tc39.es/ecma262/#sec-enumerate-object-properties
    if (obj->hasStaticPrototype()) {
      JSObject* proto = obj->staticPrototype();
      if (proto) {
        JSAtom* atom = AtomizeString(cx, str);
        if (!atom) {
          return false;
        }
        PropertyKey key = AtomToId(atom);
        NativeObject* holder = nullptr;
        PropertyResult prop;
        if (LookupPropertyPure(cx, proto, key, &holder, &prop) &&
            prop.isFound()) {
          // If deletion just made something up the chain visible, no need to
          // do anything.
          JS::PropertyAttributes attrs = GetPropertyAttributes(holder, prop);
          if (attrs.enumerable()) {
            return true;
          }
        }
      }
    }

    cursor->markDeleted();
    ni->markHasUnvisitedPropertyDeletion();
    return true;
  }

  return true;
}

/*
 * Suppress enumeration of deleted properties. This function must be called
 * when a property is deleted and there might be active enumerators.
 *
 * We maintain a list of active non-escaping for-in enumerators. To suppress
 * a property, we check whether each active enumerator contains the (obj, id)
 * pair and has not yet enumerated |id|. If so, and |id| is the next property,
 * we simply advance the cursor. Otherwise, we delete |id| from the list.
 *
 * We do not suppress enumeration of a property deleted along an object's
 * prototype chain. Only direct deletions on the object are handled.
 */
static bool SuppressDeletedPropertyHelper(JSContext* cx, HandleObject obj,
                                          Handle<JSLinearString*> str) {
  NativeIteratorListIter iter(obj->compartment()->enumeratorsAddr());
  while (!iter.done()) {
    NativeIterator* ni = iter.next();
    if (!SuppressDeletedProperty(cx, ni, obj, str)) {
      return false;
    }
  }

  return true;
}

bool js::SuppressDeletedProperty(JSContext* cx, HandleObject obj, jsid id) {
  if (MOZ_LIKELY(!obj->compartment()->objectMaybeInIteration(obj))) {
    return true;
  }

  if (id.isSymbol()) {
    return true;
  }

  Rooted<JSLinearString*> str(cx, IdToString(cx, id));
  if (!str) {
    return false;
  }
  return SuppressDeletedPropertyHelper(cx, obj, str);
}

bool js::SuppressDeletedElement(JSContext* cx, HandleObject obj,
                                uint32_t index) {
  if (MOZ_LIKELY(!obj->compartment()->objectMaybeInIteration(obj))) {
    return true;
  }

  RootedId id(cx);
  if (!IndexToId(cx, index, &id)) {
    return false;
  }

  Rooted<JSLinearString*> str(cx, IdToString(cx, id));
  if (!str) {
    return false;
  }
  return SuppressDeletedPropertyHelper(cx, obj, str);
}

#ifdef DEBUG
void js::AssertDenseElementsNotIterated(NativeObject* obj) {
  // Search for active iterators for |obj| and assert they don't contain any
  // property keys that are dense elements. This is used to check correctness
  // of the MAYBE_IN_ITERATION flag on ObjectElements.
  //
  // Ignore iterators that may contain indexed properties from objects on the
  // prototype chain, as that can result in false positives. See bug 1656744.

  // Limit the number of properties we check to avoid slowing down debug builds
  // too much.
  static constexpr uint32_t MaxPropsToCheck = 10;
  uint32_t propsChecked = 0;

  NativeIteratorListIter iter(obj->compartment()->enumeratorsAddr());
  while (!iter.done()) {
    NativeIterator* ni = iter.next();
    if (ni->objectBeingIterated() == obj &&
        !ni->maybeHasIndexedPropertiesFromProto()) {
      for (IteratorProperty* idp = ni->nextProperty();
           idp < ni->propertiesEnd(); ++idp) {
        uint32_t index;
        if (idp->asString()->isIndex(&index)) {
          MOZ_ASSERT(!obj->containsDenseElement(index));
        }
        if (++propsChecked > MaxPropsToCheck) {
          return;
        }
      }
    }
  }
}
#endif

static const JSFunctionSpec iterator_static_methods[] = {
    JS_SELF_HOSTED_FN("from", "IteratorFrom", 1, 0),
    JS_SELF_HOSTED_FN("concat", "IteratorConcat", 0, 0),
#ifdef NIGHTLY_BUILD
    JS_SELF_HOSTED_FN("range", "IteratorRange", 3, 0),
#endif
    JS_SELF_HOSTED_FN("zip", "IteratorZip", 2, 0),
    JS_SELF_HOSTED_FN("zipKeyed", "IteratorZipKeyed", 2, 0),
    JS_FS_END,
};

// These methods are only attached to Iterator.prototype when the
// Iterator Helpers feature is enabled.
static const JSFunctionSpec iterator_methods[] = {
    JS_SELF_HOSTED_FN("map", "IteratorMap", 1, 0),
    JS_SELF_HOSTED_FN("filter", "IteratorFilter", 1, 0),
    JS_SELF_HOSTED_FN("take", "IteratorTake", 1, 0),
    JS_SELF_HOSTED_FN("drop", "IteratorDrop", 1, 0),
    JS_SELF_HOSTED_FN("flatMap", "IteratorFlatMap", 1, 0),
    JS_SELF_HOSTED_FN("reduce", "IteratorReduce", 1, 0),
    JS_SELF_HOSTED_FN("toArray", "IteratorToArray", 0, 0),
    JS_SELF_HOSTED_FN("forEach", "IteratorForEach", 1, 0),
    JS_SELF_HOSTED_FN("some", "IteratorSome", 1, 0),
    JS_SELF_HOSTED_FN("every", "IteratorEvery", 1, 0),
    JS_SELF_HOSTED_FN("find", "IteratorFind", 1, 0),
    JS_SELF_HOSTED_FN("includes", "IteratorIncludes", 2, 0),
    JS_SELF_HOSTED_FN("join", "IteratorJoin", 1, 0),
    JS_SELF_HOSTED_FN("chunks", "IteratorChunks", 1, 0),
    JS_SELF_HOSTED_FN("windows", "IteratorWindows", 2, 0),
    JS_SELF_HOSTED_SYM_FN(iterator, "IteratorIdentity", 0, 0),
#ifdef ENABLE_EXPLICIT_RESOURCE_MANAGEMENT
    JS_SELF_HOSTED_SYM_FN(dispose, "IteratorDispose", 0, 0),
#endif
    JS_FS_END,
};

// https://tc39.es/proposal-iterator-helpers/#sec-SetterThatIgnoresPrototypeProperties
static bool SetterThatIgnoresPrototypeProperties(JSContext* cx,
                                                 Handle<Value> thisv,
                                                 Handle<PropertyKey> prop,
                                                 Handle<Value> value) {
  // Step 1.
  Rooted<JSObject*> thisObj(cx,
                            RequireObject(cx, JSMSG_OBJECT_REQUIRED, thisv));
  if (!thisObj) {
    return false;
  }

  // Step 2.
  JSObject* home = GlobalObject::getOrCreateIteratorPrototype(cx, cx->global());
  if (!home) {
    return false;
  }
  if (thisObj == home) {
    UniqueChars propName =
        IdToPrintableUTF8(cx, prop, IdToPrintableBehavior::IdIsPropertyKey);
    if (!propName) {
      return false;
    }

    // Step 2.b.
    JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr, JSMSG_READ_ONLY,
                              propName.get());
    return false;
  }

  // Step 3.
  Rooted<Maybe<PropertyDescriptor>> desc(cx);
  if (!GetOwnPropertyDescriptor(cx, thisObj, prop, &desc)) {
    return false;
  }

  // Step 4.
  if (desc.isNothing()) {
    // Step 4.a.
    return DefineDataProperty(cx, thisObj, prop, value, JSPROP_ENUMERATE);
  }

  // Step 5.
  return SetProperty(cx, thisObj, prop, value);
}

// https://tc39.es/proposal-iterator-helpers/#sec-get-iteratorprototype-@@tostringtag
static bool toStringTagGetter(JSContext* cx, unsigned argc, Value* vp) {
  CallArgs args = CallArgsFromVp(argc, vp);

  // Step 1.
  args.rval().setString(cx->names().Iterator);
  return true;
}

// https://tc39.es/proposal-iterator-helpers/#sec-set-iteratorprototype-@@tostringtag
static bool toStringTagSetter(JSContext* cx, unsigned argc, Value* vp) {
  CallArgs args = CallArgsFromVp(argc, vp);

  // Step 1.
  Rooted<PropertyKey> prop(
      cx, PropertyKey::Symbol(cx->wellKnownSymbols().toStringTag));
  if (!SetterThatIgnoresPrototypeProperties(cx, args.thisv(), prop,
                                            args.get(0))) {
    return false;
  }

  // Step 2.
  args.rval().setUndefined();
  return true;
}

// https://tc39.es/proposal-iterator-helpers/#sec-get-iteratorprototype-constructor
static bool constructorGetter(JSContext* cx, unsigned argc, Value* vp) {
  CallArgs args = CallArgsFromVp(argc, vp);

  // Step 1.
  JSObject* constructor =
      GlobalObject::getOrCreateConstructor(cx, JSProto_Iterator);
  if (!constructor) {
    return false;
  }
  args.rval().setObject(*constructor);
  return true;
}

// https://tc39.es/proposal-iterator-helpers/#sec-set-iteratorprototype-constructor
static bool constructorSetter(JSContext* cx, unsigned argc, Value* vp) {
  CallArgs args = CallArgsFromVp(argc, vp);

  // Step 1.
  Rooted<PropertyKey> prop(cx, NameToId(cx->names().constructor));
  if (!SetterThatIgnoresPrototypeProperties(cx, args.thisv(), prop,
                                            args.get(0))) {
    return false;
  }

  // Step 2.
  args.rval().setUndefined();
  return true;
}

static const JSPropertySpec iterator_properties[] = {
    // NOTE: Contrary to most other @@toStringTag properties, this property
    // has a special setter (and a getter).
    JS_SYM_GETSET(toStringTag, toStringTagGetter, toStringTagSetter, 0),
    JS_PS_END,
};

/* static */
template <GlobalObject::ProtoKind Kind, const JSClass* ProtoClass,
          const JSFunctionSpec* Methods, const bool needsFuseProperty>
bool GlobalObject::initObjectIteratorProto(JSContext* cx,
                                           Handle<GlobalObject*> global,
                                           Handle<JSAtom*> tag) {
  if (global->hasBuiltinProto(Kind)) {
    return true;
  }

  RootedObject iteratorProto(
      cx, GlobalObject::getOrCreateIteratorPrototype(cx, global));
  if (!iteratorProto) {
    return false;
  }

  RootedObject proto(cx, GlobalObject::createBlankPrototypeInheriting(
                             cx, ProtoClass, iteratorProto));
  if (!proto || !DefinePropertiesAndFunctions(cx, proto, nullptr, Methods) ||
      (tag && !DefineToStringTag(cx, proto, tag))) {
    return false;
  }

  if constexpr (needsFuseProperty) {
    if (!JSObject::setHasRealmFuseProperty(cx, proto)) {
      return false;
    }
  }

  global->initBuiltinProto(Kind, proto);
  return true;
}

/* static */
NativeObject* GlobalObject::getOrCreateArrayIteratorPrototype(
    JSContext* cx, Handle<GlobalObject*> global) {
  return MaybeNativeObject(getOrCreateBuiltinProto(
      cx, global, ProtoKind::ArrayIteratorProto,
      cx->names().Array_Iterator_.toHandle(),
      initObjectIteratorProto<
          ProtoKind::ArrayIteratorProto, &ArrayIteratorPrototypeClass,
          array_iterator_methods, /* hasFuseProperty= */ true>));
}

/* static */
JSObject* GlobalObject::getOrCreateStringIteratorPrototype(
    JSContext* cx, Handle<GlobalObject*> global) {
  return getOrCreateBuiltinProto(
      cx, global, ProtoKind::StringIteratorProto,
      cx->names().String_Iterator_.toHandle(),
      initObjectIteratorProto<ProtoKind::StringIteratorProto,
                              &StringIteratorPrototypeClass,
                              string_iterator_methods>);
}

/* static */
JSObject* GlobalObject::getOrCreateRegExpStringIteratorPrototype(
    JSContext* cx, Handle<GlobalObject*> global) {
  return getOrCreateBuiltinProto(
      cx, global, ProtoKind::RegExpStringIteratorProto,
      cx->names().RegExp_String_Iterator_.toHandle(),
      initObjectIteratorProto<ProtoKind::RegExpStringIteratorProto,
                              &RegExpStringIteratorPrototypeClass,
                              regexp_string_iterator_methods>);
}

#ifdef NIGHTLY_BUILD
/* static */
JSObject* GlobalObject::getOrCreateIteratorRangePrototype(
    JSContext* cx, Handle<GlobalObject*> global) {
  return getOrCreateBuiltinProto(
      cx, global, ProtoKind::IteratorRangeProto,
      cx->names().RegExp_String_Iterator_.toHandle(),
      initObjectIteratorProto<ProtoKind::IteratorRangeProto,
                              &IteratorRangePrototypeClass,
                              iterator_range_methods>);
}
#endif

// Iterator Helper Proposal 2.1.3.1 Iterator()
// https://tc39.es/proposal-iterator-helpers/#sec-iterator as of revision
// ed6e15a
static bool IteratorConstructor(JSContext* cx, unsigned argc, Value* vp) {
  CallArgs args = CallArgsFromVp(argc, vp);

  // Step 1.
  if (!ThrowIfNotConstructing(cx, args, "Iterator")) {
    return false;
  }
  // Throw TypeError if NewTarget is the active function object, preventing the
  // Iterator constructor from being used directly.
  if (args.callee() == args.newTarget().toObject()) {
    JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                              JSMSG_BOGUS_CONSTRUCTOR, "Iterator");
    return false;
  }

  // Step 2.
  RootedObject proto(cx);
  if (!GetPrototypeFromBuiltinConstructor(cx, args, JSProto_Iterator, &proto)) {
    return false;
  }

  JSObject* obj = NewObjectWithClassProto<IteratorObject>(cx, proto);
  if (!obj) {
    return false;
  }

  args.rval().setObject(*obj);
  return true;
}

static const ClassSpec IteratorObjectClassSpec = {
    GenericCreateConstructor<IteratorConstructor, 0, gc::AllocKind::FUNCTION>,
    GenericCreatePrototype<IteratorObject>,
    iterator_static_methods,
    nullptr,
    iterator_methods,
    iterator_properties,
    IteratorObject::finishInit,
};

const JSClass IteratorObject::class_ = {
    "Iterator",
    JSCLASS_HAS_CACHED_PROTO(JSProto_Iterator),
    JS_NULL_CLASS_OPS,
    &IteratorObjectClassSpec,
};

const JSClass IteratorObject::protoClass_ = {
    "Iterator.prototype",
    JSCLASS_HAS_CACHED_PROTO(JSProto_Iterator),
    JS_NULL_CLASS_OPS,
    &IteratorObjectClassSpec,
};

/* static */ bool IteratorObject::finishInit(JSContext* cx, HandleObject ctor,
                                             HandleObject proto) {
  Rooted<PropertyKey> id(cx, NameToId(cx->names().constructor));
  return JS_DefinePropertyById(cx, proto, id, constructorGetter,
                               constructorSetter, 0);
}

// Set up WrapForValidIteratorObject class and its prototype.
static const JSFunctionSpec wrap_for_valid_iterator_methods[] = {
    JS_SELF_HOSTED_FN("next", "WrapForValidIteratorNext", 0, 0),
    JS_SELF_HOSTED_FN("return", "WrapForValidIteratorReturn", 0, 0),
    JS_FS_END,
};

static const JSClass WrapForValidIteratorPrototypeClass = {
    "Wrap For Valid Iterator",
    0,
};

const JSClass WrapForValidIteratorObject::class_ = {
    "Wrap For Valid Iterator",
    JSCLASS_HAS_RESERVED_SLOTS(WrapForValidIteratorObject::SlotCount),
};

/* static */
NativeObject* GlobalObject::getOrCreateWrapForValidIteratorPrototype(
    JSContext* cx, Handle<GlobalObject*> global) {
  return MaybeNativeObject(getOrCreateBuiltinProto(
      cx, global, ProtoKind::WrapForValidIteratorProto,
      Handle<JSAtom*>(nullptr),
      initObjectIteratorProto<ProtoKind::WrapForValidIteratorProto,
                              &WrapForValidIteratorPrototypeClass,
                              wrap_for_valid_iterator_methods>));
}

WrapForValidIteratorObject* js::NewWrapForValidIterator(JSContext* cx) {
  RootedObject proto(cx, GlobalObject::getOrCreateWrapForValidIteratorPrototype(
                             cx, cx->global()));
  if (!proto) {
    return nullptr;
  }
  return NewObjectWithGivenProto<WrapForValidIteratorObject>(cx, proto);
}

// Common iterator object returned by Iterator Helper methods.
static const JSFunctionSpec iterator_helper_methods[] = {
    JS_SELF_HOSTED_FN("next", "IteratorHelperNext", 0, 0),
    JS_SELF_HOSTED_FN("return", "IteratorHelperReturn", 0, 0),
    JS_FS_END,
};

static const JSClass IteratorHelperPrototypeClass = {
    "Iterator Helper",
    0,
};

const JSClass IteratorHelperObject::class_ = {
    "Iterator Helper",
    JSCLASS_HAS_RESERVED_SLOTS(IteratorHelperObject::SlotCount),
};

#ifdef NIGHTLY_BUILD
const JSClass IteratorRangeObject::class_ = {
    "IteratorRange",
    JSCLASS_HAS_RESERVED_SLOTS(IteratorRangeSlotCount),
};
#endif

/* static */
NativeObject* GlobalObject::getOrCreateIteratorHelperPrototype(
    JSContext* cx, Handle<GlobalObject*> global) {
  return MaybeNativeObject(getOrCreateBuiltinProto(
      cx, global, ProtoKind::IteratorHelperProto,
      cx->names().Iterator_Helper_.toHandle(),
      initObjectIteratorProto<ProtoKind::IteratorHelperProto,
                              &IteratorHelperPrototypeClass,
                              iterator_helper_methods>));
}

IteratorHelperObject* js::NewIteratorHelper(JSContext* cx) {
  RootedObject proto(
      cx, GlobalObject::getOrCreateIteratorHelperPrototype(cx, cx->global()));
  if (!proto) {
    return nullptr;
  }
  return NewObjectWithGivenProto<IteratorHelperObject>(cx, proto);
}

ArrayObject* js::IterableToArray(JSContext* cx, HandleValue iterable) {
  JS::ForOfIterator iterator(cx);
  if (!iterator.init(iterable, JS::ForOfIterator::ThrowOnNonIterable)) {
    return nullptr;
  }

  Rooted<ArrayObject*> array(cx, NewDenseEmptyArray(cx));
  if (!array) {
    return nullptr;
  }

  RootedValue nextValue(cx);
  while (true) {
    bool done;
    if (!iterator.next(&nextValue, &done)) {
      return nullptr;
    }
    if (done) {
      break;
    }

    if (!NewbornArrayPush(cx, array, nextValue)) {
      return nullptr;
    }
  }
  return array;
}

bool js::HasOptimizableArrayIteratorPrototype(JSContext* cx) {
  // Return true if %ArrayIteratorPrototype% does not have (re)defined `next`
  // and `return` properties.
  return cx->realm()->realmFuses.optimizeArrayIteratorPrototypeFuse.intact();
}

template <MustBePacked Packed>
bool js::IsArrayWithDefaultIterator(JSObject* obj, JSContext* cx) {
  if constexpr (Packed == MustBePacked::Yes) {
    if (!IsPackedArray(obj)) {
      return false;
    }
  } else {
    if (!obj->is<ArrayObject>()) {
      return false;
    }
  }
  ArrayObject* arr = &obj->as<ArrayObject>();

  // Ensure Array.prototype[@@iterator] and %ArrayIteratorPrototype% haven't
  // been mutated in a way that affects the iterator protocol.
  if (!arr->realm()->realmFuses.optimizeGetIteratorFuse.intact()) {
    return false;
  }

  // Ensure the array has Array.prototype as prototype and doesn't have an own
  // @@iterator property.
  //
  // Most arrays have the default array shape so we have a fast path for this
  // case.
  GlobalObject& global = arr->global();
  if (arr->shape() == global.maybeArrayShapeWithDefaultProto()) {
    return true;
  }

  NativeObject* arrayProto = global.maybeGetArrayPrototype();
  if (!arrayProto || arr->staticPrototype() != arrayProto) {
    return false;
  }
  if (arr->containsPure(PropertyKey::Symbol(cx->wellKnownSymbols().iterator))) {
    return false;
  }

  return true;
}

template bool js::IsArrayWithDefaultIterator<MustBePacked::No>(JSObject* obj,
                                                               JSContext* cx);
template bool js::IsArrayWithDefaultIterator<MustBePacked::Yes>(JSObject* obj,
                                                                JSContext* cx);

template <typename ObjectT, JSProtoKey ProtoKey>
static bool IsMapOrSetObjectWithDefaultIterator(JSObject* objArg,
                                                JSContext* cx) {
  if (!objArg->is<ObjectT>()) {
    return false;
  }
  auto* obj = &objArg->as<ObjectT>();

  // Ensure {Map,Set}.prototype[@@iterator] and %{Map,Set}IteratorPrototype%
  // haven't been mutated in a way that affects the iterator protocol.
  //
  // Note: this doesn't guard against `return` properties on the iterator
  // prototype, so this should only be used in places where we don't have to
  // call `IteratorClose`.
  if constexpr (std::is_same_v<ObjectT, MapObject>) {
    if (!obj->realm()->realmFuses.optimizeMapObjectIteratorFuse.intact()) {
      return false;
    }
  } else {
    static_assert(std::is_same_v<ObjectT, SetObject>);
    if (!obj->realm()->realmFuses.optimizeSetObjectIteratorFuse.intact()) {
      return false;
    }
  }

  // Ensure the object has the builtin prototype as proto.
  GlobalObject& global = obj->global();
  JSObject* proto = global.maybeGetPrototype(ProtoKey);
  if (!proto || obj->staticPrototype() != proto) {
    return false;
  }

  // Ensure the Map or Set object doesn't have an own @@iterator property.
  // Most Maps and Sets have no own properties so we have a fast path for this
  // case.
  if (obj->empty()) {
    return true;
  }
  if (obj->containsPure(PropertyKey::Symbol(cx->wellKnownSymbols().iterator))) {
    return false;
  }
  return true;
}
bool js::IsMapObjectWithDefaultIterator(JSObject* obj, JSContext* cx) {
  return IsMapOrSetObjectWithDefaultIterator<MapObject, JSProto_Map>(obj, cx);
}

bool js::IsSetObjectWithDefaultIterator(JSObject* obj, JSContext* cx) {
  return IsMapOrSetObjectWithDefaultIterator<SetObject, JSProto_Set>(obj, cx);
}