ENH: Moved global inter-target dependency analysis and cycle-prevention code up from cmGlobalUnixMakefileGenerator3 to cmGlobalGenerator. Simplified cmGlobalUnixMakefileGenerator3 to use it. Later other generators may be modified to use it also.

7 files changed, 157 insertions, 222 deletions

diff --git a/Source/cmGlobalGenerator.cxx b/Source/cmGlobalGenerator.cxx
index a0eb31a..708bb86 100644
--- a/Source/cmGlobalGenerator.cxx
+++ b/Source/cmGlobalGenerator.cxx
@@ -725,10 +725,6 @@ void cmGlobalGenerator::Configure()
   // so create the map from project name to vector of local generators
   this->FillProjectMap();
 
-  // Create a map from local generator to the complete set of targets
-  // it builds by default.
-  this->FillLocalGeneratorToTargetMap();
-
   if ( !this->CMakeInstance->GetScriptMode() )
     {
     this->CMakeInstance->UpdateProgress("Configuring done", -1);
@@ -791,6 +787,10 @@ void cmGlobalGenerator::Generate()
     this->LocalGenerators[i]->GenerateTargetManifest(this->TargetManifest);
     }
 
+  // Create a map from local generator to the complete set of targets
+  // it builds by default.
+  this->FillLocalGeneratorToTargetMap();
+
   // Generate project files
   for (i = 0; i < this->LocalGenerators.size(); ++i)
     {
@@ -1264,6 +1264,7 @@ void cmGlobalGenerator::FillProjectMap()
 // generator directory level.
 void cmGlobalGenerator::FillLocalGeneratorToTargetMap()
 {
+  this->LocalGeneratorToTargetMap.clear();
   // Loop over all targets in all local generators.
   for(std::vector<cmLocalGenerator*>::const_iterator
         lgi = this->LocalGenerators.begin();
@@ -1282,14 +1283,14 @@ void cmGlobalGenerator::FillLocalGeneratorToTargetMap()
           clg = clg->GetParent())
         {
         // This local generator includes the target.
-        std::set<cmTarget*>& targetSet =
+        std::set<cmTarget const*>& targetSet =
           this->LocalGeneratorToTargetMap[clg];
         targetSet.insert(&target);
 
         // Add dependencies of the included target.  An excluded
         // target may still be included if it is a dependency of a
         // non-excluded target.
-        std::vector<cmTarget *>& tgtdeps = this->GetTargetDepends(target);
+        TargetDependSet const& tgtdeps = this->GetTargetDepends(target);
         targetSet.insert(tgtdeps.begin(), tgtdeps.end());
         }
       }
@@ -1681,79 +1682,147 @@ void cmGlobalGenerator::AppendDirectoryForConfig(const char*, const char*,
 }
 
 //----------------------------------------------------------------------------
-std::vector<cmTarget *>& cmGlobalGenerator
-::GetTargetDepends(cmTarget& target)
+cmGlobalGenerator::TargetDependSet const&
+cmGlobalGenerator::GetTargetDepends(cmTarget const& target)
 {
+  // Clarify the role of the input target.
+  cmTarget const* depender = &target;
+
   // if the depends are already in the map then return
-  std::map<cmStdString, std::vector<cmTarget *> >::iterator tgtI =
-    this->TargetDependencies.find(target.GetName());
-  if (tgtI != this->TargetDependencies.end())
+  TargetDependMap::const_iterator tgtI =
+    this->TargetDependencies.find(depender);
+  if(tgtI != this->TargetDependencies.end())
     {
     return tgtI->second;
     }
 
-  // A target should not depend on itself.
+  // Create an entry for this depender.
+  TargetDependSet& depender_depends = this->TargetDependencies[depender];
+
+  // Keep track of dependencies already listed.
   std::set<cmStdString> emitted;
-  emitted.insert(target.GetName());
 
-  // the vector of results
-  std::vector<cmTarget *>& result =
-    this->TargetDependencies[target.GetName()];
+  // A target should not depend on itself.
+  emitted.insert(depender->GetName());
 
-  // Loop over all library dependencies but not for static libs
-  if (target.GetType() != cmTarget::STATIC_LIBRARY)
+  // Loop over all targets linked directly.
+  cmTarget::LinkLibraryVectorType const& tlibs =
+    target.GetOriginalLinkLibraries();
+  for(cmTarget::LinkLibraryVectorType::const_iterator lib = tlibs.begin();
+      lib != tlibs.end(); ++lib)
     {
-    const cmTarget::LinkLibraryVectorType& tlibs = target.GetLinkLibraries();
-    for(cmTarget::LinkLibraryVectorType::const_iterator lib = tlibs.begin();
-        lib != tlibs.end(); ++lib)
+    // Don't emit the same library twice for this target.
+    if(emitted.insert(lib->first).second)
       {
-      // Don't emit the same library twice for this target.
-      if(emitted.insert(lib->first).second)
-        {
-        cmTarget *target2 =
-          target.GetMakefile()->FindTarget(lib->first.c_str(), false);
-
-        // search each local generator until a match is found
-        if (!target2)
-          {
-          target2 = this->FindTarget(0,lib->first.c_str(), false);
-          }
-
-        // if a match was found then ...
-        if (target2)
-          {
-          // Add this dependency.
-          result.push_back(target2);
-          }
-        }
+      this->ConsiderTargetDepends(depender, depender_depends,
+                                  lib->first.c_str());
       }
     }
 
   // Loop over all utility dependencies.
-  const std::set<cmStdString>& tutils = target.GetUtilities();
+  std::set<cmStdString> const& tutils = target.GetUtilities();
   for(std::set<cmStdString>::const_iterator util = tutils.begin();
       util != tutils.end(); ++util)
     {
     // Don't emit the same utility twice for this target.
     if(emitted.insert(*util).second)
       {
-      cmTarget *target2=target.GetMakefile()->FindTarget(util->c_str(), false);
+      this->ConsiderTargetDepends(depender, depender_depends,
+                                  util->c_str());
+      }
+    }
 
-      // search each local generator until a match is found
-      if (!target2)
-        {
-        target2 = this->FindTarget(0,util->c_str(), false);
-        }
+  return depender_depends;
+}
 
-      // if a match was found then ...
-      if (target2)
-        {
-        // Add this dependency.
-        result.push_back(target2);
-        }
+//----------------------------------------------------------------------------
+bool
+cmGlobalGenerator::ConsiderTargetDepends(cmTarget const* depender,
+                                         TargetDependSet& depender_depends,
+                                         const char* dependee_name)
+{
+  // Check the target's makefile first.
+  cmTarget const* dependee =
+    depender->GetMakefile()->FindTarget(dependee_name, false);
+
+  // Then search globally.
+  if(!dependee)
+    {
+    dependee = this->FindTarget(0, dependee_name, false);
+    }
+
+  // If not found then skip then the dependee.
+  if(!dependee)
+    {
+    return false;
+    }
+
+  // Check whether the depender is among the dependee's dependencies.
+  std::vector<cmTarget const*> steps;
+  if(this->FindDependency(depender, dependee, steps))
+    {
+    // This creates a cyclic dependency.
+    bool isStatic = depender->GetType() == cmTarget::STATIC_LIBRARY;
+    cmOStringStream e;
+    e << "Cyclic dependency among targets:\n"
+      << "  " << depender->GetName() << "\n";
+    for(unsigned int i = static_cast<unsigned int>(steps.size());
+        i > 0; --i)
+      {
+      cmTarget const* step = steps[i-1];
+      e << "    -> " << step->GetName() << "\n";
+      isStatic = isStatic && step->GetType() == cmTarget::STATIC_LIBRARY;
+      }
+    if(isStatic)
+      {
+      e << "  All targets are STATIC libraries.\n";
+      e << "  Dropping "
+        << depender->GetName() << " -> " << dependee->GetName()
+        << " to resolve.\n";
+      cmSystemTools::Message(e.str().c_str());
       }
+    else
+      {
+      e << "  At least one target is not a STATIC library.\n";
+      cmSystemTools::Error(e.str().c_str());
+      }
+    return false;
+    }
+  else
+    {
+    // This does not create a cyclic dependency.
+    depender_depends.insert(dependee);
+    return true;
     }
-  return result;
+}
+
+//----------------------------------------------------------------------------
+bool
+cmGlobalGenerator
+::FindDependency(cmTarget const* goal, cmTarget const* current,
+                 std::vector<cmTarget const*>& steps)
+{
+  if(current == goal)
+    {
+    steps.push_back(current);
+    return true;
+    }
+  TargetDependMap::const_iterator i = this->TargetDependencies.find(current);
+  if(i == this->TargetDependencies.end())
+    {
+    return false;
+    }
+  TargetDependSet const& depends = i->second;
+  for(TargetDependSet::const_iterator j = depends.begin();
+      j != depends.end(); ++j)
+    {
+    if(this->FindDependency(goal, *j, steps))
+      {
+      steps.push_back(current);
+      return true;
+      }
+    }
+  return false;
 }
 
 void cmGlobalGenerator::AddTarget(cmTargets::value_type &v)
diff --git a/Source/cmGlobalGenerator.h b/Source/cmGlobalGenerator.h
index dff2ca7..edb2019 100644
--- a/Source/cmGlobalGenerator.h
+++ b/Source/cmGlobalGenerator.h
@@ -223,8 +223,11 @@ public:
   virtual const char* GetRebuildCacheTargetName() { return 0; }
   virtual const char* GetCleanTargetName()        { return 0; }
 
+  // Class to track a set of dependencies.
+  class TargetDependSet: public std::set<cmTarget const*> {};
+
   // what targets does the specified target depend on
-  std::vector<cmTarget *>& GetTargetDepends(cmTarget& target);
+  TargetDependSet const& GetTargetDepends(cmTarget const& target);
 
   const std::map<cmStdString, std::vector<cmLocalGenerator*> >& GetProjectMap()
                                                const {return this->ProjectMap;}
@@ -260,7 +263,8 @@ protected:
   cmLocalGenerator* CurrentLocalGenerator;
   // map from project name to vector of local generators in that project
   std::map<cmStdString, std::vector<cmLocalGenerator*> > ProjectMap;
-  std::map<cmLocalGenerator*, std::set<cmTarget*> > LocalGeneratorToTargetMap;
+  std::map<cmLocalGenerator*, std::set<cmTarget const*> >
+  LocalGeneratorToTargetMap;
 
   // Set of named installation components requested by the project.
   std::set<cmStdString> InstallComponents;
@@ -286,13 +290,20 @@ private:
   // this is used to improve performance 
   std::map<cmStdString,cmTarget *> TotalTargets;
   std::map<cmStdString,cmTarget *> ImportedTotalTargets;
-  
-  std::map<cmStdString, std::vector<cmTarget *> > TargetDependencies;
 
   cmExternalMakefileProjectGenerator* ExtraGenerator;
 
   // track files replaced during a Generate
   std::vector<std::string> FilesReplacedDuringGenerate;
+
+  // Track inter-target dependencies.
+  bool ConsiderTargetDepends(cmTarget const* depender,
+                             TargetDependSet& depender_depends,
+                             const char* dependee_name);
+  bool FindDependency(cmTarget const* goal, cmTarget const* current,
+                      std::vector<cmTarget const*>& steps);
+  typedef std::map<cmTarget const*, TargetDependSet> TargetDependMap;
+  TargetDependMap TargetDependencies;
 };
 
 #endif
diff --git a/Source/cmGlobalUnixMakefileGenerator3.cxx b/Source/cmGlobalUnixMakefileGenerator3.cxx
index 792ee56..ff29c4a 100644
--- a/Source/cmGlobalUnixMakefileGenerator3.cxx
+++ b/Source/cmGlobalUnixMakefileGenerator3.cxx
@@ -848,7 +848,7 @@ cmGlobalUnixMakefileGenerator3
 
 //----------------------------------------------------------------------------
 int cmGlobalUnixMakefileGenerator3
-::GetTargetTotalNumberOfActions(cmTarget& target, 
+::GetTargetTotalNumberOfActions(cmTarget const& target,
                                 std::set<cmStdString> &emitted)
 {
   // do not double count
@@ -861,9 +861,9 @@ int cmGlobalUnixMakefileGenerator3
       (target.GetMakefile()->GetLocalGenerator());
     result = static_cast<int>(lg->ProgressFiles[target.GetName()].size());
     
-    std::vector<cmTarget *>& depends = this->GetTargetDepends(target);
+    TargetDependSet const& depends = this->GetTargetDepends(target);
     
-    std::vector<cmTarget *>::iterator i;
+    TargetDependSet::const_iterator i;
     for (i = depends.begin(); i != depends.end(); ++i)
       {
       result += this->GetTargetTotalNumberOfActions(**i, emitted);
@@ -877,11 +877,11 @@ unsigned long cmGlobalUnixMakefileGenerator3
 ::GetNumberOfProgressActionsInAll(cmLocalUnixMakefileGenerator3 *lg)
 {
   unsigned long result = 0;
-  std::set<cmTarget*>& targets = this->LocalGeneratorToTargetMap[lg];
-  for(std::set<cmTarget*>::iterator t = targets.begin();
+  std::set<cmTarget const*>& targets = this->LocalGeneratorToTargetMap[lg];
+  for(std::set<cmTarget const*>::iterator t = targets.begin();
       t != targets.end(); ++t)
     {
-    cmTarget* target = *t;
+    cmTarget const* target = *t;
     cmLocalUnixMakefileGenerator3 *lg3 =
       static_cast<cmLocalUnixMakefileGenerator3 *>
       (target->GetMakefile()->GetLocalGenerator());
@@ -898,80 +898,18 @@ cmGlobalUnixMakefileGenerator3
 ::AppendGlobalTargetDepends(std::vector<std::string>& depends,
                             cmTarget& target)
 {
-  // Keep track of dependencies already listed.
-  std::set<cmStdString> emitted;
-
-  // A target should not depend on itself.
-  emitted.insert(target.GetName());
-
-  // Loop over all library dependencies.
-  const cmTarget::LinkLibraryVectorType&
-    tlibs = target.GetOriginalLinkLibraries();
-  for(cmTarget::LinkLibraryVectorType::const_iterator lib = tlibs.begin();
-      lib != tlibs.end(); ++lib)
-    {
-    // Don't emit the same library twice for this target.
-    if(emitted.insert(lib->first).second)
-      {
-      // Add this dependency.
-      this->AppendAnyGlobalDepend(depends, lib->first.c_str(), target);
-      }
-    }
-
-  // Loop over all utility dependencies.
-  const std::set<cmStdString>& tutils = target.GetUtilities();
-  for(std::set<cmStdString>::const_iterator util = tutils.begin();
-      util != tutils.end(); ++util)
-    {
-    // Don't emit the same utility twice for this target.
-    if(emitted.insert(*util).second)
-      {
-      // Add this dependency.
-      this->AppendAnyGlobalDepend(depends, util->c_str(), target);
-      }
-    }
-}
-
-
-//----------------------------------------------------------------------------
-void
-cmGlobalUnixMakefileGenerator3
-::AppendAnyGlobalDepend(std::vector<std::string>& depends, const char* name,
-                        cmTarget &target)
-{
-  cmTarget *result;
-  cmLocalUnixMakefileGenerator3 *lg3;
-
-  // first check the same dir as the current target
-  lg3 = static_cast<cmLocalUnixMakefileGenerator3 *>
-    (target.GetMakefile()->GetLocalGenerator());
-  result = target.GetMakefile()->FindTarget(name, false);
-  
-  // search each local generator until a match is found
-  if (!result)
+  TargetDependSet const& depends_set = this->GetTargetDepends(target);
+  for(TargetDependSet::const_iterator i = depends_set.begin();
+      i != depends_set.end(); ++i)
     {
-    result = this->FindTarget(0, name, false);
-    if (result)
-      {
-      lg3 = static_cast<cmLocalUnixMakefileGenerator3 *>
-        (result->GetMakefile()->GetLocalGenerator());
-      }
-    }
-  
-  // if a match was found then ...
-  if (result)
-    {
-    // Avoid creating cyclic dependencies.
-    if(!this->AllowTargetDepends(&target, result))
-      {
-      return;
-      }
-
     // Create the target-level dependency.
-    std::string tgtName = lg3->GetRelativeTargetDirectory(*result);
+    cmTarget const* dep = *i;
+    cmLocalUnixMakefileGenerator3* lg3 =
+      static_cast<cmLocalUnixMakefileGenerator3*>
+      (dep->GetMakefile()->GetLocalGenerator());
+    std::string tgtName = lg3->GetRelativeTargetDirectory(*dep);
     tgtName += "/all";
     depends.push_back(tgtName);
-    return;
     }
 }
 
@@ -1057,76 +995,3 @@ bool cmGlobalUnixMakefileGenerator3
     }
   return false;
 }
-
-//----------------------------------------------------------------------------
-bool
-cmGlobalUnixMakefileGenerator3
-::AllowTargetDepends(cmTarget const* depender, cmTarget const* dependee)
-{
-  // Check whether the depender is among the dependee's dependencies.
-  std::vector<cmTarget const*> steps;
-  if(this->FindDependency(depender, dependee, steps))
-    {
-    // This creates a cyclic dependency.
-    bool isStatic = depender->GetType() == cmTarget::STATIC_LIBRARY;
-    cmOStringStream e;
-    e << "Cyclic dependency among targets:\n"
-      << "  " << depender->GetName() << "\n";
-    for(unsigned int i = static_cast<unsigned int>(steps.size());
-        i > 0; --i)
-      {
-      cmTarget const* step = steps[i-1];
-      e << "    -> " << step->GetName() << "\n";
-      isStatic = isStatic && step->GetType() == cmTarget::STATIC_LIBRARY;
-      }
-    if(isStatic)
-      {
-      e << "  All targets are STATIC libraries.\n";
-      e << "  Dropping "
-        << depender->GetName() << " -> " << dependee->GetName()
-        << " to resolve.\n";
-      cmSystemTools::Message(e.str().c_str());
-      }
-    else
-      {
-      e << "  At least one target is not a STATIC library.\n";
-      cmSystemTools::Error(e.str().c_str());
-      }
-    return false;
-    }
-  else
-    {
-    // This does not create a cyclic dependency.
-    this->TargetDependencies[depender].insert(dependee);
-    return true;
-    }
-}
-
-//----------------------------------------------------------------------------
-bool
-cmGlobalUnixMakefileGenerator3
-::FindDependency(cmTarget const* goal, cmTarget const* current,
-                 std::vector<cmTarget const*>& steps)
-{
-  if(current == goal)
-    {
-    steps.push_back(current);
-    return true;
-    }
-  TargetDependMap::const_iterator i = this->TargetDependencies.find(current);
-  if(i == this->TargetDependencies.end())
-    {
-    return false;
-    }
-  TargetDependSet const& depends = i->second;
-  for(TargetDependSet::const_iterator j = depends.begin();
-      j != depends.end(); ++j)
-    {
-    if(this->FindDependency(goal, *j, steps))
-      {
-      steps.push_back(current);
-      return true;
-      }
-    }
-  return false;
-}
diff --git a/Source/cmGlobalUnixMakefileGenerator3.h b/Source/cmGlobalUnixMakefileGenerator3.h
index 8ee023c..49c4689 100644
--- a/Source/cmGlobalUnixMakefileGenerator3.h
+++ b/Source/cmGlobalUnixMakefileGenerator3.h
@@ -114,7 +114,7 @@ public:
    const char* config, bool ignoreErrors, bool fast);
 
   // returns some progress informaiton
-  int GetTargetTotalNumberOfActions(cmTarget& target,
+  int GetTargetTotalNumberOfActions(cmTarget const& target,
                                     std::set<cmStdString> &emitted);
   unsigned long GetNumberOfProgressActionsInAll
   (cmLocalUnixMakefileGenerator3 *lg);
@@ -145,9 +145,6 @@ protected:
 
   void AppendGlobalTargetDepends(std::vector<std::string>& depends,
                                  cmTarget& target);
-  void AppendAnyGlobalDepend(std::vector<std::string>& depends, 
-                             const char* name, 
-                             cmTarget &target);
 
   // does this generator need a requires step for any of its targets
   bool NeedRequiresStep(cmTarget const&);
@@ -179,14 +176,6 @@ protected:
 
   std::map<cmStdString, int > TargetSourceFileCount;
   bool ForceVerboseMakefiles;
-
-  bool AllowTargetDepends(cmTarget const* depender,
-                          cmTarget const* dependee);
-  bool FindDependency(cmTarget const* goal, cmTarget const* current,
-                      std::vector<cmTarget const*>& steps);
-  class TargetDependSet: public std::set<cmTarget const*> {};
-  typedef std::map<cmTarget const*, TargetDependSet> TargetDependMap;
-  TargetDependMap TargetDependencies;
 };
 
 #endif
diff --git a/Source/cmLocalUnixMakefileGenerator3.cxx b/Source/cmLocalUnixMakefileGenerator3.cxx
index 49a068c..3ceeccc 100644
--- a/Source/cmLocalUnixMakefileGenerator3.cxx
+++ b/Source/cmLocalUnixMakefileGenerator3.cxx
@@ -823,7 +823,8 @@ cmLocalUnixMakefileGenerator3
 
 //----------------------------------------------------------------------------
 std::string
-cmLocalUnixMakefileGenerator3::GetRelativeTargetDirectory(cmTarget& target)
+cmLocalUnixMakefileGenerator3
+::GetRelativeTargetDirectory(cmTarget const& target)
 {
   std::string dir = this->HomeRelativeOutputPath;
   dir += this->GetTargetDirectory(target);
diff --git a/Source/cmLocalUnixMakefileGenerator3.h b/Source/cmLocalUnixMakefileGenerator3.h
index dcef5b5..c41d0d8 100644
--- a/Source/cmLocalUnixMakefileGenerator3.h
+++ b/Source/cmLocalUnixMakefileGenerator3.h
@@ -210,7 +210,7 @@ public:
   void WriteSpecialTargetsTop(std::ostream& makefileStream);
   void WriteSpecialTargetsBottom(std::ostream& makefileStream);
 
-  std::string GetRelativeTargetDirectory(cmTarget& target);
+  std::string GetRelativeTargetDirectory(cmTarget const& target);
 
   // File pairs for implicit dependency scanning.  The key of the map
   // is the depender and the value is the explicit dependee.
diff --git a/Source/cmTarget.h b/Source/cmTarget.h
index 879693a..8439ee1 100644
--- a/Source/cmTarget.h
+++ b/Source/cmTarget.h
@@ -181,7 +181,7 @@ public:
    */
   void AddUtility(const char* u) { this->Utilities.insert(u);}
   ///! Get the utilities used by this target
-  std::set<cmStdString>const& GetUtilities() { return this->Utilities; }
+  std::set<cmStdString>const& GetUtilities() const { return this->Utilities; }
 
   void AnalyzeLibDependencies( const cmMakefile& mf );