{"thread":{"id":"3636","subject":"Possible --remove-empty bug","startedAt":"2006-03-12T14:12:12Z","lastAt":"2006-03-18T07:36:44Z","messageCount":9,"participants":["Marco Costalba","Junio C Hamano","Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"17470","messageId":"e5bfff550603120612k555fc7f3v9d8d17b1bd0b9e41@mail.gmail.com","threadId":"3636","inReplyTo":null,"subject":"Possible --remove-empty bug","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2006-03-12T14:12:12Z","receivedAt":"2006-03-12T14:12:12Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":">From today git:\n\n$ git-rev-parse HEAD\nbe767c91724275c4534965c0d25c452b76057602\n$ git-rev-list be767c91724275c4534965c0d25c452b76057602 -- imap-send.c\nf2561fda364ad984ef1441a80c90b0ee04f1a7c4\n$ git-rev-list --remove-empty be767c91724275c4534965c0d25c452b76057602\n-- imap-send.c\n$\n\n>From git-rev-list documentation:\n\n--remove-empty::\n\tStop when a given path disappears from the tree.\n\nBut isn't it to be intended *after* a path disapperas from the tree?\nIn this case I would expect to see revision\nf2561fda364ad984ef1441a80c90b0ee04f1a7c4 also with --remove-empty\noption.\n\nBTW rev f2561fda364ad984ef1441a80c90b0ee04f1a7c4 is the 'Add\ngit-imap-send, derived from isync 1.0.1.' patch.\n\nThanks\nMarco\n"},{"id":"17482","messageId":"7vk6azz6xx.fsf@assigned-by-dhcp.cox.net","threadId":"3636","inReplyTo":"e5bfff550603120612k555fc7f3v9d8d17b1bd0b9e41@mail.gmail.com","subject":"Re: Possible --remove-empty bug","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-12T21:31:06Z","receivedAt":"2006-03-12T21:31:06Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Marco Costalba\" writes:\n\n>>>From git-rev-list documentation:\n>\n> --remove-empty::\n> \tStop when a given path disappears from the tree.\n>\n> But isn't it to be intended *after* a path disapperas from the tree?\n\nTo be honest, I do not know how --remove-empty is intended to\nwork. What revision traversal code does and what the above says\nare different.\n\nThe traversal code goes like this:\n\n\t* Start from given commits (both interesting and\n uninteresting), look at still-to-be-procesed commit\n one by one, by calling add_parents_to_list().\n\n * add_parents_to_list() grows still-to-be-processed\n list; if the current commit is uninteresting, mark its\n parents also uninteresting, and if no interesting\n commit remains in the still-to-be-processed list, we\n are done. On the other hand, if the current commit is\n interesting, place it to the list of results.\n\n * After the above traversal is done, the consumer calls\n\t get_revision() to retrieve commits from the list of\n\t results one-by-one. We return only interesting ones.\n\nAnd in add_parents_to_list()\n\n\t* if the commit is interesting, and when we are limiting\n by paths, we call try_to_simplify_commit(). This\n checks if the tree associated with the current commit\n is the same as one of its parents' with respect to\n specified paths, and if so pretend that the current\n commit has only that parent and no other. This can\n make a merge commit to lose other parents that we do\n not inherit the specified paths from.\n\n * try_to_simplify_commit() looks at each parent, and:\n\n - if we find a parent that has the same tree (wrt the\n paths we are interested in), we pretend it is the\n sole parent of this commit.\n\n\t - if we find a parent that does not have any of the\n specified paths, we pretend we do not have that\n parent under --remove-empty.\n\n\t - otherwise we do not munge the list of parents.\n\nMy understanding of what the code is doing from the above\nreading is to lose that empty parent, and it does not have much\nto do with stop traversing the ancestry chain at such commit. I\nam not sure that is what was intended...\n\nMaybe something like this is closer to what the documentation\nsays.\n\n-- >8 --\ndiff --git a/revision.c b/revision.c\nindex c8d93ff..03085ff 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -315,9 +315,14 @@ static void try_to_simplify_commit(struc\n \t\t\treturn;\n \n \t\tcase TREE_NEW:\n-\t\t\tif (revs->remove_empty_trees && same_tree_as_empty(p->tree)) {\n-\t\t\t\t*pp = parent->next;\n-\t\t\t\tcontinue;\n+\t\t\tif (revs->remove_empty_trees &&\n+\t\t\t same_tree_as_empty(p->tree)) {\n+\t\t\t\t/* We are adding all the specified paths from\n+\t\t\t\t * this parent, so the parents of it is\n+\t\t\t\t * not interesting, but the difference between\n+\t\t\t\t * this parent and us still is interesting.\n+\t\t\t\t */\n+\t\t\t\tp->object.flags |= UNINTERESTING;\n \t\t\t}\n \t\t/* fallthrough */\n \t\tcase TREE_DIFFERENT:\n"},{"id":"17483","messageId":"Pine.LNX.4.64.0603121450210.3618@g5.osdl.org","threadId":"3636","inReplyTo":"7vk6azz6xx.fsf@assigned-by-dhcp.cox.net","subject":"Re: Possible --remove-empty bug","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-12T22:54:13Z","receivedAt":"2006-03-12T22:54:13Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 12 Mar 2006, Junio C Hamano wrote:\n> \n> To be honest, I do not know how --remove-empty is intended to\n> work.\n\nIt's supposed to stop traversing the tree once a pathname disappears.\n\n> Maybe something like this is closer to what the documentation\n> says.\n\nIf it is, then the documentation is broken.\n\nThe fact that a pathname disappears does _not_ make the commit \nuninteresting. It just means that we should stop traversing that parent.\n\n\"uninteresting\" has a big side effect: it inherits to parents. So if you \nhave\n\n\t a\n\t / \\\n\t b c\n\t \\ /\n\t d\n\nwhere the pathname disappeared in \"b\", you must NOT mark it uninteresting, \nbecause that would mean that \"d\" is also uninteresting.\n\nThere's a huge difference between saying \"I will not traverse down this \nline any more\" and \"I mark this commit uninteresting\". The first one just \nstops adding commits to the commit list (but parents deeper down might \nstill be interesting because they are also reached through another \npathway). The second says \"this commit and all of its ancestors are \ndeemed worthless\".\n\nThe \"path goes away\" case is meant to just stop traversal, not mark all \nparents worthless.\n\n\t\tLinus\n"},{"id":"17486","messageId":"7vlkvfw3px.fsf@assigned-by-dhcp.cox.net","threadId":"3636","inReplyTo":"Pine.LNX.4.64.0603121450210.3618@g5.osdl.org","subject":"Re: Possible --remove-empty bug","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-13T01:08:58Z","receivedAt":"2006-03-13T01:08:58Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> On Sun, 12 Mar 2006, Junio C Hamano wrote:\n>> \n>> To be honest, I do not know how --remove-empty is intended to\n>> work.\n>\n> It's supposed to stop traversing the tree once a pathname disappears.\n\nThen what we should simplify is the parent commit that does not\nhave those pathnames (i.e. remove parents from that parent\ncommit). In other words, currently the code removes the parent\ncommit that makes the tree disappear, but we would want to keep\nthat parent, remove the grandparents, and then mark the parent\nuninteresting.\n\n-- >8 --\n[PATCH] revision traversal: --remove-empty fix (take #2).\n\nMarco Costalba reports that --remove-empty omits the commit that\ncreated paths we are interested in. try_to_simplify_commit()\nlogic was dropping a parent we introduced those paths against,\nwhich I think is not what we meant. Instead, this makes such\nparent parentless.\n\nSigned-off-by: Junio C Hamano \n\n---\n\ndiff --git a/revision.c b/revision.c\nindex c8d93ff..73fba5d 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -315,9 +315,18 @@ static void try_to_simplify_commit(struc\n \t\t\treturn;\n \n \t\tcase TREE_NEW:\n-\t\t\tif (revs->remove_empty_trees && same_tree_as_empty(p->tree)) {\n-\t\t\t\t*pp = parent->next;\n-\t\t\t\tcontinue;\n+\t\t\tif (revs->remove_empty_trees &&\n+\t\t\t same_tree_as_empty(p->tree)) {\n+\t\t\t\t/* We are adding all the specified\n+\t\t\t\t * paths from this parent, so the\n+\t\t\t\t * history beyond this parent is not\n+\t\t\t\t * interesting. Remove its parents\n+\t\t\t\t * (they are grandparents for us).\n+\t\t\t\t * IOW, we pretend this parent is a\n+\t\t\t\t * \"root\" commit.\n+\t\t\t\t */\n+\t\t\t\tparse_commit(p);\n+\t\t\t\tp->parents = NULL;\n \t\t\t}\n \t\t/* fallthrough */\n \t\tcase TREE_DIFFERENT:\n"},{"id":"17506","messageId":"7v4q22ucio.fsf@assigned-by-dhcp.cox.net","threadId":"3636","inReplyTo":"7vlkvfw3px.fsf@assigned-by-dhcp.cox.net","subject":"Re: Possible --remove-empty bug","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-13T05:41:51Z","receivedAt":"2006-03-13T05:41:51Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Linus Torvalds writes:\n>\n>> It's supposed to stop traversing the tree once a pathname disappears.\n>\n> Then what we should simplify is the parent commit that does not\n> have those pathnames (i.e. remove parents from that parent\n> commit). In other words, currently the code removes the parent\n> commit that makes the tree disappear, but we would want to keep\n> that parent, remove the grandparents, and then mark the parent\n> uninteresting.\n\nSorry, the last clause in the above comment is wrong, and does\nnot describe what the code attached does.\n\nIt removes the grandparents from the parent, and leaves the\nparent still interesting. As a result, in your example:\n\n ... if you have\n\n a\n / \\\n b c\n \\ /\n d\n\n where the pathname disappeared in \"b\"...\n\nwe would get this world view:\n\n a\n / \\\n b c\n /\n d\n\nbecause when inspecting a and finding that \"b\" does not have any\npaths we are interested in, b loses all of its parents.\n"},{"id":"17530","messageId":"Pine.LNX.4.64.0603131058270.3618@g5.osdl.org","threadId":"3636","inReplyTo":"7v4q22ucio.fsf@assigned-by-dhcp.cox.net","subject":"Re: Possible --remove-empty bug","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-03-13T19:03:32Z","receivedAt":"2006-03-13T19:03:32Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 12 Mar 2006, Junio C Hamano wrote:\n> \n> It removes the grandparents from the parent, and leaves the\n> parent still interesting. As a result, in your example:\n> \n> ... if you have\n> \n> a\n> / \\\n> b c\n> \\ /\n> d\n> \n> where the pathname disappeared in \"b\"...\n> \n> we would get this world view:\n> \n> a\n> / \\\n> b c\n> /\n> d\n\nYeah, that's correct. That way you still see all the history that is \nrelevant to the tree that became empty.\n\nHowever, to be honest, the only reason to ever use --remove-empty is for \nrename detection, and Frederik's approach of doing that through the \nlibrary interface directly is actually a much superior option. So we might \nas well drop the compilcation of --remove-empty entirely, unless somebody \nhas already started using it.\n\nThe _real_ optimization would be to make the pathname based pruning be \ndone incrementally instead of having to build up the whole tree. That \nwould be much more important than the --remove-empty stuff from a \nusability standpoint. I'm absolutely sure it's possible, and I simplified \nthe code earlier so that it should be simpler to do, but every time I \nactually look at the code I get confused again.\n\n\t\tLinus\n"},{"id":"17619","messageId":"e5bfff550603170257u21ee6583jabe5a6409cc40766@mail.gmail.com","threadId":"3636","inReplyTo":"Pine.LNX.4.64.0603131058270.3618@g5.osdl.org","subject":"Re: Possible --remove-empty bug","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2006-03-17T10:57:38Z","receivedAt":"2006-03-17T10:57:38Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 3/13/06, Linus Torvalds wrote:\n>\n> However, to be honest, the only reason to ever use --remove-empty is for\n> rename detection, and Frederik's approach of doing that through the\n> library interface directly is actually a much superior option. So we might\n> as well drop the compilcation of --remove-empty entirely, unless somebody\n> has already started using it.\n>\n\nIn case of a rather recent file --remove-empty option gives a good\nspeed up in history loading with git-rev-list. So qgit uses that\noption.\n\nAnnotation in qgit it is little different from blame algorithm because\nit works from oldest revision to latest instead of the contrary. This\nis due because it calculates in one pass _all_ the annotations of all\nthe different revisions of a given file, starting from file history,\ni.e. 'git-rev-list file_path' output.\n\nThe GUI interface of qgit let's the user quickly jump between two file\nrevisions. So the corresponding annotations should be already prepared\nto make it snappy.\n\n\n> The _real_ optimization would be to make the pathname based pruning be\n> done incrementally instead of having to build up the whole tree.\n\nAnything that speeds-up file git-rev-list history loading surely gives\na big boost to all annotation/blame stuff. I have made some profiling\non qgit (the public git repo version that is much faster, not the\nqgit1.1 released one) and I found that 50% to 70% of the time is spent\non git-rev-list, of the remaining the 80% is spent on git-diff-tree -p\npatch loading and only a small amount is spent on actually calculate\nthe annotation.\n\nOf course these numbers can vary a little according to file/repo, but\nthe big picture stays the same.\n\n\nMarco\n"},{"id":"17639","messageId":"7vbqw4z25v.fsf@assigned-by-dhcp.cox.net","threadId":"3636","inReplyTo":"e5bfff550603170257u21ee6583jabe5a6409cc40766@mail.gmail.com","subject":"Re: Possible --remove-empty bug","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-03-18T06:40:12Z","receivedAt":"2006-03-18T06:40:12Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Marco Costalba\" writes:\n\n> On 3/13/06, Linus Torvalds wrote:\n>>\n>> However, to be honest, the only reason to ever use --remove-empty is for\n>> rename detection, and Frederik's approach of doing that through the\n>> library interface directly is actually a much superior option. So we might\n>> as well drop the compilcation of --remove-empty entirely, unless somebody\n>> has already started using it.\n>\n> In case of a rather recent file --remove-empty option gives a good\n> speed up in history loading with git-rev-list. So qgit uses that\n> option.\n\nSo you _do_ use it, and I think I still have that remove-empty\nstuff held back in \"next\" branch. Should I unleash it?\n"},{"id":"17643","messageId":"e5bfff550603172336s58156db7wb547817c74ceb456@mail.gmail.com","threadId":"3636","inReplyTo":"7vbqw4z25v.fsf@assigned-by-dhcp.cox.net","subject":"Re: Possible --remove-empty bug","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2006-03-18T07:36:44Z","receivedAt":"2006-03-18T07:36:44Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 3/18/06, Junio C Hamano wrote:\n> \"Marco Costalba\" writes:\n>\n> >\n> > In case of a rather recent file --remove-empty option gives a good\n> > speed up in history loading with git-rev-list. So qgit uses that\n> > option.\n>\n> So you _do_ use it, and I think I still have that remove-empty\n> stuff held back in \"next\" branch. Should I unleash it?\n>\n>\n\nYes please.\n"}]}