summaryrefslogtreecommitdiffstats
path: root/Source
diff options
context:
space:
mode:
authorBrad King <brad.king@kitware.com>2008-02-07 21:14:05 (GMT)
committerBrad King <brad.king@kitware.com>2008-02-07 21:14:05 (GMT)
commit4987e17f46cb2542106ee2d9afe2752ef78d0f1f (patch)
tree15f70e63f520fb34572ba7147b6231b1e6612276 /Source
parent0bfad2946dc3da390fed5b58dcf493b55886aa31 (diff)
downloadCMake-4987e17f46cb2542106ee2d9afe2752ef78d0f1f.zip
CMake-4987e17f46cb2542106ee2d9afe2752ef78d0f1f.tar.gz
CMake-4987e17f46cb2542106ee2d9afe2752ef78d0f1f.tar.bz2
ENH: Improve link line generation for static library cycles.
- Move Tarjan algorithm from cmComputeTargetDepends into its own class cmComputeComponentGraph - Use cmComputeComponentGraph to identify the component DAG of link dependencies in cmComputeLinkDepends - Emit non-trivial component members more than once but always in a contiguous group on the link line
Diffstat (limited to 'Source')
-rw-r--r--Source/CMakeLists.txt3
-rw-r--r--Source/cmComputeComponentGraph.cxx161
-rw-r--r--Source/cmComputeComponentGraph.h87
-rw-r--r--Source/cmComputeLinkDepends.cxx196
-rw-r--r--Source/cmComputeLinkDepends.h17
-rw-r--r--Source/cmComputeTargetDepends.cxx236
-rw-r--r--Source/cmComputeTargetDepends.h42
-rw-r--r--Source/cmGraphAdjacencyList.h25
8 files changed, 512 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