{"thread":{"id":"20429","subject":"[PATCH 3/5] non-commit object support for rev-cache","startedAt":"2009-08-06T09:55:36Z","lastAt":"2009-08-06T09:55:36Z","messageCount":1,"participants":["Nick Edelen"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"119766","messageId":"op.ux8i6ywptdk399@sirnot.private","threadId":"20429","inReplyTo":null,"subject":"[PATCH 3/5] non-commit object support for rev-cache","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2009-08-06T09:55:36Z","receivedAt":"2009-08-06T09:55:36Z","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               |  206 ++++++++++++++++++++++++++++++++++++++++++++-\n t/t6015-rev-cache-list.sh |   28 ++++++\n 2 files changed, 231 insertions(+), 3 deletions(-)\n\ndiff --git a/rev-cache.c b/rev-cache.c\nindex 5d9e150..cd618cf 100755\n--- a/rev-cache.c\n+++ b/rev-cache.c\n@@ -229,6 +229,32 @@ unsigned char *get_cache_slice(struct commit *commit)\n \n /* traversal */\n \n+static void handle_noncommit(struct rev_info *revs, struct 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 cache_slice_header *head, unsigned char *map, struct commit *commit, struct commit_list **work)\n {\n \tstruct index_entry *iep;\n@@ -310,9 +336,12 @@ static int traverse_cache_slice_1(struct cache_slice_header *head, unsigned char\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@@ -766,6 +795,168 @@ static void add_object_entry(const unsigned char *sha1, int type, struct object_\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+\tstrbuf_release(&ost);\n+\tstrbuf_release(&os);\n+\t\n+\treturn 0;\n+}\n+\n static void init_revcache_directory(void)\n {\n \tstruct stat fi;\n@@ -879,6 +1070,15 @@ 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\tif (!(commit->object.flags & TREESAME)) {\n+\t\t\t/* add all unique children for this commit */\n+\t\t\tadd_object_entry(commit->tree->object.sha1, OBJ_TREE, 0, 0, 0);\n+\t\t\tobject_nr++;\n+\t\t\t\n+\t\t\tif (!object.is_end)\n+\t\t\t\tobject_nr += add_unique_objects(commit);\n+\t\t}\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);\n@@ -1055,7 +1255,7 @@ int make_cache_index(struct rev_cache_info *rci, unsigned char *cache_sha1,\n \t\t\tcontinue;\n \t\t\n \t\t/* handle index duplication\n-\t\t * -> keep old copy unless new one is an end -- based on expected usage, older ones will be more \n+\t\t * -> keep old copy unless new one is a start -- based on expected usage, older ones will be more \n \t\t * likely to lead to greater slice traversals than new ones\n \t\t * should we allow more intelligent overriding? */\n \t\tdate = ntohl(object_entry->date);\ndiff --git a/t/t6015-rev-cache-list.sh b/t/t6015-rev-cache-list.sh\nindex e61ece4..9cd722a 100755\n--- a/t/t6015-rev-cache-list.sh\n+++ b/t/t6015-rev-cache-list.sh\n@@ -75,6 +75,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@@ -97,4 +98,31 @@ test_expect_success 'test rev-caches walker directly (unlimited)' '\n \ttest -z `$sha1diff list proper_commit_list`\n '\n \n+test_expect_success 'test rev-list rev-list traversal (limited)' '\n+\tgit-rev-list HEAD --not HEAD~3 >list && \n+\ttest -z `$sha1diff list proper_commit_list_limited`\n+'\n+\n+test_expect_success 'test rev-list traversal (unlimited)' '\n+\tgit-rev-list HEAD >list && \n+\ttest -z `$sha1diff 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 -z `$sha1diff list proper_object_list`\n+'\n+\n+test_expect_success 'test rev-list with objects (limited)' '\n+\tgit-rev-list --topo-order --objects HEAD >list && \n+\ttest -z `$sha1diff list proper_object_list`\n+'\n+\n+test_expect_success 'test rev-list with objects (unlimited)' '\n+\tgit-rev-list --objects HEAD >list && \n+\ttest -z `$sha1diff list proper_object_list`\n+'\n+\n test_done\n+\n-- \ntg: (587109a..) t/revcache/objects (depends on: t/revcache/basic)\n"}]}