+// Sort the nodes in topological order.
+void CompilationGraph::TopologicalSort(std::vector<const Node*>& Out) {
+ std::queue<const Node*> Q;
+ Q.push(&getNode("root"));
+
+ while (!Q.empty()) {
+ const Node* A = Q.front();
+ Q.pop();
+ Out.push_back(A);
+ for (Node::const_iterator EB = A->EdgesBegin(), EE = A->EdgesEnd();
+ EB != EE; ++EB) {
+ Node* B = &getNode((*EB)->ToolName());
+ B->DecrInEdges();
+ if (B->HasNoInEdges())
+ Q.push(B);
+ }
+ }
+}
+
+namespace {
+ bool NotJoinNode(const Node* N) {
+ return N->ToolPtr ? !N->ToolPtr->IsJoin() : true;
+ }
+}
+
+// Call TopologicalSort and filter the resulting list to include
+// only Join nodes.
+void CompilationGraph::
+TopologicalSortFilterJoinNodes(std::vector<const Node*>& Out) {
+ std::vector<const Node*> TopSorted;
+ TopologicalSort(TopSorted);
+ std::remove_copy_if(TopSorted.begin(), TopSorted.end(),
+ std::back_inserter(Out), NotJoinNode);
+}
+
+int CompilationGraph::Build (const sys::Path& TempDir) {
+
+ InputLanguagesSet InLangs;
+
+ // Traverse initial parts of the toolchains and fill in InLangs.
+ BuildInitial(InLangs, TempDir);
+
+ std::vector<const Node*> JTV;
+ TopologicalSortFilterJoinNodes(JTV);
+
+ // For all join nodes in topological order:
+ for (std::vector<const Node*>::iterator B = JTV.begin(), E = JTV.end();
+ B != E; ++B) {
+
+ sys::Path Out;
+ const Node* CurNode = *B;
+ JoinTool* JT = &dynamic_cast<JoinTool&>(*CurNode->ToolPtr.getPtr());
+ bool IsLast = false;
+
+ // Are there any files in the join list?
+ if (JT->JoinListEmpty())
+ continue;
+
+ // Is this the last tool in the toolchain?
+ // NOTE: we can process several toolchains in parallel.
+ if (!CurNode->HasChildren() || JT->IsLast()) {
+ if (OutputFilename.empty()) {
+ Out.set("a");
+ Out.appendSuffix(JT->OutputSuffix());
+ }
+ else
+ Out.set(OutputFilename);
+ IsLast = true;