fast-checkを利用した再帰構造データのプロパティベーステストのワークアラウンド

こんにちわ。nap5です。

fast-checkを利用した再帰構造データのプロパティベーステストの紹介です

再帰データに関してはやや工夫が必要でして、そのワークアラウンドになります。

テスト対象のコードになります。

export type TFlattedMenu = {
  id: string;
  name: string;
  parentId: string | null;
};

export type TMenu = {
  id: string;
  name: string;
  parentId: string | null;
  children: TMenu[];
};

export const constructMenus = (menus: TFlattedMenu[]): TMenu[] => {
  const map = new Map<string, TMenu>(
    menus.map((menu) => [menu.id, { ...menu, children: [] }])
  );

  const result: TMenu[] = [];

  menus.forEach((menu) => {
    if (menu.parentId === null) {
      // トップレベルのメニュー項目を処理
      if (map.has(menu.id)) {
        const item = map.get(menu.id);
        if (item != null) {
          result.push(item);
        }
      }
    } else {
      // 子メニュー項目を処理
      if (map.has(menu.parentId)) {
        const parent = map.get(menu.parentId);
        if (parent != null) {
          if (map.has(menu.id)) {
            const item = map.get(menu.id);
            if (item != null) {
              parent.children.push(item);
            }
          }
        }
      }
    }
  });

  return result.filter(d => d.parentId == null);
};

export const flattenMenus = (
  menus: TMenu[],
  parentId: string | null = null,
  result: TFlattedMenu[] = []
): TFlattedMenu[] => {
  if (menus.length === 0) return result

  menus.forEach((menu) => {
    result.push({
      id: menu.id,
      name: menu.name,
      parentId: parentId,
    });

    if (menu.children.length > 0) {
      flattenMenus(menu.children, menu.id, result);
    }
  });

  return result;
};

デモデータになります

export type TFlattedMenu = {
  id: string;
  name: string;
  parentId: string | null;
};

export type TMenu = {
  id: string;
  name: string;
  parentId: string | null;
  children: TMenu[];
};

export const dbMenus: TFlattedMenu[] = [
  { id: "1", name: "Edit", parentId: null },
  { id: "2", name: "Undo", parentId: "1" },
  { id: "3", name: "Redo", parentId: "1" },
  { id: "4", name: "Cut", parentId: "1" },
  { id: "5", name: "Copy as", parentId: "1" },
  { id: "6", name: "Text", parentId: "5" },
  { id: "7", name: "Video", parentId: "5" },
  { id: "8", name: "Image", parentId: "5" },
  { id: "9", name: ".png", parentId: "8" },
  { id: "10", name: ".jpg", parentId: "8" },
  { id: "11", name: ".svg", parentId: "8" },
  { id: "12", name: ".gif", parentId: "8" },
  { id: "13", name: "Audio", parentId: "5" },
  { id: "14", name: "Share", parentId: "1" },
  { id: "15", name: "Mail", parentId: "14" },
  { id: "16", name: "Instagram", parentId: "14" },
  { id: "17", name: "Create", parentId: null },
  { id: "18", name: "As video", parentId: "17" },
  { id: "19", name: "As picutre", parentId: "17" },
  { id: "20", name: "Delete", parentId: null },
];

export const menus: TMenu[] = [
  {
    id: "1",
    name: "Edit",
    parentId: null,
    children: [
      { id: "2", name: "Undo", parentId: "1", children: [] },
      { id: "3", name: "Redo", parentId: "1", children: [] },
      { id: "4", name: "Cut", parentId: "1", children: [] },
      {
        id: "5",
        name: "Copy as",
        parentId: "1",
        children: [
          { id: "6", name: "Text", parentId: "5", children: [] },
          { id: "7", name: "Video", parentId: "5", children: [] },
          {
            id: "8",
            name: "Image",
            parentId: "5",
            children: [
              { id: "9", name: ".png", parentId: "8", children: [] },
              { id: "10", name: ".jpg", parentId: "8", children: [] },
              { id: "11", name: ".svg", parentId: "8", children: [] },
              { id: "12", name: ".gif", parentId: "8", children: [] },
            ],
          },
          { id: "13", name: "Audio", parentId: "5", children: [] },
        ],
      },
      {
        id: "14",
        name: "Share",
        parentId: "1",
        children: [
          { id: "15", name: "Mail", parentId: "14", children: [] },
          { id: "16", name: "Instagram", parentId: "14", children: [] },
        ],
      },
    ],
  },
  {
    id: "17",
    name: "Create",
    parentId: null,
    children: [
      { id: "18", name: "As video", parentId: "17", children: [] },
      { id: "19", name: "As picutre", parentId: "17", children: [] },
    ],
  },
  { id: "20", name: "Delete", parentId: null, children: [] },
];

テストコードになります。

コメントに書いたリンクを参考にするといいかもです。

親子関係の整合性を保証する工夫として以下を考慮し始めると、結構大変でした。

IDプール作って存在するIDをPopulateして重複が起きないようにし、かつ発番済みのIDのうち直近の親IDを葉ノードの親のIDに割り当て

import { describe, expect, test } from 'vitest'
import { dbMenus, menus } from './data'
import fc from 'fast-check';
import { TMenu } from './types';
import { constructMenus, flattenMenus } from './niceTree';

describe("Menu structure handy tests", () => {
  test("nested tree -> flattened tree", () => {
    const inputData = menus
    const outputData = flattenMenus(inputData, null, [])
    expect(outputData).toStrictEqual(dbMenus)
  })
  test("flattened tree -> nested tree", () => {
    const inputData = dbMenus
    const outputData = constructMenus(inputData)
    expect(outputData).toStrictEqual(menus)
  })
})

describe('Menu structure tests', () => {
  /**
   * 再帰的なメニュー構造を生成するユーティリティ関数
   * 
   * 親子関係の整合性を保証する工夫
   * 1. IDプール作って存在するIDをPopulateして重複が起きないようにし、かつ発番済みのIDのうち直近の親IDを葉ノードの親のIDに割り当て
   * 
   * @see https://github.com/dubzzz/fast-check/issues/1164#issue-744062952
   * 
   * @see https://github.com/dubzzz/fast-check/pull/3106#issuecomment-1232495323
   */
  const menuWithMaxDepth = (maxDepth: number): fc.Arbitrary<TMenu> => {
    const idSet = new Set<string>();

    const generateUniqueId = (): fc.Arbitrary<string> => {
      return fc.uuid().filter(id => !idSet.has(id));
    };

    const leaf = (parentId: string | null): fc.Arbitrary<TMenu> => fc.record({
      id: generateUniqueId(),
      name: fc.string({ minLength: 1, maxLength: 20 }),
      parentId: fc.constant(parentId),
      children: fc.constant([])
    }).map(menu => {
      idSet.add(menu.id);
      return menu;
    });

    const node = (depth: number, parentId: string | null): fc.Arbitrary<TMenu> => {
      return generateUniqueId().chain(id => {
        idSet.add(id);
        const childrenArb = depth <= 1
          ? fc.array(leaf(id), { maxLength: 3 })
          : fc.array(tree(depth - 1, id), { maxLength: 3 });

        return fc.record({
          id: fc.constant(id),
          name: fc.string({ minLength: 1, maxLength: 20 }),
          parentId: fc.constant(parentId),
          children: childrenArb
        });
      });
    };

    const tree = (depth: number, parentId: string | null): fc.Arbitrary<TMenu> => {
      return depth === maxDepth ? node(depth, null) : leaf(parentId);
    };

    return tree(maxDepth, null);
  };

  const menuArbitrary = menuWithMaxDepth(3)

  // const choiceDemoData = fc.sample(menuArbitrary, { numRuns: 3, seed: 1 })
  // console.log(JSON.stringify(choiceDemoData, null, 2))

  test('Property base test', () => {
    fc.assert(
      fc.property(
        fc.array(menuArbitrary),
        (menus) => {
          const flattened = flattenMenus(menus);
          const reconstructed = constructMenus(flattened);
          expect(reconstructed).toStrictEqual(menus);
        }
      )
    );
  });
});

サンプリングしますと、こういったデータが出力されます。

[
  {
    "id": "fbf92f4e-3364-3bff-bfff-ffff00000011",
    "name": "Q3~b)Vlt#)",
    "parentId": null,
    "children": [
      {
        "id": "94a68192-5ba2-5328-8000-001037734e2e",
        "name": "K&8$cl",
        "parentId": "fbf92f4e-3364-3bff-bfff-ffff00000011",
        "children": []
      },
      {
        "id": "00000009-001d-1000-9722-3d75db07a31c",
        "name": "Jscy$",
        "parentId": "fbf92f4e-3364-3bff-bfff-ffff00000011",
        "children": []
      }
    ]
  },
  {
    "id": "fffffffb-fffd-5fff-bfff-fffb1b2d8ac5",
    "name": "?",
    "parentId": null,
    "children": [
      {
        "id": "fffffff1-fff7-5fff-bfff-fffeffffffe4",
        "name": "appl",
        "parentId": "fffffffb-fffd-5fff-bfff-fffb1b2d8ac5",
        "children": []
      },
      {
        "id": "00000012-96f6-114f-b349-daa4e20e076e",
        "name": "~~}",
        "parentId": "fffffffb-fffd-5fff-bfff-fffb1b2d8ac5",
        "children": []
      }
    ]
  },
  {
    "id": "b9058f40-fff5-5fff-bfff-fff1fad5642b",
    "name": "D09?IX1%|",
    "parentId": null,
    "children": []
  }
]

demo code.

タイトル未設定

簡単ですが、以上です。