← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to weave.py

  • Committer: Martin Pool
  • Date: 2005-06-28 06:50:35 UTC
  • mto: This revision was merged to the branch mainline in revision 852.
  • Revision ID: mbp@sourcefrog.net-20050628065035-d3a164490179b935
Change to a more realistic weave structure which can represent insertions and 
deletions.

Tests which calculate deltas are currently not working and are skipped.

Show diffs side-by-side

added added

removed removed

Lines of Context:
weave.py
21
21
 
22
22
"""Weave - storage of related text file versions"""
23
23
 
24
 
# TODO: Perhaps have copy and comparison methods?
 
24
# TODO: Perhaps have copy and comparison methods of Weave instances?
25
25
 
26
26
 
27
27
class VerInfo(object):
54
54
    Typically the index number will be valid only inside this weave and
55
55
    the version-id is used to reference it in the larger world.
56
56
 
 
57
    The weave is represented as a list mixing edit instructions and
 
58
    literal text.  Each entry in _l can be either a string (or
 
59
    unicode), or a tuple.  If a string, it means that the given line
 
60
    should be output in the currently active revisions.
 
61
 
 
62
    If a tuple, it gives a processing instruction saying in which
 
63
    revisions the enclosed lines are active.  The tuple has the form
 
64
    (instruction, version).
 
65
 
 
66
    The instruction can be '{' or '}' for an insertion block, and '['
 
67
    and ']' for a deletion block respectively.  The version is the
 
68
    integer version index.
 
69
 
 
70
    Constraints:
 
71
 
 
72
    * A later version can delete lines that were introduced by any
 
73
      number of ancestor versions; this implies that deletion
 
74
      instructions can span insertion blocks without regard to the
 
75
      insertion block's nesting.
 
76
 
 
77
    * Similarly, deletions need not be properly nested.
 
78
 
 
79
 
57
80
    _l
58
 
        List of edit instructions.
59
 
 
60
 
        Each line is stored as a tuple of (index-id, text).  The line
61
 
        is present in the version equal to index-id.
 
81
        Text of the weave. 
62
82
 
63
83
    _v
64
84
        List of versions, indexed by index number.
81
101
 
82
102
        text
83
103
            Sequence of lines to be added in the new version."""
84
 
        if not isinstance(text, list):
85
 
            raise ValueError("text should be a list, not %s" % type(text))
86
 
 
87
104
        self._check_versions(parents)
 
105
        self._check_lines(text)
88
106
 
89
107
        idx = len(self._v)
90
108
 
105
123
                if i1 != i2:
106
124
                    raise NotImplementedError("can't handle replacing weave [%d:%d] yet"
107
125
                                              % (i1, i2))
108
 
                
109
 
                for line in newlines:
110
 
                    self._l.insert(i1 + offset, (idx, line))
111
 
                    offset += 1
 
126
 
 
127
                self._l.insert(i1 + offset, ('{', idx))
 
128
                i = i1 + offset + 1
 
129
                self._l[i:i] = newlines
 
130
                self._l.insert(i + 1, ('}', idx))
 
131
                offset += 2 + len(newlines)
112
132
 
113
133
            self._v.append(VerInfo(parents))
114
134
        else:
115
135
            # special case; adding with no parents revision; can do this
116
136
            # more quickly by just appending unconditionally
117
 
            for line in text:
118
 
                self._l.append((idx, line))
 
137
            self._l.append(('{', idx))
 
138
            self._l += text
 
139
            self._l.append(('}', idx))
119
140
 
120
141
            self._v.append(VerInfo())
121
142
            
122
143
        return idx
123
144
 
124
145
 
 
146
    def _check_lines(self, text):
 
147
        if not isinstance(text, list):
 
148
            raise ValueError("text should be a list, not %s" % type(text))
 
149
 
 
150
        for l in text:
 
151
            if not isinstance(l, basestring):
 
152
                raise ValueError("text line should be a string or unicode, not %s" % type(l))
 
153
        
 
154
 
 
155
 
125
156
    def _check_versions(self, indexes):
126
157
        """Check everything in the sequence of indexes is valid"""
127
158
        for i in indexes:
145
176
            raise IndexError('version index %d out of range' % index)
146
177
        included = set(vi.included)
147
178
        included.add(index)
148
 
        return iter(self._extract(included))
 
179
        for origin, lineno, text in self._extract(included):
 
180
            yield origin, text
149
181
 
150
182
 
151
183
    def _extract(self, included):
152
184
        """Yield annotation of lines in included set.
153
185
 
 
186
        Yields a sequence of tuples (origin, lineno, text), where
 
187
        origin is the origin version, lineno the index in the weave,
 
188
        and text the text of the line.
 
189
 
154
190
        The set typically but not necessarily corresponds to a version.
155
191
        """
156
 
        for origin, line in self._l:
157
 
            if origin in included:
158
 
                yield origin, line
 
192
        stack = []
 
193
        isactive = False
 
194
        lineno = 0
159
195
        
 
196
        for l in self._l:
 
197
            if isinstance(l, tuple):
 
198
                c, v = l
 
199
                if c == '{':
 
200
                    stack.append(l)
 
201
                    isactive = (v in included)
 
202
                elif c == '}':
 
203
                    oldc, oldv = stack.pop()
 
204
                    assert oldc == '{'
 
205
                    assert oldv == v
 
206
                    isactive == stack and (stack[-1][1] in included)
 
207
                else:
 
208
                    raise ValueError("invalid processing instruction %r" % (l,))
 
209
            else:
 
210
                assert isinstance(l, basestring)
 
211
                if isactive:
 
212
                    origin = stack[-1][1]
 
213
                    yield origin, lineno, l
 
214
            lineno += 1
160
215
 
161
216
 
162
217
    def getiter(self, index):
219
274
 
220
275
        ##print 'my lines:'
221
276
        ##pprint(self._l)
222
 
        
223
 
        lineno = 0
224
 
        for origin, line in self._l:
225
 
            if origin in included:
226
 
                basis.append((lineno, line))
227
 
            lineno += 1
228
277
 
229
 
        assert lineno == len(self._l)
 
278
        basis = list(self._extract(included))
230
279
 
231
280
        # now make a parallel list with only the text, to pass to the differ
232
 
        basis_lines = [line for (lineno, line) in basis]
 
281
        basis_lines = [line for (origin, lineno, line) in basis]
233
282
 
234
283
        # add a sentinal, because we can also match against the final line
235
284
        basis.append((len(self._l), None))