[PATCH] rev-tree support for "in X but not in Y".
[git/git.git] / rev-tree.c
CommitLineData
84fe9720
LT
1#include "cache.h"
2
28258afe
LT
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
16static int show_edges = 0;
727ff277 17static int basemask = 0;
97d9c3cd
LT
18
19struct parent {
20 struct revision *parent;
21 struct parent *next;
22};
23
24struct revision {
25 unsigned int flags;
84fe9720 26 unsigned char sha1[20];
97d9c3cd 27 struct parent *parent;
84fe9720
LT
28};
29
97d9c3cd
LT
30static struct revision **revs;
31static int nr_revs, rev_allocs;
84fe9720 32
97d9c3cd 33static int find_rev(unsigned char *sha1)
84fe9720 34{
97d9c3cd 35 int first = 0, last = nr_revs;
84fe9720
LT
36
37 while (first < last) {
38 int next = (first + last) / 2;
97d9c3cd 39 struct revision *rev = revs[next];
84fe9720
LT
40 int cmp;
41
97d9c3cd
LT
42 cmp = memcmp(sha1, rev->sha1, 20);
43 if (!cmp)
44 return next;
84fe9720
LT
45 if (cmp < 0) {
46 last = next;
47 continue;
48 }
49 first = next+1;
50 }
51 return -first-1;
52}
53
97d9c3cd 54static struct revision *lookup_rev(unsigned char *sha1)
84fe9720 55{
97d9c3cd
LT
56 int pos = find_rev(sha1);
57 struct revision *n;
84fe9720 58
84fe9720 59 if (pos >= 0)
97d9c3cd
LT
60 return revs[pos];
61
84fe9720
LT
62 pos = -pos-1;
63
97d9c3cd
LT
64 if (rev_allocs == nr_revs) {
65 rev_allocs = alloc_nr(rev_allocs);
66 revs = realloc(revs, rev_allocs * sizeof(struct revision *));
84fe9720 67 }
97d9c3cd
LT
68 n = malloc(sizeof(struct revision));
69
70 n->flags = 0;
84fe9720 71 memcpy(n->sha1, sha1, 20);
97d9c3cd
LT
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;
84fe9720
LT
80}
81
97d9c3cd 82static int add_relationship(struct revision *rev, unsigned char *parent_sha)
84fe9720 83{
97d9c3cd
LT
84 struct revision *parent_rev = lookup_rev(parent_sha);
85 struct parent **pp = &rev->parent, *p;
84fe9720 86
97d9c3cd
LT
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;
84fe9720
LT
98}
99
100static int parse_commit(unsigned char *sha1)
101{
97d9c3cd
LT
102 struct revision *rev = lookup_rev(sha1);
103
104 if (!(rev->flags & SEEN)) {
84fe9720
LT
105 void *buffer;
106 unsigned long size;
107 char type[20];
108 unsigned char parent[20];
109
97d9c3cd 110 rev->flags |= SEEN;
84fe9720
LT
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)) {
97d9c3cd 116 add_relationship(rev, parent);
84fe9720
LT
117 parse_commit(parent);
118 buffer += 48; /* "parent " + "hex sha1" + "\n" */
119 }
120 }
121 return 0;
122}
123
124static void read_cache_file(const char *path)
125{
126 FILE *file = fopen(path, "r");
127 char line[100];
128
28258afe
LT
129 if (!file)
130 usage("bad revtree cache file (%s)", path);
131
84fe9720
LT
132 while (fgets(line, sizeof(line), file)) {
133 unsigned char sha1[20], parent[20];
28258afe
LT
134 struct revision *rev;
135
84fe9720
LT
136 if (get_sha1_hex(line, sha1) || get_sha1_hex(line + 41, parent))
137 usage("bad rev-tree cache file %s", path);
28258afe
LT
138 rev = lookup_rev(sha1);
139 rev->flags |= SEEN;
140 add_relationship(rev, parent);
84fe9720
LT
141 }
142 fclose(file);
143}
144
28258afe
LT
145static 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
84fe9720 160/*
28258afe
LT
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 */
169static 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 }
727ff277
DW
184 if (mask & basemask)
185 return 0;
186
28258afe
LT
187 return 1;
188}
189
190/*
191 * Usage: rev-tree [--edges] [--cache <cache-file>] <commit-id> [<commit-id2>]
84fe9720
LT
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 */
197int main(int argc, char **argv)
198{
199 int i;
28258afe
LT
200 int nr = 0;
201 unsigned char sha1[MAX_COMMITS][20];
84fe9720 202
28258afe
LT
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")) {
84fe9720 211 read_cache_file(argv[2]);
28258afe
LT
212 i++;
213 continue;
214 }
215
216 if (!strcmp(arg, "--edges")) {
217 show_edges = 1;
84fe9720
LT
218 continue;
219 }
28258afe 220
727ff277
DW
221 if (arg[0] == '^') {
222 arg++;
223 basemask |= 1<<nr;
224 }
28258afe
LT
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++;
84fe9720
LT
229 }
230
28258afe
LT
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 */
97d9c3cd
LT
240 for (i = 0; i < nr_revs; i++) {
241 struct revision *rev = revs[i];
242 struct parent *p;
243
28258afe
LT
244 if (!interesting(rev))
245 continue;
246
771364af 247 printf("%s:%d", sha1_to_hex(rev->sha1), marked(rev));
97d9c3cd
LT
248 p = rev->parent;
249 while (p) {
771364af 250 printf(" %s:%d", sha1_to_hex(p->parent->sha1), marked(p->parent));
97d9c3cd
LT
251 p = p->next;
252 }
253 printf("\n");
84fe9720
LT
254 }
255 return 0;
256}