TypeScriptでGitを自作した話

タイトル通り、TypeScriptを使ってGitを作ってみました（mergeやrebaseといったコマンドは諦めました）
その際に参考にしたサイトや自分の実装の一部を記事にまとめておきます。Gitを作るぞ！という人の参考になればと思います。リポジトリは以下です。
https://github.com/kazuhiko-itani/typescript-git

自作した動機

• Gitの仕組みを全然知らなかったので、実際に作りながら学びたかった
• ここ1年ほど本格的なプログラミングから離れていたのでそのリハビリ

実装したコマンド

add、commit、checkout、branch、log、initなど。
実装の単純化とやる気の問題で、オプションについてはほぼ省略しています。あとmergeとrebase、pushなども実装していないので、実際にGitとして使うのは無理です。

参考にしたサイト

実装に際して、とくに参考にしたサイト、ページを以下に列挙します。手を動かしながら学びたいという人はWrite yourself a Git!がおすすめです。

• Gitのコミットの裏側で起こっていること
  • Gitの仕組みについて日本語で詳しく解説されています。図も多く、addコマンドやcommitコマンドによって何が行われているのか直感的に理解できます。
• Write yourself a Git!
  • PythonでGitを作るハンズオンです。これをやればGitの仕組みの全体像は把握できると思います。ただ、addやcommitといった花形のコマンドは解説されていないので、そこは自力で頑張る必要があります。
• Gitのステージング領域の正体を探る
  • addコマンドやcommitコマンドに深く関わっているGitのindexファイルについての解説です。
• https://github.com/git/git/blob/v2.12.0/Documentation/technical/index-format.txt
  • Gitのindexファイルのフォーマットが記述されています。addコマンドの実装時や、indexファイルのparserを書く際に必要な情報です。
• https://github.com/git/git/blob/v2.12.0/read-cache.c#L1568-L1629
  • index parserの実装です。TypeScriptでindex parserを書く際に参考しました。C言語で書かれているのでとっつきづらかったですが、実際の処理はそこまで複雑ではないので、忍耐強く読めばなんとかなります。

以下、Write yourself a Git!では解説されていないaddコマンドとcommitコマンドの実装について書きます。

addコマンドの実装

addコマンドが一体何をやっているのかについては、Gitのコミットの裏側で起こっていることを読めば理解できると思います。ざっくり言うと以下のような感じです。

1. addコマンドを実行した時点でのリポジトリ内のファイルのそれぞれについて、Git独自フォーマットのスナップショットファイル（Gitの仕組み上ではblobオブジェクトと言います）を作成
2. そのスナップショットファイルは.git/objects配下にそれぞれ配置される。ファイルパスはスナップショット情報をSHA-1に入力し、出力されたものを用いる。最初の2文字がディレクトリ名に、残りがファイル名になる
3. スナップショット情報（ファイルパスやファイルメタデータなど）の一覧を.git/indexに記述する

スナップショットファイルの中身には、対象となったファイルの中身をgzip化したものが含まれています。なのでunzipすれば元のファイル内容を復旧することができます。.git/indexはスナップショット情報の一覧ファイルなので、そこに書かれているスナップショット群を全て復元すれば、addを実行した時点のリポジトリを再現することができるという仕組みです。

addコマンドの実装は以下です。単純化のためにオプションには対応していません。コマンドを実行するリポジトリ内の全てのファイルに対してスナップショットファイルが生成されます。

const GIT_INDEX_SIGNATURE = "DIRC";
const GIT_INDEX_VERSION = 2;

export const add = (): void => {
  // リポジトリ内の各ファイルのスナップショットデータを作成
  const entries = createEntries();
  const entryBuffers: Buffer[] = [];

　　　　// .git/indexにはバイナリデータとして書き込む必要があるのでそれの準備
  entries.forEach((entry) => {
    const buffers: Buffer[] = [];

    entry.forEach((value, key) => {
      if (key === "filePath") {
        buffers.push(Buffer.from(value, "ascii"));
      } else {
        buffers.push(Buffer.from(value, "hex"));
      }
    });

    const buffer = Buffer.concat([...buffers]);
    const padding = calculatePadding(buffer.length);
    const bufferAfterPadding = Buffer.concat([
      buffer,
      Buffer.from("0".repeat(padding), "hex"),
    ]);
    entryBuffers.push(bufferAfterPadding);
  });

  // 各スナップショットデータをバイナリ化したものを結合 & ヘッダを作成し、.git/indexに書き込む
  const indexBody = Buffer.concat([...entryBuffers]);
  const indexHeader = createHeader(entries.length);
  const indexData = Buffer.concat([indexHeader, indexBody]);

  const indexFilePath = join(getGitRootPath(), "index");
  writeFileSync(indexFilePath, indexData);
};

リポジトリ内の各ファイルのスナップショットデータを作成するcreateEntries、createEntryは以下のようになっています。

// 再帰的にリポジトリ内を探索し、各ファイルのスナップショットデータを作成する
const createEntries = (
  path = getCheckoutRepoRootPath(),
  entries: GitIndexEntryDict[] = []
) => {
  const items = readdirSync(path);
  for (const item of items) {
    if (IGNORE_FILES_AND_DIRS.includes(item)) {
      continue;
    }

    const itemPath = join(path, item);
    if (lstatSync(itemPath).isDirectory()) {
      createEntries(itemPath, entries);
    } else {
      entries.push(createEntry(itemPath));
    }
  }

  return entries;
};

// スナップショットデータを作成する処理
// フォーマットはhttps://github.com/git/git/blob/v2.12.0/Documentation/technical/index-format.txtに従う（一部省略している）
const createEntry = (filePath: string) => {
  const fileMeta = lstatSync(filePath, { bigint: true });
  const dict: GitIndexEntryDict = new Map();

  // ctime
  const ctimeNanosecond = fileMeta.ctimeNs;
  dict.set(
    "ctimeSecond",
    alignLength(
      parseInt(ctimeNanosecond.toString().slice(0, 10)).toString(16),
      8
    )
  );

  // ctime nanosecond
  dict.set(
    "ctimeNanosecond",
    alignLength(parseInt(ctimeNanosecond.toString().slice(10)).toString(16), 8)
  );

  // mtime
  const mtimeNanosecond = fileMeta.mtimeNs;
  dict.set(
    "mtimeSecond",
    alignLength(
      parseInt(mtimeNanosecond.toString().slice(0, 10)).toString(16),
      8
    )
  );

  // mtime nanosecond
  dict.set(
    "mtimeNanosecond",
    alignLength(parseInt(mtimeNanosecond.toString().slice(10)).toString(16), 8)
  );

  // dev
  const dev = fileMeta.dev;
  dict.set("dev", alignLength(dev.toString(16), 8));

  // ino
  const ino = fileMeta.ino;
  dict.set("ino", alignLength(ino.toString(16), 8));

  // mode
  const mode = fileMeta.mode;
  dict.set("mode", alignLength(mode.toString(16), 8));

  // uid
  const uid = fileMeta.uid;
  dict.set("uid", alignLength(uid.toString(16), 8));

  // gid
  const gid = fileMeta.gid;
  dict.set("gid", alignLength(gid.toString(16), 8));

  // size
  const size = fileMeta.size;
  dict.set("size", alignLength(size.toString(16), 8));

  // create git object and get sha
  const sha = createBlobObject(filePath);
  dict.set("sha", sha);

  const filePathInRepo = filePath.replace(`${getCheckoutRepoRootPath()}/`, "");

  // filePathLength
  dict.set(
    "filePathLength",
    alignLength(filePathInRepo.length.toString(16), 4)
  );

  // filePath
  dict.set("filePath", filePath.replace(`${getCheckoutRepoRootPath()}/`, ""));

  return dict;
};

実装していて意外だったのが、ディレクトリはaddコマンドによるスナップショットの対象にならないことです。というのも、Gitの仕組み上ではディレクトリはtreeオブジェクトとして表現されていて、commitやcheckoutコマンドの実行時に必要になるためです。
自分の実装が間違っているのか、または見落としている情報があるのかと少し不安になっていましたが、実際にcommitコマンドを実装してみると確かに不要であることがわかりました（ただ、あったほうが実装は簡潔になる気はします）

commitコマンドの実装

.git/indexを参照すれば、ある時点のリポジトリを再現できることは先ほど説明しました。つまり、任意の時点の.git/indexを保存することができれば、いつでも任意のリポジトリを再現できます。ブランチやタグがまさにそうですが、実際にこの仕組みで実現されています。
そして任意の.git/indexを保存する仕組みがcommitです。Git上ではcommitの情報はcommitオブジェクトとして表現され、blobオブジェクトと同様に.git/objects配下に配置されます。つまり、.git/objects以下にはblobオブジェクト、commitオブジェクト（加えてtreeオブジェクト、tagオブジェクト）が混在していることになります。

commitコマンド実行時に発行されるコミットハッシュは.git/objects以下のcommitオブジェクトをそのまま指しています。なので、あるコミットハッシュを指定するということは、それはある時点の.git/indexを指すことになります。

ただ、commitオブジェクトは.git/indexをそのまま保持しているわけではありません。それどころか、一つのtreeオブジェクト（=ディレクトリ）への参照しか持っていません。
treeオブジェクトはディレクトリのスナップショットを意味し、自身が保持するファイル、ディレクトリのスナップショットへの参照（つまり、blobオブジェクトとtreeオブジェクトの情報）を持っています。
これはまさにファイルシステムにおけるディレクトリ、ファイル管理の仕組みと同様に木構造を成しているので、根さえわかれば後は再帰的にその子を探索できます。なので、commitオブジェクトが保持する情報は、プロジェクトルートのtreeオブジェクトのものがあれば十分ということになります。

つまり、commitコマンドはプロジェクトルートのtreeオブジェクトを生成する作業とも言えます。実際にはcommitオブジェクトには他の情報も含まれているので、treeオブジェクトを作って終わり！というわけではないのですが。

treeオブジェクトを作れば良いと聞くと非常にシンプルに思えるのですが、先述したように.git/indexにはディレクトリに関する情報は含まれていません。なので実装時に一工夫が必要になります。実装は以下のようになります。

type Blob = {
  mode: typeof BLOB_MODE;
  path: string;
  sha: string;
};

type Tree = {
  mode: typeof TREE_MODE;
  path: string;
  leafs: Map<string, Blob | Tree>;
};

export const commit = async (commitMessage: string): Promise<void> => {
  // .git/indexをread
  const gitIndexRaw = readFileSync(join(getGitRootPath(), "index"));
  // 内容をパース
  const gitIndex = indexParser(gitIndexRaw);
  // 中間状態としてリポジトリ構造を表した木構造を作成
  const tree = createTreeStruct(gitIndex.entries);
  // 上記のデータ構造を用いてプロジェクトルートのtreeディレクトリを作成
  const rootTreeSha = await createGitTreeObject(tree.leafs);

  // commit情報を作成
  const parentCommit = refResolve(join(getGitRootPath(), "HEAD"));
  // when first commit, parent commit is none.
  const parentCommitMessage = parentCommit ? `parent ${parentCommit}` : "";
  const author = "";

  const commitContent = `tree ${rootTreeSha}
${parentCommitMessage}
author ${author}

${commitMessage}
`;

  // commitオブジェクトのヘッダを作成
  const commitData =
    "commit" + " " + commitContent.length + "\0" + commitContent;
  // commitオブジェクトの保存先を計算
  const sha = createHash("sha1").update(commitData).digest("hex");
  const gitObjectPath = getGitObjectPathFromHash(sha);

  if (existsSync(gitObjectPath)) {
    return;
  }

  if (!existsSync(getGitObjectDirNameFromHash(sha))) {
    mkdirSync(getGitObjectDirNameFromHash(sha));
  }

  gzip(commitData, (_, buf) => {
    // 計算した保存先にcommit情報を書き込む
    writeFileSync(gitObjectPath, buf);
    // 現在のブランチの参照先を更新
    updateRef(sha);
  });

.git/indexはディレクトリに関する情報を持たないのに加えて、階層構造も持っていません。なのでそれをそのまま使うにはやや不便です。そこで、中間状態としてtrie木のようなデータ構造を定義し、treeオブジェクトとblobオブジェクトを保持することにしました。

treeオブジェクトを作成する際、該当するディレクトリが持つblobオブジェクトとtreeオブジェクトの情報が必要です。つまり、プロジェクトルートのtreeオブジェクトを作成するには、ボトムアップ的に下位のオブジェクトから順に作成していく必要があります。これは木構造を深さ優先探索の考え方で実装できます。

プロジェクトルートのtreeオブジェクト情報が作成できれば、後はヘッダをつけてcommitオブジェクトとして.git/objects配下に保存すればOKです。任意の時点のリポジトリを再現するcheckoutコマンドでは、このcommitオブジェクトをパースして、再帰的にファイル、ディレクトリを構成していけば良いということになります。

---

今回の実装ではいろいろ簡略化したのですが、それでもGitがどういった仕組みで動いているのか勉強になりました。また、バイナリ操作をする箇所も多く、それに多少慣れることができたのも良かったです。