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