← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/multiparent.py

  • Committer: Aaron Bentley
  • Date: 2007-06-11 14:59:52 UTC
  • mto: (2520.5.2 bzr.mpbundle)
  • mto: This revision was merged to the branch mainline in revision 2631.
  • Revision ID: abentley@panoramicfeedback.com-20070611145952-cwt4480gphdhen6l
Get installation started

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/multiparent.py
1
 
# Copyright (C) 2007-2011 Canonical Ltd
2
 
#
3
 
# This program is free software; you can redistribute it and/or modify
4
 
# it under the terms of the GNU General Public License as published by
5
 
# the Free Software Foundation; either version 2 of the License, or
6
 
# (at your option) any later version.
7
 
#
8
 
# This program is distributed in the hope that it will be useful,
9
 
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
 
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
 
# GNU General Public License for more details.
12
 
#
13
 
# You should have received a copy of the GNU General Public License
14
 
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
 
 
17
 
from __future__ import absolute_import
18
 
 
19
1
from bzrlib.lazy_import import lazy_import
20
2
 
21
3
lazy_import(globals(), """
22
4
import errno
23
 
import gzip
24
5
import itertools
25
6
import os
26
7
from StringIO import StringIO
27
8
 
28
9
from bzrlib import (
29
 
    bencode,
30
 
    errors,
31
10
    patiencediff,
 
11
    trace,
32
12
    ui,
33
13
    )
 
14
from bzrlib.util import bencode
34
15
""")
35
 
 
36
 
 
37
 
def topo_iter_keys(vf, keys=None):
38
 
    if keys is None:
39
 
        keys = vf.keys()
40
 
    parents = vf.get_parent_map(keys)
41
 
    return _topo_iter(parents, keys)
42
 
 
43
 
def topo_iter(vf, versions=None):
44
 
    if versions is None:
45
 
        versions = vf.versions()
46
 
    parents = vf.get_parent_map(versions)
47
 
    return _topo_iter(parents, versions)
48
 
 
49
 
def _topo_iter(parents, versions):
 
16
from bzrlib.tuned_gzip import GzipFile
 
17
 
 
18
 
 
19
def topo_iter(vf):
50
20
    seen = set()
51
21
    descendants = {}
52
 
    def pending_parents(version):
53
 
        if parents[version] is None:
54
 
            return []
55
 
        return [v for v in parents[version] if v in versions and
56
 
                v not in seen]
57
 
    for version_id in versions:
58
 
        if parents[version_id] is None:
59
 
            # parentless
60
 
            continue
61
 
        for parent_id in parents[version_id]:
 
22
    for version_id in vf.versions():
 
23
        for parent_id in vf.get_parents(version_id):
62
24
            descendants.setdefault(parent_id, []).append(version_id)
63
 
    cur = [v for v in versions if len(pending_parents(v)) == 0]
 
25
    cur = [v for v in vf.versions() if len(vf.get_parents(v)) == 0]
64
26
    while len(cur) > 0:
65
27
        next = []
66
28
        for version_id in cur:
67
29
            if version_id in seen:
68
30
                continue
69
 
            if len(pending_parents(version_id)) != 0:
 
31
            parents = vf.get_parents(version_id)
 
32
            if not seen.issuperset(parents):
70
33
                continue
71
34
            next.extend(descendants.get(version_id, []))
72
35
            yield version_id
75
38
 
76
39
 
77
40
class MultiParent(object):
78
 
    """A multi-parent diff"""
79
 
 
80
 
    __slots__ = ['hunks']
81
41
 
82
42
    def __init__(self, hunks=None):
83
43
        if hunks is not None:
94
54
        return (self.hunks == other.hunks)
95
55
 
96
56
    @staticmethod
97
 
    def from_lines(text, parents=(), left_blocks=None):
 
57
    def from_lines(text, parents=()):
98
58
        """Produce a MultiParent from a list of lines and parents"""
99
59
        def compare(parent):
100
60
            matcher = patiencediff.PatienceSequenceMatcher(None, parent,
101
61
                                                           text)
102
62
            return matcher.get_matching_blocks()
103
 
        if len(parents) > 0:
104
 
            if left_blocks is None:
105
 
                left_blocks = compare(parents[0])
106
 
            parent_comparisons = [left_blocks] + [compare(p) for p in
107
 
                                                  parents[1:]]
108
 
        else:
109
 
            parent_comparisons = []
 
63
        parent_comparisons = [compare(p) for p in parents]
110
64
        cur_line = 0
111
65
        new_text = NewText([])
112
66
        parent_text = []
124
78
                if block is None:
125
79
                    continue
126
80
                i, j, n = block
127
 
                while j + n <= cur_line:
 
81
                while j + n < cur_line:
128
82
                    block = cur_block[p] = next_block(p)
129
83
                    if block is None:
130
84
                        break
154
108
            diff.hunks.append(new_text)
155
109
        return diff
156
110
 
157
 
    def get_matching_blocks(self, parent, parent_len):
158
 
        for hunk in self.hunks:
159
 
            if not isinstance(hunk, ParentText) or hunk.parent != parent:
160
 
                continue
161
 
            yield (hunk.parent_pos, hunk.child_pos, hunk.num_lines)
162
 
        yield parent_len, self.num_lines(), 0
163
 
 
164
 
    def to_lines(self, parents=()):
165
 
        """Contruct a fulltext from this diff and its parents"""
166
 
        mpvf = MultiMemoryVersionedFile()
167
 
        for num, parent in enumerate(parents):
168
 
            mpvf.add_version(StringIO(parent).readlines(), num, [])
169
 
        mpvf.add_diff(self, 'a', range(len(parents)))
170
 
        return mpvf.get_line_list(['a'])[0]
171
 
 
172
111
    @classmethod
173
112
    def from_texts(cls, text, parents=()):
174
113
        """Produce a MultiParent from a text and list of parent text"""
175
 
        return cls.from_lines(StringIO(text).readlines(),
176
 
                              [StringIO(p).readlines() for p in parents])
 
114
        return cls.from_lines(text.splitlines(True),
 
115
                              [p.splitlines(True) for p in parents])
177
116
 
178
117
    def to_patch(self):
179
118
        """Yield text lines for a patch"""
187
126
    def zipped_patch_len(self):
188
127
        return len(gzip_string(self.to_patch()))
189
128
 
190
 
    @classmethod
191
 
    def from_patch(cls, text):
192
 
        """Create a MultiParent from its string form"""
193
 
        return cls._from_patch(StringIO(text))
194
 
 
195
129
    @staticmethod
196
 
    def _from_patch(lines):
197
 
        """This is private because it is essential to split lines on \n only"""
 
130
    def from_patch(lines):
 
131
        """Produce a MultiParent from a sequence of lines"""
198
132
        line_iter = iter(lines)
199
133
        hunks = []
200
134
        cur_line = None
211
145
            elif cur_line[0] == '\n':
212
146
                hunks[-1].lines[-1] += '\n'
213
147
            else:
214
 
                if not (cur_line[0] == 'c'):
215
 
                    raise AssertionError(cur_line[0])
 
148
                assert cur_line[0] == 'c', cur_line[0]
216
149
                parent, parent_pos, child_pos, num_lines =\
217
150
                    [int(v) for v in cur_line.split(' ')[1:]]
218
151
                hunks.append(ParentText(parent, parent_pos, child_pos,
243
176
            start = end
244
177
 
245
178
    def num_lines(self):
246
 
        """The number of lines in the output text"""
247
179
        extra_n = 0
248
180
        for hunk in reversed(self.hunks):
249
181
            if isinstance(hunk, ParentText):
252
184
        return extra_n
253
185
 
254
186
    def is_snapshot(self):
255
 
        """Return true of this hunk is effectively a fulltext"""
256
187
        if len(self.hunks) != 1:
257
188
            return False
258
189
        return (isinstance(self.hunks[0], NewText))
261
192
class NewText(object):
262
193
    """The contents of text that is introduced by this text"""
263
194
 
264
 
    __slots__ = ['lines']
265
 
 
266
195
    def __init__(self, lines):
267
196
        self.lines = lines
268
197
 
284
213
class ParentText(object):
285
214
    """A reference to text present in a parent text"""
286
215
 
287
 
    __slots__ = ['parent', 'parent_pos', 'child_pos', 'num_lines']
288
 
 
289
216
    def __init__(self, parent, parent_pos, child_pos, num_lines):
290
217
        self.parent = parent
291
218
        self.parent_pos = parent_pos
292
219
        self.child_pos = child_pos
293
220
        self.num_lines = num_lines
294
221
 
295
 
    def _as_dict(self):
296
 
        return dict(parent=self.parent, parent_pos=self.parent_pos,
297
 
                    child_pos=self.child_pos, num_lines=self.num_lines)
298
 
 
299
222
    def __repr__(self):
300
 
        return ('ParentText(%(parent)r, %(parent_pos)r, %(child_pos)r,'
301
 
                ' %(num_lines)r)' % self._as_dict())
 
223
        return 'ParentText(%(parent)r, %(parent_pos)r, %(child_pos)r,'\
 
224
            ' %(num_lines)r)' % self.__dict__
302
225
 
303
226
    def __eq__(self, other):
304
 
        if self.__class__ is not other.__class__:
 
227
        if self.__class__ != other.__class__:
305
228
            return False
306
 
        return self._as_dict() == other._as_dict()
 
229
        return (self.__dict__ == other.__dict__)
307
230
 
308
231
    def to_patch(self):
309
 
        yield ('c %(parent)d %(parent_pos)d %(child_pos)d %(num_lines)d\n'
310
 
               % self._as_dict())
 
232
        yield 'c %(parent)d %(parent_pos)d %(child_pos)d %(num_lines)d\n'\
 
233
            % self.__dict__
311
234
 
312
235
 
313
236
class BaseVersionedFile(object):
314
 
    """Pseudo-VersionedFile skeleton for MultiParent"""
 
237
    """VersionedFile skeleton for MultiParent"""
315
238
 
316
239
    def __init__(self, snapshot_interval=25, max_snapshots=None):
317
240
        self._lines = {}
323
246
    def versions(self):
324
247
        return iter(self._parents)
325
248
 
326
 
    def has_version(self, version):
327
 
        return version in self._parents
328
 
 
329
249
    def do_snapshot(self, version_id, parent_ids):
330
 
        """Determine whether to perform a snapshot for this version"""
331
250
        if self.snapshot_interval is None:
332
251
            return False
333
252
        if self.max_snapshots is not None and\
348
267
 
349
268
    def add_version(self, lines, version_id, parent_ids,
350
269
                    force_snapshot=None, single_parent=False):
351
 
        """Add a version to the versionedfile
352
 
 
353
 
        :param lines: The list of lines to add.  Must be split on '\n'.
354
 
        :param version_id: The version_id of the version to add
355
 
        :param force_snapshot: If true, force this version to be added as a
356
 
            snapshot version.  If false, force this version to be added as a
357
 
            diff.  If none, determine this automatically.
358
 
        :param single_parent: If true, use a single parent, rather than
359
 
            multiple parents.
360
 
        """
361
270
        if force_snapshot is None:
362
271
            do_snapshot = self.do_snapshot(version_id, parent_ids)
363
272
        else:
395
304
        :param single_parent: If true, omit all but one parent text, (but
396
305
            retain parent metadata).
397
306
        """
398
 
        if not (no_cache or not verify):
399
 
            raise ValueError()
 
307
        assert no_cache or not verify
400
308
        revisions = set(vf.versions())
401
309
        total = len(revisions)
402
310
        pb = ui.ui_factory.nested_progress_bar()
408
316
                    if [p for p in parents if p not in self._parents] != []:
409
317
                        continue
410
318
                    lines = [a + ' ' + l for a, l in
411
 
                             vf.annotate(revision)]
 
319
                             vf.annotate_iter(revision)]
412
320
                    if snapshots is None:
413
321
                        force_snapshot = None
414
322
                    else:
420
328
                        self.clear_cache()
421
329
                        vf.clear_cache()
422
330
                        if verify:
423
 
                            if not (lines == self.get_line_list([revision])[0]):
424
 
                                raise AssertionError()
 
331
                            assert lines == self.get_line_list([revision])[0]
425
332
                            self.clear_cache()
426
 
                    pb.update(gettext('Importing revisions'),
 
333
                    pb.update('Importing revisions',
427
334
                              (total - len(revisions)) + len(added), total)
428
335
                revisions = [r for r in revisions if r not in added]
429
336
        finally:
430
337
            pb.finished()
431
338
 
432
339
    def select_snapshots(self, vf):
433
 
        """Determine which versions to add as snapshots"""
434
340
        build_ancestors = {}
435
341
        descendants = {}
436
342
        snapshots = set()
457
363
        return [v for n, v in new_snapshots]
458
364
 
459
365
    def get_size_ranking(self):
460
 
        """Get versions ranked by size"""
461
366
        versions = []
462
367
        new_snapshots = set()
463
368
        for version_id in self.versions():
469
374
            versions.append((snapshot_len - diff_len, version_id))
470
375
        versions.sort()
471
376
        return versions
 
377
        return [v for n, v in versions]
472
378
 
473
379
    def import_diffs(self, vf):
474
 
        """Import the diffs from another pseudo-versionedfile"""
475
380
        for version_id in vf.versions():
476
381
            self.add_diff(vf.get_diff(version_id), version_id,
477
382
                          vf._parents[version_id])
478
383
 
479
384
    def get_build_ranking(self):
480
 
        """Return revisions sorted by how much they reduce build complexity"""
481
385
        could_avoid = {}
482
386
        referenced_by = {}
483
387
        for version_id in topo_iter(self):
519
423
            pass
520
424
        diff = self.get_diff(version_id)
521
425
        lines = []
522
 
        reconstructor = _Reconstructor(self, self._lines, self._parents)
 
426
        reconstructor = _Reconstructor(self, self._lines,
 
427
                                       self._parents)
523
428
        reconstructor.reconstruct_version(lines, version_id)
524
429
        self._lines[version_id] = lines
525
430
        return lines
526
431
 
527
432
 
528
433
class MultiMemoryVersionedFile(BaseVersionedFile):
529
 
    """Memory-backed pseudo-versionedfile"""
530
434
 
531
435
    def __init__(self, snapshot_interval=25, max_snapshots=None):
532
436
        BaseVersionedFile.__init__(self, snapshot_interval, max_snapshots)
537
441
        self._parents[version_id] = parent_ids
538
442
 
539
443
    def get_diff(self, version_id):
540
 
        try:
541
 
            return self._diffs[version_id]
542
 
        except KeyError:
543
 
            raise errors.RevisionNotPresent(version_id, self)
 
444
        return self._diffs[version_id]
544
445
 
545
446
    def destroy(self):
546
447
        self._diffs = {}
547
448
 
548
449
 
549
450
class MultiVersionedFile(BaseVersionedFile):
550
 
    """Disk-backed pseudo-versionedfile"""
551
451
 
552
452
    def __init__(self, filename, snapshot_interval=25, max_snapshots=None):
553
453
        BaseVersionedFile.__init__(self, snapshot_interval, max_snapshots)
562
462
            sio = StringIO(infile.read(count))
563
463
        finally:
564
464
            infile.close()
565
 
        zip_file = gzip.GzipFile(None, mode='rb', fileobj=sio)
 
465
        zip_file = GzipFile(None, mode='rb', fileobj=sio)
566
466
        try:
567
467
            file_version_id = zip_file.readline()
568
 
            content = zip_file.read()
569
 
            return MultiParent.from_patch(content)
 
468
            return MultiParent.from_patch(zip_file.readlines())
570
469
        finally:
571
470
            zip_file.close()
572
471
 
573
472
    def add_diff(self, diff, version_id, parent_ids):
574
473
        outfile = open(self._filename + '.mpknit', 'ab')
575
474
        try:
576
 
            outfile.seek(0, 2)      # workaround for windows bug:
577
 
                                    # .tell() for files opened in 'ab' mode
578
 
                                    # before any write returns 0
579
475
            start = outfile.tell()
580
476
            try:
581
 
                zipfile = gzip.GzipFile(None, mode='ab', fileobj=outfile)
 
477
                zipfile = GzipFile(None, mode='ab', fileobj=outfile)
582
478
                zipfile.writelines(itertools.chain(
583
479
                    ['version %s\n' % version_id], diff.to_patch()))
584
480
            finally:
630
526
    def _reconstruct(self, lines, req_version_id, req_start, req_end):
631
527
        """Append lines for the requested version_id range"""
632
528
        # stack of pending range requests
633
 
        if req_start == req_end:
634
 
            return
635
529
        pending_reqs = [(req_version_id, req_start, req_end)]
636
530
        while len(pending_reqs) > 0:
637
531
            req_version_id, req_start, req_end = pending_reqs.pop()
638
532
            # lazily allocate cursors for versions
639
 
            if req_version_id in self.lines:
640
 
                lines.extend(self.lines[req_version_id][req_start:req_end])
641
 
                continue
642
533
            try:
643
534
                start, end, kind, data, iterator = self.cursor[req_version_id]
644
535
            except KeyError:
675
566
 
676
567
def gzip_string(lines):
677
568
    sio = StringIO()
678
 
    data_file = gzip.GzipFile(None, mode='wb', fileobj=sio)
 
569
    data_file = GzipFile(None, mode='wb', fileobj=sio)
679
570
    data_file.writelines(lines)
680
571
    data_file.close()
681
572
    return sio.getvalue()