← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_annotator_pyx.pyx

  • Committer: John Arbash Meinel
  • Date: 2009-06-23 20:20:39 UTC
  • mto: This revision was merged to the branch mainline in revision 4522.
  • Revision ID: john@arbash-meinel.com-20090623202039-kr6mxu576z5vc4y5
Initial implementation of a Pyrex annotator.

Drops the time down to 8.6s down from 9.7s.
This implementation is basically just a copy of the python one, so I'm
a bit surprised to see that much of a win already.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_annotator_pyx.pyx
 
1
# Copyright (C) 2009 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 bzrlib import errors, graph as _mod_graph, osutils, patiencediff, ui
 
20
 
 
21
 
 
22
cdef class _NeededTextIterator:
 
23
 
 
24
    cdef object counter
 
25
    cdef object text_cache
 
26
    cdef object stream
 
27
    cdef object stream_len
 
28
    cdef object pb
 
29
 
 
30
    def __init__(self, stream, text_cache, stream_len, pb=None):
 
31
        self.counter = 0
 
32
        self.stream = stream
 
33
        self.stream_len = stream_len
 
34
        self.text_cache = text_cache
 
35
        self.stream_len = stream_len
 
36
        self.pb = pb
 
37
 
 
38
    def __iter__(self):
 
39
        return self
 
40
 
 
41
    def __next__(self):
 
42
        record = self.stream.next()
 
43
        if self.pb is not None:
 
44
            self.pb.update('extracting', self.counter, self.stream_len)
 
45
        self.counter = self.counter + 1
 
46
        lines = osutils.chunks_to_lines(record.get_bytes_as('chunked'))
 
47
        num_lines = len(lines)
 
48
        self.text_cache[record.key] = lines
 
49
        return record.key, lines, num_lines
 
50
 
 
51
 
 
52
class Annotator:
 
53
    """Class that drives performing annotations."""
 
54
 
 
55
    def __init__(self, vf):
 
56
        """Create a new Annotator from a VersionedFile."""
 
57
        self._vf = vf
 
58
        self._parent_map = {}
 
59
        self._text_cache = {}
 
60
        # Map from key => number of nexts that will be built from this key
 
61
        self._num_needed_children = {}
 
62
        self._annotations_cache = {}
 
63
        self._heads_provider = None
 
64
 
 
65
    def _get_needed_keys(self, key):
 
66
        graph = _mod_graph.Graph(self._vf)
 
67
        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
        for key, parent_keys in graph.iter_ancestry([key]):
 
72
            if parent_keys is None:
 
73
                continue
 
74
            parent_map[key] = parent_keys
 
75
            for parent_key in parent_keys:
 
76
                if parent_key in self._num_needed_children:
 
77
                    self._num_needed_children[parent_key] += 1
 
78
                else:
 
79
                    self._num_needed_children[parent_key] = 1
 
80
        self._parent_map.update(parent_map)
 
81
        # _heads_provider does some graph caching, so it is only valid while
 
82
        # self._parent_map hasn't changed
 
83
        self._heads_provider = None
 
84
        keys = parent_map.keys()
 
85
        return keys
 
86
 
 
87
    def _get_needed_texts(self, key, pb=None):
 
88
        """Get the texts we need to properly annotate key.
 
89
 
 
90
        :param key: A Key that is present in self._vf
 
91
        :return: Yield (this_key, text, num_lines)
 
92
            'text' is an opaque object that just has to work with whatever
 
93
            matcher object we are using. Currently it is always 'lines' but
 
94
            future improvements may change this to a simple text string.
 
95
        """
 
96
        keys = self._get_needed_keys(key)
 
97
        if pb is not None:
 
98
            pb.update('getting stream', 0, len(keys))
 
99
        stream  = self._vf.get_record_stream(keys, 'topological', True)
 
100
        iterator = _NeededTextIterator(stream, self._text_cache, len(keys), pb)
 
101
        return iterator
 
102
 
 
103
    def _get_parent_annotations_and_matches(self, key, text, parent_key):
 
104
        """Get the list of annotations for the parent, and the matching lines.
 
105
 
 
106
        :param text: The opaque value given by _get_needed_texts
 
107
        :param parent_key: The key for the parent text
 
108
        :return: (parent_annotations, matching_blocks)
 
109
            parent_annotations is a list as long as the number of lines in
 
110
                parent
 
111
            matching_blocks is a list of (parent_idx, text_idx, len) tuples
 
112
                indicating which lines match between the two texts
 
113
        """
 
114
        parent_lines = self._text_cache[parent_key]
 
115
        parent_annotations = self._annotations_cache[parent_key]
 
116
        # PatienceSequenceMatcher should probably be part of Policy
 
117
        matcher = patiencediff.PatienceSequenceMatcher(None,
 
118
            parent_lines, text)
 
119
        matching_blocks = matcher.get_matching_blocks()
 
120
        return parent_annotations, matching_blocks
 
121
 
 
122
    def _update_from_one_parent(self, key, annotations, lines, parent_key):
 
123
        """Reannotate this text relative to its first parent."""
 
124
        parent_annotations, matching_blocks = self._get_parent_annotations_and_matches(
 
125
            key, lines, parent_key)
 
126
 
 
127
        for parent_idx, lines_idx, match_len in matching_blocks:
 
128
            # For all matching regions we copy across the parent annotations
 
129
            annotations[lines_idx:lines_idx + match_len] = \
 
130
                parent_annotations[parent_idx:parent_idx + match_len]
 
131
 
 
132
    def _update_from_other_parents(self, key, annotations, lines,
 
133
                                   this_annotation, parent_key):
 
134
        """Reannotate this text relative to a second (or more) parent."""
 
135
        parent_annotations, matching_blocks = self._get_parent_annotations_and_matches(
 
136
            key, lines, parent_key)
 
137
 
 
138
        last_ann = None
 
139
        last_parent = None
 
140
        last_res = None
 
141
        # TODO: consider making all annotations unique and then using 'is'
 
142
        #       everywhere. Current results claim that isn't any faster,
 
143
        #       because of the time spent deduping
 
144
        #       deduping also saves a bit of memory. For NEWS it saves ~1MB,
 
145
        #       but that is out of 200-300MB for extracting everything, so a
 
146
        #       fairly trivial amount
 
147
        for parent_idx, lines_idx, match_len in matching_blocks:
 
148
            # For lines which match this parent, we will now resolve whether
 
149
            # this parent wins over the current annotation
 
150
            ann_sub = annotations[lines_idx:lines_idx + match_len]
 
151
            par_sub = parent_annotations[parent_idx:parent_idx + match_len]
 
152
            if ann_sub == par_sub:
 
153
                continue
 
154
            for idx in xrange(match_len):
 
155
                ann = ann_sub[idx]
 
156
                par_ann = par_sub[idx]
 
157
                ann_idx = lines_idx + idx
 
158
                if ann == par_ann:
 
159
                    # Nothing to change
 
160
                    continue
 
161
                if ann == this_annotation:
 
162
                    # Originally claimed 'this', but it was really in this
 
163
                    # parent
 
164
                    annotations[ann_idx] = par_ann
 
165
                    continue
 
166
                # Resolve the fact that both sides have a different value for
 
167
                # last modified
 
168
                if ann == last_ann and par_ann == last_parent:
 
169
                    annotations[ann_idx] = last_res
 
170
                else:
 
171
                    new_ann = set(ann)
 
172
                    new_ann.update(par_ann)
 
173
                    new_ann = tuple(sorted(new_ann))
 
174
                    annotations[ann_idx] = new_ann
 
175
                    last_ann = ann
 
176
                    last_parent = par_ann
 
177
                    last_res = new_ann
 
178
 
 
179
    def _record_annotation(self, key, parent_keys, annotations):
 
180
        self._annotations_cache[key] = annotations
 
181
        for parent_key in parent_keys:
 
182
            num = self._num_needed_children[parent_key]
 
183
            num -= 1
 
184
            if num == 0:
 
185
                del self._text_cache[parent_key]
 
186
                del self._annotations_cache[parent_key]
 
187
                # Do we want to clean up _num_needed_children at this point as
 
188
                # well?
 
189
            self._num_needed_children[parent_key] = num
 
190
 
 
191
    def _annotate_one(self, key, text, num_lines):
 
192
        this_annotation = (key,)
 
193
        # Note: annotations will be mutated by calls to _update_from*
 
194
        annotations = [this_annotation] * num_lines
 
195
        parent_keys = self._parent_map[key]
 
196
        if parent_keys:
 
197
            self._update_from_one_parent(key, annotations, text, parent_keys[0])
 
198
            for parent in parent_keys[1:]:
 
199
                self._update_from_other_parents(key, annotations, text,
 
200
                                                this_annotation, parent)
 
201
        self._record_annotation(key, parent_keys, annotations)
 
202
 
 
203
    def annotate(self, key):
 
204
        """Return annotated fulltext for the given key."""
 
205
        keys = self._get_needed_texts(key)
 
206
        pb = ui.ui_factory.nested_progress_bar()
 
207
        try:
 
208
            for text_key, text, num_lines in self._get_needed_texts(key, pb=pb):
 
209
                self._annotate_one(text_key, text, num_lines)
 
210
        finally:
 
211
            pb.finished()
 
212
        try:
 
213
            annotations = self._annotations_cache[key]
 
214
        except KeyError:
 
215
            raise errors.RevisionNotPresent(key, self._vf)
 
216
        return annotations, self._text_cache[key]
 
217
 
 
218
    def _get_heads_provider(self):
 
219
        if self._heads_provider is None:
 
220
            self._heads_provider = _mod_graph.KnownGraph(self._parent_map)
 
221
        return self._heads_provider
 
222
 
 
223
    def annotate_flat(self, key):
 
224
        """Determine the single-best-revision to source for each line.
 
225
 
 
226
        This is meant as a compatibility thunk to how annotate() used to work.
 
227
        """
 
228
        annotations, lines = self.annotate(key)
 
229
        assert len(annotations) == len(lines)
 
230
        out = []
 
231
        heads = self._get_heads_provider().heads
 
232
        append = out.append
 
233
        for annotation, line in zip(annotations, lines):
 
234
            if len(annotation) == 1:
 
235
                append((annotation[0], line))
 
236
            else:
 
237
                the_heads = heads(annotation)
 
238
                if len(the_heads) == 1:
 
239
                    for head in the_heads:
 
240
                        break
 
241
                else:
 
242
                    # We need to resolve the ambiguity, for now just pick the
 
243
                    # sorted smallest
 
244
                    head = sorted(the_heads)[0]
 
245
                append((head, line))
 
246
        return out