1// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_SCOPES_H_
6#define RUNTIME_VM_SCOPES_H_
7
8#include <limits>
9
10#include "platform/assert.h"
11#include "platform/globals.h"
12#include "vm/allocation.h"
13#include "vm/growable_array.h"
14#include "vm/object.h"
15#include "vm/raw_object.h"
16#include "vm/symbols.h"
17#include "vm/token.h"
18
19namespace dart {
20
21class CompileType;
22class LocalScope;
23class Slot;
24
25// Indices of [LocalVariable]s are abstract and have little todo with the
26// actual frame layout!
27//
28// There are generally 4 different kinds of [LocalVariable]s:
29//
30// a) [LocalVariable]s refering to a parameter: The indices for those
31// variables are assigned by the flow graph builder. Parameter n gets
32// assigned the index (function.num_parameters - n - 1). I.e. the last
33// parameter has index 1.
34//
35// b) [LocalVariable]s referring to actual variables in the body of a
36// function (either from Dart code or specially injected ones. The
37// indices of those variables are assigned by the scope builder
38// from 0, -1, ... -(M-1) for M local variables.
39//
40// -> These variables participate in full SSA renaming and can therefore
41// be used with [StoreLocalInstr]s (in addition to [LoadLocal]s).
42//
43// c) [LocalVariable]s referring to values on the expression stack. Those are
44// assigned by the flow graph builder. The indices of those variables are
45// assigned by the flow graph builder (it simulates the expression stack
46// height), they go from -NumVariables - ExpressionHeight.
47//
48// -> These variables participate only partially in SSA renaming and can
49// therefore only be used with [LoadLocalInstr]s and with
50// [StoreLocalInstr]s **where no phis are necessary**.
51//
52// b) [LocalVariable]s referring to captured variables. Those are never
53// loaded/stored directly. Their only purpose is to tell the flow graph
54// builder how many parent links to follow and into which context index to
55// store. The indices of those variables are assigned by the scope
56// builder and they refer to indices into context objects.
57class VariableIndex {
58 public:
59 static const int kInvalidIndex = std::numeric_limits<int>::min();
60
61 explicit VariableIndex(int value = kInvalidIndex) : value_(value) {}
62
63 bool operator==(const VariableIndex& other) { return value_ == other.value_; }
64
65 bool IsValid() const { return value_ != kInvalidIndex; }
66
67 int value() const { return value_; }
68
69 private:
70 int value_;
71};
72
73class LocalVariable : public ZoneAllocated {
74 public:
75 LocalVariable(TokenPosition declaration_pos,
76 TokenPosition token_pos,
77 const String& name,
78 const AbstractType& type,
79 CompileType* parameter_type = nullptr,
80 const Object* parameter_value = nullptr)
81 : declaration_pos_(declaration_pos),
82 token_pos_(token_pos),
83 name_(name),
84 owner_(NULL),
85 type_(type),
86 parameter_type_(parameter_type),
87 parameter_value_(parameter_value),
88 const_value_(NULL),
89 is_final_(false),
90 is_captured_(false),
91 is_invisible_(false),
92 is_captured_parameter_(false),
93 is_forced_stack_(false),
94 is_explicit_covariant_parameter_(false),
95 is_late_(false),
96 is_chained_future_(false),
97 expected_context_index_(-1),
98 late_init_offset_(0),
99 type_check_mode_(kDoTypeCheck),
100 index_() {
101 ASSERT(type.IsZoneHandle() || type.IsReadOnlyHandle());
102 ASSERT(type.IsFinalized());
103 ASSERT(name.IsSymbol());
104 }
105
106 TokenPosition token_pos() const { return token_pos_; }
107 TokenPosition declaration_token_pos() const { return declaration_pos_; }
108 const String& name() const { return name_; }
109 LocalScope* owner() const { return owner_; }
110 void set_owner(LocalScope* owner) {
111 ASSERT(owner_ == NULL);
112 owner_ = owner;
113 }
114
115 const AbstractType& type() const { return type_; }
116
117 CompileType* parameter_type() const { return parameter_type_; }
118 const Object* parameter_value() const { return parameter_value_; }
119
120 bool is_final() const { return is_final_; }
121 void set_is_final() { is_final_ = true; }
122
123 bool is_captured() const { return is_captured_; }
124 void set_is_captured() { is_captured_ = true; }
125
126 // Variables marked as forced to stack are skipped and not captured by
127 // CaptureLocalVariables - which iterates scope chain between two scopes
128 // and indiscriminately marks all variables as captured.
129 // TODO(27590) remove the hardcoded list of names from CaptureLocalVariables
130 bool is_forced_stack() const { return is_forced_stack_; }
131 void set_is_forced_stack() { is_forced_stack_ = true; }
132
133 bool is_late() const { return is_late_; }
134 void set_is_late() { is_late_ = true; }
135
136 bool is_chained_future() const { return is_chained_future_; }
137 void set_is_chained_future() { is_chained_future_ = true; }
138
139 intptr_t expected_context_index() const { return expected_context_index_; }
140 void set_expected_context_index(int index) {
141 expected_context_index_ = index;
142 }
143
144 intptr_t late_init_offset() const { return late_init_offset_; }
145 void set_late_init_offset(intptr_t late_init_offset) {
146 late_init_offset_ = late_init_offset;
147 }
148
149 bool is_explicit_covariant_parameter() const {
150 return is_explicit_covariant_parameter_;
151 }
152 void set_is_explicit_covariant_parameter() {
153 is_explicit_covariant_parameter_ = true;
154 }
155
156 enum TypeCheckMode {
157 kDoTypeCheck,
158 kSkipTypeCheck,
159 kTypeCheckedByCaller,
160 };
161
162 // Returns true if this local variable represents a parameter that needs type
163 // check when we enter the function.
164 bool needs_type_check() const { return (type_check_mode_ == kDoTypeCheck); }
165
166 // Returns true if this local variable represents a parameter which type is
167 // guaranteed by the caller.
168 bool was_type_checked_by_caller() const {
169 return type_check_mode_ == kTypeCheckedByCaller;
170 }
171
172 TypeCheckMode type_check_mode() const { return type_check_mode_; }
173 void set_type_check_mode(TypeCheckMode mode) { type_check_mode_ = mode; }
174
175 bool HasIndex() const { return index_.IsValid(); }
176 VariableIndex index() const {
177 ASSERT(HasIndex());
178 return index_;
179 }
180
181 // Assign an index to a local.
182 void set_index(VariableIndex index) {
183 ASSERT(index.IsValid());
184 index_ = index;
185 }
186
187 void set_invisible(bool value) { is_invisible_ = value; }
188 bool is_invisible() const { return is_invisible_; }
189
190 bool is_captured_parameter() const { return is_captured_parameter_; }
191 void set_is_captured_parameter(bool value) { is_captured_parameter_ = value; }
192
193 // By convention, internal variables start with a colon.
194 bool IsInternal() const { return name_.CharAt(0) == ':'; }
195
196 bool IsConst() const { return const_value_ != NULL; }
197
198 void SetConstValue(const Instance& value) {
199 ASSERT(value.IsZoneHandle() || value.IsReadOnlyHandle());
200 const_value_ = &value;
201 }
202
203 const Instance* ConstValue() const {
204 ASSERT(IsConst());
205 return const_value_;
206 }
207
208 bool Equals(const LocalVariable& other) const;
209
210 private:
211 static const int kUninitializedIndex = INT_MIN;
212
213 const TokenPosition declaration_pos_;
214 const TokenPosition token_pos_;
215 const String& name_;
216 LocalScope* owner_; // Local scope declaring this variable.
217
218 const AbstractType& type_; // Declaration type of local variable.
219
220 CompileType* const parameter_type_; // NULL or incoming parameter type.
221 const Object* parameter_value_; // NULL or incoming parameter value.
222
223 const Instance* const_value_; // NULL or compile-time const value.
224
225 bool is_final_; // If true, this variable is readonly.
226 bool is_captured_; // If true, this variable lives in the context, otherwise
227 // in the stack frame.
228 bool is_invisible_;
229 bool is_captured_parameter_;
230 bool is_forced_stack_;
231 bool is_explicit_covariant_parameter_;
232 bool is_late_;
233 bool is_chained_future_;
234 intptr_t expected_context_index_;
235 intptr_t late_init_offset_;
236 TypeCheckMode type_check_mode_;
237 VariableIndex index_;
238
239 friend class LocalScope;
240 DISALLOW_COPY_AND_ASSIGN(LocalVariable);
241};
242
243// Accumulates local variable descriptors while building
244// LocalVarDescriptors object.
245class LocalVarDescriptorsBuilder : public ValueObject {
246 public:
247 struct VarDesc {
248 const String* name;
249 LocalVarDescriptorsLayout::VarInfo info;
250 };
251
252 LocalVarDescriptorsBuilder() : vars_(8) {}
253
254 // Add variable descriptor.
255 void Add(const VarDesc& var_desc) { vars_.Add(var_desc); }
256
257 // Add all variable descriptors from given [LocalVarDescriptors] object.
258 void AddAll(Zone* zone, const LocalVarDescriptors& var_descs);
259
260 // Record deopt-id -> context-level mappings, using ranges of deopt-ids with
261 // the same context-level. [context_level_array] contains (deopt_id,
262 // context_level) tuples.
263 void AddDeoptIdToContextLevelMappings(
264 ZoneGrowableArray<intptr_t>* context_level_array);
265
266 // Finish building LocalVarDescriptor object.
267 LocalVarDescriptorsPtr Done();
268
269 private:
270 GrowableArray<VarDesc> vars_;
271};
272
273class NameReference : public ZoneAllocated {
274 public:
275 NameReference(TokenPosition token_pos, const String& name)
276 : token_pos_(token_pos), name_(name) {
277 ASSERT(name.IsSymbol());
278 }
279 const String& name() const { return name_; }
280 TokenPosition token_pos() const { return token_pos_; }
281 void set_token_pos(TokenPosition value) { token_pos_ = value; }
282
283 private:
284 TokenPosition token_pos_;
285 const String& name_;
286};
287
288class SourceLabel : public ZoneAllocated {
289 public:
290 enum Kind {
291 kFor,
292 kWhile,
293 kDoWhile,
294 kSwitch,
295 kCase,
296 kTry,
297 kCatch,
298 kForward,
299 kStatement // Any statement other than the above
300 };
301
302 SourceLabel(TokenPosition token_pos, const String& name, Kind kind)
303 : token_pos_(token_pos), name_(name), owner_(NULL), kind_(kind) {
304 ASSERT(name.IsSymbol());
305 }
306
307 static SourceLabel* New(TokenPosition token_pos, String* name, Kind kind) {
308 if (name != NULL) {
309 return new SourceLabel(token_pos, *name, kind);
310 } else {
311 return new SourceLabel(token_pos, Symbols::DefaultLabel(), kind);
312 }
313 }
314
315 TokenPosition token_pos() const { return token_pos_; }
316 const String& name() const { return name_; }
317 LocalScope* owner() const { return owner_; }
318 void set_owner(LocalScope* owner) { owner_ = owner; }
319
320 Kind kind() const { return kind_; }
321
322 // Returns the function level of the scope in which the label is defined.
323 int FunctionLevel() const;
324
325 bool IsUnresolved() { return kind_ == kForward; }
326 void ResolveForwardReference() { kind_ = kCase; }
327
328 private:
329 const TokenPosition token_pos_;
330 const String& name_;
331 LocalScope* owner_; // Local scope declaring this label.
332
333 Kind kind_;
334
335 DISALLOW_COPY_AND_ASSIGN(SourceLabel);
336};
337
338class LocalScope : public ZoneAllocated {
339 public:
340 LocalScope(LocalScope* parent, int function_level, int loop_level);
341
342 LocalScope* parent() const { return parent_; }
343 LocalScope* child() const { return child_; }
344 LocalScope* sibling() const { return sibling_; }
345 int function_level() const { return function_level_; }
346 int loop_level() const { return loop_level_; }
347
348 // Check if this scope is nested within the passed in scope.
349 bool IsNestedWithin(LocalScope* scope) const;
350
351 // The context level is only set in a scope that is either the owner scope of
352 // a captured variable or that is the owner scope of a context.
353 bool HasContextLevel() const {
354 return context_level_ != kUninitializedContextLevel;
355 }
356 int context_level() const {
357 ASSERT(HasContextLevel());
358 return context_level_;
359 }
360 void set_context_level(int context_level) {
361 ASSERT(!HasContextLevel());
362 ASSERT(context_level != kUninitializedContextLevel);
363 context_level_ = context_level;
364 }
365
366 TokenPosition begin_token_pos() const { return begin_token_pos_; }
367 void set_begin_token_pos(TokenPosition value) { begin_token_pos_ = value; }
368
369 TokenPosition end_token_pos() const { return end_token_pos_; }
370 void set_end_token_pos(TokenPosition value) { end_token_pos_ = value; }
371
372 // Return the list of variables allocated in the context and belonging to this
373 // scope and to its children at the same loop level.
374 const GrowableArray<LocalVariable*>& context_variables() const {
375 return context_variables_;
376 }
377
378 const ZoneGrowableArray<const Slot*>& context_slots() const {
379 return *context_slots_;
380 }
381
382 // The number of variables allocated in the context and belonging to this
383 // scope and to its children at the same loop level.
384 int num_context_variables() const { return context_variables().length(); }
385
386 // Add a variable to the scope. Returns false if a variable with the
387 // same name is already present.
388 bool AddVariable(LocalVariable* variable);
389
390 // Add a variable to the scope as a context allocated variable and assigns
391 // it an index within the context. Does not check if the scope already
392 // contains this variable or a variable with the same name.
393 void AddContextVariable(LocalVariable* var);
394
395 // Insert a formal parameter variable to the scope at the given position,
396 // possibly in front of aliases already added with AddVariable.
397 // Returns false if a variable with the same name is already present.
398 bool InsertParameterAt(intptr_t pos, LocalVariable* parameter);
399
400 // Add a label to the scope. Returns false if a label with the same name
401 // is already present.
402 bool AddLabel(SourceLabel* label);
403
404 // Move an unresolved label of a switch case label to an outer switch.
405 void MoveLabel(SourceLabel* label);
406
407 // Lookup a variable in this scope only.
408 LocalVariable* LocalLookupVariable(const String& name) const;
409
410 // Lookup a label in this scope only.
411 SourceLabel* LocalLookupLabel(const String& name) const;
412
413 // Lookup a variable in this scope and its parents. If the variable
414 // is found in a parent scope and 'test_only' is not true, we insert
415 // aliases of the variable in the current and intermediate scopes up to
416 // the declaration scope in order to detect "used before declared" errors.
417 // We mark a variable as 'captured' when applicable.
418 LocalVariable* LookupVariable(const String& name, bool test_only);
419
420 // Lookup a label in this scope and its parents.
421 SourceLabel* LookupLabel(const String& name);
422
423 // Lookup the "innermost" label that labels a for, while, do, or switch
424 // statement.
425 SourceLabel* LookupInnermostLabel(Token::Kind jump_kind);
426
427 // Lookup scope of outer switch statement at same function level.
428 // Returns NULL if this scope is not embedded in a switch.
429 LocalScope* LookupSwitchScope();
430
431 // Mark this variable as captured by this scope.
432 void CaptureVariable(LocalVariable* variable);
433
434 // Look for unresolved forward references to labels in this scope.
435 // If there are any, propagate the forward reference to the next
436 // outer scope of a switch statement. If there is no outer switch
437 // statement, return the first unresolved label found.
438 SourceLabel* CheckUnresolvedLabels();
439
440 // Accessing the variables in the scope.
441 intptr_t num_variables() const { return variables_.length(); }
442 LocalVariable* VariableAt(intptr_t index) const {
443 ASSERT((index >= 0) && (index < variables_.length()));
444 return variables_[index];
445 }
446
447 // Count the captured variables belonging to outer scopes and referenced in
448 // this local scope.
449 int NumCapturedVariables() const;
450
451 // Add a reference to the given name into this scope and the enclosing
452 // scopes that do not have a local variable declaration for this name
453 // already.
454 void AddReferencedName(TokenPosition token_pos, const String& name);
455 TokenPosition PreviousReferencePos(const String& name) const;
456
457 // Allocate both captured and non-captured variables declared in this scope
458 // and in its children scopes of the same function level. Allocating means
459 // assigning a frame slot index or a context slot index.
460 // Parameters to be allocated in the frame must all appear in the top scope
461 // and not in its children (we do not yet handle register parameters).
462 // Locals must be listed after parameters in top scope and in its children.
463 // Two locals in different sibling scopes may share the same frame slot.
464 //
465 // Return the index of the next available frame slot.
466 VariableIndex AllocateVariables(VariableIndex first_parameter_index,
467 int num_parameters,
468 VariableIndex first_local_index,
469 LocalScope* context_owner,
470 bool* found_captured_variables);
471
472 // Creates variable info for the scope and all its nested scopes.
473 // Must be called after AllocateVariables() has been called.
474 LocalVarDescriptorsPtr GetVarDescriptors(
475 const Function& func,
476 ZoneGrowableArray<intptr_t>* context_level_array);
477
478 // Create a ContextScope object describing all captured variables referenced
479 // from this scope and belonging to outer scopes.
480 ContextScopePtr PreserveOuterScope(int current_context_level) const;
481
482 // Mark all local variables that are accessible from this scope up to
483 // top_scope (included) as captured unless they are marked as forced to stack.
484 void CaptureLocalVariables(LocalScope* top_scope);
485
486 // Creates a LocalScope representing the outer scope of a local function to be
487 // compiled. This outer scope contains the variables captured by the function
488 // as specified by the given ContextScope, which was created during the
489 // compilation of the enclosing function.
490 static LocalScope* RestoreOuterScope(const ContextScope& context_scope);
491
492 // Create a ContextScope object which will capture "this" for an implicit
493 // closure object.
494 static ContextScopePtr CreateImplicitClosureScope(const Function& func);
495
496 private:
497 // Allocate the variable in the current context, possibly updating the current
498 // context owner scope, if the variable is the first one to be allocated at
499 // this loop level.
500 // The variable may belong to this scope or to any of its children, but at the
501 // same loop level.
502 void AllocateContextVariable(LocalVariable* variable,
503 LocalScope** context_owner);
504
505 void CollectLocalVariables(LocalVarDescriptorsBuilder* vars,
506 int16_t* scope_id);
507
508 NameReference* FindReference(const String& name) const;
509
510 static const int kUninitializedContextLevel = INT_MIN;
511 LocalScope* parent_;
512 LocalScope* child_;
513 LocalScope* sibling_;
514 int function_level_; // Reflects the nesting level of local functions.
515 int loop_level_; // Reflects the loop nesting level.
516 int context_level_; // Reflects the level of the runtime context.
517 TokenPosition begin_token_pos_; // Token index of beginning of scope.
518 TokenPosition end_token_pos_; // Token index of end of scope.
519 GrowableArray<LocalVariable*> variables_;
520 GrowableArray<SourceLabel*> labels_;
521
522 // List of variables allocated into the context which is owned by this scope,
523 // and their corresponding Slots.
524 GrowableArray<LocalVariable*> context_variables_;
525 ZoneGrowableArray<const Slot*>* context_slots_;
526
527 // List of names referenced in this scope and its children that
528 // are not resolved to local variables.
529 GrowableArray<NameReference*> referenced_;
530
531 DISALLOW_COPY_AND_ASSIGN(LocalScope);
532};
533
534} // namespace dart
535
536#endif // RUNTIME_VM_SCOPES_H_
537