/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to breezy/_patiencediff_py.py

  • Committer: Jelmer Vernooij
  • Date: 2018-11-16 23:19:12 UTC
  • mfrom: (7180 work)
  • mto: This revision was merged to the branch mainline in revision 7294.
  • Revision ID: jelmer@jelmer.uk-20181116231912-e043vpq22bdkxa6q
Merge trunk.

Show diffs side-by-side

added added

removed removed

Lines of Context:
breezy/_patiencediff_py.py
15
15
# along with this program; if not, write to the Free Software
16
16
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
17
 
 
18
from __future__ import absolute_import
18
19
 
19
20
from bisect import bisect
20
21
import difflib
21
22
 
22
 
from bzrlib.trace import mutter
23
 
 
24
 
 
25
 
__all__ = ['PatienceSequenceMatcher', 'unified_diff', 'unified_diff_files']
 
23
from .trace import mutter
26
24
 
27
25
 
28
26
def unique_lcs_py(a, b):
42
40
    # set index[line in a] = position of line in a unless
43
41
    # a is a duplicate, in which case it's set to None
44
42
    index = {}
45
 
    for i in xrange(len(a)):
46
 
        line = a[i]
 
43
    for i, line in enumerate(a):
47
44
        if line in index:
48
45
            index[line] = None
49
46
        else:
50
 
            index[line]= i
 
47
            index[line] = i
51
48
    # make btoa[i] = position of line i in a, unless
52
49
    # that line doesn't occur exactly once in both,
53
50
    # in which case it's set to None
80
77
        # as an optimization, check if the next line comes right after
81
78
        # the previous line, because usually it does
82
79
        elif stacks and stacks[k] < apos and (k == len(stacks) - 1 or
83
 
                                              stacks[k+1] > apos):
 
80
                                              stacks[k + 1] > apos):
84
81
            k += 1
85
82
        else:
86
83
            k = bisect(stacks, apos)
87
84
        if k > 0:
88
 
            backpointers[bpos] = lasts[k-1]
 
85
            backpointers[bpos] = lasts[k - 1]
89
86
        if k < len(stacks):
90
87
            stacks[k] = apos
91
88
            lasts[k] = bpos
127
124
    oldlength = len(answer)
128
125
    if alo == ahi or blo == bhi:
129
126
        return
130
 
    last_a_pos = alo-1
131
 
    last_b_pos = blo-1
 
127
    last_a_pos = alo - 1
 
128
    last_b_pos = blo - 1
132
129
    for apos, bpos in unique_lcs_py(a[alo:ahi], b[blo:bhi]):
133
130
        # recurse between lines which are unique in each file and match
134
131
        apos += alo
135
132
        bpos += blo
136
133
        # Most of the time, you will have a sequence of similar entries
137
 
        if last_a_pos+1 != apos or last_b_pos+1 != bpos:
138
 
            recurse_matches_py(a, b, last_a_pos+1, last_b_pos+1,
139
 
                apos, bpos, answer, maxrecursion - 1)
 
134
        if last_a_pos + 1 != apos or last_b_pos + 1 != bpos:
 
135
            recurse_matches_py(
 
136
                a, b, last_a_pos + 1, last_b_pos + 1, apos, bpos, answer,
 
137
                maxrecursion - 1)
140
138
        last_a_pos = apos
141
139
        last_b_pos = bpos
142
140
        answer.append((apos, bpos))
143
141
    if len(answer) > oldlength:
144
142
        # find matches between the last match and the end
145
 
        recurse_matches_py(a, b, last_a_pos+1, last_b_pos+1,
 
143
        recurse_matches_py(a, b, last_a_pos + 1, last_b_pos + 1,
146
144
                           ahi, bhi, answer, maxrecursion - 1)
147
145
    elif a[alo] == b[blo]:
148
146
        # find matching lines at the very beginning
159
157
        while nahi > alo and nbhi > blo and a[nahi - 1] == b[nbhi - 1]:
160
158
            nahi -= 1
161
159
            nbhi -= 1
162
 
        recurse_matches_py(a, b, last_a_pos+1, last_b_pos+1,
 
160
        recurse_matches_py(a, b, last_a_pos + 1, last_b_pos + 1,
163
161
                           nahi, nbhi, answer, maxrecursion - 1)
164
 
        for i in xrange(ahi - nahi):
 
162
        for i in range(ahi - nahi):
165
163
            answer.append((nahi + i, nbhi + i))
166
164
 
167
165
 
176
174
    length = 0
177
175
    for i_a, i_b in matches:
178
176
        if (start_a is not None
179
 
            and (i_a == start_a + length)
180
 
            and (i_b == start_b + length)):
 
177
                and (i_a == start_a + length)
 
178
                and (i_b == start_b + length)):
181
179
            length += 1
182
180
        else:
183
181
            if start_a is not None:
244
242
        # Matches now has individual line pairs of
245
243
        # line A matches line B, at the given offsets
246
244
        self.matching_blocks = _collapse_sequences(matches)
247
 
        self.matching_blocks.append( (len(self.a), len(self.b), 0) )
 
245
        self.matching_blocks.append((len(self.a), len(self.b), 0))
248
246
        if PatienceSequenceMatcher_py._do_check_consistency:
249
247
            if __debug__:
250
248
                _check_consistency(self.matching_blocks)