Re: [PATCH 12/12] index-pack: resolve v4 one-base trees

> This is the most common case for delta trees. In fact it's the only
> kind that's produced by packv4-create. It fits well in the way
> index-pack resolves deltas and benefits from threading (the set of
> objects depending on this base does not overlap with the set of
> objects depending on another base)
> 
> Multi-base trees will be probably processed differently.
> 
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---
>  builtin/index-pack.c | 194 ++++++++++++++++++++++++++++++++++++++++++++++-----
>  1 file changed, 178 insertions(+), 16 deletions(-)
> 
> diff --git a/builtin/index-pack.c b/builtin/index-pack.c
> index 1fa74f4..4a24bc3 100644
> --- a/builtin/index-pack.c
> +++ b/builtin/index-pack.c
> @@ -12,6 +12,8 @@
>  #include "streaming.h"
>  #include "thread-utils.h"
>  #include "packv4-parse.h"
> +#include "varint.h"
> +#include "tree-walk.h"
>  
>  static const char index_pack_usage[] =
>  "git index-pack [-v] [-o <index-file>] [--keep | --keep=<msg>] [--verify] [--strict] (<pack-file> | --stdin [--fix-thin] [<pack-file>])";
> @@ -38,8 +40,8 @@ struct base_data {
>  	struct object_entry *obj;
>  	void *data;
>  	unsigned long size;
> -	int ref_first, ref_last;
> -	int ofs_first, ofs_last;
> +	int ref_first, ref_last, tree_first;
> +	int ofs_first, ofs_last, tree_last;
>  };
>  
>  #if !defined(NO_PTHREADS) && defined(NO_THREAD_SAFE_PREAD)
> @@ -437,6 +439,7 @@ static struct base_data *alloc_base_data(void)
>  	memset(base, 0, sizeof(*base));
>  	base->ref_last = -1;
>  	base->ofs_last = -1;
> +	base->tree_last = -1;
>  	return base;
>  }
>  
> @@ -670,6 +673,8 @@ static void *unpack_tree_v4(struct object_entry *obj,
>  	}
>  
>  	if (last_base) {
> +		if (nr_deltas - delta_start > 1)
> +			die("sorry guys, multi-base trees are not supported yet");
>  		strbuf_release(&sb);
>  		return NULL;
>  	} else {
> @@ -794,6 +799,83 @@ static void *unpack_raw_entry(struct object_entry *obj,
>  	return data;
>  }
>  
> +static void *patch_one_base_tree(const struct object_entry *src,
> +				 const unsigned char *src_buf,
> +				 const unsigned char *delta_buf,
> +				 unsigned long delta_size,
> +				 unsigned long *dst_size)
> +{
> +	unsigned int nr;
> +	const unsigned char *last_base = NULL;
> +	struct strbuf sb = STRBUF_INIT;
> +	const unsigned char *p = delta_buf;
> +
> +	nr = decode_varint(&p);
> +	while (nr && p < delta_buf + delta_size) {
> +		unsigned int copy_start_or_path = decode_varint(&p);
> +		if (copy_start_or_path & 1) { /* copy_start */
> +			struct tree_desc desc;
> +			struct name_entry entry;
> +			unsigned int copy_count = decode_varint(&p);
> +			unsigned int copy_start = copy_start_or_path >> 1;
> +			if (!src)
> +				die("we are not supposed to copy from another tree!");
> +			if (copy_count & 1) { /* first delta */
> +				unsigned int id = decode_varint(&p);
> +				if (!id) {
> +					last_base = p;
> +					p += 20;
> +				} else
> +					last_base = sha1_table + (id - 1) * 20;
> +				if (hashcmp(last_base, src->idx.sha1))
> +					die(_("bad tree base in patch_one_base_tree"));
> +			} else if (!last_base)
> +				die(_("bad copy count index in patch_one_base_tree"));
> +			copy_count >>= 1;
> +			if (!copy_count)
> +				die(_("bad copy count index in patch_one_base_tree"));
> +			nr -= copy_count;
> +
> +			init_tree_desc(&desc, src_buf, src->size);
> +			while (tree_entry(&desc, &entry)) {
> +				if (copy_start)
> +					copy_start--;
> +				else if (copy_count) {
> +					strbuf_addf(&sb, "%o %s%c", entry.mode, entry.path, '\0');
> +					strbuf_add(&sb, entry.sha1, 20);
> +					copy_count--;
> +				} else
> +					break;
> +			}
> +		} else {	/* path */
> +			unsigned int path_idx = copy_start_or_path >> 1;
> +			const unsigned char *path;
> +			unsigned mode;
> +			unsigned int id;
> +			const unsigned char *entry_sha1;
> +
> +			if (path_idx >= path_dict->nb_entries)
> +				die(_("bad path index in unpack_tree_v4"));
> +			id = decode_varint(&p);
> +			if (!id) {
> +				entry_sha1 = p;
> +				p += 20;
> +			} else
> +				entry_sha1 = sha1_table + (id - 1) * 20;