Skip to contentSkip to conversation

Export three functions from diff.c

PATCH In review Thomas Rast 2 participants 10 messages Jun 15, 2016 1 message not in the archive

Subsystems (2)
lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw

cover git log -L, cleaned up and (hopefully) fixed

Quoted 11 lines · Junio C Hamano

This patch set has too many whitespace errors, and worse yet, cannot be applied with "git am --whitespace=fix" because it has test vectors that depend on having "SP followed by HT" (context lines of diff output) and traling SP (graph output).

Could you please straighten that out first?

My preference is to protect offending whitespaces like this:

	sed -e 's/Q/ /g' -e 's/Z$//' >expected-no-M <<\EOF

[...]

Quoted 1 line

which has an added benefit of making them more visible.

Sorry for the mess. I stuck to the s/#$// style I already had in some places for now, but used the Qs and ran the rest through whitespace=fix. It now applies cleanly to master.

Bo Yang (8):
Refactor parse_loc
Export three functions from diff.c
Export rewrite_parents() for 'log -L'
Implement line-history search (git log -L)
log -L: support parent rewriting
log -L: add --graph prefix before output
log -L: add --full-line-diff option
log -L: implement move/copy detection (-M/-C)

 Documentation/blame-options.txt     |   19 +-
 Documentation/git-log.txt           |   22 +
 Documentation/line-range-format.txt |   18 +
 Makefile                            |    2 +
 builtin/blame.c                     |   99 +--
 builtin/log.c                       |   79 ++-
 diff.c                              |    6 +-
 diff.h                              |   17 +
 line.c                              | 2153 +++++++++++++++++++++++++++++++++++
 line.h                              |   72 ++
 revision.c                          |   22 +-
 revision.h                          |   23 +-
 t/t4301-log-line-single-history.sh  |  685 +++++++++++
 t/t4302-log-line-merge-history.sh   |  174 +++
 t/t4303-log-line-move-detect.sh     |  238 ++++
 t/t4304-log-line-copy-detect.sh     |  220 ++++
 t/t8003-blame-corner-cases.sh       |    6 +
 17 files changed, 3730 insertions(+), 125 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
 create mode 100755 t/t4303-log-line-move-detect.sh
 create mode 100755 t/t4304-log-line-copy-detect.sh
Signature · 1 line
1.7.3.3.807.g6ee1f
#2 lore raw

PATCH 1/8 Refactor parse_loc

From: Bo Yang <[email protected]>

We want to use the same style of -L n,m argument for 'git log -L' as for git-blame. Refactor the argument parsing of the range arguments from builtin/blame.c to the (new) file that will hold the 'git log -L' logic.

To accommodate different data structures in blame and log -L, the file contents are abstracted away; parse_range_arg takes a callback that it uses to get the contents of a line of the (notional) file.

The new test is for a case that made me pause during debugging: the 'blame -L with invalid end' test was the only one that noticed an outright failure to parse the end *at all*. So make a more explicit test for that.

---
 Makefile                      |    2 +
 builtin/blame.c               |   99 +++-----------------------------------
 line.c                        |  106 +++++++++++++++++++++++++++++++++++++++++
 line.h                        |   23 +++++++++
 t/t8003-blame-corner-cases.sh |    6 ++
 5 files changed, 145 insertions(+), 91 deletions(-)
 create mode 100644 line.c
 create mode 100644 line.h
Makefile +2 -0
index 57d9c65..b015c61 100644
@@ -519,6 +519,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
@@ -606,6 +607,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
builtin/blame.c +8 -91

133 lines not on this page · raw message

line.c new file +106 -0

106 lines not on this page · raw message

line.h new file +23 -0
new file mode 100644
index 0000000..5878c94
@@ -0,0 +1,23 @@
+#ifndef LINE_H
+#define LINE_H
+
+/*
+ * Parse one item in an -L begin,end option w.r.t. the notional file
+ * object 'cb_data' consisting of 'lines' lines.
+ *
+ * The 'nth_line_cb' callback is used to determine the start of the
+ * line 'lno' inside the 'cb_data'.  The caller is expected to already
+ * have a suitable map at hand to make this a constant-time lookup.
+ *
+ * Returns 0 in case of success and -1 if there was an error.  The
+ * caller should print a usage message in the latter case.
+ */
+
+typedef const char *(*nth_line_fn_t)(void *data, long lno);
+
+extern int parse_range_arg(const char *arg,
+			   nth_line_fn_t nth_line_cb,
+			   void *cb_data, long lines,
+			   long *begin, long *end);
+
+#endif /* LINE_H */
t/t8003-blame-corner-cases.sh +6 -0
index 230143c..51d313e 100755
@@ -175,6 +175,12 @@ test_expect_success 'blame -L with invalid end' '
 	grep "has only 2 lines" errors
 '
 
+test_expect_success 'blame -L parses end' '
+	git blame -L1,1 tres >out &&
+	cat out &&
+	test $(wc -l < out) -eq 1
+'
+
 test_expect_success 'indent of line numbers, nine lines' '
 	git blame nine_lines >actual &&
 	test $(grep -c "  " actual) = 0
Signature · 1 line
1.7.3.3.807.g6ee1f
#3 lore raw

PATCH 2/8 Export three functions from diff.c

In reply to Thomas Rast

From: Bo Yang <[email protected]>

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

---
 diff.c |    6 +++---
 diff.h |   17 +++++++++++++++++
 2 files changed, 20 insertions(+), 3 deletions(-)
diff.c +3 -3
index 0a43869..a16ce69 100644
@@ -151,7 +151,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);
@@ -332,7 +332,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);
@@ -2583,7 +2583,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.h +17 -0
index 0083d92..165f368 100644
@@ -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,
@@ -317,4 +318,20 @@ extern struct userdiff_driver *get_textconv(struct diff_filespec *one);
 
 extern int parse_rename_score(const char **cp_p);
 
+/* 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 */
Signature · 1 line
1.7.3.3.807.g6ee1f
#4 lore raw

PATCH 3/8 Export rewrite_parents() for 'log -L'

In reply to Thomas Rast

From: Bo Yang <[email protected]>

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.

---
 revision.c |   13 ++++---------
 revision.h |   10 ++++++++++
 2 files changed, 14 insertions(+), 9 deletions(-)
revision.c +4 -9
index ded8812..6465c45 100644
@@ -1912,12 +1912,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;
@@ -1939,12 +1933,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:
@@ -2012,7 +2007,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;
revision.h +10 -0
index 05659c6..8897368 100644
@@ -193,4 +193,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
Signature · 1 line
1.7.3.3.807.g6ee1f
#5 lore raw

PATCH 4/8 Implement line-history search (git log -L)

In reply to Thomas Rast

From: Bo Yang <[email protected]>

'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.

When going from a commit to its parents, we map the "interesting" range of lines according to the change made. For non-merge commits, 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. After that 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.

To correctly track the line ranges over several branches, we must make sure that we have processed all children before reaching the commit itself. So we let the revision machinery topo-order the commits before doing anything.

---
 Documentation/blame-options.txt     |   19 +-
 Documentation/git-log.txt           |   18 +
 Documentation/line-range-format.txt |   18 +
 builtin/log.c                       |   73 ++-
 line.c                              | 1331 ++++++++++++++++++++++++++++++++++-
 line.h                              |   49 ++
 revision.c                          |    6 +
 revision.h                          |   11 +-
 t/t4301-log-line-single-history.sh  |  685 ++++++++++++++++++
 9 files changed, 2186 insertions(+), 24 deletions(-)
 create mode 100644 Documentation/line-range-format.txt
 create mode 100755 t/t4301-log-line-single-history.sh
Documentation/blame-options.txt +1 -18
index 16e3c68..3526835 100644
@@ -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).
Documentation/git-log.txt +18 -0
index ff41784..7fcf6e7 100644
@@ -66,6 +66,19 @@ produced by --stat etc.
 	Note that only message is considered, if also a diff is shown
 	its size is not included.
 
+-L <start>,<end>:<file>::
+	Trace the evolution of the line range given by "<start>,<end>"
+	within the <file>.  You may not give any pathspec limiters.
+	This is currently limited to a walk starting from a single
+	revision, i.e., you may only give zero or one positive
+	revision arguments.
+
+<start> and <end> can take one of these forms:
+
+include::line-range-format.txt[]
+You can specify this option more than once.
+
+
 [\--] <path>...::
 	Show only commits that affect any of the specified paths. To
 	prevent confusion with options and branch names, paths may need
@@ -132,6 +145,11 @@ git log -p -m --first-parent::
 	This makes sense only when following a strict policy of merging all
 	topic branches when staying on a single integration branch.
 
+git log -L '/int main/',/^}/:main.c::
+
+	Shows how the function `main()` in the file 'main.c' evolved
+	over time.
+
 
 Discussion
 ----------
Documentation/line-range-format.txt new file +18 -0
new file mode 100644
index 0000000..265bc23
@@ -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>.
++
builtin/log.c +71 -2

118 lines not on this page · raw message

line.c +1329 -2

1,364 lines not on this page · raw message

line.h +49 -0

59 lines not on this page · raw message

revision.c +6 -0
index 6465c45..369ec56 100644
@@ -1662,6 +1662,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");
 
revision.h +9 -2
index 8897368..585b15f 100644
@@ -14,7 +14,10 @@
 #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 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
@@ -68,7 +71,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 +141,9 @@ struct rev_info {
 	/* commit counts */
 	int count_left;
 	int count_right;
+	/* line level range that we are chasing */
+	struct decoration line_range;
+	struct decoration nontrivial_merge;
 };
 
 #define REV_TREE_SAME		0
t/t4301-log-line-single-history.sh new file +685 -0

685 lines not on this page · raw message

Signature · 1 line
1.7.3.3.807.g6ee1f
#6 lore raw

Re: [PATCH v6.1 4/8] Implement line-history search (git log -L)

Quoted 5 lines · Thomas Rast
line.c +5 -0
+void line_log_init(struct rev_info *rev, struct diff_line_range *r)
+{
+	struct commit *commit = NULL;
+	struct diff_options *opt = &rev->diffopt;
+

line.c int parse_range_arg(const char *arg, nth_line_fn_t nth_line_cb, · line 642

Quoted 10 lines
line.c +10 -0
+	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);
+}

Note that opt->nr_paths may be going away soon (cf. nd/struct-pathspec topic). Do you need this assignment here?

#7 lore raw

PATCH 5/8 log -L: support parent rewriting

In reply to Thomas Rast

From: Bo Yang <[email protected]>

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^.

---
 line.c                            |  208 +++++++++++++++++++++++++++++++-----
 revision.c                        |    1 +
 revision.h                        |    5 +-
 t/t4302-log-line-merge-history.sh |  174 +++++++++++++++++++++++++++++++
 4 files changed, 357 insertions(+), 31 deletions(-)
 create mode 100755 t/t4302-log-line-merge-history.sh
line.c +179 -29
index 1ffcaba..10870a5 100644
@@ -10,6 +10,7 @@
 #include "xdiff-interface.h"
 #include "strbuf.h"
 #include "log-tree.h"
+#include "graph.h"
 #include "line.h"
 
 struct print_range {
@@ -33,12 +34,6 @@ struct line_range {
 };
 
 /*
- * Eek-a-global
- */
-
-static int limited;
-
-/*
  * These could be in line.h but we put them here so the functions can
  * be static.
  */
@@ -596,14 +591,14 @@ static void add_line_range(struct rev_info *revs, struct commit *commit,
 {
 	struct diff_line_range *ret = NULL;
 
-	if (r) {
-		ret = lookup_decoration(&revs->line_range, &commit->object);
-		if (ret)
-			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 && r)
+		diff_line_range_merge(ret, r);
+	else
+		add_decoration(&revs->line_range, &commit->object, r);
+
+	if (r)
 		commit->object.flags |= RANGE_UPDATE;
-	}
 }
 
 static void clear_commit_line_range(struct rev_info *revs, struct commit *commit)
@@ -687,6 +682,22 @@ 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:
 	 *
@@ -920,7 +931,7 @@ static void load_tree_desc(struct tree_desc *desc, void **tree,
  * 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 *commit,
+static int assign_range_to_parent(struct rev_info *rev, struct commit *commit,
 		struct commit *parent, struct diff_line_range *range,
 		struct diff_options *opt, int map)
 {
@@ -1065,10 +1076,22 @@ static void assign_range_to_parent(struct rev_info *rev, struct commit *commit,
 			prev_range->next = NULL;
 	}
 
+	if (!map)
+		goto out;
+
 	if (final_range) {
 		assert(parent);
 		assert(final_range->spec);
 		add_line_range(rev, parent, final_range);
+	} else {
+		/*
+		 * If there is no new ranges assigned to the parent,
+		 * we should mark it as a 'root' commit.
+		 */
+		if (commit->parents && !commit->parents->next) {
+			free(commit->parents);
+			commit->parents = NULL;
+		}
 	}
 
 	/* and the ranges of current commit is updated */
@@ -1076,10 +1099,13 @@ static void assign_range_to_parent(struct rev_info *rev, struct commit *commit,
 	if (diff)
 		commit->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,
@@ -1096,13 +1122,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
@@ -1119,23 +1153,76 @@ 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;
+				parents = parents->next;
+				clear_commit_line_range(rev, list->item);
+				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) {
+			free_diff_line_ranges(state->range);
+			free(state);
+		}
+		parents = parents->next;
+	}
+
 	if (nontrivial)
 		add_decoration(&rev->nontrivial_merge, &commit->object, evil);
 	else
@@ -1327,16 +1414,36 @@ static void flush_nontrivial_merge(struct rev_info *rev,
 	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;
+	}
+
+	while (r) {
+		if (r->nr)
+			evil = 1;
+		r = r->next;
+	}
+
+	if (!evil)
+		return;
 
-	fprintf(opt->file, "%s%s%s\n", meta, "nontrivial merge found", reset);
+	fprintf(opt->file, "%s%s%s%s\n", line_prefix, meta,
+		"nontrivial merge found", reset);
 
 	while (range) {
 		if (range->nr) {
 			int lno = 1;
 			const char *ptr = range->spec->data;
-			const char *end = range->spec->data + range->spec->size;
+			const char *end = (const char *)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,
@@ -1353,12 +1460,17 @@ static void flush_nontrivial_merge(struct rev_info *rev,
 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)
+	if (!range || !(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;
@@ -1370,13 +1482,42 @@ 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);
+	}
+}
+
+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;
 	}
 }
 
@@ -1401,7 +1542,8 @@ int line_log_walk(struct rev_info *rev)
 	}
 	/* Clear the flags */
 	while (list) {
-		list->item->object.flags &= ~(RANGE_UPDATE | EVIL_MERGE | NEED_PRINT);
+		list->item->object.flags &= ~(RANGE_UPDATE | NONTRIVIAL_MERGE |
+						NEED_PRINT | EVIL_MERGE);
 		list = list->next;
 	}
 
@@ -1413,7 +1555,15 @@ int 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) {
+			if (rewrite_parents(rev, commit, rewrite_one))
+				die("Can't rewrite parent for commit %s",
+					sha1_to_hex(commit->object.sha1));
+		}
+
+		if (commit->object.flags & NEED_PRINT ||
+		    commit->object.flags & NONTRIVIAL_MERGE)
 			line_log_flush(rev, commit);
 
 		clear_commit_line_range(rev, commit);
revision.c +1 -0
index 369ec56..fbebf2f 100644
@@ -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;
 
revision.h +3 -2
index 585b15f..6100904 100644
@@ -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
t/t4302-log-line-merge-history.sh new file +174 -0

174 lines not on this page · raw message

Signature · 1 line
1.7.3.3.807.g6ee1f
#8 lore raw

PATCH 6/8 log -L: add --graph prefix before output

In reply to Thomas Rast

From: Bo Yang <[email protected]>

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

---
 line.c |   66 ++++++++++++++++++++++++++++++++++++++++++++++-----------------
 1 files changed, 48 insertions(+), 18 deletions(-)
line.c +48 -18
index 10870a5..1a9a947 100644
@@ -1242,6 +1242,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);
@@ -1264,7 +1271,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);
@@ -1274,7 +1281,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);
@@ -1316,8 +1323,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;
@@ -1325,8 +1339,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);
 	}
@@ -1345,6 +1359,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
@@ -1378,21 +1399,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);
 
@@ -1446,12 +1472,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;
 	}
@@ -1464,6 +1491,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 || !(c->object.flags & NONTRIVIAL_MERGE ||
 			c->object.flags & NEED_PRINT))
@@ -1476,11 +1505,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);
Signature · 1 line
1.7.3.3.807.g6ee1f
#9 lore raw

PATCH 7/8 log -L: add --full-line-diff option

In reply to Thomas Rast

From: Bo Yang <[email protected]>

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

---
 Documentation/git-log.txt |    4 ++++
 builtin/log.c             |    8 +++++++-
 line.c                    |   22 ++++++++++++++++------
 revision.c                |    2 ++
 revision.h                |    3 ++-
 5 files changed, 31 insertions(+), 8 deletions(-)
Documentation/git-log.txt +4 -0
index 7fcf6e7..f5769bf 100644
@@ -79,6 +79,10 @@ include::line-range-format.txt[]
 You can specify this option more than once.
 
 
+--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
builtin/log.c +7 -1
index 342d4de..fa57306 100644
@@ -99,6 +99,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;
 	static struct line_opt_callback_data line_cb = {0};
 
@@ -106,6 +107,9 @@ static void cmd_log_init(int argc, const char **argv, const char *prefix,
 		OPT_CALLBACK('L', NULL, &line_cb, "n,m:file",
 			     "Process line range n,m in file, 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()
 	};
 
@@ -188,8 +192,10 @@ static void cmd_log_init(int argc, const char **argv, const char *prefix,
 	}
 
 	/* Test whether line level history is asked for */
-	if (rev->line_level_traverse)
+	if (rev->line_level_traverse) {
 		line_log_init(rev, line_cb.ranges);
+		rev->full_line_diff = full_line_diff;
+	}
 
 	setup_pager();
 }
line.c +16 -6
index 1a9a947..742c17f 100644
@@ -1370,10 +1370,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)
+	if (!one) {
+		if (rev->full_line_diff) {
+			chunk.two = two->data;
+			chunk.two_end = (const char *)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!");
@@ -1495,7 +1503,8 @@ static void line_log_flush(struct rev_info *rev, struct commit *c)
 	struct strbuf *msgbuf;
 
 	if (!range || !(c->object.flags & NONTRIVIAL_MERGE ||
-			c->object.flags & NEED_PRINT))
+			c->object.flags & NEED_PRINT ||
+			rev->full_line_diff))
 		return;
 
 	if (rev->graph)
@@ -1516,7 +1525,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;
 		}
@@ -1573,7 +1582,7 @@ int line_log_walk(struct rev_info *rev)
 	/* Clear the flags */
 	while (list) {
 		list->item->object.flags &= ~(RANGE_UPDATE | NONTRIVIAL_MERGE |
-						NEED_PRINT | EVIL_MERGE);
+				NEED_PRINT | EVIL_MERGE);
 		list = list->next;
 	}
 
@@ -1593,7 +1602,8 @@ int line_log_walk(struct rev_info *rev)
 		}
 
 		if (commit->object.flags & NEED_PRINT ||
-		    commit->object.flags & NONTRIVIAL_MERGE)
+		    commit->object.flags & NONTRIVIAL_MERGE ||
+		    rev->full_line_diff)
 			line_log_flush(rev, commit);
 
 		clear_commit_line_range(rev, commit);
revision.c +2 -0
index fbebf2f..85a60d0 100644
@@ -1912,6 +1912,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->full_line_diff)
+		revs->dense = 0;
 	if (revs->simplify_merges)
 		simplify_merges(revs);
 	if (revs->children.name)
revision.h +2 -1
index 6100904..29babf3 100644
@@ -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,
Signature · 1 line
1.7.3.3.807.g6ee1f
#10 lore raw

PATCH 8/8 log -L: implement move/copy detection (-M/-C)

In reply to Thomas Rast

From: Bo Yang <[email protected]>

The basic idea is:

* Keep a list of "candidate snippets". Start out empty.

* Go through all candidates (determined by the level of detection chosen) and diff them against the target file.

- For each common part in the diff, put it in the "candidate snippets" if it's "worth it". (Notably there is no point in adding a snippet that is fully contained in another.)

* Score the snippets. Lines with alphanumeric characters count more.

* Filter out snippets with low score. Where there are overlaps, favour higher scores.

---
 line.c                          |  556 ++++++++++++++++++++++++++++++++++++++-
 t/t4303-log-line-move-detect.sh |  238 +++++++++++++++++
 t/t4304-log-line-copy-detect.sh |  220 +++++++++++++++
 3 files changed, 1001 insertions(+), 13 deletions(-)
 create mode 100755 t/t4303-log-line-move-detect.sh
 create mode 100755 t/t4304-log-line-copy-detect.sh
line.c +543 -13
index 742c17f..ae176da 100644
@@ -17,6 +17,7 @@ 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 */
+	int copied : 1;
 };
 
 struct print_pair {
@@ -30,6 +31,7 @@ struct line_range {
 	long pstart, pend;	/* The corresponding range of parent commit */
 	struct print_pair pair;
 			/* The changed lines inside this range */
+	int copy_score;
 	unsigned int diff:1;
 };
 
@@ -66,6 +68,7 @@ static inline void print_range_init(struct print_range *r)
 	r->start = r->end = 0;
 	r->pstart = r->pend = 0;
 	r->line_added = 0;
+	r->copied = 0;
 }
 
 static inline void print_pair_init(struct print_pair *p)
@@ -104,6 +107,7 @@ static inline void line_range_clear(struct line_range *r)
 	r->start = r->end = 0;
 	r->pstart = r->pend = 0;
 	print_pair_clear(&r->pair);
+	r->copy_score = 0;
 	r->diff = 0;
 }
 
@@ -594,7 +598,7 @@ static void add_line_range(struct rev_info *revs, struct commit *commit,
 	ret = lookup_decoration(&revs->line_range, &commit->object);
 	if (ret && r)
 		diff_line_range_merge(ret, r);
-	else
+	else if (r != NULL)
 		add_decoration(&revs->line_range, &commit->object, r);
 
 	if (r)
@@ -620,6 +624,16 @@ static void clear_commit_line_range(struct rev_info *revs, struct commit *commit
 	return ret;
 }
 
+struct diff_line_range *delete_line_range(struct rev_info *revs, struct commit *commit)
+{
+	struct diff_line_range *ret = NULL;
+
+	ret = lookup_decoration(&revs->line_range, &commit->object);
+	add_decoration(&revs->line_range, &commit->object, NULL);
+
+	return ret;
+}
+
 void line_log_init(struct rev_info *rev, struct diff_line_range *r)
 {
 	struct commit *commit = NULL;
@@ -647,6 +661,515 @@ struct take_range_cb_data {
 		 * commit and its parent */
 };
 
+struct map {
+	long start, end;
+	long pstart, pend;
+	struct diff_filespec *spec;
+	int score;
+};
+
+struct mac_cb_data {
+	long plno, tlno;
+	int nr;
+	int alloc;
+	struct map *maps;
+	struct diff_filespec *spec;
+};
+
+struct mac_state {
+	int nr;
+	int alloc;
+	struct map *maps;
+};
+
+static void mac_state_init(struct mac_state *state)
+{
+	state->nr = state->alloc = 0;
+	state->maps = NULL;
+}
+
+static void mac_cb(void *data, long same, long p_next, long t_next)
+{
+	struct mac_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 (t_end >= t_start) {
+		ALLOC_GROW(d->maps, (d->nr + 1), d->alloc);
+		d->maps[d->nr].start = t_start;
+		d->maps[d->nr].end = t_end;
+		d->maps[d->nr].pstart = p_start;
+		d->maps[d->nr].pend = p_end;
+		d->maps[d->nr].spec = d->spec;
+		d->nr++;
+	}
+
+	d->plno = p_next;
+	d->tlno = t_next;
+}
+
+static void mac_state_insert(struct mac_state *state, long s_start, long s_end,
+		long start, long end, struct diff_filespec *spec)
+{
+	int i = 0;
+	struct map *maps;
+
+	for (; i < state->nr; i++) {
+		if (state->maps[i].start > end)
+			break;
+	}
+
+	state->nr++;
+	ALLOC_GROW(state->maps, state->nr, state->alloc);
+	maps = state->maps;
+	memmove(maps + i + 1, maps + i, (state->nr - i - 1) * sizeof(*maps));
+	maps[i].start = s_start;
+	maps[i].end = s_end;
+	maps[i].pstart = start;
+	maps[i].pend = end;
+	maps[i].spec = spec;
+	spec->count++;
+}
+
+static void mac_state_remove(struct mac_state *state, long s_start, long s_end,
+		long start, long end)
+{
+	int i = 0;
+	struct map *maps = state->maps;
+
+	while (i < state->nr) {
+		if (maps[i].start < start && maps[i].end > start) {
+			maps[i].end = s_start - 1;
+			maps[i].pend -= start - s_start;
+		}
+		if (maps[i].start < end && maps[i].end > end) {
+			maps[i].start = s_end + 1;
+			maps[i].pstart += end - s_end;
+		}
+		if (maps[i].start >=start && maps[i].end <= end) {
+			memmove(maps + i, maps + i + 1, (state->nr - i - 1) * sizeof(*maps));
+			state->nr--;
+			i--;
+		}
+
+		i++;
+	}
+}
+
+/*
+ * Generally, the 'struct line_range's pstart/pend is used to store
+ * the pre-image of current range. But here, we use it to store the
+ * line range of the 'artificial' memory file.
+ */
+static struct mac_state *merge_mac(struct mac_cb_data *data,
+		struct mac_state *state, long lines)
+{
+	struct map *maps = data->maps;
+	int i = 0;
+
+	assert(state);
+
+	while (i < data->nr) {
+		int j = 0;
+		long start = maps[i].start;
+		long end = maps[i].end;
+		int should_insert = 0;
+		long should_start = start;
+		long should_end = end;
+		long may_start = start, may_end = end;
+		long start_range_len = 0, end_range_len = 0;
+
+		/* first round: finds whether this range should be inserted */
+		if (!state->nr)
+			should_insert = 1;
+		while (state && j < state->nr) {
+			if (state->maps[j].end <= start) {
+				if (j+1 == state->nr)
+					should_insert = 1;
+				j++;
+				continue;
+			}
+			if (state->maps[j].start > end)
+				should_insert = 1;
+			else {
+				if (state->maps[j].start <= start) {
+					if (state->maps[j].end >= end)
+						should_insert = 0;
+					else {
+						should_insert = 1;
+						may_start = state->maps[j].end + 1;
+						start_range_len = state->maps[j].end -
+							state->maps[j].start + 1;
+					}
+				} else {
+					if (state->maps[j].end > end) {
+						should_insert = 1;
+						may_end = state->maps[j].start - 1;
+						end_range_len = state->maps[j].end -
+							state->maps[j].start + 1;
+					} else
+						should_insert = 1;
+				}
+			}
+
+			j++;
+		}
+
+		/* second round: insert the new range and adjust the current one */
+		if (should_insert) {
+			/* We always keep the longest range in prior */
+			if (start_range_len > end_range_len) {
+				if (start_range_len > should_end - should_start + 1)
+					should_start = may_start;
+				if (end_range_len > should_end - should_start + 1)
+					should_end = may_end;
+			} else {
+				if (end_range_len > should_end - should_start + 1)
+					should_end = may_end;
+				if (start_range_len > should_end - should_start + 1)
+					should_start = may_start;
+			}
+
+			mac_state_remove(state, should_start, should_end,
+					maps[i].start, maps[i].end);
+
+			start = maps[i].pstart + should_start - maps[i].start;
+			end = maps[i].pend - (maps[i].end - should_end);
+			mac_state_insert(state, should_start, should_end, start, end, data->spec);
+		}
+
+		i++;
+	}
+
+	return state;
+}
+
+static struct mac_state *find_mac_in_file(mmfile_t *file_p, mmfile_t *file_t,
+		long lines, unsigned char *scores, struct diff_filespec *spec,
+		struct mac_state *state)
+{
+	xpparam_t xpp;
+	xdemitconf_t xecfg;
+	struct mac_cb_data cb = {0, 0, 0, 0, NULL, spec};
+
+	memset(&xpp, 0, sizeof(xpp));
+	memset(&xecfg, 0, sizeof(xecfg));
+	xecfg.ctxlen = xecfg.interhunkctxlen = 0;
+
+	xdi_diff_hunks(file_p, file_t, mac_cb, &cb, &xpp, &xecfg);
+
+	if (cb.tlno < lines) {
+		ALLOC_GROW(cb.maps, (cb.nr + 1), cb.alloc);
+		cb.maps[cb.nr].start = cb.tlno + 1;
+		cb.maps[cb.nr].end = lines;
+		cb.maps[cb.nr].pstart = cb.plno + 1;
+		cb.maps[cb.nr].pend = cb.plno + lines - cb.tlno;
+		cb.maps[cb.nr].spec = spec;
+		cb.nr++;
+	}
+
+	if (cb.nr)
+		state = merge_mac(&cb, state, lines);
+	free(cb.maps);
+
+	return state;
+}
+
+#define LINE_SCORE 6
+#define TRIVIAL_SCORE 2
+static void setup_mac_file(struct diff_filespec *spec, mmfile_t *lines,
+		unsigned char *scores, long start, long end)
+{
+	int i = 0;
+	int line = 1;
+	int size = 0;
+	char *data = spec->data;
+
+	memset(scores, TRIVIAL_SCORE, end - start + 1);
+	while (i < spec->size) {
+		int index = line - start;
+		if (line < start) {
+			if (data[i] == '\n')
+				line++;
+			i++;
+			continue;
+		}
+		if (line > end)
+			break;
+		if (size == 0)
+			lines->ptr = data + i;
+		size++;
+		if (scores[index] == TRIVIAL_SCORE && data[i] <= 'z' && data[i] >= 'a')
+			scores[index] = LINE_SCORE;
+		if (scores[index] == TRIVIAL_SCORE && data[i] <= 'Z' && data[i] >= 'A')
+			scores[index] = LINE_SCORE;
+		if (scores[index] == TRIVIAL_SCORE && data[i] <= '9' && data[i] >= '0')
+			scores[index] = LINE_SCORE;
+		if (data[i] == '\n')
+			line++;
+
+		i++;
+	}
+
+	lines->size = size;
+}
+
+static void mac_state_cal_score(long lines, unsigned char *scores, struct mac_state *state)
+{
+	struct map *maps = state->maps;
+	int i = 0;
+
+	while (i < state->nr) {
+		int score = 0;
+		int j = maps[i].start;
+		while (j <= maps[i].end) {
+			assert(j <= lines);
+			score += scores[j - 1];
+			j++;
+		}
+
+		maps[i].score = score;
+		i++;
+	}
+}
+
+#define MIN_GAP 3
+#define RANGE_MIN_SCORE 20
+static struct diff_line_range *mac_combine_remove(struct diff_line_range *range)
+{
+	struct diff_line_range *r = range, *prev = range, *ret = range;
+
+	// Firstly to combine adjacent-enough range
+	while (r) {
+		int i = 0;
+		struct line_range *rs = r->ranges;
+		for (; i < r->nr; i++) {
+			if (i + 1 < r->nr &&
+				(rs[i + 1].end - rs[i].start < MIN_GAP)) {
+				rs[i].end = rs[i + 1].end;
+				rs[i].copy_score += rs[i + 1].copy_score;
+				memmove(rs + i + 1, rs + i + 2, (r->nr - i - 1) * sizeof(*rs));
+				r->nr--;
+				i--;
+			}
+		}
+		r = r->next;
+	}
+
+	// then delete the trivial ones
+	r = range;
+	while (r) {
+		int i = 0;
+		struct line_range *rs = r->ranges;
+		for (; i < r->nr; i++) {
+			if (rs[i].copy_score < RANGE_MIN_SCORE) {
+				memmove(rs + i, rs + i + 1, (r->nr - i) * sizeof(*rs));
+				r->nr--;
+				i--;
+			}
+		}
+		r = r->next;
+	}
+
+	// then delete the empty diff_line_range
+	r = range;
+	while (r) {
+		struct diff_line_range *next = r->next;
+		if (!r->nr) {
+			diff_line_range_clear(r);
+			free(r);
+			if (ret == r) {
+				ret = next;
+				prev = next;
+			}
+		} else if (prev != r) {
+				prev->next = r;
+				prev = r;
+		}
+
+		r = next;
+	}
+
+	return ret;
+}
+
+static struct diff_line_range *mac_state_to_line_range(struct mac_state *state)
+{
+	struct diff_line_range *ret = NULL;
+	struct diff_line_range *prev = NULL;
+	struct map *maps = state->maps;
+	int i = 0;
+	struct line_range *rg = NULL;
+
+	while (i < state->nr) {
+		struct diff_line_range *r = ret;
+		while (r) {
+			if (r->spec == maps[i].spec) {
+				rg = diff_line_range_insert(r, NULL, maps[i].pstart,
+						maps[i].pend);
+				rg->copy_score += maps[i].score;
+				break;
+			}
+			r = r->next;
+		}
+
+		if (!r) {
+			r = xmalloc(sizeof(*r));
+			diff_line_range_init(r);
+			r->spec = maps[i].spec;
+			rg = diff_line_range_insert(r, NULL, maps[i].pstart, maps[i].pend);
+			rg->copy_score += maps[i].score;
+
+			if (!ret) {
+				ret = r;
+				prev = r;
+			} else {
+				prev->next = r;
+				prev = r;
+			}
+		}
+
+		i++;
+	}
+
+	return mac_combine_remove(ret);
+}
+
+struct mac_state *find_mac_in_one_file(struct commit *p,
+		char *path, mmfile_t *file_t, long lines,
+		unsigned char *scores)
+{
+	struct diff_filespec *spec = alloc_filespec(path);
+	unsigned char sha1[20];
+	unsigned mode;
+	mmfile_t file_p;
+	struct mac_state *ret = xmalloc(sizeof(*ret));
+
+	mac_state_init(ret);
+	if (get_tree_entry(p->object.sha1, path, sha1, &mode))
+		return NULL;
+	fill_filespec(spec, sha1, mode);
+	diff_populate_filespec(spec, 0);
+	file_p.ptr = spec->data;
+	file_p.size = spec->size;
+
+	ret = find_mac_in_file(&file_p, file_t, lines, scores, spec, ret);
+	mac_state_cal_score(lines, scores, ret);
+
+	return ret;
+}
+
+struct mac_state *find_mac_in_all_file(struct rev_info *rev, struct commit *c,
+		struct commit *p, mmfile_t *file_t, long lines,
+		unsigned char *scores)
+{
+	struct diff_options diff_opts;
+	const char *paths[1];
+	int j = 0;
+	struct mac_state *state = xmalloc(sizeof(*state));
+
+	mac_state_init(state);
+	/* ok, we can start to do the move/copy detect now */
+	diff_setup(&diff_opts);
+	DIFF_OPT_SET(&diff_opts, RECURSIVE);
+	diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
+	paths[0] = NULL;
+	diff_tree_setup_paths(paths, &diff_opts);
+	if (diff_setup_done(&diff_opts) < 0)
+		die("diff-setup in line.c");
+	if (DIFF_OPT_TST(&rev->diffopt, FIND_COPIES_HARDER))
+		DIFF_OPT_SET(&diff_opts, FIND_COPIES_HARDER);
+
+	diff_tree_sha1(p->tree->object.sha1, c->tree->object.sha1,
+			"", &diff_opts);
+	for (j = 0; j < diff_queued_diff.nr; j++) {
+		struct diff_filepair *p = diff_queued_diff.queue[j];
+		mmfile_t file_p;
+
+		if (!DIFF_FILE_VALID(p->one))
+			continue;
+		if (S_ISGITLINK(p->one->mode))
+			continue;
+		diff_populate_filespec(p->one, 0);
+		file_p.ptr = p->one->data;
+		file_p.size = p->one->size;
+
+		p->one->count++;
+		state = find_mac_in_file(&file_p, file_t, lines, scores, p->one, state);
+	}
+
+	diff_flush(&diff_opts);
+	diff_tree_release_paths(&diff_opts);
+
+	mac_state_cal_score(lines, scores, state);
+
+	return state;
+}
+
+static void find_mac_for_range(struct rev_info *rev,
+		struct commit *c, struct commit *p,
+		struct diff_line_range *r, struct print_range *pr)
+{
+	unsigned char *scores;
+	struct mac_state *state;
+	mmfile_t lines = {NULL, 0};
+	struct diff_line_range *copied = NULL;
+
+	/* Do not search for source of ranges shorter than 3 lines */
+	if (pr->line_added && (pr->end - pr->start) < 3)
+		return;
+
+	scores = xmalloc(pr->end - pr->start + 1);
+	setup_mac_file(r->spec, &lines, scores, pr->start, pr->end);
+
+	if (rev->diffopt.detect_rename == DIFF_DETECT_RENAME)
+		state = find_mac_in_one_file(p, r->spec->path, &lines,
+					     pr->end - pr->start + 1, scores);
+	else
+		state = find_mac_in_all_file(rev, c, p, &lines,
+					     pr->end - pr->start + 1, scores);
+
+	copied = mac_state_to_line_range(state);
+	if (copied) {
+		add_line_range(rev, p, copied);
+		pr->copied = 1;
+	}
+	free(scores);
+}
+
+/*
+ * Find the code move/copy, here we reuse the '-M/-C' options in diff options.
+ * -M means that finds the code in the same file;
+ * -C means that finds the code in all the files in parent commit.
+ */
+static void find_mac(struct rev_info *rev, struct commit *c)
+{
+	struct diff_line_range *r = lookup_line_range(rev, c);
+	struct diff_line_range *prange = NULL;
+	struct commit *p = NULL;
+
+	if (c->parents == NULL)
+		return;
+
+	assert(c->parents->next == NULL);
+	p = c->parents->item;
+	parse_commit(p);
+
+	while (r) {
+		int n;
+		for (n = 0; n < r->nr; n++) {
+			struct print_pair *pair = &r->ranges[n].pair;
+			int i;
+			for (i = 0; i < pair->nr; i++)
+				find_mac_for_range(rev, c, p, r, &pair->ranges[i]);
+		}
+
+		r = r->next;
+	}
+
+	add_line_range(rev, p, prange);
+}
+
 #define SCALE_FACTOR 4
 /*
  * [p_start, p_end] represents the pre-image of current diff hunk,
@@ -942,7 +1465,7 @@ static int assign_range_to_parent(struct rev_info *rev, struct commit *commit,
 	void *tree1 = NULL, *tree2 = NULL;
 	struct tree_desc desc1, desc2;
 	struct diff_queue_struct *queue;
-	struct take_range_cb_data cb_data = {NULL, cur_range, 0, 0};
+	struct take_range_cb_data cb_data = {NULL, cur_range, 0, 0, 0};
 	xpparam_t xpp;
 	xdemitconf_t xecfg;
 	int i, diff = 0;
@@ -1083,15 +1606,6 @@ static int assign_range_to_parent(struct rev_info *rev, struct commit *commit,
 		assert(parent);
 		assert(final_range->spec);
 		add_line_range(rev, parent, final_range);
-	} else {
-		/*
-		 * If there is no new ranges assigned to the parent,
-		 * we should mark it as a 'root' commit.
-		 */
-		if (commit->parents && !commit->parents->next) {
-			free(commit->parents);
-			commit->parents = NULL;
-		}
 	}
 
 	/* and the ranges of current commit is updated */
@@ -1120,6 +1634,18 @@ static void diff_update_parent_range(struct rev_info *rev,
 	}
 
 	assign_range_to_parent(rev, commit, c, r, &rev->diffopt, 1);
+
+	if (rev->diffopt.detect_rename > 0)
+		find_mac(rev, commit);
+
+	/*
+	 * If there is no new ranges assigned to the parent,
+	 * we should mark it as a 'root' commit.
+	 */
+	if (c != NULL && lookup_line_range(rev, c) == NULL) {
+		free(commit->parents);
+		commit->parents = NULL;
+	}
 }
 
 struct commit_state {
@@ -1306,8 +1832,12 @@ static void diff_flush_range(struct diff_options *opt, struct line_chunk *chunk,
 		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, '+');
+		if (pr->copied)
+			flush_lines(opt, &chunk->two, chunk->two_end,
+				pr->start, pr->end, &chunk->ltwo, new, ' ');
+		else
+			flush_lines(opt, &chunk->two, chunk->two_end,
+				pr->start, pr->end, &chunk->ltwo, new, '+');
 
 		cur = pr->end + 1;
 	}
t/t4303-log-line-move-detect.sh new file +238 -0

238 lines not on this page · raw message

t/t4304-log-line-copy-detect.sh new file +220 -0

220 lines not on this page · raw message

Signature · 1 line
1.7.3.3.807.g6ee1f