Merge lp:~jelmer/brz/external-patiencediff into lp:brz

[Jelmer Vernooij]

Use external patiencediff.

Use external patiencediff.

[Martin Packman (gz)]

Thanks!

review: Approve

[The Breezy Bot (the-breezy-bot)]

Running landing tests failed
https://ci.breezy-vcs.org/job/brz/job/brz-land/274/

[The Breezy Bot (the-breezy-bot)]

Running landing tests failed
https://ci.breezy-vcs.org/job/brz/job/brz-land/281/

[The Breezy Bot (the-breezy-bot)]

Running landing tests failed
https://ci.breezy-vcs.org/job/brz/job/brz-land/292/

[The Breezy Bot (the-breezy-bot)]

Running landing tests failed
https://ci.breezy-vcs.org/job/brz/job/brz-land/296/

=== modified file '.travis.yml'
--- .travis.yml	2019-01-28 23:51:14 +0000
+++ .travis.yml	2019-05-28 23:22:43 +0000
@@ -23,7 +23,7 @@
 install:
   - sudo apt install python-all-dev python3-all-dev subunit
   - travis_retry pip install -U setuptools
-  - travis_retry pip install -U pip coverage codecov flake8 testtools paramiko fastimport configobj cython testscenarios six docutils python-subunit dulwich $TEST_REQUIRE sphinx sphinx_epytext launchpadlib
+  - travis_retry pip install -U pip coverage codecov flake8 testtools paramiko fastimport configobj cython testscenarios six docutils python-subunit $TEST_REQUIRE sphinx sphinx_epytext launchpadlib patiencediff git+https://github.com/dulwich/dulwich
 
 after_success:
   - codecov

=== modified file 'breezy/_annotator_py.py'
--- breezy/_annotator_py.py	2018-11-11 03:33:20 +0000
+++ breezy/_annotator_py.py	2019-05-28 23:22:43 +0000
@@ -20,10 +20,12 @@
 
 from .lazy_import import lazy_import
 lazy_import(globals(), """
+
+import patiencediff
+
 from breezy import (
     annotate, # Must be lazy to avoid circular importing
     graph as _mod_graph,
-    patiencediff,
     )
 """)
 from . import (

=== removed file 'breezy/_patiencediff_c.c'
--- breezy/_patiencediff_c.c	2019-01-27 18:53:46 +0000
+++ breezy/_patiencediff_c.c	1970-01-01 00:00:00 +0000
@@ -1,1204 +0,0 @@
-/*
- Copyright (C) 2007, 2010 Canonical Ltd
-
- This program is free software; you can redistribute it and/or modify
- it under the terms of the GNU General Public License as published by
- the Free Software Foundation; either version 2 of the License, or
- (at your option) any later version.
-
- This program 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 General Public License for more details.
-
- You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
-
- Function equate_lines based on bdiff.c from Mercurial.
-   Copyright (C) 2005, 2006 Matt Mackall <[e-mail]>
-
- Functions unique_lcs/recurse_matches based on _patiencediff_py.py.
-   Copyright (C) 2005 Bram Cohen, Copyright (C) 2005, 2006 Canonical Ltd
-*/
-
-
-#include <stdlib.h>
-#include <string.h>
-#include <Python.h>
-
-#include "python-compat.h"
-
-
-#if defined(__GNUC__)
-#   define inline __inline__
-#elif defined(_MSC_VER)
-#   define inline __inline
-#else
-#   define inline
-#endif
-
-
-#define MIN(a, b) (((a) > (b)) ? (b) : (a))
-#define MAX(a, b) (((a) > (b)) ? (a) : (b))
-
-
-#define SENTINEL -1
-
-
-enum {
-    OP_EQUAL = 0,
-    OP_INSERT,
-    OP_DELETE,
-    OP_REPLACE
-};
-
-
-/* values from this array need to correspont to the order of the enum above */
-static char *opcode_names[] = {
-    "equal",
-    "insert",
-    "delete",
-    "replace",
-};
-
-
-struct line {
-    long hash;         /* hash code of the string/object */
-    Py_ssize_t next;   /* next line from the same equivalence class */
-    Py_ssize_t equiv;  /* equivalence class */
-    PyObject *data;
-};
-
-
-struct bucket {
-    Py_ssize_t a_head;  /* first item in `a` from this equivalence class */
-    Py_ssize_t a_count;
-    Py_ssize_t b_head;  /* first item in `b` from this equivalence class */
-    Py_ssize_t b_count;
-    Py_ssize_t a_pos;
-    Py_ssize_t b_pos;
-};
-
-
-struct hashtable {
-    Py_ssize_t last_a_pos;
-    Py_ssize_t last_b_pos;
-    Py_ssize_t size;
-    struct bucket *table;
-};
-
-struct matching_line {
-    Py_ssize_t a;     /* index of the line in `a` */
-    Py_ssize_t b;     /* index of the line in `b` */
-};
-
-
-struct matching_block {
-    Py_ssize_t a;     /* index of the first line in `a` */
-    Py_ssize_t b;     /* index of the first line in `b` */
-    Py_ssize_t len;   /* length of the block */
-};
-
-
-struct matching_blocks {
-    struct matching_block *matches;
-    Py_ssize_t count;
-};
-
-
-struct opcode {
-    int tag;
-    Py_ssize_t i1;
-    Py_ssize_t i2;
-    Py_ssize_t j1;
-    Py_ssize_t j2;
-};
-
-
-typedef struct {
-    PyObject_HEAD
-    Py_ssize_t asize;
-    Py_ssize_t bsize;
-    struct line *a;
-    struct line *b;
-    struct hashtable hashtable;
-    Py_ssize_t *backpointers;
-} PatienceSequenceMatcher;
-
-
-static inline Py_ssize_t
-bisect_left(Py_ssize_t *list, Py_ssize_t item, Py_ssize_t lo, Py_ssize_t hi)
-{
-    while (lo < hi) {
-        Py_ssize_t mid = lo / 2 + hi / 2 + (lo % 2 + hi % 2) / 2;
-        if (list[mid] < item)
-            lo = mid + 1;
-        else
-            hi = mid;
-    }
-    return lo;
-}
-
-
-static inline int
-compare_lines(struct line *a, struct line *b)
-{
-    return ((a->hash != b->hash)
-            || PyObject_RichCompareBool(a->data, b->data, Py_EQ) == 0);
-}
-
-
-static inline int
-find_equivalence_class(struct bucket *hashtable, Py_ssize_t hsize,
-                       struct line *lines, struct line *ref_lines,
-                       Py_ssize_t i)
-{
-    Py_ssize_t j;
-    for (j = lines[i].hash & hsize; hashtable[j].b_head != SENTINEL; j = (j + 1) & hsize) {
-        if (!compare_lines(lines + i, ref_lines + hashtable[j].b_head)) {
-            break;
-        }
-    }
-    return j;
-}
-
-
-static int
-equate_lines(struct hashtable *result,
-             struct line *lines_a, struct line *lines_b,
-             Py_ssize_t asize, Py_ssize_t bsize)
-{
-    Py_ssize_t i, j, hsize;
-    struct bucket *hashtable;
-
-    /* check for overflow, we need the table to be at least bsize+1 */
-    if (bsize == PY_SSIZE_T_MAX) {
-        PyErr_SetNone(PyExc_OverflowError);
-        return 0;
-    }
-
-    /* build a hash table of the next highest power of 2 */
-    hsize = 1;
-    while (hsize < bsize + 1)
-        hsize *= 2;
-
-    /* can't be 0 */
-    hashtable = (struct bucket *)malloc(sizeof(struct bucket) * hsize);
-    if (hashtable == NULL) {
-        PyErr_NoMemory();
-        return 0;
-    }
-
-    /* initialise the hashtable */
-    for (i = 0; i < hsize; i++) {
-        hashtable[i].a_count = 0;
-        hashtable[i].b_count = 0;
-        hashtable[i].a_head = SENTINEL;
-        hashtable[i].b_head = SENTINEL;
-    }
-    hsize--;
-
-    /* add lines from lines_b to the hash table chains. iterating
-       backwards so the matching lines are sorted to the linked list
-       by the line number (because we are adding new lines to the
-       head of the list) */
-    for (i = bsize - 1; i >= 0; i--) {
-        /* find the first hashtable entry, which is either empty or contains
-           the same line as lines_b[i] */
-        j = find_equivalence_class(hashtable, hsize, lines_b, lines_b, i);
-
-        /* set the equivalence class */
-        lines_b[i].equiv = j;
-
-        /* add to the head of the equivalence class */
-        lines_b[i].next = hashtable[j].b_head;
-        hashtable[j].b_head = i;
-        hashtable[j].b_count++;
-    }
-
-    /* match items from lines_a to their equivalence class in lines_b.
-       again, iterating backwards for the right order of the linked lists */
-    for (i = asize - 1; i >= 0; i--) {
-        /* find the first hash entry, which is either empty or contains
-           the same line as lines_a[i] */
-        j = find_equivalence_class(hashtable, hsize, lines_a, lines_b, i);
-
-        /* set the equivalence class, even if we are not interested in this
-           line, because the values are not pre-filled */
-        lines_a[i].equiv = j;
-
-        /* we are not interested in lines which are not also in lines_b */
-        if (hashtable[j].b_head == SENTINEL)
-            continue;
-
-        /* add to the head of the equivalence class */
-        lines_a[i].next = hashtable[j].a_head;
-        hashtable[j].a_head = i;
-        hashtable[j].a_count++;
-    }
-
-    result->last_a_pos = -1;
-    result->last_b_pos = -1;
-    result->size = hsize + 1;
-    result->table = hashtable;
-
-    return 1;
-}
-
-
-
-/* Finds longest common subsequence of unique lines in a[alo:ahi] and
-   b[blo:bhi].
-   Parameter backpointers must have allocated memory for at least
-   4 * (bhi - blo) ints. */
-Py_ssize_t
-unique_lcs(struct matching_line *answer,
-           struct hashtable *hashtable, Py_ssize_t *backpointers,
-           struct line *lines_a, struct line *lines_b,
-           Py_ssize_t alo, Py_ssize_t blo, Py_ssize_t ahi, Py_ssize_t bhi)
-{
-    Py_ssize_t i, k, equiv, apos, bpos, norm_apos, norm_bpos, bsize, stacksize;
-    Py_ssize_t *stacks, *lasts, *btoa;
-    struct bucket *h;
-
-    k = 0;
-    stacksize = 0;
-    bsize = bhi - blo;
-    h = hashtable->table;
-
-    /* "unpack" the allocated memory */
-    stacks = backpointers + bsize;
-    lasts = stacks + bsize;
-    btoa = lasts + bsize;
-
-    /* initialise the backpointers */
-    for (i = 0; i < bsize; i++)
-        backpointers[i] = SENTINEL;
-
-    if (hashtable->last_a_pos == -1 || hashtable->last_a_pos > alo)
-        for (i = 0; i < hashtable->size; i++)
-            h[i].a_pos = h[i].a_head;
-    hashtable->last_a_pos = alo;
-
-    if (hashtable->last_b_pos == -1 || hashtable->last_b_pos > blo)
-        for (i = 0; i < hashtable->size; i++)
-            h[i].b_pos = h[i].b_head;
-    hashtable->last_b_pos = blo;
-
-    for (bpos = blo; bpos < bhi; bpos++) {
-        equiv = lines_b[bpos].equiv;
-
-        /* no lines in a or b  */
-        if (h[equiv].a_count == 0 || h[equiv].b_count == 0)
-            continue;
-
-        /* find an unique line in lines_a that matches lines_b[bpos]
-           if we find more than one line within the range alo:ahi,
-           jump to the next line from lines_b immediately */
-        apos = SENTINEL;
-        /* loop through all lines in the linked list */
-        for (i = h[equiv].a_pos; i != SENTINEL; i = lines_a[i].next) {
-            /* the index is lower than alo, continue to the next line */
-            if (i < alo) {
-                h[equiv].a_pos = i;
-                continue;
-            }
-            /* the index is higher than ahi, stop searching */
-            if (i >= ahi)
-                break;
-            /* if the line is within our range, check if it's a duplicate */
-            if (apos != SENTINEL)
-                goto nextb;
-            /* save index to the line */
-            apos = i;
-        }
-        /* this line has no equivalent in lines_a[alo:ahi] */
-        if (apos == SENTINEL)
-            goto nextb;
-
-        /* check for duplicates of this line in lines_b[blo:bhi] */
-        /* loop through all lines in the linked list */
-        for (i = h[equiv].b_pos; i != SENTINEL; i = lines_b[i].next) {
-            /* the index is lower than blo, continue to the next line */
-            if (i < blo) {
-                h[equiv].b_pos = i;
-                continue;
-            }
-            /* the index is higher than bhi, stop searching */
-            if (i >= bhi)
-                break;
-            /* if this isn't the line with started with and it's within
-               our range, it's a duplicate */
-            if (i != bpos)
-                goto nextb;
-        }
-
-        /* use normalised indexes ([0,ahi-alo) instead of [alo,ahi))
-           for the patience sorting algorithm */
-        norm_bpos = bpos - blo;
-        norm_apos = apos - alo;
-        btoa[norm_bpos] = norm_apos;
-
-        /*
-        Ok, how does this work...
-
-        We have a list of matching lines from two lists, a and b. These
-        matches are stored in variable `btoa`. As we are iterating over this
-        table by bpos, the lines from b already form an increasing sequence.
-        We need to "sort" also the lines from a using the patience sorting
-        algorithm, ignoring the lines which would need to be swapped.
-
-          http://en.wikipedia.org/wiki/Patience_sorting
-
-        For each pair of lines, we need to place the line from a on either
-        an existing pile that has higher value on the top or create a new
-        pile. Variable `stacks` represents the tops of these piles and in
-        variable `lasts` we store the lines from b, that correspond to the
-        lines from a in `stacks`.
-
-        Whenever we place a new line on top of a pile, we store a
-        backpointer to the line (b) from top of the previous pile. This means
-        that after the loop, variable `backpointers` will contain an index
-        to the previous matching lines that forms an increasing sequence
-        (over both indexes a and b) with the current matching lines. If
-        either index a or b of the previous matching lines would be higher
-        than indexes of the current one or if the indexes of the current
-        one are 0, it will contain SENTINEL.
-
-        To construct the LCS, we will just need to follow these backpointers
-        from the top of the last pile and stop when we reach SENTINEL.
-        */
-
-        /* as an optimization, check if the next line comes at the end,
-           because it usually does */
-        if (stacksize && stacks[stacksize - 1] < norm_apos)
-            k = stacksize;
-        /* as an optimization, check if the next line comes right after
-           the previous line, because usually it does */
-        else if (stacksize && (stacks[k] < norm_apos) &&
-                 (k == stacksize - 1 || stacks[k + 1] > norm_apos))
-            k += 1;
-        else
-            k = bisect_left(stacks, norm_apos, 0, stacksize);
-
-        if (k > 0)
-            backpointers[norm_bpos] = lasts[k - 1];
-
-        if (k < stacksize) {
-            stacks[k] = norm_apos;
-            lasts[k] = norm_bpos;
-        }
-        else {
-            stacks[stacksize] = norm_apos;
-            lasts[stacksize] = norm_bpos;
-            stacksize += 1;
-        }
-
-
-nextb:
-        ;
-    }
-
-    if (stacksize == 0)
-        return 0;
-
-    /* backtrace the structures to find the LCS */
-    i = 0;
-    k = lasts[stacksize - 1];
-    while (k != SENTINEL) {
-        answer[i].a = btoa[k];
-        answer[i].b = k;
-        k = backpointers[k];
-        i++;
-    }
-
-    return i;
-}
-
-/* Adds a new line to the list of matching blocks, either extending the
-   current block or adding a new one. */
-static inline void
-add_matching_line(struct matching_blocks *answer, Py_ssize_t a, Py_ssize_t b)
-{
-    Py_ssize_t last_index = answer->count - 1;
-    if ((last_index >= 0) &&
-        (a == answer->matches[last_index].a +
-              answer->matches[last_index].len) &&
-        (b == answer->matches[last_index].b +
-              answer->matches[last_index].len)) {
-        /* enlarge the last block */
-        answer->matches[last_index].len++;
-    }
-    else {
-        /* create a new block */
-        last_index++;
-        answer->matches[last_index].a = a;
-        answer->matches[last_index].b = b;
-        answer->matches[last_index].len = 1;
-        answer->count++;
-    }
-}
-
-
-static int
-recurse_matches(struct matching_blocks *answer, struct hashtable *hashtable,
-                Py_ssize_t *backpointers, struct line *a, struct line *b,
-                Py_ssize_t alo, Py_ssize_t blo, Py_ssize_t ahi, Py_ssize_t bhi,
-                int maxrecursion)
-{
-    int res;
-    Py_ssize_t new, last_a_pos, last_b_pos, lcs_size, nahi, nbhi, i, apos, bpos;
-    struct matching_line *lcs;
-
-    if (maxrecursion < 0)
-        return 1;
-
-    if (alo == ahi || blo == bhi)
-        return 1;
-
-    new = 0;
-    last_a_pos = alo - 1;
-    last_b_pos = blo - 1;
-
-    lcs = (struct matching_line *)malloc(sizeof(struct matching_line) * (bhi - blo));
-    if (lcs == NULL)
-        return 0;
-
-    lcs_size = unique_lcs(lcs, hashtable, backpointers, a, b, alo, blo, ahi, bhi);
-
-    /* recurse between lines which are unique in each file and match */
-    for (i = lcs_size - 1; i >= 0; i--) {
-        apos = alo + lcs[i].a;
-        bpos = blo + lcs[i].b;
-        if (last_a_pos + 1 != apos || last_b_pos + 1 != bpos) {
-            res = recurse_matches(answer, hashtable,
-                                  backpointers, a, b,
-                                  last_a_pos + 1, last_b_pos + 1,
-                                  apos, bpos, maxrecursion - 1);
-            if (!res)
-                goto error;
-        }
-        last_a_pos = apos;
-        last_b_pos = bpos;
-        add_matching_line(answer, apos, bpos);
-        new = 1;
-    }
-
-    free(lcs);
-    lcs = NULL;
-
-    /* find matches between the last match and the end */
-    if (new > 0) {
-        res = recurse_matches(answer, hashtable,
-                              backpointers, a, b,
-                              last_a_pos + 1, last_b_pos + 1,
-                              ahi, bhi, maxrecursion - 1);
-        if (!res)
-            goto error;
-    }
-
-
-    /* find matching lines at the very beginning */
-    else if (a[alo].equiv == b[blo].equiv) {
-        while (alo < ahi && blo < bhi && a[alo].equiv == b[blo].equiv)
-            add_matching_line(answer, alo++, blo++);
-        res = recurse_matches(answer, hashtable,
-                              backpointers, a, b,
-                              alo, blo, ahi, bhi, maxrecursion - 1);
-        if (!res)
-            goto error;
-    }
-
-    /* find matching lines at the very end */
-    else if (a[ahi - 1].equiv == b[bhi - 1].equiv) {
-        nahi = ahi - 1;
-        nbhi = bhi - 1;
-        while (nahi > alo && nbhi > blo && a[nahi - 1].equiv == b[nbhi - 1].equiv) {
-            nahi--;
-            nbhi--;
-        }
-        res = recurse_matches(answer, hashtable,
-                              backpointers, a, b,
-                              last_a_pos + 1, last_b_pos + 1,
-                              nahi, nbhi, maxrecursion - 1);
-        if (!res)
-            goto error;
-        for (i = 0; i < ahi - nahi; i++)
-            add_matching_line(answer, nahi + i, nbhi + i);
-    }
-
-    return 1;
-
-error:
-    free(lcs);
-    return 0;
-}
-
-
-static void
-delete_lines(struct line *lines, Py_ssize_t size)
-{
-    struct line *line = lines;
-    while (size-- > 0) {
-        Py_XDECREF(line->data);
-        line++;
-    }
-    free(lines);
-}
-
-
-static Py_ssize_t
-load_lines(PyObject *orig, struct line **lines)
-{
-    Py_ssize_t size, i;
-    struct line *line;
-    PyObject *seq, *item;
-
-    seq = PySequence_Fast(orig, "sequence expected");
-    if (seq == NULL) {
-        return -1;
-    }
-
-    size = PySequence_Fast_GET_SIZE(seq);
-    if (size == 0) {
-        Py_DECREF(seq);
-        return 0;
-    }
-
-    /* Allocate a memory block for line data, initialized to 0 */
-    line = *lines = (struct line *)calloc(size, sizeof(struct line));
-    if (line == NULL) {
-        PyErr_NoMemory();
-        Py_DECREF(seq);
-        return -1;
-    }
-
-    for (i = 0; i < size; i++) {
-        item = PySequence_Fast_GET_ITEM(seq, i);
-        Py_INCREF(item);
-        line->data = item;
-        line->hash = PyObject_Hash(item);
-        if (line->hash == (-1)) {
-            /* Propogate the hash exception */
-            size = -1;
-            goto cleanup;
-        }
-        line->next = SENTINEL;
-        line++;
-    }
-
-    cleanup:
-    Py_DECREF(seq);
-    if (size == -1) {
-        /* Error -- cleanup unused object references */
-        delete_lines(*lines, i);
-        *lines = NULL;
-    }
-    return size;
-}
-
-
-static PyObject *
-py_unique_lcs(PyObject *self, PyObject *args)
-{
-    PyObject *aseq, *bseq, *res, *item;
-    Py_ssize_t asize, bsize, i, nmatches, *backpointers = NULL;
-    struct line *a = NULL, *b = NULL;
-    struct matching_line *matches = NULL;
-    struct hashtable hashtable;
-
-    if (!PyArg_ParseTuple(args, "OO", &aseq, &bseq))
-        return NULL;
-
-    hashtable.table = NULL;
-
-    asize = load_lines(aseq, &a);
-    bsize = load_lines(bseq, &b);
-    if (asize == -1 || bsize == -1)
-        goto error;
-
-    if (!equate_lines(&hashtable, a, b, asize, bsize))
-        goto error;
-
-    if (bsize > 0) {
-        matches = (struct matching_line *)malloc(sizeof(struct matching_line) * bsize);
-        if (matches == NULL)
-            goto error;
-
-        backpointers = (Py_ssize_t *)malloc(sizeof(Py_ssize_t) * bsize * 4);
-        if (backpointers == NULL)
-            goto error;
-    }
-
-    nmatches = unique_lcs(matches, &hashtable, backpointers, a, b, 0, 0, asize, bsize);
-
-    res = PyList_New(nmatches);
-    for (i = 0; i < nmatches; i++) {
-        item = Py_BuildValue("nn", matches[nmatches - i - 1].a, matches[nmatches - i - 1].b);
-        if (item == NULL)
-            goto error;
-        if (PyList_SetItem(res, i, item) != 0)
-            goto error;
-    }
-
-    free(backpointers);
-    free(matches);
-    free(hashtable.table);
-    delete_lines(b, bsize);
-    delete_lines(a, asize);
-    return res;
-
-error:
-    free(backpointers);
-    free(matches);
-    free(hashtable.table);
-    delete_lines(b, bsize);
-    delete_lines(a, asize);
-    return NULL;
-}
-
-
-static PyObject *
-py_recurse_matches(PyObject *self, PyObject *args)
-{
-    PyObject *aseq, *bseq, *item, *answer;
-    int maxrecursion, res;
-    Py_ssize_t i, j, asize, bsize, alo, blo, ahi, bhi;
-    Py_ssize_t *backpointers = NULL;
-    struct line *a = NULL, *b = NULL;
-    struct hashtable hashtable;
-    struct matching_blocks matches;
-
-    if (!PyArg_ParseTuple(args, "OOnnnnOi", &aseq, &bseq, &alo, &blo,
-                          &ahi, &bhi, &answer, &maxrecursion))
-        return NULL;
-
-    hashtable.table = NULL;
-    matches.matches = NULL;
-
-    asize = load_lines(aseq, &a);
-    bsize = load_lines(bseq, &b);
-    if (asize == -1 || bsize == -1)
-        goto error;
-
-    if (!equate_lines(&hashtable, a, b, asize, bsize))
-        goto error;
-
-    matches.count = 0;
-
-    if (bsize > 0) {
-        matches.matches = (struct matching_block *)malloc(sizeof(struct matching_block) * bsize);
-        if (matches.matches == NULL)
-            goto error;
-
-        backpointers = (Py_ssize_t *)malloc(sizeof(Py_ssize_t) * bsize * 4);
-        if (backpointers == NULL)
-            goto error;
-    } else {
-        matches.matches = NULL;
-        backpointers = NULL;
-    }
-
-    res = recurse_matches(&matches, &hashtable, backpointers,
-                          a, b, alo, blo, ahi, bhi, maxrecursion);
-    if (!res)
-        goto error;
-
-    for (i = 0; i < matches.count; i++) {
-        for (j = 0; j < matches.matches[i].len; j++) {
-            item = Py_BuildValue("nn", matches.matches[i].a + j,
-                                 matches.matches[i].b + j);
-            if (item == NULL)
-                goto error;
-            if (PyList_Append(answer, item) != 0)
-                goto error;
-        }
-    }
-
-    free(backpointers);
-    free(matches.matches);
-    free(hashtable.table);
-    delete_lines(b, bsize);
-    delete_lines(a, asize);
-    Py_RETURN_NONE;
-
-error:
-    free(backpointers);
-    free(matches.matches);
-    free(hashtable.table);
-    delete_lines(b, bsize);
-    delete_lines(a, asize);
-    return NULL;
-}
-
-
-static PyObject *
-PatienceSequenceMatcher_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
-{
-    PyObject *junk, *a, *b;
-    PatienceSequenceMatcher *self;
-
-    self = (PatienceSequenceMatcher *)type->tp_alloc(type, 0);
-    if (self != NULL) {
-
-        if (!PyArg_ParseTuple(args, "OOO", &junk, &a, &b)) {
-            Py_DECREF(self);
-            return NULL;
-        }
-
-        self->asize = load_lines(a, &(self->a));
-        self->bsize = load_lines(b, &(self->b));
-
-        if (self->asize == -1 || self->bsize == -1) {
-            Py_DECREF(self);
-            return NULL;
-        }
-
-        if (!equate_lines(&self->hashtable, self->a, self->b, self->asize, self->bsize)) {
-            Py_DECREF(self);
-            return NULL;
-        }
-
-        if (self->bsize > 0) {
-            self->backpointers = (Py_ssize_t *)malloc(sizeof(Py_ssize_t) * self->bsize * 4);
-            if (self->backpointers == NULL) {
-                Py_DECREF(self);
-                PyErr_NoMemory();
-                return NULL;
-            }
-        } else {
-            self->backpointers = NULL;
-        }
-
-    }
-
-    return (PyObject *)self;
-}
-
-
-static void
-PatienceSequenceMatcher_dealloc(PatienceSequenceMatcher* self)
-{
-    free(self->backpointers);
-    free(self->hashtable.table);
-    delete_lines(self->b, self->bsize);
-    delete_lines(self->a, self->asize);
-    ((PyObject *)self)->ob_type->tp_free((PyObject *)self);
-}
-
-
-static char PatienceSequenceMatcher_get_matching_blocks_doc[] =
-    "Return list of triples describing matching subsequences.\n"
-    "\n"
-    "Each triple is of the form (i, j, n), and means that\n"
-    "a[i:i+n] == b[j:j+n].  The triples are monotonically increasing in\n"
-    "i and in j.\n"
-    "\n"
-    "The last triple is a dummy, (len(a), len(b), 0), and is the only\n"
-    "triple with n==0.\n"
-    "\n"
-    ">>> s = PatienceSequenceMatcher(None, \"abxcd\", \"abcd\")\n"
-    ">>> s.get_matching_blocks()\n"
-    "[(0, 0, 2), (3, 2, 2), (5, 4, 0)]\n";
-
-static PyObject *
-PatienceSequenceMatcher_get_matching_blocks(PatienceSequenceMatcher* self)
-{
-    PyObject *answer, *item;
-    int res;
-    Py_ssize_t i;
-    struct matching_blocks matches;
-
-    matches.count = 0;
-    if (self->bsize > 0) {
-        matches.matches = (struct matching_block *)
-            malloc(sizeof(struct matching_block) * self->bsize);
-        if (matches.matches == NULL)
-            return PyErr_NoMemory();
-    } else
-        matches.matches = NULL;
-
-    res = recurse_matches(&matches, &self->hashtable, self->backpointers,
-                          self->a, self->b, 0, 0,
-                          self->asize, self->bsize, 10);
-    if (!res) {
-        free(matches.matches);
-        return PyErr_NoMemory();
-    }
-
-    answer = PyList_New(matches.count + 1);
-    if (answer == NULL) {
-        free(matches.matches);
-        return NULL;
-    }
-
-    for (i = 0; i < matches.count; i++) {
-        item = Py_BuildValue("nnn", matches.matches[i].a,
-                             matches.matches[i].b, matches.matches[i].len);
-        if (item == NULL)
-            goto error;
-        if (PyList_SetItem(answer, i, item) != 0)
-            goto error;
-    }
-    item = Py_BuildValue("nnn", self->asize, self->bsize, 0);
-    if (item == NULL)
-        goto error;
-    if (PyList_SetItem(answer, i, item) != 0)
-        goto error;
-
-    free(matches.matches);
-    return answer;
-
-error:
-    free(matches.matches);
-    Py_DECREF(answer);
-    return NULL;
-}
-
-
-static char PatienceSequenceMatcher_get_opcodes_doc[] =
-    "Return list of 5-tuples describing how to turn a into b.\n"
-    "\n"
-    "Each tuple is of the form (tag, i1, i2, j1, j2).  The first tuple\n"
-    "has i1 == j1 == 0, and remaining tuples have i1 == the i2 from the\n"
-    "tuple preceding it, and likewise for j1 == the previous j2.\n"
-    "\n"
-    "The tags are strings, with these meanings:\n"
-    "\n"
-    "'replace':  a[i1:i2] should be replaced by b[j1:j2]\n"
-    "'delete':   a[i1:i2] should be deleted.\n"
-    "               Note that j1==j2 in this case.\n"
-    "'insert':   b[j1:j2] should be inserted at a[i1:i1].\n"
-    "               Note that i1==i2 in this case.\n"
-    "'equal':    a[i1:i2] == b[j1:j2]\n"
-    "\n"
-    ">>> a = \"qabxcd\"\n"
-    ">>> b = \"abycdf\"\n"
-    ">>> s = PatienceSequenceMatcher(None, a, b)\n"
-    ">>> for tag, i1, i2, j1, j2 in s.get_opcodes():\n"
-    "...    print (\"%7s a[%d:%d] (%s) b[%d:%d] (%s)\" %\n"
-    "...           (tag, i1, i2, a[i1:i2], j1, j2, b[j1:j2]))\n"
-    " delete a[0:1] (q) b[0:0] ()\n"
-    "  equal a[1:3] (ab) b[0:2] (ab)\n"
-    "replace a[3:4] (x) b[2:3] (y)\n"
-    "  equal a[4:6] (cd) b[3:5] (cd)\n"
-    " insert a[6:6] () b[5:6] (f)\n";
-
-static PyObject *
-PatienceSequenceMatcher_get_opcodes(PatienceSequenceMatcher* self)
-{
-    PyObject *answer, *item;
-    Py_ssize_t i, j, k, ai, bj;
-    int tag, res;
-    struct matching_blocks matches;
-
-    matches.count = 0;
-    matches.matches = (struct matching_block *)malloc(sizeof(struct matching_block) * (self->bsize + 1));
-    if (matches.matches == NULL)
-        return PyErr_NoMemory();
-
-    res = recurse_matches(&matches, &self->hashtable, self->backpointers,
-                          self->a, self->b, 0, 0,
-                          self->asize, self->bsize, 10);
-    if (!res) {
-        free(matches.matches);
-        return PyErr_NoMemory();
-    }
-
-    matches.matches[matches.count].a = self->asize;
-    matches.matches[matches.count].b = self->bsize;
-    matches.matches[matches.count].len = 0;
-    matches.count++;
-
-    answer = PyList_New(0);
-    if (answer == NULL) {
-        free(matches.matches);
-        return NULL;
-    }
-
-    i = j = 0;
-    for (k = 0; k < matches.count; k++) {
-        ai = matches.matches[k].a;
-        bj = matches.matches[k].b;
-
-        tag = -1;
-        if (i < ai && j < bj)
-            tag = OP_REPLACE;
-        else if (i < ai)
-            tag = OP_DELETE;
-        else if (j < bj)
-            tag = OP_INSERT;
-
-        if (tag != -1) {
-            item = Py_BuildValue("snnnn", opcode_names[tag], i, ai, j, bj);
-            if (item == NULL)
-                goto error;
-            if (PyList_Append(answer, item) != 0)
-                goto error;
-        }
-
-        i = ai + matches.matches[k].len;
-        j = bj + matches.matches[k].len;
-
-        if (matches.matches[k].len > 0) {
-            item = Py_BuildValue("snnnn", opcode_names[OP_EQUAL], ai, i, bj, j);
-            if (item == NULL)
-                goto error;
-            if (PyList_Append(answer, item) != 0)
-                goto error;
-        }
-    }
-
-    free(matches.matches);
-    return answer;
-
-error:
-    free(matches.matches);
-    Py_DECREF(answer);
-    return NULL;
-}
-
-
-static char PatienceSequenceMatcher_get_grouped_opcodes_doc[] =
-    "Isolate change clusters by eliminating ranges with no changes.\n"
-    "\n"
-    "Return a list of groups with up to n lines of context.\n"
-    "Each group is in the same format as returned by get_opcodes().\n"
-    "\n"
-    ">>> from pprint import pprint\n"
-    ">>> a = map(str, range(1,40))\n"
-    ">>> b = a[:]\n"
-    ">>> b[8:8] = ['i']     # Make an insertion\n"
-    ">>> b[20] += 'x'       # Make a replacement\n"
-    ">>> b[23:28] = []      # Make a deletion\n"
-    ">>> b[30] += 'y'       # Make another replacement\n"
-    ">>> pprint(PatienceSequenceMatcher(None,a,b).get_grouped_opcodes())\n"
-    "[[('equal', 5, 8, 5, 8), ('insert', 8, 8, 8, 9), ('equal', 8, 11, 9, 12)],\n"
-    " [('equal', 16, 19, 17, 20),\n"
-    "  ('replace', 19, 20, 20, 21),\n"
-    "  ('equal', 20, 22, 21, 23),\n"
-    "  ('delete', 22, 27, 23, 23),\n"
-    "  ('equal', 27, 30, 23, 26)],\n"
-    " [('equal', 31, 34, 27, 30),\n"
-    "  ('replace', 34, 35, 30, 31),\n"
-    "  ('equal', 35, 38, 31, 34)]]\n";
-
-static PyObject *
-PatienceSequenceMatcher_get_grouped_opcodes(PatienceSequenceMatcher* self,
-                                            PyObject *args)
-{
-    PyObject *answer, *group, *item;
-    Py_ssize_t i, j, k, ai, bj, size, ncodes, tag;
-    Py_ssize_t i1, i2, j1, j2;
-    int n = 3, nn, res;
-    struct matching_blocks matches;
-    struct opcode *codes;
-
-    if (!PyArg_ParseTuple(args, "|i", &n))
-        return NULL;
-
-    matches.count = 0;
-    matches.matches = (struct matching_block *)malloc(sizeof(struct matching_block) * (self->bsize + 1));
-    if (matches.matches == NULL)
-        return PyErr_NoMemory();
-
-    res = recurse_matches(&matches, &self->hashtable, self->backpointers,
-                          self->a, self->b, 0, 0,
-                          self->asize, self->bsize, 10);
-    if (!res) {
-        free(matches.matches);
-        return PyErr_NoMemory();
-    }
-
-    matches.matches[matches.count].a = self->asize;
-    matches.matches[matches.count].b = self->bsize;
-    matches.matches[matches.count].len = 0;
-    matches.count++;
-
-    ncodes = 0;
-    codes = (struct opcode *)malloc(sizeof(struct opcode) * matches.count * 2);
-    if (codes == NULL) {
-        free(matches.matches);
-        return PyErr_NoMemory();
-    }
-
-    i = j = 0;
-    for (k = 0; k < matches.count; k++) {
-        ai = matches.matches[k].a;
-        bj = matches.matches[k].b;
-
-        tag = -1;
-        if (i < ai && j < bj)
-            tag = OP_REPLACE;
-        else if (i < ai)
-            tag = OP_DELETE;
-        else if (j < bj)
-            tag = OP_INSERT;
-
-        if (tag != -1) {
-            codes[ncodes].tag = tag;
-            codes[ncodes].i1 = i;
-            codes[ncodes].i2 = ai;
-            codes[ncodes].j1 = j;
-            codes[ncodes].j2 = bj;
-            ncodes++;
-        }
-
-        i = ai + matches.matches[k].len;
-        j = bj + matches.matches[k].len;
-
-        if (matches.matches[k].len > 0) {
-            codes[ncodes].tag = OP_EQUAL;
-            codes[ncodes].i1 = ai;
-            codes[ncodes].i2 = i;
-            codes[ncodes].j1 = bj;
-            codes[ncodes].j2 = j;
-            ncodes++;
-        }
-    }
-
-    if (ncodes == 0) {
-        codes[ncodes].tag = OP_EQUAL;
-        codes[ncodes].i1 = 0;
-        codes[ncodes].i2 = 1;
-        codes[ncodes].j1 = 0;
-        codes[ncodes].j2 = 1;
-        ncodes++;
-    }
-
-    /* fixup leading and trailing groups if they show no changes. */
-    if (codes[0].tag == OP_EQUAL) {
-        codes[0].i1 = MAX(codes[0].i1, codes[0].i2 - n);
-        codes[0].j1 = MAX(codes[0].j1, codes[0].j2 - n);
-    }
-    if (codes[ncodes - 1].tag == OP_EQUAL) {
-        codes[ncodes - 1].i2 = MIN(codes[ncodes - 1].i2,
-                                   codes[ncodes - 1].i1 + n);
-        codes[ncodes - 1].j2 = MIN(codes[ncodes - 1].j2,
-                                   codes[ncodes - 1].j1 + n);
-    }
-
-    group = NULL;
-
-    answer = PyList_New(0);
-    if (answer == NULL)
-        goto error;
-
-    group = PyList_New(0);
-    if (group == NULL)
-        goto error;
-
-    nn = n + n;
-    tag = -1;
-    for (i = 0; i < ncodes; i++) {
-        tag = codes[i].tag;
-        i1 = codes[i].i1;
-        i2 = codes[i].i2;
-        j1 = codes[i].j1;
-        j2 = codes[i].j2;
-        /* end the current group and start a new one whenever
-           there is a large range with no changes. */
-        if (tag == OP_EQUAL && i2 - i1 > nn) {
-            item = Py_BuildValue("snnnn", opcode_names[tag],
-                                  i1, MIN(i2, i1 + n), j1, MIN(j2, j1 + n));
-            if (item == NULL)
-                goto error;
-            if (PyList_Append(group, item) != 0)
-                goto error;
-            if (PyList_Append(answer, group) != 0)
-                goto error;
-            group = PyList_New(0);
-            if (group == NULL)
-                goto error;
-            i1 = MAX(i1, i2 - n);
-            j1 = MAX(j1, j2 - n);
-        }
-        item = Py_BuildValue("snnnn", opcode_names[tag], i1, i2, j1 ,j2);
-        if (item == NULL)
-            goto error;
-        if (PyList_Append(group, item) != 0)
-            goto error;
-    }
-    size = PyList_Size(group);
-    if (size > 0 && !(size == 1 && tag == OP_EQUAL)) {
-        if (PyList_Append(answer, group) != 0)
-            goto error;
-    }
-    else
-        Py_DECREF(group);
-
-    free(codes);
-    free(matches.matches);
-    return answer;
-
-error:
-    free(codes);
-    free(matches.matches);
-    Py_DECREF(group);
-    Py_DECREF(answer);
-    return NULL;
-}
-
-
-static PyMethodDef PatienceSequenceMatcher_methods[] = {
-    {"get_matching_blocks",
-     (PyCFunction)PatienceSequenceMatcher_get_matching_blocks,
-     METH_NOARGS,
-     PatienceSequenceMatcher_get_matching_blocks_doc},
-    {"get_opcodes",
-     (PyCFunction)PatienceSequenceMatcher_get_opcodes,
-     METH_NOARGS,
-     PatienceSequenceMatcher_get_opcodes_doc},
-    {"get_grouped_opcodes",
-     (PyCFunction)PatienceSequenceMatcher_get_grouped_opcodes,
-     METH_VARARGS,
-     PatienceSequenceMatcher_get_grouped_opcodes_doc},
-    {NULL}
-};
-
-
-static char PatienceSequenceMatcher_doc[] =
-    "C implementation of PatienceSequenceMatcher";
-
-
-static PyTypeObject PatienceSequenceMatcherType = {
-    PyObject_HEAD_INIT(NULL)
-    .tp_name = "PatienceSequenceMatcher",
-    .tp_basicsize = sizeof(PatienceSequenceMatcher),
-    .tp_dealloc = (destructor)PatienceSequenceMatcher_dealloc,
-    .tp_flags = Py_TPFLAGS_DEFAULT,
-    .tp_doc = PatienceSequenceMatcher_doc,
-    .tp_methods = PatienceSequenceMatcher_methods,
-    .tp_new = PatienceSequenceMatcher_new,
-};
-
-
-static PyMethodDef cpatiencediff_methods[] = {
-    {"unique_lcs_c", py_unique_lcs, METH_VARARGS},
-    {"recurse_matches_c", py_recurse_matches, METH_VARARGS},
-    {NULL, NULL}
-};
-
-PYMOD_INIT_FUNC(_patiencediff_c)
-{
-    PyObject* m;
-
-    if (PyType_Ready(&PatienceSequenceMatcherType) < 0)
-        return PYMOD_ERROR;
-
-    PYMOD_CREATE(m, "_patiencediff_c",
-                 "C implementation of PatienceSequenceMatcher",
-                 cpatiencediff_methods);
-    if (m == NULL) {
-        return PYMOD_ERROR;
-    }
-    Py_INCREF(&PatienceSequenceMatcherType);
-    PyModule_AddObject(m, "PatienceSequenceMatcher_c",
-                       (PyObject *)&PatienceSequenceMatcherType);
-    return PYMOD_SUCCESS(m);
-}
-
-
-/* vim: sw=4 et 
- */

=== removed file 'breezy/_patiencediff_py.py'
--- breezy/_patiencediff_py.py	2018-11-16 13:05:23 +0000
+++ breezy/_patiencediff_py.py	1970-01-01 00:00:00 +0000
@@ -1,250 +0,0 @@
-#!/usr/bin/env python
-# Copyright (C) 2005 Bram Cohen, Copyright (C) 2005, 2006 Canonical Ltd
-#
-# This program is free software; you can redistribute it and/or modify
-# it under the terms of the GNU General Public License as published by
-# the Free Software Foundation; either version 2 of the License, or
-# (at your option) any later version.
-#
-# This program 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 General Public License for more details.
-#
-# You should have received a copy of the GNU General Public License
-# along with this program; if not, write to the Free Software
-# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
-
-from __future__ import absolute_import
-
-from bisect import bisect
-import difflib
-
-from .trace import mutter
-
-
-def unique_lcs_py(a, b):
-    """Find the longest common subset for unique lines.
-
-    :param a: An indexable object (such as string or list of strings)
-    :param b: Another indexable object (such as string or list of strings)
-    :return: A list of tuples, one for each line which is matched.
-            [(line_in_a, line_in_b), ...]
-
-    This only matches lines which are unique on both sides.
-    This helps prevent common lines from over influencing match
-    results.
-    The longest common subset uses the Patience Sorting algorithm:
-    http://en.wikipedia.org/wiki/Patience_sorting
-    """
-    # set index[line in a] = position of line in a unless
-    # a is a duplicate, in which case it's set to None
-    index = {}
-    for i, line in enumerate(a):
-        if line in index:
-            index[line] = None
-        else:
-            index[line] = i
-    # make btoa[i] = position of line i in a, unless
-    # that line doesn't occur exactly once in both,
-    # in which case it's set to None
-    btoa = [None] * len(b)
-    index2 = {}
-    for pos, line in enumerate(b):
-        next = index.get(line)
-        if next is not None:
-            if line in index2:
-                # unset the previous mapping, which we now know to
-                # be invalid because the line isn't unique
-                btoa[index2[line]] = None
-                del index[line]
-            else:
-                index2[line] = pos
-                btoa[pos] = next
-    # this is the Patience sorting algorithm
-    # see http://en.wikipedia.org/wiki/Patience_sorting
-    backpointers = [None] * len(b)
-    stacks = []
-    lasts = []
-    k = 0
-    for bpos, apos in enumerate(btoa):
-        if apos is None:
-            continue
-        # as an optimization, check if the next line comes at the end,
-        # because it usually does
-        if stacks and stacks[-1] < apos:
-            k = len(stacks)
-        # as an optimization, check if the next line comes right after
-        # the previous line, because usually it does
-        elif stacks and stacks[k] < apos and (k == len(stacks) - 1 or
-                                              stacks[k + 1] > apos):
-            k += 1
-        else:
-            k = bisect(stacks, apos)
-        if k > 0:
-            backpointers[bpos] = lasts[k - 1]
-        if k < len(stacks):
-            stacks[k] = apos
-            lasts[k] = bpos
-        else:
-            stacks.append(apos)
-            lasts.append(bpos)
-    if len(lasts) == 0:
-        return []
-    result = []
-    k = lasts[-1]
-    while k is not None:
-        result.append((btoa[k], k))
-        k = backpointers[k]
-    result.reverse()
-    return result
-
-
-def recurse_matches_py(a, b, alo, blo, ahi, bhi, answer, maxrecursion):
-    """Find all of the matching text in the lines of a and b.
-
-    :param a: A sequence
-    :param b: Another sequence
-    :param alo: The start location of a to check, typically 0
-    :param ahi: The start location of b to check, typically 0
-    :param ahi: The maximum length of a to check, typically len(a)
-    :param bhi: The maximum length of b to check, typically len(b)
-    :param answer: The return array. Will be filled with tuples
-                   indicating [(line_in_a, line_in_b)]
-    :param maxrecursion: The maximum depth to recurse.
-                         Must be a positive integer.
-    :return: None, the return value is in the parameter answer, which
-             should be a list
-
-    """
-    if maxrecursion < 0:
-        mutter('max recursion depth reached')
-        # this will never happen normally, this check is to prevent DOS attacks
-        return
-    oldlength = len(answer)
-    if alo == ahi or blo == bhi:
-        return
-    last_a_pos = alo - 1
-    last_b_pos = blo - 1
-    for apos, bpos in unique_lcs_py(a[alo:ahi], b[blo:bhi]):
-        # recurse between lines which are unique in each file and match
-        apos += alo
-        bpos += blo
-        # Most of the time, you will have a sequence of similar entries
-        if last_a_pos + 1 != apos or last_b_pos + 1 != bpos:
-            recurse_matches_py(
-                a, b, last_a_pos + 1, last_b_pos + 1, apos, bpos, answer,
-                maxrecursion - 1)
-        last_a_pos = apos
-        last_b_pos = bpos
-        answer.append((apos, bpos))
-    if len(answer) > oldlength:
-        # find matches between the last match and the end
-        recurse_matches_py(a, b, last_a_pos + 1, last_b_pos + 1,
-                           ahi, bhi, answer, maxrecursion - 1)
-    elif a[alo] == b[blo]:
-        # find matching lines at the very beginning
-        while alo < ahi and blo < bhi and a[alo] == b[blo]:
-            answer.append((alo, blo))
-            alo += 1
-            blo += 1
-        recurse_matches_py(a, b, alo, blo,
-                           ahi, bhi, answer, maxrecursion - 1)
-    elif a[ahi - 1] == b[bhi - 1]:
-        # find matching lines at the very end
-        nahi = ahi - 1
-        nbhi = bhi - 1
-        while nahi > alo and nbhi > blo and a[nahi - 1] == b[nbhi - 1]:
-            nahi -= 1
-            nbhi -= 1
-        recurse_matches_py(a, b, last_a_pos + 1, last_b_pos + 1,
-                           nahi, nbhi, answer, maxrecursion - 1)
-        for i in range(ahi - nahi):
-            answer.append((nahi + i, nbhi + i))
-
-
-def _collapse_sequences(matches):
-    """Find sequences of lines.
-
-    Given a sequence of [(line_in_a, line_in_b),]
-    find regions where they both increment at the same time
-    """
-    answer = []
-    start_a = start_b = None
-    length = 0
-    for i_a, i_b in matches:
-        if (start_a is not None
-                and (i_a == start_a + length)
-                and (i_b == start_b + length)):
-            length += 1
-        else:
-            if start_a is not None:
-                answer.append((start_a, start_b, length))
-            start_a = i_a
-            start_b = i_b
-            length = 1
-
-    if length != 0:
-        answer.append((start_a, start_b, length))
-
-    return answer
-
-
-def _check_consistency(answer):
-    # For consistency sake, make sure all matches are only increasing
-    next_a = -1
-    next_b = -1
-    for (a, b, match_len) in answer:
-        if a < next_a:
-            raise ValueError('Non increasing matches for a')
-        if b < next_b:
-            raise ValueError('Non increasing matches for b')
-        next_a = a + match_len
-        next_b = b + match_len
-
-
-class PatienceSequenceMatcher_py(difflib.SequenceMatcher):
-    """Compare a pair of sequences using longest common subset."""
-
-    _do_check_consistency = True
-
-    def __init__(self, isjunk=None, a='', b=''):
-        if isjunk is not None:
-            raise NotImplementedError('Currently we do not support'
-                                      ' isjunk for sequence matching')
-        difflib.SequenceMatcher.__init__(self, isjunk, a, b)
-
-    def get_matching_blocks(self):
-        """Return list of triples describing matching subsequences.
-
-        Each triple is of the form (i, j, n), and means that
-        a[i:i+n] == b[j:j+n].  The triples are monotonically increasing in
-        i and in j.
-
-        The last triple is a dummy, (len(a), len(b), 0), and is the only
-        triple with n==0.
-
-        >>> s = PatienceSequenceMatcher(None, "abxcd", "abcd")
-        >>> s.get_matching_blocks()
-        [(0, 0, 2), (3, 2, 2), (5, 4, 0)]
-        """
-        # jam 20060525 This is the python 2.4.1 difflib get_matching_blocks
-        # implementation which uses __helper. 2.4.3 got rid of helper for
-        # doing it inline with a queue.
-        # We should consider doing the same for recurse_matches
-
-        if self.matching_blocks is not None:
-            return self.matching_blocks
-
-        matches = []
-        recurse_matches_py(self.a, self.b, 0, 0,
-                           len(self.a), len(self.b), matches, 10)
-        # Matches now has individual line pairs of
-        # line A matches line B, at the given offsets
-        self.matching_blocks = _collapse_sequences(matches)
-        self.matching_blocks.append((len(self.a), len(self.b), 0))
-        if PatienceSequenceMatcher_py._do_check_consistency:
-            if __debug__:
-                _check_consistency(self.matching_blocks)
-
-        return self.matching_blocks

=== modified file 'breezy/annotate.py'
--- breezy/annotate.py	2018-11-25 20:44:56 +0000
+++ breezy/annotate.py	2019-05-28 23:22:43 +0000
@@ -32,8 +32,10 @@
 
 from .lazy_import import lazy_import
 lazy_import(globals(), """
+
+import patiencediff
+
 from breezy import (
-    patiencediff,
     tsort,
     )
 """)

=== modified file 'breezy/bzr/knit.py'
--- breezy/bzr/knit.py	2019-03-18 04:31:21 +0000
+++ breezy/bzr/knit.py	2019-05-28 23:22:43 +0000
@@ -58,12 +58,12 @@
 
 from ..lazy_import import lazy_import
 lazy_import(globals(), """
+import patiencediff
 import gzip
 
 from breezy import (
     debug,
     diff,
-    patiencediff,
     static_tuple,
     trace,
     tsort,

=== modified file 'breezy/bzr/weave.py'
--- breezy/bzr/weave.py	2018-11-11 15:40:12 +0000
+++ breezy/bzr/weave.py	2019-05-28 23:22:43 +0000
@@ -68,6 +68,7 @@
 
 from copy import copy
 import os
+import patiencediff
 
 from ..lazy_import import lazy_import
 lazy_import(globals(), """
@@ -83,7 +84,6 @@
     UnavailableRepresentation,
     )
 from ..osutils import dirname, sha, sha_strings, split_lines
-from .. import patiencediff
 from ..revision import NULL_REVISION
 from ..sixish import (
     BytesIO,

=== modified file 'breezy/commands.py'
--- breezy/commands.py	2018-11-12 01:41:38 +0000
+++ breezy/commands.py	2019-05-28 23:22:43 +0000
@@ -264,7 +264,7 @@
         names.update(cmd.aliases)
     # candidate: modified levenshtein distance against cmd_name.
     costs = {}
-    from . import patiencediff
+    import patiencediff
     for name in sorted(names):
         matcher = patiencediff.PatienceSequenceMatcher(None, cmd_name, name)
         distance = 0.0

=== modified file 'breezy/diff.py'
--- breezy/diff.py	2018-11-25 21:48:55 +0000
+++ breezy/diff.py	2019-05-28 23:22:43 +0000
@@ -25,6 +25,7 @@
 from .lazy_import import lazy_import
 lazy_import(globals(), """
 import errno
+import patiencediff
 import subprocess
 import tempfile
 
@@ -33,7 +34,6 @@
     controldir,
     errors,
     osutils,
-    patiencediff,
     textfile,
     timestamp,
     views,
@@ -93,12 +93,11 @@
 
     if sequence_matcher is None:
         sequence_matcher = patiencediff.PatienceSequenceMatcher
-    ud = patiencediff.unified_diff_bytes(oldlines, newlines,
-                                         fromfile=old_label.encode(
-                                             path_encoding, 'replace'),
-                                         tofile=new_label.encode(
-                                             path_encoding, 'replace'),
-                                         n=context_lines, sequencematcher=sequence_matcher)
+    ud = unified_diff_bytes(
+        oldlines, newlines,
+        fromfile=old_label.encode(path_encoding, 'replace'),
+        tofile=new_label.encode(path_encoding, 'replace'),
+        n=context_lines, sequencematcher=sequence_matcher)
 
     ud = list(ud)
     if len(ud) == 0:  # Identical contents, nothing to do
@@ -117,6 +116,75 @@
     to_file.write(b'\n')
 
 
+def unified_diff_bytes(a, b, fromfile=b'', tofile=b'', fromfiledate=b'',
+                       tofiledate=b'', n=3, lineterm=b'\n', sequencematcher=None):
+    r"""
+    Compare two sequences of lines; generate the delta as a unified diff.
+
+    Unified diffs are a compact way of showing line changes and a few
+    lines of context.  The number of context lines is set by 'n' which
+    defaults to three.
+
+    By default, the diff control lines (those with ---, +++, or @@) are
+    created with a trailing newline.  This is helpful so that inputs
+    created from file.readlines() result in diffs that are suitable for
+    file.writelines() since both the inputs and outputs have trailing
+    newlines.
+
+    For inputs that do not have trailing newlines, set the lineterm
+    argument to "" so that the output will be uniformly newline free.
+
+    The unidiff format normally has a header for filenames and modification
+    times.  Any or all of these may be specified using strings for
+    'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'.  The modification
+    times are normally expressed in the format returned by time.ctime().
+
+    Example:
+
+    >>> for line in bytes_unified_diff(b'one two three four'.split(),
+    ...             b'zero one tree four'.split(), b'Original', b'Current',
+    ...             b'Sat Jan 26 23:30:50 1991', b'Fri Jun 06 10:20:52 2003',
+    ...             lineterm=b''):
+    ...     print line
+    --- Original Sat Jan 26 23:30:50 1991
+    +++ Current Fri Jun 06 10:20:52 2003
+    @@ -1,4 +1,4 @@
+    +zero
+     one
+    -two
+    -three
+    +tree
+     four
+    """
+    if sequencematcher is None:
+        sequencematcher = difflib.SequenceMatcher
+
+    if fromfiledate:
+        fromfiledate = b'\t' + bytes(fromfiledate)
+    if tofiledate:
+        tofiledate = b'\t' + bytes(tofiledate)
+
+    started = False
+    for group in sequencematcher(None, a, b).get_grouped_opcodes(n):
+        if not started:
+            yield b'--- %s%s%s' % (fromfile, fromfiledate, lineterm)
+            yield b'+++ %s%s%s' % (tofile, tofiledate, lineterm)
+            started = True
+        i1, i2, j1, j2 = group[0][1], group[-1][2], group[0][3], group[-1][4]
+        yield b"@@ -%d,%d +%d,%d @@%s" % (i1 + 1, i2 - i1, j1 + 1, j2 - j1, lineterm)
+        for tag, i1, i2, j1, j2 in group:
+            if tag == 'equal':
+                for line in a[i1:i2]:
+                    yield b' ' + line
+                continue
+            if tag == 'replace' or tag == 'delete':
+                for line in a[i1:i2]:
+                    yield b'-' + line
+            if tag == 'replace' or tag == 'insert':
+                for line in b[j1:j2]:
+                    yield b'+' + line
+
+
 def _spawn_external_diff(diffcmd, capture_errors=True):
     """Spawn the external diff process, and return the child handle.
 

=== modified file 'breezy/merge.py'
--- breezy/merge.py	2019-02-14 21:45:23 +0000
+++ breezy/merge.py	2019-05-28 23:22:43 +0000
@@ -18,6 +18,8 @@
 
 from .lazy_import import lazy_import
 lazy_import(globals(), """
+import patiencediff
+
 from breezy import (
     branch as _mod_branch,
     cleanup,
@@ -26,7 +28,6 @@
     graph as _mod_graph,
     merge3,
     osutils,
-    patiencediff,
     revision as _mod_revision,
     textfile,
     trace,

=== modified file 'breezy/merge3.py'
--- breezy/merge3.py	2019-02-02 15:13:30 +0000
+++ breezy/merge3.py	2019-05-28 23:22:43 +0000
@@ -19,9 +19,11 @@
 # mbp: "you know that thing where cvs gives you conflict markers?"
 # s: "i hate that."
 
+import patiencediff
+
+
 from . import (
     errors,
-    patiencediff,
     textfile,
     )
 

=== modified file 'breezy/multiparent.py'
--- breezy/multiparent.py	2018-11-12 01:41:38 +0000
+++ breezy/multiparent.py	2019-05-28 23:22:43 +0000
@@ -24,11 +24,11 @@
 lazy_import(globals(), """
 import gzip
 import itertools
+import patiencediff
 
 from breezy import (
     bencode,
     errors,
-    patiencediff,
     ui,
     )
 """)

=== removed file 'breezy/patiencediff.py'
--- breezy/patiencediff.py	2018-11-12 01:41:38 +0000
+++ breezy/patiencediff.py	1970-01-01 00:00:00 +0000
@@ -1,239 +0,0 @@
-#!/usr/bin/env python
-# Copyright (C) 2005, 2006, 2007 Canonical Ltd
-#
-# This program is free software; you can redistribute it and/or modify
-# it under the terms of the GNU General Public License as published by
-# the Free Software Foundation; either version 2 of the License, or
-# (at your option) any later version.
-#
-# This program 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 General Public License for more details.
-#
-# You should have received a copy of the GNU General Public License
-# along with this program; if not, write to the Free Software
-# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
-
-from __future__ import absolute_import
-
-from .lazy_import import lazy_import
-lazy_import(globals(), """
-import os
-import sys
-import time
-import difflib
-""")
-
-
-__all__ = ['PatienceSequenceMatcher', 'unified_diff', 'unified_diff_bytes',
-           'unified_diff_files']
-
-
-# This is a version of unified_diff which only adds a factory parameter
-# so that you can override the default SequenceMatcher
-# this has been submitted as a patch to python
-def unified_diff(a, b, fromfile='', tofile='', fromfiledate='',
-                 tofiledate='', n=3, lineterm='\n',
-                 sequencematcher=None):
-    r"""
-    Compare two sequences of lines; generate the delta as a unified diff.
-
-    Unified diffs are a compact way of showing line changes and a few
-    lines of context.  The number of context lines is set by 'n' which
-    defaults to three.
-
-    By default, the diff control lines (those with ---, +++, or @@) are
-    created with a trailing newline.  This is helpful so that inputs
-    created from file.readlines() result in diffs that are suitable for
-    file.writelines() since both the inputs and outputs have trailing
-    newlines.
-
-    For inputs that do not have trailing newlines, set the lineterm
-    argument to "" so that the output will be uniformly newline free.
-
-    The unidiff format normally has a header for filenames and modification
-    times.  Any or all of these may be specified using strings for
-    'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'.  The modification
-    times are normally expressed in the format returned by time.ctime().
-
-    Example:
-
-    >>> for line in unified_diff('one two three four'.split(),
-    ...             'zero one tree four'.split(), 'Original', 'Current',
-    ...             'Sat Jan 26 23:30:50 1991', 'Fri Jun 06 10:20:52 2003',
-    ...             lineterm=''):
-    ...     print line
-    --- Original Sat Jan 26 23:30:50 1991
-    +++ Current Fri Jun 06 10:20:52 2003
-    @@ -1,4 +1,4 @@
-    +zero
-     one
-    -two
-    -three
-    +tree
-     four
-    """
-    if sequencematcher is None:
-        sequencematcher = difflib.SequenceMatcher
-
-    if fromfiledate:
-        fromfiledate = '\t' + str(fromfiledate)
-    if tofiledate:
-        tofiledate = '\t' + str(tofiledate)
-
-    started = False
-    for group in sequencematcher(None, a, b).get_grouped_opcodes(n):
-        if not started:
-            yield '--- %s%s%s' % (fromfile, fromfiledate, lineterm)
-            yield '+++ %s%s%s' % (tofile, tofiledate, lineterm)
-            started = True
-        i1, i2, j1, j2 = group[0][1], group[-1][2], group[0][3], group[-1][4]
-        yield "@@ -%d,%d +%d,%d @@%s" % (i1 + 1, i2 - i1, j1 + 1, j2 - j1, lineterm)
-        for tag, i1, i2, j1, j2 in group:
-            if tag == 'equal':
-                for line in a[i1:i2]:
-                    yield ' ' + line
-                continue
-            if tag == 'replace' or tag == 'delete':
-                for line in a[i1:i2]:
-                    yield '-' + line
-            if tag == 'replace' or tag == 'insert':
-                for line in b[j1:j2]:
-                    yield '+' + line
-
-
-def unified_diff_bytes(a, b, fromfile=b'', tofile=b'', fromfiledate=b'',
-                       tofiledate=b'', n=3, lineterm=b'\n', sequencematcher=None):
-    r"""
-    Compare two sequences of lines; generate the delta as a unified diff.
-
-    Unified diffs are a compact way of showing line changes and a few
-    lines of context.  The number of context lines is set by 'n' which
-    defaults to three.
-
-    By default, the diff control lines (those with ---, +++, or @@) are
-    created with a trailing newline.  This is helpful so that inputs
-    created from file.readlines() result in diffs that are suitable for
-    file.writelines() since both the inputs and outputs have trailing
-    newlines.
-
-    For inputs that do not have trailing newlines, set the lineterm
-    argument to "" so that the output will be uniformly newline free.
-
-    The unidiff format normally has a header for filenames and modification
-    times.  Any or all of these may be specified using strings for
-    'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'.  The modification
-    times are normally expressed in the format returned by time.ctime().
-
-    Example:
-
-    >>> for line in bytes_unified_diff(b'one two three four'.split(),
-    ...             b'zero one tree four'.split(), b'Original', b'Current',
-    ...             b'Sat Jan 26 23:30:50 1991', b'Fri Jun 06 10:20:52 2003',
-    ...             lineterm=b''):
-    ...     print line
-    --- Original Sat Jan 26 23:30:50 1991
-    +++ Current Fri Jun 06 10:20:52 2003
-    @@ -1,4 +1,4 @@
-    +zero
-     one
-    -two
-    -three
-    +tree
-     four
-    """
-    if sequencematcher is None:
-        sequencematcher = difflib.SequenceMatcher
-
-    if fromfiledate:
-        fromfiledate = b'\t' + bytes(fromfiledate)
-    if tofiledate:
-        tofiledate = b'\t' + bytes(tofiledate)
-
-    started = False
-    for group in sequencematcher(None, a, b).get_grouped_opcodes(n):
-        if not started:
-            yield b'--- %s%s%s' % (fromfile, fromfiledate, lineterm)
-            yield b'+++ %s%s%s' % (tofile, tofiledate, lineterm)
-            started = True
-        i1, i2, j1, j2 = group[0][1], group[-1][2], group[0][3], group[-1][4]
-        yield b"@@ -%d,%d +%d,%d @@%s" % (i1 + 1, i2 - i1, j1 + 1, j2 - j1, lineterm)
-        for tag, i1, i2, j1, j2 in group:
-            if tag == 'equal':
-                for line in a[i1:i2]:
-                    yield b' ' + line
-                continue
-            if tag == 'replace' or tag == 'delete':
-                for line in a[i1:i2]:
-                    yield b'-' + line
-            if tag == 'replace' or tag == 'insert':
-                for line in b[j1:j2]:
-                    yield b'+' + line
-
-
-def unified_diff_files(a, b, sequencematcher=None):
-    """Generate the diff for two files.
-    """
-    # Should this actually be an error?
-    if a == b:
-        return []
-    if a == '-':
-        file_a = sys.stdin
-        time_a = time.time()
-    else:
-        file_a = open(a, 'rb')
-        time_a = os.stat(a).st_mtime
-
-    if b == '-':
-        file_b = sys.stdin
-        time_b = time.time()
-    else:
-        file_b = open(b, 'rb')
-        time_b = os.stat(b).st_mtime
-
-    # TODO: Include fromfiledate and tofiledate
-    return unified_diff_bytes(file_a.readlines(), file_b.readlines(),
-                              fromfile=a, tofile=b,
-                              sequencematcher=sequencematcher)
-
-
-try:
-    from ._patiencediff_c import (
-        unique_lcs_c as unique_lcs,
-        recurse_matches_c as recurse_matches,
-        PatienceSequenceMatcher_c as PatienceSequenceMatcher
-        )
-except ImportError:
-    from ._patiencediff_py import (
-        unique_lcs_py as unique_lcs,
-        recurse_matches_py as recurse_matches,
-        PatienceSequenceMatcher_py as PatienceSequenceMatcher
-        )  # noqa: F401
-
-
-def main(args):
-    import optparse
-    p = optparse.OptionParser(usage='%prog [options] file_a file_b'
-                                    '\nFiles can be "-" to read from stdin')
-    p.add_option('--patience', dest='matcher', action='store_const', const='patience',
-                 default='patience', help='Use the patience difference algorithm')
-    p.add_option('--difflib', dest='matcher', action='store_const', const='difflib',
-                 default='patience', help='Use python\'s difflib algorithm')
-
-    algorithms = {'patience': PatienceSequenceMatcher,
-                  'difflib': difflib.SequenceMatcher}
-
-    (opts, args) = p.parse_args(args)
-    matcher = algorithms[opts.matcher]
-
-    if len(args) != 2:
-        print('You must supply 2 filenames to diff')
-        return -1
-
-    for line in unified_diff_files(args[0], args[1], sequencematcher=matcher):
-        sys.stdout.write(line)
-
-
-if __name__ == '__main__':
-    sys.exit(main(sys.argv[1:]))

=== modified file 'breezy/plugins/commitfromnews/committemplate.py'
--- breezy/plugins/commitfromnews/committemplate.py	2018-11-16 18:33:17 +0000
+++ breezy/plugins/commitfromnews/committemplate.py	2019-05-28 23:22:43 +0000
@@ -18,7 +18,9 @@
 
 from __future__ import absolute_import
 
-from ... import bugtracker, osutils, patiencediff
+import patiencediff
+
+from ... import bugtracker, osutils
 import re
 
 _BUG_MATCH = re.compile(r'lp:(\d+)')

=== modified file 'breezy/shelf_ui.py'
--- breezy/shelf_ui.py	2019-01-01 21:08:01 +0000
+++ breezy/shelf_ui.py	2019-05-28 23:22:43 +0000
@@ -16,6 +16,7 @@
 
 from __future__ import absolute_import
 
+import patiencediff
 import shutil
 import sys
 import tempfile
@@ -29,7 +30,6 @@
     errors,
     osutils,
     patches,
-    patiencediff,
     shelf,
     textfile,
     trace,

=== modified file 'breezy/tests/features.py'
--- breezy/tests/features.py	2019-02-27 03:13:15 +0000
+++ breezy/tests/features.py	2019-05-28 23:22:43 +0000
@@ -404,8 +404,6 @@
 testtools = ModuleAvailableFeature('testtools')
 flake8 = ModuleAvailableFeature('flake8.api.legacy')
 
-compiled_patiencediff_feature = ModuleAvailableFeature(
-    'breezy._patiencediff_c')
 lsprof_feature = ModuleAvailableFeature('breezy.lsprof')
 pkg_resources_feature = ModuleAvailableFeature('pkg_resources')
 

=== modified file 'breezy/tests/test_diff.py'
--- breezy/tests/test_diff.py	2018-11-25 21:48:55 +0000
+++ breezy/tests/test_diff.py	2019-05-28 23:22:43 +0000
@@ -24,8 +24,6 @@
     diff,
     errors,
     osutils,
-    patiencediff,
-    _patiencediff_py,
     revision as _mod_revision,
     revisionspec,
     revisiontree,
@@ -867,531 +865,6 @@
                               b'.*a-file(.|\n)*b-file')
 
 
-class TestPatienceDiffLib(tests.TestCase):
-
-    def setUp(self):
-        super(TestPatienceDiffLib, self).setUp()
-        self._unique_lcs = _patiencediff_py.unique_lcs_py
-        self._recurse_matches = _patiencediff_py.recurse_matches_py
-        self._PatienceSequenceMatcher = \
-            _patiencediff_py.PatienceSequenceMatcher_py
-
-    def test_diff_unicode_string(self):
-        a = ''.join([unichr(i) for i in range(4000, 4500, 3)])
-        b = ''.join([unichr(i) for i in range(4300, 4800, 2)])
-        sm = self._PatienceSequenceMatcher(None, a, b)
-        mb = sm.get_matching_blocks()
-        self.assertEqual(35, len(mb))
-
-    def test_unique_lcs(self):
-        unique_lcs = self._unique_lcs
-        self.assertEqual(unique_lcs('', ''), [])
-        self.assertEqual(unique_lcs('', 'a'), [])
-        self.assertEqual(unique_lcs('a', ''), [])
-        self.assertEqual(unique_lcs('a', 'a'), [(0, 0)])
-        self.assertEqual(unique_lcs('a', 'b'), [])
-        self.assertEqual(unique_lcs('ab', 'ab'), [(0, 0), (1, 1)])
-        self.assertEqual(unique_lcs('abcde', 'cdeab'),
-                         [(2, 0), (3, 1), (4, 2)])
-        self.assertEqual(unique_lcs('cdeab', 'abcde'),
-                         [(0, 2), (1, 3), (2, 4)])
-        self.assertEqual(unique_lcs('abXde', 'abYde'), [(0, 0), (1, 1),
-                                                        (3, 3), (4, 4)])
-        self.assertEqual(unique_lcs('acbac', 'abc'), [(2, 1)])
-
-    def test_recurse_matches(self):
-        def test_one(a, b, matches):
-            test_matches = []
-            self._recurse_matches(
-                a, b, 0, 0, len(a), len(b), test_matches, 10)
-            self.assertEqual(test_matches, matches)
-
-        test_one(['a', '', 'b', '', 'c'], ['a', 'a', 'b', 'c', 'c'],
-                 [(0, 0), (2, 2), (4, 4)])
-        test_one(['a', 'c', 'b', 'a', 'c'], ['a', 'b', 'c'],
-                 [(0, 0), (2, 1), (4, 2)])
-        # Even though 'bc' is not unique globally, and is surrounded by
-        # non-matching lines, we should still match, because they are locally
-        # unique
-        test_one('abcdbce', 'afbcgdbce', [(0, 0), (1, 2), (2, 3), (3, 5),
-                                          (4, 6), (5, 7), (6, 8)])
-
-        # recurse_matches doesn't match non-unique
-        # lines surrounded by bogus text.
-        # The update has been done in patiencediff.SequenceMatcher instead
-
-        # This is what it could be
-        #test_one('aBccDe', 'abccde', [(0,0), (2,2), (3,3), (5,5)])
-
-        # This is what it currently gives:
-        test_one('aBccDe', 'abccde', [(0, 0), (5, 5)])
-
-    def assertDiffBlocks(self, a, b, expected_blocks):
-        """Check that the sequence matcher returns the correct blocks.
-
-        :param a: A sequence to match
-        :param b: Another sequence to match
-        :param expected_blocks: The expected output, not including the final
-            matching block (len(a), len(b), 0)
-        """
-        matcher = self._PatienceSequenceMatcher(None, a, b)
-        blocks = matcher.get_matching_blocks()
-        last = blocks.pop()
-        self.assertEqual((len(a), len(b), 0), last)
-        self.assertEqual(expected_blocks, blocks)
-
-    def test_matching_blocks(self):
-        # Some basic matching tests
-        self.assertDiffBlocks('', '', [])
-        self.assertDiffBlocks([], [], [])
-        self.assertDiffBlocks('abc', '', [])
-        self.assertDiffBlocks('', 'abc', [])
-        self.assertDiffBlocks('abcd', 'abcd', [(0, 0, 4)])
-        self.assertDiffBlocks('abcd', 'abce', [(0, 0, 3)])
-        self.assertDiffBlocks('eabc', 'abce', [(1, 0, 3)])
-        self.assertDiffBlocks('eabce', 'abce', [(1, 0, 4)])
-        self.assertDiffBlocks('abcde', 'abXde', [(0, 0, 2), (3, 3, 2)])
-        self.assertDiffBlocks('abcde', 'abXYZde', [(0, 0, 2), (3, 5, 2)])
-        self.assertDiffBlocks('abde', 'abXYZde', [(0, 0, 2), (2, 5, 2)])
-        # This may check too much, but it checks to see that
-        # a copied block stays attached to the previous section,
-        # not the later one.
-        # difflib would tend to grab the trailing longest match
-        # which would make the diff not look right
-        self.assertDiffBlocks('abcdefghijklmnop', 'abcdefxydefghijklmnop',
-                              [(0, 0, 6), (6, 11, 10)])
-
-        # make sure it supports passing in lists
-        self.assertDiffBlocks(
-            ['hello there\n',
-             'world\n',
-             'how are you today?\n'],
-            ['hello there\n',
-             'how are you today?\n'],
-            [(0, 0, 1), (2, 1, 1)])
-
-        # non unique lines surrounded by non-matching lines
-        # won't be found
-        self.assertDiffBlocks('aBccDe', 'abccde', [(0, 0, 1), (5, 5, 1)])
-
-        # But they only need to be locally unique
-        self.assertDiffBlocks('aBcDec', 'abcdec', [
-                              (0, 0, 1), (2, 2, 1), (4, 4, 2)])
-
-        # non unique blocks won't be matched
-        self.assertDiffBlocks('aBcdEcdFg', 'abcdecdfg', [(0, 0, 1), (8, 8, 1)])
-
-        # but locally unique ones will
-        self.assertDiffBlocks('aBcdEeXcdFg', 'abcdecdfg', [(0, 0, 1), (2, 2, 2),
-                                                           (5, 4, 1), (7, 5, 2), (10, 8, 1)])
-
-        self.assertDiffBlocks('abbabbXd', 'cabbabxd', [(7, 7, 1)])
-        self.assertDiffBlocks('abbabbbb', 'cabbabbc', [])
-        self.assertDiffBlocks('bbbbbbbb', 'cbbbbbbc', [])
-
-    def test_matching_blocks_tuples(self):
-        # Some basic matching tests
-        self.assertDiffBlocks([], [], [])
-        self.assertDiffBlocks([('a',), ('b',), ('c,')], [], [])
-        self.assertDiffBlocks([], [('a',), ('b',), ('c,')], [])
-        self.assertDiffBlocks([('a',), ('b',), ('c,')],
-                              [('a',), ('b',), ('c,')],
-                              [(0, 0, 3)])
-        self.assertDiffBlocks([('a',), ('b',), ('c,')],
-                              [('a',), ('b',), ('d,')],
-                              [(0, 0, 2)])
-        self.assertDiffBlocks([('d',), ('b',), ('c,')],
-                              [('a',), ('b',), ('c,')],
-                              [(1, 1, 2)])
-        self.assertDiffBlocks([('d',), ('a',), ('b',), ('c,')],
-                              [('a',), ('b',), ('c,')],
-                              [(1, 0, 3)])
-        self.assertDiffBlocks([('a', 'b'), ('c', 'd'), ('e', 'f')],
-                              [('a', 'b'), ('c', 'X'), ('e', 'f')],
-                              [(0, 0, 1), (2, 2, 1)])
-        self.assertDiffBlocks([('a', 'b'), ('c', 'd'), ('e', 'f')],
-                              [('a', 'b'), ('c', 'dX'), ('e', 'f')],
-                              [(0, 0, 1), (2, 2, 1)])
-
-    def test_opcodes(self):
-        def chk_ops(a, b, expected_codes):
-            s = self._PatienceSequenceMatcher(None, a, b)
-            self.assertEqual(expected_codes, s.get_opcodes())
-
-        chk_ops('', '', [])
-        chk_ops([], [], [])
-        chk_ops('abc', '', [('delete', 0, 3, 0, 0)])
-        chk_ops('', 'abc', [('insert', 0, 0, 0, 3)])
-        chk_ops('abcd', 'abcd', [('equal', 0, 4, 0, 4)])
-        chk_ops('abcd', 'abce', [('equal', 0, 3, 0, 3),
-                                 ('replace', 3, 4, 3, 4)
-                                 ])
-        chk_ops('eabc', 'abce', [('delete', 0, 1, 0, 0),
-                                 ('equal', 1, 4, 0, 3),
-                                 ('insert', 4, 4, 3, 4)
-                                 ])
-        chk_ops('eabce', 'abce', [('delete', 0, 1, 0, 0),
-                                  ('equal', 1, 5, 0, 4)
-                                  ])
-        chk_ops('abcde', 'abXde', [('equal', 0, 2, 0, 2),
-                                   ('replace', 2, 3, 2, 3),
-                                   ('equal', 3, 5, 3, 5)
-                                   ])
-        chk_ops('abcde', 'abXYZde', [('equal', 0, 2, 0, 2),
-                                     ('replace', 2, 3, 2, 5),
-                                     ('equal', 3, 5, 5, 7)
-                                     ])
-        chk_ops('abde', 'abXYZde', [('equal', 0, 2, 0, 2),
-                                    ('insert', 2, 2, 2, 5),
-                                    ('equal', 2, 4, 5, 7)
-                                    ])
-        chk_ops('abcdefghijklmnop', 'abcdefxydefghijklmnop',
-                [('equal', 0, 6, 0, 6),
-                 ('insert', 6, 6, 6, 11),
-                 ('equal', 6, 16, 11, 21)
-                 ])
-        chk_ops(
-            ['hello there\n', 'world\n', 'how are you today?\n'],
-            ['hello there\n', 'how are you today?\n'],
-            [('equal', 0, 1, 0, 1),
-             ('delete', 1, 2, 1, 1),
-             ('equal', 2, 3, 1, 2),
-             ])
-        chk_ops('aBccDe', 'abccde',
-                [('equal', 0, 1, 0, 1),
-                 ('replace', 1, 5, 1, 5),
-                 ('equal', 5, 6, 5, 6),
-                 ])
-        chk_ops('aBcDec', 'abcdec',
-                [('equal', 0, 1, 0, 1),
-                 ('replace', 1, 2, 1, 2),
-                 ('equal', 2, 3, 2, 3),
-                 ('replace', 3, 4, 3, 4),
-                 ('equal', 4, 6, 4, 6),
-                 ])
-        chk_ops('aBcdEcdFg', 'abcdecdfg',
-                [('equal', 0, 1, 0, 1),
-                 ('replace', 1, 8, 1, 8),
-                 ('equal', 8, 9, 8, 9)
-                 ])
-        chk_ops('aBcdEeXcdFg', 'abcdecdfg',
-                [('equal', 0, 1, 0, 1),
-                 ('replace', 1, 2, 1, 2),
-                 ('equal', 2, 4, 2, 4),
-                 ('delete', 4, 5, 4, 4),
-                 ('equal', 5, 6, 4, 5),
-                 ('delete', 6, 7, 5, 5),
-                 ('equal', 7, 9, 5, 7),
-                 ('replace', 9, 10, 7, 8),
-                 ('equal', 10, 11, 8, 9)
-                 ])
-
-    def test_grouped_opcodes(self):
-        def chk_ops(a, b, expected_codes, n=3):
-            s = self._PatienceSequenceMatcher(None, a, b)
-            self.assertEqual(expected_codes, list(s.get_grouped_opcodes(n)))
-
-        chk_ops('', '', [])
-        chk_ops([], [], [])
-        chk_ops('abc', '', [[('delete', 0, 3, 0, 0)]])
-        chk_ops('', 'abc', [[('insert', 0, 0, 0, 3)]])
-        chk_ops('abcd', 'abcd', [])
-        chk_ops('abcd', 'abce', [[('equal', 0, 3, 0, 3),
-                                  ('replace', 3, 4, 3, 4)
-                                  ]])
-        chk_ops('eabc', 'abce', [[('delete', 0, 1, 0, 0),
-                                  ('equal', 1, 4, 0, 3),
-                                  ('insert', 4, 4, 3, 4)
-                                  ]])
-        chk_ops('abcdefghijklmnop', 'abcdefxydefghijklmnop',
-                [[('equal', 3, 6, 3, 6),
-                  ('insert', 6, 6, 6, 11),
-                  ('equal', 6, 9, 11, 14)
-                  ]])
-        chk_ops('abcdefghijklmnop', 'abcdefxydefghijklmnop',
-                [[('equal', 2, 6, 2, 6),
-                  ('insert', 6, 6, 6, 11),
-                  ('equal', 6, 10, 11, 15)
-                  ]], 4)
-        chk_ops('Xabcdef', 'abcdef',
-                [[('delete', 0, 1, 0, 0),
-                  ('equal', 1, 4, 0, 3)
-                  ]])
-        chk_ops('abcdef', 'abcdefX',
-                [[('equal', 3, 6, 3, 6),
-                  ('insert', 6, 6, 6, 7)
-                  ]])
-
-    def test_multiple_ranges(self):
-        # There was an earlier bug where we used a bad set of ranges,
-        # this triggers that specific bug, to make sure it doesn't regress
-        self.assertDiffBlocks('abcdefghijklmnop',
-                              'abcXghiYZQRSTUVWXYZijklmnop',
-                              [(0, 0, 3), (6, 4, 3), (9, 20, 7)])
-
-        self.assertDiffBlocks('ABCd efghIjk  L',
-                              'AxyzBCn mo pqrstuvwI1 2  L',
-                              [(0, 0, 1), (1, 4, 2), (9, 19, 1), (12, 23, 3)])
-
-        # These are rot13 code snippets.
-        self.assertDiffBlocks('''\
-    trg nqqrq jura lbh nqq n svyr va gur qverpgbel.
-    """
-    gnxrf_netf = ['svyr*']
-    gnxrf_bcgvbaf = ['ab-erphefr']
-
-    qrs eha(frys, svyr_yvfg, ab_erphefr=Snyfr):
-        sebz omeyvo.nqq vzcbeg fzneg_nqq, nqq_ercbegre_cevag, nqq_ercbegre_ahyy
-        vs vf_dhvrg():
-            ercbegre = nqq_ercbegre_ahyy
-        ryfr:
-            ercbegre = nqq_ercbegre_cevag
-        fzneg_nqq(svyr_yvfg, abg ab_erphefr, ercbegre)
-
-
-pynff pzq_zxqve(Pbzznaq):
-'''.splitlines(True), '''\
-    trg nqqrq jura lbh nqq n svyr va gur qverpgbel.
-
-    --qel-eha jvyy fubj juvpu svyrf jbhyq or nqqrq, ohg abg npghnyyl
-    nqq gurz.
-    """
-    gnxrf_netf = ['svyr*']
-    gnxrf_bcgvbaf = ['ab-erphefr', 'qel-eha']
-
-    qrs eha(frys, svyr_yvfg, ab_erphefr=Snyfr, qel_eha=Snyfr):
-        vzcbeg omeyvo.nqq
-
-        vs qel_eha:
-            vs vf_dhvrg():
-                # Guvf vf cbvagyrff, ohg V'q engure abg envfr na reebe
-                npgvba = omeyvo.nqq.nqq_npgvba_ahyy
-            ryfr:
-  npgvba = omeyvo.nqq.nqq_npgvba_cevag
-        ryvs vf_dhvrg():
-            npgvba = omeyvo.nqq.nqq_npgvba_nqq
-        ryfr:
-       npgvba = omeyvo.nqq.nqq_npgvba_nqq_naq_cevag
-
-        omeyvo.nqq.fzneg_nqq(svyr_yvfg, abg ab_erphefr, npgvba)
-
-
-pynff pzq_zxqve(Pbzznaq):
-'''.splitlines(True), [(0, 0, 1), (1, 4, 2), (9, 19, 1), (12, 23, 3)])
-
-    def test_patience_unified_diff(self):
-        txt_a = ['hello there\n',
-                 'world\n',
-                 'how are you today?\n']
-        txt_b = ['hello there\n',
-                 'how are you today?\n']
-        unified_diff = patiencediff.unified_diff
-        psm = self._PatienceSequenceMatcher
-        self.assertEqual(['--- \n',
-                          '+++ \n',
-                          '@@ -1,3 +1,2 @@\n',
-                          ' hello there\n',
-                          '-world\n',
-                          ' how are you today?\n'
-                          ], list(unified_diff(txt_a, txt_b,
-                                               sequencematcher=psm)))
-        txt_a = [x + '\n' for x in 'abcdefghijklmnop']
-        txt_b = [x + '\n' for x in 'abcdefxydefghijklmnop']
-        # This is the result with LongestCommonSubstring matching
-        self.assertEqual(['--- \n',
-                          '+++ \n',
-                          '@@ -1,6 +1,11 @@\n',
-                          ' a\n',
-                          ' b\n',
-                          ' c\n',
-                          '+d\n',
-                          '+e\n',
-                          '+f\n',
-                          '+x\n',
-                          '+y\n',
-                          ' d\n',
-                          ' e\n',
-                          ' f\n'], list(unified_diff(txt_a, txt_b)))
-        # And the patience diff
-        self.assertEqual(['--- \n',
-                          '+++ \n',
-                          '@@ -4,6 +4,11 @@\n',
-                          ' d\n',
-                          ' e\n',
-                          ' f\n',
-                          '+x\n',
-                          '+y\n',
-                          '+d\n',
-                          '+e\n',
-                          '+f\n',
-                          ' g\n',
-                          ' h\n',
-                          ' i\n',
-                          ], list(unified_diff(txt_a, txt_b,
-                                               sequencematcher=psm)))
-
-    def test_patience_unified_diff_with_dates(self):
-        txt_a = ['hello there\n',
-                 'world\n',
-                 'how are you today?\n']
-        txt_b = ['hello there\n',
-                 'how are you today?\n']
-        unified_diff = patiencediff.unified_diff
-        psm = self._PatienceSequenceMatcher
-        self.assertEqual(['--- a\t2008-08-08\n',
-                          '+++ b\t2008-09-09\n',
-                          '@@ -1,3 +1,2 @@\n',
-                          ' hello there\n',
-                          '-world\n',
-                          ' how are you today?\n'
-                          ], list(unified_diff(txt_a, txt_b,
-                                               fromfile='a', tofile='b',
-                                               fromfiledate='2008-08-08',
-                                               tofiledate='2008-09-09',
-                                               sequencematcher=psm)))
-
-
-class TestPatienceDiffLib_c(TestPatienceDiffLib):
-
-    _test_needs_features = [features.compiled_patiencediff_feature]
-
-    def setUp(self):
-        super(TestPatienceDiffLib_c, self).setUp()
-        from breezy import _patiencediff_c
-        self._unique_lcs = _patiencediff_c.unique_lcs_c
-        self._recurse_matches = _patiencediff_c.recurse_matches_c
-        self._PatienceSequenceMatcher = \
-            _patiencediff_c.PatienceSequenceMatcher_c
-
-    def test_unhashable(self):
-        """We should get a proper exception here."""
-        # We need to be able to hash items in the sequence, lists are
-        # unhashable, and thus cannot be diffed
-        e = self.assertRaises(TypeError, self._PatienceSequenceMatcher,
-                              None, [[]], [])
-        e = self.assertRaises(TypeError, self._PatienceSequenceMatcher,
-                              None, ['valid', []], [])
-        e = self.assertRaises(TypeError, self._PatienceSequenceMatcher,
-                              None, ['valid'], [[]])
-        e = self.assertRaises(TypeError, self._PatienceSequenceMatcher,
-                              None, ['valid'], ['valid', []])
-
-
-class TestPatienceDiffLibFiles(tests.TestCaseInTempDir):
-
-    def setUp(self):
-        super(TestPatienceDiffLibFiles, self).setUp()
-        self._PatienceSequenceMatcher = \
-            _patiencediff_py.PatienceSequenceMatcher_py
-
-    def test_patience_unified_diff_files(self):
-        txt_a = [b'hello there\n',
-                 b'world\n',
-                 b'how are you today?\n']
-        txt_b = [b'hello there\n',
-                 b'how are you today?\n']
-        with open('a1', 'wb') as f:
-            f.writelines(txt_a)
-        with open('b1', 'wb') as f:
-            f.writelines(txt_b)
-
-        unified_diff_files = patiencediff.unified_diff_files
-        psm = self._PatienceSequenceMatcher
-        self.assertEqual([b'--- a1\n',
-                          b'+++ b1\n',
-                          b'@@ -1,3 +1,2 @@\n',
-                          b' hello there\n',
-                          b'-world\n',
-                          b' how are you today?\n',
-                          ], list(unified_diff_files(b'a1', b'b1',
-                                                     sequencematcher=psm)))
-
-        txt_a = [x + '\n' for x in 'abcdefghijklmnop']
-        txt_b = [x + '\n' for x in 'abcdefxydefghijklmnop']
-        with open('a2', 'wt') as f:
-            f.writelines(txt_a)
-        with open('b2', 'wt') as f:
-            f.writelines(txt_b)
-
-        # This is the result with LongestCommonSubstring matching
-        self.assertEqual([b'--- a2\n',
-                          b'+++ b2\n',
-                          b'@@ -1,6 +1,11 @@\n',
-                          b' a\n',
-                          b' b\n',
-                          b' c\n',
-                          b'+d\n',
-                          b'+e\n',
-                          b'+f\n',
-                          b'+x\n',
-                          b'+y\n',
-                          b' d\n',
-                          b' e\n',
-                          b' f\n'], list(unified_diff_files(b'a2', b'b2')))
-
-        # And the patience diff
-        self.assertEqual([b'--- a2\n',
-                          b'+++ b2\n',
-                          b'@@ -4,6 +4,11 @@\n',
-                          b' d\n',
-                          b' e\n',
-                          b' f\n',
-                          b'+x\n',
-                          b'+y\n',
-                          b'+d\n',
-                          b'+e\n',
-                          b'+f\n',
-                          b' g\n',
-                          b' h\n',
-                          b' i\n'],
-                         list(unified_diff_files(b'a2', b'b2',
-                                                 sequencematcher=psm)))
-
-
-class TestPatienceDiffLibFiles_c(TestPatienceDiffLibFiles):
-
-    _test_needs_features = [features.compiled_patiencediff_feature]
-
-    def setUp(self):
-        super(TestPatienceDiffLibFiles_c, self).setUp()
-        from breezy import _patiencediff_c
-        self._PatienceSequenceMatcher = \
-            _patiencediff_c.PatienceSequenceMatcher_c
-
-
-class TestUsingCompiledIfAvailable(tests.TestCase):
-
-    def test_PatienceSequenceMatcher(self):
-        if features.compiled_patiencediff_feature.available():
-            from breezy._patiencediff_c import PatienceSequenceMatcher_c
-            self.assertIs(PatienceSequenceMatcher_c,
-                          patiencediff.PatienceSequenceMatcher)
-        else:
-            from breezy._patiencediff_py import PatienceSequenceMatcher_py
-            self.assertIs(PatienceSequenceMatcher_py,
-                          patiencediff.PatienceSequenceMatcher)
-
-    def test_unique_lcs(self):
-        if features.compiled_patiencediff_feature.available():
-            from breezy._patiencediff_c import unique_lcs_c
-            self.assertIs(unique_lcs_c,
-                          patiencediff.unique_lcs)
-        else:
-            from breezy._patiencediff_py import unique_lcs_py
-            self.assertIs(unique_lcs_py,
-                          patiencediff.unique_lcs)
-
-    def test_recurse_matches(self):
-        if features.compiled_patiencediff_feature.available():
-            from breezy._patiencediff_c import recurse_matches_c
-            self.assertIs(recurse_matches_c,
-                          patiencediff.recurse_matches)
-        else:
-            from breezy._patiencediff_py import recurse_matches_py
-            self.assertIs(recurse_matches_py,
-                          patiencediff.recurse_matches)
-
-
 class TestDiffFromTool(tests.TestCaseWithTransport):
 
     def test_from_string(self):

=== modified file 'breezy/tests/test_import_tariff.py'
--- breezy/tests/test_import_tariff.py	2018-11-11 04:08:32 +0000
+++ breezy/tests/test_import_tariff.py	2019-05-28 23:22:43 +0000
@@ -176,7 +176,6 @@
             'breezy.merge3',
             'breezy.merge_directive',
             'breezy.msgeditor',
-            'breezy.patiencediff',
             'breezy.bzr.remote',
             'breezy.rules',
             'breezy.sign_my_commits',
@@ -252,7 +251,6 @@
                                       'breezy.merge3',
                                       'breezy.merge_directive',
                                       'breezy.msgeditor',
-                                      'breezy.patiencediff',
                                       'breezy.bzr.remote',
                                       'breezy.rules',
                                       'breezy.sign_my_commits',

=== modified file 'breezy/tests/test_knit.py'
--- breezy/tests/test_knit.py	2018-11-12 01:41:38 +0000
+++ breezy/tests/test_knit.py	2019-05-28 23:22:43 +0000
@@ -18,6 +18,7 @@
 
 import gzip
 from io import BytesIO
+from patiencediff import PatienceSequenceMatcher
 import sys
 
 from .. import (
@@ -48,7 +49,6 @@
     _KnitKeyAccess,
     make_file_factory,
     )
-from ..patiencediff import PatienceSequenceMatcher
 from ..bzr import (
     knitpack_repo,
     pack_repo,

=== modified file 'breezy/tests/test_multiparent.py'
--- breezy/tests/test_multiparent.py	2018-11-12 01:41:38 +0000
+++ breezy/tests/test_multiparent.py	2019-05-28 23:22:43 +0000
@@ -14,11 +14,11 @@
 # along with this program; if not, write to the Free Software
 # Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
+import patiencediff
 from unittest import TestCase
 
 from .. import (
     multiparent,
-    patiencediff,
     tests,
     )
 from ..sixish import int2byte

=== modified file 'breezy/textmerge.py'
--- breezy/textmerge.py	2018-11-11 04:08:32 +0000
+++ breezy/textmerge.py	2019-05-28 23:22:43 +0000
@@ -21,7 +21,7 @@
 
 from .lazy_import import lazy_import
 lazy_import(globals(), """
-from breezy import patiencediff
+import patiencediff
 """)
 
 

=== modified file 'byov.conf'
--- byov.conf	2019-05-27 03:53:43 +0000
+++ byov.conf	2019-05-28 23:22:43 +0000
@@ -13,6 +13,8 @@
 sphinx_epytext.install3 = (pip3 install sphinx_epytext)
 flake8.install = (pip install flake8)
 flake8.install3 = (pip3 install flake8)
+patiencediff.install = (pip install patiencediff)
+patiencediff.install3 = (pip3 install patiencediff)
 cython.install = (pip install cython)
 cython.install3 = (pip3 install cython)
 
@@ -32,7 +34,7 @@
 vm.packages = {brz.build_deps}, {subunit.build_deps}, bzr, git, python-junitxml
 [brz-xenial]
 vm.release = xenial
-byoci.setup.command = ({dulwich.clone} && {dulwich.install} && {dulwich.install3} && {fastimport.clone} && {fastimport.install} && {fastimport.install3} && {subunit.clone} && {flake8.install} && {flake8.install3} && {sphinx_epytext.install} && {sphinx_epytext.install3} && {cython.install} && {cython.install3})
+byoci.setup.command = ({dulwich.clone} && {dulwich.install} && {dulwich.install3} && {fastimport.clone} && {fastimport.install} && {fastimport.install3} && {subunit.clone} && {flake8.install} && {flake8.install3} && {patiencediff.install} && {patiencediff.install3} && {sphinx_epytext.install} && {sphinx_epytext.install3} && {cython.install} && {cython.install3})
 # FIXME: bzr log -l2 should be by default -- vila 2018-03-09
 byoci.tests.command = bash -o pipefail -c "bzr log -l2 && PYTHONPATH=../subunit/python:$PYTHONPATH PATH=../subunit/filters:$HOME/.local/bin:$PATH make check-ci | subunit2junitxml -o ../results.xml -f | subunit2pyunit"
 [brz-bionic]

=== modified file 'setup.py'
--- setup.py	2019-03-04 10:39:09 +0000
+++ setup.py	2019-05-28 23:22:43 +0000
@@ -65,6 +65,7 @@
     'install_requires': [
         'configobj',
         'six>=1.9.0',
+        'patiencediff',
         # Technically, Breezy works without these two dependencies too. But there's
         # no way to enable them by default and let users opt out.
         'fastimport>=0.9.8',
@@ -334,8 +335,6 @@
     add_cython_extension('breezy.bzr._dirstate_helpers_pyx')
     add_cython_extension('breezy._readdir_pyx')
 add_cython_extension('breezy.bzr._chk_map_pyx')
-ext_modules.append(Extension('breezy._patiencediff_c',
-                             ['breezy/_patiencediff_c.c']))
 add_cython_extension('breezy.bzr._btree_serializer_pyx')