The Tor Browser / file comparison

comparison: js/src/frontend/ParseMaps.h

js/src/frontend/ParseMaps.h

changeset 0
6474c204b198
equal deleted inserted replaced
-1:000000000000 0:c62879651a45
1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set ts=8 sts=4 et sw=4 tw=99:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 #ifndef frontend_ParseMaps_h
8 #define frontend_ParseMaps_h
9
10 #include "mozilla/Attributes.h"
11 #include "mozilla/TypeTraits.h"
12
13 #include "ds/InlineMap.h"
14 #include "gc/Barrier.h"
15 #include "js/Vector.h"
16
17 class JSAtom;
18
19 typedef uintptr_t jsatomid;
20
21 namespace js {
22
23 class LifoAlloc;
24
25 namespace frontend {
26
27 class DefinitionSingle;
28 class DefinitionList;
29
30 typedef InlineMap<JSAtom *, jsatomid, 24> AtomIndexMap;
31 typedef InlineMap<JSAtom *, DefinitionSingle, 24> AtomDefnMap;
32 typedef InlineMap<JSAtom *, DefinitionList, 24> AtomDefnListMap;
33
34 /*
35 * For all unmapped atoms recorded in al, add a mapping from the atom's index
36 * to its address. map->length must already be set to the number of atoms in
37 * the list and map->vector must point to pre-allocated memory.
38 */
39 void
40 InitAtomMap(AtomIndexMap *indices, HeapPtr<JSAtom> *atoms);
41
42 /*
43 * A pool that permits the reuse of the backing storage for the defn, index, or
44 * defn-or-header (multi) maps.
45 *
46 * The pool owns all the maps that are given out, and is responsible for
47 * relinquishing all resources when |purgeAll| is triggered.
48 */
49 class ParseMapPool
50 {
51 typedef Vector<void *, 32, SystemAllocPolicy> RecyclableMaps;
52
53 RecyclableMaps all;
54 RecyclableMaps recyclable;
55
56 void checkInvariants();
57
58 void recycle(void *map) {
59 JS_ASSERT(map);
60 #ifdef DEBUG
61 bool ok = false;
62 /* Make sure the map is in |all| but not already in |recyclable|. */
63 for (void **it = all.begin(), **end = all.end(); it != end; ++it) {
64 if (*it == map) {
65 ok = true;
66 break;
67 }
68 }
69 JS_ASSERT(ok);
70 for (void **it = recyclable.begin(), **end = recyclable.end(); it != end; ++it)
71 JS_ASSERT(*it != map);
72 #endif
73 JS_ASSERT(recyclable.length() < all.length());
74 recyclable.infallibleAppend(map); /* Reserved in allocateFresh. */
75 }
76
77 void *allocateFresh();
78 void *allocate() {
79 if (recyclable.empty())
80 return allocateFresh();
81
82 void *map = recyclable.popCopy();
83 asAtomMap(map)->clear();
84 return map;
85 }
86
87 /* Arbitrary atom map type, that has keys and values of the same kind. */
88 typedef AtomIndexMap AtomMapT;
89
90 static AtomMapT *asAtomMap(void *ptr) {
91 return reinterpret_cast<AtomMapT *>(ptr);
92 }
93
94 public:
95 ~ParseMapPool() {
96 purgeAll();
97 }
98
99 void purgeAll();
100
101 bool empty() const {
102 return all.empty();
103 }
104
105 /* Fallibly aquire one of the supported map types from the pool. */
106 template <typename T>
107 T *acquire() {
108 return reinterpret_cast<T *>(allocate());
109 }
110
111 /* Release one of the supported map types back to the pool. */
112
113 void release(AtomIndexMap *map) {
114 recycle((void *) map);
115 }
116
117 void release(AtomDefnMap *map) {
118 recycle((void *) map);
119 }
120
121 void release(AtomDefnListMap *map) {
122 recycle((void *) map);
123 }
124 }; /* ParseMapPool */
125
126 /*
127 * N.B. This is a POD-type so that it can be included in the ParseNode union.
128 * If possible, use the corresponding |OwnedAtomThingMapPtr| variant.
129 */
130 template <class Map>
131 struct AtomThingMapPtr
132 {
133 Map *map_;
134
135 void init() { clearMap(); }
136
137 bool ensureMap(ExclusiveContext *cx);
138 void releaseMap(ExclusiveContext *cx);
139
140 bool hasMap() const { return map_; }
141 Map *getMap() { return map_; }
142 void setMap(Map *newMap) { JS_ASSERT(!map_); map_ = newMap; }
143 void clearMap() { map_ = nullptr; }
144
145 Map *operator->() { return map_; }
146 const Map *operator->() const { return map_; }
147 Map &operator*() const { return *map_; }
148 };
149
150 typedef AtomThingMapPtr<AtomIndexMap> AtomIndexMapPtr;
151
152 /*
153 * Wrapper around an AtomThingMapPtr (or its derivatives) that automatically
154 * releases a map on destruction, if one has been acquired.
155 */
156 template <typename AtomThingMapPtrT>
157 class OwnedAtomThingMapPtr : public AtomThingMapPtrT
158 {
159 ExclusiveContext *cx;
160
161 public:
162 explicit OwnedAtomThingMapPtr(ExclusiveContext *cx) : cx(cx) {
163 AtomThingMapPtrT::init();
164 }
165
166 ~OwnedAtomThingMapPtr() {
167 AtomThingMapPtrT::releaseMap(cx);
168 }
169 };
170
171 typedef OwnedAtomThingMapPtr<AtomIndexMapPtr> OwnedAtomIndexMapPtr;
172
173 /*
174 * DefinitionSingle and DefinitionList represent either a single definition
175 * or a list of them. The representation of definitions varies between
176 * parse handlers, being either a Definition* (FullParseHandler) or a
177 * Definition::Kind (SyntaxParseHandler). Methods on the below classes are
178 * templated to distinguish the kind of value wrapped by the class.
179 */
180
181 /* Wrapper for a single definition. */
182 class DefinitionSingle
183 {
184 uintptr_t bits;
185
186 public:
187
188 template <typename ParseHandler>
189 static DefinitionSingle new_(typename ParseHandler::DefinitionNode defn)
190 {
191 DefinitionSingle res;
192 res.bits = ParseHandler::definitionToBits(defn);
193 return res;
194 }
195
196 template <typename ParseHandler>
197 typename ParseHandler::DefinitionNode get() {
198 return ParseHandler::definitionFromBits(bits);
199 }
200 };
201
202 struct AtomDefnMapPtr : public AtomThingMapPtr<AtomDefnMap>
203 {
204 template <typename ParseHandler>
205 MOZ_ALWAYS_INLINE
206 typename ParseHandler::DefinitionNode lookupDefn(JSAtom *atom) {
207 AtomDefnMap::Ptr p = map_->lookup(atom);
208 return p ? p.value().get<ParseHandler>() : ParseHandler::nullDefinition();
209 }
210 };
211
212 typedef OwnedAtomThingMapPtr<AtomDefnMapPtr> OwnedAtomDefnMapPtr;
213
214 /*
215 * A nonempty list containing one or more pointers to Definitions.
216 *
217 * By far the most common case is that the list contains exactly one
218 * Definition, so the implementation is optimized for that case.
219 *
220 * Nodes for the linked list (if any) are allocated from the tempPool of a
221 * context the caller passes into pushFront and pushBack. This means the
222 * DefinitionList does not own the memory for the nodes: the JSContext does.
223 * As a result, DefinitionList is a POD type; it can be safely and cheaply
224 * copied.
225 */
226 class DefinitionList
227 {
228 public:
229 class Range;
230
231 private:
232 friend class Range;
233
234 /* A node in a linked list of Definitions. */
235 struct Node
236 {
237 uintptr_t bits;
238 Node *next;
239
240 Node(uintptr_t bits, Node *next) : bits(bits), next(next) {}
241 };
242
243 union {
244 uintptr_t bits;
245 Node *head;
246 } u;
247
248 Node *firstNode() const {
249 JS_ASSERT(isMultiple());
250 return (Node *) (u.bits & ~0x1);
251 }
252
253 static Node *
254 allocNode(ExclusiveContext *cx, LifoAlloc &alloc, uintptr_t bits, Node *tail);
255
256 public:
257 class Range
258 {
259 friend class DefinitionList;
260
261 Node *node;
262 uintptr_t bits;
263
264 explicit Range(const DefinitionList &list) {
265 if (list.isMultiple()) {
266 node = list.firstNode();
267 bits = node->bits;
268 } else {
269 node = nullptr;
270 bits = list.u.bits;
271 }
272 }
273
274 public:
275 /* An empty Range. */
276 Range() : node(nullptr), bits(0) {}
277
278 void popFront() {
279 JS_ASSERT(!empty());
280 if (!node) {
281 bits = 0;
282 return;
283 }
284 node = node->next;
285 bits = node ? node->bits : 0;
286 }
287
288 template <typename ParseHandler>
289 typename ParseHandler::DefinitionNode front() {
290 JS_ASSERT(!empty());
291 return ParseHandler::definitionFromBits(bits);
292 }
293
294 bool empty() const {
295 JS_ASSERT_IF(!bits, !node);
296 return !bits;
297 }
298 };
299
300 DefinitionList() {
301 u.bits = 0;
302 }
303
304 explicit DefinitionList(uintptr_t bits) {
305 u.bits = bits;
306 JS_ASSERT(!isMultiple());
307 }
308
309 explicit DefinitionList(Node *node) {
310 u.head = node;
311 u.bits |= 0x1;
312 JS_ASSERT(isMultiple());
313 }
314
315 bool isMultiple() const { return (u.bits & 0x1) != 0; }
316
317 template <typename ParseHandler>
318 typename ParseHandler::DefinitionNode front() {
319 return ParseHandler::definitionFromBits(isMultiple() ? firstNode()->bits : u.bits);
320 }
321
322 /*
323 * If there are multiple Definitions in this list, remove the first and
324 * return true. Otherwise there is exactly one Definition in the list; do
325 * nothing and return false.
326 */
327 bool popFront() {
328 if (!isMultiple())
329 return false;
330
331 Node *node = firstNode();
332 Node *next = node->next;
333 if (next->next)
334 *this = DefinitionList(next);
335 else
336 *this = DefinitionList(next->bits);
337 return true;
338 }
339
340 /*
341 * Add a definition to the front of this list.
342 *
343 * Return true on success. On OOM, report on cx and return false.
344 */
345 template <typename ParseHandler>
346 bool pushFront(ExclusiveContext *cx, LifoAlloc &alloc,
347 typename ParseHandler::DefinitionNode defn) {
348 Node *tail;
349 if (isMultiple()) {
350 tail = firstNode();
351 } else {
352 tail = allocNode(cx, alloc, u.bits, nullptr);
353 if (!tail)
354 return false;
355 }
356
357 Node *node = allocNode(cx, alloc, ParseHandler::definitionToBits(defn), tail);
358 if (!node)
359 return false;
360 *this = DefinitionList(node);
361 return true;
362 }
363
364 /* Overwrite the first Definition in the list. */
365 template <typename ParseHandler>
366 void setFront(typename ParseHandler::DefinitionNode defn) {
367 if (isMultiple())
368 firstNode()->bits = ParseHandler::definitionToBits(defn);
369 else
370 *this = DefinitionList(ParseHandler::definitionToBits(defn));
371 }
372
373 Range all() const { return Range(*this); }
374
375 #ifdef DEBUG
376 void dump();
377 #endif
378 };
379
380 typedef AtomDefnMap::Range AtomDefnRange;
381 typedef AtomDefnMap::AddPtr AtomDefnAddPtr;
382 typedef AtomDefnMap::Ptr AtomDefnPtr;
383 typedef AtomIndexMap::AddPtr AtomIndexAddPtr;
384 typedef AtomIndexMap::Ptr AtomIndexPtr;
385 typedef AtomDefnListMap::Ptr AtomDefnListPtr;
386 typedef AtomDefnListMap::AddPtr AtomDefnListAddPtr;
387 typedef AtomDefnListMap::Range AtomDefnListRange;
388
389 /*
390 * AtomDecls is a map of atoms to (sequences of) Definitions. It is used by
391 * ParseContext to store declarations. A declaration associates a name with a
392 * Definition.
393 *
394 * Declarations with function scope (such as const, var, and function) are
395 * unique in the sense that they override any previous declarations with the
396 * same name. For such declarations, we only need to store a single Definition,
397 * using the method addUnique.
398 *
399 * Declarations with block scope (such as let) are slightly more complex. They
400 * override any previous declarations with the same name, but only do so for
401 * the block they are associated with. This is known as shadowing. For such
402 * definitions, we need to store a sequence of Definitions, including those
403 * introduced by previous declarations (and which are now shadowed), using the
404 * method addShadow. When we leave the block associated with the let, the method
405 * remove is used to unshadow the declaration immediately preceding it.
406 */
407 template <typename ParseHandler>
408 class AtomDecls
409 {
410 typedef typename ParseHandler::DefinitionNode DefinitionNode;
411
412 /* AtomDeclsIter needs to get at the DefnListMap directly. */
413 friend class AtomDeclsIter;
414
415 ExclusiveContext *cx;
416 LifoAlloc &alloc;
417 AtomDefnListMap *map;
418
419 AtomDecls(const AtomDecls &other) MOZ_DELETE;
420 void operator=(const AtomDecls &other) MOZ_DELETE;
421
422 public:
423 explicit AtomDecls(ExclusiveContext *cx, LifoAlloc &alloc) : cx(cx),
424 alloc(alloc),
425 map(nullptr) {}
426
427 ~AtomDecls();
428
429 bool init();
430
431 void clear() {
432 map->clear();
433 }
434
435 /* Return the definition at the head of the chain for |atom|. */
436 DefinitionNode lookupFirst(JSAtom *atom) const {
437 JS_ASSERT(map);
438 AtomDefnListPtr p = map->lookup(atom);
439 if (!p)
440 return ParseHandler::nullDefinition();
441 return p.value().front<ParseHandler>();
442 }
443
444 /* Perform a lookup that can iterate over the definitions associated with |atom|. */
445 DefinitionList::Range lookupMulti(JSAtom *atom) const {
446 JS_ASSERT(map);
447 if (AtomDefnListPtr p = map->lookup(atom))
448 return p.value().all();
449 return DefinitionList::Range();
450 }
451
452 /* Add-or-update a known-unique definition for |atom|. */
453 bool addUnique(JSAtom *atom, DefinitionNode defn) {
454 JS_ASSERT(map);
455 AtomDefnListAddPtr p = map->lookupForAdd(atom);
456 if (!p)
457 return map->add(p, atom, DefinitionList(ParseHandler::definitionToBits(defn)));
458 JS_ASSERT(!p.value().isMultiple());
459 p.value() = DefinitionList(ParseHandler::definitionToBits(defn));
460 return true;
461 }
462
463 bool addShadow(JSAtom *atom, DefinitionNode defn);
464
465 /* Updating the definition for an entry that is known to exist is infallible. */
466 void updateFirst(JSAtom *atom, DefinitionNode defn) {
467 JS_ASSERT(map);
468 AtomDefnListMap::Ptr p = map->lookup(atom);
469 JS_ASSERT(p);
470 p.value().setFront<ParseHandler>(defn);
471 }
472
473 /* Remove the node at the head of the chain for |atom|. */
474 void remove(JSAtom *atom) {
475 JS_ASSERT(map);
476 AtomDefnListMap::Ptr p = map->lookup(atom);
477 if (!p)
478 return;
479
480 DefinitionList &list = p.value();
481 if (!list.popFront()) {
482 map->remove(p);
483 return;
484 }
485 }
486
487 AtomDefnListMap::Range all() const {
488 JS_ASSERT(map);
489 return map->all();
490 }
491
492 #ifdef DEBUG
493 void dump();
494 #endif
495 };
496
497 } /* namespace frontend */
498
499 } /* namespace js */
500
501 namespace mozilla {
502
503 template <>
504 struct IsPod<js::frontend::DefinitionSingle> : TrueType {};
505
506 template <>
507 struct IsPod<js::frontend::DefinitionList> : TrueType {};
508
509 } /* namespace mozilla */
510
511 #endif /* frontend_ParseMaps_h */

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial