rev-tree.c

   1 #include "cache.h"
   2
   3 /*
   4  * The low 16 bits of the "flags" field shows whether
   5  * a commit is part of the path to the root for that
   6  * parent.
   7  *
   8  * Bit 16 is an internal flag that we've seen the
   9  * definition for this rev, and not just seen it as
  10  * a parent target.
  11  */
  12 #define MAX_COMMITS (16)
  13 #define marked(rev)     ((rev)->flags & 0xffff)
  14 #define SEEN 0x10000
  15
  16 static int show_edges = 0;
  17 static int basemask = 0;
  18
  19 struct parent {
  20         struct revision *parent;
  21         struct parent *next;
  22 };
  23
  24 struct revision {
  25         unsigned int flags;
  26         unsigned char sha1[20];
  27         struct parent *parent;
  28 };
  29
  30 static struct revision **revs;
  31 static int nr_revs, rev_allocs;
  32
  33 static int find_rev(unsigned char *sha1)
  34 {
  35         int first = 0, last = nr_revs;
  36
  37         while (first < last) {
  38                 int next = (first + last) / 2;
  39                 struct revision *rev = revs[next];
  40                 int cmp;
  41
  42                 cmp = memcmp(sha1, rev->sha1, 20);
  43                 if (!cmp)
  44                         return next;
  45                 if (cmp < 0) {
  46                         last = next;
  47                         continue;
  48                 }
  49                 first = next+1;
  50         }
  51         return -first-1;
  52 }
  53
  54 static struct revision *lookup_rev(unsigned char *sha1)
  55 {
  56         int pos = find_rev(sha1);
  57         struct revision *n;
  58
  59         if (pos >= 0)
  60                 return revs[pos];
  61
  62         pos = -pos-1;
  63
  64         if (rev_allocs == nr_revs) {
  65                 rev_allocs = alloc_nr(rev_allocs);
  66                 revs = realloc(revs, rev_allocs * sizeof(struct revision *));
  67         }
  68         n = malloc(sizeof(struct revision));
  69
  70         n->flags = 0;
  71         memcpy(n->sha1, sha1, 20);
  72         n->parent = NULL;
  73
  74         /* Insert it into the right place */
  75         memmove(revs + pos + 1, revs + pos, (nr_revs - pos) * sizeof(struct revision *));
  76         revs[pos] = n;
  77         nr_revs++;
  78
  79         return n;
  80 }
  81
  82 static int add_relationship(struct revision *rev, unsigned char *parent_sha)
  83 {
  84         struct revision *parent_rev = lookup_rev(parent_sha);
  85         struct parent **pp = &rev->parent, *p;
  86
  87         while ((p = *pp) != NULL) {
  88                 if (p->parent == parent_rev)
  89                         return 0;
  90                 pp = &p->next;
  91         }
  92
  93         p = malloc(sizeof(*p));
  94         p->parent = parent_rev;
  95         p->next = NULL;
  96         *pp = p;
  97         return 1;
  98 }
  99
 100 static int parse_commit(unsigned char *sha1)
 101 {
 102         struct revision *rev = lookup_rev(sha1);
 103
 104         if (!(rev->flags & SEEN)) {
 105                 void *buffer;
 106                 unsigned long size;
 107                 char type[20];
 108                 unsigned char parent[20];
 109
 110                 rev->flags |= SEEN;
 111                 buffer = read_sha1_file(sha1, type, &size);
 112                 if (!buffer || strcmp(type, "commit"))
 113                         return -1;
 114                 buffer += 46; /* "tree " + "hex sha1" + "\n" */
 115                 while (!memcmp(buffer, "parent ", 7) && !get_sha1_hex(buffer+7, parent)) {
 116                         add_relationship(rev, parent);
 117                         parse_commit(parent);
 118                         buffer += 48;   /* "parent " + "hex sha1" + "\n" */
 119                 }
 120         }
 121         return 0;
 122 }
 123
 124 static void read_cache_file(const char *path)
 125 {
 126         FILE *file = fopen(path, "r");
 127         char line[100];
 128
 129         if (!file)
 130                 usage("bad revtree cache file (%s)", path);
 131
 132         while (fgets(line, sizeof(line), file)) {
 133                 unsigned char sha1[20], parent[20];
 134                 struct revision *rev;
 135
 136                 if (get_sha1_hex(line, sha1) || get_sha1_hex(line + 41, parent))
 137                         usage("bad rev-tree cache file %s", path);
 138                 rev = lookup_rev(sha1);
 139                 rev->flags |= SEEN;
 140                 add_relationship(rev, parent);
 141         }
 142         fclose(file);
 143 }
 144
 145 static void mark_sha1_path(struct revision *rev, unsigned int mask)
 146 {
 147         struct parent *p;
 148
 149         if (rev->flags & mask)
 150                 return;
 151
 152         rev->flags |= mask;
 153         p = rev->parent;
 154         while (p) {
 155                 mark_sha1_path(p->parent, mask);
 156                 p = p->next;
 157         }
 158 }
 159
 160 /*
 161  * Some revisions are less interesting than others.
 162  *
 163  * For example, if we use a cache-file, that one may contain
 164  * revisions that were never used. They are never interesting.
 165  *
 166  * And sometimes we're only interested in "edge" commits, ie
 167  * places where the marking changes between parent and child.
 168  */
 169 static int interesting(struct revision *rev)
 170 {
 171         unsigned mask = marked(rev);
 172
 173         if (!mask)
 174                 return 0;
 175         if (show_edges) {
 176                 struct parent *p = rev->parent;
 177                 while (p) {
 178                         if (mask != marked(p->parent))
 179                                 return 1;
 180                         p = p->next;
 181                 }
 182                 return 0;
 183         }
 184         if (mask & basemask)
 185                 return 0;
 186
 187         return 1;
 188 }
 189
 190 /*
 191  * Usage: rev-tree [--edges] [--cache <cache-file>] <commit-id> [<commit-id2>]
 192  *
 193  * The cache-file can be quite important for big trees. This is an
 194  * expensive operation if you have to walk the whole chain of
 195  * parents in a tree with a long revision history.
 196  */
 197 int main(int argc, char **argv)
 198 {
 199         int i;
 200         int nr = 0;
 201         unsigned char sha1[MAX_COMMITS][20];
 202
 203         /*
 204          * First - pick up all the revisions we can (both from
 205          * caches and from commit file chains).
 206          */
 207         for (i = 1; i < argc ; i++) {
 208                 char *arg = argv[i];
 209
 210                 if (!strcmp(arg, "--cache")) {
 211                         read_cache_file(argv[2]);
 212                         i++;
 213                         continue;
 214                 }
 215
 216                 if (!strcmp(arg, "--edges")) {
 217                         show_edges = 1;
 218                         continue;
 219                 }
 220
 221                 if (arg[0] == '^') {
 222                         arg++;
 223                         basemask |= 1<<nr;
 224                 }
 225                 if (nr >= MAX_COMMITS || get_sha1_hex(arg, sha1[nr]))
 226                         usage("rev-tree [--edges] [--cache <cache-file>] <commit-id> [<commit-id>]");
 227                 parse_commit(sha1[nr]);
 228                 nr++;
 229         }
 230
 231         /*
 232          * Now we have the maximal tree. Walk the different sha files back to the root.
 233          */
 234         for (i = 0; i < nr; i++)
 235                 mark_sha1_path(lookup_rev(sha1[i]), 1 << i);
 236
 237         /*
 238          * Now print out the results..
 239          */
 240         for (i = 0; i < nr_revs; i++) {
 241                 struct revision *rev = revs[i];
 242                 struct parent *p;
 243
 244                 if (!interesting(rev))
 245                         continue;
 246
 247                 printf("%s:%d", sha1_to_hex(rev->sha1), marked(rev));
 248                 p = rev->parent;
 249                 while (p) {
 250                         printf(" %s:%d", sha1_to_hex(p->parent->sha1), marked(p->parent));
 251                         p = p->next;
 252                 }
 253                 printf("\n");
 254         }
 255         return 0;
 256 }