subvertpy/delta.py

   1 # Copyright (C) 2005-2006 Jelmer Vernooij <jelmer@jelmer.uk>
   2
   3 # This program is free software; you can redistribute it and/or modify
   4 # it under the terms of the GNU Lesser General Public License as published by
   5 # the Free Software Foundation; either version 2.1 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 Lesser General Public License for more details.
  12
  13 # You should have received a copy of the GNU Lesser General Public License
  14 # along with this program; if not, write to the Free Software
  15 # Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  16 """Subversion delta operations."""
  17
  18 __author__ = "Jelmer Vernooij <jelmer@jelmer.uk>"
  19 __docformat__ = "restructuredText"
  20
  21 from hashlib import (
  22     md5,
  23     )
  24
  25
  26 TXDELTA_SOURCE = 0
  27 TXDELTA_TARGET = 1
  28 TXDELTA_NEW = 2
  29 TXDELTA_INVALID = 3
  30
  31 MAX_ENCODED_INT_LEN = 10
  32
  33 DELTA_WINDOW_SIZE = 102400
  34
  35
  36 def apply_txdelta_window(sbuf, window):
  37     """Apply a txdelta window to a buffer.
  38
  39     :param sbuf: Source buffer (as bytestring)
  40     :param window: (sview_offset, sview_len, tview_len, src_ops, ops, new_data)
  41     :param sview_offset: Offset of the source view
  42     :param sview_len: Length of the source view
  43     :param tview_len: Target view length
  44     :param src_ops: Operations to apply to sview
  45     :param ops: Ops to apply
  46     :param new_data: Buffer with possible new data
  47     :return: Target buffer
  48     """
  49     (sview_offset, sview_len, tview_len, src_ops, ops, new_data) = window
  50     sview = sbuf[sview_offset:sview_offset+sview_len]
  51     tview = txdelta_apply_ops(src_ops, ops, new_data, sview)
  52     if len(tview) != tview_len:
  53         raise AssertionError("%d != %d" % (len(tview), tview_len))
  54     return tview
  55
  56
  57 def apply_txdelta_handler_chunks(source_chunks, target_chunks):
  58     """Return a function that can be called repeatedly with txdelta windows.
  59
  60     :param sbuf: Source buffer
  61     :param target_stream: Target stream
  62     """
  63     sbuf = bytes().join(source_chunks)
  64
  65     def apply_window(window):
  66         if window is None:
  67             return  # Last call
  68         target_chunks.append(apply_txdelta_window(sbuf, window))
  69     return apply_window
  70
  71
  72 def apply_txdelta_handler(sbuf, target_stream):
  73     """Return a function that can be called repeatedly with txdelta windows.
  74
  75     :param sbuf: Source buffer
  76     :param target_stream: Target stream
  77     """
  78     def apply_window(window):
  79         if window is None:
  80             return  # Last call
  81         target_stream.write(apply_txdelta_window(sbuf, window))
  82     return apply_window
  83
  84
  85 def txdelta_apply_ops(src_ops, ops, new_data, sview):
  86     """Apply txdelta operations to a source view.
  87
  88     :param src_ops: Source operations, ignored.
  89     :param ops: List of operations (action, offset, length).
  90     :param new_data: Buffer to fetch fragments with new data from
  91     :param sview: Source data
  92     :return: Result data
  93     """
  94     tview = bytearray()
  95     for (action, offset, length) in ops:
  96         if action == TXDELTA_SOURCE:
  97             # Copy from source area.
  98             tview.extend(sview[offset:offset+length])
  99         elif action == TXDELTA_TARGET:
 100             for i in range(length):
 101                 tview.append(tview[offset+i])
 102         elif action == TXDELTA_NEW:
 103             tview.extend(new_data[offset:offset+length])
 104         else:
 105             raise Exception("Invalid delta instruction code")
 106     return tview
 107
 108
 109 def send_stream(stream, handler, block_size=DELTA_WINDOW_SIZE):
 110     """Send txdelta windows that create stream to handler
 111
 112     :param stream: file-like object to read the file from
 113     :param handler: txdelta window handler function
 114     :return: MD5 hash over the stream
 115     """
 116     hash = md5()
 117     text = stream.read(block_size)
 118     if not isinstance(text, bytes):
 119         raise TypeError("The stream should read out bytes")
 120     while text:
 121         hash.update(text)
 122         window = (0, 0, len(text), 0, [(TXDELTA_NEW, 0, len(text))], text)
 123         handler(window)
 124         text = stream.read(block_size)
 125     handler(None)
 126     return hash.digest()
 127
 128
 129 def encode_length(len):
 130     """Encode a length variable.
 131
 132     :param len: Length to encode
 133     :return: String with encoded length
 134     """
 135     # Based on encode_int() in subversion/libsvn_delta/svndiff.c
 136     assert len >= 0
 137     assert isinstance(len, int), "expected int, got %r" % (len,)
 138
 139     # Count number of required bytes
 140     v = len >> 7
 141     n = 1
 142     while v > 0:
 143         v = v >> 7
 144         n += 1
 145
 146     assert n <= MAX_ENCODED_INT_LEN
 147
 148     ret = bytearray()
 149     while n > 0:
 150         n -= 1
 151         if n > 0:
 152             cont = 1
 153         else:
 154             cont = 0
 155         ret.append(((len >> (n * 7)) & 0x7f) | (cont << 7))
 156
 157     return ret
 158
 159
 160 def decode_length(text):
 161     """Decode a length variable.
 162
 163     :param text: Bytestring to decode
 164     :return: Integer with actual length
 165     """
 166     # Decode bytes until we're done.  */
 167     ret = 0
 168     next = True
 169     while next:
 170         ret = (ret << 7) | (text[0] & 0x7f)
 171         next = (text[0] >> 7) & 0x1
 172         text = text[1:]
 173     return ret, text
 174
 175
 176 def pack_svndiff_instruction(diff_params):
 177     """Pack a SVN diff instruction
 178
 179     :param diff_params: (action, offset, length)
 180     :param action: Action
 181     :param offset: Offset
 182     :param length: Length
 183     :return: encoded text
 184     """
 185     (action, offset, length) = diff_params
 186     if length < 0x3f:
 187         text = bytearray(((action << 6) + length,))
 188     else:
 189         text = bytearray((action << 6,)) + encode_length(length)
 190     if action != TXDELTA_NEW:
 191         text += encode_length(offset)
 192     return text
 193
 194
 195 def unpack_svndiff_instruction(text):
 196     """Unpack a SVN diff instruction
 197
 198     :param text: Text to parse
 199     :return: tuple with operation, remaining text
 200     """
 201     action = text[0] >> 6
 202     length = text[0] & 0x3f
 203     text = text[1:]
 204     assert action in (TXDELTA_NEW, TXDELTA_SOURCE, TXDELTA_TARGET)
 205     if length == 0:
 206         length, text = decode_length(text)
 207     if action != TXDELTA_NEW:
 208         offset, text = decode_length(text)
 209     else:
 210         offset = 0
 211     return (action, offset, length), text
 212
 213
 214 SVNDIFF0_HEADER = b"SVN\0"
 215
 216
 217 def pack_svndiff0_window(window):
 218     """Pack an individual window using svndiff0.
 219
 220     :param window: Window to pack
 221     :return: Packed diff (as bytestring)
 222     """
 223     (sview_offset, sview_len, tview_len, src_ops, ops, new_data) = window
 224     ret = (encode_length(sview_offset) +
 225            encode_length(sview_len) +
 226            encode_length(tview_len))
 227
 228     instrdata = bytearray()
 229     for op in ops:
 230         instrdata += pack_svndiff_instruction(op)
 231
 232     ret.extend(encode_length(len(instrdata)))
 233     ret.extend(encode_length(len(new_data)))
 234     ret.extend(instrdata)
 235     ret.extend(new_data)
 236     return ret
 237
 238
 239 def pack_svndiff0(windows):
 240     """Pack a SVN diff file.
 241
 242     :param windows: Iterator over diff windows
 243     :return: text
 244     """
 245     ret = SVNDIFF0_HEADER
 246     for window in windows:
 247         ret += pack_svndiff0_window(window)
 248     return ret
 249
 250
 251 def unpack_svndiff0(text):
 252     """Unpack a version 0 svndiff text.
 253
 254     :param text: Text to unpack.
 255     :return: yields tuples with sview_offset, sview_len, tview_len, ops_len,
 256         ops, newdata
 257     """
 258     assert text.startswith(SVNDIFF0_HEADER)
 259     text = text[4:]
 260
 261     while text:
 262         sview_offset, text = decode_length(text)
 263         sview_len, text = decode_length(text)
 264         tview_len, text = decode_length(text)
 265         instr_len, text = decode_length(text)
 266         newdata_len, text = decode_length(text)
 267
 268         instrdata = text[:instr_len]
 269         text = text[instr_len:]
 270
 271         ops = []
 272         while instrdata:
 273             op, instrdata = unpack_svndiff_instruction(instrdata)
 274             ops.append(op)
 275
 276         newdata = text[:newdata_len]
 277         text = text[newdata_len:]
 278         yield (sview_offset, sview_len, tview_len, len(ops), ops, newdata)