厲害了，用 Node.js 實(shí)現(xiàn)一個(gè)簡(jiǎn)易 Git！
手把手教你理解輪子之git
大廠技術(shù) 高級(jí)前端 Node進(jìn)階
點(diǎn)擊上方 程序員成長(zhǎng)指北，關(guān)注公眾號(hào)
回復(fù)1，加入高級(jí)Node交流群
當(dāng)年他陳刀仔，能用20塊贏到 3700萬(wàn)，今天我盧.....
Sry，串臺(tái)了
當(dāng)年他linus 能用兩個(gè)星期寫完Git， 今天我葉某人.... (好吧，當(dāng)場(chǎng)給linus跪下)
前言
本文試圖理解git的原理，重寫部分git命令，從最底層的幾個(gè)命令開始，聽起來(lái)很離譜，做起來(lái)也很離譜，但是真正去做了，發(fā)現(xiàn)，誒，好像沒(méi)有那么離譜。
俗話說(shuō)得好（我也不知道哪里來(lái)的俗話，maybe 我自己說(shuō)的），理解一個(gè)東西最好的方法就是實(shí)現(xiàn)它。git作為我們每天都需要去打交道的一個(gè)東西，了解它和熟悉怎么去使用它也是我們每個(gè)人的必要技能。
現(xiàn)狀分析
來(lái)，我們克服一下恐懼，我們?yōu)槭裁磿?huì)覺(jué)得這個(gè)東西很復(fù)雜，因?yàn)樗娴暮軓?fù)雜，光是上層命令，就有各種各樣的用法，就算筆者也不敢說(shuō)真的能夠精通，關(guān)鍵是他的文檔 居然夠?qū)懸槐緯?span style="margin: 0px;padding: 3px;max-width: 100%;overflow-wrap: break-word !important;box-sizing: border-box !important;font-weight: bold;color: rgb(255, 177, 27);">【Pro Git】[1]，還有王法嗎，還有法律嗎？
不過(guò)再仔細(xì)想想，我們需要了解這么多的特性嗎，我們每天日常使用的也就是幾個(gè)命令，我們是不是只需要了解他的底層機(jī)制和那幾個(gè)命令就行了？好像沒(méi)那么可怕了？OK，我們進(jìn)入正題。
對(duì)于本文，其實(shí)你并不需要了解太多的東西，一點(diǎn)點(diǎn)的Git基本知識(shí)，一點(diǎn)點(diǎn)基本語(yǔ)言知識(shí)，一點(diǎn)點(diǎn)的shell知識(shí)，OK，條件具備了，我們可以開始愉快的玩耍了。
首先我們例舉一下，我們需要用到的本地命令有些啥
git addgit commitgit checkoutgit rmgit initgit loggit refloggit show-refgit mergegit rebasegit cat-filegit hash-objectgit ls-treegit tag
嗯，差不多，單純本地的倉(cāng)庫(kù) 我們要用到的命令是不是就這些，我們將在主要內(nèi)容分享完之后，再回到這里來(lái)理解這些命令。
GIT底層結(jié)構(gòu)
不知道大家有沒(méi)有好奇過(guò)這些東西，這些玩意都是啥？我們?nèi)绾慰窟@個(gè)目錄下的文件來(lái)管理我們各種各樣奇奇怪怪的提交，而且還能回溯呢？
GIT目錄
先來(lái)看一下目錄結(jié)構(gòu)：
├── COMMIT_EDITMSG // 上一次提交的 msg
├── FETCH_HEAD // 遠(yuǎn)端的所有分支頭指針 hash
├── HEAD // 當(dāng)前頭指針
├── ORIG_HEAD //
├── config // 記錄一些配置和遠(yuǎn)端映射
├── description // 倉(cāng)庫(kù)描述
├── hooks // commit lint規(guī)則 husky植入
│ ├── applypatch-msg
│ ├── applypatch-msg.sample
│ ├── commit-msg
│ ├── commit-msg.sample
│ ├── fsmonitor-watchman.sample
│ ├── post-applypatch
│ ├── post-checkout
│ ├── post-commit
│ ├── post-merge
│ ├── post-receive
│ ├── post-rewrite
│ ├── post-update
│ ├── post-update.sample
│ ├── pre-applypatch
│ ├── pre-applypatch.sample
│ ├── pre-auto-gc
│ ├── pre-commit
│ ├── pre-commit.sample
│ ├── pre-merge-commit
│ ├── pre-merge-commit.sample
│ ├── pre-push
│ ├── pre-push.sample
│ ├── pre-rebase
│ ├── pre-rebase.sample
│ ├── pre-receive
│ ├── pre-receive.sample
│ ├── prepare-commit-msg
│ ├── prepare-commit-msg.sample
│ ├── push-to-checkout
│ ├── push-to-checkout.sample
│ ├── sendemail-validate
│ ├── update
│ └── update.sample
├── index // 暫存區(qū)
├── info
│ ├── exclude
│ └── refs
├── logs // 顧名思義，記錄我們的git log
│ ├── HEAD
│ └── refs
├── objects // git 存儲(chǔ)的我們的文件
│
├── lost-found //一些懸空的文件
│ ├── commit
│ └── other
├── packed-refs 打包好的指針頭
└── refs // 所有的hash
├── heads
├── remotes
└── tags
對(duì)這些倉(cāng)庫(kù)分析完，突然發(fā)現(xiàn)，我們是不是只需要這一個(gè)目錄下的東西，就可以將一個(gè)repo的所有源信息拷貝。
記住我們剛剛所講的東西，這個(gè)目錄的一些結(jié)構(gòu)，這對(duì)理解我們后面的命令和底層存儲(chǔ)幫助很大，我們將在后面部分深入介紹。
GIT Hash
首先git中的對(duì)象，我們一共有4種type，分別是 commit / tree / blob / tag。
我們先需要摸清楚git算hash的規(guī)則，我們一共有四種對(duì)象type，這四個(gè)type一定是要附帶到我們sha1加密后的hash里面的，還有一些文本附加信息，整體的規(guī)則如下。
"{type} {content.length}\0{content}"
OK，那我們來(lái)嘗試下生成hash值，看看我們生成的，和git 生成的 是否一致。
echo -n "hello,world" | git hash-object --stdin
const crypto = require('crypto'),
const sha1 = crypto.createHash('sha1');
sha1.update("blob 11\0hello,world");
console.log(sha1.digest('hex'));
git 本質(zhì)是一種類kv數(shù)據(jù)庫(kù)的文件系統(tǒng)，通過(guò)sha1算法生成的hash作為key，對(duì)應(yīng)到我們的git的幾類對(duì)象，然后再去樹狀的尋址，最底層存儲(chǔ)的是我們的文件內(nèi)容。
講到這了，衍生一下關(guān)于git使用sha1的目的以及前幾年google碰撞sha1算法導(dǎo)致的 sha1算法不安全的問(wèn)題，git使用sha1進(jìn)行hash的目的，更多的是為了驗(yàn)證文件完整性 防損壞等目的，同時(shí)linus本人以及stackoverflow上對(duì)這個(gè)問(wèn)題也有一些討論和回復(fù)，大家可以移步觀看。
stackoverflow的討論[2] linus針對(duì)google sha1碰撞的郵件[3]
生成hash的算法我們介紹完事了，那接下來(lái)就是根據(jù)hash去找東西了，前文提到了，git一共存在四種對(duì)象，我們分別對(duì)四種對(duì)象以及內(nèi)容尋址進(jìn)行介紹。
GIT 對(duì)象
blob
這是最底層的對(duì)象，記錄的是文件內(nèi)容，對(duì)，僅僅是文件內(nèi)容，通過(guò)我們上面計(jì)算hash的方式可以看出來(lái)，不管文件名怎么變化，我們所對(duì)應(yīng)的那塊內(nèi)容沒(méi)有改變，hash值就不會(huì)改變，找到的永遠(yuǎn)會(huì)是那個(gè)blob。
這也是為什么 git是用來(lái)管理代碼以及各種類型的文本的一種好方式，而不是用來(lái)管理word/pdf （誤）。
在純文本類型文件管理中，git只需要保存diff就行了，而如果我們代碼中全是二進(jìn)制文件，那簡(jiǎn)直是回溯噩夢(mèng)，可能真實(shí)資源就兩個(gè)pdf，一個(gè)word文件，但是版本太多，一個(gè)git倉(cāng)庫(kù)大小幾個(gè)g也不是不可能。
OK，這里可能有些同學(xué)要問(wèn)了，那我如果真的需要存儲(chǔ)很多頻繁變動(dòng)的二進(jìn)制文件，比如多媒體資源/ psd啥的， 那我需要怎么搞？好的，家人們，上鏈接。Git LFS（Large file storage）[4]一句話介紹，把我們的大文件變成文件指針存儲(chǔ)在對(duì)象中，再去lfs拉取對(duì)應(yīng)文件。
tree
剛剛我們說(shuō)了，blob對(duì)象是純粹的內(nèi)容，有些不對(duì)勁，我們內(nèi)容需要索引，我怎么去找到他？這一節(jié)的標(biāo)題叫做 tree，對(duì)，他就是以樹狀結(jié)構(gòu)來(lái)進(jìn)行組織的，隨便點(diǎn)開一個(gè)objects下面的文件cat-file看看。
可以看出來(lái)，我們整個(gè)對(duì)象的組織形式就是一棵多叉樹。通過(guò)樹級(jí)層級(jí)一層一層尋址，最后找到我們的內(nèi)容塊。整體的組織形式就是下圖。
commit
現(xiàn)在還有另一個(gè)問(wèn)題，不過(guò)我們其實(shí)上面的演示已經(jīng)解釋了一部分這個(gè)問(wèn)題了， 一個(gè)commit對(duì)應(yīng)的信息其中只有幾種，
author與對(duì)應(yīng)的時(shí)間點(diǎn) commit的時(shí)候我們輸入的描述 這個(gè)commit所指向的tree 這個(gè)commit的parent 即父節(jié)點(diǎn)
git是以類似單向鏈表的形式將我們的一個(gè)個(gè)提交組織起來(lái)的，同時(shí)，同時(shí)一個(gè)節(jié)點(diǎn)至多有2個(gè)父節(jié)點(diǎn)。到此，其實(shí)整個(gè)git內(nèi)容存儲(chǔ)的結(jié)構(gòu)我們已經(jīng)捋清楚了。
tag
最后簡(jiǎn)單介紹下，最后一種對(duì)象，tag是對(duì)某個(gè)commit的描述，其實(shí)也是一種commit。
小結(jié)
總結(jié)一下我們以上說(shuō)的內(nèi)容，我們可以得到git的一個(gè)設(shè)計(jì)思路，git記錄的是一個(gè)a → b過(guò)程的鏈表，通過(guò)鏈表，我們可以逐步回溯到a，在此之下呢，采用了一種多叉樹形結(jié)構(gòu)對(duì)我們的hash值進(jìn)行分層記錄，最底層，通過(guò)我們的hash值進(jìn)行索引，對(duì)應(yīng)到一個(gè)個(gè)壓縮后的二進(jìn)制objects。這就是整個(gè)git的結(jié)構(gòu)設(shè)計(jì)。還有一些 git對(duì)于查找效率的優(yōu)化手段，壓縮手段。
對(duì)以上內(nèi)容了解了之后，關(guān)于我們的分支本質(zhì)上，其實(shí)也是對(duì)應(yīng)一個(gè)commit，只是多了一個(gè)ref指向這個(gè)commit而已，是不是對(duì)git整個(gè)清晰多了。
這里留給大家一個(gè)課后問(wèn)題吧，git 的 gc怎么去實(shí)現(xiàn)的， 整個(gè)完整過(guò)程是啥樣的，由于這些內(nèi)容并不是本文的核心內(nèi)容，就不在這里展開了。
實(shí)現(xiàn)
前期準(zhǔn)備
回想一下前面講的，我們需要的東西有些什么，sha1，這個(gè)可以用crypto， zlib，node中也帶了這個(gè)，可以通過(guò) require('zlib')拿到。
識(shí)別命令參數(shù)
首先，讓node環(huán)境能夠讀我們的一些命令，來(lái)干各種各樣的事情，通過(guò)process的解析，我們能夠獲得輸入的參數(shù)
enum CommandEnum{
Add= 'add',
Init = 'init',
...
}
const chooseCommand = (command:CommandEnum) => {
switch(command){
case CommandEnum.Add:
return add();
case CommandEnum.Init:
return init();
...
default:
break;
}
console.log("暫不支持此命令")
}
chooseCommand(process.argv[2] as CommandEnum);
init
okk，我們現(xiàn)在進(jìn)行下一步，萬(wàn)事開頭難，先開個(gè)頭吧。使用我們的命令，初始化一個(gè)git倉(cāng)庫(kù)。
const init = ()=>{
fs.mkdirSync('.git');
fs.mkdirSync('.git/refs')
fs.mkdirSync('.git/objects')
fs.writeFileSync('.git/HEAD','ref: refs/heads/master')
fs.writeFileSync('.git/config',`
[core]
repositoryformatversion = 0
filemode = true
bare = false
logallrefupdates = true
ignorecase = true
precomposeunicode = true
`);
fs.writeFileSync('.git/description','');
}
寫入和讀取
初始化完成了，我們有了一個(gè)存儲(chǔ)庫(kù)，接著就是把大象裝進(jìn)冰箱。
剛剛我們?cè)诜窒淼倪^(guò)程中，不斷的用到兩個(gè)命令 git hash-object 和 git cat-file，這兩個(gè)命令，在我們?nèi)粘９ぷ髦校鋵?shí)不太會(huì)用到，他們兩干嘛使的呢。Git 中存在兩個(gè)命令的概念，一個(gè)是底層命令(Plumbing) ，另一個(gè)就是我們?nèi)粘?huì)使用到的上層命令(Porcelain) ， 高層命令是基于底層命令的封裝，讓我們使用起來(lái)更為方便。
引入一些npm包，定義一些結(jié)構(gòu)體
import fs from 'fs';
import zlib from 'zlib';
import crypto from 'crypto';
export enum GitObjectType{
Commit = 'commit',
Tree = 'tree',
Blob = 'blob',
Tag = 'tag'
}
來(lái)實(shí)現(xiàn)一個(gè)簡(jiǎn)單的讀取blob對(duì)象的方法，比較簡(jiǎn)陋，還不支持對(duì)content進(jìn)行解析，我們將在后續(xù)完善。
export const readObject = (sha1='f8eb512de72634ca12328d85f70b696414473914')=>{
const data = fs.readFileSync(`.git/objects/${sha1.substring(0,2)}/${sha1.substring(2)}`);
const a = zlib.inflateSync(data).toString('utf8');
const typeIndex = a.indexOf(' ');
const lengthIndex = a.indexOf(`\0`);
const objType = a.substring(0,typeIndex);
const length = a.substring(typeIndex +1,lengthIndex);
const content = a.substring(lengthIndex+1);
// console.log(a);
return {objType,length,content};
}
ok， 有了讀之后，我們還需要往里寫。
export const createObject = (obj:GitObject)=>{
const data = obj.serialize();
const sha1 = crypto.createHash('sha1');
sha1.update(data);
const name = sha1.digest("hex");
const zipData = zlib.deflateSync(data);
console.log(name);
const dirName = `.git/objects/${name.substring(0,2)}`
fs.existsSync(dirName) && fs.mkdirSync(dirName);
fs.writeFileSync(`.git/objects/${name.substring(0,2)}/${name.substring(2)}`,zipData)
return name;
}
琢磨透了讀和寫的方法，我們的cat-file命令和hash-object命令實(shí)際上實(shí)現(xiàn)起來(lái)就很簡(jiǎn)單了，只需要調(diào)用現(xiàn)有的方法就行了。
先是cat-file 對(duì)hash 名的一個(gè)尋址，同時(shí)解壓縮對(duì)應(yīng)的objects，支持四個(gè)參數(shù)，分別返回不同的結(jié)果。我們直接讀對(duì)象就完事了嗷。
export const catFile = ()=>{
const type = process.argv[3];
const sha1 = process.argv[4];
const res = readObject(sha1);
if(type ==='-t'){
console.log(res.type);
}
if(type==='-s'){
console.log(res.length);
}
if(type === '-e'){
console.log(!!res?.type)
}
if(type === '-p'){
console.log(res.content)
}
}
接著是hash-object,這個(gè)也簡(jiǎn)單的實(shí)現(xiàn)下，就是返回對(duì)應(yīng)路徑的hash值就行了
export const hashObject = ()=>{
const path = process.argv[3];
const data = fs.readFileSync(path);
const sha1 = crypto.createHash('sha1');
sha1.update(data);
const name = sha1.digest("hex");
console.log(name);
}
現(xiàn)在我們基本結(jié)構(gòu)已經(jīng)搭起來(lái)了，需要的是commit 和tree將文件串聯(lián)起來(lái)，調(diào)用我們的cat-file試試，現(xiàn)在應(yīng)該對(duì)commit和blob的解析是正確的， 但是tree的content的解析似乎有些問(wèn)題，我們后面來(lái)看這個(gè)問(wèn)題，但是commit對(duì)象的content和 blob的content不太一樣。
內(nèi)容解析完善
剛剛我們粗略的實(shí)現(xiàn)了一下讀對(duì)象，能把內(nèi)容塊讀出來(lái)了。接著我們來(lái)完善他，以便更好的服務(wù)于我們的四種對(duì)象,先改寫下我們的readObject。
readObject
export const readObject = (sha1: string)=>{
const data = fs.readFileSync(`.git/objects/${sha1.substring(0,2)}/${sha1.substring(2)}`);
const buf = zlib.inflateSync(data)
const a = buf.toString('utf8');
const typeIndex = a.indexOf(' ');
const lengthIndex = a.indexOf(`\0`);
// console.log(a);
const objType = a.substring(0,typeIndex);
// 去掉校驗(yàn)， 其實(shí)這里需要記錄長(zhǎng)度和真實(shí)長(zhǎng)度對(duì)比是否有錯(cuò)
// const length = a.substring(typeIndex +1,lengthIndex);
let obj;
if(objType===GitObjectType.Blob){
obj = new GitBlob(a.substring(lengthIndex+1));
}
if(objType===GitObjectType.Commit){
obj = new GitCommit(a.substring(lengthIndex+1))
}
if(objType===GitObjectType.Tree){
obj = new GitTree(buf.slice(lengthIndex+1))
}
return obj;
}
Blob對(duì)象實(shí)現(xiàn)起來(lái)很簡(jiǎn)單 就不在這里說(shuō)了。
Commit對(duì)象實(shí)現(xiàn)起來(lái)稍微復(fù)雜一點(diǎn)，我們需要解析commit對(duì)象中的一些鍵值對(duì)，將他們都記住，同時(shí)把commit內(nèi)容單獨(dú)存起來(lái)。一個(gè)commit對(duì)象存儲(chǔ)的東西，在上面我們已經(jīng)介紹過(guò)了，通過(guò)一個(gè)map將他存儲(chǔ)。
Commit object
class GitCommit extends GitObject{
type = GitObjectType.Commit;
data = '';
length = 0;
content:any;
map;
constructor(data:string){
super();
if(data){
this.data=data;
this.length = data.length;
}
}
serialize = ()=>{
return `${this.type} ${this.length}\0${this.data}`;
}
deserialize= ()=>{
console.log(this.recursiveParse(this.data))
return this.data;
}
recursiveParse = (data:string,map?:any):any=>{
if(!map){
map = new Map();
}
const space = data.indexOf(' ');
const nl = data.indexOf(`\n`);
console.log(space,nl);
if(space<0 || nl<space){
map.set("content",data);
return map;
}
const key = data.substring(0,space);
let end =0;
while(true){
end = data.indexOf(`\n`,end+1)
if(data[end+1] !== ' ') break;
}
const value = data.substring(space+1,end);
if(key ==='parent'){
map.has('parent') ? map.set(key+'1',value) : map.set(key,value);
} else {
map.set(key,value)
}
const restData = data.substring(end+1);
return this.recursiveParse(restData,map);
}
}
Tree Object解析
Tree Object 相對(duì)來(lái)說(shuō)是我們解析起來(lái)最為復(fù)雜的一個(gè)對(duì)象，他不像前兩個(gè)一樣，能夠通過(guò)直接toString就能拿到正常的文本，我們直接去解析就行了。Tree Object本身其實(shí)就是一個(gè)二進(jìn)制對(duì)象，關(guān)鍵吧，他還有個(gè)誤導(dǎo)，差點(diǎn)給筆者都給帶偏了，他cat-file解析出來(lái)的文件，其實(shí)并不是他原本文件長(zhǎng)的樣子....，他做了一個(gè)格式化，且修改了順序。
class GitTree extends GitObject{
type = GitObjectType.Commit;
data:Buffer = Buffer.from('');
length = 0;
constructor(data:Buffer){
super();
if(data){
this.data=data;
this.length = data.length;
}
}
serialize = ()=>{
return `${this.type} ${this.length}\0${this.data}`;
}
parseTreeOneLine = (data:Buffer,start:number)=>{
const x = data.indexOf(' ',start);
if(x<0){
return start+21;
}
const mode = data.slice(start,x).toString('ascii');
// const type =
const y = data.indexOf(`\x00`,x)
if(y<0){return x+21};
const path = data.slice(x+1,y).toString('ascii');
const sha1 = data.slice(y+1,y+21).toString('hex');
console.log(mode,path,sha1);
return y+21;
}
deserialize= ()=>{
const buffer = this.data;
let pos = 0;
let max = buffer.length;
while(pos<max){
pos = this.parseTreeOneLine(buffer,pos);
}
return this.data;
}
}
我們的底層基礎(chǔ)簡(jiǎn)單實(shí)現(xiàn)，其實(shí)到這里就完結(jié)了，大致流程能夠串起來(lái)了。
分支和ref：
分支名和ref其實(shí)也是鍵值對(duì)，分支名作為文件名存儲(chǔ)在ref目錄下，文件內(nèi)容則是一串sha1值，這串sha1值來(lái)自于commit 頭結(jié)點(diǎn)的hash值，我們可以通過(guò)這個(gè)commit 對(duì)象回溯到當(dāng)時(shí)的場(chǎng)景。
log與reflog
單純的文本文件，記錄一些commit對(duì)象以及時(shí)間點(diǎn)等。大家可以下來(lái)再去研究研究。
暫存區(qū)：
不過(guò)大家可能會(huì)有問(wèn)題，不對(duì)啊，我們平時(shí)提交不是還有stage的概念嗎，這一塊東西呢？確實(shí)，少了這一塊，不過(guò)這一塊也是git底層相對(duì)麻煩的一部分（數(shù)據(jù)處理太多T_T)，所以我并不打算在這篇分享中去實(shí)現(xiàn)他，有興趣的同學(xué)可以參考這個(gè)鏈接 git index結(jié)構(gòu)[5]。
后語(yǔ)
分享到這就差不多了，實(shí)現(xiàn)了部分的底層讀寫api，其他的api就不一一實(shí)現(xiàn)了，有興趣可以下來(lái)實(shí)現(xiàn)。
課后作業(yè)：
git 的gc問(wèn)題 底層命令來(lái)實(shí)現(xiàn)我們?nèi)粘Ｕ{(diào)用的上層命令效果 怎么去實(shí)現(xiàn)一個(gè)遠(yuǎn)程的git中心服務(wù)器，遠(yuǎn)程的命令怎么關(guān)聯(lián)？ 補(bǔ)充實(shí)現(xiàn)一個(gè)git
最后的最后，作為linus的腦殘粉，linus的一句話，送給大家，talk is cheap, show me the code .
引用文檔：
https://www.open-open.com/lib/view/open1328069609436.html
http://gitlet.maryrosecook.com/docs/gitlet.html
https://git-scm.com/docs/git-add/zh_HANS-CN
https://wyag.thb.lt/#org947aee7
Node 社群
我組建了一個(gè)氛圍特別好的 Node.js 社群，里面有很多 Node.js小伙伴，如果你對(duì)Node.js學(xué)習(xí)感興趣的話（后續(xù)有計(jì)劃也可以），我們可以一起進(jìn)行Node.js相關(guān)的交流、學(xué)習(xí)、共建。下方加 考拉 好友回復(fù)「Node」即可。
如果你覺(jué)得這篇內(nèi)容對(duì)你有幫助，我想請(qǐng)你幫我2個(gè)小忙：
1. 點(diǎn)個(gè)「在看」，讓更多人也能看到這篇文章 2. 訂閱官方博客 www.inode.club 讓我們一起成長(zhǎng) 點(diǎn)贊和在看就是最大的支持