1 (09.07.2017 17:45:28 отредактировано sunjob)

добрый день

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

в инете "как такового" решения не нашел, есть только теория

по понятным причинам не надо предлагать разобрать под микроскопом исходники "пакетных менеджеров" и прочих "комбайнов", в задачу не входит "написать мир с нуля" :о) (надеюсь, смысл понятен)

не обсуждается
- наш дистрибьютив
- как мы собираем пакеты (понятно, что все не так как надо и все через не то место :о)

в тек. момент "весь процесс" составляется в ручном режиме, если будут подходящие идеи/решения, то попробуем "заточить" под "свои задачи", если нет - значит "перебьемся" :о), как говориться, и на этом спасибо

непонятно то, что в инете оч. мало это обсуждают, т.к. сама по себе задача - чуть ли не главная в "процессе сборки", и эту задачу однозначно решают не "пакетные менеджеры" а "что-то", о чем "почему-то все молчать" (с другой стороны, ясен-пень: "ноу-хау" и соотв. корпоративные секрето-масштабы ...)

буду благодарен за
- волшебные пендили (в нужном направлении)
- ссылки
- идеи
- методы/решения - кто и как с "подобной задачей" справляется (ведь есть же такие спецы?!)

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

на входе
- "какое-либо" описание зависимостей, текст, или еще какой формат (типа пакет А зависит от А.1, А.2, А3, Б)
- возможно, вариации "версий" или еще какие-то "варианты" (типа пакет А совместим с А.1 - версии 1.0-1.5, и уже не совместим с версиями 0.1-0.9 и 1.6 и выше)

на выходе
- последовательность сборки пакетов (последовательная , не параллельная), типа сборка в след. посл-ти:
А.1, А.2, А3, Б, А

tag:
- топологическая сортировка
- теория графов
- алгоритм разрешения зависимостей

спасибо за помощь

### дополнение ###

подобная задача на самом деле достаточно востребована и повсеместно встречающаяся втч и с большим кол-вом элементов
типа, постройка дома, сборка самолета, да что угодно, где требуется составить последовательность работы (по исходным данным и к.л. зависимостям) ... ну вот есть же, однозначно решается как то, неужели ни кто ни где не сталкивался? ужели оскудале земля русская?

2

Можно хоть на bash распарсить зависимости из спеков и составить последовательность сборки.
Хотя ни кто, вроде, так не делает. У пакетов должны быть маинтейнеры, которые этим и занимаются.

3 (09.07.2017 13:20:04 отредактировано sunjob)

> распарсить зависимости из спеков
задача - не дистрибьютозависимая, а общая... т.е. зависимости буду браться не "откуда то из пакетозависимой среды", не важно, короче, откуда... НЕ привязываемся к конкретной платформе - есть "зависимость" и все, для понимания задачи - этого достаточно

> У пакетов должны быть маинтейнеры, которые этим и занимаются
ну типа, у пакетов то может и есть ментейнеры, это не отменяет описанной задачи, а только не лишний раз подчеркивает, что ПОСЛЕДОВАТЕЛЬНОСТЬ сборки весьма важна, я бы сказал, на первом месте - в процессе сборки :о)

повторю, НЕ привязываемся к конкретной платформе, к пакетным манагерам, и прочим струментариям... представьте, что система БЕЗ ПАКЕТНОГО МЕНЕДЖЕРА, ну нет ни чего подобного, надо решить - В ОБЩЕМ ВИДЕ...

спасибо

4

sunjob пишет:

ну нет ни чего подобного, надо решить - В ОБЩЕМ ВИДЕ...

Если бы оно в общем виде решалось, то не было бы столько разных решений.
Если имеется в виду автоматизированная сборка то можно смотреть в сторону portage или paludis, была еще одна более простая, но что то название из головы вылетело, вроде был еще дистрибутив с аналогичным названием.

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

5 (09.07.2017 17:21:32 отредактировано sunjob)

> столько разных решений.
какие решения то есть? просвятите, если не сложно?! ничего не нашел...(не считая дистро-зависимых монстров... ну это же понятно, что нам не подойдет никак)

> Как это делается в Slackware видно не вооруженным взглядом
никак там не делается, если не считать "ручной режим" установки последовательности сборки пакетов, к теме топика не имеет отношения

> Если имеется в виду автоматизированная сборка
ну не знаю как еще обьяснять! не нужна никакая АВТОМАТИЗАЦИЯ ПРОЦЕССА СБОРКИ

на входе
- "какое-либо" описание зависимостей, текст, или еще какой формат (типа пакет А зависит от А.1, А.2, А3, Б)
- возможно, вариации "версий" или еще какие-то "варианты" (типа пакет А совместим с А.1 - версии 1.0-1.5, и уже не совместим с версиями 0.1-0.9 и 1.6 и выше)
на выходе
- последовательность сборки пакетов (последовательная , не параллельная), типа сборка в след. посл-ти:
А.1, А.2, А3, Б, А

как еще обьяснить... попробуем так
- нет разницы, какие исходные данные, на выходе должен быть СПИСОК ПОСЛЕДОВАТЕЛЬНОСТИ СБОРКИ ПАКЕТОВ (учитывая все взаимозависимости)

ну... как то так :о)

6

sunjob, ругаться прекращаем, для начала просто убрал лишнее. П. 3.2.6 Правил форума не отменяли.

ᛈᚺ'ᚾᚷᛚᚢᛁ ᛗᚷᛚᚹ'ᚾᚨᚠᚺ ᚲᛏᚺᚢᛚᚺᚢ ᚱ'lᚷᛖᚺ ᚹᚷᚨᚺ'ᚾᚨᚷᛚ ᚠᚺᛏᚨᚷᚾ

Asus Prime B460M-K, i5-10500, Intel 630 UHD, DDR4 32 GB, SSD 500GB + HDD 2TB | Linux Mint 21.3 Cinnamon + Fedora 39 MATE (Compiz) + Windows 11 + macOS 12 Monterey

7 (09.07.2017 17:22:38 отредактировано sunjob)

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

8

sunjob пишет:

какие решения то есть? просвятите, если не сложно?!

Slackware уже сказал. Большинство дистрибутивов используют свои утилиты для сборки пакетов, по этому тут идет привязка к пакетному менеджеру.
Gentoo, Funtoo и подобные используют систему portage, создаются свои файлы с расширением ebuild в которых прописываются зависимости для сборки и сам процесс сборки, также прописывается сайт с которого будет браться исходник. Запустив сборку программы emerge program, сначала скачивается исходник с определенного сайта, далее будут собираться программы которые прописаны в зависимостях, а затем сама эта программа.
Вот пример ебилда скрипта что я тут в проектах описывал тыц
Подробнее тыц, это еще не полное руководство, так как разработчики постепенно меняют классы в дереве портов, в которых прописываются особенности сборки.

9 (09.07.2017 17:37:50 отредактировано sunjob)

ну это я в курсе :о)))
т.е.  в данном случае не катит...

+ открыть спойлер


какие решения то есть? просвятите, если не сложно?! ничего не нашел...(не считая дистро-зависимых монстров... ну это же понятно, что нам не подойдет никак)

ну не знаю как еще обьяснять! не нужна никакая АВТОМАТИЗАЦИЯ ПРОЦЕССА СБОРКИ

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

10

sunjob пишет:

ну это я в курсе :о)))
т.е.  в данном случае не катит...

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

Вы сами верите в то что это решаемая задача, с такими условиями?

11 (09.07.2017 18:09:15 отредактировано sunjob)

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

уточню: разруливать и задавать зависимости - пусть это останется на наших хрупких плечах... мы их сами будет задавать и прописывать...на выходе, т.е. то, что нам нужна  ЭТО "ПО СПИСКУ, ПОСЛЕДОВАТЕЛЬНОСТЬ ИЛИ В КАКОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ДОЛЖНЫ СОБИРАТЬСЯ ПАКЕТЫ"...

если так сложно понять задачу - выйдите из "данного континума пространств", представьте задачу в другом
контексте, постройка дома, сборка космического карабля, порядок одевания на мальчишник (надеюсь плавки вы будете одевать до того, как будут надеты штаны, а штаны до того, какбудет одет пиджак... ну или как то так...)

12

sunjob, читаем внимательно:

3.2.6. Запрещено использовать грубые выражения и ненормативную лексику (мат), включая замаскированный.
3.2.18. Запрещается обсуждать правила или действия куратора/модератора/администратора, кроме как в разделе «Техподдержка LinuxForum».

Так что настоятельно рекомендую свернуть эту тему.

ᛈᚺ'ᚾᚷᛚᚢᛁ ᛗᚷᛚᚹ'ᚾᚨᚠᚺ ᚲᛏᚺᚢᛚᚺᚢ ᚱ'lᚷᛖᚺ ᚹᚷᚨᚺ'ᚾᚨᚷᛚ ᚠᚺᛏᚨᚷᚾ

Asus Prime B460M-K, i5-10500, Intel 630 UHD, DDR4 32 GB, SSD 500GB + HDD 2TB | Linux Mint 21.3 Cinnamon + Fedora 39 MATE (Compiz) + Windows 11 + macOS 12 Monterey

13

А не, тут готовых решений нет.
Думаю постройка дерева зависимостей пусть уж останется на ваших хрупких плечах af

14

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

15

sunjob, а вам уже написали выше. Вы обозначили задачу: "напишите мне пакетный менеджер кроссдистрибутивный.
Плачу одной печенькой". Вот вам и говорят, что ваша задача нерешаема. Хотите программу? Приготовьтесь платить. И много.

Linux Mint 19.3 Mate Edition
Windows 7

16 (09.07.2017 21:06:35 отредактировано sunjob)

> напишите мне пакетный менеджер кроссдистрибутивный. Плачу одной печенькой
где это я такое написал?

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

в самом конце:

подобная задача на самом деле достаточно востребована и повсеместно встречающаяся втч и с большим кол-вом элементов типа, постройка дома, сборка самолета, да что угодно, где требуется составить последовательность работы (по исходным данным и к.л. зависимостям) ... ну вот есть же, однозначно решается как то, неужели ни кто ни где не сталкивался?

отсюда, как бы можно понять, что задача не упирается в конкретный дистиб, тем более в пакетный менеджер или что то еще подобное... смотрите шире... эти задачи повсеместны, любой техпроцесс так или иначе подразумевает "решение подобной задачи", просто пока число элементов небольшое - решение очевидное, когда число элементов превышает N-е кол-во, без автоматизации в той или иной степени уже не обойтись... и ЭТА задача решается везде, техпроцесс, любой завод, производство, любое предприятие маленькое большое итд... и вот подходим ... уже почти подошли к пониманию того, что ИЗЫСКИВАЕТСЯ...

данная задача как ни будь да решается да?! ну да, чего уж тут скромничать - решается!!! есть к.л. наработки, пакеты, программы, что то еще... есть - ой ну точно, есть!!!

вот и спрашивается у тех, кто с этими решениями сталкивался, пересекался, работал...

а если вы не в курсе, это не значит, что задача нерешабельна... увы, если мы/я/вы чего то не знаем, это еще ни чего не значит... ну точно то, что ДАННАЯ задача ЕСТЬ, и она решается, где то в ручном режиме, где то автоматизируется...

все имхо, можем дальше продолжать дискутировать В СУЩЬНОСТИ НИОЧЕМ а можем и помолчать и подумать, и м.б. кто ни будь кто в курсе добавит свои 5ть копеек ...

кто не в курсе, так можно и писать - я не в курсе, не пересекался, итд, а вопрос задан именно тем кто "ориентируется" :o)

p.s. большинство высказавшихся услышал, спасибо, теперь ждем "кто в курсе"

17

sunjob, есть. Называется пакетный менеджер.
Поэтому переставайте уже тупить и начинайте работу af

Linux Mint 19.3 Mate Edition
Windows 7

18 (09.07.2017 23:05:52 отредактировано sunjob)

уж лучше иногда молчать,  тем более когда это предлагают сделать, что бы не наговорить всякой ерунды...:о)

вы, видимо в этом своем видении задачи - хорошо разбираетесь, коль так живо "отвечаете"
раскажите, как вы будете решать задачу (или видите решение)? ну хотя бы по шагам, от начала, до получения списка...(надеюсь вы все правильно понимаете) - я пока ни как не вижу, ни хоть приблизительного решения, поэтому спрашиваю!

особенно, как вы будете разруливать зависимости, о которых пакетный манагер "не в зуб ногой" (ну вот не знает он такого то пакета или "прописаны" ошибочные зависимости... а такое это вообще на каждом шагу, как начинают тупить пакетники, после определенных некорректных манипуляций... об этом даже целые книги пишут, как разруливать такие "неразрешимые" вопросы) итд итд - мануально разрешать данные ситуации - не подойдет по определению, иначе зачем это все тут автоматизировать, в мануале и так все можно прекрасно сделать

но а пока, хотя бы на пальцах обьясните решение, которое вам видится:
- на входе "общий" список пакетов
- на выходе "правильный" список пакетов

если вы и это за еду предлагаете сделать, то, извините, мы на форуме а не в ресторане :о)
хотите - помогайте, за что я реально благодарен
не хотите - не надо, за что так же где-то как-то ... но ... спасибо :о)

19

Неужели  так тяжело догадаться как это реализовать?
   A  B
A 0  0
B 1  0

Если на bash реализовать, то создается отсортированный  список пакетов и обрабатывается в цикле, создается файл со списком массивов названия которых соответствуют названиям пакетов, далее в цикле прогоняется список и каждому массиву делается соответствие от каких пакетов он зависит зависимость (1) независимость (0).
Первыми собираются пакеты сумма элементов которых равна (0).
Далее вычитаются из массивов единицы соответствующие позициям собранных пакетов и т.д.

20 (09.07.2017 22:46:22 отредактировано sunjob)

> Неужели  так тяжело догадаться как это реализовать?
а то чего я тут с вами плюшки и чаем зря разбрасываюсь?!! было бы понятно, уж точно не воспрошал бы! :о)

если не сложно, поподробнее, пока не допетрил (простенькая реализация вполне возможна, не спорю)

что-то мне напомнило
ТЫЦ

21

sunjob пишет:

если не сложно, поподробнее, пока не допетрил

Подробнее, первыми собираются пакеты которые не имеют зависимостей, т.е. не зависят ни от одного пакета.
Далее собранные пакеты удаляются из списка зависимостей других пакетов и собираются следующие пакеты которые теперь тоже не имеют зависимостей, так как собранные уже пакеты из зависимостей уже удалены.
После сборки соответственно эти пакеты тоже будут удалены из зависимостей других пакетов и появятся новые пакеты не имеющие зависимостей.
Т.е. все решается гораздо проще чем выглядит, при наличии нескольких не имеющих зависимостей пакетов, можно даже организовать параллельную сборку, это довольно легко реализовать если список последовательности формируется с соответствующим разделителем, который разделяет группы таких пакетов...

22 (09.07.2017 23:02:49 отредактировано sunjob)

вот вы описали то, что мы прекрасно уже на своей "жoпe обкатали", т.е. в мануальном режиме...
это все прекрасно понятно, ровно до тех пор пока не появятся
- пересекающиеся зависимости
- множественные зависимости (прямые и обратные)

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

23 (09.07.2017 23:23:42 отредактировано ormorph)

Обратные зависимости как правило являются ошибками разработчиков, так как сборка пакетов не может зависеть от  тех пакетов которые зависят от данной сборки. Т.е.
   A B
A 0 1
B 1 0
Такого быть не должно, это является ошибкой.
Я таких ошибок насмотрелся в портах, они тоже как правило приводили к неразрешимым ситуациям при наличии определенных флагов...

24

пока обдумываю, тут еще идею подкинули...

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

25 (10.07.2017 08:19:14 отредактировано bormant)

ormorph,
ошибкой -- слишком громко сказано, скорее "обычным делом", см. бутстраппинг, сборку компилятора самим компилятором и т.п.
В пакетных системах такие связи разрывают искусственно, чтобы свести задачу к более простой и имеющей решение существующими средствами.

26

bormant пишет:

ошибкой -- слишком громко сказано, скорее "обычным делом", см. бутстраппинг, сборку компилятора самим компилятором и т.п.

Ну если присмотреться к gentoo, то становится видно что там формирование списка происходит схожим образом что я привел, далее когда уже нет пакетов у которых нет зависимостей, начинается поиск циклических зависимостей, и первая попавшаяся выводится на экран. Т.е. проблемы решаются постепенно, либо флаги меняются, либо ебилд правится, но это уже делается в ручную и не факт что после правки не вылезет еще какая нибудь в соседних пакетах. Портами определенно это воспринимается как ошибка.