{"thread":{"id":"30735","subject":"[PATCH v7 0/5] git log -L, all new and shiny","startedAt":"2012-06-07T10:23:24Z","lastAt":"2012-06-19T10:33:18Z","messageCount":18,"participants":["Thomas Rast","Junio C Hamano","Zbigniew JÄ™drzejewski-Szmek"],"isPatch":true,"patchVersion":7,"patchTotal":5},"messages":[{"id":"193045","messageId":"cover.1339063659.git.trast@student.ethz.ch","threadId":"30735","inReplyTo":null,"subject":"[PATCH v7 0/5] git log -L, all new and shiny","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-06-07T10:23:24Z","receivedAt":"2012-06-07T10:23:24Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"I too thought it would never happen -- but then again this is still\nnot ready, I'm just trying to give it some exposure.\n\nMy mail archive says we were at v6 last time, but this is a rewrite\nrather than a reroll. In efforts to make the code understandable, I\ntried to compose it of little functions that do little operations on\nlittle data structures, to at least some success.\n\nIf you just want to dive in, patch it into your git or pull from\n\n git://github.com/trast/git.git line-log-WIP\n\nand then try something like\n\n git log -L '/^int main/,/^}/':git.c\n git log --graph -L '/^static void sha1_object/,/^}/':builtin/index-pack.c 681b07de11\n\nThe TODO list:\n\n* I dropped the tests for now, so we need new ones.\n\n* A good split of the main patch would be nice :-)\n\n* Much of the code leaks memory like a sieve because I was lazy. It's\n workable on the git repository, but eats a few hundred MB for simple\n tasks even there.\n\n* Missing features:\n - detect/filter merges at the hunk level\n (and ideally show a combined diff for the nontrivial ones)\n - -M and -C support\n - ...?\n\nThere's also a longer-term wishlist hinted at in the commit message of\nthe main patch: the diff machinery currently makes no provisions for\nchaining its various bells and whistles. As the most obvious example,\nit is not possible to run a word diff over the result of 'log -L'.\nChanges in this direction would probably also make the implementation\nof 'log -L' fit nicely in there somewhere.\n\n\nBo Yang (3):\n Refactor parse_loc\n Export three functions from diff.c\n Export rewrite_parents() for 'log -L'\n\nThomas Rast (2):\n blame: introduce $ as \"end of file\" in -L syntax\n Implement line-history search (git log -L)\n\n Documentation/blame-options.txt | 19 +-\n Documentation/git-log.txt | 22 +\n Documentation/line-range-format.txt | 24 +\n Makefile | 2 +\n builtin/blame.c | 99 +--\n builtin/log.c | 53 ++\n diff.c | 6 +-\n diff.h | 17 +\n line.c | 1245 +++++++++++++++++++++++++++++++++++\n line.h | 79 +++\n log-tree.c | 3 +\n revision.c | 22 +-\n revision.h | 16 +-\n t/t8003-blame-corner-cases.sh | 6 +\n 14 files changed, 1491 insertions(+), 122 deletions(-)\n create mode 100644 Documentation/line-range-format.txt\n create mode 100644 line.c\n create mode 100644 line.h\n\n-- \n1.7.11.rc1.243.gbf4713c\n"},{"id":"193047","messageId":"a66100b0eb721b771f66b93ca84cbd9ba33b945f.1339063659.git.trast@student.ethz.ch","threadId":"30735","inReplyTo":"cover.1339063659.git.trast@student.ethz.ch","subject":"[PATCH v7 1/5] Refactor parse_loc","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-06-07T10:23:25Z","receivedAt":"2012-06-07T10:23:25Z","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.c | 100 ++++++++++++++++++++++++++++++++++++\n line.h | 23 +++++++++\n t/t8003-blame-corner-cases.sh | 6 +++\n 7 files changed, 158 insertions(+), 109 deletions(-)\n create mode 100644 Documentation/line-range-format.txt\n create mode 100644 line.c\n create mode 100644 line.h\n\ndiff --git a/Documentation/blame-options.txt b/Documentation/blame-options.txt\nindex d4a51da..1d9305e 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 4592f1f..9166b86 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -626,6 +626,7 @@ LIB_H += hash.h\n LIB_H += help.h\n LIB_H += kwset.h\n LIB_H += levenshtein.h\n+LIB_H += line.h\n LIB_H += list-objects.h\n LIB_H += ll-merge.h\n LIB_H += log-tree.h\n@@ -731,6 +732,7 @@ LIB_OBJS += hex.o\n LIB_OBJS += ident.o\n LIB_OBJS += kwset.o\n LIB_OBJS += levenshtein.o\n+LIB_OBJS += line.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 24d3dd5..c3b379b 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.h\"\n \n static char blame_usage[] = \"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@@ -1934,83 +1940,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@@ -2018,15 +1947,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@@ -2516,10 +2437,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.c b/line.c\nnew file mode 100644\nindex 0000000..afd2e3b\n--- /dev/null\n+++ b/line.c\n@@ -0,0 +1,100 @@\n+#include \"git-compat-util.h\"\n+#include \"line.h\"\n+\n+/*\n+ * Parse one item in the -L option\n+ */\n+const char *parse_loc(const char *spec, nth_line_fn_t nth_line,\n+\t\tvoid *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/*\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 (begin != -1 && (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+\tif (begin == -1)\n+\t\tbegin = 1;\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} else {\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\tvoid *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+\t\tif (*begin > *end) {\n+\t\t\tlong tmp = *begin;\n+\t\t\t*begin = *end;\n+\t\t\t*end = tmp;\n+\t\t}\n+\t}\n+\n+\tif (*arg)\n+\t\treturn -1;\n+\n+\treturn 0;\n+}\ndiff --git a/line.h b/line.h\nnew file mode 100644\nindex 0000000..5878c94\n--- /dev/null\n+++ b/line.h\n@@ -0,0 +1,23 @@\n+#ifndef LINE_H\n+#define LINE_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+ * caller should print a usage message in the latter case.\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_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.7.11.rc1.243.gbf4713c\n"},{"id":"193050","messageId":"d9e1235303c949849b9acfa37fc9e9a780d93873.1339063659.git.trast@student.ethz.ch","threadId":"30735","inReplyTo":"cover.1339063659.git.trast@student.ethz.ch","subject":"[PATCH v7 2/5] blame: introduce $ as \"end of file\" in -L syntax","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-06-07T10:23:26Z","receivedAt":"2012-06-07T10:23:26Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"To save the user a lookup of the last line number, introduce $ as a\nshorthand for the last line. This is mostly useful to spell \"until\nthe end of the file\" as '-L,$'.\n\nSigned-off-by: Thomas Rast \n---\n Documentation/line-range-format.txt | 6 ++++++\n line.c | 8 ++++++++\n 2 files changed, 14 insertions(+)\n\ndiff --git a/Documentation/line-range-format.txt b/Documentation/line-range-format.txt\nindex 265bc23..9ce0688 100644\n--- a/Documentation/line-range-format.txt\n+++ b/Documentation/line-range-format.txt\n@@ -16,3 +16,9 @@ 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+- `$`\n++\n+A literal dollar sign can be used as a shorthand for the last line in\n+the file.\n++\ndiff --git a/line.c b/line.c\nindex afd2e3b..a7f33ed 100644\n--- a/line.c\n+++ b/line.c\n@@ -15,6 +15,14 @@ const char *parse_loc(const char *spec, nth_line_fn_t nth_line,\n \tregmatch_t match[1];\n \n \t/*\n+\t * $ is a synonym for \"the end of the file\".\n+\t */\n+\tif (spec[0] == '$') {\n+\t\t*ret = lines;\n+\t\treturn spec + 1;\n+\t}\n+\n+\t/*\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-- \n1.7.11.rc1.243.gbf4713c\n"},{"id":"193048","messageId":"3d2d6819e02104dc954bd56be996e664dba90c54.1339063659.git.trast@student.ethz.ch","threadId":"30735","inReplyTo":"cover.1339063659.git.trast@student.ethz.ch","subject":"[PATCH v7 3/5] Export three functions from diff.c","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-06-07T10:23:27Z","receivedAt":"2012-06-07T10:23:27Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"From: Bo Yang \n\nUse fill_metainfo to fill the line level diff meta data,\nemit_line to print out a line and quote_two to quote\npaths.\n\nSigned-off-by: Bo Yang \nSigned-off-by: Thomas Rast \n---\n diff.c | 6 +++---\n diff.h | 17 +++++++++++++++++\n 2 files changed, 20 insertions(+), 3 deletions(-)\n\ndiff --git a/diff.c b/diff.c\nindex 77edd50..f9673f3 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -220,7 +220,7 @@ int git_diff_basic_config(const char *var, const char *value, void *cb)\n \treturn git_default_config(var, value, cb);\n }\n \n-static char *quote_two(const char *one, const char *two)\n+char *quote_two(const char *one, const char *two)\n {\n \tint need_one = quote_c_style(one, NULL, NULL, 1);\n \tint need_two = quote_c_style(two, NULL, NULL, 1);\n@@ -410,7 +410,7 @@ static void emit_line_0(struct diff_options *o, const char *set, const char *res\n \t\tfputc('\\n', file);\n }\n \n-static void emit_line(struct diff_options *o, const char *set, const char *reset,\n+void emit_line(struct diff_options *o, const char *set, const char *reset,\n \t\t const char *line, int len)\n {\n \temit_line_0(o, set, reset, line[0], line+1, len-1);\n@@ -2925,7 +2925,7 @@ static int similarity_index(struct diff_filepair *p)\n \treturn p->score * 100 / MAX_SCORE;\n }\n \n-static void fill_metainfo(struct strbuf *msg,\n+void fill_metainfo(struct strbuf *msg,\n \t\t\t const char *name,\n \t\t\t const char *other,\n \t\t\t struct diff_filespec *one,\ndiff --git a/diff.h b/diff.h\nindex e027650..4a7d085 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -14,6 +14,7 @@\n struct userdiff_driver;\n struct sha1_array;\n struct commit;\n+struct diff_filepair;\n \n typedef void (*change_fn_t)(struct diff_options *options,\n \t\t unsigned old_mode, unsigned new_mode,\n@@ -329,6 +330,22 @@ extern size_t fill_textconv(struct userdiff_driver *driver,\n \n extern int parse_rename_score(const char **cp_p);\n \n+/* some output functions line.c need */\n+extern void fill_metainfo(struct strbuf *msg,\n+\t\t\t const char *name,\n+\t\t\t const char *other,\n+\t\t\t struct diff_filespec *one,\n+\t\t\t struct diff_filespec *two,\n+\t\t\t struct diff_options *o,\n+\t\t\t struct diff_filepair *p,\n+\t\t\t int *must_show_header,\n+\t\t\t int use_color);\n+\n+extern void emit_line(struct diff_options *o, const char *set, const char *reset,\n+\t\t const char *line, int len);\n+\n+extern char *quote_two(const char *one, const char *two);\n+\n extern int print_stat_summary(FILE *fp, int files,\n \t\t\t int insertions, int deletions);\n \n-- \n1.7.11.rc1.243.gbf4713c\n"},{"id":"193046","messageId":"de90975ae231f0a982e6ba4cdd576e085bb08029.1339063659.git.trast@student.ethz.ch","threadId":"30735","inReplyTo":"cover.1339063659.git.trast@student.ethz.ch","subject":"[PATCH v7 4/5] Export rewrite_parents() for 'log -L'","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-06-07T10:23:28Z","receivedAt":"2012-06-07T10:23:28Z","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.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 935e7a7..183ca58 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2109,12 +2109,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@@ -2136,12 +2130,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@@ -2213,7 +2208,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 863f4f6..6d09550 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -231,4 +231,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.7.11.rc1.243.gbf4713c\n"},{"id":"193049","messageId":"61a797a048c43d64352ef86a1b224f017e7161ae.1339063659.git.trast@student.ethz.ch","threadId":"30735","inReplyTo":"cover.1339063659.git.trast@student.ethz.ch","subject":"[PATCH v7 5/5] Implement line-history search (git log -L)","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-06-07T10:23:29Z","receivedAt":"2012-06-07T10:23:29Z","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\nSigned-off-by: Bo Yang \nSigned-off-by: Thomas Rast \n---\n Documentation/git-log.txt | 22 +\n builtin/log.c | 53 +++\n line.c | 1139 ++++++++++++++++++++++++++++++++++++++++++++-\n line.h | 56 +++\n log-tree.c | 3 +\n revision.c | 9 +\n revision.h | 6 +-\n 7 files changed, 1286 insertions(+), 2 deletions(-)\n\ndiff --git a/Documentation/git-log.txt b/Documentation/git-log.txt\nindex 1f90620..9104a6d 100644\n--- a/Documentation/git-log.txt\n+++ b/Documentation/git-log.txt\n@@ -68,6 +68,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@@ -137,6 +154,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 \n Discussion\n ----------\ndiff --git a/builtin/log.c b/builtin/log.c\nindex 906dca4..4a0d5da 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.h\"\n #include \"branch.h\"\n #include \"streaming.h\"\n \n@@ -38,6 +39,12 @@\n \tNULL\n };\n \n+struct line_opt_callback_data {\n+\tstruct rev_info *rev;\n+\tconst char *prefix;\n+\tstruct line_log_data *ranges, *cur_range;\n+};\n+\n static int parse_decoration_style(const char *var, const char *value)\n {\n \tswitch (git_config_maybe_bool(var, value)) {\n@@ -72,6 +79,40 @@ 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+\tstruct line_log_data *r;\n+\tconst char *name_start, *range_arg, *full_path;\n+\tconst char *prefix = data->prefix;\n+\n+\tif (!arg)\n+\t\treturn -1;\n+\n+\tname_start = skip_range_arg(arg);\n+\tif (!name_start || *name_start != ':')\n+\t\tdie(\"-L argument '%s' not of the form start,end:file\", arg);\n+\n+\trange_arg = xstrndup(arg, name_start-arg);\n+\tname_start++;\n+\n+\tfull_path = prefix_path(prefix, prefix ? strlen(prefix) : 0,\n+\t\t\t\tname_start);\n+\n+\tr = xmalloc(sizeof(struct line_log_data));\n+\tline_log_data_init(r);\n+\tif (data->cur_range)\n+\t\tdata->cur_range->next = r;\n+\telse\n+\t\tdata->ranges = r;\n+\tdata->cur_range = r;\n+\tr->spec = alloc_filespec(full_path);\n+\tALLOC_GROW(r->args, r->arg_nr+1, r->arg_alloc);\n+\tr->args[r->arg_nr++] = range_arg;\n+\tdata->rev->line_level_traverse = 1;\n+\treturn 0;\n+}\n+\n static void cmd_log_init_defaults(struct rev_info *rev)\n {\n \tif (fmt_pretty)\n@@ -94,15 +135,23 @@ 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;\n+\tstatic struct line_opt_callback_data line_cb = {0};\n+\tstatic int full_line_diff;\n \n \tconst struct option builtin_log_options[] = {\n \t\tOPT_BOOLEAN(0, \"quiet\", &quiet, \"suppress diff output\"),\n \t\tOPT_BOOLEAN(0, \"source\", &source, \"show source\"),\n \t\t{ OPTION_CALLBACK, 0, \"decorate\", NULL, NULL, \"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 \targc = parse_options(argc, argv, prefix,\n \t\t\t builtin_log_options, builtin_log_usage,\n \t\t\t PARSE_OPT_KEEP_ARGV0 | PARSE_OPT_KEEP_UNKNOWN |\n@@ -150,6 +199,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.ranges);\n+\n \tsetup_pager();\n }\n \ndiff --git a/line.c b/line.c\nindex a7f33ed..d837bb3 100644\n--- a/line.c\n+++ b/line.c\n@@ -1,6 +1,459 @@\n #include \"git-compat-util.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.h\"\n \n+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+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+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+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+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+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+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 (!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+}\n+\n+static void free_line_log_datas(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_1(struct line_log_data *list, const char *path,\n+\t\t\t struct line_log_data **insertion_point)\n+{\n+\tstruct line_log_data *p = list;\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 struct line_log_data *\n+search_line_log_data(struct line_log_data *list, const char *path)\n+{\n+\treturn search_line_log_data_1(list, path, NULL);\n+}\n+\n+static void line_log_data_extend (struct line_log_data **list,\n+\t\t\t\t const char *path, struct range_set *rs)\n+{\n+\tstruct line_log_data *ip;\n+\tstruct line_log_data *p = search_line_log_data_1(*list, path, &ip);\n+\n+\tif (p) {\n+\t\tint i;\n+\t\tfor (i = 0; i < rs->nr; i++)\n+\t\t\trange_set_append(&p->ranges, rs->ranges[i].start,\n+\t\t\t\t\t rs->ranges[i].end);\n+\t\treturn;\n+\t}\n+\n+\tp = xcalloc(1, sizeof(struct line_log_data));\n+\trange_set_copy(&p->ranges, rs);\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+static void line_log_data_insert (struct line_log_data **list,\n+\t\t\t\t const char *path, struct range rg)\n+{\n+\t/* we fake a 1-element range_set without any allocations */\n+\tstruct range_set rs = { 1, 1, &rg };\n+\tline_log_data_extend(list, path, &rs);\n+}\n+\n+static void line_log_data_sort (struct line_log_data *list)\n+{\n+\tstruct line_log_data *p = list;\n+\twhile (p) {\n+\t\tsort_and_merge_range_set(&p->ranges);\n+\t\tp = p->next;\n+\t}\n+}\n+\n+/* In the diff handling, p=parent and t=target. */\n+\n+struct collect_diff_cbdata {\n+\tlong plno, tlno;\n+\tstruct diff_ranges *diff;\n+};\n+\n+/*\n+ * This callback being called means:\n+ * - lines [tlno,same] are from parent\n+ * - line tlno in target corresponds to plno in parent\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+\td->plno = start_a + count_a;\n+\td->tlno = 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 = {0};\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+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_datas (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+\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\tstruct diff_ranges *diff,\n+\t\t\t\t\tstruct 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 * Parse one item in the -L option\n */\n@@ -30,6 +483,8 @@ const char *parse_loc(const char *spec, nth_line_fn_t nth_line,\n \tif (begin != -1 && (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@@ -44,7 +499,8 @@ 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@@ -58,6 +514,10 @@ 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 \tif (begin == -1)\n@@ -106,3 +566,680 @@ 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, 0);\n+\n+\tif (*arg == ',')\n+\t\targ = parse_loc(arg+1, NULL, NULL, 0, 0, 0);\n+\n+\treturn arg;\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\trevs->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 line_log_data *r)\n+{\n+\tunsigned mode;\n+\tunsigned char sha1[20];\n+\n+\twhile (r) {\n+\t\tif (get_tree_entry(commit->object.sha1, r->spec->path,\n+\t\t\tsha1, &mode))\n+\t\t\tdie(\"There is no path %s in the commit\", r->spec->path);\n+\t\tfill_filespec(r->spec, sha1, mode);\n+\t\tr = r->next;\n+\t}\n+\n+\treturn;\n+}\n+\n+static void fill_line_ends(struct diff_filespec *spec, long *lines,\n+\tunsigned 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;\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 void parse_lines(struct commit *commit, struct line_log_data *r)\n+{\n+\tint i;\n+\tlong lines = 0;\n+\tunsigned long *ends = NULL;\n+\tstruct nth_line_cb cb_data;\n+\n+\twhile (r) {\n+\t\tstruct diff_filespec *spec = r->spec;\n+\t\tint num = r->arg_nr;\n+\t\tassert(spec);\n+\t\tfill_blob_sha1(commit, r);\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+\t\tfor (i = 0; i < num; i++) {\n+\t\t\tlong begin, end;\n+\t\t\tstruct range rg;\n+\t\t\tif (parse_range_arg(r->args[i], nth_line, &cb_data,\n+\t\t\t\t\t lines-1, &begin, &end))\n+\t\t\t\tdie(\"malformed -L argument '%s'\", r->args[i]);\n+\t\t\trg.start = begin-1;\n+\t\t\trg.end = end;\n+\t\t\tline_log_data_insert(&r, r->spec->path, rg);\n+\t\t}\n+\n+\t\tfree(ends);\n+\t\tends = NULL;\n+\n+\t\tr = r->next;\n+\t}\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\tstruct line_log_data *b)\n+{\n+\tstruct line_log_data *o, *prev = NULL, *head;\n+\n+\tif (!a && !b)\n+\t\treturn NULL;\n+\n+\twhile (a || b) {\n+\t\tstruct line_log_data *src;\n+\t\tstruct line_log_data *src2 = NULL;\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\to = xmalloc(sizeof(struct line_log_data));\n+\t\tline_log_data_init(o);\n+\t\to->spec = src->spec;\n+\t\to->spec->count++;\n+\t\tif (prev)\n+\t\t\tprev->next = o;\n+\t\telse\n+\t\t\thead = o;\n+\t\tprev = o;\n+\t\tif (src2)\n+\t\t\trange_set_union(&o->ranges, &src->ranges, &src2->ranges);\n+\t\telse\n+\t\t\trange_set_copy(&o->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\tstruct 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_datas(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_datas(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\tstruct 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, struct line_log_data *r)\n+{\n+\tstruct commit *commit = NULL;\n+\n+\tcommit = check_single_commit(rev);\n+\tparse_lines(commit, r);\n+\n+\tadd_line_range(rev, commit, r);\n+}\n+\n+static void load_tree_desc(struct tree_desc *desc, void **tree,\n+\t\tconst 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+\t/*\n+\t * Compose up two trees, for root commit, we make up a empty tree.\n+\t */\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+\t} else {\n+\t\tinit_tree_desc(&desc1, \"\", 0);\n+\t}\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+\tif (end > begin && end[-1] == '\\n')\n+\t\tend--;\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+}\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\tp_start = diff->parent.ranges[j].start - (diff->target.ranges[j].start-t_start);\n+\t\tp_end = diff->parent.ranges[j_last].end + (t_end-diff->target.ranges[j_last].end);\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++)\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+\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+\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+\treturn ((*diff_out)->parent.nr > 0);\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 = 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+ struct line_log_data *range = lookup_line_range(rev, commit);\n+\n+ show_log(rev);\n+ dump_diff_hacky(rev, range);\n+ return 1;\n+}\n+\n+static int process_ranges_ordinary_commit(struct rev_info *rev, struct commit *commit)\n+{\n+\tstruct commit *parent = NULL;\n+\tstruct diff_queue_struct queue;\n+\tstruct line_log_data *range = lookup_line_range(rev, commit);\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+{\n+\tstruct line_log_data *range = lookup_line_range(rev, commit);\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\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+\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+\tint changed = 0;\n+\n+\tif (lookup_line_range(rev, commit)) {\n+\t\tif (!commit->parents || !commit->parents->next)\n+\t\t\tchanged = process_ranges_ordinary_commit(rev, commit);\n+\t\telse\n+\t\t\tchanged = process_ranges_merge_commit(rev, commit);\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, *cur = NULL;\n+\n+\tlist = rev->commits;\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\tif (cur)\n+\t\t\t\tcur->next = list;\n+\t\t\telse\n+\t\t\t\tout = list;\n+\t\t\tcur = list;\n+\t\t} else\n+\t\t\tto_free = list;\n+\t\tlist = list->next;\n+\t\tfree(to_free);\n+\t}\n+\tcur->next = NULL;\n+\n+\tlist = out;\n+\twhile (list) {\n+\t\trewrite_parents(rev, list->item, line_log_rewrite_one);\n+\t\tlist = list->next;\n+\t}\n+\n+\trev->commits = out;\n+\n+\treturn 0;\n+}\ndiff --git a/line.h b/line.h\nindex 5878c94..9cbff56 100644\n--- a/line.h\n+++ b/line.h\n@@ -1,6 +1,8 @@\n #ifndef LINE_H\n #define LINE_H\n \n+#include \"diffcore.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@@ -20,4 +22,58 @@ 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+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+\tchar **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, struct line_log_data *r);\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_H */\ndiff --git a/log-tree.c b/log-tree.c\nindex c894930..3fb025d 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -809,6 +809,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 183ca58..a92e359 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.h\"\n \n volatile show_early_output_fn_t show_early_output;\n \n@@ -1851,6 +1852,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 \tif (diff_setup_done(&revs->diffopt) < 0)\n \t\tdie(\"diff_setup_done failed\");\n \n@@ -2102,6 +2109,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 6d09550..01902cf 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -92,7 +92,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@@ -168,6 +169,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\n-- \n1.7.11.rc1.243.gbf4713c\n"},{"id":"193083","messageId":"7vwr3jhw8z.fsf@alter.siamese.dyndns.org","threadId":"30735","inReplyTo":"d9e1235303c949849b9acfa37fc9e9a780d93873.1339063659.git.trast@student.ethz.ch","subject":"Re: [PATCH v7 2/5] blame: introduce $ as \"end of file\" in -L syntax","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-06-07T17:23:08Z","receivedAt":"2012-06-07T17:23:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> To save the user a lookup of the last line number, introduce $ as a\n> shorthand for the last line. This is mostly useful to spell \"until\n> the end of the file\" as '-L,$'.\n\nHmph. This is mostly useful not to error out when user (perhaps\nmistakenly) expects that the end of file is spelled as \"$\"; both\n\"git blame -L\" and \"git blame L,\" have always meant\n\"til the end\", IIRC.\n\nBecause I do not offhand think of other & better uses of \"$\" as a\nspecial case that conflicts with \"the end of file\", I do not think\nit is a bad patch that needs to be rejected, though.\n"},{"id":"193084","messageId":"7vhaunhvc8.fsf@alter.siamese.dyndns.org","threadId":"30735","inReplyTo":"61a797a048c43d64352ef86a1b224f017e7161ae.1339063659.git.trast@student.ethz.ch","subject":"Re: [PATCH v7 5/5] Implement line-history search (git log -L)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-06-07T17:42:47Z","receivedAt":"2012-06-07T17:42:47Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> This is a rewrite of much of Bo's work, mainly in an effort to split\n> it into smaller, easier to understand routines.\n\nYou mentioned \"splitting\" in the cover letter, but it does seem to\nneed a bit more work.\n\n> diff --git a/builtin/log.c b/builtin/log.c\n> index 906dca4..4a0d5da 100644\n> --- a/builtin/log.c\n> +++ b/builtin/log.c\n> @@ -38,6 +39,12 @@\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> +\tstruct line_log_data *r;\n> +\tconst char *name_start, *range_arg, *full_path;\n> ...\n> +\tALLOC_GROW(r->args, r->arg_nr+1, r->arg_alloc);\n> +\tr->args[r->arg_nr++] = range_arg;\n\nAssignment discards qualifiers from pointer target type; this\npointer does not have to be \"const char *\" perhaps?\n\n> @@ -94,15 +135,23 @@ 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;\n> +\tstatic struct line_opt_callback_data line_cb = {0};\n> +\tstatic int full_line_diff;\n\nVariable unused.\n\n> diff --git a/line.c b/line.c\n> index a7f33ed..d837bb3 100644\n> --- a/line.c\n> +++ b/line.c\n> @@ -1,6 +1,459 @@\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\nUnused.\n\n> +static struct line_log_data *\n> +search_line_log_data(struct line_log_data *list, const char *path)\n> +{\n> +\treturn search_line_log_data_1(list, path, NULL);\n> +}\n\nUnused.\n\n> +static void line_log_data_sort (struct line_log_data *list)\n> +{\n> +\tstruct line_log_data *p = list;\n> +\twhile (p) {\n> +\t\tsort_and_merge_range_set(&p->ranges);\n> +\t\tp = p->next;\n> +\t}\n> +}\n\nUnused.\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\tstruct diff_ranges *diff,\n> +\t\t\t\t\tstruct 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\nShouldn't the ranges be merged, not just appended?\n\n> diff --git a/log-tree.c b/log-tree.c\n> index c894930..3fb025d 100644\n> --- a/log-tree.c\n> +++ b/log-tree.c\n> @@ -809,6 +809,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\n#include \"line.h\" is missing from the beginning of this file.\n\n> diff --git a/revision.h b/revision.h\n> index 6d09550..01902cf 100644\n> --- a/revision.h\n> +++ b/revision.h\n> @@ -92,7 +92,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> @@ -168,6 +169,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\nGood use of decoration.\n\n> };\n> \n> #define REV_TREE_SAME\t\t0\n"},{"id":"193085","messageId":"7vaa0fhva5.fsf@alter.siamese.dyndns.org","threadId":"30735","inReplyTo":"3d2d6819e02104dc954bd56be996e664dba90c54.1339063659.git.trast@student.ethz.ch","subject":"Re: [PATCH v7 3/5] Export three functions from diff.c","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-06-07T17:44:02Z","receivedAt":"2012-06-07T17:44:02Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> From: Bo Yang \n>\n> Use fill_metainfo to fill the line level diff meta data,\n> emit_line to print out a line and quote_two to quote\n> paths.\n>\n> Signed-off-by: Bo Yang \n> Signed-off-by: Thomas Rast \n> ---\n\nWhy? Neither 4/5 or 5/5 seem to use any of these.\n"},{"id":"193086","messageId":"87wr3j6mpn.fsf@thomas.inf.ethz.ch","threadId":"30735","inReplyTo":"7vwr3jhw8z.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v7 2/5] blame: introduce $ as \"end of file\" in -L syntax","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2012-06-07T17:44:36Z","receivedAt":"2012-06-07T17:44:36Z","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>> To save the user a lookup of the last line number, introduce $ as a\n>> shorthand for the last line. This is mostly useful to spell \"until\n>> the end of the file\" as '-L,$'.\n>\n> Hmph. This is mostly useful not to error out when user (perhaps\n> mistakenly) expects that the end of file is spelled as \"$\"; both\n> \"git blame -L\" and \"git blame L,\" have always meant\n> \"til the end\", IIRC.\n\nHeh. That's actually a very good point; I think neither Bo nor me have\nthought about allowing git log -L :.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"193087","messageId":"87sje757sl.fsf@thomas.inf.ethz.ch","threadId":"30735","inReplyTo":"7vhaunhvc8.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v7 5/5] Implement line-history search (git log -L)","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2012-06-07T17:52:10Z","receivedAt":"2012-06-07T17:52:10Z","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>> This is a rewrite of much of Bo's work, mainly in an effort to split\n>> it into smaller, easier to understand routines.\n>\n> You mentioned \"splitting\" in the cover letter, but it does seem to\n> need a bit more work.\n\nYes, I think I also mentioned that it's not ready for inclusion ;-)\n\nMost of your points are spot on, however:\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> Unused.\n\nThat should end up being used a few times...\n\n>> +static void diff_ranges_filter_touched (struct diff_ranges *out,\n>> +\t\t\t\t\tstruct diff_ranges *diff,\n>> +\t\t\t\t\tstruct range_set *rs)\n...\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>\n> Shouldn't the ranges be merged, not just appended?\n\nIf the code ever passed anything but an empty struct diff_ranges as the\n'out' argument, yes. But it doesn't. In general I'm usually doing the\n'out' dance to save one heap allocation. Perhaps it would be cleaner to\nallocate all of them on the heap instead, and return as pointers, dunno.\n\n>> +\t/* line level range that we are chasing */\n>> +\tstruct decoration line_log_data;\n>\n> Good use of decoration.\n\nThat was actually Bo's idea.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"193238","messageId":"4FD46B06.4050609@in.waw.pl","threadId":"30735","inReplyTo":"61a797a048c43d64352ef86a1b224f017e7161ae.1339063659.git.trast@student.ethz.ch","subject":"Re: [PATCH v7 5/5] Implement line-history search (git log -L)","fromName":"Zbigniew JÄ™drzejewski-Szmek","fromEmail":"zbyszek@in.waw.pl","sentAt":"2012-06-10T09:38:14Z","receivedAt":"2012-06-10T09:38:14Z","isPatch":true,"sender":{"key":"zbyszek@in.waw.pl","avatar":"https://avatars.githubusercontent.com/u/349618?v=4"},"body":"On 06/07/2012 12:23 PM, Thomas Rast wrote:\n> The algorithm is then simply to process history in topological order\n> from newest to oldest, computing ranges and (partial) diffs. At\n> branch points, we need to merge the ranges we are watching. We will\n> find that many commits do not affect the chosen ranges, and mark them\n> TREESAME (in addition to those already filtered by pathspec limiting).\n> Another pass of history simplification then gets rid of such commits.\n\nHi,\n\nthis is absolutely great.\n\nWhen I run your example invocations, nothing is displayed for a very\nlong time. I understand that this is because of the extra\n'simplification pass', which means that whole results need to be ready\nbefore anything is displayed. Adding something like '-10' doesn't seem\nto have any effect, so I guess it is ignored. I hope that making '-'\nwork would not be to complicated, but more important would be getting\nincremental results. Will it be possible?\n\nZbyszek\n"},{"id":"193681","messageId":"7vlijpchm2.fsf@alter.siamese.dyndns.org","threadId":"30735","inReplyTo":"cover.1339063659.git.trast@student.ethz.ch","subject":"Re: [PATCH v7 0/5] git log -L, all new and shiny","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-06-15T04:40:53Z","receivedAt":"2012-06-15T04:40:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> I too thought it would never happen -- but then again this is still\n> not ready, I'm just trying to give it some exposure.\n> ...\n> There's also a longer-term wishlist hinted at in the commit message of\n> the main patch: the diff machinery currently makes no provisions for\n> chaining its various bells and whistles.\n\nI am not convinced that it is \"diff machinery makes no provivsions\"\nthat is the problem. Isn't it coming from the way the series limits\nthe output line range and reimplements its own output routine?\n\nAll the \"bells and whistles\" like diffstat, word coloring, etc. go\nthrough the xdi_diff_outf() interface, so isn't it the matter of\nlimiting lines that this interface calls back the \"bells and\nwhistles\" callback functions with?\n\nWhen you enter the diff machinery, you have the path and the line\nrange you are interested in of one side (lets say you are comparing\nside A and B, and have line range for side A).\n\nIf you\n\n - add a mechanism to pass the \"interesting\" line range and path\n down to the callchain from xdi_diff_outf() to xdiff_outf();\n\n - make one of these functions filter out (i.e. not call the\n callback xdiff_emit_consume_fn) hunks that do not overlap with\n the line range you are interested in (I would presume that they\n would be a few new fields in xdemitconf_t structure); and\n\n - while recording the corresponding line ranges in the other side\n of the hunks that are output,\n\nthat would give you\n\n - output that is limited to the \"interesting\" input range of side A;\n\n - the corresponding \"interesting\" range in the other side of the\n comparison, so that you can update the \"interesting\" range to\n feed to the next diff that compares side B with something else; and\n\n - for whatever processing the various \"bells and whistles\" callers\n already implement, as all their callbacks see are the lines in\n your \"interesting\" range.\n\nNo? Am I missing something?\n"},{"id":"193693","messageId":"8762as4sax.fsf@thomas.inf.ethz.ch","threadId":"30735","inReplyTo":"7vlijpchm2.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v7 0/5] git log -L, all new and shiny","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-06-15T13:29:26Z","receivedAt":"2012-06-15T13:29:26Z","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>> I too thought it would never happen -- but then again this is still\n>> not ready, I'm just trying to give it some exposure.\n>> ...\n>> There's also a longer-term wishlist hinted at in the commit message of\n>> the main patch: the diff machinery currently makes no provisions for\n>> chaining its various bells and whistles.\n>\n> I am not convinced that it is \"diff machinery makes no provivsions\"\n> that is the problem. Isn't it coming from the way the series limits\n> the output line range and reimplements its own output routine?\n\nWell, in a very circular logic sense, yes: I reimplement the output\nroutine because that's the only way I could think of doing it right now :-)\n\nHowever, notice that word-diff also reimplements its own output routine,\nthough it probably has a better standing since it is a different format.\n\n> - add a mechanism to pass the \"interesting\" line range and path\n> down to the callchain from xdi_diff_outf() to xdiff_outf();\n>\n> - make one of these functions filter out (i.e. not call the\n> callback xdiff_emit_consume_fn) hunks that do not overlap with\n> the line range you are interested in (I would presume that they\n> would be a few new fields in xdemitconf_t structure); and\n>\n> - while recording the corresponding line ranges in the other side\n> of the hunks that are output,\n\nHrm.\n\nThis would be the first backwards coupling between the revision-walk and\nthe diff generation parts, at least that I know of. Normally the\nrevision walker just calls out to the (line-wise, not tree-based) diff\nengine when it wants to show a commit. Now suddenly the diff engine is\nused (a lot, too) in simplifying the history.\n\nIdeally we would want to reuse diffs that have already been generated,\nas this is a very expensive process. The current log -L implementation\nmanages to do this at the cost of reimplementing the diff output\nroutines instead.\n\nYou solve it instead by mandating that the diff engine itself updates\nthe \"interesting\" ranges, but that needs a lot of inside knowledge: like\nin blame, we sometimes explore alternatives (e.g. for merges; or with\n-M, though log -L in this version does not implement that feature).\n\nSo we would end up with redoing diffs, or a very tight coupling, that\nIMHO just makes the mess worse.\n\nOr am I missing something?\n\nI instead have the vision that eventually diffs should be represented\ninternally as something like my pairs of struct range_set. Then we\ncould run more passes on them as needed, and have a \"common currency\"\nbetween all diff-related work. Only the last one should then actually\noutput the diff.\n\nThat still doesn't properly account for the case where the data format\nis no longer in terms of hunks (such as for word-diff, or the stat\nformats), though.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"193702","messageId":"7v1ulgd2f5.fsf@alter.siamese.dyndns.org","threadId":"30735","inReplyTo":"8762as4sax.fsf@thomas.inf.ethz.ch","subject":"Re: [PATCH v7 0/5] git log -L, all new and shiny","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-06-15T15:23:42Z","receivedAt":"2012-06-15T15:23:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> Junio C Hamano writes:\n>\n>> Thomas Rast writes:\n>>\n>>> I too thought it would never happen -- but then again this is still\n>>> not ready, I'm just trying to give it some exposure.\n>>> ...\n>>> There's also a longer-term wishlist hinted at in the commit message of\n>>> the main patch: the diff machinery currently makes no provisions for\n>>> chaining its various bells and whistles.\n>>\n>> I am not convinced that it is \"diff machinery makes no provivsions\"\n>> that is the problem. Isn't it coming from the way the series limits\n>> the output line range and reimplements its own output routine?\n>\n> Well, in a very circular logic sense, yes: I reimplement the output\n> routine because that's the only way I could think of doing it right now :-)\n>\n> However, notice that word-diff also reimplements its own output routine,\n> though it probably has a better standing since it is a different format.\n\nAlso notice that word-diff uses the same xdi_diff_outf() machinery\nto grab line-oriented diff as its input (cf. fn_out_consume), and\nthen does its thing on it. If you limit what fn_out_consume sees,\nyou can have word-diff do exactly what you want, no?\n\n> This would be the first backwards coupling between the revision-walk and\n> the diff generation parts, at least that I know of.\n\nI am not convinced if you need to have any unusual back-coupling to\nbegin with, by the way.\n\nIf you say \"git log -p [--options] -- pathspec\", the revision\nmachinery does filter commits that do not touch any paths that patch\npathspec with the TREESAME logic, but that does not necessarily mean\nyou will see _all_ the commits that are not TREESAME. If you for\nexample use ignore-space-change options, even the preimage and the\npostimage differ at the object name level (hence not TREESAME), the\ndiff machinery already knows how to tell the revision machinery not\nto show the log message and stuff, causing the commit to be skipped\nfrom the output, no?\n\nI do not know why you think you would need to do the filtering\n\"range comparison and union\" computation more than necessary. If\nthe user asks \"log -p\", you need to do it once per parent-child pair\nthat is not TREESAME at the place the current code calls run_diff().\nI suspect that \"log -p --stat\" could be improved to eliminate the\nseparate call to run_diffstat() by restructuring the code so that\nthe statistics is gathered inside run_diff(), but that is independent\nof this series. If this series hooked into the level I hinted in my\nearlier message, such an optimization will reduce calls to your\n\"range comparision and union\" computation for free.\n"},{"id":"193751","messageId":"7v1ulf94nq.fsf@alter.siamese.dyndns.org","threadId":"30735","inReplyTo":"7v1ulgd2f5.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v7 0/5] git log -L, all new and shiny","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-06-16T06:01:13Z","receivedAt":"2012-06-16T06:01:13Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Thomas Rast writes:\n>\n>> This would be the first backwards coupling between the revision-walk and\n>> the diff generation parts, at least that I know of.\n>\n> I am not convinced if you need to have any unusual back-coupling to\n> begin with, by the way.\n>\n> If you say \"git log -p [--options] -- pathspec\", the revision\n> machinery does filter commits that do not touch any paths that patch\n> pathspec with the TREESAME logic, but that does not necessarily mean\n> you will see _all_ the commits that are not TREESAME.\n\nLet's clarify this part a bit.\n\nImagine you have three commits on a single strand of pearls.\n\n\tA---B---C\n\nBetween A and B, you only corrected indentation errors in file F as\na clean-up step, and then between B and C, you did a real change.\n\"git diff A B -- F\" gives changes, \"git diff -w A B -- F\" does not.\nBoth \"git diff B C -- F\" and \"git diff -w B C -- F\" give you some\noutput.\n\nNow, \"git log --no-root -p -w C -- F\" will give you C but not B.\n\nLet's see how that happens.\n\nThe revision machinery looks at C and finds its parent B. It runs\nobject level tree comparison and finds that their trees are\ndifferent at path F. It makes a mental note that it may need to\nshow the log message of C, and asks the diff machinery to run\ndiff-tree between B and C. The diff machinery finds that it needs\nto show something even in the presense of -w option by actual\ncomparison, and just before showing the very first line of patch\noutput, it shows the log message of C (due to the earlier \"mental\nnote\").\n\nThen the revision machinery looks at B. It does the same between B\nand A, but this time around, the diff machinery finds that, even\nthough A and B were _not_ TREESAME at the revision traversal level,\nthere is nothing to be shown after filtering with the -w option.\nHence no patch is shown and log message for B is not shown, either.\n\nThe interesting part of the above is that we did not bother using\nthe -w comparison to affect TREESAME check at the revision traversal\nlevel.\n\nI consider your \"-L bottom,top\" essentially the same \"two blobs may\nbe different at the object name level, but after filtering the diff,\nthere may be no output\" filter just like the \"-w\" option is.\nInstead of filtering hunks that have changes only in whitespaces, it\nfilters hunks that do not overlap the given line range. So if you\nreplace \"-w\" in the above example with \"-L bottom,top\", exactly the\nsame thing should happen.\n\nThe current code structure does not consider the content level\nfiltering done by the \"-w\" when computing TREESAME. This DOES\naffect how the merges are simplified. If you and I start from a\ncommit X with full of indentation mistakes, you fix the earlier half\nof these mistakes and make commit T while I fix the later half of\nthese mistakes and make commit J, and we merge our results into\nmerge M:\n\n J---M\n / /\n X---T\n\nnone of \"diff -w J M\", \"diff -w T M\", \"diff -w X J\", \"diff -w X T\"\nwill output anything. \"git diff -p -w M\" will however traverse both\nbranches, even though in this example nothing will be shown in the\noutput, because no two trees in these four commits are TREESAME. \n\nIn the longer term, this _may_ be something we want to fix, but\nteaching the revision machinery about only \"-L bottom,top\" is not\nthe way to do it. Instead, we should devise a new mechanism to call\ninto the diff_patch machinery from the place where the revision\nmachinery computes TREESAME, and let it ask the filtered content\nlevel differences if any of these options (these flags flip the\nDIFF_FROM_CONTENTS diff option) are in use. As a part of the\nimplementation of that new mechanism, we may want to cache the patch\nsuch an early comparison produces, and reuse it when we actually\nproduce output, as an optimization. But I think that is not limited\nto the \"-L bottom,top\" option and an orthogonal issue, as it will\nwork equally well for existing \"-w\" filter (there may be others).\n\nThe above is where my recommendations are coming from. The first\nstep for \"-L bottom,top\" should be to hook it as a new kind of\nDIFF_FROM_CONTENTS option that compares two non-identical blobs but\npossibly yield empty result into the diff machinery at the same\nlevel as \"-w\". Once that is solidly done, we can think about\nupdating the merge simplification logic to take DIFF_FROM_CONTENTS\nchanges into account when it computes TREESAME.\n"},{"id":"193830","messageId":"87wr33wqzl.fsf@thomas.inf.ethz.ch","threadId":"30735","inReplyTo":"7v1ulf94nq.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v7 0/5] git log -L, all new and shiny","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2012-06-19T10:11:42Z","receivedAt":"2012-06-19T10:11:42Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano writes:\n\n> Junio C Hamano writes:\n>\n>> Thomas Rast writes:\n>>\n>>> This would be the first backwards coupling between the revision-walk and\n>>> the diff generation parts, at least that I know of.\n>>\n>> I am not convinced if you need to have any unusual back-coupling to\n>> begin with, by the way.\n>>\n>> If you say \"git log -p [--options] -- pathspec\", the revision\n>> machinery does filter commits that do not touch any paths that patch\n>> pathspec with the TREESAME logic, but that does not necessarily mean\n>> you will see _all_ the commits that are not TREESAME.\n[...]\n> The revision machinery looks at C and finds its parent B. It runs\n> object level tree comparison and finds that their trees are\n> different at path F. It makes a mental note that it may need to\n> show the log message of C, and asks the diff machinery to run\n> diff-tree between B and C. The diff machinery finds that it needs\n> to show something even in the presense of -w option by actual\n> comparison, and just before showing the very first line of patch\n> output, it shows the log message of C (due to the earlier \"mental\n> note\").\n>\n> Then the revision machinery looks at B. It does the same between B\n> and A, but this time around, the diff machinery finds that, even\n> though A and B were _not_ TREESAME at the revision traversal level,\n> there is nothing to be shown after filtering with the -w option.\n> Hence no patch is shown and log message for B is not shown, either.\n\nThanks for the great explanations.\n\nHaving spent some time letting this sink in (and being busy doing other\nthings), I think it's actually a good idea. It forces us to go back and\nchange it around so that the diff machinery gets a say _before_ we\nsimplify history. I think this bit will be important for log -L history\nto make sense, and it's a bug waiting to happen for the -w case.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"193831","messageId":"7vpq8v1tht.fsf@alter.siamese.dyndns.org","threadId":"30735","inReplyTo":"87wr33wqzl.fsf@thomas.inf.ethz.ch","subject":"Re: [PATCH v7 0/5] git log -L, all new and shiny","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-06-19T10:33:18Z","receivedAt":"2012-06-19T10:33:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n>> Then the revision machinery looks at B. It does the same between B\n>> and A, but this time around, the diff machinery finds that, even\n>> though A and B were _not_ TREESAME at the revision traversal level,\n>> there is nothing to be shown after filtering with the -w option.\n>> Hence no patch is shown and log message for B is not shown, either.\n>\n> Thanks for the great explanations.\n>\n> Having spent some time letting this sink in (and being busy doing other\n> things), I think it's actually a good idea. It forces us to go back and\n> change it around so that the diff machinery gets a say _before_ we\n> simplify history. I think this bit will be important for log -L history\n> to make sense, and it's a bug waiting to happen for the -w case.\n\nNote that this is not limited to \"diff_patch() already filters -w\".\n\nIf you are running with --diff-filter=A to grab only the additions,\nfor example, you may want the merge simplification to know about\nthis filtering as well.\n\nSo it is likely that you would want to hook diffcore_std(), not just\ndiff_flush(), to the TREESAME machinery. Obviously you would want\nto do this only for the merge commits; there is no point doing this\nfor single strand of pearls where the output phase already knows how\nto squelch output correctly.\n"}]}