/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to breezy/_annotator_py.py

[merge] robertc's integration, updated tests to check for retcode=3

Show diffs side-by-side

added added

removed removed

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