Я Хаскелл Git
Перевод статьи - I Haskell a Git
Автор(ы) - Vaibhav Sagar
Источник оригинальной статьи:
Опубликовано 13 августа 2017 г.
Я долго боролся с Git, и каждый раз, когда мне казалось, что я наконец-то это понял, я случайно удалял хранилище или портил отделение, что заставляло меня сомневаться в том, что я делаю. Мне было очень трудно сформировать ментальную модель инструмента из-за распространения, казалось бы, бесконечных флагов командной строки, которые мне приходилось использовать для достижения чего-либо значащего, и загадочных ошибок, которые неизбежно приводили бы.
Когда я, наконец, подумал, что понял, что происходит, я предложил рассказать об этом местной функциональной группе, потому что Git функционален, верно? Со-организаторы объяснили, что это не будет интересным или полезным докладом, но разговор о внедрении Git в Хаскелл будет очень приветствовался бы.
Этого было достаточно, чтобы начать работать над библиотекой Git, и оказалось, что понять Git изнутри намного проще, чем то, что я пытался сделать ранее. Этот блог пост - моя попытка поделиться этим комфортом и пониманием с вами.
Я решил написать это как записную книжку IHaskell, которая доступна здесь, и я включил default.nix, чтобы упростить процесс, если у вас установлен Nix. Вы должны быть в состоянии запустить
$ $(nix-build --no-out-link)/bin/ihaskell-notebook
чтобы открыть записку Jupyter со всеми зависимостями, которым вы должны следовать.
GHCi имеет удобную функцию, вдохновленную Vim, где команда с префиксом:! запускается в оболочке, и IHaskell также поддерживает это, так что я буду активно использовать это, чтобы все было автономно.
Давайте начнем с выбора Git-репозиторию. Я выбрал соляризацию Итана Шуновера, потому что она нетривиальна, хорошо известна и последний раз обновлялась в 2011 году, поэтому я уверен, что хеши здесь не устареют.
{-# LANGUAGE OverloadedStrings #-}
-- Start with a clean slate.
:!if [ -d solarized/ ]; then rm -rf solarized; fi
:!git clone https://github.com/altercation/solarized
:!cd solarized
:!git show --format=raw -s
Клонирование в «соляризацию» ...
Cloning into 'solarized'...
commit e40cd4130e2a82f9b03ada1ca378b7701b1a9110
tree ecd0e58d6832566540a30dfd4878db518d5451d0
parent ab3c5646b41de1b6d95782371289db585ba8aa85
author Trevor Bramble 1372482098 -0700
committer Trevor Bramble 1372482214 -0700
add tmux by @seebi!
git шоу отображает последний коммит в текущей отделении, --format=raw показывает его в необработанном формате, а флаг –s подавляет вывод diff, который (как мы увидим позже) не является частью фиксации.
Первое, на что мы должны обратить внимание, это тот факт, что Git имеет два формата хранения: свободные объекты и файлы пакетов. В формате свободных объектов каждый объект Git хранится в своем собственном файле в каталоге .git/objects. В формате packfile многие объекты Git хранятся в файле в каталоге .git/objects/pack со связанным индексом пакета, чтобы сделать поиск доступным.
Незакрепленные объекты используются ниже определенного порогового размера в качестве формата на диске, а упаковочные файлы используются для оптимизации пространства и для передачи файлов по сети, поскольку передача одного большого файла требует меньших издержек, чем передача большого количества маленьких файлов. С свободными объектами легче работать, поэтому я собираюсь преобразовать файлы пакета в свободные объекты.
Если вы хотите больше узнать о пакетных файлах, мой любимый ресурс - пакетные файлы Адитья Мукерджи Unpacking Git.
-- `git unpack-objects` doesn't do any unpacking if the objects already exist in the repository
:!mv .git/objects/pack/* .
-- Stream the packfiles to `git unpack-objects`, which splits them into individual objects and stores them appropriately
:!cat *.pack | git unpack-objects
-- We don't need the packfiles any more
:!rm -rf pack-*
Хорошо, упаковочные файлы исчезли, и теперь есть только незакрепленные объекты.
git шоу является примером «фарфоровой» команды для взаимодействия с пользователями, в отличие от «сантехнической» команды, которая является более низкоуровневой и предназначена для использования Git под капотом. Последний коммит в текущей отделении известен как коммит HEAD, и мы должны иметь возможность использовать git cat-file -p, чтобы получить практически тот же вывод, что и раньше (флаг -p означает «pretty-print»).
:!git cat-file -p HEAD
tree ecd0e58d6832566540a30dfd4878db518d5451d0
parent ab3c5646b41de1b6d95782371289db585ba8aa85
author Trevor Bramble 1372482098 -0700
committer Trevor Bramble 1372482214 -0700
add tmux by @seebi!
HEAD - это файл, который находится в .git/HEAD. Давайте посмотрим на его содержание.
:!cat .git/HEAD
По сути, это символическая ссылка в тексте. refs/heads/master относится к .git/refs/heads/master. Каково его содержание?
:!cat .git/refs/heads/master
e40cd4130e2a82f9b03ada1ca378b7701b1a9110
Хорошо, больше нет указателей! Это хеш SHA1, представляющий коммит, который мы хотим. Один последний git cat-file -p…
:!git cat-file -p e40cd4130e2a82f9b03ada1ca378b7701b1a9110
tree ecd0e58d6832566540a30dfd4878db518d5451d0
parent ab3c5646b41de1b6d95782371289db585ba8aa85
author Trevor Bramble 1372482098 -0700
committer Trevor Bramble 1372482214 -0700
add tmux by @seebi!
Как и ожидалось, мы получаем тот же результат, что и раньше. На что-то другое: e40cd4130e2a82f9b03ada1ca378b7701b1a9110 - это ссылка на объект, хранящийся в .git/objects/e4/0cd4130e2a82f9b03ada1ca378b7701b1a9110. Первые два символа хэша - это имя каталога, а 38 оставшихся символов - это имя файла под этим каталогом. Стоит отметить, что все объекты хранятся в этом формате, и нет разделения между типами объектов или чем-то в этом роде.
Эта необычная структура каталогов была выбрана в качестве компромисса между количеством каталогов в .git/objects и количеством файлов в каждом из этих каталогов. Один из подходов мог бы заключаться в использовании 40-символьных имен файлов и размещении всех объектов в .git/objects. Тем не менее, некоторые файловые системы имеют операции O(n) в количестве файлов в каталоге, и работа с большими репозиториями в этом случае будет очень медленной. Другой подход состоял бы в том, чтобы использовать первый символ хэша в качестве имени каталога, что привело бы к максимум 16 каталогам в каталоге .git/objects. Git остановился на первых двух символах, что дает нам не более 256 каталогов.
Давайте подтвердим, что файл существует, а затем посмотрим на его содержимое.
:!ls .git/objects/e4/0cd4130e2a82f9b03ada1ca378b7701b1a9110
:!cat .git/objects/e4/0cd4130e2a82f9b03ada1ca378b7701b1a9110 | xxd
.git/objects/e4/0cd4130e2a82f9b03ada1ca378b7701b1a9110
00000000: 7801 958e 6d6a 0331 0c44 fbdb a750 0ed0 x...mj.1.D...P..
00000010: e22f d95a 2825 f40c b980 b452 e942 9d0d ./.Z(%.....R.B..
00000020: ae53 92db d790 5ea0 bf06 1ec3 9b59 f7d6 .S....^......Y..
00000030: b601 31d3 d3e8 6660 ab7a 43d2 4229 6229 ..1...f`.zC.B)b)
00000040: 983d 27af 1f9a a992 0a06 52cc 18d4 bb0b .='.......R.....
00000050: 773b 0f60 492b 965c 2407 b520 4517 ac14 w;.`I+.\$.. E...
00000060: 530d 9196 d927 1426 6642 c7d7 f1b9 7738 S....'.&fB....w8
00000070: 75fb 99f1 deb9 c997 c1eb 7696 fd76 9cd3 u.........v..v..
00000080: 93ca 03be ac7b 7b83 90ea 3c15 fd42 f0ec .....{{...<..B..
00000090: abf7 6ed2 f974 d8ff 1d31 e43f 8763 5518 ..n..t...1.?.cU.
000000a0: ed7a 03b9 c3f1 db4c b683 fb05 c805 4f81 .z.....L......O.
Git сжимает эти файлы с помощью zlib перед их сохранением, и нам нужно это обработать. К счастью, есть инструмент zlib-flate (часть пакета qpdf), который мы можем использовать.
:!zlib-flate -uncompress < .git/objects/e4/0cd4130e2a82f9b03ada1ca378b7701b1a9110
commit 248tree ecd0e58d6832566540a30dfd4878db518d5451d0
parent ab3c5646b41de1b6d95782371289db585ba8aa85
author Trevor Bramble 1372482098 -0700
committer Trevor Bramble 1372482214 -0700
add tmux by @seebi!
Это идентично выводу git cat-file -p, за исключением коммита 248 в начале. Это заголовок, который Git использует для различения различных типов объектов, а 248 - это длина содержимого этого конкретного коммита. Существует также нулевой байт после длины содержимого, который оболочка не отображает здесь, и это станет важным, когда мы напишем код для обработки заголовка в данный момент.
Я уже поиграл с оболочкой и хочу написать немного кода. Первое, что я хотел бы сделать, это импортировать некоторые библиотеки и определить вспомогательные функции для сжатия и распаковки. Библиотека zlib Хаскеля работает с ленивыми байтовыми строками, но в остальной части этого кода я использую строгие байтовые строки, и я не хочу продолжать конвертировать туда и обратно, поэтому я определю сжатие и декомпрессию соответственно.
import qualified Codec.Compression.Zlib as Z (compress, decompress)
import Data.ByteString.Lazy (fromStrict, toStrict)
import Data.ByteString (ByteString)
import qualified Data.ByteString as B
compress, decompress :: ByteString -> ByteString
compress = toStrict . Z.compress . fromStrict
decompress = toStrict . Z.decompress . fromStrict
Теперь, чтобы воссоздать вывод zlib-flate, полученный ранее, и продемонстрируйте наличие этого нулевого байта в заголовке:
commit <- B.readFile ".git/objects/e4/0cd4130e2a82f9b03ada1ca378b7701b1a9110"
print $ decompress commit
"commit 248\NULtree ecd0e58d6832566540a30dfd4878db518d5451d0\nparent ab3c5646b41de1b6d95782371289db585ba8aa85\nauthor Trevor Bramble 1372482098 -0700\ncommitter Trevor Bramble 1372482214 -0700\n\nadd tmux by @seebi!\n"
Далее я хочу разобраться в этом контенте, проанализировав его. Я напишу парсеры, которые берут последовательность байтов и выдают значения, с которыми я могу работать. Я также хочу определить сериализаторы (или разборщики, как мне нравится думать о них), которые принимают эти значения и возвращают их обратно в последовательность байтов, с которой мы начали.
У Хаскеля есть несколько отличных вариантов для этого, и я решил использовать attoparsec. Он работает правильно и учитывает ошибку синтаксического анализа по умолчанию, вместо того, чтобы взрываться с ошибкой во время выполнения, но я вполне уверен, что мои парсеры не потерпят неудачу, поэтому я определю вспомогательную функцию, которая избавится от этого поведения.
import Data.Attoparsec.ByteString (Parser)
import qualified Data.Attoparsec.ByteString.Char8 as AC
parsed :: Parser a -> ByteString -> a
parsed parser = either error id . AC.parseOnly parser
Давайте напишем наш первый парсер! Начнем с простого заголовка. Нам нужна некоторая последовательность символов, пробел, число и нулевой байт, и комбинаторы синтаксического анализатора делают реализацию этой простой.
parseHeader :: Parser (ByteString, Int)
parseHeader = do
objectType <- AC.takeTill AC.isSpace
AC.space
len <- AC.decimal
AC.char '\NUL'
return (objectType, len)
commit <- decompress <$> B.readFile ".git/objects/e4/0cd4130e2a82f9b03ada1ca378b7701b1a9110"
parsed parseHeader commit
("commit",248)
Следующий парсер, который я хочу, - один для ссылок. Правильный способ сделать это - найти 40 символов в диапазоне от 0 до 9 или a-f, но я ленив и собираюсь вместо этого просто взять 40 символов. Кроличья нора: напишите синтаксический анализатор, который анализирует только действительные хэши SHA1.
type Ref = ByteString
parseHexRef :: Parser Ref
parseHexRef = AC.take 40
Теперь у нас есть все меньшие парсеры, которые нам нужно соединить, чтобы проанализировать коммит. Мы хотим проанализировать дерево, любое количество родителей, автора, коммиттера и сообщение. Почему любое количество родителей? Первоначальный коммит репозитория не будет иметь родителей, а коммит слияния будет иметь как минимум двух, хотя может быть и больше (это называется слиянием осьминога).
Автор и коммиттер строки состоят из имени пользователя, его адреса электронной почты, метки времени Unix и часового пояса. Лучший синтаксический анализатор для этого будет проверять каждый из этих компонентов, но чтобы продемонстрировать, я просто собираю всю строку. Кроличья нора: напиши лучше человека + анализатор времени.
В комбинаторах синтаксических анализаторов мне действительно нравится то, что я могу написать синтаксический анализатор, форма которого имитирует содержимое, которое я пытаюсь проанализировать. Это чисто милая стилистическая причуда, но мне все равно нравится это делать.
data Commit = Commit
{ commitTree :: Ref
, commitParents :: [Ref]
, commitAuthor :: ByteString
, commitCommitter :: ByteString
, commitMessage :: ByteString
} deriving (Eq, Show)
parseCommit = do
cTree <- AC.string "tree" *> AC.space *> parseHexRef <* AC.endOfLine
cParents <- AC.many' (AC.string "parent" *> AC.space *> parseHexRef <* AC.endOfLine)
cAuthor <- AC.string "author" *> AC.space *> AC.takeTill (AC.inClass "\n") <* AC.endOfLine
cCommitter <- AC.string "committer" *> AC.space *> AC.takeTill (AC.inClass "\n") <* AC.endOfLine
AC.endOfLine
cMessage <- AC.takeByteString
return $ Commit cTree cParents cAuthor cCommitter cMessage
parsed (parseHeader *> parseCommit) commit
Commit {commitTree = "ecd0e58d6832566540a30dfd4878db518d5451d0", commitParents = ["ab3c5646b41de1b6d95782371289db585ba8aa85"], commitAuthor = "Trevor Bramble 1372482098 -0700", commitCommitter = "Trevor Bramble 1372482214 -0700", commitMessage = "add tmux by @seebi!\n"}
Теперь напишем наш первый сериализатор, который принимает значения типа Commit и превращает их обратно в строки байтов. Опять, с некоторыми возможностями форматирования я могу сделать так, чтобы контент выглядел как контент, который я хочу вывести. Я могу быстро проверить, работает ли он в обоих направлениях, чтобы убедиться, что мой парсер и сериализатор работают правильно.
import Data.Monoid ((<>), mappend, mconcat)
import Data.Byteable
instance Byteable Commit where
toBytes (Commit cTree cParents cAuthor cCommitter cMessage) = mconcat
[ "tree " <> cTree <> "\n"
, mconcat (map (\cRef -> "parent " <> cRef <> "\n") cParents)
, "author " <> cAuthor <> "\n"
, "committer " <> cCommitter <> "\n"
, "\n"
, cMessage
]
parsedCommit = parsed (parseHeader *> parseCommit) commit
(parsed parseCommit . toBytes $ parsedCommit) == parsedCommit
True
Давайте вернемся назад, а также определим сериализатор для наших заголовков.
import Data.ByteString.UTF8 (fromString, toString)
withHeader :: ByteString -> ByteString -> ByteString
withHeader oType content = mconcat [oType, " ", fromString . show $ B.length content, "\NUL", content]
withHeader "commit" (toBytes parsedCommit)
commit 248tree ecd0e58d6832566540a30dfd4878db518d5451d0
parent ab3c5646b41de1b6d95782371289db585ba8aa85
author Trevor Bramble 1372482098 -0700
committer Trevor Bramble 1372482214 -0700
add tmux by @seebi!
Отлично, похоже, это правильно делает. Мы проверим это более тщательно позже.
До сих пор я избегал вопроса о том, откуда взялись хэши. Git - это адресно-ориентированное хранилище (CAS), и содержимое наших объектов Git однозначно определяет их хэш. Это очень похоже на хеш-таблицу, и это полезный способ думать о Git: хеш-таблица в файловой системе.
Более конкретно, хэш SHA1 объекта Git перед сжатием используется в качестве ссылки. Позвольте мне продемонстрировать.
import Data.Digest.Pure.SHA
hash :: ByteString -> Ref
hash = fromString . showDigest . sha1 . fromStrict
hash (withHeader "commit" (toBytes parsedCommit))
e40cd4130e2a82f9b03ada1ca378b7701b1a9110
Это тот же хеш, который мы использовали для получения коммита, что соответствует моему объяснению.
Я думаю, что это хороший момент, чтобы упомянуть, что коммиты Git формируют направленный ациклический граф, и это свойство обеспечивается способом вычисления хэшей: поскольку хеш коммитов зависит от содержимого родительских полей, коммит с предком ссылается на него ему каким-то образом понадобится, чтобы этот предок (и, следовательно, все его преемники) знали хэш окончательного коммита до его определения. Тем не менее, поскольку SHA1 недавно был нарушен на практике, возможно, в конечном итоге будет возможно сгенерировать цикл коммита Git, и мне любопытно посмотреть, как инструмент будет вести себя в его присутствии.
Теперь, когда мы закончили с коммитами, давайте посмотрим на деревья. Дерево - это то, что Git называет списком каталогов. Я думаю, что ссылка на дерево ecd0e58d6832566540a30dfd4878db518d5451d0 в вышеприведенном коммите хороша для начала.
Объект дерева состоит из некоторого числа записей дерева, и каждая запись дерева представляет directory/file со ссылкой на другой объект Git, который хранит фактическое содержимое directory/file. Я думаю об этом как о попытках, с содержанием файла на листьях.
:!git cat-file -p ecd0e58d6832566540a30dfd4878db518d5451d0
100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 .gitmodules
100644 blob ec00a76061539cf774614788270214499696f871 CHANGELOG.mkd
100644 blob f95aaf80007d225f00d3109987ee42ef2c2e0c0a DEVELOPERS.mkd
100644 blob ee08d7e44f15108ef5359550399dad55955b56ca LICENSE
100644 blob d18ee9450251ea1b9a02ebd4d6fce022df9eb5e4 README.md
040000 tree 1981c76881c6a14e14d067a44247acd1bf6bbc3a adobe-swatches-solarized
040000 tree 825c732bdd3a62aeb543ca89026a26a2ee0fba26 apple-colorpalette-solarized
040000 tree 7bab2828df5de23262a821cc48fe0ccf8bd2a9ae emacs-colors-solarized
040000 tree f5fe8c3e20b2577223f617683a52eac31c5c9f30 files
040000 tree 5b60111510dbb3d8560cf58a36a20a99fc175658 gedit
040000 tree 60c9df3d6e1994b76d72c061a02639af3d925655 gimp-palette-solarized
040000 tree 979cf43752e4d698c7b5b47cff665142a274c133 img
040000 tree 3ff6d431303b66cc50e45b6fabd72302f210aebc intellij-colors-solarized
040000 tree 8f387a531ad08f146c86e4b6007b898064ad4d7f iterm2-colors-solarized
040000 tree 1e37592e62c85909be4c5e5eb774f177766e8422 mutt-colors-solarized
040000 tree 8f321f917040d903f701a2b33aeee26aed2ee544 netbeans-colors-solarized
040000 tree 0d408465820822f6a2afccf43e9627375fedc278 osx-terminal.app-colors-solarized
040000 tree 63dfa6c40d214f8e0f76d39f7a2283e053940a19 putty-colors-solarized
040000 tree 453921a267d3eb855e40c7de73aee46088563f3e qtcreator
040000 tree 5dd6832a324187f8f521bef928891fb87cf845f6 seestyle-colors-solarized
040000 tree 3c15973ed107e7b37d1c4885f82984658ecbdf6a textmate-colors-solarized
040000 tree 4db152b36a47e31a872e778c02161f537888e44b textwrangler-bbedit-colors-solarized
040000 tree 09b5f2f69e1596c6ff66fb187ea6bdc385845152 tmux
040000 tree 635ebbb919fcbbaf6fe958998553bf3f5fe09210 utils
040000 tree b87a2100b0a79424cd4b2a4e4ef03274b130a206 vim-colors-solarized
040000 tree 8dea7190b79c05404aa6a1f0d67c5c6671d66fe1 visualstudio-colors-solarized
040000 tree 0a531826e913a4b11823ee1be6e1b367f826006f xchat
040000 tree 2870bdf394a6b6b3bd10c263ffe9396a0d3d3366 xfce4-terminal
040000 tree 5d1a212e2fd9cdc2b678e3be56cf776b2f16cfe2 xresources
Число в начале каждой записи представляет разрешения на запись и является подмножеством прав доступа к файлу Unix. 100644 соответствует blob-объекту, который является объектом Git, соответствующим файлу, а 040000 соответствует дереву. Другие числа существуют, но они редки. Остальная часть записи дерева - это ссылка на запись и имя записи.
Как и раньше, мы должны быть в состоянии распаковать файл и получить по существу тот же вывод, что и раньше, верно?
tree <- decompress <$> B.readFile ".git/objects/ec/d0e58d6832566540a30dfd4878db518d5451d0"
print tree
"tree 1282\NUL100644 .gitmodules\NUL\230\157\226\155\178\209\214CK\139)\174wZ\216\194\228\140S\145\&100644 CHANGELOG.mkd\NUL\236\NUL\167`aS\156\247taG\136'\STX\DC4I\150\150\248q100644 DEVELOPERS.mkd\NUL\249Z\175\128\NUL}\"_\NUL\211\DLE\153\135\238B\239,.\f\n100644 LICENSE\NUL\238\b\215\228O\NAK\DLE\142\245\&5\149P9\157\173U\149[V\202\&100644 README.md\NUL\209\142\233E\STXQ\234\ESC\154\STX\235\212\214\252\224\"\223\158\181\228\&40000 adobe-swatches-solarized\NUL\EM\129\199h\129\198\161N\DC4\208g\164BG\172\209\191k\188:40000 apple-colorpalette-solarized\NUL\130\\s+\221:b\174\181C\202\137\STXj&\162\238\SI\186&40000 emacs-colors-solarized\NUL{\171((\223]\226\&2b\168!\204H\254\f\207\139\210\169\174\&40000 files\NUL\245\254\140> \178Wr#\246\ETBh:R\234\195\FS\\\159\&040000 gedit\NUL[`\DC1\NAK\DLE\219\179\216V\f\245\138\&6\162\n\153\252\ETBVX40000 gimp-palette-solarized\NUL`\201\223=n\EM\148\183mr\192a\160&9\175=\146VU40000 img\NUL\151\156\244\&7R\228\214\152\199\181\180|\255fQB\162t\193\&340000 intellij-colors-solarized\NUL?\246\212\&10;f\204P\228[o\171\215#\STX\242\DLE\174\188\&40000 iterm2-colors-solarized\NUL\143\&8zS\SUB\208\143\DC4l\134\228\182\NUL{\137\128d\173M\DEL40000 mutt-colors-solarized\NUL\RS7Y.b\200Y\t\190L^^\183t\241wvn\132\"40000 netbeans-colors-solarized\NUL\143\&2\US\145p@\217\ETX\247\SOH\162\179:\238\226j\237.\229D40000 osx-terminal.app-colors-solarized\NUL\r@\132e\130\b\"\246\162\175\204\244>\150'7_\237\194x40000 putty-colors-solarized\NULc\223\166\196\r!O\142\SIv\211\159z\"\131\224S\148\n\EM40000 qtcreator\NULE9!\162g\211\235\133^@\199\222s\174\228`\136V?>40000 seestyle-colors-solarized\NUL]\214\131*2A\135\248\245!\190\249(\137\US\184|\248E\246\&40000 textmate-colors-solarized\NUL<\NAK\151>\209\a\231\179}\FSH\133\248)\132e\142\203\223j40000 textwrangler-bbedit-colors-solarized\NULM\177R\179jG\227\SUB\135.w\140\STX\SYN\USSx\136\228K40000 tmux\NUL\t\181\242\246\158\NAK\150\198\255f\251\CAN~\166\189\195\133\132QR40000 utils\NULc^\187\185\EM\252\187\175o\233X\153\133S\191?_\224\146\DLE40000 vim-colors-solarized\NUL\184z!\NUL\176\167\148$\205K*NN\240\&2t\177\&0\162\ACK40000 visualstudio-colors-solarized\NUL\141\234q\144\183\156\ENQ@J\166\161\240\214|\\fq\214o\225\&40000 xchat\NUL\nS\CAN&\233\DC3\164\177\CAN#\238\ESC\230\225\179g\248&\NULo40000 xfce4-terminal\NUL(p\189\243\148\166\182\179\189\DLE\194c\255\233\&9j\r=3f40000 xresources\NUL]\SUB!./\217\205\194\182x\227\190V\207wk/\SYN\207\226"
Хотя это очень похоже на тарабарщину, это то же содержание, что и выше, с одним большим отличием: вместо 40-байтового шестнадцатеричного представления хеша SHA1 используется 20-байтовое представление. Заголовок дерева присутствует, как и разрешение на вход. Каждое имя записи сопровождается \NUL для облегчения анализа.
Теперь мы можем определить синтаксический анализатор для объектов дерева. Кроличья нора: записи дерева должны быть отсортированы в определенном причудливом порядке, и мы хотели бы запретить дубликаты. Для этого используйте другую структуру данных и определения Ord вручную.
import Data.ByteString.Base16 (encode)
parseBinRef :: Parser Ref
parseBinRef = encode <$> AC.take 20
data Tree = Tree { treeEntries :: [TreeEntry] } deriving (Eq, Show)
data TreeEntry = TreeEntry
{ treeEntryPerms :: ByteString
, treeEntryName :: ByteString
, treeEntryRef :: Ref
} deriving (Eq, Show)
parseTreeEntry :: Parser TreeEntry
parseTreeEntry = do
perms <- fromString <$> AC.many1' AC.digit
AC.space
name <- AC.takeWhile (/='\NUL')
AC.char '\NUL'
ref <- parseBinRef
return $ TreeEntry perms name ref
parseTree :: Parser Tree
parseTree = Tree <$> AC.many' parseTreeEntry
parsedTree = parsed (parseHeader *> parseTree) tree
parsedTree
Tree {treeEntries = [TreeEntry {treeEntryPerms = "100644", treeEntryName = ".gitmodules", treeEntryRef = "e69de29bb2d1d6434b8b29ae775ad8c2e48c5391"},TreeEntry {treeEntryPerms = "100644", treeEntryName = "CHANGELOG.mkd", treeEntryRef = "ec00a76061539cf774614788270214499696f871"},TreeEntry {treeEntryPerms = "100644", treeEntryName = "DEVELOPERS.mkd", treeEntryRef = "f95aaf80007d225f00d3109987ee42ef2c2e0c0a"},TreeEntry {treeEntryPerms = "100644", treeEntryName = "LICENSE", treeEntryRef = "ee08d7e44f15108ef5359550399dad55955b56ca"},TreeEntry {treeEntryPerms = "100644", treeEntryName = "README.md", treeEntryRef = "d18ee9450251ea1b9a02ebd4d6fce022df9eb5e4"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "adobe-swatches-solarized", treeEntryRef = "1981c76881c6a14e14d067a44247acd1bf6bbc3a"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "apple-colorpalette-solarized", treeEntryRef = "825c732bdd3a62aeb543ca89026a26a2ee0fba26"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "emacs-colors-solarized", treeEntryRef = "7bab2828df5de23262a821cc48fe0ccf8bd2a9ae"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "files", treeEntryRef = "f5fe8c3e20b2577223f617683a52eac31c5c9f30"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "gedit", treeEntryRef = "5b60111510dbb3d8560cf58a36a20a99fc175658"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "gimp-palette-solarized", treeEntryRef = "60c9df3d6e1994b76d72c061a02639af3d925655"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "img", treeEntryRef = "979cf43752e4d698c7b5b47cff665142a274c133"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "intellij-colors-solarized", treeEntryRef = "3ff6d431303b66cc50e45b6fabd72302f210aebc"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "iterm2-colors-solarized", treeEntryRef = "8f387a531ad08f146c86e4b6007b898064ad4d7f"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "mutt-colors-solarized", treeEntryRef = "1e37592e62c85909be4c5e5eb774f177766e8422"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "netbeans-colors-solarized", treeEntryRef = "8f321f917040d903f701a2b33aeee26aed2ee544"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "osx-terminal.app-colors-solarized", treeEntryRef = "0d408465820822f6a2afccf43e9627375fedc278"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "putty-colors-solarized", treeEntryRef = "63dfa6c40d214f8e0f76d39f7a2283e053940a19"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "qtcreator", treeEntryRef = "453921a267d3eb855e40c7de73aee46088563f3e"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "seestyle-colors-solarized", treeEntryRef = "5dd6832a324187f8f521bef928891fb87cf845f6"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "textmate-colors-solarized", treeEntryRef = "3c15973ed107e7b37d1c4885f82984658ecbdf6a"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "textwrangler-bbedit-colors-solarized", treeEntryRef = "4db152b36a47e31a872e778c02161f537888e44b"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "tmux", treeEntryRef = "09b5f2f69e1596c6ff66fb187ea6bdc385845152"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "utils", treeEntryRef = "635ebbb919fcbbaf6fe958998553bf3f5fe09210"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "vim-colors-solarized", treeEntryRef = "b87a2100b0a79424cd4b2a4e4ef03274b130a206"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "visualstudio-colors-solarized", treeEntryRef = "8dea7190b79c05404aa6a1f0d67c5c6671d66fe1"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "xchat", treeEntryRef = "0a531826e913a4b11823ee1be6e1b367f826006f"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "xfce4-terminal", treeEntryRef = "2870bdf394a6b6b3bd10c263ffe9396a0d3d3366"},TreeEntry {treeEntryPerms = "40000", treeEntryName = "xresources", treeEntryRef = "5d1a212e2fd9cdc2b678e3be56cf776b2f16cfe2"}]}
Точно так же легко определить сериализатор. Все, что нам нужно сделать, это сериализовать записи в дереве и объединить их.
import Data.ByteString.Base16 (decode)
instance Byteable TreeEntry where
toBytes (TreeEntry perms name ref) = mconcat [perms, " ", name, "\NUL", fst $ decode ref]
instance Byteable Tree where
toBytes (Tree entries) = mconcat (map toBytes entries)
(parsed parseTree . toBytes $ parsedTree) == parsedTree
True
Далее мы переходим к блоб. Я использую ссылку, связанную с CHANGELOG.mkd, потому что .gitmodules пуст, и пока ограничиваю вывод первыми десятью строками, потому что мы все равно увидим позже.
:!git cat-file -p ec00a76061539cf774614788270214499696f871 | head -n10
Solarized Changelog
===================
## Current release 1.0.0beta2
1.0.0beta2
----------
### Summary
БЛОБ – это несколько байтов с заголовком.
import qualified Data.ByteString.Char8 as BC
blob <- decompress <$> B.readFile ".git/objects/ec/00a76061539cf774614788270214499696f871"
print $ BC.unlines . take 10 . BC.lines $ blob
"blob 5549\NULSolarized Changelog\n===================\n\n## Current release 1.0.0beta2\n\n1.0.0beta2\n----------\n\n### Summary\n\n"
Разбирать блоб легко!
data Blob = Blob { blobContent :: ByteString } deriving (Eq, Show)
parseBlob :: Parser Blob
parseBlob = Blob <$> AC.takeByteString
parsedBlob = parsed (parseHeader *> parseBlob) blob
parsedBlob
Blob {blobContent = "Solarized Changelog\n===================\n\n## Current release 1.0.0beta2\n\n1.0.0beta2\n----------\n\n### Summary\n\nSwitch to the alternative red hue (final and only hue change), included a whole\nheap of new ports and updates to the existing Vim colorscheme. The list of all \ncurrently included ports, highlighted items are new, updates noted:\n\n#### Editors & IDEs\n\n* \\[UPDATED\\] **Vim**\n* \\[NEW\\] ***Emacs***\n* \\[NEW\\] ***IntelliJ IDEA***\n* \\[NEW\\] ***NetBeans***\n* \\[NEW\\] ***SeeStyle theme for Coda & SubEthaEdit***\n* \\[NEW\\] ***TextMate***\n* \\[NEW\\] ***Visual Studio***\n\n#### Terminal Emulators\n\n* \\[UPDATED\\] **iTerm2 colorschemes**\n* \\[UPDATED\\] **OS X Terminal.app colors**\n* \\[UPDATED\\] **Xresources colors**\n\n#### Other Applications\n\n* \\[UPDATED\\] **Mutt mail client colorschemes**\n\n#### Palettes\n\n* \\[UPDATED\\] **Adobe Photoshop Swatches**\n* \\[UPDATED\\] **Apple Color Picker Palette**\n* \\[UPDATED\\] **Gimp Palette**\n\n\n### Critical Changes\n\nThese changes may require you to change your configuration.\n\n* **GLOBAL : IMPROVEMENT : New red accent color value**\n Modified red from L\\*a\\*b lightness value 45 to 50 to bring it in\n line with the other accent colors and address bleed into dark background on \n some displays, as well as reducing shift of red against base03 when viewed \n with glasses (chromatic aberration). All instances of the colorscheme and \n palettes updated to new red and avalailable for use/import without further \n modification. Forks and ports should pull new changes and/or update ported \n red value accordingly. The new red:\n\n red #dc322f\n\n* **VIM : CHANGE : Default mode now 16 color**\n Default terminal mode is now ***16 colors***. Most of the users of terminal \n mode seem comfortabel and capable changing terminal colors. This is the \n preferred method of implementing Solarized in Terminal mode. If you wish to \n instead use the degraded 256 color palette, you may do so with the \n following line in your .vimrc:\n\n let g:solarized_termcolors=256\n\n You no longer need to specify \"let g:solarized_termcolors=16\" as it is now \n the default; leaving it in your .vimrc won't hurt anything, however.\n\n* **VIM : IMPROVEMENT : New Toggle Background Plugin**\n Added new Toggle Background plugin. Will load automatically and show up as \n a menu item in the `Window` menu in gui vim. Automatically maps to\n `` if available (won't clobber that mapping if you're using it).\n Also available as a command `:ToggleBG`. To manually map to\n something other than ``:\n\n To set your own mapping in your .vimrc file, simply add the following line \n to support normal, insert and visual mode usage, changing the\n \"``\" value to the key or key combination you wish to use:\n\n call togglebg#map(\"\")\n\n Note that you'll want to use a single function key or equivalent if you want \n the plugin to work in all modes (normal, insert, visual).\n\n* **VIM : IMPROVEMENT : Special & Non-text items now more visible**\n Special characters such as trailing whitespace, tabs, newlines, when \n displayed using \":set list\" can be set to one of three levels depending on \n your needs.\n\n let g:solarized_visibility = \"normal\"| \"high\" or \"low\"\n\n I'll be honest: I still prefer low visibility. I like them barely there. \n They show up in lines that are highlighted as by the cursor line, which \n works for me. If you are with me on this, put the following in your .vimrc:\n\n let g:solarized_visibility = \"low\"\n\n### Non Critical Changes\n\nThese changes should not impact your usage of the Solarized.\n\n* **PALETTES : IMPROVEMENT : Colorspace tagged and untagged versions**\n Changed default OS X color picker palatte swatches to tagged colors (sRGB) \n and included alternate palette with untagged color swatches for advanced \n users (v1.0.0beta1 had untagged as default).\n\n* **VIM : BUGFIX : Better display in Terminal.app, other emulators**\n Terminal.app and other common terminal emulators that report 8 color mode \n had display issues due to order of synt highlighting definitions and color \n values specified. These have been conformed and reordered in such a way \n that there is a more graceful degrading of the Solarized color palette on \n 8 color terminals. Infact, the experience should be almost identical to gui \n other than lack of bold typeface.\n\n* **VIM : BUGFIX : Better distinction between status bar and split windows**\n Status bar was previously too similar to the cursor line and window splits. \n This has now been changed significantly to improve the clarity of what is \n status, cursor line and window separator.\n\n* **VIM : STREAMLINED : Removed simultaneous gui/cterm definitions**\n* Refactored solarized.vim to eliminate simultaneous definition of gui and \n cterm values.\n\n* **VIM : BUGFIX : Removed italicized front in terminal mode**\n Removed default italicized font in terminal mode in the Solarized Vim\n colorscheme (many terminal emulators display Vim italics as reversed type). \n Italics still used in GUI mode by default and can still be turned off in \n both modes by setting a variable: `let g:solarized_italic=0`.\n\n1.0.0beta1\n----------\n\nFirst public release. Included:\n\n* Adobe Photoshop Swatches\n* Apple Color Picker Palette\n* Gimp Palette\n* iTerm2 colorschemes\n* Mutt mail client colorschemes\n* OS X Terminal.app colors\n* Vim Colorscheme\n* Xresources colors\n\n\n\n***\n\nMODIFIED: 2011 Apr 16\n"}
Как их сериализует.
instance Byteable Blob where
toBytes (Blob content) = content
(parsed parseBlob . toBytes $ parsedBlob) == parsedBlob
True
Наконец, мы переходим к тегам Git, которые являются способом связать имя со ссылкой. У Git есть удобная команда show-ref --tags, которую мы можем использовать для их перечисления:
:!git show-ref --tags
31ff7f5064824d2231648119feb6dfda1a3c89f5 refs/tags/v1.0.0beta1
a3037b428f29f0c032aeeeedb4758501bc32444d refs/tags/v1.0beta
Существует два типа тегов: легкие теги и аннотированные теги. Легкие теги - это просто файлы, очень похожие на refs/heads/master, содержащие ссылку, а аннотированные теги имеют сообщение, связанное с ними, например коммит. Только аннотированные теги являются объектами Git.
:!git cat-file -p 31ff7f5064824d2231648119feb6dfda1a3c89f5
object 90581c7bfbcd279768580eec595d0ab3c094cc02
type commit
tag v1.0.0beta1
tagger Ethan Schoonover 1300994142 -0700
Initial public beta release 1.0.0beta1
Хотя теги в основном используются с коммитами, можно пометить любой объект Git. Вы даже можете пометить другой тег, хотя вряд ли захотите.
tag <- decompress <$> B.readFile ".git/objects/31/ff7f5064824d2231648119feb6dfda1a3c89f5"
print tag
"tag 182\NULobject 90581c7bfbcd279768580eec595d0ab3c094cc02\ntype commit\ntag v1.0.0beta1\ntagger Ethan Schoonover 1300994142 -0700\n\nInitial public beta release 1.0.0beta1\n"
Наш парсер для них очень похож на наш парсер коммитов. Я быстро отказался от своей стратегии «написать худший из возможных парсеров», чтобы убедиться, что наши теги могут помечать только объекты типа «commit», «tree», «blob» или «tag».
data Tag = Tag
{ tagObject :: Ref
, tagType :: ByteString
, tagTag :: ByteString
, tagTagger :: ByteString
, tagAnnotation :: ByteString
} deriving (Eq, Show)
parseTag :: Parser Tag
parseTag = do
tObject <- AC.string "object" *> AC.space *> parseHexRef <* AC.endOfLine
tType <- AC.string "type" *> AC.space *> AC.choice (map AC.string ["commit", "tree", "blob", "tag"]) <* AC.endOfLine
tTag <- AC.string "tag" *> AC.space *> AC.takeTill (AC.inClass "\n") <* AC.endOfLine
tTagger <- AC.string "tagger" *> AC.space *> AC.takeTill (AC.inClass "\n") <* AC.endOfLine
AC.endOfLine
tAnnotation <- AC.takeByteString
return $ Tag tObject tType tTag tTagger tAnnotation
parsedTag = parsed (parseHeader *> parseTag) tag
parsedTag
Tag {tagObject = "90581c7bfbcd279768580eec595d0ab3c094cc02", tagType = "commit", tagTag = "v1.0.0beta1", tagTagger = "Ethan Schoonover 1300994142 -0700", tagAnnotation = "Initial public beta release 1.0.0beta1\n"}
Наш последний сериализатор следует.
instance Byteable Tag where
toBytes (Tag tObject tType tTag tTagger tAnnotation) = mconcat
[ "object " <> tObject <> "\n"
, "type " <> tType <> "\n"
, "tag " <> tTag <> "\n"
, "tagger " <> tTagger <> "\n"
, "\n"
, tAnnotation
]
(parsed parseTag . toBytes $ parsedTag) == parsedTag
True
Хорошо, теперь собери все вместе. Мы можем определить зонтичный тип GitObject и связанный с ним анализатор, сериализатор и хеш.
data GitObject
= GitCommit Commit
| GitTree Tree
| GitBlob Blob
| GitTag Tag
deriving (Eq, Show)
parseGitObject :: Parser GitObject
parseGitObject = do
headerLen <- parseHeader
case (fst headerLen) of
"commit" -> GitCommit <$> parseCommit
"tree" -> GitTree <$> parseTree
"blob" -> GitBlob <$> parseBlob
"tag" -> GitTag <$> parseTag
_ -> error "not a git object"
instance Byteable GitObject where
toBytes obj = case obj of
GitCommit c -> withHeader "commit" (toBytes c)
GitTree t -> withHeader "tree" (toBytes t)
GitBlob b -> withHeader "blob" (toBytes b)
GitTag t -> withHeader "tag" (toBytes t)
hashObject :: GitObject -> Ref
hashObject = hash . toBytes
Давайте сделаем быстрый тест, чтобы убедиться, что наши определения работают.
hashObject . parsed parseGitObject . decompress <$> B.readFile ".git/objects/31/ff7f5064824d2231648119feb6dfda1a3c89f5"
31ff7f5064824d2231648119feb6dfda1a3c89f5
Отлично, хотя нам не хватает помощника, чтобы превратить ссылку в путь к файлу объекта Git. Давайте определим это.
import System.FilePath (())
refPath :: FilePath -> Ref -> FilePath
refPath gitDir ref = let
(dir,file) = splitAt 2 (toString ref)
in gitDir "objects" dir file
refPath ".git" "31ff7f5064824d2231648119feb6dfda1a3c89f5"
".git/objects/31/ff7f5064824d2231648119feb6dfda1a3c89f5"
Теперь мы можем определить действие readObject, которое принимает ссылку и возвращает проанализированный объект Git.
readObject :: FilePath -> Ref -> IO GitObject
readObject gitDir ref = do
let path = refPath gitDir ref
content <- decompress <$> B.readFile path
return $ parsed parseGitObject content
readObject ".git" "31ff7f5064824d2231648119feb6dfda1a3c89f5"
GitTag (Tag {tagObject = "90581c7bfbcd279768580eec595d0ab3c094cc02", tagType = "commit", tagTag = "v1.0.0beta1", tagTagger = "Ethan Schoonover 1300994142 -0700", tagAnnotation = "Initial public beta release 1.0.0beta1\n"})
Затем мы определяем действие writeObject, которое принимает объект Git и сохраняет его по правильному пути, если он еще не существует. Бит «еще не существует» - это магия Git: мы можем смело предположить, что объект с таким же хешем - это тот же объект. Каждый раз, когда дерево или блоб изменяется, на диск записываются только измененные объекты, и именно так Git удается экономить место.
import System.Directory (doesPathExist, createDirectoryIfMissing)
import System.FilePath (takeDirectory)
import Control.Monad (when, unless)
writeObject :: FilePath -> GitObject -> IO Ref
writeObject gitDir object = do
let ref = hashObject object
let path = refPath gitDir ref
exists <- doesPathExist path
unless exists $ do
let dir = takeDirectory path
createDirectoryIfMissing True dir
B.writeFile path . compress $ toBytes object
return ref
Хорошо, время для финала! Мы собираемся прочитать и затем написать каждый объект в этом Git-репозитории. Если мы все реализовали правильно, количество ссылок до и после останется неизменным, и они будут одинаковыми.
import Data.Traversable (for)
import System.Directory (listDirectory)
allRefs <- do
prefixes <- filter (\d -> length d == 2) <$> listDirectory ".git/objects/"
concat <$> for prefixes (\p ->
map (fromString . (p++)) <$> listDirectory (".git/objects" p))
print $ length allRefs
test <- for allRefs $ \ref -> do
obj <- readObject ".git" ref
ref' <- writeObject ".git" obj
return $ ref == ref'
and test
allRefs' <- do
prefixes <- filter (\d -> length d == 2) <$> listDirectory ".git/objects/"
concat <$> for prefixes (\p ->
map (fromString . (p++)) <$> listDirectory (".git/objects" p))
print $ length allRefs'
allRefs == allRefs'
2186
True
2186
True
И это по сути все, что нужно Git! Я пропустил большинство дополнительных особенностей, функций и оптимизаций, но я надеюсь, что я установил, что даже с относительно небольшим количеством кода выше вы можете реализовать работающий и пригодный для использования Git API.
Вы заметите, что одна вещь, которую я вообще не упомянул, это диффузия или слияние. Это потому что Git не хранит различия! Они вычисляются на лету, когда вы их просите. Формат packfile действительно отличается от оптимизации пространства, но я думаю, что важно отметить, что вы можете получить совершенно громоздкую реализацию без них, потому что это то, что удивило меня больше всего, когда я впервые узнал об этом.
Хорошая ментальная модель Git позволила мне использовать его лучше. Я слышал, что двоичные файлы и Git плохо сочетаются друг с другом, но я только недавно понял, почему: Git хранит каждую версию каждого файла, а двоичные файлы не очень хорошо сжимаются (в отличие от текстовых файлов), поэтому они занимают огромное количество места. Я также читал о CocoaPods, вызывающей проблемы для GitHub, и теперь я знаю, что это потому, что объекты дерева, представляющие каталог Specs, были очень большими и постоянно обновлялись, что приводило к большой нагрузке на серверы GitHub.
Что еще вы можете сделать с этой силой? Вы можете…
- создать свои собственные репозитории
- запускать аналитику на своем графике коммитов, когда git log его не обрежет!
- написать веб-API для вашего хранилища!
- использовать серверную часть своего приложения и получать и объединять бесплатно!
возможности безграничны!
Если вы хотите узнать больше, вам повезло! Писать на эту тему в изобилии и очень высокого качества. Я начал с главы Git Book о Git Internals и часто ссылался на hs-git Винсента Ханкеса и чрезвычайно исчерпывающую статью Стефана Саасена, в которой реализован git для создания git-клона (!). Другие ресурсы включают отличный Мэри Роуз ГИТ изнутри и Gitlet, а также Джона Уигли GIT из Bottom Up. Если ничего другого, я надеюсь, что простого распространения Git innards письма достаточно, чтобы убедить вас, что это полезный и полезный подход к изучению этого.
Спасибо Анни Черкаев, Иан Маккой, Джасим Абид, Джейсон Шипман, Тим Хамфрис и Томислав Вильетич за комментарии, разъяснения и предложения.