diff --git a/source/dub/dependencyresolver.d b/source/dub/dependencyresolver.d index 9038184..2e39a11 100644 --- a/source/dub/dependencyresolver.d +++ b/source/dub/dependencyresolver.d @@ -21,6 +21,7 @@ static struct TreeNodes { string pack; CONFIGS configs; + DependencyType depType = DependencyType.required; hash_t toHash() const nothrow @trusted { size_t ret = typeid(string).getHash(&pack); @@ -64,7 +65,9 @@ // find all possible configurations of each possible dependency size_t[string] package_indices; + string[size_t] package_names; CONFIG[][] all_configs; + bool[string] required_deps; bool[TreeNode] visited; void findConfigsRec(TreeNode parent, bool parent_unique) { @@ -74,6 +77,9 @@ foreach (ch; getChildren(parent)) { auto basepack = rootPackage(ch.pack); auto pidx = all_configs.length; + + if (ch.depType == DependencyType.required) required_deps[ch.pack] = true; + CONFIG[] configs; if (auto pi = basepack in package_indices) { pidx = *pi; @@ -83,6 +89,7 @@ else configs = getAllConfigs(basepack); all_configs ~= configs; package_indices[basepack] = pidx; + package_names[pidx] = basepack; } configs = getSpecificConfigs(ch) ~ configs; @@ -99,11 +106,13 @@ } findConfigsRec(root, true); - // prepend an invalid configuration to denote an unchosen dependency + // 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 (ref cfgs; all_configs) cfgs = CONFIG.invalid ~ cfgs; + foreach (i, ref cfgs; all_configs) + if (cfgs.length == 0 || package_names[i] !in required_deps) + cfgs = cfgs ~ CONFIG.invalid; logDebug("Configurations used for dependency resolution:"); foreach (n, i; package_indices) logDebug(" %s (%s): %s", n, i, all_configs[i]); @@ -133,6 +142,10 @@ // 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; + enforce(parentbase != root_base_pack, format("Root package %s contains reference to invalid package %s %s", parent.pack, ch.pack, ch.configs)); // choose another parent config to avoid the invalid child if (parentidx > maxcpi) { @@ -145,6 +158,10 @@ 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); @@ -196,6 +213,7 @@ auto cfg = all_configs[i][config_indices[i]]; if (cfg != CONFIG.invalid) ret[p] = cfg; } + purgeOptionalDependencies(root, ret); return ret; } @@ -216,8 +234,35 @@ protected abstract CONFIG[] getSpecificConfigs(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[node.pack] = true; + foreach (dep; getChildren(node).filter!(dep => dep.depType != DependencyType.optional)) + if (auto dp = 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 +} unittest { static struct IntConfig { @@ -226,8 +271,13 @@ 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!(IntConfig[], IntConfig) { + static class TestResolver : DependencyResolver!(IntConfigs, IntConfig) { private TreeNodes[][string] m_children; this(TreeNodes[][string] children) { m_children = children; } protected override IntConfig[] getAllConfigs(string pack) { @@ -243,15 +293,15 @@ } protected override IntConfig[] getSpecificConfigs(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(IntConfig[] configs, IntConfig config) { return configs.canFind(config); } + 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", [ic(2), ic(1)]), TreeNodes("d", [ic(1)]), TreeNodes("e", [ic(2), ic(1)])], - "b:1": [TreeNodes("c", [ic(2), ic(1)]), TreeNodes("d", [ic(1)])], - "b:2": [TreeNodes("c", [ic(3), ic(2)]), TreeNodes("d", [ic(2), ic(1)])], + "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": [], @@ -262,9 +312,47 @@ // handle cyclic dependencies gracefully with (TestResolver) { auto res = new TestResolver([ - "a:0": [TreeNodes("b", [ic(1)])], - "b:1": [TreeNodes("b", [ic(1)])] + "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))))); + } }