lib/bup/vfs.py

   1 """Virtual File System interface to bup repository content.
   2
   3 This module provides a path-based interface to the content of a bup
   4 repository.
   5
   6 The VFS is structured like this:
   7
   8   /SAVE-NAME/latest/...
   9   /SAVE-NAME/SAVE-DATE/...
  10   /.tag/TAG-NAME/...
  11
  12 Each path is represented by an item that has least an item.meta which
  13 may be either a Metadata object, or an integer mode.  Functions like
  14 item_mode() and item_size() will return the mode and size in either
  15 case.  Any item.meta Metadata instances must not be modified directly.
  16 Make a copy to modify via item.meta.copy() if needed, or call
  17 copy_item().
  18
  19 The want_meta argument is advisory for calls that accept it, and it
  20 may not be honored.  Callers must be able to handle an item.meta value
  21 that is either an instance of Metadata or an integer mode, perhaps
  22 via item_mode() or augment_item_meta().
  23
  24 Setting want_meta=False is rarely desirable since it can limit the VFS
  25 to only the metadata that git itself can represent, and so for
  26 example, fifos and sockets will appear to be regular files
  27 (e.g. S_ISREG(item_mode(item)) will be true).  But the option is still
  28 provided because it may be more efficient when just the path names or
  29 the more limited metadata is sufficient.
  30
  31 Any given metadata object's size may be None, in which case the size
  32 can be computed via item_size() or augment_item_meta(...,
  33 include_size=True).
  34
  35 When traversing a directory using functions like contents(), the meta
  36 value for any directories other than '.' will be a default directory
  37 mode, not a Metadata object.  This is because the actual metadata for
  38 a directory is stored inside the directory (see
  39 fill_in_metadata_if_dir() or ensure_item_has_metadata()).
  40
  41 Commit items represent commits (e.g. /.tag/some-commit or
  42 /foo/latest), and for most purposes, they appear as the underlying
  43 tree.  S_ISDIR(item_mode(item)) will return true for both tree Items
  44 and Commits and the commit's oid is the tree hash; the commit hash is
  45 item.coid.
  46
  47 """
  48
  49 from __future__ import absolute_import, print_function
  50 from binascii import hexlify, unhexlify
  51 from collections import namedtuple
  52 from errno import EINVAL, ELOOP, ENOENT, ENOTDIR
  53 from itertools import chain, dropwhile, groupby, tee
  54 from random import randrange
  55 from stat import S_IFDIR, S_IFLNK, S_IFREG, S_ISDIR, S_ISLNK, S_ISREG
  56 from time import localtime, strftime
  57 import re, sys
  58
  59 from bup import git, metadata, vint
  60 from bup.compat import hexstr, range
  61 from bup.git import BUP_CHUNKED, cp, get_commit_items, parse_commit, tree_decode
  62 from bup.helpers import debug2, last
  63 from bup.io import path_msg
  64 from bup.metadata import Metadata
  65 from bup.vint import read_bvec, write_bvec
  66 from bup.vint import read_vint, write_vint
  67 from bup.vint import read_vuint, write_vuint
  68
  69 if sys.version_info[0] < 3:
  70     from exceptions import IOError as py_IOError
  71 else:
  72     py_IOError = IOError
  73
  74 # We currently assume that it's always appropriate to just forward IOErrors
  75 # to a remote client.
  76
  77 class IOError(py_IOError):
  78     def __init__(self, errno, message, terminus=None):
  79         py_IOError.__init__(self, errno, message)
  80         self.terminus = terminus
  81
  82 def write_ioerror(port, ex):
  83     assert isinstance(ex, IOError)
  84     write_vuint(port,
  85                 (1 if ex.errno is not None else 0)
  86                 | (2 if ex.strerror is not None else 0)
  87                 | (4 if ex.terminus is not None else 0))
  88     if ex.errno is not None:
  89         write_vint(port, ex.errno)
  90     if ex.strerror is not None:
  91         write_bvec(port, ex.strerror.encode('utf-8'))
  92     if ex.terminus is not None:
  93         write_resolution(port, ex.terminus)
  94
  95 def read_ioerror(port):
  96     mask = read_vuint(port)
  97     no = read_vint(port) if 1 & mask else None
  98     msg = read_bvec(port).decode('utf-8') if 2 & mask else None
  99     term = read_resolution(port) if 4 & mask else None
 100     return IOError(errno=no, message=msg, terminus=term)
 101
 102
 103 default_file_mode = S_IFREG | 0o644
 104 default_dir_mode = S_IFDIR | 0o755
 105 default_symlink_mode = S_IFLNK | 0o755
 106
 107 def _default_mode_for_gitmode(gitmode):
 108     if S_ISREG(gitmode):
 109         return default_file_mode
 110     if S_ISDIR(gitmode):
 111         return default_dir_mode
 112     if S_ISLNK(gitmode):
 113         return default_symlink_mode
 114     raise Exception('unexpected git mode ' + oct(gitmode))
 115
 116 def _normal_or_chunked_file_size(repo, oid):
 117     """Return the size of the normal or chunked file indicated by oid."""
 118     # FIXME: --batch-format CatPipe?
 119     it = repo.cat(hexlify(oid))
 120     _, obj_t, size = next(it)
 121     ofs = 0
 122     while obj_t == b'tree':
 123         mode, name, last_oid = last(tree_decode(b''.join(it)))
 124         ofs += int(name, 16)
 125         it = repo.cat(hexlify(last_oid))
 126         _, obj_t, size = next(it)
 127     return ofs + sum(len(b) for b in it)
 128
 129 def _skip_chunks_before_offset(tree, offset):
 130     prev_ent = next(tree, None)
 131     if not prev_ent:
 132         return tree
 133     ent = None
 134     for ent in tree:
 135         ent_ofs = int(ent[1], 16)
 136         if ent_ofs > offset:
 137             return chain([prev_ent, ent], tree)
 138         if ent_ofs == offset:
 139             return chain([ent], tree)
 140         prev_ent = ent
 141     return [prev_ent]
 142
 143 def _tree_chunks(repo, tree, startofs):
 144     "Tree should be a sequence of (name, mode, hash) as per tree_decode()."
 145     assert(startofs >= 0)
 146     # name is the chunk's hex offset in the original file
 147     for mode, name, oid in _skip_chunks_before_offset(tree, startofs):
 148         ofs = int(name, 16)
 149         skipmore = startofs - ofs
 150         if skipmore < 0:
 151             skipmore = 0
 152         it = repo.cat(hexlify(oid))
 153         _, obj_t, size = next(it)
 154         data = b''.join(it)
 155         if S_ISDIR(mode):
 156             assert obj_t == b'tree'
 157             for b in _tree_chunks(repo, tree_decode(data), skipmore):
 158                 yield b
 159         else:
 160             assert obj_t == b'blob'
 161             yield data[skipmore:]
 162
 163 class _ChunkReader:
 164     def __init__(self, repo, oid, startofs):
 165         it = repo.cat(hexlify(oid))
 166         _, obj_t, size = next(it)
 167         isdir = obj_t == b'tree'
 168         data = b''.join(it)
 169         if isdir:
 170             self.it = _tree_chunks(repo, tree_decode(data), startofs)
 171             self.blob = None
 172         else:
 173             self.it = None
 174             self.blob = data[startofs:]
 175         self.ofs = startofs
 176
 177     def next(self, size):
 178         out = b''
 179         while len(out) < size:
 180             if self.it and not self.blob:
 181                 try:
 182                     self.blob = next(self.it)
 183                 except StopIteration:
 184                     self.it = None
 185             if self.blob:
 186                 want = size - len(out)
 187                 out += self.blob[:want]
 188                 self.blob = self.blob[want:]
 189             if not self.it:
 190                 break
 191         debug2('next(%d) returned %d\n' % (size, len(out)))
 192         self.ofs += len(out)
 193         return out
 194
 195 class _FileReader(object):
 196     def __init__(self, repo, oid, known_size=None):
 197         assert len(oid) == 20
 198         self.oid = oid
 199         self.ofs = 0
 200         self.reader = None
 201         self._repo = repo
 202         self._size = known_size
 203
 204     def _compute_size(self):
 205         if not self._size:
 206             self._size = _normal_or_chunked_file_size(self._repo, self.oid)
 207         return self._size
 208
 209     def seek(self, ofs):
 210         if ofs < 0 or ofs > self._compute_size():
 211             raise IOError(EINVAL, 'Invalid seek offset: %d' % ofs)
 212         self.ofs = ofs
 213
 214     def tell(self):
 215         return self.ofs
 216
 217     def read(self, count=-1):
 218         size = self._compute_size()
 219         if self.ofs >= size:
 220             return b''
 221         if count < 0:
 222             count = size - self.ofs
 223         if not self.reader or self.reader.ofs != self.ofs:
 224             self.reader = _ChunkReader(self._repo, self.oid, self.ofs)
 225         try:
 226             buf = self.reader.next(count)
 227         except:
 228             self.reader = None
 229             raise  # our offsets will be all screwed up otherwise
 230         self.ofs += len(buf)
 231         return buf
 232
 233     def close(self):
 234         pass
 235
 236     def __enter__(self):
 237         return self
 238     def __exit__(self, type, value, traceback):
 239         self.close()
 240         return False
 241
 242 _multiple_slashes_rx = re.compile(br'//+')
 243
 244 def _decompose_path(path):
 245     """Return a boolean indicating whether the path is absolute, and a
 246     reversed list of path elements, omitting any occurrences of "."
 247     and ignoring any leading or trailing slash.  If the path is
 248     effectively '/' or '.', return an empty list.
 249
 250     """
 251     path = re.sub(_multiple_slashes_rx, b'/', path)
 252     if path == b'/':
 253         return True, True, []
 254     is_absolute = must_be_dir = False
 255     if path.startswith(b'/'):
 256         is_absolute = True
 257         path = path[1:]
 258     for suffix in (b'/', b'/.'):
 259         if path.endswith(suffix):
 260             must_be_dir = True
 261             path = path[:-len(suffix)]
 262     parts = [x for x in path.split(b'/') if x != b'.']
 263     parts.reverse()
 264     if not parts:
 265         must_be_dir = True  # e.g. path was effectively '.' or '/', etc.
 266     return is_absolute, must_be_dir, parts
 267
 268
 269 Item = namedtuple('Item', ('meta', 'oid'))
 270 Chunky = namedtuple('Chunky', ('meta', 'oid'))
 271 FakeLink = namedtuple('FakeLink', ('meta', 'target'))
 272 Root = namedtuple('Root', ('meta'))
 273 Tags = namedtuple('Tags', ('meta'))
 274 RevList = namedtuple('RevList', ('meta', 'oid'))
 275 Commit = namedtuple('Commit', ('meta', 'oid', 'coid'))
 276
 277 item_types = frozenset((Item, Chunky, Root, Tags, RevList, Commit))
 278 real_tree_types = frozenset((Item, Commit))
 279
 280 def write_item(port, item):
 281     kind = type(item)
 282     name = bytes(kind.__name__.encode('ascii'))
 283     meta = item.meta
 284     has_meta = 1 if isinstance(meta, Metadata) else 0
 285     if kind in (Item, Chunky, RevList):
 286         assert len(item.oid) == 20
 287         if has_meta:
 288             vint.send(port, 'sVs', name, has_meta, item.oid)
 289             Metadata.write(meta, port, include_path=False)
 290         else:
 291             vint.send(port, 'sVsV', name, has_meta, item.oid, item.meta)
 292     elif kind in (Root, Tags):
 293         if has_meta:
 294             vint.send(port, 'sV', name, has_meta)
 295             Metadata.write(meta, port, include_path=False)
 296         else:
 297             vint.send(port, 'sVV', name, has_meta, item.meta)
 298     elif kind == Commit:
 299         assert len(item.oid) == 20
 300         assert len(item.coid) == 20
 301         if has_meta:
 302             vint.send(port, 'sVss', name, has_meta, item.oid, item.coid)
 303             Metadata.write(meta, port, include_path=False)
 304         else:
 305             vint.send(port, 'sVssV', name, has_meta, item.oid, item.coid,
 306                       item.meta)
 307     elif kind == FakeLink:
 308         if has_meta:
 309             vint.send(port, 'sVs', name, has_meta, item.target)
 310             Metadata.write(meta, port, include_path=False)
 311         else:
 312             vint.send(port, 'sVsV', name, has_meta, item.target, item.meta)
 313     else:
 314         assert False
 315
 316 def read_item(port):
 317     def read_m(port, has_meta):
 318         if has_meta:
 319             m = Metadata.read(port)
 320             return m
 321         return read_vuint(port)
 322     kind, has_meta = vint.recv(port, 'sV')
 323     if kind == b'Item':
 324         oid, meta = read_bvec(port), read_m(port, has_meta)
 325         return Item(oid=oid, meta=meta)
 326     if kind == b'Chunky':
 327         oid, meta = read_bvec(port), read_m(port, has_meta)
 328         return Chunky(oid=oid, meta=meta)
 329     if kind == b'RevList':
 330         oid, meta = read_bvec(port), read_m(port, has_meta)
 331         return RevList(oid=oid, meta=meta)
 332     if kind == b'Root':
 333         return Root(meta=read_m(port, has_meta))
 334     if kind == b'Tags':
 335         return Tags(meta=read_m(port, has_meta))
 336     if kind == b'Commit':
 337         oid, coid = vint.recv(port, 'ss')
 338         meta = read_m(port, has_meta)
 339         return Commit(oid=oid, coid=coid, meta=meta)
 340     if kind == b'FakeLink':
 341         target, meta = read_bvec(port), read_m(port, has_meta)
 342         return FakeLink(target=target, meta=meta)
 343     assert False
 344
 345 def write_resolution(port, resolution):
 346     write_vuint(port, len(resolution))
 347     for name, item in resolution:
 348         write_bvec(port, name)
 349         if item:
 350             port.write(b'\x01')
 351             write_item(port, item)
 352         else:
 353             port.write(b'\x00')
 354
 355 def read_resolution(port):
 356     n = read_vuint(port)
 357     result = []
 358     for i in range(n):
 359         name = read_bvec(port)
 360         have_item = ord(port.read(1))
 361         assert have_item in (0, 1)
 362         item = read_item(port) if have_item else None
 363         result.append((name, item))
 364     return tuple(result)
 365
 366
 367 _root = Root(meta=default_dir_mode)
 368 _tags = Tags(meta=default_dir_mode)
 369
 370
 371 ### vfs cache
 372
 373 ### A general purpose shared cache with (currently) cheap random
 374 ### eviction.  At the moment there is no weighting so a single commit
 375 ### item is just as likely to be evicted as an entire "rev-list".  See
 376 ### is_valid_cache_key for a description of the expected content.
 377
 378 _cache = {}
 379 _cache_keys = []
 380 _cache_max_items = 30000
 381
 382 def clear_cache():
 383     global _cache, _cache_keys
 384     _cache = {}
 385     _cache_keys = []
 386
 387 def is_valid_cache_key(x):
 388     """Return logically true if x looks like it could be a valid cache key
 389     (with respect to structure).  Current valid cache entries:
 390       res:... -> resolution
 391       itm:OID -> Commit
 392       rvl:OID -> {'.', commit, '2012...', next_commit, ...}
 393     """
 394     # Suspect we may eventually add "(container_oid, name) -> ...", and others.
 395     x_t = type(x)
 396     if x_t is bytes:
 397         tag = x[:4]
 398         if tag in (b'itm:', b'rvl:') and len(x) == 24:
 399             return True
 400         if tag == b'res:':
 401             return True
 402
 403 def cache_get(key):
 404     global _cache
 405     if not is_valid_cache_key(key):
 406         raise Exception('invalid cache key: ' + repr(key))
 407     return _cache.get(key)
 408
 409 def cache_notice(key, value):
 410     global _cache, _cache_keys, _cache_max_items
 411     if not is_valid_cache_key(key):
 412         raise Exception('invalid cache key: ' + repr(key))
 413     if key in _cache:
 414         return
 415     if len(_cache) < _cache_max_items:
 416         _cache_keys.append(key)
 417         _cache[key] = value
 418         return
 419     victim_i = randrange(0, len(_cache_keys))
 420     victim = _cache_keys[victim_i]
 421     del _cache[victim]
 422     _cache_keys[victim_i] = key
 423     _cache[key] = value
 424
 425 def cache_get_commit_item(oid, need_meta=True):
 426     """Return the requested tree item if it can be found in the cache.
 427     When need_meta is true don't return a cached item that only has a
 428     mode."""
 429     # tree might be stored independently, or as '.' with its entries.
 430     commit_key = b'itm:' + oid
 431     item = cache_get(commit_key)
 432     if item:
 433         if not need_meta:
 434             return item
 435         if isinstance(item.meta, Metadata):
 436             return item
 437     entries = cache_get(b'rvl:' + oid)
 438     if entries:
 439         return entries[b'.']
 440
 441 def copy_item(item):
 442     """Return a completely independent copy of item, such that
 443     modifications will not affect the original.
 444
 445     """
 446     meta = getattr(item, 'meta', None)
 447     if isinstance(meta, Metadata):
 448         return(item._replace(meta=meta.copy()))
 449     return item
 450
 451 def item_mode(item):
 452     """Return the integer mode (stat st_mode) for item."""
 453     m = item.meta
 454     if isinstance(m, Metadata):
 455         return m.mode
 456     return m
 457
 458 def _read_dir_meta(bupm):
 459     # This is because save writes unmodified Metadata() entries for
 460     # fake parents -- test-save-strip-graft.sh demonstrates.
 461     m = Metadata.read(bupm)
 462     if not m:
 463         return default_dir_mode
 464     assert m.mode is not None
 465     if m.size is None:
 466         m.size = 0
 467     return m
 468
 469 def tree_data_and_bupm(repo, oid):
 470     """Return (tree_bytes, bupm_oid) where bupm_oid will be None if the
 471     tree has no metadata (i.e. older bup save, or non-bup tree).
 472
 473     """
 474     assert len(oid) == 20
 475     it = repo.cat(hexlify(oid))
 476     _, item_t, size = next(it)
 477     data = b''.join(it)
 478     if item_t == b'commit':
 479         commit = parse_commit(data)
 480         it = repo.cat(commit.tree)
 481         _, item_t, size = next(it)
 482         data = b''.join(it)
 483         assert item_t == b'tree'
 484     elif item_t != b'tree':
 485         raise Exception('%s is not a tree or commit' % hexstr(oid))
 486     for _, mangled_name, sub_oid in tree_decode(data):
 487         if mangled_name == b'.bupm':
 488             return data, sub_oid
 489         if mangled_name > b'.bupm':
 490             break
 491     return data, None
 492
 493 def _find_treeish_oid_metadata(repo, oid):
 494     """Return the metadata for the tree or commit oid, or None if the tree
 495     has no metadata (i.e. older bup save, or non-bup tree).
 496
 497     """
 498     tree_data, bupm_oid = tree_data_and_bupm(repo, oid)
 499     if bupm_oid:
 500         with _FileReader(repo, bupm_oid) as meta_stream:
 501             return _read_dir_meta(meta_stream)
 502     return None
 503
 504 def _readlink(repo, oid):
 505     return b''.join(repo.join(hexlify(oid)))
 506
 507 def readlink(repo, item):
 508     """Return the link target of item, which must be a symlink.  Reads the
 509     target from the repository if necessary."""
 510     assert repo
 511     assert S_ISLNK(item_mode(item))
 512     if isinstance(item, FakeLink):
 513         return item.target
 514     if isinstance(item.meta, Metadata):
 515         target = item.meta.symlink_target
 516         if target:
 517             return target
 518     return _readlink(repo, item.oid)
 519
 520 def _compute_item_size(repo, item):
 521     mode = item_mode(item)
 522     if S_ISREG(mode):
 523         size = _normal_or_chunked_file_size(repo, item.oid)
 524         return size
 525     if S_ISLNK(mode):
 526         if isinstance(item, FakeLink):
 527             return len(item.target)
 528         return len(_readlink(repo, item.oid))
 529     return 0
 530
 531 def item_size(repo, item):
 532     """Return the size of item, computing it if necessary."""
 533     m = item.meta
 534     if isinstance(m, Metadata) and m.size is not None:
 535         return m.size
 536     return _compute_item_size(repo, item)
 537
 538 def tree_data_reader(repo, oid):
 539     """Return an open reader for all of the data contained within oid.  If
 540     oid refers to a tree, recursively concatenate all of its contents."""
 541     return _FileReader(repo, oid)
 542
 543 def fopen(repo, item):
 544     """Return an open reader for the given file item."""
 545     assert S_ISREG(item_mode(item))
 546     return tree_data_reader(repo, item.oid)
 547
 548 def _commit_item_from_data(oid, data):
 549     info = parse_commit(data)
 550     return Commit(meta=default_dir_mode,
 551                   oid=unhexlify(info.tree),
 552                   coid=oid)
 553
 554 def _commit_item_from_oid(repo, oid, require_meta):
 555     commit = cache_get_commit_item(oid, need_meta=require_meta)
 556     if commit and ((not require_meta) or isinstance(commit.meta, Metadata)):
 557         return commit
 558     it = repo.cat(hexlify(oid))
 559     _, typ, size = next(it)
 560     assert typ == b'commit'
 561     commit = _commit_item_from_data(oid, b''.join(it))
 562     if require_meta:
 563         meta = _find_treeish_oid_metadata(repo, commit.oid)
 564         if meta:
 565             commit = commit._replace(meta=meta)
 566     commit_key = b'itm:' + oid
 567     cache_notice(commit_key, commit)
 568     return commit
 569
 570 def _revlist_item_from_oid(repo, oid, require_meta):
 571     commit = _commit_item_from_oid(repo, oid, require_meta)
 572     return RevList(oid=oid, meta=commit.meta)
 573
 574 def root_items(repo, names=None, want_meta=True):
 575     """Yield (name, item) for the items in '/' in the VFS.  Return
 576     everything if names is logically false, otherwise return only
 577     items with a name in the collection.
 578
 579     """
 580     # FIXME: what about non-leaf refs like 'refs/heads/foo/bar/baz?
 581
 582     global _root, _tags
 583     if not names:
 584         yield b'.', _root
 585         yield b'.tag', _tags
 586         # FIXME: maybe eventually support repo.clone() or something
 587         # and pass in two repos, so we can drop the tuple() and stream
 588         # in parallel (i.e. meta vs refs).
 589         for name, oid in tuple(repo.refs([], limit_to_heads=True)):
 590             assert(name.startswith(b'refs/heads/'))
 591             yield name[11:], _revlist_item_from_oid(repo, oid, want_meta)
 592         return
 593
 594     if b'.' in names:
 595         yield b'.', _root
 596     if b'.tag' in names:
 597         yield b'.tag', _tags
 598     for ref in names:
 599         if ref in (b'.', b'.tag'):
 600             continue
 601         it = repo.cat(b'refs/heads/' + ref)
 602         oidx, typ, size = next(it)
 603         if not oidx:
 604             for _ in it: pass
 605             continue
 606         assert typ == b'commit'
 607         commit = parse_commit(b''.join(it))
 608         yield ref, _revlist_item_from_oid(repo, unhexlify(oidx), want_meta)
 609
 610 def ordered_tree_entries(tree_data, bupm=None):
 611     """Yields (name, mangled_name, kind, gitmode, oid) for each item in
 612     tree, sorted by name.
 613
 614     """
 615     # Sadly, the .bupm entries currently aren't in git tree order,
 616     # but in unmangled name order. They _do_ account for the fact
 617     # that git sorts trees (including chunked trees) as if their
 618     # names ended with "/" (so "fo" sorts after "fo." iff fo is a
 619     # directory), but we apply this on the unmangled names in save
 620     # rather than on the mangled names.
 621     # This makes streaming impossible when we need the metadata.
 622     def result_from_tree_entry(tree_entry):
 623         gitmode, mangled_name, oid = tree_entry
 624         name, kind = git.demangle_name(mangled_name, gitmode)
 625         return name, mangled_name, kind, gitmode, oid
 626
 627     tree_ents = (result_from_tree_entry(x) for x in tree_decode(tree_data))
 628     if bupm:
 629         tree_ents = sorted(tree_ents, key=lambda x: x[0])
 630     for ent in tree_ents:
 631         yield ent
 632
 633 def tree_items(oid, tree_data, names=frozenset(), bupm=None):
 634
 635     def tree_item(ent_oid, kind, gitmode):
 636         if kind == BUP_CHUNKED:
 637             meta = Metadata.read(bupm) if bupm else default_file_mode
 638             return Chunky(oid=ent_oid, meta=meta)
 639
 640         if S_ISDIR(gitmode):
 641             # No metadata here (accessable via '.' inside ent_oid).
 642             return Item(meta=default_dir_mode, oid=ent_oid)
 643
 644         meta = Metadata.read(bupm) if bupm else None
 645         # handle the case of metadata being empty/missing in bupm
 646         # (or there not being bupm at all)
 647         if meta is None:
 648             meta = _default_mode_for_gitmode(gitmode)
 649         return Item(oid=ent_oid, meta=meta)
 650
 651     assert len(oid) == 20
 652     if not names:
 653         dot_meta = _read_dir_meta(bupm) if bupm else default_dir_mode
 654         yield b'.', Item(oid=oid, meta=dot_meta)
 655         tree_entries = ordered_tree_entries(tree_data, bupm)
 656         for name, mangled_name, kind, gitmode, ent_oid in tree_entries:
 657             if mangled_name == b'.bupm':
 658                 continue
 659             assert name != b'.'
 660             yield name, tree_item(ent_oid, kind, gitmode)
 661         return
 662
 663     # Assumes the tree is properly formed, i.e. there are no
 664     # duplicates, and entries will be in git tree order.
 665     if type(names) not in (frozenset, set):
 666         names = frozenset(names)
 667     remaining = len(names)
 668
 669     # Account for the bupm sort order issue (cf. ordered_tree_entries above)
 670     last_name = max(names) if bupm else max(names) + b'/'
 671
 672     if b'.' in names:
 673         dot_meta = _read_dir_meta(bupm) if bupm else default_dir_mode
 674         yield b'.', Item(oid=oid, meta=dot_meta)
 675         if remaining == 1:
 676             return
 677         remaining -= 1
 678
 679     tree_entries = ordered_tree_entries(tree_data, bupm)
 680     for name, mangled_name, kind, gitmode, ent_oid in tree_entries:
 681         if mangled_name == b'.bupm':
 682             continue
 683         assert name != b'.'
 684         if name not in names:
 685             if name > last_name:
 686                 break  # given bupm sort order, we're finished
 687             if (kind == BUP_CHUNKED or not S_ISDIR(gitmode)) and bupm:
 688                 Metadata.read(bupm)
 689             continue
 690         yield name, tree_item(ent_oid, kind, gitmode)
 691         if remaining == 1:
 692             break
 693         remaining -= 1
 694
 695 def tree_items_with_meta(repo, oid, tree_data, names):
 696     # For now, the .bupm order doesn't quite match git's, and we don't
 697     # load the tree data incrementally anyway, so we just work in RAM
 698     # via tree_data.
 699     assert len(oid) == 20
 700     bupm = None
 701     for _, mangled_name, sub_oid in tree_decode(tree_data):
 702         if mangled_name == b'.bupm':
 703             bupm = _FileReader(repo, sub_oid)
 704             break
 705         if mangled_name > b'.bupm':
 706             break
 707     for item in tree_items(oid, tree_data, names, bupm):
 708         yield item
 709
 710 _save_name_rx = re.compile(br'^\d\d\d\d-\d\d-\d\d-\d{6}(-\d+)?$')
 711
 712 def _reverse_suffix_duplicates(strs):
 713     """Yields the elements of strs, with any runs of duplicate values
 714     suffixed with -N suffixes, where the zero padded integer N
 715     decreases to 0 by 1 (e.g. 10, 09, ..., 00).
 716
 717     """
 718     for name, duplicates in groupby(strs):
 719         ndup = len(tuple(duplicates))
 720         if ndup == 1:
 721             yield name
 722         else:
 723             ndig = len(str(ndup - 1))
 724             fmt = b'%s-' + b'%0' + (b'%d' % ndig) + b'd'
 725             for i in range(ndup - 1, -1, -1):
 726                 yield fmt % (name, i)
 727
 728 def parse_rev(f):
 729     items = f.readline().split(None)
 730     assert len(items) == 2
 731     tree, auth_sec = items
 732     return unhexlify(tree), int(auth_sec)
 733
 734 def _name_for_rev(rev):
 735     commit_oidx, (tree_oid, utc) = rev
 736     return strftime('%Y-%m-%d-%H%M%S', localtime(utc)).encode('ascii')
 737
 738 def _item_for_rev(rev):
 739     commit_oidx, (tree_oid, utc) = rev
 740     coid = unhexlify(commit_oidx)
 741     item = cache_get_commit_item(coid, need_meta=False)
 742     if item:
 743         return item
 744     item = Commit(meta=default_dir_mode, oid=tree_oid, coid=coid)
 745     commit_key = b'itm:' + coid
 746     cache_notice(commit_key, item)
 747     return item
 748
 749 def cache_commit(repo, oid):
 750     """Build, cache, and return a "name -> commit_item" dict of the entire
 751     commit rev-list.
 752
 753     """
 754     # For now, always cache with full metadata
 755     entries = {}
 756     entries[b'.'] = _revlist_item_from_oid(repo, oid, True)
 757     revs = repo.rev_list((hexlify(oid),), format=b'%T %at',
 758                          parse=parse_rev)
 759     rev_items, rev_names = tee(revs)
 760     revs = None  # Don't disturb the tees
 761     rev_names = _reverse_suffix_duplicates(_name_for_rev(x) for x in rev_names)
 762     rev_items = (_item_for_rev(x) for x in rev_items)
 763     tip = None
 764     for item in rev_items:
 765         name = next(rev_names)
 766         tip = tip or (name, item)
 767         entries[name] = item
 768     entries[b'latest'] = FakeLink(meta=default_symlink_mode, target=tip[0])
 769     revlist_key = b'rvl:' + tip[1].coid
 770     cache_notice(revlist_key, entries)
 771     return entries
 772
 773 def revlist_items(repo, oid, names):
 774     assert len(oid) == 20
 775
 776     # Special case '.' instead of caching the whole history since it's
 777     # the only way to get the metadata for the commit.
 778     if names and all(x == b'.' for x in names):
 779         yield b'.', _revlist_item_from_oid(repo, oid, True)
 780         return
 781
 782     # For now, don't worry about the possibility of the contents being
 783     # "too big" for the cache.
 784     revlist_key = b'rvl:' + oid
 785     entries = cache_get(revlist_key)
 786     if not entries:
 787         entries = cache_commit(repo, oid)
 788
 789     if not names:
 790         for name in sorted(entries.keys()):
 791             yield name, entries[name]
 792         return
 793
 794     names = frozenset(name for name in names
 795                       if _save_name_rx.match(name) or name in (b'.', b'latest'))
 796
 797     if b'.' in names:
 798         yield b'.', entries[b'.']
 799     for name in (n for n in names if n != b'.'):
 800         commit = entries.get(name)
 801         if commit:
 802             yield name, commit
 803
 804 def tags_items(repo, names):
 805     global _tags
 806
 807     def tag_item(oid):
 808         assert len(oid) == 20
 809         oidx = hexlify(oid)
 810         it = repo.cat(oidx)
 811         _, typ, size = next(it)
 812         if typ == b'commit':
 813             return cache_get_commit_item(oid, need_meta=False) \
 814                 or _commit_item_from_data(oid, b''.join(it))
 815         for _ in it: pass
 816         if typ == b'blob':
 817             return Item(meta=default_file_mode, oid=oid)
 818         elif typ == b'tree':
 819             return Item(meta=default_dir_mode, oid=oid)
 820         raise Exception('unexpected tag type ' + typ.decode('ascii')
 821                         + ' for tag ' + path_msg(name))
 822
 823     if not names:
 824         yield b'.', _tags
 825         # We have to pull these all into ram because tag_item calls cat()
 826         for name, oid in tuple(repo.refs(names, limit_to_tags=True)):
 827             assert(name.startswith(b'refs/tags/'))
 828             name = name[10:]
 829             yield name, tag_item(oid)
 830         return
 831
 832     # Assumes no duplicate refs
 833     if type(names) not in (frozenset, set):
 834         names = frozenset(names)
 835     remaining = len(names)
 836     last_name = max(names)
 837     if b'.' in names:
 838         yield b'.', _tags
 839         if remaining == 1:
 840             return
 841         remaining -= 1
 842
 843     for name, oid in repo.refs(names, limit_to_tags=True):
 844         assert(name.startswith(b'refs/tags/'))
 845         name = name[10:]
 846         if name > last_name:
 847             return
 848         if name not in names:
 849             continue
 850         yield name, tag_item(oid)
 851         if remaining == 1:
 852             return
 853         remaining -= 1
 854
 855 def contents(repo, item, names=None, want_meta=True):
 856     """Yields information about the items contained in item.  Yields
 857     (name, item) for each name in names, if the name exists, in an
 858     unspecified order.  If there are no names, then yields (name,
 859     item) for all items, including, a first item named '.'
 860     representing the container itself.
 861
 862     The meta value for any directories other than '.' will be a
 863     default directory mode, not a Metadata object.  This is because
 864     the actual metadata for a directory is stored inside the directory
 865     (see fill_in_metadata_if_dir() or ensure_item_has_metadata()).
 866
 867     Note that want_meta is advisory.  For any given item, item.meta
 868     might be a Metadata instance or a mode, and if the former,
 869     meta.size might be None.  Missing sizes can be computed via via
 870     item_size() or augment_item_meta(..., include_size=True).
 871
 872     Do not modify any item.meta Metadata instances directly.  If
 873     needed, make a copy via item.meta.copy() and modify that instead.
 874
 875     """
 876     # Q: are we comfortable promising '.' first when no names?
 877     global _root, _tags
 878     assert repo
 879     assert S_ISDIR(item_mode(item))
 880     item_t = type(item)
 881     if item_t in real_tree_types:
 882         it = repo.cat(hexlify(item.oid))
 883         _, obj_t, size = next(it)
 884         data = b''.join(it)
 885         if obj_t != b'tree':
 886             for _ in it: pass
 887             # Note: it shouldn't be possible to see an Item with type
 888             # 'commit' since a 'commit' should always produce a Commit.
 889             raise Exception('unexpected git ' + obj_t.decode('ascii'))
 890         if want_meta:
 891             item_gen = tree_items_with_meta(repo, item.oid, data, names)
 892         else:
 893             item_gen = tree_items(item.oid, data, names)
 894     elif item_t == RevList:
 895         item_gen = revlist_items(repo, item.oid, names)
 896     elif item_t == Root:
 897         item_gen = root_items(repo, names, want_meta)
 898     elif item_t == Tags:
 899         item_gen = tags_items(repo, names)
 900     else:
 901         raise Exception('unexpected VFS item ' + str(item))
 902     for x in item_gen:
 903         yield x
 904
 905 def _resolve_path(repo, path, parent=None, want_meta=True, follow=True):
 906     cache_key = b'res:%d%d%d:%s\0%s' \
 907                 % (bool(want_meta), bool(follow), repo.id(),
 908                    (b'/'.join(x[0] for x in parent) if parent else b''),
 909                    path)
 910     resolution = cache_get(cache_key)
 911     if resolution:
 912         return resolution
 913
 914     def notice_resolution(r):
 915         cache_notice(cache_key, r)
 916         return r
 917
 918     def raise_dir_required_but_not_dir(path, parent, past):
 919         raise IOError(ENOTDIR,
 920                       "path %s%s resolves to non-directory %r"
 921                       % (path,
 922                          ' (relative to %r)' % parent if parent else '',
 923                          past),
 924                       terminus=past)
 925     global _root
 926     assert repo
 927     assert len(path)
 928     if parent:
 929         for x in parent:
 930             assert len(x) == 2
 931             assert type(x[0]) in (bytes, str)
 932             assert type(x[1]) in item_types
 933         assert parent[0][1] == _root
 934         if not S_ISDIR(item_mode(parent[-1][1])):
 935             raise IOError(ENOTDIR,
 936                           'path resolution parent %r is not a directory'
 937                           % (parent,))
 938     is_absolute, must_be_dir, future = _decompose_path(path)
 939     if must_be_dir:
 940         follow = True
 941     if not future:  # path was effectively '.' or '/'
 942         if is_absolute:
 943             return notice_resolution(((b'', _root),))
 944         if parent:
 945             return notice_resolution(tuple(parent))
 946         return notice_resolution(((b'', _root),))
 947     if is_absolute:
 948         past = [(b'', _root)]
 949     else:
 950         past = list(parent) if parent else [(b'', _root)]
 951     hops = 0
 952     while True:
 953         if not future:
 954             if must_be_dir and not S_ISDIR(item_mode(past[-1][1])):
 955                 raise_dir_required_but_not_dir(path, parent, past)
 956             return notice_resolution(tuple(past))
 957         segment = future.pop()
 958         if segment == b'..':
 959             assert len(past) > 0
 960             if len(past) > 1:  # .. from / is /
 961                 assert S_ISDIR(item_mode(past[-1][1]))
 962                 past.pop()
 963         else:
 964             parent_name, parent_item = past[-1]
 965             wanted = (segment,) if not want_meta else (b'.', segment)
 966             items = tuple(contents(repo, parent_item, names=wanted,
 967                                    want_meta=want_meta))
 968             if not want_meta:
 969                 item = items[0][1] if items else None
 970             else:  # First item will be '.' and have the metadata
 971                 item = items[1][1] if len(items) == 2 else None
 972                 dot, dot_item = items[0]
 973                 assert dot == b'.'
 974                 past[-1] = parent_name, parent_item
 975             if not item:
 976                 past.append((segment, None),)
 977                 return notice_resolution(tuple(past))
 978             mode = item_mode(item)
 979             if not S_ISLNK(mode):
 980                 if not S_ISDIR(mode):
 981                     past.append((segment, item),)
 982                     if future:
 983                         raise IOError(ENOTDIR,
 984                                       'path %r%s ends internally in non-directory here: %r'
 985                                       % (path,
 986                                          ' (relative to %r)' % parent if parent else '',
 987                                          past),
 988                                       terminus=past)
 989                     if must_be_dir:
 990                         raise_dir_required_but_not_dir(path, parent, past)
 991                     return notice_resolution(tuple(past))
 992                 # It's treeish
 993                 if want_meta and type(item) in real_tree_types:
 994                     dir_meta = _find_treeish_oid_metadata(repo, item.oid)
 995                     if dir_meta:
 996                         item = item._replace(meta=dir_meta)
 997                 past.append((segment, item))
 998             else:  # symlink
 999                 if not future and not follow:
1000                     past.append((segment, item),)
1001                     continue
1002                 if hops > 100:
1003                     raise IOError(ELOOP,
1004                                   'too many symlinks encountered while resolving %r%s'
1005                                   % (path, ' relative to %r' % parent if parent else ''),
1006                                   terminus=tuple(past + [(segment, item)]))
1007                 target = readlink(repo, item)
1008                 is_absolute, _, target_future = _decompose_path(target)
1009                 if is_absolute:
1010                     if not target_future:  # path was effectively '/'
1011                         return notice_resolution(((b'', _root),))
1012                     past = [(b'', _root)]
1013                     future = target_future
1014                 else:
1015                     future.extend(target_future)
1016                 hops += 1
1017
1018 def resolve(repo, path, parent=None, want_meta=True, follow=True):
1019     """Follow the path in the virtual filesystem and return a tuple
1020     representing the location, if any, denoted by the path.  Each
1021     element in the result tuple will be (name, info), where info will
1022     be a VFS item that can be passed to functions like item_mode().
1023
1024     If follow is false, and if the final path element is a symbolic
1025     link, don't follow it, just return it in the result.
1026
1027     If a path segment that does not exist is encountered during
1028     resolution, the result will represent the location of the missing
1029     item, and that item in the result will be None.
1030
1031     Any attempt to traverse a non-directory will raise a VFS ENOTDIR
1032     IOError exception.
1033
1034     Any symlinks along the path, including at the end, will be
1035     resolved.  A VFS IOError with the errno attribute set to ELOOP
1036     will be raised if too many symlinks are traversed while following
1037     the path.  That exception is effectively like a normal
1038     ELOOP IOError exception, but will include a terminus element
1039     describing the location of the failure, which will be a tuple of
1040     (name, info) elements.
1041
1042     The parent, if specified, must be a sequence of (name, item)
1043     tuples, and will provide the starting point for the resolution of
1044     the path.  If no parent is specified, resolution will start at
1045     '/'.
1046
1047     The result may include elements of parent directly, so they must
1048     not be modified later.  If this is a concern, pass in "name,
1049     copy_item(item) for name, item in parent" instead.
1050
1051     When want_meta is true, detailed metadata will be included in each
1052     result item if it's avaiable, otherwise item.meta will be an
1053     integer mode.  The metadata size may or may not be provided, but
1054     can be computed by item_size() or augment_item_meta(...,
1055     include_size=True).  Setting want_meta=False is rarely desirable
1056     since it can limit the VFS to just the metadata git itself can
1057     represent, and so, as an example, fifos and sockets will appear to
1058     be regular files (e.g. S_ISREG(item_mode(item)) will be true) .
1059     But the option is provided because it may be more efficient when
1060     only the path names or the more limited metadata is sufficient.
1061
1062     Do not modify any item.meta Metadata instances directly.  If
1063     needed, make a copy via item.meta.copy() and modify that instead.
1064
1065     """
1066     if repo.is_remote():
1067         # Redirect to the more efficient remote version
1068         return repo.resolve(path, parent=parent, want_meta=want_meta,
1069                             follow=follow)
1070     result = _resolve_path(repo, path, parent=parent, want_meta=want_meta,
1071                            follow=follow)
1072     _, leaf_item = result[-1]
1073     if leaf_item and follow:
1074         assert not S_ISLNK(item_mode(leaf_item))
1075     return result
1076
1077 def try_resolve(repo, path, parent=None, want_meta=True):
1078     """If path does not refer to a symlink, does not exist, or refers to a
1079     valid symlink, behave exactly like resolve(..., follow=True).  If
1080     path refers to an invalid symlink, behave like resolve(...,
1081     follow=False).
1082
1083     """
1084     res = resolve(repo, path, parent=parent, want_meta=want_meta, follow=False)
1085     leaf_name, leaf_item = res[-1]
1086     if not leaf_item:
1087         return res
1088     if not S_ISLNK(item_mode(leaf_item)):
1089         return res
1090     follow = resolve(repo, leaf_name, parent=res[:-1], want_meta=want_meta)
1091     follow_name, follow_item = follow[-1]
1092     if follow_item:
1093         return follow
1094     return res
1095
1096 def augment_item_meta(repo, item, include_size=False):
1097     """Ensure item has a Metadata instance for item.meta.  If item.meta is
1098     currently a mode, replace it with a compatible "fake" Metadata
1099     instance.  If include_size is true, ensure item.meta.size is
1100     correct, computing it if needed.  If item.meta is a Metadata
1101     instance, this call may modify it in place or replace it.
1102
1103     """
1104     # If we actually had parallelism, we'd need locking...
1105     assert repo
1106     m = item.meta
1107     if isinstance(m, Metadata):
1108         if include_size and m.size is None:
1109             m.size = _compute_item_size(repo, item)
1110             return item._replace(meta=m)
1111         return item
1112     # m is mode
1113     meta = Metadata()
1114     meta.mode = m
1115     meta.uid = meta.gid = None
1116     meta.atime = meta.mtime = meta.ctime = 0
1117     if S_ISLNK(m):
1118         if isinstance(item, FakeLink):
1119             target = item.target
1120         else:
1121             target = _readlink(repo, item.oid)
1122         meta.symlink_target = target
1123         meta.size = len(target)
1124     elif include_size:
1125         meta.size = _compute_item_size(repo, item)
1126     return item._replace(meta=meta)
1127
1128 def fill_in_metadata_if_dir(repo, item):
1129     """If item is a directory and item.meta is not a Metadata instance,
1130     attempt to find the metadata for the directory.  If found, return
1131     a new item augmented to include that metadata.  Otherwise, return
1132     item.  May be useful for the output of contents().
1133
1134     """
1135     if S_ISDIR(item_mode(item)) and not isinstance(item.meta, Metadata):
1136         items = tuple(contents(repo, item, (b'.',), want_meta=True))
1137         assert len(items) == 1
1138         assert items[0][0] == b'.'
1139         item = items[0][1]
1140     return item
1141
1142 def ensure_item_has_metadata(repo, item, include_size=False):
1143     """If item is a directory, attempt to find and add its metadata.  If
1144     the item still doesn't have a Metadata instance for item.meta,
1145     give it one via augment_item_meta().  May be useful for the output
1146     of contents().
1147
1148     """
1149     return augment_item_meta(repo,
1150                              fill_in_metadata_if_dir(repo, item),
1151                              include_size=include_size)