lib/bup/vfs.py

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