Avoid linear search for non-locals in the scope code...

src/scopes.cc

 // Copyright 2006-2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 94 matching lines @@
 // ----------------------------------------------------------------------------
 // Implementation of Scope
 
 
 // Dummy constructor
 Scope::Scope()
   : inner_scopes_(0),
     locals_(false),
     temps_(0),
     params_(0),
-    nonlocals_(0),
+    dynamics_(false),
+    dynamics_local_(false),
+    dynamics_global_(false),
     unresolved_(0),
     decls_(0) {
 }
 
 
 Scope::Scope(Scope* outer_scope, Type type)
   : outer_scope_(outer_scope),
     inner_scopes_(4),
     type_(type),
     scope_name_(Factory::empty_symbol()),
     locals_(),
     temps_(4),
     params_(4),
-    nonlocals_(4),
     unresolved_(16),
     decls_(4),
     receiver_(NULL),
     function_(NULL),
     arguments_(NULL),
     arguments_shadow_(NULL),
     illegal_redecl_(NULL),
     scope_inside_with_(false),
     scope_contains_with_(false),
     scope_calls_eval_(false),
@@ skipping 258 matching lines @@
     if (var->is_accessed_from_inner_scope()) PrintF("inner scope access, ");
     PrintF("var ");
     var->var_uses()->Print();
     PrintF(", obj ");
     var->obj_uses()->Print();
     PrintF("\n");
   }
 }
 
 
+static void PrintMap(PrettyPrinter* printer, int indent, LocalsMap* map) {
+  for (LocalsMap::Entry* p = map->Start(); p != NULL; p = map->Next(p)) {
+    Variable* var = reinterpret_cast<Variable*>(p->value);
+    PrintVar(printer, indent, var);
+  }
+}
+
+
 void Scope::Print(int n) {
   int n0 = (n > 0 ? n : 0);
   int n1 = n0 + 2;  // indentation
 
   // Print header.
   Indent(n0, Header(type_));
   if (scope_name_->length() > 0) {
     PrintF(" ");
     PrintName(scope_name_);
   }
@@ skipping 40 matching lines @@
   if (function_ != NULL) {
     PrintVar(&printer, n1, function_);
   }
 
   Indent(n1, "// temporary vars\n");
   for (int i = 0; i < temps_.length(); i++) {
     PrintVar(&printer, n1, temps_[i]);
   }
 
   Indent(n1, "// local vars\n");
-  for (LocalsMap::Entry* p = locals_.Start(); p != NULL; p = locals_.Next(p)) {
-    Variable* var = reinterpret_cast<Variable*>(p->value);
-    PrintVar(&printer, n1, var);
-  }
+  PrintMap(&printer, n1, &locals_);
 
-  Indent(n1, "// nonlocal vars\n");
-  for (int i = 0; i < nonlocals_.length(); i++)
-    PrintVar(&printer, n1, nonlocals_[i]);
+  Indent(n1, "// dynamic vars\n");
+  PrintMap(&printer, n1, &dynamics_);
+  PrintMap(&printer, n1, &dynamics_local_);
+  PrintMap(&printer, n1, &dynamics_global_);
 
   // Print inner scopes (disable by providing negative n).
   if (n >= 0) {
     for (int i = 0; i < inner_scopes_.length(); i++) {
       PrintF("\n");
       inner_scopes_[i]->Print(n1);
     }
   }
 
   Indent(n0, "}\n");
 }
 #endif  // DEBUG
 
 
 Variable* Scope::NonLocal(Handle<String> name, Variable::Mode mode) {
   // Space optimization: reuse existing non-local with the same name
   // and mode.
-  for (int i = 0; i < nonlocals_.length(); i++) {
-    Variable* var = nonlocals_[i];
-    if (var->name().is_identical_to(name) && var->mode() == mode) {
-      return var;
-    }
+  LocalsMap* map = NULL;
+  switch (mode) {
+    case Variable::DYNAMIC:
+      map = &dynamics_;
+      break;
+    case Variable::DYNAMIC_LOCAL:
+      map = &dynamics_local_;
+      break;
+    case Variable::DYNAMIC_GLOBAL:
+      map = &dynamics_global_;
+      break;
+    default:
+      UNREACHABLE();
+      break;
   }
-
-  // Otherwise create a new non-local and add it to the list.
-  Variable* var = new Variable(NULL, name, mode, true, false);
-  nonlocals_.Add(var);
-
-  // Allocate it by giving it a dynamic lookup.
-  var->rewrite_ = new Slot(var, Slot::LOOKUP, -1);
-
+  Variable* var = map->Lookup(name);
+  if (var == NULL) {
+    // Declare a new non-local.
+    var = map->Declare(NULL, name, mode, true, false);
+    // Allocate it by giving it a dynamic lookup.
+    var->rewrite_ = new Slot(var, Slot::LOOKUP, -1);
+  }
   return var;
 }
 
 
 // Lookup a variable starting with this scope. The result is either
 // the statically resolved (local!) variable belonging to an outer scope,
 // or NULL. It may be NULL because a) we couldn't find a variable, or b)
 // because the variable is just a guess (and may be shadowed by another
 // variable that is introduced dynamically via an 'eval' call or a 'with'
 // statement).
@@ skipping 93 matching lines @@
       // a local or outer eval() call, or an outer 'with' statement),
       // or we don't know about the outer scope (because we are
       // in an eval scope).
       if (is_global_scope() ||
           !(scope_inside_with_ || outer_scope_is_eval_scope_ ||
             scope_calls_eval_ || outer_scope_calls_eval_)) {
         // We must have a global variable.
         ASSERT(global_scope != NULL);
         var = new Variable(global_scope, proxy->name(),
                            Variable::DYNAMIC, true, false);
-        // Ideally we simply rewrite these variables into property
-        // accesses. Unfortunately, we cannot do this here at the
-        // moment because then we can't differentiate between
-        // global variable ('x') and global property ('this.x') access.
-        // If 'x' doesn't exist, the former leads to an error, while the
-        // latter returns undefined. Sigh...
-        // var->rewrite_ = new Property(new Literal(env_->global()),
-        //                              new Literal(proxy->name()));
 
       } else if (scope_inside_with_) {
         // If we are inside a with statement we give up and look up
         // the variable at runtime.
         var = NonLocal(proxy->name(), Variable::DYNAMIC);
 
       } else if (invalidated_local != NULL) {
         // No with statements are involved and we found a local
         // variable that might be shadowed by eval introduced
         // variables.
@@ skipping 299 matching lines @@
   if (num_heap_slots_ == Context::MIN_CONTEXT_SLOTS &&
       !must_have_local_context) {
     num_heap_slots_ = 0;
   }
 
   // Allocation done.
   ASSERT(num_heap_slots_ == 0 || num_heap_slots_ >= Context::MIN_CONTEXT_SLOTS);
 }
 
 } }  // namespace v8::internal