Merge branch 'ab/commit-graph-write-progress'

The codepath to show progress meter while writing out commit-graph
file has been improved.

* ab/commit-graph-write-progress:
  commit-graph write: emit a percentage for all progress
  commit-graph write: add itermediate progress
  commit-graph write: remove empty line for readability
  commit-graph write: add more descriptive progress output
  commit-graph write: show progress for object search
  commit-graph write: more descriptive "writing out" output
  commit-graph write: add "Writing out" progress output
  commit-graph: don't call write_graph_chunk_extra_edges() unnecessarily
  commit-graph: rename "large edges" to "extra edges"
diff --git a/commit-graph.c b/commit-graph.c
index 8d52727..47e9be0 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -21,14 +21,14 @@
 #define GRAPH_CHUNKID_OIDFANOUT 0x4f494446 /* "OIDF" */
 #define GRAPH_CHUNKID_OIDLOOKUP 0x4f49444c /* "OIDL" */
 #define GRAPH_CHUNKID_DATA 0x43444154 /* "CDAT" */
-#define GRAPH_CHUNKID_LARGEEDGES 0x45444745 /* "EDGE" */
+#define GRAPH_CHUNKID_EXTRAEDGES 0x45444745 /* "EDGE" */
 
 #define GRAPH_DATA_WIDTH (the_hash_algo->rawsz + 16)
 
 #define GRAPH_VERSION_1 0x1
 #define GRAPH_VERSION GRAPH_VERSION_1
 
-#define GRAPH_OCTOPUS_EDGES_NEEDED 0x80000000
+#define GRAPH_EXTRA_EDGES_NEEDED 0x80000000
 #define GRAPH_EDGE_LAST_MASK 0x7fffffff
 #define GRAPH_PARENT_NONE 0x70000000
 
@@ -209,11 +209,11 @@ struct commit_graph *parse_commit_graph(void *graph_map, int fd,
 				graph->chunk_commit_data = data + chunk_offset;
 			break;
 
-		case GRAPH_CHUNKID_LARGEEDGES:
-			if (graph->chunk_large_edges)
+		case GRAPH_CHUNKID_EXTRAEDGES:
+			if (graph->chunk_extra_edges)
 				chunk_repeated = 1;
 			else
-				graph->chunk_large_edges = data + chunk_offset;
+				graph->chunk_extra_edges = data + chunk_offset;
 			break;
 		}
 
@@ -374,12 +374,12 @@ static int fill_commit_in_graph(struct repository *r,
 	edge_value = get_be32(commit_data + g->hash_len + 4);
 	if (edge_value == GRAPH_PARENT_NONE)
 		return 1;
-	if (!(edge_value & GRAPH_OCTOPUS_EDGES_NEEDED)) {
+	if (!(edge_value & GRAPH_EXTRA_EDGES_NEEDED)) {
 		pptr = insert_parent_or_die(r, g, edge_value, pptr);
 		return 1;
 	}
 
-	parent_data_ptr = (uint32_t*)(g->chunk_large_edges +
+	parent_data_ptr = (uint32_t*)(g->chunk_extra_edges +
 			  4 * (uint64_t)(edge_value & GRAPH_EDGE_LAST_MASK));
 	do {
 		edge_value = get_be32(parent_data_ptr);
@@ -466,7 +466,9 @@ struct tree *get_commit_tree_in_graph(struct repository *r, const struct commit
 
 static void write_graph_chunk_fanout(struct hashfile *f,
 				     struct commit **commits,
-				     int nr_commits)
+				     int nr_commits,
+				     struct progress *progress,
+				     uint64_t *progress_cnt)
 {
 	int i, count = 0;
 	struct commit **list = commits;
@@ -480,6 +482,7 @@ static void write_graph_chunk_fanout(struct hashfile *f,
 		while (count < nr_commits) {
 			if ((*list)->object.oid.hash[0] != i)
 				break;
+			display_progress(progress, ++*progress_cnt);
 			count++;
 			list++;
 		}
@@ -489,12 +492,16 @@ static void write_graph_chunk_fanout(struct hashfile *f,
 }
 
 static void write_graph_chunk_oids(struct hashfile *f, int hash_len,
-				   struct commit **commits, int nr_commits)
+				   struct commit **commits, int nr_commits,
+				   struct progress *progress,
+				   uint64_t *progress_cnt)
 {
 	struct commit **list = commits;
 	int count;
-	for (count = 0; count < nr_commits; count++, list++)
+	for (count = 0; count < nr_commits; count++, list++) {
+		display_progress(progress, ++*progress_cnt);
 		hashwrite(f, (*list)->object.oid.hash, (int)hash_len);
+	}
 }
 
 static const unsigned char *commit_to_sha1(size_t index, void *table)
@@ -504,7 +511,9 @@ static const unsigned char *commit_to_sha1(size_t index, void *table)
 }
 
 static void write_graph_chunk_data(struct hashfile *f, int hash_len,
-				   struct commit **commits, int nr_commits)
+				   struct commit **commits, int nr_commits,
+				   struct progress *progress,
+				   uint64_t *progress_cnt)
 {
 	struct commit **list = commits;
 	struct commit **last = commits + nr_commits;
@@ -514,6 +523,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,
 		struct commit_list *parent;
 		int edge_value;
 		uint32_t packedDate[2];
+		display_progress(progress, ++*progress_cnt);
 
 		parse_commit(*list);
 		hashwrite(f, get_commit_tree_oid(*list)->hash, hash_len);
@@ -542,7 +552,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,
 		if (!parent)
 			edge_value = GRAPH_PARENT_NONE;
 		else if (parent->next)
-			edge_value = GRAPH_OCTOPUS_EDGES_NEEDED | num_extra_edges;
+			edge_value = GRAPH_EXTRA_EDGES_NEEDED | num_extra_edges;
 		else {
 			edge_value = sha1_pos(parent->item->object.oid.hash,
 					      commits,
@@ -556,7 +566,7 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,
 
 		hashwrite_be32(f, edge_value);
 
-		if (edge_value & GRAPH_OCTOPUS_EDGES_NEEDED) {
+		if (edge_value & GRAPH_EXTRA_EDGES_NEEDED) {
 			do {
 				num_extra_edges++;
 				parent = parent->next;
@@ -577,9 +587,11 @@ static void write_graph_chunk_data(struct hashfile *f, int hash_len,
 	}
 }
 
-static void write_graph_chunk_large_edges(struct hashfile *f,
+static void write_graph_chunk_extra_edges(struct hashfile *f,
 					  struct commit **commits,
-					  int nr_commits)
+					  int nr_commits,
+					  struct progress *progress,
+					  uint64_t *progress_cnt)
 {
 	struct commit **list = commits;
 	struct commit **last = commits + nr_commits;
@@ -587,6 +599,9 @@ static void write_graph_chunk_large_edges(struct hashfile *f,
 
 	while (list < last) {
 		int num_parents = 0;
+
+		display_progress(progress, ++*progress_cnt);
+
 		for (parent = (*list)->parents; num_parents < 3 && parent;
 		     parent = parent->next)
 			num_parents++;
@@ -680,15 +695,15 @@ static void add_missing_parents(struct packed_oid_list *oids, struct commit *com
 
 static void close_reachable(struct packed_oid_list *oids, int report_progress)
 {
-	int i, j;
+	int i;
 	struct commit *commit;
 	struct progress *progress = NULL;
 
 	if (report_progress)
 		progress = start_delayed_progress(
-			_("Loading known commits in commit graph"), j = 0);
+			_("Loading known commits in commit graph"), oids->nr);
 	for (i = 0; i < oids->nr; i++) {
-		display_progress(progress, ++j);
+		display_progress(progress, i + 1);
 		commit = lookup_commit(the_repository, &oids->list[i]);
 		if (commit)
 			commit->object.flags |= UNINTERESTING;
@@ -702,9 +717,9 @@ static void close_reachable(struct packed_oid_list *oids, int report_progress)
 	 */
 	if (report_progress)
 		progress = start_delayed_progress(
-			_("Expanding reachable commits in commit graph"), j = 0);
+			_("Expanding reachable commits in commit graph"), oids->nr);
 	for (i = 0; i < oids->nr; i++) {
-		display_progress(progress, ++j);
+		display_progress(progress, i + 1);
 		commit = lookup_commit(the_repository, &oids->list[i]);
 
 		if (commit && !parse_commit(commit))
@@ -714,9 +729,9 @@ static void close_reachable(struct packed_oid_list *oids, int report_progress)
 
 	if (report_progress)
 		progress = start_delayed_progress(
-			_("Clearing commit marks in commit graph"), j = 0);
+			_("Clearing commit marks in commit graph"), oids->nr);
 	for (i = 0; i < oids->nr; i++) {
-		display_progress(progress, ++j);
+		display_progress(progress, i + 1);
 		commit = lookup_commit(the_repository, &oids->list[i]);
 
 		if (commit)
@@ -811,12 +826,16 @@ void write_commit_graph(const char *obj_dir,
 	struct commit_list *parent;
 	struct progress *progress = NULL;
 	const unsigned hashsz = the_hash_algo->rawsz;
+	uint64_t progress_cnt = 0;
+	struct strbuf progress_title = STRBUF_INIT;
+	unsigned long approx_nr_objects;
 
 	if (!commit_graph_compatible(the_repository))
 		return;
 
 	oids.nr = 0;
-	oids.alloc = approximate_object_count() / 32;
+	approx_nr_objects = approximate_object_count();
+	oids.alloc = approx_nr_objects / 32;
 	oids.progress = NULL;
 	oids.progress_done = 0;
 
@@ -846,8 +865,12 @@ void write_commit_graph(const char *obj_dir,
 		strbuf_addf(&packname, "%s/pack/", obj_dir);
 		dirlen = packname.len;
 		if (report_progress) {
-			oids.progress = start_delayed_progress(
-				_("Finding commits for commit graph"), 0);
+			strbuf_addf(&progress_title,
+				    Q_("Finding commits for commit graph in %d pack",
+				       "Finding commits for commit graph in %d packs",
+				       pack_indexes->nr),
+				    pack_indexes->nr);
+			oids.progress = start_delayed_progress(progress_title.buf, 0);
 			oids.progress_done = 0;
 		}
 		for (i = 0; i < pack_indexes->nr; i++) {
@@ -865,14 +888,20 @@ void write_commit_graph(const char *obj_dir,
 			free(p);
 		}
 		stop_progress(&oids.progress);
+		strbuf_reset(&progress_title);
 		strbuf_release(&packname);
 	}
 
 	if (commit_hex) {
-		if (report_progress)
-			progress = start_delayed_progress(
-				_("Finding commits for commit graph"),
-				commit_hex->nr);
+		if (report_progress) {
+			strbuf_addf(&progress_title,
+				    Q_("Finding commits for commit graph from %d ref",
+				       "Finding commits for commit graph from %d refs",
+				       commit_hex->nr),
+				    commit_hex->nr);
+			progress = start_delayed_progress(progress_title.buf,
+							  commit_hex->nr);
+		}
 		for (i = 0; i < commit_hex->nr; i++) {
 			const char *end;
 			struct object_id oid;
@@ -892,26 +921,36 @@ void write_commit_graph(const char *obj_dir,
 			}
 		}
 		stop_progress(&progress);
+		strbuf_reset(&progress_title);
 	}
 
 	if (!pack_indexes && !commit_hex) {
 		if (report_progress)
 			oids.progress = start_delayed_progress(
-				_("Finding commits for commit graph"), 0);
+				_("Finding commits for commit graph among packed objects"),
+				approx_nr_objects);
 		for_each_packed_object(add_packed_commits, &oids,
 				       FOR_EACH_OBJECT_PACK_ORDER);
+		if (oids.progress_done < approx_nr_objects)
+			display_progress(oids.progress, approx_nr_objects);
 		stop_progress(&oids.progress);
 	}
 
 	close_reachable(&oids, report_progress);
 
+	if (report_progress)
+		progress = start_delayed_progress(
+			_("Counting distinct commits in commit graph"),
+			oids.nr);
+	display_progress(progress, 0); /* TODO: Measure QSORT() progress */
 	QSORT(oids.list, oids.nr, commit_compare);
-
 	count_distinct = 1;
 	for (i = 1; i < oids.nr; i++) {
+		display_progress(progress, i + 1);
 		if (!oideq(&oids.list[i - 1], &oids.list[i]))
 			count_distinct++;
 	}
+	stop_progress(&progress);
 
 	if (count_distinct >= GRAPH_EDGE_LAST_MASK)
 		die(_("the commit graph format cannot write %d commits"), count_distinct);
@@ -921,8 +960,13 @@ void write_commit_graph(const char *obj_dir,
 	ALLOC_ARRAY(commits.list, commits.alloc);
 
 	num_extra_edges = 0;
+	if (report_progress)
+		progress = start_delayed_progress(
+			_("Finding extra edges in commit graph"),
+			oids.nr);
 	for (i = 0; i < oids.nr; i++) {
 		int num_parents = 0;
+		display_progress(progress, i + 1);
 		if (i > 0 && oideq(&oids.list[i - 1], &oids.list[i]))
 			continue;
 
@@ -939,6 +983,7 @@ void write_commit_graph(const char *obj_dir,
 		commits.nr++;
 	}
 	num_chunks = num_extra_edges ? 4 : 3;
+	stop_progress(&progress);
 
 	if (commits.nr >= GRAPH_EDGE_LAST_MASK)
 		die(_("too many commits to write graph"));
@@ -966,7 +1011,7 @@ void write_commit_graph(const char *obj_dir,
 	chunk_ids[1] = GRAPH_CHUNKID_OIDLOOKUP;
 	chunk_ids[2] = GRAPH_CHUNKID_DATA;
 	if (num_extra_edges)
-		chunk_ids[3] = GRAPH_CHUNKID_LARGEEDGES;
+		chunk_ids[3] = GRAPH_CHUNKID_EXTRAEDGES;
 	else
 		chunk_ids[3] = 0;
 	chunk_ids[4] = 0;
@@ -986,10 +1031,23 @@ void write_commit_graph(const char *obj_dir,
 		hashwrite(f, chunk_write, 12);
 	}
 
-	write_graph_chunk_fanout(f, commits.list, commits.nr);
-	write_graph_chunk_oids(f, hashsz, commits.list, commits.nr);
-	write_graph_chunk_data(f, hashsz, commits.list, commits.nr);
-	write_graph_chunk_large_edges(f, commits.list, commits.nr);
+	if (report_progress) {
+		strbuf_addf(&progress_title,
+			    Q_("Writing out commit graph in %d pass",
+			       "Writing out commit graph in %d passes",
+			       num_chunks),
+			    num_chunks);
+		progress = start_delayed_progress(
+			progress_title.buf,
+			num_chunks * commits.nr);
+	}
+	write_graph_chunk_fanout(f, commits.list, commits.nr, progress, &progress_cnt);
+	write_graph_chunk_oids(f, hashsz, commits.list, commits.nr, progress, &progress_cnt);
+	write_graph_chunk_data(f, hashsz, commits.list, commits.nr, progress, &progress_cnt);
+	if (num_extra_edges)
+		write_graph_chunk_extra_edges(f, commits.list, commits.nr, progress, &progress_cnt);
+	stop_progress(&progress);
+	strbuf_release(&progress_title);
 
 	close_commit_graph(the_repository);
 	finalize_hashfile(f, NULL, CSUM_HASH_IN_STREAM | CSUM_FSYNC);