Поздравляю всех с днем программиста! Желаю больше ярких "коммитов", принятых "пулл-реквестов", меньше незапланированных "мержей" и чтобы ваши ветви жизни оставались актуальными как можно дольше. В качестве идейного подарка предлагаю реализацию генеалогического древа средствами системы контроля версий Git. Ну что же… звучит как план!
Для тех, кто сразу все понял, выкладываю исходники генератора: GenealogyTreeInGit и сами генеалогические древа — мое и президентов США.
Кроме того, я реализовал простой социальный граф. Он отображает не только степень родства, но и статус отношений между потомками, отображает такие события как свадьба, развод, рождение ребенка, а также вклады в отношения тех или иных сторон.
Git
 |
Напомню, что Git — одна из самых популярных систем контроля версий. Она мощная: в ней можно фиксировать изменения (commit), создавать и сливать ветви (checkout и merge), сравнивать разные версии файлов (diff), вычислять авторов конкретных строк (blame), а также делать многие другие вещи. |
К счастью или к сожалению, Git в чем-то похож на государство-победителя: он позволяет менять историю, а именно менять даты, сообщения и авторов коммитов. Но это наоборот содействует в том, что позволяет добавлять членов семьи, как будто они авторы событий, сделанных в конкретную дату.
Начал я с простого: написал несколько команд и вуаля — фрагмент древа готов. Отлично. Теперь надо это проделать со всей армией родственников. Я с радостью напишу для них 200 строчек команд, в которых можно запутаться, а для президентов — все 10К!
Добавили меня в список идиотов? Вычеркивайте. Конечно же, я автоматизировал процесс и написал приложение для конвертации генеалогических данных в последовательность команд гита. Существуют несколько форматов таких данных, я выбрал GEDCOM.
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.
Автор: KvanTTT
