ENH: rework library depend stuff

3 files changed, 137 insertions, 174 deletions

diff --git a/Source/cmMakefile.cxx b/Source/cmMakefile.cxx
index f8bd461..40b0d45 100644
--- a/Source/cmMakefile.cxx
+++ b/Source/cmMakefile.cxx
@@ -665,11 +665,7 @@ void cmMakefile::AddGlobalLinkInformation(const char* name, cmTarget& target)
     {
     target.AddLinkDirectory(j->c_str());
     }
-  cmTarget::LinkLibraries::iterator  i;
-  for(i = m_LinkLibraries.begin(); i != m_LinkLibraries.end(); ++i)
-    {
-    this->AddLinkLibraryForTarget(name, i->first.c_str(), i->second);
-    }
+  target.MergeLinkLibraries( *this, name, m_LinkLibraries );
 }
 
 
@@ -703,8 +699,8 @@ void cmMakefile::AddLibrary(const char* lname, int shared,
   
   target.SetInAll(true);
   target.GetSourceLists() = srcs;
-  m_Targets.insert(cmTargets::value_type(lname,target));
   this->AddGlobalLinkInformation(lname, target);
+  m_Targets.insert(cmTargets::value_type(lname,target));
 
   // Add an entry into the cache 
   cmCacheManager::GetInstance()->
@@ -769,8 +765,10 @@ void cmMakefile::AddExecutable(const char *exeName,
     }
   target.SetInAll(true);
   target.GetSourceLists() = srcs;
-  m_Targets.insert(cmTargets::value_type(exeName,target));
   this->AddGlobalLinkInformation(exeName, target);
+
+  m_Targets.insert(cmTargets::value_type(exeName,target));
+  
   
   // Add an entry into the cache 
   cmCacheManager::GetInstance()->
diff --git a/Source/cmTarget.cxx b/Source/cmTarget.cxx
index 9142f1f..e38f245 100644
--- a/Source/cmTarget.cxx
+++ b/Source/cmTarget.cxx
@@ -21,6 +21,7 @@
 #include <set>
 
 
+
 void cmTarget::GenerateSourceFilesFromSourceLists( cmMakefile &mf)
 {
   // this is only done for non install targets
@@ -68,6 +69,31 @@ void cmTarget::GenerateSourceFilesFromSourceLists( cmMakefile &mf)
 }
 
 
+void cmTarget::MergeLinkLibraries( cmMakefile& mf,
+                                   const char *selfname,
+                                   const LinkLibraries& libs )
+{
+  for( LinkLibraries::const_iterator i = libs.begin();
+       i != libs.end(); ++i )
+    {
+    if(m_PrevLinkedLibraries.insert(i->first).second)
+      {
+      // We call this so that the dependencies get written to the cache
+      this->AddLinkLibrary( mf, selfname, i->first.c_str(), i->second );
+      }
+    }
+}
+
+void cmTarget::AddLinkDirectory(const char* d)
+{
+  // Make sure we don't add unnecessary search directories.
+  if( std::find( m_LinkDirectories.begin(), m_LinkDirectories.end(), d )
+      == m_LinkDirectories.end() )
+    m_LinkDirectories.push_back( d );
+}
+
+
+
 void cmTarget::AddLinkLibrary(const std::string& lib, 
                               LinkLibraryType llt)
 {
@@ -164,152 +190,106 @@ cmTarget::AnalyzeLibDependencies( const cmMakefile& mf )
   // hurts to document the assumptions. :-) Therefore, in the analysis
   // code, the "canonical name" of a library is simply its name as
   // given to a LINK_LIBRARIES command.
+  //
+  // Also, we will leave the original link line intact; we will just add any
+  // dependencies that were missing.
 
   typedef std::vector< std::string > LinkLine;
 
-  // Maps the canonical names to the full objects of m_LinkLibraries.
-  LibTypeMap lib_map;
-
-  // The unique list of libraries on the orginal link line. They
-  // correspond to lib_map keys. However, lib_map will also get
-  // further populated by the dependency analysis, while this will be
-  // unchanged.
-  LinkLine orig_libs;
-
-  // The list canonical names in the order they were orginally
-  // specified on the link line (m_LinkLibraries).
-  LinkLine lib_order;
-
-  // The dependency maps.
-  DependencyMap dep_map, dep_map_implicit;
-
-
-  // 1. Determine the list of unique libraries in the original link
-  // line.
-
-  LinkLibraries::iterator lib;
-  for(lib = m_LinkLibraries.begin(); lib != m_LinkLibraries.end(); ++lib)
-    {
-    // skip zero size library entries, this may happen
-    // if a variable expands to nothing.
-    if (lib->first.size() == 0) continue;
-
-    const std::string& cname = lib->first;
-    lib_order.push_back( cname );
-    if( lib_map.end() == lib_map.find( cname ) )
-      {
-      lib_map[ cname ] = *lib;
-      orig_libs.push_back( cname );
-      }
-    }
-
-  // 2. Gather the dependencies.
+  // The dependency map.
+  DependencyMap dep_map;
+  
+  // Keeps track of which dependencies have already been emitted for a given
+  // target. This could be via this function, or because they were already
+  // satisfied on the original link line.
+  DependencyMap satisfied;
 
   // If LIBRARY_OUTPUT_PATH is not set, then we must add search paths
   // for all the new libraries added by the dependency analysis.
   const char* libOutPath = mf.GetDefinition("LIBRARY_OUTPUT_PATH");
   bool addLibDirs = (libOutPath==0 || strcmp(libOutPath,"")==0);
 
-  // First, get the explicit dependencies for those libraries that
-  // have specified them.
-  for( LinkLine::iterator i = orig_libs.begin(); i != orig_libs.end(); ++i )
-    {
-    this->GatherDependencies( mf, *i, dep_map, lib_map, addLibDirs );
-    }
-
-  // For the rest, get implicit dependencies. A library x depends
-  // implicitly on a library y if x appears before y on the link
-  // line. However, x does not implicitly depend on y if y
-  // *explicitly* depends on x [*1]--such cyclic dependencies must be
-  // explicitly specified. Note that implicit dependency cycles can
-  // still occur: "-lx -ly -lx" will generate a implicit dependency
-  // cycle provided that neither x nor y have explicit dependencies.
-  //
-  // [*1] This prevents external libraries from depending on libraries
-  // generated by this project.
-
-  for( LinkLine::iterator i = orig_libs.begin(); i != orig_libs.end(); ++i )
+  // 1. Determine the dependencies already satisfied by the original link
+  // line.
+  for(LinkLibraries::iterator lib = m_LinkLibraries.begin();
+      lib != m_LinkLibraries.end(); ++lib)
     {
-    if( dep_map.find( *i ) == dep_map.end() )
+    for( LinkLibraries::iterator lib2 = lib;
+      lib2 != m_LinkLibraries.end(); ++lib2)
       {
-      LinkLine::iterator pos = std::find( lib_order.begin(), lib_order.end(), *i );
-      for( ; pos != lib_order.end(); ++pos )
-        {
-        std::set<std::string> visited;
-        if( !DependsOn( *pos, *i, dep_map, visited ) )
-          {
-          dep_map_implicit[ *i ].insert( *pos );
-          }
-        }
-      dep_map_implicit[ *i ].erase( *i ); // cannot depend on itself
+      satisfied[ lib->first ].insert( lib2->first );
       }
     }
-
-  // Combine all the depedency information
-  //   dep_map.insert( dep_map_implicit.begin(), dep_map_implicit.end() );
-  // doesn't work under MSVC++.
-  for( DependencyMap::iterator i = dep_map_implicit.begin();
-       i != dep_map_implicit.end(); ++i )
-	{
-	dep_map[ i->first ] = i->second;
-	}
-
-  // 3. Create a new link line, trying as much as possible to keep the
-  // original link line order.
-
-  // Get the link line as canonical names.
-  std::set<std::string> done, visited;
-  std::vector<std::string> link_line;
-  for( LinkLine::iterator i = orig_libs.begin(); i != orig_libs.end(); ++i )
+  
+  // 2. Build the explicit dependency map
+  for(LinkLibraries::reverse_iterator lib = m_LinkLibraries.rbegin();
+      lib != m_LinkLibraries.rend(); ++lib)
     {
-    Emit( *i, dep_map, done, visited, link_line );
+    this->GatherDependencies( mf, lib->first, dep_map );
     }
-
-  // Translate the canonical names into internal objects.
-  m_LinkLibraries.clear();
-  for( std::vector<std::string>::reverse_iterator i = link_line.rbegin();
-       i != link_line.rend(); ++i )
+  
+  // 3. Create the new link line by simply emitting any dependencies that are
+  // missing.  Start from the back and keep adding.
+  
+  LinkLibraries newLinkLibraries = m_LinkLibraries;
+  std::set<std::string> done, visited;
+  for(LinkLibraries::reverse_iterator lib = m_LinkLibraries.rbegin();
+      lib != m_LinkLibraries.rend(); ++lib)
     {
-    // Some of the libraries in the new link line may not have been in
-    // the orginal link line, but were added by the dependency
-    // analysis.
-    if( lib_map.find(*i) == lib_map.end() )
+    // skip zero size library entries, this may happen
+    // if a variable expands to nothing.
+    if (lib->first.size() == 0) continue;
+
+    std::vector<std::string> link_line;
+    Emit( lib->first, dep_map, done, visited, link_line );
+    if( link_line.size() == 0 )
+      {
+      // everything for this library is already on the link line, but since
+      // we are not going to touch the user's link line, we will output the
+      // library anyway.
+      newLinkLibraries.push_back( *lib );
+      }
+    else
       {
-      if( addLibDirs )
+      for( std::vector<std::string>::reverse_iterator k = link_line.rbegin();
+           k != link_line.rend(); ++k )
         {
-        const char* libpath = mf.GetDefinition( i->c_str() );
-        if( libpath )
+        if( satisfied[lib->first].insert( *k ).second )
           {
-          // Don't add a link directory that is already present.
-          if(std::find(m_LinkDirectories.begin(),
-                       m_LinkDirectories.end(), libpath) == m_LinkDirectories.end())
+          if( addLibDirs )
             {
-            m_LinkDirectories.push_back(libpath);
+            const char* libpath = mf.GetDefinition( k->c_str() );
+            if( libpath )
+              {
+              // Don't add a link directory that is already present.
+              if(std::find(m_LinkDirectories.begin(),
+                           m_LinkDirectories.end(), libpath) == m_LinkDirectories.end())
+                {
+                m_LinkDirectories.push_back(libpath);
+                }
+              }
             }
+          std::string linkType = *k;
+          linkType += "_LINK_TYPE";
+          cmTarget::LinkLibraryType llt = cmTarget::GENERAL;
+          const char* linkTypeString = mf.GetDefinition( linkType.c_str() );
+          if(linkTypeString)
+            {
+            if(strcmp(linkTypeString, "debug") == 0)
+              {
+              llt = cmTarget::DEBUG;
+              }
+            if(strcmp(linkTypeString, "optimized") == 0)
+              {
+              llt = cmTarget::OPTIMIZED;
+              }
+            }
+          newLinkLibraries.push_back( std::make_pair(*k,llt) );
           }
         }
-      std::string linkType = *i;
-      linkType += "_LINK_TYPE";
-      cmTarget::LinkLibraryType llt = cmTarget::GENERAL;
-      const char* linkTypeString = mf.GetDefinition( linkType.c_str() );
-      if(linkTypeString)
-        {
-        if(strcmp(linkTypeString, "debug") == 0)
-          {
-          llt = cmTarget::DEBUG;
-          }
-        if(strcmp(linkTypeString, "optimized") == 0)
-          {
-          llt = cmTarget::OPTIMIZED;
-          }
-        }
-      m_LinkLibraries.push_back( std::make_pair(*i,llt) );
-      }
-    else
-      {
-      m_LinkLibraries.push_back( lib_map[ *i ] );
       }
     }
+  m_LinkLibraries = newLinkLibraries;
 }
 
 
@@ -352,9 +332,7 @@ void cmTarget::Emit( const std::string& lib,
 
 void cmTarget::GatherDependencies( const cmMakefile& mf,
                                    const std::string& lib,
-                                   DependencyMap& dep_map,
-                                   LibTypeMap& lib_map,
-                                   bool addLibDirs )
+                                   DependencyMap& dep_map )
 {
   // If the library is already in the dependency map, then it has
   // already been fully processed.
@@ -380,38 +358,8 @@ void cmTarget::GatherDependencies( const cmMakefile& mf,
       std::string l = depline.substr( start, end-start );
       if( l.size() != 0 )
         {
-        if( addLibDirs )
-          {
-          const char* libpath = mf.GetDefinition( l.c_str() );
-          if( libpath )
-            {
-            // Don't add a link directory that is already present.
-              if(std::find(m_LinkDirectories.begin(),
-                           m_LinkDirectories.end(), libpath) == m_LinkDirectories.end())
-                {
-                m_LinkDirectories.push_back(libpath);
-                }
-            }
-          }
-        const std::string& cname = l; 
-        std::string linkType = l;
-        linkType += "_LINK_TYPE";
-        cmTarget::LinkLibraryType llt = cmTarget::GENERAL;
-        const char* linkTypeString = mf.GetDefinition( linkType.c_str() );
-        if(linkTypeString)
-          {
-          if(strcmp(linkTypeString, "debug") == 0)
-            {
-            llt = cmTarget::DEBUG;
-            }
-          if(strcmp(linkTypeString, "optimized") == 0)
-            {
-            llt = cmTarget::OPTIMIZED;
-            }
-          }
-        lib_map[ cname ] = std::make_pair(l,llt); 
-        dep_map[ lib ].insert( cname );
-        GatherDependencies( mf, cname, dep_map, lib_map, addLibDirs );
+        dep_map[ lib ].insert( l );
+        GatherDependencies( mf, l, dep_map );
         }
       start = end+1; // skip the ;
       end = depline.find( ";", start );
@@ -421,30 +369,43 @@ void cmTarget::GatherDependencies( const cmMakefile& mf,
 }
 
 
+// return true if lib1 depends on lib2
+
 bool cmTarget::DependsOn( const std::string& lib1, const std::string& lib2,
                           const DependencyMap& dep_map,
                           std::set<std::string>& visited ) const
 {
   if( !visited.insert( lib1 ).second )
+    {
     return false; // already visited here
+    }
+  
 
   if( lib1 == lib2 )
+    {
     return false;
+    }
 
   if( dep_map.find(lib1) == dep_map.end() )
+    {
     return false; // lib1 doesn't have any dependencies
+    }
 
   const std::set<std::string>& dep_set = dep_map.find(lib1)->second;
 
   if( dep_set.end() != dep_set.find( lib2 )  )
+    {
     return true; // lib1 doesn't directly depend on lib2.
+    }
 
   // Do a recursive check: does lib1 depend on x which depends on lib2?
   for( std::set<std::string>::const_iterator itr = dep_set.begin();
        itr != dep_set.end(); ++itr )
     {
-      if( DependsOn( *itr, lib2, dep_map, visited ) )
+      if( this->DependsOn( *itr, lib2, dep_map, visited ) )
+        {
         return true;
+        }
     }
 
   return false;
diff --git a/Source/cmTarget.h b/Source/cmTarget.h
index 0fcf353..37a2de5 100644
--- a/Source/cmTarget.h
+++ b/Source/cmTarget.h
@@ -80,8 +80,18 @@ public:
   typedef std::vector<std::pair<std::string,LinkLibraryType> > LinkLibraries;
   const LinkLibraries &GetLinkLibraries() const {return m_LinkLibraries;}
 
+  void AddLinkLibrary(cmMakefile& mf,
+                      const char *target, const char* lib, 
+                      LinkLibraryType llt);
+
+  void AddLinkLibrary(const std::string& lib, 
+                      LinkLibraryType llt);
+
+  void MergeLinkLibraries( cmMakefile& mf, const char* selfname, const LinkLibraries& libs );
+
   const std::vector<std::string>& GetLinkDirectories() const {return m_LinkDirectories;}
-  void AddLinkDirectory(const char* d) { m_LinkDirectories.push_back(d);}
+  
+  void AddLinkDirectory(const char* d);
 
   /**
    * Set the path where this target should be installed. This is relative to
@@ -90,13 +100,7 @@ public:
   std::string GetInstallPath() const {return m_InstallPath;}
   void SetInstallPath(const char *name) {m_InstallPath = name;}
   
-  void AddLinkLibrary(cmMakefile& mf,
-                      const char *target, const char* lib, 
-                      LinkLibraryType llt);
-
-  void AddLinkLibrary(const std::string& lib, 
-                      LinkLibraryType llt);
-
+  
   /**
    * Generate the SourceFilesList from the SourceLists. This should only be
    * done once to be safe.  
@@ -148,8 +152,7 @@ private:
    * path.
    */
   void GatherDependencies( const cmMakefile& mf, const std::string& lib,
-                           DependencyMap& dep_map,
-                           LibTypeMap& lib_map, bool addLibDirs );
+                           DependencyMap& dep_map );
 
   /**
    * Returns true if lib1 depends on lib2 according to \param
@@ -166,6 +169,7 @@ private:
   TargetType m_TargetType;
   std::vector<cmSourceFile*> m_SourceFiles;
   LinkLibraries m_LinkLibraries;
+  std::set<std::string> m_PrevLinkedLibraries;
   std::vector<std::string> m_LinkDirectories;
   bool m_InAll;
   std::string m_InstallPath;