blame: large-scale performance rewrite

The previous implementation used a single sorted linear list of blame
entries for organizing all partial or completed work.  Every subtask had
to scan the whole list, with most entries not being relevant to the
task.  The resulting run-time was quadratic to the number of separate
chunks.

This change gives every subtask its own data to work with.  Subtasks are
organized into "struct origin" chains hanging off particular commits.
Commits are organized into a priority queue, processing them in commit
date order in order to keep most of the work affecting a particular blob
collated even in the presence of an extensive merge history.

For large files with a diversified history, a speedup by a factor of 3
or more is not unusual.

Signed-off-by: David Kastrup <dak@gnu.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Revert "submodules: fix ambiguous absolute paths under Windows"

This reverts commit 4dce7d9b408b2935b85721b54a2010eda7ec1be9,
which was originally done to help Windows but was almost
immediately reverted in msysGit, and the codebase kept this
unnecessary divergence for almost two years.

Signed-off-by: Stepan Kasal <kasal@ucw.cz>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
blame: correctly handle files regardless of autocrlf

If a file contained CRLF line endings in a repository with
core.autocrlf=input, then blame always marked lines as "Not
Committed Yet", even if they were unmodified.  Don't attempt to
convert the line endings when creating the fake commit so that blame
works correctly regardless of the autocrlf setting.

Reported-by: Ephrim Khong <dr.khong@gmail.com>
Signed-off-by: brian m. carlson <sandals@crustytoothpaste.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
t/lib-httpd: require SANITY prereq

Our test httpd setup will not generally run as root, because
Apache will want to setuid, and we do not set up the "User"
config directive. On some systems, like current Debian
unstable, Apache fails to start, and we skip the tests:

    $ sudo ./t5539-fetch-http-shallow.sh --debug
    1..0 # SKIP web server setup failed
    $ cat trash*t5539*/httpd/error.log
    [...]
    (22)Invalid argument: AH00024: Couldn't set permissions on
      the rewrite-map mutex; check User and Group directives
    AH00016: Configuration Failed

However, on other systems (reportedly Ubuntu 11.04), Apache
seems to start, and then bails during our tests with:

   getpwuid: couldn't determine user name from uid 4294967295,
     you probably need to modify the User directive
   Child 12037 returned a Fatal error...  Apache is exiting!

This may be related to the pre-fork/threading model in use
(note that the second one complains of the child dying).
However, it's not even worth investigating; in either case
we just want to skip the tests, and we already recommend
against running the test suite as root. Let's just
explicitly check this condition and skip the tests rather
than expecting Apache to do the right thing.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
utf8.c: use a table for double_width

Refactor git_wcwidth() and replace the if-else-if chain.
Use the table double_width which is scanned by the bisearch() function,
which is already used to find combining code points.

Signed-off-by: Torsten Bögershausen <tboegi@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
utf8: make it easier to auto-update git_wcwidth()

The function git_wcwidth() returns for a given unicode code point the
width on the display:

 -1 for control characters,
  0 for combining or other non-visible code points
  1 for e.g. ASCII
  2 for double-width code points.

This table had been originally been extracted for one Unicode
version, probably 3.2.

We now use two tables these days, one for zero-width and another for
double-width.  Make it easier to update these tables to a later
version of Unicode by factoring out the table from utf8.c into
unicode_width.h and add the script update_unicode.sh to update the
table based on the latest Unicode specification files.

Thanks to Peter Krefting <peter@softwolves.pp.se> and Kevin Bracey
<kevin@bracey.fi> for helping with their Unicode knowledge.

Signed-off-by: Torsten Bögershausen <tboegi@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
index-pack: distinguish missing objects from type errors

When we fetch a pack that does not contain an object we
expected to receive, we get an error like:

  $ git init --bare tmp.git && cd tmp.git
  $ git fetch ../parent.git
  [...]
  error: Could not read 964953ec7bcc0245cb1d0db4095455edd21a2f2e
  fatal: Failed to traverse parents of commit b8247b40caf6704fe52736cdece6d6aae87471aa
  error: ../parent.git did not send all necessary objects

This comes from the check_everything_connected rev-list. If
we try cloning the same repo (rather than a fetch), we end
up using index-pack's --check-self-contained-and-connected
option instead, which produces output like:

  $ git clone --no-local --bare parent.git tmp.git
  [...]
  fatal: object of unexpected type
  fatal: index-pack failed

Not only is the sha1 missing, but it's a misleading message.
There's no type problem, but rather a missing object
problem; we don't notice the difference because we simply
compare OBJ_BAD != OBJ_BLOB.  Let's provide a different
message for this case:

  $ git clone --no-local --bare parent.git tmp.git
  fatal: did not receive expected object 6b00a8c61ed379d5f925a72c1987c9c52129d364
  fatal: index-pack failed

While we're at it, let's also improve a true type mismatch
error to look like

  fatal: object 6b00a8c61ed379d5f925a72c1987c9c52129d364: expected type blob, got tree

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
contrib/subtree: allow adding an annotated tag

cmd_add_commit() is passed FETCH_HEAD by cmd_add_repository, which
is then rev-parsed into an object name.  However, if the user is
fetching a tag rather than a branch HEAD, such as by executing:

  $ git subtree add -P oldGit https://github.com/git/git.git tags/v1.8.0

the object name refers to a tag and is never peeled, and the git
commit-tree call (line 561) slaps us in the face because it doesn't
peel tags to commits.

Because peeling a committish doesn't do anything if it's already a
commit, fix by peeling the object name before assigning it to $rev
using peel_committish() from git:git-sh-setup.sh, a pre-existing
dependency of git-subtree.

Reported-by: Kevin Cagle <kcagle@micron.com>
Helped-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: James Denholm <nod.helm@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Documentation: mention config sources for @{upstream}

The earlier documentation made vague references to "is set to build
on".  Flesh that out with references to the config settings, so folks
can use git-config(1) to get more detail on what @{upstream} means.
For example, @{upstream} does not care about remote.pushdefault or
branch.<name>.pushremote.

Signed-off-by: W. Trevor King <wking@tremily.us>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
wincred: add install target

Signed-off-by: Pat Thoyts <patthoyts@users.sourceforge.net>
Signed-off-by: Stepan Kasal <kasal@ucw.cz>
Acked-by: Erik Faye-Lund <kusmabite@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
wincred: avoid overwriting configured variables

Signed-off-by: Pat Thoyts <patthoyts@users.sourceforge.net>
Signed-off-by: Stepan Kasal <kasal@ucw.cz>
Acked-by: Erik Faye-Lund <kusmabite@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'bc/blame-crlf-test' into next

If a file contained CRLF line endings in a repository with
core.autocrlf=input, then blame always marked lines as "Not
Committed Yet", even if they were unmodified.

* bc/blame-crlf-test:
  blame: correctly handle files regardless of autocrlf
Merge branch 'sk/submodules-absolute-path-on-windows' into next

* sk/submodules-absolute-path-on-windows:
  Revert "submodules: fix ambiguous absolute paths under Windows"
Merge branch 'dk/blame-reorg' into next

* dk/blame-reorg:
  blame: large-scale performance rewrite
Merge branch 'tb/unicode-6.3-zero-width' into next

Update the logic to compute the display width needed for utf8
strings and allow us to more easily maintain the tables used in
that logic.

We may want to let the users choose if codepoints with ambiguous
widths are treated as a double or single width in a follow-up patch.

* tb/unicode-6.3-zero-width:
  utf8: make it easier to auto-update git_wcwidth()
  utf8.c: use a table for double_width
Merge branch 'jk/index-pack-report-missing' into next

* jk/index-pack-report-missing:
  index-pack: distinguish missing objects from type errors
Merge branch 'jd/subtree' into next

* jd/subtree:
  contrib/subtree: allow adding an annotated tag
Merge branch 'wk/doc-clarify-upstream' into next

* wk/doc-clarify-upstream:
  Documentation: mention config sources for @{upstream}
git-gui: use vcompare when comparing the git version

Since git 2.0.0 starting git gui in a submodule using a gitfile fails with
the following error:

   No working directory ../../../<path>

   couldn't change working directory
   to "../../../<path>": no such file or
   directory

This is because "git rev-parse --show-toplevel" is only run when git gui
sees a git version of at least 1.7.0 (which is the version in which the
--show-toplevel option was introduced). But it uses vsatisfies to check
that, which is documented to return false when the major version changes,
which is not what we want here.

Change vsatisfies to vcompare when testing for a git version to avoid the
problem when the major version changes (but still use vsatisfies in those
places where the Tk version is checked). This is done for both the place
that caused the reported bug and another spot where the git version is
tested for another feature.

Reported-by: Chris Packham <judge.packham@gmail.com>
Reported-by: Yann Dirson <ydirson@free.fr>
Signed-off-by: Jens Lehmann <Jens.Lehmann@web.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
git-show: fix 'git show -s' to not add extra terminator after merge commit

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 <max@max630.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>