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