Andrew's git - gitweb.git/blob

   1#include "cache.h"
   2#include "range-diff.h"
   3#include "string-list.h"
   4#include "run-command.h"
   5#include "argv-array.h"
   6#include "hashmap.h"
   7#include "xdiff-interface.h"
   8#include "linear-assignment.h"
   9#include "diffcore.h"
  10
  11struct patch_util {
  12        /* For the search for an exact match */
  13        struct hashmap_entry e;
  14        const char *diff, *patch;
  15
  16        int i, shown;
  17        int diffsize;
  18        size_t diff_offset;
  19        /* the index of the matching item in the other branch, or -1 */
  20        int matching;
  21        struct object_id oid;
  22};
  23
  24/*
  25 * Reads the patches into a string list, with the `util` field being populated
  26 * as struct object_id (will need to be free()d).
  27 */
  28static int read_patches(const char *range, struct string_list *list)
  29{
  30        struct child_process cp = CHILD_PROCESS_INIT;
  31        FILE *in;
  32        struct strbuf buf = STRBUF_INIT, line = STRBUF_INIT;
  33        struct patch_util *util = NULL;
  34        int in_header = 1;
  35
  36        argv_array_pushl(&cp.args, "log", "--no-color", "-p", "--no-merges",
  37                        "--reverse", "--date-order", "--decorate=no",
  38                        "--no-abbrev-commit", range,
  39                        NULL);
  40        cp.out = -1;
  41        cp.no_stdin = 1;
  42        cp.git_cmd = 1;
  43
  44        if (start_command(&cp))
  45                return error_errno(_("could not start `log`"));
  46        in = fdopen(cp.out, "r");
  47        if (!in) {
  48                error_errno(_("could not read `log` output"));
  49                finish_command(&cp);
  50                return -1;
  51        }
  52
  53        while (strbuf_getline(&line, in) != EOF) {
  54                const char *p;
  55
  56                if (skip_prefix(line.buf, "commit ", &p)) {
  57                        if (util) {
  58                                string_list_append(list, buf.buf)->util = util;
  59                                strbuf_reset(&buf);
  60                        }
  61                        util = xcalloc(sizeof(*util), 1);
  62                        if (get_oid(p, &util->oid)) {
  63                                error(_("could not parse commit '%s'"), p);
  64                                free(util);
  65                                string_list_clear(list, 1);
  66                                strbuf_release(&buf);
  67                                strbuf_release(&line);
  68                                fclose(in);
  69                                finish_command(&cp);
  70                                return -1;
  71                        }
  72                        util->matching = -1;
  73                        in_header = 1;
  74                        continue;
  75                }
  76
  77                if (starts_with(line.buf, "diff --git")) {
  78                        in_header = 0;
  79                        strbuf_addch(&buf, '\n');
  80                        if (!util->diff_offset)
  81                                util->diff_offset = buf.len;
  82                        strbuf_addbuf(&buf, &line);
  83                } else if (in_header) {
  84                        if (starts_with(line.buf, "Author: ")) {
  85                                strbuf_addbuf(&buf, &line);
  86                                strbuf_addstr(&buf, "\n\n");
  87                        } else if (starts_with(line.buf, "    ")) {
  88                                strbuf_rtrim(&line);
  89                                strbuf_addbuf(&buf, &line);
  90                                strbuf_addch(&buf, '\n');
  91                        }
  92                        continue;
  93                } else if (starts_with(line.buf, "@@ "))
  94                        strbuf_addstr(&buf, "@@");
  95                else if (!line.buf[0] || starts_with(line.buf, "index "))
  96                        /*
  97                         * A completely blank (not ' \n', which is context)
  98                         * line is not valid in a diff.  We skip it
  99                         * silently, because this neatly handles the blank
 100                         * separator line between commits in git-log
 101                         * output.
 102                         *
 103                         * We also want to ignore the diff's `index` lines
 104                         * because they contain exact blob hashes in which
 105                         * we are not interested.
 106                         */
 107                        continue;
 108                else
 109                        strbuf_addbuf(&buf, &line);
 110
 111                strbuf_addch(&buf, '\n');
 112                util->diffsize++;
 113        }
 114        fclose(in);
 115        strbuf_release(&line);
 116
 117        if (util)
 118                string_list_append(list, buf.buf)->util = util;
 119        strbuf_release(&buf);
 120
 121        if (finish_command(&cp))
 122                return -1;
 123
 124        return 0;
 125}
 126
 127static int patch_util_cmp(const void *dummy, const struct patch_util *a,
 128                     const struct patch_util *b, const char *keydata)
 129{
 130        return strcmp(a->diff, keydata ? keydata : b->diff);
 131}
 132
 133static void find_exact_matches(struct string_list *a, struct string_list *b)
 134{
 135        struct hashmap map;
 136        int i;
 137
 138        hashmap_init(&map, (hashmap_cmp_fn)patch_util_cmp, NULL, 0);
 139
 140        /* First, add the patches of a to a hash map */
 141        for (i = 0; i < a->nr; i++) {
 142                struct patch_util *util = a->items[i].util;
 143
 144                util->i = i;
 145                util->patch = a->items[i].string;
 146                util->diff = util->patch + util->diff_offset;
 147                hashmap_entry_init(util, strhash(util->diff));
 148                hashmap_add(&map, util);
 149        }
 150
 151        /* Now try to find exact matches in b */
 152        for (i = 0; i < b->nr; i++) {
 153                struct patch_util *util = b->items[i].util, *other;
 154
 155                util->i = i;
 156                util->patch = b->items[i].string;
 157                util->diff = util->patch + util->diff_offset;
 158                hashmap_entry_init(util, strhash(util->diff));
 159                other = hashmap_remove(&map, util, NULL);
 160                if (other) {
 161                        if (other->matching >= 0)
 162                                BUG("already assigned!");
 163
 164                        other->matching = i;
 165                        util->matching = other->i;
 166                }
 167        }
 168
 169        hashmap_free(&map, 0);
 170}
 171
 172static void diffsize_consume(void *data, char *line, unsigned long len)
 173{
 174        (*(int *)data)++;
 175}
 176
 177static int diffsize(const char *a, const char *b)
 178{
 179        xpparam_t pp = { 0 };
 180        xdemitconf_t cfg = { 0 };
 181        mmfile_t mf1, mf2;
 182        int count = 0;
 183
 184        mf1.ptr = (char *)a;
 185        mf1.size = strlen(a);
 186        mf2.ptr = (char *)b;
 187        mf2.size = strlen(b);
 188
 189        cfg.ctxlen = 3;
 190        if (!xdi_diff_outf(&mf1, &mf2, diffsize_consume, &count, &pp, &cfg))
 191                return count;
 192
 193        error(_("failed to generate diff"));
 194        return COST_MAX;
 195}
 196
 197static void get_correspondences(struct string_list *a, struct string_list *b,
 198                                int creation_factor)
 199{
 200        int n = a->nr + b->nr;
 201        int *cost, c, *a2b, *b2a;
 202        int i, j;
 203
 204        ALLOC_ARRAY(cost, st_mult(n, n));
 205        ALLOC_ARRAY(a2b, n);
 206        ALLOC_ARRAY(b2a, n);
 207
 208        for (i = 0; i < a->nr; i++) {
 209                struct patch_util *a_util = a->items[i].util;
 210
 211                for (j = 0; j < b->nr; j++) {
 212                        struct patch_util *b_util = b->items[j].util;
 213
 214                        if (a_util->matching == j)
 215                                c = 0;
 216                        else if (a_util->matching < 0 && b_util->matching < 0)
 217                                c = diffsize(a_util->diff, b_util->diff);
 218                        else
 219                                c = COST_MAX;
 220                        cost[i + n * j] = c;
 221                }
 222
 223                c = a_util->matching < 0 ?
 224                        a_util->diffsize * creation_factor / 100 : COST_MAX;
 225                for (j = b->nr; j < n; j++)
 226                        cost[i + n * j] = c;
 227        }
 228
 229        for (j = 0; j < b->nr; j++) {
 230                struct patch_util *util = b->items[j].util;
 231
 232                c = util->matching < 0 ?
 233                        util->diffsize * creation_factor / 100 : COST_MAX;
 234                for (i = a->nr; i < n; i++)
 235                        cost[i + n * j] = c;
 236        }
 237
 238        for (i = a->nr; i < n; i++)
 239                for (j = b->nr; j < n; j++)
 240                        cost[i + n * j] = 0;
 241
 242        compute_assignment(n, n, cost, a2b, b2a);
 243
 244        for (i = 0; i < a->nr; i++)
 245                if (a2b[i] >= 0 && a2b[i] < b->nr) {
 246                        struct patch_util *a_util = a->items[i].util;
 247                        struct patch_util *b_util = b->items[a2b[i]].util;
 248
 249                        a_util->matching = a2b[i];
 250                        b_util->matching = i;
 251                }
 252
 253        free(cost);
 254        free(a2b);
 255        free(b2a);
 256}
 257
 258static const char *short_oid(struct patch_util *util)
 259{
 260        return find_unique_abbrev(&util->oid, DEFAULT_ABBREV);
 261}
 262
 263static struct diff_filespec *get_filespec(const char *name, const char *p)
 264{
 265        struct diff_filespec *spec = alloc_filespec(name);
 266
 267        fill_filespec(spec, &null_oid, 0, 0644);
 268        spec->data = (char *)p;
 269        spec->size = strlen(p);
 270        spec->should_munmap = 0;
 271        spec->is_stdin = 1;
 272
 273        return spec;
 274}
 275
 276static void patch_diff(const char *a, const char *b,
 277                              struct diff_options *diffopt)
 278{
 279        diff_queue(&diff_queued_diff,
 280                   get_filespec("a", a), get_filespec("b", b));
 281
 282        diffcore_std(diffopt);
 283        diff_flush(diffopt);
 284}
 285
 286static void output(struct string_list *a, struct string_list *b,
 287                   struct diff_options *diffopt)
 288{
 289        int i = 0, j = 0;
 290
 291        /*
 292         * We assume the user is really more interested in the second argument
 293         * ("newer" version). To that end, we print the output in the order of
 294         * the RHS (the `b` parameter). To put the LHS (the `a` parameter)
 295         * commits that are no longer in the RHS into a good place, we place
 296         * them once we have shown all of their predecessors in the LHS.
 297         */
 298
 299        while (i < a->nr || j < b->nr) {
 300                struct patch_util *a_util, *b_util;
 301                a_util = i < a->nr ? a->items[i].util : NULL;
 302                b_util = j < b->nr ? b->items[j].util : NULL;
 303
 304                /* Skip all the already-shown commits from the LHS. */
 305                while (i < a->nr && a_util->shown)
 306                        a_util = ++i < a->nr ? a->items[i].util : NULL;
 307
 308                /* Show unmatched LHS commit whose predecessors were shown. */
 309                if (i < a->nr && a_util->matching < 0) {
 310                        printf("%d: %s < -: --------\n",
 311                               i + 1, short_oid(a_util));
 312                        i++;
 313                        continue;
 314                }
 315
 316                /* Show unmatched RHS commits. */
 317                while (j < b->nr && b_util->matching < 0) {
 318                        printf("-: -------- > %d: %s\n",
 319                               j + 1, short_oid(b_util));
 320                        b_util = ++j < b->nr ? b->items[j].util : NULL;
 321                }
 322
 323                /* Show matching LHS/RHS pair. */
 324                if (j < b->nr) {
 325                        a_util = a->items[b_util->matching].util;
 326                        printf("%d: %s ! %d: %s\n",
 327                               b_util->matching + 1, short_oid(a_util),
 328                               j + 1, short_oid(b_util));
 329                        if (!(diffopt->output_format & DIFF_FORMAT_NO_OUTPUT))
 330                                patch_diff(a->items[b_util->matching].string,
 331                                           b->items[j].string, diffopt);
 332                        a_util->shown = 1;
 333                        j++;
 334                }
 335        }
 336}
 337
 338int show_range_diff(const char *range1, const char *range2,
 339                    int creation_factor, struct diff_options *diffopt)
 340{
 341        int res = 0;
 342
 343        struct string_list branch1 = STRING_LIST_INIT_DUP;
 344        struct string_list branch2 = STRING_LIST_INIT_DUP;
 345
 346        if (read_patches(range1, &branch1))
 347                res = error(_("could not parse log for '%s'"), range1);
 348        if (!res && read_patches(range2, &branch2))
 349                res = error(_("could not parse log for '%s'"), range2);
 350
 351        if (!res) {
 352                find_exact_matches(&branch1, &branch2);
 353                get_correspondences(&branch1, &branch2, creation_factor);
 354                output(&branch1, &branch2, diffopt);
 355        }
 356
 357        string_list_clear(&branch1, 1);
 358        string_list_clear(&branch2, 1);
 359
 360        return res;
 361}