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#include "v8.h" 29 30#include "interface.h" 31 32namespace v8 { 33namespace internal { 34 35static bool Match(void* key1, void* key2) { 36 String* name1 = *static_cast<String**>(key1); 37 String* name2 = *static_cast<String**>(key2); 38 ASSERT(name1->IsInternalizedString()); 39 ASSERT(name2->IsInternalizedString()); 40 return name1 == name2; 41} 42 43 44Interface* Interface::Lookup(Handle<String> name, Zone* zone) { 45 ASSERT(IsModule()); 46 ZoneHashMap* map = Chase()->exports_; 47 if (map == NULL) return NULL; 48 ZoneAllocationPolicy allocator(zone); 49 ZoneHashMap::Entry* p = map->Lookup(name.location(), name->Hash(), false, 50 allocator); 51 if (p == NULL) return NULL; 52 ASSERT(*static_cast<String**>(p->key) == *name); 53 ASSERT(p->value != NULL); 54 return static_cast<Interface*>(p->value); 55} 56 57 58#ifdef DEBUG 59// Current nesting depth for debug output. 60class Nesting { 61 public: 62 Nesting() { current_ += 2; } 63 ~Nesting() { current_ -= 2; } 64 static int current() { return current_; } 65 private: 66 static int current_; 67}; 68 69int Nesting::current_ = 0; 70#endif 71 72 73void Interface::DoAdd( 74 void* name, uint32_t hash, Interface* interface, Zone* zone, bool* ok) { 75 MakeModule(ok); 76 if (!*ok) return; 77 78#ifdef DEBUG 79 if (FLAG_print_interface_details) { 80 PrintF("%*s# Adding...\n", Nesting::current(), ""); 81 PrintF("%*sthis = ", Nesting::current(), ""); 82 this->Print(Nesting::current()); 83 PrintF("%*s%s : ", Nesting::current(), "", 84 (*static_cast<String**>(name))->ToAsciiArray()); 85 interface->Print(Nesting::current()); 86 } 87#endif 88 89 ZoneHashMap** map = &Chase()->exports_; 90 ZoneAllocationPolicy allocator(zone); 91 92 if (*map == NULL) 93 *map = new ZoneHashMap(Match, ZoneHashMap::kDefaultHashMapCapacity, 94 allocator); 95 96 ZoneHashMap::Entry* p = (*map)->Lookup(name, hash, !IsFrozen(), allocator); 97 if (p == NULL) { 98 // This didn't have name but was frozen already, that's an error. 99 *ok = false; 100 } else if (p->value == NULL) { 101 p->value = interface; 102 } else { 103#ifdef DEBUG 104 Nesting nested; 105#endif 106 static_cast<Interface*>(p->value)->Unify(interface, zone, ok); 107 } 108 109#ifdef DEBUG 110 if (FLAG_print_interface_details) { 111 PrintF("%*sthis' = ", Nesting::current(), ""); 112 this->Print(Nesting::current()); 113 PrintF("%*s# Added.\n", Nesting::current(), ""); 114 } 115#endif 116} 117 118 119void Interface::Unify(Interface* that, Zone* zone, bool* ok) { 120 if (this->forward_) return this->Chase()->Unify(that, zone, ok); 121 if (that->forward_) return this->Unify(that->Chase(), zone, ok); 122 ASSERT(this->forward_ == NULL); 123 ASSERT(that->forward_ == NULL); 124 125 *ok = true; 126 if (this == that) return; 127 if (this->IsValue()) { 128 that->MakeValue(ok); 129 if (*ok && this->IsConst()) that->MakeConst(ok); 130 return; 131 } 132 if (that->IsValue()) { 133 this->MakeValue(ok); 134 if (*ok && that->IsConst()) this->MakeConst(ok); 135 return; 136 } 137 138#ifdef DEBUG 139 if (FLAG_print_interface_details) { 140 PrintF("%*s# Unifying...\n", Nesting::current(), ""); 141 PrintF("%*sthis = ", Nesting::current(), ""); 142 this->Print(Nesting::current()); 143 PrintF("%*sthat = ", Nesting::current(), ""); 144 that->Print(Nesting::current()); 145 } 146#endif 147 148 // Merge the smaller interface into the larger, for performance. 149 if (this->exports_ != NULL && (that->exports_ == NULL || 150 this->exports_->occupancy() >= that->exports_->occupancy())) { 151 this->DoUnify(that, ok, zone); 152 } else { 153 that->DoUnify(this, ok, zone); 154 } 155 156#ifdef DEBUG 157 if (FLAG_print_interface_details) { 158 PrintF("%*sthis' = ", Nesting::current(), ""); 159 this->Print(Nesting::current()); 160 PrintF("%*sthat' = ", Nesting::current(), ""); 161 that->Print(Nesting::current()); 162 PrintF("%*s# Unified.\n", Nesting::current(), ""); 163 } 164#endif 165} 166 167 168void Interface::DoUnify(Interface* that, bool* ok, Zone* zone) { 169 ASSERT(this->forward_ == NULL); 170 ASSERT(that->forward_ == NULL); 171 ASSERT(!this->IsValue()); 172 ASSERT(!that->IsValue()); 173 ASSERT(this->index_ == -1); 174 ASSERT(that->index_ == -1); 175 ASSERT(*ok); 176 177#ifdef DEBUG 178 Nesting nested; 179#endif 180 181 // Try to merge all members from that into this. 182 ZoneHashMap* map = that->exports_; 183 if (map != NULL) { 184 for (ZoneHashMap::Entry* p = map->Start(); p != NULL; p = map->Next(p)) { 185 this->DoAdd(p->key, p->hash, static_cast<Interface*>(p->value), zone, ok); 186 if (!*ok) return; 187 } 188 } 189 190 // If the new interface is larger than that's, then there were members in 191 // 'this' which 'that' didn't have. If 'that' was frozen that is an error. 192 int this_size = this->exports_ == NULL ? 0 : this->exports_->occupancy(); 193 int that_size = map == NULL ? 0 : map->occupancy(); 194 if (that->IsFrozen() && this_size > that_size) { 195 *ok = false; 196 return; 197 } 198 199 // Merge interfaces. 200 this->flags_ |= that->flags_; 201 that->forward_ = this; 202} 203 204 205#ifdef DEBUG 206void Interface::Print(int n) { 207 int n0 = n > 0 ? n : 0; 208 209 if (FLAG_print_interface_details) { 210 PrintF("%p", static_cast<void*>(this)); 211 for (Interface* link = this->forward_; link != NULL; link = link->forward_) 212 PrintF("->%p", static_cast<void*>(link)); 213 PrintF(" "); 214 } 215 216 if (IsUnknown()) { 217 PrintF("unknown\n"); 218 } else if (IsConst()) { 219 PrintF("const\n"); 220 } else if (IsValue()) { 221 PrintF("value\n"); 222 } else if (IsModule()) { 223 PrintF("module %d %s{", Index(), IsFrozen() ? "" : "(unresolved) "); 224 ZoneHashMap* map = Chase()->exports_; 225 if (map == NULL || map->occupancy() == 0) { 226 PrintF("}\n"); 227 } else if (n < 0 || n0 >= 2 * FLAG_print_interface_depth) { 228 // Avoid infinite recursion on cyclic types. 229 PrintF("...}\n"); 230 } else { 231 PrintF("\n"); 232 for (ZoneHashMap::Entry* p = map->Start(); p != NULL; p = map->Next(p)) { 233 String* name = *static_cast<String**>(p->key); 234 Interface* interface = static_cast<Interface*>(p->value); 235 PrintF("%*s%s : ", n0 + 2, "", name->ToAsciiArray()); 236 interface->Print(n0 + 2); 237 } 238 PrintF("%*s}\n", n0, ""); 239 } 240 } 241} 242#endif 243 244} } // namespace v8::internal 245