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