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