8.2. Разрешение зависимостей пакета

8.2.1. Разбор задачи

Рассмотрим задачу разрешения зависимостей пакета, граф зависимостей которого показан на рис. 44:

Зависимости разрешаются для пакета app, необходимо найти минимальное по числу пакетов решение.

В приведённом графе стрелки, соединяющие пакеты, обозначают факт наличия зависимости одного пакета от другого пакета. Например, из графа зависимостей следует, что для корректной работы пакета app версии 1.0.0 необходимо установить пакет react версии 3.1.0.

В том случае, если пакет заданной версии соединён несколькими стрелками с несколькими версиями другого пакета, то это значит, что тот пакет, из которого исходят стрелки, совместим с несколькими версиями другого пакета. Так, например, в приведённом выше графе зависимостей пакет app совместим с любой из версий пакета monaco-editor – как с monaco-editor 2.3.0, так и с monaco-editor 2.2.0. Поскольку речь идёт о минимальном по числу пакетов решении, необходимо выбрать одну из версий пакета monaco-editor, проверив транзитивные зависимости пакета app на наличие конфликтов версий.

При выборе пакета monaco-editor версии 2.3.0 возникает конфликт: monaco-editor одновременно требует установки пакета lodash 2.6.0 и пакета @replit/codemirror-css-color-picker 3.3.0, при этом пакет @replit/codemirror-css-color-picker 3.3.0 совместим только с lodash 2.5.0. Значит, разрешить зависимости для monaco-editor 2.3.0 не получится.

Аналогичным образом проверив другие подграфы легко найти решение, минимальное по числу пакетов:

Установить app 1.0.0.
Установить monaco-editor 2.2.0.
Установить @replit/codemirror-css-color-picker 3.4.0.
Установить react 3.1.0.
Не устанавливать lodash.

Выделим на графе зависимостей рис. 44 выбранные версии пакетов символом «✓», а символом «✕» – один из конфликтов версий. Результат показан на рис. 45:

Рисунок 45. Решение задачи выбора версий зависимостей

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

Введём следующие обозначения:

Пакет app обозначим как $a$.
Пакет monaco-editor – как $m$.
Пакет @replit/codemirror-css-color-picker – как $c$.
Пакет lodash – как $l$.
Пакет react – как $r$.

Версию пакета будем указывать справа от его имени. Тогда формула с логическими переменными для графа, показанного на рис. 44, будет иметь вид:

$$ \begin{align} ( a_{1.0.0} \implies m_{2.3.0} \lor m_{2.2.0} ) \land ( a_{1.0.0} \implies r_{3.1.0} ) \land ( m_{2.3.0} \implies c_{3.3.0} ) \land \\ ( m_{2.3.0} \implies l_{2.6.0} ) \land ( m_{2.2.0} \implies c_{3.5.0} \lor c_{3.4.0} ) \land ( c_{3.5.0} \implies l_{2.6.0} ) \land \\ ( c_{3.5.0} \implies r_{3.2.0} ) \land ( c_{3.4.0} \implies r_{3.1.0} ) \land ( c_{3.3.0} \implies l_{2.5.0} ) \land \\ ( c_{3.3.0} \implies r_{3.2.0} ) \land a_{1.0.0}. \end{align} $$

(5)

Легко убедиться, что при выбранных вручную версиях пакетов $a_{1.0.0}$, $m_{2.2.0}$, $c_{3.4.0}$ и $r_{3.1.0}$ формула выполняется, при этом найденное решение является минимальным по числу пакетов. На практике задачи выполнимости булевых формул, таких как формула (5), решаются при помощи SAT-решателей.

8.2.2. Упражнения

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

Задача 1. Решите задачу разрешения зависимостей для пакета xcite:

Задача 2. Решите задачу разрешения зависимостей для пакета ruby.erubis:

Задача 3. Решите задачу разрешения зависимостей для пакета libcgicc.dev:

Задача 4. Решите задачу разрешения зависимостей для пакета Sysvinit:

Задача 5. Решите задачу разрешения зависимостей для пакета scim-unikey:

Keyboard shortcuts

Конфигурационное управление. Курс в РТУ МИРЭА