| //===--- TypeCheckCircularity.cpp - Type decl circularity checking --------===// |
| // |
| // 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 an infinitely-sized-type check. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "TypeChecker.h" |
| |
| using namespace swift; |
| |
| #define DEBUG_TYPE "TypeCheckCircularity" |
| |
| namespace { |
| |
| /// The information we track for a type. |
| class TrackingInfo { |
| /// The parent type; either null or a key for an entry in TrackingMap. |
| CanType Parent; |
| |
| /// The member of the parent type that lead to this type, or null |
| /// for a tuple element; and whether the type is currently being |
| /// expanded. |
| llvm::PointerIntPair<ValueDecl *, 1, bool> ParentMemberAndIsBeingExpanded; |
| |
| public: |
| TrackingInfo(CanType parent, ValueDecl *parentMember) |
| : Parent(parent), ParentMemberAndIsBeingExpanded(parentMember, false) {} |
| |
| CanType getParentType() const { |
| return Parent; |
| } |
| |
| ValueDecl *getParentMember() const { |
| return ParentMemberAndIsBeingExpanded.getPointer(); |
| } |
| |
| bool isBeingExpanded() const { |
| return ParentMemberAndIsBeingExpanded.getInt(); |
| } |
| |
| void setBeingExpanded(bool isBeingExpanded) { |
| ParentMemberAndIsBeingExpanded.setInt(isBeingExpanded); |
| } |
| }; |
| |
| struct WorkItem { |
| enum : unsigned { |
| /// A special depth we use to say that this work item |
| /// is to *finish* expanding the target type. |
| FinishExpandingType = ~0U |
| }; |
| |
| unsigned Depth; |
| CanType Type; |
| |
| WorkItem(unsigned depth, CanType type) |
| : Depth(depth), Type(type) {} |
| }; |
| |
| struct PathElement { |
| ValueDecl *Member; // Or nullptr for a tuple element type. |
| size_t TupleIndex; |
| Type Ty; |
| |
| void dump() const; |
| void print(llvm::raw_ostream &out) const; |
| }; |
| |
| class Path { |
| SmallVector<PathElement, 8> Elements; |
| |
| public: |
| void push_back(const PathElement &elt) { Elements.push_back(elt); } |
| |
| bool empty() const { return Elements.empty(); } |
| size_t size() const { return Elements.size(); } |
| const PathElement &operator[](size_t index) const { return Elements[index]; } |
| const PathElement &back() const { return Elements.back(); } |
| |
| void dump() const; |
| void printCycle(llvm::raw_ostream &out, size_t cycleIndex) const; |
| void printInfinite(llvm::raw_ostream &out) const; |
| |
| private: |
| void printSegment(llvm::raw_ostream &out, size_t begin, size_t end, |
| size_t maxContext, bool printFirstType = true) const; |
| }; |
| |
| /// A helper class for performing a circularity check. |
| class CircularityChecker { |
| TypeChecker &TC; |
| |
| /// The original type declaration we're starting with. |
| NominalTypeDecl *OriginalDecl; |
| |
| /// The maximum circularity depth. |
| unsigned MaxDepth; |
| |
| /// Whether we encountered an unchecked declaration. |
| bool RequireDelayedChecking = false; |
| |
| llvm::DenseMap<CanType, TrackingInfo> TrackingMap; |
| SmallVector<WorkItem, 8> Workstack; |
| |
| public: |
| CircularityChecker(TypeChecker &tc, NominalTypeDecl *typeDecl) |
| : TC(tc), OriginalDecl(typeDecl), |
| MaxDepth(tc.Context.LangOpts.MaxCircularityDepth) {} |
| |
| void run(); |
| |
| private: |
| Type getOriginalType() const { |
| return OriginalDecl->getDeclaredInterfaceType(); |
| } |
| |
| bool expandType(CanType type, unsigned depth); |
| bool expandTuple(CanTupleType type, unsigned depth); |
| bool expandNominal(CanType type, NominalTypeDecl *D, unsigned depth); |
| bool expandStruct(CanType type, StructDecl *S, unsigned depth); |
| bool expandEnum(CanType type, EnumDecl *E, unsigned depth); |
| |
| bool addMember(CanType parentType, ValueDecl *member, Type memberType, |
| unsigned parentDepth); |
| |
| void startExpandingType(CanType type) { |
| auto it = TrackingMap.find(type); |
| assert(it != TrackingMap.end()); |
| |
| // Set the IsBeginExpanded flag. |
| assert(!it->second.isBeingExpanded() && "already expanding type"); |
| it->second.setBeingExpanded(true); |
| |
| // Push a work item to clear that flag. |
| pushFinishExpandingTypeWorkItem(type); |
| } |
| |
| void finishExpandingType(CanType type) { |
| auto it = TrackingMap.find(type); |
| assert(it != TrackingMap.end()); |
| |
| // Clear the IsBeginExpanded flag. |
| assert(it->second.isBeingExpanded() && "not already expanding type"); |
| it->second.setBeingExpanded(false); |
| } |
| |
| void pushFinishExpandingTypeWorkItem(CanType type) { |
| Workstack.emplace_back(WorkItem::FinishExpandingType, type); |
| } |
| |
| void pushExpandTypeWorkItem(CanType type, unsigned depth) { |
| assert(depth != WorkItem::FinishExpandingType); |
| Workstack.emplace_back(depth, type); |
| } |
| |
| bool diagnoseCircularity(CanType parentType, ValueDecl *member, |
| CanType memberType); |
| |
| bool diagnoseInfiniteRecursion(CanType parentType, ValueDecl *member, |
| CanType memberType); |
| |
| void addPathElementsTo(Path &path, CanType type); |
| void addPathElement(Path &path, ValueDecl *member, CanType memberType); |
| |
| Path buildPath(CanType parentType, ValueDecl *member, CanType memberType); |
| }; |
| |
| } // end anonymous namespace |
| |
| void TypeChecker::checkDeclCircularity(NominalTypeDecl *decl) { |
| CircularityChecker(*this, decl).run(); |
| } |
| |
| /// The main routine for performing circularity checks. |
| void CircularityChecker::run() { |
| auto type = getOriginalType()->getCanonicalType(); |
| |
| // Prime the tracking map. |
| TrackingMap.insert({type, TrackingInfo(CanType(), nullptr)}); |
| |
| // Recurse into the top-level nominal type. |
| expandNominal(type, OriginalDecl, 0); |
| |
| // Execute the workstack. |
| while (!Workstack.empty()) { |
| auto item = Workstack.pop_back_val(); |
| if (item.Depth == WorkItem::FinishExpandingType) { |
| finishExpandingType(item.Type); |
| } else if (expandType(item.Type, item.Depth)) { |
| return; |
| } |
| } |
| |
| // If we didn't report an error, but we encountered a property that |
| // hadn't been type-checked, queue the type for delayed checking. |
| if (RequireDelayedChecking) { |
| TC.DelayedCircularityChecks.push_back(OriginalDecl); |
| } |
| } |
| |
| /// Visit a type and try to expand it one level. |
| /// |
| /// \return true if a problem was found and all further processing |
| /// should be aborted. |
| bool CircularityChecker::expandType(CanType type, unsigned depth) { |
| if (auto D = type.getAnyNominal()) { |
| return expandNominal(type, D, depth); |
| } else if (auto tuple = dyn_cast<TupleType>(type)) { |
| return expandTuple(tuple, depth); |
| } else { |
| return false; |
| } |
| } |
| |
| /// Visit a tuple type and try to expand it one level. |
| bool CircularityChecker::expandTuple(CanTupleType tupleType, unsigned depth) { |
| startExpandingType(tupleType); |
| |
| for (auto eltType : tupleType.getElementTypes()) { |
| if (addMember(tupleType, nullptr, eltType, depth)) |
| return true; |
| } |
| |
| return false; |
| } |
| |
| /// Visit a nominal type and try to expand it one level. |
| bool CircularityChecker::expandNominal(CanType type, NominalTypeDecl *D, |
| unsigned depth) { |
| if (auto S = dyn_cast<StructDecl>(D)) { |
| return expandStruct(type, S, depth); |
| } else if (auto E = dyn_cast<EnumDecl>(D)) { |
| return expandEnum(type, E, depth); |
| } else { |
| // Other nominal types are representational leaves. |
| return false; |
| } |
| } |
| |
| /// Visit a struct type and try to expand it one level. |
| bool CircularityChecker::expandStruct(CanType type, StructDecl *S, |
| unsigned depth) { |
| startExpandingType(type); |
| |
| for (auto field: S->getStoredProperties()) { |
| // Ignore unchecked fields, but flag that we'll need more checking later. |
| if (!field->hasInterfaceType()) { |
| RequireDelayedChecking = true; |
| continue; |
| } |
| |
| auto fieldType = |
| type->getTypeOfMember(S->getModuleContext(), field, nullptr); |
| if (addMember(type, field, fieldType, depth)) |
| return true; |
| } |
| |
| return false; |
| } |
| |
| /// Visit an enum type and try to expand it one level. |
| bool CircularityChecker::expandEnum(CanType type, EnumDecl *E, |
| unsigned depth) { |
| // Indirect enums are representational leaves. |
| if (E->isIndirect()) return false; |
| |
| startExpandingType(type); |
| |
| for (auto elt: E->getAllElements()) { |
| // Ignore unchecked elements, but flag that we'll need more checking later. |
| if (!elt->hasInterfaceType()) { |
| RequireDelayedChecking = true; |
| continue; |
| } |
| |
| // Indirect elements are representational leaves. |
| if (elt->isIndirect()) |
| continue; |
| |
| // Ignore elements with no payload. |
| auto eltIfaceType = elt->getArgumentInterfaceType(); |
| if (!eltIfaceType) |
| continue; |
| |
| auto eltType = |
| type->getTypeOfMember(E->getModuleContext(), elt, eltIfaceType); |
| |
| if (addMember(type, elt, eltType, depth)) |
| return true; |
| } |
| |
| return false; |
| } |
| |
| bool CircularityChecker::addMember(CanType parentType, ValueDecl *member, |
| Type memberNCType, unsigned parentDepth) { |
| auto memberType = memberNCType->getCanonicalType(); |
| |
| unsigned depth = parentDepth + 1; |
| if (depth > MaxDepth) { |
| return diagnoseInfiniteRecursion(parentType, member, memberType); |
| } |
| |
| // Fast path: if the type isn't some sort of interesting type, |
| // just ignore it. |
| |
| if (isa<TupleType>(memberType)) { |
| // Ok, visit tuples. |
| } else if (memberType.getStructOrBoundGenericStruct()) { |
| // Ok, visit structs. |
| // TODO: skip non-generic types in different modules? |
| } else if (auto E = memberType.getEnumOrBoundGenericEnum()) { |
| // Ok, visit non-indirect enums. |
| if (E->isIndirect()) return false; |
| // TODO: skip non-generic types in different modules? |
| } else { |
| // Everything else is a representational leaf. |
| return false; |
| } |
| |
| // Try to start tracking the type. |
| auto insertion = TrackingMap.insert({memberType, |
| TrackingInfo(parentType, member)}); |
| |
| // If it's not already there, add an item to recurse into it. |
| if (insertion.second) { |
| pushExpandTypeWorkItem(memberType, depth); |
| return false; |
| } |
| |
| // Otherwise, we've already enqueued it. If we're not currently |
| // expanding it, there's no circularity to worry about. |
| auto &info = insertion.first->second; |
| if (!info.isBeingExpanded()) |
| return false; |
| |
| return diagnoseCircularity(parentType, member, memberType); |
| } |
| |
| static size_t findCycleIndex(const Path &path) { |
| for (auto index : IntRange<size_t>(0, path.size() - 1)) { |
| if (path[index].Ty->isEqual(path.back().Ty)) |
| return index; |
| } |
| llvm_unreachable("didn't find cycle in path"); |
| } |
| |
| static Type getMemberStorageInterfaceType(ValueDecl *member) { |
| if (auto elt = dyn_cast<EnumElementDecl>(member)) { |
| return elt->getArgumentInterfaceType(); |
| } else { |
| return member->getInterfaceType(); |
| } |
| } |
| |
| static bool isNonDependentField(const PathElement &elt) { |
| if (!elt.Member) return false; |
| return !getMemberStorageInterfaceType(elt.Member)->hasTypeParameter(); |
| } |
| |
| void LLVM_ATTRIBUTE_USED Path::dump() const { |
| auto &out = llvm::errs(); |
| printSegment(out, 0, size(), size()); |
| out << '\n'; |
| } |
| |
| /// Prints: |
| /// TypeA -> (a: TypeB) -> (b: TypeB) -> (c: CycleType) |
| /// -> (d: TypeD) -> (e: CycleType) |
| void Path::printCycle(llvm::raw_ostream &out, size_t cycleIndex) const { |
| // If the cycle goes to Self or the member type, print the |
| // path in one segment starting from the field type. |
| if (cycleIndex <= 1) { |
| printSegment(out, 1, size(), 3); |
| |
| // Otherwise, print the path in two segments. |
| } else { |
| printSegment(out, 1, cycleIndex + 1, 2); |
| printSegment(out, cycleIndex, size(), 2, false); |
| } |
| } |
| |
| /// Prints: |
| /// TypeA -> (x: TypeB) -> (y: TypeB) -> (z: TypeC) -> ... |
| void Path::printInfinite(llvm::raw_ostream &out) const { |
| printSegment(out, 1, std::min(size(), size_t(7)), 7); |
| out << " -> ..."; |
| } |
| |
| /// Prints: |
| /// [TypeA] -> (a: TypeB) -> (b: TypeB) -> (c: TypeC) |
| /// If the path is too long, elides the middle with '-> ...'. |
| void Path::printSegment(llvm::raw_ostream &out, size_t begin, size_t end, |
| size_t maxContext, bool printFirstType) const { |
| if (printFirstType) { |
| out << Elements[begin].Ty; |
| } |
| |
| size_t numElements = end - begin; |
| if (numElements > maxContext * 2) { |
| for (size_t i = begin + 1; i != begin + maxContext + 1; ++i) |
| Elements[i].print(out); |
| out << " -> ... "; |
| for (size_t i = end - maxContext; i != end; ++i) |
| Elements[i].print(out); |
| } else { |
| for (size_t i = begin + 1; i != end; ++i) { |
| Elements[i].print(out); |
| } |
| } |
| } |
| |
| void LLVM_ATTRIBUTE_USED PathElement::dump() const { |
| auto &out = llvm::errs(); |
| print(out); |
| out << '\n'; |
| } |
| |
| /// Prints: |
| /// -> (a: TypeA) |
| void PathElement::print(llvm::raw_ostream &out) const { |
| out << " -> ("; |
| if (Member) { |
| auto name = Member->getFullName(); |
| if (name) { |
| out << name; |
| } else { |
| out << "<anonymous>"; |
| } |
| } else { |
| out << '.' << TupleIndex; |
| } |
| out << ": " << Ty << ')'; |
| } |
| |
| /// Recreate a non-canonical type path. |
| Path CircularityChecker::buildPath(CanType parentType, ValueDecl *member, |
| CanType memberType) { |
| Path path; |
| addPathElementsTo(path, parentType); |
| addPathElement(path, member, memberType); |
| return path; |
| } |
| |
| /// Recreate a non-canonical path that leads to the target type. |
| void CircularityChecker::addPathElementsTo(Path &path, CanType targetType) { |
| auto it = TrackingMap.find(targetType); |
| assert(it != TrackingMap.end() && "no entry in tracking map?"); |
| |
| CanType canParentType = it->second.getParentType(); |
| if (!canParentType) { |
| path.push_back({ nullptr, 0, getOriginalType()}); |
| return; |
| } |
| |
| addPathElementsTo(path, canParentType); |
| addPathElement(path, it->second.getParentMember(), targetType); |
| } |
| |
| /// Add a non-canonical path element to a path. |
| void CircularityChecker::addPathElement(Path &path, ValueDecl *member, |
| CanType canMemberType) { |
| assert(!path.empty()); |
| |
| Type parentType = path.back().Ty; |
| |
| PathElement elt; |
| |
| if (member) { |
| elt.Member = member; |
| elt.TupleIndex = 0; |
| |
| Type memberIfaceType = getMemberStorageInterfaceType(member); |
| elt.Ty = parentType->getTypeOfMember(member->getModuleContext(), member, |
| memberIfaceType); |
| |
| } else { |
| auto tupleType = parentType->castTo<TupleType>(); |
| for (auto index : indices(tupleType->getElementTypes())) { |
| auto eltType = tupleType->getElementType(index); |
| if (eltType->getCanonicalType() == canMemberType) { |
| elt.Member = nullptr; |
| elt.TupleIndex = index; |
| elt.Ty = eltType; |
| break; |
| } |
| } |
| assert(elt.Ty && "didn't find matching element of tuple"); |
| } |
| |
| // We shouldn't print reference storage types here. |
| if (auto ref = elt.Ty->getAs<ReferenceStorageType>()) { |
| elt.Ty = ref->getReferentType(); |
| } |
| |
| // Strip outer parens from the type. (This is especially common with |
| // enum elements.) |
| if (auto parens = dyn_cast<ParenType>(elt.Ty.getPointer())) { |
| elt.Ty = parens->getSinglyDesugaredType(); |
| } |
| |
| path.push_back(elt); |
| } |
| |
| /// Diagnose a circularity. |
| /// |
| /// \returns always true |
| bool CircularityChecker::diagnoseCircularity(CanType parentType, |
| ValueDecl *member, |
| CanType memberType) { |
| auto path = buildPath(parentType, member, memberType); |
| |
| // Find the index that the cycle leads back to. |
| auto cycleIndex = findCycleIndex(path); |
| |
| // If the path to the cycle passes through a field (other than the one |
| // directly declared on this type) that does not depend on the original |
| // declaration in any way, then the type that contains that field should |
| // be responsible for reporting the cycle. |
| // TODO: we can also suppress this if the cycle would exist independently. |
| for (size_t i = 2; i < cycleIndex + 1; ++i) { |
| if (isNonDependentField(path[i])) |
| return true; |
| } |
| |
| auto baseType = path[0].Ty; |
| if (cycleIndex != 0) { |
| TC.diagnose(OriginalDecl->getLoc(), |
| diag::unsupported_infinitely_sized_type, |
| baseType); |
| } else if (isa<StructDecl>(OriginalDecl)) { |
| TC.diagnose(path[1].Member->getLoc(), |
| diag::unsupported_recursive_struct, |
| baseType); |
| } else if (isa<EnumDecl>(OriginalDecl)) { |
| TC.diagnose(OriginalDecl->getLoc(), |
| diag::recursive_enum_not_indirect, |
| baseType) |
| .fixItInsert(OriginalDecl->getStartLoc(), "indirect "); |
| } else { |
| llvm_unreachable("what kind of entity was this?"); |
| } |
| |
| // Add a note about the path we found unless it's completely trivial. |
| if (path.size() > 2) { |
| llvm::SmallString<128> pathString; { |
| llvm::raw_svector_ostream out(pathString); |
| path.printCycle(out, cycleIndex); |
| } |
| TC.diagnose(path[1].Member->getLoc(), |
| diag::note_type_cycle_starts_here, |
| pathString); |
| } else if (isa<EnumDecl>(OriginalDecl)) { |
| TC.diagnose(path[1].Member->getLoc(), |
| diag::note_recursive_enum_case_here); |
| } |
| |
| return true; |
| } |
| |
| bool CircularityChecker::diagnoseInfiniteRecursion(CanType parentType, |
| ValueDecl *member, |
| CanType memberType) { |
| auto path = buildPath(parentType, member, memberType); |
| |
| // If the path passes through a field (other than the one directly |
| // declared on this type) that does not depend on the original |
| // declaration in any way, then the type that contains that field should |
| // be responsible for reporting the cycle. |
| // Applying this heuristic only makes sense if we're assuming that |
| // it really is an infinite expansion. |
| for (size_t i = 2, e = path.size(); i < e; ++i) { |
| if (isNonDependentField(path[i])) |
| return true; |
| } |
| |
| auto baseType = path[0].Ty; |
| TC.diagnose(OriginalDecl->getLoc(), |
| diag::unsupported_infinitely_sized_type, |
| baseType); |
| |
| // Add a note about the start of the path. |
| llvm::SmallString<128> pathString; { |
| llvm::raw_svector_ostream out(pathString); |
| path.printInfinite(out); |
| } |
| |
| TC.diagnose(path[1].Member->getLoc(), |
| diag::note_type_cycle_starts_here, |
| pathString); |
| |
| return true; |
| } |