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