← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_annotator_py.py

(igc) What's New in Bazaar 2.1 document

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_annotator_py.py
 
1
# Copyright (C) 2009 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
"""Functionality for doing annotations in the 'optimal' way"""
 
18
 
 
19
from bzrlib.lazy_import import lazy_import
 
20
lazy_import(globals(), """
 
21
from bzrlib import annotate # Must be lazy to avoid circular importing
 
22
""")
 
23
from bzrlib import (
 
24
    errors,
 
25
    graph as _mod_graph,
 
26
    osutils,
 
27
    patiencediff,
 
28
    ui,
 
29
    )
 
30
 
 
31
 
 
32
class Annotator(object):
 
33
    """Class that drives performing annotations."""
 
34
 
 
35
    def __init__(self, vf):
 
36
        """Create a new Annotator from a VersionedFile."""
 
37
        self._vf = vf
 
38
        self._parent_map = {}
 
39
        self._text_cache = {}
 
40
        # Map from key => number of nexts that will be built from this key
 
41
        self._num_needed_children = {}
 
42
        self._annotations_cache = {}
 
43
        self._heads_provider = None
 
44
        self._ann_tuple_cache = {}
 
45
 
 
46
    def _update_needed_children(self, key, parent_keys):
 
47
        for parent_key in parent_keys:
 
48
            if parent_key in self._num_needed_children:
 
49
                self._num_needed_children[parent_key] += 1
 
50
            else:
 
51
                self._num_needed_children[parent_key] = 1
 
52
 
 
53
    def _get_needed_keys(self, key):
 
54
        """Determine the texts we need to get from the backing vf.
 
55
 
 
56
        :return: (vf_keys_needed, ann_keys_needed)
 
57
            vf_keys_needed  These are keys that we need to get from the vf
 
58
            ann_keys_needed Texts which we have in self._text_cache but we
 
59
                            don't have annotations for. We need to yield these
 
60
                            in the proper order so that we can get proper
 
61
                            annotations.
 
62
        """
 
63
        parent_map = self._parent_map
 
64
        # We need 1 extra copy of the node we will be looking at when we are
 
65
        # done
 
66
        self._num_needed_children[key] = 1
 
67
        vf_keys_needed = set()
 
68
        ann_keys_needed = set()
 
69
        needed_keys = set([key])
 
70
        while needed_keys:
 
71
            parent_lookup = []
 
72
            next_parent_map = {}
 
73
            for key in needed_keys:
 
74
                if key in self._parent_map:
 
75
                    # We don't need to lookup this key in the vf
 
76
                    if key not in self._text_cache:
 
77
                        # Extract this text from the vf
 
78
                        vf_keys_needed.add(key)
 
79
                    elif key not in self._annotations_cache:
 
80
                        # We do need to annotate
 
81
                        ann_keys_needed.add(key)
 
82
                        next_parent_map[key] = self._parent_map[key]
 
83
                else:
 
84
                    parent_lookup.append(key)
 
85
                    vf_keys_needed.add(key)
 
86
            needed_keys = set()
 
87
            next_parent_map.update(self._vf.get_parent_map(parent_lookup))
 
88
            for key, parent_keys in next_parent_map.iteritems():
 
89
                if parent_keys is None: # No graph versionedfile
 
90
                    parent_keys = ()
 
91
                    next_parent_map[key] = ()
 
92
                self._update_needed_children(key, parent_keys)
 
93
                needed_keys.update([key for key in parent_keys
 
94
                                         if key not in parent_map])
 
95
            parent_map.update(next_parent_map)
 
96
            # _heads_provider does some graph caching, so it is only valid while
 
97
            # self._parent_map hasn't changed
 
98
            self._heads_provider = None
 
99
        return vf_keys_needed, ann_keys_needed
 
100
 
 
101
    def _get_needed_texts(self, key, pb=None):
 
102
        """Get the texts we need to properly annotate key.
 
103
 
 
104
        :param key: A Key that is present in self._vf
 
105
        :return: Yield (this_key, text, num_lines)
 
106
            'text' is an opaque object that just has to work with whatever
 
107
            matcher object we are using. Currently it is always 'lines' but
 
108
            future improvements may change this to a simple text string.
 
109
        """
 
110
        keys, ann_keys = self._get_needed_keys(key)
 
111
        if pb is not None:
 
112
            pb.update('getting stream', 0, len(keys))
 
113
        stream  = self._vf.get_record_stream(keys, 'topological', True)
 
114
        for idx, record in enumerate(stream):
 
115
            if pb is not None:
 
116
                pb.update('extracting', 0, len(keys))
 
117
            if record.storage_kind == 'absent':
 
118
                raise errors.RevisionNotPresent(record.key, self._vf)
 
119
            this_key = record.key
 
120
            lines = osutils.chunks_to_lines(record.get_bytes_as('chunked'))
 
121
            num_lines = len(lines)
 
122
            self._text_cache[this_key] = lines
 
123
            yield this_key, lines, num_lines
 
124
        for key in ann_keys:
 
125
            lines = self._text_cache[key]
 
126
            num_lines = len(lines)
 
127
            yield key, lines, num_lines
 
128
 
 
129
    def _get_parent_annotations_and_matches(self, key, text, parent_key):
 
130
        """Get the list of annotations for the parent, and the matching lines.
 
131
 
 
132
        :param text: The opaque value given by _get_needed_texts
 
133
        :param parent_key: The key for the parent text
 
134
        :return: (parent_annotations, matching_blocks)
 
135
            parent_annotations is a list as long as the number of lines in
 
136
                parent
 
137
            matching_blocks is a list of (parent_idx, text_idx, len) tuples
 
138
                indicating which lines match between the two texts
 
139
        """
 
140
        parent_lines = self._text_cache[parent_key]
 
141
        parent_annotations = self._annotations_cache[parent_key]
 
142
        # PatienceSequenceMatcher should probably be part of Policy
 
143
        matcher = patiencediff.PatienceSequenceMatcher(None,
 
144
            parent_lines, text)
 
145
        matching_blocks = matcher.get_matching_blocks()
 
146
        return parent_annotations, matching_blocks
 
147
 
 
148
    def _update_from_first_parent(self, key, annotations, lines, parent_key):
 
149
        """Reannotate this text relative to its first parent."""
 
150
        (parent_annotations,
 
151
         matching_blocks) = self._get_parent_annotations_and_matches(
 
152
                                key, lines, parent_key)
 
153
 
 
154
        for parent_idx, lines_idx, match_len in matching_blocks:
 
155
            # For all matching regions we copy across the parent annotations
 
156
            annotations[lines_idx:lines_idx + match_len] = \
 
157
                parent_annotations[parent_idx:parent_idx + match_len]
 
158
 
 
159
    def _update_from_other_parents(self, key, annotations, lines,
 
160
                                   this_annotation, parent_key):
 
161
        """Reannotate this text relative to a second (or more) parent."""
 
162
        (parent_annotations,
 
163
         matching_blocks) = self._get_parent_annotations_and_matches(
 
164
                                key, lines, parent_key)
 
165
 
 
166
        last_ann = None
 
167
        last_parent = None
 
168
        last_res = None
 
169
        # TODO: consider making all annotations unique and then using 'is'
 
170
        #       everywhere. Current results claim that isn't any faster,
 
171
        #       because of the time spent deduping
 
172
        #       deduping also saves a bit of memory. For NEWS it saves ~1MB,
 
173
        #       but that is out of 200-300MB for extracting everything, so a
 
174
        #       fairly trivial amount
 
175
        for parent_idx, lines_idx, match_len in matching_blocks:
 
176
            # For lines which match this parent, we will now resolve whether
 
177
            # this parent wins over the current annotation
 
178
            ann_sub = annotations[lines_idx:lines_idx + match_len]
 
179
            par_sub = parent_annotations[parent_idx:parent_idx + match_len]
 
180
            if ann_sub == par_sub:
 
181
                continue
 
182
            for idx in xrange(match_len):
 
183
                ann = ann_sub[idx]
 
184
                par_ann = par_sub[idx]
 
185
                ann_idx = lines_idx + idx
 
186
                if ann == par_ann:
 
187
                    # Nothing to change
 
188
                    continue
 
189
                if ann == this_annotation:
 
190
                    # Originally claimed 'this', but it was really in this
 
191
                    # parent
 
192
                    annotations[ann_idx] = par_ann
 
193
                    continue
 
194
                # Resolve the fact that both sides have a different value for
 
195
                # last modified
 
196
                if ann == last_ann and par_ann == last_parent:
 
197
                    annotations[ann_idx] = last_res
 
198
                else:
 
199
                    new_ann = set(ann)
 
200
                    new_ann.update(par_ann)
 
201
                    new_ann = tuple(sorted(new_ann))
 
202
                    annotations[ann_idx] = new_ann
 
203
                    last_ann = ann
 
204
                    last_parent = par_ann
 
205
                    last_res = new_ann
 
206
 
 
207
    def _record_annotation(self, key, parent_keys, annotations):
 
208
        self._annotations_cache[key] = annotations
 
209
        for parent_key in parent_keys:
 
210
            num = self._num_needed_children[parent_key]
 
211
            num -= 1
 
212
            if num == 0:
 
213
                del self._text_cache[parent_key]
 
214
                del self._annotations_cache[parent_key]
 
215
                # Do we want to clean up _num_needed_children at this point as
 
216
                # well?
 
217
            self._num_needed_children[parent_key] = num
 
218
 
 
219
    def _annotate_one(self, key, text, num_lines):
 
220
        this_annotation = (key,)
 
221
        # Note: annotations will be mutated by calls to _update_from*
 
222
        annotations = [this_annotation] * num_lines
 
223
        parent_keys = self._parent_map[key]
 
224
        if parent_keys:
 
225
            self._update_from_first_parent(key, annotations, text,
 
226
                                           parent_keys[0])
 
227
            for parent in parent_keys[1:]:
 
228
                self._update_from_other_parents(key, annotations, text,
 
229
                                                this_annotation, parent)
 
230
        self._record_annotation(key, parent_keys, annotations)
 
231
 
 
232
    def add_special_text(self, key, parent_keys, text):
 
233
        """Add a specific text to the graph.
 
234
 
 
235
        This is used to add a text which is not otherwise present in the
 
236
        versioned file. (eg. a WorkingTree injecting 'current:' into the
 
237
        graph to annotate the edited content.)
 
238
 
 
239
        :param key: The key to use to request this text be annotated
 
240
        :param parent_keys: The parents of this text
 
241
        :param text: A string containing the content of the text
 
242
        """
 
243
        self._parent_map[key] = parent_keys
 
244
        self._text_cache[key] = osutils.split_lines(text)
 
245
        self._heads_provider = None
 
246
 
 
247
    def annotate(self, key):
 
248
        """Return annotated fulltext for the given key.
 
249
 
 
250
        :param key: A tuple defining the text to annotate
 
251
        :return: ([annotations], [lines])
 
252
            annotations is a list of tuples of keys, one for each line in lines
 
253
                        each key is a possible source for the given line.
 
254
            lines the text of "key" as a list of lines
 
255
        """
 
256
        pb = ui.ui_factory.nested_progress_bar()
 
257
        try:
 
258
            for text_key, text, num_lines in self._get_needed_texts(key, pb=pb):
 
259
                self._annotate_one(text_key, text, num_lines)
 
260
        finally:
 
261
            pb.finished()
 
262
        try:
 
263
            annotations = self._annotations_cache[key]
 
264
        except KeyError:
 
265
            raise errors.RevisionNotPresent(key, self._vf)
 
266
        return annotations, self._text_cache[key]
 
267
 
 
268
    def _get_heads_provider(self):
 
269
        if self._heads_provider is None:
 
270
            self._heads_provider = _mod_graph.KnownGraph(self._parent_map)
 
271
        return self._heads_provider
 
272
 
 
273
    def _resolve_annotation_tie(self, the_heads, line, tiebreaker):
 
274
        if tiebreaker is None:
 
275
            head = sorted(the_heads)[0]
 
276
        else:
 
277
            # Backwards compatibility, break up the heads into pairs and
 
278
            # resolve the result
 
279
            next_head = iter(the_heads)
 
280
            head = next_head.next()
 
281
            for possible_head in next_head:
 
282
                annotated_lines = ((head, line), (possible_head, line))
 
283
                head = tiebreaker(annotated_lines)[0]
 
284
        return head
 
285
 
 
286
    def annotate_flat(self, key):
 
287
        """Determine the single-best-revision to source for each line.
 
288
 
 
289
        This is meant as a compatibility thunk to how annotate() used to work.
 
290
        :return: [(ann_key, line)]
 
291
            A list of tuples with a single annotation key for each line.
 
292
        """
 
293
        custom_tiebreaker = annotate._break_annotation_tie
 
294
        annotations, lines = self.annotate(key)
 
295
        out = []
 
296
        heads = self._get_heads_provider().heads
 
297
        append = out.append
 
298
        for annotation, line in zip(annotations, lines):
 
299
            if len(annotation) == 1:
 
300
                head = annotation[0]
 
301
            else:
 
302
                the_heads = heads(annotation)
 
303
                if len(the_heads) == 1:
 
304
                    for head in the_heads: break # get the item out of the set
 
305
                else:
 
306
                    head = self._resolve_annotation_tie(the_heads, line,
 
307
                                                        custom_tiebreaker)
 
308
            append((head, line))
 
309
        return out