diff -r 000000000000 -r 6474c204b198 js/src/frontend/ParseMaps.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/js/src/frontend/ParseMaps.h	Wed Dec 31 06:09:35 2014 +0100
@@ -0,0 +1,511 @@
+/* -*- 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/. */
+
+#ifndef frontend_ParseMaps_h
+#define frontend_ParseMaps_h
+
+#include "mozilla/Attributes.h"
+#include "mozilla/TypeTraits.h"
+
+#include "ds/InlineMap.h"
+#include "gc/Barrier.h"
+#include "js/Vector.h"
+
+class JSAtom;
+
+typedef uintptr_t jsatomid;
+
+namespace js {
+
+class LifoAlloc;
+
+namespace frontend {
+
+class DefinitionSingle;
+class DefinitionList;
+
+typedef InlineMap<JSAtom *, jsatomid, 24> AtomIndexMap;
+typedef InlineMap<JSAtom *, DefinitionSingle, 24> AtomDefnMap;
+typedef InlineMap<JSAtom *, DefinitionList, 24> AtomDefnListMap;
+
+/*
+ * For all unmapped atoms recorded in al, add a mapping from the atom's index
+ * to its address. map->length must already be set to the number of atoms in
+ * the list and map->vector must point to pre-allocated memory.
+ */
+void
+InitAtomMap(AtomIndexMap *indices, HeapPtr<JSAtom> *atoms);
+
+/*
+ * A pool that permits the reuse of the backing storage for the defn, index, or
+ * defn-or-header (multi) maps.
+ *
+ * The pool owns all the maps that are given out, and is responsible for
+ * relinquishing all resources when |purgeAll| is triggered.
+ */
+class ParseMapPool
+{
+    typedef Vector<void *, 32, SystemAllocPolicy> RecyclableMaps;
+
+    RecyclableMaps      all;
+    RecyclableMaps      recyclable;
+
+    void checkInvariants();
+
+    void recycle(void *map) {
+        JS_ASSERT(map);
+#ifdef DEBUG
+        bool ok = false;
+        /* Make sure the map is in |all| but not already in |recyclable|. */
+        for (void **it = all.begin(), **end = all.end(); it != end; ++it) {
+            if (*it == map) {
+                ok = true;
+                break;
+            }
+        }
+        JS_ASSERT(ok);
+        for (void **it = recyclable.begin(), **end = recyclable.end(); it != end; ++it)
+            JS_ASSERT(*it != map);
+#endif
+        JS_ASSERT(recyclable.length() < all.length());
+        recyclable.infallibleAppend(map); /* Reserved in allocateFresh. */
+    }
+
+    void *allocateFresh();
+    void *allocate() {
+        if (recyclable.empty())
+            return allocateFresh();
+
+        void *map = recyclable.popCopy();
+        asAtomMap(map)->clear();
+        return map;
+    }
+
+    /* Arbitrary atom map type, that has keys and values of the same kind. */
+    typedef AtomIndexMap AtomMapT;
+
+    static AtomMapT *asAtomMap(void *ptr) {
+        return reinterpret_cast<AtomMapT *>(ptr);
+    }
+
+  public:
+    ~ParseMapPool() {
+        purgeAll();
+    }
+
+    void purgeAll();
+
+    bool empty() const {
+        return all.empty();
+    }
+
+    /* Fallibly aquire one of the supported map types from the pool. */
+    template <typename T>
+    T *acquire() {
+        return reinterpret_cast<T *>(allocate());
+    }
+
+    /* Release one of the supported map types back to the pool. */
+
+    void release(AtomIndexMap *map) {
+        recycle((void *) map);
+    }
+
+    void release(AtomDefnMap *map) {
+        recycle((void *) map);
+    }
+
+    void release(AtomDefnListMap *map) {
+        recycle((void *) map);
+    }
+}; /* ParseMapPool */
+
+/*
+ * N.B. This is a POD-type so that it can be included in the ParseNode union.
+ * If possible, use the corresponding |OwnedAtomThingMapPtr| variant.
+ */
+template <class Map>
+struct AtomThingMapPtr
+{
+    Map *map_;
+
+    void init() { clearMap(); }
+
+    bool ensureMap(ExclusiveContext *cx);
+    void releaseMap(ExclusiveContext *cx);
+
+    bool hasMap() const { return map_; }
+    Map *getMap() { return map_; }
+    void setMap(Map *newMap) { JS_ASSERT(!map_); map_ = newMap; }
+    void clearMap() { map_ = nullptr; }
+
+    Map *operator->() { return map_; }
+    const Map *operator->() const { return map_; }
+    Map &operator*() const { return *map_; }
+};
+
+typedef AtomThingMapPtr<AtomIndexMap> AtomIndexMapPtr;
+
+/*
+ * Wrapper around an AtomThingMapPtr (or its derivatives) that automatically
+ * releases a map on destruction, if one has been acquired.
+ */
+template <typename AtomThingMapPtrT>
+class OwnedAtomThingMapPtr : public AtomThingMapPtrT
+{
+    ExclusiveContext *cx;
+
+  public:
+    explicit OwnedAtomThingMapPtr(ExclusiveContext *cx) : cx(cx) {
+        AtomThingMapPtrT::init();
+    }
+
+    ~OwnedAtomThingMapPtr() {
+        AtomThingMapPtrT::releaseMap(cx);
+    }
+};
+
+typedef OwnedAtomThingMapPtr<AtomIndexMapPtr> OwnedAtomIndexMapPtr;
+
+/*
+ * DefinitionSingle and DefinitionList represent either a single definition
+ * or a list of them. The representation of definitions varies between
+ * parse handlers, being either a Definition* (FullParseHandler) or a
+ * Definition::Kind (SyntaxParseHandler). Methods on the below classes are
+ * templated to distinguish the kind of value wrapped by the class.
+ */
+
+/* Wrapper for a single definition. */
+class DefinitionSingle
+{
+    uintptr_t bits;
+
+  public:
+
+    template <typename ParseHandler>
+    static DefinitionSingle new_(typename ParseHandler::DefinitionNode defn)
+    {
+        DefinitionSingle res;
+        res.bits = ParseHandler::definitionToBits(defn);
+        return res;
+    }
+
+    template <typename ParseHandler>
+    typename ParseHandler::DefinitionNode get() {
+        return ParseHandler::definitionFromBits(bits);
+    }
+};
+
+struct AtomDefnMapPtr : public AtomThingMapPtr<AtomDefnMap>
+{
+    template <typename ParseHandler>
+    MOZ_ALWAYS_INLINE
+    typename ParseHandler::DefinitionNode lookupDefn(JSAtom *atom) {
+        AtomDefnMap::Ptr p = map_->lookup(atom);
+        return p ? p.value().get<ParseHandler>() : ParseHandler::nullDefinition();
+    }
+};
+
+typedef OwnedAtomThingMapPtr<AtomDefnMapPtr> OwnedAtomDefnMapPtr;
+
+/*
+ * A nonempty list containing one or more pointers to Definitions.
+ *
+ * By far the most common case is that the list contains exactly one
+ * Definition, so the implementation is optimized for that case.
+ *
+ * Nodes for the linked list (if any) are allocated from the tempPool of a
+ * context the caller passes into pushFront and pushBack. This means the
+ * DefinitionList does not own the memory for the nodes: the JSContext does.
+ * As a result, DefinitionList is a POD type; it can be safely and cheaply
+ * copied.
+ */
+class DefinitionList
+{
+  public:
+    class Range;
+
+  private:
+    friend class Range;
+
+    /* A node in a linked list of Definitions. */
+    struct Node
+    {
+        uintptr_t bits;
+        Node *next;
+
+        Node(uintptr_t bits, Node *next) : bits(bits), next(next) {}
+    };
+
+    union {
+        uintptr_t bits;
+        Node *head;
+    } u;
+
+    Node *firstNode() const {
+        JS_ASSERT(isMultiple());
+        return (Node *) (u.bits & ~0x1);
+    }
+
+    static Node *
+    allocNode(ExclusiveContext *cx, LifoAlloc &alloc, uintptr_t bits, Node *tail);
+
+  public:
+    class Range
+    {
+        friend class DefinitionList;
+
+        Node *node;
+        uintptr_t bits;
+
+        explicit Range(const DefinitionList &list) {
+            if (list.isMultiple()) {
+                node = list.firstNode();
+                bits = node->bits;
+            } else {
+                node = nullptr;
+                bits = list.u.bits;
+            }
+        }
+
+      public:
+        /* An empty Range. */
+        Range() : node(nullptr), bits(0) {}
+
+        void popFront() {
+            JS_ASSERT(!empty());
+            if (!node) {
+                bits = 0;
+                return;
+            }
+            node = node->next;
+            bits = node ? node->bits : 0;
+        }
+
+        template <typename ParseHandler>
+        typename ParseHandler::DefinitionNode front() {
+            JS_ASSERT(!empty());
+            return ParseHandler::definitionFromBits(bits);
+        }
+
+        bool empty() const {
+            JS_ASSERT_IF(!bits, !node);
+            return !bits;
+        }
+    };
+
+    DefinitionList() {
+        u.bits = 0;
+    }
+
+    explicit DefinitionList(uintptr_t bits) {
+        u.bits = bits;
+        JS_ASSERT(!isMultiple());
+    }
+
+    explicit DefinitionList(Node *node) {
+        u.head = node;
+        u.bits |= 0x1;
+        JS_ASSERT(isMultiple());
+    }
+
+    bool isMultiple() const { return (u.bits & 0x1) != 0; }
+
+    template <typename ParseHandler>
+    typename ParseHandler::DefinitionNode front() {
+        return ParseHandler::definitionFromBits(isMultiple() ? firstNode()->bits : u.bits);
+    }
+
+    /*
+     * If there are multiple Definitions in this list, remove the first and
+     * return true. Otherwise there is exactly one Definition in the list; do
+     * nothing and return false.
+     */
+    bool popFront() {
+        if (!isMultiple())
+            return false;
+
+        Node *node = firstNode();
+        Node *next = node->next;
+        if (next->next)
+            *this = DefinitionList(next);
+        else
+            *this = DefinitionList(next->bits);
+        return true;
+    }
+
+    /*
+     * Add a definition to the front of this list.
+     *
+     * Return true on success. On OOM, report on cx and return false.
+     */
+    template <typename ParseHandler>
+    bool pushFront(ExclusiveContext *cx, LifoAlloc &alloc,
+                   typename ParseHandler::DefinitionNode defn) {
+        Node *tail;
+        if (isMultiple()) {
+            tail = firstNode();
+        } else {
+            tail = allocNode(cx, alloc, u.bits, nullptr);
+            if (!tail)
+                return false;
+        }
+
+        Node *node = allocNode(cx, alloc, ParseHandler::definitionToBits(defn), tail);
+        if (!node)
+            return false;
+        *this = DefinitionList(node);
+        return true;
+    }
+
+    /* Overwrite the first Definition in the list. */
+    template <typename ParseHandler>
+        void setFront(typename ParseHandler::DefinitionNode defn) {
+        if (isMultiple())
+            firstNode()->bits = ParseHandler::definitionToBits(defn);
+        else
+            *this = DefinitionList(ParseHandler::definitionToBits(defn));
+    }
+
+    Range all() const { return Range(*this); }
+
+#ifdef DEBUG
+    void dump();
+#endif
+};
+
+typedef AtomDefnMap::Range      AtomDefnRange;
+typedef AtomDefnMap::AddPtr     AtomDefnAddPtr;
+typedef AtomDefnMap::Ptr        AtomDefnPtr;
+typedef AtomIndexMap::AddPtr    AtomIndexAddPtr;
+typedef AtomIndexMap::Ptr       AtomIndexPtr;
+typedef AtomDefnListMap::Ptr    AtomDefnListPtr;
+typedef AtomDefnListMap::AddPtr AtomDefnListAddPtr;
+typedef AtomDefnListMap::Range  AtomDefnListRange;
+
+/*
+ * AtomDecls is a map of atoms to (sequences of) Definitions. It is used by
+ * ParseContext to store declarations. A declaration associates a name with a
+ * Definition.
+ *
+ * Declarations with function scope (such as const, var, and function) are
+ * unique in the sense that they override any previous declarations with the
+ * same name. For such declarations, we only need to store a single Definition,
+ * using the method addUnique.
+ *
+ * Declarations with block scope (such as let) are slightly more complex. They
+ * override any previous declarations with the same name, but only do so for
+ * the block they are associated with. This is known as shadowing. For such
+ * definitions, we need to store a sequence of Definitions, including those
+ * introduced by previous declarations (and which are now shadowed), using the
+ * method addShadow. When we leave the block associated with the let, the method
+ * remove is used to unshadow the declaration immediately preceding it.
+ */
+template <typename ParseHandler>
+class AtomDecls
+{
+    typedef typename ParseHandler::DefinitionNode DefinitionNode;
+
+    /* AtomDeclsIter needs to get at the DefnListMap directly. */
+    friend class AtomDeclsIter;
+
+    ExclusiveContext *cx;
+    LifoAlloc &alloc;
+    AtomDefnListMap  *map;
+
+    AtomDecls(const AtomDecls &other) MOZ_DELETE;
+    void operator=(const AtomDecls &other) MOZ_DELETE;
+
+  public:
+    explicit AtomDecls(ExclusiveContext *cx, LifoAlloc &alloc) : cx(cx),
+                                                                 alloc(alloc),
+                                                                 map(nullptr) {}
+
+    ~AtomDecls();
+
+    bool init();
+
+    void clear() {
+        map->clear();
+    }
+
+    /* Return the definition at the head of the chain for |atom|. */
+    DefinitionNode lookupFirst(JSAtom *atom) const {
+        JS_ASSERT(map);
+        AtomDefnListPtr p = map->lookup(atom);
+        if (!p)
+            return ParseHandler::nullDefinition();
+        return p.value().front<ParseHandler>();
+    }
+
+    /* Perform a lookup that can iterate over the definitions associated with |atom|. */
+    DefinitionList::Range lookupMulti(JSAtom *atom) const {
+        JS_ASSERT(map);
+        if (AtomDefnListPtr p = map->lookup(atom))
+            return p.value().all();
+        return DefinitionList::Range();
+    }
+
+    /* Add-or-update a known-unique definition for |atom|. */
+    bool addUnique(JSAtom *atom, DefinitionNode defn) {
+        JS_ASSERT(map);
+        AtomDefnListAddPtr p = map->lookupForAdd(atom);
+        if (!p)
+            return map->add(p, atom, DefinitionList(ParseHandler::definitionToBits(defn)));
+        JS_ASSERT(!p.value().isMultiple());
+        p.value() = DefinitionList(ParseHandler::definitionToBits(defn));
+        return true;
+    }
+
+    bool addShadow(JSAtom *atom, DefinitionNode defn);
+
+    /* Updating the definition for an entry that is known to exist is infallible. */
+    void updateFirst(JSAtom *atom, DefinitionNode defn) {
+        JS_ASSERT(map);
+        AtomDefnListMap::Ptr p = map->lookup(atom);
+        JS_ASSERT(p);
+        p.value().setFront<ParseHandler>(defn);
+    }
+
+    /* Remove the node at the head of the chain for |atom|. */
+    void remove(JSAtom *atom) {
+        JS_ASSERT(map);
+        AtomDefnListMap::Ptr p = map->lookup(atom);
+        if (!p)
+            return;
+
+        DefinitionList &list = p.value();
+        if (!list.popFront()) {
+            map->remove(p);
+            return;
+        }
+    }
+
+    AtomDefnListMap::Range all() const {
+        JS_ASSERT(map);
+        return map->all();
+    }
+
+#ifdef DEBUG
+    void dump();
+#endif
+};
+
+} /* namespace frontend */
+
+} /* namespace js */
+
+namespace mozilla {
+
+template <>
+struct IsPod<js::frontend::DefinitionSingle> : TrueType {};
+
+template <>
+struct IsPod<js::frontend::DefinitionList> : TrueType {};
+
+} /* namespace mozilla */
+
+#endif /* frontend_ParseMaps_h */