lib/bup/vfs.py

   1 """Virtual File System interface to bup repository content.
   2
   3 This module provides a path-based interface to the content of a bup
   4 repository.
   5
   6 The VFS is structured like this:
   7
   8   /SAVE-NAME/latest/...
   9   /SAVE-NAME/SAVE-DATE/...
  10   /.tag/TAG-NAME/...
  11
  12 Each path is represented by an item that has least an item.meta which
  13 may be either a Metadata object, or an integer mode.  Functions like
  14 item_mode() and item_size() will return the mode and size in either
  15 case.  Any item.meta Metadata instances must not be modified directly.
  16 Make a copy to modify via item.meta.copy() if needed, or call
  17 copy_item().
  18
  19 The want_meta argument is advisory for calls that accept it, and it
  20 may not be honored.  Callers must be able to handle an item.meta value
  21 that is either an instance of Metadata or an integer mode, perhaps
  22 via item_mode() or augment_item_meta().
  23
  24 Setting want_meta=False is rarely desirable since it can limit the VFS
  25 to only the metadata that git itself can represent, and so for
  26 example, fifos and sockets will appear to be regular files
  27 (e.g. S_ISREG(item_mode(item)) will be true).  But the option is still
  28 provided because it may be more efficient when just the path names or
  29 the more limited metadata is sufficient.
  30
  31 Any given metadata object's size may be None, in which case the size
  32 can be computed via item_size() or augment_item_meta(...,
  33 include_size=True).
  34
  35 When traversing a directory using functions like contents(), the meta
  36 value for any directories other than '.' will be a default directory
  37 mode, not a Metadata object.  This is because the actual metadata for
  38 a directory is stored inside the directory (see
  39 fill_in_metadata_if_dir() or ensure_item_has_metadata()).
  40
  41 Commit items represent commits (e.g. /.tag/some-commit or
  42 /foo/latest), and for most purposes, they appear as the underlying
  43 tree.  S_ISDIR(item_mode(item)) will return true for both tree Items
  44 and Commits and the commit's oid is the tree hash; the commit hash is
  45 item.coid.
  46
  47 """
  48
  49 from __future__ import absolute_import, print_function
  50 from collections import namedtuple
  51 from errno import EINVAL, ELOOP, ENOENT, ENOTDIR
  52 from itertools import chain, dropwhile, groupby, tee
  53 from random import randrange
  54 from stat import S_IFDIR, S_IFLNK, S_IFREG, S_ISDIR, S_ISLNK, S_ISREG
  55 from time import localtime, strftime
  56 import exceptions, re, sys
  57
  58 from bup import git, metadata, vint
  59 from bup.compat import range
  60 from bup.git import BUP_CHUNKED, cp, get_commit_items, parse_commit, tree_decode
  61 from bup.helpers import debug2, last
  62 from bup.metadata import Metadata
  63 from bup.vint import read_bvec, write_bvec
  64 from bup.vint import read_vint, write_vint
  65 from bup.vint import read_vuint, write_vuint
  66
  67 # We currently assume that it's always appropriate to just forward IOErrors
  68 # to a remote client.
  69
  70 class IOError(exceptions.IOError):
  71     def __init__(self, errno, message, terminus=None):
  72         exceptions.IOError.__init__(self, errno, message)
  73         self.terminus = terminus
  74
  75 def write_ioerror(port, ex):
  76     assert isinstance(ex, IOError)
  77     write_vuint(port,
  78                 (1 if ex.errno is not None else 0)
  79                 | (2 if ex.message is not None else 0)
  80                 | (4 if ex.terminus is not None else 0))
  81     if ex.errno is not None:
  82         write_vint(port, ex.errno)
  83     if ex.message is not None:
  84         write_bvec(port, ex.message.encode('utf-8'))
  85     if ex.terminus is not None:
  86         write_resolution(port, ex.terminus)
  87
  88 def read_ioerror(port):
  89     mask = read_vuint(port)
  90     no = read_vint(port) if 1 & mask else None
  91     msg = read_bvec(port).decode('utf-8') if 2 & mask else None
  92     term = read_resolution(port) if 4 & mask else None
  93     return IOError(errno=no, message=msg, terminus=term)
  94
  95
  96 default_file_mode = S_IFREG | 0o644
  97 default_dir_mode = S_IFDIR | 0o755
  98 default_symlink_mode = S_IFLNK | 0o755
  99
 100 def _default_mode_for_gitmode(gitmode):
 101     if S_ISREG(gitmode):
 102         return default_file_mode
 103     if S_ISDIR(gitmode):
 104         return default_dir_mode
 105     if S_ISLNK(gitmode):
 106         return default_symlink_mode
 107     raise Exception('unexpected git mode ' + oct(gitmode))
 108
 109 def _normal_or_chunked_file_size(repo, oid):
 110     """Return the size of the normal or chunked file indicated by oid."""
 111     # FIXME: --batch-format CatPipe?
 112     it = repo.cat(oid.encode('hex'))
 113     _, obj_t, size = next(it)
 114     ofs = 0
 115     while obj_t == 'tree':
 116         mode, name, last_oid = last(tree_decode(''.join(it)))
 117         ofs += int(name, 16)
 118         it = repo.cat(last_oid.encode('hex'))
 119         _, obj_t, size = next(it)
 120     return ofs + sum(len(b) for b in it)
 121
 122 def _skip_chunks_before_offset(tree, offset):
 123     prev_ent = next(tree, None)
 124     if not prev_ent:
 125         return tree
 126     ent = None
 127     for ent in tree:
 128         ent_ofs = int(ent[1], 16)
 129         if ent_ofs > offset:
 130             return chain([prev_ent, ent], tree)
 131         if ent_ofs == offset:
 132             return chain([ent], tree)
 133         prev_ent = ent
 134     return [prev_ent]
 135
 136 def _tree_chunks(repo, tree, startofs):
 137     "Tree should be a sequence of (name, mode, hash) as per tree_decode()."
 138     assert(startofs >= 0)
 139     # name is the chunk's hex offset in the original file
 140     for mode, name, oid in _skip_chunks_before_offset(tree, startofs):
 141         ofs = int(name, 16)
 142         skipmore = startofs - ofs
 143         if skipmore < 0:
 144             skipmore = 0
 145         it = repo.cat(oid.encode('hex'))
 146         _, obj_t, size = next(it)
 147         data = ''.join(it)
 148         if S_ISDIR(mode):
 149             assert obj_t == 'tree'
 150             for b in _tree_chunks(repo, tree_decode(data), skipmore):
 151                 yield b
 152         else:
 153             assert obj_t == 'blob'
 154             yield data[skipmore:]
 155
 156 class _ChunkReader:
 157     def __init__(self, repo, oid, startofs):
 158         it = repo.cat(oid.encode('hex'))
 159         _, obj_t, size = next(it)
 160         isdir = obj_t == 'tree'
 161         data = ''.join(it)
 162         if isdir:
 163             self.it = _tree_chunks(repo, tree_decode(data), startofs)
 164             self.blob = None
 165         else:
 166             self.it = None
 167             self.blob = data[startofs:]
 168         self.ofs = startofs
 169
 170     def next(self, size):
 171         out = ''
 172         while len(out) < size:
 173             if self.it and not self.blob:
 174                 try:
 175                     self.blob = self.it.next()
 176                 except StopIteration:
 177                     self.it = None
 178             if self.blob:
 179                 want = size - len(out)
 180                 out += self.blob[:want]
 181                 self.blob = self.blob[want:]
 182             if not self.it:
 183                 break
 184         debug2('next(%d) returned %d\n' % (size, len(out)))
 185         self.ofs += len(out)
 186         return out
 187
 188 class _FileReader(object):
 189     def __init__(self, repo, oid, known_size=None):
 190         assert len(oid) == 20
 191         self.oid = oid
 192         self.ofs = 0
 193         self.reader = None
 194         self._repo = repo
 195         self._size = known_size
 196
 197     def _compute_size(self):
 198         if not self._size:
 199             self._size = _normal_or_chunked_file_size(self._repo, self.oid)
 200         return self._size
 201
 202     def seek(self, ofs):
 203         if ofs < 0 or ofs > self._compute_size():
 204             raise IOError(EINVAL, 'Invalid seek offset: %d' % ofs)
 205         self.ofs = ofs
 206
 207     def tell(self):
 208         return self.ofs
 209
 210     def read(self, count=-1):
 211         size = self._compute_size()
 212         if self.ofs >= size:
 213             return ''
 214         if count < 0:
 215             count = size - self.ofs
 216         if not self.reader or self.reader.ofs != self.ofs:
 217             self.reader = _ChunkReader(self._repo, self.oid, self.ofs)
 218         try:
 219             buf = self.reader.next(count)
 220         except:
 221             self.reader = None
 222             raise  # our offsets will be all screwed up otherwise
 223         self.ofs += len(buf)
 224         return buf
 225
 226     def close(self):
 227         pass
 228
 229     def __enter__(self):
 230         return self
 231     def __exit__(self, type, value, traceback):
 232         self.close()
 233         return False
 234
 235 _multiple_slashes_rx = re.compile(r'//+')
 236
 237 def _decompose_path(path):
 238     """Return a boolean indicating whether the path is absolute, and a
 239     reversed list of path elements, omitting any occurrences of "."
 240     and ignoring any leading or trailing slash.  If the path is
 241     effectively '/' or '.', return an empty list.
 242
 243     """
 244     path = re.sub(_multiple_slashes_rx, '/', path)
 245     if path == '/':
 246         return True, True, []
 247     is_absolute = must_be_dir = False
 248     if path.startswith('/'):
 249         is_absolute = True
 250         path = path[1:]
 251     for suffix in ('/', '/.'):
 252         if path.endswith(suffix):
 253             must_be_dir = True
 254             path = path[:-len(suffix)]
 255     parts = [x for x in path.split('/') if x != '.']
 256     parts.reverse()
 257     if not parts:
 258         must_be_dir = True  # e.g. path was effectively '.' or '/', etc.
 259     return is_absolute, must_be_dir, parts
 260
 261
 262 Item = namedtuple('Item', ('meta', 'oid'))
 263 Chunky = namedtuple('Chunky', ('meta', 'oid'))
 264 FakeLink = namedtuple('FakeLink', ('meta', 'target'))
 265 Root = namedtuple('Root', ('meta'))
 266 Tags = namedtuple('Tags', ('meta'))
 267 RevList = namedtuple('RevList', ('meta', 'oid'))
 268 Commit = namedtuple('Commit', ('meta', 'oid', 'coid'))
 269
 270 item_types = frozenset((Item, Chunky, Root, Tags, RevList, Commit))
 271 real_tree_types = frozenset((Item, Commit))
 272
 273 def write_item(port, item):
 274     kind = type(item)
 275     name = bytes(kind.__name__)
 276     meta = item.meta
 277     has_meta = 1 if isinstance(meta, Metadata) else 0
 278     if kind in (Item, Chunky, RevList):
 279         assert len(item.oid) == 20
 280         if has_meta:
 281             vint.send(port, 'sVs', name, has_meta, item.oid)
 282             Metadata.write(meta, port, include_path=False)
 283         else:
 284             vint.send(port, 'sVsV', name, has_meta, item.oid, item.meta)
 285     elif kind in (Root, Tags):
 286         if has_meta:
 287             vint.send(port, 'sV', name, has_meta)
 288             Metadata.write(meta, port, include_path=False)
 289         else:
 290             vint.send(port, 'sVV', name, has_meta, item.meta)
 291     elif kind == Commit:
 292         assert len(item.oid) == 20
 293         assert len(item.coid) == 20
 294         if has_meta:
 295             vint.send(port, 'sVss', name, has_meta, item.oid, item.coid)
 296             Metadata.write(meta, port, include_path=False)
 297         else:
 298             vint.send(port, 'sVssV', name, has_meta, item.oid, item.coid,
 299                       item.meta)
 300     elif kind == FakeLink:
 301         if has_meta:
 302             vint.send(port, 'sVs', name, has_meta, item.target)
 303             Metadata.write(meta, port, include_path=False)
 304         else:
 305             vint.send(port, 'sVsV', name, has_meta, item.target, item.meta)
 306     else:
 307         assert False
 308
 309 def read_item(port):
 310     def read_m(port, has_meta):
 311         if has_meta:
 312             m = Metadata.read(port)
 313             return m
 314         return read_vuint(port)
 315     kind, has_meta = vint.recv(port, 'sV')
 316     if kind == b'Item':
 317         oid, meta = read_bvec(port), read_m(port, has_meta)
 318         return Item(oid=oid, meta=meta)
 319     if kind == b'Chunky':
 320         oid, meta = read_bvec(port), read_m(port, has_meta)
 321         return Chunky(oid=oid, meta=meta)
 322     if kind == b'RevList':
 323         oid, meta = read_bvec(port), read_m(port, has_meta)
 324         return RevList(oid=oid, meta=meta)
 325     if kind == b'Root':
 326         return Root(meta=read_m(port, has_meta))
 327     if kind == b'Tags':
 328         return Tags(meta=read_m(port, has_meta))
 329     if kind == b'Commit':
 330         oid, coid = vint.recv(port, 'ss')
 331         meta = read_m(port, has_meta)
 332         return Commit(oid=oid, coid=coid, meta=meta)
 333     if kind == b'FakeLink':
 334         target, meta = read_bvec(port), read_m(port, has_meta)
 335         return FakeLink(target=target, meta=meta)
 336     assert False
 337
 338 def write_resolution(port, resolution):
 339     write_vuint(port, len(resolution))
 340     for name, item in resolution:
 341         write_bvec(port, name)
 342         if item:
 343             port.write(b'\1')
 344             write_item(port, item)
 345         else:
 346             port.write(b'\0')
 347
 348 def read_resolution(port):
 349     n = read_vuint(port)
 350     result = []
 351     for i in range(n):
 352         name = read_bvec(port)
 353         have_item = ord(port.read(1))
 354         assert have_item in (0, 1)
 355         item = read_item(port) if have_item else None
 356         result.append((name, item))
 357     return tuple(result)
 358
 359
 360 _root = Root(meta=default_dir_mode)
 361 _tags = Tags(meta=default_dir_mode)
 362
 363
 364 ### vfs cache
 365
 366 ### A general purpose shared cache with (currently) cheap random
 367 ### eviction.  At the moment there is no weighting so a single commit
 368 ### item is just as likely to be evicted as an entire "rev-list".  See
 369 ### is_valid_cache_key for a description of the expected content.
 370
 371 _cache = {}
 372 _cache_keys = []
 373 _cache_max_items = 30000
 374
 375 def clear_cache():
 376     global _cache, _cache_keys
 377     _cache = {}
 378     _cache_keys = []
 379
 380 def is_valid_cache_key(x):
 381     """Return logically true if x looks like it could be a valid cache key
 382     (with respect to structure).  Current valid cache entries:
 383       res:... -> resolution
 384       itm:OID -> Commit
 385       rvl:OID -> {'.', commit, '2012...', next_commit, ...}
 386     """
 387     # Suspect we may eventually add "(container_oid, name) -> ...", and others.
 388     x_t = type(x)
 389     if x_t is bytes:
 390         tag = x[:4]
 391         if tag in ('itm:', 'rvl:') and len(x) == 24:
 392             return True
 393         if tag == 'res:':
 394             return True
 395
 396 def cache_get(key):
 397     global _cache
 398     if not is_valid_cache_key(key):
 399         raise Exception('invalid cache key: ' + repr(key))
 400     return _cache.get(key)
 401
 402 def cache_notice(key, value):
 403     global _cache, _cache_keys, _cache_max_items
 404     if not is_valid_cache_key(key):
 405         raise Exception('invalid cache key: ' + repr(key))
 406     if key in _cache:
 407         return
 408     if len(_cache) < _cache_max_items:
 409         _cache_keys.append(key)
 410         _cache[key] = value
 411         return
 412     victim_i = randrange(0, len(_cache_keys))
 413     victim = _cache_keys[victim_i]
 414     del _cache[victim]
 415     _cache_keys[victim_i] = key
 416     _cache[key] = value
 417
 418 def cache_get_commit_item(oid, need_meta=True):
 419     """Return the requested tree item if it can be found in the cache.
 420     When need_meta is true don't return a cached item that only has a
 421     mode."""
 422     # tree might be stored independently, or as '.' with its entries.
 423     commit_key = b'itm:' + oid
 424     item = cache_get(commit_key)
 425     if item:
 426         if not need_meta:
 427             return item
 428         if isinstance(item.meta, Metadata):
 429             return item
 430     entries = cache_get(b'rvl:' + oid)
 431     if entries:
 432         return entries['.']
 433
 434 def cache_get_revlist_item(oid, need_meta=True):
 435     commit = cache_get_commit_item(oid, need_meta=need_meta)
 436     if commit:
 437         return RevList(oid=oid, meta=commit.meta)
 438
 439 def copy_item(item):
 440     """Return a completely independent copy of item, such that
 441     modifications will not affect the original.
 442
 443     """
 444     meta = getattr(item, 'meta', None)
 445     if isinstance(meta, Metadata):
 446         return(item._replace(meta=meta.copy()))
 447     return item
 448
 449 def item_mode(item):
 450     """Return the integer mode (stat st_mode) for item."""
 451     m = item.meta
 452     if isinstance(m, Metadata):
 453         return m.mode
 454     return m
 455
 456 def _read_dir_meta(bupm):
 457     # This is because save writes unmodified Metadata() entries for
 458     # fake parents -- test-save-strip-graft.sh demonstrates.
 459     m = Metadata.read(bupm)
 460     if not m:
 461         return default_dir_mode
 462     assert m.mode is not None
 463     if m.size is None:
 464         m.size = 0
 465     return m
 466
 467 def tree_data_and_bupm(repo, oid):
 468     """Return (tree_bytes, bupm_oid) where bupm_oid will be None if the
 469     tree has no metadata (i.e. older bup save, or non-bup tree).
 470
 471     """
 472     assert len(oid) == 20
 473     it = repo.cat(oid.encode('hex'))
 474     _, item_t, size = next(it)
 475     data = ''.join(it)
 476     if item_t == 'commit':
 477         commit = parse_commit(data)
 478         it = repo.cat(commit.tree)
 479         _, item_t, size = next(it)
 480         data = ''.join(it)
 481         assert item_t == 'tree'
 482     elif item_t != 'tree':
 483         raise Exception('%r is not a tree or commit' % oid.encode('hex'))
 484     for _, mangled_name, sub_oid in tree_decode(data):
 485         if mangled_name == '.bupm':
 486             return data, sub_oid
 487         if mangled_name > '.bupm':
 488             break
 489     return data, None
 490
 491 def _find_treeish_oid_metadata(repo, oid):
 492     """Return the metadata for the tree or commit oid, or None if the tree
 493     has no metadata (i.e. older bup save, or non-bup tree).
 494
 495     """
 496     tree_data, bupm_oid = tree_data_and_bupm(repo, oid)
 497     if bupm_oid:
 498         with _FileReader(repo, bupm_oid) as meta_stream:
 499             return _read_dir_meta(meta_stream)
 500     return None
 501
 502 def _readlink(repo, oid):
 503     return ''.join(repo.join(oid.encode('hex')))
 504
 505 def readlink(repo, item):
 506     """Return the link target of item, which must be a symlink.  Reads the
 507     target from the repository if necessary."""
 508     assert repo
 509     assert S_ISLNK(item_mode(item))
 510     if isinstance(item.meta, Metadata):
 511         target = item.meta.symlink_target
 512         if target:
 513             return target
 514     elif isinstance(item, FakeLink):
 515         return item.target
 516     return _readlink(repo, item.oid)
 517
 518 def _compute_item_size(repo, item):
 519     mode = item_mode(item)
 520     if S_ISREG(mode):
 521         size = _normal_or_chunked_file_size(repo, item.oid)
 522         return size
 523     if S_ISLNK(mode):
 524         return len(_readlink(repo, item.oid))
 525     return 0
 526
 527 def item_size(repo, item):
 528     """Return the size of item, computing it if necessary."""
 529     m = item.meta
 530     if isinstance(m, Metadata) and m.size is not None:
 531         return m.size
 532     return _compute_item_size(repo, item)
 533
 534 def tree_data_reader(repo, oid):
 535     """Return an open reader for all of the data contained within oid.  If
 536     oid refers to a tree, recursively concatenate all of its contents."""
 537     return _FileReader(repo, oid)
 538
 539 def fopen(repo, item):
 540     """Return an open reader for the given file item."""
 541     assert S_ISREG(item_mode(item))
 542     return tree_data_reader(repo, item.oid)
 543
 544 def _commit_item_from_data(oid, data):
 545     info = parse_commit(data)
 546     return Commit(meta=default_dir_mode,
 547                   oid=info.tree.decode('hex'),
 548                   coid=oid)
 549
 550 def _commit_item_from_oid(repo, oid, require_meta):
 551     commit = cache_get_commit_item(oid, need_meta=require_meta)
 552     if commit and ((not require_meta) or isinstance(commit.meta, Metadata)):
 553         return commit
 554     it = repo.cat(oid.encode('hex'))
 555     _, typ, size = next(it)
 556     assert typ == 'commit'
 557     commit = _commit_item_from_data(oid, ''.join(it))
 558     if require_meta:
 559         meta = _find_treeish_oid_metadata(repo, commit.oid)
 560         if meta:
 561             commit = commit._replace(meta=meta)
 562     commit_key = b'itm:' + oid
 563     cache_notice(commit_key, commit)
 564     return commit
 565
 566 def _revlist_item_from_oid(repo, oid, require_meta):
 567     commit = _commit_item_from_oid(repo, oid, require_meta)
 568     return RevList(oid=oid, meta=commit.meta)
 569
 570 def root_items(repo, names=None, want_meta=True):
 571     """Yield (name, item) for the items in '/' in the VFS.  Return
 572     everything if names is logically false, otherwise return only
 573     items with a name in the collection.
 574
 575     """
 576     # FIXME: what about non-leaf refs like 'refs/heads/foo/bar/baz?
 577
 578     global _root, _tags
 579     if not names:
 580         yield '.', _root
 581         yield '.tag', _tags
 582         # FIXME: maybe eventually support repo.clone() or something
 583         # and pass in two repos, so we can drop the tuple() and stream
 584         # in parallel (i.e. meta vs refs).
 585         for name, oid in tuple(repo.refs([], limit_to_heads=True)):
 586             assert(name.startswith('refs/heads/'))
 587             yield name[11:], _revlist_item_from_oid(repo, oid, want_meta)
 588         return
 589
 590     if '.' in names:
 591         yield '.', _root
 592     if '.tag' in names:
 593         yield '.tag', _tags
 594     for ref in names:
 595         if ref in ('.', '.tag'):
 596             continue
 597         it = repo.cat('refs/heads/' + ref)
 598         oidx, typ, size = next(it)
 599         if not oidx:
 600             for _ in it: pass
 601             continue
 602         assert typ == 'commit'
 603         commit = parse_commit(''.join(it))
 604         yield ref, _revlist_item_from_oid(repo, oidx.decode('hex'), want_meta)
 605
 606 def ordered_tree_entries(tree_data, bupm=None):
 607     """Yields (name, mangled_name, kind, gitmode, oid) for each item in
 608     tree, sorted by name.
 609
 610     """
 611     # Sadly, the .bupm entries currently aren't in git tree order,
 612     # i.e. they don't account for the fact that git sorts trees
 613     # (including our chunked trees) as if their names ended with "/",
 614     # so "fo" sorts after "fo." iff fo is a directory.  This makes
 615     # streaming impossible when we need the metadata.
 616     def result_from_tree_entry(tree_entry):
 617         gitmode, mangled_name, oid = tree_entry
 618         name, kind = git.demangle_name(mangled_name, gitmode)
 619         return name, mangled_name, kind, gitmode, oid
 620
 621     tree_ents = (result_from_tree_entry(x) for x in tree_decode(tree_data))
 622     if bupm:
 623         tree_ents = sorted(tree_ents, key=lambda x: x[0])
 624     for ent in tree_ents:
 625         yield ent
 626
 627 def tree_items(oid, tree_data, names=frozenset(), bupm=None):
 628
 629     def tree_item(ent_oid, kind, gitmode):
 630         if kind == BUP_CHUNKED:
 631             meta = Metadata.read(bupm) if bupm else default_file_mode
 632             return Chunky(oid=ent_oid, meta=meta)
 633
 634         if S_ISDIR(gitmode):
 635             # No metadata here (accessable via '.' inside ent_oid).
 636             return Item(meta=default_dir_mode, oid=ent_oid)
 637
 638         return Item(oid=ent_oid,
 639                     meta=(Metadata.read(bupm) if bupm \
 640                           else _default_mode_for_gitmode(gitmode)))
 641
 642     assert len(oid) == 20
 643     if not names:
 644         dot_meta = _read_dir_meta(bupm) if bupm else default_dir_mode
 645         yield '.', Item(oid=oid, meta=dot_meta)
 646         tree_entries = ordered_tree_entries(tree_data, bupm)
 647         for name, mangled_name, kind, gitmode, ent_oid in tree_entries:
 648             if mangled_name == '.bupm':
 649                 continue
 650             assert name != '.'
 651             yield name, tree_item(ent_oid, kind, gitmode)
 652         return
 653
 654     # Assumes the tree is properly formed, i.e. there are no
 655     # duplicates, and entries will be in git tree order.
 656     if type(names) not in (frozenset, set):
 657         names = frozenset(names)
 658     remaining = len(names)
 659
 660     # Account for the bupm sort order issue (cf. ordered_tree_entries above)
 661     last_name = max(names) if bupm else max(names) + '/'
 662
 663     if '.' in names:
 664         dot_meta = _read_dir_meta(bupm) if bupm else default_dir_mode
 665         yield '.', Item(oid=oid, meta=dot_meta)
 666         if remaining == 1:
 667             return
 668         remaining -= 1
 669
 670     tree_entries = ordered_tree_entries(tree_data, bupm)
 671     for name, mangled_name, kind, gitmode, ent_oid in tree_entries:
 672         if mangled_name == '.bupm':
 673             continue
 674         assert name != '.'
 675         if name not in names:
 676             if name > last_name:
 677                 break  # given bupm sort order, we're finished
 678             if (kind == BUP_CHUNKED or not S_ISDIR(gitmode)) and bupm:
 679                 Metadata.read(bupm)
 680             continue
 681         yield name, tree_item(ent_oid, kind, gitmode)
 682         if remaining == 1:
 683             break
 684         remaining -= 1
 685
 686 def tree_items_with_meta(repo, oid, tree_data, names):
 687     # For now, the .bupm order doesn't quite match git's, and we don't
 688     # load the tree data incrementally anyway, so we just work in RAM
 689     # via tree_data.
 690     assert len(oid) == 20
 691     bupm = None
 692     for _, mangled_name, sub_oid in tree_decode(tree_data):
 693         if mangled_name == '.bupm':
 694             bupm = _FileReader(repo, sub_oid)
 695             break
 696         if mangled_name > '.bupm':
 697             break
 698     for item in tree_items(oid, tree_data, names, bupm):
 699         yield item
 700
 701 _save_name_rx = re.compile(r'^\d\d\d\d-\d\d-\d\d-\d{6}(-\d+)?$')
 702
 703 def _reverse_suffix_duplicates(strs):
 704     """Yields the elements of strs, with any runs of duplicate values
 705     suffixed with -N suffixes, where the zero padded integer N
 706     decreases to 0 by 1 (e.g. 10, 09, ..., 00).
 707
 708     """
 709     for name, duplicates in groupby(strs):
 710         ndup = len(tuple(duplicates))
 711         if ndup == 1:
 712             yield name
 713         else:
 714             ndig = len(str(ndup - 1))
 715             fmt = '%s-' + '%0' + str(ndig) + 'd'
 716             for i in range(ndup - 1, -1, -1):
 717                 yield fmt % (name, i)
 718
 719 def parse_rev(f):
 720     items = f.readline().split(None)
 721     assert len(items) == 2
 722     tree, auth_sec = items
 723     return tree.decode('hex'), int(auth_sec)
 724
 725 def _name_for_rev(rev):
 726     commit_oidx, (tree_oid, utc) = rev
 727     return strftime('%Y-%m-%d-%H%M%S', localtime(utc))
 728
 729 def _item_for_rev(rev):
 730     commit_oidx, (tree_oid, utc) = rev
 731     coid = commit_oidx.decode('hex')
 732     item = cache_get_commit_item(coid, need_meta=False)
 733     if item:
 734         return item
 735     item = Commit(meta=default_dir_mode, oid=tree_oid, coid=coid)
 736     commit_key = b'itm:' + coid
 737     cache_notice(commit_key, item)
 738     return item
 739
 740 def cache_commit(repo, oid):
 741     """Build, cache, and return a "name -> commit_item" dict of the entire
 742     commit rev-list.
 743
 744     """
 745     # For now, always cache with full metadata
 746     entries = {}
 747     entries['.'] = _revlist_item_from_oid(repo, oid, True)
 748     revs = repo.rev_list((oid.encode('hex'),), format='%T %at',
 749                          parse=parse_rev)
 750     rev_items, rev_names = tee(revs)
 751     revs = None  # Don't disturb the tees
 752     rev_names = _reverse_suffix_duplicates(_name_for_rev(x) for x in rev_names)
 753     rev_items = (_item_for_rev(x) for x in rev_items)
 754     tip = None
 755     for item in rev_items:
 756         name = next(rev_names)
 757         tip = tip or (name, item)
 758         entries[name] = item
 759     entries['latest'] = FakeLink(meta=default_symlink_mode, target=tip[0])
 760     revlist_key = b'rvl:' + tip[1].coid
 761     cache_notice(revlist_key, entries)
 762     return entries
 763
 764 def revlist_items(repo, oid, names):
 765     assert len(oid) == 20
 766
 767     # Special case '.' instead of caching the whole history since it's
 768     # the only way to get the metadata for the commit.
 769     if names and all(x == '.' for x in names):
 770         yield '.', _revlist_item_from_oid(repo, oid, True)
 771         return
 772
 773     # For now, don't worry about the possibility of the contents being
 774     # "too big" for the cache.
 775     revlist_key = b'rvl:' + oid
 776     entries = cache_get(revlist_key)
 777     if not entries:
 778         entries = cache_commit(repo, oid)
 779
 780     if not names:
 781         for name in sorted(entries.keys()):
 782             yield name, entries[name]
 783         return
 784
 785     names = frozenset(name for name in names
 786                       if _save_name_rx.match(name) or name in ('.', 'latest'))
 787
 788     if '.' in names:
 789         yield '.', entries['.']
 790     for name in (n for n in names if n != '.'):
 791         commit = entries.get(name)
 792         if commit:
 793             yield name, commit
 794
 795 def tags_items(repo, names):
 796     global _tags
 797
 798     def tag_item(oid):
 799         assert len(oid) == 20
 800         oidx = oid.encode('hex')
 801         it = repo.cat(oidx)
 802         _, typ, size = next(it)
 803         if typ == 'commit':
 804             return cache_get_commit_item(oid, need_meta=False) \
 805                 or _commit_item_from_data(oid, ''.join(it))
 806         for _ in it: pass
 807         if typ == 'blob':
 808             return Item(meta=default_file_mode, oid=oid)
 809         elif typ == 'tree':
 810             return Item(meta=default_dir_mode, oid=oid)
 811         raise Exception('unexpected tag type ' + typ + ' for tag ' + name)
 812
 813     if not names:
 814         yield '.', _tags
 815         # We have to pull these all into ram because tag_item calls cat()
 816         for name, oid in tuple(repo.refs(names, limit_to_tags=True)):
 817             assert(name.startswith('refs/tags/'))
 818             name = name[10:]
 819             yield name, tag_item(oid)
 820         return
 821
 822     # Assumes no duplicate refs
 823     if type(names) not in (frozenset, set):
 824         names = frozenset(names)
 825     remaining = len(names)
 826     last_name = max(names)
 827     if '.' in names:
 828         yield '.', _tags
 829         if remaining == 1:
 830             return
 831         remaining -= 1
 832
 833     for name, oid in repo.refs(names, limit_to_tags=True):
 834         assert(name.startswith('refs/tags/'))
 835         name = name[10:]
 836         if name > last_name:
 837             return
 838         if name not in names:
 839             continue
 840         yield name, tag_item(oid)
 841         if remaining == 1:
 842             return
 843         remaining -= 1
 844
 845 def contents(repo, item, names=None, want_meta=True):
 846     """Yields information about the items contained in item.  Yields
 847     (name, item) for each name in names, if the name exists, in an
 848     unspecified order.  If there are no names, then yields (name,
 849     item) for all items, including, a first item named '.'
 850     representing the container itself.
 851
 852     The meta value for any directories other than '.' will be a
 853     default directory mode, not a Metadata object.  This is because
 854     the actual metadata for a directory is stored inside the directory
 855     (see fill_in_metadata_if_dir() or ensure_item_has_metadata()).
 856
 857     Note that want_meta is advisory.  For any given item, item.meta
 858     might be a Metadata instance or a mode, and if the former,
 859     meta.size might be None.  Missing sizes can be computed via via
 860     item_size() or augment_item_meta(..., include_size=True).
 861
 862     Do not modify any item.meta Metadata instances directly.  If
 863     needed, make a copy via item.meta.copy() and modify that instead.
 864
 865     """
 866     # Q: are we comfortable promising '.' first when no names?
 867     global _root, _tags
 868     assert repo
 869     assert S_ISDIR(item_mode(item))
 870     item_t = type(item)
 871     if item_t in real_tree_types:
 872         it = repo.cat(item.oid.encode('hex'))
 873         _, obj_t, size = next(it)
 874         data = ''.join(it)
 875         if obj_t != 'tree':
 876             for _ in it: pass
 877             # Note: it shouldn't be possible to see an Item with type
 878             # 'commit' since a 'commit' should always produce a Commit.
 879             raise Exception('unexpected git ' + obj_t)
 880         if want_meta:
 881             item_gen = tree_items_with_meta(repo, item.oid, data, names)
 882         else:
 883             item_gen = tree_items(item.oid, data, names)
 884     elif item_t == RevList:
 885         item_gen = revlist_items(repo, item.oid, names)
 886     elif item_t == Root:
 887         item_gen = root_items(repo, names, want_meta)
 888     elif item_t == Tags:
 889         item_gen = tags_items(repo, names)
 890     else:
 891         raise Exception('unexpected VFS item ' + str(item))
 892     for x in item_gen:
 893         yield x
 894
 895 def _resolve_path(repo, path, parent=None, want_meta=True, follow=True):
 896     cache_key = b'res:%d%d%d:%s\0%s' \
 897                 % (bool(want_meta), bool(follow), repo.id(),
 898                    ('/'.join(x[0] for x in parent) if parent else ''),
 899                    '/'.join(path))
 900     resolution = cache_get(cache_key)
 901     if resolution:
 902         return resolution
 903
 904     def notice_resolution(r):
 905         cache_notice(cache_key, r)
 906         return r
 907
 908     def raise_dir_required_but_not_dir(path, parent, past):
 909         raise IOError(ENOTDIR,
 910                       "path %r%s resolves to non-directory %r"
 911                       % (path,
 912                          ' (relative to %r)' % parent if parent else '',
 913                          past),
 914                       terminus=past)
 915     global _root
 916     assert repo
 917     assert len(path)
 918     if parent:
 919         for x in parent:
 920             assert len(x) == 2
 921             assert type(x[0]) in (bytes, str)
 922             assert type(x[1]) in item_types
 923         assert parent[0][1] == _root
 924         if not S_ISDIR(item_mode(parent[-1][1])):
 925             raise IOError(ENOTDIR,
 926                           'path resolution parent %r is not a directory'
 927                           % (parent,))
 928     is_absolute, must_be_dir, future = _decompose_path(path)
 929     if must_be_dir:
 930         follow = True
 931     if not future:  # path was effectively '.' or '/'
 932         if is_absolute:
 933             return notice_resolution((('', _root),))
 934         if parent:
 935             return notice_resolution(tuple(parent))
 936         return notice_resolution((('', _root),))
 937     if is_absolute:
 938         past = [('', _root)]
 939     else:
 940         past = list(parent) if parent else [('', _root)]
 941     hops = 0
 942     while True:
 943         if not future:
 944             if must_be_dir and not S_ISDIR(item_mode(past[-1][1])):
 945                 raise_dir_required_but_not_dir(path, parent, past)
 946             return notice_resolution(tuple(past))
 947         segment = future.pop()
 948         if segment == '..':
 949             assert len(past) > 0
 950             if len(past) > 1:  # .. from / is /
 951                 assert S_ISDIR(item_mode(past[-1][1]))
 952                 past.pop()
 953         else:
 954             parent_name, parent_item = past[-1]
 955             wanted = (segment,) if not want_meta else ('.', segment)
 956             items = tuple(contents(repo, parent_item, names=wanted,
 957                                    want_meta=want_meta))
 958             if not want_meta:
 959                 item = items[0][1] if items else None
 960             else:  # First item will be '.' and have the metadata
 961                 item = items[1][1] if len(items) == 2 else None
 962                 dot, dot_item = items[0]
 963                 assert dot == '.'
 964                 past[-1] = parent_name, parent_item
 965             if not item:
 966                 past.append((segment, None),)
 967                 return notice_resolution(tuple(past))
 968             mode = item_mode(item)
 969             if not S_ISLNK(mode):
 970                 if not S_ISDIR(mode):
 971                     past.append((segment, item),)
 972                     if future:
 973                         raise IOError(ENOTDIR,
 974                                       'path %r%s ends internally in non-directory here: %r'
 975                                       % (path,
 976                                          ' (relative to %r)' % parent if parent else '',
 977                                          past),
 978                                       terminus=past)
 979                     if must_be_dir:
 980                         raise_dir_required_but_not_dir(path, parent, past)
 981                     return notice_resolution(tuple(past))
 982                 # It's treeish
 983                 if want_meta and type(item) in real_tree_types:
 984                     dir_meta = _find_treeish_oid_metadata(repo, item.oid)
 985                     if dir_meta:
 986                         item = item._replace(meta=dir_meta)
 987                 past.append((segment, item))
 988             else:  # symlink
 989                 if not future and not follow:
 990                     past.append((segment, item),)
 991                     continue
 992                 if hops > 100:
 993                     raise IOError(ELOOP,
 994                                   'too many symlinks encountered while resolving %r%s'
 995                                   % (path, ' relative to %r' % parent if parent else ''),
 996                                   terminus=tuple(past + [(segment, item)]))
 997                 target = readlink(repo, item)
 998                 is_absolute, _, target_future = _decompose_path(target)
 999                 if is_absolute:
1000                     if not target_future:  # path was effectively '/'
1001                         return notice_resolution((('', _root),))
1002                     past = [('', _root)]
1003                     future = target_future
1004                 else:
1005                     future.extend(target_future)
1006                 hops += 1
1007
1008 def resolve(repo, path, parent=None, want_meta=True, follow=True):
1009     """Follow the path in the virtual filesystem and return a tuple
1010     representing the location, if any, denoted by the path.  Each
1011     element in the result tuple will be (name, info), where info will
1012     be a VFS item that can be passed to functions like item_mode().
1013
1014     If follow is false, and if the final path element is a symbolic
1015     link, don't follow it, just return it in the result.
1016
1017     If a path segment that does not exist is encountered during
1018     resolution, the result will represent the location of the missing
1019     item, and that item in the result will be None.
1020
1021     Any attempt to traverse a non-directory will raise a VFS ENOTDIR
1022     IOError exception.
1023
1024     Any symlinks along the path, including at the end, will be
1025     resolved.  A VFS IOError with the errno attribute set to ELOOP
1026     will be raised if too many symlinks are traversed while following
1027     the path.  That exception is effectively like a normal
1028     ELOOP IOError exception, but will include a terminus element
1029     describing the location of the failure, which will be a tuple of
1030     (name, info) elements.
1031
1032     The parent, if specified, must be a sequence of (name, item)
1033     tuples, and will provide the starting point for the resolution of
1034     the path.  If no parent is specified, resolution will start at
1035     '/'.
1036
1037     The result may include elements of parent directly, so they must
1038     not be modified later.  If this is a concern, pass in "name,
1039     copy_item(item) for name, item in parent" instead.
1040
1041     When want_meta is true, detailed metadata will be included in each
1042     result item if it's avaiable, otherwise item.meta will be an
1043     integer mode.  The metadata size may or may not be provided, but
1044     can be computed by item_size() or augment_item_meta(...,
1045     include_size=True).  Setting want_meta=False is rarely desirable
1046     since it can limit the VFS to just the metadata git itself can
1047     represent, and so, as an example, fifos and sockets will appear to
1048     be regular files (e.g. S_ISREG(item_mode(item)) will be true) .
1049     But the option is provided because it may be more efficient when
1050     only the path names or the more limited metadata is sufficient.
1051
1052     Do not modify any item.meta Metadata instances directly.  If
1053     needed, make a copy via item.meta.copy() and modify that instead.
1054
1055     """
1056     if repo.is_remote():
1057         # Redirect to the more efficient remote version
1058         return repo.resolve(path, parent=parent, want_meta=want_meta,
1059                             follow=follow)
1060     result = _resolve_path(repo, path, parent=parent, want_meta=want_meta,
1061                            follow=follow)
1062     _, leaf_item = result[-1]
1063     if leaf_item and follow:
1064         assert not S_ISLNK(item_mode(leaf_item))
1065     return result
1066
1067 def try_resolve(repo, path, parent=None, want_meta=True):
1068     """If path does not refer to a symlink, does not exist, or refers to a
1069     valid symlink, behave exactly like resolve(..., follow=True).  If
1070     path refers to an invalid symlink, behave like resolve(...,
1071     follow=False).
1072
1073     """
1074     res = resolve(repo, path, parent=parent, want_meta=want_meta, follow=False)
1075     leaf_name, leaf_item = res[-1]
1076     if not leaf_item:
1077         return res
1078     if not S_ISLNK(item_mode(leaf_item)):
1079         return res
1080     follow = resolve(repo, leaf_name, parent=res[:-1], want_meta=want_meta)
1081     follow_name, follow_item = follow[-1]
1082     if follow_item:
1083         return follow
1084     return res
1085
1086 def augment_item_meta(repo, item, include_size=False):
1087     """Ensure item has a Metadata instance for item.meta.  If item.meta is
1088     currently a mode, replace it with a compatible "fake" Metadata
1089     instance.  If include_size is true, ensure item.meta.size is
1090     correct, computing it if needed.  If item.meta is a Metadata
1091     instance, this call may modify it in place or replace it.
1092
1093     """
1094     # If we actually had parallelism, we'd need locking...
1095     assert repo
1096     m = item.meta
1097     if isinstance(m, Metadata):
1098         if include_size and m.size is None:
1099             m.size = _compute_item_size(repo, item)
1100             return item._replace(meta=m)
1101         return item
1102     # m is mode
1103     meta = Metadata()
1104     meta.mode = m
1105     meta.uid = meta.gid = meta.atime = meta.mtime = meta.ctime = 0
1106     if S_ISLNK(m):
1107         if isinstance(item, FakeLink):
1108             target = item.target
1109         else:
1110             target = _readlink(repo, item.oid)
1111         meta.symlink_target = target
1112         meta.size = len(target)
1113     elif include_size:
1114         meta.size = _compute_item_size(repo, item)
1115     return item._replace(meta=meta)
1116
1117 def fill_in_metadata_if_dir(repo, item):
1118     """If item is a directory and item.meta is not a Metadata instance,
1119     attempt to find the metadata for the directory.  If found, return
1120     a new item augmented to include that metadata.  Otherwise, return
1121     item.  May be useful for the output of contents().
1122
1123     """
1124     if S_ISDIR(item_mode(item)) and not isinstance(item.meta, Metadata):
1125         items = tuple(contents(repo, item, ('.',), want_meta=True))
1126         assert len(items) == 1
1127         assert items[0][0] == '.'
1128         item = items[0][1]
1129     return item
1130
1131 def ensure_item_has_metadata(repo, item, include_size=False):
1132     """If item is a directory, attempt to find and add its metadata.  If
1133     the item still doesn't have a Metadata instance for item.meta,
1134     give it one via augment_item_meta().  May be useful for the output
1135     of contents().
1136
1137     """
1138     return augment_item_meta(repo,
1139                              fill_in_metadata_if_dir(repo, item),
1140                              include_size=include_size)