include/swift/AST/FineGrainedDependencies.h

//===----- FineGrainedDependencies.h ----------------------------*- C++ -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2018 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
//
//===----------------------------------------------------------------------===//

#ifndef SWIFT_AST_FINE_GRAINED_DEPENDENCIES_H
#define SWIFT_AST_FINE_GRAINED_DEPENDENCIES_H

#include "swift/Basic/Debug.h"
#include "swift/Basic/Fingerprint.h"
#include "swift/Basic/LLVM.h"
#include "swift/Basic/NullablePtr.h"
#include "swift/Basic/Range.h"
#include "swift/Basic/ReferenceDependencyKeys.h"
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/Support/MD5.h"
#include "llvm/Support/MemoryBuffer.h"
#include "llvm/Support/YAMLParser.h"
#include "llvm/Support/YAMLTraits.h"
#include "llvm/Support/raw_ostream.h"
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

// Summary: The FineGrainedDependency* files contain infrastructure for a
// dependency system that, in the future, will be finer-grained than the current
// dependency system. At present--12/5/18--they are using the same input
// information as the current system and expected to produce the same results.
// In future, we'll gather more information, feed it into this dependency
// framework and get more selective recompilation.
//
// The frontend uses the information from the compiler to built a
// SourceFileDepGraph consisting of SourceFileDepGraphNodes.
// FineGrainedDependencies.* define these structures, and
// FineGrainedDependenciesProducer has the frontend-unique code used to build
// the SourceFileDepGraph.
//
// The driver reads the SourceFileDepGraph and integrates it into its dependency
// graph, a ModuleDepGraph consisting of ModuleDepGraphNodes.

// This file holds the declarations for the fine-grained dependency system
// that are used by both the driver and frontend.
// These include the graph structures common to both programs and also
// the frontend graph, which must be read by the driver.

//==============================================================================
// MARK: Shorthands
//==============================================================================

namespace swift {
class DependencyTracker;
class DiagnosticEngine;
class FrontendOptions;
class ModuleDecl;
class SourceFile;

/// Use a new namespace to help keep the experimental code from clashing.
namespace fine_grained_dependencies {

class SourceFileDepGraph;

using StringVec = std::vector<std::string>;

template <typename Element> using ConstPtrVec = std::vector<const Element *>;

template <typename First, typename Second>
using PairVec = std::vector<std::pair<First, Second>>;

using StringPairVec = PairVec<std::string, std::string>;

template <typename First, typename Second>
using ConstPtrPairVec = std::vector<std::pair<const First *, const Second *>>;

//==============================================================================
// MARK: General Utility classes
//==============================================================================

/// operator<< is needed for TwoStageMap::verify:
class DependencyKey;
raw_ostream &operator<<(raw_ostream &out, const DependencyKey &key);

/// A general class to reuse objects that are keyed by a subset of their
/// information. Used for \ref SourceFileDepGraph::Memoizer.

template <typename KeyT, typename ValueT> class Memoizer {
  using Memos = typename std::unordered_map<KeyT, ValueT>;
  /// Holding already-created objects.
  Memos memos;

public:
  Memoizer() = default;

  Optional<ValueT> findExisting(KeyT key) {
    auto iter = memos.find(key);
    if (iter != memos.end())
      return iter->second;
    return None;
  }

  /// \p createFn must create a \ref ValueT that corresponds to the \ref KeyT
  /// passed into it.
  ValueT
  findExistingOrCreateIfNew(KeyT key,
                            function_ref<ValueT(const KeyT &)> createFn) {
    if (auto existing = findExisting(key))
      return existing.getValue();
    ValueT v = createFn(key);
    (void)insert(key, v);
    return v;
  }

  /// Remember a new object (if differing from an existing one).
  /// \returns true iff the object was inserted.
  /// See \ref SourceFileDepGraphNode::addNode.
  bool insert(KeyT key, ValueT value) {
    return memos.insert(std::make_pair(key, value)).second;
  }
};

/// A general container for double-indexing, used (indirectly) in the
/// ModuleDepGraph.
template <typename Key1, typename Key2, typename Value> class TwoStageMap {
public:
  // Define this here so it can be changed easily.
  // TODO: Use llvm structure such as DenseMap. However, DenseMap does not
  // preserve pointers to elements, so be careful!
  // TODO: Consider using an ordered structure to guarantee determinism
  // when compilation order changes.
  template <typename Key, typename MapValue>
  using Map = std::unordered_map<Key, MapValue>;

  using InnerMap = Map<Key2, Value>;

private:
  Map<Key1, InnerMap> map;

public:
  Optional<Value> find(const Key1 &k1, const Key2 &k2) const {
    auto iter = map.find(k1);
    if (iter == map.end())
      return None;
    auto iter2 = iter->second.find(k2);
    return iter2 == iter->second.end() ? None : Optional<Value>(iter2->second);
  }

  NullablePtr<const InnerMap> find(const Key1 &k1) const {
    auto iter = map.find(k1);
    return iter == map.end() ? nullptr : &iter->second;
  }

  /// The sought value must be present.
  Value findAndErase(const Key1 &k1, const Key2 &k2) {
    auto &submap = map[k1];
    auto iter = submap.find(k2);
    assert(iter != submap.end() && "Cannot erase nonexistant element.");
    Value v = iter->second;
    submap.erase(iter);
    return v;
  }

  bool insert(const Key1 &k1, const Key2 &k2, Value &v) {
    return map[k1].insert(std::make_pair(k2, v)).second;
  }

  /// Move value from (old1, old2) to (new1, new2)
  bool move(const Key1 &old1, const Key2 &old2, const Key1 &new1,
            const Key2 &new2) {
    Value v = findAndErase(old1, old2);
    insert(old1, old2, v);
  }

  /// Returns the submap at \p k1. May create one if not present.
  Map<Key2, Value> &operator[](const Key1 &k1) { return map[k1]; }

  /// Invoke \p fn on each Key2 and Value matching (k, *)
  void forEachValueMatching(
      const Key1 &k1,
      function_ref<void(const Key2 &, const Value &)> fn) const {
    const auto &iter = map.find(k1);
    if (iter == map.end())
      return;
    for (auto &p : iter->second)
      fn(p.first, p.second);
  }

  /// Invoke \p fn for each entry
  void forEachEntry(
      function_ref<void(const Key1 &, const Key2 &, const Value &)> fn) const {
    for (const auto &p : map)
      for (const auto &p2 : p.second)
        fn(p.first, p2.first, p2.second);
  }

  /// Invoke fn for each Key1 and submap
  void
  forEachKey1(function_ref<void(const Key1 &, const InnerMap &)> fn) const {
    for (const auto &p : map)
      fn(p.first, p.second);
  }

  /// Check integrity and call \p verifyFn for each element, so that element can
  /// be verified.
  ///
  /// Requirements:
  // raw_ostream &operator<<(raw_ostream &out, const Key1 &), and
  // raw_ostream &operator<<(raw_ostream &out, const Key2 &)
  void verify(function_ref<void(const Key1 &k1, const Key2 &k2, Value v)>
                  verifyFn) const {
    for (const auto &p1 : map)
      for (const auto &p2 : p1.second) {
        const Key1 &k1 = p1.first;
        const Key2 &k2 = p2.first;
        Value const v = p2.second;
        verifyFn(k1, k2, v);
      }
  }
};

/// Double-indexing in either order; symmetric about key order.
/// The ModuleDepGraph needs this structure.
template <typename Key1, typename Key2, typename Value>
class BiIndexedTwoStageMap {
  TwoStageMap<Key1, Key2, Value> map1;
  TwoStageMap<Key2, Key1, Value> map2;

  using KeyPair = std::pair<Key1, Key2>;

public:
  using Key2Map = typename decltype(map1)::InnerMap;
  using Key1Map = typename decltype(map2)::InnerMap;

  bool insert(const Key1 &k1, const Key2 &k2, Value &v) {
    const bool r1 = map1.insert(k1, k2, v);
    const bool r2 = map2.insert(k2, k1, v);
    (void)r2;
    assertConsistent(r1, r2);
    return r1;
  }
  bool insert(const Key2 &k2, const Key1 &k1, Value &v) {
    return insert(k1, k2, v);
  }
  Optional<Value> find(const Key1 &k1, const Key2 &k2) const {
    auto v = map1.find(k1, k2);
    assert(assertConsistent(v, map2.find(k2, k1)));
    return v;
  }
  Optional<Value> find(const Key2 &k2, Key1 &k1) const { return find(k1, k2); }

  /// Return the submap for a given Key1. May create one, after the fashion of
  /// the standard libary.
  const Key2Map &operator[](const Key1 &k1) { return map1[k1]; }
  /// Return the submap for a given Key2. May create one, after the fashion of
  /// the standard libary.
  const Key1Map &operator[](const Key2 &k2) { return map2[k2]; }

  NullablePtr<const Key2Map> find(const Key1 &k1) const {
    return map1.find(k1);
  }
  NullablePtr<const Key1Map> find(const Key2 &k2) const {
    return map2.find(k2);
  }

  /// Element must be present.
  /// Return the erased value.
  Value findAndErase(const Key1 &k1, const Key2 &k2) {
    Value v1 = map1.findAndErase(k1, k2);
    Value v2 = map2.findAndErase(k2, k1);
    assertConsistent(v1, v2);
    return v1;
  }
  /// Element must be present.
  /// Return the erased value.
  Value findAndErase(const Key2 &k2, const Key1 &k1) {
    return findAndErase(k1, k2);
  }

  /// Invoke \p fn on each Key2 and Value matching (\p k1, *)
  void forEachValueMatching(
      const Key1 &k1,
      function_ref<void(const Key2 &, const Value &)> fn) const {
    map1.forEachValueMatching(k1, fn);
  }

  /// Invoke \p fn on each Key1 and Value matching (*, \p k2)
  void forEachValueMatching(
      const Key2 &k2,
      function_ref<void(const Key1 &, const Value &)> fn) const {
    map2.forEachValueMatching(k2, fn);
  }

  /// Invoke \p fn for each entry
  void forEachEntry(
      function_ref<void(const Key1 &, const Key2 &, const Value &)> fn) const {
    map1.forEachEntry(fn);
  }

  /// Invoke fn for each Key1 and submap
  void forEachKey1(function_ref<void(const Key1 &, const Key2Map &)> fn) const {
    map1.forEachKey1(fn);
  }

  /// Invoke fn for each Key2 and submap
  void forEachKey2(function_ref<void(const Key1 &, const Key1Map &)> fn) const {
    map2.forEachKey1(fn);
  }

  /// Verify the integrity of each map and the cross-map consistency.
  /// Then call \p verifyFn for each entry found in each of the two maps,
  /// passing an index so that the verifyFn knows which map is being tested.
  void verify(function_ref<void(const Key1 &k1, const Key2 &k2, Value v,
                                unsigned index)>
                  verifyFn) const {
    map1.verify([&](const Key1 &k1, const Key2 &k2, Value v) {
      assertConsistent(map2.find(k2, k1).getValue(), v);
    });
    map2.verify([&](const Key2 &k2, const Key1 &k1, Value v) {
      assertConsistent(map1.find(k1, k2).getValue(), v);
    });
    map1.verify([&](const Key1 &k1, const Key2 &k2, Value v) {
      verifyFn(k1, k2, v, 0);
    });
    map2.verify([&](const Key2 &k2, const Key1 &k1, Value v) {
      verifyFn(k1, k2, v, 1);
    });
  }

private:
  /// Helper function to ensure correspondence between \p v1 and \v2.
  template <typename T> static bool assertConsistent(const T v1, const T v2) {
    assert(v1 == v2 && "Map1 and map2 should have the same elements.");
    return true;
  }
};

// End of general declarations

//==============================================================================
// MARK: Start of fine-grained-dependency-specific code
//==============================================================================

/// Uses the provided module or source file to construct a dependency graph,
/// which is provided back to the caller in the continuation callback.
///
/// \Note The returned graph should not be escaped from the callback.
bool withReferenceDependencies(
    llvm::PointerUnion<const ModuleDecl *, const SourceFile *> MSF,
    const DependencyTracker &depTracker, StringRef outputPath,
    bool alsoEmitDotFile, llvm::function_ref<bool(SourceFileDepGraph &&)>);

//==============================================================================
// MARK: Enums
//==============================================================================


/// Instead of the status quo scheme of two kinds of "Depends", cascading and
/// non-cascading this code represents each entity ("Provides" in the status
/// quo), by a pair of nodes. One node represents the "implementation." If the
/// implementation changes, users of the entity need not be recompiled. The
/// other node represents the "interface." If the interface changes, any uses of
/// that definition will need to be recompiled. The implementation always
/// depends on the interface, since any change that alters the interface will
/// require the implementation to be rebuilt. The interface does not depend on
/// the implementation. In the dot files, interfaces are yellow and
/// implementations white. Each node holds an instance variable describing which
/// aspect of the entity it represents.
enum class DeclAspect { interface, implementation, aspectCount };
const std::string DeclAspectNames[]{"interface", "implementation"};

template <typename FnT> void forEachAspect(FnT fn) {
  for (size_t i = 0; i < size_t(DeclAspect::aspectCount); ++i)
    fn(DeclAspect(i));
}

/// A pair of nodes that represent the two aspects of a given entity.
/// Templated in order to serve for either SourceFileDepGraphNodes or
/// ModuleDepGraphNodes.
template <typename NodeT> class InterfaceAndImplementationPair {
  NodeT *interface;
  NodeT *implementation;

public:
  InterfaceAndImplementationPair()
      : interface(nullptr), implementation(nullptr) {}

  InterfaceAndImplementationPair(NodeT *interface, NodeT *implementation)
      : interface(interface), implementation(implementation) {
    assert(
        interface->getKey().isInterface() &&
        implementation->getKey().isImplementation() &&
        "Interface must be interface, implementation must be implementation.");
  }

  NodeT *getInterface() const { return interface; }
  NodeT *getImplementation() const { return implementation; }
};

//==============================================================================
// MARK: DependencyKey
//==============================================================================

/// The dependency system loses some precision by lumping entities together for
/// the sake of simplicity. In the future, it might be finer-grained. The
/// DependencyKey carries the information needed to find all uses from a def
/// because the data structures in the graph map the key of an entity to all the
/// nodes representing uses of that entity, even though the node may not really
/// use the entity. For example, argument names of functions are ignored.
class DependencyKey {
  // For import/export
  friend ::llvm::yaml::MappingTraits<DependencyKey>;

  NodeKind kind;
  DeclAspect aspect;
  /// The mangled context type name of the holder for \ref potentialMember, \ref
  /// member, and \ref nominal kinds. Otherwise unused.
  std::string context;
  /// The basic name of the entity. Unused for \ref potentialMember and \ref
  /// nominal kinds.
  std::string name;

public:
  /// See \ref SourceFileDepGraphNode::SourceFileDepGraphNode().
  DependencyKey()
      : kind(NodeKind::kindCount), aspect(DeclAspect::aspectCount), context(),
        name() {}

  /// For constructing a key in the frontend.
  DependencyKey(NodeKind kind, DeclAspect aspect, const std::string &context,
                const std::string &name)
      : kind(kind), aspect(aspect), context(context), name(name) {
    assert(verify());
  }

  NodeKind getKind() const { return kind; }
  DeclAspect getAspect() const { return aspect; }
  StringRef getContext() const { return context; }
  StringRef getName() const { return name; }

  StringRef getSwiftDepsFromASourceFileProvideNodeKey() const {
    assert(getKind() == NodeKind::sourceFileProvide &&
           "Receiver must be sourceFileProvide.");
    return getName();
  }

  bool operator==(const DependencyKey &rhs) const {
    return getKind() == rhs.getKind() && getAspect() == rhs.getAspect() &&
           getContext() == rhs.getContext() && getName() == rhs.getName();
  }

  bool operator!=(const DependencyKey &rhs) const { return !(*this == rhs); }

  /// Return true if this key can be recorded as a use of def.
  /// If everything is the same except for aspect, it's tricky:
  /// The implementation does not depend on the interface; it's the other way
  /// around.
  bool canDependUpon(const DependencyKey &def) const {
    if (getKind() != def.getKind() || getContext() != def.getContext() ||
        getName() != def.getName())
      return true;
    if (getAspect() == def.getAspect())
      return false;
    if (getAspect() == DeclAspect::implementation)
      return false;
    return true;
  }

  size_t hash() const {
    return llvm::hash_combine(kind, aspect, name, context);
  }
  bool isImplementation() const {
    return getAspect() == DeclAspect::implementation;
  }
  bool isInterface() const { return getAspect() == DeclAspect::interface; }

  /// Create just the interface half of the keys for a provided Decl or Decl
  /// pair
  template <NodeKind kind, typename Entity>
  static DependencyKey createForProvidedEntityInterface(Entity);

  /// Given some type of provided entity compute the context field of the key.
  template <NodeKind kind, typename Entity>
  static std::string computeContextForProvidedEntity(Entity);

  DependencyKey correspondingImplementation() const {
    return withAspect(DeclAspect::implementation);
  }

  DependencyKey withAspect(DeclAspect aspect) const {
    return DependencyKey(kind, aspect, context, name);
  }

  /// Given some type of provided entity compute the name field of the key.
  template <NodeKind kind, typename Entity>
  static std::string computeNameForProvidedEntity(Entity);

  static DependencyKey createKeyForWholeSourceFile(DeclAspect,
                                                   StringRef swiftDeps);

  std::string humanReadableName() const;

  StringRef aspectName() const { return DeclAspectNames[size_t(aspect)]; }

  void dump(llvm::raw_ostream &os) const { os << asString() << "\n"; }
  SWIFT_DEBUG_DUMP { dump(llvm::errs()); }

  /// For debugging, needed for \ref TwoStageMap::verify
  std::string asString() const;

  bool verify() const;

  /// Since I don't have Swift enums, ensure name corresspondence here.
  static void verifyNodeKindNames();

  /// Since I don't have Swift enums, ensure name corresspondence here.
  static void verifyDeclAspectNames();

private:
  // Name conversion helpers
  static std::string demangleTypeAsContext(StringRef);
};
} // namespace fine_grained_dependencies
} // namespace swift

template <>
struct std::hash<typename swift::fine_grained_dependencies::DependencyKey> {
  size_t
  operator()(const swift::fine_grained_dependencies::DependencyKey &key) const {
    return key.hash();
  }
};
template <>
struct std::hash<typename swift::fine_grained_dependencies::DeclAspect> {
  size_t
  operator()(const swift::fine_grained_dependencies::DeclAspect aspect) const {
    return size_t(aspect);
  }
};
template <>
struct std::hash<typename swift::fine_grained_dependencies::NodeKind> {
  size_t
  operator()(const swift::fine_grained_dependencies::NodeKind kind) const {
    return size_t(kind);
  }
};

namespace swift {
namespace fine_grained_dependencies {
using ContextNameFingerprint =
    std::tuple<std::string, std::string, Optional<std::string>>;
}
} // namespace swift

//==============================================================================
// MARK: DepGraphNode
//==============================================================================

/// Part of an experimental, new, infrastructure that can handle fine-grained
/// dependencies. The basic idea is a graph, where each node represents the
/// definition of entity in the program (a Decl or a source file/swiftdeps
/// file). Each node will (eventually) have a fingerprint so that we can tell
/// when an entity has changed. Arcs in the graph connect a definition that
/// provides information to a definition that uses the information, so that when
/// something changes, a traversal of the arc reveals the entities needing to be
/// rebuilt.
///
/// Some changes are transitive (i.e. “cascading”): given A -> B -> C, if the
/// link from A to B cascades then C must be rebuilt even if B does not change.
/// Rather than having two kinds of arcs, I am representing this distinction by
/// splitting the nodes: each entity has two nodes: one for its interface and
/// another for its implementation. A cascading dependency translates into one
/// that goes to the interface, while a non-cascading one goes to the
/// implementation. These graphs reflect what can be known from today’s
/// dependency information. Once the infrastructure is in place, we can work on
/// improving it.

namespace swift {
namespace fine_grained_dependencies {
class DepGraphNode {
  /// Def->use arcs go by DependencyKey. There may be >1 node for a given key.
  DependencyKey key;
  /// The frontend records in the fingerprint, all of the information about an
  /// entity, such that any uses need be rebuilt only if the fingerprint
  /// changes.
  /// When the driver reloads a dependency graph (after a frontend job has run),
  /// it can use the fingerprint to determine if the entity has changed and thus
  /// if uses need to be recompiled.
  ///
  /// However, at present, the frontend does not record this information for
  /// every Decl; it only records it for the source-file-as-a-whole in the
  /// interface hash. The inteface hash is a product of all the tokens that are
  /// not inside of function bodies. Thus, if there is no fingerprint, when the
  /// frontend creates an interface node,
  //  it adds a dependency to it from the implementation source file node (which
  //  has the intefaceHash as its fingerprint).
  Optional<Fingerprint> fingerprint;

  friend ::llvm::yaml::MappingTraits<DepGraphNode>;

public:
  /// See \ref SourceFileDepGraphNode::SourceFileDepGraphNode().
  DepGraphNode() : key(), fingerprint() {}

  DepGraphNode(DependencyKey key, Optional<Fingerprint> fingerprint)
      : key(key), fingerprint(fingerprint) {}
  DepGraphNode(const DepGraphNode &other) = default;

  bool operator==(const DepGraphNode &other) const {
    return getKey() == other.getKey() &&
           getFingerprint() == other.getFingerprint();
  }

  const DependencyKey &getKey() const { return key; }

  /// Only used when the driver is reading a SourceFileDepGraphNode.
  void setKey(const DependencyKey &key) {
    this->key = key;
  }

  const Optional<Fingerprint> getFingerprint() const { return fingerprint; }
  /// When driver reads a SourceFileDepGraphNode, it may be a node that was
  /// created to represent a name-lookup (a.k.a a "depend") in the frontend. In
  /// that case, the node represents an entity that resides in some other file
  /// whose swiftdeps file has not been read by the driver. Later, when the
  /// driver does read the node corresponding to the actual Decl, that node may
  /// (someday) have a fingerprint. In order to preserve the
  /// ModuleDepGraphNode's identity but bring its fingerprint up to date, it
  /// needs to set the fingerprint *after* the node has been created.
  void setFingerprint(Optional<Fingerprint> fp) { fingerprint = fp; }

  SWIFT_DEBUG_DUMP;
  void dump(llvm::raw_ostream &os) const;

  std::string humanReadableName(StringRef where) const;

  bool verify() const {
    key.verify();
    return true;
  }
};

//==============================================================================
// MARK: SourceFileDepGraphNode
//==============================================================================
class SourceFileDepGraph;

/// A node in a graph that represents the dependencies computed when compiling a
/// single primary source file. Each such node represents a definition. Such a
/// graph is always constructed monotonically; it never shrinks or changes once
/// finished. The frontend does not need to be able to remove nodes from the
/// graph, so it can represent arcs with a simple format relying on sequence
/// numbers.
class SourceFileDepGraphNode : public DepGraphNode {
  /// To represent Arcs in a serializable fashion, the code puts all nodes in
  /// the graph in a vector (`allNodes`), and uses the index in that vector to
  /// refer to the node.
  size_t sequenceNumber = ~0;

  /// Holds the sequence numbers of definitions I depend upon.
  llvm::SetVector<size_t> defsIDependUpon;

  /// True iff a Decl exists for this node.
  /// If a provides and a depends in the existing system both have the same key,
  /// only one SourceFileDepGraphNode is emitted.
  bool isProvides = false;

  friend ::llvm::yaml::MappingContextTraits<SourceFileDepGraphNode,
                                            SourceFileDepGraph>;

public:
  /// When the driver imports a node create an uninitialized instance for
  /// deserializing.
  SourceFileDepGraphNode() : DepGraphNode() {}

  /// Used by the frontend to build nodes.
  SourceFileDepGraphNode(DependencyKey key, Optional<Fingerprint> fingerprint,
                         bool isProvides)
      : DepGraphNode(key, fingerprint), isProvides(isProvides) {
    assert(key.verify());
  }

  bool isDepends() const { return !getIsProvides(); }

  bool getIsProvides() const { return isProvides; }
  void setIsProvides() { isProvides = true; }

  bool operator==(const SourceFileDepGraphNode &other) const {
    return DepGraphNode::operator==(other) &&
           sequenceNumber == other.sequenceNumber &&
           defsIDependUpon == other.defsIDependUpon &&
           isProvides == other.isProvides;
  }

  size_t getSequenceNumber() const { return sequenceNumber; }
  void setSequenceNumber(size_t n) { sequenceNumber = n; }

  /// In the frontend, def-use links are kept in the def node.
  /// Call \p fn with the sequence number of each use.
  void forEachDefIDependUpon(function_ref<void(size_t)> fn) const {
    std::for_each(defsIDependUpon.begin(), defsIDependUpon.end(), fn);
  }

  /// Record the sequence number, \p n, of another use.
  /// The relationship between an interface and its implementation is NOT
  /// included here. See \c
  /// SourceFileDepGraph::findExistingNodePairOrCreateAndAddIfNew.
  void addDefIDependUpon(size_t n) {
    if (n != getSequenceNumber())
      defsIDependUpon.insert(n);
  }

  std::string humanReadableName() const {
    return DepGraphNode::humanReadableName(getIsProvides() ? "here"
                                                           : "somewhere else");
  }

  SWIFT_DEBUG_DUMP;
  void dump(llvm::raw_ostream &os) const;

  bool verify() const {
    DepGraphNode::verify();
    assert(getIsProvides() || isDepends());
    assert(verifySequenceNumber());
    return true;
  }

  bool verifySequenceNumber() const {
    const auto &k = getKey();
    if (k.getKind() != NodeKind::sourceFileProvide)
      return true;
    switch (k.getAspect()) {
    case DeclAspect::interface:
      assert(getSequenceNumber() == sourceFileProvidesInterfaceSequenceNumber);
      return true;
    case DeclAspect::implementation:
      assert(getSequenceNumber() ==
             sourceFileProvidesImplementationSequenceNumber);
      return true;
    default:
      llvm_unreachable("neither interface nor implementation");
    }
  }
  static constexpr const size_t sourceFileProvidesInterfaceSequenceNumber = 0;
  static constexpr const size_t sourceFileProvidesImplementationSequenceNumber =
      1;
};

//==============================================================================
// MARK: SourceFileDepGraph
//==============================================================================

/// The dependency graph produced by the frontend and consumed by the driver.
/// See \ref Node in FineGrainedDependencies.h
class SourceFileDepGraph {
  /// Every node in the graph. Indices used for serialization.
  /// Use addNode instead of adding directly.
  std::vector<SourceFileDepGraphNode *> allNodes;

  /// When the frontend constructs the SourceFileDepGraph, it might encounter a
  /// name-lookup ("Depend") or a Decl ("Provide") whose node would be
  /// indistinguishable from a node it has already constructed. So it memoizes
  /// those nodes, reusing an existing node rather than creating a new one.
  Memoizer<DependencyKey, SourceFileDepGraphNode *> memoizedNodes;

public:
  /// For templates such as DotFileEmitter.
  using NodeType = SourceFileDepGraphNode;

  friend ::llvm::yaml::MappingTraits<SourceFileDepGraph>;

  SourceFileDepGraph() = default;
  SourceFileDepGraph(const SourceFileDepGraph &g) = delete;
  SourceFileDepGraph(SourceFileDepGraph &&g) = default;

  /// Nodes are owned by the graph.
  ~SourceFileDepGraph() {
    forEachNode([&](SourceFileDepGraphNode *n) { delete n; });
  }

  SourceFileDepGraphNode *getNode(size_t sequenceNumber) const;

  InterfaceAndImplementationPair<SourceFileDepGraphNode>
  getSourceFileNodePair() const;

  StringRef getSwiftDepsOfJobThatProducedThisGraph() const;

  std::string getGraphID() const {
    return getSourceFileNodePair().getInterface()->getKey().humanReadableName();
  }

  void forEachNode(function_ref<void(SourceFileDepGraphNode *)> fn) const {
    for (auto i : indices(allNodes))
      fn(getNode(i));
  }

  void forEachArc(function_ref<void(const SourceFileDepGraphNode *def,
                                    const SourceFileDepGraphNode *use)>
                      fn) const;

  void forEachDefDependedUponBy(
      const SourceFileDepGraphNode *n,
      function_ref<void(SourceFileDepGraphNode *)> fn) const {
    n->forEachDefIDependUpon([&](size_t useIndex) { fn(getNode(useIndex)); });
  }

  /// The frontend creates a pair of nodes for every tracked Decl and the source
  /// file itself.
  InterfaceAndImplementationPair<SourceFileDepGraphNode>
  findExistingNodePairOrCreateAndAddIfNew(const DependencyKey &interfaceKey,
                                          Optional<Fingerprint> fingerprint);

  NullablePtr<SourceFileDepGraphNode>
  findExistingNode(const DependencyKey &key);

  SourceFileDepGraphNode *
  findExistingNodeOrCreateIfNew(const DependencyKey &key,
                                const Optional<Fingerprint> fingerprint,
                                bool isProvides);

  /// \p Use is the Node that must be rebuilt when \p def changes.
  /// Record that fact in the graph.
  void addArc(SourceFileDepGraphNode *def, SourceFileDepGraphNode *use) {
    getNode(use->getSequenceNumber())
        ->addDefIDependUpon(def->getSequenceNumber());
  }

  /// Read a swiftdeps file at \p path and return a SourceFileDepGraph if
  /// successful.
  Optional<SourceFileDepGraph> static loadFromPath(StringRef);

  /// Read a swiftdeps file from \p buffer and return a SourceFileDepGraph if
  /// successful.
  Optional<SourceFileDepGraph> static loadFromBuffer(llvm::MemoryBuffer &);
  Optional<SourceFileDepGraph> static loadFromSwiftModuleBuffer(
      llvm::MemoryBuffer &);

  void verifySame(const SourceFileDepGraph &other) const;

  // Fail with a message instead of returning false.
  bool verify() const;

  /// Ensure that when read, the graph is the same as what was written.
  bool verifyReadsWhatIsWritten(StringRef path) const;

  bool verifySequenceNumber() const;

  void emitDotFile(StringRef outputPath, DiagnosticEngine &diags);

  void addNode(SourceFileDepGraphNode *n) {
    n->setSequenceNumber(allNodes.size());
    allNodes.push_back(n);
    assert(n->verifySequenceNumber() &&
           "Certain nodes must be in certain places");
  }
};

//==============================================================================
// MARK: DotFileEmitter
//==============================================================================

/// To aid in debugging, both the SourceFileDepGraph and the ModuleDepGraph can
/// be written out as dot files, which can be read into graphfiz and OmniGraffle
/// to display the graphs.
template <typename GraphT> class DotFileEmitter {
  using NodeT = typename GraphT::NodeType;

  /// Stream to write to.
  llvm::raw_ostream &out;

  /// Human-readable graph identifier.
  std::string graphID;

  /// For the sake of clarity, we commonly exclude these.
  const bool includeExternals, includeAPINotes;

  /// The graph to write out.
  const GraphT &g;

  /// Since ModuleDepGraphNodes have no sequence numbers, use the stringified
  /// pointer value for an nodeID. Memoize the nodes here.
  std::unordered_set<std::string> nodeIDs;

public:
  DotFileEmitter(llvm::raw_ostream &out, GraphT &g, const bool includeExternals,
                 const bool includeAPINotes)
      : out(out), graphID(g.getGraphID()), includeExternals(includeExternals),
        includeAPINotes(includeAPINotes), g(g) {}

  void emit() {
    emitPrelude();
    emitLegend();
    emitNodes();
    emitArcs();
    emitPostlude();
  }

private:
  void emitPrelude() const { out << "digraph \"" << graphID << "\" {\n"; }
  void emitPostlude() const { out << "\n}\n"; }
  void emitNodes() {
    g.forEachNode([&](const NodeT *n) { emitGraphNode(n); });
  }
  static std::string nodeID(const NodeT *n) {
    return std::to_string(size_t(n));
  }
  void emitGraphNode(const NodeT *n) {
    if (includeGraphNode(n)) {
      emitDotNode(nodeID(n), nodeLabel(n), shape(n), fillColor(n), style(n));
    }
  }
  void emitDotNode(StringRef id, StringRef label, StringRef shape,
                   StringRef fillColor, StringRef style = StringRef()) {
    auto inserted = nodeIDs.insert(id.str());
    (void)inserted;
    assert(inserted.second && "NodeIDs must be unique.");
    out << "\"" << id << "\" [ "
        << "label = \"" << label << "\", "
        << "shape = " << shape << " , "
        << "fillcolor = " << fillColor;
    if (!style.empty())
      out << ", "
          << "style = " << style;
    out << " ];\n";
  }
  bool includeGraphNode(const NodeT *n) const {
    bool externalPredicate =
        includeExternals || n->getKey().getKind() != NodeKind::externalDepend;
    bool apiPredicate =
        includeAPINotes ||
        !StringRef(n->getKey().humanReadableName()).endswith(".apinotes");
    return externalPredicate && apiPredicate;
  }
  bool includeGraphArc(const NodeT *def, const NodeT *use) const {
    return includeGraphNode(def) && includeGraphNode(use);
  }
  void emitArcs() {
    g.forEachArc([&](const NodeT *def, const NodeT *use) {
      if (includeGraphArc(def, use))
        emitGraphArc(def, use);
    });
  }
  /// show arc from def to use
  void emitGraphArc(const NodeT *def, const NodeT *use) const {
    auto defID = nodeID(def);
    auto useID = nodeID(use);
    assert(nodeIDs.count(defID) && "Definition must exist.");
    assert(nodeIDs.count(useID) && "Use must exist.");
    emitDotArc(defID, useID);
  }
  void emitDotArc(StringRef from, StringRef to) const {
    out << from << " -> " << to << ";\n";
  }
  static StringRef shape(const NodeT *n) {
    return shape(n->getKey().getKind());
  }
  static StringRef style(const NodeT *n) {
    return !n->getIsProvides() ? "dotted" : "solid";
  }
  static const std::string &shape(const NodeKind kind) {
    static const std::string shapes[]{"box",      "parallelogram", "ellipse",
                                      "triangle", "diamond",       "house",
                                      "hexagon"};
    return shapes[size_t(kind)];
  }
  static std::string fillColor(const NodeT *n) {
    return !n->getIsProvides() ? "azure"
                               : n->getKey().isInterface() ? "yellow" : "white";
  }

  /// Emit sample types of dependencies with their corresponding shapes.
  void emitLegend() {
    for (size_t i = 0; i < size_t(NodeKind::kindCount); ++i) {
      const auto s = shape(NodeKind(i));
      emitDotNode(s, NodeKindNames[i], s, "azure");
    }
  }
  static std::string nodeLabel(const NodeT *n) {
    return llvm::yaml::escape(n->humanReadableName());
  }
};

} // end namespace fine_grained_dependencies
} // end namespace swift

#endif // SWIFT_AST_FINE_GRAINED_DEPENDENCIES_H