Dependancies Graph
In order to reduce the number of executed tests, WatchCub framework supports dependancies among tests.
These dependancies are built and managed through dependancies graph. The dependancies graph is directed acyclic graph in which the nodes are the different test objects and the arcs reflect the relation "depends on".
For example, on the picture below tests 3 depends on tests 1 and 2, test 4 depends on test 3 and test 5 depends on tests 3 and 6. Tests 1, 2 and 6 do not depend on any other test.
Dependancies are built and manager in order to assure that no test B, depending on some other test A will get executed unless A gets executed successfully. So, in the example picture only tests 1, 2 and 6 can be executed in the very beginning.
Paces
The pace of a test is the time interval in which new instance of the test should be initialized. The default pace of a test can be configured and will most probably be 60 seconds. But for some test this will be less (30 secs for some port tests).
When the time has come for some test to be executed (according to its pace) we should make sure all its dependancies will get successfully executed first. That is, the moment one test gets "in time" all its preceding tests must succeed (no earlier than that time).
The Algorithm
With every node of the graph (test) we associate the following properties - NextExecution and LastExecution (which are timestamps, number of seconds from the Epoch), a list of node to which there is an arc outgoing from the current (ListOutgoing) and a list of nodes from which there is an arc incoming in the current (ListIncoming).
We maintain a queue of currently available for execution tests (QueueAvailable) this way:
FOREACH node IN graph DO
node.NextExecution := NOW()
node.LastExecution := 0
IF IS_EMPTY( node.ListIncoming ) THEN
PUSH( node, QueueAvailable )
INSERT( node, ListIndependant )
END IF
END FOREACH
- Every time a test (currNode) has been executed successfully
currNode.LastExecution := NOW()
currNode.NextExecution += currNode.Pace
IF IS_EMPTY( currNode.ListIncoming ) THEN
PUSH( currNode, ListIndependant )
END IF
FOREACH node IN currNode.ListOutgoing DO
IF node.NextExecution <= NOW() THEN
Available := TRUE
FOREACH parentNode IN node.ListIncoming
IF parentNode.LastExecution < node.NextExecution THEN
Available := FALSE
BREAK
END IF
END FOREACH
IF Available THEN
PUSH( node, QueueAvailable )
END IF
END IF
END FOREACH
-
What do we do when a plugin asks for a test instance?
Every time this happens, the following procedure is executed:
PROCEDURE GetTest( PluginType )
FOREACH node IN QueueAvailable
IF node.PluginType = PluginType THEN
POP( node, QueueAvailable )
RETURN node
END IF
END FOREACH
END PROCEDURE
... check if any of the independant tests has is not ready for execution
PROCEDURE Check
FOREACH node IN QueueIndependant
IF node.NextExecution <= NOW() THEN
POP( node, QueueIndependant )
PUSH( node, ListAvailable )
END IF
END FOREACH
END PROCEDURE
