~bzr-pqm/bzr/bzr.dev

0.1.1 by Martin Pool
Check in old existing knit code.
1
#! /usr/bin/python
2
3
# Copyright (C) 2005 Canonical Ltd
4
0.1.33 by Martin Pool
add gpl text
5
# This program is free software; you can redistribute it and/or modify
6
# it under the terms of the GNU General Public License as published by
7
# the Free Software Foundation; either version 2 of the License, or
8
# (at your option) any later version.
9
10
# This program is distributed in the hope that it will be useful,
11
# but WITHOUT ANY WARRANTY; without even the implied warranty of
12
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13
# GNU General Public License for more details.
14
15
# You should have received a copy of the GNU General Public License
16
# along with this program; if not, write to the Free Software
17
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
0.1.1 by Martin Pool
Check in old existing knit code.
18
19
# Author: Martin Pool <mbp@canonical.com>
20
21
0.1.38 by Martin Pool
Rename knit to weave. (I don't think there's an existing module called weave.)
22
"""Weave - storage of related text file versions"""
0.1.2 by Martin Pool
Import testsweet module adapted from bzr.
23
928 by Martin Pool
- go back to using plain builtin set()
24
# before intset (r923) 2000 versions in 41.5s
25
# with intset (r926) 2000 versions in 93s !!!
26
# better to just use plain sets.
27
931 by Martin Pool
- experiment with making Weave._extract() return a list, not a generator - slightly faster
28
# making _extract build and return a list, rather than being a generator
29
# takes 37.94s
30
0.1.61 by Martin Pool
doc
31
# TODO: Perhaps have copy method for Weave instances?
0.1.2 by Martin Pool
Import testsweet module adapted from bzr.
32
0.1.58 by Martin Pool
doc
33
# XXX: If we do weaves this way, will a merge still behave the same
34
# way if it's done in a different order?  That's a pretty desirable
35
# property.
36
0.1.62 by Martin Pool
Lame command-line client for reading and writing weaves.
37
# TODO: Nothing here so far assumes the lines are really \n newlines,
38
# rather than being split up in some other way.  We could accomodate
39
# binaries, perhaps by naively splitting on \n or perhaps using
40
# something like a rolling checksum.
41
42
# TODO: Track version names as well as indexes. 
43
0.1.85 by Martin Pool
doc
44
# TODO: End marker for each version so we can stop reading?
0.1.69 by Martin Pool
Simple text-based format for storing weaves, cleaner than
45
46
# TODO: Check that no insertion occurs inside a deletion that was
47
# active in the version of the insertion.
48
912 by Martin Pool
- update todos for weave
49
# TODO: In addition to the SHA-1 check, perhaps have some code that
50
# checks structural constraints of the weave: ie that insertions are
51
# properly nested, that there is no text outside of an insertion, that
52
# insertions or deletions are not repeated, etc.
0.1.85 by Martin Pool
doc
53
918 by Martin Pool
- start doing new weave-merge algorithm
54
# TODO: Make the info command just show info, not extract everything:
55
# it can be much faster.
56
57
# TODO: Perhaps use long integers as sets instead of set objects; may
58
# be faster.
59
60
# TODO: Parallel-extract that passes back each line along with a
61
# description of which revisions include it.  Nice for checking all
62
# shas in parallel.
63
64
0.1.85 by Martin Pool
doc
65
924 by Martin Pool
- Add IntSet class
66
0.1.47 by Martin Pool
New WeaveError and WeaveFormatError rather than assertions.
67
class WeaveError(Exception):
68
    """Exception in processing weave"""
69
70
71
class WeaveFormatError(WeaveError):
72
    """Weave invariant violated"""
73
    
74
0.1.38 by Martin Pool
Rename knit to weave. (I don't think there's an existing module called weave.)
75
class Weave(object):
76
    """weave - versioned text file storage.
0.1.2 by Martin Pool
Import testsweet module adapted from bzr.
77
    
0.1.72 by Martin Pool
Go back to weave lines normally having newlines at the end.
78
    A Weave manages versions of line-based text files, keeping track
79
    of the originating version for each line.
80
81
    To clients the "lines" of the file are represented as a list of strings.
82
    These strings  will typically have terminal newline characters, but
83
    this is not required.  In particular files commonly do not have a newline
84
    at the end of the file.
0.1.2 by Martin Pool
Import testsweet module adapted from bzr.
85
0.1.4 by Martin Pool
Start indexing knits by both integer and version string.
86
    Texts can be identified in either of two ways:
87
88
    * a nonnegative index number.
89
90
    * a version-id string.
91
0.1.38 by Martin Pool
Rename knit to weave. (I don't think there's an existing module called weave.)
92
    Typically the index number will be valid only inside this weave and
0.1.4 by Martin Pool
Start indexing knits by both integer and version string.
93
    the version-id is used to reference it in the larger world.
0.1.2 by Martin Pool
Import testsweet module adapted from bzr.
94
0.1.39 by Martin Pool
Change to a more realistic weave structure which can represent insertions and
95
    The weave is represented as a list mixing edit instructions and
96
    literal text.  Each entry in _l can be either a string (or
97
    unicode), or a tuple.  If a string, it means that the given line
98
    should be output in the currently active revisions.
99
100
    If a tuple, it gives a processing instruction saying in which
101
    revisions the enclosed lines are active.  The tuple has the form
102
    (instruction, version).
103
104
    The instruction can be '{' or '}' for an insertion block, and '['
105
    and ']' for a deletion block respectively.  The version is the
0.1.45 by Martin Pool
doc
106
    integer version index.  There is no replace operator, only deletes
107
    and inserts.
0.1.39 by Martin Pool
Change to a more realistic weave structure which can represent insertions and
108
0.1.41 by Martin Pool
Doc
109
    Constraints/notes:
0.1.39 by Martin Pool
Change to a more realistic weave structure which can represent insertions and
110
111
    * A later version can delete lines that were introduced by any
112
      number of ancestor versions; this implies that deletion
113
      instructions can span insertion blocks without regard to the
114
      insertion block's nesting.
115
0.1.41 by Martin Pool
Doc
116
    * Similarly, deletions need not be properly nested with regard to
117
      each other, because they might have been generated by
118
      independent revisions.
119
0.1.45 by Martin Pool
doc
120
    * Insertions are always made by inserting a new bracketed block
121
      into a single point in the previous weave.  This implies they
122
      can nest but not overlap, and the nesting must always have later
123
      insertions on the inside.
124
0.1.41 by Martin Pool
Doc
125
    * It doesn't seem very useful to have an active insertion
126
      inside an inactive insertion, but it might happen.
0.1.45 by Martin Pool
doc
127
      
0.1.41 by Martin Pool
Doc
128
    * Therefore, all instructions are always"considered"; that
129
      is passed onto and off the stack.  An outer inactive block
130
      doesn't disable an inner block.
131
132
    * Lines are enabled if the most recent enclosing insertion is
133
      active and none of the enclosing deletions are active.
0.1.39 by Martin Pool
Change to a more realistic weave structure which can represent insertions and
134
0.1.49 by Martin Pool
Add another constraint: revisions should not delete text that they
135
    * There is no point having a deletion directly inside its own
136
      insertion; you might as well just not write it.  And there
137
      should be no way to get an earlier version deleting a later
138
      version.
139
0.1.2 by Martin Pool
Import testsweet module adapted from bzr.
140
    _l
892 by Martin Pool
- weave stores only direct parents, and calculates and memoizes expansion as needed
141
        Text of the weave.
0.1.4 by Martin Pool
Start indexing knits by both integer and version string.
142
143
    _v
892 by Martin Pool
- weave stores only direct parents, and calculates and memoizes expansion as needed
144
        List of parents, indexed by version number.
145
        It is only necessary to store the minimal set of parents for
146
        each version; the parent's parents are implied.
0.1.13 by Martin Pool
Knit structure now allows for versions to include the lines present in other
147
0.1.89 by Martin Pool
Store SHA1 in weave file for later verification
148
    _sha1s
149
        List of hex SHA-1 of each version, or None if not recorded.
0.1.2 by Martin Pool
Import testsweet module adapted from bzr.
150
    """
0.1.4 by Martin Pool
Start indexing knits by both integer and version string.
151
    def __init__(self):
152
        self._l = []
153
        self._v = []
0.1.89 by Martin Pool
Store SHA1 in weave file for later verification
154
        self._sha1s = []
0.1.60 by Martin Pool
Weave eq and ne methods
155
156
157
    def __eq__(self, other):
158
        if not isinstance(other, Weave):
159
            return False
160
        return self._v == other._v \
161
               and self._l == other._l
162
    
163
164
    def __ne__(self, other):
165
        return not self.__eq__(other)
166
0.1.2 by Martin Pool
Import testsweet module adapted from bzr.
167
        
0.1.26 by Martin Pool
Refactor parameters to add command
168
    def add(self, parents, text):
0.1.4 by Martin Pool
Start indexing knits by both integer and version string.
169
        """Add a single text on top of the weave.
0.1.36 by Martin Pool
doc
170
  
0.1.26 by Martin Pool
Refactor parameters to add command
171
        Returns the index number of the newly added version.
172
173
        parents
892 by Martin Pool
- weave stores only direct parents, and calculates and memoizes expansion as needed
174
            List or set of direct parent version numbers.
175
            
0.1.26 by Martin Pool
Refactor parameters to add command
176
        text
177
            Sequence of lines to be added in the new version."""
0.1.82 by Martin Pool
Small weave optimizations
178
        ## self._check_versions(parents)
179
        ## self._check_lines(text)
0.1.4 by Martin Pool
Start indexing knits by both integer and version string.
180
        idx = len(self._v)
0.1.5 by Martin Pool
Add test for storing two text versions.
181
0.1.89 by Martin Pool
Store SHA1 in weave file for later verification
182
        import sha
183
        s = sha.new()
184
        for l in text:
185
            s.update(l)
186
        sha1 = s.hexdigest()
187
        del s
188
918 by Martin Pool
- start doing new weave-merge algorithm
189
        # TODO: It'd probably be faster to append things on to a new
190
        # list rather than modifying the existing one, which is likely
191
        # to cause a lot of copying.
192
0.1.26 by Martin Pool
Refactor parameters to add command
193
        if parents:
892 by Martin Pool
- weave stores only direct parents, and calculates and memoizes expansion as needed
194
            ancestors = self.inclusions(parents)
195
            delta = self._delta(ancestors, text)
0.1.25 by Martin Pool
Handle insertion of new weave layers that insert text on top of the basis
196
0.1.31 by Martin Pool
Fix insertion of multiple regions, calculating the right line offset as we go.
197
            # offset gives the number of lines that have been inserted
198
            # into the weave up to the current point; if the original edit instruction
199
            # says to change line A then we actually change (A+offset)
200
            offset = 0
201
0.1.25 by Martin Pool
Handle insertion of new weave layers that insert text on top of the basis
202
            for i1, i2, newlines in delta:
0.1.29 by Martin Pool
Better internal error
203
                assert 0 <= i1
204
                assert i1 <= i2
205
                assert i2 <= len(self._l)
0.1.56 by Martin Pool
Handle deletion of lines by marking the region with a deletion
206
207
                # the deletion and insertion are handled separately.
208
                # first delete the region.
0.1.25 by Martin Pool
Handle insertion of new weave layers that insert text on top of the basis
209
                if i1 != i2:
0.1.56 by Martin Pool
Handle deletion of lines by marking the region with a deletion
210
                    self._l.insert(i1+offset, ('[', idx))
211
                    self._l.insert(i2+offset+1, (']', idx))
212
                    offset += 2
213
                    # is this OK???
0.1.39 by Martin Pool
Change to a more realistic weave structure which can represent insertions and
214
0.1.56 by Martin Pool
Handle deletion of lines by marking the region with a deletion
215
                if newlines:
0.1.57 by Martin Pool
Fix bug in an update edit that both deletes and inserts -- previously
216
                    # there may have been a deletion spanning up to
217
                    # i2; we want to insert after this region to make sure
218
                    # we don't destroy ourselves
219
                    i = i2 + offset
0.1.56 by Martin Pool
Handle deletion of lines by marking the region with a deletion
220
                    self._l[i:i] = [('{', idx)] \
221
                                   + newlines \
222
                                   + [('}', idx)]
223
                    offset += 2 + len(newlines)
0.1.25 by Martin Pool
Handle insertion of new weave layers that insert text on top of the basis
224
0.1.75 by Martin Pool
Remove VerInfo class; just store sets directly in the list of
225
            self._addversion(parents)
0.1.25 by Martin Pool
Handle insertion of new weave layers that insert text on top of the basis
226
        else:
0.1.26 by Martin Pool
Refactor parameters to add command
227
            # special case; adding with no parents revision; can do this
0.1.25 by Martin Pool
Handle insertion of new weave layers that insert text on top of the basis
228
            # more quickly by just appending unconditionally
0.1.39 by Martin Pool
Change to a more realistic weave structure which can represent insertions and
229
            self._l.append(('{', idx))
230
            self._l += text
231
            self._l.append(('}', idx))
0.1.25 by Martin Pool
Handle insertion of new weave layers that insert text on top of the basis
232
0.1.75 by Martin Pool
Remove VerInfo class; just store sets directly in the list of
233
            self._addversion(None)
0.1.89 by Martin Pool
Store SHA1 in weave file for later verification
234
235
        self._sha1s.append(sha1)
0.1.25 by Martin Pool
Handle insertion of new weave layers that insert text on top of the basis
236
            
0.1.4 by Martin Pool
Start indexing knits by both integer and version string.
237
        return idx
0.1.2 by Martin Pool
Import testsweet module adapted from bzr.
238
0.1.27 by Martin Pool
Check that version numbers passed in are reasonable
239
0.1.78 by Martin Pool
Rename Weave.get_included to inclusions and getiter to get_iter
240
    def inclusions(self, versions):
893 by Martin Pool
- Refactor weave calculation of inclusions
241
        """Return set of all ancestors of given version(s)."""
928 by Martin Pool
- go back to using plain builtin set()
242
        i = set(versions)
893 by Martin Pool
- Refactor weave calculation of inclusions
243
        v = max(versions)
892 by Martin Pool
- weave stores only direct parents, and calculates and memoizes expansion as needed
244
        try:
893 by Martin Pool
- Refactor weave calculation of inclusions
245
            while v >= 0:
246
                if v in i:
247
                    # include all its parents
248
                    i.update(self._v[v])
249
                v -= 1
250
            return i
892 by Martin Pool
- weave stores only direct parents, and calculates and memoizes expansion as needed
251
        except IndexError:
252
            raise ValueError("version %d not present in weave" % v)
0.1.77 by Martin Pool
New Weave.get_included() does transitive expansion
253
254
890 by Martin Pool
- weave info should show minimal expression of parents
255
    def minimal_parents(self, version):
256
        """Find the minimal set of parents for the version."""
257
        included = self._v[version]
258
        if not included:
259
            return []
260
        
261
        li = list(included)
893 by Martin Pool
- Refactor weave calculation of inclusions
262
        li.sort(reverse=True)
890 by Martin Pool
- weave info should show minimal expression of parents
263
264
        mininc = []
928 by Martin Pool
- go back to using plain builtin set()
265
        gotit = set()
890 by Martin Pool
- weave info should show minimal expression of parents
266
267
        for pv in li:
268
            if pv not in gotit:
269
                mininc.append(pv)
893 by Martin Pool
- Refactor weave calculation of inclusions
270
                gotit.update(self.inclusions(pv))
890 by Martin Pool
- weave info should show minimal expression of parents
271
272
        assert mininc[0] >= 0
273
        assert mininc[-1] < version
274
        return mininc
275
276
0.1.75 by Martin Pool
Remove VerInfo class; just store sets directly in the list of
277
    def _addversion(self, parents):
278
        if parents:
892 by Martin Pool
- weave stores only direct parents, and calculates and memoizes expansion as needed
279
            self._v.append(parents)
0.1.75 by Martin Pool
Remove VerInfo class; just store sets directly in the list of
280
        else:
928 by Martin Pool
- go back to using plain builtin set()
281
            self._v.append(set())
0.1.75 by Martin Pool
Remove VerInfo class; just store sets directly in the list of
282
283
0.1.39 by Martin Pool
Change to a more realistic weave structure which can represent insertions and
284
    def _check_lines(self, text):
285
        if not isinstance(text, list):
286
            raise ValueError("text should be a list, not %s" % type(text))
287
288
        for l in text:
289
            if not isinstance(l, basestring):
869 by Martin Pool
- more weave.py command line options
290
                raise ValueError("text line should be a string or unicode, not %s"
291
                                 % type(l))
0.1.39 by Martin Pool
Change to a more realistic weave structure which can represent insertions and
292
        
293
294
0.1.27 by Martin Pool
Check that version numbers passed in are reasonable
295
    def _check_versions(self, indexes):
296
        """Check everything in the sequence of indexes is valid"""
297
        for i in indexes:
298
            try:
299
                self._v[i]
300
            except IndexError:
301
                raise IndexError("invalid version number %r" % i)
302
0.1.2 by Martin Pool
Import testsweet module adapted from bzr.
303
    
0.1.7 by Martin Pool
Add trivial annotate text
304
    def annotate(self, index):
305
        return list(self.annotate_iter(index))
306
307
0.1.78 by Martin Pool
Rename Weave.get_included to inclusions and getiter to get_iter
308
    def annotate_iter(self, version):
0.1.7 by Martin Pool
Add trivial annotate text
309
        """Yield list of (index-id, line) pairs for the specified version.
310
311
        The index indicates when the line originated in the weave."""
893 by Martin Pool
- Refactor weave calculation of inclusions
312
        for origin, lineno, text in self._extract([version]):
0.1.39 by Martin Pool
Change to a more realistic weave structure which can represent insertions and
313
            yield origin, text
0.1.22 by Martin Pool
Calculate delta for new versions relative to a set of parent versions.
314
315
918 by Martin Pool
- start doing new weave-merge algorithm
316
    def _walk(self):
317
        """Walk the weave.
318
319
        Yields sequence of
320
        (lineno, insert, deletes, text)
321
        for each literal line.
322
        """
323
        
324
        istack = []
928 by Martin Pool
- go back to using plain builtin set()
325
        dset = set()
918 by Martin Pool
- start doing new weave-merge algorithm
326
327
        lineno = 0         # line of weave, 0-based
328
329
        for l in self._l:
330
            if isinstance(l, tuple):
331
                c, v = l
332
                isactive = None
333
                if c == '{':
334
                    istack.append(v)
335
                elif c == '}':
336
                    oldv = istack.pop()
337
                elif c == '[':
926 by Martin Pool
- update more weave code to use intsets
338
                    assert v not in dset
339
                    dset.add(v)
918 by Martin Pool
- start doing new weave-merge algorithm
340
                elif c == ']':
926 by Martin Pool
- update more weave code to use intsets
341
                    dset.remove(v)
918 by Martin Pool
- start doing new weave-merge algorithm
342
                else:
343
                    raise WeaveFormatError('unexpected instruction %r'
344
                                           % v)
345
            else:
346
                assert isinstance(l, basestring)
347
                assert istack
348
                yield lineno, istack[-1], dset, l
349
            lineno += 1
350
351
352
893 by Martin Pool
- Refactor weave calculation of inclusions
353
    def _extract(self, versions):
0.1.20 by Martin Pool
Factor out Knit.extract() method
354
        """Yield annotation of lines in included set.
355
0.1.39 by Martin Pool
Change to a more realistic weave structure which can represent insertions and
356
        Yields a sequence of tuples (origin, lineno, text), where
357
        origin is the origin version, lineno the index in the weave,
358
        and text the text of the line.
359
0.1.20 by Martin Pool
Factor out Knit.extract() method
360
        The set typically but not necessarily corresponds to a version.
361
        """
893 by Martin Pool
- Refactor weave calculation of inclusions
362
        included = self.inclusions(versions)
881 by Martin Pool
- faster weave extraction
363
364
        istack = []
928 by Martin Pool
- go back to using plain builtin set()
365
        dset = set()
0.1.48 by Martin Pool
Basic parsing of delete instructions.
366
367
        lineno = 0         # line of weave, 0-based
891 by Martin Pool
- fix up refactoring of weave
368
894 by Martin Pool
- small optimization for weave extract
369
        isactive = None
0.1.85 by Martin Pool
doc
370
931 by Martin Pool
- experiment with making Weave._extract() return a list, not a generator - slightly faster
371
        result = []
372
0.1.63 by Martin Pool
Abbreviate WeaveFormatError in some code
373
        WFE = WeaveFormatError
0.1.95 by Martin Pool
- preliminary merge conflict detection
374
0.1.39 by Martin Pool
Change to a more realistic weave structure which can represent insertions and
375
        for l in self._l:
376
            if isinstance(l, tuple):
377
                c, v = l
894 by Martin Pool
- small optimization for weave extract
378
                isactive = None
891 by Martin Pool
- fix up refactoring of weave
379
                if c == '{':
380
                    assert v not in istack
381
                    istack.append(v)
382
                elif c == '}':
383
                    oldv = istack.pop()
384
                    assert oldv == v
385
                elif c == '[':
386
                    if v in included:
881 by Martin Pool
- faster weave extraction
387
                        assert v not in dset
0.1.48 by Martin Pool
Basic parsing of delete instructions.
388
                        dset.add(v)
891 by Martin Pool
- fix up refactoring of weave
389
                else:
390
                    assert c == ']'
391
                    if v in included:
881 by Martin Pool
- faster weave extraction
392
                        assert v in dset
0.1.48 by Martin Pool
Basic parsing of delete instructions.
393
                        dset.remove(v)
0.1.39 by Martin Pool
Change to a more realistic weave structure which can represent insertions and
394
            else:
395
                assert isinstance(l, basestring)
894 by Martin Pool
- small optimization for weave extract
396
                if isactive is None:
397
                    isactive = (not dset) and istack and (istack[-1] in included)
0.1.39 by Martin Pool
Change to a more realistic weave structure which can represent insertions and
398
                if isactive:
931 by Martin Pool
- experiment with making Weave._extract() return a list, not a generator - slightly faster
399
                    result.append((istack[-1], lineno, l))
0.1.39 by Martin Pool
Change to a more realistic weave structure which can represent insertions and
400
            lineno += 1
0.1.7 by Martin Pool
Add trivial annotate text
401
0.1.46 by Martin Pool
More constraints on structure of weave, and checks that they work
402
        if istack:
0.1.63 by Martin Pool
Abbreviate WeaveFormatError in some code
403
            raise WFE("unclosed insertion blocks at end of weave",
0.1.47 by Martin Pool
New WeaveError and WeaveFormatError rather than assertions.
404
                                   istack)
0.1.48 by Martin Pool
Basic parsing of delete instructions.
405
        if dset:
0.1.63 by Martin Pool
Abbreviate WeaveFormatError in some code
406
            raise WFE("unclosed deletion blocks at end of weave",
0.1.48 by Martin Pool
Basic parsing of delete instructions.
407
                                   dset)
0.1.40 by Martin Pool
Add test for extracting from weave with nested insertions
408
931 by Martin Pool
- experiment with making Weave._extract() return a list, not a generator - slightly faster
409
        return result
410
    
411
0.1.7 by Martin Pool
Add trivial annotate text
412
0.1.78 by Martin Pool
Rename Weave.get_included to inclusions and getiter to get_iter
413
    def get_iter(self, version):
0.1.5 by Martin Pool
Add test for storing two text versions.
414
        """Yield lines for the specified version."""
893 by Martin Pool
- Refactor weave calculation of inclusions
415
        for origin, lineno, line in self._extract([version]):
0.1.8 by Martin Pool
Unify get/annotate code
416
            yield line
0.1.5 by Martin Pool
Add test for storing two text versions.
417
418
0.1.4 by Martin Pool
Start indexing knits by both integer and version string.
419
    def get(self, index):
0.1.78 by Martin Pool
Rename Weave.get_included to inclusions and getiter to get_iter
420
        return list(self.get_iter(index))
0.1.1 by Martin Pool
Check in old existing knit code.
421
422
0.1.95 by Martin Pool
- preliminary merge conflict detection
423
    def mash_iter(self, included):
0.1.65 by Martin Pool
Add Weave.merge_iter to get automerged lines
424
        """Return composed version of multiple included versions."""
893 by Martin Pool
- Refactor weave calculation of inclusions
425
        for origin, lineno, text in self._extract(included):
0.1.65 by Martin Pool
Add Weave.merge_iter to get automerged lines
426
            yield text
427
428
0.1.11 by Martin Pool
Add Knit.dump method
429
    def dump(self, to_file):
430
        from pprint import pprint
0.1.38 by Martin Pool
Rename knit to weave. (I don't think there's an existing module called weave.)
431
        print >>to_file, "Weave._l = ",
0.1.11 by Martin Pool
Add Knit.dump method
432
        pprint(self._l, to_file)
0.1.38 by Martin Pool
Rename knit to weave. (I don't think there's an existing module called weave.)
433
        print >>to_file, "Weave._v = ",
0.1.18 by Martin Pool
Better Knit.dump method
434
        pprint(self._v, to_file)
0.1.11 by Martin Pool
Add Knit.dump method
435
436
0.1.91 by Martin Pool
Update Weave.check
437
438
    def numversions(self):
439
        l = len(self._v)
440
        assert l == len(self._sha1s)
441
        return l
442
443
894 by Martin Pool
- small optimization for weave extract
444
    def check(self, progress_bar=None):
0.1.91 by Martin Pool
Update Weave.check
445
        # check no circular inclusions
446
        for version in range(self.numversions()):
447
            inclusions = list(self._v[version])
448
            if inclusions:
449
                inclusions.sort()
450
                if inclusions[-1] >= version:
0.1.47 by Martin Pool
New WeaveError and WeaveFormatError rather than assertions.
451
                    raise WeaveFormatError("invalid included version %d for index %d"
0.1.91 by Martin Pool
Update Weave.check
452
                                           % (inclusions[-1], version))
453
454
        # try extracting all versions; this is a bit slow and parallel
455
        # extraction could be used
456
        import sha
894 by Martin Pool
- small optimization for weave extract
457
        nv = self.numversions()
458
        for version in range(nv):
459
            if progress_bar:
460
                progress_bar.update('checking text', version, nv)
0.1.91 by Martin Pool
Update Weave.check
461
            s = sha.new()
462
            for l in self.get_iter(version):
463
                s.update(l)
464
            hd = s.hexdigest()
465
            expected = self._sha1s[version]
466
            if hd != expected:
467
                raise WeaveError("mismatched sha1 for version %d; "
468
                                 "got %s, expected %s"
469
                                 % (version, hd, expected))
0.1.18 by Martin Pool
Better Knit.dump method
470
881 by Martin Pool
- faster weave extraction
471
        # TODO: check insertions are properly nested, that there are
472
        # no lines outside of insertion blocks, that deletions are
473
        # properly paired, etc.
474
0.1.13 by Martin Pool
Knit structure now allows for versions to include the lines present in other
475
476
0.1.95 by Martin Pool
- preliminary merge conflict detection
477
    def merge(self, merge_versions):
478
        """Automerge and mark conflicts between versions.
479
480
        This returns a sequence, each entry describing alternatives
481
        for a chunk of the file.  Each of the alternatives is given as
482
        a list of lines.
483
484
        If there is a chunk of the file where there's no diagreement,
485
        only one alternative is given.
486
        """
487
488
        # approach: find the included versions common to all the
489
        # merged versions
490
        raise NotImplementedError()
491
492
493
0.1.21 by Martin Pool
Start computing a delta to insert a new revision
494
    def _delta(self, included, lines):
495
        """Return changes from basis to new revision.
496
497
        The old text for comparison is the union of included revisions.
498
499
        This is used in inserting a new text.
0.1.22 by Martin Pool
Calculate delta for new versions relative to a set of parent versions.
500
0.1.55 by Martin Pool
doc
501
        Delta is returned as a sequence of
502
        (weave1, weave2, newlines).
503
504
        This indicates that weave1:weave2 of the old weave should be
0.1.22 by Martin Pool
Calculate delta for new versions relative to a set of parent versions.
505
        replaced by the sequence of lines in newlines.  Note that
506
        these line numbers are positions in the total weave and don't
507
        correspond to the lines in any extracted version, or even the
508
        extracted union of included versions.
509
510
        If line1=line2, this is a pure insert; if newlines=[] this is a
511
        pure delete.  (Similar to difflib.)
0.1.21 by Martin Pool
Start computing a delta to insert a new revision
512
        """
0.1.54 by Martin Pool
Fix weave line calculation when making deltas
513
        # basis a list of (origin, lineno, line)
0.1.84 by Martin Pool
Refactor Weave._delta to calculate less unused information
514
        basis_lineno = []
0.1.83 by Martin Pool
Better delta basis calculation
515
        basis_lines = []
893 by Martin Pool
- Refactor weave calculation of inclusions
516
        for origin, lineno, line in self._extract(included):
0.1.84 by Martin Pool
Refactor Weave._delta to calculate less unused information
517
            basis_lineno.append(lineno)
518
            basis_lines.append(line)
0.1.22 by Martin Pool
Calculate delta for new versions relative to a set of parent versions.
519
520
        # add a sentinal, because we can also match against the final line
0.1.84 by Martin Pool
Refactor Weave._delta to calculate less unused information
521
        basis_lineno.append(len(self._l))
0.1.22 by Martin Pool
Calculate delta for new versions relative to a set of parent versions.
522
0.1.63 by Martin Pool
Abbreviate WeaveFormatError in some code
523
        # XXX: which line of the weave should we really consider
524
        # matches the end of the file?  the current code says it's the
525
        # last line of the weave?
0.1.22 by Martin Pool
Calculate delta for new versions relative to a set of parent versions.
526
527
        from difflib import SequenceMatcher
528
        s = SequenceMatcher(None, basis_lines, lines)
529
0.1.55 by Martin Pool
doc
530
        # TODO: Perhaps return line numbers from composed weave as well?
531
0.1.22 by Martin Pool
Calculate delta for new versions relative to a set of parent versions.
532
        for tag, i1, i2, j1, j2 in s.get_opcodes():
0.1.23 by Martin Pool
tidy up
533
            ##print tag, i1, i2, j1, j2
0.1.22 by Martin Pool
Calculate delta for new versions relative to a set of parent versions.
534
535
            if tag == 'equal':
536
                continue
537
538
            # i1,i2 are given in offsets within basis_lines; we need to map them
539
            # back to offsets within the entire weave
0.1.84 by Martin Pool
Refactor Weave._delta to calculate less unused information
540
            real_i1 = basis_lineno[i1]
541
            real_i2 = basis_lineno[i2]
0.1.22 by Martin Pool
Calculate delta for new versions relative to a set of parent versions.
542
0.1.35 by Martin Pool
Clean up Knit._delta method
543
            assert 0 <= j1
544
            assert j1 <= j2
545
            assert j2 <= len(lines)
0.1.22 by Martin Pool
Calculate delta for new versions relative to a set of parent versions.
546
0.1.35 by Martin Pool
Clean up Knit._delta method
547
            yield real_i1, real_i2, lines[j1:j2]
0.1.21 by Martin Pool
Start computing a delta to insert a new revision
548
0.1.1 by Martin Pool
Check in old existing knit code.
549
918 by Martin Pool
- start doing new weave-merge algorithm
550
            
551
    def plan_merge(self, ver_a, ver_b):
552
        """Return pseudo-annotation indicating how the two versions merge.
553
554
        This is computed between versions a and b and their common
555
        base.
556
557
        Weave lines present in none of them are skipped entirely.
558
        """
926 by Martin Pool
- update more weave code to use intsets
559
        inc_a = self.inclusions([ver_a])
560
        inc_b = self.inclusions([ver_b])
918 by Martin Pool
- start doing new weave-merge algorithm
561
        inc_c = inc_a & inc_b
562
563
        for lineno, insert, deleteset, line in self._walk():
564
            if deleteset & inc_c:
565
                # killed in parent; can't be in either a or b
566
                # not relevant to our work
567
                yield 'killed-base', line
926 by Martin Pool
- update more weave code to use intsets
568
            elif insert in inc_c:
918 by Martin Pool
- start doing new weave-merge algorithm
569
                # was inserted in base
570
                killed_a = bool(deleteset & inc_a)
571
                killed_b = bool(deleteset & inc_b)
572
                if killed_a and killed_b:
573
                    yield 'killed-both', line
574
                elif killed_a:
575
                    yield 'killed-a', line
576
                elif killed_b:
577
                    yield 'killed-b', line
578
                else:
579
                    yield 'unchanged', line
926 by Martin Pool
- update more weave code to use intsets
580
            elif insert in inc_a:
918 by Martin Pool
- start doing new weave-merge algorithm
581
                if deleteset & inc_a:
582
                    yield 'ghost-a', line
583
                else:
584
                    # new in A; not in B
585
                    yield 'new-a', line
926 by Martin Pool
- update more weave code to use intsets
586
            elif insert in inc_b:
918 by Martin Pool
- start doing new weave-merge algorithm
587
                if deleteset & inc_b:
588
                    yield 'ghost-b', line
589
                else:
590
                    yield 'new-b', line
591
            else:
592
                # not in either revision
593
                yield 'irrelevant', line
594
919 by Martin Pool
- more development of weave-merge
595
        yield 'unchanged', ''           # terminator
596
597
598
599
    def weave_merge(self, plan):
600
        lines_a = []
601
        lines_b = []
602
        ch_a = ch_b = False
603
604
        for state, line in plan:
605
            if state == 'unchanged' or state == 'killed-both':
606
                # resync and flush queued conflicts changes if any
607
                if not lines_a and not lines_b:
608
                    pass
609
                elif ch_a and not ch_b:
610
                    # one-sided change:                    
611
                    for l in lines_a: yield l
612
                elif ch_b and not ch_a:
613
                    for l in lines_b: yield l
614
                elif lines_a == lines_b:
615
                    for l in lines_a: yield l
616
                else:
617
                    yield '<<<<\n'
618
                    for l in lines_a: yield l
619
                    yield '====\n'
620
                    for l in lines_b: yield l
621
                    yield '>>>>\n'
622
623
                del lines_a[:]
624
                del lines_b[:]
625
                ch_a = ch_b = False
626
                
627
            if state == 'unchanged':
628
                if line:
629
                    yield line
630
            elif state == 'killed-a':
631
                ch_a = True
632
                lines_b.append(line)
633
            elif state == 'killed-b':
634
                ch_b = True
635
                lines_a.append(line)
636
            elif state == 'new-a':
637
                ch_a = True
638
                lines_a.append(line)
639
            elif state == 'new-b':
640
                ch_b = True
641
                lines_b.append(line)
642
            else:
920 by Martin Pool
- add more test cases for weave_merge
643
                assert state in ('irrelevant', 'ghost-a', 'ghost-b', 'killed-base',
644
                                 'killed-both'), \
919 by Martin Pool
- more development of weave-merge
645
                       state
646
647
                
648
649
918 by Martin Pool
- start doing new weave-merge algorithm
650
651
0.1.62 by Martin Pool
Lame command-line client for reading and writing weaves.
652
0.1.88 by Martin Pool
Add weave info command.
653
def weave_info(filename, out):
654
    """Show some text information about the weave."""
655
    from weavefile import read_weave
656
    wf = file(filename, 'rb')
657
    w = read_weave(wf)
658
    # FIXME: doesn't work on pipes
659
    weave_size = wf.tell()
660
    print >>out, "weave file size %d bytes" % weave_size
661
    print >>out, "weave contains %d versions" % len(w._v)
662
663
    total = 0
870 by Martin Pool
- better weave info display
664
    print '%6s %6s %8s %40s %20s' % ('ver', 'lines', 'bytes', 'sha1', 'parents')
665
    for i in (6, 6, 8, 40, 20):
666
        print '-' * i,
667
    print
0.1.88 by Martin Pool
Add weave info command.
668
    for i in range(len(w._v)):
669
        text = w.get(i)
670
        lines = len(text)
671
        bytes = sum((len(a) for a in text))
0.1.91 by Martin Pool
Update Weave.check
672
        sha1 = w._sha1s[i]
870 by Martin Pool
- better weave info display
673
        print '%6d %6d %8d %40s' % (i, lines, bytes, sha1),
892 by Martin Pool
- weave stores only direct parents, and calculates and memoizes expansion as needed
674
        for pv in w._v[i]:
675
            print pv,
676
        print
0.1.88 by Martin Pool
Add weave info command.
677
        total += bytes
678
679
    print >>out, "versions total %d bytes" % total
680
    print >>out, "compression ratio %.3f" % (float(total)/float(weave_size))
869 by Martin Pool
- more weave.py command line options
681
682
683
def usage():
871 by Martin Pool
- add command for merge-based weave
684
    print """bzr weave tool
685
686
Experimental tool for weave algorithm.
687
869 by Martin Pool
- more weave.py command line options
688
usage:
689
    weave init WEAVEFILE
690
        Create an empty weave file
691
    weave get WEAVEFILE VERSION
692
        Write out specified version.
693
    weave check WEAVEFILE
694
        Check consistency of all versions.
695
    weave info WEAVEFILE
696
        Display table of contents.
697
    weave add WEAVEFILE [BASE...] < NEWTEXT
698
        Add NEWTEXT, with specified parent versions.
699
    weave annotate WEAVEFILE VERSION
700
        Display origin of each line.
701
    weave mash WEAVEFILE VERSION...
702
        Display composite of all selected versions.
703
    weave merge WEAVEFILE VERSION1 VERSION2 > OUT
704
        Auto-merge two versions and display conflicts.
871 by Martin Pool
- add command for merge-based weave
705
706
example:
707
708
    % weave init foo.weave
709
    % vi foo.txt
710
    % weave add foo.weave < foo.txt
711
    added version 0
712
713
    (create updated version)
714
    % vi foo.txt
715
    % weave get foo.weave 0 | diff -u - foo.txt
716
    % weave add foo.weave 0 < foo.txt
717
    added version 1
718
719
    % weave get foo.weave 0 > foo.txt       (create forked version)
720
    % vi foo.txt
721
    % weave add foo.weave 0 < foo.txt
722
    added version 2
723
724
    % weave merge foo.weave 1 2 > foo.txt   (merge them)
725
    % vi foo.txt                            (resolve conflicts)
726
    % weave add foo.weave 1 2 < foo.txt     (commit merged version)     
727
    
869 by Martin Pool
- more weave.py command line options
728
"""
0.1.88 by Martin Pool
Add weave info command.
729
    
730
0.1.62 by Martin Pool
Lame command-line client for reading and writing weaves.
731
732
def main(argv):
733
    import sys
734
    import os
869 by Martin Pool
- more weave.py command line options
735
    from weavefile import write_weave, read_weave
894 by Martin Pool
- small optimization for weave extract
736
    from bzrlib.progress import ProgressBar
737
738
    #import psyco
739
    #psyco.full()
740
0.1.62 by Martin Pool
Lame command-line client for reading and writing weaves.
741
    cmd = argv[1]
869 by Martin Pool
- more weave.py command line options
742
743
    def readit():
744
        return read_weave(file(argv[2], 'rb'))
745
    
746
    if cmd == 'help':
747
        usage()
748
    elif cmd == 'add':
749
        w = readit()
0.1.62 by Martin Pool
Lame command-line client for reading and writing weaves.
750
        # at the moment, based on everything in the file
869 by Martin Pool
- more weave.py command line options
751
        parents = map(int, argv[3:])
0.1.72 by Martin Pool
Go back to weave lines normally having newlines at the end.
752
        lines = sys.stdin.readlines()
0.1.69 by Martin Pool
Simple text-based format for storing weaves, cleaner than
753
        ver = w.add(parents, lines)
869 by Martin Pool
- more weave.py command line options
754
        write_weave(w, file(argv[2], 'wb'))
755
        print 'added version %d' % ver
0.1.62 by Martin Pool
Lame command-line client for reading and writing weaves.
756
    elif cmd == 'init':
757
        fn = argv[2]
758
        if os.path.exists(fn):
759
            raise IOError("file exists")
760
        w = Weave()
869 by Martin Pool
- more weave.py command line options
761
        write_weave(w, file(fn, 'wb'))
762
    elif cmd == 'get': # get one version
763
        w = readit()
0.1.94 by Martin Pool
Fix get_iter call
764
        sys.stdout.writelines(w.get_iter(int(argv[3])))
869 by Martin Pool
- more weave.py command line options
765
        
766
    elif cmd == 'mash': # get composite
767
        w = readit()
768
        sys.stdout.writelines(w.mash_iter(map(int, argv[3:])))
769
0.1.62 by Martin Pool
Lame command-line client for reading and writing weaves.
770
    elif cmd == 'annotate':
869 by Martin Pool
- more weave.py command line options
771
        w = readit()
0.1.72 by Martin Pool
Go back to weave lines normally having newlines at the end.
772
        # newline is added to all lines regardless; too hard to get
773
        # reasonable formatting otherwise
0.1.62 by Martin Pool
Lame command-line client for reading and writing weaves.
774
        lasto = None
775
        for origin, text in w.annotate(int(argv[3])):
0.1.72 by Martin Pool
Go back to weave lines normally having newlines at the end.
776
            text = text.rstrip('\r\n')
0.1.62 by Martin Pool
Lame command-line client for reading and writing weaves.
777
            if origin == lasto:
778
                print '      | %s' % (text)
779
            else:
780
                print '%5d | %s' % (origin, text)
781
                lasto = origin
871 by Martin Pool
- add command for merge-based weave
782
                
0.1.88 by Martin Pool
Add weave info command.
783
    elif cmd == 'info':
784
        weave_info(argv[2], sys.stdout)
871 by Martin Pool
- add command for merge-based weave
785
        
0.1.91 by Martin Pool
Update Weave.check
786
    elif cmd == 'check':
869 by Martin Pool
- more weave.py command line options
787
        w = readit()
894 by Martin Pool
- small optimization for weave extract
788
        pb = ProgressBar()
789
        w.check(pb)
790
        pb.clear()
871 by Martin Pool
- add command for merge-based weave
791
892 by Martin Pool
- weave stores only direct parents, and calculates and memoizes expansion as needed
792
    elif cmd == 'inclusions':
793
        w = readit()
794
        print ' '.join(map(str, w.inclusions([int(argv[3])])))
795
796
    elif cmd == 'parents':
797
        w = readit()
798
        print ' '.join(map(str, w._v[int(argv[3])]))
799
918 by Martin Pool
- start doing new weave-merge algorithm
800
    elif cmd == 'plan-merge':
801
        w = readit()
802
        for state, line in w.plan_merge(int(argv[3]), int(argv[4])):
919 by Martin Pool
- more development of weave-merge
803
            if line:
804
                print '%14s | %s' % (state, line),
918 by Martin Pool
- start doing new weave-merge algorithm
805
871 by Martin Pool
- add command for merge-based weave
806
    elif cmd == 'merge':
919 by Martin Pool
- more development of weave-merge
807
        w = readit()
808
        p = w.plan_merge(int(argv[3]), int(argv[4]))
809
        sys.stdout.writelines(w.weave_merge(p))
810
            
811
    elif cmd == 'mash-merge':
871 by Martin Pool
- add command for merge-based weave
812
        if len(argv) != 5:
813
            usage()
814
            return 1
815
816
        w = readit()
817
        v1, v2 = map(int, argv[3:5])
818
819
        basis = w.inclusions([v1]).intersection(w.inclusions([v2]))
820
821
        base_lines = list(w.mash_iter(basis))
822
        a_lines = list(w.get(v1))
823
        b_lines = list(w.get(v2))
824
825
        from bzrlib.merge3 import Merge3
826
        m3 = Merge3(base_lines, a_lines, b_lines)
827
828
        name_a = 'version %d' % v1
829
        name_b = 'version %d' % v2
830
        sys.stdout.writelines(m3.merge_lines(name_a=name_a, name_b=name_b))
0.1.62 by Martin Pool
Lame command-line client for reading and writing weaves.
831
    else:
832
        raise ValueError('unknown command %r' % cmd)
833
    
834
835
if __name__ == '__main__':
836
    import sys
837
    sys.exit(main(sys.argv))