| //===--- Evaluator.cpp - Request Evaluator Implementation -----------------===// |
| // |
| // 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 Evaluator class that evaluates and caches |
| // requests. |
| // |
| //===----------------------------------------------------------------------===// |
| #include "swift/AST/Evaluator.h" |
| #include "swift/AST/DiagnosticEngine.h" |
| #include "swift/Basic/LangOptions.h" |
| #include "swift/Basic/Range.h" |
| #include "swift/Basic/SourceManager.h" |
| #include "llvm/ADT/StringExtras.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/FileSystem.h" |
| #include "llvm/Support/SaveAndRestore.h" |
| |
| using namespace swift; |
| |
| std::string AnyRequest::getAsString() const { |
| std::string result; |
| { |
| llvm::raw_string_ostream out(result); |
| simple_display(out, *this); |
| } |
| return result; |
| } |
| |
| AbstractRequestFunction * |
| Evaluator::getAbstractRequestFunction(uint8_t zoneID, uint8_t requestID) const { |
| for (const auto &zone : requestFunctionsByZone) { |
| if (zone.first == zoneID) { |
| if (requestID < zone.second.size()) |
| return zone.second[requestID]; |
| |
| return nullptr; |
| } |
| } |
| |
| return nullptr; |
| } |
| |
| void Evaluator::registerRequestFunctions( |
| Zone zone, |
| ArrayRef<AbstractRequestFunction *> functions) { |
| uint8_t zoneID = static_cast<uint8_t>(zone); |
| #ifndef NDEBUG |
| for (const auto &zone : requestFunctionsByZone) { |
| assert(zone.first != zoneID); |
| } |
| #endif |
| |
| requestFunctionsByZone.push_back({zoneID, functions}); |
| } |
| |
| Evaluator::Evaluator(DiagnosticEngine &diags, const LangOptions &opts) |
| : diags(diags), |
| debugDumpCycles(opts.DebugDumpCycles), |
| buildDependencyGraph(opts.BuildRequestDependencyGraph), |
| recorder{} {} |
| |
| void Evaluator::emitRequestEvaluatorGraphViz(llvm::StringRef graphVizPath) { |
| std::error_code error; |
| llvm::raw_fd_ostream out(graphVizPath, error, llvm::sys::fs::F_Text); |
| printDependenciesGraphviz(out); |
| } |
| |
| bool Evaluator::checkDependency(const ActiveRequest &request) { |
| if (buildDependencyGraph) { |
| // Insert the request into the dependency graph if we haven't already. |
| auto req = AnyRequest(request); |
| dependencies.insert({req, {}}); |
| |
| // If there is an active request, record it's dependency on this request. |
| if (!activeRequests.empty()) { |
| auto activeDeps = dependencies.find_as(activeRequests.back()); |
| assert(activeDeps != dependencies.end()); |
| activeDeps->second.push_back(req); |
| } |
| } |
| |
| // Record this as an active request. |
| if (activeRequests.insert(request)) |
| return false; |
| |
| // Diagnose cycle. |
| diagnoseCycle(request); |
| return true; |
| } |
| |
| void Evaluator::diagnoseCycle(const ActiveRequest &request) { |
| if (debugDumpCycles) { |
| llvm::errs() << "===CYCLE DETECTED===\n"; |
| llvm::DenseSet<AnyRequest> visitedAnywhere; |
| llvm::SmallVector<AnyRequest, 4> visitedAlongPath; |
| std::string prefixStr; |
| SmallVector<AnyRequest, 8> highlightPath; |
| for (auto &req : activeRequests) |
| highlightPath.push_back(AnyRequest(req)); |
| printDependencies(AnyRequest(activeRequests.front()), llvm::errs(), |
| visitedAnywhere, visitedAlongPath, highlightPath, |
| prefixStr, /*lastChild=*/true); |
| } |
| |
| request.diagnoseCycle(diags); |
| for (const auto &step : llvm::reverse(activeRequests)) { |
| if (step == request) return; |
| |
| step.noteCycleStep(diags); |
| } |
| |
| llvm_unreachable("Diagnosed a cycle but it wasn't represented in the stack"); |
| } |
| |
| void Evaluator::printDependencies( |
| const AnyRequest &request, |
| llvm::raw_ostream &out, |
| llvm::DenseSet<AnyRequest> &visitedAnywhere, |
| llvm::SmallVectorImpl<AnyRequest> &visitedAlongPath, |
| llvm::ArrayRef<AnyRequest> highlightPath, |
| std::string &prefixStr, |
| bool lastChild) const { |
| out << prefixStr << " `--"; |
| |
| // Determine whether this node should be highlighted. |
| bool isHighlighted = false; |
| if (std::find(highlightPath.begin(), highlightPath.end(), request) |
| != highlightPath.end()) { |
| isHighlighted = true; |
| out.changeColor(llvm::buffer_ostream::Colors::GREEN); |
| } |
| |
| // Print this node. |
| simple_display(out, request); |
| |
| // Turn off the highlight. |
| if (isHighlighted) { |
| out.resetColor(); |
| } |
| |
| // Print the cached value, if known. |
| auto cachedValue = cache.find(request); |
| if (cachedValue != cache.end()) { |
| out << " -> "; |
| printEscapedString(cachedValue->second.getAsString(), out); |
| } |
| |
| if (!visitedAnywhere.insert(request).second) { |
| // We've already seed this node. Check whether it's part of a cycle. |
| if (std::find(visitedAlongPath.begin(), visitedAlongPath.end(), request) |
| != visitedAlongPath.end()) { |
| // We have a cyclic dependency. |
| out.changeColor(llvm::raw_ostream::RED); |
| out << " (cyclic dependency)\n"; |
| } else { |
| // We have seen this node before, but it's not a cycle. Elide its |
| // children. |
| out << " (elided)\n"; |
| } |
| |
| out.resetColor(); |
| } else if (dependencies.count(request) == 0) { |
| // We have not seen this node before, so we don't know its dependencies. |
| out.changeColor(llvm::raw_ostream::GREEN); |
| out << " (dependency not evaluated)\n"; |
| out.resetColor(); |
| |
| // Remove from the visited set. |
| visitedAnywhere.erase(request); |
| } else { |
| // Print children. |
| out << "\n"; |
| |
| // Setup the prefix to print the children. |
| prefixStr += ' '; |
| prefixStr += (lastChild ? ' ' : '|'); |
| prefixStr += " "; |
| |
| // Note that this request is along the path. |
| visitedAlongPath.push_back(request); |
| |
| // Print the children. |
| auto &dependsOn = dependencies.find(request)->second; |
| for (unsigned i : indices(dependsOn)) { |
| printDependencies(dependsOn[i], out, visitedAnywhere, visitedAlongPath, |
| highlightPath, prefixStr, i == dependsOn.size()-1); |
| } |
| |
| // Drop our changes to the prefix. |
| prefixStr.erase(prefixStr.end() - 4, prefixStr.end()); |
| |
| // Remove from the visited set and path. |
| visitedAnywhere.erase(request); |
| assert(visitedAlongPath.back() == request); |
| visitedAlongPath.pop_back(); |
| } |
| } |
| |
| void Evaluator::dumpDependencies(const AnyRequest &request) const { |
| printDependencies(request, llvm::dbgs()); |
| } |
| |
| void Evaluator::printDependenciesGraphviz(llvm::raw_ostream &out) const { |
| // Form a list of all of the requests we know about. |
| std::vector<AnyRequest> allRequests; |
| for (const auto &knownRequest : dependencies) { |
| allRequests.push_back(knownRequest.first); |
| } |
| |
| // Sort the list of requests based on the display strings, so we get |
| // deterministic output. |
| auto getDisplayString = [&](const AnyRequest &request) { |
| std::string result; |
| { |
| llvm::raw_string_ostream out(result); |
| simple_display(out, request); |
| } |
| return result; |
| }; |
| std::sort(allRequests.begin(), allRequests.end(), |
| [&](const AnyRequest &lhs, const AnyRequest &rhs) { |
| return getDisplayString(lhs) < getDisplayString(rhs); |
| }); |
| |
| // Manage request IDs to use in the resulting output graph. |
| llvm::DenseMap<AnyRequest, unsigned> requestIDs; |
| unsigned nextID = 0; |
| |
| // Prepopulate the known requests. |
| for (const auto &request : allRequests) { |
| requestIDs[request] = nextID++; |
| } |
| |
| auto getRequestID = [&](const AnyRequest &request) { |
| auto known = requestIDs.find(request); |
| if (known != requestIDs.end()) return known->second; |
| |
| // We discovered a new request; record it's ID and add it to the list of |
| // all requests. |
| allRequests.push_back(request); |
| requestIDs[request] = nextID; |
| return nextID++; |
| }; |
| |
| auto getNodeName = [&](const AnyRequest &request) { |
| std::string result; |
| { |
| llvm::raw_string_ostream out(result); |
| out << "request_" << getRequestID(request); |
| } |
| return result; |
| }; |
| |
| // Emit the graph header. |
| out << "digraph Dependencies {\n"; |
| |
| // Emit the edges. |
| llvm::DenseMap<AnyRequest, unsigned> inDegree; |
| for (const auto &source : allRequests) { |
| auto known = dependencies.find(source); |
| assert(known != dependencies.end()); |
| for (const auto &target : known->second) { |
| out << " " << getNodeName(source) << " -> " << getNodeName(target) |
| << ";\n"; |
| ++inDegree[target]; |
| } |
| } |
| |
| out << "\n"; |
| |
| static const char *colorNames[] = { |
| "aquamarine", |
| "blueviolet", |
| "brown", |
| "burlywood", |
| "cadetblue", |
| "chartreuse", |
| "chocolate", |
| "coral", |
| "cornflowerblue", |
| "crimson" |
| }; |
| const unsigned numColorNames = sizeof(colorNames) / sizeof(const char *); |
| |
| llvm::DenseMap<unsigned, unsigned> knownBuffers; |
| auto getColor = [&](const AnyRequest &request) -> Optional<const char *> { |
| SourceLoc loc = request.getNearestLoc(); |
| if (loc.isInvalid()) |
| return None; |
| |
| unsigned bufferID = diags.SourceMgr.findBufferContainingLoc(loc); |
| auto knownId = knownBuffers.find(bufferID); |
| if (knownId == knownBuffers.end()) { |
| knownId = knownBuffers.insert({bufferID, knownBuffers.size()}).first; |
| } |
| return colorNames[knownId->second % numColorNames]; |
| }; |
| |
| // Emit the nodes. |
| for (unsigned i : indices(allRequests)) { |
| const auto &request = allRequests[i]; |
| out << " " << getNodeName(request); |
| out << " [label=\""; |
| printEscapedString(request.getAsString(), out); |
| |
| auto cachedValue = cache.find(request); |
| if (cachedValue != cache.end()) { |
| out << " -> "; |
| printEscapedString(cachedValue->second.getAsString(), out); |
| } |
| out << "\""; |
| |
| if (auto color = getColor(request)) { |
| out << ", fillcolor=\"" << *color << "\""; |
| } |
| |
| out << "];\n"; |
| } |
| |
| // Emit "fake" nodes for each of the source buffers we encountered, so |
| // we know which file we're working from. |
| // FIXME: This approximates a "top level" request for, e.g., type checking |
| // an entire source file. |
| std::vector<unsigned> sourceBufferIDs; |
| for (const auto &element : knownBuffers) { |
| sourceBufferIDs.push_back(element.first); |
| } |
| std::sort(sourceBufferIDs.begin(), sourceBufferIDs.end()); |
| for (unsigned bufferID : sourceBufferIDs) { |
| out << " buffer_" << bufferID << "[label=\""; |
| printEscapedString(diags.SourceMgr.getIdentifierForBuffer(bufferID), out); |
| out << "\""; |
| |
| out << ", shape=\"box\""; |
| out << ", fillcolor=\"" |
| << colorNames[knownBuffers[bufferID] % numColorNames] << "\""; |
| out << "];\n"; |
| } |
| |
| // Emit "false" dependencies from source buffer IDs to any requests that (1) |
| // have no other incomining edges and (2) can be associated with a source |
| // buffer. |
| for (const auto &request : allRequests) { |
| if (inDegree[request] > 0) |
| continue; |
| |
| SourceLoc loc = request.getNearestLoc(); |
| if (loc.isInvalid()) |
| continue; |
| |
| unsigned bufferID = diags.SourceMgr.findBufferContainingLoc(loc); |
| out << " buffer_" << bufferID << " -> " << getNodeName(request) << ";\n"; |
| } |
| |
| // Done! |
| out << "}\n"; |
| } |
| |
| void Evaluator::dumpDependenciesGraphviz() const { |
| printDependenciesGraphviz(llvm::dbgs()); |
| } |
| |
| void evaluator::DependencyRecorder::realize( |
| const DependencyCollector::Reference &ref) { |
| auto *source = getActiveDependencySourceOrNull().get(); |
| if (!source->isPrimary()) { |
| return; |
| } |
| fileReferences[source].insert(ref); |
| } |
| |
| void evaluator::DependencyCollector::addUsedMember(NominalTypeDecl *subject, |
| DeclBaseName name) { |
| scratch.insert(Reference::usedMember(subject, name)); |
| return parent.realize(Reference::usedMember(subject, name)); |
| } |
| |
| void evaluator::DependencyCollector::addPotentialMember( |
| NominalTypeDecl *subject) { |
| scratch.insert(Reference::potentialMember(subject)); |
| return parent.realize(Reference::potentialMember(subject)); |
| } |
| |
| void evaluator::DependencyCollector::addTopLevelName(DeclBaseName name) { |
| scratch.insert(Reference::topLevel(name)); |
| return parent.realize(Reference::topLevel(name)); |
| } |
| |
| void evaluator::DependencyCollector::addDynamicLookupName(DeclBaseName name) { |
| scratch.insert(Reference::dynamic(name)); |
| return parent.realize(Reference::dynamic(name)); |
| } |
| |
| void evaluator::DependencyRecorder::record( |
| const llvm::SetVector<swift::ActiveRequest> &stack, |
| llvm::function_ref<void(DependencyCollector &)> rec) { |
| assert(!isRecording && "Probably not a good idea to allow nested recording"); |
| auto source = getActiveDependencySourceOrNull(); |
| if (source.isNull() || !source.get()->isPrimary()) { |
| return; |
| } |
| |
| llvm::SaveAndRestore<bool> restore(isRecording, true); |
| |
| DependencyCollector collector{*this}; |
| rec(collector); |
| if (collector.empty()) { |
| return; |
| } |
| |
| return unionNearestCachedRequest(stack.getArrayRef(), collector.scratch); |
| } |
| |
| void evaluator::DependencyRecorder::replay( |
| const llvm::SetVector<swift::ActiveRequest> &stack, |
| const swift::ActiveRequest &req) { |
| assert(!isRecording && "Probably not a good idea to allow nested recording"); |
| |
| auto source = getActiveDependencySourceOrNull(); |
| if (source.isNull() || !source.get()->isPrimary()) { |
| return; |
| } |
| |
| if (!req.isCached()) { |
| return; |
| } |
| |
| auto entry = requestReferences.find_as(req); |
| if (entry == requestReferences.end()) { |
| return; |
| } |
| |
| for (const auto &ref : entry->second) { |
| realize(ref); |
| } |
| |
| // N.B. This is a particularly subtle detail of the replay unioning step. The |
| // evaluator does not push cached requests onto the active request stack, |
| // so it is possible (and, in fact, quite likely) we'll wind up with an |
| // empty request stack. The remaining troublesome case is when we have a |
| // cached request being run through the uncached path - take the |
| // InterfaceTypeRequest, which involves many component requests, most of which |
| // are themselves cached. In such a case, the active stack will look like |
| // |
| // -> TypeCheckSourceFileRequest |
| // -> ... |
| // -> InterfaceTypeRequest |
| // -> ... |
| // -> UnderlyingTypeRequest |
| // |
| // We want the UnderlyingTypeRequest to union its names into the |
| // InterfaceTypeRequest, and if we were to just start searching the active |
| // stack backwards for a cached request we would find... |
| // the UnderlyingTypeRequest! So, we'll just drop it from consideration. |
| // |
| // We do *not* have to consider this during the recording step because none |
| // of the name lookup requests (or any dependency sinks in general) are |
| // cached. Should this change in the future, we will need to sink this logic |
| // into the union step itself. |
| const size_t d = (!stack.empty() && req == stack.back()) ? 1 : 0; |
| return unionNearestCachedRequest(stack.getArrayRef().drop_back(d), |
| entry->second); |
| } |
| |
| void evaluator::DependencyRecorder::unionNearestCachedRequest( |
| ArrayRef<swift::ActiveRequest> stack, |
| const DependencyCollector::ReferenceSet &scratch) { |
| auto nearest = std::find_if(stack.rbegin(), stack.rend(), |
| [](const auto &req){ return req.isCached(); }); |
| if (nearest == stack.rend()) { |
| return; |
| } |
| |
| auto entry = requestReferences.find_as(*nearest); |
| if (entry == requestReferences.end()) { |
| requestReferences.insert({AnyRequest(*nearest), scratch}); |
| } else { |
| entry->second.insert(scratch.begin(), scratch.end()); |
| } |
| } |
| |
| using namespace swift; |
| |
| void evaluator::DependencyRecorder::enumerateReferencesInFile( |
| const SourceFile *SF, ReferenceEnumerator f) const { |
| auto entry = fileReferences.find(SF); |
| if (entry == fileReferences.end()) { |
| return; |
| } |
| |
| for (const auto &ref : entry->getSecond()) { |
| switch (ref.kind) { |
| case DependencyCollector::Reference::Kind::Empty: |
| case DependencyCollector::Reference::Kind::Tombstone: |
| llvm_unreachable("Cannot enumerate dead reference!"); |
| case DependencyCollector::Reference::Kind::UsedMember: |
| case DependencyCollector::Reference::Kind::PotentialMember: |
| case DependencyCollector::Reference::Kind::TopLevel: |
| case DependencyCollector::Reference::Kind::Dynamic: |
| f(ref); |
| } |
| } |
| } |