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