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 19from .lazy_import import lazy_import 20lazy_import(globals(), """ 21 22import patiencediff 23 24from breezy import ( 25 annotate, # Must be lazy to avoid circular importing 26 graph as _mod_graph, 27 ) 28""") 29from . import ( 30 errors, 31 osutils, 32 ui, 33 ) 34 35 36class 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 313