← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/versionedfile.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2010-08-11 02:49:26 UTC
  • mfrom: (5374.2.9 2.3-send-mem-614576)
  • Revision ID: pqm@pqm.ubuntu.com-20100811024926-irizklc3vvd9h45p
(jameinel) Decrease peak memory during 'bzr send',
 but releasing texts no longer needed. (John A Meinel)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/versionedfile.py
206
206
            yield record
207
207
 
208
208
 
 
209
class _MPDiffGenerator(object):
 
210
    """Pull out the functionality for generating mp_diffs."""
 
211
 
 
212
    def __init__(self, vf, keys):
 
213
        self.vf = vf
 
214
        # This is the order the keys were requested in
 
215
        self.ordered_keys = tuple(keys)
 
216
        # keys + their parents, what we need to compute the diffs
 
217
        self.needed_keys = ()
 
218
        # Map from key: mp_diff
 
219
        self.diffs = {}
 
220
        # Map from key: parents_needed (may have ghosts)
 
221
        self.parent_map = {}
 
222
        # Parents that aren't present
 
223
        self.ghost_parents = ()
 
224
        # Map from parent_key => number of children for this text
 
225
        self.refcounts = {}
 
226
        # Content chunks that are cached while we still need them
 
227
        self.chunks = {}
 
228
 
 
229
    def _find_needed_keys(self):
 
230
        """Find the set of keys we need to request.
 
231
 
 
232
        This includes all the original keys passed in, and the non-ghost
 
233
        parents of those keys.
 
234
 
 
235
        :return: (needed_keys, refcounts)
 
236
            needed_keys is the set of all texts we need to extract
 
237
            refcounts is a dict of {key: num_children} letting us know when we
 
238
                no longer need to cache a given parent text
 
239
        """
 
240
        # All the keys and their parents
 
241
        needed_keys = set(self.ordered_keys)
 
242
        parent_map = self.vf.get_parent_map(needed_keys)
 
243
        self.parent_map = parent_map
 
244
        # TODO: Should we be using a different construct here? I think this
 
245
        #       uses difference_update internally, and we expect the result to
 
246
        #       be tiny
 
247
        missing_keys = needed_keys.difference(parent_map)
 
248
        if missing_keys:
 
249
            raise errors.RevisionNotPresent(list(missing_keys)[0], self.vf)
 
250
        # Parents that might be missing. They are allowed to be ghosts, but we
 
251
        # should check for them
 
252
        refcounts = {}
 
253
        setdefault = refcounts.setdefault
 
254
        just_parents = set()
 
255
        for child_key, parent_keys in parent_map.iteritems():
 
256
            if not parent_keys:
 
257
                # parent_keys may be None if a given VersionedFile claims to
 
258
                # not support graph operations.
 
259
                continue
 
260
            just_parents.update(parent_keys)
 
261
            needed_keys.update(parent_keys)
 
262
            for p in parent_keys:
 
263
                refcounts[p] = setdefault(p, 0) + 1
 
264
        just_parents.difference_update(parent_map)
 
265
        # Remove any parents that are actually ghosts from the needed set
 
266
        self.present_parents = set(self.vf.get_parent_map(just_parents))
 
267
        self.ghost_parents = just_parents.difference(self.present_parents)
 
268
        needed_keys.difference_update(self.ghost_parents)
 
269
        self.needed_keys = needed_keys
 
270
        self.refcounts = refcounts
 
271
        return needed_keys, refcounts
 
272
 
 
273
    def _compute_diff(self, key, parent_lines, lines):
 
274
        """Compute a single mp_diff, and store it in self._diffs"""
 
275
        if len(parent_lines) > 0:
 
276
            # XXX: _extract_blocks is not usefully defined anywhere...
 
277
            #      It was meant to extract the left-parent diff without
 
278
            #      having to recompute it for Knit content (pack-0.92,
 
279
            #      etc). That seems to have regressed somewhere
 
280
            left_parent_blocks = self.vf._extract_blocks(key,
 
281
                parent_lines[0], lines)
 
282
        else:
 
283
            left_parent_blocks = None
 
284
        diff = multiparent.MultiParent.from_lines(lines,
 
285
                    parent_lines, left_parent_blocks)
 
286
        self.diffs[key] = diff
 
287
 
 
288
    def _process_one_record(self, key, this_chunks):
 
289
        parent_keys = None
 
290
        if key in self.parent_map:
 
291
            # This record should be ready to diff, since we requested
 
292
            # content in 'topological' order
 
293
            parent_keys = self.parent_map.pop(key)
 
294
            # If a VersionedFile claims 'no-graph' support, then it may return
 
295
            # None for any parent request, so we replace it with an empty tuple
 
296
            if parent_keys is None:
 
297
                parent_keys = ()
 
298
            parent_lines = []
 
299
            for p in parent_keys:
 
300
                # Alternatively we could check p not in self.needed_keys, but
 
301
                # ghost_parents should be tiny versus huge
 
302
                if p in self.ghost_parents:
 
303
                    continue
 
304
                refcount = self.refcounts[p]
 
305
                if refcount == 1: # Last child reference
 
306
                    self.refcounts.pop(p)
 
307
                    parent_chunks = self.chunks.pop(p)
 
308
                else:
 
309
                    self.refcounts[p] = refcount - 1
 
310
                    parent_chunks = self.chunks[p]
 
311
                p_lines = osutils.chunks_to_lines(parent_chunks)
 
312
                # TODO: Should we cache the line form? We did the
 
313
                #       computation to get it, but storing it this way will
 
314
                #       be less memory efficient...
 
315
                parent_lines.append(p_lines)
 
316
                del p_lines
 
317
            lines = osutils.chunks_to_lines(this_chunks)
 
318
            # Since we needed the lines, we'll go ahead and cache them this way
 
319
            this_chunks = lines
 
320
            self._compute_diff(key, parent_lines, lines)
 
321
            del lines
 
322
        # Is this content required for any more children?
 
323
        if key in self.refcounts:
 
324
            self.chunks[key] = this_chunks
 
325
 
 
326
    def _extract_diffs(self):
 
327
        needed_keys, refcounts = self._find_needed_keys()
 
328
        for record in self.vf.get_record_stream(needed_keys,
 
329
                                                'topological', True):
 
330
            if record.storage_kind == 'absent':
 
331
                raise errors.RevisionNotPresent(record.key, self.vf)
 
332
            self._process_one_record(record.key,
 
333
                                     record.get_bytes_as('chunked'))
 
334
        
 
335
    def compute_diffs(self):
 
336
        self._extract_diffs()
 
337
        dpop = self.diffs.pop
 
338
        return [dpop(k) for k in self.ordered_keys]
 
339
 
 
340
 
209
341
class VersionedFile(object):
210
342
    """Versioned text file storage.
211
343
 
348
480
 
349
481
    def make_mpdiffs(self, version_ids):
350
482
        """Create multiparent diffs for specified versions."""
 
483
        # XXX: Can't use _MPDiffGenerator just yet. This is because version_ids
 
484
        #      is a list of strings, not keys. And while self.get_record_stream
 
485
        #      is supported, it takes *keys*, while self.get_parent_map() takes
 
486
        #      strings... *sigh*
351
487
        knit_versions = set()
352
488
        knit_versions.update(version_ids)
353
489
        parent_map = self.get_parent_map(version_ids)
1047
1183
 
1048
1184
    def make_mpdiffs(self, keys):
1049
1185
        """Create multiparent diffs for specified keys."""
1050
 
        keys_order = tuple(keys)
1051
 
        keys = frozenset(keys)
1052
 
        knit_keys = set(keys)
1053
 
        parent_map = self.get_parent_map(keys)
1054
 
        for parent_keys in parent_map.itervalues():
1055
 
            if parent_keys:
1056
 
                knit_keys.update(parent_keys)
1057
 
        missing_keys = keys - set(parent_map)
1058
 
        if missing_keys:
1059
 
            raise errors.RevisionNotPresent(list(missing_keys)[0], self)
1060
 
        # We need to filter out ghosts, because we can't diff against them.
1061
 
        maybe_ghosts = knit_keys - keys
1062
 
        ghosts = maybe_ghosts - set(self.get_parent_map(maybe_ghosts))
1063
 
        knit_keys.difference_update(ghosts)
1064
 
        lines = {}
1065
 
        chunks_to_lines = osutils.chunks_to_lines
1066
 
        for record in self.get_record_stream(knit_keys, 'topological', True):
1067
 
            lines[record.key] = chunks_to_lines(record.get_bytes_as('chunked'))
1068
 
            # line_block_dict = {}
1069
 
            # for parent, blocks in record.extract_line_blocks():
1070
 
            #   line_blocks[parent] = blocks
1071
 
            # line_blocks[record.key] = line_block_dict
1072
 
        diffs = []
1073
 
        for key in keys_order:
1074
 
            target = lines[key]
1075
 
            parents = parent_map[key] or []
1076
 
            # Note that filtering knit_keys can lead to a parent difference
1077
 
            # between the creation and the application of the mpdiff.
1078
 
            parent_lines = [lines[p] for p in parents if p in knit_keys]
1079
 
            if len(parent_lines) > 0:
1080
 
                left_parent_blocks = self._extract_blocks(key, parent_lines[0],
1081
 
                    target)
1082
 
            else:
1083
 
                left_parent_blocks = None
1084
 
            diffs.append(multiparent.MultiParent.from_lines(target,
1085
 
                parent_lines, left_parent_blocks))
1086
 
        return diffs
 
1186
        generator = _MPDiffGenerator(self, keys)
 
1187
        return generator.compute_diffs()
1087
1188
 
1088
1189
    def get_annotator(self):
1089
1190
        return annotate.Annotator(self)