Source/cmComputeLinkDepends.h

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