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

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

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

背景

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

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

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

下面就讓我們一起來分析下這些問題吧。

死循環(huán) Case

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

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

無限循環(huán)

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

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

無限遞歸調(diào)用

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

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

RangeError: Maximum call stack size exceeded

無限渲染

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

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>;
}

第二個用例，控制臺輸出了以下報錯，并且渲染卡死。

檢測死循環(huán)

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

先考慮第一種 「無限循環(huán)」 場景，如果我們發(fā)現(xiàn)循環(huán)條件執(zhí)行結(jié)果始終為 true ，且循環(huán)體中沒有中止語句（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ù)雜、涉及外部輸出，需要運行時分析，故純靜態(tài)分析難以判斷

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

運行時判斷

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

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

對于無限循環(huán)的場景，可以這么處理：

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)換。

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

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)在，我們就擁有了中止無限循環(huán)代碼的能力。

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

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

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

用頻率代替時長

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

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

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 寫一個插件快速驗證

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

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í)行時間
        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ù)，可以通過 ReturnStatement 是否為 JSXFragment/JSXElement 進行判斷
      },
      // 普通函數(shù)組件，略
      FunctionDeclaration: (path, file) => {},
    },
  };
};

測試一下

const babel = require("@babel/core");
// 測試插件
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();
    }
  }
}

正好滿足我們的需求。