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 bzrlib.lazy_import import lazy_import
22
lazy_import(globals(), """
24
annotate, # Must be lazy to avoid circular importing
36
class Annotator(object):
37
"""Class that drives performing annotations."""
39
def __init__(self, vf):
40
"""Create a new Annotator from a VersionedFile."""
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 = {}
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
55
self._num_needed_children[parent_key] = 1
57
def _get_needed_keys(self, key):
58
"""Determine the texts we need to get from the backing vf.
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
67
parent_map = self._parent_map
68
# We need 1 extra copy of the node we will be looking at when we are
70
self._num_needed_children[key] = 1
71
vf_keys_needed = set()
72
ann_keys_needed = set()
73
needed_keys = set([key])
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]
88
parent_lookup.append(key)
89
vf_keys_needed.add(key)
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
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
105
def _get_needed_texts(self, key, pb=None):
106
"""Get the texts we need to properly annotate key.
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.
114
keys, ann_keys = self._get_needed_keys(key)
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):
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
129
lines = self._text_cache[key]
130
num_lines = len(lines)
131
yield key, lines, num_lines
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.
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
141
matching_blocks is a list of (parent_idx, text_idx, len) tuples
142
indicating which lines match between the two texts
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,
149
matching_blocks = matcher.get_matching_blocks()
150
return parent_annotations, matching_blocks
152
def _update_from_first_parent(self, key, annotations, lines, parent_key):
153
"""Reannotate this text relative to its first parent."""
155
matching_blocks) = self._get_parent_annotations_and_matches(
156
key, lines, parent_key)
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]
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."""
167
matching_blocks) = self._get_parent_annotations_and_matches(
168
key, lines, parent_key)
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:
186
for idx in xrange(match_len):
188
par_ann = par_sub[idx]
189
ann_idx = lines_idx + idx
193
if ann == this_annotation:
194
# Originally claimed 'this', but it was really in this
196
annotations[ann_idx] = par_ann
198
# Resolve the fact that both sides have a different value for
200
if ann == last_ann and par_ann == last_parent:
201
annotations[ann_idx] = last_res
204
new_ann.update(par_ann)
205
new_ann = tuple(sorted(new_ann))
206
annotations[ann_idx] = new_ann
208
last_parent = par_ann
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]
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
221
self._num_needed_children[parent_key] = num
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]
229
self._update_from_first_parent(key, annotations, text,
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)
236
def add_special_text(self, key, parent_keys, text):
237
"""Add a specific text to the graph.
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.)
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
247
self._parent_map[key] = parent_keys
248
self._text_cache[key] = osutils.split_lines(text)
249
self._heads_provider = None
251
def annotate(self, key):
252
"""Return annotated fulltext for the given key.
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
260
pb = ui.ui_factory.nested_progress_bar()
262
for text_key, text, num_lines in self._get_needed_texts(key, pb=pb):
263
self._annotate_one(text_key, text, num_lines)
267
annotations = self._annotations_cache[key]
269
raise errors.RevisionNotPresent(key, self._vf)
270
return annotations, self._text_cache[key]
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
277
def _resolve_annotation_tie(self, the_heads, line, tiebreaker):
278
if tiebreaker is None:
279
head = sorted(the_heads)[0]
281
# Backwards compatibility, break up the heads into pairs and
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]
290
def annotate_flat(self, key):
291
"""Determine the single-best-revision to source for each line.
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.
297
custom_tiebreaker = annotate._break_annotation_tie
298
annotations, lines = self.annotate(key)
300
heads = self._get_heads_provider().heads
302
for annotation, line in zip(annotations, lines):
303
if len(annotation) == 1:
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
310
head = self._resolve_annotation_tie(the_heads, line,
added
removed
bzrlib/_annotator_py.py
