On 4/26/2023 12:10 PM, Junio C Hamano wrote:
> Derrick Stolee <derrickstolee@xxxxxxxxxx> writes:
>> 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
