lib/bup/git.py

   1 """Git interaction library.
   2 bup repositories are in Git format. This library allows us to
   3 interact with the Git data structures.
   4 """
   5
   6 from __future__ import absolute_import, print_function
   7 import errno, os, sys, zlib, time, subprocess, struct, stat, re, tempfile, glob
   8 from array import array
   9 from binascii import hexlify, unhexlify
  10 from collections import namedtuple
  11 from itertools import islice
  12 from numbers import Integral
  13
  14 from bup import _helpers, compat, hashsplit, path, midx, bloom, xstat
  15 from bup.compat import (buffer,
  16                         byte_int, bytes_from_byte, bytes_from_uint,
  17                         environ,
  18                         items,
  19                         range,
  20                         reraise)
  21 from bup.io import path_msg
  22 from bup.helpers import (Sha1, add_error, chunkyreader, debug1, debug2,
  23                          exo,
  24                          fdatasync,
  25                          hostname, localtime, log,
  26                          merge_dict,
  27                          merge_iter,
  28                          mmap_read, mmap_readwrite,
  29                          parse_num,
  30                          progress, qprogress, stat_if_exists,
  31                          unlink,
  32                          utc_offset_str)
  33 from bup.pwdgrp import username, userfullname
  34
  35
  36 verbose = 0
  37 repodir = None  # The default repository, once initialized
  38
  39 _typemap =  {b'blob': 3, b'tree': 2, b'commit': 1, b'tag': 4}
  40 _typermap = {v: k for k, v in items(_typemap)}
  41
  42
  43 _total_searches = 0
  44 _total_steps = 0
  45
  46
  47 class GitError(Exception):
  48     pass
  49
  50
  51 def _gitenv(repo_dir=None):
  52     if not repo_dir:
  53         repo_dir = repo()
  54     return merge_dict(environ, {b'GIT_DIR': os.path.abspath(repo_dir)})
  55
  56 def _git_wait(cmd, p):
  57     rv = p.wait()
  58     if rv != 0:
  59         raise GitError('%r returned %d' % (cmd, rv))
  60
  61 def _git_exo(cmd, **kwargs):
  62     kwargs['check'] = False
  63     result = exo(cmd, **kwargs)
  64     _, _, proc = result
  65     if proc.returncode != 0:
  66         raise GitError('%r returned %d' % (cmd, proc.returncode))
  67     return result
  68
  69 def git_config_get(option, repo_dir=None):
  70     cmd = (b'git', b'config', b'--get', option)
  71     p = subprocess.Popen(cmd, stdout=subprocess.PIPE,
  72                          env=_gitenv(repo_dir=repo_dir),
  73                          close_fds=True)
  74     r = p.stdout.read()
  75     rc = p.wait()
  76     if rc == 0:
  77         return r
  78     if rc != 1:
  79         raise GitError('%r returned %d' % (cmd, rc))
  80     return None
  81
  82
  83 def parse_tz_offset(s):
  84     """UTC offset in seconds."""
  85     tz_off = (int(s[1:3]) * 60 * 60) + (int(s[3:5]) * 60)
  86     if bytes_from_byte(s[0]) == b'-':
  87         return - tz_off
  88     return tz_off
  89
  90
  91 # FIXME: derived from http://git.rsbx.net/Documents/Git_Data_Formats.txt
  92 # Make sure that's authoritative.
  93 _start_end_char = br'[^ .,:;<>"\'\0\n]'
  94 _content_char = br'[^\0\n<>]'
  95 _safe_str_rx = br'(?:%s{1,2}|(?:%s%s*%s))' \
  96     % (_start_end_char,
  97        _start_end_char, _content_char, _start_end_char)
  98 _tz_rx = br'[-+]\d\d[0-5]\d'
  99 _parent_rx = br'(?:parent [abcdefABCDEF0123456789]{40}\n)'
 100 # Assumes every following line starting with a space is part of the
 101 # mergetag.  Is there a formal commit blob spec?
 102 _mergetag_rx = br'(?:\nmergetag object [abcdefABCDEF0123456789]{40}(?:\n [^\0\n]*)*)'
 103 _commit_rx = re.compile(br'''tree (?P<tree>[abcdefABCDEF0123456789]{40})
 104 (?P<parents>%s*)author (?P<author_name>%s) <(?P<author_mail>%s)> (?P<asec>\d+) (?P<atz>%s)
 105 committer (?P<committer_name>%s) <(?P<committer_mail>%s)> (?P<csec>\d+) (?P<ctz>%s)(?P<mergetag>%s?)
 106
 107 (?P<message>(?:.|\n)*)''' % (_parent_rx,
 108                              _safe_str_rx, _safe_str_rx, _tz_rx,
 109                              _safe_str_rx, _safe_str_rx, _tz_rx,
 110                              _mergetag_rx))
 111 _parent_hash_rx = re.compile(br'\s*parent ([abcdefABCDEF0123456789]{40})\s*')
 112
 113 # Note that the author_sec and committer_sec values are (UTC) epoch
 114 # seconds, and for now the mergetag is not included.
 115 CommitInfo = namedtuple('CommitInfo', ['tree', 'parents',
 116                                        'author_name', 'author_mail',
 117                                        'author_sec', 'author_offset',
 118                                        'committer_name', 'committer_mail',
 119                                        'committer_sec', 'committer_offset',
 120                                        'message'])
 121
 122 def parse_commit(content):
 123     commit_match = re.match(_commit_rx, content)
 124     if not commit_match:
 125         raise Exception('cannot parse commit %r' % content)
 126     matches = commit_match.groupdict()
 127     return CommitInfo(tree=matches['tree'],
 128                       parents=re.findall(_parent_hash_rx, matches['parents']),
 129                       author_name=matches['author_name'],
 130                       author_mail=matches['author_mail'],
 131                       author_sec=int(matches['asec']),
 132                       author_offset=parse_tz_offset(matches['atz']),
 133                       committer_name=matches['committer_name'],
 134                       committer_mail=matches['committer_mail'],
 135                       committer_sec=int(matches['csec']),
 136                       committer_offset=parse_tz_offset(matches['ctz']),
 137                       message=matches['message'])
 138
 139
 140 def get_cat_data(cat_iterator, expected_type):
 141     _, kind, _ = next(cat_iterator)
 142     if kind != expected_type:
 143         raise Exception('expected %r, saw %r' % (expected_type, kind))
 144     return b''.join(cat_iterator)
 145
 146 def get_commit_items(id, cp):
 147     return parse_commit(get_cat_data(cp.get(id), b'commit'))
 148
 149 def _local_git_date_str(epoch_sec):
 150     return b'%d %s' % (epoch_sec, utc_offset_str(epoch_sec))
 151
 152
 153 def _git_date_str(epoch_sec, tz_offset_sec):
 154     offs =  tz_offset_sec // 60
 155     return b'%d %s%02d%02d' \
 156         % (epoch_sec,
 157            b'+' if offs >= 0 else b'-',
 158            abs(offs) // 60,
 159            abs(offs) % 60)
 160
 161
 162 def repo(sub = b'', repo_dir=None):
 163     """Get the path to the git repository or one of its subdirectories."""
 164     repo_dir = repo_dir or repodir
 165     if not repo_dir:
 166         raise GitError('You should call check_repo_or_die()')
 167
 168     # If there's a .git subdirectory, then the actual repo is in there.
 169     gd = os.path.join(repo_dir, b'.git')
 170     if os.path.exists(gd):
 171         repo_dir = gd
 172
 173     return os.path.join(repo_dir, sub)
 174
 175
 176 _shorten_hash_rx = \
 177     re.compile(br'([^0-9a-z]|\b)([0-9a-z]{7})[0-9a-z]{33}([^0-9a-z]|\b)')
 178
 179 def shorten_hash(s):
 180     return _shorten_hash_rx.sub(br'\1\2*\3', s)
 181
 182
 183 def repo_rel(path):
 184     full = os.path.abspath(path)
 185     fullrepo = os.path.abspath(repo(b''))
 186     if not fullrepo.endswith(b'/'):
 187         fullrepo += b'/'
 188     if full.startswith(fullrepo):
 189         path = full[len(fullrepo):]
 190     if path.startswith(b'index-cache/'):
 191         path = path[len(b'index-cache/'):]
 192     return shorten_hash(path)
 193
 194
 195 def auto_midx(objdir):
 196     args = [path.exe(), b'midx', b'--auto', b'--dir', objdir]
 197     try:
 198         rv = subprocess.call(args, stdout=open(os.devnull, 'w'))
 199     except OSError as e:
 200         # make sure 'args' gets printed to help with debugging
 201         add_error('%r: exception: %s' % (args, e))
 202         raise
 203     if rv:
 204         add_error('%r: returned %d' % (args, rv))
 205
 206     args = [path.exe(), b'bloom', b'--dir', objdir]
 207     try:
 208         rv = subprocess.call(args, stdout=open(os.devnull, 'w'))
 209     except OSError as e:
 210         # make sure 'args' gets printed to help with debugging
 211         add_error('%r: exception: %s' % (args, e))
 212         raise
 213     if rv:
 214         add_error('%r: returned %d' % (args, rv))
 215
 216
 217 def mangle_name(name, mode, gitmode):
 218     """Mangle a file name to present an abstract name for segmented files.
 219     Mangled file names will have the ".bup" extension added to them. If a
 220     file's name already ends with ".bup", a ".bupl" extension is added to
 221     disambiguate normal files from segmented ones.
 222     """
 223     if stat.S_ISREG(mode) and not stat.S_ISREG(gitmode):
 224         assert(stat.S_ISDIR(gitmode))
 225         return name + b'.bup'
 226     elif name.endswith(b'.bup') or name[:-1].endswith(b'.bup'):
 227         return name + b'.bupl'
 228     else:
 229         return name
 230
 231
 232 (BUP_NORMAL, BUP_CHUNKED) = (0,1)
 233 def demangle_name(name, mode):
 234     """Remove name mangling from a file name, if necessary.
 235
 236     The return value is a tuple (demangled_filename,mode), where mode is one of
 237     the following:
 238
 239     * BUP_NORMAL  : files that should be read as-is from the repository
 240     * BUP_CHUNKED : files that were chunked and need to be reassembled
 241
 242     For more information on the name mangling algorithm, see mangle_name()
 243     """
 244     if name.endswith(b'.bupl'):
 245         return (name[:-5], BUP_NORMAL)
 246     elif name.endswith(b'.bup'):
 247         return (name[:-4], BUP_CHUNKED)
 248     elif name.endswith(b'.bupm'):
 249         return (name[:-5],
 250                 BUP_CHUNKED if stat.S_ISDIR(mode) else BUP_NORMAL)
 251     else:
 252         return (name, BUP_NORMAL)
 253
 254
 255 def calc_hash(type, content):
 256     """Calculate some content's hash in the Git fashion."""
 257     header = b'%s %d\0' % (type, len(content))
 258     sum = Sha1(header)
 259     sum.update(content)
 260     return sum.digest()
 261
 262
 263 def shalist_item_sort_key(ent):
 264     (mode, name, id) = ent
 265     assert(mode+0 == mode)
 266     if stat.S_ISDIR(mode):
 267         return name + b'/'
 268     else:
 269         return name
 270
 271
 272 def tree_encode(shalist):
 273     """Generate a git tree object from (mode,name,hash) tuples."""
 274     shalist = sorted(shalist, key = shalist_item_sort_key)
 275     l = []
 276     for (mode,name,bin) in shalist:
 277         assert(mode)
 278         assert(mode+0 == mode)
 279         assert(name)
 280         assert(len(bin) == 20)
 281         s = b'%o %s\0%s' % (mode,name,bin)
 282         assert s[0] != b'0'  # 0-padded octal is not acceptable in a git tree
 283         l.append(s)
 284     return b''.join(l)
 285
 286
 287 def tree_decode(buf):
 288     """Generate a list of (mode,name,hash) from the git tree object in buf."""
 289     ofs = 0
 290     while ofs < len(buf):
 291         z = buf.find(b'\0', ofs)
 292         assert(z > ofs)
 293         spl = buf[ofs:z].split(b' ', 1)
 294         assert(len(spl) == 2)
 295         mode,name = spl
 296         sha = buf[z+1:z+1+20]
 297         ofs = z+1+20
 298         yield (int(mode, 8), name, sha)
 299
 300
 301 def _encode_packobj(type, content, compression_level=1):
 302     if compression_level not in (0, 1, 2, 3, 4, 5, 6, 7, 8, 9):
 303         raise ValueError('invalid compression level %s' % compression_level)
 304     szout = b''
 305     sz = len(content)
 306     szbits = (sz & 0x0f) | (_typemap[type]<<4)
 307     sz >>= 4
 308     while 1:
 309         if sz: szbits |= 0x80
 310         szout += bytes_from_uint(szbits)
 311         if not sz:
 312             break
 313         szbits = sz & 0x7f
 314         sz >>= 7
 315     z = zlib.compressobj(compression_level)
 316     yield szout
 317     yield z.compress(content)
 318     yield z.flush()
 319
 320
 321 def _encode_looseobj(type, content, compression_level=1):
 322     z = zlib.compressobj(compression_level)
 323     yield z.compress(b'%s %d\0' % (type, len(content)))
 324     yield z.compress(content)
 325     yield z.flush()
 326
 327
 328 def _decode_looseobj(buf):
 329     assert(buf);
 330     s = zlib.decompress(buf)
 331     i = s.find(b'\0')
 332     assert(i > 0)
 333     l = s[:i].split(b' ')
 334     type = l[0]
 335     sz = int(l[1])
 336     content = s[i+1:]
 337     assert(type in _typemap)
 338     assert(sz == len(content))
 339     return (type, content)
 340
 341
 342 def _decode_packobj(buf):
 343     assert(buf)
 344     c = byte_int(buf[0])
 345     type = _typermap[(c & 0x70) >> 4]
 346     sz = c & 0x0f
 347     shift = 4
 348     i = 0
 349     while c & 0x80:
 350         i += 1
 351         c = byte_int(buf[i])
 352         sz |= (c & 0x7f) << shift
 353         shift += 7
 354         if not (c & 0x80):
 355             break
 356     return (type, zlib.decompress(buf[i+1:]))
 357
 358
 359 class PackIdx:
 360     def __init__(self):
 361         assert(0)
 362
 363     def find_offset(self, hash):
 364         """Get the offset of an object inside the index file."""
 365         idx = self._idx_from_hash(hash)
 366         if idx != None:
 367             return self._ofs_from_idx(idx)
 368         return None
 369
 370     def exists(self, hash, want_source=False):
 371         """Return nonempty if the object exists in this index."""
 372         if hash and (self._idx_from_hash(hash) != None):
 373             return want_source and os.path.basename(self.name) or True
 374         return None
 375
 376     def _idx_from_hash(self, hash):
 377         global _total_searches, _total_steps
 378         _total_searches += 1
 379         assert(len(hash) == 20)
 380         b1 = byte_int(hash[0])
 381         start = self.fanout[b1-1] # range -1..254
 382         end = self.fanout[b1] # range 0..255
 383         want = hash
 384         _total_steps += 1  # lookup table is a step
 385         while start < end:
 386             _total_steps += 1
 387             mid = start + (end - start) // 2
 388             v = self._idx_to_hash(mid)
 389             if v < want:
 390                 start = mid+1
 391             elif v > want:
 392                 end = mid
 393             else: # got it!
 394                 return mid
 395         return None
 396
 397
 398 class PackIdxV1(PackIdx):
 399     """Object representation of a Git pack index (version 1) file."""
 400     def __init__(self, filename, f):
 401         self.name = filename
 402         self.idxnames = [self.name]
 403         self.map = mmap_read(f)
 404         # Min size for 'L' is 4, which is sufficient for struct's '!I'
 405         self.fanout = array('L', struct.unpack('!256I', self.map))
 406         self.fanout.append(0)  # entry "-1"
 407         self.nsha = self.fanout[255]
 408         self.sha_ofs = 256 * 4
 409         # Avoid slicing shatable for individual hashes (very high overhead)
 410         self.shatable = buffer(self.map, self.sha_ofs, self.nsha * 24)
 411
 412     def __enter__(self):
 413         return self
 414
 415     def __exit__(self, type, value, traceback):
 416         self.close()
 417
 418     def __len__(self):
 419         return int(self.nsha)  # int() from long for python 2
 420
 421     def _ofs_from_idx(self, idx):
 422         if idx >= self.nsha or idx < 0:
 423             raise IndexError('invalid pack index index %d' % idx)
 424         ofs = self.sha_ofs + idx * 24
 425         return struct.unpack_from('!I', self.map, offset=ofs)[0]
 426
 427     def _idx_to_hash(self, idx):
 428         if idx >= self.nsha or idx < 0:
 429             raise IndexError('invalid pack index index %d' % idx)
 430         ofs = self.sha_ofs + idx * 24 + 4
 431         return self.map[ofs : ofs + 20]
 432
 433     def __iter__(self):
 434         start = self.sha_ofs + 4
 435         for ofs in range(start, start + 24 * self.nsha, 24):
 436             yield self.map[ofs : ofs + 20]
 437
 438     def close(self):
 439         if self.map is not None:
 440             self.shatable = None
 441             self.map.close()
 442             self.map = None
 443
 444
 445 class PackIdxV2(PackIdx):
 446     """Object representation of a Git pack index (version 2) file."""
 447     def __init__(self, filename, f):
 448         self.name = filename
 449         self.idxnames = [self.name]
 450         self.map = mmap_read(f)
 451         assert self.map[0:8] == b'\377tOc\0\0\0\2'
 452         # Min size for 'L' is 4, which is sufficient for struct's '!I'
 453         self.fanout = array('L', struct.unpack_from('!256I', self.map, offset=8))
 454         self.fanout.append(0)
 455         self.nsha = self.fanout[255]
 456         self.sha_ofs = 8 + 256*4
 457         self.ofstable_ofs = self.sha_ofs + self.nsha * 20 + self.nsha * 4
 458         self.ofs64table_ofs = self.ofstable_ofs + self.nsha * 4
 459         # Avoid slicing this for individual hashes (very high overhead)
 460         self.shatable = buffer(self.map, self.sha_ofs, self.nsha*20)
 461
 462     def __enter__(self):
 463         return self
 464
 465     def __exit__(self, type, value, traceback):
 466         self.close()
 467
 468     def __len__(self):
 469         return int(self.nsha)  # int() from long for python 2
 470
 471     def _ofs_from_idx(self, idx):
 472         if idx >= self.nsha or idx < 0:
 473             raise IndexError('invalid pack index index %d' % idx)
 474         ofs_ofs = self.ofstable_ofs + idx * 4
 475         ofs = struct.unpack_from('!I', self.map, offset=ofs_ofs)[0]
 476         if ofs & 0x80000000:
 477             idx64 = ofs & 0x7fffffff
 478             ofs64_ofs = self.ofs64table_ofs + idx64 * 8
 479             ofs = struct.unpack_from('!Q', self.map, offset=ofs64_ofs)[0]
 480         return ofs
 481
 482     def _idx_to_hash(self, idx):
 483         if idx >= self.nsha or idx < 0:
 484             raise IndexError('invalid pack index index %d' % idx)
 485         ofs = self.sha_ofs + idx * 20
 486         return self.map[ofs : ofs + 20]
 487
 488     def __iter__(self):
 489         start = self.sha_ofs
 490         for ofs in range(start, start + 20 * self.nsha, 20):
 491             yield self.map[ofs : ofs + 20]
 492
 493     def close(self):
 494         if self.map is not None:
 495             self.shatable = None
 496             self.map.close()
 497             self.map = None
 498
 499
 500 _mpi_count = 0
 501 class PackIdxList:
 502     def __init__(self, dir, ignore_midx=False):
 503         global _mpi_count
 504         assert(_mpi_count == 0) # these things suck tons of VM; don't waste it
 505         _mpi_count += 1
 506         self.dir = dir
 507         self.also = set()
 508         self.packs = []
 509         self.do_bloom = False
 510         self.bloom = None
 511         self.ignore_midx = ignore_midx
 512         self.refresh()
 513
 514     def __del__(self):
 515         global _mpi_count
 516         _mpi_count -= 1
 517         assert(_mpi_count == 0)
 518
 519     def __iter__(self):
 520         return iter(idxmerge(self.packs))
 521
 522     def __len__(self):
 523         return sum(len(pack) for pack in self.packs)
 524
 525     def exists(self, hash, want_source=False):
 526         """Return nonempty if the object exists in the index files."""
 527         global _total_searches
 528         _total_searches += 1
 529         if hash in self.also:
 530             return True
 531         if self.do_bloom and self.bloom:
 532             if self.bloom.exists(hash):
 533                 self.do_bloom = False
 534             else:
 535                 _total_searches -= 1  # was counted by bloom
 536                 return None
 537         for i in range(len(self.packs)):
 538             p = self.packs[i]
 539             _total_searches -= 1  # will be incremented by sub-pack
 540             ix = p.exists(hash, want_source=want_source)
 541             if ix:
 542                 # reorder so most recently used packs are searched first
 543                 self.packs = [p] + self.packs[:i] + self.packs[i+1:]
 544                 return ix
 545         self.do_bloom = True
 546         return None
 547
 548     def refresh(self, skip_midx = False):
 549         """Refresh the index list.
 550         This method verifies if .midx files were superseded (e.g. all of its
 551         contents are in another, bigger .midx file) and removes the superseded
 552         files.
 553
 554         If skip_midx is True, all work on .midx files will be skipped and .midx
 555         files will be removed from the list.
 556
 557         The instance variable 'ignore_midx' can force this function to
 558         always act as if skip_midx was True.
 559         """
 560         if self.bloom is not None:
 561             self.bloom.close()
 562         self.bloom = None # Always reopen the bloom as it may have been relaced
 563         self.do_bloom = False
 564         skip_midx = skip_midx or self.ignore_midx
 565         d = dict((p.name, p) for p in self.packs
 566                  if not skip_midx or not isinstance(p, midx.PackMidx))
 567         if os.path.exists(self.dir):
 568             if not skip_midx:
 569                 midxl = []
 570                 midxes = set(glob.glob(os.path.join(self.dir, b'*.midx')))
 571                 # remove any *.midx files from our list that no longer exist
 572                 for ix in list(d.values()):
 573                     if not isinstance(ix, midx.PackMidx):
 574                         continue
 575                     if ix.name in midxes:
 576                         continue
 577                     # remove the midx
 578                     del d[ix.name]
 579                     ix.close()
 580                     self.packs.remove(ix)
 581                 for ix in self.packs:
 582                     if isinstance(ix, midx.PackMidx):
 583                         for name in ix.idxnames:
 584                             d[os.path.join(self.dir, name)] = ix
 585                 for full in midxes:
 586                     if not d.get(full):
 587                         mx = midx.PackMidx(full)
 588                         (mxd, mxf) = os.path.split(mx.name)
 589                         broken = False
 590                         for n in mx.idxnames:
 591                             if not os.path.exists(os.path.join(mxd, n)):
 592                                 log(('warning: index %s missing\n'
 593                                      '  used by %s\n')
 594                                     % (path_msg(n), path_msg(mxf)))
 595                                 broken = True
 596                         if broken:
 597                             mx.close()
 598                             del mx
 599                             unlink(full)
 600                         else:
 601                             midxl.append(mx)
 602                 midxl.sort(key=lambda ix:
 603                            (-len(ix), -xstat.stat(ix.name).st_mtime))
 604                 for ix in midxl:
 605                     any_needed = False
 606                     for sub in ix.idxnames:
 607                         found = d.get(os.path.join(self.dir, sub))
 608                         if not found or isinstance(found, PackIdx):
 609                             # doesn't exist, or exists but not in a midx
 610                             any_needed = True
 611                             break
 612                     if any_needed:
 613                         d[ix.name] = ix
 614                         for name in ix.idxnames:
 615                             d[os.path.join(self.dir, name)] = ix
 616                     elif not ix.force_keep:
 617                         debug1('midx: removing redundant: %s\n'
 618                                % path_msg(os.path.basename(ix.name)))
 619                         ix.close()
 620                         unlink(ix.name)
 621             for full in glob.glob(os.path.join(self.dir, b'*.idx')):
 622                 if not d.get(full):
 623                     try:
 624                         ix = open_idx(full)
 625                     except GitError as e:
 626                         add_error(e)
 627                         continue
 628                     d[full] = ix
 629             bfull = os.path.join(self.dir, b'bup.bloom')
 630             if self.bloom is None and os.path.exists(bfull):
 631                 self.bloom = bloom.ShaBloom(bfull)
 632             self.packs = list(set(d.values()))
 633             self.packs.sort(reverse=True, key=lambda x: len(x))
 634             if self.bloom and self.bloom.valid() and len(self.bloom) >= len(self):
 635                 self.do_bloom = True
 636             else:
 637                 self.bloom = None
 638         debug1('PackIdxList: using %d index%s.\n'
 639             % (len(self.packs), len(self.packs)!=1 and 'es' or ''))
 640
 641     def add(self, hash):
 642         """Insert an additional object in the list."""
 643         self.also.add(hash)
 644
 645
 646 def open_idx(filename):
 647     if filename.endswith(b'.idx'):
 648         f = open(filename, 'rb')
 649         header = f.read(8)
 650         if header[0:4] == b'\377tOc':
 651             version = struct.unpack('!I', header[4:8])[0]
 652             if version == 2:
 653                 return PackIdxV2(filename, f)
 654             else:
 655                 raise GitError('%s: expected idx file version 2, got %d'
 656                                % (path_msg(filename), version))
 657         elif len(header) == 8 and header[0:4] < b'\377tOc':
 658             return PackIdxV1(filename, f)
 659         else:
 660             raise GitError('%s: unrecognized idx file header'
 661                            % path_msg(filename))
 662     elif filename.endswith(b'.midx'):
 663         return midx.PackMidx(filename)
 664     else:
 665         raise GitError('idx filenames must end with .idx or .midx')
 666
 667
 668 def idxmerge(idxlist, final_progress=True):
 669     """Generate a list of all the objects reachable in a PackIdxList."""
 670     def pfunc(count, total):
 671         qprogress('Reading indexes: %.2f%% (%d/%d)\r'
 672                   % (count*100.0/total, count, total))
 673     def pfinal(count, total):
 674         if final_progress:
 675             progress('Reading indexes: %.2f%% (%d/%d), done.\n'
 676                      % (100, total, total))
 677     return merge_iter(idxlist, 10024, pfunc, pfinal)
 678
 679
 680 def _make_objcache():
 681     return PackIdxList(repo(b'objects/pack'))
 682
 683 # bup-gc assumes that it can disable all PackWriter activities
 684 # (bloom/midx/cache) via the constructor and close() arguments.
 685
 686 class PackWriter:
 687     """Writes Git objects inside a pack file."""
 688     def __init__(self, objcache_maker=_make_objcache, compression_level=1,
 689                  run_midx=True, on_pack_finish=None,
 690                  max_pack_size=None, max_pack_objects=None, repo_dir=None):
 691         self.repo_dir = repo_dir or repo()
 692         self.file = None
 693         self.parentfd = None
 694         self.count = 0
 695         self.outbytes = 0
 696         self.filename = None
 697         self.idx = None
 698         self.objcache_maker = objcache_maker
 699         self.objcache = None
 700         self.compression_level = compression_level
 701         self.run_midx=run_midx
 702         self.on_pack_finish = on_pack_finish
 703         if not max_pack_size:
 704             max_pack_size = git_config_get(b'pack.packSizeLimit',
 705                                            repo_dir=self.repo_dir)
 706             if max_pack_size is not None:
 707                 max_pack_size = parse_num(max_pack_size)
 708             if not max_pack_size:
 709                 # larger packs slow down pruning
 710                 max_pack_size = 1000 * 1000 * 1000
 711         self.max_pack_size = max_pack_size
 712         # cache memory usage is about 83 bytes per object
 713         self.max_pack_objects = max_pack_objects if max_pack_objects \
 714                                 else max(1, self.max_pack_size // 5000)
 715
 716     def __del__(self):
 717         self.close()
 718
 719     def __enter__(self):
 720         return self
 721
 722     def __exit__(self, type, value, traceback):
 723         self.close()
 724
 725     def _open(self):
 726         if not self.file:
 727             objdir = dir = os.path.join(self.repo_dir, b'objects')
 728             fd, name = tempfile.mkstemp(suffix=b'.pack', dir=objdir)
 729             try:
 730                 self.file = os.fdopen(fd, 'w+b')
 731             except:
 732                 os.close(fd)
 733                 raise
 734             try:
 735                 self.parentfd = os.open(objdir, os.O_RDONLY)
 736             except:
 737                 f = self.file
 738                 self.file = None
 739                 f.close()
 740                 raise
 741             assert name.endswith(b'.pack')
 742             self.filename = name[:-5]
 743             self.file.write(b'PACK\0\0\0\2\0\0\0\0')
 744             self.idx = PackIdxV2Writer()
 745
 746     def _raw_write(self, datalist, sha):
 747         self._open()
 748         f = self.file
 749         # in case we get interrupted (eg. KeyboardInterrupt), it's best if
 750         # the file never has a *partial* blob.  So let's make sure it's
 751         # all-or-nothing.  (The blob shouldn't be very big anyway, thanks
 752         # to our hashsplit algorithm.)  f.write() does its own buffering,
 753         # but that's okay because we'll flush it in _end().
 754         oneblob = b''.join(datalist)
 755         try:
 756             f.write(oneblob)
 757         except IOError as e:
 758             reraise(GitError(e))
 759         nw = len(oneblob)
 760         crc = zlib.crc32(oneblob) & 0xffffffff
 761         self._update_idx(sha, crc, nw)
 762         self.outbytes += nw
 763         self.count += 1
 764         return nw, crc
 765
 766     def _update_idx(self, sha, crc, size):
 767         assert(sha)
 768         if self.idx:
 769             self.idx.add(sha, crc, self.file.tell() - size)
 770
 771     def _write(self, sha, type, content):
 772         if verbose:
 773             log('>')
 774         if not sha:
 775             sha = calc_hash(type, content)
 776         size, crc = self._raw_write(_encode_packobj(type, content,
 777                                                     self.compression_level),
 778                                     sha=sha)
 779         if self.outbytes >= self.max_pack_size \
 780            or self.count >= self.max_pack_objects:
 781             self.breakpoint()
 782         return sha
 783
 784     def breakpoint(self):
 785         """Clear byte and object counts and return the last processed id."""
 786         id = self._end(self.run_midx)
 787         self.outbytes = self.count = 0
 788         return id
 789
 790     def _require_objcache(self):
 791         if self.objcache is None and self.objcache_maker:
 792             self.objcache = self.objcache_maker()
 793         if self.objcache is None:
 794             raise GitError(
 795                     "PackWriter not opened or can't check exists w/o objcache")
 796
 797     def exists(self, id, want_source=False):
 798         """Return non-empty if an object is found in the object cache."""
 799         self._require_objcache()
 800         return self.objcache.exists(id, want_source=want_source)
 801
 802     def just_write(self, sha, type, content):
 803         """Write an object to the pack file without checking for duplication."""
 804         self._write(sha, type, content)
 805         # If nothing else, gc doesn't have/want an objcache
 806         if self.objcache is not None:
 807             self.objcache.add(sha)
 808
 809     def maybe_write(self, type, content):
 810         """Write an object to the pack file if not present and return its id."""
 811         sha = calc_hash(type, content)
 812         if not self.exists(sha):
 813             self._require_objcache()
 814             self.just_write(sha, type, content)
 815         return sha
 816
 817     def new_blob(self, blob):
 818         """Create a blob object in the pack with the supplied content."""
 819         return self.maybe_write(b'blob', blob)
 820
 821     def new_tree(self, shalist):
 822         """Create a tree object in the pack."""
 823         content = tree_encode(shalist)
 824         return self.maybe_write(b'tree', content)
 825
 826     def new_commit(self, tree, parent,
 827                    author, adate_sec, adate_tz,
 828                    committer, cdate_sec, cdate_tz,
 829                    msg):
 830         """Create a commit object in the pack.  The date_sec values must be
 831         epoch-seconds, and if a tz is None, the local timezone is assumed."""
 832         if adate_tz is not None:
 833             adate_str = _git_date_str(adate_sec, adate_tz)
 834         else:
 835             adate_str = _local_git_date_str(adate_sec)
 836         if cdate_tz is not None:
 837             cdate_str = _git_date_str(cdate_sec, cdate_tz)
 838         else:
 839             cdate_str = _local_git_date_str(cdate_sec)
 840         l = []
 841         if tree: l.append(b'tree %s' % hexlify(tree))
 842         if parent: l.append(b'parent %s' % hexlify(parent))
 843         if author: l.append(b'author %s %s' % (author, adate_str))
 844         if committer: l.append(b'committer %s %s' % (committer, cdate_str))
 845         l.append(b'')
 846         l.append(msg)
 847         return self.maybe_write(b'commit', b'\n'.join(l))
 848
 849     def abort(self):
 850         """Remove the pack file from disk."""
 851         f = self.file
 852         if f:
 853             pfd = self.parentfd
 854             self.file = None
 855             self.parentfd = None
 856             self.idx = None
 857             try:
 858                 try:
 859                     os.unlink(self.filename + b'.pack')
 860                 finally:
 861                     f.close()
 862             finally:
 863                 if pfd is not None:
 864                     os.close(pfd)
 865
 866     def _end(self, run_midx=True):
 867         f = self.file
 868         if not f: return None
 869         self.file = None
 870         try:
 871             self.objcache = None
 872             idx = self.idx
 873             self.idx = None
 874
 875             # update object count
 876             f.seek(8)
 877             cp = struct.pack('!i', self.count)
 878             assert(len(cp) == 4)
 879             f.write(cp)
 880
 881             # calculate the pack sha1sum
 882             f.seek(0)
 883             sum = Sha1()
 884             for b in chunkyreader(f):
 885                 sum.update(b)
 886             packbin = sum.digest()
 887             f.write(packbin)
 888             fdatasync(f.fileno())
 889         finally:
 890             f.close()
 891
 892         obj_list_sha = idx.write(self.filename + b'.idx', packbin)
 893         nameprefix = os.path.join(self.repo_dir,
 894                                   b'objects/pack/pack-' +  obj_list_sha)
 895         if os.path.exists(self.filename + b'.map'):
 896             os.unlink(self.filename + b'.map')
 897         os.rename(self.filename + b'.pack', nameprefix + b'.pack')
 898         os.rename(self.filename + b'.idx', nameprefix + b'.idx')
 899         try:
 900             os.fsync(self.parentfd)
 901         finally:
 902             os.close(self.parentfd)
 903
 904         if run_midx:
 905             auto_midx(os.path.join(self.repo_dir, b'objects/pack'))
 906
 907         if self.on_pack_finish:
 908             self.on_pack_finish(nameprefix)
 909
 910         return nameprefix
 911
 912     def close(self, run_midx=True):
 913         """Close the pack file and move it to its definitive path."""
 914         return self._end(run_midx=run_midx)
 915
 916
 917 class PackIdxV2Writer:
 918     def __init__(self):
 919         self.idx = list(list() for i in range(256))
 920         self.count = 0
 921
 922     def add(self, sha, crc, offs):
 923         assert(sha)
 924         self.count += 1
 925         self.idx[byte_int(sha[0])].append((sha, crc, offs))
 926
 927     def write(self, filename, packbin):
 928         ofs64_count = 0
 929         for section in self.idx:
 930             for entry in section:
 931                 if entry[2] >= 2**31:
 932                     ofs64_count += 1
 933
 934         # Length: header + fan-out + shas-and-crcs + overflow-offsets
 935         index_len = 8 + (4 * 256) + (28 * self.count) + (8 * ofs64_count)
 936         idx_map = None
 937         idx_f = open(filename, 'w+b')
 938         try:
 939             idx_f.truncate(index_len)
 940             fdatasync(idx_f.fileno())
 941             idx_map = mmap_readwrite(idx_f, close=False)
 942             try:
 943                 count = _helpers.write_idx(filename, idx_map, self.idx,
 944                                            self.count)
 945                 assert(count == self.count)
 946                 idx_map.flush()
 947             finally:
 948                 idx_map.close()
 949         finally:
 950             idx_f.close()
 951
 952         idx_f = open(filename, 'a+b')
 953         try:
 954             idx_f.write(packbin)
 955             idx_f.seek(0)
 956             idx_sum = Sha1()
 957             b = idx_f.read(8 + 4*256)
 958             idx_sum.update(b)
 959
 960             obj_list_sum = Sha1()
 961             for b in chunkyreader(idx_f, 20 * self.count):
 962                 idx_sum.update(b)
 963                 obj_list_sum.update(b)
 964             namebase = hexlify(obj_list_sum.digest())
 965
 966             for b in chunkyreader(idx_f):
 967                 idx_sum.update(b)
 968             idx_f.write(idx_sum.digest())
 969             fdatasync(idx_f.fileno())
 970             return namebase
 971         finally:
 972             idx_f.close()
 973
 974
 975 def list_refs(patterns=None, repo_dir=None,
 976               limit_to_heads=False, limit_to_tags=False):
 977     """Yield (refname, hash) tuples for all repository refs unless
 978     patterns are specified.  In that case, only include tuples for
 979     refs matching those patterns (cf. git-show-ref(1)).  The limits
 980     restrict the result items to refs/heads or refs/tags.  If both
 981     limits are specified, items from both sources will be included.
 982
 983     """
 984     argv = [b'git', b'show-ref']
 985     if limit_to_heads:
 986         argv.append(b'--heads')
 987     if limit_to_tags:
 988         argv.append(b'--tags')
 989     argv.append(b'--')
 990     if patterns:
 991         argv.extend(patterns)
 992     p = subprocess.Popen(argv, env=_gitenv(repo_dir), stdout=subprocess.PIPE,
 993                          close_fds=True)
 994     out = p.stdout.read().strip()
 995     rv = p.wait()  # not fatal
 996     if rv:
 997         assert(not out)
 998     if out:
 999         for d in out.split(b'\n'):
1000             sha, name = d.split(b' ', 1)
1001             yield name, unhexlify(sha)
1002
1003
1004 def read_ref(refname, repo_dir = None):
1005     """Get the commit id of the most recent commit made on a given ref."""
1006     refs = list_refs(patterns=[refname], repo_dir=repo_dir, limit_to_heads=True)
1007     l = tuple(islice(refs, 2))
1008     if l:
1009         assert(len(l) == 1)
1010         return l[0][1]
1011     else:
1012         return None
1013
1014
1015 def rev_list_invocation(ref_or_refs, format=None):
1016     if isinstance(ref_or_refs, bytes):
1017         refs = (ref_or_refs,)
1018     else:
1019         refs = ref_or_refs
1020     argv = [b'git', b'rev-list']
1021
1022     if format:
1023         argv.append(b'--pretty=format:' + format)
1024     for ref in refs:
1025         assert not ref.startswith(b'-')
1026         argv.append(ref)
1027     argv.append(b'--')
1028     return argv
1029
1030
1031 def rev_list(ref_or_refs, parse=None, format=None, repo_dir=None):
1032     """Yield information about commits as per "git rev-list".  If a format
1033     is not provided, yield one hex hash at a time.  If a format is
1034     provided, pass it to rev-list and call parse(git_stdout) for each
1035     commit with the stream positioned just after the rev-list "commit
1036     HASH" header line.  When a format is provided yield (oidx,
1037     parse(git_stdout)) for each commit.
1038
1039     """
1040     assert bool(parse) == bool(format)
1041     p = subprocess.Popen(rev_list_invocation(ref_or_refs,
1042                                              format=format),
1043                          env=_gitenv(repo_dir),
1044                          stdout = subprocess.PIPE,
1045                          close_fds=True)
1046     if not format:
1047         for line in p.stdout:
1048             yield line.strip()
1049     else:
1050         line = p.stdout.readline()
1051         while line:
1052             s = line.strip()
1053             if not s.startswith(b'commit '):
1054                 raise Exception('unexpected line ' + repr(s))
1055             s = s[7:]
1056             assert len(s) == 40
1057             yield s, parse(p.stdout)
1058             line = p.stdout.readline()
1059
1060     rv = p.wait()  # not fatal
1061     if rv:
1062         raise GitError('git rev-list returned error %d' % rv)
1063
1064
1065 def get_commit_dates(refs, repo_dir=None):
1066     """Get the dates for the specified commit refs.  For now, every unique
1067        string in refs must resolve to a different commit or this
1068        function will fail."""
1069     result = []
1070     for ref in refs:
1071         commit = get_commit_items(ref, cp(repo_dir))
1072         result.append(commit.author_sec)
1073     return result
1074
1075
1076 def rev_parse(committish, repo_dir=None):
1077     """Resolve the full hash for 'committish', if it exists.
1078
1079     Should be roughly equivalent to 'git rev-parse'.
1080
1081     Returns the hex value of the hash if it is found, None if 'committish' does
1082     not correspond to anything.
1083     """
1084     head = read_ref(committish, repo_dir=repo_dir)
1085     if head:
1086         debug2("resolved from ref: commit = %s\n" % hexlify(head))
1087         return head
1088
1089     pL = PackIdxList(repo(b'objects/pack', repo_dir=repo_dir))
1090
1091     if len(committish) == 40:
1092         try:
1093             hash = unhexlify(committish)
1094         except TypeError:
1095             return None
1096
1097         if pL.exists(hash):
1098             return hash
1099
1100     return None
1101
1102
1103 def update_ref(refname, newval, oldval, repo_dir=None):
1104     """Update a repository reference."""
1105     if not oldval:
1106         oldval = b''
1107     assert refname.startswith(b'refs/heads/') \
1108         or refname.startswith(b'refs/tags/')
1109     p = subprocess.Popen([b'git', b'update-ref', refname,
1110                           hexlify(newval), hexlify(oldval)],
1111                          env=_gitenv(repo_dir),
1112                          close_fds=True)
1113     _git_wait(b'git update-ref', p)
1114
1115
1116 def delete_ref(refname, oldvalue=None):
1117     """Delete a repository reference (see git update-ref(1))."""
1118     assert refname.startswith(b'refs/')
1119     oldvalue = [] if not oldvalue else [oldvalue]
1120     p = subprocess.Popen([b'git', b'update-ref', b'-d', refname] + oldvalue,
1121                          env=_gitenv(),
1122                          close_fds=True)
1123     _git_wait('git update-ref', p)
1124
1125
1126 def guess_repo(path=None):
1127     """Set the path value in the global variable "repodir".
1128     This makes bup look for an existing bup repository, but not fail if a
1129     repository doesn't exist. Usually, if you are interacting with a bup
1130     repository, you would not be calling this function but using
1131     check_repo_or_die().
1132     """
1133     global repodir
1134     if path:
1135         repodir = path
1136     if not repodir:
1137         repodir = environ.get(b'BUP_DIR')
1138         if not repodir:
1139             repodir = os.path.expanduser(b'~/.bup')
1140
1141
1142 def init_repo(path=None):
1143     """Create the Git bare repository for bup in a given path."""
1144     guess_repo(path)
1145     d = repo()  # appends a / to the path
1146     parent = os.path.dirname(os.path.dirname(d))
1147     if parent and not os.path.exists(parent):
1148         raise GitError('parent directory "%s" does not exist\n'
1149                        % path_msg(parent))
1150     if os.path.exists(d) and not os.path.isdir(os.path.join(d, b'.')):
1151         raise GitError('"%s" exists but is not a directory\n' % path_msg(d))
1152     p = subprocess.Popen([b'git', b'--bare', b'init'], stdout=sys.stderr,
1153                          env=_gitenv(),
1154                          close_fds=True)
1155     _git_wait('git init', p)
1156     # Force the index version configuration in order to ensure bup works
1157     # regardless of the version of the installed Git binary.
1158     p = subprocess.Popen([b'git', b'config', b'pack.indexVersion', '2'],
1159                          stdout=sys.stderr, env=_gitenv(), close_fds=True)
1160     _git_wait('git config', p)
1161     # Enable the reflog
1162     p = subprocess.Popen([b'git', b'config', b'core.logAllRefUpdates', b'true'],
1163                          stdout=sys.stderr, env=_gitenv(), close_fds=True)
1164     _git_wait('git config', p)
1165
1166
1167 def check_repo_or_die(path=None):
1168     """Check to see if a bup repository probably exists, and abort if not."""
1169     guess_repo(path)
1170     top = repo()
1171     pst = stat_if_exists(top + b'/objects/pack')
1172     if pst and stat.S_ISDIR(pst.st_mode):
1173         return
1174     if not pst:
1175         top_st = stat_if_exists(top)
1176         if not top_st:
1177             log('error: repository %r does not exist (see "bup help init")\n'
1178                 % top)
1179             sys.exit(15)
1180     log('error: %s is not a repository\n' % path_msg(top))
1181     sys.exit(14)
1182
1183
1184 def is_suitable_git(ver_str):
1185     if not ver_str.startswith(b'git version '):
1186         return 'unrecognized'
1187     ver_str = ver_str[len(b'git version '):]
1188     if ver_str.startswith(b'0.'):
1189         return 'insufficient'
1190     if ver_str.startswith(b'1.'):
1191         if re.match(br'1\.[012345]rc', ver_str):
1192             return 'insufficient'
1193         if re.match(br'1\.[01234]\.', ver_str):
1194             return 'insufficient'
1195         if re.match(br'1\.5\.[012345]($|\.)', ver_str):
1196             return 'insufficient'
1197         if re.match(br'1\.5\.6-rc', ver_str):
1198             return 'insufficient'
1199         return 'suitable'
1200     if re.match(br'[0-9]+(\.|$)?', ver_str):
1201         return 'suitable'
1202     sys.exit(13)
1203
1204 _git_great = None
1205
1206 def require_suitable_git(ver_str=None):
1207     """Raise GitError if the version of git isn't suitable.
1208
1209     Rely on ver_str when provided, rather than invoking the git in the
1210     path.
1211
1212     """
1213     global _git_great
1214     if _git_great is not None:
1215         return
1216     if environ.get(b'BUP_GIT_VERSION_IS_FINE', b'').lower() \
1217        in (b'yes', b'true', b'1'):
1218         _git_great = True
1219         return
1220     if not ver_str:
1221         ver_str, _, _ = _git_exo([b'git', b'--version'])
1222     status = is_suitable_git(ver_str)
1223     if status == 'unrecognized':
1224         raise GitError('Unexpected git --version output: %r' % ver_str)
1225     if status == 'insufficient':
1226         log('error: git version must be at least 1.5.6\n')
1227         sys.exit(1)
1228     if status == 'suitable':
1229         _git_great = True
1230         return
1231     assert False
1232
1233
1234 class _AbortableIter:
1235     def __init__(self, it, onabort = None):
1236         self.it = it
1237         self.onabort = onabort
1238         self.done = None
1239
1240     def __iter__(self):
1241         return self
1242
1243     def __next__(self):
1244         try:
1245             return next(self.it)
1246         except StopIteration as e:
1247             self.done = True
1248             raise
1249         except:
1250             self.abort()
1251             raise
1252
1253     next = __next__
1254
1255     def abort(self):
1256         """Abort iteration and call the abortion callback, if needed."""
1257         if not self.done:
1258             self.done = True
1259             if self.onabort:
1260                 self.onabort()
1261
1262     def __del__(self):
1263         self.abort()
1264
1265
1266 class CatPipe:
1267     """Link to 'git cat-file' that is used to retrieve blob data."""
1268     def __init__(self, repo_dir = None):
1269         require_suitable_git()
1270         self.repo_dir = repo_dir
1271         self.p = self.inprogress = None
1272
1273     def close(self, wait=False):
1274         p = self.p
1275         if p:
1276             p.stdout.close()
1277             p.stdin.close()
1278         self.p = None
1279         self.inprogress = None
1280         if wait:
1281             p.wait()
1282             return p.returncode
1283
1284     def restart(self):
1285         self.close()
1286         self.p = subprocess.Popen([b'git', b'cat-file', b'--batch'],
1287                                   stdin=subprocess.PIPE,
1288                                   stdout=subprocess.PIPE,
1289                                   close_fds = True,
1290                                   bufsize = 4096,
1291                                   env=_gitenv(self.repo_dir))
1292
1293     def get(self, ref):
1294         """Yield (oidx, type, size), followed by the data referred to by ref.
1295         If ref does not exist, only yield (None, None, None).
1296
1297         """
1298         if not self.p or self.p.poll() != None:
1299             self.restart()
1300         assert(self.p)
1301         poll_result = self.p.poll()
1302         assert(poll_result == None)
1303         if self.inprogress:
1304             log('get: opening %r while %r is open\n' % (ref, self.inprogress))
1305         assert(not self.inprogress)
1306         assert ref.find(b'\n') < 0
1307         assert ref.find(b'\r') < 0
1308         assert not ref.startswith(b'-')
1309         self.inprogress = ref
1310         self.p.stdin.write(ref + b'\n')
1311         self.p.stdin.flush()
1312         hdr = self.p.stdout.readline()
1313         if hdr.endswith(b' missing\n'):
1314             self.inprogress = None
1315             yield None, None, None
1316             return
1317         info = hdr.split(b' ')
1318         if len(info) != 3 or len(info[0]) != 40:
1319             raise GitError('expected object (id, type, size), got %r' % info)
1320         oidx, typ, size = info
1321         size = int(size)
1322         it = _AbortableIter(chunkyreader(self.p.stdout, size),
1323                             onabort=self.close)
1324         try:
1325             yield oidx, typ, size
1326             for blob in it:
1327                 yield blob
1328             readline_result = self.p.stdout.readline()
1329             assert readline_result == b'\n'
1330             self.inprogress = None
1331         except Exception as e:
1332             it.abort()
1333             raise
1334
1335     def _join(self, it):
1336         _, typ, _ = next(it)
1337         if typ == b'blob':
1338             for blob in it:
1339                 yield blob
1340         elif typ == b'tree':
1341             treefile = b''.join(it)
1342             for (mode, name, sha) in tree_decode(treefile):
1343                 for blob in self.join(hexlify(sha)):
1344                     yield blob
1345         elif typ == b'commit':
1346             treeline = b''.join(it).split(b'\n')[0]
1347             assert treeline.startswith(b'tree ')
1348             for blob in self.join(treeline[5:]):
1349                 yield blob
1350         else:
1351             raise GitError('invalid object type %r: expected blob/tree/commit'
1352                            % typ)
1353
1354     def join(self, id):
1355         """Generate a list of the content of all blobs that can be reached
1356         from an object.  The hash given in 'id' must point to a blob, a tree
1357         or a commit. The content of all blobs that can be seen from trees or
1358         commits will be added to the list.
1359         """
1360         for d in self._join(self.get(id)):
1361             yield d
1362
1363
1364 _cp = {}
1365
1366 def cp(repo_dir=None):
1367     """Create a CatPipe object or reuse the already existing one."""
1368     global _cp, repodir
1369     if not repo_dir:
1370         repo_dir = repodir or repo()
1371     repo_dir = os.path.abspath(repo_dir)
1372     cp = _cp.get(repo_dir)
1373     if not cp:
1374         cp = CatPipe(repo_dir)
1375         _cp[repo_dir] = cp
1376     return cp
1377
1378
1379 def close_catpipes():
1380     # FIXME: chain exceptions
1381     while _cp:
1382         _, cp = _cp.popitem()
1383         cp.close(wait=True)
1384
1385
1386 def tags(repo_dir = None):
1387     """Return a dictionary of all tags in the form {hash: [tag_names, ...]}."""
1388     tags = {}
1389     for n, c in list_refs(repo_dir = repo_dir, limit_to_tags=True):
1390         assert n.startswith(b'refs/tags/')
1391         name = n[10:]
1392         if not c in tags:
1393             tags[c] = []
1394         tags[c].append(name)  # more than one tag can point at 'c'
1395     return tags
1396
1397
1398 class MissingObject(KeyError):
1399     def __init__(self, oid):
1400         self.oid = oid
1401         KeyError.__init__(self, 'object %r is missing' % hexlify(oid))
1402
1403
1404 WalkItem = namedtuple('WalkItem', ['oid', 'type', 'mode',
1405                                    'path', 'chunk_path', 'data'])
1406 # The path is the mangled path, and if an item represents a fragment
1407 # of a chunked file, the chunk_path will be the chunked subtree path
1408 # for the chunk, i.e. ['', '2d3115e', ...].  The top-level path for a
1409 # chunked file will have a chunk_path of [''].  So some chunk subtree
1410 # of the file '/foo/bar/baz' might look like this:
1411 #
1412 #   item.path = ['foo', 'bar', 'baz.bup']
1413 #   item.chunk_path = ['', '2d3115e', '016b097']
1414 #   item.type = 'tree'
1415 #   ...
1416
1417
1418 def walk_object(get_ref, oidx, stop_at=None, include_data=None):
1419     """Yield everything reachable from oidx via get_ref (which must behave
1420     like CatPipe get) as a WalkItem, stopping whenever stop_at(oidx)
1421     returns true.  Throw MissingObject if a hash encountered is
1422     missing from the repository, and don't read or return blob content
1423     in the data field unless include_data is set.
1424
1425     """
1426     # Maintain the pending stack on the heap to avoid stack overflow
1427     pending = [(oidx, [], [], None)]
1428     while len(pending):
1429         oidx, parent_path, chunk_path, mode = pending.pop()
1430         oid = unhexlify(oidx)
1431         if stop_at and stop_at(oidx):
1432             continue
1433
1434         if (not include_data) and mode and stat.S_ISREG(mode):
1435             # If the object is a "regular file", then it's a leaf in
1436             # the graph, so we can skip reading the data if the caller
1437             # hasn't requested it.
1438             yield WalkItem(oid=oid, type=b'blob',
1439                            chunk_path=chunk_path, path=parent_path,
1440                            mode=mode,
1441                            data=None)
1442             continue
1443
1444         item_it = get_ref(oidx)
1445         get_oidx, typ, _ = next(item_it)
1446         if not get_oidx:
1447             raise MissingObject(unhexlify(oidx))
1448         if typ not in (b'blob', b'commit', b'tree'):
1449             raise Exception('unexpected repository object type %r' % typ)
1450
1451         # FIXME: set the mode based on the type when the mode is None
1452         if typ == b'blob' and not include_data:
1453             # Dump data until we can ask cat_pipe not to fetch it
1454             for ignored in item_it:
1455                 pass
1456             data = None
1457         else:
1458             data = b''.join(item_it)
1459
1460         yield WalkItem(oid=oid, type=typ,
1461                        chunk_path=chunk_path, path=parent_path,
1462                        mode=mode,
1463                        data=(data if include_data else None))
1464
1465         if typ == b'commit':
1466             commit_items = parse_commit(data)
1467             for pid in commit_items.parents:
1468                 pending.append((pid, parent_path, chunk_path, mode))
1469             pending.append((commit_items.tree, parent_path, chunk_path,
1470                             hashsplit.GIT_MODE_TREE))
1471         elif typ == b'tree':
1472             for mode, name, ent_id in tree_decode(data):
1473                 demangled, bup_type = demangle_name(name, mode)
1474                 if chunk_path:
1475                     sub_path = parent_path
1476                     sub_chunk_path = chunk_path + [name]
1477                 else:
1478                     sub_path = parent_path + [name]
1479                     if bup_type == BUP_CHUNKED:
1480                         sub_chunk_path = [b'']
1481                     else:
1482                         sub_chunk_path = chunk_path
1483                 pending.append((hexlify(ent_id), sub_path, sub_chunk_path,
1484                                 mode))