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