init_buffer(): Kill buf pointer
[git/git.git] / builtin-rev-list.c
1 #include "cache.h"
2 #include "refs.h"
3 #include "tag.h"
4 #include "commit.h"
5 #include "tree.h"
6 #include "blob.h"
7 #include "tree-walk.h"
8 #include "diff.h"
9 #include "revision.h"
10 #include "list-objects.h"
11 #include "builtin.h"
12
13 /* bits #0-15 in revision.h */
14
15 #define COUNTED (1u<<16)
16
17 static const char rev_list_usage[] =
18 "git-rev-list [OPTION] <commit-id>... [ -- paths... ]\n"
19 " limiting output:\n"
20 " --max-count=nr\n"
21 " --max-age=epoch\n"
22 " --min-age=epoch\n"
23 " --sparse\n"
24 " --no-merges\n"
25 " --remove-empty\n"
26 " --all\n"
27 " --stdin\n"
28 " ordering output:\n"
29 " --topo-order\n"
30 " --date-order\n"
31 " formatting output:\n"
32 " --parents\n"
33 " --objects | --objects-edge\n"
34 " --unpacked\n"
35 " --header | --pretty\n"
36 " --abbrev=nr | --no-abbrev\n"
37 " --abbrev-commit\n"
38 " --left-right\n"
39 " special purpose:\n"
40 " --bisect\n"
41 " --bisect-vars"
42 ;
43
44 static struct rev_info revs;
45
46 static int bisect_list;
47 static int show_timestamp;
48 static int hdr_termination;
49 static const char *header_prefix;
50
51 static void show_commit(struct commit *commit)
52 {
53 if (show_timestamp)
54 printf("%lu ", commit->date);
55 if (header_prefix)
56 fputs(header_prefix, stdout);
57 if (commit->object.flags & BOUNDARY)
58 putchar('-');
59 else if (revs.left_right) {
60 if (commit->object.flags & SYMMETRIC_LEFT)
61 putchar('<');
62 else
63 putchar('>');
64 }
65 if (revs.abbrev_commit && revs.abbrev)
66 fputs(find_unique_abbrev(commit->object.sha1, revs.abbrev),
67 stdout);
68 else
69 fputs(sha1_to_hex(commit->object.sha1), stdout);
70 if (revs.parents) {
71 struct commit_list *parents = commit->parents;
72 while (parents) {
73 struct object *o = &(parents->item->object);
74 parents = parents->next;
75 if (o->flags & TMP_MARK)
76 continue;
77 printf(" %s", sha1_to_hex(o->sha1));
78 o->flags |= TMP_MARK;
79 }
80 /* TMP_MARK is a general purpose flag that can
81 * be used locally, but the user should clean
82 * things up after it is done with them.
83 */
84 for (parents = commit->parents;
85 parents;
86 parents = parents->next)
87 parents->item->object.flags &= ~TMP_MARK;
88 }
89 if (revs.commit_format == CMIT_FMT_ONELINE)
90 putchar(' ');
91 else
92 putchar('\n');
93
94 if (revs.verbose_header) {
95 static char pretty_header[16384];
96 pretty_print_commit(revs.commit_format, commit, ~0,
97 pretty_header, sizeof(pretty_header),
98 revs.abbrev, NULL, NULL, revs.relative_date);
99 printf("%s%c", pretty_header, hdr_termination);
100 }
101 fflush(stdout);
102 if (commit->parents) {
103 free_commit_list(commit->parents);
104 commit->parents = NULL;
105 }
106 free(commit->buffer);
107 commit->buffer = NULL;
108 }
109
110 static void show_object(struct object_array_entry *p)
111 {
112 /* An object with name "foo\n0000000..." can be used to
113 * confuse downstream git-pack-objects very badly.
114 */
115 const char *ep = strchr(p->name, '\n');
116
117 if (p->item->type == OBJ_BLOB && !has_sha1_file(p->item->sha1))
118 die("missing blob object '%s'", sha1_to_hex(p->item->sha1));
119
120 if (ep) {
121 printf("%s %.*s\n", sha1_to_hex(p->item->sha1),
122 (int) (ep - p->name),
123 p->name);
124 }
125 else
126 printf("%s %s\n", sha1_to_hex(p->item->sha1), p->name);
127 }
128
129 static void show_edge(struct commit *commit)
130 {
131 printf("-%s\n", sha1_to_hex(commit->object.sha1));
132 }
133
134 /*
135 * This is a truly stupid algorithm, but it's only
136 * used for bisection, and we just don't care enough.
137 *
138 * We care just barely enough to avoid recursing for
139 * non-merge entries.
140 */
141 static int count_distance(struct commit_list *entry)
142 {
143 int nr = 0;
144
145 while (entry) {
146 struct commit *commit = entry->item;
147 struct commit_list *p;
148
149 if (commit->object.flags & (UNINTERESTING | COUNTED))
150 break;
151 if (!revs.prune_fn || (commit->object.flags & TREECHANGE))
152 nr++;
153 commit->object.flags |= COUNTED;
154 p = commit->parents;
155 entry = p;
156 if (p) {
157 p = p->next;
158 while (p) {
159 nr += count_distance(p);
160 p = p->next;
161 }
162 }
163 }
164
165 return nr;
166 }
167
168 static void clear_distance(struct commit_list *list)
169 {
170 while (list) {
171 struct commit *commit = list->item;
172 commit->object.flags &= ~COUNTED;
173 list = list->next;
174 }
175 }
176
177 #define DEBUG_BISECT 0
178
179 static inline int weight(struct commit_list *elem)
180 {
181 return *((int*)(elem->item->util));
182 }
183
184 static inline void weight_set(struct commit_list *elem, int weight)
185 {
186 *((int*)(elem->item->util)) = weight;
187 }
188
189 static int count_interesting_parents(struct commit *commit)
190 {
191 struct commit_list *p;
192 int count;
193
194 for (count = 0, p = commit->parents; p; p = p->next) {
195 if (p->item->object.flags & UNINTERESTING)
196 continue;
197 count++;
198 }
199 return count;
200 }
201
202 static inline int halfway(struct commit_list *p, int distance, int nr)
203 {
204 /*
205 * Don't short-cut something we are not going to return!
206 */
207 if (revs.prune_fn && !(p->item->object.flags & TREECHANGE))
208 return 0;
209 if (DEBUG_BISECT)
210 return 0;
211 /*
212 * 2 and 3 are halfway of 5.
213 * 3 is halfway of 6 but 2 and 4 are not.
214 */
215 distance *= 2;
216 switch (distance - nr) {
217 case -1: case 0: case 1:
218 return 1;
219 default:
220 return 0;
221 }
222 }
223
224 #if !DEBUG_BISECT
225 #define show_list(a,b,c,d) do { ; } while (0)
226 #else
227 static void show_list(const char *debug, int counted, int nr,
228 struct commit_list *list)
229 {
230 struct commit_list *p;
231
232 fprintf(stderr, "%s (%d/%d)\n", debug, counted, nr);
233
234 for (p = list; p; p = p->next) {
235 struct commit_list *pp;
236 struct commit *commit = p->item;
237 unsigned flags = commit->object.flags;
238 enum object_type type;
239 unsigned long size;
240 char *buf = read_sha1_file(commit->object.sha1, &type, &size);
241 char *ep, *sp;
242
243 fprintf(stderr, "%c%c%c ",
244 (flags & TREECHANGE) ? 'T' : ' ',
245 (flags & UNINTERESTING) ? 'U' : ' ',
246 (flags & COUNTED) ? 'C' : ' ');
247 if (commit->util)
248 fprintf(stderr, "%3d", weight(p));
249 else
250 fprintf(stderr, "---");
251 fprintf(stderr, " %.*s", 8, sha1_to_hex(commit->object.sha1));
252 for (pp = commit->parents; pp; pp = pp->next)
253 fprintf(stderr, " %.*s", 8,
254 sha1_to_hex(pp->item->object.sha1));
255
256 sp = strstr(buf, "\n\n");
257 if (sp) {
258 sp += 2;
259 for (ep = sp; *ep && *ep != '\n'; ep++)
260 ;
261 fprintf(stderr, " %.*s", (int)(ep - sp), sp);
262 }
263 fprintf(stderr, "\n");
264 }
265 }
266 #endif /* DEBUG_BISECT */
267
268 /*
269 * zero or positive weight is the number of interesting commits it can
270 * reach, including itself. Especially, weight = 0 means it does not
271 * reach any tree-changing commits (e.g. just above uninteresting one
272 * but traversal is with pathspec).
273 *
274 * weight = -1 means it has one parent and its distance is yet to
275 * be computed.
276 *
277 * weight = -2 means it has more than one parent and its distance is
278 * unknown. After running count_distance() first, they will get zero
279 * or positive distance.
280 */
281
282 static struct commit_list *find_bisection(struct commit_list *list,
283 int *reaches, int *all)
284 {
285 int n, nr, on_list, counted, distance;
286 struct commit_list *p, *best, *next, *last;
287 int *weights;
288
289 show_list("bisection 2 entry", 0, 0, list);
290
291 /*
292 * Count the number of total and tree-changing items on the
293 * list, while reversing the list.
294 */
295 for (nr = on_list = 0, last = NULL, p = list;
296 p;
297 p = next) {
298 unsigned flags = p->item->object.flags;
299
300 next = p->next;
301 if (flags & UNINTERESTING)
302 continue;
303 p->next = last;
304 last = p;
305 if (!revs.prune_fn || (flags & TREECHANGE))
306 nr++;
307 on_list++;
308 }
309 list = last;
310 show_list("bisection 2 sorted", 0, nr, list);
311
312 *all = nr;
313 weights = xcalloc(on_list, sizeof(int*));
314 counted = 0;
315
316 for (n = 0, p = list; p; p = p->next) {
317 struct commit *commit = p->item;
318 unsigned flags = commit->object.flags;
319
320 p->item->util = &weights[n++];
321 switch (count_interesting_parents(commit)) {
322 case 0:
323 if (!revs.prune_fn || (flags & TREECHANGE)) {
324 weight_set(p, 1);
325 counted++;
326 show_list("bisection 2 count one",
327 counted, nr, list);
328 }
329 /*
330 * otherwise, it is known not to reach any
331 * tree-changing commit and gets weight 0.
332 */
333 break;
334 case 1:
335 weight_set(p, -1);
336 break;
337 default:
338 weight_set(p, -2);
339 break;
340 }
341 }
342
343 show_list("bisection 2 initialize", counted, nr, list);
344
345 /*
346 * If you have only one parent in the resulting set
347 * then you can reach one commit more than that parent
348 * can reach. So we do not have to run the expensive
349 * count_distance() for single strand of pearls.
350 *
351 * However, if you have more than one parents, you cannot
352 * just add their distance and one for yourself, since
353 * they usually reach the same ancestor and you would
354 * end up counting them twice that way.
355 *
356 * So we will first count distance of merges the usual
357 * way, and then fill the blanks using cheaper algorithm.
358 */
359 for (p = list; p; p = p->next) {
360 if (p->item->object.flags & UNINTERESTING)
361 continue;
362 n = weight(p);
363 if (n != -2)
364 continue;
365 distance = count_distance(p);
366 clear_distance(list);
367 weight_set(p, distance);
368
369 /* Does it happen to be at exactly half-way? */
370 if (halfway(p, distance, nr)) {
371 p->next = NULL;
372 *reaches = distance;
373 free(weights);
374 return p;
375 }
376 counted++;
377 }
378
379 show_list("bisection 2 count_distance", counted, nr, list);
380
381 while (counted < nr) {
382 for (p = list; p; p = p->next) {
383 struct commit_list *q;
384 unsigned flags = p->item->object.flags;
385
386 if (0 <= weight(p))
387 continue;
388 for (q = p->item->parents; q; q = q->next) {
389 if (q->item->object.flags & UNINTERESTING)
390 continue;
391 if (0 <= weight(q))
392 break;
393 }
394 if (!q)
395 continue;
396
397 /*
398 * weight for p is unknown but q is known.
399 * add one for p itself if p is to be counted,
400 * otherwise inherit it from q directly.
401 */
402 if (!revs.prune_fn || (flags & TREECHANGE)) {
403 weight_set(p, weight(q)+1);
404 counted++;
405 show_list("bisection 2 count one",
406 counted, nr, list);
407 }
408 else
409 weight_set(p, weight(q));
410
411 /* Does it happen to be at exactly half-way? */
412 distance = weight(p);
413 if (halfway(p, distance, nr)) {
414 p->next = NULL;
415 *reaches = distance;
416 free(weights);
417 return p;
418 }
419 }
420 }
421
422 show_list("bisection 2 counted all", counted, nr, list);
423
424 /* Then find the best one */
425 counted = -1;
426 best = list;
427 for (p = list; p; p = p->next) {
428 unsigned flags = p->item->object.flags;
429
430 if (revs.prune_fn && !(flags & TREECHANGE))
431 continue;
432 distance = weight(p);
433 if (nr - distance < distance)
434 distance = nr - distance;
435 if (distance > counted) {
436 best = p;
437 counted = distance;
438 *reaches = weight(p);
439 }
440 }
441 if (best)
442 best->next = NULL;
443 free(weights);
444 return best;
445 }
446
447 static void read_revisions_from_stdin(struct rev_info *revs)
448 {
449 char line[1000];
450
451 while (fgets(line, sizeof(line), stdin) != NULL) {
452 int len = strlen(line);
453 if (line[len - 1] == '\n')
454 line[--len] = 0;
455 if (!len)
456 break;
457 if (line[0] == '-')
458 die("options not supported in --stdin mode");
459 if (handle_revision_arg(line, revs, 0, 1))
460 die("bad revision '%s'", line);
461 }
462 }
463
464 int cmd_rev_list(int argc, const char **argv, const char *prefix)
465 {
466 struct commit_list *list;
467 int i;
468 int read_from_stdin = 0;
469 int bisect_show_vars = 0;
470
471 git_config(git_default_config);
472 init_revisions(&revs, prefix);
473 revs.abbrev = 0;
474 revs.commit_format = CMIT_FMT_UNSPECIFIED;
475 argc = setup_revisions(argc, argv, &revs, NULL);
476
477 for (i = 1 ; i < argc; i++) {
478 const char *arg = argv[i];
479
480 if (!strcmp(arg, "--header")) {
481 revs.verbose_header = 1;
482 continue;
483 }
484 if (!strcmp(arg, "--timestamp")) {
485 show_timestamp = 1;
486 continue;
487 }
488 if (!strcmp(arg, "--bisect")) {
489 bisect_list = 1;
490 continue;
491 }
492 if (!strcmp(arg, "--bisect-vars")) {
493 bisect_list = 1;
494 bisect_show_vars = 1;
495 continue;
496 }
497 if (!strcmp(arg, "--stdin")) {
498 if (read_from_stdin++)
499 die("--stdin given twice?");
500 read_revisions_from_stdin(&revs);
501 continue;
502 }
503 usage(rev_list_usage);
504
505 }
506 if (revs.commit_format != CMIT_FMT_UNSPECIFIED) {
507 /* The command line has a --pretty */
508 hdr_termination = '\n';
509 if (revs.commit_format == CMIT_FMT_ONELINE)
510 header_prefix = "";
511 else
512 header_prefix = "commit ";
513 }
514 else if (revs.verbose_header)
515 /* Only --header was specified */
516 revs.commit_format = CMIT_FMT_RAW;
517
518 list = revs.commits;
519
520 if ((!list &&
521 (!(revs.tag_objects||revs.tree_objects||revs.blob_objects) &&
522 !revs.pending.nr)) ||
523 revs.diff)
524 usage(rev_list_usage);
525
526 save_commit_buffer = revs.verbose_header || revs.grep_filter;
527 track_object_refs = 0;
528 if (bisect_list)
529 revs.limited = 1;
530
531 prepare_revision_walk(&revs);
532 if (revs.tree_objects)
533 mark_edges_uninteresting(revs.commits, &revs, show_edge);
534
535 if (bisect_list) {
536 int reaches = reaches, all = all;
537
538 revs.commits = find_bisection(revs.commits, &reaches, &all);
539 if (bisect_show_vars) {
540 int cnt;
541 if (!revs.commits)
542 return 1;
543 /*
544 * revs.commits can reach "reaches" commits among
545 * "all" commits. If it is good, then there are
546 * (all-reaches) commits left to be bisected.
547 * On the other hand, if it is bad, then the set
548 * to bisect is "reaches".
549 * A bisect set of size N has (N-1) commits further
550 * to test, as we already know one bad one.
551 */
552 cnt = all-reaches;
553 if (cnt < reaches)
554 cnt = reaches;
555 printf("bisect_rev=%s\n"
556 "bisect_nr=%d\n"
557 "bisect_good=%d\n"
558 "bisect_bad=%d\n"
559 "bisect_all=%d\n",
560 sha1_to_hex(revs.commits->item->object.sha1),
561 cnt - 1,
562 all - reaches - 1,
563 reaches - 1,
564 all);
565 return 0;
566 }
567 }
568
569 traverse_commit_list(&revs, show_commit, show_object);
570
571 return 0;
572 }