Git源码学习系列（四）——git checkout&git-read-tree

[soapgu]

• 下一个目标是谁？

是merge还是rebase？因为我觉得这两个概念还是太难。还没到火候。
目的我对git checkout 比较感兴趣，git是怎么方便的魔术般快速的切换版本的？

• git checkout有什么？

首先git checkout也是一个shell脚本
具体内存主要是git-read-tree + git-checkout-cache
想不到这么快就和git-read-tree见面了！
当然这打脸也是相当的快，其实git-read-tree比git-write-tree要复杂的多，虽然有一部分确实是反向逻辑，但是还有很多“机关”在都之前都完全没享到

• git-read-tree 文档概况

还是先看文档比较好
功能大概是：Reads tree information into the directory cache
嗯，从已经持有化的对象数据库 tree -> cache ,算是write-tree的反向操作。
但是后面文档有大量的篇幅来讲merge！

• Single Tree Merge
• Two Tree Merge
• 3-Way Merge

这下一下子把我给整不会了啊，按照套路来，应该不是果然read-tree和write-tree一样反向操作，看懂递归一切OK了嘛。
原来git-read-tree的核心不在于read而是merge

• git-read-tree 代码梳理1

还是从read-tree.c的main函数入口开始

1. 解析参数
   主要是-或者--参数读取，设置标志位（略）

2. 重新加载cache并去除unmerged的cache
   主要用read_cache_unmerged方法实现，先调用read_cache，很熟悉了
   再检查 ce_stage的标志位，有没有unmerge的，如果有则删除。
   代码还比较简单
   先赋值cache_entry **dst;
   一次遍历，如果有删除后续项直接“补位”

3.读取tree的id
注意，这里的tree的id可以多个，前面讲到了3-Way Merge，所以tree最多可以有3个！
这里用stage变量计数
stage=2：Single Tree Merge
stage=3：Two Tree Merge
stage=4：3-Way Merge
这里我们可以把后两种情况先放一放，比较不符合我“计划”的场景。
通过调用get_sha1来实现获取tree的id
a. 尝试读取40位的sha1来获取
b. 尝试通过name匹配读取refs中的内容，再从refs的文件中获取相关sha1的id

4. 把tree读取到cache中
   这里算是符合read-tree的“中心思想”了，但是其实只是一个中间步骤！后面慢慢讲
   这里是调用unpack_tree来实现
   a）调用read_object_with_reference
   这里简化下过程通过find_sha1_file函数找到对应实体文件
   map_sha1_file_internal把文件内容读入内存
   unpack_sha1_file把内容解压出来，
   先调用unpack_sha1_header->parse_sha1_header解析出对象的type和length，我们所有对象的head都是{type} {length}。所以我们通过一次遍历完成解析
   unpack_sha1_rest把其他内容也一并解压出来

b）调用read_tree
这里和write_tree的逻辑正好相反
里面用read_tree_recursive递归实现，也有base和baselen的概念
这里不展开了，代码还是很精彩的，有兴趣的同学还是可以亲自读一下

注：主要区别在于，这里read_tree，多了一个stage的参数。
这里tree主要是遍历，read_one_entry把真正的cache_entry对象扔到cache里面去
这里再次注意stage
ce->ce_flags = create_ce_flags(baselen + len, stage);
被边进了ce_flags里面去了。

• 本节代码要点

• read_tree可以读入好几颗(1-3),这样意味着同样的filename可能有多个版本都“共存”在cache中

• 不同的的版本用stage区分，stage被记录到ce_flags 中
  这里ce_flags成了cache_entry的关键属性了，我需要扒一扒看看。

• ce_flags究竟有啥用？

其实ce_flags已经是老朋友了，第一篇就碰到了，但是对其作用搞不清楚也只能skip了。

• 从新建逻辑看

#define CE_STAGESHIFT 12
create_ce_flags(len, stage) htons((len) | ((stage) << CE_STAGESHIFT))

单看这段代码有点懵，就是左移12位的stage 和 name的length合并在一起存ce_flags

• 从读取namelen逻辑看

#define CE_NAMEMASK  (0x0fff)
#define ce_namelen(ce) (CE_NAMEMASK & ntohs((ce)->ce_flags))

这里稍微通一点，就是说我们的名字长度不可能太长（毕竟太长不现实）
名字长度最多我们用0x0fff。
再直白一点就是双字节存储16位，使用掩码0000111111111111，就是只用12位。那还有4位给谁用那？

• 从读取stage看

#define CE_STAGEMASK (0x3000)
#define CE_STAGESHIFT 12
#define ce_stage(ce) ((CE_STAGEMASK & ntohs((ce)->ce_flags)) >> CE_STAGESHIFT)

这回差不多看出来了吧
0x3000=0011000000000000做&掩码正好取了第一个字节的低字节。
再执行>> CE_STAGESHIFT，正好把右方的零“清掉”

• CE_STAGEMASK 为啥只取2位？
  容量刚刚好stage0~stage3。正好对应3-Way Merge。真是一点都不浪费！一个字段n用

• 剩下还有两个“位”存了什么信息？
  还有一个#define CE_UPDATE (0x4000)，把第二位给“占”了，暂时还不知道有啥用
  ”最高位“应该是保留了吧，并没有看到0x8000的MASK。

• 数形结合再总结理解下
  一图解千愁
  

• stage是做啥？
  绕了半天ce_stage可以从ce_flags“独立”出来了。一个blob分了好多个版本其实是没有意义的，最终，“分久必合”，这是合并前的准备。下面一节我们开始讲merge_cache

• git-read-tree 代码梳理2：初见merge_cache

接下来是merge的主逻辑啦

static const merge_fn_t merge_function[] = {
			[1] = oneway_merge,
			[2] = twoway_merge,
			[3] = threeway_merge,
		};
		merge_fn_t fn;

		if (stage < 2 || stage > 4)
			die("just how do you expect me to merge %d trees?", stage-1);
		if (emu23 && stage != 3)
			die("--emu23 takes only two trees");
		fn = merge_function[stage-1];
		if (stage == 3 && emu23) { 
			setup_emu23();
			fn = merge_function[3];
		}
		merge_cache(active_cache, active_nr, fn);

merge初始化操作

可以看到--emu23应该是有特殊处理，到stage3但是用的stage4 threeway_merge逻辑处理
merge_function正好存了三种merge的方法。
我们再进入到merge_cache函数看下merge逻辑。

static void merge_cache(struct cache_entry **src, int nr, merge_fn_t fn)
{
	struct cache_entry **dst = src;
	int tail = nr;

	while (nr) {
		int entries;
		struct cache_entry *name, *ce, *stages[4] = { NULL, };

		name = ce = *src;
		for (;;) {
			int stage = ce_stage(ce);
			stages[stage] = ce;
			ce = *++src;
			active_nr--;
			if (!--nr)
				break;
			if (!path_matches(ce, name))
				break;
		}

		entries = fn(stages, dst, src, tail);
		if (entries < 0)
			reject_merge(name);
		dst += entries;
		active_nr += entries;
	}
	check_updates(active_cache, active_nr);
}

merge_cache方法详解

1. 初始化目标指针**dst
   尾部数量tail

2. 开始遍历
   初始化变量
   int entries：本次merge的数量具体后面讲
   name：本次遍历的基础值，比较name对应的path都一样的值进入merge阶段
   ce：和name比较动态指针,如果一样存入待merge数组
   stages[4]：本次循环的merge数组，因为最多3树合并，加上本来的cache，满打满算4，所以数组直接设4

3. for循环里面收集 stages待merge元素，
   只要path_matches就继续for循环进stages

4. merge所有stages的元素
   根据合并的情况，dst指向移动，active_nr增值

• 疑问？既然是merge，就是2合1，3合1，4合1，怎么就看不到删cache那？和我们平时操作不一样嘛
  这里有必要图文讲解了，你再结合上面的代码就一下通透了

其实这里merge_cache的dst指针就是把原来的cache的整个内存“重新分配”了
这里再次感谢下cache_entry的name排序，让我们可以把相同路径的元素“自然”的凑在一起
entries就是合并结果
小于0：拒绝合并并退出，这里不展开套路
大于0：就是合并完的个数，目标都是1，暂时还没看到大于1的情况
等于0：其实就是合并结果是删除，这种情况也常见，这种情况dst指针就不动了，等下个元素加入再动

• Single Tree Merge算法

上一节里面fn就是merge算法的指针。其他的Merge算法太难。我们先挑最简单的逻辑先深入
Single Tree Merge算法是通过oneway_merge方法实现的

/*
 * One-way merge.
 *
 * The rule is:
 * - take the stat information from stage0, take the data from stage1
 */
static int oneway_merge(struct cache_entry **src, struct cache_entry **dst,
			struct cache_entry **next, int tail)
{
	struct cache_entry *old = src[0];
	struct cache_entry *a = src[1];

	if (src[2] || src[3])
		return -1;

	if (!a)
		return 0;
	if (old && same(old, a)) {
		*dst++ = old;
		return 1;
	}
	return merged_entry(a, NULL, dst);
}

注释也说很明确了，以stage1的数据为准
如果，新的树里面没这个entry，entries就直接返回0，表示删除
如果，新老cache一样，那么就无所谓新旧保留老的cache
如果新老不一，无脑用新，再调用merged_entry。
我们再看下merged_entry做了啥

merge->ce_flags |= htons(CE_UPDATE);
ce_flags 加上CE_UPDATE标志位，就是左起第2位。

merge->ce_flags &= ~htons(CE_STAGEMASK);
把stage的标志位清零

*dst++ = merge;
把合入的cache放入dst

• 尾声

最后就是回写index的逻辑，调用write_cache和commit_index_file
和update-cache的逻辑一模一样。略

总结查漏补缺

1. read-tree的核心在于merge而非read
   目前我们选择了最简场景。未来merge可能这里还有再深入。

2. 如果使用checkout切换到某个commit，就是先调用git-read-tree

等下！不是前面git-read-tree的参数是 tree-id 不是commit-id啊！我哪里搞错了
再看下文档里面教程里面也是用git-read-tree HEAD，HEAD里面也应该是commit的id啊。
一定是遗漏了啥
再读read_object_with_reference函数，发现里面有个const char *required_type

               while (1) {
		int ref_length = -1;
		const char *ref_type = NULL;

		buffer = read_sha1_file(actual_sha1, type, &isize);
		if (!buffer)
			return NULL;
		if (!strcmp(type, required_type)) {
			*size = isize;
			if (actual_sha1_return)
				memcpy(actual_sha1_return, actual_sha1, 20);
			return buffer;
		}
		/* Handle references */
		else if (!strcmp(type, "commit"))
			ref_type = "tree ";
		else if (!strcmp(type, "tag"))
			ref_type = "object ";
		else {
			free(buffer);
			return NULL;
		}
		ref_length = strlen(ref_type);

		if (memcmp(buffer, ref_type, ref_length) ||
		    get_sha1_hex(buffer + ref_length, actual_sha1)) {
			free(buffer);
			return NULL;
		}
		/* Now we have the ID of the referred-to object in
		 * actual_sha1.  Check again. */
	}

再看一遍，就是读出的对象和required_type完全一致就直接返回
如果不是，那就可能是应用对象commit或者tag
接下来把内容再截取一下

就是把“tree ”去头（红色部分），往后截取40个字符，获取新的sha1,直到读到tree为止。
OK，逻辑闭环了。只是这文档有点粗糙，应该是tree id或者是他的引用吧。

3. merge逻辑充分考虑性能
   比如我checkout一个变化不是很大的commit，通过目前的算法速度非常快。不是以前“想象中”的“全进全出”。

4. read tree，而cache不真正存tree
   非常有意思，心中有tree，手中无tree。