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