On 07/30, Johannes Schindelin wrote:
> Hi Thomas,
>
> On Sun, 29 Jul 2018, Thomas Gummerer wrote:
>
> > On 07/21, Johannes Schindelin via GitGitGadget wrote:
> > >
> > > [...]
> > >
> > > +static void find_exact_matches(struct string_list *a, struct string_list *b)
> > > +{
> > > + struct hashmap map;
> > > + int i;
> > > +
> > > + hashmap_init(&map, (hashmap_cmp_fn)patch_util_cmp, NULL, 0);
> > > +
> > > + /* First, add the patches of a to a hash map */
> > > + for (i = 0; i < a->nr; i++) {
> > > + struct patch_util *util = a->items[i].util;
> > > +
> > > + util->i = i;
> > > + util->patch = a->items[i].string;
> > > + util->diff = util->patch + util->diff_offset;
> > > + hashmap_entry_init(util, strhash(util->diff));
> > > + hashmap_add(&map, util);
> > > + }
> > > +
> > > + /* Now try to find exact matches in b */
> > > + for (i = 0; i < b->nr; i++) {
> > > + struct patch_util *util = b->items[i].util, *other;
> > > +
> > > + util->i = i;
> > > + util->patch = b->items[i].string;
> > > + util->diff = util->patch + util->diff_offset;
> > > + hashmap_entry_init(util, strhash(util->diff));
> > > + other = hashmap_remove(&map, util, NULL);
> > > + if (other) {
> > > + if (other->matching >= 0)
> > > + BUG("already assigned!");
> > > +
> > > + other->matching = i;
> > > + util->matching = other->i;
> > > + }
> > > + }
> >
> > One possibly interesting corner case here is what happens when there
> > are two patches that have the exact same diff, for example in the
> > pathological case of commit A doing something, commit B reverting
> > commit A, and then commit C reverting commit B, so it ends up with the
> > same diff.
> >
> > Having those same commits unchanged in both ranges (e.g. if a commit
> > earlier in the range has been changed, and range B has been rebased on
> > top of that), we'd get the following mapping from range A to range B
> > for the commits in question:
> >
> > A -> C
> > B -> B
> > C -> A
> >
> > Which is not quite what I would expect as the user (even though it is
> > a valid mapping, and it probably doesn't matter too much for the end
> > result of the range diff, as nothing has changed between the commits
> > anyway). So I'm not sure it's worth fixing this, as it is a
> > pathological case, and nothing really breaks.
>
> Indeed. As far as I am concerned, this falls squarely into the "let's
> cross that bridge when, or if, we reach it" category.
Makes sense, this can definitely be addressed later.
> > > +
> > > + hashmap_free(&map, 0);
> > > +}
> > > +
> > > +static void diffsize_consume(void *data, char *line, unsigned long len)
> > > +{
> > > + (*(int *)data)++;
> > > +}
> > > +
> > > +static int diffsize(const char *a, const char *b)
> > > +{
> > > + xpparam_t pp = { 0 };
> > > + xdemitconf_t cfg = { 0 };
> > > + mmfile_t mf1, mf2;
> > > + int count = 0;
> > > +
> > > + mf1.ptr = (char *)a;
> > > + mf1.size = strlen(a);
> > > + mf2.ptr = (char *)b;
> > > + mf2.size = strlen(b);
> > > +
> > > + cfg.ctxlen = 3;
> > > + if (!xdi_diff_outf(&mf1, &mf2, diffsize_consume, &count, &pp, &cfg))
> > > + return count;
> > > +
> > > + error(_("failed to generate diff"));
> > > + return COST_MAX;
> > > +}
> > > +
> > > +static void get_correspondences(struct string_list *a, struct string_list *b,
> > > + int creation_factor)
> > > +{
> > > + int n = a->nr + b->nr;
> > > + int *cost, c, *a2b, *b2a;
> > > + int i, j;
> > > +
> > > + ALLOC_ARRAY(cost, st_mult(n, n));
> > > + ALLOC_ARRAY(a2b, n);
> > > + ALLOC_ARRAY(b2a, n);
> > > +
> > > + for (i = 0; i < a->nr; i++) {
> > > + struct patch_util *a_util = a->items[i].util;
> > > +
> > > + for (j = 0; j < b->nr; j++) {
> > > + struct patch_util *b_util = b->items[j].util;
> > > +
> > > + if (a_util->matching == j)
> > > + c = 0;
> > > + else if (a_util->matching < 0 && b_util->matching < 0)
> > > + c = diffsize(a_util->diff, b_util->diff);
> > > + else
> > > + c = COST_MAX;
> > > + cost[i + n * j] = c;
> > > + }
> > > +
> > > + c = a_util->matching < 0 ?
> > > + a_util->diffsize * creation_factor / 100 : COST_MAX;
> > > + for (j = b->nr; j < n; j++)
> > > + cost[i + n * j] = c;
> > > + }
> > > +
> > > + for (j = 0; j < b->nr; j++) {
> > > + struct patch_util *util = b->items[j].util;
> > > +
> > > + c = util->matching < 0 ?
> > > + util->diffsize * creation_factor / 100 : COST_MAX;
> > > + for (i = a->nr; i < n; i++)
> > > + cost[i + n * j] = c;
> > > + }
> > > +
> > > + for (i = a->nr; i < n; i++)
> > > + for (j = b->nr; j < n; j++)
> > > + cost[i + n * j] = 0;
> > > +
> > > + compute_assignment(n, n, cost, a2b, b2a);
> > > +
> > > + for (i = 0; i < a->nr; i++)
> > > + if (a2b[i] >= 0 && a2b[i] < b->nr) {
> > > + struct patch_util *a_util = a->items[i].util;
> > > + struct patch_util *b_util = b->items[a2b[i]].util;
> > > +
> > > + a_util->matching = a2b[i];
> > > + b_util->matching = i;
> >
> > So here we re-assign 'matching' in the struct regardless of whether it
> > was assigned before while searching for exact matches or not.
>
> If `matching` were assigned here, it would indicate a bug in the code, I
> think. Before this loop, all of the `matching` fields should be `NULL`,
> and the `compute_assignment()` function is expected to populate `a2b` and
> `b2a` appropriately, i.e. no "double booking".
Hmm we are using the 'matching' fields in the loops above, e.g.:
if (a_util->matching == j)
c = 0;
They're also ints, so they can't be `NULL`, right? So what I was
thinking is that we could do
if (a_util->matching < 0) {
a_util->matching = a2b[i];
b_util->matching = i;
}
Anyway, I don't think it really matters, as there is no "double
booking", so we should essentially get the same results.
> > Shouldn't diffsize for matching patches also be 0? So are we doing
> > the 'find_exact_matches()' bit only as an optimization, or am I
> > missing some other reason why that is beneficial?
>
> An optimization.
>
> Remember, the linear assignment algorithm runs in O(n^3). That's not a
> laughing matter by any stretch of imagination. The more stuff we can get
> out of the way, as quickly as possible, the less it hurts to have a cubic
> runtime complexity.
Makes sense, that's what I was expecting, just wanted to double check
that I didn't miss something. Thanks for confirming!
> > > + }
> > > +
> > > + free(cost);
> > > + free(a2b);
> > > + free(b2a);
> > > +}
> > > +
> > > +static const char *short_oid(struct patch_util *util)
> > > +{
> > > + return find_unique_abbrev(&util->oid, DEFAULT_ABBREV);
> > > +}
> > > +
> > > +static void output(struct string_list *a, struct string_list *b)
> > > +{
> > > + int i;
> > > +
> > > + for (i = 0; i < b->nr; i++) {
> > > + struct patch_util *util = b->items[i].util, *prev;
> > > +
> > > + if (util->matching < 0)
> > > + printf("-: -------- > %d: %s\n",
> > > + i + 1, short_oid(util));
> > > + else {
> > > + prev = a->items[util->matching].util;
> > > + printf("%d: %s ! %d: %s\n",
> > > + util->matching + 1, short_oid(prev),
> > > + i + 1, short_oid(util));
> > > + }
> > > + }
> > > +
> > > + for (i = 0; i < a->nr; i++) {
> > > + struct patch_util *util = a->items[i].util;
> > > +
> > > + if (util->matching < 0)
> > > + printf("%d: %s < -: --------\n",
> > > + i + 1, short_oid(util));
> > > + }
> > > +}
> > > +
> > > +int show_range_diff(const char *range1, const char *range2,
> > > + int creation_factor)
> > > +{
> > > + int res = 0;
> > > +
> > > + struct string_list branch1 = STRING_LIST_INIT_DUP;
> > > + struct string_list branch2 = STRING_LIST_INIT_DUP;
> > > +
> > > + if (read_patches(range1, &branch1))
> > > + res = error(_("could not parse log for '%s'"), range1);
> > > + if (!res && read_patches(range2, &branch2))
> > > + res = error(_("could not parse log for '%s'"), range2);
> > > +
> > > + if (!res) {
> > > + find_exact_matches(&branch1, &branch2);
> >
> > Note to self: here we assign the matching member of struct patch_util
> > for each patch in both ranges to a patch number in the other range if
> > it is an exact match.
> >
> > We also assign the patch and diff members, and number the patches
> > using the 'i' member of struct patch_util. Let's see if that
> > numbering is still useful later.
> >
> > > + get_correspondences(&branch1, &branch2, creation_factor);
> >
> > And here we use the linear assignment algorithm to match the rest of
> > the commits.
> >
> > > + output(&branch1, &branch2);
> >
> > And finally we print the output. We don't seem to use the util->i
> > that's assigned for range b (or range 2) anywhere at the moment, which
> > I was wondering about earlier, so I assume it's there mainly for
> > symmetry, but it doesn't really hurt other than me wondering what it
> > was for.
>
> It's there because it would require extra care to do it only for one side.
>
> > > + }
> > > +
> > > + string_list_clear(&branch1, 1);
> > > + string_list_clear(&branch2, 1);
> > > +
> > > + return res;
> > > +}
> > > diff --git a/range-diff.h b/range-diff.h
> > > new file mode 100644
> > > index 000000000..dd30449c4
> > > --- /dev/null
> > > +++ b/range-diff.h
> > > @@ -0,0 +1,7 @@
> > > +#ifndef BRANCH_DIFF_H
> > > +#define BRANCH_DIFF_H
> >
> > s/BRANCH/RANGE/ above?
>
> Good eyes.
>
> Thank you for your review. It is nice to see that you can follow the code
> and come to the same conclusions as I. Can I always have you as reviewer?
Glad I could help. Can I have more hours in a day? ;) I wish I had
more time for reviewing code, but sadly the time I have is limited.
Which is why I only got to review this now as well. I did enjoy the
read!
> Ciao,
> Dscho
>
> > > +int show_range_diff(const char *range1, const char *range2,
> > > + int creation_factor);
> > > +
> > > +#endif
> > > --
> > > gitgitgadget
> > >
> >
