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, FakeLink):
 511         return item.target
 512     if isinstance(item.meta, Metadata):
 513         target = item.meta.symlink_target
 514         if target:
 515             return 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         if isinstance(item, FakeLink):
 525             return len(item.target)
 526         return len(_readlink(repo, item.oid))
 527     return 0
 528
 529 def item_size(repo, item):
 530     """Return the size of item, computing it if necessary."""
 531     m = item.meta
 532     if isinstance(m, Metadata) and m.size is not None:
 533         return m.size
 534     return _compute_item_size(repo, item)
 535
 536 def tree_data_reader(repo, oid):
 537     """Return an open reader for all of the data contained within oid.  If
 538     oid refers to a tree, recursively concatenate all of its contents."""
 539     return _FileReader(repo, oid)
 540
 541 def fopen(repo, item):
 542     """Return an open reader for the given file item."""
 543     assert S_ISREG(item_mode(item))
 544     return tree_data_reader(repo, item.oid)
 545
 546 def _commit_item_from_data(oid, data):
 547     info = parse_commit(data)
 548     return Commit(meta=default_dir_mode,
 549                   oid=info.tree.decode('hex'),
 550                   coid=oid)
 551
 552 def _commit_item_from_oid(repo, oid, require_meta):
 553     commit = cache_get_commit_item(oid, need_meta=require_meta)
 554     if commit and ((not require_meta) or isinstance(commit.meta, Metadata)):
 555         return commit
 556     it = repo.cat(oid.encode('hex'))
 557     _, typ, size = next(it)
 558     assert typ == 'commit'
 559     commit = _commit_item_from_data(oid, ''.join(it))
 560     if require_meta:
 561         meta = _find_treeish_oid_metadata(repo, commit.oid)
 562         if meta:
 563             commit = commit._replace(meta=meta)
 564     commit_key = b'itm:' + oid
 565     cache_notice(commit_key, commit)
 566     return commit
 567
 568 def _revlist_item_from_oid(repo, oid, require_meta):
 569     commit = _commit_item_from_oid(repo, oid, require_meta)
 570     return RevList(oid=oid, meta=commit.meta)
 571
 572 def root_items(repo, names=None, want_meta=True):
 573     """Yield (name, item) for the items in '/' in the VFS.  Return
 574     everything if names is logically false, otherwise return only
 575     items with a name in the collection.
 576
 577     """
 578     # FIXME: what about non-leaf refs like 'refs/heads/foo/bar/baz?
 579
 580     global _root, _tags
 581     if not names:
 582         yield '.', _root
 583         yield '.tag', _tags
 584         # FIXME: maybe eventually support repo.clone() or something
 585         # and pass in two repos, so we can drop the tuple() and stream
 586         # in parallel (i.e. meta vs refs).
 587         for name, oid in tuple(repo.refs([], limit_to_heads=True)):
 588             assert(name.startswith('refs/heads/'))
 589             yield name[11:], _revlist_item_from_oid(repo, oid, want_meta)
 590         return
 591
 592     if '.' in names:
 593         yield '.', _root
 594     if '.tag' in names:
 595         yield '.tag', _tags
 596     for ref in names:
 597         if ref in ('.', '.tag'):
 598             continue
 599         it = repo.cat('refs/heads/' + ref)
 600         oidx, typ, size = next(it)
 601         if not oidx:
 602             for _ in it: pass
 603             continue
 604         assert typ == 'commit'
 605         commit = parse_commit(''.join(it))
 606         yield ref, _revlist_item_from_oid(repo, oidx.decode('hex'), want_meta)
 607
 608 def ordered_tree_entries(tree_data, bupm=None):
 609     """Yields (name, mangled_name, kind, gitmode, oid) for each item in
 610     tree, sorted by name.
 611
 612     """
 613     # Sadly, the .bupm entries currently aren't in git tree order,
 614     # but in unmangled name order. They _do_ account for the fact
 615     # that git sorts trees (including chunked trees) as if their
 616     # names ended with "/" (so "fo" sorts after "fo." iff fo is a
 617     # directory), but we apply this on the unmangled names in save
 618     # rather than on the mangled names.
 619     # This makes streaming impossible when we need the metadata.
 620     def result_from_tree_entry(tree_entry):
 621         gitmode, mangled_name, oid = tree_entry
 622         name, kind = git.demangle_name(mangled_name, gitmode)
 623         return name, mangled_name, kind, gitmode, oid
 624
 625     tree_ents = (result_from_tree_entry(x) for x in tree_decode(tree_data))
 626     if bupm:
 627         tree_ents = sorted(tree_ents, key=lambda x: x[0])
 628     for ent in tree_ents:
 629         yield ent
 630
 631 def tree_items(oid, tree_data, names=frozenset(), bupm=None):
 632
 633     def tree_item(ent_oid, kind, gitmode):
 634         if kind == BUP_CHUNKED:
 635             meta = Metadata.read(bupm) if bupm else default_file_mode
 636             return Chunky(oid=ent_oid, meta=meta)
 637
 638         if S_ISDIR(gitmode):
 639             # No metadata here (accessable via '.' inside ent_oid).
 640             return Item(meta=default_dir_mode, oid=ent_oid)
 641
 642         meta = Metadata.read(bupm) if bupm else None
 643         # handle the case of metadata being empty/missing in bupm
 644         # (or there not being bupm at all)
 645         if meta is None:
 646             meta = _default_mode_for_gitmode(gitmode)
 647         return Item(oid=ent_oid, meta=meta)
 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)