/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

  • Committer: Jelmer Vernooij
  • Date: 2020-03-22 01:35:14 UTC
  • mfrom: (7490.7.6 work)
  • mto: This revision was merged to the branch mainline in revision 7499.
  • Revision ID: jelmer@jelmer.uk-20200322013514-7vw1ntwho04rcuj3
merge lp:brz/3.1.

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 .lazy_import import lazy_import
 
20
lazy_import(globals(), """
 
21
 
 
22
import patiencediff
 
23
 
 
24
from breezy import (
 
25
    annotate, # Must be lazy to avoid circular importing
 
26
    graph as _mod_graph,
 
27
    )
 
28
""")
 
29
from . 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 = {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.items():
 
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
 
101
            # while 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 = record.get_bytes_as('lines')
 
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(
 
148
            None, 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 range(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
        with ui.ui_factory.nested_progress_bar() as pb:
 
261
            for text_key, text, num_lines in self._get_needed_texts(
 
262
                    key, pb=pb):
 
263
                self._annotate_one(text_key, text, num_lines)
 
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(next_head)
 
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:
 
307
                        break  # get the item out of the set
 
308
                else:
 
309
                    head = self._resolve_annotation_tie(the_heads, line,
 
310
                                                        custom_tiebreaker)
 
311
            append((head, line))
 
312
        return out