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>
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>
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}