← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_groupcompress_py.py

Start adding permutation tests for _groupcompress_py and _groupcompress_pyx
We need to implement make_delta() for the python version.
(maybe, but it would be a good test for apply_delta, which we *do* care about)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_groupcompress_py.py
57
57
        except KeyError:
58
58
            return None
59
59
 
 
60
    def _get_longest_match(self, pos, max_pos, locations):
 
61
        """Get the longest possible match for the current position."""
 
62
        range_start = pos
 
63
        range_len = 0
 
64
        copy_ends = None
 
65
        while pos < max_pos:
 
66
            if locations is None:
 
67
                locations = self.get_idx_matches(pos)
 
68
            if locations is None:
 
69
                # No more matches, just return whatever we have, but we know that
 
70
                # this last position is not going to match anything
 
71
                pos += 1
 
72
                break
 
73
            else:
 
74
                if copy_ends is None:
 
75
                    # We are starting a new range
 
76
                    copy_ends = [loc + 1 for loc in locations]
 
77
                    range_len = 1
 
78
                    locations = None # Consumed
 
79
                else:
 
80
                    # We are currently in the middle of a match
 
81
                    next_locations = set(copy_ends).intersection(locations)
 
82
                    if len(next_locations):
 
83
                        # range continues
 
84
                        copy_ends = [loc + 1 for loc in next_locations]
 
85
                        range_len += 1
 
86
                        locations = None # Consumed
 
87
                    else:
 
88
                        # But we are done with this match, we should be
 
89
                        # starting a new one, though. We will pass back
 
90
                        # 'locations' so that we don't have to do another
 
91
                        # lookup.
 
92
                        break
 
93
            pos += 1
 
94
        if copy_ends is None:
 
95
            return None, pos, locations
 
96
        return (((min(copy_ends) - range_len, range_start, range_len)),
 
97
                pos, locations)
 
98
 
 
99
    def get_matching_blocks(self, lines, soft=False):
 
100
        """Return the ranges in lines which match self.lines.
 
101
 
 
102
        :param lines: lines to compress
 
103
        :return: A list of (old_start, new_start, length) tuples which reflect
 
104
            a region in self.lines that is present in lines.  The last element
 
105
            of the list is always (old_len, new_len, 0) to provide a end point
 
106
            for generating instructions from the matching blocks list.
 
107
        """
 
108
        result = []
 
109
        pos = 0
 
110
        self.set_right_lines(lines)
 
111
        locations = None
 
112
        max_pos = len(lines)
 
113
        result_append = result.append
 
114
        min_match_bytes = 10
 
115
        if soft:
 
116
            min_match_bytes = 200
 
117
        while pos < max_pos:
 
118
            block, pos, locations = self._get_longest_match(pos, max_pos,
 
119
                                                            locations)
 
120
            if block is not None:
 
121
                # Check to see if we are matching fewer than 5 characters,
 
122
                # which is turned into a simple 'insert', rather than a copy
 
123
                # If we have more than 5 lines, we definitely have more than 5
 
124
                # chars
 
125
                if block[-1] < min_match_bytes:
 
126
                    # This block may be a 'short' block, check
 
127
                    old_start, new_start, range_len = block
 
128
                    matched_bytes = sum(map(len,
 
129
                        lines[new_start:new_start + range_len]))
 
130
                    if matched_bytes < min_match_bytes:
 
131
                        block = None
 
132
            if block is not None:
 
133
                result_append(block)
 
134
        result_append((len(self.lines), len(lines), 0))
 
135
        return result
 
136
 
60
137
    def _get_matching_lines(self):
61
138
        """Return a dictionary showing matching lines."""
62
139
        matching = {}
87
164
        self._right_lines = lines
88
165
 
89
166
 
90
 
def _get_longest_match(equivalence_table, pos, max_pos, locations):
91
 
    """Get the longest possible match for the current position."""
92
 
    range_start = pos
93
 
    range_len = 0
94
 
    copy_ends = None
95
 
    while pos < max_pos:
96
 
        if locations is None:
97
 
            locations = equivalence_table.get_idx_matches(pos)
98
 
        if locations is None:
99
 
            # No more matches, just return whatever we have, but we know that
100
 
            # this last position is not going to match anything
101
 
            pos += 1
102
 
            break
103
 
        else:
104
 
            if copy_ends is None:
105
 
                # We are starting a new range
106
 
                copy_ends = [loc + 1 for loc in locations]
107
 
                range_len = 1
108
 
                locations = None # Consumed
109
 
            else:
110
 
                # We are currently in the middle of a match
111
 
                next_locations = set(copy_ends).intersection(locations)
112
 
                if len(next_locations):
113
 
                    # range continues
114
 
                    copy_ends = [loc + 1 for loc in next_locations]
115
 
                    range_len += 1
116
 
                    locations = None # Consumed
117
 
                else:
118
 
                    # But we are done with this match, we should be
119
 
                    # starting a new one, though. We will pass back 'locations'
120
 
                    # so that we don't have to do another lookup.
121
 
                    break
122
 
        pos += 1
123
 
    if copy_ends is None:
124
 
        return None, pos, locations
125
 
    return ((min(copy_ends) - range_len, range_start, range_len)), pos, locations
 
167
 
 
168
def make_delta(source_bytes, target_bytes):
 
169
    """Create a delta from source to target."""
 
170
    line_locations = EquivalenceTable([])
 
171
    return None
126
172
 
127
173
 
128
174
def apply_delta(basis, delta):