{"thread":{"id":"21678","subject":"Default history simplification","startedAt":"2009-11-19T23:30:43Z","lastAt":"2009-11-21T06:37:07Z","messageCount":4,"participants":["Tommy Wang","Jan Krüger","Jeff King","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"127941","messageId":"ae09c2a40911191530y626dd035q90de0212e0b4b6d8@mail.gmail.com","threadId":"21678","inReplyTo":null,"subject":"Default history simplification","fromName":"Tommy Wang","fromEmail":"subscription@august8.net","sentAt":"2009-11-19T23:30:43Z","receivedAt":"2009-11-19T23:30:43Z","isPatch":false,"sender":{"key":"subscription@august8.net","avatar":null},"body":"Hi all,\n\nI'm working on a small perl script that needs to reproduce the results\nof the default git history simplification used by log & rev-list when\na list of paths is given. It is important that I reproduce its\nresults exactly. I would love to simply use the rev-list built-in to\ndo my work for me; but I fear that I may have much too many path\nlimiters than the linux command-line can handle (which if I'm correct,\ncan only take so many arguments).\n\nI can understand whether a commit is included or not rather easily: we\nbasically only include a commit iff the commit introduces a change to\nthe given path (ie, it is !TREESAME to any of its parents).\n\nFor merges, I get a little confused. In the simple case of a 2-parent\nmerge, if we find that we are TREESAME with one parent -- it follows\nthat the interesting change must have come from that parent. So we\nfollow it, and can safely assume that the other parent is\nuninteresting.\n\nIf we find that we are TREESAME with both parents, it follows that\nneither parent nor the merge commit is interesting. Therefore, we\nrandomly pick the first parent and move up the graph looking for an\ninteresting commit. Looking at this more closely, the parents we\nignored will fall under three scenarios:\n\n1. It finds it way all the way up to a root commit without finding an\ninteresting commit -- which can happen if your repository has multiple\nroot commits.\n2. It will move up the graph and eventually find a common ancestor\nwith the first parent.\n3. It will find an interesting commit that has an identical/equivalent\ncommit somewhere in the first parent's ancestry.\n\nIn all 3 cases, it is safe to follow just the first TREESAME parent.\nIt is interesting to note that if are working with a repository with\nmultiple root commits (say, you imported a project without history,\nand later merged in its upstream history), you could potentially lose\nthat history with this algorithm if you happened to merge it as the\nsecond parent. This is not necessarily a flaw (in fact, it may be a\nfeature!), since you have still fully explained the state of your HEAD\nwith respect to the first parent (which is probably your mainline).\n\nIn the case that neither parent was TREESAME, we can have 2 scenarios:\n\n1. The merge commit itself made the interesting change.\n2. The interesting changes came from both parents, in which we would\nrightfully follow both parents.\n\nMy first question is this:\n\nIf the merge commit itself (D) made the interesting change, we could\npotentially follow an uninteresting parent -- most likely all the way\nup until we find a common ancestor (A). This would produce a graph\nthat looks like:\n\nA---B---D\n \\-------/ (C pruned)\n\nOr, if both parents were uninteresting:\n\nA---D (both B & C pruned)\n \\---/\n\nI assume that the simplification takes care of this by removing\nduplicate parents as well as searching for common ancestors? (It is\nnot mentioned in the documentation).\n\nMy second question is then:\n\nGiven that we perform an extra simplification pass to remove common\nancestors and duplicate parents, what is the purpose of selectively\nfollowing parents? Is it just for speed? If we always followed all\nparents and applied our duplicate simplification and common ancestor\nsimplification, we would not always arrive at the same result? In\nwhich case, if my application is not concerned with speed (ie, I don't\nmind following all parents), would I always arrive at the same graph?\n\nThanks,\n\nTommy\n"},{"id":"127986","messageId":"20091120095537.1909f6b6@perceptron","threadId":"21678","inReplyTo":"ae09c2a40911191530y626dd035q90de0212e0b4b6d8@mail.gmail.com","subject":"Re: Default history simplification","fromName":"Jan Krüger","fromEmail":"jk@jk.gs","sentAt":"2009-11-20T08:55:37Z","receivedAt":"2009-11-20T08:55:37Z","isPatch":false,"sender":{"key":"jk@jk.gs","avatar":"https://avatars.githubusercontent.com/u/1774?v=4"},"body":"Hi,\n\nTommy Wang wrote:\n> [...] I would love to simply use the rev-list built-in to\n> do my work for me; but I fear that I may have much too many path\n> limiters than the linux command-line can handle (which if I'm correct,\n> can only take so many arguments).\n\nOn my system, \"only so many arguments\" means about two megabytes worth\nof command line. On several operating systems, \"getconf ARG_MAX\" can\ntell you the approximate limit (which I think includes the space for\nenvironment variables).\n\nI don't really have any comments about the other things you said.\n\nJan\n"},{"id":"128020","messageId":"20091120144146.GC5419@coredump.intra.peff.net","threadId":"21678","inReplyTo":"ae09c2a40911191530y626dd035q90de0212e0b4b6d8@mail.gmail.com","subject":"Re: Default history simplification","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-11-20T14:41:46Z","receivedAt":"2009-11-20T14:41:46Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Nov 19, 2009 at 05:30:43PM -0600, Tommy Wang wrote:\n\n> I'm working on a small perl script that needs to reproduce the results\n> of the default git history simplification used by log & rev-list when\n> a list of paths is given. It is important that I reproduce its\n> results exactly. I would love to simply use the rev-list built-in to\n> do my work for me; but I fear that I may have much too many path\n> limiters than the linux command-line can handle (which if I'm correct,\n> can only take so many arguments).\n\nFYI, Junio just posted a patch for handling pathspec limiting over\n--stdin, which would solve this problem for you.\n\n http://article.gmane.org/gmane.comp.version-control.git/133333\n\n-Peff\n"},{"id":"128062","messageId":"7v8we0s7sc.fsf@alter.siamese.dyndns.org","threadId":"21678","inReplyTo":"20091120095537.1909f6b6@perceptron","subject":"Re: Default history simplification","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-11-21T06:37:07Z","receivedAt":"2009-11-21T06:37:07Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jan Krüger writes:\n\n> Tommy Wang wrote:\n>> [...] I would love to simply use the rev-list built-in to\n>> do my work for me; but I fear that I may have much too many path\n>> limiters than the linux command-line can handle (which if I'm correct,\n>> can only take so many arguments).\n>\n> On my system, \"only so many arguments\" means about two megabytes worth\n> of command line.\n\nGood point.\n\nThe command line limitation, even if it is very small, shouldn't be a\nproblem if Tommy is interested in recreating exactly what rev-list does.\n\nIf his tool that drives rev-list or log from the command line cannot work\nbecause his request overflows the command line, the same request will\noverflow the command line for rev-list or log, so they wouldn't work\neither.\n\nFor a more serious answer, see the other thread ;-).\n"}]}