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 = 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 = \
 403                     File(self, mangled_name, mode, sha, git.BUP_NORMAL)
 404                 continue
 405             name = mangled_name
 406             (name,bupmode) = git.demangle_name(mangled_name)
 407             if bupmode == git.BUP_CHUNKED:
 408                 mode = GIT_MODE_FILE
 409             if stat.S_ISDIR(mode):
 410                 self._subs[name] = Dir(self, name, mode, sha)
 411             elif stat.S_ISLNK(mode):
 412                 self._subs[name] = Symlink(self, name, sha, bupmode)
 413             else:
 414                 self._subs[name] = File(self, name, mode, sha, bupmode)
 415
 416     def metadata_file(self):
 417         if self._subs == None:
 418             self._mksubs()
 419         return self._metadata
 420
 421
 422 class CommitDir(Node):
 423     """A directory that contains all commits that are reachable by a ref.
 424
 425     Contains a set of subdirectories named after the commits' first byte in
 426     hexadecimal. Each of those directories contain all commits with hashes that
 427     start the same as the directory name. The name used for those
 428     subdirectories is the hash of the commit without the first byte. This
 429     separation helps us avoid having too much directories on the same level as
 430     the number of commits grows big.
 431     """
 432     def __init__(self, parent, name):
 433         Node.__init__(self, parent, name, GIT_MODE_TREE, EMPTY_SHA)
 434
 435     def _mksubs(self):
 436         self._subs = {}
 437         refs = git.list_refs()
 438         for ref in refs:
 439             #debug2('ref name: %s\n' % ref[0])
 440             revs = git.rev_list(ref[1].encode('hex'))
 441             for (date, commit) in revs:
 442                 #debug2('commit: %s  date: %s\n' % (commit.encode('hex'), date))
 443                 commithex = commit.encode('hex')
 444                 containername = commithex[:2]
 445                 dirname = commithex[2:]
 446                 n1 = self._subs.get(containername)
 447                 if not n1:
 448                     n1 = CommitList(self, containername)
 449                     self._subs[containername] = n1
 450
 451                 if n1.commits.get(dirname):
 452                     # Stop work for this ref, the rest should already be present
 453                     break
 454
 455                 n1.commits[dirname] = (commit, date)
 456
 457
 458 class CommitList(Node):
 459     """A list of commits with hashes that start with the current node's name."""
 460     def __init__(self, parent, name):
 461         Node.__init__(self, parent, name, GIT_MODE_TREE, EMPTY_SHA)
 462         self.commits = {}
 463
 464     def _mksubs(self):
 465         self._subs = {}
 466         for (name, (hash, date)) in self.commits.items():
 467             n1 = Dir(self, name, GIT_MODE_TREE, hash)
 468             n1.ctime = n1.mtime = date
 469             self._subs[name] = n1
 470
 471
 472 class TagDir(Node):
 473     """A directory that contains all tags in the repository."""
 474     def __init__(self, parent, name):
 475         Node.__init__(self, parent, name, GIT_MODE_TREE, EMPTY_SHA)
 476
 477     def _mksubs(self):
 478         self._subs = {}
 479         for (name, sha) in git.list_refs():
 480             if name.startswith('refs/tags/'):
 481                 name = name[10:]
 482                 date = git.rev_get_date(sha.encode('hex'))
 483                 commithex = sha.encode('hex')
 484                 target = '../.commit/%s/%s' % (commithex[:2], commithex[2:])
 485                 tag1 = FakeSymlink(self, name, target)
 486                 tag1.ctime = tag1.mtime = date
 487                 self._subs[name] = tag1
 488
 489
 490 class BranchList(Node):
 491     """A list of links to commits reachable by a branch in bup's repository.
 492
 493     Represents each commit as a symlink that points to the commit directory in
 494     /.commit/??/ . The symlink is named after the commit date.
 495     """
 496     def __init__(self, parent, name, hash):
 497         Node.__init__(self, parent, name, GIT_MODE_TREE, hash)
 498
 499     def _mksubs(self):
 500         self._subs = {}
 501
 502         tags = git.tags()
 503
 504         revs = list(git.rev_list(self.hash.encode('hex')))
 505         latest = revs[0]
 506         for (date, commit) in revs:
 507             l = time.localtime(date)
 508             ls = time.strftime('%Y-%m-%d-%H%M%S', l)
 509             commithex = commit.encode('hex')
 510             target = '../.commit/%s/%s' % (commithex[:2], commithex[2:])
 511             n1 = FakeSymlink(self, ls, target)
 512             n1.ctime = n1.mtime = date
 513             self._subs[ls] = n1
 514
 515             for tag in tags.get(commit, []):
 516                 t1 = FakeSymlink(self, tag, target)
 517                 t1.ctime = t1.mtime = date
 518                 self._subs[tag] = t1
 519
 520         (date, commit) = latest
 521         commithex = commit.encode('hex')
 522         target = '../.commit/%s/%s' % (commithex[:2], commithex[2:])
 523         n1 = FakeSymlink(self, 'latest', target)
 524         n1.ctime = n1.mtime = date
 525         self._subs['latest'] = n1
 526
 527
 528 class RefList(Node):
 529     """A list of branches in bup's repository.
 530
 531     The sub-nodes of the ref list are a series of CommitList for each commit
 532     hash pointed to by a branch.
 533
 534     Also, a special sub-node named '.commit' contains all commit directories
 535     that are reachable via a ref (e.g. a branch).  See CommitDir for details.
 536     """
 537     def __init__(self, parent):
 538         Node.__init__(self, parent, '/', GIT_MODE_TREE, EMPTY_SHA)
 539
 540     def _mksubs(self):
 541         self._subs = {}
 542
 543         commit_dir = CommitDir(self, '.commit')
 544         self._subs['.commit'] = commit_dir
 545
 546         tag_dir = TagDir(self, '.tag')
 547         self._subs['.tag'] = tag_dir
 548
 549         for (name,sha) in git.list_refs():
 550             if name.startswith('refs/heads/'):
 551                 name = name[11:]
 552                 date = git.rev_get_date(sha.encode('hex'))
 553                 n1 = BranchList(self, name, sha)
 554                 n1.ctime = n1.mtime = date
 555                 self._subs[name] = n1