1 files changed, 159 insertions, 158 deletions

diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index ba27d39f97..c1c74d4a79 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -1,12 +1,17 @@
 #include "cache.h"
+#include "config.h"
 #include "commit.h"
 #include "diff.h"
 #include "revision.h"
 #include "list-objects.h"
+#include "pack.h"
+#include "pack-bitmap.h"
 #include "builtin.h"
 #include "log-tree.h"
 #include "graph.h"
 #include "bisect.h"
+#include "progress.h"
+#include "reflog-walk.h"
 
 static const char rev_list_usage[] =
 "git rev-list [OPTION] <commit-id>... [ -- paths... ]\n"
@@ -16,6 +21,10 @@ static const char rev_list_usage[] =
 "    --min-age=<epoch>\n"
 "    --sparse\n"
 "    --no-merges\n"
+"    --min-parents=<n>\n"
+"    --no-min-parents\n"
+"    --max-parents=<n>\n"
+"    --no-max-parents\n"
 "    --remove-empty\n"
 "    --all\n"
 "    --branches\n"
@@ -36,22 +45,35 @@ static const char rev_list_usage[] =
 "    --abbrev=<n> | --no-abbrev\n"
 "    --abbrev-commit\n"
 "    --left-right\n"
+"    --count\n"
 "  special purpose:\n"
 "    --bisect\n"
 "    --bisect-vars\n"
 "    --bisect-all"
 ;
 
+static struct progress *progress;
+static unsigned progress_counter;
+
 static void finish_commit(struct commit *commit, void *data);
 static void show_commit(struct commit *commit, void *data)
 {
 	struct rev_list_info *info = data;
 	struct rev_info *revs = info->revs;
 
+	display_progress(progress, ++progress_counter);
+
+	if (info->flags & REV_LIST_QUIET) {
+		finish_commit(commit, data);
+		return;
+	}
+
 	graph_show_commit(revs->graph);
 
 	if (revs->count) {
-		if (commit->object.flags & SYMMETRIC_LEFT)
+		if (commit->object.flags & PATCHSAME)
+			revs->count_same++;
+		else if (commit->object.flags & SYMMETRIC_LEFT)
 			revs->count_left++;
 		else
 			revs->count_right++;
@@ -60,31 +82,21 @@ static void show_commit(struct commit *commit, void *data)
 	}
 
 	if (info->show_timestamp)
-		printf("%lu ", commit->date);
+		printf("%"PRItime" ", commit->date);
 	if (info->header_prefix)
 		fputs(info->header_prefix, stdout);
 
-	if (!revs->graph) {
-		if (commit->object.flags & BOUNDARY)
-			putchar('-');
-		else if (commit->object.flags & UNINTERESTING)
-			putchar('^');
-		else if (revs->left_right) {
-			if (commit->object.flags & SYMMETRIC_LEFT)
-				putchar('<');
-			else
-				putchar('>');
-		}
-	}
+	if (!revs->graph)
+		fputs(get_revision_mark(revs, commit), stdout);
 	if (revs->abbrev_commit && revs->abbrev)
-		fputs(find_unique_abbrev(commit->object.sha1, revs->abbrev),
+		fputs(find_unique_abbrev(commit->object.oid.hash, revs->abbrev),
 		      stdout);
 	else
-		fputs(sha1_to_hex(commit->object.sha1), stdout);
+		fputs(oid_to_hex(&commit->object.oid), stdout);
 	if (revs->print_parents) {
 		struct commit_list *parents = commit->parents;
 		while (parents) {
-			printf(" %s", sha1_to_hex(parents->item->object.sha1));
+			printf(" %s", oid_to_hex(&parents->item->object.oid));
 			parents = parents->next;
 		}
 	}
@@ -93,7 +105,7 @@ static void show_commit(struct commit *commit, void *data)
 
 		children = lookup_decoration(&revs->children, &commit->object);
 		while (children) {
-			printf(" %s", sha1_to_hex(children->item->object.sha1));
+			printf(" %s", oid_to_hex(&children->item->object.oid));
 			children = children->next;
 		}
 	}
@@ -103,54 +115,50 @@ static void show_commit(struct commit *commit, void *data)
 	else
 		putchar('\n');
 
-	if (revs->verbose_header && commit->buffer) {
+	if (revs->verbose_header && get_cached_commit_buffer(commit, NULL)) {
 		struct strbuf buf = STRBUF_INIT;
 		struct pretty_print_context ctx = {0};
 		ctx.abbrev = revs->abbrev;
 		ctx.date_mode = revs->date_mode;
-		pretty_print_commit(revs->commit_format, commit, &buf, &ctx);
-		if (revs->graph) {
-			if (buf.len) {
-				if (revs->commit_format != CMIT_FMT_ONELINE)
-					graph_show_oneline(revs->graph);
-
-				graph_show_commit_msg(revs->graph, &buf);
-
-				/*
-				 * Add a newline after the commit message.
-				 *
-				 * Usually, this newline produces a blank
-				 * padding line between entries, in which case
-				 * we need to add graph padding on this line.
-				 *
-				 * However, the commit message may not end in a
-				 * newline.  In this case the newline simply
-				 * ends the last line of the commit message,
-				 * and we don't need any graph output.  (This
-				 * always happens with CMIT_FMT_ONELINE, and it
-				 * happens with CMIT_FMT_USERFORMAT when the
-				 * format doesn't explicitly end in a newline.)
-				 */
-				if (buf.len && buf.buf[buf.len - 1] == '\n')
-					graph_show_padding(revs->graph);
-				putchar('\n');
-			} else {
-				/*
-				 * If the message buffer is empty, just show
-				 * the rest of the graph output for this
-				 * commit.
-				 */
-				if (graph_show_remainder(revs->graph))
-					putchar('\n');
-				if (revs->commit_format == CMIT_FMT_ONELINE)
-					putchar('\n');
-			}
+		ctx.date_mode_explicit = revs->date_mode_explicit;
+		ctx.fmt = revs->commit_format;
+		ctx.output_encoding = get_log_output_encoding();
+		ctx.color = revs->diffopt.use_color;
+		pretty_print_commit(&ctx, commit, &buf);
+		if (buf.len) {
+			if (revs->commit_format != CMIT_FMT_ONELINE)
+				graph_show_oneline(revs->graph);
+
+			graph_show_commit_msg(revs->graph, stdout, &buf);
+
+			/*
+			 * Add a newline after the commit message.
+			 *
+			 * Usually, this newline produces a blank
+			 * padding line between entries, in which case
+			 * we need to add graph padding on this line.
+			 *
+			 * However, the commit message may not end in a
+			 * newline.  In this case the newline simply
+			 * ends the last line of the commit message,
+			 * and we don't need any graph output.  (This
+			 * always happens with CMIT_FMT_ONELINE, and it
+			 * happens with CMIT_FMT_USERFORMAT when the
+			 * format doesn't explicitly end in a newline.)
+			 */
+			if (buf.len && buf.buf[buf.len - 1] == '\n')
+				graph_show_padding(revs->graph);
+			putchar(info->hdr_termination);
 		} else {
-			if (revs->commit_format != CMIT_FMT_USERFORMAT ||
-			    buf.len) {
-				fwrite(buf.buf, 1, buf.len, stdout);
-				putchar(info->hdr_termination);
-			}
+			/*
+			 * If the message buffer is empty, just show
+			 * the rest of the graph output for this
+			 * commit.
+			 */
+			if (graph_show_remainder(revs->graph))
+				putchar('\n');
+			if (revs->commit_format == CMIT_FMT_ONELINE)
+				putchar('\n');
 		}
 		strbuf_release(&buf);
 	} else {
@@ -167,94 +175,31 @@ static void finish_commit(struct commit *commit, void *data)
 		free_commit_list(commit->parents);
 		commit->parents = NULL;
 	}
-	free(commit->buffer);
-	commit->buffer = NULL;
+	free_commit_buffer(commit);
 }
 
-static void finish_object(struct object *obj, const struct name_path *path, const char *name)
+static void finish_object(struct object *obj, const char *name, void *cb_data)
 {
-	if (obj->type == OBJ_BLOB && !has_sha1_file(obj->sha1))
-		die("missing blob object '%s'", sha1_to_hex(obj->sha1));
+	struct rev_list_info *info = cb_data;
+	if (obj->type == OBJ_BLOB && !has_object_file(&obj->oid))
+		die("missing blob object '%s'", oid_to_hex(&obj->oid));
+	if (info->revs->verify_objects && !obj->parsed && obj->type != OBJ_COMMIT)
+		parse_object(&obj->oid);
 }
 
-static void show_object(struct object *obj, const struct name_path *path, const char *component)
+static void show_object(struct object *obj, const char *name, void *cb_data)
 {
-	char *name = path_name(path, component);
-	/* An object with name "foo\n0000000..." can be used to
-	 * confuse downstream "git pack-objects" very badly.
-	 */
-	const char *ep = strchr(name, '\n');
-
-	finish_object(obj, path, name);
-	if (ep) {
-		printf("%s %.*s\n", sha1_to_hex(obj->sha1),
-		       (int) (ep - name),
-		       name);
-	}
-	else
-		printf("%s %s\n", sha1_to_hex(obj->sha1), name);
-	free(name);
+	struct rev_list_info *info = cb_data;
+	finish_object(obj, name, cb_data);
+	display_progress(progress, ++progress_counter);
+	if (info->flags & REV_LIST_QUIET)
+		return;
+	show_object_with_name(stdout, obj, name);
 }
 
 static void show_edge(struct commit *commit)
 {
-	printf("-%s\n", sha1_to_hex(commit->object.sha1));
-}
-
-static inline int log2i(int n)
-{
-	int log2 = 0;
-
-	for (; n > 1; n >>= 1)
-		log2++;
-
-	return log2;
-}
-
-static inline int exp2i(int n)
-{
-	return 1 << n;
-}
-
-/*
- * Estimate the number of bisect steps left (after the current step)
- *
- * For any x between 0 included and 2^n excluded, the probability for
- * n - 1 steps left looks like:
- *
- * P(2^n + x) == (2^n - x) / (2^n + x)
- *
- * and P(2^n + x) < 0.5 means 2^n < 3x
- */
-int estimate_bisect_steps(int all)
-{
-	int n, x, e;
-
-	if (all < 3)
-		return 0;
-
-	n = log2i(all);
-	e = exp2i(n);
-	x = all - e;
-
-	return (e < 3 * x) ? n : n - 1;
-}
-
-void print_commit_list(struct commit_list *list,
-		       const char *format_cur,
-		       const char *format_last)
-{
-	for ( ; list; list = list->next) {
-		const char *format = list->next ? format_cur : format_last;
-		printf(format, sha1_to_hex(list->item->object.sha1));
-	}
-}
-
-static void show_tried_revs(struct commit_list *tried)
-{
-	printf("bisect_tried='");
-	print_commit_list(tried, "%s|", "%s");
-	printf("'\n");
+	printf("-%s\n", oid_to_hex(&commit->object.oid));
 }
 
 static void print_var_str(const char *var, const char *val)
@@ -269,12 +214,12 @@ static void print_var_int(const char *var, int val)
 
 static int show_bisect_vars(struct rev_list_info *info, int reaches, int all)
 {
-	int cnt, flags = info->bisect_show_flags;
-	char hex[41] = "";
+	int cnt, flags = info->flags;
+	char hex[GIT_MAX_HEXSZ + 1] = "";
 	struct commit_list *tried;
 	struct rev_info *revs = info->revs;
 
-	if (!revs->commits && !(flags & BISECT_SHOW_TRIED))
+	if (!revs->commits)
 		return 1;
 
 	revs->commits = filter_skipped(revs->commits, &tried,
@@ -295,16 +240,13 @@ static int show_bisect_vars(struct rev_list_info *info, int reaches, int all)
 		cnt = reaches;
 
 	if (revs->commits)
-		strcpy(hex, sha1_to_hex(revs->commits->item->object.sha1));
+		oid_to_hex_r(hex, &revs->commits->item->object.oid);
 
 	if (flags & BISECT_SHOW_ALL) {
 		traverse_commit_list(revs, show_commit, show_object, info);
 		printf("------\n");
 	}
 
-	if (flags & BISECT_SHOW_TRIED)
-		show_tried_revs(tried);
-
 	print_var_str("bisect_rev", hex);
 	print_var_int("bisect_nr", cnt - 1);
 	print_var_int("bisect_good", all - reaches - 1);
@@ -315,6 +257,18 @@ static int show_bisect_vars(struct rev_list_info *info, int reaches, int all)
 	return 0;
 }
 
+static int show_object_fast(
+	const unsigned char *sha1,
+	enum object_type type,
+	int exclude,
+	uint32_t name_hash,
+	struct packed_git *found_pack,
+	off_t found_offset)
+{
+	fprintf(stdout, "%s\n", sha1_to_hex(sha1));
+	return 1;
+}
+
 int cmd_rev_list(int argc, const char **argv, const char *prefix)
 {
 	struct rev_info revs;
@@ -323,7 +277,11 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	int bisect_list = 0;
 	int bisect_show_vars = 0;
 	int bisect_find_all = 0;
-	int quiet = 0;
+	int use_bitmap_index = 0;
+	const char *show_progress = NULL;
+
+	if (argc == 2 && !strcmp(argv[1], "-h"))
+		usage(rev_list_usage);
 
 	git_config(git_default_config, NULL);
 	init_revisions(&revs, prefix);
@@ -336,7 +294,8 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 	if (revs.bisect)
 		bisect_list = 1;
 
-	quiet = DIFF_OPT_TST(&revs.diffopt, QUICK);
+	if (DIFF_OPT_TST(&revs.diffopt, QUICK))
+		info.flags |= REV_LIST_QUIET;
 	for (i = 1 ; i < argc; i++) {
 		const char *arg = argv[i];
 
@@ -355,7 +314,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 		if (!strcmp(arg, "--bisect-all")) {
 			bisect_list = 1;
 			bisect_find_all = 1;
-			info.bisect_show_flags = BISECT_SHOW_ALL;
+			info.flags |= BISECT_SHOW_ALL;
 			revs.show_decorations = 1;
 			continue;
 		}
@@ -364,6 +323,18 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 			bisect_show_vars = 1;
 			continue;
 		}
+		if (!strcmp(arg, "--use-bitmap-index")) {
+			use_bitmap_index = 1;
+			continue;
+		}
+		if (!strcmp(arg, "--test-bitmap")) {
+			test_bitmap_walk(&revs);
+			return 0;
+		}
+		if (skip_prefix(arg, "--progress=", &arg)) {
+			show_progress = arg;
+			continue;
+		}
 		usage(rev_list_usage);
 
 	}
@@ -379,22 +350,49 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 		/* Only --header was specified */
 		revs.commit_format = CMIT_FMT_RAW;
 
-	if ((!revs.commits &&
-	     (!(revs.tag_objects||revs.tree_objects||revs.blob_objects) &&
-	      !revs.pending.nr)) ||
+	if ((!revs.commits && reflog_walk_empty(revs.reflog_info) &&
+	     (!(revs.tag_objects || revs.tree_objects || revs.blob_objects) &&
+	      !revs.pending.nr) &&
+	     !revs.rev_input_given) ||
 	    revs.diff)
 		usage(rev_list_usage);
 
+	if (revs.show_notes)
+		die(_("rev-list does not support display of notes"));
+
 	save_commit_buffer = (revs.verbose_header ||
 			      revs.grep_filter.pattern_list ||
 			      revs.grep_filter.header_list);
 	if (bisect_list)
 		revs.limited = 1;
 
+	if (show_progress)
+		progress = start_delayed_progress(show_progress, 0);
+
+	if (use_bitmap_index && !revs.prune) {
+		if (revs.count && !revs.left_right && !revs.cherry_mark) {
+			uint32_t commit_count;
+			int max_count = revs.max_count;
+			if (!prepare_bitmap_walk(&revs)) {
+				count_bitmap_commit_list(&commit_count, NULL, NULL, NULL);
+				if (max_count >= 0 && max_count < commit_count)
+					commit_count = max_count;
+				printf("%d\n", commit_count);
+				return 0;
+			}
+		} else if (revs.max_count < 0 &&
+			   revs.tag_objects && revs.tree_objects && revs.blob_objects) {
+			if (!prepare_bitmap_walk(&revs)) {
+				traverse_bitmap_commit_list(&show_object_fast);
+				return 0;
+			}
+		}
+	}
+
 	if (prepare_revision_walk(&revs))
 		die("revision walk setup failed");
 	if (revs.tree_objects)
-		mark_edges_uninteresting(revs.commits, &revs, show_edge);
+		mark_edges_uninteresting(&revs, show_edge);
 
 	if (bisect_list) {
 		int reaches = reaches, all = all;
@@ -406,14 +404,17 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 			return show_bisect_vars(&info, reaches, all);
 	}
 
-	traverse_commit_list(&revs,
-			     quiet ? finish_commit : show_commit,
-			     quiet ? finish_object : show_object,
-			     &info);
+	traverse_commit_list(&revs, show_commit, show_object, &info);
+
+	stop_progress(&progress);
 
 	if (revs.count) {
-		if (revs.left_right)
+		if (revs.left_right && revs.cherry_mark)
+			printf("%d\t%d\t%d\n", revs.count_left, revs.count_right, revs.count_same);
+		else if (revs.left_right)
 			printf("%d\t%d\n", revs.count_left, revs.count_right);
+		else if (revs.cherry_mark)
+			printf("%d\t%d\n", revs.count_left + revs.count_right, revs.count_same);
 		else
 			printf("%d\n", revs.count_left + revs.count_right);
 	}