| //===--- 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/CanTypeVisitor.h" |
| #include "swift/AST/Decl.h" |
| #include "swift/AST/Type.h" |
| #include "swift/AST/Types.h" |
| #include "llvm/ADT/SmallPtrSet.h" |
| using namespace swift; |
| |
| // FIXME: This is currently 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. |
| struct TypeJoin : CanTypeVisitor<TypeJoin, CanType> { |
| CanType First; |
| |
| TypeJoin(CanType First) : First(First) { |
| assert(First && "Unexpected null type!"); |
| } |
| |
| static CanType getSuperclassJoin(CanType first, CanType second); |
| |
| CanType visitClassType(CanType second); |
| CanType visitBoundGenericClassType(CanType second); |
| CanType visitArchetypeType(CanType second); |
| CanType visitDynamicSelfType(CanType second); |
| CanType visitMetatypeType(CanType second); |
| CanType visitExistentialMetatypeType(CanType second); |
| CanType visitBoundGenericEnumType(CanType second); |
| |
| CanType visitOptionalType(CanType second); |
| |
| CanType visitType(CanType second) { |
| // FIXME: Implement all the visitors. |
| // llvm_unreachable("Unimplemented type visitor!"); |
| return First->getASTContext().TheAnyType; |
| } |
| |
| public: |
| static CanType join(CanType first, CanType second) { |
| assert(!first->hasTypeVariable() && !second->hasTypeVariable() && |
| "Cannot compute join of types involving type variables"); |
| |
| assert(first->getWithoutSpecifierType()->isEqual(first) && |
| "Expected simple type!"); |
| assert(second->getWithoutSpecifierType()->isEqual(second) && |
| "Expected simple type!"); |
| |
| // If the types are equivalent, the join is obvious. |
| if (first == second) |
| return first; |
| |
| // Until we handle all the combinations of joins, we need to make |
| // sure we visit the optional side. |
| OptionalTypeKind otk; |
| if (second->getAnyOptionalObjectType(otk)) |
| return TypeJoin(first).visit(second); |
| |
| return TypeJoin(second).visit(first); |
| } |
| }; |
| |
| CanType TypeJoin::getSuperclassJoin(CanType first, CanType second) { |
| if (!first->mayHaveSuperclass() || !second->mayHaveSuperclass()) |
| return first->getASTContext().TheAnyType; |
| |
| /// Walk the superclasses of `first` looking for `second`. Record them |
| /// for our second step. |
| llvm::SmallPtrSet<CanType, 8> superclassesOfFirst; |
| for (Type super = first; super; super = super->getSuperclass()) { |
| auto canSuper = super->getCanonicalType(); |
| |
| // If we have found the second type, we're done. |
| if (canSuper == second) |
| return canSuper; |
| |
| superclassesOfFirst.insert(canSuper); |
| } |
| |
| // Look through the superclasses of second to determine if any were also |
| // superclasses of first. |
| for (Type super = second; super; super = super->getSuperclass()) { |
| auto canSuper = super->getCanonicalType(); |
| |
| // If we found the first type, we're done. |
| if (superclassesOfFirst.count(canSuper)) |
| return canSuper; |
| } |
| |
| // There is no common superclass; we're done. |
| return first->getASTContext().TheAnyType; |
| } |
| |
| CanType TypeJoin::visitClassType(CanType second) { |
| return getSuperclassJoin(First, second); |
| } |
| |
| CanType TypeJoin::visitBoundGenericClassType(CanType second) { |
| return getSuperclassJoin(First, second); |
| } |
| |
| CanType TypeJoin::visitArchetypeType(CanType second) { |
| return getSuperclassJoin(First, second); |
| } |
| |
| CanType TypeJoin::visitDynamicSelfType(CanType second) { |
| return getSuperclassJoin(First, second); |
| } |
| |
| CanType TypeJoin::visitMetatypeType(CanType second) { |
| if (First->getKind() != second->getKind()) |
| return First->getASTContext().TheAnyType; |
| |
| auto firstInstance = |
| First->castTo<AnyMetatypeType>()->getInstanceType()->getCanonicalType(); |
| auto secondInstance = |
| second->castTo<AnyMetatypeType>()->getInstanceType()->getCanonicalType(); |
| |
| auto joinInstance = join(firstInstance, secondInstance); |
| |
| if (!joinInstance) |
| return First->getASTContext().TheAnyType; |
| |
| return MetatypeType::get(joinInstance)->getCanonicalType(); |
| } |
| |
| CanType TypeJoin::visitExistentialMetatypeType(CanType second) { |
| if (First->getKind() != second->getKind()) |
| return First->getASTContext().TheAnyType; |
| |
| auto firstInstance = |
| First->castTo<AnyMetatypeType>()->getInstanceType()->getCanonicalType(); |
| auto secondInstance = |
| second->castTo<AnyMetatypeType>()->getInstanceType()->getCanonicalType(); |
| |
| auto joinInstance = join(firstInstance, secondInstance); |
| |
| if (!joinInstance) |
| return First->getASTContext().TheAnyType; |
| |
| return ExistentialMetatypeType::get(joinInstance)->getCanonicalType(); |
| } |
| |
| CanType TypeJoin::visitBoundGenericEnumType(CanType second) { |
| if (First->getKind() != second->getKind()) |
| return First->getASTContext().TheAnyType; |
| |
| OptionalTypeKind otk1, otk2; |
| auto firstObject = First->getAnyOptionalObjectType(otk1); |
| auto secondObject = second->getAnyOptionalObjectType(otk2); |
| if (otk1 == OTK_Optional || otk2 == OTK_Optional) { |
| auto canFirst = firstObject->getCanonicalType(); |
| auto canSecond = secondObject->getCanonicalType(); |
| |
| // Compute the join of the unwrapped type. If there is none, we're done. |
| auto unwrappedJoin = |
| join(canFirst ? canFirst : First, canSecond ? canSecond : second); |
| // FIXME: More general joins of enums need to be handled. |
| if (!unwrappedJoin) |
| return First->getASTContext().TheAnyType; |
| |
| return OptionalType::get(unwrappedJoin)->getCanonicalType(); |
| } |
| |
| // FIXME: More general joins of enums need to be handled. |
| return First->getASTContext().TheAnyType; |
| } |
| |
| Type Type::join(Type first, Type second) { |
| assert(first && second && "Unexpected null type!"); |
| |
| if (!first || !second) { |
| if (first) |
| return Type(ErrorType::get(first->getASTContext())); |
| |
| if (second) |
| return Type(ErrorType::get(second->getASTContext())); |
| |
| return Type(); |
| } |
| |
| return TypeJoin::join(first->getCanonicalType(), second->getCanonicalType()); |
| } |