{"thread":{"id":"23344","subject":"[PATCH 3/7 (v5)] support for non-commit objects","startedAt":"2010-04-05T19:58:13Z","lastAt":"2010-04-05T19:58:13Z","messageCount":1,"participants":["Nick Edelen"],"isPatch":true,"patchVersion":5,"patchTotal":7},"messages":[{"id":"138671","messageId":"4BBA40D5.7040104@gmail.com","threadId":"23344","inReplyTo":null,"subject":"[PATCH 3/7 (v5)] support for non-commit objects","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2010-04-05T19:58:13Z","receivedAt":"2010-04-05T19:58:13Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"Contains:\n - support for non-commit object caching\n - expansion of porcelain to accomodate non-commit objects\n - appropriate tests\n\nObjects are stored relative to the commit in which they were introduced --\ncommits are 'diffed' against their parents.  This will eliminate the need for\ntree recursion in cached commits (significantly reducing I/O), and potentially\nbe useful to external applications.\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n rev-cache.c               |  214 ++++++++++++++++++++++++++++++++++++++++++++-\n rev-cache.h               |    3 +-\n t/t6019-rev-cache-list.sh |    6 ++\n 3 files changed, 218 insertions(+), 5 deletions(-)\n\ndiff --git a/rev-cache.c b/rev-cache.c\nindex aa98585..d4b7e16 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -126,7 +126,8 @@ struct rc_object_entry *from_disked_rc_object_entry(unsigned char *src, struct r\n \tdst->type = *src >> 5;\n \tdst->is_end = !!(*src & 0x10);\n \tdst->is_start = !!(*src & 0x08);\n-\tdst->flag = *src & 0x07;\n+\tdst->has_objects = !!(*src & 0x04);\n+\tdst->flag = *src & 0x03;\n \n \tdst->sha1 = (unsigned char *)(src + 1);\n \tdst->merge_nr = *(src + 21);\n@@ -158,6 +159,7 @@ unsigned char *to_disked_rc_object_entry(struct rc_object_entry *src, unsigned c\n \t*dst  = (unsigned char)src->type << 5;\n \t*dst |= (unsigned char)src->is_end << 4;\n \t*dst |= (unsigned char)src->is_start << 3;\n+\t*dst |= (unsigned char)src->has_objects << 2;\n \t*dst |= (unsigned char)src->flag;\n \n \tif (dst + 1 != src->sha1)\n@@ -317,6 +319,32 @@ unsigned char *get_cache_slice(struct commit *commit)\n \n /* traversal */\n \n+static void handle_noncommit(struct rev_info *revs, unsigned char *ptr, struct rc_object_entry *entry)\n+{\n+\tstruct object *obj = 0;\n+\n+\tswitch (entry->type) {\n+\tcase OBJ_TREE:\n+\t\tif (revs->tree_objects)\n+\t\t\tobj = (struct object *)lookup_tree(entry->sha1);\n+\t\tbreak;\n+\tcase OBJ_BLOB:\n+\t\tif (revs->blob_objects)\n+\t\t\tobj = (struct object *)lookup_blob(entry->sha1);\n+\t\tbreak;\n+\tcase OBJ_TAG:\n+\t\tif (revs->tag_objects)\n+\t\t\tobj = (struct object *)lookup_tag(entry->sha1);\n+\t\tbreak;\n+\t}\n+\n+\tif (!obj)\n+\t\treturn;\n+\n+\tobj->flags |= FACE_VALUE;\n+\tadd_pending_object(revs, obj, \"\");\n+}\n+\n struct entrance_point {\n \tint pos;\n \tchar uninteresting;\n@@ -432,9 +460,12 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(entry);\n \n \t\t/* add extra objects if necessary */\n-\t\tif (entry->type != OBJ_COMMIT)\n+\t\tif (entry->type != OBJ_COMMIT) {\n+\t\t\tif (consume_children)\n+\t\t\t\thandle_noncommit(revs, map + index, entry);\n+\n \t\t\tcontinue;\n-\t\telse\n+\t\t} else\n \t\t\tconsume_children = 0;\n \n \t\tif (path >= total_path_nr)\n@@ -514,7 +545,9 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\t/* initialize commit */\n \t\tif (!entry->is_end) {\n \t\t\tco->date = entry->date;\n-\t\t\tobj->flags |= ADDED | FACE_VALUE;\n+\t\t\tobj->flags |= ADDED;\n+\t\t\tif (entry->has_objects)\n+\t\t\t\tobj->flags |= FACE_VALUE;\n \t\t} else\n \t\t\tparse_commit(co);\n \n@@ -867,6 +900,172 @@ static void add_object_entry(const unsigned char *sha1, int type, struct rc_obje\n \n }\n \n+/* returns non-zero to continue parsing, 0 to skip */\n+typedef int (*dump_tree_fn)(const unsigned char *, const char *, unsigned int); /* sha1, path, mode */\n+\n+/* we need to walk the trees by hash, so unfortunately we can't use traverse_trees in tree-walk.c */\n+static int dump_tree(struct tree *tree, dump_tree_fn fn)\n+{\n+\tstruct tree_desc desc;\n+\tstruct name_entry entry;\n+\tstruct tree *subtree;\n+\tint r;\n+\n+\tif (parse_tree(tree))\n+\t\treturn -1;\n+\n+\tinit_tree_desc(&desc, tree->buffer, tree->size);\n+\twhile (tree_entry(&desc, &entry)) {\n+\t\tswitch (fn(entry.sha1, entry.path, entry.mode)) {\n+\t\tcase 0:\n+\t\t\tgoto continue_loop;\n+\t\tdefault:\n+\t\t\tbreak;\n+\t\t}\n+\n+\t\tif (S_ISDIR(entry.mode)) {\n+\t\t\tsubtree = lookup_tree(entry.sha1);\n+\t\t\tif (!subtree)\n+\t\t\t\treturn -2;\n+\n+\t\t\tif ((r = dump_tree(subtree, fn)) < 0)\n+\t\t\t\treturn r;\n+\t\t}\n+\n+continue_loop:\n+\t\tcontinue;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static int dump_tree_callback(const unsigned char *sha1, const char *path, unsigned int mode)\n+{\n+\tunsigned char data[21];\n+\n+\thashcpy(data, sha1);\n+\tdata[20] = !!S_ISDIR(mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+\n+\treturn 1;\n+}\n+\n+static void tree_addremove(struct diff_options *options,\n+\tint whatnow, unsigned mode,\n+\tconst unsigned char *sha1,\n+\tconst char *concatpath, unsigned dirty_sub)\n+{\n+\tunsigned char data[21];\n+\n+\tif (whatnow != '+')\n+\t\treturn;\n+\n+\thashcpy(data, sha1);\n+\tdata[20] = !!S_ISDIR(mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+}\n+\n+static void tree_change(struct diff_options *options,\n+\tunsigned old_mode, unsigned new_mode,\n+\tconst unsigned char *old_sha1,\n+\tconst unsigned char *new_sha1,\n+\tconst char *concatpath,\n+\tunsigned old_dirty_sub, unsigned new_dirty_sub)\n+{\n+\tunsigned char data[21];\n+\n+\tif (!hashcmp(old_sha1, new_sha1))\n+\t\treturn;\n+\n+\thashcpy(data, new_sha1);\n+\tdata[20] = !!S_ISDIR(new_mode);\n+\n+\tstrbuf_add(acc_buffer, data, 21);\n+}\n+\n+static int sort_type_hash(const void *a, const void *b)\n+{\n+\tconst unsigned char *sa = (const unsigned char *)a,\n+\t\t*sb = (const unsigned char *)b;\n+\n+\tif (sa[20] == sb[20])\n+\t\treturn hashcmp(sa, sb);\n+\n+\treturn sa[20] > sb[20] ? -1 : 1;\n+}\n+\n+static int add_unique_objects(struct commit *commit)\n+{\n+\tstruct commit_list *list;\n+\tstruct strbuf os, ost, *orig_buf;\n+\tstruct diff_options opts;\n+\tint i, j, next;\n+\tchar is_first = 1;\n+\n+\tstrbuf_init(&os, 0);\n+\tstrbuf_init(&ost, 0);\n+\torig_buf = acc_buffer;\n+\n+\tdiff_setup(&opts);\n+\tDIFF_OPT_SET(&opts, RECURSIVE);\n+\tDIFF_OPT_SET(&opts, TREE_IN_RECURSIVE);\n+\topts.change = tree_change;\n+\topts.add_remove = tree_addremove;\n+\n+\t/* this is only called for non-ends (ie. all parents interesting) */\n+\tfor (list = commit->parents; list; list = list->next) {\n+\t\tif (is_first)\n+\t\t\tacc_buffer = &os;\n+\t\telse\n+\t\t\tacc_buffer = &ost;\n+\n+\t\tstrbuf_setlen(acc_buffer, 0);\n+\t\tdiff_tree_sha1(list->item->tree->object.sha1, commit->tree->object.sha1, \"\", &opts);\n+\t\tqsort(acc_buffer->buf, acc_buffer->len / 21, 21, (int (*)(const void *, const void *))hashcmp);\n+\n+\t\t/* take intersection */\n+\t\tif (!is_first) {\n+\t\t\tfor (next = i = j = 0; i < os.len; i += 21) {\n+\t\t\t\twhile (j < ost.len && hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)) < 0)\n+\t\t\t\t\tj += 21;\n+\n+\t\t\t\tif (j >= ost.len || hashcmp((unsigned char *)(ost.buf + j), (unsigned char *)(os.buf + i)))\n+\t\t\t\t\tcontinue;\n+\n+\t\t\t\tif (next != i)\n+\t\t\t\t\tmemcpy(os.buf + next, os.buf + i, 21);\n+\t\t\t\tnext += 21;\n+\t\t\t}\n+\n+\t\t\tif (next != i)\n+\t\t\t\tstrbuf_setlen(&os, next);\n+\t\t} else\n+\t\t\tis_first = 0;\n+\t}\n+\n+\tif (is_first) {\n+\t\tacc_buffer = &os;\n+\t\tdump_tree(commit->tree, dump_tree_callback);\n+\t}\n+\n+\tif (os.len)\n+\t\tqsort(os.buf, os.len / 21, 21, sort_type_hash);\n+\n+\tacc_buffer = orig_buf;\n+\tfor (i = 0; i < os.len; i += 21)\n+\t\tadd_object_entry((unsigned char *)(os.buf + i), os.buf[i + 20] ? OBJ_TREE : OBJ_BLOB, 0, 0, 0);\n+\n+\t/* last but not least, the main tree */\n+\tadd_object_entry(commit->tree->object.sha1, OBJ_TREE, 0, 0, 0);\n+\n+\tstrbuf_release(&ost);\n+\tstrbuf_release(&os);\n+\n+\treturn i / 21 + 1;\n+}\n+\n static void init_revcache_directory(void)\n {\n \tstruct stat fi;\n@@ -988,11 +1187,18 @@ int make_cache_slice(struct rev_cache_info *rci,\n \t\t\t\tcommit_list_insert(commit, starts);\n \t\t}\n \n+\t\tif (rci->objects)\n+\t\t\tobject.has_objects = 1;\n+\n \t\tcommit->indegree = 0;\n \n \t\tadd_object_entry(0, 0, &object, &merge_paths, &split_paths);\n \t\tobject_nr++;\n \n+\t\t/* add all unique children for this commit */\n+\t\tif (rci->objects && !object.is_end)\n+\t\t\tobject_nr += add_unique_objects(commit);\n+\n \t\t/* print every ~1MB or so */\n \t\tif (buffer.len > 1000000) {\n \t\t\twrite_in_full(fd, buffer.buf, buffer.len);\ndiff --git a/rev-cache.h b/rev-cache.h\nindex 76f4fb4..75c3c71 100644\n--- a/rev-cache.h\n+++ b/rev-cache.h\n@@ -66,7 +66,8 @@ struct rc_object_entry {\n \tunsigned type:3;\n \tunsigned is_end:1;\n \tunsigned is_start:1;\n-\tunsigned flag:3; /* unused */\n+\tunsigned has_objects:1;\n+\tunsigned flag:2; /* unused */\n \tunsigned char *sha1; /* 20 byte */\n \n \tunsigned char merge_nr; /* : 7 */\ndiff --git a/t/t6019-rev-cache-list.sh b/t/t6019-rev-cache-list.sh\nindex 8017e62..b6cf6fc 100644\n--- a/t/t6019-rev-cache-list.sh\n+++ b/t/t6019-rev-cache-list.sh\n@@ -102,5 +102,11 @@ test_expect_success 'test rev-caches walker directly (unlimited)' '\n \ttest_cmp_sorted list proper_commit_list\n '\n \n+#do the same for objects\n+test_expect_success 'test rev-caches walker with objects' '\n+\tgit rev-cache walk --objects HEAD >list &&\n+\ttest_cmp_sorted list proper_object_list\n+'\n+\n test_done\n \n-- \ntg: (d461192..) t/rc/objects (depends on: t/rc/basic)\n"}]}