1 // Copyright 2013 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 "types.h" 29 #include "string-stream.h" 30 31 namespace v8 { 32 namespace internal { 33 34 int Type::NumClasses() { 35 if (is_class()) { 36 return 1; 37 } else if (is_union()) { 38 Handle<Unioned> unioned = as_union(); 39 int result = 0; 40 for (int i = 0; i < unioned->length(); ++i) { 41 if (union_get(unioned, i)->is_class()) ++result; 42 } 43 return result; 44 } else { 45 return 0; 46 } 47 } 48 49 50 int Type::NumConstants() { 51 if (is_constant()) { 52 return 1; 53 } else if (is_union()) { 54 Handle<Unioned> unioned = as_union(); 55 int result = 0; 56 for (int i = 0; i < unioned->length(); ++i) { 57 if (union_get(unioned, i)->is_constant()) ++result; 58 } 59 return result; 60 } else { 61 return 0; 62 } 63 } 64 65 66 template<class T> 67 Handle<Type> Type::Iterator<T>::get_type() { 68 ASSERT(!Done()); 69 return type_->is_union() ? union_get(type_->as_union(), index_) : type_; 70 } 71 72 template<> 73 Handle<Map> Type::Iterator<Map>::Current() { 74 return get_type()->as_class(); 75 } 76 77 template<> 78 Handle<v8::internal::Object> Type::Iterator<v8::internal::Object>::Current() { 79 return get_type()->as_constant(); 80 } 81 82 83 template<> 84 bool Type::Iterator<Map>::matches(Handle<Type> type) { 85 return type->is_class(); 86 } 87 88 template<> 89 bool Type::Iterator<v8::internal::Object>::matches(Handle<Type> type) { 90 return type->is_constant(); 91 } 92 93 94 template<class T> 95 void Type::Iterator<T>::Advance() { 96 ++index_; 97 if (type_->is_union()) { 98 Handle<Unioned> unioned = type_->as_union(); 99 for (; index_ < unioned->length(); ++index_) { 100 if (matches(union_get(unioned, index_))) return; 101 } 102 } else if (index_ == 0 && matches(type_)) { 103 return; 104 } 105 index_ = -1; 106 } 107 108 template class Type::Iterator<Map>; 109 template class Type::Iterator<v8::internal::Object>; 110 111 112 // Get the smallest bitset subsuming this type. 113 int Type::LubBitset() { 114 if (this->is_bitset()) { 115 return this->as_bitset(); 116 } else if (this->is_union()) { 117 Handle<Unioned> unioned = this->as_union(); 118 int bitset = kNone; 119 for (int i = 0; i < unioned->length(); ++i) { 120 bitset |= union_get(unioned, i)->LubBitset(); 121 } 122 return bitset; 123 } else { 124 Map* map = NULL; 125 if (this->is_class()) { 126 map = *this->as_class(); 127 } else { 128 Handle<v8::internal::Object> value = this->as_constant(); 129 if (value->IsSmi()) return kSmi; 130 map = HeapObject::cast(*value)->map(); 131 if (map->instance_type() == ODDBALL_TYPE) { 132 if (value->IsUndefined()) return kUndefined; 133 if (value->IsNull()) return kNull; 134 if (value->IsTrue() || value->IsFalse()) return kBoolean; 135 if (value->IsTheHole()) return kAny; 136 } 137 } 138 switch (map->instance_type()) { 139 case STRING_TYPE: 140 case ASCII_STRING_TYPE: 141 case CONS_STRING_TYPE: 142 case CONS_ASCII_STRING_TYPE: 143 case SLICED_STRING_TYPE: 144 case SLICED_ASCII_STRING_TYPE: 145 case EXTERNAL_STRING_TYPE: 146 case EXTERNAL_ASCII_STRING_TYPE: 147 case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE: 148 case SHORT_EXTERNAL_STRING_TYPE: 149 case SHORT_EXTERNAL_ASCII_STRING_TYPE: 150 case SHORT_EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE: 151 case INTERNALIZED_STRING_TYPE: 152 case ASCII_INTERNALIZED_STRING_TYPE: 153 case CONS_INTERNALIZED_STRING_TYPE: 154 case CONS_ASCII_INTERNALIZED_STRING_TYPE: 155 case EXTERNAL_INTERNALIZED_STRING_TYPE: 156 case EXTERNAL_ASCII_INTERNALIZED_STRING_TYPE: 157 case EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE: 158 case SHORT_EXTERNAL_INTERNALIZED_STRING_TYPE: 159 case SHORT_EXTERNAL_ASCII_INTERNALIZED_STRING_TYPE: 160 case SHORT_EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE: 161 return kString; 162 case SYMBOL_TYPE: 163 return kSymbol; 164 case ODDBALL_TYPE: 165 return kOddball; 166 case HEAP_NUMBER_TYPE: 167 return kDouble; 168 case JS_VALUE_TYPE: 169 case JS_DATE_TYPE: 170 case JS_OBJECT_TYPE: 171 case JS_CONTEXT_EXTENSION_OBJECT_TYPE: 172 case JS_GENERATOR_OBJECT_TYPE: 173 case JS_MODULE_TYPE: 174 case JS_GLOBAL_OBJECT_TYPE: 175 case JS_BUILTINS_OBJECT_TYPE: 176 case JS_GLOBAL_PROXY_TYPE: 177 case JS_ARRAY_BUFFER_TYPE: 178 case JS_TYPED_ARRAY_TYPE: 179 case JS_DATA_VIEW_TYPE: 180 case JS_SET_TYPE: 181 case JS_MAP_TYPE: 182 case JS_WEAK_MAP_TYPE: 183 case JS_WEAK_SET_TYPE: 184 if (map->is_undetectable()) return kUndetectable; 185 return kOtherObject; 186 case JS_ARRAY_TYPE: 187 return kArray; 188 case JS_FUNCTION_TYPE: 189 return kFunction; 190 case JS_REGEXP_TYPE: 191 return kRegExp; 192 case JS_PROXY_TYPE: 193 case JS_FUNCTION_PROXY_TYPE: 194 return kProxy; 195 case MAP_TYPE: 196 // When compiling stub templates, the meta map is used as a place holder 197 // for the actual map with which the template is later instantiated. 198 // We treat it as a kind of type variable whose upper bound is Any. 199 // TODO(rossberg): for caching of CompareNilIC stubs to work correctly, 200 // we must exclude Undetectable here. This makes no sense, really, 201 // because it means that the template isn't actually parametric. 202 // Also, it doesn't apply elsewhere. 8-( 203 // We ought to find a cleaner solution for compiling stubs parameterised 204 // over type or class variables, esp ones with bounds... 205 return kDetectable; 206 case DECLARED_ACCESSOR_INFO_TYPE: 207 case EXECUTABLE_ACCESSOR_INFO_TYPE: 208 case ACCESSOR_PAIR_TYPE: 209 case FIXED_ARRAY_TYPE: 210 return kInternal; 211 default: 212 UNREACHABLE(); 213 return kNone; 214 } 215 } 216 } 217 218 219 // Get the largest bitset subsumed by this type. 220 int Type::GlbBitset() { 221 if (this->is_bitset()) { 222 return this->as_bitset(); 223 } else if (this->is_union()) { 224 // All but the first are non-bitsets and thus would yield kNone anyway. 225 return union_get(this->as_union(), 0)->GlbBitset(); 226 } else { 227 return kNone; 228 } 229 } 230 231 232 // Check this <= that. 233 bool Type::IsSlowCase(Type* that) { 234 // Fast path for bitsets. 235 if (that->is_bitset()) { 236 return (this->LubBitset() | that->as_bitset()) == that->as_bitset(); 237 } 238 239 if (that->is_class()) { 240 return this->is_class() && *this->as_class() == *that->as_class(); 241 } 242 if (that->is_constant()) { 243 return this->is_constant() && *this->as_constant() == *that->as_constant(); 244 } 245 246 // (T1 \/ ... \/ Tn) <= T <=> (T1 <= T) /\ ... /\ (Tn <= T) 247 if (this->is_union()) { 248 Handle<Unioned> unioned = this->as_union(); 249 for (int i = 0; i < unioned->length(); ++i) { 250 Handle<Type> this_i = union_get(unioned, i); 251 if (!this_i->Is(that)) return false; 252 } 253 return true; 254 } 255 256 // T <= (T1 \/ ... \/ Tn) <=> (T <= T1) \/ ... \/ (T <= Tn) 257 // (iff T is not a union) 258 ASSERT(!this->is_union()); 259 if (that->is_union()) { 260 Handle<Unioned> unioned = that->as_union(); 261 for (int i = 0; i < unioned->length(); ++i) { 262 Handle<Type> that_i = union_get(unioned, i); 263 if (this->Is(that_i)) return true; 264 if (this->is_bitset()) break; // Fast fail, no other field is a bitset. 265 } 266 return false; 267 } 268 269 return false; 270 } 271 272 273 // Check this overlaps that. 274 bool Type::Maybe(Type* that) { 275 // Fast path for bitsets. 276 if (this->is_bitset()) { 277 return (this->as_bitset() & that->LubBitset()) != 0; 278 } 279 if (that->is_bitset()) { 280 return (this->LubBitset() & that->as_bitset()) != 0; 281 } 282 283 // (T1 \/ ... \/ Tn) overlaps T <=> (T1 overlaps T) \/ ... \/ (Tn overlaps T) 284 if (this->is_union()) { 285 Handle<Unioned> unioned = this->as_union(); 286 for (int i = 0; i < unioned->length(); ++i) { 287 Handle<Type> this_i = union_get(unioned, i); 288 if (this_i->Maybe(that)) return true; 289 } 290 return false; 291 } 292 293 // T overlaps (T1 \/ ... \/ Tn) <=> (T overlaps T1) \/ ... \/ (T overlaps Tn) 294 if (that->is_union()) { 295 Handle<Unioned> unioned = that->as_union(); 296 for (int i = 0; i < unioned->length(); ++i) { 297 Handle<Type> that_i = union_get(unioned, i); 298 if (this->Maybe(that_i)) return true; 299 } 300 return false; 301 } 302 303 ASSERT(!that->is_union()); 304 if (this->is_class()) { 305 return that->is_class() && *this->as_class() == *that->as_class(); 306 } 307 if (this->is_constant()) { 308 return that->is_constant() && *this->as_constant() == *that->as_constant(); 309 } 310 311 return false; 312 } 313 314 315 bool Type::InUnion(Handle<Unioned> unioned, int current_size) { 316 ASSERT(!this->is_union()); 317 for (int i = 0; i < current_size; ++i) { 318 Handle<Type> type = union_get(unioned, i); 319 if (this->Is(type)) return true; 320 } 321 return false; 322 } 323 324 325 // Get non-bitsets from this which are not subsumed by union, store at unioned, 326 // starting at index. Returns updated index. 327 int Type::ExtendUnion(Handle<Unioned> result, int current_size) { 328 int old_size = current_size; 329 if (this->is_class() || this->is_constant()) { 330 if (!this->InUnion(result, old_size)) result->set(current_size++, this); 331 } else if (this->is_union()) { 332 Handle<Unioned> unioned = this->as_union(); 333 for (int i = 0; i < unioned->length(); ++i) { 334 Handle<Type> type = union_get(unioned, i); 335 ASSERT(i == 0 || !(type->is_bitset() || type->Is(union_get(unioned, 0)))); 336 if (type->is_bitset()) continue; 337 if (!type->InUnion(result, old_size)) result->set(current_size++, *type); 338 } 339 } 340 return current_size; 341 } 342 343 344 // Union is O(1) on simple bit unions, but O(n*m) on structured unions. 345 // TODO(rossberg): Should we use object sets somehow? Is it worth it? 346 Type* Type::Union(Handle<Type> type1, Handle<Type> type2) { 347 // Fast case: bit sets. 348 if (type1->is_bitset() && type2->is_bitset()) { 349 return from_bitset(type1->as_bitset() | type2->as_bitset()); 350 } 351 352 // Fast case: top or bottom types. 353 if (type1->SameValue(Type::Any())) return *type1; 354 if (type2->SameValue(Type::Any())) return *type2; 355 if (type1->SameValue(Type::None())) return *type2; 356 if (type2->SameValue(Type::None())) return *type1; 357 358 // Semi-fast case: Unioned objects are neither involved nor produced. 359 if (!(type1->is_union() || type2->is_union())) { 360 if (type1->Is(type2)) return *type2; 361 if (type2->Is(type1)) return *type1; 362 } 363 364 // Slow case: may need to produce a Unioned object. 365 Isolate* isolate = NULL; 366 int size = type1->is_bitset() || type2->is_bitset() ? 1 : 0; 367 if (!type1->is_bitset()) { 368 isolate = HeapObject::cast(*type1)->GetIsolate(); 369 size += (type1->is_union() ? type1->as_union()->length() : 1); 370 } 371 if (!type2->is_bitset()) { 372 isolate = HeapObject::cast(*type2)->GetIsolate(); 373 size += (type2->is_union() ? type2->as_union()->length() : 1); 374 } 375 ASSERT(isolate != NULL); 376 ASSERT(size >= 2); 377 Handle<Unioned> unioned = isolate->factory()->NewFixedArray(size); 378 size = 0; 379 380 int bitset = type1->GlbBitset() | type2->GlbBitset(); 381 if (bitset != kNone) unioned->set(size++, from_bitset(bitset)); 382 size = type1->ExtendUnion(unioned, size); 383 size = type2->ExtendUnion(unioned, size); 384 385 if (size == 1) { 386 return *union_get(unioned, 0); 387 } else if (size == unioned->length()) { 388 return from_handle(unioned); 389 } 390 391 // There was an overlap. Copy to smaller union. 392 Handle<Unioned> result = isolate->factory()->NewFixedArray(size); 393 for (int i = 0; i < size; ++i) result->set(i, unioned->get(i)); 394 return from_handle(result); 395 } 396 397 398 // Get non-bitsets from this which are also in that, store at unioned, 399 // starting at index. Returns updated index. 400 int Type::ExtendIntersection( 401 Handle<Unioned> result, Handle<Type> that, int current_size) { 402 int old_size = current_size; 403 if (this->is_class() || this->is_constant()) { 404 if (this->Is(that) && !this->InUnion(result, old_size)) 405 result->set(current_size++, this); 406 } else if (this->is_union()) { 407 Handle<Unioned> unioned = this->as_union(); 408 for (int i = 0; i < unioned->length(); ++i) { 409 Handle<Type> type = union_get(unioned, i); 410 ASSERT(i == 0 || !(type->is_bitset() || type->Is(union_get(unioned, 0)))); 411 if (type->is_bitset()) continue; 412 if (type->Is(that) && !type->InUnion(result, old_size)) 413 result->set(current_size++, *type); 414 } 415 } 416 return current_size; 417 } 418 419 420 // Intersection is O(1) on simple bit unions, but O(n*m) on structured unions. 421 // TODO(rossberg): Should we use object sets somehow? Is it worth it? 422 Type* Type::Intersect(Handle<Type> type1, Handle<Type> type2) { 423 // Fast case: bit sets. 424 if (type1->is_bitset() && type2->is_bitset()) { 425 return from_bitset(type1->as_bitset() & type2->as_bitset()); 426 } 427 428 // Fast case: top or bottom types. 429 if (type1->SameValue(Type::None())) return *type1; 430 if (type2->SameValue(Type::None())) return *type2; 431 if (type1->SameValue(Type::Any())) return *type2; 432 if (type2->SameValue(Type::Any())) return *type1; 433 434 // Semi-fast case: Unioned objects are neither involved nor produced. 435 if (!(type1->is_union() || type2->is_union())) { 436 if (type1->Is(type2)) return *type1; 437 if (type2->Is(type1)) return *type2; 438 } 439 440 // Slow case: may need to produce a Unioned object. 441 Isolate* isolate = NULL; 442 int size = 0; 443 if (!type1->is_bitset()) { 444 isolate = HeapObject::cast(*type1)->GetIsolate(); 445 size = (type1->is_union() ? type1->as_union()->length() : 2); 446 } 447 if (!type2->is_bitset()) { 448 isolate = HeapObject::cast(*type2)->GetIsolate(); 449 int size2 = (type2->is_union() ? type2->as_union()->length() : 2); 450 size = (size == 0 ? size2 : Min(size, size2)); 451 } 452 ASSERT(isolate != NULL); 453 ASSERT(size >= 2); 454 Handle<Unioned> unioned = isolate->factory()->NewFixedArray(size); 455 size = 0; 456 457 int bitset = type1->GlbBitset() & type2->GlbBitset(); 458 if (bitset != kNone) unioned->set(size++, from_bitset(bitset)); 459 size = type1->ExtendIntersection(unioned, type2, size); 460 size = type2->ExtendIntersection(unioned, type1, size); 461 462 if (size == 0) { 463 return None(); 464 } else if (size == 1) { 465 return *union_get(unioned, 0); 466 } else if (size == unioned->length()) { 467 return from_handle(unioned); 468 } 469 470 // There were dropped cases. Copy to smaller union. 471 Handle<Unioned> result = isolate->factory()->NewFixedArray(size); 472 for (int i = 0; i < size; ++i) result->set(i, unioned->get(i)); 473 return from_handle(result); 474 } 475 476 477 Type* Type::Optional(Handle<Type> type) { 478 return type->is_bitset() 479 ? from_bitset(type->as_bitset() | kUndefined) 480 : Union(type, Undefined()->handle_via_isolate_of(*type)); 481 } 482 483 484 Representation Representation::FromType(Handle<Type> type) { 485 if (type->Is(Type::None())) return Representation::None(); 486 if (type->Is(Type::Smi())) return Representation::Smi(); 487 if (type->Is(Type::Signed32())) return Representation::Integer32(); 488 if (type->Is(Type::Number())) return Representation::Double(); 489 return Representation::Tagged(); 490 } 491 492 493 #ifdef OBJECT_PRINT 494 void Type::TypePrint() { 495 TypePrint(stdout); 496 PrintF(stdout, "\n"); 497 Flush(stdout); 498 } 499 500 501 void Type::TypePrint(FILE* out) { 502 if (is_bitset()) { 503 int val = as_bitset(); 504 const char* composed_name = GetComposedName(val); 505 if (composed_name != NULL) { 506 PrintF(out, "%s", composed_name); 507 return; 508 } 509 bool first_entry = true; 510 PrintF(out, "{"); 511 for (unsigned i = 0; i < sizeof(val)*8; ++i) { 512 int mask = (1 << i); 513 if ((val & mask) != 0) { 514 if (!first_entry) PrintF(out, ","); 515 first_entry = false; 516 PrintF(out, "%s", GetPrimitiveName(mask)); 517 } 518 } 519 PrintF(out, "}"); 520 } else if (is_constant()) { 521 PrintF(out, "Constant(%p)", static_cast<void*>(*as_constant())); 522 } else if (is_class()) { 523 PrintF(out, "Class(%p)", static_cast<void*>(*as_class())); 524 } else if (is_union()) { 525 PrintF(out, "{"); 526 Handle<Unioned> unioned = as_union(); 527 for (int i = 0; i < unioned->length(); ++i) { 528 Handle<Type> type_i = union_get(unioned, i); 529 if (i > 0) PrintF(out, ","); 530 type_i->TypePrint(out); 531 } 532 PrintF(out, "}"); 533 } 534 } 535 #endif 536 537 538 } } // namespace v8::internal 539