Commit Graph

210 Commits

Author SHA1 Message Date
Junio C Hamano
9914cf4689 xdl_merge(): allow passing down marker_size in xmparam_t
This allows the callers of xdl_merge() to pass marker_size (defaults to 7)
in xmparam_t argument, to use conflict markers of non-default length.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
2010-01-16 23:45:29 -08:00
Junio C Hamano
00f8f97d30 xdl_merge(): introduce xmparam_t for merge specific parameters
So far we have only needed to be able to pass an option that is generic to
xdiff family of functions to this function.  Extend the interface so that
we can give it merge specific parameters.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
2010-01-16 21:33:13 -08:00
Junio C Hamano
73eb40eeaa git-merge-file --ours, --theirs
Sometimes people want their conflicting merges autoresolved by
favouring upstream changes.  The standard answer they are given is
to run "git diff --name-only | xargs git checkout MERGE_HEAD --" in
such a case.  This is to accept automerge results for the paths that
are fully resolved automatically, while taking their version of the
file in full for paths that have conflicts.

This is problematic on two counts.

One is that this is not exactly what these people want.  It discards
all changes they did on their branch for any paths that conflicted.
They usually want to salvage as much automerge result as possible in
a conflicted file, and want to take the upstream change only in the
conflicted part.

This patch teaches two new modes of operation to the lowest-lever
merge machinery, xdl_merge().  Instead of leaving the conflicted
lines from both sides enclosed in <<<, ===, and >>> markers, the
conflicts are resolved favouring our side or their side of changes.

A larger problem is that this tends to encourage a bad workflow by
allowing people to record such a mixed up half-merged result as a
full commit without auditing.  This commit does not tackle this
issue at all.  In git, we usually give long enough rope to users
with strange wishes as long as the risky features are not enabled by
default, and this is such a risky feature.

Signed-off-by: Avery Pennarun <apenwarr@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
2009-11-29 23:11:46 -08:00
Junio C Hamano
d34eca0392 Merge branch 'tf/diff-whitespace-incomplete-line'
* tf/diff-whitespace-incomplete-line:
  xutils: Fix xdl_recmatch() on incomplete lines
  xutils: Fix hashing an incomplete line with whitespaces at the end
2009-08-31 22:08:57 -07:00
Junio C Hamano
3b5ef0e216 xutils: Fix xdl_recmatch() on incomplete lines
Thell Fowler noticed that various "ignore whitespace" options to git diff
do not work well on an incomplete line.

The loop control of the function responsible for these bugs was extremely
difficult to follow.  This patch restructures the loops for three variants
of "ignore whitespace" logic.

The basic idea of the re-written logic is:

 - A loop runs while the characters from both strings we are looking at
   match.  We declare unmatch immediately when we find something that does
   not match and return false from the function.  We break out of the loop
   if we ran out of either side of the string.

   The way we skip spaces inside this loop varies depending on the style
   of ignoring whitespaces.

 - After the above loop breaks, we know that the parts of the strings we
   inspected so far match, ignoring the whitespaces.  The lines can match
   only if the remainder consists of nothing but whitespaces.  This part
   of the logic is shared across all three styles.

The new code is more obvious and should be much easier to follow.

Tested-by: Thell Fowler <git@tbfowler.name>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
2009-08-23 14:38:43 -07:00
Junio C Hamano
78ed710fcf xutils: Fix hashing an incomplete line with whitespaces at the end
Upon seeing a whitespace, xdl_hash_record_with_whitespace() first skipped
the run of whitespaces (excluding LF) that begins there, ensuring that the
pointer points at the last whitespace character in the run, and assumed
that the next character must be LF at the end of the line.  This does not
work when hashing an incomplete line, which lacks the LF at the end.

Introduce "at_eol" variable that is true when either we are at the end of
line (looking at LF) or at the end of an incomplete line, and use that
instead throughout the code.

Noticed by Thell Fowler.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
2009-08-23 13:17:59 -07:00
Pierre Habouzit
f630cfda88 refactor: use bitsizeof() instead of 8 * sizeof()
Signed-off-by: Pierre Habouzit <madcoder@debian.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
2009-07-22 21:57:41 -07:00
Junio C Hamano
456cb4cf3e Merge branch 'cb/maint-1.6.0-xdl-merge-fix' into maint
* cb/maint-1.6.0-xdl-merge-fix:
  Change xdl_merge to generate output even for null merges
  t6023: merge-file fails to output anything for a degenerate merge

Conflicts:
	xdiff/xmerge.c
2009-06-02 07:48:44 -07:00
Charles Bailey
5719db91ce Change xdl_merge to generate output even for null merges
xdl_merge used to have a check to ensure that there was at least
some change in one or other side being merged but this suppressed
output for the degenerate case when base, local and remote
contents were all identical.

Removing this check enables correct output in the degenerate case
and xdl_free_script handles freeing NULL scripts so there is no
need to have the check for these calls.

Signed-off-by: Charles Bailey <charles@hashpling.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
2009-05-24 23:56:34 -07:00
Mike Ralphson
3ea3c215c0 Fix typos / spelling in comments
Signed-off-by: Mike Ralphson <mike@abacus.co.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
2009-04-22 19:02:12 -07:00
Benjamin Kramer
8e24cbaeaf Fix various dead stores found by the clang static analyzer
http-push.c::finish_request():
  request is initialized by the for loop

index-pack.c::free_base_data():
  b is initialized by the for loop

merge-recursive.c::process_renames():
  move compare to narrower scope, and remove unused assignments to it
  remove unused variable renames2

xdiff/xdiffi.c::xdl_recs_cmp():
  remove unused variable ec

xdiff/xemit.c::xdl_emit_diff():
  xche is always overwritten

Signed-off-by: Benjamin Kramer <benny.kra@googlemail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
2009-03-15 18:25:24 -07:00
Junio C Hamano
8c4c286c39 Merge branch 'kc/maint-diff-bwi-fix' into maint
* kc/maint-diff-bwi-fix:
  Fix combined use of whitespace ignore options to diff
  test more combinations of ignore-whitespace options to diff
2009-02-05 17:52:22 -08:00
Junio C Hamano
5dc1308562 Merge branch 'js/patience-diff'
* js/patience-diff:
  bash completions: Add the --patience option
  Introduce the diff option '--patience'
  Implement the patience diff algorithm

Conflicts:
	contrib/completion/git-completion.bash
2009-01-23 21:51:38 -08:00
Junio C Hamano
9a01387b97 Merge branch 'kc/maint-diff-bwi-fix'
* kc/maint-diff-bwi-fix:
  Fix combined use of whitespace ignore options to diff
2009-01-21 17:07:51 -08:00
Keith Cascio
6d12acefd5 Fix combined use of whitespace ignore options to diff
The code used to misbehave when options to ignore certain whitespaces
(-w -b and --ignore-at-eol) were combined.

Signed-off-by: Keith Cascio <keith@cs.ucla.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
2009-01-19 21:21:58 -08:00
Johannes Schindelin
92b7de93fb Implement the patience diff algorithm
The patience diff algorithm produces slightly more intuitive output
than the classic Myers algorithm, as it does not try to minimize the
number of +/- lines first, but tries to preserve the lines that are
unique.

To this end, it first determines lines that are unique in both files,
then the maximal sequence which preserves the order (relative to both
files) is extracted.

Starting from this initial set of common lines, the rest of the lines
is handled recursively, with Myers' algorithm as a fallback when
the patience algorithm fails (due to no common unique lines).

This patch includes memory leak fixes by Pierre Habouzit.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
2009-01-07 13:35:44 -08:00
René Scharfe
6d0e674a57 diff: add option to show context between close hunks
Merge two hunks if there is only the specified number of otherwise unshown
context between them.  For --inter-hunk-context=1, the resulting patch has
the same number of lines but shows uninterrupted context instead of a
context header line in between.

Patches generated with this option are easier to read but are also more
likely to conflict if the file to be patched contains other changes.

This patch keeps the default for this option at 0.  It is intended to just
make the feature available in order to see its advantages and downsides.

Signed-off-by: Rene Scharfe <rene.scharfe@lsrfire.ath.cx>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
2008-12-29 01:05:21 -08:00
Davide Libenzi
733070bea9 xdiff: give up scanning similar lines early
In a corner case of large files whose lines do not match uniquely, the
loop to eliminate a line that matches multiple locations adjacent to a run
of lines that do not uniquely match wasted too much cycles.  Fix this by
giving up early after scanning 100 lines in both direction.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
2008-12-02 23:45:37 -08:00
Junio C Hamano
ac2abb49ce Merge branch 'dl/xdiff'
* dl/xdiff:
  xdiff: give up scanning similar lines early
2008-11-12 21:51:30 -08:00
Davide Libenzi
9b28d55401 xdiff: give up scanning similar lines early
In a corner case of large files whose lines do not match uniquely, the
loop to eliminate a line that matches multiple locations adjacent to a run
of lines that do not uniquely match wasted too much cycles.  Fix this by
giving up early after scanning 100 lines in both direction.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
2008-11-08 09:28:30 -08:00
Brian Downing
ef2e62fe23 Allow alternate "low-level" emit function from xdl_diff
For some users (e.g. git blame), getting textual patch output is just
extra work, as they can get all the information they need from the low-
level diff structures.  Allow for an alternate low-level emit function
to be defined to allow bypassing the textual patch generation; set
xemitconf_t's emit_func member to enable this.

The (void (*)()) type is pretty ugly, but the alternative would be to
include most of the private xdiff headers in xdiff.h to get the types
required for the "proper" function prototype.  Also, a (void *) won't
work, as ANSI C doesn't allow a function pointer to be cast to an
object pointer.

Signed-off-by: Brian Downing <bdowning@lavos.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
2008-10-25 12:09:31 -07:00
Junio C Hamano
83133740d9 xmerge.c: "diff3 -m" style clips merge reduction level to EAGER or less
When showing a conflicting merge result, and "--diff3 -m" style is asked
for, this patch makes sure that the merge reduction level does not exceed
XDL_MERGE_EAGER.  This is because "diff3 -m" style output would not make
sense for anything more aggressive than XDL_MERGE_EAGER, because of the
way how the merge reduction works.

"git merge-file" no longer has to force MERGE_EAGER when "--diff3" is
asked for because of this change.

Suppose a common ancestor (shared preimage) is modified to postimage #1
and #2 (each letter represents one line):

                     #####
    postimage#1: 1234ABCDE789
                    |    /
                    |   /
    preimage:    123456789
                    |   \
    postimage#2: 1234AXYE789
                     ####

XDL_MERGE_MINIMAL and XDL_MERGE_EAGER would:

 (1) find the s/56/ABCDE/ done on one side and s/56/AXYE/ done on the
     other side,

 (2) notice that they touch an overlapping area, and

 (3) mark it as a conflict, "ABCDE vs AXYE".

The difference between the two algorithms is that EAGER drops the hunk
altogether if the postimages match (i.e. both sides modified the same
way), while MINIMAL keeps it.  There is no other operation performed to
the hunk.  As the result, lines marked with "#" in the above picure will
be in the RCS merge style output like this (letters <, = and > represent
conflict marker lines):

    output:      1234<ABCDE=AXYE>789    ; with MINIMAL/EAGER

The part from the preimage that corresponds to these conflicting changes
is "56", which is what "diff3 -m" style output adds to it:

    output:      1234<ABCDE|56=AXYE>789 ; in "diff3 -m" style

Now, XDL_MERGE_ZEALOUS looks at the differences between the changes two
postimages made in order to reduce the number of lines in the conflicting
regions.  It notices that both sides start their new contents with "A",
and excludes it from the output (it also excludes "E" for the same
reason).  The conflict that used to be "ABCDE vs AXYE" is now "BCD vs XY":

    output:      1234A<BCD=XY>E789      ; with ZEALOUS

There could even be matching parts between two postimages in the middle.
Instead of one side rewriting the shared "56" to "ABCDE" and the other
side to "AXYE", imagine the case where the postimages are "ABCDE" and
"AXCYE", in which case instead of having one conflicted hunk "BCD vs XY",
you would have two conflicting hunks "B vs X" and "D vs Y".

In either case, once you reduce "ABCDE vs AXYE" to "BCD vs XY" (or "ABCDE
vs AXCYE" to "B vs X" and "D vs Y"), there is no part from the preimage
that corresponds to the conflicting change made in both postimages
anymore.  In other words, conflict reduced by ZEALOUS algorithm cannot be
expressed in "diff3 -m" style.  Representing the last illustration like
this is misleading to say the least:

    output:      1234A<BCD|56=XY>E789   ; broken "diff3 -m" style

because the preimage was not ...4A56E... to begin with.  "A" and "E" are
common only between the postimages.

Even worse, once a single conflicting hunk is split into multiple ones
(recall the example of breaking "ABCDE vs AXCYE" to "B vs X" and "D vs
Y"), there is no sane way to distribute the preimage text across split
conflicting hunks.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
2008-08-30 19:41:43 -07:00
Junio C Hamano
838338cd22 xmerge.c: minimum readability fixups
This replaces hardcoded magic constants with symbolic ones for
readability, and swaps one if/else blocks to better match the
order in which 0/1/2 variables are handled to nearby codepath.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
2008-08-30 19:41:43 -07:00
Junio C Hamano
e0af48e496 xdiff-merge: optionally show conflicts in "diff3 -m" style
When showing conflicting merges, we traditionally followed RCS's merge
output format.  The output shows:

 <<<<<<<
 postimage from one side;
 =======
 postimage of the other side; and
 >>>>>>>

Some poeple find it easier to be able to understand what is going on when
they can view the common ancestor's version, which is used by "diff3 -m",
which shows:

 <<<<<<<
 postimage from one side;
 |||||||
 shared preimage;
 =======
 postimage of the other side; and
 >>>>>>>

This is an initial step to bring that as an optional feature to git.
Only "git merge-file" has been converted, with "--diff3" option.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
2008-08-30 19:41:43 -07:00
Junio C Hamano
f2b25dd81f xdl_fill_merge_buffer(): separate out a too deeply nested function
This simply moves code around to make a separate function that prepares
a single conflicted hunk with markers into the buffer.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
2008-08-30 19:41:43 -07:00
Johannes Schindelin
ee95ec5d58 xdl_merge(): introduce XDL_MERGE_ZEALOUS_ALNUM
When a merge conflicts, there are often common lines that are not really
common, such as empty lines or lines containing a single curly bracket.

With XDL_MERGE_ZEALOUS_ALNUM, we use the following heuristics: when a
hunk does not contain any letters or digits, it is treated as conflicting.

In other words, a conflict which used to look like this:

	<<<<<<<
					a = 1;
	=======
					output();
	>>>>>>>
				}
			}
		}

	<<<<<<<
		output();
	=======
		b = 1;
	>>>>>>>

will look like this with ZEALOUS_ALNUM:

	<<<<<<<
					a = 1;
				}
			}
		}

		output();
	=======
					output();
				}
			}
		}

		b = 1;
	>>>>>>>

To demonstrate this, git-merge-file has been switched from
XDL_MERGE_ZEALOUS to XDL_MERGE_ZEALOUS_ALNUM.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
2008-02-18 00:10:37 -08:00
Johannes Schindelin
f407f14dea xdl_merge(): make XDL_MERGE_ZEALOUS output simpler
When a merge conflicts, there are often less than three common lines
between two conflicting regions.

Since a conflict takes up as many lines as are conflicting, plus three
lines for the commit markers,  the output will be shorter (and thus,
simpler) in this case, if the common lines will be merged into the
conflicting regions.

This patch merges up to three common lines into the conflicts.

For example, what looked like this before this patch:

	<<<<<<<
	if (a == 1)
	=======
	if (a != 0)
	>>>>>>>
	{
		int i;
	<<<<<<<
		a = 0;
	=======
		a = !a;
	>>>>>>>

will now look like this:

	<<<<<<<
	if (a == 1)
	{
		int i;
		a = 0;
	=======
	if (a != 0)
	{
		int i;
		a = !a;
	>>>>>>>

Suggested Linus (based on ideas by "Voltage Spike" -- if that name is
real, it is mighty cool).

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
2008-02-18 00:08:40 -08:00
Guido Ostkamp
a777e9ca54 Remove unreachable statements
Solaris Workshop Compiler found a few unreachable statements.

Signed-off-by: Guido Ostkamp <git@ostkamp.fastmail.fm>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-11-15 21:23:47 -08:00
Junio C Hamano
f258475a6e Per-path attribute based hunk header selection.
This makes"diff -p" hunk headers customizable via gitattributes mechanism.
It is based on Johannes's earlier patch that allowed to define a single
regexp to be used for everything.

The mechanism to arrive at the regexp that is used to define hunk header
is the same as other use of gitattributes.  You assign an attribute, funcname
(because "diff -p" typically uses the name of the function the patch is about
as the hunk header), a simple string value.  This can be one of the names of
built-in pattern (currently, "java" is defined) or a custom pattern name, to
be looked up from the configuration file.

  (in .gitattributes)
  *.java   funcname=java
  *.perl   funcname=perl

  (in .git/config)
  [funcname]
    java = ... # ugly and complicated regexp to override the built-in one.
    perl = ... # another ugly and complicated regexp to define a new one.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-07-06 01:20:47 -07:00
Pierre Habouzit
52fae7de4e Missing statics.
Signed-off-by: Pierre Habouzit <madcoder@debian.org>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-06-08 02:37:19 -07:00
Junio C Hamano
a6080a0a44 War on whitespace
This uses "git-apply --whitespace=strip" to fix whitespace errors that have
crept in to our source files over time.  There are a few files that need
to have trailing whitespaces (most notably, test vectors).  The results
still passes the test, and build result in Documentation/ area is unchanged.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
2007-06-07 00:04:01 -07:00
Johannes Schindelin
824f782c3f xdiff/xutils.c(xdl_hash_record): factor out whitespace handling
Since in at least one use case, xdl_hash_record() takes over 15% of the
CPU time, it makes sense to even micro-optimize it. For many cases, no
whitespace special handling is needed, and in these cases we should not
even bother to check for whitespace in _every_ iteration of the loop.

Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Signed-off-by: Junio C Hamano <junkio@cox.net>
2007-03-19 22:17:25 -07:00
Johannes Schindelin
859f9c4581 teach diff machinery about --ignore-space-at-eol
`git diff --ignore-space-at-eol` will ignore whitespace at the
line ends.

Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Signed-off-by: Junio C Hamano <junkio@cox.net>
2007-02-13 21:40:42 -08:00
Johannes Schindelin
22b6abcd08 Fix yet another subtle xdl_merge() bug
In very obscure cases, a merge can hit an unexpected code path (where the
original code went as far as saying that this was a bug). This failing
merge was noticed by Alexandre Juillard.

The problem is that the original file contains something like this:

-- snip --
two non-empty lines
before two empty lines

after two empty lines
-- snap --

and this snippet is reduced to _one_ empty line in _both_ new files.
However, it is ambiguous as to which hunk takes the empty line: the first
or the second one?

Indeed in Alexandre's example files, the xdiff algorithm attributes the
empty line to the first hunk in one case, and to the second hunk in the
other case.

(Trimming down the example files _changes_ that behaviour!)

Thus, the call to xdl_merge_cmp_lines() has no chance to realize that the
change is actually identical in both new files. Therefore,
xdl_refine_conflicts() finds an empty diff script, which was not expected
there, because (the original author of xdl_merge() thought)
xdl_merge_cmp_lines() would catch that case earlier.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-12-30 18:05:05 -08:00
Johannes Schindelin
5d6b151fdd xdl_merge(): fix a segmentation fault when refining conflicts
The function xdl_refine_conflicts() tries to break down huge
conflicts by doing a diff on the conflicting regions. However,
this does not make sense when one side is empty.

Worse, when one side is not only empty, but after EOF, the code
accessed unmapped memory.

Noticed by Luben Tuikov, Shawn Pearce and Alexandre Julliard, the
latter providing a test case.

Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-12-28 13:59:39 -08:00
Junio C Hamano
8042ed1ceb Merge branch 'master' into js/merge
* master: (42 commits)
  git-svn: correctly handle packed-refs in refs/remotes/
  add test case for recursive merge
  git-svn: correctly display fatal() error messages
  git-svn: allow dcommit to take an alternate head
  git-svn: enable logging of information not supported by git
  Clarify fetch error for missing objects.
  Move Fink and Ports check to after config file
  shortlog: fix segfault on empty authorname
  shortlog: remove "[PATCH]" prefix from shortlog output
  Make sure the empty tree exists when needed in merge-recursive.
  Don't use memcpy when source and dest. buffers may overlap
  no need to install manpages as executable
  Documentation: simpler shared repository creation
  shortlog: fix segfault on empty authorname
  Add branch.*.merge warning and documentation update
  Fix perl/ build.
  git-svn: use do_switch for --follow-parent if the SVN library supports it
  Fix documentation copy&paste typo
  git-svn: extra error check to ensure we open a file correctly
  Documentation: update git-clone man page with new behavior
  ...
2006-12-12 21:52:19 -08:00
Johannes Schindelin
98e6da8a36 xdl_merge(): fix and simplify conflict handling
Suppose you have changes in new1 to the original lines 10-20,
and changes in new2 to the original lines 15-25, then the
changes to 10-25 conflict. But it is possible that the next
changes in new1 still overlap with this change to new2.

So, in the next iteration we have to look at the same change
to new2 again.

The old code tried to be a bit too clever. The new code is
shorter and more to the point: do not fiddle with the ranges
at all.

Also, xdl_append_merge() tries harder to combine conflicts.
This is necessary, because with the above simplification,
some conflicts would not be recognized as conflicts otherwise:

In the above scenario, it is possible that there is no other
change to new1. Absent the combine logic, the change in new2
would be recorded _again_, but as a non-conflict.

Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>
2006-12-05 13:30:22 -08:00
Johannes Schindelin
c7c24889bb diff -b: ignore whitespace at end of line
This is _not_ the same as "treat eol as whitespace", since that would mean
that multiple empty lines would be treated as equal to e.g. a space.

Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-12-04 16:30:54 -08:00
Johannes Schindelin
710daa83fc xdl_merge(): fix thinko
If one side's block (of changed lines) ends later than the other
side's block, the former should be tested against the next block
of the other side, not vice versa.

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-12-02 17:28:19 -08:00
Johannes Schindelin
875b8ce476 xdl_merge(): fix an off-by-one bug
The line range is i1 .. (i1 + chg1 - 1), not i1 .. (i1 + chg1).

Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-12-02 17:28:19 -08:00
Junio C Hamano
53a7085a10 xmerge: make return value from xdl_merge() more usable.
The callers would want to know if the resulting merge is clean;
do not discard that information away after calling xdl_do_merge().

Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-12-02 17:28:19 -08:00
Johannes Schindelin
857b933e04 xdiff: add xdl_merge()
This new function implements the functionality of RCS merge, but
in-memory. It returns < 0 on error, otherwise the number of conflicts.

Finding the conflicting lines can be a very expensive task. You can
control the eagerness of this algorithm:

- a level value of 0 means that all overlapping changes are treated
  as conflicts,
- a value of 1 means that if the overlapping changes are identical,
  it is not treated as a conflict.
- If you set level to 2, overlapping changes will be analyzed, so that
  almost identical changes will not result in huge conflicts. Rather,
  only the conflicting lines will be shown inside conflict markers.

With each increasing level, the algorithm gets slower, but more accurate.
Note that the code for level 2 depends on the simple definition of
mmfile_t specific to git, and therefore it will be harder to port that
to LibXDiff.

Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-12-02 17:28:19 -08:00
Andy Parkins
f73da29fa2 Increase length of function name buffer
In xemit.c:xdl_emit_diff() a buffer for showing the function name as
commentary is allocated; this buffer was 40 characters.  This is a bit
small; particularly for C++ function names where there is often an
identical prefix (like void LongNamespace::LongClassName) on multiple
functions, which makes the context the same everywhere.  In other words
the context is useless.  This patch increases that buffer to 80
characters - which may still not be enough, but is better

Signed-off-by: Andy Parkins <andyparkins@gmail.com>
Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-11-23 22:51:41 -08:00
Petr Baudis
70da769a46 xdiff: Match GNU diff behaviour when deciding hunk comment worthiness of lines
This removes the '#' and '(' tests and adds a '$' test instead although I have
no idea what it is actually good for - but hey, if that's what GNU diff does...

Pasky only went and did as Junio sayeth.

Signed-off-by: Petr Baudis <pasky@suse.cz>
Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-10-25 12:57:33 -07:00
Jim Meyering
67aef03455 xdiff/xemit.c (xdl_find_func): Elide trailing white space in a context header.
This removes trailing blanks from git-generated diff headers
the same way a similar patch did that for GNU diff:

  http://article.gmane.org/gmane.comp.gnu.utils.bugs/13839

That is, it removes trailing blanks on the hunk header line that
shows the function name.

Signed-off-by: Jim Meyering <jim@meyering.net>
Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-10-23 14:33:54 -07:00
Junio C Hamano
3453f862e1 Merge branch 'maint'
* maint:
  Fix hash function in xdiff library
2006-10-16 21:58:54 -07:00
Linus Torvalds
9de0834663 Fix hash function in xdiff library
Jim Mayering noticed that xdiff library took insanely long time
when comparing files with many identical lines.

This was because the hash function used in the library is broken
on 64-bit architectures and caused too many collisions.

http://thread.gmane.org/gmane.comp.version-control.git/28962/focus=28994

Acked-by: Davide Libenzi <davidel@xmaliserver.org>
Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-10-16 21:27:44 -07:00
Johannes Schindelin
2344d47fba diff: fix 2 whitespace issues
When whitespace or whitespace change was ignored, the function
xdl_recmatch() returned memcmp() style differences, which is wrong,
since it should return 0 on non-match.

Also, there were three horrible off-by-one bugs, even leading to wrong
hashes in the whitespace special handling.

The issue was noticed by Ray Lehtiniemi.

For good measure, this commit adds a test.

Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-10-12 09:30:14 -07:00
Junio C Hamano
096b173234 Merge branch 'lt/merge-tree'
* lt/merge-tree:
  Improved three-way blob merging code
  Prepare "git-merge-tree" for future work
  xdiff: generate "anti-diffs" aka what is common to two files
2006-07-12 22:31:22 -07:00
Pavel Roskin
82e5a82fd7 Fix more typos, primarily in the code
The only visible change is that git-blame doesn't understand
"--compability" anymore, but it does accept "--compatibility" instead,
which is already documented.

Signed-off-by: Pavel Roskin <proski@gnu.org>
Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-07-10 00:36:44 -07:00
Linus Torvalds
a9ed376b15 xdiff: generate "anti-diffs" aka what is common to two files
This fairly trivial patch adds a new XDL_EMIT_xxx flag to tell libxdiff
that we don't want to generate the _diff_ between two files, we want to
see the lines that are _common_ to two files.

So when you set XDL_EMIT_COMMON, xdl_diff() will do everything exactly
like it used to do, but the output records it generates just contain the
lines that aren't part of the diff.

This is for doing things like generating the common base case for a file
that was added in both branches.

Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-06-28 22:24:32 -07:00
Johannes Schindelin
0d21efa51c Teach diff about -b and -w flags
This adds -b (--ignore-space-change) and -w (--ignore-all-space) flags to
diff. The main part of the patch is teaching libxdiff about it.

[jc: renamed xdl_line_match() to xdl_recmatch() since the former is used
 for different purposes in xpatchi.c which is in the parts of the upstream
 source we do not use.]

Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-06-23 17:35:27 -07:00
Junio C Hamano
d281786fcd xdiff: minor changes to match libxdiff-0.21
This reformats the change 621c53cc08
introduced to match what upstream author implemented in libxdiff-0.21
without changing any logic (hopefully ;-).  This is to help keep
us in sync with the upstream.

Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-06-19 18:43:49 -07:00
Davide Libenzi
295ba2fb89 xdiff: post-process hunks to make them consistent. 2006-04-13 16:48:45 -07:00
Marco Roeland
0ed49a3ed9 xdiff/xdiffi.c: fix warnings about possibly uninitialized variables
Compiling this module gave the following warnings (some double dutch!):

xdiff/xdiffi.c: In functie 'xdl_recs_cmp':
xdiff/xdiffi.c:298: let op: 'spl.i1' may be used uninitialized in this function
xdiff/xdiffi.c:298: let op: 'spl.i2' may be used uninitialized in this function
xdiff/xdiffi.c:219: let op: 'fbest1' may be used uninitialized in this function
xdiff/xdiffi.c:219: let op: 'bbest1' may be used uninitialized in this function

A superficial tracking of their usage, without deeper knowledge about the
algorithm, indeed confirms that there are code paths on which these
variables will be used uninitialized. In practice these code paths might never
be reached, but then these fixes will not change the algorithm. If these
code paths are ever reached we now at least have a predictable outcome. And
should the very small performance impact of these initializations be
noticeable, then they should at least be replaced by comments why certain
code paths will never be reached.

Some extra initializations in this patch now fix the warnings.
2006-04-08 23:35:22 -07:00
Davide Libenzi
ca557afff9 Clean-up trivially redundant diff.
Also corrects the line numbers in unified output when using
zero lines context.
2006-04-04 00:11:09 -07:00
Mark Wooding
acb7257729 xdiff: Show function names in hunk headers.
The speed of the built-in diff generator is nice; but the function names
shown by `diff -p' are /really/ nice.  And I hate having to choose.  So,
we hack xdiff to find the function names and print them.

xdiff has grown a flag to say whether to dig up the function names.  The
builtin_diff function passes this flag unconditionally.  I suppose it
could parse GIT_DIFF_OPTS, but it doesn't at the moment.  I've also
reintroduced the `function name' into the test suite, from which it was
removed in commit 3ce8f089.

The function names are parsed by a particularly stupid algorithm at the
moment: it just tries to find a line in the `old' file, from before the
start of the hunk, whose first character looks plausible.  Still, it's
most definitely a start.

Signed-off-by: Mark Wooding <mdw@distorted.org.uk>
Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-03-27 18:43:51 -08:00
Junio C Hamano
3ce8f08944 built-in diff: minimum tweaks
This fixes up a couple of minor issues with the real built-in
diff to be more usable:

 - Omit ---/+++ header unless we emit diff output;

 - Detect and punt binary diff like GNU does;

 - Honor GIT_DIFF_OPTS minimally (only -u<number> and
   --unified=<number> are currently supported);

 - Omit line count of 1 from "@@ -l,k +m,n @@" hunk header
   (i.e. when k == 1 or n == 1)

 - Adjust testsuite for the lack of -p support.

Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-03-25 16:50:00 -08:00
Linus Torvalds
621c53cc08 builtin-diff: \No newline at end of file.
Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-03-25 16:49:59 -08:00
Linus Torvalds
3443546f6e Use a *real* built-in diff generator
This uses a simplified libxdiff setup to generate unified diffs _without_
doing  fork/execve of GNU "diff".

This has several huge advantages, for example:

Before:

	[torvalds@g5 linux]$ time git diff v2.6.16.. > /dev/null

	real    0m24.818s
	user    0m13.332s
	sys     0m8.664s

After:

	[torvalds@g5 linux]$ time git diff v2.6.16.. > /dev/null

	real    0m4.563s
	user    0m2.944s
	sys     0m1.580s

and the fact that this should be a lot more portable (ie we can ignore all
the issues with doing fork/execve under Windows).

Perhaps even more importantly, this allows us to do diffs without actually
ever writing out the git file contents to a temporary file (and without
any of the shell quoting issues on filenames etc etc).

NOTE! THIS PATCH DOES NOT DO THAT OPTIMIZATION YET! I was lazy, and the
current "diff-core" code actually will always write the temp-files,
because it used to be something that you simply had to do. So this current
one actually writes a temp-file like before, and then reads it into memory
again just to do the diff. Stupid.

But if this basic infrastructure is accepted, we can start switching over
diff-core to not write temp-files, which should speed things up even
further, especially when doing big tree-to-tree diffs.

Now, in the interest of full disclosure, I should also point out a few
downsides:

 - the libxdiff algorithm is different, and I bet GNU diff has gotten a
   lot more testing. And the thing is, generating a diff is not an exact
   science - you can get two different diffs (and you will), and they can
   both be perfectly valid. So it's not possible to "validate" the
   libxdiff output by just comparing it against GNU diff.

 - GNU diff does some nice eye-candy, like trying to figure out what the
   last function was, and adding that information to the "@@ .." line.
   libxdiff doesn't do that.

 - The libxdiff thing has some known deficiencies. In particular, it gets
   the "\No newline at end of file" case wrong. So this is currently for
   the experimental branch only. I hope Davide will help fix it.

That said, I think the huge performance advantage, and the fact that it
integrates better is definitely worth it. But it should go into a
development branch at least due to the missing newline issue.

Technical note: this is based on libxdiff-0.17, but I did some surgery to
get rid of the extraneous fat - stuff that git doesn't need, and seriously
cutting down on mmfile_t, which had much more capabilities than the diff
algorithm either needed or used. In this version, "mmfile_t" is just a
trivial <pointer,length> tuple.

That said, I tried to keep the differences to simple removals, so that you
can do a diff between this and the libxdiff origin, and you'll basically
see just things getting deleted. Even the mmfile_t simplifications are
left in a state where the diffs should be readable.

Apologies to Davide, whom I'd love to get feedback on this all from (I
wrote my own "fill_mmfile()" for the new simpler mmfile_t format: the old
complex format had a helper function for that, but I did my surgery with
the goal in mind that eventually we _should_ just do

	mmfile_t mf;

	buf = read_sha1_file(sha1, type, &size);
	mf->ptr = buf;
	mf->size = size;
	.. use "mf" directly ..

which was really a nightmare with the old "helpful" mmfile_t, and really
is that easy with the new cut-down interfaces).

[ Btw, as any hawk-eye can see from the diff, this was actually generated
  with itself, so it is "self-hosting". That's about all the testing it
  has gotten, along with the above kernel diff, which eye-balls correctly,
  but shows the newline issue when you double-check it with "git-apply" ]

Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Signed-off-by: Junio C Hamano <junkio@cox.net>
2006-03-25 16:49:58 -08:00