1 /**
2 	Dependency configuration/version resolution algorithm.
3 
4 	Copyright: © 2014 rejectedsoftware e.K.
5 	License: Subject to the terms of the MIT license, as written in the included LICENSE.txt file.
6 	Authors: Sönke Ludwig
7 */
8 module dub.dependencyresolver;
9 
10 import dub.dependency;
11 import dub.internal.vibecompat.core.log;
12 
13 import std.algorithm : all, canFind, filter, map, sort;
14 import std.array : appender, array, join;
15 import std.conv : to;
16 import std.exception : enforce;
17 import std.typecons : Nullable;
18 import std..string : format, indexOf, lastIndexOf;
19 
20 
21 class DependencyResolver(CONFIGS, CONFIG) {
22 	static struct TreeNodes {
23 		string pack;
24 		CONFIGS configs;
25 		DependencyType depType = DependencyType.required;
26 
27 		hash_t toHash() const nothrow @trusted {
28 			size_t ret = typeid(string).getHash(&pack);
29 			ret ^= typeid(CONFIGS).getHash(&configs);
30 			return ret;
31 		}
32 		bool opEqual(in ref TreeNodes other) const { return pack == other.pack && configs == other.configs; }
33 		int opCmp(in ref TreeNodes other) const {
34 			if (pack != other.pack) return pack < other.pack ? -1 : 1;
35 			if (configs != other.configs) return configs < other.configs ? -1 : 1;
36 			return 0;
37 		}
38 	}
39 
40 	static struct TreeNode {
41 		string pack;
42 		CONFIG config;
43 
44 		hash_t toHash() const nothrow @trusted {
45 			size_t ret = pack.hashOf();
46 			ret ^= typeid(CONFIG).getHash(&config);
47 			return ret;
48 		}
49 		bool opEqual(in ref TreeNode other) const { return pack == other.pack && config == other.config; }
50 		int opCmp(in ref TreeNode other) const {
51 			if (pack != other.pack) return pack < other.pack ? -1 : 1;
52 			if (config != other.config) return config < other.config ? -1 : 1;
53 			return 0;
54 		}
55 	}
56 
57 	private static struct PackageConfigs
58 	{
59 		static struct Depender
60 		{
61 			TreeNode origin;
62 			TreeNodes dependency;
63 		}
64 
65 		// all possible configurations to test for this package
66 		CONFIG[] allConfigs;
67 
68 		// determines whether this package has any dependencies, may be
69 		// different from allConfigs.length > 0 after certain configurations
70 		// have been filtered out
71 		bool anyConfig;
72 
73 		Depender[] origins;
74 	}
75 
76 	CONFIG[string] resolve(TreeNode root, bool throw_on_failure = true)
77 	{
78 		auto root_base_pack = basePackage(root.pack);
79 
80 		// find all possible configurations of each possible dependency
81 		size_t[string] package_indices;
82 		string[size_t] package_names;
83 		PackageConfigs[] configs;
84 		bool[string] maybe_optional_deps;
85 		bool[TreeNode] visited;
86 
87 		void findConfigsRec(TreeNode parent, bool parent_unique)
88 		{
89 			if (parent in visited) return;
90 			visited[parent] = true;
91 
92 			foreach (ch; getChildren(parent)) {
93 				auto basepack = basePackage(ch.pack);
94 				auto pidx = configs.length;
95 
96 				if (ch.depType != DependencyType.required) maybe_optional_deps[ch.pack] = true;
97 
98 				PackageConfigs config;
99 				if (auto pi = basepack in package_indices) {
100 					pidx = *pi;
101 					config = configs[*pi];
102 				} else {
103 					if (basepack == root_base_pack) config.allConfigs = [root.config];
104 					else config.allConfigs = getAllConfigs(basepack);
105 					configs ~= config;
106 					package_indices[basepack] = pidx;
107 					package_names[pidx] = basepack;
108 				}
109 
110 				foreach (c; getSpecificConfigs(basepack, ch))
111 					if (!config.allConfigs.canFind(c))
112 						config.allConfigs = c ~ config.allConfigs;
113 
114 				if (config.allConfigs.length > 0)
115 					config.anyConfig = true;
116 
117 				// store package depending on this for better error messages
118 				config.origins ~= PackageConfigs.Depender(parent, ch);
119 
120 				// eliminate configurations from which we know that they can't satisfy
121 				// the uniquely defined root dependencies (==version or ~branch style dependencies)
122 				if (parent_unique) config.allConfigs = config.allConfigs.filter!(c => matches(ch.configs, c)).array;
123 
124 				configs[pidx] = config;
125 
126 				foreach (v; config.allConfigs)
127 					findConfigsRec(TreeNode(ch.pack, v), parent_unique && config.allConfigs.length == 1);
128 			}
129 		}
130 		findConfigsRec(root, true);
131 
132 		// append an invalid configuration to denote an unchosen dependency
133 		// this is used to properly support optional dependencies (when
134 		// getChildren() returns no configurations for an optional dependency,
135 		// but getAllConfigs() has already provided an existing list of configs)
136 		foreach (i, ref cfgs; configs)
137 			if (cfgs.allConfigs.length == 0 || package_names[i] in maybe_optional_deps)
138 				cfgs.allConfigs = cfgs.allConfigs ~ CONFIG.invalid;
139 
140 		logDebug("Configurations used for dependency resolution:");
141 		foreach (n, i; package_indices) logDebug("  %s (%s%s): %s", n, i, n in maybe_optional_deps ? ", maybe optional" : ", required", configs[i]);
142 
143 		auto config_indices = new size_t[configs.length];
144 		config_indices[] = 0;
145 
146 		visited = null;
147 		sizediff_t validateConfigs(TreeNode parent, ref ConflictError error)
148 		{
149 			import std.algorithm : max;
150 
151 			if (parent in visited) return -1;
152 
153 			visited[parent] = true;
154 			sizediff_t maxcpi = -1;
155 			sizediff_t parentidx = package_indices.get(basePackage(parent.pack), -1);
156 			auto parentbase = basePackage(parent.pack);
157 
158 			// loop over all dependencies
159 			foreach (ch; getChildren(parent)) {
160 				auto basepack = basePackage(ch.pack);
161 				assert(basepack in package_indices, format("%s not in packages %s", basepack, package_indices));
162 
163 				// get the current config/version of the current dependency
164 				sizediff_t childidx = package_indices[basepack];
165 				auto child = configs[childidx];
166 
167 				if (child.allConfigs.length == 1 && child.allConfigs[0] == CONFIG.invalid) {
168 					// ignore invalid optional dependencies
169 					if (ch.depType != DependencyType.required)
170 						continue;
171 
172 					if (parentbase == root_base_pack) {
173 						import std.uni : toLower;
174 						auto lp = ch.pack.toLower();
175 						if (lp != ch.pack) {
176 							logError("Dependency \"%s\" of %s contains upper case letters, but must be lower case.", ch.pack, parent.pack);
177 							if (getAllConfigs(lp).length) logError("Did you mean \"%s\"?", lp);
178 						}
179 						if (child.anyConfig)
180 							throw new Exception(format("Root package %s reference %s %s cannot be satisfied.\nPackages causing the conflict:\n\t%s",
181 								parent.pack, ch.pack, ch.configs,
182 								child.origins.map!(a => a.origin.pack ~ " depends on " ~ a.dependency.configs.to!string).join("\n\t")));
183 						else
184 							throw new Exception(format("Root package %s references unknown package %s", parent.pack, ch.pack));
185 					}
186 					// choose another parent config to avoid the invalid child
187 					if (parentidx > maxcpi) {
188 						error = ConflictError(ConflictError.Kind.invalidDependency, parent, ch, CONFIG.invalid);
189 						logDiagnostic("%s (ci=%s)", error, parentidx);
190 						maxcpi = parentidx;
191 					}
192 				} else {
193 					auto config = child.allConfigs[config_indices[childidx]];
194 					auto chnode = TreeNode(ch.pack, config);
195 
196 					if (config == CONFIG.invalid || !matches(ch.configs, config)) {
197 						// ignore missing optional dependencies
198 						if (config == CONFIG.invalid && ch.depType != DependencyType.required)
199 							continue;
200 
201 						// if we are at the root level, we can safely skip the maxcpi computation and instead choose another childidx config
202 						if (parentbase == root_base_pack) {
203 							error = ConflictError(ConflictError.Kind.noRootMatch, parent, ch, config);
204 							return childidx;
205 						}
206 
207 						if (childidx > maxcpi) {
208 							maxcpi = max(childidx, parentidx);
209 							error = ConflictError(ConflictError.Kind.childMismatch, parent, ch, config);
210 							logDebug("%s (ci=%s)", error, maxcpi);
211 						}
212 
213 						// we know that either the child or the parent needs to be switched
214 						// to another configuration, no need to continue with other children
215 						if (config == CONFIG.invalid) break;
216 					}
217 
218 					maxcpi = max(maxcpi, validateConfigs(chnode, error));
219 				}
220 			}
221 			return maxcpi;
222 		}
223 
224 		Nullable!ConflictError first_error;
225 		size_t loop_counter = 0;
226 
227 		// Leave the possibility to opt-out from the loop limit
228 		import std.process : environment;
229 		bool no_loop_limit = environment.get("DUB_NO_RESOLVE_LIMIT") !is null;
230 
231 		while (true) {
232 			assert(no_loop_limit || loop_counter++ < 1_000_000,
233 				"The dependency resolution process is taking too long. The"
234 				~ " dependency graph is likely hitting a pathological case in"
235 				~ " the resolution algorithm. Please file a bug report at"
236 				~ " https://github.com/dlang/dub/issues and mention the package"
237 				~ " recipe that reproduces this error.");
238 
239 			// check if the current combination of configurations works out
240 			visited = null;
241 			ConflictError error;
242 			auto conflict_index = validateConfigs(root, error);
243 			if (first_error.isNull) first_error = error;
244 
245 			// print out current iteration state
246 			logDebug("Interation (ci=%s) %s", conflict_index, {
247 				import std.array : join;
248 				auto cs = new string[configs.length];
249 				foreach (p, i; package_indices) {
250 					if (configs[i].allConfigs.length)
251 						cs[i] = p~" "~configs[i].allConfigs[config_indices[i]].to!string~(i >= 0 && i >= conflict_index ? " (C)" : "");
252 					else cs[i] = p ~ " [no config]";
253 				}
254 				return cs.join(", ");
255 			}());
256 
257 			if (conflict_index < 0) {
258 				CONFIG[string] ret;
259 				foreach (p, i; package_indices)
260 					if (configs[i].allConfigs.length) {
261 						auto cfg = configs[i].allConfigs[config_indices[i]];
262 						if (cfg != CONFIG.invalid) ret[p] = cfg;
263 					}
264 				logDebug("Resolved dependencies before optional-purge: %s", ret.byKey.map!(k => k~" "~ret[k].to!string));
265 				purgeOptionalDependencies(root, ret);
266 				logDebug("Resolved dependencies after optional-purge: %s", ret.byKey.map!(k => k~" "~ret[k].to!string));
267 				return ret;
268 			}
269 
270 			// find the next combination of configurations
271 			foreach_reverse (pi, ref i; config_indices) {
272 				if (pi > conflict_index) i = 0;
273 				else if (++i >= configs[pi].allConfigs.length) i = 0;
274 				else break;
275 			}
276 			if (config_indices.all!"a==0") {
277 				if (throw_on_failure) throw new Exception(format("Could not find a valid dependency tree configuration: %s", first_error.get));
278 				else return null;
279 			}
280 		}
281 	}
282 
283 	protected abstract CONFIG[] getAllConfigs(string pack);
284 	protected abstract CONFIG[] getSpecificConfigs(string pack, TreeNodes nodes);
285 	protected abstract TreeNodes[] getChildren(TreeNode node);
286 	protected abstract bool matches(CONFIGS configs, CONFIG config);
287 
288 	private void purgeOptionalDependencies(TreeNode root, ref CONFIG[string] configs)
289 	{
290 		bool[string] required;
291 		bool[string] visited;
292 
293 		void markRecursively(TreeNode node)
294 		{
295 			if (node.pack in visited) return;
296 			visited[node.pack] = true;
297 			required[basePackage(node.pack)] = true;
298 			foreach (dep; getChildren(node).filter!(dep => dep.depType != DependencyType.optional))
299 				if (auto dp = basePackage(dep.pack) in configs)
300 					markRecursively(TreeNode(dep.pack, *dp));
301 		}
302 
303 		// recursively mark all required dependencies of the concrete dependency tree
304 		markRecursively(root);
305 
306 		// remove all un-marked configurations
307 		foreach (p; configs.keys.dup)
308 			if (p !in required)
309 				configs.remove(p);
310 	}
311 
312 	private struct ConflictError {
313 		enum Kind {
314 			none,
315 			noRootMatch,
316 			childMismatch,
317 			invalidDependency
318 		}
319 
320 		Kind kind;
321 		TreeNode parent;
322 		TreeNodes child;
323 		CONFIG config;
324 
325 		string toString()
326 		const {
327 			final switch (kind) {
328 				case Kind.none: return "no error";
329 				case Kind.noRootMatch:
330 					return "No match for dependency %s %s of %s"
331 						.format(child.pack, child.configs, parent.pack);
332 				case Kind.childMismatch:
333 					return "Dependency %s -> %s %s mismatches with selected version %s"
334 						.format(parent.pack, child.pack, child.configs, config);
335 				case Kind.invalidDependency:
336 					return "Package %s contains invalid dependency %s (no version candidates)"
337 						.format(parent.pack, child.pack);
338 			}
339 		}
340 	}
341 }
342 
343 enum DependencyType {
344 	required,
345 	optionalDefault,
346 	optional
347 }
348 
349 private string basePackage(string p)
350 {
351 	auto idx = indexOf(p, ':');
352 	if (idx < 0) return p;
353 	return p[0 .. idx];
354 }
355 
356 
357 unittest {
358 	static struct IntConfig {
359 		int value;
360 		alias value this;
361 		enum invalid = IntConfig(-1);
362 	}
363 	static IntConfig ic(int v) { return IntConfig(v); }
364 	static struct IntConfigs {
365 		IntConfig[] configs;
366 		alias configs this;
367 	}
368 	static IntConfigs ics(IntConfig[] cfgs) { return IntConfigs(cfgs); }
369 
370 	static class TestResolver : DependencyResolver!(IntConfigs, IntConfig) {
371 		private TreeNodes[][string] m_children;
372 		this(TreeNodes[][string] children) { m_children = children; }
373 		protected override IntConfig[] getAllConfigs(string pack) {
374 			auto ret = appender!(IntConfig[]);
375 			foreach (p; m_children.byKey) {
376 				if (p.length <= pack.length+1) continue;
377 				if (p[0 .. pack.length] != pack || p[pack.length] != ':') continue;
378 				auto didx = p.lastIndexOf(':');
379 				ret ~= ic(p[didx+1 .. $].to!uint);
380 			}
381 			ret.data.sort!"a>b"();
382 			return ret.data;
383 		}
384 		protected override IntConfig[] getSpecificConfigs(string pack, TreeNodes nodes) { return null; }
385 		protected override TreeNodes[] getChildren(TreeNode node) { return m_children.get(node.pack ~ ":" ~ node.config.to!string(), null); }
386 		protected override bool matches(IntConfigs configs, IntConfig config) { return configs.canFind(config); }
387 	}
388 
389 	// properly back up if conflicts are detected along the way (d:2 vs d:1)
390 	with (TestResolver) {
391 		auto res = new TestResolver([
392 			"a:0": [TreeNodes("b", ics([ic(2), ic(1)])), TreeNodes("d", ics([ic(1)])), TreeNodes("e", ics([ic(2), ic(1)]))],
393 			"b:1": [TreeNodes("c", ics([ic(2), ic(1)])), TreeNodes("d", ics([ic(1)]))],
394 			"b:2": [TreeNodes("c", ics([ic(3), ic(2)])), TreeNodes("d", ics([ic(2), ic(1)]))],
395 			"c:1": [], "c:2": [], "c:3": [],
396 			"d:1": [], "d:2": [],
397 			"e:1": [], "e:2": [],
398 		]);
399 		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)))));
400 	}
401 
402 	// handle cyclic dependencies gracefully
403 	with (TestResolver) {
404 		auto res = new TestResolver([
405 			"a:0": [TreeNodes("b", ics([ic(1)]))],
406 			"b:1": [TreeNodes("b", ics([ic(1)]))]
407 		]);
408 		assert(res.resolve(TreeNode("a", ic(0))) == ["b":ic(1)]);
409 	}
410 
411 	// don't choose optional dependencies by default
412 	with (TestResolver) {
413 		auto res = new TestResolver([
414 			"a:0": [TreeNodes("b", ics([ic(1)]), DependencyType.optional)],
415 			"b:1": []
416 		]);
417 		assert(res.resolve(TreeNode("a", ic(0))).length == 0, to!string(res.resolve(TreeNode("a", ic(0)))));
418 	}
419 
420 	// choose default optional dependencies by default
421 	with (TestResolver) {
422 		auto res = new TestResolver([
423 			"a:0": [TreeNodes("b", ics([ic(1)]), DependencyType.optionalDefault)],
424 			"b:1": []
425 		]);
426 		assert(res.resolve(TreeNode("a", ic(0))) == ["b":ic(1)], to!string(res.resolve(TreeNode("a", ic(0)))));
427 	}
428 
429 	// choose optional dependency if non-optional within the dependency tree
430 	with (TestResolver) {
431 		auto res = new TestResolver([
432 			"a:0": [TreeNodes("b", ics([ic(1)]), DependencyType.optional), TreeNodes("c", ics([ic(1)]))],
433 			"b:1": [],
434 			"c:1": [TreeNodes("b", ics([ic(1)]))]
435 		]);
436 		assert(res.resolve(TreeNode("a", ic(0))) == ["b":ic(1), "c":ic(1)], to!string(res.resolve(TreeNode("a", ic(0)))));
437 	}
438 
439 	// don't choose optional dependency if non-optional outside of final dependency tree
440 	with (TestResolver) {
441 		auto res = new TestResolver([
442 			"a:0": [TreeNodes("b", ics([ic(1)]), DependencyType.optional)],
443 			"b:1": [],
444 			"preset:0": [TreeNodes("b", ics([ic(1)]))]
445 		]);
446 		assert(res.resolve(TreeNode("a", ic(0))).length == 0, to!string(res.resolve(TreeNode("a", ic(0)))));
447 	}
448 
449 	// don't choose optional dependency if non-optional in a non-selected version
450 	with (TestResolver) {
451 		auto res = new TestResolver([
452 			"a:0": [TreeNodes("b", ics([ic(1), ic(2)]))],
453 			"b:1": [TreeNodes("c", ics([ic(1)]))],
454 			"b:2": [TreeNodes("c", ics([ic(1)]), DependencyType.optional)],
455 			"c:1": []
456 		]);
457 		assert(res.resolve(TreeNode("a", ic(0))) == ["b":ic(2)], to!string(res.resolve(TreeNode("a", ic(0)))));
458 	}
459 
460 	// make sure non-satisfyable dependencies are not a problem, even if non-optional in some dependencies
461 	with (TestResolver) {
462 		auto res = new TestResolver([
463 			"a:0": [TreeNodes("b", ics([ic(1), ic(2)]))],
464 			"b:1": [TreeNodes("c", ics([ic(2)]))],
465 			"b:2": [TreeNodes("c", ics([ic(2)]), DependencyType.optional)],
466 			"c:1": []
467 		]);
468 		assert(res.resolve(TreeNode("a", ic(0))) == ["b":ic(2)], to!string(res.resolve(TreeNode("a", ic(0)))));
469 	}
470 }