« back to all changes in this revision
Viewing changes to bzrlib/knit.py
- browse files at revision 1616
- compare with another revision
- compare with revision 2485.8.58
- download diff
- download tarball
- view history from revision 1616
- Committer: Canonical.com Patch Queue Manager
- Date: 2006-03-20 10:33:11 UTC
- mfrom: (1615.1.2 bzr.mbp.integration)
- Revision ID: pqm@pqm.ubuntu.com-20060320103311-a87ccd7ffe9ce14f
(mbp) pycurl bugfixes, robert's knit performance stuff
- files modified:
- README
added
removed
bzrlib/knit.py
66
66
from copy import copy
67
67
from cStringIO import StringIO
68
68
import difflib
69
from difflib import SequenceMatcher
70
from gzip import GzipFile
71
from itertools import izip
69
import gzip
70
from itertools import izip, chain
72
71
import os
73
72
74
73
116
115
"""Return a list of (origin, text) tuples."""
117
116
return list(self.annotate_iter())
118
117
119
def apply_delta(self, delta):
120
"""Apply delta to this content."""
121
offset = 0
122
for start, end, count, lines in delta:
123
self._lines[offset+start:offset+end] = lines
124
offset = offset + (start - end) + count
125
126
118
def line_delta_iter(self, new_lines):
127
"""Generate line-based delta from new_lines to this content."""
119
"""Generate line-based delta from this content to new_lines."""
128
120
new_texts = [text for origin, text in new_lines._lines]
129
121
old_texts = [text for origin, text in self._lines]
130
s = difflib.SequenceMatcher(None, old_texts, new_texts)
122
s = SequenceMatcher(None, old_texts, new_texts)
131
123
for op in s.get_opcodes():
132
124
if op[0] == 'equal':
133
125
continue
126
# ofrom oto length data
134
127
yield (op[1], op[2], op[4]-op[3], new_lines._lines[op[3]:op[4]])
135
128
136
129
def line_delta(self, new_lines):
289
282
self._data = _KnitData(transport, relpath + DATA_SUFFIX,
290
283
access_mode, create=not len(self.versions()))
291
284
285
def _add_delta(self, version_id, parents, delta_parent, sha1, noeol, delta):
286
"""See VersionedFile._add_delta()."""
287
self._check_add(version_id, []) # should we check the lines ?
288
self._check_versions_present(parents)
289
present_parents = []
290
ghosts = []
291
parent_texts = {}
292
for parent in parents:
293
if not self.has_version(parent):
294
ghosts.append(parent)
295
else:
296
present_parents.append(parent)
297
298
if delta_parent is None:
299
# reconstitute as full text.
300
assert len(delta) == 1 or len(delta) == 0
301
if len(delta):
302
assert delta[0][0] == 0
303
assert delta[0][1] == 0, delta[0][1]
304
return super(KnitVersionedFile, self)._add_delta(version_id,
305
parents,
306
delta_parent,
307
sha1,
308
noeol,
309
delta)
310
311
digest = sha1
312
313
options = []
314
if noeol:
315
options.append('no-eol')
316
317
if delta_parent is not None:
318
# determine the current delta chain length.
319
# To speed the extract of texts the delta chain is limited
320
# to a fixed number of deltas. This should minimize both
321
# I/O and the time spend applying deltas.
322
count = 0
323
delta_parents = [delta_parent]
324
while count < 25:
325
parent = delta_parents[0]
326
method = self._index.get_method(parent)
327
if method == 'fulltext':
328
break
329
delta_parents = self._index.get_parents(parent)
330
count = count + 1
331
if method == 'line-delta':
332
# did not find a fulltext in the delta limit.
333
# just do a normal insertion.
334
return super(KnitVersionedFile, self)._add_delta(version_id,
335
parents,
336
delta_parent,
337
sha1,
338
noeol,
339
delta)
340
341
options.append('line-delta')
342
store_lines = self.factory.lower_line_delta(delta)
343
344
where, size = self._data.add_record(version_id, digest, store_lines)
345
self._index.add_version(version_id, options, where, size, parents)
346
292
347
def clear_cache(self):
293
348
"""Clear the data cache only."""
294
349
self._data.clear_cache()
322
377
current_values[3],
323
378
new_parents)
324
379
380
def get_delta(self, version_id):
381
"""Get a delta for constructing version from some other version."""
382
if not self.has_version(version_id):
383
raise RevisionNotPresent(version_id, self.filename)
384
385
parents = self.get_parents(version_id)
386
if len(parents):
387
parent = parents[0]
388
else:
389
parent = None
390
data_pos, data_size = self._index.get_position(version_id)
391
data, sha1 = self._data.read_records(((version_id, data_pos, data_size),))[version_id]
392
version_idx = self._index.lookup(version_id)
393
noeol = 'no-eol' in self._index.get_options(version_id)
394
if 'fulltext' == self._index.get_method(version_id):
395
new_content = self.factory.parse_fulltext(data, version_idx)
396
if parent is not None:
397
reference_content = self._get_content(parent)
398
old_texts = reference_content.text()
399
else:
400
old_texts = []
401
new_texts = new_content.text()
402
delta_seq = SequenceMatcher(None, old_texts, new_texts)
403
return parent, sha1, noeol, self._make_line_delta(delta_seq, new_content)
404
else:
405
delta = self.factory.parse_line_delta(data, version_idx)
406
return parent, sha1, noeol, delta
407
325
408
def get_graph_with_ghosts(self):
326
409
"""See VersionedFile.get_graph_with_ghosts()."""
327
410
graph_items = self._index.get_graph()
356
439
357
440
__contains__ = has_version
358
441
359
def _merge_annotations(self, content, parents):
442
def _merge_annotations(self, content, parents, parent_texts={},
443
delta=None, annotated=None):
360
444
"""Merge annotations for content. This is done by comparing
361
the annotations based on changed to the text."""
362
for parent_id in parents:
363
merge_content = self._get_content(parent_id)
364
seq = SequenceMatcher(None, merge_content.text(), content.text())
365
for i, j, n in seq.get_matching_blocks():
366
if n == 0:
367
continue
368
content._lines[j:j+n] = merge_content._lines[i:i+n]
445
the annotations based on changed to the text.
446
"""
447
if annotated:
448
delta_seq = None
449
for parent_id in parents:
450
merge_content = self._get_content(parent_id, parent_texts)
451
seq = SequenceMatcher(None, merge_content.text(), content.text())
452
if delta_seq is None:
453
# setup a delta seq to reuse.
454
delta_seq = seq
455
for i, j, n in seq.get_matching_blocks():
456
if n == 0:
457
continue
458
# this appears to copy (origin, text) pairs across to the new
459
# content for any line that matches the last-checked parent.
460
# FIXME: save the sequence control data for delta compression
461
# against the most relevant parent rather than rediffing.
462
content._lines[j:j+n] = merge_content._lines[i:i+n]
463
if delta:
464
if not annotated:
465
reference_content = self._get_content(parents[0], parent_texts)
466
new_texts = content.text()
467
old_texts = reference_content.text()
468
delta_seq = SequenceMatcher(None, old_texts, new_texts)
469
return self._make_line_delta(delta_seq, content)
470
471
def _make_line_delta(self, delta_seq, new_content):
472
"""Generate a line delta from delta_seq and new_content."""
473
diff_hunks = []
474
for op in delta_seq.get_opcodes():
475
if op[0] == 'equal':
476
continue
477
diff_hunks.append((op[1], op[2], op[4]-op[3], new_content._lines[op[3]:op[4]]))
478
return diff_hunks
369
479
370
480
def _get_components(self, version_id):
371
481
"""Return a list of (version_id, method, data) tuples that
424
534
425
535
return out
426
536
427
def _get_content(self, version_id):
537
def _get_content(self, version_id, parent_texts={}):
428
538
"""Returns a content object that makes up the specified
429
539
version."""
430
540
if not self.has_version(version_id):
431
541
raise RevisionNotPresent(version_id, self.filename)
432
542
543
cached_version = parent_texts.get(version_id, None)
544
if cached_version is not None:
545
return cached_version
546
433
547
if self.basis_knit and version_id in self.basis_knit:
434
548
return self.basis_knit._get_content(version_id)
435
549
442
556
content = self.factory.parse_fulltext(data, version_idx)
443
557
elif method == 'line-delta':
444
558
delta = self.factory.parse_line_delta(data, version_idx)
445
content.apply_delta(delta)
559
content._lines = self._apply_delta(content._lines, delta)
446
560
447
561
if 'no-eol' in self._index.get_options(version_id):
448
562
line = content._lines[-1][1].rstrip('\n')
449
563
content._lines[-1] = (content._lines[-1][0], line)
450
564
451
565
if sha_strings(content.text()) != digest:
452
raise KnitCorrupt(self.filename, 'sha-1 does not match')
566
import pdb;pdb.set_trace()
567
raise KnitCorrupt(self.filename, 'sha-1 does not match %s' % version_id)
453
568
454
569
return content
455
570
462
577
if version_ids:
463
578
raise RevisionNotPresent(list(version_ids)[0], self.filename)
464
579
465
def _add_lines_with_ghosts(self, version_id, parents, lines):
580
def _add_lines_with_ghosts(self, version_id, parents, lines, parent_texts):
466
581
"""See VersionedFile.add_lines_with_ghosts()."""
467
582
self._check_add(version_id, lines)
468
return self._add(version_id, lines[:], parents, self.delta)
583
return self._add(version_id, lines[:], parents, self.delta, parent_texts)
469
584
470
def _add_lines(self, version_id, parents, lines):
585
def _add_lines(self, version_id, parents, lines, parent_texts):
471
586
"""See VersionedFile.add_lines."""
472
587
self._check_add(version_id, lines)
473
588
self._check_versions_present(parents)
474
return self._add(version_id, lines[:], parents, self.delta)
589
return self._add(version_id, lines[:], parents, self.delta, parent_texts)
475
590
476
591
def _check_add(self, version_id, lines):
477
592
"""check that version_id and lines are safe to add."""
486
601
for l in lines:
487
602
assert '\n' not in l[:-1]
488
603
489
def _add(self, version_id, lines, parents, delta):
604
def _add(self, version_id, lines, parents, delta, parent_texts):
490
605
"""Add a set of lines on top of version specified by parents.
491
606
492
607
If delta is true, compress the text as a line-delta against
494
609
495
610
Any versions not present will be converted into ghosts.
496
611
"""
612
# 461 0 6546.0390 43.9100 bzrlib.knit:489(_add)
613
# +400 0 889.4890 418.9790 +bzrlib.knit:192(lower_fulltext)
614
# +461 0 1364.8070 108.8030 +bzrlib.knit:996(add_record)
615
# +461 0 193.3940 41.5720 +bzrlib.knit:898(add_version)
616
# +461 0 134.0590 18.3810 +bzrlib.osutils:361(sha_strings)
617
# +461 0 36.3420 15.4540 +bzrlib.knit:146(make)
618
# +1383 0 8.0370 8.0370 +<len>
619
# +61 0 13.5770 7.9190 +bzrlib.knit:199(lower_line_delta)
620
# +61 0 963.3470 7.8740 +bzrlib.knit:427(_get_content)
621
# +61 0 973.9950 5.2950 +bzrlib.knit:136(line_delta)
622
# +61 0 1918.1800 5.2640 +bzrlib.knit:359(_merge_annotations)
623
497
624
present_parents = []
498
625
ghosts = []
626
if parent_texts is None:
627
parent_texts = {}
499
628
for parent in parents:
500
629
if not self.has_version(parent):
501
630
ghosts.append(parent)
512
641
options.append('no-eol')
513
642
lines[-1] = lines[-1] + '\n'
514
643
515
lines = self.factory.make(lines, version_id)
516
if self.factory.annotated and len(present_parents) > 0:
517
# Merge annotations from parent texts if so is needed.
518
self._merge_annotations(lines, present_parents)
519
520
644
if len(present_parents) and delta:
521
645
# To speed the extract of texts the delta chain is limited
522
646
# to a fixed number of deltas. This should minimize both
533
657
if method == 'line-delta':
534
658
delta = False
535
659
660
lines = self.factory.make(lines, version_id)
661
if delta or (self.factory.annotated and len(present_parents) > 0):
662
# Merge annotations from parent texts if so is needed.
663
delta_hunks = self._merge_annotations(lines, present_parents, parent_texts,
664
delta, self.factory.annotated)
665
536
666
if delta:
537
667
options.append('line-delta')
538
content = self._get_content(present_parents[0])
539
delta_hunks = content.line_delta(lines)
540
668
store_lines = self.factory.lower_line_delta(delta_hunks)
541
669
else:
542
670
options.append('fulltext')
544
672
545
673
where, size = self._data.add_record(version_id, digest, store_lines)
546
674
self._index.add_version(version_id, options, where, size, parents)
675
return lines
547
676
548
677
def check(self, progress_bar=None):
549
678
"""See VersionedFile.check()."""
677
806
self._mode = mode
678
807
679
808
def write_header(self):
680
old_len = self._transport.append(self._filename, StringIO(self.HEADER))
681
if old_len != 0:
809
if self._transport.append(self._filename, StringIO(self.HEADER)):
682
810
raise KnitCorrupt(self._filename, 'misaligned after writing header')
683
811
684
812
def check_header(self, fp):
719
847
720
848
HEADER = "# bzr knit index 7\n"
721
849
850
# speed of knit parsing went from 280 ms to 280 ms with slots addition.
851
# __slots__ = ['_cache', '_history', '_transport', '_filename']
852
722
853
def _cache_version(self, version_id, options, pos, size, parents):
723
val = (version_id, options, pos, size, parents)
724
self._cache[version_id] = val
725
if not version_id in self._history:
854
"""Cache a version record in the history array and index cache.
855
856
This is inlined into __init__ for performance. KEEP IN SYNC.
857
(It saves 60ms, 25% of the __init__ overhead on local 4000 record
858
indexes).
859
"""
860
# only want the _history index to reference the 1st index entry
861
# for version_id
862
if version_id not in self._cache:
726
863
self._history.append(version_id)
727
728
def _iter_index(self, fp):
729
l = fp.readline()
730
while l != '':
731
yield l.split()
732
l = fp.readline()
733
#lines = fp.read()
734
#for l in lines.splitlines(False):
735
# yield l.split()
864
self._cache[version_id] = (version_id, options, pos, size, parents)
736
865
737
866
def __init__(self, transport, filename, mode, create=False):
738
867
_KnitComponentFile.__init__(self, transport, filename, mode)
750
879
pb.update('read knit index', count, total)
751
880
fp = self._transport.get(self._filename)
752
881
self.check_header(fp)
753
for rec in self._iter_index(fp):
882
# readlines reads the whole file at once:
883
# bad for transports like http, good for local disk
884
# we save 60 ms doing this one change (
885
# from calling readline each time to calling
886
# readlines once.
887
# probably what we want for nice behaviour on
888
# http is a incremental readlines that yields, or
889
# a check for local vs non local indexes,
890
for l in fp.readlines():
891
rec = l.split()
754
892
count += 1
755
893
total += 1
756
pb.update('read knit index', count, total)
757
parents = self._parse_parents(rec[4:])
758
self._cache_version(rec[0], rec[1].split(','), int(rec[2]), int(rec[3]),
759
parents)
894
#pb.update('read knit index', count, total)
895
# See self._parse_parents
896
parents = []
897
for value in rec[4:]:
898
if '.' == value[0]:
899
# uncompressed reference
900
parents.append(value[1:])
901
else:
902
# this is 15/4000ms faster than isinstance,
903
# (in lsprof)
904
# this function is called thousands of times a
905
# second so small variations add up.
906
assert value.__class__ is str
907
parents.append(self._history[int(value)])
908
# end self._parse_parents
909
# self._cache_version(rec[0],
910
# rec[1].split(','),
911
# int(rec[2]),
912
# int(rec[3]),
913
# parents)
914
# --- self._cache_version
915
# only want the _history index to reference the 1st
916
# index entry for version_id
917
version_id = rec[0]
918
if version_id not in self._cache:
919
self._history.append(version_id)
920
self._cache[version_id] = (version_id,
921
rec[1].split(','),
922
int(rec[2]),
923
int(rec[3]),
924
parents)
925
# --- self._cache_version
760
926
except NoSuchFile, e:
761
927
if mode != 'w' or not create:
762
928
raise
770
936
771
937
ints are looked up in the index.
772
938
.FOO values are ghosts and converted in to FOO.
939
940
NOTE: the function is retained here for clarity, and for possible
941
use in partial index reads. However bulk processing now has
942
it inlined in __init__ for inner-loop optimisation.
773
943
"""
774
944
result = []
775
945
for value in compressed_parents:
776
if value.startswith('.'):
946
if value[-1] == '.':
947
# uncompressed reference
777
948
result.append(value[1:])
778
949
else:
779
assert isinstance(value, str)
950
# this is 15/4000ms faster than isinstance,
951
# this function is called thousands of times a
952
# second so small variations add up.
953
assert value.__class__ is str
780
954
result.append(self._history[int(value)])
781
955
return result
782
956
933
1107
"""
934
1108
sio = StringIO()
935
1109
data_file = GzipFile(None, mode='wb', fileobj=sio)
936
print >>data_file, "version %s %d %s" % (version_id.encode('utf-8'), len(lines), digest)
937
data_file.writelines(lines)
938
print >>data_file, "end %s\n" % version_id.encode('utf-8')
1110
data_file.writelines(chain(
1111
["version %s %d %s\n" % (version_id.encode('utf-8'),
1112
len(lines),
1113
digest)],
1114
lines,
1115
["end %s\n\n" % version_id.encode('utf-8')]))
939
1116
data_file.close()
940
1117
length= sio.tell()
1118
941
1119
sio.seek(0)
942
1120
return length, sio
943
1121
1179
1357
self.target.fix_parents(version, new_parents)
1180
1358
return count
1181
1359
finally:
1182
pb.clear()
1183
1360
pb.finished()
1184
1361
1185
1362
1186
1363
InterVersionedFile.register_optimiser(InterKnit)
1364
1365
1366
# make GzipFile faster:
1367
import zlib
1368
class GzipFile(gzip.GzipFile):
1369
"""Knit tuned version of GzipFile.
1370
1371
This is based on the following lsprof stats:
1372
python 2.4 stock GzipFile write:
1373
58971 0 5644.3090 2721.4730 gzip:193(write)
1374
+58971 0 1159.5530 1159.5530 +<built-in method compress>
1375
+176913 0 987.0320 987.0320 +<len>
1376
+58971 0 423.1450 423.1450 +<zlib.crc32>
1377
+58971 0 353.1060 353.1060 +<method 'write' of 'cStringIO.
1378
StringO' objects>
1379
tuned GzipFile write:
1380
58971 0 4477.2590 2103.1120 bzrlib.knit:1250(write)
1381
+58971 0 1297.7620 1297.7620 +<built-in method compress>
1382
+58971 0 406.2160 406.2160 +<zlib.crc32>
1383
+58971 0 341.9020 341.9020 +<method 'write' of 'cStringIO.
1384
StringO' objects>
1385
+58971 0 328.2670 328.2670 +<len>
1386
1387
1388
Yes, its only 1.6 seconds, but they add up.
1389
"""
1390
1391
def write(self, data):
1392
if self.mode != gzip.WRITE:
1393
import errno
1394
raise IOError(errno.EBADF, "write() on read-only GzipFile object")
1395
1396
if self.fileobj is None:
1397
raise ValueError, "write() on closed GzipFile object"
1398
data_len = len(data)
1399
if data_len > 0:
1400
self.size = self.size + data_len
1401
self.crc = zlib.crc32(data, self.crc)
1402
self.fileobj.write( self.compress.compress(data) )
1403
self.offset += data_len
1404
1405
def writelines(self, lines):
1406
# profiling indicated a significant overhead
1407
# calling write for each line.
1408
# this batch call is a lot faster :).
1409
# (4 seconds to 1 seconds for the sample upgrades I was testing).
1410
self.write(''.join(lines))
1411
1412
1413
class SequenceMatcher(difflib.SequenceMatcher):
1414
"""Knit tuned sequence matcher.
1415
1416
This is based on profiling of difflib which indicated some improvements
1417
for our usage pattern.
1418
"""
1419
1420
def find_longest_match(self, alo, ahi, blo, bhi):
1421
"""Find longest matching block in a[alo:ahi] and b[blo:bhi].
1422
1423
If isjunk is not defined:
1424
1425
Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
1426
alo <= i <= i+k <= ahi
1427
blo <= j <= j+k <= bhi
1428
and for all (i',j',k') meeting those conditions,
1429
k >= k'
1430
i <= i'
1431
and if i == i', j <= j'
1432
1433
In other words, of all maximal matching blocks, return one that
1434
starts earliest in a, and of all those maximal matching blocks that
1435
start earliest in a, return the one that starts earliest in b.
1436
1437
>>> s = SequenceMatcher(None, " abcd", "abcd abcd")
1438
>>> s.find_longest_match(0, 5, 0, 9)
1439
(0, 4, 5)
1440
1441
If isjunk is defined, first the longest matching block is
1442
determined as above, but with the additional restriction that no
1443
junk element appears in the block. Then that block is extended as
1444
far as possible by matching (only) junk elements on both sides. So
1445
the resulting block never matches on junk except as identical junk
1446
happens to be adjacent to an "interesting" match.
1447
1448
Here's the same example as before, but considering blanks to be
1449
junk. That prevents " abcd" from matching the " abcd" at the tail
1450
end of the second sequence directly. Instead only the "abcd" can
1451
match, and matches the leftmost "abcd" in the second sequence:
1452
1453
>>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
1454
>>> s.find_longest_match(0, 5, 0, 9)
1455
(1, 0, 4)
1456
1457
If no blocks match, return (alo, blo, 0).
1458
1459
>>> s = SequenceMatcher(None, "ab", "c")
1460
>>> s.find_longest_match(0, 2, 0, 1)
1461
(0, 0, 0)
1462
"""
1463
1464
# CAUTION: stripping common prefix or suffix would be incorrect.
1465
# E.g.,
1466
# ab
1467
# acab
1468
# Longest matching block is "ab", but if common prefix is
1469
# stripped, it's "a" (tied with "b"). UNIX(tm) diff does so
1470
# strip, so ends up claiming that ab is changed to acab by
1471
# inserting "ca" in the middle. That's minimal but unintuitive:
1472
# "it's obvious" that someone inserted "ac" at the front.
1473
# Windiff ends up at the same place as diff, but by pairing up
1474
# the unique 'b's and then matching the first two 'a's.
1475
1476
a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.isbjunk
1477
besti, bestj, bestsize = alo, blo, 0
1478
# find longest junk-free match
1479
# during an iteration of the loop, j2len[j] = length of longest
1480
# junk-free match ending with a[i-1] and b[j]
1481
j2len = {}
1482
# nothing = []
1483
b2jget = b2j.get
1484
for i in xrange(alo, ahi):
1485
# look at all instances of a[i] in b; note that because
1486
# b2j has no junk keys, the loop is skipped if a[i] is junk
1487
j2lenget = j2len.get
1488
newj2len = {}
1489
1490
# changing b2j.get(a[i], nothing) to a try:Keyerror pair produced the
1491
# following improvement
1492
# 704 0 4650.5320 2620.7410 bzrlib.knit:1336(find_longest_match)
1493
# +326674 0 1655.1210 1655.1210 +<method 'get' of 'dict' objects>
1494
# +76519 0 374.6700 374.6700 +<method 'has_key' of 'dict' objects>
1495
# to
1496
# 704 0 3733.2820 2209.6520 bzrlib.knit:1336(find_longest_match)
1497
# +211400 0 1147.3520 1147.3520 +<method 'get' of 'dict' objects>
1498
# +76519 0 376.2780 376.2780 +<method 'has_key' of 'dict' objects>
1499
1500
try:
1501
js = b2j[a[i]]
1502
except KeyError:
1503
pass
1504
else:
1505
for j in js:
1506
# a[i] matches b[j]
1507
if j >= blo:
1508
if j >= bhi:
1509
break
1510
k = newj2len[j] = 1 + j2lenget(-1 + j, 0)
1511
if k > bestsize:
1512
besti, bestj, bestsize = 1 + i-k, 1 + j-k, k
1513
j2len = newj2len
1514
1515
# Extend the best by non-junk elements on each end. In particular,
1516
# "popular" non-junk elements aren't in b2j, which greatly speeds
1517
# the inner loop above, but also means "the best" match so far
1518
# doesn't contain any junk *or* popular non-junk elements.
1519
while besti > alo and bestj > blo and \
1520
not isbjunk(b[bestj-1]) and \
1521
a[besti-1] == b[bestj-1]:
1522
besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
1523
while besti+bestsize < ahi and bestj+bestsize < bhi and \
1524
not isbjunk(b[bestj+bestsize]) and \
1525
a[besti+bestsize] == b[bestj+bestsize]:
1526
bestsize += 1
1527
1528
# Now that we have a wholly interesting match (albeit possibly
1529
# empty!), we may as well suck up the matching junk on each
1530
# side of it too. Can't think of a good reason not to, and it
1531
# saves post-processing the (possibly considerable) expense of
1532
# figuring out what to do with it. In the case of an empty
1533
# interesting match, this is clearly the right thing to do,
1534
# because no other kind of match is possible in the regions.
1535
while besti > alo and bestj > blo and \
1536
isbjunk(b[bestj-1]) and \
1537
a[besti-1] == b[bestj-1]:
1538
besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
1539
while besti+bestsize < ahi and bestj+bestsize < bhi and \
1540
isbjunk(b[bestj+bestsize]) and \
1541
a[besti+bestsize] == b[bestj+bestsize]:
1542
bestsize = bestsize + 1
1543
1544
return besti, bestj, bestsize
1545
Loggerhead is a web-based interface for Breezy
Version: 2.0.1