xdiff: remove patience and histogram diff algorithms

xdiff: remove patience and histogram diff algorithms

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.

Differential Revision: https://phab.mercurial-scm.org/D2573

--- a/mercurial/thirdparty/xdiff/xdiff.h	Sat Mar 03 10:39:43 2018 -0800
+++ b/mercurial/thirdparty/xdiff/xdiff.h	Sat Mar 03 10:39:55 2018 -0800
@@ -27,6 +27,8 @@
 extern "C" {
 #endif /* #ifdef __cplusplus */
 
+#include <stddef.h> /* size_t */
+
 /* xpparm_t.flags */
 #define XDF_NEED_MINIMAL (1 << 0)
 
@@ -41,11 +43,6 @@
 
 #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)
 
 /* xdemitconf_t.flags */

--- a/mercurial/thirdparty/xdiff/xdiffi.c	Sat Mar 03 10:39:43 2018 -0800
+++ b/mercurial/thirdparty/xdiff/xdiffi.c	Sat Mar 03 10:39:55 2018 -0800
@@ -328,12 +328,6 @@
 	xdalgoenv_t xenv;
 	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) {
 
 		return -1;

--- a/mercurial/thirdparty/xdiff/xhistogram.c	Sat Mar 03 10:39:43 2018 -0800
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,363 +0,0 @@
-/*
- * 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);
-}

--- a/mercurial/thirdparty/xdiff/xpatience.c	Sat Mar 03 10:39:43 2018 -0800
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,390 +0,0 @@
-/*
- *  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 <[e-mail]>
- *
- */
-#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);
-}

--- a/mercurial/thirdparty/xdiff/xprepare.c	Sat Mar 03 10:39:43 2018 -0800
+++ b/mercurial/thirdparty/xdiff/xprepare.c	Sat Mar 03 10:39:55 2018 -0800
@@ -27,7 +27,6 @@
 #define XDL_MAX_EQLIMIT 1024
 #define XDL_SIMSCAN_WINDOW 100
 #define XDL_GUESS_NLINES1 256
-#define XDL_GUESS_NLINES2 20
 
 
 typedef struct s_xdlclass {
@@ -181,9 +180,7 @@
 	if (!(recs = (xrecord_t **) xdl_malloc(narec * sizeof(xrecord_t *))))
 		goto abort;
 
-	if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF)
-		hbits = hsize = 0;
-	else {
+	{
 		hbits = xdl_hashbits((unsigned int) narec);
 		hsize = 1 << hbits;
 		if (!(rhash = (xrecord_t **) xdl_malloc(hsize * sizeof(xrecord_t *))))
@@ -209,8 +206,7 @@
 			crec->ha = hav;
 			recs[nrec++] = crec;
 
-			if ((XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) &&
-			    xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)
+			if (xdl_classify_record(pass, cf, rhash, hbits, crec) < 0)
 				goto abort;
 		}
 	}
@@ -266,21 +262,12 @@
 
 	memset(&cf, 0, sizeof(cf));
 
-	/*
-	 * 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);
+	sample = XDL_GUESS_NLINES1;
 
 	enl1 = xdl_guess_lines(mf1, sample) + 1;
 	enl2 = xdl_guess_lines(mf2, sample) + 1;
 
-	if (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF &&
-	    xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0)
+	if (xdl_init_classifier(&cf, enl1 + enl2 + 1, xpp->flags) < 0)
 		return -1;
 
 	if (xdl_prepare_ctx(1, mf1, enl1, xpp, &cf, &xe->xdf1) < 0) {
@@ -295,18 +282,14 @@
 		return -1;
 	}
 
-	if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&
-	    (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) &&
-	    xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) {
-
+	if (xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) {
 		xdl_free_ctx(&xe->xdf2);
 		xdl_free_ctx(&xe->xdf1);
 		xdl_free_classifier(&cf);
 		return -1;
 	}
 
-	if (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF)
-		xdl_free_classifier(&cf);
+	xdl_free_classifier(&cf);
 
 	return 0;
 }