[PATCH V5 00/17] Reroll a version 5 of this series

[PATCH V5 00/17] Reroll a version 5 of this series

[Bo Yang]

Changes:
1. Fix all format problems;
2. Split the "too long" lines in multiple lines;
3. '$' to represent the last line of a file;
4. Error string change;
5. Add more comments;
6. Combine test cases together;
7. Struct name change

Bo Yang (17):
  parse-options: enhance STOP_AT_NON_OPTION
  parse-options: add two helper functions
  Add the basic data structure for line level history
  Refactor parse_loc
  Parse the -L options
  Export three functions from diff.c
  Add range clone functions
  map/take range to the parent of commits
  Print the line log
  Hook line history into cmd_log, ensuring a topo-ordered walk
  Make rewrite_parents public to other part of git
  Make graph_next_line external to other part of git
  Add parent rewriting to line history browser
  Add --graph prefix before line history output
  Add --full-line-diff option
  Add tests for line history browser
  Document line history browser

 Documentation/blame-options.txt     |   19 +-
 Documentation/git-log.txt           |   15 +
 Documentation/line-range-format.txt |   18 +
 Makefile                            |    2 +
 builtin/blame.c                     |   89 +--
 builtin/log.c                       |  113 +++-
 diff.c                              |    6 +-
 diff.h                              |   17 +
 graph.c                             |   14 +-
 graph.h                             |   10 +
 line.c                              | 1551 +++++++++++++++++++++++++++++++++++
 line.h                              |  141 ++++
 parse-options.c                     |   22 +-
 parse-options.h                     |    7 +-
 revision.c                          |   25 +-
 revision.h                          |   23 +-
 t/t4301-log-line-single-history.sh  |  627 ++++++++++++++
 t/t4302-log-line-merge-history.sh   |  163 ++++
 18 files changed, 2733 insertions(+), 129 deletions(-)
 create mode 100644 Documentation/line-range-format.txt
 create mode 100644 line.c
 create mode 100644 line.h
 create mode 100755 t/t4301-log-line-single-history.sh
 create mode 100755 t/t4302-log-line-merge-history.sh

-- 
1.7.2.19.g79e5d

[PATCH V5 01/17] parse-options: enhance STOP_AT_NON_OPTION

[Bo Yang]

Make parse_options_step() report PARSE_OPT_NON_OPTION instead
of PARSE_OPT_DONE to the caller, when it sees a non-option argument.

This will help implementing a nonstandard option syntax that
takes more than one parameters to an option, e.g.

  -L n1,m1 pathspec1 -L n2,m2 pathspec2

by directly calling parse_options_step(). The parse_options() API
only calls parse_options_step() once, and its callers are not affected
by this change.

Thanks-to: Jonathan Nieder <jrnieder@gmail.com>
Signed-off-by: Bo Yang <struggleyb.nku@gmail.com>
---
 parse-options.c |    3 ++-
 parse-options.h |    3 ++-
 2 files changed, 4 insertions(+), 2 deletions(-)

diff --git a/parse-options.c b/parse-options.c
index 0fa79bc..cbb49d3 100644
--- a/parse-options.c
+++ b/parse-options.c
@@ -374,7 +374,7 @@ int parse_options_step(struct parse_opt_ctx_t *ctx,
 			if (parse_nodash_opt(ctx, arg, options) == 0)
 				continue;
 			if (ctx->flags & PARSE_OPT_STOP_AT_NON_OPTION)
-				break;
+				return PARSE_OPT_NON_OPTION;
 			ctx->out[ctx->cpidx++] = ctx->argv[0];
 			continue;
 		}
@@ -456,6 +456,7 @@ int parse_options(int argc, const char **argv, const char *prefix,
 	switch (parse_options_step(&ctx, options, usagestr)) {
 	case PARSE_OPT_HELP:
 		exit(129);
+	case PARSE_OPT_NON_OPTION:
 	case PARSE_OPT_DONE:
 		break;
 	default: /* PARSE_OPT_UNKNOWN */
diff --git a/parse-options.h b/parse-options.h
index 7435cdb..407697a 100644
--- a/parse-options.h
+++ b/parse-options.h
@@ -161,7 +161,8 @@ extern NORETURN void usage_msg_opt(const char *msg,
 enum {
 	PARSE_OPT_HELP = -1,
 	PARSE_OPT_DONE,
-	PARSE_OPT_UNKNOWN
+	PARSE_OPT_NON_OPTION,
+	PARSE_OPT_UNKNOWN,
 };
 
 /*
-- 
1.7.2.19.g79e5d

[PATCH V5 02/17] parse-options: add two helper functions

[Bo Yang]

1. parse_options_current: get the current option/argument the API
   is dealing with;
2. parse_options_next: skip the current argument, moving to the
   next one. Unless 'keep' is set, discard the skipped argument
   from the final argument list.

Signed-off-by: Bo Yang <struggleyb.nku@gmail.com>
---
 parse-options.c |   19 +++++++++++++++++++
 parse-options.h |    4 ++++
 2 files changed, 23 insertions(+), 0 deletions(-)

diff --git a/parse-options.c b/parse-options.c
index cbb49d3..e0c3641 100644
--- a/parse-options.c
+++ b/parse-options.c
@@ -439,6 +439,25 @@ unknown:
 	return PARSE_OPT_DONE;
 }
 
+const char *parse_options_current(struct parse_opt_ctx_t *ctx)
+{
+	return ctx->argv[0];
+}
+
+int parse_options_next(struct parse_opt_ctx_t *ctx, int keep)
+{
+	if (ctx->argc <= 0)
+		return -1;
+
+	if (keep)
+		ctx->out[ctx->cpidx++] = ctx->argv[0];
+
+	ctx->argc--;
+	ctx->argv++;
+
+	return 0;
+}
+
 int parse_options_end(struct parse_opt_ctx_t *ctx)
 {
 	memmove(ctx->out + ctx->cpidx, ctx->argv, ctx->argc * sizeof(*ctx->out));
diff --git a/parse-options.h b/parse-options.h
index 407697a..d3b1932 100644
--- a/parse-options.h
+++ b/parse-options.h
@@ -187,6 +187,10 @@ extern int parse_options_step(struct parse_opt_ctx_t *ctx,
 			      const struct option *options,
 			      const char * const usagestr[]);
 
+extern const char *parse_options_current(struct parse_opt_ctx_t *ctx);
+
+extern int parse_options_next(struct parse_opt_ctx_t *ctx, int keep);
+
 extern int parse_options_end(struct parse_opt_ctx_t *ctx);
 
 extern int parse_options_concat(struct option *dst, size_t, struct option *src);
-- 
1.7.2.19.g79e5d

[PATCH V5 03/17] Add the basic data structure for line level history

[Bo Yang]

'struct diff_line_range' is the main data structure to keep
track of the line ranges we are currently interested in. The
user starts digging from a line range, and after examining the
diff that affects that range by a commit, we can find a new
range that corresponds to this range. So, we will associate this
new range with the commit's parent commit.

There is one 'diff_line_range' for each file, and there are
multiple 'struct line_range' in each 'diff_line_range'. In this way,
we support multiple ranges.

Within 'struct line_range', there are multiple 'struct print_range'
which represent a diff hunk.

Signed-off-by: Bo Yang <struggleyb.nku@gmail.com>
---
 Makefile   |    2 +
 line.c     |  455 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 line.h     |  128 +++++++++++++++++
 revision.h |    8 +-
 4 files changed, 591 insertions(+), 2 deletions(-)
 create mode 100644 line.c
 create mode 100644 line.h

diff --git a/Makefile b/Makefile
index 4179186..c194e79 100644
--- a/Makefile
+++ b/Makefile
@@ -496,6 +496,7 @@ LIB_H += grep.h
 LIB_H += hash.h
 LIB_H += help.h
 LIB_H += levenshtein.h
+LIB_H += line.h
 LIB_H += list-objects.h
 LIB_H += ll-merge.h
 LIB_H += log-tree.h
@@ -582,6 +583,7 @@ LIB_OBJS += help.o
 LIB_OBJS += hex.o
 LIB_OBJS += ident.o
 LIB_OBJS += levenshtein.o
+LIB_OBJS += line.o
 LIB_OBJS += list-objects.o
 LIB_OBJS += ll-merge.o
 LIB_OBJS += lockfile.o
diff --git a/line.c b/line.c
new file mode 100644
index 0000000..e277fa6
--- /dev/null
+++ b/line.c
@@ -0,0 +1,455 @@
+#include "cache.h"
+#include "tag.h"
+#include "blob.h"
+#include "tree.h"
+#include "diff.h"
+#include "commit.h"
+#include "decorate.h"
+#include "revision.h"
+#include "xdiff-interface.h"
+#include "strbuf.h"
+#include "log-tree.h"
+#include "line.h"
+
+static void cleanup(struct diff_line_range *r)
+{
+	while (r) {
+		struct diff_line_range *next = r->next;
+		DIFF_LINE_RANGE_CLEAR(r);
+		free(r);
+		r = next;
+	}
+}
+
+static struct object *verify_commit(struct rev_info *revs)
+{
+	struct object *commit = NULL;
+	int found = -1;
+	int i;
+
+	for (i = 0; i < revs->pending.nr; i++) {
+		struct object *obj = revs->pending.objects[i].item;
+		if (obj->flags & UNINTERESTING)
+			continue;
+		while (obj->type == OBJ_TAG)
+			obj = deref_tag(obj, NULL, 0);
+		if (obj->type != OBJ_COMMIT)
+			die("Non commit %s?", revs->pending.objects[i].name);
+		if (commit)
+			die("More than one commit to dig from: %s and %s?",
+			    revs->pending.objects[i].name,
+				revs->pending.objects[found].name);
+		commit = obj;
+		found = i;
+	}
+
+	if (commit == NULL)
+		die("No commit specified?");
+
+	return commit;
+}
+
+static void fill_blob_sha1(struct commit *commit, struct diff_line_range *r)
+{
+	unsigned mode;
+	unsigned char sha1[20];
+
+	while (r) {
+		if (get_tree_entry(commit->object.sha1, r->spec->path,
+			sha1, &mode))
+			goto error;
+		fill_filespec(r->spec, sha1, mode);
+		r = r->next;
+	}
+
+	return;
+error:
+	die("There is no path %s in the commit", r->spec->path);
+}
+
+static void fill_line_ends(struct diff_filespec *spec, long *lines,
+	unsigned long **line_ends)
+{
+	int num = 0, size = 50;
+	long cur = 0;
+	unsigned long *ends = NULL;
+	char *data = NULL;
+
+	if (diff_populate_filespec(spec, 0))
+		die("Cannot read blob %s", sha1_to_hex(spec->sha1));
+
+	ends = xmalloc(size * sizeof(*ends));
+	ends[cur++] = 0;
+	data = spec->data;
+	while (num < spec->size) {
+		if (data[num] == '\n' || num == spec->size - 1) {
+			ALLOC_GROW(ends, (cur + 1), size);
+			ends[cur++] = num;
+		}
+		num++;
+	}
+
+	/* shrink the array to fit the elements */
+	ends = xrealloc(ends, cur * sizeof(*ends));
+	*lines = cur;
+	*line_ends = ends;
+}
+
+static const char *nth_line(struct diff_filespec *spec, long line,
+		long lines, unsigned long *line_ends)
+{
+	assert(line < lines);
+	assert(spec && spec->data);
+
+	if (line == 0)
+		return (char *)spec->data;
+	else
+		return (char *)spec->data + line_ends[line] + 1;
+}
+
+/*
+ * copied from blame.c, indeed, we can even to use this to test
+ * whether line log works. :)
+ */
+static const char *parse_loc(const char *spec, struct diff_filespec *file,
+			     long lines, unsigned long *line_ends,
+			     long begin, long *ret)
+{
+	char *term;
+	const char *line;
+	long num;
+	int reg_error;
+	regex_t regexp;
+	regmatch_t match[1];
+
+	/* Allow "-L <something>,+20" to mean starting at <something>
+	 * for 20 lines, or "-L <something>,-5" for 5 lines ending at
+	 * <something>.
+	 */
+	if (1 < begin && (spec[0] == '+' || spec[0] == '-')) {
+		num = strtol(spec + 1, &term, 10);
+		if (term != spec + 1) {
+			if (spec[0] == '-')
+				num = 0 - num;
+			if (0 < num)
+				*ret = begin + num - 2;
+			else if (!num)
+				*ret = begin;
+			else
+				*ret = begin + num;
+			return term;
+		}
+		return spec;
+	}
+	num = strtol(spec, &term, 10);
+	if (term != spec) {
+		*ret = num;
+		return term;
+	}
+	if (spec[0] != '/')
+		return spec;
+
+	/* it could be a regexp of form /.../ */
+	for (term = (char *) spec + 1; *term && *term != '/'; term++) {
+		if (*term == '\\')
+			term++;
+	}
+	if (*term != '/')
+		return spec;
+
+	/* try [spec+1 .. term-1] as regexp */
+	*term = 0;
+	begin--; /* input is in human terms */
+	line = nth_line(file, begin, lines, line_ends);
+
+	if (!(reg_error = regcomp(&regexp, spec + 1, REG_NEWLINE)) &&
+	    !(reg_error = regexec(&regexp, line, 1, match, 0))) {
+		const char *cp = line + match[0].rm_so;
+		const char *nline;
+
+		while (begin++ < lines) {
+			nline = nth_line(file, begin, lines, line_ends);
+			if (line <= cp && cp < nline)
+				break;
+			line = nline;
+		}
+		*ret = begin;
+		regfree(&regexp);
+		*term++ = '/';
+		return term;
+	} else {
+		char errbuf[1024];
+		regerror(reg_error, &regexp, errbuf, 1024);
+		die("-L parameter '%s': %s", spec + 1, errbuf);
+	}
+}
+
+static void parse_range(long lines, unsigned long *line_ends,
+		struct line_range *r, struct diff_filespec *spec)
+{
+	const char *term;
+
+	term = parse_loc(r->arg, spec, lines, line_ends, 1, &r->start);
+	if (*term == ',') {
+		term = parse_loc(term + 1, spec, lines, line_ends,
+			r->start + 1, &r->end);
+		if (*term)
+			die("-L parameter's argument should be <start>,<end>");
+	}
+
+	if (*term)
+		die("-L parameter's argument should be <start>,<end>");
+
+	if (r->start > r->end) {
+		long tmp = r->start;
+		r->start = r->end;
+		r->end = tmp;
+	}
+
+	if (r->start < 1)
+		r->start = 1;
+	if (r->end >= lines)
+		r->end = lines - 1;
+}
+
+static void parse_lines(struct commit *commit, struct diff_line_range *r)
+{
+	int i;
+	struct line_range *old_range = NULL;
+	long lines = 0;
+	unsigned long *ends = NULL;
+
+	while (r) {
+		struct diff_filespec *spec = r->spec;
+		int num = r->nr;
+		assert(spec);
+		fill_blob_sha1(commit, r);
+		old_range = r->ranges;
+		r->ranges = NULL;
+		r->nr = r->alloc = 0;
+		fill_line_ends(spec, &lines, &ends);
+		for (i = 0; i < num; i++) {
+			parse_range(lines, ends, old_range + i, spec);
+			diff_line_range_insert(r, old_range[i].arg,
+				old_range[i].start, old_range[i].end);
+		}
+
+		free(ends);
+		ends = NULL;
+
+		r = r->next;
+		free(old_range);
+	}
+}
+
+/*
+ * Insert a new line range into a diff_line_range struct, and keep the
+ * r->ranges sorted by their starting line number.
+ */
+struct line_range *diff_line_range_insert(struct diff_line_range *r,
+		const char *arg, int start, int end)
+{
+	int i = 0;
+	struct line_range *rs = r->ranges;
+	int left_merge = 0, right_merge = 0;
+
+	assert(r != NULL);
+	assert(start <= end);
+
+	if (r->nr == 0 || rs[r->nr - 1].end < start - 1) {
+		int num = 0;
+		DIFF_LINE_RANGE_GROW(r);
+		rs = r->ranges;
+		num = r->nr - 1;
+		rs[num].arg = arg;
+		rs[num].start = start;
+		rs[num].end = end;
+		return rs + num;
+	}
+
+	for (; i < r->nr; i++) {
+		if (rs[i].end < start - 1)
+			continue;
+		if (rs[i].end == start - 1) {
+			rs[i].end = end;
+			right_merge = 1;
+			goto out;
+		}
+
+		assert(rs[i].end > start - 1);
+		if (rs[i].start <= start) {
+			if (rs[i].end < end) {
+				rs[i].end = end;
+				right_merge = 1;
+			}
+			goto out;
+		} else if (rs[i].start <= end + 1) {
+			rs[i].start = start;
+			left_merge = 1;
+			if (rs[i].end < end) {
+				rs[i].end = end;
+				right_merge = 1;
+			}
+			goto out;
+		} else {
+			int num = r->nr - i;
+			DIFF_LINE_RANGE_GROW(r);
+			rs = r->ranges;
+			memmove(rs + i + 1, rs + i, num * sizeof(struct line_range));
+			rs[i].arg = arg;
+			rs[i].start = start;
+			rs[i].end = end;
+			goto out;
+		}
+	}
+
+out:
+	assert(r->nr != i);
+	if (left_merge) {
+		int j = i;
+		for (; j > -1; j--) {
+			if (rs[j].end >= rs[i].start - 1)
+				if (rs[j].start < rs[i].start)
+					rs[i].start = rs[j].start;
+		}
+		memmove(rs + j + 1, rs + i, (r->nr - i) * sizeof(struct line_range));
+		r->nr -= i - j - 1;
+	}
+	if (right_merge) {
+		int j = i;
+		for (; j < r->nr; j++) {
+			if (rs[j].start <= rs[i].end + 1)
+				if (rs[j].end > rs[i].end)
+					rs[i].end = rs[j].end;
+		}
+		if (j < r->nr)
+			memmove(rs + i + 1, rs + j, (r->nr - j) * sizeof(struct line_range));
+		r->nr -= j - i - 1;
+	}
+	assert(r->nr);
+
+	return rs + i;
+}
+
+void diff_line_range_clear(struct diff_line_range *r)
+{
+	int i = 0, zero = 0;
+
+	for (; i < r->nr; i++) {
+		struct line_range *rg = r->ranges + i;
+		RANGE_CLEAR(rg);
+	}
+
+	if (r->prev) {
+		zero = 0;
+		if (r->prev->count == 1)
+			zero = 1;
+		free_filespec(r->prev);
+		if (zero)
+			r->prev = NULL;
+	}
+	if (r->spec) {
+		zero = 0;
+		if (r->spec->count == 1)
+			zero = 1;
+		free_filespec(r->spec);
+		if (zero)
+			r->spec = NULL;
+	}
+
+	r->status = '\0';
+	r->alloc = r->nr = 0;
+
+	if (r->ranges)
+		free(r->ranges);
+	r->ranges = NULL;
+	r->next = NULL;
+}
+
+void diff_line_range_append(struct diff_line_range *r, const char *arg)
+{
+	DIFF_LINE_RANGE_GROW(r);
+	r->ranges[r->nr - 1].arg = arg;
+}
+
+struct diff_line_range *diff_line_range_merge(struct diff_line_range *out,
+		struct diff_line_range *other)
+{
+	struct diff_line_range *one = out, *two = other;
+	struct diff_line_range *pone;
+
+	while (one) {
+		struct diff_line_range *ptwo;
+		two = other;
+		ptwo = other;
+		while (two) {
+			if (!strcmp(one->spec->path, two->spec->path)) {
+				int i = 0;
+				for (; i < two->nr; i++) {
+					diff_line_range_insert(one, NULL,
+						two->ranges[i].start,
+						two->ranges[i].end);
+				}
+				if (two == other)
+					other = other->next;
+				else
+					ptwo->next = two->next;
+				DIFF_LINE_RANGE_CLEAR(two);
+				free(two);
+				two = NULL;
+
+				break;
+			}
+
+			ptwo = two;
+			two = two->next;
+		}
+
+		pone = one;
+		one = one->next;
+	}
+	pone->next = other;
+
+	return out;
+}
+
+void add_line_range(struct rev_info *revs, struct commit *commit,
+		struct diff_line_range *r)
+{
+	struct diff_line_range *ret = NULL;
+
+	if (r != NULL) {
+		ret = lookup_decoration(&revs->line_range, &commit->object);
+		if (ret != NULL)
+			diff_line_range_merge(ret, r);
+		else
+			add_decoration(&revs->line_range, &commit->object, r);
+		commit->object.flags |= RANGE_UPDATE;
+	}
+}
+
+struct diff_line_range *lookup_line_range(struct rev_info *revs,
+		struct commit *commit)
+{
+	struct diff_line_range *ret = NULL;
+
+	ret = lookup_decoration(&revs->line_range, &commit->object);
+	return ret;
+}
+
+void setup_line(struct rev_info *rev, struct diff_line_range *r)
+{
+	struct commit *commit = NULL;
+	struct diff_options *opt = &rev->diffopt;
+
+	commit = (struct commit *)verify_commit(rev);
+	parse_lines(commit, r);
+
+	add_line_range(rev, commit, r);
+	/*
+	 * Note we support -M/-C to detect file rename
+	 */
+	opt->nr_paths = 0;
+	diff_tree_release_paths(opt);
+}
+
diff --git a/line.h b/line.h
new file mode 100644
index 0000000..a04af86
--- /dev/null
+++ b/line.h
@@ -0,0 +1,128 @@
+#ifndef LINE_H
+#define LINE_H
+
+#include "diffcore.h"
+
+struct rev_info;
+struct commit;
+struct diff_line_range;
+struct diff_options;
+
+struct print_range {
+	int start, end;		/* Line range of post-image */
+	int pstart, pend;	/* Line range of pre-image */
+	int line_added : 1;	/* whether this range is added */
+};
+
+struct print_pair {
+	int alloc, nr;
+	struct print_range *ranges;
+};
+
+#define PRINT_RANGE_INIT(r) \
+	do { \
+		(r)->start = (r)->end = 0; \
+		(r)->pstart = (r)->pend = 0; \
+		(r)->line_added = 0; \
+	} while (0)
+
+#define PRINT_PAIR_INIT(p) \
+	do { \
+		(p)->alloc = (p)->nr = 0; \
+		(p)->ranges = NULL; \
+	} while (0)
+
+#define PRINT_PAIR_GROW(p) \
+	do { \
+		(p)->nr++; \
+		ALLOC_GROW((p)->ranges, (p)->nr, (p)->alloc); \
+	} while (0)
+
+#define PRINT_PAIR_CLEAR(p) \
+	do { \
+		(p)->alloc = (p)->nr = 0; \
+		if ((p)->ranges) \
+			free((p)->ranges); \
+		(p)->ranges = NULL; \
+	} while (0)
+
+struct line_range {
+	const char *arg;	/* The argument to specify this line range */
+	long start, end;	/* The interesting line range of current commit */
+	long pstart, pend;	/* The corresponding range of parent commit */
+	struct print_pair pair;
+			/* The changed lines inside this range */
+	unsigned int diff:1;
+};
+
+struct diff_line_range {
+	struct diff_filespec *prev;
+	struct diff_filespec *spec;
+	char status;
+	int alloc;
+	int nr;
+	struct line_range *ranges;
+	unsigned int	touch:1,
+			diff:1;
+	struct diff_line_range *next;
+};
+
+#define RANGE_INIT(r) \
+	do { \
+		(r)->arg = NULL; \
+		(r)->start = (r)->end = 0; \
+		(r)->pstart = (r)->pend = 0; \
+		PRINT_PAIR_INIT(&((r)->pair)); \
+		(r)->diff = 0; \
+	} while (0)
+
+#define RANGE_CLEAR(r) \
+	do { \
+		(r)->arg = NULL; \
+		(r)->start = (r)->end = 0; \
+		(r)->pstart = (r)->pend = 0; \
+		PRINT_PAIR_CLEAR(&r->pair); \
+		(r)->diff = 0; \
+	} while (0)
+
+#define DIFF_LINE_RANGE_INIT(r) \
+	do { \
+		(r)->prev = (r)->spec = NULL; \
+		(r)->status = '\0'; \
+		(r)->alloc = (r)->nr = 0; \
+		(r)->ranges = NULL; \
+		(r)->next = NULL; \
+		(r)->touch = 0; \
+		(r)->diff = 0; \
+	} while (0)
+
+#define DIFF_LINE_RANGE_GROW(r) \
+	do { \
+		(r)->nr++; \
+		ALLOC_GROW((r)->ranges, (r)->nr, (r)->alloc); \
+		RANGE_INIT(((r)->ranges + (r)->nr - 1)); \
+	} while (0)
+
+#define DIFF_LINE_RANGE_CLEAR(r) \
+	diff_line_range_clear((r));
+
+extern struct line_range *diff_line_range_insert(struct diff_line_range *r,
+		const char *arg, int start, int end);
+
+extern void diff_line_range_append(struct diff_line_range *r, const char *arg);
+
+extern void diff_line_range_clear(struct diff_line_range *r);
+
+extern struct diff_line_range *diff_line_range_merge(
+		struct diff_line_range *out,
+		struct diff_line_range *other);
+
+extern void setup_line(struct rev_info *rev, struct diff_line_range *r);
+
+extern void add_line_range(struct rev_info *revs, struct commit *commit,
+		struct diff_line_range *r);
+
+extern struct diff_line_range *lookup_line_range(struct rev_info *revs,
+		struct commit *commit);
+
+#endif
diff --git a/revision.h b/revision.h
index 36fdf22..c0d5065 100644
--- a/revision.h
+++ b/revision.h
@@ -14,7 +14,8 @@
 #define CHILD_SHOWN	(1u<<6)
 #define ADDED		(1u<<7)	/* Parents already parsed and added? */
 #define SYMMETRIC_LEFT	(1u<<8)
-#define ALL_REV_FLAGS	((1u<<9)-1)
+#define RANGE_UPDATE	(1u<<9) /* for line level traverse */
+#define ALL_REV_FLAGS	((1u<<10)-1)
 
 #define DECORATE_SHORT_REFS	1
 #define DECORATE_FULL_REFS	2
@@ -68,7 +69,8 @@ struct rev_info {
 			cherry_pick:1,
 			bisect:1,
 			ancestry_path:1,
-			first_parent_only:1;
+			first_parent_only:1,
+			line_level_traverse:1;
 
 	/* Diff flags */
 	unsigned int	diff:1,
@@ -137,6 +139,8 @@ struct rev_info {
 	/* commit counts */
 	int count_left;
 	int count_right;
+	/* line level range that we are chasing */
+	struct decoration line_range;
 };
 
 #define REV_TREE_SAME		0
-- 
1.7.2.19.g79e5d

[PATCH V5 04/17] Refactor parse_loc

[Bo Yang]

Both 'git blame -L' and 'git log -L' parse the same style
of line number arguments, so put the 'parse_loc' function
to line.c and export it.

The caller of parse_loc should provide a callback function
which is used to calculate the start position of the nth line.
Other parts such as regexp search, line number parsing are
abstracted and re-used.

Note that, we can use '$' to specify the last line of a file.

Signed-off-by: Bo Yang <struggleyb.nku@gmail.com>
---
 builtin/blame.c |   89 +++++-------------------------------------------------
 line.c          |   52 ++++++++++++++++++++------------
 line.h          |    5 +++
 3 files changed, 46 insertions(+), 100 deletions(-)

diff --git a/builtin/blame.c b/builtin/blame.c
index 01e62fd..17b71cd 100644
--- a/builtin/blame.c
+++ b/builtin/blame.c
@@ -21,6 +21,7 @@
 #include "parse-options.h"
 #include "utf8.h"
 #include "userdiff.h"
+#include "line.h"
 
 static char blame_usage[] = "git blame [options] [rev-opts] [rev] [--] file";
 
@@ -541,11 +542,16 @@ static void dup_entry(struct blame_entry *dst, struct blame_entry *src)
 	dst->score = 0;
 }
 
-static const char *nth_line(struct scoreboard *sb, int lno)
+static const char *nth_line(struct scoreboard *sb, long lno)
 {
 	return sb->final_buf + sb->lineno[lno];
 }
 
+static const char *nth_line_cb(void *data, long lno)
+{
+	return nth_line((struct scoreboard *)data, lno);
+}
+
 /*
  * It is known that lines between tlno to same came from parent, and e
  * has an overlap with that range.  it also is known that parent's
@@ -1907,83 +1913,6 @@ static const char *add_prefix(const char *prefix, const char *path)
 }
 
 /*
- * Parsing of (comma separated) one item in the -L option
- */
-static const char *parse_loc(const char *spec,
-			     struct scoreboard *sb, long lno,
-			     long begin, long *ret)
-{
-	char *term;
-	const char *line;
-	long num;
-	int reg_error;
-	regex_t regexp;
-	regmatch_t match[1];
-
-	/* Allow "-L <something>,+20" to mean starting at <something>
-	 * for 20 lines, or "-L <something>,-5" for 5 lines ending at
-	 * <something>.
-	 */
-	if (1 < begin && (spec[0] == '+' || spec[0] == '-')) {
-		num = strtol(spec + 1, &term, 10);
-		if (term != spec + 1) {
-			if (spec[0] == '-')
-				num = 0 - num;
-			if (0 < num)
-				*ret = begin + num - 2;
-			else if (!num)
-				*ret = begin;
-			else
-				*ret = begin + num;
-			return term;
-		}
-		return spec;
-	}
-	num = strtol(spec, &term, 10);
-	if (term != spec) {
-		*ret = num;
-		return term;
-	}
-	if (spec[0] != '/')
-		return spec;
-
-	/* it could be a regexp of form /.../ */
-	for (term = (char *) spec + 1; *term && *term != '/'; term++) {
-		if (*term == '\\')
-			term++;
-	}
-	if (*term != '/')
-		return spec;
-
-	/* try [spec+1 .. term-1] as regexp */
-	*term = 0;
-	begin--; /* input is in human terms */
-	line = nth_line(sb, begin);
-
-	if (!(reg_error = regcomp(&regexp, spec + 1, REG_NEWLINE)) &&
-	    !(reg_error = regexec(&regexp, line, 1, match, 0))) {
-		const char *cp = line + match[0].rm_so;
-		const char *nline;
-
-		while (begin++ < lno) {
-			nline = nth_line(sb, begin);
-			if (line <= cp && cp < nline)
-				break;
-			line = nline;
-		}
-		*ret = begin;
-		regfree(&regexp);
-		*term++ = '/';
-		return term;
-	}
-	else {
-		char errbuf[1024];
-		regerror(reg_error, &regexp, errbuf, 1024);
-		die("-L parameter '%s': %s", spec + 1, errbuf);
-	}
-}
-
-/*
  * Parsing of -L option
  */
 static void prepare_blame_range(struct scoreboard *sb,
@@ -1993,9 +1922,9 @@ static void prepare_blame_range(struct scoreboard *sb,
 {
 	const char *term;
 
-	term = parse_loc(bottomtop, sb, lno, 1, bottom);
+	term = parse_loc(bottomtop, nth_line_cb, sb, lno, 1, bottom);
 	if (*term == ',') {
-		term = parse_loc(term + 1, sb, lno, *bottom + 1, top);
+		term = parse_loc(term + 1, nth_line_cb, sb, lno, *bottom + 1, top);
 		if (*term)
 			usage(blame_usage);
 	}
diff --git a/line.c b/line.c
index e277fa6..6c5f69e 100644
--- a/line.c
+++ b/line.c
@@ -95,25 +95,29 @@ static void fill_line_ends(struct diff_filespec *spec, long *lines,
 	*line_ends = ends;
 }
 
-static const char *nth_line(struct diff_filespec *spec, long line,
-		long lines, unsigned long *line_ends)
+struct nth_line_cb {
+	struct diff_filespec *spec;
+	long lines;
+	unsigned long *line_ends;
+};
+
+static const char *nth_line(void *data, long line)
 {
-	assert(line < lines);
-	assert(spec && spec->data);
+	struct nth_line_cb *d = data;
+	assert(d && line < d->lines);
+	assert(d->spec && d->spec->data);
 
 	if (line == 0)
-		return (char *)spec->data;
+		return (char *)d->spec->data;
 	else
-		return (char *)spec->data + line_ends[line] + 1;
+		return (char *)d->spec->data + d->line_ends[line] + 1;
 }
 
 /*
- * copied from blame.c, indeed, we can even to use this to test
- * whether line log works. :)
+ * Parsing of (comma separated) one item in the -L option
  */
-static const char *parse_loc(const char *spec, struct diff_filespec *file,
-			     long lines, unsigned long *line_ends,
-			     long begin, long *ret)
+const char *parse_loc(const char *spec, nth_line_fn_t nth_line,
+		void *data, long lines, long begin, long *ret)
 {
 	char *term;
 	const char *line;
@@ -122,6 +126,13 @@ static const char *parse_loc(const char *spec, struct diff_filespec *file,
 	regex_t regexp;
 	regmatch_t match[1];
 
+	/* Catch the '$' matcher, now it is used to match the last
+	 * line of the file. */
+	if (spec[0] == '$') {
+		*ret = lines;
+		return spec + 1;
+	}
+
 	/* Allow "-L <something>,+20" to mean starting at <something>
 	 * for 20 lines, or "-L <something>,-5" for 5 lines ending at
 	 * <something>.
@@ -160,7 +171,7 @@ static const char *parse_loc(const char *spec, struct diff_filespec *file,
 	/* try [spec+1 .. term-1] as regexp */
 	*term = 0;
 	begin--; /* input is in human terms */
-	line = nth_line(file, begin, lines, line_ends);
+	line = nth_line(data, begin);
 
 	if (!(reg_error = regcomp(&regexp, spec + 1, REG_NEWLINE)) &&
 	    !(reg_error = regexec(&regexp, line, 1, match, 0))) {
@@ -168,7 +179,7 @@ static const char *parse_loc(const char *spec, struct diff_filespec *file,
 		const char *nline;
 
 		while (begin++ < lines) {
-			nline = nth_line(file, begin, lines, line_ends);
+			nline = nth_line(data, begin);
 			if (line <= cp && cp < nline)
 				break;
 			line = nline;
@@ -188,10 +199,11 @@ static void parse_range(long lines, unsigned long *line_ends,
 		struct line_range *r, struct diff_filespec *spec)
 {
 	const char *term;
+	struct nth_line_cb data = {spec, lines, line_ends};
 
-	term = parse_loc(r->arg, spec, lines, line_ends, 1, &r->start);
+	term = parse_loc(r->arg, nth_line, &data, lines - 1, 1, &r->start);
 	if (*term == ',') {
-		term = parse_loc(term + 1, spec, lines, line_ends,
+		term = parse_loc(term + 1, nth_line, &data, lines - 1,
 			r->start + 1, &r->end);
 		if (*term)
 			die("-L parameter's argument should be <start>,<end>");
@@ -200,16 +212,16 @@ static void parse_range(long lines, unsigned long *line_ends,
 	if (*term)
 		die("-L parameter's argument should be <start>,<end>");
 
+	if (r->start < 1)
+		r->start = 1;
+	if (r->end >= lines)
+		r->end = lines - 1;
+
 	if (r->start > r->end) {
 		long tmp = r->start;
 		r->start = r->end;
 		r->end = tmp;
 	}
-
-	if (r->start < 1)
-		r->start = 1;
-	if (r->end >= lines)
-		r->end = lines - 1;
 }
 
 static void parse_lines(struct commit *commit, struct diff_line_range *r)
diff --git a/line.h b/line.h
index a04af86..5bde828 100644
--- a/line.h
+++ b/line.h
@@ -8,6 +8,8 @@ struct commit;
 struct diff_line_range;
 struct diff_options;
 
+typedef const char *(*nth_line_fn_t)(void *data, long lno);
+
 struct print_range {
 	int start, end;		/* Line range of post-image */
 	int pstart, pend;	/* Line range of pre-image */
@@ -125,4 +127,7 @@ extern void add_line_range(struct rev_info *revs, struct commit *commit,
 extern struct diff_line_range *lookup_line_range(struct rev_info *revs,
 		struct commit *commit);
 
+const char *parse_loc(const char *spec, nth_line_fn_t nth_line,
+		void *data, long lines, long begin, long *ret);
+
 #endif
-- 
1.7.2.19.g79e5d

[PATCH V5 05/17] Parse the -L options

[Bo Yang]

With the two new APIs of parse options added in the previous
commit, we parse the multiple '-L n,m <pathspec>' syntax.

Notice that users can give more than one '-L n,m' for each pathspec.
And a pathspec with all its '-L' options maps to a single
diff_line_range structure.

This has the exactly the same semantics as 'git blame -L n,m <pathspec>'
because we refactored and reused the blame code.

Signed-off-by: Bo Yang <struggleyb.nku@gmail.com>
---
 builtin/log.c |  102 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 101 insertions(+), 1 deletions(-)

diff --git a/builtin/log.c b/builtin/log.c
index 08b8722..e7c5111 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -19,6 +19,7 @@
 #include "remote.h"
 #include "string-list.h"
 #include "parse-options.h"
+#include "line.h"
 
 /* Set a default date-time format for git log ("log.date" config variable) */
 static const char *default_date_mode = NULL;
@@ -27,11 +28,24 @@ static int default_show_root = 1;
 static int decoration_style;
 static const char *fmt_patch_subject_prefix = "PATCH";
 static const char *fmt_pretty;
+static const char *dashdash = "--";
 
-static const char * const builtin_log_usage =
+static char builtin_log_usage[] =
 	"git log [<options>] [<since>..<until>] [[--] <path>...]\n"
+	"git log [<options>] -L n,m <path>\n"
 	"   or: git show [options] <object>...";
 
+static const char *log_opt_usage[] = {
+	builtin_log_usage,
+	NULL
+};
+
+struct line_opt_callback_data {
+	struct diff_line_range **range;
+	struct parse_opt_ctx_t *ctx;
+	struct rev_info *rev;
+};
+
 static int parse_decoration_style(const char *var, const char *value)
 {
 	switch (git_config_maybe_bool(var, value)) {
@@ -49,12 +63,44 @@ static int parse_decoration_style(const char *var, const char *value)
 	return -1;
 }
 
+static int log_line_range_callback(const struct option *option, const char *arg, int unset)
+{
+	struct line_opt_callback_data *data = option->value;
+	struct diff_line_range *r = *data->range;
+	struct parse_opt_ctx_t *ctx = data->ctx;
+
+	if (!arg)
+		return -1;
+
+	if (r->nr == 0 && r->next == NULL)
+		ctx->out[ctx->cpidx++] = dashdash;
+
+	diff_line_range_append(r, arg);
+	data->rev->line_level_traverse = 1;
+	return 0;
+}
+
 static void cmd_log_init(int argc, const char **argv, const char *prefix,
 			 struct rev_info *rev, struct setup_revision_opt *opt)
 {
 	int i;
 	int decoration_given = 0;
 	struct userformat_want w;
+	const char *path = NULL, *fullpath = NULL;
+	static struct diff_line_range *range;
+	struct diff_line_range *r = NULL;
+	static struct parse_opt_ctx_t ctx;
+	static struct line_opt_callback_data line_cb = {&range, &ctx, NULL};
+	static const struct option options[] = {
+		OPT_CALLBACK('L', NULL, &line_cb, "n,m",
+			     "Process only line range n,m, counting from 1",
+			     log_line_range_callback),
+		OPT_END()
+	};
+
+	line_cb.rev = rev;
+	range = xmalloc(sizeof(*range));
+	DIFF_LINE_RANGE_INIT(range);
 
 	rev->abbrev = DEFAULT_ABBREV;
 	rev->commit_format = CMIT_FMT_DEFAULT;
@@ -75,6 +121,56 @@ static void cmd_log_init(int argc, const char **argv, const char *prefix,
 	 */
 	if (argc == 2 && !strcmp(argv[1], "-h"))
 		usage(builtin_log_usage);
+
+	parse_options_start(&ctx, argc, argv, prefix, PARSE_OPT_KEEP_DASHDASH |
+			PARSE_OPT_KEEP_ARGV0 | PARSE_OPT_STOP_AT_NON_OPTION);
+	for (;;) {
+		switch (parse_options_step(&ctx, options, log_opt_usage)) {
+		case PARSE_OPT_HELP:
+			exit(129);
+		case PARSE_OPT_DONE:
+			goto parse_done;
+		case PARSE_OPT_NON_OPTION:
+			path = parse_options_current(&ctx);
+			fullpath = prefix_path(prefix, prefix ? strlen(prefix) : 0, path);
+			range->spec = alloc_filespec(fullpath);
+			free((void *)fullpath);
+			if (range->nr == 0) {
+				if (range->next) {
+					die("Path %s need a -L <range> option\n"
+					"If you want follow the history of the whole file "
+					"use 'git log -L 1,$ <path>'", range->spec->path);
+				} else {
+					parse_options_next(&ctx, 1);
+					continue;
+				}
+			}
+			r = xmalloc(sizeof(*r));
+			DIFF_LINE_RANGE_INIT(r);
+			r->next = range;
+			range = r;
+			parse_options_next(&ctx, 1);
+			continue;
+		case PARSE_OPT_UNKNOWN:
+			parse_options_next(&ctx, 1);
+			continue;
+		}
+
+		parse_revision_opt(rev, &ctx, options, log_opt_usage);
+	}
+parse_done:
+	argc = parse_options_end(&ctx);
+
+	/* die if '-L <range>' with no pathspec follow */
+	if (range->nr > 0 && range->spec == NULL)
+		die("Each -L should follow a path");
+	/* clear up the last range */
+	if (range->nr == 0) {
+		struct diff_line_range *r = range->next;
+		DIFF_LINE_RANGE_CLEAR(range);
+		range = r;
+	}
+
 	argc = setup_revisions(argc, argv, rev, opt);
 
 	memset(&w, 0, sizeof(w));
@@ -125,6 +221,10 @@ static void cmd_log_init(int argc, const char **argv, const char *prefix,
 		rev->show_decorations = 1;
 		load_ref_decorations(decoration_style);
 	}
+
+	/* Test whether line level history is asked for */
+	if (range && range->nr > 0)
+		setup_line(rev, range);
 }
 
 /*
-- 
1.7.2.19.g79e5d

[PATCH V5 06/17] Export three functions from diff.c

[Bo Yang]

Use fill_metainfo to fill the line level diff meta data,
emit_line to print out a line and quote_two to quote
paths.

Signed-off-by: Bo Yang <struggleyb.nku@gmail.com>
---
 diff.c |    6 +++---
 diff.h |   17 +++++++++++++++++
 2 files changed, 20 insertions(+), 3 deletions(-)

diff --git a/diff.c b/diff.c
index 17873f3..9efca95 100644
--- a/diff.c
+++ b/diff.c
@@ -144,7 +144,7 @@ int git_diff_basic_config(const char *var, const char *value, void *cb)
 	return git_color_default_config(var, value, cb);
 }
 
-static char *quote_two(const char *one, const char *two)
+char *quote_two(const char *one, const char *two)
 {
 	int need_one = quote_c_style(one, NULL, NULL, 1);
 	int need_two = quote_c_style(two, NULL, NULL, 1);
@@ -325,7 +325,7 @@ static void emit_line_0(struct diff_options *o, const char *set, const char *res
 		fputc('\n', file);
 }
 
-static void emit_line(struct diff_options *o, const char *set, const char *reset,
+void emit_line(struct diff_options *o, const char *set, const char *reset,
 		      const char *line, int len)
 {
 	emit_line_0(o, set, reset, line[0], line+1, len-1);
@@ -2564,7 +2564,7 @@ static int similarity_index(struct diff_filepair *p)
 	return p->score * 100 / MAX_SCORE;
 }
 
-static void fill_metainfo(struct strbuf *msg,
+void fill_metainfo(struct strbuf *msg,
 			  const char *name,
 			  const char *other,
 			  struct diff_filespec *one,
diff --git a/diff.h b/diff.h
index 063d10a..9676ab9 100644
--- a/diff.h
+++ b/diff.h
@@ -12,6 +12,7 @@ struct diff_queue_struct;
 struct strbuf;
 struct diff_filespec;
 struct userdiff_driver;
+struct diff_filepair;
 
 typedef void (*change_fn_t)(struct diff_options *options,
 		 unsigned old_mode, unsigned new_mode,
@@ -301,4 +302,20 @@ extern size_t fill_textconv(struct userdiff_driver *driver,
 
 extern struct userdiff_driver *get_textconv(struct diff_filespec *one);
 
+/* some output functions line.c need */
+extern void fill_metainfo(struct strbuf *msg,
+			  const char *name,
+			  const char *other,
+			  struct diff_filespec *one,
+			  struct diff_filespec *two,
+			  struct diff_options *o,
+			  struct diff_filepair *p,
+			  int *must_show_header,
+			  int use_color);
+
+extern void emit_line(struct diff_options *o, const char *set, const char *reset,
+		      const char *line, int len);
+
+extern char *quote_two(const char *one, const char *two);
+
 #endif /* DIFF_H */
-- 
1.7.2.19.g79e5d

[PATCH V5 07/17] Add range clone functions

[Bo Yang]

Since diff_line_range can form a single list through its
'next' pointer, we provide two kind of clone.

diff_line_range_clone:
	used to clone only the element node and set the
	element's 'next' pointer to NULL.
diff_line_range_clone_deeply:
	used to clone the whole list of ranges.

Signed-off-by: Bo Yang <struggleyb.nku@gmail.com>
---
 line.c |   39 +++++++++++++++++++++++++++++++++++++++
 line.h |    4 ++++
 2 files changed, 43 insertions(+), 0 deletions(-)

diff --git a/line.c b/line.c
index 6c5f69e..1b77172 100644
--- a/line.c
+++ b/line.c
@@ -384,6 +384,45 @@ void diff_line_range_append(struct diff_line_range *r, const char *arg)
 	r->ranges[r->nr - 1].arg = arg;
 }
 
+struct diff_line_range *diff_line_range_clone(struct diff_line_range *r)
+{
+	struct diff_line_range *ret = xmalloc(sizeof(*ret));
+	int i = 0;
+
+	DIFF_LINE_RANGE_INIT(ret);
+	ret->ranges = xcalloc(r->nr, sizeof(struct line_range));
+	memcpy(ret->ranges, r->ranges, sizeof(struct line_range) * r->nr);
+
+	ret->alloc = ret->nr = r->nr;
+
+	for (; i < ret->nr; i++)
+		PRINT_PAIR_INIT(&ret->ranges[i].pair);
+
+	ret->spec = r->spec;
+	assert(ret->spec);
+	ret->spec->count++;
+
+	return ret;
+}
+
+struct diff_line_range *diff_line_range_clone_deeply(struct diff_line_range *r)
+{
+	struct diff_line_range *ret = NULL;
+	struct diff_line_range *tmp = NULL, *prev = NULL;
+
+	assert(r);
+	ret = tmp = prev = diff_line_range_clone(r);
+	r = r->next;
+	while (r) {
+		tmp = diff_line_range_clone(r);
+		prev->next = tmp;
+		prev = tmp;
+		r = r->next;
+	}
+
+	return ret;
+}
+
 struct diff_line_range *diff_line_range_merge(struct diff_line_range *out,
 		struct diff_line_range *other)
 {
diff --git a/line.h b/line.h
index 5bde828..e03eff0 100644
--- a/line.h
+++ b/line.h
@@ -119,6 +119,10 @@ extern struct diff_line_range *diff_line_range_merge(
 		struct diff_line_range *out,
 		struct diff_line_range *other);
 
+extern struct diff_line_range *diff_line_range_clone(struct diff_line_range *r);
+
+extern struct diff_line_range *diff_line_range_clone_deeply(struct diff_line_range *r);
+
 extern void setup_line(struct rev_info *rev, struct diff_line_range *r);
 
 extern void add_line_range(struct rev_info *revs, struct commit *commit,
-- 
1.7.2.19.g79e5d

[PATCH V5 08/17] map/take range to the parent of commits

[Bo Yang]

When going from a commit to its parents, we map the "interesting"
range of lines according to the change made.
For non-merge commit, we just run map_range on the ranges, which
works as follows:

1. Run diffcore_std to find out the pre/postimage for each file.
2. Run xdi_diff_hunks on each interesting set of pre/postimages.
3. The map_range_cb callback is invoked for each hunk by the diff
   engine, and we use it to calculate the pre-image range from the
   post-image range in the function map_lines.

For merge commits, we run map_range once for every parent.
Simultaneously we use a take_range pass to eliminate all ranges
that are identical. If any ranges remain after that, then the
merge is considered non-trivial.

The algorithm that maps lines from post-image to pre-image is in
the function map_lines. Generally, we use simple line number
calculation method to do the map.

Signed-off-by: Bo Yang <struggleyb.nku@gmail.com>
---
 line.c     |  502 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 revision.h |    5 +-
 2 files changed, 506 insertions(+), 1 deletions(-)

diff --git a/line.c b/line.c
index 1b77172..ae52832 100644
--- a/line.c
+++ b/line.c
@@ -504,3 +504,505 @@ void setup_line(struct rev_info *rev, struct diff_line_range *r)
 	diff_tree_release_paths(opt);
 }
 
+struct take_range_cb_data {
+	struct diff_line_range *interesting;	/* currently interesting ranges */
+	struct diff_line_range *range;
+		/* the ranges corresponds to the interesting ranges of parent commit */
+	long plno, tlno;
+		/* the last line number of diff hunk */
+	int diff;
+		/* whether there is some line changes between the current
+		 * commit and its parent */
+};
+
+#define SCALE_FACTOR 4
+/*
+ * [p_start, p_end] represents the pre-image of current diff hunk,
+ * [t_start, t_end] represents the post-image of the current diff hunk,
+ * [start, end] represents the currently interesting line range in
+ * post-image,
+ * [o_start, o_end] represents the original line range that coresponds
+ * to current line range.
+ */
+void map_lines(long p_start, long p_end, long t_start, long t_end,
+		long start, long end, long *o_start, long *o_end)
+{
+	/*
+	 * Normally, p_start should be less than p_end, so does the
+	 * t_start and t_end. But when the line range is added from
+	 * scratch, p_start will be greater than p_end. When the line
+	 * range is deleted, t_start will be greater than t_end.
+	 */
+	if (p_start > p_end) {
+		*o_start = *o_end = 0;
+		return;
+	}
+	/* A deletion */
+	if (t_start > t_end) {
+		*o_start = p_start;
+		*o_end = p_end;
+		return;
+	}
+
+	if (start == t_start && end == t_end) {
+		*o_start = p_start;
+		*o_end = p_end;
+		return;
+	}
+
+	/*
+	 * A heuristic for lines mapping:
+	 *
+	 * When the pre-image is no more than 1/SCALE_FACTOR of the post-image,
+	 * there is no effective way to find out which part of pre-image
+	 * corresponds to the currently interesting range of post-image.
+	 * And we are in the danger of tracking totally useless lines.
+	 * So, we just treat all the post-image lines as added from scratch.
+	 */
+	if (SCALE_FACTOR * (p_end - p_start + 1) < (t_end - t_start + 1)) {
+		*o_start = *o_end = 0;
+		return;
+	}
+
+	*o_start = p_start + start - t_start;
+	*o_end = p_end - (t_end - end);
+
+	if (*o_start > *o_end) {
+		int temp = *o_start;
+		*o_start = *o_end;
+		*o_end = temp;
+	}
+
+	if (*o_start < p_start)
+		*o_start = p_start;
+	if (*o_end > p_end)
+		*o_end = p_end;
+}
+
+/*
+ * When same == 1:
+ * [p_start, p_end] represents the diff hunk line range of pre-image,
+ * [t_start, t_end] represents the diff hunk line range of post-image.
+ * When same == 0, they represent a range of identical lines between
+ * two images.
+ *
+ * This function find out the corresponding line ranges of currently
+ * interesting ranges which this diff hunk touches.
+ */
+static void map_range(struct take_range_cb_data *data, int same,
+		long p_start, long p_end, long t_start, long t_end)
+{
+	struct line_range *ranges = data->interesting->ranges;
+	long takens, takene, start, end;
+	int i = 0, out = 0, added = 0;
+	long op_start = p_start, op_end = p_end, ot_start = t_start, ot_end = t_end;
+
+	for (; i < data->interesting->nr; i++) {
+		added = 0;
+		if (t_start > ranges[i].end)
+			continue;
+		if (t_end < ranges[i].start)
+			break;
+
+		if (t_start > ranges[i].start) {
+			start = t_start;
+			takens = p_start;
+			if (t_end >= ranges[i].end) {
+				end = ranges[i].end;
+				takene = p_start + end - t_start;
+			} else {
+				end = t_end;
+				takene = p_end;
+				out = 1;
+			}
+		} else {
+			start = ranges[i].start;
+			takens = p_start + start - t_start;
+			if (t_end >= ranges[i].end) {
+				end = ranges[i].end;
+				takene = p_start + end - t_start;
+			} else {
+				end = t_end;
+				takene = p_end;
+				out = 1;
+			}
+		}
+
+		if (!same) {
+			struct print_pair *pair = &ranges[i].pair;
+			struct print_range *rr = NULL;
+			PRINT_PAIR_GROW(pair);
+			rr = pair->ranges + pair->nr - 1;
+			PRINT_RANGE_INIT(rr);
+			rr->start = start;
+			rr->end = end;
+			map_lines(op_start, op_end, ot_start, ot_end, start, end,
+					&takens, &takene);
+			if (takens == 0 && takene == 0) {
+				added = 1;
+				rr->line_added = 1;
+			}
+			rr->pstart = takens;
+			rr->pend = takene;
+			data->diff = 1;
+			data->interesting->diff = 1;
+			ranges[i].diff = 1;
+		}
+		if (added) {
+			/* Code movement/copy detect here, now place two dummy statements here */
+			int dummy = 0;
+			dummy = 1;
+		} else {
+			struct line_range *added_range = diff_line_range_insert(data->range,
+					NULL, takens, takene);
+			assert(added_range);
+			ranges[i].pstart = added_range->start;
+			ranges[i].pend = added_range->end;
+		}
+
+		t_start = end + 1;
+		p_start = takene + 1;
+
+		if (out)
+			break;
+	}
+}
+
+/*
+ * [p_start, p_end] represents the line range of pre-image,
+ * [t_start, t_end] represents the line range of post-image,
+ * and they are identical lines.
+ *
+ * This function substracts out the identical lines between current
+ * commit and its parent, from currently interesting ranges.
+ */
+static void take_range(struct take_range_cb_data *data,
+		long p_start, long p_end, long t_start, long t_end)
+{
+	struct line_range *ranges = data->interesting->ranges;
+	long takens, takene, start, end;
+	int i = 0, out = 0, added = 0;
+
+	for (; i < data->interesting->nr; i++) {
+		added = 0;
+		if (t_start > ranges[i].end)
+			continue;
+		if (t_end < ranges[i].start)
+			break;
+
+		if (t_start > ranges[i].start) {
+			long tmp = ranges[i].end;
+			ranges[i].end = t_start - 1;
+			start = t_start;
+			takens = p_start;
+			if (t_end >= tmp) {
+				end = tmp;
+				takene = p_start + end - t_start;
+				p_start = takene + 1;
+				t_start = end + 1;
+			} else {
+				end = t_end;
+				takene = p_end;
+				diff_line_range_insert(data->interesting, NULL,
+					t_end + 1, tmp);
+				out = 1;
+			}
+		} else {
+			start = ranges[i].start;
+			takens = p_start + start - t_start;
+			if (t_end >= ranges[i].end) {
+				int num = data->interesting->nr - 1;
+				end = ranges[i].end;
+				takene = p_start + end - t_start;
+				t_start = end + 1;
+				p_start = takene + 1;
+				memmove(ranges + i, ranges + i + 1, (num - i) * sizeof(*ranges));
+				data->interesting->nr = num;
+				i--;
+			} else {
+				end = t_end;
+				takene = p_end;
+				ranges[i].start = t_end + 1;
+				out = 1;
+			}
+		}
+
+		diff_line_range_insert(data->range, NULL, takens, takene);
+
+		if (out)
+			break;
+	}
+}
+
+static void take_range_cb(void *data, long same, long p_next, long t_next)
+{
+	struct take_range_cb_data *d = data;
+	long p_start = d->plno + 1, t_start = d->tlno + 1;
+	long p_end = p_start + same - t_start, t_end = same;
+
+	/* If one file is added from scratch, we should not bother to call
+	 * take_range, since there is nothing to take
+	 */
+	if (t_end >= t_start)
+		take_range(d, p_start, p_end, t_start, t_end);
+	d->plno = p_next;
+	d->tlno = t_next;
+}
+
+static void map_range_cb(void *data, long same, long p_next, long t_next)
+{
+	struct take_range_cb_data *d = data;
+
+	long p_start = d->plno + 1;
+	long t_start = d->tlno + 1;
+	long p_end = same - t_start + p_start;
+	long t_end = same;
+
+	/* Firstly, take the unchanged lines from child */
+	if (t_end >= t_start)
+		map_range(d, 1, p_start, p_end, t_start, t_end);
+
+	/* find out which lines to print */
+	t_start = same + 1;
+	p_start = d->plno + t_start - d->tlno;
+	map_range(d, 0, p_start, p_next, t_start, t_next);
+
+	d->plno = p_next;
+	d->tlno = t_next;
+}
+
+/*
+ * We support two kinds of operation in this function:
+ * 1. map == 0, take the same lines from the current commit and assign it
+ *              to parent;
+ * 2. map == 1, in addition to the same lines, we also map the changed lines
+ *              from the current commit to the parent according to the
+ *              diff output.
+ * take_range_cb and take_range are used to take same lines from current commit
+ * to parents.
+ * map_range_cb and map_range are used to map line ranges to the parent.
+ */
+static void assign_range_to_parent(struct rev_info *rev, struct commit *c,
+		struct commit *p, struct diff_line_range *r,
+		struct diff_options *opt, int map)
+{
+	struct diff_line_range *rr = xmalloc(sizeof(*rr));
+	struct diff_line_range *cr = rr, *prev_r = rr;
+	struct diff_line_range *rg = NULL;
+	struct tree_desc desc1, desc2;
+	void *tree1 = NULL, *tree2 = NULL;
+	unsigned long size1, size2;
+	struct diff_queue_struct *queue;
+	struct take_range_cb_data cb = {NULL, cr, 0, 0};
+	xpparam_t xpp;
+	xdemitconf_t xecfg;
+	int i, diff = 0;
+	xdiff_emit_hunk_consume_fn fn = map ? map_range_cb : take_range_cb;
+
+	DIFF_LINE_RANGE_INIT(cr);
+	memset(&xpp, 0, sizeof(xpp));
+	memset(&xecfg, 0, sizeof(xecfg));
+	xecfg.ctxlen = xecfg.interhunkctxlen = 0;
+
+	/*
+	 * Compose up two trees, for root commit, we make up a empty tree.
+	 */
+	assert(c);
+	tree2 = read_object_with_reference(c->tree->object.sha1, "tree",
+			&size2, NULL);
+	if (tree2 == NULL)
+		die("Unable to read tree (%s)", sha1_to_hex(c->tree->object.sha1));
+	init_tree_desc(&desc2, tree2, size2);
+	if (p) {
+		tree1 = read_object_with_reference(p->tree->object.sha1,
+				"tree", &size1, NULL);
+		if (tree1 == NULL)
+			die("Unable to read tree (%s)",
+					sha1_to_hex(p->tree->object.sha1));
+		init_tree_desc(&desc1, tree1, size1);
+	} else {
+		init_tree_desc(&desc1, "", 0);
+	}
+
+	DIFF_QUEUE_CLEAR(&diff_queued_diff);
+	diff_tree(&desc1, &desc2, "", opt);
+	diffcore_std(opt);
+
+	queue = &diff_queued_diff;
+	for (i = 0; i < queue->nr; i++) {
+		struct diff_filepair *pair = queue->queue[i];
+		struct diff_line_range *rg = r;
+		mmfile_t file_p, file_t;
+		assert(pair->two->path);
+		while (rg) {
+			assert(rg->spec->path);
+			if (!strcmp(rg->spec->path, pair->two->path))
+				break;
+			rg = rg->next;
+		}
+
+		if (rg == NULL)
+			continue;
+		rg->touch = 1;
+		if (rg->nr == 0)
+			continue;
+
+		rg->status = pair->status;
+		assert(pair->two->sha1_valid);
+		diff_populate_filespec(pair->two, 0);
+		file_t.ptr = pair->two->data;
+		file_t.size = pair->two->size;
+
+		if (rg->prev)
+			free_filespec(rg->prev);
+		rg->prev = pair->one;
+		rg->prev->count++;
+		if (pair->one->sha1_valid) {
+			diff_populate_filespec(pair->one, 0);
+			file_p.ptr = pair->one->data;
+			file_p.size = pair->one->size;
+		} else {
+			file_p.ptr = "";
+			file_p.size = 0;
+		}
+
+		if (cr->nr != 0) {
+			struct diff_line_range *tmp = xmalloc(sizeof(*tmp));
+			cr->next = tmp;
+			prev_r = cr;
+			cr = tmp;
+		} else if (cr->spec)
+			DIFF_LINE_RANGE_CLEAR(cr);
+
+		DIFF_LINE_RANGE_INIT(cr);
+		if (pair->one->sha1_valid) {
+			cr->spec = pair->one;
+			cr->spec->count++;
+		}
+
+		cb.interesting = rg;
+		cb.range = cr;
+		cb.diff = 0;
+		cb.plno = cb.tlno = 0;
+		xdi_diff_hunks(&file_p, &file_t, fn, &cb, &xpp, &xecfg);
+		if (cb.diff)
+			diff = 1;
+		/*
+		 * The remain part is the same part.
+		 * Instead of calculating the true line number of the two files,
+		 * use the biggest integer.
+		 */
+		if (map)
+			map_range(&cb, 1, cb.plno + 1, INT_MAX, cb.tlno + 1, 0x7FFFFFFF);
+		else
+			take_range(&cb, cb.plno + 1, INT_MAX, cb.tlno + 1, 0x7FFFFFFF);
+	}
+	opt->output_format = DIFF_FORMAT_NO_OUTPUT;
+	diff_flush(opt);
+
+	/*
+	 * Collect the untouch ranges, this comes from the files not changed
+	 * between two commit.
+	 */
+	rg = r;
+	while (rg) {
+		/* clear the touch one to make it usable in next round */
+		if (rg->touch) {
+			rg->touch = 0;
+		} else {
+			struct diff_line_range *untouch = diff_line_range_clone(rg);
+			if (prev_r == rr && rr->nr == 0) {
+				rr = prev_r = untouch;
+			} else {
+				prev_r->next = untouch;
+				prev_r = untouch;
+			}
+		}
+		rg = rg->next;
+	}
+
+	if (cr->nr == 0) {
+		DIFF_LINE_RANGE_CLEAR(cr);
+		free(cr);
+		if (prev_r == cr)
+			rr = NULL;
+		else
+			prev_r->next = NULL;
+	}
+
+	if (rr) {
+		assert(p);
+		add_line_range(rev, p, rr);
+	}
+
+	/* and the ranges of current commit c is updated */
+	c->object.flags &= ~RANGE_UPDATE;
+	if (diff)
+		c->object.flags |= NEED_PRINT;
+
+	if (tree1)
+		free(tree1);
+	if (tree2)
+		free(tree2);
+}
+
+static void diff_update_parent_range(struct rev_info *rev,
+		struct commit *commit)
+{
+	struct diff_line_range *r = lookup_line_range(rev, commit);
+	struct commit_list *parents = commit->parents;
+	struct commit *c = NULL;
+	if (parents) {
+		assert(parents->next == NULL);
+		c = parents->item;
+	}
+
+	assign_range_to_parent(rev, commit, c, r, &rev->diffopt, 1);
+}
+
+static void assign_parents_range(struct rev_info *rev, struct commit *commit)
+{
+	struct commit_list *parents = commit->parents;
+	struct diff_line_range *r = lookup_line_range(rev, commit);
+	struct diff_line_range *evil = NULL, *range = NULL;
+	int nontrivial = 0;
+
+	/*
+	 * If we are in linear history, update range and flush the patch if
+	 * necessary
+	 */
+	if (parents == NULL || parents->next == NULL)
+		return diff_update_parent_range(rev, commit);
+
+	/*
+	 * Loop on the parents and assign the ranges to different
+	 * parents, if there is any range left, this commit must
+	 * be an evil merge.
+	 */
+	evil = diff_line_range_clone_deeply(r);
+	parents = commit->parents;
+	while (parents) {
+		struct commit *p = parents->item;
+		assign_range_to_parent(rev, commit, p, r, &rev->diffopt, 1);
+		assign_range_to_parent(rev, commit, p, evil, &rev->diffopt, 0);
+		parents = parents->next;
+	}
+
+	/*
+	 * yes, this must be an evil merge.
+	 */
+	range = evil;
+	while (range) {
+		if (range->nr) {
+			commit->object.flags |= NEED_PRINT | EVIL_MERGE;
+			nontrivial = 1;
+		}
+		range = range->next;
+	}
+
+	if (nontrivial)
+		add_decoration(&rev->nontrivial_merge, &commit->object, evil);
+	else
+		cleanup(evil);
+}
+
diff --git a/revision.h b/revision.h
index c0d5065..2627ec4 100644
--- a/revision.h
+++ b/revision.h
@@ -15,7 +15,9 @@
 #define ADDED		(1u<<7)	/* Parents already parsed and added? */
 #define SYMMETRIC_LEFT	(1u<<8)
 #define RANGE_UPDATE	(1u<<9) /* for line level traverse */
-#define ALL_REV_FLAGS	((1u<<10)-1)
+#define NEED_PRINT	(1u<<10)
+#define EVIL_MERGE	(1u<<11)
+#define ALL_REV_FLAGS	((1u<<12)-1)
 
 #define DECORATE_SHORT_REFS	1
 #define DECORATE_FULL_REFS	2
@@ -141,6 +143,7 @@ struct rev_info {
 	int count_right;
 	/* line level range that we are chasing */
 	struct decoration line_range;
+	struct decoration nontrivial_merge;
 };
 
 #define REV_TREE_SAME		0
-- 
1.7.2.19.g79e5d

[PATCH V5 09/17] Print the line log

[Bo Yang]

'struct line_chunk' is used to make sure each file is scanned
only once when printing the lines. We track the starting line
number and the offsets of all lines in the range in this struct.

We use two functions from diff.c to generate meta info and hunk
headers in the usual format.

Signed-off-by: Bo Yang <struggleyb.nku@gmail.com>
---
 line.c |  238 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 238 insertions(+), 0 deletions(-)

diff --git a/line.c b/line.c
index ae52832..d50c0e8 100644
--- a/line.c
+++ b/line.c
@@ -1006,3 +1006,241 @@ static void assign_parents_range(struct rev_info *rev, struct commit *commit)
 		cleanup(evil);
 }
 
+struct line_chunk {
+	int lone, ltwo;
+	const char *one, *two;
+	const char *one_end, *two_end;
+	struct diff_line_range *range;
+};
+
+static void flush_lines(struct diff_options *opt, const char **ptr, const char *end,
+		int slno, int elno, int *lno, const char *color, const char heading)
+{
+	const char *p = *ptr;
+	struct strbuf buf = STRBUF_INIT;
+	const char *reset;
+
+	if (*color)
+		reset = diff_get_color_opt(opt, DIFF_RESET);
+	else
+		reset = "";
+
+	strbuf_addf(&buf, "%s%c", color, heading);
+	while (*ptr < end && *lno < slno) {
+		if (**ptr == '\n') {
+			(*lno)++;
+			if (*lno == slno) {
+				(*ptr)++;
+				break;
+			}
+		}
+		(*ptr)++;
+	}
+	assert(*ptr <= end);
+	p = *ptr;
+
+	while (*ptr < end && *lno <= elno) {
+		if (**ptr == '\n') {
+			fprintf(opt->file, "%s", buf.buf);
+			if (*ptr - p)
+				fwrite(p, *ptr - p, 1, opt->file);
+			fprintf(opt->file, "%s\n", reset);
+			p = *ptr + 1;
+			(*lno)++;
+		}
+		(*ptr)++;
+	}
+	if (*lno <= elno) {
+		fprintf(opt->file, "%s", buf.buf);
+		if (*ptr - p)
+			fwrite(p, *ptr - p, 1, opt->file);
+		fprintf(opt->file, "%s\n", reset);
+	}
+	strbuf_release(&buf);
+}
+
+static void diff_flush_range(struct diff_options *opt, struct line_chunk *chunk,
+		struct line_range *range)
+{
+	struct print_pair *pair = &range->pair;
+	const char *old = diff_get_color_opt(opt, DIFF_FILE_OLD);
+	const char *new = diff_get_color_opt(opt, DIFF_FILE_NEW);
+	int i, cur = range->start;
+
+	for (i = 0; i < pair->nr; i++) {
+		struct print_range *pr = pair->ranges + i;
+		if (cur < pr->start)
+			flush_lines(opt, &chunk->two, chunk->two_end,
+				cur, pr->start - 1, &chunk->ltwo, "", ' ');
+
+		if (!pr->line_added)
+			flush_lines(opt, &chunk->one, chunk->one_end,
+				pr->pstart, pr->pend, &chunk->lone, old, '-');
+		flush_lines(opt, &chunk->two, chunk->two_end,
+			pr->start, pr->end, &chunk->ltwo, new, '+');
+
+		cur = pr->end + 1;
+	}
+
+	if (cur <= range->end) {
+		flush_lines(opt, &chunk->two, chunk->two_end,
+			cur, range->end, &chunk->ltwo, "", ' ');
+	}
+}
+
+static void diff_flush_chunks(struct diff_options *opt, struct line_chunk *chunk)
+{
+	struct diff_line_range *range = chunk->range;
+	const char *set = diff_get_color_opt(opt, DIFF_FRAGINFO);
+	const char *reset = diff_get_color_opt(opt, DIFF_RESET);
+	int i;
+
+	for (i = 0; i < range->nr; i++) {
+		struct line_range *r = range->ranges + i;
+		long lenp = r->pend - r->pstart + 1, pstart = r->pstart;
+		long len = r->end - r->start + 1;
+		if (pstart == 0)
+			lenp = 0;
+
+		fprintf(opt->file, "%s@@ -%ld,%ld +%ld,%ld @@%s\n",
+			set, pstart, lenp, r->start, len, reset);
+
+		diff_flush_range(opt, chunk, r);
+	}
+}
+
+static void diff_flush_filepair(struct rev_info *rev, struct diff_line_range *range)
+{
+	struct diff_options *opt = &rev->diffopt;
+	struct diff_filespec *one = range->prev, *two = range->spec;
+	struct diff_filepair p = {one, two, range->status, 0};
+	struct strbuf header = STRBUF_INIT, meta = STRBUF_INIT;
+	const char *a_prefix, *b_prefix;
+	const char *name_a, *name_b, *a_one, *b_two;
+	const char *lbl[2];
+	const char *set = diff_get_color_opt(opt, DIFF_METAINFO);
+	const char *reset = diff_get_color_opt(opt, DIFF_RESET);
+	struct line_chunk chunk;
+	int must_show_header;
+
+	/*
+	 * the ranges that touch no different file, in this case
+	 * the line number will not change, and of course we have
+	 * no sensible rang->pair since there is no diff run.
+	 */
+	if (one == NULL)
+		return;
+
+	if (range->status == DIFF_STATUS_DELETED)
+		die("We are following an nonexistent file, interesting!");
+
+	name_a  = one->path;
+	name_b = two->path;
+	fill_metainfo(&meta, name_a, name_b, one, two, opt, &p, &must_show_header,
+			DIFF_OPT_TST(opt, COLOR_DIFF));
+
+	diff_set_mnemonic_prefix(opt, "a/", "b/");
+	if (DIFF_OPT_TST(opt, REVERSE_DIFF)) {
+		a_prefix = opt->b_prefix;
+		b_prefix = opt->a_prefix;
+	} else {
+		a_prefix = opt->a_prefix;
+		b_prefix = opt->b_prefix;
+	}
+
+	name_a = DIFF_FILE_VALID(one) ? name_a : name_b;
+	name_b = DIFF_FILE_VALID(two) ? name_b : name_a;
+
+	a_one = quote_two(a_prefix, name_a + (*name_a == '/'));
+	b_two = quote_two(b_prefix, name_b + (*name_b == '/'));
+	lbl[0] = DIFF_FILE_VALID(one) ? a_one : "/dev/null";
+	lbl[1] = DIFF_FILE_VALID(two) ? b_two : "/dev/null";
+	strbuf_addf(&header, "%sdiff --git %s %s%s\n", set, a_one, b_two, reset);
+	if (lbl[0][0] == '/') {
+		strbuf_addf(&header, "%snew file mode %06o%s\n", set, two->mode, reset);
+	} else if (lbl[1][0] == '/') {
+		strbuf_addf(&header, "%sdeleted file mode %06o%s\n", set, one->mode, reset);
+	} else if (one->mode != two->mode) {
+			strbuf_addf(&header, "%sold mode %06o%s\n", set, one->mode, reset);
+			strbuf_addf(&header, "%snew mode %06o%s\n", set, two->mode, reset);
+	}
+
+	fprintf(opt->file, "%s%s", header.buf, meta.buf);
+	strbuf_release(&meta);
+	strbuf_release(&header);
+	fprintf(opt->file, "%s--- %s%s\n", set, lbl[0], reset);
+	fprintf(opt->file, "%s+++ %s%s\n", set, lbl[1], reset);
+	free((void *)a_one);
+	free((void *)b_two);
+
+	chunk.one = one->data;
+	chunk.one_end = one->data + one->size;
+	chunk.lone = 1;
+	chunk.two = two->data;
+	chunk.two_end = two->data + two->size;
+	chunk.ltwo = 1;
+	chunk.range = range;
+	diff_flush_chunks(&rev->diffopt, &chunk);
+}
+
+#define EVIL_MERGE_STR "nontrivial merge found"
+static void flush_nontrivial_merge(struct rev_info *rev, struct diff_line_range *range)
+{
+	struct diff_options *opt = &rev->diffopt;
+	const char *reset = diff_get_color_opt(opt, DIFF_RESET);
+	const char *frag = diff_get_color_opt(opt, DIFF_FRAGINFO);
+	const char *meta = diff_get_color_opt(opt, DIFF_METAINFO);
+	const char *new = diff_get_color_opt(opt, DIFF_FILE_NEW);
+
+	fprintf(opt->file, "%s%s%s\n", meta, EVIL_MERGE_STR, reset);
+
+	while (range) {
+		if (range->nr) {
+			int lno = 1;
+			const char *ptr = range->spec->data;
+			const char *end = range->spec->data + range->spec->size;
+			int i = 0;
+			fprintf(opt->file, "%s%s%s\n\n", meta, range->spec->path, reset);
+			for (; i < range->nr; i++) {
+				struct line_range *r = range->ranges + i;
+				fprintf(opt->file, "%s@@ %ld,%ld @@%s\n", frag, r->start,
+					r->end - r->start + 1, reset);
+				flush_lines(opt, &ptr, end, r->start, r->end,
+					&lno, new, ' ');
+			}
+			fprintf(opt->file, "\n");
+		}
+		range = range->next;
+	}
+}
+
+static void line_log_flush(struct rev_info *rev, struct commit *c)
+{
+	struct diff_line_range *range = lookup_line_range(rev, c);
+	struct diff_line_range *nontrivial = lookup_decoration(&rev->nontrivial_merge, &c->object);
+	struct log_info log;
+
+	if (range == NULL)
+		return;
+
+	log.commit = c;
+	log.parent = NULL;
+	rev->loginfo = &log;
+	show_log(rev);
+	rev->loginfo = NULL;
+	/*
+	 * Add a new line after each commit message, of course we should
+	 * add --graph alignment later when the patches comes to master.
+	 */
+	fprintf(rev->diffopt.file, "\n");
+
+	if (c->object.flags & EVIL_MERGE)
+		return flush_nontrivial_merge(rev, nontrivial);
+
+	while (range) {
+		if (range->diff)
+			diff_flush_filepair(rev, range);
+		range = range->next;
+	}
+}
+
-- 
1.7.2.19.g79e5d

[PATCH V5 10/17] Hook line history into cmd_log, ensuring a topo-ordered walk

[Bo Yang]

To correctly track the line ranges over several branches,
we must make sure that we have processed all children before
reaching the commit itself.

Thus we introduce a first pass in cmd_line_log that runs
prepare_revision_walk to achieve the topological ordering.

Signed-off-by: Bo Yang <struggleyb.nku@gmail.com>
---
 builtin/log.c |    5 ++++-
 line.c        |   52 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 line.h        |    2 ++
 revision.c    |    6 ++++++
 4 files changed, 64 insertions(+), 1 deletions(-)

diff --git a/builtin/log.c b/builtin/log.c
index e7c5111..637bcea 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -615,7 +615,10 @@ int cmd_log(int argc, const char **argv, const char *prefix)
 	memset(&opt, 0, sizeof(opt));
 	opt.def = "HEAD";
 	cmd_log_init(argc, argv, prefix, &rev, &opt);
-	return cmd_log_walk(&rev);
+	if (rev.line_level_traverse)
+		return cmd_line_log_walk(&rev);
+	else
+		return cmd_log_walk(&rev);
 }
 
 /* format-patch */
diff --git a/line.c b/line.c
index d50c0e8..c0cb599 100644
--- a/line.c
+++ b/line.c
@@ -1244,3 +1244,55 @@ static void line_log_flush(struct rev_info *rev, struct commit *c)
 	}
 }
 
+int cmd_line_log_walk(struct rev_info *rev)
+{
+	struct commit *commit;
+	struct commit_list *list = NULL;
+	struct diff_line_range *r = NULL;
+
+	if (prepare_revision_walk(rev))
+		die("revision walk prepare failed");
+
+	list = rev->commits;
+	if (list) {
+		list->item->object.flags |= RANGE_UPDATE;
+		list = list->next;
+	}
+	/* Clear the flags */
+	while (list) {
+		list->item->object.flags &= ~(RANGE_UPDATE | EVIL_MERGE | NEED_PRINT);
+		list = list->next;
+	}
+
+	list = rev->commits;
+	while (list) {
+		struct commit_list *need_free = list;
+		commit = list->item;
+
+		if (commit->object.flags & RANGE_UPDATE)
+			assign_parents_range(rev, commit);
+
+		if (commit->object.flags & NEED_PRINT)
+			line_log_flush(rev, commit);
+
+		r = lookup_line_range(rev, commit);
+		if (r) {
+			cleanup(r);
+			r = NULL;
+			add_line_range(rev, commit, r);
+		}
+
+		r = lookup_decoration(&rev->nontrivial_merge, &commit->object);
+		if (r) {
+			cleanup(r);
+			r = NULL;
+			add_decoration(&rev->nontrivial_merge, &commit->object, r);
+		}
+
+		list = list->next;
+		free(need_free);
+	}
+
+	return 0;
+}
+
diff --git a/line.h b/line.h
index e03eff0..202130f 100644
--- a/line.h
+++ b/line.h
@@ -134,4 +134,6 @@ extern struct diff_line_range *lookup_line_range(struct rev_info *revs,
 const char *parse_loc(const char *spec, nth_line_fn_t nth_line,
 		void *data, long lines, long begin, long *ret);
 
+extern int cmd_line_log_walk(struct rev_info *rev);
+
 #endif
diff --git a/revision.c b/revision.c
index 7e82efd..25c9a94 100644
--- a/revision.c
+++ b/revision.c
@@ -1637,6 +1637,12 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s
 	if (revs->combine_merges)
 		revs->ignore_merges = 0;
 	revs->diffopt.abbrev = revs->abbrev;
+
+	if (revs->line_level_traverse) {
+		revs->limited = 1;
+		revs->topo_order = 1;
+	}
+
 	if (diff_setup_done(&revs->diffopt) < 0)
 		die("diff_setup_done failed");
 
-- 
1.7.2.19.g79e5d

[PATCH V5 11/17] Make rewrite_parents public to other part of git

[Bo Yang]

The function rewrite_one is used to rewrite a single
parent of the current commit, and is used by rewrite_parents
to rewrite all the parents.

Decouple the dependence between them by making rewrite_one
a callback function that is passed to rewrite_parents. Then
export rewrite_parents for reuse by the line history browser.

We will use this function in line.c.

Signed-off-by: Bo Yang <struggleyb.nku@gmail.com>
---
 revision.c |   13 ++++---------
 revision.h |   10 ++++++++++
 2 files changed, 14 insertions(+), 9 deletions(-)

diff --git a/revision.c b/revision.c
index 25c9a94..fb08978 100644
--- a/revision.c
+++ b/revision.c
@@ -1893,12 +1893,6 @@ int prepare_revision_walk(struct rev_info *revs)
 	return 0;
 }
 
-enum rewrite_result {
-	rewrite_one_ok,
-	rewrite_one_noparents,
-	rewrite_one_error
-};
-
 static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp)
 {
 	struct commit_list *cache = NULL;
@@ -1920,12 +1914,13 @@ static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp
 	}
 }
 
-static int rewrite_parents(struct rev_info *revs, struct commit *commit)
+int rewrite_parents(struct rev_info *revs, struct commit *commit,
+	rewrite_parent_fn_t rewrite_parent)
 {
 	struct commit_list **pp = &commit->parents;
 	while (*pp) {
 		struct commit_list *parent = *pp;
-		switch (rewrite_one(revs, &parent->item)) {
+		switch (rewrite_parent(revs, &parent->item)) {
 		case rewrite_one_ok:
 			break;
 		case rewrite_one_noparents:
@@ -1993,7 +1988,7 @@ enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit)
 	if (action == commit_show &&
 	    !revs->show_all &&
 	    revs->prune && revs->dense && want_ancestry(revs)) {
-		if (rewrite_parents(revs, commit) < 0)
+		if (rewrite_parents(revs, commit, rewrite_one) < 0)
 			return commit_error;
 	}
 	return action;
diff --git a/revision.h b/revision.h
index 2627ec4..48222f6 100644
--- a/revision.h
+++ b/revision.h
@@ -199,4 +199,14 @@ enum commit_action {
 extern enum commit_action get_commit_action(struct rev_info *revs, struct commit *commit);
 extern enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit);
 
+enum rewrite_result {
+	rewrite_one_ok,
+	rewrite_one_noparents,
+	rewrite_one_error
+};
+
+typedef enum rewrite_result (*rewrite_parent_fn_t)(struct rev_info *revs, struct commit **pp);
+
+extern int rewrite_parents(struct rev_info *revs, struct commit *commit,
+	rewrite_parent_fn_t rewrite_parent);
 #endif
-- 
1.7.2.19.g79e5d

[PATCH V5 12/17] Make graph_next_line external to other part of git

[Bo Yang]

We will use it in line level log output.

Signed-off-by: Bo Yang <struggleyb.nku@gmail.com>
---
 graph.c |   14 +-------------
 graph.h |   10 ++++++++++
 2 files changed, 11 insertions(+), 13 deletions(-)

diff --git a/graph.c b/graph.c
index ac7c605..824e055 100644
--- a/graph.c
+++ b/graph.c
@@ -4,21 +4,9 @@
 #include "graph.h"
 #include "diff.h"
 #include "revision.h"
-
 /* Internal API */
 
 /*
- * Output the next line for a graph.
- * This formats the next graph line into the specified strbuf.  It is not
- * terminated with a newline.
- *
- * Returns 1 if the line includes the current commit, and 0 otherwise.
- * graph_next_line() will return 1 exactly once for each time
- * graph_update() is called.
- */
-static int graph_next_line(struct git_graph *graph, struct strbuf *sb);
-
-/*
  * Output a padding line in the graph.
  * This is similar to graph_next_line().  However, it is guaranteed to
  * never print the current commit line.  Instead, if the commit line is
@@ -1143,7 +1131,7 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct strbuf
 		graph_update_state(graph, GRAPH_PADDING);
 }
 
-static int graph_next_line(struct git_graph *graph, struct strbuf *sb)
+int graph_next_line(struct git_graph *graph, struct strbuf *sb)
 {
 	switch (graph->state) {
 	case GRAPH_PADDING:
diff --git a/graph.h b/graph.h
index b82ae87..5b3f059 100644
--- a/graph.h
+++ b/graph.h
@@ -32,6 +32,16 @@ void graph_update(struct git_graph *graph, struct commit *commit);
  */
 int graph_is_commit_finished(struct git_graph const *graph);
 
+/*
+ * Output the next line for a graph.
+ * This formats the next graph line into the specified strbuf.  It is not
+ * terminated with a newline.
+ *
+ * Returns 1 if the line includes the current commit, and 0 otherwise.
+ * graph_next_line() will return 1 exactly once for each time
+ * graph_update() is called.
+ */
+int graph_next_line(struct git_graph *graph, struct strbuf *sb);
 
 /*
  * graph_show_*: helper functions for printing to stdout
-- 
1.7.2.19.g79e5d

[PATCH V5 13/17] Add parent rewriting to line history browser

[Bo Yang]

Walking forward through history (i.e., topologically earliest
commits first), we filter the parent list of every commit as
follows. Consider a parent P:
 - If P touches any of the interesting line ranges, we keep it.
 - If P is a merge and it takes all the interesting line ranges
   from one of its parents, P is rewritten to this parent, else
   we keep P.
 - Otherwise, P is rewritten to its (only) parent P^.

Signed-off-by: Bo Yang <struggleyb.nku@gmail.com>
---
 line.c     |  263 ++++++++++++++++++++++++++++++++++++++++++++++++++++++------
 line.h     |    2 +
 revision.c |    3 +
 revision.h |    5 +-
 4 files changed, 246 insertions(+), 27 deletions(-)

diff --git a/line.c b/line.c
index c0cb599..a2afe60 100644
--- a/line.c
+++ b/line.c
@@ -9,8 +9,11 @@
 #include "xdiff-interface.h"
 #include "strbuf.h"
 #include "log-tree.h"
+#include "graph.h"
 #include "line.h"
 
+static int limited;
+
 static void cleanup(struct diff_line_range *r)
 {
 	while (r) {
@@ -389,6 +392,7 @@ struct diff_line_range *diff_line_range_clone(struct diff_line_range *r)
 	struct diff_line_range *ret = xmalloc(sizeof(*ret));
 	int i = 0;
 
+	assert(r);
 	DIFF_LINE_RANGE_INIT(ret);
 	ret->ranges = xcalloc(r->nr, sizeof(struct line_range));
 	memcpy(ret->ranges, r->ranges, sizeof(struct line_range) * r->nr);
@@ -469,14 +473,14 @@ void add_line_range(struct rev_info *revs, struct commit *commit,
 {
 	struct diff_line_range *ret = NULL;
 
-	if (r != NULL) {
-		ret = lookup_decoration(&revs->line_range, &commit->object);
-		if (ret != NULL)
-			diff_line_range_merge(ret, r);
-		else
-			add_decoration(&revs->line_range, &commit->object, r);
+	ret = lookup_decoration(&revs->line_range, &commit->object);
+	if (ret != NULL && r != NULL)
+		diff_line_range_merge(ret, r);
+	else
+		add_decoration(&revs->line_range, &commit->object, r);
+
+	if (r != NULL)
 		commit->object.flags |= RANGE_UPDATE;
-	}
 }
 
 struct diff_line_range *lookup_line_range(struct rev_info *revs,
@@ -550,6 +554,23 @@ void map_lines(long p_start, long p_end, long t_start, long t_end,
 		return;
 	}
 
+	if (start == t_start)
+	{
+		*o_start = p_start;
+		*o_end = p_start + (end - start);
+		if (*o_end > p_end)
+			*o_end = p_end;
+		return;
+	}
+
+	if (end == t_end) {
+		*o_start = p_end - (end - start);
+		if (*o_start < p_start)
+			*o_start = p_start;
+		*o_end = p_end;
+		return;
+	}
+
 	/*
 	 * A heuristic for lines mapping:
 	 *
@@ -782,7 +803,7 @@ static void map_range_cb(void *data, long same, long p_next, long t_next)
  * to parents.
  * map_range_cb and map_range are used to map line ranges to the parent.
  */
-static void assign_range_to_parent(struct rev_info *rev, struct commit *c,
+static int assign_range_to_parent(struct rev_info *rev, struct commit *c,
 		struct commit *p, struct diff_line_range *r,
 		struct diff_options *opt, int map)
 {
@@ -930,9 +951,19 @@ static void assign_range_to_parent(struct rev_info *rev, struct commit *c,
 			prev_r->next = NULL;
 	}
 
+	if (!map)
+		goto out;
+
 	if (rr) {
 		assert(p);
 		add_line_range(rev, p, rr);
+	} else {
+		/*
+		 * If there is no new ranges assigned to the parent,
+		 * we should mark it as a 'root' commit.
+		 */
+		free(c->parents);
+		c->parents = NULL;
 	}
 
 	/* and the ranges of current commit c is updated */
@@ -940,10 +971,13 @@ static void assign_range_to_parent(struct rev_info *rev, struct commit *c,
 	if (diff)
 		c->object.flags |= NEED_PRINT;
 
+out:
 	if (tree1)
 		free(tree1);
 	if (tree2)
 		free(tree2);
+
+	return diff;
 }
 
 static void diff_update_parent_range(struct rev_info *rev,
@@ -960,13 +994,21 @@ static void diff_update_parent_range(struct rev_info *rev,
 	assign_range_to_parent(rev, commit, c, r, &rev->diffopt, 1);
 }
 
+struct commit_state {
+	struct diff_line_range *range;
+	struct object obj;
+};
+
 static void assign_parents_range(struct rev_info *rev, struct commit *commit)
 {
 	struct commit_list *parents = commit->parents;
 	struct diff_line_range *r = lookup_line_range(rev, commit);
 	struct diff_line_range *evil = NULL, *range = NULL;
+	struct decoration parents_state;
+	struct commit_state *state = NULL;
 	int nontrivial = 0;
 
+	memset(&parents_state, 0, sizeof(parents_state));
 	/*
 	 * If we are in linear history, update range and flush the patch if
 	 * necessary
@@ -983,23 +1025,78 @@ static void assign_parents_range(struct rev_info *rev, struct commit *commit)
 	parents = commit->parents;
 	while (parents) {
 		struct commit *p = parents->item;
-		assign_range_to_parent(rev, commit, p, r, &rev->diffopt, 1);
+		int diff = 0;
+		struct diff_line_range *origin_range = lookup_line_range(rev, p);
+		if (origin_range)
+			origin_range = diff_line_range_clone_deeply(origin_range);
+
+		state = xmalloc(sizeof(*state));
+		state->range = origin_range;
+		state->obj = p->object;
+		add_decoration(&parents_state, &p->object, state);
+		diff = assign_range_to_parent(rev, commit, p, r, &rev->diffopt, 1);
+		/* Since all the ranges comes from this parent, we can ignore others */
+		if (diff == 0) {
+			/* restore the state of parents before this one */
+			parents = commit->parents;
+			while (parents->item != p) {
+				struct commit_list *list = parents;
+				struct diff_line_range *line_range = NULL;
+				parents = parents->next;
+				line_range = lookup_line_range(rev, list->item);
+				cleanup(line_range);
+				state = lookup_decoration(&parents_state, &list->item->object);
+				add_decoration(&parents_state, &list->item->object, NULL);
+				add_line_range(rev, list->item, state->range);
+				list->item->object = state->obj;
+				free(state);
+				free(list);
+			}
+
+			commit->parents = parents;
+			parents = parents->next;
+			commit->parents->next = NULL;
+
+			/* free the non-use commit_list */
+			while (parents) {
+				struct commit_list *list = parents;
+				parents = parents->next;
+				free(list);
+			}
+			goto out;
+		}
+		/* take the ranges from 'commit', try to detect nontrivial merge */
 		assign_range_to_parent(rev, commit, p, evil, &rev->diffopt, 0);
 		parents = parents->next;
 	}
 
+	commit->object.flags |= NONTRIVIAL_MERGE;
 	/*
 	 * yes, this must be an evil merge.
 	 */
 	range = evil;
 	while (range) {
 		if (range->nr) {
-			commit->object.flags |= NEED_PRINT | EVIL_MERGE;
+			commit->object.flags |= EVIL_MERGE;
 			nontrivial = 1;
 		}
 		range = range->next;
 	}
 
+out:
+	/* Never print out any diff for a merge commit */
+	commit->object.flags &= ~NEED_PRINT;
+
+	parents = commit->parents;
+	while (parents) {
+		state = lookup_decoration(&parents_state, &parents->item->object);
+		if (state) {
+			cleanup(state->range);
+			free(state);
+		}
+		parents = parents->next;
+	}
+
 	if (nontrivial)
 		add_decoration(&rev->nontrivial_merge, &commit->object, evil);
 	else
@@ -1184,15 +1281,34 @@ static void diff_flush_filepair(struct rev_info *rev, struct diff_line_range *ra
 }
 
 #define EVIL_MERGE_STR "nontrivial merge found"
-static void flush_nontrivial_merge(struct rev_info *rev, struct diff_line_range *range)
+static void flush_nontrivial_merge(struct rev_info *rev,
+		struct diff_line_range *range)
 {
 	struct diff_options *opt = &rev->diffopt;
 	const char *reset = diff_get_color_opt(opt, DIFF_RESET);
 	const char *frag = diff_get_color_opt(opt, DIFF_FRAGINFO);
 	const char *meta = diff_get_color_opt(opt, DIFF_METAINFO);
 	const char *new = diff_get_color_opt(opt, DIFF_FILE_NEW);
+	char *line_prefix = "";
+	struct strbuf *msgbuf;
+	int evil = 0;
+	struct diff_line_range *r = range;
+
+	if (opt && opt->output_prefix) {
+		msgbuf = opt->output_prefix(opt, opt->output_prefix_data);
+		line_prefix = msgbuf->buf;
+	}
 
-	fprintf(opt->file, "%s%s%s\n", meta, EVIL_MERGE_STR, reset);
+	while (r) {
+		if (r->nr)
+			evil = 1;
+		r = r->next;
+	}
+
+	if (!evil)
+		return;
+
+	fprintf(opt->file, "%s%s%s%s\n", line_prefix, meta, EVIL_MERGE_STR, reset);
 
 	while (range) {
 		if (range->nr) {
@@ -1200,7 +1316,8 @@ static void flush_nontrivial_merge(struct rev_info *rev, struct diff_line_range
 			const char *ptr = range->spec->data;
 			const char *end = range->spec->data + range->spec->size;
 			int i = 0;
-			fprintf(opt->file, "%s%s%s\n\n", meta, range->spec->path, reset);
+			fprintf(opt->file, "%s%s%s%s\n", line_prefix,
+				meta, range->spec->path, reset);
 			for (; i < range->nr; i++) {
 				struct line_range *r = range->ranges + i;
 				fprintf(opt->file, "%s@@ %ld,%ld @@%s\n", frag, r->start,
@@ -1217,12 +1334,17 @@ static void flush_nontrivial_merge(struct rev_info *rev, struct diff_line_range
 static void line_log_flush(struct rev_info *rev, struct commit *c)
 {
 	struct diff_line_range *range = lookup_line_range(rev, c);
-	struct diff_line_range *nontrivial = lookup_decoration(&rev->nontrivial_merge, &c->object);
+	struct diff_line_range *nontrivial = lookup_decoration(&rev->nontrivial_merge,
+							&c->object);
 	struct log_info log;
+	struct diff_options *opt = &rev->diffopt;
 
-	if (range == NULL)
+	if (range == NULL || !(c->object.flags & NONTRIVIAL_MERGE ||
+							c->object.flags & NEED_PRINT))
 		return;
 
+	if (rev->graph)
+		graph_update(rev->graph, c);
 	log.commit = c;
 	log.parent = NULL;
 	rev->loginfo = &log;
@@ -1234,13 +1356,21 @@ static void line_log_flush(struct rev_info *rev, struct commit *c)
 	 */
 	fprintf(rev->diffopt.file, "\n");
 
-	if (c->object.flags & EVIL_MERGE)
-		return flush_nontrivial_merge(rev, nontrivial);
+	if (c->object.flags & NONTRIVIAL_MERGE)
+		flush_nontrivial_merge(rev, nontrivial);
+	else {
+		while (range) {
+			if (range->diff)
+				diff_flush_filepair(rev, range);
+			range = range->next;
+		}
+	}
 
-	while (range) {
-		if (range->diff)
-			diff_flush_filepair(rev, range);
-		range = range->next;
+	while (rev->graph && !graph_is_commit_finished(rev->graph)) {
+		struct strbuf sb;
+		strbuf_init(&sb, 0);
+		graph_next_line(rev->graph, &sb);
+		fputs(sb.buf, opt->file);
 	}
 }
 
@@ -1254,13 +1384,14 @@ int cmd_line_log_walk(struct rev_info *rev)
 		die("revision walk prepare failed");
 
 	list = rev->commits;
-	if (list) {
+	if (list && !limited) {
 		list->item->object.flags |= RANGE_UPDATE;
 		list = list->next;
 	}
 	/* Clear the flags */
-	while (list) {
-		list->item->object.flags &= ~(RANGE_UPDATE | EVIL_MERGE | NEED_PRINT);
+	while (list && !limited) {
+		list->item->object.flags &= ~(RANGE_UPDATE | NONTRIVIAL_MERGE |
+						NEED_PRINT | EVIL_MERGE);
 		list = list->next;
 	}
 
@@ -1272,7 +1403,8 @@ int cmd_line_log_walk(struct rev_info *rev)
 		if (commit->object.flags & RANGE_UPDATE)
 			assign_parents_range(rev, commit);
 
-		if (commit->object.flags & NEED_PRINT)
+		if (commit->object.flags & NEED_PRINT ||
+			commit->object.flags & NONTRIVIAL_MERGE || rev->graph)
 			line_log_flush(rev, commit);
 
 		r = lookup_line_range(rev, commit);
@@ -1296,3 +1428,84 @@ int cmd_line_log_walk(struct rev_info *rev)
 	return 0;
 }
 
+static enum rewrite_result rewrite_one(struct rev_info *rev, struct commit **pp)
+{
+	struct diff_line_range *r = NULL;
+	struct commit *p;
+	while (1) {
+		p = *pp;
+		if (p->object.flags & RANGE_UPDATE)
+			assign_parents_range(rev, p);
+		if (p->object.flags & NEED_PRINT || p->object.flags & NONTRIVIAL_MERGE)
+			return rewrite_one_ok;
+		if (!p->parents)
+			return rewrite_one_noparents;
+
+		r = lookup_line_range(rev, p);
+		if (!r)
+			return rewrite_one_noparents;
+		*pp = p->parents->item;
+	}
+}
+
+/* The rev->commits must be sorted in topologically order */
+void limit_list_line(struct rev_info *rev)
+{
+	struct commit_list *list = rev->commits;
+	struct commit_list *commits = xmalloc(sizeof(struct commit_list));
+	struct commit_list *out = commits, *prev = commits;
+	struct commit *c;
+	struct diff_line_range *r;
+
+	if (list) {
+		list->item->object.flags |= RANGE_UPDATE;
+		list = list->next;
+	}
+	/* Clear the flags */
+	while (list) {
+		list->item->object.flags &= ~(RANGE_UPDATE | NONTRIVIAL_MERGE |
+						NEED_PRINT | EVIL_MERGE);
+		list = list->next;
+	}
+
+	list = rev->commits;
+	while (list) {
+		c = list->item;
+
+		if (c->object.flags & RANGE_UPDATE)
+			assign_parents_range(rev, c);
+
+		if (c->object.flags & NEED_PRINT || c->object.flags & NONTRIVIAL_MERGE) {
+			if (rewrite_parents(rev, c, rewrite_one))
+				die("Can't rewrite parent for commit %s",
+					sha1_to_hex(c->object.sha1));
+			commits->item = c;
+			commits->next = xmalloc(sizeof(struct commit_list));
+			prev = commits;
+			commits = commits->next;
+		} else {
+			r = lookup_line_range(rev, c);
+			if (r) {
+				cleanup(r);
+				r = NULL;
+				add_line_range(rev, c, r);
+			}
+		}
+
+		list = list->next;
+	}
+
+	prev->next = NULL;
+	free(commits);
+
+	list = rev->commits;
+	while (list) {
+		struct commit_list *l = list;
+		list = list->next;
+		free(l);
+	}
+
+	rev->commits = out;
+	limited = 1;
+}
+
diff --git a/line.h b/line.h
index 202130f..c00f1e6 100644
--- a/line.h
+++ b/line.h
@@ -136,4 +136,6 @@ const char *parse_loc(const char *spec, nth_line_fn_t nth_line,
 
 extern int cmd_line_log_walk(struct rev_info *rev);
 
+extern void limit_list_line(struct rev_info *rev);
+
 #endif
diff --git a/revision.c b/revision.c
index fb08978..a6527ca 100644
--- a/revision.c
+++ b/revision.c
@@ -13,6 +13,7 @@
 #include "decorate.h"
 #include "log-tree.h"
 #include "string-list.h"
+#include "line.h"
 
 volatile show_early_output_fn_t show_early_output;
 
@@ -1886,6 +1887,8 @@ int prepare_revision_walk(struct rev_info *revs)
 			return -1;
 	if (revs->topo_order)
 		sort_in_topological_order(&revs->commits, revs->lifo);
+	if (revs->rewrite_parents && revs->line_level_traverse)
+		limit_list_line(revs);
 	if (revs->simplify_merges)
 		simplify_merges(revs);
 	if (revs->children.name)
diff --git a/revision.h b/revision.h
index 48222f6..7f7d178 100644
--- a/revision.h
+++ b/revision.h
@@ -16,8 +16,9 @@
 #define SYMMETRIC_LEFT	(1u<<8)
 #define RANGE_UPDATE	(1u<<9) /* for line level traverse */
 #define NEED_PRINT	(1u<<10)
-#define EVIL_MERGE	(1u<<11)
-#define ALL_REV_FLAGS	((1u<<12)-1)
+#define NONTRIVIAL_MERGE	(1u<<11)
+#define EVIL_MERGE	(1u<<12)
+#define ALL_REV_FLAGS	((1u<<13)-1)
 
 #define DECORATE_SHORT_REFS	1
 #define DECORATE_FULL_REFS	2
-- 
1.7.2.19.g79e5d

[PATCH V5 14/17] Add --graph prefix before line history output

[Bo Yang]

Makes the line level log output look good when used
with the '--graph' option.

Signed-off-by: Bo Yang <struggleyb.nku@gmail.com>
---
 line.c |   66 ++++++++++++++++++++++++++++++++++++++++++++++-----------------
 1 files changed, 48 insertions(+), 18 deletions(-)

diff --git a/line.c b/line.c
index a2afe60..5580768 100644
--- a/line.c
+++ b/line.c
@@ -1116,6 +1116,13 @@ static void flush_lines(struct diff_options *opt, const char **ptr, const char *
 	const char *p = *ptr;
 	struct strbuf buf = STRBUF_INIT;
 	const char *reset;
+	char *line_prefix = "";
+	struct strbuf *msgbuf;
+
+	if (opt && opt->output_prefix) {
+		msgbuf = opt->output_prefix(opt, opt->output_prefix_data);
+		line_prefix = msgbuf->buf;
+	}
 
 	if (*color)
 		reset = diff_get_color_opt(opt, DIFF_RESET);
@@ -1138,7 +1145,7 @@ static void flush_lines(struct diff_options *opt, const char **ptr, const char *
 
 	while (*ptr < end && *lno <= elno) {
 		if (**ptr == '\n') {
-			fprintf(opt->file, "%s", buf.buf);
+			fprintf(opt->file, "%s%s", line_prefix, buf.buf);
 			if (*ptr - p)
 				fwrite(p, *ptr - p, 1, opt->file);
 			fprintf(opt->file, "%s\n", reset);
@@ -1148,7 +1155,7 @@ static void flush_lines(struct diff_options *opt, const char **ptr, const char *
 		(*ptr)++;
 	}
 	if (*lno <= elno) {
-		fprintf(opt->file, "%s", buf.buf);
+		fprintf(opt->file, "%s%s", line_prefix, buf.buf);
 		if (*ptr - p)
 			fwrite(p, *ptr - p, 1, opt->file);
 		fprintf(opt->file, "%s\n", reset);
@@ -1190,8 +1197,15 @@ static void diff_flush_chunks(struct diff_options *opt, struct line_chunk *chunk
 	struct diff_line_range *range = chunk->range;
 	const char *set = diff_get_color_opt(opt, DIFF_FRAGINFO);
 	const char *reset = diff_get_color_opt(opt, DIFF_RESET);
+	char *line_prefix = "";
+	struct strbuf *msgbuf;
 	int i;
 
+	if (opt && opt->output_prefix) {
+		msgbuf = opt->output_prefix(opt, opt->output_prefix_data);
+		line_prefix = msgbuf->buf;
+	}
+
 	for (i = 0; i < range->nr; i++) {
 		struct line_range *r = range->ranges + i;
 		long lenp = r->pend - r->pstart + 1, pstart = r->pstart;
@@ -1199,8 +1213,8 @@ static void diff_flush_chunks(struct diff_options *opt, struct line_chunk *chunk
 		if (pstart == 0)
 			lenp = 0;
 
-		fprintf(opt->file, "%s@@ -%ld,%ld +%ld,%ld @@%s\n",
-			set, pstart, lenp, r->start, len, reset);
+		fprintf(opt->file, "%s%s@@ -%ld,%ld +%ld,%ld @@%s\n",
+			line_prefix, set, pstart, lenp, r->start, len, reset);
 
 		diff_flush_range(opt, chunk, r);
 	}
@@ -1219,6 +1233,13 @@ static void diff_flush_filepair(struct rev_info *rev, struct diff_line_range *ra
 	const char *reset = diff_get_color_opt(opt, DIFF_RESET);
 	struct line_chunk chunk;
 	int must_show_header;
+	char *line_prefix = "";
+	struct strbuf *msgbuf;
+
+	if (opt && opt->output_prefix) {
+		msgbuf = opt->output_prefix(opt, opt->output_prefix_data);
+		line_prefix = msgbuf->buf;
+	}
 
 	/*
 	 * the ranges that touch no different file, in this case
@@ -1252,21 +1273,26 @@ static void diff_flush_filepair(struct rev_info *rev, struct diff_line_range *ra
 	b_two = quote_two(b_prefix, name_b + (*name_b == '/'));
 	lbl[0] = DIFF_FILE_VALID(one) ? a_one : "/dev/null";
 	lbl[1] = DIFF_FILE_VALID(two) ? b_two : "/dev/null";
-	strbuf_addf(&header, "%sdiff --git %s %s%s\n", set, a_one, b_two, reset);
+	strbuf_addf(&header, "%s%sdiff --git %s %s%s\n", line_prefix,
+			set, a_one, b_two, reset);
 	if (lbl[0][0] == '/') {
-		strbuf_addf(&header, "%snew file mode %06o%s\n", set, two->mode, reset);
+		strbuf_addf(&header, "%s%snew file mode %06o%s\n",
+			line_prefix, set, two->mode, reset);
 	} else if (lbl[1][0] == '/') {
-		strbuf_addf(&header, "%sdeleted file mode %06o%s\n", set, one->mode, reset);
+		strbuf_addf(&header, "%s%sdeleted file mode %06o%s\n",
+			line_prefix, set, one->mode, reset);
 	} else if (one->mode != two->mode) {
-			strbuf_addf(&header, "%sold mode %06o%s\n", set, one->mode, reset);
-			strbuf_addf(&header, "%snew mode %06o%s\n", set, two->mode, reset);
+			strbuf_addf(&header, "%s%sold mode %06o%s\n",
+				line_prefix, set, one->mode, reset);
+			strbuf_addf(&header, "%s%snew mode %06o%s\n",
+				line_prefix, set, two->mode, reset);
 	}
 
 	fprintf(opt->file, "%s%s", header.buf, meta.buf);
 	strbuf_release(&meta);
 	strbuf_release(&header);
-	fprintf(opt->file, "%s--- %s%s\n", set, lbl[0], reset);
-	fprintf(opt->file, "%s+++ %s%s\n", set, lbl[1], reset);
+	fprintf(opt->file, "%s%s--- %s%s\n", line_prefix, set, lbl[0], reset);
+	fprintf(opt->file, "%s%s+++ %s%s\n", line_prefix, set, lbl[1], reset);
 	free((void *)a_one);
 	free((void *)b_two);
 
@@ -1320,12 +1346,13 @@ static void flush_nontrivial_merge(struct rev_info *rev,
 				meta, range->spec->path, reset);
 			for (; i < range->nr; i++) {
 				struct line_range *r = range->ranges + i;
-				fprintf(opt->file, "%s@@ %ld,%ld @@%s\n", frag, r->start,
+				fprintf(opt->file, "%s%s@@ %ld,%ld @@%s\n",
+					line_prefix, frag, r->start,
 					r->end - r->start + 1, reset);
 				flush_lines(opt, &ptr, end, r->start, r->end,
 					&lno, new, ' ');
 			}
-			fprintf(opt->file, "\n");
+			fprintf(opt->file, "%s\n", line_prefix);
 		}
 		range = range->next;
 	}
@@ -1338,6 +1365,8 @@ static void line_log_flush(struct rev_info *rev, struct commit *c)
 							&c->object);
 	struct log_info log;
 	struct diff_options *opt = &rev->diffopt;
+	char *line_prefix = "";
+	struct strbuf *msgbuf;
 
 	if (range == NULL || !(c->object.flags & NONTRIVIAL_MERGE ||
 							c->object.flags & NEED_PRINT))
@@ -1350,11 +1379,12 @@ static void line_log_flush(struct rev_info *rev, struct commit *c)
 	rev->loginfo = &log;
 	show_log(rev);
 	rev->loginfo = NULL;
-	/*
-	 * Add a new line after each commit message, of course we should
-	 * add --graph alignment later when the patches comes to master.
-	 */
-	fprintf(rev->diffopt.file, "\n");
+
+	if (opt && opt->output_prefix) {
+		msgbuf = opt->output_prefix(opt, opt->output_prefix_data);
+		line_prefix = msgbuf->buf;
+	}
+	fprintf(rev->diffopt.file, "%s\n", line_prefix);
 
 	if (c->object.flags & NONTRIVIAL_MERGE)
 		flush_nontrivial_merge(rev, nontrivial);
-- 
1.7.2.19.g79e5d

[PATCH V5 15/17] Add --full-line-diff option

[Bo Yang]

Always print the interesting ranges even if the current
commit does not change any line of it.

Signed-off-by: Bo Yang <struggleyb.nku@gmail.com>
---
 builtin/log.c |    8 +++++++-
 line.c        |   22 ++++++++++++++++------
 revision.c    |    5 ++++-
 revision.h    |    3 ++-
 4 files changed, 29 insertions(+), 9 deletions(-)

diff --git a/builtin/log.c b/builtin/log.c
index 637bcea..0151d2f 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -85,6 +85,7 @@ static void cmd_log_init(int argc, const char **argv, const char *prefix,
 {
 	int i;
 	int decoration_given = 0;
+	static int full_line_diff;
 	struct userformat_want w;
 	const char *path = NULL, *fullpath = NULL;
 	static struct diff_line_range *range;
@@ -95,6 +96,9 @@ static void cmd_log_init(int argc, const char **argv, const char *prefix,
 		OPT_CALLBACK('L', NULL, &line_cb, "n,m",
 			     "Process only line range n,m, counting from 1",
 			     log_line_range_callback),
+		OPT_BOOLEAN(0, "full-line-diff", &full_line_diff,
+			    "Always print the interesting range even if the \
+			    current commit does not change any line of it"),
 		OPT_END()
 	};
 
@@ -223,8 +227,10 @@ parse_done:
 	}
 
 	/* Test whether line level history is asked for */
-	if (range && range->nr > 0)
+	if (range && range->nr > 0) {
 		setup_line(rev, range);
+		rev->full_line_diff = full_line_diff;
+	}
 }
 
 /*
diff --git a/line.c b/line.c
index 5580768..7de6427 100644
--- a/line.c
+++ b/line.c
@@ -1244,10 +1244,18 @@ static void diff_flush_filepair(struct rev_info *rev, struct diff_line_range *ra
 	/*
 	 * the ranges that touch no different file, in this case
 	 * the line number will not change, and of course we have
-	 * no sensible rang->pair since there is no diff run.
+	 * no sensible range->pair since there is no diff run.
 	 */
-	if (one == NULL)
+	if (one == NULL) {
+		if (rev->full_line_diff) {
+			chunk.two = two->data;
+			chunk.two_end = two->data + two->size;
+			chunk.ltwo = 1;
+			chunk.range = range;
+			diff_flush_chunks(&rev->diffopt, &chunk);
+		}
 		return;
+	}
 
 	if (range->status == DIFF_STATUS_DELETED)
 		die("We are following an nonexistent file, interesting!");
@@ -1369,7 +1377,8 @@ static void line_log_flush(struct rev_info *rev, struct commit *c)
 	struct strbuf *msgbuf;
 
 	if (range == NULL || !(c->object.flags & NONTRIVIAL_MERGE ||
-							c->object.flags & NEED_PRINT))
+			c->object.flags & NEED_PRINT ||
+			rev->full_line_diff))
 		return;
 
 	if (rev->graph)
@@ -1390,7 +1399,7 @@ static void line_log_flush(struct rev_info *rev, struct commit *c)
 		flush_nontrivial_merge(rev, nontrivial);
 	else {
 		while (range) {
-			if (range->diff)
+			if (range->diff || (range->nr && rev->full_line_diff))
 				diff_flush_filepair(rev, range);
 			range = range->next;
 		}
@@ -1421,7 +1430,7 @@ int cmd_line_log_walk(struct rev_info *rev)
 	/* Clear the flags */
 	while (list && !limited) {
 		list->item->object.flags &= ~(RANGE_UPDATE | NONTRIVIAL_MERGE |
-						NEED_PRINT | EVIL_MERGE);
+				NEED_PRINT | EVIL_MERGE);
 		list = list->next;
 	}
 
@@ -1434,7 +1443,8 @@ int cmd_line_log_walk(struct rev_info *rev)
 			assign_parents_range(rev, commit);
 
 		if (commit->object.flags & NEED_PRINT ||
-			commit->object.flags & NONTRIVIAL_MERGE || rev->graph)
+			commit->object.flags & NONTRIVIAL_MERGE ||
+			rev->full_line_diff)
 			line_log_flush(rev, commit);
 
 		r = lookup_line_range(rev, commit);
diff --git a/revision.c b/revision.c
index a6527ca..62fe002 100644
--- a/revision.c
+++ b/revision.c
@@ -1887,7 +1887,10 @@ int prepare_revision_walk(struct rev_info *revs)
 			return -1;
 	if (revs->topo_order)
 		sort_in_topological_order(&revs->commits, revs->lifo);
-	if (revs->rewrite_parents && revs->line_level_traverse)
+	if (revs->full_line_diff)
+		revs->dense = 0;
+	if (revs->rewrite_parents && revs->line_level_traverse
+		&& !revs->full_line_diff)
 		limit_list_line(revs);
 	if (revs->simplify_merges)
 		simplify_merges(revs);
diff --git a/revision.h b/revision.h
index 7f7d178..db901e5 100644
--- a/revision.h
+++ b/revision.h
@@ -73,7 +73,8 @@ struct rev_info {
 			bisect:1,
 			ancestry_path:1,
 			first_parent_only:1,
-			line_level_traverse:1;
+			line_level_traverse:1,
+			full_line_diff:1;
 
 	/* Diff flags */
 	unsigned int	diff:1,
-- 
1.7.2.19.g79e5d

[PATCH V5 16/17] Add tests for line history browser

[Bo Yang]

t/t4301-log-line-single-history.sh:
  test the linear line of history.

t/t4302-log-line-merge-history.sh:
  test the case that there are merges in the history.

Signed-off-by: Bo Yang <struggleyb.nku@gmail.com>
---
Note that applying this with --whitespace=fix will make the tests
fail, as there are diffs contained which must preserve the SP TAB
sequence of context lines.
 t/t4301-log-line-single-history.sh |  627 ++++++++++++++++++++++++++++++++++++
 t/t4302-log-line-merge-history.sh  |  163 ++++++++++
 2 files changed, 790 insertions(+), 0 deletions(-)
 create mode 100755 t/t4301-log-line-single-history.sh
 create mode 100755 t/t4302-log-line-merge-history.sh

diff --git a/t/t4301-log-line-single-history.sh b/t/t4301-log-line-single-history.sh
new file mode 100755
index 0000000..19b0cb7
--- /dev/null
+++ b/t/t4301-log-line-single-history.sh
@@ -0,0 +1,627 @@
+#!/bin/sh
+#
+# Copyright (c) 2010 Bo Yang
+#
+
+test_description='Test git log -L with single line of history
+
+'
+. ./test-lib.sh
+. "$TEST_DIRECTORY"/diff-lib.sh
+
+echo >path0 'void func(){
+	int a = 0;
+	int b = 1;
+	int c;
+	c = a + b;
+}
+'
+
+echo >path1 'void output(){
+	printf("hello world");
+}
+'
+
+test_expect_success \
+    'add path0/path1 and commit.' \
+    'git add path0 path1 &&
+     git commit -m "Base commit"'
+
+echo >path0 'void func(){
+	int a = 10;
+	int b = 11;
+	int c;
+	c = a + b;
+}
+'
+
+echo >path1 'void output(){
+	const char *str = "hello world!";
+	printf("%s", str);
+}
+'
+
+test_expect_success \
+    'Change the 2,3 lines of path0 and path1.' \
+    'git add path0 path1 &&
+     git commit -m "Change 2,3 lines of path0 and path1"'
+
+echo >path0 'void func(){
+	int a = 10;
+	int b = 11;
+	int c;
+	c = 10 * (a + b);
+}
+'
+
+test_expect_success \
+	'Change the 5th line of path0.' \
+	'git add path0 &&
+	 git commit -m "Change the 5th line of path0"'
+
+echo >path0 'void func(){
+	int a = 10;
+	int b = 11;
+	printf("%d", a - b);
+}
+'
+
+test_expect_success \
+	'Final change of path0.' \
+	'git add path0 &&
+	 git commit -m "Final change of path0"'
+
+cat >expected-path0 <<\EOF
+Final change of path0
+
+diff --git a/path0 b/path0
+index 44db133..1518c15 100644
+--- a/path0
++++ b/path0
+@@ -1,6 +1,5 @@
+ void func(){
+ 	int a = 10;
+ 	int b = 11;
+-	int c;
+-	c = 10 * (a + b);
++	printf("%d", a - b);
+ }
+
+Change the 5th line of path0
+
+diff --git a/path0 b/path0
+index 9ef1692..44db133 100644
+--- a/path0
++++ b/path0
+@@ -1,6 +1,6 @@
+ void func(){
+ 	int a = 10;
+ 	int b = 11;
+ 	int c;
+-	c = a + b;
++	c = 10 * (a + b);
+ }
+
+Change 2,3 lines of path0 and path1
+
+diff --git a/path0 b/path0
+index aabffdf..9ef1692 100644
+--- a/path0
++++ b/path0
+@@ -1,6 +1,6 @@
+ void func(){
+-	int a = 0;
+-	int b = 1;
++	int a = 10;
++	int b = 11;
+ 	int c;
+ 	c = a + b;
+ }
+
+Base commit
+
+diff --git a/path0 b/path0
+new file mode 100644
+index 0000000..aabffdf
+--- /dev/null
++++ b/path0
+@@ -0,0 +1,6 @@
++void func(){
++	int a = 0;
++	int b = 1;
++	int c;
++	c = a + b;
++}
+EOF
+
+cat >expected-path1 <<\EOF
+Change 2,3 lines of path0 and path1
+
+diff --git a/path1 b/path1
+index 997d841..1d711b5 100644
+--- a/path1
++++ b/path1
+@@ -1,3 +1,4 @@
+ void output(){
+-	printf("hello world");
++	const char *str = "hello world!";
++	printf("%s", str);
+ }
+
+Base commit
+
+diff --git a/path1 b/path1
+new file mode 100644
+index 0000000..997d841
+--- /dev/null
++++ b/path1
+@@ -0,0 +1,3 @@
++void output(){
++	printf("hello world");
++}
+EOF
+
+cat >expected-pathall <<\EOF
+Final change of path0
+
+diff --git a/path0 b/path0
+index 44db133..1518c15 100644
+--- a/path0
++++ b/path0
+@@ -1,6 +1,5 @@
+ void func(){
+ 	int a = 10;
+ 	int b = 11;
+-	int c;
+-	c = 10 * (a + b);
++	printf("%d", a - b);
+ }
+
+Change the 5th line of path0
+
+diff --git a/path0 b/path0
+index 9ef1692..44db133 100644
+--- a/path0
++++ b/path0
+@@ -1,6 +1,6 @@
+ void func(){
+ 	int a = 10;
+ 	int b = 11;
+ 	int c;
+-	c = a + b;
++	c = 10 * (a + b);
+ }
+
+Change 2,3 lines of path0 and path1
+
+diff --git a/path0 b/path0
+index aabffdf..9ef1692 100644
+--- a/path0
++++ b/path0
+@@ -1,6 +1,6 @@
+ void func(){
+-	int a = 0;
+-	int b = 1;
++	int a = 10;
++	int b = 11;
+ 	int c;
+ 	c = a + b;
+ }
+diff --git a/path1 b/path1
+index 997d841..1d711b5 100644
+--- a/path1
++++ b/path1
+@@ -1,3 +1,4 @@
+ void output(){
+-	printf("hello world");
++	const char *str = "hello world!";
++	printf("%s", str);
+ }
+
+Base commit
+
+diff --git a/path0 b/path0
+new file mode 100644
+index 0000000..aabffdf
+--- /dev/null
++++ b/path0
+@@ -0,0 +1,6 @@
++void func(){
++	int a = 0;
++	int b = 1;
++	int c;
++	c = a + b;
++}
+diff --git a/path1 b/path1
+new file mode 100644
+index 0000000..997d841
+--- /dev/null
++++ b/path1
+@@ -0,0 +1,3 @@
++void output(){
++	printf("hello world");
++}
+EOF
+
+cat >expected-linenum <<\EOF
+Change 2,3 lines of path0 and path1
+
+diff --git a/path0 b/path0
+index aabffdf..9ef1692 100644
+--- a/path0
++++ b/path0
+@@ -1,2 +1,2 @@
+ void func(){
+-	int a = 0;
++	int a = 10;
+
+Base commit
+
+diff --git a/path0 b/path0
+new file mode 100644
+index 0000000..aabffdf
+--- /dev/null
++++ b/path0
+@@ -0,0 +1,2 @@
++void func(){
++	int a = 0;
+EOF
+
+cat >expected-always <<\EOF
+Final change of path0
+
+diff --git a/path0 b/path0
+index 44db133..1518c15 100644
+--- a/path0
++++ b/path0
+@@ -1,2 +1,2 @@
+ void func(){
+ 	int a = 10;
+
+Change the 5th line of path0
+
+diff --git a/path0 b/path0
+index 9ef1692..44db133 100644
+--- a/path0
++++ b/path0
+@@ -1,2 +1,2 @@
+ void func(){
+ 	int a = 10;
+
+Change 2,3 lines of path0 and path1
+
+diff --git a/path0 b/path0
+index aabffdf..9ef1692 100644
+--- a/path0
++++ b/path0
+@@ -1,2 +1,2 @@
+ void func(){
+-	int a = 0;
++	int a = 10;
+
+Base commit
+
+diff --git a/path0 b/path0
+new file mode 100644
+index 0000000..aabffdf
+--- /dev/null
++++ b/path0
+@@ -0,0 +1,2 @@
++void func(){
++	int a = 0;
+EOF
+
+test_expect_success \
+    'Show the line level log of path0' \
+    'git log --pretty=format:%s%n%b -L /func/,/^}/ path0 > current-path0'
+
+test_expect_success 'validate the path0 output.' '
+    test_cmp current-path0 expected-path0
+'
+test_expect_success \
+    'Show the line level log of path1' \
+    'git log --pretty=format:%s%n%b -L /output/,/^}/ path1 > current-path1'
+
+test_expect_success 'validate the path1 output.' '
+    test_cmp current-path1 expected-path1
+'
+test_expect_success \
+	'Show the line level log of two files' \
+    'git log --pretty=format:%s%n%b -L /func/,/^}/ path0 -L /output/,/^}/ path1 > current-pathall'
+
+test_expect_success 'validate the all path output.' '
+    test_cmp current-pathall expected-pathall
+'
+test_expect_success \
+	'Test the line number argument' \
+	'git log --pretty=format:%s%n%b -L 1,2 path0 > current-linenum'
+
+test_expect_success 'validate the line number output.' '
+    test_cmp current-linenum expected-linenum
+'
+test_expect_success \
+	'Test the --full-line-diff option' \
+	'git log --pretty=format:%s%n%b --full-line-diff -L 1,2 path0 > current-always'
+
+test_expect_success 'validate the --full-line-diff output.' '
+    test_cmp current-always expected-always
+'
+
+# Rerun all log with graph
+test_expect_success \
+    'Show the line level log of path0 with --graph' \
+    'git log --pretty=format:%s%n%b --graph -L /func/,/^}/ path0 > current-path0-graph'
+
+test_expect_success \
+    'Show the line level log of path1 with --graph' \
+    'git log --pretty=format:%s%n%b --graph -L /output/,/^}/ path1 > current-path1-graph'
+
+test_expect_success \
+    'Show the line level log of two files with --graph' \
+    'git log --pretty=format:%s%n%b --graph -L /func/,/^}/ path0 --graph -L /output/,/^}/ path1 > current-pathall-graph'
+
+test_expect_success \
+    'Test the line number argument with --graph' \
+    'git log --pretty=format:%s%n%b --graph -L 1,2 path0 > current-linenum-graph'
+
+test_expect_success \
+	'Test the --full-line-diff option with --graph option' \
+	'git log --pretty=format:%s%n%b --full-line-diff --graph -L 1,2 path0 > current-always-graph'
+
+cat > expected-path0-graph <<\EOF
+* Final change of path0
+| 
+| diff --git a/path0 b/path0
+| index 44db133..1518c15 100644
+| --- a/path0
+| +++ b/path0
+| @@ -1,6 +1,5 @@
+|  void func(){
+|  	int a = 10;
+|  	int b = 11;
+| -	int c;
+| -	c = 10 * (a + b);
+| +	printf("%d", a - b);
+|  }
+|  
+* Change the 5th line of path0
+| 
+| diff --git a/path0 b/path0
+| index 9ef1692..44db133 100644
+| --- a/path0
+| +++ b/path0
+| @@ -1,6 +1,6 @@
+|  void func(){
+|  	int a = 10;
+|  	int b = 11;
+|  	int c;
+| -	c = a + b;
+| +	c = 10 * (a + b);
+|  }
+|  
+* Change 2,3 lines of path0 and path1
+| 
+| diff --git a/path0 b/path0
+| index aabffdf..9ef1692 100644
+| --- a/path0
+| +++ b/path0
+| @@ -1,6 +1,6 @@
+|  void func(){
+| -	int a = 0;
+| -	int b = 1;
+| +	int a = 10;
+| +	int b = 11;
+|  	int c;
+|  	c = a + b;
+|  }
+|  
+* Base commit
+  
+  diff --git a/path0 b/path0
+  new file mode 100644
+  index 0000000..aabffdf
+  --- /dev/null
+  +++ b/path0
+  @@ -0,0 +1,6 @@
+  +void func(){
+  +	int a = 0;
+  +	int b = 1;
+  +	int c;
+  +	c = a + b;
+  +}
+EOF
+
+cat > expected-path1-graph <<\EOF
+* Change 2,3 lines of path0 and path1
+| 
+| diff --git a/path1 b/path1
+| index 997d841..1d711b5 100644
+| --- a/path1
+| +++ b/path1
+| @@ -1,3 +1,4 @@
+|  void output(){
+| -	printf("hello world");
+| +	const char *str = "hello world!";
+| +	printf("%s", str);
+|  }
+|  
+* Base commit
+  
+  diff --git a/path1 b/path1
+  new file mode 100644
+  index 0000000..997d841
+  --- /dev/null
+  +++ b/path1
+  @@ -0,0 +1,3 @@
+  +void output(){
+  +	printf("hello world");
+  +}
+EOF
+
+cat > expected-pathall-graph <<\EOF
+* Final change of path0
+| 
+| diff --git a/path0 b/path0
+| index 44db133..1518c15 100644
+| --- a/path0
+| +++ b/path0
+| @@ -1,6 +1,5 @@
+|  void func(){
+|  	int a = 10;
+|  	int b = 11;
+| -	int c;
+| -	c = 10 * (a + b);
+| +	printf("%d", a - b);
+|  }
+|  
+* Change the 5th line of path0
+| 
+| diff --git a/path0 b/path0
+| index 9ef1692..44db133 100644
+| --- a/path0
+| +++ b/path0
+| @@ -1,6 +1,6 @@
+|  void func(){
+|  	int a = 10;
+|  	int b = 11;
+|  	int c;
+| -	c = a + b;
+| +	c = 10 * (a + b);
+|  }
+|  
+* Change 2,3 lines of path0 and path1
+| 
+| diff --git a/path0 b/path0
+| index aabffdf..9ef1692 100644
+| --- a/path0
+| +++ b/path0
+| @@ -1,6 +1,6 @@
+|  void func(){
+| -	int a = 0;
+| -	int b = 1;
+| +	int a = 10;
+| +	int b = 11;
+|  	int c;
+|  	c = a + b;
+|  }
+| diff --git a/path1 b/path1
+| index 997d841..1d711b5 100644
+| --- a/path1
+| +++ b/path1
+| @@ -1,3 +1,4 @@
+|  void output(){
+| -	printf("hello world");
+| +	const char *str = "hello world!";
+| +	printf("%s", str);
+|  }
+|  
+* Base commit
+  
+  diff --git a/path0 b/path0
+  new file mode 100644
+  index 0000000..aabffdf
+  --- /dev/null
+  +++ b/path0
+  @@ -0,0 +1,6 @@
+  +void func(){
+  +	int a = 0;
+  +	int b = 1;
+  +	int c;
+  +	c = a + b;
+  +}
+  diff --git a/path1 b/path1
+  new file mode 100644
+  index 0000000..997d841
+  --- /dev/null
+  +++ b/path1
+  @@ -0,0 +1,3 @@
+  +void output(){
+  +	printf("hello world");
+  +}
+EOF
+
+cat > expected-linenum-graph <<\EOF
+* Change 2,3 lines of path0 and path1
+| 
+| diff --git a/path0 b/path0
+| index aabffdf..9ef1692 100644
+| --- a/path0
+| +++ b/path0
+| @@ -1,2 +1,2 @@
+|  void func(){
+| -	int a = 0;
+| +	int a = 10;
+|  
+* Base commit
+  
+  diff --git a/path0 b/path0
+  new file mode 100644
+  index 0000000..aabffdf
+  --- /dev/null
+  +++ b/path0
+  @@ -0,0 +1,2 @@
+  +void func(){
+  +	int a = 0;
+EOF
+
+cat > expected-always-graph <<\EOF
+* Final change of path0
+| 
+| diff --git a/path0 b/path0
+| index 44db133..1518c15 100644
+| --- a/path0
+| +++ b/path0
+| @@ -1,2 +1,2 @@
+|  void func(){
+|  	int a = 10;
+|  
+* Change the 5th line of path0
+| 
+| diff --git a/path0 b/path0
+| index 9ef1692..44db133 100644
+| --- a/path0
+| +++ b/path0
+| @@ -1,2 +1,2 @@
+|  void func(){
+|  	int a = 10;
+|  
+* Change 2,3 lines of path0 and path1
+| 
+| diff --git a/path0 b/path0
+| index aabffdf..9ef1692 100644
+| --- a/path0
+| +++ b/path0
+| @@ -1,2 +1,2 @@
+|  void func(){
+| -	int a = 0;
+| +	int a = 10;
+|  
+* Base commit
+  
+  diff --git a/path0 b/path0
+  new file mode 100644
+  index 0000000..aabffdf
+  --- /dev/null
+  +++ b/path0
+  @@ -0,0 +1,2 @@
+  +void func(){
+  +	int a = 0;
+EOF
+
+test_expect_success \
+    'validate the path0 output.' \
+    'test_cmp current-path0-graph expected-path0-graph'
+test_expect_success \
+	'validate the path1 output.' \
+	'test_cmp current-path1-graph expected-path1-graph'
+test_expect_success \
+	'validate the all path output.' \
+	'test_cmp current-pathall-graph expected-pathall-graph'
+test_expect_success \
+	'validate graph output' \
+	'test_cmp current-linenum-graph expected-linenum-graph'
+test_expect_success \
+	'validate --full-line-diff output' \
+	'test_cmp current-always-graph expected-always-graph'
+
+test_done
diff --git a/t/t4302-log-line-merge-history.sh b/t/t4302-log-line-merge-history.sh
new file mode 100755
index 0000000..1536cc4
--- /dev/null
+++ b/t/t4302-log-line-merge-history.sh
@@ -0,0 +1,163 @@
+#!/bin/sh
+#
+# Copyright (c) 2010 Bo Yang
+#
+
+test_description='Test git log -L with merge commit
+
+'
+. ./test-lib.sh
+. "$TEST_DIRECTORY"/diff-lib.sh
+
+echo >path0 'void func(){
+	printf("hello");
+}
+'
+
+test_expect_success \
+    'Add path0 and commit.' \
+    'git add path0 &&
+     git commit -m "Base commit"'
+
+echo >path0 'void func(){
+	printf("hello earth");
+}
+'
+
+test_expect_success \
+    'Change path0 in master.' \
+    'git add path0 &&
+     git commit -m "Change path0 in master"'
+
+test_expect_success \
+	'Make a new branch from the base commit' \
+	'git checkout -b feature master^'
+
+echo >path0 'void func(){
+	print("hello moon");
+}
+'
+
+test_expect_success \
+    'Change path0 in feature.' \
+    'git add path0 &&
+     git commit -m "Change path0 in feature"'
+
+test_expect_success \
+	'Merge the master to feature' \
+	'! git merge master'
+
+echo >path0 'void func(){
+	printf("hello earth and moon");
+}
+'
+
+test_expect_success \
+	'Resolve the conflict' \
+	'git add path0 &&
+	 git commit -m "Merge two branches"'
+
+test_expect_success \
+    'Show the line level log of path0' \
+    'git log --pretty=format:%s%n%b -L /func/,/^}/ path0 > current'
+
+cat >expected <<\EOF
+Merge two branches
+
+nontrivial merge found
+path0
+@@ 2,1 @@
+ 	printf("hello earth and moon");
+
+
+Change path0 in master
+
+diff --git a/path0 b/path0
+index f628dea..bef7fa3 100644
+--- a/path0
++++ b/path0
+@@ -1,3 +1,3 @@
+ void func(){
+-	printf("hello");
++	printf("hello earth");
+ }
+
+Change path0 in feature
+
+diff --git a/path0 b/path0
+index f628dea..a940ef6 100644
+--- a/path0
++++ b/path0
+@@ -1,3 +1,3 @@
+ void func(){
+-	printf("hello");
++	print("hello moon");
+ }
+
+Base commit
+
+diff --git a/path0 b/path0
+new file mode 100644
+index 0000000..f628dea
+--- /dev/null
++++ b/path0
+@@ -0,0 +1,3 @@
++void func(){
++	printf("hello");
++}
+EOF
+
+cat > expected-graph <<\EOF
+*   Merge two branches
+|\  
+| | 
+| | nontrivial merge found
+| | path0
+| | @@ 2,1 @@
+| |  	printf("hello earth and moon");
+| | 
+| |   
+| * Change path0 in master
+| | 
+| | diff --git a/path0 b/path0
+| | index f628dea..bef7fa3 100644
+| | --- a/path0
+| | +++ b/path0
+| | @@ -2,1 +2,1 @@
+| | -	printf("hello");
+| | +	printf("hello earth");
+| |   
+* | Change path0 in feature
+|/  
+|   
+|   diff --git a/path0 b/path0
+|   index f628dea..a940ef6 100644
+|   --- a/path0
+|   +++ b/path0
+|   @@ -2,1 +2,1 @@
+|   -	printf("hello");
+|   +	print("hello moon");
+|  
+* Base commit
+  
+  diff --git a/path0 b/path0
+  new file mode 100644
+  index 0000000..f628dea
+  --- /dev/null
+  +++ b/path0
+  @@ -0,0 +2,1 @@
+  +	printf("hello");
+EOF
+
+test_expect_success \
+    'Show the line log of the 2 line of path0 with graph' \
+    'git log --pretty=format:%s%n%b --graph -L 2,+1 path0 > current-graph'
+
+test_expect_success \
+    'validate the output.' \
+    'test_cmp current expected'
+test_expect_success \
+    'validate the graph output.' \
+    'test_cmp current-graph expected-graph'
+
+test_done
-- 
1.7.2.19.g79e5d

[PATCH V5 17/17] Document line history browser

[Bo Yang]

Both 'git log' and 'git blame' support the same format
of '-L' arguments, so we refactor its description into
a new file.

And it is possible to use more than one '-L' option
for each path.

Signed-off-by: Bo Yang <struggleyb.nku@gmail.com>
---
 Documentation/blame-options.txt     |   19 +------------------
 Documentation/git-log.txt           |   15 +++++++++++++++
 Documentation/line-range-format.txt |   18 ++++++++++++++++++
 3 files changed, 34 insertions(+), 18 deletions(-)
 create mode 100644 Documentation/line-range-format.txt

diff --git a/Documentation/blame-options.txt b/Documentation/blame-options.txt
index 16e3c68..3526835 100644
--- a/Documentation/blame-options.txt
+++ b/Documentation/blame-options.txt
@@ -13,24 +13,7 @@
 	Annotate only the given line range.  <start> and <end> can take
 	one of these forms:
 
-	- number
-+
-If <start> or <end> is a number, it specifies an
-absolute line number (lines count from 1).
-+
-
-- /regex/
-+
-This form will use the first line matching the given
-POSIX regex.  If <end> is a regex, it will search
-starting at the line given by <start>.
-+
-
-- +offset or -offset
-+
-This is only valid for <end> and will specify a number
-of lines before or after the line given by <start>.
-+
+include::line-range-format.txt[]
 
 -l::
 	Show long rev (Default: off).
diff --git a/Documentation/git-log.txt b/Documentation/git-log.txt
index e970664..6f712e7 100644
--- a/Documentation/git-log.txt
+++ b/Documentation/git-log.txt
@@ -9,6 +9,7 @@ git-log - Show commit logs
 SYNOPSIS
 --------
 'git log' [<options>] [<since>..<until>] [[\--] <path>...]
+'git log' [<options>] -L n,m <path>
 
 DESCRIPTION
 -----------
@@ -19,6 +20,9 @@ command to control what is shown and how, and options applicable to
 the 'git diff-*' commands to control how the changes
 each commit introduces are shown.
 
+With '-L' option, the command will help to trace the history of user specified
+line ranges. It can trace multiple ranges coming from multiple files.
+
 
 OPTIONS
 -------
@@ -63,6 +67,17 @@ OPTIONS
 	Note that only message is considered, if also a diff is shown
 	its size is not included.
 
+-L <start>,<end>::
+	The line range.  <start> and <end> can take one of these forms:
+
+include::line-range-format.txt[]
+You can also specify this option more than once before each path.
+
+
+--full-line-diff::
+	Always print the interesting range even if the current commit
+	does not change any line of the range.
+
 [\--] <path>...::
 	Show only commits that affect any of the specified paths. To
 	prevent confusion with options and branch names, paths may need
diff --git a/Documentation/line-range-format.txt b/Documentation/line-range-format.txt
new file mode 100644
index 0000000..265bc23
--- /dev/null
+++ b/Documentation/line-range-format.txt
@@ -0,0 +1,18 @@
+- number
++
+If <start> or <end> is a number, it specifies an
+absolute line number (lines count from 1).
++
+
+- /regex/
++
+This form will use the first line matching the given
+POSIX regex.  If <end> is a regex, it will search
+starting at the line given by <start>.
++
+
+- +offset or -offset
++
+This is only valid for <end> and will specify a number
+of lines before or after the line given by <start>.
++
-- 
1.7.2.19.g79e5d

Re: [PATCH V5 16/17] Add tests for line history browser

[Ævar Arnfjörð Bjarmason]

On Wed, Aug 11, 2010 at 15:03, Bo Yang <struggleyb.nku@gmail.com> wrote:
> t/t4301-log-line-single-history.sh:
>  test the linear line of history.
>
> t/t4302-log-line-merge-history.sh:
>  test the case that there are merges in the history.

This is failing smoke tests on my smoker:
http://smoke.git.nix.is/app/projects/report_details/21

> Signed-off-by: Bo Yang <struggleyb.nku@gmail.com>

> +test_expect_success 'validate the path0 output.' '
> +    test_cmp current-path0 expected-path0
> +'

That gives me:

    $ diff -ru trash\
directory.t4301-log-line-single-history/{expected,current}-path0
    --- trash directory.t4301-log-line-single-history/expected-path0
     2010-08-12 01:20:18.000000000 +0000
    +++ trash directory.t4301-log-line-single-history/current-path0
2010-08-12 01:20:18.000000000 +0000
    @@ -6,8 +6,8 @@
     +++ b/path0
     @@ -1,6 +1,5 @@
      void func(){
    -       int a = 10;
    -       int b = 11;
    +       int a = 10;
    +       int b = 11;
     -      int c;
     -      c = 10 * (a + b);
     +      printf("%d", a - b);
    @@ -21,9 +21,9 @@
     +++ b/path0
     @@ -1,6 +1,6 @@
      void func(){
    -       int a = 10;
    -       int b = 11;
    -       int c;
    +       int a = 10;
    +       int b = 11;
    +       int c;
     -      c = a + b;
     +      c = 10 * (a + b);
      }
    @@ -40,8 +40,8 @@
     -      int b = 1;
     +      int a = 10;
     +      int b = 11;
    -       int c;
    -       c = a + b;
    +       int c;
    +       c = a + b;
      }

     Base commit


> [...]

More of these test fails, see the TAP output at the smoker.

> diff --git a/t/t4302-log-line-merge-history.sh b/t/t4302-log-line-merge-history.sh
> new file mode 100755
> index 0000000..1536cc4
> --- /dev/null

[...]

> +test_expect_success \
> +    'validate the output.' \
> +    'test_cmp current expected'

Gives:

    $ diff -ru trash\ directory.t4302-log-line-merge-history/{expected,current}
    --- trash directory.t4302-log-line-merge-history/expected
2010-08-12 01:21:47.000000000 +0000
    +++ trash directory.t4302-log-line-merge-history/current
2010-08-12 01:21:47.000000000 +0000
    @@ -3,7 +3,7 @@
     nontrivial merge found
     path0
     @@ 2,1 @@
    -       printf("hello earth and moon");
    +       printf("hello earth and moon");


     Change path0 in master

That's just a whitespace change, the diff goes away on diff -w.

> +test_expect_success \
> +    'validate the graph output.' \
> +    'test_cmp current-graph expected-graph'
> +

More whitespace changes:

    $ diff -ru trash\
directory.t4302-log-line-merge-history/{expected,current}-graph
    --- trash directory.t4302-log-line-merge-history/expected-graph
2010-08-12 01:23:53.000000000 +0000
    +++ trash directory.t4302-log-line-merge-history/current-graph
2010-08-12 01:23:53.000000000 +0000
    @@ -1,14 +1,14 @@
     *   Merge two branches
    -|\
    -| |
    +|\
    +| |
     | | nontrivial merge found
     | | path0
     | | @@ 2,1 @@
     | |    printf("hello earth and moon");
    -| |
    -| |
    +| |
    +| |
     | * Change path0 in master
    -| |
    +| |
     | | diff --git a/path0 b/path0
     | | index f628dea..bef7fa3 100644
     | | --- a/path0
    @@ -16,10 +16,10 @@
     | | @@ -2,1 +2,1 @@
     | | -  printf("hello");
     | | +  printf("hello earth");
    -| |
    +| |
     * | Change path0 in feature
    -|/
    -|
    +|/
    +|
     |   diff --git a/path0 b/path0
     |   index f628dea..a940ef6 100644
     |   --- a/path0
    @@ -27,9 +27,9 @@
     |   @@ -2,1 +2,1 @@
     |   -  printf("hello");
     |   +  print("hello moon");
    -|
    +|
     * Base commit
    -
    +
       diff --git a/path0 b/path0
       new file mode 100644
       index 0000000..f628dea

Re: [PATCH V5 00/17] Reroll a version 5 of this series

[david]

what is this series?

this is all good incramental information, but there's no info indicating 
what this is updating.

David Lang

On Wed, 11 Aug 2010, Bo Yang wrote:

> Changes:
> 1. Fix all format problems;
> 2. Split the "too long" lines in multiple lines;
> 3. '$' to represent the last line of a file;
> 4. Error string change;
> 5. Add more comments;
> 6. Combine test cases together;
> 7. Struct name change
>
> Bo Yang (17):
>  parse-options: enhance STOP_AT_NON_OPTION
>  parse-options: add two helper functions
>  Add the basic data structure for line level history
>  Refactor parse_loc
>  Parse the -L options
>  Export three functions from diff.c
>  Add range clone functions
>  map/take range to the parent of commits
>  Print the line log
>  Hook line history into cmd_log, ensuring a topo-ordered walk
>  Make rewrite_parents public to other part of git
>  Make graph_next_line external to other part of git
>  Add parent rewriting to line history browser
>  Add --graph prefix before line history output
>  Add --full-line-diff option
>  Add tests for line history browser
>  Document line history browser
>
> Documentation/blame-options.txt     |   19 +-
> Documentation/git-log.txt           |   15 +
> Documentation/line-range-format.txt |   18 +
> Makefile                            |    2 +
> builtin/blame.c                     |   89 +--
> builtin/log.c                       |  113 +++-
> diff.c                              |    6 +-
> diff.h                              |   17 +
> graph.c                             |   14 +-
> graph.h                             |   10 +
> line.c                              | 1551 +++++++++++++++++++++++++++++++++++
> line.h                              |  141 ++++
> parse-options.c                     |   22 +-
> parse-options.h                     |    7 +-
> revision.c                          |   25 +-
> revision.h                          |   23 +-
> t/t4301-log-line-single-history.sh  |  627 ++++++++++++++
> t/t4302-log-line-merge-history.sh   |  163 ++++
> 18 files changed, 2733 insertions(+), 129 deletions(-)
> create mode 100644 Documentation/line-range-format.txt
> create mode 100644 line.c
> create mode 100644 line.h
> create mode 100755 t/t4301-log-line-single-history.sh
> create mode 100755 t/t4302-log-line-merge-history.sh
>
>

Re: [PATCH V5 16/17] Add tests for line history browser

[Bo Yang]

Hi Ævar,

   Seems this is the SP problem. Do you apply this series with
--whitespace=fix ? This will erase some spaces in the diff files,
so...

-- 
Regards!
Bo
----------------------------
My blog: http://blog.morebits.org
Why Git: http://www.whygitisbetterthanx.com/

Re: [PATCH V5 16/17] Add tests for line history browser

[Ævar Arnfjörð Bjarmason]

On Thu, Aug 12, 2010 at 12:24, Bo Yang <struggleyb.nku@gmail.com> wrote:
> Hi Ævar,
>
>   Seems this is the SP problem. Do you apply this series with
> --whitespace=fix ? This will erase some spaces in the diff files,

I just pulled it down from pu, maybe Junio applied it like that.

Try pulling down pu and testing, do you have failures?

Re: [PATCH V5 00/17] Reroll a version 5 of this series

[Junio C Hamano]

Bo Yang <struggleyb.nku@gmail.com> writes:

> 3. '$' to represent the last line of a file;

That is probably a nice addition but a literal '$' is rather hard to type
from the shell.  I thought "-L n," already meant the same thing as
"starting at line n thru the end"?

It appears that this, when applied to v1.7.2 (with minimum compilation
fixes), does not pass its own self test.  I haven't looked at the details
but will queue the series to 'pu'.

Re: [PATCH V5 16/17] Add tests for line history browser

[Junio C Hamano]

Bo Yang <struggleyb.nku@gmail.com> writes:

>    Seems this is the SP problem. Do you apply this series with
> --whitespace=fix ? This will erase some spaces in the diff files,
> so...

That probably is it.  Your patches have other whitespace breakages (mostly
"new blank line at EOF") that I had to use --whitespace=fix to correct
them.

Re: [PATCH V5 16/17] Add tests for line history browser

[Junio C Hamano]

Bo Yang <struggleyb.nku@gmail.com> writes:

> +test_description='Test git log -L with single line of history
> +
> +'
> +. ./test-lib.sh
> +. "$TEST_DIRECTORY"/diff-lib.sh
> +
> +echo >path0 'void func(){
> +	int a = 0;
> +	int b = 1;
> +	int c;
> +	c = a + b;
> +}
> +'

Please do not have a set-up code like this one outside of test.

You may want to also adjust the coding style of the sample code ;-)  The
brace at the beginning of a function body sits at the leftmost column.

> +echo >path1 'void output(){
> +	printf("hello world");
> +}
> +'
> +
> +test_expect_success \
> +    'add path0/path1 and commit.' \
> +    'git add path0 path1 &&
> +     git commit -m "Base commit"'

And these days we indent and quote like this:

	test_expect_success 'what this test does' '
        	the body of the
                test
                comes
                here
	'

which makes it easier to read and by not requiring excessive use of
backslashes.

Perhaps like this (or use 'sed -e "s/^	|//"' instead of cat and indent the
here text by one tabstop plus a vertical bar)?

test_expect_success 'add path0/path1 and commit' '
	cat >path0 <<\EOF &&
void func(void)
{
        int a = 0;
        int b = 1;
	int c;
        c = a + b;
}
EOF
	cat >path1 <<\EOF &&
void output(void)
{
        printf("Hello, World!");
}
EOF
	git add path0 path1 &&
        test_tick &&
        git commit -m "Base commit"
'

log -L crash (Re: [PATCH V5 13/17] Add parent rewriting to line history browser)

[Jonathan Nieder]

Hi Bo et al,

The following test fails (segfaults) for me.  It bisects to 83361f5
(Add parent rewriting to line history browser, 2010-08-11).  Notes
from --valgrind:

	Invalid read of size 4
	   at assign_parents_range (line.c:1069)
	   by cmd_line_log_walk (line.c:1403)
	   by cmd_log (log.c:619)
	   by handle_internal_command (git.c:270)
	   by main (git.c:470)
	 Address 0x432a90c is 4 bytes inside a block of size 8 free'd
	   at free (vg_replace_malloc.c:366)
	   by assign_range_to_parent (line.c:964)
	   by assign_parents_range (line.c:1036)
	   by cmd_line_log_walk (line.c:1403)
	   by cmd_log (log.c:619)
	   by handle_internal_command (git.c:270)
	   by main (git.c:470)
 
	Invalid read of size 4
	   at assign_parents_range (line.c:1041)
	   by cmd_line_log_walk (line.c:1403)
	   by cmd_log (log.c:619)
	   by handle_internal_command (git.c:270)
	   by main (git.c:470)
	 Address 0x0 is not stack'd, malloc'd or (recently) free'd

	Process terminating with default action of signal 11 (SIGSEGV): dumping core
	 Access not within mapped region at address 0x0
	   at assign_parents_range (line.c:1041)
	   by cmd_line_log_walk (line.c:1403)
	   by cmd_log (log.c:619)
	   by handle_internal_command (git.c:270)
	   by main (git.c:470)
	 If you believe this happened as a result of a stack
	 overflow in your program's main thread (unlikely but
	 possible), you can try to increase the size of the
	 main thread stack using the --main-stacksize= flag.
	 The main thread stack size used in this run was 8388608.

Ideas?

diff --git a/t/t0011-crash.sh b/t/t0011-crash.sh
index e69de29..5cb3ef3 100644
--- a/t/t0011-crash.sh
+++ b/t/t0011-crash.sh
@@ -0,0 +1,11 @@
+#!/bin/sh
+
+test_description=crash
+. ./test-lib.sh
+
+test_expect_success "doesn't crash" '
+	GIT_DIR="$TEST_DIRECTORY"/../.git \
+		git log -L "/while (1) {/,/}/" git.c
+'
+
+test_done
-- 

Re: log -L crash (Re: [PATCH V5 13/17] Add parent rewriting to line history browser)

[Bo Yang]

Hi Jonathan,

   Thanks a lot for providing such a detail valgrind trace output, I
will find out what happened to the code in this Friday, and give a fix
then. Thanks again for let me know it. Thanks!

On Tue, Aug 31, 2010 at 1:10 AM, Jonathan Nieder <jrnieder@gmail.com> wrote:
> Hi Bo et al,
>
> The following test fails (segfaults) for me.  It bisects to 83361f5
> (Add parent rewriting to line history browser, 2010-08-11).  Notes
> from --valgrind:
>
>        Invalid read of size 4
>           at assign_parents_range (line.c:1069)
>           by cmd_line_log_walk (line.c:1403)
>           by cmd_log (log.c:619)
>           by handle_internal_command (git.c:270)
>           by main (git.c:470)
>         Address 0x432a90c is 4 bytes inside a block of size 8 free'd
>           at free (vg_replace_malloc.c:366)
>           by assign_range_to_parent (line.c:964)
>           by assign_parents_range (line.c:1036)
>           by cmd_line_log_walk (line.c:1403)
>           by cmd_log (log.c:619)
>           by handle_internal_command (git.c:270)
>           by main (git.c:470)
>
>        Invalid read of size 4
>           at assign_parents_range (line.c:1041)
>           by cmd_line_log_walk (line.c:1403)
>           by cmd_log (log.c:619)
>           by handle_internal_command (git.c:270)
>           by main (git.c:470)
>         Address 0x0 is not stack'd, malloc'd or (recently) free'd
>
>        Process terminating with default action of signal 11 (SIGSEGV): dumping core
>         Access not within mapped region at address 0x0
>           at assign_parents_range (line.c:1041)
>           by cmd_line_log_walk (line.c:1403)
>           by cmd_log (log.c:619)
>           by handle_internal_command (git.c:270)
>           by main (git.c:470)
>         If you believe this happened as a result of a stack
>         overflow in your program's main thread (unlikely but
>         possible), you can try to increase the size of the
>         main thread stack using the --main-stacksize= flag.
>         The main thread stack size used in this run was 8388608.
>
> Ideas?
>
> diff --git a/t/t0011-crash.sh b/t/t0011-crash.sh
> index e69de29..5cb3ef3 100644
> --- a/t/t0011-crash.sh
> +++ b/t/t0011-crash.sh
> @@ -0,0 +1,11 @@
> +#!/bin/sh
> +
> +test_description=crash
> +. ./test-lib.sh
> +
> +test_expect_success "doesn't crash" '
> +       GIT_DIR="$TEST_DIRECTORY"/../.git \
> +               git log -L "/while (1) {/,/}/" git.c
> +'
> +
> +test_done
> --
>



-- 
Regards!
Bo
----------------------------
My blog: http://blog.morebits.org
Why Git: http://www.whygitisbetterthanx.com/

[PATCH] log -L: do not free parents lists we might need again

[Thomas Rast]

The parent rewriting code of 'git log -L' was too aggressive in
freeing memory: assign_range_to_parent() will free the commit->parents
field when it sees that a parent cannot pass off any blame (is a root
commit in rewritten history).

Its caller assign_parents_range() however will, upon finding the first
parent that takes *full* blame for all ranges, rewind and reinstate
all previous parents' line ranges and parent lists.  This resurrects
pointers to ranges that were freed in assign_range_to_parent() under
some circumstances.

Furthermore, we must not empty the parent lists either: the same
rewind/reinstate code relies on them.

Do both only if the commit was an ordinary (not merge or root) commit,
in which case the merge code-path discussed here is never taken.

Reported-by: Jonathan Nieder <jrnieder@gmail.com>
Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---
[sorry for the double post, forgot to cc the list]

After staring at it for some time, I think this is the problem.

Sadly I cannot come up with an independent test that reproduces it (or
at least generates a valgrind warning).  Based on my analysis I tried

 diff --git a/t/t4302-log-line-merge-history.sh b/t/t4302-log-line-merge-history.sh
 index 8634116..7c86903 100755
 --- a/t/t4302-log-line-merge-history.sh
 +++ b/t/t4302-log-line-merge-history.sh
 @@ -171,4 +171,17 @@ test_expect_success 'validate the graph output.' '
  	test_cmp current-graph expected-graph
  '
  
 +test_expect_success 'set up trivial side merge' '
 +	git checkout -b trivial-side &&
 +	echo new_line >> path0 &&
 +	git add path0 &&
 +	git commit -m new_line &&
 +	git checkout master &&
 +	git merge --no-ff trivial-side
 +'
 +
 +test_expect_success 'log -L on the trivial-merged file' '
 +	git log -L /new_line/,+1 path0
 +'
 +
  test_done

but that does not fail.  I am hesitant to add your original test
because it strays into the directory where git was built, to test with
git's own history.  It just feels wrong.


 line.c |    6 ++++--
 1 files changed, 4 insertions(+), 2 deletions(-)

diff --git a/line.c b/line.c
index 63dd19a..b0deafb 100644
--- a/line.c
+++ b/line.c
@@ -961,8 +961,10 @@ static int assign_range_to_parent(struct rev_info *rev, struct commit *c,
 		 * If there is no new ranges assigned to the parent,
 		 * we should mark it as a 'root' commit.
 		 */
-		free(c->parents);
-		c->parents = NULL;
+		if (c->parents && !c->parents->next) {
+			free(c->parents);
+			c->parents = NULL;
+		}
 	}
 
 	/* and the ranges of current commit c is updated */
-- 
1.7.3.rc1.333.gf62981