js/src/vm/Iteration.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 /* JavaScript iterators. */
   8
   9 #include "vm/Iteration.h"
  10
  11 #include "mozilla/ArrayUtils.h"
  12 #include "mozilla/DebugOnly.h"
  13 #include "mozilla/Likely.h"
  14 #include "mozilla/Maybe.h"
  15 #include "mozilla/MemoryReporting.h"
  16 #include "mozilla/PodOperations.h"
  17
  18 #include <algorithm>
  19 #include <new>
  20
  21 #include "jsapi.h"
  22 #include "jstypes.h"
  23
  24 #include "builtin/Array.h"
  25 #include "builtin/SelfHostingDefines.h"
  26 #include "ds/Sort.h"
  27 #include "gc/GC.h"
  28 #include "gc/GCContext.h"
  29 #include "js/ForOfIterator.h"         // JS::ForOfIterator
  30 #include "js/friend/ErrorMessages.h"  // js::GetErrorMessage, JSMSG_*
  31 #include "js/PropertySpec.h"
  32 #include "util/DifferentialTesting.h"
  33 #include "util/Poison.h"
  34 #include "vm/GlobalObject.h"
  35 #include "vm/Interpreter.h"
  36 #include "vm/JSContext.h"
  37 #include "vm/JSObject.h"
  38 #include "vm/NativeObject.h"  // js::PlainObject
  39 #include "vm/Shape.h"
  40 #include "vm/StringType.h"
  41 #include "vm/TypedArrayObject.h"
  42
  43 #ifdef ENABLE_RECORD_TUPLE
  44 #  include "builtin/RecordObject.h"
  45 #  include "builtin/TupleObject.h"
  46 #endif
  47
  48 #include "vm/NativeObject-inl.h"
  49 #include "vm/PlainObject-inl.h"  // js::PlainObject::createWithTemplate
  50
  51 using namespace js;
  52
  53 using mozilla::ArrayEqual;
  54 using mozilla::DebugOnly;
  55 using mozilla::Maybe;
  56 using mozilla::PodCopy;
  57
  58 using RootedPropertyIteratorObject = Rooted<PropertyIteratorObject*>;
  59
  60 static const gc::AllocKind ITERATOR_FINALIZE_KIND =
  61     gc::AllocKind::OBJECT2_BACKGROUND;
  62
  63 // Beware!  This function may have to trace incompletely-initialized
  64 // |NativeIterator| allocations if the |IdToString| in that constructor recurs
  65 // into this code.
  66 void NativeIterator::trace(JSTracer* trc) {
  67   TraceNullableEdge(trc, &objectBeingIterated_, "objectBeingIterated_");
  68   TraceNullableEdge(trc, &iterObj_, "iterObj");
  69
  70   // The limits below are correct at every instant of |NativeIterator|
  71   // initialization, with the end-pointer incremented as each new shape is
  72   // created, so they're safe to use here.
  73   std::for_each(shapesBegin(), shapesEnd(), [trc](GCPtr<Shape*>& shape) {
  74     TraceEdge(trc, &shape, "iterator_shape");
  75   });
  76
  77   // But as properties must be created *before* shapes, |propertiesBegin()|
  78   // that depends on |shapesEnd()| having its final value can't safely be
  79   // used.  Until this is fully initialized, use |propertyCursor_| instead,
  80   // which points at the start of properties even in partially initialized
  81   // |NativeIterator|s.  (|propertiesEnd()| is safe at all times with respect
  82   // to the properly-chosen beginning.)
  83   //
  84   // Note that we must trace all properties (not just those not yet visited,
  85   // or just visited, due to |NativeIterator::previousPropertyWas|) for
  86   // |NativeIterator|s to be reusable.
  87   GCPtr<JSLinearString*>* begin =
  88       MOZ_LIKELY(isInitialized()) ? propertiesBegin() : propertyCursor_;
  89   std::for_each(begin, propertiesEnd(), [trc](GCPtr<JSLinearString*>& prop) {
  90     // Properties begin life non-null and never *become*
  91     // null.  (Deletion-suppression will shift trailing
  92     // properties over a deleted property in the properties
  93     // array, but it doesn't null them out.)
  94     TraceEdge(trc, &prop, "prop");
  95   });
  96 }
  97
  98 using PropertyKeySet = GCHashSet<PropertyKey, DefaultHasher<PropertyKey>>;
  99
 100 class PropertyEnumerator {
 101   RootedObject obj_;
 102   MutableHandleIdVector props_;
 103   PropertyIndexVector* indices_;
 104
 105   uint32_t flags_;
 106   Rooted<PropertyKeySet> visited_;
 107
 108   bool enumeratingProtoChain_ = false;
 109
 110   enum class IndicesState {
 111     // Every property that has been enumerated so far can be represented as a
 112     // PropertyIndex, but we are not currently producing a list of indices. If
 113     // the state is Valid when we are done enumerating, then the resulting
 114     // iterator can be marked as NativeIteratorIndices::AvailableOnRequest.
 115     Valid,
 116
 117     // Every property that has been enumerated so far can be represented as a
 118     // PropertyIndex, and |indices_| points to a PropertyIndexVector containing
 119     // those indices. This is used when we want to create a NativeIterator with
 120     // valid indices.
 121     Allocating,
 122
 123     // It is not possible to represent every property of the object being
 124     // enumerated as a PropertyIndex. For example, enumerated properties on the
 125     // prototype chain are unsupported. We can transition to this state from
 126     // either of the other two.
 127     Unsupported
 128   };
 129   IndicesState indicesState_;
 130
 131  public:
 132   PropertyEnumerator(JSContext* cx, JSObject* obj, uint32_t flags,
 133                      MutableHandleIdVector props,
 134                      PropertyIndexVector* indices = nullptr)
 135       : obj_(cx, obj),
 136         props_(props),
 137         indices_(indices),
 138         flags_(flags),
 139         visited_(cx, PropertyKeySet(cx)),
 140         indicesState_(indices ? IndicesState::Allocating
 141                               : IndicesState::Valid) {}
 142
 143   bool snapshot(JSContext* cx);
 144
 145   void markIndicesUnsupported() { indicesState_ = IndicesState::Unsupported; }
 146   bool supportsIndices() const {
 147     return indicesState_ != IndicesState::Unsupported;
 148   }
 149   bool allocatingIndices() const {
 150     return indicesState_ == IndicesState::Allocating;
 151   }
 152
 153  private:
 154   template <bool CheckForDuplicates>
 155   bool enumerate(JSContext* cx, jsid id, bool enumerable,
 156                  PropertyIndex index = PropertyIndex::Invalid());
 157
 158   bool enumerateExtraProperties(JSContext* cx);
 159
 160   template <bool CheckForDuplicates>
 161   bool enumerateNativeProperties(JSContext* cx);
 162
 163   bool enumerateNativeProperties(JSContext* cx, bool checkForDuplicates) {
 164     if (checkForDuplicates) {
 165       return enumerateNativeProperties<true>(cx);
 166     }
 167     return enumerateNativeProperties<false>(cx);
 168   }
 169
 170   template <bool CheckForDuplicates>
 171   bool enumerateProxyProperties(JSContext* cx);
 172
 173   void reversePropsAndIndicesAfter(size_t initialLength) {
 174     // We iterate through prop maps in descending order of property creation,
 175     // but we need our return value to be in ascending order. If we are tracking
 176     // property indices, make sure to keep them in sync.
 177     MOZ_ASSERT(props_.begin() + initialLength <= props_.end());
 178     MOZ_ASSERT_IF(allocatingIndices(), props_.length() == indices_->length());
 179
 180     std::reverse(props_.begin() + initialLength, props_.end());
 181     if (allocatingIndices()) {
 182       std::reverse(indices_->begin() + initialLength, indices_->end());
 183     }
 184   }
 185 };
 186
 187 template <bool CheckForDuplicates>
 188 bool PropertyEnumerator::enumerate(JSContext* cx, jsid id, bool enumerable,
 189                                    PropertyIndex index) {
 190   if (CheckForDuplicates) {
 191     // If we've already seen this, we definitely won't add it.
 192     PropertyKeySet::AddPtr p = visited_.lookupForAdd(id);
 193     if (MOZ_UNLIKELY(!!p)) {
 194       return true;
 195     }
 196
 197     // It's not necessary to add properties to the hash set at the end of
 198     // the prototype chain, but custom enumeration behaviors might return
 199     // duplicated properties, so always add in such cases.
 200     if (obj_->is<ProxyObject>() || obj_->staticPrototype() ||
 201         obj_->getClass()->getNewEnumerate()) {
 202       if (!visited_.add(p, id)) {
 203         return false;
 204       }
 205     }
 206   }
 207
 208   if (!enumerable && !(flags_ & JSITER_HIDDEN)) {
 209     return true;
 210   }
 211
 212   // Symbol-keyed properties and nonenumerable properties are skipped unless
 213   // the caller specifically asks for them. A caller can also filter out
 214   // non-symbols by asking for JSITER_SYMBOLSONLY. PrivateName symbols are
 215   // skipped unless JSITER_PRIVATE is passed.
 216   if (id.isSymbol()) {
 217     if (!(flags_ & JSITER_SYMBOLS)) {
 218       return true;
 219     }
 220     if (!(flags_ & JSITER_PRIVATE) && id.isPrivateName()) {
 221       return true;
 222     }
 223   } else {
 224     if ((flags_ & JSITER_SYMBOLSONLY)) {
 225       return true;
 226     }
 227   }
 228
 229   MOZ_ASSERT_IF(allocatingIndices(), indices_->length() == props_.length());
 230   if (!props_.append(id)) {
 231     return false;
 232   }
 233
 234   if (!supportsIndices()) {
 235     return true;
 236   }
 237   if (index.kind() == PropertyIndex::Kind::Invalid || enumeratingProtoChain_) {
 238     markIndicesUnsupported();
 239     return true;
 240   }
 241
 242   if (allocatingIndices() && !indices_->append(index)) {
 243     return false;
 244   }
 245
 246   return true;
 247 }
 248
 249 bool PropertyEnumerator::enumerateExtraProperties(JSContext* cx) {
 250   MOZ_ASSERT(obj_->getClass()->getNewEnumerate());
 251
 252   RootedIdVector properties(cx);
 253   bool enumerableOnly = !(flags_ & JSITER_HIDDEN);
 254   if (!obj_->getClass()->getNewEnumerate()(cx, obj_, &properties,
 255                                            enumerableOnly)) {
 256     return false;
 257   }
 258
 259   RootedId id(cx);
 260   for (size_t n = 0; n < properties.length(); n++) {
 261     id = properties[n];
 262
 263     // The enumerate hook does not indicate whether the properties
 264     // it returns are enumerable or not. Since we already passed
 265     // `enumerableOnly` to the hook to filter out non-enumerable
 266     // properties, it doesn't really matter what we pass here.
 267     bool enumerable = true;
 268     if (!enumerate<true>(cx, id, enumerable)) {
 269       return false;
 270     }
 271   }
 272
 273   return true;
 274 }
 275
 276 static bool SortComparatorIntegerIds(jsid a, jsid b, bool* lessOrEqualp) {
 277   uint32_t indexA, indexB;
 278   MOZ_ALWAYS_TRUE(IdIsIndex(a, &indexA));
 279   MOZ_ALWAYS_TRUE(IdIsIndex(b, &indexB));
 280   *lessOrEqualp = (indexA <= indexB);
 281   return true;
 282 }
 283
 284 template <bool CheckForDuplicates>
 285 bool PropertyEnumerator::enumerateNativeProperties(JSContext* cx) {
 286   Handle<NativeObject*> pobj = obj_.as<NativeObject>();
 287
 288   // We don't need to iterate over the shape's properties if we're only
 289   // interested in enumerable properties and the object is known to have no
 290   // enumerable properties.
 291   //
 292   // Don't optimize if CheckForDuplicates is true, because non-enumerable
 293   // properties still have to participate in duplicate-property checking.
 294   const bool iterShapeProperties = CheckForDuplicates ||
 295                                    (flags_ & JSITER_HIDDEN) ||
 296                                    pobj->hasEnumerableProperty();
 297
 298   bool enumerateSymbols;
 299   if (flags_ & JSITER_SYMBOLSONLY) {
 300     if (!iterShapeProperties) {
 301       return true;
 302     }
 303     enumerateSymbols = true;
 304   } else {
 305     // Collect any dense elements from this object.
 306     size_t firstElemIndex = props_.length();
 307     size_t initlen = pobj->getDenseInitializedLength();
 308     const Value* elements = pobj->getDenseElements();
 309     bool hasHoles = false;
 310     for (uint32_t i = 0; i < initlen; ++i) {
 311       if (elements[i].isMagic(JS_ELEMENTS_HOLE)) {
 312         hasHoles = true;
 313       } else {
 314         // Dense arrays never get so large that i would not fit into an
 315         // integer id.
 316         if (!enumerate<CheckForDuplicates>(cx, PropertyKey::Int(i),
 317                                            /* enumerable = */ true,
 318                                            PropertyIndex::ForElement(i))) {
 319           return false;
 320         }
 321       }
 322     }
 323
 324     // Collect any typed array or shared typed array elements from this
 325     // object.
 326     if (pobj->is<TypedArrayObject>()) {
 327       size_t len = pobj->as<TypedArrayObject>().length().valueOr(0);
 328
 329       // Fail early if the typed array is enormous, because this will be very
 330       // slow and will likely report OOM. This also means we don't need to
 331       // handle indices greater than PropertyKey::IntMax in the loop below.
 332       static_assert(PropertyKey::IntMax == INT32_MAX);
 333       if (len > INT32_MAX) {
 334         ReportOutOfMemory(cx);
 335         return false;
 336       }
 337
 338       for (uint32_t i = 0; i < len; i++) {
 339         if (!enumerate<CheckForDuplicates>(cx, PropertyKey::Int(i),
 340                                            /* enumerable = */ true)) {
 341           return false;
 342         }
 343       }
 344     }
 345 #ifdef ENABLE_RECORD_TUPLE
 346     else {
 347       Rooted<RecordType*> rec(cx);
 348       if (RecordObject::maybeUnbox(pobj, &rec)) {
 349         Rooted<ArrayObject*> keys(cx, rec->keys());
 350
 351         for (size_t i = 0; i < keys->length(); i++) {
 352           JSAtom* key = &keys->getDenseElement(i).toString()->asAtom();
 353           PropertyKey id = AtomToId(key);
 354           if (!enumerate<CheckForDuplicates>(cx, id,
 355                                              /* enumerable = */ true)) {
 356             return false;
 357           }
 358         }
 359
 360         return true;
 361       } else {
 362         mozilla::Maybe<TupleType&> tup = TupleObject::maybeUnbox(pobj);
 363         if (tup) {
 364           uint32_t len = tup->length();
 365
 366           for (size_t i = 0; i < len; i++) {
 367             // We expect tuple indices not to get so large that `i` won't
 368             // fit into an `int32_t`.
 369             MOZ_ASSERT(PropertyKey::fitsInInt(i));
 370             PropertyKey id = PropertyKey::Int(i);
 371             if (!enumerate<CheckForDuplicates>(cx, id,
 372                                                /* enumerable = */ true)) {
 373               return false;
 374             }
 375           }
 376
 377           return true;
 378         }
 379       }
 380     }
 381 #endif
 382
 383     // The code below enumerates shape properties (including sparse elements) so
 384     // if we can ignore those we're done.
 385     if (!iterShapeProperties) {
 386       return true;
 387     }
 388
 389     // Collect any sparse elements from this object.
 390     bool isIndexed = pobj->isIndexed();
 391     if (isIndexed) {
 392       // If the dense elements didn't have holes, we don't need to include
 393       // them in the sort.
 394       if (!hasHoles) {
 395         firstElemIndex = props_.length();
 396       }
 397
 398       for (ShapePropertyIter<NoGC> iter(pobj->shape()); !iter.done(); iter++) {
 399         jsid id = iter->key();
 400         uint32_t dummy;
 401         if (IdIsIndex(id, &dummy)) {
 402           if (!enumerate<CheckForDuplicates>(cx, id, iter->enumerable())) {
 403             return false;
 404           }
 405         }
 406       }
 407
 408       MOZ_ASSERT(firstElemIndex <= props_.length());
 409
 410       jsid* ids = props_.begin() + firstElemIndex;
 411       size_t n = props_.length() - firstElemIndex;
 412
 413       RootedIdVector tmp(cx);
 414       if (!tmp.resize(n)) {
 415         return false;
 416       }
 417       PodCopy(tmp.begin(), ids, n);
 418
 419       if (!MergeSort(ids, n, tmp.begin(), SortComparatorIntegerIds)) {
 420         return false;
 421       }
 422     }
 423
 424     size_t initialLength = props_.length();
 425
 426     /* Collect all unique property names from this object's shape. */
 427     bool symbolsFound = false;
 428     for (ShapePropertyIter<NoGC> iter(pobj->shape()); !iter.done(); iter++) {
 429       jsid id = iter->key();
 430
 431       if (id.isSymbol()) {
 432         symbolsFound = true;
 433         continue;
 434       }
 435
 436       uint32_t dummy;
 437       if (isIndexed && IdIsIndex(id, &dummy)) {
 438         continue;
 439       }
 440
 441       PropertyIndex index = iter->isDataProperty()
 442                                 ? PropertyIndex::ForSlot(pobj, iter->slot())
 443                                 : PropertyIndex::Invalid();
 444       if (!enumerate<CheckForDuplicates>(cx, id, iter->enumerable(), index)) {
 445         return false;
 446       }
 447     }
 448     reversePropsAndIndicesAfter(initialLength);
 449
 450     enumerateSymbols = symbolsFound && (flags_ & JSITER_SYMBOLS);
 451   }
 452
 453   if (enumerateSymbols) {
 454     MOZ_ASSERT(iterShapeProperties);
 455     MOZ_ASSERT(!allocatingIndices());
 456
 457     // Do a second pass to collect symbols. The spec requires that all symbols
 458     // appear after all strings in [[OwnPropertyKeys]] for ordinary objects:
 459     // https://tc39.es/ecma262/#sec-ordinaryownpropertykeys
 460     size_t initialLength = props_.length();
 461     for (ShapePropertyIter<NoGC> iter(pobj->shape()); !iter.done(); iter++) {
 462       jsid id = iter->key();
 463       if (id.isSymbol()) {
 464         if (!enumerate<CheckForDuplicates>(cx, id, iter->enumerable())) {
 465           return false;
 466         }
 467       }
 468     }
 469     reversePropsAndIndicesAfter(initialLength);
 470   }
 471
 472   return true;
 473 }
 474
 475 template <bool CheckForDuplicates>
 476 bool PropertyEnumerator::enumerateProxyProperties(JSContext* cx) {
 477   MOZ_ASSERT(obj_->is<ProxyObject>());
 478
 479   RootedIdVector proxyProps(cx);
 480
 481   if (flags_ & JSITER_HIDDEN || flags_ & JSITER_SYMBOLS) {
 482     // This gets all property keys, both strings and symbols. The call to
 483     // enumerate in the loop below will filter out unwanted keys, per the
 484     // flags.
 485     if (!Proxy::ownPropertyKeys(cx, obj_, &proxyProps)) {
 486       return false;
 487     }
 488
 489     Rooted<mozilla::Maybe<PropertyDescriptor>> desc(cx);
 490     for (size_t n = 0, len = proxyProps.length(); n < len; n++) {
 491       bool enumerable = false;
 492
 493       // We need to filter, if the caller just wants enumerable symbols.
 494       if (!(flags_ & JSITER_HIDDEN)) {
 495         if (!Proxy::getOwnPropertyDescriptor(cx, obj_, proxyProps[n], &desc)) {
 496           return false;
 497         }
 498         enumerable = desc.isSome() && desc->enumerable();
 499       }
 500
 501       if (!enumerate<CheckForDuplicates>(cx, proxyProps[n], enumerable)) {
 502         return false;
 503       }
 504     }
 505
 506     return true;
 507   }
 508
 509   // Returns enumerable property names (no symbols).
 510   if (!Proxy::getOwnEnumerablePropertyKeys(cx, obj_, &proxyProps)) {
 511     return false;
 512   }
 513
 514   for (size_t n = 0, len = proxyProps.length(); n < len; n++) {
 515     if (!enumerate<CheckForDuplicates>(cx, proxyProps[n], true)) {
 516       return false;
 517     }
 518   }
 519
 520   return true;
 521 }
 522
 523 #ifdef DEBUG
 524
 525 struct SortComparatorIds {
 526   JSContext* const cx;
 527
 528   explicit SortComparatorIds(JSContext* cx) : cx(cx) {}
 529
 530   bool operator()(jsid aArg, jsid bArg, bool* lessOrEqualp) {
 531     RootedId a(cx, aArg);
 532     RootedId b(cx, bArg);
 533
 534     // Pick an arbitrary order on jsids that is as stable as possible
 535     // across executions.
 536     if (a == b) {
 537       *lessOrEqualp = true;
 538       return true;
 539     }
 540
 541     enum class KeyType { Void, Int, String, Symbol };
 542
 543     auto keyType = [](PropertyKey key) {
 544       if (key.isString()) {
 545         return KeyType::String;
 546       }
 547       if (key.isInt()) {
 548         return KeyType::Int;
 549       }
 550       if (key.isSymbol()) {
 551         return KeyType::Symbol;
 552       }
 553       MOZ_ASSERT(key.isVoid());
 554       return KeyType::Void;
 555     };
 556
 557     if (keyType(a) != keyType(b)) {
 558       *lessOrEqualp = (keyType(a) <= keyType(b));
 559       return true;
 560     }
 561
 562     if (a.isInt()) {
 563       *lessOrEqualp = (a.toInt() <= b.toInt());
 564       return true;
 565     }
 566
 567     RootedString astr(cx), bstr(cx);
 568     if (a.isSymbol()) {
 569       MOZ_ASSERT(b.isSymbol());
 570       JS::SymbolCode ca = a.toSymbol()->code();
 571       JS::SymbolCode cb = b.toSymbol()->code();
 572       if (ca != cb) {
 573         *lessOrEqualp = uint32_t(ca) <= uint32_t(cb);
 574         return true;
 575       }
 576       MOZ_ASSERT(ca == JS::SymbolCode::PrivateNameSymbol ||
 577                  ca == JS::SymbolCode::InSymbolRegistry ||
 578                  ca == JS::SymbolCode::UniqueSymbol);
 579       astr = a.toSymbol()->description();
 580       bstr = b.toSymbol()->description();
 581       if (!astr || !bstr) {
 582         *lessOrEqualp = !astr;
 583         return true;
 584       }
 585
 586       // Fall through to string comparison on the descriptions. The sort
 587       // order is nondeterministic if two different unique symbols have
 588       // the same description.
 589     } else {
 590       astr = IdToString(cx, a);
 591       if (!astr) {
 592         return false;
 593       }
 594       bstr = IdToString(cx, b);
 595       if (!bstr) {
 596         return false;
 597       }
 598     }
 599
 600     int32_t result;
 601     if (!CompareStrings(cx, astr, bstr, &result)) {
 602       return false;
 603     }
 604
 605     *lessOrEqualp = (result <= 0);
 606     return true;
 607   }
 608 };
 609
 610 #endif /* DEBUG */
 611
 612 static void AssertNoEnumerableProperties(NativeObject* obj) {
 613 #ifdef DEBUG
 614   // Verify the object has no enumerable properties if the HasEnumerable
 615   // ObjectFlag is not set.
 616
 617   MOZ_ASSERT(!obj->hasEnumerableProperty());
 618
 619   static constexpr size_t MaxPropsToCheck = 5;
 620
 621   size_t count = 0;
 622   for (ShapePropertyIter<NoGC> iter(obj->shape()); !iter.done(); iter++) {
 623     MOZ_ASSERT(!iter->enumerable());
 624     if (++count > MaxPropsToCheck) {
 625       break;
 626     }
 627   }
 628 #endif  // DEBUG
 629 }
 630
 631 static bool ProtoMayHaveEnumerableProperties(JSObject* obj) {
 632   if (!obj->is<NativeObject>()) {
 633     return true;
 634   }
 635
 636   JSObject* proto = obj->as<NativeObject>().staticPrototype();
 637   while (proto) {
 638     if (!proto->is<NativeObject>()) {
 639       return true;
 640     }
 641     NativeObject* nproto = &proto->as<NativeObject>();
 642     if (nproto->hasEnumerableProperty() ||
 643         nproto->getDenseInitializedLength() > 0 ||
 644         ClassCanHaveExtraEnumeratedProperties(nproto->getClass())) {
 645       return true;
 646     }
 647     AssertNoEnumerableProperties(nproto);
 648     proto = nproto->staticPrototype();
 649   }
 650
 651   return false;
 652 }
 653
 654 bool PropertyEnumerator::snapshot(JSContext* cx) {
 655   // If we're only interested in enumerable properties and the proto chain has
 656   // no enumerable properties (the common case), we can optimize this to ignore
 657   // the proto chain. This also lets us take advantage of the no-duplicate-check
 658   // optimization below.
 659   if (!(flags_ & JSITER_HIDDEN) && !(flags_ & JSITER_OWNONLY) &&
 660       !ProtoMayHaveEnumerableProperties(obj_)) {
 661     flags_ |= JSITER_OWNONLY;
 662   }
 663
 664   // Don't check for duplicates if we're only interested in own properties.
 665   // This does the right thing for most objects: native objects don't have
 666   // duplicate property ids and we allow the [[OwnPropertyKeys]] proxy trap to
 667   // return duplicates.
 668   //
 669   // The only special case is when the object has a newEnumerate hook: it
 670   // can return duplicate properties and we have to filter them. This is
 671   // handled below.
 672   bool checkForDuplicates = !(flags_ & JSITER_OWNONLY);
 673
 674   do {
 675     if (obj_->getClass()->getNewEnumerate()) {
 676       markIndicesUnsupported();
 677
 678       if (!enumerateExtraProperties(cx)) {
 679         return false;
 680       }
 681
 682       if (obj_->is<NativeObject>()) {
 683         if (!enumerateNativeProperties(cx, /*checkForDuplicates*/ true)) {
 684           return false;
 685         }
 686       }
 687
 688     } else if (obj_->is<NativeObject>()) {
 689       // Give the object a chance to resolve all lazy properties
 690       if (JSEnumerateOp enumerateOp = obj_->getClass()->getEnumerate()) {
 691         markIndicesUnsupported();
 692         if (!enumerateOp(cx, obj_.as<NativeObject>())) {
 693           return false;
 694         }
 695       }
 696       if (!enumerateNativeProperties(cx, checkForDuplicates)) {
 697         return false;
 698       }
 699     } else if (obj_->is<ProxyObject>()) {
 700       markIndicesUnsupported();
 701       if (checkForDuplicates) {
 702         if (!enumerateProxyProperties<true>(cx)) {
 703           return false;
 704         }
 705       } else {
 706         if (!enumerateProxyProperties<false>(cx)) {
 707           return false;
 708         }
 709       }
 710     } else {
 711       MOZ_CRASH("non-native objects must have an enumerate op");
 712     }
 713
 714     if (flags_ & JSITER_OWNONLY) {
 715       break;
 716     }
 717
 718     if (!GetPrototype(cx, obj_, &obj_)) {
 719       return false;
 720     }
 721     enumeratingProtoChain_ = true;
 722
 723     // The [[Prototype]] chain might be cyclic.
 724     if (!CheckForInterrupt(cx)) {
 725       return false;
 726     }
 727   } while (obj_ != nullptr);
 728
 729 #ifdef DEBUG
 730   if (js::SupportDifferentialTesting() && !supportsIndices()) {
 731     /*
 732      * In some cases the enumeration order for an object depends on the
 733      * execution mode (interpreter vs. JIT), especially for native objects
 734      * with a class enumerate hook (where resolving a property changes the
 735      * resulting enumeration order). These aren't really bugs, but the
 736      * differences can change the generated output and confuse correctness
 737      * fuzzers, so we sort the ids if such a fuzzer is running.
 738      *
 739      * We don't do this in the general case because (a) doing so is slow,
 740      * and (b) it also breaks the web, which expects enumeration order to
 741      * follow the order in which properties are added, in certain cases.
 742      * Since ECMA does not specify an enumeration order for objects, both
 743      * behaviors are technically correct to do.
 744      */
 745
 746     jsid* ids = props_.begin();
 747     size_t n = props_.length();
 748
 749     RootedIdVector tmp(cx);
 750     if (!tmp.resize(n)) {
 751       return false;
 752     }
 753     PodCopy(tmp.begin(), ids, n);
 754
 755     if (!MergeSort(ids, n, tmp.begin(), SortComparatorIds(cx))) {
 756       return false;
 757     }
 758   }
 759 #endif
 760
 761   return true;
 762 }
 763
 764 JS_PUBLIC_API bool js::GetPropertyKeys(JSContext* cx, HandleObject obj,
 765                                        unsigned flags,
 766                                        MutableHandleIdVector props) {
 767   uint32_t validFlags =
 768       flags & (JSITER_OWNONLY | JSITER_HIDDEN | JSITER_SYMBOLS |
 769                JSITER_SYMBOLSONLY | JSITER_PRIVATE);
 770
 771   PropertyEnumerator enumerator(cx, obj, validFlags, props);
 772   return enumerator.snapshot(cx);
 773 }
 774
 775 static inline void RegisterEnumerator(JSContext* cx, NativeIterator* ni) {
 776   MOZ_ASSERT(ni->objectBeingIterated());
 777
 778   // Register non-escaping native enumerators (for-in) with the current
 779   // context.
 780   ni->link(cx->compartment()->enumeratorsAddr());
 781
 782   MOZ_ASSERT(!ni->isActive());
 783   ni->markActive();
 784 }
 785
 786 static PropertyIteratorObject* NewPropertyIteratorObject(JSContext* cx) {
 787   const JSClass* clasp = &PropertyIteratorObject::class_;
 788   Rooted<SharedShape*> shape(
 789       cx,
 790       SharedShape::getInitialShape(cx, clasp, cx->realm(), TaggedProto(nullptr),
 791                                    ITERATOR_FINALIZE_KIND));
 792   if (!shape) {
 793     return nullptr;
 794   }
 795
 796   auto* res = NativeObject::create<PropertyIteratorObject>(
 797       cx, ITERATOR_FINALIZE_KIND, GetInitialHeap(GenericObject, clasp), shape);
 798   if (!res) {
 799     return nullptr;
 800   }
 801
 802   // CodeGenerator::visitIteratorStartO assumes the iterator object is not
 803   // inside the nursery when deciding whether a barrier is necessary.
 804   MOZ_ASSERT(!js::gc::IsInsideNursery(res));
 805   return res;
 806 }
 807
 808 static inline size_t NumTrailingBytes(size_t propertyCount, size_t shapeCount,
 809                                       bool hasIndices) {
 810   static_assert(alignof(GCPtr<JSLinearString*>) <= alignof(NativeIterator));
 811   static_assert(alignof(GCPtr<Shape*>) <= alignof(GCPtr<JSLinearString*>));
 812   static_assert(alignof(PropertyIndex) <= alignof(GCPtr<Shape*>));
 813   size_t result = propertyCount * sizeof(GCPtr<JSLinearString*>) +
 814                   shapeCount * sizeof(GCPtr<Shape*>);
 815   if (hasIndices) {
 816     result += propertyCount * sizeof(PropertyIndex);
 817   }
 818   return result;
 819 }
 820
 821 static inline size_t AllocationSize(size_t propertyCount, size_t shapeCount,
 822                                     bool hasIndices) {
 823   return sizeof(NativeIterator) +
 824          NumTrailingBytes(propertyCount, shapeCount, hasIndices);
 825 }
 826
 827 static PropertyIteratorObject* CreatePropertyIterator(
 828     JSContext* cx, Handle<JSObject*> objBeingIterated, HandleIdVector props,
 829     bool supportsIndices, PropertyIndexVector* indices,
 830     uint32_t cacheableProtoChainLength) {
 831   MOZ_ASSERT_IF(indices, supportsIndices);
 832   if (props.length() > NativeIterator::PropCountLimit) {
 833     ReportAllocationOverflow(cx);
 834     return nullptr;
 835   }
 836
 837   bool hasIndices = !!indices;
 838
 839   // If the iterator is cacheable, we store the shape of each object
 840   // along the proto chain in the iterator. If the iterator is not
 841   // cacheable, but has indices, then we store one shape (the shape of
 842   // the object being iterated.)
 843   uint32_t numShapes = cacheableProtoChainLength;
 844   if (numShapes == 0 && hasIndices) {
 845     numShapes = 1;
 846   }
 847
 848   Rooted<PropertyIteratorObject*> propIter(cx, NewPropertyIteratorObject(cx));
 849   if (!propIter) {
 850     return nullptr;
 851   }
 852
 853   void* mem = cx->pod_malloc_with_extra<NativeIterator, uint8_t>(
 854       NumTrailingBytes(props.length(), numShapes, hasIndices));
 855   if (!mem) {
 856     return nullptr;
 857   }
 858
 859   // This also registers |ni| with |propIter|.
 860   bool hadError = false;
 861   new (mem) NativeIterator(cx, propIter, objBeingIterated, props,
 862                            supportsIndices, indices, numShapes, &hadError);
 863   if (hadError) {
 864     return nullptr;
 865   }
 866
 867   return propIter;
 868 }
 869
 870 static HashNumber HashIteratorShape(Shape* shape) {
 871   return DefaultHasher<Shape*>::hash(shape);
 872 }
 873
 874 /**
 875  * Initialize a fresh NativeIterator.
 876  *
 877  * This definition is a bit tricky: some parts of initializing are fallible, so
 878  * as we initialize, we must carefully keep this in GC-safe state (see
 879  * NativeIterator::trace).
 880  */
 881 NativeIterator::NativeIterator(JSContext* cx,
 882                                Handle<PropertyIteratorObject*> propIter,
 883                                Handle<JSObject*> objBeingIterated,
 884                                HandleIdVector props, bool supportsIndices,
 885                                PropertyIndexVector* indices, uint32_t numShapes,
 886                                bool* hadError)
 887     : objectBeingIterated_(objBeingIterated),
 888       iterObj_(propIter),
 889       // NativeIterator initially acts (before full initialization) as if it
 890       // contains no shapes...
 891       shapesEnd_(shapesBegin()),
 892       // ...and no properties.
 893       propertyCursor_(
 894           reinterpret_cast<GCPtr<JSLinearString*>*>(shapesBegin() + numShapes)),
 895       propertiesEnd_(propertyCursor_),
 896       shapesHash_(0),
 897       flagsAndCount_(
 898           initialFlagsAndCount(props.length()))  // note: no Flags::Initialized
 899 {
 900   // If there are shapes, the object and all objects on its prototype chain must
 901   // be native objects. See CanCompareIterableObjectToCache.
 902   MOZ_ASSERT_IF(numShapes > 0,
 903                 objBeingIterated && objBeingIterated->is<NativeObject>());
 904
 905   MOZ_ASSERT(!*hadError);
 906
 907   bool hasActualIndices = !!indices;
 908   MOZ_ASSERT_IF(hasActualIndices, indices->length() == props.length());
 909
 910   // NOTE: This must be done first thing: The caller can't free `this` on error
 911   //       because it has GCPtr fields whose barriers have already fired; the
 912   //       store buffer has pointers to them. Only the GC can free `this` (via
 913   //       PropertyIteratorObject::finalize).
 914   propIter->initNativeIterator(this);
 915
 916   // The GC asserts on finalization that `this->allocationSize()` matches the
 917   // `nbytes` passed to `AddCellMemory`. So once these lines run, we must make
 918   // `this->allocationSize()` correct. That means infallibly initializing the
 919   // shapes, and ensuring that indicesState_.allocated() is true if we've
 920   // allocated space for indices. It's OK for the constructor to fail after
 921   // that.
 922   size_t nbytes = AllocationSize(props.length(), numShapes, hasActualIndices);
 923   AddCellMemory(propIter, nbytes, MemoryUse::NativeIterator);
 924   if (supportsIndices) {
 925     if (hasActualIndices) {
 926       // If the string allocation fails, indicesAllocated() must be true
 927       // so that this->allocationSize() is correct. Set it to Disabled. It will
 928       // be updated below.
 929       setIndicesState(NativeIteratorIndices::Disabled);
 930     } else {
 931       // This object supports indices (ie it only has own enumerable
 932       // properties), but we didn't allocate them because we haven't seen a
 933       // consumer yet. We mark the iterator so that potential consumers know to
 934       // request a fresh iterator with indices.
 935       setIndicesState(NativeIteratorIndices::AvailableOnRequest);
 936     }
 937   }
 938
 939   if (numShapes > 0) {
 940     // Construct shapes into the shapes array.  Also compute the shapesHash,
 941     // which incorporates Shape* addresses that could have changed during a GC
 942     // triggered in (among other places) |IdToString| above.
 943     JSObject* pobj = objBeingIterated;
 944     HashNumber shapesHash = 0;
 945     for (uint32_t i = 0; i < numShapes; i++) {
 946       MOZ_ASSERT(pobj->is<NativeObject>());
 947       Shape* shape = pobj->shape();
 948       new (shapesEnd_) GCPtr<Shape*>(shape);
 949       shapesEnd_++;
 950       shapesHash = mozilla::AddToHash(shapesHash, HashIteratorShape(shape));
 951       pobj = pobj->staticPrototype();
 952     }
 953     shapesHash_ = shapesHash;
 954
 955     // There are two cases in which we need to store shapes. If this
 956     // iterator is cacheable, we store the shapes for the entire proto
 957     // chain so we can check that the cached iterator is still valid
 958     // (see MacroAssembler::maybeLoadIteratorFromShape). If this iterator
 959     // has indices, then even if it isn't cacheable we need to store the
 960     // shape of the iterated object itself (see IteratorHasIndicesAndBranch).
 961     // In the former case, assert that we're storing the entire proto chain.
 962     MOZ_ASSERT_IF(numShapes > 1, pobj == nullptr);
 963   }
 964   MOZ_ASSERT(static_cast<void*>(shapesEnd_) == propertyCursor_);
 965
 966   // Allocate any strings in the nursery until the first minor GC. After this
 967   // point they will end up getting tenured anyway because they are reachable
 968   // from |propIter| which will be tenured.
 969   AutoSelectGCHeap gcHeap(cx);
 970
 971   size_t numProps = props.length();
 972   for (size_t i = 0; i < numProps; i++) {
 973     JSLinearString* str = IdToString(cx, props[i], gcHeap);
 974     if (!str) {
 975       *hadError = true;
 976       return;
 977     }
 978     new (propertiesEnd_) GCPtr<JSLinearString*>(str);
 979     propertiesEnd_++;
 980   }
 981
 982   if (hasActualIndices) {
 983     PropertyIndex* cursor = indicesBegin();
 984     for (size_t i = 0; i < numProps; i++) {
 985       *cursor++ = (*indices)[i];
 986     }
 987     MOZ_ASSERT(uintptr_t(cursor) == uintptr_t(this) + nbytes);
 988     setIndicesState(NativeIteratorIndices::Valid);
 989   }
 990
 991   markInitialized();
 992
 993   MOZ_ASSERT(!*hadError);
 994 }
 995
 996 inline size_t NativeIterator::allocationSize() const {
 997   size_t numShapes = shapesEnd() - shapesBegin();
 998
 999   return AllocationSize(initialPropertyCount(), numShapes, indicesAllocated());
1000 }
1001
1002 /* static */
1003 bool IteratorHashPolicy::match(PropertyIteratorObject* obj,
1004                                const Lookup& lookup) {
1005   NativeIterator* ni = obj->getNativeIterator();
1006   if (ni->shapesHash() != lookup.shapesHash ||
1007       ni->shapeCount() != lookup.numShapes) {
1008     return false;
1009   }
1010
1011   return ArrayEqual(reinterpret_cast<Shape**>(ni->shapesBegin()), lookup.shapes,
1012                     ni->shapeCount());
1013 }
1014
1015 static inline bool CanCompareIterableObjectToCache(JSObject* obj) {
1016   if (obj->is<NativeObject>()) {
1017     return obj->as<NativeObject>().getDenseInitializedLength() == 0;
1018   }
1019   return false;
1020 }
1021
1022 static bool CanStoreInIteratorCache(JSObject* obj) {
1023   do {
1024     MOZ_ASSERT(obj->as<NativeObject>().getDenseInitializedLength() == 0);
1025
1026     // Typed arrays have indexed properties not captured by the Shape guard.
1027     // Enumerate hooks may add extra properties.
1028     if (MOZ_UNLIKELY(ClassCanHaveExtraEnumeratedProperties(obj->getClass()))) {
1029       return false;
1030     }
1031
1032     obj = obj->staticPrototype();
1033   } while (obj);
1034
1035   return true;
1036 }
1037
1038 static MOZ_ALWAYS_INLINE PropertyIteratorObject* LookupInShapeIteratorCache(
1039     JSContext* cx, JSObject* obj, uint32_t* cacheableProtoChainLength) {
1040   if (!obj->shape()->cache().isIterator() ||
1041       !CanCompareIterableObjectToCache(obj)) {
1042     return nullptr;
1043   }
1044   PropertyIteratorObject* iterobj = obj->shape()->cache().toIterator();
1045   NativeIterator* ni = iterobj->getNativeIterator();
1046   MOZ_ASSERT(*ni->shapesBegin() == obj->shape());
1047   if (!ni->isReusable()) {
1048     return nullptr;
1049   }
1050
1051   // Verify shapes of proto chain.
1052   JSObject* pobj = obj;
1053   for (GCPtr<Shape*>* s = ni->shapesBegin() + 1; s != ni->shapesEnd(); s++) {
1054     Shape* shape = *s;
1055     pobj = pobj->staticPrototype();
1056     if (pobj->shape() != shape) {
1057       return nullptr;
1058     }
1059     if (!CanCompareIterableObjectToCache(pobj)) {
1060       return nullptr;
1061     }
1062   }
1063   MOZ_ASSERT(CanStoreInIteratorCache(obj));
1064   *cacheableProtoChainLength = ni->shapeCount();
1065   return iterobj;
1066 }
1067
1068 static MOZ_ALWAYS_INLINE PropertyIteratorObject* LookupInIteratorCache(
1069     JSContext* cx, JSObject* obj, uint32_t* cacheableProtoChainLength) {
1070   MOZ_ASSERT(*cacheableProtoChainLength == 0);
1071
1072   if (PropertyIteratorObject* shapeCached =
1073           LookupInShapeIteratorCache(cx, obj, cacheableProtoChainLength)) {
1074     return shapeCached;
1075   }
1076
1077   Vector<Shape*, 8> shapes(cx);
1078   HashNumber shapesHash = 0;
1079   JSObject* pobj = obj;
1080   do {
1081     if (!CanCompareIterableObjectToCache(pobj)) {
1082       return nullptr;
1083     }
1084
1085     MOZ_ASSERT(pobj->is<NativeObject>());
1086     Shape* shape = pobj->shape();
1087     shapesHash = mozilla::AddToHash(shapesHash, HashIteratorShape(shape));
1088
1089     if (MOZ_UNLIKELY(!shapes.append(shape))) {
1090       cx->recoverFromOutOfMemory();
1091       return nullptr;
1092     }
1093
1094     pobj = pobj->staticPrototype();
1095   } while (pobj);
1096
1097   MOZ_ASSERT(!shapes.empty());
1098   *cacheableProtoChainLength = shapes.length();
1099
1100   IteratorHashPolicy::Lookup lookup(shapes.begin(), shapes.length(),
1101                                     shapesHash);
1102   auto p = ObjectRealm::get(obj).iteratorCache.lookup(lookup);
1103   if (!p) {
1104     return nullptr;
1105   }
1106
1107   PropertyIteratorObject* iterobj = *p;
1108   MOZ_ASSERT(iterobj->compartment() == cx->compartment());
1109
1110   NativeIterator* ni = iterobj->getNativeIterator();
1111   if (!ni->isReusable()) {
1112     return nullptr;
1113   }
1114
1115   return iterobj;
1116 }
1117
1118 [[nodiscard]] static bool StoreInIteratorCache(
1119     JSContext* cx, JSObject* obj, PropertyIteratorObject* iterobj) {
1120   MOZ_ASSERT(CanStoreInIteratorCache(obj));
1121
1122   NativeIterator* ni = iterobj->getNativeIterator();
1123   MOZ_ASSERT(ni->shapeCount() > 0);
1124
1125   obj->shape()->maybeCacheIterator(cx, iterobj);
1126
1127   IteratorHashPolicy::Lookup lookup(
1128       reinterpret_cast<Shape**>(ni->shapesBegin()), ni->shapeCount(),
1129       ni->shapesHash());
1130
1131   ObjectRealm::IteratorCache& cache = ObjectRealm::get(obj).iteratorCache;
1132   bool ok;
1133   auto p = cache.lookupForAdd(lookup);
1134   if (MOZ_LIKELY(!p)) {
1135     ok = cache.add(p, iterobj);
1136   } else {
1137     // If we weren't able to use an existing cached iterator, just
1138     // replace it.
1139     cache.remove(p);
1140     ok = cache.relookupOrAdd(p, lookup, iterobj);
1141   }
1142   if (!ok) {
1143     ReportOutOfMemory(cx);
1144     return false;
1145   }
1146
1147   return true;
1148 }
1149
1150 bool js::EnumerateProperties(JSContext* cx, HandleObject obj,
1151                              MutableHandleIdVector props) {
1152   MOZ_ASSERT(props.empty());
1153
1154   if (MOZ_UNLIKELY(obj->is<ProxyObject>())) {
1155     return Proxy::enumerate(cx, obj, props);
1156   }
1157
1158   uint32_t flags = 0;
1159   PropertyEnumerator enumerator(cx, obj, flags, props);
1160   return enumerator.snapshot(cx);
1161 }
1162
1163 #ifdef DEBUG
1164 static bool IndicesAreValid(NativeObject* obj, NativeIterator* ni) {
1165   MOZ_ASSERT(ni->hasValidIndices());
1166   size_t numDenseElements = obj->getDenseInitializedLength();
1167   size_t numFixedSlots = obj->numFixedSlots();
1168   const Value* elements = obj->getDenseElements();
1169
1170   GCPtr<JSLinearString*>* keys = ni->propertiesBegin();
1171   PropertyIndex* indices = ni->indicesBegin();
1172
1173   for (uint32_t i = 0; i < ni->numKeys(); i++) {
1174     PropertyIndex index = indices[i];
1175     switch (index.kind()) {
1176       case PropertyIndex::Kind::Element:
1177         // Verify that the dense element exists and is not a hole.
1178         if (index.index() >= numDenseElements ||
1179             elements[index.index()].isMagic(JS_ELEMENTS_HOLE)) {
1180           return false;
1181         }
1182         break;
1183       case PropertyIndex::Kind::FixedSlot: {
1184         // Verify that the slot exists and is an enumerable data property with
1185         // the expected key.
1186         Maybe<PropertyInfo> prop =
1187             obj->lookupPure(AtomToId(&keys[i]->asAtom()));
1188         if (!prop.isSome() || !prop->hasSlot() || !prop->enumerable() ||
1189             !prop->isDataProperty() || prop->slot() != index.index()) {
1190           return false;
1191         }
1192         break;
1193       }
1194       case PropertyIndex::Kind::DynamicSlot: {
1195         // Verify that the slot exists and is an enumerable data property with
1196         // the expected key.
1197         Maybe<PropertyInfo> prop =
1198             obj->lookupPure(AtomToId(&keys[i]->asAtom()));
1199         if (!prop.isSome() || !prop->hasSlot() || !prop->enumerable() ||
1200             !prop->isDataProperty() ||
1201             prop->slot() - numFixedSlots != index.index()) {
1202           return false;
1203         }
1204         break;
1205       }
1206       case PropertyIndex::Kind::Invalid:
1207         return false;
1208     }
1209   }
1210   return true;
1211 }
1212 #endif
1213
1214 template <bool WantIndices>
1215 static PropertyIteratorObject* GetIteratorImpl(JSContext* cx,
1216                                                HandleObject obj) {
1217   MOZ_ASSERT(!obj->is<PropertyIteratorObject>());
1218   MOZ_ASSERT(cx->compartment() == obj->compartment(),
1219              "We may end up allocating shapes in the wrong zone!");
1220
1221   uint32_t cacheableProtoChainLength = 0;
1222   if (PropertyIteratorObject* iterobj =
1223           LookupInIteratorCache(cx, obj, &cacheableProtoChainLength)) {
1224     NativeIterator* ni = iterobj->getNativeIterator();
1225     bool recreateWithIndices = WantIndices && ni->indicesAvailableOnRequest();
1226     if (!recreateWithIndices) {
1227       MOZ_ASSERT_IF(WantIndices && ni->hasValidIndices(),
1228                     IndicesAreValid(&obj->as<NativeObject>(), ni));
1229       ni->initObjectBeingIterated(*obj);
1230       RegisterEnumerator(cx, ni);
1231       return iterobj;
1232     }
1233   }
1234
1235   if (cacheableProtoChainLength > 0 && !CanStoreInIteratorCache(obj)) {
1236     cacheableProtoChainLength = 0;
1237   }
1238
1239   RootedIdVector keys(cx);
1240   PropertyIndexVector indices(cx);
1241   bool supportsIndices = false;
1242
1243   if (MOZ_UNLIKELY(obj->is<ProxyObject>())) {
1244     if (!Proxy::enumerate(cx, obj, &keys)) {
1245       return nullptr;
1246     }
1247   } else {
1248     uint32_t flags = 0;
1249     PropertyEnumerator enumerator(cx, obj, flags, &keys, &indices);
1250     if (!enumerator.snapshot(cx)) {
1251       return nullptr;
1252     }
1253     supportsIndices = enumerator.supportsIndices();
1254     MOZ_ASSERT_IF(WantIndices && supportsIndices,
1255                   keys.length() == indices.length());
1256   }
1257
1258   // If the object has dense elements, mark the dense elements as
1259   // maybe-in-iteration.
1260   //
1261   // The iterator is a snapshot so if indexed properties are added after this
1262   // point we don't need to do anything. However, the object might have sparse
1263   // elements now that can be densified later. To account for this, we set the
1264   // maybe-in-iteration flag also in NativeObject::maybeDensifySparseElements.
1265   //
1266   // In debug builds, AssertDenseElementsNotIterated is used to check the flag
1267   // is set correctly.
1268   if (obj->is<NativeObject>() &&
1269       obj->as<NativeObject>().getDenseInitializedLength() > 0) {
1270     obj->as<NativeObject>().markDenseElementsMaybeInIteration();
1271   }
1272
1273   PropertyIndexVector* indicesPtr =
1274       WantIndices && supportsIndices ? &indices : nullptr;
1275   PropertyIteratorObject* iterobj = CreatePropertyIterator(
1276       cx, obj, keys, supportsIndices, indicesPtr, cacheableProtoChainLength);
1277   if (!iterobj) {
1278     return nullptr;
1279   }
1280   RegisterEnumerator(cx, iterobj->getNativeIterator());
1281
1282   cx->check(iterobj);
1283   MOZ_ASSERT_IF(
1284       WantIndices && supportsIndices,
1285       IndicesAreValid(&obj->as<NativeObject>(), iterobj->getNativeIterator()));
1286
1287 #ifdef DEBUG
1288   if (obj->is<NativeObject>()) {
1289     if (PrototypeMayHaveIndexedProperties(&obj->as<NativeObject>())) {
1290       iterobj->getNativeIterator()->setMaybeHasIndexedPropertiesFromProto();
1291     }
1292   }
1293 #endif
1294
1295   // Cache the iterator object.
1296   if (cacheableProtoChainLength > 0) {
1297     if (!StoreInIteratorCache(cx, obj, iterobj)) {
1298       return nullptr;
1299     }
1300   }
1301
1302   return iterobj;
1303 }
1304
1305 PropertyIteratorObject* js::GetIterator(JSContext* cx, HandleObject obj) {
1306   return GetIteratorImpl<false>(cx, obj);
1307 }
1308
1309 PropertyIteratorObject* js::GetIteratorWithIndices(JSContext* cx,
1310                                                    HandleObject obj) {
1311   return GetIteratorImpl<true>(cx, obj);
1312 }
1313
1314 PropertyIteratorObject* js::LookupInIteratorCache(JSContext* cx,
1315                                                   HandleObject obj) {
1316   uint32_t dummy = 0;
1317   return LookupInIteratorCache(cx, obj, &dummy);
1318 }
1319
1320 PropertyIteratorObject* js::LookupInShapeIteratorCache(JSContext* cx,
1321                                                        HandleObject obj) {
1322   uint32_t dummy = 0;
1323   return LookupInShapeIteratorCache(cx, obj, &dummy);
1324 }
1325
1326 // ES 2017 draft 7.4.7.
1327 PlainObject* js::CreateIterResultObject(JSContext* cx, HandleValue value,
1328                                         bool done) {
1329   // Step 1 (implicit).
1330
1331   // Step 2.
1332   Rooted<PlainObject*> templateObject(
1333       cx, GlobalObject::getOrCreateIterResultTemplateObject(cx));
1334   if (!templateObject) {
1335     return nullptr;
1336   }
1337
1338   PlainObject* resultObj = PlainObject::createWithTemplate(cx, templateObject);
1339   if (!resultObj) {
1340     return nullptr;
1341   }
1342
1343   // Step 3.
1344   resultObj->setSlot(GlobalObject::IterResultObjectValueSlot, value);
1345
1346   // Step 4.
1347   resultObj->setSlot(GlobalObject::IterResultObjectDoneSlot,
1348                      done ? TrueHandleValue : FalseHandleValue);
1349
1350   // Step 5.
1351   return resultObj;
1352 }
1353
1354 PlainObject* GlobalObject::getOrCreateIterResultTemplateObject(JSContext* cx) {
1355   HeapPtr<PlainObject*>& obj = cx->global()->data().iterResultTemplate;
1356   if (obj) {
1357     return obj;
1358   }
1359
1360   PlainObject* templateObj =
1361       createIterResultTemplateObject(cx, WithObjectPrototype::Yes);
1362   obj.init(templateObj);
1363   return obj;
1364 }
1365
1366 /* static */
1367 PlainObject* GlobalObject::getOrCreateIterResultWithoutPrototypeTemplateObject(
1368     JSContext* cx) {
1369   HeapPtr<PlainObject*>& obj =
1370       cx->global()->data().iterResultWithoutPrototypeTemplate;
1371   if (obj) {
1372     return obj;
1373   }
1374
1375   PlainObject* templateObj =
1376       createIterResultTemplateObject(cx, WithObjectPrototype::No);
1377   obj.init(templateObj);
1378   return obj;
1379 }
1380
1381 /* static */
1382 PlainObject* GlobalObject::createIterResultTemplateObject(
1383     JSContext* cx, WithObjectPrototype withProto) {
1384   // Create template plain object
1385   Rooted<PlainObject*> templateObject(
1386       cx, withProto == WithObjectPrototype::Yes
1387               ? NewPlainObject(cx, TenuredObject)
1388               : NewPlainObjectWithProto(cx, nullptr));
1389   if (!templateObject) {
1390     return nullptr;
1391   }
1392
1393   // Set dummy `value` property
1394   if (!NativeDefineDataProperty(cx, templateObject, cx->names().value,
1395                                 UndefinedHandleValue, JSPROP_ENUMERATE)) {
1396     return nullptr;
1397   }
1398
1399   // Set dummy `done` property
1400   if (!NativeDefineDataProperty(cx, templateObject, cx->names().done,
1401                                 TrueHandleValue, JSPROP_ENUMERATE)) {
1402     return nullptr;
1403   }
1404
1405 #ifdef DEBUG
1406   // Make sure that the properties are in the right slots.
1407   ShapePropertyIter<NoGC> iter(templateObject->shape());
1408   MOZ_ASSERT(iter->slot() == GlobalObject::IterResultObjectDoneSlot &&
1409              iter->key() == NameToId(cx->names().done));
1410   iter++;
1411   MOZ_ASSERT(iter->slot() == GlobalObject::IterResultObjectValueSlot &&
1412              iter->key() == NameToId(cx->names().value));
1413 #endif
1414
1415   return templateObject;
1416 }
1417
1418 /*** Iterator objects *******************************************************/
1419
1420 size_t PropertyIteratorObject::sizeOfMisc(
1421     mozilla::MallocSizeOf mallocSizeOf) const {
1422   return mallocSizeOf(getNativeIterator());
1423 }
1424
1425 void PropertyIteratorObject::trace(JSTracer* trc, JSObject* obj) {
1426   if (NativeIterator* ni =
1427           obj->as<PropertyIteratorObject>().getNativeIterator()) {
1428     ni->trace(trc);
1429   }
1430 }
1431
1432 void PropertyIteratorObject::finalize(JS::GCContext* gcx, JSObject* obj) {
1433   if (NativeIterator* ni =
1434           obj->as<PropertyIteratorObject>().getNativeIterator()) {
1435     gcx->free_(obj, ni, ni->allocationSize(), MemoryUse::NativeIterator);
1436   }
1437 }
1438
1439 const JSClassOps PropertyIteratorObject::classOps_ = {
1440     nullptr,   // addProperty
1441     nullptr,   // delProperty
1442     nullptr,   // enumerate
1443     nullptr,   // newEnumerate
1444     nullptr,   // resolve
1445     nullptr,   // mayResolve
1446     finalize,  // finalize
1447     nullptr,   // call
1448     nullptr,   // construct
1449     trace,     // trace
1450 };
1451
1452 const JSClass PropertyIteratorObject::class_ = {
1453     "Iterator",
1454     JSCLASS_HAS_RESERVED_SLOTS(SlotCount) | JSCLASS_BACKGROUND_FINALIZE,
1455     &PropertyIteratorObject::classOps_};
1456
1457 static const JSClass ArrayIteratorPrototypeClass = {"Array Iterator", 0};
1458
1459 enum {
1460   ArrayIteratorSlotIteratedObject,
1461   ArrayIteratorSlotNextIndex,
1462   ArrayIteratorSlotItemKind,
1463   ArrayIteratorSlotCount
1464 };
1465
1466 const JSClass ArrayIteratorObject::class_ = {
1467     "Array Iterator", JSCLASS_HAS_RESERVED_SLOTS(ArrayIteratorSlotCount)};
1468
1469 ArrayIteratorObject* js::NewArrayIteratorTemplate(JSContext* cx) {
1470   RootedObject proto(
1471       cx, GlobalObject::getOrCreateArrayIteratorPrototype(cx, cx->global()));
1472   if (!proto) {
1473     return nullptr;
1474   }
1475
1476   return NewTenuredObjectWithGivenProto<ArrayIteratorObject>(cx, proto);
1477 }
1478
1479 ArrayIteratorObject* js::NewArrayIterator(JSContext* cx) {
1480   RootedObject proto(
1481       cx, GlobalObject::getOrCreateArrayIteratorPrototype(cx, cx->global()));
1482   if (!proto) {
1483     return nullptr;
1484   }
1485
1486   return NewObjectWithGivenProto<ArrayIteratorObject>(cx, proto);
1487 }
1488
1489 static const JSFunctionSpec array_iterator_methods[] = {
1490     JS_SELF_HOSTED_FN("next", "ArrayIteratorNext", 0, 0), JS_FS_END};
1491
1492 static const JSClass StringIteratorPrototypeClass = {"String Iterator", 0};
1493
1494 enum {
1495   StringIteratorSlotIteratedObject,
1496   StringIteratorSlotNextIndex,
1497   StringIteratorSlotCount
1498 };
1499
1500 const JSClass StringIteratorObject::class_ = {
1501     "String Iterator", JSCLASS_HAS_RESERVED_SLOTS(StringIteratorSlotCount)};
1502
1503 static const JSFunctionSpec string_iterator_methods[] = {
1504     JS_SELF_HOSTED_FN("next", "StringIteratorNext", 0, 0), JS_FS_END};
1505
1506 StringIteratorObject* js::NewStringIteratorTemplate(JSContext* cx) {
1507   RootedObject proto(
1508       cx, GlobalObject::getOrCreateStringIteratorPrototype(cx, cx->global()));
1509   if (!proto) {
1510     return nullptr;
1511   }
1512
1513   return NewTenuredObjectWithGivenProto<StringIteratorObject>(cx, proto);
1514 }
1515
1516 StringIteratorObject* js::NewStringIterator(JSContext* cx) {
1517   RootedObject proto(
1518       cx, GlobalObject::getOrCreateStringIteratorPrototype(cx, cx->global()));
1519   if (!proto) {
1520     return nullptr;
1521   }
1522
1523   return NewObjectWithGivenProto<StringIteratorObject>(cx, proto);
1524 }
1525
1526 static const JSClass RegExpStringIteratorPrototypeClass = {
1527     "RegExp String Iterator", 0};
1528
1529 enum {
1530   // The regular expression used for iteration. May hold the original RegExp
1531   // object when it is reused instead of a new RegExp object.
1532   RegExpStringIteratorSlotRegExp,
1533
1534   // The String value being iterated upon.
1535   RegExpStringIteratorSlotString,
1536
1537   // The source string of the original RegExp object. Used to validate we can
1538   // reuse the original RegExp object for matching.
1539   RegExpStringIteratorSlotSource,
1540
1541   // The flags of the original RegExp object.
1542   RegExpStringIteratorSlotFlags,
1543
1544   // When non-negative, this slot holds the current lastIndex position when
1545   // reusing the original RegExp object for matching. When set to |-1|, the
1546   // iterator has finished. When set to any other negative value, the
1547   // iterator is not yet exhausted and we're not on the fast path and we're
1548   // not reusing the input RegExp object.
1549   RegExpStringIteratorSlotLastIndex,
1550
1551   RegExpStringIteratorSlotCount
1552 };
1553
1554 static_assert(RegExpStringIteratorSlotRegExp ==
1555                   REGEXP_STRING_ITERATOR_REGEXP_SLOT,
1556               "RegExpStringIteratorSlotRegExp must match self-hosting define "
1557               "for regexp slot.");
1558 static_assert(RegExpStringIteratorSlotString ==
1559                   REGEXP_STRING_ITERATOR_STRING_SLOT,
1560               "RegExpStringIteratorSlotString must match self-hosting define "
1561               "for string slot.");
1562 static_assert(RegExpStringIteratorSlotSource ==
1563                   REGEXP_STRING_ITERATOR_SOURCE_SLOT,
1564               "RegExpStringIteratorSlotString must match self-hosting define "
1565               "for source slot.");
1566 static_assert(RegExpStringIteratorSlotFlags ==
1567                   REGEXP_STRING_ITERATOR_FLAGS_SLOT,
1568               "RegExpStringIteratorSlotFlags must match self-hosting define "
1569               "for flags slot.");
1570 static_assert(RegExpStringIteratorSlotLastIndex ==
1571                   REGEXP_STRING_ITERATOR_LASTINDEX_SLOT,
1572               "RegExpStringIteratorSlotLastIndex must match self-hosting "
1573               "define for lastIndex slot.");
1574
1575 const JSClass RegExpStringIteratorObject::class_ = {
1576     "RegExp String Iterator",
1577     JSCLASS_HAS_RESERVED_SLOTS(RegExpStringIteratorSlotCount)};
1578
1579 static const JSFunctionSpec regexp_string_iterator_methods[] = {
1580     JS_SELF_HOSTED_FN("next", "RegExpStringIteratorNext", 0, 0),
1581
1582     JS_FS_END};
1583
1584 RegExpStringIteratorObject* js::NewRegExpStringIteratorTemplate(JSContext* cx) {
1585   RootedObject proto(cx, GlobalObject::getOrCreateRegExpStringIteratorPrototype(
1586                              cx, cx->global()));
1587   if (!proto) {
1588     return nullptr;
1589   }
1590
1591   return NewTenuredObjectWithGivenProto<RegExpStringIteratorObject>(cx, proto);
1592 }
1593
1594 RegExpStringIteratorObject* js::NewRegExpStringIterator(JSContext* cx) {
1595   RootedObject proto(cx, GlobalObject::getOrCreateRegExpStringIteratorPrototype(
1596                              cx, cx->global()));
1597   if (!proto) {
1598     return nullptr;
1599   }
1600
1601   return NewObjectWithGivenProto<RegExpStringIteratorObject>(cx, proto);
1602 }
1603
1604 // static
1605 PropertyIteratorObject* GlobalObject::getOrCreateEmptyIterator(JSContext* cx) {
1606   if (!cx->global()->data().emptyIterator) {
1607     RootedIdVector props(cx);  // Empty
1608     PropertyIteratorObject* iter =
1609         CreatePropertyIterator(cx, nullptr, props, false, nullptr, 0);
1610     if (!iter) {
1611       return nullptr;
1612     }
1613     iter->getNativeIterator()->markEmptyIteratorSingleton();
1614     cx->global()->data().emptyIterator.init(iter);
1615   }
1616   return cx->global()->data().emptyIterator;
1617 }
1618
1619 PropertyIteratorObject* js::ValueToIterator(JSContext* cx, HandleValue vp) {
1620   RootedObject obj(cx);
1621   if (vp.isObject()) {
1622     /* Common case. */
1623     obj = &vp.toObject();
1624   } else if (vp.isNullOrUndefined()) {
1625     /*
1626      * Enumerating over null and undefined gives an empty enumerator, so
1627      * that |for (var p in <null or undefined>) <loop>;| never executes
1628      * <loop>, per ES5 12.6.4.
1629      */
1630     return GlobalObject::getOrCreateEmptyIterator(cx);
1631   } else {
1632     obj = ToObject(cx, vp);
1633     if (!obj) {
1634       return nullptr;
1635     }
1636   }
1637
1638   return GetIterator(cx, obj);
1639 }
1640
1641 void js::CloseIterator(JSObject* obj) {
1642   if (!obj->is<PropertyIteratorObject>()) {
1643     return;
1644   }
1645
1646   // Remove iterator from the active list, which is a stack. The shared iterator
1647   // used for for-in with null/undefined is immutable and unlinked.
1648
1649   NativeIterator* ni = obj->as<PropertyIteratorObject>().getNativeIterator();
1650   if (ni->isEmptyIteratorSingleton()) {
1651     return;
1652   }
1653
1654   ni->unlink();
1655
1656   MOZ_ASSERT(ni->isActive());
1657   ni->markInactive();
1658
1659   ni->clearObjectBeingIterated();
1660
1661   // Reset the enumerator; it may still be in the cached iterators for
1662   // this thread and can be reused.
1663   ni->resetPropertyCursorForReuse();
1664 }
1665
1666 bool js::IteratorCloseForException(JSContext* cx, HandleObject obj) {
1667   MOZ_ASSERT(cx->isExceptionPending());
1668
1669   bool isClosingGenerator = cx->isClosingGenerator();
1670   JS::AutoSaveExceptionState savedExc(cx);
1671
1672   // Implements IteratorClose (ES 7.4.6) for exception unwinding. See
1673   // also the bytecode generated by BytecodeEmitter::emitIteratorClose.
1674
1675   // Step 3.
1676   //
1677   // Get the "return" method.
1678   RootedValue returnMethod(cx);
1679   if (!GetProperty(cx, obj, obj, cx->names().return_, &returnMethod)) {
1680     return false;
1681   }
1682
1683   // Step 4.
1684   //
1685   // Do nothing if "return" is null or undefined. Throw a TypeError if the
1686   // method is not IsCallable.
1687   if (returnMethod.isNullOrUndefined()) {
1688     return true;
1689   }
1690   if (!IsCallable(returnMethod)) {
1691     return ReportIsNotFunction(cx, returnMethod);
1692   }
1693
1694   // Step 5, 6, 8.
1695   //
1696   // Call "return" if it is not null or undefined.
1697   RootedValue rval(cx);
1698   bool ok = Call(cx, returnMethod, obj, &rval);
1699   if (isClosingGenerator) {
1700     // Closing an iterator is implemented as an exception, but in spec
1701     // terms it is a Completion value with [[Type]] return. In this case
1702     // we *do* care if the call threw and if it returned an object.
1703     if (!ok) {
1704       return false;
1705     }
1706     if (!rval.isObject()) {
1707       return ThrowCheckIsObject(cx, CheckIsObjectKind::IteratorReturn);
1708     }
1709   } else {
1710     // We don't care if the call threw or that it returned an Object, as
1711     // Step 6 says if IteratorClose is being called during a throw, the
1712     // original throw has primacy.
1713     savedExc.restore();
1714   }
1715
1716   return true;
1717 }
1718
1719 void js::UnwindIteratorForUncatchableException(JSObject* obj) {
1720   if (obj->is<PropertyIteratorObject>()) {
1721     NativeIterator* ni = obj->as<PropertyIteratorObject>().getNativeIterator();
1722     if (ni->isEmptyIteratorSingleton()) {
1723       return;
1724     }
1725     ni->unlink();
1726   }
1727 }
1728
1729 static bool SuppressDeletedProperty(JSContext* cx, NativeIterator* ni,
1730                                     HandleObject obj,
1731                                     Handle<JSLinearString*> str) {
1732   if (ni->objectBeingIterated() != obj) {
1733     return true;
1734   }
1735
1736   ni->disableIndices();
1737
1738   // Optimization for the following common case:
1739   //
1740   //    for (var p in o) {
1741   //        delete o[p];
1742   //    }
1743   //
1744   // Note that usually both strings will be atoms so we only check for pointer
1745   // equality here.
1746   if (ni->previousPropertyWas(str)) {
1747     return true;
1748   }
1749
1750   while (true) {
1751     bool restart = false;
1752
1753     // Check whether id is still to come.
1754     GCPtr<JSLinearString*>* const cursor = ni->nextProperty();
1755     GCPtr<JSLinearString*>* const end = ni->propertiesEnd();
1756     for (GCPtr<JSLinearString*>* idp = cursor; idp < end; ++idp) {
1757       // Common case: both strings are atoms.
1758       if ((*idp)->isAtom() && str->isAtom()) {
1759         if (*idp != str) {
1760           continue;
1761         }
1762       } else {
1763         if (!EqualStrings(*idp, str)) {
1764           continue;
1765         }
1766       }
1767
1768       // Check whether another property along the prototype chain became
1769       // visible as a result of this deletion.
1770       RootedObject proto(cx);
1771       if (!GetPrototype(cx, obj, &proto)) {
1772         return false;
1773       }
1774       if (proto) {
1775         RootedId id(cx);
1776         RootedValue idv(cx, StringValue(*idp));
1777         if (!PrimitiveValueToId<CanGC>(cx, idv, &id)) {
1778           return false;
1779         }
1780
1781         Rooted<mozilla::Maybe<PropertyDescriptor>> desc(cx);
1782         RootedObject holder(cx);
1783         if (!GetPropertyDescriptor(cx, proto, id, &desc, &holder)) {
1784           return false;
1785         }
1786
1787         if (desc.isSome() && desc->enumerable()) {
1788           continue;
1789         }
1790       }
1791
1792       // If GetPropertyDescriptor above removed a property from ni, start
1793       // over.
1794       if (end != ni->propertiesEnd() || cursor != ni->nextProperty()) {
1795         restart = true;
1796         break;
1797       }
1798
1799       // No property along the prototype chain stepped in to take the
1800       // property's place, so go ahead and delete id from the list.
1801       // If it is the next property to be enumerated, just skip it.
1802       if (idp == cursor) {
1803         ni->incCursor();
1804       } else {
1805         for (GCPtr<JSLinearString*>* p = idp; p + 1 != end; p++) {
1806           *p = *(p + 1);
1807         }
1808
1809         ni->trimLastProperty();
1810       }
1811
1812       ni->markHasUnvisitedPropertyDeletion();
1813       return true;
1814     }
1815
1816     if (!restart) {
1817       return true;
1818     }
1819   }
1820 }
1821
1822 /*
1823  * Suppress enumeration of deleted properties. This function must be called
1824  * when a property is deleted and there might be active enumerators.
1825  *
1826  * We maintain a list of active non-escaping for-in enumerators. To suppress
1827  * a property, we check whether each active enumerator contains the (obj, id)
1828  * pair and has not yet enumerated |id|. If so, and |id| is the next property,
1829  * we simply advance the cursor. Otherwise, we delete |id| from the list.
1830  *
1831  * We do not suppress enumeration of a property deleted along an object's
1832  * prototype chain. Only direct deletions on the object are handled.
1833  */
1834 static bool SuppressDeletedPropertyHelper(JSContext* cx, HandleObject obj,
1835                                           Handle<JSLinearString*> str) {
1836   NativeIteratorListIter iter(obj->compartment()->enumeratorsAddr());
1837   while (!iter.done()) {
1838     NativeIterator* ni = iter.next();
1839     if (!SuppressDeletedProperty(cx, ni, obj, str)) {
1840       return false;
1841     }
1842   }
1843
1844   return true;
1845 }
1846
1847 bool js::SuppressDeletedProperty(JSContext* cx, HandleObject obj, jsid id) {
1848   if (MOZ_LIKELY(!obj->compartment()->objectMaybeInIteration(obj))) {
1849     return true;
1850   }
1851
1852   if (id.isSymbol()) {
1853     return true;
1854   }
1855
1856   Rooted<JSLinearString*> str(cx, IdToString(cx, id));
1857   if (!str) {
1858     return false;
1859   }
1860   return SuppressDeletedPropertyHelper(cx, obj, str);
1861 }
1862
1863 bool js::SuppressDeletedElement(JSContext* cx, HandleObject obj,
1864                                 uint32_t index) {
1865   if (MOZ_LIKELY(!obj->compartment()->objectMaybeInIteration(obj))) {
1866     return true;
1867   }
1868
1869   RootedId id(cx);
1870   if (!IndexToId(cx, index, &id)) {
1871     return false;
1872   }
1873
1874   Rooted<JSLinearString*> str(cx, IdToString(cx, id));
1875   if (!str) {
1876     return false;
1877   }
1878   return SuppressDeletedPropertyHelper(cx, obj, str);
1879 }
1880
1881 #ifdef DEBUG
1882 void js::AssertDenseElementsNotIterated(NativeObject* obj) {
1883   // Search for active iterators for |obj| and assert they don't contain any
1884   // property keys that are dense elements. This is used to check correctness
1885   // of the MAYBE_IN_ITERATION flag on ObjectElements.
1886   //
1887   // Ignore iterators that may contain indexed properties from objects on the
1888   // prototype chain, as that can result in false positives. See bug 1656744.
1889
1890   // Limit the number of properties we check to avoid slowing down debug builds
1891   // too much.
1892   static constexpr uint32_t MaxPropsToCheck = 10;
1893   uint32_t propsChecked = 0;
1894
1895   NativeIteratorListIter iter(obj->compartment()->enumeratorsAddr());
1896   while (!iter.done()) {
1897     NativeIterator* ni = iter.next();
1898     if (ni->objectBeingIterated() == obj &&
1899         !ni->maybeHasIndexedPropertiesFromProto()) {
1900       for (GCPtr<JSLinearString*>* idp = ni->nextProperty();
1901            idp < ni->propertiesEnd(); ++idp) {
1902         uint32_t index;
1903         if (idp->get()->isIndex(&index)) {
1904           MOZ_ASSERT(!obj->containsDenseElement(index));
1905         }
1906         if (++propsChecked > MaxPropsToCheck) {
1907           return;
1908         }
1909       }
1910     }
1911   }
1912 }
1913 #endif
1914
1915 static const JSFunctionSpec iterator_methods[] = {
1916     JS_SELF_HOSTED_SYM_FN(iterator, "IteratorIdentity", 0, 0),
1917     JS_FS_END,
1918 };
1919
1920 static const JSFunctionSpec iterator_static_methods[] = {
1921     JS_SELF_HOSTED_FN("from", "IteratorFrom", 1, 0),
1922     JS_FS_END,
1923 };
1924
1925 // These methods are only attached to Iterator.prototype when the
1926 // Iterator Helpers feature is enabled.
1927 static const JSFunctionSpec iterator_methods_with_helpers[] = {
1928     JS_SELF_HOSTED_FN("map", "IteratorMap", 1, 0),
1929     JS_SELF_HOSTED_FN("filter", "IteratorFilter", 1, 0),
1930     JS_SELF_HOSTED_FN("take", "IteratorTake", 1, 0),
1931     JS_SELF_HOSTED_FN("drop", "IteratorDrop", 1, 0),
1932     JS_SELF_HOSTED_FN("flatMap", "IteratorFlatMap", 1, 0),
1933     JS_SELF_HOSTED_FN("reduce", "IteratorReduce", 1, 0),
1934     JS_SELF_HOSTED_FN("toArray", "IteratorToArray", 0, 0),
1935     JS_SELF_HOSTED_FN("forEach", "IteratorForEach", 1, 0),
1936     JS_SELF_HOSTED_FN("some", "IteratorSome", 1, 0),
1937     JS_SELF_HOSTED_FN("every", "IteratorEvery", 1, 0),
1938     JS_SELF_HOSTED_FN("find", "IteratorFind", 1, 0),
1939     JS_SELF_HOSTED_SYM_FN(iterator, "IteratorIdentity", 0, 0),
1940     JS_FS_END,
1941 };
1942
1943 static const JSPropertySpec iterator_properties[] = {
1944     // NOTE: Contrary to most other @@toStringTag properties, this property is
1945     // writable.
1946     JS_STRING_SYM_PS(toStringTag, "Iterator", 0),
1947     JS_PS_END,
1948 };
1949
1950 /* static */
1951 bool GlobalObject::initIteratorProto(JSContext* cx,
1952                                      Handle<GlobalObject*> global) {
1953   if (global->hasBuiltinProto(ProtoKind::IteratorProto)) {
1954     return true;
1955   }
1956
1957   RootedObject proto(
1958       cx, GlobalObject::createBlankPrototype<PlainObject>(cx, global));
1959   if (!proto) {
1960     return false;
1961   }
1962
1963   // %IteratorPrototype%.map.[[Prototype]] is %Generator% and
1964   // %Generator%.prototype.[[Prototype]] is %IteratorPrototype%.
1965   // Populate the slot early, to prevent runaway mutual recursion.
1966   global->initBuiltinProto(ProtoKind::IteratorProto, proto);
1967
1968   if (!DefinePropertiesAndFunctions(cx, proto, nullptr, iterator_methods)) {
1969     // In this case, we leave a partially initialized object in the
1970     // slot. There's no obvious way to do better, since this object may already
1971     // be in the prototype chain of %GeneratorPrototype%.
1972     return false;
1973   }
1974
1975   return true;
1976 }
1977
1978 /* static */
1979 template <GlobalObject::ProtoKind Kind, const JSClass* ProtoClass,
1980           const JSFunctionSpec* Methods, const bool needsFuseProperty>
1981 bool GlobalObject::initObjectIteratorProto(JSContext* cx,
1982                                            Handle<GlobalObject*> global,
1983                                            Handle<JSAtom*> tag) {
1984   if (global->hasBuiltinProto(Kind)) {
1985     return true;
1986   }
1987
1988   RootedObject iteratorProto(
1989       cx, GlobalObject::getOrCreateIteratorPrototype(cx, global));
1990   if (!iteratorProto) {
1991     return false;
1992   }
1993
1994   RootedObject proto(cx, GlobalObject::createBlankPrototypeInheriting(
1995                              cx, ProtoClass, iteratorProto));
1996   if (!proto || !DefinePropertiesAndFunctions(cx, proto, nullptr, Methods) ||
1997       (tag && !DefineToStringTag(cx, proto, tag))) {
1998     return false;
1999   }
2000
2001   if constexpr (needsFuseProperty) {
2002     if (!JSObject::setHasFuseProperty(cx, proto)) {
2003       return false;
2004     }
2005   }
2006
2007   global->initBuiltinProto(Kind, proto);
2008   return true;
2009 }
2010
2011 /* static */
2012 NativeObject* GlobalObject::getOrCreateArrayIteratorPrototype(
2013     JSContext* cx, Handle<GlobalObject*> global) {
2014   return MaybeNativeObject(getOrCreateBuiltinProto(
2015       cx, global, ProtoKind::ArrayIteratorProto,
2016       cx->names().Array_Iterator_.toHandle(),
2017       initObjectIteratorProto<
2018           ProtoKind::ArrayIteratorProto, &ArrayIteratorPrototypeClass,
2019           array_iterator_methods, /* hasFuseProperty= */ true>));
2020 }
2021
2022 /* static */
2023 JSObject* GlobalObject::getOrCreateStringIteratorPrototype(
2024     JSContext* cx, Handle<GlobalObject*> global) {
2025   return getOrCreateBuiltinProto(
2026       cx, global, ProtoKind::StringIteratorProto,
2027       cx->names().String_Iterator_.toHandle(),
2028       initObjectIteratorProto<ProtoKind::StringIteratorProto,
2029                               &StringIteratorPrototypeClass,
2030                               string_iterator_methods>);
2031 }
2032
2033 /* static */
2034 JSObject* GlobalObject::getOrCreateRegExpStringIteratorPrototype(
2035     JSContext* cx, Handle<GlobalObject*> global) {
2036   return getOrCreateBuiltinProto(
2037       cx, global, ProtoKind::RegExpStringIteratorProto,
2038       cx->names().RegExp_String_Iterator_.toHandle(),
2039       initObjectIteratorProto<ProtoKind::RegExpStringIteratorProto,
2040                               &RegExpStringIteratorPrototypeClass,
2041                               regexp_string_iterator_methods>);
2042 }
2043
2044 // Iterator Helper Proposal 2.1.3.1 Iterator()
2045 // https://tc39.es/proposal-iterator-helpers/#sec-iterator as of revision
2046 // ed6e15a
2047 static bool IteratorConstructor(JSContext* cx, unsigned argc, Value* vp) {
2048   CallArgs args = CallArgsFromVp(argc, vp);
2049
2050   // Step 1.
2051   if (!ThrowIfNotConstructing(cx, args, "Iterator")) {
2052     return false;
2053   }
2054   // Throw TypeError if NewTarget is the active function object, preventing the
2055   // Iterator constructor from being used directly.
2056   if (args.callee() == args.newTarget().toObject()) {
2057     JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
2058                               JSMSG_BOGUS_CONSTRUCTOR, "Iterator");
2059     return false;
2060   }
2061
2062   // Step 2.
2063   RootedObject proto(cx);
2064   if (!GetPrototypeFromBuiltinConstructor(cx, args, JSProto_Iterator, &proto)) {
2065     return false;
2066   }
2067
2068   JSObject* obj = NewObjectWithClassProto<IteratorObject>(cx, proto);
2069   if (!obj) {
2070     return false;
2071   }
2072
2073   args.rval().setObject(*obj);
2074   return true;
2075 }
2076
2077 static const ClassSpec IteratorObjectClassSpec = {
2078     GenericCreateConstructor<IteratorConstructor, 0, gc::AllocKind::FUNCTION>,
2079     GenericCreatePrototype<IteratorObject>,
2080     iterator_static_methods,
2081     nullptr,
2082     iterator_methods_with_helpers,
2083     iterator_properties,
2084     nullptr,
2085 };
2086
2087 const JSClass IteratorObject::class_ = {
2088     "Iterator",
2089     JSCLASS_HAS_CACHED_PROTO(JSProto_Iterator),
2090     JS_NULL_CLASS_OPS,
2091     &IteratorObjectClassSpec,
2092 };
2093
2094 const JSClass IteratorObject::protoClass_ = {
2095     "Iterator.prototype",
2096     JSCLASS_HAS_CACHED_PROTO(JSProto_Iterator),
2097     JS_NULL_CLASS_OPS,
2098     &IteratorObjectClassSpec,
2099 };
2100
2101 // Set up WrapForValidIteratorObject class and its prototype.
2102 static const JSFunctionSpec wrap_for_valid_iterator_methods[] = {
2103     JS_SELF_HOSTED_FN("next", "WrapForValidIteratorNext", 0, 0),
2104     JS_SELF_HOSTED_FN("return", "WrapForValidIteratorReturn", 0, 0),
2105     JS_FS_END,
2106 };
2107
2108 static const JSClass WrapForValidIteratorPrototypeClass = {
2109     "Wrap For Valid Iterator", 0};
2110
2111 const JSClass WrapForValidIteratorObject::class_ = {
2112     "Wrap For Valid Iterator",
2113     JSCLASS_HAS_RESERVED_SLOTS(WrapForValidIteratorObject::SlotCount),
2114 };
2115
2116 /* static */
2117 NativeObject* GlobalObject::getOrCreateWrapForValidIteratorPrototype(
2118     JSContext* cx, Handle<GlobalObject*> global) {
2119   return MaybeNativeObject(getOrCreateBuiltinProto(
2120       cx, global, ProtoKind::WrapForValidIteratorProto,
2121       Handle<JSAtom*>(nullptr),
2122       initObjectIteratorProto<ProtoKind::WrapForValidIteratorProto,
2123                               &WrapForValidIteratorPrototypeClass,
2124                               wrap_for_valid_iterator_methods>));
2125 }
2126
2127 WrapForValidIteratorObject* js::NewWrapForValidIterator(JSContext* cx) {
2128   RootedObject proto(cx, GlobalObject::getOrCreateWrapForValidIteratorPrototype(
2129                              cx, cx->global()));
2130   if (!proto) {
2131     return nullptr;
2132   }
2133   return NewObjectWithGivenProto<WrapForValidIteratorObject>(cx, proto);
2134 }
2135
2136 // Common iterator object returned by Iterator Helper methods.
2137 static const JSFunctionSpec iterator_helper_methods[] = {
2138     JS_SELF_HOSTED_FN("next", "IteratorHelperNext", 0, 0),
2139     JS_SELF_HOSTED_FN("return", "IteratorHelperReturn", 0, 0),
2140     JS_FS_END,
2141 };
2142
2143 static const JSClass IteratorHelperPrototypeClass = {"Iterator Helper", 0};
2144
2145 const JSClass IteratorHelperObject::class_ = {
2146     "Iterator Helper",
2147     JSCLASS_HAS_RESERVED_SLOTS(IteratorHelperObject::SlotCount),
2148 };
2149
2150 /* static */
2151 NativeObject* GlobalObject::getOrCreateIteratorHelperPrototype(
2152     JSContext* cx, Handle<GlobalObject*> global) {
2153   return MaybeNativeObject(getOrCreateBuiltinProto(
2154       cx, global, ProtoKind::IteratorHelperProto,
2155       cx->names().Iterator_Helper_.toHandle(),
2156       initObjectIteratorProto<ProtoKind::IteratorHelperProto,
2157                               &IteratorHelperPrototypeClass,
2158                               iterator_helper_methods>));
2159 }
2160
2161 IteratorHelperObject* js::NewIteratorHelper(JSContext* cx) {
2162   RootedObject proto(
2163       cx, GlobalObject::getOrCreateIteratorHelperPrototype(cx, cx->global()));
2164   if (!proto) {
2165     return nullptr;
2166   }
2167   return NewObjectWithGivenProto<IteratorHelperObject>(cx, proto);
2168 }
2169
2170 bool js::IterableToArray(JSContext* cx, HandleValue iterable,
2171                          MutableHandle<ArrayObject*> array) {
2172   JS::ForOfIterator iterator(cx);
2173   if (!iterator.init(iterable, JS::ForOfIterator::ThrowOnNonIterable)) {
2174     return false;
2175   }
2176
2177   array.set(NewDenseEmptyArray(cx));
2178   if (!array) {
2179     return false;
2180   }
2181
2182   RootedValue nextValue(cx);
2183   while (true) {
2184     bool done;
2185     if (!iterator.next(&nextValue, &done)) {
2186       return false;
2187     }
2188     if (done) {
2189       break;
2190     }
2191
2192     if (!NewbornArrayPush(cx, array, nextValue)) {
2193       return false;
2194     }
2195   }
2196   return true;
2197 }