7.6 Depth-first search strategy

7.6 Depth-first search strategy

7.6.1 Depth-first search assumptions

The depth-first search strategy is analogous to the depth-first search method taught in introductory algorithms classes. The strategy assumes that the program being debugged has a single main procedure. If the problem system has multiple main procedures, because there are multiple executables in the system, wrap an outer loop around the control structure that visits each main procedure in turn. If the problem system has no main procedure, as in the case of libraries, treat the test case that is invoking the library as the main procedure.

This strategy is easier to use if you have a tool available that will generate a tree structure showing the calling hierarchy of the application. Failing that, a cross-reference listing of the application can also be useful.

7.6.2 Depth-first control structure

The next code sample shows the control structure for the depth-first strategy.

 Set suspect list to empty  Invoke DFS with name of top level procedure  DFS ( ancestor )      Set visited(ancestor) to true      For each descendant procedure called by ancestor          procedure          If visited(descendant) is false          Then              Test the hypothesis that the errors occurs                  during the execution of descendant              If the hypothesis is true              Then                  Prepend the candidate to the front of                      the suspect list              End-if              DFS(descendant)          End-if      End-for  End-DFS  The first element of the suspect list is the procedure      in which the defect occurs