Friday, January 26, 2007

Topological Sort Joy

I finally modified sinan to make use of all the dependency analysis code I wrote for ewrepo. One thing that I needed to do was produce a list, in the dependent order, of the graph of dependencies in the internal project applications. This is essential for compile time things like parse transforms are going to work correctly. I wrestled with how to do this correctly for quite a bit before I realized that its a simple topological sort. I should really have realized this immediately, but I didn't. Fortunately, this isn't a difficult algorithm, especially since I didn't even need to implement it. Joe Armstrong wrote a topo sort for his ermake project and made it available in the contribs section of Once I found that it didn't take to long to integrate it into sinan.

Once I got to thinking about this dependency problem I realized that there was at least one more area that a topological sort was needed. Thats in the run order of the task list. Each task may have any number of tasks that it depends on. Right now my code would just run each dependent task multiple times. Thats a bug, fortunately it wont take more then a few minutes to integrate the topo sort into this area as well.