~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_annotator_py.py

  • Committer: Martin von Gagern
  • Date: 2011-06-01 12:53:56 UTC
  • mto: This revision was merged to the branch mainline in revision 6009.
  • Revision ID: martin.vgagern@gmx.net-20110601125356-lwozv2vecea6hxfz
Change from no_decorate to classify as name for the argument.

The command line switch remains as --no-classify, to keep backwards
compatibility.  Users are free to include --no-classify in an alias, and
still use --classify to change back.

Show diffs side-by-side

added added

removed removed

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