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