{"thread":{"id":"23342","subject":"[PATCH 2/7 (v5)] basic api and porcelain","startedAt":"2010-04-05T19:58:05Z","lastAt":"2010-04-06T21:40:35Z","messageCount":3,"participants":["Nick Edelen","Julian Phillips"],"isPatch":true,"patchVersion":5,"patchTotal":7},"messages":[{"id":"138669","messageId":"4BBA40CD.5040301@gmail.com","threadId":"23342","inReplyTo":null,"subject":"[PATCH 2/7 (v5)] basic api and porcelain","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2010-04-05T19:58:05Z","receivedAt":"2010-04-05T19:58:05Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"Provides:\n - minimal API: caching only commit topo data\n - minimal porcelain: add and walk cache slices\n - appropriate tests\n\nSigned-off-by: Nick Edelen <sirnot@gmail.com>\n\n---\n Makefile                  |    2 +\n builtin.h                 |    1 +\n builtin/rev-cache.c       |  210 ++++++++\n commit.c                  |    2 +\n git.c                     |    1 +\n rev-cache.c               | 1273 +++++++++++++++++++++++++++++++++++++++++++++\n rev-cache.h               |  105 ++++\n revision.c                |    2 +-\n revision.h                |   26 +-\n t/t6019-rev-cache-list.sh |  106 ++++\n 10 files changed, 1726 insertions(+), 2 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex e210a42..4d87da4 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -597,6 +597,7 @@ LIB_OBJS += refs.o\n LIB_OBJS += remote.o\n LIB_OBJS += replace_object.o\n LIB_OBJS += rerere.o\n+LIB_OBJS += rev-cache.o\n LIB_OBJS += resolve-undo.o\n LIB_OBJS += revision.o\n LIB_OBJS += run-command.o\n@@ -697,6 +698,7 @@ BUILTIN_OBJS += builtin/reflog.o\n BUILTIN_OBJS += builtin/remote.o\n BUILTIN_OBJS += builtin/replace.o\n BUILTIN_OBJS += builtin/rerere.o\n+BUILTIN_OBJS += builtin/rev-cache.o\n BUILTIN_OBJS += builtin/reset.o\n BUILTIN_OBJS += builtin/rev-list.o\n BUILTIN_OBJS += builtin/rev-parse.o\ndiff --git a/builtin.h b/builtin.h\nindex 464588b..1fea332 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -112,6 +112,7 @@ extern int cmd_remote(int argc, const char **argv, const char *prefix);\n extern int cmd_config(int argc, const char **argv, const char *prefix);\n extern int cmd_rerere(int argc, const char **argv, const char *prefix);\n extern int cmd_reset(int argc, const char **argv, const char *prefix);\n+extern int cmd_rev_cache(int argc, const char **argv, const char *prefix);\n extern int cmd_rev_list(int argc, const char **argv, const char *prefix);\n extern int cmd_rev_parse(int argc, const char **argv, const char *prefix);\n extern int cmd_revert(int argc, const char **argv, const char *prefix);\ndiff --git a/builtin/rev-cache.c b/builtin/rev-cache.c\nnew file mode 100644\nindex 0000000..e322467\n--- /dev/null\n+++ b/builtin/rev-cache.c\n@@ -0,0 +1,210 @@\n+#include \"cache.h\"\n+#include \"object.h\"\n+#include \"commit.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n+#include \"rev-cache.h\"\n+\n+/* porcelain for rev-cache.c */\n+static int handle_add(int argc, const char *argv[]) /* args beyond this command */\n+{\n+\tstruct rev_info revs;\n+\tstruct rev_cache_info rci;\n+\tchar dostdin = 0;\n+\tunsigned int flags = 0;\n+\tint i, retval;\n+\tunsigned char cache_sha1[20];\n+\tstruct commit_list *starts = 0, *ends = 0;\n+\tstruct commit *commit;\n+\n+\tinit_revisions(&revs, 0);\n+\tinit_rev_cache_info(&rci);\n+\n+\tfor (i = 0; i < argc; i++) {\n+\t\tif (!strcmp(argv[i], \"--stdin\"))\n+\t\t\tdostdin = 1;\n+\t\telse if (!strcmp(argv[i], \"--fresh\") || !strcmp(argv[i], \"--incremental\"))\n+\t\t\tstarts_from_slices(&revs, UNINTERESTING);\n+\t\telse if (!strcmp(argv[i], \"--not\"))\n+\t\t\tflags ^= UNINTERESTING;\n+\t\telse if (!strcmp(argv[i], \"--legs\") || !strcmp(argv[i], \"--close\"))\n+\t\t\trci.legs = 1;\n+\t\telse if (!strcmp(argv[i], \"--no-objects\"))\n+\t\t\trci.objects = 0;\n+\t\telse if (!strcmp(argv[i], \"--all\")) {\n+\t\t\tconst char *args[2];\n+\t\t\tint argn = 0;\n+\n+\t\t\targs[argn++] = \"rev-list\";\n+\t\t\targs[argn++] = \"--all\";\n+\t\t\tsetup_revisions(argn, args, &revs, 0);\n+\t\t} else\n+\t\t\thandle_revision_arg(argv[i], &revs, flags, 1);\n+\t}\n+\n+\tif (dostdin) {\n+\t\tchar line[1000];\n+\n+\t\tflags = 0;\n+\t\twhile (fgets(line, sizeof(line), stdin)) {\n+\t\t\tint len = strlen(line);\n+\t\t\twhile (len && (line[len - 1] == '\\n' || line[len - 1] == '\\r'))\n+\t\t\t\tline[--len] = 0;\n+\n+\t\t\tif (!len)\n+\t\t\t\tbreak;\n+\n+\t\t\tif (!strcmp(line, \"--not\"))\n+\t\t\t\tflags ^= UNINTERESTING;\n+\t\t\telse\n+\t\t\t\thandle_revision_arg(line, &revs, flags, 1);\n+\t\t}\n+\t}\n+\n+\tretval = make_cache_slice(&rci, &revs, &starts, &ends, cache_sha1);\n+\tif (retval < 0)\n+\t\treturn retval;\n+\n+\tprintf(\"%s\\n\", sha1_to_hex(cache_sha1));\n+\n+\tfprintf(stderr, \"endpoints:\\n\");\n+\twhile ((commit = pop_commit(&starts)))\n+\t\tfprintf(stderr, \"S %s\\n\", sha1_to_hex(commit->object.sha1));\n+\twhile ((commit = pop_commit(&ends)))\n+\t\tfprintf(stderr, \"E %s\\n\", sha1_to_hex(commit->object.sha1));\n+\n+\treturn 0;\n+}\n+\n+static int handle_walk(int argc, const char *argv[])\n+{\n+\tstruct commit *commit;\n+\tstruct rev_info revs;\n+\tstruct commit_list *queue, *work, **qp;\n+\tunsigned char *sha1p, *sha1pt;\n+\tunsigned long date = 0;\n+\tunsigned int flags = 0;\n+\tint retval, slop = 5, i;\n+\n+\tinit_revisions(&revs, 0);\n+\n+\tfor (i = 0; i < argc; i++) {\n+\t\tif (!strcmp(argv[i], \"--not\"))\n+\t\t\tflags ^= UNINTERESTING;\n+\t\telse if (!strcmp(argv[i], \"--objects\"))\n+\t\t\trevs.tree_objects = revs.blob_objects = 1;\n+\t\telse\n+\t\t\thandle_revision_arg(argv[i], &revs, flags, 1);\n+\t}\n+\n+\twork = 0;\n+\tsha1p = 0;\n+\tfor (i = 0; i < revs.pending.nr; i++) {\n+\t\tcommit = lookup_commit(revs.pending.objects[i].item->sha1);\n+\n+\t\tsha1pt = get_cache_slice(commit);\n+\t\tif (!sha1pt)\n+\t\t\tdie(\"%s: not in a cache slice\", sha1_to_hex(commit->object.sha1));\n+\n+\t\tif (!i)\n+\t\t\tsha1p = sha1pt;\n+\t\telse if (sha1p != sha1pt)\n+\t\t\tdie(\"walking porcelain is /per/ cache slice; commits cannot be spread out amoung several\");\n+\n+\t\tinsert_by_date(commit, &work);\n+\t}\n+\n+\tif (!sha1p)\n+\t\tdie(\"nothing to traverse!\");\n+\n+\trevs.pending.nr = 0;\n+\tqueue = 0;\n+\tqp = &queue;\n+\tcommit = pop_commit(&work);\n+\tretval = traverse_cache_slice(&revs, sha1p, commit, &date, &slop, &qp, &work);\n+\tif (retval < 0)\n+\t\treturn retval;\n+\n+\tfprintf(stderr, \"queue:\\n\");\n+\twhile ((commit = pop_commit(&queue)) != 0) {\n+\t\tprintf(\"%s\\n\", sha1_to_hex(commit->object.sha1));\n+\t}\n+\n+\tfprintf(stderr, \"work:\\n\");\n+\twhile ((commit = pop_commit(&work)) != 0) {\n+\t\tprintf(\"%s\\n\", sha1_to_hex(commit->object.sha1));\n+\t}\n+\n+\tfprintf(stderr, \"pending:\\n\");\n+\tfor (i = 0; i < revs.pending.nr; i++) {\n+\t\tstruct object *obj = revs.pending.objects[i].item;\n+\n+\t\t/* unfortunately, despite our careful generation, object duplication *is* a possibility...\n+\t\t * (eg. same object introduced into two different branches) */\n+\t\tif (obj->flags & SEEN)\n+\t\t\tcontinue;\n+\n+\t\tprintf(\"%s\\n\", sha1_to_hex(revs.pending.objects[i].item->sha1));\n+\t\tobj->flags |= SEEN;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static int handle_help(void)\n+{\n+\tchar *usage = \"\\\n+usage:\\n\\\n+git-rev-cache COMMAND [options] [<commit>...]\\n\\\n+commands:\\n\\\n+  add    - add revisions to the cache.  reads commit ids from stdin, \\n\\\n+           START = 'interesting', END = boundary of 'uninterestingness'\\n\\\n+           options:\\n\\\n+            --all                  use all branch heads as starts\\n\\\n+            --fresh/--incremental  exclude everything already in a cache slice\\n\\\n+            --stdin                also read commit ids from stdin (same form\\n\\\n+                                   as cmd)\\n\\\n+            --legs/--close         ensure branch is entirely self-contained\\n\\\n+            --no-objects           don't add non-commit objects to slice\\n\\\n+  walk   - walk a cache slice based on set of commits; formatted as add\\n\\\n+           options:\\n\\\n+           --objects               include non-commit objects in traversals\\n\\\n+  fuse   - coalesce cache slices into a single cache.\\n\\\n+           options:\\n\\\n+            --all                  include all objects in repository\\n\\\n+            --no-objects           don't add non-commit objects to slice\\n\\\n+            --ignore-size[=N]      ignore slices of size >= N; defaults to ~5MB\\n\\\n+            --keep-size[=N]\\n\\\n+  index  - regnerate the cache index.\\n\\\n+  alt    - create a slice pointer to slice identified by a passed path\";\n+\n+\tputs(usage);\n+\n+\treturn 0;\n+}\n+\n+int cmd_rev_cache(int argc, const char *argv[], const char *prefix)\n+{\n+\tconst char *arg;\n+\tint r;\n+\n+\tgit_config(git_default_config, NULL);\n+\n+\tif (argc > 1)\n+\t\targ = argv[1];\n+\telse\n+\t\targ = \"\";\n+\n+\targc -= 2;\n+\targv += 2;\n+\tif (!strcmp(arg, \"add\"))\n+\t\tr = handle_add(argc, argv);\n+\telse if (!strcmp(arg, \"walk\"))\n+\t\tr = handle_walk(argc, argv);\n+\telse\n+\t\treturn handle_help();\n+\n+\tfprintf(stderr, \"final return value: %d\\n\", r);\n+\n+\treturn 0;\n+}\ndiff --git a/commit.c b/commit.c\nindex 731191e..263dd74 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -251,6 +251,8 @@ int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size)\n \titem->tree = lookup_tree(parent);\n \tbufptr += 46; /* \"tree \" + \"hex sha1\" + \"\\n\" */\n \tpptr = &item->parents;\n+\twhile (pop_commit(pptr))\n+\t\t; /* clear anything from cache */\n \n \tgraft = lookup_commit_graft(item->object.sha1);\n \twhile (bufptr + 48 < tail && !memcmp(bufptr, \"parent \", 7)) {\ndiff --git a/git.c b/git.c\nindex 6bae305..5b77f49 100644\n--- a/git.c\n+++ b/git.c\n@@ -363,6 +363,7 @@ static void handle_internal_command(int argc, const char **argv)\n \t\t{ \"repo-config\", cmd_config },\n \t\t{ \"rerere\", cmd_rerere, RUN_SETUP },\n \t\t{ \"reset\", cmd_reset, RUN_SETUP },\n+\t\t{ \"rev-cache\", cmd_rev_cache, RUN_SETUP },\n \t\t{ \"rev-list\", cmd_rev_list, RUN_SETUP },\n \t\t{ \"rev-parse\", cmd_rev_parse },\n \t\t{ \"revert\", cmd_revert, RUN_SETUP | NEED_WORK_TREE },\ndiff --git a/rev-cache.c b/rev-cache.c\nnew file mode 100644\nindex 0000000..aa98585\n--- /dev/null\n+++ b/rev-cache.c\n@@ -0,0 +1,1273 @@\n+#include \"cache.h\"\n+#include \"object.h\"\n+#include \"commit.h\"\n+#include \"tree.h\"\n+#include \"tree-walk.h\"\n+#include \"blob.h\"\n+#include \"tag.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n+#include \"rev-cache.h\"\n+#include \"run-command.h\"\n+\n+/* list resembles pack index format */\n+static uint32_t fanout[0xff + 2];\n+\n+static unsigned char *idx_map;\n+static int idx_size;\n+static struct rc_index_header idx_head;\n+static unsigned char *idx_caches;\n+static char no_idx;\n+\n+static struct strbuf *acc_buffer;\n+\n+#define SLOP\t\t\t5\n+\n+#define INDEX_ENTRY_SIZE\t\t(\\\n+\t20 +\t\t\t\t\t\t\\\n+\t1 +\t\t\t\t\t\t\t\\\n+\t4\t\t\t\t\t\t\t\\\n+)\n+\n+#define OBJECT_ENTRY_SIZE\t(\\\n+\t1 +\t\t\t\t\t\t\\\n+\t20 +\t\t\t\t\t\\\n+\t1 +\t\t\t\t\t\t\\\n+\t1 +\t\t\t\t\t\t\\\n+\t1 +\t\t\t\t\t\t\\\n+\t4 +\t\t\t\t\t\t\\\n+\t2\t\t\t\t\t\t\\\n+)\n+\n+#define SLICE_HEADER_SIZE\t\t(\\\n+\t8 +\t\t\t\t\t\t\t\\\n+\t1 +\t\t\t\t\t\t\t\\\n+\t4 +\t\t\t\t\t\t\t\\\n+\t4 +\t\t\t\t\t\t\t\\\n+\t2 +\t\t\t\t\t\t\t\\\n+\t4 +\t\t\t\t\t\t\t\\\n+\t20\t\t\t\t\t\t\t\\\n+)\n+\n+#define INDEX_HEADER_SIZE\t\t(\\\n+\t8 +\t\t\t\t\t\t\t\\\n+\t1 +\t\t\t\t\t\t\t\\\n+\t4 +\t\t\t\t\t\t\t\\\n+\t4 +\t\t\t\t\t\t\t\\\n+\t1 +\t\t\t\t\t\t\t\\\n+\t4\t\t\t\t\t\t\t\\\n+)\n+\n+/* initialization */\n+\n+#define UNPACK_UINT32(p)\t\t((uint32_t)*(p) << 24 | (uint32_t)*((p) + 1) << 16 | \\\n+\t\t\t\t\t\t\t\t\t(uint32_t)*((p) + 2) << 8 | (uint32_t)*((p) + 3))\n+\n+#define PACK_UINT32(p, n)\t\tdo {\t\t\\\n+\t*(p) = (unsigned char)((n) >> 24);\t\t\t\\\n+\t*((p) + 1) = (unsigned char)((n) >> 16);\t\\\n+\t*((p) + 2) = (unsigned char)((n) >> 8);\t\t\\\n+\t*((p) + 3) = (unsigned char)(n);\t\t\t\\\n+} while (0)\n+\n+#define UNPACK_UINT16(p)\t\t((uint16_t)*(p) << 8 | (uint16_t)*((p) + 1))\n+\n+#define PACK_UINT16(p, n)\t\tdo {\t\t\\\n+\t*(p) = (unsigned char)((n) >> 8);\t\t\t\\\n+\t*((p) + 1) = (unsigned char)(n);\t\t\t\\\n+} while (0)\n+\n+struct rc_index_entry *from_disked_rc_index_entry(unsigned char *src, struct rc_index_entry *dst)\n+{\n+\tstatic struct rc_index_entry entry[4];\n+\tstatic int cur;\n+\n+\tif (!dst)\n+\t\tdst = &entry[cur++ & 0x3];\n+\n+\tdst->sha1 = (unsigned char *)src;\n+\tdst->is_start = !!(src[20] & 0x80);\n+\tdst->cache_index = src[20] & 0x7f;\n+\tdst->pos = UNPACK_UINT32(src + 21);\n+\n+\treturn dst;\n+}\n+\n+unsigned char *to_disked_rc_index_entry(struct rc_index_entry *src, unsigned char **dstp)\n+{\n+\tstatic unsigned char entry[4][INDEX_ENTRY_SIZE];\n+\tstatic int cur;\n+\tunsigned char *dst = *dstp;\n+\n+\tif (!dstp || !*dstp) {\n+\t\tdst = entry[cur++ & 0x3];\n+\n+\t\tif (dstp)\n+\t\t\t*dstp = dst;\n+\t} else\n+\t\tdst = *dstp;\n+\n+\tif (dst != src->sha1)\n+\t\thashcpy(dst, src->sha1);\n+\tdst[20] = (unsigned char)src->is_start << 7 | (unsigned char)src->cache_index;\n+\tPACK_UINT32(dst + 21, src->pos);\n+\n+\treturn dst;\n+}\n+\n+struct rc_object_entry *from_disked_rc_object_entry(unsigned char *src, struct rc_object_entry *dst)\n+{\n+\tstatic struct rc_object_entry entry[4];\n+\tstatic int cur;\n+\n+\tif (!dst)\n+\t\tdst = &entry[cur++ & 0x3];\n+\n+\tdst->type = *src >> 5;\n+\tdst->is_end = !!(*src & 0x10);\n+\tdst->is_start = !!(*src & 0x08);\n+\tdst->flag = *src & 0x07;\n+\n+\tdst->sha1 = (unsigned char *)(src + 1);\n+\tdst->merge_nr = *(src + 21);\n+\tdst->split_nr = *(src + 22);\n+\n+\tdst->size_size = *(src + 23) >> 5;\n+\tdst->padding = *(src + 23) & 0x1f;\n+\n+\tdst->date = UNPACK_UINT32(src + 24);\n+\tdst->path = UNPACK_UINT16(src + 28);\n+\n+\treturn dst;\n+}\n+\n+unsigned char *to_disked_rc_object_entry(struct rc_object_entry *src, unsigned char **dstp)\n+{\n+\tstatic unsigned char entry[4][OBJECT_ENTRY_SIZE];\n+\tstatic int cur;\n+\tunsigned char *dst;\n+\n+\tif (!dstp || !*dstp) {\n+\t\tdst = entry[cur++ & 0x3];\n+\n+\t\tif (dstp)\n+\t\t\t*dstp = dst;\n+\t} else\n+\t\tdst = *dstp;\n+\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->flag;\n+\n+\tif (dst + 1 != src->sha1)\n+\t\thashcpy(dst + 1, src->sha1);\n+\t*(dst + 21) = src->merge_nr;\n+\t*(dst + 22) = src->split_nr;\n+\n+\t*(dst + 23)  = (unsigned char)src->size_size << 5;\n+\t*(dst + 23) |= (unsigned char)src->padding;\n+\n+\tPACK_UINT32(dst + 24, src->date);\n+\tPACK_UINT16(dst + 28, src->path);\n+\n+\treturn dst;\n+}\n+\n+static int get_index_head(unsigned char *map, int len, struct rc_index_header *head, uint32_t *fanout, unsigned char **caches)\n+{\n+\tint i, index = INDEX_HEADER_SIZE;\n+\n+\tif (memcmp(map, \"REVINDEX\", 8) || *(map + 8) != SUPPORTED_REVINDEX_VERSION)\n+\t\treturn -1;\n+\n+\tmemcpy(head->signature, \"REVINDEX\", 8);\n+\thead->version = *(map + 8);\n+\thead->ofs_objects = UNPACK_UINT32(map + 9);\n+\thead->object_nr = UNPACK_UINT32(map + 13);\n+\thead->cache_nr = *(map + 17);\n+\thead->max_date = UNPACK_UINT32(map + 18);\n+\n+\tif (len < index + head->cache_nr * 20 + 0x100 * sizeof(uint32_t))\n+\t\treturn -2;\n+\n+\t*caches = xmalloc(head->cache_nr * 20);\n+\tmemcpy(*caches, map + index, head->cache_nr * 20);\n+\tindex += head->cache_nr * 20;\n+\n+\tmemcpy(fanout, map + index, 0x100 * sizeof(uint32_t));\n+\tfor (i = 0; i <= 0xff; i++)\n+\t\tfanout[i] = ntohl(fanout[i]);\n+\tfanout[0x100] = len;\n+\n+\treturn 0;\n+}\n+\n+/* added in init_index */\n+static void cleanup_cache_slices(void)\n+{\n+\tif (idx_map) {\n+\t\tfree(idx_caches);\n+\t\tmunmap(idx_map, idx_size);\n+\t\tidx_map = 0;\n+\t}\n+\n+}\n+\n+static int init_index(void)\n+{\n+\tint fd;\n+\tstruct stat fi;\n+\n+\tfd = open(git_path(\"rev-cache/index\"), O_RDONLY);\n+\tif (fd == -1 || fstat(fd, &fi))\n+\t\tgoto end;\n+\tif (fi.st_size < INDEX_HEADER_SIZE)\n+\t\tgoto end;\n+\n+\tidx_size = fi.st_size;\n+\tidx_map = xmmap(0, idx_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tclose(fd);\n+\tif (idx_map == MAP_FAILED)\n+\t\tgoto end;\n+\tif (get_index_head(idx_map, fi.st_size, &idx_head, fanout, &idx_caches))\n+\t\tgoto end;\n+\n+\tatexit(cleanup_cache_slices);\n+\n+\treturn 0;\n+\n+end:\n+\tidx_map = 0;\n+\tno_idx = 1;\n+\treturn -1;\n+}\n+\n+/* this assumes index is already loaded */\n+static unsigned char *search_index_1(unsigned char *sha1)\n+{\n+\tint start, end, starti, endi, i, len, r;\n+\tunsigned char *iep;\n+\n+\tif (!idx_map)\n+\t\treturn 0;\n+\n+\t/* binary search */\n+\tstart = fanout[(int)sha1[0]];\n+\tend = fanout[(int)sha1[0] + 1];\n+\tlen = (end - start) / INDEX_ENTRY_SIZE;\n+\tif (!len || len * INDEX_ENTRY_SIZE != end - start)\n+\t\treturn 0;\n+\n+\tstarti = 0;\n+\tendi = len - 1;\n+\tfor (;;) {\n+\t\ti = (endi + starti) / 2;\n+\t\tiep = idx_map + start + i * INDEX_ENTRY_SIZE;\n+\t\tr = hashcmp(sha1, iep);\n+\n+\t\tif (r) {\n+\t\t\tif (starti + 1 == endi) {\n+\t\t\t\tstarti++;\n+\t\t\t\tcontinue;\n+\t\t\t} else if (starti == endi)\n+\t\t\t\tbreak;\n+\n+\t\t\tif (r > 0)\n+\t\t\t\tstarti = i;\n+\t\t\telse /* r < 0 */\n+\t\t\t\tendi = i;\n+\t\t} else\n+\t\t\treturn iep;\n+\t}\n+\n+\treturn 0;\n+}\n+\n+static struct rc_index_entry *search_index(unsigned char *sha1)\n+{\n+\tunsigned char *ied = search_index_1(sha1);\n+\n+\tif (ied)\n+\t\treturn from_disked_rc_index_entry(ied, 0);\n+\n+\treturn 0;\n+}\n+\n+unsigned char *get_cache_slice(struct commit *commit)\n+{\n+\tstruct rc_index_entry *ie;\n+\n+\tif (!idx_map) {\n+\t\tif (no_idx)\n+\t\t\treturn 0;\n+\t\tinit_index();\n+\t}\n+\n+\tif (commit->date > idx_head.max_date)\n+\t\treturn 0;\n+\n+\tie = search_index(commit->object.sha1);\n+\tif (ie && ie->cache_index < idx_head.cache_nr)\n+\t\treturn idx_caches + ie->cache_index * 20;\n+\n+\treturn 0;\n+}\n+\n+\n+/* traversal */\n+\n+struct entrance_point {\n+\tint pos;\n+\tchar uninteresting;\n+};\n+\n+static int eps_sort_callback(const void *a, const void *b)\n+{\n+\tstruct entrance_point *aep, *bep;\n+\n+\taep = (struct entrance_point *)a;\n+\tbep = (struct entrance_point *)b;\n+\n+\tif (aep->pos == bep->pos)\n+\t\treturn 0;\n+\n+\treturn aep->pos > bep->pos ? 1 : -1;\n+}\n+\n+static int setup_traversal(struct rc_slice_header *head, struct entrance_point **peps, int *peplen,\n+\tstruct commit *commit, struct commit_list **work)\n+{\n+\tstruct rc_index_entry *iep;\n+\tstruct commit_list *prev, *wp, **wpp;\n+\tstruct entrance_point *eps;\n+\tint retval, curep = 1, eplen = 10;\n+\n+\teps = xcalloc(1, eplen * sizeof(struct entrance_point));\n+\tiep = search_index(commit->object.sha1);\n+\n+\t/* the .uniniteresting bit isn't strictly necessary, as we check the object during traversal as well,\n+\t * but we might as well initialize it while we're at it */\n+\teps[0].pos = iep->pos;\n+\teps[0].uninteresting = !!(commit->object.flags & UNINTERESTING);\n+\tretval = iep->pos;\n+\n+\t/* include any others in the work array */\n+\tprev = 0;\n+\twpp = work;\n+\twp = *work;\n+\twhile (wp) {\n+\t\tstruct object *obj = &wp->item->object;\n+\t\tstruct commit *co;\n+\n+\t\t/* is this in our cache slice? */\n+\t\tiep = search_index(obj->sha1);\n+\t\tif (!iep || hashcmp(idx_caches + iep->cache_index * 20, head->sha1)) {\n+\t\t\tprev = wp;\n+\t\t\twp = wp->next;\n+\t\t\twpp = &wp;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tif (iep->pos < retval)\n+\t\t\tretval = iep->pos;\n+\n+\t\t/* mark this for later */\n+\t\tif (curep == eplen) {\n+\t\t\teplen += 10;\n+\t\t\teps = xrealloc(eps, eplen * sizeof(struct entrance_point));\n+\t\t}\n+\n+\t\teps[curep].pos = iep->pos;\n+\t\teps[curep].uninteresting = !!(obj->flags & UNINTERESTING);\n+\t\tcurep++;\n+\n+\t\t/* remove from work list */\n+\t\tco = pop_commit(wpp);\n+\t\twp = *wpp;\n+\t\tif (prev)\n+\t\t\tprev->next = wp;\n+\t}\n+\n+\tqsort(eps, curep, sizeof(struct entrance_point), eps_sort_callback);\n+\t*peps = eps;\n+\t*peplen = curep;\n+\treturn retval;\n+}\n+\n+#define IPATH\t\t\t\t0x40\n+#define UPATH\t\t\t\t0x80\n+\n+#define GET_COUNT(x)\t\t((x) & 0x3f)\n+#define SET_COUNT(x, s)\t\t((x) = ((x) & ~0x3f) | ((s) & 0x3f))\n+\n+static int traverse_cache_slice_1(struct rc_slice_header *head, unsigned char *map,\n+\tstruct rev_info *revs, struct commit *commit,\n+\tunsigned long *date_so_far, int *slop_so_far,\n+\tstruct commit_list ***queue, struct commit_list **work)\n+{\n+\tstruct commit_list *insert_cache = 0;\n+\tstruct commit **last_objects, *co;\n+\tint i, total_path_nr = head->path_nr, retval = -1;\n+\tchar consume_children = 0;\n+\tunsigned char *paths;\n+\tstruct entrance_point *eps;\n+\tint eplen, curep = 0;\n+\n+\ti = setup_traversal(head, &eps, &eplen, commit, work);\n+\tif (i < 0)\n+\t\treturn -1;\n+\n+\tpaths = xcalloc(total_path_nr, sizeof(uint16_t));\n+\tlast_objects = xcalloc(total_path_nr, sizeof(struct commit *));\n+\n+\t/* i already set */\n+\twhile (i < head->size) {\n+\t\tstruct rc_object_entry *entry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n+\t\tint path = entry->path;\n+\t\tstruct object *obj;\n+\t\tint index = i;\n+\t\tchar uninteresting;\n+\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\t\tcontinue;\n+\t\telse\n+\t\t\tconsume_children = 0;\n+\n+\t\tif (path >= total_path_nr)\n+\t\t\tgoto end;\n+\n+\t\t/* in one of our branches?\n+\t\t * uninteresting trumps interesting */\n+\t\tif (curep < eplen && index == eps[curep].pos)\n+\t\t\tpaths[path] |= eps[curep++].uninteresting ? UPATH : IPATH;\n+\t\telse if (!paths[path])\n+\t\t\tcontinue;\n+\n+\t\t/* date stuff */\n+\t\tif (revs->max_age != -1 && entry->date < revs->max_age)\n+\t\t\tpaths[path] |= UPATH;\n+\n+\t\t/* lookup object */\n+\t\tco = lookup_commit(entry->sha1);\n+\t\tobj = &co->object;\n+\n+\t\tif (obj->flags & UNINTERESTING)\n+\t\t\tpaths[path] |= UPATH;\n+\n+\t\tif ((paths[path] & IPATH) && (paths[path] & UPATH)) {\n+\t\t\tpaths[path] = UPATH;\n+\n+\t\t\t/* mark edge */\n+\t\t\tif (last_objects[path]) {\n+\t\t\t\tparse_commit(last_objects[path]);\n+\n+\t\t\t\tlast_objects[path]->object.flags &= ~FACE_VALUE;\n+\t\t\t\tlast_objects[path] = 0;\n+\t\t\t}\n+\t\t}\n+\n+\t\t/* now we gotta re-assess the whole interesting thing... */\n+\t\tuninteresting = !!(paths[path] & UPATH);\n+\n+\t\t/* first close paths */\n+\t\tif (entry->split_nr) {\n+\t\t\tint j, off = index + OBJECT_ENTRY_SIZE + RC_PATH_SIZE(entry->merge_nr);\n+\n+\t\t\tfor (j = 0; j < entry->split_nr; j++) {\n+\t\t\t\tunsigned short p = ntohs(*(uint16_t *)(map + off + RC_PATH_SIZE(j)));\n+\n+\t\t\t\tif (p >= total_path_nr)\n+\t\t\t\t\tgoto end;\n+\n+\t\t\t\t/* boundary commit? */\n+\t\t\t\tif ((paths[p] & IPATH) && uninteresting) {\n+\t\t\t\t\tif (last_objects[p]) {\n+\t\t\t\t\t\tparse_commit(last_objects[p]);\n+\n+\t\t\t\t\t\tlast_objects[p]->object.flags &= ~FACE_VALUE;\n+\t\t\t\t\t\tlast_objects[p] = 0;\n+\t\t\t\t\t}\n+\t\t\t\t} else if (last_objects[p] && !last_objects[p]->object.parsed)\n+\t\t\t\t\tcommit_list_insert(co, &last_objects[p]->parents);\n+\n+\t\t\t\t/* can't close a merge path until all are parents have been encountered */\n+\t\t\t\tif (GET_COUNT(paths[p])) {\n+\t\t\t\t\tSET_COUNT(paths[p], GET_COUNT(paths[p]) - 1);\n+\n+\t\t\t\t\tif (GET_COUNT(paths[p]))\n+\t\t\t\t\t\tcontinue;\n+\t\t\t\t}\n+\n+\t\t\t\tpaths[p] = 0;\n+\t\t\t\tlast_objects[p] = 0;\n+\t\t\t}\n+\t\t}\n+\n+\t\t/* make topo relations */\n+\t\tif (last_objects[path] && !last_objects[path]->object.parsed)\n+\t\t\tcommit_list_insert(co, &last_objects[path]->parents);\n+\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} else\n+\t\t\tparse_commit(co);\n+\n+\t\tobj->flags |= SEEN;\n+\n+\t\tif (uninteresting)\n+\t\t\tobj->flags |= UNINTERESTING;\n+\n+\t\t/* we need to know what the edges are */\n+\t\tlast_objects[path] = co;\n+\n+\t\t/* add to list */\n+\t\tif (!(obj->flags & UNINTERESTING) || revs->show_all) {\n+\t\t\tif (entry->is_end)\n+\t\t\t\tinsert_by_date_cached(co, work, insert_cache, &insert_cache);\n+\t\t\telse\n+\t\t\t\t*queue = &commit_list_insert(co, *queue)->next;\n+\n+\t\t\t/* add children to list as well */\n+\t\t\tif (obj->flags & UNINTERESTING)\n+\t\t\t\tconsume_children = 0;\n+\t\t\telse\n+\t\t\t\tconsume_children = 1;\n+\t\t}\n+\n+\t\t/* open parents */\n+\t\tif (entry->merge_nr) {\n+\t\t\tint j, off = index + OBJECT_ENTRY_SIZE;\n+\t\t\tchar flag = uninteresting ? UPATH : IPATH;\n+\n+\t\t\tfor (j = 0; j < entry->merge_nr; j++) {\n+\t\t\t\tunsigned short p = ntohs(*(uint16_t *)(map + off + RC_PATH_SIZE(j)));\n+\n+\t\t\t\tif (p >= total_path_nr)\n+\t\t\t\t\tgoto end;\n+\n+\t\t\t\tif (paths[p] & flag)\n+\t\t\t\t\tcontinue;\n+\n+\t\t\t\tpaths[p] |= flag;\n+\t\t\t}\n+\n+\t\t\t/* make sure we don't use this path before all our parents have had their say */\n+\t\t\tSET_COUNT(paths[path], entry->merge_nr);\n+\t\t}\n+\n+\t}\n+\n+\tretval = 0;\n+\n+end:\n+\tfree(paths);\n+\tfree(last_objects);\n+\tfree(eps);\n+\n+\treturn retval;\n+}\n+\n+static int get_cache_slice_header(unsigned char *cache_sha1, unsigned char *map, int len, struct rc_slice_header *head)\n+{\n+\tint t;\n+\n+\tmemcpy(head->signature, map, 8);\n+\thead->version = *(map + 8);\n+\thead->ofs_objects = UNPACK_UINT32(map + 9);\n+\n+\thead->object_nr = UNPACK_UINT32(map + 13);\n+\thead->path_nr = UNPACK_UINT16(map + 17);\n+\thead->size = UNPACK_UINT32(map + 19);\n+\n+\thashcpy(head->sha1, map + 23);\n+\n+\tif (memcmp(head->signature, \"REVCACHE\", 8))\n+\t\treturn -1;\n+\tif (head->version != SUPPORTED_REVCACHE_VERSION)\n+\t\treturn -2;\n+\tif (hashcmp(head->sha1, cache_sha1))\n+\t\treturn -3;\n+\tt = SLICE_HEADER_SIZE;\n+\tif (t != head->ofs_objects || t >= len)\n+\t\treturn -4;\n+\n+\thead->size = len;\n+\n+\treturn 0;\n+}\n+\n+int traverse_cache_slice(struct rev_info *revs,\n+\tunsigned char *cache_sha1, struct commit *commit,\n+\tunsigned long *date_so_far, int *slop_so_far,\n+\tstruct commit_list ***queue, struct commit_list **work)\n+{\n+\tint fd = -1, retval = -3;\n+\tstruct stat fi;\n+\tstruct rc_slice_header head;\n+\tstruct rev_cache_info *rci;\n+\tunsigned char *map = MAP_FAILED;\n+\n+\t/* the index should've been loaded already to find cache_sha1, but it's good\n+\t * to be absolutely sure... */\n+\tif (!idx_map)\n+\t\tinit_index();\n+\tif (!idx_map)\n+\t\treturn -1;\n+\n+\t/* load options */\n+\trci = &revs->rev_cache_info;\n+\n+\tmemset(&head, 0, sizeof(struct rc_slice_header));\n+\n+\tfd = open(git_path(\"rev-cache/%s\", sha1_to_hex(cache_sha1)), O_RDONLY);\n+\tif (fd == -1)\n+\t\tgoto end;\n+\tif (fstat(fd, &fi) || fi.st_size < SLICE_HEADER_SIZE)\n+\t\tgoto end;\n+\n+\tmap = xmmap(0, fi.st_size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tif (map == MAP_FAILED)\n+\t\tgoto end;\n+\tif (get_cache_slice_header(cache_sha1, map, fi.st_size, &head))\n+\t\tgoto end;\n+\n+\tretval = traverse_cache_slice_1(&head, map, revs, commit, date_so_far, slop_so_far, queue, work);\n+\n+end:\n+\tif (map != MAP_FAILED)\n+\t\tmunmap(map, fi.st_size);\n+\tif (fd != -1)\n+\t\tclose(fd);\n+\n+\treturn retval;\n+}\n+\n+\n+\n+/* generation */\n+\n+struct path_track {\n+\tstruct commit *commit;\n+\tint path; /* for keeping track of children */\n+\n+\tstruct path_track *next, *prev;\n+};\n+\n+static unsigned char *paths;\n+static int path_nr = 1, path_sz;\n+\n+static struct path_track *path_track;\n+static struct path_track *path_track_alloc;\n+\n+#define PATH_IN_USE\t\t\t0x80 /* biggest bit we can get as a char */\n+\n+static int get_new_path(void)\n+{\n+\tint i;\n+\n+\tfor (i = 1; i < path_nr; i++)\n+\t\tif (!paths[i])\n+\t\t\tbreak;\n+\n+\tif (i == path_nr) {\n+\t\tif (path_nr >= path_sz) {\n+\t\t\tpath_sz += 50;\n+\t\t\tpaths = xrealloc(paths, path_sz);\n+\t\t\tmemset(paths + path_sz - 50, 0, 50);\n+\t\t}\n+\t\tpath_nr++;\n+\t}\n+\n+\tpaths[i] = PATH_IN_USE;\n+\treturn i;\n+}\n+\n+static void remove_path_track(struct path_track **ppt, char total_free)\n+{\n+\tstruct path_track *t = *ppt;\n+\n+\tif (t->next)\n+\t\tt->next->prev = t->prev;\n+\tif (t->prev)\n+\t\tt->prev->next = t->next;\n+\n+\tt = t->next;\n+\n+\tif (total_free)\n+\t\tfree(*ppt);\n+\telse {\n+\t\t(*ppt)->next = path_track_alloc;\n+\t\tpath_track_alloc = *ppt;\n+\t}\n+\n+\t*ppt = t;\n+}\n+\n+static struct path_track *make_path_track(struct path_track **head, struct commit *commit)\n+{\n+\tstruct path_track *pt;\n+\n+\tif (path_track_alloc) {\n+\t\tpt = path_track_alloc;\n+\t\tpath_track_alloc = pt->next;\n+\t} else\n+\t\tpt = xmalloc(sizeof(struct path_track));\n+\n+\tmemset(pt, 0, sizeof(struct path_track));\n+\tpt->commit = commit;\n+\n+\tpt->next = *head;\n+\tif (*head)\n+\t\t(*head)->prev = pt;\n+\t*head = pt;\n+\n+\treturn pt;\n+}\n+\n+static void add_path_to_track(struct commit *commit, int path)\n+{\n+\tmake_path_track(&path_track, commit);\n+\tpath_track->path = path;\n+}\n+\n+static void handle_paths(struct commit *commit, struct rc_object_entry *object, struct strbuf *merge_str, struct strbuf *split_str)\n+{\n+\tint child_nr, parent_nr, open_parent_nr, this_path;\n+\tstruct commit_list *list;\n+\tstruct commit *first_parent;\n+\tstruct path_track **ppt, *pt;\n+\n+\t/* we can only re-use a closed path once all it's children have been encountered,\n+\t * as we need to keep track of commit boundaries */\n+\tppt = &path_track;\n+\tpt = *ppt;\n+\tchild_nr = 0;\n+\twhile (pt) {\n+\t\tif (pt->commit == commit) {\n+\t\t\tuint16_t write_path;\n+\n+\t\t\tif (paths[pt->path] != PATH_IN_USE)\n+\t\t\t\tpaths[pt->path]--;\n+\n+\t\t\t/* make sure we can handle this */\n+\t\t\tchild_nr++;\n+\t\t\tif (child_nr > 0x7f)\n+\t\t\t\tdie(\"%s: too many branches!  rev-cache can only handle %d parents/children per commit\",\n+\t\t\t\t\tsha1_to_hex(object->sha1), 0x7f);\n+\n+\t\t\t/* add to split list */\n+\t\t\tobject->split_nr++;\n+\t\t\twrite_path = htons((uint16_t)pt->path);\n+\t\t\tstrbuf_add(split_str, &write_path, sizeof(uint16_t));\n+\n+\t\t\tremove_path_track(ppt, 0);\n+\t\t\tpt = *ppt;\n+\t\t} else {\n+\t\t\tpt = pt->next;\n+\t\t\tppt = &pt;\n+\t\t}\n+\t}\n+\n+\t/* initialize our self! */\n+\tif (!commit->indegree) {\n+\t\tcommit->indegree = get_new_path();\n+\t\tobject->is_start = 1;\n+\t}\n+\n+\tthis_path = commit->indegree;\n+\tpaths[this_path] = PATH_IN_USE;\n+\tobject->path = this_path;\n+\n+\t/* count interesting parents */\n+\tparent_nr = open_parent_nr = 0;\n+\tfirst_parent = 0;\n+\tfor (list = commit->parents; list; list = list->next) {\n+\t\tif (list->item->object.flags & UNINTERESTING) {\n+\t\t\tobject->is_end = 1;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tparent_nr++;\n+\t\tif (!list->item->indegree)\n+\t\t\topen_parent_nr++;\n+\t\tif (!first_parent)\n+\t\t\tfirst_parent = list->item;\n+\t}\n+\n+\tif (!parent_nr)\n+\t\treturn;\n+\n+\tif (parent_nr == 1 && open_parent_nr == 1) {\n+\t\tfirst_parent->indegree = this_path;\n+\t\treturn;\n+\t}\n+\n+\t/* bail out on obscene parent/child #s */\n+\tif (parent_nr > 0x7f)\n+\t\tdie(\"%s: too many parents in merge!  rev-cache can only handle %d parents/children per commit\",\n+\t\t\tsha1_to_hex(object->sha1), 0x7f);\n+\n+\t/* make merge list */\n+\tobject->merge_nr = parent_nr;\n+\tpaths[this_path] = parent_nr;\n+\n+\tfor (list = commit->parents; list; list = list->next) {\n+\t\tstruct commit *p = list->item;\n+\t\tuint16_t write_path;\n+\n+\t\tif (p->object.flags & UNINTERESTING)\n+\t\t\tcontinue;\n+\n+\t\t/* unfortunately due to boundary tracking we can't re-use merge paths\n+\t\t * (unable to guarantee last parent path = this -> last won't always be able to\n+\t\t * set this as a boundary object */\n+\t\tif (!p->indegree)\n+\t\t\tp->indegree = get_new_path();\n+\n+\t\twrite_path = htons((uint16_t)p->indegree);\n+\t\tstrbuf_add(merge_str, &write_path, sizeof(uint16_t));\n+\n+\t\t/* make sure path is properly ended */\n+\t\tadd_path_to_track(p, this_path);\n+\t}\n+\n+}\n+\n+\n+static void add_object_entry(const unsigned char *sha1, int type, struct rc_object_entry *nothisone,\n+\tstruct strbuf *merge_str, struct strbuf *split_str)\n+{\n+\tstruct rc_object_entry object;\n+\n+\tif (!nothisone) {\n+\t\tmemset(&object, 0, sizeof(object));\n+\t\tobject.sha1 = (unsigned char *)sha1;\n+\t\tobject.type = type;\n+\n+\t\tif (merge_str)\n+\t\t\tobject.merge_nr = merge_str->len / sizeof(uint16_t);\n+\t\tif (split_str)\n+\t\t\tobject.split_nr = split_str->len / sizeof(uint16_t);\n+\n+\t\tnothisone = &object;\n+\t}\n+\n+\tstrbuf_add(acc_buffer, to_disked_rc_object_entry(nothisone, 0), OBJECT_ENTRY_SIZE);\n+\n+\tif (merge_str && merge_str->len)\n+\t\tstrbuf_add(acc_buffer, merge_str->buf, merge_str->len);\n+\tif (split_str && split_str->len)\n+\t\tstrbuf_add(acc_buffer, split_str->buf, split_str->len);\n+\n+}\n+\n+static void init_revcache_directory(void)\n+{\n+\tstruct stat fi;\n+\n+\tif (stat(git_path(\"rev-cache\"), &fi) || !S_ISDIR(fi.st_mode))\n+\t\tif (mkdir(git_path(\"rev-cache\"), 0777))\n+\t\t\tdie(\"can't make rev-cache directory\");\n+\n+}\n+\n+void init_rev_cache_info(struct rev_cache_info *rci)\n+{\n+\trci->objects = 1;\n+\trci->legs = 0;\n+\trci->make_index = 1;\n+\n+\trci->add_to_pending = 1;\n+\n+\trci->ignore_size = 0;\n+}\n+\n+void maybe_fill_with_defaults(struct rev_cache_info *rci)\n+{\n+\tstatic struct rev_cache_info def_rci;\n+\n+\tif (rci)\n+\t\treturn;\n+\n+\tinit_rev_cache_info(&def_rci);\n+\trci = &def_rci;\n+}\n+\n+int make_cache_slice(struct rev_cache_info *rci,\n+\tstruct rev_info *revs, struct commit_list **starts, struct commit_list **ends,\n+\tunsigned char *cache_sha1)\n+{\n+\tstruct rev_info therevs;\n+\tstruct strbuf buffer, startlist, endlist;\n+\tstruct rc_slice_header head;\n+\tstruct commit *commit;\n+\tunsigned char sha1[20], whead[SLICE_HEADER_SIZE];\n+\tstruct strbuf merge_paths, split_paths;\n+\tint object_nr, total_sz, fd;\n+\tchar file[PATH_MAX], *newfile;\n+\tstruct rev_cache_info *trci;\n+\tgit_SHA_CTX ctx;\n+\n+\tmaybe_fill_with_defaults(rci);\n+\n+\tinit_revcache_directory();\n+\tstrcpy(file, git_path(\"rev-cache/XXXXXX\"));\n+\tfd = xmkstemp(file);\n+\n+\tstrbuf_init(&buffer, 0);\n+\tstrbuf_init(&startlist, 0);\n+\tstrbuf_init(&endlist, 0);\n+\tstrbuf_init(&merge_paths, 0);\n+\tstrbuf_init(&split_paths, 0);\n+\tacc_buffer = &buffer;\n+\n+\tif (!revs) {\n+\t\trevs = &therevs;\n+\t\tinit_revisions(revs, 0);\n+\n+\t\t/* we're gonna assume no one else has already traversed this... */\n+\t\twhile ((commit = pop_commit(starts)))\n+\t\t\tadd_pending_object(revs, &commit->object, 0);\n+\n+\t\twhile ((commit = pop_commit(ends))) {\n+\t\t\tcommit->object.flags |= UNINTERESTING;\n+\t\t\tadd_pending_object(revs, &commit->object, 0);\n+\t\t}\n+\t}\n+\n+\t/* write head placeholder */\n+\tmemset(&head, 0, sizeof(head));\n+\tmemset(&whead, 0, SLICE_HEADER_SIZE);\n+\thead.ofs_objects = SLICE_HEADER_SIZE;\n+\txwrite(fd, &whead, SLICE_HEADER_SIZE);\n+\n+\t/* init revisions! */\n+\trevs->tree_objects = 1;\n+\trevs->blob_objects = 1;\n+\trevs->topo_order = 1;\n+\trevs->lifo = 1;\n+\n+\t/* re-use info from other caches if possible */\n+\ttrci = &revs->rev_cache_info;\n+\tinit_rev_cache_info(trci);\n+\ttrci->add_to_pending = 0;\n+\n+\tsetup_revisions(0, 0, revs, 0);\n+\tif (prepare_revision_walk(revs))\n+\t\tdie(\"died preparing revision walk\");\n+\n+\tobject_nr = total_sz = 0;\n+\twhile ((commit = get_revision(revs)) != 0) {\n+\t\tstruct rc_object_entry object;\n+\n+\t\tstrbuf_setlen(&merge_paths, 0);\n+\t\tstrbuf_setlen(&split_paths, 0);\n+\n+\t\tmemset(&object, 0, sizeof(object));\n+\t\tobject.type = OBJ_COMMIT;\n+\t\tobject.date = commit->date;\n+\t\tobject.sha1 = commit->object.sha1;\n+\n+\t\thandle_paths(commit, &object, &merge_paths, &split_paths);\n+\n+\t\tif (object.is_end) {\n+\t\t\tstrbuf_add(&endlist, object.sha1, 20);\n+\t\t\tif (ends)\n+\t\t\t\tcommit_list_insert(commit, ends);\n+\t\t}\n+\t\t/* the two *aren't* mutually exclusive */\n+\t\tif (object.is_start) {\n+\t\t\tstrbuf_add(&startlist, object.sha1, 20);\n+\t\t\tif (starts)\n+\t\t\t\tcommit_list_insert(commit, starts);\n+\t\t}\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/* print every ~1MB or so */\n+\t\tif (buffer.len > 1000000) {\n+\t\t\twrite_in_full(fd, buffer.buf, buffer.len);\n+\t\t\ttotal_sz += buffer.len;\n+\n+\t\t\tstrbuf_setlen(&buffer, 0);\n+\t\t}\n+\t}\n+\n+\tif (buffer.len) {\n+\t\twrite_in_full(fd, buffer.buf, buffer.len);\n+\t\ttotal_sz += buffer.len;\n+\t}\n+\n+\t/* go ahead a free some stuff... */\n+\tstrbuf_release(&buffer);\n+\tstrbuf_release(&merge_paths);\n+\tstrbuf_release(&split_paths);\n+\tif (path_sz)\n+\t\tfree(paths);\n+\twhile (path_track_alloc)\n+\t\tremove_path_track(&path_track_alloc, 1);\n+\n+\t/* the meaning of the hash name is more or less irrelevant, it's the uniqueness that matters */\n+\tstrbuf_add(&endlist, startlist.buf, startlist.len);\n+\tgit_SHA1_Init(&ctx);\n+\tgit_SHA1_Update(&ctx, endlist.buf, endlist.len);\n+\tgit_SHA1_Final(sha1, &ctx);\n+\n+\t/* initialize header */\n+\tstrcpy(head.signature, \"REVCACHE\");\n+\thead.version = SUPPORTED_REVCACHE_VERSION;\n+\n+\thead.object_nr = object_nr;\n+\thead.size = head.ofs_objects + total_sz;\n+\thead.path_nr = path_nr;\n+\thashcpy(head.sha1, sha1);\n+\n+\t/* ...and whead */\n+\tmemcpy(whead, \"REVCACHE\", 8);\n+\t*(whead + 8) = head.version;\n+\tPACK_UINT32(whead + 9, head.ofs_objects);\n+\n+\tPACK_UINT32(whead + 13, head.object_nr);\n+\tPACK_UINT16(whead + 17, head.path_nr);\n+\n+\tPACK_UINT32(whead + 19, head.size);\n+\thashcpy(whead + 23, head.sha1);\n+\n+\t/* some info! */\n+\tfprintf(stderr, \"objects: %d\\n\", object_nr);\n+\tfprintf(stderr, \"paths: %d\\n\", path_nr);\n+\n+\tlseek(fd, 0, SEEK_SET);\n+\txwrite(fd, &whead, SLICE_HEADER_SIZE);\n+\n+\tif (rci->make_index && make_cache_index(rci, sha1, fd, head.size) < 0)\n+\t\tdie(\"can't update index\");\n+\n+\tclose(fd);\n+\n+\tnewfile = git_path(\"rev-cache/%s\", sha1_to_hex(sha1));\n+\tif (rename(file, newfile))\n+\t\tdie(\"can't move temp file\");\n+\n+\t/* let our caller know what we've just made */\n+\tif (cache_sha1)\n+\t\thashcpy(cache_sha1, sha1);\n+\n+\tstrbuf_release(&endlist);\n+\tstrbuf_release(&startlist);\n+\n+\treturn 0;\n+}\n+\n+\n+static int index_sort_hash(const void *a, const void *b)\n+{\n+\treturn hashcmp(((struct rc_index_entry_ondisk *)a)->sha1, ((struct rc_index_entry_ondisk *)b)->sha1);\n+}\n+\n+static int write_cache_index(struct strbuf *body)\n+{\n+\tunsigned char whead[INDEX_HEADER_SIZE];\n+\tstruct lock_file *lk;\n+\tint fd, i;\n+\n+\t/* clear index map if loaded */\n+\tif (idx_map) {\n+\t\tmunmap(idx_map, idx_size);\n+\t\tidx_map = 0;\n+\t}\n+\n+\tlk = xcalloc(sizeof(struct lock_file), 1);\n+\tfd = hold_lock_file_for_update(lk, git_path(\"rev-cache/index\"), 0);\n+\tif (fd < 0) {\n+\t\tfree(lk);\n+\t\treturn -1;\n+\t}\n+\n+\t/* endianness yay! */\n+\tmemcpy(whead, \"REVINDEX\", 8);\n+\t*(whead + 8) = idx_head.version;\n+\tPACK_UINT32(whead + 9, idx_head.ofs_objects);\n+\tPACK_UINT32(whead + 13, idx_head.object_nr);\n+\t*(whead + 17) = idx_head.cache_nr;\n+\tPACK_UINT32(whead + 18, idx_head.max_date);\n+\n+\twrite(fd, &whead, INDEX_HEADER_SIZE);\n+\twrite_in_full(fd, idx_caches, idx_head.cache_nr * 20);\n+\n+\tfor (i = 0; i <= 0xff; i++)\n+\t\tfanout[i] = htonl(fanout[i]);\n+\twrite_in_full(fd, fanout, 0x100 * sizeof(uint32_t));\n+\n+\twrite_in_full(fd, body->buf, body->len);\n+\n+\tif (commit_lock_file(lk) < 0)\n+\t\treturn -2;\n+\n+\t/* lk freed by lockfile.c */\n+\n+\treturn 0;\n+}\n+\n+int make_cache_index(struct rev_cache_info *rci, unsigned char *cache_sha1,\n+\tint fd, unsigned int size)\n+{\n+\tstruct strbuf buffer;\n+\tint i, cache_index, cur;\n+\tunsigned char *map;\n+\tunsigned long max_date;\n+\n+\tif (!idx_map)\n+\t\tinit_index();\n+\n+\tlseek(fd, 0, SEEK_SET);\n+\tmap = xmmap(0, size, PROT_READ, MAP_PRIVATE, fd, 0);\n+\tif (map == MAP_FAILED)\n+\t\treturn -1;\n+\n+\tstrbuf_init(&buffer, 0);\n+\tif (idx_map) {\n+\t\tstrbuf_add(&buffer, idx_map + fanout[0], fanout[0x100] - fanout[0]);\n+\t} else {\n+\t\t/* not an update */\n+\t\tmemset(&idx_head, 0, sizeof(struct rc_index_header));\n+\t\tidx_caches = 0;\n+\n+\t\tstrcpy(idx_head.signature, \"REVINDEX\");\n+\t\tidx_head.version = SUPPORTED_REVINDEX_VERSION;\n+\t\tidx_head.ofs_objects = INDEX_HEADER_SIZE + 0x100 * sizeof(uint32_t);\n+\t}\n+\n+\t/* are we remaking a slice? */\n+\tfor (i = 0; i < idx_head.cache_nr; i++)\n+\t\tif (!hashcmp(idx_caches + i * 20, cache_sha1))\n+\t\t\tbreak;\n+\n+\tif (i == idx_head.cache_nr) {\n+\t\tcache_index = idx_head.cache_nr++;\n+\t\tidx_head.ofs_objects += 20;\n+\n+\t\tfprintf(stderr, \"bla: %d\\n\", idx_head.cache_nr * 20);\n+\t\tidx_caches = xrealloc(idx_caches, idx_head.cache_nr * 20);\n+\t\thashcpy(idx_caches + cache_index * 20, cache_sha1);\n+\t} else\n+\t\tcache_index = i;\n+\n+\ti = SLICE_HEADER_SIZE; /* offset */\n+\tmax_date = idx_head.max_date;\n+\twhile (i < size) {\n+\t\tstruct rc_index_entry index_entry, *entry;\n+\t\tunsigned char *disked_entry;\n+\t\tstruct rc_object_entry *object_entry = RC_OBTAIN_OBJECT_ENTRY(map + i);\n+\t\tunsigned long date;\n+\t\tint off, pos = i;\n+\n+\t\ti += RC_ACTUAL_OBJECT_ENTRY_SIZE(object_entry);\n+\n+\t\tif (object_entry->type != OBJ_COMMIT)\n+\t\t\tcontinue;\n+\n+\t\t/* don't include ends; otherwise we'll find ourselves in loops */\n+\t\tif (object_entry->is_end)\n+\t\t\tcontinue;\n+\n+\t\t/* handle index duplication\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\tdate = object_entry->date;\n+\t\tif (date > idx_head.max_date) {\n+\t\t\tdisked_entry = 0;\n+\t\t\tif (date > max_date)\n+\t\t\t\tmax_date = date;\n+\t\t} else\n+\t\t\tdisked_entry = search_index_1(object_entry->sha1);\n+\n+\t\tif (disked_entry && !object_entry->is_start)\n+\t\t\tcontinue;\n+\t\telse if (disked_entry) {\n+\t\t\t/* mmm, pointer arithmetic... tasty */  /* (entry - idx_map = offset, so cast is valid) */\n+\t\t\toff = (unsigned int)((unsigned char *)disked_entry - idx_map) - fanout[0];\n+\t\t\tdisked_entry = (unsigned char *)(buffer.buf + off);\n+\t\t\tentry = from_disked_rc_index_entry(disked_entry, 0);\n+\t\t} else\n+\t\t\tentry = &index_entry;\n+\n+\t\tmemset(entry, 0, sizeof(index_entry));\n+\t\tentry->sha1 = object_entry->sha1;\n+\t\tentry->is_start = object_entry->is_start;\n+\t\tentry->cache_index = cache_index;\n+\t\tentry->pos = pos;\n+\n+\t\tif (entry == &index_entry) {\n+\t\t\tstrbuf_add(&buffer, to_disked_rc_index_entry(entry, 0), INDEX_ENTRY_SIZE);\n+\t\t\tidx_head.object_nr++;\n+\t\t} else\n+\t\t\tto_disked_rc_index_entry(entry, &disked_entry);\n+\n+\t}\n+\n+\tidx_head.max_date = max_date;\n+\tqsort(buffer.buf, buffer.len / INDEX_ENTRY_SIZE, INDEX_ENTRY_SIZE, index_sort_hash);\n+\n+\t/* generate fanout */\n+\tcur = 0x00;\n+\tfor (i = 0; i < buffer.len; i += INDEX_ENTRY_SIZE) {\n+\t\tstruct rc_index_entry_ondisk *entry = (struct rc_index_entry_ondisk *)(buffer.buf + i);\n+\n+\t\twhile (cur <= entry->sha1[0])\n+\t\t\tfanout[cur++] = i + idx_head.ofs_objects;\n+\t}\n+\n+\twhile (cur <= 0xff)\n+\t\tfanout[cur++] = idx_head.ofs_objects + buffer.len;\n+\n+\t/* BOOM! */\n+\tif (write_cache_index(&buffer))\n+\t\treturn -1;\n+\n+\tmunmap(map, size);\n+\tstrbuf_release(&buffer);\n+\n+\t/* idx_map is unloaded without cleanup_cache_slices(), so regardless of previous index existence\n+\t * we can still free this up */\n+\tfree(idx_caches);\n+\n+\treturn 0;\n+}\n+\n+\n+/* add start-commits from each cache slice (uninterestingness will be propogated) */\n+void starts_from_slices(struct rev_info *revs, unsigned int flags)\n+{\n+\tstruct commit *commit;\n+\tint i;\n+\n+\tif (!idx_map)\n+\t\tinit_index();\n+\tif (!idx_map)\n+\t\treturn;\n+\n+\tfor (i = idx_head.ofs_objects; i < idx_size; i += INDEX_ENTRY_SIZE) {\n+\t\tstruct rc_index_entry *entry = RC_OBTAIN_INDEX_ENTRY(idx_map + i);\n+\n+\t\tif (!entry->is_start)\n+\t\t\tcontinue;\n+\n+\t\tcommit = lookup_commit(entry->sha1);\n+\t\tif (!commit)\n+\t\t\tcontinue;\n+\n+\t\tcommit->object.flags |= flags;\n+\t\tadd_pending_object(revs, &commit->object, 0);\n+\t}\n+\n+}\ndiff --git a/rev-cache.h b/rev-cache.h\nnew file mode 100644\nindex 0000000..76f4fb4\n--- /dev/null\n+++ b/rev-cache.h\n@@ -0,0 +1,105 @@\n+#ifndef REV_CACHE_H\n+#define REV_CACHE_H\n+\n+#define SUPPORTED_REVCACHE_VERSION \t\t1\n+#define SUPPORTED_REVINDEX_VERSION\t\t1\n+\n+#define RC_PATH_SIZE(x)\t(2 * (x))\n+\n+#define RC_OBTAIN_OBJECT_ENTRY(p)\t\t\tfrom_disked_rc_object_entry((unsigned char *)(p), 0)\n+#define RC_OBTAIN_INDEX_ENTRY(p)\t\t\tfrom_disked_rc_index_entry((unsigned char *)(p), 0)\n+\n+#define RC_ACTUAL_OBJECT_ENTRY_SIZE(e)\t\t(OBJECT_ENTRY_SIZE + RC_PATH_SIZE((e)->merge_nr + (e)->split_nr) + (e)->size_size)\n+\n+/* single index maps objects to cache files */\n+struct rc_index_header {\n+\tchar signature[8]; /* REVINDEX */\n+\tunsigned char version;\n+\tuint32_t ofs_objects;\n+\n+\tuint32_t object_nr;\n+\tunsigned char cache_nr;\n+\n+\tuint32_t max_date;\n+};\n+\n+struct rc_index_entry_ondisk {\n+\tunsigned char sha1[20];\n+\tunsigned char flags;\n+\tuint32_t pos;\n+};\n+\n+struct rc_index_entry {\n+\tunsigned char *sha1;\n+\tunsigned is_start:1;\n+\tunsigned cache_index:7;\n+\tuint32_t pos;\n+};\n+\n+\n+/* structure for actual cache file */\n+struct rc_slice_header {\n+\tchar signature[8]; /* REVCACHE */\n+\tunsigned char version;\n+\tuint32_t ofs_objects;\n+\n+\tuint32_t object_nr;\n+\tuint16_t path_nr;\n+\tuint32_t size;\n+\n+\tunsigned char sha1[20];\n+};\n+\n+struct rc_object_entry_ondisk {\n+\tunsigned char flags;\n+\tunsigned char sha1[20];\n+\n+\tunsigned char merge_nr;\n+\tunsigned char split_nr;\n+\tunsigned char sizes;\n+\n+\tuint32_t date;\n+\tuint16_t path;\n+};\n+\n+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 char *sha1; /* 20 byte */\n+\n+\tunsigned char merge_nr; /* : 7 */\n+\tunsigned char split_nr; /* : 7 */\n+\tunsigned size_size:3;\n+\tunsigned padding:5;\n+\n+\tuint32_t date;\n+\tuint16_t path;\n+\n+\t/* merge paths */\n+\t/* split paths */\n+\t/* size */\n+};\n+\n+struct rc_index_entry *from_disked_rc_index_entry(unsigned char *src, struct rc_index_entry *dst);\n+unsigned char *to_disked_rc_index_entry(struct rc_index_entry *src, unsigned char **dst);\n+struct rc_object_entry *from_disked_rc_object_entry(unsigned char *src, struct rc_object_entry *dst);\n+unsigned char *to_disked_rc_object_entry(struct rc_object_entry *src, unsigned char **dst);\n+\n+extern unsigned char *get_cache_slice(struct commit *commit);\n+extern int traverse_cache_slice(struct rev_info *revs,\n+\tunsigned char *cache_sha1, struct commit *commit,\n+\tunsigned long *date_so_far, int *slop_so_far,\n+\tstruct commit_list ***queue, struct commit_list **work);\n+\n+extern void init_rev_cache_info(struct rev_cache_info *rci);\n+extern int make_cache_slice(struct rev_cache_info *rci,\n+\tstruct rev_info *revs, struct commit_list **starts, struct commit_list **ends,\n+\tunsigned char *cache_sha1);\n+extern int make_cache_index(struct rev_cache_info *rci, unsigned char *cache_sha1,\n+\tint fd, unsigned int size);\n+\n+extern void starts_from_slices(struct rev_info *revs, unsigned int flags);\n+\n+#endif\ndiff --git a/revision.c b/revision.c\nindex f4b8b38..cd3dba8 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -444,7 +444,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)\n \tcommit->object.flags |= TREESAME;\n }\n \n-static void insert_by_date_cached(struct commit *p, struct commit_list **head,\n+void insert_by_date_cached(struct commit *p, struct commit_list **head,\n \t\t    struct commit_list *cached_base, struct commit_list **cache)\n {\n \tstruct commit_list *new_entry;\ndiff --git a/revision.h b/revision.h\nindex 568f1c9..0662c8c 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -14,7 +14,8 @@\n #define CHILD_SHOWN\t(1u<<6)\n #define ADDED\t\t(1u<<7)\t/* Parents already parsed and added? */\n #define SYMMETRIC_LEFT\t(1u<<8)\n-#define ALL_REV_FLAGS\t((1u<<9)-1)\n+#define FACE_VALUE\t(1u<<9)\n+#define ALL_REV_FLAGS\t((1u<<10)-1)\n \n #define DECORATE_SHORT_REFS\t1\n #define DECORATE_FULL_REFS\t2\n@@ -23,6 +24,19 @@ struct rev_info;\n struct log_info;\n struct string_list;\n \n+struct rev_cache_info {\n+\t/* generation flags */\n+\tunsigned objects : 1,\n+\t\tlegs : 1,\n+\t\tmake_index : 1;\n+\n+\t/* traversal flags */\n+\tunsigned add_to_pending : 1;\n+\n+\t/* fuse options */\n+\tunsigned int ignore_size;\n+};\n+\n struct rev_info {\n \t/* Starting list */\n \tstruct commit_list *commits;\n@@ -79,6 +93,10 @@ struct rev_info {\n \t\t\tdense_combined_merges:1,\n \t\t\talways_show_header:1;\n \n+\t/* rev-cache flags */\n+\tunsigned int for_pack:1,\n+\t\tdont_cache_me:1;\n+\n \t/* Format info */\n \tunsigned int\tshown_one:1,\n \t\t\tshow_merge:1,\n@@ -131,6 +149,9 @@ struct rev_info {\n \n \t/* notes-specific options: which refs to show */\n \tstruct display_notes_opt notes_opt;\n+\t\n+\t/* caching info, used ONLY by traverse_cache_slice */\n+\tstruct rev_cache_info rev_cache_info;\n };\n \n #define REV_TREE_SAME\t\t0\n@@ -186,4 +207,7 @@ enum commit_action {\n extern enum commit_action get_commit_action(struct rev_info *revs, struct commit *commit);\n extern enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit);\n \n+extern void insert_by_date_cached(struct commit *p, struct commit_list **head,\n+\t\t    struct commit_list *cached_base, struct commit_list **cache);\n+\n #endif\ndiff --git a/t/t6019-rev-cache-list.sh b/t/t6019-rev-cache-list.sh\nnew file mode 100644\nindex 0000000..8017e62\n--- /dev/null\n+++ b/t/t6019-rev-cache-list.sh\n@@ -0,0 +1,106 @@\n+#!/bin/sh\n+\n+test_description='git rev-cache tests'\n+. ./test-lib.sh\n+\n+test_cmp_sorted() {\n+\tgrep -io \"[a-f0-9]*\" $1 | sort >.tmpfile1 &&\n+\tgrep -io \"[a-f0-9]*\" $2 | sort >.tmpfile2 &&\n+\ttest_cmp .tmpfile1 .tmpfile2\n+}\n+\n+# we want a totally wacked out branch structure...\n+# we need branching and merging of sizes up through 3, tree\n+# addition/deletion, and enough branching to exercise path\n+# reuse\n+test_expect_success 'init repo' '\n+\techo bla >file &&\n+\tgit add . &&\n+\tgit commit -m \"bla\" &&\n+\n+\tgit branch b1 &&\n+\tgit checkout b1 &&\n+\techo blu >file2 &&\n+\tmkdir d1 &&\n+\techo bang >d1/filed1 &&\n+\tgit add . &&\n+\tgit commit -m \"blu\" &&\n+\n+\tgit checkout master &&\n+\tgit branch b2 &&\n+\tgit checkout b2 &&\n+\techo kaplaa >>file &&\n+\tgit commit -a -m \"kaplaa\" &&\n+\n+\tgit checkout master &&\n+\tmkdir smoke &&\n+\techo omg >smoke/bong &&\n+\tgit add . &&\n+\tgit commit -m \"omg\" &&\n+\n+\tgit branch b4 &&\n+\tgit checkout b4 &&\n+\techo shazam >file8 &&\n+\tgit add . &&\n+\tgit commit -m \"shazam\" &&\n+\tgit merge -m \"merge b2\" b2 &&\n+\n+\techo bam >smoke/pipe &&\n+\tgit add .\n+\tgit commit -m \"bam\" &&\n+\n+\tgit checkout master &&\n+\techo pow >file7 &&\n+\tgit add . &&\n+\tgit commit -m \"pow\" &&\n+\tgit merge -m \"merge b4\" b4 &&\n+\n+\tgit checkout b1 &&\n+\techo stuff >d1/filed1 &&\n+\tgit commit -a -m \"stuff\" &&\n+\n+\tgit branch b11 &&\n+\tgit checkout b11 &&\n+\techo wazzup >file3 &&\n+\tgit add file3 &&\n+\tgit commit -m \"wazzup\" &&\n+\n+\tgit checkout b1 &&\n+\tmkdir d1/d2 &&\n+\techo lol >d1/d2/filed2 &&\n+\tgit add . &&\n+\tgit commit -m \"lol\" &&\n+\n+\tgit checkout master &&\n+\tgit merge -m \"triple merge\" b1 b11 &&\n+\tgit rm -r d1 &&\n+\tgit commit -a -m \"oh noes\"\n+'\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+\tgrep \"final return value: 0\" output.err\n+'\n+\n+test_expect_success 'remake cache slice' '\n+\tgit rev-cache add HEAD 2>output.err &&\n+\tgrep \"final return value: 0\" output.err\n+'\n+\n+#check core mechanics and rev-list hook for commits\n+test_expect_success 'test rev-caches walker directly (limited)' '\n+\tgit rev-cache walk HEAD --not HEAD~3 >list &&\n+\ttest_cmp_sorted list proper_commit_list_limited\n+'\n+\n+test_expect_success 'test rev-caches walker directly (unlimited)' '\n+\tgit rev-cache walk HEAD >list &&\n+\ttest_cmp_sorted list proper_commit_list\n+'\n+\n+test_done\n+\n-- \ntg: (bac39ea..) t/rc/basic (depends on: t/rc/docs)\n"},{"id":"138775","messageId":"dbe35e7547614331d19b811c180731aa@212.159.54.234","threadId":"23342","inReplyTo":"4BBA40CD.5040301@gmail.com","subject":"Re: [PATCH 2/7 (v5)] basic api and porcelain","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2010-04-06T19:25:57Z","receivedAt":"2010-04-06T19:25:57Z","isPatch":true,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"On Mon, 05 Apr 2010 20:58:05 +0100, Nick Edelen <sirnot@gmail.com> wrote:\n> +\t/* initialize header */\n> +\tstrcpy(head.signature, \"REVCACHE\");\n\nhead.signature is 8 characters (see below), and so is \"REVCACHE\".  Surely\neither\nhead.signature needs to be 9 characters, or you shouldn't use strcpy. \nIndeed, mostly you do seem to be using memcpy ...\n\nThis is in a couple of other places too, with both rc_index_header, and\nrc_slice_header.\n\n> +/* single index maps objects to cache files */\n> +struct rc_index_header {\n> +\tchar signature[8]; /* REVINDEX */\n> +\tunsigned char version;\n> +\tuint32_t ofs_objects;\n> +\n> +\tuint32_t object_nr;\n> +\tunsigned char cache_nr;\n> +\n> +\tuint32_t max_date;\n> +};\n\n> +/* structure for actual cache file */\n> +struct rc_slice_header {\n> +\tchar signature[8]; /* REVCACHE */\n> +\tunsigned char version;\n> +\tuint32_t ofs_objects;\n> +\n> +\tuint32_t object_nr;\n> +\tuint16_t path_nr;\n> +\tuint32_t size;\n> +\n> +\tunsigned char sha1[20];\n> +};\n\n-- \nJulian\n"},{"id":"138783","messageId":"g2jc77435a81004061440l47f98094v99930eeb4ae6088@mail.gmail.com","threadId":"23342","inReplyTo":"dbe35e7547614331d19b811c180731aa@212.159.54.234","subject":"Re: [PATCH 2/7 (v5)] basic api and porcelain","fromName":"Nick Edelen","fromEmail":"sirnot@gmail.com","sentAt":"2010-04-06T21:40:35Z","receivedAt":"2010-04-06T21:40:35Z","isPatch":true,"sender":{"key":"sirnot@gmail.com","avatar":null},"body":"> head.signature is 8 characters (see below), and so is \"REVCACHE\".  Surely\n> either\n> head.signature needs to be 9 characters, or you shouldn't use strcpy.\n> Indeed, mostly you do seem to be using memcpy ...\n\naw shit, don't know how those slipped in there...  managed to do that\nwith slice pointer initialization too.  looks like I might have to do\nanother submission later.\n"}]}