如何探测 JS 代码中的死循环

[xieranmaya]

如何探测 JS 代码中的死循环

需求

最近在做一个工具（具体是什么工具，稍后再透露）的时候，我有一个需要探测代码中是否包含死循环的需求，而不管它有没有，我都想要我自己的代码能够继续执行下去。

停机问题

首先需要说明的是，理论上，没有通用的方法在不执行一段代码的情况下探测它是否包含死循环，因为这涉及到停机问题。而即使是执行这段代码，你依然无法判断它是陷入了死循环还是只是暂时没有结束循环而已。

关于为什么没有办法判断一段代码是否是死循环以及它与停机问题的关系，可以稍做一下解释：

假设我写了下面这段代码：

for(var i = 2;hasNextPrime(i); i++) {
    if (isPrime(i)) {
        console.log(i)
    }
}

代码意义很明显，它想把所有的素数都打印出来

现在我想要把它传给一个程序（后称法官程序）让这个程序来帮我判断这段代码运行后会不会停止

理想情况下（即让理想图灵机来运行这段代码）它应该是不会停止的，因为素数有无穷个。

但如果是法官程序来告诉我它会停止或者不会停止，将会发生什么呢？

1. 如果法官程序告诉我它会停止，则它就是在告诉我，素数是有限个的。
2. 如果法官程序告诉我它永远不会停止，则它就是在告诉我，素数有无穷个。

如果是第一种情况，显然是法官程序错了。
而如果是第二种情况，则我可以用这种方式证明非常多的数学理论和猜想。只要把这些猜想它们写成程序然后让这个法官程序来判断这段程序会不会结束就好了。如果会，则猜想正确，如果不会，则猜不正确，或者反过来。

而这就形成了一个悖论。关于停机问题，笔者了解的也不够深入，就只解释到这里好了。

判断死循环几种的思路

下面我们言归正传，那么如何判断一段代码是否会产生死循环呢？

一般的做法都是：我执行你的代码，但如果你的代码在一段时间内没有返回结果或没有结束运行，则我认为你的代码是死循环。

在前端（其实最常见的就是前端以及一些脚本语言中了），我们确实会遇到检测一段代码（尤其是别人写的代码）中是否有死循环这样的需求，如果是你，你会怎么做呢？可以先思考一下，思考完成后再继续阅读

直接运行被判断的代码

最容易想到的可能就是把代码运行起来了，然后看它能不能在一定时间内结束，如果能，当然皆大欢喜，如果不能，那就说明这段代码中有死循环。

但是这么做真的就足够了吗？试一下你就会发现这样做并不可行，因为在浏览器中 JS 是在单线程中执行的，而如果你执行了那段需要被 judge 的代码而它进入了死循环，页面会整体卡死，不能进行任何交互，只要这个死循环不结束，页面中任何其它代码都不会执行了，你的 “判断这段代码是否结束的代码” 当然也不会有机会执行。

所以这个方案其实并不可行。

Web Worker

不过当我提到单线程时，你应该想到了在现代浏览器中，提供了类似多线程的能力：Web Worker。其实这种方案之前就有人提过（http://cwestblog.com/2016/03/16/javascript-detecting-infinite-loops/），把代码放进 web Worker 里执行，然后如果在一定时间内没有收到来自这个 Worker 的响应事件，则认为这段代码进入了死循环，于是把这个 Worker 给 kill 掉。

但这个方案其实有一定的局限性：我们知道在 Web Worker 之前页面一直是构建于单线程之上的，Web 为了不引入过多的复杂性，也一直不允许使用多线程，你可能会以为 timer 算是多线程，其实它们只是 Event Loop。而终于在引入了 Web Worker 这个 “真正” 的多线程机制后，其实也有诸多的限制：比如说，在 Worker 线程内不允许访问能能够改变页面 UI 的任何 API。单就这一点，就让用 Worker 来判断代码是否可能进入死循环这条路的可行性大打折扣，因为这段被 judge 的代码可能也是需要访问 DOM 或者至少想要访问一些在 Worker 中不允许被访问的对象的。所以当你有这种场景时，这个方案并不可行。撇开这一点，它还有另外的问题，就是只有高级浏览器支持。

iframe或者新窗口/新标签

如果不用 Worker，顺着多线程的思路，容易想到，我们可以把代码放进 iframe 或者另一个页面（标签）里执行，然后看这个页面能否给我们反馈。这个思路看起来可行，其实还是有问题：

经过测试，如果一个页面的 iframe 里包含死循环，则整个标签都会卡死掉。

而如果你开一个新标签来运行被 judge 的代码，如果它产生了死循环，那么你将无法关闭那个标签页，因为它卡死了。

所以这两种方案也被否定了。

死循环如何才有可能产生？

那么还有没有办法能够即不让主页面卡死，还能 judge 某代码是否死循环呢？而且最好还能让这段代码与主代码在同一个环境下执行。

通过观察我们会发现，死循环只会由循环语句触发，也就是 for，while 和 do while 语句。你可能会说我们是不是漏考虑了递归，其实如果是递归函数中出现所谓的死循环，我们并不用担心，因为如果是纯递归造成的死循环，递归调用栈的深度很快会达到最大值，引擎会主动结束它，并抛出一个错误。

所以我们只需要判断所有的循环语句不会陷入死循环就可以了。

再说的简单点，就是只要保证循环语句不一直执行就可以了。

再说的直白点，就是我们如果发现循环执行的时间太久，就认为它陷入了死循环。

大致代码如下：

var start = new Date()
for (;;) {
    if (Date.now() - start > 1000) {
        throw new Error('Loop running too long!')
    }
    // normal code
}

另一个需要注意的是，如果真有 judge 某代码是否会死循环的这种需求，我们需要 judge 的代码一般来说都是由用户输入的，也就是说这段代码在执行之前，其实是文本。

另一种解决思路

那么我们可以分析这段文本所表示的代码，在里面所有的循环的前后插入一个我们自己的函数，在循环开始的时候计一下时，在循环体每次运行时也计一下时，然后与循环开始的时间进行对比，如果发现这个循环运行了太久（比如说一秒），就抛一个错误出来，这样循环就被这个抛出的错误给结束掉了。

你可能会说，如果这段循环被包在一个 try catch 块里面呢？抛的错误岂不是会被捕获到？确实会被捕获到，但是同时这个运行了太久的循环也结束了。而我们会把所有的循环前后都插入一个我们写好的用于统计时间的函数，同时甚至可以把代码的行号一同传给我们的函数。

大致代码如下，我们把计时函数封装成了一个 tick 函数：

tick(1)
for(;;) {
    tick(1)
    doSth()
    try {
        tick(2)
        while(true) {
            tick(2)
            doSthOther()
        }
    } catch(e) {

    }
}

tick(3,16);do {tick(3,16);//此处16是表示行号
    doAnotherThing()
} while(true)

我们给每一个循环语句的前后都插入一个 tick 函数，并给这两个 tick 函数传入相同的参数以标识循环语句的 id，然后执行这段代码。

注意我对 do while 循环的代码插入，对于典型风格的代码，我们可以在完全不改变代码行数量的前提下插入我们的代码，同时给 tick 传入当前代码的行号（因为在插入代码时，这段代码还是文本）做为其第二个参数，这样在其抛错时可以告诉我们具体是哪一行的循环陷入了死循环。

当第二个 tick(id) 发现自己相对于第一个 tick(id)（其只记录下循环开始的时间）在很长时间（比如一秒）以后还在被调用的时候，它就抛出一个错误，因为第二个 tick(id)是循环体内的第一个语句，它与循环头（for/while/do）之间并没有隔着一个 try，所以其抛错的话，会把死循环结束掉。

在抛错之前，tick 函数还可以告知我们，它在里面发现了一个死循环，甚至还可以告诉我们具体的行号。同时如果它抛出的这个错误没有被里面的代码 catch 到的话，错误则会冒泡直到被我们的代码捕获到，我们的代码既然 judge 这段代码，当然会把执行它的过程放在 try 里面了，如果我们的代码不是直接执行的这段代码，比如是把它放在 script 标签里执行的那我们可以通过 tick 函数主动给我们通知。

但还有一个问题，如何插入我们的代码看起来像是一个难题：如果代码有着良好的风格，所有的循环体都被大括号包着，而且循环判断条件也比较正常，这很好办，用简单的正则表达式就可以完成对代码的插入。但如果你遇到下面这样的代码要怎么办呢：

while (true) foo();

while (true)
    for (;;)
        do
            bar();
        while(true)

for(var i = 0; i<(function(){
    return 8
}()); i++) {
    console.log(i)
}

遇到这种代码，正则就很难正确的把我们的代码插入进去了。不能指望正则了。。。

不过也不是没有办法，我们可以先把代码解析成语法树（AST），然后通过修改语法树的形式来插入我们的代码，然后再把语法树转换回代码字符串。

JS 社区现在如此活跃，除了 Babel，还有不止一个可以解析语法树的工具，就不在此一一列举了。

这样一来就解决了如何 judge 一段代码是否包含死循环的问题。

然而事情并没有结束

等一等，我们是不是忽略了什么？

仅仅判断循环执行的时间真的足够了吗？

如果我们遇到下面这样的代码怎么办？

function * range(start, end) {
    for(var i = start; i<end; i++) {
        yield i // <<<<<<<<<<<<注意这一行
    }
}

如果是在异步场景里，两次 yield 的执行间隔可能是很久的。而如果我们仅仅只是判断循环 “执行” 的时间长度，即总是把循环体每次执行的时间点与循环开始执行的时间点进行对比，则并不能覆盖到这种情况，事实上循环并没有执行几次，但是因为 “执行” 了很久，会被我们误判，有没有什么解决方案呢？

当然是有的。可以很容易的观察到，在这种场景下，循环体执行的次数其实是非常有限的，所以我们可以在 tick 函数内部一边记录循环开始的时刻，一边记录循环体执行的次数，一边记录循环体最后一次执行的时刻。由此来计算出循环体执行的频率（以 Hz 为单位），如果执行频率非常高而且还执行的很久，则我们认为这是一个死循环。

那么问题又来了，如何选择一个合适的频率而尽量不发生误判呢？

其实这两种场景的界线是很明确的：一种是同步一种是异步。

而异步代码的执行间隔，最短也是两个事件循环之间的间隔。在浏览器中，两个事件循环之间的间隔一般来说是 4ms。换算成频率就是 250Hz。所以如果一个循环的执行频率远大于 250Hz 且执行了很长时间，则我们可以认为它陷入了死循环。而如果一个循环的执行频率在 250Hz 以内，则我们认为它其实是一个 generator 或者 async 函数，不对其进行抛错。

在 Node 中，两次事件循环的间隔是 1ms，也就是 1000Hz。如果一个循环真的在不停的同步执行的话，其实它的频率是元大于 1000Hz 的，根据不同的场景，同步循环的循环体执行频率大概在一百万赫兹到一千万赫兹的数量级，所以还是有明显区分的：

如果一个循环的执行频率在 10000Hz 以上，可以认为是同步循环。
而如果在 10000Hz 以下，则可以认为是异步循环。

如此一来，我们可以极大的减少误判的可能性，甚至是能够杜绝。

后续分析

POC

为了验证我的想法，我把这个功能写成了一个小的库，地址在这里：https://github.com/xieranmaya/infinite-loop-detector，已经在我文首提到的产品在使用了。

目前只是最初级的版本，仅用了正则表达式替换代码，用到的正则也非常简单，只能匹配按照典型风格书写的代码。也没有前文提到的检测频率和代码行号的功能。如果你有这方面的需求，欢迎给我提 Pull Request。

主要提供一个方法：infiniteLoopDetector.wrap(codeStr) 用来把一段表示 代码的字符串提换成被插入了 detector 函数的代码。仅支持传入字符串，不能传函数，object 等，就像 eval 一样。因为如果把这些对象转换成字符串，可能会损失词法作用域，暂时这么做，传的类型不对就抛错。大概这么用：

var code = `
for (;;) {
  console.log(1)
}`

code = infiniteLoopDetector.wrap(code)
// Can only wrap plain code string, no function or other things, or it will throw
// There is also an `unwrap` method to restore the converted code to the previous shape

try {
  eval(code)
} catch(e) {
  if (e.type === 'InfiniteLoopError') {
    console.log('infinite loop detected')
  }
}

关于词法作用域的损失，理论上来说这不是一个需要担心的问题，因为如果你要 judge 一段代码是否包含死循环，很大程度上这段代码是首先以字符串形式存在的，比如是用户输入的代码，而不是处于某个作用域内的活代码，于是就不存在词法作用域的问题了。如果真的要判断一段活代码是会陷入死循环，只转换局部的代码（除非它是纯函数）肯定是会让词法作用域损失掉的，能做的只有把那段代码所在的 script 标签的内容或者整个 js 文件给转换了，索性这种情况并不多。

跟 Node 和 require 的集成

如果你在 Node 上有强烈的探测死循环的需求，你甚至可以对 require 做一下 patch，让被 require 进来的代码自动被 wrap 成插入了检测函数的代码，当然，也可以在浏览器中实现类似的机制。具体怎么对 require 进行 patch，相关的技术文章有很多，就不在此文详述了。

不过如果你已经大量使用了 import 来管理自己 js 代码的依赖，那可能就要在编译过程上动刀子了。编译过程在目前基本已经是前端开发必备的步骤了，检测死循环也可以从这个点切入，在编译过程中增加代码变幻。

如果你有更好的思路也欢迎探讨~

全文完，谢谢阅读。如有纰漏之处还请留言指正。

原创文章，禁止转载。

[zz-33]

有些启发，3Q...