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