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
462 // CC-OFFNXT(G.FUN.01, huge_cyclomatic_complexity, huge_method) solid logic
IsSubtypeImpl(Type lhs,Type rhs,TypeSystem * tsys)463 bool IsSubtypeImpl(Type lhs, Type rhs, TypeSystem *tsys)
464 {
465 ASSERT(InvariantHolds(lhs, tsys));
466 ASSERT(InvariantHolds(rhs, tsys));
467 if (lhs.IsBuiltin() && rhs.IsBuiltin()) {
468 auto lhsBuiltin = lhs.GetBuiltin();
469 auto rhsBuiltin = rhs.GetBuiltin();
470 return (builtin_supertypes[lhsBuiltin] & Bitmap({rhsBuiltin})) != 0;
471 }
472 if (lhs.IsBuiltin() && rhs.IsClass()) {
473 auto lhsBuiltin = lhs.GetBuiltin();
474 auto rhsClass = rhs.GetClass();
475 auto *checker = class_subtyping_funs[lhsBuiltin].is_class_supertype_of_builtin;
476 return checker != nullptr && checker(rhsClass);
477 }
478 if (lhs.IsClass() && rhs.IsBuiltin()) {
479 auto const *lhsClass = lhs.GetClass();
480 auto rhsBuiltin = rhs.GetBuiltin();
481 auto *checker = class_subtyping_funs[rhsBuiltin].is_builtin_supertype_of_class;
482 return checker != nullptr && checker(lhsClass);
483 }
484 if (lhs.IsClass() && rhs.IsClass()) {
485 return IsClassSubtypeOfType(lhs.GetClass(), rhs, tsys);
486 }
487 if ((lhs.IsBuiltin() || lhs.IsClass()) && rhs.IsIntersection()) {
488 for (auto e : rhs.GetIntersectionMembers(tsys)) {
489 if (!IsSubtype(lhs, e, tsys)) {
490 return false;
491 }
492 }
493 return true;
494 }
495 if (lhs.IsIntersection() && (rhs.IsBuiltin() || rhs.IsClass())) {
496 for (auto e : lhs.GetIntersectionMembers(tsys)) {
497 if (IsSubtype(e, rhs, tsys)) {
498 return true;
499 }
500 }
501 return false;
502 }
503 if ((lhs.IsBuiltin() || lhs.IsClass()) && rhs.IsUnion()) {
504 for (auto e : rhs.GetUnionMembers(tsys)) {
505 if (IsSubtype(lhs, e, tsys)) {
506 return true;
507 }
508 }
509 return false;
510 }
511 if (lhs.IsUnion() && (rhs.IsBuiltin() || rhs.IsClass())) {
512 for (auto e : lhs.GetUnionMembers(tsys)) {
513 if (!IsSubtype(e, rhs, tsys)) {
514 return false;
515 }
516 }
517 return true;
518 }
519 ASSERT(lhs.IsUnion() || lhs.IsIntersection());
520 ASSERT(rhs.IsUnion() || rhs.IsIntersection());
521 if (rhs.IsIntersection()) {
522 for (auto e : rhs.GetIntersectionMembers(tsys)) {
523 if (!IsSubtype(lhs, e, tsys)) {
524 return false;
525 }
526 }
527 return true;
528 }
529 if (lhs.IsUnion()) {
530 for (auto e : lhs.GetUnionMembers(tsys)) {
531 if (!IsSubtype(e, rhs, tsys)) {
532 return false;
533 }
534 }
535 return true;
536 }
537 ASSERT(lhs.IsIntersection() && rhs.IsUnion());
538 for (auto e : rhs.GetUnionMembers(tsys)) {
539 if (IsSubtype(lhs, e, tsys)) {
540 return true;
541 }
542 }
543 return false;
544 }
545
IsIntersectionReasonable(Span<Type> members)546 static bool IsIntersectionReasonable(Span<Type> members)
547 {
548 #ifdef UNCOMMENT_WHEN_READY
549 // We know that none of the members is a subtype of any other.
550 bool have_builtins = false;
551 bool have_classes = false;
552
553 // Nothing is a subclass of both a class and a builtin (except NULL_POINTER and BOT).
554 for (auto const &mtp : *members) {
555 if (mtp.IsBuiltin()) {
556 have_builtins = true;
557 if (have_classes) {
558 return false;
559 }
560 } else {
561 ASSERT(mtp.IsClass());
562 have_classes = true;
563 if (have_builtins) {
564 return false;
565 }
566 }
567 }
568 #endif
569
570 // Java specific?
571 bool haveClass = false;
572 for (auto const &mtp : members) {
573 if (mtp.IsClass()) {
574 Class const *cls = mtp.GetClass();
575 if (cls->IsFinal()) {
576 // no meaningful intersection possible
577 return false;
578 }
579 if (!cls->IsInterface() && haveClass) {
580 return false;
581 }
582 if (!cls->IsInterface()) {
583 haveClass = true;
584 }
585 }
586 }
587 return true;
588 }
589
ToIntersectionSpan(Type const * tp,TypeSystem const * tsys)590 static Span<Type const> ToIntersectionSpan(Type const *tp, TypeSystem const *tsys)
591 {
592 if (tp->IsBuiltin() || tp->IsClass()) {
593 return Span {tp, 1};
594 }
595 if (tp->IsIntersection()) {
596 return tp->GetIntersectionMembers(tsys);
597 }
598 UNREACHABLE();
599 }
600
ToUnionSpan(Type const * tp,TypeSystem const * tsys)601 static Span<Type const> ToUnionSpan(Type const *tp, TypeSystem const *tsys)
602 {
603 if (tp->IsBuiltin() || tp->IsClass() || tp->IsIntersection()) {
604 return Span {tp, 1};
605 }
606 if (tp->IsUnion()) {
607 return tp->GetUnionMembers(tsys);
608 }
609 UNREACHABLE();
610 }
611
IntersectSpans(Span<Type const> lhs,Span<Type const> rhs,TypeSystem * tsys)612 Type Type::IntersectSpans(Span<Type const> lhs, Span<Type const> rhs, TypeSystem *tsys)
613 {
614 PandaVector<Type> res;
615
616 for (auto ltp : lhs) {
617 bool toInclude = true;
618 for (auto rtp : rhs) {
619 if (IsSubtype(rtp, ltp, tsys) && ltp != rtp) {
620 toInclude = false;
621 break;
622 }
623 }
624 if (toInclude) {
625 res.push_back(ltp);
626 }
627 }
628 for (auto rtp : rhs) {
629 bool toInclude = true;
630 for (auto ltp : lhs) {
631 if (IsSubtype(ltp, rtp, tsys)) {
632 toInclude = false;
633 break;
634 }
635 }
636 if (toInclude) {
637 res.push_back(rtp);
638 }
639 }
640 ASSERT(res.size() > 1); // otherwise would mean lhs <: rhs or rhs <: lhs
641 if (IsIntersectionReasonable(Span {res})) {
642 return Intersection(Span {res}, tsys);
643 }
644 return Type {Builtin::BOT};
645 }
646
TpIntersection(Type lhs,Type rhs,TypeSystem * tsys)647 Type TpIntersection(Type lhs, Type rhs, TypeSystem *tsys)
648 {
649 ASSERT(InvariantHolds(lhs, tsys));
650 ASSERT(InvariantHolds(rhs, tsys));
651 if (IsSubtype(lhs, rhs, tsys)) {
652 return lhs;
653 }
654 if (IsSubtype(rhs, lhs, tsys)) {
655 return rhs;
656 }
657 if (lhs.IsBuiltin() && rhs.IsBuiltin()) {
658 // No nontrivial intersections among builtins
659 return Type {Builtin::BOT};
660 }
661 if ((lhs.IsClass() || lhs.IsBuiltin()) && (rhs.IsClass() || lhs.IsBuiltin())) {
662 PandaVector<Type> res {lhs, rhs};
663 if (IsIntersectionReasonable(Span {res})) {
664 return Type::Intersection(Span {res}, tsys);
665 }
666 return Type {Builtin::BOT};
667 }
668
669 // Now at least one of the sides is at least an intersection
670 if (!lhs.IsUnion() && !rhs.IsUnion()) {
671 // they are also at most intersections.
672 // Spans are only invalidated before return form IntersectSpans.
673 return Type::IntersectSpans(ToIntersectionSpan(&lhs, tsys), ToIntersectionSpan(&rhs, tsys), tsys);
674 }
675
676 // At least one of the sides is a union.
677 // Spans will be invalidated in the course of building the intersection, so we need to copy them.
678 PandaUnorderedSet<Type> unionRes;
679 auto lhsSpan = ToUnionSpan(&lhs, tsys);
680 auto rhsSpan = ToUnionSpan(&rhs, tsys);
681 PandaVector<Type> lhsVec {lhsSpan.begin(), lhsSpan.end()};
682 PandaVector<Type> rhsVec {rhsSpan.begin(), rhsSpan.end()};
683
684 for (auto mLhs : lhsVec) {
685 for (auto mRhs : rhsVec) {
686 Type alt = TpIntersection(mLhs, mRhs, tsys);
687 if (alt != Type {Type::Builtin::BOT}) {
688 unionRes.insert(alt);
689 }
690 }
691 }
692 if (unionRes.empty()) {
693 return Type {Type::Builtin::BOT};
694 }
695 if (unionRes.size() == 1) {
696 return *unionRes.cbegin();
697 }
698 PandaVector<Type> unionResVec;
699 for (auto &m : unionRes) {
700 unionResVec.push_back(m);
701 }
702 return Type::Union(Span {unionResVec}, tsys);
703 }
704
TpUnion(Type lhs,Type rhs,TypeSystem * tsys)705 Type TpUnion(Type lhs, Type rhs, TypeSystem *tsys)
706 {
707 // return lhs for lhs==rhs case
708 if (IsSubtype(rhs, lhs, tsys)) {
709 return lhs;
710 }
711 if (IsSubtype(lhs, rhs, tsys)) {
712 return rhs;
713 }
714 if (lhs.IsBuiltin() && rhs.IsBuiltin()) {
715 return Type {builtin_lub[lhs.GetBuiltin()][rhs.GetBuiltin()]};
716 }
717 PandaVector<Type> unionRes;
718 auto lhsSpan = ToUnionSpan(&lhs, tsys);
719 auto rhsSpan = ToUnionSpan(&rhs, tsys);
720 for (auto mLhs : lhsSpan) {
721 bool toInclude = true;
722 for (auto mRhs : rhsSpan) {
723 if (IsSubtype(mLhs, mRhs, tsys) && mLhs != mRhs) {
724 toInclude = false;
725 break;
726 }
727 }
728 if (toInclude) {
729 unionRes.push_back(mLhs);
730 }
731 }
732 for (auto mRhs : rhsSpan) {
733 bool toInclude = true;
734 for (auto mLhs : lhsSpan) {
735 if (IsSubtype(mRhs, mLhs, tsys)) {
736 toInclude = false;
737 break;
738 }
739 }
740 if (toInclude) {
741 unionRes.push_back(mRhs);
742 }
743 }
744 ASSERT(unionRes.size() > 1);
745 return Type::Union(Span {unionRes}, tsys);
746 }
747
GetArrayElementType(TypeSystem * tsys) const748 Type Type::GetArrayElementType(TypeSystem *tsys) const
749 {
750 if (IsClass()) {
751 Class const *klass = GetClass();
752 if (klass->IsArrayClass()) {
753 auto *arrayComponent = klass->GetComponentType();
754 ASSERT(arrayComponent != nullptr);
755 return Type {arrayComponent};
756 }
757 return Top();
758 }
759 if (IsIntersection()) {
760 auto members = GetIntersectionMembers(tsys);
761 PandaVector<Type> vec;
762 for (auto m : members) {
763 vec.push_back(m.GetArrayElementType(tsys));
764 if (vec.back() == Top()) {
765 return Top();
766 }
767 }
768 // Reasonableness should already be encoded in reasonableness of members.
769 ASSERT(IsIntersectionReasonable(Span {vec}));
770 return Intersection(Span {vec}, tsys);
771 }
772 if (IsUnion()) {
773 // GetArrayElementType may invalidate span, so copy it.
774 auto membersSpan = GetUnionMembers(tsys);
775 PandaVector<Type> members {membersSpan.begin(), membersSpan.end()};
776 PandaVector<Type> vec;
777 for (auto m : members) {
778 vec.push_back(m.GetArrayElementType(tsys));
779 if (vec.back() == Top()) {
780 return Top();
781 }
782 }
783 return Union(Span {vec}, tsys);
784 }
785 return Top();
786 }
787 } // namespace ark::verifier
788