1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/frontend/ParseMaps.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,511 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#ifndef frontend_ParseMaps_h
1.11 +#define frontend_ParseMaps_h
1.12 +
1.13 +#include "mozilla/Attributes.h"
1.14 +#include "mozilla/TypeTraits.h"
1.15 +
1.16 +#include "ds/InlineMap.h"
1.17 +#include "gc/Barrier.h"
1.18 +#include "js/Vector.h"
1.19 +
1.20 +class JSAtom;
1.21 +
1.22 +typedef uintptr_t jsatomid;
1.23 +
1.24 +namespace js {
1.25 +
1.26 +class LifoAlloc;
1.27 +
1.28 +namespace frontend {
1.29 +
1.30 +class DefinitionSingle;
1.31 +class DefinitionList;
1.32 +
1.33 +typedef InlineMap<JSAtom *, jsatomid, 24> AtomIndexMap;
1.34 +typedef InlineMap<JSAtom *, DefinitionSingle, 24> AtomDefnMap;
1.35 +typedef InlineMap<JSAtom *, DefinitionList, 24> AtomDefnListMap;
1.36 +
1.37 +/*
1.38 + * For all unmapped atoms recorded in al, add a mapping from the atom's index
1.39 + * to its address. map->length must already be set to the number of atoms in
1.40 + * the list and map->vector must point to pre-allocated memory.
1.41 + */
1.42 +void
1.43 +InitAtomMap(AtomIndexMap *indices, HeapPtr<JSAtom> *atoms);
1.44 +
1.45 +/*
1.46 + * A pool that permits the reuse of the backing storage for the defn, index, or
1.47 + * defn-or-header (multi) maps.
1.48 + *
1.49 + * The pool owns all the maps that are given out, and is responsible for
1.50 + * relinquishing all resources when |purgeAll| is triggered.
1.51 + */
1.52 +class ParseMapPool
1.53 +{
1.54 + typedef Vector<void *, 32, SystemAllocPolicy> RecyclableMaps;
1.55 +
1.56 + RecyclableMaps all;
1.57 + RecyclableMaps recyclable;
1.58 +
1.59 + void checkInvariants();
1.60 +
1.61 + void recycle(void *map) {
1.62 + JS_ASSERT(map);
1.63 +#ifdef DEBUG
1.64 + bool ok = false;
1.65 + /* Make sure the map is in |all| but not already in |recyclable|. */
1.66 + for (void **it = all.begin(), **end = all.end(); it != end; ++it) {
1.67 + if (*it == map) {
1.68 + ok = true;
1.69 + break;
1.70 + }
1.71 + }
1.72 + JS_ASSERT(ok);
1.73 + for (void **it = recyclable.begin(), **end = recyclable.end(); it != end; ++it)
1.74 + JS_ASSERT(*it != map);
1.75 +#endif
1.76 + JS_ASSERT(recyclable.length() < all.length());
1.77 + recyclable.infallibleAppend(map); /* Reserved in allocateFresh. */
1.78 + }
1.79 +
1.80 + void *allocateFresh();
1.81 + void *allocate() {
1.82 + if (recyclable.empty())
1.83 + return allocateFresh();
1.84 +
1.85 + void *map = recyclable.popCopy();
1.86 + asAtomMap(map)->clear();
1.87 + return map;
1.88 + }
1.89 +
1.90 + /* Arbitrary atom map type, that has keys and values of the same kind. */
1.91 + typedef AtomIndexMap AtomMapT;
1.92 +
1.93 + static AtomMapT *asAtomMap(void *ptr) {
1.94 + return reinterpret_cast<AtomMapT *>(ptr);
1.95 + }
1.96 +
1.97 + public:
1.98 + ~ParseMapPool() {
1.99 + purgeAll();
1.100 + }
1.101 +
1.102 + void purgeAll();
1.103 +
1.104 + bool empty() const {
1.105 + return all.empty();
1.106 + }
1.107 +
1.108 + /* Fallibly aquire one of the supported map types from the pool. */
1.109 + template <typename T>
1.110 + T *acquire() {
1.111 + return reinterpret_cast<T *>(allocate());
1.112 + }
1.113 +
1.114 + /* Release one of the supported map types back to the pool. */
1.115 +
1.116 + void release(AtomIndexMap *map) {
1.117 + recycle((void *) map);
1.118 + }
1.119 +
1.120 + void release(AtomDefnMap *map) {
1.121 + recycle((void *) map);
1.122 + }
1.123 +
1.124 + void release(AtomDefnListMap *map) {
1.125 + recycle((void *) map);
1.126 + }
1.127 +}; /* ParseMapPool */
1.128 +
1.129 +/*
1.130 + * N.B. This is a POD-type so that it can be included in the ParseNode union.
1.131 + * If possible, use the corresponding |OwnedAtomThingMapPtr| variant.
1.132 + */
1.133 +template <class Map>
1.134 +struct AtomThingMapPtr
1.135 +{
1.136 + Map *map_;
1.137 +
1.138 + void init() { clearMap(); }
1.139 +
1.140 + bool ensureMap(ExclusiveContext *cx);
1.141 + void releaseMap(ExclusiveContext *cx);
1.142 +
1.143 + bool hasMap() const { return map_; }
1.144 + Map *getMap() { return map_; }
1.145 + void setMap(Map *newMap) { JS_ASSERT(!map_); map_ = newMap; }
1.146 + void clearMap() { map_ = nullptr; }
1.147 +
1.148 + Map *operator->() { return map_; }
1.149 + const Map *operator->() const { return map_; }
1.150 + Map &operator*() const { return *map_; }
1.151 +};
1.152 +
1.153 +typedef AtomThingMapPtr<AtomIndexMap> AtomIndexMapPtr;
1.154 +
1.155 +/*
1.156 + * Wrapper around an AtomThingMapPtr (or its derivatives) that automatically
1.157 + * releases a map on destruction, if one has been acquired.
1.158 + */
1.159 +template <typename AtomThingMapPtrT>
1.160 +class OwnedAtomThingMapPtr : public AtomThingMapPtrT
1.161 +{
1.162 + ExclusiveContext *cx;
1.163 +
1.164 + public:
1.165 + explicit OwnedAtomThingMapPtr(ExclusiveContext *cx) : cx(cx) {
1.166 + AtomThingMapPtrT::init();
1.167 + }
1.168 +
1.169 + ~OwnedAtomThingMapPtr() {
1.170 + AtomThingMapPtrT::releaseMap(cx);
1.171 + }
1.172 +};
1.173 +
1.174 +typedef OwnedAtomThingMapPtr<AtomIndexMapPtr> OwnedAtomIndexMapPtr;
1.175 +
1.176 +/*
1.177 + * DefinitionSingle and DefinitionList represent either a single definition
1.178 + * or a list of them. The representation of definitions varies between
1.179 + * parse handlers, being either a Definition* (FullParseHandler) or a
1.180 + * Definition::Kind (SyntaxParseHandler). Methods on the below classes are
1.181 + * templated to distinguish the kind of value wrapped by the class.
1.182 + */
1.183 +
1.184 +/* Wrapper for a single definition. */
1.185 +class DefinitionSingle
1.186 +{
1.187 + uintptr_t bits;
1.188 +
1.189 + public:
1.190 +
1.191 + template <typename ParseHandler>
1.192 + static DefinitionSingle new_(typename ParseHandler::DefinitionNode defn)
1.193 + {
1.194 + DefinitionSingle res;
1.195 + res.bits = ParseHandler::definitionToBits(defn);
1.196 + return res;
1.197 + }
1.198 +
1.199 + template <typename ParseHandler>
1.200 + typename ParseHandler::DefinitionNode get() {
1.201 + return ParseHandler::definitionFromBits(bits);
1.202 + }
1.203 +};
1.204 +
1.205 +struct AtomDefnMapPtr : public AtomThingMapPtr<AtomDefnMap>
1.206 +{
1.207 + template <typename ParseHandler>
1.208 + MOZ_ALWAYS_INLINE
1.209 + typename ParseHandler::DefinitionNode lookupDefn(JSAtom *atom) {
1.210 + AtomDefnMap::Ptr p = map_->lookup(atom);
1.211 + return p ? p.value().get<ParseHandler>() : ParseHandler::nullDefinition();
1.212 + }
1.213 +};
1.214 +
1.215 +typedef OwnedAtomThingMapPtr<AtomDefnMapPtr> OwnedAtomDefnMapPtr;
1.216 +
1.217 +/*
1.218 + * A nonempty list containing one or more pointers to Definitions.
1.219 + *
1.220 + * By far the most common case is that the list contains exactly one
1.221 + * Definition, so the implementation is optimized for that case.
1.222 + *
1.223 + * Nodes for the linked list (if any) are allocated from the tempPool of a
1.224 + * context the caller passes into pushFront and pushBack. This means the
1.225 + * DefinitionList does not own the memory for the nodes: the JSContext does.
1.226 + * As a result, DefinitionList is a POD type; it can be safely and cheaply
1.227 + * copied.
1.228 + */
1.229 +class DefinitionList
1.230 +{
1.231 + public:
1.232 + class Range;
1.233 +
1.234 + private:
1.235 + friend class Range;
1.236 +
1.237 + /* A node in a linked list of Definitions. */
1.238 + struct Node
1.239 + {
1.240 + uintptr_t bits;
1.241 + Node *next;
1.242 +
1.243 + Node(uintptr_t bits, Node *next) : bits(bits), next(next) {}
1.244 + };
1.245 +
1.246 + union {
1.247 + uintptr_t bits;
1.248 + Node *head;
1.249 + } u;
1.250 +
1.251 + Node *firstNode() const {
1.252 + JS_ASSERT(isMultiple());
1.253 + return (Node *) (u.bits & ~0x1);
1.254 + }
1.255 +
1.256 + static Node *
1.257 + allocNode(ExclusiveContext *cx, LifoAlloc &alloc, uintptr_t bits, Node *tail);
1.258 +
1.259 + public:
1.260 + class Range
1.261 + {
1.262 + friend class DefinitionList;
1.263 +
1.264 + Node *node;
1.265 + uintptr_t bits;
1.266 +
1.267 + explicit Range(const DefinitionList &list) {
1.268 + if (list.isMultiple()) {
1.269 + node = list.firstNode();
1.270 + bits = node->bits;
1.271 + } else {
1.272 + node = nullptr;
1.273 + bits = list.u.bits;
1.274 + }
1.275 + }
1.276 +
1.277 + public:
1.278 + /* An empty Range. */
1.279 + Range() : node(nullptr), bits(0) {}
1.280 +
1.281 + void popFront() {
1.282 + JS_ASSERT(!empty());
1.283 + if (!node) {
1.284 + bits = 0;
1.285 + return;
1.286 + }
1.287 + node = node->next;
1.288 + bits = node ? node->bits : 0;
1.289 + }
1.290 +
1.291 + template <typename ParseHandler>
1.292 + typename ParseHandler::DefinitionNode front() {
1.293 + JS_ASSERT(!empty());
1.294 + return ParseHandler::definitionFromBits(bits);
1.295 + }
1.296 +
1.297 + bool empty() const {
1.298 + JS_ASSERT_IF(!bits, !node);
1.299 + return !bits;
1.300 + }
1.301 + };
1.302 +
1.303 + DefinitionList() {
1.304 + u.bits = 0;
1.305 + }
1.306 +
1.307 + explicit DefinitionList(uintptr_t bits) {
1.308 + u.bits = bits;
1.309 + JS_ASSERT(!isMultiple());
1.310 + }
1.311 +
1.312 + explicit DefinitionList(Node *node) {
1.313 + u.head = node;
1.314 + u.bits |= 0x1;
1.315 + JS_ASSERT(isMultiple());
1.316 + }
1.317 +
1.318 + bool isMultiple() const { return (u.bits & 0x1) != 0; }
1.319 +
1.320 + template <typename ParseHandler>
1.321 + typename ParseHandler::DefinitionNode front() {
1.322 + return ParseHandler::definitionFromBits(isMultiple() ? firstNode()->bits : u.bits);
1.323 + }
1.324 +
1.325 + /*
1.326 + * If there are multiple Definitions in this list, remove the first and
1.327 + * return true. Otherwise there is exactly one Definition in the list; do
1.328 + * nothing and return false.
1.329 + */
1.330 + bool popFront() {
1.331 + if (!isMultiple())
1.332 + return false;
1.333 +
1.334 + Node *node = firstNode();
1.335 + Node *next = node->next;
1.336 + if (next->next)
1.337 + *this = DefinitionList(next);
1.338 + else
1.339 + *this = DefinitionList(next->bits);
1.340 + return true;
1.341 + }
1.342 +
1.343 + /*
1.344 + * Add a definition to the front of this list.
1.345 + *
1.346 + * Return true on success. On OOM, report on cx and return false.
1.347 + */
1.348 + template <typename ParseHandler>
1.349 + bool pushFront(ExclusiveContext *cx, LifoAlloc &alloc,
1.350 + typename ParseHandler::DefinitionNode defn) {
1.351 + Node *tail;
1.352 + if (isMultiple()) {
1.353 + tail = firstNode();
1.354 + } else {
1.355 + tail = allocNode(cx, alloc, u.bits, nullptr);
1.356 + if (!tail)
1.357 + return false;
1.358 + }
1.359 +
1.360 + Node *node = allocNode(cx, alloc, ParseHandler::definitionToBits(defn), tail);
1.361 + if (!node)
1.362 + return false;
1.363 + *this = DefinitionList(node);
1.364 + return true;
1.365 + }
1.366 +
1.367 + /* Overwrite the first Definition in the list. */
1.368 + template <typename ParseHandler>
1.369 + void setFront(typename ParseHandler::DefinitionNode defn) {
1.370 + if (isMultiple())
1.371 + firstNode()->bits = ParseHandler::definitionToBits(defn);
1.372 + else
1.373 + *this = DefinitionList(ParseHandler::definitionToBits(defn));
1.374 + }
1.375 +
1.376 + Range all() const { return Range(*this); }
1.377 +
1.378 +#ifdef DEBUG
1.379 + void dump();
1.380 +#endif
1.381 +};
1.382 +
1.383 +typedef AtomDefnMap::Range AtomDefnRange;
1.384 +typedef AtomDefnMap::AddPtr AtomDefnAddPtr;
1.385 +typedef AtomDefnMap::Ptr AtomDefnPtr;
1.386 +typedef AtomIndexMap::AddPtr AtomIndexAddPtr;
1.387 +typedef AtomIndexMap::Ptr AtomIndexPtr;
1.388 +typedef AtomDefnListMap::Ptr AtomDefnListPtr;
1.389 +typedef AtomDefnListMap::AddPtr AtomDefnListAddPtr;
1.390 +typedef AtomDefnListMap::Range AtomDefnListRange;
1.391 +
1.392 +/*
1.393 + * AtomDecls is a map of atoms to (sequences of) Definitions. It is used by
1.394 + * ParseContext to store declarations. A declaration associates a name with a
1.395 + * Definition.
1.396 + *
1.397 + * Declarations with function scope (such as const, var, and function) are
1.398 + * unique in the sense that they override any previous declarations with the
1.399 + * same name. For such declarations, we only need to store a single Definition,
1.400 + * using the method addUnique.
1.401 + *
1.402 + * Declarations with block scope (such as let) are slightly more complex. They
1.403 + * override any previous declarations with the same name, but only do so for
1.404 + * the block they are associated with. This is known as shadowing. For such
1.405 + * definitions, we need to store a sequence of Definitions, including those
1.406 + * introduced by previous declarations (and which are now shadowed), using the
1.407 + * method addShadow. When we leave the block associated with the let, the method
1.408 + * remove is used to unshadow the declaration immediately preceding it.
1.409 + */
1.410 +template <typename ParseHandler>
1.411 +class AtomDecls
1.412 +{
1.413 + typedef typename ParseHandler::DefinitionNode DefinitionNode;
1.414 +
1.415 + /* AtomDeclsIter needs to get at the DefnListMap directly. */
1.416 + friend class AtomDeclsIter;
1.417 +
1.418 + ExclusiveContext *cx;
1.419 + LifoAlloc &alloc;
1.420 + AtomDefnListMap *map;
1.421 +
1.422 + AtomDecls(const AtomDecls &other) MOZ_DELETE;
1.423 + void operator=(const AtomDecls &other) MOZ_DELETE;
1.424 +
1.425 + public:
1.426 + explicit AtomDecls(ExclusiveContext *cx, LifoAlloc &alloc) : cx(cx),
1.427 + alloc(alloc),
1.428 + map(nullptr) {}
1.429 +
1.430 + ~AtomDecls();
1.431 +
1.432 + bool init();
1.433 +
1.434 + void clear() {
1.435 + map->clear();
1.436 + }
1.437 +
1.438 + /* Return the definition at the head of the chain for |atom|. */
1.439 + DefinitionNode lookupFirst(JSAtom *atom) const {
1.440 + JS_ASSERT(map);
1.441 + AtomDefnListPtr p = map->lookup(atom);
1.442 + if (!p)
1.443 + return ParseHandler::nullDefinition();
1.444 + return p.value().front<ParseHandler>();
1.445 + }
1.446 +
1.447 + /* Perform a lookup that can iterate over the definitions associated with |atom|. */
1.448 + DefinitionList::Range lookupMulti(JSAtom *atom) const {
1.449 + JS_ASSERT(map);
1.450 + if (AtomDefnListPtr p = map->lookup(atom))
1.451 + return p.value().all();
1.452 + return DefinitionList::Range();
1.453 + }
1.454 +
1.455 + /* Add-or-update a known-unique definition for |atom|. */
1.456 + bool addUnique(JSAtom *atom, DefinitionNode defn) {
1.457 + JS_ASSERT(map);
1.458 + AtomDefnListAddPtr p = map->lookupForAdd(atom);
1.459 + if (!p)
1.460 + return map->add(p, atom, DefinitionList(ParseHandler::definitionToBits(defn)));
1.461 + JS_ASSERT(!p.value().isMultiple());
1.462 + p.value() = DefinitionList(ParseHandler::definitionToBits(defn));
1.463 + return true;
1.464 + }
1.465 +
1.466 + bool addShadow(JSAtom *atom, DefinitionNode defn);
1.467 +
1.468 + /* Updating the definition for an entry that is known to exist is infallible. */
1.469 + void updateFirst(JSAtom *atom, DefinitionNode defn) {
1.470 + JS_ASSERT(map);
1.471 + AtomDefnListMap::Ptr p = map->lookup(atom);
1.472 + JS_ASSERT(p);
1.473 + p.value().setFront<ParseHandler>(defn);
1.474 + }
1.475 +
1.476 + /* Remove the node at the head of the chain for |atom|. */
1.477 + void remove(JSAtom *atom) {
1.478 + JS_ASSERT(map);
1.479 + AtomDefnListMap::Ptr p = map->lookup(atom);
1.480 + if (!p)
1.481 + return;
1.482 +
1.483 + DefinitionList &list = p.value();
1.484 + if (!list.popFront()) {
1.485 + map->remove(p);
1.486 + return;
1.487 + }
1.488 + }
1.489 +
1.490 + AtomDefnListMap::Range all() const {
1.491 + JS_ASSERT(map);
1.492 + return map->all();
1.493 + }
1.494 +
1.495 +#ifdef DEBUG
1.496 + void dump();
1.497 +#endif
1.498 +};
1.499 +
1.500 +} /* namespace frontend */
1.501 +
1.502 +} /* namespace js */
1.503 +
1.504 +namespace mozilla {
1.505 +
1.506 +template <>
1.507 +struct IsPod<js::frontend::DefinitionSingle> : TrueType {};
1.508 +
1.509 +template <>
1.510 +struct IsPod<js::frontend::DefinitionList> : TrueType {};
1.511 +
1.512 +} /* namespace mozilla */
1.513 +
1.514 +#endif /* frontend_ParseMaps_h */
