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