Re: Commit graph not using minimal number of columns

From: Derrick Stolee <derrickstolee@github.com>
Date: Apr 26, 2023, 17:35 UTC
Message-ID: <eb1c6c62-1081-a9d2-8504-db8bffc6c870@github.com>
In-Reply-To: <xmqq1qk6vd3v.fsf@gitster.g>

On 4/26/2023 12:10 PM, Junio C Hamano wrote:

> Derrick Stolee <derrickstolee@github.com> writes:

Show 18 quoted lines

>> I don't think there is anything actionable to do here, as
>> these commit-ordering options are well-defined and should not
>> be altered. If there was an algorithm to modify the commit
>> order in such a way that minimized the graph output, that
>> would be interesting, but the cases it minimizes are probably
>> too rare to be worth the effort.
> 
> Yes, in addition to and next to "--{topo,date}-order", if somebody
> can come up with a new "--graph-friendly-order", it may be an
> interesting addition.
> 
> A tangent.  I do not offhand remember if --date-order works purely
> on the timestamps in the commit objects, or do we take corrections
> based on the generation numbers?  It seems that we only use the
> compare_commits_by_gen_then_commit_date helper for prio queue
> manipulation (to avoid the "slop" thing terminating the revision
> walk too early) and not actual sorting.  I wonder if it makes much
> difference if we used it instead of compare_commits_by_commit_date()

The --date-order guarantees topological relationships are respected, which is how it is different from the default order.

For the incremental topo-order logic, the topo_queue determines the final order (the algorithm ensures that the indegree_queue has walked far enough that we only add commits to topo_queue if their "in degree" is zero and thus safe to use within topological constraints).

Here is how we pick the comparison:

	switch (revs->sort_order) {
	default: /* REV_SORT_IN_GRAPH_ORDER */
		info->topo_queue.compare = NULL;
		break;
	case REV_SORT_BY_COMMIT_DATE:
		info->topo_queue.compare = compare_commits_by_commit_date;
		break;
	case REV_SORT_BY_AUTHOR_DATE:
		init_author_date_slab(&info->author_date);
		info->topo_queue.compare = compare_commits_by_author_date;
		info->topo_queue.cb_data = &info->author_date;
		break;
	}

Using NULL makes the topo_queue act as a stack instead of a queue.

But crucially, --date-order sets to compare_commits_by_commit_date, so generation number has nothing to do with this part of the walk (it has everything to do with indegree_queue, though).

To adapt this algorithm to a newer, dynamic ordering that cares about minimizing the rendered graph, I don't think changing the priority queue comparison would be sufficient. Something deeper would be required and would be quite messy.

Thanks, -Stolee