lib/bup/git.py

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