Поздравляю всех с днем программиста! Желаю больше ярких "коммитов", принятых "пулл-реквестов", меньше незапланированных "мержей" и чтобы ваши ветви жизни оставались актуальными как можно дольше. В качестве идейного подарка предлагаю реализацию генеалогического древа средствами системы контроля версий Git. Ну что же... звучит как план!
Для тех, кто сразу все понял, выкладываю исходники генератора: GenealogyTreeInGit и сами генеалогические древа - мое и президентов США.
Кроме того, я реализовал простой социальный граф. Он отображает не только степень родства, но и статус отношений между потомками, отображает такие события как свадьба, развод, рождение ребенка, а также вклады в отношения тех или иных сторон.
 |
Напомню, что Git - одна из самых популярных систем контроля версий. Она мощная: в ней можно фиксировать изменения (commit), создавать и сливать ветви (checkout и merge), сравнивать разные версии файлов (diff), вычислять авторов конкретных строк (blame), а также делать многие другие вещи. |
К счастью или к сожалению, Git в чем-то похож на государство-победителя: он позволяет менять историю, а именно менять даты, сообщения и авторов коммитов. Но это наоборот содействует в том, что позволяет добавлять членов семьи, как будто они авторы событий, сделанных в конкретную дату.
Начал я с простого: написал несколько команд и вуаля - фрагмент древа готов. Отлично. Теперь надо это проделать со всей армией родственников. Я с радостью напишу для них 200 строчек команд, в которых можно запутаться, а для президентов - все 10К!
Добавили меня в список идиотов? Вычеркивайте. Конечно же, я автоматизировал процесс и написал приложение для конвертации генеалогических данных в последовательность команд гита. Существуют несколько форматов таких данных, я выбрал GEDCOM.
 |
GEDCOM - формат описания генеалогических древ. Довольно старый, но текстовый и в целом простой. Спецификация формата неплохо описана в интернете. Поддерживается чуть ли не всеми генеалогическими программами, поэтому примеров для него существует множество: древо президентов США, королевской династии, Шекспира. |
Я реализовал все это безобразие на .NET Core - он удобный и кроссплатформенный. Для парсинга и обработки GEDCOM есть несколько библиотек под C#, например GeneGenie.Gedcom, gedcomx-csharp. Я решил написать собственную на основе GedcomParser. Ну потому что она обладает фатальным недостатком... На самом деле, нет: мне захотелось самому лучше разобраться в формате и избавиться от всех зависимостей, что позволит при желании легко портировать проект на другие языки.
Настал момент обхода извлеченных личностей в удобном нам формате и генерации команд Git для них. Было решено отсортировать все события в хронологическом порядке, а затем создавать ветки, мержить и коммитить их, продвигаясь в порядке возрастания дат. К сожалению, не у всех событий есть даты, поэтому пришлось изрядно повозиться, чтобы отсортировать все события правильно. На носу 2^2^3, и я осознал, что такой подход не совсем правильный, так как при обходе в глубину с датами возиться вообще не пришлось бы. Исправлюсь позже (но это не точно).
Все, что требуется на этом этапе - инициализировать репозиторий:
mkdir Family
cd Family
git init
В этой части скрипта обходятся и коммитятся все события. Для этого использовались такие команды:
git checkout --orphan branch_namegit merge @I1@ --allow-unrelated-histories --no-commitgit commit -m "msg" --date "" --author "name <email>" --allow-empty
Первая, checkout, создает ветвь для каждой личности. Флаг --orphan позволяет
создавать ветки-сироты, т.е. ветки, не имеющие родителей. Ветка-сирота создается
один раз - при последующем переключении checkout этот параметр опускается.
В конечном итоге практически все коммиты имеют родителей, за исключением самых
дальних предков, потому что для них более ранние неизвестны.
Вторая команда, merge, объединяет родителей и создает ребенка. Будем писать в
сообщении коммита Birth - рождение с соответствующим годом. Также указываем флаги
--allow-unrelated-histories и --no-commit для возможности мержить ветки-сироты
и для того, чтобы закоммитить изменения позже. Некоторые дети являются приемными,
поэтому для них будем писать Adopted. Забавно, но Git позволяет создавать шведские
семьи, т.е. мержить одновременно несколько веток. А еще ветки не имеют пола, что
придется по душе любителям "родитель 1" и "родитель 2".
Наконец, третья команда, commit, создает коммит с сообщением -m,
датой --date и автором --author. Как уже писал, Git позволяет подменять сообщение,
автора и дату коммита. Более того, Git позволяет создавать коммиты без файлов с помощью
флага --allow-empty и без сообщений с помощью --allow-empty-message. У автора также
необходимо указывать электронную почту, но Git принимает и пустую - нужно просто
передать <>. К сожалению, Git не уважает стариков: дата коммита почему-то снизу
ограничена 1 январем 1970 года - более ранняя дата будет неправильно отображаться.
Однако все не так страшно: можно просто записывать реальную дату в
описание. Тем не менее, Git верит в будущее и принимает даты в будущем - обратите
внимание на моего сына Git. Матерей- и отцов-одиночек, кстати, тоже можно
создавать.
В социальном графе фиксируются и другие события, помимо рождения: крещение,
изменение места жительства, получение образования, женитьба, развод, смерть, похороны.
После смерти ветвь попадает в цифровой рай в ветви невозможно появление
последующих событий, разве что кроме похорон. На сервере такую
ветвь вообще можно запечатать, т. е. сделать protected branch
(не волнуйтесь: в будущем "воскресить" можно будет при необходимости).
Событие "Свадьба" имеет двух предков - супругов. А "Развод" имеет одного предка - предыдущее событие "Свадьба". Над семейной жизнью надо работать, как и над детьми, поэтому можно сказать, что после свадьбы появляется еще и новый потомок - "отношения", которые заканчиваются после развода. Ну и возобновляются опять после следующих циклов свадьба-развод. Кроме того, в отношениях могут участвовать несколько человек (слияние нескольких веток).
Добавим вишенку к торту: сделаем бекап репозитория и выгрузим всех людей на GitHub, GitLab, либо любой другой сервер, поддерживающий Git. Можно пушить все ветки одну за другой, но мы с помощью волшебной команды запушим их все, что намного быстрее и проще:
git remote add origin https://gitlab.com/KvanTTT/Family.git
git push origin --all -u
Для генерации обычного генеалогического древа нужно передавать флаг
--only-birth-events при запуске генератора. В этом случае будет создаваться
по одному коммиту на человека (рождение). В противном случае будет
генерироваться социальная сеть социальный граф.
В качестве небольшого примера, который по крайней мере везде откроется, я создал свое генеалогическое древо, а в качестве большого примера - древо президентов США (2145 человек). Они доступны в репозиториях Kochurkins и Presidents соответственно. Для создания своего я использовал сервис geni.com, откуда экспортировал древо в GEDCOM. Сгенерированный скрипт создания генеалогического репозитория доступен в Gist.
На GitHub, да и на GitLab можно перемещаться по предкам и потомкам. Это похоже
на генеалогические вики-системы Familypedia
или WeRelate. Правда, гит(х|л)абы в чем-то
более продвинуты: из них древа легко выкачиваются (с помощью команды --clone).
А главное, можно открыть сразу весь граф. (В существующих генеалогических программах
почему-то возникали сложности с открытием в полном объеме даже небольших графов.)
Причем делать это можно с помощью разных инструментов (веб-сервис, Git Extesions,
Sourcetree,
GitKraken
и других). Кроме того, эти сервисы можно использовать бесплатно, в отличие от
большинства генеалогических.
Примечательно, в гит*абах доступно даже какое-то подобие аналитики: можно узнать,
у кого самая инстаграмная жизнь насыщенная событиями жизнь. Ну или самая открытая:
на вкладке Insights отображается список людей в порядке уменьшения числа коммитов.
К сожалению, большие древа GitHub и GitLab отображают некорректно, однако хранят их правильно - можно заглянуть в репозиторий и убедиться в этом. Вот как выглядит мое дерево в веб-интерфейсе гитлаба:
Не очень ясно, как дополнять историю с корней. Пока что приходится генерировать ее полностью из GEDCOM-файла. Не исключаю, что это можно сделать с помощью хитрого rebase - можете поэкспериментировать и рассказать в комментариях. Также было бы неплохо переписать код, чтобы он работал "коммит-ориентированно", а не "событийно ориентированно", т.к. это естественней относительно гита: на самом деле, ветви в нем являются последовательностью коммитов, а не отдельными сущностями. Еще я думал, как можно привязать теги и подмодули, но пока что не знаю, как это лучше сделать.
Если расширить идею генеалогических древ дальше, на веб-сервисы для разработчиков, то с помощью issues можно заводить разные глобальные задачи и распределять их по разным вехам (milestone): детство, юность, зрелость, старость.
Помимо генеалогических древ, можно превращать другие буханки хлеба в троллейбусы
кодировать в гите генеалогические древа языков программирования
(это еще больше "по-кодерски"), синтаксические деревья и вообще любые древовидные
структуры. Гит можно освоить и домохозяйкам, чтобы выстраивать взаимосвязи между
героями бразильских сериалов :)
Практическая польза: эта разминка помогает лучше понять устройство гита, его команды, а также формат описания генеалогических деревьев GEDCOM.
Исходники самой статьи доступны на GitHub - присылайте pull request туда, если найдете ошибки или захотите дополнить контент. Для конвертации в формат habr.com используется библиотека MarkConv.