From 70110bc17beacf28f2d4f77c6f0d09e22a7b8f6f Mon Sep 17 00:00:00 2001
From: "kasperl@chromium.org"
 <kasperl@chromium.org@ce2b1a6d-e550-0410-aec6-3dcde31c8c00>
Date: Wed, 13 May 2009 16:27:40 +0000
Subject: [PATCH] Avoid linear search for non-locals in the scope code when
 resolving variables inside with and eval scopes. Review URL:
 http://codereview.chromium.org/114024

git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@1937 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
---
 src/scopes.cc | 67 +++++++++++++++++++++++++++++++++--------------------------
 src/scopes.h  |  4 +++-
 2 files changed, 40 insertions(+), 31 deletions(-)

diff --git a/src/scopes.cc b/src/scopes.cc
index e959f02..c9dd497 100644
--- a/src/scopes.cc
+++ b/src/scopes.cc
@@ -112,7 +112,9 @@ Scope::Scope()
     locals_(false),
     temps_(0),
     params_(0),
-    nonlocals_(0),
+    dynamics_(false),
+    dynamics_local_(false),
+    dynamics_global_(false),
     unresolved_(0),
     decls_(0) {
 }
@@ -126,7 +128,6 @@ Scope::Scope(Scope* outer_scope, Type type)
     locals_(),
     temps_(4),
     params_(4),
-    nonlocals_(4),
     unresolved_(16),
     decls_(4),
     receiver_(NULL),
@@ -405,6 +406,14 @@ static void PrintVar(PrettyPrinter* printer, int indent, Variable* var) {
 }
 
 
+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
@@ -465,14 +474,12 @@ void Scope::Print(int n) {
   }
 
   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) {
@@ -490,20 +497,28 @@ void Scope::Print(int n) {
 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;
+  }
+  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);
   }
-
-  // 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);
-
   return var;
 }
 
@@ -617,14 +632,6 @@ void Scope::ResolveVariable(Scope* global_scope,
         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
diff --git a/src/scopes.h b/src/scopes.h
index e78bd2a..869bc2c 100644
--- a/src/scopes.h
+++ b/src/scopes.h
@@ -278,7 +278,9 @@ class Scope: public ZoneObject {
   // parameter list in source order
   ZoneList<Variable*> params_;
   // variables that must be looked up dynamically
-  ZoneList<Variable*> nonlocals_;
+  LocalsMap dynamics_;
+  LocalsMap dynamics_local_;
+  LocalsMap dynamics_global_;
   // unresolved variables referred to from this scope
   ZoneList<VariableProxy*> unresolved_;
   // declarations
-- 
2.7.4