← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/rename_map.py

  • Committer: Aaron Bentley
  • Date: 2009-03-14 22:45:55 UTC
  • mto: This revision was merged to the branch mainline in revision 4196.
  • Revision ID: aaron@aaronbentley.com-20090314224555-bms29zgiiuqny2e0
Cleanup and enhance tests.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/rename_map.py
32
32
 
33
33
    @staticmethod
34
34
    def iter_edge_hashes(lines):
35
 
        """Iterate through the hashes of line pairs (which make up an edge)."""
 
35
        """Iterate through the hashes of line pairs (which make up an edge).
 
36
 
 
37
        The hash is truncated using a modulus to avoid excessive memory
 
38
        consumption by the hitscount dict.  A modulus of 10Mi means that the
 
39
        maximum number of keys is 10Mi.  (Keys are normally 32 bits, e.g.
 
40
        4 Gi)
 
41
        """
36
42
        modulus = 1024 * 1024 * 10
37
43
        for n in range(len(lines)):
38
44
            yield hash(tuple(lines[n:n+2])) % modulus
69
75
        """Count the number of hash hits for each tag, for the given lines.
70
76
 
71
77
        Hits are weighted according to the number of tags the hash is
72
 
        associated with; more tags means that the lines are not unique and
73
 
        should tend to be ignored.
 
78
        associated with; more tags means that the hash is less rare and should
 
79
        tend to be ignored.
74
80
        :param lines: The lines to calculate hashes of.
 
81
        :return: a dict of {tag: hitcount}
75
82
        """
76
83
        hits = {}
77
84
        for my_hash in self.iter_edge_hashes(lines):
90
97
 
91
98
        :return: A list of tuples of count, path, file_id.
92
99
        """
93
 
        ordered_hits = []
 
100
        all_hits = []
94
101
        task = ui_factory.nested_progress_bar()
95
102
        try:
96
103
            for num, path in enumerate(paths):
100
107
                    hits = self.hitcounts(my_file.readlines())
101
108
                finally:
102
109
                    my_file.close()
103
 
                ordered_hits.extend((v, path, k) for k, v in hits.items())
 
110
                all_hits.extend((v, path, k) for k, v in hits.items())
104
111
        finally:
105
112
            task.finished()
106
 
        return ordered_hits
 
113
        return all_hits
107
114
 
108
115
    def file_match(self, tree, paths):
109
116
        """Return a mapping from file_ids to the supplied paths."""
110
 
        ordered_hits = self.get_all_hits(tree, paths)
111
 
        ordered_hits.sort(reverse=True)
112
 
        return self._match_hits(ordered_hits)
 
117
        return self._match_hits(self.get_all_hits(tree, paths))
113
118
 
114
119
    @staticmethod
115
 
    def _match_hits(ordered_hits):
 
120
    def _match_hits(hit_list):
 
121
        """Using a hit list, determin a path-to-fileid map.
 
122
 
 
123
        The hit list is a list of (count, path, file_id), where count is a
 
124
        (possibly float) number, with higher numbers indicating stronger
 
125
        matches.
 
126
        """
116
127
        seen_file_ids = set()
117
128
        seen_paths = set()
118
129
        path_map = {}
119
 
        for count, path, file_id in ordered_hits:
 
130
        for count, path, file_id in sorted(hit_list, reverse=True):
120
131
            if path in seen_paths or file_id in seen_file_ids:
121
132
                continue
122
133
            path_map[path] = file_id
125
136
        return path_map
126
137
 
127
138
    def get_required_parents(self, matches, tree):
 
139
        """Return a dict of all file parents that must be versioned.
 
140
 
 
141
        The keys are the required parents and the values are sets of their
 
142
        children.
 
143
        """
128
144
        required_parents = {}
129
145
        for path in matches:
130
146
            while True:
144
160
        return require_ids
145
161
 
146
162
    def match_parents(self, required_parents, missing_parents):
147
 
        ordered_hits = []
 
163
        """Map parent directories to file-ids.
 
164
 
 
165
        This is done by finding similarity between the file-ids of children of
 
166
        required parent directories and the file-ids of children of missing
 
167
        parent directories.
 
168
        """
 
169
        all_hits = []
148
170
        for file_id, file_id_children in missing_parents.iteritems():
149
171
            for path, path_children in required_parents.iteritems():
150
172
                hits = len(path_children.intersection(file_id_children))
151
173
                if hits > 0:
152
 
                    ordered_hits.append((hits, path, file_id))
153
 
        ordered_hits.sort(reverse=True)
154
 
        return self._match_hits(ordered_hits)
 
174
                    all_hits.append((hits, path, file_id))
 
175
        return self._match_hits(all_hits)
155
176
 
156
177
    @staticmethod
157
178
    def guess_renames(tree):