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