diff options
Diffstat (limited to 'js/src/frontend/UsedNameTracker.h')
| -rw-r--r-- | js/src/frontend/UsedNameTracker.h | 265 |
1 files changed, 265 insertions, 0 deletions
diff --git a/js/src/frontend/UsedNameTracker.h b/js/src/frontend/UsedNameTracker.h new file mode 100644 index 0000000000..2a52208128 --- /dev/null +++ b/js/src/frontend/UsedNameTracker.h @@ -0,0 +1,265 @@ +/* -*- 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_UsedNameTracker_h +#define frontend_UsedNameTracker_h + +#include "mozilla/Assertions.h" +#include "mozilla/Maybe.h" + +#include <stdint.h> + +#include "frontend/ParserAtom.h" // TaggedParserAtomIndex +#include "frontend/TaggedParserAtomIndexHasher.h" // TaggedParserAtomIndexHasher +#include "frontend/Token.h" +#include "js/AllocPolicy.h" +#include "js/HashTable.h" +#include "js/Vector.h" + +namespace js { +namespace frontend { + +// A data structure for tracking used names per parsing session in order to +// compute which bindings are closed over. Scripts and scopes are numbered +// monotonically in textual order and unresolved uses of a name are tracked by +// lists of identifier uses, which are a pair of (ScriptId,ScopeId). +// +// For an identifier `i` with a use (ScriptId,ScopeId) in the Used list, +// ScriptId tracks the most nested script that has a use of u, and ScopeId +// tracks the most nested scope that is still being parsed (as the lists will be +// filtered as we finish processing a particular scope). +// +// ScriptId is used to answer the question "is `i` used by a nested function?" +// ScopeId is used to answer the question "is `i` used in any scopes currently +// being parsed?" +// +// The algorithm: +// +// Let Used be a map of names to lists. +// Let Declared(ScopeId) be a list of declarations for a scope numbered with +// ScopeId +// +// 1. Number all scopes in monotonic increasing order in textual order. +// 2. Number all scripts in monotonic increasing order in textual order. +// 3. When an identifier `i` is used in (ScriptId,ScopeId), append that use to +// the list Used[i] (creating the list and table entry if necessary). +// 4. When an identifier `i` is declared in a scope numbered ScopeId, append `i` +// to Declared(ScopeId). +// 5. When we finish parsing a scope numbered with ScopeId, in script numbered +// ScriptId, for each declared name d in Declared(ScopeId): +// a. If d is found in Used, mark d as closed over if there is a value +// (UsedScriptId, UsedScopeId) in Used[d] such that UsedScriptId > ScriptId +// and UsedScopeId > ScopeId. +// b. Remove all values uses in Used[d] where UsedScopeId > ScopeId. +// +// Steps 1 and 2 are implemented by UsedNameTracker::next{Script,Scope}Id. +// Step 3 is implemented by UsedNameTracker::noteUsedInScope. +// Step 4 is implemented by ParseContext::Scope::addDeclaredName. +// Step 5 is implemented by UsedNameTracker::noteBoundInScope and +// Parser::propagateFreeNamesAndMarkClosedOverBindings +// +// The following is a worked example to show how the algorithm works on a +// relatively simple piece of code. (clang-format is disabled due to the width +// of the example). + +// clang-format off +// +// // Script 1, Scope 1 +// var x = 1; // Declared(1) = [x]; +// function f() {// Script 2, Scope 2 +// if (x > 10) { //Scope 3 // Used[x] = [(2,2)]; +// var x = 12; // Declared(3) = [x]; +// function g() // Script 3 +// { // Scope 4 +// return x; // Used[x] = [(2,2), (3,4)] +// } // Leaving Script 3, Scope 4: No declared variables. +// } // Leaving Script 2, Scope 3: Declared(3) = [x]; +// // - Used[x][1] = (2,2) is not > (2,3) +// // - Used[x][2] = (3,4) is > (2,3), so mark x as closed over. +// // - Update Used[x]: [] -- Makes sense, as at this point we have +// // bound all the unbound x to a particlar +// // declaration.. +// +// else { // Scope 5 +// var x = 14; // Declared(5) = [x] +// function g() // Script 4 +// { // Scope 6 +// return y; // Used[y] = [(4,6)] +// } // Leaving Script 4, Scope 6: No declarations. +// } // Leaving Script 2, Scope 5: Declared(5) = [x] +// // - Used[x] = [], so don't mark x as closed over. +// var y = 12; // Declared(2) = [y] +// } // Leaving Script 2, Scope 2: Declared(2) = [y] +// // - Used[y][1] = (4,6) is > (2,2), so mark y as closed over. +// // - Update Used[y]: []. + +// clang-format on + +struct UnboundPrivateName { + TaggedParserAtomIndex atom; + TokenPos position; + + UnboundPrivateName(TaggedParserAtomIndex atom, TokenPos position) + : atom(atom), position(position) {} +}; + +class UsedNameTracker { + public: + struct Use { + uint32_t scriptId; + uint32_t scopeId; + }; + + class UsedNameInfo { + friend class UsedNameTracker; + + Vector<Use, 6> uses_; + + void resetToScope(uint32_t scriptId, uint32_t scopeId); + + NameVisibility visibility_ = NameVisibility::Public; + + // The first place this name was used. This is important to track + // for private names, as we will use this location to issue + // diagnostics for using a name that's not defined lexically. + mozilla::Maybe<TokenPos> firstUsePos_; + + public: + explicit UsedNameInfo(FrontendContext* fc, NameVisibility visibility, + mozilla::Maybe<TokenPos> position) + : uses_(fc), visibility_(visibility), firstUsePos_(position) {} + + UsedNameInfo(UsedNameInfo&& other) = default; + + bool noteUsedInScope(uint32_t scriptId, uint32_t scopeId) { + if (uses_.empty() || uses_.back().scopeId < scopeId) { + return uses_.append(Use{scriptId, scopeId}); + } + return true; + } + + void noteBoundInScope(uint32_t scriptId, uint32_t scopeId, + bool* closedOver) { + *closedOver = false; + while (!uses_.empty()) { + Use& innermost = uses_.back(); + if (innermost.scopeId < scopeId) { + break; + } + if (innermost.scriptId > scriptId) { + *closedOver = true; + } + uses_.popBack(); + } + } + + bool isUsedInScript(uint32_t scriptId) const { + return !uses_.empty() && uses_.back().scriptId >= scriptId; + } + + // To allow disambiguating public and private symbols + bool isPublic() { return visibility_ == NameVisibility::Public; } + + bool empty() const { return uses_.empty(); } + + mozilla::Maybe<TokenPos> pos() { return firstUsePos_; } + + // When we leave a scope, and subsequently find a new private name + // reference, we don't want our error messages to be attributed to an old + // scope, so we update the position in that scenario. + void maybeUpdatePos(mozilla::Maybe<TokenPos> p) { + MOZ_ASSERT_IF(!isPublic(), p.isSome()); + + if (empty() && !isPublic()) { + firstUsePos_ = p; + } + } + }; + + using UsedNameMap = + HashMap<TaggedParserAtomIndex, UsedNameInfo, TaggedParserAtomIndexHasher>; + + private: + // The map of names to chains of uses. + UsedNameMap map_; + + // Monotonically increasing id for all nested scripts. + uint32_t scriptCounter_; + + // Monotonically increasing id for all nested scopes. + uint32_t scopeCounter_; + + // Set if a private name was encountered. + // Used to short circuit some private field early error checks + bool hasPrivateNames_; + + public: + explicit UsedNameTracker(FrontendContext* fc) + : map_(fc), + scriptCounter_(0), + scopeCounter_(0), + hasPrivateNames_(false) {} + + uint32_t nextScriptId() { + MOZ_ASSERT(scriptCounter_ != UINT32_MAX, + "ParseContext::Scope::init should have prevented wraparound"); + return scriptCounter_++; + } + + uint32_t nextScopeId() { + MOZ_ASSERT(scopeCounter_ != UINT32_MAX); + return scopeCounter_++; + } + + UsedNameMap::Ptr lookup(TaggedParserAtomIndex name) const { + return map_.lookup(name); + } + + [[nodiscard]] bool noteUse( + FrontendContext* fc, TaggedParserAtomIndex name, + NameVisibility visibility, uint32_t scriptId, uint32_t scopeId, + mozilla::Maybe<TokenPos> tokenPosition = mozilla::Nothing()); + + // Fill maybeUnboundName with the first (source order) unbound name, or + // Nothing() if there are no unbound names. + [[nodiscard]] bool hasUnboundPrivateNames( + FrontendContext* fc, + mozilla::Maybe<UnboundPrivateName>& maybeUnboundName); + + // Return a list of unbound private names, sorted by increasing location in + // the source. + [[nodiscard]] bool getUnboundPrivateNames( + Vector<UnboundPrivateName, 8>& unboundPrivateNames); + + struct RewindToken { + private: + friend class UsedNameTracker; + uint32_t scriptId; + uint32_t scopeId; + }; + + RewindToken getRewindToken() const { + RewindToken token; + token.scriptId = scriptCounter_; + token.scopeId = scopeCounter_; + return token; + } + + // Resets state so that scriptId and scopeId are the innermost script and + // scope, respectively. Used for rewinding state on syntax parse failure. + void rewind(RewindToken token); + + const UsedNameMap& map() const { return map_; } + +#if defined(DEBUG) || defined(JS_JITSPEW) + void dump(ParserAtomsTable& table); +#endif +}; + +} // namespace frontend +} // namespace js + +#endif |