Я нахожусь в процессе написания диспетчера пакетов, и для этого я хочу, чтобы разрешение зависимости было максимально мощным.
В каждом пакете есть список версий, и каждая версия содержит следующую информацию:
- Соответствующий идентификатор
- Зависимости (список пакетов и для каждого пакета набор допустимых версий)
- Конфликты (список пакетов и для каждого пакета - набор версий, которые вызывают проблемы вместе с этой версией).
- Предоставляет (список пакетов и для каждого пакета - набор версий, которые этот пакет также содержит/содержит)
Для текущего состояния у меня есть список пакетов и их текущие версии.
Теперь я хочу, учитывая список доступных пакетов и текущего состояния, иметь возможность получать версию для каждого пакета в списке пакетов, принимая во внимание данные ограничения (зависимости, конфликтующие пакеты, пакеты, предоставляемые другими пакеты) и вернуть список версий для каждого из этих пакетов. Возможны круговые зависимости.
Если действительное состояние не может быть достигнуто, версии существующих пакетов могут быть изменены, хотя это необходимо сделать только при необходимости. Если не удастся достичь допустимого состояния, информация о причине должна быть доступна (чтобы сообщить пользователю "это может сработать, если вы удалите X" и т.д.).
Если возможно, также возможно "блокировать" пакеты для определенной версии, и в этом случае версия пакета не может быть изменена.
То, что я пытаюсь выполнить, очень похоже на то, что уже делают существующие менеджеры пакетов, с той разницей, что необязательно использовать последнюю версию пакета (предположение, которое, по-видимому, делает большинство менеджеров пакетов).
Единственная идея, которую я имею до сих пор, заключается в создании структуры всех возможных состояний для всех возможных версий рассматриваемых пакетов, а затем удаления недопустимых состояний. Я действительно надеюсь, что это не единственное решение, так как оно чувствует себя "грубой силой". Пребывание в течение нескольких секунд для ~ 500 доступных пакетов с ~ 100 версиями каждый, и ~ 150 установленных пакетов были бы хорошей целью (хотя чем быстрее, тем лучше).
Я не верю, что это вопрос, специфичный для языка, но чтобы лучше проиллюстрировать его, вот немного псевдокода:
struct Version
integer id
list<Package, set<integer>> dependencies
list<Package, set<integer>> conflicts
list<Package, set<integer>> provides
struct Package
string id
list<Version> versions
struct State
map<Package, Version> packages
map<Package, boolean> isVersionLocked
State resolve(State initialState, list<Package> availablePackages, list<Package> newPackages)
{
// do stuff here
}
(если вы должны иметь реальный код или знать о существующей реализации того, что делает это (на любом языке, предпочитаемом на С++), не стесняйтесь упоминать его в любом случае)
