summaryrefslogtreecommitdiffstats
path: root/js/src/frontend/UsedNameTracker.h
diff options
context:
space:
mode:
Diffstat (limited to 'js/src/frontend/UsedNameTracker.h')
-rw-r--r--js/src/frontend/UsedNameTracker.h265
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