1// Copyright 2014 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/types.h"
6
7#include "src/string-stream.h"
8#include "src/types-inl.h"
9
10namespace v8 {
11namespace internal {
12
13// -----------------------------------------------------------------------------
14// Glb and lub computation.
15
16// The largest bitset subsumed by this type.
17template<class Config>
18int TypeImpl<Config>::BitsetType::Glb(TypeImpl* type) {
19  DisallowHeapAllocation no_allocation;
20  if (type->IsBitset()) {
21    return type->AsBitset();
22  } else if (type->IsUnion()) {
23    UnionHandle unioned = handle(type->AsUnion());
24    int bitset = kNone;
25    for (int i = 0; i < unioned->Length(); ++i) {
26      bitset |= unioned->Get(i)->BitsetGlb();
27    }
28    return bitset;
29  } else if (type->IsClass()) {
30    // Little hack to avoid the need for a region for handlification here...
31    return REPRESENTATION(Config::is_class(type)
32        ? Lub(*Config::as_class(type))
33        : type->AsClass()->Bound(NULL)->AsBitset());
34  } else if (type->IsConstant()) {
35    return REPRESENTATION(type->AsConstant()->Bound()->AsBitset());
36  } else if (type->IsContext()) {
37    return REPRESENTATION(type->AsContext()->Bound()->AsBitset());
38  } else if (type->IsArray()) {
39    return REPRESENTATION(type->AsArray()->Bound()->AsBitset());
40  } else if (type->IsFunction()) {
41    return REPRESENTATION(type->AsFunction()->Bound()->AsBitset());
42  } else {
43    UNREACHABLE();
44    return kNone;
45  }
46}
47
48
49// The smallest bitset subsuming this type.
50template<class Config>
51int TypeImpl<Config>::BitsetType::Lub(TypeImpl* type) {
52  DisallowHeapAllocation no_allocation;
53  if (type->IsBitset()) {
54    return type->AsBitset();
55  } else if (type->IsUnion()) {
56    UnionHandle unioned = handle(type->AsUnion());
57    int bitset = kNone;
58    for (int i = 0; i < unioned->Length(); ++i) {
59      bitset |= unioned->Get(i)->BitsetLub();
60    }
61    return bitset;
62  } else if (type->IsClass()) {
63    // Little hack to avoid the need for a region for handlification here...
64    return Config::is_class(type) ? Lub(*Config::as_class(type)) :
65        type->AsClass()->Bound(NULL)->AsBitset();
66  } else if (type->IsConstant()) {
67    return type->AsConstant()->Bound()->AsBitset();
68  } else if (type->IsContext()) {
69    return type->AsContext()->Bound()->AsBitset();
70  } else if (type->IsArray()) {
71    return type->AsArray()->Bound()->AsBitset();
72  } else if (type->IsFunction()) {
73    return type->AsFunction()->Bound()->AsBitset();
74  } else {
75    UNREACHABLE();
76    return kNone;
77  }
78}
79
80
81// The smallest bitset subsuming this type, ignoring explicit bounds.
82template<class Config>
83int TypeImpl<Config>::BitsetType::InherentLub(TypeImpl* type) {
84  DisallowHeapAllocation no_allocation;
85  if (type->IsBitset()) {
86    return type->AsBitset();
87  } else if (type->IsUnion()) {
88    UnionHandle unioned = handle(type->AsUnion());
89    int bitset = kNone;
90    for (int i = 0; i < unioned->Length(); ++i) {
91      bitset |= unioned->Get(i)->InherentBitsetLub();
92    }
93    return bitset;
94  } else if (type->IsClass()) {
95    return Lub(*type->AsClass()->Map());
96  } else if (type->IsConstant()) {
97    return Lub(*type->AsConstant()->Value());
98  } else if (type->IsContext()) {
99    return kInternal & kTaggedPtr;
100  } else if (type->IsArray()) {
101    return kArray;
102  } else if (type->IsFunction()) {
103    return kFunction;
104  } else {
105    UNREACHABLE();
106    return kNone;
107  }
108}
109
110
111template<class Config>
112int TypeImpl<Config>::BitsetType::Lub(i::Object* value) {
113  DisallowHeapAllocation no_allocation;
114  if (value->IsNumber()) {
115    return Lub(value->Number()) & (value->IsSmi() ? kTaggedInt : kTaggedPtr);
116  }
117  return Lub(i::HeapObject::cast(value)->map());
118}
119
120
121template<class Config>
122int TypeImpl<Config>::BitsetType::Lub(double value) {
123  DisallowHeapAllocation no_allocation;
124  if (i::IsMinusZero(value)) return kMinusZero;
125  if (std::isnan(value)) return kNaN;
126  if (IsUint32Double(value)) return Lub(FastD2UI(value));
127  if (IsInt32Double(value)) return Lub(FastD2I(value));
128  return kOtherNumber;
129}
130
131
132template<class Config>
133int TypeImpl<Config>::BitsetType::Lub(int32_t value) {
134  if (value >= 0x40000000) {
135    return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall;
136  }
137  if (value >= 0) return kUnsignedSmall;
138  if (value >= -0x40000000) return kOtherSignedSmall;
139  return i::SmiValuesAre31Bits() ? kOtherSigned32 : kOtherSignedSmall;
140}
141
142
143template<class Config>
144int TypeImpl<Config>::BitsetType::Lub(uint32_t value) {
145  DisallowHeapAllocation no_allocation;
146  if (value >= 0x80000000u) return kOtherUnsigned32;
147  if (value >= 0x40000000u) {
148    return i::SmiValuesAre31Bits() ? kOtherUnsigned31 : kUnsignedSmall;
149  }
150  return kUnsignedSmall;
151}
152
153
154template<class Config>
155int TypeImpl<Config>::BitsetType::Lub(i::Map* map) {
156  DisallowHeapAllocation no_allocation;
157  switch (map->instance_type()) {
158    case STRING_TYPE:
159    case ASCII_STRING_TYPE:
160    case CONS_STRING_TYPE:
161    case CONS_ASCII_STRING_TYPE:
162    case SLICED_STRING_TYPE:
163    case SLICED_ASCII_STRING_TYPE:
164    case EXTERNAL_STRING_TYPE:
165    case EXTERNAL_ASCII_STRING_TYPE:
166    case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
167    case SHORT_EXTERNAL_STRING_TYPE:
168    case SHORT_EXTERNAL_ASCII_STRING_TYPE:
169    case SHORT_EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
170    case INTERNALIZED_STRING_TYPE:
171    case ASCII_INTERNALIZED_STRING_TYPE:
172    case EXTERNAL_INTERNALIZED_STRING_TYPE:
173    case EXTERNAL_ASCII_INTERNALIZED_STRING_TYPE:
174    case EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
175    case SHORT_EXTERNAL_INTERNALIZED_STRING_TYPE:
176    case SHORT_EXTERNAL_ASCII_INTERNALIZED_STRING_TYPE:
177    case SHORT_EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
178      return kString;
179    case SYMBOL_TYPE:
180      return kSymbol;
181    case ODDBALL_TYPE: {
182      Heap* heap = map->GetHeap();
183      if (map == heap->undefined_map()) return kUndefined;
184      if (map == heap->the_hole_map()) return kAny;  // TODO(rossberg): kNone?
185      if (map == heap->null_map()) return kNull;
186      if (map == heap->boolean_map()) return kBoolean;
187      ASSERT(map == heap->uninitialized_map() ||
188             map == heap->no_interceptor_result_sentinel_map() ||
189             map == heap->termination_exception_map() ||
190             map == heap->arguments_marker_map());
191      return kInternal & kTaggedPtr;
192    }
193    case HEAP_NUMBER_TYPE:
194      return kNumber & kTaggedPtr;
195    case JS_VALUE_TYPE:
196    case JS_DATE_TYPE:
197    case JS_OBJECT_TYPE:
198    case JS_CONTEXT_EXTENSION_OBJECT_TYPE:
199    case JS_GENERATOR_OBJECT_TYPE:
200    case JS_MODULE_TYPE:
201    case JS_GLOBAL_OBJECT_TYPE:
202    case JS_BUILTINS_OBJECT_TYPE:
203    case JS_GLOBAL_PROXY_TYPE:
204    case JS_ARRAY_BUFFER_TYPE:
205    case JS_TYPED_ARRAY_TYPE:
206    case JS_DATA_VIEW_TYPE:
207    case JS_SET_TYPE:
208    case JS_MAP_TYPE:
209    case JS_SET_ITERATOR_TYPE:
210    case JS_MAP_ITERATOR_TYPE:
211    case JS_WEAK_MAP_TYPE:
212    case JS_WEAK_SET_TYPE:
213      if (map->is_undetectable()) return kUndetectable;
214      return kOtherObject;
215    case JS_ARRAY_TYPE:
216      return kArray;
217    case JS_FUNCTION_TYPE:
218      return kFunction;
219    case JS_REGEXP_TYPE:
220      return kRegExp;
221    case JS_PROXY_TYPE:
222    case JS_FUNCTION_PROXY_TYPE:
223      return kProxy;
224    case MAP_TYPE:
225      // When compiling stub templates, the meta map is used as a place holder
226      // for the actual map with which the template is later instantiated.
227      // We treat it as a kind of type variable whose upper bound is Any.
228      // TODO(rossberg): for caching of CompareNilIC stubs to work correctly,
229      // we must exclude Undetectable here. This makes no sense, really,
230      // because it means that the template isn't actually parametric.
231      // Also, it doesn't apply elsewhere. 8-(
232      // We ought to find a cleaner solution for compiling stubs parameterised
233      // over type or class variables, esp ones with bounds...
234      return kDetectable;
235    case DECLARED_ACCESSOR_INFO_TYPE:
236    case EXECUTABLE_ACCESSOR_INFO_TYPE:
237    case SHARED_FUNCTION_INFO_TYPE:
238    case ACCESSOR_PAIR_TYPE:
239    case FIXED_ARRAY_TYPE:
240    case FOREIGN_TYPE:
241      return kInternal & kTaggedPtr;
242    default:
243      UNREACHABLE();
244      return kNone;
245  }
246}
247
248
249// -----------------------------------------------------------------------------
250// Predicates.
251
252// Check this <= that.
253template<class Config>
254bool TypeImpl<Config>::SlowIs(TypeImpl* that) {
255  DisallowHeapAllocation no_allocation;
256
257  // Fast path for bitsets.
258  if (this->IsNone()) return true;
259  if (that->IsBitset()) {
260    return (BitsetType::Lub(this) | that->AsBitset()) == that->AsBitset();
261  }
262  if (this->IsBitset() && SEMANTIC(this->AsBitset()) == BitsetType::kNone) {
263    // Bitsets only have non-bitset supertypes along the representation axis.
264    int that_bitset = that->BitsetGlb();
265    return (this->AsBitset() | that_bitset) == that_bitset;
266  }
267
268  if (that->IsClass()) {
269    return this->IsClass()
270        && *this->AsClass()->Map() == *that->AsClass()->Map()
271        && ((Config::is_class(that) && Config::is_class(this)) ||
272            BitsetType::New(this->BitsetLub())->Is(
273                BitsetType::New(that->BitsetLub())));
274  }
275  if (that->IsConstant()) {
276    return this->IsConstant()
277        && *this->AsConstant()->Value() == *that->AsConstant()->Value()
278        && this->AsConstant()->Bound()->Is(that->AsConstant()->Bound());
279  }
280  if (that->IsContext()) {
281    return this->IsContext()
282        && this->AsContext()->Outer()->Equals(that->AsContext()->Outer());
283  }
284  if (that->IsArray()) {
285    return this->IsArray()
286        && this->AsArray()->Element()->Equals(that->AsArray()->Element());
287  }
288  if (that->IsFunction()) {
289    // We currently do not allow for any variance here, in order to keep
290    // Union and Intersect operations simple.
291    if (!this->IsFunction()) return false;
292    FunctionType* this_fun = this->AsFunction();
293    FunctionType* that_fun = that->AsFunction();
294    if (this_fun->Arity() != that_fun->Arity() ||
295        !this_fun->Result()->Equals(that_fun->Result()) ||
296        !that_fun->Receiver()->Equals(this_fun->Receiver())) {
297      return false;
298    }
299    for (int i = 0; i < this_fun->Arity(); ++i) {
300      if (!that_fun->Parameter(i)->Equals(this_fun->Parameter(i))) return false;
301    }
302    return true;
303  }
304
305  // (T1 \/ ... \/ Tn) <= T  <=>  (T1 <= T) /\ ... /\ (Tn <= T)
306  if (this->IsUnion()) {
307    UnionHandle unioned = handle(this->AsUnion());
308    for (int i = 0; i < unioned->Length(); ++i) {
309      if (!unioned->Get(i)->Is(that)) return false;
310    }
311    return true;
312  }
313
314  // T <= (T1 \/ ... \/ Tn)  <=>  (T <= T1) \/ ... \/ (T <= Tn)
315  // (iff T is not a union)
316  ASSERT(!this->IsUnion());
317  if (that->IsUnion()) {
318    UnionHandle unioned = handle(that->AsUnion());
319    for (int i = 0; i < unioned->Length(); ++i) {
320      if (this->Is(unioned->Get(i))) return true;
321      if (this->IsBitset()) break;  // Fast fail, only first field is a bitset.
322    }
323    return false;
324  }
325
326  return false;
327}
328
329
330template<class Config>
331bool TypeImpl<Config>::NowIs(TypeImpl* that) {
332  DisallowHeapAllocation no_allocation;
333
334  // TODO(rossberg): this is incorrect for
335  //   Union(Constant(V), T)->NowIs(Class(M))
336  // but fuzzing does not cover that!
337  if (this->IsConstant()) {
338    i::Object* object = *this->AsConstant()->Value();
339    if (object->IsHeapObject()) {
340      i::Map* map = i::HeapObject::cast(object)->map();
341      for (Iterator<i::Map> it = that->Classes(); !it.Done(); it.Advance()) {
342        if (*it.Current() == map) return true;
343      }
344    }
345  }
346  return this->Is(that);
347}
348
349
350// Check if this contains only (currently) stable classes.
351template<class Config>
352bool TypeImpl<Config>::NowStable() {
353  DisallowHeapAllocation no_allocation;
354  for (Iterator<i::Map> it = this->Classes(); !it.Done(); it.Advance()) {
355    if (!it.Current()->is_stable()) return false;
356  }
357  return true;
358}
359
360
361// Check this overlaps that.
362template<class Config>
363bool TypeImpl<Config>::Maybe(TypeImpl* that) {
364  DisallowHeapAllocation no_allocation;
365
366  // (T1 \/ ... \/ Tn) overlaps T <=> (T1 overlaps T) \/ ... \/ (Tn overlaps T)
367  if (this->IsUnion()) {
368    UnionHandle unioned = handle(this->AsUnion());
369    for (int i = 0; i < unioned->Length(); ++i) {
370      if (unioned->Get(i)->Maybe(that)) return true;
371    }
372    return false;
373  }
374
375  // T overlaps (T1 \/ ... \/ Tn) <=> (T overlaps T1) \/ ... \/ (T overlaps Tn)
376  if (that->IsUnion()) {
377    UnionHandle unioned = handle(that->AsUnion());
378    for (int i = 0; i < unioned->Length(); ++i) {
379      if (this->Maybe(unioned->Get(i))) return true;
380    }
381    return false;
382  }
383
384  ASSERT(!this->IsUnion() && !that->IsUnion());
385  if (this->IsBitset()) {
386    return BitsetType::IsInhabited(this->AsBitset() & that->BitsetLub());
387  }
388  if (that->IsBitset()) {
389    return BitsetType::IsInhabited(this->BitsetLub() & that->AsBitset());
390  }
391  if (this->IsClass()) {
392    return that->IsClass()
393        && *this->AsClass()->Map() == *that->AsClass()->Map();
394  }
395  if (this->IsConstant()) {
396    return that->IsConstant()
397        && *this->AsConstant()->Value() == *that->AsConstant()->Value();
398  }
399  if (this->IsContext()) {
400    return this->Equals(that);
401  }
402  if (this->IsArray()) {
403    // There is no variance!
404    return this->Equals(that);
405  }
406  if (this->IsFunction()) {
407    // There is no variance!
408    return this->Equals(that);
409  }
410
411  return false;
412}
413
414
415// Check if value is contained in (inhabits) type.
416template<class Config>
417bool TypeImpl<Config>::Contains(i::Object* value) {
418  DisallowHeapAllocation no_allocation;
419  for (Iterator<i::Object> it = this->Constants(); !it.Done(); it.Advance()) {
420    if (*it.Current() == value) return true;
421  }
422  return BitsetType::New(BitsetType::Lub(value))->Is(this);
423}
424
425
426template<class Config>
427bool TypeImpl<Config>::UnionType::Wellformed() {
428  ASSERT(this->Length() >= 2);
429  for (int i = 0; i < this->Length(); ++i) {
430    ASSERT(!this->Get(i)->IsUnion());
431    if (i > 0) ASSERT(!this->Get(i)->IsBitset());
432    for (int j = 0; j < this->Length(); ++j) {
433      if (i != j) ASSERT(!this->Get(i)->Is(this->Get(j)));
434    }
435  }
436  return true;
437}
438
439
440// -----------------------------------------------------------------------------
441// Union and intersection
442
443template<class Config>
444typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Narrow(
445    int bitset, Region* region) {
446  TypeHandle bound = BitsetType::New(bitset, region);
447  if (this->IsClass()) {
448    return ClassType::New(this->AsClass()->Map(), bound, region);
449  } else if (this->IsConstant()) {
450    return ConstantType::New(this->AsConstant()->Value(), bound, region);
451  } else if (this->IsContext()) {
452    return ContextType::New(this->AsContext()->Outer(), bound, region);
453  } else if (this->IsArray()) {
454    return ArrayType::New(this->AsArray()->Element(), bound, region);
455  } else if (this->IsFunction()) {
456    FunctionType* function = this->AsFunction();
457    int arity = function->Arity();
458    FunctionHandle type = FunctionType::New(
459        function->Result(), function->Receiver(), bound, arity, region);
460    for (int i = 0; i < arity; ++i) {
461      type->InitParameter(i, function->Parameter(i));
462    }
463    return type;
464  }
465  UNREACHABLE();
466  return TypeHandle();
467}
468
469
470template<class Config>
471int TypeImpl<Config>::BoundBy(TypeImpl* that) {
472  ASSERT(!this->IsUnion());
473  if (that->IsUnion()) {
474    UnionType* unioned = that->AsUnion();
475    int length = unioned->Length();
476    int bitset = BitsetType::kNone;
477    for (int i = 0; i < length; ++i) {
478      bitset |= BoundBy(unioned->Get(i)->unhandle());
479    }
480    return bitset;
481  } else if (that->IsClass() && this->IsClass() &&
482      *this->AsClass()->Map() == *that->AsClass()->Map()) {
483    return that->BitsetLub();
484  } else if (that->IsConstant() && this->IsConstant() &&
485      *this->AsConstant()->Value() == *that->AsConstant()->Value()) {
486    return that->AsConstant()->Bound()->AsBitset();
487  } else if (that->IsContext() && this->IsContext() && this->Is(that)) {
488    return that->AsContext()->Bound()->AsBitset();
489  } else if (that->IsArray() && this->IsArray() && this->Is(that)) {
490    return that->AsArray()->Bound()->AsBitset();
491  } else if (that->IsFunction() && this->IsFunction() && this->Is(that)) {
492    return that->AsFunction()->Bound()->AsBitset();
493  }
494  return that->BitsetGlb();
495}
496
497
498template<class Config>
499int TypeImpl<Config>::IndexInUnion(
500    int bound, UnionHandle unioned, int current_size) {
501  ASSERT(!this->IsUnion());
502  for (int i = 0; i < current_size; ++i) {
503    TypeHandle that = unioned->Get(i);
504    if (that->IsBitset()) {
505      if ((bound | that->AsBitset()) == that->AsBitset()) return i;
506    } else if (that->IsClass() && this->IsClass()) {
507      if (*this->AsClass()->Map() == *that->AsClass()->Map()) return i;
508    } else if (that->IsConstant() && this->IsConstant()) {
509      if (*this->AsConstant()->Value() == *that->AsConstant()->Value())
510        return i;
511    } else if (that->IsContext() && this->IsContext()) {
512      if (this->Is(that)) return i;
513    } else if (that->IsArray() && this->IsArray()) {
514      if (this->Is(that)) return i;
515    } else if (that->IsFunction() && this->IsFunction()) {
516      if (this->Is(that)) return i;
517    }
518  }
519  return -1;
520}
521
522
523// Get non-bitsets from type, bounded by upper.
524// Store at result starting at index. Returns updated index.
525template<class Config>
526int TypeImpl<Config>::ExtendUnion(
527    UnionHandle result, int size, TypeHandle type,
528    TypeHandle other, bool is_intersect, Region* region) {
529  int old_size = size;
530  if (type->IsUnion()) {
531    UnionHandle unioned = handle(type->AsUnion());
532    for (int i = 0; i < unioned->Length(); ++i) {
533      TypeHandle type_i = unioned->Get(i);
534      ASSERT(i == 0 || !(type_i->IsBitset() || type_i->Is(unioned->Get(0))));
535      if (!type_i->IsBitset()) {
536        size = ExtendUnion(result, size, type_i, other, is_intersect, region);
537      }
538    }
539  } else if (!type->IsBitset()) {
540    ASSERT(type->IsClass() || type->IsConstant() ||
541           type->IsArray() || type->IsFunction() || type->IsContext());
542    int inherent_bound = type->InherentBitsetLub();
543    int old_bound = type->BitsetLub();
544    int other_bound = type->BoundBy(other->unhandle()) & inherent_bound;
545    int new_bound =
546        is_intersect ? (old_bound & other_bound) : (old_bound | other_bound);
547    if (new_bound != BitsetType::kNone) {
548      int i = type->IndexInUnion(new_bound, result, old_size);
549      if (i == -1) {
550        i = size++;
551      } else if (result->Get(i)->IsBitset()) {
552        return size;  // Already fully subsumed.
553      } else {
554        int type_i_bound = result->Get(i)->BitsetLub();
555        new_bound |= type_i_bound;
556        if (new_bound == type_i_bound) return size;
557      }
558      if (new_bound != old_bound) type = type->Narrow(new_bound, region);
559      result->Set(i, type);
560    }
561  }
562  return size;
563}
564
565
566// If bitset is subsumed by another entry in the result, remove it.
567// (Only bitsets with empty semantic axis can be subtypes of non-bitsets.)
568template<class Config>
569int TypeImpl<Config>::NormalizeUnion(UnionHandle result, int size, int bitset) {
570  if (bitset != BitsetType::kNone && SEMANTIC(bitset) == BitsetType::kNone) {
571    for (int i = 1; i < size; ++i) {
572      int glb = result->Get(i)->BitsetGlb();
573      if ((bitset | glb) == glb) {
574        for (int j = 1; j < size; ++j) {
575          result->Set(j - 1, result->Get(j));
576        }
577        --size;
578        break;
579      }
580    }
581  }
582  return size;
583}
584
585
586// Union is O(1) on simple bitsets, but O(n*m) on structured unions.
587template<class Config>
588typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Union(
589    TypeHandle type1, TypeHandle type2, Region* region) {
590  // Fast case: bit sets.
591  if (type1->IsBitset() && type2->IsBitset()) {
592    return BitsetType::New(type1->AsBitset() | type2->AsBitset(), region);
593  }
594
595  // Fast case: top or bottom types.
596  if (type1->IsAny() || type2->IsNone()) return type1;
597  if (type2->IsAny() || type1->IsNone()) return type2;
598
599  // Semi-fast case: Unioned objects are neither involved nor produced.
600  if (!(type1->IsUnion() || type2->IsUnion())) {
601    if (type1->Is(type2)) return type2;
602    if (type2->Is(type1)) return type1;
603  }
604
605  // Slow case: may need to produce a Unioned object.
606  int size = 0;
607  if (!type1->IsBitset()) {
608    size += (type1->IsUnion() ? type1->AsUnion()->Length() : 1);
609  }
610  if (!type2->IsBitset()) {
611    size += (type2->IsUnion() ? type2->AsUnion()->Length() : 1);
612  }
613  int bitset = type1->BitsetGlb() | type2->BitsetGlb();
614  if (bitset != BitsetType::kNone) ++size;
615  ASSERT(size >= 1);
616
617  UnionHandle unioned = UnionType::New(size, region);
618  size = 0;
619  if (bitset != BitsetType::kNone) {
620    unioned->Set(size++, BitsetType::New(bitset, region));
621  }
622  size = ExtendUnion(unioned, size, type1, type2, false, region);
623  size = ExtendUnion(unioned, size, type2, type1, false, region);
624  size = NormalizeUnion(unioned, size, bitset);
625
626  if (size == 1) {
627    return unioned->Get(0);
628  } else {
629    unioned->Shrink(size);
630    ASSERT(unioned->Wellformed());
631    return unioned;
632  }
633}
634
635
636// Intersection is O(1) on simple bitsets, but O(n*m) on structured unions.
637template<class Config>
638typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Intersect(
639    TypeHandle type1, TypeHandle type2, Region* region) {
640  // Fast case: bit sets.
641  if (type1->IsBitset() && type2->IsBitset()) {
642    return BitsetType::New(type1->AsBitset() & type2->AsBitset(), region);
643  }
644
645  // Fast case: top or bottom types.
646  if (type1->IsNone() || type2->IsAny()) return type1;
647  if (type2->IsNone() || type1->IsAny()) return type2;
648
649  // Semi-fast case: Unioned objects are neither involved nor produced.
650  if (!(type1->IsUnion() || type2->IsUnion())) {
651    if (type1->Is(type2)) return type1;
652    if (type2->Is(type1)) return type2;
653  }
654
655  // Slow case: may need to produce a Unioned object.
656  int size = 0;
657  if (!type1->IsBitset()) {
658    size += (type1->IsUnion() ? type1->AsUnion()->Length() : 1);
659  }
660  if (!type2->IsBitset()) {
661    size += (type2->IsUnion() ? type2->AsUnion()->Length() : 1);
662  }
663  int bitset = type1->BitsetGlb() & type2->BitsetGlb();
664  if (bitset != BitsetType::kNone) ++size;
665  ASSERT(size >= 1);
666
667  UnionHandle unioned = UnionType::New(size, region);
668  size = 0;
669  if (bitset != BitsetType::kNone) {
670    unioned->Set(size++, BitsetType::New(bitset, region));
671  }
672  size = ExtendUnion(unioned, size, type1, type2, true, region);
673  size = ExtendUnion(unioned, size, type2, type1, true, region);
674  size = NormalizeUnion(unioned, size, bitset);
675
676  if (size == 0) {
677    return None(region);
678  } else if (size == 1) {
679    return unioned->Get(0);
680  } else {
681    unioned->Shrink(size);
682    ASSERT(unioned->Wellformed());
683    return unioned;
684  }
685}
686
687
688// -----------------------------------------------------------------------------
689// Iteration.
690
691template<class Config>
692int TypeImpl<Config>::NumClasses() {
693  DisallowHeapAllocation no_allocation;
694  if (this->IsClass()) {
695    return 1;
696  } else if (this->IsUnion()) {
697    UnionHandle unioned = handle(this->AsUnion());
698    int result = 0;
699    for (int i = 0; i < unioned->Length(); ++i) {
700      if (unioned->Get(i)->IsClass()) ++result;
701    }
702    return result;
703  } else {
704    return 0;
705  }
706}
707
708
709template<class Config>
710int TypeImpl<Config>::NumConstants() {
711  DisallowHeapAllocation no_allocation;
712  if (this->IsConstant()) {
713    return 1;
714  } else if (this->IsUnion()) {
715    UnionHandle unioned = handle(this->AsUnion());
716    int result = 0;
717    for (int i = 0; i < unioned->Length(); ++i) {
718      if (unioned->Get(i)->IsConstant()) ++result;
719    }
720    return result;
721  } else {
722    return 0;
723  }
724}
725
726
727template<class Config> template<class T>
728typename TypeImpl<Config>::TypeHandle
729TypeImpl<Config>::Iterator<T>::get_type() {
730  ASSERT(!Done());
731  return type_->IsUnion() ? type_->AsUnion()->Get(index_) : type_;
732}
733
734
735// C++ cannot specialise nested templates, so we have to go through this
736// contortion with an auxiliary template to simulate it.
737template<class Config, class T>
738struct TypeImplIteratorAux {
739  static bool matches(typename TypeImpl<Config>::TypeHandle type);
740  static i::Handle<T> current(typename TypeImpl<Config>::TypeHandle type);
741};
742
743template<class Config>
744struct TypeImplIteratorAux<Config, i::Map> {
745  static bool matches(typename TypeImpl<Config>::TypeHandle type) {
746    return type->IsClass();
747  }
748  static i::Handle<i::Map> current(typename TypeImpl<Config>::TypeHandle type) {
749    return type->AsClass()->Map();
750  }
751};
752
753template<class Config>
754struct TypeImplIteratorAux<Config, i::Object> {
755  static bool matches(typename TypeImpl<Config>::TypeHandle type) {
756    return type->IsConstant();
757  }
758  static i::Handle<i::Object> current(
759      typename TypeImpl<Config>::TypeHandle type) {
760    return type->AsConstant()->Value();
761  }
762};
763
764template<class Config> template<class T>
765bool TypeImpl<Config>::Iterator<T>::matches(TypeHandle type) {
766  return TypeImplIteratorAux<Config, T>::matches(type);
767}
768
769template<class Config> template<class T>
770i::Handle<T> TypeImpl<Config>::Iterator<T>::Current() {
771  return TypeImplIteratorAux<Config, T>::current(get_type());
772}
773
774
775template<class Config> template<class T>
776void TypeImpl<Config>::Iterator<T>::Advance() {
777  DisallowHeapAllocation no_allocation;
778  ++index_;
779  if (type_->IsUnion()) {
780    UnionHandle unioned = handle(type_->AsUnion());
781    for (; index_ < unioned->Length(); ++index_) {
782      if (matches(unioned->Get(index_))) return;
783    }
784  } else if (index_ == 0 && matches(type_)) {
785    return;
786  }
787  index_ = -1;
788}
789
790
791// -----------------------------------------------------------------------------
792// Conversion between low-level representations.
793
794template<class Config>
795template<class OtherType>
796typename TypeImpl<Config>::TypeHandle TypeImpl<Config>::Convert(
797    typename OtherType::TypeHandle type, Region* region) {
798  if (type->IsBitset()) {
799    return BitsetType::New(type->AsBitset(), region);
800  } else if (type->IsClass()) {
801    return ClassType::New(
802        type->AsClass()->Map(),
803        BitsetType::New(type->BitsetLub(), region), region);
804  } else if (type->IsConstant()) {
805    return ConstantType::New(
806        type->AsConstant()->Value(),
807        Convert<OtherType>(type->AsConstant()->Bound(), region), region);
808  } else if (type->IsContext()) {
809    TypeHandle outer = Convert<OtherType>(type->AsContext()->Outer(), region);
810    return ContextType::New(outer, region);
811  } else if (type->IsUnion()) {
812    int length = type->AsUnion()->Length();
813    UnionHandle unioned = UnionType::New(length, region);
814    for (int i = 0; i < length; ++i) {
815      unioned->Set(i, Convert<OtherType>(type->AsUnion()->Get(i), region));
816    }
817    return unioned;
818  } else if (type->IsArray()) {
819    return ArrayType::New(
820        Convert<OtherType>(type->AsArray()->Element(), region),
821        Convert<OtherType>(type->AsArray()->Bound(), region), region);
822  } else if (type->IsFunction()) {
823    FunctionHandle function = FunctionType::New(
824        Convert<OtherType>(type->AsFunction()->Result(), region),
825        Convert<OtherType>(type->AsFunction()->Receiver(), region),
826        Convert<OtherType>(type->AsFunction()->Bound(), region),
827        type->AsFunction()->Arity(), region);
828    for (int i = 0; i < function->Arity(); ++i) {
829      function->InitParameter(i,
830          Convert<OtherType>(type->AsFunction()->Parameter(i), region));
831    }
832    return function;
833  } else {
834    UNREACHABLE();
835    return None(region);
836  }
837}
838
839
840// -----------------------------------------------------------------------------
841// Printing.
842
843template<class Config>
844const char* TypeImpl<Config>::BitsetType::Name(int bitset) {
845  switch (bitset) {
846    case REPRESENTATION(kAny): return "Any";
847    #define RETURN_NAMED_REPRESENTATION_TYPE(type, value) \
848    case REPRESENTATION(k##type): return #type;
849    REPRESENTATION_BITSET_TYPE_LIST(RETURN_NAMED_REPRESENTATION_TYPE)
850    #undef RETURN_NAMED_REPRESENTATION_TYPE
851
852    #define RETURN_NAMED_SEMANTIC_TYPE(type, value) \
853    case SEMANTIC(k##type): return #type;
854    SEMANTIC_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE)
855    #undef RETURN_NAMED_SEMANTIC_TYPE
856
857    default:
858      return NULL;
859  }
860}
861
862
863template<class Config>
864void TypeImpl<Config>::BitsetType::PrintTo(StringStream* stream, int bitset) {
865  DisallowHeapAllocation no_allocation;
866  const char* name = Name(bitset);
867  if (name != NULL) {
868    stream->Add("%s", name);
869  } else {
870    static const int named_bitsets[] = {
871      #define BITSET_CONSTANT(type, value) REPRESENTATION(k##type),
872      REPRESENTATION_BITSET_TYPE_LIST(BITSET_CONSTANT)
873      #undef BITSET_CONSTANT
874
875      #define BITSET_CONSTANT(type, value) SEMANTIC(k##type),
876      SEMANTIC_BITSET_TYPE_LIST(BITSET_CONSTANT)
877      #undef BITSET_CONSTANT
878    };
879
880    bool is_first = true;
881    stream->Add("(");
882    for (int i(ARRAY_SIZE(named_bitsets) - 1); bitset != 0 && i >= 0; --i) {
883      int subset = named_bitsets[i];
884      if ((bitset & subset) == subset) {
885        if (!is_first) stream->Add(" | ");
886        is_first = false;
887        stream->Add("%s", Name(subset));
888        bitset -= subset;
889      }
890    }
891    ASSERT(bitset == 0);
892    stream->Add(")");
893  }
894}
895
896
897template<class Config>
898void TypeImpl<Config>::PrintTo(StringStream* stream, PrintDimension dim) {
899  DisallowHeapAllocation no_allocation;
900  if (dim != REPRESENTATION_DIM) {
901    if (this->IsBitset()) {
902      BitsetType::PrintTo(stream, SEMANTIC(this->AsBitset()));
903    } else if (this->IsClass()) {
904      stream->Add("Class(%p < ", static_cast<void*>(*this->AsClass()->Map()));
905      BitsetType::New(BitsetType::Lub(this))->PrintTo(stream, dim);
906      stream->Add(")");
907      return;
908    } else if (this->IsConstant()) {
909      stream->Add("Constant(%p : ",
910             static_cast<void*>(*this->AsConstant()->Value()));
911      BitsetType::New(BitsetType::Lub(this))->PrintTo(stream, dim);
912      stream->Add(")");
913      return;
914    } else if (this->IsContext()) {
915      stream->Add("Context(");
916      this->AsContext()->Outer()->PrintTo(stream, dim);
917      stream->Add(")");
918    } else if (this->IsUnion()) {
919      stream->Add("(");
920      UnionHandle unioned = handle(this->AsUnion());
921      for (int i = 0; i < unioned->Length(); ++i) {
922        TypeHandle type_i = unioned->Get(i);
923        if (i > 0) stream->Add(" | ");
924        type_i->PrintTo(stream, dim);
925      }
926      stream->Add(")");
927      return;
928    } else if (this->IsArray()) {
929      stream->Add("Array(");
930      AsArray()->Element()->PrintTo(stream, dim);
931      stream->Add(")");
932    } else if (this->IsFunction()) {
933      if (!this->AsFunction()->Receiver()->IsAny()) {
934        this->AsFunction()->Receiver()->PrintTo(stream, dim);
935        stream->Add(".");
936      }
937      stream->Add("(");
938      for (int i = 0; i < this->AsFunction()->Arity(); ++i) {
939        if (i > 0) stream->Add(", ");
940        this->AsFunction()->Parameter(i)->PrintTo(stream, dim);
941      }
942      stream->Add(")->");
943      this->AsFunction()->Result()->PrintTo(stream, dim);
944    } else {
945      UNREACHABLE();
946    }
947  }
948  if (dim == BOTH_DIMS) {
949    stream->Add("/");
950  }
951  if (dim != SEMANTIC_DIM) {
952    BitsetType::PrintTo(stream, REPRESENTATION(this->BitsetLub()));
953  }
954}
955
956
957template<class Config>
958void TypeImpl<Config>::TypePrint(FILE* out, PrintDimension dim) {
959  HeapStringAllocator allocator;
960  StringStream stream(&allocator);
961  PrintTo(&stream, dim);
962  stream.OutputToFile(out);
963}
964
965
966template<class Config>
967void TypeImpl<Config>::TypePrint(PrintDimension dim) {
968  TypePrint(stdout, dim);
969  PrintF(stdout, "\n");
970  Flush(stdout);
971}
972
973
974// -----------------------------------------------------------------------------
975// Instantiations.
976
977template class TypeImpl<ZoneTypeConfig>;
978template class TypeImpl<ZoneTypeConfig>::Iterator<i::Map>;
979template class TypeImpl<ZoneTypeConfig>::Iterator<i::Object>;
980
981template class TypeImpl<HeapTypeConfig>;
982template class TypeImpl<HeapTypeConfig>::Iterator<i::Map>;
983template class TypeImpl<HeapTypeConfig>::Iterator<i::Object>;
984
985template TypeImpl<ZoneTypeConfig>::TypeHandle
986  TypeImpl<ZoneTypeConfig>::Convert<HeapType>(
987    TypeImpl<HeapTypeConfig>::TypeHandle, TypeImpl<ZoneTypeConfig>::Region*);
988template TypeImpl<HeapTypeConfig>::TypeHandle
989  TypeImpl<HeapTypeConfig>::Convert<Type>(
990    TypeImpl<ZoneTypeConfig>::TypeHandle, TypeImpl<HeapTypeConfig>::Region*);
991
992} }  // namespace v8::internal
993