Distinguish "strong" and "weak" target dependency edges

Utility dependencies are "strong" because they must be enforced to
generate a working build.  Link dependencies are "weak" because they can
be broken in the case of a static library cycle.

4 files changed, 42 insertions, 13 deletions

diff --git a/Source/cmComputeComponentGraph.cxx b/Source/cmComputeComponentGraph.cxx
index 165af10..5bec6a1 100644
--- a/Source/cmComputeComponentGraph.cxx
+++ b/Source/cmComputeComponentGraph.cxx
@@ -149,7 +149,10 @@ void cmComputeComponentGraph::TransferEdges()
       int j_component = this->TarjanComponents[j];
       if(i_component != j_component)
         {
-        this->ComponentGraph[i_component].push_back(j_component);
+        // We do not attempt to combine duplicate edges, but instead
+        // store the inter-component edges with suitable multiplicity.
+        this->ComponentGraph[i_component].push_back(
+          cmGraphEdge(j_component, ni->IsStrong()));
         }
       }
     }
diff --git a/Source/cmComputeLinkDepends.cxx b/Source/cmComputeLinkDepends.cxx
index 4b0214e..342c217 100644
--- a/Source/cmComputeLinkDepends.cxx
+++ b/Source/cmComputeLinkDepends.cxx
@@ -761,7 +761,8 @@ cmComputeLinkDepends::DisplayComponents()
     EdgeList const& ol = this->CCG->GetComponentGraphEdges(c);
     for(EdgeList::const_iterator oi = ol.begin(); oi != ol.end(); ++oi)
       {
-      fprintf(stderr, "  followed by Component (%d)\n", *oi);
+      int i = *oi;
+      fprintf(stderr, "  followed by Component (%d)\n", i);
       }
     fprintf(stderr, "  topo order index %d\n",
             this->ComponentOrder[c]);
diff --git a/Source/cmComputeTargetDepends.cxx b/Source/cmComputeTargetDepends.cxx
index e82606c..2b6b5ec 100644
--- a/Source/cmComputeTargetDepends.cxx
+++ b/Source/cmComputeTargetDepends.cxx
@@ -195,15 +195,13 @@ void cmComputeTargetDepends::CollectTargetDepends(int depender_index)
   // Get the depender.
   cmTarget* depender = this->Targets[depender_index];
 
-  // Keep track of dependencies already listed.
-  std::set<cmStdString> emitted;
-
-  // A target should not depend on itself.
-  emitted.insert(depender->GetName());
-
   // Loop over all targets linked directly.
+  {
   cmTarget::LinkLibraryVectorType const& tlibs =
     depender->GetOriginalLinkLibraries();
+  std::set<cmStdString> emitted;
+  // A target should not depend on itself.
+  emitted.insert(depender->GetName());
   for(cmTarget::LinkLibraryVectorType::const_iterator lib = tlibs.begin();
       lib != tlibs.end(); ++lib)
     {
@@ -213,9 +211,14 @@ void cmComputeTargetDepends::CollectTargetDepends(int depender_index)
       this->AddTargetDepend(depender_index, lib->first.c_str(), true);
       }
     }
+  }
 
   // Loop over all utility dependencies.
+  {
   std::set<cmStdString> const& tutils = depender->GetUtilities();
+  std::set<cmStdString> emitted;
+  // A target should not depend on itself.
+  emitted.insert(depender->GetName());
   for(std::set<cmStdString>::const_iterator util = tutils.begin();
       util != tutils.end(); ++util)
     {
@@ -225,6 +228,7 @@ void cmComputeTargetDepends::CollectTargetDepends(int depender_index)
       this->AddTargetDepend(depender_index, util->c_str(), false);
       }
     }
+  }
 }
 
 //----------------------------------------------------------------------------
@@ -272,7 +276,8 @@ void cmComputeTargetDepends::AddTargetDepend(int depender_index,
   int dependee_index = tii->second;
 
   // Add this entry to the dependency graph.
-  this->InitialGraph[depender_index].push_back(dependee_index);
+  this->InitialGraph[depender_index].push_back(
+    cmGraphEdge(dependee_index, !linking));
 }
 
 //----------------------------------------------------------------------------
@@ -291,8 +296,8 @@ cmComputeTargetDepends::DisplayGraph(Graph const& graph, const char* name)
       {
       int dependee_index = *ni;
       cmTarget* dependee = this->Targets[dependee_index];
-      fprintf(stderr, "  depends on target %d [%s]\n", dependee_index,
-              dependee->GetName());
+      fprintf(stderr, "  depends on target %d [%s] (%s)\n", dependee_index,
+              dependee->GetName(), ni->IsStrong()? "strong" : "weak");
       }
     }
   fprintf(stderr, "\n");
@@ -390,7 +395,8 @@ cmComputeTargetDepends
       if(cmap[j] == c)
         {
         cmTarget* dependee = this->Targets[j];
-        e << "    depends on \"" << dependee->GetName() << "\"\n";
+        e << "    depends on \"" << dependee->GetName() << "\""
+          << " (" << (ni->IsStrong()? "strong" : "weak") << ")\n";
         }
       }
     }
diff --git a/Source/cmGraphAdjacencyList.h b/Source/cmGraphAdjacencyList.h
index 41411c4..0149d33 100644
--- a/Source/cmGraphAdjacencyList.h
+++ b/Source/cmGraphAdjacencyList.h
@@ -14,7 +14,26 @@
 
 #include "cmStandardIncludes.h"
 
-struct cmGraphEdgeList: public std::vector<int> {};
+/**
+ * Graph edge representation.  Most use cases just need the
+ * destination vertex, so we support conversion to/from an int.  We
+ * also store boolean to indicate whether an edge is "strong".
+ */
+class cmGraphEdge
+{
+public:
+  cmGraphEdge(): Dest(0), Strong(true) {}
+  cmGraphEdge(int n): Dest(n), Strong(true) {}
+  cmGraphEdge(int n, bool s): Dest(n), Strong(s) {}
+  cmGraphEdge(cmGraphEdge const& r): Dest(r.Dest), Strong(r.Strong) {}
+  operator int() const { return this->Dest; }
+
+  bool IsStrong() const { return this->Strong; }
+private:
+  int Dest;
+  bool Strong;
+};
+struct cmGraphEdgeList: public std::vector<cmGraphEdge> {};
 struct cmGraphNodeList: public std::vector<int> {};
 struct cmGraphAdjacencyList: public std::vector<cmGraphEdgeList> {};