公式引擎架构设计

📊📝📽️ Univer General

本章节介绍 Univer 公式引擎的整体架构，建议在阅读本章节之前，先阅读整体架构。

公式引擎设计的主要目标如下：

支持 Univer 的不同文档类型和相关功能接入公式
提供快速的使用体验，支持和 web worker 和服务端计算
支持高级公式能力，对齐 Microsoft Office 365 所提供的功能，包括但不限于：
1. 感知公式执行状态，支持停止公式执行，支持循环引用检测及迭代计算执行次数设置
2. let / lambda 等自定义函数
3. 支持超级表、公式和范围命名

整体架构

架构图如下：

formula engine architecture

Model，存储公式初始数据，例如所在位置，公式字符串等
Engine，负责公式字符串的词法分析和语法分析，分析公式之间的依赖关系等等
Service，提供公式计算环境，提供注册函数的能力，并提供自定义名称、超级表、公式调度等服务
Command 和 Controller，负责控制公式模块协调运作
Function，实现函数

Model

主要管理公式字符串，通过引用化存储来优化内存占用。

formulaModelRef

此外还对数组公式、数公式范围的数据进行管理。

代码见 formula-data.model.ts (opens in a new tab)。

Engine

Engine 是公式引擎的核心，它提供以下能力：

依赖分析，对一组公式的执行顺序做出判断
对每一个公式字符串进行语法分析、词法分析，生成语法树
通过语法树进行计算
提供函数所需的大部分基础运算，包括加减乘除，字符拼接，三角函数等等

Engine 架构如下图所示：

engine

Lexer

负责对公式字符串进行词法分析。匹配引擎定义好的 token，根据规则生成节点，并将这些节点构建为 LexerNode tree。比如 A1、B10、SUM 等都会被识别为 LexerNode。节点类型的识别则会由 Parser 负责。例如

=(sum(sum(A1:B10), E10, 100) + 5) * 6 - 1

转换后的 LexerNode 树如下所示：

engineLexer

在生成 LexerNode 树之后，引擎会调用转换方法，采用后缀表达式 (opens in a new tab)来替换原始的中缀表达式以消除运算中的括号。例如

( 3 + 4 ) * 5 - 6

会转换为：

3 4 + 5 × 6 -

Parser

Parser 的职责主要是对 Lexer 生成的 LexerNode 树进行以下转换操作生成 AstNode 树：

将节点中的 SUM 等函数名转换为 FunctionNode 公式节点，E10 等引用转换为 ReferenceNode 引用节点，+ 等运算符转换为 OperatorNode 操作符节点
其他类型的 node 还包括：
1. LambdaNode lambda 函数专用，将 lambda 函数进行入参，以及包装为 lambda-value-object
2. UnionNode，把 A1:B10 合并为 RangeReference
3. PrefixNode，将 - 识别为负数，以及旧版本的兼容 @
4. SuffixNode，识别 % 为百分比，# 为动态数组公式的范围简写
5. ValueNode，识别文本、数字、逻辑三个基础类型的值
将 let 转换为 lambda 执行
为 lambda 注入参数

转换 LexerNode 树为 AstNode 树后的示意图：

engineParser

Interpreter

负责执行单个公式，调用 ast-node 的方法递归的得到函数返回值，主要有下列职责：

将运算符转换为 meta function 并执行，主要包括加减乘除运算符和数值比较运算符
将字符、数字，布尔值实例化为 ValueObject，将数组实例化为 ArrayValueObject
将 reference 实例化为 ReferenceObject，并调用内部方法转为 ArrayValueObject
调用具体函数开始执行运算，函数接收的值为所有 object 的基类 BaseValueObject，返回值为 ReferenceObject | BaseValueObject | AsyncValueObject
异步的计算会在上层 await 得到结果再传递到下层，所以函数内不需要写异步方法，只用把 Promise 作为参数传给 AsyncValueObject 并返回
对 INDIRECT 和 OFFSET 等引用函数，返回 ReferenceObject

BaseValueObject

BaseValueObject 是公式引擎计算非常重要的操作类型，它有下列继承类型：

NullValueObject

代表空值，再与其他类型值进行计算时会被当做 false 或 0，如果无法计算会直接返回 ErrorValueObject

ErrorValueObject

代表错误，类似 Excel 的 #VALUE!、#NAME!、#REF! 等，函数内可以直接返回 ErrorValueObject 代表公式计算错误。

PrimitiveValueObject

由可分为三种基础值类型，NumberValueObject StingValueObject 和 BooleanValueObject，分别实现了自己的数值计算方法，使用了 big.js (opens in a new tab) 处理底层计算的精度问题。

new NumberValueObject(100).plus(new NumberValueObject(100)); // return NumberValueObject
 
new StringValueObject(100).concatenateFront(new NumberValueObject(100)); // return StringValueObject
 
new NumberValueObject(100).isEqual(new NumberValueObject(100)); // return BooleanValueObject

LambdaValueObject

将 lambda 函数作为值传参给下层函数使用，会应用在 MAKEARRAY (opens in a new tab) REDUCE (opens in a new tab) 等函数中。

ArrayValueObject

是实现矩阵计算的核心，可以与任何 PrimitiveValueObject 或其他 ArrayValueObject 进行计算，计算演示如下图：

arrayObjectCalculate

其自身也支持如：sum、average、min、max、std、var、power 等计算，并且针对 vlookup、xlookup、match 等函数实现了如 Numpy 的 slice (opens in a new tab) 和 filter (opens in a new tab) 能力：

export class Vlookup extends BaseFunction {
  override calculate(
    lookupValue: BaseValueObject,
    tableArray: BaseValueObject,
    colIndexNum: BaseValueObject,
    rangeLookup?: BaseValueObject
  ) {
 
    const colIndexNumValue = this.getIndexNumValue(colIndexNum);
 
    // 对 tableArray 进行切片操作，获取第一列的矩阵
    const searchArray = (tableArray as ArrayValueObject).slice(, [0, 1]);
 
    // 对 tableArray 进行切片操作，获取 colIndexNumValue 指定列的矩阵
    const resultArray = (tableArray as ArrayValueObject).slice(, [colIndexNumValue - 1, colIndexNumValue]);
 
    // searchArray.isEqual(value) ，得到一个 true or false 的矩阵
    // resultArray.pick，调用 array 的 pick 方法从 true or false 的矩阵中范围对应索引的结果。相当于 numpy 的 filter
    // 最后通过 getFirstCell 返回匹配到的第一个结果值
    return resultArray.pick(searchArray.isEqual(lookupValue) as ArrayValueObject).getFirstCell();
  }
}

在公式数量较多的情况下，ArrayValueObject 实现了对列的倒排索引，以便于提升迭代性能：

arrayObjectInvertedIndex

Dependency

负责公式依赖分析，对需要计算的公式进行标脏，输出标脏公式的执行队列。

engineDependency

如上图所示，A1 单元格的内容变更后，会对 A2、A3、A4、A5 单元格的公式进行标脏，标脏后的公式进行依赖关系分析，最终的输出顺序为：A2 -> A3 -> A5 -> A4

如果遇到 INDIRECT / OFFSET (opens in a new tab) 等类似的引用函数，则 Dependency 模块会调用 Lexer 和 Parser 执行预计算，提前算出这类函数的引用范围，再以此进行依赖关系的计算。

Service

Service 为计算过程提供各种各样的服务，这里介绍几个重要的 service：

IFormulaCurrentConfigService 和 IFormulaRuntimeService

用于加载 Univer 数据，以及存放公式执行过程中的临时数据，公式执行完毕后 runtime 会返回所有计算结果

IFunctionService

用于函数和函数描述的注册，用户也可以通过 uniscript 注册快捷自定义函数。

IFeatureCalculationManagerService

注册数据透视表、条件格式、数据验证等 sheet 领域内的功能函数，以透视表为例：

数据透视表可以注册一个依赖范围和一个 getDirtyData
在公式对依赖范围标脏后执行 getDirtyData 方法，实现透视表内的计算逻辑
getDirtyData 方法可返回一个脏区和脏区的临时数据，用于继续计算依赖透视表结果的公式。最后得到正确结果。

IOtherFormulaManagerService

CalculateFormulaService

触发公式计算的核心方法，实现了如下功能：

公式循环依赖执行
运行时状态返回，包括执行公式总量，已执行完成数量。
数组公式返回结果后的二次标脏和执行
使用 requestImmediateMacroTask 避免了 setTimeout 4ms 限制，实现了公式在宏任务下的运行，支持公式执行终止。
公式执行时间统计

Function

采取矩阵计算的方式实现函数逻辑，减少了代码量，并且收敛了核心逻辑，让函数实现更加标准，可以保证准确性和质量。

公式引擎参考了 Numpy 的矩阵运算理念，减少了实现函数的代码量，并收敛了包括数值计算、三角函数计算到 BaseValueObject 中，为函数实现的标准化了做好了铺垫。

实现一个 Sum 公式的代码如下：

export class Sum extends BaseFunction {
  override calculate(...variants: BaseValueObject[]) {
    // 新建一个用于累加的 0 变量
    let accumulatorAll: BaseValueObject = new NumberValueObject(0);
 
    // Sum 函数的入参数量由用户决定，这里循环获取并计算。
    for (let i = 0; i < variants.length; i++) {
      let variant = variants[i];
 
      // 如果入参是 A1:B10 的引用范围，上层会把它自动转换为一个 ArrayValueObject，
      if (variant.isArray()) {
        // 调用 ArrayValueObject 上的 sum 函数，累加所有的 valueObject 值
        variant = (variant as ArrayValueObject).sum();
      }
 
      // 调用 ValueObject 上的数值计算函数 Plus 进行累加
      accumulatorAll = accumulatorAll.plus(variant);
    }
 
    return accumulatorAll;
  }
}

Univer 架构渲染引擎架构设计