# 三重控制流平坦化
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
获取条件 test 表达式,获取初始化参数的值。
访问到最底部的节点,然后通过遍历的方式,获取其赋值语句,这里又分为两种情况:a. 在当前层数可以找到最顶部参数的赋值语句的地方 b. 在当前层数只能找到其上一节点的参数的赋值地方 (应对多重 switch 嵌套)。
思路,从初始 for 循环出发,初始化变量的值,然后根据 SwitchStatement 获取到当前变量及其对应的值,然后进入到 case 节点的位置,这里需要进行一个判断,判断其下一层是否还是 SwitchStatemen 类型,如果不是,那么就进行节点的合并,在这里面一定会包含一个关于初始值变化的位置,因此需要在这些 Expressionstatement 中找到其赋值表达式 (Assignmentexpression),然后在进行一次计算,但是在这种情况下,难免会碰到更深层的 SwitchStatement,当游走到最深处的时候,需要判断,其是走向该 Switch 节点下的其他部分,还是赋值了大变量走入其他分支,最后根据 return 或者是结束语句判断是是否该 for 循环结束。
核心思路:将初始化和判断语句写入一个函数,这样可以做到一次获取全部初始变量的值,将所有的 Switch 节点均写为一个类似字典的形式,方便进入对应的节点。
但是,有个致命的问题就是 IF 表达式判断。
通过对这里的分析,发现其本质上是走的一个 for 循环的流程,同时,其对应的 else 节点属于结束节点。
大胆假设,假如 test 节点的类型为 BinaryExpression,同时其 right 部分为 MemberExpression,而且其 Identifier 部分为 length,那么这个就为 for 循环的 test 部分,同时其第一次 stack 包含的 var 声明式,在这里为 var E = 0; 代表 for 循环的起始值,其中有个流程包含 E++ 对应 for 循环的自增值。本质上这是一个环形结构。
# 流程梳理
# STEP1 运行步骤
初始化 b=4
进入该节点
然后碰到 if 流,根据变量名判断,这属于函数参数名,所以这两个分支应该都会走到,进入第一个 b=8 的分支。
发现,接下来走到的是 b=0 的分支。
接着又进入了一个 if 分支,可以发现,这里是对 A 的长度进行了一个判断,进入 b=64 分支,
先走 32 这个分支,给 x 赋值
即接下来走的是 b=3 这个分支。
然后又跳转到 128 分支
然后又跳回 0 分支,也就是说,继续重复上述步骤。
那么我们需要梳理其流程,然后对其进行一个还原,在这里可以看到,我们在进入 b=0 分支后先进行了一个对其长度判断,然后
进入一长串循环该步骤,最后跳出到 b=2 这个分支。
其初始头为 b=0 结束头为 b=128.
我们最后希望将其还原为
var E=0
for(;E<A.length;){
......
E++;
}
的形式,后面跟的是 b=2 的分支。
# 难点
也就是说,在 if 的判断表达式为二元表达式,类似 a<b 这种形式的时候,都是生成的 for 循环,这样假如采取栈的形式当下一次的初值和开始的初值相等,那么就可以退出,但是,这是对于单情况而言,假如其中嵌套 if 表达式,那么还需对其进行一个判断。
思路:
- if 表达式的判断部分为二元表达式,进入 for 循环,此处对应的是该流程的外部参数,记录 if 表达式中左节点的参数名 (该处一般为接下来进行更新操作的地方)。
- 进行接下来的流程操作,假如直接是与 for 循环开始节点一样的值,那么直接返回,但是,假如是经过一个 if 表达式,其中,if 表达式的判断部分为一开始的左节点参数,一般,这个参数初始值为 0,即,随着 for 循环的运行,这个值会进入不同的流程,那么这部分的 If 表达式的节点都需要保留,那么,就只有在 else 节点结束后,才算退出 for 循环。
个人觉得,如果枚举全部情况,虽然还原后的结果看上去很好看,但是需要耗费大量的时间、精力,退而求其次,我们可以没必要一步到位,可以只还原 if 表达式,同时不对花指令进行删除,直接生成一个包含花指令的结果。
以上述流程为例,这里流程 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,一般电脑带不动,会直接爆内存不足。。