diff options
| -rw-r--r-- | Source/CMakeLists.txt | 3 | ||||
| -rw-r--r-- | Source/cmComputeComponentGraph.cxx | 161 | ||||
| -rw-r--r-- | Source/cmComputeComponentGraph.h | 87 | ||||
| -rw-r--r-- | Source/cmComputeLinkDepends.cxx | 196 | ||||
| -rw-r--r-- | Source/cmComputeLinkDepends.h | 17 | ||||
| -rw-r--r-- | Source/cmComputeTargetDepends.cxx | 236 | ||||
| -rw-r--r-- | Source/cmComputeTargetDepends.h | 42 | ||||
| -rw-r--r-- | Source/cmGraphAdjacencyList.h | 25 | ||||
| -rwxr-xr-x | bootstrap | 1 |
9 files changed, 513 insertions, 255 deletions
diff --git a/Source/CMakeLists.txt b/Source/CMakeLists.txt index 55dc3a1..bef596e 100644 --- a/Source/CMakeLists.txt +++ b/Source/CMakeLists.txt @@ -87,6 +87,8 @@ SET(SRCS cmCommandArgumentLexer.cxx cmCommandArgumentParser.cxx cmCommandArgumentParserHelper.cxx + cmComputeComponentGraph.cxx + cmComputeComponentGraph.h cmComputeLinkDepends.cxx cmComputeLinkDepends.h cmComputeLinkInformation.cxx @@ -138,6 +140,7 @@ SET(SRCS cmGlobalGenerator.h cmGlobalUnixMakefileGenerator3.cxx cmGlobalUnixMakefileGenerator3.h + cmGraphAdjacencyList.h cmInstallGenerator.h cmInstallGenerator.cxx cmInstallExportGenerator.cxx diff --git a/Source/cmComputeComponentGraph.cxx b/Source/cmComputeComponentGraph.cxx new file mode 100644 index 0000000..b76635f --- /dev/null +++ b/Source/cmComputeComponentGraph.cxx @@ -0,0 +1,161 @@ +/*========================================================================= + + Program: CMake - Cross-Platform Makefile Generator + Module: $RCSfile$ + Language: C++ + Date: $Date$ + Version: $Revision$ + + Copyright (c) 2002 Kitware, Inc., Insight Consortium. All rights reserved. + See Copyright.txt or http://www.cmake.org/HTML/Copyright.html for details. + + This software is distributed WITHOUT ANY WARRANTY; without even + the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR + PURPOSE. See the above copyright notices for more information. + +=========================================================================*/ +#include "cmComputeComponentGraph.h" + +#include <algorithm> + +#include <assert.h> + +//---------------------------------------------------------------------------- +cmComputeComponentGraph::cmComputeComponentGraph(Graph const& input): + InputGraph(input) +{ + // Identify components. + this->Tarjan(); + + // Compute the component graph. + this->ComponentGraph.resize(0); + this->ComponentGraph.resize(this->Components.size()); + this->TransferEdges(); +} + +//---------------------------------------------------------------------------- +cmComputeComponentGraph::~cmComputeComponentGraph() +{ +} + +//---------------------------------------------------------------------------- +void cmComputeComponentGraph::Tarjan() +{ + int n = static_cast<int>(this->InputGraph.size()); + TarjanEntry entry = {0,0}; + this->TarjanEntries.resize(0); + this->TarjanEntries.resize(n, entry); + this->TarjanComponents.resize(0); + this->TarjanComponents.resize(n, -1); + this->TarjanWalkId = 0; + this->TarjanVisited.resize(0); + this->TarjanVisited.resize(n, 0); + for(int i = 0; i < n; ++i) + { + // Start a new DFS from this node if it has never been visited. + if(!this->TarjanVisited[i]) + { + assert(this->TarjanStack.empty()); + ++this->TarjanWalkId; + this->TarjanIndex = 0; + this->TarjanVisit(i); + } + } +} + +//---------------------------------------------------------------------------- +void cmComputeComponentGraph::TarjanVisit(int i) +{ + // We are now visiting this node. + this->TarjanVisited[i] = this->TarjanWalkId; + + // Initialize the entry. + this->TarjanEntries[i].Root = i; + this->TarjanComponents[i] = -1; + this->TarjanEntries[i].VisitIndex = ++this->TarjanIndex; + this->TarjanStack.push(i); + + // Follow outgoing edges. + NodeList const& nl = this->InputGraph[i]; + for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) + { + int j = *ni; + + // Ignore edges to nodes that have been reached by a previous DFS + // walk. Since we did not reach the current node from that walk + // it must not belong to the same component and it has already + // been assigned to a component. + if(this->TarjanVisited[j] > 0 && + this->TarjanVisited[j] < this->TarjanWalkId) + { + continue; + } + + // Visit the destination if it has not yet been visited. + if(!this->TarjanVisited[j]) + { + this->TarjanVisit(j); + } + + // If the destination has not yet been assigned to a component, + // check if it has a better root for the current object. + if(this->TarjanComponents[j] < 0) + { + if(this->TarjanEntries[this->TarjanEntries[j].Root].VisitIndex < + this->TarjanEntries[this->TarjanEntries[i].Root].VisitIndex) + { + this->TarjanEntries[i].Root = this->TarjanEntries[j].Root; + } + } + } + + // Check if we have found a component. + if(this->TarjanEntries[i].Root == i) + { + // Yes. Create it. + int c = static_cast<int>(this->Components.size()); + this->Components.push_back(NodeList()); + NodeList& component = this->Components[c]; + + // Populate the component list. + int j; + do + { + // Get the next member of the component. + j = this->TarjanStack.top(); + this->TarjanStack.pop(); + + // Assign the member to the component. + this->TarjanComponents[j] = c; + this->TarjanEntries[j].Root = i; + + // Store the node in its component. + component.push_back(j); + } while(j != i); + + // Sort the component members for clarity. + std::sort(component.begin(), component.end()); + } +} + +//---------------------------------------------------------------------------- +void cmComputeComponentGraph::TransferEdges() +{ + // Map inter-component edges in the original graph to edges in the + // component graph. + int n = static_cast<int>(this->InputGraph.size()); + for(int i=0; i < n; ++i) + { + int i_component = this->TarjanComponents[i]; + NodeList const& nl = this->InputGraph[i]; + for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) + { + int j = *ni; + int j_component = this->TarjanComponents[j]; + if(i_component != j_component) + { + this->ComponentGraph[i_component].push_back(j_component); + } + } + } +} diff --git a/Source/cmComputeComponentGraph.h b/Source/cmComputeComponentGraph.h new file mode 100644 index 0000000..a75afcf --- /dev/null +++ b/Source/cmComputeComponentGraph.h @@ -0,0 +1,87 @@ +/*========================================================================= + + Program: CMake - Cross-Platform Makefile Generator + Module: $RCSfile$ + Language: C++ + Date: $Date$ + Version: $Revision$ + + Copyright (c) 2002 Kitware, Inc., Insight Consortium. All rights reserved. + See Copyright.txt or http://www.cmake.org/HTML/Copyright.html for details. + + This software is distributed WITHOUT ANY WARRANTY; without even + the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR + PURPOSE. See the above copyright notices for more information. + +=========================================================================*/ +#ifndef cmComputeComponentGraph_h +#define cmComputeComponentGraph_h + +#include "cmStandardIncludes.h" + +#include "cmGraphAdjacencyList.h" + +#include <stack> + +/** \class cmComputeComponentGraph + * \brief Analyze a graph to determine strongly connected components. + * + * Convert a directed graph into a directed acyclic graph whose nodes + * correspond to strongly connected components of the original graph. + * + * We use Tarjan's algorithm to enumerate the components efficiently. + * An advantage of this approach is that the components are identified + * in a topologically sorted order. + */ +class cmComputeComponentGraph +{ +public: + // Represent the graph with an adjacency list. + typedef cmGraphNodeList NodeList; + typedef cmGraphAdjacencyList Graph; + + cmComputeComponentGraph(Graph const& input); + ~cmComputeComponentGraph(); + + /** Get the adjacency list of the component graph. */ + Graph const& GetComponentGraph() const + { return this->ComponentGraph; } + NodeList const& GetComponentGraphEdges(int c) const + { return this->ComponentGraph[c]; } + + /** Get map from component index to original node indices. */ + std::vector<NodeList> const& GetComponents() const + { return this->Components; } + NodeList const& GetComponent(int c) const + { return this->Components[c]; } + + /** Get map from original node index to component index. */ + std::vector<int> const& GetComponentMap() const + { return this->TarjanComponents; } + +private: + void TransferEdges(); + + Graph const& InputGraph; + Graph ComponentGraph; + + // Tarjan's algorithm. + struct TarjanEntry + { + int Root; + int VisitIndex; + }; + int TarjanWalkId; + std::vector<int> TarjanVisited; + std::vector<int> TarjanComponents; + std::vector<TarjanEntry> TarjanEntries; + std::stack<int> TarjanStack; + int TarjanIndex; + void Tarjan(); + void TarjanVisit(int i); + + // Connected components. + std::vector<NodeList> Components; +}; + +#endif diff --git a/Source/cmComputeLinkDepends.cxx b/Source/cmComputeLinkDepends.cxx index cfcfe24..30f43f8 100644 --- a/Source/cmComputeLinkDepends.cxx +++ b/Source/cmComputeLinkDepends.cxx @@ -16,6 +16,7 @@ =========================================================================*/ #include "cmComputeLinkDepends.h" +#include "cmComputeComponentGraph.h" #include "cmGlobalGenerator.h" #include "cmLocalGenerator.h" #include "cmMakefile.h" @@ -96,31 +97,47 @@ For the unknown items, we infer dependencies by looking at the B: intersect( {Y,C} , {} ) = {} ; infer no edges C: intersect( {} , {B} ) = {} ; infer no edges +------------------------------------------------------------------------------ + Once the complete graph is formed from all known and inferred -dependencies, we walk the graph with a series of depth-first-searches -in order to emit link items. When visiting a node all edges are -followed first because the neighbors must precede the item. Once -neighbors across all edges have been emitted it is safe to emit the -current node. +dependencies we must use it to produce a valid link line. If the +dependency graph were known to be acyclic a simple depth-first-search +would produce a correct link line. Unfortunately we cannot make this +assumption so the following technique is used. + +The original graph is converted to a directed acyclic graph in which +each node corresponds to a strongly connected component of the +original graph. For example, the dependency graph + + X <- A <- B <- C <- A <- Y -If a single DFS returns to a node it previously reached then a cycle -is present. Cyclic link dependencies are resolved simply by repeating -one of the cycle entries at the beginning and end of the cycle -members. For example, the graph +contains strongly connected components {X}, {A,B,C}, and {Y}. The +implied directed acyclic graph (DAG) is - A <- B , B <- C , C <- A + {X} <- {A,B,C} <- {Y} -can be satisfied with the link item list +The final list of link items is constructed by a series of +depth-first-searches through this DAG of components. When visiting a +component all outgoing edges are followed first because the neighbors +must precede it. Once neighbors across all edges have been emitted it +is safe to emit the current component. - A B C A +Trivial components (those with one item) are handled simply by +emitting the item. Non-trivial components (those with more than one +item) are assumed to consist only of static libraries that may be +safely repeated on the link line. We emit members of the component +multiple times (see code below for details). The final link line for +the example graph might be -When a node is reached a second time during the same DFS we make sure -its item has been emitted and then skip following its outgoing edges -again. + X A B C A B C Y + +------------------------------------------------------------------------------ The initial exploration of dependencies using a BFS associates an integer index with each link item. When the graph is built outgoing -edges are sorted by this index. This preserves the original link +edges are sorted by this index. + +This preserves the original link order as much as possible subject to the dependencies. After the initial exploration of the link interface tree, any @@ -190,6 +207,9 @@ cmComputeLinkDepends::Compute() // Infer dependencies of targets for which they were not known. this->InferDependencies(); + // Cleanup the constraint graph. + this->CleanConstraintGraph(); + // Display the constraint graph. if(this->DebugMode) { @@ -223,7 +243,7 @@ cmComputeLinkDepends::AllocateLinkEntry(std::string const& item) lei = this->LinkEntryIndex.insert(index_entry).first; this->EntryList.push_back(LinkEntry()); this->InferredDependSets.push_back(0); - this->EntryConstraintGraph.push_back(EntryConstraintSet()); + this->EntryConstraintGraph.push_back(NodeList()); return lei; } @@ -354,7 +374,7 @@ void cmComputeLinkDepends::HandleSharedDependency(SharedDepEntry const& dep) // This shared library dependency must be preceded by the item that // listed it. - this->EntryConstraintGraph[index].insert(dep.DependerIndex); + this->EntryConstraintGraph[index].push_back(dep.DependerIndex); // Target items may have their own dependencies. if(entry.Target) @@ -469,7 +489,7 @@ cmComputeLinkDepends::AddLinkEntries(int depender_index, // The depender must come before the dependee. if(depender_index >= 0) { - this->EntryConstraintGraph[dependee_index].insert(depender_index); + this->EntryConstraintGraph[dependee_index].push_back(depender_index); } // Update the inferred dependencies for earlier items. @@ -531,22 +551,37 @@ void cmComputeLinkDepends::InferDependencies() for(DependSet::const_iterator j = common.begin(); j != common.end(); ++j) { int dependee_index = *j; - this->EntryConstraintGraph[dependee_index].insert(depender_index); + this->EntryConstraintGraph[dependee_index].push_back(depender_index); } } } //---------------------------------------------------------------------------- +void cmComputeLinkDepends::CleanConstraintGraph() +{ + for(Graph::iterator i = this->EntryConstraintGraph.begin(); + i != this->EntryConstraintGraph.end(); ++i) + { + // Sort the outgoing edges for each graph node so that the + // original order will be preserved as much as possible. + cmsys_stl::sort(i->begin(), i->end()); + + // Make the edge list unique. + NodeList::iterator last = cmsys_stl::unique(i->begin(), i->end()); + i->erase(last, i->end()); + } +} + +//---------------------------------------------------------------------------- void cmComputeLinkDepends::DisplayConstraintGraph() { - // Display the conflict graph. + // Display the graph nodes and their edges. cmOStringStream e; for(unsigned int i=0; i < this->EntryConstraintGraph.size(); ++i) { - EntryConstraintSet const& cset = this->EntryConstraintGraph[i]; + NodeList const& nl = this->EntryConstraintGraph[i]; e << "item " << i << " is [" << this->EntryList[i].Item << "]\n"; - for(EntryConstraintSet::const_iterator j = cset.begin(); - j != cset.end(); ++j) + for(NodeList::const_iterator j = nl.begin(); j != nl.end(); ++j) { e << " item " << *j << " must precede it\n"; } @@ -557,56 +592,107 @@ void cmComputeLinkDepends::DisplayConstraintGraph() //---------------------------------------------------------------------------- void cmComputeLinkDepends::OrderLinkEntires() { + // Compute the DAG of strongly connected components. The algorithm + // used by cmComputeComponentGraph should identify the components in + // the same order in which the items were originally discovered in + // the BFS. This should preserve the original order when no + // constraints disallow it. + cmComputeComponentGraph ccg(this->EntryConstraintGraph); + Graph const& cgraph = ccg.GetComponentGraph(); + if(this->DebugMode) + { + this->DisplayComponents(ccg); + } + // Setup visit tracking. - this->EntryVisited.resize(this->EntryList.size(), 0); - this->WalkId = 0; + this->ComponentVisited.resize(cgraph.size(), 0); - // Start a DFS from every entry. - for(unsigned int i=0; i < this->EntryList.size(); ++i) + // The component graph is guaranteed to be acyclic. Start a DFS + // from every entry. + for(unsigned int c=0; c < cgraph.size(); ++c) { - ++this->WalkId; - this->VisitLinkEntry(i); + this->VisitComponent(ccg, c); } } //---------------------------------------------------------------------------- -void cmComputeLinkDepends::VisitLinkEntry(unsigned int i) +void +cmComputeLinkDepends::DisplayComponents(cmComputeComponentGraph const& ccg) { - // Check if the node has already been visited. - if(this->EntryVisited[i]) + fprintf(stderr, "The strongly connected components are:\n"); + std::vector<NodeList> const& components = ccg.GetComponents(); + for(unsigned int c=0; c < components.size(); ++c) { - if(this->EntryVisited[i] == this->WalkId) + fprintf(stderr, "Component (%u):\n", c); + NodeList const& nl = components[c]; + for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) { - // We have reached a node previously visited on this DFS. There - // is a cycle. In order to allow linking with cyclic - // dependencies we make sure the item is emitted but do not - // follow its outgoing edges again. - if(this->EntryEmitted.insert(i).second) - { - // The item has not been previously emitted so we emit it now. - // It will be emitted again when the stack unwinds back up to - // the beginning of the cycle. - this->FinalLinkEntries.push_back(this->EntryList[i]); - } + int i = *ni; + fprintf(stderr, " item %d [%s]\n", i, + this->EntryList[i].Item.c_str()); } + } + fprintf(stderr, "\n"); +} + +//---------------------------------------------------------------------------- +void +cmComputeLinkDepends::VisitComponent(cmComputeComponentGraph const& ccg, + unsigned int c) +{ + // Check if the node has already been visited. + if(this->ComponentVisited[c]) + { return; } - // We are now visiting this node so mark it. - this->EntryVisited[i] = this->WalkId; + // We are now visiting this component so mark it. + this->ComponentVisited[c] = 1; - // Visit the neighbors of the node first. - EntryConstraintSet const& cset = this->EntryConstraintGraph[i]; - for(EntryConstraintSet::const_iterator j = cset.begin(); - j != cset.end(); ++j) + // Visit the neighbors of the component first. + NodeList const& nl = ccg.GetComponentGraphEdges(c); + for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) { - this->VisitLinkEntry(*j); + this->VisitComponent(ccg, *ni); } // Now that all items required to come before this one have been - // emmitted, emit this item. - this->EntryEmitted.insert(i); - this->FinalLinkEntries.push_back(this->EntryList[i]); + // emmitted, emit this component's items. + this->EmitComponent(ccg.GetComponent(c)); +} + +//---------------------------------------------------------------------------- +void cmComputeLinkDepends::EmitComponent(NodeList const& nl) +{ + assert(!nl.empty()); + + // Handle trivial components. + if(nl.size() == 1) + { + this->FinalLinkEntries.push_back(this->EntryList[nl[0]]); + return; + } + + // This is a non-trivial strongly connected component of the + // original graph. It consists of two or more libraries (archives) + // that mutually require objects from one another. In the worst + // case we may have to repeat the list of libraries as many times as + // there are object files in the biggest archive. For now we just + // list them twice. + // + // The list of items in the component has been sorted by the order + // of discovery in the original BFS of dependencies. This has the + // advantage that the item directly linked by a target requiring + // this component will come first which minimizes the number of + // repeats needed. + for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) + { + this->FinalLinkEntries.push_back(this->EntryList[*ni]); + } + for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) + { + this->FinalLinkEntries.push_back(this->EntryList[*ni]); + } } //---------------------------------------------------------------------------- diff --git a/Source/cmComputeLinkDepends.h b/Source/cmComputeLinkDepends.h index 1e422a6..b81f8bc 100644 --- a/Source/cmComputeLinkDepends.h +++ b/Source/cmComputeLinkDepends.h @@ -20,8 +20,11 @@ #include "cmStandardIncludes.h" #include "cmTarget.h" +#include "cmGraphAdjacencyList.h" + #include <queue> +class cmComputeComponentGraph; class cmGlobalGenerator; class cmLocalGenerator; class cmMakefile; @@ -109,16 +112,18 @@ private: void InferDependencies(); // Ordering constraint graph adjacency list. - struct EntryConstraintSet: public std::set<int> {}; - std::vector<EntryConstraintSet> EntryConstraintGraph; + typedef cmGraphNodeList NodeList; + typedef cmGraphAdjacencyList Graph; + Graph EntryConstraintGraph; + void CleanConstraintGraph(); void DisplayConstraintGraph(); // Ordering algorithm. - std::vector<int> EntryVisited; - std::set<int> EntryEmitted; - int WalkId; void OrderLinkEntires(); - void VisitLinkEntry(unsigned int i); + std::vector<char> ComponentVisited; + void DisplayComponents(cmComputeComponentGraph const& ccg); + void VisitComponent(cmComputeComponentGraph const& ccg, unsigned int i); + void EmitComponent(NodeList const& nl); void DisplayFinalEntries(); }; diff --git a/Source/cmComputeTargetDepends.cxx b/Source/cmComputeTargetDepends.cxx index 3062c4d..d13a6db 100644 --- a/Source/cmComputeTargetDepends.cxx +++ b/Source/cmComputeTargetDepends.cxx @@ -16,6 +16,7 @@ =========================================================================*/ #include "cmComputeTargetDepends.h" +#include "cmComputeComponentGraph.h" #include "cmGlobalGenerator.h" #include "cmLocalGenerator.h" #include "cmMakefile.h" @@ -117,25 +118,25 @@ bool cmComputeTargetDepends::Compute() this->CollectDepends(); if(this->DebugMode) { - this->DisplayGraph(this->TargetDependGraph, "initial"); + this->DisplayGraph(this->InitialGraph, "initial"); } // Identify components. - this->Tarjan(); + cmComputeComponentGraph ccg(this->InitialGraph); if(this->DebugMode) { - this->DisplayComponents(); + this->DisplayComponents(ccg); } - if(!this->CheckComponents()) + if(!this->CheckComponents(ccg)) { return false; } // Compute the final dependency graph. - this->ComputeFinalDepends(); + this->ComputeFinalDepends(ccg); if(this->DebugMode) { - this->DisplayGraph(this->FinalDependGraph, "final"); + this->DisplayGraph(this->FinalGraph, "final"); } return true; @@ -153,11 +154,10 @@ cmComputeTargetDepends::GetTargetDirectDepends(cmTarget* t, int i = tii->second; // Get its final dependencies. - TargetDependList const& tdl = this->FinalDependGraph[i]; - for(TargetDependList::const_iterator di = tdl.begin(); - di != tdl.end(); ++di) + NodeList const& nl = this->FinalGraph[i]; + for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) { - deps.insert(this->Targets[*di]); + deps.insert(this->Targets[*ni]); } } @@ -184,7 +184,7 @@ void cmComputeTargetDepends::CollectTargets() void cmComputeTargetDepends::CollectDepends() { // Allocate the dependency graph adjacency lists. - this->TargetDependGraph.resize(this->Targets.size()); + this->InitialGraph.resize(this->Targets.size()); // Compute each dependency list. for(unsigned int i=0; i < this->Targets.size(); ++i) @@ -265,27 +265,24 @@ void cmComputeTargetDepends::AddTargetDepend(int depender_index, int dependee_index = tii->second; // Add this entry to the dependency graph. - this->TargetDependGraph[depender_index].push_back(dependee_index); + this->InitialGraph[depender_index].push_back(dependee_index); } //---------------------------------------------------------------------------- void -cmComputeTargetDepends -::DisplayGraph(std::vector<TargetDependList> const& graph, - const char* name) +cmComputeTargetDepends::DisplayGraph(Graph const& graph, const char* name) { fprintf(stderr, "The %s target dependency graph is:\n", name); int n = static_cast<int>(graph.size()); for(int depender_index = 0; depender_index < n; ++depender_index) { - TargetDependList const& tdl = graph[depender_index]; + NodeList const& nl = graph[depender_index]; cmTarget* depender = this->Targets[depender_index]; fprintf(stderr, "target %d is [%s]\n", depender_index, depender->GetName()); - for(TargetDependList::const_iterator di = tdl.begin(); - di != tdl.end(); ++di) + for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) { - int dependee_index = *di; + int dependee_index = *ni; cmTarget* dependee = this->Targets[dependee_index]; fprintf(stderr, " depends on target %d [%s]\n", dependee_index, dependee->GetName()); @@ -295,115 +292,20 @@ cmComputeTargetDepends } //---------------------------------------------------------------------------- -void cmComputeTargetDepends::Tarjan() -{ - int n = static_cast<int>(this->TargetDependGraph.size()); - TarjanEntry entry = {0,-1,0}; - this->TarjanEntries.resize(n, entry); - this->TarjanWalkId = 0; - this->TarjanVisited.resize(n, 0); - for(int i = 0; i < n; ++i) - { - // Start a new DFS from this node if it has never been visited. - if(!this->TarjanVisited[i]) - { - assert(this->TarjanStack.empty()); - ++this->TarjanWalkId; - this->TarjanIndex = 0; - this->TarjanVisit(i); - } - } -} - -//---------------------------------------------------------------------------- -void cmComputeTargetDepends::TarjanVisit(int i) -{ - // We are now visiting this node. - this->TarjanVisited[i] = this->TarjanWalkId; - - // Initialize the entry. - this->TarjanEntries[i].Root = i; - this->TarjanEntries[i].Component = -1; - this->TarjanEntries[i].VisitIndex = ++this->TarjanIndex; - this->TarjanStack.push(i); - - // Follow outgoing edges. - TargetDependList const& tdl = this->TargetDependGraph[i]; - for(TargetDependList::const_iterator di = tdl.begin(); - di != tdl.end(); ++di) - { - int j = *di; - - // Ignore edges to nodes that have been reached by a previous DFS - // walk. Since we did not reach the current node from that walk - // it must not belong to the same component and it has already - // been assigned to a component. - if(this->TarjanVisited[j] > 0 && - this->TarjanVisited[j] < this->TarjanWalkId) - { - continue; - } - - // Visit the destination if it has not yet been visited. - if(!this->TarjanVisited[j]) - { - this->TarjanVisit(j); - } - - // If the destination has not yet been assigned to a component, - // check if it is a better potential root for the current object. - if(this->TarjanEntries[j].Component < 0) - { - if(this->TarjanEntries[this->TarjanEntries[j].Root].VisitIndex < - this->TarjanEntries[this->TarjanEntries[i].Root].VisitIndex) - { - this->TarjanEntries[i].Root = this->TarjanEntries[j].Root; - } - } - } - - // Check if we have found a component. - if(this->TarjanEntries[i].Root == i) - { - // Yes. Create it. - int c = static_cast<int>(this->Components.size()); - this->Components.push_back(ComponentList()); - ComponentList& component = this->Components[c]; - - // Populate the component list. - int j; - do - { - // Get the next member of the component. - j = this->TarjanStack.top(); - this->TarjanStack.pop(); - - // Assign the member to the component. - this->TarjanEntries[j].Component = c; - this->TarjanEntries[j].Root = i; - - // Store the node in its component. - component.push_back(j); - } while(j != i); - - // Sort the component members for clarity. - std::sort(component.begin(), component.end()); - } -} - -//---------------------------------------------------------------------------- -void cmComputeTargetDepends::DisplayComponents() +void +cmComputeTargetDepends +::DisplayComponents(cmComputeComponentGraph const& ccg) { fprintf(stderr, "The strongly connected components are:\n"); - int n = static_cast<int>(this->Components.size()); + std::vector<NodeList> const& components = ccg.GetComponents(); + int n = static_cast<int>(components.size()); for(int c = 0; c < n; ++c) { - ComponentList const& cl = this->Components[c]; + NodeList const& nl = components[c]; fprintf(stderr, "Component (%d):\n", c); - for(ComponentList::const_iterator ci = cl.begin(); - ci != cl.end(); ++ci) + for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) { - int i = *ci; + int i = *ni; fprintf(stderr, " contains target %d [%s]\n", i, this->Targets[i]->GetName()); } @@ -412,28 +314,31 @@ void cmComputeTargetDepends::DisplayComponents() } //---------------------------------------------------------------------------- -bool cmComputeTargetDepends::CheckComponents() +bool +cmComputeTargetDepends +::CheckComponents(cmComputeComponentGraph const& ccg) { // All non-trivial components should consist only of static // libraries. - int nc = static_cast<int>(this->Components.size()); + std::vector<NodeList> const& components = ccg.GetComponents(); + int nc = static_cast<int>(components.size()); for(int c=0; c < nc; ++c) { // Get the current component. - ComponentList const& cl = this->Components[c]; + NodeList const& nl = components[c]; // Skip trivial components. - if(cl.size() < 2) + if(nl.size() < 2) { continue; } // Make sure the component is all STATIC_LIBRARY targets. - for(ComponentList::const_iterator ci = cl.begin(); ci != cl.end(); ++ci) + for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) { - if(this->Targets[*ci]->GetType() != cmTarget::STATIC_LIBRARY) + if(this->Targets[*ni]->GetType() != cmTarget::STATIC_LIBRARY) { - this->ComplainAboutBadComponent(c); + this->ComplainAboutBadComponent(ccg, c); return false; } } @@ -443,16 +348,17 @@ bool cmComputeTargetDepends::CheckComponents() //---------------------------------------------------------------------------- void -cmComputeTargetDepends::ComplainAboutBadComponent(int c) +cmComputeTargetDepends +::ComplainAboutBadComponent(cmComputeComponentGraph const& ccg, int c) { - // Get the bad component. - ComponentList const& cl = this->Components[c]; - // Construct the error message. cmOStringStream e; e << "The inter-target dependency graph contains the following " << "strongly connected component (cycle):\n"; - for(ComponentList::const_iterator ci = cl.begin(); ci != cl.end(); ++ci) + std::vector<NodeList> const& components = ccg.GetComponents(); + std::vector<int> const& cmap = ccg.GetComponentMap(); + NodeList const& cl = components[c]; + for(NodeList::const_iterator ci = cl.begin(); ci != cl.end(); ++ci) { // Get the depender. int i = *ci; @@ -463,12 +369,11 @@ cmComputeTargetDepends::ComplainAboutBadComponent(int c) << cmTarget::TargetTypeNames[depender->GetType()] << "\n"; // List its dependencies that are inside the component. - TargetDependList const& tdl = this->TargetDependGraph[i]; - for(TargetDependList::const_iterator di = tdl.begin(); - di != tdl.end(); ++di) + NodeList const& nl = this->InitialGraph[i]; + for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) { - int j = *di; - if(this->TarjanEntries[j].Component == c) + int j = *ni; + if(cmap[j] == c) { cmTarget* dependee = this->Targets[j]; e << " depends on " << dependee->GetName() << "\n"; @@ -481,46 +386,45 @@ cmComputeTargetDepends::ComplainAboutBadComponent(int c) } //---------------------------------------------------------------------------- -void cmComputeTargetDepends::ComputeFinalDepends() +void +cmComputeTargetDepends +::ComputeFinalDepends(cmComputeComponentGraph const& ccg) { - int n = static_cast<int>(this->TargetDependGraph.size()); - this->FinalDependGraph.resize(n); + // Get the component graph information. + std::vector<NodeList> const& components = ccg.GetComponents(); + Graph const& cgraph = ccg.GetComponentGraph(); + + // Allocate the final graph. + this->FinalGraph.resize(0); + this->FinalGraph.resize(this->InitialGraph.size()); // Convert inter-component edges to connect component tails to heads. - for(int i=0; i < n; ++i) + int n = static_cast<int>(cgraph.size()); + for(int depender_component=0; depender_component < n; ++depender_component) { - int depender_component = this->TarjanEntries[i].Component; - int depender_component_tail = - this->Components[depender_component].back(); - - TargetDependList const& tdl = this->TargetDependGraph[i]; - for(TargetDependList::const_iterator di = tdl.begin(); - di != tdl.end(); ++di) + int depender_component_tail = components[depender_component].back(); + NodeList const& nl = cgraph[depender_component]; + for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni) { - int j = *di; - int dependee_component = this->TarjanEntries[j].Component; - int dependee_component_head = - this->Components[dependee_component].front(); - if(depender_component != dependee_component) - { - this->FinalDependGraph[depender_component_tail] - .push_back(dependee_component_head); - } + int dependee_component = *ni; + int dependee_component_head = components[dependee_component].front(); + this->FinalGraph[depender_component_tail] + .push_back(dependee_component_head); } } // Compute intra-component edges. - int nc = static_cast<int>(this->Components.size()); + int nc = static_cast<int>(components.size()); for(int c=0; c < nc; ++c) { // Within the component each target depends on that following it. - ComponentList const& cl = this->Components[c]; - ComponentList::const_iterator ci = cl.begin(); - int last_i = *ci; - for(++ci; ci != cl.end(); ++ci) + NodeList const& nl = components[c]; + NodeList::const_iterator ni = nl.begin(); + int last_i = *ni; + for(++ni; ni != nl.end(); ++ni) { - int i = *ci; - this->FinalDependGraph[last_i].push_back(i); + int i = *ni; + this->FinalGraph[last_i].push_back(i); last_i = i; } } diff --git a/Source/cmComputeTargetDepends.h b/Source/cmComputeTargetDepends.h index 9c17731..707256e 100644 --- a/Source/cmComputeTargetDepends.h +++ b/Source/cmComputeTargetDepends.h @@ -19,8 +19,11 @@ #include "cmStandardIncludes.h" +#include "cmGraphAdjacencyList.h" + #include <stack> +class cmComputeComponentGraph; class cmGlobalGenerator; class cmTarget; @@ -46,7 +49,7 @@ private: void CollectDepends(); void CollectTargetDepends(int depender_index); void AddTargetDepend(int depender_index, const char* dependee_name); - void ComputeFinalDepends(); + void ComputeFinalDepends(cmComputeComponentGraph const& ccg); cmGlobalGenerator* GlobalGenerator; bool DebugMode; @@ -58,33 +61,16 @@ private: // Represent the target dependency graph. The entry at each // top-level index corresponds to a depender whose dependencies are // listed. - struct TargetDependList: public std::vector<int> {}; - std::vector<TargetDependList> TargetDependGraph; - std::vector<TargetDependList> FinalDependGraph; - void DisplayGraph(std::vector<TargetDependList> const& graph, - const char* name); - - // Tarjan's algorithm. - struct TarjanEntry - { - int Root; - int Component; - int VisitIndex; - }; - int TarjanWalkId; - std::vector<int> TarjanVisited; - std::vector<TarjanEntry> TarjanEntries; - std::stack<int> TarjanStack; - int TarjanIndex; - void Tarjan(); - void TarjanVisit(int i); - - // Connected components. - struct ComponentList: public std::vector<int> {}; - std::vector<ComponentList> Components; - void DisplayComponents(); - bool CheckComponents(); - void ComplainAboutBadComponent(int c); + typedef cmGraphNodeList NodeList; + typedef cmGraphAdjacencyList Graph; + Graph InitialGraph; + Graph FinalGraph; + void DisplayGraph(Graph const& graph, const char* name); + + // Deal with connected components. + void DisplayComponents(cmComputeComponentGraph const& ccg); + bool CheckComponents(cmComputeComponentGraph const& ccg); + void ComplainAboutBadComponent(cmComputeComponentGraph const& ccg, int c); }; #endif diff --git a/Source/cmGraphAdjacencyList.h b/Source/cmGraphAdjacencyList.h new file mode 100644 index 0000000..ef0aa09 --- /dev/null +++ b/Source/cmGraphAdjacencyList.h @@ -0,0 +1,25 @@ +/*========================================================================= + + Program: CMake - Cross-Platform Makefile Generator + Module: $RCSfile$ + Language: C++ + Date: $Date$ + Version: $Revision$ + + Copyright (c) 2002 Kitware, Inc., Insight Consortium. All rights reserved. + See Copyright.txt or http://www.cmake.org/HTML/Copyright.html for details. + + This software is distributed WITHOUT ANY WARRANTY; without even + the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR + PURPOSE. See the above copyright notices for more information. + +=========================================================================*/ +#ifndef cmGraphAdjacencyList_h +#define cmGraphAdjacencyList_h + +#include "cmStandardIncludes.h" + +struct cmGraphNodeList: public std::vector<int> {}; +struct cmGraphAdjacencyList: public std::vector<cmGraphNodeList> {}; + +#endif @@ -171,6 +171,7 @@ CMAKE_CXX_SOURCES="\ cmComputeLinkInformation \ cmOrderRuntimeDirectories \ cmComputeTargetDepends \ + cmComputeComponentGraph \ " if ${cmake_system_mingw}; then |