Dependency
##Introduction
The Dependency Task is responsible for calculating dependencies between the JavaScript files contained in the framework ('core' and 'ui') and the concrete Application. Therefor each file, that has some dependencies to one or more other files must provide a special tag, which indicates the dependencies.
In JavaScript functions and objects used in file must be specified some where above the first execution. See Example:
function a (){
alert('function a');
}
a(); // will work.
b(); // will probably not work.
function b (){
alert('function b');
}So the business of the dependency task is to take care, that the JavaScript files of both, the project and the framework are included in the right sequence. The information about the sequence is carried in each file. Its done by adding:
m_require('name_to_dependency.js');
at the top of a JavaScript file. To place m_require at the very begin of a file is not mandatory, the Dependency Task will find it any way, but it makes developing much easier when looking for dependencies.
##The task flow
Task has three major challenges:
- resolve all dependencies from the files
- build a dependency tree, characterizing the dependency relations between the files
- sort the dependencies
resolve all dependencies
The first thing is to take a look a every file, extract the dependencies. A file can none, 1, or multiple dependencies.
This can be done by looping through all files of the framework and check each file by regular expression for m_require. The Dependencies are stored in the object representation of the file, for that every file object has a array containing its dependencies.
function resolveDependencies() {
framework.files.forEach(function(file) {
if(file.isJavaScript()){
var _re, _match, _path;
var deps = [];
/*RegExp = all string match: m_require('someFile.js');*/
_re = new RegExp("[^//]m_require\\([\"'](.*?)[\"']\\)", "g");
while (_match = _re.exec(file.content)) {
_path = _match[1];
if (!/\.js$/.test(_path)){
_path += '.js';
}
deps.push(_path)
}
if(deps.length >= 1){
/*Add the found dependencies to the file.*/
file.dependencies = deps;
}
}
});
return framework;
}After this, the framework is passed on to the next step in the dependency task.
build the dependency tree
Now the things are getting a bit tricky. A folder, inside the framework, can contain files:
- with dependencies
- without any dependencies
- without dependencies, but other files have a dependency to this one
All this files are mixed up in one or more folders. Since we wanna to have a nice tree, describing the relations between the files we probably want to see something like this:
As you can see in the tree above, we have one root node, which means this is a file with no dependencies to other files, but it serves as a dependency for other. The direction of the edges indicates the dependency relation and means: "is dependent on ...". So here file: B depends on file: A. And we have files like: F, G,L who have more than one dependency, therefor they occur as children of more than one parent.
This sort of tree is the simple case, with one root node and all other files have dependencies to each other. But there are other files out there, waiting to chop the tree.
There can be more then one root node. This means there are a several files with no dependencies, but other files are needing them as a dependency. And we have "solo" files without any dependency. When building the tree the first thing is to locate all potential root nodes -> all files with node dependencies. This will give us all files, with no dependency and files with no dependency+no other files are depended on them. To finde all potential root nodes, its a easy thing, just look at every file and check if the dependency array is empty.
Example code: here the found root nodes are added as new tree nodes
/*object to hold the root nodes.*/
var _roots = [];
/* find and add the root nodes first!*/
framework.files.forEach(function (file){
if(file.isJavaScript() && file.dependencies.length === 0){
_roots.push(new _TreeNode(file.getName(),file));
}
});
}here the found root nodes are added as new tree nodes to a array, holding this nodes. After looking for all potential root nodes we can looking for other potential files (nodes) which have dependencies to one or many of the found root nodes. So the we can iterate over the files agin and looking for files to fit in on of our trees, yes thats right, there can be more then just one tree. As a result we can end up with 1 tree in best case , n -trees (n = number of files) in worst case. And guess what, files can be occur in several trees as well!
So iterating over the files, for that case the dependency task is equipped with a tree build object. This object takes a root node a adds all found files depending on this node to the tree, this action is done recursively:
The result is a Array of dependency trees. One for each found root node.
sort the dependency trees
The final action of the dependency task is to traverse the dependency trees, and order all node (aka. files) in to a list. This final list can easily iterated by the Merger Task, to generate a single file, in the right sequence.
The traversal is done according to the 'Breadth-first' search algorithm, see at: http://en.wikipedia.org/wiki/Breadth-first_search. This algorithm is walking the tree, level per level, to find the wanted node.
Its based on the queuing all nodes that have been visited, take the first node from the queue and look, if this is the wanted node return it. if not, get all direct children of this node and put them in the queue. And execute the BFS recursively. If the queue get empty the whole tree have been visited, and the wanted node is can not be found.
Here is the pseudo code of the BFS
procedure BFS(Graph,source):
create a queue Q
enqueue source onto Q
mark source
while Q is not empty:
dequeue an item from Q into v
for each edge e incident on v in Graph:
let w be the other end of e
if w is not marked:
mark w
enqueue w onto QIn our case we are not looking for a particular node, so we have to modify the BFS in that way the whole tree is traversed. The condition is here:
A node is depended on a other node
The traversal level per level comes quit handy, as it can help to fix the problem of multi dependencies of the files. As a result a file will occur in the tree for every dependency. But a file with multi dependencies can not be merged into the final sequence on it first occurrence but on its last. So if adding a file to the final sequence make a check if all dependencies are already in the sequence. If the answer is NO. skip this node ... and wait for the next occurrence, this will happen because a file with multi dependencies a N x in the tree (N = amount of dependencies). If the answer is YES, all dependencies are already in the final sequence.
This image describes the step in which a node (file) is added to the final sequence. A comes first at step 1, N last at step 8. The nodes F, G and L are added only if all there dependencies are already in the final sequence.
Take a look at node F. F could be included in the final sequence at step 4 -> because it is a direct child of: C, but it has also dependencies to: M. So the include of F has to be wait 1 additional step.
