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 33namespace v8 { 34namespace internal { 35 36 37// This class implements the following abstract grammar of interfaces 38// (i.e. module types): 39// interface ::= UNDETERMINED | VALUE | CONST | MODULE(exports) 40// exports ::= {name : interface, ...} 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. 44// Undetermined types are unification variables that can be unified freely. 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. 56 57class Interface : public ZoneObject { 58 public: 59 // --------------------------------------------------------------------------- 60 // Factory methods. 61 62 static Interface* NewUnknown(Zone* zone) { 63 return new(zone) Interface(NONE); 64 } 65 66 static Interface* NewValue() { 67 static Interface value_interface(VALUE + FROZEN); // Cached. 68 return &value_interface; 69 } 70 71 static Interface* NewConst() { 72 static Interface value_interface(VALUE + CONST + FROZEN); // Cached. 73 return &value_interface; 74 } 75 76 static Interface* NewModule(Zone* zone) { 77 return new(zone) Interface(MODULE); 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. 85 void Add(Handle<String> name, Interface* interface, Zone* zone, bool* ok) { 86 DoAdd(name.location(), name->Hash(), interface, zone, ok); 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. 91 void Unify(Interface* that, Zone* zone, bool* ok); 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 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 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 117 // Assign an index. 118 void Allocate(int index) { 119 ASSERT(IsModule() && IsFrozen() && Chase()->index_ == -1); 120 Chase()->index_ = index; 121 } 122 123 // --------------------------------------------------------------------------- 124 // Accessors. 125 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 132 // Check whether this is a constant type. 133 bool IsConst() { return Chase()->flags_ & CONST; } 134 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 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 } 158 159 // Look up an exported name. Returns NULL if not (yet) defined. 160 Interface* Lookup(Handle<String> name, Zone* zone); 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 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 205 CONST = 2, // This type describes a constant 206 MODULE = 4, // This type describes a module 207 FROZEN = 8 // This type is fully determined 208 }; 209 210 int flags_; 211 Interface* forward_; // Unification link 212 ZoneHashMap* exports_; // Module exports and their types (allocated lazily) 213 int index_; 214 215 explicit Interface(int flags) 216 : flags_(flags), 217 forward_(NULL), 218 exports_(NULL), 219 index_(-1) { 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 233 void DoAdd(void* name, uint32_t hash, Interface* interface, Zone* zone, 234 bool* ok); 235 void DoUnify(Interface* that, bool* ok, Zone* zone); 236}; 237 238} } // namespace v8::internal 239 240#endif // V8_INTERFACE_H_ 241