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@xxxxxxxxx>
---
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
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html