| //===--- DependencyGraph.cpp - Track intra-module dependencies ------------===// |
| // |
| // 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 |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "swift/Basic/ReferenceDependencyKeys.h" |
| #include "swift/Basic/Statistic.h" |
| #include "swift/Driver/DependencyGraph.h" |
| #include "swift/Demangling/Demangle.h" |
| #include "llvm/ADT/SmallString.h" |
| #include "llvm/ADT/SmallVector.h" |
| #include "llvm/ADT/StringSwitch.h" |
| #include "llvm/ADT/STLExtras.h" |
| #include "llvm/Support/raw_ostream.h" |
| #include "llvm/Support/MemoryBuffer.h" |
| #include "llvm/Support/SourceMgr.h" |
| #include "llvm/Support/YAMLParser.h" |
| |
| using namespace swift; |
| |
| enum class DependencyGraphImpl::DependencyKind : uint8_t { |
| TopLevelName = 1 << 0, |
| DynamicLookupName = 1 << 1, |
| NominalType = 1 << 2, |
| NominalTypeMember = 1 << 3, |
| ExternalFile = 1 << 4, |
| }; |
| enum class DependencyGraphImpl::DependencyFlags : uint8_t { |
| IsCascading = 1 << 0 |
| }; |
| |
| class DependencyGraphImpl::MarkTracerImpl::Entry { |
| public: |
| const void *Node; |
| StringRef Name; |
| DependencyMaskTy KindMask; |
| }; |
| |
| DependencyGraphImpl::MarkTracerImpl::MarkTracerImpl(UnifiedStatsReporter *Stats) |
| : Stats(Stats) {} |
| DependencyGraphImpl::MarkTracerImpl::~MarkTracerImpl() = default; |
| |
| using LoadResult = DependencyGraphImpl::LoadResult; |
| using DependencyKind = DependencyGraphImpl::DependencyKind; |
| using DependencyCallbackTy = LoadResult(StringRef, DependencyKind, bool); |
| using InterfaceHashCallbackTy = LoadResult(StringRef); |
| |
| static LoadResult |
| parseDependencyFile(llvm::MemoryBuffer &buffer, |
| llvm::function_ref<DependencyCallbackTy> providesCallback, |
| llvm::function_ref<DependencyCallbackTy> dependsCallback, |
| llvm::function_ref<InterfaceHashCallbackTy> interfaceHashCallback) { |
| namespace yaml = llvm::yaml; |
| |
| // FIXME: Switch to a format other than YAML. |
| llvm::SourceMgr SM; |
| yaml::Stream stream(buffer.getMemBufferRef(), SM); |
| auto I = stream.begin(); |
| if (I == stream.end() || !I->getRoot()) |
| return LoadResult::HadError; |
| |
| auto *topLevelMap = dyn_cast<yaml::MappingNode>(I->getRoot()); |
| if (!topLevelMap) { |
| if (isa<yaml::NullNode>(I->getRoot())) |
| return LoadResult::UpToDate; |
| return LoadResult::HadError; |
| } |
| |
| LoadResult result = LoadResult::UpToDate; |
| SmallString<64> scratch; |
| |
| // After an entry, we know more about the node as a whole. |
| // Update the "result" variable above. |
| // This is a macro rather than a lambda because it contains a return. |
| #define UPDATE_RESULT(update) switch (update) {\ |
| case LoadResult::HadError: \ |
| return LoadResult::HadError; \ |
| case LoadResult::UpToDate: \ |
| break; \ |
| case LoadResult::AffectsDownstream: \ |
| result = LoadResult::AffectsDownstream; \ |
| break; \ |
| } \ |
| |
| // FIXME: LLVM's YAML support does incremental parsing in such a way that |
| // for-range loops break. |
| for (auto i = topLevelMap->begin(), e = topLevelMap->end(); i != e; ++i) { |
| if (isa<yaml::NullNode>(i->getValue())) |
| continue; |
| |
| auto *key = dyn_cast<yaml::ScalarNode>(i->getKey()); |
| if (!key) |
| return LoadResult::HadError; |
| StringRef keyString = key->getValue(scratch); |
| |
| using namespace reference_dependency_keys; |
| |
| if (keyString == interfaceHash) { |
| auto *value = dyn_cast<yaml::ScalarNode>(i->getValue()); |
| if (!value) |
| return LoadResult::HadError; |
| |
| StringRef valueString = value->getValue(scratch); |
| UPDATE_RESULT(interfaceHashCallback(valueString)); |
| |
| } else { |
| enum class DependencyDirection : bool { |
| Depends, |
| Provides |
| }; |
| using KindPair = std::pair<DependencyKind, DependencyDirection>; |
| |
| KindPair dirAndKind = llvm::StringSwitch<KindPair>(key->getValue(scratch)) |
| .Case(dependsTopLevel, |
| std::make_pair(DependencyKind::TopLevelName, |
| DependencyDirection::Depends)) |
| .Case(dependsNominal, |
| std::make_pair(DependencyKind::NominalType, |
| DependencyDirection::Depends)) |
| .Case(dependsMember, |
| std::make_pair(DependencyKind::NominalTypeMember, |
| DependencyDirection::Depends)) |
| .Case(dependsDynamicLookup, |
| std::make_pair(DependencyKind::DynamicLookupName, |
| DependencyDirection::Depends)) |
| .Case(dependsExternal, |
| std::make_pair(DependencyKind::ExternalFile, |
| DependencyDirection::Depends)) |
| .Case(providesTopLevel, |
| std::make_pair(DependencyKind::TopLevelName, |
| DependencyDirection::Provides)) |
| .Case(providesNominal, |
| std::make_pair(DependencyKind::NominalType, |
| DependencyDirection::Provides)) |
| .Case(providesMember, |
| std::make_pair(DependencyKind::NominalTypeMember, |
| DependencyDirection::Provides)) |
| .Case(providesDynamicLookup, |
| std::make_pair(DependencyKind::DynamicLookupName, |
| DependencyDirection::Provides)) |
| .Default(std::make_pair(DependencyKind(), |
| DependencyDirection::Depends)); |
| if (dirAndKind.first == DependencyKind()) |
| return LoadResult::HadError; |
| |
| auto *entries = dyn_cast<yaml::SequenceNode>(i->getValue()); |
| if (!entries) |
| return LoadResult::HadError; |
| |
| if (dirAndKind.first == DependencyKind::NominalTypeMember) { |
| // Handle member dependencies specially. Rather than being a single |
| // string, they come in the form ["{MangledBaseName}", "memberName"]. |
| for (yaml::Node &rawEntry : *entries) { |
| bool isCascading = rawEntry.getRawTag() != "!private"; |
| |
| auto *entry = dyn_cast<yaml::SequenceNode>(&rawEntry); |
| if (!entry) |
| return LoadResult::HadError; |
| |
| auto iter = entry->begin(); |
| auto *base = dyn_cast<yaml::ScalarNode>(&*iter); |
| if (!base) |
| return LoadResult::HadError; |
| ++iter; |
| |
| auto *member = dyn_cast<yaml::ScalarNode>(&*iter); |
| if (!member) |
| return LoadResult::HadError; |
| ++iter; |
| |
| // FIXME: LLVM's YAML support doesn't implement == correctly for end |
| // iterators. |
| assert(!(iter != entry->end())); |
| |
| bool isDepends = dirAndKind.second == DependencyDirection::Depends; |
| auto &callback = isDepends ? dependsCallback : providesCallback; |
| |
| // Smash the type and member names together so we can continue using |
| // StringMap. |
| SmallString<64> appended; |
| appended += base->getValue(scratch); |
| appended.push_back('\0'); |
| appended += member->getValue(scratch); |
| |
| UPDATE_RESULT(callback(appended.str(), dirAndKind.first, |
| isCascading)); |
| } |
| } else { |
| for (const yaml::Node &rawEntry : *entries) { |
| auto *entry = dyn_cast<yaml::ScalarNode>(&rawEntry); |
| if (!entry) |
| return LoadResult::HadError; |
| |
| bool isDepends = dirAndKind.second == DependencyDirection::Depends; |
| auto &callback = isDepends ? dependsCallback : providesCallback; |
| |
| UPDATE_RESULT(callback(entry->getValue(scratch), dirAndKind.first, |
| entry->getRawTag() != "!private")); |
| } |
| } |
| } |
| } |
| |
| return result; |
| } |
| |
| LoadResult DependencyGraphImpl::loadFromPath(const void *node, StringRef path) { |
| auto buffer = llvm::MemoryBuffer::getFile(path); |
| if (!buffer) |
| return LoadResult::HadError; |
| return loadFromBuffer(node, *buffer.get()); |
| } |
| |
| LoadResult |
| DependencyGraphImpl::loadFromString(const void *node, StringRef data) { |
| auto buffer = llvm::MemoryBuffer::getMemBuffer(data); |
| return loadFromBuffer(node, *buffer); |
| } |
| |
| LoadResult DependencyGraphImpl::loadFromBuffer(const void *node, |
| llvm::MemoryBuffer &buffer) { |
| auto &provides = Provides[node]; |
| |
| auto dependsCallback = [this, node](StringRef name, DependencyKind kind, |
| bool isCascading) -> LoadResult { |
| if (kind == DependencyKind::ExternalFile) |
| ExternalDependencies.insert(name); |
| |
| auto &entries = Dependencies[name]; |
| auto iter = std::find_if(entries.first.begin(), entries.first.end(), |
| [node](const DependencyEntryTy &entry) -> bool { |
| return node == entry.node; |
| }); |
| |
| DependencyFlagsTy flags; |
| if (isCascading) |
| flags |= DependencyFlags::IsCascading; |
| |
| if (iter == entries.first.end()) { |
| entries.first.push_back({node, kind, flags}); |
| } else { |
| iter->kindMask |= kind; |
| iter->flags |= flags; |
| } |
| |
| if (isCascading && (entries.second & kind)) |
| return LoadResult::AffectsDownstream; |
| return LoadResult::UpToDate; |
| }; |
| |
| auto providesCallback = |
| [&provides](StringRef name, DependencyKind kind, |
| bool isCascading) -> LoadResult { |
| assert(isCascading); |
| auto iter = std::find_if(provides.begin(), provides.end(), |
| [name](const ProvidesEntryTy &entry) -> bool { |
| return name == entry.name; |
| }); |
| |
| if (iter == provides.end()) |
| provides.push_back({name, kind}); |
| else |
| iter->kindMask |= kind; |
| |
| return LoadResult::UpToDate; |
| }; |
| |
| auto interfaceHashCallback = [this, node](StringRef hash) -> LoadResult { |
| auto insertResult = InterfaceHashes.insert(std::make_pair(node, hash)); |
| |
| if (insertResult.second) { |
| // Treat a newly-added hash as up-to-date. This includes the initial |
| // load of the file. |
| return LoadResult::UpToDate; |
| } |
| |
| auto iter = insertResult.first; |
| if (hash != iter->second) { |
| iter->second = hash; |
| return LoadResult::AffectsDownstream; |
| } |
| |
| return LoadResult::UpToDate; |
| }; |
| |
| return parseDependencyFile(buffer, providesCallback, dependsCallback, |
| interfaceHashCallback); |
| } |
| |
| void DependencyGraphImpl::markExternal(SmallVectorImpl<const void *> &visited, |
| StringRef externalDependency) { |
| auto allDependents = Dependencies.find(externalDependency); |
| assert(allDependents != Dependencies.end() && "not a dependency!"); |
| allDependents->second.second |= DependencyKind::ExternalFile; |
| |
| for (const auto &dependent : allDependents->second.first) { |
| if (!dependent.kindMask.contains(DependencyKind::ExternalFile)) |
| continue; |
| if (isMarked(dependent.node)) |
| continue; |
| assert(dependent.flags & DependencyFlags::IsCascading); |
| visited.push_back(dependent.node); |
| markTransitive(visited, dependent.node); |
| } |
| } |
| |
| void |
| DependencyGraphImpl::markTransitive(SmallVectorImpl<const void *> &visited, |
| const void *node, MarkTracerImpl *tracer) { |
| assert(Provides.count(node) && "node is not in the graph"); |
| llvm::SpecificBumpPtrAllocator<MarkTracerImpl::Entry> scratchAlloc; |
| |
| struct WorklistEntry { |
| ArrayRef<MarkTracerImpl::Entry> Reason; |
| const void *Node; |
| bool IsCascading; |
| }; |
| |
| SmallVector<WorklistEntry, 16> worklist; |
| SmallPtrSet<const void *, 16> visitedSet; |
| |
| auto addDependentsToWorklist = [&](const void *next, |
| ArrayRef<MarkTracerImpl::Entry> reason) { |
| auto allProvided = Provides.find(next); |
| if (allProvided == Provides.end()) |
| return; |
| |
| for (const auto &provided : allProvided->second) { |
| auto allDependents = Dependencies.find(provided.name); |
| if (allDependents == Dependencies.end()) |
| continue; |
| |
| if (allDependents->second.second.contains(provided.kindMask)) |
| continue; |
| |
| // Record that we've traversed this dependency. |
| allDependents->second.second |= provided.kindMask; |
| |
| for (const auto &dependent : allDependents->second.first) { |
| if (dependent.node == next) |
| continue; |
| auto intersectingKinds = provided.kindMask & dependent.kindMask; |
| if (!intersectingKinds) |
| continue; |
| if (isMarked(dependent.node)) |
| continue; |
| bool isCascading{dependent.flags & DependencyFlags::IsCascading}; |
| |
| MutableArrayRef<MarkTracerImpl::Entry> newReason; |
| if (tracer) { |
| tracer->countStatsForNodeMarking(intersectingKinds, isCascading); |
| newReason = {scratchAlloc.Allocate(reason.size()+1), reason.size()+1}; |
| std::uninitialized_copy(reason.begin(), reason.end(), |
| newReason.begin()); |
| new (&newReason.back()) MarkTracerImpl::Entry({next, provided.name, |
| intersectingKinds}); |
| } |
| worklist.push_back({ newReason, dependent.node, isCascading }); |
| } |
| } |
| }; |
| |
| auto record = [&](WorklistEntry next) { |
| if (!visitedSet.insert(next.Node).second) |
| return; |
| visited.push_back(next.Node); |
| if (tracer) { |
| auto &savedReason = tracer->Table[next.Node]; |
| savedReason.clear(); |
| savedReason.append(next.Reason.begin(), next.Reason.end()); |
| } |
| }; |
| |
| // Always mark through the starting node, even if it's already marked. |
| markIntransitive(node); |
| addDependentsToWorklist(node, {}); |
| |
| while (!worklist.empty()) { |
| auto next = worklist.pop_back_val(); |
| |
| // Is this a non-cascading dependency? |
| if (!next.IsCascading) { |
| if (!isMarked(next.Node)) |
| record(next); |
| continue; |
| } |
| |
| addDependentsToWorklist(next.Node, next.Reason); |
| if (!markIntransitive(next.Node)) |
| continue; |
| record(next); |
| } |
| } |
| |
| void DependencyGraphImpl::MarkTracerImpl::countStatsForNodeMarking( |
| const OptionSet<DependencyKind> &Kind, bool IsCascading) const { |
| |
| if (!Stats) |
| return; |
| |
| auto &D = Stats->getDriverCounters(); |
| if (IsCascading) { |
| if (Kind & DependencyKind::TopLevelName) |
| D.DriverDepCascadingTopLevel++; |
| if (Kind & DependencyKind::DynamicLookupName) |
| D.DriverDepCascadingDynamic++; |
| if (Kind & DependencyKind::NominalType) |
| D.DriverDepCascadingNominal++; |
| if (Kind & DependencyKind::NominalTypeMember) |
| D.DriverDepCascadingMember++; |
| if (Kind & DependencyKind::NominalTypeMember) |
| D.DriverDepCascadingExternal++; |
| } else { |
| if (Kind & DependencyKind::TopLevelName) |
| D.DriverDepTopLevel++; |
| if (Kind & DependencyKind::DynamicLookupName) |
| D.DriverDepDynamic++; |
| if (Kind & DependencyKind::NominalType) |
| D.DriverDepNominal++; |
| if (Kind & DependencyKind::NominalTypeMember) |
| D.DriverDepMember++; |
| if (Kind & DependencyKind::NominalTypeMember) |
| D.DriverDepExternal++; |
| } |
| } |
| |
| void DependencyGraphImpl::MarkTracerImpl::printPath( |
| raw_ostream &out, |
| const void *item, |
| llvm::function_ref<void (const void *)> printItem) const { |
| for (const Entry &entry : Table.lookup(item)) { |
| out << "\t"; |
| printItem(entry.Node); |
| if (entry.KindMask.contains(DependencyKind::TopLevelName)) { |
| out << " provides top-level name '" << entry.Name << "'\n"; |
| |
| } else if (entry.KindMask.contains(DependencyKind::NominalType)) { |
| SmallString<64> name{entry.Name}; |
| if (name.front() == 'P') |
| name.push_back('_'); |
| out << " provides type '" |
| << swift::Demangle::demangleTypeAsString(name.str()) |
| << "'\n"; |
| |
| } else if (entry.KindMask.contains(DependencyKind::NominalTypeMember)) { |
| SmallString<64> name{entry.Name}; |
| size_t splitPoint = name.find('\0'); |
| assert(splitPoint != StringRef::npos); |
| |
| StringRef typePart; |
| if (name.front() == 'P') { |
| name[splitPoint] = '_'; |
| typePart = name.str().slice(0, splitPoint+1); |
| } else { |
| typePart = name.str().slice(0, splitPoint); |
| } |
| StringRef memberPart = name.str().substr(splitPoint+1); |
| |
| if (memberPart.empty()) { |
| out << " provides non-private members of type '" |
| << swift::Demangle::demangleTypeAsString(typePart) |
| << "'\n"; |
| } else { |
| out << " provides member '" << memberPart << "' of type '" |
| << swift::Demangle::demangleTypeAsString(typePart) |
| << "'\n"; |
| } |
| } else if (entry.KindMask.contains(DependencyKind::DynamicLookupName)) { |
| out << " provides AnyObject member '" << entry.Name << "'\n"; |
| |
| } else { |
| llvm_unreachable("not a dependency kind between nodes"); |
| } |
| } |
| } |
