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