lib/bup/vfs2.py

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