# 三重控制流平坦化
function n() {
  for (var e = 1; void 0 !== e;) {
    var a = 7 & e;
    var r = e >> 3;
    var s = 7 & r;
    switch (a) {
      case 0:
        switch (s) {
          case 0:
            i += "a";
            e = 2;
            break;
          case 1:
            if (i) {
              e = 0;
            } else {
              e = 2;
            }
            break;
          case 2:
            i += "hB";
            e = 8;
        }
        break;
      case 1:
        var c = "egdirbsj";
        var b = c.split("").reverse().join("");
        var k = j[b];
        var o = !k;
        if (o) {
          e = 3;
        } else {
          e = 5;
        }
        break;
      case 2:
        i += "ck";
        d(15, 0, k, i, t);
        return !0;
        ;
      case 3:
        return;
      case 4:
        var t = function (e) {
          var a = e[0];
          var r = "\u03a2\u03c3\u03b7\u03de\u03a8\u03cd\u03f7";
          var s = "";
          var c = 0;
          for (var b = 0; b < r.length; b++) {
            b || (c = 972);
            var k = r.charCodeAt(b);
            var o = k ^ c;
            c = k;
            s += String.fromCharCode(o);
          }
          var t = a === s;
          t && d(0, "");
        };
        var i = "pus";
        if (i) {
          e = 16;
        } else {
          e = 8;
        }
        break;
      case 5:
        var n = "def";
        n += "ault";
        k = k[n];
        var h = !k;
        if (h) {
          e = 6;
        } else {
          e = 4;
        }
        break;
      case 6:
        return;
    }
  }
}

上述为其模型的典型特征。

通过分析,我们可以发现,其中 for 循环中的 test 语句,为判断这个循环是否停止的条件,我们知道要使得 for 循环停止,可以添加 break 语句或者通过外嵌函数的方法,直接 return 出来,在这里我们可以看到,采用的是第二种方法,也就是说,在还原碰到 return 语句的时候,作为结束条件停止即可。

大变量:指代这里的 e

初始化参数:指代这里的 a、r、s

  1. 获取条件 test 表达式,获取初始化参数的值。

  2. 访问到最底部的节点,然后通过遍历的方式,获取其赋值语句,这里又分为两种情况:a. 在当前层数可以找到最顶部参数的赋值语句的地方 b. 在当前层数只能找到其上一节点的参数的赋值地方 (应对多重 switch 嵌套)。

    思路,从初始 for 循环出发,初始化变量的值,然后根据 SwitchStatement 获取到当前变量及其对应的值,然后进入到 case 节点的位置,这里需要进行一个判断,判断其下一层是否还是 SwitchStatemen 类型,如果不是,那么就进行节点的合并,在这里面一定会包含一个关于初始值变化的位置,因此需要在这些 Expressionstatement 中找到其赋值表达式 (Assignmentexpression),然后在进行一次计算,但是在这种情况下,难免会碰到更深层的 SwitchStatement,当游走到最深处的时候,需要判断,其是走向该 Switch 节点下的其他部分,还是赋值了大变量走入其他分支,最后根据 return 或者是结束语句判断是是否该 for 循环结束。

    核心思路:将初始化和判断语句写入一个函数,这样可以做到一次获取全部初始变量的值,将所有的 Switch 节点均写为一个类似字典的形式,方便进入对应的节点。

但是,有个致命的问题就是 IF 表达式判断。

image-20220314224908224

通过对这里的分析,发现其本质上是走的一个 for 循环的流程,同时,其对应的 else 节点属于结束节点。

大胆假设,假如 test 节点的类型为 BinaryExpression,同时其 right 部分为 MemberExpression,而且其 Identifier 部分为 length,那么这个就为 for 循环的 test 部分,同时其第一次 stack 包含的 var 声明式,在这里为 var E = 0; 代表 for 循环的起始值,其中有个流程包含 E++ 对应 for 循环的自增值。本质上这是一个环形结构。

# 流程梳理
# STEP1 运行步骤

初始化 b=4

进入该节点

image-20220317210749234

然后碰到 if 流,根据变量名判断,这属于函数参数名,所以这两个分支应该都会走到,进入第一个 b=8 的分支。

image-20220317210938365

发现,接下来走到的是 b=0 的分支。

image-20220317211033300

接着又进入了一个 if 分支,可以发现,这里是对 A 的长度进行了一个判断,进入 b=64 分支,

image-20220317211633194

先走 32 这个分支,给 x 赋值

image-20220317222822658

即接下来走的是 b=3 这个分支。

image-20220317211912799

然后又跳转到 128 分支

image-20220317212010367

然后又跳回 0 分支,也就是说,继续重复上述步骤。

那么我们需要梳理其流程,然后对其进行一个还原,在这里可以看到,我们在进入 b=0 分支后先进行了一个对其长度判断,然后

进入一长串循环该步骤,最后跳出到 b=2 这个分支。

其初始头为 b=0 结束头为 b=128.

我们最后希望将其还原为

var E=0

for(;E<A.length;){

​ ......

​ E++;

}

的形式,后面跟的是 b=2 的分支。

# 难点

image-20220329225917160

也就是说,在 if 的判断表达式为二元表达式,类似 a<b 这种形式的时候,都是生成的 for 循环,这样假如采取栈的形式当下一次的初值和开始的初值相等,那么就可以退出,但是,这是对于单情况而言,假如其中嵌套 if 表达式,那么还需对其进行一个判断。

思路:

  1. if 表达式的判断部分为二元表达式,进入 for 循环,此处对应的是该流程的外部参数,记录 if 表达式中左节点的参数名 (该处一般为接下来进行更新操作的地方)。
  2. 进行接下来的流程操作,假如直接是与 for 循环开始节点一样的值,那么直接返回,但是,假如是经过一个 if 表达式,其中,if 表达式的判断部分为一开始的左节点参数,一般,这个参数初始值为 0,即,随着 for 循环的运行,这个值会进入不同的流程,那么这部分的 If 表达式的节点都需要保留,那么,就只有在 else 节点结束后,才算退出 for 循环。

个人觉得,如果枚举全部情况,虽然还原后的结果看上去很好看,但是需要耗费大量的时间、精力,退而求其次,我们可以没必要一步到位,可以只还原 if 表达式,同时不对花指令进行删除,直接生成一个包含花指令的结果。

image-20220416214725791

以上述流程为例,这里流程 f 到流程 a 实际上是一个假流程,假如采用顺序执行还原,那么就会一直重复 abdfabdf 这几个部分,那么我们要做的是,建立一个类似栈的东西,将流程存入栈中,同时,这里的栈只包含 if 流程的初始值 (对应 if 左节点对应的流程参数),那么栈中的内容就为 abdf,如果在碰到 a,那么该流程就结束了。

/*****************************************************
 *
 *
 * Author:  mr2
 * Date:    2022-03-13
 * File:    SwitchFix
 * Project: ast_tools
 *****************************************************/
const parser = require("@babel/parser");
const types = require("@babel/types");
const generator = require("@babel/generator").default;
const traverse_Switch = {
    ForStatement(path) {
        fix(path)
    },
};
function get_other_expression(arr){
    let temparr = [];
    for(let i of arr){
        if(!types.isSwitchStatement(i)){
            temparr.push(i);
        };
    };
    return temparr;
};
function get_switch_expression(arr){
    for(let i of arr){
        if(types.isSwitchStatement(i)){
            return i
        };
    };
    return false
};
function get_switch_obj(SwitchNode){
    let CaseNode = SwitchNode.cases;
    let current_obj = {}
    for(let i of CaseNode){
        // 如果节点里为 SwitchStatement
        if(get_switch_expression(i.consequent)){
            current_obj[i.test.value] = get_switch_obj(get_switch_expression(i.consequent));
        }else {
            current_obj[i.test.value] = i.consequent;
        }
    };
    return current_obj;
};
function return_obj_create(init_expression, init_params_body){
    let temparr = [];
    for(let exp of init_params_body){
        temparr.push(types.objectProperty(types.stringLiteral(exp.declarations[0].id.name), exp.declarations[0].id));
    };
    temparr.push(types.objectProperty(types.stringLiteral(init_expression.declarations[0].id.name), init_expression.declarations[0].id));
    let now_obj = types.objectExpression(temparr);
    return now_obj;
};
// 游走到最底层节点
function get_lowest_node(init_value,SwitchNode, SwitchObj){
    // 给定初始对象
    let test_var = SwitchNode.discriminant.name;
    // 获取当前对象的初始值
    let now_case_value = init_value[test_var];
    // 进入最底层
    let now_node;
    if(types.isSwitchStatement(SwitchNode.cases[now_case_value].consequent[0])){
        // console.log(generator(SwitchNode.cases[now_case_value].consequent[0]).code);
        now_node = get_lowest_node(init_value, SwitchNode.cases[now_case_value].consequent[0], SwitchObj[now_case_value])
    }else {
        now_node = SwitchObj[now_case_value];
    };
    return now_node;
};
// 用于节点游走,为一个递归函数 (大变量初始值,对应的 SwitchStatement)
//base_var_name:for 循环的变量,for 循环的值,SwitchNode 对应的 node 节点,init_data 初始化变量,init_var_indentify 判断是否停止,SwitchObj 游走到底部节点,out_arr 用于保存参数,stack 用于记录不包含 If 的所有节点,var_stack 用于记录 for 循环生成的参数
function get_node_expression(base_var_name,value,SwitchNode,init_data,init_var_identify,SwitchObj,out_arr,stack,var_stack,test_node,for_stament_arr,if_stack){
     if(!init_var_identify(value)) return;
     if(if_stack.indexOf(value) > -1 ) return;
     let init_value = init_data(value);
     //console.log (' 开始进行变量初始化 ',init_value, init_var_identify (0));
     //console.log (' 当前 base_var_value',init_value [base_var_name]);
     if(for_stament_arr.length > 0 && for_stament_arr[for_stament_arr.length-1] == init_value[base_var_name]){
         return;
     }
     let now_arr = get_lowest_node(init_value,SwitchNode,SwitchObj);
     //console.log (' 当前参数 ',generator (types.blockStatement (stack)).code);
     //console.log (' 当前节点参数 ',generator (types.blockStatement (now_arr)).code);
     for(let i of now_arr){
         if(types.isExpressionStatement(i) && types.isAssignmentExpression(i.expression)){
             if(i.expression.left.name == base_var_name){
                 if(i.expression.operator == '='){
                     get_node_expression(base_var_name,i.expression.right.value,SwitchNode,init_data,init_var_identify,SwitchObj,out_arr,stack,var_stack,test_node,for_stament_arr,if_stack);
                     continue;
                 };
             }
         }
         if(types.isBreakStatement(i)) continue;
         if(!types.isIfStatement(i)) stack.push(i);
         if(types.isIfStatement(i)){
             // console.log(if_stack);
             //console.log (' 当前判断 ',generator (i.test).code);
             if_stack.push(value);
             let consequentExpression = i.consequent.body[0].expression;
             let alternateExpression = i.alternate.body[0].expression;
             let if_left_arr = [],if_right_arr = [];
             let now_stack = stack.slice(0);
             //for 循环的话不考虑 stack
             if(types.isBinaryExpression(i.test)){
                let begin_value = init_data(consequentExpression.right.value)[base_var_name];
                // 传入上一层的 value
                let result_arr = [];
                for_stament_arr.push(init_value[base_var_name])
                //console.log (' 开始生成 for 循环,此时节点的值为 ',for_stament_arr);
                let base_for_test_name = i.test.left.name;
                get_node_expression(base_var_name,begin_value,SwitchNode,init_data,init_var_identify,SwitchObj,result_arr,now_stack,var_stack,base_for_test_name,for_stament_arr,if_stack);
                //console.log ('for 循环样式:',generator (types.forStatement (null,i.test,null,types.blockStatement (result_arr))).code);
                // 只有判断表达式的右边类似 a.length 的形式才计算值
                 let for_type = types.forStatement(null, i.test, null, types.blockStatement(result_arr));
                 out_arr.push(for_type);
                let for_end_value = init_data(alternateExpression.right.value)[base_var_name];
                //console.log ('else 节点 value',for_end_value,' 开始进入 else 节点 ');
                for_stament_arr.pop();
                let else_result_arr = [];
                get_node_expression(base_var_name,for_end_value,SwitchNode,init_data,init_var_identify,SwitchObj,out_arr,now_stack,var_stack,test_node,for_stament_arr,if_stack);
                continue;
             } else {
             // 进入 if 节点的内部的时候,要传入上一层入口处的流程参数,然后在到该部分的时候,退出 if 节点
             // 递归计算左节点
             let left_stack=if_stack.slice(0),right_stack=if_stack.slice(0);
             //console.log (' 开始进入 '+generator (i.test).code+' 左节点 ');
             get_node_expression(base_var_name, consequentExpression.right.value, SwitchNode, init_data, init_var_identify, SwitchObj, if_left_arr, now_stack, var_stack, test_node, for_stament_arr, left_stack);
             // 递归计算右节点
             //console.log (' 开始进入 '+generator (i.test).code+' 右节点 ');
             get_node_expression(base_var_name, alternateExpression.right.value, SwitchNode, init_data, init_var_identify, SwitchObj, if_right_arr, now_stack, var_stack, test_node, for_stament_arr, right_stack);
             out_arr.push(types.ifStatement(i.test, types.blockStatement(if_left_arr), types.blockStatement(if_right_arr)));
             continue;
         }
         };
         if(out_arr) out_arr.push(i);
         if(types.isReturnStatement(i)) return;
     };
};
function fix(path) {
    const {init,test,update,body} = path.node;
    if(update) return;
    if(!init) return;
    let init_params_body = get_other_expression(body.body);
    let return_obj_statement = return_obj_create(init, init_params_body);
    init_params_body.push(types.returnStatement(return_obj_statement));
    // 将初始化的值 eval 进内存。后续可以直接调用
    eval(generator(types.functionDeclaration(types.identifier('init_var_identify'),
        [init.declarations[0].id],
        types.blockStatement([types.returnStatement(test)])
        )).code);
    eval(generator(types.functionDeclaration(types.identifier('init_data'),
        [init.declarations[0].id],
        types.blockStatement(init_params_body)
        )).code);
    let SwitchNode = get_switch_expression(body.body);
    let SwitchObj = get_switch_obj(SwitchNode);
    let out_arr = [],stack=[],for_stament_arr=[],if_stack=[];
    get_node_expression(init.declarations[0].id.name,init.declarations[0].init.value,SwitchNode,init_data,init_var_identify,SwitchObj,out_arr,[],stack,{},for_stament_arr,if_stack);
    // console.log(out_arr);
    path.replaceWithMultiple(out_arr);
};
exports.fix = traverse_Switch;

以这种思路会有致命的弊端,他的 if 流程越多,那么所需要的内存越大,如果有 1000 个 if,那么空间复杂度就是 2^1000,一般电脑带不动,会直接爆内存不足。。

Edited on

Give me a cup of [coffee]~( ̄▽ ̄)~*

Mr2 WeChat Pay

WeChat Pay