Рекурсивные схемы

Рекурсивные схемы используются для описания структур данных, содержащих ссылки на самих себя. Наиболее распространённые примеры:

  • древовидные структуры;
  • вложенные комментарии;
  • файловые системы;
  • AST (Abstract Syntax Tree);
  • графы;
  • меню с дочерними элементами;
  • категории с подкатегориями.

В обычных схемах достаточно прямого описания полей. Однако при рекурсии схема должна ссылаться сама на себя, что приводит к проблеме циклической зависимости во время инициализации.

Для решения этой задачи в Zod применяется механизм z.lazy().

Проблема циклической зависимости

Попытка напрямую сослаться на схему внутри самой себя приводит к ошибке:

import { z } from "zod";

const CategorySchema = z.object({
  name: z.string(),
  children: z.array(CategorySchema)
});

Ошибка возникает потому, что CategorySchema ещё не определена в момент обращения к ней.

JavaScript пытается прочитать переменную до завершения её инициализации.

Использование z.lazy

z.lazy() откладывает вычисление схемы до момента реального использования.

Базовый синтаксис:

z.lazy(() => схема)

Пример рекурсивной схемы:

import { z } from "zod";

const CategorySchema = z.lazy(() =>
  z.object({
    name: z.string(),
    children: z.array(CategorySchema)
  })
);

Теперь схема корректно ссылается сама на себя.

Рекурсивное дерево категорий

Описание структуры

type Category = {
  name: string;
  children: Category[];
};

Схема Zod

import { z } from "zod";

const CategorySchema: z.ZodType<Category> = z.lazy(() =>
  z.object({
    name: z.string(),
    children: z.array(CategorySchema)
  })
);

Проверка данных

const data = {
  name: "Programming",
  children: [
    {
      name: "JavaScript",
      children: [
        {
          name: "Node.js",
          children: []
        }
      ]
    },
    {
      name: "Python",
      children: []
    }
  ]
};

const result = CategorySchema.parse(data);

console.log(result);

Типизация рекурсивных схем

TypeScript не всегда способен автоматически вывести тип рекурсивной структуры. Поэтому часто применяется явное указание типа через z.ZodType.

Пример

type Node = {
  value: string;
  children: Node[];
};

const NodeSchema: z.ZodType<Node> = z.lazy(() =>
  z.object({
    value: z.string(),
    children: z.array(NodeSchema)
  })
);

Без z.ZodType<Node> TypeScript может вывести некорректный тип или потерять информацию о рекурсии.

Вложенные комментарии

Структура

type Comment = {
  id: number;
  text: string;
  replies: Comment[];
};

Схема

import { z } from "zod";

type Comment = {
  id: number;
  text: string;
  replies: Comment[];
};

const CommentSchema: z.ZodType<Comment> = z.lazy(() =>
  z.object({
    id: z.number(),
    text: z.string(),
    replies: z.array(CommentSchema)
  })
);

Проверка комментариев

const comments = {
  id: 1,
  text: "Главный комментарий",
  replies: [
    {
      id: 2,
      text: "Ответ",
      replies: [
        {
          id: 3,
          text: "Ответ на ответ",
          replies: []
        }
      ]
    }
  ]
};

CommentSchema.parse(comments);

Рекурсивные union-схемы

Рекурсия часто комбинируется с z.union().

Например, узел дерева может быть:

  • либо файлом;
  • либо директорией.

Файловая система

Типы

type FileNode = {
  type: "file";
  name: string;
  size: number;
};

type DirectoryNode = {
  type: "directory";
  name: string;
  children: Node[];
};

type Node = FileNode | DirectoryNode;

Схемы

import { z } from "zod";

type FileNode = {
  type: "file";
  name: string;
  size: number;
};

type DirectoryNode = {
  type: "directory";
  name: string;
  children: Node[];
};

type Node = FileNode | DirectoryNode;

const NodeSchema: z.ZodType<Node> = z.lazy(() =>
  z.union([
    z.object({
      type: z.literal("file"),
      name: z.string(),
      size: z.number()
    }),

    z.object({
      type: z.literal("directory"),
      name: z.string(),
      children: z.array(NodeSchema)
    })
  ])
);

Проверка структуры

const fileTree = {
  type: "directory",
  name: "src",
  children: [
    {
      type: "file",
      name: "index.ts",
      size: 1200
    },
    {
      type: "directory",
      name: "components",
      children: [
        {
          type: "file",
          name: "Button.tsx",
          size: 3400
        }
      ]
    }
  ]
};

NodeSchema.parse(fileTree);

discriminatedUnion и рекурсия

При наличии поля-дискриминатора эффективнее использовать z.discriminatedUnion().

Преимущества

  • более быстрая валидация;
  • понятные ошибки;
  • лучшая интеграция с TypeScript;
  • корректное narrowing типов.

Пример

import { z } from "zod";

type FileNode = {
  type: "file";
  name: string;
  size: number;
};

type DirectoryNode = {
  type: "directory";
  name: string;
  children: Node[];
};

type Node = FileNode | DirectoryNode;

const NodeSchema: z.ZodType<Node> = z.lazy(() =>
  z.discriminatedUnion("type", [
    z.object({
      type: z.literal("file"),
      name: z.string(),
      size: z.number()
    }),

    z.object({
      type: z.literal("directory"),
      name: z.string(),
      children: z.array(NodeSchema)
    })
  ])
);

Ограничение глубины рекурсии

Иногда требуется ограничить уровень вложенности.

Например:

  • защита от слишком глубоких JSON;
  • защита от DoS;
  • контроль структуры API;
  • ограничения UI.

Проверка через superRefine

import { z } from "zod";

type Category = {
  name: string;
  children: Category[];
};

const MAX_DEPTH = 3;

const CategorySchema: z.ZodType<Category> = z.lazy(() =>
  z.object({
    name: z.string(),
    children: z.array(CategorySchema)
  })
);

function validateDepth(
  node: Category,
  depth = 0
): boolean {
  if (depth > MAX_DEPTH) {
    return false;
  }

  return node.children.every(child =>
    validateDepth(child, depth + 1)
  );
}

const LimitedCategorySchema =
  CategorySchema.superRefine((value, ctx) => {
    if (!validateDepth(value)) {
      ctx.addIssue({
        code: z.ZodIssueCode.custom,
        message: "Превышена максимальная глубина"
      });
    }
  });

Рекурсивные массивы

Рекурсия может строиться не только через объекты.

Пример вложенных массивов

type NestedArray = (string | NestedArray)[];

Схема

import { z } from "zod";

type NestedArray = (string | NestedArray)[];

const NestedArraySchema: z.ZodType<NestedArray> =
  z.lazy(() =>
    z.array(
      z.union([
        z.string(),
        NestedArraySchema
      ])
    )
  );

Проверка

const data = [
  "a",
  [
    "b",
    [
      "c"
    ]
  ]
];

NestedArraySchema.parse(data);

Рекурсивные AST-структуры

AST широко используются:

  • в компиляторах;
  • парсерах;
  • интерпретаторах;
  • линтерах;
  • шаблонизаторах.

Арифметическое выражение

Типы

type NumberNode = {
  type: "number";
  value: number;
};

type BinaryNode = {
  type: "binary";
  operator: "+" | "-" | "*" | "/";
  left: Expression;
  right: Expression;
};

type Expression =
  | NumberNode
  | BinaryNode;

Схема

import { z } from "zod";

type NumberNode = {
  type: "number";
  value: number;
};

type BinaryNode = {
  type: "binary";
  operator: "+" | "-" | "*" | "/";
  left: Expression;
  right: Expression;
};

type Expression =
  | NumberNode
  | BinaryNode;

const ExpressionSchema: z.ZodType<Expression> =
  z.lazy(() =>
    z.discriminatedUnion("type", [
      z.object({
        type: z.literal("number"),
        value: z.number()
      }),

      z.object({
        type: z.literal("binary"),
        operator: z.enum(["+", "-", "*", "/"]),
        left: ExpressionSchema,
        right: ExpressionSchema
      })
    ])
  );

Проверка AST

const expression = {
  type: "binary",
  operator: "*",

  left: {
    type: "number",
    value: 10
  },

  right: {
    type: "binary",
    operator: "+",

    left: {
      type: "number",
      value: 2
    },

    right: {
      type: "number",
      value: 5
    }
  }
};

ExpressionSchema.parse(expression);

Частично рекурсивные схемы

Необязательно делать рекурсивной всю структуру.

Пример

import { z } from "zod";

const UserSchema = z.object({
  id: z.number(),
  name: z.string()
});

type TreeNode = {
  owner: z.infer<typeof UserSchema>;
  children: TreeNode[];
};

const TreeNodeSchema: z.ZodType<TreeNode> =
  z.lazy(() =>
    z.object({
      owner: UserSchema,
      children: z.array(TreeNodeSchema)
    })
  );

nullable и optional в рекурсивных схемах

Рекурсивные ссылки часто бывают необязательными.

nullable

type LinkedList = {
  value: number;
  next: LinkedList | null;
};
import { z } from "zod";

type LinkedList = {
  value: number;
  next: LinkedList | null;
};

const LinkedListSchema: z.ZodType<LinkedList> =
  z.lazy(() =>
    z.object({
      value: z.number(),
      next: LinkedListSchema.nullable()
    })
  );

optional

type TreeNode = {
  value: string;
  child?: TreeNode;
};
import { z } from "zod";

type TreeNode = {
  value: string;
  child?: TreeNode;
};

const TreeNodeSchema: z.ZodType<TreeNode> =
  z.lazy(() =>
    z.object({
      value: z.string(),
      child: TreeNodeSchema.optional()
    })
  );

Взаимная рекурсия

Иногда две схемы ссылаются друг на друга.

Пример структуры

type User = {
  name: string;
  posts: Post[];
};

type Post = {
  title: string;
  author: User;
};

Реализация

import { z } from "zod";

type User = {
  name: string;
  posts: Post[];
};

type Post = {
  title: string;
  author: User;
};

const UserSchema: z.ZodType<User> = z.lazy(() =>
  z.object({
    name: z.string(),
    posts: z.array(PostSchema)
  })
);

const PostSchema: z.ZodType<Post> = z.lazy(() =>
  z.object({
    title: z.string(),
    author: UserSchema
  })
);

Ошибки в рекурсивных схемах

Рекурсивные структуры могут генерировать очень длинные пути ошибок.

Пример ошибки

const data = {
  name: "Root",
  children: [
    {
      name: "Child",
      children: [
        {
          name: 123,
          children: []
        }
      ]
    }
  ]
};

CategorySchema.safeParse(data);

Ошибка:

[
  {
    path: ["children", 0, "children", 0, "name"],
    message: "Expected string, received number"
  }
]

safeParse в рекурсивных структурах

Для сложных вложенных структур безопаснее использовать safeParse.

const result = CategorySchema.safeParse(data);

if (!result.success) {
  console.log(result.error.format());
}

transform и рекурсия

Рекурсивные схемы поддерживают преобразования.

Пример нормализации

import { z } from "zod";

type Category = {
  name: string;
  children: Category[];
};

const CategorySchema: z.ZodType<Category> =
  z.lazy(() =>
    z.object({
      name: z.string().transform(v => v.trim()),
      children: z.array(CategorySchema)
    })
  );

preprocess и рекурсивные схемы

z.preprocess() позволяет подготовить данные до основной проверки.

Пример

import { z } from "zod";

const NumberTreeSchema = z.lazy(() =>
  z.object({
    value: z.preprocess(
      value => Number(value),
      z.number()
    ),

    children: z.array(NumberTreeSchema)
  })
);

Производительность рекурсивных схем

Рекурсивная валидация может быть дорогой операцией.

Основные факторы:

  • глубина вложенности;
  • количество узлов;
  • сложность union-схем;
  • наличие refine/superRefine;
  • transform/preprocess.

Потенциальные проблемы

Stack overflow

Слишком глубокая рекурсия может привести к переполнению стека:

const deep = {
  value: 1,
  child: {
    value: 2,
    child: {
      value: 3
    }
  }
};

При тысячах уровней вложенности возможен:

RangeError: Maximum call stack size exceeded

Оптимизация

Использование discriminatedUnion

z.discriminatedUnion(...)

работает быстрее обычного:

z.union(...)

Ограничение глубины

superRefine(...)

Избежание тяжёлых refine

Сложные вычисления внутри refine и superRefine могут многократно замедлять рекурсивную проверку.

infer и рекурсивные схемы

В простых случаях возможно получение типа через z.infer.

Пример

const TreeSchema = z.lazy(() =>
  z.object({
    value: z.string(),
    children: z.array(TreeSchema)
  })
);

type Tree = z.infer<typeof TreeSchema>;

Однако TypeScript иногда хуже обрабатывает сложную рекурсию через infer, чем через явное объявление типа.

Комбинирование recursive schema и extend

Базовая схема

const BaseNodeSchema = z.object({
  id: z.string()
});

Расширение

type TreeNode = {
  id: string;
  children: TreeNode[];
};

const TreeNodeSchema: z.ZodType<TreeNode> =
  z.lazy(() =>
    BaseNodeSchema.extend({
      children: z.array(TreeNodeSchema)
    })
  );

Комбинирование recursive schema и merge

const TimestampSchema = z.object({
  createdAt: z.date()
});

type Node = {
  createdAt: Date;
  children: Node[];
};

const NodeSchema: z.ZodType<Node> =
  z.lazy(() =>
    TimestampSchema.merge(
      z.object({
        children: z.array(NodeSchema)
      })
    )
  );

Проверка JSON-подобных структур

Рекурсия особенно полезна для описания JSON.

JSON-тип

type Json =
  | string
  | number
  | boolean
  | null
  | Json[]
  | { [key: string]: Json };

JSON-схема

import { z } from "zod";

type Json =
  | string
  | number
  | boolean
  | null
  | Json[]
  | { [key: string]: Json };

const JsonSchema: z.ZodType<Json> = z.lazy(() =>
  z.union([
    z.string(),
    z.number(),
    z.boolean(),
    z.null(),
    z.array(JsonSchema),
    z.record(JsonSchema)
  ])
);

Основные особенности z.lazy

Отложенная инициализация

Схема создаётся только при необходимости.

Поддержка самоссылок

children: z.array(NodeSchema)

Поддержка взаимных ссылок

UserSchema <-> PostSchema

Совместимость с любыми схемами

z.lazy() работает с:

  • object;
  • union;
  • discriminatedUnion;
  • array;
  • tuple;
  • record;
  • nullable;
  • optional;
  • transform;
  • refine;
  • preprocess.

Типичные ошибки

Отсутствие z.lazy

children: z.array(NodeSchema)

без:

z.lazy(...)

Бесконечная рекурсия в данных

Схемы Zod не умеют корректно обрабатывать циклические ссылки объектов:

const obj: any = {};

obj.self = obj;

Проверка подобных структур может привести к бесконечной рекурсии.

Потеря типов

const Schema = z.lazy(() => ...)

без:

z.ZodType<MyType>

может ухудшить типизацию.

Слишком сложные union-схемы

Большие рекурсивные union способны значительно замедлять валидацию.

Лучше использовать:

z.discriminatedUnion()

где это возможно.

Оглавление