Source/cmComputeLinkDepends.h

   1 /*=========================================================================
   2
   3   Program:   CMake - Cross-Platform Makefile Generator
   4   Module:    $RCSfile: cmComputeLinkDepends.h,v $
   5   Language:  C++
   6   Date:      $Date: 2009-04-06 15:10:37 $
   7   Version:   $Revision: 1.16 $
   8
   9   Copyright (c) 2002 Kitware, Inc., Insight Consortium.  All rights reserved.
  10   See Copyright.txt or http://www.cmake.org/HTML/Copyright.html for details.
  11
  12      This software is distributed WITHOUT ANY WARRANTY; without even
  13      the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  14      PURPOSE.  See the above copyright notices for more information.
  15
  16 =========================================================================*/
  17 #ifndef cmComputeLinkDepends_h
  18 #define cmComputeLinkDepends_h
  19
  20 #include "cmStandardIncludes.h"
  21 #include "cmTarget.h"
  22
  23 #include "cmGraphAdjacencyList.h"
  24
  25 #include <queue>
  26
  27 class cmComputeComponentGraph;
  28 class cmGlobalGenerator;
  29 class cmLocalGenerator;
  30 class cmMakefile;
  31 class cmTarget;
  32 class cmake;
  33
  34 /** \class cmComputeLinkDepends
  35  * \brief Compute link dependencies for targets.
  36  */
  37 class cmComputeLinkDepends
  38 {
  39 public:
  40   cmComputeLinkDepends(cmTarget* target, const char* config);
  41   ~cmComputeLinkDepends();
  42
  43   // Basic information about each link item.
  44   struct LinkEntry
  45   {
  46     std::string Item;
  47     cmTarget* Target;
  48     bool IsSharedDep;
  49     bool IsFlag;
  50     LinkEntry(): Item(), Target(0), IsSharedDep(false), IsFlag(false) {}
  51     LinkEntry(LinkEntry const& r):
  52       Item(r.Item), Target(r.Target), IsSharedDep(r.IsSharedDep),
  53       IsFlag(r.IsFlag) {}
  54   };
  55
  56   typedef std::vector<LinkEntry> EntryVector;
  57   EntryVector const& Compute();
  58
  59   void SetOldLinkDirMode(bool b);
  60   std::set<cmTarget*> const& GetOldWrongConfigItems() const
  61     { return this->OldWrongConfigItems; }
  62
  63 private:
  64
  65   // Context information.
  66   cmTarget* Target;
  67   cmMakefile* Makefile;
  68   cmLocalGenerator* LocalGenerator;
  69   cmGlobalGenerator* GlobalGenerator;
  70   cmake* CMakeInstance;
  71   bool DebugMode;
  72
  73   // Configuration information.
  74   const char* Config;
  75   cmTarget::LinkLibraryType LinkType;
  76
  77   // Output information.
  78   EntryVector FinalLinkEntries;
  79
  80   typedef cmTarget::LinkLibraryVectorType LinkLibraryVectorType;
  81
  82   std::map<cmStdString, int>::iterator
  83   AllocateLinkEntry(std::string const& item);
  84   int AddLinkEntry(int depender_index, std::string const& item);
  85   void AddVarLinkEntries(int depender_index, const char* value);
  86   void AddTargetLinkEntries(int depender_index,
  87                             LinkLibraryVectorType const& libs);
  88   void AddLinkEntries(int depender_index,
  89                       std::vector<std::string> const& libs);
  90   std::string CleanItemName(std::string const& item);
  91   cmTarget* FindTargetToLink(int depender_index, const char* name);
  92
  93   // One entry for each unique item.
  94   std::vector<LinkEntry> EntryList;
  95   std::map<cmStdString, int> LinkEntryIndex;
  96
  97   // BFS of initial dependencies.
  98   struct BFSEntry
  99   {
 100     int Index;
 101     const char* LibDepends;
 102   };
 103   std::queue<BFSEntry> BFSQueue;
 104   void FollowLinkEntry(BFSEntry const&);
 105
 106   // Shared libraries that are included only because they are
 107   // dependencies of other shared libraries, not because they are part
 108   // of the interface.
 109   struct SharedDepEntry
 110   {
 111     std::string Item;
 112     int DependerIndex;
 113   };
 114   std::queue<SharedDepEntry> SharedDepQueue;
 115   void QueueSharedDependencies(int depender_index,
 116                                std::vector<std::string> const& deps);
 117   void HandleSharedDependency(SharedDepEntry const& dep);
 118
 119   // Dependency inferral for each link item.
 120   struct DependSet: public std::set<int> {};
 121   struct DependSetList: public std::vector<DependSet> {};
 122   std::vector<DependSetList*> InferredDependSets;
 123   void InferDependencies();
 124
 125   // Ordering constraint graph adjacency list.
 126   typedef cmGraphNodeList NodeList;
 127   typedef cmGraphAdjacencyList Graph;
 128   Graph EntryConstraintGraph;
 129   void CleanConstraintGraph();
 130   void DisplayConstraintGraph();
 131
 132   // Ordering algorithm.
 133   void OrderLinkEntires();
 134   std::vector<char> ComponentVisited;
 135   std::vector<int> ComponentOrder;
 136   int ComponentOrderId;
 137   struct PendingComponent
 138   {
 139     // The real component id.  Needed because the map is indexed by
 140     // component topological index.
 141     int Id;
 142
 143     // The number of times the component needs to be seen.  This is
 144     // always 1 for trivial components and is initially 2 for
 145     // non-trivial components.
 146     int Count;
 147
 148     // The entries yet to be seen to complete the component.
 149     std::set<int> Entries;
 150   };
 151   std::map<int, PendingComponent> PendingComponents;
 152   cmComputeComponentGraph* CCG;
 153   std::vector<int> FinalLinkOrder;
 154   void DisplayComponents();
 155   void VisitComponent(unsigned int c);
 156   void VisitEntry(int index);
 157   PendingComponent& MakePendingComponent(unsigned int component);
 158   void DisplayFinalEntries();
 159
 160   // Record of the original link line.
 161   std::vector<int> OriginalEntries;
 162
 163   // Compatibility help.
 164   bool OldLinkDirMode;
 165   void CheckWrongConfigItem(int depender_index, std::string const& item);
 166   std::set<cmTarget*> OldWrongConfigItems;
 167 };
 168
 169 #endif