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 }