{"thread":{"id":"55003","subject":"DEVEL: Help with feature implementation","startedAt":"2021-01-18T18:08:52Z","lastAt":"2021-01-20T02:23:33Z","messageCount":16,"participants":["Aiyee Bee","Antonio Russo","Derrick Stolee","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"414604","messageId":"C8MHFL3YJDSF.1GLOUSV7BYS1X@localhost","threadId":"55003","inReplyTo":null,"subject":"DEVEL: Help with feature implementation","fromName":"Aiyee Bee","fromEmail":"shane.880088.supw@gmail.com","sentAt":"2021-01-18T18:06:52Z","receivedAt":"2021-01-18T18:08:52Z","isPatch":false,"sender":{"key":"shane.880088.supw@gmail.com","avatar":null},"body":"Hello everybody!\n\nI want to implement a feature in git, and I'm looking for some help.\n\nI wanted to add a history-simplification option to rev-list so that it\ndoesn't simplify away any irrelevant commits if they have multiple\nrelevant _children_, i.e. when they are the point where two relevant\nhistories diverge.\n\nBasically the effect I want for --show-forkpoints (named like --show-pulls):\nhttp://ix.io/2Ms6\n\nBut it seems there is no existing apparatus in the revision walker for\ndeciding simplification on basis of *children*, am I correct? Admittedly\nmy understanding of it is still a WIP, but I don't see anything that\ncould help.\n\nI was hoping that simply the flag CHILD_SHOWN could be checked, but it\nseems that's only set on boundary commits :(\n\nThis option would be pretty useful when used with some diffs, to see how\nmuch two forks have diverged. Currently if you use history simplification,\nthe diffs for both divergent histories will be created against the last\nrelevant commit instead of the last common ancestor, which creates pretty\nuseless diffs with a lot of intersection between them.\n\nAre there any viable alternative means to do this that I can explore?\n\nThanks!\n\nFriendlyNeighborhoodShane\n"},{"id":"414605","messageId":"f29fadef-6497-403c-59e0-8bd7beec77af@aerusso.net","threadId":"55003","inReplyTo":"C8MHFL3YJDSF.1GLOUSV7BYS1X@localhost","subject":"Re: DEVEL: Help with feature implementation","fromName":"Antonio Russo","fromEmail":"aerusso@aerusso.net","sentAt":"2021-01-18T18:19:54Z","receivedAt":"2021-01-18T18:21:27Z","isPatch":false,"sender":{"key":"aerusso@aerusso.net","avatar":"https://avatars.githubusercontent.com/u/6502699?v=4"},"body":"On 1/18/21 11:06 AM, Aiyee Bee wrote:\n> Hello everybody!\n> \n> I want to implement a feature in git, and I'm looking for some help.\n> \n> I wanted to add a history-simplification option to rev-list so that it\n> doesn't simplify away any irrelevant commits if they have multiple\n> relevant _children_, i.e. when they are the point where two relevant\n> histories diverge.\n\nI'm actually working on something that does the opposite---it ignores\nthe fork point when drawing the graph.  (I'm currently dog-fooding a\npartial implementation of this.)\n\n> Basically the effect I want for --show-forkpoints (named like --show-pulls):\n> http://ix.io/2Ms6\n> \n> But it seems there is no existing apparatus in the revision walker for\n> deciding simplification on basis of *children*, am I correct? Admittedly\n> my understanding of it is still a WIP, but I don't see anything that\n> could help.\n\nIt's even worse than this.  AFAICT, there are two code paths: one for when\nthe git-commit-graph is enabled, and one when it is not.  There's a special\n\"revs->limited\" option which lets you deal with the commits all at once, at\nthe expense of losing all the speed improvements from the git-commit-graph\nefforts.\n\nAside: I want to get rid of that alternative path.  But I only have limited\ntime.\n\n> I was hoping that simply the flag CHILD_SHOWN could be checked, but it\n> seems that's only set on boundary commits :(\n> \n> This option would be pretty useful when used with some diffs, to see how\n> much two forks have diverged. Currently if you use history simplification,\n> the diffs for both divergent histories will be created against the last\n> relevant commit instead of the last common ancestor, which creates pretty\n> useless diffs with a lot of intersection between them.\n\nSounds neat!\n\n> Are there any viable alternative means to do this that I can explore?\n\nI too would like to hear about suggestions for this.\n\n> \n> Thanks!\n> \n> FriendlyNeighborhoodShane\n> \n"},{"id":"414608","messageId":"60516c8b-adc0-18a5-ac26-b147b1857016@gmail.com","threadId":"55003","inReplyTo":"C8MHFL3YJDSF.1GLOUSV7BYS1X@localhost","subject":"Re: DEVEL: Help with feature implementation","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-01-18T18:26:57Z","receivedAt":"2021-01-18T18:28:02Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/18/2021 1:06 PM, Aiyee Bee wrote:\n> Hello everybody!\n> \n> I want to implement a feature in git, and I'm looking for some help.\n> \n> I wanted to add a history-simplification option to rev-list so that it\n> doesn't simplify away any irrelevant commits if they have multiple\n> relevant _children_, i.e. when they are the point where two relevant\n> histories diverge.\n> \n> Basically the effect I want for --show-forkpoints (named like --show-pulls):\n> http://ix.io/2Ms6\n\nI think what you really want is --full-history --simplify-merges [1]. This\nwill show the merges that \"fork\" the history into parallel tracks where\nat least two of them contain interesting commits.\n\nNote that this option is expensive to compute, as it walks every\nreachable commit before returning a single result.\n\nThanks,\n-Stolee\n\n[1] https://git-scm.com/docs/git-log#Documentation/git-log.txt---simplify-merges\n"},{"id":"414610","messageId":"C8MIWAN0N50F.235740W7QGT05@localhost","threadId":"55003","inReplyTo":"60516c8b-adc0-18a5-ac26-b147b1857016@gmail.com","subject":"Re: DEVEL: Help with feature implementation","fromName":"Aiyee Bee","fromEmail":"shane.880088.supw@gmail.com","sentAt":"2021-01-18T19:15:43Z","receivedAt":"2021-01-18T19:18:29Z","isPatch":false,"sender":{"key":"shane.880088.supw@gmail.com","avatar":null},"body":"Hi Antonio and Derrick!\n\n> I think what you really want is --full-history --simplify-merges [1]. This\n> will show the merges that \"fork\" the history into parallel tracks where\n> at least two of them contain interesting commits.\n\nIt doesn't look like the implementation of --simplify-merges helps much\nhere. That makes its decision on basis of the parents of the commit, which is\nsimple to do as it's information attached freely to each commit. I think the\nproblem here would be figuring out, given any commit, how many of its children\nare \"relevant\" commits.\n\n> I'm actually working on something that does the opposite---it ignores\n> the fork point when drawing the graph.  (I'm currently dog-fooding a\n> partial implementation of this.)\n\nThat's a pretty interesting coincidence :)\n\nJust to throw ideas out there, maybe we could attach another commit_list,\nchildren, to the commit metadata, so that all this becomes a little easier.\nBut I guess that's be pretty impractical and inefficient.\n\nMaybe a more practical (but still pretty unusual) solution would be adding\ncounters to each commit that tell us how many times they have been traversed\nThrough various histories?\n"},{"id":"414918","messageId":"C8MJ3Z9R5UAV.3TJWJSOZBG32V@localhost","threadId":"55003","inReplyTo":"60516c8b-adc0-18a5-ac26-b147b1857016@gmail.com","subject":"Re: DEVEL: Help with feature implementation","fromName":"Aiyee Bee","fromEmail":"shane.880088.supw@gmail.com","sentAt":"2021-01-18T19:25:45Z","receivedAt":"2021-01-18T19:31:19Z","isPatch":false,"sender":{"key":"shane.880088.supw@gmail.com","avatar":null},"body":""},{"id":"414612","messageId":"C8MJ83LNOZ1Q.OCQKHOTGHKWF@localhost","threadId":"55003","inReplyTo":"60516c8b-adc0-18a5-ac26-b147b1857016@gmail.com","subject":"Re: DEVEL: Help with feature implementation","fromName":"Aiyee Bee","fromEmail":"shane.880088.supw@gmail.com","sentAt":"2021-01-18T19:31:08Z","receivedAt":"2021-01-18T19:42:24Z","isPatch":false,"sender":{"key":"shane.880088.supw@gmail.com","avatar":null},"body":"Hi Antonio and Derrick!\n\n> I think what you really want is --full-history --simplify-merges [1]. This\n> will show the merges that \"fork\" the history into parallel tracks where\n> at least two of them contain interesting commits.\n\nIt doesn't look like the implementation of --simplify-merges helps much\nhere. That makes its decision on basis of the parents of the commit, which is\nsimple to do as it's information attached freely to each commit. I think the\nproblem here would be figuring out, given any commit, how many of its children\nare \"relevant\" commits.\n\n> I'm actually working on something that does the opposite---it ignores\n> the fork point when drawing the graph.  (I'm currently dog-fooding a\n> partial implementation of this.)\n\nThat's a pretty interesting coincidence :)\n\nJust to throw ideas out there, maybe we could attach another commit_list,\nchildren, to the commit metadata, so that all this becomes a little easier.\nBut I guess that's be pretty impractical and inefficient.\n\nMaybe a more practical (but still pretty unusual) solution would be adding\ncounters to each commit that tell us how many times they have been traversed\nThrough various histories?\n"},{"id":"414622","messageId":"38ed4389-ba9f-743a-3fa3-5ffab12ef0a9@gmail.com","threadId":"55003","inReplyTo":"C8MJ83LNOZ1Q.OCQKHOTGHKWF@localhost","subject":"Re: DEVEL: Help with feature implementation","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-01-18T20:58:05Z","receivedAt":"2021-01-18T20:59:01Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/18/2021 2:31 PM, Aiyee Bee wrote:\n> Hi Antonio and Derrick!\n> \n>> I think what you really want is --full-history --simplify-merges [1]. This\n>> will show the merges that \"fork\" the history into parallel tracks where\n>> at least two of them contain interesting commits.\n> \n> It doesn't look like the implementation of --simplify-merges helps much\n> here. That makes its decision on basis of the parents of the commit, which is\n> simple to do as it's information attached freely to each commit. I think the\n> problem here would be figuring out, given any commit, how many of its children\n> are \"relevant\" commits.\n\nYou should definitely give this a try instead of assuming things about the\nimplementation. The algorithm uses a lot of \"simplifying\" that makes it look\nlike the decision is a local one. However, I assure you that is not the case.\n\nPlease assemble a test case that demonstrates the behavior you want and how\nthat is different from what is present in --simplify-merges.\n\n-Stolee\n"},{"id":"414635","messageId":"xmqqzh15j1ot.fsf@gitster.c.googlers.com","threadId":"55003","inReplyTo":"C8MIWAN0N50F.235740W7QGT05@localhost","subject":"Re: DEVEL: Help with feature implementation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-01-18T22:54:42Z","receivedAt":"2021-01-18T22:55:47Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Aiyee Bee\" <shane.880088.supw@gmail.com> writes:\n\n> Maybe a more practical (but still pretty unusual) solution would be adding\n> counters to each commit that tell us how many times they have been traversed\n> Through various histories?\n\nThe \"--show-forkpoints\" output shown there at http://ix.io/2Ms6\nlooks interesting.  I think you'd need only 1 bit counter\n(i.e. \"have we visited it only once, or more than once\" bit) for\nyour purpose?  You traverse from F and Z and the first time you\nreach C (probably through the F->E->D->C path), you see no SEEN flag\non the object so leave the new bit alone, and then when the traverse\nreaches C again (this time through the Z->Y->C path), while stopping\nfurther traversal because you notice C is already SEEN, you mark it\nwith the new bit so record that it has been visited at least twice.\n\n"},{"id":"414648","messageId":"992cd021-d6f6-dfe4-1918-45643aa85a61@aerusso.net","threadId":"55003","inReplyTo":"38ed4389-ba9f-743a-3fa3-5ffab12ef0a9@gmail.com","subject":"Re: DEVEL: Help with feature implementation","fromName":"Antonio Russo","fromEmail":"aerusso@aerusso.net","sentAt":"2021-01-19T00:54:06Z","receivedAt":"2021-01-19T00:55:27Z","isPatch":false,"sender":{"key":"aerusso@aerusso.net","avatar":"https://avatars.githubusercontent.com/u/6502699?v=4"},"body":"On 1/18/21 1:58 PM, Derrick Stolee wrote:\n> On 1/18/2021 2:31 PM, Aiyee Bee wrote:\n>> Hi Antonio and Derrick!\n>>\n>>> I think what you really want is --full-history --simplify-merges [1]. This\n>>> will show the merges that \"fork\" the history into parallel tracks where\n>>> at least two of them contain interesting commits.\n>>\n>> It doesn't look like the implementation of --simplify-merges helps much\n>> here. That makes its decision on basis of the parents of the commit, which is\n>> simple to do as it's information attached freely to each commit. I think the\n>> problem here would be figuring out, given any commit, how many of its children\n>> are \"relevant\" commits.\n> \n> You should definitely give this a try instead of assuming things about the\n> implementation. The algorithm uses a lot of \"simplifying\" that makes it look\n> like the decision is a local one. However, I assure you that is not the case.\n\nAs a side note, would this list be willing to look at patches that remove\nthe need to use revs->limited?  Adding new features would be much easier if\nwe could restrict git to use streaming algorithms for these simplifications.\n\n> Please assemble a test case that demonstrates the behavior you want and how\n> that is different from what is present in --simplify-merges.\n\nI can't figure out how to get the behavior from --simplify-merges, which is\ndescribed as\n\n\tAdditional option to --full-history to remove some needless\n\tmerges from  the resulting history, as there are no selected\n\tcommits contributing to this merge.\n\nIt seems that the desired behavior is to include commits which are parents to\nmultiple branches.  Here is an example:\n\ntest_commit() {\n echo >> file\n git add file\n git commit \"$@\"\n}\n\ngit init\ntest_commit -m a\ntest_commit -m b\ntest_commit -m c\ngit checkout -b fork\ntest_commit -m y\ntest_commit -m z\ngit switch master\ntest_commit -m d\ntest_commit -m e\ntest_commit -m f\n\ngit log --graph --oneline master fork\n\n* 08029fd f\n* 55b09fe e\n* 83b7801 d\n| * efc204e z\n| * 316219e y\n|/  \n* 3594039 c\n* 4321987 b\n* bd44220 a\n\ngit log --graph --oneline --full-history --simplify-merges master fork\n\n* 08029fd f\n* 55b09fe e\n* 83b7801 d\n| * efc204e z\n| * 316219e y\n|/  \n* 3594039 c\n* 4321987 b\n* bd44220 a\n\ngit log --graph --oneline --simplify-by-decoration --full-history --simplify-merges master fork\n\n* 08029fd f\n| * efc204e z\n|/  \n* bd44220 a\n\ngit log --graph --oneline --full-history --simplify-merges master fork\n\n* 08029fd f\n* 55b09fe e\n* 83b7801 d\n| * efc204e z\n| * 316219e y\n|/  \n* 3594039 c\n* 4321987 b\n* bd44220 a\n\ngit --version\ngit version 2.30.0\n\nI can't seem to get commit c, the crucial fork, to show up with simplifications with this mechanism.\nAm I missing something here?\n\n> \n> -Stolee\n> \n\nAntonio\n"},{"id":"414649","messageId":"xmqq7do9iuqj.fsf@gitster.c.googlers.com","threadId":"55003","inReplyTo":"992cd021-d6f6-dfe4-1918-45643aa85a61@aerusso.net","subject":"Re: DEVEL: Help with feature implementation","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-01-19T01:24:52Z","receivedAt":"2021-01-19T01:26:11Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Antonio Russo <aerusso@aerusso.net> writes:\n\n> As a side note, would this list be willing to look at patches that remove\n> the need to use revs->limited?  Adding new features would be much easier if\n> we could restrict git to use streaming algorithms for these simplifications.\n\nDo you mean you will write new implementations of operations like\n\"--simplify-merges\", \"--ancestory-path\" and all its friends without\nthe need for the \"limited\" bit?\n\nWilling to look at?  I do not know about others, but sure, it would\nmake be extremely excited.\n\nYou may be able to rewrite some other operations that implicitly\nrequire the limited bit into an incremental implementation, but I am\nskeptical that you can do \"simplify-merges\" in a streaming fashion\nin such a way that we'd dig a bit but not all the way down before\nmaking decisions on which commits should be included in the output\nand how their parenthood relationship should appear etc.  I and\nLinus tried independently and we did not get that far in our\nattempts (note: there wasn't commit-graph back then).\n\nIf you are talking about precomputed stuff like commit-graph, that\nmay change the equation, but we'd prefer to have the system work\nwithout requiring these auxiliary data (in other words, it would be\nfine to use them as optimization).\n\n"},{"id":"414650","messageId":"5e5ece7c-3f34-caa1-db87-084b42c1cb62@gmail.com","threadId":"55003","inReplyTo":"992cd021-d6f6-dfe4-1918-45643aa85a61@aerusso.net","subject":"Re: DEVEL: Help with feature implementation","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-01-19T02:39:37Z","receivedAt":"2021-01-19T02:40:51Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/18/2021 7:54 PM, Antonio Russo wrote:\n> On 1/18/21 1:58 PM, Derrick Stolee wrote:\n>> On 1/18/2021 2:31 PM, Aiyee Bee wrote:\n>>> Hi Antonio and Derrick!\n>>>\n>>>> I think what you really want is --full-history --simplify-merges [1]. This\n>>>> will show the merges that \"fork\" the history into parallel tracks where\n>>>> at least two of them contain interesting commits.\n>>>\n>>> It doesn't look like the implementation of --simplify-merges helps much\n>>> here. That makes its decision on basis of the parents of the commit, which is\n>>> simple to do as it's information attached freely to each commit. I think the\n>>> problem here would be figuring out, given any commit, how many of its children\n>>> are \"relevant\" commits.\n>>\n>> You should definitely give this a try instead of assuming things about the\n>> implementation. The algorithm uses a lot of \"simplifying\" that makes it look\n>> like the decision is a local one. However, I assure you that is not the case.\n> \n> As a side note, would this list be willing to look at patches that remove\n> the need to use revs->limited?  Adding new features would be much easier if\n> we could restrict git to use streaming algorithms for these simplifications.\n\nI would _love_ to see patches that remove that bit (without modifying\nthe behavior).\n\nFair warning: I definitely spent a few weeks attempting to do any amount\nof reducing the depth one needs to walk in order to compute the\n--simplify-merges history, but a sufficiently-complicated branch history\nmakes it nearly impossible to gain a benefit.\n\n>> Please assemble a test case that demonstrates the behavior you want and how\n>> that is different from what is present in --simplify-merges.\n> \n> I can't figure out how to get the behavior from --simplify-merges, which is\n> described as\n> \n> \tAdditional option to --full-history to remove some needless\n> \tmerges from  the resulting history, as there are no selected\n> \tcommits contributing to this merge.\n> \n> It seems that the desired behavior is to include commits which are parents to\n> multiple branches.  Here is an example:\n\nThank you for these examples. They clearly show that I misread your\nask, because you're not looking for \"merge commits\" but instead you\nare looking to show the \"merge bases\" as history is walking.\n\nSorry for misinterpreting your request, then doubling down on it.\n\n> test_commit() {\n>  echo >> file\n>  git add file\n>  git commit \"$@\"\n> }\n> \n> git init\n> test_commit -m a\n> test_commit -m b\n> test_commit -m c\n> git checkout -b fork\n> test_commit -m y\n> test_commit -m z\n> git switch master\n> test_commit -m d\n> test_commit -m e\n> test_commit -m f\n> \n> git log --graph --oneline master fork\n> \n> * 08029fd f\n> * 55b09fe e\n> * 83b7801 d\n> | * efc204e z\n> | * 316219e y\n> |/  \n> * 3594039 c\n> * 4321987 b\n> * bd44220 a\n> \n> git log --graph --oneline --full-history --simplify-merges master fork\n> \n> * 08029fd f\n> * 55b09fe e\n> * 83b7801 d\n> | * efc204e z\n> | * 316219e y\n> |/  \n> * 3594039 c\n> * 4321987 b\n> * bd44220 a\n> \n> git log --graph --oneline --simplify-by-decoration --full-history --simplify-merges master fork\n> \n> * 08029fd f\n> | * efc204e z\n> |/  \n> * bd44220 a\n> \n> git log --graph --oneline --full-history --simplify-merges master fork\n> \n> * 08029fd f\n> * 55b09fe e\n> * 83b7801 d\n> | * efc204e z\n> | * 316219e y\n> |/  \n> * 3594039 c\n> * 4321987 b\n> * bd44220 a\n> \n> git --version\n> git version 2.30.0\n> \n> I can't seem to get commit c, the crucial fork, to show up with simplifications with this mechanism.\n> Am I missing something here?\n\nIn your example, you are not specifying a path. In this case, you are\nreally looking for \"git merge-base master fork\". You could also use\n\"git log --boundary master...fork\" to show everything up to and\nincluding 'c'.\n\nNow, if you specify a pathspec, then 'git merge-base' isn't going to\nhelp. That becomes a technically interesting problem.\n\nThe biggest reason that \"git log\" doesn't show this commit 'c' easily\nis because...it's not really that important. When that commit was\ncreated, it didn't \"know\" that it would be a common base of two\ndiverging branches. By surfacing the commit, we are very unlikely to\npresent the user with information that is helpful.\n\nOne way to expose the \"first layer\" of these merge bases is with the\n--boundary option.\n\nHere is an example of two branches in the Git ecosystem that can\npresent an interesting real example: code in builtin/gc.c has been\nchanged in both 'master' from origin (https://github.com/git/git) and\nin 'main' from windows (https://github.com/git-for-windows/git):\n\n$ git log --no-decorate --oneline --graph origin/master...windows/main  -- builtin/gc.c\n* b2ace18759c Merge branch 'ds/maintenance-part-4'\n* c977ff44073 Merge branch 'pk/subsub-fetch-fix-take-2'\n*   95124ead43a Merge branch 'main' into maintenance-and-headless\n|\\  \n| * ff61c9b1f49 Start the merging-rebase to v2.30.0-rc2\n| * afb16063390 Start the merging-rebase to v2.30.0-rc0\n| * 13c9d54a45b Start the merging-rebase to v2.29.0-rc0\n| * c00a524ea88 strvec: rename struct fields\n| * a864a84f1ee strvec: fix indentation in renamed calls\n| * 12922aa02db strvec: convert builtin/ callers away from argv_array name\n| * 86f1b0f0e04 strvec: rename files from argv-array to strvec\n* 5bef0904826 git maintenance: avoid console window in scheduled tasks on Windows\n\nSomething that is hard to see from this picture is that the first two\ncommits are not actually connected to the third. This is more visible\nwhen adding --boundary:\n\n$ git log --no-decorate --oneline --graph --boundary origin/master...windows/main -- builtin/gc.c\n*   b2ace18759c Merge branch 'ds/maintenance-part-4'\n|\\  \n* \\   c977ff44073 Merge branch 'pk/subsub-fetch-fix-take-2'\n|\\ \\  \n| | | *   95124ead43a Merge branch 'main' into maintenance-and-headless\n| | | |\\  \n| | | | *   ff61c9b1f49 Start the merging-rebase to v2.30.0-rc2\n| | | | |\\  \n| | | | | *   afb16063390 Start the merging-rebase to v2.30.0-rc0\n| | | | | |\\  \n| | | | | | *   13c9d54a45b Start the merging-rebase to v2.29.0-rc0\n| | | | | | |\\  \n| | | | | | | * c00a524ea88 strvec: rename struct fields\n| | | | | | | * a864a84f1ee strvec: fix indentation in renamed calls\n| | | | | | | * 12922aa02db strvec: convert builtin/ callers away from argv_array name\n| | | | | | | * 86f1b0f0e04 strvec: rename files from argv-array to strvec\n| | | * | | | | 5bef0904826 git maintenance: avoid console window in scheduled tasks on Windows\n| | |/ / / / /  \n| | | | | | o 47ae905ffb9 Git 2.28\n| | | | | o d98273ba77e Git 2.29-rc0\n| | | | o 1c52ecf4ba0 Git 2.30-rc0\n| | | o 4a0de43f492 Git 2.30-rc2\n| o | 898f80736c7 Git 2.29.2\n|  /  \no / 71ca53e8125 Git 2.30\n /  \no 3797a0a7b7a maintenance: use Windows scheduled tasks\n\nNotice that all these boundaries are actually adding \"uninteresting\"\nbases _and_ merges.\n\nProbably, the suggested --show-forkpoints would need to start from\nsomething like this and simplify it further.\n\nThe problem that I see as well is what happens as the history itself\nbranches repeatedly. Consider the history of builtin/gc.c again, this\ntime with a single starting ref. (I have inserted places where your\nfork points might add commits to the first few results.)\n\n$ git log --no-decorate --oneline --graph origin/master -- builtin/gc.c\n*   b2ace18759c Merge branch 'ds/maintenance-part-4'\n|\\  \n| * 3797a0a7b7a maintenance: use Windows scheduled tasks\n| * 2afe7e35672 maintenance: use launchctl on macOS\n| * 31345d5545e maintenance: extract platform-specific scheduling\n* | 66dc0a3625e gc: fix handling of crontab magic markers\n* |   f2a75cb312d Merge branch 'rs/maintenance-run-outside-repo'\n|\\ \\  \n| * | e72f7defc4f maintenance: fix SEGFAULT when no repository\n* | |   d702cb9e890 Merge branch 'ds/maintenance-part-3'\n|\\ \\ \\  \n| * | | 483a6d9b5da maintenance: use 'git config --fixed-value'\n* | | |   1c04cdd424b Merge branch 'ab/gc-keep-base-option'\n|\\ \\ \\ \\  \n| |_|/ /  \n|/| | |   \n\n* | | |  (some fork point here)\n\n| * | | 793c1464d3e gc: rename keep_base_pack variable for --keep-largest-pack\n* | | | a1c74791d5f gc: fix cast in compare_tasks_by_selection()\n| |/ /  \n|/| |   \n\n* | |    (some fork point here)\n\n* | |   7660da16182 Merge branch 'ds/maintenance-part-3'\n|\\ \\ \\  \n| | |/  \n| |/|   \n\n| * |    (some fork point here)\n\n| * | 61f7a383d3b maintenance: use 'incremental' strategy by default\n| * | a4cb1a2339c maintenance: create maintenance.strategy config\n| * | 2fec604f8df maintenance: add start/stop subcommands\n| * | 0c18b700810 maintenance: add [un]register subcommands\n| * | b08ff1fee00 maintenance: add --schedule option and config\n* | |   902f358555c Merge branch 'rs/clear-commit-marks-in-repo\n\nWhen using file history simplification, there is actually a very\nsimple way to detect whether a commit is a fork point (assuming\nthat you are walking in generation number order):\n\n- As you walk and see that commit C is not TREESAME to commit D,\n  increment a \"walked indegree\" count on D. (Note: this would be\n  different from the current \"indegree\" slab used in topo-order\n  calculations.)\n\n- As you visit a commit, check its indegree. If this is larger\n  than 1, then it is a forkpoint of two \"interesting\" histories.\n\nThis entire procedure relies on the fact that simplified history\nonly visits multiple parents if the merge commit is not TREESAME\nto _any_ parent. Otherwise, it walks only to its first TREESAME\nparent, \"simplifying away\" the other parents.\n\nTo implement your fork-points in the case of --full-history\nor --simplify-merges would require something much more sophisticated.\n\n   (taking an extra pause here to shift gears)\n\nBut I think the --show-forkpoints option needs to be justified a\nbit better. I'm still not convinced that this is actually\ninteresting information, unless you are literally looking for a\nmerge base or a log boundary, in which case there are ways to\nexpose those values.\n\nThe example of --show-pulls has such a justification:\n\n  If a user wants to see which merge commits introduced the\n  interesting commits into this history, then --show-pulls\n  presents those merges. Such merges might have extra\n  information in their commit messages, such as pull request\n  IDs, topic branch names, or information about tricky merge\n  conflict resolutions.\n\nIs there something similar to justify --show-forkpoint?\n\nThanks,\n-Stolee\n"},{"id":"414659","messageId":"C8MW4U7TN2CA.2NMNG05BE2J97@localhost","threadId":"55003","inReplyTo":"5e5ece7c-3f34-caa1-db87-084b42c1cb62@gmail.com","subject":"Re: DEVEL: Help with feature implementation","fromName":"Aiyee Bee","fromEmail":"shane.880088.supw@gmail.com","sentAt":"2021-01-19T05:38:07Z","receivedAt":"2021-01-19T06:39:37Z","isPatch":false,"sender":{"key":"shane.880088.supw@gmail.com","avatar":null},"body":"Hi Derrick and Junio!\n\nThanks for confirming my suspicions, that there isn't existing apparatus\nfor doing this, and a new bit can be added as a flag. Thanks for the\n*pointers, I'll try working it out! With Antonio, in fact, since they'd\nneed the same thing for implementing the opposite feature.\n\nAs for the justification, to elaborate on what I said in the opening mail:\n\nThis option would be pretty useful when used with diff options, to see how\nmuch two forks have diverged. I recently wanted to compare two long-running\nforks of a project and see how far they have diverged. I used the options:\n--simplufy-by-decoration --decorate-refs=\"refs/remotes/*/main\" -p\n\nBut currently with this history simplification, the diffs for both divergent\nhistories will be created against the last \"relevant\" (decorated) commit\ninstead of the last common ancestor, which creates pretty useless diffs with\na lot of intersection between them.\n\nYou're right that the option doesn't sound very useful when thought of in\nregards to history limiting by path, but IMO it's pretty useful in cases\nlike these, when you use simplify to get an 'overview' of the history.\n\nAlso sorry for the blank/duplicate emails everyone! My email client seems to\nbe misbehaving, largely because I tried to tinker with it :P\n\n- Aiyee Bee\n"},{"id":"414660","messageId":"C8MW35119PZ3.3DYS0P3OSK9ZU@localhost","threadId":"55003","inReplyTo":"5e5ece7c-3f34-caa1-db87-084b42c1cb62@gmail.com","subject":"Re: DEVEL: Help with feature implementation","fromName":"Aiyee Bee","fromEmail":"shane.880088.supw@gmail.com","sentAt":"2021-01-19T05:35:54Z","receivedAt":"2021-01-19T06:41:58Z","isPatch":false,"sender":{"key":"shane.880088.supw@gmail.com","avatar":null},"body":""},{"id":"414683","messageId":"9fc9d752-06f4-e75d-1549-f257fd34e0c3@aerusso.net","threadId":"55003","inReplyTo":"xmqq7do9iuqj.fsf@gitster.c.googlers.com","subject":"Re: DEVEL: Help with feature implementation","fromName":"Antonio Russo","fromEmail":"aerusso@aerusso.net","sentAt":"2021-01-19T14:52:37Z","receivedAt":"2021-01-19T15:09:27Z","isPatch":false,"sender":{"key":"aerusso@aerusso.net","avatar":"https://avatars.githubusercontent.com/u/6502699?v=4"},"body":"On 1/18/21 6:24 PM, Junio C Hamano wrote:\n> Antonio Russo <aerusso@aerusso.net> writes:\n> \n>> As a side note, would this list be willing to look at patches that remove\n>> the need to use revs->limited?  Adding new features would be much easier if\n>> we could restrict git to use streaming algorithms for these simplifications.\n> \n> Do you mean you will write new implementations of operations like\n> \"--simplify-merges\", \"--ancestory-path\" and all its friends without\n> the need for the \"limited\" bit?\n\nYes.\n\n> Willing to look at?  I do not know about others, but sure, it would\n> make be extremely excited.\n> \n> You may be able to rewrite some other operations that implicitly\n> require the limited bit into an incremental implementation, but I am\n> skeptical that you can do \"simplify-merges\" in a streaming fashion\n> in such a way that we'd dig a bit but not all the way down before\n> making decisions on which commits should be included in the output\n> and how their parenthood relationship should appear etc.  I and\n> Linus tried independently and we did not get that far in our\n> attempts (note: there wasn't commit-graph back then).\n\nYeah, it's a big task (but, it'd be useful work, rather than doing\nanother rewrite of my feature to make it work when revs->limited).\nEach of the flags (simplify-merges, ancestry-path, etc.) is its own\nlittle sub-project.\n\nI haven't thought about any one flag specifically, but the fact that\ntwo complete code paths exist right now just seem like a nightmare.\nI'm not necessarily interested in making the implementations faster,\nbut rather getting rid of the duplicated code path.\n\nIt's also a long-term goal, but it's nice to hear that people would\nbe interested in it.\n\n> If you are talking about precomputed stuff like commit-graph, that\n> may change the equation, but we'd prefer to have the system work\n> without requiring these auxiliary data (in other words, it would be\n> fine to use them as optimization).\n\nNo, I understand that generation numbers can only be used as an\noptimization (i.e., they might all be GENERATION_NUMBER_INFINITY).\n"},{"id":"414684","messageId":"0a83391e-3cf3-49a7-e558-ef726b9432fb@aerusso.net","threadId":"55003","inReplyTo":"5e5ece7c-3f34-caa1-db87-084b42c1cb62@gmail.com","subject":"Re: DEVEL: Help with feature implementation","fromName":"Antonio Russo","fromEmail":"aerusso@aerusso.net","sentAt":"2021-01-19T15:13:46Z","receivedAt":"2021-01-19T15:16:41Z","isPatch":false,"sender":{"key":"aerusso@aerusso.net","avatar":"https://avatars.githubusercontent.com/u/6502699?v=4"},"body":"\n\nOn 1/18/21 7:39 PM, Derrick Stolee wrote:\n> On 1/18/2021 7:54 PM, Antonio Russo wrote:\n>> On 1/18/21 1:58 PM, Derrick Stolee wrote:\n>>> On 1/18/2021 2:31 PM, Aiyee Bee wrote:\n>>>> Hi Antonio and Derrick!\n>>>>\n>>>>> I think what you really want is --full-history --simplify-merges [1]. This\n>>>>> will show the merges that \"fork\" the history into parallel tracks where\n>>>>> at least two of them contain interesting commits.\n>>>>\n>>>> It doesn't look like the implementation of --simplify-merges helps much\n>>>> here. That makes its decision on basis of the parents of the commit, which is\n>>>> simple to do as it's information attached freely to each commit. I think the\n>>>> problem here would be figuring out, given any commit, how many of its children\n>>>> are \"relevant\" commits.\n>>>\n>>> You should definitely give this a try instead of assuming things about the\n>>> implementation. The algorithm uses a lot of \"simplifying\" that makes it look\n>>> like the decision is a local one. However, I assure you that is not the case.\n>>\n>> As a side note, would this list be willing to look at patches that remove\n>> the need to use revs->limited?  Adding new features would be much easier if\n>> we could restrict git to use streaming algorithms for these simplifications.\n> \n> I would _love_ to see patches that remove that bit (without modifying\n> the behavior).\n> \n> Fair warning: I definitely spent a few weeks attempting to do any amount\n> of reducing the depth one needs to walk in order to compute the\n> --simplify-merges history, but a sufficiently-complicated branch history\n> makes it nearly impossible to gain a benefit.\n\nThe goal I had in mind was just to remove the alternate code path, making\nnew features easier to write (i.e., you don't have to do them twice).\n\n>>> Please assemble a test case that demonstrates the behavior you want and how\n>>> that is different from what is present in --simplify-merges.\n>>\n>> I can't figure out how to get the behavior from --simplify-merges, which is\n>> described as\n>>\n>> \tAdditional option to --full-history to remove some needless\n>> \tmerges from  the resulting history, as there are no selected\n>> \tcommits contributing to this merge.\n>>\n>> It seems that the desired behavior is to include commits which are parents to\n>> multiple branches.  Here is an example:\n> \n> Thank you for these examples. They clearly show that I misread your\n> ask, because you're not looking for \"merge commits\" but instead you\n> are looking to show the \"merge bases\" as history is walking.\n> \n> Sorry for misinterpreting your request, then doubling down on it.\n\nNo problem! (Just to be clear, the is a request of shane.880088.supw,\nnot me.)\n\n> \n>> test_commit() {\n>>  echo >> file\n>>  git add file\n>>  git commit \"$@\"\n>> }\n>>\n>> git init\n>> test_commit -m a\n>> test_commit -m b\n>> test_commit -m c\n>> git checkout -b fork\n>> test_commit -m y\n>> test_commit -m z\n>> git switch master\n>> test_commit -m d\n>> test_commit -m e\n>> test_commit -m f\n>>\n>> git log --graph --oneline master fork\n>>\n>> * 08029fd f\n>> * 55b09fe e\n>> * 83b7801 d\n>> | * efc204e z\n>> | * 316219e y\n>> |/  \n>> * 3594039 c\n>> * 4321987 b\n>> * bd44220 a\n>>\n>> git log --graph --oneline --full-history --simplify-merges master fork\n>>\n>> * 08029fd f\n>> * 55b09fe e\n>> * 83b7801 d\n>> | * efc204e z\n>> | * 316219e y\n>> |/  \n>> * 3594039 c\n>> * 4321987 b\n>> * bd44220 a\n>>\n>> git log --graph --oneline --simplify-by-decoration --full-history --simplify-merges master fork\n>>\n>> * 08029fd f\n>> | * efc204e z\n>> |/  \n>> * bd44220 a\n>>\n>> git log --graph --oneline --full-history --simplify-merges master fork\n>>\n>> * 08029fd f\n>> * 55b09fe e\n>> * 83b7801 d\n>> | * efc204e z\n>> | * 316219e y\n>> |/  \n>> * 3594039 c\n>> * 4321987 b\n>> * bd44220 a\n>>\n>> git --version\n>> git version 2.30.0\n>>\n>> I can't seem to get commit c, the crucial fork, to show up with simplifications with this mechanism.\n>> Am I missing something here?\n> \n> In your example, you are not specifying a path. In this case, you are\n> really looking for \"git merge-base master fork\". You could also use\n> \"git log --boundary master...fork\" to show everything up to and\n> including 'c'.\n> \n> Now, if you specify a pathspec, then 'git merge-base' isn't going to\n> help. That becomes a technically interesting problem.\n> \n> The biggest reason that \"git log\" doesn't show this commit 'c' easily\n> is because...it's not really that important. When that commit was\n> created, it didn't \"know\" that it would be a common base of two\n> diverging branches. By surfacing the commit, we are very unlikely to\n> present the user with information that is helpful.\n\nI think shane.880088.supw's point was that it's importance is, exactly as\nyou point out, not locally computable, only arising because it is a merge\nbase.\n\n[snip (but an interesting read)]\n\n> \n> Thanks,\n> -Stolee\n>\nAntonio\n"},{"id":"414770","messageId":"ac68007e-ca66-0229-fa8f-4ceb7d6d8f23@gmail.com","threadId":"55003","inReplyTo":"9fc9d752-06f4-e75d-1549-f257fd34e0c3@aerusso.net","subject":"Re: DEVEL: Help with feature implementation","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2021-01-20T02:21:06Z","receivedAt":"2021-01-20T02:23:33Z","isPatch":false,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 1/19/2021 9:52 AM, Antonio Russo wrote:\n> On 1/18/21 6:24 PM, Junio C Hamano wrote:\n>> Antonio Russo <aerusso@aerusso.net> writes:\n>>\n>>> As a side note, would this list be willing to look at patches that remove\n>>> the need to use revs->limited?  Adding new features would be much easier if\n>>> we could restrict git to use streaming algorithms for these simplifications.\n>>\n>> Do you mean you will write new implementations of operations like\n>> \"--simplify-merges\", \"--ancestory-path\" and all its friends without\n>> the need for the \"limited\" bit?\n> \n> Yes.\n> \n>> Willing to look at?  I do not know about others, but sure, it would\n>> make be extremely excited.\n>>\n>> You may be able to rewrite some other operations that implicitly\n>> require the limited bit into an incremental implementation, but I am\n>> skeptical that you can do \"simplify-merges\" in a streaming fashion\n>> in such a way that we'd dig a bit but not all the way down before\n>> making decisions on which commits should be included in the output\n>> and how their parenthood relationship should appear etc.  I and\n>> Linus tried independently and we did not get that far in our\n>> attempts (note: there wasn't commit-graph back then).\n> \n> Yeah, it's a big task (but, it'd be useful work, rather than doing\n> another rewrite of my feature to make it work when revs->limited).\n> Each of the flags (simplify-merges, ancestry-path, etc.) is its own\n> little sub-project.\n> \n> I haven't thought about any one flag specifically, but the fact that\n> two complete code paths exist right now just seem like a nightmare.\n> I'm not necessarily interested in making the implementations faster,\n> but rather getting rid of the duplicated code path.\n\nIt's definitely a long shot to remove the limited flag altogether,\nbut a good start would be to remove sort_in_topological_order().\nAll of its logic is already re-implemented in the streaming version\n(see every use of \"struct topo_walk_info\" in revision.c). The\nstreaming is designed to be faster in the presence of a commit-graph\nfile, but it should still work correctly without one. Since all\ncommits with have \"generation number infinity,\" each phase of the\nwalk will do the same as the limit_list() and walk all reachable\ncommits before returning the first result.\n\nThe only thing to ask is: what is the overhead of the streaming\nversion over sort_in_topological_order()? Is there one? You'd need\nto do performance tests without a commit-graph file.\n\nThis has long been on my own TODO list, but I haven't been able to\nprioritize it over other things. I'd be happy to review the change.\nIt also would be a good way to familiarize yourself with the code\nand how we already do some streaming things, even when \"extra\"\ninformation is needed to accomplish that.\n\nThanks,\n-Stolee\n"}]}