summaryrefslogtreecommitdiffstats
path: root/js/src/frontend/ScopeBindingCache.h
blob: ee3dc35e33bf565517769c2ea8121847dc4ef7f3 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
 * vim: set ts=8 sts=2 et sw=2 tw=80:
 * 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_ScopeBindingCache_h
#define frontend_ScopeBindingCache_h

#include "mozilla/Attributes.h"  // MOZ_STACK_CLASS
#include "mozilla/HashTable.h"   // mozilla::HashMap

#include "jstypes.h"  // JS_PUBLIC_API

#include "frontend/NameAnalysisTypes.h"  // NameLocation
#include "frontend/ParserAtom.h"  // TaggedPArserAtomIndex, ParserAtomsTable

#include "js/Utility.h"  // AutoEnterOOMUnsafeRegion

#include "vm/Scope.h"       // AbstractBaseScopeData
#include "vm/StringType.h"  // JSAtom

namespace js {
namespace frontend {

struct CompilationAtomCache;
struct CompilationStencil;
struct ScopeStencilRef;
struct CompilationStencilMerger;

// Generic atom wrapper which provides a way to interpret any Atom given
// contextual information. Thus, this structure offers the ability to compare
// Atom from different domains.
//
// This structure provides a `hash` field which is universal across all Atom
// representations. Thus, Atoms from different contexes can be registered in a
// hash table and looked up with a different Atom kind.
struct GenericAtom {
  // Emitter names are TaggedParserAtomIndex which are registered in the
  // ParserAtomsTable of an extensible compilation stencil, frequently related
  // to bytecode emitter, which lookup names in the scope chain to replace names
  // by variable locations.
  struct EmitterName {
    FrontendContext* fc;
    ParserAtomsTable& parserAtoms;
    CompilationAtomCache& atomCache;
    TaggedParserAtomIndex index;

    EmitterName(FrontendContext* fc, ParserAtomsTable& parserAtoms,
                CompilationAtomCache& atomCache, TaggedParserAtomIndex index)
        : fc(fc),
          parserAtoms(parserAtoms),
          atomCache(atomCache),
          index(index) {}
  };

  // Stencil names are TaggedParserAtomIndex which are registered in a
  // ParserAtomVector of a compilation stencil, frequently related to the result
  // of a compilation. It can be seen while manipulating names of a scope chain
  // while delazifying functions using a stencil for context.
  struct StencilName {
    const CompilationStencil& stencil;
    TaggedParserAtomIndex index;
  };

  // Any names are references to different Atom representation, including some
  // which are interpretable given some contexts such as EmitterName and
  // StencilName.
  using AnyName = mozilla::Variant<EmitterName, StencilName, JSAtom*>;

  HashNumber hash;
  AnyName ref;

  // Constructor for atoms managed by an ExtensibleCompilationState, while
  // compiling a script.
  GenericAtom(FrontendContext* fc, ParserAtomsTable& parserAtoms,
              CompilationAtomCache& atomCache, TaggedParserAtomIndex index);

  // Constructors for atoms managed by a CompilationStencil or a
  // BorrowingCompilationStencil, which provide contextual information from an
  // already compiled script.
  GenericAtom(const CompilationStencil& context, TaggedParserAtomIndex index);
  GenericAtom(ScopeStencilRef& scope, TaggedParserAtomIndex index);

  // Constructor for atoms managed by the Garbage Collector, while providing
  // contextual scope information when delazifying functions on the main thread.
  GenericAtom(const Scope*, JSAtom* ptr) : GenericAtom(ptr) {}
  explicit GenericAtom(JSAtom* ptr) : ref(ptr) { hash = ptr->hash(); }

  bool operator==(const GenericAtom& other) const;
};

template <typename NameT>
struct BindingHasher;

template <>
struct BindingHasher<TaggedParserAtomIndex> {
  // This is a GenericAtom::StencilName stripped from its context which is the
  // same for every key.
  using Key = TaggedParserAtomIndex;
  struct Lookup {
    // When building a BindingMap, we assume that the TaggedParserAtomIndex is
    // coming from an existing Stencil, and is not an EmitterName.
    const CompilationStencil& keyStencil;
    GenericAtom other;

    Lookup(ScopeStencilRef& scope_ref, const GenericAtom& other);
  };

  static HashNumber hash(const Lookup& aLookup) { return aLookup.other.hash; }

  static bool match(const Key& aKey, const Lookup& aLookup) {
    GenericAtom key(aLookup.keyStencil, aKey);
    return key == aLookup.other;
  }
};

template <>
struct BindingHasher<JSAtom*> {
  using Key = JSAtom*;
  struct Lookup {
    GenericAtom other;

    template <typename Any>
    Lookup(const Any&, const GenericAtom& other) : other(other) {}
  };

  static HashNumber hash(const Lookup& aLookup) { return aLookup.other.hash; }

  static bool match(const Key& aKey, const Lookup& aLookup) {
    GenericAtom key(aKey);
    return key == aLookup.other;
  }
};

// Map the bound names to their respective name location. This is used to avoid
// doing a linear lookup over the list of bindings each time we are looking for
// a single name.
//
// The names given used as a key are either JSAtom in the case of a on-demand
// delazification, or a TaggedParserAtomIndex in case of a
// concurrent-delazification. In both case Lookup arguments are not trivially
// created out of a key, as in the case of a TaggedParserAtomIndex, the
// CompilationStencil should be provided to interpret the TaggedParserAtomIndex
// which are stored in this hash table.
template <typename NameT>
struct BindingMap {
  using Lookup = typename BindingHasher<NameT>::Lookup;
  using Map =
      HashMap<NameT, NameLocation, BindingHasher<NameT>, js::SystemAllocPolicy>;

  Map hashMap;
  mozilla::Maybe<NameLocation> catchAll;
};

// For each list of bound names, map the list of bound names to the hash table
// which is used to reduce the time needed per lookup.
//
// The name parameter are either JSAtom in the case of a on-demand
// delazification, or a TaggedParserAtomIndex in case of a
// concurrent-delazification.
template <typename NameT, typename ScopeT = NameT>
using ScopeBindingMap =
    HashMap<AbstractBaseScopeData<ScopeT>*, BindingMap<NameT>,
            DefaultHasher<AbstractBaseScopeData<ScopeT>*>,
            js::SystemAllocPolicy>;

// Common interface for a cache holding the mapping of Scope to a hash table
// which mirror the binding mapping stored in the scope.
class ScopeBindingCache {
 public:
  using CacheGeneration = size_t;

  virtual CacheGeneration getCurrentGeneration() const = 0;

  // Check whether the cache provided as argument is capable of storing the type
  // of scope given as arguments.
  virtual bool canCacheFor(Scope* ptr);
  virtual bool canCacheFor(ScopeStencilRef ref);

  // Create a new BindingMap cache for a given scope. This cache should then be
  // filled with all names which might be looked up.
  virtual BindingMap<JSAtom*>* createCacheFor(Scope* ptr);
  virtual BindingMap<TaggedParserAtomIndex>* createCacheFor(
      ScopeStencilRef ref);

  // Return the BindingMap created for the associated scope, unless the
  // generation value does not match the one stored internally, in which case a
  // null pointer is always returned.
  virtual BindingMap<JSAtom*>* lookupScope(Scope* ptr, CacheGeneration gen);
  virtual BindingMap<TaggedParserAtomIndex>* lookupScope(ScopeStencilRef ref,
                                                         CacheGeneration gen);
};

// NoScopeBindingCache is a no-op which does not implement a ScopeBindingCache.
//
// This is useful when compiling a global script or module, where we are not
// interested in looking up anything from the enclosing scope chain.
class NoScopeBindingCache final : public ScopeBindingCache {
 public:
  CacheGeneration getCurrentGeneration() const override { return 1; };

  bool canCacheFor(Scope* ptr) override;
  bool canCacheFor(ScopeStencilRef ref) override;
};

// StencilScopeBindingCache provides an interface to cache the bindings provided
// by a CompilationStencilMerger.
//
// This cache lives on the stack and its content would be invalidated once going
// out of scope. The constructor expects a reference to a
// CompilationStencilMerger, that is expected to:
//   - out-live this class.
//   - contain the enclosing scope which are manipulated by this class.
//   - be the receiver of delazified functions.
class MOZ_STACK_CLASS StencilScopeBindingCache final
    : public ScopeBindingCache {
  ScopeBindingMap<TaggedParserAtomIndex> scopeMap;
#ifdef DEBUG
  const CompilationStencilMerger& merger_;
#endif

 public:
  explicit StencilScopeBindingCache(const CompilationStencilMerger& merger)
#ifdef DEBUG
      : merger_(merger)
#endif
  {
  }

  // The cache content is always valid as long as it does not out-live the
  // CompilationStencilMerger. No need for a generation number.
  CacheGeneration getCurrentGeneration() const override { return 1; }

  bool canCacheFor(ScopeStencilRef ref) override;
  BindingMap<TaggedParserAtomIndex>* createCacheFor(
      ScopeStencilRef ref) override;
  BindingMap<TaggedParserAtomIndex>* lookupScope(ScopeStencilRef ref,
                                                 CacheGeneration gen) override;
};

// RuntimeScopeBindingCache is used to hold the binding map for each scope which
// is hold by a Scope managed by the garbage collector.
//
// This cache is not thread safe.
//
// The generation number is used to assert the validity of the cached content.
// During a GC, the cached content is thrown away and getCurrentGeneration
// returns a different number. When the generation number differs from the
// initialization of the cached content, the cache content might be renewed or
// ignored.
class RuntimeScopeBindingCache final : public ScopeBindingCache {
  ScopeBindingMap<JSAtom*, JSAtom> scopeMap;

  // This value is initialized to 1, such that we can differentiate it from the
  // typical 0-init of size_t values, when non-initialized.
  size_t cacheGeneration = 1;

 public:
  CacheGeneration getCurrentGeneration() const override {
    return cacheGeneration;
  }

  bool canCacheFor(Scope* ptr) override;
  BindingMap<JSAtom*>* createCacheFor(Scope* ptr) override;
  BindingMap<JSAtom*>* lookupScope(Scope* ptr, CacheGeneration gen) override;

  // The ScopeBindingCache is not instrumented for tracing weakly the keys used
  // for mapping to the NameLocation. Instead, we always purge during compaction
  // or collection, and increment the cacheGeneration to notify all consumers
  // that the cache can no longer be used without being re-populated.
  void purge() {
    cacheGeneration++;
    scopeMap.clearAndCompact();
  }
};

}  // namespace frontend
}  // namespace js

#endif  // frontend_ScopeBindingCache_h