tor-browser

UsedNameTracker.h (9840B)

---

/* -*- 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;
   }

   bool isClosedOver(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