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, ENOTDIR
  53 from itertools import chain, 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, vint
  60 from bup.compat import hexstr, range, str_type
  61 from bup.git import BUP_CHUNKED, 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 = (Item, Chunky, Root, Tags, RevList, Commit)
 278 real_tree_types = (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     if isinstance(x, bytes):
 396         tag = x[:4]
 397         if tag in (b'itm:', b'rvl:') and len(x) == 24:
 398             return True
 399         if tag == b'res:':
 400             return True
 401     return False
 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, overwrite=False):
 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         if overwrite:
 415             _cache[key] = value
 416         return
 417     if len(_cache) < _cache_max_items:
 418         _cache_keys.append(key)
 419         _cache[key] = value
 420         return
 421     victim_i = randrange(0, len(_cache_keys))
 422     victim = _cache_keys[victim_i]
 423     del _cache[victim]
 424     _cache_keys[victim_i] = key
 425     _cache[key] = value
 426
 427 def _has_metadata_if_needed(item, need_meta):
 428     if not need_meta:
 429         return True
 430     if isinstance(item.meta, Metadata):
 431         return True
 432     return False
 433
 434 def cache_get_commit_item(oid, need_meta=True):
 435     """Return the requested tree item if it can be found in the cache.
 436     When need_meta is true don't return a cached item that only has a
 437     mode."""
 438     # tree might be stored independently, or as '.' with its entries.
 439     commit_key = b'itm:' + oid
 440     item = cache_get(commit_key)
 441     if item:
 442         if _has_metadata_if_needed(item, need_meta):
 443             return item
 444     entries = cache_get(b'rvl:' + oid)
 445     if entries:
 446         item = entries[b'.']
 447         if _has_metadata_if_needed(item, need_meta):
 448             return item
 449     return None
 450
 451 def copy_item(item):
 452     """Return a completely independent copy of item, such that
 453     modifications will not affect the original.
 454
 455     """
 456     meta = getattr(item, 'meta', None)
 457     if isinstance(meta, Metadata):
 458         return(item._replace(meta=meta.copy()))
 459     return item
 460
 461 def item_mode(item):
 462     """Return the integer mode (stat st_mode) for item."""
 463     m = item.meta
 464     if isinstance(m, Metadata):
 465         return m.mode
 466     return m
 467
 468 def _read_dir_meta(bupm):
 469     # This is because save writes unmodified Metadata() entries for
 470     # fake parents -- test-save-strip-graft.sh demonstrates.
 471     m = Metadata.read(bupm)
 472     if not m:
 473         return default_dir_mode
 474     assert m.mode is not None
 475     if m.size is None:
 476         m.size = 0
 477     return m
 478
 479 def tree_data_and_bupm(repo, oid):
 480     """Return (tree_bytes, bupm_oid) where bupm_oid will be None if the
 481     tree has no metadata (i.e. older bup save, or non-bup tree).
 482
 483     """
 484     assert len(oid) == 20
 485     it = repo.cat(hexlify(oid))
 486     _, item_t, size = next(it)
 487     data = b''.join(it)
 488     if item_t == b'commit':
 489         commit = parse_commit(data)
 490         it = repo.cat(commit.tree)
 491         _, item_t, size = next(it)
 492         data = b''.join(it)
 493         assert item_t == b'tree'
 494     elif item_t != b'tree':
 495         raise Exception('%s is not a tree or commit' % hexstr(oid))
 496     for _, mangled_name, sub_oid in tree_decode(data):
 497         if mangled_name == b'.bupm':
 498             return data, sub_oid
 499         if mangled_name > b'.bupm':
 500             break
 501     return data, None
 502
 503 def _find_treeish_oid_metadata(repo, oid):
 504     """Return the metadata for the tree or commit oid, or None if the tree
 505     has no metadata (i.e. older bup save, or non-bup tree).
 506
 507     """
 508     tree_data, bupm_oid = tree_data_and_bupm(repo, oid)
 509     if bupm_oid:
 510         with _FileReader(repo, bupm_oid) as meta_stream:
 511             return _read_dir_meta(meta_stream)
 512     return None
 513
 514 def _readlink(repo, oid):
 515     return b''.join(repo.join(hexlify(oid)))
 516
 517 def readlink(repo, item):
 518     """Return the link target of item, which must be a symlink.  Reads the
 519     target from the repository if necessary."""
 520     assert repo
 521     assert S_ISLNK(item_mode(item))
 522     if isinstance(item, FakeLink):
 523         return item.target
 524     if isinstance(item.meta, Metadata):
 525         target = item.meta.symlink_target
 526         if target:
 527             return target
 528     return _readlink(repo, item.oid)
 529
 530 def _compute_item_size(repo, item):
 531     mode = item_mode(item)
 532     if S_ISREG(mode):
 533         size = _normal_or_chunked_file_size(repo, item.oid)
 534         return size
 535     if S_ISLNK(mode):
 536         if isinstance(item, FakeLink):
 537             return len(item.target)
 538         return len(_readlink(repo, item.oid))
 539     return 0
 540
 541 def item_size(repo, item):
 542     """Return the size of item, computing it if necessary."""
 543     m = item.meta
 544     if isinstance(m, Metadata) and m.size is not None:
 545         return m.size
 546     return _compute_item_size(repo, item)
 547
 548 def tree_data_reader(repo, oid):
 549     """Return an open reader for all of the data contained within oid.  If
 550     oid refers to a tree, recursively concatenate all of its contents."""
 551     return _FileReader(repo, oid)
 552
 553 def fopen(repo, item):
 554     """Return an open reader for the given file item."""
 555     assert S_ISREG(item_mode(item))
 556     return tree_data_reader(repo, item.oid)
 557
 558 def _commit_item_from_data(oid, data):
 559     info = parse_commit(data)
 560     return Commit(meta=default_dir_mode,
 561                   oid=unhexlify(info.tree),
 562                   coid=oid)
 563
 564 def _commit_item_from_oid(repo, oid, require_meta):
 565     commit = cache_get_commit_item(oid, need_meta=require_meta)
 566     if commit and ((not require_meta) or isinstance(commit.meta, Metadata)):
 567         return commit
 568     it = repo.cat(hexlify(oid))
 569     _, typ, size = next(it)
 570     assert typ == b'commit'
 571     commit = _commit_item_from_data(oid, b''.join(it))
 572     if require_meta:
 573         meta = _find_treeish_oid_metadata(repo, commit.oid)
 574         if meta:
 575             commit = commit._replace(meta=meta)
 576     commit_key = b'itm:' + oid
 577     cache_notice(commit_key, commit, overwrite=True)
 578     return commit
 579
 580 def _revlist_item_from_oid(repo, oid, require_meta):
 581     commit = _commit_item_from_oid(repo, oid, require_meta)
 582     return RevList(oid=oid, meta=commit.meta)
 583
 584 def root_items(repo, names=None, want_meta=True):
 585     """Yield (name, item) for the items in '/' in the VFS.  Return
 586     everything if names is logically false, otherwise return only
 587     items with a name in the collection.
 588
 589     """
 590     # FIXME: what about non-leaf refs like 'refs/heads/foo/bar/baz?
 591
 592     global _root, _tags
 593     if not names:
 594         yield b'.', _root
 595         yield b'.tag', _tags
 596         # FIXME: maybe eventually support repo.clone() or something
 597         # and pass in two repos, so we can drop the tuple() and stream
 598         # in parallel (i.e. meta vs refs).
 599         for name, oid in tuple(repo.refs([], limit_to_heads=True)):
 600             assert(name.startswith(b'refs/heads/'))
 601             yield name[11:], _revlist_item_from_oid(repo, oid, want_meta)
 602         return
 603
 604     if b'.' in names:
 605         yield b'.', _root
 606     if b'.tag' in names:
 607         yield b'.tag', _tags
 608     for ref in names:
 609         if ref in (b'.', b'.tag'):
 610             continue
 611         it = repo.cat(b'refs/heads/' + ref)
 612         oidx, typ, size = next(it)
 613         if not oidx:
 614             for _ in it: pass
 615             continue
 616         assert typ == b'commit'
 617         commit = parse_commit(b''.join(it))
 618         yield ref, _revlist_item_from_oid(repo, unhexlify(oidx), want_meta)
 619
 620 def ordered_tree_entries(tree_data, bupm=None):
 621     """Yields (name, mangled_name, kind, gitmode, oid) for each item in
 622     tree, sorted by name.
 623
 624     """
 625     # Sadly, the .bupm entries currently aren't in git tree order,
 626     # but in unmangled name order. They _do_ account for the fact
 627     # that git sorts trees (including chunked trees) as if their
 628     # names ended with "/" (so "fo" sorts after "fo." iff fo is a
 629     # directory), but we apply this on the unmangled names in save
 630     # rather than on the mangled names.
 631     # This makes streaming impossible when we need the metadata.
 632     def result_from_tree_entry(tree_entry):
 633         gitmode, mangled_name, oid = tree_entry
 634         name, kind = git.demangle_name(mangled_name, gitmode)
 635         return name, mangled_name, kind, gitmode, oid
 636
 637     tree_ents = (result_from_tree_entry(x) for x in tree_decode(tree_data))
 638     if bupm:
 639         tree_ents = sorted(tree_ents, key=lambda x: x[0])
 640     for ent in tree_ents:
 641         yield ent
 642
 643 def tree_items(oid, tree_data, names=frozenset(), bupm=None):
 644
 645     def tree_item(ent_oid, kind, gitmode):
 646         if kind == BUP_CHUNKED:
 647             meta = Metadata.read(bupm) if bupm else default_file_mode
 648             return Chunky(oid=ent_oid, meta=meta)
 649
 650         if S_ISDIR(gitmode):
 651             # No metadata here (accessable via '.' inside ent_oid).
 652             return Item(meta=default_dir_mode, oid=ent_oid)
 653
 654         meta = Metadata.read(bupm) if bupm else None
 655         # handle the case of metadata being empty/missing in bupm
 656         # (or there not being bupm at all)
 657         if meta is None:
 658             meta = _default_mode_for_gitmode(gitmode)
 659         return Item(oid=ent_oid, meta=meta)
 660
 661     assert len(oid) == 20
 662     if not names:
 663         dot_meta = _read_dir_meta(bupm) if bupm else default_dir_mode
 664         yield b'.', Item(oid=oid, meta=dot_meta)
 665         tree_entries = ordered_tree_entries(tree_data, bupm)
 666         for name, mangled_name, kind, gitmode, ent_oid in tree_entries:
 667             if mangled_name == b'.bupm':
 668                 continue
 669             assert name != b'.'
 670             yield name, tree_item(ent_oid, kind, gitmode)
 671         return
 672
 673     # Assumes the tree is properly formed, i.e. there are no
 674     # duplicates, and entries will be in git tree order.
 675     if isinstance(names, (frozenset, set)):
 676         names = frozenset(names)
 677     remaining = len(names)
 678
 679     # Account for the bupm sort order issue (cf. ordered_tree_entries above)
 680     last_name = max(names) if bupm else max(names) + b'/'
 681
 682     if b'.' in names:
 683         dot_meta = _read_dir_meta(bupm) if bupm else default_dir_mode
 684         yield b'.', Item(oid=oid, meta=dot_meta)
 685         if remaining == 1:
 686             return
 687         remaining -= 1
 688
 689     tree_entries = ordered_tree_entries(tree_data, bupm)
 690     for name, mangled_name, kind, gitmode, ent_oid in tree_entries:
 691         if mangled_name == b'.bupm':
 692             continue
 693         assert name != b'.'
 694         if name not in names:
 695             if name > last_name:
 696                 break  # given bupm sort order, we're finished
 697             if (kind == BUP_CHUNKED or not S_ISDIR(gitmode)) and bupm:
 698                 Metadata.read(bupm)
 699             continue
 700         yield name, tree_item(ent_oid, kind, gitmode)
 701         if remaining == 1:
 702             break
 703         remaining -= 1
 704
 705 def tree_items_with_meta(repo, oid, tree_data, names):
 706     # For now, the .bupm order doesn't quite match git's, and we don't
 707     # load the tree data incrementally anyway, so we just work in RAM
 708     # via tree_data.
 709     assert len(oid) == 20
 710     bupm = None
 711     for _, mangled_name, sub_oid in tree_decode(tree_data):
 712         if mangled_name == b'.bupm':
 713             bupm = _FileReader(repo, sub_oid)
 714             break
 715         if mangled_name > b'.bupm':
 716             break
 717     for item in tree_items(oid, tree_data, names, bupm):
 718         yield item
 719
 720 _save_name_rx = re.compile(br'^\d\d\d\d-\d\d-\d\d-\d{6}(-\d+)?$')
 721
 722 def _reverse_suffix_duplicates(strs):
 723     """Yields the elements of strs, with any runs of duplicate values
 724     suffixed with -N suffixes, where the zero padded integer N
 725     decreases to 0 by 1 (e.g. 10, 09, ..., 00).
 726
 727     """
 728     for name, duplicates in groupby(strs):
 729         ndup = len(tuple(duplicates))
 730         if ndup == 1:
 731             yield name
 732         else:
 733             ndig = len(str(ndup - 1))
 734             fmt = b'%s-' + b'%0' + (b'%d' % ndig) + b'd'
 735             for i in range(ndup - 1, -1, -1):
 736                 yield fmt % (name, i)
 737
 738 def parse_rev(f):
 739     items = f.readline().split(None)
 740     assert len(items) == 2
 741     tree, auth_sec = items
 742     return unhexlify(tree), int(auth_sec)
 743
 744 def _name_for_rev(rev):
 745     commit_oidx, (tree_oid, utc) = rev
 746     return strftime('%Y-%m-%d-%H%M%S', localtime(utc)).encode('ascii')
 747
 748 def _item_for_rev(rev):
 749     commit_oidx, (tree_oid, utc) = rev
 750     coid = unhexlify(commit_oidx)
 751     item = cache_get_commit_item(coid, need_meta=False)
 752     if item:
 753         return item
 754     item = Commit(meta=default_dir_mode, oid=tree_oid, coid=coid)
 755     commit_key = b'itm:' + coid
 756     cache_notice(commit_key, item)
 757     return item
 758
 759 # non-string singleton
 760 _HAS_META_ENTRY = object()
 761
 762 def cache_commit(repo, oid, require_meta=True):
 763     """Build, cache, and return a "name -> commit_item" dict of the entire
 764     commit rev-list.
 765
 766     """
 767     entries = {}
 768     entries[b'.'] = _revlist_item_from_oid(repo, oid, require_meta)
 769     revs = repo.rev_list((hexlify(oid),), format=b'%T %at',
 770                          parse=parse_rev)
 771     rev_items, rev_names = tee(revs)
 772     revs = None  # Don't disturb the tees
 773     rev_names = _reverse_suffix_duplicates(_name_for_rev(x) for x in rev_names)
 774     rev_items = (_item_for_rev(x) for x in rev_items)
 775     tip = None
 776     for item in rev_items:
 777         name = next(rev_names)
 778         tip = tip or (name, item)
 779         entries[name] = item
 780     entries[b'latest'] = FakeLink(meta=default_symlink_mode, target=tip[0])
 781     revlist_key = b'rvl:' + tip[1].coid
 782     entries[_HAS_META_ENTRY] = require_meta
 783     cache_notice(revlist_key, entries, overwrite=True)
 784     return entries
 785
 786 def revlist_items(repo, oid, names, require_meta=True):
 787     assert len(oid) == 20
 788
 789     # Special case '.' instead of caching the whole history since it's
 790     # the only way to get the metadata for the commit.
 791     if names and all(x == b'.' for x in names):
 792         yield b'.', _revlist_item_from_oid(repo, oid, require_meta)
 793         return
 794
 795     # For now, don't worry about the possibility of the contents being
 796     # "too big" for the cache.
 797     revlist_key = b'rvl:' + oid
 798     entries = cache_get(revlist_key)
 799     if entries and require_meta and not entries[_HAS_META_ENTRY]:
 800         entries = None
 801     if not entries:
 802         entries = cache_commit(repo, oid, require_meta)
 803
 804     if not names:
 805         for name in sorted((n for n in entries.keys() if n != _HAS_META_ENTRY)):
 806             yield name, entries[name]
 807         return
 808
 809     names = frozenset(name for name in names
 810                       if _save_name_rx.match(name) or name in (b'.', b'latest'))
 811
 812     if b'.' in names:
 813         yield b'.', entries[b'.']
 814     for name in (n for n in names if n != b'.'):
 815         if name == _HAS_META_ENTRY:
 816             continue
 817         commit = entries.get(name)
 818         if commit:
 819             yield name, commit
 820
 821 def tags_items(repo, names):
 822     global _tags
 823
 824     def tag_item(oid):
 825         assert len(oid) == 20
 826         oidx = hexlify(oid)
 827         it = repo.cat(oidx)
 828         _, typ, size = next(it)
 829         if typ == b'commit':
 830             return cache_get_commit_item(oid, need_meta=False) \
 831                 or _commit_item_from_data(oid, b''.join(it))
 832         for _ in it: pass
 833         if typ == b'blob':
 834             return Item(meta=default_file_mode, oid=oid)
 835         elif typ == b'tree':
 836             return Item(meta=default_dir_mode, oid=oid)
 837         raise Exception('unexpected tag type ' + typ.decode('ascii')
 838                         + ' for tag ' + path_msg(name))
 839
 840     if not names:
 841         yield b'.', _tags
 842         # We have to pull these all into ram because tag_item calls cat()
 843         for name, oid in tuple(repo.refs(names, limit_to_tags=True)):
 844             assert(name.startswith(b'refs/tags/'))
 845             name = name[10:]
 846             yield name, tag_item(oid)
 847         return
 848
 849     # Assumes no duplicate refs
 850     if isinstance(names, (frozenset, set)):
 851         names = frozenset(names)
 852     remaining = len(names)
 853     last_name = max(names)
 854     if b'.' in names:
 855         yield b'.', _tags
 856         if remaining == 1:
 857             return
 858         remaining -= 1
 859
 860     for name, oid in repo.refs(names, limit_to_tags=True):
 861         assert(name.startswith(b'refs/tags/'))
 862         name = name[10:]
 863         if name > last_name:
 864             return
 865         if name not in names:
 866             continue
 867         yield name, tag_item(oid)
 868         if remaining == 1:
 869             return
 870         remaining -= 1
 871
 872 def contents(repo, item, names=None, want_meta=True):
 873     """Yields information about the items contained in item.  Yields
 874     (name, item) for each name in names, if the name exists, in an
 875     unspecified order.  If there are no names, then yields (name,
 876     item) for all items, including, a first item named '.'
 877     representing the container itself.
 878
 879     The meta value for any directories other than '.' will be a
 880     default directory mode, not a Metadata object.  This is because
 881     the actual metadata for a directory is stored inside the directory
 882     (see fill_in_metadata_if_dir() or ensure_item_has_metadata()).
 883
 884     Note that want_meta is advisory.  For any given item, item.meta
 885     might be a Metadata instance or a mode, and if the former,
 886     meta.size might be None.  Missing sizes can be computed via via
 887     item_size() or augment_item_meta(..., include_size=True).
 888
 889     Do not modify any item.meta Metadata instances directly.  If
 890     needed, make a copy via item.meta.copy() and modify that instead.
 891
 892     """
 893     # Q: are we comfortable promising '.' first when no names?
 894     global _root, _tags
 895     assert repo
 896     assert S_ISDIR(item_mode(item))
 897     if isinstance(item, real_tree_types):
 898         it = repo.cat(hexlify(item.oid))
 899         _, obj_t, size = next(it)
 900         data = b''.join(it)
 901         if obj_t != b'tree':
 902             for _ in it: pass
 903             # Note: it shouldn't be possible to see an Item with type
 904             # 'commit' since a 'commit' should always produce a Commit.
 905             raise Exception('unexpected git ' + obj_t.decode('ascii'))
 906         if want_meta:
 907             item_gen = tree_items_with_meta(repo, item.oid, data, names)
 908         else:
 909             item_gen = tree_items(item.oid, data, names)
 910     elif isinstance(item, RevList):
 911         item_gen = revlist_items(repo, item.oid, names,
 912                                  require_meta=want_meta)
 913     elif isinstance(item, Root):
 914         item_gen = root_items(repo, names, want_meta)
 915     elif isinstance(item, Tags):
 916         item_gen = tags_items(repo, names)
 917     else:
 918         raise Exception('unexpected VFS item ' + str(item))
 919     for x in item_gen:
 920         yield x
 921
 922 def _resolve_path(repo, path, parent=None, want_meta=True, follow=True):
 923     cache_key = b'res:%d%d%d:%s\0%s' \
 924                 % (bool(want_meta), bool(follow), repo.id(),
 925                    (b'/'.join(x[0] for x in parent) if parent else b''),
 926                    path)
 927     resolution = cache_get(cache_key)
 928     if resolution:
 929         return resolution
 930
 931     def notice_resolution(r):
 932         cache_notice(cache_key, r)
 933         return r
 934
 935     def raise_dir_required_but_not_dir(path, parent, past):
 936         raise IOError(ENOTDIR,
 937                       "path %s%s resolves to non-directory %r"
 938                       % (path,
 939                          ' (relative to %r)' % parent if parent else '',
 940                          past),
 941                       terminus=past)
 942     global _root
 943     assert repo
 944     assert len(path)
 945     if parent:
 946         for x in parent:
 947             assert len(x) == 2
 948             assert isinstance(x[0], (bytes, str_type))
 949             assert isinstance(x[1], item_types)
 950         assert parent[0][1] == _root
 951         if not S_ISDIR(item_mode(parent[-1][1])):
 952             raise IOError(ENOTDIR,
 953                           'path resolution parent %r is not a directory'
 954                           % (parent,))
 955     is_absolute, must_be_dir, future = _decompose_path(path)
 956     if must_be_dir:
 957         follow = True
 958     if not future:  # path was effectively '.' or '/'
 959         if is_absolute:
 960             return notice_resolution(((b'', _root),))
 961         if parent:
 962             return notice_resolution(tuple(parent))
 963         return notice_resolution(((b'', _root),))
 964     if is_absolute:
 965         past = [(b'', _root)]
 966     else:
 967         past = list(parent) if parent else [(b'', _root)]
 968     hops = 0
 969     while True:
 970         if not future:
 971             if must_be_dir and not S_ISDIR(item_mode(past[-1][1])):
 972                 raise_dir_required_but_not_dir(path, parent, past)
 973             return notice_resolution(tuple(past))
 974         segment = future.pop()
 975         if segment == b'..':
 976             assert len(past) > 0
 977             if len(past) > 1:  # .. from / is /
 978                 assert S_ISDIR(item_mode(past[-1][1]))
 979                 past.pop()
 980         else:
 981             parent_name, parent_item = past[-1]
 982             wanted = (segment,) if not want_meta else (b'.', segment)
 983             items = tuple(contents(repo, parent_item, names=wanted,
 984                                    want_meta=want_meta))
 985             if not want_meta:
 986                 item = items[0][1] if items else None
 987             else:  # First item will be '.' and have the metadata
 988                 item = items[1][1] if len(items) == 2 else None
 989                 dot, dot_item = items[0]
 990                 assert dot == b'.'
 991                 past[-1] = parent_name, parent_item
 992             if not item:
 993                 past.append((segment, None),)
 994                 return notice_resolution(tuple(past))
 995             mode = item_mode(item)
 996             if not S_ISLNK(mode):
 997                 if not S_ISDIR(mode):
 998                     past.append((segment, item),)
 999                     if future:
1000                         raise IOError(ENOTDIR,
1001                                       'path %r%s ends internally in non-directory here: %r'
1002                                       % (path,
1003                                          ' (relative to %r)' % parent if parent else '',
1004                                          past),
1005                                       terminus=past)
1006                     if must_be_dir:
1007                         raise_dir_required_but_not_dir(path, parent, past)
1008                     return notice_resolution(tuple(past))
1009                 # It's treeish
1010                 if want_meta and isinstance(item, real_tree_types):
1011                     dir_meta = _find_treeish_oid_metadata(repo, item.oid)
1012                     if dir_meta:
1013                         item = item._replace(meta=dir_meta)
1014                 past.append((segment, item))
1015             else:  # symlink
1016                 if not future and not follow:
1017                     past.append((segment, item),)
1018                     continue
1019                 if hops > 100:
1020                     raise IOError(ELOOP,
1021                                   'too many symlinks encountered while resolving %r%s'
1022                                   % (path, ' relative to %r' % parent if parent else ''),
1023                                   terminus=tuple(past + [(segment, item)]))
1024                 target = readlink(repo, item)
1025                 is_absolute, _, target_future = _decompose_path(target)
1026                 if is_absolute:
1027                     if not target_future:  # path was effectively '/'
1028                         return notice_resolution(((b'', _root),))
1029                     past = [(b'', _root)]
1030                     future = target_future
1031                 else:
1032                     future.extend(target_future)
1033                 hops += 1
1034
1035 def resolve(repo, path, parent=None, want_meta=True, follow=True):
1036     """Follow the path in the virtual filesystem and return a tuple
1037     representing the location, if any, denoted by the path.  Each
1038     element in the result tuple will be (name, info), where info will
1039     be a VFS item that can be passed to functions like item_mode().
1040
1041     If follow is false, and if the final path element is a symbolic
1042     link, don't follow it, just return it in the result.
1043
1044     If a path segment that does not exist is encountered during
1045     resolution, the result will represent the location of the missing
1046     item, and that item in the result will be None.
1047
1048     Any attempt to traverse a non-directory will raise a VFS ENOTDIR
1049     IOError exception.
1050
1051     Any symlinks along the path, including at the end, will be
1052     resolved.  A VFS IOError with the errno attribute set to ELOOP
1053     will be raised if too many symlinks are traversed while following
1054     the path.  That exception is effectively like a normal
1055     ELOOP IOError exception, but will include a terminus element
1056     describing the location of the failure, which will be a tuple of
1057     (name, info) elements.
1058
1059     The parent, if specified, must be a sequence of (name, item)
1060     tuples, and will provide the starting point for the resolution of
1061     the path.  If no parent is specified, resolution will start at
1062     '/'.
1063
1064     The result may include elements of parent directly, so they must
1065     not be modified later.  If this is a concern, pass in "name,
1066     copy_item(item) for name, item in parent" instead.
1067
1068     When want_meta is true, detailed metadata will be included in each
1069     result item if it's avaiable, otherwise item.meta will be an
1070     integer mode.  The metadata size may or may not be provided, but
1071     can be computed by item_size() or augment_item_meta(...,
1072     include_size=True).  Setting want_meta=False is rarely desirable
1073     since it can limit the VFS to just the metadata git itself can
1074     represent, and so, as an example, fifos and sockets will appear to
1075     be regular files (e.g. S_ISREG(item_mode(item)) will be true) .
1076     But the option is provided because it may be more efficient when
1077     only the path names or the more limited metadata is sufficient.
1078
1079     Do not modify any item.meta Metadata instances directly.  If
1080     needed, make a copy via item.meta.copy() and modify that instead.
1081
1082     """
1083     if repo.is_remote():
1084         # Redirect to the more efficient remote version
1085         return repo.resolve(path, parent=parent, want_meta=want_meta,
1086                             follow=follow)
1087     result = _resolve_path(repo, path, parent=parent, want_meta=want_meta,
1088                            follow=follow)
1089     _, leaf_item = result[-1]
1090     if leaf_item and follow:
1091         assert not S_ISLNK(item_mode(leaf_item))
1092     return result
1093
1094 def try_resolve(repo, path, parent=None, want_meta=True):
1095     """If path does not refer to a symlink, does not exist, or refers to a
1096     valid symlink, behave exactly like resolve(..., follow=True).  If
1097     path refers to an invalid symlink, behave like resolve(...,
1098     follow=False).
1099
1100     """
1101     res = resolve(repo, path, parent=parent, want_meta=want_meta, follow=False)
1102     leaf_name, leaf_item = res[-1]
1103     if not leaf_item:
1104         return res
1105     if not S_ISLNK(item_mode(leaf_item)):
1106         return res
1107     follow = resolve(repo, leaf_name, parent=res[:-1], want_meta=want_meta)
1108     follow_name, follow_item = follow[-1]
1109     if follow_item:
1110         return follow
1111     return res
1112
1113 def augment_item_meta(repo, item, include_size=False):
1114     """Ensure item has a Metadata instance for item.meta.  If item.meta is
1115     currently a mode, replace it with a compatible "fake" Metadata
1116     instance.  If include_size is true, ensure item.meta.size is
1117     correct, computing it if needed.  If item.meta is a Metadata
1118     instance, this call may modify it in place or replace it.
1119
1120     """
1121     # If we actually had parallelism, we'd need locking...
1122     assert repo
1123     m = item.meta
1124     if isinstance(m, Metadata):
1125         if include_size and m.size is None:
1126             m.size = _compute_item_size(repo, item)
1127             return item._replace(meta=m)
1128         return item
1129     # m is mode
1130     meta = Metadata()
1131     meta.mode = m
1132     meta.uid = meta.gid = None
1133     meta.atime = meta.mtime = meta.ctime = 0
1134     if S_ISLNK(m):
1135         if isinstance(item, FakeLink):
1136             target = item.target
1137         else:
1138             target = _readlink(repo, item.oid)
1139         meta.symlink_target = target
1140         meta.size = len(target)
1141     elif include_size:
1142         meta.size = _compute_item_size(repo, item)
1143     return item._replace(meta=meta)
1144
1145 def fill_in_metadata_if_dir(repo, item):
1146     """If item is a directory and item.meta is not a Metadata instance,
1147     attempt to find the metadata for the directory.  If found, return
1148     a new item augmented to include that metadata.  Otherwise, return
1149     item.  May be useful for the output of contents().
1150
1151     """
1152     if S_ISDIR(item_mode(item)) and not isinstance(item.meta, Metadata):
1153         items = tuple(contents(repo, item, (b'.',), want_meta=True))
1154         assert len(items) == 1
1155         assert items[0][0] == b'.'
1156         item = items[0][1]
1157     return item
1158
1159 def ensure_item_has_metadata(repo, item, include_size=False):
1160     """If item is a directory, attempt to find and add its metadata.  If
1161     the item still doesn't have a Metadata instance for item.meta,
1162     give it one via augment_item_meta().  May be useful for the output
1163     of contents().
1164
1165     """
1166     return augment_item_meta(repo,
1167                              fill_in_metadata_if_dir(repo, item),
1168                              include_size=include_size)