Skip to content

Instantly share code, notes, and snippets.

@FergusInLondon
Last active April 29, 2020 15:57
Show Gist options
  • Save FergusInLondon/3c2e9f2fbcff71ace8b3b58a28c5c39e to your computer and use it in GitHub Desktop.
Save FergusInLondon/3c2e9f2fbcff71ace8b3b58a28c5c39e to your computer and use it in GitHub Desktop.
Dependency Traversal
const target = {
"groupId": "main",
"artifactId": "root",
"parent": "main:parentOne",
"dependencies": [
"dependency:nine",
"dependency:ten",
"dependency:eleven"
]
};
const traverser = DependencyTraverser(target);
traverser.traverseToRoot();
traverser.parseDependencies();
console.log("Processing Order: ", traverser.getProcessingOrder());
console.log("Number of Nodes: ", traverser.getNumberOfNodes());
console.log("Dependency Tree: ", traverser.getTree());
const _ = require("lodash");
const fixtures = require("./fixtures.js");
/**
* Simple object capable of demonstrating how to build a dependency tree
* from a POM-like structure; using BFS (queue based).
*/
function DependencyTraverser(targetObject = {})
{
/** Queue containing dependencies to process */
let queue = [];
/** Internal Cache Object. */
let seenDependencies = {};
/** Object which will hold our final dependency tree */
let dependencyTree = {}
/** Demonstration/Debugging variables */
let numberOfNodes = 0;
let processingOrder = [];
/**
* Every item on the queue must contain: (a) an indentifier for the
* target dependency, and (b) a "chain", signifying the location
* of the dependency in the final tree.
*/
const generateDependencyQueueObject = (identifier, chain = []) => {
return{
identifier, chain
}
};
/**
* Generate an indentifier for a given dependency; version is not
* required at this level, as there will only ever be one version
* present in a given tree.
*/
const getCoords = (dep) => {
return dep.groupId + ':' + dep.artifactId;
};
const retrieveDependency = (identifier) => {
// Demonstration - just grab the data fom our fixtures.
if (seenDependencies[identifier] === undefined) {
seenDependencies[identifier] = fixtures[identifier];
}
return seenDependencies[identifier];
}
const retrieveParent = (parentIdentifier) => {
// Demonstration - just grab the data from our fixtures.
return fixtures[ parentIdentifier ];
}
/**
* Given a dependency object, and a chain, place the dependency
* in the correct location of the dependency tree.
*/
const addToTree = (dep, chain) => {
// No chain, place dependency in the root
if (chain.length < 1) {
dependencyTree[ getCoords(dep) ] = dep;
}
/* todo: insert 'depencencies' for every 2nd element */
const parentNode = _.get(dependencyTree, chain.join('.'), {});
parentNode[ getCoords(dep) ] = dep;
};
/**
* Process the dependencies found in the dependency queue (FIFO), does so
* by shifting off the first element and concatenating any subsequent
* dependencies.
*
* Operates on the queue "in-place".
*/
const processDepQueue = () => {
let queueEntry;
while (queueEntry = queue.shift()) {
let dep = retrieveDependency(queueEntry.identifier);
// Iterate over the sub dependencies, adding them to our Queue for
// later processing.
const currentCoords = getCoords(dep);
if (dep.dependencies && dep.dependencies.length > 0) {
queue = queue.concat(dep.dependencies.map( (innerDep) => {
let newChain = queueEntry.chain.slice();
newChain.push(currentCoords);
return generateDependencyQueueObject(innerDep, newChain);
}));
}
// Place in tree
addToTree(dep, queueEntry.chain)
// Increment Counter
numberOfNodes++;
// DEMONSTRATION: log the processing order to check this solves the issue
processingOrder.push(currentCoords);
}
};
return {
/**
* Traverse to the root node, initialising queue as a list of
* dependencies - ordered correctly with highest node first.
*/
traverseToRoot : () => {
const recurseUp = (node) => {
if (!node.parent) {
return;
}
const parentNode = retrieveParent(node.parent);
if (parentNode.dependencies && parentNode.dependencies.length > 0) {
queue = parentNode.dependencies
.map((dep) => {return generateDependencyQueueObject(dep) })
.concat(queue)
}
return recurseUp(parentNode);
};
return recurseUp(targetObject);
},
/**
* Append the direct dependencies from the target object to those
* discovered in the parent(s) object(s). Then begin processing
* our dependency queue.
*/
parseDependencies : () => {
if (targetObject.dependencies && targetObject.dependencies.length > 0) {
queue = queue.concat(targetObject.dependencies
.map((dep) => {return generateDependencyQueueObject(dep) }));
}
processDepQueue();
},
getTree : () => {
return dependencyTree;
},
getNumberOfNodes: () => {
return numberOfNodes;
},
getProcessingOrder: () => {
// For demonstration reasons; dump out the processing order.
return processingOrder;
}
}
};
var exports = module.exports = {
"main:parentOne" : {
"parent": "main:parentTwo",
"groupId": "main",
"artifactId": "parentOne",
"dependencies": [ "dependency:eight" ]
},
"main:parentTwo" : {
"parent": "main:parentThree",
"groupId": "main",
"artifactId": "parentTwo",
"dependencies": [ "dependency:four", "dependency:five", "dependency:six", "dependency:seven" ]
},
"main:parentThree" : {
"groupId": "main",
"artifactId": "parentThree",
"dependencies": [ "dependency:one", "dependency:two", "dependency:three" ]
},
"dependency:one" : { "groupId": "dependency", "artifactId": "one" },
"dependency:two" : { "groupId": "dependency", "artifactId": "two" },
"dependency:three" : { "groupId": "dependency", "artifactId": "three" },
"dependency:four" : { "groupId": "dependency", "artifactId": "four" },
"dependency:five" : { "groupId": "dependency", "artifactId": "five" },
"dependency:six" : { "groupId": "dependency", "artifactId": "six" },
"dependency:seven" : { "groupId": "dependency", "artifactId": "seven" },
"dependency:eight" : { "groupId": "dependency", "artifactId": "eight" },
"dependency:nine" : { "groupId": "dependency", "artifactId": "nine", "dependencies": [
"dependency:twelve", "dependency:thirteen"
]},
"dependency:ten" : { "groupId": "dependency", "artifactId": "ten", "dependencies": [
"dependency:fourteen"
]},
"dependency:eleven" : { "groupId": "dependency", "artifactId": "eleven" },
"dependency:twelve" : { "groupId": "dependency", "artifactId": "twelve" },
"dependency:thirteen" : { "groupId": "dependency", "artifactId": "thirteen" },
"dependency:fourteen" : { "groupId": "dependency", "artifactId": "fourteen", "dependencies": [
"dependency:fifteen", "dependency:sixteen"
]},
"dependency:fifteen" : { "groupId": "dependency", "artifactId": "fifteen" },
"dependency:sixteen" : { "groupId": "dependency", "artifactId": "sixteen" },
}
@FergusInLondon
Copy link
Author

Output

Pay special attention to the Processing Order, and compare with the resulting Dependency Tree. Dependencies are processed closest first; regardless of nesting.

Processing Order:  [ 'dependency:one',
  'dependency:two',
  'dependency:three',
  'dependency:four',
  'dependency:five',
  'dependency:six',
  'dependency:seven',
  'dependency:eight',
  'dependency:nine',
  'dependency:ten',
  'dependency:eleven',
  'dependency:twelve',
  'dependency:thirteen',
  'dependency:fourteen',
  'dependency:fifteen',
  'dependency:sixteen' ]
Number of Nodes:  16
Dependency Tree:  { 'dependency:one': { groupId: 'dependency', artifactId: 'one' },
  'dependency:two': { groupId: 'dependency', artifactId: 'two' },
  'dependency:three': { groupId: 'dependency', artifactId: 'three' },
  'dependency:four': { groupId: 'dependency', artifactId: 'four' },
  'dependency:five': { groupId: 'dependency', artifactId: 'five' },
  'dependency:six': { groupId: 'dependency', artifactId: 'six' },
  'dependency:seven': { groupId: 'dependency', artifactId: 'seven' },
  'dependency:eight': { groupId: 'dependency', artifactId: 'eight' },
  'dependency:nine': 
   { groupId: 'dependency',
     artifactId: 'nine',
     dependencies: [ 'dependency:twelve', 'dependency:thirteen' ],
     'dependency:twelve': { groupId: 'dependency', artifactId: 'twelve' },
     'dependency:thirteen': { groupId: 'dependency', artifactId: 'thirteen' } },
  'dependency:ten': 
   { groupId: 'dependency',
     artifactId: 'ten',
     dependencies: [ 'dependency:fourteen' ],
     'dependency:fourteen': 
      { groupId: 'dependency',
        artifactId: 'fourteen',
        dependencies: [Object],
        'dependency:fifteen': [Object],
        'dependency:sixteen': [Object] } },
  'dependency:eleven': { groupId: 'dependency', artifactId: 'eleven' } }

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment