Merge topic 'imported-target-dependencies'

e01cce2 Allow add_dependencies() on imported targets (#10395)
bc7395c Merge branch 'vs-target-dependencies' into imported-target-dependencies
fd614e6 Use modern global dependency graph for VS < 8 deps
605f4bc Record edge type in global dependency graph
82596fc Merge branch 'vs8-direct-depends' into vs-target-dependencies

10 files changed, 270 insertions, 109 deletions

diff --git a/Source/cmAddDependenciesCommand.cxx b/Source/cmAddDependenciesCommand.cxx
index 1205f07..a77140d 100644
--- a/Source/cmAddDependenciesCommand.cxx
+++ b/Source/cmAddDependenciesCommand.cxx
@@ -24,11 +24,7 @@ bool cmAddDependenciesCommand
     }
 
   std::string target_name = args[0];
-
-  cmTarget* target = 
-    this->GetMakefile()->GetLocalGenerator()->
-    GetGlobalGenerator()->FindTarget(0, target_name.c_str());
-  if(target)
+  if(cmTarget* target = this->Makefile->FindTargetToUse(target_name.c_str()))
     {
     std::vector<std::string>::const_iterator s = args.begin();
     ++s; // skip over target_name
diff --git a/Source/cmAddDependenciesCommand.h b/Source/cmAddDependenciesCommand.h
index 6a981c3..fee011c 100644
--- a/Source/cmAddDependenciesCommand.h
+++ b/Source/cmAddDependenciesCommand.h
@@ -62,6 +62,8 @@ public:
       "top-level target is one created by ADD_EXECUTABLE, ADD_LIBRARY, "
       "or ADD_CUSTOM_TARGET.  Adding dependencies with this command "
       "can be used to make sure one target is built before another target.  "
+      "Dependencies added to an IMPORTED target are followed transitively "
+      "in its place since the target itself does not build.  "
       "See the DEPENDS option of ADD_CUSTOM_TARGET "
       "and ADD_CUSTOM_COMMAND for adding file-level dependencies in custom "
       "rules.  See the OBJECT_DEPENDS option in "
diff --git a/Source/cmComputeTargetDepends.cxx b/Source/cmComputeTargetDepends.cxx
index 313c680..a4ca363 100644
--- a/Source/cmComputeTargetDepends.cxx
+++ b/Source/cmComputeTargetDepends.cxx
@@ -144,7 +144,7 @@ bool cmComputeTargetDepends::Compute()
 //----------------------------------------------------------------------------
 void
 cmComputeTargetDepends::GetTargetDirectDepends(cmTarget* t,
-                                               std::set<cmTarget*>& deps)
+                                               cmTargetDependSet& deps)
 {
   // Lookup the index for this target.  All targets should be known by
   // this point.
@@ -156,7 +156,9 @@ cmComputeTargetDepends::GetTargetDirectDepends(cmTarget* t,
   EdgeList const& nl = this->FinalGraph[i];
   for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
     {
-    deps.insert(this->Targets[*ni]);
+    cmTarget* dep = this->Targets[*ni];
+    cmTargetDependSet::iterator di = deps.insert(dep).first;
+    di->SetType(ni->IsStrong());
     }
 }
 
@@ -244,13 +246,7 @@ void cmComputeTargetDepends::AddTargetDepend(int depender_index,
 
   // Check the target's makefile first.
   cmTarget* dependee =
-    depender->GetMakefile()->FindTarget(dependee_name);
-
-  // Then search globally.
-  if(!dependee)
-    {
-    dependee = this->GlobalGenerator->FindTarget(0, dependee_name);
-    }
+    depender->GetMakefile()->FindTargetToUse(dependee_name);
 
   // Skip targets that will not really be linked.  This is probably a
   // name conflict between an external library and an executable
@@ -262,25 +258,42 @@ void cmComputeTargetDepends::AddTargetDepend(int depender_index,
     dependee = 0;
     }
 
-  // If not found then skip then the dependee.
-  if(!dependee)
+  if(dependee)
     {
-    return;
+    this->AddTargetDepend(depender_index, dependee, linking);
     }
+}
 
-  // No imported targets should have been found.
-  assert(!dependee->IsImported());
-
-  // Lookup the index for this target.  All targets should be known by
-  // this point.
-  std::map<cmTarget*, int>::const_iterator tii =
-    this->TargetIndex.find(dependee);
-  assert(tii != this->TargetIndex.end());
-  int dependee_index = tii->second;
-
-  // Add this entry to the dependency graph.
-  this->InitialGraph[depender_index].push_back(
-    cmGraphEdge(dependee_index, !linking));
+//----------------------------------------------------------------------------
+void cmComputeTargetDepends::AddTargetDepend(int depender_index,
+                                             cmTarget* dependee,
+                                             bool linking)
+{
+  if(dependee->IsImported())
+    {
+    // Skip imported targets but follow their utility dependencies.
+    std::set<cmStdString> const& utils = dependee->GetUtilities();
+    for(std::set<cmStdString>::const_iterator i = utils.begin();
+        i != utils.end(); ++i)
+      {
+      cmTarget* transitive_dependee =
+        dependee->GetMakefile()->FindTargetToUse(i->c_str());
+      this->AddTargetDepend(depender_index, transitive_dependee, false);
+      }
+    }
+  else
+    {
+    // Lookup the index for this target.  All targets should be known by
+    // this point.
+    std::map<cmTarget*, int>::const_iterator tii =
+      this->TargetIndex.find(dependee);
+    assert(tii != this->TargetIndex.end());
+    int dependee_index = tii->second;
+
+    // Add this entry to the dependency graph.
+    this->InitialGraph[depender_index].push_back(
+      cmGraphEdge(dependee_index, !linking));
+    }
 }
 
 //----------------------------------------------------------------------------
@@ -445,7 +458,7 @@ cmComputeTargetDepends
       int j = *ei;
       if(cmap[j] == c && ei->IsStrong())
         {
-        this->FinalGraph[i].push_back(j);
+        this->FinalGraph[i].push_back(cmGraphEdge(j, true));
         if(!this->IntraComponent(cmap, c, j, head, emitted, visited))
           {
           return false;
@@ -456,7 +469,7 @@ cmComputeTargetDepends
     // Prepend to a linear linked-list of intra-component edges.
     if(*head >= 0)
       {
-      this->FinalGraph[i].push_back(*head);
+      this->FinalGraph[i].push_back(cmGraphEdge(*head, false));
       }
     else
       {
@@ -515,7 +528,7 @@ cmComputeTargetDepends
       int dependee_component = *ni;
       int dependee_component_head = this->ComponentHead[dependee_component];
       this->FinalGraph[depender_component_tail]
-        .push_back(dependee_component_head);
+        .push_back(cmGraphEdge(dependee_component_head, ni->IsStrong()));
       }
     }
   return true;
diff --git a/Source/cmComputeTargetDepends.h b/Source/cmComputeTargetDepends.h
index 240de76..67bce72 100644
--- a/Source/cmComputeTargetDepends.h
+++ b/Source/cmComputeTargetDepends.h
@@ -21,6 +21,7 @@
 class cmComputeComponentGraph;
 class cmGlobalGenerator;
 class cmTarget;
+class cmTargetDependSet;
 
 /** \class cmComputeTargetDepends
  * \brief Compute global interdependencies among targets.
@@ -38,13 +39,14 @@ public:
   bool Compute();
 
   std::vector<cmTarget*> const& GetTargets() const { return this->Targets; }
-  void GetTargetDirectDepends(cmTarget* t, std::set<cmTarget*>& deps);
+  void GetTargetDirectDepends(cmTarget* t, cmTargetDependSet& deps);
 private:
   void CollectTargets();
   void CollectDepends();
   void CollectTargetDepends(int depender_index);
   void AddTargetDepend(int depender_index, const char* dependee_name,
                        bool linking);
+  void AddTargetDepend(int depender_index, cmTarget* dependee, bool linking);
   bool ComputeFinalDepends(cmComputeComponentGraph const& ccg);
 
   cmGlobalGenerator* GlobalGenerator;
diff --git a/Source/cmGlobalGenerator.h b/Source/cmGlobalGenerator.h
index e68ed08..7e43124 100644
--- a/Source/cmGlobalGenerator.h
+++ b/Source/cmGlobalGenerator.h
@@ -16,6 +16,7 @@
 #include "cmStandardIncludes.h"
 
 #include "cmTarget.h" // For cmTargets
+#include "cmTargetDepend.h" // For cmTargetDependSet
 
 class cmake;
 class cmMakefile;
@@ -233,7 +234,7 @@ public:
   virtual const char* GetCleanTargetName()        { return 0; }
 
   // Class to track a set of dependencies.
-  class TargetDependSet: public std::set<cmTarget*> {};
+  typedef cmTargetDependSet TargetDependSet;
 
   // what targets does the specified target depend on directly
   // via a target_link_libraries or add_dependencies
diff --git a/Source/cmGlobalVisualStudioGenerator.cxx b/Source/cmGlobalVisualStudioGenerator.cxx
index bae18a3..7696e6c 100644
--- a/Source/cmGlobalVisualStudioGenerator.cxx
+++ b/Source/cmGlobalVisualStudioGenerator.cxx
@@ -237,6 +237,59 @@ std::string cmGlobalVisualStudioGenerator::GetUserMacrosRegKeyBase()
 }
 
 //----------------------------------------------------------------------------
+void cmGlobalVisualStudioGenerator::FillLinkClosure(cmTarget* target,
+                                                    TargetSet& linked)
+{
+  if(linked.insert(target).second)
+    {
+    TargetDependSet const& depends = this->GetTargetDirectDepends(*target);
+    for(TargetDependSet::const_iterator di = depends.begin();
+        di != depends.end(); ++di)
+      {
+      if(di->IsLink())
+        {
+        this->FillLinkClosure(*di, linked);
+        }
+      }
+    }
+}
+
+//----------------------------------------------------------------------------
+cmGlobalVisualStudioGenerator::TargetSet const&
+cmGlobalVisualStudioGenerator::GetTargetLinkClosure(cmTarget* target)
+{
+  TargetSetMap::iterator i = this->TargetLinkClosure.find(target);
+  if(i == this->TargetLinkClosure.end())
+    {
+    TargetSetMap::value_type entry(target, TargetSet());
+    i = this->TargetLinkClosure.insert(entry).first;
+    this->FillLinkClosure(target, i->second);
+    }
+  return i->second;
+}
+
+//----------------------------------------------------------------------------
+void cmGlobalVisualStudioGenerator::FollowLinkDepends(
+  cmTarget* target, std::set<cmTarget*>& linked)
+{
+  if(linked.insert(target).second &&
+     target->GetType() == cmTarget::STATIC_LIBRARY)
+    {
+    // Static library targets do not list their link dependencies so
+    // we must follow them transitively now.
+    TargetDependSet const& depends = this->GetTargetDirectDepends(*target);
+    for(TargetDependSet::const_iterator di = depends.begin();
+        di != depends.end(); ++di)
+      {
+      if(di->IsLink())
+        {
+        this->FollowLinkDepends(*di, linked);
+        }
+      }
+    }
+}
+
+//----------------------------------------------------------------------------
 bool cmGlobalVisualStudioGenerator::ComputeTargetDepends()
 {
   if(!this->cmGlobalGenerator::ComputeTargetDepends())
@@ -269,51 +322,94 @@ void cmGlobalVisualStudioGenerator::ComputeVSTargetDepends(cmTarget& target)
     return;
     }
   VSDependSet& vsTargetDepend = this->VSTargetDepends[&target];
+  // VS <= 7.1 has two behaviors that affect solution dependencies.
+  //
+  // (1) Solution-level dependencies between a linkable target and a
+  // library cause that library to be linked.  We use an intermedite
+  // empty utility target to express the dependency.  (VS 8 and above
+  // provide a project file "LinkLibraryDependencies" setting to
+  // choose whether to activate this behavior.  We disable it except
+  // when linking external project files.)
+  //
+  // (2) We cannot let static libraries depend directly on targets to
+  // which they "link" because the librarian tool will copy the
+  // targets into the static library.  While the work-around for
+  // behavior (1) would also avoid this, it would create a large
+  // number of extra utility targets for little gain.  Instead, use
+  // the above work-around only for dependencies explicitly added by
+  // the add_dependencies() command.  Approximate link dependencies by
+  // leaving them out for the static library itself but following them
+  // transitively for other targets.
+
+  bool allowLinkable = (target.GetType() != cmTarget::STATIC_LIBRARY &&
+                        target.GetType() != cmTarget::SHARED_LIBRARY &&
+                        target.GetType() != cmTarget::MODULE_LIBRARY &&
+                        target.GetType() != cmTarget::EXECUTABLE);
+
+  TargetDependSet const& depends = this->GetTargetDirectDepends(target);
+
+  // Collect implicit link dependencies (target_link_libraries).
+  // Static libraries cannot depend on their link implementation
+  // due to behavior (2), but they do not really need to.
+  std::set<cmTarget*> linkDepends;
   if(target.GetType() != cmTarget::STATIC_LIBRARY)
     {
-    cmTarget::LinkLibraryVectorType const& libs = target.GetLinkLibraries();
-    for(cmTarget::LinkLibraryVectorType::const_iterator j = libs.begin();
-        j != libs.end(); ++j)
+    for(TargetDependSet::const_iterator di = depends.begin();
+        di != depends.end(); ++di)
       {
-      if(j->first != target.GetName() &&
-         this->FindTarget(0, j->first.c_str()))
+      cmTargetDepend dep = *di;
+      if(dep.IsLink())
         {
-        vsTargetDepend.insert(j->first);
+        this->FollowLinkDepends(dep, linkDepends);
         }
       }
     }
-  std::set<cmStdString> const& utils = target.GetUtilities();
-  for(std::set<cmStdString>::const_iterator i = utils.begin();
-      i != utils.end(); ++i)
+
+  // Collext explicit util dependencies (add_dependencies).
+  std::set<cmTarget*> utilDepends;
+  for(TargetDependSet::const_iterator di = depends.begin();
+      di != depends.end(); ++di)
     {
-    if(*i != target.GetName())
+    cmTargetDepend dep = *di;
+    if(dep.IsUtil())
       {
-      std::string name = this->GetUtilityForTarget(target, i->c_str());
-      vsTargetDepend.insert(name);
+      this->FollowLinkDepends(dep, utilDepends);
       }
     }
-}
 
-//----------------------------------------------------------------------------
-bool cmGlobalVisualStudioGenerator::CheckTargetLinks(cmTarget& target,
-                                                     const char* name)
-{
-  // Return whether the given target links to a target with the given name.
-  if(target.GetType() == cmTarget::STATIC_LIBRARY)
+  // Collect all targets linked by this target so we can avoid
+  // intermediate targets below.
+  TargetSet linked;
+  if(target.GetType() != cmTarget::STATIC_LIBRARY)
     {
-    // Static libraries never link to anything.
-    return false;
+    linked = this->GetTargetLinkClosure(&target);
     }
-  cmTarget::LinkLibraryVectorType const& libs = target.GetLinkLibraries();
-  for(cmTarget::LinkLibraryVectorType::const_iterator i = libs.begin();
-      i != libs.end(); ++i)
+
+  // Emit link dependencies.
+  for(std::set<cmTarget*>::iterator di = linkDepends.begin();
+      di != linkDepends.end(); ++di)
+    {
+    cmTarget* dep = *di;
+    vsTargetDepend.insert(dep->GetName());
+    }
+
+  // Emit util dependencies.  Possibly use intermediate targets.
+  for(std::set<cmTarget*>::iterator di = utilDepends.begin();
+      di != utilDepends.end(); ++di)
     {
-    if(i->first == name)
+    cmTarget* dep = *di;
+    if(allowLinkable || !dep->IsLinkable() || linked.count(dep))
       {
-      return true;
+      // Direct dependency allowed.
+      vsTargetDepend.insert(dep->GetName());
+      }
+    else
+      {
+      // Direct dependency on linkable target not allowed.
+      // Use an intermediate utility target.
+      vsTargetDepend.insert(this->GetUtilityDepend(dep));
       }
     }
-  return false;
 }
 
 //----------------------------------------------------------------------------
@@ -330,45 +426,6 @@ std::string cmGlobalVisualStudioGenerator::GetUtilityDepend(cmTarget* target)
 }
 
 //----------------------------------------------------------------------------
-std::string
-cmGlobalVisualStudioGenerator::GetUtilityForTarget(cmTarget& target,
-                                                   const char* name)
-{
-  if(!this->VSLinksDependencies())
-    {
-    return name;
-    }
-
-  // Possibly depend on an intermediate utility target to avoid
-  // linking.
-  if(target.GetType() == cmTarget::STATIC_LIBRARY ||
-     target.GetType() == cmTarget::SHARED_LIBRARY ||
-     target.GetType() == cmTarget::MODULE_LIBRARY ||
-     target.GetType() == cmTarget::EXECUTABLE)
-    {
-    // The depender is a target that links.
-    if(cmTarget* depTarget = this->FindTarget(0, name))
-      {
-      if(depTarget->GetType() == cmTarget::STATIC_LIBRARY ||
-         depTarget->GetType() == cmTarget::SHARED_LIBRARY ||
-         depTarget->GetType() == cmTarget::MODULE_LIBRARY)
-        {
-        // This utility dependency will cause an attempt to link.  If
-        // the depender does not already link the dependee we need an
-        // intermediate target.
-        if(!this->CheckTargetLinks(target, name))
-          {
-          return this->GetUtilityDepend(depTarget);
-          }
-        }
-      }
-    }
-
-  // No special case.  Just use the original dependency name.
-  return name;
-}
-
-//----------------------------------------------------------------------------
 #include <windows.h>
 
 //----------------------------------------------------------------------------
@@ -706,11 +763,22 @@ cmGlobalVisualStudioGenerator::TargetCompare
 
 //----------------------------------------------------------------------------
 cmGlobalVisualStudioGenerator::OrderedTargetDependSet
-::OrderedTargetDependSet(cmGlobalGenerator::TargetDependSet const& targets)
+::OrderedTargetDependSet(TargetDependSet const& targets)
 {
-  for(cmGlobalGenerator::TargetDependSet::const_iterator ti =
+  for(TargetDependSet::const_iterator ti =
         targets.begin(); ti != targets.end(); ++ti)
     {
     this->insert(*ti);
     }
 }
+
+//----------------------------------------------------------------------------
+cmGlobalVisualStudioGenerator::OrderedTargetDependSet
+::OrderedTargetDependSet(TargetSet const& targets)
+{
+  for(TargetSet::const_iterator ti = targets.begin();
+      ti != targets.end(); ++ti)
+    {
+    this->insert(*ti);
+    }
+}
diff --git a/Source/cmGlobalVisualStudioGenerator.h b/Source/cmGlobalVisualStudioGenerator.h
index c8ea339..bc96f4e 100644
--- a/Source/cmGlobalVisualStudioGenerator.h
+++ b/Source/cmGlobalVisualStudioGenerator.h
@@ -69,15 +69,12 @@ public:
       i.e. "Can I build Debug and Release in the same tree?" */
   virtual bool IsMultiConfig() { return true; }
 
+  class TargetSet: public std::set<cmTarget*> {};
   struct TargetCompare
   {
     bool operator()(cmTarget const* l, cmTarget const* r) const;
   };
-  class OrderedTargetDependSet: public std::multiset<cmTarget*, TargetCompare>
-  {
-  public:
-    OrderedTargetDependSet(cmGlobalGenerator::TargetDependSet const&);
-  };
+  class OrderedTargetDependSet;
 
 protected:
   // Does this VS version link targets to each other if there are
@@ -99,6 +96,24 @@ protected:
   std::string GetUtilityDepend(cmTarget* target);
   typedef std::map<cmTarget*, cmStdString> UtilityDependsMap;
   UtilityDependsMap UtilityDepends;
+private:
+  void FollowLinkDepends(cmTarget* target, std::set<cmTarget*>& linked);
+
+  class TargetSetMap: public std::map<cmTarget*, TargetSet> {};
+  TargetSetMap TargetLinkClosure;
+  void FillLinkClosure(cmTarget* target, TargetSet& linked);
+  TargetSet const& GetTargetLinkClosure(cmTarget* target);
+};
+
+class cmGlobalVisualStudioGenerator::OrderedTargetDependSet:
+  public std::multiset<cmTargetDepend,
+                       cmGlobalVisualStudioGenerator::TargetCompare>
+{
+public:
+  typedef cmGlobalGenerator::TargetDependSet TargetDependSet;
+  typedef cmGlobalVisualStudioGenerator::TargetSet TargetSet;
+  OrderedTargetDependSet(TargetDependSet const&);
+  OrderedTargetDependSet(TargetSet const&);
 };
 
 #endif
diff --git a/Source/cmTargetDepend.h b/Source/cmTargetDepend.h
new file mode 100644
index 0000000..258bacd
--- /dev/null
+++ b/Source/cmTargetDepend.h
@@ -0,0 +1,48 @@
+/*============================================================================
+  CMake - Cross Platform Makefile Generator
+  Copyright 2000-2010 Kitware, Inc., Insight Software Consortium
+
+  Distributed under the OSI-approved BSD License (the "License");
+  see accompanying file Copyright.txt for details.
+
+  This software is distributed WITHOUT ANY WARRANTY; without even the
+  implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+  See the License for more information.
+============================================================================*/
+#ifndef cmTargetDepend_h
+#define cmTargetDepend_h
+
+#include "cmStandardIncludes.h"
+
+class cmTarget;
+
+/** One edge in the global target dependency graph.
+    It may be marked as a 'link' or 'util' edge or both.  */
+class cmTargetDepend
+{
+  cmTarget* Target;
+
+  // The set order depends only on the Target, so we use
+  // mutable members to acheive a map with set syntax.
+  mutable bool Link;
+  mutable bool Util;
+public:
+  cmTargetDepend(cmTarget* t): Target(t), Link(false), Util(false) {}
+  operator cmTarget*() const { return this->Target; }
+  cmTarget* operator->() const { return this->Target; }
+  cmTarget& operator*() const { return *this->Target; }
+  friend bool operator < (cmTargetDepend const& l, cmTargetDepend const& r)
+    { return l.Target < r.Target; }
+  void SetType(bool strong) const
+    {
+    if(strong) { this->Util = true; }
+    else { this->Link = true; }
+    }
+  bool IsLink() const { return this->Link; }
+  bool IsUtil() const { return this->Util; }
+};
+
+/** Unordered set of (direct) dependencies of a target. */
+class cmTargetDependSet: public std::set<cmTargetDepend> {};
+
+#endif
diff --git a/Tests/ExportImport/Import/A/CMakeLists.txt b/Tests/ExportImport/Import/A/CMakeLists.txt
index 34b8717..0828343 100644
--- a/Tests/ExportImport/Import/A/CMakeLists.txt
+++ b/Tests/ExportImport/Import/A/CMakeLists.txt
@@ -75,6 +75,22 @@ foreach(c DEBUG RELWITHDEBINFO)
   set_property(TARGET imp_testExe1b PROPERTY COMPILE_DEFINITIONS_${c} EXE_DBG)
 endforeach(c)
 
+# Create a custom target to generate a header for the libraries below.
+include_directories(${CMAKE_CURRENT_BINARY_DIR})
+add_custom_command(
+  OUTPUT testLib2.h
+  VERBATIM COMMAND
+  ${CMAKE_COMMAND} -E echo "extern int testLib2(void);" > testLib2.h
+  )
+add_custom_target(hdr_testLib2 DEPENDS testLib2.h)
+
+# Drive the header generation through an indirect chain of imported
+# target dependencies.
+add_library(dep_testLib2 UNKNOWN IMPORTED)
+add_dependencies(dep_testLib2 hdr_testLib2)
+add_dependencies(bld_testLib2 dep_testLib2)
+add_dependencies(exp_testLib2 dep_testLib2)
+
 # Create a library to be linked by another directory in this project
 # to test transitive linking to otherwise invisible imported targets.
 add_library(imp_lib1 STATIC imp_lib1.c)
diff --git a/Tests/ExportImport/Import/A/imp_lib1.c b/Tests/ExportImport/Import/A/imp_lib1.c
index d8c66e6..5b3215e 100644
--- a/Tests/ExportImport/Import/A/imp_lib1.c
+++ b/Tests/ExportImport/Import/A/imp_lib1.c
@@ -1,4 +1,4 @@
-extern int testLib2(void);
+#include "testLib2.h"
 
 int imp_lib1(void)
 {