tree-diff.c

   1 /*
   2  * Helper functions for tree diff generation
   3  */
   4 #include "cache.h"
   5 #include "diff.h"
   6
   7 // What paths are we interested in?
   8 static int nr_paths = 0;
   9 static const char **paths = NULL;
  10 static int *pathlens = NULL;
  11
  12 static void update_tree_entry(struct tree_desc *desc)
  13 {
  14         void *buf = desc->buf;
  15         unsigned long size = desc->size;
  16         int len = strlen(buf) + 1 + 20;
  17
  18         if (size < len)
  19                 die("corrupt tree file");
  20         desc->buf = buf + len;
  21         desc->size = size - len;
  22 }
  23
  24 static const unsigned char *extract(struct tree_desc *desc, const char **pathp, unsigned int *modep)
  25 {
  26         void *tree = desc->buf;
  27         unsigned long size = desc->size;
  28         int len = strlen(tree)+1;
  29         const unsigned char *sha1 = tree + len;
  30         const char *path = strchr(tree, ' ');
  31         unsigned int mode;
  32
  33         if (!path || size < len + 20 || sscanf(tree, "%o", &mode) != 1)
  34                 die("corrupt tree file");
  35         *pathp = path+1;
  36         *modep = DIFF_FILE_CANON_MODE(mode);
  37         return sha1;
  38 }
  39
  40 static char *malloc_base(const char *base, const char *path, int pathlen)
  41 {
  42         int baselen = strlen(base);
  43         char *newbase = xmalloc(baselen + pathlen + 2);
  44         memcpy(newbase, base, baselen);
  45         memcpy(newbase + baselen, path, pathlen);
  46         memcpy(newbase + baselen + pathlen, "/", 2);
  47         return newbase;
  48 }
  49
  50 static int show_entry(struct diff_options *opt, const char *prefix, struct tree_desc *desc, const char *base);
  51
  52 static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const char *base, struct diff_options *opt)
  53 {
  54         unsigned mode1, mode2;
  55         const char *path1, *path2;
  56         const unsigned char *sha1, *sha2;
  57         int cmp, pathlen1, pathlen2;
  58
  59         sha1 = extract(t1, &path1, &mode1);
  60         sha2 = extract(t2, &path2, &mode2);
  61
  62         pathlen1 = strlen(path1);
  63         pathlen2 = strlen(path2);
  64         cmp = base_name_compare(path1, pathlen1, mode1, path2, pathlen2, mode2);
  65         if (cmp < 0) {
  66                 show_entry(opt, "-", t1, base);
  67                 return -1;
  68         }
  69         if (cmp > 0) {
  70                 show_entry(opt, "+", t2, base);
  71                 return 1;
  72         }
  73         if (!opt->find_copies_harder &&
  74             !memcmp(sha1, sha2, 20) && mode1 == mode2)
  75                 return 0;
  76
  77         /*
  78          * If the filemode has changed to/from a directory from/to a regular
  79          * file, we need to consider it a remove and an add.
  80          */
  81         if (S_ISDIR(mode1) != S_ISDIR(mode2)) {
  82                 show_entry(opt, "-", t1, base);
  83                 show_entry(opt, "+", t2, base);
  84                 return 0;
  85         }
  86
  87         if (opt->recursive && S_ISDIR(mode1)) {
  88                 int retval;
  89                 char *newbase = malloc_base(base, path1, pathlen1);
  90                 if (opt->tree_in_recursive)
  91                         opt->change(opt, mode1, mode2,
  92                                     sha1, sha2, base, path1);
  93                 retval = diff_tree_sha1(sha1, sha2, newbase, opt);
  94                 free(newbase);
  95                 return retval;
  96         }
  97
  98         opt->change(opt, mode1, mode2, sha1, sha2, base, path1);
  99         return 0;
 100 }
 101
 102 static int interesting(struct tree_desc *desc, const char *base)
 103 {
 104         const char *path;
 105         unsigned mode;
 106         int i;
 107         int baselen, pathlen;
 108
 109         if (!nr_paths)
 110                 return 1;
 111
 112         (void)extract(desc, &path, &mode);
 113
 114         pathlen = strlen(path);
 115         baselen = strlen(base);
 116
 117         for (i=0; i < nr_paths; i++) {
 118                 const char *match = paths[i];
 119                 int matchlen = pathlens[i];
 120
 121                 if (baselen >= matchlen) {
 122                         /* If it doesn't match, move along... */
 123                         if (strncmp(base, match, matchlen))
 124                                 continue;
 125
 126                         /* The base is a subdirectory of a path which was specified. */
 127                         return 1;
 128                 }
 129
 130                 /* Does the base match? */
 131                 if (strncmp(base, match, baselen))
 132                         continue;
 133
 134                 match += baselen;
 135                 matchlen -= baselen;
 136
 137                 if (pathlen > matchlen)
 138                         continue;
 139
 140                 if (matchlen > pathlen) {
 141                         if (match[pathlen] != '/')
 142                                 continue;
 143                         if (!S_ISDIR(mode))
 144                                 continue;
 145                 }
 146
 147                 if (strncmp(path, match, pathlen))
 148                         continue;
 149
 150                 return 1;
 151         }
 152         return 0; /* No matches */
 153 }
 154
 155 /* A whole sub-tree went away or appeared */
 156 static void show_tree(struct diff_options *opt, const char *prefix, struct tree_desc *desc, const char *base)
 157 {
 158         while (desc->size) {
 159                 if (interesting(desc, base))
 160                         show_entry(opt, prefix, desc, base);
 161                 update_tree_entry(desc);
 162         }
 163 }
 164
 165 /* A file entry went away or appeared */
 166 static int show_entry(struct diff_options *opt, const char *prefix, struct tree_desc *desc, const char *base)
 167 {
 168         unsigned mode;
 169         const char *path;
 170         const unsigned char *sha1 = extract(desc, &path, &mode);
 171
 172         if (opt->recursive && S_ISDIR(mode)) {
 173                 char type[20];
 174                 char *newbase = malloc_base(base, path, strlen(path));
 175                 struct tree_desc inner;
 176                 void *tree;
 177
 178                 tree = read_sha1_file(sha1, type, &inner.size);
 179                 if (!tree || strcmp(type, "tree"))
 180                         die("corrupt tree sha %s", sha1_to_hex(sha1));
 181
 182                 inner.buf = tree;
 183                 show_tree(opt, prefix, &inner, newbase);
 184
 185                 free(tree);
 186                 free(newbase);
 187                 return 0;
 188         }
 189
 190         opt->add_remove(opt, prefix[0], mode, sha1, base, path);
 191         return 0;
 192 }
 193
 194 int diff_tree(struct tree_desc *t1, struct tree_desc *t2, const char *base, struct diff_options *opt)
 195 {
 196         while (t1->size | t2->size) {
 197                 if (nr_paths && t1->size && !interesting(t1, base)) {
 198                         update_tree_entry(t1);
 199                         continue;
 200                 }
 201                 if (nr_paths && t2->size && !interesting(t2, base)) {
 202                         update_tree_entry(t2);
 203                         continue;
 204                 }
 205                 if (!t1->size) {
 206                         show_entry(opt, "+", t2, base);
 207                         update_tree_entry(t2);
 208                         continue;
 209                 }
 210                 if (!t2->size) {
 211                         show_entry(opt, "-", t1, base);
 212                         update_tree_entry(t1);
 213                         continue;
 214                 }
 215                 switch (compare_tree_entry(t1, t2, base, opt)) {
 216                 case -1:
 217                         update_tree_entry(t1);
 218                         continue;
 219                 case 0:
 220                         update_tree_entry(t1);
 221                         /* Fallthrough */
 222                 case 1:
 223                         update_tree_entry(t2);
 224                         continue;
 225                 }
 226                 die("git-diff-tree: internal error");
 227         }
 228         return 0;
 229 }
 230
 231 int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)
 232 {
 233         void *tree1, *tree2;
 234         struct tree_desc t1, t2;
 235         int retval;
 236
 237         tree1 = read_object_with_reference(old, "tree", &t1.size, NULL);
 238         if (!tree1)
 239                 die("unable to read source tree (%s)", sha1_to_hex(old));
 240         tree2 = read_object_with_reference(new, "tree", &t2.size, NULL);
 241         if (!tree2)
 242                 die("unable to read destination tree (%s)", sha1_to_hex(new));
 243         t1.buf = tree1;
 244         t2.buf = tree2;
 245         retval = diff_tree(&t1, &t2, base, opt);
 246         free(tree1);
 247         free(tree2);
 248         return retval;
 249 }
 250
 251 static int count_paths(const char **paths)
 252 {
 253         int i = 0;
 254         while (*paths++)
 255                 i++;
 256         return i;
 257 }
 258
 259 void diff_tree_setup_paths(const char **p)
 260 {
 261         if (p) {
 262                 int i;
 263
 264                 paths = p;
 265                 nr_paths = count_paths(paths);
 266                 if (nr_paths == 0) {
 267                         pathlens = NULL;
 268                         return;
 269                 }
 270                 pathlens = xmalloc(nr_paths * sizeof(int));
 271                 for (i=0; i<nr_paths; i++)
 272                         pathlens[i] = strlen(paths[i]);
 273         }
 274 }