/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-01-12 13:56:10 UTC
  • mto: This revision was merged to the branch mainline in revision 7443.
  • Revision ID: jelmer@jelmer.uk-20200112135610-0a9bct6x4cw7he6y
Add strip_segment_parameters function.

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 = osutils.chunks_to_lines(record.get_bytes_as('chunked'))
 
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