1 /**
2 * Copyright (c) 2021-2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "verification/type/type_type.h"
17
18 #include "verification/type/type_system.h"
19 #include "verification/util/mem.h"
20
21 namespace panda::verifier {
22 using Builtin = Type::Builtin;
23
24 // NOLINTBEGIN(fuchsia-statically-constructed-objects,readability-identifier-naming)
25 namespace {
26
27 std::array<std::string, Builtin::LAST> builtin_names = {
28 "*undefined*", "top", "u1", "i8", "u8", "i16", "u16", "i32",
29 "u32", "f32", "f64", "i64", "u64", "integral8", "integral16", "integral32",
30 "integral64", "float32", "float64", "bits32", "bits64", "primitive", "reference", "null_reference",
31 "object", "type_class", "array", "bot"};
32
Bitmap(std::initializer_list<Builtin> vs)33 constexpr uint32_t Bitmap(std::initializer_list<Builtin> vs)
34 {
35 uint32_t result = 0;
36 for (auto v : vs) {
37 result |= 1U << v;
38 }
39 return result;
40 }
41
42 template <size_t SZ>
TransitiveClosure(std::array<uint32_t,SZ> const * source)43 std::array<uint32_t, SZ> TransitiveClosure(std::array<uint32_t, SZ> const *source)
44 {
45 std::array<uint32_t, SZ> result = *source;
46 for (size_t i = 0; i < SZ; i++) {
47 result[i] |= Bitmap({Builtin {i}});
48 }
49
50 bool changed = true;
51 while (changed) {
52 changed = false;
53 for (size_t i = 0; i < SZ; i++) {
54 uint32_t pre = result[i];
55 uint32_t post = pre;
56 for (size_t j = 0; j < SZ; j++) {
57 if ((post & Bitmap({Builtin {j}})) != 0) {
58 post |= result[j];
59 }
60 }
61 if (post != pre) {
62 result[i] = post;
63 changed = true;
64 }
65 }
66 }
67 return result;
68 }
69
70 std::array<uint32_t, Builtin::LAST> builtin_supertypes_nontrans = {
71 0, // undefined
72 0, // top
73 Bitmap({Builtin::U8, Builtin::I8}), // u1
74 Bitmap({Builtin::I16, Builtin::INTEGRAL8}), // i8
75 Bitmap({Builtin::U16, Builtin::I16, Builtin::INTEGRAL8}), // u8
76 Bitmap({Builtin::I32, Builtin::INTEGRAL16}), // i16
77 Bitmap({Builtin::I32, Builtin::U32, Builtin::INTEGRAL16}), // u16
78 Bitmap({Builtin::INTEGRAL32}), // i32
79 Bitmap({Builtin::INTEGRAL32}), // u32
80 Bitmap({Builtin::FLOAT32}), // f32
81 Bitmap({Builtin::FLOAT64}), // f64
82 Bitmap({Builtin::INTEGRAL64}), // i64
83 Bitmap({Builtin::INTEGRAL64}), // u64
84 Bitmap({Builtin::INTEGRAL16}), // integral8
85 Bitmap({Builtin::INTEGRAL32}), // integral16
86 Bitmap({Builtin::BITS32}), // integral32
87 Bitmap({Builtin::BITS64}), // integral64
88 Bitmap({Builtin::BITS32}), // float32
89 Bitmap({Builtin::BITS64}), // float64
90 Bitmap({Builtin::PRIMITIVE}), // bits32
91 Bitmap({Builtin::PRIMITIVE}), // bits64
92 Bitmap({Builtin::TOP}), // primitive
93 Bitmap({Builtin::TOP}), // reference
94 Bitmap({Builtin::REFERENCE, Builtin::OBJECT, Builtin::TYPE_CLASS, Builtin::ARRAY}), // null_reference
95 Bitmap({Builtin::REFERENCE}), // object
96 Bitmap({Builtin::REFERENCE}), // type_class
97 Bitmap({Builtin::OBJECT}), // array
98 Bitmap({Builtin::U1, Builtin::I8, Builtin::U8, Builtin::I16, Builtin::U16, Builtin::I32, Builtin::U32, Builtin::F32,
99 Builtin::F64, Builtin::I64, Builtin::U64, Builtin::NULL_REFERENCE, Builtin::OBJECT,
100 Builtin::ARRAY})}; // bot
101
102 std::array<uint32_t, Builtin::LAST> builtin_supertypes = TransitiveClosure(&builtin_supertypes_nontrans);
103
BuildBuiltinLeastUpperBounds(std::array<uint32_t,Builtin::LAST> const & supertypes)104 std::array<std::array<Builtin, Builtin::LAST>, Builtin::LAST> BuildBuiltinLeastUpperBounds(
105 std::array<uint32_t, Builtin::LAST> const &supertypes)
106 {
107 std::array<std::array<Builtin, Builtin::LAST>, Builtin::LAST> result {};
108 // Ignore ununsed index 0
109 for (size_t lhs = 1; lhs < Builtin::LAST; lhs++) {
110 for (size_t rhs = 1; rhs < lhs; rhs++) {
111 Builtin candidate = Builtin::TOP;
112 uint32_t supertype_bits = supertypes[lhs] & supertypes[rhs];
113 for (size_t cc = 1; cc < Builtin::LAST; cc++) {
114 if ((supertype_bits & Bitmap({Builtin {cc}})) != 0 && (supertypes[cc] & Bitmap({candidate})) != 0) {
115 candidate = Builtin {cc};
116 }
117 }
118 result[lhs][rhs] = candidate;
119 result[rhs][lhs] = candidate;
120 }
121 result[lhs][lhs] = Builtin {lhs};
122 }
123 return result;
124 }
125
126 std::array<std::array<Builtin, Builtin::LAST>, Builtin::LAST> builtin_lub =
127 BuildBuiltinLeastUpperBounds(builtin_supertypes);
128
129 using ClassSubtypingCheckFun = bool (*)(Class const *);
130
AlwaysTrue(Class const * _)131 bool AlwaysTrue([[maybe_unused]] Class const *_)
132 {
133 return true;
134 }
135
IsClassArray(Class const * klass)136 bool IsClassArray(Class const *klass)
137 {
138 return klass->IsArrayClass();
139 }
140
IsClassClass(Class const * klass)141 bool IsClassClass(Class const *klass)
142 {
143 return klass->IsClassClass();
144 }
145
IsObjectClass(Class const * klass)146 bool IsObjectClass(Class const *klass)
147 {
148 return klass->IsObjectClass();
149 }
150
151 struct ClassSubtypingFuns {
152 ClassSubtypingCheckFun isBuiltinSupertypeOfClass;
153 ClassSubtypingCheckFun isClassSupertypeOfBuiltin;
154 };
155
156 std::array<ClassSubtypingFuns, Builtin::LAST> class_subtyping_funs {
157 ClassSubtypingFuns {nullptr, nullptr}, // undefined
158 ClassSubtypingFuns {AlwaysTrue, nullptr}, // top
159 ClassSubtypingFuns {nullptr, nullptr}, // u1
160 ClassSubtypingFuns {nullptr, nullptr}, // i8
161 ClassSubtypingFuns {nullptr, nullptr}, // u8
162 ClassSubtypingFuns {nullptr, nullptr}, // i16
163 ClassSubtypingFuns {nullptr, nullptr}, // u16
164 ClassSubtypingFuns {nullptr, nullptr}, // i32
165 ClassSubtypingFuns {nullptr, nullptr}, // u32
166 ClassSubtypingFuns {nullptr, nullptr}, // f32
167 ClassSubtypingFuns {nullptr, nullptr}, // f64
168 ClassSubtypingFuns {nullptr, nullptr}, // i64
169 ClassSubtypingFuns {nullptr, nullptr}, // u64
170 ClassSubtypingFuns {nullptr, nullptr}, // integral8
171 ClassSubtypingFuns {nullptr, nullptr}, // integral16
172 ClassSubtypingFuns {nullptr, nullptr}, // integral32
173 ClassSubtypingFuns {nullptr, nullptr}, // integral64
174 ClassSubtypingFuns {nullptr, nullptr}, // float32
175 ClassSubtypingFuns {nullptr, nullptr}, // float64
176 ClassSubtypingFuns {nullptr, nullptr}, // bits32
177 ClassSubtypingFuns {nullptr, nullptr}, // bits64
178 ClassSubtypingFuns {nullptr, nullptr}, // primitive
179 ClassSubtypingFuns {AlwaysTrue, nullptr}, // reference
180 ClassSubtypingFuns {nullptr, AlwaysTrue}, // null_reference
181 ClassSubtypingFuns {AlwaysTrue, IsObjectClass}, // object
182 ClassSubtypingFuns {IsClassClass, nullptr}, // type_class
183 ClassSubtypingFuns {IsClassArray, nullptr}, // array
184 ClassSubtypingFuns {nullptr, AlwaysTrue}}; // bot
185
InvariantHolds(Type tp,TypeSystem const * tsys)186 [[maybe_unused]] bool InvariantHolds(Type tp, TypeSystem const *tsys)
187 {
188 if (tp.IsBuiltin() || tp.IsClass()) {
189 return true;
190 }
191 if (tp.IsIntersection()) {
192 auto members = tp.GetIntersectionMembers(tsys);
193 if (members.size() < 2UL) {
194 return false;
195 }
196 for (auto mtp : members) {
197 if (mtp.IsIntersection() || mtp.IsUnion() || mtp == Type {Builtin::BOT} || mtp == Type {Builtin::TOP}) {
198 return false;
199 }
200 }
201 return true;
202 }
203 if (tp.IsUnion()) {
204 auto members = tp.GetUnionMembers(tsys);
205 if (members.size() < 2UL) {
206 return false;
207 }
208 for (auto mtp : members) {
209 if (mtp.IsUnion() || mtp == Type {Builtin::TOP} || mtp == Type {Builtin::BOT}) {
210 return false;
211 }
212 }
213 return true;
214 }
215 UNREACHABLE();
216 }
217
218 } // namespace
219 // NOLINTEND(fuchsia-statically-constructed-objects,readability-identifier-naming)
220
221 // Careful: span is invalidated whenever a new intersection or union is created.
GetIntersectionMembers(TypeSystem const * tsys) const222 Span<Type const> Type::GetIntersectionMembers(TypeSystem const *tsys) const
223 {
224 ASSERT(IsIntersection());
225 uintptr_t payload = GetPayload(content_);
226 return tsys->GetTypeSpan(SpanIndex(payload), SpanSize(payload));
227 }
228
229 // Careful: span is invalidated whenever a new intersection or union is created.
GetUnionMembers(TypeSystem const * tsys) const230 Span<Type const> Type::GetUnionMembers(TypeSystem const *tsys) const
231 {
232 ASSERT(IsUnion());
233 uintptr_t payload = GetPayload(content_);
234 return tsys->GetTypeSpan(SpanIndex(payload), SpanSize(payload));
235 }
236
IsConsistent() const237 bool Type::IsConsistent() const
238 {
239 if (IsNone()) {
240 return false;
241 }
242 if (IsBuiltin()) {
243 return GetBuiltin() != Builtin::TOP;
244 }
245 return true;
246 }
247
ToString(TypeSystem const * tsys) const248 PandaString Type::ToString(TypeSystem const *tsys) const
249 {
250 if (IsNone()) {
251 return "<none>";
252 }
253 if (IsBuiltin()) {
254 return PandaString(builtin_names[GetBuiltin()]);
255 }
256 if (IsClass()) {
257 auto const *klass = GetClass();
258 if (klass->IsArrayClass()) {
259 ASSERT(klass->GetComponentType() != nullptr);
260 return (Type {klass->GetComponentType()}).ToString(tsys) + "[]";
261 }
262 return PandaString {klass->GetName()};
263 }
264 std::stringstream ss;
265 if (IsIntersection()) {
266 auto members = GetIntersectionMembers(tsys);
267 ASSERT(!members.empty());
268 ss << "(";
269 bool first = true;
270 for (auto t : members) {
271 if (!first) {
272 ss << " & ";
273 } else {
274 first = false;
275 }
276 ss << t.ToString(tsys);
277 }
278 ss << ")";
279 return PandaString(ss.str());
280 }
281 if (IsUnion()) {
282 auto members = GetUnionMembers(tsys);
283 ASSERT(!members.empty());
284 ss << "(";
285 bool first = true;
286 for (auto t : members) {
287 if (!first) {
288 ss << " | ";
289 } else {
290 first = false;
291 }
292 ss << t.ToString(tsys);
293 }
294 ss << ")";
295 return PandaString(ss.str());
296 }
297 return "<unexpected kind of AbstractType>";
298 }
299
ToTypeId() const300 panda_file::Type::TypeId Type::ToTypeId() const
301 {
302 using TypeId = panda_file::Type::TypeId;
303 if (!IsBuiltin()) {
304 return TypeId::INVALID;
305 }
306 switch (GetBuiltin()) {
307 case Builtin::TOP:
308 return TypeId::VOID;
309 case Builtin::U1:
310 return TypeId::U1;
311 case Builtin::I8:
312 return TypeId::I8;
313 case Builtin::U8:
314 return TypeId::U8;
315 case Builtin::I16:
316 return TypeId::I16;
317 case Builtin::U16:
318 return TypeId::U16;
319 case Builtin::I32:
320 return TypeId::I32;
321 case Builtin::U32:
322 return TypeId::U32;
323 case Builtin::F32:
324 return TypeId::F32;
325 case Builtin::F64:
326 return TypeId::F64;
327 case Builtin::I64:
328 return TypeId::I64;
329 case Builtin::U64:
330 return TypeId::U64;
331 default:
332 return TypeId::INVALID;
333 }
334 }
335
GetTypeWidth() const336 size_t Type::GetTypeWidth() const
337 {
338 using TypeId = panda_file::Type::TypeId;
339 auto typeId = ToTypeId();
340 if (typeId != TypeId::INVALID) {
341 return panda_file::Type(typeId).GetBitWidth();
342 }
343 switch (GetBuiltin()) {
344 case Builtin::INTEGRAL8:
345 return coretypes::INT8_BITS;
346 case Builtin::INTEGRAL16:
347 return coretypes::INT16_BITS;
348 case Builtin::INTEGRAL32:
349 case Builtin::FLOAT32:
350 case Builtin::BITS32:
351 return coretypes::INT32_BITS;
352 case Builtin::INTEGRAL64:
353 case Builtin::FLOAT64:
354 case Builtin::BITS64:
355 return coretypes::INT64_BITS;
356 case Builtin::REFERENCE:
357 case Builtin::NULL_REFERENCE:
358 return 0;
359 default:
360 UNREACHABLE();
361 }
362 }
363
FromTypeId(panda_file::Type::TypeId tid)364 Type Type::FromTypeId(panda_file::Type::TypeId tid)
365 {
366 using TypeId = panda_file::Type::TypeId;
367 switch (tid) {
368 case TypeId::VOID:
369 return Type {Builtin::TOP};
370 case TypeId::U1:
371 return Type {Builtin::U1};
372 case TypeId::I8:
373 return Type {Builtin::I8};
374 case TypeId::U8:
375 return Type {Builtin::U8};
376 case TypeId::I16:
377 return Type {Builtin::I16};
378 case TypeId::U16:
379 return Type {Builtin::U16};
380 case TypeId::I32:
381 return Type {Builtin::I32};
382 case TypeId::U32:
383 return Type {Builtin::U32};
384 case TypeId::F32:
385 return Type {Builtin::F32};
386 case TypeId::F64:
387 return Type {Builtin::F64};
388 case TypeId::I64:
389 return Type {Builtin::I64};
390 case TypeId::U64:
391 return Type {Builtin::U64};
392 case TypeId::REFERENCE:
393 return Type {Builtin::REFERENCE};
394 default:
395 UNREACHABLE();
396 }
397 }
398
CopySpanToTypeSystem(Span<Type> span,TypeSystem * tsys)399 static Span<Type> CopySpanToTypeSystem(Span<Type> span, TypeSystem *tsys)
400 {
401 Span<Type> dest = tsys->GetNewTypeSpan(span.size());
402 std::copy(span.begin(), span.end(), dest.begin());
403 return dest;
404 }
405
406 /* static */
Intersection(Span<Type> span,TypeSystem * tsys)407 Type Type::Intersection(Span<Type> span, TypeSystem *tsys)
408 {
409 Span<Type> rspan = CopySpanToTypeSystem(span, tsys);
410 return Type {ConstructWithTag(INTERSECTION_TAG, ConstructPayload(rspan.size(), tsys->GetSpanIndex(rspan)))};
411 }
412
413 /* static */
Union(Span<Type> span,TypeSystem * tsys)414 Type Type::Union(Span<Type> span, TypeSystem *tsys)
415 {
416 Span<Type> rspan = CopySpanToTypeSystem(span, tsys);
417 return Type {ConstructWithTag(UNION_TAG, ConstructPayload(rspan.size(), tsys->GetSpanIndex(rspan)))};
418 }
419
IsClassSubtypeOfType(Class const * lhsClass,Type rhs,TypeSystem * tsys)420 static bool IsClassSubtypeOfType(Class const *lhsClass, Type rhs, TypeSystem *tsys)
421 {
422 // Deal with arrays; those are covariant
423 {
424 auto *lhsComponent = lhsClass->GetComponentType();
425 if (lhsComponent != nullptr) {
426 if (!rhs.IsClass() || rhs.GetClass()->GetComponentType() == nullptr) {
427 Type supertypeOfArray = tsys->SupertypeOfArray();
428 return supertypeOfArray.IsConsistent() && IsSubtype(supertypeOfArray, rhs, tsys);
429 }
430 auto *rhsComponent = rhs.GetClass()->GetComponentType();
431 auto rhsComponentType = Type {rhsComponent};
432 return IsClassSubtypeOfType(lhsComponent, rhsComponentType, tsys);
433 }
434 }
435
436 return tsys->SupertypesOfClass(lhsClass)->count(rhs) > 0;
437 }
438
IsSubtypeImpl(Type lhs,Type rhs,TypeSystem * tsys)439 bool IsSubtypeImpl(Type lhs, Type rhs, TypeSystem *tsys)
440 {
441 ASSERT(InvariantHolds(lhs, tsys));
442 ASSERT(InvariantHolds(rhs, tsys));
443 if (lhs.IsBuiltin() && rhs.IsBuiltin()) {
444 auto lhsBuiltin = lhs.GetBuiltin();
445 auto rhsBuiltin = rhs.GetBuiltin();
446 return (builtin_supertypes[lhsBuiltin] & Bitmap({rhsBuiltin})) != 0;
447 }
448 if (lhs.IsBuiltin() && rhs.IsClass()) {
449 auto lhsBuiltin = lhs.GetBuiltin();
450 auto rhsClass = rhs.GetClass();
451 auto *checker = class_subtyping_funs[lhsBuiltin].isClassSupertypeOfBuiltin;
452 return checker != nullptr && checker(rhsClass);
453 }
454 if (lhs.IsClass() && rhs.IsBuiltin()) {
455 auto const *lhsClass = lhs.GetClass();
456 auto rhsBuiltin = rhs.GetBuiltin();
457 auto *checker = class_subtyping_funs[rhsBuiltin].isBuiltinSupertypeOfClass;
458 return checker != nullptr && checker(lhsClass);
459 }
460 if (lhs.IsClass() && rhs.IsClass()) {
461 return IsClassSubtypeOfType(lhs.GetClass(), rhs, tsys);
462 }
463 if ((lhs.IsBuiltin() || lhs.IsClass()) && rhs.IsIntersection()) {
464 for (auto e : rhs.GetIntersectionMembers(tsys)) {
465 if (!IsSubtype(lhs, e, tsys)) {
466 return false;
467 }
468 }
469 return true;
470 }
471 if (lhs.IsIntersection() && (rhs.IsBuiltin() || rhs.IsClass())) {
472 for (auto e : lhs.GetIntersectionMembers(tsys)) {
473 if (IsSubtype(e, rhs, tsys)) {
474 return true;
475 }
476 }
477 return false;
478 }
479 if ((lhs.IsBuiltin() || lhs.IsClass()) && rhs.IsUnion()) {
480 for (auto e : rhs.GetUnionMembers(tsys)) {
481 if (IsSubtype(lhs, e, tsys)) {
482 return true;
483 }
484 }
485 return false;
486 }
487 if (lhs.IsUnion() && (rhs.IsBuiltin() || rhs.IsClass())) {
488 for (auto e : lhs.GetUnionMembers(tsys)) {
489 if (!IsSubtype(e, rhs, tsys)) {
490 return false;
491 }
492 }
493 return true;
494 }
495 ASSERT(lhs.IsUnion() || lhs.IsIntersection());
496 ASSERT(rhs.IsUnion() || rhs.IsIntersection());
497 if (rhs.IsIntersection()) {
498 for (auto e : rhs.GetIntersectionMembers(tsys)) {
499 if (!IsSubtype(lhs, e, tsys)) {
500 return false;
501 }
502 }
503 return true;
504 }
505 if (lhs.IsUnion()) {
506 for (auto e : lhs.GetUnionMembers(tsys)) {
507 if (!IsSubtype(e, rhs, tsys)) {
508 return false;
509 }
510 }
511 return true;
512 }
513 ASSERT(lhs.IsIntersection() && rhs.IsUnion());
514 for (auto e : rhs.GetUnionMembers(tsys)) {
515 if (IsSubtype(lhs, e, tsys)) {
516 return true;
517 }
518 }
519 return false;
520 }
521
IsIntersectionReasonable(Span<Type> members)522 static bool IsIntersectionReasonable(Span<Type> members)
523 {
524 #ifdef UNCOMMENT_WHEN_READY
525 // We know that none of the members is a subtype of any other.
526 bool have_builtins = false;
527 bool have_classes = false;
528
529 // Nothing is a subclass of both a class and a builtin (except NULL_POINTER and BOT).
530 for (auto const &mtp : *members) {
531 if (mtp.IsBuiltin()) {
532 have_builtins = true;
533 if (have_classes) {
534 return false;
535 }
536 } else {
537 ASSERT(mtp.IsClass());
538 have_classes = true;
539 if (have_builtins) {
540 return false;
541 }
542 }
543 }
544 #endif
545
546 // Java specific?
547 bool haveClass = false;
548 for (auto const &mtp : members) {
549 if (mtp.IsClass()) {
550 Class const *cls = mtp.GetClass();
551 if (cls->IsFinal()) {
552 // no meaningful intersection possible
553 return false;
554 }
555 if (!cls->IsInterface() && haveClass) {
556 // no memaningful intersection between classes,
557 // other than subtyping
558 return false;
559 }
560 if (!cls->IsInterface()) {
561 haveClass = true;
562 }
563 }
564 }
565 return true;
566 }
567
ToIntersectionSpan(Type const * tp,TypeSystem const * tsys)568 static Span<Type const> ToIntersectionSpan(Type const *tp, TypeSystem const *tsys)
569 {
570 if (tp->IsBuiltin() || tp->IsClass()) {
571 return Span {tp, 1};
572 }
573 if (tp->IsIntersection()) {
574 return tp->GetIntersectionMembers(tsys);
575 }
576 UNREACHABLE();
577 }
578
ToUnionSpan(Type const * tp,TypeSystem const * tsys)579 static Span<Type const> ToUnionSpan(Type const *tp, TypeSystem const *tsys)
580 {
581 if (tp->IsBuiltin() || tp->IsClass() || tp->IsIntersection()) {
582 return Span {tp, 1};
583 }
584 if (tp->IsUnion()) {
585 return tp->GetUnionMembers(tsys);
586 }
587 UNREACHABLE();
588 }
589
IntersectSpans(Span<Type const> lhs,Span<Type const> rhs,TypeSystem * tsys)590 Type Type::IntersectSpans(Span<Type const> lhs, Span<Type const> rhs, TypeSystem *tsys)
591 {
592 PandaVector<Type> res;
593
594 for (auto ltp : lhs) {
595 bool toInclude = true;
596 for (auto rtp : rhs) {
597 if (IsSubtype(rtp, ltp, tsys) && ltp != rtp) {
598 toInclude = false;
599 break;
600 }
601 }
602 if (toInclude) {
603 res.push_back(ltp);
604 }
605 }
606 for (auto rtp : rhs) {
607 bool toInclude = true;
608 for (auto ltp : lhs) {
609 if (IsSubtype(ltp, rtp, tsys)) {
610 toInclude = false;
611 break;
612 }
613 }
614 if (toInclude) {
615 res.push_back(rtp);
616 }
617 }
618 ASSERT(res.size() > 1); // otherwise would mean lhs <: rhs or rhs <: lhs
619 if (IsIntersectionReasonable(Span {res})) {
620 return Intersection(Span {res}, tsys);
621 }
622 return Type {Builtin::BOT};
623 }
624
TpIntersection(Type lhs,Type rhs,TypeSystem * tsys)625 Type TpIntersection(Type lhs, Type rhs, TypeSystem *tsys)
626 {
627 ASSERT(InvariantHolds(lhs, tsys));
628 ASSERT(InvariantHolds(rhs, tsys));
629 if (IsSubtype(lhs, rhs, tsys)) {
630 return lhs;
631 }
632 if (IsSubtype(rhs, lhs, tsys)) {
633 return rhs;
634 }
635 if (lhs.IsBuiltin() && rhs.IsBuiltin()) {
636 // No nontrivial intersections among builtins
637 return Type {Builtin::BOT};
638 }
639 if ((lhs.IsClass() || lhs.IsBuiltin()) && (rhs.IsClass() || lhs.IsBuiltin())) {
640 PandaVector<Type> res {lhs, rhs};
641 if (IsIntersectionReasonable(Span {res})) {
642 return Type::Intersection(Span {res}, tsys);
643 }
644 return Type {Builtin::BOT};
645 }
646
647 // Now at least one of the sides is at least an intersection
648 if (!lhs.IsUnion() && !rhs.IsUnion()) {
649 // they are also at most intersections.
650 // Spans are only invalidated before return form IntersectSpans.
651 return Type::IntersectSpans(ToIntersectionSpan(&lhs, tsys), ToIntersectionSpan(&rhs, tsys), tsys);
652 }
653
654 // At least one of the sides is a union.
655 // Spans will be invalidated in the course of building the intersection, so we need to copy them.
656 PandaUnorderedSet<Type> unionRes;
657 auto lhsSpan = ToUnionSpan(&lhs, tsys);
658 auto rhsSpan = ToUnionSpan(&rhs, tsys);
659 PandaVector<Type> lhsVec {lhsSpan.begin(), lhsSpan.end()};
660 PandaVector<Type> rhsVec {rhsSpan.begin(), rhsSpan.end()};
661
662 for (auto mLhs : lhsVec) {
663 for (auto mRhs : rhsVec) {
664 Type alt = TpIntersection(mLhs, mRhs, tsys);
665 if (alt != Type {Type::Builtin::BOT}) {
666 unionRes.insert(alt);
667 }
668 }
669 }
670 if (unionRes.empty()) {
671 return Type {Type::Builtin::BOT};
672 }
673 if (unionRes.size() == 1) {
674 return *unionRes.cbegin();
675 }
676 PandaVector<Type> unionResVec;
677 for (auto &m : unionRes) {
678 unionResVec.push_back(m);
679 }
680 return Type::Union(Span {unionResVec}, tsys);
681 }
682
TpUnion(Type lhs,Type rhs,TypeSystem * tsys)683 Type TpUnion(Type lhs, Type rhs, TypeSystem *tsys)
684 {
685 // return lhs for lhs==rhs case
686 if (IsSubtype(rhs, lhs, tsys)) {
687 return lhs;
688 }
689 if (IsSubtype(lhs, rhs, tsys)) {
690 return rhs;
691 }
692 if (lhs.IsBuiltin() && rhs.IsBuiltin()) {
693 return Type {builtin_lub[lhs.GetBuiltin()][rhs.GetBuiltin()]};
694 }
695 PandaVector<Type> unionRes;
696 auto lhsSpan = ToUnionSpan(&lhs, tsys);
697 auto rhsSpan = ToUnionSpan(&rhs, tsys);
698 for (auto mLhs : lhsSpan) {
699 bool toInclude = true;
700 for (auto mRhs : rhsSpan) {
701 if (IsSubtype(mLhs, mRhs, tsys) && mLhs != mRhs) {
702 toInclude = false;
703 break;
704 }
705 }
706 if (toInclude) {
707 unionRes.push_back(mLhs);
708 }
709 }
710 for (auto mRhs : rhsSpan) {
711 bool toInclude = true;
712 for (auto mLhs : lhsSpan) {
713 if (IsSubtype(mRhs, mLhs, tsys)) {
714 toInclude = false;
715 break;
716 }
717 }
718 if (toInclude) {
719 unionRes.push_back(mRhs);
720 }
721 }
722 ASSERT(unionRes.size() > 1);
723 return Type::Union(Span {unionRes}, tsys);
724 }
725
GetArrayElementType(TypeSystem * tsys) const726 Type Type::GetArrayElementType(TypeSystem *tsys) const
727 {
728 if (IsClass()) {
729 Class const *klass = GetClass();
730 if (klass->IsArrayClass()) {
731 auto *arrayComponent = klass->GetComponentType();
732 ASSERT(arrayComponent != nullptr);
733 return Type {arrayComponent};
734 }
735 return Top();
736 }
737 if (IsIntersection()) {
738 auto members = GetIntersectionMembers(tsys);
739 PandaVector<Type> vec;
740 for (auto m : members) {
741 vec.push_back(m.GetArrayElementType(tsys));
742 if (vec.back() == Top()) {
743 return Top();
744 }
745 }
746 // Reasonableness should already be encoded in reasonableness of members.
747 ASSERT(IsIntersectionReasonable(Span {vec}));
748 return Intersection(Span {vec}, tsys);
749 }
750 if (IsUnion()) {
751 // GetArrayElementType may invalidate span, so copy it.
752 auto membersSpan = GetUnionMembers(tsys);
753 PandaVector<Type> members {membersSpan.begin(), membersSpan.end()};
754 PandaVector<Type> vec;
755 for (auto m : members) {
756 vec.push_back(m.GetArrayElementType(tsys));
757 if (vec.back() == Top()) {
758 return Top();
759 }
760 }
761 return Union(Span {vec}, tsys);
762 }
763 return Top();
764 }
765 } // namespace panda::verifier
766