fixup! Simplify

2 files changed, 122 insertions, 157 deletions

diff --git a/src/server/CompiledGraph.cpp b/src/server/CompiledGraph.cpp
index f31fa595..32302174 100644
--- a/src/server/CompiledGraph.cpp
+++ b/src/server/CompiledGraph.cpp
@@ -15,6 +15,7 @@
 */
 
 #include <algorithm>
+#include <unordered_set>
 
 #include "ingen/ColorContext.hpp"
 #include "ingen/Configuration.hpp"
@@ -29,39 +30,53 @@
 namespace Ingen {
 namespace Server {
 
+using BlockSet = std::unordered_set<BlockImpl*>;
+
 /** Graph contains ambiguous feedback with no delay nodes. */
-class FeedbackException : public std::exception {
+class FeedbackException : public Raul::Exception {
 public:
-	FeedbackException(const BlockImpl* node, const BlockImpl* root=nullptr)
-		: node(node)
-		, root(root)
-	{}
-
-	const BlockImpl* node;
-	const BlockImpl* root;
+	FeedbackException(const BlockImpl* node, const BlockImpl* root = nullptr)
+		: Raul::Exception(
+		    std::string("Feedback at ") + node->path()
+		    + (root ? std::string(" from ") + root->path() : std::string()))
+	{
+	}
 };
 
-CompiledGraph::CompiledGraph(GraphImpl* graph)
-	: _master(std::unique_ptr<Task>(new Task(Task::Mode::SEQUENTIAL)))
-{
-	compile_graph(graph);
-}
+class ScopedMark {
+public:
+	ScopedMark(BlockImpl* block, BlockImpl::Mark active, BlockImpl::Mark done)
+		: _old(block->get_mark())
+		, _done(done)
+	{
+		block->set_mark(active);
+	}
+
+	~ScopedMark()
+	{
+		_block->set_mark(_done);
+	}
+
+	ScopedMark(const ScopedMark&) = delete;
+
+	BlockImpl::Mark old() const { return _old; }
 
-MPtr<CompiledGraph>
-CompiledGraph::compile(Raul::Maid& maid, GraphImpl& graph)
+private:
+	BlockImpl*      _block;
+	BlockImpl::Mark _old;
+	BlockImpl::Mark _done;
+};
+
+static bool
+has_provider_with_fan_out(BlockImpl* n)
 {
-	try {
-		return maid.make_managed<CompiledGraph>(&graph);
-	} catch (const FeedbackException& e) {
-		Log& log = graph.engine().log();
-		if (e.node && e.root) {
-			log.error(fmt("Feedback compiling %1% from %2%\n")
-			          % e.node->path() % e.root->path());
-		} else {
-			log.error(fmt("Feedback compiling %1%\n") % e.node->path());
+	for (auto* p : n->providers()) {
+		if (p->dependants().size() > 1) {
+			return true;
 		}
-		return MPtr<CompiledGraph>();
 	}
+
+	return false;
 }
 
 static size_t
@@ -76,14 +91,71 @@ num_unvisited_dependants(BlockImpl* block)
 	return count;
 }
 
-void
-CompiledGraph::compile_graph(GraphImpl* graph)
+/** Throw a FeedbackException iff `dependant` has `root` as a dependency.
+ *
+ * This must be used when the normal traversal short-cuts and adds to the
+ * future working set so that feedback cycles that would be discovered by a
+ * full BFS are still detected.
+ */
+static void
+check_feedback(const BlockImpl* root, BlockImpl* node)
+{
+	if (node == root || node->get_mark() == BlockImpl::Mark::VISITING) {
+		throw FeedbackException(node, root);
+	}
+
+	const ScopedMark mark(node, BlockImpl::Mark::VISITING, node->get_mark());
+	for (auto p : node->providers()) {
+		check_feedback(root, p);
+	}
+}
+
+static void
+compile_block(BlockImpl* n, Task& task, BlockSet& k)
+{
+	switch (n->get_mark()) {
+	case BlockImpl::Mark::UNVISITED: {
+		ScopedMark mark(n, BlockImpl::Mark::VISITING, BlockImpl::Mark::VISITED);
+		if (has_provider_with_fan_out(n)) {
+			// Provider shared by other dependants, enqueue providers for later
+			// Prepends n to current task: (... n ...)
+			task.emplace_front(n);
+			for (auto p : n->providers()) {
+				check_feedback(n, p);
+				if (num_unvisited_dependants(p) == 0) {
+					k.insert(p);
+				}
+			}
+		} else {
+			// All providers have only this dependant
+			// Runs node after parallel providers: (... (seq (par p...) n) ...)
+			task.emplace_front(Task::Mode::SEQUENTIAL);
+			task.front().emplace_front(n);
+
+			task.front().emplace_front(Task::Mode::PARALLEL);
+			for (auto p : n->providers()) {
+				compile_block(p, task.front().front(), k);
+			}
+		}
+		break;
+	}
+
+	case BlockImpl::Mark::VISITING:
+		throw FeedbackException(n);
+
+	case BlockImpl::Mark::VISITED:
+		break;
+	}
+}
+
+CompiledGraph::CompiledGraph(GraphImpl& graph)
+	: _master(std::unique_ptr<Task>(new Task(Task::Mode::SEQUENTIAL)))
 {
 	ThreadManager::assert_thread(THREAD_PRE_PROCESS);
 
 	// Start with sink nodes (no outputs, or connected only to graph outputs)
 	BlockSet blocks;
-	for (auto& b : graph->blocks()) {
+	for (auto& b : graph.blocks()) {
 		// Mark all blocks as unvisited initially
 		b.set_mark(BlockImpl::Mark::UNVISITED);
 
@@ -97,121 +169,37 @@ CompiledGraph::compile_graph(GraphImpl* graph)
 	while (!blocks.empty()) {
 		BlockSet predecessors;
 
-		Task par(Task::Mode::PARALLEL);
+		_master->emplace_front(Task::Mode::PARALLEL);
 		for (auto b : blocks) {
 			assert(num_unvisited_dependants(b) == 0);
-			Task seq(Task::Mode::SEQUENTIAL);
-			compile_block(b, seq, predecessors);
-			par.push_front(std::move(seq));
+			compile_block(b, _master->front(), predecessors);
 		}
-		_master->push_front(std::move(par));
-		blocks = predecessors;
-	}
-
-	_master = Task::simplify(std::move(_master));
-
-	if (graph->engine().world()->conf().option("trace").get<int32_t>()) {
-		ColorContext ctx(stderr, ColorContext::Color::YELLOW);
-		dump(graph->path());
-	}
-}
 
-/** Throw a FeedbackException iff `dependant` has `root` as a dependency. */
-static void
-check_feedback(const BlockImpl* root, BlockImpl* provider)
-{
-	if (provider == root) {
-		throw FeedbackException(root);
-	}
-
-	for (auto p : provider->providers()) {
-		const BlockImpl::Mark mark = p->get_mark();
-		switch (mark) {
-		case BlockImpl::Mark::UNVISITED:
-			p->set_mark(BlockImpl::Mark::VISITING);
-			check_feedback(root, p);
-			break;
-		case BlockImpl::Mark::VISITING:
-			throw FeedbackException(p, root);
-		case BlockImpl::Mark::VISITED:
-			break;
-		}
-		p->set_mark(mark);
+		blocks = std::move(predecessors);
 	}
-}
 
-void
-CompiledGraph::compile_provider(const BlockImpl* root,
-                                BlockImpl*       block,
-                                Task&            task,
-                                BlockSet&        k)
-{
-	if (block->dependants().size() > 1) {
-		/* Provider has other dependants, so this is the tail of a sequential task.
-		   Add provider to future working set and stop traversal. */
-		check_feedback(root, block);
-		if (num_unvisited_dependants(block) == 0) {
-			k.insert(block);
-		}
-	} else {
-		// Calling dependant has only this provider, add here
-		if (task.mode() == Task::Mode::PARALLEL) {
-			// Inside a parallel task, compile into a new sequential child
-			Task seq(Task::Mode::SEQUENTIAL);
-			compile_block(block, seq, k);
-			task.push_front(std::move(seq));
-		} else {
-			// Prepend to given sequential task
-			compile_block(block, task, k);
-		}
-	}
+	_master = Task::simplify(std::move(_master));
 }
 
-void
-CompiledGraph::compile_block(BlockImpl* n, Task& task, BlockSet& k)
+MPtr<CompiledGraph> compile(Raul::Maid& maid, GraphImpl& graph)
 {
-	switch (n->get_mark()) {
-	case BlockImpl::Mark::UNVISITED:
-		n->set_mark(BlockImpl::Mark::VISITING);
-
-		// Execute this task after the providers to follow
-		task.push_front(Task(Task::Mode::SINGLE, n));
-
-		if (n->providers().size() <= 1) {
-			// Single provider, prepend it to this sequential task
-			for (auto p : n->providers()) {
-				compile_provider(n, p, task, k);
-			}
-		} else {
-			// Stop recursion and enqueue providers for the next round
-			for (auto p : n->providers()) {
-				if (num_unvisited_dependants(p) == 0) {
-					k.insert(p);
-				}
-			}
+	try {
+		auto result = maid.make_managed<CompiledGraph>(graph);
+
+		if (graph.engine().world()->conf().option("trace").get<int32_t>()) {
+			Log& log  = graph.engine().log();
+			auto sink = [&log](const std::string& s) { log.trace(s); };
+			sink(graph.path() + " =>\n  ");
+			result->master().dump(sink, 2, true);
+			sink("\n");
 		}
-		n->set_mark(BlockImpl::Mark::VISITED);
-		break;
-
-	case BlockImpl::Mark::VISITING:
-		throw FeedbackException(n);
 
-	case BlockImpl::Mark::VISITED:
-		break;
+		return result;
+	} catch (const FeedbackException& e) {
+		graph.engine().log().error(e.what());
 	}
-}
 
-void
-CompiledGraph::dump(const std::string& name) const
-{
-	auto sink = [](const std::string& s) {
-		fwrite(s.c_str(), 1, s.size(), stderr);
-	};
-
-	sink("(compiled-graph ");
-	sink(name);
-	_master->dump(sink, 2, false);
-	sink(")\n");
+	return MPtr<CompiledGraph>();
 }
 
 } // namespace Server
diff --git a/src/server/CompiledGraph.hpp b/src/server/CompiledGraph.hpp
index 43b03f92..c3bb1ce1 100644
--- a/src/server/CompiledGraph.hpp
+++ b/src/server/CompiledGraph.hpp
@@ -17,9 +17,8 @@
 #ifndef INGEN_ENGINE_COMPILEDGRAPH_HPP
 #define INGEN_ENGINE_COMPILEDGRAPH_HPP
 
-#include <functional>
-#include <unordered_set>
-#include <vector>
+#include <memory>
+#include <string>
 
 #include "ingen/types.hpp"
 #include "raul/Maid.hpp"
@@ -43,37 +42,15 @@ class CompiledGraph : public Raul::Maid::Disposable
                     , public Raul::Noncopyable
 {
 public:
-	static MPtr<CompiledGraph> compile(Raul::Maid& maid, GraphImpl& graph);
+	explicit CompiledGraph(GraphImpl& graph);
 
 	Task& master() { return *_master; }
 
 private:
-	friend class Raul::Maid;  ///< Allow make_managed to construct
-
-	CompiledGraph(GraphImpl* graph);
-
-	typedef std::unordered_set<BlockImpl*> BlockSet;
-
-	void dump(const std::string& name) const;
-
-	void compile_graph(GraphImpl* graph);
-
-	void compile_block(BlockImpl* n,
-	                   Task&      task,
-	                   BlockSet&  k);
-
-	void compile_provider(const BlockImpl* root,
-	                      BlockImpl*       block,
-	                      Task&            task,
-	                      BlockSet&        k);
-
 	std::unique_ptr<Task> _master;
 };
 
-inline MPtr<CompiledGraph> compile(Raul::Maid& maid, GraphImpl& graph)
-{
-	return CompiledGraph::compile(maid, graph);
-}
+MPtr<CompiledGraph> compile(Raul::Maid& maid, GraphImpl& graph);
 
 } // namespace Server
 } // namespace Ingen