On 29/01/13 07:44, Adam Murdoch wrote:
Implementation-wise, I would think about busting up building the task
graph into 2 steps:
1. Build the task graph proper, with a node for each task in the graph
and edges to represent the various types of dependencies.
2. Once the graph is built, calculate the execution plan:
- Take each node that has no incoming edges, sort them and then
traverse each in turn.
- To traverse a node
- Take each soft dependency, sort them and traverse each in turn.
- Take each hard dependency, sort them and traverse each in turn.
I've finally managed to get the stuff that was preventing me from
working on that out of the door and I'm looking into this again.
Buildinng a task graph seems to be a bit of an overkill to me for this
feature as we can get away without it for now. There are two main
problems I see with building the graph:
- we would need to have three phases instead of the two you are
mentioning - first build the graph with only 'hard' dependencies, then
go through all nodes and add 'soft' dependencies (soft/always runs after
dependencies can only be added when the nodes of the graph are known as
a 'soft' dependency only kicks in if the task we should run after is in
the graph) and only then perform a toposort
- I don't feel competent enough to come up with how that graph should
look like from the implementation point of view, what methods it should
expose, etc
I believe the following is simpler and better for now:
- every time DefaultTaskExecutionPlan.addToTaskGraph() is called then
create/update an unordered set of tasks that have to be executed and
maintain a set of tasks that aren't dependencies of other tasks (have no
incoming edges); the first set would be then used to check if a given
'soft' dependency should be taken into account when ordering and the
second set would serve as the starting point for the toposort
- add a CachingTaskDependencyResolveContext field to reuse resolved task
dependecies between the two phases of the algorithm
- add determineExecutionPlan() method that has to be called before any
call to getTaskToExecute() and that performs a toposort the way you have
described in the second phase of your algorithm with the result being
what currently is the executionPlan field after the last call to
addTaskToGraph() but with 'soft' dependencies taken into account.
I will start implementing it this way. Please let me know if you don't
believe that this is the right way to go.
