/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 bzrlib/merge_directive.py

  • Committer: John Arbash Meinel
  • Date: 2009-10-12 15:55:26 UTC
  • mto: (4679.5.3 2.1-static-tuple-no-use)
  • mto: This revision was merged to the branch mainline in revision 4735.
  • Revision ID: john@arbash-meinel.com-20091012155526-b46tuz5cibebbnct
Change the _lookup function to use Quadratic Probing.

The main strength is that we get a bit of locality (collision resolution
looks quickly close to the location.)
The main weakness is that we don't use the upper bits of the hash to
induce divergence. So while we nicely handle collisions in neighboring
buckets (Quadratic means their resolution chains will diverge), if
two objects hash to the same bucket, their resolution chains are identical.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/merge_directive.py
1
 
# Copyright (C) 2007-2010 Canonical Ltd
 
1
# Copyright (C) 2007 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
64
64
            " provided to the next.", (1, 15, 0), False))
65
65
 
66
66
 
67
 
class BaseMergeDirective(object):
68
 
    """A request to perform a merge into a branch.
69
 
 
70
 
    This is the base class that all merge directive implementations 
71
 
    should derive from.
72
 
 
73
 
    :cvar multiple_output_files: Whether or not this merge directive 
74
 
        stores a set of revisions in more than one file
75
 
    """
 
67
class _BaseMergeDirective(object):
76
68
 
77
69
    hooks = MergeDirectiveHooks()
78
70
 
79
 
    multiple_output_files = False
80
 
 
81
71
    def __init__(self, revision_id, testament_sha1, time, timezone,
82
72
                 target_branch, patch=None, source_branch=None, message=None,
83
73
                 bundle=None):
102
92
        self.source_branch = source_branch
103
93
        self.message = message
104
94
 
105
 
    def to_lines(self):
106
 
        """Serialize as a list of lines
107
 
 
108
 
        :return: a list of lines
109
 
        """
110
 
        raise NotImplementedError(self.to_lines)
111
 
 
112
 
    def to_files(self):
113
 
        """Serialize as a set of files.
114
 
 
115
 
        :return: List of tuples with filename and contents as lines
116
 
        """
117
 
        raise NotImplementedError(self.to_files)
118
 
 
119
 
    def get_raw_bundle(self):
120
 
        """Return the bundle for this merge directive.
121
 
 
122
 
        :return: bundle text or None if there is no bundle
123
 
        """
124
 
        return None
125
 
 
126
95
    def _to_lines(self, base_revision=False):
127
96
        """Serialize as a list of lines
128
97
 
142
111
        lines.append('# \n')
143
112
        return lines
144
113
 
145
 
    def write_to_directory(self, path):
146
 
        """Write this merge directive to a series of files in a directory.
147
 
 
148
 
        :param path: Filesystem path to write to
149
 
        """
150
 
        raise NotImplementedError(self.write_to_directory)
151
 
 
152
114
    @classmethod
153
115
    def from_objects(klass, repository, revision_id, time, timezone,
154
116
                 target_branch, patch_type='bundle',
341
303
                                          basename, body)
342
304
 
343
305
 
344
 
class MergeDirective(BaseMergeDirective):
 
306
class MergeDirective(_BaseMergeDirective):
345
307
 
346
308
    """A request to perform a merge into a branch.
347
309
 
376
338
        :param source_branch: A public location to merge the revision from
377
339
        :param message: The message to use when committing this merge
378
340
        """
379
 
        BaseMergeDirective.__init__(self, revision_id, testament_sha1, time,
 
341
        _BaseMergeDirective.__init__(self, revision_id, testament_sha1, time,
380
342
            timezone, target_branch, patch, source_branch, message)
381
343
        if patch_type not in (None, 'diff', 'bundle'):
382
344
            raise ValueError(patch_type)
409
371
        :return: a MergeRequest
410
372
        """
411
373
        line_iter = iter(lines)
412
 
        firstline = ""
413
374
        for line in line_iter:
414
375
            if line.startswith('# Bazaar merge directive format '):
415
 
                return _format_registry.get(line[2:].rstrip())._from_lines(
416
 
                    line_iter)
417
 
            firstline = firstline or line.strip()
418
 
        raise errors.NotAMergeDirective(firstline)
 
376
                break
 
377
        else:
 
378
            if len(lines) > 0:
 
379
                raise errors.NotAMergeDirective(lines[0])
 
380
            else:
 
381
                raise errors.NotAMergeDirective('')
 
382
        return _format_registry.get(line[2:].rstrip())._from_lines(line_iter)
419
383
 
420
384
    @classmethod
421
385
    def _from_lines(klass, line_iter):
466
430
        return None, self.revision_id, 'inapplicable'
467
431
 
468
432
 
469
 
class MergeDirective2(BaseMergeDirective):
 
433
class MergeDirective2(_BaseMergeDirective):
470
434
 
471
435
    _format_string = 'Bazaar merge directive format 2 (Bazaar 0.90)'
472
436
 
475
439
                 bundle=None, base_revision_id=None):
476
440
        if source_branch is None and bundle is None:
477
441
            raise errors.NoMergeSource()
478
 
        BaseMergeDirective.__init__(self, revision_id, testament_sha1, time,
 
442
        _BaseMergeDirective.__init__(self, revision_id, testament_sha1, time,
479
443
            timezone, target_branch, patch, source_branch, message)
480
444
        self.bundle = bundle
481
445
        self.base_revision_id = base_revision_id
618
582
                    revision_id):
619
583
                    raise errors.PublicBranchOutOfDate(public_branch,
620
584
                                                       revision_id)
621
 
            testament_sha1 = t.as_sha1()
622
585
        finally:
623
586
            for entry in reversed(locked):
624
587
                entry.unlock()
625
 
        return klass(revision_id, testament_sha1, time, timezone,
626
 
            target_branch, patch, public_branch, message, bundle,
627
 
            base_revision_id)
 
588
        return klass(revision_id, t.as_sha1(), time, timezone, target_branch,
 
589
            patch, public_branch, message, bundle, base_revision_id)
628
590
 
629
591
    def _verify_patch(self, repository):
630
592
        calculated_patch = self._generate_diff(repository, self.revision_id,