1 #include "cache.h" 2 #include "object-store.h" 3 #include "tag.h" 4 #include "blob.h" 5 #include "tree.h" 6 #include "commit.h" 7 #include "diff.h" 8 #include "diff-merges.h" 9 #include "refs.h" 10 #include "revision.h" 11 #include "repository.h" 12 #include "graph.h" 13 #include "grep.h" 14 #include "reflog-walk.h" 15 #include "patch-ids.h" 16 #include "decorate.h" 17 #include "log-tree.h" 18 #include "string-list.h" 19 #include "line-log.h" 20 #include "mailmap.h" 21 #include "commit-slab.h" 22 #include "dir.h" 23 #include "cache-tree.h" 24 #include "bisect.h" 25 #include "packfile.h" 26 #include "worktree.h" 27 #include "strvec.h" 28 #include "commit-reach.h" 29 #include "commit-graph.h" 30 #include "prio-queue.h" 31 #include "hashmap.h" 32 #include "utf8.h" 33 #include "bloom.h" 34 #include "json-writer.h" 35 36 volatile show_early_output_fn_t show_early_output; 37 38 static const char *term_bad; 39 static const char *term_good; 40 41 implement_shared_commit_slab(revision_sources, char *); 42 43 static inline int want_ancestry(const struct rev_info *revs); 44 45 void show_object_with_name(FILE *out, struct object *obj, const char *name) 46 { 47 const char *p; 48 49 fprintf(out, "%s ", oid_to_hex(&obj->oid)); 50 for (p = name; *p && *p != '\n'; p++) 51 fputc(*p, out); 52 fputc('\n', out); 53 } 54 55 static void mark_blob_uninteresting(struct blob *blob) 56 { 57 if (!blob) 58 return; 59 if (blob->object.flags & UNINTERESTING) 60 return; 61 blob->object.flags |= UNINTERESTING; 62 } 63 64 static void mark_tree_contents_uninteresting(struct repository *r, 65 struct tree *tree) 66 { 67 struct tree_desc desc; 68 struct name_entry entry; 69 70 if (parse_tree_gently(tree, 1) < 0) 71 return; 72 73 init_tree_desc(&desc, tree->buffer, tree->size); 74 while (tree_entry(&desc, &entry)) { 75 switch (object_type(entry.mode)) { 76 case OBJ_TREE: 77 mark_tree_uninteresting(r, lookup_tree(r, &entry.oid)); 78 break; 79 case OBJ_BLOB: 80 mark_blob_uninteresting(lookup_blob(r, &entry.oid)); 81 break; 82 default: 83 /* Subproject commit - not in this repository */ 84 break; 85 } 86 } 87 88 /* 89 * We don't care about the tree any more 90 * after it has been marked uninteresting. 91 */ 92 free_tree_buffer(tree); 93 } 94 95 void mark_tree_uninteresting(struct repository *r, struct tree *tree) 96 { 97 struct object *obj; 98 99 if (!tree) 100 return; 101 102 obj = &tree->object; 103 if (obj->flags & UNINTERESTING) 104 return; 105 obj->flags |= UNINTERESTING; 106 mark_tree_contents_uninteresting(r, tree); 107 } 108 109 struct path_and_oids_entry { 110 struct hashmap_entry ent; 111 char *path; 112 struct oidset trees; 113 }; 114 115 static int path_and_oids_cmp(const void *hashmap_cmp_fn_data, 116 const struct hashmap_entry *eptr, 117 const struct hashmap_entry *entry_or_key, 118 const void *keydata) 119 { 120 const struct path_and_oids_entry *e1, *e2; 121 122 e1 = container_of(eptr, const struct path_and_oids_entry, ent); 123 e2 = container_of(entry_or_key, const struct path_and_oids_entry, ent); 124 125 return strcmp(e1->path, e2->path); 126 } 127 128 static void paths_and_oids_clear(struct hashmap *map) 129 { 130 struct hashmap_iter iter; 131 struct path_and_oids_entry *entry; 132 133 hashmap_for_each_entry(map, &iter, entry, ent /* member name */) { 134 oidset_clear(&entry->trees); 135 free(entry->path); 136 } 137 138 hashmap_clear_and_free(map, struct path_and_oids_entry, ent); 139 } 140 141 static void paths_and_oids_insert(struct hashmap *map, 142 const char *path, 143 const struct object_id *oid) 144 { 145 int hash = strhash(path); 146 struct path_and_oids_entry key; 147 struct path_and_oids_entry *entry; 148 149 hashmap_entry_init(&key.ent, hash); 150 151 /* use a shallow copy for the lookup */ 152 key.path = (char *)path; 153 oidset_init(&key.trees, 0); 154 155 entry = hashmap_get_entry(map, &key, ent, NULL); 156 if (!entry) { 157 CALLOC_ARRAY(entry, 1); 158 hashmap_entry_init(&entry->ent, hash); 159 entry->path = xstrdup(key.path); 160 oidset_init(&entry->trees, 16); 161 hashmap_put(map, &entry->ent); 162 } 163 164 oidset_insert(&entry->trees, oid); 165 } 166 167 static void add_children_by_path(struct repository *r, 168 struct tree *tree, 169 struct hashmap *map) 170 { 171 struct tree_desc desc; 172 struct name_entry entry; 173 174 if (!tree) 175 return; 176 177 if (parse_tree_gently(tree, 1) < 0) 178 return; 179 180 init_tree_desc(&desc, tree->buffer, tree->size); 181 while (tree_entry(&desc, &entry)) { 182 switch (object_type(entry.mode)) { 183 case OBJ_TREE: 184 paths_and_oids_insert(map, entry.path, &entry.oid); 185 186 if (tree->object.flags & UNINTERESTING) { 187 struct tree *child = lookup_tree(r, &entry.oid); 188 if (child) 189 child->object.flags |= UNINTERESTING; 190 } 191 break; 192 case OBJ_BLOB: 193 if (tree->object.flags & UNINTERESTING) { 194 struct blob *child = lookup_blob(r, &entry.oid); 195 if (child) 196 child->object.flags |= UNINTERESTING; 197 } 198 break; 199 default: 200 /* Subproject commit - not in this repository */ 201 break; 202 } 203 } 204 205 free_tree_buffer(tree); 206 } 207 208 void mark_trees_uninteresting_sparse(struct repository *r, 209 struct oidset *trees) 210 { 211 unsigned has_interesting = 0, has_uninteresting = 0; 212 struct hashmap map = HASHMAP_INIT(path_and_oids_cmp, NULL); 213 struct hashmap_iter map_iter; 214 struct path_and_oids_entry *entry; 215 struct object_id *oid; 216 struct oidset_iter iter; 217 218 oidset_iter_init(trees, &iter); 219 while ((!has_interesting || !has_uninteresting) && 220 (oid = oidset_iter_next(&iter))) { 221 struct tree *tree = lookup_tree(r, oid); 222 223 if (!tree) 224 continue; 225 226 if (tree->object.flags & UNINTERESTING) 227 has_uninteresting = 1; 228 else 229 has_interesting = 1; 230 } 231 232 /* Do not walk unless we have both types of trees. */ 233 if (!has_uninteresting || !has_interesting) 234 return; 235 236 oidset_iter_init(trees, &iter); 237 while ((oid = oidset_iter_next(&iter))) { 238 struct tree *tree = lookup_tree(r, oid); 239 add_children_by_path(r, tree, &map); 240 } 241 242 hashmap_for_each_entry(&map, &map_iter, entry, ent /* member name */) 243 mark_trees_uninteresting_sparse(r, &entry->trees); 244 245 paths_and_oids_clear(&map); 246 } 247 248 struct commit_stack { 249 struct commit **items; 250 size_t nr, alloc; 251 }; 252 #define COMMIT_STACK_INIT { 0 } 253 254 static void commit_stack_push(struct commit_stack *stack, struct commit *commit) 255 { 256 ALLOC_GROW(stack->items, stack->nr + 1, stack->alloc); 257 stack->items[stack->nr++] = commit; 258 } 259 260 static struct commit *commit_stack_pop(struct commit_stack *stack) 261 { 262 return stack->nr ? stack->items[--stack->nr] : NULL; 263 } 264 265 static void commit_stack_clear(struct commit_stack *stack) 266 { 267 FREE_AND_NULL(stack->items); 268 stack->nr = stack->alloc = 0; 269 } 270 271 static void mark_one_parent_uninteresting(struct commit *commit, 272 struct commit_stack *pending) 273 { 274 struct commit_list *l; 275 276 if (commit->object.flags & UNINTERESTING) 277 return; 278 commit->object.flags |= UNINTERESTING; 279 280 /* 281 * Normally we haven't parsed the parent 282 * yet, so we won't have a parent of a parent 283 * here. However, it may turn out that we've 284 * reached this commit some other way (where it 285 * wasn't uninteresting), in which case we need 286 * to mark its parents recursively too.. 287 */ 288 for (l = commit->parents; l; l = l->next) 289 commit_stack_push(pending, l->item); 290 } 291 292 void mark_parents_uninteresting(struct commit *commit) 293 { 294 struct commit_stack pending = COMMIT_STACK_INIT; 295 struct commit_list *l; 296 297 for (l = commit->parents; l; l = l->next) 298 mark_one_parent_uninteresting(l->item, &pending); 299 300 while (pending.nr > 0) 301 mark_one_parent_uninteresting(commit_stack_pop(&pending), 302 &pending); 303 304 commit_stack_clear(&pending); 305 } 306 307 static void add_pending_object_with_path(struct rev_info *revs, 308 struct object *obj, 309 const char *name, unsigned mode, 310 const char *path) 311 { 312 struct interpret_branch_name_options options = { 0 }; 313 if (!obj) 314 return; 315 if (revs->no_walk && (obj->flags & UNINTERESTING)) 316 revs->no_walk = 0; 317 if (revs->reflog_info && obj->type == OBJ_COMMIT) { 318 struct strbuf buf = STRBUF_INIT; 319 size_t namelen = strlen(name); 320 int len = interpret_branch_name(name, namelen, &buf, &options); 321 322 if (0 < len && len < namelen && buf.len) 323 strbuf_addstr(&buf, name + len); 324 add_reflog_for_walk(revs->reflog_info, 325 (struct commit *)obj, 326 buf.buf[0] ? buf.buf: name); 327 strbuf_release(&buf); 328 return; /* do not add the commit itself */ 329 } 330 add_object_array_with_path(obj, name, &revs->pending, mode, path); 331 } 332 333 static void add_pending_object_with_mode(struct rev_info *revs, 334 struct object *obj, 335 const char *name, unsigned mode) 336 { 337 add_pending_object_with_path(revs, obj, name, mode, NULL); 338 } 339 340 void add_pending_object(struct rev_info *revs, 341 struct object *obj, const char *name) 342 { 343 add_pending_object_with_mode(revs, obj, name, S_IFINVALID); 344 } 345 346 void add_head_to_pending(struct rev_info *revs) 347 { 348 struct object_id oid; 349 struct object *obj; 350 if (get_oid("HEAD", &oid)) 351 return; 352 obj = parse_object(revs->repo, &oid); 353 if (!obj) 354 return; 355 add_pending_object(revs, obj, "HEAD"); 356 } 357 358 static struct object *get_reference(struct rev_info *revs, const char *name, 359 const struct object_id *oid, 360 unsigned int flags) 361 { 362 struct object *object; 363 struct commit *commit; 364 365 /* 366 * If the repository has commit graphs, we try to opportunistically 367 * look up the object ID in those graphs. Like this, we can avoid 368 * parsing commit data from disk. 369 */ 370 commit = lookup_commit_in_graph(revs->repo, oid); 371 if (commit) 372 object = &commit->object; 373 else 374 object = parse_object(revs->repo, oid); 375 376 if (!object) { 377 if (revs->ignore_missing) 378 return object; 379 if (revs->exclude_promisor_objects && is_promisor_object(oid)) 380 return NULL; 381 die("bad object %s", name); 382 } 383 object->flags |= flags; 384 return object; 385 } 386 387 void add_pending_oid(struct rev_info *revs, const char *name, 388 const struct object_id *oid, unsigned int flags) 389 { 390 struct object *object = get_reference(revs, name, oid, flags); 391 add_pending_object(revs, object, name); 392 } 393 394 static struct commit *handle_commit(struct rev_info *revs, 395 struct object_array_entry *entry) 396 { 397 struct object *object = entry->item; 398 const char *name = entry->name; 399 const char *path = entry->path; 400 unsigned int mode = entry->mode; 401 unsigned long flags = object->flags; 402 403 /* 404 * Tag object? Look what it points to.. 405 */ 406 while (object->type == OBJ_TAG) { 407 struct tag *tag = (struct tag *) object; 408 if (revs->tag_objects && !(flags & UNINTERESTING)) 409 add_pending_object(revs, object, tag->tag); 410 object = parse_object(revs->repo, get_tagged_oid(tag)); 411 if (!object) { 412 if (revs->ignore_missing_links || (flags & UNINTERESTING)) 413 return NULL; 414 if (revs->exclude_promisor_objects && 415 is_promisor_object(&tag->tagged->oid)) 416 return NULL; 417 die("bad object %s", oid_to_hex(&tag->tagged->oid)); 418 } 419 object->flags |= flags; 420 /* 421 * We'll handle the tagged object by looping or dropping 422 * through to the non-tag handlers below. Do not 423 * propagate path data from the tag's pending entry. 424 */ 425 path = NULL; 426 mode = 0; 427 } 428 429 /* 430 * Commit object? Just return it, we'll do all the complex 431 * reachability crud. 432 */ 433 if (object->type == OBJ_COMMIT) { 434 struct commit *commit = (struct commit *)object; 435 436 if (repo_parse_commit(revs->repo, commit) < 0) 437 die("unable to parse commit %s", name); 438 if (flags & UNINTERESTING) { 439 mark_parents_uninteresting(commit); 440 441 if (!revs->topo_order || !generation_numbers_enabled(the_repository)) 442 revs->limited = 1; 443 } 444 if (revs->sources) { 445 char **slot = revision_sources_at(revs->sources, commit); 446 447 if (!*slot) 448 *slot = xstrdup(name); 449 } 450 return commit; 451 } 452 453 /* 454 * Tree object? Either mark it uninteresting, or add it 455 * to the list of objects to look at later.. 456 */ 457 if (object->type == OBJ_TREE) { 458 struct tree *tree = (struct tree *)object; 459 if (!revs->tree_objects) 460 return NULL; 461 if (flags & UNINTERESTING) { 462 mark_tree_contents_uninteresting(revs->repo, tree); 463 return NULL; 464 } 465 add_pending_object_with_path(revs, object, name, mode, path); 466 return NULL; 467 } 468 469 /* 470 * Blob object? You know the drill by now.. 471 */ 472 if (object->type == OBJ_BLOB) { 473 if (!revs->blob_objects) 474 return NULL; 475 if (flags & UNINTERESTING) 476 return NULL; 477 add_pending_object_with_path(revs, object, name, mode, path); 478 return NULL; 479 } 480 die("%s is unknown object", name); 481 } 482 483 static int everybody_uninteresting(struct commit_list *orig, 484 struct commit **interesting_cache) 485 { 486 struct commit_list *list = orig; 487 488 if (*interesting_cache) { 489 struct commit *commit = *interesting_cache; 490 if (!(commit->object.flags & UNINTERESTING)) 491 return 0; 492 } 493 494 while (list) { 495 struct commit *commit = list->item; 496 list = list->next; 497 if (commit->object.flags & UNINTERESTING) 498 continue; 499 500 *interesting_cache = commit; 501 return 0; 502 } 503 return 1; 504 } 505 506 /* 507 * A definition of "relevant" commit that we can use to simplify limited graphs 508 * by eliminating side branches. 509 * 510 * A "relevant" commit is one that is !UNINTERESTING (ie we are including it 511 * in our list), or that is a specified BOTTOM commit. Then after computing 512 * a limited list, during processing we can generally ignore boundary merges 513 * coming from outside the graph, (ie from irrelevant parents), and treat 514 * those merges as if they were single-parent. TREESAME is defined to consider 515 * only relevant parents, if any. If we are TREESAME to our on-graph parents, 516 * we don't care if we were !TREESAME to non-graph parents. 517 * 518 * Treating bottom commits as relevant ensures that a limited graph's 519 * connection to the actual bottom commit is not viewed as a side branch, but 520 * treated as part of the graph. For example: 521 * 522 * ....Z...A---X---o---o---B 523 * . / 524 * W---Y 525 * 526 * When computing "A..B", the A-X connection is at least as important as 527 * Y-X, despite A being flagged UNINTERESTING. 528 * 529 * And when computing --ancestry-path "A..B", the A-X connection is more 530 * important than Y-X, despite both A and Y being flagged UNINTERESTING. 531 */ 532 static inline int relevant_commit(struct commit *commit) 533 { 534 return (commit->object.flags & (UNINTERESTING | BOTTOM)) != UNINTERESTING; 535 } 536 537 /* 538 * Return a single relevant commit from a parent list. If we are a TREESAME 539 * commit, and this selects one of our parents, then we can safely simplify to 540 * that parent. 541 */ 542 static struct commit *one_relevant_parent(const struct rev_info *revs, 543 struct commit_list *orig) 544 { 545 struct commit_list *list = orig; 546 struct commit *relevant = NULL; 547 548 if (!orig) 549 return NULL; 550 551 /* 552 * For 1-parent commits, or if first-parent-only, then return that 553 * first parent (even if not "relevant" by the above definition). 554 * TREESAME will have been set purely on that parent. 555 */ 556 if (revs->first_parent_only || !orig->next) 557 return orig->item; 558 559 /* 560 * For multi-parent commits, identify a sole relevant parent, if any. 561 * If we have only one relevant parent, then TREESAME will be set purely 562 * with regard to that parent, and we can simplify accordingly. 563 * 564 * If we have more than one relevant parent, or no relevant parents 565 * (and multiple irrelevant ones), then we can't select a parent here 566 * and return NULL. 567 */ 568 while (list) { 569 struct commit *commit = list->item; 570 list = list->next; 571 if (relevant_commit(commit)) { 572 if (relevant) 573 return NULL; 574 relevant = commit; 575 } 576 } 577 return relevant; 578 } 579 580 /* 581 * The goal is to get REV_TREE_NEW as the result only if the 582 * diff consists of all '+' (and no other changes), REV_TREE_OLD 583 * if the whole diff is removal of old data, and otherwise 584 * REV_TREE_DIFFERENT (of course if the trees are the same we 585 * want REV_TREE_SAME). 586 * 587 * The only time we care about the distinction is when 588 * remove_empty_trees is in effect, in which case we care only about 589 * whether the whole change is REV_TREE_NEW, or if there's another type 590 * of change. Which means we can stop the diff early in either of these 591 * cases: 592 * 593 * 1. We're not using remove_empty_trees at all. 594 * 595 * 2. We saw anything except REV_TREE_NEW. 596 */ 597 static int tree_difference = REV_TREE_SAME; 598 599 static void file_add_remove(struct diff_options *options, 600 int addremove, unsigned mode, 601 const struct object_id *oid, 602 int oid_valid, 603 const char *fullpath, unsigned dirty_submodule) 604 { 605 int diff = addremove == '+' ? REV_TREE_NEW : REV_TREE_OLD; 606 struct rev_info *revs = options->change_fn_data; 607 608 tree_difference |= diff; 609 if (!revs->remove_empty_trees || tree_difference != REV_TREE_NEW) 610 options->flags.has_changes = 1; 611 } 612 613 static void file_change(struct diff_options *options, 614 unsigned old_mode, unsigned new_mode, 615 const struct object_id *old_oid, 616 const struct object_id *new_oid, 617 int old_oid_valid, int new_oid_valid, 618 const char *fullpath, 619 unsigned old_dirty_submodule, unsigned new_dirty_submodule) 620 { 621 tree_difference = REV_TREE_DIFFERENT; 622 options->flags.has_changes = 1; 623 } 624 625 static int bloom_filter_atexit_registered; 626 static unsigned int count_bloom_filter_maybe; 627 static unsigned int count_bloom_filter_definitely_not; 628 static unsigned int count_bloom_filter_false_positive; 629 static unsigned int count_bloom_filter_not_present; 630 631 static void trace2_bloom_filter_statistics_atexit(void) 632 { 633 struct json_writer jw = JSON_WRITER_INIT; 634 635 jw_object_begin(&jw, 0); 636 jw_object_intmax(&jw, "filter_not_present", count_bloom_filter_not_present); 637 jw_object_intmax(&jw, "maybe", count_bloom_filter_maybe); 638 jw_object_intmax(&jw, "definitely_not", count_bloom_filter_definitely_not); 639 jw_object_intmax(&jw, "false_positive", count_bloom_filter_false_positive); 640 jw_end(&jw); 641 642 trace2_data_json("bloom", the_repository, "statistics", &jw); 643 644 jw_release(&jw); 645 } 646 647 static int forbid_bloom_filters(struct pathspec *spec) 648 { 649 if (spec->has_wildcard) 650 return 1; 651 if (spec->nr > 1) 652 return 1; 653 if (spec->magic & ~PATHSPEC_LITERAL) 654 return 1; 655 if (spec->nr && (spec->items[0].magic & ~PATHSPEC_LITERAL)) 656 return 1; 657 658 return 0; 659 } 660 661 static void prepare_to_use_bloom_filter(struct rev_info *revs) 662 { 663 struct pathspec_item *pi; 664 char *path_alloc = NULL; 665 const char *path, *p; 666 size_t len; 667 int path_component_nr = 1; 668 669 if (!revs->commits) 670 return; 671 672 if (forbid_bloom_filters(&revs->prune_data)) 673 return; 674 675 repo_parse_commit(revs->repo, revs->commits->item); 676 677 revs->bloom_filter_settings = get_bloom_filter_settings(revs->repo); 678 if (!revs->bloom_filter_settings) 679 return; 680 681 if (!revs->pruning.pathspec.nr) 682 return; 683 684 pi = &revs->pruning.pathspec.items[0]; 685 686 /* remove single trailing slash from path, if needed */ 687 if (pi->len > 0 && pi->match[pi->len - 1] == '/') { 688 path_alloc = xmemdupz(pi->match, pi->len - 1); 689 path = path_alloc; 690 } else 691 path = pi->match; 692 693 len = strlen(path); 694 if (!len) { 695 revs->bloom_filter_settings = NULL; 696 free(path_alloc); 697 return; 698 } 699 700 p = path; 701 while (*p) { 702 /* 703 * At this point, the path is normalized to use Unix-style 704 * path separators. This is required due to how the 705 * changed-path Bloom filters store the paths. 706 */ 707 if (*p == '/') 708 path_component_nr++; 709 p++; 710 } 711 712 revs->bloom_keys_nr = path_component_nr; 713 ALLOC_ARRAY(revs->bloom_keys, revs->bloom_keys_nr); 714 715 fill_bloom_key(path, len, &revs->bloom_keys[0], 716 revs->bloom_filter_settings); 717 path_component_nr = 1; 718 719 p = path + len - 1; 720 while (p > path) { 721 if (*p == '/') 722 fill_bloom_key(path, p - path, 723 &revs->bloom_keys[path_component_nr++], 724 revs->bloom_filter_settings); 725 p--; 726 } 727 728 if (trace2_is_enabled() && !bloom_filter_atexit_registered) { 729 atexit(trace2_bloom_filter_statistics_atexit); 730 bloom_filter_atexit_registered = 1; 731 } 732 733 free(path_alloc); 734 } 735 736 static int check_maybe_different_in_bloom_filter(struct rev_info *revs, 737 struct commit *commit) 738 { 739 struct bloom_filter *filter; 740 int result = 1, j; 741 742 if (!revs->repo->objects->commit_graph) 743 return -1; 744 745 if (commit_graph_generation(commit) == GENERATION_NUMBER_INFINITY) 746 return -1; 747 748 filter = get_bloom_filter(revs->repo, commit); 749 750 if (!filter) { 751 count_bloom_filter_not_present++; 752 return -1; 753 } 754 755 for (j = 0; result && j < revs->bloom_keys_nr; j++) { 756 result = bloom_filter_contains(filter, 757 &revs->bloom_keys[j], 758 revs->bloom_filter_settings); 759 } 760 761 if (result) 762 count_bloom_filter_maybe++; 763 else 764 count_bloom_filter_definitely_not++; 765 766 return result; 767 } 768 769 static int rev_compare_tree(struct rev_info *revs, 770 struct commit *parent, struct commit *commit, int nth_parent) 771 { 772 struct tree *t1 = get_commit_tree(parent); 773 struct tree *t2 = get_commit_tree(commit); 774 int bloom_ret = 1; 775 776 if (!t1) 777 return REV_TREE_NEW; 778 if (!t2) 779 return REV_TREE_OLD; 780 781 if (revs->simplify_by_decoration) { 782 /* 783 * If we are simplifying by decoration, then the commit 784 * is worth showing if it has a tag pointing at it. 785 */ 786 if (get_name_decoration(&commit->object)) 787 return REV_TREE_DIFFERENT; 788 /* 789 * A commit that is not pointed by a tag is uninteresting 790 * if we are not limited by path. This means that you will 791 * see the usual "commits that touch the paths" plus any 792 * tagged commit by specifying both --simplify-by-decoration 793 * and pathspec. 794 */ 795 if (!revs->prune_data.nr) 796 return REV_TREE_SAME; 797 } 798 799 if (revs->bloom_keys_nr && !nth_parent) { 800 bloom_ret = check_maybe_different_in_bloom_filter(revs, commit); 801 802 if (bloom_ret == 0) 803 return REV_TREE_SAME; 804 } 805 806 tree_difference = REV_TREE_SAME; 807 revs->pruning.flags.has_changes = 0; 808 diff_tree_oid(&t1->object.oid, &t2->object.oid, "", &revs->pruning); 809 810 if (!nth_parent) 811 if (bloom_ret == 1 && tree_difference == REV_TREE_SAME) 812 count_bloom_filter_false_positive++; 813 814 return tree_difference; 815 } 816 817 static int rev_same_tree_as_empty(struct rev_info *revs, struct commit *commit) 818 { 819 struct tree *t1 = get_commit_tree(commit); 820 821 if (!t1) 822 return 0; 823 824 tree_difference = REV_TREE_SAME; 825 revs->pruning.flags.has_changes = 0; 826 diff_tree_oid(NULL, &t1->object.oid, "", &revs->pruning); 827 828 return tree_difference == REV_TREE_SAME; 829 } 830 831 struct treesame_state { 832 unsigned int nparents; 833 unsigned char treesame[FLEX_ARRAY]; 834 }; 835 836 static struct treesame_state *initialise_treesame(struct rev_info *revs, struct commit *commit) 837 { 838 unsigned n = commit_list_count(commit->parents); 839 struct treesame_state *st = xcalloc(1, st_add(sizeof(*st), n)); 840 st->nparents = n; 841 add_decoration(&revs->treesame, &commit->object, st); 842 return st; 843 } 844 845 /* 846 * Must be called immediately after removing the nth_parent from a commit's 847 * parent list, if we are maintaining the per-parent treesame[] decoration. 848 * This does not recalculate the master TREESAME flag - update_treesame() 849 * should be called to update it after a sequence of treesame[] modifications 850 * that may have affected it. 851 */ 852 static int compact_treesame(struct rev_info *revs, struct commit *commit, unsigned nth_parent) 853 { 854 struct treesame_state *st; 855 int old_same; 856 857 if (!commit->parents) { 858 /* 859 * Have just removed the only parent from a non-merge. 860 * Different handling, as we lack decoration. 861 */ 862 if (nth_parent != 0) 863 die("compact_treesame %u", nth_parent); 864 old_same = !!(commit->object.flags & TREESAME); 865 if (rev_same_tree_as_empty(revs, commit)) 866 commit->object.flags |= TREESAME; 867 else 868 commit->object.flags &= ~TREESAME; 869 return old_same; 870 } 871 872 st = lookup_decoration(&revs->treesame, &commit->object); 873 if (!st || nth_parent >= st->nparents) 874 die("compact_treesame %u", nth_parent); 875 876 old_same = st->treesame[nth_parent]; 877 memmove(st->treesame + nth_parent, 878 st->treesame + nth_parent + 1, 879 st->nparents - nth_parent - 1); 880 881 /* 882 * If we've just become a non-merge commit, update TREESAME 883 * immediately, and remove the no-longer-needed decoration. 884 * If still a merge, defer update until update_treesame(). 885 */ 886 if (--st->nparents == 1) { 887 if (commit->parents->next) 888 die("compact_treesame parents mismatch"); 889 if (st->treesame[0] && revs->dense) 890 commit->object.flags |= TREESAME; 891 else 892 commit->object.flags &= ~TREESAME; 893 free(add_decoration(&revs->treesame, &commit->object, NULL)); 894 } 895 896 return old_same; 897 } 898 899 static unsigned update_treesame(struct rev_info *revs, struct commit *commit) 900 { 901 if (commit->parents && commit->parents->next) { 902 unsigned n; 903 struct treesame_state *st; 904 struct commit_list *p; 905 unsigned relevant_parents; 906 unsigned relevant_change, irrelevant_change; 907 908 st = lookup_decoration(&revs->treesame, &commit->object); 909 if (!st) 910 die("update_treesame %s", oid_to_hex(&commit->object.oid)); 911 relevant_parents = 0; 912 relevant_change = irrelevant_change = 0; 913 for (p = commit->parents, n = 0; p; n++, p = p->next) { 914 if (relevant_commit(p->item)) { 915 relevant_change |= !st->treesame[n]; 916 relevant_parents++; 917 } else 918 irrelevant_change |= !st->treesame[n]; 919 } 920 if (relevant_parents ? relevant_change : irrelevant_change) 921 commit->object.flags &= ~TREESAME; 922 else 923 commit->object.flags |= TREESAME; 924 } 925 926 return commit->object.flags & TREESAME; 927 } 928 929 static inline int limiting_can_increase_treesame(const struct rev_info *revs) 930 { 931 /* 932 * TREESAME is irrelevant unless prune && dense; 933 * if simplify_history is set, we can't have a mixture of TREESAME and 934 * !TREESAME INTERESTING parents (and we don't have treesame[] 935 * decoration anyway); 936 * if first_parent_only is set, then the TREESAME flag is locked 937 * against the first parent (and again we lack treesame[] decoration). 938 */ 939 return revs->prune && revs->dense && 940 !revs->simplify_history && 941 !revs->first_parent_only; 942 } 943 944 static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit) 945 { 946 struct commit_list **pp, *parent; 947 struct treesame_state *ts = NULL; 948 int relevant_change = 0, irrelevant_change = 0; 949 int relevant_parents, nth_parent; 950 951 /* 952 * If we don't do pruning, everything is interesting 953 */ 954 if (!revs->prune) 955 return; 956 957 if (!get_commit_tree(commit)) 958 return; 959 960 if (!commit->parents) { 961 if (rev_same_tree_as_empty(revs, commit)) 962 commit->object.flags |= TREESAME; 963 return; 964 } 965 966 /* 967 * Normal non-merge commit? If we don't want to make the 968 * history dense, we consider it always to be a change.. 969 */ 970 if (!revs->dense && !commit->parents->next) 971 return; 972 973 for (pp = &commit->parents, nth_parent = 0, relevant_parents = 0; 974 (parent = *pp) != NULL; 975 pp = &parent->next, nth_parent++) { 976 struct commit *p = parent->item; 977 if (relevant_commit(p)) 978 relevant_parents++; 979 980 if (nth_parent == 1) { 981 /* 982 * This our second loop iteration - so we now know 983 * we're dealing with a merge. 984 * 985 * Do not compare with later parents when we care only about 986 * the first parent chain, in order to avoid derailing the 987 * traversal to follow a side branch that brought everything 988 * in the path we are limited to by the pathspec. 989 */ 990 if (revs->first_parent_only) 991 break; 992 /* 993 * If this will remain a potentially-simplifiable 994 * merge, remember per-parent treesame if needed. 995 * Initialise the array with the comparison from our 996 * first iteration. 997 */ 998 if (revs->treesame.name && 999 !revs->simplify_history && 1000 !(commit->object.flags & UNINTERESTING)) { 1001 ts = initialise_treesame(revs, commit); 1002 if (!(irrelevant_change || relevant_change)) 1003 ts->treesame[0] = 1; 1004 } 1005 } 1006 if (repo_parse_commit(revs->repo, p) < 0) 1007 die("cannot simplify commit %s (because of %s)", 1008 oid_to_hex(&commit->object.oid), 1009 oid_to_hex(&p->object.oid)); 1010 switch (rev_compare_tree(revs, p, commit, nth_parent)) { 1011 case REV_TREE_SAME: 1012 if (!revs->simplify_history || !relevant_commit(p)) { 1013 /* Even if a merge with an uninteresting 1014 * side branch brought the entire change 1015 * we are interested in, we do not want 1016 * to lose the other branches of this 1017 * merge, so we just keep going. 1018 */ 1019 if (ts) 1020 ts->treesame[nth_parent] = 1; 1021 continue; 1022 } 1023 parent->next = NULL; 1024 commit->parents = parent; 1025 1026 /* 1027 * A merge commit is a "diversion" if it is not 1028 * TREESAME to its first parent but is TREESAME 1029 * to a later parent. In the simplified history, 1030 * we "divert" the history walk to the later 1031 * parent. These commits are shown when "show_pulls" 1032 * is enabled, so do not mark the object as 1033 * TREESAME here. 1034 */ 1035 if (!revs->show_pulls || !nth_parent) 1036 commit->object.flags |= TREESAME; 1037 1038 return; 1039 1040 case REV_TREE_NEW: 1041 if (revs->remove_empty_trees && 1042 rev_same_tree_as_empty(revs, p)) { 1043 /* We are adding all the specified 1044 * paths from this parent, so the 1045 * history beyond this parent is not 1046 * interesting. Remove its parents 1047 * (they are grandparents for us). 1048 * IOW, we pretend this parent is a 1049 * "root" commit. 1050 */ 1051 if (repo_parse_commit(revs->repo, p) < 0) 1052 die("cannot simplify commit %s (invalid %s)", 1053 oid_to_hex(&commit->object.oid), 1054 oid_to_hex(&p->object.oid)); 1055 p->parents = NULL; 1056 } 1057 /* fallthrough */ 1058 case REV_TREE_OLD: 1059 case REV_TREE_DIFFERENT: 1060 if (relevant_commit(p)) 1061 relevant_change = 1; 1062 else 1063 irrelevant_change = 1; 1064 1065 if (!nth_parent) 1066 commit->object.flags |= PULL_MERGE; 1067 1068 continue; 1069 } 1070 die("bad tree compare for commit %s", oid_to_hex(&commit->object.oid)); 1071 } 1072 1073 /* 1074 * TREESAME is straightforward for single-parent commits. For merge 1075 * commits, it is most useful to define it so that "irrelevant" 1076 * parents cannot make us !TREESAME - if we have any relevant 1077 * parents, then we only consider TREESAMEness with respect to them, 1078 * allowing irrelevant merges from uninteresting branches to be 1079 * simplified away. Only if we have only irrelevant parents do we 1080 * base TREESAME on them. Note that this logic is replicated in 1081 * update_treesame, which should be kept in sync. 1082 */ 1083 if (relevant_parents ? !relevant_change : !irrelevant_change) 1084 commit->object.flags |= TREESAME; 1085 } 1086 1087 static int process_parents(struct rev_info *revs, struct commit *commit, 1088 struct commit_list **list, struct prio_queue *queue) 1089 { 1090 struct commit_list *parent = commit->parents; 1091 unsigned left_flag; 1092 1093 if (commit->object.flags & ADDED) 1094 return 0; 1095 commit->object.flags |= ADDED; 1096 1097 if (revs->include_check && 1098 !revs->include_check(commit, revs->include_check_data)) 1099 return 0; 1100 1101 /* 1102 * If the commit is uninteresting, don't try to 1103 * prune parents - we want the maximal uninteresting 1104 * set. 1105 * 1106 * Normally we haven't parsed the parent 1107 * yet, so we won't have a parent of a parent 1108 * here. However, it may turn out that we've 1109 * reached this commit some other way (where it 1110 * wasn't uninteresting), in which case we need 1111 * to mark its parents recursively too.. 1112 */ 1113 if (commit->object.flags & UNINTERESTING) { 1114 while (parent) { 1115 struct commit *p = parent->item; 1116 parent = parent->next; 1117 if (p) 1118 p->object.flags |= UNINTERESTING; 1119 if (repo_parse_commit_gently(revs->repo, p, 1) < 0) 1120 continue; 1121 if (p->parents) 1122 mark_parents_uninteresting(p); 1123 if (p->object.flags & SEEN) 1124 continue; 1125 p->object.flags |= (SEEN | NOT_USER_GIVEN); 1126 if (list) 1127 commit_list_insert_by_date(p, list); 1128 if (queue) 1129 prio_queue_put(queue, p); 1130 } 1131 return 0; 1132 } 1133 1134 /* 1135 * Ok, the commit wasn't uninteresting. Try to 1136 * simplify the commit history and find the parent 1137 * that has no differences in the path set if one exists. 1138 */ 1139 try_to_simplify_commit(revs, commit); 1140 1141 if (revs->no_walk) 1142 return 0; 1143 1144 left_flag = (commit->object.flags & SYMMETRIC_LEFT); 1145 1146 for (parent = commit->parents; parent; parent = parent->next) { 1147 struct commit *p = parent->item; 1148 int gently = revs->ignore_missing_links || 1149 revs->exclude_promisor_objects; 1150 if (repo_parse_commit_gently(revs->repo, p, gently) < 0) { 1151 if (revs->exclude_promisor_objects && 1152 is_promisor_object(&p->object.oid)) { 1153 if (revs->first_parent_only) 1154 break; 1155 continue; 1156 } 1157 return -1; 1158 } 1159 if (revs->sources) { 1160 char **slot = revision_sources_at(revs->sources, p); 1161 1162 if (!*slot) 1163 *slot = *revision_sources_at(revs->sources, commit); 1164 } 1165 p->object.flags |= left_flag; 1166 if (!(p->object.flags & SEEN)) { 1167 p->object.flags |= (SEEN | NOT_USER_GIVEN); 1168 if (list) 1169 commit_list_insert_by_date(p, list); 1170 if (queue) 1171 prio_queue_put(queue, p); 1172 } 1173 if (revs->first_parent_only) 1174 break; 1175 } 1176 return 0; 1177 } 1178 1179 static void cherry_pick_list(struct commit_list *list, struct rev_info *revs) 1180 { 1181 struct commit_list *p; 1182 int left_count = 0, right_count = 0; 1183 int left_first; 1184 struct patch_ids ids; 1185 unsigned cherry_flag; 1186 1187 /* First count the commits on the left and on the right */ 1188 for (p = list; p; p = p->next) { 1189 struct commit *commit = p->item; 1190 unsigned flags = commit->object.flags; 1191 if (flags & BOUNDARY) 1192 ; 1193 else if (flags & SYMMETRIC_LEFT) 1194 left_count++; 1195 else 1196 right_count++; 1197 } 1198 1199 if (!left_count || !right_count) 1200 return; 1201 1202 left_first = left_count < right_count; 1203 init_patch_ids(revs->repo, &ids); 1204 ids.diffopts.pathspec = revs->diffopt.pathspec; 1205 1206 /* Compute patch-ids for one side */ 1207 for (p = list; p; p = p->next) { 1208 struct commit *commit = p->item; 1209 unsigned flags = commit->object.flags; 1210 1211 if (flags & BOUNDARY) 1212 continue; 1213 /* 1214 * If we have fewer left, left_first is set and we omit 1215 * commits on the right branch in this loop. If we have 1216 * fewer right, we skip the left ones. 1217 */ 1218 if (left_first != !!(flags & SYMMETRIC_LEFT)) 1219 continue; 1220 add_commit_patch_id(commit, &ids); 1221 } 1222 1223 /* either cherry_mark or cherry_pick are true */ 1224 cherry_flag = revs->cherry_mark ? PATCHSAME : SHOWN; 1225 1226 /* Check the other side */ 1227 for (p = list; p; p = p->next) { 1228 struct commit *commit = p->item; 1229 struct patch_id *id; 1230 unsigned flags = commit->object.flags; 1231 1232 if (flags & BOUNDARY) 1233 continue; 1234 /* 1235 * If we have fewer left, left_first is set and we omit 1236 * commits on the left branch in this loop. 1237 */ 1238 if (left_first == !!(flags & SYMMETRIC_LEFT)) 1239 continue; 1240 1241 /* 1242 * Have we seen the same patch id? 1243 */ 1244 id = patch_id_iter_first(commit, &ids); 1245 if (!id) 1246 continue; 1247 1248 commit->object.flags |= cherry_flag; 1249 do { 1250 id->commit->object.flags |= cherry_flag; 1251 } while ((id = patch_id_iter_next(id, &ids))); 1252 } 1253 1254 free_patch_ids(&ids); 1255 } 1256 1257 /* How many extra uninteresting commits we want to see.. */ 1258 #define SLOP 5 1259 1260 static int still_interesting(struct commit_list *src, timestamp_t date, int slop, 1261 struct commit **interesting_cache) 1262 { 1263 /* 1264 * No source list at all? We're definitely done.. 1265 */ 1266 if (!src) 1267 return 0; 1268 1269 /* 1270 * Does the destination list contain entries with a date 1271 * before the source list? Definitely _not_ done. 1272 */ 1273 if (date <= src->item->date) 1274 return SLOP; 1275 1276 /* 1277 * Does the source list still have interesting commits in 1278 * it? Definitely not done.. 1279 */ 1280 if (!everybody_uninteresting(src, interesting_cache)) 1281 return SLOP; 1282 1283 /* Ok, we're closing in.. */ 1284 return slop-1; 1285 } 1286 1287 /* 1288 * "rev-list --ancestry-path A..B" computes commits that are ancestors 1289 * of B but not ancestors of A but further limits the result to those 1290 * that are descendants of A. This takes the list of bottom commits and 1291 * the result of "A..B" without --ancestry-path, and limits the latter 1292 * further to the ones that can reach one of the commits in "bottom". 1293 */ 1294 static void limit_to_ancestry(struct commit_list *bottom, struct commit_list *list) 1295 { 1296 struct commit_list *p; 1297 struct commit_list *rlist = NULL; 1298 int made_progress; 1299 1300 /* 1301 * Reverse the list so that it will be likely that we would 1302 * process parents before children. 1303 */ 1304 for (p = list; p; p = p->next) 1305 commit_list_insert(p->item, &rlist); 1306 1307 for (p = bottom; p; p = p->next) 1308 p->item->object.flags |= TMP_MARK; 1309 1310 /* 1311 * Mark the ones that can reach bottom commits in "list", 1312 * in a bottom-up fashion. 1313 */ 1314 do { 1315 made_progress = 0; 1316 for (p = rlist; p; p = p->next) { 1317 struct commit *c = p->item; 1318 struct commit_list *parents; 1319 if (c->object.flags & (TMP_MARK | UNINTERESTING)) 1320 continue; 1321 for (parents = c->parents; 1322 parents; 1323 parents = parents->next) { 1324 if (!(parents->item->object.flags & TMP_MARK)) 1325 continue; 1326 c->object.flags |= TMP_MARK; 1327 made_progress = 1; 1328 break; 1329 } 1330 } 1331 } while (made_progress); 1332 1333 /* 1334 * NEEDSWORK: decide if we want to remove parents that are 1335 * not marked with TMP_MARK from commit->parents for commits 1336 * in the resulting list. We may not want to do that, though. 1337 */ 1338 1339 /* 1340 * The ones that are not marked with TMP_MARK are uninteresting 1341 */ 1342 for (p = list; p; p = p->next) { 1343 struct commit *c = p->item; 1344 if (c->object.flags & TMP_MARK) 1345 continue; 1346 c->object.flags |= UNINTERESTING; 1347 } 1348 1349 /* We are done with the TMP_MARK */ 1350 for (p = list; p; p = p->next) 1351 p->item->object.flags &= ~TMP_MARK; 1352 for (p = bottom; p; p = p->next) 1353 p->item->object.flags &= ~TMP_MARK; 1354 free_commit_list(rlist); 1355 } 1356 1357 /* 1358 * Before walking the history, keep the set of "negative" refs the 1359 * caller has asked to exclude. 1360 * 1361 * This is used to compute "rev-list --ancestry-path A..B", as we need 1362 * to filter the result of "A..B" further to the ones that can actually 1363 * reach A. 1364 */ 1365 static struct commit_list *collect_bottom_commits(struct commit_list *list) 1366 { 1367 struct commit_list *elem, *bottom = NULL; 1368 for (elem = list; elem; elem = elem->next) 1369 if (elem->item->object.flags & BOTTOM) 1370 commit_list_insert(elem->item, &bottom); 1371 return bottom; 1372 } 1373 1374 /* Assumes either left_only or right_only is set */ 1375 static void limit_left_right(struct commit_list *list, struct rev_info *revs) 1376 { 1377 struct commit_list *p; 1378 1379 for (p = list; p; p = p->next) { 1380 struct commit *commit = p->item; 1381 1382 if (revs->right_only) { 1383 if (commit->object.flags & SYMMETRIC_LEFT) 1384 commit->object.flags |= SHOWN; 1385 } else /* revs->left_only is set */ 1386 if (!(commit->object.flags & SYMMETRIC_LEFT)) 1387 commit->object.flags |= SHOWN; 1388 } 1389 } 1390 1391 static int limit_list(struct rev_info *revs) 1392 { 1393 int slop = SLOP; 1394 timestamp_t date = TIME_MAX; 1395 struct commit_list *original_list = revs->commits; 1396 struct commit_list *newlist = NULL; 1397 struct commit_list **p = &newlist; 1398 struct commit_list *bottom = NULL; 1399 struct commit *interesting_cache = NULL; 1400 1401 if (revs->ancestry_path) { 1402 bottom = collect_bottom_commits(original_list); 1403 if (!bottom) 1404 die("--ancestry-path given but there are no bottom commits"); 1405 } 1406 1407 while (original_list) { 1408 struct commit *commit = pop_commit(&original_list); 1409 struct object *obj = &commit->object; 1410 show_early_output_fn_t show; 1411 1412 if (commit == interesting_cache) 1413 interesting_cache = NULL; 1414 1415 if (revs->max_age != -1 && (commit->date < revs->max_age)) 1416 obj->flags |= UNINTERESTING; 1417 if (process_parents(revs, commit, &original_list, NULL) < 0) 1418 return -1; 1419 if (obj->flags & UNINTERESTING) { 1420 mark_parents_uninteresting(commit); 1421 slop = still_interesting(original_list, date, slop, &interesting_cache); 1422 if (slop) 1423 continue; 1424 break; 1425 } 1426 if (revs->min_age != -1 && (commit->date > revs->min_age) && 1427 !revs->line_level_traverse) 1428 continue; 1429 date = commit->date; 1430 p = &commit_list_insert(commit, p)->next; 1431 1432 show = show_early_output; 1433 if (!show) 1434 continue; 1435 1436 show(revs, newlist); 1437 show_early_output = NULL; 1438 } 1439 if (revs->cherry_pick || revs->cherry_mark) 1440 cherry_pick_list(newlist, revs); 1441 1442 if (revs->left_only || revs->right_only) 1443 limit_left_right(newlist, revs); 1444 1445 if (bottom) { 1446 limit_to_ancestry(bottom, newlist); 1447 free_commit_list(bottom); 1448 } 1449 1450 /* 1451 * Check if any commits have become TREESAME by some of their parents 1452 * becoming UNINTERESTING. 1453 */ 1454 if (limiting_can_increase_treesame(revs)) { 1455 struct commit_list *list = NULL; 1456 for (list = newlist; list; list = list->next) { 1457 struct commit *c = list->item; 1458 if (c->object.flags & (UNINTERESTING | TREESAME)) 1459 continue; 1460 update_treesame(revs, c); 1461 } 1462 } 1463 1464 free_commit_list(original_list); 1465 revs->commits = newlist; 1466 return 0; 1467 } 1468 1469 /* 1470 * Add an entry to refs->cmdline with the specified information. 1471 * *name is copied. 1472 */ 1473 static void add_rev_cmdline(struct rev_info *revs, 1474 struct object *item, 1475 const char *name, 1476 int whence, 1477 unsigned flags) 1478 { 1479 struct rev_cmdline_info *info = &revs->cmdline; 1480 unsigned int nr = info->nr; 1481 1482 ALLOC_GROW(info->rev, nr + 1, info->alloc); 1483 info->rev[nr].item = item; 1484 info->rev[nr].name = xstrdup(name); 1485 info->rev[nr].whence = whence; 1486 info->rev[nr].flags = flags; 1487 info->nr++; 1488 } 1489 1490 static void add_rev_cmdline_list(struct rev_info *revs, 1491 struct commit_list *commit_list, 1492 int whence, 1493 unsigned flags) 1494 { 1495 while (commit_list) { 1496 struct object *object = &commit_list->item->object; 1497 add_rev_cmdline(revs, object, oid_to_hex(&object->oid), 1498 whence, flags); 1499 commit_list = commit_list->next; 1500 } 1501 } 1502 1503 struct all_refs_cb { 1504 int all_flags; 1505 int warned_bad_reflog; 1506 struct rev_info *all_revs; 1507 const char *name_for_errormsg; 1508 struct worktree *wt; 1509 }; 1510 1511 int ref_excluded(struct string_list *ref_excludes, const char *path) 1512 { 1513 struct string_list_item *item; 1514 1515 if (!ref_excludes) 1516 return 0; 1517 for_each_string_list_item(item, ref_excludes) { 1518 if (!wildmatch(item->string, path, 0)) 1519 return 1; 1520 } 1521 return 0; 1522 } 1523 1524 static int handle_one_ref(const char *path, const struct object_id *oid, 1525 int flag, void *cb_data) 1526 { 1527 struct all_refs_cb *cb = cb_data; 1528 struct object *object; 1529 1530 if (ref_excluded(cb->all_revs->ref_excludes, path)) 1531 return 0; 1532 1533 object = get_reference(cb->all_revs, path, oid, cb->all_flags); 1534 add_rev_cmdline(cb->all_revs, object, path, REV_CMD_REF, cb->all_flags); 1535 add_pending_object(cb->all_revs, object, path); 1536 return 0; 1537 } 1538 1539 static void init_all_refs_cb(struct all_refs_cb *cb, struct rev_info *revs, 1540 unsigned flags) 1541 { 1542 cb->all_revs = revs; 1543 cb->all_flags = flags; 1544 revs->rev_input_given = 1; 1545 cb->wt = NULL; 1546 } 1547 1548 void clear_ref_exclusion(struct string_list **ref_excludes_p) 1549 { 1550 if (*ref_excludes_p) { 1551 string_list_clear(*ref_excludes_p, 0); 1552 free(*ref_excludes_p); 1553 } 1554 *ref_excludes_p = NULL; 1555 } 1556 1557 void add_ref_exclusion(struct string_list **ref_excludes_p, const char *exclude) 1558 { 1559 if (!*ref_excludes_p) { 1560 CALLOC_ARRAY(*ref_excludes_p, 1); 1561 (*ref_excludes_p)->strdup_strings = 1; 1562 } 1563 string_list_append(*ref_excludes_p, exclude); 1564 } 1565 1566 static void handle_refs(struct ref_store *refs, 1567 struct rev_info *revs, unsigned flags, 1568 int (*for_each)(struct ref_store *, each_ref_fn, void *)) 1569 { 1570 struct all_refs_cb cb; 1571 1572 if (!refs) { 1573 /* this could happen with uninitialized submodules */ 1574 return; 1575 } 1576 1577 init_all_refs_cb(&cb, revs, flags); 1578 for_each(refs, handle_one_ref, &cb); 1579 } 1580 1581 static void handle_one_reflog_commit(struct object_id *oid, void *cb_data) 1582 { 1583 struct all_refs_cb *cb = cb_data; 1584 if (!is_null_oid(oid)) { 1585 struct object *o = parse_object(cb->all_revs->repo, oid); 1586 if (o) { 1587 o->flags |= cb->all_flags; 1588 /* ??? CMDLINEFLAGS ??? */ 1589 add_pending_object(cb->all_revs, o, ""); 1590 } 1591 else if (!cb->warned_bad_reflog) { 1592 warning("reflog of '%s' references pruned commits", 1593 cb->name_for_errormsg); 1594 cb->warned_bad_reflog = 1; 1595 } 1596 } 1597 } 1598 1599 static int handle_one_reflog_ent(struct object_id *ooid, struct object_id *noid, 1600 const char *email, timestamp_t timestamp, int tz, 1601 const char *message, void *cb_data) 1602 { 1603 handle_one_reflog_commit(ooid, cb_data); 1604 handle_one_reflog_commit(noid, cb_data); 1605 return 0; 1606 } 1607 1608 static int handle_one_reflog(const char *refname_in_wt, 1609 const struct object_id *oid, 1610 int flag, void *cb_data) 1611 { 1612 struct all_refs_cb *cb = cb_data; 1613 struct strbuf refname = STRBUF_INIT; 1614 1615 cb->warned_bad_reflog = 0; 1616 strbuf_worktree_ref(cb->wt, &refname, refname_in_wt); 1617 cb->name_for_errormsg = refname.buf; 1618 refs_for_each_reflog_ent(get_main_ref_store(the_repository), 1619 refname.buf, 1620 handle_one_reflog_ent, cb_data); 1621 strbuf_release(&refname); 1622 return 0; 1623 } 1624 1625 static void add_other_reflogs_to_pending(struct all_refs_cb *cb) 1626 { 1627 struct worktree **worktrees, **p; 1628 1629 worktrees = get_worktrees(); 1630 for (p = worktrees; *p; p++) { 1631 struct worktree *wt = *p; 1632 1633 if (wt->is_current) 1634 continue; 1635 1636 cb->wt = wt; 1637 refs_for_each_reflog(get_worktree_ref_store(wt), 1638 handle_one_reflog, 1639 cb); 1640 } 1641 free_worktrees(worktrees); 1642 } 1643 1644 void add_reflogs_to_pending(struct rev_info *revs, unsigned flags) 1645 { 1646 struct all_refs_cb cb; 1647 1648 cb.all_revs = revs; 1649 cb.all_flags = flags; 1650 cb.wt = NULL; 1651 for_each_reflog(handle_one_reflog, &cb); 1652 1653 if (!revs->single_worktree) 1654 add_other_reflogs_to_pending(&cb); 1655 } 1656 1657 static void add_cache_tree(struct cache_tree *it, struct rev_info *revs, 1658 struct strbuf *path, unsigned int flags) 1659 { 1660 size_t baselen = path->len; 1661 int i; 1662 1663 if (it->entry_count >= 0) { 1664 struct tree *tree = lookup_tree(revs->repo, &it->oid); 1665 tree->object.flags |= flags; 1666 add_pending_object_with_path(revs, &tree->object, "", 1667 040000, path->buf); 1668 } 1669 1670 for (i = 0; i < it->subtree_nr; i++) { 1671 struct cache_tree_sub *sub = it->down[i]; 1672 strbuf_addf(path, "%s%s", baselen ? "/" : "", sub->name); 1673 add_cache_tree(sub->cache_tree, revs, path, flags); 1674 strbuf_setlen(path, baselen); 1675 } 1676 1677 } 1678 1679 static void do_add_index_objects_to_pending(struct rev_info *revs, 1680 struct index_state *istate, 1681 unsigned int flags) 1682 { 1683 int i; 1684 1685 /* TODO: audit for interaction with sparse-index. */ 1686 ensure_full_index(istate); 1687 for (i = 0; i < istate->cache_nr; i++) { 1688 struct cache_entry *ce = istate->cache[i]; 1689 struct blob *blob; 1690 1691 if (S_ISGITLINK(ce->ce_mode)) 1692 continue; 1693 1694 blob = lookup_blob(revs->repo, &ce->oid); 1695 if (!blob) 1696 die("unable to add index blob to traversal"); 1697 blob->object.flags |= flags; 1698 add_pending_object_with_path(revs, &blob->object, "", 1699 ce->ce_mode, ce->name); 1700 } 1701 1702 if (istate->cache_tree) { 1703 struct strbuf path = STRBUF_INIT; 1704 add_cache_tree(istate->cache_tree, revs, &path, flags); 1705 strbuf_release(&path); 1706 } 1707 } 1708 1709 void add_index_objects_to_pending(struct rev_info *revs, unsigned int flags) 1710 { 1711 struct worktree **worktrees, **p; 1712 1713 repo_read_index(revs->repo); 1714 do_add_index_objects_to_pending(revs, revs->repo->index, flags); 1715 1716 if (revs->single_worktree) 1717 return; 1718 1719 worktrees = get_worktrees(); 1720 for (p = worktrees; *p; p++) { 1721 struct worktree *wt = *p; 1722 struct index_state istate = { NULL }; 1723 1724 if (wt->is_current) 1725 continue; /* current index already taken care of */ 1726 1727 if (read_index_from(&istate, 1728 worktree_git_path(wt, "index"), 1729 get_worktree_git_dir(wt)) > 0) 1730 do_add_index_objects_to_pending(revs, &istate, flags); 1731 discard_index(&istate); 1732 } 1733 free_worktrees(worktrees); 1734 } 1735 1736 struct add_alternate_refs_data { 1737 struct rev_info *revs; 1738 unsigned int flags; 1739 }; 1740 1741 static void add_one_alternate_ref(const struct object_id *oid, 1742 void *vdata) 1743 { 1744 const char *name = ".alternate"; 1745 struct add_alternate_refs_data *data = vdata; 1746 struct object *obj; 1747 1748 obj = get_reference(data->revs, name, oid, data->flags); 1749 add_rev_cmdline(data->revs, obj, name, REV_CMD_REV, data->flags); 1750 add_pending_object(data->revs, obj, name); 1751 } 1752 1753 static void add_alternate_refs_to_pending(struct rev_info *revs, 1754 unsigned int flags) 1755 { 1756 struct add_alternate_refs_data data; 1757 data.revs = revs; 1758 data.flags = flags; 1759 for_each_alternate_ref(add_one_alternate_ref, &data); 1760 } 1761 1762 static int add_parents_only(struct rev_info *revs, const char *arg_, int flags, 1763 int exclude_parent) 1764 { 1765 struct object_id oid; 1766 struct object *it; 1767 struct commit *commit; 1768 struct commit_list *parents; 1769 int parent_number; 1770 const char *arg = arg_; 1771 1772 if (*arg == '^') { 1773 flags ^= UNINTERESTING | BOTTOM; 1774 arg++; 1775 } 1776 if (get_oid_committish(arg, &oid)) 1777 return 0; 1778 while (1) { 1779 it = get_reference(revs, arg, &oid, 0); 1780 if (!it && revs->ignore_missing) 1781 return 0; 1782 if (it->type != OBJ_TAG) 1783 break; 1784 if (!((struct tag*)it)->tagged) 1785 return 0; 1786 oidcpy(&oid, &((struct tag*)it)->tagged->oid); 1787 } 1788 if (it->type != OBJ_COMMIT) 1789 return 0; 1790 commit = (struct commit *)it; 1791 if (exclude_parent && 1792 exclude_parent > commit_list_count(commit->parents)) 1793 return 0; 1794 for (parents = commit->parents, parent_number = 1; 1795 parents; 1796 parents = parents->next, parent_number++) { 1797 if (exclude_parent && parent_number != exclude_parent) 1798 continue; 1799 1800 it = &parents->item->object; 1801 it->flags |= flags; 1802 add_rev_cmdline(revs, it, arg_, REV_CMD_PARENTS_ONLY, flags); 1803 add_pending_object(revs, it, arg); 1804 } 1805 return 1; 1806 } 1807 1808 void repo_init_revisions(struct repository *r, 1809 struct rev_info *revs, 1810 const char *prefix) 1811 { 1812 memset(revs, 0, sizeof(*revs)); 1813 1814 revs->repo = r; 1815 revs->abbrev = DEFAULT_ABBREV; 1816 revs->simplify_history = 1; 1817 revs->pruning.repo = r; 1818 revs->pruning.flags.recursive = 1; 1819 revs->pruning.flags.quick = 1; 1820 revs->pruning.add_remove = file_add_remove; 1821 revs->pruning.change = file_change; 1822 revs->pruning.change_fn_data = revs; 1823 revs->sort_order = REV_SORT_IN_GRAPH_ORDER; 1824 revs->dense = 1; 1825 revs->prefix = prefix; 1826 revs->max_age = -1; 1827 revs->min_age = -1; 1828 revs->skip_count = -1; 1829 revs->max_count = -1; 1830 revs->max_parents = -1; 1831 revs->expand_tabs_in_log = -1; 1832 1833 revs->commit_format = CMIT_FMT_DEFAULT; 1834 revs->expand_tabs_in_log_default = 8; 1835 1836 grep_init(&revs->grep_filter, revs->repo, prefix); 1837 revs->grep_filter.status_only = 1; 1838 1839 repo_diff_setup(revs->repo, &revs->diffopt); 1840 if (prefix && !revs->diffopt.prefix) { 1841 revs->diffopt.prefix = prefix; 1842 revs->diffopt.prefix_length = strlen(prefix); 1843 } 1844 1845 init_display_notes(&revs->notes_opt); 1846 } 1847 1848 static void add_pending_commit_list(struct rev_info *revs, 1849 struct commit_list *commit_list, 1850 unsigned int flags) 1851 { 1852 while (commit_list) { 1853 struct object *object = &commit_list->item->object; 1854 object->flags |= flags; 1855 add_pending_object(revs, object, oid_to_hex(&object->oid)); 1856 commit_list = commit_list->next; 1857 } 1858 } 1859 1860 static void prepare_show_merge(struct rev_info *revs) 1861 { 1862 struct commit_list *bases; 1863 struct commit *head, *other; 1864 struct object_id oid; 1865 const char **prune = NULL; 1866 int i, prune_num = 1; /* counting terminating NULL */ 1867 struct index_state *istate = revs->repo->index; 1868 1869 if (get_oid("HEAD", &oid)) 1870 die("--merge without HEAD?"); 1871 head = lookup_commit_or_die(&oid, "HEAD"); 1872 if (get_oid("MERGE_HEAD", &oid)) 1873 die("--merge without MERGE_HEAD?"); 1874 other = lookup_commit_or_die(&oid, "MERGE_HEAD"); 1875 add_pending_object(revs, &head->object, "HEAD"); 1876 add_pending_object(revs, &other->object, "MERGE_HEAD"); 1877 bases = get_merge_bases(head, other); 1878 add_rev_cmdline_list(revs, bases, REV_CMD_MERGE_BASE, UNINTERESTING | BOTTOM); 1879 add_pending_commit_list(revs, bases, UNINTERESTING | BOTTOM); 1880 free_commit_list(bases); 1881 head->object.flags |= SYMMETRIC_LEFT; 1882 1883 if (!istate->cache_nr) 1884 repo_read_index(revs->repo); 1885 for (i = 0; i < istate->cache_nr; i++) { 1886 const struct cache_entry *ce = istate->cache[i]; 1887 if (!ce_stage(ce)) 1888 continue; 1889 if (ce_path_match(istate, ce, &revs->prune_data, NULL)) { 1890 prune_num++; 1891 REALLOC_ARRAY(prune, prune_num); 1892 prune[prune_num-2] = ce->name; 1893 prune[prune_num-1] = NULL; 1894 } 1895 while ((i+1 < istate->cache_nr) && 1896 ce_same_name(ce, istate->cache[i+1])) 1897 i++; 1898 } 1899 clear_pathspec(&revs->prune_data); 1900 parse_pathspec(&revs->prune_data, PATHSPEC_ALL_MAGIC & ~PATHSPEC_LITERAL, 1901 PATHSPEC_PREFER_FULL | PATHSPEC_LITERAL_PATH, "", prune); 1902 revs->limited = 1; 1903 } 1904 1905 static int dotdot_missing(const char *arg, char *dotdot, 1906 struct rev_info *revs, int symmetric) 1907 { 1908 if (revs->ignore_missing) 1909 return 0; 1910 /* de-munge so we report the full argument */ 1911 *dotdot = '.'; 1912 die(symmetric 1913 ? "Invalid symmetric difference expression %s" 1914 : "Invalid revision range %s", arg); 1915 } 1916 1917 static int handle_dotdot_1(const char *arg, char *dotdot, 1918 struct rev_info *revs, int flags, 1919 int cant_be_filename, 1920 struct object_context *a_oc, 1921 struct object_context *b_oc) 1922 { 1923 const char *a_name, *b_name; 1924 struct object_id a_oid, b_oid; 1925 struct object *a_obj, *b_obj; 1926 unsigned int a_flags, b_flags; 1927 int symmetric = 0; 1928 unsigned int flags_exclude = flags ^ (UNINTERESTING | BOTTOM); 1929 unsigned int oc_flags = GET_OID_COMMITTISH | GET_OID_RECORD_PATH; 1930 1931 a_name = arg; 1932 if (!*a_name) 1933 a_name = "HEAD"; 1934 1935 b_name = dotdot + 2; 1936 if (*b_name == '.') { 1937 symmetric = 1; 1938 b_name++; 1939 } 1940 if (!*b_name) 1941 b_name = "HEAD"; 1942 1943 if (get_oid_with_context(revs->repo, a_name, oc_flags, &a_oid, a_oc) || 1944 get_oid_with_context(revs->repo, b_name, oc_flags, &b_oid, b_oc)) 1945 return -1; 1946 1947 if (!cant_be_filename) { 1948 *dotdot = '.'; 1949 verify_non_filename(revs->prefix, arg); 1950 *dotdot = '\0'; 1951 } 1952 1953 a_obj = parse_object(revs->repo, &a_oid); 1954 b_obj = parse_object(revs->repo, &b_oid); 1955 if (!a_obj || !b_obj) 1956 return dotdot_missing(arg, dotdot, revs, symmetric); 1957 1958 if (!symmetric) { 1959 /* just A..B */ 1960 b_flags = flags; 1961 a_flags = flags_exclude; 1962 } else { 1963 /* A...B -- find merge bases between the two */ 1964 struct commit *a, *b; 1965 struct commit_list *exclude; 1966 1967 a = lookup_commit_reference(revs->repo, &a_obj->oid); 1968 b = lookup_commit_reference(revs->repo, &b_obj->oid); 1969 if (!a || !b) 1970 return dotdot_missing(arg, dotdot, revs, symmetric); 1971 1972 exclude = get_merge_bases(a, b); 1973 add_rev_cmdline_list(revs, exclude, REV_CMD_MERGE_BASE, 1974 flags_exclude); 1975 add_pending_commit_list(revs, exclude, flags_exclude); 1976 free_commit_list(exclude); 1977 1978 b_flags = flags; 1979 a_flags = flags | SYMMETRIC_LEFT; 1980 } 1981 1982 a_obj->flags |= a_flags; 1983 b_obj->flags |= b_flags; 1984 add_rev_cmdline(revs, a_obj, a_name, REV_CMD_LEFT, a_flags); 1985 add_rev_cmdline(revs, b_obj, b_name, REV_CMD_RIGHT, b_flags); 1986 add_pending_object_with_path(revs, a_obj, a_name, a_oc->mode, a_oc->path); 1987 add_pending_object_with_path(revs, b_obj, b_name, b_oc->mode, b_oc->path); 1988 return 0; 1989 } 1990 1991 static int handle_dotdot(const char *arg, 1992 struct rev_info *revs, int flags, 1993 int cant_be_filename) 1994 { 1995 struct object_context a_oc, b_oc; 1996 char *dotdot = strstr(arg, ".."); 1997 int ret; 1998 1999 if (!dotdot) 2000 return -1; 2001 2002 memset(&a_oc, 0, sizeof(a_oc)); 2003 memset(&b_oc, 0, sizeof(b_oc)); 2004 2005 *dotdot = '\0'; 2006 ret = handle_dotdot_1(arg, dotdot, revs, flags, cant_be_filename, 2007 &a_oc, &b_oc); 2008 *dotdot = '.'; 2009 2010 free(a_oc.path); 2011 free(b_oc.path); 2012 2013 return ret; 2014 } 2015 2016 static int handle_revision_arg_1(const char *arg_, struct rev_info *revs, int flags, unsigned revarg_opt) 2017 { 2018 struct object_context oc; 2019 char *mark; 2020 struct object *object; 2021 struct object_id oid; 2022 int local_flags; 2023 const char *arg = arg_; 2024 int cant_be_filename = revarg_opt & REVARG_CANNOT_BE_FILENAME; 2025 unsigned get_sha1_flags = GET_OID_RECORD_PATH; 2026 2027 flags = flags & UNINTERESTING ? flags | BOTTOM : flags & ~BOTTOM; 2028 2029 if (!cant_be_filename && !strcmp(arg, "..")) { 2030 /* 2031 * Just ".."? That is not a range but the 2032 * pathspec for the parent directory. 2033 */ 2034 return -1; 2035 } 2036 2037 if (!handle_dotdot(arg, revs, flags, revarg_opt)) 2038 return 0; 2039 2040 mark = strstr(arg, "^@"); 2041 if (mark && !mark[2]) { 2042 *mark = 0; 2043 if (add_parents_only(revs, arg, flags, 0)) 2044 return 0; 2045 *mark = '^'; 2046 } 2047 mark = strstr(arg, "^!"); 2048 if (mark && !mark[2]) { 2049 *mark = 0; 2050 if (!add_parents_only(revs, arg, flags ^ (UNINTERESTING | BOTTOM), 0)) 2051 *mark = '^'; 2052 } 2053 mark = strstr(arg, "^-"); 2054 if (mark) { 2055 int exclude_parent = 1; 2056 2057 if (mark[2]) { 2058 char *end; 2059 exclude_parent = strtoul(mark + 2, &end, 10); 2060 if (*end != '\0' || !exclude_parent) 2061 return -1; 2062 } 2063 2064 *mark = 0; 2065 if (!add_parents_only(revs, arg, flags ^ (UNINTERESTING | BOTTOM), exclude_parent)) 2066 *mark = '^'; 2067 } 2068 2069 local_flags = 0; 2070 if (*arg == '^') { 2071 local_flags = UNINTERESTING | BOTTOM; 2072 arg++; 2073 } 2074 2075 if (revarg_opt & REVARG_COMMITTISH) 2076 get_sha1_flags |= GET_OID_COMMITTISH; 2077 2078 if (get_oid_with_context(revs->repo, arg, get_sha1_flags, &oid, &oc)) 2079 return revs->ignore_missing ? 0 : -1; 2080 if (!cant_be_filename) 2081 verify_non_filename(revs->prefix, arg); 2082 object = get_reference(revs, arg, &oid, flags ^ local_flags); 2083 if (!object) 2084 return revs->ignore_missing ? 0 : -1; 2085 add_rev_cmdline(revs, object, arg_, REV_CMD_REV, flags ^ local_flags); 2086 add_pending_object_with_path(revs, object, arg, oc.mode, oc.path); 2087 free(oc.path); 2088 return 0; 2089 } 2090 2091 int handle_revision_arg(const char *arg, struct rev_info *revs, int flags, unsigned revarg_opt) 2092 { 2093 int ret = handle_revision_arg_1(arg, revs, flags, revarg_opt); 2094 if (!ret) 2095 revs->rev_input_given = 1; 2096 return ret; 2097 } 2098 2099 static void read_pathspec_from_stdin(struct strbuf *sb, 2100 struct strvec *prune) 2101 { 2102 while (strbuf_getline(sb, stdin) != EOF) 2103 strvec_push(prune, sb->buf); 2104 } 2105 2106 static void read_revisions_from_stdin(struct rev_info *revs, 2107 struct strvec *prune) 2108 { 2109 struct strbuf sb; 2110 int seen_dashdash = 0; 2111 int save_warning; 2112 2113 save_warning = warn_on_object_refname_ambiguity; 2114 warn_on_object_refname_ambiguity = 0; 2115 2116 strbuf_init(&sb, 1000); 2117 while (strbuf_getline(&sb, stdin) != EOF) { 2118 int len = sb.len; 2119 if (!len) 2120 break; 2121 if (sb.buf[0] == '-') { 2122 if (len == 2 && sb.buf[1] == '-') { 2123 seen_dashdash = 1; 2124 break; 2125 } 2126 die("options not supported in --stdin mode"); 2127 } 2128 if (handle_revision_arg(sb.buf, revs, 0, 2129 REVARG_CANNOT_BE_FILENAME)) 2130 die("bad revision '%s'", sb.buf); 2131 } 2132 if (seen_dashdash) 2133 read_pathspec_from_stdin(&sb, prune); 2134 2135 strbuf_release(&sb); 2136 warn_on_object_refname_ambiguity = save_warning; 2137 } 2138 2139 static void add_grep(struct rev_info *revs, const char *ptn, enum grep_pat_token what) 2140 { 2141 append_grep_pattern(&revs->grep_filter, ptn, "command line", 0, what); 2142 } 2143 2144 static void add_header_grep(struct rev_info *revs, enum grep_header_field field, const char *pattern) 2145 { 2146 append_header_grep_pattern(&revs->grep_filter, field, pattern); 2147 } 2148 2149 static void add_message_grep(struct rev_info *revs, const char *pattern) 2150 { 2151 add_grep(revs, pattern, GREP_PATTERN_BODY); 2152 } 2153 2154 static int handle_revision_opt(struct rev_info *revs, int argc, const char **argv, 2155 int *unkc, const char **unkv, 2156 const struct setup_revision_opt* opt) 2157 { 2158 const char *arg = argv[0]; 2159 const char *optarg; 2160 int argcount; 2161 const unsigned hexsz = the_hash_algo->hexsz; 2162 2163 /* pseudo revision arguments */ 2164 if (!strcmp(arg, "--all") || !strcmp(arg, "--branches") || 2165 !strcmp(arg, "--tags") || !strcmp(arg, "--remotes") || 2166 !strcmp(arg, "--reflog") || !strcmp(arg, "--not") || 2167 !strcmp(arg, "--no-walk") || !strcmp(arg, "--do-walk") || 2168 !strcmp(arg, "--bisect") || starts_with(arg, "--glob=") || 2169 !strcmp(arg, "--indexed-objects") || 2170 !strcmp(arg, "--alternate-refs") || 2171 starts_with(arg, "--exclude=") || 2172 starts_with(arg, "--branches=") || starts_with(arg, "--tags=") || 2173 starts_with(arg, "--remotes=") || starts_with(arg, "--no-walk=")) 2174 { 2175 unkv[(*unkc)++] = arg; 2176 return 1; 2177 } 2178 2179 if ((argcount = parse_long_opt("max-count", argv, &optarg))) { 2180 revs->max_count = atoi(optarg); 2181 revs->no_walk = 0; 2182 return argcount; 2183 } else if ((argcount = parse_long_opt("skip", argv, &optarg))) { 2184 revs->skip_count = atoi(optarg); 2185 return argcount; 2186 } else if ((*arg == '-') && isdigit(arg[1])) { 2187 /* accept -<digit>, like traditional "head" */ 2188 if (strtol_i(arg + 1, 10, &revs->max_count) < 0 || 2189 revs->max_count < 0) 2190 die("'%s': not a non-negative integer", arg + 1); 2191 revs->no_walk = 0; 2192 } else if (!strcmp(arg, "-n")) { 2193 if (argc <= 1) 2194 return error("-n requires an argument"); 2195 revs->max_count = atoi(argv[1]); 2196 revs->no_walk = 0; 2197 return 2; 2198 } else if (skip_prefix(arg, "-n", &optarg)) { 2199 revs->max_count = atoi(optarg); 2200 revs->no_walk = 0; 2201 } else if ((argcount = parse_long_opt("max-age", argv, &optarg))) { 2202 revs->max_age = atoi(optarg); 2203 return argcount; 2204 } else if ((argcount = parse_long_opt("since", argv, &optarg))) { 2205 revs->max_age = approxidate(optarg); 2206 return argcount; 2207 } else if ((argcount = parse_long_opt("after", argv, &optarg))) { 2208 revs->max_age = approxidate(optarg); 2209 return argcount; 2210 } else if ((argcount = parse_long_opt("min-age", argv, &optarg))) { 2211 revs->min_age = atoi(optarg); 2212 return argcount; 2213 } else if ((argcount = parse_long_opt("before", argv, &optarg))) { 2214 revs->min_age = approxidate(optarg); 2215 return argcount; 2216 } else if ((argcount = parse_long_opt("until", argv, &optarg))) { 2217 revs->min_age = approxidate(optarg); 2218 return argcount; 2219 } else if (!strcmp(arg, "--first-parent")) { 2220 revs->first_parent_only = 1; 2221 } else if (!strcmp(arg, "--ancestry-path")) { 2222 revs->ancestry_path = 1; 2223 revs->simplify_history = 0; 2224 revs->limited = 1; 2225 } else if (!strcmp(arg, "-g") || !strcmp(arg, "--walk-reflogs")) { 2226 init_reflog_walk(&revs->reflog_info); 2227 } else if (!strcmp(arg, "--default")) { 2228 if (argc <= 1) 2229 return error("bad --default argument"); 2230 revs->def = argv[1]; 2231 return 2; 2232 } else if (!strcmp(arg, "--merge")) { 2233 revs->show_merge = 1; 2234 } else if (!strcmp(arg, "--topo-order")) { 2235 revs->sort_order = REV_SORT_IN_GRAPH_ORDER; 2236 revs->topo_order = 1; 2237 } else if (!strcmp(arg, "--simplify-merges")) { 2238 revs->simplify_merges = 1; 2239 revs->topo_order = 1; 2240 revs->rewrite_parents = 1; 2241 revs->simplify_history = 0; 2242 revs->limited = 1; 2243 } else if (!strcmp(arg, "--simplify-by-decoration")) { 2244 revs->simplify_merges = 1; 2245 revs->topo_order = 1; 2246 revs->rewrite_parents = 1; 2247 revs->simplify_history = 0; 2248 revs->simplify_by_decoration = 1; 2249 revs->limited = 1; 2250 revs->prune = 1; 2251 } else if (!strcmp(arg, "--date-order")) { 2252 revs->sort_order = REV_SORT_BY_COMMIT_DATE; 2253 revs->topo_order = 1; 2254 } else if (!strcmp(arg, "--author-date-order")) { 2255 revs->sort_order = REV_SORT_BY_AUTHOR_DATE; 2256 revs->topo_order = 1; 2257 } else if (!strcmp(arg, "--early-output")) { 2258 revs->early_output = 100; 2259 revs->topo_order = 1; 2260 } else if (skip_prefix(arg, "--early-output=", &optarg)) { 2261 if (strtoul_ui(optarg, 10, &revs->early_output) < 0) 2262 die("'%s': not a non-negative integer", optarg); 2263 revs->topo_order = 1; 2264 } else if (!strcmp(arg, "--parents")) { 2265 revs->rewrite_parents = 1; 2266 revs->print_parents = 1; 2267 } else if (!strcmp(arg, "--dense")) { 2268 revs->dense = 1; 2269 } else if (!strcmp(arg, "--sparse")) { 2270 revs->dense = 0; 2271 } else if (!strcmp(arg, "--in-commit-order")) { 2272 revs->tree_blobs_in_commit_order = 1; 2273 } else if (!strcmp(arg, "--remove-empty")) { 2274 revs->remove_empty_trees = 1; 2275 } else if (!strcmp(arg, "--merges")) { 2276 revs->min_parents = 2; 2277 } else if (!strcmp(arg, "--no-merges")) { 2278 revs->max_parents = 1; 2279 } else if (skip_prefix(arg, "--min-parents=", &optarg)) { 2280 revs->min_parents = atoi(optarg); 2281 } else if (!strcmp(arg, "--no-min-parents")) { 2282 revs->min_parents = 0; 2283 } else if (skip_prefix(arg, "--max-parents=", &optarg)) { 2284 revs->max_parents = atoi(optarg); 2285 } else if (!strcmp(arg, "--no-max-parents")) { 2286 revs->max_parents = -1; 2287 } else if (!strcmp(arg, "--boundary")) { 2288 revs->boundary = 1; 2289 } else if (!strcmp(arg, "--left-right")) { 2290 revs->left_right = 1; 2291 } else if (!strcmp(arg, "--left-only")) { 2292 if (revs->right_only) 2293 die("--left-only is incompatible with --right-only" 2294 " or --cherry"); 2295 revs->left_only = 1; 2296 } else if (!strcmp(arg, "--right-only")) { 2297 if (revs->left_only) 2298 die("--right-only is incompatible with --left-only"); 2299 revs->right_only = 1; 2300 } else if (!strcmp(arg, "--cherry")) { 2301 if (revs->left_only) 2302 die("--cherry is incompatible with --left-only"); 2303 revs->cherry_mark = 1; 2304 revs->right_only = 1; 2305 revs->max_parents = 1; 2306 revs->limited = 1; 2307 } else if (!strcmp(arg, "--count")) { 2308 revs->count = 1; 2309 } else if (!strcmp(arg, "--cherry-mark")) { 2310 if (revs->cherry_pick) 2311 die("--cherry-mark is incompatible with --cherry-pick"); 2312 revs->cherry_mark = 1; 2313 revs->limited = 1; /* needs limit_list() */ 2314 } else if (!strcmp(arg, "--cherry-pick")) { 2315 if (revs->cherry_mark) 2316 die("--cherry-pick is incompatible with --cherry-mark"); 2317 revs->cherry_pick = 1; 2318 revs->limited = 1; 2319 } else if (!strcmp(arg, "--objects")) { 2320 revs->tag_objects = 1; 2321 revs->tree_objects = 1; 2322 revs->blob_objects = 1; 2323 } else if (!strcmp(arg, "--objects-edge")) { 2324 revs->tag_objects = 1; 2325 revs->tree_objects = 1; 2326 revs->blob_objects = 1; 2327 revs->edge_hint = 1; 2328 } else if (!strcmp(arg, "--objects-edge-aggressive")) { 2329 revs->tag_objects = 1; 2330 revs->tree_objects = 1; 2331 revs->blob_objects = 1; 2332 revs->edge_hint = 1; 2333 revs->edge_hint_aggressive = 1; 2334 } else if (!strcmp(arg, "--verify-objects")) { 2335 revs->tag_objects = 1; 2336 revs->tree_objects = 1; 2337 revs->blob_objects = 1; 2338 revs->verify_objects = 1; 2339 } else if (!strcmp(arg, "--unpacked")) { 2340 revs->unpacked = 1; 2341 } else if (starts_with(arg, "--unpacked=")) { 2342 die(_("--unpacked=<packfile> no longer supported")); 2343 } else if (!strcmp(arg, "--no-kept-objects")) { 2344 revs->no_kept_objects = 1; 2345 revs->keep_pack_cache_flags |= IN_CORE_KEEP_PACKS; 2346 revs->keep_pack_cache_flags |= ON_DISK_KEEP_PACKS; 2347 } else if (skip_prefix(arg, "--no-kept-objects=", &optarg)) { 2348 revs->no_kept_objects = 1; 2349 if (!strcmp(optarg, "in-core")) 2350 revs->keep_pack_cache_flags |= IN_CORE_KEEP_PACKS; 2351 if (!strcmp(optarg, "on-disk")) 2352 revs->keep_pack_cache_flags |= ON_DISK_KEEP_PACKS; 2353 } else if (!strcmp(arg, "-r")) { 2354 revs->diff = 1; 2355 revs->diffopt.flags.recursive = 1; 2356 } else if (!strcmp(arg, "-t")) { 2357 revs->diff = 1; 2358 revs->diffopt.flags.recursive = 1; 2359 revs->diffopt.flags.tree_in_recursive = 1; 2360 } else if ((argcount = diff_merges_parse_opts(revs, argv))) { 2361 return argcount; 2362 } else if (!strcmp(arg, "-v")) { 2363 revs->verbose_header = 1; 2364 } else if (!strcmp(arg, "--pretty")) { 2365 revs->verbose_header = 1; 2366 revs->pretty_given = 1; 2367 get_commit_format(NULL, revs); 2368 } else if (skip_prefix(arg, "--pretty=", &optarg) || 2369 skip_prefix(arg, "--format=", &optarg)) { 2370 /* 2371 * Detached form ("--pretty X" as opposed to "--pretty=X") 2372 * not allowed, since the argument is optional. 2373 */ 2374 revs->verbose_header = 1; 2375 revs->pretty_given = 1; 2376 get_commit_format(optarg, revs); 2377 } else if (!strcmp(arg, "--expand-tabs")) { 2378 revs->expand_tabs_in_log = 8; 2379 } else if (!strcmp(arg, "--no-expand-tabs")) { 2380 revs->expand_tabs_in_log = 0; 2381 } else if (skip_prefix(arg, "--expand-tabs=", &arg)) { 2382 int val; 2383 if (strtol_i(arg, 10, &val) < 0 || val < 0) 2384 die("'%s': not a non-negative integer", arg); 2385 revs->expand_tabs_in_log = val; 2386 } else if (!strcmp(arg, "--show-notes") || !strcmp(arg, "--notes")) { 2387 enable_default_display_notes(&revs->notes_opt, &revs->show_notes); 2388 revs->show_notes_given = 1; 2389 } else if (!strcmp(arg, "--show-signature")) { 2390 revs->show_signature = 1; 2391 } else if (!strcmp(arg, "--no-show-signature")) { 2392 revs->show_signature = 0; 2393 } else if (!strcmp(arg, "--show-linear-break")) { 2394 revs->break_bar = " .........."; 2395 revs->track_linear = 1; 2396 revs->track_first_time = 1; 2397 } else if (skip_prefix(arg, "--show-linear-break=", &optarg)) { 2398 revs->break_bar = xstrdup(optarg); 2399 revs->track_linear = 1; 2400 revs->track_first_time = 1; 2401 } else if (skip_prefix(arg, "--show-notes=", &optarg) || 2402 skip_prefix(arg, "--notes=", &optarg)) { 2403 if (starts_with(arg, "--show-notes=") && 2404 revs->notes_opt.use_default_notes < 0) 2405 revs->notes_opt.use_default_notes = 1; 2406 enable_ref_display_notes(&revs->notes_opt, &revs->show_notes, optarg); 2407 revs->show_notes_given = 1; 2408 } else if (!strcmp(arg, "--no-notes")) { 2409 disable_display_notes(&revs->notes_opt, &revs->show_notes); 2410 revs->show_notes_given = 1; 2411 } else if (!strcmp(arg, "--standard-notes")) { 2412 revs->show_notes_given = 1; 2413 revs->notes_opt.use_default_notes = 1; 2414 } else if (!strcmp(arg, "--no-standard-notes")) { 2415 revs->notes_opt.use_default_notes = 0; 2416 } else if (!strcmp(arg, "--oneline")) { 2417 revs->verbose_header = 1; 2418 get_commit_format("oneline", revs); 2419 revs->pretty_given = 1; 2420 revs->abbrev_commit = 1; 2421 } else if (!strcmp(arg, "--graph")) { 2422 revs->topo_order = 1; 2423 revs->rewrite_parents = 1; 2424 revs->graph = graph_init(revs); 2425 } else if (!strcmp(arg, "--encode-email-headers")) { 2426 revs->encode_email_headers = 1; 2427 } else if (!strcmp(arg, "--no-encode-email-headers")) { 2428 revs->encode_email_headers = 0; 2429 } else if (!strcmp(arg, "--root")) { 2430 revs->show_root_diff = 1; 2431 } else if (!strcmp(arg, "--no-commit-id")) { 2432 revs->no_commit_id = 1; 2433 } else if (!strcmp(arg, "--always")) { 2434 revs->always_show_header = 1; 2435 } else if (!strcmp(arg, "--no-abbrev")) { 2436 revs->abbrev = 0; 2437 } else if (!strcmp(arg, "--abbrev")) { 2438 revs->abbrev = DEFAULT_ABBREV; 2439 } else if (skip_prefix(arg, "--abbrev=", &optarg)) { 2440 revs->abbrev = strtoul(optarg, NULL, 10); 2441 if (revs->abbrev < MINIMUM_ABBREV) 2442 revs->abbrev = MINIMUM_ABBREV; 2443 else if (revs->abbrev > hexsz) 2444 revs->abbrev = hexsz; 2445 } else if (!strcmp(arg, "--abbrev-commit")) { 2446 revs->abbrev_commit = 1; 2447 revs->abbrev_commit_given = 1; 2448 } else if (!strcmp(arg, "--no-abbrev-commit")) { 2449 revs->abbrev_commit = 0; 2450 } else if (!strcmp(arg, "--full-diff")) { 2451 revs->diff = 1; 2452 revs->full_diff = 1; 2453 } else if (!strcmp(arg, "--show-pulls")) { 2454 revs->show_pulls = 1; 2455 } else if (!strcmp(arg, "--full-history")) { 2456 revs->simplify_history = 0; 2457 } else if (!strcmp(arg, "--relative-date")) { 2458 revs->date_mode.type = DATE_RELATIVE; 2459 revs->date_mode_explicit = 1; 2460 } else if ((argcount = parse_long_opt("date", argv, &optarg))) { 2461 parse_date_format(optarg, &revs->date_mode); 2462 revs->date_mode_explicit = 1; 2463 return argcount; 2464 } else if (!strcmp(arg, "--log-size")) { 2465 revs->show_log_size = 1; 2466 } 2467 /* 2468 * Grepping the commit log 2469 */ 2470 else if ((argcount = parse_long_opt("author", argv, &optarg))) { 2471 add_header_grep(revs, GREP_HEADER_AUTHOR, optarg); 2472 return argcount; 2473 } else if ((argcount = parse_long_opt("committer", argv, &optarg))) { 2474 add_header_grep(revs, GREP_HEADER_COMMITTER, optarg); 2475 return argcount; 2476 } else if ((argcount = parse_long_opt("grep-reflog", argv, &optarg))) { 2477 add_header_grep(revs, GREP_HEADER_REFLOG, optarg); 2478 return argcount; 2479 } else if ((argcount = parse_long_opt("grep", argv, &optarg))) { 2480 add_message_grep(revs, optarg); 2481 return argcount; 2482 } else if (!strcmp(arg, "--basic-regexp")) { 2483 revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_BRE; 2484 } else if (!strcmp(arg, "--extended-regexp") || !strcmp(arg, "-E")) { 2485 revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_ERE; 2486 } else if (!strcmp(arg, "--regexp-ignore-case") || !strcmp(arg, "-i")) { 2487 revs->grep_filter.ignore_case = 1; 2488 revs->diffopt.pickaxe_opts |= DIFF_PICKAXE_IGNORE_CASE; 2489 } else if (!strcmp(arg, "--fixed-strings") || !strcmp(arg, "-F")) { 2490 revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_FIXED; 2491 } else if (!strcmp(arg, "--perl-regexp") || !strcmp(arg, "-P")) { 2492 revs->grep_filter.pattern_type_option = GREP_PATTERN_TYPE_PCRE; 2493 } else if (!strcmp(arg, "--all-match")) { 2494 revs->grep_filter.all_match = 1; 2495 } else if (!strcmp(arg, "--invert-grep")) { 2496 revs->invert_grep = 1; 2497 } else if ((argcount = parse_long_opt("encoding", argv, &optarg))) { 2498 if (strcmp(optarg, "none")) 2499 git_log_output_encoding = xstrdup(optarg); 2500 else 2501 git_log_output_encoding = ""; 2502 return argcount; 2503 } else if (!strcmp(arg, "--reverse")) { 2504 revs->reverse ^= 1; 2505 } else if (!strcmp(arg, "--children")) { 2506 revs->children.name = "children"; 2507 revs->limited = 1; 2508 } else if (!strcmp(arg, "--ignore-missing")) { 2509 revs->ignore_missing = 1; 2510 } else if (opt && opt->allow_exclude_promisor_objects && 2511 !strcmp(arg, "--exclude-promisor-objects")) { 2512 if (fetch_if_missing) 2513 BUG("exclude_promisor_objects can only be used when fetch_if_missing is 0"); 2514 revs->exclude_promisor_objects = 1; 2515 } else { 2516 int opts = diff_opt_parse(&revs->diffopt, argv, argc, revs->prefix); 2517 if (!opts) 2518 unkv[(*unkc)++] = arg; 2519 return opts; 2520 } 2521 if (revs->graph && revs->track_linear) 2522 die("--show-linear-break and --graph are incompatible"); 2523 2524 return 1; 2525 } 2526 2527 void parse_revision_opt(struct rev_info *revs, struct parse_opt_ctx_t *ctx, 2528 const struct option *options, 2529 const char * const usagestr[]) 2530 { 2531 int n = handle_revision_opt(revs, ctx->argc, ctx->argv, 2532 &ctx->cpidx, ctx->out, NULL); 2533 if (n <= 0) { 2534 error("unknown option `%s'", ctx->argv[0]); 2535 usage_with_options(usagestr, options); 2536 } 2537 ctx->argv += n; 2538 ctx->argc -= n; 2539 } 2540 2541 static int for_each_bisect_ref(struct ref_store *refs, each_ref_fn fn, 2542 void *cb_data, const char *term) 2543 { 2544 struct strbuf bisect_refs = STRBUF_INIT; 2545 int status; 2546 strbuf_addf(&bisect_refs, "refs/bisect/%s", term); 2547 status = refs_for_each_fullref_in(refs, bisect_refs.buf, fn, cb_data); 2548 strbuf_release(&bisect_refs); 2549 return status; 2550 } 2551 2552 static int for_each_bad_bisect_ref(struct ref_store *refs, each_ref_fn fn, void *cb_data) 2553 { 2554 return for_each_bisect_ref(refs, fn, cb_data, term_bad); 2555 } 2556 2557 static int for_each_good_bisect_ref(struct ref_store *refs, each_ref_fn fn, void *cb_data) 2558 { 2559 return for_each_bisect_ref(refs, fn, cb_data, term_good); 2560 } 2561 2562 static int handle_revision_pseudo_opt(struct rev_info *revs, 2563 const char **argv, int *flags) 2564 { 2565 const char *arg = argv[0]; 2566 const char *optarg; 2567 struct ref_store *refs; 2568 int argcount; 2569 2570 if (revs->repo != the_repository) { 2571 /* 2572 * We need some something like get_submodule_worktrees() 2573 * before we can go through all worktrees of a submodule, 2574 * .e.g with adding all HEADs from --all, which is not 2575 * supported right now, so stick to single worktree. 2576 */ 2577 if (!revs->single_worktree) 2578 BUG("--single-worktree cannot be used together with submodule"); 2579 } 2580 refs = get_main_ref_store(revs->repo); 2581 2582 /* 2583 * NOTE! 2584 * 2585 * Commands like "git shortlog" will not accept the options below 2586 * unless parse_revision_opt queues them (as opposed to erroring 2587 * out). 2588 * 2589 * When implementing your new pseudo-option, remember to 2590 * register it in the list at the top of handle_revision_opt. 2591 */ 2592 if (!strcmp(arg, "--all")) { 2593 handle_refs(refs, revs, *flags, refs_for_each_ref); 2594 handle_refs(refs, revs, *flags, refs_head_ref); 2595 if (!revs->single_worktree) { 2596 struct all_refs_cb cb; 2597 2598 init_all_refs_cb(&cb, revs, *flags); 2599 other_head_refs(handle_one_ref, &cb); 2600 } 2601 clear_ref_exclusion(&revs->ref_excludes); 2602 } else if (!strcmp(arg, "--branches")) { 2603 handle_refs(refs, revs, *flags, refs_for_each_branch_ref); 2604 clear_ref_exclusion(&revs->ref_excludes); 2605 } else if (!strcmp(arg, "--bisect")) { 2606 read_bisect_terms(&term_bad, &term_good); 2607 handle_refs(refs, revs, *flags, for_each_bad_bisect_ref); 2608 handle_refs(refs, revs, *flags ^ (UNINTERESTING | BOTTOM), 2609 for_each_good_bisect_ref); 2610 revs->bisect = 1; 2611 } else if (!strcmp(arg, "--tags")) { 2612 handle_refs(refs, revs, *flags, refs_for_each_tag_ref); 2613 clear_ref_exclusion(&revs->ref_excludes); 2614 } else if (!strcmp(arg, "--remotes")) { 2615 handle_refs(refs, revs, *flags, refs_for_each_remote_ref); 2616 clear_ref_exclusion(&revs->ref_excludes); 2617 } else if ((argcount = parse_long_opt("glob", argv, &optarg))) { 2618 struct all_refs_cb cb; 2619 init_all_refs_cb(&cb, revs, *flags); 2620 for_each_glob_ref(handle_one_ref, optarg, &cb); 2621 clear_ref_exclusion(&revs->ref_excludes); 2622 return argcount; 2623 } else if ((argcount = parse_long_opt("exclude", argv, &optarg))) { 2624 add_ref_exclusion(&revs->ref_excludes, optarg); 2625 return argcount; 2626 } else if (skip_prefix(arg, "--branches=", &optarg)) { 2627 struct all_refs_cb cb; 2628 init_all_refs_cb(&cb, revs, *flags); 2629 for_each_glob_ref_in(handle_one_ref, optarg, "refs/heads/", &cb); 2630 clear_ref_exclusion(&revs->ref_excludes); 2631 } else if (skip_prefix(arg, "--tags=", &optarg)) { 2632 struct all_refs_cb cb; 2633 init_all_refs_cb(&cb, revs, *flags); 2634 for_each_glob_ref_in(handle_one_ref, optarg, "refs/tags/", &cb); 2635 clear_ref_exclusion(&revs->ref_excludes); 2636 } else if (skip_prefix(arg, "--remotes=", &optarg)) { 2637 struct all_refs_cb cb; 2638 init_all_refs_cb(&cb, revs, *flags); 2639 for_each_glob_ref_in(handle_one_ref, optarg, "refs/remotes/", &cb); 2640 clear_ref_exclusion(&revs->ref_excludes); 2641 } else if (!strcmp(arg, "--reflog")) { 2642 add_reflogs_to_pending(revs, *flags); 2643 } else if (!strcmp(arg, "--indexed-objects")) { 2644 add_index_objects_to_pending(revs, *flags); 2645 } else if (!strcmp(arg, "--alternate-refs")) { 2646 add_alternate_refs_to_pending(revs, *flags); 2647 } else if (!strcmp(arg, "--not")) { 2648 *flags ^= UNINTERESTING | BOTTOM; 2649 } else if (!strcmp(arg, "--no-walk")) { 2650 revs->no_walk = 1; 2651 } else if (skip_prefix(arg, "--no-walk=", &optarg)) { 2652 /* 2653 * Detached form ("--no-walk X" as opposed to "--no-walk=X") 2654 * not allowed, since the argument is optional. 2655 */ 2656 revs->no_walk = 1; 2657 if (!strcmp(optarg, "sorted")) 2658 revs->unsorted_input = 0; 2659 else if (!strcmp(optarg, "unsorted")) 2660 revs->unsorted_input = 1; 2661 else 2662 return error("invalid argument to --no-walk"); 2663 } else if (!strcmp(arg, "--do-walk")) { 2664 revs->no_walk = 0; 2665 } else if (!strcmp(arg, "--single-worktree")) { 2666 revs->single_worktree = 1; 2667 } else { 2668 return 0; 2669 } 2670 2671 return 1; 2672 } 2673 2674 static void NORETURN diagnose_missing_default(const char *def) 2675 { 2676 int flags; 2677 const char *refname; 2678 2679 refname = resolve_ref_unsafe(def, 0, NULL, &flags); 2680 if (!refname || !(flags & REF_ISSYMREF) || (flags & REF_ISBROKEN)) 2681 die(_("your current branch appears to be broken")); 2682 2683 skip_prefix(refname, "refs/heads/", &refname); 2684 die(_("your current branch '%s' does not have any commits yet"), 2685 refname); 2686 } 2687 2688 /* 2689 * Parse revision information, filling in the "rev_info" structure, 2690 * and removing the used arguments from the argument list. 2691 * 2692 * Returns the number of arguments left that weren't recognized 2693 * (which are also moved to the head of the argument list) 2694 */ 2695 int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct setup_revision_opt *opt) 2696 { 2697 int i, flags, left, seen_dashdash, revarg_opt; 2698 struct strvec prune_data = STRVEC_INIT; 2699 int seen_end_of_options = 0; 2700 2701 /* First, search for "--" */ 2702 if (opt && opt->assume_dashdash) { 2703 seen_dashdash = 1; 2704 } else { 2705 seen_dashdash = 0; 2706 for (i = 1; i < argc; i++) { 2707 const char *arg = argv[i]; 2708 if (strcmp(arg, "--")) 2709 continue; 2710 argv[i] = NULL; 2711 argc = i; 2712 if (argv[i + 1]) 2713 strvec_pushv(&prune_data, argv + i + 1); 2714 seen_dashdash = 1; 2715 break; 2716 } 2717 } 2718 2719 /* Second, deal with arguments and options */ 2720 flags = 0; 2721 revarg_opt = opt ? opt->revarg_opt : 0; 2722 if (seen_dashdash) 2723 revarg_opt |= REVARG_CANNOT_BE_FILENAME; 2724 for (left = i = 1; i < argc; i++) { 2725 const char *arg = argv[i]; 2726 if (!seen_end_of_options && *arg == '-') { 2727 int opts; 2728 2729 opts = handle_revision_pseudo_opt( 2730 revs, argv + i, 2731 &flags); 2732 if (opts > 0) { 2733 i += opts - 1; 2734 continue; 2735 } 2736 2737 if (!strcmp(arg, "--stdin")) { 2738 if (revs->disable_stdin) { 2739 argv[left++] = arg; 2740 continue; 2741 } 2742 if (revs->read_from_stdin++) 2743 die("--stdin given twice?"); 2744 read_revisions_from_stdin(revs, &prune_data); 2745 continue; 2746 } 2747 2748 if (!strcmp(arg, "--end-of-options")) { 2749 seen_end_of_options = 1; 2750 continue; 2751 } 2752 2753 opts = handle_revision_opt(revs, argc - i, argv + i, 2754 &left, argv, opt); 2755 if (opts > 0) { 2756 i += opts - 1; 2757 continue; 2758 } 2759 if (opts < 0) 2760 exit(128); 2761 continue; 2762 } 2763 2764 2765 if (handle_revision_arg(arg, revs, flags, revarg_opt)) { 2766 int j; 2767 if (seen_dashdash || *arg == '^') 2768 die("bad revision '%s'", arg); 2769 2770 /* If we didn't have a "--": 2771 * (1) all filenames must exist; 2772 * (2) all rev-args must not be interpretable 2773 * as a valid filename. 2774 * but the latter we have checked in the main loop. 2775 */ 2776 for (j = i; j < argc; j++) 2777 verify_filename(revs->prefix, argv[j], j == i); 2778 2779 strvec_pushv(&prune_data, argv + i); 2780 break; 2781 } 2782 } 2783 2784 if (prune_data.nr) { 2785 /* 2786 * If we need to introduce the magic "a lone ':' means no 2787 * pathspec whatsoever", here is the place to do so. 2788 * 2789 * if (prune_data.nr == 1 && !strcmp(prune_data[0], ":")) { 2790 * prune_data.nr = 0; 2791 * prune_data.alloc = 0; 2792 * free(prune_data.path); 2793 * prune_data.path = NULL; 2794 * } else { 2795 * terminate prune_data.alloc with NULL and 2796 * call init_pathspec() to set revs->prune_data here. 2797 * } 2798 */ 2799 parse_pathspec(&revs->prune_data, 0, 0, 2800 revs->prefix, prune_data.v); 2801 } 2802 strvec_clear(&prune_data); 2803 2804 if (revs->def == NULL) 2805 revs->def = opt ? opt->def : NULL; 2806 if (opt && opt->tweak) 2807 opt->tweak(revs, opt); 2808 if (revs->show_merge) 2809 prepare_show_merge(revs); 2810 if (revs->def && !revs->pending.nr && !revs->rev_input_given) { 2811 struct object_id oid; 2812 struct object *object; 2813 struct object_context oc; 2814 if (get_oid_with_context(revs->repo, revs->def, 0, &oid, &oc)) 2815 diagnose_missing_default(revs->def); 2816 object = get_reference(revs, revs->def, &oid, 0); 2817 add_pending_object_with_mode(revs, object, revs->def, oc.mode); 2818 } 2819 2820 /* Did the user ask for any diff output? Run the diff! */ 2821 if (revs->diffopt.output_format & ~DIFF_FORMAT_NO_OUTPUT) 2822 revs->diff = 1; 2823 2824 /* Pickaxe, diff-filter and rename following need diffs */ 2825 if ((revs->diffopt.pickaxe_opts & DIFF_PICKAXE_KINDS_MASK) || 2826 revs->diffopt.filter || 2827 revs->diffopt.flags.follow_renames) 2828 revs->diff = 1; 2829 2830 if (revs->diffopt.objfind) 2831 revs->simplify_history = 0; 2832 2833 if (revs->line_level_traverse) { 2834 if (want_ancestry(revs)) 2835 revs->limited = 1; 2836 revs->topo_order = 1; 2837 } 2838 2839 if (revs->topo_order && !generation_numbers_enabled(the_repository)) 2840 revs->limited = 1; 2841 2842 if (revs->prune_data.nr) { 2843 copy_pathspec(&revs->pruning.pathspec, &revs->prune_data); 2844 /* Can't prune commits with rename following: the paths change.. */ 2845 if (!revs->diffopt.flags.follow_renames) 2846 revs->prune = 1; 2847 if (!revs->full_diff) 2848 copy_pathspec(&revs->diffopt.pathspec, 2849 &revs->prune_data); 2850 } 2851 2852 diff_merges_setup_revs(revs); 2853 2854 revs->diffopt.abbrev = revs->abbrev; 2855 2856 diff_setup_done(&revs->diffopt); 2857 2858 grep_commit_pattern_type(GREP_PATTERN_TYPE_UNSPECIFIED, 2859 &revs->grep_filter); 2860 if (!is_encoding_utf8(get_log_output_encoding())) 2861 revs->grep_filter.ignore_locale = 1; 2862 compile_grep_patterns(&revs->grep_filter); 2863 2864 if (revs->reverse && revs->reflog_info) 2865 die("cannot combine --reverse with --walk-reflogs"); 2866 if (revs->reflog_info && revs->limited) 2867 die("cannot combine --walk-reflogs with history-limiting options"); 2868 if (revs->rewrite_parents && revs->children.name) 2869 die("cannot combine --parents and --children"); 2870 2871 /* 2872 * Limitations on the graph functionality 2873 */ 2874 if (revs->reverse && revs->graph) 2875 die("cannot combine --reverse with --graph"); 2876 2877 if (revs->reflog_info && revs->graph) 2878 die("cannot combine --walk-reflogs with --graph"); 2879 if (revs->no_walk && revs->graph) 2880 die("cannot combine --no-walk with --graph"); 2881 if (!revs->reflog_info && revs->grep_filter.use_reflog_filter) 2882 die("cannot use --grep-reflog without --walk-reflogs"); 2883 2884 if (revs->line_level_traverse && 2885 (revs->diffopt.output_format & ~(DIFF_FORMAT_PATCH | DIFF_FORMAT_NO_OUTPUT))) 2886 die(_("-L does not yet support diff formats besides -p and -s")); 2887 2888 if (revs->expand_tabs_in_log < 0) 2889 revs->expand_tabs_in_log = revs->expand_tabs_in_log_default; 2890 2891 return left; 2892 } 2893 2894 static void add_child(struct rev_info *revs, struct commit *parent, struct commit *child) 2895 { 2896 struct commit_list *l = xcalloc(1, sizeof(*l)); 2897 2898 l->item = child; 2899 l->next = add_decoration(&revs->children, &parent->object, l); 2900 } 2901 2902 static int remove_duplicate_parents(struct rev_info *revs, struct commit *commit) 2903 { 2904 struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object); 2905 struct commit_list **pp, *p; 2906 int surviving_parents; 2907 2908 /* Examine existing parents while marking ones we have seen... */ 2909 pp = &commit->parents; 2910 surviving_parents = 0; 2911 while ((p = *pp) != NULL) { 2912 struct commit *parent = p->item; 2913 if (parent->object.flags & TMP_MARK) { 2914 *pp = p->next; 2915 if (ts) 2916 compact_treesame(revs, commit, surviving_parents); 2917 continue; 2918 } 2919 parent->object.flags |= TMP_MARK; 2920 surviving_parents++; 2921 pp = &p->next; 2922 } 2923 /* clear the temporary mark */ 2924 for (p = commit->parents; p; p = p->next) { 2925 p->item->object.flags &= ~TMP_MARK; 2926 } 2927 /* no update_treesame() - removing duplicates can't affect TREESAME */ 2928 return surviving_parents; 2929 } 2930 2931 struct merge_simplify_state { 2932 struct commit *simplified; 2933 }; 2934 2935 static struct merge_simplify_state *locate_simplify_state(struct rev_info *revs, struct commit *commit) 2936 { 2937 struct merge_simplify_state *st; 2938 2939 st = lookup_decoration(&revs->merge_simplification, &commit->object); 2940 if (!st) { 2941 CALLOC_ARRAY(st, 1); 2942 add_decoration(&revs->merge_simplification, &commit->object, st); 2943 } 2944 return st; 2945 } 2946 2947 static int mark_redundant_parents(struct commit *commit) 2948 { 2949 struct commit_list *h = reduce_heads(commit->parents); 2950 int i = 0, marked = 0; 2951 struct commit_list *po, *pn; 2952 2953 /* Want these for sanity-checking only */ 2954 int orig_cnt = commit_list_count(commit->parents); 2955 int cnt = commit_list_count(h); 2956 2957 /* 2958 * Not ready to remove items yet, just mark them for now, based 2959 * on the output of reduce_heads(). reduce_heads outputs the reduced 2960 * set in its original order, so this isn't too hard. 2961 */ 2962 po = commit->parents; 2963 pn = h; 2964 while (po) { 2965 if (pn && po->item == pn->item) { 2966 pn = pn->next; 2967 i++; 2968 } else { 2969 po->item->object.flags |= TMP_MARK; 2970 marked++; 2971 } 2972 po=po->next; 2973 } 2974 2975 if (i != cnt || cnt+marked != orig_cnt) 2976 die("mark_redundant_parents %d %d %d %d", orig_cnt, cnt, i, marked); 2977 2978 free_commit_list(h); 2979 2980 return marked; 2981 } 2982 2983 static int mark_treesame_root_parents(struct commit *commit) 2984 { 2985 struct commit_list *p; 2986 int marked = 0; 2987 2988 for (p = commit->parents; p; p = p->next) { 2989 struct commit *parent = p->item; 2990 if (!parent->parents && (parent->object.flags & TREESAME)) { 2991 parent->object.flags |= TMP_MARK; 2992 marked++; 2993 } 2994 } 2995 2996 return marked; 2997 } 2998 2999 /* 3000 * Awkward naming - this means one parent we are TREESAME to. 3001 * cf mark_treesame_root_parents: root parents that are TREESAME (to an 3002 * empty tree). Better name suggestions? 3003 */ 3004 static int leave_one_treesame_to_parent(struct rev_info *revs, struct commit *commit) 3005 { 3006 struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object); 3007 struct commit *unmarked = NULL, *marked = NULL; 3008 struct commit_list *p; 3009 unsigned n; 3010 3011 for (p = commit->parents, n = 0; p; p = p->next, n++) { 3012 if (ts->treesame[n]) { 3013 if (p->item->object.flags & TMP_MARK) { 3014 if (!marked) 3015 marked = p->item; 3016 } else { 3017 if (!unmarked) { 3018 unmarked = p->item; 3019 break; 3020 } 3021 } 3022 } 3023 } 3024 3025 /* 3026 * If we are TREESAME to a marked-for-deletion parent, but not to any 3027 * unmarked parents, unmark the first TREESAME parent. This is the 3028 * parent that the default simplify_history==1 scan would have followed, 3029 * and it doesn't make sense to omit that path when asking for a 3030 * simplified full history. Retaining it improves the chances of 3031 * understanding odd missed merges that took an old version of a file. 3032 * 3033 * Example: 3034 * 3035 * I--------*X A modified the file, but mainline merge X used 3036 * \ / "-s ours", so took the version from I. X is 3037 * `-*A--' TREESAME to I and !TREESAME to A. 3038 * 3039 * Default log from X would produce "I". Without this check, 3040 * --full-history --simplify-merges would produce "I-A-X", showing 3041 * the merge commit X and that it changed A, but not making clear that 3042 * it had just taken the I version. With this check, the topology above 3043 * is retained. 3044 * 3045 * Note that it is possible that the simplification chooses a different 3046 * TREESAME parent from the default, in which case this test doesn't 3047 * activate, and we _do_ drop the default parent. Example: 3048 * 3049 * I------X A modified the file, but it was reverted in B, 3050 * \ / meaning mainline merge X is TREESAME to both 3051 * *A-*B parents. 3052 * 3053 * Default log would produce "I" by following the first parent; 3054 * --full-history --simplify-merges will produce "I-A-B". But this is a 3055 * reasonable result - it presents a logical full history leading from 3056 * I to X, and X is not an important merge. 3057 */ 3058 if (!unmarked && marked) { 3059 marked->object.flags &= ~TMP_MARK; 3060 return 1; 3061 } 3062 3063 return 0; 3064 } 3065 3066 static int remove_marked_parents(struct rev_info *revs, struct commit *commit) 3067 { 3068 struct commit_list **pp, *p; 3069 int nth_parent, removed = 0; 3070 3071 pp = &commit->parents; 3072 nth_parent = 0; 3073 while ((p = *pp) != NULL) { 3074 struct commit *parent = p->item; 3075 if (parent->object.flags & TMP_MARK) { 3076 parent->object.flags &= ~TMP_MARK; 3077 *pp = p->next; 3078 free(p); 3079 removed++; 3080 compact_treesame(revs, commit, nth_parent); 3081 continue; 3082 } 3083 pp = &p->next; 3084 nth_parent++; 3085 } 3086 3087 /* Removing parents can only increase TREESAMEness */ 3088 if (removed && !(commit->object.flags & TREESAME)) 3089 update_treesame(revs, commit); 3090 3091 return nth_parent; 3092 } 3093 3094 static struct commit_list **simplify_one(struct rev_info *revs, struct commit *commit, struct commit_list **tail) 3095 { 3096 struct commit_list *p; 3097 struct commit *parent; 3098 struct merge_simplify_state *st, *pst; 3099 int cnt; 3100 3101 st = locate_simplify_state(revs, commit); 3102 3103 /* 3104 * Have we handled this one? 3105 */ 3106 if (st->simplified) 3107 return tail; 3108 3109 /* 3110 * An UNINTERESTING commit simplifies to itself, so does a 3111 * root commit. We do not rewrite parents of such commit 3112 * anyway. 3113 */ 3114 if ((commit->object.flags & UNINTERESTING) || !commit->parents) { 3115 st->simplified = commit; 3116 return tail; 3117 } 3118 3119 /* 3120 * Do we know what commit all of our parents that matter 3121 * should be rewritten to? Otherwise we are not ready to 3122 * rewrite this one yet. 3123 */ 3124 for (cnt = 0, p = commit->parents; p; p = p->next) { 3125 pst = locate_simplify_state(revs, p->item); 3126 if (!pst->simplified) { 3127 tail = &commit_list_insert(p->item, tail)->next; 3128 cnt++; 3129 } 3130 if (revs->first_parent_only) 3131 break; 3132 } 3133 if (cnt) { 3134 tail = &commit_list_insert(commit, tail)->next; 3135 return tail; 3136 } 3137 3138 /* 3139 * Rewrite our list of parents. Note that this cannot 3140 * affect our TREESAME flags in any way - a commit is 3141 * always TREESAME to its simplification. 3142 */ 3143 for (p = commit->parents; p; p = p->next) { 3144 pst = locate_simplify_state(revs, p->item); 3145 p->item = pst->simplified; 3146 if (revs->first_parent_only) 3147 break; 3148 } 3149 3150 if (revs->first_parent_only) 3151 cnt = 1; 3152 else 3153 cnt = remove_duplicate_parents(revs, commit); 3154 3155 /* 3156 * It is possible that we are a merge and one side branch 3157 * does not have any commit that touches the given paths; 3158 * in such a case, the immediate parent from that branch 3159 * will be rewritten to be the merge base. 3160 * 3161 * o----X X: the commit we are looking at; 3162 * / / o: a commit that touches the paths; 3163 * ---o----' 3164 * 3165 * Further, a merge of an independent branch that doesn't 3166 * touch the path will reduce to a treesame root parent: 3167 * 3168 * ----o----X X: the commit we are looking at; 3169 * / o: a commit that touches the paths; 3170 * r r: a root commit not touching the paths 3171 * 3172 * Detect and simplify both cases. 3173 */ 3174 if (1 < cnt) { 3175 int marked = mark_redundant_parents(commit); 3176 marked += mark_treesame_root_parents(commit); 3177 if (marked) 3178 marked -= leave_one_treesame_to_parent(revs, commit); 3179 if (marked) 3180 cnt = remove_marked_parents(revs, commit); 3181 } 3182 3183 /* 3184 * A commit simplifies to itself if it is a root, if it is 3185 * UNINTERESTING, if it touches the given paths, or if it is a 3186 * merge and its parents don't simplify to one relevant commit 3187 * (the first two cases are already handled at the beginning of 3188 * this function). 3189 * 3190 * Otherwise, it simplifies to what its sole relevant parent 3191 * simplifies to. 3192 */ 3193 if (!cnt || 3194 (commit->object.flags & UNINTERESTING) || 3195 !(commit->object.flags & TREESAME) || 3196 (parent = one_relevant_parent(revs, commit->parents)) == NULL || 3197 (revs->show_pulls && (commit->object.flags & PULL_MERGE))) 3198 st->simplified = commit; 3199 else { 3200 pst = locate_simplify_state(revs, parent); 3201 st->simplified = pst->simplified; 3202 } 3203 return tail; 3204 } 3205 3206 static void simplify_merges(struct rev_info *revs) 3207 { 3208 struct commit_list *list, *next; 3209 struct commit_list *yet_to_do, **tail; 3210 struct commit *commit; 3211 3212 if (!revs->prune) 3213 return; 3214 3215 /* feed the list reversed */ 3216 yet_to_do = NULL; 3217 for (list = revs->commits; list; list = next) { 3218 commit = list->item; 3219 next = list->next; 3220 /* 3221 * Do not free(list) here yet; the original list 3222 * is used later in this function. 3223 */ 3224 commit_list_insert(commit, &yet_to_do); 3225 } 3226 while (yet_to_do) { 3227 list = yet_to_do; 3228 yet_to_do = NULL; 3229 tail = &yet_to_do; 3230 while (list) { 3231 commit = pop_commit(&list); 3232 tail = simplify_one(revs, commit, tail); 3233 } 3234 } 3235 3236 /* clean up the result, removing the simplified ones */ 3237 list = revs->commits; 3238 revs->commits = NULL; 3239 tail = &revs->commits; 3240 while (list) { 3241 struct merge_simplify_state *st; 3242 3243 commit = pop_commit(&list); 3244 st = locate_simplify_state(revs, commit); 3245 if (st->simplified == commit) 3246 tail = &commit_list_insert(commit, tail)->next; 3247 } 3248 } 3249 3250 static void set_children(struct rev_info *revs) 3251 { 3252 struct commit_list *l; 3253 for (l = revs->commits; l; l = l->next) { 3254 struct commit *commit = l->item; 3255 struct commit_list *p; 3256 3257 for (p = commit->parents; p; p = p->next) 3258 add_child(revs, p->item, commit); 3259 } 3260 } 3261 3262 void reset_revision_walk(void) 3263 { 3264 clear_object_flags(SEEN | ADDED | SHOWN | TOPO_WALK_EXPLORED | TOPO_WALK_INDEGREE); 3265 } 3266 3267 static int mark_uninteresting(const struct object_id *oid, 3268 struct packed_git *pack, 3269 uint32_t pos, 3270 void *cb) 3271 { 3272 struct rev_info *revs = cb; 3273 struct object *o = lookup_unknown_object(revs->repo, oid); 3274 o->flags |= UNINTERESTING | SEEN; 3275 return 0; 3276 } 3277 3278 define_commit_slab(indegree_slab, int); 3279 define_commit_slab(author_date_slab, timestamp_t); 3280 3281 struct topo_walk_info { 3282 timestamp_t min_generation; 3283 struct prio_queue explore_queue; 3284 struct prio_queue indegree_queue; 3285 struct prio_queue topo_queue; 3286 struct indegree_slab indegree; 3287 struct author_date_slab author_date; 3288 }; 3289 3290 static int topo_walk_atexit_registered; 3291 static unsigned int count_explore_walked; 3292 static unsigned int count_indegree_walked; 3293 static unsigned int count_topo_walked; 3294 3295 static void trace2_topo_walk_statistics_atexit(void) 3296 { 3297 struct json_writer jw = JSON_WRITER_INIT; 3298 3299 jw_object_begin(&jw, 0); 3300 jw_object_intmax(&jw, "count_explore_walked", count_explore_walked); 3301 jw_object_intmax(&jw, "count_indegree_walked", count_indegree_walked); 3302 jw_object_intmax(&jw, "count_topo_walked", count_topo_walked); 3303 jw_end(&jw); 3304 3305 trace2_data_json("topo_walk", the_repository, "statistics", &jw); 3306 3307 jw_release(&jw); 3308 } 3309 3310 static inline void test_flag_and_insert(struct prio_queue *q, struct commit *c, int flag) 3311 { 3312 if (c->object.flags & flag) 3313 return; 3314 3315 c->object.flags |= flag; 3316 prio_queue_put(q, c); 3317 } 3318 3319 static void explore_walk_step(struct rev_info *revs) 3320 { 3321 struct topo_walk_info *info = revs->topo_walk_info; 3322 struct commit_list *p; 3323 struct commit *c = prio_queue_get(&info->explore_queue); 3324 3325 if (!c) 3326 return; 3327 3328 if (repo_parse_commit_gently(revs->repo, c, 1) < 0) 3329 return; 3330 3331 count_explore_walked++; 3332 3333 if (revs->sort_order == REV_SORT_BY_AUTHOR_DATE) 3334 record_author_date(&info->author_date, c); 3335 3336 if (revs->max_age != -1 && (c->date < revs->max_age)) 3337 c->object.flags |= UNINTERESTING; 3338 3339 if (process_parents(revs, c, NULL, NULL) < 0) 3340 return; 3341 3342 if (c->object.flags & UNINTERESTING) 3343 mark_parents_uninteresting(c); 3344 3345 for (p = c->parents; p; p = p->next) 3346 test_flag_and_insert(&info->explore_queue, p->item, TOPO_WALK_EXPLORED); 3347 } 3348 3349 static void explore_to_depth(struct rev_info *revs, 3350 timestamp_t gen_cutoff) 3351 { 3352 struct topo_walk_info *info = revs->topo_walk_info; 3353 struct commit *c; 3354 while ((c = prio_queue_peek(&info->explore_queue)) && 3355 commit_graph_generation(c) >= gen_cutoff) 3356 explore_walk_step(revs); 3357 } 3358 3359 static void indegree_walk_step(struct rev_info *revs) 3360 { 3361 struct commit_list *p; 3362 struct topo_walk_info *info = revs->topo_walk_info; 3363 struct commit *c = prio_queue_get(&info->indegree_queue); 3364 3365 if (!c) 3366 return; 3367 3368 if (repo_parse_commit_gently(revs->repo, c, 1) < 0) 3369 return; 3370 3371 count_indegree_walked++; 3372 3373 explore_to_depth(revs, commit_graph_generation(c)); 3374 3375 for (p = c->parents; p; p = p->next) { 3376 struct commit *parent = p->item; 3377 int *pi = indegree_slab_at(&info->indegree, parent); 3378 3379 if (repo_parse_commit_gently(revs->repo, parent, 1) < 0) 3380 return; 3381 3382 if (*pi) 3383 (*pi)++; 3384 else 3385 *pi = 2; 3386 3387 test_flag_and_insert(&info->indegree_queue, parent, TOPO_WALK_INDEGREE); 3388 3389 if (revs->first_parent_only) 3390 return; 3391 } 3392 } 3393 3394 static void compute_indegrees_to_depth(struct rev_info *revs, 3395 timestamp_t gen_cutoff) 3396 { 3397 struct topo_walk_info *info = revs->topo_walk_info; 3398 struct commit *c; 3399 while ((c = prio_queue_peek(&info->indegree_queue)) && 3400 commit_graph_generation(c) >= gen_cutoff) 3401 indegree_walk_step(revs); 3402 } 3403 3404 static void reset_topo_walk(struct rev_info *revs) 3405 { 3406 struct topo_walk_info *info = revs->topo_walk_info; 3407 3408 clear_prio_queue(&info->explore_queue); 3409 clear_prio_queue(&info->indegree_queue); 3410 clear_prio_queue(&info->topo_queue); 3411 clear_indegree_slab(&info->indegree); 3412 clear_author_date_slab(&info->author_date); 3413 3414 FREE_AND_NULL(revs->topo_walk_info); 3415 } 3416 3417 static void init_topo_walk(struct rev_info *revs) 3418 { 3419 struct topo_walk_info *info; 3420 struct commit_list *list; 3421 if (revs->topo_walk_info) 3422 reset_topo_walk(revs); 3423 3424 revs->topo_walk_info = xmalloc(sizeof(struct topo_walk_info)); 3425 info = revs->topo_walk_info; 3426 memset(info, 0, sizeof(struct topo_walk_info)); 3427 3428 init_indegree_slab(&info->indegree); 3429 memset(&info->explore_queue, 0, sizeof(info->explore_queue)); 3430 memset(&info->indegree_queue, 0, sizeof(info->indegree_queue)); 3431 memset(&info->topo_queue, 0, sizeof(info->topo_queue)); 3432 3433 switch (revs->sort_order) { 3434 default: /* REV_SORT_IN_GRAPH_ORDER */ 3435 info->topo_queue.compare = NULL; 3436 break; 3437 case REV_SORT_BY_COMMIT_DATE: 3438 info->topo_queue.compare = compare_commits_by_commit_date; 3439 break; 3440 case REV_SORT_BY_AUTHOR_DATE: 3441 init_author_date_slab(&info->author_date); 3442 info->topo_queue.compare = compare_commits_by_author_date; 3443 info->topo_queue.cb_data = &info->author_date; 3444 break; 3445 } 3446 3447 info->explore_queue.compare = compare_commits_by_gen_then_commit_date; 3448 info->indegree_queue.compare = compare_commits_by_gen_then_commit_date; 3449 3450 info->min_generation = GENERATION_NUMBER_INFINITY; 3451 for (list = revs->commits; list; list = list->next) { 3452 struct commit *c = list->item; 3453 timestamp_t generation; 3454 3455 if (repo_parse_commit_gently(revs->repo, c, 1)) 3456 continue; 3457 3458 test_flag_and_insert(&info->explore_queue, c, TOPO_WALK_EXPLORED); 3459 test_flag_and_insert(&info->indegree_queue, c, TOPO_WALK_INDEGREE); 3460 3461 generation = commit_graph_generation(c); 3462 if (generation < info->min_generation) 3463 info->min_generation = generation; 3464 3465 *(indegree_slab_at(&info->indegree, c)) = 1; 3466 3467 if (revs->sort_order == REV_SORT_BY_AUTHOR_DATE) 3468 record_author_date(&info->author_date, c); 3469 } 3470 compute_indegrees_to_depth(revs, info->min_generation); 3471 3472 for (list = revs->commits; list; list = list->next) { 3473 struct commit *c = list->item; 3474 3475 if (*(indegree_slab_at(&info->indegree, c)) == 1) 3476 prio_queue_put(&info->topo_queue, c); 3477 } 3478 3479 /* 3480 * This is unfortunate; the initial tips need to be shown 3481 * in the order given from the revision traversal machinery. 3482 */ 3483 if (revs->sort_order == REV_SORT_IN_GRAPH_ORDER) 3484 prio_queue_reverse(&info->topo_queue); 3485 3486 if (trace2_is_enabled() && !topo_walk_atexit_registered) { 3487 atexit(trace2_topo_walk_statistics_atexit); 3488 topo_walk_atexit_registered = 1; 3489 } 3490 } 3491 3492 static struct commit *next_topo_commit(struct rev_info *revs) 3493 { 3494 struct commit *c; 3495 struct topo_walk_info *info = revs->topo_walk_info; 3496 3497 /* pop next off of topo_queue */ 3498 c = prio_queue_get(&info->topo_queue); 3499 3500 if (c) 3501 *(indegree_slab_at(&info->indegree, c)) = 0; 3502 3503 return c; 3504 } 3505 3506 static void expand_topo_walk(struct rev_info *revs, struct commit *commit) 3507 { 3508 struct commit_list *p; 3509 struct topo_walk_info *info = revs->topo_walk_info; 3510 if (process_parents(revs, commit, NULL, NULL) < 0) { 3511 if (!revs->ignore_missing_links) 3512 die("Failed to traverse parents of commit %s", 3513 oid_to_hex(&commit->object.oid)); 3514 } 3515 3516 count_topo_walked++; 3517 3518 for (p = commit->parents; p; p = p->next) { 3519 struct commit *parent = p->item; 3520 int *pi; 3521 timestamp_t generation; 3522 3523 if (parent->object.flags & UNINTERESTING) 3524 continue; 3525 3526 if (repo_parse_commit_gently(revs->repo, parent, 1) < 0) 3527 continue; 3528 3529 generation = commit_graph_generation(parent); 3530 if (generation < info->min_generation) { 3531 info->min_generation = generation; 3532 compute_indegrees_to_depth(revs, info->min_generation); 3533 } 3534 3535 pi = indegree_slab_at(&info->indegree, parent); 3536 3537 (*pi)--; 3538 if (*pi == 1) 3539 prio_queue_put(&info->topo_queue, parent); 3540 3541 if (revs->first_parent_only) 3542 return; 3543 } 3544 } 3545 3546 int prepare_revision_walk(struct rev_info *revs) 3547 { 3548 int i; 3549 struct object_array old_pending; 3550 struct commit_list **next = &revs->commits; 3551 3552 memcpy(&old_pending, &revs->pending, sizeof(old_pending)); 3553 revs->pending.nr = 0; 3554 revs->pending.alloc = 0; 3555 revs->pending.objects = NULL; 3556 for (i = 0; i < old_pending.nr; i++) { 3557 struct object_array_entry *e = old_pending.objects + i; 3558 struct commit *commit = handle_commit(revs, e); 3559 if (commit) { 3560 if (!(commit->object.flags & SEEN)) { 3561 commit->object.flags |= SEEN; 3562 next = commit_list_append(commit, next); 3563 } 3564 } 3565 } 3566 object_array_clear(&old_pending); 3567 3568 /* Signal whether we need per-parent treesame decoration */ 3569 if (revs->simplify_merges || 3570 (revs->limited && limiting_can_increase_treesame(revs))) 3571 revs->treesame.name = "treesame"; 3572 3573 if (revs->exclude_promisor_objects) { 3574 for_each_packed_object(mark_uninteresting, revs, 3575 FOR_EACH_OBJECT_PROMISOR_ONLY); 3576 } 3577 3578 if (!revs->reflog_info) 3579 prepare_to_use_bloom_filter(revs); 3580 if (!revs->unsorted_input) 3581 commit_list_sort_by_date(&revs->commits); 3582 if (revs->no_walk) 3583 return 0; 3584 if (revs->limited) { 3585 if (limit_list(revs) < 0) 3586 return -1; 3587 if (revs->topo_order) 3588 sort_in_topological_order(&revs->commits, revs->sort_order); 3589 } else if (revs->topo_order) 3590 init_topo_walk(revs); 3591 if (revs->line_level_traverse && want_ancestry(revs)) 3592 /* 3593 * At the moment we can only do line-level log with parent 3594 * rewriting by performing this expensive pre-filtering step. 3595 * If parent rewriting is not requested, then we rather 3596 * perform the line-level log filtering during the regular 3597 * history traversal. 3598 */ 3599 line_log_filter(revs); 3600 if (revs->simplify_merges) 3601 simplify_merges(revs); 3602 if (revs->children.name) 3603 set_children(revs); 3604 3605 return 0; 3606 } 3607 3608 static enum rewrite_result rewrite_one_1(struct rev_info *revs, 3609 struct commit **pp, 3610 struct prio_queue *queue) 3611 { 3612 for (;;) { 3613 struct commit *p = *pp; 3614 if (!revs->limited) 3615 if (process_parents(revs, p, NULL, queue) < 0) 3616 return rewrite_one_error; 3617 if (p->object.flags & UNINTERESTING) 3618 return rewrite_one_ok; 3619 if (!(p->object.flags & TREESAME)) 3620 return rewrite_one_ok; 3621 if (!p->parents) 3622 return rewrite_one_noparents; 3623 if ((p = one_relevant_parent(revs, p->parents)) == NULL) 3624 return rewrite_one_ok; 3625 *pp = p; 3626 } 3627 } 3628 3629 static void merge_queue_into_list(struct prio_queue *q, struct commit_list **list) 3630 { 3631 while (q->nr) { 3632 struct commit *item = prio_queue_peek(q); 3633 struct commit_list *p = *list; 3634 3635 if (p && p->item->date >= item->date) 3636 list = &p->next; 3637 else { 3638 p = commit_list_insert(item, list); 3639 list = &p->next; /* skip newly added item */ 3640 prio_queue_get(q); /* pop item */ 3641 } 3642 } 3643 } 3644 3645 static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp) 3646 { 3647 struct prio_queue queue = { compare_commits_by_commit_date }; 3648 enum rewrite_result ret = rewrite_one_1(revs, pp, &queue); 3649 merge_queue_into_list(&queue, &revs->commits); 3650 clear_prio_queue(&queue); 3651 return ret; 3652 } 3653 3654 int rewrite_parents(struct rev_info *revs, struct commit *commit, 3655 rewrite_parent_fn_t rewrite_parent) 3656 { 3657 struct commit_list **pp = &commit->parents; 3658 while (*pp) { 3659 struct commit_list *parent = *pp; 3660 switch (rewrite_parent(revs, &parent->item)) { 3661 case rewrite_one_ok: 3662 break; 3663 case rewrite_one_noparents: 3664 *pp = parent->next; 3665 continue; 3666 case rewrite_one_error: 3667 return -1; 3668 } 3669 pp = &parent->next; 3670 } 3671 remove_duplicate_parents(revs, commit); 3672 return 0; 3673 } 3674 3675 static int commit_rewrite_person(struct strbuf *buf, const char *what, struct string_list *mailmap) 3676 { 3677 char *person, *endp; 3678 size_t len, namelen, maillen; 3679 const char *name; 3680 const char *mail; 3681 struct ident_split ident; 3682 3683 person = strstr(buf->buf, what); 3684 if (!person) 3685 return 0; 3686 3687 person += strlen(what); 3688 endp = strchr(person, '\n'); 3689 if (!endp) 3690 return 0; 3691 3692 len = endp - person; 3693 3694 if (split_ident_line(&ident, person, len)) 3695 return 0; 3696 3697 mail = ident.mail_begin; 3698 maillen = ident.mail_end - ident.mail_begin; 3699 name = ident.name_begin; 3700 namelen = ident.name_end - ident.name_begin; 3701 3702 if (map_user(mailmap, &mail, &maillen, &name, &namelen)) { 3703 struct strbuf namemail = STRBUF_INIT; 3704 3705 strbuf_addf(&namemail, "%.*s <%.*s>", 3706 (int)namelen, name, (int)maillen, mail); 3707 3708 strbuf_splice(buf, ident.name_begin - buf->buf, 3709 ident.mail_end - ident.name_begin + 1, 3710 namemail.buf, namemail.len); 3711 3712 strbuf_release(&namemail); 3713 3714 return 1; 3715 } 3716 3717 return 0; 3718 } 3719 3720 static int commit_match(struct commit *commit, struct rev_info *opt) 3721 { 3722 int retval; 3723 const char *encoding; 3724 const char *message; 3725 struct strbuf buf = STRBUF_INIT; 3726 3727 if (!opt->grep_filter.pattern_list && !opt->grep_filter.header_list) 3728 return 1; 3729 3730 /* Prepend "fake" headers as needed */ 3731 if (opt->grep_filter.use_reflog_filter) { 3732 strbuf_addstr(&buf, "reflog "); 3733 get_reflog_message(&buf, opt->reflog_info); 3734 strbuf_addch(&buf, '\n'); 3735 } 3736 3737 /* 3738 * We grep in the user's output encoding, under the assumption that it 3739 * is the encoding they are most likely to write their grep pattern 3740 * for. In addition, it means we will match the "notes" encoding below, 3741 * so we will not end up with a buffer that has two different encodings 3742 * in it. 3743 */ 3744 encoding = get_log_output_encoding(); 3745 message = logmsg_reencode(commit, NULL, encoding); 3746 3747 /* Copy the commit to temporary if we are using "fake" headers */ 3748 if (buf.len) 3749 strbuf_addstr(&buf, message); 3750 3751 if (opt->grep_filter.header_list && opt->mailmap) { 3752 if (!buf.len) 3753 strbuf_addstr(&buf, message); 3754 3755 commit_rewrite_person(&buf, "\nauthor ", opt->mailmap); 3756 commit_rewrite_person(&buf, "\ncommitter ", opt->mailmap); 3757 } 3758 3759 /* Append "fake" message parts as needed */ 3760 if (opt->show_notes) { 3761 if (!buf.len) 3762 strbuf_addstr(&buf, message); 3763 format_display_notes(&commit->object.oid, &buf, encoding, 1); 3764 } 3765 3766 /* 3767 * Find either in the original commit message, or in the temporary. 3768 * Note that we cast away the constness of "message" here. It is 3769 * const because it may come from the cached commit buffer. That's OK, 3770 * because we know that it is modifiable heap memory, and that while 3771 * grep_buffer may modify it for speed, it will restore any 3772 * changes before returning. 3773 */ 3774 if (buf.len) 3775 retval = grep_buffer(&opt->grep_filter, buf.buf, buf.len); 3776 else 3777 retval = grep_buffer(&opt->grep_filter, 3778 (char *)message, strlen(message)); 3779 strbuf_release(&buf); 3780 unuse_commit_buffer(commit, message); 3781 return opt->invert_grep ? !retval : retval; 3782 } 3783 3784 static inline int want_ancestry(const struct rev_info *revs) 3785 { 3786 return (revs->rewrite_parents || revs->children.name); 3787 } 3788 3789 /* 3790 * Return a timestamp to be used for --since/--until comparisons for this 3791 * commit, based on the revision options. 3792 */ 3793 static timestamp_t comparison_date(const struct rev_info *revs, 3794 struct commit *commit) 3795 { 3796 return revs->reflog_info ? 3797 get_reflog_timestamp(revs->reflog_info) : 3798 commit->date; 3799 } 3800 3801 enum commit_action get_commit_action(struct rev_info *revs, struct commit *commit) 3802 { 3803 if (commit->object.flags & SHOWN) 3804 return commit_ignore; 3805 if (revs->unpacked && has_object_pack(&commit->object.oid)) 3806 return commit_ignore; 3807 if (revs->no_kept_objects) { 3808 if (has_object_kept_pack(&commit->object.oid, 3809 revs->keep_pack_cache_flags)) 3810 return commit_ignore; 3811 } 3812 if (commit->object.flags & UNINTERESTING) 3813 return commit_ignore; 3814 if (revs->line_level_traverse && !want_ancestry(revs)) { 3815 /* 3816 * In case of line-level log with parent rewriting 3817 * prepare_revision_walk() already took care of all line-level 3818 * log filtering, and there is nothing left to do here. 3819 * 3820 * If parent rewriting was not requested, then this is the 3821 * place to perform the line-level log filtering. Notably, 3822 * this check, though expensive, must come before the other, 3823 * cheaper filtering conditions, because the tracked line 3824 * ranges must be adjusted even when the commit will end up 3825 * being ignored based on other conditions. 3826 */ 3827 if (!line_log_process_ranges_arbitrary_commit(revs, commit)) 3828 return commit_ignore; 3829 } 3830 if (revs->min_age != -1 && 3831 comparison_date(revs, commit) > revs->min_age) 3832 return commit_ignore; 3833 if (revs->min_parents || (revs->max_parents >= 0)) { 3834 int n = commit_list_count(commit->parents); 3835 if ((n < revs->min_parents) || 3836 ((revs->max_parents >= 0) && (n > revs->max_parents))) 3837 return commit_ignore; 3838 } 3839 if (!commit_match(commit, revs)) 3840 return commit_ignore; 3841 if (revs->prune && revs->dense) { 3842 /* Commit without changes? */ 3843 if (commit->object.flags & TREESAME) { 3844 int n; 3845 struct commit_list *p; 3846 /* drop merges unless we want parenthood */ 3847 if (!want_ancestry(revs)) 3848 return commit_ignore; 3849 3850 if (revs->show_pulls && (commit->object.flags & PULL_MERGE)) 3851 return commit_show; 3852 3853 /* 3854 * If we want ancestry, then need to keep any merges 3855 * between relevant commits to tie together topology. 3856 * For consistency with TREESAME and simplification 3857 * use "relevant" here rather than just INTERESTING, 3858 * to treat bottom commit(s) as part of the topology. 3859 */ 3860 for (n = 0, p = commit->parents; p; p = p->next) 3861 if (relevant_commit(p->item)) 3862 if (++n >= 2) 3863 return commit_show; 3864 return commit_ignore; 3865 } 3866 } 3867 return commit_show; 3868 } 3869 3870 define_commit_slab(saved_parents, struct commit_list *); 3871 3872 #define EMPTY_PARENT_LIST ((struct commit_list *)-1) 3873 3874 /* 3875 * You may only call save_parents() once per commit (this is checked 3876 * for non-root commits). 3877 */ 3878 static void save_parents(struct rev_info *revs, struct commit *commit) 3879 { 3880 struct commit_list **pp; 3881 3882 if (!revs->saved_parents_slab) { 3883 revs->saved_parents_slab = xmalloc(sizeof(struct saved_parents)); 3884 init_saved_parents(revs->saved_parents_slab); 3885 } 3886 3887 pp = saved_parents_at(revs->saved_parents_slab, commit); 3888 3889 /* 3890 * When walking with reflogs, we may visit the same commit 3891 * several times: once for each appearance in the reflog. 3892 * 3893 * In this case, save_parents() will be called multiple times. 3894 * We want to keep only the first set of parents. We need to 3895 * store a sentinel value for an empty (i.e., NULL) parent 3896 * list to distinguish it from a not-yet-saved list, however. 3897 */ 3898 if (*pp) 3899 return; 3900 if (commit->parents) 3901 *pp = copy_commit_list(commit->parents); 3902 else 3903 *pp = EMPTY_PARENT_LIST; 3904 } 3905 3906 static void free_saved_parents(struct rev_info *revs) 3907 { 3908 if (revs->saved_parents_slab) 3909 clear_saved_parents(revs->saved_parents_slab); 3910 } 3911 3912 struct commit_list *get_saved_parents(struct rev_info *revs, const struct commit *commit) 3913 { 3914 struct commit_list *parents; 3915 3916 if (!revs->saved_parents_slab) 3917 return commit->parents; 3918 3919 parents = *saved_parents_at(revs->saved_parents_slab, commit); 3920 if (parents == EMPTY_PARENT_LIST) 3921 return NULL; 3922 return parents; 3923 } 3924 3925 enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit) 3926 { 3927 enum commit_action action = get_commit_action(revs, commit); 3928 3929 if (action == commit_show && 3930 revs->prune && revs->dense && want_ancestry(revs)) { 3931 /* 3932 * --full-diff on simplified parents is no good: it 3933 * will show spurious changes from the commits that 3934 * were elided. So we save the parents on the side 3935 * when --full-diff is in effect. 3936 */ 3937 if (revs->full_diff) 3938 save_parents(revs, commit); 3939 if (rewrite_parents(revs, commit, rewrite_one) < 0) 3940 return commit_error; 3941 } 3942 return action; 3943 } 3944 3945 static void track_linear(struct rev_info *revs, struct commit *commit) 3946 { 3947 if (revs->track_first_time) { 3948 revs->linear = 1; 3949 revs->track_first_time = 0; 3950 } else { 3951 struct commit_list *p; 3952 for (p = revs->previous_parents; p; p = p->next) 3953 if (p->item == NULL || /* first commit */ 3954 oideq(&p->item->object.oid, &commit->object.oid)) 3955 break; 3956 revs->linear = p != NULL; 3957 } 3958 if (revs->reverse) { 3959 if (revs->linear) 3960 commit->object.flags |= TRACK_LINEAR; 3961 } 3962 free_commit_list(revs->previous_parents); 3963 revs->previous_parents = copy_commit_list(commit->parents); 3964 } 3965 3966 static struct commit *get_revision_1(struct rev_info *revs) 3967 { 3968 while (1) { 3969 struct commit *commit; 3970 3971 if (revs->reflog_info) 3972 commit = next_reflog_entry(revs->reflog_info); 3973 else if (revs->topo_walk_info) 3974 commit = next_topo_commit(revs); 3975 else 3976 commit = pop_commit(&revs->commits); 3977 3978 if (!commit) 3979 return NULL; 3980 3981 if (revs->reflog_info) 3982 commit->object.flags &= ~(ADDED | SEEN | SHOWN); 3983 3984 /* 3985 * If we haven't done the list limiting, we need to look at 3986 * the parents here. We also need to do the date-based limiting 3987 * that we'd otherwise have done in limit_list(). 3988 */ 3989 if (!revs->limited) { 3990 if (revs->max_age != -1 && 3991 comparison_date(revs, commit) < revs->max_age) 3992 continue; 3993 3994 if (revs->reflog_info) 3995 try_to_simplify_commit(revs, commit); 3996 else if (revs->topo_walk_info) 3997 expand_topo_walk(revs, commit); 3998 else if (process_parents(revs, commit, &revs->commits, NULL) < 0) { 3999 if (!revs->ignore_missing_links) 4000 die("Failed to traverse parents of commit %s", 4001 oid_to_hex(&commit->object.oid)); 4002 } 4003 } 4004 4005 switch (simplify_commit(revs, commit)) { 4006 case commit_ignore: 4007 continue; 4008 case commit_error: 4009 die("Failed to simplify parents of commit %s", 4010 oid_to_hex(&commit->object.oid)); 4011 default: 4012 if (revs->track_linear) 4013 track_linear(revs, commit); 4014 return commit; 4015 } 4016 } 4017 } 4018 4019 /* 4020 * Return true for entries that have not yet been shown. (This is an 4021 * object_array_each_func_t.) 4022 */ 4023 static int entry_unshown(struct object_array_entry *entry, void *cb_data_unused) 4024 { 4025 return !(entry->item->flags & SHOWN); 4026 } 4027 4028 /* 4029 * If array is on the verge of a realloc, garbage-collect any entries 4030 * that have already been shown to try to free up some space. 4031 */ 4032 static void gc_boundary(struct object_array *array) 4033 { 4034 if (array->nr == array->alloc) 4035 object_array_filter(array, entry_unshown, NULL); 4036 } 4037 4038 static void create_boundary_commit_list(struct rev_info *revs) 4039 { 4040 unsigned i; 4041 struct commit *c; 4042 struct object_array *array = &revs->boundary_commits; 4043 struct object_array_entry *objects = array->objects; 4044 4045 /* 4046 * If revs->commits is non-NULL at this point, an error occurred in 4047 * get_revision_1(). Ignore the error and continue printing the 4048 * boundary commits anyway. (This is what the code has always 4049 * done.) 4050 */ 4051 if (revs->commits) { 4052 free_commit_list(revs->commits); 4053 revs->commits = NULL; 4054 } 4055 4056 /* 4057 * Put all of the actual boundary commits from revs->boundary_commits 4058 * into revs->commits 4059 */ 4060 for (i = 0; i < array->nr; i++) { 4061 c = (struct commit *)(objects[i].item); 4062 if (!c) 4063 continue; 4064 if (!(c->object.flags & CHILD_SHOWN)) 4065 continue; 4066 if (c->object.flags & (SHOWN | BOUNDARY)) 4067 continue; 4068 c->object.flags |= BOUNDARY; 4069 commit_list_insert(c, &revs->commits); 4070 } 4071 4072 /* 4073 * If revs->topo_order is set, sort the boundary commits 4074 * in topological order 4075 */ 4076 sort_in_topological_order(&revs->commits, revs->sort_order); 4077 } 4078 4079 static struct commit *get_revision_internal(struct rev_info *revs) 4080 { 4081 struct commit *c = NULL; 4082 struct commit_list *l; 4083 4084 if (revs->boundary == 2) { 4085 /* 4086 * All of the normal commits have already been returned, 4087 * and we are now returning boundary commits. 4088 * create_boundary_commit_list() has populated 4089 * revs->commits with the remaining commits to return. 4090 */ 4091 c = pop_commit(&revs->commits); 4092 if (c) 4093 c->object.flags |= SHOWN; 4094 return c; 4095 } 4096 4097 /* 4098 * If our max_count counter has reached zero, then we are done. We 4099 * don't simply return NULL because we still might need to show 4100 * boundary commits. But we want to avoid calling get_revision_1, which 4101 * might do a considerable amount of work finding the next commit only 4102 * for us to throw it away. 4103 * 4104 * If it is non-zero, then either we don't have a max_count at all 4105 * (-1), or it is still counting, in which case we decrement. 4106 */ 4107 if (revs->max_count) { 4108 c = get_revision_1(revs); 4109 if (c) { 4110 while (revs->skip_count > 0) { 4111 revs->skip_count--; 4112 c = get_revision_1(revs); 4113 if (!c) 4114 break; 4115 } 4116 } 4117 4118 if (revs->max_count > 0) 4119 revs->max_count--; 4120 } 4121 4122 if (c) 4123 c->object.flags |= SHOWN; 4124 4125 if (!revs->boundary) 4126 return c; 4127 4128 if (!c) { 4129 /* 4130 * get_revision_1() runs out the commits, and 4131 * we are done computing the boundaries. 4132 * switch to boundary commits output mode. 4133 */ 4134 revs->boundary = 2; 4135 4136 /* 4137 * Update revs->commits to contain the list of 4138 * boundary commits. 4139 */ 4140 create_boundary_commit_list(revs); 4141 4142 return get_revision_internal(revs); 4143 } 4144 4145 /* 4146 * boundary commits are the commits that are parents of the 4147 * ones we got from get_revision_1() but they themselves are 4148 * not returned from get_revision_1(). Before returning 4149 * 'c', we need to mark its parents that they could be boundaries. 4150 */ 4151 4152 for (l = c->parents; l; l = l->next) { 4153 struct object *p; 4154 p = &(l->item->object); 4155 if (p->flags & (CHILD_SHOWN | SHOWN)) 4156 continue; 4157 p->flags |= CHILD_SHOWN; 4158 gc_boundary(&revs->boundary_commits); 4159 add_object_array(p, NULL, &revs->boundary_commits); 4160 } 4161 4162 return c; 4163 } 4164 4165 struct commit *get_revision(struct rev_info *revs) 4166 { 4167 struct commit *c; 4168 struct commit_list *reversed; 4169 4170 if (revs->reverse) { 4171 reversed = NULL; 4172 while ((c = get_revision_internal(revs))) 4173 commit_list_insert(c, &reversed); 4174 revs->commits = reversed; 4175 revs->reverse = 0; 4176 revs->reverse_output_stage = 1; 4177 } 4178 4179 if (revs->reverse_output_stage) { 4180 c = pop_commit(&revs->commits); 4181 if (revs->track_linear) 4182 revs->linear = !!(c && c->object.flags & TRACK_LINEAR); 4183 return c; 4184 } 4185 4186 c = get_revision_internal(revs); 4187 if (c && revs->graph) 4188 graph_update(revs->graph, c); 4189 if (!c) { 4190 free_saved_parents(revs); 4191 if (revs->previous_parents) { 4192 free_commit_list(revs->previous_parents); 4193 revs->previous_parents = NULL; 4194 } 4195 } 4196 return c; 4197 } 4198 4199 const char *get_revision_mark(const struct rev_info *revs, const struct commit *commit) 4200 { 4201 if (commit->object.flags & BOUNDARY) 4202 return "-"; 4203 else if (commit->object.flags & UNINTERESTING) 4204 return "^"; 4205 else if (commit->object.flags & PATCHSAME) 4206 return "="; 4207 else if (!revs || revs->left_right) { 4208 if (commit->object.flags & SYMMETRIC_LEFT) 4209 return "<"; 4210 else 4211 return ">"; 4212 } else if (revs->graph) 4213 return "*"; 4214 else if (revs->cherry_mark) 4215 return "+"; 4216 return ""; 4217 } 4218 4219 void put_revision_mark(const struct rev_info *revs, const struct commit *commit) 4220 { 4221 const char *mark = get_revision_mark(revs, commit); 4222 if (!strlen(mark)) 4223 return; 4224 fputs(mark, stdout); 4225 putchar(' '); 4226 } 4227