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