summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/server/CompiledGraph.cpp248
-rw-r--r--src/server/CompiledGraph.hpp31
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
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-16 19:26:47 +0000