ENH: Add library dependency analysis.

29 files changed, 539 insertions, 39 deletions

diff --git a/Source/CMakeLists.txt b/Source/CMakeLists.txt
index b9f3b56..0a27df0 100644
--- a/Source/CMakeLists.txt
+++ b/Source/CMakeLists.txt
@@ -162,6 +162,14 @@ IF(BUILD_TESTING)
       ${CMake_BINARY_DIR}/Tests/Wrapping/bin
       TestDriverTest subdir/test3)
 
+    ADD_TEST(dependency ${CMake_BINARY_DIR}/Source/cmaketest 
+      ${CMake_SOURCE_DIR}/Tests/Dependency 
+      ${CMake_BINARY_DIR}/Tests/Dependency
+      exec
+      ${CMake_BINARY_DIR}/Tests/Dependency/Exec
+      Dependency)
+
+  ENDIF (DART_ROOT)
 ENDIF(BUILD_TESTING)
 
 
diff --git a/Source/cmDSPWriter.cxx b/Source/cmDSPWriter.cxx
index 867961c..54c696b 100644
--- a/Source/cmDSPWriter.cxx
+++ b/Source/cmDSPWriter.cxx
@@ -653,8 +653,8 @@ void cmDSPWriter::WriteDSPHeader(std::ostream& fout, const char *libName,
       libMultiLineOptions += " \n";
       }
     }
-  std::vector<std::string>::iterator i;
-  std::vector<std::string>& libdirs = m_Makefile->GetLinkDirectories();
+  std::vector<std::string>::const_iterator i;
+  const std::vector<std::string>& libdirs = target.GetLinkDirectories();
   for(i = libdirs.begin(); i != libdirs.end(); ++i)
     {
     std::string path = *i;
diff --git a/Source/cmDSWWriter.cxx b/Source/cmDSWWriter.cxx
index c6dbfef..d06c407 100644
--- a/Source/cmDSWWriter.cxx
+++ b/Source/cmDSWWriter.cxx
@@ -169,8 +169,7 @@ void cmDSWWriter::WriteDSWFile(std::ostream& fout)
                   }
                 else
                   {
-                  l->second.GetLinkLibraries().push_back(
-                    cmTarget::LinkLibraries::value_type(al->first, cmTarget::GENERAL));
+                  l->second.AddLinkLibrary(al->first, cmTarget::GENERAL);
                   }
                 }
               }
diff --git a/Source/cmMSDotNETGenerator.cxx b/Source/cmMSDotNETGenerator.cxx
index 58ee5fd..ff5e27c 100644
--- a/Source/cmMSDotNETGenerator.cxx
+++ b/Source/cmMSDotNETGenerator.cxx
@@ -240,9 +240,7 @@ void cmMSDotNETGenerator::WriteSLNFile(std::ostream& fout)
                   }
                 else
                   {
-                  l->second.GetLinkLibraries().push_back(
-                    cmTarget::LinkLibraries::value_type(al->first,
-                                                        cmTarget::GENERAL));
+                  l->second.AddLinkLibrary(al->first,cmTarget::GENERAL);
                   }
                 }
               }
@@ -907,7 +905,7 @@ void cmMSDotNETGenerator::OutputModuleDefinitionFile(std::ostream& fout,
 void cmMSDotNETGenerator::OutputLibraryDirectories(std::ostream& fout,
                                                    const char*,
                                                    const char*,
-                                                   const cmTarget &)
+                                                   const cmTarget &tgt)
 {
   bool hasone = false;
   if(m_LibraryOutputPath.size())
@@ -922,8 +920,8 @@ void cmMSDotNETGenerator::OutputLibraryDirectories(std::ostream& fout,
     }
     
   std::set<std::string> pathEmitted;
-  std::vector<std::string>::iterator i;
-  std::vector<std::string>& libdirs = m_Makefile->GetLinkDirectories();
+  std::vector<std::string>::const_iterator i;
+  const std::vector<std::string>& libdirs = tgt.GetLinkDirectories();
   for(i = libdirs.begin(); i != libdirs.end(); ++i)
     {
     std::string lpath = *i;
diff --git a/Source/cmMakefile.cxx b/Source/cmMakefile.cxx
index fd2989a..091bbb4 100644
--- a/Source/cmMakefile.cxx
+++ b/Source/cmMakefile.cxx
@@ -429,6 +429,8 @@ void cmMakefile::GenerateMakefile()
     {
     l->second.GenerateSourceFilesFromSourceLists(*this);
     l->second.MergeLibraries(m_LinkLibraries);
+    l->second.MergeDirectories(m_LinkDirectories);
+    l->second.AnalyzeLibDependencies(*this);
     }
   // now do the generation
   m_MakefileGenerator->GenerateMakefile();
@@ -521,9 +523,7 @@ void cmMakefile::AddLinkLibraryForTarget(const char *target,
 {
   if (m_Targets.find(target) != m_Targets.end())
     {
-    m_Targets[target].GetLinkLibraries().
-      push_back(
-        std::pair<std::string, cmTarget::LinkLibraryType>(lib,llt));
+    m_Targets[target].AddLinkLibrary( *this, target, lib, llt );
     }
   else
     {
@@ -695,6 +695,15 @@ void cmMakefile::AddLibrary(const char* lname, int shared,
 		      "Whether a library is static, shared or module.",
 		      cmCacheManager::INTERNAL);
     }
+
+  // Clear its dependencies. Otherwise, dependencies might persist
+  // over changes in CMakeLists.txt, making the information stale and
+  // hence useless.
+  std::string depname = lname;
+  depname += "_LIB_DEPENDS";
+  cmCacheManager::GetInstance()->
+    AddCacheEntry(depname.c_str(), "",
+                  "Dependencies for target", cmCacheManager::INTERNAL);
 }
 
 void cmMakefile::AddExecutable(const char *exeName, 
@@ -861,7 +870,7 @@ void cmMakefile::ExpandVariables()
     }
 }
 
-bool cmMakefile::IsOn(const char* name)
+bool cmMakefile::IsOn(const char* name) const
 {
   const char* value = this->GetDefinition(name);
   return cmSystemTools::IsOn(value);
diff --git a/Source/cmMakefile.h b/Source/cmMakefile.h
index dede6ac..d6db91c 100644
--- a/Source/cmMakefile.h
+++ b/Source/cmMakefile.h
@@ -391,14 +391,6 @@ public:
     }
 
   /**
-   * Get a list of link directories in the build.
-   */
-  std::vector<std::string>& GetLinkDirectories()
-    { 
-    return m_LinkDirectories;
-    }
-  
-  /**
    * Return a list of source files in this makefile.
    */
   typedef std::map<cmStdString,std::vector<cmSourceFile*> > SourceMap;
@@ -440,7 +432,7 @@ public:
   /** Test a boolean cache entry to see if it is true or false, 
    *  returns false if no entry defined.
    */
-  bool IsOn(const char* name);
+  bool IsOn(const char* name) const;
 
   /**
    * Get a list of preprocessor define flags.
diff --git a/Source/cmNMakeMakefileGenerator.cxx b/Source/cmNMakeMakefileGenerator.cxx
index 3744560..eee9685 100644
--- a/Source/cmNMakeMakefileGenerator.cxx
+++ b/Source/cmNMakeMakefileGenerator.cxx
@@ -578,8 +578,8 @@ void cmNMakeMakefileGenerator::OutputLinkLibraries(std::ostream& fout,
         
   if (lib_path_opt.size())
     {
-    std::vector<std::string>& libdirs = m_Makefile->GetLinkDirectories();
-    for(std::vector<std::string>::iterator libDir = libdirs.begin();
+    const std::vector<std::string>& libdirs = tgt.GetLinkDirectories();
+    for(std::vector<std::string>::const_iterator libDir = libdirs.begin();
         libDir != libdirs.end(); ++libDir)
       { 
       std::string libpath = ShortPath(libDir->c_str());
diff --git a/Source/cmTarget.cxx b/Source/cmTarget.cxx
index cd0a96a..8410f0e 100644
--- a/Source/cmTarget.cxx
+++ b/Source/cmTarget.cxx
@@ -17,6 +17,10 @@
 #include "cmTarget.h"
 #include "cmMakefile.h"
 
+#include <map>
+#include <set>
+
+
 void cmTarget::GenerateSourceFilesFromSourceLists( cmMakefile &mf)
 {
   // this is only done for non install targets
@@ -59,20 +63,52 @@ void cmTarget::GenerateSourceFilesFromSourceLists( cmMakefile &mf)
   LinkLibraries::iterator p = m_LinkLibraries.begin();
   for (;p != m_LinkLibraries.end(); ++p)
     {
-    mf.ExpandVariablesInString(p->first);    
+    mf.ExpandVariablesInString(p->first);
     }
 }
 
 void cmTarget::MergeLibraries(const LinkLibraries &ll)
 {
-  typedef std::vector<std::pair<std::string,LinkLibraryType> > LinkLibraries;
+  m_LinkLibraries.insert( m_LinkLibraries.end(), ll.begin(), ll.end() );
+}
+
+void cmTarget::MergeDirectories(const std::vector<std::string>  &ld)
+{
+  m_LinkDirectories.insert( m_LinkDirectories.end(), ld.begin(), ld.end() );
+}
+
 
-  LinkLibraries::const_iterator p = ll.begin();
-  for (;p != ll.end(); ++p)
+void cmTarget::AddLinkLibrary(const std::string& lib, 
+                              LinkLibraryType llt)
+{
+  m_LinkLibraries.push_back( std::pair<std::string, cmTarget::LinkLibraryType>(lib,llt) );
+}
+
+void cmTarget::AddLinkLibrary(cmMakefile& mf,
+                              const char *target, const char* lib, 
+                              LinkLibraryType llt)
+{
+  m_LinkLibraries.push_back( std::pair<std::string, cmTarget::LinkLibraryType>(lib,llt) );
+
+  // Add the explicit dependency information for this target. This is
+  // simply a set of libraries separated by ";". There should always
+  // be a trailing ";". These library names are not canonical, in that
+  // they may be "-framework x", "-ly", "/path/libz.a", etc.
+  std::string cache_name( target );
+  cache_name += "_LIB_DEPENDS";
+  std::string dependencies;
+  const char* old_val = mf.GetDefinition( cache_name.c_str() );
+  if( old_val )
     {
-    m_LinkLibraries.push_back(*p);
+    dependencies += old_val;
     }
-
+  if( dependencies.find( lib ) == std::string::npos )
+    {
+    dependencies += lib;
+    dependencies += ";";
+    }
+  mf.AddCacheDefinition( cache_name.c_str(), dependencies.c_str(),
+                         "Dependencies for the target", cmCacheManager::INTERNAL );
 }
 
 bool cmTarget::HasCxx() const
@@ -87,3 +123,264 @@ bool cmTarget::HasCxx() const
     }
   return false;
 }
+
+
+void
+cmTarget::AnalyzeLibDependencies( const cmMakefile& mf )
+{
+  typedef std::map< std::string, std::pair<std::string,LinkLibraryType> > LibMap;
+  typedef std::vector< std::string > LinkLine;
+
+  // Maps the canonical names to the full objects of m_LinkLibraries.
+  LibMap lib_map;
+
+  // 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;
+
+  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;
+
+    std::string cname = CanonicalLibraryName(lib->first);
+    lib_map[ cname ] = *lib;
+    lib_order.push_back( cname );
+    }
+
+  // First, get the explicit dependencies for those libraries that
+  // have specified them
+  for( LibMap::iterator i = lib_map.begin(); i != lib_map.end(); ++i )
+    {
+    GatherDependencies( mf, i->first, dep_map );
+    }
+
+  // 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( LibMap::iterator i = lib_map.begin(); i != lib_map.end(); ++i )
+    {
+    if( dep_map.find( i->first ) == dep_map.end() )
+      {
+      LinkLine::iterator pos = std::find( lib_order.begin(), lib_order.end(), i->first );
+      for( ; pos != lib_order.end(); ++pos )
+        {
+        std::set<std::string> visited;
+        if( !DependsOn( *pos, i->first, dep_map, visited ) )
+          {
+          dep_map_implicit[ i->first ].insert( *pos );
+          }
+        }
+      dep_map_implicit[ i->first ].erase( i->first ); // cannot depend on itself
+      }
+    }
+
+  // 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;
+	}
+
+  // Create a new link line order.
+  std::set<std::string> done, visited;
+  std::vector<std::string> link_line;
+  for( LibMap::iterator i = lib_map.begin(); i != lib_map.end(); ++i )
+    {
+    Emit( i->first, dep_map, done, visited, link_line );
+    }
+
+
+  // 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);
+
+  m_LinkLibraries.clear();
+  for( std::vector<std::string>::reverse_iterator i = link_line.rbegin();
+       i != link_line.rend(); ++i )
+    {
+    // 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. For these libraries, we assume the GENERAL type and
+    // add the name of the library.
+    if( lib_map.find(*i) == lib_map.end() )
+      {
+      if( addLibDirs )
+        {
+        const char* libpath = mf.GetDefinition( i->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);
+            }
+          }
+        }
+      m_LinkLibraries.push_back( std::make_pair(*i,GENERAL) );
+      }
+    else
+      {
+      m_LinkLibraries.push_back( lib_map[ *i ] );
+      }
+    }
+}
+
+
+
+std::string cmTarget::CanonicalLibraryName( const std::string& lib ) const
+{
+  cmRegularExpression reg("((^[ \t]*\\-l)|(^[ \t]*\\-framework[ \t]*))(.+)");
+  if(lib.find('/') != std::string::npos
+     && !reg.find(lib))
+    {
+    std::string dir, file;
+    cmSystemTools::SplitProgramPath(lib.c_str(),
+                                      dir, file);
+    cmRegularExpression libname("lib(.*)(\\.so|\\.sl|\\.a|\\.dylib).*");
+    cmRegularExpression libname_noprefix("(.*)(\\.so|\\.sl|\\.a|\\.dylib|\\.lib).*");
+    if(libname.find(file))
+      {
+      return libname.match(1);
+      }
+    else if(libname_noprefix.find(file))
+      {
+      return libname_noprefix.match(1);
+      }
+	else
+	  {
+	  return file;
+	  }
+    }
+  else
+    {
+    if(!reg.find(lib))
+      {
+      return lib;
+      }
+    else
+      {
+      return reg.match(4);
+      }
+    }
+}
+
+
+void cmTarget::Emit( const std::string& lib,
+                     const DependencyMap& dep_map,
+                     std::set<std::string>& emitted,
+                     std::set<std::string>& visited,
+                     std::vector<std::string>& link_line ) const
+{
+  // It's already been emitted
+  if( emitted.find(lib) != emitted.end() )
+    return;
+
+  // If this library hasn't been visited before, then emit all its
+  // dependencies before emitting the library itself. If it has been
+  // visited before, then there is a dependency cycle. Just emit the
+  // library itself, and let the recursion that got us here deal with
+  // emitting the dependencies for the library.
+
+  if( visited.insert(lib).second )
+    {
+    if( dep_map.find(lib) != dep_map.end() ) // does it have dependencies?
+      {
+      const std::set<std::string>& dep_on = dep_map.find( lib )->second;
+      std::set<std::string>::const_iterator i;
+      for( i = dep_on.begin(); i != dep_on.end(); ++i )
+        {
+        Emit( *i, dep_map, emitted, visited, link_line );
+        }
+      }
+    }
+  link_line.push_back( lib );
+  emitted.insert(lib);
+}
+
+
+void cmTarget::GatherDependencies( const cmMakefile& mf,
+                                   const std::string& lib,
+                                   DependencyMap& dep_map ) const
+{
+  // If the library is already in the dependency map, then it has
+  // already been fully processed.
+  if( dep_map.find(lib) != dep_map.end() )
+    return;
+
+  const char* deps = mf.GetDefinition( (lib+"_LIB_DEPENDS").c_str() );
+  if( deps )
+    {
+    // Make sure this library is in the map, even if it has an empty
+    // set of dependencies. This distinguishes the case of explicitly
+    // no dependencies with that of unspecified dependencies.
+    dep_map[lib];
+
+    // Parse the dependency information, which is simply a set of
+    // libraries separated by ";". There is always a trailing ";".
+    std::string depline = deps;
+    std::string::size_type start = 0;
+    std::string::size_type end;
+    end = depline.find( ";", start );
+    while( end != std::string::npos )
+      {
+      std::string l = depline.substr( start, end-start );
+      if( l.size() != 0 )
+        {
+        const std::string cname = CanonicalLibraryName(l);
+        dep_map[ lib ].insert( cname );
+        GatherDependencies( mf, cname, dep_map );
+        }
+      start = end+1; // skip the ;
+      end = depline.find( ";", start );
+      }
+    dep_map[lib].erase(lib); // cannot depend on itself
+    }
+}
+
+
+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 ) )
+        return true;
+    }
+
+  return false;
+}
diff --git a/Source/cmTarget.h b/Source/cmTarget.h
index 255e1a5..6abdab2 100644
--- a/Source/cmTarget.h
+++ b/Source/cmTarget.h
@@ -79,7 +79,8 @@ public:
   enum LinkLibraryType {GENERAL, DEBUG, OPTIMIZED};
   typedef std::vector<std::pair<std::string,LinkLibraryType> > LinkLibraries;
   const LinkLibraries &GetLinkLibraries() const {return m_LinkLibraries;}
-  LinkLibraries &GetLinkLibraries() {return m_LinkLibraries;}
+
+  const std::vector<std::string>& GetLinkDirectories() const {return m_LinkDirectories;}
 
   /**
    * Set the path where this target should be installed. This is relative to
@@ -88,10 +89,22 @@ 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);
+
   /**
    * Merge Link Libraries into this targets current list 
    */
   void MergeLibraries(const LinkLibraries &ll);
+
+  /**
+   * Merge Link Directories into this targets current list 
+   */
+  void MergeDirectories(const std::vector<std::string> &ld);
     
   /**
    * Generate the SourceFilesList from the SourceLists. This should only be
@@ -107,12 +120,59 @@ public:
   ///! Get the utilities used by this target
   std::set<std::string>const& GetUtilities() const { return m_Utilities; }
 
+  void AnalyzeLibDependencies( const cmMakefile& mf );
+
+private:
+  /**
+   * This map holds the dependency graph. map[x] returns a set of
+   * direct dependencies of x.
+   */
+  typedef std::map< std::string, std::set< std::string > > DependencyMap;
+
+  /**
+   * For each library in the link line, return a canonical name. The
+   * orginal library names have complicated forms, such as "x",
+   * "libx.so", "/full/path/libx.a", "-lx", and "-framework x".
+   */
+  std::string CanonicalLibraryName( const std::string& lib ) const;
+
+  /**
+   * Emits the library \param lib and all its dependencies into
+   * link_line.  \param emitted keeps track of the libraries that have
+   * been emitted to avoid duplicates--it is more efficient than
+   * searching link_line. \param visited is used detect cycles. Note
+   * that \param link_line is in reverse order, in that the
+   * dependencies of a library are listed before the library itself.
+   */
+  void Emit( const std::string& lib,
+             const DependencyMap& dep_map,
+             std::set<std::string>& emitted,
+             std::set<std::string>& visited,
+             std::vector<std::string>& link_line ) const;
+
+  /**
+   * Finds the explicit dependencies for \param lib, if they have been
+   * specified, and inserts them into \param dep_map.
+   */
+  void GatherDependencies( const cmMakefile& mf, const std::string& lib,
+                           DependencyMap& dep_map ) const;
+
+  /**
+   * Returns true if lib1 depends on lib2 according to \param
+   * dep_map. \param visited is used to prevent infinite loops when
+   * cycles are present.
+   */
+  bool DependsOn( const std::string& lib1, const std::string& lib2,
+                  const DependencyMap& dep_map,
+                  std::set<std::string>& visited ) const;
+
 private:
   std::vector<cmCustomCommand> m_CustomCommands;
   std::vector<std::string> m_SourceLists;
   TargetType m_TargetType;
   std::vector<cmSourceFile*> m_SourceFiles;
   LinkLibraries m_LinkLibraries;
+  std::vector<std::string> m_LinkDirectories;
   bool m_InAll;
   std::string m_InstallPath;
   std::set<std::string> m_Utilities;
diff --git a/Source/cmUnixMakefileGenerator.cxx b/Source/cmUnixMakefileGenerator.cxx
index 125f5c1..9a31a20 100644
--- a/Source/cmUnixMakefileGenerator.cxx
+++ b/Source/cmUnixMakefileGenerator.cxx
@@ -480,8 +480,8 @@ void cmUnixMakefileGenerator::OutputLinkLibraries(std::ostream& fout,
 
   // collect all the flags needed for linking libraries
   std::string linkLibs;
-  std::vector<std::string>& libdirs = m_Makefile->GetLinkDirectories();
-  for(std::vector<std::string>::iterator libDir = libdirs.begin();
+  const std::vector<std::string>& libdirs = tgt.GetLinkDirectories();
+  for(std::vector<std::string>::const_iterator libDir = libdirs.begin();
       libDir != libdirs.end(); ++libDir)
     { 
     std::string libpath = this->ConvertToOutputPath(libDir->c_str());
@@ -564,11 +564,6 @@ void cmUnixMakefileGenerator::OutputLinkLibraries(std::ostream& fout,
 
   linkLibs += librariesLinked;
 
-  if(!targetLibrary)
-    {
-    // For executables, add these a second time so order does not matter
-    linkLibs += librariesLinked;
-    }
   fout << linkLibs;
 
   if(outputRuntime && runtimeDirs.size()>0)
diff --git a/Tests/Dependency/CMakeLists.txt b/Tests/Dependency/CMakeLists.txt
new file mode 100644
index 0000000..81365d1
--- /dev/null
+++ b/Tests/Dependency/CMakeLists.txt
@@ -0,0 +1,38 @@
+PROJECT( Dependency )
+
+SET( LIBRARY_OUTPUT_PATH ${Dependency_BINARY_DIR}/Lib )
+SET( CMAKE_ANALYZE_LIB_DEPENDS "ON" )
+
+# There is one executable that depends on eight libraries. The
+# system has the following dependency graph:
+#
+#                    +----------- NoDepC  <----  EXECUTABLE
+#                    |                            |    |
+#                    V                            |    |
+#                                                 |    |
+#                  NoDepA  <----- NoDepB  <-------+    |
+#                                                      |
+#                    ^                                 |
+#                    |                                 |
+#      One  <------ Four ----->  Two  <----- Five  <---+
+#                                 |
+#       ^            ^            |
+#       |            |            |
+#       +--------- Three  <-------+
+#
+# NoDepA:
+# NoDepB: NoDepA
+# NoDepC: NoDepA
+# One:
+# Two: Three
+# Three: One Four
+# Four: One Two A
+# Five: Two
+# Exec: NoDepB NoDepC Five
+#
+# The libraries One,...,Five have their dependencies explicitly
+# encoded. The libraries NoDepA,...,NoDepC do not.
+
+SUBDIRS( NoDepA NoDepB NoDepC )
+SUBDIRS( One Two Three Four Five )
+SUBDIRS( Exec )
diff --git a/Tests/Dependency/Exec/CMakeLists.txt b/Tests/Dependency/Exec/CMakeLists.txt
new file mode 100644
index 0000000..7214b05
--- /dev/null
+++ b/Tests/Dependency/Exec/CMakeLists.txt
@@ -0,0 +1,6 @@
+ADD_EXECUTABLE( exec ExecMain.c )
+
+# This executable directly depends on NoDepB, NoDepC and Five. However,
+# since NoDepB and NoDepC do not have explicit dependency information,
+# and they depend on NoDepA, we have to manually specify that dependency.
+LINK_LIBRARIES( NoDepB NoDepC NoDepA Five )
diff --git a/Tests/Dependency/Exec/ExecMain.c b/Tests/Dependency/Exec/ExecMain.c
new file mode 100644
index 0000000..b666a24
--- /dev/null
+++ b/Tests/Dependency/Exec/ExecMain.c
@@ -0,0 +1,16 @@
+#include <stdio.h>
+
+void NoDepBFunction();
+void NoDepCFunction();
+void FiveFunction();
+
+int main( )
+{
+  FiveFunction();
+  NoDepBFunction();
+  NoDepCFunction();
+
+  printf("Dependency test executable ran successfully.\n");
+
+  return 0;
+}
diff --git a/Tests/Dependency/Five/CMakeLists.txt b/Tests/Dependency/Five/CMakeLists.txt
new file mode 100644
index 0000000..27f6a1f
--- /dev/null
+++ b/Tests/Dependency/Five/CMakeLists.txt
@@ -0,0 +1,3 @@
+ADD_LIBRARY( Five FiveSrc.c )
+TARGET_LINK_LIBRARIES( Five Two )
+
diff --git a/Tests/Dependency/Five/FiveSrc.c b/Tests/Dependency/Five/FiveSrc.c
new file mode 100644
index 0000000..33d8ad7
--- /dev/null
+++ b/Tests/Dependency/Five/FiveSrc.c
@@ -0,0 +1,6 @@
+void TwoFunction();
+
+void FiveFunction()
+{
+  TwoFunction();
+}
diff --git a/Tests/Dependency/Four/CMakeLists.txt b/Tests/Dependency/Four/CMakeLists.txt
new file mode 100644
index 0000000..ba3711f
--- /dev/null
+++ b/Tests/Dependency/Four/CMakeLists.txt
@@ -0,0 +1,3 @@
+ADD_LIBRARY( Four FourSrc.c )
+TARGET_LINK_LIBRARIES( Four One Two NoDepA )
+
diff --git a/Tests/Dependency/Four/FourSrc.c b/Tests/Dependency/Four/FourSrc.c
new file mode 100644
index 0000000..e8fefcd
--- /dev/null
+++ b/Tests/Dependency/Four/FourSrc.c
@@ -0,0 +1,14 @@
+void NoDepAFunction();
+void OneFunction();
+void TwoFunction();
+
+void FourFunction()
+{
+  static int count = 0;
+  if( count == 0 ) {
+    ++count;
+    TwoFunction();
+  }
+  OneFunction();
+  NoDepAFunction();
+}
diff --git a/Tests/Dependency/NoDepA/CMakeLists.txt b/Tests/Dependency/NoDepA/CMakeLists.txt
new file mode 100644
index 0000000..cedf185
--- /dev/null
+++ b/Tests/Dependency/NoDepA/CMakeLists.txt
@@ -0,0 +1 @@
+ADD_LIBRARY( NoDepA NoDepASrc.c )
diff --git a/Tests/Dependency/NoDepA/NoDepASrc.c b/Tests/Dependency/NoDepA/NoDepASrc.c
new file mode 100644
index 0000000..8c4072b
--- /dev/null
+++ b/Tests/Dependency/NoDepA/NoDepASrc.c
@@ -0,0 +1,3 @@
+void NoDepAFunction()
+{
+}
diff --git a/Tests/Dependency/NoDepB/CMakeLists.txt b/Tests/Dependency/NoDepB/CMakeLists.txt
new file mode 100644
index 0000000..0d69f68
--- /dev/null
+++ b/Tests/Dependency/NoDepB/CMakeLists.txt
@@ -0,0 +1,3 @@
+ADD_LIBRARY( NoDepB NoDepBSrc.c )
+# This library depends on NoDepA, but the
+# dependency is not explicitly specified.
diff --git a/Tests/Dependency/NoDepB/NoDepBSrc.c b/Tests/Dependency/NoDepB/NoDepBSrc.c
new file mode 100644
index 0000000..ddc71c5
--- /dev/null
+++ b/Tests/Dependency/NoDepB/NoDepBSrc.c
@@ -0,0 +1,6 @@
+void NoDepAFunction();
+
+void NoDepBFunction()
+{
+  NoDepAFunction();
+}
diff --git a/Tests/Dependency/NoDepC/CMakeLists.txt b/Tests/Dependency/NoDepC/CMakeLists.txt
new file mode 100644
index 0000000..88b29ba
--- /dev/null
+++ b/Tests/Dependency/NoDepC/CMakeLists.txt
@@ -0,0 +1,3 @@
+ADD_LIBRARY( NoDepC NoDepCSrc.c )
+# This library depends on NoDepA, but the
+# dependency is not explicitly specified.
diff --git a/Tests/Dependency/NoDepC/NoDepCSrc.c b/Tests/Dependency/NoDepC/NoDepCSrc.c
new file mode 100644
index 0000000..b478c59
--- /dev/null
+++ b/Tests/Dependency/NoDepC/NoDepCSrc.c
@@ -0,0 +1,6 @@
+void NoDepAFunction();
+
+void NoDepCFunction()
+{
+  NoDepAFunction();
+}
diff --git a/Tests/Dependency/One/CMakeLists.txt b/Tests/Dependency/One/CMakeLists.txt
new file mode 100644
index 0000000..b50b2e9
--- /dev/null
+++ b/Tests/Dependency/One/CMakeLists.txt
@@ -0,0 +1,3 @@
+ADD_LIBRARY( One OneSrc.c )
+# This library has no dependencies
+TARGET_LINK_LIBRARIES( One "" )
diff --git a/Tests/Dependency/One/OneSrc.c b/Tests/Dependency/One/OneSrc.c
new file mode 100644
index 0000000..9801c25
--- /dev/null
+++ b/Tests/Dependency/One/OneSrc.c
@@ -0,0 +1,3 @@
+void OneFunction()
+{
+}
diff --git a/Tests/Dependency/Three/CMakeLists.txt b/Tests/Dependency/Three/CMakeLists.txt
new file mode 100644
index 0000000..6b20dcb
--- /dev/null
+++ b/Tests/Dependency/Three/CMakeLists.txt
@@ -0,0 +1,3 @@
+ADD_LIBRARY( Three ThreeSrc.c )
+TARGET_LINK_LIBRARIES( Three One Four )
+
diff --git a/Tests/Dependency/Three/ThreeSrc.c b/Tests/Dependency/Three/ThreeSrc.c
new file mode 100644
index 0000000..9c77f17
--- /dev/null
+++ b/Tests/Dependency/Three/ThreeSrc.c
@@ -0,0 +1,12 @@
+void OneFunction();
+void FourFunction();
+
+void ThreeFunction()
+{
+  static int count = 0;
+  if( count == 0 ) {
+    ++count;
+    FourFunction();
+  }
+  OneFunction();
+}
diff --git a/Tests/Dependency/Two/CMakeLists.txt b/Tests/Dependency/Two/CMakeLists.txt
new file mode 100644
index 0000000..6a9630e
--- /dev/null
+++ b/Tests/Dependency/Two/CMakeLists.txt
@@ -0,0 +1,3 @@
+ADD_LIBRARY( Two TwoSrc.c )
+TARGET_LINK_LIBRARIES( Two Three )
+
diff --git a/Tests/Dependency/Two/TwoSrc.c b/Tests/Dependency/Two/TwoSrc.c
new file mode 100644
index 0000000..981df09
--- /dev/null
+++ b/Tests/Dependency/Two/TwoSrc.c
@@ -0,0 +1,10 @@
+void ThreeFunction();
+
+void TwoFunction()
+{
+  static int count = 0;
+  if( count == 0 ) {
+    ++count;
+    ThreeFunction();
+  }
+}