git ssb

1
var buffered = require('pull-buffered')
2
var pull = require('pull-stream')
3
var toPull = require('stream-to-pull-stream')
4
var pako = require('pako')
5
var createHash = require('./util').createHash
6
var cat = require('pull-cat')
7
8
exports.decode = decodePack
9
exports.encode = encodePack
10
11
var PACK_VERSION = 2
12
13
var objectTypes = [
14
  'none', 'commit', 'tree', 'blob',
15
  'tag', 'unused', 'ofs-delta', 'ref-delta'
16
]
17
var objectTypeNums = {
18
  commit: 1,
19
  tree: 2,
20
  blob: 3,
21
  tag: 4,
22
  'ofs-delta': 6,
23
  'ref-delta': 7
24
}
25
26
function error(cb) {
27
  return function (err) {
28
    cb(err || true)
29
  }
30
}
31
32
function inflateBytes(read) {
33
  var inflate = new pako.Inflate()
34
  var ended, dataOut
35
36
  inflate.onData = function (data) {
37
    dataOut = new Buffer(data)
38
    // console.error('inflated data', data.length)
39
  }
40
41
  inflate.onEnd = function (status) {
42
    ended = (status === 0) ? true : new Error(inflate.strm.msg)
43
    // console.error('inflated end', status, ended)
44
  }
45
46
  return function (abort, cb) {
47
    if (ended) return cb(ended)
48
    read(abort, function next(end, data) {
49
      if (end === true) {
50
        end = null
51
        data = []
52
      }
53
      if (ended = end) return cb(end)
54
      if (data.length > 1) return cb(new Error('got more than one byte'))
55
      dataOut = null
56
      inflate.push(data, end === true)
57
      if (dataOut)
58
        cb(null, dataOut)
59
      else if (ended)
60
        cb(ended)
61
      else
62
        // let the stack unwind
63
        setImmediate(function () {
64
          read(null, next)
65
        })
66
    })
67
  }
68
}
69
70
function deflate(read) {
71
  var def = new pako.Deflate()
72
  var queue = []
73
  var ended
74
75
  def.onData = function (data) {
76
    queue.push([null, new Buffer(data)])
77
  }
78
79
  def.onEnd = function (status) {
80
    queue.push([(status === 0) ? true : new Error(def.strm.msg)])
81
  }
82
83
  return function readOut(abort, cb) {
84
    if (ended)
85
      cb(ended)
86
    else if (queue.length)
87
      cb.apply(this, queue.shift())
88
    else
89
      read(abort, function next(end, data) {
90
        if (end === true) def.push([], true)
91
        else if (end) return cb(end)
92
        else def.push(data)
93
        readOut(null, cb)
94
      })
95
  }
96
}
97
98
function decodePack(opts, repo, onEnd, read) {
99
  if (read === undefined)
100
    return decodePack.bind(this, opts, repo, onEnd)
101
  onEnd = onEnd || function(err) {
102
    if (err) throw err
103
  }
104
105
  var ended
106
  var numObjects = -1
107
  var checksum = createHash('sha1')
108
  var b = buffered(read)
109
  // TODO: optimize to pass through buffers to checksum
110
  var readByte = checksum(b.chunks(1))
111
  var readWord = checksum(b.chunks(4))
112
  var readHash = checksum(b.chunks(20))
113
  var readChecksum = b.chunks(20)
114
  var expectChecksum = true
115
116
  function readHeader(cb) {
117
    readWord(null, function (end, header) {
118
      if (ended = end) return cb(end)
119
      if (!header.equals(header, new Buffer('PACK')))
120
        read(new Error('Invalid packfile header'), error(cb))
121
      else
122
        readVersion(cb)
123
    })
124
  }
125
126
  function readVersion(cb) {
127
    readWord(null, function (end, word) {
128
      if (ended = end) return cb(end)
129
      var version = word.readUInt32BE()
130
      if (version < 2 || version > 3)
131
        read(new Error('Invalid packfile version ' + version), error(cb))
132
      else
133
        readNumObjects(cb)
134
    })
135
  }
136
137
  function readNumObjects(cb) {
138
    readWord(null, function (end, word) {
139
      if (ended = end) return cb(end)
140
      numObjects = word.readUInt32BE()
141
      if (opts.verbosity >= 2)
142
        console.error(numObjects + ' objects')
143
      if (opts.onHeader)
144
        opts.onHeader(numObjects)
145
      readObject(null, cb)
146
    })
147
  }
148
149
  function readTypedVarInt(cb) {
150
    var type, value, shift
151
    // https://codewords.recurse.com/images/three/varint.svg
152
    readByte(null, function (end, buf) {
153
      if (ended = end) return cb(end)
154
      var firstByte = buf[0]
155
      type = objectTypes[(firstByte >> 4) & 7]
156
      value = firstByte & 15
157
      // console.error('byte1', firstByte, firstByte.toString(2))
158
      shift = 4
159
      checkByte(firstByte)
160
    })
161
162
    function checkByte(byte) {
163
      if (byte & 0x80)
164
        readByte(null, gotByte)
165
      else
166
        cb(null, type, value)
167
    }
168
169
    function gotByte(end, buf) {
170
      if (ended = end) return cb(end)
171
      var byte = buf[0]
172
      value += (byte & 0x7f) << shift
173
      shift += 7
174
      // console.error('byte', byte, byte.toString(2))
175
      checkByte(byte)
176
    }
177
  }
178
179
  function getObject(cb) {
180
    readTypedVarInt(function (end, type, length) {
181
      if (opts.verbosity >= 2)
182
        console.error('read object header', end, type, length)
183
      numObjects--
184
      if (end === true && expectChecksum)
185
        onEnd(new Error('Missing checksum'))
186
      if (ended = end) return cb(end)
187
      // TODO: verify that the inflated data is the correct length
188
      if (type == 'ref-delta')
189
        getObjectFromRefDelta(length, cb)
190
      else
191
        cb(null, {
192
          type: type,
193
          length: length,
194
          read: inflateBytes(readByte)
195
        })
196
    })
197
  }
198
199
  // TODO: test with ref-delta objects in pack
200
  function getObjectFromRefDelta(length, cb) {
201
    readHash(null, function (end, sourceHash) {
202
      if (end) return cb(end)
203
      sourceHash = sourceHash.toString('hex')
204
      var b = buffered(inflateBytes(readByte))
205
      var readInflatedByte = b.chunks(1)
206
      readVarInt(readInflatedByte, function (err, expectedSourceLength) {
207
        if (err) return cb(err)
208
        readVarInt(readInflatedByte, function (err, expectedTargetLength) {
209
          if (err) return cb(err)
210
          if (opts.verbosity >= 3)
211
            console.error('getting object', sourceHash)
212
          repo.getObject(sourceHash, function (err, sourceObject) {
213
            if (opts.verbosity >= 3)
214
              console.error('got object', sourceHash, sourceObject, err)
215
            if (err) return cb(err)
216
            if (sourceObject.length != expectedSourceLength)
217
              cb(new Error('Incorrect source object size in ref delta'))
218
            else
219
              patchObject(opts, b, length, sourceObject,
220
                expectedTargetLength, cb)
221
          })
222
        })
223
      })
224
    })
225
  }
226
227
  function readTrailer(cb) {
228
    // read the checksum before it updates to include the trailer
229
    var expected = checksum.digest()
230
    readChecksum(null, function (end, value) {
231
      cb(true)
232
      if (end === true && expectChecksum)
233
        onEnd(new Error('Missing checksum'))
234
      if (!value.equals(expected)) {
235
        onEnd(new Error('Checksum mismatch: ' +
236
          expected.hexSlice() + ' != ' + value.hexSlice()))
237
      } else {
238
        if (opts.verbosity >= 3)
239
          console.error('checksum ok', expected.hexSlice())
240
        onEnd(null)
241
      }
242
    })
243
  }
244
245
  function readObject(abort, cb) {
246
    if (ended) cb(ended)
247
    else if (abort) read(abort, function (err) { cb(ended = err || abort) })
248
    else if (numObjects < 0) readHeader(cb)
249
    else if (numObjects > 0) getObject(cb)
250
    else if (expectChecksum) readTrailer(cb)
251
  }
252
253
  return readObject
254
}
255
256
function readVarInt(readByte, cb) {
257
  var value = 0, shift = 0
258
  readByte(null, function gotByte(end, buf) {
259
    if (ended = end) return cb(end)
260
    var byte = buf[0]
261
    value += (byte & 0x7f) << shift
262
    shift += 7
263
    if (byte & 0x80)
264
      readByte(null, gotByte)
265
    else
266
      cb(null, value)
267
  })
268
}
269
270
function patchObject(opts, deltaB, deltaLength, srcObject, targetLength, cb) {
271
  var readByte = deltaB.chunks(1)
272
  var srcBuf
273
  var ended
274
275
  if (opts.verbosity >= 2)
276
    console.error('patching', srcObject.type, targetLength)
277
  pull(
278
    srcObject.read,
279
    pull.collect(function (err, bufs) {
280
      srcBuf = Buffer.concat(bufs, srcObject.length)
281
      cb(null, {
282
        type: srcObject.type,
283
        length: targetLength,
284
        read: read
285
      })
286
    })
287
  )
288
289
  function read(abort, cb) {
290
    if (ended) return cb(ended)
291
    readByte(null, function (end, dBuf) {
292
      if (ended = end) return cb(end)
293
      var cmd = dBuf[0]
294
      if (cmd & 0x80)
295
        // skip a variable amount and then pass through a variable amount
296
        readOffsetSize(cmd, deltaB, function (err, offset, size) {
297
          if (err) return earlyEnd(err)
298
          var buf = srcBuf.slice(offset, offset + size)
299
          cb(end, buf)
300
        })
301
      else if (cmd)
302
        // insert `cmd` bytes from delta
303
        deltaB.chunks(cmd)(null, cb)
304
      else
305
        cb(new Error("unexpected delta opcode 0"))
306
    })
307
308
    function earlyEnd(err) {
309
      cb(err === true ? new Error('stream ended early') : err)
310
    }
311
  }
312
}
313
314
function readOffsetSize(cmd, b, readCb) {
315
  var readByte = b.chunks(1)
316
  var offset = 0, size = 0
317
318
  function addByte(bit, outPos, cb) {
319
    if (cmd & (1 << bit))
320
      readByte(null, function (err, buf) {
321
        if (err) readCb(err)
322
        else cb(buf[0] << (outPos << 3))
323
      })
324
    else
325
      cb(0)
326
  }
327
328
  addByte(0, 0, function (val) {
329
    offset = val
330
    addByte(1, 1, function (val) {
331
      offset |= val
332
      addByte(2, 2, function (val) {
333
        offset |= val
334
        addByte(3, 3, function (val) {
335
          offset |= val
336
          addSize()
337
        })
338
      })
339
    })
340
  })
341
  function addSize() {
342
    addByte(4, 0, function (val) {
343
      size = val
344
      addByte(5, 1, function (val) {
345
        size |= val
346
        addByte(6, 2, function (val) {
347
          size |= val
348
          readCb(null, offset, size || 0x10000)
349
        })
350
      })
351
    })
352
  }
353
}
354
355
function encodeTypedVarInt(typeStr, length, cb) {
356
  var type = objectTypeNums[typeStr]
357
  // console.error('TYPE', type, typeStr, 'len', length, typeof cb)
358
  if (!type)
359
    return cb(new Error("Bad object type " + typeStr))
360
361
  var vals = []
362
  var b = (type << 4) | (length & 15)
363
  for (length >>= 4; length; length >>= 7) {
364
    vals.push(b | 0x80)
365
    b = length & 0x7f
366
  }
367
  vals.push(b)
368
  /*
369
  console.error('sending var int', vals, vals.map(function (n) {
370
    return ('00000000' + Number(n).toString(2)).substr(-8)
371
  }))
372
  */
373
  cb(null, new Buffer(vals))
374
}
375
376
function encodePack(opts, numObjects, readObject) {
377
  if (numObjects === undefined)
378
    numObjects = opts, opts = null
379
  if (readObject === undefined)
380
    return encodePack.bind(this, opts, numObjects)
381
382
  var header = new Buffer(12)
383
  header.write('PACK')
384
  header.writeUInt32BE(PACK_VERSION, 4)
385
  header.writeUInt32BE(numObjects, 8)
386
  var checksum = createHash('sha1')
387
  var readData
388
389
  return cat([
390
    checksum(cat([
391
      pull.once(header),
392
      encodeObject
393
    ])),
394
    checksum.readDigest
395
  ])
396
397
  function encodeObject(abort, cb) {
398
    if (readData)
399
      readData(abort, function (end, data) {
400
        if (end === true)
401
          readObject(abort, nextObject)
402
        else
403
          cb(end, data)
404
      })
405
    else
406
      readObject(abort, nextObject)
407
408
    function nextObject(end, object) {
409
      if (end) return cb(end)
410
      readData = deflate(object.read)
411
      encodeTypedVarInt(object.type, object.length, cb)
412
    }
413
  }
414
}
415