1 files changed, 244 insertions, 0 deletions
diff --git a/js/src/frontend/UsedNameTracker.h b/js/src/frontend/UsedNameTracker.h
new file mode 100644
index 0000000000..0b7417b540
--- /dev/null
+++ b/js/src/frontend/UsedNameTracker.h
@@ -0,0 +1,244 @@
+/* -*- 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/Attributes.h"
+
+#include "frontend/Token.h"
+#include "js/AllocPolicy.h"
+#include "js/HashTable.h"
+#include "js/Vector.h"
+
+#include "vm/StringType.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 {
+  const ParserAtom* atom;
+  TokenPos position;
+
+  UnboundPrivateName(const ParserAtom* 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(JSContext* cx, NameVisibility visibility,
+                          mozilla::Maybe<TokenPos> position)
+        : uses_(cx), 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() { return uses_.empty(); }
+
+    mozilla::Maybe<TokenPos> pos() { return firstUsePos_; }
+  };
+
+  using UsedNameMap = HashMap<const ParserAtom*, UsedNameInfo,
+                              DefaultHasher<const ParserAtom*>>;
+
+ 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(JSContext* cx)
+      : map_(cx),
+        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(const ParserAtom* name) const {
+    return map_.lookup(name);
+  }
+
+  MOZ_MUST_USE bool noteUse(
+      JSContext* cx, const ParserAtom* 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.
+  MOZ_MUST_USE bool hasUnboundPrivateNames(
+      JSContext* cx, mozilla::Maybe<UnboundPrivateName>& maybeUnboundName);
+
+  // Return a list of unbound private names, sorted by increasing location in
+  // the source.
+  MOZ_MUST_USE 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);
+};
+
+}  // namespace frontend
+}  // namespace js
+
+#endif