user/sven/git.git/commit.c, branch v1.8.0.2

Merge branch 'jc/merge-bases-paint-fix'

2012-10-08T18:42:15Z

"git fmt-merge-msg" (an internal helper reduce_heads() it uses) had a severe performance regression; an empty "git pull" took forever to finish as the result. * jc/merge-bases-paint-fix: paint_down_to_common(): parse commit before relying on its timestamp

paint_down_to_common(): parse commit before relying on its timestamp

2012-10-04T22:49:39Z

When refactoring the merge-base computation to reduce the pairwise O(n*(n-1)) traversals to parallel O(n) traversals, the code forgot that timestamp based heuristics needs each commit to have been parsed. This caused an empty "git pull" to spend cycles, traversing the history all the way down to 0 (because an unparsed commit object has 0 timestamp, and any other commit object with positive timestamp will be processed for its parents, all getting parsed), only to come up with a merge message to be used. Signed-off-by: Junio C Hamano

commit.c: mark a file-scope private symbol as static

2012-09-16T05:58:20Z

Signed-off-by: Junio C Hamano

Merge branch 'jc/merge-bases'

2012-09-11T18:36:05Z

Optimise the "merge-base" computation a bit, and also update its users that do not need the full merge-base information to call a cheaper subset. * jc/merge-bases: reduce_heads(): reimplement on top of remove_redundant() merge-base: "--is-ancestor A B" get_merge_bases_many(): walk from many tips in parallel in_merge_bases(): use paint_down_to_common() merge_bases_many(): split out the logic to paint history in_merge_bases(): omit unnecessary redundant common ancestor reduction http-push: use in_merge_bases() for fast-forward check receive-pack: use in_merge_bases() for fast-forward check in_merge_bases(): support only one "other" commit

Merge branch 'lt/commit-tree-guess-utf-8'

2012-09-07T18:08:38Z

Teach "git commit" and "git commit-tree" the "we are told to use utf-8 in log message, but this does not look like utf-8---attempt to pass it through convert-from-latin1-to-utf8 and see if it makes sense" heuristics "git mailinfo" already uses. * lt/commit-tree-guess-utf-8: commit/commit-tree: correct latin1 to utf-8

reduce_heads(): reimplement on top of remove_redundant()

2012-08-31T18:45:36Z

This is used by "git merge" and "git merge-base --independent" but used to use a similar N*(N-1) traversals to reject commits that are ancestors of other commits. Reimplement it on top of remove_redundant(). Note that the callers of this function are allowed to pass the same commit more than once, but remove_redundant() is designed to be fed each commit only once. The function removes duplicates before calling remove_redundant(). Signed-off-by: Junio C Hamano

get_merge_bases_many(): walk from many tips in parallel

2012-08-31T00:25:57Z

The get_merge_bases_many() function reduces the result returned by the merge_bases_many() function, which is a set of possible merge bases, by excluding commits that can be reached from other commits. We used to do N*(N-1) traversals for this, but we can check if one commit reaches which other (N-1) commits by a single traversal, and repeat it for all the candidates to find the answer. Introduce remove_redundant() helper function to do this painting; we should be able to use it to reimplement reduce_heads() as well. Signed-off-by: Junio C Hamano

in_merge_bases(): use paint_down_to_common()

2012-08-31T00:25:57Z

With paint_down_to_common(), we can tell if "commit" is reachable from "reference" by simply looking at its object flag, instead of iterating over the merge bases. Signed-off-by: Junio C Hamano

merge_bases_many(): split out the logic to paint history

2012-08-31T00:25:57Z

Introduce a new helper function paint_down_to_common() that takes the same parameters as merge_bases_many(), but without the first optimization of not painting anything when "one" is one of the "twos" (or vice versa), and the last clean-up of removing the common ancestor that is known to be an ancestor of another common one. This way, the caller of the new function could tell if "one" is reachable from any of the "twos" by simply looking at the flag bits of "one". If (and only if) it is painted in PARENT2, it is reachable from one of the "twos". Signed-off-by: Junio C Hamano

in_merge_bases(): omit unnecessary redundant common ancestor reduction

2012-08-28T15:37:07Z

The function get_merge_bases() needs to postprocess the result from merge_bases_many() in order to make sure none of the commit is a true ancestor of another commit, which is expensive. However, when checking if a commit is an ancestor of another commit, we only need to see if the commit is a common ancestor between the two, and do not have to care if other common ancestors merge_bases_many() finds are true merge bases or an ancestor of another merge base. Signed-off-by: Thomas Rast Signed-off-by: Junio C Hamano