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