This is an archive of the discontinued Mercurial Phabricator instance.

Differential D2573

xdiff: remove patience and histogram diff algorithms
ClosedPublic

Authored by ryanmce on Mar 2 2018, 7:25 PM.

Details

Reviewers
indygreg
durin42
Group Reviewers
hg-reviewers
Commits
rHG9e7b14caf67f: xdiff: remove patience and histogram diff algorithms
rHG3ee9ca23dad0: xdiff: remove patience and histogram diff algorithms
Summary

Patience diff is the normal diff algorithm, plus some greediness that
unconditionally matches common common unique lines. That means it is easy to
construct cases to let it generate suboptimal result, like:

open('a', 'w').write('\n'.join(list('a' + 'x' * 300 + 'u' + 'x' * 700 + 'a\n')))
open('b', 'w').write('\n'.join(list('b' + 'x' * 700 + 'u' + 'x' * 300 + 'b\n')))

Patience diff has been advertised as being able to generate better results for
some C code changes. However, the more scientific way to do that is the
indention heuristic [1].

Since patience diff could generate suboptimal result more easily and its
"better" diff feature could be replaced by the new indention heuristic, let's
just remove it and its variant histogram diff to simplify the code.

[1]: https://github.com/git/git/commit/433860f3d0beb0c6f205290bd16cda413148f098

Test Plan

gcc -fPIC *.c --shared -o xdiff.so still builds.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

ryanmce created this revision.Mar 2 2018, 7:25 PM
quark edited the summary of this revision. (Show Details)Mar 3 2018, 3:07 PM
quark retitled this revision from xdiff: remove patience and histogram diffs to xdiff: remove patience and histogram diff algorithms.
quark updated this revision to Diff 6456.
quark updated this revision to Diff 6473.Mar 3 2018, 3:30 PM
indygreg accepted this revision as: indygreg.Mar 3 2018, 3:50 PM
indygreg added a subscriber: indygreg.

I'm leaning towards keeping these algorithms so we can expose them as alternate implementations in the future. It will also making syncing code from upstream easier. But removing the unused-by-us code is fine.

quark added a subscriber: quark.Mar 3 2018, 4:21 PM

Googling "patience diff", most results will say it is slower but has better diff quality sometimes.

That is very misleading - the algorithm adds greediness (i.e. incorrectness) and is in theory faster in some cases. The "better" quality is also untrue comparing to indent heuristic.

Technically, I don't think it's worthwhile to keep - definitely worse quality and unpredictable performance changes comparing to default diff + indent heuristic setup.

From a non-technical point of view, I think educating people that they cannot be misled is very important. This one alone is an enough reason to do the cleanup, imo.

durin42 accepted this revision.Mar 3 2018, 6:11 PM
This revision is now accepted and ready to land.Mar 3 2018, 6:11 PM
Closed by commit rHG3ee9ca23dad0: xdiff: remove patience and histogram diff algorithms (authored by quark). · Explain WhyMar 3 2018, 6:40 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 6512

mercurial/thirdparty/xdiff/xdiff.h

#if !defined(XDIFF_H) #if !defined(XDIFF_H)
#define XDIFF_H #define XDIFF_H
#ifdef __cplusplus #ifdef __cplusplus
extern "C" { extern "C" {
#endif /* #ifdef __cplusplus */ #endif /* #ifdef __cplusplus */
#include <stddef.h> /* size_t */
/* xpparm_t.flags */ /* xpparm_t.flags */
#define XDF_NEED_MINIMAL (1 << 0) #define XDF_NEED_MINIMAL (1 << 0)
#define XDF_IGNORE_WHITESPACE (1 << 1) #define XDF_IGNORE_WHITESPACE (1 << 1)
#define XDF_IGNORE_WHITESPACE_CHANGE (1 << 2) #define XDF_IGNORE_WHITESPACE_CHANGE (1 << 2)
#define XDF_IGNORE_WHITESPACE_AT_EOL (1 << 3) #define XDF_IGNORE_WHITESPACE_AT_EOL (1 << 3)
#define XDF_IGNORE_CR_AT_EOL (1 << 4) #define XDF_IGNORE_CR_AT_EOL (1 << 4)
#define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | \ #define XDF_WHITESPACE_FLAGS (XDF_IGNORE_WHITESPACE | \
XDF_IGNORE_WHITESPACE_CHANGE | \ XDF_IGNORE_WHITESPACE_CHANGE | \
XDF_IGNORE_WHITESPACE_AT_EOL | \ XDF_IGNORE_WHITESPACE_AT_EOL | \
XDF_IGNORE_CR_AT_EOL) XDF_IGNORE_CR_AT_EOL)
#define XDF_IGNORE_BLANK_LINES (1 << 7) #define XDF_IGNORE_BLANK_LINES (1 << 7)
#define XDF_PATIENCE_DIFF (1 << 14)
#define XDF_HISTOGRAM_DIFF (1 << 15)
#define XDF_DIFF_ALGORITHM_MASK (XDF_PATIENCE_DIFF | XDF_HISTOGRAM_DIFF)
#define XDF_DIFF_ALG(x) ((x) & XDF_DIFF_ALGORITHM_MASK)
#define XDF_INDENT_HEURISTIC (1 << 23) #define XDF_INDENT_HEURISTIC (1 << 23)
/* xdemitconf_t.flags */ /* xdemitconf_t.flags */
#define XDL_EMIT_FUNCNAMES (1 << 0) #define XDL_EMIT_FUNCNAMES (1 << 0)
#define XDL_EMIT_FUNCCONTEXT (1 << 2) #define XDL_EMIT_FUNCCONTEXT (1 << 2)
#define XDL_MMB_READONLY (1 << 0) #define XDL_MMB_READONLY (1 << 0)

mercurial/thirdparty/xdiff/xdiffi.c

int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
xdfenv_t *xe) { xdfenv_t *xe) {
long ndiags; long ndiags;
long *kvd, *kvdf, *kvdb; long *kvd, *kvdf, *kvdb;
xdalgoenv_t xenv; xdalgoenv_t xenv;
diffdata_t dd1, dd2; diffdata_t dd1, dd2;
if (XDF_DIFF_ALG(xpp->flags) == XDF_PATIENCE_DIFF)
return xdl_do_patience_diff(mf1, mf2, xpp, xe);
if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF)
return xdl_do_histogram_diff(mf1, mf2, xpp, xe);
if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) { if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) {
return -1; return -1;
} }
/* /*
* Allocate and setup K vectors to be used by the differential algorithm. * Allocate and setup K vectors to be used by the differential algorithm.
* One is to store the forward path and one to store the backward path. * One is to store the forward path and one to store the backward path.

mercurial/thirdparty/xdiff/xhistogram.c

  • This file was deleted.
/*
* Copyright (C) 2010, Google Inc.
* and other copyright owners as documented in JGit's IP log.
*
* This program and the accompanying materials are made available
* under the terms of the Eclipse Distribution License v1.0 which
* accompanies this distribution, is reproduced below, and is
* available at http://www.eclipse.org/org/documents/edl-v10.php
*
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or
* without modification, are permitted provided that the following
* conditions are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* - Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials provided
* with the distribution.
*
* - Neither the name of the Eclipse Foundation, Inc. nor the
* names of its contributors may be used to endorse or promote
* products derived from this software without specific prior
* written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
* CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
* CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#include "xinclude.h"
#include "xtypes.h"
#include "xdiff.h"
#define MAX_PTR UINT_MAX
#define MAX_CNT UINT_MAX
#define LINE_END(n) (line##n + count##n - 1)
#define LINE_END_PTR(n) (*line##n + *count##n - 1)
struct histindex {
struct record {
unsigned int ptr, cnt;
struct record *next;
} **records, /* an occurrence */
**line_map; /* map of line to record chain */
chastore_t rcha;
unsigned int *next_ptrs;
unsigned int table_bits,
records_size,
line_map_size;
unsigned int max_chain_length,
key_shift,
ptr_shift;
unsigned int cnt,
has_common;
xdfenv_t *env;
xpparam_t const *xpp;
};
struct region {
unsigned int begin1, end1;
unsigned int begin2, end2;
};
#define LINE_MAP(i, a) (i->line_map[(a) - i->ptr_shift])
#define NEXT_PTR(index, ptr) \
(index->next_ptrs[(ptr) - index->ptr_shift])
#define CNT(index, ptr) \
((LINE_MAP(index, ptr))->cnt)
#define REC(env, s, l) \
(env->xdf##s.recs[l - 1])
static int cmp_recs(xpparam_t const *xpp,
xrecord_t *r1, xrecord_t *r2)
{
return r1->ha == r2->ha &&
xdl_recmatch(r1->ptr, r1->size, r2->ptr, r2->size,
xpp->flags);
}
#define CMP_ENV(xpp, env, s1, l1, s2, l2) \
(cmp_recs(xpp, REC(env, s1, l1), REC(env, s2, l2)))
#define CMP(i, s1, l1, s2, l2) \
(cmp_recs(i->xpp, REC(i->env, s1, l1), REC(i->env, s2, l2)))
#define TABLE_HASH(index, side, line) \
XDL_HASHLONG((REC(index->env, side, line))->ha, index->table_bits)
static int scanA(struct histindex *index, int line1, int count1)
{
unsigned int ptr, tbl_idx;
unsigned int chain_len;
struct record **rec_chain, *rec;
for (ptr = LINE_END(1); line1 <= ptr; ptr--) {
tbl_idx = TABLE_HASH(index, 1, ptr);
rec_chain = index->records + tbl_idx;
rec = *rec_chain;
chain_len = 0;
while (rec) {
if (CMP(index, 1, rec->ptr, 1, ptr)) {
/*
* ptr is identical to another element. Insert
* it onto the front of the existing element
* chain.
*/
NEXT_PTR(index, ptr) = rec->ptr;
rec->ptr = ptr;
/* cap rec->cnt at MAX_CNT */
rec->cnt = XDL_MIN(MAX_CNT, rec->cnt + 1);
LINE_MAP(index, ptr) = rec;
goto continue_scan;
}
rec = rec->next;
chain_len++;
}
if (chain_len == index->max_chain_length)
return -1;
/*
* This is the first time we have ever seen this particular
* element in the sequence. Construct a new chain for it.
*/
if (!(rec = xdl_cha_alloc(&index->rcha)))
return -1;
rec->ptr = ptr;
rec->cnt = 1;
rec->next = *rec_chain;
*rec_chain = rec;
LINE_MAP(index, ptr) = rec;
continue_scan:
; /* no op */
}
return 0;
}
static int try_lcs(struct histindex *index, struct region *lcs, int b_ptr,
int line1, int count1, int line2, int count2)
{
unsigned int b_next = b_ptr + 1;
struct record *rec = index->records[TABLE_HASH(index, 2, b_ptr)];
unsigned int as, ae, bs, be, np, rc;
int should_break;
for (; rec; rec = rec->next) {
if (rec->cnt > index->cnt) {
if (!index->has_common)
index->has_common = CMP(index, 1, rec->ptr, 2, b_ptr);
continue;
}
as = rec->ptr;
if (!CMP(index, 1, as, 2, b_ptr))
continue;
index->has_common = 1;
for (;;) {
should_break = 0;
np = NEXT_PTR(index, as);
bs = b_ptr;
ae = as;
be = bs;
rc = rec->cnt;
while (line1 < as && line2 < bs
&& CMP(index, 1, as - 1, 2, bs - 1)) {
as--;
bs--;
if (1 < rc)
rc = XDL_MIN(rc, CNT(index, as));
}
while (ae < LINE_END(1) && be < LINE_END(2)
&& CMP(index, 1, ae + 1, 2, be + 1)) {
ae++;
be++;
if (1 < rc)
rc = XDL_MIN(rc, CNT(index, ae));
}
if (b_next <= be)
b_next = be + 1;
if (lcs->end1 - lcs->begin1 < ae - as || rc < index->cnt) {
lcs->begin1 = as;
lcs->begin2 = bs;
lcs->end1 = ae;
lcs->end2 = be;
index->cnt = rc;
}
if (np == 0)
break;
while (np <= ae) {
np = NEXT_PTR(index, np);
if (np == 0) {
should_break = 1;
break;
}
}
if (should_break)
break;
as = np;
}
}
return b_next;
}
static int find_lcs(struct histindex *index, struct region *lcs,
int line1, int count1, int line2, int count2) {
int b_ptr;
if (scanA(index, line1, count1))
return -1;
index->cnt = index->max_chain_length + 1;
for (b_ptr = line2; b_ptr <= LINE_END(2); )
b_ptr = try_lcs(index, lcs, b_ptr, line1, count1, line2, count2);
return index->has_common && index->max_chain_length < index->cnt;
}
static int fall_back_to_classic_diff(struct histindex *index,
int line1, int count1, int line2, int count2)
{
xpparam_t xpp;
xpp.flags = index->xpp->flags & ~XDF_DIFF_ALGORITHM_MASK;
return xdl_fall_back_diff(index->env, &xpp,
line1, count1, line2, count2);
}
static int histogram_diff(xpparam_t const *xpp, xdfenv_t *env,
int line1, int count1, int line2, int count2)
{
struct histindex index;
struct region lcs;
int sz;
int result = -1;
if (count1 <= 0 && count2 <= 0)
return 0;
if (LINE_END(1) >= MAX_PTR)
return -1;
if (!count1) {
while(count2--)
env->xdf2.rchg[line2++ - 1] = 1;
return 0;
} else if (!count2) {
while(count1--)
env->xdf1.rchg[line1++ - 1] = 1;
return 0;
}
memset(&index, 0, sizeof(index));
index.env = env;
index.xpp = xpp;
index.records = NULL;
index.line_map = NULL;
/* in case of early xdl_cha_free() */
index.rcha.head = NULL;
index.table_bits = xdl_hashbits(count1);
sz = index.records_size = 1 << index.table_bits;
sz *= sizeof(struct record *);
if (!(index.records = (struct record **) xdl_malloc(sz)))
goto cleanup;
memset(index.records, 0, sz);
sz = index.line_map_size = count1;
sz *= sizeof(struct record *);
if (!(index.line_map = (struct record **) xdl_malloc(sz)))
goto cleanup;
memset(index.line_map, 0, sz);
sz = index.line_map_size;
sz *= sizeof(unsigned int);
if (!(index.next_ptrs = (unsigned int *) xdl_malloc(sz)))
goto cleanup;
memset(index.next_ptrs, 0, sz);
/* lines / 4 + 1 comes from xprepare.c:xdl_prepare_ctx() */
if (xdl_cha_init(&index.rcha, sizeof(struct record), count1 / 4 + 1) < 0)
goto cleanup;
index.ptr_shift = line1;
index.max_chain_length = 64;
memset(&lcs, 0, sizeof(lcs));
if (find_lcs(&index, &lcs, line1, count1, line2, count2))
result = fall_back_to_classic_diff(&index, line1, count1, line2, count2);
else {
if (lcs.begin1 == 0 && lcs.begin2 == 0) {
while (count1--)
env->xdf1.rchg[line1++ - 1] = 1;
while (count2--)
env->xdf2.rchg[line2++ - 1] = 1;
result = 0;
} else {
result = histogram_diff(xpp, env,
line1, lcs.begin1 - line1,
line2, lcs.begin2 - line2);
if (result)
goto cleanup;
result = histogram_diff(xpp, env,
lcs.end1 + 1, LINE_END(1) - lcs.end1,
lcs.end2 + 1, LINE_END(2) - lcs.end2);
if (result)
goto cleanup;
}
}
cleanup:
xdl_free(index.records);
xdl_free(index.line_map);
xdl_free(index.next_ptrs);
xdl_cha_free(&index.rcha);
return result;
}
int xdl_do_histogram_diff(mmfile_t *file1, mmfile_t *file2,
xpparam_t const *xpp, xdfenv_t *env)
{
if (xdl_prepare_env(file1, file2, xpp, env) < 0)
return -1;
return histogram_diff(xpp, env,
env->xdf1.dstart + 1, env->xdf1.dend - env->xdf1.dstart + 1,
env->xdf2.dstart + 1, env->xdf2.dend - env->xdf2.dstart + 1);
}

mercurial/thirdparty/xdiff/xpatience.c

  • This file was deleted.
/*
* LibXDiff by Davide Libenzi ( File Differential Library )
* Copyright (C) 2003-2016 Davide Libenzi, Johannes E. Schindelin
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, see
* <http://www.gnu.org/licenses/>.
*
* Davide Libenzi <davidel@xmailserver.org>
*
*/
#include "xinclude.h"
#include "xtypes.h"
#include "xdiff.h"
/*
* The basic idea of patience diff is to find lines that are unique in
* both files. These are intuitively the ones that we want to see as
* common lines.
*
* The maximal ordered sequence of such line pairs (where ordered means
* that the order in the sequence agrees with the order of the lines in
* both files) naturally defines an initial set of common lines.
*
* Now, the algorithm tries to extend the set of common lines by growing
* the line ranges where the files have identical lines.
*
* Between those common lines, the patience diff algorithm is applied
* recursively, until no unique line pairs can be found; these line ranges
* are handled by the well-known Myers algorithm.
*/
#define NON_UNIQUE ULONG_MAX
/*
* This is a hash mapping from line hash to line numbers in the first and
* second file.
*/
struct hashmap {
int nr, alloc;
struct entry {
unsigned long hash;
/*
* 0 = unused entry, 1 = first line, 2 = second, etc.
* line2 is NON_UNIQUE if the line is not unique
* in either the first or the second file.
*/
unsigned long line1, line2;
/*
* "next" & "previous" are used for the longest common
* sequence;
* initially, "next" reflects only the order in file1.
*/
struct entry *next, *previous;
/*
* If 1, this entry can serve as an anchor. See
* Documentation/diff-options.txt for more information.
*/
unsigned anchor : 1;
} *entries, *first, *last;
/* were common records found? */
unsigned long has_matches;
mmfile_t *file1, *file2;
xdfenv_t *env;
xpparam_t const *xpp;
};
static int is_anchor(xpparam_t const *xpp, const char *line)
{
int i;
for (i = 0; i < xpp->anchors_nr; i++) {
if (!strncmp(line, xpp->anchors[i], strlen(xpp->anchors[i])))
return 1;
}
return 0;
}
/* The argument "pass" is 1 for the first file, 2 for the second. */
static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,
int pass)
{
xrecord_t **records = pass == 1 ?
map->env->xdf1.recs : map->env->xdf2.recs;
xrecord_t *record = records[line - 1], *other;
/*
* After xdl_prepare_env() (or more precisely, due to
* xdl_classify_record()), the "ha" member of the records (AKA lines)
* is _not_ the hash anymore, but a linearized version of it. In
* other words, the "ha" member is guaranteed to start with 0 and
* the second record's ha can only be 0 or 1, etc.
*
* So we multiply ha by 2 in the hope that the hashing was
* "unique enough".
*/
int index = (int)((record->ha << 1) % map->alloc);
while (map->entries[index].line1) {
other = map->env->xdf1.recs[map->entries[index].line1 - 1];
if (map->entries[index].hash != record->ha ||
!xdl_recmatch(record->ptr, record->size,
other->ptr, other->size,
map->xpp->flags)) {
if (++index >= map->alloc)
index = 0;
continue;
}
if (pass == 2)
map->has_matches = 1;
if (pass == 1 || map->entries[index].line2)
map->entries[index].line2 = NON_UNIQUE;
else
map->entries[index].line2 = line;
return;
}
if (pass == 2)
return;
map->entries[index].line1 = line;
map->entries[index].hash = record->ha;
map->entries[index].anchor = is_anchor(xpp, map->env->xdf1.recs[line - 1]->ptr);
if (!map->first)
map->first = map->entries + index;
if (map->last) {
map->last->next = map->entries + index;
map->entries[index].previous = map->last;
}
map->last = map->entries + index;
map->nr++;
}
/*
* This function has to be called for each recursion into the inter-hunk
* parts, as previously non-unique lines can become unique when being
* restricted to a smaller part of the files.
*
* It is assumed that env has been prepared using xdl_prepare().
*/
static int fill_hashmap(mmfile_t *file1, mmfile_t *file2,
xpparam_t const *xpp, xdfenv_t *env,
struct hashmap *result,
int line1, int count1, int line2, int count2)
{
result->file1 = file1;
result->file2 = file2;
result->xpp = xpp;
result->env = env;
/* We know exactly how large we want the hash map */
result->alloc = count1 * 2;
result->entries = (struct entry *)
xdl_malloc(result->alloc * sizeof(struct entry));
if (!result->entries)
return -1;
memset(result->entries, 0, result->alloc * sizeof(struct entry));
/* First, fill with entries from the first file */
while (count1--)
insert_record(xpp, line1++, result, 1);
/* Then search for matches in the second file */
while (count2--)
insert_record(xpp, line2++, result, 2);
return 0;
}
/*
* Find the longest sequence with a smaller last element (meaning a smaller
* line2, as we construct the sequence with entries ordered by line1).
*/
static int binary_search(struct entry **sequence, int longest,
struct entry *entry)
{
int left = -1, right = longest;
while (left + 1 < right) {
int middle = left + (right - left) / 2;
/* by construction, no two entries can be equal */
if (sequence[middle]->line2 > entry->line2)
right = middle;
else
left = middle;
}
/* return the index in "sequence", _not_ the sequence length */
return left;
}
/*
* The idea is to start with the list of common unique lines sorted by
* the order in file1. For each of these pairs, the longest (partial)
* sequence whose last element's line2 is smaller is determined.
*
* For efficiency, the sequences are kept in a list containing exactly one
* item per sequence length: the sequence with the smallest last
* element (in terms of line2).
*/
static struct entry *find_longest_common_sequence(struct hashmap *map)
{
struct entry **sequence = xdl_malloc(map->nr * sizeof(struct entry *));
int longest = 0, i;
struct entry *entry;
/*
* If not -1, this entry in sequence must never be overridden.
* Therefore, overriding entries before this has no effect, so
* do not do that either.
*/
int anchor_i = -1;
for (entry = map->first; entry; entry = entry->next) {
if (!entry->line2 || entry->line2 == NON_UNIQUE)
continue;
i = binary_search(sequence, longest, entry);
entry->previous = i < 0 ? NULL : sequence[i];
++i;
if (i <= anchor_i)
continue;
sequence[i] = entry;
if (entry->anchor) {
anchor_i = i;
longest = anchor_i + 1;
} else if (i == longest) {
longest++;
}
}
/* No common unique lines were found */
if (!longest) {
xdl_free(sequence);
return NULL;
}
/* Iterate starting at the last element, adjusting the "next" members */
entry = sequence[longest - 1];
entry->next = NULL;
while (entry->previous) {
entry->previous->next = entry;
entry = entry->previous;
}
xdl_free(sequence);
return entry;
}
static int match(struct hashmap *map, int line1, int line2)
{
xrecord_t *record1 = map->env->xdf1.recs[line1 - 1];
xrecord_t *record2 = map->env->xdf2.recs[line2 - 1];
return xdl_recmatch(record1->ptr, record1->size,
record2->ptr, record2->size, map->xpp->flags);
}
static int patience_diff(mmfile_t *file1, mmfile_t *file2,
xpparam_t const *xpp, xdfenv_t *env,
int line1, int count1, int line2, int count2);
static int walk_common_sequence(struct hashmap *map, struct entry *first,
int line1, int count1, int line2, int count2)
{
int end1 = line1 + count1, end2 = line2 + count2;
int next1, next2;
for (;;) {
/* Try to grow the line ranges of common lines */
if (first) {
next1 = first->line1;
next2 = first->line2;
while (next1 > line1 && next2 > line2 &&
match(map, next1 - 1, next2 - 1)) {
next1--;
next2--;
}
} else {
next1 = end1;
next2 = end2;
}
while (line1 < next1 && line2 < next2 &&
match(map, line1, line2)) {
line1++;
line2++;
}
/* Recurse */
if (next1 > line1 || next2 > line2) {
struct hashmap submap;
memset(&submap, 0, sizeof(submap));
if (patience_diff(map->file1, map->file2,
map->xpp, map->env,
line1, next1 - line1,
line2, next2 - line2))
return -1;
}
if (!first)
return 0;
while (first->next &&
first->next->line1 == first->line1 + 1 &&
first->next->line2 == first->line2 + 1)
first = first->next;
line1 = first->line1 + 1;
line2 = first->line2 + 1;
first = first->next;
}
}
static int fall_back_to_classic_diff(struct hashmap *map,
int line1, int count1, int line2, int count2)
{
xpparam_t xpp;
xpp.flags = map->xpp->flags & ~XDF_DIFF_ALGORITHM_MASK;
return xdl_fall_back_diff(map->env, &xpp,
line1, count1, line2, count2);
}
/*
* Recursively find the longest common sequence of unique lines,
* and if none was found, ask xdl_do_diff() to do the job.
*
* This function assumes that env was prepared with xdl_prepare_env().
*/
static int patience_diff(mmfile_t *file1, mmfile_t *file2,
xpparam_t const *xpp, xdfenv_t *env,
int line1, int count1, int line2, int count2)
{
struct hashmap map;
struct entry *first;
int result = 0;
/* trivial case: one side is empty */
if (!count1) {
while(count2--)
env->xdf2.rchg[line2++ - 1] = 1;
return 0;
} else if (!count2) {
while(count1--)
env->xdf1.rchg[line1++ - 1] = 1;
return 0;
}
memset(&map, 0, sizeof(map));
if (fill_hashmap(file1, file2, xpp, env, &map,
line1, count1, line2, count2))
return -1;
/* are there any matching lines at all? */
if (!map.has_matches) {
while(count1--)
env->xdf1.rchg[line1++ - 1] = 1;
while(count2--)
env->xdf2.rchg[line2++ - 1] = 1;
xdl_free(map.entries);
return 0;
}
first = find_longest_common_sequence(&map);
if (first)
result = walk_common_sequence(&map, first,
line1, count1, line2, count2);
else
result = fall_back_to_classic_diff(&map,
line1, count1, line2, count2);
xdl_free(map.entries);
return result;
}
int xdl_do_patience_diff(mmfile_t *file1, mmfile_t *file2,
xpparam_t const *xpp, xdfenv_t *env)
{
if (xdl_prepare_env(file1, file2, xpp, env) < 0)
return -1;
/* environment is cleaned up in xdl_diff() */
return patience_diff(file1, file2, xpp, env,
1, env->xdf1.nrec, 1, env->xdf2.nrec);
}

mercurial/thirdparty/xdiff/xprepare.c

#include "xinclude.h" #include "xinclude.h"
#define XDL_KPDIS_RUN 4 #define XDL_KPDIS_RUN 4
#define XDL_MAX_EQLIMIT 1024 #define XDL_MAX_EQLIMIT 1024
#define XDL_SIMSCAN_WINDOW 100 #define XDL_SIMSCAN_WINDOW 100
#define XDL_GUESS_NLINES1 256 #define XDL_GUESS_NLINES1 256
#define XDL_GUESS_NLINES2 20
typedef struct s_xdlclass { typedef struct s_xdlclass {
struct s_xdlclass *next; struct s_xdlclass *next;
unsigned long ha; unsigned long ha;
char const *line; char const *line;
long size; long size;
long idx; long idx;
rhash = NULL; rhash = NULL;
recs = NULL; recs = NULL;
if (xdl_cha_init(&xdf->rcha, sizeof(xrecord_t), narec / 4 + 1) < 0) if (xdl_cha_init(&xdf->rcha, sizeof(xrecord_t), narec / 4 + 1) < 0)
goto abort; goto abort;
if (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *)))) if (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *))))
goto abort; goto abort;
if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF) {
hbits = hsize = 0;
else {
hbits = xdl_hashbits((unsigned int) narec); hbits = xdl_hashbits((unsigned int) narec);
hsize = 1 << hbits; hsize = 1 << hbits;
if (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *)))) if (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))
goto abort; goto abort;
memset(rhash, 0, hsize * sizeof(xrecord_t *)); memset(rhash, 0, hsize * sizeof(xrecord_t *));
} }
nrec = 0; nrec = 0;
} }
if (!(crec = xdl_cha_alloc(&xdf->rcha))) if (!(crec = xdl_cha_alloc(&xdf->rcha)))
goto abort; goto abort;
crec->ptr = prev; crec->ptr = prev;
crec->size = (long) (cur - prev); crec->size = (long) (cur - prev);
crec->ha = hav; crec->ha = hav;
recs[nrec++] = crec; recs[nrec++] = crec;
if ((XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) && if (xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)
xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)
goto abort; goto abort;
} }
} }
if (!(rchg = (char *) xdl_malloc((nrec + 2) * sizeof(char)))) if (!(rchg = (char *) xdl_malloc((nrec + 2) * sizeof(char))))
goto abort; goto abort;
memset(rchg, 0, (nrec + 2) * sizeof(char)); memset(rchg, 0, (nrec + 2) * sizeof(char));
int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
xdfenv_t *xe) { xdfenv_t *xe) {
long enl1, enl2, sample; long enl1, enl2, sample;
xdlclassifier_t cf; xdlclassifier_t cf;
memset(&cf, 0, sizeof(cf)); memset(&cf, 0, sizeof(cf));
/* sample = XDL_GUESS_NLINES1;
* For histogram diff, we can afford a smaller sample size and
* thus a poorer estimate of the number of lines, as the hash
* table (rhash) won't be filled up/grown. The number of lines
* (nrecs) will be updated correctly anyway by
* xdl_prepare_ctx().
*/
sample = (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF
? XDL_GUESS_NLINES2 : XDL_GUESS_NLINES1);
enl1 = xdl_guess_lines(mf1, sample) + 1; enl1 = xdl_guess_lines(mf1, sample) + 1;
enl2 = xdl_guess_lines(mf2, sample) + 1; enl2 = xdl_guess_lines(mf2, sample) + 1;
if (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF && if (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0)
xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0)
return -1; return -1;
if (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) { if (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {
xdl_free_classifier(&cf); xdl_free_classifier(&cf);
return -1; return -1;
} }
if (xdl_prepare_ctx(2, mf2, enl2, xpp, &cf, &xe->xdf2) < 0) { if (xdl_prepare_ctx(2, mf2, enl2, xpp, &cf, &xe->xdf2) < 0) {
xdl_free_ctx(&xe->xdf1); xdl_free_ctx(&xe->xdf1);
xdl_free_classifier(&cf); xdl_free_classifier(&cf);
return -1; return -1;
} }
if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) && if (xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) {
(XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) &&
xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) {
xdl_free_ctx(&xe->xdf2); xdl_free_ctx(&xe->xdf2);
xdl_free_ctx(&xe->xdf1); xdl_free_ctx(&xe->xdf1);
xdl_free_classifier(&cf); xdl_free_classifier(&cf);
return -1; return -1;
} }
if (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)
xdl_free_classifier(&cf); xdl_free_classifier(&cf);
return 0; return 0;
} }
void xdl_free_env(xdfenv_t *xe) { void xdl_free_env(xdfenv_t *xe) {
xdl_free_ctx(&xe->xdf2); xdl_free_ctx(&xe->xdf2);
mercurial/thirdparty/xdiff/xdiffi.c