Merge lp:~leonardr/lazr.restful/bleed-through-stack into lp:lazr.restful

[Leonard Richardson]

[Leonard Richardson (leonardr)]

This branch introduces the BleedThroughDict, a data structure I'll be using in my multi-version web service code to keep track of which Python annotations apply to which versions of the web service.

The basic idea behind the BleedThroughDict: it's a stack of dictionaries that acts like a single dictionary. I can push a dictionary onto the stack containing annotations for version n, then another dictionary containing annotations for version n+1. Any annotations defined in version n but not in version n+1 will 'bleed through', and version n+1 will inherit their values.

I couldn't find a similar data structure already existing, but if there is one in an easily accessible utility library I'm happy to use it instead.

I did not implement all of dict's methods, only the ones I think I'll need for the multi-version code.

[lp:~leonardr/lazr.restful/bleed-through-stack]

97. By Leonard Richardson on 2010-01-13

Removed probably unnecessary substack code.

[Jonathan Lange (jml)]

Hey Leonard,

I can't find much to comment on in this branch -- the test coverage is great, the docs read well and the code is clean.

I don't know of any other general data abstractions like this, but would note that it's got similarities to the layered configuration approach we have in lazr.config. Perhaps there's code that can be shared there.

Some thoughts:
  - Although 'append' and 'pop' rhyme nicely with the list methods, I think I would prefer 'push' to 'append', since it makes the stack nature clear. Change at your discretion.
  - 'missing' is private, so it should probably be prefixed with an underscore.
  - You know your needs best, but I reckon you'll want an __iter__ and maybe keys() & values().

Minor formatting issues:
  - in _get_from_top_of_stack, there should be spaces around the minus operator in the 'range' call.
  - in the doc, 'my_new_dict = { 1 : 2 }' should read 'my_new_dict = {1: 2}'

cheers,
jml

review: Approve

[Leonard Richardson (leonardr)]

I filed bug 507399 to see if lazr.config can use BleedThroughDict.

[lp:~leonardr/lazr.restful/bleed-through-stack]

98. By Leonard Richardson on 2010-01-14

Response to feedback.

=== modified file 'src/lazr/restful/docs/utils.txt'
--- src/lazr/restful/docs/utils.txt	2010-01-11 14:38:47 +0000
+++ src/lazr/restful/docs/utils.txt	2010-01-14 10:11:11 +0000
@@ -1,6 +1,210 @@
 Various utility functions
 *************************
 
+BleedThroughDict
+================
+
+This class is a stack of named dicts that can be treated as a single
+dict. Values from dicts lower on the stack will "bleed through" to the
+top, unless blocked by a value from a dict higher on the stack.
+
+A BleedThroughDict starts out empty and unusable. It can't be treated
+as a dict because there are no real dicts in the stack.
+
+    >>> from lazr.restful.utils import BleedThroughDict
+    >>> stack = BleedThroughDict()
+
+    >>> stack.is_empty
+    True
+
+    >>> stack.dict_names
+    []
+
+    >>> sorted(stack.items())
+    []
+
+    >>> stack.pop()
+    Traceback (most recent call last):
+    ...
+    IndexError: pop from empty list
+
+    >>> stack['key'] = 'value'
+    Traceback (most recent call last):
+    ...
+    IndexError: Stack is empty
+
+    >>> stack['key']
+    Traceback (most recent call last):
+    ...
+    KeyError: 'key'
+    >>> print stack.get('key')
+    None
+    >>> print stack.get('key', 'default')
+    default
+
+    >>> del stack['key']
+    Traceback (most recent call last):
+    ...
+    IndexError: Stack is empty
+
+To use a BleedThroughDict you must push a named dict onto the
+stack. Now it acts just like a regular dict.
+
+    >>> stack.push('dict #1')
+    >>> stack['key'] = 'value'
+    >>> print stack['key']
+    value
+    >>> print stack.get('key', 'default')
+    value
+
+    >>> sorted(stack.items())
+    [('key', 'value')]
+
+You can pop a named dict off a stack: you'll get back a tuple
+(name, dict, opaque). (See below for what 'opaque' means.)
+
+    >>> print stack.pop()
+    ('dict #1', {'key': 'value'}, False)
+
+    >>> stack.push('dict #1')
+    >>> stack['key'] = 'value'
+    >>> stack['key2'] = 'value2'
+
+Push a second named dict onto the stack, and things start to get
+interesting.
+
+    >>> stack.push('dict #2')
+    >>> print stack['key']
+    value
+    >>> print stack['key2']
+    value2
+
+Setting a value will overwrite any preexisting value...
+
+    >>> stack['key'] = "A different value"
+    >>> print stack['key']
+    A different value
+    >>> sorted(stack.items())
+    [('key', 'A different value'), ('key2', 'value2')]
+
+But removing the new value will restore the old value.
+
+    >>> del stack['key']
+    >>> print stack['key']
+    value
+    >>> sorted(stack.items())
+    [('key', 'value'), ('key2', 'value2')]
+
+You can only delete a value that's present in a dict at the top of the
+stack.
+
+    >>> print stack['key']
+    value
+    >>> del stack['key']
+    Traceback (most recent call last):
+    ...
+    KeyError: 'key'
+
+Passing in a dictionary
+-----------------------
+
+By default. the 'push' method pushess an empty named dictionary onto
+the stack. You can pass in a dictionary object as well as a name, and
+a copy of that dictionary will be used instead.
+
+    >>> stack[1]
+    Traceback (most recent call last):
+    ...
+    KeyError: 1
+
+    >>> my_new_dict = {1: 2}
+    >>> stack.push('dict of numbers', my_new_dict)
+    >>> stack[1]
+    2
+    >>> stack[1] = 10
+
+Since the BleedThroughDict makes a copy, the original dictionary is
+not affected by changes to the BleedthroughStack.
+
+    >>> stack[1]
+    10
+    >>> my_new_dict[1]
+    2
+
+Opaque dictionaries
+-------------------
+
+When you push a dictionary onto the stack you can declare it to be
+opaque. Values from dictionaries lower in the stack will not bleed
+through an opaque dictionary.
+
+    >>> print stack['key']
+    value
+
+    >>> stack.push("An opaque dictionary", opaque=True)
+
+The dictionaries that define 'key' and 'key2' are still there...
+
+    >>> stack.dict_names
+    ['dict #1', 'dict #2', 'dict of numbers', 'An opaque dictionary']
+
+...but 'key' and 'key2' are no longer accessible.
+
+    >>> sorted(stack.items())
+    []
+
+    >>> stack['key']
+    Traceback (most recent call last):
+    ...
+    KeyError: 'key'
+
+    >>> stack['key2']
+    Traceback (most recent call last):
+    ...
+    KeyError: 'key2'
+
+    >>> stack['key'] = 'Brand new value'
+    >>> print stack['key']
+    Brand new value
+
+If you pop the opaque dictionary off the stack...
+
+    >>> print stack.pop()
+    ('An opaque dictionary', {'key': 'Brand new value'}, True)
+
+...'key' and 'key2' are visible again.
+
+    >>> sorted(stack.items())
+    [(1, 10), ('key', 'value'), ('key2', 'value2')]
+
+You can push a transparent dictionary on top of an opaque dictionary.
+Values from the opaque dictionary will still be visible, but values
+from below the opaque dictionary will not become visible.
+
+    >>> stack.push("An opaque dictionary", opaque=True)
+    >>> stack['key'] = 'Another value'
+
+    >>> stack.push("A transparent dictionary")
+
+    >>> sorted(stack.items())
+    [('key', 'Another value')]
+
+    >>> print stack['key']
+    Another value
+
+    >>> stack['key2']
+    Traceback (most recent call last):
+    ...
+    KeyError: 'key2'
+
+And of course you can push another opaque dictionary onto the stack,
+and stop values from bleeding through any further.
+
+    >>> stack.push("Another opaque dictionary", opaque=True)
+
+    >>> sorted(stack.items())
+    []
+
 implement_from_dict
 ===================
 

=== modified file 'src/lazr/restful/utils.py'
--- src/lazr/restful/utils.py	2010-01-11 14:38:47 +0000
+++ src/lazr/restful/utils.py	2010-01-14 10:11:11 +0000
@@ -4,6 +4,7 @@
 
 __metaclass__ = type
 __all__ = [
+    'BleedThroughDict',
     'camelcase_to_underscore_separated',
     'get_current_browser_request',
     'implement_from_dict',
@@ -28,6 +29,122 @@
 
 missing = object()
 
+
+class BleedThroughDict(object):
+    """A stack of named dictionaries that acts as a single dictionary.
+
+    If a key can't be found in the dictionary on top of the stack,
+    this class will look in the dictionary just below the top of the
+    stack, then the dictionary below that, and so on--until it
+    encounters the end of the stack or a dictionary that was defined
+    as 'opaque'.
+    """
+    missing = object()
+
+    def __init__(self):
+        """Initialize the bleed-through dictionary."""
+        self.stack = []
+
+    def push(self, name, dictionary=None, opaque=False):
+        """Pushes a dictionary onto the stack.
+
+        :arg name: The name of the dictionary to push.
+        :arg dictionary: The contents of the dictionary to push.
+        :arg opaque: If True, values will not 'bleed through' from
+                     dictionaries lower on the stack.
+        """
+        if name is None:
+            self.stack.append(name)
+            return
+        if dictionary is None:
+            dictionary = {}
+        self.stack.append((name, dict(dictionary), opaque))
+
+    def pop(self):
+        """Pop a tuple representing a dictionary from the stack.
+
+        :return: A 3-tuple (name, dict, opaque). 'dict' is the
+        contents of the dictionary. 'opaque' is whether or not the
+        dictionary was defined as opaque. This 3-tuple can be passed
+        in as the *args to append().
+        """
+        return self.stack.pop()
+
+    @property
+    def dict_names(self):
+        """Return the names of dictionaries in the stack.
+
+        The names are useful for passing into substack().
+        """
+        return [item[0] for item in self.stack if item is not None]
+
+    @property
+    def is_empty(self):
+        """Is the stack empty?"""
+        return len(self.stack) == 0
+
+    def __getitem__(self, key):
+        """Look up an item somewhere in the stack."""
+        if self.is_empty:
+            raise KeyError(key)
+        value = self._get_from_top_of_stack(key)
+        if value is missing:
+            raise KeyError(key)
+        return value
+
+    def get(self, key, default=None):
+        """Look up an item somewhere in the stack, with default fallback."""
+        if self.is_empty:
+            return default
+        value = self._get_from_top_of_stack(key)
+        if value is missing:
+            return default
+        return value
+
+    def items(self):
+        """Return a merged view of the items in the dictionary."""
+        # Find the last opaque dictionary in the stack. We'll get our
+        # values from it and every subsequent dictionary. If there are
+        # no opaque dictionaries, we'll get our values from the entire
+        # stack.
+        dictionaries = self.stack
+        for i in range(len(self.stack)-1, -1, -1):
+            name, dictionary, opaque = self.stack[i]
+            if opaque:
+                dictionaries = self.stack[i:]
+                break
+        final_dictionary = {}
+        for name, dictionary, opaque in dictionaries:
+            final_dictionary.update(dictionary)
+        return final_dictionary.items()
+
+    def __setitem__(self, key, value):
+        """Set a value in the dict at the top of the stack."""
+        if self.is_empty:
+            raise IndexError("Stack is empty")
+        self.stack[-1][1][key] = value
+
+    def __delitem__(self, key):
+        """Delete a value from the dict at the top of the stack."""
+        if self.is_empty:
+            raise IndexError("Stack is empty")
+        del self.stack[-1][1][key]
+
+    def _get_from_top_of_stack(self, key):
+        """Try to find the given key, starting from the top of the stack.
+
+        If the key is not present in the dict at the top of the stack,
+        this method tries the dict beneath it, and so on to the bottom.
+        """
+        value = missing
+        for i in range(len(self.stack) - 1, -1, -1):
+            name, dictionary, opaque = self.stack[i]
+            value = dictionary.get(key, missing)
+            if opaque or value is not missing:
+                break
+        return value
+
+
 def implement_from_dict(class_name, interface, values, superclass=object):
     """Return a class that implements an interface's attributes.