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