lib/bup/vfs.py

   1 """Virtual File System representing bup's repository contents.
   2
   3 The vfs.py library makes it possible to expose contents from bup's repository
   4 and abstracts internal name mangling and storage from the exposition layer.
   5 """
   6 import os, re, stat, time
   7 from bup import git, metadata
   8 from helpers import *
   9 from bup.hashsplit import GIT_MODE_TREE, GIT_MODE_FILE
  10
  11 EMPTY_SHA='\0'*20
  12
  13 _cp = None
  14 def cp():
  15     """Create a git.CatPipe object or reuse the already existing one."""
  16     global _cp
  17     if not _cp:
  18         _cp = git.CatPipe()
  19     return _cp
  20
  21 class NodeError(Exception):
  22     """VFS base exception."""
  23     pass
  24
  25 class NoSuchFile(NodeError):
  26     """Request of a file that does not exist."""
  27     pass
  28
  29 class NotDir(NodeError):
  30     """Attempt to do a directory action on a file that is not one."""
  31     pass
  32
  33 class NotFile(NodeError):
  34     """Access to a node that does not represent a file."""
  35     pass
  36
  37 class TooManySymlinks(NodeError):
  38     """Symlink dereferencing level is too deep."""
  39     pass
  40
  41
  42 def _treeget(hash):
  43     it = cp().get(hash.encode('hex'))
  44     type = it.next()
  45     assert(type == 'tree')
  46     return git.tree_decode(''.join(it))
  47
  48
  49 def _tree_decode(hash):
  50     tree = [(int(name,16),stat.S_ISDIR(mode),sha)
  51             for (mode,name,sha)
  52             in _treeget(hash)]
  53     assert(tree == list(sorted(tree)))
  54     return tree
  55
  56
  57 def _chunk_len(hash):
  58     return sum(len(b) for b in cp().join(hash.encode('hex')))
  59
  60
  61 def _last_chunk_info(hash):
  62     tree = _tree_decode(hash)
  63     assert(tree)
  64     (ofs,isdir,sha) = tree[-1]
  65     if isdir:
  66         (subofs, sublen) = _last_chunk_info(sha)
  67         return (ofs+subofs, sublen)
  68     else:
  69         return (ofs, _chunk_len(sha))
  70
  71
  72 def _total_size(hash):
  73     (lastofs, lastsize) = _last_chunk_info(hash)
  74     return lastofs + lastsize
  75
  76
  77 def _chunkiter(hash, startofs):
  78     assert(startofs >= 0)
  79     tree = _tree_decode(hash)
  80
  81     # skip elements before startofs
  82     for i in xrange(len(tree)):
  83         if i+1 >= len(tree) or tree[i+1][0] > startofs:
  84             break
  85     first = i
  86
  87     # iterate through what's left
  88     for i in xrange(first, len(tree)):
  89         (ofs,isdir,sha) = tree[i]
  90         skipmore = startofs-ofs
  91         if skipmore < 0:
  92             skipmore = 0
  93         if isdir:
  94             for b in _chunkiter(sha, skipmore):
  95                 yield b
  96         else:
  97             yield ''.join(cp().join(sha.encode('hex')))[skipmore:]
  98
  99
 100 class _ChunkReader:
 101     def __init__(self, hash, isdir, startofs):
 102         if isdir:
 103             self.it = _chunkiter(hash, startofs)
 104             self.blob = None
 105         else:
 106             self.it = None
 107             self.blob = ''.join(cp().join(hash.encode('hex')))[startofs:]
 108         self.ofs = startofs
 109
 110     def next(self, size):
 111         out = ''
 112         while len(out) < size:
 113             if self.it and not self.blob:
 114                 try:
 115                     self.blob = self.it.next()
 116                 except StopIteration:
 117                     self.it = None
 118             if self.blob:
 119                 want = size - len(out)
 120                 out += self.blob[:want]
 121                 self.blob = self.blob[want:]
 122             if not self.it:
 123                 break
 124         debug2('next(%d) returned %d\n' % (size, len(out)))
 125         self.ofs += len(out)
 126         return out
 127
 128
 129 class _FileReader(object):
 130     def __init__(self, hash, size, isdir):
 131         self.hash = hash
 132         self.ofs = 0
 133         self.size = size
 134         self.isdir = isdir
 135         self.reader = None
 136
 137     def seek(self, ofs):
 138         if ofs > self.size:
 139             self.ofs = self.size
 140         elif ofs < 0:
 141             self.ofs = 0
 142         else:
 143             self.ofs = ofs
 144
 145     def tell(self):
 146         return self.ofs
 147
 148     def read(self, count = -1):
 149         if count < 0:
 150             count = self.size - self.ofs
 151         if not self.reader or self.reader.ofs != self.ofs:
 152             self.reader = _ChunkReader(self.hash, self.isdir, self.ofs)
 153         try:
 154             buf = self.reader.next(count)
 155         except:
 156             self.reader = None
 157             raise  # our offsets will be all screwed up otherwise
 158         self.ofs += len(buf)
 159         return buf
 160
 161     def close(self):
 162         pass
 163
 164
 165 class Node:
 166     """Base class for file representation."""
 167     def __init__(self, parent, name, mode, hash):
 168         self.parent = parent
 169         self.name = name
 170         self.mode = mode
 171         self.hash = hash
 172         self.ctime = self.mtime = self.atime = 0
 173         self._subs = None
 174         self._metadata = None
 175
 176     def __repr__(self):
 177         return "<%s object at %s - name:%r hash:%s parent:%r>" \
 178             % (self.__class__, hex(id(self)),
 179                self.name, self.hash.encode('hex'),
 180                self.parent.name if self.parent else None)
 181
 182     def __cmp__(a, b):
 183         if a is b:
 184             return 0
 185         return (cmp(a and a.parent, b and b.parent) or
 186                 cmp(a and a.name, b and b.name))
 187
 188     def __iter__(self):
 189         return iter(self.subs())
 190
 191     def fullname(self, stop_at=None):
 192         """Get this file's full path."""
 193         assert(self != stop_at)  # would be the empty string; too weird
 194         if self.parent and self.parent != stop_at:
 195             return os.path.join(self.parent.fullname(stop_at=stop_at),
 196                                 self.name)
 197         else:
 198             return self.name
 199
 200     def _mksubs(self):
 201         self._subs = {}
 202
 203     def subs(self):
 204         """Get a list of nodes that are contained in this node."""
 205         if self._subs == None:
 206             self._mksubs()
 207         return sorted(self._subs.values())
 208
 209     def sub(self, name):
 210         """Get node named 'name' that is contained in this node."""
 211         if self._subs == None:
 212             self._mksubs()
 213         ret = self._subs.get(name)
 214         if not ret:
 215             raise NoSuchFile("no file %r in %r" % (name, self.name))
 216         return ret
 217
 218     def top(self):
 219         """Return the very top node of the tree."""
 220         if self.parent:
 221             return self.parent.top()
 222         else:
 223             return self
 224
 225     def fs_top(self):
 226         """Return the top node of the particular backup set.
 227
 228         If this node isn't inside a backup set, return the root level.
 229         """
 230         if self.parent and not isinstance(self.parent, CommitList):
 231             return self.parent.fs_top()
 232         else:
 233             return self
 234
 235     def _lresolve(self, parts):
 236         #debug2('_lresolve %r in %r\n' % (parts, self.name))
 237         if not parts:
 238             return self
 239         (first, rest) = (parts[0], parts[1:])
 240         if first == '.':
 241             return self._lresolve(rest)
 242         elif first == '..':
 243             if not self.parent:
 244                 raise NoSuchFile("no parent dir for %r" % self.name)
 245             return self.parent._lresolve(rest)
 246         elif rest:
 247             return self.sub(first)._lresolve(rest)
 248         else:
 249             return self.sub(first)
 250
 251     def lresolve(self, path, stay_inside_fs=False):
 252         """Walk into a given sub-path of this node.
 253
 254         If the last element is a symlink, leave it as a symlink, don't resolve
 255         it.  (like lstat())
 256         """
 257         start = self
 258         if not path:
 259             return start
 260         if path.startswith('/'):
 261             if stay_inside_fs:
 262                 start = self.fs_top()
 263             else:
 264                 start = self.top()
 265             path = path[1:]
 266         parts = re.split(r'/+', path or '.')
 267         if not parts[-1]:
 268             parts[-1] = '.'
 269         #debug2('parts: %r %r\n' % (path, parts))
 270         return start._lresolve(parts)
 271
 272     def resolve(self, path = ''):
 273         """Like lresolve(), and dereference it if it was a symlink."""
 274         return self.lresolve(path).lresolve('.')
 275
 276     def try_resolve(self, path = ''):
 277         """Like resolve(), but don't worry if a symlink uses an invalid path.
 278
 279         Returns an error if any intermediate nodes were invalid.
 280         """
 281         n = self.lresolve(path)
 282         try:
 283             n = n.lresolve('.')
 284         except NoSuchFile:
 285             pass
 286         return n
 287
 288     def nlinks(self):
 289         """Get the number of hard links to the current node."""
 290         if self._subs == None:
 291             self._mksubs()
 292         return 1
 293
 294     def size(self):
 295         """Get the size of the current node."""
 296         return 0
 297
 298     def open(self):
 299         """Open the current node. It is an error to open a non-file node."""
 300         raise NotFile('%s is not a regular file' % self.name)
 301
 302     def _populate_metadata(self):
 303         # Only Dirs contain .bupm files, so by default, do nothing.
 304         pass
 305
 306     def metadata(self):
 307         """Return this Node's Metadata() object, if any."""
 308         if self.parent:
 309             self.parent._populate_metadata()
 310         return self._metadata
 311
 312
 313 class File(Node):
 314     """A normal file from bup's repository."""
 315     def __init__(self, parent, name, mode, hash, bupmode):
 316         Node.__init__(self, parent, name, mode, hash)
 317         self.bupmode = bupmode
 318         self._cached_size = None
 319         self._filereader = None
 320
 321     def open(self):
 322         """Open the file."""
 323         # You'd think FUSE might call this only once each time a file is
 324         # opened, but no; it's really more of a refcount, and it's called
 325         # once per read().  Thus, it's important to cache the filereader
 326         # object here so we're not constantly re-seeking.
 327         if not self._filereader:
 328             self._filereader = _FileReader(self.hash, self.size(),
 329                                            self.bupmode == git.BUP_CHUNKED)
 330         self._filereader.seek(0)
 331         return self._filereader
 332
 333     def size(self):
 334         """Get this file's size."""
 335         if self._cached_size == None:
 336             debug1('<<<<File.size() is calculating (for %r)...\n' % self.name)
 337             if self.bupmode == git.BUP_CHUNKED:
 338                 self._cached_size = _total_size(self.hash)
 339             else:
 340                 self._cached_size = _chunk_len(self.hash)
 341             debug1('<<<<File.size() done.\n')
 342         return self._cached_size
 343
 344
 345 _symrefs = 0
 346 class Symlink(File):
 347     """A symbolic link from bup's repository."""
 348     def __init__(self, parent, name, hash, bupmode):
 349         File.__init__(self, parent, name, 0120000, hash, bupmode)
 350
 351     def size(self):
 352         """Get the file size of the file at which this link points."""
 353         return len(self.readlink())
 354
 355     def readlink(self):
 356         """Get the path that this link points at."""
 357         return ''.join(cp().join(self.hash.encode('hex')))
 358
 359     def dereference(self):
 360         """Get the node that this link points at.
 361
 362         If the path is invalid, raise a NoSuchFile exception. If the level of
 363         indirection of symlinks is 100 levels deep, raise a TooManySymlinks
 364         exception.
 365         """
 366         global _symrefs
 367         if _symrefs > 100:
 368             raise TooManySymlinks('too many levels of symlinks: %r'
 369                                   % self.fullname())
 370         _symrefs += 1
 371         try:
 372             try:
 373                 return self.parent.lresolve(self.readlink(),
 374                                             stay_inside_fs=True)
 375             except NoSuchFile:
 376                 raise NoSuchFile("%s: broken symlink to %r"
 377                                  % (self.fullname(), self.readlink()))
 378         finally:
 379             _symrefs -= 1
 380
 381     def _lresolve(self, parts):
 382         return self.dereference()._lresolve(parts)
 383
 384
 385 class FakeSymlink(Symlink):
 386     """A symlink that is not stored in the bup repository."""
 387     def __init__(self, parent, name, toname):
 388         Symlink.__init__(self, parent, name, EMPTY_SHA, git.BUP_NORMAL)
 389         self.toname = toname
 390
 391     def readlink(self):
 392         """Get the path that this link points at."""
 393         return self.toname
 394
 395
 396 class Dir(Node):
 397     """A directory stored inside of bup's repository."""
 398
 399     def __init__(self, *args, **kwargs):
 400         Node.__init__(self, *args, **kwargs)
 401         self._bupm = None
 402
 403     def _populate_metadata(self):
 404         if not self._subs:
 405             self._mksubs()
 406         if not self._bupm:
 407             return
 408         meta_stream = self._bupm.open()
 409         self._metadata = metadata.Metadata.read(meta_stream)
 410         for sub in self:
 411             if not stat.S_ISDIR(sub.mode):
 412                 sub._metadata = metadata.Metadata.read(meta_stream)
 413
 414     def _mksubs(self):
 415         self._subs = {}
 416         it = cp().get(self.hash.encode('hex'))
 417         type = it.next()
 418         if type == 'commit':
 419             del it
 420             it = cp().get(self.hash.encode('hex') + ':')
 421             type = it.next()
 422         assert(type == 'tree')
 423         for (mode,mangled_name,sha) in git.tree_decode(''.join(it)):
 424             if mangled_name == '.bupm':
 425                 self._bupm = File(self, mangled_name, mode, sha, git.BUP_NORMAL)
 426                 continue
 427             name = mangled_name
 428             (name,bupmode) = git.demangle_name(mangled_name)
 429             if bupmode == git.BUP_CHUNKED:
 430                 mode = GIT_MODE_FILE
 431             if stat.S_ISDIR(mode):
 432                 self._subs[name] = Dir(self, name, mode, sha)
 433             elif stat.S_ISLNK(mode):
 434                 self._subs[name] = Symlink(self, name, sha, bupmode)
 435             else:
 436                 self._subs[name] = File(self, name, mode, sha, bupmode)
 437
 438     def metadata(self):
 439         """Return this Dir's Metadata() object, if any."""
 440         self._populate_metadata()
 441         return self._metadata
 442
 443     def metadata_file(self):
 444         """Return this Dir's .bupm File, if any."""
 445         if not self._subs:
 446             self._mksubs()
 447         return self._bupm
 448
 449
 450 class CommitDir(Node):
 451     """A directory that contains all commits that are reachable by a ref.
 452
 453     Contains a set of subdirectories named after the commits' first byte in
 454     hexadecimal. Each of those directories contain all commits with hashes that
 455     start the same as the directory name. The name used for those
 456     subdirectories is the hash of the commit without the first byte. This
 457     separation helps us avoid having too much directories on the same level as
 458     the number of commits grows big.
 459     """
 460     def __init__(self, parent, name):
 461         Node.__init__(self, parent, name, GIT_MODE_TREE, EMPTY_SHA)
 462
 463     def _mksubs(self):
 464         self._subs = {}
 465         refs = git.list_refs()
 466         for ref in refs:
 467             #debug2('ref name: %s\n' % ref[0])
 468             revs = git.rev_list(ref[1].encode('hex'))
 469             for (date, commit) in revs:
 470                 #debug2('commit: %s  date: %s\n' % (commit.encode('hex'), date))
 471                 commithex = commit.encode('hex')
 472                 containername = commithex[:2]
 473                 dirname = commithex[2:]
 474                 n1 = self._subs.get(containername)
 475                 if not n1:
 476                     n1 = CommitList(self, containername)
 477                     self._subs[containername] = n1
 478
 479                 if n1.commits.get(dirname):
 480                     # Stop work for this ref, the rest should already be present
 481                     break
 482
 483                 n1.commits[dirname] = (commit, date)
 484
 485
 486 class CommitList(Node):
 487     """A list of commits with hashes that start with the current node's name."""
 488     def __init__(self, parent, name):
 489         Node.__init__(self, parent, name, GIT_MODE_TREE, EMPTY_SHA)
 490         self.commits = {}
 491
 492     def _mksubs(self):
 493         self._subs = {}
 494         for (name, (hash, date)) in self.commits.items():
 495             n1 = Dir(self, name, GIT_MODE_TREE, hash)
 496             n1.ctime = n1.mtime = date
 497             self._subs[name] = n1
 498
 499
 500 class TagDir(Node):
 501     """A directory that contains all tags in the repository."""
 502     def __init__(self, parent, name):
 503         Node.__init__(self, parent, name, GIT_MODE_TREE, EMPTY_SHA)
 504
 505     def _mksubs(self):
 506         self._subs = {}
 507         for (name, sha) in git.list_refs():
 508             if name.startswith('refs/tags/'):
 509                 name = name[10:]
 510                 date = git.rev_get_date(sha.encode('hex'))
 511                 commithex = sha.encode('hex')
 512                 target = '../.commit/%s/%s' % (commithex[:2], commithex[2:])
 513                 tag1 = FakeSymlink(self, name, target)
 514                 tag1.ctime = tag1.mtime = date
 515                 self._subs[name] = tag1
 516
 517
 518 class BranchList(Node):
 519     """A list of links to commits reachable by a branch in bup's repository.
 520
 521     Represents each commit as a symlink that points to the commit directory in
 522     /.commit/??/ . The symlink is named after the commit date.
 523     """
 524     def __init__(self, parent, name, hash):
 525         Node.__init__(self, parent, name, GIT_MODE_TREE, hash)
 526
 527     def _mksubs(self):
 528         self._subs = {}
 529
 530         tags = git.tags()
 531
 532         revs = list(git.rev_list(self.hash.encode('hex')))
 533         latest = revs[0]
 534         for (date, commit) in revs:
 535             l = time.localtime(date)
 536             ls = time.strftime('%Y-%m-%d-%H%M%S', l)
 537             commithex = commit.encode('hex')
 538             target = '../.commit/%s/%s' % (commithex[:2], commithex[2:])
 539             n1 = FakeSymlink(self, ls, target)
 540             n1.ctime = n1.mtime = date
 541             self._subs[ls] = n1
 542
 543             for tag in tags.get(commit, []):
 544                 t1 = FakeSymlink(self, tag, target)
 545                 t1.ctime = t1.mtime = date
 546                 self._subs[tag] = t1
 547
 548         (date, commit) = latest
 549         commithex = commit.encode('hex')
 550         target = '../.commit/%s/%s' % (commithex[:2], commithex[2:])
 551         n1 = FakeSymlink(self, 'latest', target)
 552         n1.ctime = n1.mtime = date
 553         self._subs['latest'] = n1
 554
 555
 556 class RefList(Node):
 557     """A list of branches in bup's repository.
 558
 559     The sub-nodes of the ref list are a series of CommitList for each commit
 560     hash pointed to by a branch.
 561
 562     Also, a special sub-node named '.commit' contains all commit directories
 563     that are reachable via a ref (e.g. a branch).  See CommitDir for details.
 564     """
 565     def __init__(self, parent):
 566         Node.__init__(self, parent, '/', GIT_MODE_TREE, EMPTY_SHA)
 567
 568     def _mksubs(self):
 569         self._subs = {}
 570
 571         commit_dir = CommitDir(self, '.commit')
 572         self._subs['.commit'] = commit_dir
 573
 574         tag_dir = TagDir(self, '.tag')
 575         self._subs['.tag'] = tag_dir
 576
 577         for (name,sha) in git.list_refs():
 578             if name.startswith('refs/heads/'):
 579                 name = name[11:]
 580                 date = git.rev_get_date(sha.encode('hex'))
 581                 n1 = BranchList(self, name, sha)
 582                 n1.ctime = n1.mtime = date
 583                 self._subs[name] = n1