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