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
  20 The want_meta argument is advisory for calls that accept it, and it
  21 may not be honored.  Callers must be able to handle an item.meta value
  22 that is either an instance of Metadata or an integer mode, perhaps
  23 via item_mode() or augment_item_meta().
  24
  25 Setting want_meta=False is rarely desirable since it can limit the VFS
  26 to only the metadata that git itself can represent, and so for
  27 example, fifos and sockets will appear to be regular files
  28 (e.g. S_ISREG(item_mode(item)) will be true).  But the option is still
  29 provided because it may be more efficient when just the path names or
  30 the more limited metadata is sufficient.
  31
  32 Any given metadata object's size may be None, in which case the size
  33 can be computed via item_size() or augment_item_meta(...,
  34 include_size=True).
  35
  36 When traversing a directory using functions like contents(), the meta
  37 value for any directories other than '.' will be a default directory
  38 mode, not a Metadata object.  This is because the actual metadata for
  39 a directory is stored inside the directory (see
  40 fill_in_metadata_if_dir() or ensure_item_has_metadata()).
  41
  42 Commit items represent commits (e.g. /.tag/some-commit or
  43 /foo/latest), and for most purposes, they appear as the underlying
  44 tree.  S_ISDIR(item_mode(item)) will return true for both tree Items
  45 and Commits and the commit's oid is the tree hash; the commit hash is
  46 item.coid.
  47
  48 """
  49
  50 from __future__ import absolute_import, print_function
  51 from collections import namedtuple
  52 from errno import ELOOP, ENOENT, ENOTDIR
  53 from itertools import chain, dropwhile, groupby, izip, tee
  54 from random import randrange
  55 from stat import S_IFDIR, S_IFLNK, S_IFREG, S_ISDIR, S_ISLNK, S_ISREG
  56 from time import localtime, strftime
  57 import exceptions, re, sys
  58
  59 from bup import client, git, metadata
  60 from bup.compat import range
  61 from bup.git import BUP_CHUNKED, cp, get_commit_items, parse_commit, tree_decode
  62 from bup.helpers import debug2, last
  63 from bup.metadata import Metadata
  64 from bup.repo import LocalRepo, RemoteRepo
  65
  66
  67 class IOError(exceptions.IOError):
  68     def __init__(self, errno, message, terminus=None):
  69         exceptions.IOError.__init__(self, errno, message)
  70         self.terminus = terminus
  71
  72 default_file_mode = S_IFREG | 0o644
  73 default_dir_mode = S_IFDIR | 0o755
  74 default_symlink_mode = S_IFLNK | 0o755
  75
  76 def _default_mode_for_gitmode(gitmode):
  77     if S_ISREG(gitmode):
  78         return default_file_mode
  79     if S_ISDIR(gitmode):
  80         return default_dir_mode
  81     if S_ISLNK(gitmode):
  82         return default_symlink_mode
  83     raise Exception('unexpected git mode ' + oct(gitmode))
  84
  85 def _normal_or_chunked_file_size(repo, oid):
  86     """Return the size of the normal or chunked file indicated by oid."""
  87     # FIXME: --batch-format CatPipe?
  88     it = repo.cat(oid.encode('hex'))
  89     _, obj_t, size = next(it)
  90     ofs = 0
  91     while obj_t == 'tree':
  92         mode, name, last_oid = last(tree_decode(''.join(it)))
  93         ofs += int(name, 16)
  94         it = repo.cat(last_oid.encode('hex'))
  95         _, obj_t, size = next(it)
  96     return ofs + sum(len(b) for b in it)
  97
  98 def _tree_chunks(repo, tree, startofs):
  99     "Tree should be a sequence of (name, mode, hash) as per tree_decode()."
 100     assert(startofs >= 0)
 101     # name is the chunk's hex offset in the original file
 102     tree = dropwhile(lambda (_1, name, _2): int(name, 16) < startofs, tree)
 103     for mode, name, oid in tree:
 104         ofs = int(name, 16)
 105         skipmore = startofs - ofs
 106         if skipmore < 0:
 107             skipmore = 0
 108         it = repo.cat(oid.encode('hex'))
 109         _, obj_t, size = next(it)
 110         data = ''.join(it)
 111         if S_ISDIR(mode):
 112             assert obj_t == 'tree'
 113             for b in _tree_chunks(repo, tree_decode(data), skipmore):
 114                 yield b
 115         else:
 116             assert obj_t == 'blob'
 117             yield data[skipmore:]
 118
 119 class _ChunkReader:
 120     def __init__(self, repo, oid, startofs):
 121         it = repo.cat(oid.encode('hex'))
 122         _, obj_t, size = next(it)
 123         isdir = obj_t == 'tree'
 124         data = ''.join(it)
 125         if isdir:
 126             self.it = _tree_chunks(repo, tree_decode(data), startofs)
 127             self.blob = None
 128         else:
 129             self.it = None
 130             self.blob = data[startofs:]
 131         self.ofs = startofs
 132
 133     def next(self, size):
 134         out = ''
 135         while len(out) < size:
 136             if self.it and not self.blob:
 137                 try:
 138                     self.blob = self.it.next()
 139                 except StopIteration:
 140                     self.it = None
 141             if self.blob:
 142                 want = size - len(out)
 143                 out += self.blob[:want]
 144                 self.blob = self.blob[want:]
 145             if not self.it:
 146                 break
 147         debug2('next(%d) returned %d\n' % (size, len(out)))
 148         self.ofs += len(out)
 149         return out
 150
 151 class _FileReader(object):
 152     def __init__(self, repo, oid, known_size=None):
 153         assert len(oid) == 20
 154         self.oid = oid
 155         self.ofs = 0
 156         self.reader = None
 157         self._repo = repo
 158         self._size = known_size
 159
 160     def _compute_size(self):
 161         if not self._size:
 162             self._size = _normal_or_chunked_file_size(self._repo, self.oid)
 163         return self._size
 164
 165     def seek(self, ofs):
 166         if ofs < 0:
 167             raise IOError(errno.EINVAL, 'Invalid argument')
 168         if ofs > self._compute_size():
 169             raise IOError(errno.EINVAL, 'Invalid argument')
 170         self.ofs = ofs
 171
 172     def tell(self):
 173         return self.ofs
 174
 175     def read(self, count=-1):
 176         if count < 0:
 177             count = self._compute_size() - self.ofs
 178         if not self.reader or self.reader.ofs != self.ofs:
 179             self.reader = _ChunkReader(self._repo, self.oid, self.ofs)
 180         try:
 181             buf = self.reader.next(count)
 182         except:
 183             self.reader = None
 184             raise  # our offsets will be all screwed up otherwise
 185         self.ofs += len(buf)
 186         return buf
 187
 188     def close(self):
 189         pass
 190
 191     def __enter__(self):
 192         return self
 193     def __exit__(self, type, value, traceback):
 194         self.close()
 195         return False
 196
 197 _multiple_slashes_rx = re.compile(r'//+')
 198
 199 def _decompose_path(path):
 200     """Return a boolean indicating whether the path is absolute, and a
 201     reversed list of path elements, omitting any occurrences of "."
 202     and ignoring any leading or trailing slash.  If the path is
 203     effectively '/' or '.', return an empty list.
 204
 205     """
 206     path = re.sub(_multiple_slashes_rx, '/', path)
 207     if path == '/':
 208         return True, True, []
 209     is_absolute = must_be_dir = False
 210     if path.startswith('/'):
 211         is_absolute = True
 212         path = path[1:]
 213     for suffix in ('/', '/.'):
 214         if path.endswith(suffix):
 215             must_be_dir = True
 216             path = path[:-len(suffix)]
 217     parts = [x for x in path.split('/') if x != '.']
 218     parts.reverse()
 219     if not parts:
 220         must_be_dir = True  # e.g. path was effectively '.' or '/', etc.
 221     return is_absolute, must_be_dir, parts
 222
 223
 224 Item = namedtuple('Item', ('meta', 'oid'))
 225 Chunky = namedtuple('Chunky', ('meta', 'oid'))
 226 Root = namedtuple('Root', ('meta'))
 227 Tags = namedtuple('Tags', ('meta'))
 228 RevList = namedtuple('RevList', ('meta', 'oid'))
 229 Commit = namedtuple('Commit', ('meta', 'oid', 'coid'))
 230
 231 item_types = frozenset((Item, Chunky, Root, Tags, RevList, Commit))
 232 real_tree_types = frozenset((Item, Commit))
 233
 234 _root = Root(meta=default_dir_mode)
 235 _tags = Tags(meta=default_dir_mode)
 236
 237
 238 ### vfs cache
 239
 240 ### A general purpose shared cache with (currently) cheap random
 241 ### eviction.  There is currently no weighting so a single commit item
 242 ### is just as likely to be evicted as an entire "rev-list".  See
 243 ### is_valid_cache_key for a description of the expected content.
 244
 245 _cache = {}
 246 _cache_keys = []
 247 _cache_max_items = 30000
 248
 249 def clear_cache():
 250     global _cache, _cache_keys
 251     _cache = {}
 252     _cache_keys = []
 253
 254 def is_valid_cache_key(x):
 255     """Return logically true if x looks like it could be a valid cache key
 256     (with respect to structure).  Current valid cache entries:
 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 bytes:
 264         if len(x) == 20:
 265             return True
 266         if len(x) == 22 and x.endswith(b':r'):
 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
 290 def cache_get_commit_item(oid, need_meta=True):
 291     """Return the requested tree item if it can be found in the cache.
 292     When need_meta is true don't return a cached item that only has a
 293     mode."""
 294     # tree might be stored independently, or as '.' with its entries.
 295     item = cache_get(oid)
 296     if item:
 297         if not need_meta:
 298             return item
 299         if isinstance(item.meta, Metadata):
 300             return item
 301     entries = cache_get(oid + b':r')
 302     if entries:
 303         return entries['.']
 304
 305 def cache_get_revlist_item(oid, need_meta=True):
 306     commit = cache_get_commit_item(oid, need_meta=need_meta)
 307     if commit:
 308         return RevList(oid=oid, meta=commit.meta)
 309
 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
 738     if item_t in real_tree_types:
 739         it = repo.cat(item.oid.encode('hex'))
 740         _, obj_type, size = next(it)
 741         data = ''.join(it)
 742         if obj_type == 'tree':
 743             if want_meta:
 744                 item_gen = tree_items_with_meta(repo, item.oid, data, names)
 745             else:
 746                 item_gen = tree_items(item.oid, data, names)
 747         elif obj_type == 'commit':
 748             if want_meta:
 749                 item_gen = tree_items_with_meta(repo, item.oid, tree_data, names)
 750             else:
 751                 item_gen = tree_items(item.oid, tree_data, names)
 752         else:
 753             for _ in it: pass
 754             raise Exception('unexpected git ' + obj_type)
 755     elif item_t == RevList:
 756         item_gen = revlist_items(repo, item.oid, names)
 757     elif item_t == Root:
 758         item_gen = root_items(repo, names, want_meta)
 759     elif item_t == Tags:
 760         item_gen = tags_items(repo, names)
 761     else:
 762         raise Exception('unexpected VFS item ' + str(item))
 763     for x in item_gen:
 764         yield x
 765
 766 def _resolve_path(repo, path, parent=None, want_meta=True, deref=False):
 767     def raise_dir_required_but_not_dir(path, parent, past):
 768         raise IOError(ENOTDIR,
 769                       "path %r%s resolves to non-directory %r"
 770                       % (path,
 771                          ' (relative to %r)' % parent if parent else '',
 772                          past),
 773                       terminus=past)
 774     global _root
 775     assert repo
 776     assert len(path)
 777     if parent:
 778         for x in parent:
 779             assert len(x) == 2
 780             assert type(x[0]) in (bytes, str)
 781             assert type(x[1]) in item_types
 782         assert parent[0][1] == _root
 783         if not S_ISDIR(item_mode(parent[-1][1])):
 784             raise IOError(ENOTDIR,
 785                           'path resolution parent %r is not a directory'
 786                           % (parent,))
 787     is_absolute, must_be_dir, future = _decompose_path(path)
 788     if must_be_dir:
 789         deref = True
 790     if not future:  # path was effectively '.' or '/'
 791         if is_absolute:
 792             return (('', _root),)
 793         if parent:
 794             return tuple(parent)
 795         return [('', _root)]
 796     if is_absolute:
 797         past = [('', _root)]
 798     else:
 799         past = list(parent) if parent else [('', _root)]
 800     hops = 0
 801     while True:
 802         if not future:
 803             if must_be_dir and not S_ISDIR(item_mode(past[-1][1])):
 804                 raise_dir_required_but_not_dir(path, parent, past)
 805             return tuple(past)
 806         segment = future.pop()
 807         if segment == '..':
 808             assert len(past) > 0
 809             if len(past) > 1:  # .. from / is /
 810                 assert S_ISDIR(item_mode(past[-1][1]))
 811                 past.pop()
 812         else:
 813             parent_name, parent_item = past[-1]
 814             wanted = (segment,) if not want_meta else ('.', segment)
 815             items = tuple(contents(repo, parent_item, names=wanted,
 816                                    want_meta=want_meta))
 817             if not want_meta:
 818                 item = items[0][1] if items else None
 819             else:  # First item will be '.' and have the metadata
 820                 item = items[1][1] if len(items) == 2 else None
 821                 dot, dot_item = items[0]
 822                 assert dot == '.'
 823                 past[-1] = parent_name, parent_item
 824             if not item:
 825                 past.append((segment, None),)
 826                 return tuple(past)
 827             mode = item_mode(item)
 828             if not S_ISLNK(mode):
 829                 if not S_ISDIR(mode):
 830                     past.append((segment, item),)
 831                     if future:
 832                         raise IOError(ENOTDIR,
 833                                       'path %r%s ends internally in non-directory here: %r'
 834                                       % (path,
 835                                          ' (relative to %r)' % parent if parent else '',
 836                                          past),
 837                                       terminus=past)
 838                     if must_be_dir:
 839                         raise_dir_required_but_not_dir(path, parent, past)
 840                     return tuple(past)
 841                 # It's treeish
 842                 if want_meta and type(item) in real_tree_types:
 843                     dir_meta = _find_treeish_oid_metadata(repo, item.oid)
 844                     if dir_meta:
 845                         item = item._replace(meta=dir_meta)
 846                 past.append((segment, item))
 847             else:  # symlink
 848                 if not future and not deref:
 849                     past.append((segment, item),)
 850                     continue
 851                 if hops > 100:
 852                     raise IOError(ELOOP,
 853                                   'too many symlinks encountered while resolving %r%s'
 854                                   % (path, ' relative to %r' % parent if parent else ''),
 855                                   terminus=tuple(past + [(segment, item)]))
 856                 target = readlink(repo, item)
 857                 is_absolute, _, target_future = _decompose_path(target)
 858                 if is_absolute:
 859                     if not target_future:  # path was effectively '/'
 860                         return (('', _root),)
 861                     past = [('', _root)]
 862                     future = target_future
 863                 else:
 864                     future.extend(target_future)
 865                 hops += 1
 866
 867 def lresolve(repo, path, parent=None, want_meta=True):
 868     """Perform exactly the same function as resolve(), except if the final
 869     path element is a symbolic link, don't follow it, just return it
 870     in the result.
 871
 872     """
 873     return _resolve_path(repo, path, parent=parent, want_meta=want_meta,
 874                          deref=False)
 875
 876 def resolve(repo, path, parent=None, want_meta=True):
 877     """Follow the path in the virtual filesystem and return a tuple
 878     representing the location, if any, denoted by the path.  Each
 879     element in the result tuple will be (name, info), where info will
 880     be a VFS item that can be passed to functions like item_mode().
 881
 882     If a path segment that does not exist is encountered during
 883     resolution, the result will represent the location of the missing
 884     item, and that item in the result will be None.
 885
 886     Any attempt to traverse a non-directory will raise a VFS ENOTDIR
 887     IOError exception.
 888
 889     Any symlinks along the path, including at the end, will be
 890     resolved.  A VFS IOError with the errno attribute set to ELOOP
 891     will be raised if too many symlinks are traversed while following
 892     the path.  That exception is effectively like a normal
 893     ELOOP IOError exception, but will include a terminus element
 894     describing the location of the failure, which will be a tuple of
 895     (name, info) elements.
 896
 897     The parent, if specified, must be a sequence of (name, item)
 898     tuples, and will provide the starting point for the resolution of
 899     the path.  If no parent is specified, resolution will start at
 900     '/'.
 901
 902     The result may include elements of parent directly, so they must
 903     not be modified later.  If this is a concern, pass in "name,
 904     copy_item(item) for name, item in parent" instead.
 905
 906     When want_meta is true, detailed metadata will be included in each
 907     result item if it's avaiable, otherwise item.meta will be an
 908     integer mode.  The metadata size may or may not be provided, but
 909     can be computed by item_size() or augment_item_meta(...,
 910     include_size=True).  Setting want_meta=False is rarely desirable
 911     since it can limit the VFS to just the metadata git itself can
 912     represent, and so, as an example, fifos and sockets will appear to
 913     be regular files (e.g. S_ISREG(item_mode(item)) will be true) .
 914     But the option is provided because it may be more efficient when
 915     only the path names or the more limited metadata is sufficient.
 916
 917     Do not modify any item.meta Metadata instances directly.  If
 918     needed, make a copy via item.meta.copy() and modify that instead.
 919
 920     """
 921     result = _resolve_path(repo, path, parent=parent, want_meta=want_meta,
 922                            deref=True)
 923     _, leaf_item = result[-1]
 924     if leaf_item:
 925         assert not S_ISLNK(item_mode(leaf_item))
 926     return result
 927
 928 def try_resolve(repo, path, parent=None, want_meta=True):
 929     """If path does not refer to a symlink, does not exist, or refers to a
 930     valid symlink, behave exactly like resolve().  If path refers to
 931     an invalid symlink, behave like lresolve.
 932
 933     """
 934     res = lresolve(repo, path, parent=parent, want_meta=want_meta)
 935     leaf_name, leaf_item = res[-1]
 936     if not leaf_item:
 937         return res
 938     if not S_ISLNK(item_mode(leaf_item)):
 939         return res
 940     deref = resolve(repo, leaf_name, parent=res[:-1], want_meta=want_meta)
 941     deref_name, deref_item = deref[-1]
 942     if deref_item:
 943         return deref
 944     return res
 945
 946 def augment_item_meta(repo, item, include_size=False):
 947     """Ensure item has a Metadata instance for item.meta.  If item.meta is
 948     currently a mode, replace it with a compatible "fake" Metadata
 949     instance.  If include_size is true, ensure item.meta.size is
 950     correct, computing it if needed.  If item.meta is a Metadata
 951     instance, this call may modify it in place or replace it.
 952
 953     """
 954     # If we actually had parallelism, we'd need locking...
 955     assert repo
 956     m = item.meta
 957     if isinstance(m, Metadata):
 958         if include_size and m.size is None:
 959             m.size = _compute_item_size(repo, item)
 960             return item._replace(meta=m)
 961         return item
 962     # m is mode
 963     meta = Metadata()
 964     meta.mode = m
 965     meta.uid = meta.gid = meta.atime = meta.mtime = meta.ctime = 0
 966     if S_ISLNK(m):
 967         target = _readlink(repo, item.oid)
 968         meta.symlink_target = target
 969         meta.size = len(target)
 970     elif include_size:
 971         meta.size = _compute_item_size(repo, item)
 972     return item._replace(meta=meta)
 973
 974 def fill_in_metadata_if_dir(repo, item):
 975     """If item is a directory and item.meta is not a Metadata instance,
 976     attempt to find the metadata for the directory.  If found, return
 977     a new item augmented to include that metadata.  Otherwise, return
 978     item.  May be useful for the output of contents().
 979
 980     """
 981     if S_ISDIR(item_mode(item)) and not isinstance(item.meta, Metadata):
 982         items = tuple(contents(repo, item, ('.',), want_meta=True))
 983         assert len(items) == 1
 984         assert items[0][0] == '.'
 985         item = items[0][1]
 986     return item
 987
 988 def ensure_item_has_metadata(repo, item, include_size=False):
 989     """If item is a directory, attempt to find and add its metadata.  If
 990     the item still doesn't have a Metadata instance for item.meta,
 991     give it one via augment_item_meta().  May be useful for the output
 992     of contents().
 993
 994     """
 995     return augment_item_meta(repo,
 996                              fill_in_metadata_if_dir(repo, item),
 997                              include_size=include_size)