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