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     # but in unmangled name order. They _do_ account for the fact
 622     # that git sorts trees (including chunked trees) as if their
 623     # names ended with "/" (so "fo" sorts after "fo." iff fo is a
 624     # directory), but we apply this on the unmangled names in save
 625     # rather than on the mangled names.
 626     # This makes streaming impossible when we need the metadata.
 627     def result_from_tree_entry(tree_entry):
 628         gitmode, mangled_name, oid = tree_entry
 629         name, kind = git.demangle_name(mangled_name, gitmode)
 630         return name, mangled_name, kind, gitmode, oid
 631
 632     tree_ents = (result_from_tree_entry(x) for x in tree_decode(tree_data))
 633     if bupm:
 634         tree_ents = sorted(tree_ents, key=lambda x: x[0])
 635     for ent in tree_ents:
 636         yield ent
 637
 638 def tree_items(oid, tree_data, names=frozenset(), bupm=None):
 639
 640     def tree_item(ent_oid, kind, gitmode):
 641         if kind == BUP_CHUNKED:
 642             meta = Metadata.read(bupm) if bupm else default_file_mode
 643             return Chunky(oid=ent_oid, meta=meta)
 644
 645         if S_ISDIR(gitmode):
 646             # No metadata here (accessable via '.' inside ent_oid).
 647             return Item(meta=default_dir_mode, oid=ent_oid)
 648
 649         meta = Metadata.read(bupm) if bupm else None
 650         # handle the case of metadata being empty/missing in bupm
 651         # (or there not being bupm at all)
 652         if meta is None:
 653             meta = _default_mode_for_gitmode(gitmode)
 654         return Item(oid=ent_oid, meta=meta)
 655
 656     assert len(oid) == 20
 657     if not names:
 658         dot_meta = _read_dir_meta(bupm) if bupm else default_dir_mode
 659         yield b'.', Item(oid=oid, meta=dot_meta)
 660         tree_entries = ordered_tree_entries(tree_data, bupm)
 661         for name, mangled_name, kind, gitmode, ent_oid in tree_entries:
 662             if mangled_name == b'.bupm':
 663                 continue
 664             assert name != b'.'
 665             yield name, tree_item(ent_oid, kind, gitmode)
 666         return
 667
 668     # Assumes the tree is properly formed, i.e. there are no
 669     # duplicates, and entries will be in git tree order.
 670     if type(names) not in (frozenset, set):
 671         names = frozenset(names)
 672     remaining = len(names)
 673
 674     # Account for the bupm sort order issue (cf. ordered_tree_entries above)
 675     last_name = max(names) if bupm else max(names) + b'/'
 676
 677     if b'.' in names:
 678         dot_meta = _read_dir_meta(bupm) if bupm else default_dir_mode
 679         yield b'.', Item(oid=oid, meta=dot_meta)
 680         if remaining == 1:
 681             return
 682         remaining -= 1
 683
 684     tree_entries = ordered_tree_entries(tree_data, bupm)
 685     for name, mangled_name, kind, gitmode, ent_oid in tree_entries:
 686         if mangled_name == b'.bupm':
 687             continue
 688         assert name != b'.'
 689         if name not in names:
 690             if name > last_name:
 691                 break  # given bupm sort order, we're finished
 692             if (kind == BUP_CHUNKED or not S_ISDIR(gitmode)) and bupm:
 693                 Metadata.read(bupm)
 694             continue
 695         yield name, tree_item(ent_oid, kind, gitmode)
 696         if remaining == 1:
 697             break
 698         remaining -= 1
 699
 700 def tree_items_with_meta(repo, oid, tree_data, names):
 701     # For now, the .bupm order doesn't quite match git's, and we don't
 702     # load the tree data incrementally anyway, so we just work in RAM
 703     # via tree_data.
 704     assert len(oid) == 20
 705     bupm = None
 706     for _, mangled_name, sub_oid in tree_decode(tree_data):
 707         if mangled_name == b'.bupm':
 708             bupm = _FileReader(repo, sub_oid)
 709             break
 710         if mangled_name > b'.bupm':
 711             break
 712     for item in tree_items(oid, tree_data, names, bupm):
 713         yield item
 714
 715 _save_name_rx = re.compile(br'^\d\d\d\d-\d\d-\d\d-\d{6}(-\d+)?$')
 716
 717 def _reverse_suffix_duplicates(strs):
 718     """Yields the elements of strs, with any runs of duplicate values
 719     suffixed with -N suffixes, where the zero padded integer N
 720     decreases to 0 by 1 (e.g. 10, 09, ..., 00).
 721
 722     """
 723     for name, duplicates in groupby(strs):
 724         ndup = len(tuple(duplicates))
 725         if ndup == 1:
 726             yield name
 727         else:
 728             ndig = len(str(ndup - 1))
 729             fmt = b'%s-' + b'%0' + (b'%d' % ndig) + b'd'
 730             for i in range(ndup - 1, -1, -1):
 731                 yield fmt % (name, i)
 732
 733 def parse_rev(f):
 734     items = f.readline().split(None)
 735     assert len(items) == 2
 736     tree, auth_sec = items
 737     return unhexlify(tree), int(auth_sec)
 738
 739 def _name_for_rev(rev):
 740     commit_oidx, (tree_oid, utc) = rev
 741     return strftime('%Y-%m-%d-%H%M%S', localtime(utc)).encode('ascii')
 742
 743 def _item_for_rev(rev):
 744     commit_oidx, (tree_oid, utc) = rev
 745     coid = unhexlify(commit_oidx)
 746     item = cache_get_commit_item(coid, need_meta=False)
 747     if item:
 748         return item
 749     item = Commit(meta=default_dir_mode, oid=tree_oid, coid=coid)
 750     commit_key = b'itm:' + coid
 751     cache_notice(commit_key, item)
 752     return item
 753
 754 def cache_commit(repo, oid):
 755     """Build, cache, and return a "name -> commit_item" dict of the entire
 756     commit rev-list.
 757
 758     """
 759     # For now, always cache with full metadata
 760     entries = {}
 761     entries[b'.'] = _revlist_item_from_oid(repo, oid, True)
 762     revs = repo.rev_list((hexlify(oid),), format=b'%T %at',
 763                          parse=parse_rev)
 764     rev_items, rev_names = tee(revs)
 765     revs = None  # Don't disturb the tees
 766     rev_names = _reverse_suffix_duplicates(_name_for_rev(x) for x in rev_names)
 767     rev_items = (_item_for_rev(x) for x in rev_items)
 768     tip = None
 769     for item in rev_items:
 770         name = next(rev_names)
 771         tip = tip or (name, item)
 772         entries[name] = item
 773     entries[b'latest'] = FakeLink(meta=default_symlink_mode, target=tip[0])
 774     revlist_key = b'rvl:' + tip[1].coid
 775     cache_notice(revlist_key, entries)
 776     return entries
 777
 778 def revlist_items(repo, oid, names):
 779     assert len(oid) == 20
 780
 781     # Special case '.' instead of caching the whole history since it's
 782     # the only way to get the metadata for the commit.
 783     if names and all(x == b'.' for x in names):
 784         yield b'.', _revlist_item_from_oid(repo, oid, True)
 785         return
 786
 787     # For now, don't worry about the possibility of the contents being
 788     # "too big" for the cache.
 789     revlist_key = b'rvl:' + oid
 790     entries = cache_get(revlist_key)
 791     if not entries:
 792         entries = cache_commit(repo, oid)
 793
 794     if not names:
 795         for name in sorted(entries.keys()):
 796             yield name, entries[name]
 797         return
 798
 799     names = frozenset(name for name in names
 800                       if _save_name_rx.match(name) or name in (b'.', b'latest'))
 801
 802     if b'.' in names:
 803         yield b'.', entries[b'.']
 804     for name in (n for n in names if n != b'.'):
 805         commit = entries.get(name)
 806         if commit:
 807             yield name, commit
 808
 809 def tags_items(repo, names):
 810     global _tags
 811
 812     def tag_item(oid):
 813         assert len(oid) == 20
 814         oidx = hexlify(oid)
 815         it = repo.cat(oidx)
 816         _, typ, size = next(it)
 817         if typ == b'commit':
 818             return cache_get_commit_item(oid, need_meta=False) \
 819                 or _commit_item_from_data(oid, b''.join(it))
 820         for _ in it: pass
 821         if typ == b'blob':
 822             return Item(meta=default_file_mode, oid=oid)
 823         elif typ == b'tree':
 824             return Item(meta=default_dir_mode, oid=oid)
 825         raise Exception('unexpected tag type ' + typ.decode('ascii')
 826                         + ' for tag ' + path_msg(name))
 827
 828     if not names:
 829         yield b'.', _tags
 830         # We have to pull these all into ram because tag_item calls cat()
 831         for name, oid in tuple(repo.refs(names, limit_to_tags=True)):
 832             assert(name.startswith(b'refs/tags/'))
 833             name = name[10:]
 834             yield name, tag_item(oid)
 835         return
 836
 837     # Assumes no duplicate refs
 838     if type(names) not in (frozenset, set):
 839         names = frozenset(names)
 840     remaining = len(names)
 841     last_name = max(names)
 842     if b'.' in names:
 843         yield b'.', _tags
 844         if remaining == 1:
 845             return
 846         remaining -= 1
 847
 848     for name, oid in repo.refs(names, limit_to_tags=True):
 849         assert(name.startswith(b'refs/tags/'))
 850         name = name[10:]
 851         if name > last_name:
 852             return
 853         if name not in names:
 854             continue
 855         yield name, tag_item(oid)
 856         if remaining == 1:
 857             return
 858         remaining -= 1
 859
 860 def contents(repo, item, names=None, want_meta=True):
 861     """Yields information about the items contained in item.  Yields
 862     (name, item) for each name in names, if the name exists, in an
 863     unspecified order.  If there are no names, then yields (name,
 864     item) for all items, including, a first item named '.'
 865     representing the container itself.
 866
 867     The meta value for any directories other than '.' will be a
 868     default directory mode, not a Metadata object.  This is because
 869     the actual metadata for a directory is stored inside the directory
 870     (see fill_in_metadata_if_dir() or ensure_item_has_metadata()).
 871
 872     Note that want_meta is advisory.  For any given item, item.meta
 873     might be a Metadata instance or a mode, and if the former,
 874     meta.size might be None.  Missing sizes can be computed via via
 875     item_size() or augment_item_meta(..., include_size=True).
 876
 877     Do not modify any item.meta Metadata instances directly.  If
 878     needed, make a copy via item.meta.copy() and modify that instead.
 879
 880     """
 881     # Q: are we comfortable promising '.' first when no names?
 882     global _root, _tags
 883     assert repo
 884     assert S_ISDIR(item_mode(item))
 885     item_t = type(item)
 886     if item_t in real_tree_types:
 887         it = repo.cat(hexlify(item.oid))
 888         _, obj_t, size = next(it)
 889         data = b''.join(it)
 890         if obj_t != b'tree':
 891             for _ in it: pass
 892             # Note: it shouldn't be possible to see an Item with type
 893             # 'commit' since a 'commit' should always produce a Commit.
 894             raise Exception('unexpected git ' + obj_t.decode('ascii'))
 895         if want_meta:
 896             item_gen = tree_items_with_meta(repo, item.oid, data, names)
 897         else:
 898             item_gen = tree_items(item.oid, data, names)
 899     elif item_t == RevList:
 900         item_gen = revlist_items(repo, item.oid, names)
 901     elif item_t == Root:
 902         item_gen = root_items(repo, names, want_meta)
 903     elif item_t == Tags:
 904         item_gen = tags_items(repo, names)
 905     else:
 906         raise Exception('unexpected VFS item ' + str(item))
 907     for x in item_gen:
 908         yield x
 909
 910 def _resolve_path(repo, path, parent=None, want_meta=True, follow=True):
 911     cache_key = b'res:%d%d%d:%s\0%s' \
 912                 % (bool(want_meta), bool(follow), repo.id(),
 913                    (b'/'.join(x[0] for x in parent) if parent else b''),
 914                    path)
 915     resolution = cache_get(cache_key)
 916     if resolution:
 917         return resolution
 918
 919     def notice_resolution(r):
 920         cache_notice(cache_key, r)
 921         return r
 922
 923     def raise_dir_required_but_not_dir(path, parent, past):
 924         raise IOError(ENOTDIR,
 925                       "path %s%s resolves to non-directory %r"
 926                       % (path,
 927                          ' (relative to %r)' % parent if parent else '',
 928                          past),
 929                       terminus=past)
 930     global _root
 931     assert repo
 932     assert len(path)
 933     if parent:
 934         for x in parent:
 935             assert len(x) == 2
 936             assert type(x[0]) in (bytes, str)
 937             assert type(x[1]) in item_types
 938         assert parent[0][1] == _root
 939         if not S_ISDIR(item_mode(parent[-1][1])):
 940             raise IOError(ENOTDIR,
 941                           'path resolution parent %r is not a directory'
 942                           % (parent,))
 943     is_absolute, must_be_dir, future = _decompose_path(path)
 944     if must_be_dir:
 945         follow = True
 946     if not future:  # path was effectively '.' or '/'
 947         if is_absolute:
 948             return notice_resolution(((b'', _root),))
 949         if parent:
 950             return notice_resolution(tuple(parent))
 951         return notice_resolution(((b'', _root),))
 952     if is_absolute:
 953         past = [(b'', _root)]
 954     else:
 955         past = list(parent) if parent else [(b'', _root)]
 956     hops = 0
 957     while True:
 958         if not future:
 959             if must_be_dir and not S_ISDIR(item_mode(past[-1][1])):
 960                 raise_dir_required_but_not_dir(path, parent, past)
 961             return notice_resolution(tuple(past))
 962         segment = future.pop()
 963         if segment == b'..':
 964             assert len(past) > 0
 965             if len(past) > 1:  # .. from / is /
 966                 assert S_ISDIR(item_mode(past[-1][1]))
 967                 past.pop()
 968         else:
 969             parent_name, parent_item = past[-1]
 970             wanted = (segment,) if not want_meta else (b'.', segment)
 971             items = tuple(contents(repo, parent_item, names=wanted,
 972                                    want_meta=want_meta))
 973             if not want_meta:
 974                 item = items[0][1] if items else None
 975             else:  # First item will be '.' and have the metadata
 976                 item = items[1][1] if len(items) == 2 else None
 977                 dot, dot_item = items[0]
 978                 assert dot == b'.'
 979                 past[-1] = parent_name, parent_item
 980             if not item:
 981                 past.append((segment, None),)
 982                 return notice_resolution(tuple(past))
 983             mode = item_mode(item)
 984             if not S_ISLNK(mode):
 985                 if not S_ISDIR(mode):
 986                     past.append((segment, item),)
 987                     if future:
 988                         raise IOError(ENOTDIR,
 989                                       'path %r%s ends internally in non-directory here: %r'
 990                                       % (path,
 991                                          ' (relative to %r)' % parent if parent else '',
 992                                          past),
 993                                       terminus=past)
 994                     if must_be_dir:
 995                         raise_dir_required_but_not_dir(path, parent, past)
 996                     return notice_resolution(tuple(past))
 997                 # It's treeish
 998                 if want_meta and type(item) in real_tree_types:
 999                     dir_meta = _find_treeish_oid_metadata(repo, item.oid)
1000                     if dir_meta:
1001                         item = item._replace(meta=dir_meta)
1002                 past.append((segment, item))
1003             else:  # symlink
1004                 if not future and not follow:
1005                     past.append((segment, item),)
1006                     continue
1007                 if hops > 100:
1008                     raise IOError(ELOOP,
1009                                   'too many symlinks encountered while resolving %r%s'
1010                                   % (path, ' relative to %r' % parent if parent else ''),
1011                                   terminus=tuple(past + [(segment, item)]))
1012                 target = readlink(repo, item)
1013                 is_absolute, _, target_future = _decompose_path(target)
1014                 if is_absolute:
1015                     if not target_future:  # path was effectively '/'
1016                         return notice_resolution(((b'', _root),))
1017                     past = [(b'', _root)]
1018                     future = target_future
1019                 else:
1020                     future.extend(target_future)
1021                 hops += 1
1022
1023 def resolve(repo, path, parent=None, want_meta=True, follow=True):
1024     """Follow the path in the virtual filesystem and return a tuple
1025     representing the location, if any, denoted by the path.  Each
1026     element in the result tuple will be (name, info), where info will
1027     be a VFS item that can be passed to functions like item_mode().
1028
1029     If follow is false, and if the final path element is a symbolic
1030     link, don't follow it, just return it in the result.
1031
1032     If a path segment that does not exist is encountered during
1033     resolution, the result will represent the location of the missing
1034     item, and that item in the result will be None.
1035
1036     Any attempt to traverse a non-directory will raise a VFS ENOTDIR
1037     IOError exception.
1038
1039     Any symlinks along the path, including at the end, will be
1040     resolved.  A VFS IOError with the errno attribute set to ELOOP
1041     will be raised if too many symlinks are traversed while following
1042     the path.  That exception is effectively like a normal
1043     ELOOP IOError exception, but will include a terminus element
1044     describing the location of the failure, which will be a tuple of
1045     (name, info) elements.
1046
1047     The parent, if specified, must be a sequence of (name, item)
1048     tuples, and will provide the starting point for the resolution of
1049     the path.  If no parent is specified, resolution will start at
1050     '/'.
1051
1052     The result may include elements of parent directly, so they must
1053     not be modified later.  If this is a concern, pass in "name,
1054     copy_item(item) for name, item in parent" instead.
1055
1056     When want_meta is true, detailed metadata will be included in each
1057     result item if it's avaiable, otherwise item.meta will be an
1058     integer mode.  The metadata size may or may not be provided, but
1059     can be computed by item_size() or augment_item_meta(...,
1060     include_size=True).  Setting want_meta=False is rarely desirable
1061     since it can limit the VFS to just the metadata git itself can
1062     represent, and so, as an example, fifos and sockets will appear to
1063     be regular files (e.g. S_ISREG(item_mode(item)) will be true) .
1064     But the option is provided because it may be more efficient when
1065     only the path names or the more limited metadata is sufficient.
1066
1067     Do not modify any item.meta Metadata instances directly.  If
1068     needed, make a copy via item.meta.copy() and modify that instead.
1069
1070     """
1071     if repo.is_remote():
1072         # Redirect to the more efficient remote version
1073         return repo.resolve(path, parent=parent, want_meta=want_meta,
1074                             follow=follow)
1075     result = _resolve_path(repo, path, parent=parent, want_meta=want_meta,
1076                            follow=follow)
1077     _, leaf_item = result[-1]
1078     if leaf_item and follow:
1079         assert not S_ISLNK(item_mode(leaf_item))
1080     return result
1081
1082 def try_resolve(repo, path, parent=None, want_meta=True):
1083     """If path does not refer to a symlink, does not exist, or refers to a
1084     valid symlink, behave exactly like resolve(..., follow=True).  If
1085     path refers to an invalid symlink, behave like resolve(...,
1086     follow=False).
1087
1088     """
1089     res = resolve(repo, path, parent=parent, want_meta=want_meta, follow=False)
1090     leaf_name, leaf_item = res[-1]
1091     if not leaf_item:
1092         return res
1093     if not S_ISLNK(item_mode(leaf_item)):
1094         return res
1095     follow = resolve(repo, leaf_name, parent=res[:-1], want_meta=want_meta)
1096     follow_name, follow_item = follow[-1]
1097     if follow_item:
1098         return follow
1099     return res
1100
1101 def augment_item_meta(repo, item, include_size=False):
1102     """Ensure item has a Metadata instance for item.meta.  If item.meta is
1103     currently a mode, replace it with a compatible "fake" Metadata
1104     instance.  If include_size is true, ensure item.meta.size is
1105     correct, computing it if needed.  If item.meta is a Metadata
1106     instance, this call may modify it in place or replace it.
1107
1108     """
1109     # If we actually had parallelism, we'd need locking...
1110     assert repo
1111     m = item.meta
1112     if isinstance(m, Metadata):
1113         if include_size and m.size is None:
1114             m.size = _compute_item_size(repo, item)
1115             return item._replace(meta=m)
1116         return item
1117     # m is mode
1118     meta = Metadata()
1119     meta.mode = m
1120     meta.uid = meta.gid = meta.atime = meta.mtime = meta.ctime = 0
1121     if S_ISLNK(m):
1122         if isinstance(item, FakeLink):
1123             target = item.target
1124         else:
1125             target = _readlink(repo, item.oid)
1126         meta.symlink_target = target
1127         meta.size = len(target)
1128     elif include_size:
1129         meta.size = _compute_item_size(repo, item)
1130     return item._replace(meta=meta)
1131
1132 def fill_in_metadata_if_dir(repo, item):
1133     """If item is a directory and item.meta is not a Metadata instance,
1134     attempt to find the metadata for the directory.  If found, return
1135     a new item augmented to include that metadata.  Otherwise, return
1136     item.  May be useful for the output of contents().
1137
1138     """
1139     if S_ISDIR(item_mode(item)) and not isinstance(item.meta, Metadata):
1140         items = tuple(contents(repo, item, (b'.',), want_meta=True))
1141         assert len(items) == 1
1142         assert items[0][0] == b'.'
1143         item = items[0][1]
1144     return item
1145
1146 def ensure_item_has_metadata(repo, item, include_size=False):
1147     """If item is a directory, attempt to find and add its metadata.  If
1148     the item still doesn't have a Metadata instance for item.meta,
1149     give it one via augment_item_meta().  May be useful for the output
1150     of contents().
1151
1152     """
1153     return augment_item_meta(repo,
1154                              fill_in_metadata_if_dir(repo, item),
1155                              include_size=include_size)