~bzr-pqm/bzr/bzr.dev

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
# Copyright (C) 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

from bzrlib.lazy_import import lazy_import

lazy_import(globals(), """
import errno
import itertools
import os
from StringIO import StringIO

from bzrlib import (
    patiencediff,
    trace,
    ui,
    )
from bzrlib.util import bencode
""")
from bzrlib.tuned_gzip import GzipFile


def topo_iter(vf, versions=None):
    seen = set()
    descendants = {}
    if versions is None:
        versions = vf.versions()
    def pending_parents(version):
        return [v for v in vf.get_parents(version) if v in versions and
                v not in seen]
    for version_id in versions:
        for parent_id in vf.get_parents(version_id):
            descendants.setdefault(parent_id, []).append(version_id)
    cur = [v for v in versions if len(pending_parents(v)) == 0]
    while len(cur) > 0:
        next = []
        for version_id in cur:
            if version_id in seen:
                continue
            if len(pending_parents(version_id)) != 0:
                continue
            next.extend(descendants.get(version_id, []))
            yield version_id
            seen.add(version_id)
        cur = next
    assert len(seen) == len(versions)


class MultiParent(object):
    """A multi-parent diff"""

    def __init__(self, hunks=None):
        if hunks is not None:
            self.hunks = hunks
        else:
            self.hunks = []

    def __repr__(self):
        return "MultiParent(%r)" % self.hunks

    def __eq__(self, other):
        if self.__class__ is not other.__class__:
            return False
        return (self.hunks == other.hunks)

    @staticmethod
    def from_lines(text, parents=(), left_blocks=None):
        """Produce a MultiParent from a list of lines and parents"""
        def compare(parent):
            matcher = patiencediff.PatienceSequenceMatcher(None, parent,
                                                           text)
            return matcher.get_matching_blocks()
        if len(parents) > 0:
            if left_blocks is None:
                left_blocks = compare(parents[0])
            parent_comparisons = [left_blocks] + [compare(p) for p in
                                                  parents[1:]]
        else:
            parent_comparisons = []
        cur_line = 0
        new_text = NewText([])
        parent_text = []
        block_iter = [iter(i) for i in parent_comparisons]
        diff = MultiParent([])
        def next_block(p):
            try:
                return block_iter[p].next()
            except StopIteration:
                return None
        cur_block = [next_block(p) for p, i in enumerate(block_iter)]
        while cur_line < len(text):
            best_match = None
            for p, block in enumerate(cur_block):
                if block is None:
                    continue
                i, j, n = block
                while j + n <= cur_line:
                    block = cur_block[p] = next_block(p)
                    if block is None:
                        break
                    i, j, n = block
                if block is None:
                    continue
                if j > cur_line:
                    continue
                offset = cur_line - j
                i += offset
                j = cur_line
                n -= offset
                if n == 0:
                    continue
                if best_match is None or n > best_match.num_lines:
                    best_match = ParentText(p, i, j, n)
            if best_match is None:
                new_text.lines.append(text[cur_line])
                cur_line += 1
            else:
                if len(new_text.lines) > 0:
                    diff.hunks.append(new_text)
                    new_text = NewText([])
                diff.hunks.append(best_match)
                cur_line += best_match.num_lines
        if len(new_text.lines) > 0:
            diff.hunks.append(new_text)
        return diff

    def get_matching_blocks(self, parent, parent_len):
        for hunk in self.hunks:
            if not isinstance(hunk, ParentText) or hunk.parent != parent:
                continue
            yield (hunk.parent_pos, hunk.child_pos, hunk.num_lines)
        yield parent_len, self.num_lines(), 0

    def to_lines(self, parents=()):
        """Contruct a fulltext from this diff and its parents"""
        mpvf = MultiMemoryVersionedFile()
        for num, parent in enumerate(parents):
            mpvf.add_version(StringIO(parent).readlines(), num, [])
        mpvf.add_diff(self, 'a', range(len(parents)))
        return mpvf.get_line_list(['a'])[0]

    @classmethod
    def from_texts(cls, text, parents=()):
        """Produce a MultiParent from a text and list of parent text"""
        return cls.from_lines(StringIO(text).readlines(),
                              [StringIO(p).readlines() for p in parents])

    def to_patch(self):
        """Yield text lines for a patch"""
        for hunk in self.hunks:
            for line in hunk.to_patch():
                yield line

    def patch_len(self):
        return len(''.join(self.to_patch()))

    def zipped_patch_len(self):
        return len(gzip_string(self.to_patch()))

    @classmethod
    def from_patch(cls, text):
        """Create a MultiParent from its string form"""
        return cls._from_patch(StringIO(text))

    @staticmethod
    def _from_patch(lines):
        """This is private because it is essential to split lines on \n only"""
        line_iter = iter(lines)
        hunks = []
        cur_line = None
        while(True):
            try:
                cur_line = line_iter.next()
            except StopIteration:
                break
            if cur_line[0] == 'i':
                num_lines = int(cur_line.split(' ')[1])
                hunk_lines = [line_iter.next() for x in xrange(num_lines)]
                hunk_lines[-1] = hunk_lines[-1][:-1]
                hunks.append(NewText(hunk_lines))
            elif cur_line[0] == '\n':
                hunks[-1].lines[-1] += '\n'
            else:
                assert cur_line[0] == 'c', cur_line[0]
                parent, parent_pos, child_pos, num_lines =\
                    [int(v) for v in cur_line.split(' ')[1:]]
                hunks.append(ParentText(parent, parent_pos, child_pos,
                                        num_lines))
        return MultiParent(hunks)

    def range_iterator(self):
        """Iterate through the hunks, with range indicated

        kind is "new" or "parent".
        for "new", data is a list of lines.
        for "parent", data is (parent, parent_start, parent_end)
        :return: a generator of (start, end, kind, data)
        """
        start = 0
        for hunk in self.hunks:
            if isinstance(hunk, NewText):
                kind = 'new'
                end = start + len(hunk.lines)
                data = hunk.lines
            else:
                kind = 'parent'
                start = hunk.child_pos
                end = start + hunk.num_lines
                data = (hunk.parent, hunk.parent_pos, hunk.parent_pos +
                        hunk.num_lines)
            yield start, end, kind, data
            start = end

    def num_lines(self):
        """The number of lines in the output text"""
        extra_n = 0
        for hunk in reversed(self.hunks):
            if isinstance(hunk, ParentText):
               return hunk.child_pos + hunk.num_lines + extra_n
            extra_n += len(hunk.lines)
        return extra_n

    def is_snapshot(self):
        """Return true of this hunk is effectively a fulltext"""
        if len(self.hunks) != 1:
            return False
        return (isinstance(self.hunks[0], NewText))


class NewText(object):
    """The contents of text that is introduced by this text"""

    def __init__(self, lines):
        self.lines = lines

    def __eq__(self, other):
        if self.__class__ is not other.__class__:
            return False
        return (other.lines == self.lines)

    def __repr__(self):
        return 'NewText(%r)' % self.lines

    def to_patch(self):
        yield 'i %d\n' % len(self.lines)
        for line in self.lines:
            yield line
        yield '\n'


class ParentText(object):
    """A reference to text present in a parent text"""

    def __init__(self, parent, parent_pos, child_pos, num_lines):
        self.parent = parent
        self.parent_pos = parent_pos
        self.child_pos = child_pos
        self.num_lines = num_lines

    def __repr__(self):
        return 'ParentText(%(parent)r, %(parent_pos)r, %(child_pos)r,'\
            ' %(num_lines)r)' % self.__dict__

    def __eq__(self, other):
        if self.__class__ != other.__class__:
            return False
        return (self.__dict__ == other.__dict__)

    def to_patch(self):
        yield 'c %(parent)d %(parent_pos)d %(child_pos)d %(num_lines)d\n'\
            % self.__dict__


class BaseVersionedFile(object):
    """Pseudo-VersionedFile skeleton for MultiParent"""

    def __init__(self, snapshot_interval=25, max_snapshots=None):
        self._lines = {}
        self._parents = {}
        self._snapshots = set()
        self.snapshot_interval = snapshot_interval
        self.max_snapshots = max_snapshots

    def versions(self):
        return iter(self._parents)

    def has_version(self, version):
        return version in self._parents

    def do_snapshot(self, version_id, parent_ids):
        """Determine whether to perform a a snapshot for this version"""
        if self.snapshot_interval is None:
            return False
        if self.max_snapshots is not None and\
            len(self._snapshots) == self.max_snapshots:
            return False
        if len(parent_ids) == 0:
            return True
        for ignored in xrange(self.snapshot_interval):
            if len(parent_ids) == 0:
                return False
            version_ids = parent_ids
            parent_ids = []
            for version_id in version_ids:
                if version_id not in self._snapshots:
                    parent_ids.extend(self._parents[version_id])
        else:
            return True

    def add_version(self, lines, version_id, parent_ids,
                    force_snapshot=None, single_parent=False):
        """Add a version to the versionedfile

        :param lines: The list of lines to add.  Must be split on '\n'.
        :param version_id: The version_id of the version to add
        :param force_snapshot: If true, force this version to be added as a
            snapshot version.  If false, force this version to be added as a
            diff.  If none, determine this automatically.
        :param single_parent: If true, use a single parent, rather than
            multiple parents.
        """
        if force_snapshot is None:
            do_snapshot = self.do_snapshot(version_id, parent_ids)
        else:
            do_snapshot = force_snapshot
        if do_snapshot:
            self._snapshots.add(version_id)
            diff = MultiParent([NewText(lines)])
        else:
            if single_parent:
                parent_lines = self.get_line_list(parent_ids[:1])
            else:
                parent_lines = self.get_line_list(parent_ids)
            diff = MultiParent.from_lines(lines, parent_lines)
            if diff.is_snapshot():
                self._snapshots.add(version_id)
        self.add_diff(diff, version_id, parent_ids)
        self._lines[version_id] = lines

    def get_parents(self, version_id):
        return self._parents[version_id]

    def make_snapshot(self, version_id):
        snapdiff = MultiParent([NewText(self.cache_version(version_id))])
        self.add_diff(snapdiff, version_id, self._parents[version_id])
        self._snapshots.add(version_id)

    def import_versionedfile(self, vf, snapshots, no_cache=True,
                             single_parent=False, verify=False):
        """Import all revisions of a versionedfile

        :param vf: The versionedfile to import
        :param snapshots: If provided, the revisions to make snapshots of.
            Otherwise, this will be auto-determined
        :param no_cache: If true, clear the cache after every add.
        :param single_parent: If true, omit all but one parent text, (but
            retain parent metadata).
        """
        assert no_cache or not verify
        revisions = set(vf.versions())
        total = len(revisions)
        pb = ui.ui_factory.nested_progress_bar()
        try:
            while len(revisions) > 0:
                added = set()
                for revision in revisions:
                    parents = vf.get_parents(revision)
                    if [p for p in parents if p not in self._parents] != []:
                        continue
                    lines = [a + ' ' + l for a, l in
                             vf.annotate_iter(revision)]
                    if snapshots is None:
                        force_snapshot = None
                    else:
                        force_snapshot = (revision in snapshots)
                    self.add_version(lines, revision, parents, force_snapshot,
                                     single_parent)
                    added.add(revision)
                    if no_cache:
                        self.clear_cache()
                        vf.clear_cache()
                        if verify:
                            assert lines == self.get_line_list([revision])[0]
                            self.clear_cache()
                    pb.update('Importing revisions',
                              (total - len(revisions)) + len(added), total)
                revisions = [r for r in revisions if r not in added]
        finally:
            pb.finished()

    def select_snapshots(self, vf):
        """Determine which versions to add as snapshots"""
        build_ancestors = {}
        descendants = {}
        snapshots = set()
        for version_id in topo_iter(vf):
            potential_build_ancestors = set(vf.get_parents(version_id))
            parents = vf.get_parents(version_id)
            if len(parents) == 0:
                snapshots.add(version_id)
                build_ancestors[version_id] = set()
            else:
                for parent in vf.get_parents(version_id):
                    potential_build_ancestors.update(build_ancestors[parent])
                if len(potential_build_ancestors) > self.snapshot_interval:
                    snapshots.add(version_id)
                    build_ancestors[version_id] = set()
                else:
                    build_ancestors[version_id] = potential_build_ancestors
        return snapshots

    def select_by_size(self, num):
        """Select snapshots for minimum output size"""
        num -= len(self._snapshots)
        new_snapshots = self.get_size_ranking()[-num:]
        return [v for n, v in new_snapshots]

    def get_size_ranking(self):
        """Get versions ranked by size"""
        versions = []
        new_snapshots = set()
        for version_id in self.versions():
            if version_id in self._snapshots:
                continue
            diff_len = self.get_diff(version_id).patch_len()
            snapshot_len = MultiParent([NewText(
                self.cache_version(version_id))]).patch_len()
            versions.append((snapshot_len - diff_len, version_id))
        versions.sort()
        return versions

    def import_diffs(self, vf):
        """Import the diffs from another pseudo-versionedfile"""
        for version_id in vf.versions():
            self.add_diff(vf.get_diff(version_id), version_id,
                          vf._parents[version_id])

    def get_build_ranking(self):
        """Return revisions sorted by how much they reduce build complexity"""
        could_avoid = {}
        referenced_by = {}
        for version_id in topo_iter(self):
            could_avoid[version_id] = set()
            if version_id not in self._snapshots:
                for parent_id in self._parents[version_id]:
                    could_avoid[version_id].update(could_avoid[parent_id])
                could_avoid[version_id].update(self._parents)
                could_avoid[version_id].discard(version_id)
            for avoid_id in could_avoid[version_id]:
                referenced_by.setdefault(avoid_id, set()).add(version_id)
        available_versions = list(self.versions())
        ranking = []
        while len(available_versions) > 0:
            available_versions.sort(key=lambda x:
                len(could_avoid[x]) *
                len(referenced_by.get(x, [])))
            selected = available_versions.pop()
            ranking.append(selected)
            for version_id in referenced_by[selected]:
                could_avoid[version_id].difference_update(
                    could_avoid[selected])
            for version_id in could_avoid[selected]:
                referenced_by[version_id].difference_update(
                    referenced_by[selected]
                )
        return ranking

    def clear_cache(self):
        self._lines.clear()

    def get_line_list(self, version_ids):
        return [self.cache_version(v) for v in version_ids]

    def cache_version(self, version_id):
        try:
            return self._lines[version_id]
        except KeyError:
            pass
        diff = self.get_diff(version_id)
        lines = []
        reconstructor = _Reconstructor(self, self._lines, self._parents)
        reconstructor.reconstruct_version(lines, version_id)
        self._lines[version_id] = lines
        return lines


class MultiMemoryVersionedFile(BaseVersionedFile):
    """Memory-backed pseudo-versionedfile"""

    def __init__(self, snapshot_interval=25, max_snapshots=None):
        BaseVersionedFile.__init__(self, snapshot_interval, max_snapshots)
        self._diffs = {}

    def add_diff(self, diff, version_id, parent_ids):
        self._diffs[version_id] = diff
        self._parents[version_id] = parent_ids

    def get_diff(self, version_id):
        return self._diffs[version_id]

    def destroy(self):
        self._diffs = {}


class MultiVersionedFile(BaseVersionedFile):
    """Disk-backed pseudo-versionedfile"""

    def __init__(self, filename, snapshot_interval=25, max_snapshots=None):
        BaseVersionedFile.__init__(self, snapshot_interval, max_snapshots)
        self._filename = filename
        self._diff_offset = {}

    def get_diff(self, version_id):
        start, count = self._diff_offset[version_id]
        infile = open(self._filename + '.mpknit', 'rb')
        try:
            infile.seek(start)
            sio = StringIO(infile.read(count))
        finally:
            infile.close()
        zip_file = GzipFile(None, mode='rb', fileobj=sio)
        try:
            file_version_id = zip_file.readline()
            return MultiParent.from_patch(zip_file.read())
        finally:
            zip_file.close()

    def add_diff(self, diff, version_id, parent_ids):
        outfile = open(self._filename + '.mpknit', 'ab')
        try:
            start = outfile.tell()
            try:
                zipfile = GzipFile(None, mode='ab', fileobj=outfile)
                zipfile.writelines(itertools.chain(
                    ['version %s\n' % version_id], diff.to_patch()))
            finally:
                zipfile.close()
            end = outfile.tell()
        finally:
            outfile.close()
        self._diff_offset[version_id] = (start, end-start)
        self._parents[version_id] = parent_ids

    def destroy(self):
        try:
            os.unlink(self._filename + '.mpknit')
        except OSError, e:
            if e.errno != errno.ENOENT:
                raise
        try:
            os.unlink(self._filename + '.mpidx')
        except OSError, e:
            if e.errno != errno.ENOENT:
                raise

    def save(self):
        open(self._filename + '.mpidx', 'wb').write(bencode.bencode(
            (self._parents, list(self._snapshots), self._diff_offset)))

    def load(self):
        self._parents, snapshots, self._diff_offset = bencode.bdecode(
            open(self._filename + '.mpidx', 'rb').read())
        self._snapshots = set(snapshots)


class _Reconstructor(object):
    """Build a text from the diffs, ancestry graph and cached lines"""

    def __init__(self, diffs, lines, parents):
        self.diffs = diffs
        self.lines = lines
        self.parents = parents
        self.cursor = {}

    def reconstruct(self, lines, parent_text, version_id):
        """Append the lines referred to by a ParentText to lines"""
        parent_id = self.parents[version_id][parent_text.parent]
        end = parent_text.parent_pos + parent_text.num_lines
        return self._reconstruct(lines, parent_id, parent_text.parent_pos,
                                 end)

    def _reconstruct(self, lines, req_version_id, req_start, req_end):
        """Append lines for the requested version_id range"""
        # stack of pending range requests
        if req_start == req_end:
            return
        pending_reqs = [(req_version_id, req_start, req_end)]
        while len(pending_reqs) > 0:
            req_version_id, req_start, req_end = pending_reqs.pop()
            # lazily allocate cursors for versions
            if req_version_id in self.lines:
                lines.extend(self.lines[req_version_id][req_start:req_end])
                continue
            try:
                start, end, kind, data, iterator = self.cursor[req_version_id]
            except KeyError:
                iterator = self.diffs.get_diff(req_version_id).range_iterator()
                start, end, kind, data = iterator.next()
            if start > req_start:
                iterator = self.diffs.get_diff(req_version_id).range_iterator()
                start, end, kind, data = iterator.next()

            # find the first hunk relevant to the request
            while end <= req_start:
                start, end, kind, data = iterator.next()
            self.cursor[req_version_id] = start, end, kind, data, iterator
            # if the hunk can't satisfy the whole request, split it in two,
            # and leave the second half for later.
            if req_end > end:
                pending_reqs.append((req_version_id, end, req_end))
                req_end = end
            if kind == 'new':
                lines.extend(data[req_start - start: (req_end - start)])
            else:
                # If the hunk is a ParentText, rewrite it as a range request
                # for the parent, and make it the next pending request.
                parent, parent_start, parent_end = data
                new_version_id = self.parents[req_version_id][parent]
                new_start = parent_start + req_start - start
                new_end = parent_end + req_end - end
                pending_reqs.append((new_version_id, new_start, new_end))

    def reconstruct_version(self, lines, version_id):
        length = self.diffs.get_diff(version_id).num_lines()
        return self._reconstruct(lines, version_id, 0, length)


def gzip_string(lines):
    sio = StringIO()
    data_file = GzipFile(None, mode='wb', fileobj=sio)
    data_file.writelines(lines)
    data_file.close()
    return sio.getvalue()