Расширение JQ Recursive Tree

Question

Я пытаюсь проанализировать структуру JSON для извлечения пути зависимости для использования в скрипте автоматизации.

Структура этого JSON извлекается в такой формат:

[
  {
    "Id": "abc",
    "Dependencies": [
    ]
  },
  {
    "Id": "def",
    "Dependencies": [
      "abc"
    ]
  },
  {
    "Id": "ghi",
    "Dependencies": [
      "def"
    ]
  }
]

Примечание: удалено множество других не относящихся к делу полей.

План состоит в том, чтобы передать моей команде JQ идентификатор одного из них и получить список обратно.

Например:

Ввод: abc
Ожидаемый вывод: []

Ввод: def
Ожидаемый вывод: ["abc"]

Ввод: ghi
Ожидаемый вывод: ["abc", "def"]

В настоящее время имеется такой скрипт jq (https://jqplay.org/s/NAhuXNYXXO):

    jq 
    '. as $original | .[] | 
    select(.Id == "INPUTVARIABLE") | 
    [.Dependencies[]] as $level1Dep | [$original[] | select( [ .Id == $level1Dep[] ] | any )] as $level1Full | $level1Full[] | 
    [.Dependencies[]] as $level2Dep | [$original[] | select ( [ .Id == $level2Dep[] ] | any )] as $level2Full | 
    [$level1Dep[], $level2Dep[]]'

Вход: abc
Выход: пусто

Ввод: def Ввод: ["abc"]

Ввод: ghi Ввод: ["def","abc"]

Отлично! Однако, как вы можете видеть, это не особенно масштабируемо и будет обрабатывать только два уровня зависимостей (https://jqplay.org/s/Zs0xIvJ2Zn), а также ужасно разваливается при наличии нескольких зависимостей на элементе (https://jqplay.org/s/eB9zHQSH2r).

Есть ли способ построить это в JQ или мне нужно перейти на другой язык?

Answer 1

Вот короткая программа, которая эффективно обрабатывает циклические зависимости и иллюстрирует, как можно определить подфункцию после создания локальной переменной (здесь, $ next) для эффективности:

def dependents($x):
  (map( {(.Id): .Dependencies}) | add) as $next
  # Input: array of dependents computed so far
  # Output: array of all dependents
  | def tc($x):
    ($next[$x] - .) as $new
    | if $new == [] then .
      else (. + $new | unique)
      # avoid calling unique again:
      | . + ([tc($new[])[]] - .)
      end ;
  [] | tc($x);

  dependents($start)

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

При заданном входе и вызове, таком как

jq --arg start START -f program.jq input.json

, для различных значений START выводится:

START output
abc   []
def   ["abc"]
ghi   ["def", "abc"]

Если вывод должен быть отсортирован, просто добавьте вызов до sort.

Answer 2

Я знаю, что данные не могут иметь циклические зависимости, они извлекаются из базы данных, которая обеспечивает это.

Тогда это тривиально. Сократите ввод JSON до объекта, где каждый Id и соответствующий массив зависимостей связаны, и просмотрите его, агрегируя зависимости, используя рекурсивную функцию.

def deps($depdb; $id):
  def _deps($id): $depdb[$id] // empty
    | . + map(_deps(.)[]);
  _deps($id);
deps(map({(.Id): .Dependencies}) | add; $fid)

Вызов:

jq -c --arg fid 'ghi' -f prog.jq file

^{Демонстрация в Интернете - произвольные уровни зависимостей
Демонстрация в режиме онлайн - множественные зависимости на Id}