runtime/vm/scopes.cc - sdk.git - Git at Google

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.

 #include "vm/scopes.h"

 #include "vm/ast.h"
 #include "vm/bit_vector.h"
 #include "vm/object.h"
 #include "vm/parser.h"
 #include "vm/stack_frame.h"
 #include "vm/symbols.h"

 namespace dart {

 int SourceLabel::FunctionLevel() const {
   ASSERT(owner() != NULL);
   return owner()->function_level();
 }


 LocalScope::LocalScope(LocalScope* parent, int function_level, int loop_level)
     : parent_(parent),
       child_(NULL),
       sibling_(NULL),
       function_level_(function_level),
       loop_level_(loop_level),
       context_level_(LocalScope::kUnitializedContextLevel),
       num_context_variables_(0),
       begin_token_pos_(0),
       end_token_pos_(0),
       variables_(),
       labels_() {
   // Hook this node into the children of the parent, unless the parent has a
   // different function_level, since the local scope of a nested function can
   // be discarded after it has been parsed.
   if ((parent != NULL) && (parent->function_level() == function_level)) {
     sibling_ = parent->child_;
     parent->child_ = this;
   }
 }


 bool LocalScope::IsNestedWithin(LocalScope* scope) const {
   const LocalScope* current_scope = this;
   while (current_scope != NULL) {
     if (current_scope == scope) {
       return true;
     }
     current_scope = current_scope->parent();
   }
   return false;
 }


 bool LocalScope::AddVariable(LocalVariable* variable) {
   ASSERT(variable != NULL);
   if (LocalLookupVariable(variable->name()) != NULL) {
     return false;
   }
   variables_.Add(variable);
   if (variable->owner() == NULL) {
     // Variables must be added to their owner scope first. Subsequent calls
     // to 'add' treat the variable as an alias.
     variable->set_owner(this);
   }
   return true;
 }


 bool LocalScope::AddLabel(SourceLabel* label) {
   if (LocalLookupLabel(label->name()) != NULL) {
     return false;
   }
   labels_.Add(label);
   if (label->owner() == NULL) {
     // Labels must be added to their owner scope first. Subsequent calls
     // to 'add' treat the label as an alias.
     label->set_owner(this);
   }
   return true;
 }


 void LocalScope::AllocateContextVariable(LocalVariable* variable,
                                          LocalScope** context_owner) {
   ASSERT(variable->is_captured());
   ASSERT(variable->owner()->loop_level() == loop_level());
   if (num_context_variables_ == 0) {
     // This scope will allocate and chain a new context.
     int new_context_level = ((*context_owner) == NULL) ?
         1 : (*context_owner)->context_level() + 1;
     // This scope becomes the current context owner.
     *context_owner = this;
     set_context_level(new_context_level);
   }
   // The context level in the owner scope of a captured variable indicates at
   // code generation time how far to walk up the context chain in order to
   // access the variable from the current context level.
   if (!variable->owner()->HasContextLevel()) {
     ASSERT(variable->owner() != this);
     variable->owner()->set_context_level(context_level());
   } else {
     ASSERT(variable->owner()->context_level() == context_level());
   }
   variable->set_index(num_context_variables_++);
 }


 int LocalScope::AllocateVariables(int first_parameter_index,
                                   int num_parameters,
                                   int first_frame_index,
                                   LocalScope* loop_owner,
                                   LocalScope** context_owner) {
   // We should not allocate variables of nested functions while compiling an
   // enclosing function.
   ASSERT(function_level() == 0);
   ASSERT(num_parameters >= 0);

   // Keep track of the current loop owner scope, that is of the highest parent
   // scope at the same loop level as this scope.
   if (loop_level() > loop_owner->loop_level()) {
     loop_owner = this;
   }
   // Parameters must be listed first and must all appear in the top scope.
   ASSERT(num_parameters <= num_variables());
   int pos = 0;  // Current variable position.
   int frame_index = first_parameter_index;  // Current free frame index.
   while (pos < num_parameters) {
     LocalVariable* parameter = VariableAt(pos);
     pos++;
     ASSERT(parameter->owner() == this);
     if (parameter->is_captured()) {
       // A captured parameter has a slot allocated in the frame and one in the
       // context, where it gets copied to. The parameter index reflects the
       // context allocation index.
       frame_index--;
       loop_owner->AllocateContextVariable(parameter, context_owner);
     } else {
       parameter->set_index(frame_index--);
     }
   }
   // No overlapping of parameters and locals.
   ASSERT(frame_index >= first_frame_index);
   frame_index = first_frame_index;
   while (pos < num_variables()) {
     LocalVariable* variable = VariableAt(pos);
     pos++;
     if (variable->owner() == this) {
       if (variable->is_captured()) {
         loop_owner->AllocateContextVariable(variable, context_owner);
       } else {
         variable->set_index(frame_index--);
       }
     }
   }
   // Allocate variables of all children.
   int min_frame_index = frame_index;
   LocalScope* child = this->child();
   while (child != NULL) {
     LocalScope* child_context_owner = *context_owner;
     int const dummy_parameter_index = 0;  // Ignored, since no parameters.
     int const num_parameters_in_child = 0;  // No parameters in children scopes.
     int child_frame_index = child->AllocateVariables(dummy_parameter_index,
                                                      num_parameters_in_child,
                                                      frame_index,
                                                      loop_owner,
                                                      &child_context_owner);
     if (child_frame_index < min_frame_index) {
       min_frame_index = child_frame_index;
     }
     // A context allocated at a deeper loop level than the current loop level is
     // not shared between children.
     if ((child_context_owner != *context_owner) &&
         (child_context_owner->loop_level() <= loop_owner->loop_level())) {
       *context_owner = child_context_owner;  // Share context between siblings.
     }
     child = child->sibling();
   }
   return min_frame_index;
 }


 RawLocalVarDescriptors* LocalScope::GetVarDescriptors(const Function& func) {
   GrowableArray<VarDesc> vars(8);
   // First enter all variables from scopes of outer functions.
   const ContextScope& context_scope =
       ContextScope::Handle(func.context_scope());
   if (!context_scope.IsNull()) {
     ASSERT(func.IsLocalFunction());
     for (int i = 0; i < context_scope.num_variables(); i++) {
       VarDesc desc;
       desc.name = &String::Handle(context_scope.NameAt(i));
       desc.info.kind =  RawLocalVarDescriptors::kContextVar;
       desc.info.scope_id = context_scope.ContextLevelAt(i);
       desc.info.begin_pos = begin_token_pos();
       desc.info.end_pos = end_token_pos();
       ASSERT(desc.info.begin_pos <= desc.info.end_pos);
       desc.info.index = context_scope.ContextIndexAt(i);
       vars.Add(desc);
     }
   }
   // Now collect all variables from local scopes.
   int16_t scope_id = 0;
   CollectLocalVariables(&vars, &scope_id);

   const LocalVarDescriptors& var_desc =
       LocalVarDescriptors::Handle(LocalVarDescriptors::New(vars.length()));
   for (int i = 0; i < vars.length(); i++) {
     var_desc.SetVar(i, *(vars[i].name), &vars[i].info);
   }
   return var_desc.raw();
 }


 // The parser creates internal variables that start with ":"
 static bool IsInternalIdentifier(const String& str) {
   ASSERT(str.Length() > 0);
   return str.CharAt(0) == ':';
 }


 // Add variables that are declared in this scope to vars, then collect
 // variables of children, followed by siblings.
 void LocalScope::CollectLocalVariables(GrowableArray<VarDesc>* vars,
                                        int16_t* scope_id) {
   (*scope_id)++;
   if (HasContextLevel() &&
       ((parent() == NULL) ||
       (!parent()->HasContextLevel()) ||
       (parent()->context_level() != context_level()))) {
     // This is the outermost scope with a context level or this scope's
     // context level differs from its parent's level.
     VarDesc desc;
     desc.name = &String::Handle();  // No name.
     desc.info.kind =  RawLocalVarDescriptors::kContextLevel;
     desc.info.scope_id = *scope_id;
     desc.info.begin_pos = begin_token_pos();
     desc.info.end_pos = end_token_pos();
     desc.info.index = context_level();
     vars->Add(desc);
   }
   for (int i = 0; i < this->variables_.length(); i++) {
     LocalVariable* var = variables_[i];
     if (var->owner() == this) {
       if (!IsInternalIdentifier(var->name())) {
         // This is a regular Dart variable, either stack-based or captured.
         VarDesc desc;
         desc.name = &var->name();
         if (var->is_captured()) {
           desc.info.kind = RawLocalVarDescriptors::kContextVar;
           ASSERT(var->owner() != NULL);
           ASSERT(var->owner()->context_level() >= 0);
           desc.info.scope_id = var->owner()->context_level();
         } else {
           desc.info.kind = RawLocalVarDescriptors::kStackVar;
           desc.info.scope_id = *scope_id;
         }
         desc.info.begin_pos = var->token_pos();
         desc.info.end_pos = var->owner()->end_token_pos();
         desc.info.index = var->index();
         vars->Add(desc);
       } else if (var->name().Equals(Symbols::SavedEntryContextVar())) {
         // This is the local variable in which the function saves the
         // caller's chain of closure contexts (caller's CTX register).
         VarDesc desc;
         desc.name = &var->name();
         desc.info.kind = RawLocalVarDescriptors::kSavedEntryContext;
         desc.info.scope_id = 0;
         desc.info.begin_pos = 0;
         desc.info.end_pos = 0;
         desc.info.index = var->index();
         vars->Add(desc);
       } else if (var->name().Equals(Symbols::SavedCurrentContextVar())) {
         // This is the local variable in which the function saves its
         // own context before calling a closure function.
         VarDesc desc;
         desc.name = &var->name();
         desc.info.kind = RawLocalVarDescriptors::kSavedCurrentContext;
         desc.info.scope_id = 0;
         desc.info.begin_pos = 0;
         desc.info.end_pos = 0;
         desc.info.index = var->index();
         vars->Add(desc);
       }
     }
   }
   LocalScope* child = this->child();
   while (child != NULL) {
     child->CollectLocalVariables(vars, scope_id);
     child = child->sibling();
   }
 }


 SourceLabel* LocalScope::LocalLookupLabel(const String& name) const {
   for (intptr_t i = 0; i < labels_.length(); i++) {
     SourceLabel* label = labels_[i];
     if (label->name().Equals(name)) {
       return label;
     }
   }
   return NULL;
 }


 LocalVariable* LocalScope::LocalLookupVariable(const String& name) const {
   ASSERT(name.IsSymbol());
   for (intptr_t i = 0; i < variables_.length(); i++) {
     LocalVariable* var = variables_[i];
     ASSERT(var->name().IsSymbol());
     if (var->name().raw() == name.raw()) {
       return var;
     }
   }
   return NULL;
 }


 LocalVariable* LocalScope::LookupVariable(const String& name, bool test_only) {
   LocalScope* current_scope = this;
   while (current_scope != NULL) {
     LocalVariable* var = current_scope->LocalLookupVariable(name);
     if ((var != NULL) && !var->is_invisible_) {
       if (!test_only) {
         if (var->owner()->function_level() != function_level()) {
           var->set_is_captured();
         }
         // Insert aliases of the variable in intermediate scopes.
         LocalScope* intermediate_scope = this;
         while (intermediate_scope != current_scope) {
           intermediate_scope->variables_.Add(var);
           ASSERT(var->owner() != intermediate_scope);  // Item is an alias.
           intermediate_scope = intermediate_scope->parent();
         }
       }
       return var;
     }
     current_scope = current_scope->parent();
   }
   return NULL;
 }


 bool LocalScope::CaptureVariable(const String& name) {
   ASSERT(name.IsSymbol());
   LocalScope* current_scope = this;
   while (current_scope != NULL) {
     LocalVariable* var = current_scope->LocalLookupVariable(name);
     if (var != NULL) {
       if (var->owner()->function_level() != function_level()) {
         var->set_is_captured();
       }
       // Insert aliases of the variable in intermediate scopes.
       LocalScope* intermediate_scope = this;
       while (intermediate_scope != current_scope) {
         intermediate_scope->variables_.Add(var);
         ASSERT(var->owner() != intermediate_scope);  // Item is an alias.
         intermediate_scope = intermediate_scope->parent();
       }
       return true;
     }
     current_scope = current_scope->parent();
   }
   return false;
 }


 SourceLabel* LocalScope::LookupLabel(const String& name) {
   LocalScope* current_scope = this;
   while (current_scope != NULL) {
     SourceLabel* label = current_scope->LocalLookupLabel(name);
     if (label != NULL) {
       return label;
     }
     current_scope = current_scope->parent();
   }
   return NULL;
 }


 SourceLabel* LocalScope::LookupInnermostLabel(Token::Kind jump_kind) {
   ASSERT((jump_kind == Token::kCONTINUE) || (jump_kind == Token::kBREAK));
   LocalScope* current_scope = this;
   while (current_scope != NULL) {
     for (intptr_t i = 0; i < current_scope->labels_.length(); i++) {
       SourceLabel* label = current_scope->labels_[i];
       if ((label->kind() == SourceLabel::kWhile) ||
           (label->kind() == SourceLabel::kFor) ||
           (label->kind() == SourceLabel::kDoWhile) ||
           ((jump_kind == Token::kBREAK) &&
               (label->kind() == SourceLabel::kSwitch))) {
         return label;
       }
     }
     current_scope = current_scope->parent();
   }
   return NULL;
 }


 SourceLabel* LocalScope::LookupInnermostCatchLabel() {
   LocalScope* current_scope = this;
   while (current_scope != NULL) {
     for (intptr_t i = 0; i < current_scope->labels_.length(); i++) {
       SourceLabel* label = current_scope->labels_[i];
       if (label->kind() == SourceLabel::kCatch) {
         return label;
       }
     }
     current_scope = current_scope->parent();
   }
   return NULL;
 }


 LocalScope* LocalScope::LookupSwitchScope() {
   LocalScope* current_scope = this->parent();
   int this_level = this->function_level();
   while (current_scope != NULL &&
          current_scope->function_level() == this_level) {
     for (int i = 0; i < current_scope->labels_.length(); i++) {
       SourceLabel* label = current_scope->labels_[i];
       if (label->kind() == SourceLabel::kSwitch) {
         // This scope contains a label that is bound to a switch statement,
         // so it is the scope of the a statement body.
         return current_scope;
       }
     }
     current_scope = current_scope->parent();
   }
   // We did not find a switch statement scope at the same function level.
   return NULL;
 }


 SourceLabel* LocalScope::CheckUnresolvedLabels() {
   for (int i = 0; i < this->labels_.length(); i++) {
     SourceLabel* label = this->labels_[i];
     if (label->kind() == SourceLabel::kForward) {
       LocalScope* outer_switch = LookupSwitchScope();
       if (outer_switch == NULL) {
         return label;
       } else {
         outer_switch->AddLabel(label);
       }
     }
   }
   return NULL;
 }


 int LocalScope::NumCapturedVariables() const {
   // It is not necessary to traverse parent scopes, since we are only interested
   // in the captured variables referenced in this scope. If this scope
   // references a captured variable declared in a parent scope, it will contain
   // an alias for that variable.

   // Since code generation for nested functions is postponed until first
   // invocation, the function level of the closure scope can only be 1.
   ASSERT(function_level() == 1);

   int num_captured = 0;
   for (int i = 0; i < num_variables(); i++) {
     LocalVariable* variable = VariableAt(i);
     // Count the aliases of captured variables belonging to outer scopes.
     if (variable->owner()->function_level() != 1) {
       ASSERT(variable->is_captured());
       ASSERT(variable->owner()->function_level() == 0);
       num_captured++;
     }
   }
   return num_captured;
 }


 RawContextScope* LocalScope::PreserveOuterScope(int current_context_level)
     const {
   // Since code generation for nested functions is postponed until first
   // invocation, the function level of the closure scope can only be 1.
   ASSERT(function_level() == 1);

   // Count the number of referenced captured variables.
   intptr_t num_captured_vars = NumCapturedVariables();

   // Create a ContextScope with space for num_captured_vars descriptors.
   const ContextScope& context_scope =
       ContextScope::Handle(ContextScope::New(num_captured_vars));

   // Create a descriptor for each referenced captured variable of enclosing
   // functions to preserve its name and its context allocation information.
   int captured_idx = 0;
   for (int i = 0; i < num_variables(); i++) {
     LocalVariable* variable = VariableAt(i);
     // Preserve the aliases of captured variables belonging to outer scopes.
     if (variable->owner()->function_level() != 1) {
       context_scope.SetTokenIndexAt(captured_idx, variable->token_pos());
       context_scope.SetNameAt(captured_idx, variable->name());
       context_scope.SetIsFinalAt(captured_idx, variable->is_final());
       context_scope.SetIsConstAt(captured_idx, variable->IsConst());
       if (variable->IsConst()) {
         context_scope.SetConstValueAt(captured_idx, *variable->ConstValue());
       } else {
         context_scope.SetTypeAt(captured_idx, variable->type());
       }
       context_scope.SetContextIndexAt(captured_idx, variable->index());
       // Adjust the context level relative to the current context level,
       // since the context of the current scope will be at level 0 when
       // compiling the nested function.
       int adjusted_context_level =
           variable->owner()->context_level() - current_context_level;
       context_scope.SetContextLevelAt(captured_idx, adjusted_context_level);
       captured_idx++;
     }
   }
   ASSERT(context_scope.num_variables() == captured_idx);  // Verify count.
   return context_scope.raw();
 }


 LocalScope* LocalScope::RestoreOuterScope(const ContextScope& context_scope) {
   // The function level of the outer scope is one less than the function level
   // of the current function, which is 0.
   LocalScope* outer_scope = new LocalScope(NULL, -1, 0);
   // Add all variables as aliases to the outer scope.
   for (int i = 0; i < context_scope.num_variables(); i++) {
     LocalVariable* variable;
     if (context_scope.IsConstAt(i)) {
       variable = new LocalVariable(context_scope.TokenIndexAt(i),
           String::ZoneHandle(context_scope.NameAt(i)),
           AbstractType::ZoneHandle(Type::DynamicType()));
       variable->SetConstValue(
           Instance::ZoneHandle(context_scope.ConstValueAt(i)));
     } else {
       variable = new LocalVariable(context_scope.TokenIndexAt(i),
           String::ZoneHandle(context_scope.NameAt(i)),
           AbstractType::ZoneHandle(context_scope.TypeAt(i)));
     }
     variable->set_is_captured();
     variable->set_index(context_scope.ContextIndexAt(i));
     if (context_scope.IsFinalAt(i)) {
       variable->set_is_final();
     }
     // Create a fake owner scope describing the index and context level of the
     // variable. Function level and loop level are unused (set to 0), since
     // context level has already been assigned.
     LocalScope* owner_scope = new LocalScope(NULL, 0, 0);
     owner_scope->set_context_level(context_scope.ContextLevelAt(i));
     owner_scope->AddVariable(variable);
     outer_scope->AddVariable(variable);  // As alias.
     ASSERT(variable->owner() == owner_scope);
   }
   return outer_scope;
 }


 RawContextScope* LocalScope::CreateImplicitClosureScope(const Function& func) {
   static const intptr_t kNumCapturedVars = 1;

   // Create a ContextScope with space for kNumCapturedVars descriptors.
   const ContextScope& context_scope =
       ContextScope::Handle(ContextScope::New(kNumCapturedVars));

   // Create a descriptor for 'this' variable.
   context_scope.SetTokenIndexAt(0, func.token_pos());
   context_scope.SetNameAt(0, Symbols::This());
   context_scope.SetIsFinalAt(0, true);
   context_scope.SetIsConstAt(0, false);
   const AbstractType& type = AbstractType::Handle(func.ParameterTypeAt(0));
   context_scope.SetTypeAt(0, type);
   context_scope.SetContextIndexAt(0, 0);
   context_scope.SetContextLevelAt(0, 0);
   ASSERT(context_scope.num_variables() == kNumCapturedVars);  // Verify count.
   return context_scope.raw();
 }


 bool LocalVariable::Equals(const LocalVariable& other) const {
   if (HasIndex() && other.HasIndex() && (index() == other.index())) {
     if (is_captured() == other.is_captured()) {
       if (!is_captured()) {
         return true;
       }
       if (owner()->context_level() == other.owner()->context_level()) {
         return true;
       }
     }
   }
   return false;
 }


 int LocalVariable::BitIndexIn(intptr_t fixed_parameter_count) const {
   ASSERT(!is_captured());
   // Parameters have positive indexes with the lowest index being
   // kParamEndSlotFromFp + 1.  Locals and copied parameters have negative
   // indexes with the lowest (closest to 0) index being kFirstLocalSlotFromFp.
   if (index() > 0) {
     // Shift non-negative indexes so that the lowest one is 0.
     return fixed_parameter_count - (index() - kParamEndSlotFromFp);
   } else {
     // Shift negative indexes so that the lowest one is 0 (they are still
     // non-positive).
     return fixed_parameter_count - (index() - kFirstLocalSlotFromFp);
   }
 }


 }  // namespace dart
	// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
	// for details. All rights reserved. Use of this source code is governed by a
	// BSD-style license that can be found in the LICENSE file.

	#include "vm/scopes.h"

	#include "vm/ast.h"
	#include "vm/bit_vector.h"
	#include "vm/object.h"
	#include "vm/parser.h"
	#include "vm/stack_frame.h"
	#include "vm/symbols.h"

	namespace dart {

	int SourceLabel::FunctionLevel() const {
	ASSERT(owner() != NULL);
	return owner()->function_level();
	}


	LocalScope::LocalScope(LocalScope* parent, int function_level, int loop_level)
	: parent_(parent),
	child_(NULL),
	sibling_(NULL),
	function_level_(function_level),
	loop_level_(loop_level),
	context_level_(LocalScope::kUnitializedContextLevel),
	num_context_variables_(0),
	begin_token_pos_(0),
	end_token_pos_(0),
	variables_(),
	labels_() {
	// Hook this node into the children of the parent, unless the parent has a
	// different function_level, since the local scope of a nested function can
	// be discarded after it has been parsed.
	if ((parent != NULL) && (parent->function_level() == function_level)) {
	sibling_ = parent->child_;
	parent->child_ = this;
	}
	}


	bool LocalScope::IsNestedWithin(LocalScope* scope) const {
	const LocalScope* current_scope = this;
	while (current_scope != NULL) {
	if (current_scope == scope) {
	return true;
	}
	current_scope = current_scope->parent();
	}
	return false;
	}


	bool LocalScope::AddVariable(LocalVariable* variable) {
	ASSERT(variable != NULL);
	if (LocalLookupVariable(variable->name()) != NULL) {
	return false;
	}
	variables_.Add(variable);
	if (variable->owner() == NULL) {
	// Variables must be added to their owner scope first. Subsequent calls
	// to 'add' treat the variable as an alias.
	variable->set_owner(this);
	}
	return true;
	}


	bool LocalScope::AddLabel(SourceLabel* label) {
	if (LocalLookupLabel(label->name()) != NULL) {
	return false;
	}
	labels_.Add(label);
	if (label->owner() == NULL) {
	// Labels must be added to their owner scope first. Subsequent calls
	// to 'add' treat the label as an alias.
	label->set_owner(this);
	}
	return true;
	}


	void LocalScope::AllocateContextVariable(LocalVariable* variable,
	LocalScope** context_owner) {
	ASSERT(variable->is_captured());
	ASSERT(variable->owner()->loop_level() == loop_level());
	if (num_context_variables_ == 0) {
	// This scope will allocate and chain a new context.
	int new_context_level = ((*context_owner) == NULL) ?
	1 : (*context_owner)->context_level() + 1;
	// This scope becomes the current context owner.
	*context_owner = this;
	set_context_level(new_context_level);
	}
	// The context level in the owner scope of a captured variable indicates at
	// code generation time how far to walk up the context chain in order to
	// access the variable from the current context level.
	if (!variable->owner()->HasContextLevel()) {
	ASSERT(variable->owner() != this);
	variable->owner()->set_context_level(context_level());
	} else {
	ASSERT(variable->owner()->context_level() == context_level());
	}
	variable->set_index(num_context_variables_++);
	}


	int LocalScope::AllocateVariables(int first_parameter_index,
	int num_parameters,
	int first_frame_index,
	LocalScope* loop_owner,
	LocalScope** context_owner) {
	// We should not allocate variables of nested functions while compiling an
	// enclosing function.
	ASSERT(function_level() == 0);
	ASSERT(num_parameters >= 0);

	// Keep track of the current loop owner scope, that is of the highest parent
	// scope at the same loop level as this scope.
	if (loop_level() > loop_owner->loop_level()) {
	loop_owner = this;
	}
	// Parameters must be listed first and must all appear in the top scope.
	ASSERT(num_parameters <= num_variables());
	int pos = 0; // Current variable position.
	int frame_index = first_parameter_index; // Current free frame index.
	while (pos < num_parameters) {
	LocalVariable* parameter = VariableAt(pos);
	pos++;
	ASSERT(parameter->owner() == this);
	if (parameter->is_captured()) {
	// A captured parameter has a slot allocated in the frame and one in the
	// context, where it gets copied to. The parameter index reflects the
	// context allocation index.
	frame_index--;
	loop_owner->AllocateContextVariable(parameter, context_owner);
	} else {
	parameter->set_index(frame_index--);
	}
	}
	// No overlapping of parameters and locals.
	ASSERT(frame_index >= first_frame_index);
	frame_index = first_frame_index;
	while (pos < num_variables()) {
	LocalVariable* variable = VariableAt(pos);
	pos++;
	if (variable->owner() == this) {
	if (variable->is_captured()) {
	loop_owner->AllocateContextVariable(variable, context_owner);
	} else {
	variable->set_index(frame_index--);
	}
	}
	}
	// Allocate variables of all children.
	int min_frame_index = frame_index;
	LocalScope* child = this->child();
	while (child != NULL) {
	LocalScope* child_context_owner = *context_owner;
	int const dummy_parameter_index = 0; // Ignored, since no parameters.
	int const num_parameters_in_child = 0; // No parameters in children scopes.
	int child_frame_index = child->AllocateVariables(dummy_parameter_index,
	num_parameters_in_child,
	frame_index,
	loop_owner,
	&child_context_owner);
	if (child_frame_index < min_frame_index) {
	min_frame_index = child_frame_index;
	}
	// A context allocated at a deeper loop level than the current loop level is
	// not shared between children.
	if ((child_context_owner != *context_owner) &&
	(child_context_owner->loop_level() <= loop_owner->loop_level())) {
	*context_owner = child_context_owner; // Share context between siblings.
	}
	child = child->sibling();
	}
	return min_frame_index;
	}


	RawLocalVarDescriptors* LocalScope::GetVarDescriptors(const Function& func) {
	GrowableArray<VarDesc> vars(8);
	// First enter all variables from scopes of outer functions.
	const ContextScope& context_scope =
	ContextScope::Handle(func.context_scope());
	if (!context_scope.IsNull()) {
	ASSERT(func.IsLocalFunction());
	for (int i = 0; i < context_scope.num_variables(); i++) {
	VarDesc desc;
	desc.name = &String::Handle(context_scope.NameAt(i));
	desc.info.kind = RawLocalVarDescriptors::kContextVar;
	desc.info.scope_id = context_scope.ContextLevelAt(i);
	desc.info.begin_pos = begin_token_pos();
	desc.info.end_pos = end_token_pos();
	ASSERT(desc.info.begin_pos <= desc.info.end_pos);
	desc.info.index = context_scope.ContextIndexAt(i);
	vars.Add(desc);
	}
	}
	// Now collect all variables from local scopes.
	int16_t scope_id = 0;
	CollectLocalVariables(&vars, &scope_id);

	const LocalVarDescriptors& var_desc =
	LocalVarDescriptors::Handle(LocalVarDescriptors::New(vars.length()));
	for (int i = 0; i < vars.length(); i++) {
	var_desc.SetVar(i, *(vars[i].name), &vars[i].info);
	}
	return var_desc.raw();
	}


	// The parser creates internal variables that start with ":"
	static bool IsInternalIdentifier(const String& str) {
	ASSERT(str.Length() > 0);
	return str.CharAt(0) == ':';
	}


	// Add variables that are declared in this scope to vars, then collect
	// variables of children, followed by siblings.
	void LocalScope::CollectLocalVariables(GrowableArray<VarDesc>* vars,
	int16_t* scope_id) {
	(*scope_id)++;
	if (HasContextLevel() &&
	((parent() == NULL) \|\|
	(!parent()->HasContextLevel()) \|\|
	(parent()->context_level() != context_level()))) {
	// This is the outermost scope with a context level or this scope's
	// context level differs from its parent's level.
	VarDesc desc;
	desc.name = &String::Handle(); // No name.
	desc.info.kind = RawLocalVarDescriptors::kContextLevel;
	desc.info.scope_id = *scope_id;
	desc.info.begin_pos = begin_token_pos();
	desc.info.end_pos = end_token_pos();
	desc.info.index = context_level();
	vars->Add(desc);
	}
	for (int i = 0; i < this->variables_.length(); i++) {
	LocalVariable* var = variables_[i];
	if (var->owner() == this) {
	if (!IsInternalIdentifier(var->name())) {
	// This is a regular Dart variable, either stack-based or captured.
	VarDesc desc;
	desc.name = &var->name();
	if (var->is_captured()) {
	desc.info.kind = RawLocalVarDescriptors::kContextVar;
	ASSERT(var->owner() != NULL);
	ASSERT(var->owner()->context_level() >= 0);
	desc.info.scope_id = var->owner()->context_level();
	} else {
	desc.info.kind = RawLocalVarDescriptors::kStackVar;
	desc.info.scope_id = *scope_id;
	}
	desc.info.begin_pos = var->token_pos();
	desc.info.end_pos = var->owner()->end_token_pos();
	desc.info.index = var->index();
	vars->Add(desc);
	} else if (var->name().Equals(Symbols::SavedEntryContextVar())) {
	// This is the local variable in which the function saves the
	// caller's chain of closure contexts (caller's CTX register).
	VarDesc desc;
	desc.name = &var->name();
	desc.info.kind = RawLocalVarDescriptors::kSavedEntryContext;
	desc.info.scope_id = 0;
	desc.info.begin_pos = 0;
	desc.info.end_pos = 0;
	desc.info.index = var->index();
	vars->Add(desc);
	} else if (var->name().Equals(Symbols::SavedCurrentContextVar())) {
	// This is the local variable in which the function saves its
	// own context before calling a closure function.
	VarDesc desc;
	desc.name = &var->name();
	desc.info.kind = RawLocalVarDescriptors::kSavedCurrentContext;
	desc.info.scope_id = 0;
	desc.info.begin_pos = 0;
	desc.info.end_pos = 0;
	desc.info.index = var->index();
	vars->Add(desc);
	}
	}
	}
	LocalScope* child = this->child();
	while (child != NULL) {
	child->CollectLocalVariables(vars, scope_id);
	child = child->sibling();
	}
	}


	SourceLabel* LocalScope::LocalLookupLabel(const String& name) const {
	for (intptr_t i = 0; i < labels_.length(); i++) {
	SourceLabel* label = labels_[i];
	if (label->name().Equals(name)) {
	return label;
	}
	}
	return NULL;
	}


	LocalVariable* LocalScope::LocalLookupVariable(const String& name) const {
	ASSERT(name.IsSymbol());
	for (intptr_t i = 0; i < variables_.length(); i++) {
	LocalVariable* var = variables_[i];
	ASSERT(var->name().IsSymbol());
	if (var->name().raw() == name.raw()) {
	return var;
	}
	}
	return NULL;
	}


	LocalVariable* LocalScope::LookupVariable(const String& name, bool test_only) {
	LocalScope* current_scope = this;
	while (current_scope != NULL) {
	LocalVariable* var = current_scope->LocalLookupVariable(name);
	if ((var != NULL) && !var->is_invisible_) {
	if (!test_only) {
	if (var->owner()->function_level() != function_level()) {
	var->set_is_captured();
	}
	// Insert aliases of the variable in intermediate scopes.
	LocalScope* intermediate_scope = this;
	while (intermediate_scope != current_scope) {
	intermediate_scope->variables_.Add(var);
	ASSERT(var->owner() != intermediate_scope); // Item is an alias.
	intermediate_scope = intermediate_scope->parent();
	}
	}
	return var;
	}
	current_scope = current_scope->parent();
	}
	return NULL;
	}


	bool LocalScope::CaptureVariable(const String& name) {
	ASSERT(name.IsSymbol());
	LocalScope* current_scope = this;
	while (current_scope != NULL) {
	LocalVariable* var = current_scope->LocalLookupVariable(name);
	if (var != NULL) {
	if (var->owner()->function_level() != function_level()) {
	var->set_is_captured();
	}
	// Insert aliases of the variable in intermediate scopes.
	LocalScope* intermediate_scope = this;
	while (intermediate_scope != current_scope) {
	intermediate_scope->variables_.Add(var);
	ASSERT(var->owner() != intermediate_scope); // Item is an alias.
	intermediate_scope = intermediate_scope->parent();
	}
	return true;
	}
	current_scope = current_scope->parent();
	}
	return false;
	}


	SourceLabel* LocalScope::LookupLabel(const String& name) {
	LocalScope* current_scope = this;
	while (current_scope != NULL) {
	SourceLabel* label = current_scope->LocalLookupLabel(name);
	if (label != NULL) {
	return label;
	}
	current_scope = current_scope->parent();
	}
	return NULL;
	}


	SourceLabel* LocalScope::LookupInnermostLabel(Token::Kind jump_kind) {
	ASSERT((jump_kind == Token::kCONTINUE) \|\| (jump_kind == Token::kBREAK));
	LocalScope* current_scope = this;
	while (current_scope != NULL) {
	for (intptr_t i = 0; i < current_scope->labels_.length(); i++) {
	SourceLabel* label = current_scope->labels_[i];
	if ((label->kind() == SourceLabel::kWhile) \|\|
	(label->kind() == SourceLabel::kFor) \|\|
	(label->kind() == SourceLabel::kDoWhile) \|\|
	((jump_kind == Token::kBREAK) &&
	(label->kind() == SourceLabel::kSwitch))) {
	return label;
	}
	}
	current_scope = current_scope->parent();
	}
	return NULL;
	}


	SourceLabel* LocalScope::LookupInnermostCatchLabel() {
	LocalScope* current_scope = this;
	while (current_scope != NULL) {
	for (intptr_t i = 0; i < current_scope->labels_.length(); i++) {
	SourceLabel* label = current_scope->labels_[i];
	if (label->kind() == SourceLabel::kCatch) {
	return label;
	}
	}
	current_scope = current_scope->parent();
	}
	return NULL;
	}


	LocalScope* LocalScope::LookupSwitchScope() {
	LocalScope* current_scope = this->parent();
	int this_level = this->function_level();
	while (current_scope != NULL &&
	current_scope->function_level() == this_level) {
	for (int i = 0; i < current_scope->labels_.length(); i++) {
	SourceLabel* label = current_scope->labels_[i];
	if (label->kind() == SourceLabel::kSwitch) {
	// This scope contains a label that is bound to a switch statement,
	// so it is the scope of the a statement body.
	return current_scope;
	}
	}
	current_scope = current_scope->parent();
	}
	// We did not find a switch statement scope at the same function level.
	return NULL;
	}


	SourceLabel* LocalScope::CheckUnresolvedLabels() {
	for (int i = 0; i < this->labels_.length(); i++) {
	SourceLabel* label = this->labels_[i];
	if (label->kind() == SourceLabel::kForward) {
	LocalScope* outer_switch = LookupSwitchScope();
	if (outer_switch == NULL) {
	return label;
	} else {
	outer_switch->AddLabel(label);
	}
	}
	}
	return NULL;
	}


	int LocalScope::NumCapturedVariables() const {
	// It is not necessary to traverse parent scopes, since we are only interested
	// in the captured variables referenced in this scope. If this scope
	// references a captured variable declared in a parent scope, it will contain
	// an alias for that variable.

	// Since code generation for nested functions is postponed until first
	// invocation, the function level of the closure scope can only be 1.
	ASSERT(function_level() == 1);

	int num_captured = 0;
	for (int i = 0; i < num_variables(); i++) {
	LocalVariable* variable = VariableAt(i);
	// Count the aliases of captured variables belonging to outer scopes.
	if (variable->owner()->function_level() != 1) {
	ASSERT(variable->is_captured());
	ASSERT(variable->owner()->function_level() == 0);
	num_captured++;
	}
	}
	return num_captured;
	}


	RawContextScope* LocalScope::PreserveOuterScope(int current_context_level)
	const {
	// Since code generation for nested functions is postponed until first
	// invocation, the function level of the closure scope can only be 1.
	ASSERT(function_level() == 1);

	// Count the number of referenced captured variables.
	intptr_t num_captured_vars = NumCapturedVariables();

	// Create a ContextScope with space for num_captured_vars descriptors.
	const ContextScope& context_scope =
	ContextScope::Handle(ContextScope::New(num_captured_vars));

	// Create a descriptor for each referenced captured variable of enclosing
	// functions to preserve its name and its context allocation information.
	int captured_idx = 0;
	for (int i = 0; i < num_variables(); i++) {
	LocalVariable* variable = VariableAt(i);
	// Preserve the aliases of captured variables belonging to outer scopes.
	if (variable->owner()->function_level() != 1) {
	context_scope.SetTokenIndexAt(captured_idx, variable->token_pos());
	context_scope.SetNameAt(captured_idx, variable->name());
	context_scope.SetIsFinalAt(captured_idx, variable->is_final());
	context_scope.SetIsConstAt(captured_idx, variable->IsConst());
	if (variable->IsConst()) {
	context_scope.SetConstValueAt(captured_idx, *variable->ConstValue());
	} else {
	context_scope.SetTypeAt(captured_idx, variable->type());
	}
	context_scope.SetContextIndexAt(captured_idx, variable->index());
	// Adjust the context level relative to the current context level,
	// since the context of the current scope will be at level 0 when
	// compiling the nested function.
	int adjusted_context_level =
	variable->owner()->context_level() - current_context_level;
	context_scope.SetContextLevelAt(captured_idx, adjusted_context_level);
	captured_idx++;
	}
	}
	ASSERT(context_scope.num_variables() == captured_idx); // Verify count.
	return context_scope.raw();
	}


	LocalScope* LocalScope::RestoreOuterScope(const ContextScope& context_scope) {
	// The function level of the outer scope is one less than the function level
	// of the current function, which is 0.
	LocalScope* outer_scope = new LocalScope(NULL, -1, 0);
	// Add all variables as aliases to the outer scope.
	for (int i = 0; i < context_scope.num_variables(); i++) {
	LocalVariable* variable;
	if (context_scope.IsConstAt(i)) {
	variable = new LocalVariable(context_scope.TokenIndexAt(i),
	String::ZoneHandle(context_scope.NameAt(i)),
	AbstractType::ZoneHandle(Type::DynamicType()));
	variable->SetConstValue(
	Instance::ZoneHandle(context_scope.ConstValueAt(i)));
	} else {
	variable = new LocalVariable(context_scope.TokenIndexAt(i),
	String::ZoneHandle(context_scope.NameAt(i)),
	AbstractType::ZoneHandle(context_scope.TypeAt(i)));
	}
	variable->set_is_captured();
	variable->set_index(context_scope.ContextIndexAt(i));
	if (context_scope.IsFinalAt(i)) {
	variable->set_is_final();
	}
	// Create a fake owner scope describing the index and context level of the
	// variable. Function level and loop level are unused (set to 0), since
	// context level has already been assigned.
	LocalScope* owner_scope = new LocalScope(NULL, 0, 0);
	owner_scope->set_context_level(context_scope.ContextLevelAt(i));
	owner_scope->AddVariable(variable);
	outer_scope->AddVariable(variable); // As alias.
	ASSERT(variable->owner() == owner_scope);
	}
	return outer_scope;
	}


	RawContextScope* LocalScope::CreateImplicitClosureScope(const Function& func) {
	static const intptr_t kNumCapturedVars = 1;

	// Create a ContextScope with space for kNumCapturedVars descriptors.
	const ContextScope& context_scope =
	ContextScope::Handle(ContextScope::New(kNumCapturedVars));

	// Create a descriptor for 'this' variable.
	context_scope.SetTokenIndexAt(0, func.token_pos());
	context_scope.SetNameAt(0, Symbols::This());
	context_scope.SetIsFinalAt(0, true);
	context_scope.SetIsConstAt(0, false);
	const AbstractType& type = AbstractType::Handle(func.ParameterTypeAt(0));
	context_scope.SetTypeAt(0, type);
	context_scope.SetContextIndexAt(0, 0);
	context_scope.SetContextLevelAt(0, 0);
	ASSERT(context_scope.num_variables() == kNumCapturedVars); // Verify count.
	return context_scope.raw();
	}


	bool LocalVariable::Equals(const LocalVariable& other) const {
	if (HasIndex() && other.HasIndex() && (index() == other.index())) {
	if (is_captured() == other.is_captured()) {
	if (!is_captured()) {
	return true;
	}
	if (owner()->context_level() == other.owner()->context_level()) {
	return true;
	}
	}
	}
	return false;
	}


	int LocalVariable::BitIndexIn(intptr_t fixed_parameter_count) const {
	ASSERT(!is_captured());
	// Parameters have positive indexes with the lowest index being
	// kParamEndSlotFromFp + 1. Locals and copied parameters have negative
	// indexes with the lowest (closest to 0) index being kFirstLocalSlotFromFp.
	if (index() > 0) {
	// Shift non-negative indexes so that the lowest one is 0.
	return fixed_parameter_count - (index() - kParamEndSlotFromFp);
	} else {
	// Shift negative indexes so that the lowest one is 0 (they are still
	// non-positive).
	return fixed_parameter_count - (index() - kFirstLocalSlotFromFp);
	}
	}


	} // namespace dart