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         if self._subs == None:
 285             self._mksubs()
 286         return 1
 287
 288     def size(self):
 289         """Get the size of the current node."""
 290         return 0
 291
 292     def open(self):
 293         """Open the current node. It is an error to open a non-file node."""
 294         raise NotFile('%s is not a regular file' % self.name)
 295
 296     def _populate_metadata(self, force=False):
 297         # Only Dirs contain .bupm files, so by default, do nothing.
 298         pass
 299
 300     def metadata(self):
 301         """Return this Node's Metadata() object, if any."""
 302         if not self._metadata and self.parent:
 303             self.parent._populate_metadata(force=True)
 304         return self._metadata
 305
 306     def release(self):
 307         """Release resources that can be automatically restored (at a cost)."""
 308         self._metadata = None
 309         self._subs = None
 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, **kwargs):
 399         Node.__init__(self, *args, **kwargs)
 400         self._bupm = None
 401
 402     def _populate_metadata(self, force=False):
 403         if self._metadata and not force:
 404             return
 405         if not self._subs:
 406             self._mksubs()
 407         if not self._bupm:
 408             return
 409         meta_stream = self._bupm.open()
 410         dir_meta = metadata.Metadata.read(meta_stream)
 411         for sub in self:
 412             if not stat.S_ISDIR(sub.mode):
 413                 sub._metadata = metadata.Metadata.read(meta_stream)
 414         self._metadata = dir_meta
 415
 416     def _mksubs(self):
 417         self._subs = {}
 418         it = cp().get(self.hash.encode('hex'))
 419         type = it.next()
 420         if type == 'commit':
 421             del it
 422             it = cp().get(self.hash.encode('hex') + ':')
 423             type = it.next()
 424         assert(type == 'tree')
 425         for (mode,mangled_name,sha) in git.tree_decode(''.join(it)):
 426             if mangled_name == '.bupm':
 427                 bupmode = stat.S_ISDIR(mode) and BUP_CHUNKED or BUP_NORMAL
 428                 self._bupm = File(self, mangled_name, GIT_MODE_FILE, sha,
 429                                   bupmode)
 430                 continue
 431             name = mangled_name
 432             (name,bupmode) = git.demangle_name(mangled_name)
 433             if bupmode == git.BUP_CHUNKED:
 434                 mode = GIT_MODE_FILE
 435             if stat.S_ISDIR(mode):
 436                 self._subs[name] = Dir(self, name, mode, sha)
 437             elif stat.S_ISLNK(mode):
 438                 self._subs[name] = Symlink(self, name, sha, bupmode)
 439             else:
 440                 self._subs[name] = File(self, name, mode, sha, bupmode)
 441
 442     def metadata(self):
 443         """Return this Dir's Metadata() object, if any."""
 444         self._populate_metadata()
 445         return self._metadata
 446
 447     def metadata_file(self):
 448         """Return this Dir's .bupm File, if any."""
 449         if not self._subs:
 450             self._mksubs()
 451         return self._bupm
 452
 453     def release(self):
 454         """Release restorable resources held by this node."""
 455         self._bupm = None
 456         super(Dir, self).release()
 457
 458
 459 class CommitDir(Node):
 460     """A directory that contains all commits that are reachable by a ref.
 461
 462     Contains a set of subdirectories named after the commits' first byte in
 463     hexadecimal. Each of those directories contain all commits with hashes that
 464     start the same as the directory name. The name used for those
 465     subdirectories is the hash of the commit without the first byte. This
 466     separation helps us avoid having too much directories on the same level as
 467     the number of commits grows big.
 468     """
 469     def __init__(self, parent, name):
 470         Node.__init__(self, parent, name, GIT_MODE_TREE, EMPTY_SHA)
 471
 472     def _mksubs(self):
 473         self._subs = {}
 474         refs = git.list_refs()
 475         for ref in refs:
 476             #debug2('ref name: %s\n' % ref[0])
 477             revs = git.rev_list(ref[1].encode('hex'))
 478             for (date, commit) in revs:
 479                 #debug2('commit: %s  date: %s\n' % (commit.encode('hex'), date))
 480                 commithex = commit.encode('hex')
 481                 containername = commithex[:2]
 482                 dirname = commithex[2:]
 483                 n1 = self._subs.get(containername)
 484                 if not n1:
 485                     n1 = CommitList(self, containername)
 486                     self._subs[containername] = n1
 487
 488                 if n1.commits.get(dirname):
 489                     # Stop work for this ref, the rest should already be present
 490                     break
 491
 492                 n1.commits[dirname] = (commit, date)
 493
 494
 495 class CommitList(Node):
 496     """A list of commits with hashes that start with the current node's name."""
 497     def __init__(self, parent, name):
 498         Node.__init__(self, parent, name, GIT_MODE_TREE, EMPTY_SHA)
 499         self.commits = {}
 500
 501     def _mksubs(self):
 502         self._subs = {}
 503         for (name, (hash, date)) in self.commits.items():
 504             n1 = Dir(self, name, GIT_MODE_TREE, hash)
 505             n1.ctime = n1.mtime = date
 506             self._subs[name] = n1
 507
 508
 509 class TagDir(Node):
 510     """A directory that contains all tags in the repository."""
 511     def __init__(self, parent, name):
 512         Node.__init__(self, parent, name, GIT_MODE_TREE, EMPTY_SHA)
 513
 514     def _mksubs(self):
 515         self._subs = {}
 516         for (name, sha) in git.list_refs():
 517             if name.startswith('refs/tags/'):
 518                 name = name[10:]
 519                 date = git.get_commit_dates([sha.encode('hex')])[0]
 520                 commithex = sha.encode('hex')
 521                 target = '../.commit/%s/%s' % (commithex[:2], commithex[2:])
 522                 tag1 = FakeSymlink(self, name, target)
 523                 tag1.ctime = tag1.mtime = date
 524                 self._subs[name] = tag1
 525
 526
 527 class BranchList(Node):
 528     """A list of links to commits reachable by a branch in bup's repository.
 529
 530     Represents each commit as a symlink that points to the commit directory in
 531     /.commit/??/ . The symlink is named after the commit date.
 532     """
 533     def __init__(self, parent, name, hash):
 534         Node.__init__(self, parent, name, GIT_MODE_TREE, hash)
 535
 536     def _mksubs(self):
 537         self._subs = {}
 538
 539         tags = git.tags()
 540
 541         revs = list(git.rev_list(self.hash.encode('hex')))
 542         latest = revs[0]
 543         for (date, commit) in revs:
 544             l = time.localtime(date)
 545             ls = time.strftime('%Y-%m-%d-%H%M%S', l)
 546             commithex = commit.encode('hex')
 547             target = '../.commit/%s/%s' % (commithex[:2], commithex[2:])
 548             n1 = FakeSymlink(self, ls, target)
 549             n1.ctime = n1.mtime = date
 550             self._subs[ls] = n1
 551
 552             for tag in tags.get(commit, []):
 553                 t1 = FakeSymlink(self, tag, target)
 554                 t1.ctime = t1.mtime = date
 555                 self._subs[tag] = t1
 556
 557         (date, commit) = latest
 558         commithex = commit.encode('hex')
 559         target = '../.commit/%s/%s' % (commithex[:2], commithex[2:])
 560         n1 = FakeSymlink(self, 'latest', target)
 561         n1.ctime = n1.mtime = date
 562         self._subs['latest'] = n1
 563
 564
 565 class RefList(Node):
 566     """A list of branches in bup's repository.
 567
 568     The sub-nodes of the ref list are a series of CommitList for each commit
 569     hash pointed to by a branch.
 570
 571     Also, a special sub-node named '.commit' contains all commit directories
 572     that are reachable via a ref (e.g. a branch).  See CommitDir for details.
 573     """
 574     def __init__(self, parent):
 575         Node.__init__(self, parent, '/', GIT_MODE_TREE, EMPTY_SHA)
 576
 577     def _mksubs(self):
 578         self._subs = {}
 579
 580         commit_dir = CommitDir(self, '.commit')
 581         self._subs['.commit'] = commit_dir
 582
 583         tag_dir = TagDir(self, '.tag')
 584         self._subs['.tag'] = tag_dir
 585
 586         refs_info = [(name[11:], sha) for (name,sha) in git.list_refs() \
 587                      if name.startswith('refs/heads/')]
 588
 589         dates = git.get_commit_dates([sha.encode('hex')
 590                                       for (name, sha) in refs_info])
 591
 592         for (name, sha), date in zip(refs_info, dates):
 593             n1 = BranchList(self, name, sha)
 594             n1.ctime = n1.mtime = date
 595             self._subs[name] = n1