解开 Knuth 的结：如何重构意大利面条式代码？

这个问题的灵感来自如何将流程图转化为实施？ https://stackoverflow.com/questions/36647765它询问如何通过算法消除goto代码中的语句。这answer https://stackoverflow.com/a/36661381/4068338一般问题描述于this http://dl.acm.org/citation.cfm?id=512979科学论文。

我已经实现了一些代码如下高级草图来自 Knuth 的算法 X计算机编程的艺术描述了产生具有受限前缀的词典排列（见本期第 16 页draft http://www.cs.utsa.edu/~wagner/knuth/fasc2b.pdf).

这是对应的流程图 https://i.stack.imgur.com/v99AG.png上述算法。

这可能是一个very聪明和very高效的算法，但是结构代码似乎很难遵循。我最终使用了旧的goto-风格的实现：

//Algorithm X;
1:
initialize();
2:
enter_level(k);
3:
set(a[k],q);
if(test() == ok) {
  if (k == n) {
    visit();
    goto 6;
  }
  goto 4;
}
goto 5;
4:
increase(k);
goto 2;
5:
increasev2(a[k]);
if (q != 0) {
  goto 3;
}
6:
decrease(k);
if (k==0) {
  goto 7;
}
set(p,u_k);
goto 5;
7:
return;

问题是：如何重构这段代码以消除all the goto calls?

一个（虚假的）答案是建议“查找引用的科学论文，并逐行跟踪”——确实，这当然是有可能的。但这个问题是关于有经验的程序员一旦看到这个就会立即看到什么意大利面条代码 https://stackoverflow.com/questions/983574/unravelling-assembly-language-spaghetti-code.

我感兴趣的是how一步一步的重构，不仅仅是代码。

Note:

1. 根据算法 X 的高级规范和goto跳跃。实现黑盒功能initialize()等只需要一些额外的说明，但这些与结构的代码。函数调用期间发生的事情并不重要，因为现在的重点是程序的流程。
2. 通常争论的“是GOTO 仍然被视为有害吗？ https://stackoverflow.com/questions/46586/goto-still-considered-harmful“与这个问题完全无关，应该not在答案和评论中都得到解决。

有关的：如何使用或完成意大利面条代码？ https://stackoverflow.com/questions/4694053/how-to-work-with-or-complete-the-spaghetti-code

无需太多努力（也没有太多风险），您就可以快速减少 goto 和标签的数量。

1) 删除未在任何地方引用的标签（这将是标签 1:)

2）查找除了 goto 之外无法输入的代码块，这些代码在少数地方被调用。这些通常可以简单地分解出来。 4：可以通过将代码移动到调用它的地方来处理，并且可以安全地完成，因为它唯一的出口是 goto。这也允许我们删除上面的 goto 5，因为该代码将简单地跳转到 5:。 7：可以通过修改if语句来处理。此时我们有

initialize();
2:
enter_level(k);
3:
set(a[k],q);
if(test() == ok) {
  if (k == n) {
    visit();
    goto 6;
  }
  increase(k);
  goto 2;
}
5:
increasev2(a[k]);
if (q != 0) {
  goto 3;
}
6:
decrease(k);
if (k!=0) {
  set(p,u_k);
  goto 5;
}
return;

我倾向于在这里停下来。但如果继续下去，问题就变成了识别循环并用循环结构替换 goto。然而，由于代码的构造方式，进行这些更改的风险似乎要大得多。另外，你可能最终会遇到中断和继续，无论如何，这都是某种 goto。我最终得到的是这个（如果没有一些我不会保证它的正确性very严格测试）：

initialize();
enter_level(k);
while (true) {
  set(a[k],q);
  if(test() == ok) {
    if (k == n) {
      visit();
    } else {
      increase(k);
      enter_level(k);
      continue;
    }
  } else {
    increasev2(a[k]);
    if (q != 0) {
      continue; 
    }
  }
  while (true) {
    decrease(k);
    if (k!=0) {
      set(p,u_k);
      increasev2(a[k]);
      if (q != 0) {
        break; 
      }
    } else {
      return;
    }
  }
}

我做了3：一个循环，6：一个内循环。我通过复制 5: 代码来代替 goto，并用中断替换 goto 3，从而摆脱了 goto 5。这使得制作更干净的循环变得更容易。 goto 6 通过使用 else 来修复。 goto 3 继续。

之后（如果你还有精力）你可以尝试将循环从 while(true) 与 continue 更改为 whiles 与实际条件。

最好先开发测试，然后进行一两个更改并进行测试。进行另一次更改，然后再次测试。如果你不这样做，很容易在早期犯下结构性错误，然后使后续步骤无效并迫使你重新开始。