← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/knit.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2007-09-06 03:41:24 UTC
  • mfrom: (2794.1.3 knits)
  • Revision ID: pqm@pqm.ubuntu.com-20070906034124-gf4re7orinpud4to
(robertc) Nuke VersionedFile add/get delta support which was never used, and reduce memory copies during commits of unannotated file such as inventory. (Robert Collins).

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/knit.py
133
133
class KnitContent(object):
134
134
    """Content of a knit version to which deltas can be applied."""
135
135
 
136
 
    def __init__(self, lines):
137
 
        self._lines = lines
138
 
 
139
 
    def annotate_iter(self):
140
 
        """Yield tuples of (origin, text) for each content line."""
141
 
        return iter(self._lines)
142
 
 
143
136
    def annotate(self):
144
137
        """Return a list of (origin, text) tuples."""
145
138
        return list(self.annotate_iter())
158
151
    def line_delta(self, new_lines):
159
152
        return list(self.line_delta_iter(new_lines))
160
153
 
161
 
    def text(self):
162
 
        return [text for origin, text in self._lines]
163
 
 
164
 
    def copy(self):
165
 
        return KnitContent(self._lines[:])
166
 
 
167
154
    @staticmethod
168
155
    def get_line_delta_blocks(knit_delta, source, target):
169
156
        """Extract SequenceMatcher.get_matching_blocks() from a knit delta"""
191
178
        yield s_pos + (target_len - t_pos), target_len, 0
192
179
 
193
180
 
194
 
class _KnitFactory(object):
195
 
    """Base factory for creating content objects."""
196
 
 
197
 
    def make(self, lines, version_id):
198
 
        num_lines = len(lines)
199
 
        return KnitContent(zip([version_id] * num_lines, lines))
200
 
 
201
 
 
202
 
class KnitAnnotateFactory(_KnitFactory):
 
181
class AnnotatedKnitContent(KnitContent):
 
182
    """Annotated content."""
 
183
 
 
184
    def __init__(self, lines):
 
185
        self._lines = lines
 
186
 
 
187
    def annotate_iter(self):
 
188
        """Yield tuples of (origin, text) for each content line."""
 
189
        return iter(self._lines)
 
190
 
 
191
    def strip_last_line_newline(self):
 
192
        line = self._lines[-1][1].rstrip('\n')
 
193
        self._lines[-1] = (self._lines[-1][0], line)
 
194
 
 
195
    def text(self):
 
196
        return [text for origin, text in self._lines]
 
197
 
 
198
    def copy(self):
 
199
        return AnnotatedKnitContent(self._lines[:])
 
200
 
 
201
 
 
202
class PlainKnitContent(KnitContent):
 
203
    """Unannotated content.
 
204
    
 
205
    When annotate[_iter] is called on this content, the same version is reported
 
206
    for all lines. Generally, annotate[_iter] is not useful on PlainKnitContent
 
207
    objects.
 
208
    """
 
209
 
 
210
    def __init__(self, lines, version_id):
 
211
        self._lines = lines
 
212
        self._version_id = version_id
 
213
 
 
214
    def annotate_iter(self):
 
215
        """Yield tuples of (origin, text) for each content line."""
 
216
        for line in self._lines:
 
217
            yield self._version_id, line
 
218
 
 
219
    def copy(self):
 
220
        return PlainKnitContent(self._lines[:], self._version_id)
 
221
 
 
222
    def strip_last_line_newline(self):
 
223
        self._lines[-1] = self._lines[-1].rstrip('\n')
 
224
 
 
225
    def text(self):
 
226
        return self._lines
 
227
 
 
228
 
 
229
class KnitAnnotateFactory(object):
203
230
    """Factory for creating annotated Content objects."""
204
231
 
205
232
    annotated = True
206
233
 
 
234
    def make(self, lines, version_id):
 
235
        num_lines = len(lines)
 
236
        return AnnotatedKnitContent(zip([version_id] * num_lines, lines))
 
237
 
207
238
    def parse_fulltext(self, content, version_id):
208
239
        """Convert fulltext to internal representation
209
240
 
217
248
        #       Figure out a way to not require the overhead of turning the
218
249
        #       list back into tuples.
219
250
        lines = [tuple(line.split(' ', 1)) for line in content]
220
 
        return KnitContent(lines)
 
251
        return AnnotatedKnitContent(lines)
221
252
 
222
253
    def parse_line_delta_iter(self, lines):
223
254
        return iter(self.parse_line_delta(lines))
295
326
        return content.annotate_iter()
296
327
 
297
328
 
298
 
class KnitPlainFactory(_KnitFactory):
 
329
class KnitPlainFactory(object):
299
330
    """Factory for creating plain Content objects."""
300
331
 
301
332
    annotated = False
302
333
 
 
334
    def make(self, lines, version_id):
 
335
        return PlainKnitContent(lines, version_id)
 
336
 
303
337
    def parse_fulltext(self, content, version_id):
304
338
        """This parses an unannotated fulltext.
305
339
 
315
349
            header = lines[cur]
316
350
            cur += 1
317
351
            start, end, c = [int(n) for n in header.split(',')]
318
 
            yield start, end, c, zip([version_id] * c, lines[cur:cur+c])
 
352
            yield start, end, c, lines[cur:cur+c]
319
353
            cur += c
320
354
 
321
355
    def parse_line_delta(self, lines, version_id):
346
380
        out = []
347
381
        for start, end, c, lines in delta:
348
382
            out.append('%d,%d,%d\n' % (start, end, c))
349
 
            out.extend([text for origin, text in lines])
 
383
            out.extend(lines)
350
384
        return out
351
385
 
352
386
    def annotate_iter(self, knit, version_id):
452
486
 
453
487
        return fulltext_size > delta_size
454
488
 
455
 
    def _add_delta(self, version_id, parents, delta_parent, sha1, noeol, delta):
456
 
        """See VersionedFile._add_delta()."""
457
 
        self._check_add(version_id, []) # should we check the lines ?
458
 
        self._check_versions_present(parents)
459
 
        present_parents = []
460
 
        ghosts = []
461
 
        parent_texts = {}
462
 
        for parent in parents:
463
 
            if not self.has_version(parent):
464
 
                ghosts.append(parent)
465
 
            else:
466
 
                present_parents.append(parent)
467
 
 
468
 
        if delta_parent is None:
469
 
            # reconstitute as full text.
470
 
            assert len(delta) == 1 or len(delta) == 0
471
 
            if len(delta):
472
 
                assert delta[0][0] == 0
473
 
                assert delta[0][1] == 0, delta[0][1]
474
 
            return super(KnitVersionedFile, self)._add_delta(version_id,
475
 
                                                             parents,
476
 
                                                             delta_parent,
477
 
                                                             sha1,
478
 
                                                             noeol,
479
 
                                                             delta)
480
 
 
481
 
        digest = sha1
482
 
 
483
 
        options = []
484
 
        if noeol:
485
 
            options.append('no-eol')
486
 
 
487
 
        if delta_parent is not None:
488
 
            # determine the current delta chain length.
489
 
            # To speed the extract of texts the delta chain is limited
490
 
            # to a fixed number of deltas.  This should minimize both
491
 
            # I/O and the time spend applying deltas.
492
 
            # The window was changed to a maximum of 200 deltas, but also added
493
 
            # was a check that the total compressed size of the deltas is
494
 
            # smaller than the compressed size of the fulltext.
495
 
            if not self._check_should_delta([delta_parent]):
496
 
                # We don't want a delta here, just do a normal insertion.
497
 
                return super(KnitVersionedFile, self)._add_delta(version_id,
498
 
                                                                 parents,
499
 
                                                                 delta_parent,
500
 
                                                                 sha1,
501
 
                                                                 noeol,
502
 
                                                                 delta)
503
 
 
504
 
        options.append('line-delta')
505
 
        store_lines = self.factory.lower_line_delta(delta)
506
 
 
507
 
        access_memo = self._data.add_record(version_id, digest, store_lines)
508
 
        self._index.add_version(version_id, options, access_memo, parents)
509
 
 
510
489
    def _add_raw_records(self, records, data):
511
490
        """Add all the records 'records' with data pre-joined in 'data'.
512
491
 
641
620
        """Get a delta for constructing version from some other version."""
642
621
        version_id = osutils.safe_revision_id(version_id)
643
622
        self.check_not_reserved_id(version_id)
644
 
        if not self.has_version(version_id):
645
 
            raise RevisionNotPresent(version_id, self.filename)
646
 
        
647
623
        parents = self.get_parents(version_id)
648
624
        if len(parents):
649
625
            parent = parents[0]
841
817
    def _get_content(self, version_id, parent_texts={}):
842
818
        """Returns a content object that makes up the specified
843
819
        version."""
844
 
        if not self.has_version(version_id):
845
 
            raise RevisionNotPresent(version_id, self.filename)
846
 
 
847
820
        cached_version = parent_texts.get(version_id, None)
848
821
        if cached_version is not None:
 
822
            if not self.has_version(version_id):
 
823
                raise RevisionNotPresent(version_id, self.filename)
849
824
            return cached_version
850
825
 
851
826
        text_map, contents_map = self._get_content_maps([version_id])
855
830
        """Check that all specified versions are present."""
856
831
        self._index.check_versions_present(version_ids)
857
832
 
858
 
    def _add_lines_with_ghosts(self, version_id, parents, lines, parent_texts):
 
833
    def _add_lines_with_ghosts(self, version_id, parents, lines, parent_texts,
 
834
        nostore_sha):
859
835
        """See VersionedFile.add_lines_with_ghosts()."""
860
836
        self._check_add(version_id, lines)
861
 
        return self._add(version_id, lines[:], parents, self.delta, parent_texts)
 
837
        return self._add(version_id, lines[:], parents, self.delta,
 
838
            parent_texts, None, nostore_sha)
862
839
 
863
840
    def _add_lines(self, version_id, parents, lines, parent_texts,
864
 
                   left_matching_blocks=None):
 
841
                   left_matching_blocks, nostore_sha):
865
842
        """See VersionedFile.add_lines."""
866
843
        self._check_add(version_id, lines)
867
844
        self._check_versions_present(parents)
868
845
        return self._add(version_id, lines[:], parents, self.delta,
869
 
                         parent_texts, left_matching_blocks)
 
846
            parent_texts, left_matching_blocks, nostore_sha)
870
847
 
871
848
    def _check_add(self, version_id, lines):
872
849
        """check that version_id and lines are safe to add."""
875
852
        if contains_whitespace(version_id):
876
853
            raise InvalidRevisionId(version_id, self.filename)
877
854
        self.check_not_reserved_id(version_id)
 
855
        # Technically this is a case of Look Before You Leap, but:
 
856
        # - for knits this saves wasted space in the error case
 
857
        # - for packs this avoids dead space in the pack
 
858
        # - it also avoids undetected poisoning attacks.
 
859
        # - its 1.5% of total commit time, so ignore it unless it becomes a
 
860
        #   larger percentage.
878
861
        if self.has_version(version_id):
879
862
            raise RevisionAlreadyPresent(version_id, self.filename)
880
863
        self._check_lines_not_unicode(lines)
881
864
        self._check_lines_are_lines(lines)
882
865
 
883
866
    def _add(self, version_id, lines, parents, delta, parent_texts,
884
 
             left_matching_blocks=None):
 
867
             left_matching_blocks, nostore_sha):
885
868
        """Add a set of lines on top of version specified by parents.
886
869
 
887
870
        If delta is true, compress the text as a line-delta against
915
898
            delta = False
916
899
 
917
900
        digest = sha_strings(lines)
 
901
        if nostore_sha == digest:
 
902
            raise errors.ExistingContent
918
903
        text_length = sum(map(len, lines))
919
904
        options = []
920
905
        if lines:
929
914
            delta = self._check_should_delta(present_parents)
930
915
 
931
916
        assert isinstance(version_id, str)
932
 
        lines = self.factory.make(lines, version_id)
 
917
        content = self.factory.make(lines, version_id)
933
918
        if delta or (self.factory.annotated and len(present_parents) > 0):
934
919
            # Merge annotations from parent texts if so is needed.
935
 
            delta_hunks = self._merge_annotations(lines, present_parents,
 
920
            delta_hunks = self._merge_annotations(content, present_parents,
936
921
                parent_texts, delta, self.factory.annotated,
937
922
                left_matching_blocks)
938
923
 
941
926
            store_lines = self.factory.lower_line_delta(delta_hunks)
942
927
        else:
943
928
            options.append('fulltext')
944
 
            store_lines = self.factory.lower_fulltext(lines)
 
929
            store_lines = self.factory.lower_fulltext(content)
945
930
 
946
931
        access_memo = self._data.add_record(version_id, digest, store_lines)
947
932
        self._index.add_version(version_id, options, access_memo, parents)
948
 
        return digest, text_length, lines
 
933
        return digest, text_length, content
949
934
 
950
935
    def check(self, progress_bar=None):
951
936
        """See VersionedFile.check()."""
1035
1020
                    elif method == 'line-delta':
1036
1021
                        delta = self.factory.parse_line_delta(data, version_id)
1037
1022
                        content = content.copy()
1038
 
                        content._lines = self._apply_delta(content._lines, 
 
1023
                        content._lines = self._apply_delta(content._lines,
1039
1024
                                                           delta)
1040
1025
                    content_map[component_id] = content
1041
1026
 
1042
1027
            if 'no-eol' in self._index.get_options(version_id):
1043
1028
                content = content.copy()
1044
 
                line = content._lines[-1][1].rstrip('\n')
1045
 
                content._lines[-1] = (content._lines[-1][0], line)
 
1029
                content.strip_last_line_newline()
1046
1030
            final_content[version_id] = content
1047
1031
 
1048
1032
            # digest here is the digest from the last applied component.
1049
1033
            text = content.text()
1050
1034
            if sha_strings(text) != digest:
1051
 
                raise KnitCorrupt(self.filename, 
 
1035
                raise KnitCorrupt(self.filename,
1052
1036
                                  'sha-1 does not match %s' % version_id)
1053
1037
 
1054
 
            text_map[version_id] = text 
1055
 
        return text_map, final_content 
 
1038
            text_map[version_id] = text
 
1039
        return text_map, final_content
1056
1040
 
1057
1041
    def iter_lines_added_or_present_in_versions(self, version_ids=None, 
1058
1042
                                                pb=None):