LoveIsBug

大头

标签云

分类

日历

十一月
27	28	29	30	31	1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30

留言

微博

代码之美 - 081022

《漂亮的调试》，Andreas Zeller以ddd的一个bug为引，介绍了增量调试（Delta Debugging），主要思想类同二分，算法好理解，可是程序看不大明白。

程序如下。

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, deltas[i])
 
            if test(next_c_fail) == FAIL and n == 2:
                c_fail = next_c_fail
                n = 2; offset = 0; break
            elif test(next_c_fail) == PASS:
                c_pass = next_c_fail
                n = 2; offset = 0; break
            elif test(next_c_pass) == FAIL:
                c_fail = next_c_pass
                n = 2; offset = 0; break
            elif test(next_c_fail) == FAIL:
                c_fail = next_c_fail
                n = max(n - 1, 2); offset = i; break
            elif test(next_c_pass) == PASS:
                c_pass = next_c_pass
                n = max(n - 1, 2); offset = i; break
            else:
                j = j + 1
 
        if j >= n:
            if n >= len(delta):
                return (delta, c_pass, c_fail)
            else:
                n = min(len(delta), n * 2)
 

1，第三行注释翻译成：“C_PASS是C_PASS'的子集，C_FAIL'是C_FAIL的子集”。想了一想，没错，函数是逐步缩小c_pass和c_fail之间的差异，在书中例子里，也是通常情况下，c_pass是空的，c_fail是“失败全集”。

2，在 j < n 这个循环里，n = 2, i = 0, 把全集分成两部分，如果第一个 if 成立，c_fail等于其中一部分，n = 2, offset = 0, break是否是跳出这一堆if-elif-else？跳出的话回到循环开始，j 没有机会改变，i 也就仍然等于0。我尝试着模拟几种情况，n等于2、4、8，似乎程序跑步到 else 里，j = j + 1 没有机会被执行，i 的值也就得不到改变。也许我对 test 函数的返回理解有误。摇头叹息看不懂看不懂。

作者说在这本书的O'Reilly网页上也有这段代码，于是去下载，下载的代码和书上的不大一样，算法是一致的，清楚多了，一看就明白。再回头看上面这一段，还是觉得不大对。作罢作罢。

文中还提到Continuout Testing。作者说他开了一门课，专门讲授科学方法和增量调试，课程幻灯片和参考文献在：http://www.whyprogramsfail.com/，可是我打不开这个网页。还有增量调试的主页：http://www.st.cs.uni-sb.de/dd/。

十一月
日	一	二	三	四	五	六
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30

十一月
日	一	二	三	四	五	六
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30

又是被优先级问题折腾了三天

代码之美 - 081022

十一月
日	一	二	三	四	五	六
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30