← Back to branch summary

~ubuntu-branches/ubuntu/saucy/mozjs17/saucy

« back to all changes in this revision

Viewing changes to js/src/frontend/ParseMaps.h

  • Committer: Package Import Robot
  • Author(s): Rico Tzschichholz
  • Date: 2013-05-25 12:24:23 UTC
  • Revision ID: package-import@ubuntu.com-20130525122423-zmxucrhtensw90xy
Tags: upstream-17.0.0
Import upstream version 17.0.0

Show diffs side-by-side

added added

removed removed

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