{"thread":{"id":"14578","subject":"Bizarre missing changes (git bug?)","startedAt":"2008-07-21T20:26:06Z","lastAt":"2008-08-01T07:50:28Z","messageCount":58,"participants":["Tim Harper","Linus Torvalds","Alex Riesen","Roman Zippel","Martin Langhoff","Jeff King","David Kastrup","Olivier Galibert","Kevin Ballard","Jakub Narebski","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"84236","messageId":"8502DF7C-5303-49E8-8C67-F837343E2F0C@gmail.com","threadId":"14578","inReplyTo":null,"subject":"Bizarre missing changes (git bug?)","fromName":"Tim Harper","fromEmail":"timcharper@gmail.com","sentAt":"2008-07-21T20:26:06Z","receivedAt":"2008-07-21T20:26:06Z","isPatch":false,"sender":{"key":"timcharper@gmail.com","avatar":"https://gravatar.com/avatar/1a2e0c06c7862ff065ee6b1d53195333a5a0577c040ecb2856a150d8e0b00ecd?d=mp&s=160"},"body":"I ran into a strange issue that has left me scratching my head.\n\nI have a commit in my history, that does indeed show up in my branch, \nnamed \"sprint\"\n\nThe following commands yield as follows (I've modified the output \nslightly to conceal any potentially proprietary information):\n\n#########################\ngit log HEAD -p\n\ncommit 8f9effffb0dcdacd514085608e8923fbbe00ff29\nAuthor: Name Concealed \nDate: Mon Jul 14 16:19:18 2008 -0600\n\n commit message....\n\ndiff --git a/app/controllers/events_controller.rb b/app/controllers/ \nevents_controller.rb\nindex 6905ba4..a0b7dfc 100644\n--- a/app/controllers/events_controller.rb\n+++ b/app/controllers/events_controller.rb\n@@ -238,36 +238,37 @@ class EventsController < ApplicationController\n }.freeze\n\n RUBY_STUFF = {\n- changes...\n- changes...\n- changes...\n+ changes...\n+ changes...\n+ changes...\n\ndiff --git a/spec/fixtures/factors.yml b/spec/fixtures/factors.yml\nindex 186ed73..3c76e86 100755\n--- a/spec/fixtures/factors.yml\n+++ b/spec/fixtures/factors.yml\n@@ -2483,4 +2483,54 @@ some_branch:\n file:\n contents:\n- reliable_on:\n\\ No newline at end of file\n+ data:\n+fixture_name:\n+ id: 115\n+ file: Event\n+ contents: behavior\n\n\n#########################\ngit log spec/fixtures/factors.yml\n\n... commit 8f9effff is not listed anywhere\n\n#########################\ngit log app/controllers/events_controller.rb\n\n... commit 8f9effff shows up\n\n#########################\ngit branch --contains 8f9effff\n\n some-task-branch\n* sprint\n\n\nThe changes in 8f9effff for app/controllers/events_controller.rb show \nup in the working copy, however the changes for spec/fixtures/ \nfactors.yml are nowhere to be seen. It's as if the history of that \nparticular file diverged somehow, but I know that can't be true since \ngit doesn't track files.\n\nAnyone run into this before? Any idea what might have caused it? \nWe're a bit concerned about this because if we don't know how to avoid \nthis, we no longer can feel certain that when something is committed, \nit will make it out in our release.\n\nAny help or clues VERY much apperciated. Thanks!\n\nTim\n"},{"id":"84237","messageId":"alpine.LFD.1.10.0807211331390.31863@woody.linux-foundation.org","threadId":"14578","inReplyTo":"8502DF7C-5303-49E8-8C67-F837343E2F0C@gmail.com","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-21T20:37:34Z","receivedAt":"2008-07-21T20:37:34Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 21 Jul 2008, Tim Harper wrote:\n> \n> Anyone run into this before? Any idea what might have caused it? We're a bit\n> concerned about this because if we don't know how to avoid this, we no longer\n> can feel certain that when something is committed, it will make it out in our\n> release.\n\nRead up on '--full-history'.\n\nBy default, git simplifies the history for logs that have path \nsimplification: only walking down the side of a merge that all the data \ncame from (ie the unchanged side). So it only leaves merges around if \nthere was changes from _all_ parents.\n\nSo without --full-history, if any parent matches the state, it just \nremoves the merge and picks that parent that contained all the state. \nObviously, any changes to that file can be sufficiently explained by \nwalking just that limited history, because they must have changed in \n_that_ history too!\n\nThat default behaviour leads to a *much* simpler history, and is usually \nwhat you want - it avoids unnecessary duplication when something was \nchanged trivially the same way in both branches - 'git log' will just pick \nthe first branch.\n\nSo, if you had two (or more) commits that both fixed the same bug in \ndifferent branches, and thus both branches actually ended up with the same \ncontents, it does mean that \"git log \" will only show _one_ of \nthe fixes.\n\nIn this case, it apparently showed another version than the one you were \nlooking for.\n\n\t\t\t\tLinus\n"},{"id":"84238","messageId":"20080721204243.GA4748@blimp.local","threadId":"14578","inReplyTo":"8502DF7C-5303-49E8-8C67-F837343E2F0C@gmail.com","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2008-07-21T20:42:43Z","receivedAt":"2008-07-21T20:42:43Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Tim Harper, Mon, Jul 21, 2008 22:26:06 +0200:\n> I ran into a strange issue that has left me scratching my head.\n>\n> I have a commit in my history, that does indeed show up in my branch, \n> named \"sprint\"\n>\n...\n>\n> Any help or clues VERY much apperciated. Thanks!\n>\n\nTry looking at the history graph in gitk\n\n $ gitk --all -- app/controllers/events_controller.rb spec/fixtures/factors.yml\n\nIt usually shows the history in a very understandable way and\nit can help to detect when the histories have diverged.\n"},{"id":"84249","messageId":"E301C92A-8794-4E90-9C85-D73B94A2648C@gmail.com","threadId":"14578","inReplyTo":"alpine.LFD.1.10.0807211331390.31863@woody.linux-foundation.org","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Tim Harper","fromEmail":"timcharper@gmail.com","sentAt":"2008-07-21T22:53:55Z","receivedAt":"2008-07-21T22:53:55Z","isPatch":false,"sender":{"key":"timcharper@gmail.com","avatar":"https://gravatar.com/avatar/1a2e0c06c7862ff065ee6b1d53195333a5a0577c040ecb2856a150d8e0b00ecd?d=mp&s=160"},"body":"\nOn Jul 21, 2008, at 2:37 PM, Linus Torvalds wrote:\n\n>\n>\n> On Mon, 21 Jul 2008, Tim Harper wrote:\n>>\n>> Anyone run into this before? Any idea what might have caused it? \n>> We're a bit\n>> concerned about this because if we don't know how to avoid this, we \n>> no longer\n>> can feel certain that when something is committed, it will make it \n>> out in our\n>> release.\n>\n> Read up on '--full-history'.\n>\n> By default, git simplifies the history for logs that have path\n> simplification: only walking down the side of a merge that all the \n> data\n> came from (ie the unchanged side). So it only leaves merges around if\n> there was changes from _all_ parents.\n>\n> So without --full-history, if any parent matches the state, it just\n> removes the merge and picks that parent that contained all the state.\n> Obviously, any changes to that file can be sufficiently explained by\n> walking just that limited history, because they must have changed in\n> _that_ history too!\n>\n> That default behaviour leads to a *much* simpler history, and is \n> usually\n> what you want - it avoids unnecessary duplication when something was\n> changed trivially the same way in both branches - 'git log' will \n> just pick\n> the first branch.\n>\n\nAgreed - this was an insightful decision.\n\n> So, if you had two (or more) commits that both fixed the same bug in\n> different branches, and thus both branches actually ended up with \n> the same\n> contents, it does mean that \"git log \" will only show \n> _one_ of\n> the fixes.\n>\n> In this case, it apparently showed another version than the one you \n> were\n> looking for.\n>\n> \t\t\t\tLinus\n\nGit has made me feel stupid on various occasions. This is no \nexception as the problem turned out being in the chair, not in git.\n\nAfter running through git bisect, and ran the command Alex Riesen \nsuggested, it made it pretty crystal clear where things went wrong. \nIt turned out to be a bad merge that was from a conflict related to \nwhite-space issues, and the wrong resolution was chosen (a resolution \nthat also consequently turned out to be no change).\n\nAnother false impression I had is a merge conflict resolution would \nalways be displayed in a merge commit. However, after running over \nthe merges again, if you pick the right or left, discarding the one or \nthe other, nothing is shown in \"git log -p\" for the merge commit. Is \nthere a way to see what was chosen for a conflict resolution? Seeing \nthat in the merge commit would have made things a little more clear.\n\nThank you for articulating git branch's behavior - all is clear as mud \nnow :)\n\nTim\n"},{"id":"84250","messageId":"191E68A7-7F91-48E7-BC47-BEC74CC7EC42@gmail.com","threadId":"14578","inReplyTo":"E301C92A-8794-4E90-9C85-D73B94A2648C@gmail.com","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Tim Harper","fromEmail":"timcharper@gmail.com","sentAt":"2008-07-21T22:55:24Z","receivedAt":"2008-07-21T22:55:24Z","isPatch":false,"sender":{"key":"timcharper@gmail.com","avatar":"https://gravatar.com/avatar/1a2e0c06c7862ff065ee6b1d53195333a5a0577c040ecb2856a150d8e0b00ecd?d=mp&s=160"},"body":"\nOn Jul 21, 2008, at 4:53 PM, Tim Harper wrote:\n\n>\n> On Jul 21, 2008, at 2:37 PM, Linus Torvalds wrote:\n>\n>>\n>>\n>> On Mon, 21 Jul 2008, Tim Harper wrote:\n>>>\n>>> Anyone run into this before? Any idea what might have caused it? \n>>> We're a bit\n>>> concerned about this because if we don't know how to avoid this, \n>>> we no longer\n>>> can feel certain that when something is committed, it will make it \n>>> out in our\n>>> release.\n>>\n>> Read up on '--full-history'.\n>>\n>> By default, git simplifies the history for logs that have path\n>> simplification: only walking down the side of a merge that all the \n>> data\n>> came from (ie the unchanged side). So it only leaves merges around if\n>> there was changes from _all_ parents.\n>>\n>> So without --full-history, if any parent matches the state, it just\n>> removes the merge and picks that parent that contained all the state.\n>> Obviously, any changes to that file can be sufficiently explained by\n>> walking just that limited history, because they must have changed in\n>> _that_ history too!\n>>\n>> That default behaviour leads to a *much* simpler history, and is \n>> usually\n>> what you want - it avoids unnecessary duplication when something was\n>> changed trivially the same way in both branches - 'git log' will \n>> just pick\n>> the first branch.\n>>\n>\n> Agreed - this was an insightful decision.\n>\n>> So, if you had two (or more) commits that both fixed the same bug in\n>> different branches, and thus both branches actually ended up with \n>> the same\n>> contents, it does mean that \"git log \" will only show \n>> _one_ of\n>> the fixes.\n>>\n>> In this case, it apparently showed another version than the one you \n>> were\n>> looking for.\n>>\n>> \t\t\t\tLinus\n>\n> Git has made me feel stupid on various occasions. This is no \n> exception as the problem turned out being in the chair, not in git.\n>\n> After running through git bisect, and ran the command Alex Riesen \n> suggested, it made it pretty crystal clear where things went wrong. \n> It turned out to be a bad merge that was from a conflict related to \n> white-space issues, and the wrong resolution was chosen (a \n> resolution that also consequently turned out to be no change).\n>\n> Another false impression I had is a merge conflict resolution would \n> always be displayed in a merge commit. However, after running over \n> the merges again, if you pick the right or left, discarding the one \n> or the other, nothing is shown in \"git log -p\" for the merge \n> commit. Is there a way to see what was chosen for a conflict \n> resolution? Seeing that in the merge commit would have made things \n> a little more clear.\n>\n\nActually, I found it:\n\nhttp://www.kernel.org/pub/software/scm/git/docs/git-log.html\n\n\"git log -p -c\" gives me what I was looking for\n\nTim\n\n> Thank you for articulating git branch's behavior - all is clear as \n> mud now :)\n>\n> Tim\n"},{"id":"84251","messageId":"alpine.LFD.1.10.0807211546590.3007@woody.linux-foundation.org","threadId":"14578","inReplyTo":"8C23FB54-A28E-4294-ABEA-A5766200768B@gmail.com","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-21T22:57:58Z","receivedAt":"2008-07-21T22:57:58Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n[ git channel added back to cc, because this is an interesting question in \n itself ]\n\nOn Mon, 21 Jul 2008, Tim Harper wrote:\n> \n> Another false impression I had is a merge conflict resolution would always be\n> displayed in a merge commit. However, after running over the merges again, if\n> you pick the right or left, discarding the one or the other, nothing is shown\n> in \"git log -p\" for the merge commit. Is there a way to see what was chosen\n> for a conflict resolution? Seeing that in the merge commit would have made\n> things a little more clear.\n\nThe default behavior for showing merges is \"--cc\", which is the condensed \nversion that only shows _actual_ conflicts that got resolved differently \nfrom either of the sources.\n\nBut note how this is an \"after-the-fact\" determination: it doesn't look \nwhether the merge _did_ conflict (because doing that would require \nre-running the whole merge!), but it looks whether the end _result_ is \ndifferent from either side.\n\nSo you can easily have a merge that conflicts - but then you resolve that \nmerge by picking just one side of the merge as the result. And in that \ncase the \"--cc\" diff will not show anything at all - because the end \nresult did not conflict with the sources of the merge!\n\nSo \"--cc\" only shows output if: the merge itself actually changed \nsomething from _all_ parents. This can happen if:\n\n - there was a non-trivial conflict, and the end result really was a \n \"mixture\" of the two. The result wasn't just a select of either side, \n it was a combination of the two.\n\n This is obviously one \"common\" case for a merge resolution.\n\n But it's equally common that when you merge something you just say \"Ok, \n that other side did it better, I'll just pick that version\". And in \n that case, \"--cc\" won't show anything at all, because it's not really a \n conflict any more once you've done that choice.\n\n - There can also be an \"evil merge\" that actually adds/changes/deletes \n code that didn't exist AT ALL in either side. And --cc is very much \n designed to show that.\n\n This is actually not always a bad thing (despite the name \"evil \n merge\"), because it happens regularly that one branch had changed some \n infrastructure setup or other, and the other branch had added a totally \n new use of that infrastructure - and as a result the _merge_ needs to \n add that setup code that didn't exist in either of the branches (in one \n because the use wasn't there, in the other because the setup wasn't \n needed).\n\nAnyway, this all means that yes, \"--cc\" _often_ shows conflicts, but not \nalways - exactly because it doesn't show the ones that the merge had \ncommitted as a non-conflict.\n\nIf you actually want to see the _real_ conflicts that happened as the \nmerge was done, you do have to re-do it. \n\n\t\tLinus\n"},{"id":"84997","messageId":"200807260512.40088.zippel@linux-m68k.org","threadId":"14578","inReplyTo":"alpine.LFD.1.10.0807211331390.31863@woody.linux-foundation.org","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Roman Zippel","fromEmail":"zippel@linux-m68k.org","sentAt":"2008-07-26T03:12:38Z","receivedAt":"2008-07-26T03:12:38Z","isPatch":false,"sender":{"key":"zippel@linux-m68k.org","avatar":null},"body":"Hi,\n\nOn Monday 21. July 2008, Linus Torvalds wrote:\n\n> Read up on '--full-history'.\n>\n> By default, git simplifies the history for logs that have path\n> simplification: only walking down the side of a merge that all the data\n> came from (ie the unchanged side). So it only leaves merges around if\n> there was changes from _all_ parents.\n>\n> So without --full-history, if any parent matches the state, it just\n> removes the merge and picks that parent that contained all the state.\n> Obviously, any changes to that file can be sufficiently explained by\n> walking just that limited history, because they must have changed in\n> _that_ history too!\n\nIs that really a good default behaviour? Is there a way to change that \ndefault?\n\nI'm currently looking into converting the m68k CVS repository and I'd like to \nproperly regenerate it as two separate lines of development. The problem is \nif I look at the file history, I often only see one side of the changes when \nthings got merged because of this default.\nWhat makes this worse is that graphical front ends may inherit this behaviour. \nI tested this with qgit and it only shows half of the history. giggle \nretrieves the history like --full-history, but it lacks empty merges, so it \nmakes it harder to see what got merged when.\nFor example a history that actually looks this:\n\nlinux -+-----import----+-----------import----+------...\nm68k \\-commit-commit-\\-merge-commit-commit-\\-merge...\n\nWithout the merges it looks like this:\n\nlinux -+-----import----------------import--------------+...\nm68k \\-commit-commit---------commit-commit \\...\n\nAnd without --full-history these \"loose ends\" aren't visible as in qgit.\n\nWhen researching historical changes one wants to know when something was \nintroduced and when it was merged, but this simplification makes it harder \nthan it really has to be.\nIMO the default should be to show the complete history, so one doesn't miss \nsomething by accident that might be important or as the original example \nshows it might be confusing if one sees a change with \"git log --stat id..\" \nand the change disappears when one looks at \"git log path\".\n\nbye, Roman\n"},{"id":"85111","messageId":"alpine.LFD.1.10.0807261249430.4188@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"200807260512.40088.zippel@linux-m68k.org","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-26T19:58:21Z","receivedAt":"2008-07-26T19:58:21Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 26 Jul 2008, Roman Zippel wrote:\n> >\n> > So without --full-history, if any parent matches the state, it just\n> > removes the merge and picks that parent that contained all the state.\n> > Obviously, any changes to that file can be sufficiently explained by\n> > walking just that limited history, because they must have changed in\n> > _that_ history too!\n> \n> Is that really a good default behaviour?\n\nYes. It's the only sane default right now. See below.\n\n> Is there a way to change that default?\n\nUse an alias or something.\n\nTo see why it's the default, do a few tests. In particular, try it with \ngitk on the kernel. Try it on some fairly simple file that doesn't get a \nlot of churn. Example:\n\n\tgitk lib/vsprintf.c\n\nvs\n\n\tgitk --full-history lib/vsprintf.c\n\nand if you don't _immediately_ see why --full-history isn't the default, \nthere's likely something wrong with you. One is useful. The other is not.\n\nSo we absolutely _have_ to simplify merges. There is no question about it.\n\nThat said, we currently simplify merges the simple and stupid way, and \nI've hinted several times on this mailing list that there is a better way \nto do it (last time it was the discussion about \"filter-branch\".\n\nIn fact, if you google for \n\n\tfilter-branch full-history\n\nyou'll find some of the discussion. In order to make --full-history useful \nas a default, we'd need to do an after-the-fact merge cleanup (ie remove \nlines of development that are later found to really be totally \nuninteresting), but that is *hard*.\n\nBut if we did that, I'd agree to making --full-history the default (and it \nwould be a good thing, no doubt about it - I just cannot see how to do ti \nsimply and sanely enough)\n\n\t\tLinus\n"},{"id":"85181","messageId":"Pine.LNX.4.64.0807270049290.6791@localhost.localdomain","threadId":"14578","inReplyTo":"alpine.LFD.1.10.0807261249430.4188@nehalem.linux-foundation.org","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Roman Zippel","fromEmail":"zippel@linux-m68k.org","sentAt":"2008-07-27T17:50:55Z","receivedAt":"2008-07-27T17:50:55Z","isPatch":false,"sender":{"key":"zippel@linux-m68k.org","avatar":null},"body":"Hi,\n\nOn Sat, 26 Jul 2008, Linus Torvalds wrote:\n\n> > Is there a way to change that default?\n> \n> Use an alias or something.\n\nThis doesn't help with the graphical front ends and they only use what git \ngives them.\n\n> To see why it's the default, do a few tests. In particular, try it with \n> gitk on the kernel. Try it on some fairly simple file that doesn't get a \n> lot of churn. Example:\n> \n> \tgitk lib/vsprintf.c\n> \n> vs\n> \n> \tgitk --full-history lib/vsprintf.c\n> \n> and if you don't _immediately_ see why --full-history isn't the default, \n> there's likely something wrong with you. One is useful. The other is not.\n> \n> So we absolutely _have_ to simplify merges. There is no question about it.\n\nWell, I don't want that much history.\nLet's take a different example. Look at kernel/sched_rt.c with git-log, \n--full-history shows an extra commit of a patch which was committed and \nmerged twice, but there is no information how this other patch was merged. \nIf you have giggle installed, you'll see that commit as a loose end.\n\n(I have git version 1.5.6.2 installed in case it matters.)\n\n> That said, we currently simplify merges the simple and stupid way, and \n> I've hinted several times on this mailing list that there is a better way \n> to do it (last time it was the discussion about \"filter-branch\".\n> \n> In fact, if you google for \n> \n> \tfilter-branch full-history\n> \n> you'll find some of the discussion. In order to make --full-history useful \n> as a default, we'd need to do an after-the-fact merge cleanup (ie remove \n> lines of development that are later found to really be totally \n> uninteresting), but that is *hard*.\n\nI played a little with it in the ruby script below, which produces a \ncomplete connected graph of all content nodes and which have been merged \ninto the head, e.g. for sched_rt.c it produces that extra commit merge. \nThe script basically eliminates all empty merges. As input to the script I \nused \"git log --parents --name-only --full-history kernel/sched_rt.c | \ngrep -e ^commit -e ^kernel\", which seems to produce the same amount of \ncommits as \"gitk --full-history ...\".\n\nThe main function is to check, whether one parent of a commit is an \nancestor of another parent, so that this path can be eliminated. I tried \nit with other paths and too simple implementations quickly lead to \nexponential behaviour. :) It probably also shouldn't be recursive, I had \nto increase the stack limit, otherwise I got stack exceptions.\nOtherwise it seems to work fine, it wasn't that hard :-)\n\nThe ruby syntax shouldn't be too hard too read, the nonobvious thing is \nmaybe that '$' marks global variables.\n\nbye, Roman\n\n\n#! /usr/bin/ruby\n\n$parent = Hash.new\n$content = Hash.new\n$result = Hash.new\n\ncommit = nil\nhead = nil\nwhile l = $stdin.gets\n\ta = l.split(\" \")\n\tif a[0] == \"commit\"\n\t\tcommit = a[1]\n\t\thead = commit unless head\n\t\t$parent[commit] = a[2..-1]\n\telse\n\t\t$content[commit] = true\n\tend\nend\n\n$parent_check = Hash.new\n$parent_cache = Hash.new\n\ndef commit_has_parent?(commit, commit2)\n\tif $parent_check[commit]\n\t\tprint \"parent loop for #{commit} (#{commit2})?\\n\"\n\t\tp $parent_check\n\t\treturn false\n\tend\n\treturn $parent_cache[commit] if $parent_cache.has_key?(commit)\n\t$parent_check[commit] = true\n\tres = false\n\tif $content[commit] > $content[commit2]\n\t\t$parent[commit].each do |parent|\n\t\t\tif parent == commit2 || commit_has_parent?(parent, commit2)\n\t\t\t\tres = true\n\t\t\t\tbreak;\n\t\t\tend\n\t\tend\n\tend\n\t$parent_cache[commit] = res\n\t$parent_check.delete(commit)\n\t$parent_cache.clear if $parent_check.empty?\n\treturn res\nend\n\ndef check_commit(commit)\n\treturn $result[commit] if $result.has_key? commit\n\ta = Array.new\n\t$parent[commit].each do |parent|\n\t\tparent = check_commit(parent)\n\t\tif parent\n\t\t\ta.each_index do |i|\n\t\t\t\tif a[i] == parent || commit_has_parent?(a[i], parent)\n\t\t\t\t\tparent = nil\n\t\t\t\t\tbreak\n\t\t\t\telsif commit_has_parent?(parent, a[i])\n\t\t\t\t\ta[i] = parent\n\t\t\t\t\tparent = nil\n\t\t\t\t\tbreak\n\t\t\t\tend\n\t\t\tend\n\t\tend\n\t\ta.push(parent) if parent\n\tend\n\t$parent[commit] = a\n\t$content[commit] = true if a.size > 1\n\tif $content[commit]\n\t\t$result[commit] = commit\n\t\tmax = 1\n\t\ta.each do |parent|\n\t\t\tmax = $content[parent] + 1 if max <= $content[parent]\n\t\tend\n\t\t$content[commit] = max\n\telse\n\t\t$result[commit] = a[0]\n\tend\n\treturn $result[commit]\nend\n\ncheck_commit(head)\n#p $result\n#p $parent\n\np $content.keys.size\n$content.each_key do |commit|\n\tp [ commit, $parent[commit] ]\n\tcommit = $parent[commit][0]\nend\n"},{"id":"85189","messageId":"alpine.LFD.1.10.0807271144520.3486@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807270049290.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-27T18:47:18Z","receivedAt":"2008-07-27T18:47:18Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 27 Jul 2008, Roman Zippel wrote:\n\n> Hi,\n> \n> On Sat, 26 Jul 2008, Linus Torvalds wrote:\n> \n> > > Is there a way to change that default?\n> > \n> > Use an alias or something.\n> \n> This doesn't help with the graphical front ends and they only use what git \n> gives them.\n\nAnd the graphical front-ends is exactly why --full-history cannot be the \ndefault.\n\nWe _could_ make it the default for non-graphical ones, if we also say \n\"--no-merges\". But then:\n\n> > To see why it's the default, do a few tests. In particular, try it with \n> > gitk on the kernel. Try it on some fairly simple file that doesn't get a \n> > lot of churn. Example:\n> > \n> > \tgitk lib/vsprintf.c\n> > \n> > vs\n> > \n> > \tgitk --full-history lib/vsprintf.c\n> > \n> > and if you don't _immediately_ see why --full-history isn't the default, \n> > there's likely something wrong with you. One is useful. The other is not.\n> > \n> > So we absolutely _have_ to simplify merges. There is no question about it.\n> \n> Well, I don't want that much history.\n\nRight. Nobody does.\n\n> Let's take a different example.\n\nNo, let's not.\n\nUnless you can solve that _one_ example efficiently, nothing else matters. \n\nThe above example is all you ever need. Make that one work right (and \nefficiently), and everything is fine.\n\nAnd no, some random ruby code doesn't make any difference what-so-ever. \nThere are efficiency constraints here that make any ruby solution be \nunrealistic to begin with.\n\n\t\t\tLinus\n"},{"id":"85206","messageId":"Pine.LNX.4.64.0807272101470.6791@localhost.localdomain","threadId":"14578","inReplyTo":"alpine.LFD.1.10.0807271144520.3486@nehalem.linux-foundation.org","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Roman Zippel","fromEmail":"zippel@linux-m68k.org","sentAt":"2008-07-27T23:14:09Z","receivedAt":"2008-07-27T23:14:09Z","isPatch":false,"sender":{"key":"zippel@linux-m68k.org","avatar":null},"body":"Hi,\n\nOn Sun, 27 Jul 2008, Linus Torvalds wrote:\n\n> > > > Is there a way to change that default?\n> > > \n> > > Use an alias or something.\n> > \n> > This doesn't help with the graphical front ends and they only use what git \n> > gives them.\n> \n> And the graphical front-ends is exactly why --full-history cannot be the \n> default.\n\nIf you mean current gitk style --full-history I agree, the problem is \nstill that git is hiding too much history with the simplified history...\n\n> > Let's take a different example.\n> \n> No, let's not.\n> \n> Unless you can solve that _one_ example efficiently, nothing else matters. \n> \n> The above example is all you ever need. Make that one work right (and \n> efficiently), and everything is fine.\n> \n> And no, some random ruby code doesn't make any difference what-so-ever. \n> There are efficiency constraints here that make any ruby solution be \n> unrealistic to begin with.\n\nWhy are you dismissing what I wrote without even giving it a second \nthought? I didn't bother with the initial example, because it's so \nsimple, that it's no real challenge.\nDid I say anywhere it had to be done in ruby? All I tried was to \ndemonstrate a possible algorithm to solve the problem. I did time the \nexecution and compared to the time it took to extract the history it \nwasn't significant for such a simple script.\nWhat did I do wrong that you rebuff me based on this secondary problem \n(which I'm quite aware of, because it was me who mentioned in first place) \nand giving the primary problem (which is the missing history) no \nattention?\n\nIf you had any questions, I'd be happy to answer them. If you think that \nthe demonstrated algorithm doesn't work, I'd be glad to know why. If the \nalgorithm might work, any hint what could be do done to try it for real, \nwould be great. But I don't get any of this. Why?\n\nbye, Roman\n"},{"id":"85208","messageId":"alpine.LFD.1.10.0807271613440.3486@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807272101470.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-27T23:18:05Z","receivedAt":"2008-07-27T23:18:05Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 28 Jul 2008, Roman Zippel wrote:\n> \n> Why are you dismissing what I wrote without even giving it a second \n> thought? I didn't bother with the initial example, because it's so \n> simple, that it's no real challenge.\n\nDid you try it? It really shouldn't be any simpler than anything else. And \nI dismissed what you wrote because the example you _did_ state was about \nsomething else entirely (ie apparently some giggle bug that simplifies \nthings incorrectly).\n\n> What did I do wrong that you rebuff me based on this secondary problem \n> (which I'm quite aware of, because it was me who mentioned in first place) \n> and giving the primary problem (which is the missing history) no \n> attention?\n\nIt's not missing history. It's all there in --full-history. The default is \nto give a reasonable simplification, and I told you what the \nsimplification was, and it's perfectly conceptually fine - AND IT IS MUCH \nMORE EFFICIENT than the alternatives.\n\nSo I'm not seeing your point what-so-ever. \n\nMy point is:\n\n - with full-history, you have it all, but it's useless in practice\n\n - without full-history, it's useful in practice\n\nYou never gave any examples otherwise.\n\n\t\t\tLinus\n"},{"id":"85209","messageId":"46a038f90807271625x35c561fdv6dc6b2c312f45fa1@mail.gmail.com","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807272101470.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2008-07-27T23:25:07Z","receivedAt":"2008-07-27T23:25:07Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On Mon, Jul 28, 2008 at 11:14 AM, Roman Zippel wrote:\n> Why are you dismissing what I wrote without even giving it a second\n> thought? I didn't bother with the initial example, because it's so\n> simple, that it's no real challenge.\n\nI can't speak for anyone else, but you do have to keep in mind that a\nsolution to this has to be rather fast - and I mean fast in git terms,\nnot in scripting-language-fast terms.\n\nThat you can do it Ruby - and I may be able to do it Perl - has little\nbearing on what can be done inside the git log machinery with a small\nperformance penalty.\n\ncheers,\n\n\n\nm\n-- \n martin.langhoff@gmail.com\n martin@laptop.org -- School Server Architect\n - ask interesting questions\n - don't get distracted with shiny stuff - working code first\n - http://wiki.laptop.org/go/User:Martinlanghoff\n"},{"id":"85210","messageId":"Pine.LNX.4.64.0807280141140.6791@localhost.localdomain","threadId":"14578","inReplyTo":"alpine.LFD.1.10.0807271613440.3486@nehalem.linux-foundation.org","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Roman Zippel","fromEmail":"zippel@linux-m68k.org","sentAt":"2008-07-28T00:00:41Z","receivedAt":"2008-07-28T00:00:41Z","isPatch":false,"sender":{"key":"zippel@linux-m68k.org","avatar":null},"body":"Hi,\n\nOn Sun, 27 Jul 2008, Linus Torvalds wrote:\n\n> > Why are you dismissing what I wrote without even giving it a second \n> > thought? I didn't bother with the initial example, because it's so \n> > simple, that it's no real challenge.\n> \n> Did you try it? It really shouldn't be any simpler than anything else. And \n\nOf course I did:\n\n$ git log --parents --name-only --full-history lib/vsprintf.c | grep -e ^commit | wc -l\n5929\n\nThis is same amount of commits as for gitk.\n\n$ /usr/bin/time git log --parents --name-only --full-history lib/vsprintf.c | grep -e ^commit -e ^lib | /usr/bin/time ruby ../filter.rb\n3.08user 0.14system 0:03.54elapsed 91%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+48230minor)pagefaults 0swaps\n20\n[\"72fd4a35a824331d7a0f4168d7576502d95d34b3\", [\"0a6047eef1c465c38aacfbdab193161b3f0cd144\"]]\n[\"06b2a76d25d3cfbd14680021c1d356c91be6904e\", [\"96e3e18eed3b48f6d4377dee0326a106e8a04569\"]]\n[\"1da177e4c3f41524e886b7f1b8a0c1fc7321cac2\", []]\n[\"e905914f96e11862b130dd229f73045dad9a34e8\", [\"f796937a062c7aeb44cd0e75e1586c8543634a7d\"]]\n[\"4e57b6817880946a3a78d5d8cad1ace363f7e449\", [\"8032230694ec56c168a1404c67a54d281536cbed\"]]\n[\"4f9d5f4a353440f2265781bfa641587964901861\", [\"9b706aee7d92d6ac3002547aea12e3eaa0a750ae\"]]\n[\"0a6047eef1c465c38aacfbdab193161b3f0cd144\", [\"e905914f96e11862b130dd229f73045dad9a34e8\"]]\n[\"c6b40d16d1cfa1a01158049bb887a9bbe48ef7ba\", [\"11443ec7d9286dd25663516436a14edfb5f43857\"]]\n[\"ea6f3281a145d16ed53e88b0627f78d5cde6068f\", [\"72fd4a35a824331d7a0f4168d7576502d95d34b3\"]]\n[\"11443ec7d9286dd25663516436a14edfb5f43857\", [\"ea6f3281a145d16ed53e88b0627f78d5cde6068f\"]]\n[\"b39a734097d5095d63eb9c709a6aaf965633bb01\", [\"c6b40d16d1cfa1a01158049bb887a9bbe48ef7ba\"]]\n[\"78a8bf69b32980879975f7e31d30386c50bfe851\", [\"0f9bfa569d46f2346a53a940b2b9e49a38635732\"]]\n[\"4d8a743cdd2690c0bc8d1b8cbd02cffb1ead849f\", [\"78a8bf69b32980879975f7e31d30386c50bfe851\"]]\n[\"0fe1ef24f7bd0020f29ffe287dfdb9ead33ca0b2\", [\"4d8a743cdd2690c0bc8d1b8cbd02cffb1ead849f\"]]\n[\"9b706aee7d92d6ac3002547aea12e3eaa0a750ae\", [\"06b2a76d25d3cfbd14680021c1d356c91be6904e\"]]\n[\"0f9bfa569d46f2346a53a940b2b9e49a38635732\", [\"4f9d5f4a353440f2265781bfa641587964901861\"]]\n[\"4277eedd7908a0ca8b66fad46ee76b0ad96e6ef2\", [\"b39a734097d5095d63eb9c709a6aaf965633bb01\"]]\n[\"8032230694ec56c168a1404c67a54d281536cbed\", [\"1da177e4c3f41524e886b7f1b8a0c1fc7321cac2\"]]\n[\"f796937a062c7aeb44cd0e75e1586c8543634a7d\", [\"4e57b6817880946a3a78d5d8cad1ace363f7e449\"]]\n[\"96e3e18eed3b48f6d4377dee0326a106e8a04569\", [\"4277eedd7908a0ca8b66fad46ee76b0ad96e6ef2\"]]\n0.12user 0.02system 0:03.64elapsed 3%CPU (0avgtext+0avgdata 0maxresident)k\n0inputs+0outputs (0major+7252minor)pagefaults 0swaps\n\nThese are the same 20 commits (with parents) from a simple git-log.\n\n> I dismissed what you wrote because the example you _did_ state was about \n> something else entirely (ie apparently some giggle bug that simplifies \n> things incorrectly).\n\nI'm trying to get back things to the topic and it's not just giggle, every \ntool presents a different version of the history.\n\n> > What did I do wrong that you rebuff me based on this secondary problem \n> > (which I'm quite aware of, because it was me who mentioned in first place) \n> > and giving the primary problem (which is the missing history) no \n> > attention?\n> \n> It's not missing history. It's all there in --full-history. The default is \n> to give a reasonable simplification, and I told you what the \n> simplification was, and it's perfectly conceptually fine - AND IT IS MUCH \n> MORE EFFICIENT than the alternatives.\n> \n> So I'm not seeing your point what-so-ever. \n\nThat's why I gave you an alternative example, where history is missing.\n\n> - with full-history, you have it all, but it's useless in practice\n\nCould you please specify which full-history you mean, gitk --full-history \nor git-log --full-history?\n\n> - without full-history, it's useful in practice\n\n>From a VCS I would still expect nevertheless to present a correct \nhistory not some approximation.\n\nbye, Roman\n"},{"id":"85227","messageId":"Pine.LNX.4.64.0807280308120.6791@localhost.localdomain","threadId":"14578","inReplyTo":"46a038f90807271625x35c561fdv6dc6b2c312f45fa1@mail.gmail.com","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Roman Zippel","fromEmail":"zippel@linux-m68k.org","sentAt":"2008-07-28T01:29:39Z","receivedAt":"2008-07-28T01:29:39Z","isPatch":false,"sender":{"key":"zippel@linux-m68k.org","avatar":null},"body":"Hi,\n\nOn Mon, 28 Jul 2008, Martin Langhoff wrote:\n\n> On Mon, Jul 28, 2008 at 11:14 AM, Roman Zippel wrote:\n> > Why are you dismissing what I wrote without even giving it a second\n> > thought? I didn't bother with the initial example, because it's so\n> > simple, that it's no real challenge.\n> \n> I can't speak for anyone else, but you do have to keep in mind that a\n> solution to this has to be rather fast - and I mean fast in git terms,\n> not in scripting-language-fast terms.\n\nYou also have to keep in mind, that I haven't really hacked git before, so \nI'm just trying to do something with the data I can somehow extract from \nit. I seriously didn't thought that anyone wouldn't understand that the \ncode example was just a proof of concept.\n\n> That you can do it Ruby - and I may be able to do it Perl - has little\n> bearing on what can be done inside the git log machinery with a small\n> performance penalty.\n\nIt also has to do with correctness, is performance more important than \ncorrectness? \nPart of the problem is, what is the correct history, as which it should be \ndisplayed via the various interfaces by default.\n\nbye, Roman\n"},{"id":"85236","messageId":"alpine.LFD.1.10.0807272148030.3486@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807280141140.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-28T05:00:58Z","receivedAt":"2008-07-28T05:00:58Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 28 Jul 2008, Roman Zippel wrote:\n> \n> Of course I did:\n> \n> $ git log --parents --name-only --full-history lib/vsprintf.c | grep -e ^commit | wc -l\n> 5929\n> \n> This is same amount of commits as for gitk.\n\nOF COURSE it's the same numbr of commits. That's what gitk uses. That's \nwhat you *have* to use.\n\nYou don't actually understand how git works, do you?\n\n> These are the same 20 commits (with parents) from a simple git-log.\n\nSo what? The point I tried to make is that _any_ algorithm that gets the \nabove case right by actually simplifying the commits \"post facto\" probably \ngets any case right. You tried to find some more interestign case, but you \nmissed the whole point - even the \"simple\" case is quite hard enough. \n\nIOW, don't look for anythign more difficult, because if you do, you don't \nunderstand the problem to begin with!\n\nDo you not understand that the problem is that \"post facto\" isn't actually \nacceptable? Have you looked at all at the revision reading code? Hmm?\n\nThe regular merge simplification does the simplification _before_ it has \ngathered the whole history of commits. And that is really really \nimportant.\n\nAnd I realize that you don't even seem to understand the difference. But \nto simplify it for you, let me give you a challenge. Try this:\n\n\ttime sh -c \"git log --parents --full-history lib/vsprintf.c | head\"\n\nand if it takes noticeably more than a tenth of a second on my machine, \nyou lose.\n\nBecause that's roughly what it takes right now, and it's what means that \neffectively the normal log is instantaneous. It's why you can start \nlooking at the log without waiting for three seconds, even though the \n_full_ log may take three seconds to compute (ok, on my machine it takes \n2.3s, but whatever).\n\nAnd it's why gitk can start printing out the history _before_ three \nseconds has passed. And that's really really important.\n\nTry it. Really. Just do \"gitk lib/vsprintf.c\" and look at how it does \nthings incrementally. It doesn't wait for a couple of seconds and then \nshow things.\n\nAbsolutely EVERYTHING in git would be totally trivial if you did it all \nbased on generating first the whole history, and then simplifying it from \nthere. But git would be unusably slow in real life, and it would scale \n_horribly_ badly with history size.\n\nSo _all_ the normal code actually generates the history INCREMENTALLY, and \nit absolutely _has_ to work that way.\n\n\t\t\tLinus\n"},{"id":"85237","messageId":"alpine.LFD.1.10.0807272206480.3486@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"alpine.LFD.1.10.0807272148030.3486@nehalem.linux-foundation.org","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-28T05:30:59Z","receivedAt":"2008-07-28T05:30:59Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 27 Jul 2008, Linus Torvalds wrote:\n> \n> And it's why gitk can start printing out the history _before_ three \n> seconds has passed. And that's really really important.\n\nBtw, the reason it's really really important is that \"three seconds\" can \nactually easily be \"three minutes\" - if the project is big, or if you \nsimply don't have everything in the cache, so you actually need to do tons \nof IO to generate the whole history.\n\nSo every normal operation absolutely _must_ be incremental and not rely on \nany calculation of the whole history in order to then simplify it.\n\nOf course, post-processing is fine for some things. For example, in the \nthread I pointed you to originally (see filter-branch + full-history in \ngoogle, or look in some git archive) I suggested a post-processing of the \nmerge history for filter-branch. I suspect it's very acceptable for _that_ \nkind of use to \"batch\" things up and not do them with partial knowledge.\n\nBut this incremental thing is why I for example suggest people should use \n\"git gui blame\" instead of \"git blame\" when looking for problems - because \nthe latter cannot be done incrementally, and as a result can cause really \nirritating delays (exactly because it basically needs to synchronously \nwalk back to the beginning of history).\n\nThe kernel repo, btw, is pretty small in this regard. The cases that \ncaused much more pain were the insane KDE ones that were something like \nten times the size. We've optimized things pretty aggressively, but...\n\nBtw, if I sound irritated, it's because we had all these discussions about \nthree _years_ ago when git got started. This is not a new issue. It's \nhard.\n\nI've been pushing on people to do things incrementally very hard over the \nlast few years because it's such a _huge_ usability issue.\n\nFor example, I've pointed you to the incremental nature of \"gitk\" as an \nexample of how things should work, but that's actually fairly recent: it \nwasn't that long ago that \"gitk\" used to pass in \"--topo-order\" or \n\"--date-order\" to the core git revision machinery, and that actually is \nanother of those \"global\" operations that you need the whole history for.\n\nSo gitk actually used to pause for three seconds (or ten. or thirty) \nbefore it would show the results. I'm really happy to report that Paul \nfinally did the (trivial) topo-sort in gitk, meaning that he could re-sort \nit as necessary and keep things incremental. It was one of my biggest UI \ngripes for the longest time (and I wasted time adding a special \"partial \noutput mode\" that gitk didn't even then end up using because Paul did \nthings the right way).\n\nBtw, from a git log viewer standpoint, the \"merge history simplification\" \nis all the exact same problem as the \"--topo-order\" flag is: you could \nuse the (incremental and very verbose)\n\n\tgit log --full-history --parents\n\noutput as the base-line, and then you could do the commit simplification \nof things interactively.\n\nBut \"git log\" itself cannot do it by default, since that would mean that \ngit log itself would have to wait for the whole history to be generated. \n\nThat's because output to a pipe is fundamentally linear (ie it cannot \n\"re-write\" the things it has already shown as it finds a simplification: \nthere is no incremental way to rewrite things \"after the fact\").\n\n\t\t\tLinus\n"},{"id":"85389","messageId":"Pine.LNX.4.64.0807281241180.6791@localhost.localdomain","threadId":"14578","inReplyTo":"alpine.LFD.1.10.0807272148030.3486@nehalem.linux-foundation.org","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Roman Zippel","fromEmail":"zippel@linux-m68k.org","sentAt":"2008-07-29T02:59:01Z","receivedAt":"2008-07-29T02:59:01Z","isPatch":false,"sender":{"key":"zippel@linux-m68k.org","avatar":null},"body":"Hi,\n\nOn Sun, 27 Jul 2008, Linus Torvalds wrote:\n\n> You don't actually understand how git works, do you?\n\nProbably not and to be honest I don't care, all I want is my history - the \ncorrect one. All I know it's in there somehow and all I care is how to get \nit out of there.\nRight now you're giving me the choice between a crappy incomplete history \nor a crappy history full of useless information. That's it? As long as \nyour challenge involves being compared to crappy history, I'm not \ninterested. If the solution should involve a switch \"--correct-history\" \nor I have to wait for the result, I don't care, because it's the correct \nhistory I want. As long as you're trying to sell me crappy history I'm not \nbuying it.\n\nCan we please get past this and look at what is required to produce the \ncorrect history?\n\nFact is based on the current git-log output it's simply impossible to \nproduce the correct history without reading the whole history first, since \nthe very last commit can still be relevant for an earlier merge to connect \nit properly into the graph. This means we need some extra information \nbefore even starting to scan through the commits. Luckily this information \ncan be cached once it has been generated and it also can be updated \nincrementally. E.g. this information could be generated while generating \nthe pack, so you only had to scan the commits which haven't been packed \nyet, but it's also possible to update it when merging/pulling new data. \nIt's also not much information that is needed, all that is needed is list \nof commits per file (which are are usually only a few, mostly even none), \nwhich git-log can use, so it knows that these are important while scanning \nthe tree.\n\nTechnically I don't see a really hard problem to implement this, the \nproblem for me is only that I have no idea where to start this within git \nand how to integrate it. The other problem (over which I have absolutely \nno control) is whether anyone actually wants to produce a correct history.\nI hope there is someone, otherwise there would be no need for \"git-log \n--full-history\" (which is also used by git-web), this e.g. produces a nice \nexample in kernel/printk.c, where git-web produces two commits (search for \ntty_write_message), for which none of the front ends can tell me usefully \nhow it fits into the history (they either don't show it at all or it's \nlost in \"gitk --full-history\").\n\nbye, Roman\n"},{"id":"85390","messageId":"46a038f90807282015m7ce3da10h71dfee221c960332@mail.gmail.com","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807281241180.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2008-07-29T03:15:28Z","receivedAt":"2008-07-29T03:15:28Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On Tue, Jul 29, 2008 at 2:59 PM, Roman Zippel wrote:\n> Can we please get past this and look at what is required to produce the\n> correct history?\n\nRoman - correct is --full-history -- any simplification that makes it\neasy on your eyes *is* a simplification. And consumers that want to do\nnice user-friendly simplification like gitk does can hang off the data\nstream.\n\n> it's also possible to update it when merging/pulling new data.\n\nIf that's what you want to do, you can prototype it with a hook on\nfetch and commit. That is definitely an area that hasn't been explored\n- what nicer (but expensive) views on the history we have can be\nafforded by pre-computing things on fetch and commit hooks.\n\ncheers,\n\n\n\nm\n-- \n martin.langhoff@gmail.com\n martin@laptop.org -- School Server Architect\n - ask interesting questions\n - don't get distracted with shiny stuff - working code first\n - http://wiki.laptop.org/go/User:Martinlanghoff\n"},{"id":"85391","messageId":"alpine.LFD.1.10.0807282023290.3334@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807281241180.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-29T03:29:59Z","receivedAt":"2008-07-29T03:29:59Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 29 Jul 2008, Roman Zippel wrote:\n> \n> Right now you're giving me the choice between a crappy incomplete history \n> or a crappy history full of useless information. That's it? As long as \n> your challenge involves being compared to crappy history, I'm not \n> interested.\n\nNo, my challenges have not been about \"crappy history\" but about \nperformance and about getting it right. The reason I pointed you to \nlib/vsprintf.c had nothing to do with crappiness, and had everythign to do \nwith just picking a random example of something where you absolutely \n*HAVE* to simplify history.\n\nThe fact that it simplifies to a linear one is totally immaterial. You \ncontinue to miss the point. Over and over AND OVER again!\n\n> Can we please get past this and look at what is required to produce the \n> correct history?\n\nI'm not even going to bother with this argument.\n\nYou dismiss all my issues, and then you continue to talk about \"correct\", \neven though it isn't a correctness thing - it's a difference of opinion. \nMe, I *much* prefer the simplified history. That _is_ the correct one for \nme.\n\nAnd the sad part is, what you want is there. It's a command line switch \naway. You were told in the very first message what the switch was. If you \ndon't want to use \"--full-history\", you can actually use \"git whatchanged\" \ninstead of \"git log\", and it implies the switch without you even having to \ntype it.\n\nSo it's all there. Use it. Just don't bother adding me to the cc to your \ninane flames, because I'm fed up with the fact that you can't actually be \nbothered to read my emails, and just want to flame.\n\nAnd quite frankly, I've seen that behaviour from you before, when it comes \nto other things. So go away. Write the code. Come back with patches. In \nthe meantime, we've told you what to do: use --full-history if you really \nwant it.\n\n\t\t\tLinus\n"},{"id":"85392","messageId":"alpine.LFD.1.10.0807282031240.3334@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"alpine.LFD.1.10.0807282023290.3334@nehalem.linux-foundation.org","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-29T03:33:51Z","receivedAt":"2008-07-29T03:33:51Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 28 Jul 2008, Linus Torvalds wrote:\n> \n> And quite frankly, I've seen that behaviour from you before, when it comes \n> to other things. So go away. Write the code. Come back with patches. In \n> the meantime, we've told you what to do: use --full-history if you really \n> want it.\n\nBtw, if you really do end up wanting to actually do something about it, I \ncan already tell you that trying to do so in \"git log\" isn't going to be \nuseful. Do it in \"gitk\" instead, and make gitk simplify the --full-history \noutput.\n\nI tried to explain to you the why part earlier (go back and look for \n\"incremental\" and \"topo-sort\"), but it all seemed to fly right by you, and \nyou started repeating your ranting instead.\n\nIOW, put up or shut up.\n\n\t\t\tLinus\n"},{"id":"85410","messageId":"20080729053108.GH26997@sigill.intra.peff.net","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807281241180.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-07-29T05:31:08Z","receivedAt":"2008-07-29T05:31:08Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 29, 2008 at 04:59:01AM +0200, Roman Zippel wrote:\n\n> Right now you're giving me the choice between a crappy incomplete history \n> or a crappy history full of useless information. That's it? As long as \n> your challenge involves being compared to crappy history, I'm not \n> interested. If the solution should involve a switch \"--correct-history\" \n> or I have to wait for the result, I don't care, because it's the correct \n> history I want. As long as you're trying to sell me crappy history I'm not \n> buying it.\n> \n> Can we please get past this and look at what is required to produce the \n> correct history?\n\nYou seem to be indicating here (and elsewhere in the thread) that there\nexists some history graph for which neither \"git log\" nor \"git log\n--full-history\" produces the output you want, but that there is some\nbetter output (even if it might take more time to compute).\n\nPerhaps I am just slow, but I haven't been able to figure out what that\nhistory is, or what the \"correct\" output should be. Can you try to state\nmore clearly what it is you are looking for?\n\n-Peff\n"},{"id":"85450","messageId":"Pine.LNX.4.64.0807291235350.6791@localhost.localdomain","threadId":"14578","inReplyTo":"alpine.LFD.1.10.0807282023290.3334@nehalem.linux-foundation.org","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Roman Zippel","fromEmail":"zippel@linux-m68k.org","sentAt":"2008-07-29T11:39:34Z","receivedAt":"2008-07-29T11:39:34Z","isPatch":false,"sender":{"key":"zippel@linux-m68k.org","avatar":null},"body":"Hi,\n\nOn Mon, 28 Jul 2008, Linus Torvalds wrote:\n\n> You dismiss all my issues, and then you continue to talk about \"correct\", \n> even though it isn't a correctness thing - it's a difference of opinion. \n> Me, I *much* prefer the simplified history. That _is_ the correct one for \n> me.\n\nI'm not dismissing it, but your focus is on how to get this result. If the \nresults were always the same, I wouldn't have a problem at all.\nThat's why I'm trying to give you an example where the end result differs, \nhow are we supposed to get to an agreement on _how_ to get the result, if \nwe don't even agree on _what_ the result should be?\n\n> And quite frankly, I've seen that behaviour from you before, when it comes \n> to other things.\n\nWhat exact behaviour is that? That I dare to disagree with you?\n\n> So go away. Write the code. Come back with patches.\n\nIf you knew me that well, you also knew that such threats don't work with \nme.\nIn this case you know perfectly well, that I don't know the code as well \nas you, so without any help it would require a huge waste of time with the \nrisk of rejection.\n\nbye, Roman\n"},{"id":"85454","messageId":"86fxps7vd1.fsf@lola.quinscape.zz","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807291235350.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2008-07-29T12:00:58Z","receivedAt":"2008-07-29T12:00:58Z","isPatch":false,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Roman Zippel writes:\n\n> On Mon, 28 Jul 2008, Linus Torvalds wrote:\n>\n>> So go away. Write the code. Come back with patches.\n>\n> If you knew me that well, you also knew that such threats don't work\n> with me.\n\nI'd like to add to Linus' suggested course of action the task \"look up\nthreat in a dictionary\".\n\n> In this case you know perfectly well, that I don't know the code as\n> well as you, so without any help it would require a huge waste of time\n> with the risk of rejection.\n\nIf _you_ need the functionality, you can easily keep it around in _your_\ncopy. That's what I do with a few patches that were not accepted here.\nSo the \"risk of rejection\" has no real cost for you (apart from an\noccasional rebase on origin, which is cheap). Just for others. And of\nno-one else argues your case, then they probably don't mind.\n\n-- \nDavid Kastrup\n"},{"id":"85458","messageId":"Pine.LNX.4.64.0807291339580.6791@localhost.localdomain","threadId":"14578","inReplyTo":"20080729053108.GH26997@sigill.intra.peff.net","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Roman Zippel","fromEmail":"zippel@linux-m68k.org","sentAt":"2008-07-29T12:32:14Z","receivedAt":"2008-07-29T12:32:14Z","isPatch":false,"sender":{"key":"zippel@linux-m68k.org","avatar":null},"body":"Hi,\n\nOn Tue, 29 Jul 2008, Jeff King wrote:\n\n> > Can we please get past this and look at what is required to produce the \n> > correct history?\n> \n> You seem to be indicating here (and elsewhere in the thread) that there\n> exists some history graph for which neither \"git log\" nor \"git log\n> --full-history\" produces the output you want, but that there is some\n> better output (even if it might take more time to compute).\n> \n> Perhaps I am just slow, but I haven't been able to figure out what that\n> history is, or what the \"correct\" output should be. Can you try to state\n> more clearly what it is you are looking for?\n\nMost frequently this involves changes where the same change is merged \ntwice. Another interesting example is kernel/printk.c where a change is \nadded and later removed again before it's merged.\nWith \"git-log --full-history\" you see these changes, but it lacks the \nnecessary merges to produce a full graph. As consequence none of the \ngraphical front ends produce a useful history graph.\n\nThis problem now hits me now more seriously in a repository conversion, \nwhere it frequently happened, that changes were applied both locally and \nupstream, so that I have relatively many of these empty merges and the \ndefault git-log output is useless. --full-history is more of a workaround \nthan a real solution and again the history graph in _all_ graphical front \nends is useless.\n\nMore generally this means in any kind of situation where you maintain your \nown repository and it takes a while until upstream accepts your changes, \nso that you frequently have duplicated changes (because upstream doesn't \nuse git or doesn't pull directly), you have to be careful to get the right \nhistory out of git.\n\nThe point is now that I think the problem is solvable even within Linus' \nconstraints, so that git-log produces the right output by default and a \nworkaround like --full-history isn't needed anymore.\n\nbye, Roman\n"},{"id":"85463","messageId":"20080729124827.GB14052@dspnet.fr.eu.org","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807291339580.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Olivier Galibert","fromEmail":"galibert@pobox.com","sentAt":"2008-07-29T12:48:27Z","receivedAt":"2008-07-29T12:48:27Z","isPatch":false,"sender":{"key":"galibert@pobox.com","avatar":null},"body":"On Tue, Jul 29, 2008 at 02:32:14PM +0200, Roman Zippel wrote:\n> Most frequently this involves changes where the same change is merged \n> twice. [...]\n\nYou're not answering the question. You cite cases when you consider\nboth the default and the full-history output incorrect from a\nusefulness point of view. The question is, what would the correct\noutput be, from your point of view? What should be shown, and what\nshouldn't?\n\n OG.\n"},{"id":"85464","messageId":"20080729125247.GC12069@sigill.intra.peff.net","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807291339580.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-07-29T12:52:47Z","receivedAt":"2008-07-29T12:52:47Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 29, 2008 at 02:32:14PM +0200, Roman Zippel wrote:\n\n> > Perhaps I am just slow, but I haven't been able to figure out what that\n> > history is, or what the \"correct\" output should be. Can you try to state\n> > more clearly what it is you are looking for?\n> \n> Most frequently this involves changes where the same change is merged \n> twice. Another interesting example is kernel/printk.c where a change is \n> added and later removed again before it's merged.\n\nI glanced briefly over \"gitk kernel/printk.c\" and it looks pretty sane.\nI was really hoping for you to make your case as something like:\n\n 1. here is an ascii diagram of an actual history graph (or a recipe of\n git commands for making one)\n 2. here is what git-log (or gitk) produces for this history by\n default; and here is why it is not optimal (presumably some\n information it fails to convey)\n 3. here is what git-log (or gitk) with --full-history produces; and\n here is why it is not optimal (presumably because it is too messy)\n 4. here is what output I would like to see. Bonus points for \"and here\n is an algorithm that accomplishes it.\"\n\n> The point is now that I think the problem is solvable even within Linus' \n> constraints, so that git-log produces the right output by default and a \n> workaround like --full-history isn't needed anymore.\n\nI think this is a separate issue. Even if you came up with some great\nnew history simplification, it likely wouldn't become the _default_\nright away anyway. So you need to:\n\n 1. produce a new simplification algorithm that is at least useful in\n _some_ contexts. Then this can be used when desired for those\n contexts. It almost doesn't matter how efficient it is, if it is\n providing results that are otherwise unavailable. A user can choose\n to take the performance hit to get those results.\n\n 2. If that algorithm doesn't provide worse output in any other\n contexts _and_ it has similar performance to the current default,\n then it can be considered for the default.\n\nBut I haven't seen convincing evidence leading to step '1', so arguing\nabout step '2' seems pointless.\n\n-Peff\n"},{"id":"85483","messageId":"alpine.LFD.1.10.0807290838360.3334@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807291235350.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-29T15:50:02Z","receivedAt":"2008-07-29T15:50:02Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 29 Jul 2008, Roman Zippel wrote:\n> \n> I'm not dismissing it, but your focus is on how to get this result.\n\nNo, you misunderstand.\n\nMy focus is really on one single thing:\n\n - performance\n\nwith a smaller focus on the fact that I simply don't see how it's \n_possible_ to do better than our current all-or-nothing approach of \nsimplification (eg either extreme simplification or none at all: nothing \nor --full-history).\n\nSo here's my challenge again, which you seem to have TOTALLY MISSED.\n\nMake this be fast:\n\n\ttime sh -c \"git log | head\"\n\nnothing else matters. If you can make that one be fast, I'm happy. \n\nAnd that \"| head\" is really very fundamentally important. The important \nthing from a performance standpoint is not how long the _whole_ \"log\" \ntakes. The important thing is how fast it _feels_, and that is directly \ntied to how fast it starts outputting the data.\n\nPut another way: I _know_ how to simplify things. Trust me, Roman. That's \nnot the problem. But doing it incrementally is really really hard, to the \npoint that I actually believe that it is impossible to do. \n\nAnd doing it after-the-fact is simply not interesting. We could trivially \n(well, _fairly_ trivially) do it when we do the topology sort. But I have \nlong long tried to teach people _not_ to do the topo sort inside the core \ngit machinery, exactly because it is a horrid thing from an interactivity \nstandpoint.\n\nIn fact, you can see what I'm talking about by trying --topo-order in the \nabove timing test.\n\nReally. Just _try_ it. And if you still don't understand what I'm talking \nabout, I don't know what to say.\n\n> > And quite frankly, I've seen that behaviour from you before, when it comes \n> > to other things.\n> \n> What exact behaviour is that? That I dare to disagree with you?\n\nNo. The fact that you like arguing _pointlessly_, and just being abrasive, \nwithout actually helping or understanding the big picture. I'm thinking \nback on the whole scheduler thing. You weren't arguing with _me_, but you \nhad the same modus operandi.\n\n\t\t\tLinus\n"},{"id":"85492","messageId":"alpine.LFD.1.10.0807291006070.3334@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"20080729125247.GC12069@sigill.intra.peff.net","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-29T17:25:35Z","receivedAt":"2008-07-29T17:25:35Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 29 Jul 2008, Jeff King wrote:\n> \n> I glanced briefly over \"gitk kernel/printk.c\" and it looks pretty sane.\n\nJeff, it _is_ sane. When Roman says it's \"incorrect\", he is just wrong.\n\nBut it's true that \"gitk kernel/printk.c\" does simplify the history, and \ndoes so very aggressively. It does so very much by design, and has done it \nsince pretty much day one. And it's a good thing - and it is \"correct\" - \nbut it does mean that you may literally be missing things that are part of \n\"history\" but that didn't matter much.\n\nThe most trivial way to show this is actually by making such a simple case \nthat it's obvious what is going on. Do this:\n\n\tmkdir test-simplification\n\tcd test-simplification\n\tgit init\n\techo \"Hi there\" > file\n\tgit add file\n\tgit commit -m\"Initial file\"\n\n\tgit branch other-branch\n\n\techo \"Hello\" > file\n\tgit add file\n\tgit commit -m\"Modified file\"\n\n\tgit checkout other-branch\n\n\techo \"Hello\" > file\n\tgit add file\n\tgit commit -m\"Another person modified the file identically\"\n\n\techo \"This is a stupid example\" > another-file\n\tgit add another-file\n\tgit commit -m\"Add another file\"\n\n\tgit merge master\n\nNow, do these three things\n\n\tgitk\n\tgitk file\n\tgitk --full-history file\n\nand compare them. They all show _different_ histories.\n\nWhich one is \"correct\"? They all are. It just depends on what you want to \nsee.\n\nThe \"gitk file\" history is the simplest one BY FAR, because it has very \naggressively simplified history to the point where it tried to find the \n_simplest_ history that explains the current contents of 'file'[*]\n\n>From a practical standpoint, and from having used this a long time, I'd \nargue that the simple history is the one that you want 99.9% of all time. \nBut not _always_. Sometimes, the things that got simplified away actually \nmatter. It's rare, but it happens.\n\nFor example, maybe you had a bug-fix that you _know_ you did, and it it \ndoesn't show up in the simplified history. That really pisses you off, and \nit apparently really pisses Roman off that it can happen. But the fact is, \nthat still doesn't mean that the simple history is \"wrong\" or even \n\"incomplete\".\n\nNo, it's actually meaningful data in itself. If the bug-fix doesn't show \nin the simplified history, then that simply means that the bug-fix was not \non a branch that could _possibly_ have mattered for the current contents. \n\nSo once you are _aware_ of history simplification and are mentally able to \naccept it, the fact that history got simplified is actually just another \ntool.\n\nAnd that's why \"-full-history\" and \"git whatchanged\" exist. They are ways \nto start delving deeper - they shouldn't be the _default_ mode, but they \nare ways to show more information when the initial default simple mode \nturns out to show that something didn't even matter for the end result.\n\nAnd yes, there is a mid-way point between \"aggressive simplification\" \n(default) and \"no simplification at all\" (--full-history). It's more \ncomplex than either, and I do think it would be useful to have. It's what \nRoman wants, but as long as he thinks it's the _only_ correct answer, and \nrefuses to face the performance issues, the discussion with Roman is kind \nof pointless.\n\n\t\t\tLinus\n\n[*] when I say \"_simplest_ history\", I do want to point out that the \nhistory simplification is always a \"local optimization\", and it doesn't \ntry to check all possible paths: there can be other histories that are \neven simpler on a global scale.\n\nBut in practice it is _one_ history of the file, and it's a history that \nis not \"unnecessarily complicated\" considering the simple heurstics for \nfinding it.\n\nSo think \"local minima\" instead of \"global minima\", and in practice the \nlocal one is pretty close to the global one, although there are obviously \nalways extreme cases where the two can differ by a whole lot.\n"},{"id":"85546","messageId":"Pine.LNX.4.64.0807291433430.6791@localhost.localdomain","threadId":"14578","inReplyTo":"46a038f90807282015m7ce3da10h71dfee221c960332@mail.gmail.com","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Roman Zippel","fromEmail":"zippel@linux-m68k.org","sentAt":"2008-07-30T00:16:41Z","receivedAt":"2008-07-30T00:16:41Z","isPatch":false,"sender":{"key":"zippel@linux-m68k.org","avatar":null},"body":"Hi,\n\nOn Tue, 29 Jul 2008, Martin Langhoff wrote:\n\n> On Tue, Jul 29, 2008 at 2:59 PM, Roman Zippel wrote:\n> > Can we please get past this and look at what is required to produce the\n> > correct history?\n> \n> Roman - correct is --full-history -- any simplification that makes it\n> easy on your eyes *is* a simplification. And consumers that want to do\n> nice user-friendly simplification like gitk does can hang off the data\n> stream.\n\nI don't quite understand what you're trying to say.\nTo avoid further confusion it maybe helps to specify a few of the terms:\n\n- full history graph: produced by \"git-log --full-history --parents\"\n- compact history graph: the full history graph without without any \n repeated merges, this is what my example script produces.\n- full simplified history: output of \"git-log --full-history\"\n- short simplified history: standard output of \"git-log\"\n\nThe important part about the history graphs is that all commits are \nproperly connected in it (i.e. all except the head commit have a child), \nThis is needed to know if you don't just what want to know what happened, \nbut also how it got merged, also any graphical interface needs it to \nproduce a useful history graph.\n\nWhat the short simplified history is more pure laziness, it's fast and \ngets the most common cases right, but in order to do this it has to ignore \npart of the history. The full simplified history at least produces \nproduces the full change history, but it lacks part of the merge history \nand it stills takes longer to generate.\n\nThe point I'm trying to make is that the compact history graph has the \npotential to completely replace the simplified history. The only problem \nis that it needs a bit of cached extra information, then it can be as fast \nthe short simplified history for the common case and it still can produce \nas much information as the full simplified history, thus you can still \napply as much simplification as you want on top of it.\n\nKeep in mind that e.g. git-web is using the full simplified history, so \nwhat I'm offering also has the potential to improve git-web performance...\n\n> > it's also possible to update it when merging/pulling new data.\n> \n> If that's what you want to do, you can prototype it with a hook on\n> fetch and commit. That is definitely an area that hasn't been explored\n> - what nicer (but expensive) views on the history we have can be\n> afforded by pre-computing things on fetch and commit hooks.\n\nI already did the prototype, I know how to generate that information, the \nproblem is to get that information to the various graphical interfaces.\n\nbye, Roman\n"},{"id":"85547","messageId":"46a038f90807291725r134b2a43gb3da00151e22d443@mail.gmail.com","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807291433430.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2008-07-30T00:25:39Z","receivedAt":"2008-07-30T00:25:39Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On Wed, Jul 30, 2008 at 12:16 PM, Roman Zippel wrote:\n> I already did the prototype\n\nafaict people around here are only interested if it can be done\nwithout losing the early-output niceness of current git-log. That it\ncan be worked out in a \"put it all in memory and work it in there\"\nmodel is _not_ interesting for git.\n\ncheers,\n\n\n\nm\n-- \n martin.langhoff@gmail.com\n martin@laptop.org -- School Server Architect\n - ask interesting questions\n - don't get distracted with shiny stuff - working code first\n - http://wiki.laptop.org/go/User:Martinlanghoff\n"},{"id":"85548","messageId":"alpine.LFD.1.10.0807291716060.3334@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807291433430.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-30T00:32:33Z","receivedAt":"2008-07-30T00:32:33Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 30 Jul 2008, Roman Zippel wrote:\n> \n> What the short simplified history is more pure laziness\n\nNo.\n\nRoman, you're an idiot who doesn't even _understand_ what you are talking \nabout. Sadly, you then _think_ you are so smart that you then refuse to \neven consider the fact that others disagree, so you don't even read what \nthey write.\n\nGo to my previous email in this thread. Do the example. Look at the \nsimplified version. Ponder.\n\nIt's not \"pure lazyness\" when you get the simplified version. It's \nactually a MORE USEFUL RESULT! The simplified version shows the minimal \nexplanation of how things ended up the way they are, and that is damn \nuseful. What you want is extra _clutter_ most of the time.\n\nIt's really sad how you cannot get over your own prejudices here. \n\nSo Roman. Go back, read my previous email in this thread. It's message ID \nis\n\n\t\n\nin case it helps you find it.\n\nRead it twice, or three times. Read it with the notion that maybe you \ndidn't know best after all. Read it with the possibility that maybe there \nare smarter people than you, and people who have actually worked with git \nfor several years.\n\nAnd if you can't do that, at least stop cc'ing me with your idiocy.\n\nTo get to the meat of your email:\n\n> The point I'm trying to make is that the compact history graph has the \n> potential to completely replace the simplified history. The only problem \n> is that it needs a bit of cached extra information, then it can be as fast \n> the short simplified history for the common case and it still can produce \n> as much information as the full simplified history, thus you can still \n> apply as much simplification as you want on top of it.\n\nYou're simply full of sh*t. You make two huge mistakes, and I'll spend \nanother few minutes of my life trying to educate you one final more time, \neven though from every single indication I have so far, you are unable to \nlearn simply because you think you already know the answer.\n\nYour two mistakes are:\n\n - your \"only\" problem is fundamental. It's unsolvable. Git history \n simplification isn't per-file or even per-directory. It's \n per-any-random-set-of-pathnames. You can't \"cache\" the simplified \n information, and it's not \"a bit\" of cached extra info. It's \n fundamentally a metric truckload of info.\n\n With a cache, you can make the performance of a repeated query go fast, \n but that's totally uninteresting.\n\n - But the other huge mistake you make is EVEN MORE STUPID, because it's \n so ironic. That magical output you want, and claim is so perfect, and \n point out \"thus you can still apply as much simplification as you want \n on top of it\"? You know what? It already _exists_! It's exactly that \n --full-history case.\n\n Can you not see that? That's exactly that --full-history --parents \n cases. It gives you the full information. You can simplify it to what \n you want, exactly because it did _not_ simplify things for you. I've \n even told you so, multiple times, when I suggested you try to do that \n simplification in \"gitk\".\n\nIn other words, git has the two cases you want: the \"extreme simplified \nhistory\" (that is nice to see what really _mattered_, with no extra \nunnecessary duplicate history that didn't actually affect the end result), \nand the \"full\" history (ooh, I know, we could make a command line called \n\"--full-history\" to get the latter, so that people who wanted to see it \nall and perhaps distill it to something else could do so).\n\nAnd I've told you over and over what you should look at, and I've told you \nover and over that the default is actually the _useful_ case, and why. But \nyou seem to refuse to listen. You just close your ears and repeat your \nmantra, even though people smarter than you have told you why it's done \nthe way it's done. \n\nStop stuffing your ears. Listen to what people tell you.\n\n\t\tLinus\n"},{"id":"85552","messageId":"alpine.LFD.1.10.0807291738280.3334@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"alpine.LFD.1.10.0807291716060.3334@nehalem.linux-foundation.org","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-30T00:48:11Z","receivedAt":"2008-07-30T00:48:11Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 29 Jul 2008, Linus Torvalds wrote:\n> \n> - But the other huge mistake you make is EVEN MORE STUPID, because it's \n> so ironic. That magical output you want, and claim is so perfect, and \n> point out \"thus you can still apply as much simplification as you want \n> on top of it\"? You know what? It already _exists_! It's exactly that \n> --full-history case.\n\nPut in other terms: what you ask for can be fairly trivially done as a \nfilter on the _current_ git output (preferably merged into the tool that \nshows it graphically in the first place), with absolutely no downside.\n\nIn contrast, if somebody was really so _stupid_ as to go with your output \nformat, then yes, he could further simplify it down to the current default \nformat, but with a huge performance/interactivity downside.\n\nSee? Your preferred format is not actually the \"best\" format. Not at all. \nQuite the reverse. Your preferred format is much better off being a \nsecondary post-processing format exactly because it can be generated from \none of the primary formats easily enough.\n\nBut the reverse isn't true: the current primary formats cannot be \ngenerated from your preferred format without losing something important \n(performance).\n\nBut I'll make you a deal: if you actually write the filter in C form, I \ncan pretty much guarantee that we can easily add it as a new flag. It \nreally should be pretty easy to integrate it into the revision parsing \nmachinery alongside --topo-order, since it's really the same kind of \noperation.\n\nIn fact, it's possible that the current --topo-order sorting could \npossibly be made to just do the simplification (conditionally, of course, \nsince it has the latency problem). See the function\n\n\tvoid sort_in_topological_order(struct commit_list ** list, int lifo)\n\nin commit.c - that's where it would hook in.\n\n\t\tLinus\n"},{"id":"85555","messageId":"Pine.LNX.4.64.0807300223010.6791@localhost.localdomain","threadId":"14578","inReplyTo":"alpine.LFD.1.10.0807290838360.3334@nehalem.linux-foundation.org","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Roman Zippel","fromEmail":"zippel@linux-m68k.org","sentAt":"2008-07-30T01:14:12Z","receivedAt":"2008-07-30T01:14:12Z","isPatch":false,"sender":{"key":"zippel@linux-m68k.org","avatar":null},"body":"Hi,\n\nOn Tue, 29 Jul 2008, Linus Torvalds wrote:\n\n> On Tue, 29 Jul 2008, Roman Zippel wrote:\n> > \n> > I'm not dismissing it, but your focus is on how to get this result.\n> \n> No, you misunderstand.\n> \n> My focus is really on one single thing:\n> \n> - performance\n> \n> with a smaller focus on the fact that I simply don't see how it's \n> _possible_ to do better than our current all-or-nothing approach of \n> simplification (eg either extreme simplification or none at all: nothing \n> or --full-history).\n\nThat's exactly what I'm not dismissing as you claim, but I've hit the \nproblem where this approach simply produces crap, so I'm foremost \ninterested in getting a useful result, only after that I'm interested in \nthe performance (which I think is possible).\n\n> So here's my challenge again, which you seem to have TOTALLY MISSED.\n> \n> Make this be fast:\n> \n> \ttime sh -c \"git log | head\"\n> \n> nothing else matters. If you can make that one be fast, I'm happy. \n\nI already explained it, but you simply dismissed it. It's possible, but it \nrequires a bit of cached information (e.g. as part of the pack file, which \nis needed for decent performance anyway).\n\n> In fact, you can see what I'm talking about by trying --topo-order in the \n> above timing test.\n\nPlease give me full example.\ngitk --topo-order kernel/printk.c shows no difference (e.g. it doesn't \nshow 02630a12c7f72fa294981c8d86e38038781c25b7), several experiments with \ngit-rev-list show no improvement either.\n\n> > > And quite frankly, I've seen that behaviour from you before, when it comes \n> > > to other things.\n> > \n> > What exact behaviour is that? That I dare to disagree with you?\n> \n> No. The fact that you like arguing _pointlessly_, and just being abrasive, \n> without actually helping or understanding the big picture.\n\nThe problem is that your picture doesn't include my specific problem, I'm \nvery interested in the big picture, but I'd like to be in it.\n\n> I'm thinking \n> back on the whole scheduler thing. You weren't arguing with _me_, but you \n> had the same modus operandi.\n\nWell, it seems I have talent for finding the special cases, e.g. last time \nI tested the scheduler it was performing twice as bad as the old scheduler \non m68k. I've also seen cases where it sacrifices throughput for \ninteractivity.\nAnyway, this is the wrong place for it anyway, the problem I'm hitting is \nthese \"good enough\" solutions, which work in most situations, but fail in \na few special situations, but nobody is interested to get these right \nunless your name is Linus.\n\nbye, Roman\n"},{"id":"85559","messageId":"3B2566EF-807E-46E6-8447-D13A5904F00C@sb.org","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807300223010.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Kevin Ballard","fromEmail":"kevin@sb.org","sentAt":"2008-07-30T01:32:14Z","receivedAt":"2008-07-30T01:32:14Z","isPatch":false,"sender":{"key":"kevin@sb.org","avatar":"https://avatars.githubusercontent.com/u/714?v=4"},"body":"On Jul 29, 2008, at 6:14 PM, Roman Zippel wrote:\n\n>> So here's my challenge again, which you seem to have TOTALLY MISSED.\n>>\n>> Make this be fast:\n>>\n>> \ttime sh -c \"git log | head\"\n>>\n>> nothing else matters. If you can make that one be fast, I'm happy.\n>\n> I already explained it, but you simply dismissed it. It's possible, \n> but it\n> requires a bit of cached information (e.g. as part of the pack file, \n> which\n> is needed for decent performance anyway).\n\nAs an outside observer, this argument is basically akin to \"it's easy \nto fly, you just need some faerie dust\". Basically, you're dismissing \nthe entire complexity of the problem by saying \"oh, that's easy, just \nuse some cached data\" without any proof that this would work, or any \nsample code, or really any evidence at all. Given that the path \nsimplification can be arbitrarily complex (I can pass any set of paths \nI want), I don't believe that you can just use \"a bit of cached \ninformation\" for this. If you did rely on cached information, said \ninformation would probably be orders of magnitude larger than the \nobject graph itself (for repos with lots of files).\n\n>> In fact, you can see what I'm talking about by trying --topo-order \n>> in the\n>> above timing test.\n>\n> Please give me full example.\n> gitk --topo-order kernel/printk.c shows no difference (e.g. it doesn't\n> show 02630a12c7f72fa294981c8d86e38038781c25b7), several experiments \n> with\n> git-rev-list show no improvement either.\n\nHe's not saying it changes what commits are shown, he's saying it has \na performance impact - topo order has to post-process the graph. For a \nquick demonstration, run `time sh -c 'git log | head'` vs `time sh -c \n'git log --topo-order | head'`.\n\n-Kevin Ballard\n\n-- \nKevin Ballard\nhttp://kevin.sb.org\nkevin@sb.org\nhttp://www.tildesoft.com\n"},{"id":"85558","messageId":"alpine.LFD.1.10.0807291822590.3334@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807300223010.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-30T01:49:41Z","receivedAt":"2008-07-30T01:49:41Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 30 Jul 2008, Roman Zippel wrote:\n> > \n> > \ttime sh -c \"git log | head\"\n> > \n> > nothing else matters. If you can make that one be fast, I'm happy. \n> \n> I already explained it, but you simply dismissed it. It's possible, but it \n> requires a bit of cached information (e.g. as part of the pack file, which \n> is needed for decent performance anyway).\n\nBzzt. Wrong. Try again.\n\n> > In fact, you can see what I'm talking about by trying --topo-order in the \n> > above timing test.\n> \n> Please give me full example.\n> gitk --topo-order kernel/printk.c shows no difference (e.g. it doesn't \n> show 02630a12c7f72fa294981c8d86e38038781c25b7), several experiments with \n> git-rev-list show no improvement either.\n\nRoman, what the f*ck is wrong with you? Let me repeat that thing one more \ntime:\n\n\tyou can see what I'm talking about by trying --topo-order in the\n\tabove timing test.\n\t ^^^^^^^^^^^\n\nThe fact is, --topo-order is a post-processing thing, exactly the way your \nhalf-way simplification would be. It requires _all_ commits, and it \nrequires them because we cannot guarantee that we output all children \nbefore the parents when there are multiple threads without a central clock \n(ie any distributed environment).\n\nSo for --topo-order, we generate the whole history, and then we sort it. \n\nAs a result, it has horrible interactivity behavior. Try it. Here's some \nrandom command lines, and the times:\n\n\ttime git log --topo-order drivers/scsi/scsi_lib.c | head\n\n\treal 0m0.688s\n\tuser 0m0.652s\n\tsys 0m0.036s\n\nand without:\n\n\ttime git log drivers/scsi/scsi_lib.c | head\n\n\treal 0m0.033s\n\tuser 0m0.024s\n\tsys 0m0.008s\n\ndo you see the difference? They happen to output _exactly_ the same ten \nlines, but one of them takes the better part of a second (and that's on \npretty much the fastest machine you can find right now - on a laptop with \na slow disk and without things in cache, it would take many many seconds).\n\nThe other one is instantaneous.\n\nNow, I realize that 0.033s vs 0.688s doesn't sound like a big deal, even \nthough that's a 20x difference, but that 20x difference is a _really_ big \ndeal when the machine is slower, or when \"old history\" isn't in the disk \ncache any more.\n\nFor example, try doing the timings after flushing the disk caches to \nsimulate cold-cache behavior. Do it with a slow disk. Or do it over NFS. \nYes, even the \"fast\" case will actually be painfully slow (well, it is for \nme, people who are used to CVS probably think it's just \"normal\"). \n\nAnd yes, it will depend a lot on the file in question too. Obviously, if \nthe first change is far back in history, it will be slow _regardless_, but \nI've at least personally found that in practice, you tend to look at logs \nof _recent_ things much much much more than you look at things that \nhaven't changed lately.\t\n\nIt will also depend a lot on whether you are packed or not. For example, \nif you are well packed, the pack-file IO locality is really really good, \nand the 20x slowdown is much less. I just tested with a laptop with a slow \ndisk, and the --topo-order case was \"only\" 2.5x slower, almost certainly \nbecause the IO required to bring in the first part of the history ended up \nbeing a large portion of the total IO, and so the \"whole history\" case was \nnot 20x slower, because there was not 20x more IO due to the good locality \nand the kernel doing readahead etc.\n\nBut 2.5x slower is really bad, wouldn't you agree? We're not talking about \na few percent here, we're talking about more than twice as long. It's very \nnoticeable, especially when the end result was --topo-order: 29.8s, no \ntopo-order 12.1s\n\n(Yeah, that wasn't a very realistic example, but on that same machine, \nonce it's in the cache, it's 0.13s vs 1.6s: one is \"instant\", the other is \nvery much a \"wait for it\" kind of thing.)\n\nTHAT is the kind of performance difference you see.\n\nAnd trust me, it's a performance difference that you can really notice in \nreal life. I'm not kidding you. Just try it:\n\n\tgit log kernel/sched.c\nvs\n\tgit log --topo-order kernel/sched.c\n\nand one is instant, the other one pauses before it starts showing \nsomething. One feels fast, the other feels slow.\n\nAt the same time, if you actually time the _whole_ log, it's all exactly \nthe same speed:\n\n\t[torvalds@nehalem linux]$ time git log --topo-order kernel/sched.c > /dev/null \n\treal\t0m0.708s\n\tuser\t0m0.684s\n\tsys\t0m0.020s\n\n\t[torvalds@nehalem linux]$ time git log kernel/sched.c > /dev/null \n\treal\t0m0.703s\n\tuser\t0m0.672s\n\tsys\t0m0.032s\n\nNotice? The cost of the topological sort itself is basically zero. But \nfrom an interactivity standpoint, it's _deadly_.\n\nAnd please note that here \"--topo-sort\" is just an example of a random \n\"global history post-processing\" thing. It's not that I want you to use \nthe topological sort per se, it's just an example of the whole issue with \n_any_ post-factum operation. The topological sort is not expensive as a \nsort. What is expensive is that it needs to get the whole history to work.\n\nAnd also please notice that this is a huge scalability issue. \"git log\" \nshould not become slower as a project gets more history. Sure, the full \nlog will take longer to generate (because there's _more_ of it), but the \ntop commits should always show up immediately.\n\nAgain, if you have a filter (where \"topological sort\" is just an example \nof such a filter) that requires the full history to work, it simply \n_fundamentally_ cannot scale well. If very fundamentally will slow down \nwith bigger history.\n\n> The problem is that your picture doesn't include my specific problem, I'm \n> very interested in the big picture, but I'd like to be in it.\n\nRoman, I've been trying to explain this \"interactive\" thing for _days_ \nnow. That's the big picture. The whole \"you have to be able to generate \nhistory incrementally\" thing.\n\nFirst generating the whole global history, and then simplifying it, is \nsimply not acceptable. It's too slow, and it doesn't scale.\n\n\t\t\tLinus\n"},{"id":"85557","messageId":"Pine.LNX.4.64.0807300315280.6791@localhost.localdomain","threadId":"14578","inReplyTo":"alpine.LFD.1.10.0807291006070.3334@nehalem.linux-foundation.org","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Roman Zippel","fromEmail":"zippel@linux-m68k.org","sentAt":"2008-07-30T01:50:01Z","receivedAt":"2008-07-30T01:50:01Z","isPatch":false,"sender":{"key":"zippel@linux-m68k.org","avatar":null},"body":"Hi,\n\nOn Tue, 29 Jul 2008, Linus Torvalds wrote:\n\n> Now, do these three things\n> \n> \tgitk\n> \tgitk file\n> \tgitk --full-history file\n> \n> and compare them. They all show _different_ histories.\n> \n> Which one is \"correct\"? They all are. It just depends on what you want to \n> see.\n> \n> The \"gitk file\" history is the simplest one BY FAR, because it has very \n> aggressively simplified history to the point where it tried to find the \n> _simplest_ history that explains the current contents of 'file'[*]\n\nIt's \"aggressively simplified\" by not even bothering to look for more.\n\"simplified\" implies there is something more complex beforehand, but all \nit does is simple scan through the history as fast possible without \nbothering looking left or right.\n\"simplified\" implies to me it's something intentional, but this is more of \nan accidental optimization which happens to work in most situations and in \nthe special cases it just picks a random change and hopes for the best.\n\n\"git-log --full-history file\" at least produces the full change history, \nbut it has an performance impact and it doesn't produce a complete graph \nusable for graphical front ends.\n\n> >From a practical standpoint, and from having used this a long time, I'd \n> argue that the simple history is the one that you want 99.9% of all time. \n> But not _always_. Sometimes, the things that got simplified away actually \n> matter. It's rare, but it happens.\n> \n> For example, maybe you had a bug-fix that you _know_ you did, and it it \n> doesn't show up in the simplified history. That really pisses you off, and \n> it apparently really pisses Roman off that it can happen. But the fact is, \n> that still doesn't mean that the simple history is \"wrong\" or even \n> \"incomplete\".\n\nI gave more general examples. Tracking upstream source can produce this \nproblem frequently. Another example are stable/unstable branches where the \nstable branch is occasionally merged into the unstable branch can produce \nthis problem.\n\n> No, it's actually meaningful data in itself. If the bug-fix doesn't show \n> in the simplified history, then that simply means that the bug-fix was not \n> on a branch that could _possibly_ have mattered for the current contents. \n> \n> So once you are _aware_ of history simplification and are mentally able to \n> accept it, the fact that history got simplified is actually just another \n> tool.\n\nThis is your _subjective_ interpretion of this problem, because it's not a \nproblem for you, nobody else can possibly have this problem (or they just \ncrazy).\nEven if I know about this limitation it still doesn't solve the problem, \nthat _none_ of the graphical interfaces can show me a useful history graph \nof these situations.\n\nbye, Roman\n"},{"id":"85560","messageId":"alpine.LFD.1.10.0807291851120.3334@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807300315280.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-30T02:05:08Z","receivedAt":"2008-07-30T02:05:08Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 30 Jul 2008, Roman Zippel wrote:\n> > \n> > The \"gitk file\" history is the simplest one BY FAR, because it has very \n> > aggressively simplified history to the point where it tried to find the \n> > _simplest_ history that explains the current contents of 'file'[*]\n> \n> It's \"aggressively simplified\" by not even bothering to look for more.\n\nYes and no.\n\nIt's aggressively simplified because that's the right output with the \nminimal unnecessary irrelevant information. It explains how the file came \nto a particular state, with the simplest possible self-consistent history.\n\n(Again, the caveat about \"simplest possible\" always beign a local \nminimization, not a global one).\n\nThe fact that it also obviously involved less work (so git can do it \nfaster, and with fewer disk and memory accesses) is a huge bonus, of \ncourse.\n\nAre you complaining about the fact that I'm smart, and I get the right \nresult I want with less work and with a simpler algorithm?\n\nWhat's your point?\n\n> \"simplified\" implies there is something more complex beforehand, but all \n> it does is simple scan through the history as fast possible without \n> bothering looking left or right.\n\nYou're just being stupid.\n\nIt's not that it's not \"bothering\" looking left or right. It very much \n*does* bother to look left or right. But once it finds that one or the \nother explains the situation entirely, it then says \"screw left, I already \nknow that rigth gives me the information I want\".\n\nIn other words, it's doing the _smart_ thing. \n\nI don't understand why you complain about intelligence.\n\nIt's *not* just looking at one single history. Look at\n\n\tgitk kernel/sched.c\n\nand notice that the simplified history is not linear. It tries to make it \nAS LINEAR AS POSSIBLE, BUT NO MORE.\n\n \"Make everything as simple as possible, but not simpler.\"\n\t\t\t- Albert Einstein\n\nYou seem to complain about the fact that it's doing that. That's stupid of \nyou.\n\n> \"simplified\" implies to me it's something intentional, but this is more of \n> an accidental optimization which happens to work in most situations and in \n> the special cases it just picks a random change and hopes for the best.\n\nYou're just crazy. There is nothing accidental there what-so-ever.\n\n> \"git-log --full-history file\" at least produces the full change history, \n> but it has an performance impact and it doesn't produce a complete graph \n> usable for graphical front ends.\n\nUmm. You have to add \"--parents\" if you want a full graph. Without that, \nyou can never re-generate the graph anyway.\n\nAnd when you do that, it _does_ give all the commits needed to complete \nthe picture.\n\nIn other words, git (once again) is actually smarter than you, and does \nthe right thing, and (once again) you complain about something that you \njust don't understand.\n\n> I gave more general examples. Tracking upstream source can produce this \n> problem frequently. Another example are stable/unstable branches where the \n> stable branch is occasionally merged into the unstable branch can produce \n> this problem.\n\nYou call it a \"problem\", but you don't actually give any reason for \ncalling it that. IT IS NOT A PROBLEM. It's very much by design, and it's \nbecause what you want.\n\nUse --full-history if you want the full history. \n\n> This is your _subjective_ interpretion of this problem, because it's not a \n> problem for you, nobody else can possibly have this problem (or they just \n> crazy).\n\nNo, Roman. You're not crazy because you have some issue that I cannot \nunderstand. You're crazy because you make the same mistake over and over, \nand don't listen when people tell you what the mistake was.\n\n\t\"Insanity is doing the same thing over and over again and \n\t expecting different results.\"\n\t\t\t- Various\n\nPlease. People have told you where you go wrong. Many times. So why do you \nkeep repeating it?\n\nTake the time to slow down, listen, and realize that you're on the wrong \ntrack, and that others really _have_ spent time and thought on this.\n\n\t\tLinus\n"},{"id":"85561","messageId":"Pine.LNX.4.64.0807300430590.6791@localhost.localdomain","threadId":"14578","inReplyTo":"20080729125247.GC12069@sigill.intra.peff.net","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Roman Zippel","fromEmail":"zippel@linux-m68k.org","sentAt":"2008-07-30T02:48:54Z","receivedAt":"2008-07-30T02:48:54Z","isPatch":false,"sender":{"key":"zippel@linux-m68k.org","avatar":null},"body":"Hi,\n\nOn Tue, 29 Jul 2008, Jeff King wrote:\n\n> > > Perhaps I am just slow, but I haven't been able to figure out what that\n> > > history is, or what the \"correct\" output should be. Can you try to state\n> > > more clearly what it is you are looking for?\n> > \n> > Most frequently this involves changes where the same change is merged \n> > twice. Another interesting example is kernel/printk.c where a change is \n> > added and later removed again before it's merged.\n> \n> I glanced briefly over \"gitk kernel/printk.c\" and it looks pretty sane.\n> I was really hoping for you to make your case as something like:\n> \n> 1. here is an ascii diagram of an actual history graph (or a recipe of\n> git commands for making one)\n> 2. here is what git-log (or gitk) produces for this history by\n> default; and here is why it is not optimal (presumably some\n> information it fails to convey)\n> 3. here is what git-log (or gitk) with --full-history produces; and\n> here is why it is not optimal (presumably because it is too messy)\n> 4. here is what output I would like to see. Bonus points for \"and here\n> is an algorithm that accomplishes it.\"\n\nFor printk.c look for commit 02630a12c7f72fa294981c8d86e38038781c25b7 and \ntry to find it in the graphical outputs.\nHere is a bit better example than Linus gave:\n\nmkdir test\ncd test\ngit init\n\necho 1 > file1\necho a > file2\n\ngit add file1 file2\ngit commit -m \"initial commit\"\ngit tag base\n\ngit branch test1 base\ngit checkout test1\necho 2 > file1\ngit commit -a -m \"duplicate change 1\"\n\ngit branch test2 base\ngit checkout test2\necho 2 > file1\ngit commit -a -m \"duplicate change 2\"\n\ngit branch test3 base\ngit checkout test3\necho b > file2\ngit commit -a -m \"some other change\"\n\ngit checkout base\n\ngit merge test1\ngit merge test2\ngit merge test3\n\nNow compare the output of \"git-log file1\", \"git-log --full-history file1\" \nand \"git-log --full-history --parents file1\". You get either both merge \ncommits or none, but only one of it is relevant to file1.\n\nThe problem is that in practice \"git-log --full-history --parents\" \nproduces way too much information to be useful right away.\n\nbye, Roman\n"},{"id":"85562","messageId":"6E45FC6B-B5ED-4A7D-8EBA-66CE0347FFB0@sb.org","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807300430590.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Kevin Ballard","fromEmail":"kevin@sb.org","sentAt":"2008-07-30T03:20:45Z","receivedAt":"2008-07-30T03:20:45Z","isPatch":false,"sender":{"key":"kevin@sb.org","avatar":"https://avatars.githubusercontent.com/u/714?v=4"},"body":"On Jul 29, 2008, at 7:48 PM, Roman Zippel wrote:\n\n> For printk.c look for commit \n> 02630a12c7f72fa294981c8d86e38038781c25b7 and\n> try to find it in the graphical outputs.\n> Here is a bit better example than Linus gave:\n>\n> [snip]\n>\n> Now compare the output of \"git-log file1\", \"git-log --full-history \n> file1\"\n> and \"git-log --full-history --parents file1\". You get either both \n> merge\n> commits or none, but only one of it is relevant to file1.\n>\n> The problem is that in practice \"git-log --full-history --parents\"\n> produces way too much information to be useful right away.\n\nOutput looks correct to me. And of course --full-history --parents \ngives lots of output - that's what it's for. You seem to believe that \nthe appropriate output is, what, to display the initial commit, both \ncommits that modified file1, and the first merge, yes? Can you please \nclarify the logic that states that the first merge commit should be \nshown but the second should not?\n\n-Kevin Ballard\n\n-- \nKevin Ballard\nhttp://kevin.sb.org\nkevin@sb.org\nhttp://www.tildesoft.com\n"},{"id":"85563","messageId":"alpine.LFD.1.10.0807292002520.3334@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807300430590.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-30T03:21:49Z","receivedAt":"2008-07-30T03:21:49Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 30 Jul 2008, Roman Zippel wrote:\n> \n> For printk.c look for commit 02630a12c7f72fa294981c8d86e38038781c25b7 and \n> try to find it in the graphical outputs.\n\nUmm.\n\nWhy would you? Yes, it's there, if you ask for --full-history. And no, I \ndon't think --full-history is actually useful to humans - it's very much \nthere as a \"here's all the data\" thing where you could have the tools \npost-process it, where often \"post-processing\" is actually just searching \nfor it.\n\nAnd no, it's not there if you don't use --full-history.\n\nBut now, instead of _complaining_ about this, I would suggest you think \nabout why it's a _good_ thing, and why it's so useful?\n\nIn other words, you're arriving at all your complaints from the wrong \nangle entirely, and because you have convinced yourself that things have \nto work a certain way, and then you're upset when they don't.\n\nBut you should _unconvince_ yourself - and look at whether maybe all your \ninitial preconceptions were perhaps totally wrong? Because they were.\n\nThe reason that commit 02630a12c7f72fa294981c8d86e38038781c25b7 doesn't \nshow up in the normal log when looking at kernel/printk.c is that it \nreally doesn't exist as a _relevant_ part of history for the current state \nof that file. It exists only as a a side-branch for the GFS2 quota code \nthat first adds a line\n\n\t+EXPORT_SYMBOL_GPL(tty_write_message);\n\n(in commit b346671fa196a), and then removes the line not long after (in \nthat commit 02630a12c7f). And both of them go away (along with the whole \nside-branch), because they didn't end up mattering for the end result: \nthey only ever existed in that side branch, and by the time it was merged \nback into the main branch, all changes had been undone.\n\nIn other words, that change - in a VERY REAL WAY - never actually mattered \nfor the current state of kernel/printk.c. And the history simplification \nsees that, and avoids showing the whole pointless branch.\n\nThis is such an obviously _good_ thing that I really am surprised ay how \nyou can continue to argue against it. Especially as the examples you give \n\"for\" your argument are so wonderful examples _against_ it.\n\nAnd yes, you can actually force gitk to show the state of that commit and \nthus force it to acknowledge that that state was relevant (although you \nwon't necessarily force it to acknowledge that the relevance ties together \nwith the final end result). You do that by just telling it that you're not \njust interested in HEAD, but in that commit too.\n\nSo I would literally suggest that anybody interested in this subject \nreally just do\n\n\tgitk kernel/printk.c &\n\tgitk HEAD 02630a12c7f72fa294981c8d86e38038781c25b7 kernel/printk.c &\n\nin the kernel, and now compare the two side-by-side. Notice where they \ndiffer (hint: look for the commit a0f1ccfd8d37457a6d8a9e01acebeefcdfcc306e \n- \"[PATCH] lockdep: do not recurse in printk\" - which is in both, and look \nbelow it).\n\nNow, which graph is the more relevant and understandable one from the \nstandpoint of what the current state of kernel/printk.c is?\n\nHonestly now, Roman.\n\nBecause if you were actually willing to see this as a _feature_ (which it \nvery much is), you'd admit that it's a damn clever and useful one. But I \nsuspect you have dug yourself so deep into a hole that you can't admit \nthat even to yourself any more.\n\n\t\t\t\tLinus\n"},{"id":"85564","messageId":"alpine.LFD.1.10.0807292028290.3334@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"alpine.LFD.1.10.0807292002520.3334@nehalem.linux-foundation.org","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-30T03:35:54Z","receivedAt":"2008-07-30T03:35:54Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 29 Jul 2008, Linus Torvalds wrote:\n> \n> In other words, that change - in a VERY REAL WAY - never actually mattered \n> for the current state of kernel/printk.c. And the history simplification \n> sees that, and avoids showing the whole pointless branch.\n\nBtw, Roman, this is a really really important thing for you to realize. \n\nYou need to realize that your \"perfect\" output really REALLY is totally \ninferior, if what you are actually interested in is \"how did things get to \nbe the way they are\".\n\nIt's a _feature_. It's not a bug. And it's a really good one.\n\nIf side branches didn't matter for the contents of the file, those side \nbranches simply don't matter, and showing them is just a distraction.\n\nYes, you can ask for the history that doesn't matter for the end result. \nAnd yes, I acknowledge freely that it would be good to then have a \nseparate cleanup phase to make that thing more readable. In fact, in the \nvery first reply to you I pointed you to a thread where I said exactly \nthat, long before this thread even started.\n\nBut no, the current default isn't broken. No, it's not \"lazy\" either. No, \nit was not an \"accident\". And no, it's not \"incorrect\".\n\nAnd until you can see that (along with all the reasons I've outlined why \nyour \"fixed\" approach is a total piece of sh*t from a performance angle), \nyou're just being stupid.\n\n\t\t\t\tLinus\n"},{"id":"85565","messageId":"20080730042330.GA3350@sigill.intra.peff.net","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807300430590.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-07-30T04:23:31Z","receivedAt":"2008-07-30T04:23:31Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 30, 2008 at 04:48:54AM +0200, Roman Zippel wrote:\n\n> Now compare the output of \"git-log file1\", \"git-log --full-history file1\" \n> and \"git-log --full-history --parents file1\". You get either both merge \n> commits or none, but only one of it is relevant to file1.\n\nAh, I see.\n\nSo if I understand you, you wanted to see something like:\n\n\nA--B\n \\ \\\n C--D\n\nwhere\n\n A = initial commit\n B = duplicate change 1\n C = duplicate change 2\n D = merge branch 'test2' into HEAD\n\nwhere the simplification isn't as aggressive (you still see the\nduplicate commits and the merge), but we can get rid of the later merge\nbetween A and D because A is already an ancestor of D.\n\nSo do you have a proposed set of simplification rules that will produce\nthat output?\n\n-Peff\n"},{"id":"85566","messageId":"20080730042609.GB3350@sigill.intra.peff.net","threadId":"14578","inReplyTo":"alpine.LFD.1.10.0807291006070.3334@nehalem.linux-foundation.org","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2008-07-30T04:26:09Z","receivedAt":"2008-07-30T04:26:09Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 29, 2008 at 10:25:35AM -0700, Linus Torvalds wrote:\n\n> On Tue, 29 Jul 2008, Jeff King wrote:\n> > \n> > I glanced briefly over \"gitk kernel/printk.c\" and it looks pretty sane.\n> \n> Jeff, it _is_ sane. When Roman says it's \"incorrect\", he is just wrong.\n\nI agree with you, btw. It is definitely correct and useful; however, I\nam curious if there is some \"in between\" level of simplification that\nmight produce an alternate graph that has interesting features. And that\nis why I am trying to get Roman to lay out exactly what it is he wants.\n\n-Peff\n"},{"id":"85570","messageId":"alpine.LFD.1.10.0807292126430.3334@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"20080730042609.GB3350@sigill.intra.peff.net","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-30T04:52:35Z","receivedAt":"2008-07-30T04:52:35Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 30 Jul 2008, Jeff King wrote:\n> \n> I agree with you, btw. It is definitely correct and useful; however, I\n> am curious if there is some \"in between\" level of simplification that\n> might produce an alternate graph that has interesting features. And that\n> is why I am trying to get Roman to lay out exactly what it is he wants.\n\nActually, I know what he wants, since I tried to describe it for the \nfilter-branch discussion. It's really not that conceptually complex.\n\nBasically, the stupid model is to just do this:\n\n - start with --full-history\n\n - for each merge, look at both parents. If one parent leads directly to \n a commit that can be reached from the the other, just remove that \n parent as being redundant. And if that removal leads to a merge now \n becoming a non-merge, and it has no changes wrt its single remaining \n parent, remove the commit entirely (rewriting any parenthood to make \n the rest all stay together, of course)\n\n - repeat until you cannot do any more simplification (removing one commit \n can actually cause its children to now become targets for this \n simplification).\n\nand I suspect that\n\n (a) the stupid model is probably at least O(n^3) if done stupidly and \n O(n^2) with some modest amount of smarts (keeping a list of at least \n potential targets of simplification and expanding it only when \n actually simplifying), but that\n (b) you can concentrate on just the merges that the current optimizing \n algorithm would have removed, so 'n' is not the total number of \n commits, but at most the number of merges, and more likely actually \n just the number of trivial merges in that file, and finally\n (c) there is likely some smart and efficient graph minimization algorithm \n that is O(nlogn) or something.\n\nso I don't think it's likely to be hugely more expensive than the \ntopo-sort is. All the real expense is in the same thing the topo-sort \nexpense, namely in generating the list up-front.\n\nI bet googling for \"minimal directed acyclic graph\" will give pointers.\n\nAnd despite the fact that I've argued against Roman's world-view, I \nactually _do_ think it would be nice to have that third mode, the same way \nthat we have --topo-order. It wouldn't be good for the _default_ view, but \nthen neither is --full-history, so that's not a big argument.\n\nThat said, I'd like to (again) repeat the caveat that it's probably best \ndone in the tool that actally visualizes the mess - exactly for the same \nreason that I argued for the topological sort being done in gitk. It's \nvery painful to have to wait for the first few commits to start appearing \nin the history window.\n\nAdmittedly most of my work is actually done on machines that are pretty \nfast, but every once in a while I travel with a laptop. And more \nimportantly, not everybody gets new hardware from Intel for testing even \nbefore the CPU has been released. So others will still appreciate \nincremental history updates, even if my machine might be fast enough (and \nmy kernel tree always in the caches) that I myself could live with a \nsynchronous version a-la --topo-order.\n\n\t\t\tLinus\n"},{"id":"85591","messageId":"m3iqunu5u3.fsf@localhost.localdomain","threadId":"14578","inReplyTo":"Pine.LNX.4.64.0807291433430.6791@localhost.localdomain","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2008-07-30T08:36:11Z","receivedAt":"2008-07-30T08:36:11Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Roman Zippel writes:\n\n> I don't quite understand what you're trying to say.\n> To avoid further confusion it maybe helps to specify a few of the terms:\n> \n> - full history graph: produced by \"git-log --full-history --parents\"\n> - compact history graph: the full history graph without without any \n> repeated merges, this is what my example script produces.\n> - full simplified history: output of \"git-log --full-history\"\n> - short simplified history: standard output of \"git-log\"\n[...]\n\n> Keep in mind that e.g. git-web is using the full simplified history, so \n> what I'm offering also has the potential to improve git-web performance...\n\nThe fact that gitweb is using --full-history for a 'history' view\nis a historical reason, backwards compatibility with the view that\nwas shown before gitweb used \"git rev-list [flags] -- \", see\ncommit cdd4037d\n\n gitweb: optimize per-file history generation\n \n The rev-list command that is recent enough can filter commits\n based on paths they touch, so use it instead of generating the\n full list and limiting it by passing it with diff-tree --stdin.\n \n [jc: The patch originally came from Luben Tuikov but the it was\n corrupt, but it was short enough to be applied by hand. I\n added the --full-history to make the output compatible with the\n original while doing so.]\n \n Signed-off-by: Junio C Hamano \n\nRemoving '--parents' was put later, to remove unnecessary merges\nfrom a view (there was long discussion on git mailing list about\n--full-history with and without --parents), in 208b2dff\n\n gitweb: We do longer need the --parents flag in rev-list.\n \n We only want to know the direct parents of a given commit object,\n these parents are available in the --header output of rev-list. If\n --parents is supplied with --full-history the output includes merge\n commits that aren't relevant.\n \n Signed-off-by: Robert Fitzsimons \n Signed-off-by: Junio C Hamano \n\nBesides gitweb currently does not generate graphical history view,\nso '--parents' are unnecessary.\n\nBut if it was done from the scratch, gitweb should definitely\nuse simplified history, instead of what you call \"full simplified\nhistory\", perhaps with an option to use '--full-history' (there\nis infractructure in gitweb for adding extra options).\n\n\n(Nitpick: it is 'gitweb', not 'git-web'.)\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"85712","messageId":"7vej5b3ozz.fsf@gitster.siamese.dyndns.org","threadId":"14578","inReplyTo":"alpine.LFD.1.10.0807291738280.3334@nehalem.linux-foundation.org","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-30T23:56:32Z","receivedAt":"2008-07-30T23:56:32Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> But the reverse isn't true: the current primary formats cannot be \n> generated from your preferred format without losing something important \n> (performance).\n>\n> But I'll make you a deal: if you actually write the filter in C form, I \n> can pretty much guarantee that we can easily add it as a new flag. It \n> really should be pretty easy to integrate it into the revision parsing \n> machinery alongside --topo-order, since it's really the same kind of \n> operation.\n\nI am not Roman, but so I do not know if I did what Roman wanted to, but\nhere is a quick hack. \"gitk --post-simplify -- kernel/printk.c\" is\nslightly more readable than --full-history with this patch.\n\n-- >8 --\nSubject: [PATCH] revision traversal: teach --post-simplify\n\nThe --full-history traversal keeps all merges and non-merge commits that\ntouch paths in the given pathspec. This is useful to view both sides of a\nmerge in a topology like this:\n\n A---M---o\n / /\n ---O---B\n\nwhen A and B makes identical change to the given paths. The revision\ntraversal without --full-history aims to come up with a simplest history\nto explain the final state of the tree, and one of the side branches can\nbe pruned away.\n\nThe behaviour to keep all merges however is inconvenient if neither A nor\nB touches the paths we are interested in. --full-history reduces the\ntopology to:\n\n ---O---M---o\n\nin such a case, without removing M.\n\nThis adds a post processing phase on top of --full-history traversal to\nremove needless merges from the resulting history.\n\nThe idea is to compute, for each commit in the \"full history\" result set,\nthe commit that should replace it in the simplified history. This\nreplacement commit is defined as follows:\n\n * In any case, we first figure out the replacement commits of parents of\n the commit we are looking at. The commit we are looking at is\n rewritten as if its parents are replacement commits of its original\n parents.\n\n * If the commit is marked as TREESAME (i.e. it modifies the paths we are\n interested in), then the replacement commit is itself. IOW, the commit\n is not dropped from the final result.\n\n * Otherwise, we examine the parents of the commit.\n\n - If they replace to the same commit, because the commit we are looking\n at itself does not touch the interesting paths, we replace the commit\n we are looking at with the replacement commit of its parents.\n\n - If some of the parents replace to one commit, and some other parents\n replace to another different commit, the commit we are looking at\n needs to stay as a merge in the final result.\n\nThe algorithm outlined above alone does not quite work; the reason is\nbecause \"all parents are replaced by the same commit\" rule is too strict.\nIt needs to be relaxed to remove parents that are ancestor of some other\nparents, and that is why post_simplify_one() calls a rather expensive\nreduce_heads().\n\nSigned-off-by: Junio C Hamano \n---\n revision.c | 125 ++++++++++++++++++++++++++++++++++++++++++++++++++----------\n revision.h | 1 +\n 2 files changed, 106 insertions(+), 20 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 3897fec..a843c42 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1045,6 +1045,10 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t} else if (!strcmp(arg, \"--topo-order\")) {\n \t\trevs->lifo = 1;\n \t\trevs->topo_order = 1;\n+\t} else if (!strcmp(arg, \"--post-simplify\")) {\n+\t\trevs->post_simplify = 1;\n+\t\trevs->topo_order = 1;\n+\t\trevs->simplify_history = 0;\n \t} else if (!strcmp(arg, \"--date-order\")) {\n \t\trevs->lifo = 0;\n \t\trevs->topo_order = 1;\n@@ -1378,6 +1382,105 @@ static void add_child(struct rev_info *revs, struct commit *parent, struct commi\n \tl->next = add_decoration(&revs->children, &parent->object, l);\n }\n \n+static int remove_duplicate_parents(struct commit *commit)\n+{\n+\tstruct commit_list **pp, *p;\n+\tint surviving_parents;\n+\n+\t/* Examine existing parents while marking ones we have seen... */\n+\tpp = &commit->parents;\n+\twhile ((p = *pp) != NULL) {\n+\t\tstruct commit *parent = p->item;\n+\t\tif (parent->object.flags & TMP_MARK) {\n+\t\t\t*pp = p->next;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tparent->object.flags |= TMP_MARK;\n+\t\tpp = &p->next;\n+\t}\n+\t/* count them while clearing the temporary mark */\n+\tsurviving_parents = 0;\n+\tfor (p = commit->parents; p; p = p->next) {\n+\t\tp->item->object.flags &= ~TMP_MARK;\n+\t\tsurviving_parents++;\n+\t}\n+\treturn surviving_parents;\n+}\n+\n+static int post_simplify_one(struct commit *commit)\n+{\n+\tstruct commit_list *p;\n+\tint num_parents;\n+\n+\tfor (p = commit->parents; p; p = p->next)\n+\t\tif (!p->item->util)\n+\t\t\treturn 0;\n+\n+\t/* All of our parents know what they should be rewritten to */\n+\tfor (p = commit->parents; p; p = p->next)\n+\t\tp->item = p->item->util;\n+\tnum_parents = remove_duplicate_parents(commit);\n+\n+\tif (1 < num_parents) {\n+\t\tstruct commit_list *h = reduce_heads(commit->parents);\n+\t\tnum_parents = commit_list_count(h);\n+\t\tfree_commit_list(commit->parents);\n+\t\tcommit->parents = h;\n+\t}\n+\n+\t/*\n+\t * We stand for ourselves if we are root, if we change the tree,\n+\t * or if we are a merge and our parents simplify to different\n+\t * commits. Otherwise we can be replaced by the commit our\n+\t * sole parent is replaced by.\n+\t */\n+\tif (!num_parents ||\n+\t !(commit->object.flags & TREESAME) ||\n+\t (1 < num_parents))\n+\t\tcommit->util = commit;\n+\telse\n+\t\tcommit->util = commit->parents->item->util;\n+\n+\treturn 1;\n+}\n+\n+static void post_simplify(struct rev_info *revs)\n+{\n+\tstruct commit_list *list;\n+\tstruct commit_list *yet_to_do, **tail;\n+\n+\t/* feed the list reversed */\n+\tyet_to_do = NULL;\n+\tfor (list = revs->commits; list; list = list->next)\n+\t\tcommit_list_insert(list->item, &yet_to_do);\n+\twhile (yet_to_do) {\n+\t\tlist = yet_to_do;\n+\t\tyet_to_do = NULL;\n+\t\ttail = &yet_to_do;\n+\t\twhile (list) {\n+\t\t\tstruct commit *commit = list->item;\n+\t\t\tstruct commit_list *next = list->next;\n+\t\t\tfree(list);\n+\t\t\tlist = next;\n+\t\t\tif (!post_simplify_one(commit))\n+\t\t\t\ttail = &commit_list_insert(commit, tail)->next;\n+\t\t}\n+\t}\n+\n+\t/* clean up the result, removing the simplified ones */\n+\tlist = revs->commits;\n+\trevs->commits = NULL;\n+\ttail = &revs->commits;\n+\twhile (list) {\n+\t\tstruct commit *commit = list->item;\n+\t\tstruct commit_list *next = list->next;\n+\t\tfree(list);\n+\t\tlist = next;\n+\t\tif (commit->util == commit)\n+\t\t\ttail = &commit_list_insert(commit, tail)->next;\n+\t}\n+}\n+\n static void set_children(struct rev_info *revs)\n {\n \tstruct commit_list *l;\n@@ -1418,6 +1521,8 @@ int prepare_revision_walk(struct rev_info *revs)\n \t\t\treturn -1;\n \tif (revs->topo_order)\n \t\tsort_in_topological_order(&revs->commits, revs->lifo);\n+\tif (revs->post_simplify)\n+\t\tpost_simplify(revs);\n \tif (revs->children.name)\n \t\tset_children(revs);\n \treturn 0;\n@@ -1450,26 +1555,6 @@ static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp\n \t}\n }\n \n-static void remove_duplicate_parents(struct commit *commit)\n-{\n-\tstruct commit_list **pp, *p;\n-\n-\t/* Examine existing parents while marking ones we have seen... */\n-\tpp = &commit->parents;\n-\twhile ((p = *pp) != NULL) {\n-\t\tstruct commit *parent = p->item;\n-\t\tif (parent->object.flags & TMP_MARK) {\n-\t\t\t*pp = p->next;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tparent->object.flags |= TMP_MARK;\n-\t\tpp = &p->next;\n-\t}\n-\t/* ... and clear the temporary mark */\n-\tfor (p = commit->parents; p; p = p->next)\n-\t\tp->item->object.flags &= ~TMP_MARK;\n-}\n-\n static int rewrite_parents(struct rev_info *revs, struct commit *commit)\n {\n \tstruct commit_list **pp = &commit->parents;\ndiff --git a/revision.h b/revision.h\nindex f64e8ce..953e69b 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -41,6 +41,7 @@ struct rev_info {\n \t\t\tsimplify_history:1,\n \t\t\tlifo:1,\n \t\t\ttopo_order:1,\n+\t\t\tpost_simplify:1,\n \t\t\ttag_objects:1,\n \t\t\ttree_objects:1,\n \t\t\tblob_objects:1,\n-- \n1.6.0.rc1.29.gc4aca\n"},{"id":"85717","messageId":"7vabfy52p0.fsf@gitster.siamese.dyndns.org","threadId":"14578","inReplyTo":"7vej5b3ozz.fsf@gitster.siamese.dyndns.org","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-31T00:15:23Z","receivedAt":"2008-07-31T00:15:23Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> The idea is to compute, for each commit in the \"full history\" result set,\n> the commit that should replace it in the simplified history. This\n> replacement commit is defined as follows:\n>\n> * In any case, we first figure out the replacement commits of parents of\n> the commit we are looking at. The commit we are looking at is\n> rewritten as if its parents are replacement commits of its original\n> parents.\n>\n> * If the commit is marked as TREESAME (i.e. it modifies the paths we are\n> interested in), then the replacement commit is itself. IOW, the commit\n> is not dropped from the final result.\n\nA typo here. This comment should have said !TREESAME (the code is correct).\n"},{"id":"85720","messageId":"alpine.LFD.1.10.0807301720170.3277@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"7vej5b3ozz.fsf@gitster.siamese.dyndns.org","subject":"Re: Bizarre missing changes (git bug?)","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-31T00:30:57Z","receivedAt":"2008-07-31T00:30:57Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 30 Jul 2008, Junio C Hamano wrote:\n> \n> I am not Roman, but so I do not know if I did what Roman wanted to, but\n> here is a quick hack. \"gitk --post-simplify -- kernel/printk.c\" is\n> slightly more readable than --full-history with this patch.\n\n.. and if by \"slightly\", you mean \"a lot\", then yes.\n\nPatch looks fine to me. I didn't look at the code logic very closely, but \nI suspect that it's actually hard to get the right answer with broken \ncode, and the logic doesn't look broken. So Ack.\n\nThe filter-branch thing should probably be taught about this at least as \nan option. I think it was Johannes Sixt that worried about that one. Added \nto cc.\n\n\t\tLinus\n"},{"id":"85742","messageId":"7vhca6zcuy.fsf@gitster.siamese.dyndns.org","threadId":"14578","inReplyTo":"7vej5b3ozz.fsf@gitster.siamese.dyndns.org","subject":"[PATCH v2] revision traversal: show full history with merge simplification","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-31T08:17:41Z","receivedAt":"2008-07-31T08:17:41Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"The --full-history traversal keeps all merges in addition to non-merge\ncommits that touch paths in the given pathspec. This is useful to view\nboth sides of a merge in a topology like this:\n\n A---M---o\n / /\n ---O---B\n\neven when A and B makes identical change to the given paths. The revision\ntraversal without --full-history aims to come up with the simplest history\nto explain the final state of the tree, and one of the side branches can\nbe pruned away.\n\nThe behaviour to keep all merges however is inconvenient if neither A nor\nB touches the paths we are interested in. --full-history reduces the\ntopology to:\n\n ---O---M---o\n\nin such a case, without removing M.\n\nThis adds a post processing phase on top of --full-history traversal to\nremove needless merges from the resulting history.\n\nThe idea is to compute, for each commit in the \"full history\" result set,\nthe commit that should replace it in the simplified history. The commit\nto replace it in the final history is determined as follows:\n\n * In any case, we first figure out the replacement commits of parents of\n the commit we are looking at. The commit we are looking at is\n rewritten as if the replacement commits of its original parents are its\n parents. While doing so, we reduce the redundant parents from the\n rewritten parent list by not just removing the identical ones, but also\n removing a parent that is an ancestor of another parent.\n\n * After the above parent simplification, if the commit is a root commit,\n an UNINTERESTING commit, a merge commit, or modifies the paths we are\n interested in, then the replacement commit of the commit is itself. In\n other words, such a commit is not dropped from the final result.\n\nThe first point above essentially means that the history is rewritten in\nthe bottom up direction. We can rewrite the parent list of a commit only\nafter we know how all of its parents are rewritten. This means that the\nprocessing needs to happen on the full history (i.e. after limit_list()).\n\nSigned-off-by: Junio C Hamano \n---\n\n * Changes from the \"quick hack\" are:\n\n - When the history is bounded at the bottom, the v1 patch did not\n terminate, because it wanted to know the replacement for\n UNINTERESTING parents of commits on revs->commit list, but these\n parents were never processed. Oops.\n\n - The option implies rewrite_parents. I was tempted to make it imply\n \"--parents\" (which would make it always emit parent information as\n well), but didn't.\n\n - Toposort is still implied but it is done at the end.\n\n - The code is more heavily commented.\n\n - I do not think \"--post-simplify\" is particulary a good name, but I\n couldn't come up with a good one. To mark it clearly not ready for\n 'master', I changed the name to a meaningless word for now ;-)\n\n * Timings (best of 5 runs)\n\n $ git rev-list --parents --full-history --topo-order HEAD -- kernel/printk.c\n 3.75user 0.47system 0:04.22elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n\n $ git rev-list --parents --oyoyo HEAD -- kernel/printk.c\n 4.31user 0.06system 0:04.37elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k\n\n $ git rev-list --parents --full-history HEAD -- kernel/printk.c | head -n 200\n 0.16user 0.02system 0:00.18elapsed 103%CPU (0avgtext+0avgdata 0maxresident)k\n\n revision.c | 171 +++++++++++++++++++++++++++++++++++++++++++++++++++++-------\n revision.h | 1 +\n 2 files changed, 152 insertions(+), 20 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 3897fec..3b59e02 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1045,6 +1045,11 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t} else if (!strcmp(arg, \"--topo-order\")) {\n \t\trevs->lifo = 1;\n \t\trevs->topo_order = 1;\n+\t} else if (!strcmp(arg, \"--oyoyo\")) {\n+\t\trevs->post_simplify = 1;\n+\t\trevs->rewrite_parents = 1;\n+\t\trevs->simplify_history = 0;\n+\t\trevs->limited = 1;\n \t} else if (!strcmp(arg, \"--date-order\")) {\n \t\trevs->lifo = 0;\n \t\trevs->topo_order = 1;\n@@ -1378,6 +1383,150 @@ static void add_child(struct rev_info *revs, struct commit *parent, struct commi\n \tl->next = add_decoration(&revs->children, &parent->object, l);\n }\n \n+static int remove_duplicate_parents(struct commit *commit)\n+{\n+\tstruct commit_list **pp, *p;\n+\tint surviving_parents;\n+\n+\t/* Examine existing parents while marking ones we have seen... */\n+\tpp = &commit->parents;\n+\twhile ((p = *pp) != NULL) {\n+\t\tstruct commit *parent = p->item;\n+\t\tif (parent->object.flags & TMP_MARK) {\n+\t\t\t*pp = p->next;\n+\t\t\tcontinue;\n+\t\t}\n+\t\tparent->object.flags |= TMP_MARK;\n+\t\tpp = &p->next;\n+\t}\n+\t/* count them while clearing the temporary mark */\n+\tsurviving_parents = 0;\n+\tfor (p = commit->parents; p; p = p->next) {\n+\t\tp->item->object.flags &= ~TMP_MARK;\n+\t\tsurviving_parents++;\n+\t}\n+\treturn surviving_parents;\n+}\n+\n+static struct commit_list **post_simplify_one(struct commit *commit, struct commit_list **tail)\n+{\n+\tstruct commit_list *p;\n+\tint cnt;\n+\n+\t/*\n+\t * We store which commit each one simplifies to in its util field.\n+\t * Have we handled this one?\n+\t */\n+\tif (commit->util)\n+\t\treturn tail;\n+\n+\t/*\n+\t * An UNINTERESTING commit simplifies to itself, so does a\n+\t * root commit. We do not rewrite parents of such commit\n+\t * anyway.\n+\t */\n+\tif ((commit->object.flags & UNINTERESTING) || !commit->parents) {\n+\t\tcommit->util = commit;\n+\t\treturn tail;\n+\t}\n+\n+\t/*\n+\t * Do we know what commit all of our parents should be rewritten to?\n+\t * Otherwise we are not ready to rewrite this one yet.\n+\t */\n+\tfor (cnt = 0, p = commit->parents; p; p = p->next) {\n+\t\tif (!p->item->util) {\n+\t\t\ttail = &commit_list_insert(p->item, tail)->next;\n+\t\t\tcnt++;\n+\t\t}\n+\t}\n+\tif (cnt)\n+\t\treturn tail;\n+\n+\t/*\n+\t * Rewrite our list of parents.\n+\t */\n+\tfor (p = commit->parents; p; p = p->next)\n+\t\tp->item = p->item->util;\n+\tcnt = remove_duplicate_parents(commit);\n+\n+\t/*\n+\t * It is possible that we are a merge and one side branch\n+\t * does not have any commit that touches the given paths;\n+\t * in such a case, the immediate parents will be rewritten\n+\t * to different commits.\n+\t *\n+\t * o----X\t\tX: the commit we are looking at;\n+\t * / /\t\to: a commit that touches the paths;\n+\t * ---o----'\n+\t *\n+\t * Further reduce the parents by removing redundant parents.\n+\t */\n+\tif (1 < cnt) {\n+\t\tstruct commit_list *h = reduce_heads(commit->parents);\n+\t\tcnt = commit_list_count(h);\n+\t\tfree_commit_list(commit->parents);\n+\t\tcommit->parents = h;\n+\t}\n+\n+\t/*\n+\t * A commit simplifies to itself if it is a root, if it is\n+\t * UNINTERESTING, if it touches the given paths, or if it is a\n+\t * merge and its parents simplifies to more than one commits\n+\t * (the first two cases are already handled at the beginning of\n+\t * this function).\n+\t *\n+\t * Otherwise, it simplifies to what its sole parent simplifies to.\n+\t */\n+\tif (!cnt ||\n+\t (commit->object.flags & UNINTERESTING) ||\n+\t !(commit->object.flags & TREESAME) ||\n+\t (1 < cnt))\n+\t\tcommit->util = commit;\n+\telse\n+\t\tcommit->util = commit->parents->item->util;\n+\treturn tail;\n+}\n+\n+static void post_simplify(struct rev_info *revs)\n+{\n+\tstruct commit_list *list;\n+\tstruct commit_list *yet_to_do, **tail;\n+\n+\t/* feed the list reversed */\n+\tyet_to_do = NULL;\n+\tfor (list = revs->commits; list; list = list->next)\n+\t\tcommit_list_insert(list->item, &yet_to_do);\n+\twhile (yet_to_do) {\n+\t\tlist = yet_to_do;\n+\t\tyet_to_do = NULL;\n+\t\ttail = &yet_to_do;\n+\t\twhile (list) {\n+\t\t\tstruct commit *commit = list->item;\n+\t\t\tstruct commit_list *next = list->next;\n+\t\t\tfree(list);\n+\t\t\tlist = next;\n+\t\t\ttail = post_simplify_one(commit, tail);\n+\t\t}\n+\t}\n+\n+\t/* clean up the result, removing the simplified ones */\n+\tlist = revs->commits;\n+\trevs->commits = NULL;\n+\ttail = &revs->commits;\n+\twhile (list) {\n+\t\tstruct commit *commit = list->item;\n+\t\tstruct commit_list *next = list->next;\n+\t\tfree(list);\n+\t\tlist = next;\n+\t\tif (commit->util == commit)\n+\t\t\ttail = &commit_list_insert(commit, tail)->next;\n+\t}\n+\n+\t/* sort topologically at the end */\n+\tsort_in_topological_order(&revs->commits, revs->lifo);\n+}\n+\n static void set_children(struct rev_info *revs)\n {\n \tstruct commit_list *l;\n@@ -1418,6 +1567,8 @@ int prepare_revision_walk(struct rev_info *revs)\n \t\t\treturn -1;\n \tif (revs->topo_order)\n \t\tsort_in_topological_order(&revs->commits, revs->lifo);\n+\tif (revs->post_simplify)\n+\t\tpost_simplify(revs);\n \tif (revs->children.name)\n \t\tset_children(revs);\n \treturn 0;\n@@ -1450,26 +1601,6 @@ static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp\n \t}\n }\n \n-static void remove_duplicate_parents(struct commit *commit)\n-{\n-\tstruct commit_list **pp, *p;\n-\n-\t/* Examine existing parents while marking ones we have seen... */\n-\tpp = &commit->parents;\n-\twhile ((p = *pp) != NULL) {\n-\t\tstruct commit *parent = p->item;\n-\t\tif (parent->object.flags & TMP_MARK) {\n-\t\t\t*pp = p->next;\n-\t\t\tcontinue;\n-\t\t}\n-\t\tparent->object.flags |= TMP_MARK;\n-\t\tpp = &p->next;\n-\t}\n-\t/* ... and clear the temporary mark */\n-\tfor (p = commit->parents; p; p = p->next)\n-\t\tp->item->object.flags &= ~TMP_MARK;\n-}\n-\n static int rewrite_parents(struct rev_info *revs, struct commit *commit)\n {\n \tstruct commit_list **pp = &commit->parents;\ndiff --git a/revision.h b/revision.h\nindex f64e8ce..953e69b 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -41,6 +41,7 @@ struct rev_info {\n \t\t\tsimplify_history:1,\n \t\t\tlifo:1,\n \t\t\ttopo_order:1,\n+\t\t\tpost_simplify:1,\n \t\t\ttag_objects:1,\n \t\t\ttree_objects:1,\n \t\t\tblob_objects:1,\n-- \n1.6.0.rc1.31.gf448e\n"},{"id":"85743","messageId":"7vd4kuzcst.fsf@gitster.siamese.dyndns.org","threadId":"14578","inReplyTo":"7vhca6zcuy.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH v2] revision traversal: show full history with merge simplification","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-31T08:18:58Z","receivedAt":"2008-07-31T08:18:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"If you look at the output from the \"kernel/printk.c\" with this patch, you\nwould notice that there still are somewhat meaningless merges shown in the\nhistory (e.g. scroll down to 185a257f2f73bcd89050ad02da5bedbc28fc43fa).\n\nThe mainline side keeps making steady changes to the path, but the side\nbranch that made tty_write_message available to others with b346671\n([PATCH] Export tty_write_message() for GFS2 quota code, 2006-01-16) keeps\nmany \"Merge from master\" until it is merged back to the mainline, even\nafter the earlier change is reverted by 02630a1 ([GFS2] Remove dependance\non tty_write_message(), 2006-07-03).\n\nI wonder if we can do something clever to reduce these pointless (from the\npoint of view of explaining kernel/printk.c's evolution, at least) merges\nfrom the output. This might be another example of the reason why it is a\ngood thing that you keep teaching people: \"On your xyzzy topic, you are\ndoing xyzzy development, not xyzzy development plus random changes ---\ndon't merge my tree into yours!\", and we could dismiss these extra merges\nwe see in the output as artifacts from a bad practice, but as long as we\nare spending extra cycles, it would be better if we could reduce such\nclutter.\n\nI am still undecided about the option name.\n\nThe existing --full-history is \"show history fully without simplifying the\nmerge at all\". This is \"show history fully with merge simplification\".\nPerhaps --simplify-merges?\n"},{"id":"85838","messageId":"7vabfxyacx.fsf_-_@gitster.siamese.dyndns.org","threadId":"14578","inReplyTo":"7vhca6zcuy.fsf@gitster.siamese.dyndns.org","subject":"[PATCH v3-wip] revision traversal: show full history with merge simplification","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-31T22:09:18Z","receivedAt":"2008-07-31T22:09:18Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This one makes it incremental. It is not relative to v2 but on top of\n'master'.\n\nThe idea and the logic to find what parents to rewrite is the same as the\nprevious one, but this one works incrementally as much as possible. When\nyou have this topology, where commits with capital letters are the ones\nthat change the paths you are interested in:\n\n\n A---M---o---C---D---o\n / /\n ---o---B\n\n(1) we can tell that the rightmost one 'o' is not we want to show, without\n digging any further than D;\n\n(2) we can show D after inspecting C without digging any further. C is\n the sole parent of D, and C itself is an interesting one, so D's\n parent will stay to be C and not its ancestor.\n\n(3) before showing C, we need to know what the rewritten parent of it\n would be; we need to dig down to M and notice that it has two parents\n that simplify to a different commit (both A and B touch the path we\n are interested in), so M simplifies to itself and it becomes the\n parent of C. IOW, we need to dig no further than A and B in order to\n show C.\n\n$ time sh -c 'git log --pretty=oneline --abbrev-commit \\\n\t--simplify-merges --parents \\\n\t-- kernel/printk.c | head -n 1'\n5dfb66b... 1d9b9f6... c9272c4... Merge branch 'for-linus' of git://git.o-hand.com/linux-mfd\n\nreal 0m0.344s\nuser 0m0.324s\nsys 0m0.020s\n\nThe same query with 's/| head -n 1/>/dev/null' is more expensive. In fact\nit is much more expensive than the non-incremental one (v2), and about\nthree times more expensive than non-limiting --full-history for explaining\nthe history of kernel/printk.c. There must be opportunity to further\noptimize this, but I'd stop here for now, as you keep saying this is hard,\nand if I continue thinking about this any longer my head would explode ;-)\n\n---\n revision.c | 106 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++--\n revision.h | 1 +\n 2 files changed, 103 insertions(+), 4 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 3897fec..9554a70 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -1045,6 +1045,10 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t} else if (!strcmp(arg, \"--topo-order\")) {\n \t\trevs->lifo = 1;\n \t\trevs->topo_order = 1;\n+\t} else if (!strcmp(arg, \"--simplify-merges\")) {\n+\t\trevs->simplify_merges = 1;\n+\t\trevs->rewrite_parents = 1;\n+\t\trevs->simplify_history = 0;\n \t} else if (!strcmp(arg, \"--date-order\")) {\n \t\trevs->lifo = 0;\n \t\trevs->topo_order = 1;\n@@ -1450,9 +1454,10 @@ static enum rewrite_result rewrite_one(struct rev_info *revs, struct commit **pp\n \t}\n }\n \n-static void remove_duplicate_parents(struct commit *commit)\n+static int remove_duplicate_parents(struct commit *commit)\n {\n \tstruct commit_list **pp, *p;\n+\tint surviving_parents;\n \n \t/* Examine existing parents while marking ones we have seen... */\n \tpp = &commit->parents;\n@@ -1465,9 +1470,13 @@ static void remove_duplicate_parents(struct commit *commit)\n \t\tparent->object.flags |= TMP_MARK;\n \t\tpp = &p->next;\n \t}\n-\t/* ... and clear the temporary mark */\n-\tfor (p = commit->parents; p; p = p->next)\n+\t/* count them while clearing the temporary mark */\n+\tsurviving_parents = 0;\n+\tfor (p = commit->parents; p; p = p->next) {\n \t\tp->item->object.flags &= ~TMP_MARK;\n+\t\tsurviving_parents++;\n+\t}\n+\treturn surviving_parents;\n }\n \n static int rewrite_parents(struct rev_info *revs, struct commit *commit)\n@@ -1536,6 +1545,89 @@ enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit)\n \treturn commit_show;\n }\n \n+static void simplify_merges(struct rev_info *revs, struct commit *commit)\n+{\n+\tstruct commit_list *work = NULL;\n+\n+\tcommit_list_insert(commit, &work);\n+\twhile (!commit->util && work) {\n+\t\tstruct commit *c;\n+\t\tstruct commit_list *p;\n+\t\tint cnt;\n+\n+\t\tc = pop_commit(&work);\n+\t\tif (c->util)\n+\t\t\tcontinue;\n+\t\tif ((c->object.flags & UNINTERESTING) || !c->parents) {\n+\t\t\tc->util = c;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\t/*\n+\t\t * Do we know what commit all of the parents of this\n+\t\t * should be rewritten to? Otherwise we are not ready\n+\t\t * to rewrite this one yet.\n+\t\t */\n+\t\tfor (cnt = 0, p = c->parents; p; p = p->next) {\n+\t\t\tif (!p->item->util) {\n+\t\t\t\tif (!cnt)\n+\t\t\t\t\tcommit_list_insert(c, &work);\n+\t\t\t\tcommit_list_insert(p->item, &work);\n+\t\t\t\tcnt++;\n+\t\t\t}\n+\t\t}\n+\t\tif (cnt)\n+\t\t\tcontinue;\n+\n+\t\t/*\n+\t\t * Rewrite the list of parents.\n+\t\t */\n+\t\tfor (p = c->parents; p; p = p->next)\n+\t\t\tp->item = p->item->util;\n+\t\tcnt = remove_duplicate_parents(c);\n+\n+\t\t/*\n+\t\t * It is possible that this is a merge and one side\n+\t\t * branch does not have any commit that touches the\n+\t\t * given paths; in such a case, the immediate parents\n+\t\t * will be rewritten to different commits if we do not\n+\t\t * reduce such a false merge of fast-forward parents.\n+\t\t *\n+\t\t * o----X\t\tX: the commit we are looking at;\n+\t\t * / /\t\to: a commit that touches the paths;\n+\t\t * ---o----'\n+\t\t *\n+\t\t * Further reduce the parents by removing redundant\n+\t\t * parents.\n+\t\t */\n+\t\tif (1 < cnt) {\n+\t\t\tstruct commit_list *h = reduce_heads(c->parents);\n+\t\t\tcnt = commit_list_count(h);\n+\t\t\tfree_commit_list(c->parents);\n+\t\t\tc->parents = h;\n+\t\t}\n+\n+\t\t/*\n+\t\t * A commit simplifies to itself if it is a root, if\n+\t\t * it is UNINTERESTING, if it touches the given paths,\n+\t\t * or if it is a merge and its parents simplifies to\n+\t\t * more than one commits (the first two cases are\n+\t\t * already handled at the beginning of this function).\n+\t\t *\n+\t\t * Otherwise, it simplifies to what its sole parent\n+\t\t * simplifies to.\n+\t\t */\n+\t\tif (!cnt ||\n+\t\t (c->object.flags & UNINTERESTING) ||\n+\t\t !(c->object.flags & TREESAME) ||\n+\t\t (1 < cnt))\n+\t\t\tc->util = c;\n+\t\telse\n+\t\t\tc->util = c->parents->item->util;\n+\t}\n+\tfree_commit_list(work);\n+}\n+\n static struct commit *get_revision_1(struct rev_info *revs)\n {\n \tif (!revs->commits)\n@@ -1570,8 +1662,14 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \t\tcase commit_error:\n \t\t\treturn NULL;\n \t\tdefault:\n-\t\t\treturn commit;\n+\t\t\tbreak;\n+\t\t}\n+\t\tif (revs->simplify_merges && !commit->util) {\n+\t\t\tsimplify_merges(revs, commit);\n+\t\t\tif (commit->util != commit)\n+\t\t\t\tcontinue;\n \t\t}\n+\t\treturn commit;\n \t} while (revs->commits);\n \treturn NULL;\n }\ndiff --git a/revision.h b/revision.h\nindex f64e8ce..dfa06b5 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -41,6 +41,7 @@ struct rev_info {\n \t\t\tsimplify_history:1,\n \t\t\tlifo:1,\n \t\t\ttopo_order:1,\n+\t\t\tsimplify_merges:1,\n \t\t\ttag_objects:1,\n \t\t\ttree_objects:1,\n \t\t\tblob_objects:1,\n"},{"id":"85841","messageId":"alpine.LFD.1.10.0807311513020.3277@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"7vabfxyacx.fsf_-_@gitster.siamese.dyndns.org","subject":"Re: [PATCH v3-wip] revision traversal: show full history with merge simplification","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-31T22:26:17Z","receivedAt":"2008-07-31T22:26:17Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 31 Jul 2008, Junio C Hamano wrote:\n> \n> The same query with 's/| head -n 1/>/dev/null' is more expensive. In fact\n> it is much more expensive than the non-incremental one (v2), and about\n> three times more expensive than non-limiting --full-history for explaining\n> the history of kernel/printk.c.\n\nHmm? Why is that, exactly? Does it walk over the same commit over and over \nand over again or something?\n\nCan you combine --simplify-merges and --topo-order to get a fast version \nagain (since --topo-order will force a non-incrmental walk)?\n\nI have this suspicion (gut feel only, not anything else to back it up) \nthat for any complex global history, you'll always end up having a lot of \nmerges \"live\" and have a hard time getting a lot of early output. \n\nThat may be why you get a fairly big delay before even the first commit:\n\n> $ time sh -c 'git log --pretty=oneline --abbrev-commit \\\n> --simplify-merges --parents \\\n> -- kernel/printk.c | head -n 1'\n> 5dfb66b... 1d9b9f6... c9272c4... Merge branch 'for-linus' of git://git.o-hand.com/linux-mfd\n>\n> real 0m0.344s\n> user 0m0.324s\n> sys 0m0.020s\n\n>From your previous email:\n\n $ git rev-list --parents --full-history --topo-order HEAD -- kernel/printk.c\n 3.75user 0.47system 0:04.22elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k\n\nso that's less than 10% of the whole time, but it's still a _lot_ slower \nthan the\n\n $ git rev-list --parents --full-history HEAD -- kernel/printk.c | head -n 200\n 0.16user 0.02system 0:00.18elapsed 103%CPU (0avgtext+0avgdata 0maxresident)k\n\nand that was the first 200 commits, not just the first one. I bet you got \nthe first one in about a tenth of that time - so I'm guessing 0.016s (also \nbased on my own testing - it's below 0.01s here, but I'm willing to bet my \nmachine is faster than yours is).\n\nSo getting the first one with \"--simplify-merges\" was really a _lot_ \nslower.\n\nThat said, I'm a huge beliver in the incremental approach - it just looks \nlike this is potentially \"just barely incremental\" in practice.\n\nOf course, with a more linear history than the kernel, your approach \nprobably works better.\n\n\t\t\tLinus\n"},{"id":"85843","messageId":"alpine.LFD.1.10.0807311526270.3277@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"7vd4kuzcst.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH v2] revision traversal: show full history with merge simplification","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-07-31T22:30:55Z","receivedAt":"2008-07-31T22:30:55Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 31 Jul 2008, Junio C Hamano wrote:\n>\n> If you look at the output from the \"kernel/printk.c\" with this patch, you\n> would notice that there still are somewhat meaningless merges shown in the\n> history (e.g. scroll down to 185a257f2f73bcd89050ad02da5bedbc28fc43fa).\n\nThey're not really meaningless.\n\nYes, they are pointless for the end result, but once you start showing \nthat whole pointless branch they very much are needed for a complete view \nof the \"shape\" of history. The merges are real points on that branch where \nprintk changed because it got updates from mainlines.\n\nSo either you should have the full simplification (which only shows stuff \nthat is really meaningful for the end result), or you need for those \n\"pointless\" merges to remain (because you show the changes that happened \non side branches).\n\nI obviously believe that the full simplification is what you most often \nwant, but the --post-simplify thing does make sense.\n\n(And yes, I agree that the name should be something else, and that \n--simplify-merges makes more sense. The \"post-simplify\" thing is an \nimplementation issue, and doesn't describe what the effect is. And with \nyour incremental one, even that isn't true).\n\n\t\t\tLinus\n"},{"id":"85844","messageId":"7v63qly93u.fsf@gitster.siamese.dyndns.org","threadId":"14578","inReplyTo":"alpine.LFD.1.10.0807311513020.3277@nehalem.linux-foundation.org","subject":"Re: [PATCH v3-wip] revision traversal: show full history with merge simplification","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-07-31T22:36:21Z","receivedAt":"2008-07-31T22:36:21Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Thu, 31 Jul 2008, Junio C Hamano wrote:\n>> \n>> The same query with 's/| head -n 1/>/dev/null' is more expensive. In fact\n>> it is much more expensive than the non-incremental one (v2), and about\n>> three times more expensive than non-limiting --full-history for explaining\n>> the history of kernel/printk.c.\n>\n> Hmm? Why is that, exactly? Does it walk over the same commit over and over \n> and over again or something?\n>\n> Can you combine --simplify-merges and --topo-order to get a fast version \n> again (since --topo-order will force a non-incrmental walk)?\n\nHeh, nice try to make my head explode ;-) Not today, no, really, no...\n"},{"id":"85855","messageId":"7vabfxv3px.fsf@gitster.siamese.dyndns.org","threadId":"14578","inReplyTo":"alpine.LFD.1.10.0807311513020.3277@nehalem.linux-foundation.org","subject":"Re: [PATCH v3-wip] revision traversal: show full history with merge simplification","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-08-01T03:00:58Z","receivedAt":"2008-08-01T03:00:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Thu, 31 Jul 2008, Junio C Hamano wrote:\n>> \n>> The same query with 's/| head -n 1/>/dev/null' is more expensive. In fact\n>> it is much more expensive than the non-incremental one (v2), and about\n>> three times more expensive than non-limiting --full-history for explaining\n>> the history of kernel/printk.c.\n>\n> Hmm? Why is that, exactly? Does it walk over the same commit over and over \n> and over again or something?\n\nIt was even worse than that.\n\nThe output from v3 is incorrect, as the place the new call is hooked into\nknows only that the commit in question is not UNINTERESTING, but hasn't\ninspected its parents, but the simplification logic needs to dig into the\nparent chain deep enough, which it does not do correctly using the proper\nsimplification logic (i.e. add_parents_to_list()).\n"},{"id":"85858","messageId":"alpine.LFD.1.10.0807312044240.3277@nehalem.linux-foundation.org","threadId":"14578","inReplyTo":"7vabfxv3px.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH v3-wip] revision traversal: show full history with merge simplification","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2008-08-01T03:48:18Z","receivedAt":"2008-08-01T03:48:18Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Thu, 31 Jul 2008, Junio C Hamano wrote:\n>\n> It was even worse than that.\n> \n> The output from v3 is incorrect\n\nOk. I'm really not surprised. Incrementally is really hard. I'm reminded \nof all the problems we had with just the \"trivial\" issue of just knowing \nwhen to consider something uninteresting or not, that ended up depending \non commit timestamps etc, and had problems with people having their clocks \nset incorrectly.\n\nDoing the ops once you have the full DAG is usually _trivial_ by \ncomparison. \n\n\t\tLinus\n"},{"id":"85873","messageId":"7vhca5tbqz.fsf@gitster.siamese.dyndns.org","threadId":"14578","inReplyTo":"alpine.LFD.1.10.0807312044240.3277@nehalem.linux-foundation.org","subject":"Re: [PATCH v3-wip] revision traversal: show full history with merge simplification","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-08-01T07:50:28Z","receivedAt":"2008-08-01T07:50:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Thu, 31 Jul 2008, Junio C Hamano wrote:\n>>\n>> It was even worse than that.\n>> \n>> The output from v3 is incorrect\n>\n> Ok. I'm really not surprised. Incrementally is really hard. I'm reminded \n> of all the problems we had with just the \"trivial\" issue of just knowing \n> when to consider something uninteresting or not, that ended up depending \n> on commit timestamps etc, and had problems with people having their clocks \n> set incorrectly.\n>\n> Doing the ops once you have the full DAG is usually _trivial_ by \n> comparison. \n\nSurely. I wasn't productive tonight anyway, and I'll give up for now and\nkeep the post-processing version in 'pu', perhaps queued in 'next' during\nthe 1.6.0-rc period. Perhaps somebody cleverer than me will feel itchy\nenough to make an incremental version someday ;-)\n"}]}