{"thread":{"id":"33247","subject":"[PATCH v9 0/5] git log -L","startedAt":"2013-03-21T12:52:35Z","lastAt":"2013-03-24T07:38:54Z","messageCount":12,"participants":["Thomas Rast","Junio C Hamano","Eric Sunshine","Jeff King"],"isPatch":true,"patchVersion":9,"patchTotal":5},"messages":[{"id":"211859","messageId":"cover.1363865444.git.trast@student.ethz.ch","threadId":"33247","inReplyTo":null,"subject":"[PATCH v9 0/5] git log -L","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-21T12:52:35Z","receivedAt":"2013-03-21T12:52:35Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Compared to the previous round at\n\n http://thread.gmane.org/gmane.comp.version-control.git/217236\n\nI made the following changes (numbers from v8):\n\n[1/5] Refactor parse_loc\n\n Based on Junio's suggestions, the refactoring is now to a new file\n line-range.c that line-log.c will later use. (It still irks me too\n much to call straight into builtin/blame.c.)\n\n I also re-copied the existing functions, to make sure that they are\n the same. Junio correctly spotted some differences, and since we\n claim to only refactor those are bad.\n\n[2/5] Export rewrite_parents() for 'log -L'\n\n Unchanged.\n\n[2.5/5] blame: introduce $ as \"end of file\" in -L syntax\n\n Dropped. As Junio remarked, omitting the end is already a valid way\n of saying the same.\n\n[3/5] Implement line-history search (git log -L)\n\n Integrated Ramsay's fixes and Junio's remarks. Also made some minor\n cleanups. Added a perf test.\n\n[4/5] log -L: :pattern:file syntax to find by funcname\n\n Adjusted for changes in the earlier patches; otherwise the same.\n\n[5/5] Speed up log -L... -M\n\n Added to this series, I posted the same patch earlier in the side\n thread about the bad performance. The perf test from 4/5 neatly\n shows the difference.\n\nBo Yang (2):\n Refactor parse_loc\n Export rewrite_parents() for 'log -L'\n\nThomas Rast (3):\n Implement line-history search (git log -L)\n log -L: :pattern:file syntax to find by funcname\n Speed up log -L... -M\n\n Documentation/blame-options.txt | 21 +-\n Documentation/git-blame.txt | 6 +-\n Documentation/git-log.txt | 23 +\n Documentation/line-range-format.txt | 25 +\n Makefile | 4 +\n builtin/blame.c | 99 +--\n builtin/log.c | 31 +\n line-log.c | 1228 +++++++++++++++++++++++++++++++++++\n line-log.h | 49 ++\n line-range.c | 237 +++++++\n line-range.h | 36 +\n log-tree.c | 4 +\n revision.c | 22 +-\n revision.h | 16 +-\n t/perf/p4211-line-log.sh | 34 +\n t/t4211-line-log.sh | 40 ++\n t/t4211/expect.beginning-of-file | 43 ++\n t/t4211/expect.end-of-file | 62 ++\n t/t4211/expect.move-support-f | 40 ++\n t/t4211/expect.simple-f | 59 ++\n t/t4211/expect.simple-main | 68 ++\n t/t4211/expect.two-ranges | 102 +++\n t/t4211/expect.vanishes-early | 39 ++\n t/t4211/history.export | 330 ++++++++++\n t/t8003-blame-corner-cases.sh | 6 +\n 25 files changed, 2501 insertions(+), 123 deletions(-)\n create mode 100644 Documentation/line-range-format.txt\n create mode 100644 line-log.c\n create mode 100644 line-log.h\n create mode 100644 line-range.c\n create mode 100644 line-range.h\n create mode 100755 t/perf/p4211-line-log.sh\n create mode 100755 t/t4211-line-log.sh\n create mode 100644 t/t4211/expect.beginning-of-file\n create mode 100644 t/t4211/expect.end-of-file\n create mode 100644 t/t4211/expect.move-support-f\n create mode 100644 t/t4211/expect.simple-f\n create mode 100644 t/t4211/expect.simple-main\n create mode 100644 t/t4211/expect.two-ranges\n create mode 100644 t/t4211/expect.vanishes-early\n create mode 100644 t/t4211/history.export\n\n-- \n1.8.2.241.gee8bb87\n"},{"id":"211861","messageId":"2ea2c802cc98f485e3c347f278126db0395791a6.1363865444.git.trast@student.ethz.ch","threadId":"33247","inReplyTo":"cover.1363865444.git.trast@student.ethz.ch","subject":"[PATCH v9 1/5] Refactor parse_loc","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-21T12:52:36Z","receivedAt":"2013-03-21T12:52:36Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"From: Bo Yang \n\nWe want to use the same style of -L n,m argument for 'git log -L' as\nfor git-blame. Refactor the argument parsing of the range arguments\nfrom builtin/blame.c to the (new) file that will hold the 'git log -L'\nlogic.\n\nTo accommodate different data structures in blame and log -L, the file\ncontents are abstracted away; parse_range_arg takes a callback that it\nuses to get the contents of a line of the (notional) file.\n\nThe new test is for a case that made me pause during debugging: the\n'blame -L with invalid end' test was the only one that noticed an\noutright failure to parse the end *at all*. So make a more explicit\ntest for that.\n\nSigned-off-by: Bo Yang \nSigned-off-by: Thomas Rast \n---\n Documentation/blame-options.txt | 19 +------\n Documentation/line-range-format.txt | 18 +++++++\n Makefile | 2 +\n builtin/blame.c | 99 +++----------------------------------\n line-range.c | 92 ++++++++++++++++++++++++++++++++++\n line-range.h | 24 +++++++++\n t/t8003-blame-corner-cases.sh | 6 +++\n 7 files changed, 151 insertions(+), 109 deletions(-)\n create mode 100644 Documentation/line-range-format.txt\n create mode 100644 line-range.c\n create mode 100644 line-range.h\n\ndiff --git a/Documentation/blame-options.txt b/Documentation/blame-options.txt\nindex b0d31df..6998d9f 100644\n--- a/Documentation/blame-options.txt\n+++ b/Documentation/blame-options.txt\n@@ -13,24 +13,7 @@\n \tAnnotate only the given line range. and can take\n \tone of these forms:\n \n-\t- number\n-+\n-If or is a number, it specifies an\n-absolute line number (lines count from 1).\n-+\n-\n-- /regex/\n-+\n-This form will use the first line matching the given\n-POSIX regex. If is a regex, it will search\n-starting at the line given by .\n-+\n-\n-- +offset or -offset\n-+\n-This is only valid for and will specify a number\n-of lines before or after the line given by .\n-+\n+include::line-range-format.txt[]\n \n -l::\n \tShow long rev (Default: off).\ndiff --git a/Documentation/line-range-format.txt b/Documentation/line-range-format.txt\nnew file mode 100644\nindex 0000000..265bc23\n--- /dev/null\n+++ b/Documentation/line-range-format.txt\n@@ -0,0 +1,18 @@\n+- number\n++\n+If or is a number, it specifies an\n+absolute line number (lines count from 1).\n++\n+\n+- /regex/\n++\n+This form will use the first line matching the given\n+POSIX regex. If is a regex, it will search\n+starting at the line given by .\n++\n+\n+- +offset or -offset\n++\n+This is only valid for and will specify a number\n+of lines before or after the line given by .\n++\ndiff --git a/Makefile b/Makefile\nindex 598d631..e83f64b 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -667,6 +667,7 @@ LIB_H += help.h\n LIB_H += http.h\n LIB_H += kwset.h\n LIB_H += levenshtein.h\n+LIB_H += line-range.h\n LIB_H += list-objects.h\n LIB_H += ll-merge.h\n LIB_H += log-tree.h\n@@ -795,6 +796,7 @@ LIB_OBJS += hex.o\n LIB_OBJS += ident.o\n LIB_OBJS += kwset.o\n LIB_OBJS += levenshtein.o\n+LIB_OBJS += line-range.o\n LIB_OBJS += list-objects.o\n LIB_OBJS += ll-merge.o\n LIB_OBJS += lockfile.o\ndiff --git a/builtin/blame.c b/builtin/blame.c\nindex 86100e9..20eb439 100644\n--- a/builtin/blame.c\n+++ b/builtin/blame.c\n@@ -21,6 +21,7 @@\n #include \"parse-options.h\"\n #include \"utf8.h\"\n #include \"userdiff.h\"\n+#include \"line-range.h\"\n \n static char blame_usage[] = N_(\"git blame [options] [rev-opts] [rev] [--] file\");\n \n@@ -566,11 +567,16 @@ static void dup_entry(struct blame_entry *dst, struct blame_entry *src)\n \tdst->score = 0;\n }\n \n-static const char *nth_line(struct scoreboard *sb, int lno)\n+static const char *nth_line(struct scoreboard *sb, long lno)\n {\n \treturn sb->final_buf + sb->lineno[lno];\n }\n \n+static const char *nth_line_cb(void *data, long lno)\n+{\n+\treturn nth_line((struct scoreboard *)data, lno);\n+}\n+\n /*\n * It is known that lines between tlno to same came from parent, and e\n * has an overlap with that range. it also is known that parent's\n@@ -1927,83 +1933,6 @@ static const char *add_prefix(const char *prefix, const char *path)\n }\n \n /*\n- * Parsing of (comma separated) one item in the -L option\n- */\n-static const char *parse_loc(const char *spec,\n-\t\t\t struct scoreboard *sb, long lno,\n-\t\t\t long begin, long *ret)\n-{\n-\tchar *term;\n-\tconst char *line;\n-\tlong num;\n-\tint reg_error;\n-\tregex_t regexp;\n-\tregmatch_t match[1];\n-\n-\t/* Allow \"-L ,+20\" to mean starting at \n-\t * for 20 lines, or \"-L ,-5\" for 5 lines ending at\n-\t * .\n-\t */\n-\tif (1 < begin && (spec[0] == '+' || spec[0] == '-')) {\n-\t\tnum = strtol(spec + 1, &term, 10);\n-\t\tif (term != spec + 1) {\n-\t\t\tif (spec[0] == '-')\n-\t\t\t\tnum = 0 - num;\n-\t\t\tif (0 < num)\n-\t\t\t\t*ret = begin + num - 2;\n-\t\t\telse if (!num)\n-\t\t\t\t*ret = begin;\n-\t\t\telse\n-\t\t\t\t*ret = begin + num;\n-\t\t\treturn term;\n-\t\t}\n-\t\treturn spec;\n-\t}\n-\tnum = strtol(spec, &term, 10);\n-\tif (term != spec) {\n-\t\t*ret = num;\n-\t\treturn term;\n-\t}\n-\tif (spec[0] != '/')\n-\t\treturn spec;\n-\n-\t/* it could be a regexp of form /.../ */\n-\tfor (term = (char *) spec + 1; *term && *term != '/'; term++) {\n-\t\tif (*term == '\\\\')\n-\t\t\tterm++;\n-\t}\n-\tif (*term != '/')\n-\t\treturn spec;\n-\n-\t/* try [spec+1 .. term-1] as regexp */\n-\t*term = 0;\n-\tbegin--; /* input is in human terms */\n-\tline = nth_line(sb, begin);\n-\n-\tif (!(reg_error = regcomp(®exp, spec + 1, REG_NEWLINE)) &&\n-\t !(reg_error = regexec(®exp, line, 1, match, 0))) {\n-\t\tconst char *cp = line + match[0].rm_so;\n-\t\tconst char *nline;\n-\n-\t\twhile (begin++ < lno) {\n-\t\t\tnline = nth_line(sb, begin);\n-\t\t\tif (line <= cp && cp < nline)\n-\t\t\t\tbreak;\n-\t\t\tline = nline;\n-\t\t}\n-\t\t*ret = begin;\n-\t\tregfree(®exp);\n-\t\t*term++ = '/';\n-\t\treturn term;\n-\t}\n-\telse {\n-\t\tchar errbuf[1024];\n-\t\tregerror(reg_error, ®exp, errbuf, 1024);\n-\t\tdie(\"-L parameter '%s': %s\", spec + 1, errbuf);\n-\t}\n-}\n-\n-/*\n * Parsing of -L option\n */\n static void prepare_blame_range(struct scoreboard *sb,\n@@ -2011,15 +1940,7 @@ static void prepare_blame_range(struct scoreboard *sb,\n \t\t\t\tlong lno,\n \t\t\t\tlong *bottom, long *top)\n {\n-\tconst char *term;\n-\n-\tterm = parse_loc(bottomtop, sb, lno, 1, bottom);\n-\tif (*term == ',') {\n-\t\tterm = parse_loc(term + 1, sb, lno, *bottom + 1, top);\n-\t\tif (*term)\n-\t\t\tusage(blame_usage);\n-\t}\n-\tif (*term)\n+\tif (parse_range_arg(bottomtop, nth_line_cb, sb, lno, bottom, top))\n \t\tusage(blame_usage);\n }\n \n@@ -2569,10 +2490,6 @@ int cmd_blame(int argc, const char **argv, const char *prefix)\n \tbottom = top = 0;\n \tif (bottomtop)\n \t\tprepare_blame_range(&sb, bottomtop, lno, &bottom, &top);\n-\tif (bottom && top && top < bottom) {\n-\t\tlong tmp;\n-\t\ttmp = top; top = bottom; bottom = tmp;\n-\t}\n \tif (bottom < 1)\n \t\tbottom = 1;\n \tif (top < 1)\ndiff --git a/line-range.c b/line-range.c\nnew file mode 100644\nindex 0000000..0af43bf\n--- /dev/null\n+++ b/line-range.c\n@@ -0,0 +1,92 @@\n+#include \"git-compat-util.h\"\n+#include \"line-range.h\"\n+\n+/*\n+ * Parse one item in the -L option\n+ */\n+static const char *parse_loc(const char *spec, nth_line_fn_t nth_line,\n+\t\t\t void *data, long lines, long begin, long *ret)\n+{\n+\tchar *term;\n+\tconst char *line;\n+\tlong num;\n+\tint reg_error;\n+\tregex_t regexp;\n+\tregmatch_t match[1];\n+\n+\t/* Allow \"-L ,+20\" to mean starting at \n+\t * for 20 lines, or \"-L ,-5\" for 5 lines ending at\n+\t * .\n+\t */\n+\tif (1 < begin && (spec[0] == '+' || spec[0] == '-')) {\n+\t\tnum = strtol(spec + 1, &term, 10);\n+\t\tif (term != spec + 1) {\n+\t\t\tif (spec[0] == '-')\n+\t\t\t\tnum = 0 - num;\n+\t\t\tif (0 < num)\n+\t\t\t\t*ret = begin + num - 2;\n+\t\t\telse if (!num)\n+\t\t\t\t*ret = begin;\n+\t\t\telse\n+\t\t\t\t*ret = begin + num;\n+\t\t\treturn term;\n+\t\t}\n+\t\treturn spec;\n+\t}\n+\tnum = strtol(spec, &term, 10);\n+\tif (term != spec) {\n+\t\t*ret = num;\n+\t\treturn term;\n+\t}\n+\tif (spec[0] != '/')\n+\t\treturn spec;\n+\n+\t/* it could be a regexp of form /.../ */\n+\tfor (term = (char *) spec + 1; *term && *term != '/'; term++) {\n+\t\tif (*term == '\\\\')\n+\t\t\tterm++;\n+\t}\n+\tif (*term != '/')\n+\t\treturn spec;\n+\n+\t/* try [spec+1 .. term-1] as regexp */\n+\t*term = 0;\n+\tbegin--; /* input is in human terms */\n+\tline = nth_line(data, begin);\n+\n+\tif (!(reg_error = regcomp(®exp, spec + 1, REG_NEWLINE)) &&\n+\t !(reg_error = regexec(®exp, line, 1, match, 0))) {\n+\t\tconst char *cp = line + match[0].rm_so;\n+\t\tconst char *nline;\n+\n+\t\twhile (begin++ < lines) {\n+\t\t\tnline = nth_line(data, begin);\n+\t\t\tif (line <= cp && cp < nline)\n+\t\t\t\tbreak;\n+\t\t\tline = nline;\n+\t\t}\n+\t\t*ret = begin;\n+\t\tregfree(®exp);\n+\t\t*term++ = '/';\n+\t\treturn term;\n+\t}\n+\telse {\n+\t\tchar errbuf[1024];\n+\t\tregerror(reg_error, ®exp, errbuf, 1024);\n+\t\tdie(\"-L parameter '%s': %s\", spec + 1, errbuf);\n+\t}\n+}\n+\n+int parse_range_arg(const char *arg, nth_line_fn_t nth_line_cb,\n+\t\t void *cb_data, long lines, long *begin, long *end)\n+{\n+\targ = parse_loc(arg, nth_line_cb, cb_data, lines, 1, begin);\n+\n+\tif (*arg == ',')\n+\t\targ = parse_loc(arg+1, nth_line_cb, cb_data, lines, *begin+1, end);\n+\n+\tif (*arg)\n+\t\treturn -1;\n+\n+\treturn 0;\n+}\ndiff --git a/line-range.h b/line-range.h\nnew file mode 100644\nindex 0000000..830f25b\n--- /dev/null\n+++ b/line-range.h\n@@ -0,0 +1,24 @@\n+#ifndef LINE_RANGE_H\n+#define LINE_RANGE_H\n+\n+/*\n+ * Parse one item in an -L begin,end option w.r.t. the notional file\n+ * object 'cb_data' consisting of 'lines' lines.\n+ *\n+ * The 'nth_line_cb' callback is used to determine the start of the\n+ * line 'lno' inside the 'cb_data'. The caller is expected to already\n+ * have a suitable map at hand to make this a constant-time lookup.\n+ *\n+ * Returns 0 in case of success and -1 if there was an error. The\n+ * actual range is stored in *begin and *end. The counting starts\n+ * at 1! In case of error, the caller should show usage message.\n+ */\n+\n+typedef const char *(*nth_line_fn_t)(void *data, long lno);\n+\n+extern int parse_range_arg(const char *arg,\n+\t\t\t nth_line_fn_t nth_line_cb,\n+\t\t\t void *cb_data, long lines,\n+\t\t\t long *begin, long *end);\n+\n+#endif /* LINE_RANGE_H */\ndiff --git a/t/t8003-blame-corner-cases.sh b/t/t8003-blame-corner-cases.sh\nindex 230143c..e7cac1d 100755\n--- a/t/t8003-blame-corner-cases.sh\n+++ b/t/t8003-blame-corner-cases.sh\n@@ -175,6 +175,12 @@ test_expect_success 'blame -L with invalid end' '\n \tgrep \"has only 2 lines\" errors\n '\n \n+test_expect_success 'blame parses part of -L' '\n+\tgit blame -L1,1 tres >out &&\n+\tcat out &&\n+\ttest $(wc -l < out) -eq 1\n+'\n+\n test_expect_success 'indent of line numbers, nine lines' '\n \tgit blame nine_lines >actual &&\n \ttest $(grep -c \" \" actual) = 0\n-- \n1.8.2.241.gee8bb87\n"},{"id":"211864","messageId":"e995dd0279409040190317005953fdb216f6f6af.1363865444.git.trast@student.ethz.ch","threadId":"33247","inReplyTo":"cover.1363865444.git.trast@student.ethz.ch","subject":"[PATCH v9 2/5] Export rewrite_parents() for 'log -L'","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-21T12:52:37Z","receivedAt":"2013-03-21T12:52:37Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"From: Bo Yang \n\nThe function rewrite_one is used to rewrite a single\nparent of the current commit, and is used by rewrite_parents\nto rewrite all the parents.\n\nDecouple the dependence between them by making rewrite_one\na callback function that is passed to rewrite_parents. Then\nexport rewrite_parents for reuse by the line history browser.\n\nWe will use this function in line-log.c.\n\nSigned-off-by: Bo Yang \nSigned-off-by: Thomas Rast \n---\n revision.c | 13 ++++---------\n revision.h | 10 ++++++++++\n 2 files changed, 14 insertions(+), 9 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex ef60205..46319d5 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2173,12 +2173,6 @@ int prepare_revision_walk(struct rev_info *revs)\n \treturn 0;\n }\n \n-enum rewrite_result {\n-\trewrite_one_ok,\n-\trewrite_one_noparents,\n-\trewrite_one_error\n-};\n-\n static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp)\n {\n \tstruct commit_list *cache = NULL;\n@@ -2200,12 +2194,13 @@ static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp\n \t}\n }\n \n-static int rewrite_parents(struct rev_info *revs, struct commit *commit)\n+int rewrite_parents(struct rev_info *revs, struct commit *commit,\n+\trewrite_parent_fn_t rewrite_parent)\n {\n \tstruct commit_list **pp = &commit->parents;\n \twhile (*pp) {\n \t\tstruct commit_list *parent = *pp;\n-\t\tswitch (rewrite_one(revs, &parent->item)) {\n+\t\tswitch (rewrite_parent(revs, &parent->item)) {\n \t\tcase rewrite_one_ok:\n \t\t\tbreak;\n \t\tcase rewrite_one_noparents:\n@@ -2371,7 +2366,7 @@ enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit)\n \tif (action == commit_show &&\n \t !revs->show_all &&\n \t revs->prune && revs->dense && want_ancestry(revs)) {\n-\t\tif (rewrite_parents(revs, commit) < 0)\n+\t\tif (rewrite_parents(revs, commit, rewrite_one) < 0)\n \t\t\treturn commit_error;\n \t}\n \treturn action;\ndiff --git a/revision.h b/revision.h\nindex 5da09ee..640110d 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -241,4 +241,14 @@ 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+enum rewrite_result {\n+\trewrite_one_ok,\n+\trewrite_one_noparents,\n+\trewrite_one_error\n+};\n+\n+typedef enum rewrite_result (*rewrite_parent_fn_t)(struct rev_info *revs, struct commit **pp);\n+\n+extern int rewrite_parents(struct rev_info *revs, struct commit *commit,\n+\trewrite_parent_fn_t rewrite_parent);\n #endif\n-- \n1.8.2.241.gee8bb87\n"},{"id":"211862","messageId":"b8cabd5ca63a17577fca524891046e5a3d3dfc60.1363865444.git.trast@student.ethz.ch","threadId":"33247","inReplyTo":"cover.1363865444.git.trast@student.ethz.ch","subject":"[PATCH v9 3/5] Implement line-history search (git log -L)","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-21T12:52:38Z","receivedAt":"2013-03-21T12:52:38Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"This is a rewrite of much of Bo's work, mainly in an effort to split\nit into smaller, easier to understand routines.\n\nThe algorithm is built around the struct range_set, which encodes a\nseries of line ranges as intervals [a,b). This is used in two\ncontexts:\n\n* A set of lines we are tracking (which will change as we dig through\n history).\n* To encode diffs, as pairs of ranges.\n\nThe main routine is range_set_map_across_diff(). It processes the\ndiff between a commit C and some parent P. It determines which diff\nhunks are relevant to the ranges tracked in C, and computes the new\nranges for P.\n\nThe algorithm is then simply to process history in topological order\nfrom newest to oldest, computing ranges and (partial) diffs. At\nbranch points, we need to merge the ranges we are watching. We will\nfind that many commits do not affect the chosen ranges, and mark them\nTREESAME (in addition to those already filtered by pathspec limiting).\nAnother pass of history simplification then gets rid of such commits.\n\nThis is wired as an extra filtering pass in the log machinery. This\ncurrently only reduces code duplication, but should allow for other\nsimplifications and options to be used.\n\nFinally, we hook a diff printer into the output chain. Ideally we\nwould wire directly into the diff logic, to optionally use features\nlike word diff. However, that will require some major reworking of\nthe diff chain, so we completely replace the output with our own diff\nfor now.\n\nAs this was a GSoC project, and has quite some history by now, many\npeople have helped. In no particular order, thanks go to\n\n Jakub Narebski \n Jens Lehmann \n Jonathan Nieder \n Junio C Hamano \n Ramsay Jones \n Will Palmer \n\nApologies to everyone I forgot.\n\nSigned-off-by: Bo Yang \nSigned-off-by: Thomas Rast \n---\n Documentation/git-log.txt | 22 +\n Makefile | 2 +\n builtin/log.c | 31 +\n line-log.c | 1179 ++++++++++++++++++++++++++++++++++++++\n line-log.h | 49 ++\n line-range.c | 19 +-\n line-range.h | 11 +\n log-tree.c | 4 +\n revision.c | 9 +\n revision.h | 6 +-\n t/perf/p4211-line-log.sh | 34 ++\n t/t4211-line-log.sh | 38 ++\n t/t4211/expect.beginning-of-file | 43 ++\n t/t4211/expect.end-of-file | 62 ++\n t/t4211/expect.move-support-f | 40 ++\n t/t4211/expect.simple-f | 59 ++\n t/t4211/expect.simple-main | 68 +++\n t/t4211/expect.two-ranges | 102 ++++\n t/t4211/expect.vanishes-early | 39 ++\n t/t4211/history.export | 330 +++++++++++\n 20 files changed, 2145 insertions(+), 2 deletions(-)\n create mode 100644 line-log.c\n create mode 100644 line-log.h\n create mode 100755 t/perf/p4211-line-log.sh\n create mode 100755 t/t4211-line-log.sh\n create mode 100644 t/t4211/expect.beginning-of-file\n create mode 100644 t/t4211/expect.end-of-file\n create mode 100644 t/t4211/expect.move-support-f\n create mode 100644 t/t4211/expect.simple-f\n create mode 100644 t/t4211/expect.simple-main\n create mode 100644 t/t4211/expect.two-ranges\n create mode 100644 t/t4211/expect.vanishes-early\n create mode 100644 t/t4211/history.export\n\ndiff --git a/Documentation/git-log.txt b/Documentation/git-log.txt\nindex 69db578..8727c60 100644\n--- a/Documentation/git-log.txt\n+++ b/Documentation/git-log.txt\n@@ -69,6 +69,23 @@ produced by --stat etc.\n \tNote that only message is considered, if also a diff is shown\n \tits size is not included.\n \n+-L ,:::\n+\tTrace the evolution of the line range given by \",\"\n+\twithin the . You may not give any pathspec limiters.\n+\tThis is currently limited to a walk starting from a single\n+\trevision, i.e., you may only give zero or one positive\n+\trevision arguments.\n+\n+ and can take one of these forms:\n+\n+include::line-range-format.txt[]\n+You can specify this option more than once.\n+\n+\n+--full-line-diff::\n+\tAlways print the interesting range even if the current commit\n+\tdoes not change any line of the range.\n+\n [\\--] ...::\n \tShow only commits that are enough to explain how the files\n \tthat match the specified paths came to be. See \"History\n@@ -138,6 +155,11 @@ Examples\n \tThis makes sense only when following a strict policy of merging all\n \ttopic branches when staying on a single integration branch.\n \n+git log -L '/int main/',/^}/:main.c::\n+\n+\tShows how the function `main()` in the file 'main.c' evolved\n+\tover time.\n+\n `git log -3`::\n \tLimits the number of commits to show to 3.\n \ndiff --git a/Makefile b/Makefile\nindex e83f64b..2156fa7 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -667,6 +667,7 @@ LIB_H += help.h\n LIB_H += http.h\n LIB_H += kwset.h\n LIB_H += levenshtein.h\n+LIB_H += line-log.h\n LIB_H += line-range.h\n LIB_H += list-objects.h\n LIB_H += ll-merge.h\n@@ -796,6 +797,7 @@ LIB_OBJS += hex.o\n LIB_OBJS += ident.o\n LIB_OBJS += kwset.o\n LIB_OBJS += levenshtein.o\n+LIB_OBJS += line-log.o\n LIB_OBJS += line-range.o\n LIB_OBJS += list-objects.o\n LIB_OBJS += ll-merge.o\ndiff --git a/builtin/log.c b/builtin/log.c\nindex 8f0b2e8..d584ff1 100644\n--- a/builtin/log.c\n+++ b/builtin/log.c\n@@ -19,6 +19,7 @@\n #include \"remote.h\"\n #include \"string-list.h\"\n #include \"parse-options.h\"\n+#include \"line-log.h\"\n #include \"branch.h\"\n #include \"streaming.h\"\n #include \"version.h\"\n@@ -41,6 +42,12 @@\n \tNULL\n };\n \n+struct line_opt_callback_data {\n+\tstruct rev_info *rev;\n+\tconst char *prefix;\n+\tstruct string_list args;\n+};\n+\n static int parse_decoration_style(const char *var, const char *value)\n {\n \tswitch (git_config_maybe_bool(var, value)) {\n@@ -75,6 +82,19 @@ static int decorate_callback(const struct option *opt, const char *arg, int unse\n \treturn 0;\n }\n \n+static int log_line_range_callback(const struct option *option, const char *arg, int unset)\n+{\n+\tstruct line_opt_callback_data *data = option->value;\n+\n+\tif (!arg)\n+\t\treturn -1;\n+\n+\tdata->rev->line_level_traverse = 1;\n+\tstring_list_append(&data->args, arg);\n+\n+\treturn 0;\n+}\n+\n static void cmd_log_init_defaults(struct rev_info *rev)\n {\n \tif (fmt_pretty)\n@@ -97,6 +117,7 @@ static void cmd_log_init_finish(int argc, const char **argv, const char *prefix,\n {\n \tstruct userformat_want w;\n \tint quiet = 0, source = 0, mailmap = 0;\n+\tstatic struct line_opt_callback_data line_cb = {NULL, NULL, STRING_LIST_INIT_DUP};\n \n \tconst struct option builtin_log_options[] = {\n \t\tOPT_BOOLEAN(0, \"quiet\", &quiet, N_(\"suppress diff output\")),\n@@ -104,9 +125,15 @@ static void cmd_log_init_finish(int argc, const char **argv, const char *prefix,\n \t\tOPT_BOOLEAN(0, \"use-mailmap\", &mailmap, N_(\"Use mail map file\")),\n \t\t{ OPTION_CALLBACK, 0, \"decorate\", NULL, NULL, N_(\"decorate options\"),\n \t\t PARSE_OPT_OPTARG, decorate_callback},\n+\t\tOPT_CALLBACK('L', NULL, &line_cb, \"n,m:file\",\n+\t\t\t \"Process line range n,m in file, counting from 1\",\n+\t\t\t log_line_range_callback),\n \t\tOPT_END()\n \t};\n \n+\tline_cb.rev = rev;\n+\tline_cb.prefix = prefix;\n+\n \tmailmap = use_mailmap_config;\n \targc = parse_options(argc, argv, prefix,\n \t\t\t builtin_log_options, builtin_log_usage,\n@@ -160,6 +187,10 @@ static void cmd_log_init_finish(int argc, const char **argv, const char *prefix,\n \t\trev->show_decorations = 1;\n \t\tload_ref_decorations(decoration_style);\n \t}\n+\n+\tif (rev->line_level_traverse)\n+\t\tline_log_init(rev, line_cb.prefix, &line_cb.args);\n+\n \tsetup_pager();\n }\n \ndiff --git a/line-log.c b/line-log.c\nnew file mode 100644\nindex 0000000..29162fc\n--- /dev/null\n+++ b/line-log.c\n@@ -0,0 +1,1179 @@\n+#include \"git-compat-util.h\"\n+#include \"line-range.h\"\n+#include \"cache.h\"\n+#include \"tag.h\"\n+#include \"blob.h\"\n+#include \"tree.h\"\n+#include \"diff.h\"\n+#include \"commit.h\"\n+#include \"decorate.h\"\n+#include \"revision.h\"\n+#include \"xdiff-interface.h\"\n+#include \"strbuf.h\"\n+#include \"log-tree.h\"\n+#include \"graph.h\"\n+#include \"line-log.h\"\n+\n+static void range_set_grow(struct range_set *rs, size_t extra)\n+{\n+\tALLOC_GROW(rs->ranges, rs->nr + extra, rs->alloc);\n+}\n+\n+/* Either initialization would be fine */\n+#define RANGE_SET_INIT {0}\n+\n+static void range_set_init(struct range_set *rs, size_t prealloc)\n+{\n+\trs->alloc = rs->nr = 0;\n+\trs->ranges = NULL;\n+\tif (prealloc)\n+\t\trange_set_grow(rs, prealloc);\n+}\n+\n+static void range_set_release(struct range_set *rs)\n+{\n+\tfree(rs->ranges);\n+\trs->alloc = rs->nr = 0;\n+\trs->ranges = NULL;\n+}\n+\n+/* dst must be uninitialized! */\n+static void range_set_copy(struct range_set *dst, struct range_set *src)\n+{\n+\trange_set_init(dst, src->nr);\n+\tmemcpy(dst->ranges, src->ranges, src->nr*sizeof(struct range_set));\n+\tdst->nr = src->nr;\n+}\n+static void range_set_move(struct range_set *dst, struct range_set *src)\n+{\n+\trange_set_release(dst);\n+\tdst->ranges = src->ranges;\n+\tdst->nr = src->nr;\n+\tdst->alloc = src->alloc;\n+\tsrc->ranges = NULL;\n+\tsrc->alloc = src->nr = 0;\n+}\n+\n+/* tack on a _new_ range _at the end_ */\n+static void range_set_append(struct range_set *rs, long a, long b)\n+{\n+\tassert(a <= b);\n+\tassert(rs->nr == 0 || rs->ranges[rs->nr-1].end <= a);\n+\trange_set_grow(rs, 1);\n+\trs->ranges[rs->nr].start = a;\n+\trs->ranges[rs->nr].end = b;\n+\trs->nr++;\n+}\n+\n+static int range_cmp(const void *_r, const void *_s)\n+{\n+\tconst struct range *r = _r;\n+\tconst struct range *s = _s;\n+\n+\t/* this could be simply 'return r.start-s.start', but for the types */\n+\tif (r->start == s->start)\n+\t\treturn 0;\n+\tif (r->start < s->start)\n+\t\treturn -1;\n+\treturn 1;\n+}\n+\n+/*\n+ * Helper: In-place pass of sorting and merging the ranges in the\n+ * range set, to re-establish the invariants after another operation\n+ *\n+ * NEEDSWORK currently not needed\n+ */\n+static void sort_and_merge_range_set(struct range_set *rs)\n+{\n+\tint i;\n+\tint o = 1; /* output cursor */\n+\n+\tqsort(rs->ranges, rs->nr, sizeof(struct range), range_cmp);\n+\n+\tfor (i = 1; i < rs->nr; i++) {\n+\t\tif (rs->ranges[i].start <= rs->ranges[o-1].end) {\n+\t\t\trs->ranges[o-1].end = rs->ranges[i].end;\n+\t\t} else {\n+\t\t\trs->ranges[o].start = rs->ranges[i].start;\n+\t\t\trs->ranges[o].end = rs->ranges[i].end;\n+\t\t\to++;\n+\t\t}\n+\t}\n+\tassert(o <= rs->nr);\n+\trs->nr = o;\n+}\n+\n+/*\n+ * Union of range sets (i.e., sets of line numbers). Used to merge\n+ * them when searches meet at a common ancestor.\n+ *\n+ * This is also where the ranges are consolidated into canonical form:\n+ * overlapping and adjacent ranges are merged, and empty ranges are\n+ * removed.\n+ */\n+static void range_set_union(struct range_set *out,\n+\t\t\t struct range_set *a, struct range_set *b)\n+{\n+\tint i = 0, j = 0, o = 0;\n+\tstruct range *ra = a->ranges;\n+\tstruct range *rb = b->ranges;\n+\t/* cannot make an alias of out->ranges: it may change during grow */\n+\n+\tassert(out->nr == 0);\n+\twhile (i < a->nr || j < b->nr) {\n+\t\tstruct range *new;\n+\t\tif (i < a->nr && j < b->nr) {\n+\t\t\tif (ra[i].start < rb[j].start)\n+\t\t\t\tnew = &ra[i++];\n+\t\t\telse if (ra[i].start > rb[j].start)\n+\t\t\t\tnew = &rb[j++];\n+\t\t\telse if (ra[i].end < rb[j].end)\n+\t\t\t\tnew = &ra[i++];\n+\t\t\telse\n+\t\t\t\tnew = &rb[j++];\n+\t\t} else if (i < a->nr) /* b exhausted */\n+\t\t\tnew = &ra[i++];\n+\t\telse /* a exhausted */\n+\t\t\tnew = &rb[j++];\n+\t\tif (new->start == new->end)\n+\t\t\t; /* empty range */\n+\t\telse if (!o || out->ranges[o-1].end < new->start) {\n+\t\t\trange_set_grow(out, 1);\n+\t\t\tout->ranges[o].start = new->start;\n+\t\t\tout->ranges[o].end = new->end;\n+\t\t\to++;\n+\t\t} else if (out->ranges[o-1].end < new->end) {\n+\t\t\tout->ranges[o-1].end = new->end;\n+\t\t}\n+\t}\n+\tout->nr = o;\n+}\n+\n+/*\n+ * Difference of range sets (out = a \\ b). Pass the \"interesting\"\n+ * ranges as 'a' and the target side of the diff as 'b': it removes\n+ * the ranges for which the commit is responsible.\n+ */\n+static void range_set_difference(struct range_set *out,\n+\t\t\t\t struct range_set *a, struct range_set *b)\n+{\n+\tint i, j = 0;\n+\tfor (i = 0; i < a->nr; i++) {\n+\t\tlong start = a->ranges[i].start;\n+\t\tlong end = a->ranges[i].end;\n+\t\twhile (start < end) {\n+\t\t\twhile (j < b->nr && start >= b->ranges[j].end)\n+\t\t\t\t/*\n+\t\t\t\t * a: |-------\n+\t\t\t\t * b: ------|\n+\t\t\t\t */\n+\t\t\t\tj++;\n+\t\t\tif (j >= b->nr || end < b->ranges[j].start) {\n+\t\t\t\t/*\n+\t\t\t\t * b exhausted, or\n+\t\t\t\t * a: ----|\n+\t\t\t\t * b: |----\n+\t\t\t\t */\n+\t\t\t\trange_set_append(out, start, end);\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif (start >= b->ranges[j].start) {\n+\t\t\t\t/*\n+\t\t\t\t * a: |--????\n+\t\t\t\t * b: |------|\n+\t\t\t\t */\n+\t\t\t\tstart = b->ranges[j].end;\n+\t\t\t} else if (end > b->ranges[j].start) {\n+\t\t\t\t/*\n+\t\t\t\t * a: |-----|\n+\t\t\t\t * b: |--?????\n+\t\t\t\t */\n+\t\t\t\tif (start < b->ranges[j].start)\n+\t\t\t\t\trange_set_append(out, start, b->ranges[j].start);\n+\t\t\t\tstart = b->ranges[j].end;\n+\t\t\t}\n+\t\t}\n+\t}\n+}\n+\n+static void diff_ranges_init(struct diff_ranges *diff)\n+{\n+\trange_set_init(&diff->parent, 0);\n+\trange_set_init(&diff->target, 0);\n+}\n+\n+static void diff_ranges_release(struct diff_ranges *diff)\n+{\n+\trange_set_release(&diff->parent);\n+\trange_set_release(&diff->target);\n+}\n+\n+void line_log_data_init(struct line_log_data *r)\n+{\n+\tmemset(r, 0, sizeof(struct line_log_data));\n+\trange_set_init(&r->ranges, 0);\n+}\n+\n+static void line_log_data_clear(struct line_log_data *r)\n+{\n+\trange_set_release(&r->ranges);\n+\tif (r->pair)\n+\t\tdiff_free_filepair(r->pair);\n+}\n+\n+static void free_line_log_data(struct line_log_data *r)\n+{\n+\twhile (r) {\n+\t\tstruct line_log_data *next = r->next;\n+\t\tline_log_data_clear(r);\n+\t\tfree(r);\n+\t\tr = next;\n+\t}\n+}\n+\n+static struct line_log_data *\n+search_line_log_data(struct line_log_data *list, const char *path,\n+\t\t struct line_log_data **insertion_point)\n+{\n+\tstruct line_log_data *p = list;\n+\tif (insertion_point)\n+\t\t*insertion_point = NULL;\n+\twhile (p) {\n+\t\tint cmp = strcmp(p->spec->path, path);\n+\t\tif (!cmp)\n+\t\t\treturn p;\n+\t\tif (insertion_point && cmp < 0)\n+\t\t\t*insertion_point = p;\n+\t\tp = p->next;\n+\t}\n+\treturn NULL;\n+}\n+\n+static void line_log_data_insert(struct line_log_data **list,\n+\t\t\t\t struct diff_filespec *spec,\n+\t\t\t\t long begin, long end)\n+{\n+\tstruct line_log_data *ip;\n+\tstruct line_log_data *p = search_line_log_data(*list, spec->path, &ip);\n+\n+\tif (p) {\n+\t\trange_set_append(&p->ranges, begin, end);\n+\t\tsort_and_merge_range_set(&p->ranges);\n+\t\tfree_filespec(spec);\n+\t\treturn;\n+\t}\n+\n+\tp = xcalloc(1, sizeof(struct line_log_data));\n+\tp->spec = spec;\n+\trange_set_append(&p->ranges, begin, end);\n+\tif (ip) {\n+\t\tp->next = ip->next;\n+\t\tip->next = p;\n+\t} else {\n+\t\tp->next = *list;\n+\t\t*list = p;\n+\t}\n+}\n+\n+struct collect_diff_cbdata {\n+\tstruct diff_ranges *diff;\n+};\n+\n+static int collect_diff_cb(long start_a, long count_a,\n+\t\t\t long start_b, long count_b,\n+\t\t\t void *data)\n+{\n+\tstruct collect_diff_cbdata *d = data;\n+\n+\tif (count_a >= 0)\n+\t\trange_set_append(&d->diff->parent, start_a, start_a + count_a);\n+\tif (count_b >= 0)\n+\t\trange_set_append(&d->diff->target, start_b, start_b + count_b);\n+\n+\treturn 0;\n+}\n+\n+static void collect_diff(mmfile_t *parent, mmfile_t *target, struct diff_ranges *out)\n+{\n+\tstruct collect_diff_cbdata cbdata = {NULL};\n+\txpparam_t xpp;\n+\txdemitconf_t xecfg;\n+\txdemitcb_t ecb;\n+\n+\tmemset(&xpp, 0, sizeof(xpp));\n+\tmemset(&xecfg, 0, sizeof(xecfg));\n+\txecfg.ctxlen = xecfg.interhunkctxlen = 0;\n+\n+\tcbdata.diff = out;\n+\txecfg.hunk_func = collect_diff_cb;\n+\tmemset(&ecb, 0, sizeof(ecb));\n+\tecb.priv = &cbdata;\n+\txdi_diff(parent, target, &xpp, &xecfg, &ecb);\n+}\n+\n+/*\n+ * These are handy for debugging. Removing them with #if 0 silences\n+ * the \"unused function\" warning.\n+ */\n+#if 0\n+static void dump_range_set(struct range_set *rs, const char *desc)\n+{\n+\tint i;\n+\tprintf(\"range set %s (%d items):\\n\", desc, rs->nr);\n+\tfor (i = 0; i < rs->nr; i++)\n+\t\tprintf(\"\\t[%ld,%ld]\\n\", rs->ranges[i].start, rs->ranges[i].end);\n+}\n+\n+static void dump_line_log_data(struct line_log_data *r)\n+{\n+\tchar buf[4096];\n+\twhile (r) {\n+\t\tsnprintf(buf, 4096, \"file %s\\n\", r->spec->path);\n+\t\tdump_range_set(&r->ranges, buf);\n+\t\tr = r->next;\n+\t}\n+}\n+\n+static void dump_diff_ranges(struct diff_ranges *diff, const char *desc)\n+{\n+\tint i;\n+\tassert(diff->parent.nr == diff->target.nr);\n+\tprintf(\"diff ranges %s (%d items):\\n\", desc, diff->parent.nr);\n+\tprintf(\"\\tparent\\ttarget\\n\");\n+\tfor (i = 0; i < diff->parent.nr; i++) {\n+\t\tprintf(\"\\t[%ld,%ld]\\t[%ld,%ld]\\n\",\n+\t\t diff->parent.ranges[i].start,\n+\t\t diff->parent.ranges[i].end,\n+\t\t diff->target.ranges[i].start,\n+\t\t diff->target.ranges[i].end);\n+\t}\n+}\n+#endif\n+\n+\n+static int ranges_overlap(struct range *a, struct range *b)\n+{\n+\treturn !(a->end <= b->start || b->end <= a->start);\n+}\n+\n+/*\n+ * Given a diff and the set of interesting ranges, determine all hunks\n+ * of the diff which touch (overlap) at least one of the interesting\n+ * ranges in the target.\n+ */\n+static void diff_ranges_filter_touched(struct diff_ranges *out,\n+\t\t\t\t struct diff_ranges *diff,\n+\t\t\t\t struct range_set *rs)\n+{\n+\tint i, j = 0;\n+\n+\tassert(out->target.nr == 0);\n+\n+\tfor (i = 0; i < diff->target.nr; i++) {\n+\t\twhile (diff->target.ranges[i].start > rs->ranges[j].end) {\n+\t\t\tj++;\n+\t\t\tif (j == rs->nr)\n+\t\t\t\treturn;\n+\t\t}\n+\t\tif (ranges_overlap(&diff->target.ranges[i], &rs->ranges[j])) {\n+\t\t\trange_set_append(&out->parent,\n+\t\t\t\t\t diff->parent.ranges[i].start,\n+\t\t\t\t\t diff->parent.ranges[i].end);\n+\t\t\trange_set_append(&out->target,\n+\t\t\t\t\t diff->target.ranges[i].start,\n+\t\t\t\t\t diff->target.ranges[i].end);\n+\t\t}\n+\t}\n+}\n+\n+/*\n+ * Adjust the line counts in 'rs' to account for the lines\n+ * added/removed in the diff.\n+ */\n+static void range_set_shift_diff(struct range_set *out,\n+\t\t\t\t struct range_set *rs,\n+\t\t\t\t struct diff_ranges *diff)\n+{\n+\tint i, j = 0;\n+\tlong offset = 0;\n+\tstruct range *src = rs->ranges;\n+\tstruct range *target = diff->target.ranges;\n+\tstruct range *parent = diff->parent.ranges;\n+\n+\tfor (i = 0; i < rs->nr; i++) {\n+\t\twhile (j < diff->target.nr && src[i].start >= target[j].start) {\n+\t\t\toffset += (parent[j].end-parent[j].start)\n+\t\t\t\t- (target[j].end-target[j].start);\n+\t\t\tj++;\n+\t\t}\n+\t\trange_set_append(out, src[i].start+offset, src[i].end+offset);\n+\t}\n+}\n+\n+/*\n+ * Given a diff and the set of interesting ranges, map the ranges\n+ * across the diff. That is: observe that the target commit takes\n+ * blame for all the + (target-side) ranges. So for every pair of\n+ * ranges in the diff that was touched, we remove the latter and add\n+ * its parent side.\n+ */\n+static void range_set_map_across_diff(struct range_set *out,\n+\t\t\t\t struct range_set *rs,\n+\t\t\t\t struct diff_ranges *diff,\n+\t\t\t\t struct diff_ranges **touched_out)\n+{\n+\tstruct diff_ranges *touched = xmalloc(sizeof(*touched));\n+\tstruct range_set tmp1 = RANGE_SET_INIT;\n+\tstruct range_set tmp2 = RANGE_SET_INIT;\n+\n+\tdiff_ranges_init(touched);\n+\tdiff_ranges_filter_touched(touched, diff, rs);\n+\trange_set_difference(&tmp1, rs, &touched->target);\n+\trange_set_shift_diff(&tmp2, &tmp1, diff);\n+\trange_set_union(out, &tmp2, &touched->parent);\n+\trange_set_release(&tmp1);\n+\trange_set_release(&tmp2);\n+\n+\t*touched_out = touched;\n+}\n+\n+\n+static struct commit *check_single_commit(struct rev_info *revs)\n+{\n+\tstruct object *commit = NULL;\n+\tint found = -1;\n+\tint i;\n+\n+\tfor (i = 0; i < revs->pending.nr; i++) {\n+\t\tstruct object *obj = revs->pending.objects[i].item;\n+\t\tif (obj->flags & UNINTERESTING)\n+\t\t\tcontinue;\n+\t\twhile (obj->type == OBJ_TAG)\n+\t\t\tobj = deref_tag(obj, NULL, 0);\n+\t\tif (obj->type != OBJ_COMMIT)\n+\t\t\tdie(\"Non commit %s?\", revs->pending.objects[i].name);\n+\t\tif (commit)\n+\t\t\tdie(\"More than one commit to dig from: %s and %s?\",\n+\t\t\t revs->pending.objects[i].name,\n+\t\t\t revs->pending.objects[found].name);\n+\t\tcommit = obj;\n+\t\tfound = i;\n+\t}\n+\n+\tif (!commit)\n+\t\tdie(\"No commit specified?\");\n+\n+\treturn (struct commit *) commit;\n+}\n+\n+static void fill_blob_sha1(struct commit *commit, struct diff_filespec *spec)\n+{\n+\tunsigned mode;\n+\tunsigned char sha1[20];\n+\n+\tif (get_tree_entry(commit->object.sha1, spec->path,\n+\t\t\t sha1, &mode))\n+\t\tdie(\"There is no path %s in the commit\", spec->path);\n+\tfill_filespec(spec, sha1, 1, mode);\n+\n+\treturn;\n+}\n+\n+static void fill_line_ends(struct diff_filespec *spec, long *lines,\n+\t\t\t unsigned long **line_ends)\n+{\n+\tint num = 0, size = 50;\n+\tlong cur = 0;\n+\tunsigned long *ends = NULL;\n+\tchar *data = NULL;\n+\n+\tif (diff_populate_filespec(spec, 0))\n+\t\tdie(\"Cannot read blob %s\", sha1_to_hex(spec->sha1));\n+\n+\tends = xmalloc(size * sizeof(*ends));\n+\tends[cur++] = 0;\n+\tdata = spec->data;\n+\twhile (num < spec->size) {\n+\t\tif (data[num] == '\\n' || num == spec->size - 1) {\n+\t\t\tALLOC_GROW(ends, (cur + 1), size);\n+\t\t\tends[cur++] = num;\n+\t\t}\n+\t\tnum++;\n+\t}\n+\n+\t/* shrink the array to fit the elements */\n+\tends = xrealloc(ends, cur * sizeof(*ends));\n+\t*lines = cur-1;\n+\t*line_ends = ends;\n+}\n+\n+struct nth_line_cb {\n+\tstruct diff_filespec *spec;\n+\tlong lines;\n+\tunsigned long *line_ends;\n+};\n+\n+static const char *nth_line(void *data, long line)\n+{\n+\tstruct nth_line_cb *d = data;\n+\tassert(d && line <= d->lines);\n+\tassert(d->spec && d->spec->data);\n+\n+\tif (line == 0)\n+\t\treturn (char *)d->spec->data;\n+\telse\n+\t\treturn (char *)d->spec->data + d->line_ends[line] + 1;\n+}\n+\n+static struct line_log_data *\n+parse_lines(struct commit *commit, const char *prefix, struct string_list *args)\n+{\n+\tlong lines = 0;\n+\tunsigned long *ends = NULL;\n+\tstruct nth_line_cb cb_data;\n+\tstruct string_list_item *item;\n+\tstruct line_log_data *ranges = NULL;\n+\n+\tfor_each_string_list_item(item, args) {\n+\t\tconst char *name_part, *range_part;\n+\t\tconst char *full_name;\n+\t\tstruct diff_filespec *spec;\n+\t\tlong begin = 0, end = 0;\n+\n+\t\tname_part = skip_range_arg(item->string);\n+\t\tif (!name_part || *name_part != ':')\n+\t\t\tdie(\"-L argument '%s' not of the form start,end:file\",\n+\t\t\t item->string);\n+\t\trange_part = xstrndup(item->string, name_part - item->string);\n+\t\tname_part++;\n+\n+\t\tfull_name = prefix_path(prefix, prefix ? strlen(prefix) : 0,\n+\t\t\t\t\tname_part);\n+\n+\t\tspec = alloc_filespec(full_name);\n+\t\tfill_blob_sha1(commit, spec);\n+\t\tfill_line_ends(spec, &lines, &ends);\n+\t\tcb_data.spec = spec;\n+\t\tcb_data.lines = lines;\n+\t\tcb_data.line_ends = ends;\n+\n+\t\tif (parse_range_arg(range_part, nth_line, &cb_data,\n+\t\t\t\t lines, &begin, &end))\n+\t\t\tdie(\"malformed -L argument '%s'\", range_part);\n+\t\tif (begin < 1)\n+\t\t\tbegin = 1;\n+\t\tif (end < 1)\n+\t\t\tend = lines;\n+\t\tbegin--;\n+\t\tif (lines < end || lines < begin)\n+\t\t\tdie(\"file %s has only %ld lines\", name_part, lines);\n+\t\tline_log_data_insert(&ranges, spec, begin, end);\n+\n+\t\tfree(ends);\n+\t\tends = NULL;\n+\t}\n+\n+\treturn ranges;\n+}\n+\n+static struct line_log_data *line_log_data_copy_one(struct line_log_data *r)\n+{\n+\tstruct line_log_data *ret = xmalloc(sizeof(*ret));\n+\n+\tassert(r);\n+\tline_log_data_init(ret);\n+\trange_set_copy(&ret->ranges, &r->ranges);\n+\n+\tret->spec = r->spec;\n+\tassert(ret->spec);\n+\tret->spec->count++;\n+\n+\treturn ret;\n+}\n+\n+static struct line_log_data *\n+line_log_data_copy(struct line_log_data *r)\n+{\n+\tstruct line_log_data *ret = NULL;\n+\tstruct line_log_data *tmp = NULL, *prev = NULL;\n+\n+\tassert(r);\n+\tret = tmp = prev = line_log_data_copy_one(r);\n+\tr = r->next;\n+\twhile (r) {\n+\t\ttmp = line_log_data_copy_one(r);\n+\t\tprev->next = tmp;\n+\t\tprev = tmp;\n+\t\tr = r->next;\n+\t}\n+\n+\treturn ret;\n+}\n+\n+/* merge two range sets across files */\n+static struct line_log_data *line_log_data_merge(struct line_log_data *a,\n+\t\t\t\t\t\t struct line_log_data *b)\n+{\n+\tstruct line_log_data *head = NULL, **pp = &head;\n+\n+\twhile (a || b) {\n+\t\tstruct line_log_data *src;\n+\t\tstruct line_log_data *src2 = NULL;\n+\t\tstruct line_log_data *d;\n+\t\tint cmp;\n+\t\tif (!a)\n+\t\t\tcmp = 1;\n+\t\telse if (!b)\n+\t\t\tcmp = -1;\n+\t\telse\n+\t\t\tcmp = strcmp(a->spec->path, b->spec->path);\n+\t\tif (cmp < 0) {\n+\t\t\tsrc = a;\n+\t\t\ta = a->next;\n+\t\t} else if (cmp == 0) {\n+\t\t\tsrc = a;\n+\t\t\ta = a->next;\n+\t\t\tsrc2 = b;\n+\t\t\tb = b->next;\n+\t\t} else {\n+\t\t\tsrc = b;\n+\t\t\tb = b->next;\n+\t\t}\n+\t\td = xmalloc(sizeof(struct line_log_data));\n+\t\tline_log_data_init(d);\n+\t\td->spec = src->spec;\n+\t\td->spec->count++;\n+\t\t*pp = d;\n+\t\tpp = &d->next;\n+\t\tif (src2)\n+\t\t\trange_set_union(&d->ranges, &src->ranges, &src2->ranges);\n+\t\telse\n+\t\t\trange_set_copy(&d->ranges, &src->ranges);\n+\t}\n+\n+\treturn head;\n+}\n+\n+static void add_line_range(struct rev_info *revs, struct commit *commit,\n+\t\t\t struct line_log_data *range)\n+{\n+\tstruct line_log_data *old = NULL;\n+\tstruct line_log_data *new = NULL;\n+\n+\told = lookup_decoration(&revs->line_log_data, &commit->object);\n+\tif (old && range) {\n+\t\tnew = line_log_data_merge(old, range);\n+\t\tfree_line_log_data(old);\n+\t} else if (range)\n+\t\tnew = line_log_data_copy(range);\n+\n+\tif (new)\n+\t\tadd_decoration(&revs->line_log_data, &commit->object, new);\n+}\n+\n+static void clear_commit_line_range(struct rev_info *revs, struct commit *commit)\n+{\n+\tstruct line_log_data *r;\n+\tr = lookup_decoration(&revs->line_log_data, &commit->object);\n+\tif (!r)\n+\t\treturn;\n+\tfree_line_log_data(r);\n+\tadd_decoration(&revs->line_log_data, &commit->object, NULL);\n+}\n+\n+static struct line_log_data *lookup_line_range(struct rev_info *revs,\n+\t\t\t\t\t struct commit *commit)\n+{\n+\tstruct line_log_data *ret = NULL;\n+\n+\tret = lookup_decoration(&revs->line_log_data, &commit->object);\n+\treturn ret;\n+}\n+\n+void line_log_init(struct rev_info *rev, const char *prefix, struct string_list *args)\n+{\n+\tstruct commit *commit = NULL;\n+\tstruct line_log_data *range;\n+\n+\tcommit = check_single_commit(rev);\n+\trange = parse_lines(commit, prefix, args);\n+\tadd_line_range(rev, commit, range);\n+\n+\tif (!rev->diffopt.detect_rename) {\n+\t\tint i, count = 0;\n+\t\tstruct line_log_data *r = range;\n+\t\tconst char **paths;\n+\t\twhile (r) {\n+\t\t\tcount++;\n+\t\t\tr = r->next;\n+\t\t}\n+\t\tpaths = xmalloc((count+1)*sizeof(char *));\n+\t\tr = range;\n+\t\tfor (i = 0; i < count; i++) {\n+\t\t\tpaths[i] = xstrdup(r->spec->path);\n+\t\t\tr = r->next;\n+\t\t}\n+\t\tpaths[count] = NULL;\n+\t\tinit_pathspec(&rev->diffopt.pathspec, paths);\n+\t\tfree(paths);\n+\t}\n+}\n+\n+static void load_tree_desc(struct tree_desc *desc, void **tree,\n+\t\t\t const unsigned char *sha1)\n+{\n+\tunsigned long size;\n+\t*tree = read_object_with_reference(sha1, tree_type, &size, NULL);\n+\tif (!*tree)\n+\t\tdie(\"Unable to read tree (%s)\", sha1_to_hex(sha1));\n+\tinit_tree_desc(desc, *tree, size);\n+}\n+\n+static int count_parents(struct commit *commit)\n+{\n+\tstruct commit_list *parents = commit->parents;\n+\tint count = 0;\n+\twhile (parents) {\n+\t\tcount++;\n+\t\tparents = parents->next;\n+\t}\n+\treturn count;\n+}\n+\n+static void move_diff_queue(struct diff_queue_struct *dst,\n+\t\t\t struct diff_queue_struct *src)\n+{\n+\tassert(src != dst);\n+\tmemcpy(dst, src, sizeof(struct diff_queue_struct));\n+\tDIFF_QUEUE_CLEAR(src);\n+}\n+\n+static void queue_diffs(struct diff_options *opt,\n+\t\t\tstruct diff_queue_struct *queue,\n+\t\t\tstruct commit *commit, struct commit *parent)\n+{\n+\tvoid *tree1 = NULL, *tree2 = NULL;\n+\tstruct tree_desc desc1, desc2;\n+\n+\tassert(commit);\n+\tload_tree_desc(&desc2, &tree2, commit->tree->object.sha1);\n+\tif (parent)\n+\t\tload_tree_desc(&desc1, &tree1, parent->tree->object.sha1);\n+\telse\n+\t\tinit_tree_desc(&desc1, \"\", 0);\n+\n+\tDIFF_QUEUE_CLEAR(&diff_queued_diff);\n+\tdiff_tree(&desc1, &desc2, \"\", opt);\n+\tdiffcore_std(opt);\n+\tmove_diff_queue(queue, &diff_queued_diff);\n+\n+\tif (tree1)\n+\t\tfree(tree1);\n+\tif (tree2)\n+\t\tfree(tree2);\n+}\n+\n+static char *get_nth_line(long line, unsigned long *ends, void *data)\n+{\n+\tif (line == 0)\n+\t\treturn (char *)data;\n+\telse\n+\t\treturn (char *)data + ends[line] + 1;\n+}\n+\n+static void print_line(const char *prefix, char first,\n+\t\t long line, unsigned long *ends, void *data,\n+\t\t const char *color, const char *reset)\n+{\n+\tchar *begin = get_nth_line(line, ends, data);\n+\tchar *end = get_nth_line(line+1, ends, data);\n+\tint had_nl = 0;\n+\n+\tif (end > begin && end[-1] == '\\n') {\n+\t\tend--;\n+\t\thad_nl = 1;\n+\t}\n+\n+\tfputs(prefix, stdout);\n+\tfputs(color, stdout);\n+\tputchar(first);\n+\tfwrite(begin, 1, end-begin, stdout);\n+\tfputs(reset, stdout);\n+\tputchar('\\n');\n+\tif (!had_nl)\n+\t\tfputs(\"\\\\ No newline at end of file\\n\", stdout);\n+}\n+\n+static char *output_prefix(struct diff_options *opt)\n+{\n+\tchar *prefix = \"\";\n+\n+\tif (opt->output_prefix) {\n+\t\tstruct strbuf *sb = opt->output_prefix(opt, opt->output_prefix_data);\n+\t\tprefix = sb->buf;\n+\t}\n+\n+\treturn prefix;\n+}\n+\n+static void dump_diff_hacky_one(struct rev_info *rev, struct line_log_data *range)\n+{\n+\tint i, j = 0;\n+\tlong p_lines, t_lines;\n+\tunsigned long *p_ends = NULL, *t_ends = NULL;\n+\tstruct diff_filepair *pair = range->pair;\n+\tstruct diff_ranges *diff = &range->diff;\n+\n+\tstruct diff_options *opt = &rev->diffopt;\n+\tchar *prefix = output_prefix(opt);\n+\tconst char *c_reset = diff_get_color(opt->use_color, DIFF_RESET);\n+\tconst char *c_frag = diff_get_color(opt->use_color, DIFF_FRAGINFO);\n+\tconst char *c_meta = diff_get_color(opt->use_color, DIFF_METAINFO);\n+\tconst char *c_old = diff_get_color(opt->use_color, DIFF_FILE_OLD);\n+\tconst char *c_new = diff_get_color(opt->use_color, DIFF_FILE_NEW);\n+\tconst char *c_plain = diff_get_color(opt->use_color, DIFF_PLAIN);\n+\n+\tif (!pair || !diff)\n+\t\treturn;\n+\n+\tif (pair->one->sha1_valid)\n+\t\tfill_line_ends(pair->one, &p_lines, &p_ends);\n+\tfill_line_ends(pair->two, &t_lines, &t_ends);\n+\n+\tprintf(\"%s%sdiff --git a/%s b/%s%s\\n\", prefix, c_meta, pair->one->path, pair->two->path, c_reset);\n+\tprintf(\"%s%s--- %s%s%s\\n\", prefix, c_meta,\n+\t pair->one->sha1_valid ? \"a/\" : \"\",\n+\t pair->one->sha1_valid ? pair->one->path : \"/dev/null\",\n+\t c_reset);\n+\tprintf(\"%s%s+++ b/%s%s\\n\", prefix, c_meta, pair->two->path, c_reset);\n+\tfor (i = 0; i < range->ranges.nr; i++) {\n+\t\tlong p_start, p_end;\n+\t\tlong t_start = range->ranges.ranges[i].start;\n+\t\tlong t_end = range->ranges.ranges[i].end;\n+\t\tlong t_cur = t_start;\n+\t\tint j_last;\n+\n+\t\twhile (j < diff->target.nr && diff->target.ranges[j].end < t_start)\n+\t\t\tj++;\n+\t\tif (j == diff->target.nr || diff->target.ranges[j].start > t_end)\n+\t\t\tcontinue;\n+\n+\t\t/* Scan ahead to determine the last diff that falls in this range */\n+\t\tj_last = j;\n+\t\twhile (j_last < diff->target.nr && diff->target.ranges[j_last].start < t_end)\n+\t\t\tj_last++;\n+\t\tif (j_last > j)\n+\t\t\tj_last--;\n+\n+\t\t/*\n+\t\t * Compute parent hunk headers: we know that the diff\n+\t\t * has the correct line numbers (but not all hunks).\n+\t\t * So it suffices to shift the start/end according to\n+\t\t * the line numbers of the first/last hunk(s) that\n+\t\t * fall in this range.\n+\t\t */\n+\t\tif (t_start < diff->target.ranges[j].start)\n+\t\t\tp_start = diff->parent.ranges[j].start - (diff->target.ranges[j].start-t_start);\n+\t\telse\n+\t\t\tp_start = diff->parent.ranges[j].start;\n+\t\tif (t_end > diff->target.ranges[j_last].end)\n+\t\t\tp_end = diff->parent.ranges[j_last].end + (t_end-diff->target.ranges[j_last].end);\n+\t\telse\n+\t\t\tp_end = diff->parent.ranges[j_last].end;\n+\n+\t\tif (!p_start && !p_end) {\n+\t\t\tp_start = -1;\n+\t\t\tp_end = -1;\n+\t\t}\n+\n+\t\t/* Now output a diff hunk for this range */\n+\t\tprintf(\"%s%s@@ -%ld,%ld +%ld,%ld @@%s\\n\",\n+\t\t prefix, c_frag,\n+\t\t p_start+1, p_end-p_start, t_start+1, t_end-t_start,\n+\t\t c_reset);\n+\t\twhile (j < diff->target.nr && diff->target.ranges[j].start < t_end) {\n+\t\t\tint k;\n+\t\t\tfor (; t_cur < diff->target.ranges[j].start; t_cur++)\n+\t\t\t\tprint_line(prefix, ' ', t_cur, t_ends, pair->two->data,\n+\t\t\t\t\t c_plain, c_reset);\n+\t\t\tfor (k = diff->parent.ranges[j].start; k < diff->parent.ranges[j].end; k++)\n+\t\t\t\tprint_line(prefix, '-', k, p_ends, pair->one->data,\n+\t\t\t\t\t c_old, c_reset);\n+\t\t\tfor (; t_cur < diff->target.ranges[j].end && t_cur < t_end; t_cur++)\n+\t\t\t\tprint_line(prefix, '+', t_cur, t_ends, pair->two->data,\n+\t\t\t\t\t c_new, c_reset);\n+\t\t\tj++;\n+\t\t}\n+\t\tfor (; t_cur < t_end; t_cur++)\n+\t\t\tprint_line(prefix, ' ', t_cur, t_ends, pair->two->data,\n+\t\t\t\t c_plain, c_reset);\n+\t}\n+\n+\tfree(p_ends);\n+\tfree(t_ends);\n+}\n+\n+/*\n+ * NEEDSWORK: manually building a diff here is not the Right\n+ * Thing(tm). log -L should be built into the diff pipeline.\n+ */\n+static void dump_diff_hacky(struct rev_info *rev, struct line_log_data *range)\n+{\n+\tputs(output_prefix(&rev->diffopt));\n+\twhile (range) {\n+\t\tdump_diff_hacky_one(rev, range);\n+\t\trange = range->next;\n+\t}\n+}\n+\n+/*\n+ * Unlike most other functions, this destructively operates on\n+ * 'range'.\n+ */\n+static int process_diff_filepair(struct rev_info *rev,\n+\t\t\t\t struct diff_filepair *pair,\n+\t\t\t\t struct line_log_data *range,\n+\t\t\t\t struct diff_ranges **diff_out)\n+{\n+\tstruct line_log_data *rg = range;\n+\tstruct range_set tmp;\n+\tstruct diff_ranges diff;\n+\tmmfile_t file_parent, file_target;\n+\n+\tassert(pair->two->path);\n+\twhile (rg) {\n+\t\tassert(rg->spec->path);\n+\t\tif (!strcmp(rg->spec->path, pair->two->path))\n+\t\t\tbreak;\n+\t\trg = rg->next;\n+\t}\n+\n+\tif (!rg)\n+\t\treturn 0;\n+\tif (rg->ranges.nr == 0)\n+\t\treturn 0;\n+\n+\tassert(pair->two->sha1_valid);\n+\tdiff_populate_filespec(pair->two, 0);\n+\tfile_target.ptr = pair->two->data;\n+\tfile_target.size = pair->two->size;\n+\n+\tif (pair->one->sha1_valid) {\n+\t\tdiff_populate_filespec(pair->one, 0);\n+\t\tfile_parent.ptr = pair->one->data;\n+\t\tfile_parent.size = pair->one->size;\n+\t} else {\n+\t\tfile_parent.ptr = \"\";\n+\t\tfile_parent.size = 0;\n+\t}\n+\n+\tdiff_ranges_init(&diff);\n+\tcollect_diff(&file_parent, &file_target, &diff);\n+\n+\t/* NEEDSWORK should apply some heuristics to prevent mismatches */\n+\trg->spec->path = xstrdup(pair->one->path);\n+\n+\trange_set_init(&tmp, 0);\n+\trange_set_map_across_diff(&tmp, &rg->ranges, &diff, diff_out);\n+\trange_set_release(&rg->ranges);\n+\trange_set_move(&rg->ranges, &tmp);\n+\n+\tdiff_ranges_release(&diff);\n+\n+\treturn ((*diff_out)->parent.nr > 0);\n+}\n+\n+static struct diff_filepair *diff_filepair_dup(struct diff_filepair *pair)\n+{\n+\tstruct diff_filepair *new = xmalloc(sizeof(struct diff_filepair));\n+\tnew->one = pair->one;\n+\tnew->two = pair->two;\n+\tnew->one->count++;\n+\tnew->two->count++;\n+\treturn new;\n+}\n+\n+static void free_diffqueues(int n, struct diff_queue_struct *dq)\n+{\n+\tint i, j;\n+\tfor (i = 0; i < n; i++)\n+\t\tfor (j = 0; j < dq[i].nr; j++)\n+\t\t\tdiff_free_filepair(dq[i].queue[j]);\n+\tfree(dq);\n+}\n+\n+static int process_all_files(struct line_log_data **range_out,\n+\t\t\t struct rev_info *rev,\n+\t\t\t struct diff_queue_struct *queue,\n+\t\t\t struct line_log_data *range)\n+{\n+\tint i, changed = 0;\n+\n+\t*range_out = line_log_data_copy(range);\n+\n+\tfor (i = 0; i < queue->nr; i++) {\n+\t\tstruct diff_ranges *pairdiff = NULL;\n+\t\tif (process_diff_filepair(rev, queue->queue[i], *range_out, &pairdiff)) {\n+\t\t\tstruct line_log_data *rg = range;\n+\t\t\tchanged++;\n+\t\t\t/* NEEDSWORK tramples over data structures not owned here */\n+\t\t\twhile (rg && strcmp(rg->spec->path, queue->queue[i]->two->path))\n+\t\t\t\trg = rg->next;\n+\t\t\tassert(rg);\n+\t\t\trg->pair = diff_filepair_dup(queue->queue[i]);\n+\t\t\tmemcpy(&rg->diff, pairdiff, sizeof(struct diff_ranges));\n+\t\t}\n+\t}\n+\n+\treturn changed;\n+}\n+\n+int line_log_print(struct rev_info *rev, struct commit *commit)\n+{\n+\tstruct line_log_data *range = lookup_line_range(rev, commit);\n+\n+\tshow_log(rev);\n+\tdump_diff_hacky(rev, range);\n+\treturn 1;\n+}\n+\n+static int process_ranges_ordinary_commit(struct rev_info *rev, struct commit *commit,\n+\t\t\t\t\t struct line_log_data *range)\n+{\n+\tstruct commit *parent = NULL;\n+\tstruct diff_queue_struct queue;\n+\tstruct line_log_data *parent_range;\n+\tint changed;\n+\n+\tif (commit->parents)\n+\t\tparent = commit->parents->item;\n+\n+\tqueue_diffs(&rev->diffopt, &queue, commit, parent);\n+\tchanged = process_all_files(&parent_range, rev, &queue, range);\n+\tif (parent)\n+\t\tadd_line_range(rev, parent, parent_range);\n+\treturn changed;\n+}\n+\n+static int process_ranges_merge_commit(struct rev_info *rev, struct commit *commit,\n+\t\t\t\t struct line_log_data *range)\n+{\n+\tstruct diff_queue_struct *diffqueues;\n+\tstruct line_log_data **cand;\n+\tstruct commit **parents;\n+\tstruct commit_list *p;\n+\tint i;\n+\tint nparents = count_parents(commit);\n+\n+\tdiffqueues = xmalloc(nparents * sizeof(*diffqueues));\n+\tcand = xmalloc(nparents * sizeof(*cand));\n+\tparents = xmalloc(nparents * sizeof(*parents));\n+\n+\tp = commit->parents;\n+\tfor (i = 0; i < nparents; i++) {\n+\t\tparents[i] = p->item;\n+\t\tp = p->next;\n+\t\tqueue_diffs(&rev->diffopt, &diffqueues[i], commit, parents[i]);\n+\t}\n+\n+\tfor (i = 0; i < nparents; i++) {\n+\t\tint changed;\n+\t\tcand[i] = NULL;\n+\t\tchanged = process_all_files(&cand[i], rev, &diffqueues[i], range);\n+\t\tif (!changed) {\n+\t\t\t/*\n+\t\t\t * This parent can take all the blame, so we\n+\t\t\t * don't follow any other path in history\n+\t\t\t */\n+\t\t\tadd_line_range(rev, parents[i], cand[i]);\n+\t\t\tclear_commit_line_range(rev, commit);\n+\t\t\tcommit->parents = xmalloc(sizeof(struct commit_list));\n+\t\t\tcommit->parents->item = parents[i];\n+\t\t\tcommit->parents->next = NULL;\n+\t\t\tfree(parents);\n+\t\t\tfree(cand);\n+\t\t\tfree_diffqueues(nparents, diffqueues);\n+\t\t\t/* NEEDSWORK leaking like a sieve */\n+\t\t\treturn 0;\n+\t\t}\n+\t}\n+\n+\t/*\n+\t * No single parent took the blame. We add the candidates\n+\t * from the above loop to the parents.\n+\t */\n+\tfor (i = 0; i < nparents; i++) {\n+\t\tadd_line_range(rev, parents[i], cand[i]);\n+\t}\n+\n+\tclear_commit_line_range(rev, commit);\n+\tfree(parents);\n+\tfree(cand);\n+\tfree_diffqueues(nparents, diffqueues);\n+\treturn 1;\n+\n+\t/* NEEDSWORK evil merge detection stuff */\n+\t/* NEEDSWORK leaking like a sieve */\n+}\n+\n+static int process_ranges_arbitrary_commit(struct rev_info *rev, struct commit *commit)\n+{\n+\tstruct line_log_data *range = lookup_line_range(rev, commit);\n+\tint changed = 0;\n+\n+\tif (range) {\n+\t\tif (!commit->parents || !commit->parents->next)\n+\t\t\tchanged = process_ranges_ordinary_commit(rev, commit, range);\n+\t\telse\n+\t\t\tchanged = process_ranges_merge_commit(rev, commit, range);\n+\t}\n+\n+\tif (!changed)\n+\t\tcommit->object.flags |= TREESAME;\n+\n+\treturn changed;\n+}\n+\n+static enum rewrite_result line_log_rewrite_one(struct rev_info *rev, struct commit **pp)\n+{\n+\tfor (;;) {\n+\t\tstruct commit *p = *pp;\n+\t\tif (p->parents && p->parents->next)\n+\t\t\treturn rewrite_one_ok;\n+\t\tif (p->object.flags & UNINTERESTING)\n+\t\t\treturn rewrite_one_ok;\n+\t\tif (!(p->object.flags & TREESAME))\n+\t\t\treturn rewrite_one_ok;\n+\t\tif (!p->parents)\n+\t\t\treturn rewrite_one_noparents;\n+\t\t*pp = p->parents->item;\n+\t}\n+}\n+\n+int line_log_filter(struct rev_info *rev)\n+{\n+\tstruct commit *commit;\n+\tstruct commit_list *list = rev->commits;\n+\tstruct commit_list *out = NULL, **pp = &out;\n+\n+\twhile (list) {\n+\t\tstruct commit_list *to_free = NULL;\n+\t\tcommit = list->item;\n+\t\tif (process_ranges_arbitrary_commit(rev, commit)) {\n+\t\t\t*pp = list;\n+\t\t\tpp = &list->next;\n+\t\t} else\n+\t\t\tto_free = list;\n+\t\tlist = list->next;\n+\t\tfree(to_free);\n+\t}\n+\t*pp = NULL;\n+\n+\tfor (list = out; list; list = list->next)\n+\t\trewrite_parents(rev, list->item, line_log_rewrite_one);\n+\n+\trev->commits = out;\n+\n+\treturn 0;\n+}\ndiff --git a/line-log.h b/line-log.h\nnew file mode 100644\nindex 0000000..9acd123\n--- /dev/null\n+++ b/line-log.h\n@@ -0,0 +1,49 @@\n+#ifndef LINE_LOG_H\n+#define LINE_LOG_H\n+\n+#include \"diffcore.h\"\n+\n+struct rev_info;\n+struct commit;\n+\n+/* A range [start,end]. Lines are numbered starting at 0, and the\n+ * ranges include start but exclude end. */\n+struct range {\n+\tlong start, end;\n+};\n+\n+/* A set of ranges. The ranges must always be disjoint and sorted. */\n+struct range_set {\n+\tint alloc, nr;\n+\tstruct range *ranges;\n+};\n+\n+/* A diff, encoded as the set of pre- and post-image ranges where the\n+ * files differ. A pair of ranges corresponds to a hunk. */\n+struct diff_ranges {\n+\tstruct range_set parent;\n+\tstruct range_set target;\n+};\n+\n+/* Linked list of interesting files and their associated ranges. The\n+ * list must be kept sorted by spec->path */\n+struct line_log_data {\n+\tstruct line_log_data *next;\n+\tstruct diff_filespec *spec;\n+\tchar status;\n+\tstruct range_set ranges;\n+\tint arg_alloc, arg_nr;\n+\tconst char **args;\n+\tstruct diff_filepair *pair;\n+\tstruct diff_ranges diff;\n+};\n+\n+extern void line_log_data_init(struct line_log_data *r);\n+\n+extern void line_log_init(struct rev_info *rev, const char *prefix, struct string_list *args);\n+\n+extern int line_log_filter(struct rev_info *rev);\n+\n+extern int line_log_print(struct rev_info *rev, struct commit *commit);\n+\n+#endif /* LINE_LOG_H */\ndiff --git a/line-range.c b/line-range.c\nindex 0af43bf..d0c7dac 100644\n--- a/line-range.c\n+++ b/line-range.c\n@@ -21,6 +21,8 @@ static const char *parse_loc(const char *spec, nth_line_fn_t nth_line,\n \tif (1 < begin && (spec[0] == '+' || spec[0] == '-')) {\n \t\tnum = strtol(spec + 1, &term, 10);\n \t\tif (term != spec + 1) {\n+\t\t\tif (!ret)\n+\t\t\t\treturn term;\n \t\t\tif (spec[0] == '-')\n \t\t\t\tnum = 0 - num;\n \t\t\tif (0 < num)\n@@ -35,7 +37,8 @@ static const char *parse_loc(const char *spec, nth_line_fn_t nth_line,\n \t}\n \tnum = strtol(spec, &term, 10);\n \tif (term != spec) {\n-\t\t*ret = num;\n+\t\tif (ret)\n+\t\t\t*ret = num;\n \t\treturn term;\n \t}\n \tif (spec[0] != '/')\n@@ -49,6 +52,10 @@ static const char *parse_loc(const char *spec, nth_line_fn_t nth_line,\n \tif (*term != '/')\n \t\treturn spec;\n \n+\t/* in the scan-only case we are not interested in the regex */\n+\tif (!ret)\n+\t\treturn term+1;\n+\n \t/* try [spec+1 .. term-1] as regexp */\n \t*term = 0;\n \tbegin--; /* input is in human terms */\n@@ -90,3 +97,13 @@ int parse_range_arg(const char *arg, nth_line_fn_t nth_line_cb,\n \n \treturn 0;\n }\n+\n+const char *skip_range_arg(const char *arg)\n+{\n+\targ = parse_loc(arg, NULL, NULL, 0, -1, NULL);\n+\n+\tif (*arg == ',')\n+\t\targ = parse_loc(arg+1, NULL, NULL, 0, 0, NULL);\n+\n+\treturn arg;\n+}\ndiff --git a/line-range.h b/line-range.h\nindex 830f25b..88aaf08 100644\n--- a/line-range.h\n+++ b/line-range.h\n@@ -21,4 +21,15 @@ extern int parse_range_arg(const char *arg,\n \t\t\t void *cb_data, long lines,\n \t\t\t long *begin, long *end);\n \n+/*\n+ * Scan past a range argument that could be parsed by\n+ * 'parse_range_arg', to help the caller determine the start of the\n+ * filename in '-L n,m:file' syntax.\n+ *\n+ * Returns a pointer to the first character after the 'n,m' part, or\n+ * NULL in case the argument is obviously malformed.\n+ */\n+\n+extern const char *skip_range_arg(const char *arg);\n+\n #endif /* LINE_RANGE_H */\ndiff --git a/log-tree.c b/log-tree.c\nindex 5dc45c4..793d2c8 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -9,6 +9,7 @@\n #include \"string-list.h\"\n #include \"color.h\"\n #include \"gpg-interface.h\"\n+#include \"line-log.h\"\n \n struct decoration name_decoration = { \"object names\" };\n \n@@ -856,6 +857,9 @@ int log_tree_commit(struct rev_info *opt, struct commit *commit)\n \tlog.parent = NULL;\n \topt->loginfo = &log;\n \n+\tif (opt->line_level_traverse)\n+\t\treturn line_log_print(opt, commit);\n+\n \tshown = log_tree_diff(opt, commit, &log);\n \tif (!shown && opt->loginfo && opt->always_show_header) {\n \t\tlog.parent = NULL;\ndiff --git a/revision.c b/revision.c\nindex 46319d5..3ad9d08 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -13,6 +13,7 @@\n #include \"decorate.h\"\n #include \"log-tree.h\"\n #include \"string-list.h\"\n+#include \"line-log.h\"\n #include \"mailmap.h\"\n \n volatile show_early_output_fn_t show_early_output;\n@@ -1896,6 +1897,12 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s\n \tif (revs->combine_merges)\n \t\trevs->ignore_merges = 0;\n \trevs->diffopt.abbrev = revs->abbrev;\n+\n+\tif (revs->line_level_traverse) {\n+\t\trevs->limited = 1;\n+\t\trevs->topo_order = 1;\n+\t}\n+\n \tdiff_setup_done(&revs->diffopt);\n \n \tgrep_commit_pattern_type(GREP_PATTERN_TYPE_UNSPECIFIED,\n@@ -2166,6 +2173,8 @@ int prepare_revision_walk(struct rev_info *revs)\n \t\t\treturn -1;\n \tif (revs->topo_order)\n \t\tsort_in_topological_order(&revs->commits, revs->lifo);\n+\tif (revs->line_level_traverse)\n+\t\tline_log_filter(revs);\n \tif (revs->simplify_merges)\n \t\tsimplify_merges(revs);\n \tif (revs->children.name)\ndiff --git a/revision.h b/revision.h\nindex 640110d..6b2870c 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -96,7 +96,8 @@ struct rev_info {\n \t\t\tcherry_mark:1,\n \t\t\tbisect:1,\n \t\t\tancestry_path:1,\n-\t\t\tfirst_parent_only:1;\n+\t\t\tfirst_parent_only:1,\n+\t\t\tline_level_traverse:1;\n \n \t/* Diff flags */\n \tunsigned int\tdiff:1,\n@@ -175,6 +176,9 @@ struct rev_info {\n \tint count_left;\n \tint count_right;\n \tint count_same;\n+\n+\t/* line level range that we are chasing */\n+\tstruct decoration line_log_data;\n };\n \n #define REV_TREE_SAME\t\t0\ndiff --git a/t/perf/p4211-line-log.sh b/t/perf/p4211-line-log.sh\nnew file mode 100755\nindex 0000000..3d074b0\n--- /dev/null\n+++ b/t/perf/p4211-line-log.sh\n@@ -0,0 +1,34 @@\n+#!/bin/sh\n+\n+test_description='Tests log -L performance'\n+. ./perf-lib.sh\n+\n+test_perf_default_repo\n+\n+# Pick a file to log pseudo-randomly. The sort key is the blob hash,\n+# so it is stable.\n+test_expect_success 'select a file' '\n+\tgit ls-tree HEAD | grep ^100644 |\n+\tsort -k 3 | head -1 | cut -f 2 >filelist\n+'\n+\n+file=$(cat filelist)\n+export file\n+\n+test_perf 'git rev-list --topo-order (baseline)' '\n+\tgit rev-list --topo-order HEAD >/dev/null\n+'\n+\n+test_perf 'git log --follow (baseline for -M)' '\n+\tgit log --oneline --follow -- \"$file\" >/dev/null\n+'\n+\n+test_perf 'git log -L' '\n+\tgit log -L 1:\"$file\" >/dev/null\n+'\n+\n+test_perf 'git log -M -L' '\n+\tgit log -M -L 1:\"$file\" >/dev/null\n+'\n+\n+test_done\ndiff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\nnew file mode 100755\nindex 0000000..286390d\n--- /dev/null\n+++ b/t/t4211-line-log.sh\n@@ -0,0 +1,38 @@\n+#!/bin/sh\n+\n+test_description='test log -L'\n+. ./test-lib.sh\n+\n+test_expect_success 'setup (import history)' '\n+\tgit fast-import < \"$TEST_DIRECTORY\"/t4211/history.export &&\n+\tgit reset --hard\n+'\n+\n+canned_test () {\n+\ttest_expect_success \"$1\" \"\n+\t\tgit log $1 >actual &&\n+\t\ttest_cmp \\\"\\$TEST_DIRECTORY\\\"/t4211/expect.$2 actual\n+\t\"\n+}\n+\n+canned_test \"-L 4,12:a.c simple\" simple-f\n+canned_test \"-L 4,+9:a.c simple\" simple-f\n+canned_test \"-L '/long f/,/^}/:a.c' simple\" simple-f\n+\n+canned_test \"-L '/main/,/^}/:a.c' simple\" simple-main\n+\n+canned_test \"-L 1,+4:a.c simple\" beginning-of-file\n+\n+canned_test \"-L 20:a.c simple\" end-of-file\n+\n+test_expect_success \"-L 20,10000:a.c (bogus end)\" '\n+\ttest_must_fail git log -L 20,10000:a.c simple 2>errors &&\n+\tgrep \"has only.*lines\" errors\n+'\n+\n+canned_test \"-L '/long f/',/^}/:a.c -L /main/,/^}/:a.c simple\" two-ranges\n+canned_test \"-L 24,+1:a.c simple\" vanishes-early\n+\n+canned_test \"-L '/long f/,/^}/:b.c' move-support\" move-support-f\n+\n+test_done\ndiff --git a/t/t4211/expect.beginning-of-file b/t/t4211/expect.beginning-of-file\nnew file mode 100644\nindex 0000000..91b4054\n--- /dev/null\n+++ b/t/t4211/expect.beginning-of-file\n@@ -0,0 +1,43 @@\n+commit 4a23ae5c98d59a58c6da036156959f2dc9f472ad\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:47:40 2013 +0100\n+\n+ change at very beginning\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -1,3 +1,4 @@\n++#include \n+ #include \n+ \n+ long f(long x)\n+\n+commit a6eb82647d5d67f893da442f8f9375fd89a3b1e2\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:45:16 2013 +0100\n+\n+ touch both functions\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -1,3 +1,3 @@\n+ #include \n+ \n+-int f(int x)\n++long f(long x)\n+\n+commit de4c48ae814792c02a49c4c3c0c757ae69c55f6a\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:44:48 2013 +0100\n+\n+ initial\n+\n+diff --git a/a.c b/a.c\n+--- /dev/null\n++++ b/a.c\n+@@ -0,0 +1,3 @@\n++#include \n++\n++int f(int x)\ndiff --git a/t/t4211/expect.end-of-file b/t/t4211/expect.end-of-file\nnew file mode 100644\nindex 0000000..bd25bb2\n--- /dev/null\n+++ b/t/t4211/expect.end-of-file\n@@ -0,0 +1,62 @@\n+commit 4659538844daa2849b1a9e7d6fadb96fcd26fc83\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:48:43 2013 +0100\n+\n+ change back to complete line\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -20,3 +20,5 @@\n+ \tprintf(\"%ld\\n\", f(15));\n+ \treturn 0;\n+-}\n+\\ No newline at end of file\n++}\n++\n++/* incomplete lines are bad! */\n+\n+commit 100b61a6f2f720f812620a9d10afb3a960ccb73c\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:48:10 2013 +0100\n+\n+ change to an incomplete line at end\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -20,3 +20,3 @@\n+ \tprintf(\"%ld\\n\", f(15));\n+ \treturn 0;\n+-}\n++}\n+\\ No newline at end of file\n+\n+commit a6eb82647d5d67f893da442f8f9375fd89a3b1e2\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:45:16 2013 +0100\n+\n+ touch both functions\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -19,3 +19,3 @@\n+-\tprintf(\"%d\\n\", f(15));\n++\tprintf(\"%ld\\n\", f(15));\n+ \treturn 0;\n+ }\n+\n+commit de4c48ae814792c02a49c4c3c0c757ae69c55f6a\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:44:48 2013 +0100\n+\n+ initial\n+\n+diff --git a/a.c b/a.c\n+--- /dev/null\n++++ b/a.c\n+@@ -0,0 +18,3 @@\n++\tprintf(\"%d\\n\", f(15));\n++\treturn 0;\n++}\ndiff --git a/t/t4211/expect.move-support-f b/t/t4211/expect.move-support-f\nnew file mode 100644\nindex 0000000..78a8cf1\n--- /dev/null\n+++ b/t/t4211/expect.move-support-f\n@@ -0,0 +1,40 @@\n+commit 6ce3c4ff690136099bb17e1a8766b75764726ea7\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:49:50 2013 +0100\n+\n+ another simple change\n+\n+diff --git a/b.c b/b.c\n+--- a/b.c\n++++ b/b.c\n+@@ -4,9 +4,9 @@\n+ long f(long x)\n+ {\n+ \tint s = 0;\n+ \twhile (x) {\n+-\t\tx >>= 1;\n++\t\tx /= 2;\n+ \t\ts++;\n+ \t}\n+ \treturn s;\n+ }\n+\n+commit e6da343666244ea9e67cbe3f3bd26da860f9fe0e\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:49:28 2013 +0100\n+\n+ move file\n+\n+diff --git a/b.c b/b.c\n+--- /dev/null\n++++ b/b.c\n+@@ -0,0 +4,9 @@\n++long f(long x)\n++{\n++\tint s = 0;\n++\twhile (x) {\n++\t\tx >>= 1;\n++\t\ts++;\n++\t}\n++\treturn s;\n++}\ndiff --git a/t/t4211/expect.simple-f b/t/t4211/expect.simple-f\nnew file mode 100644\nindex 0000000..a1f5bc4\n--- /dev/null\n+++ b/t/t4211/expect.simple-f\n@@ -0,0 +1,59 @@\n+commit a6eb82647d5d67f893da442f8f9375fd89a3b1e2\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:45:16 2013 +0100\n+\n+ touch both functions\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -3,9 +3,9 @@\n+-int f(int x)\n++long f(long x)\n+ {\n+ \tint s = 0;\n+ \twhile (x) {\n+ \t\tx >>= 1;\n+ \t\ts++;\n+ \t}\n+ \treturn s;\n+ }\n+\n+commit f04fb20f2c77850996cba739709acc6faecc58f7\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:44:55 2013 +0100\n+\n+ change f()\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -3,8 +3,9 @@\n+ int f(int x)\n+ {\n+ \tint s = 0;\n+ \twhile (x) {\n+ \t\tx >>= 1;\n+ \t\ts++;\n+ \t}\n++\treturn s;\n+ }\n+\n+commit de4c48ae814792c02a49c4c3c0c757ae69c55f6a\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:44:48 2013 +0100\n+\n+ initial\n+\n+diff --git a/a.c b/a.c\n+--- /dev/null\n++++ b/a.c\n+@@ -0,0 +3,8 @@\n++int f(int x)\n++{\n++\tint s = 0;\n++\twhile (x) {\n++\t\tx >>= 1;\n++\t\ts++;\n++\t}\n++}\ndiff --git a/t/t4211/expect.simple-main b/t/t4211/expect.simple-main\nnew file mode 100644\nindex 0000000..39ce39b\n--- /dev/null\n+++ b/t/t4211/expect.simple-main\n@@ -0,0 +1,68 @@\n+commit 4659538844daa2849b1a9e7d6fadb96fcd26fc83\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:48:43 2013 +0100\n+\n+ change back to complete line\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -18,5 +18,5 @@\n+ int main ()\n+ {\n+ \tprintf(\"%ld\\n\", f(15));\n+ \treturn 0;\n+-}\n+\\ No newline at end of file\n++}\n+\n+commit 100b61a6f2f720f812620a9d10afb3a960ccb73c\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:48:10 2013 +0100\n+\n+ change to an incomplete line at end\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -18,5 +18,5 @@\n+ int main ()\n+ {\n+ \tprintf(\"%ld\\n\", f(15));\n+ \treturn 0;\n+-}\n++}\n+\\ No newline at end of file\n+\n+commit a6eb82647d5d67f893da442f8f9375fd89a3b1e2\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:45:16 2013 +0100\n+\n+ touch both functions\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -17,5 +17,5 @@\n+ int main ()\n+ {\n+-\tprintf(\"%d\\n\", f(15));\n++\tprintf(\"%ld\\n\", f(15));\n+ \treturn 0;\n+ }\n+\n+commit de4c48ae814792c02a49c4c3c0c757ae69c55f6a\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:44:48 2013 +0100\n+\n+ initial\n+\n+diff --git a/a.c b/a.c\n+--- /dev/null\n++++ b/a.c\n+@@ -0,0 +16,5 @@\n++int main ()\n++{\n++\tprintf(\"%d\\n\", f(15));\n++\treturn 0;\n++}\ndiff --git a/t/t4211/expect.two-ranges b/t/t4211/expect.two-ranges\nnew file mode 100644\nindex 0000000..6109aa0\n--- /dev/null\n+++ b/t/t4211/expect.two-ranges\n@@ -0,0 +1,102 @@\n+commit 4659538844daa2849b1a9e7d6fadb96fcd26fc83\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:48:43 2013 +0100\n+\n+ change back to complete line\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -18,5 +18,5 @@\n+ int main ()\n+ {\n+ \tprintf(\"%ld\\n\", f(15));\n+ \treturn 0;\n+-}\n+\\ No newline at end of file\n++}\n+\n+commit 100b61a6f2f720f812620a9d10afb3a960ccb73c\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:48:10 2013 +0100\n+\n+ change to an incomplete line at end\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -18,5 +18,5 @@\n+ int main ()\n+ {\n+ \tprintf(\"%ld\\n\", f(15));\n+ \treturn 0;\n+-}\n++}\n+\\ No newline at end of file\n+\n+commit a6eb82647d5d67f893da442f8f9375fd89a3b1e2\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:45:16 2013 +0100\n+\n+ touch both functions\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -3,9 +3,9 @@\n+-int f(int x)\n++long f(long x)\n+ {\n+ \tint s = 0;\n+ \twhile (x) {\n+ \t\tx >>= 1;\n+ \t\ts++;\n+ \t}\n+ \treturn s;\n+ }\n+@@ -17,5 +17,5 @@\n+ int main ()\n+ {\n+-\tprintf(\"%d\\n\", f(15));\n++\tprintf(\"%ld\\n\", f(15));\n+ \treturn 0;\n+ }\n+\n+commit f04fb20f2c77850996cba739709acc6faecc58f7\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:44:55 2013 +0100\n+\n+ change f()\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -3,8 +3,9 @@\n+ int f(int x)\n+ {\n+ \tint s = 0;\n+ \twhile (x) {\n+ \t\tx >>= 1;\n+ \t\ts++;\n+ \t}\n++\treturn s;\n+ }\n+\n+commit de4c48ae814792c02a49c4c3c0c757ae69c55f6a\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:44:48 2013 +0100\n+\n+ initial\n+\n+diff --git a/a.c b/a.c\n+--- /dev/null\n++++ b/a.c\n+@@ -0,0 +3,8 @@\n++int f(int x)\n++{\n++\tint s = 0;\n++\twhile (x) {\n++\t\tx >>= 1;\n++\t\ts++;\n++\t}\n++}\ndiff --git a/t/t4211/expect.vanishes-early b/t/t4211/expect.vanishes-early\nnew file mode 100644\nindex 0000000..1f7cd06\n--- /dev/null\n+++ b/t/t4211/expect.vanishes-early\n@@ -0,0 +1,39 @@\n+commit 4659538844daa2849b1a9e7d6fadb96fcd26fc83\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:48:43 2013 +0100\n+\n+ change back to complete line\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -22,1 +24,1 @@\n+-}\n+\\ No newline at end of file\n++/* incomplete lines are bad! */\n+\n+commit 100b61a6f2f720f812620a9d10afb3a960ccb73c\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:48:10 2013 +0100\n+\n+ change to an incomplete line at end\n+\n+diff --git a/a.c b/a.c\n+--- a/a.c\n++++ b/a.c\n+@@ -22,1 +22,1 @@\n+-}\n++}\n+\\ No newline at end of file\n+\n+commit de4c48ae814792c02a49c4c3c0c757ae69c55f6a\n+Author: Thomas Rast \n+Date: Thu Feb 28 10:44:48 2013 +0100\n+\n+ initial\n+\n+diff --git a/a.c b/a.c\n+--- /dev/null\n++++ b/a.c\n+@@ -0,0 +20,1 @@\n++}\ndiff --git a/t/t4211/history.export b/t/t4211/history.export\nnew file mode 100644\nindex 0000000..c159794\n--- /dev/null\n+++ b/t/t4211/history.export\n@@ -0,0 +1,330 @@\n+blob\n+mark :1\n+data 157\n+#include \n+\n+int f(int x)\n+{\n+\tint s = 0;\n+\twhile (x) {\n+\t\tx >>= 1;\n+\t\ts++;\n+\t}\n+}\n+\n+/*\n+ * A comment.\n+ */\n+\n+int main ()\n+{\n+\tprintf(\"%d\\n\", f(15));\n+\treturn 0;\n+}\n+\n+reset refs/tags/simple\n+commit refs/tags/simple\n+mark :2\n+author Thomas Rast 1362044688 +0100\n+committer Thomas Rast 1362044688 +0100\n+data 8\n+initial\n+M 100644 :1 a.c\n+\n+blob\n+mark :3\n+data 168\n+#include \n+\n+int f(int x)\n+{\n+\tint s = 0;\n+\twhile (x) {\n+\t\tx >>= 1;\n+\t\ts++;\n+\t}\n+\treturn s;\n+}\n+\n+/*\n+ * A comment.\n+ */\n+\n+int main ()\n+{\n+\tprintf(\"%d\\n\", f(15));\n+\treturn 0;\n+}\n+\n+commit refs/tags/simple\n+mark :4\n+author Thomas Rast 1362044695 +0100\n+committer Thomas Rast 1362044695 +0100\n+data 11\n+change f()\n+from :2\n+M 100644 :3 a.c\n+\n+blob\n+mark :5\n+data 171\n+#include \n+\n+long f(long x)\n+{\n+\tint s = 0;\n+\twhile (x) {\n+\t\tx >>= 1;\n+\t\ts++;\n+\t}\n+\treturn s;\n+}\n+\n+/*\n+ * A comment.\n+ */\n+\n+int main ()\n+{\n+\tprintf(\"%ld\\n\", f(15));\n+\treturn 0;\n+}\n+\n+commit refs/tags/simple\n+mark :6\n+author Thomas Rast 1362044716 +0100\n+committer Thomas Rast 1362044716 +0100\n+data 21\n+touch both functions\n+from :4\n+M 100644 :5 a.c\n+\n+blob\n+mark :7\n+data 185\n+#include \n+\n+long f(long x)\n+{\n+\tint s = 0;\n+\twhile (x) {\n+\t\tx >>= 1;\n+\t\ts++;\n+\t}\n+\treturn s;\n+}\n+\n+/*\n+ * This is only an example!\n+ */\n+\n+int main ()\n+{\n+\tprintf(\"%ld\\n\", f(15));\n+\treturn 0;\n+}\n+\n+commit refs/tags/simple\n+mark :8\n+author Thomas Rast 1362044741 +0100\n+committer Thomas Rast 1362044741 +0100\n+data 14\n+touch comment\n+from :6\n+M 100644 :7 a.c\n+\n+blob\n+mark :9\n+data 205\n+#include \n+#include \n+\n+long f(long x)\n+{\n+\tint s = 0;\n+\twhile (x) {\n+\t\tx >>= 1;\n+\t\ts++;\n+\t}\n+\treturn s;\n+}\n+\n+/*\n+ * This is only an example!\n+ */\n+\n+int main ()\n+{\n+\tprintf(\"%ld\\n\", f(15));\n+\treturn 0;\n+}\n+\n+commit refs/tags/simple\n+mark :10\n+author Thomas Rast 1362044860 +0100\n+committer Thomas Rast 1362044860 +0100\n+data 25\n+change at very beginning\n+from :8\n+M 100644 :9 a.c\n+\n+blob\n+mark :11\n+data 204\n+#include \n+#include \n+\n+long f(long x)\n+{\n+\tint s = 0;\n+\twhile (x) {\n+\t\tx >>= 1;\n+\t\ts++;\n+\t}\n+\treturn s;\n+}\n+\n+/*\n+ * This is only an example!\n+ */\n+\n+int main ()\n+{\n+\tprintf(\"%ld\\n\", f(15));\n+\treturn 0;\n+}\n+commit refs/tags/simple\n+mark :12\n+author Thomas Rast 1362044890 +0100\n+committer Thomas Rast 1362044890 +0100\n+data 36\n+change to an incomplete line at end\n+from :10\n+M 100644 :11 a.c\n+\n+blob\n+mark :13\n+data 238\n+#include \n+#include \n+\n+long f(long x)\n+{\n+\tint s = 0;\n+\twhile (x) {\n+\t\tx >>= 1;\n+\t\ts++;\n+\t}\n+\treturn s;\n+}\n+\n+/*\n+ * This is only an example!\n+ */\n+\n+int main ()\n+{\n+\tprintf(\"%ld\\n\", f(15));\n+\treturn 0;\n+}\n+\n+/* incomplete lines are bad! */\n+\n+commit refs/tags/simple\n+mark :14\n+author Thomas Rast 1362044923 +0100\n+committer Thomas Rast 1362044923 +0100\n+data 29\n+change back to complete line\n+from :12\n+M 100644 :13 a.c\n+\n+commit refs/tags/move-support\n+mark :15\n+author Thomas Rast 1362044968 +0100\n+committer Thomas Rast 1362044968 +0100\n+data 10\n+move file\n+from :14\n+D a.c\n+M 100644 :13 b.c\n+\n+blob\n+mark :16\n+data 237\n+#include \n+#include \n+\n+long f(long x)\n+{\n+\tint s = 0;\n+\twhile (x) {\n+\t\tx /= 2;\n+\t\ts++;\n+\t}\n+\treturn s;\n+}\n+\n+/*\n+ * This is only an example!\n+ */\n+\n+int main ()\n+{\n+\tprintf(\"%ld\\n\", f(15));\n+\treturn 0;\n+}\n+\n+/* incomplete lines are bad! */\n+\n+commit refs/tags/move-support\n+mark :17\n+author Thomas Rast 1362044990 +0100\n+committer Thomas Rast 1362044990 +0100\n+data 22\n+another simple change\n+from :15\n+M 100644 :16 b.c\n+\n+blob\n+mark :18\n+data 254\n+#include \n+#include \n+\n+long f(long x);\n+\n+/*\n+ * This is only an example!\n+ */\n+\n+int main ()\n+{\n+\tprintf(\"%ld\\n\", f(15));\n+\treturn 0;\n+}\n+\n+/* incomplete lines are bad! */\n+\n+long f(long x)\n+{\n+\tint s = 0;\n+\twhile (x) {\n+\t\tx /= 2;\n+\t\ts++;\n+\t}\n+\treturn s;\n+}\n+\n+commit refs/heads/master\n+mark :19\n+author Thomas Rast 1362045024 +0100\n+committer Thomas Rast 1362045024 +0100\n+data 21\n+move within the file\n+from :17\n+M 100644 :18 b.c\n+\n+reset refs/heads/master\n+from :19\n+\n-- \n1.8.2.241.gee8bb87\n"},{"id":"211860","messageId":"153eaec7aff9618de3c30aa0b21556e1ed512e12.1363865444.git.trast@student.ethz.ch","threadId":"33247","inReplyTo":"cover.1363865444.git.trast@student.ethz.ch","subject":"[PATCH v9 4/5] log -L: :pattern:file syntax to find by funcname","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-21T12:52:39Z","receivedAt":"2013-03-21T12:52:39Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"This new syntax finds a funcname matching /pattern/, and then takes from there\nup to (but not including) the next funcname. So you can say\n\n git log -L:main:main.c\n\nand it will dig up the main() function and show its line-log, provided\nthere are no other funcnames matching 'main'.\n\nSigned-off-by: Thomas Rast \n---\n Documentation/blame-options.txt | 2 +-\n Documentation/git-blame.txt | 6 +-\n Documentation/git-log.txt | 11 +--\n Documentation/line-range-format.txt | 7 ++\n builtin/blame.c | 2 +-\n line-log.c | 5 +-\n line-range.c | 130 +++++++++++++++++++++++++++++++++++-\n line-range.h | 3 +-\n t/t4211-line-log.sh | 2 +\n 9 files changed, 154 insertions(+), 14 deletions(-)\n\ndiff --git a/Documentation/blame-options.txt b/Documentation/blame-options.txt\nindex 6998d9f..e9f984b 100644\n--- a/Documentation/blame-options.txt\n+++ b/Documentation/blame-options.txt\n@@ -9,7 +9,7 @@\n --show-stats::\n \tInclude additional statistics at the end of blame output.\n \n--L ,::\n+-L ,, -L :::\n \tAnnotate only the given line range. and can take\n \tone of these forms:\n \ndiff --git a/Documentation/git-blame.txt b/Documentation/git-blame.txt\nindex 9a05c2b..6cea7f1 100644\n--- a/Documentation/git-blame.txt\n+++ b/Documentation/git-blame.txt\n@@ -8,9 +8,9 @@ git-blame - Show what revision and author last modified each line of a file\n SYNOPSIS\n --------\n [verse]\n-'git blame' [-c] [-b] [-l] [--root] [-t] [-f] [-n] [-s] [-e] [-p] [-w] [--incremental] [-L n,m]\n-\t [-S ] [-M] [-C] [-C] [-C] [--since=] [--abbrev=]\n-\t [ | --contents | --reverse ] [--] \n+'git blame' [-c] [-b] [-l] [--root] [-t] [-f] [-n] [-s] [-e] [-p] [-w] [--incremental]\n+\t [-L n,m | -L :fn] [-S ] [-M] [-C] [-C] [-C] [--since=]\n+\t [--abbrev=] [ | --contents | --reverse ] [--] \n \n DESCRIPTION\n -----------\ndiff --git a/Documentation/git-log.txt b/Documentation/git-log.txt\nindex 8727c60..4850226 100644\n--- a/Documentation/git-log.txt\n+++ b/Documentation/git-log.txt\n@@ -69,12 +69,13 @@ produced by --stat etc.\n \tNote that only message is considered, if also a diff is shown\n \tits size is not included.\n \n--L ,:::\n+-L ,:, -L ::::\n+\n \tTrace the evolution of the line range given by \",\"\n-\twithin the . You may not give any pathspec limiters.\n-\tThis is currently limited to a walk starting from a single\n-\trevision, i.e., you may only give zero or one positive\n-\trevision arguments.\n+\t(or the funcname regex ) within the . You may\n+\tnot give any pathspec limiters. This is currently limited to\n+\ta walk starting from a single revision, i.e., you may only\n+\tgive zero or one positive revision arguments.\n \n and can take one of these forms:\n \ndiff --git a/Documentation/line-range-format.txt b/Documentation/line-range-format.txt\nindex 265bc23..3e7ce72 100644\n--- a/Documentation/line-range-format.txt\n+++ b/Documentation/line-range-format.txt\n@@ -16,3 +16,10 @@ starting at the line given by .\n This is only valid for and will specify a number\n of lines before or after the line given by .\n +\n+\n+- :regex\n++\n+If the option's argument is of the form :regex, it denotes the range\n+from the first funcname line that matches , up to the next\n+funcname line.\n++\ndiff --git a/builtin/blame.c b/builtin/blame.c\nindex 20eb439..1c09d55 100644\n--- a/builtin/blame.c\n+++ b/builtin/blame.c\n@@ -1940,7 +1940,7 @@ static void prepare_blame_range(struct scoreboard *sb,\n \t\t\t\tlong lno,\n \t\t\t\tlong *bottom, long *top)\n {\n-\tif (parse_range_arg(bottomtop, nth_line_cb, sb, lno, bottom, top))\n+\tif (parse_range_arg(bottomtop, nth_line_cb, sb, lno, bottom, top, sb->path))\n \t\tusage(blame_usage);\n }\n \ndiff --git a/line-log.c b/line-log.c\nindex 29162fc..81c8d74 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -12,6 +12,7 @@\n #include \"strbuf.h\"\n #include \"log-tree.h\"\n #include \"graph.h\"\n+#include \"userdiff.h\"\n #include \"line-log.h\"\n \n static void range_set_grow(struct range_set *rs, size_t extra)\n@@ -438,7 +439,6 @@ static void range_set_map_across_diff(struct range_set *out,\n \t*touched_out = touched;\n }\n \n-\n static struct commit *check_single_commit(struct rev_info *revs)\n {\n \tstruct object *commit = NULL;\n@@ -559,7 +559,8 @@ static const char *nth_line(void *data, long line)\n \t\tcb_data.line_ends = ends;\n \n \t\tif (parse_range_arg(range_part, nth_line, &cb_data,\n-\t\t\t\t lines, &begin, &end))\n+\t\t\t\t lines, &begin, &end,\n+\t\t\t\t spec->path))\n \t\t\tdie(\"malformed -L argument '%s'\", range_part);\n \t\tif (begin < 1)\n \t\t\tbegin = 1;\ndiff --git a/line-range.c b/line-range.c\nindex d0c7dac..ea141ab 100644\n--- a/line-range.c\n+++ b/line-range.c\n@@ -1,5 +1,8 @@\n #include \"git-compat-util.h\"\n #include \"line-range.h\"\n+#include \"xdiff-interface.h\"\n+#include \"strbuf.h\"\n+#include \"userdiff.h\"\n \n /*\n * Parse one item in the -L option\n@@ -84,9 +87,131 @@ static const char *parse_loc(const char *spec, nth_line_fn_t nth_line,\n \t}\n }\n \n+static int match_funcname(xdemitconf_t *xecfg, const char *bol, const char *eol)\n+{\n+\tif (xecfg) {\n+\t\tchar buf[1];\n+\t\treturn xecfg->find_func(bol, eol - bol, buf, 1,\n+\t\t\t\t\txecfg->find_func_priv) >= 0;\n+\t}\n+\n+\tif (bol == eol)\n+\t\treturn 0;\n+\tif (isalpha(*bol) || *bol == '_' || *bol == '$')\n+\t\treturn 1;\n+\treturn 0;\n+}\n+\n+static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char *start,\n+\t\t\t\t\t\t regex_t *regexp)\n+{\n+\tint reg_error;\n+\tregmatch_t match[1];\n+\twhile (1) {\n+\t\tconst char *bol, *eol;\n+\t\treg_error = regexec(regexp, start, 1, match, 0);\n+\t\tif (reg_error == REG_NOMATCH)\n+\t\t\treturn NULL;\n+\t\telse if (reg_error) {\n+\t\t\tchar errbuf[1024];\n+\t\t\tregerror(reg_error, regexp, errbuf, 1024);\n+\t\t\tdie(\"-L parameter: regexec() failed: %s\", errbuf);\n+\t\t}\n+\t\t/* determine extent of line matched */\n+\t\tbol = start+match[0].rm_so;\n+\t\teol = start+match[0].rm_eo;\n+\t\twhile (bol > start && *bol != '\\n')\n+\t\t\tbol--;\n+\t\tif (*bol == '\\n')\n+\t\t\tbol++;\n+\t\twhile (*eol && *eol != '\\n')\n+\t\t\teol++;\n+\t\tif (*eol == '\\n')\n+\t\t\teol++;\n+\t\t/* is it a funcname line? */\n+\t\tif (match_funcname(xecfg, (char*) bol, (char*) eol))\n+\t\t\treturn bol;\n+\t\tstart = eol;\n+\t}\n+}\n+\n+static const char *parse_range_funcname(const char *arg, nth_line_fn_t nth_line_cb,\n+\t\t\t\t\tvoid *cb_data, long lines, long *begin, long *end,\n+\t\t\t\t\tconst char *path)\n+{\n+\tconst char *pattern;\n+\tconst char *term;\n+\tstruct userdiff_driver *drv;\n+\txdemitconf_t *xecfg = NULL;\n+\tconst char *start;\n+\tconst char *p;\n+\tint reg_error;\n+\tregex_t regexp;\n+\n+\tpattern = arg+1;\n+\tterm = (char*) strchr(pattern, ':');\n+\tif (term) {\n+\t\tassert(!begin);\n+\t\treturn term;\n+\t}\n+\t/* all of the rest is the regex */\n+\tterm = pattern + strlen(pattern);\n+\n+\tstart = nth_line_cb(cb_data, 0);\n+\n+\tdrv = userdiff_find_by_path(path);\n+\tif (drv && drv->funcname.pattern) {\n+\t\tconst struct userdiff_funcname *pe = &drv->funcname;\n+\t\txecfg = xcalloc(1, sizeof(*xecfg));\n+\t\txdiff_set_find_func(xecfg, pe->pattern, pe->cflags);\n+\t}\n+\n+\treg_error = regcomp(®exp, pattern, REG_NEWLINE);\n+\tif (reg_error) {\n+\t\tchar errbuf[1024];\n+\t\tregerror(reg_error, ®exp, errbuf, 1024);\n+\t\tdie(\"-L parameter '%s': %s\", pattern, errbuf);\n+\t}\n+\n+\tp = find_funcname_matching_regexp(xecfg, (char*) start, ®exp);\n+\tif (!p)\n+\t\tdie(\"-L parameter '%s': no match\", pattern);\n+\t*begin = 0;\n+\twhile (p > nth_line_cb(cb_data, *begin))\n+\t\t(*begin)++;\n+\n+\tif (*begin >= lines)\n+\t\tdie(\"-L parameter '%s' matches at EOF\", pattern);\n+\n+\t*end = *begin+1;\n+\twhile (*end < lines) {\n+\t\tconst char *bol = nth_line_cb(cb_data, *end);\n+\t\tconst char *eol = nth_line_cb(cb_data, *end+1);\n+\t\tif (match_funcname(xecfg, bol, eol))\n+\t\t\tbreak;\n+\t\t(*end)++;\n+\t}\n+\n+\tregfree(®exp);\n+\tfree(xecfg);\n+\n+\t/* compensate for 1-based numbering */\n+\t(*begin)++;\n+\n+\treturn term;\n+}\n+\n int parse_range_arg(const char *arg, nth_line_fn_t nth_line_cb,\n-\t\t void *cb_data, long lines, long *begin, long *end)\n+\t\t void *cb_data, long lines, long *begin, long *end,\n+\t\t const char *path)\n {\n+\tif (*arg == ':') {\n+\t\targ = parse_range_funcname(arg, nth_line_cb, cb_data, lines, begin, end, path);\n+\t\tif (*arg)\n+\t\t\treturn -1;\n+\t\treturn 0;\n+\t}\n+\n \targ = parse_loc(arg, nth_line_cb, cb_data, lines, 1, begin);\n \n \tif (*arg == ',')\n@@ -100,6 +225,9 @@ int parse_range_arg(const char *arg, nth_line_fn_t nth_line_cb,\n \n const char *skip_range_arg(const char *arg)\n {\n+\tif (*arg == ':')\n+\t\treturn parse_range_funcname(arg, NULL, NULL, 0, NULL, NULL, NULL);\n+\n \targ = parse_loc(arg, NULL, NULL, 0, -1, NULL);\n \n \tif (*arg == ',')\ndiff --git a/line-range.h b/line-range.h\nindex 88aaf08..ae3d012 100644\n--- a/line-range.h\n+++ b/line-range.h\n@@ -19,7 +19,8 @@\n extern int parse_range_arg(const char *arg,\n \t\t\t nth_line_fn_t nth_line_cb,\n \t\t\t void *cb_data, long lines,\n-\t\t\t long *begin, long *end);\n+\t\t\t long *begin, long *end,\n+\t\t\t const char *path);\n \n /*\n * Scan past a range argument that could be parsed by\ndiff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\nindex 286390d..096679d 100755\n--- a/t/t4211-line-log.sh\n+++ b/t/t4211-line-log.sh\n@@ -18,8 +18,10 @@ canned_test () {\n canned_test \"-L 4,12:a.c simple\" simple-f\n canned_test \"-L 4,+9:a.c simple\" simple-f\n canned_test \"-L '/long f/,/^}/:a.c' simple\" simple-f\n+canned_test \"-L :f:a.c simple\" simple-f-to-main\n \n canned_test \"-L '/main/,/^}/:a.c' simple\" simple-main\n+canned_test \"-L :main:a.c simple\" simple-main-to-end\n \n canned_test \"-L 1,+4:a.c simple\" beginning-of-file\n \n-- \n1.8.2.241.gee8bb87\n"},{"id":"211863","messageId":"72a500432c0e6fde830f505204a1d02180710656.1363865444.git.trast@student.ethz.ch","threadId":"33247","inReplyTo":"cover.1363865444.git.trast@student.ethz.ch","subject":"[PATCH v9 5/5] Speed up log -L... -M","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-21T12:52:40Z","receivedAt":"2013-03-21T12:52:40Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"So far log -L only used the implicit diff filtering by pathspec. If\nthe user specifies -M, we cannot do that, and so we simply handed the\nwhole diff queue (which is approximately 'git show --raw') to\ndiffcore_std().\n\nUnfortunately this is very slow. We can optimize a lot if we throw\nout files that we know cannot possibly be interesting, in the same\nspirit that the pathspec filtering reduces the number of files.\n\nHowever, in this case, we have to be more careful. Because we want to\nlook out for renames, we need to keep all filepairs where something\nwas deleted.\n\nThis is a bit hacky and should really be replaced by equivalent\nsupport in --follow, and just using that. However, in the meantime it\nspeeds up 'log -M -L' by an order of magnitude.\n\nSigned-off-by: Thomas Rast \n---\n line-log.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++----\n 1 file changed, 52 insertions(+), 4 deletions(-)\n\ndiff --git a/line-log.c b/line-log.c\nindex 81c8d74..4327327 100644\n--- a/line-log.c\n+++ b/line-log.c\n@@ -750,7 +750,50 @@ static void move_diff_queue(struct diff_queue_struct *dst,\n \tDIFF_QUEUE_CLEAR(src);\n }\n \n-static void queue_diffs(struct diff_options *opt,\n+static void filter_diffs_for_paths(struct line_log_data *range, int keep_deletions)\n+{\n+\tint i;\n+\tstruct diff_queue_struct outq;\n+\tDIFF_QUEUE_CLEAR(&outq);\n+\n+\tfor (i = 0; i < diff_queued_diff.nr; i++) {\n+\t\tstruct diff_filepair *p = diff_queued_diff.queue[i];\n+\t\tstruct line_log_data *rg = NULL;\n+\n+\t\tif (!DIFF_FILE_VALID(p->two)) {\n+\t\t\tif (keep_deletions)\n+\t\t\t\tdiff_q(&outq, p);\n+\t\t\telse\n+\t\t\t\tdiff_free_filepair(p);\n+\t\t\tcontinue;\n+\t\t}\n+\t\tfor (rg = range; rg; rg = rg->next) {\n+\t\t\tif (!strcmp(rg->spec->path, p->two->path))\n+\t\t\t\tbreak;\n+\t\t}\n+\t\tif (rg)\n+\t\t\tdiff_q(&outq, p);\n+\t\telse\n+\t\t\tdiff_free_filepair(p);\n+\t}\n+\tfree(diff_queued_diff.queue);\n+\tdiff_queued_diff = outq;\n+}\n+\n+static inline int diff_might_be_rename(void)\n+{\n+\tint i;\n+\tfor (i = 0; i < diff_queued_diff.nr; i++)\n+\t\tif (!DIFF_FILE_VALID(diff_queued_diff.queue[i]->one)) {\n+\t\t\t/* fprintf(stderr, \"diff_might_be_rename found creation of: %s\\n\", */\n+\t\t\t/* \tdiff_queued_diff.queue[i]->two->path); */\n+\t\t\treturn 1;\n+\t\t}\n+\treturn 0;\n+}\n+\n+static void queue_diffs(struct line_log_data *range,\n+\t\t\tstruct diff_options *opt,\n \t\t\tstruct diff_queue_struct *queue,\n \t\t\tstruct commit *commit, struct commit *parent)\n {\n@@ -766,7 +809,12 @@ static void queue_diffs(struct diff_options *opt,\n \n \tDIFF_QUEUE_CLEAR(&diff_queued_diff);\n \tdiff_tree(&desc1, &desc2, \"\", opt);\n-\tdiffcore_std(opt);\n+\tif (opt->detect_rename) {\n+\t\tfilter_diffs_for_paths(range, 1);\n+\t\tif (diff_might_be_rename())\n+\t\t\tdiffcore_std(opt);\n+\t\tfilter_diffs_for_paths(range, 0);\n+\t}\n \tmove_diff_queue(queue, &diff_queued_diff);\n \n \tif (tree1)\n@@ -1050,7 +1098,7 @@ static int process_ranges_ordinary_commit(struct rev_info *rev, struct commit *c\n \tif (commit->parents)\n \t\tparent = commit->parents->item;\n \n-\tqueue_diffs(&rev->diffopt, &queue, commit, parent);\n+\tqueue_diffs(range, &rev->diffopt, &queue, commit, parent);\n \tchanged = process_all_files(&parent_range, rev, &queue, range);\n \tif (parent)\n \t\tadd_line_range(rev, parent, parent_range);\n@@ -1075,7 +1123,7 @@ static int process_ranges_merge_commit(struct rev_info *rev, struct commit *comm\n \tfor (i = 0; i < nparents; i++) {\n \t\tparents[i] = p->item;\n \t\tp = p->next;\n-\t\tqueue_diffs(&rev->diffopt, &diffqueues[i], commit, parents[i]);\n+\t\tqueue_diffs(range, &rev->diffopt, &diffqueues[i], commit, parents[i]);\n \t}\n \n \tfor (i = 0; i < nparents; i++) {\n-- \n1.8.2.241.gee8bb87\n"},{"id":"211886","messageId":"7vr4j8a7zy.fsf@alter.siamese.dyndns.org","threadId":"33247","inReplyTo":"b8cabd5ca63a17577fca524891046e5a3d3dfc60.1363865444.git.trast@student.ethz.ch","subject":"Re: [PATCH v9 3/5] Implement line-history search (git log -L)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-21T19:05:37Z","receivedAt":"2013-03-21T19:05:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> +void line_log_init(struct rev_info *rev, const char *prefix, struct string_list *args)\n> +{\n> +\tstruct commit *commit = NULL;\n> +\tstruct line_log_data *range;\n> +\n> +\tcommit = check_single_commit(rev);\n> +\trange = parse_lines(commit, prefix, args);\n> +\tadd_line_range(rev, commit, range);\n> +\n> +\tif (!rev->diffopt.detect_rename) {\n> +\t\tint i, count = 0;\n> +\t\tstruct line_log_data *r = range;\n> +\t\tconst char **paths;\n> +\t\twhile (r) {\n> +\t\t\tcount++;\n> +\t\t\tr = r->next;\n> +\t\t}\n> +\t\tpaths = xmalloc((count+1)*sizeof(char *));\n> +\t\tr = range;\n> +\t\tfor (i = 0; i < count; i++) {\n> +\t\t\tpaths[i] = xstrdup(r->spec->path);\n> +\t\t\tr = r->next;\n> +\t\t}\n> +\t\tpaths[count] = NULL;\n> +\t\tinit_pathspec(&rev->diffopt.pathspec, paths);\n> +\t\tfree(paths);\n> +\t}\n> +}\n\nWhy not do the pathspec limitation under \"-M\"?\n\nIt is not like you are picking up origins of blocks of lines copied\nor moved from other files like \"blame -C\" does, so I suspect it\nwould be simpler to mimic what --follow does, which is to (1) use\nthe pathspec to follow the paths you care about, and then (2) when\nyou find one or more of the paths you were following disappear in a\ncommit, only at that point you re-check to see if there are other\npaths that existed in the parent that the disappeared paths were\nrenamed from, and match with that one.\n"},{"id":"211901","messageId":"CAPig+cSG1gYohpZQZxnCpKgkUPs=Dwfokx+3OhiqdGKX8fajBw@mail.gmail.com","threadId":"33247","inReplyTo":"72a500432c0e6fde830f505204a1d02180710656.1363865444.git.trast@student.ethz.ch","subject":"Re: [PATCH v9 5/5] Speed up log -L... -M","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2013-03-21T21:11:28Z","receivedAt":"2013-03-21T21:11:28Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Thu, Mar 21, 2013 at 8:52 AM, Thomas Rast wrote:\n> This is a bit hacky and should really be replaced by equivalent\n> support in --follow, and just using that. However, in the meantime it\n\ns/using/use/\n\n> speeds up 'log -M -L' by an order of magnitude.\n"},{"id":"212024","messageId":"87k3oyzmg7.fsf@pctrast.inf.ethz.ch","threadId":"33247","inReplyTo":"CAPig+cSG1gYohpZQZxnCpKgkUPs=Dwfokx+3OhiqdGKX8fajBw@mail.gmail.com","subject":"Re: [PATCH v9 5/5] Speed up log -L... -M","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2013-03-23T05:58:48Z","receivedAt":"2013-03-23T05:58:48Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Eric Sunshine writes:\n\n> On Thu, Mar 21, 2013 at 8:52 AM, Thomas Rast wrote:\n>> This is a bit hacky and should really be replaced by equivalent\n>> support in --follow, and just using that. However, in the meantime it\n>\n> s/using/use/\n\nI'm not a native speaker, but I really think 'using' is more correct\nhere. But feel free to suggest a better wording. The intention is that\nwe should proceed in two steps: 'git log --follow' first needs to learn\nto adjust its pathspec filter as it walks revisions, much like I did\nhere. Then this patch should be reverted in favor of just enabling\n--follow.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"212025","messageId":"87fvzmzmcy.fsf@pctrast.inf.ethz.ch","threadId":"33247","inReplyTo":"7vr4j8a7zy.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v9 3/5] Implement line-history search (git log -L)","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2013-03-23T06:00:45Z","receivedAt":"2013-03-23T06:00:45Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano writes:\n\n> Thomas Rast writes:\n>\n>> +void line_log_init(struct rev_info *rev, const char *prefix, struct\n>> string_list *args)\n>> +{\n>> +\tstruct commit *commit = NULL;\n>> +\tstruct line_log_data *range;\n>> +\n>> +\tcommit = check_single_commit(rev);\n>> +\trange = parse_lines(commit, prefix, args);\n>> +\tadd_line_range(rev, commit, range);\n>> +\n>> +\tif (!rev->diffopt.detect_rename) {\n>> +\t\tint i, count = 0;\n>> +\t\tstruct line_log_data *r = range;\n>> +\t\tconst char **paths;\n>> +\t\twhile (r) {\n>> +\t\t\tcount++;\n>> +\t\t\tr = r->next;\n>> +\t\t}\n>> +\t\tpaths = xmalloc((count+1)*sizeof(char *));\n>> +\t\tr = range;\n>> +\t\tfor (i = 0; i < count; i++) {\n>> +\t\t\tpaths[i] = xstrdup(r->spec->path);\n>> +\t\t\tr = r->next;\n>> +\t\t}\n>> +\t\tpaths[count] = NULL;\n>> +\t\tinit_pathspec(&rev->diffopt.pathspec, paths);\n>> +\t\tfree(paths);\n>> +\t}\n>> +}\n>\n> Why not do the pathspec limitation under \"-M\"?\n>\n> It is not like you are picking up origins of blocks of lines copied\n> or moved from other files like \"blame -C\" does, so I suspect it\n> would be simpler to mimic what --follow does, which is to (1) use\n> the pathspec to follow the paths you care about, and then (2) when\n> you find one or more of the paths you were following disappear in a\n> commit, only at that point you re-check to see if there are other\n> paths that existed in the parent that the disappeared paths were\n> renamed from, and match with that one.\n\nIt's acting too soon though. The way log -L is currently wired, we do\none revision walk with the pathspec filter already enabled to do the\ntopo sorting. Wiring it in *at that point* would be equivalent to\nfixing --follow.\n\nWhich I plan to do Real Soon Now(tm). But let's not open too many cans\nof worms at the same time.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"212039","messageId":"20130323090459.GB25600@sigill.intra.peff.net","threadId":"33247","inReplyTo":"87k3oyzmg7.fsf@pctrast.inf.ethz.ch","subject":"Re: [PATCH v9 5/5] Speed up log -L... -M","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-23T09:04:59Z","receivedAt":"2013-03-23T09:04:59Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Mar 23, 2013 at 06:58:48AM +0100, Thomas Rast wrote:\n\n> Eric Sunshine writes:\n> \n> > On Thu, Mar 21, 2013 at 8:52 AM, Thomas Rast wrote:\n> >> This is a bit hacky and should really be replaced by equivalent\n> >> support in --follow, and just using that. However, in the meantime it\n> >\n> > s/using/use/\n> \n> I'm not a native speaker, but I really think 'using' is more correct\n> here.\n\nCannot...resist...grammar discussion.\n\nI think you are both potentially right.\n\nYou might consider the two items \"equivalent support\" and \"using that\"\nto be two noun phrases that are objects of the preposition \"by\", and\nthat the writer simply omits the second \"by\" after the \"and\". In which\ncase you are making a noun phrase from a verb phrase, and would want to\nuse the gerund form \"using\". And the sentence, simplifying out some\nmodifiers and adding the missing \"by\" (which is fine to omit, but the\nparts of speech become much clearer with it there), looks like:\n\n ...should be replaced by equivalent support, and by using that.\n\nHowever, you could also argue that the final clause is a second verb\nphrase for \"this should\" which just omits the extra \"should\" (which is\nalso OK in a list. In which case \"use\" acts as a verb, and parses as:\n\n ...should be replaced by equivalent support, and this should just use\n that.\n\nSo I think it is correct either way, and though it parses slightly\ndifferently, the overall meaning is the same.\n\nPhew. Totally not worth that much discussion, but for some reason I find\nthese sorts of ambiguous language cases interesting.\n\n-Peff\n"},{"id":"212081","messageId":"CAPig+cSnndjHWJ3U-DE3qG9Q3VvuDgyFnnfwZ8m3K335nwFCwQ@mail.gmail.com","threadId":"33247","inReplyTo":"20130323090459.GB25600@sigill.intra.peff.net","subject":"Re: [PATCH v9 5/5] Speed up log -L... -M","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2013-03-24T07:38:54Z","receivedAt":"2013-03-24T07:38:54Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Sat, Mar 23, 2013 at 5:04 AM, Jeff King wrote:\n> On Sat, Mar 23, 2013 at 06:58:48AM +0100, Thomas Rast wrote:\n>> Eric Sunshine writes:\n>> > On Thu, Mar 21, 2013 at 8:52 AM, Thomas Rast wrote:\n>> >> This is a bit hacky and should really be replaced by equivalent\n>> >> support in --follow, and just using that. However, in the meantime it\n>> >\n>> > s/using/use/\n>>\n>> I'm not a native speaker, but I really think 'using' is more correct\n>> here.\n>\n> Cannot...resist...grammar discussion.\n>\n> I think you are both potentially right.\n>\n> You might consider the two items \"equivalent support\" and \"using that\"\n> to be two noun phrases that are objects of the preposition \"by\", and\n> that the writer simply omits the second \"by\" after the \"and\". In which\n> case you are making a noun phrase from a verb phrase, and would want to\n> use the gerund form \"using\". And the sentence, simplifying out some\n> modifiers and adding the missing \"by\" (which is fine to omit, but the\n> parts of speech become much clearer with it there), looks like:\n>\n> ...should be replaced by equivalent support, and by using that.\n>\n> However, you could also argue that the final clause is a second verb\n> phrase for \"this should\" which just omits the extra \"should\" (which is\n> also OK in a list. In which case \"use\" acts as a verb, and parses as:\n>\n> ...should be replaced by equivalent support, and this should just use\n> that.\n>\n> So I think it is correct either way, and though it parses slightly\n> differently, the overall meaning is the same.\n>\n> Phew. Totally not worth that much discussion, but for some reason I find\n> these sorts of ambiguous language cases interesting.\n\nWishing to avoid bike-shedding the commit message, I suggested\ns/using/use/ as a minor change to help clarify the grammar a bit.\nHowever, perhaps it could be rephrased as:\n\n This is a bit hacky and should really be replaced by equivalent\n support in --follow, which can then be employed instead.\n\n-- ES\n"}]}