/*
  This file is part of Ingen.
  Copyright 2015-2017 David Robillard <http://drobilla.net/>

  Ingen is free software: you can redistribute it and/or modify it under the
  terms of the GNU Affero General Public License as published by the Free
  Software Foundation, either version 3 of the License, or any later version.

  Ingen is distributed in the hope that it will be useful, but WITHOUT ANY
  WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  A PARTICULAR PURPOSE.  See the GNU Affero General Public License for details.

  You should have received a copy of the GNU Affero General Public License
  along with Ingen.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <algorithm>
#include <unordered_set>

#include "ingen/ColorContext.hpp"
#include "ingen/Configuration.hpp"
#include "ingen/Log.hpp"
#include "ingen/World.hpp"

#include "CompiledGraph.hpp"
#include "Engine.hpp"
#include "GraphImpl.hpp"
#include "ThreadManager.hpp"

namespace Ingen {
namespace Server {

using BlockSet = std::unordered_set<BlockImpl*>;

/** Graph contains ambiguous feedback with no delay nodes. */
class FeedbackException : public Raul::Exception {
public:
	FeedbackException(const BlockImpl* node, const BlockImpl* root = nullptr)
		: Raul::Exception(
		    std::string("Feedback at ") + node->path()
		    + (root ? std::string(" from ") + root->path() : std::string()))
	{
	}
};

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; }

private:
	BlockImpl*      _block;
	BlockImpl::Mark _old;
	BlockImpl::Mark _done;
};

static bool
has_provider_with_fan_out(BlockImpl* n)
{
	for (auto* p : n->providers()) {
		if (p->dependants().size() > 1) {
			return true;
		}
	}

	return false;
}

static size_t
num_unvisited_dependants(BlockImpl* block)
{
	size_t count = 0;
	for (BlockImpl* b : block->dependants()) {
		if (b->get_mark() == BlockImpl::Mark::UNVISITED) {
			++count;
		}
	}
	return count;
}

/** 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()) {
		// Mark all blocks as unvisited initially
		b.set_mark(BlockImpl::Mark::UNVISITED);

		if (b.dependants().empty()) {
			// Block has no dependants, add to initial working set
			blocks.insert(&b);
		}
	}

	// Keep compiling working set until all nodes are visited
	while (!blocks.empty()) {
		BlockSet predecessors;

		_master->emplace_front(Task::Mode::PARALLEL);
		for (auto b : blocks) {
			assert(num_unvisited_dependants(b) == 0);
			compile_block(b, _master->front(), predecessors);
		}

		blocks = std::move(predecessors);
	}

	_master = Task::simplify(std::move(_master));
}

MPtr<CompiledGraph> compile(Raul::Maid& maid, GraphImpl& graph)
{
	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");
		}

		return result;
	} catch (const FeedbackException& e) {
		graph.engine().log().error(e.what());
	}

	return MPtr<CompiledGraph>();
}

} // namespace Server
} // namespace Ingen