rev-tree.c

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