Alex Rivera | Logout

In python, how does the following AutoVivification class work?

Asked 2012-11-07T18:52:10.090
13

In searching for a way of working with nested dictionaries, I found the following code posted by nosklo, which I would like to have explained, please.

class AutoVivification(dict):
    """Implementation of perl's autovivification feature."""
    def __getitem__(self, item):
        try:
            return dict.__getitem__(self, item)
        except KeyError:
            value = self[item] = type(self)()
            return value

Testing:

a = AutoVivification()

a[1][2][3] = 4
a[1][3][3] = 5
a[1][2]['test'] = 6

print a

Output:

{1: {2: {'test': 6, 3: 4}, 3: {3: 5}}}

I'm a pretty newbie programmer. I have learned most of what I know on my own time on the side, with my only formal training being on Turbo Pascal back in high school. I understand and am able to use classes in simple ways, such as using __init__, class methods, and storing data within instances of the class with foo.man = 'choo'.

I have no idea how the series of square brackets get directed, correctly, through the class (I presume they are calling __getitem__ somehow) and don't understand how they each get handled so concisely without having to call the method three times individually.

I was under the impression that the (dict) in the class declaration would be handled by an __init__.

I've used try: except: before, though again, in quite simple ways. It looks to me like the try, when it runs, is calling a series of function __getitem__. I gather that if the current level's dictionary exists, the try will pass and go to the next dictionary. The except, I gather, runs when there's a KeyError but I haven't seen self used like that before. Self's being treated li

python dictionary autovivification
Edit
Report

1 Answer

19

Line by line:

class AutoVivification(dict):

We make a subclass of dict, so AutoVivification is a kind of dict, with some local changes.

def __getitem__(self, item):

The __getitem()__ hook is called whenever someone tries to access an item on the instance through [...] index lookups. So whenever someone does object[somekey], type(object).__getitem__(object, somekey) is called.

We'll skip the try for a moment, next line is:

 return dict.__getitem__(self, item)

This calls the unbound method __getitem__(), and passes in our own instance to it, together with the key. In other words, we call the original __getitem__ as defined by our parent class dict.

Now, we all know what happens if there is no item key in a dictionary, a KeyError is raised. This is where the try:, except KeyError combo comes in:

    try:
        return dict.__getitem__(self, item)
    except KeyError:
        value = self[item] = type(self)()
        return value

So, if the current instance (which is a sub-type of dict) doesn't have a given key, it'll catch the KeyError exception the original dict.__getitem__() method throws, and instead we create a new value, store that in self[item] and return that value.

Now, remember that self is a (subclass) of dict, so it's a dictionary. It thus can assign new values (for which it'll use the __setitem__ hook, incidentially), and in t

answered 2012-11-07T19:07:02.400

Your Answer