Make "rev-tree" capable of showing the difference in reachability between two
[git/git.git] / 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 }