Track backtraces in target dependencies internally

Carry backtraces on target dependency edges to refer to the line in
project code that caused the edge to appear.

6 files changed, 50 insertions, 19 deletions

diff --git a/Source/cmComputeComponentGraph.cxx b/Source/cmComputeComponentGraph.cxx
index a7dc1ca..5820df6 100644
--- a/Source/cmComputeComponentGraph.cxx
+++ b/Source/cmComputeComponentGraph.cxx
@@ -125,8 +125,8 @@ void cmComputeComponentGraph::TransferEdges()
       if (i_component != j_component) {
         // We do not attempt to combine duplicate edges, but instead
         // store the inter-component edges with suitable multiplicity.
-        this->ComponentGraph[i_component].emplace_back(j_component,
-                                                       ni.IsStrong());
+        this->ComponentGraph[i_component].emplace_back(
+          j_component, ni.IsStrong(), ni.GetBacktrace());
       }
     }
   }
diff --git a/Source/cmComputeLinkDepends.cxx b/Source/cmComputeLinkDepends.cxx
index e3d53e4..4717cf6 100644
--- a/Source/cmComputeLinkDepends.cxx
+++ b/Source/cmComputeLinkDepends.cxx
@@ -420,7 +420,8 @@ void cmComputeLinkDepends::HandleSharedDependency(SharedDepEntry const& dep)
 
   // This shared library dependency must follow the item that listed
   // it.
-  this->EntryConstraintGraph[dep.DependerIndex].push_back(index);
+  this->EntryConstraintGraph[dep.DependerIndex].emplace_back(
+    index, true, cmListFileBacktrace());
 
   // Target items may have their own dependencies.
   if (entry.Target) {
@@ -523,7 +524,8 @@ void cmComputeLinkDepends::AddLinkEntries(int depender_index,
 
     // The dependee must come after the depender.
     if (depender_index >= 0) {
-      this->EntryConstraintGraph[depender_index].push_back(dependee_index);
+      this->EntryConstraintGraph[depender_index].emplace_back(
+        dependee_index, false, cmListFileBacktrace());
     } else {
       // This is a direct dependency of the target being linked.
       this->OriginalEntries.push_back(dependee_index);
@@ -595,7 +597,10 @@ void cmComputeLinkDepends::InferDependencies()
 
     // Add the inferred dependencies to the graph.
     cmGraphEdgeList& edges = this->EntryConstraintGraph[depender_index];
-    edges.insert(edges.end(), common.begin(), common.end());
+    edges.reserve(edges.size() + common.size());
+    for (auto const& c : common) {
+      edges.emplace_back(c, true, cmListFileBacktrace());
+    }
   }
 }
 
diff --git a/Source/cmComputeTargetDepends.cxx b/Source/cmComputeTargetDepends.cxx
index 28e1251..f8ac333 100644
--- a/Source/cmComputeTargetDepends.cxx
+++ b/Source/cmComputeTargetDepends.cxx
@@ -151,6 +151,7 @@ void cmComputeTargetDepends::GetTargetDirectDepends(cmGeneratorTarget const* t,
     cmGeneratorTarget const* dep = this->Targets[ni];
     cmTargetDependSet::iterator di = deps.insert(dep).first;
     di->SetType(ni.IsStrong());
+    di->SetBacktrace(ni.GetBacktrace());
   }
 }
 
@@ -258,7 +259,8 @@ void cmComputeTargetDepends::CollectTargetDepends(int depender_index)
 
 void cmComputeTargetDepends::AddInterfaceDepends(
   int depender_index, const cmGeneratorTarget* dependee,
-  const std::string& config, std::set<cmLinkItem>& emitted)
+  cmListFileBacktrace const& dependee_backtrace, const std::string& config,
+  std::set<cmLinkItem>& emitted)
 {
   cmGeneratorTarget const* depender = this->Targets[depender_index];
   if (cmLinkInterface const* iface =
@@ -266,8 +268,13 @@ void cmComputeTargetDepends::AddInterfaceDepends(
     for (cmLinkItem const& lib : iface->Libraries) {
       // Don't emit the same library twice for this target.
       if (emitted.insert(lib).second) {
-        this->AddTargetDepend(depender_index, lib, true);
-        this->AddInterfaceDepends(depender_index, lib, config, emitted);
+        // Inject the backtrace of the original link dependency whose
+        // link interface we are adding.  This indicates the line of
+        // code in the project that caused this dependency to be added.
+        cmLinkItem libBT = lib;
+        libBT.Backtrace = dependee_backtrace;
+        this->AddTargetDepend(depender_index, libBT, true);
+        this->AddInterfaceDepends(depender_index, libBT, config, emitted);
       }
     }
   }
@@ -290,7 +297,8 @@ void cmComputeTargetDepends::AddInterfaceDepends(
   if (dependee) {
     // A target should not depend on itself.
     emitted.insert(cmLinkItem(depender, cmListFileBacktrace()));
-    this->AddInterfaceDepends(depender_index, dependee, config, emitted);
+    this->AddInterfaceDepends(depender_index, dependee,
+                              dependee_name.Backtrace, config, emitted);
   }
 }
 
@@ -340,13 +348,14 @@ void cmComputeTargetDepends::AddTargetDepend(int depender_index,
   }
 
   if (dependee) {
-    this->AddTargetDepend(depender_index, dependee, linking);
+    this->AddTargetDepend(depender_index, dependee, dependee_name.Backtrace,
+                          linking);
   }
 }
 
-void cmComputeTargetDepends::AddTargetDepend(int depender_index,
-                                             const cmGeneratorTarget* dependee,
-                                             bool linking)
+void cmComputeTargetDepends::AddTargetDepend(
+  int depender_index, cmGeneratorTarget const* dependee,
+  cmListFileBacktrace const& dependee_backtrace, bool linking)
 {
   if (dependee->IsImported() ||
       dependee->GetType() == cmStateEnums::INTERFACE_LIBRARY) {
@@ -355,7 +364,8 @@ void cmComputeTargetDepends::AddTargetDepend(int depender_index,
     std::set<cmLinkItem> const& utils = dependee->GetUtilityItems();
     for (cmLinkItem const& i : utils) {
       if (cmGeneratorTarget const* transitive_dependee = i.Target) {
-        this->AddTargetDepend(depender_index, transitive_dependee, false);
+        this->AddTargetDepend(depender_index, transitive_dependee, i.Backtrace,
+                              false);
       }
     }
   } else {
@@ -367,7 +377,8 @@ void cmComputeTargetDepends::AddTargetDepend(int depender_index,
     int dependee_index = tii->second;
 
     // Add this entry to the dependency graph.
-    this->InitialGraph[depender_index].emplace_back(dependee_index, !linking);
+    this->InitialGraph[depender_index].emplace_back(dependee_index, !linking,
+                                                    dependee_backtrace);
   }
 }
 
@@ -501,7 +512,7 @@ bool cmComputeTargetDepends::IntraComponent(std::vector<int> const& cmap,
     for (cmGraphEdge const& edge : el) {
       int j = edge;
       if (cmap[j] == c && edge.IsStrong()) {
-        this->FinalGraph[i].emplace_back(j, true);
+        this->FinalGraph[i].emplace_back(j, true, edge.GetBacktrace());
         if (!this->IntraComponent(cmap, c, j, head, emitted, visited)) {
           return false;
         }
@@ -510,7 +521,7 @@ bool cmComputeTargetDepends::IntraComponent(std::vector<int> const& cmap,
 
     // Prepend to a linear linked-list of intra-component edges.
     if (*head >= 0) {
-      this->FinalGraph[i].emplace_back(*head, false);
+      this->FinalGraph[i].emplace_back(*head, false, cmListFileBacktrace());
     } else {
       this->ComponentTail[c] = i;
     }
@@ -561,7 +572,7 @@ bool cmComputeTargetDepends::ComputeFinalDepends(
       int dependee_component = ni;
       int dependee_component_head = this->ComponentHead[dependee_component];
       this->FinalGraph[depender_component_tail].emplace_back(
-        dependee_component_head, ni.IsStrong());
+        dependee_component_head, ni.IsStrong(), ni.GetBacktrace());
     }
   }
   return true;
diff --git a/Source/cmComputeTargetDepends.h b/Source/cmComputeTargetDepends.h
index 3046e8a..3840bd7 100644
--- a/Source/cmComputeTargetDepends.h
+++ b/Source/cmComputeTargetDepends.h
@@ -6,6 +6,7 @@
 #include "cmConfigure.h" // IWYU pragma: keep
 
 #include "cmGraphAdjacencyList.h"
+#include "cmListFileCache.h"
 
 #include <map>
 #include <set>
@@ -47,6 +48,7 @@ private:
   void AddTargetDepend(int depender_index, cmLinkItem const& dependee_name,
                        bool linking);
   void AddTargetDepend(int depender_index, cmGeneratorTarget const* dependee,
+                       cmListFileBacktrace const& dependee_backtrace,
                        bool linking);
   bool ComputeFinalDepends(cmComputeComponentGraph const& ccg);
   void AddInterfaceDepends(int depender_index, cmLinkItem const& dependee_name,
@@ -54,6 +56,7 @@ private:
                            std::set<cmLinkItem>& emitted);
   void AddInterfaceDepends(int depender_index,
                            cmGeneratorTarget const* dependee,
+                           cmListFileBacktrace const& dependee_backtrace,
                            const std::string& config,
                            std::set<cmLinkItem>& emitted);
   cmGlobalGenerator* GlobalGenerator;
diff --git a/Source/cmGraphAdjacencyList.h b/Source/cmGraphAdjacencyList.h
index 6a0a799..fb2eee2 100644
--- a/Source/cmGraphAdjacencyList.h
+++ b/Source/cmGraphAdjacencyList.h
@@ -5,6 +5,8 @@
 
 #include "cmConfigure.h" // IWYU pragma: keep
 
+#include "cmListFileCache.h"
+
 #include <vector>
 
 /**
@@ -15,18 +17,22 @@
 class cmGraphEdge
 {
 public:
-  cmGraphEdge(int n = 0, bool s = true)
+  cmGraphEdge(int n, bool s, cmListFileBacktrace const& bt)
     : Dest(n)
     , Strong(s)
+    , Backtrace(bt)
   {
   }
   operator int() const { return this->Dest; }
 
   bool IsStrong() const { return this->Strong; }
 
+  cmListFileBacktrace const& GetBacktrace() const { return this->Backtrace; }
+
 private:
   int Dest;
   bool Strong;
+  cmListFileBacktrace Backtrace;
 };
 struct cmGraphEdgeList : public std::vector<cmGraphEdge>
 {
diff --git a/Source/cmTargetDepend.h b/Source/cmTargetDepend.h
index b698db6..5ea0085 100644
--- a/Source/cmTargetDepend.h
+++ b/Source/cmTargetDepend.h
@@ -19,6 +19,7 @@ class cmTargetDepend
   // mutable members to achieve a map with set syntax.
   mutable bool Link;
   mutable bool Util;
+  mutable cmListFileBacktrace Backtrace;
 
 public:
   cmTargetDepend(cmGeneratorTarget const* t)
@@ -42,8 +43,13 @@ public:
       this->Link = true;
     }
   }
+  void SetBacktrace(cmListFileBacktrace const& bt) const
+  {
+    this->Backtrace = bt;
+  }
   bool IsLink() const { return this->Link; }
   bool IsUtil() const { return this->Util; }
+  cmListFileBacktrace const& GetBacktrace() const { return this->Backtrace; }
 };
 
 /** Unordered set of (direct) dependencies of a target. */