Add delta-islands.{c,h}

Hosting providers that allow users to "fork" existing
repos want those forks to share as much disk space as
possible.

Alternates are an existing solution to keep all the
objects from all the forks into a unique central repo,
but this can have some drawbacks. Especially when
packing the central repo, deltas will be created
between objects from different forks.

This can make cloning or fetching a fork much slower
and much more CPU intensive as Git might have to
compute new deltas for many objects to avoid sending
objects from a different fork.

Because the inefficiency primarily arises when an
object is deltified against another object that does
not exist in the same fork, we partition objects into
sets that appear in the same fork, and define
"delta islands". When finding delta base, we do not
allow an object outside the same island to be
considered as its base.

So "delta islands" is a way to store objects from
different forks in the same repo and packfile without
having deltas between objects from different forks.

This patch implements the delta islands mechanism in
"delta-islands.{c,h}", but does not yet make use of it.

A few new fields are added in 'struct object_entry'
in "pack-objects.h" though.

The documentation will follow in a patch that actually
uses delta islands in "builtin/pack-objects.c".

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

Fifth batch for 2.19 cycle

Signed-off-by: Junio C Hamano <gitster@pobox.com>

Merge branch 'jt/commit-graph-per-object-store'

The singleton commit-graph in-core instance is made per in-core
repository instance.

* jt/commit-graph-per-object-store:
  commit-graph: add repo arg to graph readers
  commit-graph: store graph in struct object_store
  commit-graph: add free_commit_graph
  commit-graph: add missing forward declaration
  object-store: add missing include
  commit-graph: refactor preparing commit graph

Merge branch 'es/chain-lint-in-subshell'

Look for broken "&&" chains that are hidden in subshell, many of
which have been found and corrected.

* es/chain-lint-in-subshell:
  t/chainlint.sed: drop extra spaces from regex character class
  t/chainlint: add chainlint "specialized" test cases
  t/chainlint: add chainlint "complex" test cases
  t/chainlint: add chainlint "cuddled" test cases
  t/chainlint: add chainlint "loop" and "conditional" test cases
  t/chainlint: add chainlint "nested subshell" test cases
  t/chainlint: add chainlint "one-liner" test cases
  t/chainlint: add chainlint "whitespace" test cases
  t/chainlint: add chainlint "basic" test cases
  t/Makefile: add machinery to check correctness of chainlint.sed
  t/test-lib: teach --chain-lint to detect broken &&-chains in subshells

Merge branch 'jt/tags-to-promised-blobs-fix'

The lazy clone support had a few places where missing but promised
objects were not correctly tolerated, which have been fixed.

* jt/tags-to-promised-blobs-fix:
  tag: don't warn if target is missing but promised
  revision: tolerate promised targets of tags

Merge branch 'jt/fetch-negotiator-skipping'

Add a server-side knob to skip commits in exponential/fibbonacci
stride in an attempt to cover wider swath of history with a smaller
number of iterations, potentially accepting a larger packfile
transfer, instead of going back one commit a time during common
ancestor discovery during the "git fetch" transaction.

* jt/fetch-negotiator-skipping:
  negotiator/skipping: skip commits during fetch

Merge branch 'jm/send-email-tls-auth-on-batch'

"git send-email" when using in a batched mode that limits the
number of messages sent in a single SMTP session lost the contents
of the variable used to choose between tls/ssl, unable to send the
second and later batches, which has been fixed.

* jm/send-email-tls-auth-on-batch:
  send-email: fix tls AUTH when sending batch

Merge branch 'bc/sequencer-export-work-tree-as-well'

"git rebase" started exporting GIT_DIR environment variable and
exposing it to hook scripts when part of it got rewritten in C.
Instead of matching the old scripted Porcelains' behaviour,
compensate by also exporting GIT_WORK_TREE environment as well to
lessen the damage.  This can harm existing hooks that want to
operate on different repository, but the current behaviour is
already broken for them anyway.

* bc/sequencer-export-work-tree-as-well:
  sequencer: pass absolute GIT_WORK_TREE to exec commands

Merge branch 'en/t7405-recursive-submodule-conflicts'

Tests to cover conflict cases that involve submodules have been
added for merge-recursive.

* en/t7405-recursive-submodule-conflicts:
  t7405: verify 'merge --abort' works after submodule/path conflicts
  t7405: add a directory/submodule conflict
  t7405: add a file/submodule conflict

Merge branch 'en/t6036-merge-recursive-tests'

Tests to cover various conflicting cases have been added for
merge-recursive.

* en/t6036-merge-recursive-tests:
  t6036: add a failed conflict detection case: regular files, different modes
  t6036: add a failed conflict detection case with conflicting types
  t6036: add a failed conflict detection case with submodule add/add
  t6036: add a failed conflict detection case with submodule modify/modify
  t6036: add a failed conflict detection case with symlink add/add
  t6036: add a failed conflict detection case with symlink modify/modify

Merge branch 'en/dirty-merge-fixes'

The recursive merge strategy did not properly ensure there was no
change between HEAD and the index before performing its operation,
which has been corrected.

* en/dirty-merge-fixes:
  merge: fix misleading pre-merge check documentation
  merge-recursive: enforce rule that index matches head before merging
  t6044: add more testcases with staged changes before a merge is invoked
  merge-recursive: fix assumption that head tree being merged is HEAD
  merge-recursive: make sure when we say we abort that we actually abort
  t6044: add a testcase for index matching head, when head doesn't match HEAD
  t6044: verify that merges expected to abort actually abort
  index_has_changes(): avoid assuming operating on the_index
  read-cache.c: move index_has_changes() from merge.c

Merge branch 'js/rebase-merge-octopus'

"git rebase --rebase-merges" mode now handles octopus merges as
well.

* js/rebase-merge-octopus:
  rebase --rebase-merges: adjust man page for octopus support
  rebase --rebase-merges: add support for octopus merges
  merge: allow reading the merge commit message from a file

Merge branch 'tb/grep-only-matching'

"git grep" learned the "--only-matching" option.

* tb/grep-only-matching:
  grep.c: teach 'git grep --only-matching'
  grep.c: extract show_line_header()

Merge branch 'kg/gc-auto-windows-workaround'

"git gc --auto" opens file descriptors for the packfiles before
spawning "git repack/prune", which would upset Windows that does
not want a process to work on a file that is open by another
process.  The issue has been worked around.

* kg/gc-auto-windows-workaround:
  gc --auto: release pack files before auto packing

Merge branch 'jm/cache-entry-from-mem-pool'

For a large tree, the index needs to hold many cache entries
allocated on heap.  These cache entries are now allocated out of a
dedicated memory pool to amortize malloc(3) overhead.

* jm/cache-entry-from-mem-pool:
  block alloc: add validations around cache_entry lifecyle
  block alloc: allocate cache entries from mem_pool
  mem-pool: fill out functionality
  mem-pool: add life cycle management functions
  mem-pool: only search head block for available space
  block alloc: add lifecycle APIs for cache_entry structs
  read-cache: teach make_cache_entry to take object_id
  read-cache: teach refresh_cache_entry to take istate

Merge branch 'jt/fetch-nego-tip'

"git fetch" learned a new option "--negotiation-tip" to limit the
set of commits it tells the other end as "have", to reduce wasted
bandwidth and cycles, which would be helpful when the receiving
repository has a lot of refs that have little to do with the
history at the remote it is fetching from.

* jt/fetch-nego-tip:
  fetch-pack: support negotiation tip whitelist

Merge branch 'en/t6042-insane-merge-rename-testcases'

Various glitches in the heuristics of merge-recursive strategy have
been documented in new tests.

* en/t6042-insane-merge-rename-testcases:
  t6042: add testcase covering long chains of rename conflicts
  t6042: add testcase covering rename/rename(2to1)/delete/delete conflict
  t6042: add testcase covering rename/add/delete conflict type

Merge branch 'sb/object-store-lookup'

lookup_commit_reference() and friends have been updated to find
in-core object for a specific in-core repository instance.

* sb/object-store-lookup: (32 commits)
  commit.c: allow lookup_commit_reference to handle arbitrary repositories
  commit.c: allow lookup_commit_reference_gently to handle arbitrary repositories
  tag.c: allow deref_tag to handle arbitrary repositories
  object.c: allow parse_object to handle arbitrary repositories
  object.c: allow parse_object_buffer to handle arbitrary repositories
  commit.c: allow get_cached_commit_buffer to handle arbitrary repositories
  commit.c: allow set_commit_buffer to handle arbitrary repositories
  commit.c: migrate the commit buffer to the parsed object store
  commit-slabs: remove realloc counter outside of slab struct
  commit.c: allow parse_commit_buffer to handle arbitrary repositories
  tag: allow parse_tag_buffer to handle arbitrary repositories
  tag: allow lookup_tag to handle arbitrary repositories
  commit: allow lookup_commit to handle arbitrary repositories
  tree: allow lookup_tree to handle arbitrary repositories
  blob: allow lookup_blob to handle arbitrary repositories
  object: allow lookup_object to handle arbitrary repositories
  object: allow object_as_type to handle arbitrary repositories
  tag: add repository argument to deref_tag
  tag: add repository argument to parse_tag_buffer
  tag: add repository argument to lookup_tag
  ...

Merge branch 'is/parsing-line-range'

Parsing of -L[<N>][,[<M>]] parameters "git blame" and "git log"
take has been tweaked.

* is/parsing-line-range:
  log: prevent error if line range ends past end of file
  blame: prevent error if range ends past end of file

Merge branch 'jt/fetch-pack-negotiator'

Code restructuring and a small fix to transport protocol v2 during
fetching.

* jt/fetch-pack-negotiator:
  fetch-pack: introduce negotiator API
  fetch-pack: move common check and marking together
  fetch-pack: make negotiation-related vars local
  fetch-pack: use ref adv. to prune "have" sent
  fetch-pack: directly end negotiation if ACK ready
  fetch-pack: clear marks before re-marking
  fetch-pack: split up everything_local()

Merge branch 'ab/checkout-default-remote'

"git checkout" and "git worktree add" learned to honor
checkout.defaultRemote when auto-vivifying a local branch out of a
remote tracking branch in a repository with multiple remotes that
have tracking branches that share the same names.

* ab/checkout-default-remote:
  checkout & worktree: introduce checkout.defaultRemote
  checkout: add advice for ambiguous "checkout <branch>"
  builtin/checkout.c: use "ret" variable for return
  checkout: pass the "num_matches" up to callers
  checkout.c: change "unique" member to "num_matches"
  checkout.c: introduce an *_INIT macro
  checkout.h: wrap the arguments to unique_tracking_name()
  checkout tests: index should be clean after dwim checkout

Merge branch 'sb/diff-color-move-more'

"git diff --color-moved" feature has further been tweaked.

* sb/diff-color-move-more:
  diff.c: offer config option to control ws handling in move detection
  diff.c: add white space mode to move detection that allows indent changes
  diff.c: factor advance_or_nullify out of mark_color_as_moved
  diff.c: decouple white space treatment from move detection algorithm
  diff.c: add a blocks mode for moved code detection
  diff.c: adjust hash function signature to match hashmap expectation
  diff.c: do not pass diff options as keydata to hashmap
  t4015: avoid git as a pipe input
  xdiff/xdiffi.c: remove unneeded function declarations
  xdiff/xdiff.h: remove unused flags

Merge branch 'es/test-fixes'

Test clean-up and corrections.

* es/test-fixes: (26 commits)
  t5608: fix broken &&-chain
  t9119: fix broken &&-chains
  t9000-t9999: fix broken &&-chains
  t7000-t7999: fix broken &&-chains
  t6000-t6999: fix broken &&-chains
  t5000-t5999: fix broken &&-chains
  t4000-t4999: fix broken &&-chains
  t3030: fix broken &&-chains
  t3000-t3999: fix broken &&-chains
  t2000-t2999: fix broken &&-chains
  t1000-t1999: fix broken &&-chains
  t0000-t0999: fix broken &&-chains
  t9814: simplify convoluted check that command correctly errors out
  t9001: fix broken "invoke hook" test
  t7810: use test_expect_code() instead of hand-rolled comparison
  t7400: fix broken "submodule add/reconfigure --force" test
  t7201: drop pointless "exit 0" at end of subshell
  t6036: fix broken "merge fails but has appropriate contents" tests
  t5505: modernize and simplify hard-to-digest test
  t5406: use write_script() instead of birthing shell script manually
  ...

Merge branch 'ds/commit-graph-fsck'

"git fsck" learns to make sure the optional commit-graph file is in
a sane state.

* ds/commit-graph-fsck: (23 commits)
  coccinelle: update commit.cocci
  commit-graph: update design document
  gc: automatically write commit-graph files
  commit-graph: add '--reachable' option
  commit-graph: use string-list API for input
  fsck: verify commit-graph
  commit-graph: verify contents match checksum
  commit-graph: test for corrupted octopus edge
  commit-graph: verify commit date
  commit-graph: verify generation number
  commit-graph: verify parent list
  commit-graph: verify root tree OIDs
  commit-graph: verify objects exist
  commit-graph: verify corrupt OID fanout and lookup
  commit-graph: verify required chunks are present
  commit-graph: verify catches corrupt signature
  commit-graph: add 'verify' subcommand
  commit-graph: load a root tree from specific graph
  commit: force commit to parse from object database
  commit-graph: parse commit from chosen graph
  ...

Merge branch 'jk/fsck-gitmodules-gently'

Recent "security fix" to pay attention to contents of ".gitmodules"
while accepting "git push" was a bit overly strict than necessary,
which has been adjusted.

* jk/fsck-gitmodules-gently:
  fsck: downgrade gitmodulesParse default to "info"
  fsck: split ".gitmodules too large" error from parse failure
  fsck: silence stderr when parsing .gitmodules
  config: add options parameter to git_config_from_mem
  config: add CONFIG_ERROR_SILENT handler
  config: turn die_on_error into caller-facing enum

Merge branch 'bc/object-id'

Conversion from uchar[40] to struct object_id continues.

* bc/object-id:
  pretty: switch hard-coded constants to the_hash_algo
  sha1-file: convert constants to uses of the_hash_algo
  log-tree: switch GIT_SHA1_HEXSZ to the_hash_algo->hexsz
  diff: switch GIT_SHA1_HEXSZ to use the_hash_algo
  builtin/merge-recursive: make hash independent
  builtin/merge: switch to use the_hash_algo
  builtin/fmt-merge-msg: make hash independent
  builtin/update-index: simplify parsing of cacheinfo
  builtin/update-index: convert to using the_hash_algo
  refs/files-backend: use the_hash_algo for writing refs
  sha1-name: use the_hash_algo when parsing object names
  strbuf: allocate space with GIT_MAX_HEXSZ
  commit: express tree entry constants in terms of the_hash_algo
  hex: switch to using the_hash_algo
  tree-walk: replace hard-coded constants with the_hash_algo
  cache: update object ID functions for the_hash_algo

Merge branch 'en/t6036-recursive-corner-cases'

Tests to cover more D/F conflict cases have been added for
merge-recursive.

* en/t6036-recursive-corner-cases:
  t6036: fix broken && chain in sub-shell
  t6036: add lots of detail for directory/file conflicts in recursive case

Merge branch 'sg/httpd-test-unflake'

httpd tests saw occasional breakage due to the way its access log
gets inspected by the tests, which has been updated to make them
less flaky.

* sg/httpd-test-unflake:
  t/lib-httpd: avoid occasional failures when checking access.log
  t/lib-httpd: add the strip_access_log() helper function
  t5541: clean up truncating access log

Merge branch 'bp/test-drop-caches-for-windows'

A test helper update for Windows.

* bp/test-drop-caches-for-windows:
  handle lower case drive letters on Windows

Merge branch 'jk/has-uncommitted-changes-fix'

"git pull --rebase" on a corrupt HEAD caused a segfault.  In
general we substitute an empty tree object when running the in-core
equivalent of the diff-index command, and the codepath has been
corrected to do so as well to fix this issue.

* jk/has-uncommitted-changes-fix:
  has_uncommitted_changes(): fall back to empty tree

t/chainlint.sed: drop extra spaces from regex character class

This character class, like many others in this script, matches
horizontal whitespace consisting of spaces and tabs, however, a few
extra, entirely harmless, spaces somehow slipped into the expression.
Removing them is purely a cosmetic fix.

While at it, re-indent three lines with a single TAB each which were
incorrectly indented with six spaces. Also, a purely cosmetic fix.

Signed-off-by: Eric Sunshine <sunshine@sunshineco.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

Fourth batch for 2.19 cycle

Signed-off-by: Junio C Hamano <gitster@pobox.com>

Merge branch 'as/sequencer-customizable-comment-char'

Honor core.commentchar when preparing the list of commits to replay
in "rebase -i".

* as/sequencer-customizable-comment-char:
  sequencer: use configured comment character

Merge branch 'sb/blame-color'

Code clean-up.

* sb/blame-color:
  blame: prefer xsnprintf to strcpy for colors

Merge branch 'nd/command-list'

Build doc update for Windows.

* nd/command-list:
  vcbuild/README: update to accommodate for missing common-cmds.h

Merge branch 'es/test-lint-one-shot-export'

Look for broken use of "VAR=VAL shell_func" in test scripts as part
of test-lint.

* es/test-lint-one-shot-export:
  t/check-non-portable-shell: detect "FOO=bar shell_func"
  t/check-non-portable-shell: make error messages more compact
  t/check-non-portable-shell: stop being so polite
  t6046/t9833: fix use of "VAR=VAL cmd" with a shell function

Merge branch 'wc/find-commit-with-pattern-on-detached-head'

"git rev-parse ':/substring'" did not consider the history leading
only to HEAD when looking for a commit with the given substring,
when the HEAD is detached.  This has been fixed.

* wc/find-commit-with-pattern-on-detached-head:
  sha1-name.c: for ":/", find detached HEAD commits

Merge branch 'jc/t3404-one-shot-export-fix'

Correct a broken use of "VAR=VAL shell_func" in a test.

* jc/t3404-one-shot-export-fix:
  t3404: fix use of "VAR=VAL cmd" with a shell function

Merge branch 'mk/merge-in-sparse-checkout'

"git reset --merge" (hence "git merge ---abort") and "git reset --hard"
had trouble working correctly in a sparsely checked out working
tree after a conflict, which has been corrected.

* mk/merge-in-sparse-checkout:
  unpack-trees: do not fail reset because of unmerged skipped entry

Merge branch 'hs/push-cert-check-cleanup'

Code clean-up.

* hs/push-cert-check-cleanup:
  gpg-interface: make parse_gpg_output static and remove from interface header
  builtin/receive-pack: use check_signature from gpg-interface

Merge branch 'jk/empty-pick-fix'

Handling of an empty range by "git cherry-pick" was inconsistent
depending on how the range ended up to be empty, which has been
corrected.

* jk/empty-pick-fix:
  sequencer: don't say BUG on bogus input
  sequencer: handle empty-set cases consistently

Merge branch 'bp/log-ref-write-fd-with-strbuf'

Code clean-up.

* bp/log-ref-write-fd-with-strbuf:
  convert log_ref_write_fd() to use strbuf

Merge branch 'jt/partial-clone-fsck-connectivity'

Partial clone support of "git clone" has been updated to correctly
validate the objects it receives from the other side.  The server
side has been corrected to send objects that are directly
requested, even if they may match the filtering criteria (e.g. when
doing a "lazy blob" partial clone).

* jt/partial-clone-fsck-connectivity:
  clone: check connectivity even if clone is partial
  upload-pack: send refs' objects despite "filter"

Merge branch 'bc/send-email-auto-cte'

The content-transfer-encoding of the message "git send-email" sends
out by default was 8bit, which can cause trouble when there is an
overlong line to bust RFC 5322/2822 limit.  A new option 'auto' to
automatically switch to quoted-printable when there is such a line
in the payload has been introduced and is made the default.

* bc/send-email-auto-cte:
  docs: correct RFC specifying email line length
  send-email: automatically determine transfer-encoding
  send-email: accept long lines with suitable transfer encoding
  send-email: add an auto option for transfer encoding

Merge branch 'bb/unicode-11-width'

The character display width table has been updated to match the
latest Unicode standard.

* bb/unicode-11-width:
  unicode: update the width tables to Unicode 11

Merge branch 'bb/pedantic'

The codebase has been updated to compile cleanly with -pedantic
option.

* bb/pedantic:
  utf8.c: avoid char overflow
  string-list.c: avoid conversion from void * to function pointer
  sequencer.c: avoid empty statements at top level
  convert.c: replace "\e" escapes with "\033".
  fixup! refs/refs-internal.h: avoid forward declaration of an enum
  refs/refs-internal.h: avoid forward declaration of an enum
  fixup! connect.h: avoid forward declaration of an enum
  connect.h: avoid forward declaration of an enum

Merge branch 'tb/config-default'

Compilation fix.

* tb/config-default:
  builtin/config: work around an unsized array forward declaration

Merge branch 'mh/fast-import-no-diff-delta-empty'

"git fast-import" has been updated to avoid attempting to create
delta against a zero-byte-long string, which is pointless.

* mh/fast-import-no-diff-delta-empty:
  fast-import: do not call diff_delta() with empty buffer

Merge branch 'kn/userdiff-php'

The userdiff pattern for .php has been updated.

* kn/userdiff-php:
  userdiff: support new keywords in PHP hunk header
  t4018: add missing test cases for PHP

Merge branch 'jk/fetch-all-peeled-fix'

Test modernization.

* jk/fetch-all-peeled-fix:
  t5500: prettify non-commit tag tests

Merge branch 'ag/rebase-p'

The help message shown in the editor to edit todo list in "rebase -p"
has regressed recently, which has been corrected.

* ag/rebase-p:
  git-rebase--preserve-merges: fix formatting of todo help message

Merge branch 'jt/connectivity-check-after-unshallow'

"git fetch" failed to correctly validate the set of objects it
received when making a shallow history deeper, which has been
corrected.

* jt/connectivity-check-after-unshallow:
  fetch-pack: write shallow, then check connectivity
  fetch-pack: implement ref-in-want
  fetch-pack: put shallow info in output parameter
  fetch: refactor to make function args narrower
  fetch: refactor fetch_refs into two functions
  fetch: refactor the population of peer ref OIDs
  upload-pack: test negotiation with changing repository
  upload-pack: implement ref-in-want
  test-pkt-line: add unpack-sideband subcommand

Merge branch 'jk/for-each-ref-icase'

The "--ignore-case" option of "git for-each-ref" (and its friends)
did not work correctly, which has been fixed.

* jk/for-each-ref-icase:
  ref-filter: avoid backend filtering with --ignore-case
  for-each-ref: consistently pass WM_IGNORECASE flag
  t6300: add a test for --ignore-case

Merge branch 'en/t5407-rebase-m-fix'

* en/t5407-rebase-m-fix:
  t5407: fix test to cover intended arguments

Merge branch 'en/apply-comment-fix'

* en/apply-comment-fix:
  apply: fix grammar error in comment

Merge branch 'en/rebase-consistency'

"git rebase" behaved slightly differently depending on which one of
the three backends gets used; this has been documented and an
effort to make them more uniform has begun.

* en/rebase-consistency:
  git-rebase: make --allow-empty-message the default
  t3401: add directory rename testcases for rebase and am
  git-rebase.txt: document behavioral differences between modes
  directory-rename-detection.txt: technical docs on abilities and limitations
  git-rebase.txt: address confusion between --no-ff vs --force-rebase
  git-rebase: error out when incompatible options passed
  t3422: new testcases for checking when incompatible options passed
  git-rebase.sh: update help messages a bit
  git-rebase.txt: document incompatible options

Merge branch 'sb/submodule-move-head-error-msg'

"git checkout --recurse-submodules another-branch" did not report
in which submodule it failed to update the working tree, which
resulted in an unhelpful error message.

* sb/submodule-move-head-error-msg:
  submodule.c: report the submodule that an error occurs in

Merge branch 'rj/submodule-fsck-skip'

"fsck.skipList" did not prevent a blob object listed there from
being inspected for is contents (e.g. we recently started to
inspect the contents of ".gitmodules" for certain malicious
patterns), which has been corrected.

* rj/submodule-fsck-skip:
  fsck: check skiplist for object in fsck_blob()

diff.c: offer config option to control ws handling in move detection

Signed-off-by: Stefan Beller <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff.c: add white space mode to move detection that allows indent changes

The option of --color-moved has proven to be useful as observed on the
mailing list. However when refactoring sometimes the indentation changes,
for example when partitioning a functions into smaller helper functions
the code usually mostly moved around except for a decrease in indentation.

To just review the moved code ignoring the change in indentation, a mode
to ignore spaces in the move detection as implemented in a previous patch
would be enough.  However the whole move coloring as motivated in commit
2e2d5ac (diff.c: color moved lines differently, 2017-06-30), brought
up the notion of the reviewer being able to trust the move of a "block".

As there are languages such as python, which depend on proper relative
indentation for the control flow of the program, ignoring any white space
change in a block would not uphold the promises of 2e2d5ac that allows
reviewers to pay less attention to the inside of a block, as inside
the reviewer wants to assume the same program flow.

This new mode of white space ignorance will take this into account and will
only allow the same white space changes per line in each block. This patch
even allows only for the same change at the beginning of the lines.

As this is a white space mode, it is made exclusive to other white space
modes in the move detection.

This patch brings some challenges, related to the detection of blocks.
We need a wide net to catch the possible moved lines, but then need to
narrow down to check if the blocks are still intact. Consider this
example (ignoring block sizes):

 - A
 - B
 - C
 +    A
 +    B
 +    C

At the beginning of a block when checking if there is a counterpart
for A, we have to ignore all space changes. However at the following
lines we have to check if the indent change stayed the same.

Checking if the indentation change did stay the same, is done by computing
the indentation change by the difference in line length, and then assume
the change is only in the beginning of the longer line, the common tail
is the same. That is why the test contains lines like:

 - <TAB> A
 ...
 + A <TAB>
 ...

As the first line starting a block is caught using a compare function that
ignores white spaces unlike the rest of the block, where the white space
delta is taken into account for the comparison, we also have to think about
the following situation:

 - A
 - B
 -   A
 -   B
 +    A
 +    B
 +      A
 +      B

When checking if the first A (both in the + and - lines) is a start of
a block, we have to check all 'A' and record all the white space deltas
such that we can find the example above to be just one block that is
indented.

Signed-off-by: Stefan Beller <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

Third batch for 2.19 cycle

Signed-off-by: Junio C Hamano <gitster@pobox.com>

Merge branch 'js/enhanced-version-info'

Build fix.

* js/enhanced-version-info:
  Makefile: fix the "built from commit" code

Merge branch 'sb/mailmap'

* sb/mailmap:
  .mailmap: merge different spellings of names

Merge branch 'ms/core-icase-doc'

Clarify that setting core.ignoreCase to deviate from reality would
not turn a case-incapable filesystem into a case-capable one.

* ms/core-icase-doc:
  Documentation: declare "core.ignoreCase" as internal variable

Merge branch 'ds/commit-graph'

Docfix.

* ds/commit-graph:
  commit-graph: fix documentation inconsistencies

Merge branch 'tz/exclude-doc-smallfixes'

Doc updates.

* tz/exclude-doc-smallfixes:
  dir.c: fix typos in core.excludesfile comment
  gitignore.txt: clarify default core.excludesfile path

Merge branch 'js/rebase-recreate-merge'

Docfix.

* js/rebase-recreate-merge:
  rebase: fix documentation formatting

Merge branch 'en/rebase-i-microfixes'

* en/rebase-i-microfixes:
  git-rebase--merge: modernize "git-$cmd" to "git $cmd"
  Fix use of strategy options with interactive rebases
  t3418: add testcase showing problems with rebase -i and strategy options

Merge branch 'mb/filter-branch-optim'

"git filter-branch" when used with the "--state-branch" option
still attempted to rewrite the commits whose filtered result is
known from the previous attempt (which is recorded on the state
branch); the command has been corrected not to waste cycles doing
so.

* mb/filter-branch-optim:
  filter-branch: skip commits present on --state-branch

Merge branch 'dj/runtime-prefix'

POSIX portability fix in Makefile to fix a glitch introduced a few
releases ago.

* dj/runtime-prefix:
  Makefile: tweak sed invocation

Merge branch 'ao/config-from-gitmodules'

Tighten the API to make it harder to misuse in-tree .gitmodules
file, even though it shares the same syntax with configuration
files, to read random configuration items from it.

* ao/config-from-gitmodules:
  submodule-config: reuse config_from_gitmodules in repo_read_gitmodules
  submodule-config: pass repository as argument to config_from_gitmodules
  submodule-config: make 'config_from_gitmodules' private
  submodule-config: add helper to get 'update-clone' config from .gitmodules
  submodule-config: add helper function to get 'fetch' config from .gitmodules
  config: move config_from_gitmodules to submodule-config.c

Merge branch 'jk/branch-l-0-deprecation'

The "-l" option in "git branch -l" is an unfortunate short-hand for
"--create-reflog", but many users, both old and new, somehow expect
it to be something else, perhaps "--list".  This step warns when "-l"
is used as a short-hand for "--create-reflog" and warns about the
future repurposing of the it when it is used.

* jk/branch-l-0-deprecation:
  branch: deprecate "-l" option
  t: switch "branch -l" to "branch --create-reflog"
  t3200: unset core.logallrefupdates when testing reflog creation

Merge branch 'tb/grep-column'

"git grep" learned the "--column" option that gives not just the
line number but the column number of the hit.

* tb/grep-column:
  contrib/git-jump/git-jump: jump to exact location
  grep.c: add configuration variables to show matched option
  builtin/grep.c: add '--column' option to 'git-grep(1)'
  grep.c: display column number of first match
  grep.[ch]: extend grep_opt to allow showing matched column
  grep.c: expose {,inverted} match column in match_line()
  Documentation/config.txt: camel-case lineNumber for consistency

Merge branch 'vs/typofixes'

Doc fix.

* vs/typofixes:
  Documentation: spelling and grammar fixes

Merge branch 'bw/protocol-v2'

Doc fix.

* bw/protocol-v2:
  protocol-v2 doc: put HTTP headers after request

Merge branch 'jt/remove-pack-bitmap-global'

The effort to move globals to per-repository in-core structure
continues.

* jt/remove-pack-bitmap-global:
  pack-bitmap: add free function
  pack-bitmap: remove bitmap_git global variable

Merge branch 'bw/config-refer-to-gitsubmodules-doc'

Docfix.

* bw/config-refer-to-gitsubmodules-doc:
  docs: link to gitsubmodules

Merge branch 'xy/format-patch-prereq-patch-id-fix'

Recently added "--base" option to "git format-patch" command did
not correctly generate prereq patch ids.

* xy/format-patch-prereq-patch-id-fix:
  format-patch: clear UNINTERESTING flag before prepare_bases

Merge branch 'pw/rebase-i-keep-reword-after-conflict'

Bugfix for "rebase -i" corner case regression.

* pw/rebase-i-keep-reword-after-conflict:
  sequencer: do not squash 'reword' commits when we hit conflicts

Merge branch 'ld/p423'

Code preparation to make "git p4" closer to be usable with Python 3.

* ld/p423:
  git-p4: python3: fix octal constants
  git-p4: python3: use print() function
  git-p4: python3: basestring workaround
  git-p4: python3: remove backticks
  git-p4: python3: replace dict.has_key(k) with "k in dict"
  git-p4: python3: replace <> with !=

Merge branch 'ds/ewah-cleanup'

Remove unused function definitions and declarations from ewah
bitmap subsystem.

* ds/ewah-cleanup:
  ewah: delete unused 'rlwit_discharge_empty()'
  ewah: drop ewah_serialize_native function
  ewah: drop ewah_deserialize function
  ewah_io: delete unused 'ewah_serialize()'
  ewah_bitmap: delete unused 'ewah_or()'
  ewah_bitmap: delete unused 'ewah_not()'
  ewah_bitmap: delete unused 'ewah_and_not()'
  ewah_bitmap: delete unused 'ewah_and()'
  ewah/bitmap.c: delete unused 'bitmap_each_bit()'
  ewah/bitmap.c: delete unused 'bitmap_clear()'

Merge branch 'sb/submodule-core-worktree'

"git submodule" did not correctly adjust core.worktree setting that
indicates whether/where a submodule repository has its associated
working tree across various state transitions, which has been
corrected.

* sb/submodule-core-worktree:
  submodule deinit: unset core.worktree
  submodule: ensure core.worktree is set after update
  submodule: unset core.worktree if no working tree is present

Merge branch 'sb/object-store-grafts'

The conversion to pass "the_repository" and then "a_repository"
throughout the object access API continues.

* sb/object-store-grafts:
  commit: allow lookup_commit_graft to handle arbitrary repositories
  commit: allow prepare_commit_graft to handle arbitrary repositories
  shallow: migrate shallow information into the object parser
  path.c: migrate global git_path_* to take a repository argument
  cache: convert get_graft_file to handle arbitrary repositories
  commit: convert read_graft_file to handle arbitrary repositories
  commit: convert register_commit_graft to handle arbitrary repositories
  commit: convert commit_graft_pos() to handle arbitrary repositories
  shallow: add repository argument to is_repository_shallow
  shallow: add repository argument to check_shallow_file_for_update
  shallow: add repository argument to register_shallow
  shallow: add repository argument to set_alternate_shallow_file
  commit: add repository argument to lookup_commit_graft
  commit: add repository argument to prepare_commit_graft
  commit: add repository argument to read_graft_file
  commit: add repository argument to register_commit_graft
  commit: add repository argument to commit_graft_pos
  object: move grafts to object parser
  object-store: move object access functions to object-store.h

Merge branch 'en/merge-recursive-cleanup'

Code cleanup.

* en/merge-recursive-cleanup:
  merge-recursive: add pointer about unduly complex looking code
  merge-recursive: rename conflict_rename_*() family of functions
  merge-recursive: clarify the rename_dir/RENAME_DIR meaning
  merge-recursive: align labels with their respective code blocks
  merge-recursive: fix numerous argument alignment issues
  merge-recursive: fix miscellaneous grammar error in comment

commit-graph: add repo arg to graph readers

Add a struct repository argument to the functions in commit-graph.h that
read the commit graph. (This commit does not affect functions that write
commit graphs.)

Because the commit graph functions can now read the commit graph of any
repository, the global variable core_commit_graph has been removed.
Instead, the config option core.commitGraph is now read on the first
time in a repository that a commit is attempted to be parsed using its
commit graph.

This commit includes a test that exercises the functionality on an
arbitrary repository that is not the_repository.

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

commit-graph: store graph in struct object_store

Instead of storing commit graphs in static variables, store them in
struct object_store. There are no changes to the signatures of existing
functions - they all still only support the_repository, and support for
other instances of struct repository will be added in a subsequent
commit.

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

commit-graph: add free_commit_graph

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

commit-graph: add missing forward declaration

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

object-store: add missing include

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

commit-graph: refactor preparing commit graph

Two functions in the code (1) check if the repository is configured for
commit graphs, (2) call prepare_commit_graph(), and (3) check if the
graph exists. Move (1) and (3) into prepare_commit_graph(), reducing
duplication of code.

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

Merge branch 'ds/commit-graph-fsck' into jt/commit-graph-per-object-store

* ds/commit-graph-fsck: (23 commits)
  coccinelle: update commit.cocci
  commit-graph: update design document
  gc: automatically write commit-graph files
  commit-graph: add '--reachable' option
  commit-graph: use string-list API for input
  fsck: verify commit-graph
  commit-graph: verify contents match checksum
  commit-graph: test for corrupted octopus edge
  commit-graph: verify commit date
  commit-graph: verify generation number
  commit-graph: verify parent list
  commit-graph: verify root tree OIDs
  commit-graph: verify objects exist
  commit-graph: verify corrupt OID fanout and lookup
  commit-graph: verify required chunks are present
  commit-graph: verify catches corrupt signature
  commit-graph: add 'verify' subcommand
  commit-graph: load a root tree from specific graph
  commit: force commit to parse from object database
  commit-graph: parse commit from chosen graph
  ...

diff.c: factor advance_or_nullify out of mark_color_as_moved

This moves the part of code that checks if we're still in a block
into its own function.  We'll need a different approach on advancing
the blocks in a later patch, so having it as a separate function will
prove useful.

While at it rename the variable `p` to `prev` to indicate that it refers
to the previous line. This is as pmb[i] was assigned in the last iteration
of the outmost for loop.

Further rename `pnext` to `cur` to indicate that this should match up with
the current line of the outmost for loop.

Also replace the advancement of pmb[i] to reuse `cur` instead of
using `p->next` (which is how the name for pnext could be explained.

Signed-off-by: Stefan Beller <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff.c: decouple white space treatment from move detection algorithm

In the original implementation of the move detection logic the choice for
ignoring white space changes is the same for the move detection as it is
for the regular diff.  Some cases came up where different treatment would
have been nice.

Allow the user to specify that white space should be ignored differently
during detection of moved lines than during generation of added and removed
lines. This is done by providing analogs to the --ignore-space-at-eol,
-b, and -w options by introducing the option --color-moved-ws=<modes>
with the modes named "ignore-space-at-eol", "ignore-space-change" and
"ignore-all-space", which is used only during the move detection phase.

As we change the default, we'll adjust the tests.

For now we do not infer any options to treat white spaces in the move
detection from the generic white space options given to diff.
This can be tuned later to reasonable default.

As we plan on adding more white space related options in a later patch,
that interferes with the current white space options, use a flag field
and clamp it down to  XDF_WHITESPACE_FLAGS, as that (a) allows to easily
check at parse time if we give invalid combinations and (b) can reuse
parts of this patch.

By having the white space treatment in its own option, we'll also
make it easier for a later patch to have an config option for
spaces in the move detection.

Signed-off-by: Stefan Beller <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff.c: add a blocks mode for moved code detection

The new "blocks" mode provides a middle ground between plain and zebra.
It is as intuitive (few colors) as plain, but still has the requirement
for a minimum of lines/characters to count a block as moved.

Suggested-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
 (https://public-inbox.org/git/87o9j0uljo.fsf@evledraar.gmail.com/)
Signed-off-by: Stefan Beller <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff.c: adjust hash function signature to match hashmap expectation

This makes the follow up patch easier.

Signed-off-by: Stefan Beller <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff.c: do not pass diff options as keydata to hashmap

When we initialize the hashmap, we give it a pointer to the
diff_options, which it then passes along to each call of the
hashmap_cmp_fn function. There's no need to pass it a second time as
the "keydata" parameter, and our comparison functions never look at
keydata.

This was a mistake left over from an earlier round of 2e2d5ac184
(diff.c: color moved lines differently, 2017-06-30), before hashmap
learned to pass the data pointer for us.

Explanation-by: Jeff King <peff@peff.net>
Signed-off-by: Stefan Beller <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

t4015: avoid git as a pipe input

In t4015 we have a pattern of

    git diff [<options, related to color>] |
        grep -v "index" |
        test_decode_color >actual &&

to produce output that we want to test against. This pattern was introduced
in 86b452e2769 (diff.c: add dimming to moved line detection, 2017-06-30)
as then the focus on getting the colors right. However the pattern used
is not best practice as we do care about the exit code of Git. So let's
not have Git as the upstream of a pipe. Piping the output of grep to
some function is fine as we assume grep to be un-flawed in our test suite.

Signed-off-by: Stefan Beller <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

xdiff/xdiffi.c: remove unneeded function declarations

There is no need to forward-declare these functions, as they are used
after their implementation only.

Signed-off-by: Stefan Beller <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

xdiff/xdiff.h: remove unused flags

These flags were there since the beginning (3443546f6e (Use a *real*
built-in diff generator, 2006-03-24), but were never used. Remove them.

Signed-off-by: Stefan Beller <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

t/chainlint: add chainlint "specialized" test cases

The --chain-lint option uses heuristics and knowledge of shell syntax to
detect broken &&-chains in subshells by pure textual inspection. The
heuristics handle a range of stylistic variations in existing tests
(evolved over the years), however, they are still best-guesses. As such,
it is possible for future changes to accidentally break assumptions upon
which the heuristics are based. Protect against this possibility by
adding tests which check the linter itself for correctness.

In addition to protecting against regressions, these tests help document
(for humans) expected behavior, which is important since the linter's
implementation language ('sed') does not necessarily lend itself to easy
comprehension.

Signed-off-by: Eric Sunshine <sunshine@sunshineco.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>