{"thread":{"id":"59654","subject":"Commit graph not using minimal number of columns","startedAt":"2023-04-25T23:39:26Z","lastAt":"2023-04-27T18:24:10Z","messageCount":8,"participants":["Javier Mora","Junio C Hamano","Derrick Stolee"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"476077","messageId":"CAH1-q0hReZoDWmXo7St10Dk6uc+6ZUQSxqvu1cJ7w3r7ftR9PQ@mail.gmail.com","threadId":"59654","inReplyTo":null,"subject":"Commit graph not using minimal number of columns","fromName":"Javier Mora","fromEmail":"cousteaulecommandant@gmail.com","sentAt":"2023-04-25T23:39:01Z","receivedAt":"2023-04-25T23:39:26Z","isPatch":false,"sender":{"key":"cousteaulecommandant@gmail.com","avatar":"https://avatars.githubusercontent.com/u/6584870?v=4"},"body":"This is something that annoys me a lot whenever I'm maintaining a git\nrepo with two branches - a main development one and a \"fork\" or\nalteration of the main one, which periodically merges changes from the\nmain one while at the same time maintaining some additional feature.\n\nWhen I display the commit graph with `git log --graph` or `gitk`, this\ntype of graph shows up really nice, with two parallel \"tracks\"\ncorresponding to the two branches with periodic merges between them.\nHowever, if for some reason I merge an early version of the main\nbranch when there's already a newer commit in that branch, then the\nentire graph becomes an ugly mess that uses a lot of horizontal space,\nand I lose the visual representation of \"two parallel tracks\".\nThis seems to be due to git relying on commit dates to decide which\ncommit goes first, rather than relying solely on topological order.\n\nExample:\n```\nmkdir TEST_git\ncd TEST_git\ngit init -b main\n\ntouch A\ngit add A\ngit commit -m 'First commit'\n\ngit switch -c fork\ntouch Z\ngit add Z\ngit commit -m 'Introduced feature Z'\n\nfor i in B C D E F; do\n    git switch main\n    touch \"$i\"\n    git add \"$i\"\n    git commit -m \"Add $i\"\n    git switch fork\n    git merge --no-edit main\ndone\n\ngit log --all --decorate --oneline --graph\n# ^ displays a pretty \"two-track\" graph\n\ngit switch main\nfor i in G H; do\n    touch \"$i\"\n    git add \"$i\"\n    git commit -m \"Add $i\"\ndone\ngit switch fork\ngit merge --no-edit main~1\n\ngit log --all --decorate --oneline --graph\n# ^ displays a complete mess that doesn't resemble two tracks\n```\n\nThis seems to happen because commit H was created after G but before\nmerging G into `fork`, and can be mitigated by updating the committer\ndate of H so that it is newer than the merge of G into `fork`, but\nthat is not always an option.  It also seems to go away after merging\nH into `fork`, but that won't work if H is part of a\ntemporary/abandoned branch I don't plan to merge yet.  And I found\nthat calling `git log main --all ...` somehow fixes the graph as well.\nIn these cases, the option `--date-order` actually seems to yield\nbetter graphs than the default (`--topo-order`), but that option is\nnot ideal, since it may interleave commits from two separate branches,\nwhereas the default will group commits \"semantically\".\n\nWhat do you think?  Do you agree that this sort of thing looks\nannoying?  Do you think there might be a way to solve this kind of\nissue by improving the graph generation algorithm, so that it\nminimizes the number of columns in the graph (for example, preferring\nto display merge commits as late as possible)?  Or is this actually\nintentional, because the developers consider that in this sort of\nsituation it would be preferable to group all the merges together?\n"},{"id":"476078","messageId":"xmqq8refy114.fsf@gitster.g","threadId":"59654","inReplyTo":"CAH1-q0hReZoDWmXo7St10Dk6uc+6ZUQSxqvu1cJ7w3r7ftR9PQ@mail.gmail.com","subject":"Re: Commit graph not using minimal number of columns","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-04-25T23:50:31Z","receivedAt":"2023-04-25T23:50:36Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Javier Mora <cousteaulecommandant@gmail.com> writes:\n\n> git log --all --decorate --oneline --graph\n> # ^ displays a complete mess that doesn't resemble two tracks\n\n\"git log --all --oneline --graph --date-order\"?\n\n\n"},{"id":"476094","messageId":"86188f31-f492-d195-d4d5-b0582906621a@github.com","threadId":"59654","inReplyTo":"xmqq8refy114.fsf@gitster.g","subject":"Re: Commit graph not using minimal number of columns","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-04-26T10:45:24Z","receivedAt":"2023-04-26T10:47:06Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/25/2023 7:50 PM, Junio C Hamano wrote:\n> Javier Mora <cousteaulecommandant@gmail.com> writes:\n> \n>> git log --all --decorate --oneline --graph\n>> # ^ displays a complete mess that doesn't resemble two tracks\n\nThat mess is this:\n\n*   ac6812d (HEAD -> fork) Merge branch 'main' (early part) into fork\n|\\  \n* \\   92dbe19 Merge branch 'main' into fork\n|\\ \\  \n* \\ \\   c372f7b Merge branch 'main' into fork\n|\\ \\ \\  \n* \\ \\ \\   48cae29 Merge branch 'main' into fork\n|\\ \\ \\ \\  \n* \\ \\ \\ \\   1bd2ff0 Merge branch 'main' into fork\n|\\ \\ \\ \\ \\  \n* \\ \\ \\ \\ \\   a5ab648 Merge branch 'main' into fork\n|\\ \\ \\ \\ \\ \\  \n* | | | | | | 362d201 Introduced feature Z\n| | | | | | | * d46dfcc (main) Add H\n| | | | | | |/  \n| | | | | | * ac40305 Add G\n| | | | | |/  \n| | | | | * 867e17a Add F\n| | | | |/  \n| | | | * 23b1d2b Add E\n| | | |/  \n| | | * 8c36fda Add D\n| | |/  \n| | * cae1373 Add C\n| |/  \n| * 808c738 Add B\n|/  \n* 20b84d5 First commit\n\nThis width is necessary to avoid crossing lines _given the order\nof the commits_, which is picked independently of the graph\nrendering.\n\n> \"git log --all --oneline --graph --date-order\"?\n\nHere is that output, breaking topological ties with the commit\ndate order:\n\n*   ac6812d (HEAD -> fork) Merge branch 'main' (early part) into fork\n|\\  \n| | * d46dfcc (main) Add H\n| |/  \n| * ac40305 Add G\n* | 92dbe19 Merge branch 'main' into fork\n|\\| \n* |   c372f7b Merge branch 'main' into fork\n|\\ \\  \n| | * 867e17a Add F\n| |/  \n* |   48cae29 Merge branch 'main' into fork\n|\\ \\  \n| | * 23b1d2b Add E\n| |/  \n* |   1bd2ff0 Merge branch 'main' into fork\n|\\ \\  \n| | * 8c36fda Add D\n| |/  \n* |   a5ab648 Merge branch 'main' into fork\n|\\ \\  \n| | * cae1373 Add C\n| |/  \n* | 362d201 Introduced feature Z\n| * 808c738 Add B\n|/  \n* 20b84d5 First commit\n\nBut really, the key issue is that both branches are being used\nas tips. This means that in --topo-order (implied by --graph),\nevery commit reachable from 'fork' but not 'main' must be shown\nbefore the first commit of 'main'.\n\nIf we only use 'fork' as a starting point, then the --topo-order\nis the best of all the options:\n\n*   ac6812d (HEAD -> fork) Merge branch 'main' (early part) into fork\n|\\  \n| * ac40305 Add G\n* | 92dbe19 Merge branch 'main' into fork\n|\\| \n| * 867e17a Add F\n* | c372f7b Merge branch 'main' into fork\n|\\| \n| * 23b1d2b Add E\n* | 48cae29 Merge branch 'main' into fork\n|\\| \n| * 8c36fda Add D\n* | 1bd2ff0 Merge branch 'main' into fork\n|\\| \n| * cae1373 Add C\n* | a5ab648 Merge branch 'main' into fork\n|\\| \n| * 808c738 Add B\n* | 362d201 Introduced feature Z\n|/  \n* 20b84d5 First commit\n\nI don't think there is anything actionable to do here, as\nthese commit-ordering options are well-defined and should not\nbe altered. If there was an algorithm to modify the commit\norder in such a way that minimized the graph output, that\nwould be interesting, but the cases it minimizes are probably\ntoo rare to be worth the effort.\n\nThanks,\n-Stolee\n"},{"id":"476118","messageId":"xmqq1qk6vd3v.fsf@gitster.g","threadId":"59654","inReplyTo":"86188f31-f492-d195-d4d5-b0582906621a@github.com","subject":"Re: Commit graph not using minimal number of columns","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-04-26T16:10:12Z","receivedAt":"2023-04-26T16:10:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee <derrickstolee@github.com> writes:\n\n> This width is necessary to avoid crossing lines _given the order\n> of the commits_, which is picked independently of the graph\n> rendering.\n\nThanks for giving the crucial bit.\n\nObject listing order is determined first, and then graph algorithm\nworks on the series of commits that comes out of the revision\nwalking machinery.\n\n> I don't think there is anything actionable to do here, as\n> these commit-ordering options are well-defined and should not\n> be altered. If there was an algorithm to modify the commit\n> order in such a way that minimized the graph output, that\n> would be interesting, but the cases it minimizes are probably\n> too rare to be worth the effort.\n\nYes, in addition to and next to \"--{topo,date}-order\", if somebody\ncan come up with a new \"--graph-friendly-order\", it may be an\ninteresting addition.\n\nA tangent.  I do not offhand remember if --date-order works purely\non the timestamps in the commit objects, or do we take corrections\nbased on the generation numbers?  It seems that we only use the\ncompare_commits_by_gen_then_commit_date helper for prio queue\nmanipulation (to avoid the \"slop\" thing terminating the revision\nwalk too early) and not actual sorting.  I wonder if it makes much\ndifference if we used it instead of compare_commits_by_commit_date()\n\nThanks.\n\n"},{"id":"476124","messageId":"eb1c6c62-1081-a9d2-8504-db8bffc6c870@github.com","threadId":"59654","inReplyTo":"xmqq1qk6vd3v.fsf@gitster.g","subject":"Re: Commit graph not using minimal number of columns","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-04-26T17:35:32Z","receivedAt":"2023-04-26T17:35:38Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/26/2023 12:10 PM, Junio C Hamano wrote:\n> Derrick Stolee <derrickstolee@github.com> writes:\n\n>> I don't think there is anything actionable to do here, as\n>> these commit-ordering options are well-defined and should not\n>> be altered. If there was an algorithm to modify the commit\n>> order in such a way that minimized the graph output, that\n>> would be interesting, but the cases it minimizes are probably\n>> too rare to be worth the effort.\n> \n> Yes, in addition to and next to \"--{topo,date}-order\", if somebody\n> can come up with a new \"--graph-friendly-order\", it may be an\n> interesting addition.\n> \n> A tangent.  I do not offhand remember if --date-order works purely\n> on the timestamps in the commit objects, or do we take corrections\n> based on the generation numbers?  It seems that we only use the\n> compare_commits_by_gen_then_commit_date helper for prio queue\n> manipulation (to avoid the \"slop\" thing terminating the revision\n> walk too early) and not actual sorting.  I wonder if it makes much\n> difference if we used it instead of compare_commits_by_commit_date()\n\nThe --date-order guarantees topological relationships are respected,\nwhich is how it is different from the default order.\n\nFor the incremental topo-order logic, the topo_queue determines the\nfinal order (the algorithm ensures that the indegree_queue has walked\nfar enough that we only add commits to topo_queue if their \"in\ndegree\" is zero and thus safe to use within topological constraints).\n\nHere is how we pick the comparison:\n\n\tswitch (revs->sort_order) {\n\tdefault: /* REV_SORT_IN_GRAPH_ORDER */\n\t\tinfo->topo_queue.compare = NULL;\n\t\tbreak;\n\tcase REV_SORT_BY_COMMIT_DATE:\n\t\tinfo->topo_queue.compare = compare_commits_by_commit_date;\n\t\tbreak;\n\tcase REV_SORT_BY_AUTHOR_DATE:\n\t\tinit_author_date_slab(&info->author_date);\n\t\tinfo->topo_queue.compare = compare_commits_by_author_date;\n\t\tinfo->topo_queue.cb_data = &info->author_date;\n\t\tbreak;\n\t}\n\nUsing NULL makes the topo_queue act as a stack instead of a queue.\n\nBut crucially, --date-order sets to compare_commits_by_commit_date, so\ngeneration number has nothing to do with this part of the walk (it has\neverything to do with indegree_queue, though).\n\nTo adapt this algorithm to a newer, dynamic ordering that cares about\nminimizing the rendered graph, I don't think changing the priority\nqueue comparison would be sufficient. Something deeper would be\nrequired and would be quite messy.\n\nThanks,\n-Stolee\n"},{"id":"476126","messageId":"xmqqwn1ysfo4.fsf@gitster.g","threadId":"59654","inReplyTo":"eb1c6c62-1081-a9d2-8504-db8bffc6c870@github.com","subject":"Re: Commit graph not using minimal number of columns","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-04-26T17:43:07Z","receivedAt":"2023-04-26T17:43:13Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee <derrickstolee@github.com> writes:\n\n> To adapt this algorithm to a newer, dynamic ordering that cares about\n> minimizing the rendered graph, I don't think changing the priority\n> queue comparison would be sufficient. Something deeper would be\n> required and would be quite messy.\n\nOh, I wasn't thinking about \"graph-friendly\" at all.  \n\nI was wondering if we replaced --date-order implementation with\ncorrected commit date from the generation number work would give us\na better output order that users would expect in general (with or\nwithout --graph).\n\n\n"},{"id":"476204","messageId":"7ec7f7b2-3e7a-afb9-7042-a4375970e8d8@github.com","threadId":"59654","inReplyTo":"xmqqwn1ysfo4.fsf@gitster.g","subject":"Re: Commit graph not using minimal number of columns","fromName":"Derrick Stolee","fromEmail":"derrickstolee@github.com","sentAt":"2023-04-27T13:02:43Z","receivedAt":"2023-04-27T13:02:52Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 4/26/2023 1:43 PM, Junio C Hamano wrote:\n> Derrick Stolee <derrickstolee@github.com> writes:\n> \n>> To adapt this algorithm to a newer, dynamic ordering that cares about\n>> minimizing the rendered graph, I don't think changing the priority\n>> queue comparison would be sufficient. Something deeper would be\n>> required and would be quite messy.\n> \n> Oh, I wasn't thinking about \"graph-friendly\" at all.  \n> \n> I was wondering if we replaced --date-order implementation with\n> corrected commit date from the generation number work would give us\n> a better output order that users would expect in general (with or\n> without --graph).\n\nAh. My mistake.\n\nCorrected commit date should be equal to commit date unless there\nis clock skew causing a commit to be older than its parent, (or\nwe have a path of commits with equal commit date) so I don't\nanticipate that being helpful in general.\n\nThanks,\n-Stolee\n"},{"id":"476222","messageId":"xmqq4jp1kwu2.fsf@gitster.g","threadId":"59654","inReplyTo":"7ec7f7b2-3e7a-afb9-7042-a4375970e8d8@github.com","subject":"Re: Commit graph not using minimal number of columns","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2023-04-27T18:24:05Z","receivedAt":"2023-04-27T18:24:10Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee <derrickstolee@github.com> writes:\n\n> Corrected commit date should be equal to commit date unless there\n> is clock skew causing a commit to be older than its parent, (or\n> we have a path of commits with equal commit date) so I don't\n> anticipate that being helpful in general.\n\nYes, exactly.  For normal cases it should not matter.\n\nI was wondering if the current --date-order shows commits in an\norder that end-users find unnatural in a branchy history with many\ncommits that have wrong commit dates, and if so, tweaking the\ndate-order to instead use the corrected commit date may help and if\nso how much.\n\nThanks.\n\n\n"}]}