{"thread":{"id":"24718","subject":"[PATCH v5.1 08/17] map/take range to the parent of commits","startedAt":"2010-08-12T13:09:58Z","lastAt":"2010-08-12T13:09:58Z","messageCount":1,"participants":["Bo Yang"],"isPatch":true,"patchVersion":5,"patchTotal":17},"messages":[{"id":"147901","messageId":"1281618598-6721-1-git-send-email-struggleyb.nku@gmail.com","threadId":"24718","inReplyTo":null,"subject":"[PATCH v5.1 08/17] map/take range to the parent of commits","fromName":"Bo Yang","fromEmail":"struggleyb.nku@gmail.com","sentAt":"2010-08-12T13:09:58Z","receivedAt":"2010-08-12T13:09:58Z","isPatch":true,"sender":{"key":"struggleyb.nku@gmail.com","avatar":"https://avatars.githubusercontent.com/u/233030?v=4"},"body":"When going from a commit to its parents, we map the \"interesting\"\nrange of lines according to the change made.\nFor non-merge commit, we just run map_range on the ranges, which\nworks as follows:\n\n1. Run diffcore_std to find out the pre/postimage for each file.\n2. Run xdi_diff_hunks on each interesting set of pre/postimages.\n3. The map_range_cb callback is invoked for each hunk by the diff\n   engine, and we use it to calculate the pre-image range from the\n   post-image range in the function map_lines.\n\nFor merge commits, we run map_range once for every parent.\nSimultaneously we use a take_range pass to eliminate all ranges\nthat are identical. If any ranges remain after that, then the\nmerge is considered non-trivial.\n\nThe algorithm that maps lines from post-image to pre-image is in\nthe function map_lines. Generally, we use simple line number\ncalculation method to do the map.\n\nSigned-off-by: Bo Yang <struggleyb.nku@gmail.com>\n---\n line.c     |  502 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n revision.h |    5 +-\n 2 files changed, 506 insertions(+), 1 deletions(-)\n\ndiff --git a/line.c b/line.c\nindex 1b77172..1aa828b 100644\n--- a/line.c\n+++ b/line.c\n@@ -504,3 +504,505 @@ void setup_line(struct rev_info *rev, struct diff_line_range *r)\n \tdiff_tree_release_paths(opt);\n }\n \n+struct take_range_cb_data {\n+\tstruct diff_line_range *interesting;\t/* currently interesting ranges */\n+\tstruct diff_line_range *range;\n+\t\t/* the ranges corresponds to the interesting ranges of parent commit */\n+\tlong plno, tlno;\n+\t\t/* the last line number of diff hunk */\n+\tint diff;\n+\t\t/* whether there is some line changes between the current\n+\t\t * commit and its parent */\n+};\n+\n+#define SCALE_FACTOR 4\n+/*\n+ * [p_start, p_end] represents the pre-image of current diff hunk,\n+ * [t_start, t_end] represents the post-image of the current diff hunk,\n+ * [start, end] represents the currently interesting line range in\n+ * post-image,\n+ * [o_start, o_end] represents the original line range that coresponds\n+ * to current line range.\n+ */\n+void map_lines(long p_start, long p_end, long t_start, long t_end,\n+\t\tlong start, long end, long *o_start, long *o_end)\n+{\n+\t/*\n+\t * Normally, p_start should be less than p_end, so does the\n+\t * t_start and t_end. But when the line range is added from\n+\t * scratch, p_start will be greater than p_end. When the line\n+\t * range is deleted, t_start will be greater than t_end.\n+\t */\n+\tif (p_start > p_end) {\n+\t\t*o_start = *o_end = 0;\n+\t\treturn;\n+\t}\n+\t/* A deletion */\n+\tif (t_start > t_end) {\n+\t\t*o_start = p_start;\n+\t\t*o_end = p_end;\n+\t\treturn;\n+\t}\n+\n+\tif (start == t_start && end == t_end) {\n+\t\t*o_start = p_start;\n+\t\t*o_end = p_end;\n+\t\treturn;\n+\t}\n+\n+\t/*\n+\t * A heuristic for lines mapping:\n+\t *\n+\t * When the pre-image is no more than 1/SCALE_FACTOR of the post-image,\n+\t * there is no effective way to find out which part of pre-image\n+\t * corresponds to the currently interesting range of post-image.\n+\t * And we are in the danger of tracking totally useless lines.\n+\t * So, we just treat all the post-image lines as added from scratch.\n+\t */\n+\tif (SCALE_FACTOR * (p_end - p_start + 1) < (t_end - t_start + 1)) {\n+\t\t*o_start = *o_end = 0;\n+\t\treturn;\n+\t}\n+\n+\t*o_start = p_start + start - t_start;\n+\t*o_end = p_end - (t_end - end);\n+\n+\tif (*o_start > *o_end) {\n+\t\tint temp = *o_start;\n+\t\t*o_start = *o_end;\n+\t\t*o_end = temp;\n+\t}\n+\n+\tif (*o_start < p_start)\n+\t\t*o_start = p_start;\n+\tif (*o_end > p_end)\n+\t\t*o_end = p_end;\n+}\n+\n+/*\n+ * When same == 1:\n+ * [p_start, p_end] represents the diff hunk line range of pre-image,\n+ * [t_start, t_end] represents the diff hunk line range of post-image.\n+ * When same == 0, they represent a range of identical lines between\n+ * two images.\n+ *\n+ * This function find out the corresponding line ranges of currently\n+ * interesting ranges which this diff hunk touches.\n+ */\n+static void map_range(struct take_range_cb_data *data, int same,\n+\t\tlong p_start, long p_end, long t_start, long t_end)\n+{\n+\tstruct line_range *ranges = data->interesting->ranges;\n+\tlong takens, takene, start, end;\n+\tint i = 0, out = 0, added = 0;\n+\tlong op_start = p_start, op_end = p_end, ot_start = t_start, ot_end = t_end;\n+\n+\tfor (; i < data->interesting->nr; i++) {\n+\t\tadded = 0;\n+\t\tif (t_start > ranges[i].end)\n+\t\t\tcontinue;\n+\t\tif (t_end < ranges[i].start)\n+\t\t\tbreak;\n+\n+\t\tif (t_start > ranges[i].start) {\n+\t\t\tstart = t_start;\n+\t\t\ttakens = p_start;\n+\t\t\tif (t_end >= ranges[i].end) {\n+\t\t\t\tend = ranges[i].end;\n+\t\t\t\ttakene = p_start + end - t_start;\n+\t\t\t} else {\n+\t\t\t\tend = t_end;\n+\t\t\t\ttakene = p_end;\n+\t\t\t\tout = 1;\n+\t\t\t}\n+\t\t} else {\n+\t\t\tstart = ranges[i].start;\n+\t\t\ttakens = p_start + start - t_start;\n+\t\t\tif (t_end >= ranges[i].end) {\n+\t\t\t\tend = ranges[i].end;\n+\t\t\t\ttakene = p_start + end - t_start;\n+\t\t\t} else {\n+\t\t\t\tend = t_end;\n+\t\t\t\ttakene = p_end;\n+\t\t\t\tout = 1;\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (!same) {\n+\t\t\tstruct print_pair *pair = &ranges[i].pair;\n+\t\t\tstruct print_range *rr = NULL;\n+\t\t\tPRINT_PAIR_GROW(pair);\n+\t\t\trr = pair->ranges + pair->nr - 1;\n+\t\t\tPRINT_RANGE_INIT(rr);\n+\t\t\trr->start = start;\n+\t\t\trr->end = end;\n+\t\t\tmap_lines(op_start, op_end, ot_start, ot_end, start, end,\n+\t\t\t\t\t&takens, &takene);\n+\t\t\tif (takens == 0 && takene == 0) {\n+\t\t\t\tadded = 1;\n+\t\t\t\trr->line_added = 1;\n+\t\t\t}\n+\t\t\trr->pstart = takens;\n+\t\t\trr->pend = takene;\n+\t\t\tdata->diff = 1;\n+\t\t\tdata->interesting->diff = 1;\n+\t\t\tranges[i].diff = 1;\n+\t\t}\n+\t\tif (added) {\n+\t\t\t/* Code movement/copy detect here, now place two dummy statements here */\n+\t\t\tint dummy = 0;\n+\t\t\tdummy = 1;\n+\t\t} else {\n+\t\t\tstruct line_range *added_range = diff_line_range_insert(data->range,\n+\t\t\t\t\tNULL, takens, takene);\n+\t\t\tassert(added_range);\n+\t\t\tranges[i].pstart = added_range->start;\n+\t\t\tranges[i].pend = added_range->end;\n+\t\t}\n+\n+\t\tt_start = end + 1;\n+\t\tp_start = takene + 1;\n+\n+\t\tif (out)\n+\t\t\tbreak;\n+\t}\n+}\n+\n+/*\n+ * [p_start, p_end] represents the line range of pre-image,\n+ * [t_start, t_end] represents the line range of post-image,\n+ * and they are identical lines.\n+ *\n+ * This function substracts out the identical lines between current\n+ * commit and its parent, from currently interesting ranges.\n+ */\n+static void take_range(struct take_range_cb_data *data,\n+\t\tlong p_start, long p_end, long t_start, long t_end)\n+{\n+\tstruct line_range *ranges = data->interesting->ranges;\n+\tlong takens, takene, start, end;\n+\tint i = 0, out = 0, added = 0;\n+\n+\tfor (; i < data->interesting->nr; i++) {\n+\t\tadded = 0;\n+\t\tif (t_start > ranges[i].end)\n+\t\t\tcontinue;\n+\t\tif (t_end < ranges[i].start)\n+\t\t\tbreak;\n+\n+\t\tif (t_start > ranges[i].start) {\n+\t\t\tlong tmp = ranges[i].end;\n+\t\t\tranges[i].end = t_start - 1;\n+\t\t\tstart = t_start;\n+\t\t\ttakens = p_start;\n+\t\t\tif (t_end >= tmp) {\n+\t\t\t\tend = tmp;\n+\t\t\t\ttakene = p_start + end - t_start;\n+\t\t\t\tp_start = takene + 1;\n+\t\t\t\tt_start = end + 1;\n+\t\t\t} else {\n+\t\t\t\tend = t_end;\n+\t\t\t\ttakene = p_end;\n+\t\t\t\tdiff_line_range_insert(data->interesting, NULL,\n+\t\t\t\t\tt_end + 1, tmp);\n+\t\t\t\tout = 1;\n+\t\t\t}\n+\t\t} else {\n+\t\t\tstart = ranges[i].start;\n+\t\t\ttakens = p_start + start - t_start;\n+\t\t\tif (t_end >= ranges[i].end) {\n+\t\t\t\tint num = data->interesting->nr - 1;\n+\t\t\t\tend = ranges[i].end;\n+\t\t\t\ttakene = p_start + end - t_start;\n+\t\t\t\tt_start = end + 1;\n+\t\t\t\tp_start = takene + 1;\n+\t\t\t\tmemmove(ranges + i, ranges + i + 1, (num - i) * sizeof(*ranges));\n+\t\t\t\tdata->interesting->nr = num;\n+\t\t\t\ti--;\n+\t\t\t} else {\n+\t\t\t\tend = t_end;\n+\t\t\t\ttakene = p_end;\n+\t\t\t\tranges[i].start = t_end + 1;\n+\t\t\t\tout = 1;\n+\t\t\t}\n+\t\t}\n+\n+\t\tdiff_line_range_insert(data->range, NULL, takens, takene);\n+\n+\t\tif (out)\n+\t\t\tbreak;\n+\t}\n+}\n+\n+static void take_range_cb(void *data, long same, long p_next, long t_next)\n+{\n+\tstruct take_range_cb_data *d = data;\n+\tlong p_start = d->plno + 1, t_start = d->tlno + 1;\n+\tlong p_end = p_start + same - t_start, t_end = same;\n+\n+\t/* If one file is added from scratch, we should not bother to call\n+\t * take_range, since there is nothing to take\n+\t */\n+\tif (t_end >= t_start)\n+\t\ttake_range(d, p_start, p_end, t_start, t_end);\n+\td->plno = p_next;\n+\td->tlno = t_next;\n+}\n+\n+static void map_range_cb(void *data, long same, long p_next, long t_next)\n+{\n+\tstruct take_range_cb_data *d = data;\n+\n+\tlong p_start = d->plno + 1;\n+\tlong t_start = d->tlno + 1;\n+\tlong p_end = same - t_start + p_start;\n+\tlong t_end = same;\n+\n+\t/* Firstly, take the unchanged lines from child */\n+\tif (t_end >= t_start)\n+\t\tmap_range(d, 1, p_start, p_end, t_start, t_end);\n+\n+\t/* find out which lines to print */\n+\tt_start = same + 1;\n+\tp_start = d->plno + t_start - d->tlno;\n+\tmap_range(d, 0, p_start, p_next, t_start, t_next);\n+\n+\td->plno = p_next;\n+\td->tlno = t_next;\n+}\n+\n+/*\n+ * We support two kinds of operation in this function:\n+ * 1. map == 0, take the same lines from the current commit and assign it\n+ *              to parent;\n+ * 2. map == 1, in addition to the same lines, we also map the changed lines\n+ *              from the current commit to the parent according to the\n+ *              diff output.\n+ * take_range_cb and take_range are used to take same lines from current commit\n+ * to parents.\n+ * map_range_cb and map_range are used to map line ranges to the parent.\n+ */\n+static void assign_range_to_parent(struct rev_info *rev, struct commit *c,\n+\t\tstruct commit *p, struct diff_line_range *r,\n+\t\tstruct diff_options *opt, int map)\n+{\n+\tstruct diff_line_range *rr = xmalloc(sizeof(*rr));\n+\tstruct diff_line_range *cr = rr, *prev_r = rr;\n+\tstruct diff_line_range *rg = NULL;\n+\tstruct tree_desc desc1, desc2;\n+\tvoid *tree1 = NULL, *tree2 = NULL;\n+\tunsigned long size1, size2;\n+\tstruct diff_queue_struct *queue;\n+\tstruct take_range_cb_data cb = {NULL, cr, 0, 0};\n+\txpparam_t xpp;\n+\txdemitconf_t xecfg;\n+\tint i, diff = 0;\n+\txdiff_emit_hunk_consume_fn fn = map ? map_range_cb : take_range_cb;\n+\n+\tDIFF_LINE_RANGE_INIT(cr);\n+\tmemset(&xpp, 0, sizeof(xpp));\n+\tmemset(&xecfg, 0, sizeof(xecfg));\n+\txecfg.ctxlen = xecfg.interhunkctxlen = 0;\n+\n+\t/*\n+\t * Compose up two trees, for root commit, we make up a empty tree.\n+\t */\n+\tassert(c);\n+\ttree2 = read_object_with_reference(c->tree->object.sha1, \"tree\",\n+\t\t\t&size2, NULL);\n+\tif (tree2 == NULL)\n+\t\tdie(\"Unable to read tree (%s)\", sha1_to_hex(c->tree->object.sha1));\n+\tinit_tree_desc(&desc2, tree2, size2);\n+\tif (p) {\n+\t\ttree1 = read_object_with_reference(p->tree->object.sha1,\n+\t\t\t\t\"tree\", &size1, NULL);\n+\t\tif (tree1 == NULL)\n+\t\t\tdie(\"Unable to read tree (%s)\",\n+\t\t\t\t\tsha1_to_hex(p->tree->object.sha1));\n+\t\tinit_tree_desc(&desc1, tree1, size1);\n+\t} else {\n+\t\tinit_tree_desc(&desc1, \"\", 0);\n+\t}\n+\n+\tDIFF_QUEUE_CLEAR(&diff_queued_diff);\n+\tdiff_tree(&desc1, &desc2, \"\", opt);\n+\tdiffcore_std(opt);\n+\n+\tqueue = &diff_queued_diff;\n+\tfor (i = 0; i < queue->nr; i++) {\n+\t\tstruct diff_filepair *pair = queue->queue[i];\n+\t\tstruct diff_line_range *rg = r;\n+\t\tmmfile_t file_p, file_t;\n+\t\tassert(pair->two->path);\n+\t\twhile (rg) {\n+\t\t\tassert(rg->spec->path);\n+\t\t\tif (!strcmp(rg->spec->path, pair->two->path))\n+\t\t\t\tbreak;\n+\t\t\trg = rg->next;\n+\t\t}\n+\n+\t\tif (rg == NULL)\n+\t\t\tcontinue;\n+\t\trg->touch = 1;\n+\t\tif (rg->nr == 0)\n+\t\t\tcontinue;\n+\n+\t\trg->status = pair->status;\n+\t\tassert(pair->two->sha1_valid);\n+\t\tdiff_populate_filespec(pair->two, 0);\n+\t\tfile_t.ptr = pair->two->data;\n+\t\tfile_t.size = pair->two->size;\n+\n+\t\tif (rg->prev)\n+\t\t\tfree_filespec(rg->prev);\n+\t\trg->prev = pair->one;\n+\t\trg->prev->count++;\n+\t\tif (pair->one->sha1_valid) {\n+\t\t\tdiff_populate_filespec(pair->one, 0);\n+\t\t\tfile_p.ptr = pair->one->data;\n+\t\t\tfile_p.size = pair->one->size;\n+\t\t} else {\n+\t\t\tfile_p.ptr = \"\";\n+\t\t\tfile_p.size = 0;\n+\t\t}\n+\n+\t\tif (cr->nr != 0) {\n+\t\t\tstruct diff_line_range *tmp = xmalloc(sizeof(*tmp));\n+\t\t\tcr->next = tmp;\n+\t\t\tprev_r = cr;\n+\t\t\tcr = tmp;\n+\t\t} else if (cr->spec)\n+\t\t\tDIFF_LINE_RANGE_CLEAR(cr);\n+\n+\t\tDIFF_LINE_RANGE_INIT(cr);\n+\t\tif (pair->one->sha1_valid) {\n+\t\t\tcr->spec = pair->one;\n+\t\t\tcr->spec->count++;\n+\t\t}\n+\n+\t\tcb.interesting = rg;\n+\t\tcb.range = cr;\n+\t\tcb.diff = 0;\n+\t\tcb.plno = cb.tlno = 0;\n+\t\txdi_diff_hunks(&file_p, &file_t, fn, &cb, &xpp, &xecfg);\n+\t\tif (cb.diff)\n+\t\t\tdiff = 1;\n+\t\t/*\n+\t\t * The remain part is the same part.\n+\t\t * Instead of calculating the true line number of the two files,\n+\t\t * use the biggest integer.\n+\t\t */\n+\t\tif (map)\n+\t\t\tmap_range(&cb, 1, cb.plno + 1, INT_MAX, cb.tlno + 1, INT_MAX);\n+\t\telse\n+\t\t\ttake_range(&cb, cb.plno + 1, INT_MAX, cb.tlno + 1, INT_MAX);\n+\t}\n+\topt->output_format = DIFF_FORMAT_NO_OUTPUT;\n+\tdiff_flush(opt);\n+\n+\t/*\n+\t * Collect the untouch ranges, this comes from the files not changed\n+\t * between two commit.\n+\t */\n+\trg = r;\n+\twhile (rg) {\n+\t\t/* clear the touch one to make it usable in next round */\n+\t\tif (rg->touch) {\n+\t\t\trg->touch = 0;\n+\t\t} else {\n+\t\t\tstruct diff_line_range *untouch = diff_line_range_clone(rg);\n+\t\t\tif (prev_r == rr && rr->nr == 0) {\n+\t\t\t\trr = prev_r = untouch;\n+\t\t\t} else {\n+\t\t\t\tprev_r->next = untouch;\n+\t\t\t\tprev_r = untouch;\n+\t\t\t}\n+\t\t}\n+\t\trg = rg->next;\n+\t}\n+\n+\tif (cr->nr == 0) {\n+\t\tDIFF_LINE_RANGE_CLEAR(cr);\n+\t\tfree(cr);\n+\t\tif (prev_r == cr)\n+\t\t\trr = NULL;\n+\t\telse\n+\t\t\tprev_r->next = NULL;\n+\t}\n+\n+\tif (rr) {\n+\t\tassert(p);\n+\t\tadd_line_range(rev, p, rr);\n+\t}\n+\n+\t/* and the ranges of current commit c is updated */\n+\tc->object.flags &= ~RANGE_UPDATE;\n+\tif (diff)\n+\t\tc->object.flags |= NEED_PRINT;\n+\n+\tif (tree1)\n+\t\tfree(tree1);\n+\tif (tree2)\n+\t\tfree(tree2);\n+}\n+\n+static void diff_update_parent_range(struct rev_info *rev,\n+\t\tstruct commit *commit)\n+{\n+\tstruct diff_line_range *r = lookup_line_range(rev, commit);\n+\tstruct commit_list *parents = commit->parents;\n+\tstruct commit *c = NULL;\n+\tif (parents) {\n+\t\tassert(parents->next == NULL);\n+\t\tc = parents->item;\n+\t}\n+\n+\tassign_range_to_parent(rev, commit, c, r, &rev->diffopt, 1);\n+}\n+\n+static void assign_parents_range(struct rev_info *rev, struct commit *commit)\n+{\n+\tstruct commit_list *parents = commit->parents;\n+\tstruct diff_line_range *r = lookup_line_range(rev, commit);\n+\tstruct diff_line_range *evil = NULL, *range = NULL;\n+\tint nontrivial = 0;\n+\n+\t/*\n+\t * If we are in linear history, update range and flush the patch if\n+\t * necessary\n+\t */\n+\tif (parents == NULL || parents->next == NULL)\n+\t\treturn diff_update_parent_range(rev, commit);\n+\n+\t/*\n+\t * Loop on the parents and assign the ranges to different\n+\t * parents, if there is any range left, this commit must\n+\t * be an evil merge.\n+\t */\n+\tevil = diff_line_range_clone_deeply(r);\n+\tparents = commit->parents;\n+\twhile (parents) {\n+\t\tstruct commit *p = parents->item;\n+\t\tassign_range_to_parent(rev, commit, p, r, &rev->diffopt, 1);\n+\t\tassign_range_to_parent(rev, commit, p, evil, &rev->diffopt, 0);\n+\t\tparents = parents->next;\n+\t}\n+\n+\t/*\n+\t * yes, this must be an evil merge.\n+\t */\n+\trange = evil;\n+\twhile (range) {\n+\t\tif (range->nr) {\n+\t\t\tcommit->object.flags |= NEED_PRINT | EVIL_MERGE;\n+\t\t\tnontrivial = 1;\n+\t\t}\n+\t\trange = range->next;\n+\t}\n+\n+\tif (nontrivial)\n+\t\tadd_decoration(&rev->nontrivial_merge, &commit->object, evil);\n+\telse\n+\t\tcleanup(evil);\n+}\n+\ndiff --git a/revision.h b/revision.h\nindex c0d5065..2627ec4 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -15,7 +15,9 @@\n #define ADDED\t\t(1u<<7)\t/* Parents already parsed and added? */\n #define SYMMETRIC_LEFT\t(1u<<8)\n #define RANGE_UPDATE\t(1u<<9) /* for line level traverse */\n-#define ALL_REV_FLAGS\t((1u<<10)-1)\n+#define NEED_PRINT\t(1u<<10)\n+#define EVIL_MERGE\t(1u<<11)\n+#define ALL_REV_FLAGS\t((1u<<12)-1)\n \n #define DECORATE_SHORT_REFS\t1\n #define DECORATE_FULL_REFS\t2\n@@ -141,6 +143,7 @@ struct rev_info {\n \tint count_right;\n \t/* line level range that we are chasing */\n \tstruct decoration line_range;\n+\tstruct decoration nontrivial_merge;\n };\n \n #define REV_TREE_SAME\t\t0\n-- \n1.7.0.2.273.gc2413.dirty\n"}]}