/**
	Dependency configuration/version resolution algorithm.
 
	Copyright: © 2014 rejectedsoftware e.K.
	License: Subject to the terms of the MIT license, as written in the included LICENSE.txt file.
	Authors: Sönke Ludwig
*/
module dub.dependencyresolver;
 
import dub.dependency;
import dub.internal.vibecompat.core.log;
 
import std.algorithm : all, canFind, filter, map, sort;
import std.array : appender, array;
import std.conv : to;
import std.exception : enforce;
import std.string : format, indexOf, lastIndexOf;
 
 
class DependencyResolver(CONFIGS, CONFIG) {
	static struct TreeNodes {
		string pack;
		CONFIGS configs;
		DependencyType depType = DependencyType.required;
 
		hash_t toHash() const nothrow @trusted {
			size_t ret = typeid(string).getHash(&pack);
			ret ^= typeid(CONFIGS).getHash(&configs);
			return ret;
		}
		bool opEqual(in ref TreeNodes other) const { return pack == other.pack && configs == other.configs; }
		int opCmp(in ref TreeNodes other) const {
			if (pack != other.pack) return pack < other.pack ? -1 : 1;
			if (configs != other.configs) return configs < other.configs ? -1 : 1;
			return 0;
		}
	}
 
	static struct TreeNode {
		string pack;
		CONFIG config;
 
		hash_t toHash() const nothrow @trusted {
			size_t ret = typeid(string).getHash(&pack);
			ret ^= typeid(CONFIG).getHash(&config);
			return ret;
		}
		bool opEqual(in ref TreeNode other) const { return pack == other.pack && config == other.config; }
		int opCmp(in ref TreeNode other) const {
			if (pack != other.pack) return pack < other.pack ? -1 : 1;
			if (config != other.config) return config < other.config ? -1 : 1;
			return 0;
		}
	}
 
	CONFIG[string] resolve(TreeNode root, bool throw_on_failure = true)
	{
		auto root_base_pack = basePackage(root.pack);
 
		// find all possible configurations of each possible dependency
		size_t[string] package_indices;
		string[size_t] package_names;
		CONFIG[][] all_configs;
		bool[] any_config;
		bool[string] maybe_optional_deps;
		bool[TreeNode] visited;
 
		void findConfigsRec(TreeNode parent, bool parent_unique)
		{
			if (parent in visited) return;
			visited[parent] = true;
 
			foreach (ch; getChildren(parent)) {
				auto basepack = basePackage(ch.pack);
				auto pidx = all_configs.length;
 
				if (ch.depType != DependencyType.required) maybe_optional_deps[ch.pack] = true;
 
				CONFIG[] configs;
				if (auto pi = basepack in package_indices) {
					pidx = *pi;
					configs = all_configs[*pi];
				} else {
					if (basepack == root_base_pack) configs = [root.config];
					else configs = getAllConfigs(basepack);
					all_configs ~= configs;
					package_indices[basepack] = pidx;
					package_names[pidx] = basepack;
				}
 
				foreach (c; getSpecificConfigs(basepack, ch))
					if (!configs.canFind(c))
						configs = c ~ configs;
 
				if (any_config.length <= pidx) any_config.length = pidx+1;
				any_config[pidx] = configs.length > 0;
 
				// eliminate configurations from which we know that they can't satisfy
				// the uniquely defined root dependencies (==version or ~branch style dependencies)
				if (parent_unique) configs = configs.filter!(c => matches(ch.configs, c)).array;
 
				all_configs[pidx] = configs;
 
				foreach (v; configs)
					findConfigsRec(TreeNode(ch.pack, v), parent_unique && configs.length == 1);
			}
		}
		findConfigsRec(root, true);
 
		// append an invalid configuration to denote an unchosen dependency
		// this is used to properly support optional dependencies (when
		// getChildren() returns no configurations for an optional dependency,
		// but getAllConfigs() has already provided an existing list of configs)
		foreach (i, ref cfgs; all_configs)
			if (cfgs.length == 0 || package_names[i] in maybe_optional_deps)
				cfgs = cfgs ~ CONFIG.invalid;
 
		logDebug("Configurations used for dependency resolution:");
		foreach (n, i; package_indices) logDebug("  %s (%s%s): %s", n, i, n in maybe_optional_deps ? ", maybe optional" : ", required", all_configs[i]);
 
		auto config_indices = new size_t[all_configs.length];
		config_indices[] = 0;
 
		string last_error;
 
		visited = null;
		sizediff_t validateConfigs(TreeNode parent, ref string error)
		{
			import std.algorithm : max;
 
			if (parent in visited) return -1;
 
			visited[parent] = true;
			sizediff_t maxcpi = -1;
			sizediff_t parentidx = package_indices.get(basePackage(parent.pack), -1);
			auto parentbase = basePackage(parent.pack);
 
			// loop over all dependencies
			foreach (ch; getChildren(parent)) {
				auto basepack = basePackage(ch.pack);
				assert(basepack in package_indices, format("%s not in packages %s", basepack, package_indices));
 
				// get the current config/version of the current dependency
				sizediff_t childidx = package_indices[basepack];
				if (all_configs[childidx] == [CONFIG.invalid]) {
					// ignore invalid optional dependencies
					if (ch.depType != DependencyType.required)
						continue;
 
					if (parentbase == root_base_pack) {
						import std.uni : toLower;
						auto lp = ch.pack.toLower();
						if (lp != ch.pack) {
							logError("Dependency \"%s\" of %s contains upper case letters, but must be lower case.", ch.pack, parent.pack);
							if (getAllConfigs(lp).length) logError("Did you mean \"%s\"?", lp);
						}
						bool pvalid = any_config[childidx];
						if (pvalid)
							throw new Exception(format("Root package %s reference %s %s cannot be satisfied.", parent.pack, ch.pack, ch.configs));
						else
							throw new Exception(format("Root package %s references unknown package %s", parent.pack, ch.pack));
					}
					// choose another parent config to avoid the invalid child
					if (parentidx > maxcpi) {
						error = format("Package %s contains invalid dependency %s", parent.pack, ch.pack);
						logDiagnostic("%s (ci=%s)", error, parentidx);
						maxcpi = parentidx;
					}
				} else {
					auto config = all_configs[childidx][config_indices[childidx]];
					auto chnode = TreeNode(ch.pack, config);
 
					if (config == CONFIG.invalid || !matches(ch.configs, config)) {
						// ignore missing optional dependencies
						if (config == CONFIG.invalid && ch.depType != DependencyType.required)
							continue;
 
						// if we are at the root level, we can safely skip the maxcpi computation and instead choose another childidx config
						if (parentbase == root_base_pack) {
							error = format("No match for dependency %s %s of %s", ch.pack, ch.configs, parent.pack);
							return childidx;
						}
 
						if (childidx > maxcpi) {
							maxcpi = max(childidx, parentidx);
							error = format("Dependency %s -> %s %s mismatches with selected version %s", parent.pack, ch.pack, ch.configs, config);
							logDebug("%s (ci=%s)", error, maxcpi);
						}
 
						// we know that either the child or the parent needs to be switched
						// to another configuration, no need to continue with other children
						if (config == CONFIG.invalid) break;
					}
 
					maxcpi = max(maxcpi, validateConfigs(chnode, error));
				}
			}
			return maxcpi;
		}
 
		string first_error;
 
		while (true) {
			// check if the current combination of configurations works out
			visited = null;
			string error;
			auto conflict_index = validateConfigs(root, error);
			if (first_error !is null) first_error = error;
 
			// print out current iteration state
			logDebug("Interation (ci=%s) %s", conflict_index, {
				import std.array : join;
				auto cs = new string[all_configs.length];
				foreach (p, i; package_indices) {
					if (all_configs[i].length)
						cs[i] = p~" "~all_configs[i][config_indices[i]].to!string~(i >= 0 && i >= conflict_index ? " (C)" : "");
					else cs[i] = p ~ " [no config]";
				}
				return cs.join(", ");
			}());
 
			if (conflict_index < 0) {
				CONFIG[string] ret;
				foreach (p, i; package_indices)
					if (all_configs[i].length) {
						auto cfg = all_configs[i][config_indices[i]];
						if (cfg != CONFIG.invalid) ret[p] = cfg;
					}
				logDebug("Resolved dependencies before optional-purge: %s", ret.byKey.map!(k => k~" "~ret[k].to!string));
				purgeOptionalDependencies(root, ret);
				logDebug("Resolved dependencies after optional-purge: %s", ret.byKey.map!(k => k~" "~ret[k].to!string));
				return ret;
			}
 
			// find the next combination of configurations
			foreach_reverse (pi, ref i; config_indices) {
				if (pi > conflict_index) i = 0;
				else if (++i >= all_configs[pi].length) i = 0;
				else break;
			}
			if (config_indices.all!"a==0") {
				if (throw_on_failure) throw new Exception("Could not find a valid dependency tree configuration: "~first_error);
				else return null;
			}
		}
	}
 
	protected abstract CONFIG[] getAllConfigs(string pack);
	protected abstract CONFIG[] getSpecificConfigs(string pack, TreeNodes nodes);
	protected abstract TreeNodes[] getChildren(TreeNode node);
	protected abstract bool matches(CONFIGS configs, CONFIG config);
 
	private void purgeOptionalDependencies(TreeNode root, ref CONFIG[string] configs)
	{
		bool[string] required;
 
		void markRecursively(TreeNode node)
		{
			if (node.pack in required) return;
			required[basePackage(node.pack)] = true;
			foreach (dep; getChildren(node).filter!(dep => dep.depType != DependencyType.optional))
				if (auto dp = basePackage(dep.pack) in configs)
					markRecursively(TreeNode(dep.pack, *dp));
		}
 
		// recursively mark all required dependencies of the concrete dependency tree
		markRecursively(root);
 
		// remove all un-marked configurations
		foreach (p; configs.keys.dup)
			if (p !in required)
				configs.remove(p);
	}
}
 
enum DependencyType {
	required,
	optionalDefault,
	optional
}
 
private string basePackage(string p)
{
	auto idx = indexOf(p, ":");
	if (idx < 0) return p;
	return p[0 .. idx];
}
 
 
unittest {
	static struct IntConfig {
		int value;
		alias value this;
		enum invalid = IntConfig(-1);
	}
	static IntConfig ic(int v) { return IntConfig(v); }
	static struct IntConfigs {
		IntConfig[] configs;
		alias configs this;
	}
	static IntConfigs ics(IntConfig[] cfgs) { return IntConfigs(cfgs); }
 
	static class TestResolver : DependencyResolver!(IntConfigs, IntConfig) {
		private TreeNodes[][string] m_children;
		this(TreeNodes[][string] children) { m_children = children; }
		protected override IntConfig[] getAllConfigs(string pack) {
			auto ret = appender!(IntConfig[]);
			foreach (p; m_children.byKey) {
				if (p.length <= pack.length+1) continue;
				if (p[0 .. pack.length] != pack || p[pack.length] != ':') continue;
				auto didx = p.lastIndexOf(':');
				ret ~= ic(p[didx+1 .. $].to!uint);
			}
			ret.data.sort!"a>b"();
			return ret.data;
		}
		protected override IntConfig[] getSpecificConfigs(string pack, TreeNodes nodes) { return null; }
		protected override TreeNodes[] getChildren(TreeNode node) { return m_children.get(node.pack ~ ":" ~ node.config.to!string(), null); }
		protected override bool matches(IntConfigs configs, IntConfig config) { return configs.canFind(config); }
	}
 
	// properly back up if conflicts are detected along the way (d:2 vs d:1)
	with (TestResolver) {
		auto res = new TestResolver([
			"a:0": [TreeNodes("b", ics([ic(2), ic(1)])), TreeNodes("d", ics([ic(1)])), TreeNodes("e", ics([ic(2), ic(1)]))],
			"b:1": [TreeNodes("c", ics([ic(2), ic(1)])), TreeNodes("d", ics([ic(1)]))],
			"b:2": [TreeNodes("c", ics([ic(3), ic(2)])), TreeNodes("d", ics([ic(2), ic(1)]))],
			"c:1": [], "c:2": [], "c:3": [],
			"d:1": [], "d:2": [],
			"e:1": [], "e:2": [],
		]);
		assert(res.resolve(TreeNode("a", ic(0))) == ["b":ic(2), "c":ic(3), "d":ic(1), "e":ic(2)], format("%s", res.resolve(TreeNode("a", ic(0)))));
	}
 
	// handle cyclic dependencies gracefully
	with (TestResolver) {
		auto res = new TestResolver([
			"a:0": [TreeNodes("b", ics([ic(1)]))],
			"b:1": [TreeNodes("b", ics([ic(1)]))]
		]);
		assert(res.resolve(TreeNode("a", ic(0))) == ["b":ic(1)]);
	}
 
	// don't choose optional dependencies by default
	with (TestResolver) {
		auto res = new TestResolver([
			"a:0": [TreeNodes("b", ics([ic(1)]), DependencyType.optional)],
			"b:1": []
		]);
		assert(res.resolve(TreeNode("a", ic(0))).length == 0, to!string(res.resolve(TreeNode("a", ic(0)))));
	}
 
	// choose default optional dependencies by default
	with (TestResolver) {
		auto res = new TestResolver([
			"a:0": [TreeNodes("b", ics([ic(1)]), DependencyType.optionalDefault)],
			"b:1": []
		]);
		assert(res.resolve(TreeNode("a", ic(0))) == ["b":ic(1)], to!string(res.resolve(TreeNode("a", ic(0)))));
	}
 
	// choose optional dependency if non-optional within the dependency tree
	with (TestResolver) {
		auto res = new TestResolver([
			"a:0": [TreeNodes("b", ics([ic(1)]), DependencyType.optional), TreeNodes("c", ics([ic(1)]))],
			"b:1": [],
			"c:1": [TreeNodes("b", ics([ic(1)]))]
		]);
		assert(res.resolve(TreeNode("a", ic(0))) == ["b":ic(1), "c":ic(1)], to!string(res.resolve(TreeNode("a", ic(0)))));
	}
 
	// don't choose optional dependency if non-optional outside of final dependency tree
	with (TestResolver) {
		auto res = new TestResolver([
			"a:0": [TreeNodes("b", ics([ic(1)]), DependencyType.optional)],
			"b:1": [],
			"preset:0": [TreeNodes("b", ics([ic(1)]))]
		]);
		assert(res.resolve(TreeNode("a", ic(0))).length == 0, to!string(res.resolve(TreeNode("a", ic(0)))));
	}
 
	// don't choose optional dependency if non-optional in a non-selected version
	with (TestResolver) {
		auto res = new TestResolver([
			"a:0": [TreeNodes("b", ics([ic(1), ic(2)]))],
			"b:1": [TreeNodes("c", ics([ic(1)]))],
			"b:2": [TreeNodes("c", ics([ic(1)]), DependencyType.optional)],
			"c:1": []
		]);
		assert(res.resolve(TreeNode("a", ic(0))) == ["b":ic(2)], to!string(res.resolve(TreeNode("a", ic(0)))));
	}
 
	// make sure non-satisfyable dependencies are not a problem, even if non-optional in some dependencies
	with (TestResolver) {
		auto res = new TestResolver([
			"a:0": [TreeNodes("b", ics([ic(1), ic(2)]))],
			"b:1": [TreeNodes("c", ics([ic(2)]))],
			"b:2": [TreeNodes("c", ics([ic(2)]), DependencyType.optional)],
			"c:1": []
		]);
		assert(res.resolve(TreeNode("a", ic(0))) == ["b":ic(2)], to!string(res.resolve(TreeNode("a", ic(0)))));
	}
}