1 /**
2 	Dependency configuration/version resolution algorithm.
3 
4 	Copyright: © 2014-2018 Sönke Ludwig
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 /** Resolves dependency graph with multiple configurations per package.
22 
23 	The term "configuration" can mean any kind of alternative dependency
24 	configuration of a package. In particular, it can mean different
25 	versions of a package.
26 
27 	`CONFIG` is an abstract type denoting a single configuration of a certain
28 	package, whereas `CONFIGS` denotes a set of configurations. The
29 	representation of both can be freely chosen, so that `CONFIGS` for example
30 	can be defined in terms of a version range.
31 */
32 class DependencyResolver(CONFIGS, CONFIG) {
33 	/** Encapsulates a list of outgoing edges in the dependency graph.
34 
35 		A value of this type represents a single dependency with multiple
36 		possible configurations for the target package.
37 	*/
38 	static struct TreeNodes {
39 		string pack;
40 		CONFIGS configs;
41 		DependencyType depType = DependencyType.required;
42 
43 		size_t toHash() const nothrow @trusted {
44 			size_t ret = typeid(string).getHash(&pack);
45 			ret ^= typeid(CONFIGS).getHash(&configs);
46 			return ret;
47 		}
48 		bool opEqual(in ref TreeNodes other) const { return pack == other.pack && configs == other.configs; }
49 		int opCmp(in ref TreeNodes other) const {
50 			if (pack != other.pack) return pack < other.pack ? -1 : 1;
51 			if (configs != other.configs) return configs < other.configs ? -1 : 1;
52 			return 0;
53 		}
54 	}
55 
56 	/** A single node in the dependency graph.
57 
58 		Nodes are a combination of a package and a single package configuration.
59 	*/
60 	static struct TreeNode {
61 		string pack;
62 		CONFIG config;
63 
64 		size_t toHash() const nothrow @trusted {
65 			size_t ret = pack.hashOf();
66 			ret ^= typeid(CONFIG).getHash(&config);
67 			return ret;
68 		}
69 		bool opEqual(in ref TreeNode other) const { return pack == other.pack && config == other.config; }
70 		int opCmp(in ref TreeNode other) const {
71 			if (pack != other.pack) return pack < other.pack ? -1 : 1;
72 			if (config != other.config) return config < other.config ? -1 : 1;
73 			return 0;
74 		}
75 	}
76 
77 	CONFIG[string] resolve(TreeNode root, bool throw_on_failure = true)
78 	{
79 		// Leave the possibility to opt-out from the loop limit
80 		import std.process : environment;
81 		bool no_loop_limit = environment.get("DUB_NO_RESOLVE_LIMIT") !is null;
82 
83 		auto rootbase = root.pack.basePackageName;
84 
85 		// build up the dependency graph, eliminating as many configurations/
86 		// versions as possible
87 		ResolveContext context;
88 		context.configs[rootbase] = [ResolveConfig(root.config, true)];
89 		long loop_counter = no_loop_limit ? long.max : 1_000_000;
90 		constrain(root, context, loop_counter);
91 
92 		// remove any non-default optional dependencies
93 		purgeOptionalDependencies(root, context.result);
94 
95 		// the root package is implied by the `root` argument and will not be
96 		// returned explicitly
97 		context.result.remove(rootbase);
98 
99 		logDiagnostic("Dependency resolution result:");
100 		foreach (d; context.result.keys.sort())
101 			logDiagnostic("  %s: %s", d, context.result[d]);
102 
103 		return context.result;
104 	}
105 
106 	protected abstract CONFIG[] getAllConfigs(string pack);
107 	protected abstract CONFIG[] getSpecificConfigs(string pack, TreeNodes nodes);
108 	protected abstract TreeNodes[] getChildren(TreeNode node);
109 	protected abstract bool matches(CONFIGS configs, CONFIG config);
110 
111 	private static struct ResolveConfig {
112 		CONFIG config;
113 		bool included;
114 	}
115 
116 	private static struct ResolveContext {
117 		/** Contains all packages visited by the resolution process so far.
118 
119 			The key is the qualified name of the package (base + sub)
120 		*/
121 		void[0][string] visited;
122 
123 		/// The finally chosen configurations for each package
124 		CONFIG[string] result;
125 
126 		/// The set of available configurations for each package
127 		ResolveConfig[][string] configs;
128 
129 		/// Determines if a certain package has already been processed
130 		bool isVisited(string package_) const { return (package_ in visited) !is null; }
131 
132 		/// Marks a package as processed
133 		void setVisited(string package_) { visited[package_] = (void[0]).init; }
134 
135 		/// Returns a deep clone
136 		ResolveContext clone()
137 		{
138 			ResolveContext ret;
139 			ret.visited = this.visited.dup;
140 			ret.result = this.result.dup;
141 			foreach (pack, cfgs; this.configs) {
142 				ret.configs[pack] = cfgs.dup;
143 			}
144 			return ret;
145 		}
146 	}
147 
148 
149 	/** Starting with a single node, fills `context` with a minimized set of
150 		configurations that form valid solutions.
151 	*/
152 	private void constrain(TreeNode n, ref ResolveContext context, ref long max_iterations)
153 	{
154 		auto base = n.pack.basePackageName;
155 		assert(base in context.configs);
156 		if (context.isVisited(n.pack)) return;
157 		context.setVisited(n.pack);
158 		context.result[base] = n.config;
159 		foreach (j, ref sc; context.configs[base])
160 			sc.included = sc.config == n.config;
161 
162 		auto dependencies = getChildren(n);
163 
164 		foreach (dep; dependencies) {
165 			// lazily load all dependency configurations
166 			auto depbase = dep.pack.basePackageName;
167 			auto di = depbase in context.configs;
168 			if (!di) {
169 				context.configs[depbase] =
170 					getAllConfigs(depbase)
171 					.map!(c => ResolveConfig(c, true))
172 					.array;
173 				di = depbase in context.configs;
174 			}
175 
176 			// add any dependee defined dependency configurations
177 			foreach (sc; getSpecificConfigs(n.pack, dep))
178 				if (!(*di).canFind!(c => c.config == sc))
179 					*di = ResolveConfig(sc, true) ~ *di;
180 
181 			// restrain the configurations to the current dependency spec
182 			bool any_config = false;
183 			foreach (i, ref c; *di)
184 				if (c.included) {
185 					if (!matches(dep.configs, c.config))
186 						c.included = false;
187 					else any_config = true;
188 				}
189 
190 			if (!any_config && dep.depType == DependencyType.required) {
191 				if ((*di).length)
192 					throw new ResolveException(n, dep, context);
193 				else throw new DependencyLoadException(n, dep);
194 			}
195 		}
196 
197 		constrainDependencies(n, dependencies, 0, context, max_iterations);
198 	}
199 
200 	/** Recurses back into `constrain` while recursively going through `n`'s
201 		dependencies.
202 
203 		This attempts to constrain each dependency, while keeping each of them
204 		in a nested stack frame. This allows any errors to properly back
205 		propagate.
206 	*/
207 	private void constrainDependencies(TreeNode n, TreeNodes[] dependencies, size_t depidx,
208 		ref ResolveContext context, ref long max_iterations)
209 	{
210 		if (depidx >= dependencies.length) return;
211 
212 		assert (--max_iterations > 0,
213 			"The dependency resolution process is taking too long. The"
214 			~ " dependency graph is likely hitting a pathological case in"
215 			~ " the resolution algorithm. Please file a bug report at"
216 			~ " https://github.com/dlang/dub/issues and mention the package"
217 			~ " recipe that reproduces this error.");
218 
219 		auto dep = &dependencies[depidx];
220 		auto depbase = dep.pack.basePackageName;
221 		auto depconfigs = context.configs[depbase];
222 
223 		Exception first_err;
224 
225 		// try each configuration/version of the current dependency
226 		foreach (i, c; depconfigs) {
227 			if (c.included) {
228 				try {
229 					// try the configuration on a cloned context
230 					auto subcontext = context.clone;
231 					constrain(TreeNode(dep.pack, c.config), subcontext, max_iterations);
232 					constrainDependencies(n, dependencies, depidx+1, subcontext, max_iterations);
233 					// if a branch succeeded, replace the current context
234 					// with the one from the branch and return
235 					context = subcontext;
236 					return;
237 				} catch (Exception e) {
238 					if (!first_err) first_err = e;
239 				}
240 			}
241 		}
242 
243 		// ignore unsatisfiable optional dependencies
244 		if (dep.depType != DependencyType.required) {
245 			auto subcontext = context.clone;
246 			constrainDependencies(n, dependencies, depidx+1, subcontext, max_iterations);
247 			context = subcontext;
248 			return;
249 		}
250 
251 		// report the first error encountered to the user
252 		if (first_err) throw first_err;
253 
254 		// should have thrown in constrainRec before reaching this
255 		assert(false, format("Got no configuration for dependency %s %s of %s %s!?",
256 			dep.pack, dep.configs, n.pack, n.config));
257 	}
258 
259 	private void purgeOptionalDependencies(TreeNode root, ref CONFIG[string] configs)
260 	{
261 		bool[string] required;
262 		bool[string] visited;
263 
264 		void markRecursively(TreeNode node)
265 		{
266 			if (node.pack in visited) return;
267 			visited[node.pack] = true;
268 			required[node.pack.basePackageName] = true;
269 			foreach (dep; getChildren(node).filter!(dep => dep.depType != DependencyType.optional))
270 				if (auto dp = dep.pack.basePackageName in configs)
271 					markRecursively(TreeNode(dep.pack, *dp));
272 		}
273 
274 		// recursively mark all required dependencies of the concrete dependency tree
275 		markRecursively(root);
276 
277 		// remove all un-marked configurations
278 		foreach (p; configs.keys.dup)
279 			if (p !in required)
280 				configs.remove(p);
281 	}
282 
283 	final class ResolveException : Exception {
284 		import std.range : chain, only;
285 		import std.typecons : tuple;
286 
287 		string failedNode;
288 
289 		this(TreeNode parent, TreeNodes dep, in ref ResolveContext context, string file = __FILE__, size_t line = __LINE__)
290 		{
291 			auto m = format("Unresolvable dependencies to package %s:", dep.pack.basePackageName);
292 			super(m, file, line);
293 
294 			this.failedNode = dep.pack;
295 
296 			auto failbase = failedNode.basePackageName;
297 
298 			// get the list of all dependencies to the failed package
299 			auto deps = context.visited.byKey
300 				.filter!(p => p.basePackageName in context.result)
301 				.map!(p => TreeNode(p, context.result[p.basePackageName]))
302 				.map!(n => getChildren(n)
303 					.filter!(d => d.pack.basePackageName == failbase)
304 					.map!(d => tuple(n, d))
305 				)
306 				.join
307 				.sort!((a, b) => a[0].pack < b[0].pack);
308 
309 			foreach (d; deps) {
310 				// filter out trivial self-dependencies
311 				if (d[0].pack.basePackageName == failbase
312 					&& matches(d[1].configs, d[0].config))
313 					continue;
314 				msg ~= format("\n  %s %s depends on %s %s", d[0].pack, d[0].config, d[1].pack, d[1].configs);
315 			}
316 		}
317 	}
318 
319 	final class DependencyLoadException : Exception {
320 		TreeNode parent;
321 		TreeNodes dependency;
322 
323 		this(TreeNode parent, TreeNodes dep)
324 		{
325 			auto m = format("Failed to find any versions for package %s, referenced by %s %s",
326 				dep.pack, parent.pack, parent.config);
327 			super(m, file, line);
328 
329 			this.parent = parent;
330 			this.dependency = dep;
331 		}
332 	}
333 }
334 
335 enum DependencyType {
336 	required,
337 	optionalDefault,
338 	optional
339 }
340 
341 private string basePackageName(string p)
342 {
343 	import std.algorithm.searching : findSplit;
344 	return p.findSplit(":")[0];
345 }
346 
347 unittest {
348 	static struct IntConfig {
349 		int value;
350 		alias value this;
351 		enum invalid = IntConfig(-1);
352 	}
353 	static IntConfig ic(int v) { return IntConfig(v); }
354 	static struct IntConfigs {
355 		IntConfig[] configs;
356 		alias configs this;
357 	}
358 	static IntConfigs ics(IntConfig[] cfgs) { return IntConfigs(cfgs); }
359 
360 	static class TestResolver : DependencyResolver!(IntConfigs, IntConfig) {
361 		private TreeNodes[][string] m_children;
362 		this(TreeNodes[][string] children) { m_children = children; }
363 		protected override IntConfig[] getAllConfigs(string pack) {
364 			auto ret = appender!(IntConfig[]);
365 			foreach (p; m_children.byKey) {
366 				if (p.length <= pack.length+1) continue;
367 				if (p[0 .. pack.length] != pack || p[pack.length] != ':') continue;
368 				auto didx = p.lastIndexOf(':');
369 				ret ~= ic(p[didx+1 .. $].to!uint);
370 			}
371 			ret.data.sort!"a>b"();
372 			return ret.data;
373 		}
374 		protected override IntConfig[] getSpecificConfigs(string pack, TreeNodes nodes) { return null; }
375 		protected override TreeNodes[] getChildren(TreeNode node) { return m_children.get(node.pack ~ ":" ~ node.config.to!string(), null); }
376 		protected override bool matches(IntConfigs configs, IntConfig config) { return configs.canFind(config); }
377 	}
378 
379 	// properly back up if conflicts are detected along the way (d:2 vs d:1)
380 	with (TestResolver) {
381 		auto res = new TestResolver([
382 			"a:0": [TreeNodes("b", ics([ic(2), ic(1)])), TreeNodes("d", ics([ic(1)])), TreeNodes("e", ics([ic(2), ic(1)]))],
383 			"b:1": [TreeNodes("c", ics([ic(2), ic(1)])), TreeNodes("d", ics([ic(1)]))],
384 			"b:2": [TreeNodes("c", ics([ic(3), ic(2)])), TreeNodes("d", ics([ic(2), ic(1)]))],
385 			"c:1": [], "c:2": [], "c:3": [],
386 			"d:1": [], "d:2": [],
387 			"e:1": [], "e:2": [],
388 		]);
389 		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)))));
390 	}
391 
392 	// handle cyclic dependencies gracefully
393 	with (TestResolver) {
394 		auto res = new TestResolver([
395 			"a:0": [TreeNodes("b", ics([ic(1)]))],
396 			"b:1": [TreeNodes("b", ics([ic(1)]))]
397 		]);
398 		assert(res.resolve(TreeNode("a", ic(0))) == ["b":ic(1)]);
399 	}
400 
401 	// don't choose optional dependencies by default
402 	with (TestResolver) {
403 		auto res = new TestResolver([
404 			"a:0": [TreeNodes("b", ics([ic(1)]), DependencyType.optional)],
405 			"b:1": []
406 		]);
407 		assert(res.resolve(TreeNode("a", ic(0))).length == 0, to!string(res.resolve(TreeNode("a", ic(0)))));
408 	}
409 
410 	// choose default optional dependencies by default
411 	with (TestResolver) {
412 		auto res = new TestResolver([
413 			"a:0": [TreeNodes("b", ics([ic(1)]), DependencyType.optionalDefault)],
414 			"b:1": []
415 		]);
416 		assert(res.resolve(TreeNode("a", ic(0))) == ["b":ic(1)], to!string(res.resolve(TreeNode("a", ic(0)))));
417 	}
418 
419 	// choose optional dependency if non-optional within the dependency tree
420 	with (TestResolver) {
421 		auto res = new TestResolver([
422 			"a:0": [TreeNodes("b", ics([ic(1)]), DependencyType.optional), TreeNodes("c", ics([ic(1)]))],
423 			"b:1": [],
424 			"c:1": [TreeNodes("b", ics([ic(1)]))]
425 		]);
426 		assert(res.resolve(TreeNode("a", ic(0))) == ["b":ic(1), "c":ic(1)], to!string(res.resolve(TreeNode("a", ic(0)))));
427 	}
428 
429 	// don't choose optional dependency if non-optional outside of final dependency tree
430 	with (TestResolver) {
431 		auto res = new TestResolver([
432 			"a:0": [TreeNodes("b", ics([ic(1)]), DependencyType.optional)],
433 			"b:1": [],
434 			"preset:0": [TreeNodes("b", ics([ic(1)]))]
435 		]);
436 		assert(res.resolve(TreeNode("a", ic(0))).length == 0, to!string(res.resolve(TreeNode("a", ic(0)))));
437 	}
438 
439 	// don't choose optional dependency if non-optional in a non-selected version
440 	with (TestResolver) {
441 		auto res = new TestResolver([
442 			"a:0": [TreeNodes("b", ics([ic(1), ic(2)]))],
443 			"b:1": [TreeNodes("c", ics([ic(1)]))],
444 			"b:2": [TreeNodes("c", ics([ic(1)]), DependencyType.optional)],
445 			"c:1": []
446 		]);
447 		assert(res.resolve(TreeNode("a", ic(0))) == ["b":ic(2)], to!string(res.resolve(TreeNode("a", ic(0)))));
448 	}
449 
450 	// make sure non-satisfiable dependencies are not a problem, even if non-optional in some dependencies
451 	with (TestResolver) {
452 		auto res = new TestResolver([
453 			"a:0": [TreeNodes("b", ics([ic(1), ic(2)]))],
454 			"b:1": [TreeNodes("c", ics([ic(2)]))],
455 			"b:2": [TreeNodes("c", ics([ic(2)]), DependencyType.optional)],
456 			"c:1": []
457 		]);
458 		assert(res.resolve(TreeNode("a", ic(0))) == ["b":ic(2)], to!string(res.resolve(TreeNode("a", ic(0)))));
459 	}
460 
461 	// check error message for multiple conflicting dependencies
462 	with (TestResolver) {
463 		auto res = new TestResolver([
464 			"a:0": [TreeNodes("b", ics([ic(1)])), TreeNodes("c", ics([ic(1)]))],
465 			"b:1": [TreeNodes("d", ics([ic(1)]))],
466 			"c:1": [TreeNodes("d", ics([ic(2)]))],
467 			"d:1": [],
468 			"d:2": []
469 		]);
470 		try {
471 			res.resolve(TreeNode("a", ic(0)));
472 			assert(false, "Expected resolve to throw.");
473 		} catch (ResolveException e) {
474 			assert(e.msg ==
475 				"Unresolvable dependencies to package d:"
476 				~ "\n  b 1 depends on d [1]"
477 				~ "\n  c 1 depends on d [2]");
478 		}
479 	}
480 
481 	// check error message for invalid dependency
482 	with (TestResolver) {
483 		auto res = new TestResolver([
484 			"a:0": [TreeNodes("b", ics([ic(1)]))]
485 		]);
486 		try {
487 			res.resolve(TreeNode("a", ic(0)));
488 			assert(false, "Expected resolve to throw.");
489 		} catch (DependencyLoadException e) {
490 			assert(e.msg == "Failed to find any versions for package b, referenced by a 0");
491 		}
492 	}
493 
494 	// regression: unresolvable optional dependency skips the remaining dependencies
495 	with (TestResolver) {
496 		auto res = new TestResolver([
497 			"a:0": [
498 				TreeNodes("b", ics([ic(2)]), DependencyType.optional),
499 				TreeNodes("c", ics([ic(1)]))
500 			],
501 			"b:1": [],
502 			"c:1": []
503 		]);
504 		assert(res.resolve(TreeNode("a", ic(0))) == ["c":ic(1)]);
505 	}
506 }