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 inObject = false
107
  var numObjects = -1
108
  var checksum = createHash('sha1')
109
  var b = buffered(read)
110
  // TODO: optimize to pass through buffers to checksum
111
  var readByte = checksum(b.chunks(1))
112
  var readWord = checksum(b.chunks(4))
113
  var readHash = checksum(b.chunks(20))
114
  var readChecksum = b.chunks(20)
115
  var expectChecksum = true
116
  var _cb
117
118
  function readHeader(cb) {
119
    readWord(null, function (end, header) {
120
      if (ended = end) return cb(end)
121
      if (!header.equals(header, new Buffer('PACK')))
122
        read(new Error('Invalid packfile header'), error(cb))
123
      else
124
        readVersion(cb)
125
    })
126
  }
127
128
  function readVersion(cb) {
129
    readWord(null, function (end, word) {
130
      if (ended = end) return cb(end)
131
      var version = word.readUInt32BE()
132
      if (version < 2 || version > 3)
133
        read(new Error('Invalid packfile version ' + version), error(cb))
134
      else
135
        readNumObjects(cb)
136
    })
137
  }
138
139
  function readNumObjects(cb) {
140
    readWord(null, function (end, word) {
141
      if (ended = end) return cb(end)
142
      numObjects = word.readUInt32BE()
143
      if (opts.verbosity >= 2)
144
        console.error(numObjects + ' objects')
145
      if (opts.onHeader)
146
        opts.onHeader(numObjects)
147
      readObject(null, cb)
148
    })
149
  }
150
151
  function readTypedVarInt(cb) {
152
    var type, value, shift
153
    // https://codewords.recurse.com/images/three/varint.svg
154
    readByte(null, function (end, buf) {
155
      if (ended = end) return cb(end)
156
      var firstByte = buf[0]
157
      type = objectTypes[(firstByte >> 4) & 7]
158
      value = firstByte & 15
159
      // console.error('byte1', firstByte, firstByte.toString(2))
160
      shift = 4
161
      checkByte(firstByte)
162
    })
163
164
    function checkByte(byte) {
165
      if (byte & 0x80)
166
        readByte(null, gotByte)
167
      else
168
        cb(null, type, value)
169
    }
170
171
    function gotByte(end, buf) {
172
      if (ended = end) return cb(end)
173
      var byte = buf[0]
174
      value += (byte & 0x7f) << shift
175
      shift += 7
176
      // console.error('byte', byte, byte.toString(2))
177
      checkByte(byte)
178
    }
179
  }
180
181
  function getObject(cb) {
182
    inObject = true
183
    readTypedVarInt(function (end, type, length) {
184
      if (opts.verbosity >= 2)
185
        console.error('read object header', end, type, length)
186
      numObjects--
187
      if (end === true && expectChecksum)
188
        onEnd(new Error('Missing checksum'))
189
      if (ended = end) return cb(end)
190
      // TODO: verify that the inflated data is the correct length
191
      if (type == 'ref-delta')
192
        getObjectFromRefDelta(length, gotObject)
193
      else
194
        gotObject(null, {
195
          type: type,
196
          length: length,
197
          read: inflateBytes(readByte)
198
        })
199
    })
200
201
    function gotObject(err, obj) {
202
      // pass through the object but detect when it ends
203
      if (err) return cb(err)
204
      cb(null, {
205
        type: obj.type,
206
        length: obj.length,
207
        read: pull(
208
          obj.read,
209
          pull.through(null, function () {
210
            inObject = false
211
            if (_cb) {
212
              var cb = _cb
213
              readObject(null, cb)
214
            }
215
          })
216
        )
217
      })
218
    }
219
  }
220
221
  // TODO: test with ref-delta objects in pack
222
  function getObjectFromRefDelta(length, cb) {
223
    readHash(null, function (end, sourceHash) {
224
      if (end) return cb(end)
225
      sourceHash = sourceHash.toString('hex')
226
      var b = buffered(inflateBytes(readByte))
227
      var readInflatedByte = b.chunks(1)
228
      readVarInt(readInflatedByte, function (err, expectedSourceLength) {
229
        if (err) return cb(err)
230
        readVarInt(readInflatedByte, function (err, expectedTargetLength) {
231
          if (err) return cb(err)
232
          if (opts.verbosity >= 3)
233
            console.error('getting object', sourceHash)
234
          setTimeout(function () {
235
            repo.getObject(sourceHash, function (err, sourceObject) {
236
              if (opts.verbosity >= 3)
237
                console.error('got object', sourceHash, sourceObject, err)
238
              if (err) return cb(err)
239
              if (sourceObject.length != expectedSourceLength)
240
                cb(new Error('Incorrect source object size in ref delta'))
241
              else
242
                patchObject(opts, b, length, sourceObject,
243
                  expectedTargetLength, cb)
244
            })
245
          }, 50)
246
        })
247
      })
248
    })
249
  }
250
251
  function readTrailer(cb) {
252
    // read the checksum before it updates to include the trailer
253
    var expected = checksum.digest()
254
    readChecksum(null, function (end, value) {
255
      cb(true)
256
      if (end === true && expectChecksum)
257
        onEnd(new Error('Missing checksum'))
258
      if (!value.equals(expected)) {
259
        onEnd(new Error('Checksum mismatch: ' +
260
          expected.hexSlice() + ' != ' + value.hexSlice()))
261
      } else {
262
        if (opts.verbosity >= 3)
263
          console.error('checksum ok', expected.hexSlice())
264
        onEnd(null)
265
      }
266
    })
267
  }
268
269
  function readObject(abort, cb) {
270
    if (ended) cb(ended)
271
    else if (inObject) _cb = cb
272
    else if (abort) read(abort, function (err) { cb(ended = err || abort) })
273
    else if (numObjects < 0) readHeader(cb)
274
    else if (numObjects > 0) getObject(cb)
275
    else if (expectChecksum) readTrailer(cb)
276
  }
277
278
  return readObject
279
}
280
281
function readVarInt(readByte, cb) {
282
  var value = 0, shift = 0
283
  readByte(null, function gotByte(end, buf) {
284
    if (ended = end) return cb(end)
285
    var byte = buf[0]
286
    value += (byte & 0x7f) << shift
287
    shift += 7
288
    if (byte & 0x80)
289
      readByte(null, gotByte)
290
    else
291
      cb(null, value)
292
  })
293
}
294
295
function patchObject(opts, deltaB, deltaLength, srcObject, targetLength, cb) {
296
  var readByte = deltaB.chunks(1)
297
  var srcBuf
298
  var ended
299
300
  if (opts.verbosity >= 2)
301
    console.error('patching', srcObject.type, targetLength)
302
  pull(
303
    srcObject.read,
304
    pull.collect(function (err, bufs) {
305
      srcBuf = Buffer.concat(bufs, srcObject.length)
306
      cb(null, {
307
        type: srcObject.type,
308
        length: targetLength,
309
        read: read
310
      })
311
    })
312
  )
313
314
  function read(abort, cb) {
315
    if (ended) return cb(ended)
316
    readByte(null, function (end, dBuf) {
317
      if (ended = end) return cb(end)
318
      var cmd = dBuf[0]
319
      if (cmd & 0x80)
320
        // skip a variable amount and then pass through a variable amount
321
        readOffsetSize(cmd, deltaB, function (err, offset, size) {
322
          if (err) return earlyEnd(err)
323
          var buf = srcBuf.slice(offset, offset + size)
324
          cb(end, buf)
325
        })
326
      else if (cmd)
327
        // insert `cmd` bytes from delta
328
        deltaB.chunks(cmd)(null, cb)
329
      else
330
        cb(new Error("unexpected delta opcode 0"))
331
    })
332
333
    function earlyEnd(err) {
334
      cb(err === true ? new Error('stream ended early') : err)
335
    }
336
  }
337
}
338
339
function readOffsetSize(cmd, b, readCb) {
340
  var readByte = b.chunks(1)
341
  var offset = 0, size = 0
342
343
  function addByte(bit, outPos, cb) {
344
    if (cmd & (1 << bit))
345
      readByte(null, function (err, buf) {
346
        if (err) readCb(err)
347
        else cb(buf[0] << (outPos << 3))
348
      })
349
    else
350
      cb(0)
351
  }
352
353
  addByte(0, 0, function (val) {
354
    offset = val
355
    addByte(1, 1, function (val) {
356
      offset |= val
357
      addByte(2, 2, function (val) {
358
        offset |= val
359
        addByte(3, 3, function (val) {
360
          offset |= val
361
          addSize()
362
        })
363
      })
364
    })
365
  })
366
  function addSize() {
367
    addByte(4, 0, function (val) {
368
      size = val
369
      addByte(5, 1, function (val) {
370
        size |= val
371
        addByte(6, 2, function (val) {
372
          size |= val
373
          readCb(null, offset, size || 0x10000)
374
        })
375
      })
376
    })
377
  }
378
}
379
380
function encodeTypedVarInt(typeStr, length, cb) {
381
  var type = objectTypeNums[typeStr]
382
  // console.error('TYPE', type, typeStr, 'len', length, typeof cb)
383
  if (!type)
384
    return cb(new Error("Bad object type " + typeStr))
385
386
  var vals = []
387
  var b = (type << 4) | (length & 15)
388
  for (length >>= 4; length; length >>= 7) {
389
    vals.push(b | 0x80)
390
    b = length & 0x7f
391
  }
392
  vals.push(b)
393
  /*
394
  console.error('sending var int', vals, vals.map(function (n) {
395
    return ('00000000' + Number(n).toString(2)).substr(-8)
396
  }))
397
  */
398
  cb(null, new Buffer(vals))
399
}
400
401
function encodePack(opts, numObjects, readObject) {
402
  if (numObjects === undefined)
403
    numObjects = opts, opts = null
404
  if (readObject === undefined)
405
    return encodePack.bind(this, opts, numObjects)
406
407
  var header = new Buffer(12)
408
  header.write('PACK')
409
  header.writeUInt32BE(PACK_VERSION, 4)
410
  header.writeUInt32BE(numObjects, 8)
411
  var checksum = createHash('sha1')
412
  var readData
413
414
  return cat([
415
    checksum(cat([
416
      pull.once(header),
417
      encodeObject
418
    ])),
419
    checksum.readDigest
420
  ])
421
422
  function encodeObject(abort, cb) {
423
    if (readData)
424
      readData(abort, function (end, data) {
425
        if (end === true)
426
          readObject(abort, nextObject)
427
        else
428
          cb(end, data)
429
      })
430
    else
431
      readObject(abort, nextObject)
432
433
    function nextObject(end, object) {
434
      if (end) return cb(end)
435
      readData = deflate(object.read)
436
      encodeTypedVarInt(object.type, object.length, cb)
437
    }
438
  }
439
}
440