Source/cmComputeTargetDepends.cxx

   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 #include "cmComputeTargetDepends.h"
  13
  14 #include "cmComputeComponentGraph.h"
  15 #include "cmGlobalGenerator.h"
  16 #include "cmLocalGenerator.h"
  17 #include "cmMakefile.h"
  18 #include "cmSystemTools.h"
  19 #include "cmTarget.h"
  20 #include "cmake.h"
  21
  22 #include <algorithm>
  23
  24 #include <assert.h>
  25
  26 /*
  27
  28 This class is meant to analyze inter-target dependencies globally
  29 during the generation step.  The goal is to produce a set of direct
  30 dependencies for each target such that no cycles are left and the
  31 build order is safe.
  32
  33 For most target types cyclic dependencies are not allowed.  However
  34 STATIC libraries may depend on each other in a cyclic fashion.  In
  35 general the directed dependency graph forms a directed-acyclic-graph
  36 of strongly connected components.  All strongly connected components
  37 should consist of only STATIC_LIBRARY targets.
  38
  39 In order to safely break dependency cycles we must preserve all other
  40 dependencies passing through the corresponding strongly connected component.
  41 The approach taken by this class is as follows:
  42
  43   - Collect all targets and form the original dependency graph
  44   - Run Tarjan's algorithm to extract the strongly connected components
  45     (error if any member of a non-trivial component is not STATIC)
  46   - The original dependencies imply a DAG on the components.
  47     Use the implied DAG to construct a final safe set of dependencies.
  48
  49 The final dependency set is constructed as follows:
  50
  51   - For each connected component targets are placed in an arbitrary
  52     order.  Each target depends on the target following it in the order.
  53     The first target is designated the head and the last target the tail.
  54     (most components will be just 1 target anyway)
  55
  56   - Original dependencies between targets in different components are
  57     converted to connect the depender's component tail to the
  58     dependee's component head.
  59
  60 In most cases this will reproduce the original dependencies.  However
  61 when there are cycles of static libraries they will be broken in a
  62 safe manner.
  63
  64 For example, consider targets A0, A1, A2, B0, B1, B2, and C with these
  65 dependencies:
  66
  67   A0 -> A1 -> A2 -> A0  ,  B0 -> B1 -> B2 -> B0 -> A0  ,  C -> B0
  68
  69 Components may be identified as
  70
  71   Component 0: A0, A1, A2
  72   Component 1: B0, B1, B2
  73   Component 2: C
  74
  75 Intra-component dependencies are:
  76
  77   0: A0 -> A1 -> A2   , head=A0, tail=A2
  78   1: B0 -> B1 -> B2   , head=B0, tail=B2
  79   2: head=C, tail=C
  80
  81 The inter-component dependencies are converted as:
  82
  83   B0 -> A0  is component 1->0 and becomes  B2 -> A0
  84   C  -> B0  is component 2->1 and becomes  C  -> B0
  85
  86 This leads to the final target dependencies:
  87
  88   C -> B0 -> B1 -> B2 -> A0 -> A1 -> A2
  89
  90 These produce a safe build order since C depends directly or
  91 transitively on all the static libraries it links.
  92
  93 */
  94
  95 //----------------------------------------------------------------------------
  96 cmComputeTargetDepends::cmComputeTargetDepends(cmGlobalGenerator* gg)
  97 {
  98   this->GlobalGenerator = gg;
  99   cmake* cm = this->GlobalGenerator->GetCMakeInstance();
 100   this->DebugMode = cm->GetPropertyAsBool("GLOBAL_DEPENDS_DEBUG_MODE");
 101   this->NoCycles = cm->GetPropertyAsBool("GLOBAL_DEPENDS_NO_CYCLES");
 102 }
 103
 104 //----------------------------------------------------------------------------
 105 cmComputeTargetDepends::~cmComputeTargetDepends()
 106 {
 107 }
 108
 109 //----------------------------------------------------------------------------
 110 bool cmComputeTargetDepends::Compute()
 111 {
 112   // Build the original graph.
 113   this->CollectTargets();
 114   this->CollectDepends();
 115   if(this->DebugMode)
 116     {
 117     this->DisplayGraph(this->InitialGraph, "initial");
 118     }
 119
 120   // Identify components.
 121   cmComputeComponentGraph ccg(this->InitialGraph);
 122   if(this->DebugMode)
 123     {
 124     this->DisplayComponents(ccg);
 125     }
 126   if(!this->CheckComponents(ccg))
 127     {
 128     return false;
 129     }
 130
 131   // Compute the final dependency graph.
 132   if(!this->ComputeFinalDepends(ccg))
 133     {
 134     return false;
 135     }
 136   if(this->DebugMode)
 137     {
 138     this->DisplayGraph(this->FinalGraph, "final");
 139     }
 140
 141   return true;
 142 }
 143
 144 //----------------------------------------------------------------------------
 145 void
 146 cmComputeTargetDepends::GetTargetDirectDepends(cmTarget* t,
 147                                                cmTargetDependSet& deps)
 148 {
 149   // Lookup the index for this target.  All targets should be known by
 150   // this point.
 151   std::map<cmTarget*, int>::const_iterator tii = this->TargetIndex.find(t);
 152   assert(tii != this->TargetIndex.end());
 153   int i = tii->second;
 154
 155   // Get its final dependencies.
 156   EdgeList const& nl = this->FinalGraph[i];
 157   for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
 158     {
 159     cmTarget* dep = this->Targets[*ni];
 160     cmTargetDependSet::iterator di = deps.insert(dep).first;
 161     di->SetType(ni->IsStrong());
 162     }
 163 }
 164
 165 //----------------------------------------------------------------------------
 166 void cmComputeTargetDepends::CollectTargets()
 167 {
 168   // Collect all targets from all generators.
 169   std::vector<cmLocalGenerator*> const& lgens =
 170     this->GlobalGenerator->GetLocalGenerators();
 171   for(unsigned int i = 0; i < lgens.size(); ++i)
 172     {
 173     cmTargets& targets = lgens[i]->GetMakefile()->GetTargets();
 174     for(cmTargets::iterator ti = targets.begin(); ti != targets.end(); ++ti)
 175       {
 176       cmTarget* target = &ti->second;
 177       int index = static_cast<int>(this->Targets.size());
 178       this->TargetIndex[target] = index;
 179       this->Targets.push_back(target);
 180       }
 181     }
 182 }
 183
 184 //----------------------------------------------------------------------------
 185 void cmComputeTargetDepends::CollectDepends()
 186 {
 187   // Allocate the dependency graph adjacency lists.
 188   this->InitialGraph.resize(this->Targets.size());
 189
 190   // Compute each dependency list.
 191   for(unsigned int i=0; i < this->Targets.size(); ++i)
 192     {
 193     this->CollectTargetDepends(i);
 194     }
 195 }
 196
 197 //----------------------------------------------------------------------------
 198 void cmComputeTargetDepends::CollectTargetDepends(int depender_index)
 199 {
 200   // Get the depender.
 201   cmTarget* depender = this->Targets[depender_index];
 202
 203   // Loop over all targets linked directly in all configs.
 204   // We need to make targets depend on the union of all config-specific
 205   // dependencies in all targets, because the generated build-systems can't
 206   // deal with config-specific dependencies.
 207   {
 208   std::set<cmStdString> emitted;
 209   {
 210   std::vector<std::string> tlibs;
 211   depender->GetDirectLinkLibraries(0, tlibs, depender);
 212   // A target should not depend on itself.
 213   emitted.insert(depender->GetName());
 214   for(std::vector<std::string>::const_iterator lib = tlibs.begin();
 215       lib != tlibs.end(); ++lib)
 216     {
 217     // Don't emit the same library twice for this target.
 218     if(emitted.insert(*lib).second)
 219       {
 220       this->AddTargetDepend(depender_index, lib->c_str(), true);
 221       this->AddInterfaceDepends(depender_index, lib->c_str(),
 222                                 true, emitted);
 223       }
 224     }
 225   }
 226   std::vector<std::string> configs;
 227   depender->GetMakefile()->GetConfigurations(configs);
 228   for (std::vector<std::string>::const_iterator it = configs.begin();
 229     it != configs.end(); ++it)
 230     {
 231     std::vector<std::string> tlibs;
 232     depender->GetDirectLinkLibraries(it->c_str(), tlibs, depender);
 233     // A target should not depend on itself.
 234     emitted.insert(depender->GetName());
 235     for(std::vector<std::string>::const_iterator lib = tlibs.begin();
 236         lib != tlibs.end(); ++lib)
 237       {
 238       // Don't emit the same library twice for this target.
 239       if(emitted.insert(*lib).second)
 240         {
 241         this->AddTargetDepend(depender_index, lib->c_str(), true);
 242         this->AddInterfaceDepends(depender_index, lib->c_str(),
 243                                   true, emitted);
 244         }
 245       }
 246     }
 247   }
 248
 249   // Loop over all utility dependencies.
 250   {
 251   std::set<cmStdString> const& tutils = depender->GetUtilities();
 252   std::set<cmStdString> emitted;
 253   // A target should not depend on itself.
 254   emitted.insert(depender->GetName());
 255   for(std::set<cmStdString>::const_iterator util = tutils.begin();
 256       util != tutils.end(); ++util)
 257     {
 258     // Don't emit the same utility twice for this target.
 259     if(emitted.insert(*util).second)
 260       {
 261       this->AddTargetDepend(depender_index, util->c_str(), false);
 262       }
 263     }
 264   }
 265 }
 266
 267 //----------------------------------------------------------------------------
 268 void cmComputeTargetDepends::AddInterfaceDepends(int depender_index,
 269                                                  cmTarget* dependee,
 270                                                  const char *config,
 271                                                std::set<cmStdString> &emitted)
 272 {
 273   cmTarget* depender = this->Targets[depender_index];
 274   if(cmTarget::LinkInterface const* iface =
 275                                 dependee->GetLinkInterface(config, depender))
 276     {
 277     for(std::vector<std::string>::const_iterator
 278         lib = iface->Libraries.begin();
 279         lib != iface->Libraries.end(); ++lib)
 280       {
 281       // Don't emit the same library twice for this target.
 282       if(emitted.insert(*lib).second)
 283         {
 284         this->AddTargetDepend(depender_index, lib->c_str(), true);
 285         this->AddInterfaceDepends(depender_index, lib->c_str(),
 286                                   true, emitted);
 287         }
 288       }
 289     }
 290 }
 291
 292 //----------------------------------------------------------------------------
 293 void cmComputeTargetDepends::AddInterfaceDepends(int depender_index,
 294                                              const char* dependee_name,
 295                                              bool linking,
 296                                              std::set<cmStdString> &emitted)
 297 {
 298   cmTarget* depender = this->Targets[depender_index];
 299   cmTarget* dependee =
 300     depender->GetMakefile()->FindTargetToUse(dependee_name);
 301   // Skip targets that will not really be linked.  This is probably a
 302   // name conflict between an external library and an executable
 303   // within the project.
 304   if(linking && dependee &&
 305      dependee->GetType() == cmTarget::EXECUTABLE &&
 306      !dependee->IsExecutableWithExports())
 307     {
 308     dependee = 0;
 309     }
 310
 311   if(dependee)
 312     {
 313     this->AddInterfaceDepends(depender_index, dependee, 0, emitted);
 314     std::vector<std::string> configs;
 315     depender->GetMakefile()->GetConfigurations(configs);
 316     for (std::vector<std::string>::const_iterator it = configs.begin();
 317       it != configs.end(); ++it)
 318       {
 319       // A target should not depend on itself.
 320       emitted.insert(depender->GetName());
 321       this->AddInterfaceDepends(depender_index, dependee,
 322                                 it->c_str(), emitted);
 323       }
 324     }
 325 }
 326
 327 //----------------------------------------------------------------------------
 328 void cmComputeTargetDepends::AddTargetDepend(int depender_index,
 329                                              const char* dependee_name,
 330                                              bool linking)
 331 {
 332   // Get the depender.
 333   cmTarget* depender = this->Targets[depender_index];
 334
 335   // Check the target's makefile first.
 336   cmTarget* dependee =
 337     depender->GetMakefile()->FindTargetToUse(dependee_name);
 338
 339   // Skip targets that will not really be linked.  This is probably a
 340   // name conflict between an external library and an executable
 341   // within the project.
 342   if(linking && dependee &&
 343      dependee->GetType() == cmTarget::EXECUTABLE &&
 344      !dependee->IsExecutableWithExports())
 345     {
 346     dependee = 0;
 347     }
 348
 349   if(dependee)
 350     {
 351     this->AddTargetDepend(depender_index, dependee, linking);
 352     }
 353 }
 354
 355 //----------------------------------------------------------------------------
 356 void cmComputeTargetDepends::AddTargetDepend(int depender_index,
 357                                              cmTarget* dependee,
 358                                              bool linking)
 359 {
 360   if(dependee->IsImported())
 361     {
 362     // Skip imported targets but follow their utility dependencies.
 363     std::set<cmStdString> const& utils = dependee->GetUtilities();
 364     for(std::set<cmStdString>::const_iterator i = utils.begin();
 365         i != utils.end(); ++i)
 366       {
 367       if(cmTarget* transitive_dependee =
 368          dependee->GetMakefile()->FindTargetToUse(i->c_str()))
 369         {
 370         this->AddTargetDepend(depender_index, transitive_dependee, false);
 371         }
 372       }
 373     }
 374   else
 375     {
 376     // Lookup the index for this target.  All targets should be known by
 377     // this point.
 378     std::map<cmTarget*, int>::const_iterator tii =
 379       this->TargetIndex.find(dependee);
 380     assert(tii != this->TargetIndex.end());
 381     int dependee_index = tii->second;
 382
 383     // Add this entry to the dependency graph.
 384     this->InitialGraph[depender_index].push_back(
 385       cmGraphEdge(dependee_index, !linking));
 386     }
 387 }
 388
 389 //----------------------------------------------------------------------------
 390 void
 391 cmComputeTargetDepends::DisplayGraph(Graph const& graph, const char* name)
 392 {
 393   fprintf(stderr, "The %s target dependency graph is:\n", name);
 394   int n = static_cast<int>(graph.size());
 395   for(int depender_index = 0; depender_index < n; ++depender_index)
 396     {
 397     EdgeList const& nl = graph[depender_index];
 398     cmTarget* depender = this->Targets[depender_index];
 399     fprintf(stderr, "target %d is [%s]\n",
 400             depender_index, depender->GetName());
 401     for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
 402       {
 403       int dependee_index = *ni;
 404       cmTarget* dependee = this->Targets[dependee_index];
 405       fprintf(stderr, "  depends on target %d [%s] (%s)\n", dependee_index,
 406               dependee->GetName(), ni->IsStrong()? "strong" : "weak");
 407       }
 408     }
 409   fprintf(stderr, "\n");
 410 }
 411
 412 //----------------------------------------------------------------------------
 413 void
 414 cmComputeTargetDepends
 415 ::DisplayComponents(cmComputeComponentGraph const& ccg)
 416 {
 417   fprintf(stderr, "The strongly connected components are:\n");
 418   std::vector<NodeList> const& components = ccg.GetComponents();
 419   int n = static_cast<int>(components.size());
 420   for(int c = 0; c < n; ++c)
 421     {
 422     NodeList const& nl = components[c];
 423     fprintf(stderr, "Component (%d):\n", c);
 424     for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
 425       {
 426       int i = *ni;
 427       fprintf(stderr, "  contains target %d [%s]\n",
 428               i, this->Targets[i]->GetName());
 429       }
 430     }
 431   fprintf(stderr, "\n");
 432 }
 433
 434 //----------------------------------------------------------------------------
 435 bool
 436 cmComputeTargetDepends
 437 ::CheckComponents(cmComputeComponentGraph const& ccg)
 438 {
 439   // All non-trivial components should consist only of static
 440   // libraries.
 441   std::vector<NodeList> const& components = ccg.GetComponents();
 442   int nc = static_cast<int>(components.size());
 443   for(int c=0; c < nc; ++c)
 444     {
 445     // Get the current component.
 446     NodeList const& nl = components[c];
 447
 448     // Skip trivial components.
 449     if(nl.size() < 2)
 450       {
 451       continue;
 452       }
 453
 454     // Immediately complain if no cycles are allowed at all.
 455     if(this->NoCycles)
 456       {
 457       this->ComplainAboutBadComponent(ccg, c);
 458       return false;
 459       }
 460
 461     // Make sure the component is all STATIC_LIBRARY targets.
 462     for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
 463       {
 464       if(this->Targets[*ni]->GetType() != cmTarget::STATIC_LIBRARY)
 465         {
 466         this->ComplainAboutBadComponent(ccg, c);
 467         return false;
 468         }
 469       }
 470     }
 471   return true;
 472 }
 473
 474 //----------------------------------------------------------------------------
 475 void
 476 cmComputeTargetDepends
 477 ::ComplainAboutBadComponent(cmComputeComponentGraph const& ccg, int c,
 478                             bool strong)
 479 {
 480   // Construct the error message.
 481   cmOStringStream e;
 482   e << "The inter-target dependency graph contains the following "
 483     << "strongly connected component (cycle):\n";
 484   std::vector<NodeList> const& components = ccg.GetComponents();
 485   std::vector<int> const& cmap = ccg.GetComponentMap();
 486   NodeList const& cl = components[c];
 487   for(NodeList::const_iterator ci = cl.begin(); ci != cl.end(); ++ci)
 488     {
 489     // Get the depender.
 490     int i = *ci;
 491     cmTarget* depender = this->Targets[i];
 492
 493     // Describe the depender.
 494     e << "  \"" << depender->GetName() << "\" of type "
 495       << cmTarget::GetTargetTypeName(depender->GetType()) << "\n";
 496
 497     // List its dependencies that are inside the component.
 498     EdgeList const& nl = this->InitialGraph[i];
 499     for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
 500       {
 501       int j = *ni;
 502       if(cmap[j] == c)
 503         {
 504         cmTarget* dependee = this->Targets[j];
 505         e << "    depends on \"" << dependee->GetName() << "\""
 506           << " (" << (ni->IsStrong()? "strong" : "weak") << ")\n";
 507         }
 508       }
 509     }
 510   if(strong)
 511     {
 512     // Custom command executable dependencies cannot occur within a
 513     // component of static libraries.  The cycle must appear in calls
 514     // to add_dependencies.
 515     e << "The component contains at least one cycle consisting of strong "
 516       << "dependencies (created by add_dependencies) that cannot be broken.";
 517     }
 518   else if(this->NoCycles)
 519     {
 520     e << "The GLOBAL_DEPENDS_NO_CYCLES global property is enabled, so "
 521       << "cyclic dependencies are not allowed even among static libraries.";
 522     }
 523   else
 524     {
 525     e << "At least one of these targets is not a STATIC_LIBRARY.  "
 526       << "Cyclic dependencies are allowed only among static libraries.";
 527     }
 528   cmSystemTools::Error(e.str().c_str());
 529 }
 530
 531 //----------------------------------------------------------------------------
 532 bool
 533 cmComputeTargetDepends
 534 ::IntraComponent(std::vector<int> const& cmap, int c, int i, int* head,
 535                  std::set<int>& emitted, std::set<int>& visited)
 536 {
 537   if(!visited.insert(i).second)
 538     {
 539     // Cycle in utility depends!
 540     return false;
 541     }
 542   if(emitted.insert(i).second)
 543     {
 544     // Honor strong intra-component edges in the final order.
 545     EdgeList const& el = this->InitialGraph[i];
 546     for(EdgeList::const_iterator ei = el.begin(); ei != el.end(); ++ei)
 547       {
 548       int j = *ei;
 549       if(cmap[j] == c && ei->IsStrong())
 550         {
 551         this->FinalGraph[i].push_back(cmGraphEdge(j, true));
 552         if(!this->IntraComponent(cmap, c, j, head, emitted, visited))
 553           {
 554           return false;
 555           }
 556         }
 557       }
 558
 559     // Prepend to a linear linked-list of intra-component edges.
 560     if(*head >= 0)
 561       {
 562       this->FinalGraph[i].push_back(cmGraphEdge(*head, false));
 563       }
 564     else
 565       {
 566       this->ComponentTail[c] = i;
 567       }
 568     *head = i;
 569     }
 570   return true;
 571 }
 572
 573 //----------------------------------------------------------------------------
 574 bool
 575 cmComputeTargetDepends
 576 ::ComputeFinalDepends(cmComputeComponentGraph const& ccg)
 577 {
 578   // Get the component graph information.
 579   std::vector<NodeList> const& components = ccg.GetComponents();
 580   Graph const& cgraph = ccg.GetComponentGraph();
 581
 582   // Allocate the final graph.
 583   this->FinalGraph.resize(0);
 584   this->FinalGraph.resize(this->InitialGraph.size());
 585
 586   // Choose intra-component edges to linearize dependencies.
 587   std::vector<int> const& cmap = ccg.GetComponentMap();
 588   this->ComponentHead.resize(components.size());
 589   this->ComponentTail.resize(components.size());
 590   int nc = static_cast<int>(components.size());
 591   for(int c=0; c < nc; ++c)
 592     {
 593     int head = -1;
 594     std::set<int> emitted;
 595     NodeList const& nl = components[c];
 596     for(NodeList::const_reverse_iterator ni = nl.rbegin();
 597         ni != nl.rend(); ++ni)
 598       {
 599       std::set<int> visited;
 600       if(!this->IntraComponent(cmap, c, *ni, &head, emitted, visited))
 601         {
 602         // Cycle in add_dependencies within component!
 603         this->ComplainAboutBadComponent(ccg, c, true);
 604         return false;
 605         }
 606       }
 607     this->ComponentHead[c] = head;
 608     }
 609
 610   // Convert inter-component edges to connect component tails to heads.
 611   int n = static_cast<int>(cgraph.size());
 612   for(int depender_component=0; depender_component < n; ++depender_component)
 613     {
 614     int depender_component_tail = this->ComponentTail[depender_component];
 615     EdgeList const& nl = cgraph[depender_component];
 616     for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
 617       {
 618       int dependee_component = *ni;
 619       int dependee_component_head = this->ComponentHead[dependee_component];
 620       this->FinalGraph[depender_component_tail]
 621         .push_back(cmGraphEdge(dependee_component_head, ni->IsStrong()));
 622       }
 623     }
 624   return true;
 625 }