1// Copyright 2012 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef V8_INTERFACE_H_
6#define V8_INTERFACE_H_
7
8#include "src/zone-inl.h"  // For operator new.
9
10namespace v8 {
11namespace internal {
12
13
14// This class implements the following abstract grammar of interfaces
15// (i.e. module types):
16//   interface ::= UNDETERMINED | VALUE | CONST | MODULE(exports)
17//   exports ::= {name : interface, ...}
18// A frozen type is one that is fully determined. Unification does not
19// allow to turn non-const values into const, or adding additional exports to
20// frozen interfaces. Otherwise, unifying modules merges their exports.
21// Undetermined types are unification variables that can be unified freely.
22// There is a natural subsort lattice that reflects the increase of knowledge:
23//
24//            undetermined
25//           //     |    \\                                                    .
26//       value  (frozen)  module
27//      //   \\  /    \  //
28//  const   fr.value  fr.module
29//      \\    /
30//     fr.const
31//
32// where the bold lines are the only transitions allowed.
33
34class Interface : public ZoneObject {
35 public:
36  // ---------------------------------------------------------------------------
37  // Factory methods.
38
39  static Interface* NewUnknown(Zone* zone) {
40    return new(zone) Interface(NONE);
41  }
42
43  static Interface* NewValue() {
44    static Interface value_interface(VALUE + FROZEN);  // Cached.
45    return &value_interface;
46  }
47
48  static Interface* NewConst() {
49    static Interface value_interface(VALUE + CONST + FROZEN);  // Cached.
50    return &value_interface;
51  }
52
53  static Interface* NewModule(Zone* zone) {
54    return new(zone) Interface(MODULE);
55  }
56
57  // ---------------------------------------------------------------------------
58  // Mutators.
59
60  // Add a name to the list of exports. If it already exists, unify with
61  // interface, otherwise insert unless this is closed.
62  void Add(Handle<String> name, Interface* interface, Zone* zone, bool* ok) {
63    DoAdd(name.location(), name->Hash(), interface, zone, ok);
64  }
65
66  // Unify with another interface. If successful, both interface objects will
67  // represent the same type, and changes to one are reflected in the other.
68  void Unify(Interface* that, Zone* zone, bool* ok);
69
70  // Determine this interface to be a value interface.
71  void MakeValue(bool* ok) {
72    *ok = !IsModule();
73    if (*ok) Chase()->flags_ |= VALUE;
74  }
75
76  // Determine this interface to be an immutable interface.
77  void MakeConst(bool* ok) {
78    *ok = !IsModule() && (IsConst() || !IsFrozen());
79    if (*ok) Chase()->flags_ |= VALUE + CONST;
80  }
81
82  // Determine this interface to be a module interface.
83  void MakeModule(bool* ok) {
84    *ok = !IsValue();
85    if (*ok) Chase()->flags_ |= MODULE;
86  }
87
88  // Do not allow any further refinements, directly or through unification.
89  void Freeze(bool* ok) {
90    *ok = IsValue() || IsModule();
91    if (*ok) Chase()->flags_ |= FROZEN;
92  }
93
94  // Assign an index.
95  void Allocate(int index) {
96    ASSERT(IsModule() && IsFrozen() && Chase()->index_ == -1);
97    Chase()->index_ = index;
98  }
99
100  // ---------------------------------------------------------------------------
101  // Accessors.
102
103  // Check whether this is still a fully undetermined type.
104  bool IsUnknown() { return Chase()->flags_ == NONE; }
105
106  // Check whether this is a value type.
107  bool IsValue() { return Chase()->flags_ & VALUE; }
108
109  // Check whether this is a constant type.
110  bool IsConst() { return Chase()->flags_ & CONST; }
111
112  // Check whether this is a module type.
113  bool IsModule() { return Chase()->flags_ & MODULE; }
114
115  // Check whether this is closed (i.e. fully determined).
116  bool IsFrozen() { return Chase()->flags_ & FROZEN; }
117
118  bool IsUnified(Interface* that) {
119    return Chase() == that->Chase()
120        || (this->IsValue() == that->IsValue() &&
121            this->IsConst() == that->IsConst());
122  }
123
124  int Length() {
125    ASSERT(IsModule() && IsFrozen());
126    ZoneHashMap* exports = Chase()->exports_;
127    return exports ? exports->occupancy() : 0;
128  }
129
130  // The context slot in the hosting global context pointing to this module.
131  int Index() {
132    ASSERT(IsModule() && IsFrozen());
133    return Chase()->index_;
134  }
135
136  // Look up an exported name. Returns NULL if not (yet) defined.
137  Interface* Lookup(Handle<String> name, Zone* zone);
138
139  // ---------------------------------------------------------------------------
140  // Iterators.
141
142  // Use like:
143  //   for (auto it = interface->iterator(); !it.done(); it.Advance()) {
144  //     ... it.name() ... it.interface() ...
145  //   }
146  class Iterator {
147   public:
148    bool done() const { return entry_ == NULL; }
149    Handle<String> name() const {
150      ASSERT(!done());
151      return Handle<String>(*static_cast<String**>(entry_->key));
152    }
153    Interface* interface() const {
154      ASSERT(!done());
155      return static_cast<Interface*>(entry_->value);
156    }
157    void Advance() { entry_ = exports_->Next(entry_); }
158
159   private:
160    friend class Interface;
161    explicit Iterator(const ZoneHashMap* exports)
162        : exports_(exports), entry_(exports ? exports->Start() : NULL) {}
163
164    const ZoneHashMap* exports_;
165    ZoneHashMap::Entry* entry_;
166  };
167
168  Iterator iterator() const { return Iterator(this->exports_); }
169
170  // ---------------------------------------------------------------------------
171  // Debugging.
172#ifdef DEBUG
173  void Print(int n = 0);  // n = indentation; n < 0 => don't print recursively
174#endif
175
176  // ---------------------------------------------------------------------------
177  // Implementation.
178 private:
179  enum Flags {    // All flags are monotonic
180    NONE = 0,
181    VALUE = 1,    // This type describes a value
182    CONST = 2,    // This type describes a constant
183    MODULE = 4,   // This type describes a module
184    FROZEN = 8    // This type is fully determined
185  };
186
187  int flags_;
188  Interface* forward_;     // Unification link
189  ZoneHashMap* exports_;   // Module exports and their types (allocated lazily)
190  int index_;
191
192  explicit Interface(int flags)
193    : flags_(flags),
194      forward_(NULL),
195      exports_(NULL),
196      index_(-1) {
197#ifdef DEBUG
198    if (FLAG_print_interface_details)
199      PrintF("# Creating %p\n", static_cast<void*>(this));
200#endif
201  }
202
203  Interface* Chase() {
204    Interface* result = this;
205    while (result->forward_ != NULL) result = result->forward_;
206    if (result != this) forward_ = result;  // On-the-fly path compression.
207    return result;
208  }
209
210  void DoAdd(void* name, uint32_t hash, Interface* interface, Zone* zone,
211             bool* ok);
212  void DoUnify(Interface* that, bool* ok, Zone* zone);
213};
214
215} }  // namespace v8::internal
216
217#endif  // V8_INTERFACE_H_
218