1// Copyright 2011 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28#include <stdlib.h>
29
30#include "v8.h"
31
32#include "scopeinfo.h"
33#include "scopes.h"
34
35#include "allocation-inl.h"
36
37namespace v8 {
38namespace internal {
39
40
41Handle<ScopeInfo> ScopeInfo::Create(Scope* scope) {
42  // Collect stack and context locals.
43  ZoneList<Variable*> stack_locals(scope->StackLocalCount());
44  ZoneList<Variable*> context_locals(scope->ContextLocalCount());
45  scope->CollectStackAndContextLocals(&stack_locals, &context_locals);
46  const int stack_local_count = stack_locals.length();
47  const int context_local_count = context_locals.length();
48  // Make sure we allocate the correct amount.
49  ASSERT(scope->StackLocalCount() == stack_local_count);
50  ASSERT(scope->ContextLocalCount() == context_local_count);
51
52  // Determine use and location of the function variable if it is present.
53  FunctionVariableInfo function_name_info;
54  VariableMode function_variable_mode;
55  if (scope->is_function_scope() && scope->function() != NULL) {
56    Variable* var = scope->function()->var();
57    if (!var->is_used()) {
58      function_name_info = UNUSED;
59    } else if (var->IsContextSlot()) {
60      function_name_info = CONTEXT;
61    } else {
62      ASSERT(var->IsStackLocal());
63      function_name_info = STACK;
64    }
65    function_variable_mode = var->mode();
66  } else {
67    function_name_info = NONE;
68    function_variable_mode = VAR;
69  }
70
71  const bool has_function_name = function_name_info != NONE;
72  const int parameter_count = scope->num_parameters();
73  const int length = kVariablePartIndex
74      + parameter_count + stack_local_count + 2 * context_local_count
75      + (has_function_name ? 2 : 0);
76
77  Handle<ScopeInfo> scope_info = FACTORY->NewScopeInfo(length);
78
79  // Encode the flags.
80  int flags = TypeField::encode(scope->type()) |
81      CallsEvalField::encode(scope->calls_eval()) |
82      LanguageModeField::encode(scope->language_mode()) |
83      FunctionVariableField::encode(function_name_info) |
84      FunctionVariableMode::encode(function_variable_mode);
85  scope_info->SetFlags(flags);
86  scope_info->SetParameterCount(parameter_count);
87  scope_info->SetStackLocalCount(stack_local_count);
88  scope_info->SetContextLocalCount(context_local_count);
89
90  int index = kVariablePartIndex;
91  // Add parameters.
92  ASSERT(index == scope_info->ParameterEntriesIndex());
93  for (int i = 0; i < parameter_count; ++i) {
94    scope_info->set(index++, *scope->parameter(i)->name());
95  }
96
97  // Add stack locals' names. We are assuming that the stack locals'
98  // slots are allocated in increasing order, so we can simply add
99  // them to the ScopeInfo object.
100  ASSERT(index == scope_info->StackLocalEntriesIndex());
101  for (int i = 0; i < stack_local_count; ++i) {
102    ASSERT(stack_locals[i]->index() == i);
103    scope_info->set(index++, *stack_locals[i]->name());
104  }
105
106  // Due to usage analysis, context-allocated locals are not necessarily in
107  // increasing order: Some of them may be parameters which are allocated before
108  // the non-parameter locals. When the non-parameter locals are sorted
109  // according to usage, the allocated slot indices may not be in increasing
110  // order with the variable list anymore. Thus, we first need to sort them by
111  // context slot index before adding them to the ScopeInfo object.
112  context_locals.Sort(&Variable::CompareIndex);
113
114  // Add context locals' names.
115  ASSERT(index == scope_info->ContextLocalNameEntriesIndex());
116  for (int i = 0; i < context_local_count; ++i) {
117    scope_info->set(index++, *context_locals[i]->name());
118  }
119
120  // Add context locals' info.
121  ASSERT(index == scope_info->ContextLocalInfoEntriesIndex());
122  for (int i = 0; i < context_local_count; ++i) {
123    Variable* var = context_locals[i];
124    uint32_t value = ContextLocalMode::encode(var->mode()) |
125        ContextLocalInitFlag::encode(var->initialization_flag());
126    scope_info->set(index++, Smi::FromInt(value));
127  }
128
129  // If present, add the function variable name and its index.
130  ASSERT(index == scope_info->FunctionNameEntryIndex());
131  if (has_function_name) {
132    int var_index = scope->function()->var()->index();
133    scope_info->set(index++, *scope->function()->name());
134    scope_info->set(index++, Smi::FromInt(var_index));
135    ASSERT(function_name_info != STACK ||
136           (var_index == scope_info->StackLocalCount() &&
137            var_index == scope_info->StackSlotCount() - 1));
138    ASSERT(function_name_info != CONTEXT ||
139           var_index == scope_info->ContextLength() - 1);
140  }
141
142  ASSERT(index == scope_info->length());
143  ASSERT(scope->num_parameters() == scope_info->ParameterCount());
144  ASSERT(scope->num_stack_slots() == scope_info->StackSlotCount());
145  ASSERT(scope->num_heap_slots() == scope_info->ContextLength());
146  return scope_info;
147}
148
149
150ScopeInfo* ScopeInfo::Empty() {
151  return reinterpret_cast<ScopeInfo*>(HEAP->empty_fixed_array());
152}
153
154
155ScopeType ScopeInfo::Type() {
156  ASSERT(length() > 0);
157  return TypeField::decode(Flags());
158}
159
160
161bool ScopeInfo::CallsEval() {
162  return length() > 0 && CallsEvalField::decode(Flags());
163}
164
165
166LanguageMode ScopeInfo::language_mode() {
167  return length() > 0 ? LanguageModeField::decode(Flags()) : CLASSIC_MODE;
168}
169
170
171int ScopeInfo::LocalCount() {
172  return StackLocalCount() + ContextLocalCount();
173}
174
175
176int ScopeInfo::StackSlotCount() {
177  if (length() > 0) {
178    bool function_name_stack_slot =
179        FunctionVariableField::decode(Flags()) == STACK;
180    return StackLocalCount() + (function_name_stack_slot ? 1 : 0);
181  }
182  return 0;
183}
184
185
186int ScopeInfo::ContextLength() {
187  if (length() > 0) {
188    int context_locals = ContextLocalCount();
189    bool function_name_context_slot =
190        FunctionVariableField::decode(Flags()) == CONTEXT;
191    bool has_context = context_locals > 0 ||
192        function_name_context_slot ||
193        Type() == WITH_SCOPE ||
194        (Type() == FUNCTION_SCOPE && CallsEval());
195    if (has_context) {
196      return Context::MIN_CONTEXT_SLOTS + context_locals +
197          (function_name_context_slot ? 1 : 0);
198    }
199  }
200  return 0;
201}
202
203
204bool ScopeInfo::HasFunctionName() {
205  if (length() > 0) {
206    return NONE != FunctionVariableField::decode(Flags());
207  } else {
208    return false;
209  }
210}
211
212
213bool ScopeInfo::HasHeapAllocatedLocals() {
214  if (length() > 0) {
215    return ContextLocalCount() > 0;
216  } else {
217    return false;
218  }
219}
220
221
222bool ScopeInfo::HasContext() {
223  if (length() > 0) {
224    return ContextLength() > 0;
225  } else {
226    return false;
227  }
228}
229
230
231String* ScopeInfo::FunctionName() {
232  ASSERT(HasFunctionName());
233  return String::cast(get(FunctionNameEntryIndex()));
234}
235
236
237String* ScopeInfo::ParameterName(int var) {
238  ASSERT(0 <= var && var < ParameterCount());
239  int info_index = ParameterEntriesIndex() + var;
240  return String::cast(get(info_index));
241}
242
243
244String* ScopeInfo::LocalName(int var) {
245  ASSERT(0 <= var && var < LocalCount());
246  ASSERT(StackLocalEntriesIndex() + StackLocalCount() ==
247         ContextLocalNameEntriesIndex());
248  int info_index = StackLocalEntriesIndex() + var;
249  return String::cast(get(info_index));
250}
251
252
253String* ScopeInfo::StackLocalName(int var) {
254  ASSERT(0 <= var && var < StackLocalCount());
255  int info_index = StackLocalEntriesIndex() + var;
256  return String::cast(get(info_index));
257}
258
259
260String* ScopeInfo::ContextLocalName(int var) {
261  ASSERT(0 <= var && var < ContextLocalCount());
262  int info_index = ContextLocalNameEntriesIndex() + var;
263  return String::cast(get(info_index));
264}
265
266
267VariableMode ScopeInfo::ContextLocalMode(int var) {
268  ASSERT(0 <= var && var < ContextLocalCount());
269  int info_index = ContextLocalInfoEntriesIndex() + var;
270  int value = Smi::cast(get(info_index))->value();
271  return ContextLocalMode::decode(value);
272}
273
274
275InitializationFlag ScopeInfo::ContextLocalInitFlag(int var) {
276  ASSERT(0 <= var && var < ContextLocalCount());
277  int info_index = ContextLocalInfoEntriesIndex() + var;
278  int value = Smi::cast(get(info_index))->value();
279  return ContextLocalInitFlag::decode(value);
280}
281
282
283int ScopeInfo::StackSlotIndex(String* name) {
284  ASSERT(name->IsSymbol());
285  if (length() > 0) {
286    int start = StackLocalEntriesIndex();
287    int end = StackLocalEntriesIndex() + StackLocalCount();
288    for (int i = start; i < end; ++i) {
289      if (name == get(i)) {
290        return i - start;
291      }
292    }
293  }
294  return -1;
295}
296
297
298int ScopeInfo::ContextSlotIndex(String* name,
299                                VariableMode* mode,
300                                InitializationFlag* init_flag) {
301  ASSERT(name->IsSymbol());
302  ASSERT(mode != NULL);
303  ASSERT(init_flag != NULL);
304  if (length() > 0) {
305    ContextSlotCache* context_slot_cache = GetIsolate()->context_slot_cache();
306    int result = context_slot_cache->Lookup(this, name, mode, init_flag);
307    if (result != ContextSlotCache::kNotFound) {
308      ASSERT(result < ContextLength());
309      return result;
310    }
311
312    int start = ContextLocalNameEntriesIndex();
313    int end = ContextLocalNameEntriesIndex() + ContextLocalCount();
314    for (int i = start; i < end; ++i) {
315      if (name == get(i)) {
316        int var = i - start;
317        *mode = ContextLocalMode(var);
318        *init_flag = ContextLocalInitFlag(var);
319        result = Context::MIN_CONTEXT_SLOTS + var;
320        context_slot_cache->Update(this, name, *mode, *init_flag, result);
321        ASSERT(result < ContextLength());
322        return result;
323      }
324    }
325    context_slot_cache->Update(this, name, INTERNAL, kNeedsInitialization, -1);
326  }
327  return -1;
328}
329
330
331int ScopeInfo::ParameterIndex(String* name) {
332  ASSERT(name->IsSymbol());
333  if (length() > 0) {
334    // We must read parameters from the end since for
335    // multiply declared parameters the value of the
336    // last declaration of that parameter is used
337    // inside a function (and thus we need to look
338    // at the last index). Was bug# 1110337.
339    int start = ParameterEntriesIndex();
340    int end = ParameterEntriesIndex() + ParameterCount();
341    for (int i = end - 1; i >= start; --i) {
342      if (name == get(i)) {
343        return i - start;
344      }
345    }
346  }
347  return -1;
348}
349
350
351int ScopeInfo::FunctionContextSlotIndex(String* name, VariableMode* mode) {
352  ASSERT(name->IsSymbol());
353  ASSERT(mode != NULL);
354  if (length() > 0) {
355    if (FunctionVariableField::decode(Flags()) == CONTEXT &&
356        FunctionName() == name) {
357      *mode = FunctionVariableMode::decode(Flags());
358      return Smi::cast(get(FunctionNameEntryIndex() + 1))->value();
359    }
360  }
361  return -1;
362}
363
364
365int ScopeInfo::ParameterEntriesIndex() {
366  ASSERT(length() > 0);
367  return kVariablePartIndex;
368}
369
370
371int ScopeInfo::StackLocalEntriesIndex() {
372  return ParameterEntriesIndex() + ParameterCount();
373}
374
375
376int ScopeInfo::ContextLocalNameEntriesIndex() {
377  return StackLocalEntriesIndex() + StackLocalCount();
378}
379
380
381int ScopeInfo::ContextLocalInfoEntriesIndex() {
382  return ContextLocalNameEntriesIndex() + ContextLocalCount();
383}
384
385
386int ScopeInfo::FunctionNameEntryIndex() {
387  return ContextLocalInfoEntriesIndex() + ContextLocalCount();
388}
389
390
391int ContextSlotCache::Hash(Object* data, String* name) {
392  // Uses only lower 32 bits if pointers are larger.
393  uintptr_t addr_hash =
394      static_cast<uint32_t>(reinterpret_cast<uintptr_t>(data)) >> 2;
395  return static_cast<int>((addr_hash ^ name->Hash()) % kLength);
396}
397
398
399int ContextSlotCache::Lookup(Object* data,
400                             String* name,
401                             VariableMode* mode,
402                             InitializationFlag* init_flag) {
403  int index = Hash(data, name);
404  Key& key = keys_[index];
405  if ((key.data == data) && key.name->Equals(name)) {
406    Value result(values_[index]);
407    if (mode != NULL) *mode = result.mode();
408    if (init_flag != NULL) *init_flag = result.initialization_flag();
409    return result.index() + kNotFound;
410  }
411  return kNotFound;
412}
413
414
415void ContextSlotCache::Update(Object* data,
416                              String* name,
417                              VariableMode mode,
418                              InitializationFlag init_flag,
419                              int slot_index) {
420  String* symbol;
421  ASSERT(slot_index > kNotFound);
422  if (HEAP->LookupSymbolIfExists(name, &symbol)) {
423    int index = Hash(data, symbol);
424    Key& key = keys_[index];
425    key.data = data;
426    key.name = symbol;
427    // Please note value only takes a uint as index.
428    values_[index] = Value(mode, init_flag, slot_index - kNotFound).raw();
429#ifdef DEBUG
430    ValidateEntry(data, name, mode, init_flag, slot_index);
431#endif
432  }
433}
434
435
436void ContextSlotCache::Clear() {
437  for (int index = 0; index < kLength; index++) keys_[index].data = NULL;
438}
439
440
441#ifdef DEBUG
442
443void ContextSlotCache::ValidateEntry(Object* data,
444                                     String* name,
445                                     VariableMode mode,
446                                     InitializationFlag init_flag,
447                                     int slot_index) {
448  String* symbol;
449  if (HEAP->LookupSymbolIfExists(name, &symbol)) {
450    int index = Hash(data, name);
451    Key& key = keys_[index];
452    ASSERT(key.data == data);
453    ASSERT(key.name->Equals(name));
454    Value result(values_[index]);
455    ASSERT(result.mode() == mode);
456    ASSERT(result.initialization_flag() == init_flag);
457    ASSERT(result.index() + kNotFound == slot_index);
458  }
459}
460
461
462static void PrintList(const char* list_name,
463                      int nof_internal_slots,
464                      int start,
465                      int end,
466                      ScopeInfo* scope_info) {
467  if (start < end) {
468    PrintF("\n  // %s\n", list_name);
469    if (nof_internal_slots > 0) {
470      PrintF("  %2d - %2d [internal slots]\n", 0 , nof_internal_slots - 1);
471    }
472    for (int i = nof_internal_slots; start < end; ++i, ++start) {
473      PrintF("  %2d ", i);
474      String::cast(scope_info->get(start))->ShortPrint();
475      PrintF("\n");
476    }
477  }
478}
479
480
481void ScopeInfo::Print() {
482  PrintF("ScopeInfo ");
483  if (HasFunctionName()) {
484    FunctionName()->ShortPrint();
485  } else {
486    PrintF("/* no function name */");
487  }
488  PrintF("{");
489
490  PrintList("parameters", 0,
491            ParameterEntriesIndex(),
492            ParameterEntriesIndex() + ParameterCount(),
493            this);
494  PrintList("stack slots", 0,
495            StackLocalEntriesIndex(),
496            StackLocalEntriesIndex() + StackLocalCount(),
497            this);
498  PrintList("context slots",
499            Context::MIN_CONTEXT_SLOTS,
500            ContextLocalNameEntriesIndex(),
501            ContextLocalNameEntriesIndex() + ContextLocalCount(),
502            this);
503
504  PrintF("}\n");
505}
506#endif  // DEBUG
507
508} }  // namespace v8::internal
509