FormEditor 欄位內計算功能開發心得：叡揚部落格

一開始的需求

FormEditor 一直想要有類似 Excel 或 monday 那樣的計算功能。

2020 年三月得知這個需求後，本來打算安排實習生做。因為這個功能很好拆分，可以先完成語言設計，再和 FormEditor 整合在一起。事實上語言本身並不難做，反而花了很多時間調整 FormEditor 的結構才整合成功。

FormEditor 是什麼？

FormEditor 是 Vital BizForm 雲端智慧表單的核心功能，它提供了一個精簡、清爽、現代化的互動表單。可以製作自己的表頭、表格欄位，表格欄位可以水平分割或是垂直分割。還有多欄位表格可以用。欄位可以是文字、數字、下拉選單、單選清單、多選清單、日期、圖片，或是串接 CRM 資料。

這次實作的計算功能，讓使用者可以在網頁介面中，自行輸入我們定義的語言、引用文字或數字欄位中的值，並保留空間，以便未來處理更多不同類型的欄位。

在開始之前

要怎麼設計計算欄位呢？

在 2015 年左右，我參加了朋友辦的 Workshop ，在那個 Workshop 中，認識到個一種精簡的程式語言，叫做 λ-calculus ， λ 演算。

它的核心概念很簡單，從 JS 的角度來看就是說我們這個語言只有三個東西：值、函數、和把值應用到函數上這件事。於是程式就成了一個由這三種東西構成的樹（或者是圖，如果你共用了樹的節點的話）。再配上兩種規則：改名字的規則、和應用值到函數上怎麼化簡（reduce）的規則，我們就能做計算了。

這裡說的計算，更像是不斷套用剛剛提到的規則，把一棵語法樹，變成另一棵較小的樹。這個過程叫做 tree reduction （或是 graph reduction ）。

從這個角度出發，在設計 FormEditor 計算欄位時，先考慮的是「怎麼描述語法樹」，接著再決定「怎麼化簡這棵樹」，然後我們就有一個能動的語言了。

語法

於是設計此語言時，不是先寫下 BNF 才實作，反而是邊寫 parser ，邊寫 unit test 來決定它的行為。

語法節點有：

<empty>
<paren>
<num>
<str>
<boolean>
<list>
<subscript>
<error>
<field>
<list-field>
<func>
<binary>

它們可以分成兩類。

項 (term)

項 (term) 是求值的終點，所有的計算欄位最後都該算出一個項。

<empty>
<num>
<str>
<boolean>
<list>
<error>

<empty> 表示什麼都沒有，遇到空的輸入時，就會得到 <empty> 。

<num > 和 <str > 對應到兩種欄位類型，數字欄位與文字欄位，也可以表示直接輸入的值，例如 123 或 "John" 。

<boolean> 對應到 TRUE 和 FALSE 。

<list> 用來表示好幾個計算結果，通常一開始是多欄位的值，因為多欄位是一種一個名稱對應到許多有序的值的欄位。如果一個 <list> 裡面裝的東西都是 term ，無法繼續求值，那整個 list 也是個 term 。

<error> 則是用來表示和計算欄位有關的任何錯誤，包含 parsing 錯誤與 evaluation 錯誤。

Redex

Redex 指的是可化簡的表達式 (reducible expression) ，表示還可以求值的表達式。

<paren>
<list>
<subscript>
<field>
<list-field>
<func>
<binary>

<paren> 表示 () ，用來調整四則運算時的優先權。

只要 <list> 內還有可以求值的 redex ，那它也是個 redex 。

<subscript> 用來表示 list[3] 中的 [3] ，用來從 <list> 中取值。

<field> 表示參考另外一個欄位的值。

<list-field> 表示參考另外一個多欄位的值。

<func> 表示套用一個函數 (function application) 。

<binary> 表示一個二元計算，例如 a + b 。

實作

第一個實作的模組是語法模組， syntax.js 。

在這個模組中，我們直接把 JavaScript 函數當成「值的構造函數 (data constructor) 」用，而不經過 class 的 new 關鍵字。例如下面的 Num 會幫你生出個 <num> 節點：

export const Num = (value) => ({
  type: NodeType.NUMBER,
  value: value,
});

可以用的構造函數有： Empty, Paren, Num, Str, Bool, List, Subscript, Err, Field, ListField, Func 和 Binary ，和上面的語法一一對應著。

parser 模組就叫做 parser.js ，在寫 parser 時，我們靠 parsimmon 這個 parser combinator 函式庫，幫我們以小 parser 組合出大 parser 。雖然有這樣的組合能力，但為了方便，有些小 parser 還是靠 regular expression 處理它的輸入。

GitHub - jneen/parsimmon: A monadic LL(infinity) parser combinator library for javascript

A monadic LL(infinity) parser combinator library for javascript - jneen/parsimmon

https://github.com/jneen/parsimmon

從 parser 程式碼，我們可以整理出 BNF ：

<expr> ::= <subscript>
        |  <binary>
        |  <func>
        |  <field>
        |  <list-field>
        |  <num>
        |  <str>
        |  <empty>

<empty> ::= <optional-whitespaces>

<str> ::= <parsimmon-string>

<num> ::= <parsimmon-number>

<bool> ::= "true" | "false" | "TRUE" | "FALSE"

<subscript> ::= <subscript-base> "[" <num> "]"

<subscript-base> ::= "(" <binary> ")"
                  |  <subscriptable>

<subscriptable> ::= <func>
                 |  <field>
                 |  <list-field>
                 |  <str>

<field> ::= "{" <symbol-without-spaces-and-right-brace> "}"

<list-field> ::= "[" <symbol-without-spaces-and-right-bracket> "]"

<paren> ::= "(" <expr> ")"

<func> ::= <symbol> "(" <expr-list> ")"

<expr-list> ::= <expr>
             |  <expr> "," <expr-list>

<binary> ::= <mul-div-ops>
          |  <mul-div-ops> ("+" | "-") <binary>

<mul-div-ops> ::= <non-binary>
               | <non-binary> ("*" | "/") <mul-div-ops>

<non-binary> ::= <subscript>
              |  <func>
              |  <field>
              |  <list-field>
              |  <num>
              |  <str>
              |  <paren>

語境

當 FormEditor 切換到可以執行計算欄位的模式時（例如編輯時的預覽模式、撰寫模式），會以 FormEditor 的內部資料製作出計算語境 (context) 。

例如我們有三個欄位 title, summary, empty ， title 存著 "foo" ， summary 中存著 42 ， empty 中啥都沒放，那會得到這樣的語境：

{
  'title': {
    info: Cell.Field(),
    expr: Str('foo'),
  },
  'summary': {
    info: Cell.Field(),
    expr: Num(42),
  },
  'empty': {
    info: Cell.Field(),
    expr: Empty(),
  },
};

如果我們有一個欄位叫 formula ，裡面放著公式 {title} + {summary} ，會得到這樣的語境：

{
  'title': {
    info: Cell.Field(),
    expr: Binary('+', Field('title'), Field('summary')),
  },
};

如果我們有個多欄位叫做 foobar ，裡面有兩個欄位，放著兩個數字 41 和 42 ，會得到這樣的語境：

{
  'title': {
    info: Cell.ListField(2),
    expr: List([Num(41), Num(42)]),
  },
};

語境中的 info 現在用來表示這個欄位是單欄位還是多欄位，求值 (evaluate) 時我們需要這個資訊。

FormEditor 內部將單欄位、多欄位原型、多欄位本身分別存在三個不同的地方。單欄位在 dataBox.fields_description 、多欄位原型在 dataBox.form_description 、預覽模式中，從多欄位原型生出來的欄位在 dataBox.listrow_discription 。

在計算公式程式碼最上層的 index.js 中， contextFromDataBox 函數會幫我們從 dataBox 生出計算語境。每次公式更新都要呼叫它。同一個檔案中也暴露了其他函數，方便我們只更新部分計算語境，但在此不詳細說明。

FormEditor 多欄位資料是從單欄位改出來的，得另外整理，才能得出 displayName 和欄位間的關係。整理多欄位資料用的函數位於 FormEditor 的 utils 資料夾中。

求值

求值基本上就是不斷重複「找到可以求值的表達式 (redex) ，得出結果 (term) 」，直到無法繼續下去。在 FormEditor 中我們用到一種叫做 löb 的函數，幫我們把準備好的語境，映射成方便求值用的函數。為了要完成這件事，我們得先準備一個為計算語境設計的 map 函數：

function contextMap(ctx, f) {
  let result = {};
  for (let key in ctx) {
    const { info, expr } = ctx[key];
    result[key] = { info, expr: f(expr, info) };
  }
  return result;
}

就像 Array 的 map 會把 f 應用在所有的元素上， contextMap 也會把 f 應用在計算語境內所有的表達式上。而且 f 除了 expression 本身外，還可以得到欄位資訊 info 。

再準備 JavaScript 版的 löb 函數：

function contextLoeb(ctx) {
  let results;
  const go = (f) => () => f(results);
  results = contextMap(ctx, go);
  return results;
}

它的作用是把整個語境交給自己的每一個內容物。

最後將它們組合起來，就會得到我們的求值函數：

export function run(exprTable) {
  const table = validate(exprTable); // 檢查語境合不合法
  let ctx = contextMap(table, construct); // 把 evaluation rules 應用到計算語境上
  ctx = contextLoeb(ctx); // 計算所有的依賴和引用關係
  return contextMap(ctx, x => x()); // 得出計算結果
}

求值的時候，先靠一個 contextMap 把，用 construct 函數，把每個表達式都變成一個「根據語境來求值的函數」，再用 contextLoeb 把這些函數應用在整個語境的求值結果上。

最後再用一次 contextMap ，把每個求值函數都跑一次，就得到求值完成的語境了。

之所以最後還要跑一次，是因為 JavaScript 是一個嚴格 (strict) 求值的語言，得多墊一層函數，避免它過早求值導致程式卡死。

再來我們關心的是怎麼寫那個 construct 函數。

對項 (term) 求值

對一般項求值很無腦，基本上就是直接傳回它自己。 ( 和 ) 其實不算是個 term ，他還得把裡面的東西拿出來。

之所以特別為括號準備一種語法，是為了之後繪製到畫面上的時候可以保留括號，但又不必留太多關於原始公式的資訊。

function construct(expr, info) {
  switch (expr.type) {
    // 略
    case NodeType.EMPTY: return () => expr;
    case NodeType.PAREN: return () => expr.expr;
    case NodeType.NUMBER: return () => expr;
    case NodeType.STRING: return () => expr;
    case NodeType.ERROR: return () => expr;
    // 略
    default: return () => Err('FormFormula.Eval.UnknownExpression');
  }
}

對 list 求值也不難，對 list 內裝的表達式求值後，再放回 list 中就好了。用索引取值的時候，會先檢查求出來的表達式是不是 list ，是的話再拿出裡面裝的東西。

function construct(expr, info) {
  switch (expr.type) {
    // 略
    case NodeType.LIST: return (ctx) =>
      List(expr.values
        .map(v => construct(v, info))
        .map(thunk => thunk(ctx)));
    case NodeType.SUBSCRIPT: return (ctx) => {
      let result = construct(expr.value, info)(ctx);
      if (result.type === NodeType.STRING) {
        return Str(result.value[expr.index]);
      } else if (result.type === NodeType.LIST) {
        const target = result.values[expr.index];
        return target || Err('FormFormula.Eval.IndexOutOfBound', expr);
      } else {
        return Err('FormFormula.Eval.NotSubscriptable', result);
      }
    }
    // 略
  }
}

對欄位參考求值

對 field 和 list field 求值時，可以看到 löb 的威力。 löb 讓我們可以存取整個計算語境 ctx ，於是我們可以靠 expr.name 取得其他欄位內的表達式。

在操作 FormEditor 時，我們希望當一個多欄位引用另外一個單欄位的值時，會自動把那個單欄位的值放到每一個欄位中，於是此時會看 info 來檢查現在正在求值的欄位是不是多欄位。如果是，那當被參考的欄位為單欄位時，就會自動按欄位數量生出 list 。如果是多欄位，則不做事，反正多欄位內的 list 在顯示時會被展開到每個欄位中。

另外要注意的是，現在 field 和 list field 在功能上並沒有分別，之所以分兩種語法，除了為了畫面顯示之外，也保留空間，以便未來設計師修改 list field 的行為。

function construct(expr, info) {
  switch (expr.type) {
    // 略
    case NodeType.FIELD: return (ctx) => {
      const cell = ctx[expr.name];
      if (!cell || typeof cell.expr !== 'function') {
        return Err('FormFormula.Eval.FieldNotFound', expr);
      }
      const term = cell.expr(ctx);
      // 如果當前表達式在多欄位內，且引用了單欄位的值，則按欄位數量創造一個 list
      if (
        info.type === CellType.LIST_FIELD &&
        cell.info.type === CellType.FIELD
      ) {
        return List(range(info.count).map(() => term));
      }
      return term;
    }
    case NodeType.LIST_FIELD: return (ctx) => {
      const cell = ctx[expr.name];
      if (!cell || typeof cell.expr !== 'function') {
        return Err('FormFormula.Eval.ListFieldNotFound', expr);
      }
      const term = cell.expr(ctx);
      // 如果當前表達式在多欄位內，且引用了單欄位的值，則按欄位數量創造一個 list
      if (
        info.type === CellType.LIST_FIELD &&
        cell.info.type === CellType.FIELD
      ) {
        return List(range(info.count).map(() => term));
      }
      return term;
    }
    // 略
  }
}

對函數與二元運算子求值

原生函數 (primitive functions) 和二元運算子 (binary operators) 定義在獨立的 functionTable 中，放在 primitives.js 。

雖然它們都是以 JavaScript 實作的，但我們並不直接把值傳給 JavaScript 函數，而是把表達式傳過去，讓這些原生函數決定該怎麼處理。

這樣做的好處是，當未來引進不同的語法，例如 date 或是 currency 時，可以擴展我們的原生函數，而不被 JavaScript 奇怪的自動轉型影響。也可以實現兩個 list 相加之類的功能。

function construct(expr, info) {
  switch (expr.type) {
    // 略
    case NodeType.FUNCTION: return (ctx) => {
      const func = functionTable[expr.name];
      if (typeof func !== 'function') {
        return Err('FormFormula.Eval.FunctionNotFound', expr);
      }
      // 對參數求值
      const args = expr.args.map((e) => construct(e, info)(ctx));
      let errs = [];
      for (let arg of args) {
        if (arg.type === NodeType.ERROR) errs.push(arg);
      }
      if (errs.length) {
        return errConcat(errs);
      }
      return func.call(undefined, args);
    }
    case NodeType.BINARY: return (ctx) => {
      const func = functionTable[expr.name];
      if (typeof func !== 'function') {
        return Err('FormFormula.Eval.OperatorNotFound', expr);
      }
      const left = construct(expr.left, info)(ctx);
      const right = construct(expr.right, info)(ctx);
      let errs = [];
      if (left.type === NodeType.ERROR) errs.push(left);
      if (right.type === NodeType.ERROR) errs.push(right);
      if (errs.length) {
        return errConcat(errs);
      }
      return func.call(undefined, left, right);
    }
    // 略
  }
}

primitives.js 也包含了這些原生函數顯示在 FormEditor 公式編輯器裡的說明。

環狀引用分析

FormEditor 計算公式中，不存在使用者定義的函數，所以我們可以假設當用戶沒有寫出循環參考的公式時，計算公式一定會終止。

要偵測存不存在循環參考，我們先搜集每個表達式中參考到的欄位 (field) 名稱：

function collectFields(expr) {
  switch (expr.type) {
    case NodeType.PAREN:
      return collectFields(expr.expr);
    case NodeType.LIST:
      return expr.values.reduce((acc, arg) => acc.concat(collectFields(arg)), []);
    case NodeType.SUBSCRIPT:
      return collectFields(expr.value);
    case NodeType.FIELD:
      return [expr];
    case NodeType.LIST_FIELD:
      return [expr];
    case NodeType.FUNCTION:
      return expr.args.reduce((acc, arg) => acc.concat(collectFields(arg)), []);
    case NodeType.BINARY:
      return [...collectFields(expr.left), ...collectFields(expr.right)];
    default:
      return [];
  }
}

再來設計一個函數 walk ，可以從特定欄位開始，檢查計算過程中，這個欄位會看到哪些其他欄位：

function walk(ctx, field, seen) {
  const cell = ctx[field.name];
  if (!cell) return seen;
  const fields = collectFields(cell.expr).filter(fld => !seen[fld.name]);
  let current = {...seen};
  for (let fld of fields) {
    current[fld.name] = true;
  }
  return fields.reduce(
    (acc, fld) => objectConcat(acc, walk(ctx, fld, current)),
    current,
  );
}

最後可以檢查某個欄位是否參考到自己：

export function checkCycle(ctx, name) {
    const seen = walk(ctx, Field(name), {});
    return !!seen[name];
}

未來只要修改 collectFields ，就能支援新的語法。

整合

修改事件傳遞方式

原本 FormEditor 在欄位被修改後，會直接觸發全域回呼 (callback) 函數來通知外部程式。但為了加上計算公式，我們希望欄位被修改後，能在 FormEditor 的 UI 結構中傳遞，最後再通知外界。這樣過程中我就可以監聽從下往上傳的事件，決定什麼時候該更新計算公式。

欄位本身位在 FormFieldType.vue ，從這邊開始，靠 Vue 的 $emit 來把欄位資訊往上傳。

礙於目前 FormEditor 的結構，在往上傳的過程中，我們會在事件裡添加一些資訊，最後在 App.vue 的 HandleChange 與 HandleInput 中，再讓 Vuex 修改 store 中的計算語境。

另外因為 FormEditor 是靠 v-model 對資料做雙向綁定，在更新計算結果時，會再次觸發修改事件。為了避免大規模修改架構，我們另外做了一個 debounce 16ms 的 debouncedEmit 來把最後的計算結果往外界傳。

儲存原始碼與計算結果

欄位資訊通常叫做 field info ，每個欄位都可以選擇自己的型態，後端服務支援的欄位型態有：

text
textarea
number
dropdown
radio
checklist
date
datetime
image
signature
custom

我們這幾次添加的新欄位通通都屬於最後的 custom 型態。

新型態有：

related
autofill
formula

為了區分它們，現在把這些新型態放在 fieldInfo.value[0] 中。

為了封裝這件事，我們提供了自定義的 setter 和 getter ：

export function getType(fieldInfo) {
  return fieldInfo.type === FieldInfoType.CUSTOM
    ? fieldInfo.value[0]
    : fieldInfo.type;
}

export function setType(fieldInfo, type) {
  switch (type) {
    case FieldInfoPseudoType.RELATED:
    case FieldInfoPseudoType.AUTOFILL:
    case FieldInfoPseudoType.FORMULA:
      fieldInfo.type = FieldInfoType.CUSTOM;
      fieldInfo.value[0] = type;
      return;
    default:
      fieldInfo.type = type;
      return;
  }
}

呈現計算結果

計算結果仍是表達式，我們要把它轉成人類好讀的格式。要把表達式轉成字串不難：

export function print(expr) {
  switch (expr.type) {
    case NodeType.EMPTY: return '';
    case NodeType.PAREN: return `(${print(expr.expr)})`;
    case NodeType.NUMBER: return `${expr.value}`;
    case NodeType.STRING: return expr.value;
    case NodeType.BOOLEAN: return `${expr.value}`.toUpperCase();
    case NodeType.LIST: return `[${expr.values.map(print).join(', ')}]`;
    case NodeType.SUBSCRIPT: return `${print(expr.value)}[${expr.index}]`;
    case NodeType.ERROR: return `error: ${expr.message}`;
    case NodeType.FIELD: return `{${expr.name}}`;
    case NodeType.LIST_FIELD: return `[${expr.name}]`;
    case NodeType.FUNCTION: return `${expr.name}(${expr.args.map(print).join(', ')})`;
    case NodeType.BINARY: return `${print(expr.left)} ${expr.name} ${print(expr.right)}`;
    default: return '?';
  }
}

比較特別的是要把表達式呈現在網頁上這件事。如果直接把表達式轉成巢狀的 HTML DOM 元素，雖然好寫，但是無法讓瀏覽器幫我們自動換行。

於是我們在計算欄位的 token.js 中準備了顯示用的資料結構 Token ，在轉換成 HTML DOM 元素前，得先把表達式轉換成 Token 陣列，這樣才能把它從左自右畫出來：

export function printTokens(expr) {
  switch (expr.type) {
    case NodeType.EMPTY:
      return [];
    case NodeType.PAREN:
      return [
        LeftParen(),
        ...printTokens(expr.expr),
        RightParen(),
      ];
    case NodeType.NUMBER:
      return [Num(expr.value)];
    case NodeType.STRING:
      return [Str(expr.value)];
    case NodeType.BOOLEAN:
      return [Bool(expr.value)];
    case NodeType.LIST:
      return [
        LeftBracket(),
        ...expr.values.reduce((acc, e, i) => {
          const tokens = printTokens(e);
          if (i !== expr.values.length - 1) {
            return [...acc, ...tokens, Comma()];
          }
          return [...acc, ...tokens];
        }, []),
        RightBracket(),
      ];
    case NodeType.SUBSCRIPT:
      return [
        ...printTokens(expr.value),
        LeftBracket(),
        Num(expr.index),
        RightBracket(),
      ];
    case NodeType.ERROR:
      return [Err(expr.message, expr.payload)];
    case NodeType.FIELD:
      return [Field(expr.name)];
    case NodeType.LIST_FIELD:
      return [ListField(expr.name)];
    case NodeType.FUNCTION:
      return [
        Func(expr.name),
        LeftParen(),
        ...expr.args.reduce((acc, e, i) => {
          const tokens = printTokens(e);
          if (i !== expr.args.length - 1) {
            return [...acc, ...tokens, Comma()];
          }
          return [...acc, ...tokens];
        }, []),
        RightParen(),
      ];
    case NodeType.BINARY:
      return [
        ...printTokens(expr.left),
        Op(expr.name),
        ...printTokens(expr.right),
      ];
    default:
      return [];
  }
}

程式比 print 長一點，但一樣是分別處理各種表達式，再把結果接起來。