tor-browser

ScopeBindingCache.h (11945B)

---

/* -*- 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/Assertions.h"  // mozilla::MakeCompilerAssumeUnreachableFakeValue
#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/StringType.h"  // JSAtom

namespace js {

template <typename NameT>
class AbstractBaseScopeData;

namespace frontend {

struct CompilationAtomCache;
struct CompilationStencil;
struct ScopeStencilRef;
struct FakeStencilGlobalScope;
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);
 GenericAtom(const FakeStencilGlobalScope& scope, TaggedParserAtomIndex index)
     : ref((JSAtom*)nullptr) {
   MOZ_MAKE_COMPILER_ASSUME_IS_UNREACHABLE();
 }

 // 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);
   Lookup(const FakeStencilGlobalScope& scope_ref, const GenericAtom& other)
       : keyStencil(mozilla::MakeCompilerAssumeUnreachableFakeValue<
                    const CompilationStencil&>()),
         other(other) {
     MOZ_MAKE_COMPILER_ASSUME_IS_UNREACHABLE();
   }
 };

 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);
 virtual bool canCacheFor(const FakeStencilGlobalScope& 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);
 virtual BindingMap<TaggedParserAtomIndex>* createCacheFor(
     const FakeStencilGlobalScope& 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);
 virtual BindingMap<TaggedParserAtomIndex>* lookupScope(
     const FakeStencilGlobalScope& 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;
 bool canCacheFor(const FakeStencilGlobalScope& 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 InitialStencilAndDelazifications& stencils_;
#endif

public:
 explicit StencilScopeBindingCache(
     const InitialStencilAndDelazifications& stencils)
#ifdef DEBUG
     : stencils_(stencils)
#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;
 bool canCacheFor(const FakeStencilGlobalScope& ref) override;

 BindingMap<TaggedParserAtomIndex>* createCacheFor(
     ScopeStencilRef ref) override;
 BindingMap<TaggedParserAtomIndex>* createCacheFor(
     const FakeStencilGlobalScope& ref) override;

 BindingMap<TaggedParserAtomIndex>* lookupScope(ScopeStencilRef ref,
                                                CacheGeneration gen) override;
 BindingMap<TaggedParserAtomIndex>* lookupScope(
     const FakeStencilGlobalScope& 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