{"thread":{"id":"20578","subject":"[PATCH 3/6 (v3)] non-commit object support for rev-cache","startedAt":"2009-08-13T10:24:38Z","lastAt":"2009-08-13T10:24:38Z","messageCount":1,"participants":["Nick Edelen"],"isPatch":true,"patchVersion":3,"patchTotal":6},"messages":[{"id":"120507","messageId":"op.uyli7cshtdk399@sirnot.belkin","threadId":"20578","inReplyTo":null,"subject":"[PATCH 3/6 (v3)] non-commit object support for rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-13T10:24:38Z","receivedAt":"2009-08-13T10:24:38Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"Summarized, this third patch 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               |  202 ++++++++++++++++++++++++++++++++++++++++++++-\n t/t6015-rev-cache-list.sh |    8 ++\n 2 files changed, 208 insertions(+), 2 deletions(-)\n\ndiff --git a/rev-cache.c b/rev-cache.c\nindex 623c735..e1b5f9f 100644\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -172,6 +172,32 @@ unsigned char *get_cache_slice(struct commit *commit)\n \n /* traversal */\n \n+static void handle_noncommit(struct rev_info *revs, struct rc_object_entry *entry)\n+{\n+\tstruct object *obj = 0;\n+\t\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+\t\n+\tif (!obj)\n+\t\treturn;\n+\t\n+\tobj->flags |= FACE_VALUE;\n+\tadd_pending_object(revs, obj, \"\");\n+}\n+\n static int setup_traversal(struct rc_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work)\n {\n \tstruct rc_index_entry *iep;\n@@ -252,9 +278,12 @@ static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *m\n \t\ti += ACTUAL_OBJECT_ENTRY_SIZE(entry);\n \t\t\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, entry);\n+\t\t\t\n \t\t\tcontinue;\n-\t\telse\n+\t\t} else\n \t\t\tconsume_children = 0;\n \t\t\n \t\tif (path >= total_path_nr)\n@@ -682,6 +711,171 @@ static void add_object_entry(const unsigned char *sha1, int type, struct rc_obje\n \t\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+\t\n+\tif (parse_tree(tree))\n+\t\treturn -1;\n+\t\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+\t\t\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+\t\t\t\n+\t\t\tif ((r = dump_tree(subtree, fn)) < 0)\n+\t\t\t\treturn r;\n+\t\t}\n+\t\t\n+continue_loop:\n+\t\tcontinue;\n+\t}\n+\t\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+\t\n+\thashcpy(data, sha1);\n+\tdata[20] = !!S_ISDIR(mode);\n+\t\n+\tstrbuf_add(g_buffer, data, 21);\n+\t\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)\n+{\n+\tunsigned char data[21];\n+\t\n+\tif (whatnow != '+')\n+\t\treturn;\n+\t\n+\thashcpy(data, sha1);\n+\tdata[20] = !!S_ISDIR(mode);\n+\t\n+\tstrbuf_add(g_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+{\n+\tunsigned char data[21];\n+\t\n+\tif (!hashcmp(old_sha1, new_sha1))\n+\t\treturn;\n+\t\n+\thashcpy(data, new_sha1);\n+\tdata[20] = !!S_ISDIR(new_mode);\n+\t\n+\tstrbuf_add(g_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+\t\n+\tif (sa[20] == sb[20])\n+\t\treturn hashcmp(sa, sb);\n+\t\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+\t\n+\tstrbuf_init(&os, 0);\n+\tstrbuf_init(&ost, 0);\n+\torig_buf = g_buffer;\n+\t\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+\t\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\tg_buffer = &os;\n+\t\telse \n+\t\t\tg_buffer = &ost;\n+\t\t\n+\t\tstrbuf_setlen(g_buffer, 0);\n+\t\tdiff_tree_sha1(list->item->tree->object.sha1, commit->tree->object.sha1, \"\", &opts);\n+\t\tqsort(g_buffer->buf, g_buffer->len / 21, 21, (int (*)(const void *, const void *))hashcmp);\n+\t\t\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+\t\t\t\t\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+\t\t\t\t\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+\t\t\t\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+\t\n+\tif (is_first) {\n+\t\tg_buffer = &os;\n+\t\tdump_tree(commit->tree, dump_tree_callback);\n+\t}\n+\t\n+\tif (os.len)\n+\t\tqsort(os.buf, os.len / 21, 21, sort_type_hash);\n+\t\n+\tg_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+\t\n+\t/* last but not least, the main tree */\n+\tadd_object_entry(commit->tree->object.sha1, OBJ_TREE, 0, 0, 0);\n+\t\n+\tstrbuf_release(&ost);\n+\tstrbuf_release(&os);\n+\t\n+\treturn i / 21 + 1;\n+}\n+\n static void init_revcache_directory(void)\n {\n \tstruct stat fi;\n@@ -809,6 +1003,10 @@ int make_cache_slice(struct rev_cache_info *rci,\n \t\tadd_object_entry(0, 0, &object, &merge_paths, &split_paths);\n \t\tobject_nr++;\n \t\t\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+\t\t\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/t/t6015-rev-cache-list.sh b/t/t6015-rev-cache-list.sh\nindex e7474fd..afa0303 100755\n--- a/t/t6015-rev-cache-list.sh\n+++ b/t/t6015-rev-cache-list.sh\n@@ -79,6 +79,7 @@ test_expect_success 'init repo' '\n \n git-rev-list HEAD --not HEAD~3 >proper_commit_list_limited\n git-rev-list HEAD >proper_commit_list\n+git-rev-list HEAD --objects >proper_object_list\n \n test_expect_success 'make cache slice' '\n \tgit-rev-cache add HEAD 2>output.err && \n@@ -101,4 +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: (965f7fe..) t/revcache/objects (depends on: t/revcache/basic)\n"}]}