用TPP开启TDD的easy模式

Test-Drived Development

测试驱动开发三步曲：写一个失败的测试用例->编写生产代码通过这个测试用例（transformation）->重构（refactor）。重构是指不改变程序的外在行为的前提下消除代码坏味道，目前已有不少的指导书籍。而第二步变形（Transformation） 编写生产代码通过测试用例，这是TDD三个环节中最困难的，有时甚至会陷入僵局。

Transformation Priority Premise

变形（Transformation）的困难在于：如果步子太大，会花费很长时间才能通过测试；如果实现思路不对，甚至陷入僵局（impasse）无法进一步演进。Uncle Bob在2013年提出了TPP（transformation priority premise）的方法，他认为优秀代码的演进过程不是从一个愚蠢的状态逐步转变为一个优雅的状态；而是从一个具体的状态转变成为一个通用的状态。因此他对常用的编码变形手段进行排序，优先级高的手段是更具体的手段，而低优先级的变形手段是更通用的手段。通过这个变形优先列表不仅可以很好的控制节奏，最重要的是尽量推迟通用的手段。

通过测试用例的驱动不断的深入，问题的本质会逐步浮现。当本质浮现之后，再逐步采用通用的手段演进。

TDD陷入困境往往是过早的采用通用的手段。通用的手段步子更大、更死板，有时看似更简洁，但隐藏了细节，难以进一步演进。

TPP的列表如下（1为最高优先级）：

1 ({} → nil) no code at all → code that employs nil（空函数 ->返回空结果）

2 (nil → constant)（空->常量）

3 (constant → constant+) a simple constant to a more complex constant（常量->更复杂的多个常量）

4 (constant → scalar) replacing a constant with a variable or an argument（常量->变量）

5 (statement → statements) adding more unconditional statements.（单条语句->多条语句）

6 (unconditional → if) splitting the execution path（无条件语句->if分支语句）

7 (scalar → array)（变量->数组）

8 (array → container)（数组->容器）

9 (statement → tail-recursion)（语句->尾部递归）

10 (if → while)

11 (statement → non-tail-recursion)（语句->非尾部递归）

12 (expression → function) replacing an expression with a function or algorithm（表达式->函数或算法）

13 (variable → assignment) replacing the value of a variable.（变量->赋值）

14 (case) adding a case (or else) to an existing switch or if（新增case或else语句->已有的switch或if语句）

来源： https://en.wikipedia.org/wiki/Transformation_Priority_Premise

---

代码操练

下面以Anagrams为例进行代码操练（c++、gtest），看看TPP是否如何帮助我们走出困境。

需求描述

对于给定的字符串，输出所有潜在字符组合。问题描述比较清晰，但如何解决？

• 第一个测试用例：
  
  一个空的字符串，可能的anagrams集合也为空

TEST(Anagrams, test_anagrams_of_null_should_be_null)
{
    vector result = {};
    ASSERT_EQ(result, getAnagrams(""));
}

• 变形：应用最高优先级的变形手段返回一个空的结果集合 ({} →nil)

vector getAnagrams(string str)
{
    return vector();
}

• 重构：定义结果集合的数据类型Result，更好的揭示意图。

typedef vector<string> Result;
Result getAnagrams(string str)
{
    return Result();
}

测试用例同步重构

TEST(Anagrams, test_anagrams_of_null_should_be_null)
{
    Result result = {};
    ASSERT_EQ(result, getAnagrams(""));
}

• 第二个测试用例：一个字符的anagrams只有其自身

TEST(Anagrams, test_anagrams_of_a_should_be_a)
{
    Result result = {"a"};
    ASSERT_EQ(result, getAnagrams("a"));
}

• 变形：中优先级的变形手段(nil→ constant)、(constant → scalar)、(unconditional → if)

Result getAnagrams(string str)
{
    if (str == "")
        return Result();
    Result res = {str};
    return res;
}

• 第三个测试用例：两个字符的anagrams包含两个结果

TEST(Anagrams, test_anagrams_of_ab_should_be_ab_ba)
{
    Result result = {"ab", "ba"};
    ASSERT_EQ(result, getAnagrams("ab"));
}

• 变形 ： 把两个字符进行相互颠倒，就可以搞定。
  
  因此按照惯性的方法继续中优先级的变形手段： (unconditional → if)

Result getAnagrams(string str)
{
    if (str == "")
        return Result();
    Result res = {str};
    if (str.size() == 2)
        res.push_back(str.substr(1, 1) + str.substr(0, 1));
    return res;
}

• 第四个测试用例：三个字符的anagrams包含六个结果

TEST(Anagrams, test_anagrams_of_abc_should_be_abc_acb_bac_bca_cab_cba)
{
    Result result = {"abc", "acb", "bac", "bca", "cab", "cba"};
    ASSERT_EQ(result, getAnagrams("abc"));
}

• 变形 or 僵局
  
  三个字符的问题可以转换为两个字符的问题吗？似乎可以先遍历选取第一个字符，再剩下就是已解决的两个字符的已知问题。
  
  但是结果如何组合在一起？需要组合一个字符和一个数组…
  
  步子太大了，容易陷入僵局（impasse），说好的easy模式呢？
  
  回顾当前思路和上一步的变形过程，过早的使用相对低优先级的手段 (unconditional → if)，隐藏了包含问题本质的细节，也难以继续演进。如下面这段代码隐藏了两个字符下的anagrams规律。

    Result res = {str};
    if (str.size() == 2)
        res.push_back(str.substr(1, 1) + str.substr(0, 1));
    return res;

现在重新回到easy模式下，按照TPP的优先顺序，优选高优先级的手段(nil → constant)、(constant → constant+)

Result getAnagrams(string str)
{
    if (str.size() == 0)
        return Result();
    else if(str.size() == 1)
        return Result{str};
    else if(str.size() == 2){
        return Result{str,
            str.substr(1, 1) + str.substr(0, 1)};
    }
}

但是第三个测试用例的问题如何解决呢？easy，用高优先级的方法吧！

    else if(str.size() == 2){
        return Result{str,
            str.substr(1, 1) + str.substr(0, 1)};
    }
    else{
        return Result{"abc", "acb", "bac", "bca", "cab", "cba"};
    }

呵呵，有点骗人？

但变形还没有结束，继续…

    else{
        return Result{string("a") + "bc", 
                      string("a") + "cb", 
                      "bac", 
                      "bca", 
                      "cab", 
                      "cba"};
    }

这个时候“bc”和“cb”是n-1规模的答案集合，当然要用(statement → tail-recursion)手段变形

        return Result{string("a") + getAnagrams("bc")[0], 
                      string("a") + getAnagrams("bc")[1], 

“a”代表字符串的首字符，继续变形(constant → scalar)

        return Result{str.substr(0, 1) + getAnagrams("bc")[0], 
                      str.substr(0, 1) + getAnagrams("bc")[1], 

同理其他的语句也用类似的方法变形

        return Result{str.substr(0, 1) + getAnagrams("bc")[0], 
                      str.substr(0, 1) + getAnagrams("bc")[1], 
                      str.substr(1, 1) + getAnagrams("ac")[0], 
                      str.substr(1, 1) + getAnagrams("ac")[1], 
                      str.substr(2, 1) + getAnagrams("ab")[0], 
                      str.substr(2, 1) + getAnagrams("ab")[1]};

“bc”、“ac”、“ab”都是代表剩下的字符串。因此在这里考虑提出一个函数，处理剩下的字符串，继续变形。

        return Result{str.substr(0, 1) + getAnagrams(strDelChar(str , 0))[0], 
                      str.substr(0, 1) + getAnagrams("bc")[1], 
                      str.substr(1, 1) + getAnagrams("ac")[0], 
                      str.substr(1, 1) + getAnagrams("ac")[1], 
                      str.substr(2, 1) + getAnagrams("ab")[0], 
                      str.substr(2, 1) + getAnagrams("ab")[1]};

吸取刚才的教训，strDelChar这个函数我也按照TPP的顺序变形，坚持easy模式！

string  strDelChar(string s, size_t pos){
    return "bc";
}

对其他的挑剩下的字符也采用相同的方式处理

        return Result{str.substr(0, 1) + getAnagrams(strDelChar(str , 0))[0], 
                      str.substr(0, 1) + getAnagrams(strDelChar(str , 0))[1], 
                      str.substr(1, 1) + getAnagrams(strDelChar(str , 1))[0], 
                      str.substr(1, 1) + getAnagrams(strDelChar(str , 1))[1], 
                      str.substr(2, 1) + getAnagrams(strDelChar(str , 2))[0], 
                      str.substr(2, 1) + getAnagrams(strDelChar(str , 2))[1]};

此时的strDelChar函数变形成这样了

string  strDelChar(string s, size_t pos){
    if (pos == 0) 
        return "bc";
    if (pos == 1)
        return "ac";
    return "ab";
}

根据常量实际的意义继续变形(constant → scalar)

string  strDelChar(string s, size_t pos){
    if (pos == 0) 
        return s.substr(1, 2);
    if (pos == 1)
        return s.substr(0, 1) + s.substr(2, 1);
    else
        return s.substr(0, 2);
}

剩下的字符串包括两部分的内容：扣去字符前的部分、扣去字符后面的部分。因此继续变形

string  strDelChar(string s, size_t pos){
    if (pos == 0) 
        return s.substr(0, 0) +s.substr(1, 2);
    if (pos == 1)
        return s.substr(0, 1) + s.substr(2, 1);
    else
        return s.substr(0, 2) + s.substr(2, 0);
}

通过上面的代码可以看到pos就是分割点，pos位置的字符被扣去。因此可以采用更通用的方法继续变形

string  strDelChar(string s, size_t pos){
    string before = s.substr(0, pos);
    string after = s.substr(pos+1);
    return before + after;
}

最后消除不必要的局部变量，搞定这个函数

string  strDelChar(string s, size_t pos){
    return s.substr(0, pos) + s.substr(pos+1);
}

获取首字符的地方也可以抽取一个函数

    else{
        return Result{strGetChar(str, 0) + getAnagrams(strDelChar(str , 0))[0], 
                      strGetChar(str, 0) + getAnagrams(strDelChar(str , 0))[1], 
                      strGetChar(str, 1) + getAnagrams(strDelChar(str , 1))[0], 
                      strGetChar(str, 1) + getAnagrams(strDelChar(str , 1))[1], 
                      strGetChar(str, 2) + getAnagrams(strDelChar(str , 2))[0], 
                      strGetChar(str, 2) + getAnagrams(strDelChar(str , 2))[1]};
    }

string strGetChar(string s, size_t pos){
    return s.substr(pos, 1);
}

一系列变形后，函数更通用了，不仅仅处理abc的问题，所有三个字符的问题都可以解决。

继续回到刚才的主体测试函数继续变形，此处的六条语句实际上是一个遍历首字符的过程，因此抽取外层的循环：

    else{
        Result res;
        for (size_t i = 0; i < str.size(); i++){
            res.push_back(strGetChar(str, i) + getAnagrams(strDelChar(str , i))[0]);
            res.push_back(strGetChar(str, i) + getAnagrams(strDelChar(str , i))[1]);
        }
        return res;
    }

内部的两条语句本质上是遍历两个字符子问题的结果集，因此继续变形

    else{
        Result res;
        for (size_t i = 0; i < str.size(); i++){
            Result subRes = getAnagrams(strDelChar(str, i));
            for (auto subResStr : subRes){
                res.push_back(strGetChar(str, i) + subResStr);
            }
        }
        return res;
    }

再回顾一下完整的这个主体函数：

else分支部分 将规模为n的原问题分解为 遍历首字符 + 规模为n-1的问题，通过递归解决了更大规模的问题。因此现在这部分代码更加通用。

Result getAnagrams(string str)
{
    if (str.size() == 0)
        return Result();
    else if(str.size() == 1)
        return Result{str};
    else if(str.size() == 2){
        return Result{str.substr(0, 1) + str.substr(1, 1),
                      str.substr(1, 1) + str.substr(0, 1)};
    }
    else{
        Result res;
        for (size_t i = 0; i < str.size(); i++){
            Result subRes = getAnagrams(strDelChar(str, i));
            for (auto subResStr : subRes)
                res.push_back(strGetChar(str, i) + subResStr);
        }
        return res;
    }
}

再看一下其他的分支情况：

1 规模为0的情况是else分支的特殊情况，0不进入循环体。因此第一个if语句可以删除。

2 规模为1的情况属于递归的出口，因此第一个else if必须保留。

3 规模为2的情况也是首字符+规模1（2-1）的问题。因此规模2的问题属于else分支的一种特殊情况，也可以删除。

删除无用的代码，最终的结果：

string  strDelChar(string s, size_t pos){
    return s.substr(0, pos) + s.substr(pos + 1);
}
Result getAnagrams(string str)
{
    Result res;
    if(str.size() == 1)
        return Result{str};
    for (size_t i = 0; i < str.size(); i++){
       Result subRes = getAnagrams(strDelChar(str, i));
       for (auto subResStr : subRes)
           res.push_back(str.substr(i, 1) + subResStr);
   }
   return res;
}

添加最后一个四个字符的测试用例验证一下，当然是没有问题的。

TEST(Anagrams, test_anagrams_of_biro)
{
    Result result = {"biro", "bior", "brio", "broi", "boir", "bori",
                    "ibro", "ibor", "irbo", "irob", "iobr", "iorb",
                    "rbio", "rboi", "ribo", "riob", "robi", "roib",
                    "obir", "obri", "oibr", "oirb", "orbi", "orib"};
    ASSERT_EQ(result, getAnagrams("biro"));
}

总结

通过实际的代码操练，体会了TPP的价值。在编程的初期，尽量使用一些具体的手段（高优先级），这样可以最大的保留问题的细节。随着TDD的深入，问题的本质会逐步的自动暴露出来。此时才采用一些更通用的的手段（低优先级）描述问题的本质。这种方式不仅可以控制变形的节奏，也帮助开发人员理解问题的本质，避免陷入僵局。

最后补充Uncle Bob关于TPP实施的注意事项：

1. When passing a test, preferhigher priority transformations.
   
   （在编写生产代码时，优选高优先级变形手段）
2. When posing a test chooseone that can be passed with higher priority transformations.
   
   （在编写测试用例时，优选可用高优先变形手段解决的测试用例）
3. When an implementationseems to require a low priority transformation, backtrack to see if there is asimpler test to pass.
   
   （当需要使用低优先级手段时，回头看看是否有更简单的测试用例）

来自为知笔记(Wiz)