← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_annotator_py.py

  • Committer: Patch Queue Manager
  • Date: 2016-04-21 04:10:52 UTC
  • mfrom: (6616.1.1 fix-en-user-guide)
  • Revision ID: pqm@pqm.ubuntu.com-20160421041052-clcye7ns1qcl2n7w
(richard-wilbur) Ensure build of English use guide always uses English text
 even when user's locale specifies a different language. (Jelmer Vernooij)

Show diffs side-by-side

added added

removed removed

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