~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_patiencediff_c.c

  • Committer: John Arbash Meinel
  • Date: 2007-04-30 17:45:10 UTC
  • mfrom: (2472.3.2 renamed_file_111288)
  • mto: This revision was merged to the branch mainline in revision 2475.
  • Revision ID: john@arbash-meinel.com-20070430174510-qdteh5dy45gbj785
[merge] bugfix for bug #111288, resolve conflicts.

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
/*
2
 
 Copyright (C) 2007, 2010 Canonical Ltd
3
 
 
4
 
 This program is free software; you can redistribute it and/or modify
5
 
 it under the terms of the GNU General Public License as published by
6
 
 the Free Software Foundation; either version 2 of the License, or
7
 
 (at your option) any later version.
8
 
 
9
 
 This program is distributed in the hope that it will be useful,
10
 
 but WITHOUT ANY WARRANTY; without even the implied warranty of
11
 
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12
 
 GNU General Public License for more details.
13
 
 
14
 
 You should have received a copy of the GNU General Public License
15
 
 along with this program; if not, write to the Free Software
16
 
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
 
 
18
 
 Function equate_lines based on bdiff.c from Mercurial.
19
 
   Copyright (C) 2005, 2006 Matt Mackall <mpm@selenic.com>
20
 
 
21
 
 Functions unique_lcs/recurse_matches based on _patiencediff_py.py.
22
 
   Copyright (C) 2005 Bram Cohen, Copyright (C) 2005, 2006 Canonical Ltd
23
 
*/
24
 
 
25
 
 
26
 
#include <stdlib.h>
27
 
#include <string.h>
28
 
#include <Python.h>
29
 
 
30
 
#include "python-compat.h"
31
 
 
32
 
 
33
 
#if defined(__GNUC__)
34
 
#   define inline __inline__
35
 
#elif defined(_MSC_VER)
36
 
#   define inline __inline
37
 
#else
38
 
#   define inline
39
 
#endif
40
 
 
41
 
 
42
 
#define MIN(a, b) (((a) > (b)) ? (b) : (a))
43
 
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
44
 
 
45
 
 
46
 
#define SENTINEL -1
47
 
 
48
 
 
49
 
/* malloc returns NULL on some platforms if you try to allocate nothing,
50
 
 * causing <https://bugs.edge.launchpad.net/bzr/+bug/511267> and
51
 
 * <https://bugs.edge.launchpad.net/bzr/+bug/331095>.  On glibc it passes, but
52
 
 * let's make it fail to aid testing. */
53
 
#define guarded_malloc(x) ( (x) ? malloc(x) : NULL )
54
 
 
55
 
enum {
56
 
    OP_EQUAL = 0,
57
 
    OP_INSERT,
58
 
    OP_DELETE,
59
 
    OP_REPLACE
60
 
};
61
 
 
62
 
 
63
 
/* values from this array need to correspont to the order of the enum above */
64
 
static char *opcode_names[] = {
65
 
    "equal",
66
 
    "insert",
67
 
    "delete",
68
 
    "replace",
69
 
};
70
 
 
71
 
 
72
 
struct line {
73
 
    long hash;         /* hash code of the string/object */
74
 
    Py_ssize_t next;   /* next line from the same equivalence class */
75
 
    Py_ssize_t equiv;  /* equivalence class */
76
 
    PyObject *data;
77
 
};
78
 
 
79
 
 
80
 
struct bucket {
81
 
    Py_ssize_t a_head;  /* first item in `a` from this equivalence class */
82
 
    Py_ssize_t a_count;
83
 
    Py_ssize_t b_head;  /* first item in `b` from this equivalence class */
84
 
    Py_ssize_t b_count;
85
 
    Py_ssize_t a_pos;
86
 
    Py_ssize_t b_pos;
87
 
};
88
 
 
89
 
 
90
 
struct hashtable {
91
 
    Py_ssize_t last_a_pos;
92
 
    Py_ssize_t last_b_pos;
93
 
    Py_ssize_t size;
94
 
    struct bucket *table;
95
 
};
96
 
 
97
 
struct matching_line {
98
 
    Py_ssize_t a;     /* index of the line in `a` */
99
 
    Py_ssize_t b;     /* index of the line in `b` */
100
 
};
101
 
 
102
 
 
103
 
struct matching_block {
104
 
    Py_ssize_t a;     /* index of the first line in `a` */
105
 
    Py_ssize_t b;     /* index of the first line in `b` */
106
 
    Py_ssize_t len;   /* length of the block */
107
 
};
108
 
 
109
 
 
110
 
struct matching_blocks {
111
 
    struct matching_block *matches;
112
 
    Py_ssize_t count;
113
 
};
114
 
 
115
 
 
116
 
struct opcode {
117
 
    int tag;
118
 
    Py_ssize_t i1;
119
 
    Py_ssize_t i2;
120
 
    Py_ssize_t j1;
121
 
    Py_ssize_t j2;
122
 
};
123
 
 
124
 
 
125
 
typedef struct {
126
 
    PyObject_HEAD
127
 
    Py_ssize_t asize;
128
 
    Py_ssize_t bsize;
129
 
    struct line *a;
130
 
    struct line *b;
131
 
    struct hashtable hashtable;
132
 
    Py_ssize_t *backpointers;
133
 
} PatienceSequenceMatcher;
134
 
 
135
 
 
136
 
static inline Py_ssize_t
137
 
bisect_left(Py_ssize_t *list, Py_ssize_t item, Py_ssize_t lo, Py_ssize_t hi)
138
 
{
139
 
    while (lo < hi) {
140
 
        Py_ssize_t mid = lo / 2 + hi / 2 + (lo % 2 + hi % 2) / 2;
141
 
        if (list[mid] < item)
142
 
            lo = mid + 1;
143
 
        else
144
 
            hi = mid;
145
 
    }
146
 
    return lo;
147
 
}
148
 
 
149
 
 
150
 
static inline int
151
 
compare_lines(struct line *a, struct line *b)
152
 
{
153
 
    return ((a->hash != b->hash)
154
 
            || PyObject_Compare(a->data, b->data));
155
 
}
156
 
 
157
 
 
158
 
static inline int
159
 
find_equivalence_class(struct bucket *hashtable, Py_ssize_t hsize,
160
 
                       struct line *lines, struct line *ref_lines,
161
 
                       Py_ssize_t i)
162
 
{
163
 
    Py_ssize_t j;
164
 
    for (j = lines[i].hash & hsize; hashtable[j].b_head != SENTINEL; j = (j + 1) & hsize) {
165
 
        if (!compare_lines(lines + i, ref_lines + hashtable[j].b_head)) {
166
 
            break;
167
 
        }
168
 
    }
169
 
    return j;
170
 
}
171
 
 
172
 
 
173
 
static int
174
 
equate_lines(struct hashtable *result,
175
 
             struct line *lines_a, struct line *lines_b,
176
 
             Py_ssize_t asize, Py_ssize_t bsize)
177
 
{
178
 
    Py_ssize_t i, j, hsize;
179
 
    struct bucket *hashtable;
180
 
 
181
 
    /* check for overflow, we need the table to be at least bsize+1 */
182
 
    if (bsize == PY_SSIZE_T_MAX) {
183
 
        PyErr_SetNone(PyExc_OverflowError);
184
 
        return 0;
185
 
    }
186
 
 
187
 
    /* build a hash table of the next highest power of 2 */
188
 
    hsize = 1;
189
 
    while (hsize < bsize + 1)
190
 
        hsize *= 2;
191
 
 
192
 
    /* can't be 0 */
193
 
    hashtable = (struct bucket *) guarded_malloc(sizeof(struct bucket) * hsize);
194
 
    if (hashtable == NULL) {
195
 
        PyErr_NoMemory();
196
 
        return 0;
197
 
    }
198
 
 
199
 
    /* initialise the hashtable */
200
 
    for (i = 0; i < hsize; i++) {
201
 
        hashtable[i].a_count = 0;
202
 
        hashtable[i].b_count = 0;
203
 
        hashtable[i].a_head = SENTINEL;
204
 
        hashtable[i].b_head = SENTINEL;
205
 
    }
206
 
    hsize--;
207
 
 
208
 
    /* add lines from lines_b to the hash table chains. iterating
209
 
       backwards so the matching lines are sorted to the linked list
210
 
       by the line number (because we are adding new lines to the
211
 
       head of the list) */
212
 
    for (i = bsize - 1; i >= 0; i--) {
213
 
        /* find the first hashtable entry, which is either empty or contains
214
 
           the same line as lines_b[i] */
215
 
        j = find_equivalence_class(hashtable, hsize, lines_b, lines_b, i);
216
 
 
217
 
        /* set the equivalence class */
218
 
        lines_b[i].equiv = j;
219
 
 
220
 
        /* add to the head of the equivalence class */
221
 
        lines_b[i].next = hashtable[j].b_head;
222
 
        hashtable[j].b_head = i;
223
 
        hashtable[j].b_count++;
224
 
    }
225
 
 
226
 
    /* match items from lines_a to their equivalence class in lines_b.
227
 
       again, iterating backwards for the right order of the linked lists */
228
 
    for (i = asize - 1; i >= 0; i--) {
229
 
        /* find the first hash entry, which is either empty or contains
230
 
           the same line as lines_a[i] */
231
 
        j = find_equivalence_class(hashtable, hsize, lines_a, lines_b, i);
232
 
 
233
 
        /* set the equivalence class, even if we are not interested in this
234
 
           line, because the values are not pre-filled */
235
 
        lines_a[i].equiv = j;
236
 
 
237
 
        /* we are not interested in lines which are not also in lines_b */
238
 
        if (hashtable[j].b_head == SENTINEL)
239
 
            continue;
240
 
 
241
 
        /* add to the head of the equivalence class */
242
 
        lines_a[i].next = hashtable[j].a_head;
243
 
        hashtable[j].a_head = i;
244
 
        hashtable[j].a_count++;
245
 
    }
246
 
 
247
 
    result->last_a_pos = -1;
248
 
    result->last_b_pos = -1;
249
 
    result->size = hsize + 1;
250
 
    result->table = hashtable;
251
 
 
252
 
    return 1;
253
 
}
254
 
 
255
 
 
256
 
 
257
 
/* Finds longest common subsequence of unique lines in a[alo:ahi] and
258
 
   b[blo:bhi].
259
 
   Parameter backpointers must have allocated memory for at least
260
 
   4 * (bhi - blo) ints. */
261
 
Py_ssize_t
262
 
unique_lcs(struct matching_line *answer,
263
 
           struct hashtable *hashtable, Py_ssize_t *backpointers,
264
 
           struct line *lines_a, struct line *lines_b,
265
 
           Py_ssize_t alo, Py_ssize_t blo, Py_ssize_t ahi, Py_ssize_t bhi)
266
 
{
267
 
    Py_ssize_t i, k, equiv, apos, bpos, norm_apos, norm_bpos, bsize, stacksize;
268
 
    Py_ssize_t *stacks, *lasts, *btoa;
269
 
    struct bucket *h;
270
 
 
271
 
    k = 0;
272
 
    stacksize = 0;
273
 
    bsize = bhi - blo;
274
 
    h = hashtable->table;
275
 
 
276
 
    /* "unpack" the allocated memory */
277
 
    stacks = backpointers + bsize;
278
 
    lasts = stacks + bsize;
279
 
    btoa = lasts + bsize;
280
 
 
281
 
    /* initialise the backpointers */
282
 
    for (i = 0; i < bsize; i++)
283
 
        backpointers[i] = SENTINEL;
284
 
 
285
 
    if (hashtable->last_a_pos == -1 || hashtable->last_a_pos > alo)
286
 
        for (i = 0; i < hashtable->size; i++)
287
 
            h[i].a_pos = h[i].a_head;
288
 
    hashtable->last_a_pos = alo;
289
 
 
290
 
    if (hashtable->last_b_pos == -1 || hashtable->last_b_pos > blo)
291
 
        for (i = 0; i < hashtable->size; i++)
292
 
            h[i].b_pos = h[i].b_head;
293
 
    hashtable->last_b_pos = blo;
294
 
 
295
 
    for (bpos = blo; bpos < bhi; bpos++) {
296
 
        equiv = lines_b[bpos].equiv;
297
 
 
298
 
        /* no lines in a or b  */
299
 
        if (h[equiv].a_count == 0 || h[equiv].b_count == 0)
300
 
            continue;
301
 
 
302
 
        /* find an unique line in lines_a that matches lines_b[bpos]
303
 
           if we find more than one line within the range alo:ahi,
304
 
           jump to the next line from lines_b immediately */
305
 
        apos = SENTINEL;
306
 
        /* loop through all lines in the linked list */
307
 
        for (i = h[equiv].a_pos; i != SENTINEL; i = lines_a[i].next) {
308
 
            /* the index is lower than alo, continue to the next line */
309
 
            if (i < alo) {
310
 
                h[equiv].a_pos = i;
311
 
                continue;
312
 
            }
313
 
            /* the index is higher than ahi, stop searching */
314
 
            if (i >= ahi)
315
 
                break;
316
 
            /* if the line is within our range, check if it's a duplicate */
317
 
            if (apos != SENTINEL)
318
 
                goto nextb;
319
 
            /* save index to the line */
320
 
            apos = i;
321
 
        }
322
 
        /* this line has no equivalent in lines_a[alo:ahi] */
323
 
        if (apos == SENTINEL)
324
 
            goto nextb;
325
 
 
326
 
        /* check for duplicates of this line in lines_b[blo:bhi] */
327
 
        /* loop through all lines in the linked list */
328
 
        for (i = h[equiv].b_pos; i != SENTINEL; i = lines_b[i].next) {
329
 
            /* the index is lower than blo, continue to the next line */
330
 
            if (i < blo) {
331
 
                h[equiv].b_pos = i;
332
 
                continue;
333
 
            }
334
 
            /* the index is higher than bhi, stop searching */
335
 
            if (i >= bhi)
336
 
                break;
337
 
            /* if this isn't the line with started with and it's within
338
 
               our range, it's a duplicate */
339
 
            if (i != bpos)
340
 
                goto nextb;
341
 
        }
342
 
 
343
 
        /* use normalised indexes ([0,ahi-alo) instead of [alo,ahi))
344
 
           for the patience sorting algorithm */
345
 
        norm_bpos = bpos - blo;
346
 
        norm_apos = apos - alo;
347
 
        btoa[norm_bpos] = norm_apos;
348
 
 
349
 
        /*
350
 
        Ok, how does this work...
351
 
 
352
 
        We have a list of matching lines from two lists, a and b. These
353
 
        matches are stored in variable `btoa`. As we are iterating over this
354
 
        table by bpos, the lines from b already form an increasing sequence.
355
 
        We need to "sort" also the lines from a using the patience sorting
356
 
        algorithm, ignoring the lines which would need to be swapped.
357
 
 
358
 
          http://en.wikipedia.org/wiki/Patience_sorting
359
 
 
360
 
        For each pair of lines, we need to place the line from a on either
361
 
        an existing pile that has higher value on the top or create a new
362
 
        pile. Variable `stacks` represents the tops of these piles and in
363
 
        variable `lasts` we store the lines from b, that correspond to the
364
 
        lines from a in `stacks`.
365
 
 
366
 
        Whenever we place a new line on top of a pile, we store a
367
 
        backpointer to the line (b) from top of the previous pile. This means
368
 
        that after the loop, variable `backpointers` will contain an index
369
 
        to the previous matching lines that forms an increasing sequence
370
 
        (over both indexes a and b) with the current matching lines. If
371
 
        either index a or b of the previous matching lines would be higher
372
 
        than indexes of the current one or if the indexes of the current
373
 
        one are 0, it will contain SENTINEL.
374
 
 
375
 
        To construct the LCS, we will just need to follow these backpointers
376
 
        from the top of the last pile and stop when we reach SENTINEL.
377
 
        */
378
 
 
379
 
        /* as an optimization, check if the next line comes at the end,
380
 
           because it usually does */
381
 
        if (stacksize && stacks[stacksize - 1] < norm_apos)
382
 
            k = stacksize;
383
 
        /* as an optimization, check if the next line comes right after
384
 
           the previous line, because usually it does */
385
 
        else if (stacksize && (stacks[k] < norm_apos) &&
386
 
                 (k == stacksize - 1 || stacks[k + 1] > norm_apos))
387
 
            k += 1;
388
 
        else
389
 
            k = bisect_left(stacks, norm_apos, 0, stacksize);
390
 
 
391
 
        if (k > 0)
392
 
            backpointers[norm_bpos] = lasts[k - 1];
393
 
 
394
 
        if (k < stacksize) {
395
 
            stacks[k] = norm_apos;
396
 
            lasts[k] = norm_bpos;
397
 
        }
398
 
        else {
399
 
            stacks[stacksize] = norm_apos;
400
 
            lasts[stacksize] = norm_bpos;
401
 
            stacksize += 1;
402
 
        }
403
 
 
404
 
 
405
 
nextb:
406
 
        ;
407
 
    }
408
 
 
409
 
    if (stacksize == 0)
410
 
        return 0;
411
 
 
412
 
    /* backtrace the structures to find the LCS */
413
 
    i = 0;
414
 
    k = lasts[stacksize - 1];
415
 
    while (k != SENTINEL) {
416
 
        answer[i].a = btoa[k];
417
 
        answer[i].b = k;
418
 
        k = backpointers[k];
419
 
        i++;
420
 
    }
421
 
 
422
 
    return i;
423
 
}
424
 
 
425
 
/* Adds a new line to the list of matching blocks, either extending the
426
 
   current block or adding a new one. */
427
 
static inline void
428
 
add_matching_line(struct matching_blocks *answer, Py_ssize_t a, Py_ssize_t b)
429
 
{
430
 
    Py_ssize_t last_index = answer->count - 1;
431
 
    if ((last_index >= 0) &&
432
 
        (a == answer->matches[last_index].a +
433
 
              answer->matches[last_index].len) &&
434
 
        (b == answer->matches[last_index].b +
435
 
              answer->matches[last_index].len)) {
436
 
        /* enlarge the last block */
437
 
        answer->matches[last_index].len++;
438
 
    }
439
 
    else {
440
 
        /* create a new block */
441
 
        last_index++;
442
 
        answer->matches[last_index].a = a;
443
 
        answer->matches[last_index].b = b;
444
 
        answer->matches[last_index].len = 1;
445
 
        answer->count++;
446
 
    }
447
 
}
448
 
 
449
 
 
450
 
static int
451
 
recurse_matches(struct matching_blocks *answer, struct hashtable *hashtable,
452
 
                Py_ssize_t *backpointers, struct line *a, struct line *b,
453
 
                Py_ssize_t alo, Py_ssize_t blo, Py_ssize_t ahi, Py_ssize_t bhi,
454
 
                int maxrecursion)
455
 
{
456
 
    int res;
457
 
    Py_ssize_t new, last_a_pos, last_b_pos, lcs_size, nahi, nbhi, i, apos, bpos;
458
 
    struct matching_line *lcs;
459
 
 
460
 
    if (maxrecursion < 0)
461
 
        return 1;
462
 
 
463
 
    if (alo == ahi || blo == bhi)
464
 
        return 1;
465
 
 
466
 
    new = 0;
467
 
    last_a_pos = alo - 1;
468
 
    last_b_pos = blo - 1;
469
 
 
470
 
    lcs = (struct matching_line *)guarded_malloc(sizeof(struct matching_line) * (bhi - blo));
471
 
    if (lcs == NULL)
472
 
        return 0;
473
 
 
474
 
    lcs_size = unique_lcs(lcs, hashtable, backpointers, a, b, alo, blo, ahi, bhi);
475
 
 
476
 
    /* recurse between lines which are unique in each file and match */
477
 
    for (i = lcs_size - 1; i >= 0; i--) {
478
 
        apos = alo + lcs[i].a;
479
 
        bpos = blo + lcs[i].b;
480
 
        if (last_a_pos + 1 != apos || last_b_pos + 1 != bpos) {
481
 
            res = recurse_matches(answer, hashtable,
482
 
                                  backpointers, a, b,
483
 
                                  last_a_pos + 1, last_b_pos + 1,
484
 
                                  apos, bpos, maxrecursion - 1);
485
 
            if (!res)
486
 
                goto error;
487
 
        }
488
 
        last_a_pos = apos;
489
 
        last_b_pos = bpos;
490
 
        add_matching_line(answer, apos, bpos);
491
 
        new = 1;
492
 
    }
493
 
 
494
 
    free(lcs);
495
 
    lcs = NULL;
496
 
 
497
 
    /* find matches between the last match and the end */
498
 
    if (new > 0) {
499
 
        res = recurse_matches(answer, hashtable,
500
 
                              backpointers, a, b,
501
 
                              last_a_pos + 1, last_b_pos + 1,
502
 
                              ahi, bhi, maxrecursion - 1);
503
 
        if (!res)
504
 
            goto error;
505
 
    }
506
 
 
507
 
 
508
 
    /* find matching lines at the very beginning */
509
 
    else if (a[alo].equiv == b[blo].equiv) {
510
 
        while (alo < ahi && blo < bhi && a[alo].equiv == b[blo].equiv)
511
 
            add_matching_line(answer, alo++, blo++);
512
 
        res = recurse_matches(answer, hashtable,
513
 
                              backpointers, a, b,
514
 
                              alo, blo, ahi, bhi, maxrecursion - 1);
515
 
        if (!res)
516
 
            goto error;
517
 
    }
518
 
 
519
 
    /* find matching lines at the very end */
520
 
    else if (a[ahi - 1].equiv == b[bhi - 1].equiv) {
521
 
        nahi = ahi - 1;
522
 
        nbhi = bhi - 1;
523
 
        while (nahi > alo && nbhi > blo && a[nahi - 1].equiv == b[nbhi - 1].equiv) {
524
 
            nahi--;
525
 
            nbhi--;
526
 
        }
527
 
        res = recurse_matches(answer, hashtable,
528
 
                              backpointers, a, b,
529
 
                              last_a_pos + 1, last_b_pos + 1,
530
 
                              nahi, nbhi, maxrecursion - 1);
531
 
        if (!res)
532
 
            goto error;
533
 
        for (i = 0; i < ahi - nahi; i++)
534
 
            add_matching_line(answer, nahi + i, nbhi + i);
535
 
    }
536
 
 
537
 
    return 1;
538
 
 
539
 
error:
540
 
    free(lcs);
541
 
    return 0;
542
 
}
543
 
 
544
 
 
545
 
static void
546
 
delete_lines(struct line *lines, Py_ssize_t size)
547
 
{
548
 
    struct line *line = lines;
549
 
    while (size-- > 0) {
550
 
        Py_XDECREF(line->data);
551
 
        line++;
552
 
    }
553
 
    free(lines);
554
 
}
555
 
 
556
 
 
557
 
static Py_ssize_t
558
 
load_lines(PyObject *orig, struct line **lines)
559
 
{
560
 
    Py_ssize_t size, i;
561
 
    struct line *line;
562
 
    PyObject *seq, *item;
563
 
 
564
 
    seq = PySequence_Fast(orig, "sequence expected");
565
 
    if (seq == NULL) {
566
 
        return -1;
567
 
    }
568
 
 
569
 
    size = PySequence_Fast_GET_SIZE(seq);
570
 
    if (size == 0) {
571
 
        Py_DECREF(seq);
572
 
        return 0;
573
 
    }
574
 
 
575
 
    /* Allocate a memory block for line data, initialized to 0 */
576
 
    line = *lines = (struct line *)calloc(size, sizeof(struct line));
577
 
    if (line == NULL) {
578
 
        PyErr_NoMemory();
579
 
        Py_DECREF(seq);
580
 
        return -1;
581
 
    }
582
 
 
583
 
    for (i = 0; i < size; i++) {
584
 
        item = PySequence_Fast_GET_ITEM(seq, i);
585
 
        Py_INCREF(item);
586
 
        line->data = item;
587
 
        line->hash = PyObject_Hash(item);
588
 
        if (line->hash == (-1)) {
589
 
            /* Propogate the hash exception */
590
 
            size = -1;
591
 
            goto cleanup;
592
 
        }
593
 
        line->next = SENTINEL;
594
 
        line++;
595
 
    }
596
 
 
597
 
    cleanup:
598
 
    Py_DECREF(seq);
599
 
    if (size == -1) {
600
 
        /* Error -- cleanup unused object references */
601
 
        delete_lines(*lines, i);
602
 
        *lines = NULL;
603
 
    }
604
 
    return size;
605
 
}
606
 
 
607
 
 
608
 
static PyObject *
609
 
py_unique_lcs(PyObject *self, PyObject *args)
610
 
{
611
 
    PyObject *aseq, *bseq, *res, *item;
612
 
    Py_ssize_t asize, bsize, i, nmatches, *backpointers = NULL;
613
 
    struct line *a = NULL, *b = NULL;
614
 
    struct matching_line *matches = NULL;
615
 
    struct hashtable hashtable;
616
 
 
617
 
    if (!PyArg_ParseTuple(args, "OO", &aseq, &bseq))
618
 
        return NULL;
619
 
 
620
 
    hashtable.table = NULL;
621
 
 
622
 
    asize = load_lines(aseq, &a);
623
 
    bsize = load_lines(bseq, &b);
624
 
    if (asize == -1 || bsize == -1)
625
 
        goto error;
626
 
 
627
 
    if (!equate_lines(&hashtable, a, b, asize, bsize))
628
 
        goto error;
629
 
 
630
 
    if (bsize > 0) {
631
 
        matches = (struct matching_line *)guarded_malloc(sizeof(struct matching_line) * bsize);
632
 
        if (matches == NULL)
633
 
            goto error;
634
 
 
635
 
        backpointers = (Py_ssize_t *)guarded_malloc(sizeof(Py_ssize_t) * bsize * 4);
636
 
        if (backpointers == NULL)
637
 
            goto error;
638
 
    }
639
 
 
640
 
    nmatches = unique_lcs(matches, &hashtable, backpointers, a, b, 0, 0, asize, bsize);
641
 
 
642
 
    res = PyList_New(nmatches);
643
 
    for (i = 0; i < nmatches; i++) {
644
 
#if PY_VERSION_HEX < 0x02050000
645
 
        item = Py_BuildValue("ii", matches[nmatches - i - 1].a, matches[nmatches - i - 1].b);
646
 
#else
647
 
        item = Py_BuildValue("nn", matches[nmatches - i - 1].a, matches[nmatches - i - 1].b);
648
 
#endif
649
 
        if (item == NULL)
650
 
            goto error;
651
 
        if (PyList_SetItem(res, i, item) != 0)
652
 
            goto error;
653
 
    }
654
 
 
655
 
    free(backpointers);
656
 
    free(matches);
657
 
    free(hashtable.table);
658
 
    delete_lines(b, bsize);
659
 
    delete_lines(a, asize);
660
 
    return res;
661
 
 
662
 
error:
663
 
    free(backpointers);
664
 
    free(matches);
665
 
    free(hashtable.table);
666
 
    delete_lines(b, bsize);
667
 
    delete_lines(a, asize);
668
 
    return NULL;
669
 
}
670
 
 
671
 
 
672
 
static PyObject *
673
 
py_recurse_matches(PyObject *self, PyObject *args)
674
 
{
675
 
    PyObject *aseq, *bseq, *item, *answer;
676
 
    int maxrecursion, res;
677
 
    Py_ssize_t i, j, asize, bsize, alo, blo, ahi, bhi;
678
 
    Py_ssize_t *backpointers = NULL;
679
 
    struct line *a = NULL, *b = NULL;
680
 
    struct hashtable hashtable;
681
 
    struct matching_blocks matches;
682
 
 
683
 
#if PY_VERSION_HEX < 0x02050000
684
 
    if (!PyArg_ParseTuple(args, "OOiiiiOi", &aseq, &bseq, &alo, &blo,
685
 
                          &ahi, &bhi, &answer, &maxrecursion))
686
 
#else
687
 
    if (!PyArg_ParseTuple(args, "OOnnnnOi", &aseq, &bseq, &alo, &blo,
688
 
                          &ahi, &bhi, &answer, &maxrecursion))
689
 
#endif
690
 
        return NULL;
691
 
 
692
 
    hashtable.table = NULL;
693
 
    matches.matches = NULL;
694
 
 
695
 
    asize = load_lines(aseq, &a);
696
 
    bsize = load_lines(bseq, &b);
697
 
    if (asize == -1 || bsize == -1)
698
 
        goto error;
699
 
 
700
 
    if (!equate_lines(&hashtable, a, b, asize, bsize))
701
 
        goto error;
702
 
 
703
 
    matches.count = 0;
704
 
 
705
 
    if (bsize > 0) {
706
 
        matches.matches = (struct matching_block *)guarded_malloc(sizeof(struct matching_block) * bsize);
707
 
        if (matches.matches == NULL)
708
 
            goto error;
709
 
 
710
 
        backpointers = (Py_ssize_t *)guarded_malloc(sizeof(Py_ssize_t) * bsize * 4);
711
 
        if (backpointers == NULL)
712
 
            goto error;
713
 
    } else {
714
 
        matches.matches = NULL;
715
 
        backpointers = NULL;
716
 
    }
717
 
 
718
 
    res = recurse_matches(&matches, &hashtable, backpointers,
719
 
                          a, b, alo, blo, ahi, bhi, maxrecursion);
720
 
    if (!res)
721
 
        goto error;
722
 
 
723
 
    for (i = 0; i < matches.count; i++) {
724
 
        for (j = 0; j < matches.matches[i].len; j++) {
725
 
#if PY_VERSION_HEX < 0x02050000
726
 
            item = Py_BuildValue("ii", matches.matches[i].a + j,
727
 
                                 matches.matches[i].b + j);
728
 
#else
729
 
            item = Py_BuildValue("nn", matches.matches[i].a + j,
730
 
                                 matches.matches[i].b + j);
731
 
#endif
732
 
            if (item == NULL)
733
 
                goto error;
734
 
            if (PyList_Append(answer, item) != 0)
735
 
                goto error;
736
 
        }
737
 
    }
738
 
 
739
 
    free(backpointers);
740
 
    free(matches.matches);
741
 
    free(hashtable.table);
742
 
    delete_lines(b, bsize);
743
 
    delete_lines(a, asize);
744
 
    Py_RETURN_NONE;
745
 
 
746
 
error:
747
 
    free(backpointers);
748
 
    free(matches.matches);
749
 
    free(hashtable.table);
750
 
    delete_lines(b, bsize);
751
 
    delete_lines(a, asize);
752
 
    return NULL;
753
 
}
754
 
 
755
 
 
756
 
static PyObject *
757
 
PatienceSequenceMatcher_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
758
 
{
759
 
    PyObject *junk, *a, *b;
760
 
    PatienceSequenceMatcher *self;
761
 
 
762
 
    self = (PatienceSequenceMatcher *)type->tp_alloc(type, 0);
763
 
    if (self != NULL) {
764
 
 
765
 
        if (!PyArg_ParseTuple(args, "OOO", &junk, &a, &b)) {
766
 
            Py_DECREF(self);
767
 
            return NULL;
768
 
        }
769
 
 
770
 
        self->asize = load_lines(a, &(self->a));
771
 
        self->bsize = load_lines(b, &(self->b));
772
 
 
773
 
        if (self->asize == -1 || self->bsize == -1) {
774
 
            Py_DECREF(self);
775
 
            return NULL;
776
 
        }
777
 
 
778
 
        if (!equate_lines(&self->hashtable, self->a, self->b, self->asize, self->bsize)) {
779
 
            Py_DECREF(self);
780
 
            return NULL;
781
 
        }
782
 
 
783
 
        if (self->bsize > 0) {
784
 
            self->backpointers = (Py_ssize_t *)guarded_malloc(sizeof(Py_ssize_t) * self->bsize * 4);
785
 
            if (self->backpointers == NULL) {
786
 
                Py_DECREF(self);
787
 
                PyErr_NoMemory();
788
 
                return NULL;
789
 
            }
790
 
        } else {
791
 
            self->backpointers = NULL;
792
 
        }
793
 
 
794
 
    }
795
 
 
796
 
    return (PyObject *)self;
797
 
}
798
 
 
799
 
 
800
 
static void
801
 
PatienceSequenceMatcher_dealloc(PatienceSequenceMatcher* self)
802
 
{
803
 
    free(self->backpointers);
804
 
    free(self->hashtable.table);
805
 
    delete_lines(self->b, self->bsize);
806
 
    delete_lines(self->a, self->asize);
807
 
    self->ob_type->tp_free((PyObject *)self);
808
 
}
809
 
 
810
 
 
811
 
static char PatienceSequenceMatcher_get_matching_blocks_doc[] =
812
 
    "Return list of triples describing matching subsequences.\n"
813
 
    "\n"
814
 
    "Each triple is of the form (i, j, n), and means that\n"
815
 
    "a[i:i+n] == b[j:j+n].  The triples are monotonically increasing in\n"
816
 
    "i and in j.\n"
817
 
    "\n"
818
 
    "The last triple is a dummy, (len(a), len(b), 0), and is the only\n"
819
 
    "triple with n==0.\n"
820
 
    "\n"
821
 
    ">>> s = PatienceSequenceMatcher(None, \"abxcd\", \"abcd\")\n"
822
 
    ">>> s.get_matching_blocks()\n"
823
 
    "[(0, 0, 2), (3, 2, 2), (5, 4, 0)]\n";
824
 
 
825
 
static PyObject *
826
 
PatienceSequenceMatcher_get_matching_blocks(PatienceSequenceMatcher* self)
827
 
{
828
 
    PyObject *answer, *item;
829
 
    int res;
830
 
    Py_ssize_t i;
831
 
    struct matching_blocks matches;
832
 
 
833
 
    matches.count = 0;
834
 
    if (self->bsize > 0) {
835
 
        matches.matches = (struct matching_block *)
836
 
            guarded_malloc(sizeof(struct matching_block) * self->bsize);
837
 
        if (matches.matches == NULL)
838
 
            return PyErr_NoMemory();
839
 
    } else
840
 
        matches.matches = NULL;
841
 
 
842
 
    res = recurse_matches(&matches, &self->hashtable, self->backpointers,
843
 
                          self->a, self->b, 0, 0,
844
 
                          self->asize, self->bsize, 10);
845
 
    if (!res) {
846
 
        free(matches.matches);
847
 
        return PyErr_NoMemory();
848
 
    }
849
 
 
850
 
    answer = PyList_New(matches.count + 1);
851
 
    if (answer == NULL) {
852
 
        free(matches.matches);
853
 
        return NULL;
854
 
    }
855
 
 
856
 
    for (i = 0; i < matches.count; i++) {
857
 
#if PY_VERSION_HEX < 0x02050000
858
 
        item = Py_BuildValue("iii", matches.matches[i].a,
859
 
                             matches.matches[i].b, matches.matches[i].len);
860
 
#else
861
 
        item = Py_BuildValue("nnn", matches.matches[i].a,
862
 
                             matches.matches[i].b, matches.matches[i].len);
863
 
#endif
864
 
        if (item == NULL)
865
 
            goto error;
866
 
        if (PyList_SetItem(answer, i, item) != 0)
867
 
            goto error;
868
 
    }
869
 
#if PY_VERSION_HEX < 0x02050000
870
 
    item = Py_BuildValue("iii", self->asize, self->bsize, 0);
871
 
#else
872
 
    item = Py_BuildValue("nnn", self->asize, self->bsize, 0);
873
 
#endif
874
 
    if (item == NULL)
875
 
        goto error;
876
 
    if (PyList_SetItem(answer, i, item) != 0)
877
 
        goto error;
878
 
 
879
 
    free(matches.matches);
880
 
    return answer;
881
 
 
882
 
error:
883
 
    free(matches.matches);
884
 
    Py_DECREF(answer);
885
 
    return NULL;
886
 
}
887
 
 
888
 
 
889
 
static char PatienceSequenceMatcher_get_opcodes_doc[] =
890
 
    "Return list of 5-tuples describing how to turn a into b.\n"
891
 
    "\n"
892
 
    "Each tuple is of the form (tag, i1, i2, j1, j2).  The first tuple\n"
893
 
    "has i1 == j1 == 0, and remaining tuples have i1 == the i2 from the\n"
894
 
    "tuple preceding it, and likewise for j1 == the previous j2.\n"
895
 
    "\n"
896
 
    "The tags are strings, with these meanings:\n"
897
 
    "\n"
898
 
    "'replace':  a[i1:i2] should be replaced by b[j1:j2]\n"
899
 
    "'delete':   a[i1:i2] should be deleted.\n"
900
 
    "               Note that j1==j2 in this case.\n"
901
 
    "'insert':   b[j1:j2] should be inserted at a[i1:i1].\n"
902
 
    "               Note that i1==i2 in this case.\n"
903
 
    "'equal':    a[i1:i2] == b[j1:j2]\n"
904
 
    "\n"
905
 
    ">>> a = \"qabxcd\"\n"
906
 
    ">>> b = \"abycdf\"\n"
907
 
    ">>> s = PatienceSequenceMatcher(None, a, b)\n"
908
 
    ">>> for tag, i1, i2, j1, j2 in s.get_opcodes():\n"
909
 
    "...    print (\"%7s a[%d:%d] (%s) b[%d:%d] (%s)\" %\n"
910
 
    "...           (tag, i1, i2, a[i1:i2], j1, j2, b[j1:j2]))\n"
911
 
    " delete a[0:1] (q) b[0:0] ()\n"
912
 
    "  equal a[1:3] (ab) b[0:2] (ab)\n"
913
 
    "replace a[3:4] (x) b[2:3] (y)\n"
914
 
    "  equal a[4:6] (cd) b[3:5] (cd)\n"
915
 
    " insert a[6:6] () b[5:6] (f)\n";
916
 
 
917
 
static PyObject *
918
 
PatienceSequenceMatcher_get_opcodes(PatienceSequenceMatcher* self)
919
 
{
920
 
    PyObject *answer, *item;
921
 
    Py_ssize_t i, j, k, ai, bj;
922
 
    int tag, res;
923
 
    struct matching_blocks matches;
924
 
 
925
 
    matches.count = 0;
926
 
    matches.matches = (struct matching_block *)guarded_malloc(sizeof(struct matching_block) * (self->bsize + 1));
927
 
    if (matches.matches == NULL)
928
 
        return PyErr_NoMemory();
929
 
 
930
 
    res = recurse_matches(&matches, &self->hashtable, self->backpointers,
931
 
                          self->a, self->b, 0, 0,
932
 
                          self->asize, self->bsize, 10);
933
 
    if (!res) {
934
 
        free(matches.matches);
935
 
        return PyErr_NoMemory();
936
 
    }
937
 
 
938
 
    matches.matches[matches.count].a = self->asize;
939
 
    matches.matches[matches.count].b = self->bsize;
940
 
    matches.matches[matches.count].len = 0;
941
 
    matches.count++;
942
 
 
943
 
    answer = PyList_New(0);
944
 
    if (answer == NULL) {
945
 
        free(matches.matches);
946
 
        return NULL;
947
 
    }
948
 
 
949
 
    i = j = 0;
950
 
    for (k = 0; k < matches.count; k++) {
951
 
        ai = matches.matches[k].a;
952
 
        bj = matches.matches[k].b;
953
 
 
954
 
        tag = -1;
955
 
        if (i < ai && j < bj)
956
 
            tag = OP_REPLACE;
957
 
        else if (i < ai)
958
 
            tag = OP_DELETE;
959
 
        else if (j < bj)
960
 
            tag = OP_INSERT;
961
 
 
962
 
        if (tag != -1) {
963
 
#if PY_VERSION_HEX < 0x02050000
964
 
            item = Py_BuildValue("siiii", opcode_names[tag], i, ai, j, bj);
965
 
#else
966
 
            item = Py_BuildValue("snnnn", opcode_names[tag], i, ai, j, bj);
967
 
#endif
968
 
            if (item == NULL)
969
 
                goto error;
970
 
            if (PyList_Append(answer, item) != 0)
971
 
                goto error;
972
 
        }
973
 
 
974
 
        i = ai + matches.matches[k].len;
975
 
        j = bj + matches.matches[k].len;
976
 
 
977
 
        if (matches.matches[k].len > 0) {
978
 
#if PY_VERSION_HEX < 0x02050000
979
 
            item = Py_BuildValue("siiii", opcode_names[OP_EQUAL], ai, i, bj, j);
980
 
#else
981
 
            item = Py_BuildValue("snnnn", opcode_names[OP_EQUAL], ai, i, bj, j);
982
 
#endif
983
 
            if (item == NULL)
984
 
                goto error;
985
 
            if (PyList_Append(answer, item) != 0)
986
 
                goto error;
987
 
        }
988
 
    }
989
 
 
990
 
    free(matches.matches);
991
 
    return answer;
992
 
 
993
 
error:
994
 
    free(matches.matches);
995
 
    Py_DECREF(answer);
996
 
    return NULL;
997
 
}
998
 
 
999
 
 
1000
 
static char PatienceSequenceMatcher_get_grouped_opcodes_doc[] =
1001
 
    "Isolate change clusters by eliminating ranges with no changes.\n"
1002
 
    "\n"
1003
 
    "Return a list of groups with upto n lines of context.\n"
1004
 
    "Each group is in the same format as returned by get_opcodes().\n"
1005
 
    "\n"
1006
 
    ">>> from pprint import pprint\n"
1007
 
    ">>> a = map(str, range(1,40))\n"
1008
 
    ">>> b = a[:]\n"
1009
 
    ">>> b[8:8] = ['i']     # Make an insertion\n"
1010
 
    ">>> b[20] += 'x'       # Make a replacement\n"
1011
 
    ">>> b[23:28] = []      # Make a deletion\n"
1012
 
    ">>> b[30] += 'y'       # Make another replacement\n"
1013
 
    ">>> pprint(PatienceSequenceMatcher(None,a,b).get_grouped_opcodes())\n"
1014
 
    "[[('equal', 5, 8, 5, 8), ('insert', 8, 8, 8, 9), ('equal', 8, 11, 9, 12)],\n"
1015
 
    " [('equal', 16, 19, 17, 20),\n"
1016
 
    "  ('replace', 19, 20, 20, 21),\n"
1017
 
    "  ('equal', 20, 22, 21, 23),\n"
1018
 
    "  ('delete', 22, 27, 23, 23),\n"
1019
 
    "  ('equal', 27, 30, 23, 26)],\n"
1020
 
    " [('equal', 31, 34, 27, 30),\n"
1021
 
    "  ('replace', 34, 35, 30, 31),\n"
1022
 
    "  ('equal', 35, 38, 31, 34)]]\n";
1023
 
 
1024
 
static PyObject *
1025
 
PatienceSequenceMatcher_get_grouped_opcodes(PatienceSequenceMatcher* self,
1026
 
                                            PyObject *args)
1027
 
{
1028
 
    PyObject *answer, *group, *item;
1029
 
    Py_ssize_t i, j, k, ai, bj, size, ncodes, tag;
1030
 
    Py_ssize_t i1, i2, j1, j2;
1031
 
    int n = 3, nn, res;
1032
 
    struct matching_blocks matches;
1033
 
    struct opcode *codes;
1034
 
 
1035
 
    if (!PyArg_ParseTuple(args, "|i", &n))
1036
 
        return NULL;
1037
 
 
1038
 
    matches.count = 0;
1039
 
    matches.matches = (struct matching_block *)guarded_malloc(sizeof(struct matching_block) * (self->bsize + 1));
1040
 
    if (matches.matches == NULL)
1041
 
        return PyErr_NoMemory();
1042
 
 
1043
 
    res = recurse_matches(&matches, &self->hashtable, self->backpointers,
1044
 
                          self->a, self->b, 0, 0,
1045
 
                          self->asize, self->bsize, 10);
1046
 
    if (!res) {
1047
 
        free(matches.matches);
1048
 
        return PyErr_NoMemory();
1049
 
    }
1050
 
 
1051
 
    matches.matches[matches.count].a = self->asize;
1052
 
    matches.matches[matches.count].b = self->bsize;
1053
 
    matches.matches[matches.count].len = 0;
1054
 
    matches.count++;
1055
 
 
1056
 
    ncodes = 0;
1057
 
    codes = (struct opcode *)guarded_malloc(sizeof(struct opcode) * matches.count * 2);
1058
 
    if (codes == NULL) {
1059
 
        free(matches.matches);
1060
 
        return PyErr_NoMemory();
1061
 
    }
1062
 
 
1063
 
    i = j = 0;
1064
 
    for (k = 0; k < matches.count; k++) {
1065
 
        ai = matches.matches[k].a;
1066
 
        bj = matches.matches[k].b;
1067
 
 
1068
 
        tag = -1;
1069
 
        if (i < ai && j < bj)
1070
 
            tag = OP_REPLACE;
1071
 
        else if (i < ai)
1072
 
            tag = OP_DELETE;
1073
 
        else if (j < bj)
1074
 
            tag = OP_INSERT;
1075
 
 
1076
 
        if (tag != -1) {
1077
 
            codes[ncodes].tag = tag;
1078
 
            codes[ncodes].i1 = i;
1079
 
            codes[ncodes].i2 = ai;
1080
 
            codes[ncodes].j1 = j;
1081
 
            codes[ncodes].j2 = bj;
1082
 
            ncodes++;
1083
 
        }
1084
 
 
1085
 
        i = ai + matches.matches[k].len;
1086
 
        j = bj + matches.matches[k].len;
1087
 
 
1088
 
        if (matches.matches[k].len > 0) {
1089
 
            codes[ncodes].tag = OP_EQUAL;
1090
 
            codes[ncodes].i1 = ai;
1091
 
            codes[ncodes].i2 = i;
1092
 
            codes[ncodes].j1 = bj;
1093
 
            codes[ncodes].j2 = j;
1094
 
            ncodes++;
1095
 
        }
1096
 
    }
1097
 
 
1098
 
    if (ncodes == 0) {
1099
 
        codes[ncodes].tag = OP_EQUAL;
1100
 
        codes[ncodes].i1 = 0;
1101
 
        codes[ncodes].i2 = 1;
1102
 
        codes[ncodes].j1 = 0;
1103
 
        codes[ncodes].j2 = 1;
1104
 
        ncodes++;
1105
 
    }
1106
 
 
1107
 
    /* fixup leading and trailing groups if they show no changes. */
1108
 
    if (codes[0].tag == OP_EQUAL) {
1109
 
        codes[0].i1 = MAX(codes[0].i1, codes[0].i2 - n);
1110
 
        codes[0].j1 = MAX(codes[0].j1, codes[0].j2 - n);
1111
 
    }
1112
 
    if (codes[ncodes - 1].tag == OP_EQUAL) {
1113
 
        codes[ncodes - 1].i2 = MIN(codes[ncodes - 1].i2,
1114
 
                                   codes[ncodes - 1].i1 + n);
1115
 
        codes[ncodes - 1].j2 = MIN(codes[ncodes - 1].j2,
1116
 
                                   codes[ncodes - 1].j1 + n);
1117
 
    }
1118
 
 
1119
 
    group = NULL;
1120
 
 
1121
 
    answer = PyList_New(0);
1122
 
    if (answer == NULL)
1123
 
        goto error;
1124
 
 
1125
 
    group = PyList_New(0);
1126
 
    if (group == NULL)
1127
 
        goto error;
1128
 
 
1129
 
    nn = n + n;
1130
 
    tag = -1;
1131
 
    for (i = 0; i < ncodes; i++) {
1132
 
        tag = codes[i].tag;
1133
 
        i1 = codes[i].i1;
1134
 
        i2 = codes[i].i2;
1135
 
        j1 = codes[i].j1;
1136
 
        j2 = codes[i].j2;
1137
 
        /* end the current group and start a new one whenever
1138
 
           there is a large range with no changes. */
1139
 
        if (tag == OP_EQUAL && i2 - i1 > nn) {
1140
 
#if PY_VERSION_HEX < 0x02050000
1141
 
            item = Py_BuildValue("siiii", opcode_names[tag],
1142
 
                                  i1, MIN(i2, i1 + n), j1, MIN(j2, j1 + n));
1143
 
#else
1144
 
            item = Py_BuildValue("snnnn", opcode_names[tag],
1145
 
                                  i1, MIN(i2, i1 + n), j1, MIN(j2, j1 + n));
1146
 
#endif
1147
 
            if (item == NULL)
1148
 
                goto error;
1149
 
            if (PyList_Append(group, item) != 0)
1150
 
                goto error;
1151
 
            if (PyList_Append(answer, group) != 0)
1152
 
                goto error;
1153
 
            group = PyList_New(0);
1154
 
            if (group == NULL)
1155
 
                goto error;
1156
 
            i1 = MAX(i1, i2 - n);
1157
 
            j1 = MAX(j1, j2 - n);
1158
 
        }
1159
 
#if PY_VERSION_HEX < 0x02050000
1160
 
        item = Py_BuildValue("siiii", opcode_names[tag], i1, i2, j1 ,j2);
1161
 
#else
1162
 
        item = Py_BuildValue("snnnn", opcode_names[tag], i1, i2, j1 ,j2);
1163
 
#endif
1164
 
        if (item == NULL)
1165
 
            goto error;
1166
 
        if (PyList_Append(group, item) != 0)
1167
 
            goto error;
1168
 
    }
1169
 
    size = PyList_Size(group);
1170
 
    if (size > 0 && !(size == 1 && tag == OP_EQUAL)) {
1171
 
        if (PyList_Append(answer, group) != 0)
1172
 
            goto error;
1173
 
    }
1174
 
    else
1175
 
        Py_DECREF(group);
1176
 
 
1177
 
    free(codes);
1178
 
    free(matches.matches);
1179
 
    return answer;
1180
 
 
1181
 
error:
1182
 
    free(codes);
1183
 
    free(matches.matches);
1184
 
    Py_DECREF(group);
1185
 
    Py_DECREF(answer);
1186
 
    return NULL;
1187
 
}
1188
 
 
1189
 
 
1190
 
static PyMethodDef PatienceSequenceMatcher_methods[] = {
1191
 
    {"get_matching_blocks",
1192
 
     (PyCFunction)PatienceSequenceMatcher_get_matching_blocks,
1193
 
     METH_NOARGS,
1194
 
     PatienceSequenceMatcher_get_matching_blocks_doc},
1195
 
    {"get_opcodes",
1196
 
     (PyCFunction)PatienceSequenceMatcher_get_opcodes,
1197
 
     METH_NOARGS,
1198
 
     PatienceSequenceMatcher_get_opcodes_doc},
1199
 
    {"get_grouped_opcodes",
1200
 
     (PyCFunction)PatienceSequenceMatcher_get_grouped_opcodes,
1201
 
     METH_VARARGS,
1202
 
     PatienceSequenceMatcher_get_grouped_opcodes_doc},
1203
 
    {NULL}
1204
 
};
1205
 
 
1206
 
 
1207
 
static char PatienceSequenceMatcher_doc[] =
1208
 
    "C implementation of PatienceSequenceMatcher";
1209
 
 
1210
 
 
1211
 
static PyTypeObject PatienceSequenceMatcherType = {
1212
 
    PyObject_HEAD_INIT(NULL)
1213
 
    0,                                           /* ob_size */
1214
 
    "PatienceSequenceMatcher",                   /* tp_name */
1215
 
    sizeof(PatienceSequenceMatcher),             /* tp_basicsize */
1216
 
    0,                                           /* tp_itemsize */
1217
 
    (destructor)PatienceSequenceMatcher_dealloc, /* tp_dealloc */
1218
 
    0,                                           /* tp_print */
1219
 
    0,                                           /* tp_getattr */
1220
 
    0,                                           /* tp_setattr */
1221
 
    0,                                           /* tp_compare */
1222
 
    0,                                           /* tp_repr */
1223
 
    0,                                           /* tp_as_number */
1224
 
    0,                                           /* tp_as_sequence */
1225
 
    0,                                           /* tp_as_mapping */
1226
 
    0,                                           /* tp_hash */
1227
 
    0,                                           /* tp_call */
1228
 
    0,                                           /* tp_str */
1229
 
    0,                                           /* tp_getattro */
1230
 
    0,                                           /* tp_setattro */
1231
 
    0,                                           /* tp_as_buffer */
1232
 
    Py_TPFLAGS_DEFAULT,                          /* tp_flags*/
1233
 
    PatienceSequenceMatcher_doc,                 /* tp_doc */
1234
 
    0,                                           /* tp_traverse */
1235
 
    0,                                           /* tp_clear */
1236
 
    0,                                           /* tp_richcompare */
1237
 
    0,                                           /* tp_weaklistoffset */
1238
 
    0,                                           /* tp_iter */
1239
 
    0,                                           /* tp_iternext */
1240
 
    PatienceSequenceMatcher_methods,             /* tp_methods */
1241
 
    0,                                           /* tp_members */
1242
 
    0,                                           /* tp_getset */
1243
 
    0,                                           /* tp_base */
1244
 
    0,                                           /* tp_dict */
1245
 
    0,                                           /* tp_descr_get */
1246
 
    0,                                           /* tp_descr_set */
1247
 
    0,                                           /* tp_dictoffset */
1248
 
    0,                                           /* tp_init */
1249
 
    0,                                           /* tp_alloc */
1250
 
    PatienceSequenceMatcher_new,                 /* tp_new */
1251
 
};
1252
 
 
1253
 
 
1254
 
static PyMethodDef cpatiencediff_methods[] = {
1255
 
    {"unique_lcs_c", py_unique_lcs, METH_VARARGS},
1256
 
    {"recurse_matches_c", py_recurse_matches, METH_VARARGS},
1257
 
    {NULL, NULL}
1258
 
};
1259
 
 
1260
 
 
1261
 
PyMODINIT_FUNC
1262
 
init_patiencediff_c(void)
1263
 
{
1264
 
    PyObject* m;
1265
 
 
1266
 
    if (PyType_Ready(&PatienceSequenceMatcherType) < 0)
1267
 
        return;
1268
 
 
1269
 
    m = Py_InitModule3("_patiencediff_c", cpatiencediff_methods,
1270
 
                       "C implementation of PatienceSequenceMatcher");
1271
 
    if (m == NULL)
1272
 
      return;
1273
 
 
1274
 
    Py_INCREF(&PatienceSequenceMatcherType);
1275
 
    PyModule_AddObject(m, "PatienceSequenceMatcher_c",
1276
 
                       (PyObject *)&PatienceSequenceMatcherType);
1277
 
}
1278
 
 
1279
 
 
1280
 
/* vim: sw=4 et 
1281
 
 */