一文詳解如何檢測(cè)并解決JS代碼中的死循環(huán)

更新時(shí)間：2023年09月11日 08:24:49 作者：francecil

這篇文章主要想和大家來(lái)一起探討一下能否通過(guò)靜態(tài)分析的方式檢測(cè)出死循環(huán),如果不能,我們又應(yīng)該如何在不借用其他線程的情況下,解決死循環(huán)卡住問(wèn)題,感興趣的可以了解下

背景

之前做的一個(gè)需求，需要探測(cè)用戶 js 代碼是否存在死循環(huán)。若發(fā)現(xiàn)死循環(huán)，則提前拋錯(cuò)，而不是繼續(xù)執(zhí)行直至線程卡死。

業(yè)界也有挺多類似的需求，比如 CodeSandbox 沙盒的 Infinite Loop Protection，可以避免用戶在調(diào)試代碼時(shí)寫了死循環(huán)導(dǎo)致頁(yè)面標(biāo)簽崩潰。

能否通過(guò)靜態(tài)分析的方式檢測(cè)出死循環(huán)？如果不能，我們又應(yīng)該如何在不借用其他線程的情況下，解決死循環(huán)卡住問(wèn)題？

下面就讓我們一起來(lái)分析下這些問(wèn)題吧。

死循環(huán) Case

什么情況下會(huì)導(dǎo)致死循環(huán)？列舉了常見(jiàn)的幾種情況：

無(wú)限循環(huán)：循環(huán)條件始終為正，且循環(huán)體中沒(méi)有中斷語(yǔ)句
無(wú)限遞歸調(diào)用
無(wú)限渲染：表現(xiàn)在 React 等視圖框架，渲染函數(shù)執(zhí)行時(shí)又觸發(fā)了數(shù)據(jù)變動(dòng)
...

無(wú)限循環(huán)

while (true) { // 循環(huán)條件也可能是一個(gè)很復(fù)雜、有外部入?yún)⒌呐袛嗾Z(yǔ)句，但始終為正
  // 死循環(huán)
  if(1 !== 2) { // 中止條件永不觸發(fā)
      return
  }
}

這類場(chǎng)景，循環(huán)條件始終為正，而在循環(huán)體中，要么沒(méi)有中止條件，要么中止條件永遠(yuǎn)不觸發(fā)，進(jìn)而導(dǎo)致線程卡死。

無(wú)限遞歸調(diào)用

(function recursive() {
  recursive(); // 死循環(huán)
})();

對(duì)于這類情況，執(zhí)行引擎在達(dá)到最大遞歸調(diào)用棧深度后，便會(huì)拋出 RangeError ，我們無(wú)需主動(dòng)處理。

RangeError: Maximum call stack size exceeded

無(wú)限渲染

這里以 React 框架為例，在 render 函數(shù)中又觸發(fā)了數(shù)據(jù)的變更。這邊的用例比較直白，現(xiàn)實(shí)中的用例可能會(huì)非常隱蔽。

import React from "react";
export default class App extends React.Component {
  constructor() {
    super();
    this.state = {
      num: 1
    };
  }
  render() {
    this.setState((state) => ({ state: state + 1 }));
    return <div>{this.state.num}</div>;
  }
}

import React, { useState, useEffect } from "react";

export default function App() {
  const [count, setCount] = useState(0);
  useEffect(() => {
    setCount(count + 1); // infinite loop
  }, [count]);
  return <div>hello</div>;
}

第二個(gè)用例，控制臺(tái)輸出了以下報(bào)錯(cuò)，并且渲染卡死。

檢測(cè)死循環(huán)

能否通過(guò)靜態(tài)分析的方式，檢測(cè)出一段代碼存在死循環(huán)？

先考慮第一種 「無(wú)限循環(huán)」 場(chǎng)景，如果我們發(fā)現(xiàn)循環(huán)條件執(zhí)行結(jié)果始終為 true ，且循環(huán)體中沒(méi)有中止語(yǔ)句（throw/return/break），那么這類用例必定是死循環(huán)。

while(true) {
    // 死循環(huán)
}

然而這樣的代碼畢竟是少數(shù)，大部分用例是在不經(jīng)意間寫出死循環(huán)的，比如

while (x > y && (x % 2 === 0 || y % 2 === 1)) {
  // 死循環(huán)，復(fù)雜條件難以分析
}

判斷復(fù)雜、涉及外部輸出，需要運(yùn)行時(shí)分析，故純靜態(tài)分析難以判斷

該問(wèn)題在可計(jì)算性領(lǐng)域被稱為停機(jī)問(wèn)題，已被證明無(wú)法通過(guò)一個(gè)通用算法分析出一段代碼是否存在死循環(huán)

運(yùn)行時(shí)判斷

既然靜態(tài)分析無(wú)法解決，那么是否換個(gè)思路：給循環(huán)體加點(diǎn)判斷代碼，當(dāng)循環(huán)次數(shù)過(guò)多或者循環(huán)執(zhí)行過(guò)久的時(shí)候，就認(rèn)為是死循環(huán)，并拋出異常。

我們先以執(zhí)行過(guò)久作為死循環(huán)判斷條件 （后面會(huì)繼續(xù)優(yōu)化） ：

對(duì)于無(wú)限循環(huán)的場(chǎng)景，可以這么處理：

while(true) {
    // 死循環(huán)
}
// 調(diào)整為
let _loopStart = Date.now() 
while(true) {
    if(Date.now() - _loopStart > MAX_TIMEOUT) {
        throw new RangeError('Potential infinite loop: exceeded')
    }
    // 死循環(huán)
}

for 循環(huán)、do...while 循環(huán)同理轉(zhuǎn)換。

對(duì)于循環(huán)的場(chǎng)景，可以這么處理：

import React from "react";
let _loopStart = Date.now() 
export default class App extends React.Component {
  constructor() {
    super();
    this.state = {
      num: 1
    };
  }
  render() {
    if(Date.now() - _loopStart > MAX_TIMEOUT) {
        console.warn('Potential infinite loop: exceeded')
        return;
    }
    this.setState((state) => ({ state: state + 1 }));
    return <div>{this.state.num}</div>;
  }
}

現(xiàn)在，我們就擁有了中止無(wú)限循環(huán)代碼的能力。

至于代碼是如何插入的，下一節(jié)會(huì)給出 babel 插件代碼。

現(xiàn)在的問(wèn)題是，使用執(zhí)行時(shí)長(zhǎng)作為判斷條件，是否合理？上面的第二個(gè)用例「無(wú)限渲染」很明顯就不正確，另外涉及異步場(chǎng)景，也依然有問(wèn)題。

for(let i=0;i<10;i++){
    await fetch('/xxx')
}

用頻率代替時(shí)長(zhǎng)

我們可以換個(gè)思路，統(tǒng)計(jì)兩次循環(huán)之間的間隔。若足夠小，說(shuō)明是同步代碼死循環(huán)；若足夠大，說(shuō)明是異步循環(huán)調(diào)用，可以不用考慮。

關(guān)于足夠小，我們可以粗淺的以 4ms 作為界限。通常來(lái)說(shuō)， 1ms 能夠執(zhí)行數(shù)百次指令，只要循環(huán)體中的代碼不是非常復(fù)雜，通常都能夠在 4ms 內(nèi)返回。再加入最大執(zhí)行次數(shù)進(jìn)行綜合判斷

while(true) {
    // 死循環(huán)
}
// 調(diào)整為
const MAX_ITERATIONS = 2000 // 最大可循環(huán)次數(shù)
const MAX_INTERVAL = 4 // 最大執(zhí)行間隔
let lastDate = Date.now() 
let loopCount = 0
while(true) {
    loopCount++
    if(Date.now() - lastDate <= MAX_INTERVAL && loopCount % MAX_ITERATIONS === 0) {
        throw new RangeError('Potential infinite loop: exceeded')
    } else {
        lastDate = Date.now()
    }
    // 死循環(huán)
}

Babel 處理

根據(jù)上面的分析，我們可以使用 babel 寫一個(gè)插件快速驗(yàn)證

關(guān)于 babel 插件的知識(shí)，可以查看中文官方文檔

const MAX_ITERATIONS = 2000; // 最大迭代次數(shù)
const MAX_INTERVAL = 4; // 最大執(zhí)行間隔
module.exports = ({ types: t, template }) => {
  // 生成循環(huán)體判斷條件
  const buildGuard = template(`
    %%iterator%%++
    if (%%iterator%% % %%maxIterations%% === 0 && Date.now() - %%lastDate%% <= %%maxInterval%%) {
      throw new RangeError('Potential infinite loop: exceeded ');
    } else {
        %%lastDate%% = Date.now()
    }
  `);
  return {
    visitor: {
      "WhileStatement|ForStatement|DoWhileStatement": (path) => {
        // 新增變量：執(zhí)行次數(shù)
        const iterator = path.scope.parent.generateUidIdentifier("loopIt");
        const iteratorInit = t.numericLiteral(0);
        path.scope.parent.push({
          id: iterator,
          init: iteratorInit,
        });
        // 新增變量：上次執(zhí)行時(shí)間
        const lastDate = path.scope.parent.generateUidIdentifier("lastDate");
        const lastDateInit = t.callExpression(
          t.memberExpression(t.identifier("Date"), t.identifier("now")),
          []
        );
        path.scope.parent.push({
          id: lastDate,
          init: lastDateInit,
        });
        // 插入循環(huán)體
        const guard = buildGuard({
          iterator,
          maxIterations: t.numericLiteral(MAX_ITERATIONS),
          lastDate,
          maxInterval: t.numericLiteral(MAX_INTERVAL) 
        });
        // 處理 No block statement 的情況，比如 `while (1) 1;`
        if (!path.get("body").isBlockStatement()) {
          const statement = path.get("body").node;
          path.get("body").replaceWith(t.blockStatement([guard, statement]));
        } else {
          path.get("body").unshiftContainer("body", guard);
        }
      },
      // 類組件函數(shù)，略
      ClassDeclaration: (path, file) => {},
      // 箭頭函數(shù)組件，略
      VariableDeclaration: (path, file) => {
        // 判斷是否為 JSX 函數(shù)，可以通過(guò) ReturnStatement 是否為 JSXFragment/JSXElement 進(jìn)行判斷
      },
      // 普通函數(shù)組件，略
      FunctionDeclaration: (path, file) => {},
    },
  };
};

測(cè)試一下

const babel = require("@babel/core");
// 測(cè)試插件
const code = `
while(true){
    for(;;) {
    }
}
`;
const result = babel.transformSync(code, {
  plugins: [require("./plugin")],
  // presets: ["@babel/preset-env"],
});
console.log(result.code);

得到如下輸出

"use strict";
var _loopIt = 0,
  _lastDate = Date.now();
while (true) {
  var _loopIt2 = 0,
    _lastDate2 = Date.now();
  _loopIt++;
  if (_loopIt % 2000 === 0 && Date.now() - _lastDate <= 4) {
    throw new RangeError('Potential infinite loop: exceeded ');
  } else {
    _lastDate = Date.now();
  }
  for (;;) {
    _loopIt2++;
    if (_loopIt2 % 2000 === 0 && Date.now() - _lastDate2 <= 4) {
      throw new RangeError('Potential infinite loop: exceeded ');
    } else {
      _lastDate2 = Date.now();
    }
  }
}

正好滿足我們的需求。