src/allmydata/filetree/directory.py

   1
   2 from zope.interface import implements
   3 from twisted.internet import defer
   4 from cStringIO import StringIO
   5 from allmydata.filetree.interfaces import (
   6     INode, INodeMaker, IDirectoryNode, ISubTree,
   7     ICHKDirectoryNode, ISSKDirectoryNode,
   8     NoSuchChildError,
   9     )
  10 from allmydata.filetree.basenode import BaseDataNode
  11 from allmydata import download
  12 from allmydata.util import bencode
  13
  14 # interesting feature ideas:
  15 #  pubsub for MutableDirectoryNode: get rapid notification of changes
  16 #  caused by someone else
  17 #
  18 #  bind a local physical directory to the MutableDirectoryNode contents:
  19 #  each time the vdrive changes, update the local drive to match, and
  20 #  vice versa.
  21
  22 from itertools import islice, izip
  23 def in_pairs(iterable):
  24     "s -> (s0,s1), (s2,s3), (s4,s5), ..."
  25     a = islice(iterable, 0, None, 2)
  26     b = islice(iterable, 1, None, 2)
  27     return izip(a, b)
  28
  29
  30 class SubTreeNode:
  31     implements(INode, IDirectoryNode)
  32
  33     def __init__(self, tree):
  34         self.enclosing_tree = tree
  35         self.children = {}
  36 #        # subdirectory_node_children maps child name to another SubTreeNode
  37 #        # instance. This is only for internal directory nodes. All other
  38 #        # nodes are listed in child_specifications instead.
  39 #        self.subdirectory_node_children = {}
  40 #        # child_specifications maps child name to a specification tuple which
  41 #        # describes how to obtain the actual child. For example, if "foo.jpg"
  42 #        # in this node represents a CHK-encoded FILE with a uri of "fooURI",
  43 #        # then self.child_specifications["foo.jpg"] = ("CHKFILE","fooURI")
  44 #        self.child_specifications = {}
  45
  46     def list(self):
  47         return self.children
  48
  49     def get(self, childname):
  50         if childname in self.children:
  51             return self.children[childname]
  52         else:
  53             raise NoSuchChildError("no child named '%s'" % (childname,))
  54
  55     def get_subtree(self):
  56         return self.enclosing_tree
  57
  58     def delete(self, childname):
  59         assert self.enclosing_tree.is_mutable()
  60         if childname in self.children:
  61             del self.children[childname]
  62         else:
  63             raise NoSuchChildError("no child named '%s'" % (childname,))
  64
  65     def add_subdir(self, childname):
  66         assert childname not in self.children
  67         newnode = SubTreeNode(self.enclosing_tree)
  68         self.children[childname] = newnode
  69         return newnode
  70
  71     def add(self, childname, node):
  72         assert childname not in self.children
  73         assert INode(node)
  74         self.children[childname] = node
  75         return self
  76
  77     def serialize_node(self):
  78         # note: this is a one-pass recursive serialization that will result
  79         # in the whole file table being held in memory. This is only
  80         # appropriate for directories with fewer than, say, 10k nodes. If we
  81         # support larger directories, we should turn this into some kind of
  82         # generator instead, and write the serialized data directly to a
  83         # tempfile.
  84         #
  85         # [name1, child1, name2, child2..]
  86         #
  87         #  child1 is either a list for subdirs, or a string for non-subdirs
  88
  89         data = []
  90         for name in sorted(self.children.keys()):
  91             data.append(name)
  92             data.append(self.children[name].serialize_node())
  93         return data
  94
  95     def populate_dirnode(self, data, node_maker):
  96         assert INodeMaker(node_maker)
  97         assert len(data) % 2 == 0
  98         for (name, child_data) in in_pairs(data):
  99             if isinstance(child_data, (list, tuple)):
 100                 child = SubTreeNode(self.enclosing_tree)
 101                 child.populate_dirnode(child_data, node_maker)
 102             else:
 103                 assert isinstance(child_data, str)
 104                 child = node_maker.make_node_from_serialized(child_data)
 105             self.children[name] = child
 106
 107     def is_leaf_subtree(self):
 108         return False
 109
 110
 111 class _DirectorySubTree(object):
 112     """I represent a set of connected directories that all share the same
 113     access control: any given person can read or write anything in this tree
 114     as a group, and it is not possible to give access to some pieces of this
 115     tree and not to others. Read-only access to individual files can be
 116     granted independently, of course, but through an unnamed URI, not as a
 117     subdirectory.
 118
 119     Each internal directory is represented by a separate Node.
 120
 121     This is an abstract base class. Individual subclasses will implement
 122     various forms of serialization, persistence, and mutability.
 123
 124     """
 125     implements(ISubTree)
 126
 127
 128     def new(self):
 129         # create a new, empty directory
 130         self.root = SubTreeNode(self)
 131         self.mutable = True # sure, why not
 132         return self
 133
 134     def populate_from_node(self, node, parent_is_mutable, node_maker, downloader):
 135         # self.populate_from_node must be defined by the subclass (CHK or
 136         # SSK), since it controls how the spec is interpreted. It will
 137         # probably use the contents of the node to figure out what to
 138         # download from the mesh, then pass this downloaded serialized data
 139         # to populate_from_data()
 140         raise NotImplementedError
 141
 142     def _populate_from_data(self, data, node_maker):
 143         self.root = SubTreeNode(self)
 144         self.root.populate_dirnode(bencode.bdecode(data), node_maker)
 145         return self
 146
 147     def serialize_subtree_to_file(self, f):
 148         sexprs = self.root.serialize_node()
 149         bencode.bwrite(sexprs, f)
 150
 151     def is_mutable(self):
 152         return self.mutable
 153
 154     def get_node_for_path(self, path):
 155         # this is restricted to traversing our own subtree. Returns
 156         # (found_path, node, remaining_path)
 157         found_path = []
 158         remaining_path = path[:]
 159         node = self.root
 160         while remaining_path:
 161             name = remaining_path[0]
 162             try:
 163                 childnode = node.get(name)
 164             except NoSuchChildError:
 165                 # The node *would* be in this subtree if it existed, but it
 166                 # doesn't. Leave found_path and remaining_path alone, and
 167                 # node points at the last parent node that was on the path.
 168                 break
 169             if IDirectoryNode.providedBy(childnode):
 170                 # recurse
 171                 node = childnode
 172                 found_path.append(name)
 173                 remaining_path.pop(0)
 174                 continue
 175             else:
 176                 # the path takes us out of this subtree and into another
 177                 node = childnode # next subtree node
 178                 found_path.append(name)
 179                 remaining_path.pop(0)
 180                 break
 181         return (found_path, node, remaining_path)
 182
 183     def put_node_at_path(self, path, new_node):
 184         assert len(path) > 0
 185         child_name = path[-1]
 186
 187         # first step: get (or create) the parent directory
 188         node = self.root
 189         for subdir_name in path[:-1]:
 190             # TODO: peeking at private attributes is naughty, but using
 191             # node.get() and catching NoSuchChildError would be slightly
 192             # ugly. Reconsider the IDirectoryNode.get() API.
 193             childnode = node.children.get(subdir_name)
 194             if childnode:
 195                 assert IDirectoryNode.providedBy(childnode)
 196             else:
 197                 # we have to create new directories until the parent exists
 198                 childnode = node.add_subdir(subdir_name)
 199             node = childnode
 200
 201         # 'node' is now pointing at the parent directory
 202         if child_name in node.children:
 203             # oops, there's already something there. We can replace it.
 204             # TODO: How do we free the subtree that was just orphaned?
 205             node.delete(child_name)
 206
 207         # now we can finally add the new node
 208         node.add(child_name, new_node)
 209
 210     def delete_node_at_path(self, path):
 211         assert len(path) > 0
 212         child_name = path[-1]
 213
 214         # first step: get the parent directory
 215         node = self.root
 216         for subdir_name in path[:-1]:
 217             subdir_node = node.get(subdir_name) # may raise NoSuchChildError
 218             node = subdir_node
 219
 220         # 'node' is now pointing at the parent directory. Let's make sure the
 221         # path they want to delete actually exists. We don't really care what
 222         # the child *is*, just that it exists.
 223         node.get(child_name) # may raise NoSuchChildError
 224
 225         # now delete it
 226         # TODO: How do we free the subtree that was just orphaned?
 227         node.delete(child_name)
 228
 229
 230 class LocalFileSubTreeNode(BaseDataNode):
 231     prefix = "LocalFileDirectory"
 232
 233     def new(self, filename):
 234         self.filename = filename
 235         return self
 236
 237     def get_base_data(self):
 238         return self.filename
 239     def set_base_data(self, data):
 240         self.filename = data
 241
 242     def is_leaf_subtree(self):
 243         return False
 244
 245 class LocalFileSubTree(_DirectorySubTree):
 246     node_class = LocalFileSubTreeNode
 247
 248     def new(self, filename):
 249         self.filename = filename
 250         return _DirectorySubTree.new(self)
 251
 252     def populate_from_node(self, node, parent_is_mutable, node_maker, downloader):
 253         self.mutable = True # probably
 254         self.filename = node.filename
 255         f = open(self.filename, "rb")
 256         data = f.read()
 257         f.close()
 258         d = defer.succeed(data)
 259         d.addCallback(self._populate_from_data, node_maker)
 260         return d
 261
 262     def mutation_modifies_parent(self):
 263         return False
 264
 265     def create_node_now(self):
 266         return LocalFileSubTreeNode().new(self.filename)
 267
 268     def _update(self):
 269         f = open(self.filename, "wb")
 270         self.serialize_subtree_to_file(f)
 271         f.close()
 272
 273     def update_now(self, uploader):
 274         self._update()
 275         return self.create_node_now()
 276
 277     def update(self, work_queue):
 278         # TODO: this may suffer from the same execute-too-early problem as
 279         # redirect.LocalFileRedirection
 280         self._update()
 281         return None
 282
 283
 284 class CHKDirectorySubTreeNode(BaseDataNode):
 285     implements(ICHKDirectoryNode)
 286     prefix = "CHKDirectory"
 287
 288     def get_base_data(self):
 289         return self.uri
 290     def set_base_data(self, data):
 291         self.uri = data
 292
 293     def get_uri(self):
 294         return self.uri
 295
 296     def is_leaf_subtree(self):
 297         return False
 298
 299
 300 class CHKDirectorySubTree(_DirectorySubTree):
 301     # maybe mutable, maybe not
 302     node_class = CHKDirectorySubTreeNode
 303
 304     def new(self):
 305         self.uri = None
 306         return _DirectorySubTree.new(self)
 307
 308     def set_uri(self, uri):
 309         self.uri = uri
 310
 311     def populate_from_node(self, node, parent_is_mutable, node_maker, downloader):
 312         assert ICHKDirectoryNode(node)
 313         self.mutable = parent_is_mutable
 314         d = downloader.download(node.get_uri(), download.Data())
 315         d.addCallback(self._populate_from_data, node_maker)
 316         def _populated(res):
 317             self.uri = node.get_uri()
 318             return self
 319         d.addCallback(_populated)
 320         return d
 321
 322     def mutation_modifies_parent(self):
 323         return True
 324
 325     def create_node_now(self):
 326         return CHKDirectorySubTreeNode().new(self.uri)
 327
 328     def update_now(self, uploader):
 329         f = StringIO()
 330         self.serialize_subtree_to_file(f)
 331         data = f.getvalue()
 332         d = uploader.upload_data(data)
 333         def _uploaded(uri):
 334             self.uri = uri
 335             return self.create_node_now()
 336         d.addCallback(_uploaded)
 337         return d
 338
 339     def update(self, workqueue):
 340         # this is the CHK form
 341         old_uri = self.uri
 342         f, filename = workqueue.create_tempfile(".chkdir")
 343         self.serialize_subtree_to_file(f)
 344         f.close()
 345         boxname = workqueue.create_boxname()
 346         workqueue.add_upload_chk(filename, boxname)
 347         workqueue.add_delete_tempfile(filename)
 348         workqueue.add_retain_uri_from_box(boxname)
 349         workqueue.add_delete_box(boxname)
 350         if old_uri:
 351             workqueue.add_unlink_uri(old_uri)
 352         # TODO: think about how self.old_uri will get updated. I *think* that
 353         # this whole instance will get replaced, so it ought to be ok. But
 354         # this needs investigation.
 355
 356         # mutation affects our parent, so we return a boxname for them
 357         return boxname
 358
 359
 360 class SSKDirectorySubTreeNode(object):
 361     implements(INode, ISSKDirectoryNode)
 362     prefix = "SSKDirectory"
 363
 364     def serialize_node(self):
 365         data = (self.read_cap, self.write_cap)
 366         return "%s:%s" % (self.prefix, bencode.bencode(data))
 367     def populate_node(self, body, node_maker):
 368         self.read_cap, self.write_cap = bencode.bdecode(body)
 369
 370     def get_read_capability(self):
 371         return self.read_cap
 372     def get_write_capability(self):
 373         return self.write_cap
 374     def set_read_capability(self, read_cap):
 375         self.read_cap = read_cap
 376     def set_write_capability(self, write_cap):
 377         self.write_cap = write_cap
 378
 379     def is_leaf_subtree(self):
 380         return False
 381
 382
 383 class SSKDirectorySubTree(_DirectorySubTree):
 384     node_class = SSKDirectorySubTreeNode
 385
 386     def new(self):
 387         _DirectorySubTree.new(self)
 388         self.version = 0
 389         # TODO: populate
 390         return self
 391
 392     def populate_from_node(self, node, parent_is_mutable, node_maker, downloader):
 393         node = ISSKDirectoryNode(node)
 394         self.read_capability = node.get_read_capability()
 395         self.write_capability = node.get_write_capability()
 396         self.mutable = bool(self.write_capability)
 397         d = downloader.download_ssk(self.read_capability, download.Data())
 398         d.addCallback(self._populate_from_data, node_maker)
 399         return d
 400
 401     def set_version(self, version):
 402         self.version = version
 403
 404     def mutation_modifies_parent(self):
 405         return False
 406
 407     def create_node_now(self):
 408         node = SSKDirectorySubTreeNode()
 409         node.set_read_capability(self.read_capability)
 410         node.set_write_capability(self.write_capability)
 411         return node
 412
 413     def update_now(self, uploader):
 414         if not self.write_capability:
 415             raise RuntimeError("This SSKDirectorySubTree is not mutable")
 416
 417         f = StringIO()
 418         self.serialize_subtree_to_file(f)
 419         data = f.getvalue()
 420
 421         self.version += 1
 422         d = uploader.upload_ssk_data(self.write_capability, self.version, data)
 423         d.addCallback(lambda ignored: self.create_node_now())
 424         return d
 425
 426     def update(self, workqueue):
 427         # this is the SSK form
 428         f, filename = workqueue.create_tempfile(".sskdir")
 429         self.serialize_subtree_to_file(f)
 430         f.close()
 431
 432         oldversion = self.version
 433         self.version = self.version + 1
 434
 435         workqueue.add_upload_ssk(self.write_capability, oldversion, filename)
 436         workqueue.add_delete_tempfile(filename)
 437         workqueue.add_retain_ssk(self.read_capability)
 438         # mutation does not affect our parent
 439         return None