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 "<bup.vfs.Node object at X - name:%r hash:%s parent:%r>" \
 178             % (self.name, self.hash.encode('hex'),
 179                self.parent.name if self.parent.name 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         self._populate_metadata()
 445         return self._bupm
 446
 447
 448 class CommitDir(Node):
 449     """A directory that contains all commits that are reachable by a ref.
 450
 451     Contains a set of subdirectories named after the commits' first byte in
 452     hexadecimal. Each of those directories contain all commits with hashes that
 453     start the same as the directory name. The name used for those
 454     subdirectories is the hash of the commit without the first byte. This
 455     separation helps us avoid having too much directories on the same level as
 456     the number of commits grows big.
 457     """
 458     def __init__(self, parent, name):
 459         Node.__init__(self, parent, name, GIT_MODE_TREE, EMPTY_SHA)
 460
 461     def _mksubs(self):
 462         self._subs = {}
 463         refs = git.list_refs()
 464         for ref in refs:
 465             #debug2('ref name: %s\n' % ref[0])
 466             revs = git.rev_list(ref[1].encode('hex'))
 467             for (date, commit) in revs:
 468                 #debug2('commit: %s  date: %s\n' % (commit.encode('hex'), date))
 469                 commithex = commit.encode('hex')
 470                 containername = commithex[:2]
 471                 dirname = commithex[2:]
 472                 n1 = self._subs.get(containername)
 473                 if not n1:
 474                     n1 = CommitList(self, containername)
 475                     self._subs[containername] = n1
 476
 477                 if n1.commits.get(dirname):
 478                     # Stop work for this ref, the rest should already be present
 479                     break
 480
 481                 n1.commits[dirname] = (commit, date)
 482
 483
 484 class CommitList(Node):
 485     """A list of commits with hashes that start with the current node's name."""
 486     def __init__(self, parent, name):
 487         Node.__init__(self, parent, name, GIT_MODE_TREE, EMPTY_SHA)
 488         self.commits = {}
 489
 490     def _mksubs(self):
 491         self._subs = {}
 492         for (name, (hash, date)) in self.commits.items():
 493             n1 = Dir(self, name, GIT_MODE_TREE, hash)
 494             n1.ctime = n1.mtime = date
 495             self._subs[name] = n1
 496
 497
 498 class TagDir(Node):
 499     """A directory that contains all tags in the repository."""
 500     def __init__(self, parent, name):
 501         Node.__init__(self, parent, name, GIT_MODE_TREE, EMPTY_SHA)
 502
 503     def _mksubs(self):
 504         self._subs = {}
 505         for (name, sha) in git.list_refs():
 506             if name.startswith('refs/tags/'):
 507                 name = name[10:]
 508                 date = git.rev_get_date(sha.encode('hex'))
 509                 commithex = sha.encode('hex')
 510                 target = '../.commit/%s/%s' % (commithex[:2], commithex[2:])
 511                 tag1 = FakeSymlink(self, name, target)
 512                 tag1.ctime = tag1.mtime = date
 513                 self._subs[name] = tag1
 514
 515
 516 class BranchList(Node):
 517     """A list of links to commits reachable by a branch in bup's repository.
 518
 519     Represents each commit as a symlink that points to the commit directory in
 520     /.commit/??/ . The symlink is named after the commit date.
 521     """
 522     def __init__(self, parent, name, hash):
 523         Node.__init__(self, parent, name, GIT_MODE_TREE, hash)
 524
 525     def _mksubs(self):
 526         self._subs = {}
 527
 528         tags = git.tags()
 529
 530         revs = list(git.rev_list(self.hash.encode('hex')))
 531         latest = revs[0]
 532         for (date, commit) in revs:
 533             l = time.localtime(date)
 534             ls = time.strftime('%Y-%m-%d-%H%M%S', l)
 535             commithex = commit.encode('hex')
 536             target = '../.commit/%s/%s' % (commithex[:2], commithex[2:])
 537             n1 = FakeSymlink(self, ls, target)
 538             n1.ctime = n1.mtime = date
 539             self._subs[ls] = n1
 540
 541             for tag in tags.get(commit, []):
 542                 t1 = FakeSymlink(self, tag, target)
 543                 t1.ctime = t1.mtime = date
 544                 self._subs[tag] = t1
 545
 546         (date, commit) = latest
 547         commithex = commit.encode('hex')
 548         target = '../.commit/%s/%s' % (commithex[:2], commithex[2:])
 549         n1 = FakeSymlink(self, 'latest', target)
 550         n1.ctime = n1.mtime = date
 551         self._subs['latest'] = n1
 552
 553
 554 class RefList(Node):
 555     """A list of branches in bup's repository.
 556
 557     The sub-nodes of the ref list are a series of CommitList for each commit
 558     hash pointed to by a branch.
 559
 560     Also, a special sub-node named '.commit' contains all commit directories
 561     that are reachable via a ref (e.g. a branch).  See CommitDir for details.
 562     """
 563     def __init__(self, parent):
 564         Node.__init__(self, parent, '/', GIT_MODE_TREE, EMPTY_SHA)
 565
 566     def _mksubs(self):
 567         self._subs = {}
 568
 569         commit_dir = CommitDir(self, '.commit')
 570         self._subs['.commit'] = commit_dir
 571
 572         tag_dir = TagDir(self, '.tag')
 573         self._subs['.tag'] = tag_dir
 574
 575         for (name,sha) in git.list_refs():
 576             if name.startswith('refs/heads/'):
 577                 name = name[11:]
 578                 date = git.rev_get_date(sha.encode('hex'))
 579                 n1 = BranchList(self, name, sha)
 580                 n1.ctime = n1.mtime = date
 581                 self._subs[name] = n1