Univer
Univer Doc
架构
公式引擎架构设计

公式引擎架构设计

📊📝📽️ Univer General

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

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

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

整体架构

架构图如下:

formula engine architecture

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

Model

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

formulaModelRef

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

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

Engine

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

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

Engine 架构如下图所示:

engine

Lexer

负责对公式字符串进行词法分析。匹配引擎定义好的 token,根据规则生成节点,并将这些节点构建为 LexerNode tree。比如 A1B10SUM 等都会被识别为 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 树:

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

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

engineParser

Interpreter

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

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

BaseValueObject

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

NullValueObject

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

ErrorValueObject

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

PrimitiveValueObject

由可分为三种基础值类型,NumberValueObject StingValueObjectBooleanValueObject,分别实现了自己的数值计算方法,使用了 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 领域内的功能函数,以透视表为例:

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

IOtherFormulaManagerService

注册 doc 和 slide 等非表格领域的公式,这些公式不会被 sheet 内的公式依赖,所以不需要返回脏区和脏区临时数据

CalculateFormulaService

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

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

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

Copyright © 2021-2024 DreamNum Co,Ltd. All Rights Reserved.