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