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, cmTarget *head);
  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   cmTarget* HeadTarget;
  63   cmMakefile* Makefile;
  64   cmLocalGenerator* LocalGenerator;
  65   cmGlobalGenerator* GlobalGenerator;
  66   cmake* CMakeInstance;
  67   bool DebugMode;
  68
  69   // Configuration information.
  70   const char* Config;
  71   cmTarget::LinkLibraryType LinkType;
  72
  73   // Output information.
  74   EntryVector FinalLinkEntries;
  75
  76   typedef cmTarget::LinkLibraryVectorType LinkLibraryVectorType;
  77
  78   std::map<cmStdString, int>::iterator
  79   AllocateLinkEntry(std::string const& item);
  80   int AddLinkEntry(int depender_index, std::string const& item);
  81   void AddVarLinkEntries(int depender_index, const char* value);
  82   void AddDirectLinkEntries();
  83   void AddLinkEntries(int depender_index,
  84                       std::vector<std::string> const& libs);
  85   cmTarget* FindTargetToLink(int depender_index, const char* name);
  86
  87   // One entry for each unique item.
  88   std::vector<LinkEntry> EntryList;
  89   std::map<cmStdString, int> LinkEntryIndex;
  90
  91   // BFS of initial dependencies.
  92   struct BFSEntry
  93   {
  94     int Index;
  95     const char* LibDepends;
  96   };
  97   std::queue<BFSEntry> BFSQueue;
  98   void FollowLinkEntry(BFSEntry const&);
  99
 100   // Shared libraries that are included only because they are
 101   // dependencies of other shared libraries, not because they are part
 102   // of the interface.
 103   struct SharedDepEntry
 104   {
 105     std::string Item;
 106     int DependerIndex;
 107   };
 108   std::queue<SharedDepEntry> SharedDepQueue;
 109   std::set<int> SharedDepFollowed;
 110   void FollowSharedDeps(int depender_index,
 111                         cmTarget::LinkInterface const* iface,
 112                         bool follow_interface = false);
 113   void QueueSharedDependencies(int depender_index,
 114                                std::vector<std::string> const& deps);
 115   void HandleSharedDependency(SharedDepEntry const& dep);
 116
 117   // Dependency inferral for each link item.
 118   struct DependSet: public std::set<int> {};
 119   struct DependSetList: public std::vector<DependSet> {};
 120   std::vector<DependSetList*> InferredDependSets;
 121   void InferDependencies();
 122
 123   // Ordering constraint graph adjacency list.
 124   typedef cmGraphNodeList NodeList;
 125   typedef cmGraphEdgeList EdgeList;
 126   typedef cmGraphAdjacencyList Graph;
 127   Graph EntryConstraintGraph;
 128   void CleanConstraintGraph();
 129   void DisplayConstraintGraph();
 130
 131   // Ordering algorithm.
 132   void OrderLinkEntires();
 133   std::vector<char> ComponentVisited;
 134   std::vector<int> ComponentOrder;
 135   int ComponentOrderId;
 136   struct PendingComponent
 137   {
 138     // The real component id.  Needed because the map is indexed by
 139     // component topological index.
 140     int Id;
 141
 142     // The number of times the component needs to be seen.  This is
 143     // always 1 for trivial components and is initially 2 for
 144     // non-trivial components.
 145     int Count;
 146
 147     // The entries yet to be seen to complete the component.
 148     std::set<int> Entries;
 149   };
 150   std::map<int, PendingComponent> PendingComponents;
 151   cmComputeComponentGraph* CCG;
 152   std::vector<int> FinalLinkOrder;
 153   void DisplayComponents();
 154   void VisitComponent(unsigned int c);
 155   void VisitEntry(int index);
 156   PendingComponent& MakePendingComponent(unsigned int component);
 157   int ComputeComponentCount(NodeList const& nl);
 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