| //===--- 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/TypeVisitor.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 : TypeVisitor<TypeJoin, Type> { |
| Type First; |
| |
| TypeJoin(Type First) : First(First) { |
| assert(First && "Unexpected null type!"); |
| } |
| |
| static Type getSuperclassJoin(Type first, Type second); |
| |
| Type visitClassType(Type second); |
| Type visitBoundGenericClassType(Type second); |
| Type visitArchetypeType(Type second); |
| Type visitDynamicSelfType(Type second); |
| Type visitMetatypeType(Type second); |
| Type visitExistentialMetatypeType(Type second); |
| Type visitBoundGenericEnumType(Type second); |
| |
| Type visitOptionalType(Type second); |
| |
| Type visitType(Type second) { |
| // FIXME: Implement all the visitors. |
| // llvm_unreachable("Unimplemented type visitor!"); |
| return First->getASTContext().TheAnyType; |
| } |
| |
| public: |
| static Type join(Type first, Type second) { |
| if (!first || !second) { |
| if (first) |
| return ErrorType::get(first->getASTContext()); |
| |
| if (second) |
| return ErrorType::get(second->getASTContext()); |
| |
| return Type(); |
| } |
| |
| 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->isEqual(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); |
| } |
| }; |
| |
| Type TypeJoin::getSuperclassJoin(Type first, Type second) { |
| if (!first || !second) |
| return TypeJoin::join(first, 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; |
| CanType canSecond = second->getCanonicalType(); |
| for (Type super = first; super; super = super->getSuperclass()) { |
| CanType canSuper = super->getCanonicalType(); |
| |
| // If we have found the second type, we're done. |
| if (canSuper == canSecond) |
| return super; |
| |
| 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()) { |
| CanType canSuper = super->getCanonicalType(); |
| |
| // If we found the first type, we're done. |
| if (superclassesOfFirst.count(canSuper)) |
| return super; |
| } |
| |
| // There is no common superclass; we're done. |
| return first->getASTContext().TheAnyType; |
| } |
| |
| Type TypeJoin::visitClassType(Type second) { |
| return getSuperclassJoin(First, second); |
| } |
| |
| Type TypeJoin::visitBoundGenericClassType(Type second) { |
| return getSuperclassJoin(First, second); |
| } |
| |
| Type TypeJoin::visitArchetypeType(Type second) { |
| return getSuperclassJoin(First, second); |
| } |
| |
| Type TypeJoin::visitDynamicSelfType(Type second) { |
| return getSuperclassJoin(First, second); |
| } |
| |
| Type TypeJoin::visitMetatypeType(Type second) { |
| if (First->getKind() != second->getKind()) |
| return First->getASTContext().TheAnyType; |
| |
| auto firstInstance = First->castTo<AnyMetatypeType>()->getInstanceType(); |
| auto secondInstance = second->castTo<AnyMetatypeType>()->getInstanceType(); |
| |
| auto joinInstance = join(firstInstance, secondInstance); |
| |
| if (!joinInstance) |
| return First->getASTContext().TheAnyType; |
| |
| return MetatypeType::get(joinInstance); |
| } |
| |
| Type TypeJoin::visitExistentialMetatypeType(Type second) { |
| if (First->getKind() != second->getKind()) |
| return First->getASTContext().TheAnyType; |
| |
| auto firstInstance = First->castTo<AnyMetatypeType>()->getInstanceType(); |
| auto secondInstance = second->castTo<AnyMetatypeType>()->getInstanceType(); |
| |
| auto joinInstance = join(firstInstance, secondInstance); |
| |
| if (!joinInstance) |
| return First->getASTContext().TheAnyType; |
| |
| return ExistentialMetatypeType::get(joinInstance); |
| } |
| |
| Type TypeJoin::visitBoundGenericEnumType(Type second) { |
| if (First->getKind() != second->getKind()) |
| return First->getASTContext().TheAnyType; |
| |
| OptionalTypeKind otk1, otk2; |
| Type objectType1 = First->getAnyOptionalObjectType(otk1); |
| Type objectType2 = second->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 : First, |
| objectType2 ? objectType2 : second); |
| // FIXME: More general joins of enums need to be handled. |
| if (!unwrappedJoin) |
| return First->getASTContext().TheAnyType; |
| |
| return OptionalType::get(unwrappedJoin); |
| } |
| |
| // FIXME: More general joins of enums need to be handled. |
| return First->getASTContext().TheAnyType; |
| } |
| |
| Type TypeJoin::visitOptionalType(Type second) { |
| auto canFirst = First->getCanonicalType(); |
| auto canSecond = second->getCanonicalType(); |
| |
| return TypeJoin::join(canFirst, canSecond); |
| } |
| |
| Type Type::join(Type type1, Type type2) { |
| assert(type1 && type2 && "Unexpected null type!"); |
| |
| return TypeJoin::join(type1, type2); |
| } |