delta/git.git/combine-diff.c, branch nd/unify-ref-parse

Merge branch 'mk/show-s-no-extra-blank-line-for-merges'

2014-06-06T18:35:02+00:00

* mk/show-s-no-extra-blank-line-for-merges:
  git-show: fix 'git show -s' to not add extra terminator after merge commit

git-show: fix 'git show -s' to not add extra terminator after merge commit

2014-05-15T16:32:08+00:00

When git show -s is called for merge commit it prints extra newline
after any merge commit. This differs from output for commits with one
parent. Fix it by more thorough checking that diff output is disabled.

The code in question exists since commit 3969cf7db1. The additional
newline is really needed for cases when patch is requested, test
t4013-diff-various.sh contains cases which can demonstrate behavior when
the condition is restricted further.

Tests:

Added merge commit to 'set up a bit of history' case in t7007-show.sh to
cover the fix.

Existing tests are updated to demonstrate the new behaviour.  Earlier,
the tests that used "git show -s --pretty=format:%s", even though
"--pretty=format:%s" calls for item separator semantics and does not ask
for the terminating newline after the last item, expected the output to
end with such a newline.  They were relying on the buggy behaviour.  Use
of "--format=%s", which is equivalent to "--pretty=tformat:%s" that asks
for a terminating newline after each item, is a more realistic way to
use the command.

In the test 'merge log messages' the expected data is changed, because
it was explicitly listing the extra newline. Also the msg.nologff and
msg.nolognoff expected files are replaced by one msg.nolog, because they
were diffing because of the bug, and now there should be no difference.

Signed-off-by: Max Kirillov 
Signed-off-by: Junio C Hamano

combine-diff: speed it up, by using multiparent diff tree-walker directly

2014-04-07T21:41:49+00:00

As was recently shown in "combine-diff: optimize
combine_diff_path sets intersection", combine-diff runs very slowly. In
that commit we optimized paths sets intersection, but that accounted
only for ~ 25% of the slowness, and as my tracing showed, for linux.git
v3.10..v3.11, for merges a lot of time is spent computing
diff(commit,commit^2) just to only then intersect that huge diff to
almost small set of files from diff(commit,commit^1).

In previous commit, we described the problem in more details, and
reworked the diff tree-walker to be general one - i.e. to work in
multiple parent case too. Now is the time to take advantage of it for
finding paths for combine diff.

The implementation is straightforward - if we know, we can get generated
diff paths directly, and at present that means no diff filtering or
rename/copy detection was requested(*), we can call multiparent tree-walker
directly and get ready paths.

(*) because e.g. at present, all diffcore transformations work on
    diff_filepair queues, but in the future, that limitation can be
    lifted, if filters would operate directly on combine_diff_paths.

Timings for `git log --raw --no-abbrev --no-renames` without `-c` ("git log")
and with `-c` ("git log -c") and with `-c --merges` ("git log -c --merges")
before and after the patch are as follows:

                linux.git v3.10..v3.11

            log     log -c     log -c --merges

    before  1.9s    16.4s      15.2s
    after   1.9s     2.4s       1.1s

The result stayed the same.

Signed-off-by: Kirill Smelkov 
Signed-off-by: Junio C Hamano

combine-diff: move changed-paths scanning logic into its own function

2014-02-24T22:46:11+00:00

Move code for finding paths for which diff(commit,parent_i) is not-empty
for all parents to separate function - at present we have generic (and
slow) code for this job, which translates 1 n-parent problem to n
1-parent problems and then intersect results, and will be adding another
limited, but faster, paths scanning implementation in the next patch.

Signed-off-by: Kirill Smelkov 
Signed-off-by: Junio C Hamano

combine-diff: move show_log_first logic/action out of paths scanning

2014-02-24T22:46:11+00:00

Judging from sample outputs and tests nothing changes in diff -c output,
and this change will help later patches, when we'll be refactoring paths
scanning into its own function with several variants - the
show_log_first logic / code will stay common to all of them.

NOTE: only now we have to take care to explicitly not show anything if
    parents array is empty, as in fact there are some clients in Git code,
    which calls diff_tree_combined() in such a way.

Signed-off-by: Kirill Smelkov 
Signed-off-by: Junio C Hamano

combine-diff: simplify intersect_paths() further

2014-02-24T22:44:57+00:00

Linus once said:

    I actually wish more people understood the really core low-level
    kind of coding. Not big, complex stuff like the lockless name
    lookup, but simply good use of pointers-to-pointers etc. For
    example, I've seen too many people who delete a singly-linked
    list entry by keeping track of the "prev" entry, and then to
    delete the entry, doing something like

	if (prev)
	    prev->next = entry->next;
	else
	    list_head = entry->next;

    and whenever I see code like that, I just go "This person
    doesn't understand pointers". And it's sadly quite common.

    People who understand pointers just use a "pointer to the entry
    pointer", and initialize that with the address of the
    list_head. And then as they traverse the list, they can remove
    the entry without using any conditionals, by just doing a "*pp =
    entry->next".

Applying that simplification lets us lose 7 lines from this function
even while adding 2 lines of comment.

I was tempted to squash this into the original commit, but because
the benchmarking described in the commit log is without this
simplification, I decided to keep it a separate follow-up patch.

Signed-off-by: Junio C Hamano

combine-diff: combine_diff_path.len is not needed anymore

2014-02-24T22:44:57+00:00

The field was used in order to speed-up name comparison and also to
mark removed paths by setting it to 0.

Because the updated code does significantly less strcmp and also
just removes paths from the list and free right after we know a path
will not be needed, it is not needed anymore.

Signed-off-by: Kirill Smelkov 
Signed-off-by: Junio C Hamano

combine-diff: optimize combine_diff_path sets intersection

2014-02-24T22:44:57+00:00

When generating combined diff, for each commit, we intersect diff
paths from diff(parent_0,commit) to diff(parent_i,commit) comparing
all paths pairs, i.e. doing it the quadratic way. That is correct,
but could be optimized.

Paths come from trees in sorted (= tree) order, and so does diff_tree()
emits resulting paths in that order too. Now if we look at diffcore
transformations, all of them, except diffcore_order, preserve resulting
path ordering:

    - skip_stat_unmatch, grep, pickaxe, filter
                            -- just skip elements -> order stays preserved

    - break                 -- just breaks diff for a path, adding path
                               dup after the path -> order stays preserved

    - detect rename/copy    -- resulting paths are emitted sorted
                               (verified empirically)

So only diffcore_order changes diff paths ordering.

But diffcore_order meaning affects only presentation - i.e. only how to
show the diff, so we could do all the internal computations without
paths reordering, and order only resultant paths set. This is faster,
since, if we know two paths sets are all ordered, their intersection
could be done in linear time.

This patch does just that.

Timings for `git log --raw --no-abbrev --no-renames` without `-c` ("git log")
and with `-c` ("git log -c") before and after the patch are as follows:

                linux.git v3.10..v3.11

            log     log -c

    before  1.9s    20.4s
    after   1.9s    16.6s

                navy.git    (private repo)

            log     log -c

    before  0.83s   15.6s
    after   0.83s    2.1s

P.S.

I think linux.git case is sped up not so much as the second one, since
in navy.git, there are more exotic (subtree, etc) merges.

P.P.S.

My tracing showed that the rest of the time (16.6s vs 1.9s) is usually
spent in computing huge diffs from commit to second parent. Will try to
deal with it, if I'll have time.

P.P.P.S.

For combine_diff_path, ->len is not needed anymore - will remove it in
the next noisy cleanup path, to maintain good signal/noise ratio here.

Signed-off-by: Kirill Smelkov 
Signed-off-by: Junio C Hamano

Merge branch 'jl/submodule-mv'

2013-09-09T21:36:15+00:00

"git mv A B" when moving a submodule A does "the right thing",
inclusing relocating its working tree and adjusting the paths in
the .gitmodules file.

* jl/submodule-mv: (53 commits)
  rm: delete .gitmodules entry of submodules removed from the work tree
  mv: update the path entry in .gitmodules for moved submodules
  submodule.c: add .gitmodules staging helper functions
  mv: move submodules using a gitfile
  mv: move submodules together with their work trees
  rm: do not set a variable twice without intermediate reading.
  t6131 - skip tests if on case-insensitive file system
  parse_pathspec: accept :(icase)path syntax
  pathspec: support :(glob) syntax
  pathspec: make --literal-pathspecs disable pathspec magic
  pathspec: support :(literal) syntax for noglob pathspec
  kill limit_pathspec_to_literal() as it's only used by parse_pathspec()
  parse_pathspec: preserve prefix length via PATHSPEC_PREFIX_ORIGIN
  parse_pathspec: make sure the prefix part is wildcard-free
  rename field "raw" to "_raw" in struct pathspec
  tree-diff: remove the use of pathspec's raw[] in follow-rename codepath
  remove match_pathspec() in favor of match_pathspec_depth()
  remove init_pathspec() in favor of parse_pathspec()
  remove diff_tree_{setup,release}_paths
  convert common_prefix() to use struct pathspec
  ...

Merge branch 'tr/log-full-diff-keep-true-parents'

2013-09-09T21:33:16+00:00

Output from "git log --full-diff -- " looked strange,
because comparison was done with the previous ancestor that touched
the specified , causing the patches for paths outside the
pathspec to show more than the single commit has changed.

Tweak "git reflog -p" for the same reason using the same mechanism.

* tr/log-full-diff-keep-true-parents:
  log: use true parents for diff when walking reflogs
  log: use true parents for diff even when rewriting