Beautiful Code [311]
diff -r gdb-4.16/gdb/infcmd.c gdb-4.17/gdb/infcmd.c
1239c1278
< "Set arguments to give program being debugged when it is started.\n\
---
> "Set argument list to give program being debugged when it is started.\n\
This change from arguments to argument list was the cause for gdb 4.17 no longer working with ddd. This text is output by gdb when the user requests help for the set args command. However, it is also used in other places. When given the command show args, gdb 4.16 replies:
Arguments to give program being debugged is "11 14"
gdb 4.17, however, replies:
Argument list to give program being debugged is "11 14"
This new reply was what confused ddd because it expected the reply to start with Arguments. Thus, my script had actually determined the failure-inducing change—after five days of work, but yet in a fully automatic version.
Beautiful Debugging > Delta Debugging
28.5. Delta Debugging
Over the next several months, I refined and optimized the algorithm as well as the tool, such that eventually it would need just one hour to find the failure-inducing change. I eventually published the algorithm under the name delta debugging because it "debugs" programs by isolating a delta, or difference between two versions.
Here I'll show my Python implementation of the delta debugging algorithm. The function dd() takes three arguments—two lists of changes as well as a test:
The list c_pass contains the "working" configuration—in our case, the list of changes that must be applied to make the program work. In our case (which is typical), this is the empty list.
The list c_fail contains the "failing" configuration—in our case, the list of changes required to make the program fail. In our case, this would be a list of 8,721 changes (which we would encapsulate in, say, Change objects).
The test function accepts a list of changes, applies them, and runs a test. It returns PASS, FAIL, or UNRESOLVED as the outcome, depending on whether the test was successful, failed, or had an unresolved outcome. In our case, the test function would apply the changes via patch and run the test as just described.
The dd( ) function systematically narrows down the difference between c_pass and c_fail, and eventually returns a triple of values. The first of these values would be the isolated delta—in our case, a single Change object containing the one-line change to the gdb source code.
If you plan to implement dd() yourself, you can easily use the code shown here (and included on the O'Reilly web site for this book). You also need three supporting functions:
split (list, n)
Splits a list into n sublists of equal length (except for possibly the last). Thus:
split([1, 2, 3, 4, 5], 3)
yields:
[[1, 2], [3, 4], [5]]
listminus() and listunion( )
Return the difference or union of two sets represented as lists, respectively. Thus:
listminus([1, 2, 3], [1, 2])
yields:
[3]
whereas:
listunion([1, 2, 3], [3, 4])
yields:
[1, 2, 3, 4]
The Python code is shown in Example 28-1.
Example 28-1. An implementation of the delta debugging algorithm
Code View: Scroll / Show All
def dd(c_pass, c_fail, test):
"""Return a triple (DELTA, C_PASS', C_FAIL') such that
- C_PASS subseteq C_PASS' subset C_FAIL' subseteq C_FAIL holds
- DELTA = C_FAIL' - C_PASS' is a minimal difference
between C_PASS' and C_FAIL' that is relevant with respect
to TEST."""
n = 2 # Number of subsets
while 1:
assert test(c_pass) == PASS # Invariant
assert test(c_fail) == FAIL # Invariant
assert n >= 2
delta = listminus(c_fail, c_pass)
if n > len(delta):
# No further minimizing
return (delta, c_pass, c_fail)
deltas = split(delta, n)
assert len(deltas) == n
offset = 0
j = 0
while j < n:
i = (j + offset) % n
next_c_pass = listunion(c_pass, deltas[i])
next_c_fail = listminus(c_fail,