Skip to content

Instantly share code, notes, and snippets.

@TilBlechschmidt

TilBlechschmidt/DependencyResolver.js

Last active October 22, 2018 14:56
Show Gist options
  • Save TilBlechschmidt/a7c60a8b87525bba3c2f3f3e780ece7f to your computer and use it in GitHub Desktop.
Save TilBlechschmidt/a7c60a8b87525bba3c2f3f3e780ece7f to your computer and use it in GitHub Desktop.
Download ZIP
Dependency resolver written for KSPackage-lib
Raw
DependencyResolver.js
import { flatten } from "./helpers";
export default class DependencyResolver {
tree = {};
resolvableSets = [];
constructor(featuresToResolve: [string], getDependency, resolveDependencyChoices) {
// Add the features we want to resolve to the tree root
featuresToResolve.forEach(feature => this.tree[feature] = null);
this.getDependency = getDependency;
this.resolveDependencyChoices = resolveDependencyChoices;
}
resolveLeaf(treeBranch) {
return Object.keys(treeBranch).reduce((result, subBranch) => {
// SubBranch is not yet resolved. Do so now!
if (treeBranch[subBranch] === null) {
// Resolve the dependencies
let dependency = this.getDependency(subBranch);
treeBranch[subBranch] = {};
if (dependency.depends !== undefined) {
for (let subDependency in dependency.depends) {
if (!dependency.depends.hasOwnProperty(subDependency)) continue;
subDependency = dependency.depends[subDependency];
let choices = this.resolveDependencyChoices(subDependency);
if (choices.length > 1) {
// Insert all the choices
treeBranch[subBranch][subDependency] = choices.map(choice => choice.identifier);
} else if (choices.length < 1) {
// This branch won't lead anywhere
return false;
} else {
// Initialize the leaf of the subBranch with the only choice
treeBranch[subBranch][choices[0].identifier] = null;
}
}
}
return result && this.resolveLeaf(treeBranch[subBranch]);
} else if (!(treeBranch[subBranch] instanceof Array) && Object.keys(treeBranch[subBranch]).length > 0) {
// Go further down the tree
return result && this.resolveLeaf(treeBranch[subBranch]);
}
return result;
}, true);
}
static getReferenceToFirstChoice(treeBranch, parentMod) {
for (let subBranch in treeBranch) {
if (!treeBranch.hasOwnProperty(subBranch)) continue;
if (treeBranch[subBranch] instanceof Array) {
return {
mod: parentMod,
feature: subBranch,
choices: treeBranch[subBranch],
select: choice => {
delete treeBranch[subBranch];
treeBranch[choice] = null;
}
}
} else {
const result = DependencyResolver.getReferenceToFirstChoice(treeBranch[subBranch], subBranch);
if (result instanceof Object) return result;
}
}
return undefined;
}
static insertFirstAvailableChoice(fullTree, treeBranch) {
for (let subBranch in treeBranch) {
if (!treeBranch.hasOwnProperty(subBranch)) continue;
if (treeBranch[subBranch] instanceof Array) {
// Return a set of full trees that have a choice selected
const choices = treeBranch[subBranch];
const choiceTrees = choices.map(choice => {
// Make a backup
let subBranchData = treeBranch[subBranch];
// Modify the tree
delete treeBranch[subBranch];
treeBranch[choice] = null;
// Create a copy
let treeCopy = JSON.parse(JSON.stringify(fullTree));
// Revert what we've done
treeBranch[subBranch] = subBranchData;
delete treeBranch[choice];
// Return the copy
return treeCopy;
});
treeBranch[subBranch] = choices;
return choiceTrees;
} else {
const result = DependencyResolver.insertFirstAvailableChoice(fullTree, treeBranch[subBranch]);
if (result instanceof Object) return result;
}
}
return false;
}
static doesTreeContainChoice(treeBranch) {
let result = false;
for (let subBranch in treeBranch) {
if (!treeBranch.hasOwnProperty(subBranch)) continue;
if (treeBranch[subBranch] instanceof Array) {
return true;
} else {
result = result || DependencyResolver.doesTreeContainChoice(treeBranch[subBranch]);
if (result) return true;
}
}
return result;
}
convertChoicesToTrees(tree) {
if (!this.resolveLeaf(tree)) return [];
if (DependencyResolver.doesTreeContainChoice(tree)) {
// [Tree]
let trees = DependencyResolver.insertFirstAvailableChoice(tree, tree);
// [[Tree]]
let choiceInlinedTrees = trees.map(tree => this.convertChoicesToTrees(tree));
return flatten(choiceInlinedTrees);
} else {
return [tree];
}
}
static flattenTreeIntoSet(tree) {
let flattenTree = (set, tree) => {
Object.keys(tree).forEach(dependency => {
if (tree[dependency] instanceof Array) return;
// Add all elements at the current level
set.add(dependency);
// Process subTrees
if (tree[dependency] !== null) flattenTree(set, tree[dependency]);
});
};
let set = new Set();
flattenTree(set, tree);
return set;
}
isSetConflicting(set) {
for (let item of set) {
let conflicts = this.getDependency(item).conflicts;
if (conflicts instanceof Array) {
for (let conflict in conflicts) {
if (conflicts.hasOwnProperty(conflict) && set.has(conflicts[conflict])) {
return true;
}
}
}
}
return false;
}
isChoiceResolvable(choice) {
return this.resolvableSets.reduce((acc, set) => acc || set.has(choice), false);
}
buildDependencyTrees() {
// Recursively resolve the tree and build a tree for each combination of choices
let allTrees = this.convertChoicesToTrees(this.tree);
// Flatten every tree into a set of mods
let allTreesFlattened = allTrees.map(DependencyResolver.flattenTreeIntoSet);
// Throw out sets with conflicts in them
this.resolvableSets = allTreesFlattened.filter(set => !this.isSetConflicting(set));
}
resolveNextChoice() {
// Resolve the tree as far as possible
this.resolveLeaf(this.tree);
// Get the first available choice
const choice = DependencyResolver.getReferenceToFirstChoice(this.tree);
if (!choice) return undefined;
// Filter choice.choices by looking at this.resolvableSets
const { choices, unresolvableChoices } = choice.choices.reduce((result, choice) => {
if (this.isChoiceResolvable(choice)) result.choices.push(choice);
else result.unresolvableChoices.push(choice);
return result;
}, { choices: [], unresolvableChoices: [] });
choice.choices = choices;
choice.unresolvableChoices = unresolvableChoices;
// Additionally extend choice.select by filtering this.resolvableSets by the resulting tree.
const originalFunction = choice.select;
choice.select = choice => {
originalFunction(choice);
const currentSet = DependencyResolver.flattenTreeIntoSet(this.tree);
this.resolvableSets = this.resolvableSets.filter(set => {
return [...currentSet.keys()].reduce((result, queuedMod) => set.has(queuedMod) && result, true);
});
};
return choice;
}
};
Raw
ExampleUsage.js
import DependencyResolver from "./DependencyResolver";
const deps = [
{
identifier: "a",
depends: ["z", "f"]
},
{
identifier: "x",
provides: ["z"],
conflicts: ["u", "v"]
},
{
identifier: "y",
provides: ["z"],
depends: ["j"]
},
{ identifier: "i", provides: ["j"] },
{ identifier: "r", provides: ["j"] },
// This should get nuked since 'o' doesn't exist
{ identifier: "k", provides: ["j"], depends: ["o"] },
{
identifier: "b",
depends: ["g"]
},
{
identifier: "u",
provides: ["g"],
conflicts: ["x"]
},
{
identifier: "v",
provides: ["g"],
conflicts: ["x"]
},
{
identifier: "c",
depends: ["d", "e"]
},
{ identifier: "e" },
{ identifier: "d", depends: ["f"] },
{ identifier: "f" }
];
const resolveDependencyChoices = dependencyIdentifier => {
return deps.filter(x =>
x.identifier === dependencyIdentifier
|| (x.provides !== undefined && x.provides.indexOf(dependencyIdentifier) > -1)
);
};
const getDependency = dependencyIdentifier => {
return deps.find(x => x.identifier === dependencyIdentifier);
};
const depRes = new DependencyResolver(["a", "b", "c"], getDependency, resolveDependencyChoices);
depRes.buildDependencyTrees();
let choice = depRes.resolveNextChoice();
while (choice !== undefined) {
// TODO Ask the user right here
choice.select(choice.choices[0]);
choice = depRes.resolveNextChoice();
}
console.log(DependencyResolver.flattenTreeIntoSet(depRes.tree));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment