| //===--- TypeJoinMeet.cpp - Swift Type "join" and "meet" -----------------===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors |
| // Licensed under Apache License v2.0 with Runtime Library Exception |
| // |
| // See https://swift.org/LICENSE.txt for license information |
| // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements the "join" operation for types (and, eventually, |
| // "meet"). |
| // |
| //===----------------------------------------------------------------------===// |
| #include "swift/AST/ASTContext.h" |
| #include "swift/AST/Decl.h" |
| #include "swift/AST/Type.h" |
| #include "swift/AST/Types.h" |
| #include "llvm/ADT/SmallPtrSet.h" |
| using namespace swift; |
| |
| Type Type::join(Type type1, Type type2) { |
| assert(!type1->hasTypeVariable() && !type2->hasTypeVariable() && |
| "Cannot compute join of types involving type variables"); |
| |
| assert(type1->getWithoutSpecifierType()->isEqual(type1) && |
| "Expected simple type!"); |
| assert(type2->getWithoutSpecifierType()->isEqual(type2) && |
| "Expected simple type!"); |
| |
| // FIXME: This algorithm is woefully incomplete, and is only currently used |
| // for optimizing away extra exploratory work in the constraint solver. It |
| // should eventually encompass all of the subtyping rules of the language. |
| |
| // If the types are equivalent, the join is obvious. |
| if (type1->isEqual(type2)) |
| return type1; |
| |
| // If both are class metatypes, compute the join of the instance type and |
| // wrap the result in a metatype. |
| if (auto *metatype1 = type1->getAs<MetatypeType>()) { |
| if (auto *metatype2 = type2->getAs<MetatypeType>()) { |
| auto instance1 = metatype1->getInstanceType(); |
| auto instance2 = metatype2->getInstanceType(); |
| if (instance1->mayHaveSuperclass() && |
| instance2->mayHaveSuperclass()) { |
| auto result = Type::join(instance1, instance2); |
| if (!result) |
| return result; |
| return MetatypeType::get(result); |
| } |
| } |
| } |
| |
| // If both are existential metatypes, compute the join of the instance type |
| // and wrap the result in an existential metatype. |
| if (auto *metatype1 = type1->getAs<ExistentialMetatypeType>()) { |
| if (auto *metatype2 = type2->getAs<ExistentialMetatypeType>()) { |
| auto instance1 = metatype1->getInstanceType(); |
| auto instance2 = metatype2->getInstanceType(); |
| auto result = Type::join(instance1, instance2); |
| if (!result) |
| return result; |
| return ExistentialMetatypeType::get(result); |
| } |
| } |
| |
| // If both are class types or opaque types that potentially have superclasses, |
| // find the common superclass. |
| if (type1->mayHaveSuperclass() && type2->mayHaveSuperclass()) { |
| /// Walk the superclasses of type1 looking for type2. Record them for our |
| /// second step. |
| llvm::SmallPtrSet<CanType, 8> superclassesOfType1; |
| CanType canType2 = type2->getCanonicalType(); |
| for (Type super1 = type1; super1; super1 = super1->getSuperclass()) { |
| CanType canSuper1 = super1->getCanonicalType(); |
| |
| // If we have found the second type, we're done. |
| if (canSuper1 == canType2) return super1; |
| |
| superclassesOfType1.insert(canSuper1); |
| } |
| |
| // Look through the superclasses of type2 to determine if any were also |
| // superclasses of type1. |
| for (Type super2 = type2; super2; super2 = super2->getSuperclass()) { |
| CanType canSuper2 = super2->getCanonicalType(); |
| |
| // If we found the first type, we're done. |
| if (superclassesOfType1.count(canSuper2)) return super2; |
| } |
| |
| // There is no common superclass; we're done. |
| return nullptr; |
| } |
| |
| // If one or both of the types are optional types, look at the underlying |
| // object type. |
| OptionalTypeKind otk1, otk2; |
| Type objectType1 = type1->getAnyOptionalObjectType(otk1); |
| Type objectType2 = type2->getAnyOptionalObjectType(otk2); |
| if (otk1 == OTK_Optional || otk2 == OTK_Optional) { |
| // Compute the join of the unwrapped type. If there is none, we're done. |
| Type unwrappedJoin = join(objectType1 ? objectType1 : type1, |
| objectType2 ? objectType2 : type2); |
| if (!unwrappedJoin) return nullptr; |
| |
| return OptionalType::get(unwrappedJoin); |
| } |
| |
| // The join can only be an existential. |
| return nullptr; |
| } |
| |