Introduce with scope and rework variable resolution.

src/scopes.cc

 // Copyright 2011 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 206 matching lines @@
 Scope* Scope::DeserializeScopeChain(CompilationInfo* info,
                                     Scope* global_scope) {
   // Reconstruct the outer scope chain from a closure's context chain.
   ASSERT(!info->closure().is_null());
   Context* context = info->closure()->context();
   Scope* current_scope = NULL;
   Scope* innermost_scope = NULL;
   bool contains_with = false;
   while (!context->IsGlobalContext()) {
     if (context->IsWithContext()) {
+      Scope* with_scope = new Scope(WITH_SCOPE);

[Kevin Millikin (Chromium), 2011/09/15 09:38:13]

Make the constructor take the current scope and call AddInnerScope.  It's
strange to have one variant that requires it to be configured manually.  Then
you don't need the local with_scope.

[Steven, 2011/09/15 19:54:06]

There's already such a constructor that is used during parsing to construct the
scope tree and it takes the outer scope rather than an inner scope. I will reuse
the constructor for function and block scopes instead.
On 2011/09/15 09:38:13, Kevin Millikin wrote:

+      with_scope->AddInnerScope(current_scope);
+      current_scope = with_scope;
       // All the inner scopes are inside a with.
       contains_with = true;
       for (Scope* s = innermost_scope; s != NULL; s = s->outer_scope()) {
         s->scope_inside_with_ = true;
       }
+    } else if (context->IsFunctionContext()) {
+      SerializedScopeInfo* scope_info =
+          context->closure()->shared()->scope_info();
+      current_scope = new Scope(current_scope, FUNCTION_SCOPE,
+                                Handle<SerializedScopeInfo>(scope_info));
+    } else if (context->IsBlockContext()) {
+      SerializedScopeInfo* scope_info =
+          SerializedScopeInfo::cast(context->extension());
+      current_scope = new Scope(current_scope, BLOCK_SCOPE,
+                                Handle<SerializedScopeInfo>(scope_info));
     } else {
-      if (context->IsFunctionContext()) {
-        SerializedScopeInfo* scope_info =
-            context->closure()->shared()->scope_info();
-        current_scope = new Scope(current_scope, FUNCTION_SCOPE,
-            Handle<SerializedScopeInfo>(scope_info));
-      } else if (context->IsBlockContext()) {
-        SerializedScopeInfo* scope_info =
-            SerializedScopeInfo::cast(context->extension());
-        current_scope = new Scope(current_scope, BLOCK_SCOPE,
-            Handle<SerializedScopeInfo>(scope_info));
-      } else {
-        ASSERT(context->IsCatchContext());
-        String* name = String::cast(context->extension());
-        current_scope = new Scope(current_scope, Handle<String>(name));
-      }
-      if (contains_with) current_scope->RecordWithStatement();
-      if (innermost_scope == NULL) innermost_scope = current_scope;
+      ASSERT(context->IsCatchContext());
+      String* name = String::cast(context->extension());
+      current_scope = new Scope(current_scope, Handle<String>(name));
     }
+    if (contains_with) current_scope->RecordWithStatement();
+    if (innermost_scope == NULL) innermost_scope = current_scope;
 
     // Forget about a with when we move to a context for a different function.
     if (context->previous()->closure() != context->closure()) {
       contains_with = false;
     }
     context = context->previous();
   }
 
   global_scope->AddInnerScope(current_scope);
   return (innermost_scope == NULL) ? global_scope : innermost_scope;
@@ skipping 32 matching lines @@
   }
 
   // Declare convenience variables.
   // Declare and allocate receiver (even for the global scope, and even
   // if naccesses_ == 0).
   // NOTE: When loading parameters in the global scope, we must take
   // care not to access them as properties of the global object, but
   // instead load them directly from the stack. Currently, the only
   // such parameter is 'this' which is passed on the stack when
   // invoking scripts
-  if (is_catch_scope() || is_block_scope()) {
+  if (is_catch_scope() || is_block_scope() || is_with_scope()) {

[Kevin Millikin (Chromium), 2011/09/15 09:38:13]

Flip the condition and use:

if (is_declaration_scope()) { ... } else { ... }

[Steven, 2011/09/15 19:54:06]

Done.

     ASSERT(outer_scope() != NULL);
     receiver_ = outer_scope()->receiver();
   } else {
     ASSERT(is_function_scope() ||
            is_global_scope() ||
            is_eval_scope());
     Variable* var =
         variables_.Declare(this,
                            isolate_->factory()->this_symbol(),
                            Variable::VAR,
@@ skipping 187 matching lines @@
 }
 
 
 Declaration* Scope::CheckConflictingVarDeclarations() {
   int length = decls_.length();
   for (int i = 0; i < length; i++) {
     Declaration* decl = decls_[i];
     if (decl->mode() != Variable::VAR) continue;
     Handle<String> name = decl->proxy()->name();
     bool cond = true;
     for (Scope* scope = decl->scope(); cond ; scope = scope->outer_scope_) {

[Kevin Millikin (Chromium), 2011/09/15 09:38:13]

I found the logic of this loop too complicated.  You could try something like:

Scope* previous = NULL;
Scope* current = decl->scope();
do {
  ... current ...
  previous = current;
  current = current->outer_scope_;
} while (!previous->is_declaration_scope());

[Steven, 2011/09/15 19:54:06]

Done.

       // There is a conflict if there exists a non-VAR binding.
       Variable* other_var = scope->variables_.Lookup(name);
       if (other_var != NULL && other_var->mode() != Variable::VAR) {
         return decl;
       }
 
       // Include declaration scope in the iteration but stop after.
-      if (!scope->is_block_scope() && !scope->is_catch_scope()) cond = false;
+      if (scope->is_declaration_scope()) cond = false;
     }
   }
   return NULL;
 }
 
 
 template<class Allocator>
 void Scope::CollectUsedVariables(List<Variable*, Allocator>* locals) {
   // Collect variables in this scope.
   // Note that the function_ variable - if present - is not
@@ skipping 90 matching lines @@
   for (Scope* s = this; s != scope; s = s->outer_scope_) {
     ASSERT(s != NULL);  // scope must be in the scope chain
     if (s->num_heap_slots() > 0) n++;
   }
   return n;
 }
 
 
 Scope* Scope::DeclarationScope() {
   Scope* scope = this;
-  while (scope->is_catch_scope() ||
-         scope->is_block_scope()) {
+  while (!scope->is_declaration_scope()) {
     scope = scope->outer_scope();
   }
   return scope;
 }
 
 
 Handle<SerializedScopeInfo> Scope::GetSerializedScopeInfo() {
   if (scope_info_.is_null()) {
     scope_info_ = SerializedScopeInfo::Create(this);
   }
   return scope_info_;
 }
 
 
 #ifdef DEBUG
 static const char* Header(Scope::Type type) {
   switch (type) {
     case Scope::EVAL_SCOPE: return "eval";
     case Scope::FUNCTION_SCOPE: return "function";
     case Scope::GLOBAL_SCOPE: return "global";
     case Scope::CATCH_SCOPE: return "catch";
     case Scope::BLOCK_SCOPE: return "block";
+    case Scope::WITH_SCOPE: return "with";
   }
   UNREACHABLE();
   return NULL;
 }
 
 
 static void Indent(int n, const char* str) {
   PrintF("%*s%s", n, "", str);
 }
 
@@ skipping 140 matching lines @@
   if (var == NULL) {
     // Declare a new non-local.
     var = map->Declare(NULL, name, mode, true, Variable::NORMAL);
     // Allocate it by giving it a dynamic lookup.
     var->AllocateTo(Variable::LOOKUP, -1);
   }
   return var;
 }
 
 
-// Lookup a variable starting with this scope. The result is either
-// the statically resolved 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).
-Variable* Scope::LookupRecursive(Handle<String> name,
-                                 bool from_inner_scope,
-                                 Variable** invalidated_local) {
-  // If we find a variable, but the current scope calls 'eval', the found
-  // variable may not be the correct one (the 'eval' may introduce a
-  // property with the same name). In that case, remember that the variable
-  // found is just a guess.
-  bool guess = scope_calls_eval_;
+Scope::LookupResult Scope::LookupRecursive(Handle<String> name,
+                                           bool from_inner_scope,
+                                           Variable** var) {
+  // Try to find the variable in this scope.
+  *var = LocalLookup(name);
 
-  // Try to find the variable in this scope.
-  Variable* var = LocalLookup(name);
+  if (*var != NULL) {
+    // We found a variable and we are done. (Even if there is an 'eval' in this
+    // scope which introduces the same variable again, the resulting variable
+    // remains the same.)
 
-  if (var != NULL) {
-    // We found a variable. If this is not an inner lookup, we are done.
-    // (Even if there is an 'eval' in this scope which introduces the
-    // same variable again, the resulting variable remains the same.
-    // Note that enclosing 'with' statements are handled at the call site.)
-    if (!from_inner_scope)
-      return var;
-
-  } else {
-    // We did not find a variable locally. Check against the function variable,
-    // if any. We can do this for all scopes, since the function variable is
-    // only present - if at all - for function scopes.
-    //
-    // This lookup corresponds to a lookup in the "intermediate" scope sitting
-    // between this scope and the outer scope. (ECMA-262, 3rd., requires that
-    // the name of named function literal is kept in an intermediate scope
-    // in between this scope and the next outer scope.)
-    if (function_ != NULL && function_->name().is_identical_to(name)) {
-      var = function_->var();
-
-    } else if (outer_scope_ != NULL) {
-      var = outer_scope_->LookupRecursive(name, true, invalidated_local);
-      // We may have found a variable in an outer scope. However, if
-      // the current scope is inside a 'with', the actual variable may
-      // be a property introduced via the 'with' statement. Then, the
-      // variable we may have found is just a guess.
-      if (scope_inside_with_)
-        guess = true;
+    // If this is a lookup from an inner scope, mark the variable.
+    if (from_inner_scope) {
+      (*var)->MarkAsAccessedFromInnerScope();

[Kevin Millikin (Chromium), 2011/09/16 05:23:21]

This is annoying to check here.  Isn't it possible to just have the caller mark
the result of the recursive call to LookupRecursive (and to not mark the result
of the initial call to LookupRecursive) and then skip passing the "I am a
recursive call" flag and having the callee do the marking?

[Steven, 2011/09/16 10:48:14]

Sure, done.
On 2011/09/16 05:23:21, Kevin Millikin wrote:

     }
 
-    // If we did not find a variable, we are done.
-    if (var == NULL)
-      return NULL;
+    if (is_global_scope()) return GLOBAL;

[Kevin Millikin (Chromium), 2011/09/15 09:38:13]

return is_global_scope() ? GLOBAL : FOUND;

Though I actually think this should always be FOUND.

[Steven, 2011/09/15 19:54:06]

We need to distinguish locally bound variables from global variables. If we use
FOUND here for variables found in the global scope I would have to include
multiple checks elsewhere.
On 2011/09/15 09:38:13, Kevin Millikin wrote:

[Kevin Millikin (Chromium), 2011/09/16 05:23:21]

That's what I'm asking about.

The old code will return a variable if there is a global var/function/const
binding.  Then the code in ResolveVariable will just bind to it.

You've changed it to return GLOBAL and set *var in that case, but then you check
the LookupResult flag first and ignore *var in the GLOBAL case.  So the new code
does something different in that case.

Is that necessary?  Harmless?

[Steven, 2011/09/16 10:48:14]

Yes, I'm sorry you're right. The old code only threw away the found binding if
shadowing might occur, but I threw it always away. But the second patchset
already does it correctly.
On 2011/09/16 05:23:21, Kevin Millikin wrote:

+    return FOUND;
   }
 
-  ASSERT(var != NULL);
-
-  // If this is a lookup from an inner scope, mark the variable.
-  if (from_inner_scope) {
-    var->MarkAsAccessedFromInnerScope();
+  // We did not find a variable locally. Check against the function variable,
+  // if any. We can do this for all scopes, since the function variable is
+  // only present - if at all - for function scopes.
+  //
+  // This lookup corresponds to a lookup in the "intermediate" scope sitting
+  // between this scope and the outer scope. (ECMA-262, 3rd., requires that
+  // the name of named function literal is kept in an intermediate scope
+  // in between this scope and the next outer scope.)
+  LookupResult result = GLOBAL;
+  if (function_ != NULL && function_->name().is_identical_to(name)) {
+    *var = function_->var();
+    if (from_inner_scope) {
+      (*var)->MarkAsAccessedFromInnerScope();
+    }
+    result = FOUND;
+  } else if (outer_scope_ != NULL) {
+    result = outer_scope_->LookupRecursive(name, true, var);
   }
 
-  // If the variable we have found is just a guess, invalidate the
-  // result. If the found variable is local, record that fact so we
-  // can generate fast code to get it if it is not shadowed by eval.
-  if (guess) {
-    if (!var->is_global()) *invalidated_local = var;
-    var = NULL;
-  }
+  // We may have found a variable in an outer scope. However, if the current
+  // scope is a 'with' scope, the actual variable may be a property introduced
+  // via the 'with' statement. Then, the variable we may have found is just a
+  // guess.
+  // Note that we must do a lookup in the outer scope anyway, because if we find
+  // one, we must mark that variable as potentially accessed from inside of an
+  // inner with scope (the property may not be in the 'with' object).
+  if (is_with_scope()) return FOUND_WITH;
 
-  return var;
+  // If we have found a variable in an outer scope, but the current scope calls
+  // 'eval', the found variable may not be the correct one (the 'eval' may
+  // introduce a property with the same name). In that case, remember that the
+  // variable found is just a guess.
+  if (result == FOUND && scope_calls_eval_) return FOUND_EVAL;
+
+  return result;
 }
 
 
 void Scope::ResolveVariable(Scope* global_scope,
                             Handle<Context> context,
                             VariableProxy* proxy) {
   ASSERT(global_scope == NULL || global_scope->is_global_scope());
 
   // If the proxy is already resolved there's nothing to do
   // (functions and consts may be resolved by the parser).
   if (proxy->var() != NULL) return;
 
   // Otherwise, try to resolve the variable.
-  Variable* invalidated_local = NULL;
-  Variable* var = LookupRecursive(proxy->name(), false, &invalidated_local);
+  Variable* var = NULL;
+  LookupResult result = LookupRecursive(proxy->name(), false, &var);
 
-  if (proxy->inside_with()) {
-    // If we are inside a local 'with' statement, all bets are off
-    // and we cannot resolve the proxy to a local variable even if
-    // we found an outer matching variable.
-    // Note that we must do a lookup anyway, because if we find one,
-    // we must mark that variable as potentially accessed from this
-    // inner scope (the property may not be in the 'with' object).
-    var = NonLocal(proxy->name(), Variable::DYNAMIC);
+  switch (result) {
+    case FOUND:
+      break;
 
-  } else {
-    // We are not inside a local 'with' statement.
+    case FOUND_WITH:
+      // If we are inside a local 'with' statement, all bets are off

[Kevin Millikin (Chromium), 2011/09/15 09:38:13]

I lot of these comments are confusing and should be rewritten as you clean
things up.  This one mentions a local 'with' statement.  I'm not sure what that
means, but I would just say something like "If we passed a with statement on our
way to the binding scope....".

[Steven, 2011/09/15 19:54:06]

I cleaned them up. PTAL.
On 2011/09/15 09:38:13, Kevin Millikin wrote:

+      // and we cannot resolve the proxy to a local variable even if
+      // we found an outer matching variable.
+      var = NonLocal(proxy->name(), Variable::DYNAMIC);
+      break;
 
-    if (var == NULL) {
+    case FOUND_EVAL: {
+      // No with statements are involved and we found a local variable
+      // that might be shadowed by eval introduced variables.
+      Variable* invalidated_local = var;
+      var = NonLocal(proxy->name(), Variable::DYNAMIC_LOCAL);
+      var->set_local_if_not_shadowed(invalidated_local);
+      break;
+    }
+
+    case GLOBAL:
       // We did not find the variable. We have a global variable

[Kevin Millikin (Chromium), 2011/09/15 09:38:13]

Or we did find it, and it was in the global scope.  It's also a bit confusing
(warty) that we don't care about eval in the global scope because we'll just do
a global object property lookup in any case.

[Steven, 2011/09/15 19:54:06]

Eval in the global scope can't introduce shadowed bindings, so in that case the
variable shouldn't be marked as being potentially shadowed. If a global variable
is not shadowed it will get the location Variable::UNALLOCATED which should
result in a fast object property lookup. Otherwise it will be Variable::LOOKUP
which will result in EmitLoadGlobalCheckExtensions emitting code to traverse the
context chain to check if any extension objects are present.
On 2011/09/15 09:38:13, Kevin Millikin wrote:

[Kevin Millikin (Chromium), 2011/09/16 05:23:21]

Yes, I know.  Perhaps the names are a just bit off.  It's also a bit
confusing/error prone to sometimes return a vlaue in the out output parameter
var and not use it.

I suggest that the true alternatives from LookupRecursive are:

BOUND(var): There is a definitely not-shadowed binding (it may be global, but
that doesn't matter, I thiink)

EVAL_SHADOWED(var): There is a binding for the var but there is some scope
between the variable reference scope (inclusive) and binding scope (exclusive)
that calls eval (and there is no with between the reference and binding).

EVAL_SHADOWED(NULL): There is no binding and there is a scope that calls eval
between the var reference (inclusive) and the global scope (exclusive).

INSIDE_WITH(NULL): There is a with scope in the chain and no binding for the var
before that.

UNBOUND(NULL): There is no binding, no scope calls eval, we're not inside a
with.  In that case, we introduce an implicit global declaration for the
variable.

Does that sound about right?

[Steven, 2011/09/16 10:48:14]

For BOUND it does indeed not matter much if the variable is global or not, just
if a scope that calls eval is found we need to distinguish them, i.e. we need to
discriminate possibly shadowed globally bound variables from possibly shadowed
locally bound variables. But ok, this can be done via var->is_global() instead
of distinguishing between non-shadowed global/local bindings from the beginning.
On 2011/09/16 05:23:21, Kevin Millikin wrote:

       // if we are in the global scope (we know already that we
       // are outside a 'with' statement) or if there is no way
       // that the variable might be introduced dynamically (through
       // 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_ ||

[Kevin Millikin (Chromium), 2011/09/15 09:38:13]

Is all this junk still necessary?  If we got GLOBAL, then we are definitely not
inside with (because that would be FOUND_WITH), and we don't have this scope
(unless it's the global scope) or any outer scope that calls eval (except
possibly the global scope) because that would be FOUND_EVAL.

[Steven, 2011/09/15 19:54:06]

Not necessary anymore.
On 2011/09/15 09:38:13, Kevin Millikin wrote:

             scope_calls_eval_ || outer_scope_calls_eval_)) {
         // We must have a global variable.
         ASSERT(global_scope != NULL);
         var = global_scope->DeclareGlobal(proxy->name());

[Kevin Millikin (Chromium), 2011/09/15 09:38:13]

Is it right to (re)declare this variable even in the case that we found a
global-declared var/function/const already?  It doesn't seem like it matches the
old behavior.

[Steven, 2011/09/15 19:54:06]

I think it matched the old behaviour, but now I avoid redeclaration.
On 2011/09/15 09:38:13, Kevin Millikin wrote:

 
       } else if (scope_inside_with_) {
         // If we are inside a with statement we give up and look up
         // the variable at runtime.
+        ASSERT(false);

[Kevin Millikin (Chromium), 2011/09/15 09:38:13]

Just get rid of this case completely and assert !scope_inside_with_.

BTW, ASSERT(false) is spelled "UNREACHABLE()" in the V8 code.

[Steven, 2011/09/15 19:54:06]

Sorry, this is dead code I forgot to delete.
On 2011/09/15 09:38:13, Kevin Millikin wrote:

         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.
-        var = NonLocal(proxy->name(), Variable::DYNAMIC_LOCAL);
-        var->set_local_if_not_shadowed(invalidated_local);
-
       } else if (outer_scope_is_eval_scope_) {

[Kevin Millikin (Chromium), 2011/09/15 09:38:13]

It would be great if we could get rid of this flag too, and even the whole
propagate scope info pass.

[Steven, 2011/09/15 19:54:06]

Got rid of the flag, but still need the propagate pass
for outer_scope_calls_non_strict_eval which is also used
elsewhere.
On 2011/09/15 09:38:13, Kevin Millikin wrote:

         // No with statements and we did not find a local and the code
         // is executed with a call to eval.  The context contains
         // scope information that we can use to determine if the
         // variable is global if it is not shadowed by eval-introduced
         // variables.
         if (context->GlobalIfNotShadowedByEval(proxy->name())) {
           var = NonLocal(proxy->name(), Variable::DYNAMIC_GLOBAL);
-
         } else {
           var = NonLocal(proxy->name(), Variable::DYNAMIC);
         }
 
       } else {
         // No with statements and we did not find a local and the code
         // is not executed with a call to eval.  We know that this
         // variable is global unless it is shadowed by eval-introduced
         // variables.
         var = NonLocal(proxy->name(), Variable::DYNAMIC_GLOBAL);
       }
-    }
+      break;
   }
 
+  ASSERT(var != NULL);
   proxy->BindTo(var);
 }
 
 
 void Scope::ResolveVariablesRecursively(Scope* global_scope,
                                         Handle<Context> context) {
   ASSERT(global_scope == NULL || global_scope->is_global_scope());
 
   // Resolve unresolved variables for this scope.
   for (int i = 0; i < unresolved_.length(); i++) {
@@ skipping 228 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