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
IsInteger(i::Object * x)20 bool AstType::IsInteger(i::Object* x) {
21 return x->IsNumber() && AstType::IsInteger(x->Number());
22 }
23
24 // -----------------------------------------------------------------------------
25 // Range-related helper functions.
26
IsEmpty()27 bool AstRangeType::Limits::IsEmpty() { return this->min > this->max; }
28
Intersect(Limits lhs,Limits rhs)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
Union(Limits lhs,Limits rhs)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
Overlap(AstRangeType * lhs,AstRangeType * rhs)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
Contains(AstRangeType * lhs,AstRangeType * rhs)54 bool AstType::Contains(AstRangeType* lhs, AstRangeType* rhs) {
55 DisallowHeapAllocation no_allocation;
56 return lhs->Min() <= rhs->Min() && rhs->Max() <= lhs->Max();
57 }
58
Contains(AstRangeType * lhs,AstConstantType * rhs)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
Contains(AstRangeType * range,i::Object * val)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
Min()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
Max()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.
Glb(AstType * 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.
Lub(AstType * type)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
Lub(i::Map * map)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
Lub(i::Object * value)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
Lub(double value)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
Boundaries()355 const AstBitsetType::Boundary* AstBitsetType::Boundaries() {
356 return BoundariesArray;
357 }
358
BoundariesSize()359 size_t AstBitsetType::BoundariesSize() {
360 // Windows doesn't like arraysize here.
361 // return arraysize(BoundariesArray);
362 return 7;
363 }
364
ExpandInternals(AstType::bitset bits)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
Lub(double min,double max)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
NumberBits(bitset bits)391 AstType::bitset AstBitsetType::NumberBits(bitset bits) {
392 return AST_SEMANTIC(bits & kPlainNumber);
393 }
394
Glb(double min,double max)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
Min(bitset bits)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
Max(bitset bits)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
SimplyEquals(AstType * that)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
Representation()497 AstType::bitset AstType::Representation() {
498 return AST_REPRESENTATION(this->BitsetLub());
499 }
500
501 // Check if [this] <= [that].
SlowIs(AstType * 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.
SemanticIs(AstType * that)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).
NowOf(i::Object * value,Zone * zone)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
NowContains(i::Object * value)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
NowIs(AstType * that)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.
NowStable()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.
Maybe(AstType * that)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
SemanticMaybe(AstType * that)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].
GetRange()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
Contains(i::Object * value)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
Wellformed()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
AddIsSafe(int x,int y)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
Intersect(AstType * type1,AstType * type2,Zone * zone)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
UpdateRange(AstType * range,AstUnionType * result,int size,Zone * zone)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
ToLimits(bitset bits,Zone * zone)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
IntersectRangeAndBitset(AstType * range,AstType * bitset,Zone * zone)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
IntersectAux(AstType * lhs,AstType * rhs,AstUnionType * result,int size,AstRangeType::Limits * lims,Zone * zone)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.
NormalizeRangeAndBitset(AstType * range,bitset * bits,Zone * zone)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
Union(AstType * type1,AstType * type2,Zone * zone)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].
AddToUnion(AstType * type,AstUnionType * result,int size,Zone * zone)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
NormalizeUnion(AstType * union_type,int size,Zone * zone)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
Representation(AstType * t,Zone * zone)1056 AstType* AstType::Representation(AstType* t, Zone* zone) {
1057 return AstBitsetType::New(t->Representation());
1058 }
1059
1060 // static
Semantic(AstType * t,Zone * zone)1061 AstType* AstType::Semantic(AstType* t, Zone* zone) {
1062 return Intersect(t, AstBitsetType::New(AstBitsetType::kSemantic), zone);
1063 }
1064
1065 // -----------------------------------------------------------------------------
1066 // Iteration.
1067
NumClasses()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
NumConstants()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>
get_type()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> {
matchesv8::internal::TypeImplIteratorAux1114 static bool matches(AstType* type) { return type->IsClass(); }
currentv8::internal::TypeImplIteratorAux1115 static i::Handle<i::Map> current(AstType* type) {
1116 return type->AsClass()->Map();
1117 }
1118 };
1119
1120 template <>
1121 struct TypeImplIteratorAux<i::Object> {
matchesv8::internal::TypeImplIteratorAux1122 static bool matches(AstType* type) { return type->IsConstant(); }
currentv8::internal::TypeImplIteratorAux1123 static i::Handle<i::Object> current(AstType* type) {
1124 return type->AsConstant()->Value();
1125 }
1126 };
1127
1128 template <class T>
matches(AstType * type)1129 bool AstType::Iterator<T>::matches(AstType* type) {
1130 return TypeImplIteratorAux<T>::matches(type);
1131 }
1132
1133 template <class T>
Current()1134 i::Handle<T> AstType::Iterator<T>::Current() {
1135 return TypeImplIteratorAux<T>::current(get_type());
1136 }
1137
1138 template <class T>
Advance()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
Name(bitset bits)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
Print(std::ostream & os,bitset bits)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
PrintTo(std::ostream & os,PrintDimension dim)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
Print()1279 void AstType::Print() {
1280 OFStream os(stdout);
1281 PrintTo(os);
1282 os << std::endl;
1283 }
Print(bitset bits)1284 void AstBitsetType::Print(bitset bits) {
1285 OFStream os(stdout);
1286 Print(os, bits);
1287 os << std::endl;
1288 }
1289 #endif
1290
SignedSmall()1291 AstBitsetType::bitset AstBitsetType::SignedSmall() {
1292 return i::SmiValuesAre31Bits() ? kSigned31 : kSigned32;
1293 }
1294
UnsignedSmall()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