Graphviz: Restore support for per-target dependency graph options

The behaviors controlled by options `GRAPHVIZ_GENERATE_PER_TARGET` and
`GRAPHVIZ_GENERATE_DEPENDERS` were broken by commit 553658393c (Graphviz:
added test suite, fixes, enhancements, 2019-10-08, v3.17.0-rc1~615^2).
It had not been covered in the test suite previously, and those changes
left out checks for these features from the `default_options` case.

Implement the previously-existing behavior in the new graphviz
generation engine added by the above-mentioned commit.

Fixes: #20928

2 files changed, 145 insertions, 7 deletions

diff --git a/Source/cmGraphVizWriter.cxx b/Source/cmGraphVizWriter.cxx
index 1b776786a2..e03b2ca6c6 100644
--- a/Source/cmGraphVizWriter.cxx
+++ b/Source/cmGraphVizWriter.cxx
@@ -67,6 +67,36 @@ const char* getShapeForTarget(const cmLinkItem& item)
       return GRAPHVIZ_NODE_SHAPE_LIBRARY_UNKNOWN;
   }
 }
+
+struct DependeesDir
+{
+  template <typename T>
+  static const cmLinkItem& src(const T& con)
+  {
+    return con.src;
+  }
+
+  template <typename T>
+  static const cmLinkItem& dst(const T& con)
+  {
+    return con.dst;
+  }
+};
+
+struct DependersDir
+{
+  template <typename T>
+  static const cmLinkItem& src(const T& con)
+  {
+    return con.dst;
+  }
+
+  template <typename T>
+  static const cmLinkItem& dst(const T& con)
+  {
+    return con.src;
+  }
+};
 }
 
 cmGraphVizWriter::cmGraphVizWriter(std::string const& fileName,
@@ -173,18 +203,16 @@ void cmGraphVizWriter::VisitLink(cmLinkItem const& depender,
     return;
   }
 
+  // write global data directly
   this->WriteConnection(this->GlobalFileStream, depender, dependee, scopeType);
 
   if (this->GeneratePerTarget) {
-    auto fileStream = PerTargetFileStreams[depender.AsStr()].get();
-    this->WriteNode(*fileStream, dependee);
-    this->WriteConnection(*fileStream, depender, dependee, scopeType);
+    PerTargetConnections[depender].emplace_back(depender, dependee, scopeType);
   }
 
   if (this->GenerateDependers) {
-    auto fileStream = TargetDependersFileStreams[dependee.AsStr()].get();
-    this->WriteNode(*fileStream, depender);
-    this->WriteConnection(*fileStream, depender, dependee, scopeType);
+    TargetDependersConnections[dependee].emplace_back(dependee, depender,
+                                                      scopeType);
   }
 }
 
@@ -288,10 +316,86 @@ void cmGraphVizWriter::Write()
     }
   }
 
+  // write global data and collect all connection data for per target graphs
   for (auto const gt : sortedGeneratorTargets) {
     auto item = cmLinkItem(gt, false, gt->GetBacktrace());
     this->VisitItem(item);
   }
+
+  if (this->GeneratePerTarget) {
+    WritePerTargetConnections<DependeesDir>(PerTargetConnections,
+                                            PerTargetFileStreams);
+  }
+
+  if (this->GenerateDependers) {
+    WritePerTargetConnections<DependersDir>(TargetDependersConnections,
+                                            TargetDependersFileStreams);
+  }
+}
+
+void cmGraphVizWriter::FindAllConnections(const ConnectionsMap& connectionMap,
+                                          const cmLinkItem& rootItem,
+                                          Connections& extendedCons,
+                                          std::set<cmLinkItem>& visitedItems)
+{
+  // some "targets" are not in map, e.g. linker flags as -lm or
+  // targets without dependency.
+  // in both cases we are finished with traversing the graph
+  if (connectionMap.find(rootItem) == connectionMap.cend()) {
+    return;
+  }
+
+  const Connections& origCons = connectionMap.at(rootItem);
+
+  for (const Connection& con : origCons) {
+    extendedCons.emplace_back(con);
+    const cmLinkItem& dstItem = con.dst;
+    bool const visited = visitedItems.find(dstItem) != visitedItems.cend();
+    if (!visited) {
+      visitedItems.insert(dstItem);
+      FindAllConnections(connectionMap, dstItem, extendedCons, visitedItems);
+    }
+  }
+}
+
+void cmGraphVizWriter::FindAllConnections(const ConnectionsMap& connectionMap,
+                                          const cmLinkItem& rootItem,
+                                          Connections& extendedCons)
+{
+  std::set<cmLinkItem> visitedItems = { rootItem };
+  FindAllConnections(connectionMap, rootItem, extendedCons, visitedItems);
+}
+
+template <typename DirFunc>
+void cmGraphVizWriter::WritePerTargetConnections(
+  const ConnectionsMap& connections, const FileStreamMap& streams)
+{
+  // the per target connections must be extended by indirect dependencies
+  ConnectionsMap extendedConnections;
+  for (auto const& conPerTarget : connections) {
+    const cmLinkItem& rootItem = conPerTarget.first;
+    Connections& extendedCons = extendedConnections[conPerTarget.first];
+    FindAllConnections(connections, rootItem, extendedCons);
+  }
+
+  for (auto const& conPerTarget : extendedConnections) {
+    const cmLinkItem& rootItem = conPerTarget.first;
+
+    // some of the nodes are excluded completely and are not written
+    if (this->ItemExcluded(rootItem)) {
+      continue;
+    }
+
+    const Connections& cons = conPerTarget.second;
+    auto fileStream = streams.at(rootItem.AsStr()).get();
+
+    for (const Connection& con : cons) {
+      const cmLinkItem& src = DirFunc::src(con);
+      const cmLinkItem& dst = DirFunc::dst(con);
+      this->WriteNode(*fileStream, con.dst);
+      this->WriteConnection(*fileStream, src, dst, con.scopeType);
+    }
+  }
 }
 
 void cmGraphVizWriter::WriteHeader(cmGeneratedFileStream& fs,
diff --git a/Source/cmGraphVizWriter.h b/Source/cmGraphVizWriter.h
index 578660dbbb..9766068a2a 100644
--- a/Source/cmGraphVizWriter.h
+++ b/Source/cmGraphVizWriter.h
@@ -7,16 +7,18 @@
 
 #include <map>
 #include <memory>
+#include <set>
 #include <string>
+#include <utility>
 #include <vector>
 
 #include "cmsys/RegularExpression.hxx"
 
 #include "cmGeneratedFileStream.h"
+#include "cmLinkItem.h"
 #include "cmLinkItemGraphVisitor.h"
 #include "cmStateTypes.h"
 
-class cmLinkItem;
 class cmGlobalGenerator;
 
 /** This class implements writing files for graphviz (dot) for graphs
@@ -47,6 +49,22 @@ private:
   using FileStreamMap =
     std::map<std::string, std::unique_ptr<cmGeneratedFileStream>>;
 
+  struct Connection
+  {
+    Connection(cmLinkItem s, cmLinkItem d, std::string scope)
+      : src(std::move(s))
+      , dst(std::move(d))
+      , scopeType(std::move(scope))
+    {
+    }
+
+    cmLinkItem src;
+    cmLinkItem dst;
+    std::string scopeType;
+  };
+  using Connections = std::vector<Connection>;
+  using ConnectionsMap = std::map<cmLinkItem, Connections>;
+
   void VisitLink(cmLinkItem const& depender, cmLinkItem const& dependee,
                  bool isDirectLink, std::string const& scopeType = "");
 
@@ -66,6 +84,19 @@ private:
                        cmLinkItem const& dependeeTargetName,
                        std::string const& edgeStyle);
 
+  void FindAllConnections(const ConnectionsMap& connectionMap,
+                          const cmLinkItem& rootItem,
+                          Connections& extendedCons,
+                          std::set<cmLinkItem>& visitedItems);
+
+  void FindAllConnections(const ConnectionsMap& connectionMap,
+                          const cmLinkItem& rootItem,
+                          Connections& extendedCons);
+
+  template <typename DirFunc>
+  void WritePerTargetConnections(const ConnectionsMap& connections,
+                                 const FileStreamMap& streams);
+
   bool ItemExcluded(cmLinkItem const& item);
   bool ItemNameFilteredOut(std::string const& itemName);
   bool TargetTypeEnabled(cmStateEnums::TargetType targetType) const;
@@ -83,6 +114,9 @@ private:
   FileStreamMap PerTargetFileStreams;
   FileStreamMap TargetDependersFileStreams;
 
+  ConnectionsMap PerTargetConnections;
+  ConnectionsMap TargetDependersConnections;
+
   std::string GraphName;
   std::string GraphHeader;
   std::string GraphNodePrefix;