{"thread":{"id":"26071","subject":"[PATCH v6.1 0/8] git log -L, cleaned up and (hopefully) fixed","startedAt":"2010-12-14T22:54:07Z","lastAt":"2010-12-15T00:20:48Z","messageCount":10,"participants":["Thomas Rast","Junio C Hamano"],"isPatch":true,"patchVersion":6,"patchTotal":8},"messages":[{"id":"158108","messageId":"cover.1292366984.git.trast@student.ethz.ch","threadId":"26071","inReplyTo":"7vhbegroj2.fsf@alter.siamese.dyndns.org","subject":"[PATCH v6.1 0/8] git log -L, cleaned up and (hopefully) fixed","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2010-12-14T22:54:07Z","receivedAt":"2010-12-14T22:54:07Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano wrote:\n> \n> This patch set has too many whitespace errors, and worse yet, cannot be\n> applied with \"git am --whitespace=fix\" because it has test vectors that\n> depend on having \"SP followed by HT\" (context lines of diff output) and\n> traling SP (graph output).\n> \n> Could you please straighten that out first?\n> \n> My preference is to protect offending whitespaces like this:\n> \n> \tsed -e 's/Q/ /g' -e 's/Z$//' >expected-no-M <<\\EOF\n[...]\n> which has an added benefit of making them more visible.\n\nSorry for the mess.  I stuck to the s/#$// style I already had in some\nplaces for now, but used the Qs and ran the rest through\nwhitespace=fix.  It now applies cleanly to master.\n\n\nBo Yang (8):\n  Refactor parse_loc\n  Export three functions from diff.c\n  Export rewrite_parents() for 'log -L'\n  Implement line-history search (git log -L)\n  log -L: support parent rewriting\n  log -L: add --graph prefix before output\n  log -L: add --full-line-diff option\n  log -L: implement move/copy detection (-M/-C)\n\n Documentation/blame-options.txt     |   19 +-\n Documentation/git-log.txt           |   22 +\n Documentation/line-range-format.txt |   18 +\n Makefile                            |    2 +\n builtin/blame.c                     |   99 +--\n builtin/log.c                       |   79 ++-\n diff.c                              |    6 +-\n diff.h                              |   17 +\n line.c                              | 2153 +++++++++++++++++++++++++++++++++++\n line.h                              |   72 ++\n revision.c                          |   22 +-\n revision.h                          |   23 +-\n t/t4301-log-line-single-history.sh  |  685 +++++++++++\n t/t4302-log-line-merge-history.sh   |  174 +++\n t/t4303-log-line-move-detect.sh     |  238 ++++\n t/t4304-log-line-copy-detect.sh     |  220 ++++\n t/t8003-blame-corner-cases.sh       |    6 +\n 17 files changed, 3730 insertions(+), 125 deletions(-)\n create mode 100644 Documentation/line-range-format.txt\n create mode 100644 line.c\n create mode 100644 line.h\n create mode 100755 t/t4301-log-line-single-history.sh\n create mode 100755 t/t4302-log-line-merge-history.sh\n create mode 100755 t/t4303-log-line-move-detect.sh\n create mode 100755 t/t4304-log-line-copy-detect.sh\n\n-- \n1.7.3.3.807.g6ee1f\n"},{"id":"158115","messageId":"d02cc233962cf4f1430025d2f61bd11602a64427.1292366984.git.trast@student.ethz.ch","threadId":"26071","inReplyTo":"cover.1292366984.git.trast@student.ethz.ch","subject":"[PATCH v6.1 1/8] Refactor parse_loc","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2010-12-14T22:54:08Z","receivedAt":"2010-12-14T22:54:08Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"From: Bo Yang <struggleyb.nku@gmail.com>\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 <struggleyb.nku@gmail.com>\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\n---\n Makefile                      |    2 +\n builtin/blame.c               |   99 +++-----------------------------------\n line.c                        |  106 +++++++++++++++++++++++++++++++++++++++++\n line.h                        |   23 +++++++++\n t/t8003-blame-corner-cases.sh |    6 ++\n 5 files changed, 145 insertions(+), 91 deletions(-)\n create mode 100644 line.c\n create mode 100644 line.h\n\ndiff --git a/Makefile b/Makefile\nindex 57d9c65..b015c61 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -519,6 +519,7 @@ LIB_H += grep.h\n LIB_H += hash.h\n LIB_H += help.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@@ -606,6 +607,7 @@ LIB_OBJS += help.o\n LIB_OBJS += hex.o\n LIB_OBJS += ident.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 aa30ec5..5eeddcb 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@@ -551,11 +552,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@@ -1925,83 +1931,6 @@ static unsigned parse_score(const char *arg)\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 <something>,+20\" to mean starting at <something>\n-\t * for 20 lines, or \"-L <something>,-5\" for 5 lines ending at\n-\t * <something>.\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(&regexp, spec + 1, REG_NEWLINE)) &&\n-\t    !(reg_error = regexec(&regexp, 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(&regexp);\n-\t\t*term++ = '/';\n-\t\treturn term;\n-\t}\n-\telse {\n-\t\tchar errbuf[1024];\n-\t\tregerror(reg_error, &regexp, 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@@ -2009,15 +1938,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@@ -2504,10 +2425,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..778cd7b\n--- /dev/null\n+++ b/line.c\n@@ -0,0 +1,106 @@\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/* Catch the '$' matcher, now it is used to match the last\n+\t * line of the file. */\n+\tif (spec[0] == '$') {\n+\t\t*ret = lines;\n+\t\treturn spec + 1;\n+\t}\n+\n+\t/* Allow \"-L <something>,+20\" to mean starting at <something>\n+\t * for 20 lines, or \"-L <something>,-5\" for 5 lines ending at\n+\t * <something>.\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(&regexp, spec + 1, REG_NEWLINE)) &&\n+\t    !(reg_error = regexec(&regexp, 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(&regexp);\n+\t\t*term++ = '/';\n+\t\treturn term;\n+\t} else {\n+\t\tchar errbuf[1024];\n+\t\tregerror(reg_error, &regexp, 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..51d313e 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 -L parses end' '\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.3.3.807.g6ee1f\n"},{"id":"158114","messageId":"26d2cee09e764a97adabb33c16f9a56da901a61d.1292366984.git.trast@student.ethz.ch","threadId":"26071","inReplyTo":"cover.1292366984.git.trast@student.ethz.ch","subject":"[PATCH v6.1 2/8] Export three functions from diff.c","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2010-12-14T22:54:09Z","receivedAt":"2010-12-14T22:54:09Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"From: Bo Yang <struggleyb.nku@gmail.com>\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 <struggleyb.nku@gmail.com>\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\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 0a43869..a16ce69 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -151,7 +151,7 @@ int git_diff_basic_config(const char *var, const char *value, void *cb)\n \treturn git_color_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@@ -332,7 +332,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@@ -2583,7 +2583,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 0083d92..165f368 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -12,6 +12,7 @@ struct diff_queue_struct;\n struct strbuf;\n struct diff_filespec;\n struct userdiff_driver;\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@@ -317,4 +318,20 @@ extern struct userdiff_driver *get_textconv(struct diff_filespec *one);\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 #endif /* DIFF_H */\n-- \n1.7.3.3.807.g6ee1f\n"},{"id":"158113","messageId":"94ab1278fe71a37dffa5db1b657f0a8689488ab1.1292366984.git.trast@student.ethz.ch","threadId":"26071","inReplyTo":"cover.1292366984.git.trast@student.ethz.ch","subject":"[PATCH v6.1 3/8] Export rewrite_parents() for 'log -L'","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2010-12-14T22:54:10Z","receivedAt":"2010-12-14T22:54:10Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"From: Bo Yang <struggleyb.nku@gmail.com>\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 <struggleyb.nku@gmail.com>\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\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 ded8812..6465c45 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1912,12 +1912,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@@ -1939,12 +1933,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@@ -2012,7 +2007,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 05659c6..8897368 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -193,4 +193,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.3.3.807.g6ee1f\n"},{"id":"158111","messageId":"426fca7313fc9466efa036b7b86947f23548fc26.1292366984.git.trast@student.ethz.ch","threadId":"26071","inReplyTo":"cover.1292366984.git.trast@student.ethz.ch","subject":"[PATCH v6.1 4/8] Implement line-history search (git log -L)","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2010-12-14T22:54:11Z","receivedAt":"2010-12-14T22:54:11Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"From: Bo Yang <struggleyb.nku@gmail.com>\n\n'struct diff_line_range' is the main data structure to keep\ntrack of the line ranges we are currently interested in. The\nuser starts digging from a line range, and after examining the\ndiff that affects that range by a commit, we can find a new\nrange that corresponds to this range. So, we will associate this\nnew range with the commit's parent commit.\n\nThere is one 'diff_line_range' for each file, and there are\nmultiple 'struct line_range' in each 'diff_line_range'. In this way,\nwe support multiple ranges.\n\nWithin 'struct line_range', there are multiple 'struct print_range'\nwhich represent a diff hunk.\n\nWhen going from a commit to its parents, we map the \"interesting\"\nrange of lines according to the change made.  For non-merge commits,\nwe just run map_range on the ranges, which works as follows:\n\n1. Run diffcore_std to find out the pre/postimage for each file.\n2. Run xdi_diff_hunks on each interesting set of pre/postimages.\n3. The map_range_cb callback is invoked for each hunk by the diff\n   engine, and we use it to calculate the pre-image range from the\n   post-image range in the function map_lines.\n\nFor merge commits, we run map_range once for every parent.  After that\nwe use a take_range pass to eliminate all ranges that are identical.\nIf any ranges remain after that, then the merge is considered\nnon-trivial.\n\nThe algorithm that maps lines from post-image to pre-image is in the\nfunction map_lines.\n\nTo correctly track the line ranges over several branches, we must make\nsure that we have processed all children before reaching the commit\nitself.  So we let the revision machinery topo-order the commits\nbefore doing anything.\n\nSigned-off-by: Bo Yang <struggleyb.nku@gmail.com>\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\n---\n Documentation/blame-options.txt     |   19 +-\n Documentation/git-log.txt           |   18 +\n Documentation/line-range-format.txt |   18 +\n builtin/log.c                       |   73 ++-\n line.c                              | 1331 ++++++++++++++++++++++++++++++++++-\n line.h                              |   49 ++\n revision.c                          |    6 +\n revision.h                          |   11 +-\n t/t4301-log-line-single-history.sh  |  685 ++++++++++++++++++\n 9 files changed, 2186 insertions(+), 24 deletions(-)\n create mode 100644 Documentation/line-range-format.txt\n create mode 100755 t/t4301-log-line-single-history.sh\n\ndiff --git a/Documentation/blame-options.txt b/Documentation/blame-options.txt\nindex 16e3c68..3526835 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.  <start> and <end> can take\n \tone of these forms:\n \n-\t- number\n-+\n-If <start> or <end> 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 <end> is a regex, it will search\n-starting at the line given by <start>.\n-+\n-\n-- +offset or -offset\n-+\n-This is only valid for <end> and will specify a number\n-of lines before or after the line given by <start>.\n-+\n+include::line-range-format.txt[]\n \n -l::\n \tShow long rev (Default: off).\ndiff --git a/Documentation/git-log.txt b/Documentation/git-log.txt\nindex ff41784..7fcf6e7 100644\n--- a/Documentation/git-log.txt\n+++ b/Documentation/git-log.txt\n@@ -66,6 +66,19 @@ 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 <start>,<end>:<file>::\n+\tTrace the evolution of the line range given by \"<start>,<end>\"\n+\twithin the <file>.  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+<start> and <end> 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 [\\--] <path>...::\n \tShow only commits that affect any of the specified paths. To\n \tprevent confusion with options and branch names, paths may need\n@@ -132,6 +145,11 @@ git log -p -m --first-parent::\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/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 <start> or <end> 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 <end> is a regex, it will search\n+starting at the line given by <start>.\n++\n+\n+- +offset or -offset\n++\n+This is only valid for <end> and will specify a number\n+of lines before or after the line given by <start>.\n++\ndiff --git a/builtin/log.c b/builtin/log.c\nindex d8c6c28..342d4de 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 \n /* Set a default date-time format for git log (\"log.date\" config variable) */\n static const char *default_date_mode = NULL;\n@@ -28,10 +29,21 @@\n static const char *fmt_patch_subject_prefix = \"PATCH\";\n static const char *fmt_pretty;\n \n-static const char * const builtin_log_usage =\n+static char builtin_log_usage[] =\n \t\"git log [<options>] [<since>..<until>] [[--] <path>...]\\n\"\n \t\"   or: git show [options] <object>...\";\n \n+static const char *log_opt_usage[] = {\n+\tbuiltin_log_usage,\n+\tNULL\n+};\n+\n+struct line_opt_callback_data {\n+\tstruct rev_info *rev;\n+\tconst char *prefix;\n+\tstruct diff_line_range *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@@ -49,12 +61,53 @@ static int parse_decoration_style(const char *var, const char *value)\n \treturn -1;\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 diff_line_range *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 diff_line_range));\n+\tdiff_line_range_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+\tdiff_line_range_append(r, range_arg);\n+\tdata->rev->line_level_traverse = 1;\n+\treturn 0;\n+}\n+\n static void cmd_log_init(int argc, const char **argv, const char *prefix,\n \t\t\t struct rev_info *rev, struct setup_revision_opt *opt)\n {\n \tint i;\n \tint decoration_given = 0;\n \tstruct userformat_want w;\n+\tstatic struct line_opt_callback_data line_cb = {0};\n+\n+\tstatic const struct option options[] = {\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 \trev->abbrev = DEFAULT_ABBREV;\n \trev->commit_format = CMIT_FMT_DEFAULT;\n@@ -75,6 +128,14 @@ static void cmd_log_init(int argc, const char **argv, const char *prefix,\n \t */\n \tif (argc == 2 && !strcmp(argv[1], \"-h\"))\n \t\tusage(builtin_log_usage);\n+\n+\tline_cb.rev = rev;\n+\tline_cb.prefix = prefix;\n+\n+\targc = parse_options(argc, argv, prefix, options, log_opt_usage,\n+\t\t\t     PARSE_OPT_KEEP_DASHDASH | PARSE_OPT_KEEP_ARGV0 |\n+\t\t\t     PARSE_OPT_KEEP_UNKNOWN);\n+\n \targc = setup_revisions(argc, argv, rev, opt);\n \n \tmemset(&w, 0, sizeof(w));\n@@ -125,6 +186,11 @@ static void cmd_log_init(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+\t/* Test whether line level history is asked for */\n+\tif (rev->line_level_traverse)\n+\t\tline_log_init(rev, line_cb.ranges);\n+\n \tsetup_pager();\n }\n \n@@ -509,7 +575,10 @@ int cmd_log(int argc, const char **argv, const char *prefix)\n \tmemset(&opt, 0, sizeof(opt));\n \topt.def = \"HEAD\";\n \tcmd_log_init(argc, argv, prefix, &rev, &opt);\n-\treturn cmd_log_walk(&rev);\n+\tif (rev.line_level_traverse)\n+\t\treturn line_log_walk(&rev);\n+\telse\n+\t\treturn cmd_log_walk(&rev);\n }\n \n /* format-patch */\ndiff --git a/line.c b/line.c\nindex 778cd7b..1ffcaba 100644\n--- a/line.c\n+++ b/line.c\n@@ -1,6 +1,124 @@\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 \"line.h\"\n \n+struct print_range {\n+\tint start, end;\t\t/* Line range of post-image */\n+\tint pstart, pend;\t/* Line range of pre-image */\n+\tint line_added : 1;\t/* whether this range is added */\n+};\n+\n+struct print_pair {\n+\tint alloc, nr;\n+\tstruct print_range *ranges;\n+};\n+\n+struct line_range {\n+\tconst char *arg;\t/* The argument to specify this line range */\n+\tlong start, end;\t/* The interesting line range of current commit */\n+\tlong pstart, pend;\t/* The corresponding range of parent commit */\n+\tstruct print_pair pair;\n+\t\t\t/* The changed lines inside this range */\n+\tunsigned int diff:1;\n+};\n+\n+/*\n+ * Eek-a-global\n+ */\n+\n+static int limited;\n+\n+/*\n+ * These could be in line.h but we put them here so the functions can\n+ * be static.\n+ */\n+\n+static struct line_range *diff_line_range_insert(struct diff_line_range *r,\n+\t       const char *arg, int start, int end);\n+\n+static void diff_line_range_clear(struct diff_line_range *r);\n+\n+static struct diff_line_range *diff_line_range_merge(\n+\t       struct diff_line_range *out,\n+\t       struct diff_line_range *other);\n+\n+static struct diff_line_range *diff_line_range_clone(struct diff_line_range *r);\n+\n+static struct diff_line_range *diff_line_range_clone_deeply(struct diff_line_range *r);\n+\n+static void add_line_range(struct rev_info *revs, struct commit *commit,\n+\t       struct diff_line_range *r);\n+\n+static struct diff_line_range *lookup_line_range(struct rev_info *revs,\n+\t       struct commit *commit);\n+\n+/*\n+ * Data structure helpers\n+ */\n+\n+static inline void print_range_init(struct print_range *r)\n+{\n+\tr->start = r->end = 0;\n+\tr->pstart = r->pend = 0;\n+\tr->line_added = 0;\n+}\n+\n+static inline void print_pair_init(struct print_pair *p)\n+{\n+\tp->alloc = p->nr = 0;\n+\tp->ranges = NULL;\n+}\n+\n+static inline void print_pair_grow(struct print_pair *p)\n+{\n+\tp->nr++;\n+\tALLOC_GROW(p->ranges, p->nr, p->alloc);\n+}\n+\n+static inline void print_pair_clear(struct print_pair *p)\n+{\n+\tp->alloc = p->nr = 0;\n+\tif (p->ranges)\n+\t\tfree(p->ranges);\n+\tp->ranges = NULL;\n+}\n+\n+static inline void line_range_init(struct line_range *r)\n+{\n+\tr->arg = NULL;\n+\tr->start = r->end = 0;\n+\tr->pstart = r->pend = 0;\n+\tprint_pair_init(&(r->pair));\n+\tr->copy_score = 0;\n+\tr->diff = 0;\n+}\n+\n+static inline void line_range_clear(struct line_range *r)\n+{\n+\tr->arg = NULL;\n+\tr->start = r->end = 0;\n+\tr->pstart = r->pend = 0;\n+\tprint_pair_clear(&r->pair);\n+\tr->diff = 0;\n+}\n+\n+static inline void diff_line_range_grow(struct diff_line_range *r)\n+{\n+\tr->nr++;\n+\tALLOC_GROW(r->ranges, r->nr, r->alloc);\n+\tline_range_init((r->ranges + r->nr - 1));\n+}\n+\n /*\n  * Parse one item in the -L option\n  */\n@@ -17,7 +135,8 @@\n \t/* Catch the '$' matcher, now it is used to match the last\n \t * line of the file. */\n \tif (spec[0] == '$') {\n-\t\t*ret = lines;\n+\t\tif (ret)\n+\t\t\t*ret = lines;\n \t\treturn spec + 1;\n \t}\n \n@@ -28,6 +147,8 @@\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@@ -42,7 +163,8 @@\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@@ -56,6 +178,10 @@\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@@ -104,3 +230,1204 @@ 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 void free_diff_line_ranges(struct diff_line_range *r)\n+{\n+\twhile (r) {\n+\t\tstruct diff_line_range *next = r->next;\n+\t\tdiff_line_range_clear(r);\n+\t\tfree(r);\n+\t\tr = next;\n+\t}\n+}\n+\n+static struct object *verify_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 commit;\n+}\n+\n+static void fill_blob_sha1(struct commit *commit, struct diff_line_range *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\tgoto error;\n+\t\tfill_filespec(r->spec, sha1, mode);\n+\t\tr = r->next;\n+\t}\n+\n+\treturn;\n+error:\n+\tdie(\"There is no path %s in the commit\", r->spec->path);\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 diff_line_range *r)\n+{\n+\tint i;\n+\tstruct line_range *old_range = NULL;\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->nr;\n+\t\tassert(spec);\n+\t\tfill_blob_sha1(commit, r);\n+\t\told_range = r->ranges;\n+\t\tr->ranges = NULL;\n+\t\tr->nr = r->alloc = 0;\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\tif (parse_range_arg(old_range[i].arg, nth_line, &cb_data,\n+\t\t\t\t\t    lines-1, &begin, &end))\n+\t\t\t\tdie(\"malformed -L argument '%s'\", old_range[i].arg);\n+\t\t\tdiff_line_range_insert(r, old_range[i].arg, begin, end);\n+\t\t}\n+\n+\t\tfree(ends);\n+\t\tends = NULL;\n+\n+\t\tr = r->next;\n+\t\tfree(old_range);\n+\t}\n+}\n+\n+/*\n+ * Insert a new line range into a diff_line_range struct, and keep the\n+ * r->ranges sorted by their starting line number.\n+ */\n+static struct line_range *diff_line_range_insert(struct diff_line_range *r,\n+\t\tconst char *arg, int start, int end)\n+{\n+\tint i = 0;\n+\tstruct line_range *rs = r->ranges;\n+\tint left_merge = 0, right_merge = 0;\n+\n+\tassert(r);\n+\tassert(start <= end);\n+\n+\tif (r->nr == 0 || rs[r->nr - 1].end < start - 1) {\n+\t\tint num = 0;\n+\t\tdiff_line_range_grow(r);\n+\t\trs = r->ranges;\n+\t\tnum = r->nr - 1;\n+\t\trs[num].arg = arg;\n+\t\trs[num].start = start;\n+\t\trs[num].end = end;\n+\t\treturn rs + num;\n+\t}\n+\n+\tfor (; i < r->nr; i++) {\n+\t\tif (rs[i].end < start - 1)\n+\t\t\tcontinue;\n+\t\tif (rs[i].end == start - 1) {\n+\t\t\trs[i].end = end;\n+\t\t\tright_merge = 1;\n+\t\t\tgoto out;\n+\t\t}\n+\n+\t\tassert(rs[i].end > start - 1);\n+\t\tif (rs[i].start <= start) {\n+\t\t\tif (rs[i].end < end) {\n+\t\t\t\trs[i].end = end;\n+\t\t\t\tright_merge = 1;\n+\t\t\t}\n+\t\t\tgoto out;\n+\t\t} else if (rs[i].start <= end + 1) {\n+\t\t\trs[i].start = start;\n+\t\t\tleft_merge = 1;\n+\t\t\tif (rs[i].end < end) {\n+\t\t\t\trs[i].end = end;\n+\t\t\t\tright_merge = 1;\n+\t\t\t}\n+\t\t\tgoto out;\n+\t\t} else {\n+\t\t\tint num = r->nr - i;\n+\t\t\tdiff_line_range_grow(r);\n+\t\t\trs = r->ranges;\n+\t\t\tmemmove(rs + i + 1, rs + i, num * sizeof(struct line_range));\n+\t\t\trs[i].arg = arg;\n+\t\t\trs[i].start = start;\n+\t\t\trs[i].end = end;\n+\t\t\tgoto out;\n+\t\t}\n+\t}\n+\n+out:\n+\tassert(r->nr != i);\n+\tif (left_merge) {\n+\t\tint j = i;\n+\t\tfor (; j > -1; j--) {\n+\t\t\tif (rs[j].end >= rs[i].start - 1)\n+\t\t\t\tif (rs[j].start < rs[i].start)\n+\t\t\t\t\trs[i].start = rs[j].start;\n+\t\t}\n+\t\tmemmove(rs + j + 1, rs + i, (r->nr - i) * sizeof(struct line_range));\n+\t\tr->nr -= i - j - 1;\n+\t}\n+\tif (right_merge) {\n+\t\tint j = i;\n+\t\tfor (; j < r->nr; j++) {\n+\t\t\tif (rs[j].start <= rs[i].end + 1)\n+\t\t\t\tif (rs[j].end > rs[i].end)\n+\t\t\t\t\trs[i].end = rs[j].end;\n+\t\t}\n+\t\tif (j < r->nr)\n+\t\t\tmemmove(rs + i + 1, rs + j, (r->nr - j) * sizeof(struct line_range));\n+\t\tr->nr -= j - i - 1;\n+\t}\n+\tassert(r->nr);\n+\n+\treturn rs + i;\n+}\n+\n+static void diff_line_range_clear(struct diff_line_range *r)\n+{\n+\tint i = 0, zero = 0;\n+\n+\tfor (; i < r->nr; i++) {\n+\t\tstruct line_range *rg = r->ranges + i;\n+\t\tline_range_clear(rg);\n+\t}\n+\n+\tif (r->prev) {\n+\t\tzero = 0;\n+\t\tif (r->prev->count == 1)\n+\t\t\tzero = 1;\n+\t\tfree_filespec(r->prev);\n+\t\tif (zero)\n+\t\t\tr->prev = NULL;\n+\t}\n+\tif (r->spec) {\n+\t\tzero = 0;\n+\t\tif (r->spec->count == 1)\n+\t\t\tzero = 1;\n+\t\tfree_filespec(r->spec);\n+\t\tif (zero)\n+\t\t\tr->spec = NULL;\n+\t}\n+\n+\tr->status = '\\0';\n+\tr->alloc = r->nr = 0;\n+\n+\tif (r->ranges)\n+\t\tfree(r->ranges);\n+\tr->ranges = NULL;\n+\tr->next = NULL;\n+}\n+\n+void diff_line_range_append(struct diff_line_range *r, const char *arg)\n+{\n+\tdiff_line_range_grow(r);\n+\tr->ranges[r->nr - 1].arg = arg;\n+}\n+\n+static struct diff_line_range *diff_line_range_clone(struct diff_line_range *r)\n+{\n+\tstruct diff_line_range *ret = xmalloc(sizeof(*ret));\n+\tint i = 0;\n+\n+\tassert(r);\n+\tdiff_line_range_init(ret);\n+\tret->ranges = xcalloc(r->nr, sizeof(struct line_range));\n+\tmemcpy(ret->ranges, r->ranges, sizeof(struct line_range) * r->nr);\n+\n+\tret->alloc = ret->nr = r->nr;\n+\n+\tfor (; i < ret->nr; i++)\n+\t\tprint_pair_init(&ret->ranges[i].pair);\n+\n+\tret->spec = r->spec;\n+\tassert(ret->spec);\n+\tret->spec->count++;\n+\n+\treturn ret;\n+}\n+\n+static struct diff_line_range *\n+diff_line_range_clone_deeply(struct diff_line_range *r)\n+{\n+\tstruct diff_line_range *ret = NULL;\n+\tstruct diff_line_range *tmp = NULL, *prev = NULL;\n+\n+\tassert(r);\n+\tret = tmp = prev = diff_line_range_clone(r);\n+\tr = r->next;\n+\twhile (r) {\n+\t\ttmp = diff_line_range_clone(r);\n+\t\tprev->next = tmp;\n+\t\tprev = tmp;\n+\t\tr = r->next;\n+\t}\n+\n+\treturn ret;\n+}\n+\n+static struct diff_line_range *diff_line_range_merge(struct diff_line_range *out,\n+\t\tstruct diff_line_range *other)\n+{\n+\tstruct diff_line_range *one = out, *two = other;\n+\tstruct diff_line_range *pone = NULL;\n+\n+\twhile (one) {\n+\t\tstruct diff_line_range *ptwo;\n+\t\ttwo = other;\n+\t\tptwo = other;\n+\t\twhile (two) {\n+\t\t\tif (!strcmp(one->spec->path, two->spec->path)) {\n+\t\t\t\tint i = 0;\n+\t\t\t\tfor (; i < two->nr; i++) {\n+\t\t\t\t\tdiff_line_range_insert(one, NULL,\n+\t\t\t\t\t\ttwo->ranges[i].start,\n+\t\t\t\t\t\ttwo->ranges[i].end);\n+\t\t\t\t}\n+\t\t\t\tif (two == other)\n+\t\t\t\t\tother = other->next;\n+\t\t\t\telse\n+\t\t\t\t\tptwo->next = two->next;\n+\t\t\t\tdiff_line_range_clear(two);\n+\t\t\t\tfree(two);\n+\t\t\t\ttwo = NULL;\n+\n+\t\t\t\tbreak;\n+\t\t\t}\n+\n+\t\t\tptwo = two;\n+\t\t\ttwo = two->next;\n+\t\t}\n+\n+\t\tpone = one;\n+\t\tone = one->next;\n+\t}\n+\tpone->next = other;\n+\n+\treturn out;\n+}\n+\n+static void add_line_range(struct rev_info *revs, struct commit *commit,\n+\t\tstruct diff_line_range *r)\n+{\n+\tstruct diff_line_range *ret = NULL;\n+\n+\tif (r) {\n+\t\tret = lookup_decoration(&revs->line_range, &commit->object);\n+\t\tif (ret)\n+\t\t\tdiff_line_range_merge(ret, r);\n+\t\telse\n+\t\t\tadd_decoration(&revs->line_range, &commit->object, r);\n+\t\tcommit->object.flags |= RANGE_UPDATE;\n+\t}\n+}\n+\n+static void clear_commit_line_range(struct rev_info *revs, struct commit *commit)\n+{\n+\tstruct diff_line_range *r;\n+\tr = lookup_decoration(&revs->line_range, &commit->object);\n+\tif (!r)\n+\t\treturn;\n+\tfree_diff_line_ranges(r);\n+\tadd_decoration(&revs->line_range, &commit->object, NULL);\n+}\n+\n+static struct diff_line_range *lookup_line_range(struct rev_info *revs,\n+\t\tstruct commit *commit)\n+{\n+\tstruct diff_line_range *ret = NULL;\n+\n+\tret = lookup_decoration(&revs->line_range, &commit->object);\n+\treturn ret;\n+}\n+\n+void line_log_init(struct rev_info *rev, struct diff_line_range *r)\n+{\n+\tstruct commit *commit = NULL;\n+\tstruct diff_options *opt = &rev->diffopt;\n+\n+\tcommit = (struct commit *)verify_commit(rev);\n+\tparse_lines(commit, r);\n+\n+\tadd_line_range(rev, commit, r);\n+\t/*\n+\t * Note we support -M/-C to detect file rename\n+\t */\n+\topt->nr_paths = 0;\n+\tdiff_tree_release_paths(opt);\n+}\n+\n+struct take_range_cb_data {\n+\tstruct diff_line_range *interesting;\t/* currently interesting ranges */\n+\tstruct diff_line_range *range;\n+\t\t/* the ranges corresponds to the interesting ranges of parent commit */\n+\tlong plno, tlno;\n+\t\t/* the last line number of diff hunk */\n+\tint diff;\n+\t\t/* whether there is some line changes between the current\n+\t\t * commit and its parent */\n+};\n+\n+#define SCALE_FACTOR 4\n+/*\n+ * [p_start, p_end] represents the pre-image of current diff hunk,\n+ * [t_start, t_end] represents the post-image of the current diff hunk,\n+ * [start, end] represents the currently interesting line range in\n+ * post-image,\n+ * [o_start, o_end] represents the original line range that coresponds\n+ * to current line range.\n+ */\n+void map_lines(long p_start, long p_end, long t_start, long t_end,\n+\t\tlong start, long end, long *o_start, long *o_end)\n+{\n+\t/*\n+\t * Normally, p_start should be less than p_end, so does the\n+\t * t_start and t_end. But when the line range is added from\n+\t * scratch, p_start will be greater than p_end. When the line\n+\t * range is deleted, t_start will be greater than t_end.\n+\t */\n+\tif (p_start > p_end) {\n+\t\t*o_start = *o_end = 0;\n+\t\treturn;\n+\t}\n+\t/* A deletion */\n+\tif (t_start > t_end) {\n+\t\t*o_start = p_start;\n+\t\t*o_end = p_end;\n+\t\treturn;\n+\t}\n+\n+\tif (start == t_start && end == t_end) {\n+\t\t*o_start = p_start;\n+\t\t*o_end = p_end;\n+\t\treturn;\n+\t}\n+\n+\t/*\n+\t * A heuristic for lines mapping:\n+\t *\n+\t * When the pre-image is no more than 1/SCALE_FACTOR of the post-image,\n+\t * there is no effective way to find out which part of pre-image\n+\t * corresponds to the currently interesting range of post-image.\n+\t * And we are in the danger of tracking totally useless lines.\n+\t * So, we just treat all the post-image lines as added from scratch.\n+\t */\n+\tif (SCALE_FACTOR * (p_end - p_start + 1) < (t_end - t_start + 1)) {\n+\t\t*o_start = *o_end = 0;\n+\t\treturn;\n+\t}\n+\n+\t*o_start = p_start + start - t_start;\n+\t*o_end = p_end - (t_end - end);\n+\n+\tif (*o_start > *o_end) {\n+\t\tint temp = *o_start;\n+\t\t*o_start = *o_end;\n+\t\t*o_end = temp;\n+\t}\n+\n+\tif (*o_start < p_start)\n+\t\t*o_start = p_start;\n+\tif (*o_end > p_end)\n+\t\t*o_end = p_end;\n+}\n+\n+/*\n+ * When same == 1:\n+ * [p_start, p_end] represents the diff hunk line range of pre-image,\n+ * [t_start, t_end] represents the diff hunk line range of post-image.\n+ * When same == 0, they represent a range of identical lines between\n+ * two images.\n+ *\n+ * This function find out the corresponding line ranges of currently\n+ * interesting ranges which this diff hunk touches.\n+ */\n+static void map_range(struct take_range_cb_data *data, int same,\n+\t\tlong p_start, long p_end, long t_start, long t_end)\n+{\n+\tstruct line_range *ranges = data->interesting->ranges;\n+\tlong takens, takene, start, end;\n+\tint i = 0, out = 0, added = 0;\n+\tlong op_start = p_start, op_end = p_end, ot_start = t_start, ot_end = t_end;\n+\n+\tfor (; i < data->interesting->nr; i++) {\n+\t\tadded = 0;\n+\t\tif (t_start > ranges[i].end)\n+\t\t\tcontinue;\n+\t\tif (t_end < ranges[i].start)\n+\t\t\tbreak;\n+\n+\t\tif (t_start > ranges[i].start) {\n+\t\t\tstart = t_start;\n+\t\t\ttakens = p_start;\n+\t\t} else {\n+\t\t\tstart = ranges[i].start;\n+\t\t\ttakens = p_start + start - t_start;\n+\t\t}\n+\n+\t\tif (t_end >= ranges[i].end) {\n+\t\t\tend = ranges[i].end;\n+\t\t\ttakene = p_start + end - t_start;\n+\t\t} else {\n+\t\t\tend = t_end;\n+\t\t\ttakene = p_end;\n+\t\t\tout = 1;\n+\t\t}\n+\n+\t\tif (!same) {\n+\t\t\tstruct print_pair *pair = &ranges[i].pair;\n+\t\t\tstruct print_range *rr = NULL;\n+\t\t\tprint_pair_grow(pair);\n+\t\t\trr = pair->ranges + pair->nr - 1;\n+\t\t\tprint_range_init(rr);\n+\t\t\trr->start = start;\n+\t\t\trr->end = end;\n+\t\t\tmap_lines(op_start, op_end, ot_start, ot_end, start, end,\n+\t\t\t\t\t&takens, &takene);\n+\t\t\tif (takens == 0 && takene == 0) {\n+\t\t\t\tadded = 1;\n+\t\t\t\trr->line_added = 1;\n+\t\t\t}\n+\t\t\trr->pstart = takens;\n+\t\t\trr->pend = takene;\n+\t\t\tdata->diff = 1;\n+\t\t\tdata->interesting->diff = 1;\n+\t\t\tranges[i].diff = 1;\n+\t\t}\n+\t\tif (added) {\n+\t\t\t/* Code movement/copy goes here */\n+\t\t} else {\n+\t\t\tstruct line_range *added_range = diff_line_range_insert(data->range,\n+\t\t\t\t\tNULL, takens, takene);\n+\t\t\tassert(added_range);\n+\t\t\tranges[i].pstart = added_range->start;\n+\t\t\tranges[i].pend = added_range->end;\n+\t\t}\n+\n+\t\tt_start = end + 1;\n+\t\tp_start = takene + 1;\n+\n+\t\tif (out)\n+\t\t\tbreak;\n+\t}\n+}\n+\n+/*\n+ * [p_start, p_end] represents the line range of pre-image,\n+ * [t_start, t_end] represents the line range of post-image,\n+ * and they are identical lines.\n+ *\n+ * This function substracts out the identical lines between current\n+ * commit and its parent, from currently interesting ranges.\n+ */\n+static void take_range(struct take_range_cb_data *data,\n+\t\tlong p_start, long p_end, long t_start, long t_end)\n+{\n+\tstruct line_range *ranges = data->interesting->ranges;\n+\tlong takens, takene, start, end;\n+\tint i = 0, out = 0, added = 0;\n+\n+\tfor (; i < data->interesting->nr; i++) {\n+\t\tadded = 0;\n+\t\tif (t_start > ranges[i].end)\n+\t\t\tcontinue;\n+\t\tif (t_end < ranges[i].start)\n+\t\t\tbreak;\n+\n+\t\tif (t_start > ranges[i].start) {\n+\t\t\tlong tmp = ranges[i].end;\n+\t\t\tranges[i].end = t_start - 1;\n+\t\t\tstart = t_start;\n+\t\t\ttakens = p_start;\n+\t\t\tif (t_end >= tmp) {\n+\t\t\t\tend = tmp;\n+\t\t\t\ttakene = p_start + end - t_start;\n+\t\t\t\tp_start = takene + 1;\n+\t\t\t\tt_start = end + 1;\n+\t\t\t} else {\n+\t\t\t\tend = t_end;\n+\t\t\t\ttakene = p_end;\n+\t\t\t\tdiff_line_range_insert(data->interesting, NULL,\n+\t\t\t\t\tt_end + 1, tmp);\n+\t\t\t\tout = 1;\n+\t\t\t}\n+\t\t} else {\n+\t\t\tstart = ranges[i].start;\n+\t\t\ttakens = p_start + start - t_start;\n+\t\t\tif (t_end >= ranges[i].end) {\n+\t\t\t\tint num = data->interesting->nr - 1;\n+\t\t\t\tend = ranges[i].end;\n+\t\t\t\ttakene = p_start + end - t_start;\n+\t\t\t\tt_start = end + 1;\n+\t\t\t\tp_start = takene + 1;\n+\t\t\t\tmemmove(ranges + i, ranges + i + 1, (num - i) * sizeof(*ranges));\n+\t\t\t\tdata->interesting->nr = num;\n+\t\t\t\ti--;\n+\t\t\t} else {\n+\t\t\t\tend = t_end;\n+\t\t\t\ttakene = p_end;\n+\t\t\t\tranges[i].start = t_end + 1;\n+\t\t\t\tout = 1;\n+\t\t\t}\n+\t\t}\n+\n+\t\tdiff_line_range_insert(data->range, NULL, takens, takene);\n+\n+\t\tif (out)\n+\t\t\tbreak;\n+\t}\n+}\n+\n+static void take_range_cb(void *data, long same, long p_next, long t_next)\n+{\n+\tstruct take_range_cb_data *d = data;\n+\tlong p_start = d->plno + 1, t_start = d->tlno + 1;\n+\tlong p_end = p_start + same - t_start, t_end = same;\n+\n+\t/* If one file is added from scratch, we should not bother to call\n+\t * take_range, since there is nothing to take\n+\t */\n+\tif (t_end >= t_start)\n+\t\ttake_range(d, p_start, p_end, t_start, t_end);\n+\td->plno = p_next;\n+\td->tlno = t_next;\n+}\n+\n+static void map_range_cb(void *data, long same, long p_next, long t_next)\n+{\n+\tstruct take_range_cb_data *d = data;\n+\n+\tlong p_start = d->plno + 1;\n+\tlong t_start = d->tlno + 1;\n+\tlong p_end = same - t_start + p_start;\n+\tlong t_end = same;\n+\n+\t/* Firstly, take the unchanged lines from child */\n+\tif (t_end >= t_start)\n+\t\tmap_range(d, 1, p_start, p_end, t_start, t_end);\n+\n+\t/* find out which lines to print */\n+\tt_start = same + 1;\n+\tp_start = d->plno + t_start - d->tlno;\n+\tmap_range(d, 0, p_start, p_next, t_start, t_next);\n+\n+\td->plno = p_next;\n+\td->tlno = t_next;\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+/*\n+ * We support two kinds of operation in this function:\n+ * 1. map == 0, take the same lines from the current commit and assign it\n+ *              to parent;\n+ * 2. map == 1, in addition to the same lines, we also map the changed lines\n+ *              from the current commit to the parent according to the\n+ *              diff output.\n+ * take_range_cb and take_range are used to take same lines from current commit\n+ * to parents.\n+ * map_range_cb and map_range are used to map line ranges to the parent.\n+ */\n+static void assign_range_to_parent(struct rev_info *rev, struct commit *commit,\n+\t\tstruct commit *parent, struct diff_line_range *range,\n+\t\tstruct diff_options *opt, int map)\n+{\n+\tstruct diff_line_range *final_range = xmalloc(sizeof(*final_range));\n+\tstruct diff_line_range *cur_range = final_range;\n+\tstruct diff_line_range *prev_range = final_range;\n+\tstruct diff_line_range *rg = NULL;\n+\tvoid *tree1 = NULL, *tree2 = NULL;\n+\tstruct tree_desc desc1, desc2;\n+\tstruct diff_queue_struct *queue;\n+\tstruct take_range_cb_data cb_data = {NULL, cur_range, 0, 0};\n+\txpparam_t xpp;\n+\txdemitconf_t xecfg;\n+\tint i, diff = 0;\n+\txdiff_emit_hunk_consume_fn fn = map ? map_range_cb : take_range_cb;\n+\n+\tdiff_line_range_init(cur_range);\n+\tmemset(&xpp, 0, sizeof(xpp));\n+\tmemset(&xecfg, 0, sizeof(xecfg));\n+\txecfg.ctxlen = xecfg.interhunkctxlen = 0;\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+\n+\tqueue = &diff_queued_diff;\n+\tfor (i = 0; i < queue->nr; i++) {\n+\t\tstruct diff_filepair *pair = queue->queue[i];\n+\t\tstruct diff_line_range *rg = range;\n+\t\tmmfile_t file_parent, file_t;\n+\t\tassert(pair->two->path);\n+\t\twhile (rg) {\n+\t\t\tassert(rg->spec->path);\n+\t\t\tif (!strcmp(rg->spec->path, pair->two->path))\n+\t\t\t\tbreak;\n+\t\t\trg = rg->next;\n+\t\t}\n+\n+\t\tif (!rg)\n+\t\t\tcontinue;\n+\t\trg->touched = 1;\n+\t\tif (rg->nr == 0)\n+\t\t\tcontinue;\n+\n+\t\trg->status = pair->status;\n+\t\tassert(pair->two->sha1_valid);\n+\t\tdiff_populate_filespec(pair->two, 0);\n+\t\tfile_t.ptr = pair->two->data;\n+\t\tfile_t.size = pair->two->size;\n+\n+\t\tif (rg->prev)\n+\t\t\tfree_filespec(rg->prev);\n+\t\trg->prev = pair->one;\n+\t\trg->prev->count++;\n+\t\tif (pair->one->sha1_valid) {\n+\t\t\tdiff_populate_filespec(pair->one, 0);\n+\t\t\tfile_parent.ptr = pair->one->data;\n+\t\t\tfile_parent.size = pair->one->size;\n+\t\t} else {\n+\t\t\tfile_parent.ptr = \"\";\n+\t\t\tfile_parent.size = 0;\n+\t\t}\n+\n+\t\tif (cur_range->nr != 0) {\n+\t\t\tstruct diff_line_range *tmp = xmalloc(sizeof(*tmp));\n+\t\t\tcur_range->next = tmp;\n+\t\t\tprev_range = cur_range;\n+\t\t\tcur_range = tmp;\n+\t\t} else if (cur_range->spec)\n+\t\t\tdiff_line_range_clear(cur_range);\n+\n+\t\tdiff_line_range_init(cur_range);\n+\t\tif (pair->one->sha1_valid) {\n+\t\t\tcur_range->spec = pair->one;\n+\t\t\tcur_range->spec->count++;\n+\t\t} else {\n+\t\t\tassert(is_null_sha1(pair->one->sha1));\n+\t\t\tcur_range->spec = pair->two;\n+\t\t\tcur_range->spec->count++;\n+\t\t}\n+\n+\t\tcb_data.interesting = rg;\n+\t\tcb_data.range = cur_range;\n+\t\tcb_data.diff = 0;\n+\t\tcb_data.plno = cb_data.tlno = 0;\n+\t\txdi_diff_hunks(&file_parent, &file_t, fn, &cb_data, &xpp, &xecfg);\n+\t\tif (cb_data.diff)\n+\t\t\tdiff = 1;\n+\t\t/*\n+\t\t * The remain part is the same part.\n+\t\t * Instead of calculating the true line number of the two files,\n+\t\t * use the biggest integer.\n+\t\t */\n+\t\tif (map)\n+\t\t\tmap_range(&cb_data, 1, cb_data.plno + 1,\n+\t\t\t\t  INT_MAX, cb_data.tlno + 1, INT_MAX);\n+\t\telse\n+\t\t\ttake_range(&cb_data, cb_data.plno + 1,\n+\t\t\t\t   INT_MAX, cb_data.tlno + 1, INT_MAX);\n+\t}\n+\topt->output_format = DIFF_FORMAT_NO_OUTPUT;\n+\tdiff_flush(opt);\n+\n+\t/*\n+\t * Collect the untouched ranges, this comes from the files not changed\n+\t * between two commit.\n+\t */\n+\trg = range;\n+\twhile (rg) {\n+\t\t/* clear the touched one to make it usable in next round */\n+\t\tif (rg->touched) {\n+\t\t\trg->touched = 0;\n+\t\t} else {\n+\t\t\tstruct diff_line_range *untouched = diff_line_range_clone(rg);\n+\t\t\tif (prev_range == final_range && final_range->nr == 0) {\n+\t\t\t\tfinal_range = prev_range = untouched;\n+\t\t\t} else {\n+\t\t\t\tprev_range->next = untouched;\n+\t\t\t\tprev_range = untouched;\n+\t\t\t}\n+\t\t}\n+\t\trg = rg->next;\n+\t}\n+\n+\tif (cur_range->nr == 0) {\n+\t\tdiff_line_range_clear(cur_range);\n+\t\tfree(cur_range);\n+\t\tif (prev_range == cur_range)\n+\t\t\tfinal_range = NULL;\n+\t\telse\n+\t\t\tprev_range->next = NULL;\n+\t}\n+\n+\tif (final_range) {\n+\t\tassert(parent);\n+\t\tassert(final_range->spec);\n+\t\tadd_line_range(rev, parent, final_range);\n+\t}\n+\n+\t/* and the ranges of current commit is updated */\n+\tcommit->object.flags &= ~RANGE_UPDATE;\n+\tif (diff)\n+\t\tcommit->object.flags |= NEED_PRINT;\n+\n+\tif (tree1)\n+\t\tfree(tree1);\n+\tif (tree2)\n+\t\tfree(tree2);\n+}\n+\n+static void diff_update_parent_range(struct rev_info *rev,\n+\t\tstruct commit *commit)\n+{\n+\tstruct diff_line_range *r = lookup_line_range(rev, commit);\n+\tstruct commit_list *parents = commit->parents;\n+\tstruct commit *c = NULL;\n+\tif (parents) {\n+\t\tassert(!parents->next);\n+\t\tc = parents->item;\n+\t}\n+\n+\tassign_range_to_parent(rev, commit, c, r, &rev->diffopt, 1);\n+}\n+\n+static void assign_parents_range(struct rev_info *rev, struct commit *commit)\n+{\n+\tstruct commit_list *parents = commit->parents;\n+\tstruct diff_line_range *r = lookup_line_range(rev, commit);\n+\tstruct diff_line_range *evil = NULL, *range = NULL;\n+\tint nontrivial = 0;\n+\n+\t/*\n+\t * If we are in linear history, update range and flush the patch if\n+\t * necessary\n+\t */\n+\tif (!parents || !parents->next)\n+\t\treturn diff_update_parent_range(rev, commit);\n+\n+\t/*\n+\t * Loop on the parents and assign the ranges to different\n+\t * parents, if there is any range left, this commit must\n+\t * be an evil merge.\n+\t */\n+\tevil = diff_line_range_clone_deeply(r);\n+\tparents = commit->parents;\n+\twhile (parents) {\n+\t\tstruct commit *p = parents->item;\n+\t\tassign_range_to_parent(rev, commit, p, r, &rev->diffopt, 1);\n+\t\tassign_range_to_parent(rev, commit, p, evil, &rev->diffopt, 0);\n+\t\tparents = parents->next;\n+\t}\n+\n+\t/*\n+\t * yes, this must be an evil merge.\n+\t */\n+\trange = evil;\n+\twhile (range) {\n+\t\tif (range->nr) {\n+\t\t\tcommit->object.flags |= NEED_PRINT | EVIL_MERGE;\n+\t\t\tnontrivial = 1;\n+\t\t}\n+\t\trange = range->next;\n+\t}\n+\n+\tif (nontrivial)\n+\t\tadd_decoration(&rev->nontrivial_merge, &commit->object, evil);\n+\telse\n+\t\tfree_diff_line_ranges(evil);\n+}\n+\n+struct line_chunk {\n+\tint lone, ltwo;\n+\tconst char *one, *two;\n+\tconst char *one_end, *two_end;\n+\tstruct diff_line_range *range;\n+};\n+\n+static void flush_lines(struct diff_options *opt, const char **ptr, const char *end,\n+\t\tint slno, int elno, int *lno, const char *color, const char heading)\n+{\n+\tconst char *p = *ptr;\n+\tstruct strbuf buf = STRBUF_INIT;\n+\tconst char *reset;\n+\n+\tif (*color)\n+\t\treset = diff_get_color_opt(opt, DIFF_RESET);\n+\telse\n+\t\treset = \"\";\n+\n+\tstrbuf_addf(&buf, \"%s%c\", color, heading);\n+\twhile (*ptr < end && *lno < slno) {\n+\t\tif (**ptr == '\\n') {\n+\t\t\t(*lno)++;\n+\t\t\tif (*lno == slno) {\n+\t\t\t\t(*ptr)++;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n+\t\t(*ptr)++;\n+\t}\n+\tassert(*ptr <= end);\n+\tp = *ptr;\n+\n+\twhile (*ptr < end && *lno <= elno) {\n+\t\tif (**ptr == '\\n') {\n+\t\t\tfprintf(opt->file, \"%s\", buf.buf);\n+\t\t\tif (*ptr - p)\n+\t\t\t\tfwrite(p, *ptr - p, 1, opt->file);\n+\t\t\tfprintf(opt->file, \"%s\\n\", reset);\n+\t\t\tp = *ptr + 1;\n+\t\t\t(*lno)++;\n+\t\t}\n+\t\t(*ptr)++;\n+\t}\n+\tif (*lno <= elno) {\n+\t\tfprintf(opt->file, \"%s\", buf.buf);\n+\t\tif (*ptr - p)\n+\t\t\tfwrite(p, *ptr - p, 1, opt->file);\n+\t\tfprintf(opt->file, \"%s\\n\", reset);\n+\t}\n+\tstrbuf_release(&buf);\n+}\n+\n+static void diff_flush_range(struct diff_options *opt, struct line_chunk *chunk,\n+\t\tstruct line_range *range)\n+{\n+\tstruct print_pair *pair = &range->pair;\n+\tconst char *old = diff_get_color_opt(opt, DIFF_FILE_OLD);\n+\tconst char *new = diff_get_color_opt(opt, DIFF_FILE_NEW);\n+\tint i, cur = range->start;\n+\n+\tfor (i = 0; i < pair->nr; i++) {\n+\t\tstruct print_range *pr = pair->ranges + i;\n+\t\tif (cur < pr->start)\n+\t\t\tflush_lines(opt, &chunk->two, chunk->two_end,\n+\t\t\t\tcur, pr->start - 1, &chunk->ltwo, \"\", ' ');\n+\n+\t\tif (!pr->line_added)\n+\t\t\tflush_lines(opt, &chunk->one, chunk->one_end,\n+\t\t\t\tpr->pstart, pr->pend, &chunk->lone, old, '-');\n+\t\tflush_lines(opt, &chunk->two, chunk->two_end,\n+\t\t\tpr->start, pr->end, &chunk->ltwo, new, '+');\n+\n+\t\tcur = pr->end + 1;\n+\t}\n+\n+\tif (cur <= range->end) {\n+\t\tflush_lines(opt, &chunk->two, chunk->two_end,\n+\t\t\tcur, range->end, &chunk->ltwo, \"\", ' ');\n+\t}\n+}\n+\n+static void diff_flush_chunks(struct diff_options *opt, struct line_chunk *chunk)\n+{\n+\tstruct diff_line_range *range = chunk->range;\n+\tconst char *set = diff_get_color_opt(opt, DIFF_FRAGINFO);\n+\tconst char *reset = diff_get_color_opt(opt, DIFF_RESET);\n+\tint i;\n+\n+\tfor (i = 0; i < range->nr; i++) {\n+\t\tstruct line_range *r = range->ranges + i;\n+\t\tlong lenp = r->pend - r->pstart + 1, pstart = r->pstart;\n+\t\tlong len = r->end - r->start + 1;\n+\t\tif (pstart == 0)\n+\t\t\tlenp = 0;\n+\n+\t\tfprintf(opt->file, \"%s@@ -%ld,%ld +%ld,%ld @@%s\\n\",\n+\t\t\tset, pstart, lenp, r->start, len, reset);\n+\n+\t\tdiff_flush_range(opt, chunk, r);\n+\t}\n+}\n+\n+static void diff_flush_filepair(struct rev_info *rev, struct diff_line_range *range)\n+{\n+\tstruct diff_options *opt = &rev->diffopt;\n+\tstruct diff_filespec *one = range->prev, *two = range->spec;\n+\tstruct diff_filepair p = {one, two, range->status, 0};\n+\tstruct strbuf header = STRBUF_INIT, meta = STRBUF_INIT;\n+\tconst char *a_prefix, *b_prefix;\n+\tconst char *name_a, *name_b, *a_one, *b_two;\n+\tconst char *lbl[2];\n+\tconst char *set = diff_get_color_opt(opt, DIFF_METAINFO);\n+\tconst char *reset = diff_get_color_opt(opt, DIFF_RESET);\n+\tstruct line_chunk chunk;\n+\tint must_show_header;\n+\n+\t/*\n+\t * the ranges that touch no different file, in this case\n+\t * the line number will not change, and of course we have\n+\t * no sensible rang->pair since there is no diff run.\n+\t */\n+\tif (!one)\n+\t\treturn;\n+\n+\tif (range->status == DIFF_STATUS_DELETED)\n+\t\tdie(\"We are following an nonexistent file, interesting!\");\n+\n+\tname_a  = one->path;\n+\tname_b = two->path;\n+\tfill_metainfo(&meta, name_a, name_b, one, two, opt, &p, &must_show_header,\n+\t\t\tDIFF_OPT_TST(opt, COLOR_DIFF));\n+\n+\tdiff_set_mnemonic_prefix(opt, \"a/\", \"b/\");\n+\tif (DIFF_OPT_TST(opt, REVERSE_DIFF)) {\n+\t\ta_prefix = opt->b_prefix;\n+\t\tb_prefix = opt->a_prefix;\n+\t} else {\n+\t\ta_prefix = opt->a_prefix;\n+\t\tb_prefix = opt->b_prefix;\n+\t}\n+\n+\tname_a = DIFF_FILE_VALID(one) ? name_a : name_b;\n+\tname_b = DIFF_FILE_VALID(two) ? name_b : name_a;\n+\n+\ta_one = quote_two(a_prefix, name_a + (*name_a == '/'));\n+\tb_two = quote_two(b_prefix, name_b + (*name_b == '/'));\n+\tlbl[0] = DIFF_FILE_VALID(one) ? a_one : \"/dev/null\";\n+\tlbl[1] = DIFF_FILE_VALID(two) ? b_two : \"/dev/null\";\n+\tstrbuf_addf(&header, \"%sdiff --git %s %s%s\\n\", set, a_one, b_two, reset);\n+\tif (lbl[0][0] == '/') {\n+\t\tstrbuf_addf(&header, \"%snew file mode %06o%s\\n\", set, two->mode, reset);\n+\t} else if (lbl[1][0] == '/') {\n+\t\tstrbuf_addf(&header, \"%sdeleted file mode %06o%s\\n\", set, one->mode, reset);\n+\t} else if (one->mode != two->mode) {\n+\t\t\tstrbuf_addf(&header, \"%sold mode %06o%s\\n\", set, one->mode, reset);\n+\t\t\tstrbuf_addf(&header, \"%snew mode %06o%s\\n\", set, two->mode, reset);\n+\t}\n+\n+\tfprintf(opt->file, \"%s%s\", header.buf, meta.buf);\n+\tstrbuf_release(&meta);\n+\tstrbuf_release(&header);\n+\tfprintf(opt->file, \"%s--- %s%s\\n\", set, lbl[0], reset);\n+\tfprintf(opt->file, \"%s+++ %s%s\\n\", set, lbl[1], reset);\n+\tfree((void *)a_one);\n+\tfree((void *)b_two);\n+\n+\tchunk.one = one->data;\n+\tchunk.one_end = (const char *)one->data + one->size;\n+\tchunk.lone = 1;\n+\tchunk.two = two->data;\n+\tchunk.two_end = (const char *)two->data + two->size;\n+\tchunk.ltwo = 1;\n+\tchunk.range = range;\n+\tdiff_flush_chunks(&rev->diffopt, &chunk);\n+}\n+\n+static void flush_nontrivial_merge(struct rev_info *rev,\n+\t\tstruct diff_line_range *range)\n+{\n+\tstruct diff_options *opt = &rev->diffopt;\n+\tconst char *reset = diff_get_color_opt(opt, DIFF_RESET);\n+\tconst char *frag = diff_get_color_opt(opt, DIFF_FRAGINFO);\n+\tconst char *meta = diff_get_color_opt(opt, DIFF_METAINFO);\n+\tconst char *new = diff_get_color_opt(opt, DIFF_FILE_NEW);\n+\n+\tfprintf(opt->file, \"%s%s%s\\n\", meta, \"nontrivial merge found\", reset);\n+\n+\twhile (range) {\n+\t\tif (range->nr) {\n+\t\t\tint lno = 1;\n+\t\t\tconst char *ptr = range->spec->data;\n+\t\t\tconst char *end = range->spec->data + range->spec->size;\n+\t\t\tint i = 0;\n+\t\t\tfprintf(opt->file, \"%s%s%s\\n\\n\", meta, range->spec->path, reset);\n+\t\t\tfor (; i < range->nr; i++) {\n+\t\t\t\tstruct line_range *r = range->ranges + i;\n+\t\t\t\tfprintf(opt->file, \"%s@@ %ld,%ld @@%s\\n\", frag, r->start,\n+\t\t\t\t\tr->end - r->start + 1, reset);\n+\t\t\t\tflush_lines(opt, &ptr, end, r->start, r->end,\n+\t\t\t\t\t&lno, new, ' ');\n+\t\t\t}\n+\t\t\tfprintf(opt->file, \"\\n\");\n+\t\t}\n+\t\trange = range->next;\n+\t}\n+}\n+\n+static void line_log_flush(struct rev_info *rev, struct commit *c)\n+{\n+\tstruct diff_line_range *range = lookup_line_range(rev, c);\n+\tstruct diff_line_range *nontrivial = lookup_decoration(&rev->nontrivial_merge, &c->object);\n+\tstruct log_info log;\n+\n+\tif (!range)\n+\t\treturn;\n+\n+\tlog.commit = c;\n+\tlog.parent = NULL;\n+\trev->loginfo = &log;\n+\tshow_log(rev);\n+\trev->loginfo = NULL;\n+\t/*\n+\t * Add a new line after each commit message, of course we should\n+\t * add --graph alignment later when the patches comes to master.\n+\t */\n+\tfprintf(rev->diffopt.file, \"\\n\");\n+\n+\tif (c->object.flags & EVIL_MERGE)\n+\t\treturn flush_nontrivial_merge(rev, nontrivial);\n+\n+\twhile (range) {\n+\t\tif (range->diff)\n+\t\t\tdiff_flush_filepair(rev, range);\n+\t\trange = range->next;\n+\t}\n+}\n+\n+int line_log_walk(struct rev_info *rev)\n+{\n+\tstruct commit *commit;\n+\tstruct commit_list *list = NULL;\n+\tstruct diff_line_range *r = NULL;\n+\n+\tif (prepare_revision_walk(rev))\n+\t\tdie(\"revision walk prepare failed\");\n+\n+\t/*\n+\t * Note that -L automatically turns on --topo-order, so\n+\t * rev->commits already holds all commits in the range.  The\n+\t * first commit is our starting point.\n+\t */\n+\tlist = rev->commits;\n+\tif (list) {\n+\t\tlist->item->object.flags |= RANGE_UPDATE;\n+\t\tlist = list->next;\n+\t}\n+\t/* Clear the flags */\n+\twhile (list) {\n+\t\tlist->item->object.flags &= ~(RANGE_UPDATE | EVIL_MERGE | NEED_PRINT);\n+\t\tlist = list->next;\n+\t}\n+\n+\tlist = rev->commits;\n+\twhile (list) {\n+\t\tstruct commit_list *need_free = list;\n+\t\tcommit = list->item;\n+\n+\t\tif (commit->object.flags & RANGE_UPDATE)\n+\t\t\tassign_parents_range(rev, commit);\n+\n+\t\tif (commit->object.flags & NEED_PRINT)\n+\t\t\tline_log_flush(rev, commit);\n+\n+\t\tclear_commit_line_range(rev, commit);\n+\n+\t\tr = lookup_decoration(&rev->nontrivial_merge, &commit->object);\n+\t\tif (r) {\n+\t\t\tfree_diff_line_ranges(r);\n+\t\t\tadd_decoration(&rev->nontrivial_merge, &commit->object,\n+\t\t\t\t       NULL);\n+\t\t}\n+\n+\t\tlist = list->next;\n+\t\tfree(need_free);\n+\t}\n+\n+\treturn 0;\n+}\ndiff --git a/line.h b/line.h\nindex 5878c94..5f2931a 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,51 @@ 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+struct diff_line_range;\n+struct diff_options;\n+\n+struct line_range;\n+\n+struct diff_line_range {\n+\tstruct diff_filespec *prev;\n+\tstruct diff_filespec *spec;\n+\tchar status;\n+\tint alloc;\n+\tint nr;\n+\tstruct line_range *ranges;\n+\tunsigned int\ttouched:1,\n+\t\t\tdiff:1;\n+\tstruct diff_line_range *next;\n+};\n+\n+static inline void diff_line_range_init(struct diff_line_range *r)\n+{\n+\tr->prev = r->spec = NULL;\n+\tr->status = '\\0';\n+\tr->alloc = r->nr = 0;\n+\tr->ranges = NULL;\n+\tr->next = NULL;\n+\tr->touched = 0;\n+\tr->diff = 0;\n+}\n+\n+extern void diff_line_range_append(struct diff_line_range *r, const char *arg);\n+\n+extern void line_log_init(struct rev_info *rev, struct diff_line_range *r);\n+\n+extern int line_log_walk(struct rev_info *rev);\n+\n #endif /* LINE_H */\ndiff --git a/revision.c b/revision.c\nindex 6465c45..369ec56 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1662,6 +1662,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 \ndiff --git a/revision.h b/revision.h\nindex 8897368..585b15f 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -14,7 +14,10 @@\n #define CHILD_SHOWN\t(1u<<6)\n #define ADDED\t\t(1u<<7)\t/* Parents already parsed and added? */\n #define SYMMETRIC_LEFT\t(1u<<8)\n-#define ALL_REV_FLAGS\t((1u<<9)-1)\n+#define RANGE_UPDATE\t(1u<<9) /* for line level traverse */\n+#define NEED_PRINT\t(1u<<10)\n+#define EVIL_MERGE\t(1u<<11)\n+#define ALL_REV_FLAGS\t((1u<<12)-1)\n \n #define DECORATE_SHORT_REFS\t1\n #define DECORATE_FULL_REFS\t2\n@@ -68,7 +71,8 @@ struct rev_info {\n \t\t\tcherry_pick: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@@ -137,6 +141,9 @@ struct rev_info {\n \t/* commit counts */\n \tint count_left;\n \tint count_right;\n+\t/* line level range that we are chasing */\n+\tstruct decoration line_range;\n+\tstruct decoration nontrivial_merge;\n };\n \n #define REV_TREE_SAME\t\t0\ndiff --git a/t/t4301-log-line-single-history.sh b/t/t4301-log-line-single-history.sh\nnew file mode 100755\nindex 0000000..59e9654\n--- /dev/null\n+++ b/t/t4301-log-line-single-history.sh\n@@ -0,0 +1,685 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2010 Bo Yang\n+#\n+\n+test_description='Test git log -L with single line of history'\n+\n+. ./test-lib.sh\n+. \"$TEST_DIRECTORY\"/diff-lib.sh\n+\n+cat >path0 <<\\EOF\n+void func()\n+{\n+\tint a = 0;\n+\tint b = 1;\n+\tint c;\n+\tc = a + b;\n+}\n+EOF\n+\n+cat >path1 <<\\EOF\n+void output()\n+{\n+\tprintf(\"hello world\");\n+}\n+EOF\n+\n+test_expect_success 'add path0/path1 and commit.' '\n+\tgit add path0 path1 &&\n+\tgit commit -m \"Base commit\"\n+'\n+\n+cat >path0 <<\\EOF\n+void func()\n+{\n+\tint a = 10;\n+\tint b = 11;\n+\tint c;\n+\tc = a + b;\n+}\n+EOF\n+\n+cat >path1 <<\\EOF\n+void output()\n+{\n+\tconst char *str = \"hello world!\";\n+\tprintf(\"%s\", str);\n+}\n+EOF\n+\n+test_expect_success 'Change the 2,3 lines of path0 and path1.' '\n+\tgit add path0 path1 &&\n+\tgit commit -m \"Change 2,3 lines of path0 and path1\"\n+'\n+\n+cat >path0 <<\\EOF\n+void func()\n+{\n+\tint a = 10;\n+\tint b = 11;\n+\tint c;\n+\tc = 10 * (a + b);\n+}\n+EOF\n+\n+test_expect_success 'Change the 5th line of path0.' '\n+\tgit add path0 &&\n+\tgit commit -m \"Change the 5th line of path0\"\n+'\n+\n+cat >path0 <<\\EOF\n+void func()\n+{\n+\tint a = 10;\n+\tint b = 11;\n+\tprintf(\"%d\", a - b);\n+}\n+EOF\n+\n+test_expect_success 'Final change of path0.' '\n+\tgit add path0 &&\n+\tgit commit -m \"Final change of path0\"\n+'\n+\n+sed 's/Q/ /g' >expected-path0 <<\\EOF\n+Final change of path0\n+\n+diff --git a/path0 b/path0\n+index ccdf243..ccf8bcf 100644\n+--- a/path0\n++++ b/path0\n+@@ -1,7 +1,6 @@\n+ void func()\n+ {\n+Q\tint a = 10;\n+Q\tint b = 11;\n+-\tint c;\n+-\tc = 10 * (a + b);\n++\tprintf(\"%d\", a - b);\n+ }\n+\n+Change the 5th line of path0\n+\n+diff --git a/path0 b/path0\n+index b0eb888..ccdf243 100644\n+--- a/path0\n++++ b/path0\n+@@ -1,7 +1,7 @@\n+ void func()\n+ {\n+Q\tint a = 10;\n+Q\tint b = 11;\n+Q\tint c;\n+-\tc = a + b;\n++\tc = 10 * (a + b);\n+ }\n+\n+Change 2,3 lines of path0 and path1\n+\n+diff --git a/path0 b/path0\n+index fb33939..b0eb888 100644\n+--- a/path0\n++++ b/path0\n+@@ -1,7 +1,7 @@\n+ void func()\n+ {\n+-\tint a = 0;\n+-\tint b = 1;\n++\tint a = 10;\n++\tint b = 11;\n+Q\tint c;\n+Q\tc = a + b;\n+ }\n+\n+Base commit\n+\n+diff --git a/path0 b/path0\n+new file mode 100644\n+index 0000000..fb33939\n+--- /dev/null\n++++ b/path0\n+@@ -0,0 +1,7 @@\n++void func()\n++{\n++\tint a = 0;\n++\tint b = 1;\n++\tint c;\n++\tc = a + b;\n++}\n+EOF\n+\n+cat >expected-path1 <<\\EOF\n+Change 2,3 lines of path0 and path1\n+\n+diff --git a/path1 b/path1\n+index 52be2a5..cc54b12 100644\n+--- a/path1\n++++ b/path1\n+@@ -1,4 +1,5 @@\n+ void output()\n+ {\n+-\tprintf(\"hello world\");\n++\tconst char *str = \"hello world!\";\n++\tprintf(\"%s\", str);\n+ }\n+\n+Base commit\n+\n+diff --git a/path1 b/path1\n+new file mode 100644\n+index 0000000..52be2a5\n+--- /dev/null\n++++ b/path1\n+@@ -0,0 +1,4 @@\n++void output()\n++{\n++\tprintf(\"hello world\");\n++}\n+EOF\n+\n+sed 's/Q/ /g' >expected-pathall <<\\EOF\n+Final change of path0\n+\n+diff --git a/path0 b/path0\n+index ccdf243..ccf8bcf 100644\n+--- a/path0\n++++ b/path0\n+@@ -1,7 +1,6 @@\n+ void func()\n+ {\n+Q\tint a = 10;\n+Q\tint b = 11;\n+-\tint c;\n+-\tc = 10 * (a + b);\n++\tprintf(\"%d\", a - b);\n+ }\n+\n+Change the 5th line of path0\n+\n+diff --git a/path0 b/path0\n+index b0eb888..ccdf243 100644\n+--- a/path0\n++++ b/path0\n+@@ -1,7 +1,7 @@\n+ void func()\n+ {\n+Q\tint a = 10;\n+Q\tint b = 11;\n+Q\tint c;\n+-\tc = a + b;\n++\tc = 10 * (a + b);\n+ }\n+\n+Change 2,3 lines of path0 and path1\n+\n+diff --git a/path0 b/path0\n+index fb33939..b0eb888 100644\n+--- a/path0\n++++ b/path0\n+@@ -1,7 +1,7 @@\n+ void func()\n+ {\n+-\tint a = 0;\n+-\tint b = 1;\n++\tint a = 10;\n++\tint b = 11;\n+Q\tint c;\n+Q\tc = a + b;\n+ }\n+diff --git a/path1 b/path1\n+index 52be2a5..cc54b12 100644\n+--- a/path1\n++++ b/path1\n+@@ -1,4 +1,5 @@\n+ void output()\n+ {\n+-\tprintf(\"hello world\");\n++\tconst char *str = \"hello world!\";\n++\tprintf(\"%s\", str);\n+ }\n+\n+Base commit\n+\n+diff --git a/path0 b/path0\n+new file mode 100644\n+index 0000000..fb33939\n+--- /dev/null\n++++ b/path0\n+@@ -0,0 +1,7 @@\n++void func()\n++{\n++\tint a = 0;\n++\tint b = 1;\n++\tint c;\n++\tc = a + b;\n++}\n+diff --git a/path1 b/path1\n+new file mode 100644\n+index 0000000..52be2a5\n+--- /dev/null\n++++ b/path1\n+@@ -0,0 +1,4 @@\n++void output()\n++{\n++\tprintf(\"hello world\");\n++}\n+EOF\n+\n+cat >expected-linenum <<\\EOF\n+Change 2,3 lines of path0 and path1\n+\n+diff --git a/path0 b/path0\n+index fb33939..b0eb888 100644\n+--- a/path0\n++++ b/path0\n+@@ -2,3 +2,3 @@\n+ {\n+-\tint a = 0;\n+-\tint b = 1;\n++\tint a = 10;\n++\tint b = 11;\n+\n+Base commit\n+\n+diff --git a/path0 b/path0\n+new file mode 100644\n+index 0000000..fb33939\n+--- /dev/null\n++++ b/path0\n+@@ -0,0 +2,3 @@\n++{\n++\tint a = 0;\n++\tint b = 1;\n+EOF\n+\n+sed 's/Q/ /g' >expected-always <<\\EOF\n+Final change of path0\n+\n+diff --git a/path0 b/path0\n+index ccdf243..ccf8bcf 100644\n+--- a/path0\n++++ b/path0\n+@@ -2,3 +2,3 @@\n+ {\n+Q\tint a = 10;\n+Q\tint b = 11;\n+\n+Change the 5th line of path0\n+\n+diff --git a/path0 b/path0\n+index b0eb888..ccdf243 100644\n+--- a/path0\n++++ b/path0\n+@@ -2,3 +2,3 @@\n+ {\n+Q\tint a = 10;\n+Q\tint b = 11;\n+\n+Change 2,3 lines of path0 and path1\n+\n+diff --git a/path0 b/path0\n+index fb33939..b0eb888 100644\n+--- a/path0\n++++ b/path0\n+@@ -2,3 +2,3 @@\n+ {\n+-\tint a = 0;\n+-\tint b = 1;\n++\tint a = 10;\n++\tint b = 11;\n+\n+Base commit\n+\n+diff --git a/path0 b/path0\n+new file mode 100644\n+index 0000000..fb33939\n+--- /dev/null\n++++ b/path0\n+@@ -0,0 +2,3 @@\n++{\n++\tint a = 0;\n++\tint b = 1;\n+EOF\n+\n+test_expect_success 'Show the line level log of path0' '\n+\tgit log --pretty=format:%s%n%b -L /func/,/^}/:path0 > current-path0\n+'\n+\n+test_expect_success 'validate the path0 output.' '\n+\ttest_cmp current-path0 expected-path0\n+'\n+\n+test_expect_success 'Show the line level log of path1' '\n+\tgit log --pretty=format:%s%n%b -L /output/,/^}/:path1 > current-path1\n+'\n+\n+test_expect_success 'validate the path1 output.' '\n+\ttest_cmp current-path1 expected-path1\n+'\n+\n+test_expect_success 'Show the line level log of two files' '\n+\tgit log --pretty=format:%s%n%b -L /func/,/^}/:path0 -L /output/,/^}/:path1 > current-pathall\n+'\n+\n+test_expect_success 'validate the all path output.' '\n+\ttest_cmp current-pathall expected-pathall\n+'\n+\n+test_expect_success 'Test the line number argument' '\n+\tgit log --pretty=format:%s%n%b -L 2,4:path0 > current-linenum\n+'\n+\n+test_expect_success 'validate the line number output.' '\n+\ttest_cmp current-linenum expected-linenum\n+'\n+test_expect_success 'Test the --full-line-diff option' '\n+\tgit log --pretty=format:%s%n%b --full-line-diff -L 2,4:path0 > current-always\n+'\n+\n+test_expect_success 'validate the --full-line-diff output.' '\n+    test_cmp current-always expected-always\n+'\n+\n+# Rerun all log with graph\n+test_expect_success 'Show the line level log of path0 with --graph' '\n+\tgit log --pretty=format:%s%n%b --graph -L /func/,/^}/:path0 > current-path0-graph\n+'\n+\n+test_expect_success 'Show the line level log of path1 with --graph' '\n+\tgit log --pretty=format:%s%n%b --graph -L /output/,/^}/:path1 > current-path1-graph\n+'\n+\n+test_expect_success 'Show the line level log of two files with --graph' '\n+\tgit log --pretty=format:%s%n%b --graph -L /func/,/^}/:path0 -L /output/,/^}/:path1 > current-pathall-graph\n+'\n+\n+test_expect_success 'Test the line number argument with --graph' '\n+\tgit log --pretty=format:%s%n%b --graph -L 2,4:path0 > current-linenum-graph\n+'\n+\n+test_expect_success 'Test the --full-line-diff option with --graph option' '\n+\tgit log --pretty=format:%s%n%b --full-line-diff --graph -L 2,4:path0 > current-always-graph\n+'\n+\n+sed -e 's/Q/ /g' -e 's/#$//' > expected-path0-graph <<\\EOF\n+* Final change of path0\n+| #\n+| diff --git a/path0 b/path0\n+| index ccdf243..ccf8bcf 100644\n+| --- a/path0\n+| +++ b/path0\n+| @@ -1,7 +1,6 @@\n+|  void func()\n+|  {\n+|QQ\tint a = 10;\n+|QQ\tint b = 11;\n+| -\tint c;\n+| -\tc = 10 * (a + b);\n+| +\tprintf(\"%d\", a - b);\n+|  }\n+|  #\n+* Change the 5th line of path0\n+| #\n+| diff --git a/path0 b/path0\n+| index b0eb888..ccdf243 100644\n+| --- a/path0\n+| +++ b/path0\n+| @@ -1,7 +1,7 @@\n+|  void func()\n+|  {\n+|QQ\tint a = 10;\n+|QQ\tint b = 11;\n+|QQ\tint c;\n+| -\tc = a + b;\n+| +\tc = 10 * (a + b);\n+|  }\n+|  #\n+* Change 2,3 lines of path0 and path1\n+| #\n+| diff --git a/path0 b/path0\n+| index fb33939..b0eb888 100644\n+| --- a/path0\n+| +++ b/path0\n+| @@ -1,7 +1,7 @@\n+|  void func()\n+|  {\n+| -\tint a = 0;\n+| -\tint b = 1;\n+| +\tint a = 10;\n+| +\tint b = 11;\n+|QQ\tint c;\n+|QQ\tc = a + b;\n+|  }\n+|  #\n+* Base commit\n+  #\n+  diff --git a/path0 b/path0\n+  new file mode 100644\n+  index 0000000..fb33939\n+  --- /dev/null\n+  +++ b/path0\n+  @@ -0,0 +1,7 @@\n+  +void func()\n+  +{\n+  +\tint a = 0;\n+  +\tint b = 1;\n+  +\tint c;\n+  +\tc = a + b;\n+  +}\n+EOF\n+\n+sed 's/#$//' > expected-path1-graph <<\\EOF\n+* Change 2,3 lines of path0 and path1\n+| #\n+| diff --git a/path1 b/path1\n+| index 52be2a5..cc54b12 100644\n+| --- a/path1\n+| +++ b/path1\n+| @@ -1,4 +1,5 @@\n+|  void output()\n+|  {\n+| -\tprintf(\"hello world\");\n+| +\tconst char *str = \"hello world!\";\n+| +\tprintf(\"%s\", str);\n+|  }\n+|  #\n+* Base commit\n+  #\n+  diff --git a/path1 b/path1\n+  new file mode 100644\n+  index 0000000..52be2a5\n+  --- /dev/null\n+  +++ b/path1\n+  @@ -0,0 +1,4 @@\n+  +void output()\n+  +{\n+  +\tprintf(\"hello world\");\n+  +}\n+EOF\n+\n+sed -e 's/Q/ /g' -e 's/#$//' > expected-pathall-graph <<\\EOF\n+* Final change of path0\n+| #\n+| diff --git a/path0 b/path0\n+| index ccdf243..ccf8bcf 100644\n+| --- a/path0\n+| +++ b/path0\n+| @@ -1,7 +1,6 @@\n+|  void func()\n+|  {\n+|QQ\tint a = 10;\n+|QQ\tint b = 11;\n+| -\tint c;\n+| -\tc = 10 * (a + b);\n+| +\tprintf(\"%d\", a - b);\n+|  }\n+|  #\n+* Change the 5th line of path0\n+| #\n+| diff --git a/path0 b/path0\n+| index b0eb888..ccdf243 100644\n+| --- a/path0\n+| +++ b/path0\n+| @@ -1,7 +1,7 @@\n+|  void func()\n+|  {\n+|QQ\tint a = 10;\n+|QQ\tint b = 11;\n+|QQ\tint c;\n+| -\tc = a + b;\n+| +\tc = 10 * (a + b);\n+|  }\n+|  #\n+* Change 2,3 lines of path0 and path1\n+| #\n+| diff --git a/path0 b/path0\n+| index fb33939..b0eb888 100644\n+| --- a/path0\n+| +++ b/path0\n+| @@ -1,7 +1,7 @@\n+|  void func()\n+|  {\n+| -\tint a = 0;\n+| -\tint b = 1;\n+| +\tint a = 10;\n+| +\tint b = 11;\n+|QQ\tint c;\n+|QQ\tc = a + b;\n+|  }\n+| diff --git a/path1 b/path1\n+| index 52be2a5..cc54b12 100644\n+| --- a/path1\n+| +++ b/path1\n+| @@ -1,4 +1,5 @@\n+|  void output()\n+|  {\n+| -\tprintf(\"hello world\");\n+| +\tconst char *str = \"hello world!\";\n+| +\tprintf(\"%s\", str);\n+|  }\n+|  #\n+* Base commit\n+  #\n+  diff --git a/path0 b/path0\n+  new file mode 100644\n+  index 0000000..fb33939\n+  --- /dev/null\n+  +++ b/path0\n+  @@ -0,0 +1,7 @@\n+  +void func()\n+  +{\n+  +\tint a = 0;\n+  +\tint b = 1;\n+  +\tint c;\n+  +\tc = a + b;\n+  +}\n+  diff --git a/path1 b/path1\n+  new file mode 100644\n+  index 0000000..52be2a5\n+  --- /dev/null\n+  +++ b/path1\n+  @@ -0,0 +1,4 @@\n+  +void output()\n+  +{\n+  +\tprintf(\"hello world\");\n+  +}\n+EOF\n+\n+sed 's/#$//' > expected-linenum-graph <<\\EOF\n+* Change 2,3 lines of path0 and path1\n+| #\n+| diff --git a/path0 b/path0\n+| index fb33939..b0eb888 100644\n+| --- a/path0\n+| +++ b/path0\n+| @@ -2,3 +2,3 @@\n+|  {\n+| -\tint a = 0;\n+| -\tint b = 1;\n+| +\tint a = 10;\n+| +\tint b = 11;\n+|  #\n+* Base commit\n+  #\n+  diff --git a/path0 b/path0\n+  new file mode 100644\n+  index 0000000..fb33939\n+  --- /dev/null\n+  +++ b/path0\n+  @@ -0,0 +2,3 @@\n+  +{\n+  +\tint a = 0;\n+  +\tint b = 1;\n+EOF\n+\n+sed -e 's/Q/ /g' -e 's/#$//' > expected-always-graph <<\\EOF\n+* Final change of path0\n+| #\n+| diff --git a/path0 b/path0\n+| index ccdf243..ccf8bcf 100644\n+| --- a/path0\n+| +++ b/path0\n+| @@ -2,3 +2,3 @@\n+|  {\n+|QQ\tint a = 10;\n+|QQ\tint b = 11;\n+|  #\n+* Change the 5th line of path0\n+| #\n+| diff --git a/path0 b/path0\n+| index b0eb888..ccdf243 100644\n+| --- a/path0\n+| +++ b/path0\n+| @@ -2,3 +2,3 @@\n+|  {\n+|QQ\tint a = 10;\n+|QQ\tint b = 11;\n+|  #\n+* Change 2,3 lines of path0 and path1\n+| #\n+| diff --git a/path0 b/path0\n+| index fb33939..b0eb888 100644\n+| --- a/path0\n+| +++ b/path0\n+| @@ -2,3 +2,3 @@\n+|  {\n+| -\tint a = 0;\n+| -\tint b = 1;\n+| +\tint a = 10;\n+| +\tint b = 11;\n+|  #\n+* Base commit\n+  #\n+  diff --git a/path0 b/path0\n+  new file mode 100644\n+  index 0000000..fb33939\n+  --- /dev/null\n+  +++ b/path0\n+  @@ -0,0 +2,3 @@\n+  +{\n+  +\tint a = 0;\n+  +\tint b = 1;\n+EOF\n+\n+test_expect_success 'validate the path0 output.' '\n+\ttest_cmp current-path0-graph expected-path0-graph\n+'\n+\n+test_expect_success 'validate the path1 output.' '\n+\ttest_cmp current-path1-graph expected-path1-graph\n+'\n+\n+test_expect_success 'validate the all path output.' '\n+\ttest_cmp current-pathall-graph expected-pathall-graph\n+'\n+\n+test_expect_success 'validate graph output' '\n+\ttest_cmp current-linenum-graph expected-linenum-graph\n+'\n+\n+test_expect_success 'validate --full-line-diff output' '\n+\ttest_cmp current-always-graph expected-always-graph\n+'\n+\n+test_done\n-- \n1.7.3.3.807.g6ee1f\n"},{"id":"158109","messageId":"f6128f23b20409bfee7e982a5d0780053e8d52bb.1292366984.git.trast@student.ethz.ch","threadId":"26071","inReplyTo":"cover.1292366984.git.trast@student.ethz.ch","subject":"[PATCH v6.1 5/8] log -L: support parent rewriting","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2010-12-14T22:54:12Z","receivedAt":"2010-12-14T22:54:12Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"From: Bo Yang <struggleyb.nku@gmail.com>\n\nWalking forward through history (i.e., topologically earliest\ncommits first), we filter the parent list of every commit as\nfollows. Consider a parent P:\n - If P touches any of the interesting line ranges, we keep it.\n - If P is a merge and it takes all the interesting line ranges\n   from one of its parents, P is rewritten to this parent, else\n   we keep P.\n - Otherwise, P is rewritten to its (only) parent P^.\n\nSigned-off-by: Bo Yang <struggleyb.nku@gmail.com>\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\n---\n line.c                            |  208 +++++++++++++++++++++++++++++++-----\n revision.c                        |    1 +\n revision.h                        |    5 +-\n t/t4302-log-line-merge-history.sh |  174 +++++++++++++++++++++++++++++++\n 4 files changed, 357 insertions(+), 31 deletions(-)\n create mode 100755 t/t4302-log-line-merge-history.sh\n\ndiff --git a/line.c b/line.c\nindex 1ffcaba..10870a5 100644\n--- a/line.c\n+++ b/line.c\n@@ -10,6 +10,7 @@\n #include \"xdiff-interface.h\"\n #include \"strbuf.h\"\n #include \"log-tree.h\"\n+#include \"graph.h\"\n #include \"line.h\"\n \n struct print_range {\n@@ -33,12 +34,6 @@ struct line_range {\n };\n \n /*\n- * Eek-a-global\n- */\n-\n-static int limited;\n-\n-/*\n  * These could be in line.h but we put them here so the functions can\n  * be static.\n  */\n@@ -596,14 +591,14 @@ static void add_line_range(struct rev_info *revs, struct commit *commit,\n {\n \tstruct diff_line_range *ret = NULL;\n \n-\tif (r) {\n-\t\tret = lookup_decoration(&revs->line_range, &commit->object);\n-\t\tif (ret)\n-\t\t\tdiff_line_range_merge(ret, r);\n-\t\telse\n-\t\t\tadd_decoration(&revs->line_range, &commit->object, r);\n+\tret = lookup_decoration(&revs->line_range, &commit->object);\n+\tif (ret && r)\n+\t\tdiff_line_range_merge(ret, r);\n+\telse\n+\t\tadd_decoration(&revs->line_range, &commit->object, r);\n+\n+\tif (r)\n \t\tcommit->object.flags |= RANGE_UPDATE;\n-\t}\n }\n \n static void clear_commit_line_range(struct rev_info *revs, struct commit *commit)\n@@ -687,6 +682,22 @@ void map_lines(long p_start, long p_end, long t_start, long t_end,\n \t\treturn;\n \t}\n \n+\tif (start == t_start) {\n+\t\t*o_start = p_start;\n+\t\t*o_end = p_start + (end - start);\n+\t\tif (*o_end > p_end)\n+\t\t\t*o_end = p_end;\n+\t\treturn;\n+\t}\n+\n+\tif (end == t_end) {\n+\t\t*o_start = p_end - (end - start);\n+\t\tif (*o_start < p_start)\n+\t\t\t*o_start = p_start;\n+\t\t*o_end = p_end;\n+\t\treturn;\n+\t}\n+\n \t/*\n \t * A heuristic for lines mapping:\n \t *\n@@ -920,7 +931,7 @@ static void load_tree_desc(struct tree_desc *desc, void **tree,\n  * to parents.\n  * map_range_cb and map_range are used to map line ranges to the parent.\n  */\n-static void assign_range_to_parent(struct rev_info *rev, struct commit *commit,\n+static int assign_range_to_parent(struct rev_info *rev, struct commit *commit,\n \t\tstruct commit *parent, struct diff_line_range *range,\n \t\tstruct diff_options *opt, int map)\n {\n@@ -1065,10 +1076,22 @@ static void assign_range_to_parent(struct rev_info *rev, struct commit *commit,\n \t\t\tprev_range->next = NULL;\n \t}\n \n+\tif (!map)\n+\t\tgoto out;\n+\n \tif (final_range) {\n \t\tassert(parent);\n \t\tassert(final_range->spec);\n \t\tadd_line_range(rev, parent, final_range);\n+\t} else {\n+\t\t/*\n+\t\t * If there is no new ranges assigned to the parent,\n+\t\t * we should mark it as a 'root' commit.\n+\t\t */\n+\t\tif (commit->parents && !commit->parents->next) {\n+\t\t\tfree(commit->parents);\n+\t\t\tcommit->parents = NULL;\n+\t\t}\n \t}\n \n \t/* and the ranges of current commit is updated */\n@@ -1076,10 +1099,13 @@ static void assign_range_to_parent(struct rev_info *rev, struct commit *commit,\n \tif (diff)\n \t\tcommit->object.flags |= NEED_PRINT;\n \n+out:\n \tif (tree1)\n \t\tfree(tree1);\n \tif (tree2)\n \t\tfree(tree2);\n+\n+\treturn diff;\n }\n \n static void diff_update_parent_range(struct rev_info *rev,\n@@ -1096,13 +1122,21 @@ static void diff_update_parent_range(struct rev_info *rev,\n \tassign_range_to_parent(rev, commit, c, r, &rev->diffopt, 1);\n }\n \n+struct commit_state {\n+\tstruct diff_line_range *range;\n+\tstruct object obj;\n+};\n+\n static void assign_parents_range(struct rev_info *rev, struct commit *commit)\n {\n \tstruct commit_list *parents = commit->parents;\n \tstruct diff_line_range *r = lookup_line_range(rev, commit);\n \tstruct diff_line_range *evil = NULL, *range = NULL;\n+\tstruct decoration parents_state;\n+\tstruct commit_state *state = NULL;\n \tint nontrivial = 0;\n \n+\tmemset(&parents_state, 0, sizeof(parents_state));\n \t/*\n \t * If we are in linear history, update range and flush the patch if\n \t * necessary\n@@ -1119,23 +1153,76 @@ static void assign_parents_range(struct rev_info *rev, struct commit *commit)\n \tparents = commit->parents;\n \twhile (parents) {\n \t\tstruct commit *p = parents->item;\n-\t\tassign_range_to_parent(rev, commit, p, r, &rev->diffopt, 1);\n+\t\tint diff = 0;\n+\t\tstruct diff_line_range *origin_range = lookup_line_range(rev, p);\n+\t\tif (origin_range)\n+\t\t\torigin_range = diff_line_range_clone_deeply(origin_range);\n+\n+\t\tstate = xmalloc(sizeof(*state));\n+\t\tstate->range = origin_range;\n+\t\tstate->obj = p->object;\n+\t\tadd_decoration(&parents_state, &p->object, state);\n+\t\tdiff = assign_range_to_parent(rev, commit, p, r, &rev->diffopt, 1);\n+\t\t/* Since all the ranges comes from this parent, we can ignore others */\n+\t\tif (diff == 0) {\n+\t\t\t/* restore the state of parents before this one */\n+\t\t\tparents = commit->parents;\n+\t\t\twhile (parents->item != p) {\n+\t\t\t\tstruct commit_list *list = parents;\n+\t\t\t\tparents = parents->next;\n+\t\t\t\tclear_commit_line_range(rev, list->item);\n+\t\t\t\tstate = lookup_decoration(&parents_state, &list->item->object);\n+\t\t\t\tadd_decoration(&parents_state, &list->item->object, NULL);\n+\t\t\t\tadd_line_range(rev, list->item, state->range);\n+\t\t\t\tlist->item->object = state->obj;\n+\t\t\t\tfree(state);\n+\t\t\t\tfree(list);\n+\t\t\t}\n+\n+\t\t\tcommit->parents = parents;\n+\t\t\tparents = parents->next;\n+\t\t\tcommit->parents->next = NULL;\n+\n+\t\t\t/* free the non-use commit_list */\n+\t\t\twhile (parents) {\n+\t\t\t\tstruct commit_list *list = parents;\n+\t\t\t\tparents = parents->next;\n+\t\t\t\tfree(list);\n+\t\t\t}\n+\t\t\tgoto out;\n+\t\t}\n+\t\t/* take the ranges from 'commit', try to detect nontrivial merge */\n \t\tassign_range_to_parent(rev, commit, p, evil, &rev->diffopt, 0);\n \t\tparents = parents->next;\n \t}\n \n+\tcommit->object.flags |= NONTRIVIAL_MERGE;\n \t/*\n \t * yes, this must be an evil merge.\n \t */\n \trange = evil;\n \twhile (range) {\n \t\tif (range->nr) {\n-\t\t\tcommit->object.flags |= NEED_PRINT | EVIL_MERGE;\n+\t\t\tcommit->object.flags |= EVIL_MERGE;\n \t\t\tnontrivial = 1;\n \t\t}\n \t\trange = range->next;\n \t}\n \n+out:\n+\t/* Never print out any diff for a merge commit */\n+\tcommit->object.flags &= ~NEED_PRINT;\n+\n+\tparents = commit->parents;\n+\twhile (parents) {\n+\t\tstate = lookup_decoration(&parents_state, &parents->item->object);\n+\t\tif (state) {\n+\t\t\tfree_diff_line_ranges(state->range);\n+\t\t\tfree(state);\n+\t\t}\n+\t\tparents = parents->next;\n+\t}\n+\n \tif (nontrivial)\n \t\tadd_decoration(&rev->nontrivial_merge, &commit->object, evil);\n \telse\n@@ -1327,16 +1414,36 @@ static void flush_nontrivial_merge(struct rev_info *rev,\n \tconst char *frag = diff_get_color_opt(opt, DIFF_FRAGINFO);\n \tconst char *meta = diff_get_color_opt(opt, DIFF_METAINFO);\n \tconst char *new = diff_get_color_opt(opt, DIFF_FILE_NEW);\n+\tchar *line_prefix = \"\";\n+\tstruct strbuf *msgbuf;\n+\tint evil = 0;\n+\tstruct diff_line_range *r = range;\n+\n+\tif (opt && opt->output_prefix) {\n+\t\tmsgbuf = opt->output_prefix(opt, opt->output_prefix_data);\n+\t\tline_prefix = msgbuf->buf;\n+\t}\n+\n+\twhile (r) {\n+\t\tif (r->nr)\n+\t\t\tevil = 1;\n+\t\tr = r->next;\n+\t}\n+\n+\tif (!evil)\n+\t\treturn;\n \n-\tfprintf(opt->file, \"%s%s%s\\n\", meta, \"nontrivial merge found\", reset);\n+\tfprintf(opt->file, \"%s%s%s%s\\n\", line_prefix, meta,\n+\t\t\"nontrivial merge found\", reset);\n \n \twhile (range) {\n \t\tif (range->nr) {\n \t\t\tint lno = 1;\n \t\t\tconst char *ptr = range->spec->data;\n-\t\t\tconst char *end = range->spec->data + range->spec->size;\n+\t\t\tconst char *end = (const char *)range->spec->data + range->spec->size;\n \t\t\tint i = 0;\n-\t\t\tfprintf(opt->file, \"%s%s%s\\n\\n\", meta, range->spec->path, reset);\n+\t\t\tfprintf(opt->file, \"%s%s%s%s\\n\", line_prefix,\n+\t\t\t\tmeta, range->spec->path, reset);\n \t\t\tfor (; i < range->nr; i++) {\n \t\t\t\tstruct line_range *r = range->ranges + i;\n \t\t\t\tfprintf(opt->file, \"%s@@ %ld,%ld @@%s\\n\", frag, r->start,\n@@ -1353,12 +1460,17 @@ static void flush_nontrivial_merge(struct rev_info *rev,\n static void line_log_flush(struct rev_info *rev, struct commit *c)\n {\n \tstruct diff_line_range *range = lookup_line_range(rev, c);\n-\tstruct diff_line_range *nontrivial = lookup_decoration(&rev->nontrivial_merge, &c->object);\n+\tstruct diff_line_range *nontrivial = lookup_decoration(&rev->nontrivial_merge,\n+\t\t\t\t\t\t\t&c->object);\n \tstruct log_info log;\n+\tstruct diff_options *opt = &rev->diffopt;\n \n-\tif (!range)\n+\tif (!range || !(c->object.flags & NONTRIVIAL_MERGE ||\n+\t\t\tc->object.flags & NEED_PRINT))\n \t\treturn;\n \n+\tif (rev->graph)\n+\t\tgraph_update(rev->graph, c);\n \tlog.commit = c;\n \tlog.parent = NULL;\n \trev->loginfo = &log;\n@@ -1370,13 +1482,42 @@ static void line_log_flush(struct rev_info *rev, struct commit *c)\n \t */\n \tfprintf(rev->diffopt.file, \"\\n\");\n \n-\tif (c->object.flags & EVIL_MERGE)\n-\t\treturn flush_nontrivial_merge(rev, nontrivial);\n+\tif (c->object.flags & NONTRIVIAL_MERGE)\n+\t\tflush_nontrivial_merge(rev, nontrivial);\n+\telse {\n+\t\twhile (range) {\n+\t\t\tif (range->diff)\n+\t\t\t\tdiff_flush_filepair(rev, range);\n+\t\t\trange = range->next;\n+\t\t}\n+\t}\n \n-\twhile (range) {\n-\t\tif (range->diff)\n-\t\t\tdiff_flush_filepair(rev, range);\n-\t\trange = range->next;\n+\twhile (rev->graph && !graph_is_commit_finished(rev->graph)) {\n+\t\tstruct strbuf sb;\n+\t\tstrbuf_init(&sb, 0);\n+\t\tgraph_next_line(rev->graph, &sb);\n+\t\tfputs(sb.buf, opt->file);\n+\t}\n+}\n+\n+static enum rewrite_result rewrite_one(struct rev_info *rev, struct commit **pp)\n+{\n+\tstruct diff_line_range *r = NULL;\n+\tstruct commit *p;\n+\twhile (1) {\n+\t\tp = *pp;\n+\t\tif (p->object.flags & RANGE_UPDATE)\n+\t\t\tassign_parents_range(rev, p);\n+\t\tif (p->object.flags & NEED_PRINT ||\n+\t\t    p->object.flags & NONTRIVIAL_MERGE)\n+\t\t\treturn rewrite_one_ok;\n+\t\tif (!p->parents)\n+\t\t\treturn rewrite_one_noparents;\n+\n+\t\tr = lookup_line_range(rev, p);\n+\t\tif (!r)\n+\t\t\treturn rewrite_one_noparents;\n+\t\t*pp = p->parents->item;\n \t}\n }\n \n@@ -1401,7 +1542,8 @@ int line_log_walk(struct rev_info *rev)\n \t}\n \t/* Clear the flags */\n \twhile (list) {\n-\t\tlist->item->object.flags &= ~(RANGE_UPDATE | EVIL_MERGE | NEED_PRINT);\n+\t\tlist->item->object.flags &= ~(RANGE_UPDATE | NONTRIVIAL_MERGE |\n+\t\t\t\t\t\tNEED_PRINT | EVIL_MERGE);\n \t\tlist = list->next;\n \t}\n \n@@ -1413,7 +1555,15 @@ int line_log_walk(struct rev_info *rev)\n \t\tif (commit->object.flags & RANGE_UPDATE)\n \t\t\tassign_parents_range(rev, commit);\n \n-\t\tif (commit->object.flags & NEED_PRINT)\n+\t\tif (commit->object.flags & NEED_PRINT ||\n+\t\t    commit->object.flags & NONTRIVIAL_MERGE) {\n+\t\t\tif (rewrite_parents(rev, commit, rewrite_one))\n+\t\t\t\tdie(\"Can't rewrite parent for commit %s\",\n+\t\t\t\t\tsha1_to_hex(commit->object.sha1));\n+\t\t}\n+\n+\t\tif (commit->object.flags & NEED_PRINT ||\n+\t\t    commit->object.flags & NONTRIVIAL_MERGE)\n \t\t\tline_log_flush(rev, commit);\n \n \t\tclear_commit_line_range(rev, commit);\ndiff --git a/revision.c b/revision.c\nindex 369ec56..fbebf2f 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 \ndiff --git a/revision.h b/revision.h\nindex 585b15f..6100904 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -16,8 +16,9 @@\n #define SYMMETRIC_LEFT\t(1u<<8)\n #define RANGE_UPDATE\t(1u<<9) /* for line level traverse */\n #define NEED_PRINT\t(1u<<10)\n-#define EVIL_MERGE\t(1u<<11)\n-#define ALL_REV_FLAGS\t((1u<<12)-1)\n+#define NONTRIVIAL_MERGE\t(1u<<11)\n+#define EVIL_MERGE\t(1u<<12)\n+#define ALL_REV_FLAGS\t((1u<<13)-1)\n \n #define DECORATE_SHORT_REFS\t1\n #define DECORATE_FULL_REFS\t2\ndiff --git a/t/t4302-log-line-merge-history.sh b/t/t4302-log-line-merge-history.sh\nnew file mode 100755\nindex 0000000..0c8d023\n--- /dev/null\n+++ b/t/t4302-log-line-merge-history.sh\n@@ -0,0 +1,174 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2010 Bo Yang\n+#\n+\n+test_description='Test git log -L with merge commit'\n+\n+. ./test-lib.sh\n+. \"$TEST_DIRECTORY\"/diff-lib.sh\n+\n+cat >path0 <<\\EOF\n+void func()\n+{\n+\tprintf(\"hello\");\n+}\n+EOF\n+\n+test_expect_success 'Add path0 and commit.' '\n+\tgit add path0 &&\n+\tgit commit -m \"Base commit\"\n+'\n+\n+cat >path0 <<\\EOF\n+void func()\n+{\n+\tprintf(\"hello earth\");\n+}\n+EOF\n+\n+test_expect_success 'Change path0 in master.' '\n+\tgit add path0 &&\n+\tgit commit -m \"Change path0 in master\"\n+'\n+\n+test_expect_success 'Make a new branch from the base commit' '\n+\tgit checkout -b feature master^\n+'\n+\n+cat >path0 <<\\EOF\n+void func()\n+{\n+\tprint(\"hello moon\");\n+}\n+EOF\n+\n+test_expect_success 'Change path0 in feature.' '\n+\tgit add path0 &&\n+\tgit commit -m \"Change path0 in feature\"\n+'\n+\n+test_expect_success 'Merge the master to feature' '\n+\t! git merge master\n+'\n+\n+cat >path0 <<\\EOF\n+void func()\n+{\n+\tprintf(\"hello earth and moon\");\n+}\n+EOF\n+\n+test_expect_success 'Resolve the conflict' '\n+\tgit add path0 &&\n+\tgit commit -m \"Merge two branches\"\n+'\n+\n+test_expect_success 'Show the line level log of path0' '\n+\tgit log --pretty=format:%s%n%b -L /func/,/^}/:path0 > current\n+'\n+\n+sed 's/Q/ /g' >expected <<\\EOF\n+Merge two branches\n+\n+nontrivial merge found\n+path0\n+@@ 3,1 @@\n+Q\tprintf(\"hello earth and moon\");\n+\n+\n+Change path0 in master\n+\n+diff --git a/path0 b/path0\n+index 56aeee5..11e66c5 100644\n+--- a/path0\n++++ b/path0\n+@@ -1,4 +1,4 @@\n+ void func()\n+ {\n+-\tprintf(\"hello\");\n++\tprintf(\"hello earth\");\n+ }\n+\n+Change path0 in feature\n+\n+diff --git a/path0 b/path0\n+index 56aeee5..258fced 100644\n+--- a/path0\n++++ b/path0\n+@@ -1,4 +1,4 @@\n+ void func()\n+ {\n+-\tprintf(\"hello\");\n++\tprint(\"hello moon\");\n+ }\n+\n+Base commit\n+\n+diff --git a/path0 b/path0\n+new file mode 100644\n+index 0000000..56aeee5\n+--- /dev/null\n++++ b/path0\n+@@ -0,0 +1,4 @@\n++void func()\n++{\n++\tprintf(\"hello\");\n++}\n+EOF\n+\n+sed -e 's/Q/ /g' -e 's/#$//' > expected-graph <<\\EOF\n+*   Merge two branches\n+|\\  #\n+| | #\n+| | nontrivial merge found\n+| | path0\n+| | @@ 3,1 @@\n+| |QQ\tprintf(\"hello earth and moon\");\n+| | #\n+| |   #\n+| * Change path0 in master\n+| | #\n+| | diff --git a/path0 b/path0\n+| | index 56aeee5..11e66c5 100644\n+| | --- a/path0\n+| | +++ b/path0\n+| | @@ -3,1 +3,1 @@\n+| | -\tprintf(\"hello\");\n+| | +\tprintf(\"hello earth\");\n+| |   #\n+* | Change path0 in feature\n+|/  #\n+|   #\n+|   diff --git a/path0 b/path0\n+|   index 56aeee5..258fced 100644\n+|   --- a/path0\n+|   +++ b/path0\n+|   @@ -3,1 +3,1 @@\n+|   -\tprintf(\"hello\");\n+|   +\tprint(\"hello moon\");\n+|  #\n+* Base commit\n+  #\n+  diff --git a/path0 b/path0\n+  new file mode 100644\n+  index 0000000..56aeee5\n+  --- /dev/null\n+  +++ b/path0\n+  @@ -0,0 +3,1 @@\n+  +\tprintf(\"hello\");\n+EOF\n+\n+test_expect_success 'Show the line log of the 2 line of path0 with graph' '\n+\tgit log --pretty=format:%s%n%b --graph -L 3,+1:path0 > current-graph\n+'\n+\n+test_expect_success 'validate the output.' '\n+\ttest_cmp current expected\n+'\n+\n+test_expect_success 'validate the graph output.' '\n+\ttest_cmp current-graph expected-graph\n+'\n+\n+test_done\n-- \n1.7.3.3.807.g6ee1f\n"},{"id":"158112","messageId":"a1a60895616caf59b901705d9c0374ecb7f40db3.1292366984.git.trast@student.ethz.ch","threadId":"26071","inReplyTo":"cover.1292366984.git.trast@student.ethz.ch","subject":"[PATCH v6.1 6/8] log -L: add --graph prefix before output","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2010-12-14T22:54:13Z","receivedAt":"2010-12-14T22:54:13Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"From: Bo Yang <struggleyb.nku@gmail.com>\n\nMakes the line level log output look good when used\nwith the '--graph' option.\n\nSigned-off-by: Bo Yang <struggleyb.nku@gmail.com>\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\n---\n line.c |   66 ++++++++++++++++++++++++++++++++++++++++++++++-----------------\n 1 files changed, 48 insertions(+), 18 deletions(-)\n\ndiff --git a/line.c b/line.c\nindex 10870a5..1a9a947 100644\n--- a/line.c\n+++ b/line.c\n@@ -1242,6 +1242,13 @@ static void flush_lines(struct diff_options *opt, const char **ptr, const char *\n \tconst char *p = *ptr;\n \tstruct strbuf buf = STRBUF_INIT;\n \tconst char *reset;\n+\tchar *line_prefix = \"\";\n+\tstruct strbuf *msgbuf;\n+\n+\tif (opt && opt->output_prefix) {\n+\t\tmsgbuf = opt->output_prefix(opt, opt->output_prefix_data);\n+\t\tline_prefix = msgbuf->buf;\n+\t}\n \n \tif (*color)\n \t\treset = diff_get_color_opt(opt, DIFF_RESET);\n@@ -1264,7 +1271,7 @@ static void flush_lines(struct diff_options *opt, const char **ptr, const char *\n \n \twhile (*ptr < end && *lno <= elno) {\n \t\tif (**ptr == '\\n') {\n-\t\t\tfprintf(opt->file, \"%s\", buf.buf);\n+\t\t\tfprintf(opt->file, \"%s%s\", line_prefix, buf.buf);\n \t\t\tif (*ptr - p)\n \t\t\t\tfwrite(p, *ptr - p, 1, opt->file);\n \t\t\tfprintf(opt->file, \"%s\\n\", reset);\n@@ -1274,7 +1281,7 @@ static void flush_lines(struct diff_options *opt, const char **ptr, const char *\n \t\t(*ptr)++;\n \t}\n \tif (*lno <= elno) {\n-\t\tfprintf(opt->file, \"%s\", buf.buf);\n+\t\tfprintf(opt->file, \"%s%s\", line_prefix, buf.buf);\n \t\tif (*ptr - p)\n \t\t\tfwrite(p, *ptr - p, 1, opt->file);\n \t\tfprintf(opt->file, \"%s\\n\", reset);\n@@ -1316,8 +1323,15 @@ static void diff_flush_chunks(struct diff_options *opt, struct line_chunk *chunk\n \tstruct diff_line_range *range = chunk->range;\n \tconst char *set = diff_get_color_opt(opt, DIFF_FRAGINFO);\n \tconst char *reset = diff_get_color_opt(opt, DIFF_RESET);\n+\tchar *line_prefix = \"\";\n+\tstruct strbuf *msgbuf;\n \tint i;\n \n+\tif (opt && opt->output_prefix) {\n+\t\tmsgbuf = opt->output_prefix(opt, opt->output_prefix_data);\n+\t\tline_prefix = msgbuf->buf;\n+\t}\n+\n \tfor (i = 0; i < range->nr; i++) {\n \t\tstruct line_range *r = range->ranges + i;\n \t\tlong lenp = r->pend - r->pstart + 1, pstart = r->pstart;\n@@ -1325,8 +1339,8 @@ static void diff_flush_chunks(struct diff_options *opt, struct line_chunk *chunk\n \t\tif (pstart == 0)\n \t\t\tlenp = 0;\n \n-\t\tfprintf(opt->file, \"%s@@ -%ld,%ld +%ld,%ld @@%s\\n\",\n-\t\t\tset, pstart, lenp, r->start, len, reset);\n+\t\tfprintf(opt->file, \"%s%s@@ -%ld,%ld +%ld,%ld @@%s\\n\",\n+\t\t\tline_prefix, set, pstart, lenp, r->start, len, reset);\n \n \t\tdiff_flush_range(opt, chunk, r);\n \t}\n@@ -1345,6 +1359,13 @@ static void diff_flush_filepair(struct rev_info *rev, struct diff_line_range *ra\n \tconst char *reset = diff_get_color_opt(opt, DIFF_RESET);\n \tstruct line_chunk chunk;\n \tint must_show_header;\n+\tchar *line_prefix = \"\";\n+\tstruct strbuf *msgbuf;\n+\n+\tif (opt && opt->output_prefix) {\n+\t\tmsgbuf = opt->output_prefix(opt, opt->output_prefix_data);\n+\t\tline_prefix = msgbuf->buf;\n+\t}\n \n \t/*\n \t * the ranges that touch no different file, in this case\n@@ -1378,21 +1399,26 @@ static void diff_flush_filepair(struct rev_info *rev, struct diff_line_range *ra\n \tb_two = quote_two(b_prefix, name_b + (*name_b == '/'));\n \tlbl[0] = DIFF_FILE_VALID(one) ? a_one : \"/dev/null\";\n \tlbl[1] = DIFF_FILE_VALID(two) ? b_two : \"/dev/null\";\n-\tstrbuf_addf(&header, \"%sdiff --git %s %s%s\\n\", set, a_one, b_two, reset);\n+\tstrbuf_addf(&header, \"%s%sdiff --git %s %s%s\\n\", line_prefix,\n+\t\t\tset, a_one, b_two, reset);\n \tif (lbl[0][0] == '/') {\n-\t\tstrbuf_addf(&header, \"%snew file mode %06o%s\\n\", set, two->mode, reset);\n+\t\tstrbuf_addf(&header, \"%s%snew file mode %06o%s\\n\",\n+\t\t\tline_prefix, set, two->mode, reset);\n \t} else if (lbl[1][0] == '/') {\n-\t\tstrbuf_addf(&header, \"%sdeleted file mode %06o%s\\n\", set, one->mode, reset);\n+\t\tstrbuf_addf(&header, \"%s%sdeleted file mode %06o%s\\n\",\n+\t\t\tline_prefix, set, one->mode, reset);\n \t} else if (one->mode != two->mode) {\n-\t\t\tstrbuf_addf(&header, \"%sold mode %06o%s\\n\", set, one->mode, reset);\n-\t\t\tstrbuf_addf(&header, \"%snew mode %06o%s\\n\", set, two->mode, reset);\n+\t\t\tstrbuf_addf(&header, \"%s%sold mode %06o%s\\n\",\n+\t\t\t\tline_prefix, set, one->mode, reset);\n+\t\t\tstrbuf_addf(&header, \"%s%snew mode %06o%s\\n\",\n+\t\t\t\tline_prefix, set, two->mode, reset);\n \t}\n \n \tfprintf(opt->file, \"%s%s\", header.buf, meta.buf);\n \tstrbuf_release(&meta);\n \tstrbuf_release(&header);\n-\tfprintf(opt->file, \"%s--- %s%s\\n\", set, lbl[0], reset);\n-\tfprintf(opt->file, \"%s+++ %s%s\\n\", set, lbl[1], reset);\n+\tfprintf(opt->file, \"%s%s--- %s%s\\n\", line_prefix, set, lbl[0], reset);\n+\tfprintf(opt->file, \"%s%s+++ %s%s\\n\", line_prefix, set, lbl[1], reset);\n \tfree((void *)a_one);\n \tfree((void *)b_two);\n \n@@ -1446,12 +1472,13 @@ static void flush_nontrivial_merge(struct rev_info *rev,\n \t\t\t\tmeta, range->spec->path, reset);\n \t\t\tfor (; i < range->nr; i++) {\n \t\t\t\tstruct line_range *r = range->ranges + i;\n-\t\t\t\tfprintf(opt->file, \"%s@@ %ld,%ld @@%s\\n\", frag, r->start,\n+\t\t\t\tfprintf(opt->file, \"%s%s@@ %ld,%ld @@%s\\n\",\n+\t\t\t\t\tline_prefix, frag, r->start,\n \t\t\t\t\tr->end - r->start + 1, reset);\n \t\t\t\tflush_lines(opt, &ptr, end, r->start, r->end,\n \t\t\t\t\t&lno, new, ' ');\n \t\t\t}\n-\t\t\tfprintf(opt->file, \"\\n\");\n+\t\t\tfprintf(opt->file, \"%s\\n\", line_prefix);\n \t\t}\n \t\trange = range->next;\n \t}\n@@ -1464,6 +1491,8 @@ static void line_log_flush(struct rev_info *rev, struct commit *c)\n \t\t\t\t\t\t\t&c->object);\n \tstruct log_info log;\n \tstruct diff_options *opt = &rev->diffopt;\n+\tchar *line_prefix = \"\";\n+\tstruct strbuf *msgbuf;\n \n \tif (!range || !(c->object.flags & NONTRIVIAL_MERGE ||\n \t\t\tc->object.flags & NEED_PRINT))\n@@ -1476,11 +1505,12 @@ static void line_log_flush(struct rev_info *rev, struct commit *c)\n \trev->loginfo = &log;\n \tshow_log(rev);\n \trev->loginfo = NULL;\n-\t/*\n-\t * Add a new line after each commit message, of course we should\n-\t * add --graph alignment later when the patches comes to master.\n-\t */\n-\tfprintf(rev->diffopt.file, \"\\n\");\n+\n+\tif (opt && opt->output_prefix) {\n+\t\tmsgbuf = opt->output_prefix(opt, opt->output_prefix_data);\n+\t\tline_prefix = msgbuf->buf;\n+\t}\n+\tfprintf(rev->diffopt.file, \"%s\\n\", line_prefix);\n \n \tif (c->object.flags & NONTRIVIAL_MERGE)\n \t\tflush_nontrivial_merge(rev, nontrivial);\n-- \n1.7.3.3.807.g6ee1f\n"},{"id":"158110","messageId":"d7d0fce58759b42ced83b6cc0bb4158dac8acc38.1292366984.git.trast@student.ethz.ch","threadId":"26071","inReplyTo":"cover.1292366984.git.trast@student.ethz.ch","subject":"[PATCH v6.1 7/8] log -L: add --full-line-diff option","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2010-12-14T22:54:14Z","receivedAt":"2010-12-14T22:54:14Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"From: Bo Yang <struggleyb.nku@gmail.com>\n\nAlways print the interesting ranges even if the current\ncommit does not change any line of it.\n\nSigned-off-by: Bo Yang <struggleyb.nku@gmail.com>\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\n---\n Documentation/git-log.txt |    4 ++++\n builtin/log.c             |    8 +++++++-\n line.c                    |   22 ++++++++++++++++------\n revision.c                |    2 ++\n revision.h                |    3 ++-\n 5 files changed, 31 insertions(+), 8 deletions(-)\n\ndiff --git a/Documentation/git-log.txt b/Documentation/git-log.txt\nindex 7fcf6e7..f5769bf 100644\n--- a/Documentation/git-log.txt\n+++ b/Documentation/git-log.txt\n@@ -79,6 +79,10 @@ 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 [\\--] <path>...::\n \tShow only commits that affect any of the specified paths. To\n \tprevent confusion with options and branch names, paths may need\ndiff --git a/builtin/log.c b/builtin/log.c\nindex 342d4de..fa57306 100644\n--- a/builtin/log.c\n+++ b/builtin/log.c\n@@ -99,6 +99,7 @@ static void cmd_log_init(int argc, const char **argv, const char *prefix,\n {\n \tint i;\n \tint decoration_given = 0;\n+\tstatic int full_line_diff;\n \tstruct userformat_want w;\n \tstatic struct line_opt_callback_data line_cb = {0};\n \n@@ -106,6 +107,9 @@ static void cmd_log_init(int argc, const char **argv, const char *prefix,\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_BOOLEAN(0, \"full-line-diff\", &full_line_diff,\n+\t\t\t    \"Always print the interesting range even if the \\\n+\t\t\t    current commit does not change any line of it\"),\n \t\tOPT_END()\n \t};\n \n@@ -188,8 +192,10 @@ static void cmd_log_init(int argc, const char **argv, const char *prefix,\n \t}\n \n \t/* Test whether line level history is asked for */\n-\tif (rev->line_level_traverse)\n+\tif (rev->line_level_traverse) {\n \t\tline_log_init(rev, line_cb.ranges);\n+\t\trev->full_line_diff = full_line_diff;\n+\t}\n \n \tsetup_pager();\n }\ndiff --git a/line.c b/line.c\nindex 1a9a947..742c17f 100644\n--- a/line.c\n+++ b/line.c\n@@ -1370,10 +1370,18 @@ static void diff_flush_filepair(struct rev_info *rev, struct diff_line_range *ra\n \t/*\n \t * the ranges that touch no different file, in this case\n \t * the line number will not change, and of course we have\n-\t * no sensible rang->pair since there is no diff run.\n+\t * no sensible range->pair since there is no diff run.\n \t */\n-\tif (!one)\n+\tif (!one) {\n+\t\tif (rev->full_line_diff) {\n+\t\t\tchunk.two = two->data;\n+\t\t\tchunk.two_end = (const char *)two->data + two->size;\n+\t\t\tchunk.ltwo = 1;\n+\t\t\tchunk.range = range;\n+\t\t\tdiff_flush_chunks(&rev->diffopt, &chunk);\n+\t\t}\n \t\treturn;\n+\t}\n \n \tif (range->status == DIFF_STATUS_DELETED)\n \t\tdie(\"We are following an nonexistent file, interesting!\");\n@@ -1495,7 +1503,8 @@ static void line_log_flush(struct rev_info *rev, struct commit *c)\n \tstruct strbuf *msgbuf;\n \n \tif (!range || !(c->object.flags & NONTRIVIAL_MERGE ||\n-\t\t\tc->object.flags & NEED_PRINT))\n+\t\t\tc->object.flags & NEED_PRINT ||\n+\t\t\trev->full_line_diff))\n \t\treturn;\n \n \tif (rev->graph)\n@@ -1516,7 +1525,7 @@ static void line_log_flush(struct rev_info *rev, struct commit *c)\n \t\tflush_nontrivial_merge(rev, nontrivial);\n \telse {\n \t\twhile (range) {\n-\t\t\tif (range->diff)\n+\t\t\tif (range->diff || (range->nr && rev->full_line_diff))\n \t\t\t\tdiff_flush_filepair(rev, range);\n \t\t\trange = range->next;\n \t\t}\n@@ -1573,7 +1582,7 @@ int line_log_walk(struct rev_info *rev)\n \t/* Clear the flags */\n \twhile (list) {\n \t\tlist->item->object.flags &= ~(RANGE_UPDATE | NONTRIVIAL_MERGE |\n-\t\t\t\t\t\tNEED_PRINT | EVIL_MERGE);\n+\t\t\t\tNEED_PRINT | EVIL_MERGE);\n \t\tlist = list->next;\n \t}\n \n@@ -1593,7 +1602,8 @@ int line_log_walk(struct rev_info *rev)\n \t\t}\n \n \t\tif (commit->object.flags & NEED_PRINT ||\n-\t\t    commit->object.flags & NONTRIVIAL_MERGE)\n+\t\t    commit->object.flags & NONTRIVIAL_MERGE ||\n+\t\t    rev->full_line_diff)\n \t\t\tline_log_flush(rev, commit);\n \n \t\tclear_commit_line_range(rev, commit);\ndiff --git a/revision.c b/revision.c\nindex fbebf2f..85a60d0 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1912,6 +1912,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->full_line_diff)\n+\t\trevs->dense = 0;\n \tif (revs->simplify_merges)\n \t\tsimplify_merges(revs);\n \tif (revs->children.name)\ndiff --git a/revision.h b/revision.h\nindex 6100904..29babf3 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -73,7 +73,8 @@ struct rev_info {\n \t\t\tbisect:1,\n \t\t\tancestry_path:1,\n \t\t\tfirst_parent_only:1,\n-\t\t\tline_level_traverse:1;\n+\t\t\tline_level_traverse:1,\n+\t\t\tfull_line_diff:1;\n \n \t/* Diff flags */\n \tunsigned int\tdiff:1,\n-- \n1.7.3.3.807.g6ee1f\n"},{"id":"158116","messageId":"581d171bc4ae048ca07dfe1d51bac3533a2788aa.1292366984.git.trast@student.ethz.ch","threadId":"26071","inReplyTo":"cover.1292366984.git.trast@student.ethz.ch","subject":"[PATCH v6.1 8/8] log -L: implement move/copy detection (-M/-C)","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2010-12-14T22:54:15Z","receivedAt":"2010-12-14T22:54:15Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"From: Bo Yang <struggleyb.nku@gmail.com>\n\nThe basic idea is:\n\n* Keep a list of \"candidate snippets\".  Start out empty.\n\n* Go through all candidates (determined by the level of detection\n  chosen) and diff them against the target file.\n\n  - For each common part in the diff, put it in the \"candidate\n    snippets\" if it's \"worth it\".  (Notably there is no point in\n    adding a snippet that is fully contained in another.)\n\n* Score the snippets.  Lines with alphanumeric characters count more.\n\n* Filter out snippets with low score.  Where there are overlaps,\n  favour higher scores.\n\nSigned-off-by: Bo Yang <struggleyb.nku@gmail.com>\nSigned-off-by: Thomas Rast <trast@student.ethz.ch>\n---\n line.c                          |  556 ++++++++++++++++++++++++++++++++++++++-\n t/t4303-log-line-move-detect.sh |  238 +++++++++++++++++\n t/t4304-log-line-copy-detect.sh |  220 +++++++++++++++\n 3 files changed, 1001 insertions(+), 13 deletions(-)\n create mode 100755 t/t4303-log-line-move-detect.sh\n create mode 100755 t/t4304-log-line-copy-detect.sh\n\ndiff --git a/line.c b/line.c\nindex 742c17f..ae176da 100644\n--- a/line.c\n+++ b/line.c\n@@ -17,6 +17,7 @@ struct print_range {\n \tint start, end;\t\t/* Line range of post-image */\n \tint pstart, pend;\t/* Line range of pre-image */\n \tint line_added : 1;\t/* whether this range is added */\n+\tint copied : 1;\n };\n \n struct print_pair {\n@@ -30,6 +31,7 @@ struct line_range {\n \tlong pstart, pend;\t/* The corresponding range of parent commit */\n \tstruct print_pair pair;\n \t\t\t/* The changed lines inside this range */\n+\tint copy_score;\n \tunsigned int diff:1;\n };\n \n@@ -66,6 +68,7 @@ static inline void print_range_init(struct print_range *r)\n \tr->start = r->end = 0;\n \tr->pstart = r->pend = 0;\n \tr->line_added = 0;\n+\tr->copied = 0;\n }\n \n static inline void print_pair_init(struct print_pair *p)\n@@ -104,6 +107,7 @@ static inline void line_range_clear(struct line_range *r)\n \tr->start = r->end = 0;\n \tr->pstart = r->pend = 0;\n \tprint_pair_clear(&r->pair);\n+\tr->copy_score = 0;\n \tr->diff = 0;\n }\n \n@@ -594,7 +598,7 @@ static void add_line_range(struct rev_info *revs, struct commit *commit,\n \tret = lookup_decoration(&revs->line_range, &commit->object);\n \tif (ret && r)\n \t\tdiff_line_range_merge(ret, r);\n-\telse\n+\telse if (r != NULL)\n \t\tadd_decoration(&revs->line_range, &commit->object, r);\n \n \tif (r)\n@@ -620,6 +624,16 @@ static void clear_commit_line_range(struct rev_info *revs, struct commit *commit\n \treturn ret;\n }\n \n+struct diff_line_range *delete_line_range(struct rev_info *revs, struct commit *commit)\n+{\n+\tstruct diff_line_range *ret = NULL;\n+\n+\tret = lookup_decoration(&revs->line_range, &commit->object);\n+\tadd_decoration(&revs->line_range, &commit->object, NULL);\n+\n+\treturn ret;\n+}\n+\n void line_log_init(struct rev_info *rev, struct diff_line_range *r)\n {\n \tstruct commit *commit = NULL;\n@@ -647,6 +661,515 @@ struct take_range_cb_data {\n \t\t * commit and its parent */\n };\n \n+struct map {\n+\tlong start, end;\n+\tlong pstart, pend;\n+\tstruct diff_filespec *spec;\n+\tint score;\n+};\n+\n+struct mac_cb_data {\n+\tlong plno, tlno;\n+\tint nr;\n+\tint alloc;\n+\tstruct map *maps;\n+\tstruct diff_filespec *spec;\n+};\n+\n+struct mac_state {\n+\tint nr;\n+\tint alloc;\n+\tstruct map *maps;\n+};\n+\n+static void mac_state_init(struct mac_state *state)\n+{\n+\tstate->nr = state->alloc = 0;\n+\tstate->maps = NULL;\n+}\n+\n+static void mac_cb(void *data, long same, long p_next, long t_next)\n+{\n+\tstruct mac_cb_data *d = data;\n+\tlong p_start = d->plno + 1, t_start = d->tlno + 1;\n+\tlong p_end = p_start + same - t_start, t_end = same;\n+\n+\tif (t_end >= t_start) {\n+\t\tALLOC_GROW(d->maps, (d->nr + 1), d->alloc);\n+\t\td->maps[d->nr].start = t_start;\n+\t\td->maps[d->nr].end = t_end;\n+\t\td->maps[d->nr].pstart = p_start;\n+\t\td->maps[d->nr].pend = p_end;\n+\t\td->maps[d->nr].spec = d->spec;\n+\t\td->nr++;\n+\t}\n+\n+\td->plno = p_next;\n+\td->tlno = t_next;\n+}\n+\n+static void mac_state_insert(struct mac_state *state, long s_start, long s_end,\n+\t\tlong start, long end, struct diff_filespec *spec)\n+{\n+\tint i = 0;\n+\tstruct map *maps;\n+\n+\tfor (; i < state->nr; i++) {\n+\t\tif (state->maps[i].start > end)\n+\t\t\tbreak;\n+\t}\n+\n+\tstate->nr++;\n+\tALLOC_GROW(state->maps, state->nr, state->alloc);\n+\tmaps = state->maps;\n+\tmemmove(maps + i + 1, maps + i, (state->nr - i - 1) * sizeof(*maps));\n+\tmaps[i].start = s_start;\n+\tmaps[i].end = s_end;\n+\tmaps[i].pstart = start;\n+\tmaps[i].pend = end;\n+\tmaps[i].spec = spec;\n+\tspec->count++;\n+}\n+\n+static void mac_state_remove(struct mac_state *state, long s_start, long s_end,\n+\t\tlong start, long end)\n+{\n+\tint i = 0;\n+\tstruct map *maps = state->maps;\n+\n+\twhile (i < state->nr) {\n+\t\tif (maps[i].start < start && maps[i].end > start) {\n+\t\t\tmaps[i].end = s_start - 1;\n+\t\t\tmaps[i].pend -= start - s_start;\n+\t\t}\n+\t\tif (maps[i].start < end && maps[i].end > end) {\n+\t\t\tmaps[i].start = s_end + 1;\n+\t\t\tmaps[i].pstart += end - s_end;\n+\t\t}\n+\t\tif (maps[i].start >=start && maps[i].end <= end) {\n+\t\t\tmemmove(maps + i, maps + i + 1, (state->nr - i - 1) * sizeof(*maps));\n+\t\t\tstate->nr--;\n+\t\t\ti--;\n+\t\t}\n+\n+\t\ti++;\n+\t}\n+}\n+\n+/*\n+ * Generally, the 'struct line_range's pstart/pend is used to store\n+ * the pre-image of current range. But here, we use it to store the\n+ * line range of the 'artificial' memory file.\n+ */\n+static struct mac_state *merge_mac(struct mac_cb_data *data,\n+\t\tstruct mac_state *state, long lines)\n+{\n+\tstruct map *maps = data->maps;\n+\tint i = 0;\n+\n+\tassert(state);\n+\n+\twhile (i < data->nr) {\n+\t\tint j = 0;\n+\t\tlong start = maps[i].start;\n+\t\tlong end = maps[i].end;\n+\t\tint should_insert = 0;\n+\t\tlong should_start = start;\n+\t\tlong should_end = end;\n+\t\tlong may_start = start, may_end = end;\n+\t\tlong start_range_len = 0, end_range_len = 0;\n+\n+\t\t/* first round: finds whether this range should be inserted */\n+\t\tif (!state->nr)\n+\t\t\tshould_insert = 1;\n+\t\twhile (state && j < state->nr) {\n+\t\t\tif (state->maps[j].end <= start) {\n+\t\t\t\tif (j+1 == state->nr)\n+\t\t\t\t\tshould_insert = 1;\n+\t\t\t\tj++;\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tif (state->maps[j].start > end)\n+\t\t\t\tshould_insert = 1;\n+\t\t\telse {\n+\t\t\t\tif (state->maps[j].start <= start) {\n+\t\t\t\t\tif (state->maps[j].end >= end)\n+\t\t\t\t\t\tshould_insert = 0;\n+\t\t\t\t\telse {\n+\t\t\t\t\t\tshould_insert = 1;\n+\t\t\t\t\t\tmay_start = state->maps[j].end + 1;\n+\t\t\t\t\t\tstart_range_len = state->maps[j].end -\n+\t\t\t\t\t\t\tstate->maps[j].start + 1;\n+\t\t\t\t\t}\n+\t\t\t\t} else {\n+\t\t\t\t\tif (state->maps[j].end > end) {\n+\t\t\t\t\t\tshould_insert = 1;\n+\t\t\t\t\t\tmay_end = state->maps[j].start - 1;\n+\t\t\t\t\t\tend_range_len = state->maps[j].end -\n+\t\t\t\t\t\t\tstate->maps[j].start + 1;\n+\t\t\t\t\t} else\n+\t\t\t\t\t\tshould_insert = 1;\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t\tj++;\n+\t\t}\n+\n+\t\t/* second round: insert the new range and adjust the current one */\n+\t\tif (should_insert) {\n+\t\t\t/* We always keep the longest range in prior */\n+\t\t\tif (start_range_len > end_range_len) {\n+\t\t\t\tif (start_range_len > should_end - should_start + 1)\n+\t\t\t\t\tshould_start = may_start;\n+\t\t\t\tif (end_range_len > should_end - should_start + 1)\n+\t\t\t\t\tshould_end = may_end;\n+\t\t\t} else {\n+\t\t\t\tif (end_range_len > should_end - should_start + 1)\n+\t\t\t\t\tshould_end = may_end;\n+\t\t\t\tif (start_range_len > should_end - should_start + 1)\n+\t\t\t\t\tshould_start = may_start;\n+\t\t\t}\n+\n+\t\t\tmac_state_remove(state, should_start, should_end,\n+\t\t\t\t\tmaps[i].start, maps[i].end);\n+\n+\t\t\tstart = maps[i].pstart + should_start - maps[i].start;\n+\t\t\tend = maps[i].pend - (maps[i].end - should_end);\n+\t\t\tmac_state_insert(state, should_start, should_end, start, end, data->spec);\n+\t\t}\n+\n+\t\ti++;\n+\t}\n+\n+\treturn state;\n+}\n+\n+static struct mac_state *find_mac_in_file(mmfile_t *file_p, mmfile_t *file_t,\n+\t\tlong lines, unsigned char *scores, struct diff_filespec *spec,\n+\t\tstruct mac_state *state)\n+{\n+\txpparam_t xpp;\n+\txdemitconf_t xecfg;\n+\tstruct mac_cb_data cb = {0, 0, 0, 0, NULL, spec};\n+\n+\tmemset(&xpp, 0, sizeof(xpp));\n+\tmemset(&xecfg, 0, sizeof(xecfg));\n+\txecfg.ctxlen = xecfg.interhunkctxlen = 0;\n+\n+\txdi_diff_hunks(file_p, file_t, mac_cb, &cb, &xpp, &xecfg);\n+\n+\tif (cb.tlno < lines) {\n+\t\tALLOC_GROW(cb.maps, (cb.nr + 1), cb.alloc);\n+\t\tcb.maps[cb.nr].start = cb.tlno + 1;\n+\t\tcb.maps[cb.nr].end = lines;\n+\t\tcb.maps[cb.nr].pstart = cb.plno + 1;\n+\t\tcb.maps[cb.nr].pend = cb.plno + lines - cb.tlno;\n+\t\tcb.maps[cb.nr].spec = spec;\n+\t\tcb.nr++;\n+\t}\n+\n+\tif (cb.nr)\n+\t\tstate = merge_mac(&cb, state, lines);\n+\tfree(cb.maps);\n+\n+\treturn state;\n+}\n+\n+#define LINE_SCORE 6\n+#define TRIVIAL_SCORE 2\n+static void setup_mac_file(struct diff_filespec *spec, mmfile_t *lines,\n+\t\tunsigned char *scores, long start, long end)\n+{\n+\tint i = 0;\n+\tint line = 1;\n+\tint size = 0;\n+\tchar *data = spec->data;\n+\n+\tmemset(scores, TRIVIAL_SCORE, end - start + 1);\n+\twhile (i < spec->size) {\n+\t\tint index = line - start;\n+\t\tif (line < start) {\n+\t\t\tif (data[i] == '\\n')\n+\t\t\t\tline++;\n+\t\t\ti++;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tif (line > end)\n+\t\t\tbreak;\n+\t\tif (size == 0)\n+\t\t\tlines->ptr = data + i;\n+\t\tsize++;\n+\t\tif (scores[index] == TRIVIAL_SCORE && data[i] <= 'z' && data[i] >= 'a')\n+\t\t\tscores[index] = LINE_SCORE;\n+\t\tif (scores[index] == TRIVIAL_SCORE && data[i] <= 'Z' && data[i] >= 'A')\n+\t\t\tscores[index] = LINE_SCORE;\n+\t\tif (scores[index] == TRIVIAL_SCORE && data[i] <= '9' && data[i] >= '0')\n+\t\t\tscores[index] = LINE_SCORE;\n+\t\tif (data[i] == '\\n')\n+\t\t\tline++;\n+\n+\t\ti++;\n+\t}\n+\n+\tlines->size = size;\n+}\n+\n+static void mac_state_cal_score(long lines, unsigned char *scores, struct mac_state *state)\n+{\n+\tstruct map *maps = state->maps;\n+\tint i = 0;\n+\n+\twhile (i < state->nr) {\n+\t\tint score = 0;\n+\t\tint j = maps[i].start;\n+\t\twhile (j <= maps[i].end) {\n+\t\t\tassert(j <= lines);\n+\t\t\tscore += scores[j - 1];\n+\t\t\tj++;\n+\t\t}\n+\n+\t\tmaps[i].score = score;\n+\t\ti++;\n+\t}\n+}\n+\n+#define MIN_GAP 3\n+#define RANGE_MIN_SCORE 20\n+static struct diff_line_range *mac_combine_remove(struct diff_line_range *range)\n+{\n+\tstruct diff_line_range *r = range, *prev = range, *ret = range;\n+\n+\t// Firstly to combine adjacent-enough range\n+\twhile (r) {\n+\t\tint i = 0;\n+\t\tstruct line_range *rs = r->ranges;\n+\t\tfor (; i < r->nr; i++) {\n+\t\t\tif (i + 1 < r->nr &&\n+\t\t\t\t(rs[i + 1].end - rs[i].start < MIN_GAP)) {\n+\t\t\t\trs[i].end = rs[i + 1].end;\n+\t\t\t\trs[i].copy_score += rs[i + 1].copy_score;\n+\t\t\t\tmemmove(rs + i + 1, rs + i + 2, (r->nr - i - 1) * sizeof(*rs));\n+\t\t\t\tr->nr--;\n+\t\t\t\ti--;\n+\t\t\t}\n+\t\t}\n+\t\tr = r->next;\n+\t}\n+\n+\t// then delete the trivial ones\n+\tr = range;\n+\twhile (r) {\n+\t\tint i = 0;\n+\t\tstruct line_range *rs = r->ranges;\n+\t\tfor (; i < r->nr; i++) {\n+\t\t\tif (rs[i].copy_score < RANGE_MIN_SCORE) {\n+\t\t\t\tmemmove(rs + i, rs + i + 1, (r->nr - i) * sizeof(*rs));\n+\t\t\t\tr->nr--;\n+\t\t\t\ti--;\n+\t\t\t}\n+\t\t}\n+\t\tr = r->next;\n+\t}\n+\n+\t// then delete the empty diff_line_range\n+\tr = range;\n+\twhile (r) {\n+\t\tstruct diff_line_range *next = r->next;\n+\t\tif (!r->nr) {\n+\t\t\tdiff_line_range_clear(r);\n+\t\t\tfree(r);\n+\t\t\tif (ret == r) {\n+\t\t\t\tret = next;\n+\t\t\t\tprev = next;\n+\t\t\t}\n+\t\t} else if (prev != r) {\n+\t\t\t\tprev->next = r;\n+\t\t\t\tprev = r;\n+\t\t}\n+\n+\t\tr = next;\n+\t}\n+\n+\treturn ret;\n+}\n+\n+static struct diff_line_range *mac_state_to_line_range(struct mac_state *state)\n+{\n+\tstruct diff_line_range *ret = NULL;\n+\tstruct diff_line_range *prev = NULL;\n+\tstruct map *maps = state->maps;\n+\tint i = 0;\n+\tstruct line_range *rg = NULL;\n+\n+\twhile (i < state->nr) {\n+\t\tstruct diff_line_range *r = ret;\n+\t\twhile (r) {\n+\t\t\tif (r->spec == maps[i].spec) {\n+\t\t\t\trg = diff_line_range_insert(r, NULL, maps[i].pstart,\n+\t\t\t\t\t\tmaps[i].pend);\n+\t\t\t\trg->copy_score += maps[i].score;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tr = r->next;\n+\t\t}\n+\n+\t\tif (!r) {\n+\t\t\tr = xmalloc(sizeof(*r));\n+\t\t\tdiff_line_range_init(r);\n+\t\t\tr->spec = maps[i].spec;\n+\t\t\trg = diff_line_range_insert(r, NULL, maps[i].pstart, maps[i].pend);\n+\t\t\trg->copy_score += maps[i].score;\n+\n+\t\t\tif (!ret) {\n+\t\t\t\tret = r;\n+\t\t\t\tprev = r;\n+\t\t\t} else {\n+\t\t\t\tprev->next = r;\n+\t\t\t\tprev = r;\n+\t\t\t}\n+\t\t}\n+\n+\t\ti++;\n+\t}\n+\n+\treturn mac_combine_remove(ret);\n+}\n+\n+struct mac_state *find_mac_in_one_file(struct commit *p,\n+\t\tchar *path, mmfile_t *file_t, long lines,\n+\t\tunsigned char *scores)\n+{\n+\tstruct diff_filespec *spec = alloc_filespec(path);\n+\tunsigned char sha1[20];\n+\tunsigned mode;\n+\tmmfile_t file_p;\n+\tstruct mac_state *ret = xmalloc(sizeof(*ret));\n+\n+\tmac_state_init(ret);\n+\tif (get_tree_entry(p->object.sha1, path, sha1, &mode))\n+\t\treturn NULL;\n+\tfill_filespec(spec, sha1, mode);\n+\tdiff_populate_filespec(spec, 0);\n+\tfile_p.ptr = spec->data;\n+\tfile_p.size = spec->size;\n+\n+\tret = find_mac_in_file(&file_p, file_t, lines, scores, spec, ret);\n+\tmac_state_cal_score(lines, scores, ret);\n+\n+\treturn ret;\n+}\n+\n+struct mac_state *find_mac_in_all_file(struct rev_info *rev, struct commit *c,\n+\t\tstruct commit *p, mmfile_t *file_t, long lines,\n+\t\tunsigned char *scores)\n+{\n+\tstruct diff_options diff_opts;\n+\tconst char *paths[1];\n+\tint j = 0;\n+\tstruct mac_state *state = xmalloc(sizeof(*state));\n+\n+\tmac_state_init(state);\n+\t/* ok, we can start to do the move/copy detect now */\n+\tdiff_setup(&diff_opts);\n+\tDIFF_OPT_SET(&diff_opts, RECURSIVE);\n+\tdiff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;\n+\tpaths[0] = NULL;\n+\tdiff_tree_setup_paths(paths, &diff_opts);\n+\tif (diff_setup_done(&diff_opts) < 0)\n+\t\tdie(\"diff-setup in line.c\");\n+\tif (DIFF_OPT_TST(&rev->diffopt, FIND_COPIES_HARDER))\n+\t\tDIFF_OPT_SET(&diff_opts, FIND_COPIES_HARDER);\n+\n+\tdiff_tree_sha1(p->tree->object.sha1, c->tree->object.sha1,\n+\t\t\t\"\", &diff_opts);\n+\tfor (j = 0; j < diff_queued_diff.nr; j++) {\n+\t\tstruct diff_filepair *p = diff_queued_diff.queue[j];\n+\t\tmmfile_t file_p;\n+\n+\t\tif (!DIFF_FILE_VALID(p->one))\n+\t\t\tcontinue;\n+\t\tif (S_ISGITLINK(p->one->mode))\n+\t\t\tcontinue;\n+\t\tdiff_populate_filespec(p->one, 0);\n+\t\tfile_p.ptr = p->one->data;\n+\t\tfile_p.size = p->one->size;\n+\n+\t\tp->one->count++;\n+\t\tstate = find_mac_in_file(&file_p, file_t, lines, scores, p->one, state);\n+\t}\n+\n+\tdiff_flush(&diff_opts);\n+\tdiff_tree_release_paths(&diff_opts);\n+\n+\tmac_state_cal_score(lines, scores, state);\n+\n+\treturn state;\n+}\n+\n+static void find_mac_for_range(struct rev_info *rev,\n+\t\tstruct commit *c, struct commit *p,\n+\t\tstruct diff_line_range *r, struct print_range *pr)\n+{\n+\tunsigned char *scores;\n+\tstruct mac_state *state;\n+\tmmfile_t lines = {NULL, 0};\n+\tstruct diff_line_range *copied = NULL;\n+\n+\t/* Do not search for source of ranges shorter than 3 lines */\n+\tif (pr->line_added && (pr->end - pr->start) < 3)\n+\t\treturn;\n+\n+\tscores = xmalloc(pr->end - pr->start + 1);\n+\tsetup_mac_file(r->spec, &lines, scores, pr->start, pr->end);\n+\n+\tif (rev->diffopt.detect_rename == DIFF_DETECT_RENAME)\n+\t\tstate = find_mac_in_one_file(p, r->spec->path, &lines,\n+\t\t\t\t\t     pr->end - pr->start + 1, scores);\n+\telse\n+\t\tstate = find_mac_in_all_file(rev, c, p, &lines,\n+\t\t\t\t\t     pr->end - pr->start + 1, scores);\n+\n+\tcopied = mac_state_to_line_range(state);\n+\tif (copied) {\n+\t\tadd_line_range(rev, p, copied);\n+\t\tpr->copied = 1;\n+\t}\n+\tfree(scores);\n+}\n+\n+/*\n+ * Find the code move/copy, here we reuse the '-M/-C' options in diff options.\n+ * -M means that finds the code in the same file;\n+ * -C means that finds the code in all the files in parent commit.\n+ */\n+static void find_mac(struct rev_info *rev, struct commit *c)\n+{\n+\tstruct diff_line_range *r = lookup_line_range(rev, c);\n+\tstruct diff_line_range *prange = NULL;\n+\tstruct commit *p = NULL;\n+\n+\tif (c->parents == NULL)\n+\t\treturn;\n+\n+\tassert(c->parents->next == NULL);\n+\tp = c->parents->item;\n+\tparse_commit(p);\n+\n+\twhile (r) {\n+\t\tint n;\n+\t\tfor (n = 0; n < r->nr; n++) {\n+\t\t\tstruct print_pair *pair = &r->ranges[n].pair;\n+\t\t\tint i;\n+\t\t\tfor (i = 0; i < pair->nr; i++)\n+\t\t\t\tfind_mac_for_range(rev, c, p, r, &pair->ranges[i]);\n+\t\t}\n+\n+\t\tr = r->next;\n+\t}\n+\n+\tadd_line_range(rev, p, prange);\n+}\n+\n #define SCALE_FACTOR 4\n /*\n  * [p_start, p_end] represents the pre-image of current diff hunk,\n@@ -942,7 +1465,7 @@ static int assign_range_to_parent(struct rev_info *rev, struct commit *commit,\n \tvoid *tree1 = NULL, *tree2 = NULL;\n \tstruct tree_desc desc1, desc2;\n \tstruct diff_queue_struct *queue;\n-\tstruct take_range_cb_data cb_data = {NULL, cur_range, 0, 0};\n+\tstruct take_range_cb_data cb_data = {NULL, cur_range, 0, 0, 0};\n \txpparam_t xpp;\n \txdemitconf_t xecfg;\n \tint i, diff = 0;\n@@ -1083,15 +1606,6 @@ static int assign_range_to_parent(struct rev_info *rev, struct commit *commit,\n \t\tassert(parent);\n \t\tassert(final_range->spec);\n \t\tadd_line_range(rev, parent, final_range);\n-\t} else {\n-\t\t/*\n-\t\t * If there is no new ranges assigned to the parent,\n-\t\t * we should mark it as a 'root' commit.\n-\t\t */\n-\t\tif (commit->parents && !commit->parents->next) {\n-\t\t\tfree(commit->parents);\n-\t\t\tcommit->parents = NULL;\n-\t\t}\n \t}\n \n \t/* and the ranges of current commit is updated */\n@@ -1120,6 +1634,18 @@ static void diff_update_parent_range(struct rev_info *rev,\n \t}\n \n \tassign_range_to_parent(rev, commit, c, r, &rev->diffopt, 1);\n+\n+\tif (rev->diffopt.detect_rename > 0)\n+\t\tfind_mac(rev, commit);\n+\n+\t/*\n+\t * If there is no new ranges assigned to the parent,\n+\t * we should mark it as a 'root' commit.\n+\t */\n+\tif (c != NULL && lookup_line_range(rev, c) == NULL) {\n+\t\tfree(commit->parents);\n+\t\tcommit->parents = NULL;\n+\t}\n }\n \n struct commit_state {\n@@ -1306,8 +1832,12 @@ static void diff_flush_range(struct diff_options *opt, struct line_chunk *chunk,\n \t\tif (!pr->line_added)\n \t\t\tflush_lines(opt, &chunk->one, chunk->one_end,\n \t\t\t\tpr->pstart, pr->pend, &chunk->lone, old, '-');\n-\t\tflush_lines(opt, &chunk->two, chunk->two_end,\n-\t\t\tpr->start, pr->end, &chunk->ltwo, new, '+');\n+\t\tif (pr->copied)\n+\t\t\tflush_lines(opt, &chunk->two, chunk->two_end,\n+\t\t\t\tpr->start, pr->end, &chunk->ltwo, new, ' ');\n+\t\telse\n+\t\t\tflush_lines(opt, &chunk->two, chunk->two_end,\n+\t\t\t\tpr->start, pr->end, &chunk->ltwo, new, '+');\n \n \t\tcur = pr->end + 1;\n \t}\ndiff --git a/t/t4303-log-line-move-detect.sh b/t/t4303-log-line-move-detect.sh\nnew file mode 100755\nindex 0000000..0462ec0\n--- /dev/null\n+++ b/t/t4303-log-line-move-detect.sh\n@@ -0,0 +1,238 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2010 Bo Yang\n+#\n+\n+test_description='Test git log -L with code movement'\n+\n+. ./test-lib.sh\n+. \"$TEST_DIRECTORY\"/diff-lib.sh\n+\n+cat >path0 <<\\EOF\n+void func()\n+{\n+\tint a = 0;\n+\tint b = 1;\n+\tint c;\n+\tc = a + b;\n+}\n+\n+void output()\n+{\n+\tprintf(\"hello world\");\n+}\n+EOF\n+\n+test_expect_success 'add path0 and commit.' '\n+\tgit add path0 &&\n+\tgit commit -m \"Base commit\"\n+'\n+\n+cat >path0 <<\\EOF\n+void func()\n+{\n+\tint a = 0;\n+\tint b = 1;\n+\tint c;\n+\tc = a + b;\n+}\n+\n+void output()\n+{\n+\tint d = 3;\n+\tint e = 5;\n+\tprintf(\"hello world\");\n+\tprintf(\"bye!\");\n+}\n+EOF\n+\n+test_expect_success 'Change the some lines of path0.' '\n+\tgit add path0 &&\n+\tgit commit -m \"Change some lines of path0\"\n+'\n+\n+cat >path0 <<\\EOF\n+void func()\n+{\n+\tint a = 0;\n+\tint b = 1;\n+\tint c;\n+\tc = a + b;\n+}\n+\n+void output()\n+{\n+\tint d = 3;\n+\tint e = 5;\n+\tprintf(\"hello world\");\n+\tprintf(\"bye!\");\n+}\n+\n+void comb()\n+{\n+\tint a = 0;\n+\tint b = 1;\n+\tint c;\n+\tc = a + b;\n+\tint d = 3;\n+\tint e = 5;\n+\tprintf(\"hello world\");\n+\tprintf(\"bye!\");\n+}\n+EOF\n+\n+test_expect_success 'Move two functions into one' '\n+\tgit add path0 &&\n+\tgit commit -m \"Move two functions into one\"\n+'\n+\n+cat >path0 <<\\EOF\n+void comb()\n+{\n+\tint a = 0;\n+\tint b = 1;\n+\tint c;\n+\tc = a + b;\n+\tprintf(\"hello world\");\n+\tprintf(\"bye!\");\n+}\n+EOF\n+\n+test_expect_success 'Final change of path0.' '\n+\tgit add path0 &&\n+\tgit commit -m \"Final change of path0\"\n+'\n+\n+sed -e 's/Q/ /g' -e 's/#$//' >expected-no-M <<\\EOF\n+* Final change of path0\n+| #\n+| diff --git a/path0 b/path0\n+| index 495f978..b744a93 100644\n+| --- a/path0\n+| +++ b/path0\n+| @@ -17,11 +1,9 @@\n+|  void comb()\n+|  {\n+|QQ\tint a = 0;\n+|QQ\tint b = 1;\n+|QQ\tint c;\n+|QQ\tc = a + b;\n+| -\tint d = 3;\n+| -\tint e = 5;\n+|QQ\tprintf(\"hello world\");\n+|QQ\tprintf(\"bye!\");\n+|  }\n+|  #\n+* Move two functions into one\n+  #\n+  diff --git a/path0 b/path0\n+  index cd42622..495f978 100644\n+  --- a/path0\n+  +++ b/path0\n+  @@ -0,0 +17,11 @@\n+  +void comb()\n+  +{\n+  +\tint a = 0;\n+  +\tint b = 1;\n+  +\tint c;\n+  +\tc = a + b;\n+  +\tint d = 3;\n+  +\tint e = 5;\n+  +\tprintf(\"hello world\");\n+  +\tprintf(\"bye!\");\n+  +}\n+EOF\n+\n+sed -e 's/Q/ /g' -e 's/#$//' >expected-M <<\\EOF\n+* Final change of path0\n+| #\n+| diff --git a/path0 b/path0\n+| index 495f978..b744a93 100644\n+| --- a/path0\n+| +++ b/path0\n+| @@ -17,11 +1,9 @@\n+|  void comb()\n+|  {\n+|QQ\tint a = 0;\n+|QQ\tint b = 1;\n+|QQ\tint c;\n+|QQ\tc = a + b;\n+| -\tint d = 3;\n+| -\tint e = 5;\n+|QQ\tprintf(\"hello world\");\n+|QQ\tprintf(\"bye!\");\n+|  }\n+|  #\n+* Move two functions into one\n+| #\n+| diff --git a/path0 b/path0\n+| index cd42622..495f978 100644\n+| --- a/path0\n+| +++ b/path0\n+| @@ -0,0 +17,11 @@\n+|  void comb()\n+|  {\n+|QQ\tint a = 0;\n+|QQ\tint b = 1;\n+|QQ\tint c;\n+|QQ\tc = a + b;\n+|QQ\tint d = 3;\n+|QQ\tint e = 5;\n+|QQ\tprintf(\"hello world\");\n+|QQ\tprintf(\"bye!\");\n+|  }\n+|  #\n+* Change some lines of path0\n+| #\n+| diff --git a/path0 b/path0\n+| index f5e09df..cd42622 100644\n+| --- a/path0\n+| +++ b/path0\n+| @@ -2,5 +2,5 @@\n+|  {\n+|QQ\tint a = 0;\n+|QQ\tint b = 1;\n+|QQ\tint c;\n+|QQ\tc = a + b;\n+| @@ -11,2 +11,5 @@\n+| +\tint d = 3;\n+| +\tint e = 5;\n+|QQ\tprintf(\"hello world\");\n+| +\tprintf(\"bye!\");\n+|  }\n+|  #\n+* Base commit\n+  #\n+  diff --git a/path0 b/path0\n+  new file mode 100644\n+  index 0000000..f5e09df\n+  --- /dev/null\n+  +++ b/path0\n+  @@ -0,0 +2,5 @@\n+  +{\n+  +\tint a = 0;\n+  +\tint b = 1;\n+  +\tint c;\n+  +\tc = a + b;\n+  @@ -0,0 +11,2 @@\n+  +\tprintf(\"hello world\");\n+  +}\n+EOF\n+\n+test_expect_success 'Show the line level log of path0' '\n+\tgit log --pretty=format:%s%n%b --graph -L /comb/,/^}/:path0 > current-no-M\n+'\n+\n+test_expect_success 'validate the path0 output.' '\n+\ttest_cmp current-no-M expected-no-M\n+'\n+\n+test_expect_success 'Show the line level log of path0 with -M' '\n+\tgit log --pretty=format:%s%n%b --graph -M -L /comb/,/^}/:path0 > current-M\n+'\n+\n+test_expect_success 'validate the path1 output.' '\n+\ttest_cmp current-M expected-M\n+'\n+\n+test_done\ndiff --git a/t/t4304-log-line-copy-detect.sh b/t/t4304-log-line-copy-detect.sh\nnew file mode 100755\nindex 0000000..de0e004\n--- /dev/null\n+++ b/t/t4304-log-line-copy-detect.sh\n@@ -0,0 +1,220 @@\n+#!/bin/sh\n+#\n+# Copyright (c) 2010 Bo Yang\n+#\n+\n+test_description='Test git log -L with -C'\n+\n+. ./test-lib.sh\n+. \"$TEST_DIRECTORY\"/diff-lib.sh\n+\n+cat >path0 <<\\EOF\n+void func()\n+{\n+\tint a = 0;\n+\tint b = 1;\n+\tint c;\n+\tc = a + b;\n+}\n+EOF\n+\n+cat >path1 <<\\EOF\n+void output()\n+{\n+\tprintf(\"hello world\");\n+}\n+EOF\n+\n+test_expect_success 'add path0/path1 and commit.' '\n+\tgit add path0 path1 &&\n+\tgit commit -m \"Base commit\"\n+'\n+\n+cat >path1 <<\\EOF\n+void output()\n+{\n+\tint d = 3;\n+\tint e = 5;\n+\tprintf(\"hello world\");\n+\tprintf(\"bye!\");\n+}\n+EOF\n+\n+test_expect_success 'Change the some lines of path1.' '\n+\tgit add path1 &&\n+\tgit commit -m \"Change some lines of path1\"\n+'\n+\n+cat >path2 <<\\EOF\n+void comb()\n+{\n+\tint a = 0;\n+\tint b = 1;\n+\tint c;\n+\tc = a + b;\n+\tint d = 3;\n+\tint e = 5;\n+\tprintf(\"hello world\");\n+\tprintf(\"bye!\");\n+}\n+EOF\n+\n+test_expect_success 'Move two functions into one in path2' '\n+\tgit add path2 &&\n+\tgit rm path0 path1 &&\n+\tgit commit -m \"Move two functions into path2\"\n+'\n+\n+cat >path2 <<\\EOF\n+void comb()\n+{\n+\tint a = 0;\n+\tint b = 1;\n+\tint c;\n+\tc = a + b;\n+\tprintf(\"hello world\");\n+\tprintf(\"bye!\");\n+}\n+EOF\n+\n+test_expect_success 'Final change of path2.' '\n+\tgit add path2 &&\n+\tgit commit -m \"Final change of path2\"\n+'\n+\n+sed -e 's/Q/ /g' -e 's/#$//' >expected-no-C <<\\EOF\n+* Final change of path2\n+| #\n+| diff --git a/path2 b/path2\n+| index ca6a800..b744a93 100644\n+| --- a/path2\n+| +++ b/path2\n+| @@ -1,11 +1,9 @@\n+|  void comb()\n+|  {\n+|QQ\tint a = 0;\n+|QQ\tint b = 1;\n+|QQ\tint c;\n+|QQ\tc = a + b;\n+| -\tint d = 3;\n+| -\tint e = 5;\n+|QQ\tprintf(\"hello world\");\n+|QQ\tprintf(\"bye!\");\n+|  }\n+|  #\n+* Move two functions into path2\n+  #\n+  diff --git a/path2 b/path2\n+  new file mode 100644\n+  index 0000000..ca6a800\n+  --- /dev/null\n+  +++ b/path2\n+  @@ -0,0 +1,11 @@\n+  +void comb()\n+  +{\n+  +\tint a = 0;\n+  +\tint b = 1;\n+  +\tint c;\n+  +\tc = a + b;\n+  +\tint d = 3;\n+  +\tint e = 5;\n+  +\tprintf(\"hello world\");\n+  +\tprintf(\"bye!\");\n+  +}\n+EOF\n+\n+sed -e 's/Q/ /g' -e 's/#$//' >expected-C <<\\EOF\n+* Final change of path2\n+| #\n+| diff --git a/path2 b/path2\n+| index ca6a800..b744a93 100644\n+| --- a/path2\n+| +++ b/path2\n+| @@ -1,11 +1,9 @@\n+|  void comb()\n+|  {\n+|QQ\tint a = 0;\n+|QQ\tint b = 1;\n+|QQ\tint c;\n+|QQ\tc = a + b;\n+| -\tint d = 3;\n+| -\tint e = 5;\n+|QQ\tprintf(\"hello world\");\n+|QQ\tprintf(\"bye!\");\n+|  }\n+|  #\n+* Move two functions into path2\n+| #\n+| diff --git a/path2 b/path2\n+| new file mode 100644\n+| index 0000000..ca6a800\n+| --- /dev/null\n+| +++ b/path2\n+| @@ -0,0 +1,11 @@\n+|  void comb()\n+|  {\n+|QQ\tint a = 0;\n+|QQ\tint b = 1;\n+|QQ\tint c;\n+|QQ\tc = a + b;\n+|QQ\tint d = 3;\n+|QQ\tint e = 5;\n+|QQ\tprintf(\"hello world\");\n+|QQ\tprintf(\"bye!\");\n+|  }\n+|  #\n+* Change some lines of path1\n+| #\n+| diff --git a/path1 b/path1\n+| index 52be2a5..bf3a80f 100644\n+| --- a/path1\n+| +++ b/path1\n+| @@ -2,3 +2,6 @@\n+|  {\n+| +\tint d = 3;\n+| +\tint e = 5;\n+|QQ\tprintf(\"hello world\");\n+| +\tprintf(\"bye!\");\n+|  }\n+|  #\n+* Base commit\n+  #\n+  diff --git a/path1 b/path1\n+  new file mode 100644\n+  index 0000000..52be2a5\n+  --- /dev/null\n+  +++ b/path1\n+  @@ -0,0 +2,3 @@\n+  +{\n+  +\tprintf(\"hello world\");\n+  +}\n+  diff --git a/path0 b/path0\n+  new file mode 100644\n+  index 0000000..fb33939\n+  --- /dev/null\n+  +++ b/path0\n+  @@ -0,0 +2,5 @@\n+  +{\n+  +\tint a = 0;\n+  +\tint b = 1;\n+  +\tint c;\n+  +\tc = a + b;\n+EOF\n+\n+test_expect_success 'Show the line level log of path2' '\n+\tgit log --pretty=format:%s%n%b --graph -L /comb/,/^}/:path2 > current-no-C\n+'\n+\n+test_expect_success 'validate the path2 output.' '\n+\ttest_cmp current-no-C expected-no-C\n+'\n+\n+test_expect_success 'Show the line level log of path2 with -C' '\n+\tgit log --pretty=format:%s%n%b --graph -C -L /comb/,/^}/:path2 > current-C\n+'\n+\n+test_expect_success 'validate the path2 output.' '\n+\ttest_cmp current-C expected-C\n+'\n+\n+test_done\n-- \n1.7.3.3.807.g6ee1f\n"},{"id":"158127","messageId":"7vfwtzrin3.fsf@alter.siamese.dyndns.org","threadId":"26071","inReplyTo":"426fca7313fc9466efa036b7b86947f23548fc26.1292366984.git.trast@student.ethz.ch","subject":"Re: [PATCH v6.1 4/8] Implement line-history search (git log -L)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-12-15T00:20:48Z","receivedAt":"2010-12-15T00:20:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast <trast@student.ethz.ch> writes:\n\n> +void line_log_init(struct rev_info *rev, struct diff_line_range *r)\n> +{\n> +\tstruct commit *commit = NULL;\n> +\tstruct diff_options *opt = &rev->diffopt;\n> +\n> +\tcommit = (struct commit *)verify_commit(rev);\n> +\tparse_lines(commit, r);\n> +\n> +\tadd_line_range(rev, commit, r);\n> +\t/*\n> +\t * Note we support -M/-C to detect file rename\n> +\t */\n> +\topt->nr_paths = 0;\n> +\tdiff_tree_release_paths(opt);\n> +}\n\nNote that opt->nr_paths may be going away soon (cf. nd/struct-pathspec\ntopic).  Do you need this assignment here?\n"}]}