BUG: Correct some of the dependency analysis code.

- Make sure the original link line is untouched
- Avoid duplicating the link line when supporting version < 1.4
- Make sure the cyclic dependencies and such are output correctly in
  complicated cases.
- Avoid outputing dependencies that are already satisfied on the original
  link line when possible.

18 files changed, 216 insertions, 71 deletions

diff --git a/Source/CMakeLists.txt b/Source/CMakeLists.txt
index 56713da..f21807b 100644
--- a/Source/CMakeLists.txt
+++ b/Source/CMakeLists.txt
@@ -177,6 +177,34 @@ IF(BUILD_TESTING)
       ${CMake_BINARY_DIR}/Tests/Dependency/WOLibOut/Exec
       Dependency)
 
+    ADD_TEST(dependency2 ${CMake_BINARY_DIR}/Source/cmaketest 
+      ${CMake_SOURCE_DIR}/Tests/Dependency 
+      ${CMake_BINARY_DIR}/Tests/Dependency/WithLibOut
+      exec2
+      ${CMake_BINARY_DIR}/Tests/Dependency/WithLibOut/Exec2
+      Dependency CMAKE_ARGS -DLIBRARY_OUTPUT_PATH:PATH=${CMake_BINARY_DIR}/Tests/Dependency/WithLibOut/Lib)
+
+    ADD_TEST(dependency3 ${CMake_BINARY_DIR}/Source/cmaketest 
+      ${CMake_SOURCE_DIR}/Tests/Dependency 
+      ${CMake_BINARY_DIR}/Tests/Dependency/WithLibOut
+      exec3
+      ${CMake_BINARY_DIR}/Tests/Dependency/WithLibOut/Exec3
+      Dependency CMAKE_ARGS -DLIBRARY_OUTPUT_PATH:PATH=${CMake_BINARY_DIR}/Tests/Dependency/WithLibOut/Lib)
+
+    ADD_TEST(dependency4 ${CMake_BINARY_DIR}/Source/cmaketest 
+      ${CMake_SOURCE_DIR}/Tests/Dependency 
+      ${CMake_BINARY_DIR}/Tests/Dependency/WithLibOut
+      exec4
+      ${CMake_BINARY_DIR}/Tests/Dependency/WithLibOut/Exec4
+      Dependency CMAKE_ARGS -DLIBRARY_OUTPUT_PATH:PATH=${CMake_BINARY_DIR}/Tests/Dependency/WithLibOut/Lib)
+
+    ADD_TEST(linkline ${CMake_BINARY_DIR}/Source/cmaketest 
+      ${CMake_SOURCE_DIR}/Tests/LinkLine
+      ${CMake_BINARY_DIR}/Tests/LinkLine
+      Exec
+      ${CMake_BINARY_DIR}/Tests/LinkLine
+      LinkLine)
+
   ENDIF (DART_ROOT)
 ENDIF(BUILD_TESTING)
 
diff --git a/Source/cmTarget.cxx b/Source/cmTarget.cxx
index 62da8cf..13a5358 100644
--- a/Source/cmTarget.cxx
+++ b/Source/cmTarget.cxx
@@ -19,7 +19,7 @@
 
 #include <map>
 #include <set>
-
+#include <cassert>
 
 
 void cmTarget::GenerateSourceFilesFromSourceLists( cmMakefile &mf)
@@ -73,15 +73,17 @@ void cmTarget::MergeLinkLibraries( cmMakefile& mf,
                                    const char *selfname,
                                    const LinkLibraries& libs )
 {
-  for( LinkLibraries::const_iterator i = libs.begin();
-       i != libs.end(); ++i )
+  // Only add on libraries we haven't added on before.
+  // Assumption: the global link libraries could only grow, never shrink
+  assert( libs.size() >= m_PrevLinkedLibraries.size() );
+  LinkLibraries::const_iterator i = libs.begin();
+  i += m_PrevLinkedLibraries.size();
+  for( ; 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 );
-      }
+    // We call this so that the dependencies get written to the cache
+    this->AddLinkLibrary( mf, selfname, i->first.c_str(), i->second );
     }
+  m_PrevLinkedLibraries = libs;
 }
 
 void cmTarget::AddLinkDirectory(const char* d)
@@ -231,8 +233,8 @@ cmTarget::AnalyzeLibDependencies( const cmMakefile& mf )
   // 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<cmStdString> done, visited;
+  std::vector<std::string> newLinkLibraries;
   for(LinkLibraries::reverse_iterator lib = m_LinkLibraries.rbegin();
       lib != m_LinkLibraries.rend(); ++lib)
     {
@@ -240,56 +242,57 @@ cmTarget::AnalyzeLibDependencies( const cmMakefile& mf )
     // 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 )
+    // Emit all the dependencies that are not already satisfied on the
+    // original link line.
+    if( dep_map.find(lib->first) != dep_map.end() ) // does it have dependencies?
       {
-      // 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 );
+      const std::set<cmStdString>& dep_on = dep_map.find( lib->first )->second;
+      std::set<cmStdString>::iterator i;
+      for( i = dep_on.begin(); i != dep_on.end(); ++i )
+        {
+        if( satisfied[lib->first].end() == satisfied[lib->first].find( *i ) )
+          {
+          Emit( *i, dep_map, done, visited, newLinkLibraries );
+          }
+        }
       }
-    else
+    }
+
+  // 4. Add the new libraries to the link line.
+
+  for( std::vector<std::string>::reverse_iterator k = newLinkLibraries.rbegin();
+       k != newLinkLibraries.rend(); ++k )
+    {
+    if( addLibDirs )
       {
-      for( std::vector<std::string>::reverse_iterator k = link_line.rbegin();
-           k != link_line.rend(); ++k )
+      const char* libpath = mf.GetDefinition( k->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 )
-            {
-            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) );
+          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;
+        }
+      }
+    m_LinkLibraries.push_back( std::make_pair(*k,llt) );
     }
-  m_LinkLibraries = newLinkLibraries;
 }
 
 
diff --git a/Source/cmTarget.h b/Source/cmTarget.h
index a4e2ac5..cbd2dd6 100644
--- a/Source/cmTarget.h
+++ b/Source/cmTarget.h
@@ -169,7 +169,7 @@ private:
   TargetType m_TargetType;
   std::vector<cmSourceFile*> m_SourceFiles;
   LinkLibraries m_LinkLibraries;
-  std::set<cmStdString> m_PrevLinkedLibraries;
+  LinkLibraries m_PrevLinkedLibraries;
   std::vector<std::string> m_LinkDirectories;
   bool m_InAll;
   std::string m_InstallPath;
diff --git a/Tests/Dependency/CMakeLists.txt b/Tests/Dependency/CMakeLists.txt
index b7debc6..724f109 100644
--- a/Tests/Dependency/CMakeLists.txt
+++ b/Tests/Dependency/CMakeLists.txt
@@ -3,23 +3,6 @@ PROJECT( Dependency )
 # There is one executable that depends on eight libraries. The
 # system has the following dependency graph:
 #
-#                    +----------- NoDepC  <----  EXECUTABLE ---+
-#                    |                            |    |       |
-#                    V                            |    |       |
-#                                                 |    |       |
-#                  NoDepA  <----- NoDepB  <-------+    |       |
-#                                                      |       |
-#                    ^                                 |       V
-#                    |                                 |
-#      One  <------ Four ----->  Two  <----- Five  <---|----- SixB
-#                                |                     |       |
-#       ^           ^  ^         |  ^         ^        |       |
-#       |           |  +-----+   |   \        |        |       |
-#       |           |        |   |    \       |        |       |
-#       +--------- Three  <------+      --- SixA  <----+       |
-#                            |                                 |
-#                            |                                 |
-#                            +---------------------------------+
 # NoDepA:
 # NoDepB: NoDepA
 # NoDepC: NoDepA
@@ -30,14 +13,20 @@ PROJECT( Dependency )
 # Five: Two
 # SixA: Two Five
 # SixB: Four Five
+# Seven: Two
+# Eight: Seven
+#
 # Exec: NoDepB NoDepC SixA SixB
+# Exec2: Eight Five
+# Exec3: Eight Five
+# Exec4: Five Two
 #
-# The libraries One,...,Five have their dependencies explicitly
+# The libraries One,...,Eight have their dependencies explicitly
 # encoded. The libraries NoDepA,...,NoDepC do not.
 #
 # Although SixB does not depend on Two, there is a dependency listed
 # in the corresponding CMakeLists.txt just because of commands used.
 
 SUBDIRS( NoDepA NoDepB NoDepC )
-SUBDIRS( One Two Three Four Five Six )
-SUBDIRS( Exec )
+SUBDIRS( One Two Three Four Five Six Seven Eight )
+SUBDIRS( Exec Exec2 Exec3 Exec4 )
diff --git a/Tests/Dependency/Eight/CMakeLists.txt b/Tests/Dependency/Eight/CMakeLists.txt
new file mode 100644
index 0000000..5d8e756
--- /dev/null
+++ b/Tests/Dependency/Eight/CMakeLists.txt
@@ -0,0 +1,3 @@
+ADD_LIBRARY( Eight EightSrc.c )
+TARGET_LINK_LIBRARIES( Eight Seven )
+
diff --git a/Tests/Dependency/Eight/EightSrc.c b/Tests/Dependency/Eight/EightSrc.c
new file mode 100644
index 0000000..7bfa481
--- /dev/null
+++ b/Tests/Dependency/Eight/EightSrc.c
@@ -0,0 +1,6 @@
+void SevenFunction();
+
+void EightFunction()
+{
+  SevenFunction();
+}
diff --git a/Tests/Dependency/Exec2/CMakeLists.txt b/Tests/Dependency/Exec2/CMakeLists.txt
new file mode 100644
index 0000000..ee0c74d
--- /dev/null
+++ b/Tests/Dependency/Exec2/CMakeLists.txt
@@ -0,0 +1,12 @@
+# Here, Eight depends on Seven, which has the same dependencies as Five.
+# If the dependencies of Five are emitted, and then we attempt to emit the
+# dependencies of Seven, then we find that they have already been done. So:
+#  Original line:      Eight Five
+#  Add deps of Five:   Eight Five Two ... NoDepA 
+# Now, we must make sure that Seven gets inserted between Five and Two, and
+# not at the end. Unfortunately, if we get it wrong, the test will only
+# fail on a platform where the link order makes a difference.
+LINK_LIBRARIES( Eight Five )
+
+ADD_EXECUTABLE( exec2 ExecMain.c )
+
diff --git a/Tests/Dependency/Exec2/ExecMain.c b/Tests/Dependency/Exec2/ExecMain.c
new file mode 100644
index 0000000..d08a796
--- /dev/null
+++ b/Tests/Dependency/Exec2/ExecMain.c
@@ -0,0 +1,14 @@
+#include <stdio.h>
+
+void FiveFunction();
+void EightFunction();
+
+int main( )
+{
+  FiveFunction();
+  EightFunction();
+
+  printf("Dependency test executable ran successfully.\n");
+
+  return 0;
+}
diff --git a/Tests/Dependency/Exec3/CMakeLists.txt b/Tests/Dependency/Exec3/CMakeLists.txt
new file mode 100644
index 0000000..b33e732
--- /dev/null
+++ b/Tests/Dependency/Exec3/CMakeLists.txt
@@ -0,0 +1,6 @@
+# Here, Five already has it's immediate dependency, Two satisfied. We must
+# make sure Two gets output anyway, because Eight indirectly depends on it.
+LINK_LIBRARIES( Five Two Eight Five )
+
+ADD_EXECUTABLE( exec3 ExecMain.c )
+
diff --git a/Tests/Dependency/Exec3/ExecMain.c b/Tests/Dependency/Exec3/ExecMain.c
new file mode 100644
index 0000000..d08a796
--- /dev/null
+++ b/Tests/Dependency/Exec3/ExecMain.c
@@ -0,0 +1,14 @@
+#include <stdio.h>
+
+void FiveFunction();
+void EightFunction();
+
+int main( )
+{
+  FiveFunction();
+  EightFunction();
+
+  printf("Dependency test executable ran successfully.\n");
+
+  return 0;
+}
diff --git a/Tests/Dependency/Exec4/CMakeLists.txt b/Tests/Dependency/Exec4/CMakeLists.txt
new file mode 100644
index 0000000..6fcb153
--- /dev/null
+++ b/Tests/Dependency/Exec4/CMakeLists.txt
@@ -0,0 +1,6 @@
+# Even though Five's dependency on Two is explicitly satisfied, Two
+# must be emitted again in order to satisfy a cyclic dependency on Three.
+LINK_LIBRARIES( Five Two Five )
+
+ADD_EXECUTABLE( exec4 ExecMain.c )
+
diff --git a/Tests/Dependency/Exec4/ExecMain.c b/Tests/Dependency/Exec4/ExecMain.c
new file mode 100644
index 0000000..3f53573
--- /dev/null
+++ b/Tests/Dependency/Exec4/ExecMain.c
@@ -0,0 +1,14 @@
+#include <stdio.h>
+
+void FiveFunction();
+void TwoFunction();
+
+int main( )
+{
+  FiveFunction();
+  TwoFunction();
+
+  printf("Dependency test executable ran successfully.\n");
+
+  return 0;
+}
diff --git a/Tests/Dependency/Seven/CMakeLists.txt b/Tests/Dependency/Seven/CMakeLists.txt
new file mode 100644
index 0000000..51a38d8
--- /dev/null
+++ b/Tests/Dependency/Seven/CMakeLists.txt
@@ -0,0 +1,3 @@
+ADD_LIBRARY( Seven SevenSrc.c )
+TARGET_LINK_LIBRARIES( Seven Two )
+
diff --git a/Tests/Dependency/Seven/SevenSrc.c b/Tests/Dependency/Seven/SevenSrc.c
new file mode 100644
index 0000000..e1f3329
--- /dev/null
+++ b/Tests/Dependency/Seven/SevenSrc.c
@@ -0,0 +1,6 @@
+void TwoFunction();
+
+void SevenFunction()
+{
+  TwoFunction();
+}
diff --git a/Tests/LinkLine/CMakeLists.txt b/Tests/LinkLine/CMakeLists.txt
new file mode 100644
index 0000000..a7d138d
--- /dev/null
+++ b/Tests/LinkLine/CMakeLists.txt
@@ -0,0 +1,12 @@
+PROJECT( LinkLine )
+
+# Makes sure that the library order as specified by the user are
+# unchanged by dependency analysis, etc.  libOne and libTwo are
+# dependent on each other. The link line should be -lOne -lTwo -lOne.
+
+ADD_LIBRARY( One One.c )
+ADD_LIBRARY( Two Two.c )
+
+LINK_LIBRARIES( One Two )
+ADD_EXECUTABLE( Exec Exec.c )
+LINK_LIBRARIES( One )
diff --git a/Tests/LinkLine/Exec.c b/Tests/LinkLine/Exec.c
new file mode 100644
index 0000000..807a7a8
--- /dev/null
+++ b/Tests/LinkLine/Exec.c
@@ -0,0 +1,9 @@
+void OneFunc();
+void TwoFunc();
+
+int main()
+{
+  OneFunc();
+  TwoFunc();
+  return 0;
+}
diff --git a/Tests/LinkLine/One.c b/Tests/LinkLine/One.c
new file mode 100644
index 0000000..167f07d
--- /dev/null
+++ b/Tests/LinkLine/One.c
@@ -0,0 +1,10 @@
+void TwoFunc();
+
+void OneFunc()
+{
+  static int i = 0;
+  ++i;
+  if( i==1 ) {
+    TwoFunc();
+  }
+}
diff --git a/Tests/LinkLine/Two.c b/Tests/LinkLine/Two.c
new file mode 100644
index 0000000..0db73a8
--- /dev/null
+++ b/Tests/LinkLine/Two.c
@@ -0,0 +1,10 @@
+void OneFunc();
+
+void TwoFunc()
+{
+  static int i = 0;
+  ++i;
+  if( i==1 ) {
+    OneFunc();
+  }
+}