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