Keep track of the addition order of variables explicitly.

src/ast/scopes.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/ast/scopes.h"
 
 #include <set>
 
 #include "src/accessors.h"
 #include "src/bootstrapper.h"
@@ skipping 12 matching lines @@
 //       use. Because a Variable holding a handle with the same location exists
 //       this is ensured.
 
 VariableMap::VariableMap(Zone* zone)
     : ZoneHashMap(ZoneHashMap::PointersMatch, 8, ZoneAllocationPolicy(zone)) {}
 
 Variable* VariableMap::Declare(Zone* zone, Scope* scope,
                                const AstRawString* name, VariableMode mode,
                                Variable::Kind kind,
                                InitializationFlag initialization_flag,
-                               MaybeAssignedFlag maybe_assigned_flag) {
+                               MaybeAssignedFlag maybe_assigned_flag,
+                               bool* added) {
   // AstRawStrings are unambiguous, i.e., the same string is always represented
   // by the same AstRawString*.
   // FIXME(marja): fix the type of Lookup.
   Entry* p =
       ZoneHashMap::LookupOrInsert(const_cast<AstRawString*>(name), name->hash(),
                                   ZoneAllocationPolicy(zone));
-  if (p->value == NULL) {
+  if (added) *added = p->value == nullptr;
+  if (p->value == nullptr) {
     // The variable has not been declared yet -> insert it.
     DCHECK(p->key == name);
     p->value = new (zone) Variable(scope, name, mode, kind, initialization_flag,
                                    maybe_assigned_flag);
   }
   return reinterpret_cast<Variable*>(p->value);
 }
 
 
 Variable* VariableMap::Lookup(const AstRawString* name) {
@@ skipping 21 matching lines @@
 }
 
 
 // ----------------------------------------------------------------------------
 // Implementation of Scope
 
 Scope::Scope(Zone* zone, Scope* outer_scope, ScopeType scope_type)
     : zone_(zone),
       outer_scope_(outer_scope),
       variables_(zone),
+      ordered_variables_(4, zone),
       decls_(4, zone),
       scope_type_(scope_type) {
   SetDefaults();
   if (outer_scope == nullptr) {
     // If the outer scope is null, this cannot be a with scope. The outermost
     // scope must be a script scope.
     DCHECK_EQ(SCRIPT_SCOPE, scope_type);
   } else {
     set_language_mode(outer_scope->language_mode());
     force_context_allocation_ =
@@ skipping 26 matching lines @@
   module_descriptor_ = new (zone) ModuleDescriptor(zone);
   set_language_mode(STRICT);
   DeclareThis(ast_value_factory);
 }
 
 Scope::Scope(Zone* zone, Scope* inner_scope, ScopeType scope_type,
              Handle<ScopeInfo> scope_info)
     : zone_(zone),
       outer_scope_(nullptr),
       variables_(zone),
+      ordered_variables_(0, zone),
       decls_(0, zone),
       scope_info_(scope_info),
       scope_type_(scope_type) {
   SetDefaults();
 #ifdef DEBUG
   already_resolved_ = true;
 #endif
   if (scope_type == WITH_SCOPE) {
     DCHECK(scope_info.is_null());
   } else {
@@ skipping 15 matching lines @@
       params_(0, zone),
       sloppy_block_function_map_(zone) {
   SetDefaults();
 }
 
 Scope::Scope(Zone* zone, Scope* inner_scope,
              const AstRawString* catch_variable_name)
     : zone_(zone),
       outer_scope_(nullptr),
       variables_(zone),
+      ordered_variables_(0, zone),
       decls_(0, zone),
       scope_type_(CATCH_SCOPE) {
   SetDefaults();
 #ifdef DEBUG
   already_resolved_ = true;
 #endif
   if (inner_scope != nullptr) AddInnerScope(inner_scope);
   Variable* variable =
       variables_.Declare(zone, this, catch_variable_name, VAR, Variable::NORMAL,
                          kCreatedInitialized);
@@ skipping 246 matching lines @@
   scope->CheckZones();
 #endif
 }
 
 void DeclarationScope::DeclareThis(AstValueFactory* ast_value_factory) {
   DCHECK(!already_resolved_);
   DCHECK(is_declaration_scope());
   DCHECK(has_this_declaration());
 
   bool subclass_constructor = IsSubclassConstructor(function_kind_);
-  Variable* var = variables_.Declare(
+  Variable* var = Declare(
       zone(), this, ast_value_factory->this_string(),
       subclass_constructor ? CONST : VAR, Variable::THIS,
       subclass_constructor ? kNeedsInitialization : kCreatedInitialized);
   receiver_ = var;
 }
 
 void DeclarationScope::DeclareDefaultFunctionVariables(
     AstValueFactory* ast_value_factory) {
   DCHECK(is_function_scope());
   DCHECK(!is_arrow_scope());
   // Declare 'arguments' variable which exists in all non arrow functions.
   // Note that it might never be accessed, in which case it won't be
   // allocated during variable allocation.
-  arguments_ =
-      variables_.Declare(zone(), this, ast_value_factory->arguments_string(),
-                         VAR, Variable::ARGUMENTS, kCreatedInitialized);
+  arguments_ = Declare(zone(), this, ast_value_factory->arguments_string(), VAR,
+                       Variable::ARGUMENTS, kCreatedInitialized);
 
-  new_target_ =
-      variables_.Declare(zone(), this, ast_value_factory->new_target_string(),
-                         CONST, Variable::NORMAL, kCreatedInitialized);
+  new_target_ = Declare(zone(), this, ast_value_factory->new_target_string(),
+                        CONST, Variable::NORMAL, kCreatedInitialized);
 
   if (IsConciseMethod(function_kind_) || IsClassConstructor(function_kind_) ||
       IsAccessorFunction(function_kind_)) {
-    this_function_ = variables_.Declare(
-        zone(), this, ast_value_factory->this_function_string(), CONST,
-        Variable::NORMAL, kCreatedInitialized);
+    this_function_ =
+        Declare(zone(), this, ast_value_factory->this_function_string(), CONST,
+                Variable::NORMAL, kCreatedInitialized);
   }
 }
 
 Variable* DeclarationScope::DeclareFunctionVar(const AstRawString* name) {
   DCHECK(is_function_scope());
   DCHECK_NULL(function_);
   VariableMode mode = is_strict(language_mode()) ? CONST : CONST_LEGACY;
   function_ = new (zone())
       Variable(this, name, mode, Variable::NORMAL, kCreatedInitialized);
   return function_;
@@ skipping 197 matching lines @@
 Variable* DeclarationScope::DeclareParameter(
     const AstRawString* name, VariableMode mode, bool is_optional, bool is_rest,
     bool* is_duplicate, AstValueFactory* ast_value_factory) {
   DCHECK(!already_resolved_);
   DCHECK(is_function_scope());
   DCHECK(!is_optional || !is_rest);
   Variable* var;
   if (mode == TEMPORARY) {
     var = NewTemporary(name);
   } else {
-    var = variables_.Declare(zone(), this, name, mode, Variable::NORMAL,
-                             kCreatedInitialized);
+    var = Declare(zone(), this, name, mode, Variable::NORMAL,
+                  kCreatedInitialized);
     // TODO(wingo): Avoid O(n^2) check.
     *is_duplicate = IsDeclaredParameter(name);
   }
   if (!is_optional && !is_rest && arity_ == params_.length()) {
     ++arity_;
   }
   if (is_rest) {
     DCHECK_NULL(rest_parameter_);
     rest_parameter_ = var;
     rest_index_ = num_parameters();
   }
   params_.Add(var, zone());
   if (name == ast_value_factory->arguments_string()) {
     has_arguments_parameter_ = true;
   }
   return var;
 }
 
 Variable* Scope::DeclareLocal(const AstRawString* name, VariableMode mode,
                               InitializationFlag init_flag, Variable::Kind kind,
                               MaybeAssignedFlag maybe_assigned_flag) {
   DCHECK(!already_resolved_);
   // This function handles VAR, LET, and CONST modes.  DYNAMIC variables are
   // introduced during variable allocation, and TEMPORARY variables are
   // allocated via NewTemporary().
   DCHECK(IsDeclaredVariableMode(mode));
-  return variables_.Declare(zone(), this, name, mode, kind, init_flag,
-                            maybe_assigned_flag);
+  return Declare(zone(), this, name, mode, kind, init_flag,
+                 maybe_assigned_flag);
 }
 
 Variable* DeclarationScope::DeclareDynamicGlobal(const AstRawString* name,
                                                  Variable::Kind kind) {
   DCHECK(is_script_scope());
-  return variables_.Declare(zone(), this, name, DYNAMIC_GLOBAL, kind,
-                            kCreatedInitialized);
+  return Declare(zone(), this, name, DYNAMIC_GLOBAL, kind, kCreatedInitialized);
 }
 
 
 bool Scope::RemoveUnresolved(VariableProxy* var) {
   if (unresolved_ == var) {
     unresolved_ = var->next_unresolved();
     var->set_next_unresolved(nullptr);
     return true;
   }
   VariableProxy* current = unresolved_;
@@ skipping 69 matching lines @@
         if (decls_[j]->proxy()->raw_name() == name) {
           return decls_[j];
         }
       }
       DCHECK(false);
     }
   }
   return nullptr;
 }
 
-class VarAndOrder {
- public:
-  VarAndOrder(Variable* var, int order) : var_(var), order_(order) { }
-  Variable* var() const { return var_; }
-  int order() const { return order_; }
-  static int Compare(const VarAndOrder* a, const VarAndOrder* b) {
-    return a->order_ - b->order_;
-  }
-
- private:
-  Variable* var_;
-  int order_;
-};
-
 void Scope::CollectStackAndContextLocals(ZoneList<Variable*>* stack_locals,
                                          ZoneList<Variable*>* context_locals,
                                          ZoneList<Variable*>* context_globals) {
   DCHECK(stack_locals != NULL);
   DCHECK(context_locals != NULL);
   DCHECK(context_globals != NULL);
 
   // Collect temporaries which are always allocated on the stack, unless the
   // context as a whole has forced context allocation.
   if (is_declaration_scope()) {
     ZoneList<Variable*>* temps = AsDeclarationScope()->temps();
     for (int i = 0; i < temps->length(); i++) {
       Variable* var = (*temps)[i];
       if (var->is_used()) {
         if (var->IsContextSlot()) {
           DCHECK(has_forced_context_allocation());
           context_locals->Add(var, zone());
         } else if (var->IsStackLocal()) {
           stack_locals->Add(var, zone());
         } else {
           DCHECK(var->IsParameter());
         }
       }
     }
   }
 
-  // Collect declared local variables.
-  ZoneList<VarAndOrder> vars(variables_.occupancy(), zone());
-  for (VariableMap::Entry* p = variables_.Start();
-       p != NULL;
-       p = variables_.Next(p)) {
-    Variable* var = reinterpret_cast<Variable*>(p->value);
-    if (var->is_used()) {
-      vars.Add(VarAndOrder(var, p->order), zone());
-    }
-  }
-  vars.Sort(VarAndOrder::Compare);
-  int var_count = vars.length();
-  for (int i = 0; i < var_count; i++) {
-    Variable* var = vars[i].var();
+  for (int i = 0; i < ordered_variables_.length(); i++) {
+    Variable* var = ordered_variables_[i];
     if (var->IsStackLocal()) {
       stack_locals->Add(var, zone());
     } else if (var->IsContextSlot()) {
       context_locals->Add(var, zone());
     } else if (var->IsGlobalSlot()) {
       context_globals->Add(var, zone());
     }
   }
 }
 
@@ skipping 764 matching lines @@
 
 void Scope::AllocateNonParameterLocalsAndDeclaredGlobals() {
   // All variables that have no rewrite yet are non-parameter locals.
   if (is_declaration_scope()) {
     ZoneList<Variable*>* temps = AsDeclarationScope()->temps();
     for (int i = 0; i < temps->length(); i++) {
       AllocateNonParameterLocal((*temps)[i]);
     }
   }
 
-  ZoneList<VarAndOrder> vars(variables_.occupancy(), zone());
-  for (VariableMap::Entry* p = variables_.Start();
-       p != NULL;
-       p = variables_.Next(p)) {
-    Variable* var = reinterpret_cast<Variable*>(p->value);
-    vars.Add(VarAndOrder(var, p->order), zone());
-  }
-  vars.Sort(VarAndOrder::Compare);
-  int var_count = vars.length();
-  for (int i = 0; i < var_count; i++) {
-    AllocateNonParameterLocal(vars[i].var());
+  for (int i = 0; i < ordered_variables_.length(); i++) {
+    AllocateNonParameterLocal(ordered_variables_[i]);
   }
 
   if (FLAG_global_var_shortcuts) {
-    for (int i = 0; i < var_count; i++) {
-      AllocateDeclaredGlobal(vars[i].var());
+    for (int i = 0; i < ordered_variables_.length(); i++) {
+      AllocateDeclaredGlobal(ordered_variables_[i]);
     }
   }
 
   if (is_declaration_scope()) {
     AsDeclarationScope()->AllocateLocals();
   }
 }
 
 void DeclarationScope::AllocateLocals() {
   // For now, function_ must be allocated at the very end.  If it gets
@@ skipping 90 matching lines @@
       function != nullptr && function->IsContextSlot();
   return num_heap_slots() - Context::MIN_CONTEXT_SLOTS - num_global_slots() -
          (is_function_var_in_context ? 1 : 0);
 }
 
 
 int Scope::ContextGlobalCount() const { return num_global_slots(); }
 
 }  // namespace internal
 }  // namespace v8