The Tor Browser: js/src/builtin/MapObject.cpp@6474c204b198 (annotated)

js/src/builtin/MapObject.cpp@6474c204b198 (annotated)

js/src/builtin/MapObject.cpp

Wed, 31 Dec 2014 06:09:35 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Wed, 31 Dec 2014 06:09:35 +0100
changeset 0: 6474c204b198
permissions: -rw-r--r--

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  * vim: set ts=8 sts=4 et sw=4 tw=99:
  * 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/. */
 #include "builtin/MapObject.h"
 #include "mozilla/Move.h"
 #include "jscntxt.h"
 #include "jsiter.h"
 #include "jsobj.h"
 #include "gc/Marking.h"
 #include "js/Utility.h"
 #include "vm/GlobalObject.h"
 #include "vm/Interpreter.h"
 #include "jsobjinlines.h"
 using namespace js;
 using mozilla::NumberEqualsInt32;
 using mozilla::Forward;
 using mozilla::IsNaN;
 using mozilla::Move;
 using mozilla::ArrayLength;
 using JS::DoubleNaNValue;
 using JS::ForOfIterator;
 /*** OrderedHashTable ****************************************************************************/
 /*
  * Define two collection templates, js::OrderedHashMap and js::OrderedHashSet.
  * They are like js::HashMap and js::HashSet except that:
  *
  *   - Iterating over an Ordered hash table visits the entries in the order in
  *     which they were inserted. This means that unlike a HashMap, the behavior
  *     of an OrderedHashMap is deterministic (as long as the HashPolicy methods
  *     are effect-free and consistent); the hashing is a pure performance
  *     optimization.
  *
  *   - Range objects over Ordered tables remain valid even when entries are
  *     added or removed or the table is resized. (However in the case of
  *     removing entries, note the warning on class Range below.)
  *
  *   - The API is a little different, so it's not a drop-in replacement.
  *     In particular, the hash policy is a little different.
  *     Also, the Ordered templates lack the Ptr and AddPtr types.
  *
  * Hash policies
  *
  * See the comment about "Hash policy" in HashTable.h for general features that
  * hash policy classes must provide. Hash policies for OrderedHashMaps and Sets
  * must additionally provide a distinguished "empty" key value and the
  * following static member functions:
  *     bool isEmpty(const Key &);
  *     void makeEmpty(Key *);
  */
 namespace js {
 namespace detail {
 /*
  * detail::OrderedHashTable is the underlying data structure used to implement both
  * OrderedHashMap and OrderedHashSet. Programs should use one of those two
  * templates rather than OrderedHashTable.
  */
 template <class T, class Ops, class AllocPolicy>
 class OrderedHashTable
 {
   public:
     typedef typename Ops::KeyType Key;
     typedef typename Ops::Lookup Lookup;
     struct Data
     {
         T element;
         Data *chain;
         Data(const T &e, Data *c) : element(e), chain(c) {}
         Data(T &&e, Data *c) : element(Move(e)), chain(c) {}
     };
     class Range;
     friend class Range;
   private:
     Data **hashTable;           // hash table (has hashBuckets() elements)
     Data *data;                 // data vector, an array of Data objects
                                 // data[0:dataLength] are constructed
     uint32_t dataLength;        // number of constructed elements in data
     uint32_t dataCapacity;      // size of data, in elements
     uint32_t liveCount;         // dataLength less empty (removed) entries
     uint32_t hashShift;         // multiplicative hash shift
     Range *ranges;              // list of all live Ranges on this table
     AllocPolicy alloc;
   public:
     OrderedHashTable(AllocPolicy &ap)
         : hashTable(nullptr), data(nullptr), dataLength(0), ranges(nullptr), alloc(ap) {}
     bool init() {
         MOZ_ASSERT(!hashTable, "init must be called at most once");
         uint32_t buckets = initialBuckets();
         Data **tableAlloc = static_cast<Data **>(alloc.malloc_(buckets * sizeof(Data *)));
         if (!tableAlloc)
             return false;
         for (uint32_t i = 0; i < buckets; i++)
             tableAlloc[i] = nullptr;
         uint32_t capacity = uint32_t(buckets * fillFactor());
         Data *dataAlloc = static_cast<Data *>(alloc.malloc_(capacity * sizeof(Data)));
         if (!dataAlloc) {
             alloc.free_(tableAlloc);
             return false;
         }
         // clear() requires that members are assigned only after all allocation
         // has succeeded, and that this->ranges is left untouched.
         hashTable = tableAlloc;
         data = dataAlloc;
         dataLength = 0;
         dataCapacity = capacity;
         liveCount = 0;
         hashShift = HashNumberSizeBits - initialBucketsLog2();
         MOZ_ASSERT(hashBuckets() == buckets);
         return true;
     }
     ~OrderedHashTable() {
         for (Range *r = ranges, *next; r; r = next) {
             next = r->next;
             r->onTableDestroyed();
         }
         alloc.free_(hashTable);
         freeData(data, dataLength);
     }
     /* Return the number of elements in the table. */
     uint32_t count() const { return liveCount; }
     /* True if any element matches l. */
     bool has(const Lookup &l) const {
         return lookup(l) != nullptr;
     }
     /* Return a pointer to the element, if any, that matches l, or nullptr. */
     T *get(const Lookup &l) {
         Data *e = lookup(l, prepareHash(l));
         return e ? &e->element : nullptr;
     }
     /* Return a pointer to the element, if any, that matches l, or nullptr. */
     const T *get(const Lookup &l) const {
         return const_cast<OrderedHashTable *>(this)->get(l);
     }
     /*
      * If the table already contains an entry that matches |element|,
      * replace that entry with |element|. Otherwise add a new entry.
      *
      * On success, return true, whether there was already a matching element or
      * not. On allocation failure, return false. If this returns false, it
      * means the element was not added to the table.
      */
     template <typename ElementInput>
     bool put(ElementInput &&element) {
         HashNumber h = prepareHash(Ops::getKey(element));
         if (Data *e = lookup(Ops::getKey(element), h)) {
             e->element = Forward<ElementInput>(element);
             return true;
         }
         if (dataLength == dataCapacity) {
             // If the hashTable is more than 1/4 deleted data, simply rehash in
             // place to free up some space. Otherwise, grow the table.
             uint32_t newHashShift = liveCount >= dataCapacity * 0.75 ? hashShift - 1 : hashShift;
             if (!rehash(newHashShift))
                 return false;
         }
         h >>= hashShift;
         liveCount++;
         Data *e = &data[dataLength++];
         new (e) Data(Forward<ElementInput>(element), hashTable[h]);
         hashTable[h] = e;
         return true;
     }
     /*
      * If the table contains an element matching l, remove it and set *foundp
      * to true. Otherwise set *foundp to false.
      *
      * Return true on success, false if we tried to shrink the table and hit an
      * allocation failure. Even if this returns false, *foundp is set correctly
      * and the matching element was removed. Shrinking is an optimization and
      * it's OK for it to fail.
      */
     bool remove(const Lookup &l, bool *foundp) {
         // Note: This could be optimized so that removing the last entry,
         // data[dataLength - 1], decrements dataLength. LIFO use cases would
         // benefit.
         // If a matching entry exists, empty it.
         Data *e = lookup(l, prepareHash(l));
         if (e == nullptr) {
             *foundp = false;
             return true;
         }
         *foundp = true;
         liveCount--;
         Ops::makeEmpty(&e->element);
         // Update active Ranges.
         uint32_t pos = e - data;
         for (Range *r = ranges; r; r = r->next)
             r->onRemove(pos);
         // If many entries have been removed, try to shrink the table.
         if (hashBuckets() > initialBuckets() && liveCount < dataLength * minDataFill()) {
             if (!rehash(hashShift + 1))
                 return false;
         }
         return true;
     }
     /*
      * Remove all entries.
      *
      * Returns false on OOM, leaving the OrderedHashTable and any live Ranges
      * in the old state.
      *
      * The effect on live Ranges is the same as removing all entries; in
      * particular, those Ranges are still live and will see any entries added
      * after a successful clear().
      */
     bool clear() {
         if (dataLength != 0) {
             Data **oldHashTable = hashTable;
             Data *oldData = data;
             uint32_t oldDataLength = dataLength;
             hashTable = nullptr;
             if (!init()) {
                 // init() only mutates members on success; see comment above.
                 hashTable = oldHashTable;
                 return false;
             }
             alloc.free_(oldHashTable);
             freeData(oldData, oldDataLength);
             for (Range *r = ranges; r; r = r->next)
                 r->onClear();
         }
         MOZ_ASSERT(hashTable);
         MOZ_ASSERT(data);
         MOZ_ASSERT(dataLength == 0);
         MOZ_ASSERT(liveCount == 0);
         return true;
     }
     /*
      * Ranges are used to iterate over OrderedHashTables.
      *
      * Suppose 'Map' is some instance of OrderedHashMap, and 'map' is a Map.
      * Then you can walk all the key-value pairs like this:
      *
      *     for (Map::Range r = map.all(); !r.empty(); r.popFront()) {
      *         Map::Entry &pair = r.front();
      *         ... do something with pair ...
      *     }
      *
      * Ranges remain valid for the lifetime of the OrderedHashTable, even if
      * entries are added or removed or the table is resized. Don't do anything
      * to a Range, except destroy it, after the OrderedHashTable has been
      * destroyed. (We support destroying the two objects in either order to
      * humor the GC, bless its nondeterministic heart.)
      *
      * Warning: The behavior when the current front() entry is removed from the
      * table is subtly different from js::HashTable<>::Enum::removeFront()!
      * HashTable::Enum doesn't skip any entries when you removeFront() and then
      * popFront(). OrderedHashTable::Range does! (This is useful for using a
      * Range to implement JS Map.prototype.iterator.)
      *
      * The workaround is to call popFront() as soon as possible,
      * before there's any possibility of modifying the table:
      *
      *     for (Map::Range r = map.all(); !r.empty(); ) {
      *         Key key = r.front().key;         // this won't modify map
      *         Value val = r.front().value;     // this won't modify map
      *         r.popFront();
      *         // ...do things that might modify map...
      *     }
      */
     class Range
     {
         friend class OrderedHashTable;
         OrderedHashTable &ht;
         /* The index of front() within ht.data. */
         uint32_t i;
         /*
          * The number of nonempty entries in ht.data to the left of front().
          * This is used when the table is resized or compacted.
          */
         uint32_t count;
         /*
          * Links in the doubly-linked list of active Ranges on ht.
          *
          * prevp points to the previous Range's .next field;
          *   or to ht.ranges if this is the first Range in the list.
          * next points to the next Range;
          *   or nullptr if this is the last Range in the list.
          *
          * Invariant: *prevp == this.
          */
         Range **prevp;
         Range *next;
         /*
          * Create a Range over all the entries in ht.
          * (This is private on purpose. End users must use ht.all().)
          */
         Range(OrderedHashTable &ht) : ht(ht), i(0), count(0), prevp(&ht.ranges), next(ht.ranges) {
             *prevp = this;
             if (next)
                 next->prevp = &next;
             seek();
         }
       public:
         Range(const Range &other)
             : ht(other.ht), i(other.i), count(other.count), prevp(&ht.ranges), next(ht.ranges)
         {
             *prevp = this;
             if (next)
                 next->prevp = &next;
         }
         ~Range() {
             *prevp = next;
             if (next)
                 next->prevp = prevp;
         }
       private:
         // Prohibit copy assignment.
         Range &operator=(const Range &other) MOZ_DELETE;
         void seek() {
             while (i < ht.dataLength && Ops::isEmpty(Ops::getKey(ht.data[i].element)))
                 i++;
         }
         /*
          * The hash table calls this when an entry is removed.
          * j is the index of the removed entry.
          */
         void onRemove(uint32_t j) {
             MOZ_ASSERT(valid());
             if (j < i)
                 count--;
             if (j == i)
                 seek();
         }
         /*
          * The hash table calls this when the table is resized or compacted.
          * Since |count| is the number of nonempty entries to the left of
          * front(), discarding the empty entries will not affect count, and it
          * will make i and count equal.
          */
         void onCompact() {
             MOZ_ASSERT(valid());
             i = count;
         }
         /* The hash table calls this when cleared. */
         void onClear() {
             MOZ_ASSERT(valid());
             i = count = 0;
         }
         bool valid() const {
             return next != this;
         }
         void onTableDestroyed() {
             MOZ_ASSERT(valid());
             prevp = &next;
             next = this;
         }
       public:
         bool empty() const {
             MOZ_ASSERT(valid());
             return i >= ht.dataLength;
         }
         /*
          * Return the first element in the range. This must not be called if
          * this->empty().
          *
          * Warning: Removing an entry from the table also removes it from any
          * live Ranges, and a Range can become empty that way, rendering
          * front() invalid. If in doubt, check empty() before calling front().
          */
         T &front() {
             MOZ_ASSERT(valid());
             MOZ_ASSERT(!empty());
             return ht.data[i].element;
         }
         /*
          * Remove the first element from this range.
          * This must not be called if this->empty().
          *
          * Warning: Removing an entry from the table also removes it from any
          * live Ranges, and a Range can become empty that way, rendering
          * popFront() invalid. If in doubt, check empty() before calling
          * popFront().
          */
         void popFront() {
             MOZ_ASSERT(valid());
             MOZ_ASSERT(!empty());
             MOZ_ASSERT(!Ops::isEmpty(Ops::getKey(ht.data[i].element)));
             count++;
             i++;
             seek();
         }
         /*
          * Change the key of the front entry.
          *
          * This calls Ops::hash on both the current key and the new key.
          * Ops::hash on the current key must return the same hash code as
          * when the entry was added to the table.
          */
         void rekeyFront(const Key &k) {
             MOZ_ASSERT(valid());
             Data &entry = ht.data[i];
             HashNumber oldHash = prepareHash(Ops::getKey(entry.element)) >> ht.hashShift;
             HashNumber newHash = prepareHash(k) >> ht.hashShift;
             Ops::setKey(entry.element, k);
             if (newHash != oldHash) {
                 // Remove this entry from its old hash chain. (If this crashes
                 // reading nullptr, it would mean we did not find this entry on
                 // the hash chain where we expected it. That probably means the
                 // key's hash code changed since it was inserted, breaking the
                 // hash code invariant.)
                 Data **ep = &ht.hashTable[oldHash];
                 while (*ep != &entry)
                     ep = &(*ep)->chain;
                 *ep = entry.chain;
                 // Add it to the new hash chain. We could just insert it at the
                 // beginning of the chain. Instead, we do a bit of work to
                 // preserve the invariant that hash chains always go in reverse
                 // insertion order (descending memory order). No code currently
                 // depends on this invariant, so it's fine to kill it if
                 // needed.
                 ep = &ht.hashTable[newHash];
                 while (*ep && *ep > &entry)
                     ep = &(*ep)->chain;
                 entry.chain = *ep;
                 *ep = &entry;
             }
         }
     };
     Range all() { return Range(*this); }
     /*
      * Change the value of the given key.
      *
      * This calls Ops::hash on both the current key and the new key.
      * Ops::hash on the current key must return the same hash code as
      * when the entry was added to the table.
      */
     void rekeyOneEntry(const Key &current, const Key &newKey, const T &element) {
         if (current == newKey)
             return;
         Data *entry = lookup(current, prepareHash(current));
         if (!entry)
             return;
         HashNumber oldHash = prepareHash(current) >> hashShift;
         HashNumber newHash = prepareHash(newKey) >> hashShift;
         entry->element = element;
         // Remove this entry from its old hash chain. (If this crashes
         // reading nullptr, it would mean we did not find this entry on
         // the hash chain where we expected it. That probably means the
         // key's hash code changed since it was inserted, breaking the
         // hash code invariant.)
         Data **ep = &hashTable[oldHash];
         while (*ep != entry)
             ep = &(*ep)->chain;
         *ep = entry->chain;
         // Add it to the new hash chain. We could just insert it at the
         // beginning of the chain. Instead, we do a bit of work to
         // preserve the invariant that hash chains always go in reverse
         // insertion order (descending memory order). No code currently
         // depends on this invariant, so it's fine to kill it if
         // needed.
         ep = &hashTable[newHash];
         while (*ep && *ep > entry)
             ep = &(*ep)->chain;
         entry->chain = *ep;
         *ep = entry;
     }
   private:
     /* Logarithm base 2 of the number of buckets in the hash table initially. */
     static uint32_t initialBucketsLog2() { return 1; }
     static uint32_t initialBuckets() { return 1 << initialBucketsLog2(); }
     /*
      * The maximum load factor (mean number of entries per bucket).
      * It is an invariant that
      *     dataCapacity == floor(hashBuckets() * fillFactor()).
      *
      * The fill factor should be between 2 and 4, and it should be chosen so that
      * the fill factor times sizeof(Data) is close to but <= a power of 2.
      * This fixed fill factor was chosen to make the size of the data
      * array, in bytes, close to a power of two when sizeof(T) is 16.
      */
     static double fillFactor() { return 8.0 / 3.0; }
     /*
      * The minimum permitted value of (liveCount / dataLength).
      * If that ratio drops below this value, we shrink the table.
      */
     static double minDataFill() { return 0.25; }
     static HashNumber prepareHash(const Lookup &l) {
         return ScrambleHashCode(Ops::hash(l));
     }
     /* The size of hashTable, in elements. Always a power of two. */
     uint32_t hashBuckets() const {
         return 1 << (HashNumberSizeBits - hashShift);
     }
     static void destroyData(Data *data, uint32_t length) {
         for (Data *p = data + length; p != data; )
             (--p)->~Data();
     }
     void freeData(Data *data, uint32_t length) {
         destroyData(data, length);
         alloc.free_(data);
     }
     Data *lookup(const Lookup &l, HashNumber h) {
         for (Data *e = hashTable[h >> hashShift]; e; e = e->chain) {
             if (Ops::match(Ops::getKey(e->element), l))
                 return e;
         }
         return nullptr;
     }
     const Data *lookup(const Lookup &l) const {
         return const_cast<OrderedHashTable *>(this)->lookup(l, prepareHash(l));
     }
     /* This is called after rehashing the table. */
     void compacted() {
         // If we had any empty entries, compacting may have moved live entries
         // to the left within |data|. Notify all live Ranges of the change.
         for (Range *r = ranges; r; r = r->next)
             r->onCompact();
     }
     /* Compact the entries in |data| and rehash them. */
     void rehashInPlace() {
         for (uint32_t i = 0, N = hashBuckets(); i < N; i++)
             hashTable[i] = nullptr;
         Data *wp = data, *end = data + dataLength;
         for (Data *rp = data; rp != end; rp++) {
             if (!Ops::isEmpty(Ops::getKey(rp->element))) {
                 HashNumber h = prepareHash(Ops::getKey(rp->element)) >> hashShift;
                 if (rp != wp)
                     wp->element = Move(rp->element);
                 wp->chain = hashTable[h];
                 hashTable[h] = wp;
                 wp++;
             }
         }
         MOZ_ASSERT(wp == data + liveCount);
         while (wp != end)
             (--end)->~Data();
         dataLength = liveCount;
         compacted();
     }
     /*
      * Grow, shrink, or compact both |hashTable| and |data|.
      *
      * On success, this returns true, dataLength == liveCount, and there are no
      * empty elements in data[0:dataLength]. On allocation failure, this
      * leaves everything as it was and returns false.
      */
     bool rehash(uint32_t newHashShift) {
         // If the size of the table is not changing, rehash in place to avoid
         // allocating memory.
         if (newHashShift == hashShift) {
             rehashInPlace();
             return true;
         }
         size_t newHashBuckets = 1 << (HashNumberSizeBits - newHashShift);
         Data **newHashTable = static_cast<Data **>(alloc.malloc_(newHashBuckets * sizeof(Data *)));
         if (!newHashTable)
             return false;
         for (uint32_t i = 0; i < newHashBuckets; i++)
             newHashTable[i] = nullptr;
         uint32_t newCapacity = uint32_t(newHashBuckets * fillFactor());
         Data *newData = static_cast<Data *>(alloc.malloc_(newCapacity * sizeof(Data)));
         if (!newData) {
             alloc.free_(newHashTable);
             return false;
         }
         Data *wp = newData;
         for (Data *p = data, *end = data + dataLength; p != end; p++) {
             if (!Ops::isEmpty(Ops::getKey(p->element))) {
                 HashNumber h = prepareHash(Ops::getKey(p->element)) >> newHashShift;
                 new (wp) Data(Move(p->element), newHashTable[h]);
                 newHashTable[h] = wp;
                 wp++;
             }
         }
         MOZ_ASSERT(wp == newData + liveCount);
         alloc.free_(hashTable);
         freeData(data, dataLength);
         hashTable = newHashTable;
         data = newData;
         dataLength = liveCount;
         dataCapacity = newCapacity;
         hashShift = newHashShift;
         MOZ_ASSERT(hashBuckets() == newHashBuckets);
         compacted();
         return true;
     }
     // Not copyable.
     OrderedHashTable &operator=(const OrderedHashTable &) MOZ_DELETE;
     OrderedHashTable(const OrderedHashTable &) MOZ_DELETE;
 };
 }  // namespace detail
 template <class Key, class Value, class OrderedHashPolicy, class AllocPolicy>
 class OrderedHashMap
 {
   public:
     class Entry
     {
         template <class, class, class> friend class detail::OrderedHashTable;
         void operator=(const Entry &rhs) {
             const_cast<Key &>(key) = rhs.key;
             value = rhs.value;
         }
         void operator=(Entry &&rhs) {
             MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
             const_cast<Key &>(key) = Move(rhs.key);
             value = Move(rhs.value);
         }
       public:
         Entry() : key(), value() {}
         Entry(const Key &k, const Value &v) : key(k), value(v) {}
         Entry(Entry &&rhs) : key(Move(rhs.key)), value(Move(rhs.value)) {}
         const Key key;
         Value value;
     };
   private:
     struct MapOps : OrderedHashPolicy
     {
         typedef Key KeyType;
         static void makeEmpty(Entry *e) {
             OrderedHashPolicy::makeEmpty(const_cast<Key *>(&e->key));
             // Clear the value. Destroying it is another possibility, but that
             // would complicate class Entry considerably.
             e->value = Value();
         }
         static const Key &getKey(const Entry &e) { return e.key; }
         static void setKey(Entry &e, const Key &k) { const_cast<Key &>(e.key) = k; }
     };
     typedef detail::OrderedHashTable<Entry, MapOps, AllocPolicy> Impl;
     Impl impl;
   public:
     typedef typename Impl::Range Range;
     OrderedHashMap(AllocPolicy ap = AllocPolicy()) : impl(ap) {}
     bool init()                                     { return impl.init(); }
     uint32_t count() const                          { return impl.count(); }
     bool has(const Key &key) const                  { return impl.has(key); }
     Range all()                                     { return impl.all(); }
     const Entry *get(const Key &key) const          { return impl.get(key); }
     Entry *get(const Key &key)                      { return impl.get(key); }
     bool put(const Key &key, const Value &value)    { return impl.put(Entry(key, value)); }
     bool remove(const Key &key, bool *foundp)       { return impl.remove(key, foundp); }
     bool clear()                                    { return impl.clear(); }
     void rekeyOneEntry(const Key &current, const Key &newKey) {
         const Entry *e = get(current);
         if (!e)
             return;
         return impl.rekeyOneEntry(current, newKey, Entry(newKey, e->value));
     }
 };
 template <class T, class OrderedHashPolicy, class AllocPolicy>
 class OrderedHashSet
 {
   private:
     struct SetOps : OrderedHashPolicy
     {
         typedef const T KeyType;
         static const T &getKey(const T &v) { return v; }
         static void setKey(const T &e, const T &v) { const_cast<T &>(e) = v; }
     };
     typedef detail::OrderedHashTable<T, SetOps, AllocPolicy> Impl;
     Impl impl;
   public:
     typedef typename Impl::Range Range;
     OrderedHashSet(AllocPolicy ap = AllocPolicy()) : impl(ap) {}
     bool init()                                     { return impl.init(); }
     uint32_t count() const                          { return impl.count(); }
     bool has(const T &value) const                  { return impl.has(value); }
     Range all()                                     { return impl.all(); }
     bool put(const T &value)                        { return impl.put(value); }
     bool remove(const T &value, bool *foundp)       { return impl.remove(value, foundp); }
     bool clear()                                    { return impl.clear(); }
     void rekeyOneEntry(const T &current, const T &newKey) {
         return impl.rekeyOneEntry(current, newKey, newKey);
     }
 };
 }  // namespace js
 /*** HashableValue *******************************************************************************/
 bool
 HashableValue::setValue(JSContext *cx, HandleValue v)
 {
     if (v.isString()) {
         // Atomize so that hash() and operator==() are fast and infallible.
         JSString *str = AtomizeString(cx, v.toString(), DoNotInternAtom);
         if (!str)
             return false;
         value = StringValue(str);
     } else if (v.isDouble()) {
         double d = v.toDouble();
         int32_t i;
         if (NumberEqualsInt32(d, &i)) {
             // Normalize int32_t-valued doubles to int32_t for faster hashing and testing.
             value = Int32Value(i);
         } else if (IsNaN(d)) {
             // NaNs with different bits must hash and test identically.
             value = DoubleNaNValue();
         } else {
             value = v;
         }
     } else {
         value = v;
     }
     JS_ASSERT(value.isUndefined() || value.isNull() || value.isBoolean() ||
               value.isNumber() || value.isString() || value.isObject());
     return true;
 }
 HashNumber
 HashableValue::hash() const
 {
     // HashableValue::setValue normalizes values so that the SameValue relation
     // on HashableValues is the same as the == relationship on
     // value.data.asBits.
     return value.asRawBits();
 }
 bool
 HashableValue::operator==(const HashableValue &other) const
 {
     // Two HashableValues are equal if they have equal bits.
     bool b = (value.asRawBits() == other.value.asRawBits());
 #ifdef DEBUG
     bool same;
     JS_ASSERT(SameValue(nullptr, value, other.value, &same));
     JS_ASSERT(same == b);
 #endif
     return b;
 }
 HashableValue
 HashableValue::mark(JSTracer *trc) const
 {
     HashableValue hv(*this);
     trc->setTracingLocation((void *)this);
     gc::MarkValue(trc, &hv.value, "key");
     return hv;
 }
 /*** MapIterator *********************************************************************************/
 namespace {
 class MapIteratorObject : public JSObject
 {
   public:
     static const Class class_;
     enum { TargetSlot, KindSlot, RangeSlot, SlotCount };
     static const JSFunctionSpec methods[];
     static MapIteratorObject *create(JSContext *cx, HandleObject mapobj, ValueMap *data,
                                      MapObject::IteratorKind kind);
     static void finalize(FreeOp *fop, JSObject *obj);
   private:
     static inline bool is(HandleValue v);
     inline ValueMap::Range *range();
     inline MapObject::IteratorKind kind() const;
     static bool next_impl(JSContext *cx, CallArgs args);
     static bool next(JSContext *cx, unsigned argc, Value *vp);
 };
 } /* anonymous namespace */
 const Class MapIteratorObject::class_ = {
     "Map Iterator",
     JSCLASS_IMPLEMENTS_BARRIERS |
     JSCLASS_HAS_RESERVED_SLOTS(MapIteratorObject::SlotCount),
     JS_PropertyStub,         /* addProperty */
     JS_DeletePropertyStub,   /* delProperty */
     JS_PropertyStub,         /* getProperty */
     JS_StrictPropertyStub,   /* setProperty */
     JS_EnumerateStub,
     JS_ResolveStub,
     JS_ConvertStub,
     MapIteratorObject::finalize
 };
 const JSFunctionSpec MapIteratorObject::methods[] = {
     JS_SELF_HOSTED_FN("@@iterator", "IteratorIdentity", 0, 0),
     JS_FN("next", next, 0, 0),
     JS_FS_END
 };
 inline ValueMap::Range *
 MapIteratorObject::range()
 {
     return static_cast<ValueMap::Range *>(getSlot(RangeSlot).toPrivate());
 }
 inline MapObject::IteratorKind
 MapIteratorObject::kind() const
 {
     int32_t i = getSlot(KindSlot).toInt32();
     JS_ASSERT(i == MapObject::Keys || i == MapObject::Values || i == MapObject::Entries);
     return MapObject::IteratorKind(i);
 }
 bool
 GlobalObject::initMapIteratorProto(JSContext *cx, Handle<GlobalObject *> global)
 {
     JSObject *base = GlobalObject::getOrCreateIteratorPrototype(cx, global);
     if (!base)
         return false;
     Rooted<JSObject*> proto(cx,
         NewObjectWithGivenProto(cx, &MapIteratorObject::class_, base, global));
     if (!proto)
         return false;
     proto->setSlot(MapIteratorObject::RangeSlot, PrivateValue(nullptr));
     if (!JS_DefineFunctions(cx, proto, MapIteratorObject::methods))
         return false;
     global->setReservedSlot(MAP_ITERATOR_PROTO, ObjectValue(*proto));
     return true;
 }
 MapIteratorObject *
 MapIteratorObject::create(JSContext *cx, HandleObject mapobj, ValueMap *data,
                           MapObject::IteratorKind kind)
 {
     Rooted<GlobalObject *> global(cx, &mapobj->global());
     Rooted<JSObject*> proto(cx, GlobalObject::getOrCreateMapIteratorPrototype(cx, global));
     if (!proto)
         return nullptr;
     ValueMap::Range *range = cx->new_<ValueMap::Range>(data->all());
     if (!range)
         return nullptr;
     JSObject *iterobj = NewObjectWithGivenProto(cx, &class_, proto, global);
     if (!iterobj) {
         js_delete(range);
         return nullptr;
     }
     iterobj->setSlot(TargetSlot, ObjectValue(*mapobj));
     iterobj->setSlot(KindSlot, Int32Value(int32_t(kind)));
     iterobj->setSlot(RangeSlot, PrivateValue(range));
     return static_cast<MapIteratorObject *>(iterobj);
 }
 void
 MapIteratorObject::finalize(FreeOp *fop, JSObject *obj)
 {
     fop->delete_(obj->as<MapIteratorObject>().range());
 }
 bool
 MapIteratorObject::is(HandleValue v)
 {
     return v.isObject() && v.toObject().hasClass(&class_);
 }
 bool
 MapIteratorObject::next_impl(JSContext *cx, CallArgs args)
 {
     MapIteratorObject &thisobj = args.thisv().toObject().as<MapIteratorObject>();
     ValueMap::Range *range = thisobj.range();
     RootedValue value(cx);
     bool done;
     if (!range || range->empty()) {
         js_delete(range);
         thisobj.setReservedSlot(RangeSlot, PrivateValue(nullptr));
         value.setUndefined();
         done = true;
     } else {
         switch (thisobj.kind()) {
           case MapObject::Keys:
             value = range->front().key.get();
             break;
           case MapObject::Values:
             value = range->front().value;
             break;
           case MapObject::Entries: {
             JS::AutoValueArray<2> pair(cx);
             pair[0].set(range->front().key.get());
             pair[1].set(range->front().value);
             JSObject *pairobj = NewDenseCopiedArray(cx, pair.length(), pair.begin());
             if (!pairobj)
                 return false;
             value.setObject(*pairobj);
             break;
           }
         }
         range->popFront();
         done = false;
     }
     RootedObject result(cx, CreateItrResultObject(cx, value, done));
     if (!result)
         return false;
     args.rval().setObject(*result);
     return true;
 }
 bool
 MapIteratorObject::next(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     return CallNonGenericMethod(cx, is, next_impl, args);
 }
 /*** Map *****************************************************************************************/
 const Class MapObject::class_ = {
     "Map",
     JSCLASS_HAS_PRIVATE | JSCLASS_IMPLEMENTS_BARRIERS |
     JSCLASS_HAS_CACHED_PROTO(JSProto_Map),
     JS_PropertyStub,         // addProperty
     JS_DeletePropertyStub,   // delProperty
     JS_PropertyStub,         // getProperty
     JS_StrictPropertyStub,   // setProperty
     JS_EnumerateStub,
     JS_ResolveStub,
     JS_ConvertStub,
     finalize,
     nullptr,                 // call
     nullptr,                 // hasInstance
     nullptr,                 // construct
     mark
 };
 const JSPropertySpec MapObject::properties[] = {
     JS_PSG("size", size, 0),
     JS_PS_END
 };
 const JSFunctionSpec MapObject::methods[] = {
     JS_FN("get", get, 1, 0),
     JS_FN("has", has, 1, 0),
     JS_FN("set", set, 2, 0),
     JS_FN("delete", delete_, 1, 0),
     JS_FN("keys", keys, 0, 0),
     JS_FN("values", values, 0, 0),
     JS_FN("clear", clear, 0, 0),
     JS_SELF_HOSTED_FN("forEach", "MapForEach", 2, 0),
     JS_FS_END
 };
 static JSObject *
 InitClass(JSContext *cx, Handle<GlobalObject*> global, const Class *clasp, JSProtoKey key, Native construct,
           const JSPropertySpec *properties, const JSFunctionSpec *methods)
 {
     Rooted<JSObject*> proto(cx, global->createBlankPrototype(cx, clasp));
     if (!proto)
         return nullptr;
     proto->setPrivate(nullptr);
     Rooted<JSFunction*> ctor(cx, global->createConstructor(cx, construct, ClassName(key, cx), 0));
     if (!ctor ||
         !LinkConstructorAndPrototype(cx, ctor, proto) ||
         !DefinePropertiesAndBrand(cx, proto, properties, methods) ||
         !GlobalObject::initBuiltinConstructor(cx, global, key, ctor, proto))
     {
         return nullptr;
     }
     return proto;
 }
 JSObject *
 MapObject::initClass(JSContext *cx, JSObject *obj)
 {
     Rooted<GlobalObject*> global(cx, &obj->as<GlobalObject>());
     RootedObject proto(cx,
         InitClass(cx, global, &class_, JSProto_Map, construct, properties, methods));
     if (proto) {
         // Define the "entries" method.
         JSFunction *fun = JS_DefineFunction(cx, proto, "entries", entries, 0, 0);
         if (!fun)
             return nullptr;
         // Define its alias.
         RootedValue funval(cx, ObjectValue(*fun));
         if (!JS_DefineProperty(cx, proto, js_std_iterator_str, funval, 0))
             return nullptr;
     }
     return proto;
 }
 template <class Range>
 static void
 MarkKey(Range &r, const HashableValue &key, JSTracer *trc)
 {
     HashableValue newKey = key.mark(trc);
     if (newKey.get() != key.get()) {
         // The hash function only uses the bits of the Value, so it is safe to
         // rekey even when the object or string has been modified by the GC.
         r.rekeyFront(newKey);
     }
 }
 void
 MapObject::mark(JSTracer *trc, JSObject *obj)
 {
     if (ValueMap *map = obj->as<MapObject>().getData()) {
         for (ValueMap::Range r = map->all(); !r.empty(); r.popFront()) {
             MarkKey(r, r.front().key, trc);
             gc::MarkValue(trc, &r.front().value, "value");
         }
     }
 }
 #ifdef JSGC_GENERATIONAL
 struct UnbarrieredHashPolicy {
     typedef Value Lookup;
     static HashNumber hash(const Lookup &v) { return v.asRawBits(); }
     static bool match(const Value &k, const Lookup &l) { return k == l; }
     static bool isEmpty(const Value &v) { return v.isMagic(JS_HASH_KEY_EMPTY); }
     static void makeEmpty(Value *vp) { vp->setMagic(JS_HASH_KEY_EMPTY); }
 };
 template <typename TableType>
 class OrderedHashTableRef : public gc::BufferableRef
 {
     TableType *table;
     Value key;
   public:
     explicit OrderedHashTableRef(TableType *t, const Value &k) : table(t), key(k) {}
     void mark(JSTracer *trc) {
         JS_ASSERT(UnbarrieredHashPolicy::hash(key) ==
                   HashableValue::Hasher::hash(*reinterpret_cast<HashableValue*>(&key)));
         Value prior = key;
         gc::MarkValueUnbarriered(trc, &key, "ordered hash table key");
         table->rekeyOneEntry(prior, key);
     }
 };
 #endif
 static void
 WriteBarrierPost(JSRuntime *rt, ValueMap *map, const HashableValue &key)
 {
 #ifdef JSGC_GENERATIONAL
     typedef OrderedHashMap<Value, Value, UnbarrieredHashPolicy, RuntimeAllocPolicy> UnbarrieredMap;
     rt->gcStoreBuffer.putGeneric(OrderedHashTableRef<UnbarrieredMap>(
                 reinterpret_cast<UnbarrieredMap *>(map), key.get()));
 #endif
 }
 static void
 WriteBarrierPost(JSRuntime *rt, ValueSet *set, const HashableValue &key)
 {
 #ifdef JSGC_GENERATIONAL
     typedef OrderedHashSet<Value, UnbarrieredHashPolicy, RuntimeAllocPolicy> UnbarrieredSet;
     rt->gcStoreBuffer.putGeneric(OrderedHashTableRef<UnbarrieredSet>(
                 reinterpret_cast<UnbarrieredSet *>(set), key.get()));
 #endif
 }
 void
 MapObject::finalize(FreeOp *fop, JSObject *obj)
 {
     if (ValueMap *map = obj->as<MapObject>().getData())
         fop->delete_(map);
 }
 bool
 MapObject::construct(JSContext *cx, unsigned argc, Value *vp)
 {
     Rooted<JSObject*> obj(cx, NewBuiltinClassInstance(cx, &class_));
     if (!obj)
         return false;
     ValueMap *map = cx->new_<ValueMap>(cx->runtime());
     if (!map)
         return false;
     if (!map->init()) {
         js_ReportOutOfMemory(cx);
         return false;
     }
     obj->setPrivate(map);
     CallArgs args = CallArgsFromVp(argc, vp);
     if (args.hasDefined(0)) {
         ForOfIterator iter(cx);
         if (!iter.init(args[0]))
             return false;
         RootedValue pairVal(cx);
         RootedObject pairObj(cx);
         while (true) {
             bool done;
             if (!iter.next(&pairVal, &done))
                 return false;
             if (done)
                 break;
             if (!pairVal.isObject()) {
                 JS_ReportErrorNumber(cx, js_GetErrorMessage, nullptr, JSMSG_INVALID_MAP_ITERABLE);
                 return false;
             }
             pairObj = &pairVal.toObject();
             if (!pairObj)
                 return false;
             RootedValue key(cx);
             if (!JSObject::getElement(cx, pairObj, pairObj, 0, &key))
                 return false;
             AutoHashableValueRooter hkey(cx);
             if (!hkey.setValue(cx, key))
                 return false;
             RootedValue val(cx);
             if (!JSObject::getElement(cx, pairObj, pairObj, 1, &val))
                 return false;
             RelocatableValue rval(val);
             if (!map->put(hkey, rval)) {
                 js_ReportOutOfMemory(cx);
                 return false;
             }
             WriteBarrierPost(cx->runtime(), map, hkey);
         }
     }
     args.rval().setObject(*obj);
     return true;
 }
 bool
 MapObject::is(HandleValue v)
 {
     return v.isObject() && v.toObject().hasClass(&class_) && v.toObject().getPrivate();
 }
 #define ARG0_KEY(cx, args, key)                                               \
     AutoHashableValueRooter key(cx);                                          \
     if (args.length() > 0 && !key.setValue(cx, args[0]))                      \
         return false
 ValueMap &
 MapObject::extract(CallReceiver call)
 {
     JS_ASSERT(call.thisv().isObject());
     JS_ASSERT(call.thisv().toObject().hasClass(&MapObject::class_));
     return *call.thisv().toObject().as<MapObject>().getData();
 }
 bool
 MapObject::size_impl(JSContext *cx, CallArgs args)
 {
     JS_ASSERT(MapObject::is(args.thisv()));
     ValueMap &map = extract(args);
     JS_STATIC_ASSERT(sizeof map.count() <= sizeof(uint32_t));
     args.rval().setNumber(map.count());
     return true;
 }
 bool
 MapObject::size(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     return CallNonGenericMethod<MapObject::is, MapObject::size_impl>(cx, args);
 }
 bool
 MapObject::get_impl(JSContext *cx, CallArgs args)
 {
     JS_ASSERT(MapObject::is(args.thisv()));
     ValueMap &map = extract(args);
     ARG0_KEY(cx, args, key);
     if (ValueMap::Entry *p = map.get(key))
         args.rval().set(p->value);
     else
         args.rval().setUndefined();
     return true;
 }
 bool
 MapObject::get(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     return CallNonGenericMethod<MapObject::is, MapObject::get_impl>(cx, args);
 }
 bool
 MapObject::has_impl(JSContext *cx, CallArgs args)
 {
     JS_ASSERT(MapObject::is(args.thisv()));
     ValueMap &map = extract(args);
     ARG0_KEY(cx, args, key);
     args.rval().setBoolean(map.has(key));
     return true;
 }
 bool
 MapObject::has(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     return CallNonGenericMethod<MapObject::is, MapObject::has_impl>(cx, args);
 }
 bool
 MapObject::set_impl(JSContext *cx, CallArgs args)
 {
     JS_ASSERT(MapObject::is(args.thisv()));
     ValueMap &map = extract(args);
     ARG0_KEY(cx, args, key);
     RelocatableValue rval(args.get(1));
     if (!map.put(key, rval)) {
         js_ReportOutOfMemory(cx);
         return false;
     }
     WriteBarrierPost(cx->runtime(), &map, key);
     args.rval().setUndefined();
     return true;
 }
 bool
 MapObject::set(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     return CallNonGenericMethod<MapObject::is, MapObject::set_impl>(cx, args);
 }
 bool
 MapObject::delete_impl(JSContext *cx, CallArgs args)
 {
     // MapObject::mark does not mark deleted entries. Incremental GC therefore
     // requires that no RelocatableValue objects pointing to heap values be
     // left alive in the ValueMap.
     //
     // OrderedHashMap::remove() doesn't destroy the removed entry. It merely
     // calls OrderedHashMap::MapOps::makeEmpty. But that is sufficient, because
     // makeEmpty clears the value by doing e->value = Value(), and in the case
     // of a ValueMap, Value() means RelocatableValue(), which is the same as
     // RelocatableValue(UndefinedValue()).
     JS_ASSERT(MapObject::is(args.thisv()));
     ValueMap &map = extract(args);
     ARG0_KEY(cx, args, key);
     bool found;
     if (!map.remove(key, &found)) {
         js_ReportOutOfMemory(cx);
         return false;
     }
     args.rval().setBoolean(found);
     return true;
 }
 bool
 MapObject::delete_(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     return CallNonGenericMethod<MapObject::is, MapObject::delete_impl>(cx, args);
 }
 bool
 MapObject::iterator_impl(JSContext *cx, CallArgs args, IteratorKind kind)
 {
     Rooted<MapObject*> mapobj(cx, &args.thisv().toObject().as<MapObject>());
     ValueMap &map = *mapobj->getData();
     Rooted<JSObject*> iterobj(cx, MapIteratorObject::create(cx, mapobj, &map, kind));
     if (!iterobj)
         return false;
     args.rval().setObject(*iterobj);
     return true;
 }
 bool
 MapObject::keys_impl(JSContext *cx, CallArgs args)
 {
     return iterator_impl(cx, args, Keys);
 }
 bool
 MapObject::keys(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     return CallNonGenericMethod(cx, is, keys_impl, args);
 }
 bool
 MapObject::values_impl(JSContext *cx, CallArgs args)
 {
     return iterator_impl(cx, args, Values);
 }
 bool
 MapObject::values(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     return CallNonGenericMethod(cx, is, values_impl, args);
 }
 bool
 MapObject::entries_impl(JSContext *cx, CallArgs args)
 {
     return iterator_impl(cx, args, Entries);
 }
 bool
 MapObject::entries(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     return CallNonGenericMethod(cx, is, entries_impl, args);
 }
 bool
 MapObject::clear_impl(JSContext *cx, CallArgs args)
 {
     Rooted<MapObject*> mapobj(cx, &args.thisv().toObject().as<MapObject>());
     if (!mapobj->getData()->clear()) {
         js_ReportOutOfMemory(cx);
         return false;
     }
     args.rval().setUndefined();
     return true;
 }
 bool
 MapObject::clear(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     return CallNonGenericMethod(cx, is, clear_impl, args);
 }
 JSObject *
 js_InitMapClass(JSContext *cx, HandleObject obj)
 {
     return MapObject::initClass(cx, obj);
 }
 /*** SetIterator *********************************************************************************/
 namespace {
 class SetIteratorObject : public JSObject
 {
   public:
     static const Class class_;
     enum { TargetSlot, KindSlot, RangeSlot, SlotCount };
     static const JSFunctionSpec methods[];
     static SetIteratorObject *create(JSContext *cx, HandleObject setobj, ValueSet *data,
                                      SetObject::IteratorKind kind);
     static void finalize(FreeOp *fop, JSObject *obj);
   private:
     static inline bool is(HandleValue v);
     inline ValueSet::Range *range();
     inline SetObject::IteratorKind kind() const;
     static bool next_impl(JSContext *cx, CallArgs args);
     static bool next(JSContext *cx, unsigned argc, Value *vp);
 };
 } /* anonymous namespace */
 const Class SetIteratorObject::class_ = {
     "Set Iterator",
     JSCLASS_IMPLEMENTS_BARRIERS |
     JSCLASS_HAS_RESERVED_SLOTS(SetIteratorObject::SlotCount),
     JS_PropertyStub,         /* addProperty */
     JS_DeletePropertyStub,   /* delProperty */
     JS_PropertyStub,         /* getProperty */
     JS_StrictPropertyStub,   /* setProperty */
     JS_EnumerateStub,
     JS_ResolveStub,
     JS_ConvertStub,
     SetIteratorObject::finalize
 };
 const JSFunctionSpec SetIteratorObject::methods[] = {
     JS_SELF_HOSTED_FN("@@iterator", "IteratorIdentity", 0, 0),
     JS_FN("next", next, 0, 0),
     JS_FS_END
 };
 inline ValueSet::Range *
 SetIteratorObject::range()
 {
     return static_cast<ValueSet::Range *>(getSlot(RangeSlot).toPrivate());
 }
 inline SetObject::IteratorKind
 SetIteratorObject::kind() const
 {
     int32_t i = getSlot(KindSlot).toInt32();
     JS_ASSERT(i == SetObject::Values || i == SetObject::Entries);
     return SetObject::IteratorKind(i);
 }
 bool
 GlobalObject::initSetIteratorProto(JSContext *cx, Handle<GlobalObject*> global)
 {
     JSObject *base = GlobalObject::getOrCreateIteratorPrototype(cx, global);
     if (!base)
         return false;
     RootedObject proto(cx, NewObjectWithGivenProto(cx, &SetIteratorObject::class_, base, global));
     if (!proto)
         return false;
     proto->setSlot(SetIteratorObject::RangeSlot, PrivateValue(nullptr));
     if (!JS_DefineFunctions(cx, proto, SetIteratorObject::methods))
         return false;
     global->setReservedSlot(SET_ITERATOR_PROTO, ObjectValue(*proto));
     return true;
 }
 SetIteratorObject *
 SetIteratorObject::create(JSContext *cx, HandleObject setobj, ValueSet *data,
                           SetObject::IteratorKind kind)
 {
     Rooted<GlobalObject *> global(cx, &setobj->global());
     Rooted<JSObject*> proto(cx, GlobalObject::getOrCreateSetIteratorPrototype(cx, global));
     if (!proto)
         return nullptr;
     ValueSet::Range *range = cx->new_<ValueSet::Range>(data->all());
     if (!range)
         return nullptr;
     JSObject *iterobj = NewObjectWithGivenProto(cx, &class_, proto, global);
     if (!iterobj) {
         js_delete(range);
         return nullptr;
     }
     iterobj->setSlot(TargetSlot, ObjectValue(*setobj));
     iterobj->setSlot(KindSlot, Int32Value(int32_t(kind)));
     iterobj->setSlot(RangeSlot, PrivateValue(range));
     return static_cast<SetIteratorObject *>(iterobj);
 }
 void
 SetIteratorObject::finalize(FreeOp *fop, JSObject *obj)
 {
     fop->delete_(obj->as<SetIteratorObject>().range());
 }
 bool
 SetIteratorObject::is(HandleValue v)
 {
     return v.isObject() && v.toObject().is<SetIteratorObject>();
 }
 bool
 SetIteratorObject::next_impl(JSContext *cx, CallArgs args)
 {
     SetIteratorObject &thisobj = args.thisv().toObject().as<SetIteratorObject>();
     ValueSet::Range *range = thisobj.range();
     RootedValue value(cx);
     bool done;
     if (!range || range->empty()) {
         js_delete(range);
         thisobj.setReservedSlot(RangeSlot, PrivateValue(nullptr));
         value.setUndefined();
         done = true;
     } else {
         switch (thisobj.kind()) {
           case SetObject::Values:
             value = range->front().get();
             break;
           case SetObject::Entries: {
             JS::AutoValueArray<2> pair(cx);
             pair[0].set(range->front().get());
             pair[1].set(range->front().get());
             JSObject *pairObj = NewDenseCopiedArray(cx, 2, pair.begin());
             if (!pairObj)
               return false;
             value.setObject(*pairObj);
             break;
           }
         }
         range->popFront();
         done = false;
     }
     RootedObject result(cx, CreateItrResultObject(cx, value, done));
     if (!result)
         return false;
     args.rval().setObject(*result);
     return true;
 }
 bool
 SetIteratorObject::next(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     return CallNonGenericMethod(cx, is, next_impl, args);
 }
 /*** Set *****************************************************************************************/
 const Class SetObject::class_ = {
     "Set",
     JSCLASS_HAS_PRIVATE | JSCLASS_IMPLEMENTS_BARRIERS |
     JSCLASS_HAS_CACHED_PROTO(JSProto_Set),
     JS_PropertyStub,         // addProperty
     JS_DeletePropertyStub,   // delProperty
     JS_PropertyStub,         // getProperty
     JS_StrictPropertyStub,   // setProperty
     JS_EnumerateStub,
     JS_ResolveStub,
     JS_ConvertStub,
     finalize,
     nullptr,                 // call
     nullptr,                 // hasInstance
     nullptr,                 // construct
     mark
 };
 const JSPropertySpec SetObject::properties[] = {
     JS_PSG("size", size, 0),
     JS_PS_END
 };
 const JSFunctionSpec SetObject::methods[] = {
     JS_FN("has", has, 1, 0),
     JS_FN("add", add, 1, 0),
     JS_FN("delete", delete_, 1, 0),
     JS_FN("entries", entries, 0, 0),
     JS_FN("clear", clear, 0, 0),
     JS_SELF_HOSTED_FN("forEach", "SetForEach", 2, 0),
     JS_FS_END
 };
 JSObject *
 SetObject::initClass(JSContext *cx, JSObject *obj)
 {
     Rooted<GlobalObject*> global(cx, &obj->as<GlobalObject>());
     RootedObject proto(cx,
         InitClass(cx, global, &class_, JSProto_Set, construct, properties, methods));
     if (proto) {
         // Define the "values" method.
         JSFunction *fun = JS_DefineFunction(cx, proto, "values", values, 0, 0);
         if (!fun)
             return nullptr;
         // Define its aliases.
         RootedValue funval(cx, ObjectValue(*fun));
         if (!JS_DefineProperty(cx, proto, "keys", funval, 0))
             return nullptr;
         if (!JS_DefineProperty(cx, proto, js_std_iterator_str, funval, 0))
             return nullptr;
     }
     return proto;
 }
 void
 SetObject::mark(JSTracer *trc, JSObject *obj)
 {
     SetObject *setobj = static_cast<SetObject *>(obj);
     if (ValueSet *set = setobj->getData()) {
         for (ValueSet::Range r = set->all(); !r.empty(); r.popFront())
             MarkKey(r, r.front(), trc);
     }
 }
 void
 SetObject::finalize(FreeOp *fop, JSObject *obj)
 {
     SetObject *setobj = static_cast<SetObject *>(obj);
     if (ValueSet *set = setobj->getData())
         fop->delete_(set);
 }
 bool
 SetObject::construct(JSContext *cx, unsigned argc, Value *vp)
 {
     Rooted<JSObject*> obj(cx, NewBuiltinClassInstance(cx, &class_));
     if (!obj)
         return false;
     ValueSet *set = cx->new_<ValueSet>(cx->runtime());
     if (!set)
         return false;
     if (!set->init()) {
         js_ReportOutOfMemory(cx);
         return false;
     }
     obj->setPrivate(set);
     CallArgs args = CallArgsFromVp(argc, vp);
     if (args.hasDefined(0)) {
         RootedValue keyVal(cx);
         ForOfIterator iter(cx);
         if (!iter.init(args[0]))
             return false;
         AutoHashableValueRooter key(cx);
         while (true) {
             bool done;
             if (!iter.next(&keyVal, &done))
                 return false;
             if (done)
                 break;
             if (!key.setValue(cx, keyVal))
                 return false;
             if (!set->put(key)) {
                 js_ReportOutOfMemory(cx);
                 return false;
             }
             WriteBarrierPost(cx->runtime(), set, key);
         }
     }
     args.rval().setObject(*obj);
     return true;
 }
 bool
 SetObject::is(HandleValue v)
 {
     return v.isObject() && v.toObject().hasClass(&class_) && v.toObject().getPrivate();
 }
 ValueSet &
 SetObject::extract(CallReceiver call)
 {
     JS_ASSERT(call.thisv().isObject());
     JS_ASSERT(call.thisv().toObject().hasClass(&SetObject::class_));
     return *static_cast<SetObject&>(call.thisv().toObject()).getData();
 }
 bool
 SetObject::size_impl(JSContext *cx, CallArgs args)
 {
     JS_ASSERT(is(args.thisv()));
     ValueSet &set = extract(args);
     JS_STATIC_ASSERT(sizeof set.count() <= sizeof(uint32_t));
     args.rval().setNumber(set.count());
     return true;
 }
 bool
 SetObject::size(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     return CallNonGenericMethod<SetObject::is, SetObject::size_impl>(cx, args);
 }
 bool
 SetObject::has_impl(JSContext *cx, CallArgs args)
 {
     JS_ASSERT(is(args.thisv()));
     ValueSet &set = extract(args);
     ARG0_KEY(cx, args, key);
     args.rval().setBoolean(set.has(key));
     return true;
 }
 bool
 SetObject::has(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     return CallNonGenericMethod<SetObject::is, SetObject::has_impl>(cx, args);
 }
 bool
 SetObject::add_impl(JSContext *cx, CallArgs args)
 {
     JS_ASSERT(is(args.thisv()));
     ValueSet &set = extract(args);
     ARG0_KEY(cx, args, key);
     if (!set.put(key)) {
         js_ReportOutOfMemory(cx);
         return false;
     }
     WriteBarrierPost(cx->runtime(), &set, key);
     args.rval().setUndefined();
     return true;
 }
 bool
 SetObject::add(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     return CallNonGenericMethod<SetObject::is, SetObject::add_impl>(cx, args);
 }
 bool
 SetObject::delete_impl(JSContext *cx, CallArgs args)
 {
     JS_ASSERT(is(args.thisv()));
     ValueSet &set = extract(args);
     ARG0_KEY(cx, args, key);
     bool found;
     if (!set.remove(key, &found)) {
         js_ReportOutOfMemory(cx);
         return false;
     }
     args.rval().setBoolean(found);
     return true;
 }
 bool
 SetObject::delete_(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     return CallNonGenericMethod<SetObject::is, SetObject::delete_impl>(cx, args);
 }
 bool
 SetObject::iterator_impl(JSContext *cx, CallArgs args, IteratorKind kind)
 {
     Rooted<SetObject*> setobj(cx, &args.thisv().toObject().as<SetObject>());
     ValueSet &set = *setobj->getData();
     Rooted<JSObject*> iterobj(cx, SetIteratorObject::create(cx, setobj, &set, kind));
     if (!iterobj)
         return false;
     args.rval().setObject(*iterobj);
     return true;
 }
 bool
 SetObject::values_impl(JSContext *cx, CallArgs args)
 {
     return iterator_impl(cx, args, Values);
 }
 bool
 SetObject::values(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     return CallNonGenericMethod(cx, is, values_impl, args);
 }
 bool
 SetObject::entries_impl(JSContext *cx, CallArgs args)
 {
     return iterator_impl(cx, args, Entries);
 }
 bool
 SetObject::entries(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     return CallNonGenericMethod(cx, is, entries_impl, args);
 }
 bool
 SetObject::clear_impl(JSContext *cx, CallArgs args)
 {
     Rooted<SetObject*> setobj(cx, &args.thisv().toObject().as<SetObject>());
     if (!setobj->getData()->clear()) {
         js_ReportOutOfMemory(cx);
         return false;
     }
     args.rval().setUndefined();
     return true;
 }
 bool
 SetObject::clear(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     return CallNonGenericMethod(cx, is, clear_impl, args);
 }
 JSObject *
 js_InitSetClass(JSContext *cx, HandleObject obj)
 {
     return SetObject::initClass(cx, obj);
 }

The Tor Browser / annotate

js/src/builtin/MapObject.cpp@6474c204b198 (annotated)

js/src/builtin/MapObject.cpp