Possible --remove-empty bug

$ git-rev-parse HEAD be767c91724275c4534965c0d25c452b76057602 $ git-rev-list be767c91724275c4534965c0d25c452b76057602 -- imap-send.c f2561fda364ad984ef1441a80c90b0ee04f1a7c4 $ git-rev-list --remove-empty be767c91724275c4534965c0d25c452b76057602 -- imap-send.c $

--remove-empty::
	Stop when a given path disappears from the tree.

But isn't it to be intended *after* a path disapperas from the tree? In this case I would expect to see revision f2561fda364ad984ef1441a80c90b0ee04f1a7c4 also with --remove-empty option.

BTW rev f2561fda364ad984ef1441a80c90b0ee04f1a7c4 is the 'Add git-imap-send, derived from isync 1.0.1.' patch.

Thanks Marco

"Marco Costalba" <mcostalba@gmail.com> writes:

To be honest, I do not know how --remove-empty is intended to work. What revision traversal code does and what the above says are different.

The traversal code goes like this:

	* Start from given commits (both interesting and
          uninteresting), look at still-to-be-procesed commit
          one by one, by calling add_parents_to_list().

          * add_parents_to_list() grows still-to-be-processed
            list; if the current commit is uninteresting, mark its
            parents also uninteresting, and if no interesting
            commit remains in the still-to-be-processed list, we
            are done.  On the other hand, if the current commit is
            interesting, place it to the list of results.

        * After the above traversal is done, the consumer calls
	  get_revision() to retrieve commits from the list of
	  results one-by-one.  We return only interesting ones.

And in add_parents_to_list()

	* if the commit is interesting, and when we are limiting
          by paths, we call try_to_simplify_commit().  This
          checks if the tree associated with the current commit
          is the same as one of its parents' with respect to
          specified paths, and if so pretend that the current
          commit has only that parent and no other.  This can
          make a merge commit to lose other parents that we do
          not inherit the specified paths from.

        * try_to_simplify_commit() looks at each parent, and:

          - if we find a parent that has the same tree (wrt the
            paths we are interested in), we pretend it is the
            sole parent of this commit.

	  - if we find a parent that does not have any of the
            specified paths, we pretend we do not have that
            parent under --remove-empty.

	  - otherwise we do not munge the list of parents.

My understanding of what the code is doing from the above reading is to lose that empty parent, and it does not have much to do with stop traversing the ancestry chain at such commit. I am not sure that is what was intended...

Maybe something like this is closer to what the documentation says.

-- >8 --

On Sun, 12 Mar 2006, Junio C Hamano wrote:

It's supposed to stop traversing the tree once a pathname disappears.

If it is, then the documentation is broken.

The fact that a pathname disappears does _not_ make the commit uninteresting. It just means that we should stop traversing that parent.

"uninteresting" has a big side effect: it inherits to parents. So if you have

	    a
	   / \
	  b   c
	   \ /
	    d

where the pathname disappeared in "b", you must NOT mark it uninteresting, because that would mean that "d" is also uninteresting.

There's a huge difference between saying "I will not traverse down this line any more" and "I mark this commit uninteresting". The first one just stops adding commits to the commit list (but parents deeper down might still be interesting because they are also reached through another pathway). The second says "this commit and all of its ancestors are deemed worthless".

The "path goes away" case is meant to just stop traversal, not mark all parents worthless.

		Linus

Linus Torvalds <torvalds@osdl.org> writes:

Then what we should simplify is the parent commit that does not have those pathnames (i.e. remove parents from that parent commit). In other words, currently the code removes the parent commit that makes the tree disappear, but we would want to keep that parent, remove the grandparents, and then mark the parent uninteresting.

-- >8 -- [PATCH] revision traversal: --remove-empty fix (take #2).

Marco Costalba reports that --remove-empty omits the commit that created paths we are interested in. try_to_simplify_commit() logic was dropping a parent we introduced those paths against, which I think is not what we meant. Instead, this makes such parent parentless.

Signed-off-by: Junio C Hamano <junkio@cox.net>

---

Junio C Hamano <junkio@cox.net> writes:

Sorry, the last clause in the above comment is wrong, and does not describe what the code attached does.

It removes the grandparents from the parent, and leaves the parent still interesting. As a result, in your example:

    ... if you have

                a
               / \
              b   c
               \ /
                d

    where the pathname disappeared in "b"...

we would get this world view:

                a
               / \
              b   c
                 /
                d

because when inspecting a and finding that "b" does not have any paths we are interested in, b loses all of its parents.

On Sun, 12 Mar 2006, Junio C Hamano wrote:

Yeah, that's correct. That way you still see all the history that is relevant to the tree that became empty.

However, to be honest, the only reason to ever use --remove-empty is for rename detection, and Frederik's approach of doing that through the library interface directly is actually a much superior option. So we might as well drop the compilcation of --remove-empty entirely, unless somebody has already started using it.

The _real_ optimization would be to make the pathname based pruning be done incrementally instead of having to build up the whole tree. That would be much more important than the --remove-empty stuff from a usability standpoint. I'm absolutely sure it's possible, and I simplified the code earlier so that it should be simpler to do, but every time I actually look at the code I get confused again.

		Linus

On 3/13/06, Linus Torvalds <torvalds@osdl.org> wrote:

In case of a rather recent file --remove-empty option gives a good speed up in history loading with git-rev-list. So qgit uses that option.

Annotation in qgit it is little different from blame algorithm because it works from oldest revision to latest instead of the contrary. This is due because it calculates in one pass _all_ the annotations of all the different revisions of a given file, starting from file history, i.e. 'git-rev-list file_path' output.

The GUI interface of qgit let's the user quickly jump between two file revisions. So the corresponding annotations should be already prepared to make it snappy.

Anything that speeds-up file git-rev-list history loading surely gives a big boost to all annotation/blame stuff. I have made some profiling on qgit (the public git repo version that is much faster, not the qgit1.1 released one) and I found that 50% to 70% of the time is spent on git-rev-list, of the remaining the 80% is spent on git-diff-tree -p patch loading and only a small amount is spent on actually calculate the annotation.

Of course these numbers can vary a little according to file/repo, but the big picture stays the same.

Marco

"Marco Costalba" <mcostalba@gmail.com> writes:

So you _do_ use it, and I think I still have that remove-empty stuff held back in "next" branch. Should I unleash it?

On 3/18/06, Junio C Hamano <junkio@cox.net> wrote:

Yes please.