On Tue, Feb 14, 2023 at 08:36:44PM +0100, Christian Weisgerber wrote:
> About two weeks ago I committed jca's LLVM 15 diff to a local branch
> in my OpenBSD src repository, and I have performed a number of
> "got merge master" commits since.  The git log --graph output looks
> like two spaghettis who love each other very much. ;-)
> 
> When I use got or tog log -b to show the merged commits, the resultant
> ordering is... strange.
> 
> $ got log -s
> 2023-02-14 llvm15  merge refs/heads/master into refs/heads/llvm15
> 2023-02-13 b433205 merge refs/heads/master into refs/heads/llvm15
> 2023-02-12 63a41c1 merge refs/heads/master into refs/heads/llvm15
> 2023-02-09 7c80d1d merge refs/heads/master into refs/heads/llvm15
> 2023-02-03 6e9f183 merge refs/heads/master into refs/heads/llvm15
> 2023-02-02 c2ad0c1 llvm: update to 15.0.7
> [...]
> 
> Git puts all the commits that were brought in by the lastest merge
> between the two merge commits:
> 
> $ git log --oneline llvm15 | cut -c1-72
> 96f584075b7 merge refs/heads/master into refs/heads/llvm15
> d765bd22e38 Add -mpls to the route monitor case. It is an allowed addres
> 715494ad5dd use pragma pack around PPTable_t definitions
> 12139144481 use pragma pack around dmub_addr definition
> f289c483c58 regen
> 97b0c01557f Backout previous. Assertion was triggered within tsleep().
> 6a3029d85ff Fix scmi(4) entry.
> 503521236de smci -> scmi
> 873f6148a9d Typofix -ssthresh in HISTORY
> b4508d7f4f3 sync
> 5cf727077ff scmi(4)
> 2fb1186fe0e Add a driver for the ARM System Control and Management Inter
> 422309e7553 Add RK356x TSADC clocks.
> 305ac5f9173 Add dwqe(4), a driver for the Synopsis DesignWare Ethernet Q
> f3cb3cf5c8c Mention TCS4525.
> f478b5544f0 Add support for the Shenzhen Tangcheng Technology TCS4525 vo
> db911497a2e Adjust function prototype of a stub function after change to
> 988ba0ba4c3 Pass struct rib_entry to rde_generate_updates() instead of s
> b433205fa21 merge refs/heads/master into refs/heads/llvm15
> [...]
> 
> By contrast, got produces a history I can't make head or tail of:
> 
> $ got log -b -s | cut -c1-72
> 2023-02-14 llvm15  merge refs/heads/master into refs/heads/llvm15
> 2023-02-14 master  Add -mpls to the route monitor case. It is an allowed
> 2023-02-13 b433205 merge refs/heads/master into refs/heads/llvm15
> 2023-02-14 715494a use pragma pack around PPTable_t definitions
> 2023-02-13 0b0de91 Also lock the map in the execve-driven calls to uvm_m
> 2023-02-12 63a41c1 merge refs/heads/master into refs/heads/llvm15
> 2023-02-14 1213914 use pragma pack around dmub_addr definition
> 2023-02-13 aea972f Upon fork, copy the copyin_check structure to the new
> 2023-02-11 454ecbe non-padded 64-bit system calls arrived 2021/12/23, ov
> 2023-02-09 7c80d1d merge refs/heads/master into refs/heads/llvm15
> 2023-02-14 f289c48 regen
> 2023-02-13 3bd9ea3 regen
> 2023-02-11 dbaa3ef sync
> 2023-02-09 efd8dad consolidate mbuf header parsing on device driver laye
> 2023-02-03 6e9f183 merge refs/heads/master into refs/heads/llvm15
> 2023-02-14 97b0c01 Backout previous. Assertion was triggered within tsle
> 2023-02-13 0a470f0 asn1x509 test: Remove unnecessary line continuations
> 2023-02-11 8c7f5cc non-padded 64-bit system calls arrived 2021/12/23, ov
> 2023-02-09 69fcf33 Recognize the cores on Apple's M2 Pro/Max SoCs.
> 2023-02-03 a114beb Fix tput when compiled with clang-15 -O2
> [...]
> 
> The commits are all there, but the order is baffling.

This problem is also visible in tog.

The underlying reason is in the commit graph implementation.
It doesn't actually try to present the graph in a way that makes sense.

The current implementation spools all commits onto a list.
It only keeps track of open branch tips and keeps pulling commits from all
those tips in a round-robin fashion. It does not keep a record of chains of
parents and related merges to find "merge-points" and "split-points",
if you will, to find a nice way of presenting the history.

This could certainly be improved. I've made a few short attempts but never
got anywhere fast, so I dropped it again. Someone else who finds playing
with graph traversal algorithms a lot of fun should take another look.