关于javascript:如何优雅的实现一个表达式解释器

在流程编排、规定引擎等场景下，咱们常常会遇到对一段用户自定义表达式进行解释运行的需要。表达式语法能够很多样，以最近我遇到的一个需要场景为例，须要反对以下类型表达式的解释运行：

基于以上需要场景，咱们能够总结出，咱们须要的表达式解释器须要以下能力。

• 反对的数据类型：String/Number/Boolean/Array/Object
• 反对上下文拜访
• 反对属性拜访
• 反对运算符 + – * / === !== >= <= && ||
• 反对对象、数组、字符串的罕用办法

几种简陋的实现

要实现上述剖析的能力，咱们先来从能力实现角度登程疾速做几个简陋的实现。

with + eval

上面，基于 with + eval 来对表达式解释器进行一个简陋的实现。

function interpret(code, ctx) {return eval(`with(ctx){${code}}`);
}

const ctx = {a: 1, b: 2, c: { d: 3} };

const result = interpret(`a + c.d`, ctx);

console.log(result); // 4

eval() 存在两个显著的问题：

• 安全性问题：eval() 是一个危险的函数，因为第三方代码能够拜访到 eval() 被调用时的作用域，所以极易受到不同形式的攻打；
• 性能问题：eval() 的执行必须要调用 JS 解释器将 JS 代码转换成机器码，这就意味着 eval() 将强制浏览器破费大量老本查找变量名。另外，相似批改变量类型的行为也会强制浏览器破费老本从新生成机器码。

此时，举荐应用 Function() 来代替，因为 Function 构造函数创立的函数只能在全局作用域中运行，所以绝对 eval() 来说更平安且因为变量名查找上更加节约老本而绝对性能更好；

另外，with + eval 实现形式还有个致命问题，就是如果拜访指定上下文 ctx 没有的变量时，均会沿着 ctx 的作用域链向上查找变量。

示例如下：

function sandbox(code, ctx) {return eval(`with(ctx){${code}}`);
}

const ctx = {a: 1, b: 2, c: { d: 3} };

const outerName = 'jack';
const a = 10;

sandbox(`a + '_' + outerName`, ctx); // 1_jack

因而，接下来，咱们应用 with + Function 进行一个优化实现。

with + Function

上面是应用 with + Function 进行的一个表达式解释器实现

function interpret(code, ctx){return new Function('global', `with(global){return ${code}}`).call(ctx, ctx);
}

const ctx = {a: 1, b: 2, c: { d: 3} };

interpret(`a + c.d`, ctx); // 4

with + Function 的实现形式，尽管相较 with + eval 形式绝对更平安、性能更佳。

然而这种形式，也无奈解决 with + eval 形式的致命问题，变量的拜访会沿着作用域链逐级上找，直至拜访到全局变量。从而导致其余作用域中的变量和办法极易受到篡改或其余形式的攻打。

为了解决该致命问题，Proxy 给咱们提供了很好的解法。

with + Function + Proxy

上面介绍如何通过 with + Function + Proxy 的形式来实现表达式解释器，从而在实现机制上防止用户代码对其余作用域的拜访和篡改。

function sandbox(code, ctx = {}) {

    const ctxWithProxy = new Proxy(ctx, {has: (target, prop) => {if (!target.hasOwnProperty(prop)) {throw new Error(`Invalid expression - ${prop}`);
            }

            return target.hasOwnProperty(prop);
        }
    });

    return new Function('global', `with(global){${code}}`).call(ctxWithProxy, ctxWithProxy);
}

const ctx = {a: 1, b: 2, c: { d: 3} };

const e = 10;

sandbox(`return a + c.d`, ctx); // 4

sandbox(`return e`, ctx); // Error: Invalid expression - e

这种形式借助 Proxy 能够无效阻止用户代码对作用域链的拜访，看起来可能无效隔离以后作用域和其余父级作用域。那么这种形式是完满的形式吗？咱们前面会再进行详细分析。

Nodejs vm

如果你的代码是运行在 Node.js 中，那么还有一个更加简略的办法，就是 Node.js 的 vm 模块。

const vm = require('vm');

const x = 1;

const context = {x: 2};
vm.createContext(context); // Contextify the object.

const code = 'x += 40; var y = 17;';

vm.runInContext(code, context);

console.log(context.x); // 42
console.log(context.y); // 17

console.log(x); // 1; y is not defined.

该办法也可能无效阻断用户代码沿着作用域链进行非预期的拜访和篡改。

vm 模块的应用是很简略的，然而 vm 确是官网不举荐的一种办法，因为 vm 是不平安的。

The node:vm module is not a security mechanism. Do not use it to run untrusted code.

存在的问题

上述几种实现形式，均可能在性能上满足对表达式解释器的诉求，然而均存在一个致命的问题，那就是安全性问题。次要有以下几种安全性问题：

沙箱逃逸

可通过原型链拜访，实现沙箱逃逸，从而批改原生办法。

// 批改原生办法
sandbox(`({}).constructor.prototype.toString = () => { console.log('Escape!'); }; ({}).toString();`);

// 跳过 Proxy 限度执行非法代码
sandbox(`new arr.constructor.constructor('while(true){console.log("loop")}')()`, ctx)

退出过程

能够通过 constructor 拜访 process，操作过程。

// 执行 process.exit()
sandbox('var x = this.constructor.constructor("return process")().exit()');

裸露环境变量

能够通过 constructor 裸露环境变量。

sandbox('var x = this.constructor.constructor("return process.env")()');

透露源码

能够通过 process 透露源码。

sandbox('var x = this.constructor.constructor("return process.mainModule.require(\'fs\').readFileSync(process.mainModule.filename,\'utf-8\')")()');

执行命令行

可通过 process 执行命令行。

sandbox('var x = this.constructor.constructor("return process.mainModule.require(\'child_process\').execSync(\'cat /etc/passwd\',{encoding:'utf-8'})")()');

DoS 攻打

可通过循环语句 while 等进行 DoS 攻打。

sandbox('while(true){}');

一个不简陋的实现

设计思路

基于前文实现形式的问题剖析，对计划进行优化设计，须要满足以下在平安管控、根底能力和能力拓展三个方面的需要。

平安管控

• 防止宿主环境烦扰：不容许拜访 / 批改原型链（通过禁止拜访 __proto__、prototype、constructor 等）;
• 禁止原生办法调用：
• 禁止赋值、循环、条件判断语句：

根底能力

• 操作符反对，反对算数运算符、关系运算符、逻辑操作符、符号优先级 & 括号优先级、三元运算符等；
• 反对上下文拜访、属性拜访；

能力拓展

• Lodash 办法反对，反对所有 Lodash 办法，实现对对象、数组、字符串等的根底操作：

如何实现一个解释器

要实现一个解释器，咱们须要先理解如何实现一个解释器。

这里须要对解释器和编译器进行概念辨别。
解释器（Interpreter）是一个基于用户输出执行源码的工具；编译器（Compiler）是将源码转换成另一种语言或机器码的工具。

解释器会解析源码，生成 AST（Abstract Syntax Tree）形象语法树，一一迭代并执行 AST 节点。

解释器有四个阶段：

• 词法剖析（lexical analysis）
• 语法分析（syntax analysis）
• 语义剖析（semantic analysis）
• 执行（evaluating）

词法剖析

词法分析器读入组成源码的字符流，并且将它们组织成有意义的符号流。

a + b / c.d.e

+-----------------------+
| a | + | b | / | c.d.e |
+-----------------------+

语法分析

语法分析将词法剖析中生成的符号流转换为 AST 形象语法树。

AST 可视化示例：

AST 数据结构示例：

{
  "type": "Program",
  "start": 0,
  "end": 13,
  "body": [
    {
      "type": "ExpressionStatement",
      "start": 0,
      "end": 13,
      "expression": {
        "type": "BinaryExpression",
        "start": 0,
        "end": 13,
        "left": {
          "type": "Identifier",
          "start": 0,
          "end": 1,
          "name": "a"
        },
        "operator": "+",
        "right": {
          "type": "BinaryExpression",
          "start": 4,
          "end": 13,
          "left": {
            "type": "Identifier",
            "start": 4,
            "end": 5,
            "name": "b"
          },
          "operator": "/",
          "right": {
            "type": "MemberExpression",
            "start": 8,
            "end": 13,
            "object": {
              "type": "MemberExpression",
              "start": 8,
              "end": 11,
              "object": {
                "type": "Identifier",
                "start": 8,
                "end": 9,
                "name": "c"
              },
              "property": {
                "type": "Identifier",
                "start": 10,
                "end": 11,
                "name": "d"
              },
              "computed": false,
              "optional": false
            },
            "property": {
              "type": "Identifier",
              "start": 12,
              "end": 13,
              "name": "e"
            },
            "computed": false,
            "optional": false
          }
        }
      }
    }
  ],
  "sourceType": "module"
}

语义剖析

语义剖析会对 AST 形象语法树进行语义查看，查看 AST 是否和语言定义的语义统一。如果呈现不统一的状况，解释器就能够间接报错，阻断解释器解释并执行代码的过程。

执行

执行阶段会迭代整个 AST 形象语法树，一一执行各个 AST 节点。

示例如下：

5 + 7
|
    |
    v
+---+  +---+
| 5 |  | 7 |
+---+  +---+
  \     /
   \   /
    \ /
   +---+
   | + |
   +---+
{
    rhs: 5,
    op: '+'.
    lhs: 7
}

通过以上步骤，咱们就实现了一个简略的解释器。

表达式解释器有以下利用场景：

• 流程编排：通过动静脚本来治理流程调度，例如，基于微服务来动静搭建流程。
• 规定引擎：利用动静表达式来实时批改配置，例如，营销规定配置、审核流条件判断。

• 脚本引擎：利用动静脚本来实现在线编辑器。

  一个完满满足需要的实现 – Aexpr

  基于上述设计思路和解释器实现逻辑，我实现了一个完满满足需要的实现 – Aexpr。
  Aexpr 是一个平安的 JavaScript 表达式解释器，反对运算符、上下文拜访、属性拜访和 Lodash 办法。
  反对：

• 数据类型：number/boolean/string/object/array

• 运算符：

  • 数学运算符：+ – * /
  • 逻辑运算符：&& || > >= < <= === !==
  • 三元运算符：a ? b : c
• 上下文拜访
• 属性拜访
• 函数：反对所有 Lodash 办法，然而禁止函数类型的入参，以防止用户进行原型链拜访

Aexpr 的劣势是：

• 平安保障：

  • 通过无限的 AST 语义反对，防止原型链拜访，以达到沙箱隔离的成果
  • 通过禁用 while 等循环语句，防止 DoS 攻打
  • 通过禁止赋值语句 =，防止用户对原生办法或变量的篡改
  • 通过禁止原生办法的调用，防止非预期的攻打

• 能力拓展

  • 通过对所有 Lodash 办法的反对，满足了对对象、数组、字符串等数据类型的拓展反对

Aexpr 的 AST 形象语法树生成借助了一个好用的工具 Jison。Jison 能够反对自定义 AST 的生成语法，来生成咱们想要的 AST。

Aexpr 的应用示例：

const interpret = require('aexpr');

// invoke the function
// interpret(codeStr: string, context?: object);

// calculate
interpret('1 + 2 / 4 * 6');
interpret('1 + 2 / (4 * 6)');

// compare
interpret('1 > 2');
interpret('1 < 2');
interpret('1 <= 2');
interpret('2 <= 2');
interpret('2 === 2');

// logic
interpret('1 && 2');
interpret('1 || 0');

// context accessing && property accessing
interpret('a + b / c.d.e', { a: 2, b: 3, c: { d: { e: 5} } });

// lodash functions
interpret(`_.has(obj, 'a.b')`, {obj: { a: { b: 1, c: 2} } });
interpret('_.indexOf(arr, 1)', {arr: [1, 2, 3, 4] });

const arr = [{ 'user': 'barney', 'active': false},
    {'user': 'fred', 'active': false},
    {'user': 'pebbles', 'active': true}
];

// not support function type input params to avoid prototype access
expect(interpret.bind(null, `_.findIndex(users, function(o) {return o.user == 'barney';})`)).toThrow('Parse error');
// support ordinary input params
expect(interpret(`_.findIndex(users, { 'user': 'fred', 'active': false})`, {users: arr})).toBe(1);

参考资料

• Build a JS Interpreter in JavaScript Using Acorn as a Parser
• 从编译原理看一个解释器的实现
• 表达式引擎简介
• java 脚本引擎的设计原理浅析
• Drools, IKExpression, Aviator 和 Groovy 字符串表达式求值比拟
• Java 动静脚本 & 规定引擎、计算 / 表达式引擎
• jison
• 用 bison 做语法分析
• 编译器根本流程
• 前端技术 — 对于 JS 沙箱（JS 隔离）的几种计划带来的思考和瞻望
• 说说微前端 JS 沙箱实现的几种形式