/*=========================================================================

  Program:   CMake - Cross-Platform Makefile Generator
  Module:    $RCSfile$
  Language:  C++
  Date:      $Date$
  Version:   $Revision$

  Copyright (c) 2002 Kitware, Inc., Insight Consortium.  All rights reserved.
  See Copyright.txt or http://www.cmake.org/HTML/Copyright.html for details.

     This software is distributed WITHOUT ANY WARRANTY; without even 
     the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
     PURPOSE.  See the above copyright notices for more information.

=========================================================================*/
#include "cmTarget.h"
#include "cmMakefile.h"
#include "cmSourceFile.h"

#include <map>
#include <set>


void cmTarget::SetType(TargetType type)
{
  // only add dependency information for library targets
  m_TargetType = type;
  if(m_TargetType >= STATIC_LIBRARY && m_TargetType <= MODULE_LIBRARY) {
    m_RecordDependencies = true;
  } else {
    m_RecordDependencies = false;
  }
}


void cmTarget::GenerateSourceFilesFromSourceLists( cmMakefile &mf)
{
  // this is only done for non install targets
  if ((this->m_TargetType == cmTarget::INSTALL_FILES)
      || (this->m_TargetType == cmTarget::INSTALL_PROGRAMS))
    {
    return;
    }

  // for each src lists add the classes
  for (std::vector<std::string>::const_iterator s = m_SourceLists.begin();
       s != m_SourceLists.end(); ++s)
    {
    int done = 0;
    // replace any variables
    std::string temps = *s;
    mf.ExpandVariablesInString(temps);

    // Next if one wasn't found then assume it is a single class
    if (!done && mf.GetSource(temps.c_str()))
      {
      m_SourceFiles.push_back(mf.GetSource(temps.c_str()));
      done = 1;
      }

    // if it wasn't a source file listed with the makefile
    // see if it is a variable. This is for old CMake 1.2 compatability 
    // where a source list would be passed into here, by making it
    // a vector we need to possibly lookup the variable to maintain
    // CMake 1.2 compatability.
    const char* versionValue
      = mf.GetDefinition("CMAKE_MINIMUM_REQUIRED_VERSION");
    if (!done)
      {
      if (!versionValue || atof(versionValue) <= 1.2)
        {
        const char* varValue = 
          mf.GetDefinition(temps.c_str());
        // if the definition exists
        if (varValue)
          {
          std::vector<std::string> tval;
          tval.push_back(varValue);
          std::vector<std::string> args;
          cmSystemTools::ExpandListArguments(tval, args);
          unsigned int i;
          for (i = 0; i < args.size(); ++i)
            {
            if (mf.GetSource(args[i].c_str()))
              {
              m_SourceFiles.push_back(mf.GetSource(args[i].c_str()));
              }
            else
              {
              cmSourceFile file;
              file.SetProperty("ABSTRACT","0");
              file.SetName(args[i].c_str(), mf.GetCurrentDirectory(),
                           mf.GetSourceExtensions(),
                           mf.GetHeaderExtensions());
              m_SourceFiles.push_back(mf.AddSource(file));
              }
            }
          done = 1;
          }
        }
      }
      
    // if we still are not done, try to create the SourceFile structure
    if (!done)
      {
      cmSourceFile file;
      file.SetProperty("ABSTRACT","0");
      file.SetName(temps.c_str(), mf.GetCurrentDirectory(),
                   mf.GetSourceExtensions(),
                   mf.GetHeaderExtensions());
      m_SourceFiles.push_back(mf.AddSource(file));
      done = 1;
      }
    }
  
  // expand any link library variables whle we are at it
  LinkLibraries::iterator p = m_LinkLibraries.begin();
  for (;p != m_LinkLibraries.end(); ++p)
    {
    mf.ExpandVariablesInString(p->first);
    }
}


void cmTarget::MergeLinkLibraries( cmMakefile& mf,
                                   const char *selfname,
                                   const LinkLibraries& libs )
{
  // Only add on libraries we haven't added on before.
  // Assumption: the global link libraries could only grow, never shrink
  LinkLibraries::const_iterator i = libs.begin();
  i += m_PrevLinkedLibraries.size();
  for( ; i != libs.end(); ++i )
    {
    // 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)
{
  // 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::ClearDependencyInformation( cmMakefile& mf, const char* target )
{
  // Clear the dependencies. The cache variable must exist iff we are
  // recording dependency information for this target.
  std::string depname = target;
  depname += "_LIB_DEPENDS";
  if (m_RecordDependencies)
    {
    mf.AddCacheDefinition(depname.c_str(), "",
                          "Dependencies for target", cmCacheManager::STATIC);
    }
  else
    {
    if (mf.GetDefinition( depname.c_str() ))
      {
      std::string message = "Target ";
      message += target;
      message += " has dependency information when it shouldn't.\n";
      message += "Your cache is probably stale. Please remove the entry\n  ";
      message += depname;
      message += "\nfrom the cache.";
      cmSystemTools::Error( message.c_str() );  
      }
    }
}



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)
{
  // Never add a self dependency, even if the user asks for it.
  if(strcmp( target, lib ) == 0)
    {
    return;
    }

  m_LinkLibraries.push_back( std::pair<std::string, cmTarget::LinkLibraryType>(lib,llt) );

  if(llt != cmTarget::GENERAL)
    {
    std::string linkTypeName = lib;
    linkTypeName += "_LINK_TYPE";
    switch(llt)
      {
      case cmTarget::DEBUG:
        mf.AddCacheDefinition(linkTypeName.c_str(),
                              "debug", "Library is used for debug links only", 
                              cmCacheManager::STATIC);
        break;
      case cmTarget::OPTIMIZED:
        mf.AddCacheDefinition(linkTypeName.c_str(),
                              "optimized", "Library is used for debug links only", 
                              cmCacheManager::STATIC);
        break;
      case cmTarget::GENERAL: break;
      }
    }
  // 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.
  // We shouldn't remove duplicates here because external libraries
  // may be purposefully duplicated to handle recursive dependencies,
  // and we removing one instance will break the link line. Duplicates
  // will be appropriately eliminated at emit time.
  if(m_RecordDependencies)
    {
    std::string targetEntry = target;
    targetEntry += "_LIB_DEPENDS";
    std::string dependencies;
    const char* old_val = mf.GetDefinition( targetEntry.c_str() );
    if( old_val )
      {
      dependencies += old_val;
      }
    dependencies += lib;
    dependencies += ";";
    mf.AddCacheDefinition( targetEntry.c_str(), dependencies.c_str(),
                           "Dependencies for the target", 
                           cmCacheManager::STATIC );
    }
  
}

bool cmTarget::HasCxx() const
{
  for(std::vector<cmSourceFile*>::const_iterator i =  m_SourceFiles.begin();
      i != m_SourceFiles.end(); ++i)
    {
    if((*i)->GetSourceExtension() != "c" &&
       (*i)->GetSourceExtension() != "h")
      {
      return true;
      }
    }
  return false;
}





void
cmTarget::AnalyzeLibDependencies( const cmMakefile& mf )
{
  // There are two key parts of the dependency analysis: (1)
  // determining the libraries in the link line, and (2) constructing
  // the dependency graph for those libraries.
  //
  // The latter is done using the cache entries that record the
  // dependencies of each library.
  //
  // The former is a more thorny issue, since it is not clear how to
  // determine if two libraries listed on the link line refer to the a
  // single library or not. For example, consider the link "libraries"
  //    /usr/lib/libtiff.so -ltiff 
  // Is this one library or two? The solution implemented here is the
  // simplest (and probably the only practical) one: two libraries are
  // the same if their "link strings" are identical. Thus, the two
  // libraries above are considered distinct. This also means that for
  // dependency analysis to be effective, the CMake user must specify
  // libraries build by his project without using any linker flags or
  // file extensions. That is,
  //    LINK_LIBRARIES( One Two )
  // instead of
  //    LINK_LIBRARIES( -lOne ${binarypath}/libTwo.a )
  // The former is probably what most users would do, but it never
  // 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.
  //
  // There is a problem with recursive external libraries
  // (i.e. libraries with no dependency information that are
  // recursively dependent). We must make sure that the we emit one of
  // the libraries twice to satisfy the recursion, but we shouldn't
  // emit it more times than necessary. In particular, we must make
  // sure that handling this improbable case doesn't cost us when
  // dealing with the common case of non-recursive libraries. The
  // solution is to assume that the recursion is satisfied at one node
  // of the dependency tree. To illustrate, assume libA and libB are
  // extrenal and mutually dependent. Suppose libX depends on
  // libA, and libY on libA and libX. Then
  //   TARGET_LINK_LIBRARIES( Y X A B A )
  //   TARGET_LINK_LIBRARIES( X A B A )
  //   TARGET_LINK_LIBRARIES( Exec Y )
  // would result in "-lY -lX -lA -lB -lA". This is the correct way to
  // specify the dependencies, since the mutual dependency of A and B
  // is resolved *every time libA is specified*.
  //
  // Something like
  //   TARGET_LINK_LIBRARIES( Y X A B A )
  //   TARGET_LINK_LIBRARIES( X A B )
  //   TARGET_LINK_LIBRARIES( Exec Y )
  // would result in "-lY -lX -lA -lB", and the mutual dependency
  // information is lost. This is because in some case (Y), the mutual
  // dependency of A and B is listed, while in another other case (X),
  // it is not. Depending on which line actually emits A, the mutual
  // dependency may or may not be on the final link line.  We can't
  // handle this pathalogical case cleanly without emitting extra
  // libraries for the normal cases. Besides, the dependency
  // information for X is wrong anyway: if we build an executable
  // depending on X alone, we would not have the mutual dependency on
  // A and B resolved.
  //
  // IMPROVEMENTS:
  // -- The current algorithm will not always pick the "optimal" link line
  //    when recursive dependencies are present. It will instead break the
  //    cycles at an aribtrary point. The majority of projects won't have
  //    cyclic dependencies, so this is probably not a big deal. Note that
  //    the link line is always correct, just not necessary optimal.

  typedef std::vector< std::string > LinkLine;

  // The dependency map.
  DependencyMap dep_map;

  // 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);

  // 1. Build the dependency graph
  //
  for(LinkLibraries::reverse_iterator lib = m_LinkLibraries.rbegin();
      lib != m_LinkLibraries.rend(); ++lib)
    {
    this->GatherDependencies( mf, lib->first, dep_map );
    }

  // 2. Remove any dependencies that are already satisfied in the original
  // link line.
  //
  for(LinkLibraries::iterator lib = m_LinkLibraries.begin();
      lib != m_LinkLibraries.end(); ++lib)
    {
    for( LinkLibraries::iterator lib2 = lib;
      lib2 != m_LinkLibraries.end(); ++lib2)
      {
      DeleteDependency( dep_map, lib->first, lib2->first );
      }
    }

  
  // 3. Create the new link line by simply emitting any dependencies that are
  // missing.  Start from the back and keep adding.
  //
  std::set<cmStdString> done, visited;
  std::vector<std::string> newLinkLibraries;
  for(LinkLibraries::reverse_iterator lib = m_LinkLibraries.rbegin();
      lib != m_LinkLibraries.rend(); ++lib)
    {
    // skip zero size library entries, this may happen
    // if a variable expands to nothing.
    if (lib->first.size() != 0)
      {
      Emit( lib->first, dep_map, done, visited, newLinkLibraries );
      }
    }


  // 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 )
      {
      // who the hell knows what this is, I think that K contains the
      // name of a library but ... Ken
      // k contains the same stuff that are on the LINK_LIBRARIES
      // commands. Normally, they would just be library names. -- Amitha.
      std::string libPathStr = *k + "_CMAKE_PATH";
      const char* libpath = mf.GetDefinition( libPathStr.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;
        }
      }
    m_LinkLibraries.push_back( std::make_pair(*k,llt) );
    }
}


void cmTarget::InsertDependency( DependencyMap& depMap,
                                 const cmStdString& lib,
                                 const cmStdString& dep ) const
{
  depMap[lib].push_back(dep);
}

void cmTarget::DeleteDependency( DependencyMap& depMap,
                                 const cmStdString& lib,
                                 const cmStdString& dep ) const
{
  // Make sure there is an entry in the map for lib. If so, delete all
  // dependencies to dep. There may be repeated entries because of
  // external libraries that are specified multiple times.
  DependencyMap::iterator map_itr = depMap.find( lib );
  if( map_itr != depMap.end() )
    {
    DependencyList& depList = map_itr->second;
    DependencyList::iterator itr;
    while( (itr = std::find(depList.begin(), depList.end(), dep)) != depList.end() )
      {
      depList.erase( itr );
      }
    }
}

void cmTarget::Emit( const std::string& lib,
                     const DependencyMap& dep_map,
                     std::set<cmStdString>& emitted,
                     std::set<cmStdString>& visited,
                     std::vector<std::string>& link_line ) const
{
  // It's already been emitted
  if( emitted.find(lib) != emitted.end() )
    return;

  // Emit the dependencies only if this library node hasn't been
  // visited before. If it has, then we have a cycle. The recursion
  // that got us here should take care of everything.

  if( visited.insert(lib).second )
    {
    if( dep_map.find(lib) != dep_map.end() ) // does it have dependencies?
      {
      const DependencyList& dep_on = dep_map.find( lib )->second;
      DependencyList::const_reverse_iterator i;

      // To cater for recursive external libraries, we must emit
      // duplicates on this link line *unless* they were emitted by
      // some other node, in which case we assume that the recursion
      // was resolved then. We making the simplifying assumption that
      // any duplicates on a single link line are on purpose, and must
      // be preserved.

      // This variable will keep track of the libraries that were
      // emitted directory from the current node, and not from a
      // recursive call. This way, if we come across a library that
      // has already been emitted, we repeat it iff it has been
      // emitted here.
      std::set<cmStdString> emitted_here;
      for( i = dep_on.rbegin(); i != dep_on.rend(); ++i )
        {
        if( emitted_here.find(*i) != emitted_here.end() )
          {
          // a repeat. Must emit.
          emitted.insert(*i);
          link_line.push_back( *i );
          }
        else
          {
          // Emit only if no-one else has
          if( emitted.find(*i) == emitted.end() )
            {
            // emit dependencies
            Emit( *i, dep_map, emitted, visited, link_line );
            // emit self
            emitted.insert(*i);
            emitted_here.insert(*i);
            link_line.push_back( *i );
            }
          }
        }
      }
    }
}


void cmTarget::GatherDependencies( const cmMakefile& mf,
                                   const std::string& lib,
                                   DependencyMap& dep_map )
{
  // 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 && strcmp(deps,"") != 0 )
    {
    // 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 )
        {
        InsertDependency( dep_map, lib, l );
        GatherDependencies( mf, l, dep_map );
        }
      start = end+1; // skip the ;
      end = depline.find( ";", start );
      }
    DeleteDependency( dep_map, lib, lib); // cannot depend on itself
    }
}
