Home | History | Annotate | Download | only in ast 
      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 <iomanip>
      6 
      7 #include "src/ast/ast-types.h"
      8 
      9 #include "src/handles-inl.h"
     10 #include "src/objects-inl.h"
     11 #include "src/ostreams.h"
     12 
     13 namespace v8 {
     14 namespace internal {
     15 
     16 // NOTE: If code is marked as being a "shortcut", this means that removing
     17 // the code won't affect the semantics of the surrounding function definition.
     18 
     19 // static
     20 bool AstType::IsInteger(i::Object* x) {
     21   return x->IsNumber() && AstType::IsInteger(x->Number());
     22 }
     23 
     24 // -----------------------------------------------------------------------------
     25 // Range-related helper functions.
     26 
     27 bool AstRangeType::Limits::IsEmpty() { return this->min > this->max; }
     28 
     29 AstRangeType::Limits AstRangeType::Limits::Intersect(Limits lhs, Limits rhs) {
     30   DisallowHeapAllocation no_allocation;
     31   Limits result(lhs);
     32   if (lhs.min < rhs.min) result.min = rhs.min;
     33   if (lhs.max > rhs.max) result.max = rhs.max;
     34   return result;
     35 }
     36 
     37 AstRangeType::Limits AstRangeType::Limits::Union(Limits lhs, Limits rhs) {
     38   DisallowHeapAllocation no_allocation;
     39   if (lhs.IsEmpty()) return rhs;
     40   if (rhs.IsEmpty()) return lhs;
     41   Limits result(lhs);
     42   if (lhs.min > rhs.min) result.min = rhs.min;
     43   if (lhs.max < rhs.max) result.max = rhs.max;
     44   return result;
     45 }
     46 
     47 bool AstType::Overlap(AstRangeType* lhs, AstRangeType* rhs) {
     48   DisallowHeapAllocation no_allocation;
     49   return !AstRangeType::Limits::Intersect(AstRangeType::Limits(lhs),
     50                                           AstRangeType::Limits(rhs))
     51               .IsEmpty();
     52 }
     53 
     54 bool AstType::Contains(AstRangeType* lhs, AstRangeType* rhs) {
     55   DisallowHeapAllocation no_allocation;
     56   return lhs->Min() <= rhs->Min() && rhs->Max() <= lhs->Max();
     57 }
     58 
     59 bool AstType::Contains(AstRangeType* lhs, AstConstantType* rhs) {
     60   DisallowHeapAllocation no_allocation;
     61   return IsInteger(*rhs->Value()) && lhs->Min() <= rhs->Value()->Number() &&
     62          rhs->Value()->Number() <= lhs->Max();
     63 }
     64 
     65 bool AstType::Contains(AstRangeType* range, i::Object* val) {
     66   DisallowHeapAllocation no_allocation;
     67   return IsInteger(val) && range->Min() <= val->Number() &&
     68          val->Number() <= range->Max();
     69 }
     70 
     71 // -----------------------------------------------------------------------------
     72 // Min and Max computation.
     73 
     74 double AstType::Min() {
     75   DCHECK(this->SemanticIs(Number()));
     76   if (this->IsBitset()) return AstBitsetType::Min(this->AsBitset());
     77   if (this->IsUnion()) {
     78     double min = +V8_INFINITY;
     79     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
     80       min = std::min(min, this->AsUnion()->Get(i)->Min());
     81     }
     82     return min;
     83   }
     84   if (this->IsRange()) return this->AsRange()->Min();
     85   if (this->IsConstant()) return this->AsConstant()->Value()->Number();
     86   UNREACHABLE();
     87   return 0;
     88 }
     89 
     90 double AstType::Max() {
     91   DCHECK(this->SemanticIs(Number()));
     92   if (this->IsBitset()) return AstBitsetType::Max(this->AsBitset());
     93   if (this->IsUnion()) {
     94     double max = -V8_INFINITY;
     95     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
     96       max = std::max(max, this->AsUnion()->Get(i)->Max());
     97     }
     98     return max;
     99   }
    100   if (this->IsRange()) return this->AsRange()->Max();
    101   if (this->IsConstant()) return this->AsConstant()->Value()->Number();
    102   UNREACHABLE();
    103   return 0;
    104 }
    105 
    106 // -----------------------------------------------------------------------------
    107 // Glb and lub computation.
    108 
    109 // The largest bitset subsumed by this type.
    110 AstType::bitset AstBitsetType::Glb(AstType* type) {
    111   DisallowHeapAllocation no_allocation;
    112   // Fast case.
    113   if (IsBitset(type)) {
    114     return type->AsBitset();
    115   } else if (type->IsUnion()) {
    116     SLOW_DCHECK(type->AsUnion()->Wellformed());
    117     return type->AsUnion()->Get(0)->BitsetGlb() |
    118            AST_SEMANTIC(type->AsUnion()->Get(1)->BitsetGlb());  // Shortcut.
    119   } else if (type->IsRange()) {
    120     bitset glb = AST_SEMANTIC(
    121         AstBitsetType::Glb(type->AsRange()->Min(), type->AsRange()->Max()));
    122     return glb | AST_REPRESENTATION(type->BitsetLub());
    123   } else {
    124     return type->Representation();
    125   }
    126 }
    127 
    128 // The smallest bitset subsuming this type, possibly not a proper one.
    129 AstType::bitset AstBitsetType::Lub(AstType* type) {
    130   DisallowHeapAllocation no_allocation;
    131   if (IsBitset(type)) return type->AsBitset();
    132   if (type->IsUnion()) {
    133     // Take the representation from the first element, which is always
    134     // a bitset.
    135     int bitset = type->AsUnion()->Get(0)->BitsetLub();
    136     for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) {
    137       // Other elements only contribute their semantic part.
    138       bitset |= AST_SEMANTIC(type->AsUnion()->Get(i)->BitsetLub());
    139     }
    140     return bitset;
    141   }
    142   if (type->IsClass()) return type->AsClass()->Lub();
    143   if (type->IsConstant()) return type->AsConstant()->Lub();
    144   if (type->IsRange()) return type->AsRange()->Lub();
    145   if (type->IsContext()) return kOtherInternal & kTaggedPointer;
    146   if (type->IsArray()) return kOtherObject;
    147   if (type->IsFunction()) return kFunction;
    148   if (type->IsTuple()) return kOtherInternal;
    149   UNREACHABLE();
    150   return kNone;
    151 }
    152 
    153 AstType::bitset AstBitsetType::Lub(i::Map* map) {
    154   DisallowHeapAllocation no_allocation;
    155   switch (map->instance_type()) {
    156     case STRING_TYPE:
    157     case ONE_BYTE_STRING_TYPE:
    158     case CONS_STRING_TYPE:
    159     case CONS_ONE_BYTE_STRING_TYPE:
    160     case THIN_STRING_TYPE:
    161     case THIN_ONE_BYTE_STRING_TYPE:
    162     case SLICED_STRING_TYPE:
    163     case SLICED_ONE_BYTE_STRING_TYPE:
    164     case EXTERNAL_STRING_TYPE:
    165     case EXTERNAL_ONE_BYTE_STRING_TYPE:
    166     case EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
    167     case SHORT_EXTERNAL_STRING_TYPE:
    168     case SHORT_EXTERNAL_ONE_BYTE_STRING_TYPE:
    169     case SHORT_EXTERNAL_STRING_WITH_ONE_BYTE_DATA_TYPE:
    170       return kOtherString;
    171     case INTERNALIZED_STRING_TYPE:
    172     case ONE_BYTE_INTERNALIZED_STRING_TYPE:
    173     case EXTERNAL_INTERNALIZED_STRING_TYPE:
    174     case EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
    175     case EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
    176     case SHORT_EXTERNAL_INTERNALIZED_STRING_TYPE:
    177     case SHORT_EXTERNAL_ONE_BYTE_INTERNALIZED_STRING_TYPE:
    178     case SHORT_EXTERNAL_INTERNALIZED_STRING_WITH_ONE_BYTE_DATA_TYPE:
    179       return kInternalizedString;
    180     case SYMBOL_TYPE:
    181       return kSymbol;
    182     case ODDBALL_TYPE: {
    183       Heap* heap = map->GetHeap();
    184       if (map == heap->undefined_map()) return kUndefined;
    185       if (map == heap->null_map()) return kNull;
    186       if (map == heap->boolean_map()) return kBoolean;
    187       if (map == heap->the_hole_map()) return kHole;
    188       DCHECK(map == heap->uninitialized_map() ||
    189              map == heap->no_interceptor_result_sentinel_map() ||
    190              map == heap->termination_exception_map() ||
    191              map == heap->arguments_marker_map() ||
    192              map == heap->optimized_out_map() ||
    193              map == heap->stale_register_map());
    194       return kOtherInternal & kTaggedPointer;
    195     }
    196     case HEAP_NUMBER_TYPE:
    197       return kNumber & kTaggedPointer;
    198     case JS_OBJECT_TYPE:
    199     case JS_ARGUMENTS_TYPE:
    200     case JS_ERROR_TYPE:
    201     case JS_GLOBAL_OBJECT_TYPE:
    202     case JS_GLOBAL_PROXY_TYPE:
    203     case JS_API_OBJECT_TYPE:
    204     case JS_SPECIAL_API_OBJECT_TYPE:
    205       if (map->is_undetectable()) return kOtherUndetectable;
    206       return kOtherObject;
    207     case JS_VALUE_TYPE:
    208     case JS_MESSAGE_OBJECT_TYPE:
    209     case JS_DATE_TYPE:
    210     case JS_CONTEXT_EXTENSION_OBJECT_TYPE:
    211     case JS_GENERATOR_OBJECT_TYPE:
    212     case JS_MODULE_NAMESPACE_TYPE:
    213     case JS_ARRAY_BUFFER_TYPE:
    214     case JS_ARRAY_TYPE:
    215     case JS_REGEXP_TYPE:  // TODO(rossberg): there should be a RegExp type.
    216     case JS_TYPED_ARRAY_TYPE:
    217     case JS_DATA_VIEW_TYPE:
    218     case JS_SET_TYPE:
    219     case JS_MAP_TYPE:
    220     case JS_SET_ITERATOR_TYPE:
    221     case JS_MAP_ITERATOR_TYPE:
    222     case JS_STRING_ITERATOR_TYPE:
    223     case JS_ASYNC_FROM_SYNC_ITERATOR_TYPE:
    224 
    225     case JS_TYPED_ARRAY_KEY_ITERATOR_TYPE:
    226     case JS_FAST_ARRAY_KEY_ITERATOR_TYPE:
    227     case JS_GENERIC_ARRAY_KEY_ITERATOR_TYPE:
    228     case JS_UINT8_ARRAY_KEY_VALUE_ITERATOR_TYPE:
    229     case JS_INT8_ARRAY_KEY_VALUE_ITERATOR_TYPE:
    230     case JS_UINT16_ARRAY_KEY_VALUE_ITERATOR_TYPE:
    231     case JS_INT16_ARRAY_KEY_VALUE_ITERATOR_TYPE:
    232     case JS_UINT32_ARRAY_KEY_VALUE_ITERATOR_TYPE:
    233     case JS_INT32_ARRAY_KEY_VALUE_ITERATOR_TYPE:
    234     case JS_FLOAT32_ARRAY_KEY_VALUE_ITERATOR_TYPE:
    235     case JS_FLOAT64_ARRAY_KEY_VALUE_ITERATOR_TYPE:
    236     case JS_UINT8_CLAMPED_ARRAY_KEY_VALUE_ITERATOR_TYPE:
    237     case JS_FAST_SMI_ARRAY_KEY_VALUE_ITERATOR_TYPE:
    238     case JS_FAST_HOLEY_SMI_ARRAY_KEY_VALUE_ITERATOR_TYPE:
    239     case JS_FAST_ARRAY_KEY_VALUE_ITERATOR_TYPE:
    240     case JS_FAST_HOLEY_ARRAY_KEY_VALUE_ITERATOR_TYPE:
    241     case JS_FAST_DOUBLE_ARRAY_KEY_VALUE_ITERATOR_TYPE:
    242     case JS_FAST_HOLEY_DOUBLE_ARRAY_KEY_VALUE_ITERATOR_TYPE:
    243     case JS_GENERIC_ARRAY_KEY_VALUE_ITERATOR_TYPE:
    244     case JS_UINT8_ARRAY_VALUE_ITERATOR_TYPE:
    245     case JS_INT8_ARRAY_VALUE_ITERATOR_TYPE:
    246     case JS_UINT16_ARRAY_VALUE_ITERATOR_TYPE:
    247     case JS_INT16_ARRAY_VALUE_ITERATOR_TYPE:
    248     case JS_UINT32_ARRAY_VALUE_ITERATOR_TYPE:
    249     case JS_INT32_ARRAY_VALUE_ITERATOR_TYPE:
    250     case JS_FLOAT32_ARRAY_VALUE_ITERATOR_TYPE:
    251     case JS_FLOAT64_ARRAY_VALUE_ITERATOR_TYPE:
    252     case JS_UINT8_CLAMPED_ARRAY_VALUE_ITERATOR_TYPE:
    253     case JS_FAST_SMI_ARRAY_VALUE_ITERATOR_TYPE:
    254     case JS_FAST_HOLEY_SMI_ARRAY_VALUE_ITERATOR_TYPE:
    255     case JS_FAST_ARRAY_VALUE_ITERATOR_TYPE:
    256     case JS_FAST_HOLEY_ARRAY_VALUE_ITERATOR_TYPE:
    257     case JS_FAST_DOUBLE_ARRAY_VALUE_ITERATOR_TYPE:
    258     case JS_FAST_HOLEY_DOUBLE_ARRAY_VALUE_ITERATOR_TYPE:
    259     case JS_GENERIC_ARRAY_VALUE_ITERATOR_TYPE:
    260 
    261     case JS_WEAK_MAP_TYPE:
    262     case JS_WEAK_SET_TYPE:
    263     case JS_PROMISE_CAPABILITY_TYPE:
    264     case JS_PROMISE_TYPE:
    265     case JS_BOUND_FUNCTION_TYPE:
    266       DCHECK(!map->is_undetectable());
    267       return kOtherObject;
    268     case JS_FUNCTION_TYPE:
    269       DCHECK(!map->is_undetectable());
    270       return kFunction;
    271     case JS_PROXY_TYPE:
    272       DCHECK(!map->is_undetectable());
    273       return kProxy;
    274     case MAP_TYPE:
    275     case ALLOCATION_SITE_TYPE:
    276     case ACCESSOR_INFO_TYPE:
    277     case SHARED_FUNCTION_INFO_TYPE:
    278     case ACCESSOR_PAIR_TYPE:
    279     case FIXED_ARRAY_TYPE:
    280     case FIXED_DOUBLE_ARRAY_TYPE:
    281     case BYTE_ARRAY_TYPE:
    282     case BYTECODE_ARRAY_TYPE:
    283     case TRANSITION_ARRAY_TYPE:
    284     case FOREIGN_TYPE:
    285     case SCRIPT_TYPE:
    286     case CODE_TYPE:
    287     case PROPERTY_CELL_TYPE:
    288     case MODULE_TYPE:
    289     case MODULE_INFO_ENTRY_TYPE:
    290       return kOtherInternal & kTaggedPointer;
    291 
    292     // Remaining instance types are unsupported for now. If any of them do
    293     // require bit set types, they should get kOtherInternal & kTaggedPointer.
    294     case MUTABLE_HEAP_NUMBER_TYPE:
    295     case FREE_SPACE_TYPE:
    296 #define FIXED_TYPED_ARRAY_CASE(Type, type, TYPE, ctype, size) \
    297   case FIXED_##TYPE##_ARRAY_TYPE:
    298 
    299       TYPED_ARRAYS(FIXED_TYPED_ARRAY_CASE)
    300 #undef FIXED_TYPED_ARRAY_CASE
    301     case FILLER_TYPE:
    302     case ACCESS_CHECK_INFO_TYPE:
    303     case INTERCEPTOR_INFO_TYPE:
    304     case CALL_HANDLER_INFO_TYPE:
    305     case PROMISE_RESOLVE_THENABLE_JOB_INFO_TYPE:
    306     case PROMISE_REACTION_JOB_INFO_TYPE:
    307     case FUNCTION_TEMPLATE_INFO_TYPE:
    308     case OBJECT_TEMPLATE_INFO_TYPE:
    309     case ALLOCATION_MEMENTO_TYPE:
    310     case TYPE_FEEDBACK_INFO_TYPE:
    311     case ALIASED_ARGUMENTS_ENTRY_TYPE:
    312     case DEBUG_INFO_TYPE:
    313     case BREAK_POINT_INFO_TYPE:
    314     case CELL_TYPE:
    315     case WEAK_CELL_TYPE:
    316     case PROTOTYPE_INFO_TYPE:
    317     case TUPLE2_TYPE:
    318     case TUPLE3_TYPE:
    319     case CONTEXT_EXTENSION_TYPE:
    320     case CONSTANT_ELEMENTS_PAIR_TYPE:
    321       UNREACHABLE();
    322       return kNone;
    323   }
    324   UNREACHABLE();
    325   return kNone;
    326 }
    327 
    328 AstType::bitset AstBitsetType::Lub(i::Object* value) {
    329   DisallowHeapAllocation no_allocation;
    330   if (value->IsNumber()) {
    331     return Lub(value->Number()) &
    332            (value->IsSmi() ? kTaggedSigned : kTaggedPointer);
    333   }
    334   return Lub(i::HeapObject::cast(value)->map());
    335 }
    336 
    337 AstType::bitset AstBitsetType::Lub(double value) {
    338   DisallowHeapAllocation no_allocation;
    339   if (i::IsMinusZero(value)) return kMinusZero;
    340   if (std::isnan(value)) return kNaN;
    341   if (IsUint32Double(value) || IsInt32Double(value)) return Lub(value, value);
    342   return kOtherNumber;
    343 }
    344 
    345 // Minimum values of plain numeric bitsets.
    346 const AstBitsetType::Boundary AstBitsetType::BoundariesArray[] = {
    347     {kOtherNumber, kPlainNumber, -V8_INFINITY},
    348     {kOtherSigned32, kNegative32, kMinInt},
    349     {kNegative31, kNegative31, -0x40000000},
    350     {kUnsigned30, kUnsigned30, 0},
    351     {kOtherUnsigned31, kUnsigned31, 0x40000000},
    352     {kOtherUnsigned32, kUnsigned32, 0x80000000},
    353     {kOtherNumber, kPlainNumber, static_cast<double>(kMaxUInt32) + 1}};
    354 
    355 const AstBitsetType::Boundary* AstBitsetType::Boundaries() {
    356   return BoundariesArray;
    357 }
    358 
    359 size_t AstBitsetType::BoundariesSize() {
    360   // Windows doesn't like arraysize here.
    361   // return arraysize(BoundariesArray);
    362   return 7;
    363 }
    364 
    365 AstType::bitset AstBitsetType::ExpandInternals(AstType::bitset bits) {
    366   DisallowHeapAllocation no_allocation;
    367   if (!(bits & AST_SEMANTIC(kPlainNumber))) return bits;  // Shortcut.
    368   const Boundary* boundaries = Boundaries();
    369   for (size_t i = 0; i < BoundariesSize(); ++i) {
    370     DCHECK(AstBitsetType::Is(boundaries[i].internal, boundaries[i].external));
    371     if (bits & AST_SEMANTIC(boundaries[i].internal))
    372       bits |= AST_SEMANTIC(boundaries[i].external);
    373   }
    374   return bits;
    375 }
    376 
    377 AstType::bitset AstBitsetType::Lub(double min, double max) {
    378   DisallowHeapAllocation no_allocation;
    379   int lub = kNone;
    380   const Boundary* mins = Boundaries();
    381 
    382   for (size_t i = 1; i < BoundariesSize(); ++i) {
    383     if (min < mins[i].min) {
    384       lub |= mins[i - 1].internal;
    385       if (max < mins[i].min) return lub;
    386     }
    387   }
    388   return lub | mins[BoundariesSize() - 1].internal;
    389 }
    390 
    391 AstType::bitset AstBitsetType::NumberBits(bitset bits) {
    392   return AST_SEMANTIC(bits & kPlainNumber);
    393 }
    394 
    395 AstType::bitset AstBitsetType::Glb(double min, double max) {
    396   DisallowHeapAllocation no_allocation;
    397   int glb = kNone;
    398   const Boundary* mins = Boundaries();
    399 
    400   // If the range does not touch 0, the bound is empty.
    401   if (max < -1 || min > 0) return glb;
    402 
    403   for (size_t i = 1; i + 1 < BoundariesSize(); ++i) {
    404     if (min <= mins[i].min) {
    405       if (max + 1 < mins[i + 1].min) break;
    406       glb |= mins[i].external;
    407     }
    408   }
    409   // OtherNumber also contains float numbers, so it can never be
    410   // in the greatest lower bound.
    411   return glb & ~(AST_SEMANTIC(kOtherNumber));
    412 }
    413 
    414 double AstBitsetType::Min(bitset bits) {
    415   DisallowHeapAllocation no_allocation;
    416   DCHECK(Is(AST_SEMANTIC(bits), kNumber));
    417   const Boundary* mins = Boundaries();
    418   bool mz = AST_SEMANTIC(bits & kMinusZero);
    419   for (size_t i = 0; i < BoundariesSize(); ++i) {
    420     if (Is(AST_SEMANTIC(mins[i].internal), bits)) {
    421       return mz ? std::min(0.0, mins[i].min) : mins[i].min;
    422     }
    423   }
    424   if (mz) return 0;
    425   return std::numeric_limits<double>::quiet_NaN();
    426 }
    427 
    428 double AstBitsetType::Max(bitset bits) {
    429   DisallowHeapAllocation no_allocation;
    430   DCHECK(Is(AST_SEMANTIC(bits), kNumber));
    431   const Boundary* mins = Boundaries();
    432   bool mz = AST_SEMANTIC(bits & kMinusZero);
    433   if (AstBitsetType::Is(AST_SEMANTIC(mins[BoundariesSize() - 1].internal),
    434                         bits)) {
    435     return +V8_INFINITY;
    436   }
    437   for (size_t i = BoundariesSize() - 1; i-- > 0;) {
    438     if (Is(AST_SEMANTIC(mins[i].internal), bits)) {
    439       return mz ? std::max(0.0, mins[i + 1].min - 1) : mins[i + 1].min - 1;
    440     }
    441   }
    442   if (mz) return 0;
    443   return std::numeric_limits<double>::quiet_NaN();
    444 }
    445 
    446 // -----------------------------------------------------------------------------
    447 // Predicates.
    448 
    449 bool AstType::SimplyEquals(AstType* that) {
    450   DisallowHeapAllocation no_allocation;
    451   if (this->IsClass()) {
    452     return that->IsClass() &&
    453            *this->AsClass()->Map() == *that->AsClass()->Map();
    454   }
    455   if (this->IsConstant()) {
    456     return that->IsConstant() &&
    457            *this->AsConstant()->Value() == *that->AsConstant()->Value();
    458   }
    459   if (this->IsContext()) {
    460     return that->IsContext() &&
    461            this->AsContext()->Outer()->Equals(that->AsContext()->Outer());
    462   }
    463   if (this->IsArray()) {
    464     return that->IsArray() &&
    465            this->AsArray()->Element()->Equals(that->AsArray()->Element());
    466   }
    467   if (this->IsFunction()) {
    468     if (!that->IsFunction()) return false;
    469     AstFunctionType* this_fun = this->AsFunction();
    470     AstFunctionType* that_fun = that->AsFunction();
    471     if (this_fun->Arity() != that_fun->Arity() ||
    472         !this_fun->Result()->Equals(that_fun->Result()) ||
    473         !this_fun->Receiver()->Equals(that_fun->Receiver())) {
    474       return false;
    475     }
    476     for (int i = 0, n = this_fun->Arity(); i < n; ++i) {
    477       if (!this_fun->Parameter(i)->Equals(that_fun->Parameter(i))) return false;
    478     }
    479     return true;
    480   }
    481   if (this->IsTuple()) {
    482     if (!that->IsTuple()) return false;
    483     AstTupleType* this_tuple = this->AsTuple();
    484     AstTupleType* that_tuple = that->AsTuple();
    485     if (this_tuple->Arity() != that_tuple->Arity()) {
    486       return false;
    487     }
    488     for (int i = 0, n = this_tuple->Arity(); i < n; ++i) {
    489       if (!this_tuple->Element(i)->Equals(that_tuple->Element(i))) return false;
    490     }
    491     return true;
    492   }
    493   UNREACHABLE();
    494   return false;
    495 }
    496 
    497 AstType::bitset AstType::Representation() {
    498   return AST_REPRESENTATION(this->BitsetLub());
    499 }
    500 
    501 // Check if [this] <= [that].
    502 bool AstType::SlowIs(AstType* that) {
    503   DisallowHeapAllocation no_allocation;
    504 
    505   // Fast bitset cases
    506   if (that->IsBitset()) {
    507     return AstBitsetType::Is(this->BitsetLub(), that->AsBitset());
    508   }
    509 
    510   if (this->IsBitset()) {
    511     return AstBitsetType::Is(this->AsBitset(), that->BitsetGlb());
    512   }
    513 
    514   // Check the representations.
    515   if (!AstBitsetType::Is(Representation(), that->Representation())) {
    516     return false;
    517   }
    518 
    519   // Check the semantic part.
    520   return SemanticIs(that);
    521 }
    522 
    523 // Check if AST_SEMANTIC([this]) <= AST_SEMANTIC([that]). The result of the
    524 // method
    525 // should be independent of the representation axis of the types.
    526 bool AstType::SemanticIs(AstType* that) {
    527   DisallowHeapAllocation no_allocation;
    528 
    529   if (this == that) return true;
    530 
    531   if (that->IsBitset()) {
    532     return AstBitsetType::Is(AST_SEMANTIC(this->BitsetLub()), that->AsBitset());
    533   }
    534   if (this->IsBitset()) {
    535     return AstBitsetType::Is(AST_SEMANTIC(this->AsBitset()), that->BitsetGlb());
    536   }
    537 
    538   // (T1 \/ ... \/ Tn) <= T  if  (T1 <= T) /\ ... /\ (Tn <= T)
    539   if (this->IsUnion()) {
    540     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
    541       if (!this->AsUnion()->Get(i)->SemanticIs(that)) return false;
    542     }
    543     return true;
    544   }
    545 
    546   // T <= (T1 \/ ... \/ Tn)  if  (T <= T1) \/ ... \/ (T <= Tn)
    547   if (that->IsUnion()) {
    548     for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
    549       if (this->SemanticIs(that->AsUnion()->Get(i))) return true;
    550       if (i > 1 && this->IsRange()) return false;  // Shortcut.
    551     }
    552     return false;
    553   }
    554 
    555   if (that->IsRange()) {
    556     return (this->IsRange() && Contains(that->AsRange(), this->AsRange())) ||
    557            (this->IsConstant() &&
    558             Contains(that->AsRange(), this->AsConstant()));
    559   }
    560   if (this->IsRange()) return false;
    561 
    562   return this->SimplyEquals(that);
    563 }
    564 
    565 // Most precise _current_ type of a value (usually its class).
    566 AstType* AstType::NowOf(i::Object* value, Zone* zone) {
    567   if (value->IsSmi() ||
    568       i::HeapObject::cast(value)->map()->instance_type() == HEAP_NUMBER_TYPE) {
    569     return Of(value, zone);
    570   }
    571   return Class(i::handle(i::HeapObject::cast(value)->map()), zone);
    572 }
    573 
    574 bool AstType::NowContains(i::Object* value) {
    575   DisallowHeapAllocation no_allocation;
    576   if (this->IsAny()) return true;
    577   if (value->IsHeapObject()) {
    578     i::Map* map = i::HeapObject::cast(value)->map();
    579     for (Iterator<i::Map> it = this->Classes(); !it.Done(); it.Advance()) {
    580       if (*it.Current() == map) return true;
    581     }
    582   }
    583   return this->Contains(value);
    584 }
    585 
    586 bool AstType::NowIs(AstType* that) {
    587   DisallowHeapAllocation no_allocation;
    588 
    589   // TODO(rossberg): this is incorrect for
    590   //   Union(Constant(V), T)->NowIs(Class(M))
    591   // but fuzzing does not cover that!
    592   if (this->IsConstant()) {
    593     i::Object* object = *this->AsConstant()->Value();
    594     if (object->IsHeapObject()) {
    595       i::Map* map = i::HeapObject::cast(object)->map();
    596       for (Iterator<i::Map> it = that->Classes(); !it.Done(); it.Advance()) {
    597         if (*it.Current() == map) return true;
    598       }
    599     }
    600   }
    601   return this->Is(that);
    602 }
    603 
    604 // Check if [this] contains only (currently) stable classes.
    605 bool AstType::NowStable() {
    606   DisallowHeapAllocation no_allocation;
    607   return !this->IsClass() || this->AsClass()->Map()->is_stable();
    608 }
    609 
    610 // Check if [this] and [that] overlap.
    611 bool AstType::Maybe(AstType* that) {
    612   DisallowHeapAllocation no_allocation;
    613 
    614   // Take care of the representation part (and also approximate
    615   // the semantic part).
    616   if (!AstBitsetType::IsInhabited(this->BitsetLub() & that->BitsetLub()))
    617     return false;
    618 
    619   return SemanticMaybe(that);
    620 }
    621 
    622 bool AstType::SemanticMaybe(AstType* that) {
    623   DisallowHeapAllocation no_allocation;
    624 
    625   // (T1 \/ ... \/ Tn) overlaps T  if  (T1 overlaps T) \/ ... \/ (Tn overlaps T)
    626   if (this->IsUnion()) {
    627     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
    628       if (this->AsUnion()->Get(i)->SemanticMaybe(that)) return true;
    629     }
    630     return false;
    631   }
    632 
    633   // T overlaps (T1 \/ ... \/ Tn)  if  (T overlaps T1) \/ ... \/ (T overlaps Tn)
    634   if (that->IsUnion()) {
    635     for (int i = 0, n = that->AsUnion()->Length(); i < n; ++i) {
    636       if (this->SemanticMaybe(that->AsUnion()->Get(i))) return true;
    637     }
    638     return false;
    639   }
    640 
    641   if (!AstBitsetType::SemanticIsInhabited(this->BitsetLub() &
    642                                           that->BitsetLub()))
    643     return false;
    644 
    645   if (this->IsBitset() && that->IsBitset()) return true;
    646 
    647   if (this->IsClass() != that->IsClass()) return true;
    648 
    649   if (this->IsRange()) {
    650     if (that->IsConstant()) {
    651       return Contains(this->AsRange(), that->AsConstant());
    652     }
    653     if (that->IsRange()) {
    654       return Overlap(this->AsRange(), that->AsRange());
    655     }
    656     if (that->IsBitset()) {
    657       bitset number_bits = AstBitsetType::NumberBits(that->AsBitset());
    658       if (number_bits == AstBitsetType::kNone) {
    659         return false;
    660       }
    661       double min = std::max(AstBitsetType::Min(number_bits), this->Min());
    662       double max = std::min(AstBitsetType::Max(number_bits), this->Max());
    663       return min <= max;
    664     }
    665   }
    666   if (that->IsRange()) {
    667     return that->SemanticMaybe(this);  // This case is handled above.
    668   }
    669 
    670   if (this->IsBitset() || that->IsBitset()) return true;
    671 
    672   return this->SimplyEquals(that);
    673 }
    674 
    675 // Return the range in [this], or [NULL].
    676 AstType* AstType::GetRange() {
    677   DisallowHeapAllocation no_allocation;
    678   if (this->IsRange()) return this;
    679   if (this->IsUnion() && this->AsUnion()->Get(1)->IsRange()) {
    680     return this->AsUnion()->Get(1);
    681   }
    682   return NULL;
    683 }
    684 
    685 bool AstType::Contains(i::Object* value) {
    686   DisallowHeapAllocation no_allocation;
    687   for (Iterator<i::Object> it = this->Constants(); !it.Done(); it.Advance()) {
    688     if (*it.Current() == value) return true;
    689   }
    690   if (IsInteger(value)) {
    691     AstType* range = this->GetRange();
    692     if (range != NULL && Contains(range->AsRange(), value)) return true;
    693   }
    694   return AstBitsetType::New(AstBitsetType::Lub(value))->Is(this);
    695 }
    696 
    697 bool AstUnionType::Wellformed() {
    698   DisallowHeapAllocation no_allocation;
    699   // This checks the invariants of the union representation:
    700   // 1. There are at least two elements.
    701   // 2. The first element is a bitset, no other element is a bitset.
    702   // 3. At most one element is a range, and it must be the second one.
    703   // 4. No element is itself a union.
    704   // 5. No element (except the bitset) is a subtype of any other.
    705   // 6. If there is a range, then the bitset type does not contain
    706   //    plain number bits.
    707   DCHECK(this->Length() >= 2);       // (1)
    708   DCHECK(this->Get(0)->IsBitset());  // (2a)
    709 
    710   for (int i = 0; i < this->Length(); ++i) {
    711     if (i != 0) DCHECK(!this->Get(i)->IsBitset());  // (2b)
    712     if (i != 1) DCHECK(!this->Get(i)->IsRange());   // (3)
    713     DCHECK(!this->Get(i)->IsUnion());               // (4)
    714     for (int j = 0; j < this->Length(); ++j) {
    715       if (i != j && i != 0)
    716         DCHECK(!this->Get(i)->SemanticIs(this->Get(j)));  // (5)
    717     }
    718   }
    719   DCHECK(!this->Get(1)->IsRange() ||
    720          (AstBitsetType::NumberBits(this->Get(0)->AsBitset()) ==
    721           AstBitsetType::kNone));  // (6)
    722   return true;
    723 }
    724 
    725 // -----------------------------------------------------------------------------
    726 // Union and intersection
    727 
    728 static bool AddIsSafe(int x, int y) {
    729   return x >= 0 ? y <= std::numeric_limits<int>::max() - x
    730                 : y >= std::numeric_limits<int>::min() - x;
    731 }
    732 
    733 AstType* AstType::Intersect(AstType* type1, AstType* type2, Zone* zone) {
    734   // Fast case: bit sets.
    735   if (type1->IsBitset() && type2->IsBitset()) {
    736     return AstBitsetType::New(type1->AsBitset() & type2->AsBitset());
    737   }
    738 
    739   // Fast case: top or bottom types.
    740   if (type1->IsNone() || type2->IsAny()) return type1;  // Shortcut.
    741   if (type2->IsNone() || type1->IsAny()) return type2;  // Shortcut.
    742 
    743   // Semi-fast case.
    744   if (type1->Is(type2)) return type1;
    745   if (type2->Is(type1)) return type2;
    746 
    747   // Slow case: create union.
    748 
    749   // Figure out the representation of the result first.
    750   // The rest of the method should not change this representation and
    751   // it should not make any decisions based on representations (i.e.,
    752   // it should only use the semantic part of types).
    753   const bitset representation =
    754       type1->Representation() & type2->Representation();
    755 
    756   // Semantic subtyping check - this is needed for consistency with the
    757   // semi-fast case above - we should behave the same way regardless of
    758   // representations. Intersection with a universal bitset should only update
    759   // the representations.
    760   if (type1->SemanticIs(type2)) {
    761     type2 = Any();
    762   } else if (type2->SemanticIs(type1)) {
    763     type1 = Any();
    764   }
    765 
    766   bitset bits =
    767       AST_SEMANTIC(type1->BitsetGlb() & type2->BitsetGlb()) | representation;
    768   int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
    769   int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
    770   if (!AddIsSafe(size1, size2)) return Any();
    771   int size = size1 + size2;
    772   if (!AddIsSafe(size, 2)) return Any();
    773   size += 2;
    774   AstType* result_type = AstUnionType::New(size, zone);
    775   AstUnionType* result = result_type->AsUnion();
    776   size = 0;
    777 
    778   // Deal with bitsets.
    779   result->Set(size++, AstBitsetType::New(bits));
    780 
    781   AstRangeType::Limits lims = AstRangeType::Limits::Empty();
    782   size = IntersectAux(type1, type2, result, size, &lims, zone);
    783 
    784   // If the range is not empty, then insert it into the union and
    785   // remove the number bits from the bitset.
    786   if (!lims.IsEmpty()) {
    787     size = UpdateRange(AstRangeType::New(lims, representation, zone), result,
    788                        size, zone);
    789 
    790     // Remove the number bits.
    791     bitset number_bits = AstBitsetType::NumberBits(bits);
    792     bits &= ~number_bits;
    793     result->Set(0, AstBitsetType::New(bits));
    794   }
    795   return NormalizeUnion(result_type, size, zone);
    796 }
    797 
    798 int AstType::UpdateRange(AstType* range, AstUnionType* result, int size,
    799                          Zone* zone) {
    800   if (size == 1) {
    801     result->Set(size++, range);
    802   } else {
    803     // Make space for the range.
    804     result->Set(size++, result->Get(1));
    805     result->Set(1, range);
    806   }
    807 
    808   // Remove any components that just got subsumed.
    809   for (int i = 2; i < size;) {
    810     if (result->Get(i)->SemanticIs(range)) {
    811       result->Set(i, result->Get(--size));
    812     } else {
    813       ++i;
    814     }
    815   }
    816   return size;
    817 }
    818 
    819 AstRangeType::Limits AstType::ToLimits(bitset bits, Zone* zone) {
    820   bitset number_bits = AstBitsetType::NumberBits(bits);
    821 
    822   if (number_bits == AstBitsetType::kNone) {
    823     return AstRangeType::Limits::Empty();
    824   }
    825 
    826   return AstRangeType::Limits(AstBitsetType::Min(number_bits),
    827                               AstBitsetType::Max(number_bits));
    828 }
    829 
    830 AstRangeType::Limits AstType::IntersectRangeAndBitset(AstType* range,
    831                                                       AstType* bitset,
    832                                                       Zone* zone) {
    833   AstRangeType::Limits range_lims(range->AsRange());
    834   AstRangeType::Limits bitset_lims = ToLimits(bitset->AsBitset(), zone);
    835   return AstRangeType::Limits::Intersect(range_lims, bitset_lims);
    836 }
    837 
    838 int AstType::IntersectAux(AstType* lhs, AstType* rhs, AstUnionType* result,
    839                           int size, AstRangeType::Limits* lims, Zone* zone) {
    840   if (lhs->IsUnion()) {
    841     for (int i = 0, n = lhs->AsUnion()->Length(); i < n; ++i) {
    842       size =
    843           IntersectAux(lhs->AsUnion()->Get(i), rhs, result, size, lims, zone);
    844     }
    845     return size;
    846   }
    847   if (rhs->IsUnion()) {
    848     for (int i = 0, n = rhs->AsUnion()->Length(); i < n; ++i) {
    849       size =
    850           IntersectAux(lhs, rhs->AsUnion()->Get(i), result, size, lims, zone);
    851     }
    852     return size;
    853   }
    854 
    855   if (!AstBitsetType::SemanticIsInhabited(lhs->BitsetLub() &
    856                                           rhs->BitsetLub())) {
    857     return size;
    858   }
    859 
    860   if (lhs->IsRange()) {
    861     if (rhs->IsBitset()) {
    862       AstRangeType::Limits lim = IntersectRangeAndBitset(lhs, rhs, zone);
    863 
    864       if (!lim.IsEmpty()) {
    865         *lims = AstRangeType::Limits::Union(lim, *lims);
    866       }
    867       return size;
    868     }
    869     if (rhs->IsClass()) {
    870       *lims = AstRangeType::Limits::Union(AstRangeType::Limits(lhs->AsRange()),
    871                                           *lims);
    872     }
    873     if (rhs->IsConstant() && Contains(lhs->AsRange(), rhs->AsConstant())) {
    874       return AddToUnion(rhs, result, size, zone);
    875     }
    876     if (rhs->IsRange()) {
    877       AstRangeType::Limits lim =
    878           AstRangeType::Limits::Intersect(AstRangeType::Limits(lhs->AsRange()),
    879                                           AstRangeType::Limits(rhs->AsRange()));
    880       if (!lim.IsEmpty()) {
    881         *lims = AstRangeType::Limits::Union(lim, *lims);
    882       }
    883     }
    884     return size;
    885   }
    886   if (rhs->IsRange()) {
    887     // This case is handled symmetrically above.
    888     return IntersectAux(rhs, lhs, result, size, lims, zone);
    889   }
    890   if (lhs->IsBitset() || rhs->IsBitset()) {
    891     return AddToUnion(lhs->IsBitset() ? rhs : lhs, result, size, zone);
    892   }
    893   if (lhs->IsClass() != rhs->IsClass()) {
    894     return AddToUnion(lhs->IsClass() ? rhs : lhs, result, size, zone);
    895   }
    896   if (lhs->SimplyEquals(rhs)) {
    897     return AddToUnion(lhs, result, size, zone);
    898   }
    899   return size;
    900 }
    901 
    902 // Make sure that we produce a well-formed range and bitset:
    903 // If the range is non-empty, the number bits in the bitset should be
    904 // clear. Moreover, if we have a canonical range (such as Signed32),
    905 // we want to produce a bitset rather than a range.
    906 AstType* AstType::NormalizeRangeAndBitset(AstType* range, bitset* bits,
    907                                           Zone* zone) {
    908   // Fast path: If the bitset does not mention numbers, we can just keep the
    909   // range.
    910   bitset number_bits = AstBitsetType::NumberBits(*bits);
    911   if (number_bits == 0) {
    912     return range;
    913   }
    914 
    915   // If the range is semantically contained within the bitset, return None and
    916   // leave the bitset untouched.
    917   bitset range_lub = AST_SEMANTIC(range->BitsetLub());
    918   if (AstBitsetType::Is(range_lub, *bits)) {
    919     return None();
    920   }
    921 
    922   // Slow path: reconcile the bitset range and the range.
    923   double bitset_min = AstBitsetType::Min(number_bits);
    924   double bitset_max = AstBitsetType::Max(number_bits);
    925 
    926   double range_min = range->Min();
    927   double range_max = range->Max();
    928 
    929   // Remove the number bits from the bitset, they would just confuse us now.
    930   // NOTE: bits contains OtherNumber iff bits contains PlainNumber, in which
    931   // case we already returned after the subtype check above.
    932   *bits &= ~number_bits;
    933 
    934   if (range_min <= bitset_min && range_max >= bitset_max) {
    935     // Bitset is contained within the range, just return the range.
    936     return range;
    937   }
    938 
    939   if (bitset_min < range_min) {
    940     range_min = bitset_min;
    941   }
    942   if (bitset_max > range_max) {
    943     range_max = bitset_max;
    944   }
    945   return AstRangeType::New(range_min, range_max, AstBitsetType::kNone, zone);
    946 }
    947 
    948 AstType* AstType::Union(AstType* type1, AstType* type2, Zone* zone) {
    949   // Fast case: bit sets.
    950   if (type1->IsBitset() && type2->IsBitset()) {
    951     return AstBitsetType::New(type1->AsBitset() | type2->AsBitset());
    952   }
    953 
    954   // Fast case: top or bottom types.
    955   if (type1->IsAny() || type2->IsNone()) return type1;
    956   if (type2->IsAny() || type1->IsNone()) return type2;
    957 
    958   // Semi-fast case.
    959   if (type1->Is(type2)) return type2;
    960   if (type2->Is(type1)) return type1;
    961 
    962   // Figure out the representation of the result.
    963   // The rest of the method should not change this representation and
    964   // it should not make any decisions based on representations (i.e.,
    965   // it should only use the semantic part of types).
    966   const bitset representation =
    967       type1->Representation() | type2->Representation();
    968 
    969   // Slow case: create union.
    970   int size1 = type1->IsUnion() ? type1->AsUnion()->Length() : 1;
    971   int size2 = type2->IsUnion() ? type2->AsUnion()->Length() : 1;
    972   if (!AddIsSafe(size1, size2)) return Any();
    973   int size = size1 + size2;
    974   if (!AddIsSafe(size, 2)) return Any();
    975   size += 2;
    976   AstType* result_type = AstUnionType::New(size, zone);
    977   AstUnionType* result = result_type->AsUnion();
    978   size = 0;
    979 
    980   // Compute the new bitset.
    981   bitset new_bitset = AST_SEMANTIC(type1->BitsetGlb() | type2->BitsetGlb());
    982 
    983   // Deal with ranges.
    984   AstType* range = None();
    985   AstType* range1 = type1->GetRange();
    986   AstType* range2 = type2->GetRange();
    987   if (range1 != NULL && range2 != NULL) {
    988     AstRangeType::Limits lims =
    989         AstRangeType::Limits::Union(AstRangeType::Limits(range1->AsRange()),
    990                                     AstRangeType::Limits(range2->AsRange()));
    991     AstType* union_range = AstRangeType::New(lims, representation, zone);
    992     range = NormalizeRangeAndBitset(union_range, &new_bitset, zone);
    993   } else if (range1 != NULL) {
    994     range = NormalizeRangeAndBitset(range1, &new_bitset, zone);
    995   } else if (range2 != NULL) {
    996     range = NormalizeRangeAndBitset(range2, &new_bitset, zone);
    997   }
    998   new_bitset = AST_SEMANTIC(new_bitset) | representation;
    999   AstType* bits = AstBitsetType::New(new_bitset);
   1000   result->Set(size++, bits);
   1001   if (!range->IsNone()) result->Set(size++, range);
   1002 
   1003   size = AddToUnion(type1, result, size, zone);
   1004   size = AddToUnion(type2, result, size, zone);
   1005   return NormalizeUnion(result_type, size, zone);
   1006 }
   1007 
   1008 // Add [type] to [result] unless [type] is bitset, range, or already subsumed.
   1009 // Return new size of [result].
   1010 int AstType::AddToUnion(AstType* type, AstUnionType* result, int size,
   1011                         Zone* zone) {
   1012   if (type->IsBitset() || type->IsRange()) return size;
   1013   if (type->IsUnion()) {
   1014     for (int i = 0, n = type->AsUnion()->Length(); i < n; ++i) {
   1015       size = AddToUnion(type->AsUnion()->Get(i), result, size, zone);
   1016     }
   1017     return size;
   1018   }
   1019   for (int i = 0; i < size; ++i) {
   1020     if (type->SemanticIs(result->Get(i))) return size;
   1021   }
   1022   result->Set(size++, type);
   1023   return size;
   1024 }
   1025 
   1026 AstType* AstType::NormalizeUnion(AstType* union_type, int size, Zone* zone) {
   1027   AstUnionType* unioned = union_type->AsUnion();
   1028   DCHECK(size >= 1);
   1029   DCHECK(unioned->Get(0)->IsBitset());
   1030   // If the union has just one element, return it.
   1031   if (size == 1) {
   1032     return unioned->Get(0);
   1033   }
   1034   bitset bits = unioned->Get(0)->AsBitset();
   1035   // If the union only consists of a range, we can get rid of the union.
   1036   if (size == 2 && AST_SEMANTIC(bits) == AstBitsetType::kNone) {
   1037     bitset representation = AST_REPRESENTATION(bits);
   1038     if (representation == unioned->Get(1)->Representation()) {
   1039       return unioned->Get(1);
   1040     }
   1041     if (unioned->Get(1)->IsRange()) {
   1042       return AstRangeType::New(unioned->Get(1)->AsRange()->Min(),
   1043                                unioned->Get(1)->AsRange()->Max(),
   1044                                unioned->Get(0)->AsBitset(), zone);
   1045     }
   1046   }
   1047   unioned->Shrink(size);
   1048   SLOW_DCHECK(unioned->Wellformed());
   1049   return union_type;
   1050 }
   1051 
   1052 // -----------------------------------------------------------------------------
   1053 // Component extraction
   1054 
   1055 // static
   1056 AstType* AstType::Representation(AstType* t, Zone* zone) {
   1057   return AstBitsetType::New(t->Representation());
   1058 }
   1059 
   1060 // static
   1061 AstType* AstType::Semantic(AstType* t, Zone* zone) {
   1062   return Intersect(t, AstBitsetType::New(AstBitsetType::kSemantic), zone);
   1063 }
   1064 
   1065 // -----------------------------------------------------------------------------
   1066 // Iteration.
   1067 
   1068 int AstType::NumClasses() {
   1069   DisallowHeapAllocation no_allocation;
   1070   if (this->IsClass()) {
   1071     return 1;
   1072   } else if (this->IsUnion()) {
   1073     int result = 0;
   1074     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
   1075       if (this->AsUnion()->Get(i)->IsClass()) ++result;
   1076     }
   1077     return result;
   1078   } else {
   1079     return 0;
   1080   }
   1081 }
   1082 
   1083 int AstType::NumConstants() {
   1084   DisallowHeapAllocation no_allocation;
   1085   if (this->IsConstant()) {
   1086     return 1;
   1087   } else if (this->IsUnion()) {
   1088     int result = 0;
   1089     for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
   1090       if (this->AsUnion()->Get(i)->IsConstant()) ++result;
   1091     }
   1092     return result;
   1093   } else {
   1094     return 0;
   1095   }
   1096 }
   1097 
   1098 template <class T>
   1099 AstType* AstType::Iterator<T>::get_type() {
   1100   DCHECK(!Done());
   1101   return type_->IsUnion() ? type_->AsUnion()->Get(index_) : type_;
   1102 }
   1103 
   1104 // C++ cannot specialise nested templates, so we have to go through this
   1105 // contortion with an auxiliary template to simulate it.
   1106 template <class T>
   1107 struct TypeImplIteratorAux {
   1108   static bool matches(AstType* type);
   1109   static i::Handle<T> current(AstType* type);
   1110 };
   1111 
   1112 template <>
   1113 struct TypeImplIteratorAux<i::Map> {
   1114   static bool matches(AstType* type) { return type->IsClass(); }
   1115   static i::Handle<i::Map> current(AstType* type) {
   1116     return type->AsClass()->Map();
   1117   }
   1118 };
   1119 
   1120 template <>
   1121 struct TypeImplIteratorAux<i::Object> {
   1122   static bool matches(AstType* type) { return type->IsConstant(); }
   1123   static i::Handle<i::Object> current(AstType* type) {
   1124     return type->AsConstant()->Value();
   1125   }
   1126 };
   1127 
   1128 template <class T>
   1129 bool AstType::Iterator<T>::matches(AstType* type) {
   1130   return TypeImplIteratorAux<T>::matches(type);
   1131 }
   1132 
   1133 template <class T>
   1134 i::Handle<T> AstType::Iterator<T>::Current() {
   1135   return TypeImplIteratorAux<T>::current(get_type());
   1136 }
   1137 
   1138 template <class T>
   1139 void AstType::Iterator<T>::Advance() {
   1140   DisallowHeapAllocation no_allocation;
   1141   ++index_;
   1142   if (type_->IsUnion()) {
   1143     for (int n = type_->AsUnion()->Length(); index_ < n; ++index_) {
   1144       if (matches(type_->AsUnion()->Get(index_))) return;
   1145     }
   1146   } else if (index_ == 0 && matches(type_)) {
   1147     return;
   1148   }
   1149   index_ = -1;
   1150 }
   1151 
   1152 // -----------------------------------------------------------------------------
   1153 // Printing.
   1154 
   1155 const char* AstBitsetType::Name(bitset bits) {
   1156   switch (bits) {
   1157     case AST_REPRESENTATION(kAny):
   1158       return "Any";
   1159 #define RETURN_NAMED_REPRESENTATION_TYPE(type, value) \
   1160   case AST_REPRESENTATION(k##type):                   \
   1161     return #type;
   1162       AST_REPRESENTATION_BITSET_TYPE_LIST(RETURN_NAMED_REPRESENTATION_TYPE)
   1163 #undef RETURN_NAMED_REPRESENTATION_TYPE
   1164 
   1165 #define RETURN_NAMED_SEMANTIC_TYPE(type, value) \
   1166   case AST_SEMANTIC(k##type):                   \
   1167     return #type;
   1168       AST_SEMANTIC_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE)
   1169       AST_INTERNAL_BITSET_TYPE_LIST(RETURN_NAMED_SEMANTIC_TYPE)
   1170 #undef RETURN_NAMED_SEMANTIC_TYPE
   1171 
   1172     default:
   1173       return NULL;
   1174   }
   1175 }
   1176 
   1177 void AstBitsetType::Print(std::ostream& os,  // NOLINT
   1178                           bitset bits) {
   1179   DisallowHeapAllocation no_allocation;
   1180   const char* name = Name(bits);
   1181   if (name != NULL) {
   1182     os << name;
   1183     return;
   1184   }
   1185 
   1186   // clang-format off
   1187   static const bitset named_bitsets[] = {
   1188 #define BITSET_CONSTANT(type, value) AST_REPRESENTATION(k##type),
   1189     AST_REPRESENTATION_BITSET_TYPE_LIST(BITSET_CONSTANT)
   1190 #undef BITSET_CONSTANT
   1191 
   1192 #define BITSET_CONSTANT(type, value) AST_SEMANTIC(k##type),
   1193     AST_INTERNAL_BITSET_TYPE_LIST(BITSET_CONSTANT)
   1194     AST_SEMANTIC_BITSET_TYPE_LIST(BITSET_CONSTANT)
   1195 #undef BITSET_CONSTANT
   1196   };
   1197   // clang-format on
   1198 
   1199   bool is_first = true;
   1200   os << "(";
   1201   for (int i(arraysize(named_bitsets) - 1); bits != 0 && i >= 0; --i) {
   1202     bitset subset = named_bitsets[i];
   1203     if ((bits & subset) == subset) {
   1204       if (!is_first) os << " | ";
   1205       is_first = false;
   1206       os << Name(subset);
   1207       bits -= subset;
   1208     }
   1209   }
   1210   DCHECK(bits == 0);
   1211   os << ")";
   1212 }
   1213 
   1214 void AstType::PrintTo(std::ostream& os, PrintDimension dim) {
   1215   DisallowHeapAllocation no_allocation;
   1216   if (dim != REPRESENTATION_DIM) {
   1217     if (this->IsBitset()) {
   1218       AstBitsetType::Print(os, AST_SEMANTIC(this->AsBitset()));
   1219     } else if (this->IsClass()) {
   1220       os << "Class(" << static_cast<void*>(*this->AsClass()->Map()) << " < ";
   1221       AstBitsetType::New(AstBitsetType::Lub(this))->PrintTo(os, dim);
   1222       os << ")";
   1223     } else if (this->IsConstant()) {
   1224       os << "Constant(" << Brief(*this->AsConstant()->Value()) << ")";
   1225     } else if (this->IsRange()) {
   1226       std::ostream::fmtflags saved_flags = os.setf(std::ios::fixed);
   1227       std::streamsize saved_precision = os.precision(0);
   1228       os << "Range(" << this->AsRange()->Min() << ", " << this->AsRange()->Max()
   1229          << ")";
   1230       os.flags(saved_flags);
   1231       os.precision(saved_precision);
   1232     } else if (this->IsContext()) {
   1233       os << "Context(";
   1234       this->AsContext()->Outer()->PrintTo(os, dim);
   1235       os << ")";
   1236     } else if (this->IsUnion()) {
   1237       os << "(";
   1238       for (int i = 0, n = this->AsUnion()->Length(); i < n; ++i) {
   1239         AstType* type_i = this->AsUnion()->Get(i);
   1240         if (i > 0) os << " | ";
   1241         type_i->PrintTo(os, dim);
   1242       }
   1243       os << ")";
   1244     } else if (this->IsArray()) {
   1245       os << "Array(";
   1246       AsArray()->Element()->PrintTo(os, dim);
   1247       os << ")";
   1248     } else if (this->IsFunction()) {
   1249       if (!this->AsFunction()->Receiver()->IsAny()) {
   1250         this->AsFunction()->Receiver()->PrintTo(os, dim);
   1251         os << ".";
   1252       }
   1253       os << "(";
   1254       for (int i = 0; i < this->AsFunction()->Arity(); ++i) {
   1255         if (i > 0) os << ", ";
   1256         this->AsFunction()->Parameter(i)->PrintTo(os, dim);
   1257       }
   1258       os << ")->";
   1259       this->AsFunction()->Result()->PrintTo(os, dim);
   1260     } else if (this->IsTuple()) {
   1261       os << "<";
   1262       for (int i = 0, n = this->AsTuple()->Arity(); i < n; ++i) {
   1263         AstType* type_i = this->AsTuple()->Element(i);
   1264         if (i > 0) os << ", ";
   1265         type_i->PrintTo(os, dim);
   1266       }
   1267       os << ">";
   1268     } else {
   1269       UNREACHABLE();
   1270     }
   1271   }
   1272   if (dim == BOTH_DIMS) os << "/";
   1273   if (dim != SEMANTIC_DIM) {
   1274     AstBitsetType::Print(os, AST_REPRESENTATION(this->BitsetLub()));
   1275   }
   1276 }
   1277 
   1278 #ifdef DEBUG
   1279 void AstType::Print() {
   1280   OFStream os(stdout);
   1281   PrintTo(os);
   1282   os << std::endl;
   1283 }
   1284 void AstBitsetType::Print(bitset bits) {
   1285   OFStream os(stdout);
   1286   Print(os, bits);
   1287   os << std::endl;
   1288 }
   1289 #endif
   1290 
   1291 AstBitsetType::bitset AstBitsetType::SignedSmall() {
   1292   return i::SmiValuesAre31Bits() ? kSigned31 : kSigned32;
   1293 }
   1294 
   1295 AstBitsetType::bitset AstBitsetType::UnsignedSmall() {
   1296   return i::SmiValuesAre31Bits() ? kUnsigned30 : kUnsigned31;
   1297 }
   1298 
   1299 // -----------------------------------------------------------------------------
   1300 // Instantiations.
   1301 
   1302 template class AstType::Iterator<i::Map>;
   1303 template class AstType::Iterator<i::Object>;
   1304 
   1305 }  // namespace internal
   1306 }  // namespace v8
   1307