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

Рекурсивные схемы используются для описания структур данных, в которых элементы могут содержать объекты того же типа. Подобные структуры встречаются в деревьях, графах, вложенных комментариях, файловых системах, AST-деревьях, меню навигации и многих других моделях данных.

Ajv полностью поддерживает рекурсивные схемы JSON Schema, включая:

самоссылки через $ref
взаимную рекурсию между схемами
динамическую рекурсию через $recursiveRef
рекурсию Draft 2019-09 и Draft 2020-12
переиспользование схем через $defs

Базовая идея рекурсии

Рекурсивная схема — это схема, которая ссылается сама на себя.

Простейший пример — дерево категорий:

{
  "name": "Electronics",
  "children": [
    {
      "name": "Phones",
      "children": []
    }
  ]
}

Каждый узел дерева содержит:

собственные данные
массив дочерних элементов того же типа

Простая рекурсивная схема

Описание дерева

const schema = {
  type: "object",

  properties: {
    name: {
      type: "string"
    },

    children: {
      type: "array",
      items: {
        $ref: "#"
      }
    }
  },

  required: ["name", "children"],

  additionalProperties: false
}

Что означает `$ref: "#"`

Символ # указывает на корень текущей схемы.

Фактически:

items: {
  $ref: "#"
}

означает:

items должны соответствовать всей текущей схеме

Получается рекурсивная структура:

node
 └── children[]
      └── node
           └── children[]
                └── node

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

import Ajv from "ajv"

const ajv = new Ajv()

const validate = ajv.compile(schema)

const data = {
  name: "Root",
  children: [
    {
      name: "Child 1",
      children: []
    },
    {
      name: "Child 2",
      children: [
        {
          name: "Nested",
          children: []
        }
      ]
    }
  ]
}

console.log(validate(data))

Результат:

true

Ошибка внутри глубокой вложенности

const invalidData = {
  name: "Root",
  children: [
    {
      name: "Child",
      children: [
        {
          children: []
        }
      ]
    }
  ]
}

Ошибка:

console.log(validate.errors)

Пример результата:

[
  {
    instancePath: "/children/0/children/0",
    keyword: "required",
    params: {
      missingProperty: "name"
    },
    message: "must have required property 'name'"
  }
]

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

Использование `$defs`

В реальных схемах рекурсивные структуры обычно выносятся в $defs.

Схема дерева через `$defs`

const schema = {
  $defs: {
    node: {
      type: "object",

      properties: {
        name: {
          type: "string"
        },

        children: {
          type: "array",

          items: {
            $ref: "#/$defs/node"
          }
        }
      },

      required: ["name", "children"],

      additionalProperties: false
    }
  },

  $ref: "#/$defs/node"
}

Почему `$defs` предпочтительнее

Такой подход:

делает схему читаемой
упрощает поддержку
позволяет переиспользовать определения
снижает вероятность циклических ошибок
облегчает композицию схем

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

Классическая задача — древовидные комментарии.

Пример данных

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

Схема

const schema = {
  $defs: {
    comment: {
      type: "object",

      properties: {
        id: {
          type: "integer"
        },

        text: {
          type: "string"
        },

        replies: {
          type: "array",

          items: {
            $ref: "#/$defs/comment"
          }
        }
      },

      required: ["id", "text", "replies"],

      additionalProperties: false
    }
  },

  $ref: "#/$defs/comment"
}

Рекурсивные структуры с разными типами узлов

Иногда узлы дерева имеют разные типы.

Например:

папка
файл

Структура файловой системы

{
  "type": "folder",
  "name": "src",
  "children": [
    {
      "type": "file",
      "name": "index.js"
    }
  ]
}

Схема

const schema = {
  $defs: {
    file: {
      type: "object",

      properties: {
        type: {
          const: "file"
        },

        name: {
          type: "string"
        }
      },

      required: ["type", "name"],

      additionalProperties: false
    },

    folder: {
      type: "object",

      properties: {
        type: {
          const: "folder"
        },

        name: {
          type: "string"
        },

        children: {
          type: "array",

          items: {
            $ref: "#/$defs/node"
          }
        }
      },

      required: ["type", "name", "children"],

      additionalProperties: false
    },

    node: {
      oneOf: [
        {
          $ref: "#/$defs/file"
        },
        {
          $ref: "#/$defs/folder"
        }
      ]
    }
  },

  $ref: "#/$defs/node"
}

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

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

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

Пример

user
 └── posts[]
      └── post
           └── author
                └── user

Схема

const schema = {
  $defs: {
    user: {
      type: "object",

      properties: {
        id: {
          type: "integer"
        },

        posts: {
          type: "array",

          items: {
            $ref: "#/$defs/post"
          }
        }
      },

      required: ["id", "posts"]
    },

    post: {
      type: "object",

      properties: {
        title: {
          type: "string"
        },

        author: {
          $ref: "#/$defs/user"
        }
      },

      required: ["title", "author"]
    }
  },

  $ref: "#/$defs/user"
}

Проблема бесконечной рекурсии

JSON Schema описывает структуру данных, а не реальные ссылки объектов JavaScript.

Поэтому схема:

{
  $ref: "#"
}

не вызывает бесконечного цикла сама по себе.

Ajv строит внутренний граф схем и корректно обрабатывает циклические ссылки.

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

JSON Schema не содержит встроенного механизма ограничения глубины.

Однако существуют обходные решения.

Вариант через разные уровни схем

const schema = {
  $defs: {
    level3: {
      type: "object",

      properties: {
        value: {
          type: "string"
        }
      }
    },

    level2: {
      type: "object",

      properties: {
        value: {
          type: "string"
        },

        child: {
          $ref: "#/$defs/level3"
        }
      }
    },

    level1: {
      type: "object",

      properties: {
        value: {
          type: "string"
        },

        child: {
          $ref: "#/$defs/level2"
        }
      }
    }
  },

  $ref: "#/$defs/level1"
}

Рекурсия и `anyOf`

Рекурсивные схемы часто комбинируются с anyOf, oneOf и allOf.

Пример AST-узлов

const schema = {
  $defs: {
    literal: {
      type: "object",

      properties: {
        type: {
          const: "Literal"
        },

        value: {
          type: "number"
        }
      },

      required: ["type", "value"]
    },

    binaryExpression: {
      type: "object",

      properties: {
        type: {
          const: "BinaryExpression"
        },

        left: {
          $ref: "#/$defs/expression"
        },

        right: {
          $ref: "#/$defs/expression"
        }
      },

      required: ["type", "left", "right"]
    },

    expression: {
      anyOf: [
        {
          $ref: "#/$defs/literal"
        },
        {
          $ref: "#/$defs/binaryExpression"
        }
      ]
    }
  },

  $ref: "#/$defs/expression"
}

Рекурсия между несколькими файлами схем

Ajv поддерживает внешние ссылки.

Схема `node.json`

{
  "$id": "https://example.com/node.json",

  "type": "object",

  "properties": {
    "name": {
      "type": "string"
    },

    "children": {
      "type": "array",

      "items": {
        "$ref": "https://example.com/node.json"
      }
    }
  }
}

Регистрация схемы

import Ajv from "ajv"

const ajv = new Ajv()

ajv.addSchema(nodeSchema)

const validate = ajv.getSchema(
  "https://example.com/node.json"
)

`$recursiveRef` и `$recursiveAnchor`

Начиная с Draft 2019-09 появился механизм динамической рекурсии.

Основная проблема обычного `$ref`

Обычный $ref всегда указывает на фиксированную схему.

Это затрудняет расширение рекурсивных схем через наследование.

Динамическая рекурсия

const treeSchema = {
  $id: "tree",

  $recursiveAnchor: true,

  type: "object",

  properties: {
    data: true,

    children: {
      type: "array",

      items: {
        $recursiveRef: "#"
      }
    }
  }
}

Что делает `$recursiveRef`

$recursiveRef ищет ближайший $recursiveAnchor.

Это позволяет:

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

Расширение рекурсивной схемы

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

const baseSchema = {
  $id: "base",

  $recursiveAnchor: true,

  type: "object",

  properties: {
    children: {
      type: "array",

      items: {
        $recursiveRef: "#"
      }
    }
  }
}

Расширенная схема

const extendedSchema = {
  $id: "extended",

  $recursiveAnchor: true,

  allOf: [
    {
      $ref: "base"
    },

    {
      properties: {
        title: {
          type: "string"
        }
      },

      required: ["title"]
    }
  ]
}

Теперь рекурсия будет ссылаться уже на extendedSchema, а не на baseSchema.

Особенности производительности

Рекурсивные схемы могут создавать:

глубокие вызовы функций
большое количество проверок
сложные ветвления

Особенно это заметно при:

anyOf
oneOf
больших деревьях
AST-структурах
тысячах узлов

Оптимизация

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

const ajv = new Ajv({
  discriminator: true
})

Минимизация `oneOf`

Плохо:

oneOf: [
  ...
  ...
  ...
  ...
]

Лучше:

properties: {
  type: {
    enum: ["a", "b"]
  }
}

Отключение лишних проверок

const ajv = new Ajv({
  allErrors: false
})

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

Неверный путь `$ref`

Ошибка:

$ref: "#/definitions/node"

при использовании $defs.

Правильно:

$ref: "#/$defs/node"

Потеря обязательных полей

Ошибка:

required: ["name"]

без children.

Из-за этого часть узлов может оказаться неполной.

Бесконтрольный `additionalProperties`

Если забыть:

additionalProperties: false

внутри рекурсивной схемы, структура может принимать произвольные поля на любом уровне вложенности.

Отладка рекурсивных схем

Просмотр ошибок

console.log(validate.errors)

Форматированный вывод

import Ajv from "ajv"
import addFormats from "ajv-formats"

const ajv = new Ajv({
  allErrors: true,
  verbose: true
})

ajv-errors

Плагин:

npm install ajv-errors

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

import Ajv from "ajv"
import ajvErrors from "ajv-errors"

const ajv = new Ajv({
  allErrors: true
})

ajvErrors(ajv)

Практические сценарии

Деревья DOM

element
 └── children[]
      └── element

Навигационные меню

menu
 └── items[]
      └── submenu

Категории интернет-магазина

category
 └── subcategories[]
      └── category

AST-компиляторы

expression
 └── expression
      └── expression

Организационная структура

employee
 └── subordinates[]
      └── employee

Рекурсия и TypeScript

Ajv часто используется совместно с TypeScript.

Рекурсивный тип

type TreeNode = {
  name: string
  children: TreeNode[]
}

Схема

const schema = {
  $defs: {
    node: {
      type: "object",

      properties: {
        name: {
          type: "string"
        },

        children: {
          type: "array",

          items: {
            $ref: "#/$defs/node"
          }
        }
      },

      required: ["name", "children"]
    }
  },

  $ref: "#/$defs/node"
}

Компиляция рекурсивных схем

Ajv компилирует рекурсивные схемы в JavaScript-код.

Во время компиляции:

строится граф ссылок
создаются внутренние функции валидаторов
обрабатываются циклические зависимости
оптимизируются повторные проверки

Генерация standalone-кода

import standaloneCode from "ajv/dist/standalone"

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

Ограничения JSON Schema

JSON Schema плохо подходит для:

циклических ссылок объектов JavaScript
графов с прямыми ссылками
двусвязных структур
проверки ссылочной целостности

JSON Schema валидирует структуру JSON, а не реальные объектные связи памяти.

Когда рекурсия особенно полезна

Рекурсивные схемы особенно эффективны для:

деревьев
AST
XML-подобных структур
вложенных меню
UI-компонентов
систем комментариев
категорий
файловых систем
иерархий ролей
организационных структур
конфигурационных DSL

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

Базовая идея рекурсии

Простая рекурсивная схема

Описание дерева

Что означает $ref: "#"

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

Ошибка внутри глубокой вложенности

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

Схема дерева через $defs

Почему $defs предпочтительнее

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

Пример данных

Схема

Рекурсивные структуры с разными типами узлов

Структура файловой системы

Схема

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

Пример

Схема

Проблема бесконечной рекурсии

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

Вариант через разные уровни схем

Рекурсия и anyOf

Пример AST-узлов

Рекурсия между несколькими файлами схем

Схема node.json

Регистрация схемы

$recursiveRef и $recursiveAnchor

Основная проблема обычного $ref

Динамическая рекурсия

Что делает $recursiveRef

Расширение рекурсивной схемы

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

Расширенная схема

Особенности производительности

Оптимизация

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

Минимизация oneOf

Отключение лишних проверок

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

Неверный путь $ref

Потеря обязательных полей

Бесконтрольный additionalProperties

Отладка рекурсивных схем

Просмотр ошибок

Форматированный вывод

ajv-errors

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

Практические сценарии

Деревья DOM

Навигационные меню

Категории интернет-магазина

AST-компиляторы

Организационная структура

Рекомендации по проектированию

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

Выделение базового узла

Добавление дискриминаторов

Ограничение дополнительных свойств

Использование идентификаторов

Рекурсия и TypeScript

Рекурсивный тип

Схема

Компиляция рекурсивных схем

Генерация standalone-кода

Ограничения JSON Schema

Когда рекурсия особенно полезна

Что означает `$ref: "#"`

Использование `$defs`

Схема дерева через `$defs`

Почему `$defs` предпочтительнее

Рекурсия и `anyOf`

Схема `node.json`

`$recursiveRef` и `$recursiveAnchor`

Основная проблема обычного `$ref`

Что делает `$recursiveRef`

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

Минимизация `oneOf`

Неверный путь `$ref`

Бесконтрольный `additionalProperties`

Использование `$defs`