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
   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
 175     def __repr__(self):
 176         return "<bup.vfs.Node object at X - name:%r hash:%s parent:%r>" \
 177             % (self.name, self.hash.encode('hex'),
 178                self.parent.name if self.parent.name else None)
 179
 180     def __cmp__(a, b):
 181         if a is b:
 182             return 0
 183         return (cmp(a and a.parent, b and b.parent) or
 184                 cmp(a and a.name, b and b.name))
 185
 186     def __iter__(self):
 187         return iter(self.subs())
 188
 189     def fullname(self, stop_at=None):
 190         """Get this file's full path."""
 191         assert(self != stop_at)  # would be the empty string; too weird
 192         if self.parent and self.parent != stop_at:
 193             return os.path.join(self.parent.fullname(stop_at=stop_at),
 194                                 self.name)
 195         else:
 196             return self.name
 197
 198     def _mksubs(self):
 199         self._subs = {}
 200
 201     def subs(self):
 202         """Get a list of nodes that are contained in this node."""
 203         if self._subs == None:
 204             self._mksubs()
 205         return sorted(self._subs.values())
 206
 207     def sub(self, name):
 208         """Get node named 'name' that is contained in this node."""
 209         if self._subs == None:
 210             self._mksubs()
 211         ret = self._subs.get(name)
 212         if not ret:
 213             raise NoSuchFile("no file %r in %r" % (name, self.name))
 214         return ret
 215
 216     def top(self):
 217         """Return the very top node of the tree."""
 218         if self.parent:
 219             return self.parent.top()
 220         else:
 221             return self
 222
 223     def fs_top(self):
 224         """Return the top node of the particular backup set.
 225
 226         If this node isn't inside a backup set, return the root level.
 227         """
 228         if self.parent and not isinstance(self.parent, CommitList):
 229             return self.parent.fs_top()
 230         else:
 231             return self
 232
 233     def _lresolve(self, parts):
 234         #debug2('_lresolve %r in %r\n' % (parts, self.name))
 235         if not parts:
 236             return self
 237         (first, rest) = (parts[0], parts[1:])
 238         if first == '.':
 239             return self._lresolve(rest)
 240         elif first == '..':
 241             if not self.parent:
 242                 raise NoSuchFile("no parent dir for %r" % self.name)
 243             return self.parent._lresolve(rest)
 244         elif rest:
 245             return self.sub(first)._lresolve(rest)
 246         else:
 247             return self.sub(first)
 248
 249     def lresolve(self, path, stay_inside_fs=False):
 250         """Walk into a given sub-path of this node.
 251
 252         If the last element is a symlink, leave it as a symlink, don't resolve
 253         it.  (like lstat())
 254         """
 255         start = self
 256         if not path:
 257             return start
 258         if path.startswith('/'):
 259             if stay_inside_fs:
 260                 start = self.fs_top()
 261             else:
 262                 start = self.top()
 263             path = path[1:]
 264         parts = re.split(r'/+', path or '.')
 265         if not parts[-1]:
 266             parts[-1] = '.'
 267         #debug2('parts: %r %r\n' % (path, parts))
 268         return start._lresolve(parts)
 269
 270     def resolve(self, path = ''):
 271         """Like lresolve(), and dereference it if it was a symlink."""
 272         return self.lresolve(path).lresolve('.')
 273
 274     def try_resolve(self, path = ''):
 275         """Like resolve(), but don't worry if a symlink uses an invalid path.
 276
 277         Returns an error if any intermediate nodes were invalid.
 278         """
 279         n = self.lresolve(path)
 280         try:
 281             n = n.lresolve('.')
 282         except NoSuchFile:
 283             pass
 284         return n
 285
 286     def nlinks(self):
 287         """Get the number of hard links to the current node."""
 288         if self._subs == None:
 289             self._mksubs()
 290         return 1
 291
 292     def size(self):
 293         """Get the size of the current node."""
 294         return 0
 295
 296     def open(self):
 297         """Open the current node. It is an error to open a non-file node."""
 298         raise NotFile('%s is not a regular file' % self.name)
 299
 300
 301 class File(Node):
 302     """A normal file from bup's repository."""
 303     def __init__(self, parent, name, mode, hash, bupmode):
 304         Node.__init__(self, parent, name, mode, hash)
 305         self.bupmode = bupmode
 306         self._cached_size = None
 307         self._filereader = None
 308
 309     def open(self):
 310         """Open the file."""
 311         # You'd think FUSE might call this only once each time a file is
 312         # opened, but no; it's really more of a refcount, and it's called
 313         # once per read().  Thus, it's important to cache the filereader
 314         # object here so we're not constantly re-seeking.
 315         if not self._filereader:
 316             self._filereader = _FileReader(self.hash, self.size(),
 317                                            self.bupmode == git.BUP_CHUNKED)
 318         self._filereader.seek(0)
 319         return self._filereader
 320
 321     def size(self):
 322         """Get this file's size."""
 323         if self._cached_size == None:
 324             debug1('<<<<File.size() is calculating (for %r)...\n' % self.name)
 325             if self.bupmode == git.BUP_CHUNKED:
 326                 self._cached_size = _total_size(self.hash)
 327             else:
 328                 self._cached_size = _chunk_len(self.hash)
 329             debug1('<<<<File.size() done.\n')
 330         return self._cached_size
 331
 332
 333 _symrefs = 0
 334 class Symlink(File):
 335     """A symbolic link from bup's repository."""
 336     def __init__(self, parent, name, hash, bupmode):
 337         File.__init__(self, parent, name, 0120000, hash, bupmode)
 338
 339     def size(self):
 340         """Get the file size of the file at which this link points."""
 341         return len(self.readlink())
 342
 343     def readlink(self):
 344         """Get the path that this link points at."""
 345         return ''.join(cp().join(self.hash.encode('hex')))
 346
 347     def dereference(self):
 348         """Get the node that this link points at.
 349
 350         If the path is invalid, raise a NoSuchFile exception. If the level of
 351         indirection of symlinks is 100 levels deep, raise a TooManySymlinks
 352         exception.
 353         """
 354         global _symrefs
 355         if _symrefs > 100:
 356             raise TooManySymlinks('too many levels of symlinks: %r'
 357                                   % self.fullname())
 358         _symrefs += 1
 359         try:
 360             try:
 361                 return self.parent.lresolve(self.readlink(),
 362                                             stay_inside_fs=True)
 363             except NoSuchFile:
 364                 raise NoSuchFile("%s: broken symlink to %r"
 365                                  % (self.fullname(), self.readlink()))
 366         finally:
 367             _symrefs -= 1
 368
 369     def _lresolve(self, parts):
 370         return self.dereference()._lresolve(parts)
 371
 372
 373 class FakeSymlink(Symlink):
 374     """A symlink that is not stored in the bup repository."""
 375     def __init__(self, parent, name, toname):
 376         Symlink.__init__(self, parent, name, EMPTY_SHA, git.BUP_NORMAL)
 377         self.toname = toname
 378
 379     def readlink(self):
 380         """Get the path that this link points at."""
 381         return self.toname
 382
 383
 384 class Dir(Node):
 385     """A directory stored inside of bup's repository."""
 386
 387     def __init__(self, *args):
 388         Node.__init__(self, *args)
 389         self._metadata_sha = None
 390
 391     def _mksubs(self):
 392         self._subs = {}
 393         it = cp().get(self.hash.encode('hex'))
 394         type = it.next()
 395         if type == 'commit':
 396             del it
 397             it = cp().get(self.hash.encode('hex') + ':')
 398             type = it.next()
 399         assert(type == 'tree')
 400         for (mode,mangled_name,sha) in git.tree_decode(''.join(it)):
 401             if mangled_name == '.bupm':
 402                 self._metadata_sha = sha
 403                 continue
 404             name = mangled_name
 405             (name,bupmode) = git.demangle_name(mangled_name)
 406             if bupmode == git.BUP_CHUNKED:
 407                 mode = GIT_MODE_FILE
 408             if stat.S_ISDIR(mode):
 409                 self._subs[name] = Dir(self, name, mode, sha)
 410             elif stat.S_ISLNK(mode):
 411                 self._subs[name] = Symlink(self, name, sha, bupmode)
 412             else:
 413                 self._subs[name] = File(self, name, mode, sha, bupmode)
 414
 415
 416 class CommitDir(Node):
 417     """A directory that contains all commits that are reachable by a ref.
 418
 419     Contains a set of subdirectories named after the commits' first byte in
 420     hexadecimal. Each of those directories contain all commits with hashes that
 421     start the same as the directory name. The name used for those
 422     subdirectories is the hash of the commit without the first byte. This
 423     separation helps us avoid having too much directories on the same level as
 424     the number of commits grows big.
 425     """
 426     def __init__(self, parent, name):
 427         Node.__init__(self, parent, name, GIT_MODE_TREE, EMPTY_SHA)
 428
 429     def _mksubs(self):
 430         self._subs = {}
 431         refs = git.list_refs()
 432         for ref in refs:
 433             #debug2('ref name: %s\n' % ref[0])
 434             revs = git.rev_list(ref[1].encode('hex'))
 435             for (date, commit) in revs:
 436                 #debug2('commit: %s  date: %s\n' % (commit.encode('hex'), date))
 437                 commithex = commit.encode('hex')
 438                 containername = commithex[:2]
 439                 dirname = commithex[2:]
 440                 n1 = self._subs.get(containername)
 441                 if not n1:
 442                     n1 = CommitList(self, containername)
 443                     self._subs[containername] = n1
 444
 445                 if n1.commits.get(dirname):
 446                     # Stop work for this ref, the rest should already be present
 447                     break
 448
 449                 n1.commits[dirname] = (commit, date)
 450
 451
 452 class CommitList(Node):
 453     """A list of commits with hashes that start with the current node's name."""
 454     def __init__(self, parent, name):
 455         Node.__init__(self, parent, name, GIT_MODE_TREE, EMPTY_SHA)
 456         self.commits = {}
 457
 458     def _mksubs(self):
 459         self._subs = {}
 460         for (name, (hash, date)) in self.commits.items():
 461             n1 = Dir(self, name, GIT_MODE_TREE, hash)
 462             n1.ctime = n1.mtime = date
 463             self._subs[name] = n1
 464
 465
 466 class TagDir(Node):
 467     """A directory that contains all tags in the repository."""
 468     def __init__(self, parent, name):
 469         Node.__init__(self, parent, name, GIT_MODE_TREE, EMPTY_SHA)
 470
 471     def _mksubs(self):
 472         self._subs = {}
 473         for (name, sha) in git.list_refs():
 474             if name.startswith('refs/tags/'):
 475                 name = name[10:]
 476                 date = git.rev_get_date(sha.encode('hex'))
 477                 commithex = sha.encode('hex')
 478                 target = '../.commit/%s/%s' % (commithex[:2], commithex[2:])
 479                 tag1 = FakeSymlink(self, name, target)
 480                 tag1.ctime = tag1.mtime = date
 481                 self._subs[name] = tag1
 482
 483
 484 class BranchList(Node):
 485     """A list of links to commits reachable by a branch in bup's repository.
 486
 487     Represents each commit as a symlink that points to the commit directory in
 488     /.commit/??/ . The symlink is named after the commit date.
 489     """
 490     def __init__(self, parent, name, hash):
 491         Node.__init__(self, parent, name, GIT_MODE_TREE, hash)
 492
 493     def _mksubs(self):
 494         self._subs = {}
 495
 496         tags = git.tags()
 497
 498         revs = list(git.rev_list(self.hash.encode('hex')))
 499         latest = revs[0]
 500         for (date, commit) in revs:
 501             l = time.localtime(date)
 502             ls = time.strftime('%Y-%m-%d-%H%M%S', l)
 503             commithex = commit.encode('hex')
 504             target = '../.commit/%s/%s' % (commithex[:2], commithex[2:])
 505             n1 = FakeSymlink(self, ls, target)
 506             n1.ctime = n1.mtime = date
 507             self._subs[ls] = n1
 508
 509             for tag in tags.get(commit, []):
 510                 t1 = FakeSymlink(self, tag, target)
 511                 t1.ctime = t1.mtime = date
 512                 self._subs[tag] = t1
 513
 514         (date, commit) = latest
 515         commithex = commit.encode('hex')
 516         target = '../.commit/%s/%s' % (commithex[:2], commithex[2:])
 517         n1 = FakeSymlink(self, 'latest', target)
 518         n1.ctime = n1.mtime = date
 519         self._subs['latest'] = n1
 520
 521
 522 class RefList(Node):
 523     """A list of branches in bup's repository.
 524
 525     The sub-nodes of the ref list are a series of CommitList for each commit
 526     hash pointed to by a branch.
 527
 528     Also, a special sub-node named '.commit' contains all commit directories
 529     that are reachable via a ref (e.g. a branch).  See CommitDir for details.
 530     """
 531     def __init__(self, parent):
 532         Node.__init__(self, parent, '/', GIT_MODE_TREE, EMPTY_SHA)
 533
 534     def _mksubs(self):
 535         self._subs = {}
 536
 537         commit_dir = CommitDir(self, '.commit')
 538         self._subs['.commit'] = commit_dir
 539
 540         tag_dir = TagDir(self, '.tag')
 541         self._subs['.tag'] = tag_dir
 542
 543         for (name,sha) in git.list_refs():
 544             if name.startswith('refs/heads/'):
 545                 name = name[11:]
 546                 date = git.rev_get_date(sha.encode('hex'))
 547                 n1 = BranchList(self, name, sha)
 548                 n1.ctime = n1.mtime = date
 549                 self._subs[name] = n1