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