Javascript does not have any kind of dependency management built into the language; rather you have to use external tools to do the management for you. We have a rather large Javascript code base, and Rake is our build management tool, so the natural choice for me was to investigate available Ruby solutions; unfortunately, none of them worked well for me.

What I really want is a tool that simply takes all the Javascript source files in a directory, and tell me what order they should be included. At that point, I can decide whether to run them through JsLint, Spidermonkey, concatenate them, compress them or whatever; those tasks are relatively simple, but the dependency management part seems hard. The math nerds would call this order that I want “topological sort”, but it’s really just a fancy word for the process that most people go through on Sunday morning.

Suppose I like to wake up on Sunday morning, eat breakfast, and go for a jog. Certain things need to happen before I go for a jog; I’d need to put my clothes on before doing so, and certain articles of clothing must be donned before others (I’d ruin my socks if I put my shoes on first). Let’s break it down:

- Underpants go on before shorts.
- Shoes go on after socks.
- Shoes go on after shorts.
- You’ll need to wear a shirt.
- Jogging must be done after all this stuff, but before eating (or else I’d get cramps).
- I’d want to get a shower in, but this is best done after jogging.

This process doesn’t have to be routine every morning; socks and underpants must go on before shoes, but there’s no requirement that one has to be put one on before the other. I’m really only interested in an order that satisfies the above requirements, and this order can be found by modeling each dependency as an arc in a dependency graph:

In the above figure, if a task is dependent on another, then an arc connects them. As expected, the head of the arc originates from the dependent task; after all, I’ll want to do that dependent task first. My goal, then, is to find some linear ordering of the above nodes such that if node u is the head of an arc, the tail v of that arc appears after u in that ordering. In other words, one thing I’d like to do is avoid the embarrassing mistake of starting my jog stark naked.

This goal can be achieved by performing a depth first search on the graph, marking nodes “done” as I go along. To do this, I take each node, and recursively follow the arcs through as deeply as possible (without repeating any nodes) until I can’t go any deeper, then mark that node as “done”.

In the above figure, I’ve randomly chosen to follow “shirt” and its arcs all the way down to “shower”, then “breakfast”, then “jogging”, and finally back to “shirt”. After that, I decided to pick “socks” and follow it down to “shoes”, ignoring “jogging” as it’s already been marked. I do the same with “underwear”. As it turns out, the reverse order in which I’ve marked the nodes gives me a topological sort, which is what is desired:

This very strategy is employed to topologically sort Javascript dependencies, and as a bonus, circular dependencies can be detected. If one labels the arcs that are followed in the depth first search above as “tree edges”, then we have a depth first search tree. Any arcs that are not tree edges and point back to some predecessor of the arc head is denoted a “back edge”; by examining these back edges, one can quickly see exactly which files are involved in circular dependencies and raise an error.