The Tor Browser / file revision

 /* -*- 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 */