Scope tree serialization and ScopeIterator cleanup.

src/scopeinfo.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 33 matching lines @@
   // Consider sorting them according to type as well?
   return x - y;
 }
 
 
 template<class Allocator>
 ScopeInfo<Allocator>::ScopeInfo(Scope* scope)
     : function_name_(FACTORY->empty_symbol()),
       calls_eval_(scope->calls_eval()),
       is_strict_mode_(scope->is_strict_mode()),
+      type_(scope->type()),
+      source_beg_statement_pos_(scope->SourceBegStatementPos()),
+      source_end_statement_pos_(scope->SourceEndStatementPos()),
       parameters_(scope->num_parameters()),
       stack_slots_(scope->num_stack_slots()),
       context_slots_(scope->num_heap_slots()),
-      context_modes_(scope->num_heap_slots()) {
+      context_modes_(scope->num_heap_slots()),
+      inner_scopeinfos_(scope->InnerScopes()->length()) {
   // Add parameters.
   for (int i = 0; i < scope->num_parameters(); i++) {
     ASSERT(parameters_.length() == i);
     parameters_.Add(scope->parameter(i)->name());
   }
 
   // Add stack locals and collect heap locals.
   // We are assuming that the locals' slots are allocated in
   // increasing order, so we can simply add them to the
   // ScopeInfo lists. However, due to usage analysis, this is
@@ skipping 66 matching lines @@
       // Contexts::Lookup() function. Thus record an empty symbol here so we
       // get the correct number of context slots.
       ASSERT(proxy->var()->index() - Context::MIN_CONTEXT_SLOTS ==
              context_slots_.length());
       ASSERT(proxy->var()->index() - Context::MIN_CONTEXT_SLOTS ==
              context_modes_.length());
       context_slots_.Add(FACTORY->empty_symbol());
       context_modes_.Add(Variable::INTERNAL);
     }
   }
+
+  // Add nested scope information. Only nested block, catch or with scopes are
+  // tracked, but no inner function scopes.
+  ZoneList<Scope*>* inner_scopes = scope->InnerScopes();
+  for (int i = 0; i < inner_scopes->length(); i++) {
+    if (!inner_scopes->at(i)->is_declaration_scope()) {
+      inner_scopeinfos_.Add(SerializedScopeInfo::Create(inner_scopes->at(i)));
+    }
+  }
 }
 
 
 // Encoding format in a FixedArray object:
 //
 // - function name
 //
 // - calls eval boolean flag

[Kevin Millikin (Chromium), 2011/10/05 08:43:36]

This is a separate change, but this class should be cleaned up.

(1) The encoding should be represent in code (with something other than the
magic number below), and not just in this comment.  I suggest named constants
like all the other HeapObject layouts.

(2) It's a small improvement, but we can pack the flags and type into a single
pointer.

(3) The streaming interface of the Read/Write functions is just clumsy and
doesn't really seem necessary.  A straight random access interface makes it more
clear what's going on, I think.

(4) Related to 3, it's probably simplest to have a fixed part up front, and all
the variable sized stuff at the end.  This should give the same performance with
a much simpler layout and implementation.

[Steven, 2011/10/06 19:09:27]

Yes I agree. We will talk about this cleanup later again.
On 2011/10/05 08:43:36, Kevin Millikin wrote:

 //
+// - is strict mode scope
+//
+// - scope type
+//
+// - start statement position
+//
+// - end statement position
+//
 // - number of variables in the context object (smi) (= function context
 //   slot index + 1)
 // - list of pairs (name, Var mode) of context-allocated variables (starting
 //   with context slot 0)
 //
 // - number of parameters (smi)
 // - list of parameter names (starting with parameter 0 first)
 //
 // - number of variables on the stack (smi)
 // - list of names of stack-allocated variables (starting with stack slot 0)
+//
+// - number of immediate nested scopes (smi)
+// - list of handles to serialized scope infos for nested scopes
 
 // The ScopeInfo representation could be simplified and the ScopeInfo
 // re-implemented (with almost the same interface). Here is a
 // suggestion for the new format:
 //
 // - have a single list with all variable names (parameters, stack locals,
 //   context locals), followed by a list of non-Object* values containing
 //   the variables information (what kind, index, attributes)
 // - searching the linear list of names is fast and yields an index into the
 //   list if the variable name is found
 // - that list index is then used to find the variable information in the
 //   subsequent list
 // - the list entries don't have to be in any particular order, so all the
 //   current sorting business can go away
 // - the ScopeInfo lookup routines can be reduced to perhaps a single lookup
 //   which returns all information at once
 // - when gathering the information from a Scope, we only need to iterate
 //   through the local variables (parameters and context info is already
 //   present)
 
 
-static inline Object** ReadInt(Object** p, int* x) {
-  *x = (reinterpret_cast<Smi*>(*p++))->value();
+template <class T>
+static inline Object** ReadInt(Object** p, T* x) {
+  *x = static_cast<T>((reinterpret_cast<Smi*>(*p++))->value());
   return p;
 }
 
 
 static inline Object** ReadBool(Object** p, bool* x) {
   *x = (reinterpret_cast<Smi*>(*p++))->value() != 0;
   return p;
 }
 
 
-static inline Object** ReadSymbol(Object** p, Handle<String>* s) {
-  *s = Handle<String>(reinterpret_cast<String*>(*p++));
+template <class T>
+static inline Object** ReadObject(Object** p, Handle<T>* s) {
+  *s = Handle<T>::cast(Handle<Object>(*p++));
   return p;
 }
 
 
-template <class Allocator>
-static Object** ReadList(Object** p, List<Handle<String>, Allocator >* list) {
+template <class Allocator, class T>
+static Object** ReadList(Object** p, List<Handle<T>, Allocator >* list) {
   ASSERT(list->is_empty());
   int n;
   p = ReadInt(p, &n);
   while (n-- > 0) {
-    Handle<String> s;
-    p = ReadSymbol(p, &s);
+    Handle<T> s;
+    p = ReadObject(p, &s);
     list->Add(s);
   }
   return p;
 }
 
 
 template <class Allocator>
 static Object** ReadList(Object** p,
                          List<Handle<String>, Allocator>* list,
                          List<Variable::Mode, Allocator>* modes) {
   ASSERT(list->is_empty());
   int n;
   p = ReadInt(p, &n);
   while (n-- > 0) {
     Handle<String> s;
     int m;
-    p = ReadSymbol(p, &s);
+    p = ReadObject(p, &s);
     p = ReadInt(p, &m);
     list->Add(s);
     modes->Add(static_cast<Variable::Mode>(m));
   }
   return p;
 }
 
 
 template<class Allocator>
 ScopeInfo<Allocator>::ScopeInfo(SerializedScopeInfo* data)

[Kevin Millikin (Chromium), 2011/10/05 08:43:36]

Also, for future refactoring.  Do we need the ability to construct a ScopeInfo
from a SerializedScopeInfo?  (Do we need ScopeInfo at all?)

[Steven, 2011/10/06 19:09:27]

No we can unify those classes, they only differ slightly in the functionality
they expose.
On 2011/10/05 08:43:36, Kevin Millikin wrote:

   : function_name_(FACTORY->empty_symbol()),
     parameters_(4),
     stack_slots_(8),
     context_slots_(8),
-    context_modes_(8) {
+    context_modes_(8),
+    inner_scopeinfos_(4) {
   if (data->length() > 0) {
     Object** p0 = data->data_start();
     Object** p = p0;
-    p = ReadSymbol(p, &function_name_);
+    p = ReadObject(p, &function_name_);
     p = ReadBool(p, &calls_eval_);
     p = ReadBool(p, &is_strict_mode_);
+    p = ReadInt(p, &type_);
+    p = ReadInt(p, &source_beg_statement_pos_);
+    p = ReadInt(p, &source_end_statement_pos_);
     p = ReadList<Allocator>(p, &context_slots_, &context_modes_);
     p = ReadList<Allocator>(p, &parameters_);
     p = ReadList<Allocator>(p, &stack_slots_);
+    p = ReadList<Allocator>(p, &inner_scopeinfos_);
     ASSERT((p - p0) == FixedArray::cast(data)->length());
   }
 }
 
 
 static inline Object** WriteInt(Object** p, int x) {
   *p++ = Smi::FromInt(x);
   return p;
 }
 
 
 static inline Object** WriteBool(Object** p, bool b) {
   *p++ = Smi::FromInt(b ? 1 : 0);
   return p;
 }
 
 
-static inline Object** WriteSymbol(Object** p, Handle<String> s) {
+template <class T>
+static inline Object** WriteObject(Object** p, Handle<T> s) {
   *p++ = *s;
   return p;
 }
 
 
-template <class Allocator>
-static Object** WriteList(Object** p, List<Handle<String>, Allocator >* list) {
+template <class Allocator, class T>
+static Object** WriteList(Object** p, List<Handle<T>, Allocator >* list) {
   const int n = list->length();
   p = WriteInt(p, n);
   for (int i = 0; i < n; i++) {
-    p = WriteSymbol(p, list->at(i));
+    p = WriteObject(p, list->at(i));
   }
   return p;
 }
 
 
 template <class Allocator>
 static Object** WriteList(Object** p,
                           List<Handle<String>, Allocator>* list,
                           List<Variable::Mode, Allocator>* modes) {
   const int n = list->length();
   p = WriteInt(p, n);
   for (int i = 0; i < n; i++) {
-    p = WriteSymbol(p, list->at(i));
+    p = WriteObject(p, list->at(i));
     p = WriteInt(p, modes->at(i));
   }
   return p;
 }
 
 
 template<class Allocator>
 Handle<SerializedScopeInfo> ScopeInfo<Allocator>::Serialize() {
-  // function name, calls eval, is_strict_mode, length for 3 tables:
-  const int extra_slots = 1 + 1 + 1 + 3;
+  // function name, calls eval, is_strict_mode, scope type, source beg pos,
+  // source end pos, length for 4 tables:
+  const int extra_slots = 1 + 1 + 1 + 1 + 1 + 1 + 4;
   int length = extra_slots +
                context_slots_.length() * 2 +
                parameters_.length() +
-               stack_slots_.length();
+               stack_slots_.length() +
+               inner_scopeinfos_.length();
 
   Handle<SerializedScopeInfo> data(
       SerializedScopeInfo::cast(*FACTORY->NewSerializedScopeInfo(length)));
   AssertNoAllocation nogc;
 
   Object** p0 = data->data_start();
   Object** p = p0;
-  p = WriteSymbol(p, function_name_);
+  p = WriteObject(p, function_name_);
   p = WriteBool(p, calls_eval_);
   p = WriteBool(p, is_strict_mode_);
+  p = WriteInt(p, type_);
+  p = WriteInt(p, source_beg_statement_pos_);
+  p = WriteInt(p, source_end_statement_pos_);
   p = WriteList(p, &context_slots_, &context_modes_);
   p = WriteList(p, &parameters_);
   p = WriteList(p, &stack_slots_);
+  p = WriteList(p, &inner_scopeinfos_);
   ASSERT((p - p0) == length);
 
   return data;
 }
 
 
 template<class Allocator>
 Handle<String> ScopeInfo<Allocator>::LocalName(int i) const {
   // A local variable can be allocated either on the stack or in the context.
   // For variables allocated in the context they are always preceded by
@@ skipping 24 matching lines @@
 }
 
 
 SerializedScopeInfo* SerializedScopeInfo::Empty() {
   return reinterpret_cast<SerializedScopeInfo*>(HEAP->empty_fixed_array());
 }
 
 
 Object** SerializedScopeInfo::ContextEntriesAddr() {
   ASSERT(length() > 0);
-  // +3 for function name, calls eval, strict mode.
-  return data_start() + 3;
+  // +6 for function name, calls eval, strict mode, scope type, source beg pos,
+  // source end pos.
+  return data_start() + 6;
 }
 
 
 Object** SerializedScopeInfo::ParameterEntriesAddr() {
   ASSERT(length() > 0);
   Object** p = ContextEntriesAddr();
   int number_of_context_slots;
   p = ReadInt(p, &number_of_context_slots);
   return p + number_of_context_slots*2;  // *2 for pairs
 }
 
 
 Object** SerializedScopeInfo::StackSlotEntriesAddr() {
   ASSERT(length() > 0);
   Object** p = ParameterEntriesAddr();
   int number_of_parameter_slots;
   p = ReadInt(p, &number_of_parameter_slots);
   return p + number_of_parameter_slots;
 }
 
 
+Object** SerializedScopeInfo::NestedScopeEntriesAddr() {
+  ASSERT(length() > 0);
+  Object** p = StackSlotEntriesAddr();
+  int number_of_stack_slots;
+  p = ReadInt(p, &number_of_stack_slots);
+  return p + number_of_stack_slots;
+}
+
+
 bool SerializedScopeInfo::CallsEval() {
   if (length() > 0) {
     Object** p = data_start() + 1;  // +1 for function name.
     bool calls_eval;
     p = ReadBool(p, &calls_eval);
     return calls_eval;
   }
   return false;
 }
 
 
 bool SerializedScopeInfo::IsStrictMode() {
   if (length() > 0) {
     Object** p = data_start() + 2;  // +2 for function name, calls eval.
     bool strict_mode;
     p = ReadBool(p, &strict_mode);
     return strict_mode;
   }
   return false;
 }
 
 
+Scope::Type SerializedScopeInfo::ScopeType() {
+  ASSERT(length() > 0);
+  // +3 for function name, calls eval, strict mode.
+  Object** p = data_start() + 3;
+  Scope::Type type;
+  p = ReadInt(p, &type);

[Kevin Millikin (Chromium), 2011/10/05 08:43:36]

Future refactoring: if you decide to keep the streaming interface, the default
for Read is wrong.  It should be:

Scope::Type type = ReadInt(&p);

So you can just write here:

return ReadInt(&p);

+  return type;
+}
+
+
+int SerializedScopeInfo::SourceBegStatementPos() {
+  if (length() > 0) {
+    // +4 for function name, calls eval, strict mode, scope type.
+    Object** p = data_start() + 4;
+    int source_beg_statement_pos;
+    p = ReadInt(p, &source_beg_statement_pos);
+    return source_beg_statement_pos;
+  }
+  return -1;

[Kevin Millikin (Chromium), 2011/10/05 08:43:36]

-1 is RelocInfo::kNoPosition?

[Steven, 2011/10/06 19:09:27]

Yes it is. Using the named constant now.
On 2011/10/05 08:43:36, Kevin Millikin wrote:

+}
+
+
+int SerializedScopeInfo::SourceEndStatementPos() {
+  if (length() > 0) {
+    // +5 for function name, calls eval, strict mode, scope type,
+    // source beg pos.
+    Object** p = data_start() + 5;
+    int source_end_statement_pos;
+    p = ReadInt(p, &source_end_statement_pos);
+    return source_end_statement_pos;
+  }
+  return -1;
+}
+
+
 int SerializedScopeInfo::NumberOfStackSlots() {
   if (length() > 0) {
     Object** p = StackSlotEntriesAddr();
     int number_of_stack_slots;
     ReadInt(p, &number_of_stack_slots);
     return number_of_stack_slots;
   }
   return 0;
 }
 
 
 int SerializedScopeInfo::NumberOfContextSlots() {
   if (length() > 0) {
     Object** p = ContextEntriesAddr();
     int number_of_context_slots;
     ReadInt(p, &number_of_context_slots);
     return number_of_context_slots + Context::MIN_CONTEXT_SLOTS;
   }
   return 0;
 }
 
 
+int SerializedScopeInfo::NumberOfNestedScopes() {
+  if (length() > 0) {
+    Object** p = NestedScopeEntriesAddr();
+    int number_of_nested_scopes;
+    ReadInt(p, &number_of_nested_scopes);
+    return number_of_nested_scopes;
+  }
+  return 0;
+}
+
+
+Handle<SerializedScopeInfo> SerializedScopeInfo::NestedScope(int i) {
+  ASSERT(0 <= i && i < NumberOfNestedScopes());
+  Object* p = *(NestedScopeEntriesAddr() + i + 1);
+  return Handle<SerializedScopeInfo>(reinterpret_cast<SerializedScopeInfo*>(p));
+}
+
+
 bool SerializedScopeInfo::HasHeapAllocatedLocals() {
   if (length() > 0) {
     Object** p = ContextEntriesAddr();
     int number_of_context_slots;
     ReadInt(p, &number_of_context_slots);
     return number_of_context_slots > 0;
   }
   return false;
 }
 
 
+bool SerializedScopeInfo::HasContext() {
+  return HasHeapAllocatedLocals() ||
+      ScopeType() == Scope::WITH_SCOPE;
+}
+
+
 int SerializedScopeInfo::StackSlotIndex(String* name) {
   ASSERT(name->IsSymbol());
   if (length() > 0) {
     // Slots start after length entry.
     Object** p0 = StackSlotEntriesAddr();
     int number_of_stack_slots;
     p0 = ReadInt(p0, &number_of_stack_slots);
     Object** p = p0;
     Object** end = p0 + number_of_stack_slots;
     while (p != end) {
@@ skipping 71 matching lines @@
       ReadInt(p, &number_of_context_slots);
       ASSERT(number_of_context_slots != 0);
       // The function context slot is the last entry.
       return number_of_context_slots + Context::MIN_CONTEXT_SLOTS - 1;
     }
   }
   return -1;
 }
 
 
+void SerializedScopeInfo::GetNestedScopeChain(
+    List<Handle<SerializedScopeInfo> >* chain,
+    int position) {
+  chain->Add(Handle<SerializedScopeInfo>(this));
+
+  for (int i = 0; i < NumberOfNestedScopes(); i++) {
+    Handle<SerializedScopeInfo> scope = NestedScope(i);
+    int beg_pos = scope->SourceBegStatementPos();
+    int end_pos = scope->SourceEndStatementPos();
+    ASSERT(beg_pos >= 0 && end_pos >= 0);
+    if (beg_pos <= position && position <= end_pos) {
+      scope->GetNestedScopeChain(chain, position);
+      return;
+    }
+  }
+}
+
+
 int ContextSlotCache::Hash(Object* data, String* name) {
   // Uses only lower 32 bits if pointers are larger.
   uintptr_t addr_hash =
       static_cast<uint32_t>(reinterpret_cast<uintptr_t>(data)) >> 2;
   return static_cast<int>((addr_hash ^ name->Hash()) % kLength);
 }
 
 
 int ContextSlotCache::Lookup(Object* data,
                              String* name,
@@ skipping 89 matching lines @@
 }
 #endif  // DEBUG
 
 
 // Make sure the classes get instantiated by the template system.
 template class ScopeInfo<FreeStoreAllocationPolicy>;
 template class ScopeInfo<PreallocatedStorage>;
 template class ScopeInfo<ZoneListAllocationPolicy>;
 
 } }  // namespace v8::internal