Source/cmComputeLinkDepends.h

   1 /* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
   2    file Copyright.txt or https://cmake.org/licensing for details.  */
   3 #pragma once
   4
   5 #include "cmConfigure.h" // IWYU pragma: keep
   6
   7 #include <map>
   8 #include <memory>
   9 #include <queue>
  10 #include <set>
  11 #include <string>
  12 #include <utility>
  13 #include <vector>
  14
  15 #include "cmGraphAdjacencyList.h"
  16 #include "cmLinkItem.h"
  17 #include "cmListFileCache.h"
  18 #include "cmTargetLinkLibraryType.h"
  19
  20 class cmComputeComponentGraph;
  21 class cmGeneratorTarget;
  22 class cmGlobalGenerator;
  23 class cmMakefile;
  24 class cmake;
  25
  26 /** \class cmComputeLinkDepends
  27  * \brief Compute link dependencies for targets.
  28  */
  29 class cmComputeLinkDepends
  30 {
  31 public:
  32   cmComputeLinkDepends(cmGeneratorTarget const* target,
  33                        const std::string& config,
  34                        const std::string& linkLanguage);
  35   ~cmComputeLinkDepends();
  36
  37   cmComputeLinkDepends(const cmComputeLinkDepends&) = delete;
  38   cmComputeLinkDepends& operator=(const cmComputeLinkDepends&) = delete;
  39
  40   // Basic information about each link item.
  41   struct LinkEntry
  42   {
  43     LinkEntry() = default;
  44     LinkEntry(BT<std::string> item, cmGeneratorTarget const* target = nullptr)
  45       : Item(std::move(item))
  46       , Target(target)
  47     {
  48     }
  49
  50     static const std::string DEFAULT;
  51
  52     enum EntryKind
  53     {
  54       Library,
  55       Object,
  56       SharedDep,
  57       Flag,
  58       // The following member is for the management of items specified
  59       // through genex $<LINK_GROUP:...>
  60       Group
  61     };
  62
  63     BT<std::string> Item;
  64     cmGeneratorTarget const* Target = nullptr;
  65     EntryKind Kind = Library;
  66     // The following member is for the management of items specified
  67     // through genex $<LINK_LIBRARY:...>
  68     std::string Feature = std::string(DEFAULT);
  69   };
  70
  71   using EntryVector = std::vector<LinkEntry>;
  72   EntryVector const& Compute();
  73
  74   void SetOldLinkDirMode(bool b);
  75   std::set<cmGeneratorTarget const*> const& GetOldWrongConfigItems() const
  76   {
  77     return this->OldWrongConfigItems;
  78   }
  79
  80 private:
  81   // Context information.
  82   cmGeneratorTarget const* Target;
  83   cmMakefile* Makefile;
  84   cmGlobalGenerator const* GlobalGenerator;
  85   cmake* CMakeInstance;
  86   std::string LinkLanguage;
  87   std::string Config;
  88   EntryVector FinalLinkEntries;
  89   std::map<std::string, std::string> LinkLibraryOverride;
  90
  91   std::string const& GetCurrentFeature(
  92     std::string const& item, std::string const& defaultFeature) const;
  93
  94   std::pair<std::map<cmLinkItem, int>::iterator, bool> AllocateLinkEntry(
  95     cmLinkItem const& item);
  96   std::pair<int, bool> AddLinkEntry(cmLinkItem const& item,
  97                                     int groupIndex = -1);
  98   void AddLinkObject(cmLinkItem const& item);
  99   void AddVarLinkEntries(int depender_index, const char* value);
 100   void AddDirectLinkEntries();
 101   template <typename T>
 102   void AddLinkEntries(int depender_index, std::vector<T> const& libs);
 103   void AddLinkObjects(std::vector<cmLinkItem> const& objs);
 104   cmLinkItem ResolveLinkItem(int depender_index, const std::string& name);
 105
 106   // One entry for each unique item.
 107   std::vector<LinkEntry> EntryList;
 108   std::map<cmLinkItem, int> LinkEntryIndex;
 109
 110   // map storing, for each group, the list of items
 111   std::map<int, std::vector<int>> GroupItems;
 112
 113   // BFS of initial dependencies.
 114   struct BFSEntry
 115   {
 116     int Index;
 117     int GroupIndex;
 118     const char* LibDepends;
 119   };
 120   std::queue<BFSEntry> BFSQueue;
 121   void FollowLinkEntry(BFSEntry qe);
 122
 123   // Shared libraries that are included only because they are
 124   // dependencies of other shared libraries, not because they are part
 125   // of the interface.
 126   struct SharedDepEntry
 127   {
 128     cmLinkItem Item;
 129     int DependerIndex;
 130   };
 131   std::queue<SharedDepEntry> SharedDepQueue;
 132   std::set<int> SharedDepFollowed;
 133   void FollowSharedDeps(int depender_index, cmLinkInterface const* iface,
 134                         bool follow_interface = false);
 135   void QueueSharedDependencies(int depender_index,
 136                                std::vector<cmLinkItem> const& deps);
 137   void HandleSharedDependency(SharedDepEntry const& dep);
 138
 139   // Dependency inferral for each link item.
 140   struct DependSet : public std::set<int>
 141   {
 142   };
 143   struct DependSetList : public std::vector<DependSet>
 144   {
 145     bool Initialized = false;
 146   };
 147   std::vector<DependSetList> InferredDependSets;
 148   void InferDependencies();
 149
 150   // To finalize dependencies over groups in place of raw items
 151   void UpdateGroupDependencies();
 152
 153   // Ordering constraint graph adjacency list.
 154   using NodeList = cmGraphNodeList;
 155   using EdgeList = cmGraphEdgeList;
 156   using Graph = cmGraphAdjacencyList;
 157   Graph EntryConstraintGraph;
 158   void CleanConstraintGraph();
 159   bool CheckCircularDependencies() const;
 160   void DisplayConstraintGraph();
 161
 162   // Ordering algorithm.
 163   void OrderLinkEntries();
 164   std::vector<char> ComponentVisited;
 165   std::vector<int> ComponentOrder;
 166
 167   struct PendingComponent
 168   {
 169     // The real component id.  Needed because the map is indexed by
 170     // component topological index.
 171     int Id;
 172
 173     // The number of times the component needs to be seen.  This is
 174     // always 1 for trivial components and is initially 2 for
 175     // non-trivial components.
 176     int Count;
 177
 178     // The entries yet to be seen to complete the component.
 179     std::set<int> Entries;
 180   };
 181   std::map<int, PendingComponent> PendingComponents;
 182   std::unique_ptr<cmComputeComponentGraph> CCG;
 183   std::vector<int> FinalLinkOrder;
 184   void DisplayComponents();
 185   void VisitComponent(unsigned int c);
 186   void VisitEntry(int index);
 187   PendingComponent& MakePendingComponent(unsigned int component);
 188   int ComputeComponentCount(NodeList const& nl);
 189   void DisplayFinalEntries();
 190
 191   // Record of the original link line.
 192   std::vector<int> OriginalEntries;
 193   std::set<cmGeneratorTarget const*> OldWrongConfigItems;
 194   void CheckWrongConfigItem(cmLinkItem const& item);
 195
 196   // Record of explicitly linked object files.
 197   std::vector<int> ObjectEntries;
 198
 199   int ComponentOrderId;
 200   cmTargetLinkLibraryType LinkType;
 201   bool HasConfig;
 202   bool DebugMode;
 203   bool OldLinkDirMode;
 204 };