| //===--- ClassHierarchyAnalysis.cpp - Class hierarchy analysis --*- C++ -*-===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors |
| // Licensed under Apache License v2.0 with Runtime Library Exception |
| // |
| // See http://swift.org/LICENSE.txt for license information |
| // See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "swift/SILOptimizer/Analysis/ClassHierarchyAnalysis.h" |
| #include "swift/AST/ASTContext.h" |
| #include "swift/AST/ASTWalker.h" |
| #include "swift/AST/Module.h" |
| #include "swift/SIL/SILInstruction.h" |
| #include "swift/SIL/SILValue.h" |
| #include "swift/SIL/SILModule.h" |
| |
| using namespace swift; |
| |
| namespace { |
| /// A helper class to collect all nominal type declarations. |
| class NominalTypeWalker: public ASTWalker { |
| ClassHierarchyAnalysis::ProtocolImplementations &ProtocolImplementationsCache; |
| public: |
| NominalTypeWalker(ClassHierarchyAnalysis::ProtocolImplementations |
| &ProtocolImplementationsCache) |
| :ProtocolImplementationsCache(ProtocolImplementationsCache) { |
| } |
| |
| virtual bool walkToDeclPre(Decl *D) { |
| auto *NTD = dyn_cast<NominalTypeDecl>(D); |
| if (!NTD) |
| return true; |
| auto Protocols = NTD->getAllProtocols(); |
| // We are only interested in types implementing protocols. |
| if (!Protocols.empty()) { |
| for (auto &Protocol : Protocols) { |
| auto &K = ProtocolImplementationsCache[Protocol]; |
| K.push_back(NTD); |
| } |
| } |
| return true; |
| } |
| }; |
| } |
| |
| void ClassHierarchyAnalysis::init() { |
| // Process all types implementing protocols. |
| SmallVector<Decl *, 32> Decls; |
| // TODO: It would be better if we could get all declarations |
| // from a given module, not only the top-level ones. |
| M->getSwiftModule()->getTopLevelDecls(Decls); |
| |
| NominalTypeWalker Walker(ProtocolImplementationsCache); |
| for(auto *D: Decls) { |
| D->walk(Walker); |
| } |
| |
| // For each class declaration in our V-table list: |
| for (auto &VT : M->getVTableList()) { |
| ClassDecl *C = VT.getClass(); |
| // Ignore classes that are at the top of the class hierarchy: |
| if (!C->hasSuperclass()) |
| continue; |
| |
| // Add the superclass to the list of inherited classes. |
| ClassDecl *Super = C->getSuperclass()->getClassOrBoundGenericClass(); |
| auto &K = DirectSubclassesCache[Super]; |
| assert(std::find(K.begin(), K.end(), C) == K.end() && |
| "Class vector must be unique"); |
| K.push_back(C); |
| } |
| } |
| |
| /// \brief Get all subclasses of a given class. |
| /// Does not include any direct subclasses of given base class. |
| /// |
| /// \p Base class, whose direct subclasses are to be excluded |
| /// \p Current class, whose direct and indirect subclasses are |
| /// to be collected. |
| /// \p IndirectSubs placeholder for collected results |
| void ClassHierarchyAnalysis::getIndirectSubClasses(ClassDecl *Cur, |
| ClassList &IndirectSubs) { |
| unsigned Idx = IndirectSubs.size(); |
| |
| if (!hasKnownDirectSubclasses(Cur)) |
| return; |
| |
| // Produce a set of all indirect subclasses in a |
| // breadth-first order; |
| |
| // First add subclasses of direct subclasses. |
| for (auto C : getDirectSubClasses(Cur)) { |
| // Get direct subclasses |
| if (!hasKnownDirectSubclasses(C)) |
| continue; |
| auto &DirectSubclasses = getDirectSubClasses(C); |
| // Remember all direct subclasses of the current one. |
| for (auto S : DirectSubclasses) { |
| IndirectSubs.push_back(S); |
| } |
| } |
| |
| // Then recursively add direct subclasses of already |
| // added subclasses. |
| while (Idx != IndirectSubs.size()) { |
| auto C = IndirectSubs[Idx++]; |
| // Get direct subclasses |
| if (!hasKnownDirectSubclasses(C)) |
| continue; |
| auto &DirectSubclasses = getDirectSubClasses(C); |
| // Remember all direct subclasses of the current one. |
| for (auto S : DirectSubclasses) { |
| IndirectSubs.push_back(S); |
| } |
| } |
| } |
| |
| |
| ClassHierarchyAnalysis::~ClassHierarchyAnalysis() {} |