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 cache_get_revlist_item(oid, need_meta=True):
 442     commit = cache_get_commit_item(oid, need_meta=need_meta)
 443     if commit:
 444         return RevList(oid=oid, meta=commit.meta)
 445
 446 def copy_item(item):
 447     """Return a completely independent copy of item, such that
 448     modifications will not affect the original.
 449
 450     """
 451     meta = getattr(item, 'meta', None)
 452     if isinstance(meta, Metadata):
 453         return(item._replace(meta=meta.copy()))
 454     return item
 455
 456 def item_mode(item):
 457     """Return the integer mode (stat st_mode) for item."""
 458     m = item.meta
 459     if isinstance(m, Metadata):
 460         return m.mode
 461     return m
 462
 463 def _read_dir_meta(bupm):
 464     # This is because save writes unmodified Metadata() entries for
 465     # fake parents -- test-save-strip-graft.sh demonstrates.
 466     m = Metadata.read(bupm)
 467     if not m:
 468         return default_dir_mode
 469     assert m.mode is not None
 470     if m.size is None:
 471         m.size = 0
 472     return m
 473
 474 def tree_data_and_bupm(repo, oid):
 475     """Return (tree_bytes, bupm_oid) where bupm_oid will be None if the
 476     tree has no metadata (i.e. older bup save, or non-bup tree).
 477
 478     """
 479     assert len(oid) == 20
 480     it = repo.cat(hexlify(oid))
 481     _, item_t, size = next(it)
 482     data = b''.join(it)
 483     if item_t == b'commit':
 484         commit = parse_commit(data)
 485         it = repo.cat(commit.tree)
 486         _, item_t, size = next(it)
 487         data = b''.join(it)
 488         assert item_t == b'tree'
 489     elif item_t != b'tree':
 490         raise Exception('%s is not a tree or commit' % hexstr(oid))
 491     for _, mangled_name, sub_oid in tree_decode(data):
 492         if mangled_name == b'.bupm':
 493             return data, sub_oid
 494         if mangled_name > b'.bupm':
 495             break
 496     return data, None
 497
 498 def _find_treeish_oid_metadata(repo, oid):
 499     """Return the metadata for the tree or commit oid, or None if the tree
 500     has no metadata (i.e. older bup save, or non-bup tree).
 501
 502     """
 503     tree_data, bupm_oid = tree_data_and_bupm(repo, oid)
 504     if bupm_oid:
 505         with _FileReader(repo, bupm_oid) as meta_stream:
 506             return _read_dir_meta(meta_stream)
 507     return None
 508
 509 def _readlink(repo, oid):
 510     return b''.join(repo.join(hexlify(oid)))
 511
 512 def readlink(repo, item):
 513     """Return the link target of item, which must be a symlink.  Reads the
 514     target from the repository if necessary."""
 515     assert repo
 516     assert S_ISLNK(item_mode(item))
 517     if isinstance(item, FakeLink):
 518         return item.target
 519     if isinstance(item.meta, Metadata):
 520         target = item.meta.symlink_target
 521         if target:
 522             return target
 523     return _readlink(repo, item.oid)
 524
 525 def _compute_item_size(repo, item):
 526     mode = item_mode(item)
 527     if S_ISREG(mode):
 528         size = _normal_or_chunked_file_size(repo, item.oid)
 529         return size
 530     if S_ISLNK(mode):
 531         if isinstance(item, FakeLink):
 532             return len(item.target)
 533         return len(_readlink(repo, item.oid))
 534     return 0
 535
 536 def item_size(repo, item):
 537     """Return the size of item, computing it if necessary."""
 538     m = item.meta
 539     if isinstance(m, Metadata) and m.size is not None:
 540         return m.size
 541     return _compute_item_size(repo, item)
 542
 543 def tree_data_reader(repo, oid):
 544     """Return an open reader for all of the data contained within oid.  If
 545     oid refers to a tree, recursively concatenate all of its contents."""
 546     return _FileReader(repo, oid)
 547
 548 def fopen(repo, item):
 549     """Return an open reader for the given file item."""
 550     assert S_ISREG(item_mode(item))
 551     return tree_data_reader(repo, item.oid)
 552
 553 def _commit_item_from_data(oid, data):
 554     info = parse_commit(data)
 555     return Commit(meta=default_dir_mode,
 556                   oid=unhexlify(info.tree),
 557                   coid=oid)
 558
 559 def _commit_item_from_oid(repo, oid, require_meta):
 560     commit = cache_get_commit_item(oid, need_meta=require_meta)
 561     if commit and ((not require_meta) or isinstance(commit.meta, Metadata)):
 562         return commit
 563     it = repo.cat(hexlify(oid))
 564     _, typ, size = next(it)
 565     assert typ == b'commit'
 566     commit = _commit_item_from_data(oid, b''.join(it))
 567     if require_meta:
 568         meta = _find_treeish_oid_metadata(repo, commit.oid)
 569         if meta:
 570             commit = commit._replace(meta=meta)
 571     commit_key = b'itm:' + oid
 572     cache_notice(commit_key, commit)
 573     return commit
 574
 575 def _revlist_item_from_oid(repo, oid, require_meta):
 576     commit = _commit_item_from_oid(repo, oid, require_meta)
 577     return RevList(oid=oid, meta=commit.meta)
 578
 579 def root_items(repo, names=None, want_meta=True):
 580     """Yield (name, item) for the items in '/' in the VFS.  Return
 581     everything if names is logically false, otherwise return only
 582     items with a name in the collection.
 583
 584     """
 585     # FIXME: what about non-leaf refs like 'refs/heads/foo/bar/baz?
 586
 587     global _root, _tags
 588     if not names:
 589         yield b'.', _root
 590         yield b'.tag', _tags
 591         # FIXME: maybe eventually support repo.clone() or something
 592         # and pass in two repos, so we can drop the tuple() and stream
 593         # in parallel (i.e. meta vs refs).
 594         for name, oid in tuple(repo.refs([], limit_to_heads=True)):
 595             assert(name.startswith(b'refs/heads/'))
 596             yield name[11:], _revlist_item_from_oid(repo, oid, want_meta)
 597         return
 598
 599     if b'.' in names:
 600         yield b'.', _root
 601     if b'.tag' in names:
 602         yield b'.tag', _tags
 603     for ref in names:
 604         if ref in (b'.', b'.tag'):
 605             continue
 606         it = repo.cat(b'refs/heads/' + ref)
 607         oidx, typ, size = next(it)
 608         if not oidx:
 609             for _ in it: pass
 610             continue
 611         assert typ == b'commit'
 612         commit = parse_commit(b''.join(it))
 613         yield ref, _revlist_item_from_oid(repo, unhexlify(oidx), want_meta)
 614
 615 def ordered_tree_entries(tree_data, bupm=None):
 616     """Yields (name, mangled_name, kind, gitmode, oid) for each item in
 617     tree, sorted by name.
 618
 619     """
 620     # Sadly, the .bupm entries currently aren't in git tree order,
 621     # i.e. they don't account for the fact that git sorts trees
 622     # (including our chunked trees) as if their names ended with "/",
 623     # so "fo" sorts after "fo." iff fo is a directory.  This makes
 624     # streaming impossible when we need the metadata.
 625     def result_from_tree_entry(tree_entry):
 626         gitmode, mangled_name, oid = tree_entry
 627         name, kind = git.demangle_name(mangled_name, gitmode)
 628         return name, mangled_name, kind, gitmode, oid
 629
 630     tree_ents = (result_from_tree_entry(x) for x in tree_decode(tree_data))
 631     if bupm:
 632         tree_ents = sorted(tree_ents, key=lambda x: x[0])
 633     for ent in tree_ents:
 634         yield ent
 635
 636 def tree_items(oid, tree_data, names=frozenset(), bupm=None):
 637
 638     def tree_item(ent_oid, kind, gitmode):
 639         if kind == BUP_CHUNKED:
 640             meta = Metadata.read(bupm) if bupm else default_file_mode
 641             return Chunky(oid=ent_oid, meta=meta)
 642
 643         if S_ISDIR(gitmode):
 644             # No metadata here (accessable via '.' inside ent_oid).
 645             return Item(meta=default_dir_mode, oid=ent_oid)
 646
 647         return Item(oid=ent_oid,
 648                     meta=(Metadata.read(bupm) if bupm \
 649                           else _default_mode_for_gitmode(gitmode)))
 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 = meta.atime = meta.mtime = meta.ctime = 0
1116     if S_ISLNK(m):
1117         if isinstance(item, FakeLink):
1118             target = item.target
1119         else:
1120             target = _readlink(repo, item.oid)
1121         meta.symlink_target = target
1122         meta.size = len(target)
1123     elif include_size:
1124         meta.size = _compute_item_size(repo, item)
1125     return item._replace(meta=meta)
1126
1127 def fill_in_metadata_if_dir(repo, item):
1128     """If item is a directory and item.meta is not a Metadata instance,
1129     attempt to find the metadata for the directory.  If found, return
1130     a new item augmented to include that metadata.  Otherwise, return
1131     item.  May be useful for the output of contents().
1132
1133     """
1134     if S_ISDIR(item_mode(item)) and not isinstance(item.meta, Metadata):
1135         items = tuple(contents(repo, item, (b'.',), want_meta=True))
1136         assert len(items) == 1
1137         assert items[0][0] == b'.'
1138         item = items[0][1]
1139     return item
1140
1141 def ensure_item_has_metadata(repo, item, include_size=False):
1142     """If item is a directory, attempt to find and add its metadata.  If
1143     the item still doesn't have a Metadata instance for item.meta,
1144     give it one via augment_item_meta().  May be useful for the output
1145     of contents().
1146
1147     """
1148     return augment_item_meta(repo,
1149                              fill_in_metadata_if_dir(repo, item),
1150                              include_size=include_size)