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