Пишем свой git: минимальная реализация на Rust / Хабр

Контроль версий долгое время был для меня «чёрным ящиком»: я не понимал, как именно хранятся файлы, как формируются diff’ы и из чего состоят коммиты. А поскольку я люблю изобретать велосипеды, почему бы не попробовать реализовать git самому?

Хеширование

В основе git лежат хеши — а именно SHA-1. Когда вы коммитите файл, git вычисляет его хеш и сохраняет объект в .git/objects/. Затем, чтобы можно было снова найти этот файл, git создаёт объект tree — список файлов и поддиректорий с соответствующими хешами — хеширует его и тоже сохраняет в .git/objects/.

После этого создаётся объект commit, который содержит:

хеш дерева;
хеш предыдущего коммита;
автора;
коммитера;
сообщение коммита.

Таким образом, каждый коммит ссылается на предыдущий, образуя цепочку. Сам commit-объект тоже хешируется и сохраняется в .git/objects/.

Первой задачей было выбрать алгоритм хеширования. Git использует SHA-1 — старый и криптографически скомпрометированный алгоритм. В моём случае это не проблема: хеши нужны лишь для идентификации содержимого, а не для защиты секретов. Совместимость с git меня не интересовала, поэтому я решил использовать «новый» (с 2001 года) стандарт — SHA-256.

Сжатие объектов

Все объекты в git также сжимаются для экономии места, поэтому чтение и запись в .git/objects/ всегда сопровождаются сжатием и распаковкой. Git использует zlib, но если посмотреть на альтернативы, zstd выглядит более пер��пективно.

Поскольку совместимость с git мне не нужна, я выбрал zstd.

Название я тоже решил придумать своё — tvc, сокращение от Tony’s Version Control. Простое имя, внушающее доверие 🙂

Соответственно:

.tvc — аналог .git
.tvcignore — аналог .gitignore

Реализация

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

чтение аргументов командной строки;
чтение ignore-файла;
ls — вывод неигнорируемых файлов в рабочей директории;
хеширование файлов;
сжатие файлов;
распаковка файлов;
генерация tree-объектов;
генерация commit-объектов;
генерация файла HEAD
checkout коммитов.

Для реализации подобных сторонних проектов я почти всегда выбираю язык Rust, пусть в нём и не очень силён.

Команда ls

Команда ls оказалась довольно простой: я рекурсивно обхожу текущую директорию, пропускаю файлы и каталоги, попадающие под правила из .tvcignore, и вызываю callback для каждого файла.

match subcommand.as_str() {
    "ls" => {
        let cb = |path: &Path| {
            let hash = sha256::try_digest(&path)
                .unwrap_or("<invalid hash>".to_string());
            println!("{}\t{}", path.display(), &hash);
        };

        read_dir_recursive(Path::new("./"), &ignore_rules, &cb).unwrap();
    }
}

В callback’е я хеширую содержимое файла с помощью sha256::try_digest(&path) (не знаю, почему хеширование иногда называют digesting, но по сути это одно и то же) и вывожу путь и хеш в stdout.

Сжатие и распаковка

Сжатие и распаковка с помощью библиотеки zstd тоже оказались тривиальными:

fn decompress_object(object: &str) -> std::io::Result<String> {
    let path = PathBuf::from(format!("./.tvc/objects/{}", object));
    let object = File::open(path)?;

    let mut buf: String = String::new();
    let mut decoder = zstd::Decoder::new(object)?;
    decoder.read_to_string(&mut buf)?;
    decoder.finish();

    Ok(buf)
}

fn compress_file(source: &Path, dest: &Path) -> std::io::Result<()> {
    let input  = File::open(source)?;
    let output = File::create(dest)?;

    let mut encoder = zstd::Encoder::new(output, 3)?;
    std::io::copy(&mut &input, &mut encoder)?;
    encoder.finish()?;

    Ok(())
}

Коммиты

Чтобы создать коммит, нужно сохранить следующие свойства:

тип объекта (commit);
состояние файловой системы на момент коммита (tree);
предыдущий коммит (HEAD, если он существует);
автора;
сообщение коммита.

Git также хранит размер объекта в заголовке и различает author и committer. Поскольку в большинстве случаев это один и тот же человек, я решил не реализовывать это различие. Оно полезно для merge и rebase, но я всё равно не планировал реализовывать эти возможности.

"commit" => {
    let message = args.iter().skip(1)
        .map(|s| s.as_str())
        .collect::<Vec<_>>()
        .join(" ");
    let author = "god"; // TODO: track commit author
    let parent_hash = head;

    let tree = generate_tree(Path::new("./"), &ignore_rules).expect("tree error");
    let tree_hash = digest(tree);

    /* ===== commit format =====
    <type> \0
    tree\t<tree>\n
    parent\t<parent>\n
    author\t<author>\n
    message\t<message>\n
    */
    let commit_object = format!(
        "commit \0tree\t{}\nparent\t{}\nauthor\t{}\nmessage\t{}",
        tree_hash, parent_hash, author, message
    );

    let commit_hash = digest(&commit_object);
    let dest = PathBuf::from(format!("./.tvc/objects/{}", commit_hash));
    let dest_file = File::create(dest)?;
    let mut encoder = zstd::Encoder::new(dest_file, 3)?;

    encoder.write_all(commit_object.as_bytes())?;
    encoder.finish()?;

    // Update HEAD
    fs::write("./.tvc/HEAD", &commit_hash)?;
    println!("HEAD is now at: {}", commit_hash);
}

Вся «тяжёлая» работа здесь происходит в generate_tree(). Функция проходит по корневой директории, хеширует, сжимает и сохраняет каждый файл в .tvc/objects/, добавляя имя файла и его хеш в строку.

Поддиректории обрабатываются рекурсивно той же функцией. Получившийся tree-объект хешируется, сохраняется и включается в родительское дерево.

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

Checkout коммитов

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

После парсинга данные укладываются в структуры:

#[derive(Debug, Clone)]
struct Commit {
    tree: String,
    parent: String,
    author: String,
    message: String,
}

// Формирование структуры Commit из строки commit-объекта
impl From<String> for Commit {
    fn from(string: String) -> Self {
        ...
    }
}

#[derive(Debug, Clone)]
struct Tree {
    trees: Vec<(String, Tree)>,   // (path, Tree)
    blobs: Vec<(String, String)>, // (path, hash)
}

impl Tree {
    fn from_hash(string: &str) -> Self {
        let object = decompress_object(string).unwrap();
        Tree::from_string(object.as_str())
    }

    fn from_string(string: &str) -> Self {
        ...
    }
}

После этого можно реализовать метод, который восстанавливает файловую структуру. Чтобы случайно не затереть свой код (я тестировал всё на самом tvc), я сделал обязательный аргумент пути, куда выполнять checkout:

impl Tree {
	...
	fn generate_fs(&self, path: &Path) -> std::io::Result<()> {
		fs::create_dir(&path).unwrap_or(());

		for (dirname, blob) in &self.blobs {
			let file = decompress_object(blob)?;
			fs::write(path.join(dirname), file.as_bytes())?;
		}

		for (dirname, tree) in &self.trees {
			tree.generate_fs(&path.join(dirname))?;
		}

		Ok(())
	}
}

Итоги

Это было очень увлекательное упражнение. Оно хорошо показывает, что git по сути — это хранилище файлов, адресуемых по их содержимому: простая база «хеш → данные».

Самой сложной частью проекта оказалось не хеширование и не сжатие, а парсинг. Если бы я делал это снова, я бы, скорее всего, использовал хорошо определённый формат вроде JSON или YAML для хранения информации об ��бъектах.

Если вам интересно посмотреть код — он доступен на GitHub.

Пишем свой git: минимальная реализация на Rust