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