Revision 24ff4d56cf400126aa93ac9a5b9d8a21afadf3f6 authored by Björn Gustavsson on 06 March 2010, 14:30:29 UTC, committed by Junio C Hamano on 07 March 2010, 07:53:00 UTC
In the next commit, we will make it possible for blank context
lines to match beyond the end of the file. That means that a hunk
with a preimage that has more lines than present in the file may
be possible to successfully apply. Therefore, we must remove
the quick rejection test in find_pos().

find_pos() will already work correctly without the quick
rejection test, but that might not be obvious. Therefore,
comment the test for handling out-of-range line numbers in
find_pos() and cast the "line" variable to the same (unsigned)
type as img->nr.

What are performance implications of removing the quick
rejection test?

It can only help "git apply" to reject a patch faster. For example,
if I have a file with one million lines and a patch that removes
slightly more than 50 percent of the lines and try to apply that
patch twice, the second attempt will fail slightly faster
with the test than without (based on actual measurements).

However, there is the pathological case of a patch with many
more context lines than the default three, and applying that patch
using "git apply -C1". Without the rejection test, the running
time will be roughly proportional to the number of context lines
times the size of the file. That could be handled by writing
a more complicated rejection test (it would have to count the
number of blanks at the end of the preimage), but I don't find
that worth doing until there is a real-world use case that
would benfit from it.

It would be possible to keep the quick rejection test if
--whitespace=fix is not given, but I don't like that from
a testing point of view.

Signed-off-by: Björn Gustavsson <bgustavsson@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
1 parent 9b25949
History
File Mode Size
Documentation
block-sha1
compat
contrib
git-gui
git_remote_helpers
gitk-git
gitweb
perl
ppc
t
templates
xdiff
.gitattributes -rw-r--r-- 105 bytes
.gitignore -rw-r--r-- 2.8 KB
.mailmap -rw-r--r-- 2.5 KB
COPYING -rw-r--r-- 18.3 KB
GIT-VERSION-GEN -rwxr-xr-x 734 bytes
INSTALL -rw-r--r-- 6.3 KB
Makefile -rw-r--r-- 57.1 KB
README -rw-r--r-- 2.4 KB
RelNotes l--------- 32 bytes
abspath.c -rw-r--r-- 2.8 KB
advice.c -rw-r--r-- 1.3 KB
advice.h -rw-r--r-- 399 bytes
alias.c -rw-r--r-- 1.4 KB
alloc.c -rw-r--r-- 1.7 KB
archive-tar.c -rw-r--r-- 6.3 KB
archive-zip.c -rw-r--r-- 7.3 KB
archive.c -rw-r--r-- 10.2 KB
archive.h -rw-r--r-- 927 bytes
attr.c -rw-r--r-- 16.1 KB
attr.h -rw-r--r-- 973 bytes
base85.c -rw-r--r-- 2.7 KB
bisect.c -rw-r--r-- 23.7 KB
bisect.h -rw-r--r-- 820 bytes
blob.c -rw-r--r-- 565 bytes
blob.h -rw-r--r-- 664 bytes
branch.c -rw-r--r-- 5.4 KB
branch.h -rw-r--r-- 1.0 KB
builtin-add.c -rw-r--r-- 11.3 KB
builtin-annotate.c -rw-r--r-- 446 bytes
builtin-apply.c -rw-r--r-- 91.6 KB
builtin-archive.c -rw-r--r-- 3.5 KB
builtin-bisect--helper.c -rw-r--r-- 617 bytes
builtin-blame.c -rw-r--r-- 62.8 KB
builtin-branch.c -rw-r--r-- 18.7 KB
builtin-bundle.c -rw-r--r-- 1.8 KB
builtin-cat-file.c -rw-r--r-- 5.6 KB
builtin-check-attr.c -rw-r--r-- 2.9 KB
builtin-check-ref-format.c -rw-r--r-- 1.4 KB
builtin-checkout-index.c -rw-r--r-- 8.1 KB
builtin-checkout.c -rw-r--r-- 22.9 KB
builtin-clean.c -rw-r--r-- 4.1 KB
builtin-clone.c -rw-r--r-- 17.2 KB
builtin-commit-tree.c -rw-r--r-- 3.6 KB
builtin-commit.c -rw-r--r-- 35.5 KB
builtin-config.c -rw-r--r-- 13.5 KB
builtin-count-objects.c -rw-r--r-- 3.0 KB
builtin-describe.c -rw-r--r-- 9.9 KB
builtin-diff-files.c -rw-r--r-- 1.9 KB
builtin-diff-index.c -rw-r--r-- 1.2 KB
builtin-diff-tree.c -rw-r--r-- 4.2 KB
builtin-diff.c -rw-r--r-- 10.6 KB
builtin-fast-export.c -rw-r--r-- 16.0 KB
builtin-fetch-pack.c -rw-r--r-- 22.7 KB
builtin-fetch.c -rw-r--r-- 24.1 KB
builtin-fmt-merge-msg.c -rw-r--r-- 8.7 KB
builtin-for-each-ref.c -rw-r--r-- 22.4 KB
builtin-fsck.c -rw-r--r-- 15.8 KB
builtin-gc.c -rw-r--r-- 6.1 KB
builtin-grep.c -rw-r--r-- 23.2 KB
builtin-hash-object.c -rw-r--r-- 3.5 KB
builtin-help.c -rw-r--r-- 11.3 KB
builtin-index-pack.c -rw-r--r-- 26.8 KB
builtin-init-db.c -rw-r--r-- 13.4 KB
builtin-log.c -rw-r--r-- 34.9 KB
builtin-ls-files.c -rw-r--r-- 15.3 KB
builtin-ls-remote.c -rw-r--r-- 2.4 KB
builtin-ls-tree.c -rw-r--r-- 4.4 KB
builtin-mailinfo.c -rw-r--r-- 23.5 KB
builtin-mailsplit.c -rw-r--r-- 6.3 KB
builtin-merge-base.c -rw-r--r-- 1.4 KB
builtin-merge-file.c -rw-r--r-- 2.7 KB
builtin-merge-index.c -rw-r--r-- 2.2 KB
builtin-merge-ours.c -rw-r--r-- 926 bytes
builtin-merge-recursive.c -rw-r--r-- 2.1 KB
builtin-merge-tree.c -rw-r--r-- 8.1 KB
builtin-merge.c -rw-r--r-- 33.4 KB
builtin-mktag.c -rw-r--r-- 5.2 KB
builtin-mktree.c -rw-r--r-- 5.0 KB
builtin-mv.c -rw-r--r-- 5.9 KB
builtin-name-rev.c -rw-r--r-- 7.1 KB
builtin-pack-objects.c -rw-r--r-- 59.3 KB
builtin-pack-redundant.c -rw-r--r-- 15.0 KB
builtin-pack-refs.c -rw-r--r-- 589 bytes
builtin-patch-id.c -rw-r--r-- 1.6 KB
builtin-prune-packed.c -rw-r--r-- 1.9 KB
builtin-prune.c -rw-r--r-- 3.8 KB
builtin-push.c -rw-r--r-- 6.5 KB
builtin-read-tree.c -rw-r--r-- 6.5 KB
builtin-receive-pack.c -rw-r--r-- 16.7 KB
builtin-reflog.c -rw-r--r-- 17.7 KB
builtin-remote.c -rw-r--r-- 38.7 KB
builtin-replace.c -rw-r--r-- 3.9 KB
builtin-rerere.c -rw-r--r-- 3.8 KB
builtin-reset.c -rw-r--r-- 9.3 KB
builtin-rev-list.c -rw-r--r-- 9.4 KB
builtin-rev-parse.c -rw-r--r-- 15.8 KB
builtin-revert.c -rw-r--r-- 11.7 KB
builtin-rm.c -rw-r--r-- 7.0 KB
builtin-send-pack.c -rw-r--r-- 14.8 KB
builtin-shortlog.c -rw-r--r-- 8.6 KB
builtin-show-branch.c -rw-r--r-- 23.0 KB
builtin-show-ref.c -rw-r--r-- 6.3 KB
builtin-stripspace.c -rw-r--r-- 2.0 KB
builtin-symbolic-ref.c -rw-r--r-- 1.3 KB
builtin-tag.c -rw-r--r-- 11.3 KB
builtin-tar-tree.c -rw-r--r-- 2.5 KB
builtin-unpack-file.c -rw-r--r-- 845 bytes
builtin-unpack-objects.c -rw-r--r-- 12.9 KB
builtin-update-index.c -rw-r--r-- 20.3 KB
builtin-update-ref.c -rw-r--r-- 1.6 KB
builtin-update-server-info.c -rw-r--r-- 591 bytes
builtin-upload-archive.c -rw-r--r-- 4.0 KB
builtin-var.c -rw-r--r-- 1.8 KB
builtin-verify-pack.c -rw-r--r-- 4.1 KB
builtin-verify-tag.c -rw-r--r-- 2.7 KB
builtin-write-tree.c -rw-r--r-- 1.5 KB
builtin.h -rw-r--r-- 8.0 KB
bundle.c -rw-r--r-- 10.2 KB
bundle.h -rw-r--r-- 627 bytes
cache-tree.c -rw-r--r-- 15.6 KB
cache-tree.h -rw-r--r-- 1.4 KB
cache.h -rw-r--r-- 36.2 KB
check-builtins.sh -rwxr-xr-x 588 bytes
check-racy.c -rw-r--r-- 538 bytes
check_bindir -rwxr-xr-x 369 bytes
color.c -rw-r--r-- 4.5 KB
color.h -rw-r--r-- 1.4 KB
combine-diff.c -rw-r--r-- 27.8 KB
command-list.txt -rw-r--r-- 7.7 KB
commit.c -rw-r--r-- 17.5 KB
commit.h -rw-r--r-- 4.8 KB
config.c -rw-r--r-- 29.8 KB
config.mak.in -rw-r--r-- 1.4 KB
configure.ac -rw-r--r-- 24.0 KB
connect.c -rw-r--r-- 13.7 KB
convert.c -rw-r--r-- 14.1 KB
copy.c -rw-r--r-- 1.6 KB
csum-file.c -rw-r--r-- 2.5 KB
csum-file.h -rw-r--r-- 761 bytes
ctype.c -rw-r--r-- 874 bytes
daemon.c -rw-r--r-- 25.1 KB
date.c -rw-r--r-- 22.2 KB
decorate.c -rw-r--r-- 1.8 KB
decorate.h -rw-r--r-- 400 bytes
delta.h -rw-r--r-- 3.4 KB
diff-delta.c -rw-r--r-- 15.3 KB
diff-lib.c -rw-r--r-- 13.4 KB
diff-no-index.c -rw-r--r-- 6.1 KB
diff.c -rw-r--r-- 100.1 KB
diff.h -rw-r--r-- 9.2 KB
diffcore-break.c -rw-r--r-- 8.7 KB
diffcore-delta.c -rw-r--r-- 5.4 KB
diffcore-order.c -rw-r--r-- 2.2 KB
diffcore-pickaxe.c -rw-r--r-- 3.2 KB
diffcore-rename.c -rw-r--r-- 16.9 KB
diffcore.h -rw-r--r-- 4.1 KB
dir.c -rw-r--r-- 24.2 KB
dir.h -rw-r--r-- 2.8 KB
editor.c -rw-r--r-- 1.1 KB
entry.c -rw-r--r-- 6.0 KB
environment.c -rw-r--r-- 4.9 KB
exec_cmd.c -rw-r--r-- 3.3 KB
exec_cmd.h -rw-r--r-- 487 bytes
fast-import.c -rw-r--r-- 75.0 KB
fetch-pack.h -rw-r--r-- 479 bytes
fixup-builtins -rwxr-xr-x 432 bytes
fsck.c -rw-r--r-- 8.0 KB
fsck.h -rw-r--r-- 1.0 KB
generate-cmdlist.sh -rwxr-xr-x 443 bytes
git-add--interactive.perl -rwxr-xr-x 34.4 KB
git-am.sh -rwxr-xr-x 17.8 KB
git-archimport.perl -rwxr-xr-x 36.0 KB
git-bisect.sh -rwxr-xr-x 9.8 KB
git-compat-util.h -rw-r--r-- 11.5 KB
git-cvsexportcommit.perl -rwxr-xr-x 12.4 KB
git-cvsimport.perl -rwxr-xr-x 28.1 KB
git-cvsserver.perl -rwxr-xr-x 114.9 KB
git-difftool--helper.sh -rwxr-xr-x 1.7 KB
git-difftool.perl -rwxr-xr-x 2.6 KB
git-filter-branch.sh -rwxr-xr-x 11.9 KB
git-instaweb.sh -rwxr-xr-x 11.0 KB
git-lost-found.sh -rwxr-xr-x 554 bytes
git-merge-octopus.sh -rwxr-xr-x 2.0 KB
git-merge-one-file.sh -rwxr-xr-x 3.7 KB
git-merge-resolve.sh -rwxr-xr-x 944 bytes
git-mergetool--lib.sh -rw-r--r-- 8.8 KB
git-mergetool.sh -rwxr-xr-x 6.0 KB
git-notes.sh -rwxr-xr-x 2.7 KB
git-parse-remote.sh -rwxr-xr-x 1.9 KB
git-pull.sh -rwxr-xr-x 7.8 KB
git-quiltimport.sh -rwxr-xr-x 3.3 KB
git-rebase--interactive.sh -rwxr-xr-x 23.1 KB
git-rebase.sh -rwxr-xr-x 14.0 KB
git-relink.perl -rwxr-xr-x 4.0 KB
git-repack.sh -rwxr-xr-x 4.4 KB
git-request-pull.sh -rwxr-xr-x 1.6 KB
git-send-email.perl -rwxr-xr-x 33.1 KB
git-sh-setup.sh -rwxr-xr-x 3.5 KB
git-stash.sh -rwxr-xr-x 8.4 KB
git-submodule.sh -rwxr-xr-x 17.0 KB
git-svn.perl -rwxr-xr-x 171.0 KB
git-web--browse.sh -rwxr-xr-x 3.9 KB
git.c -rw-r--r-- 14.9 KB
git.spec.in -rw-r--r-- 10.0 KB
graph.c -rw-r--r-- 34.6 KB
graph.h -rw-r--r-- 2.5 KB
grep.c -rw-r--r-- 21.0 KB
grep.h -rw-r--r-- 2.2 KB
hash.c -rw-r--r-- 2.5 KB
hash.h -rw-r--r-- 1.1 KB
help.c -rw-r--r-- 8.4 KB
help.h -rw-r--r-- 751 bytes
hex.c -rw-r--r-- 2.1 KB
http-backend.c -rw-r--r-- 14.1 KB
http-fetch.c -rw-r--r-- 2.3 KB
http-push.c -rw-r--r-- 54.2 KB
http-walker.c -rw-r--r-- 13.7 KB
http.c -rw-r--r-- 31.0 KB
http.h -rw-r--r-- 5.1 KB
ident.c -rw-r--r-- 6.1 KB
imap-send.c -rw-r--r-- 31.3 KB
levenshtein.c -rw-r--r-- 2.5 KB
levenshtein.h -rw-r--r-- 201 bytes
list-objects.c -rw-r--r-- 4.6 KB
list-objects.h -rw-r--r-- 422 bytes
ll-merge.c -rw-r--r-- 9.6 KB
ll-merge.h -rw-r--r-- 337 bytes
lockfile.c -rw-r--r-- 6.3 KB
log-tree.c -rw-r--r-- 14.1 KB
log-tree.h -rw-r--r-- 783 bytes
mailmap.c -rw-r--r-- 6.5 KB
mailmap.h -rw-r--r-- 263 bytes
match-trees.c -rw-r--r-- 8.7 KB
merge-file.c -rw-r--r-- 2.4 KB
merge-recursive.c -rw-r--r-- 38.8 KB
merge-recursive.h -rw-r--r-- 1.5 KB
name-hash.c -rw-r--r-- 2.5 KB
notes.c -rw-r--r-- 12.4 KB
notes.h -rw-r--r-- 295 bytes
object.c -rw-r--r-- 5.8 KB
object.h -rw-r--r-- 2.5 KB
pack-check.c -rw-r--r-- 4.5 KB
pack-refs.c -rw-r--r-- 2.8 KB
pack-refs.h -rw-r--r-- 465 bytes
pack-revindex.c -rw-r--r-- 4.0 KB
pack-revindex.h -rw-r--r-- 223 bytes
pack-write.c -rw-r--r-- 7.3 KB
pack.h -rw-r--r-- 2.2 KB
pager.c -rw-r--r-- 2.1 KB
parse-options.c -rw-r--r-- 15.6 KB
parse-options.h -rw-r--r-- 7.0 KB
patch-delta.c -rw-r--r-- 2.1 KB
patch-ids.c -rw-r--r-- 2.5 KB
patch-ids.h -rw-r--r-- 490 bytes
path.c -rw-r--r-- 14.5 KB
pkt-line.c -rw-r--r-- 3.3 KB
pkt-line.h -rw-r--r-- 589 bytes
preload-index.c -rw-r--r-- 2.3 KB
pretty.c -rw-r--r-- 26.7 KB
progress.c -rw-r--r-- 6.5 KB
progress.h -rw-r--r-- 504 bytes
quote.c -rw-r--r-- 10.2 KB
quote.h -rw-r--r-- 2.5 KB
reachable.c -rw-r--r-- 5.6 KB
reachable.h -rw-r--r-- 127 bytes
read-cache.c -rw-r--r-- 44.2 KB
reflog-walk.c -rw-r--r-- 7.7 KB
reflog-walk.h -rw-r--r-- 664 bytes
refs.c -rw-r--r-- 43.5 KB
refs.h -rw-r--r-- 3.9 KB
remote-curl.c -rw-r--r-- 19.4 KB
remote.c -rw-r--r-- 41.1 KB
remote.h -rw-r--r-- 4.2 KB
replace_object.c -rw-r--r-- 2.6 KB
rerere.c -rw-r--r-- 14.3 KB
rerere.h -rw-r--r-- 505 bytes
resolve-undo.c -rw-r--r-- 4.0 KB
resolve-undo.h -rw-r--r-- 546 bytes
revision.c -rw-r--r-- 52.5 KB
revision.h -rw-r--r-- 4.3 KB
run-command.c -rw-r--r-- 11.5 KB
run-command.h -rw-r--r-- 2.6 KB
send-pack.h -rw-r--r-- 374 bytes
server-info.c -rw-r--r-- 5.2 KB
setup.c -rw-r--r-- 13.4 KB
sha1-lookup.c -rw-r--r-- 7.8 KB
sha1-lookup.h -rw-r--r-- 403 bytes
sha1_file.c -rw-r--r-- 62.8 KB
sha1_name.c -rw-r--r-- 25.8 KB
shallow.c -rw-r--r-- 2.3 KB
shell.c -rw-r--r-- 2.2 KB
shortlog.h -rw-r--r-- 450 bytes
show-index.c -rw-r--r-- 2.2 KB
sideband.c -rw-r--r-- 3.4 KB
sideband.h -rw-r--r-- 326 bytes
sigchain.c -rw-r--r-- 969 bytes
sigchain.h -rw-r--r-- 215 bytes
strbuf.c -rw-r--r-- 8.0 KB
strbuf.h -rw-r--r-- 5.0 KB
string-list.c -rw-r--r-- 4.2 KB
string-list.h -rw-r--r-- 1.7 KB
submodule.c -rw-r--r-- 4.5 KB
submodule.h -rw-r--r-- 281 bytes
symlinks.c -rw-r--r-- 7.9 KB
tag.c -rw-r--r-- 2.7 KB
tag.h -rw-r--r-- 471 bytes
tar.h -rw-r--r-- 644 bytes
test-chmtime.c -rw-r--r-- 2.6 KB
test-ctype.c -rw-r--r-- 1.4 KB
test-date.c -rw-r--r-- 1.3 KB
test-delta.c -rw-r--r-- 1.8 KB
test-dump-cache-tree.c -rw-r--r-- 1.5 KB
test-genrandom.c -rw-r--r-- 722 bytes
test-index-version.c -rw-r--r-- 264 bytes
test-match-trees.c -rw-r--r-- 588 bytes
test-parse-options.c -rw-r--r-- 3.0 KB
test-path-utils.c -rw-r--r-- 872 bytes
test-run-command.c -rw-r--r-- 774 bytes
test-sha1.c -rw-r--r-- 816 bytes
test-sha1.sh -rwxr-xr-x 1.9 KB
test-sigchain.c -rw-r--r-- 344 bytes
thread-utils.c -rw-r--r-- 965 bytes
thread-utils.h -rw-r--r-- 109 bytes
trace.c -rw-r--r-- 3.5 KB
transport-helper.c -rw-r--r-- 17.4 KB
transport.c -rw-r--r-- 29.3 KB
transport.h -rw-r--r-- 4.7 KB
tree-diff.c -rw-r--r-- 11.9 KB
tree-walk.c -rw-r--r-- 10.1 KB
tree-walk.h -rw-r--r-- 1.7 KB
tree.c -rw-r--r-- 7.0 KB
tree.h -rw-r--r-- 883 bytes
unimplemented.sh -rw-r--r-- 100 bytes
unpack-trees.c -rw-r--r-- 35.7 KB
unpack-trees.h -rw-r--r-- 1.6 KB
upload-pack.c -rw-r--r-- 17.5 KB
usage.c -rw-r--r-- 2.4 KB
userdiff.c -rw-r--r-- 6.0 KB
userdiff.h -rw-r--r-- 477 bytes
utf8.c -rw-r--r-- 13.0 KB
utf8.h -rw-r--r-- 613 bytes
walker.c -rw-r--r-- 7.2 KB
walker.h -rw-r--r-- 1.1 KB
wrap-for-bin.sh -rw-r--r-- 526 bytes
wrapper.c -rw-r--r-- 6.3 KB
write_or_die.c -rw-r--r-- 2.0 KB
ws.c -rw-r--r-- 8.2 KB
wt-status.c -rw-r--r-- 18.7 KB
wt-status.h -rw-r--r-- 1.3 KB
xdiff-interface.c -rw-r--r-- 7.9 KB
xdiff-interface.h -rw-r--r-- 1.1 KB

README

back to top