git.py

   1 import os, errno, zlib, time, sha, subprocess, struct, stat, re, tempfile
   2 from helpers import *
   3
   4 verbose = 0
   5 ignore_midx = 0
   6 home_repodir = os.path.expanduser('~/.bup')
   7 repodir = None
   8
   9 _typemap =  { 'blob':3, 'tree':2, 'commit':1, 'tag':4 }
  10 _typermap = { 3:'blob', 2:'tree', 1:'commit', 4:'tag' }
  11
  12
  13 class GitError(Exception):
  14     pass
  15
  16
  17 def repo(sub = ''):
  18     global repodir
  19     if not repodir:
  20         raise GitError('You should call check_repo_or_die()')
  21     gd = os.path.join(repodir, '.git')
  22     if os.path.exists(gd):
  23         repodir = gd
  24     return os.path.join(repodir, sub)
  25
  26
  27 def _encode_packobj(type, content):
  28     szout = ''
  29     sz = len(content)
  30     szbits = (sz & 0x0f) | (_typemap[type]<<4)
  31     sz >>= 4
  32     while 1:
  33         if sz: szbits |= 0x80
  34         szout += chr(szbits)
  35         if not sz:
  36             break
  37         szbits = sz & 0x7f
  38         sz >>= 7
  39     z = zlib.compressobj(1)
  40     yield szout
  41     yield z.compress(content)
  42     yield z.flush()
  43
  44
  45 def _encode_looseobj(type, content):
  46     z = zlib.compressobj(1)
  47     yield z.compress('%s %d\0' % (type, len(content)))
  48     yield z.compress(content)
  49     yield z.flush()
  50
  51
  52 def _decode_looseobj(buf):
  53     assert(buf);
  54     s = zlib.decompress(buf)
  55     i = s.find('\0')
  56     assert(i > 0)
  57     l = s[:i].split(' ')
  58     type = l[0]
  59     sz = int(l[1])
  60     content = s[i+1:]
  61     assert(type in _typemap)
  62     assert(sz == len(content))
  63     return (type, content)
  64
  65
  66 def _decode_packobj(buf):
  67     assert(buf)
  68     c = ord(buf[0])
  69     type = _typermap[(c & 0x70) >> 4]
  70     sz = c & 0x0f
  71     shift = 4
  72     i = 0
  73     while c & 0x80:
  74         i += 1
  75         c = ord(buf[i])
  76         sz |= (c & 0x7f) << shift
  77         shift += 7
  78         if not (c & 0x80):
  79             break
  80     return (type, zlib.decompress(buf[i+1:]))
  81
  82
  83 class PackIndex:
  84     def __init__(self, filename):
  85         self.name = filename
  86         self.map = mmap_read(open(filename))
  87         assert(str(self.map[0:8]) == '\377tOc\0\0\0\2')
  88         self.fanout = list(struct.unpack('!256I',
  89                                          str(buffer(self.map, 8, 256*4))))
  90         self.fanout.append(0)  # entry "-1"
  91         nsha = self.fanout[255]
  92         self.ofstable = buffer(self.map,
  93                                8 + 256*4 + nsha*20 + nsha*4,
  94                                nsha*4)
  95         self.ofs64table = buffer(self.map,
  96                                  8 + 256*4 + nsha*20 + nsha*4 + nsha*4)
  97
  98     def _ofs_from_idx(self, idx):
  99         ofs = struct.unpack('!I', str(buffer(self.ofstable, idx*4, 4)))[0]
 100         if ofs & 0x80000000:
 101             idx64 = ofs & 0x7fffffff
 102             ofs = struct.unpack('!I',
 103                                 str(buffer(self.ofs64table, idx64*8, 8)))[0]
 104         return ofs
 105
 106     def _idx_from_hash(self, hash):
 107         assert(len(hash) == 20)
 108         b1 = ord(hash[0])
 109         start = self.fanout[b1-1] # range -1..254
 110         end = self.fanout[b1] # range 0..255
 111         buf = buffer(self.map, 8 + 256*4, end*20)
 112         want = str(hash)
 113         while start < end:
 114             mid = start + (end-start)/2
 115             v = str(buf[mid*20:(mid+1)*20])
 116             if v < want:
 117                 start = mid+1
 118             elif v > want:
 119                 end = mid
 120             else: # got it!
 121                 return mid
 122         return None
 123
 124     def find_offset(self, hash):
 125         idx = self._idx_from_hash(hash)
 126         if idx != None:
 127             return self._ofs_from_idx(idx)
 128         return None
 129
 130     def exists(self, hash):
 131         return hash and (self._idx_from_hash(hash) != None) and True or None
 132
 133     def __iter__(self):
 134         for i in xrange(self.fanout[255]):
 135             yield buffer(self.map, 8 + 256*4 + 20*i, 20)
 136
 137     def __len__(self):
 138         return self.fanout[255]
 139
 140
 141 def extract_bits(buf, bits):
 142     mask = (1<<bits) - 1
 143     v = struct.unpack('!Q', buf[0:8])[0]
 144     v = (v >> (64-bits)) & mask
 145     return v
 146
 147
 148 class PackMidx:
 149     def __init__(self, filename):
 150         self.name = filename
 151         assert(filename.endswith('.midx'))
 152         self.map = mmap_read(open(filename))
 153         assert(str(self.map[0:8]) == 'MIDX\0\0\0\1')
 154         self.bits = struct.unpack('!I', self.map[8:12])[0]
 155         self.entries = 2**self.bits
 156         self.fanout = buffer(self.map, 12, self.entries*8)
 157         shaofs = 12 + self.entries*8
 158         nsha = self._fanget(self.entries-1)
 159         self.shalist = buffer(self.map, shaofs, nsha*20)
 160         self.idxnames = str(self.map[shaofs + 20*nsha:]).split('\0')
 161
 162     def _fanget(self, i):
 163         start = i*8
 164         s = self.fanout[start:start+8]
 165         return struct.unpack('!Q', s)[0]
 166
 167     def exists(self, hash):
 168         want = str(hash)
 169         el = extract_bits(want, self.bits)
 170         if el:
 171             start = self._fanget(el-1)
 172         else:
 173             start = 0
 174         end = self._fanget(el)
 175         while start < end:
 176             mid = start + (end-start)/2
 177             v = str(self.shalist[mid*20:(mid+1)*20])
 178             if v < want:
 179                 start = mid+1
 180             elif v > want:
 181                 end = mid
 182             else: # got it!
 183                 return True
 184         return None
 185
 186     def __iter__(self):
 187         for i in xrange(self._fanget(self.entries-1)):
 188             yield buffer(self.shalist, i*20, 20)
 189
 190     def __len__(self):
 191         return self._fanget(self.entries-1)
 192
 193
 194 _mpi_count = 0
 195 class MultiPackIndex:
 196     def __init__(self, dir):
 197         global _mpi_count
 198         assert(_mpi_count == 0)
 199         _mpi_count += 1
 200         self.dir = dir
 201         self.also = {}
 202         self.packs = []
 203         self.refresh()
 204
 205     def __del__(self):
 206         global _mpi_count
 207         _mpi_count -= 1
 208         assert(_mpi_count == 0)
 209
 210     def exists(self, hash):
 211         if hash in self.also:
 212             return True
 213         for i in range(len(self.packs)):
 214             p = self.packs[i]
 215             if p.exists(hash):
 216                 # reorder so most recently used packs are searched first
 217                 self.packs = [p] + self.packs[:i] + self.packs[i+1:]
 218                 return p.name
 219         return None
 220
 221     def refresh(self):
 222         global ignore_midx
 223         d = dict([(p.name, 1) for p in self.packs])
 224         if os.path.exists(self.dir):
 225             if not ignore_midx:
 226                 midxl = []
 227                 for f in os.listdir(self.dir):
 228                     full = os.path.join(self.dir, f)
 229                     if f.endswith('.midx') and not d.get(full):
 230                         midxl.append(PackMidx(full))
 231                 midxl.sort(lambda x,y: -cmp(len(x),len(y)))
 232                 for ix in midxl:
 233                     any = 0
 234                     for sub in ix.idxnames:
 235                         if not d.get(os.path.join(self.dir, sub)):
 236                             self.packs.append(ix)
 237                             d[ix.name] = 1
 238                             for name in ix.idxnames:
 239                                 d[os.path.join(self.dir, name)] = 1
 240                             break
 241             for f in os.listdir(self.dir):
 242                 full = os.path.join(self.dir, f)
 243                 if f.endswith('.idx') and not d.get(full):
 244                     self.packs.append(PackIndex(full))
 245                     d[full] = 1
 246         #log('MultiPackIndex: using %d packs.\n' % len(self.packs))
 247
 248     def add(self, hash):
 249         self.also[hash] = 1
 250
 251     def zap_also(self):
 252         self.also = {}
 253
 254
 255 def calc_hash(type, content):
 256     header = '%s %d\0' % (type, len(content))
 257     sum = sha.sha(header)
 258     sum.update(content)
 259     return sum.digest()
 260
 261
 262 def _shalist_sort_key(ent):
 263     (mode, name, id) = ent
 264     if stat.S_ISDIR(int(mode, 8)):
 265         return name + '/'
 266     else:
 267         return name
 268
 269
 270 class PackWriter:
 271     def __init__(self, objcache_maker=None):
 272         self.count = 0
 273         self.outbytes = 0
 274         self.filename = None
 275         self.file = None
 276         self.objcache_maker = objcache_maker
 277         self.objcache = None
 278
 279     def __del__(self):
 280         self.close()
 281
 282     def _make_objcache(self):
 283         if not self.objcache:
 284             if self.objcache_maker:
 285                 self.objcache = self.objcache_maker()
 286             else:
 287                 self.objcache = MultiPackIndex(repo('objects/pack'))
 288
 289     def _open(self):
 290         if not self.file:
 291             self._make_objcache()
 292             (fd,name) = tempfile.mkstemp(suffix='.pack', dir=repo('objects'))
 293             self.file = os.fdopen(fd, 'w+b')
 294             assert(name.endswith('.pack'))
 295             self.filename = name[:-5]
 296             self.file.write('PACK\0\0\0\2\0\0\0\0')
 297
 298     def _raw_write(self, datalist):
 299         self._open()
 300         f = self.file
 301         for d in datalist:
 302             f.write(d)
 303             self.outbytes += len(d)
 304         self.count += 1
 305
 306     def _write(self, bin, type, content):
 307         if verbose:
 308             log('>')
 309         self._raw_write(_encode_packobj(type, content))
 310         return bin
 311
 312     def breakpoint(self):
 313         id = self._end()
 314         self.outbytes = self.count = 0
 315         return id
 316
 317     def write(self, type, content):
 318         return self._write(calc_hash(type, content), type, content)
 319
 320     def exists(self, id):
 321         if not self.objcache:
 322             self._make_objcache()
 323         return self.objcache.exists(id)
 324
 325     def maybe_write(self, type, content):
 326         bin = calc_hash(type, content)
 327         if not self.exists(bin):
 328             self._write(bin, type, content)
 329             self.objcache.add(bin)
 330         return bin
 331
 332     def new_blob(self, blob):
 333         return self.maybe_write('blob', blob)
 334
 335     def new_tree(self, shalist):
 336         shalist = sorted(shalist, key = _shalist_sort_key)
 337         l = []
 338         for (mode,name,bin) in shalist:
 339             assert(mode)
 340             assert(mode[0] != '0')
 341             assert(name)
 342             assert(len(bin) == 20)
 343             l.append('%s %s\0%s' % (mode,name,bin))
 344         return self.maybe_write('tree', ''.join(l))
 345
 346     def _new_commit(self, tree, parent, author, adate, committer, cdate, msg):
 347         l = []
 348         if tree: l.append('tree %s' % tree.encode('hex'))
 349         if parent: l.append('parent %s' % parent.encode('hex'))
 350         if author: l.append('author %s %s' % (author, _git_date(adate)))
 351         if committer: l.append('committer %s %s' % (committer, _git_date(cdate)))
 352         l.append('')
 353         l.append(msg)
 354         return self.maybe_write('commit', '\n'.join(l))
 355
 356     def new_commit(self, parent, tree, msg):
 357         now = time.time()
 358         userline = '%s <%s@%s>' % (userfullname(), username(), hostname())
 359         commit = self._new_commit(tree, parent,
 360                                   userline, now, userline, now,
 361                                   msg)
 362         return commit
 363
 364     def abort(self):
 365         f = self.file
 366         if f:
 367             self.file = None
 368             f.close()
 369             os.unlink(self.filename + '.pack')
 370
 371     def _end(self):
 372         f = self.file
 373         if not f: return None
 374         self.file = None
 375         self.objcache = None
 376
 377         # update object count
 378         f.seek(8)
 379         cp = struct.pack('!i', self.count)
 380         assert(len(cp) == 4)
 381         f.write(cp)
 382
 383         # calculate the pack sha1sum
 384         f.seek(0)
 385         sum = sha.sha()
 386         while 1:
 387             b = f.read(65536)
 388             sum.update(b)
 389             if not b: break
 390         f.write(sum.digest())
 391
 392         f.close()
 393
 394         p = subprocess.Popen(['git', 'index-pack', '-v',
 395                               '--index-version=2',
 396                               self.filename + '.pack'],
 397                              preexec_fn = _gitenv,
 398                              stdout = subprocess.PIPE)
 399         out = p.stdout.read().strip()
 400         _git_wait('git index-pack', p)
 401         if not out:
 402             raise GitError('git index-pack produced no output')
 403         nameprefix = repo('objects/pack/%s' % out)
 404         if os.path.exists(self.filename + '.map'):
 405             os.unlink(self.filename + '.map')
 406         os.rename(self.filename + '.pack', nameprefix + '.pack')
 407         os.rename(self.filename + '.idx', nameprefix + '.idx')
 408         return nameprefix
 409
 410     def close(self):
 411         return self._end()
 412
 413
 414 def _git_date(date):
 415     return time.strftime('%s %z', time.localtime(date))
 416
 417
 418 def _gitenv():
 419     os.environ['GIT_DIR'] = os.path.abspath(repo())
 420
 421
 422 def list_refs(refname = None):
 423     argv = ['git', 'show-ref', '--']
 424     if refname:
 425         argv += [refname]
 426     p = subprocess.Popen(argv, preexec_fn = _gitenv, stdout = subprocess.PIPE)
 427     out = p.stdout.read().strip()
 428     rv = p.wait()  # not fatal
 429     if rv:
 430         assert(not out)
 431     if out:
 432         for d in out.split('\n'):
 433             (sha, name) = d.split(' ', 1)
 434             yield (name, sha.decode('hex'))
 435
 436
 437 def read_ref(refname):
 438     l = list(list_refs(refname))
 439     if l:
 440         assert(len(l) == 1)
 441         return l[0][1]
 442     else:
 443         return None
 444
 445
 446 def rev_list(ref):
 447     assert(not ref.startswith('-'))
 448     argv = ['git', 'rev-list', '--pretty=format:%ct', ref, '--']
 449     p = subprocess.Popen(argv, preexec_fn = _gitenv, stdout = subprocess.PIPE)
 450     commit = None
 451     for row in p.stdout:
 452         s = row.strip()
 453         if s.startswith('commit '):
 454             commit = s[7:].decode('hex')
 455         else:
 456             date = int(s)
 457             yield (date, commit)
 458     rv = p.wait()  # not fatal
 459     if rv:
 460         raise GitError, 'git rev-list returned error %d' % rv
 461
 462
 463 def update_ref(refname, newval, oldval):
 464     if not oldval:
 465         oldval = ''
 466     assert(refname.startswith('refs/heads/'))
 467     p = subprocess.Popen(['git', 'update-ref', refname,
 468                           newval.encode('hex'), oldval.encode('hex')],
 469                          preexec_fn = _gitenv)
 470     _git_wait('git update-ref', p)
 471
 472
 473 def guess_repo(path=None):
 474     global repodir
 475     if path:
 476         repodir = path
 477     if not repodir:
 478         repodir = os.environ.get('BUP_DIR')
 479         if not repodir:
 480             repodir = os.path.expanduser('~/.bup')
 481
 482
 483 def init_repo(path=None):
 484     guess_repo(path)
 485     d = repo()
 486     if os.path.exists(d) and not os.path.isdir(os.path.join(d, '.')):
 487         raise GitError('"%d" exists but is not a directory\n' % d)
 488     p = subprocess.Popen(['git', '--bare', 'init'], stdout=sys.stderr,
 489                          preexec_fn = _gitenv)
 490     _git_wait('git init', p)
 491     p = subprocess.Popen(['git', 'config', 'pack.indexVersion', '2'],
 492                          stdout=sys.stderr, preexec_fn = _gitenv)
 493     _git_wait('git config', p)
 494
 495
 496 def check_repo_or_die(path=None):
 497     guess_repo(path)
 498     if not os.path.isdir(repo('objects/pack/.')):
 499         if repodir == home_repodir:
 500             init_repo()
 501         else:
 502             log('error: %r is not a bup/git repository\n' % repo())
 503             sys.exit(15)
 504
 505
 506 def _treeparse(buf):
 507     ofs = 0
 508     while ofs < len(buf):
 509         z = buf[ofs:].find('\0')
 510         assert(z > 0)
 511         spl = buf[ofs:ofs+z].split(' ', 1)
 512         assert(len(spl) == 2)
 513         sha = buf[ofs+z+1:ofs+z+1+20]
 514         ofs += z+1+20
 515         yield (spl[0], spl[1], sha)
 516
 517
 518 _ver = None
 519 def ver():
 520     global _ver
 521     if not _ver:
 522         p = subprocess.Popen(['git', '--version'],
 523                              stdout=subprocess.PIPE)
 524         gvs = p.stdout.read()
 525         _git_wait('git --version', p)
 526         m = re.match(r'git version (\S+.\S+)', gvs)
 527         if not m:
 528             raise GitError('git --version weird output: %r' % gvs)
 529         _ver = tuple(m.group(1).split('.'))
 530     needed = ('1','5', '3', '1')
 531     if _ver < needed:
 532         raise GitError('git version %s or higher is required; you have %s'
 533                        % ('.'.join(needed), '.'.join(_ver)))
 534     return _ver
 535
 536
 537 def _git_wait(cmd, p):
 538     rv = p.wait()
 539     if rv != 0:
 540         raise GitError('%s returned %d' % (cmd, rv))
 541
 542
 543 def _git_capture(argv):
 544     p = subprocess.Popen(argv, stdout=subprocess.PIPE, preexec_fn = _gitenv)
 545     r = p.stdout.read()
 546     _git_wait(repr(argv), p)
 547     return r
 548
 549
 550 _ver_warned = 0
 551 class CatPipe:
 552     def __init__(self):
 553         global _ver_warned
 554         wanted = ('1','5','6')
 555         if ver() < wanted:
 556             if not _ver_warned:
 557                 log('warning: git version < %s; bup will be slow.\n'
 558                     % '.'.join(wanted))
 559                 _ver_warned = 1
 560             self.get = self._slow_get
 561         else:
 562             self.p = subprocess.Popen(['git', 'cat-file', '--batch'],
 563                                       stdin=subprocess.PIPE,
 564                                       stdout=subprocess.PIPE,
 565                                       preexec_fn = _gitenv)
 566             self.get = self._fast_get
 567
 568     def _fast_get(self, id):
 569         assert(id.find('\n') < 0)
 570         assert(id.find('\r') < 0)
 571         assert(id[0] != '-')
 572         self.p.stdin.write('%s\n' % id)
 573         hdr = self.p.stdout.readline()
 574         if hdr.endswith(' missing\n'):
 575             raise KeyError('blob %r is missing' % id)
 576         spl = hdr.split(' ')
 577         if len(spl) != 3 or len(spl[0]) != 40:
 578             raise GitError('expected blob, got %r' % spl)
 579         (hex, type, size) = spl
 580         it = iter(chunkyreader(self.p.stdout, int(spl[2])))
 581         try:
 582             yield type
 583             for blob in it:
 584                 yield blob
 585         except StopIteration:
 586             while 1:
 587                 it.next()
 588         assert(self.p.stdout.readline() == '\n')
 589
 590     def _slow_get(self, id):
 591         assert(id.find('\n') < 0)
 592         assert(id.find('\r') < 0)
 593         assert(id[0] != '-')
 594         type = _git_capture(['git', 'cat-file', '-t', id]).strip()
 595         yield type
 596
 597         p = subprocess.Popen(['git', 'cat-file', type, id],
 598                              stdout=subprocess.PIPE,
 599                              preexec_fn = _gitenv)
 600         for blob in chunkyreader(p.stdout):
 601             yield blob
 602         _git_wait('git cat-file', p)
 603
 604     def _join(self, it):
 605         type = it.next()
 606         if type == 'blob':
 607             for blob in it:
 608                 yield blob
 609         elif type == 'tree':
 610             treefile = ''.join(it)
 611             for (mode, name, sha) in _treeparse(treefile):
 612                 for blob in self.join(sha.encode('hex')):
 613                     yield blob
 614         elif type == 'commit':
 615             treeline = ''.join(it).split('\n')[0]
 616             assert(treeline.startswith('tree '))
 617             for blob in self.join(treeline[5:]):
 618                 yield blob
 619         else:
 620             raise GitError('invalid object type %r: expected blob/tree/commit'
 621                            % type)
 622
 623     def join(self, id):
 624         for d in self._join(self.get(id)):
 625             yield d
 626
 627
 628 def cat(id):
 629     c = CatPipe()
 630     for d in c.join(id):
 631         yield d