From a390f6065fb14a9768f3b1693adf9586870945cd Mon Sep 17 00:00:00 2001 From: David Robillard Date: Thu, 15 Mar 2018 01:48:55 -0400 Subject: fixup! Simplify --- src/server/CompiledGraph.cpp | 248 ++++++++++++++++++++----------------------- src/server/CompiledGraph.hpp | 31 +----- 2 files changed, 122 insertions(+), 157 deletions(-) (limited to 'src/server') 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 +#include #include "ingen/ColorContext.hpp" #include "ingen/Configuration.hpp" @@ -29,39 +30,53 @@ namespace Ingen { namespace Server { +using BlockSet = std::unordered_set; + /** 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(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::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(&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(); } + + 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(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()) { - 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 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(graph); + + if (graph.engine().world()->conf().option("trace").get()) { + 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(); } } // 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 -#include -#include +#include +#include #include "ingen/types.hpp" #include "raul/Maid.hpp" @@ -43,37 +42,15 @@ class CompiledGraph : public Raul::Maid::Disposable , public Raul::Noncopyable { public: - static MPtr 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 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 _master; }; -inline MPtr compile(Raul::Maid& maid, GraphImpl& graph) -{ - return CompiledGraph::compile(maid, graph); -} +MPtr compile(Raul::Maid& maid, GraphImpl& graph); } // namespace Server } // namespace Ingen -- cgit v1.2.1