Abstract
В систему контроля версий mercurial версии 2.6 [1] был добавлен новый алгоритм сортировки closesort в команду convert, позволяющий оптимизировать расположение коммитов, в которых закрываются ветки. В отличие от алгоритма datesort, который might well increase the size of the destination repo by 10-20 times [2], closesort незначительно меняет размер репозитория. Данный алгоритм может быть интересен для workflow в которых активно ведется работа с ветвями, причем все открытые ветви закрываются.Rationale
 |
| Fig. 1 Визуальный мусор |
При активной работе с ветками рано или поздно может возникнуть ситуация, когда необходимо массово закрыть устаревшие ветви. Множество очень старых ветвей приводит к тому, что граф заполняется визуальным мусором. На Fig. 1 изображен типичный пример такой массовой чистки устаревших ветвей, на 1 живую ветвь приходится 15 мусорных.
Изменение порядка версий в большинстве случаев (сохранение хэшей между мажорными версиями mercurial не гарантируется) не будет влиять на хэши версий, поэтому такую сортировку можно периодический выполнять на центральном репозитории, при этом клиенты не заметят изменений, либо могут заново импортировать отсортированный репозиторий.
Methods
Порядок версий необходимо менять, с использованием максимально стандартного механизма, желательно с использованием внутреннего API, что избавило бы от парсинга вывода команд.
Попытка 1
Поиск готовых или похожих решений натолкнул на обсуждение [3] проблемы оптимизации чрезвычайно больших репозиториев, вылившихся в итоге в расширение shrink-revlog [4]. Данное расширение как раз занималось топологической сортировкой и достаточно было написать собственную функцию сортировки к двум имеющимся. Алгоритм был написан, при этом потребовалось прокинуть внутрь функции сортировки объект репозитория.
Но первый же запуск на реальном репозитории привел к ошибке выхода за пределы массива. Выяснилось, что в репозитории используется два файла changelog и manifest [5]. В первом хранится информация о коммитах, а во втором информация о файлах [6], при этом, если в коммите не было изменений в файлах, то появится расхождение в нумерации между этими двумя файлами. Сортировка же changelog была запрещена, поскольку это повредит репозиторий.
Попытка 2
В качестве "Плана Б" можно было встроиться в стандартное расширение convert. В нем уже присутствовали branchsort, datesort и sourcesort. Необходимый алгоритм отличался от sourcesort одним условием:
def makesourcesorter():
"""Source specific sort."""
keyfn = lambda n: self.commitcache[n].sortkey
def picknext(nodes):
return sorted(nodes, key=keyfn)[0]
return picknext
def makeclosesorter():
"""Close order sort."""
keyfn = lambda n: ('close' not in self.commitcache[n].extra,
self.commitcache[n].sortkey)
def picknext(nodes):
return sorted(nodes, key=keyfn)[0]
return picknext
И успешно решал поставленную задачу.
Pull request
Я сразу пошел в IRC разработчиков с целью обсудить данное решение, но особого интереса там не проявили и отправили в мейллист. После этого, Kevin предложил попробовать branchsort [7]. Данный алгоритм упорядочивал только самые простые случаи, но не справлялся со сложными. На IRC мне посоветовали засылать патч, раз никто не возразил. Патч был заслан и запушен Bryan [8]. В этот раз на всё-про-всё, от идеи до аппрува, ушел всего лишь месяц, а не пол года, как в прошлый раз [9].
Results
Максимальная ширина
На реальном рабочем репозитории с 5528 коммитов, максимальная ширина графа составляла 60 параллельных веток. После конвертации, ширина максимальная ширина репозитория уменьшилась до 26.
Средняя ширина
Подсчет средней ширины графа производился командой hg log -G | awk '/changeset/ {cnt++; width += (index($0,"changeset")-2)/2} END {print width / cnt}'. Данная подсчет не учитывает некоторых особых случаев, но подойдет для примерной оценки. До конвертации 21.16 и после 6.08.
Discussion
Алгоритм успешно, в разы сокращаяет ширину графа избавляя от визуального мусора. Из главных минусов можно указать то, что рассчет хэша у ревизии изменился между версиями 1.7 и 2.6, что приведет к несоответствию историй. Но, поскольку repository surgery можно проводить очень редко, это не является большой проблемой.
