🐈

Rustで自作Git作った話

2021/03/27に公開1

簡易的な自作Gitを作ったので記事にしておこうと思います。

https://caspur.wintu.dev/front/lives/171
ここで発表したスライドに補足説明とコードを付け足したものです

Speaker Deck

https://speakerdeck.com/garebareda/zi-zuo-gitzuo-tutahua

GitHub

https://github.com/garebareDA/smallgit

自作GitのGitオブジェクトの仕様

自作Gitで使われているファイルの説明からしていきます。
Blob
Tree
Commit
の三種類のファイルが存在しています。
本家Gitはこれに加えTagが存在してます。
これらをGitオブジェクトと言います。
この三種類のファイルは拡張子なのでどれかを判別しているわけではなく、ファイルの中身で判断します。

Blob

BlobはUNIXとかで言うファイルの役割をしています。
中身は

blob {コミットするファイルのサイズ}\0{コミットするファイルの中身}

となっています。
最初にblobと書き込みこのファイルがBlobということを示します。
そしてスペースを挟んでコミットするファイルのサイズを書き込みます。
それからnull文字で区切ってコミットするファイルの中身を書き込みます。
この部分は本家Gitの仕様と一致しています。

Tree

Treeはディレクトリの役割をしています。
TreeにはBlobや階層を表すために別のTreeが書き込まれています。
中身は

tree {null文字以降のサイズ}\0
tree {Treeのハッシュ} {Treeの表すディレクトリのパス}\n
blob {Blobのハッシュ} {Blobの表すファイルのパス}\n

ハッシュに関しては後述します。
最初にtreeと書き込みこのファイルがTreeということを示します。
そしてスペースを挟んでnull文字以降のサイズを書き込みます。
それからnull文字で区切って別のTreeやBlobを書き込みます。

tree {Treeのハッシュ} {Treeの表すディレクトリのパス}\n
blob {Blobのハッシュ} {Blobの表すファイルのパス}\n

の部分はそれぞれどのGitオブジェクトかを表すために前にtreeblobを書き込んでいます。
パスの部分は後々Git管理しているファイルとディレクトリを探すのが面倒なため書き込んでいます。
Treeの仕様は本家Gitと少し違うと思います、本当はパーミッションなどを保存する必要があると思います。

Commit

Commitは名前の通りCommitの情報を書き込むためのオブジェクトです。
中身は

commit {サイズ}\0
tree {Treeのハッシュ} before {前回のCommitのハッシュ}

同じく先頭にcommitと書き込みこのファイルがCommitであることを示します。
あとは単純に最上層のTreeと前回のCommitを書き込んでいます。

ハッシュ

ハッシュはGitオブジェクトを探し出すための一意な値です。
例えばBlobなら

blob {コミットするファイルのサイズ}\0{コミットするファイルの中身

これをSHA-1でハッシュ値にしBlobやTree、Commitのファイル名を生成されたハッシュ値にします。
Treeなどに書き込むハッシュはここで生成されたハッシュを使います。

Gitオブジェクトの生成

Gitオブジェクトはzlibで圧縮してファイル名をハッシュ値にして生成します。

実装したコマンド

自作Gitに実装しているコマンドを実装した順に説明していきます。

initコマンド

とりあえず一番最初に簡単に実装できそうなinitコマンドから実装しました。
initコマンドは必要なディレクトとファイルを生成する初期化コマンドです。
initコマンドとそれにより生成されるディレクトリの説明をします。

.smallgit
	/index
	/refs
	/refs/main
	/objects

initコマンドを実行すると上のようにディレクトリとファイルが生成されます。
役割は

indexはファイルでaddしたファイルがメモされます。
refsはディレクトリでブランチのファイルが格納されます。
refs/mainはファイルでmainはブランチの名前です。ファイルの中には常に最新のCommitハッシュ書き込まれています。
/objectsはディレクトリですべてのGitオブジェクト格納されます。

ファイルとディレクトリを生成するだけなのでコードの説明はは省略します。

addコマンド

前回のコミットと見比べて更新されているファイルをステータスと一緒にindexファイルに書き込むコマンドです。
このコマンドを実行した時点でObjectsディレクトリにコミットするファイルのBlobが生成されます。
addコマンドは前回のコミットと比較する必要があるため実装順は addコマンドのindexに書き込む処理 -> commitコマンドの実装 -> addコマンドの比較処理 となっています。
コードはこんな感じになってます。

https://github.com/garebareDA/smallgit/blob/main/src/add/add_files.rs

// /src/add/add_files.rs

use super::super::common;
use super::super::common::serch_dir::SerchDir;
use super::super::tree;
use std::fs;
use std::fs::File;
use std::io::Write;
use std::path::Path;

pub fn write_index(dir: SerchDir) -> Result<(), String> {
  let index_path = Path::new("./.smallgit/index");
  if !index_path.exists() {
    return Err("index file not found".to_string());
  }
  let mut index_file = File::create(index_path).unwrap();
  let mut tree = tree::tree_git_object::CommitGet::new();
  match tree.tree_main() {
    Ok(_) => {}
    Err(e) => {
      return Err(e);
    }
  }

  for path in dir.get_paths_file().iter() {
    let content = fs::read_to_string(path).unwrap();
    let format_content = format!("blob {}\0{}", content.as_bytes().len(), content);
    let hex = common::sha1::sha1_gen(&format_content);
    let (check, status) = tree.check_blob(path, &hex);
    if !check {
      index_file
        .write(&format!("{} {} {}\n", status, path, hex).as_bytes())
        .unwrap();
    }
  }

  let remove_file = tree.check_remove_blob(&dir);
  if remove_file.is_empty() {
    return Ok(());
  }
  for remove in remove_file.iter() {
    index_file
      .write(&format!("remove {} {}\n", remove.name, remove.hash).as_bytes())
      .unwrap();
  }

  return Ok(());
}

pub fn create_objects() -> Result<(), String> {
  let objects_path = "./.smallgit/objects";
  match common::index_readed::read_index() {
    Ok(indexs) => {
      for index in indexs.iter() {
        let path = &format!("./{}", index.path);
        let add_path = Path::new(path);
        if !add_path.exists() {
          continue;
        }
        let content = fs::read_to_string(add_path).unwrap();
        let format_content = format!("blob {}\0{}", content.as_bytes().len(), content);
        match common::zlib::zlib_encoder(&format_content) {
          Ok(byte) => {
            let objects_path_format = format!("{}/{}", objects_path, index.hex);
            let mut file = File::create(objects_path_format).unwrap();
            file.write_all(&byte).unwrap();
          }
          Err(_) => return Err("zlib encode error".to_string()),
        }
      }
      common::index_readed::index_display(&indexs);
    }
    Err(_) => {
      return Err("There are no modified files".to_string());
    }
  }
  return Ok(());
}

write_index関数の説明からしていきます。

  let index_path = Path::new("./.smallgit/index");
  if !index_path.exists() {
    return Err("index file not found".to_string());
  }
  let mut index_file = File::create(index_path).unwrap();

まずindexファイルを作成して初期化します。

  let mut tree = tree::tree_git_object::CommitGet::new();
  match tree.tree_main() {
    Ok(_) => {}
    Err(e) => {
      return Err(e);
    }
  }

この部分は前回のコミットから木構造を生成しています。
この木構造を使い前回のコミットと比較してindexに削除などをステータスをメモします。
中身に関しては省略します。

  for path in dir.get_paths_file().iter() {
    let content = fs::read_to_string(path).unwrap();
    let format_content = format!("blob {}\0{}", content.as_bytes().len(), content);
    let hex = common::sha1::sha1_gen(&format_content);
    let (check, status) = tree.check_blob(path, &hex);
    if !check {
      index_file
        .write(&format!("{} {} {}\n", status, path, hex).as_bytes())
        .unwrap();
    }

ここではaddに指定されたファイルまたディレクトを一旦Blobのフォーマットに当てはめてハッシュ値にします。
そしてtree.check_blob(path, &hex);で前回のコミットのBlobとハッシュ値を比較しています。
比較してファイルが変更されている場合はchange、全く前回のコミットに無い場合はcreateとステータスがなり、indexファイルに{ステータス} {そのファイルのパス} {ハッシュ値}という形で書き込まれます。

  let remove_file = tree.check_remove_blob(&dir);
  if remove_file.is_empty() {
    return Ok(());
  }
  for remove in remove_file.iter() {
    index_file
      .write(&format!("remove {} {}\n", remove.name, remove.hash).as_bytes())
      .unwrap();
  }

ここでは前回のコミットと比較して削除されているファイルを探し出しています。
削除されているいる場合ステータスはremoveと書き込まれます。

次はcreate_objects関数の説明をします。

  let objects_path = "./.smallgit/objects";
  match common::index_readed::read_index() {
    Ok(indexs) => { ....

最初のこの部分はindexファイルからステータスなどを読み込んでいます。

      for index in indexs.iter() {
        let path = &format!("./{}", index.path);
        let add_path = Path::new(path);
        if !add_path.exists() {
          continue;
        }
        let content = fs::read_to_string(add_path).unwrap();
        let format_content = format!("blob {}\0{}", content.as_bytes().len(), content);
        match common::zlib::zlib_encoder(&format_content) {
          Ok(byte) => {
            let objects_path_format = format!("{}/{}", objects_path, index.hex);
            let mut file = File::create(objects_path_format).unwrap();
            file.write_all(&byte).unwrap();
          }
          Err(_) => return Err("zlib encode error".to_string()),
        }

そして見つからないファイルのパスは無視して、objetsディレクトリにBlobを生成しています。

commitコマンド

commitコマンドはindexに書き込まれたステータス、パス、ハッシュを元にobjectsディレクトリにTree、Commitを生成してmainブランチにCommitのハッシュを書き込むコマンドになります。
コードはこんな感じです。
https://github.com/garebareDA/smallgit/blob/main/src/commit/commit_file.rs

use super::super::tree;
use super::super::common::index_readed;
use std::fs::File;

pub struct CommitObject {
  commit_hash:String,
  pub index: Vec<index_readed::IndexReaded>,
  pub tree_dir: Vec<String>,
}

impl CommitObject {
  pub fn new() -> Self {
    Self {
      commit_hash: "".to_string(),
      index: Vec::new(),
      tree_dir: Vec::new(),
    }
  }

  pub fn commit_file(&mut self) -> Result<(), String> {
    match index_readed::read_index() {
      Ok(index) => {
        self.index = index;
      }
      Err(s) => {
        return Err(s);
      }
    }
    self.extraction_dir();
    let mut tree_root = self.generate_tree();
    let mut tree_main = tree::tree_git_object::CommitGet::new();
    match tree_main.tree_main() {
      Ok(_) => {}
      Err(e) => {
        return Err(e);
      }
    }
    self.comparsion_tree(&mut tree_root, &mut tree_main.tree);
    match self.create_tree_file(&mut tree_main.tree) {
      Ok(hash) => match self.create_commit_file(&hash) {
        Ok(()) => {
          self.commit_hash = hash;
          self.clear_index();
          return Ok(());
        }
        Err(e) => {
          return Err(e);
        }
      },
      Err(e) => {
        return Err(e);
      }
    }
  }
....

順番に説明していきます。

 pub fn commit_file(&mut self) -> Result<(), String> {
    match index_readed::read_index() {
      Ok(index) => {
        self.index = index;
      }
      Err(s) => {
        return Err(s);
      }
      self.extraction_dir();
    }

まず比較するためにindexファイルの中身を保持しています。
そしてself.extraction_dir();でindexに書き込まれているパスから使われているディレクトリだけを抽出してtree_dirに追加してこれも保持しておきます。
わざわざ保持しなくてもいいのですがなぜか保持しています。ここ実装したとき多分眠かったんじゃないかと。

    let mut tree_root = self.generate_tree();
    let mut tree_main = tree::tree_git_object::CommitGet::new();
    match tree_main.tree_main() {
      Ok(_) => {}
      Err(e) => {
        return Err(e);
      }
    }

ここはself.generate_tree()で先程保持したディレクトリなどからindexに書き込まれているものを木構造にしています。
そして前回のコミットと比較するために前回のコミットを木構造にして取得しています。

    self.comparsion_tree(&mut tree_root, &mut tree_main.tree);
    match self.create_tree_file(&mut tree_main.tree) {
      Ok(hash) => match self.create_commit_file(&hash) {
        Ok(()) => {
          self.commit_hash = hash;
          self.clear_index();
          return Ok(());
        }
        Err(e) => {
          return Err(e);
        }
      },
      Err(e) => {
        return Err(e);
      }
    }

self.comparsion_tree関数でindexから生成した木構造と前回のコミットの木構造を比較しています。
indexから生成した方は更新したファイルのみが木構造になっているのでその部分と前回の方を差し替えています。
そして self.create_tree_file関数で差し替え済みの木構造をもとにTreeを生成しています。
最後にself.create_commit_file関数でCommitを生成してindexファイルを初期化すればコミットの完了です。

statusコマンド

indexファイルをそのまま表示するだけのコマンドです。

 match common::index_readed::read_index() {
            Ok(indexs) => {
                for index in indexs {
                    println!("{} {}", index.status, index.path);
                }
            }
            Err(e) => {
                eprintln!("{}", e);
                return
            }
        }
        return;

cat-fileコマンド

ここまでで結構Gitっぽいなと思っていたのですがファイルの中身見れなきゃ意味ねぇと思い最後に実装しました。
指定されたハッシュのファイルを表示するコマンドです。

use super::super::common;
use std::fs::File;
use std::io::Read;
use std::path::Path;

pub fn display(hash: &str) -> Result<(), String> {
  let objects_path = format!("./.smallgit/objects/{}", hash);
  let path = Path::new(&objects_path);
  let mut buffer = Vec::new();
  if !path.exists() {
    return Err("git objects not found".to_string());
  }

  match File::open(path) {
    Ok(mut file) => {
      let _ = file.read_to_end(&mut buffer).unwrap();
      let inner = common::zlib::zlib_dencoder(&buffer);
      let inner_split: Vec<&str> = inner.split("\0").collect();
      let file_type_split: Vec<&str> = inner_split[0].split(" ").collect();
      let file_type = file_type_split[0];
      match file_type {
        "commit"=> {
          println!("commit object");
          println!("{}", inner_split[1]);
        }

        "tree" => {
          println!("tree object");
          println!("{}", inner_split[1]);
        }

        "blob" => {
          println!("{}", inner_split[1]);
        }
        _ => {
          return Err("git objects error".to_string());
        }
      }
      return Ok(());
    }

    Err(_) => {
      return Err("file open error".to_string());
    }
  }
}

コードは単にzlibでエンコードされているのをデコードしてGitオブジェクトを判別にして表示しているだけになります。

比較して差分とかは出せないのですがまぁ結構Gitっぽいので満足してます。

参考

https://engineering.mercari.com/blog/entry/2015-09-14-175300/
https://blog.freedom-man.com/mygit
https://git-scm.com/book/ja/v2/Gitの内側-Gitオブジェクト
http://koseki.hatenablog.com/entry/2014/04/22/inside-git-1

Discussion

eduidleduidl

こんにちは.

  match tree.tree_main() {
    Ok(_) => {}
    Err(e) => {
      return Err(e);
    }
  }

このような処理を他にもいくつかの箇所でやっていますが、?演算子を使うとより短く書けます.例えば、上のコードだと以下のように書けます(?をつかうとfromによってキャストされるので厳密には同一ではありませんが).

  tree.tree_main()?;

参考

https://doc.rust-jp.rs/book-ja/ch09-02-recoverable-errors-with-result.html#エラー委譲のショートカット-演算子

https://qiita.com/nirasan/items/321e7cc42e0e0f238254#-演算子