Open5

Reposoup: GitリポジトリからパスIDを全て抽出する

okuokuokuoku

ちょっと悩んだけど、まぁスケーラビリティに関しては後で考えれば良いか。。

パスIDとは

パスIDは "ファイルのblameを取った際に登場する可能性のあるファイル名集合のID" である。

つまり、少くともリネームや移動に対しては 耐性 を持つ必要がある。耐性を持つとは、つまり、ファイルのリネームや移動を行っても、IDが変化しないという性質が必要となる。

ファイル分割やマージに関しては耐性は不要である 。これに対する対策は別途メタデータを設けて対策する。また、Gitは確率的に正しくファイルのリネームを検出できないことがあるので、これに関しても変化を許容することにする。

また、 IDはブランチ間で共有される 。(Gitでは重要な特徴ではないがSubversionを考慮するとこの特徴が問題になる -- SubversionでパスIDを生成するためにはブランチのrootをどこかに定める必要がある)

okuokuokuoku

GitリポジトリのIDを導出する

Subversionと異なり、GitにはリポジトリUUIDの概念が存在しない。とりあえず

sha256("git-unnamed:" + <最初のコミットのSHA>)

をIDとして使うことにする。例えば テンプレートリポジトリ のように無関係なリポジトリがinitial commitを共有するケースがあるので、たぶんGitHubのリポジトリIDとかの方が妥当だろう。

最初のコミットを求めるには git rev-list HEAD して最後の行を得る。( rev-list は辿るコミットの量を限定できるが、 git rev-list --reverse -1 HEAD では HEAD のコミットしか表示されない)

okuokuokuoku

pass1: コミット情報のダンプ

まず、1つ1つのコミットについて、どのようなファイルが出現・削除・移動されたのかの情報をダンプする。この際 コミットには単調増加する番号をアサインする 。

(マージされた pull request および リリースブランチについては後で考える)

  • repository-ids.txt -- このコミットのデータの抽出元のリポジトリID
  • primary-prev.txt -- 直前のコミットID
  • primary-next.txt -- 直後のコミットID
  • primary-revid.txt -- 単調増加するコミット番号。ここではGitHub上のpull requestによってマージされたコミットは列挙されないので無視して良く、単純にinitial commit = 1 とした番号がアサインされていくことになる。
  • creates.txt -- このリビジョンで新しく作成されたファイルのリスト
  • renames.txt -- このリビジョンでリネーム もしくは 移動されたファイルのリスト
  • deletes.txt -- このリビジョンで削除されたファイルのリスト

最初のコミット情報は git rev-list --first-parent のヒストリを対象に出力する。

ファイルリストは git -c "diff.renamelimit=9999999" diff --no-abbrev --raw HEAD^..HEAD のようにしてraw diff( https://git-scm.com/docs/git-diff#_raw_output_format )から抽出する。

okuokuokuoku

pass2: flooding

pass1で作成したコミット情報を 古 → 新 の順にスキャンしてパス"名"ID → パスID間のlookup tableを作成する。

パス"名"ID と パスID

パス名IDはローカルで一意に生成可能でなければならないので、以下のようにして生成する。

sha256(<リポジトリID> + フルパス)

パスIDは乱数で良いが、単純のためここでもSHA256で生成する。

sha256("pathid:" + <リポジトリID> + create時点のコミットID + フルパス)

Pass2.1: パスIDの生成

全ての creates.txt について、パスIDを生成して初登場コミットと元の名前を記録する。

  • repository-id.txt -- リポジトリID
  • commit.txt -- コミットID
  • name.txt -- フルパス

Pass2.2: lookup tableの作成

コミット情報を 古 → 新 の順にスキャンして、パス名IDごとに以下の情報を集積する。この処理は creates.txt 、 renames.txt と deletes.txt それぞれについて行う。

  • primary-pathids.txt -- パス名の履歴

primary-pathids.txt は以下のフォーマットでパス名IDに割り当てられたパスIDの履歴を記録する。

<開始コミットID> <TAB> <終了コミットID> <TAB> <パスID>

または

<開始コミットID> <TAB> <TAB> <パスID>

終了コミットIDが無い場合は、そのパスIDが現在も有効であることを示す。

履歴はソートされる 。各行は 古 → 新 の順に並べられることになる。

実際の処理は以下の順で行う:

  1. creates.txt にある全てのパスについて、パスIDを生成してそのIDを primary-pathids.txt に追記する (これは実際にはPass2.1と同時に行える)
  2. deletes.txt にある全てのパスについて、 primary-pathids.txt の最新のエントリに終了コミットIDを入れる
  3. renames.txt にある全てのパスについて、 primary-pathids.txt の最新エントリに終了コミットIDを入れ、更に primary-pathids.txt に追記する

renameによる上書きケース

上記の処理順は順不同ではなく、上記の通りの順で処理する必要がある。renameによってファイルが上書きされた場合を考慮すると上記の順でないと正しく処理できない。

okuokuokuoku

non-fast-forward の処理

いわゆるforce pushが発生した場合は pass2 をゼロからやりなおす必要がある。

... チートを思いつかないのでバカ正直に全部最初からやるしか無いんじゃないかな。。