summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorBrad King <brad.king@kitware.com>2010-08-31 18:36:50 (GMT)
committerCMake Topic Stage <kwrobot@kitware.com>2010-08-31 18:36:50 (GMT)
commit1976c45a3c65534966d51b6e2f1d460081bb49b5 (patch)
tree5cd14bf293e95332657288e73a81fdddf389746a
parentd2a65b5f40d8be6710d0ca815e6a5863885db749 (diff)
parentadb58d5e36e482e7cc2c0b1a37d94b21da9234df (diff)
downloadCMake-1976c45a3c65534966d51b6e2f1d460081bb49b5.zip
CMake-1976c45a3c65534966d51b6e2f1d460081bb49b5.tar.gz
CMake-1976c45a3c65534966d51b6e2f1d460081bb49b5.tar.bz2
Merge topic 'intra-component-dependencies'
adb58d5 Honor strong intra-component target dependencies 681cf01 Distinguish "strong" and "weak" target dependency edges 7be2617 Split notion of node lists and edge lists
-rw-r--r--Source/cmComputeComponentGraph.cxx13
-rw-r--r--Source/cmComputeComponentGraph.h3
-rw-r--r--Source/cmComputeLinkDepends.cxx23
-rw-r--r--Source/cmComputeLinkDepends.h1
-rw-r--r--Source/cmComputeTargetDepends.cxx149
-rw-r--r--Source/cmComputeTargetDepends.h11
-rw-r--r--Source/cmGraphAdjacencyList.h22
-rw-r--r--Tests/Dependency/Four/CMakeLists.txt3
-rw-r--r--Tests/Dependency/Four/FourSrc.c1
9 files changed, 166 insertions, 60 deletions
diff --git a/Source/cmComputeComponentGraph.cxx b/Source/cmComputeComponentGraph.cxx
index 3f2a361..5bec6a1 100644
--- a/Source/cmComputeComponentGraph.cxx
+++ b/Source/cmComputeComponentGraph.cxx
@@ -71,8 +71,8 @@ void cmComputeComponentGraph::TarjanVisit(int i)
this->TarjanStack.push(i);
// Follow outgoing edges.
- NodeList const& nl = this->InputGraph[i];
- for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
+ EdgeList const& nl = this->InputGraph[i];
+ for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
{
int j = *ni;
@@ -142,14 +142,17 @@ void cmComputeComponentGraph::TransferEdges()
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)
+ EdgeList const& nl = this->InputGraph[i];
+ for(EdgeList::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);
+ // We do not attempt to combine duplicate edges, but instead
+ // store the inter-component edges with suitable multiplicity.
+ this->ComponentGraph[i_component].push_back(
+ cmGraphEdge(j_component, ni->IsStrong()));
}
}
}
diff --git a/Source/cmComputeComponentGraph.h b/Source/cmComputeComponentGraph.h
index 855a141..a2ce946 100644
--- a/Source/cmComputeComponentGraph.h
+++ b/Source/cmComputeComponentGraph.h
@@ -33,6 +33,7 @@ class cmComputeComponentGraph
public:
// Represent the graph with an adjacency list.
typedef cmGraphNodeList NodeList;
+ typedef cmGraphEdgeList EdgeList;
typedef cmGraphAdjacencyList Graph;
cmComputeComponentGraph(Graph const& input);
@@ -41,7 +42,7 @@ public:
/** Get the adjacency list of the component graph. */
Graph const& GetComponentGraph() const
{ return this->ComponentGraph; }
- NodeList const& GetComponentGraphEdges(int c) const
+ EdgeList const& GetComponentGraphEdges(int c) const
{ return this->ComponentGraph[c]; }
/** Get map from component index to original node indices. */
diff --git a/Source/cmComputeLinkDepends.cxx b/Source/cmComputeLinkDepends.cxx
index 24410ec..342c217 100644
--- a/Source/cmComputeLinkDepends.cxx
+++ b/Source/cmComputeLinkDepends.cxx
@@ -285,7 +285,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(NodeList());
+ this->EntryConstraintGraph.push_back(EdgeList());
return lei;
}
@@ -669,7 +669,7 @@ void cmComputeLinkDepends::CleanConstraintGraph()
cmsys_stl::sort(i->begin(), i->end());
// Make the edge list unique.
- NodeList::iterator last = cmsys_stl::unique(i->begin(), i->end());
+ EdgeList::iterator last = cmsys_stl::unique(i->begin(), i->end());
i->erase(last, i->end());
}
}
@@ -681,9 +681,9 @@ void cmComputeLinkDepends::DisplayConstraintGraph()
cmOStringStream e;
for(unsigned int i=0; i < this->EntryConstraintGraph.size(); ++i)
{
- NodeList const& nl = this->EntryConstraintGraph[i];
+ EdgeList const& nl = this->EntryConstraintGraph[i];
e << "item " << i << " is [" << this->EntryList[i].Item << "]\n";
- for(NodeList::const_iterator j = nl.begin(); j != nl.end(); ++j)
+ for(EdgeList::const_iterator j = nl.begin(); j != nl.end(); ++j)
{
e << " item " << *j << " must follow it\n";
}
@@ -758,10 +758,11 @@ cmComputeLinkDepends::DisplayComponents()
fprintf(stderr, " item %d [%s]\n", i,
this->EntryList[i].Item.c_str());
}
- NodeList const& ol = this->CCG->GetComponentGraphEdges(c);
- for(NodeList::const_iterator oi = ol.begin(); oi != ol.end(); ++oi)
+ EdgeList const& ol = this->CCG->GetComponentGraphEdges(c);
+ for(EdgeList::const_iterator oi = ol.begin(); oi != ol.end(); ++oi)
{
- fprintf(stderr, " followed by Component (%d)\n", *oi);
+ int i = *oi;
+ fprintf(stderr, " followed by Component (%d)\n", i);
}
fprintf(stderr, " topo order index %d\n",
this->ComponentOrder[c]);
@@ -784,8 +785,8 @@ void cmComputeLinkDepends::VisitComponent(unsigned int c)
// Visit the neighbors of the component first.
// Run in reverse order so the topological order will preserve the
// original order where there are no constraints.
- NodeList const& nl = this->CCG->GetComponentGraphEdges(c);
- for(NodeList::const_reverse_iterator ni = nl.rbegin();
+ EdgeList const& nl = this->CCG->GetComponentGraphEdges(c);
+ for(EdgeList::const_reverse_iterator ni = nl.rbegin();
ni != nl.rend(); ++ni)
{
this->VisitComponent(*ni);
@@ -856,8 +857,8 @@ void cmComputeLinkDepends::VisitEntry(int index)
// are now pending.
if(completed)
{
- NodeList const& ol = this->CCG->GetComponentGraphEdges(component);
- for(NodeList::const_iterator oi = ol.begin(); oi != ol.end(); ++oi)
+ EdgeList const& ol = this->CCG->GetComponentGraphEdges(component);
+ for(EdgeList::const_iterator oi = ol.begin(); oi != ol.end(); ++oi)
{
// This entire component is now pending no matter whether it has
// been partially seen already.
diff --git a/Source/cmComputeLinkDepends.h b/Source/cmComputeLinkDepends.h
index a08afb6..e196e00 100644
--- a/Source/cmComputeLinkDepends.h
+++ b/Source/cmComputeLinkDepends.h
@@ -117,6 +117,7 @@ private:
// Ordering constraint graph adjacency list.
typedef cmGraphNodeList NodeList;
+ typedef cmGraphEdgeList EdgeList;
typedef cmGraphAdjacencyList Graph;
Graph EntryConstraintGraph;
void CleanConstraintGraph();
diff --git a/Source/cmComputeTargetDepends.cxx b/Source/cmComputeTargetDepends.cxx
index 94b8527..313c680 100644
--- a/Source/cmComputeTargetDepends.cxx
+++ b/Source/cmComputeTargetDepends.cxx
@@ -129,7 +129,10 @@ bool cmComputeTargetDepends::Compute()
}
// Compute the final dependency graph.
- this->ComputeFinalDepends(ccg);
+ if(!this->ComputeFinalDepends(ccg))
+ {
+ return false;
+ }
if(this->DebugMode)
{
this->DisplayGraph(this->FinalGraph, "final");
@@ -150,8 +153,8 @@ cmComputeTargetDepends::GetTargetDirectDepends(cmTarget* t,
int i = tii->second;
// Get its final dependencies.
- NodeList const& nl = this->FinalGraph[i];
- for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
+ EdgeList const& nl = this->FinalGraph[i];
+ for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
{
deps.insert(this->Targets[*ni]);
}
@@ -195,15 +198,13 @@ void cmComputeTargetDepends::CollectTargetDepends(int depender_index)
// Get the depender.
cmTarget* depender = this->Targets[depender_index];
- // Keep track of dependencies already listed.
- std::set<cmStdString> emitted;
-
- // A target should not depend on itself.
- emitted.insert(depender->GetName());
-
// Loop over all targets linked directly.
+ {
cmTarget::LinkLibraryVectorType const& tlibs =
depender->GetOriginalLinkLibraries();
+ std::set<cmStdString> emitted;
+ // A target should not depend on itself.
+ emitted.insert(depender->GetName());
for(cmTarget::LinkLibraryVectorType::const_iterator lib = tlibs.begin();
lib != tlibs.end(); ++lib)
{
@@ -213,9 +214,14 @@ void cmComputeTargetDepends::CollectTargetDepends(int depender_index)
this->AddTargetDepend(depender_index, lib->first.c_str(), true);
}
}
+ }
// Loop over all utility dependencies.
+ {
std::set<cmStdString> const& tutils = depender->GetUtilities();
+ std::set<cmStdString> emitted;
+ // A target should not depend on itself.
+ emitted.insert(depender->GetName());
for(std::set<cmStdString>::const_iterator util = tutils.begin();
util != tutils.end(); ++util)
{
@@ -225,6 +231,7 @@ void cmComputeTargetDepends::CollectTargetDepends(int depender_index)
this->AddTargetDepend(depender_index, util->c_str(), false);
}
}
+ }
}
//----------------------------------------------------------------------------
@@ -272,7 +279,8 @@ void cmComputeTargetDepends::AddTargetDepend(int depender_index,
int dependee_index = tii->second;
// Add this entry to the dependency graph.
- this->InitialGraph[depender_index].push_back(dependee_index);
+ this->InitialGraph[depender_index].push_back(
+ cmGraphEdge(dependee_index, !linking));
}
//----------------------------------------------------------------------------
@@ -283,16 +291,16 @@ cmComputeTargetDepends::DisplayGraph(Graph const& graph, const char* name)
int n = static_cast<int>(graph.size());
for(int depender_index = 0; depender_index < n; ++depender_index)
{
- NodeList const& nl = graph[depender_index];
+ EdgeList const& nl = graph[depender_index];
cmTarget* depender = this->Targets[depender_index];
fprintf(stderr, "target %d is [%s]\n",
depender_index, depender->GetName());
- for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
+ for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
{
int dependee_index = *ni;
cmTarget* dependee = this->Targets[dependee_index];
- fprintf(stderr, " depends on target %d [%s]\n", dependee_index,
- dependee->GetName());
+ fprintf(stderr, " depends on target %d [%s] (%s)\n", dependee_index,
+ dependee->GetName(), ni->IsStrong()? "strong" : "weak");
}
}
fprintf(stderr, "\n");
@@ -363,7 +371,8 @@ cmComputeTargetDepends
//----------------------------------------------------------------------------
void
cmComputeTargetDepends
-::ComplainAboutBadComponent(cmComputeComponentGraph const& ccg, int c)
+::ComplainAboutBadComponent(cmComputeComponentGraph const& ccg, int c,
+ bool strong)
{
// Construct the error message.
cmOStringStream e;
@@ -383,18 +392,27 @@ cmComputeTargetDepends
<< cmTarget::TargetTypeNames[depender->GetType()] << "\n";
// List its dependencies that are inside the component.
- NodeList const& nl = this->InitialGraph[i];
- for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
+ EdgeList const& nl = this->InitialGraph[i];
+ for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
{
int j = *ni;
if(cmap[j] == c)
{
cmTarget* dependee = this->Targets[j];
- e << " depends on \"" << dependee->GetName() << "\"\n";
+ e << " depends on \"" << dependee->GetName() << "\""
+ << " (" << (ni->IsStrong()? "strong" : "weak") << ")\n";
}
}
}
- if(this->NoCycles)
+ if(strong)
+ {
+ // Custom command executable dependencies cannot occur within a
+ // component of static libraries. The cycle must appear in calls
+ // to add_dependencies.
+ e << "The component contains at least one cycle consisting of strong "
+ << "dependencies (created by add_dependencies) that cannot be broken.";
+ }
+ else if(this->NoCycles)
{
e << "The GLOBAL_DEPENDS_NO_CYCLES global property is enabled, so "
<< "cyclic dependencies are not allowed even among static libraries.";
@@ -408,7 +426,49 @@ cmComputeTargetDepends
}
//----------------------------------------------------------------------------
-void
+bool
+cmComputeTargetDepends
+::IntraComponent(std::vector<int> const& cmap, int c, int i, int* head,
+ std::set<int>& emitted, std::set<int>& visited)
+{
+ if(!visited.insert(i).second)
+ {
+ // Cycle in utility depends!
+ return false;
+ }
+ if(emitted.insert(i).second)
+ {
+ // Honor strong intra-component edges in the final order.
+ EdgeList const& el = this->InitialGraph[i];
+ for(EdgeList::const_iterator ei = el.begin(); ei != el.end(); ++ei)
+ {
+ int j = *ei;
+ if(cmap[j] == c && ei->IsStrong())
+ {
+ this->FinalGraph[i].push_back(j);
+ if(!this->IntraComponent(cmap, c, j, head, emitted, visited))
+ {
+ return false;
+ }
+ }
+ }
+
+ // Prepend to a linear linked-list of intra-component edges.
+ if(*head >= 0)
+ {
+ this->FinalGraph[i].push_back(*head);
+ }
+ else
+ {
+ this->ComponentTail[c] = i;
+ }
+ *head = i;
+ }
+ return true;
+}
+
+//----------------------------------------------------------------------------
+bool
cmComputeTargetDepends
::ComputeFinalDepends(cmComputeComponentGraph const& ccg)
{
@@ -420,34 +480,43 @@ cmComputeTargetDepends
this->FinalGraph.resize(0);
this->FinalGraph.resize(this->InitialGraph.size());
+ // Choose intra-component edges to linearize dependencies.
+ std::vector<int> const& cmap = ccg.GetComponentMap();
+ this->ComponentHead.resize(components.size());
+ this->ComponentTail.resize(components.size());
+ int nc = static_cast<int>(components.size());
+ for(int c=0; c < nc; ++c)
+ {
+ int head = -1;
+ std::set<int> emitted;
+ NodeList const& nl = components[c];
+ for(NodeList::const_reverse_iterator ni = nl.rbegin();
+ ni != nl.rend(); ++ni)
+ {
+ std::set<int> visited;
+ if(!this->IntraComponent(cmap, c, *ni, &head, emitted, visited))
+ {
+ // Cycle in add_dependencies within component!
+ this->ComplainAboutBadComponent(ccg, c, true);
+ return false;
+ }
+ }
+ this->ComponentHead[c] = head;
+ }
+
// Convert inter-component edges to connect component tails to heads.
int n = static_cast<int>(cgraph.size());
for(int depender_component=0; depender_component < n; ++depender_component)
{
- 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 depender_component_tail = this->ComponentTail[depender_component];
+ EdgeList const& nl = cgraph[depender_component];
+ for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
{
int dependee_component = *ni;
- int dependee_component_head = components[dependee_component].front();
+ int dependee_component_head = this->ComponentHead[dependee_component];
this->FinalGraph[depender_component_tail]
.push_back(dependee_component_head);
}
}
-
- // Compute intra-component edges.
- int nc = static_cast<int>(components.size());
- for(int c=0; c < nc; ++c)
- {
- // Within the component each target depends on that following it.
- NodeList const& nl = components[c];
- NodeList::const_iterator ni = nl.begin();
- int last_i = *ni;
- for(++ni; ni != nl.end(); ++ni)
- {
- int i = *ni;
- this->FinalGraph[last_i].push_back(i);
- last_i = i;
- }
- }
+ return true;
}
diff --git a/Source/cmComputeTargetDepends.h b/Source/cmComputeTargetDepends.h
index 68e3e47..240de76 100644
--- a/Source/cmComputeTargetDepends.h
+++ b/Source/cmComputeTargetDepends.h
@@ -45,7 +45,7 @@ private:
void CollectTargetDepends(int depender_index);
void AddTargetDepend(int depender_index, const char* dependee_name,
bool linking);
- void ComputeFinalDepends(cmComputeComponentGraph const& ccg);
+ bool ComputeFinalDepends(cmComputeComponentGraph const& ccg);
cmGlobalGenerator* GlobalGenerator;
bool DebugMode;
@@ -59,6 +59,7 @@ private:
// top-level index corresponds to a depender whose dependencies are
// listed.
typedef cmGraphNodeList NodeList;
+ typedef cmGraphEdgeList EdgeList;
typedef cmGraphAdjacencyList Graph;
Graph InitialGraph;
Graph FinalGraph;
@@ -67,7 +68,13 @@ private:
// Deal with connected components.
void DisplayComponents(cmComputeComponentGraph const& ccg);
bool CheckComponents(cmComputeComponentGraph const& ccg);
- void ComplainAboutBadComponent(cmComputeComponentGraph const& ccg, int c);
+ void ComplainAboutBadComponent(cmComputeComponentGraph const& ccg, int c,
+ bool strong = false);
+
+ std::vector<int> ComponentHead;
+ std::vector<int> ComponentTail;
+ bool IntraComponent(std::vector<int> const& cmap, int c, int i, int* head,
+ std::set<int>& emitted, std::set<int>& visited);
};
#endif
diff --git a/Source/cmGraphAdjacencyList.h b/Source/cmGraphAdjacencyList.h
index 7794840..0149d33 100644
--- a/Source/cmGraphAdjacencyList.h
+++ b/Source/cmGraphAdjacencyList.h
@@ -14,7 +14,27 @@
#include "cmStandardIncludes.h"
+/**
+ * Graph edge representation. Most use cases just need the
+ * destination vertex, so we support conversion to/from an int. We
+ * also store boolean to indicate whether an edge is "strong".
+ */
+class cmGraphEdge
+{
+public:
+ cmGraphEdge(): Dest(0), Strong(true) {}
+ cmGraphEdge(int n): Dest(n), Strong(true) {}
+ cmGraphEdge(int n, bool s): Dest(n), Strong(s) {}
+ cmGraphEdge(cmGraphEdge const& r): Dest(r.Dest), Strong(r.Strong) {}
+ operator int() const { return this->Dest; }
+
+ bool IsStrong() const { return this->Strong; }
+private:
+ int Dest;
+ bool Strong;
+};
+struct cmGraphEdgeList: public std::vector<cmGraphEdge> {};
struct cmGraphNodeList: public std::vector<int> {};
-struct cmGraphAdjacencyList: public std::vector<cmGraphNodeList> {};
+struct cmGraphAdjacencyList: public std::vector<cmGraphEdgeList> {};
#endif
diff --git a/Tests/Dependency/Four/CMakeLists.txt b/Tests/Dependency/Four/CMakeLists.txt
index ba3711f..df0f162 100644
--- a/Tests/Dependency/Four/CMakeLists.txt
+++ b/Tests/Dependency/Four/CMakeLists.txt
@@ -1,3 +1,6 @@
+INCLUDE_DIRECTORIES(${Dependency_BINARY_DIR}/Two)
ADD_LIBRARY( Four FourSrc.c )
TARGET_LINK_LIBRARIES( Four One Two NoDepA )
+# TwoCustom must build before Four.
+ADD_DEPENDENCIES(Four TwoCustom)
diff --git a/Tests/Dependency/Four/FourSrc.c b/Tests/Dependency/Four/FourSrc.c
index e8fefcd..23a66a4 100644
--- a/Tests/Dependency/Four/FourSrc.c
+++ b/Tests/Dependency/Four/FourSrc.c
@@ -1,3 +1,4 @@
+#include <two-test.h> /* Requires TwoCustom to be built first. */
void NoDepAFunction();
void OneFunction();
void TwoFunction();